src/runtime/cheneygc.c

   1 /*
   2  * stop and copy GC based on Cheney's algorithm
   3  */
   4
   5 /*
   6  * This software is part of the SBCL system. See the README file for
   7  * more information.
   8  *
   9  * This software is derived from the CMU CL system, which was
  10  * written at Carnegie Mellon University and released into the
  11  * public domain. The software is in the public domain and is
  12  * provided with absolutely no warranty. See the COPYING and CREDITS
  13  * files for more information.
  14  */
  15
  16 #include <stdio.h>
  17 #include <sys/time.h>
  18 #include <sys/resource.h>
  19 #include <signal.h>
  20 #include "runtime.h"
  21 #include "sbcl.h"
  22 #include "os.h"
  23 #include "gc.h"
  24 #include "gc-internal.h"
  25 #include "globals.h"
  26 #include "interrupt.h"
  27 #include "validate.h"
  28 #include "lispregs.h"
  29 #include "interr.h"
  30 #include "genesis/static-symbols.h"
  31 #include "genesis/primitive-objects.h"
  32 #include "thread.h"
  33
  34 /* So you need to debug? */
  35 #if 0
  36 #define PRINTNOISE
  37 #define DEBUG_SPACE_PREDICATES
  38 #define DEBUG_SCAVENGE_VERBOSE
  39 #define DEBUG_COPY_VERBOSE
  40 #define DEBUG_CODE_GC
  41 #endif
  42
  43 lispobj *from_space;
  44 lispobj *from_space_free_pointer;
  45
  46 lispobj *new_space;
  47 lispobj *new_space_free_pointer;
  48
  49 static void scavenge_newspace(void);
  50 static void scavenge_interrupt_contexts(void);
  51 extern struct interrupt_data * global_interrupt_data;
  52
  53 extern unsigned long bytes_consed_between_gcs;
  54
  55 \f
  56 /* collecting garbage */
  57
  58 #ifdef PRINTNOISE
  59 static double
  60 tv_diff(struct timeval *x, struct timeval *y)
  61 {
  62     return (((double) x->tv_sec + (double) x->tv_usec * 1.0e-6) -
  63             ((double) y->tv_sec + (double) y->tv_usec * 1.0e-6));
  64 }
  65 #endif
  66
  67 #define BYTES_ZERO_BEFORE_END (1<<12)
  68
  69 /* FIXME do we need this?  Doesn't it duplicate lisp code in
  70  * scrub-control-stack? */
  71
  72 static void
  73 zero_stack(void)
  74 {
  75     u32 *ptr = (u32 *)current_control_stack_pointer;
  76  search:
  77     do {
  78         if (*ptr)
  79             goto fill;
  80         ptr++;
  81     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
  82     return;
  83  fill:
  84     do {
  85         *ptr++ = 0;
  86     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
  87
  88     goto search;
  89 }
  90
  91
  92 void *
  93 gc_general_alloc(int bytes, int unboxed_p, int quick_p) {
  94     lispobj *new=new_space_free_pointer;
  95     new_space_free_pointer+=(bytes/4);
  96     return new;
  97 }
  98
  99 lispobj  copy_large_unboxed_object(lispobj object, int nwords) {
 100     return copy_object(object,nwords);
 101 }
 102 lispobj  copy_unboxed_object(lispobj object, int nwords) {
 103     return copy_object(object,nwords);
 104 }
 105 lispobj  copy_large_object(lispobj object, int nwords) {
 106     return copy_object(object,nwords);
 107 }
 108
 109 /* Note: The generic GC interface we're implementing passes us a
 110  * last_generation argument. That's meaningless for us, since we're
 111  * not a generational GC. So we ignore it. */
 112 void
 113 collect_garbage(unsigned ignore)
 114 {
 115 #ifdef PRINTNOISE
 116     struct timeval start_tv, stop_tv;
 117     struct rusage start_rusage, stop_rusage;
 118     double real_time, system_time, user_time;
 119     double percent_retained, gc_rate;
 120     unsigned long size_discarded;
 121 #endif
 122     unsigned long size_retained;
 123     lispobj *current_static_space_free_pointer;
 124     unsigned long static_space_size;
 125     unsigned long control_stack_size, binding_stack_size;
 126     sigset_t tmp, old;
 127     struct thread *th=arch_os_get_current_thread();
 128     struct interrupt_data *data=
 129         th ? th->interrupt_data : global_interrupt_data;
 130
 131
 132 #ifdef PRINTNOISE
 133     printf("[Collecting garbage ... \n");
 134
 135     getrusage(RUSAGE_SELF, &start_rusage);
 136     gettimeofday(&start_tv, (struct timezone *) 0);
 137 #endif
 138
 139     /* it's possible that signals are blocked already if this was called
 140      * from a signal handler (e.g. with the sigsegv gc_trigger stuff) */
 141     sigemptyset(&tmp);
 142     sigaddset_blockable(&tmp);
 143     sigprocmask(SIG_BLOCK, &tmp, &old);
 144
 145     current_static_space_free_pointer =
 146         (lispobj *) ((unsigned long)
 147                      SymbolValue(STATIC_SPACE_FREE_POINTER,0));
 148
 149
 150     /* Set up from space and new space pointers. */
 151
 152     from_space = current_dynamic_space;
 153     from_space_free_pointer = dynamic_space_free_pointer;
 154
 155 #ifdef PRINTNOISE
 156     fprintf(stderr,"from_space = %lx\n",
 157             (unsigned long) current_dynamic_space);
 158 #endif
 159     if (current_dynamic_space == (lispobj *) DYNAMIC_0_SPACE_START)
 160         new_space = (lispobj *)DYNAMIC_1_SPACE_START;
 161     else if (current_dynamic_space == (lispobj *) DYNAMIC_1_SPACE_START)
 162         new_space = (lispobj *) DYNAMIC_0_SPACE_START;
 163     else {
 164         lose("GC lossage.  Current dynamic space is bogus!\n");
 165     }
 166     new_space_free_pointer = new_space;
 167
 168     /* Initialize the weak pointer list. */
 169     weak_pointers = (struct weak_pointer *) NULL;
 170
 171
 172     /* Scavenge all of the roots. */
 173 #ifdef PRINTNOISE
 174     printf("Scavenging interrupt contexts ...\n");
 175 #endif
 176     scavenge_interrupt_contexts();
 177
 178 #ifdef PRINTNOISE
 179     printf("Scavenging interrupt handlers (%d bytes) ...\n",
 180            (int)sizeof(interrupt_handlers));
 181 #endif
 182     scavenge((lispobj *) data->interrupt_handlers,
 183              sizeof(data->interrupt_handlers) / sizeof(lispobj));
 184
 185     /* _size quantities are in units of sizeof(lispobj) - i.e. 4 */
 186     control_stack_size =
 187         current_control_stack_pointer-
 188         (lispobj *)th->control_stack_start;
 189 #ifdef PRINTNOISE
 190     printf("Scavenging the control stack at %p (%ld words) ...\n",
 191            ((lispobj *)th->control_stack_start),
 192            control_stack_size);
 193 #endif
 194     scavenge(((lispobj *)th->control_stack_start), control_stack_size);
 195
 196
 197     binding_stack_size =
 198         current_binding_stack_pointer -
 199         (lispobj *)th->binding_stack_start;
 200 #ifdef PRINTNOISE
 201     printf("Scavenging the binding stack %x - %x (%d words) ...\n",
 202            th->binding_stack_start,current_binding_stack_pointer,
 203            (int)(binding_stack_size));
 204 #endif
 205     scavenge(((lispobj *)th->binding_stack_start), binding_stack_size);
 206
 207     static_space_size =
 208         current_static_space_free_pointer - (lispobj *) STATIC_SPACE_START;
 209 #ifdef PRINTNOISE
 210     printf("Scavenging static space %x - %x (%d words) ...\n",
 211            STATIC_SPACE_START,current_static_space_free_pointer,
 212            (int)(static_space_size));
 213 #endif
 214     scavenge(((lispobj *)STATIC_SPACE_START), static_space_size);
 215
 216     /* Scavenge newspace. */
 217 #ifdef PRINTNOISE
 218     printf("Scavenging new space (%d bytes) ...\n",
 219            (int)((new_space_free_pointer - new_space) * sizeof(lispobj)));
 220 #endif
 221     scavenge_newspace();
 222
 223
 224 #if defined(DEBUG_PRINT_GARBAGE)
 225     print_garbage(from_space, from_space_free_pointer);
 226 #endif
 227
 228     /* Scan the weak pointers. */
 229 #ifdef PRINTNOISE
 230     printf("Scanning weak pointers ...\n");
 231 #endif
 232     scan_weak_pointers();
 233
 234
 235     /* Flip spaces. */
 236 #ifdef PRINTNOISE
 237     printf("Flipping spaces ...\n");
 238 #endif
 239
 240     os_zero((os_vm_address_t) current_dynamic_space,
 241             (os_vm_size_t) DYNAMIC_SPACE_SIZE);
 242
 243     current_dynamic_space = new_space;
 244     dynamic_space_free_pointer = new_space_free_pointer;
 245
 246 #ifdef PRINTNOISE
 247     size_discarded = (from_space_free_pointer - from_space) * sizeof(lispobj);
 248 #endif
 249     size_retained = (new_space_free_pointer - new_space) * sizeof(lispobj);
 250
 251     /* Zero stack. */
 252 #ifdef PRINTNOISE
 253     printf("Zeroing empty part of control stack ...\n");
 254 #endif
 255     zero_stack();
 256     set_auto_gc_trigger(size_retained+bytes_consed_between_gcs);
 257     sigprocmask(SIG_SETMASK, &old, 0);
 258
 259
 260 #ifdef PRINTNOISE
 261     gettimeofday(&stop_tv, (struct timezone *) 0);
 262     getrusage(RUSAGE_SELF, &stop_rusage);
 263
 264     printf("done.]\n");
 265
 266     percent_retained = (((float) size_retained) /
 267                         ((float) size_discarded)) * 100.0;
 268
 269     printf("Total of %ld bytes out of %ld bytes retained (%3.2f%%).\n",
 270            size_retained, size_discarded, percent_retained);
 271
 272     real_time = tv_diff(&stop_tv, &start_tv);
 273     user_time = tv_diff(&stop_rusage.ru_utime, &start_rusage.ru_utime);
 274     system_time = tv_diff(&stop_rusage.ru_stime, &start_rusage.ru_stime);
 275
 276 #if 0
 277     printf("Statistics:\n");
 278     printf("%10.2f sec of real time\n", real_time);
 279     printf("%10.2f sec of user time,\n", user_time);
 280     printf("%10.2f sec of system time.\n", system_time);
 281 #else
 282     printf("Statistics: %10.2fs real, %10.2fs user, %10.2fs system.\n",
 283            real_time, user_time, system_time);
 284 #endif
 285
 286     gc_rate = ((float) size_retained / (float) (1<<20)) / real_time;
 287
 288     printf("%10.2f M bytes/sec collected.\n", gc_rate);
 289 #endif
 290     /* os_flush_icache((os_vm_address_t) 0, sizeof(unsigned long)); */
 291     /* Maybe FIXME: it's possible that we could significantly reduce
 292      * RSS by zeroing the from_space or madvise(MADV_DONTNEED) or
 293      * similar os-dependent tricks here */
 294 }
 295
 296 \f
 297 /* scavenging */
 298
 299 static void
 300 scavenge_newspace(void)
 301 {
 302     lispobj *here, *next;
 303
 304     here = new_space;
 305     while (here < new_space_free_pointer) {
 306         /*      printf("here=%lx, new_space_free_pointer=%lx\n",
 307                 here,new_space_free_pointer); */
 308         next = new_space_free_pointer;
 309         scavenge(here, next - here);
 310         here = next;
 311     }
 312     /* printf("done with newspace\n"); */
 313 }
 314 \f
 315 /* scavenging interrupt contexts */
 316
 317 static int boxed_registers[] = BOXED_REGISTERS;
 318
 319 static void
 320 scavenge_interrupt_context(os_context_t *context)
 321 {
 322     int i;
 323 #ifdef reg_LIP
 324     unsigned long lip;
 325     unsigned long lip_offset;
 326     int lip_register_pair;
 327 #endif
 328     unsigned long pc_code_offset;
 329 #ifdef ARCH_HAS_LINK_REGISTER
 330     unsigned long lr_code_offset;
 331 #endif
 332 #ifdef ARCH_HAS_NPC_REGISTER
 333     unsigned long npc_code_offset;
 334 #endif
 335 #ifdef DEBUG_SCAVENGE_VERBOSE
 336     fprintf(stderr, "Scavenging interrupt context at 0x%x\n",context);
 337 #endif
 338     /* Find the LIP's register pair and calculate its offset */
 339     /* before we scavenge the context. */
 340 #ifdef reg_LIP
 341     lip = *os_context_register_addr(context, reg_LIP);
 342     /*  0x7FFFFFFF or 0x7FFFFFFFFFFFFFFF ? */
 343     lip_offset = 0x7FFFFFFF;
 344     lip_register_pair = -1;
 345     for (i = 0; i < (sizeof(boxed_registers) / sizeof(int)); i++) {
 346         unsigned long reg;
 347         long offset;
 348         int index;
 349
 350         index = boxed_registers[i];
 351         reg = *os_context_register_addr(context, index);
 352         /* would be using PTR if not for integer length issues */
 353         if ((reg & ~((1L<<N_LOWTAG_BITS)-1)) <= lip) {
 354             offset = lip - reg;
 355             if (offset < lip_offset) {
 356                 lip_offset = offset;
 357                 lip_register_pair = index;
 358             }
 359         }
 360     }
 361 #endif /* reg_LIP */
 362
 363     /* Compute the PC's offset from the start of the CODE */
 364     /* register. */
 365     pc_code_offset =
 366         *os_context_pc_addr(context) -
 367         *os_context_register_addr(context, reg_CODE);
 368 #ifdef ARCH_HAS_NPC_REGISTER
 369     npc_code_offset =
 370         *os_context_npc_addr(context) -
 371         *os_context_register_addr(context, reg_CODE);
 372 #endif
 373 #ifdef ARCH_HAS_LINK_REGISTER
 374     lr_code_offset =
 375         *os_context_lr_addr(context) -
 376         *os_context_register_addr(context, reg_CODE);
 377 #endif
 378
 379     /* Scavenge all boxed registers in the context. */
 380     for (i = 0; i < (sizeof(boxed_registers) / sizeof(int)); i++) {
 381         int index;
 382         lispobj foo;
 383
 384         index = boxed_registers[i];
 385         foo = *os_context_register_addr(context,index);
 386         scavenge((lispobj *) &foo, 1);
 387         *os_context_register_addr(context,index) = foo;
 388
 389         /* this is unlikely to work as intended on bigendian
 390          * 64 bit platforms */
 391
 392         scavenge((lispobj *)
 393                  os_context_register_addr(context, index), 1);
 394     }
 395
 396 #ifdef reg_LIP
 397     /* Fix the LIP */
 398     *os_context_register_addr(context, reg_LIP) =
 399         *os_context_register_addr(context, lip_register_pair) + lip_offset;
 400 #endif /* reg_LIP */
 401
 402     /* Fix the PC if it was in from space */
 403     if (from_space_p(*os_context_pc_addr(context)))
 404         *os_context_pc_addr(context) =
 405             *os_context_register_addr(context, reg_CODE) + pc_code_offset;
 406 #ifdef ARCH_HAS_LINK_REGISTER
 407     /* Fix the LR ditto; important if we're being called from
 408      * an assembly routine that expects to return using blr, otherwise
 409      * harmless */
 410     if (from_space_p(*os_context_lr_addr(context)))
 411         *os_context_lr_addr(context) =
 412             *os_context_register_addr(context, reg_CODE) + lr_code_offset;
 413 #endif
 414
 415 #ifdef ARCH_HAS_NPC_REGISTER
 416     if (from_space_p(*os_context_npc_addr(context)))
 417         *os_context_npc_addr(context) =
 418             *os_context_register_addr(context, reg_CODE) + npc_code_offset;
 419 #endif
 420 }
 421
 422 void scavenge_interrupt_contexts(void)
 423 {
 424     int i, index;
 425     os_context_t *context;
 426
 427     struct thread *th=arch_os_get_current_thread();
 428     struct interrupt_data *data=
 429         th ? th->interrupt_data : global_interrupt_data;
 430
 431     index = fixnum_value(SymbolValue(FREE_INTERRUPT_CONTEXT_INDEX,0));
 432
 433
 434 #ifdef DEBUG_SCAVENGE_VERBOSE
 435     fprintf(stderr, "%d interrupt contexts to scan\n",index);
 436 #endif
 437     for (i = 0; i < index; i++) {
 438         context = th->interrupt_contexts[i];
 439         scavenge_interrupt_context(context);
 440     }
 441 }
 442
 443 \f
 444 /* debugging code */
 445
 446 void
 447 print_garbage(lispobj *from_space, lispobj *from_space_free_pointer)
 448 {
 449     lispobj *start;
 450     int total_words_not_copied;
 451
 452     printf("Scanning from space ...\n");
 453
 454     total_words_not_copied = 0;
 455     start = from_space;
 456     while (start < from_space_free_pointer) {
 457         lispobj object;
 458         int forwardp, type, nwords;
 459         lispobj header;
 460
 461         object = *start;
 462         forwardp = is_lisp_pointer(object) && new_space_p(object);
 463
 464         if (forwardp) {
 465             int tag;
 466             lispobj *pointer;
 467
 468             tag = lowtag_of(object);
 469
 470             switch (tag) {
 471             case LIST_POINTER_LOWTAG:
 472                 nwords = 2;
 473                 break;
 474             case INSTANCE_POINTER_LOWTAG:
 475                 printf("Don't know about instances yet!\n");
 476                 nwords = 1;
 477                 break;
 478             case FUN_POINTER_LOWTAG:
 479                 nwords = 1;
 480                 break;
 481             case OTHER_POINTER_LOWTAG:
 482                 pointer = (lispobj *) native_pointer(object);
 483                 header = *pointer;
 484                 type = widetag_of(header);
 485                 nwords = (sizetab[type])(pointer);
 486                 break;
 487             default: nwords=1;  /* shut yer whinging, gcc */
 488             }
 489         } else {
 490             type = widetag_of(object);
 491             nwords = (sizetab[type])(start);
 492             total_words_not_copied += nwords;
 493             printf("%4d words not copied at 0x%16lx; ",
 494                    nwords, (unsigned long) start);
 495             printf("Header word is 0x%08x\n",
 496                    (unsigned int) object);
 497         }
 498         start += nwords;
 499     }
 500     printf("%d total words not copied.\n", total_words_not_copied);
 501 }
 502
 503 \f
 504 /* code and code-related objects */
 505
 506 /* FIXME (1) this could probably be defined using something like
 507  *  sizeof(lispobj)*floor(sizeof(struct simple_fun)/sizeof(lispobj))
 508  *    -  FUN_POINTER_LOWTAG
 509  * as I'm reasonably sure that simple_fun->code must always be the
 510  * last slot in the object
 511
 512  * FIXME (2) it also appears in purify.c, and it has a different value
 513  * for SPARC users in that bit
 514  */
 515
 516 #define FUN_RAW_ADDR_OFFSET (6*sizeof(lispobj) - FUN_POINTER_LOWTAG)
 517
 518 /* Note: on the sparc we don't have to do anything special for fdefns, */
 519 /* 'cause the raw-addr has a function lowtag. */
 520 #ifndef LISP_FEATURE_SPARC
 521 static int
 522 scav_fdefn(lispobj *where, lispobj object)
 523 {
 524     struct fdefn *fdefn;
 525
 526     fdefn = (struct fdefn *)where;
 527
 528     if ((char *)(fdefn->fun + FUN_RAW_ADDR_OFFSET)
 529         == (char *)((unsigned long)(fdefn->raw_addr))) {
 530         scavenge(where + 1, sizeof(struct fdefn)/sizeof(lispobj) - 1);
 531         fdefn->raw_addr =
 532             (u32)  ((char *) LOW_WORD(fdefn->fun)) + FUN_RAW_ADDR_OFFSET;
 533         return sizeof(struct fdefn) / sizeof(lispobj);
 534     }
 535     else
 536         return 1;
 537 }
 538 #endif
 539
 540
 541 \f
 542 /* vector-like objects */
 543
 544 /* #define NWORDS(x,y) (CEILING((x),(y)) / (y)) */
 545
 546 static int
 547 scav_vector(lispobj *where, lispobj object)
 548 {
 549     if (HeaderValue(object) == subtype_VectorValidHashing) {
 550         *where =
 551             (subtype_VectorMustRehash<<N_WIDETAG_BITS) | SIMPLE_VECTOR_WIDETAG;
 552     }
 553
 554     return 1;
 555 }
 556
 557 \f
 558 /* weak pointers */
 559
 560 #define WEAK_POINTER_NWORDS \
 561         CEILING((sizeof(struct weak_pointer) / sizeof(lispobj)), 2)
 562
 563 static int
 564 scav_weak_pointer(lispobj *where, lispobj object)
 565 {
 566     /* Do not let GC scavenge the value slot of the weak pointer */
 567     /* (that is why it is a weak pointer).  Note:  we could use */
 568     /* the scav_unboxed method here. */
 569
 570     return WEAK_POINTER_NWORDS;
 571 }
 572
 573 \f
 574 /* initialization.  if gc_init can be moved to after core load, we could
 575  * combine these two functions */
 576
 577 void
 578 gc_init(void)
 579 {
 580     gc_init_tables();
 581     scavtab[SIMPLE_VECTOR_WIDETAG] = scav_vector;
 582     scavtab[WEAK_POINTER_WIDETAG] = scav_weak_pointer;
 583 }
 584
 585 void
 586 gc_initialize_pointers(void)
 587 {
 588     /* FIXME: We do nothing here.  We (briefly) misguidedly attempted
 589        to set current_dynamic_space to DYNAMIC_0_SPACE_START here,
 590        forgetting that (a) actually it could be the other and (b) it's
 591        set in coreparse.c anyway.  There's a FIXME note left here to
 592        note that current_dynamic_space is a violation of OAOO: we can
 593        tell which dynamic space we're currently in by looking at
 594        dynamic_space_free_pointer.  -- CSR, 2002-08-09 */
 595 }
 596
 597
 598
 599 \f
 600 /* noise to manipulate the gc trigger stuff */
 601
 602 /* Functions that substantially change the dynamic space free pointer
 603  * (collect_garbage, purify) are responsible also for resettting the
 604  * auto_gc_trigger */
 605 void set_auto_gc_trigger(os_vm_size_t dynamic_usage)
 606 {
 607     os_vm_address_t addr=(os_vm_address_t)current_dynamic_space
 608         + dynamic_usage;
 609     long length = DYNAMIC_SPACE_SIZE - dynamic_usage;
 610
 611     if (addr < (os_vm_address_t)dynamic_space_free_pointer) {
 612         fprintf(stderr,
 613            "set_auto_gc_trigger: tried to set gc trigger too low! (%d < %p)\n",
 614                 (unsigned int)dynamic_usage,
 615                 (os_vm_address_t)dynamic_space_free_pointer
 616                 - (os_vm_address_t)current_dynamic_space);
 617         lose("lost");
 618     }
 619     else if (length < 0) {
 620         fprintf(stderr,
 621                 "set_auto_gc_trigger: tried to set gc trigger too high! (%p)\n",
 622                 dynamic_usage);
 623         lose("lost");
 624     }
 625
 626     addr=os_round_up_to_page(addr);
 627     length=os_trunc_size_to_page(length);
 628
 629 #if defined(SUNOS) || defined(SOLARIS)
 630     os_invalidate(addr,length);
 631 #else
 632     os_protect(addr, length, 0);
 633 #endif
 634
 635     current_auto_gc_trigger = (lispobj *)addr;
 636 }
 637
 638 void clear_auto_gc_trigger(void)
 639 {
 640     if (current_auto_gc_trigger!=NULL){
 641 #if defined(SUNOS) || defined(SOLARIS)/* don't want to force whole space into swapping mode... */
 642         os_vm_address_t addr=(os_vm_address_t)current_auto_gc_trigger;
 643         os_vm_size_t length=
 644             DYNAMIC_SPACE_SIZE + (os_vm_address_t)current_dynamic_space - addr;
 645
 646         os_validate(addr,length);
 647 #else
 648         os_protect((os_vm_address_t)current_dynamic_space,
 649                    DYNAMIC_SPACE_SIZE,
 650                    OS_VM_PROT_ALL);
 651 #endif
 652
 653         current_auto_gc_trigger = NULL;
 654     }
 655 }