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