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