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
  33 /* So you need to debug? */
  34 #if 0
  35 #define PRINTNOISE
  36 #define DEBUG_SPACE_PREDICATES
  37 #define DEBUG_SCAVENGE_VERBOSE
  38 #define DEBUG_COPY_VERBOSE
  39 #define DEBUG_CODE_GC
  40 #endif
  41
  42 lispobj *from_space;
  43 lispobj *from_space_free_pointer;
  44
  45 lispobj *new_space;
  46 lispobj *new_space_free_pointer;
  47
  48 static void scavenge_newspace(void);
  49 static void scavenge_interrupt_contexts(void);
  50
  51 \f
  52 /* collecting garbage */
  53
  54 #ifdef PRINTNOISE
  55 static double
  56 tv_diff(struct timeval *x, struct timeval *y)
  57 {
  58     return (((double) x->tv_sec + (double) x->tv_usec * 1.0e-6) -
  59             ((double) y->tv_sec + (double) y->tv_usec * 1.0e-6));
  60 }
  61 #endif
  62
  63 #define BYTES_ZERO_BEFORE_END (1<<12)
  64
  65 /* FIXME do we need this?  Doesn't it duplicate lisp code in
  66  * scrub-control-stack? */
  67
  68 static void
  69 zero_stack(void)
  70 {
  71     u32 *ptr = (u32 *)current_control_stack_pointer;
  72  search:
  73     do {
  74         if (*ptr)
  75             goto fill;
  76         ptr++;
  77     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
  78     return;
  79  fill:
  80     do {
  81         *ptr++ = 0;
  82     } while (((unsigned long)ptr) & (BYTES_ZERO_BEFORE_END-1));
  83
  84     goto search;
  85 }
  86
  87
  88 void *
  89 gc_general_alloc(int bytes, int unboxed_p, int quick_p) {
  90     lispobj *new=new_space_free_pointer;
  91     new_space_free_pointer+=(bytes/4);
  92     return new;
  93 }
  94
  95 lispobj  copy_large_unboxed_object(lispobj object, int nwords) {
  96     return copy_object(object,nwords);
  97 }
  98 lispobj  copy_unboxed_object(lispobj object, int nwords) {
  99     return copy_object(object,nwords);
 100 }
 101 lispobj  copy_large_object(lispobj object, int nwords) {
 102     return copy_object(object,nwords);
 103 }
 104
 105 /* Note: The generic GC interface we're implementing passes us a
 106  * last_generation argument. That's meaningless for us, since we're
 107  * not a generational GC. So we ignore it. */
 108 void
 109 collect_garbage(unsigned ignore)
 110 {
 111 #ifdef PRINTNOISE
 112     struct timeval start_tv, stop_tv;
 113     struct rusage start_rusage, stop_rusage;
 114     double real_time, system_time, user_time;
 115     double percent_retained, gc_rate;
 116     unsigned long size_discarded;
 117     unsigned long size_retained;
 118 #endif
 119     lispobj *current_static_space_free_pointer;
 120     unsigned long static_space_size;
 121     unsigned long control_stack_size, binding_stack_size;
 122     sigset_t tmp, old;
 123
 124 #ifdef PRINTNOISE
 125     printf("[Collecting garbage ... \n");
 126
 127     getrusage(RUSAGE_SELF, &start_rusage);
 128     gettimeofday(&start_tv, (struct timezone *) 0);
 129 #endif
 130
 131     sigemptyset(&tmp);
 132     sigaddset_blockable(&tmp);
 133     sigprocmask(SIG_BLOCK, &tmp, &old);
 134
 135     current_static_space_free_pointer =
 136         (lispobj *) ((unsigned long)
 137                      SymbolValue(STATIC_SPACE_FREE_POINTER));
 138
 139
 140     /* Set up from space and new space pointers. */
 141
 142     from_space = current_dynamic_space;
 143     from_space_free_pointer = dynamic_space_free_pointer;
 144
 145 #ifdef PRINTNOISE
 146     fprintf(stderr,"from_space = %lx\n",
 147             (unsigned long) current_dynamic_space);
 148 #endif
 149     if (current_dynamic_space == (lispobj *) DYNAMIC_0_SPACE_START)
 150         new_space = (lispobj *)DYNAMIC_1_SPACE_START;
 151     else if (current_dynamic_space == (lispobj *) DYNAMIC_1_SPACE_START)
 152         new_space = (lispobj *) DYNAMIC_0_SPACE_START;
 153     else {
 154         lose("GC lossage.  Current dynamic space is bogus!\n");
 155     }
 156     new_space_free_pointer = new_space;
 157
 158     /* Initialize the weak pointer list. */
 159     weak_pointers = (struct weak_pointer *) NULL;
 160
 161
 162     /* Scavenge all of the roots. */
 163 #ifdef PRINTNOISE
 164     printf("Scavenging interrupt contexts ...\n");
 165 #endif
 166     scavenge_interrupt_contexts();
 167
 168 #ifdef PRINTNOISE
 169     printf("Scavenging interrupt handlers (%d bytes) ...\n",
 170            (int)sizeof(interrupt_handlers));
 171 #endif
 172     scavenge((lispobj *) interrupt_handlers,
 173              sizeof(interrupt_handlers) / sizeof(lispobj));
 174
 175     /* _size quantities are in units of sizeof(lispobj) - i.e. 4 */
 176     control_stack_size =
 177         current_control_stack_pointer-
 178         (lispobj *)CONTROL_STACK_START;
 179 #ifdef PRINTNOISE
 180     printf("Scavenging the control stack at %p (%ld words) ...\n",
 181            ((lispobj *)CONTROL_STACK_START),
 182            control_stack_size);
 183 #endif
 184     scavenge(((lispobj *)CONTROL_STACK_START), control_stack_size);
 185
 186
 187     binding_stack_size =
 188         current_binding_stack_pointer -
 189         (lispobj *)BINDING_STACK_START;
 190 #ifdef PRINTNOISE
 191     printf("Scavenging the binding stack %x - %x (%d words) ...\n",
 192            BINDING_STACK_START,current_binding_stack_pointer,
 193            (int)(binding_stack_size));
 194 #endif
 195     scavenge(((lispobj *)BINDING_STACK_START), binding_stack_size);
 196
 197     static_space_size =
 198         current_static_space_free_pointer - (lispobj *) STATIC_SPACE_START;
 199 #ifdef PRINTNOISE
 200     printf("Scavenging static space %x - %x (%d words) ...\n",
 201            STATIC_SPACE_START,current_static_space_free_pointer,
 202            (int)(static_space_size));
 203 #endif
 204     scavenge(((lispobj *)STATIC_SPACE_START), static_space_size);
 205
 206     /* Scavenge newspace. */
 207 #ifdef PRINTNOISE
 208     printf("Scavenging new space (%d bytes) ...\n",
 209            (int)((new_space_free_pointer - new_space) * sizeof(lispobj)));
 210 #endif
 211     scavenge_newspace();
 212
 213
 214 #if defined(DEBUG_PRINT_GARBAGE)
 215     print_garbage(from_space, from_space_free_pointer);
 216 #endif
 217
 218     /* Scan the weak pointers. */
 219 #ifdef PRINTNOISE
 220     printf("Scanning weak pointers ...\n");
 221 #endif
 222     scan_weak_pointers();
 223
 224
 225     /* Flip spaces. */
 226 #ifdef PRINTNOISE
 227     printf("Flipping spaces ...\n");
 228 #endif
 229
 230     os_zero((os_vm_address_t) current_dynamic_space,
 231             (os_vm_size_t) DYNAMIC_SPACE_SIZE);
 232
 233     current_dynamic_space = new_space;
 234     dynamic_space_free_pointer = new_space_free_pointer;
 235
 236 #ifdef PRINTNOISE
 237     size_discarded = (from_space_free_pointer - from_space) * sizeof(lispobj);
 238     size_retained = (new_space_free_pointer - new_space) * sizeof(lispobj);
 239 #endif
 240
 241     /* Zero stack. */
 242 #ifdef PRINTNOISE
 243     printf("Zeroing empty part of control stack ...\n");
 244 #endif
 245     zero_stack();
 246
 247     sigprocmask(SIG_SETMASK, &old, 0);
 248
 249
 250 #ifdef PRINTNOISE
 251     gettimeofday(&stop_tv, (struct timezone *) 0);
 252     getrusage(RUSAGE_SELF, &stop_rusage);
 253
 254     printf("done.]\n");
 255
 256     percent_retained = (((float) size_retained) /
 257                         ((float) size_discarded)) * 100.0;
 258
 259     printf("Total of %ld bytes out of %ld bytes retained (%3.2f%%).\n",
 260            size_retained, size_discarded, percent_retained);
 261
 262     real_time = tv_diff(&stop_tv, &start_tv);
 263     user_time = tv_diff(&stop_rusage.ru_utime, &start_rusage.ru_utime);
 264     system_time = tv_diff(&stop_rusage.ru_stime, &start_rusage.ru_stime);
 265
 266 #if 0
 267     printf("Statistics:\n");
 268     printf("%10.2f sec of real time\n", real_time);
 269     printf("%10.2f sec of user time,\n", user_time);
 270     printf("%10.2f sec of system time.\n", system_time);
 271 #else
 272     printf("Statistics: %10.2fs real, %10.2fs user, %10.2fs system.\n",
 273            real_time, user_time, system_time);
 274 #endif
 275
 276     gc_rate = ((float) size_retained / (float) (1<<20)) / real_time;
 277
 278     printf("%10.2f M bytes/sec collected.\n", gc_rate);
 279 #endif
 280     /* os_flush_icache((os_vm_address_t) 0, sizeof(unsigned long)); */
 281     /* Maybe FIXME: it's possible that we could significantly reduce
 282      * RSS by zeroing the from_space or madvise(MADV_DONTNEED) or
 283      * similar os-dependent tricks here */
 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 or 0x7FFFFFFFFFFFFFFF ? */
 333     lip_offset = 0x7FFFFFFF;
 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     index = fixnum_value(SymbolValue(FREE_INTERRUPT_CONTEXT_INDEX));
 418
 419 #ifdef DEBUG_SCAVENGE_VERBOSE
 420     fprintf(stderr, "%d interrupt contexts to scan\n",index);
 421 #endif
 422     for (i = 0; i < index; i++) {
 423         context = lisp_interrupt_contexts[i];
 424         scavenge_interrupt_context(context);
 425     }
 426 }
 427
 428 \f
 429 /* debugging code */
 430
 431 void
 432 print_garbage(lispobj *from_space, lispobj *from_space_free_pointer)
 433 {
 434     lispobj *start;
 435     int total_words_not_copied;
 436
 437     printf("Scanning from space ...\n");
 438
 439     total_words_not_copied = 0;
 440     start = from_space;
 441     while (start < from_space_free_pointer) {
 442         lispobj object;
 443         int forwardp, type, nwords;
 444         lispobj header;
 445
 446         object = *start;
 447         forwardp = is_lisp_pointer(object) && new_space_p(object);
 448
 449         if (forwardp) {
 450             int tag;
 451             lispobj *pointer;
 452
 453             tag = lowtag_of(object);
 454
 455             switch (tag) {
 456             case LIST_POINTER_LOWTAG:
 457                 nwords = 2;
 458                 break;
 459             case INSTANCE_POINTER_LOWTAG:
 460                 printf("Don't know about instances yet!\n");
 461                 nwords = 1;
 462                 break;
 463             case FUN_POINTER_LOWTAG:
 464                 nwords = 1;
 465                 break;
 466             case OTHER_POINTER_LOWTAG:
 467                 pointer = (lispobj *) native_pointer(object);
 468                 header = *pointer;
 469                 type = widetag_of(header);
 470                 nwords = (sizetab[type])(pointer);
 471                 break;
 472             default: nwords=1;  /* shut yer whinging, gcc */
 473             }
 474         } else {
 475             type = widetag_of(object);
 476             nwords = (sizetab[type])(start);
 477             total_words_not_copied += nwords;
 478             printf("%4d words not copied at 0x%16lx; ",
 479                    nwords, (unsigned long) start);
 480             printf("Header word is 0x%08x\n",
 481                    (unsigned int) object);
 482         }
 483         start += nwords;
 484     }
 485     printf("%d total words not copied.\n", total_words_not_copied);
 486 }
 487
 488 \f
 489 /* code and code-related objects */
 490
 491 /* FIXME (1) this could probably be defined using something like
 492  *  sizeof(lispobj)*floor(sizeof(struct simple_fun)/sizeof(lispobj))
 493  *    -  FUN_POINTER_LOWTAG
 494  * as I'm reasonably sure that simple_fun->code must always be the
 495  * last slot in the object
 496
 497  * FIXME (2) it also appears in purify.c, and it has a different value
 498  * for SPARC users in that bit
 499  */
 500
 501 #define FUN_RAW_ADDR_OFFSET (6*sizeof(lispobj) - FUN_POINTER_LOWTAG)
 502
 503 /* Note: on the sparc we don't have to do anything special for fdefns, */
 504 /* 'cause the raw-addr has a function lowtag. */
 505 #ifndef LISP_FEATURE_SPARC
 506 static int
 507 scav_fdefn(lispobj *where, lispobj object)
 508 {
 509     struct fdefn *fdefn;
 510
 511     fdefn = (struct fdefn *)where;
 512
 513     if ((char *)(fdefn->fun + FUN_RAW_ADDR_OFFSET)
 514         == (char *)((unsigned long)(fdefn->raw_addr))) {
 515         scavenge(where + 1, sizeof(struct fdefn)/sizeof(lispobj) - 1);
 516         fdefn->raw_addr =
 517             (u32)  ((char *) LOW_WORD(fdefn->fun)) + FUN_RAW_ADDR_OFFSET;
 518         return sizeof(struct fdefn) / sizeof(lispobj);
 519     }
 520     else
 521         return 1;
 522 }
 523 #endif
 524
 525
 526 \f
 527 /* vector-like objects */
 528
 529 /* #define NWORDS(x,y) (CEILING((x),(y)) / (y)) */
 530
 531 static int
 532 scav_vector(lispobj *where, lispobj object)
 533 {
 534     if (HeaderValue(object) == subtype_VectorValidHashing) {
 535         *where =
 536             (subtype_VectorMustRehash<<N_WIDETAG_BITS) | SIMPLE_VECTOR_WIDETAG;
 537     }
 538
 539     return 1;
 540 }
 541
 542 \f
 543 /* weak pointers */
 544
 545 #define WEAK_POINTER_NWORDS \
 546         CEILING((sizeof(struct weak_pointer) / sizeof(lispobj)), 2)
 547
 548 static int
 549 scav_weak_pointer(lispobj *where, lispobj object)
 550 {
 551     /* Do not let GC scavenge the value slot of the weak pointer */
 552     /* (that is why it is a weak pointer).  Note:  we could use */
 553     /* the scav_unboxed method here. */
 554
 555     return WEAK_POINTER_NWORDS;
 556 }
 557
 558 \f
 559 /* initialization.  if gc_init can be moved to after core load, we could
 560  * combine these two functions */
 561
 562 void
 563 gc_init(void)
 564 {
 565     gc_init_tables();
 566     scavtab[SIMPLE_VECTOR_WIDETAG] = scav_vector;
 567     scavtab[WEAK_POINTER_WIDETAG] = scav_weak_pointer;
 568 }
 569
 570 void
 571 gc_initialize_pointers(void)
 572 {
 573     /* FIXME: We do nothing here.  We (briefly) misguidedly attempted
 574        to set current_dynamic_space to DYNAMIC_0_SPACE_START here,
 575        forgetting that (a) actually it could be the other and (b) it's
 576        set in coreparse.c anyway.  There's a FIXME note left here to
 577        note that current_dynamic_space is a violation of OAOO: we can
 578        tell which dynamic space we're currently in by looking at
 579        dynamic_space_free_pointer.  -- CSR, 2002-08-09 */
 580 }
 581
 582
 583
 584 \f
 585 /* noise to manipulate the gc trigger stuff */
 586
 587 void set_auto_gc_trigger(os_vm_size_t dynamic_usage)
 588 {
 589     os_vm_address_t addr=(os_vm_address_t)current_dynamic_space
 590         + dynamic_usage;
 591
 592     long length = DYNAMIC_SPACE_SIZE - dynamic_usage;
 593
 594     if (addr < (os_vm_address_t)dynamic_space_free_pointer) {
 595         fprintf(stderr,
 596            "set_auto_gc_trigger: tried to set gc trigger too low! (%d < %p)\n",
 597                 (unsigned int)dynamic_usage,
 598                 (os_vm_address_t)dynamic_space_free_pointer
 599                 - (os_vm_address_t)current_dynamic_space);
 600         lose("lost");
 601     }
 602     else if (length < 0) {
 603         fprintf(stderr,
 604                 "set_auto_gc_trigger: tried to set gc trigger too high! (%p)\n",
 605                 dynamic_usage);
 606         lose("lost");
 607     }
 608
 609     addr=os_round_up_to_page(addr);
 610     length=os_trunc_size_to_page(length);
 611
 612 #if defined(SUNOS) || defined(SOLARIS)
 613     os_invalidate(addr,length);
 614 #else
 615     os_protect(addr, length, 0);
 616 #endif
 617
 618     current_auto_gc_trigger = (lispobj *)addr;
 619 }
 620
 621 void clear_auto_gc_trigger(void)
 622 {
 623     if (current_auto_gc_trigger!=NULL){
 624 #if defined(SUNOS) || defined(SOLARIS)/* don't want to force whole space into swapping mode... */
 625         os_vm_address_t addr=(os_vm_address_t)current_auto_gc_trigger;
 626         os_vm_size_t length=
 627             DYNAMIC_SPACE_SIZE + (os_vm_address_t)current_dynamic_space - addr;
 628
 629         os_validate(addr,length);
 630 #else
 631         os_protect((os_vm_address_t)current_dynamic_space,
 632                    DYNAMIC_SPACE_SIZE,
 633                    OS_VM_PROT_ALL);
 634 #endif
 635
 636         current_auto_gc_trigger = NULL;
 637     }
 638 }