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