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