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 /* This does nothing. It's only to satisfy a reference from gc-common. */
  51 char gc_coalesce_string_literals = 0;
  52
  53 static void scavenge_newspace(void);
  54
  55 \f
  56 /* collecting garbage */
  57
  58 #ifdef PRINTNOISE
  59 static double
  60 tv_diff(struct timeval *x, struct timeval *y)
  61 {
  62     return (((double) x->tv_sec + (double) x->tv_usec * 1.0e-6) -
  63             ((double) y->tv_sec + (double) y->tv_usec * 1.0e-6));
  64 }
  65 #endif
  66
  67 void *
  68 gc_general_alloc(word_t bytes, int page_type_flag, int quick_p) {
  69     lispobj *new=new_space_free_pointer;
  70     new_space_free_pointer+=(bytes/N_WORD_BYTES);
  71     return new;
  72 }
  73
  74 lispobj  copy_large_unboxed_object(lispobj object, sword_t nwords) {
  75     return copy_object(object,nwords);
  76 }
  77 lispobj  copy_unboxed_object(lispobj object, sword_t nwords) {
  78     return copy_object(object,nwords);
  79 }
  80 lispobj  copy_large_object(lispobj object, sword_t nwords) {
  81     return copy_object(object,nwords);
  82 }
  83
  84 /* Note: The generic GC interface we're implementing passes us a
  85  * last_generation argument. That's meaningless for us, since we're
  86  * not a generational GC. So we ignore it. */
  87 void
  88 collect_garbage(generation_index_t ignore)
  89 {
  90 #ifdef PRINTNOISE
  91     struct timeval start_tv, stop_tv;
  92     struct rusage start_rusage, stop_rusage;
  93     double real_time, system_time, user_time;
  94     double percent_retained, gc_rate;
  95     unsigned long size_discarded;
  96 #endif
  97     unsigned long size_retained;
  98     lispobj *current_static_space_free_pointer;
  99     sigset_t old;
 100     struct thread *th=arch_os_get_current_thread();
 101
 102 #ifdef PRINTNOISE
 103     printf("[Collecting garbage ... \n");
 104
 105     getrusage(RUSAGE_SELF, &start_rusage);
 106     gettimeofday(&start_tv, (struct timezone *) 0);
 107 #endif
 108
 109     /* it's possible that signals are blocked already if this was called
 110      * from a signal handler (e.g. with the sigsegv gc_trigger stuff) */
 111     block_blockable_signals(&old);
 112
 113     current_static_space_free_pointer =
 114         (lispobj *) ((unsigned long)
 115                      SymbolValue(STATIC_SPACE_FREE_POINTER,0));
 116
 117
 118     /* Set up from space and new space pointers. */
 119
 120     from_space = current_dynamic_space;
 121     from_space_free_pointer = dynamic_space_free_pointer;
 122
 123 #ifdef PRINTNOISE
 124     fprintf(stderr,"from_space = %lx\n",
 125             (unsigned long) current_dynamic_space);
 126 #endif
 127     if (current_dynamic_space == (lispobj *) DYNAMIC_0_SPACE_START)
 128         new_space = (lispobj *)DYNAMIC_1_SPACE_START;
 129     else if (current_dynamic_space == (lispobj *) DYNAMIC_1_SPACE_START)
 130         new_space = (lispobj *) DYNAMIC_0_SPACE_START;
 131     else {
 132         lose("GC lossage.  Current dynamic space is bogus!\n");
 133     }
 134     new_space_free_pointer = new_space;
 135
 136     /* Initialize the weak pointer list. */
 137     weak_pointers = (struct weak_pointer *) NULL;
 138
 139
 140     /* Scavenge all of the roots. */
 141 #ifdef PRINTNOISE
 142     printf("Scavenging interrupt contexts ...\n");
 143 #endif
 144     scavenge_interrupt_contexts(th);
 145
 146 #ifdef PRINTNOISE
 147     printf("Scavenging interrupt handlers (%d bytes) ...\n",
 148            (int)sizeof(interrupt_handlers));
 149 #endif
 150     scavenge((lispobj *) interrupt_handlers,
 151              sizeof(interrupt_handlers) / sizeof(lispobj));
 152
 153 #ifdef PRINTNOISE
 154     printf("Scavenging the control stack ...\n");
 155 #endif
 156     scavenge_control_stack(th);
 157
 158     scav_binding_stack((lispobj*)th->binding_stack_start,
 159                        (lispobj*)get_binding_stack_pointer(th));
 160
 161 #ifdef PRINTNOISE
 162     printf("Scavenging static space %p - %p (%d words) ...\n",
 163            (void*)STATIC_SPACE_START,
 164            current_static_space_free_pointer,
 165            (int)(current_static_space_free_pointer
 166                  - (lispobj *) STATIC_SPACE_START));
 167 #endif
 168     heap_scavenge(((lispobj *)STATIC_SPACE_START),
 169                   current_static_space_free_pointer);
 170
 171     /* Scavenge newspace. */
 172 #ifdef PRINTNOISE
 173     printf("Scavenging new space (%d bytes) ...\n",
 174            (int)((new_space_free_pointer - new_space) * sizeof(lispobj)));
 175 #endif
 176     scavenge_newspace();
 177
 178
 179 #if defined(DEBUG_PRINT_GARBAGE)
 180     print_garbage(from_space, from_space_free_pointer);
 181 #endif
 182
 183     /* Scan the weak pointers. */
 184 #ifdef PRINTNOISE
 185     printf("Scanning weak hash tables ...\n");
 186 #endif
 187     scan_weak_hash_tables();
 188
 189     /* Scan the weak pointers. */
 190 #ifdef PRINTNOISE
 191     printf("Scanning weak pointers ...\n");
 192 #endif
 193     scan_weak_pointers();
 194
 195     /* Flip spaces. */
 196 #ifdef PRINTNOISE
 197     printf("Flipping spaces ...\n");
 198 #endif
 199
 200     /* Maybe FIXME: it's possible that we could significantly reduce
 201      * RSS by zeroing the from_space or madvise(MADV_DONTNEED) or
 202      * similar os-dependent tricks here */
 203 #ifdef LISP_FEATURE_HPUX
 204     /* hpux cant handle unmapping areas that are not 100% mapped */
 205     clear_auto_gc_trigger();
 206 #endif
 207     os_zero((os_vm_address_t) from_space,
 208             (os_vm_size_t) dynamic_space_size);
 209
 210     current_dynamic_space = new_space;
 211     dynamic_space_free_pointer = new_space_free_pointer;
 212
 213 #ifdef PRINTNOISE
 214     size_discarded = (from_space_free_pointer - from_space) * sizeof(lispobj);
 215 #endif
 216     size_retained = (new_space_free_pointer - new_space) * sizeof(lispobj);
 217
 218     os_flush_icache((os_vm_address_t)new_space, size_retained);
 219
 220     /* Zero stack. */
 221 #ifdef PRINTNOISE
 222     printf("Zeroing empty part of control stack ...\n");
 223 #endif
 224     scrub_control_stack();
 225     set_auto_gc_trigger(size_retained+bytes_consed_between_gcs);
 226     thread_sigmask(SIG_SETMASK, &old, 0);
 227
 228
 229 #ifdef PRINTNOISE
 230     gettimeofday(&stop_tv, (struct timezone *) 0);
 231     getrusage(RUSAGE_SELF, &stop_rusage);
 232
 233     printf("done.]\n");
 234
 235     percent_retained = (((float) size_retained) /
 236                         ((float) size_discarded)) * 100.0;
 237
 238     printf("Total of %ld bytes out of %ld bytes retained (%3.2f%%).\n",
 239            size_retained, size_discarded, percent_retained);
 240
 241     real_time = tv_diff(&stop_tv, &start_tv);
 242     user_time = tv_diff(&stop_rusage.ru_utime, &start_rusage.ru_utime);
 243     system_time = tv_diff(&stop_rusage.ru_stime, &start_rusage.ru_stime);
 244
 245     printf("Statistics: %10.2fs real, %10.2fs user, %10.2fs system.\n",
 246            real_time, user_time, system_time);
 247
 248     gc_rate = ((float) size_retained / (float) (1<<20)) / real_time;
 249
 250     printf("%10.2f M bytes/sec collected.\n", gc_rate);
 251 #endif
 252 }
 253
 254 \f
 255 /* scavenging */
 256
 257 static void
 258 scavenge_newspace(void)
 259 {
 260     lispobj *here, *next;
 261
 262     here = new_space;
 263     while (here < new_space_free_pointer) {
 264         /*      printf("here=%lx, new_space_free_pointer=%lx\n",
 265                 here,new_space_free_pointer); */
 266         next = new_space_free_pointer;
 267         heap_scavenge(here, next);
 268         scav_weak_hash_tables();
 269         here = next;
 270     }
 271     /* printf("done with newspace\n"); */
 272 }
 273 \f
 274 /* debugging code */
 275
 276 void
 277 print_garbage(lispobj *from_space, lispobj *from_space_free_pointer)
 278 {
 279     lispobj *start;
 280     int total_words_not_copied;
 281
 282     printf("Scanning from space ...\n");
 283
 284     total_words_not_copied = 0;
 285     start = from_space;
 286     while (start < from_space_free_pointer) {
 287         lispobj object;
 288         int forwardp, type, nwords;
 289         lispobj header;
 290
 291         object = *start;
 292         forwardp = is_lisp_pointer(object) && new_space_p(object);
 293
 294         if (forwardp) {
 295             int tag;
 296             lispobj *pointer;
 297
 298             tag = lowtag_of(object);
 299
 300             switch (tag) {
 301             case LIST_POINTER_LOWTAG:
 302                 nwords = 2;
 303                 break;
 304             case INSTANCE_POINTER_LOWTAG:
 305                 printf("Don't know about instances yet!\n");
 306                 nwords = 1;
 307                 break;
 308             case FUN_POINTER_LOWTAG:
 309                 nwords = 1;
 310                 break;
 311             case OTHER_POINTER_LOWTAG:
 312                 pointer = native_pointer(object);
 313                 header = *pointer;
 314                 type = widetag_of(header);
 315                 nwords = (sizetab[type])(pointer);
 316                 break;
 317             default: nwords=1;  /* shut yer whinging, gcc */
 318             }
 319         } else {
 320             type = widetag_of(object);
 321             nwords = (sizetab[type])(start);
 322             total_words_not_copied += nwords;
 323             printf("%4d words not copied at 0x%16lx; ",
 324                    nwords, (unsigned long) start);
 325             printf("Header word is 0x%08x\n",
 326                    (unsigned int) object);
 327         }
 328         start += nwords;
 329     }
 330     printf("%d total words not copied.\n", total_words_not_copied);
 331 }
 332
 333 \f
 334 /* weak pointers */
 335
 336 static sword_t
 337 scav_weak_pointer(lispobj *where, lispobj object)
 338 {
 339     /* Do not let GC scavenge the value slot of the weak pointer */
 340     /* (that is why it is a weak pointer).  Note:  we could use */
 341     /* the scav_unboxed method here. */
 342
 343     return WEAK_POINTER_NWORDS;
 344 }
 345 \f
 346 lispobj *
 347 search_read_only_space(void *pointer)
 348 {
 349     lispobj* start = (lispobj*)READ_ONLY_SPACE_START;
 350     lispobj* end = (lispobj*)SymbolValue(READ_ONLY_SPACE_FREE_POINTER,0);
 351     if ((pointer < (void *)start) || (pointer >= (void *)end))
 352         return NULL;
 353     return gc_search_space(start, pointer);
 354 }
 355
 356 lispobj *
 357 search_static_space(void *pointer)
 358 {
 359     lispobj* start = (lispobj*)STATIC_SPACE_START;
 360     lispobj* end = (lispobj*)SymbolValue(STATIC_SPACE_FREE_POINTER,0);
 361     if ((pointer < (void *)start) || (pointer >= (void *)end))
 362         return NULL;
 363     return gc_search_space(start, pointer);
 364 }
 365
 366 lispobj *
 367 search_dynamic_space(void *pointer)
 368 {
 369     lispobj *start = (lispobj *) current_dynamic_space;
 370     lispobj *end = (lispobj *) dynamic_space_free_pointer;
 371     if ((pointer < (void *)start) || (pointer >= (void *)end))
 372         return NULL;
 373     return gc_search_space(start, pointer);
 374 }
 375 \f
 376 /* initialization.  if gc_init can be moved to after core load, we could
 377  * combine these two functions */
 378
 379 void
 380 gc_init(void)
 381 {
 382     scavtab[WEAK_POINTER_WIDETAG] = scav_weak_pointer;
 383 }
 384
 385 void
 386 gc_initialize_pointers(void)
 387 {
 388     /* FIXME: We do nothing here.  We (briefly) misguidedly attempted
 389        to set current_dynamic_space to DYNAMIC_0_SPACE_START here,
 390        forgetting that (a) actually it could be the other and (b) it's
 391        set in coreparse.c anyway.  There's a FIXME note left here to
 392        note that current_dynamic_space is a violation of OAOO: we can
 393        tell which dynamic space we're currently in by looking at
 394        dynamic_space_free_pointer.  -- CSR, 2002-08-09 */
 395 }
 396
 397
 398
 399 \f
 400 /* noise to manipulate the gc trigger stuff */
 401
 402 /* Functions that substantially change the dynamic space free pointer
 403  * (collect_garbage, purify) are responsible also for resetting the
 404  * auto_gc_trigger */
 405 void set_auto_gc_trigger(os_vm_size_t dynamic_usage)
 406 {
 407     os_vm_address_t addr;
 408     os_vm_size_t length;
 409
 410     addr = os_round_up_to_page((os_vm_address_t)current_dynamic_space
 411                                + dynamic_usage);
 412     if (addr < (os_vm_address_t)dynamic_space_free_pointer)
 413         lose("set_auto_gc_trigger: tried to set gc trigger too low! (%ld < 0x%08lx)\n",
 414              (unsigned long)dynamic_usage,
 415              (unsigned long)((os_vm_address_t)dynamic_space_free_pointer
 416                              - (os_vm_address_t)current_dynamic_space));
 417
 418     if (dynamic_usage > dynamic_space_size)
 419         lose("set_auto_gc_trigger: tried to set gc trigger too high! (0x%08lx)\n",
 420              (unsigned long)dynamic_usage);
 421     length = os_trunc_size_to_page(dynamic_space_size - dynamic_usage);
 422
 423 #if defined(SUNOS) || defined(SOLARIS) || defined(LISP_FEATURE_HPUX)
 424     os_invalidate(addr, length);
 425 #else
 426     os_protect(addr, length, 0);
 427 #endif
 428
 429     current_auto_gc_trigger = (lispobj *)addr;
 430 }
 431
 432 void clear_auto_gc_trigger(void)
 433 {
 434     os_vm_address_t addr;
 435     os_vm_size_t length;
 436
 437     if (current_auto_gc_trigger == NULL)
 438         return;
 439
 440     addr = (os_vm_address_t)current_auto_gc_trigger;
 441     length = dynamic_space_size + (os_vm_address_t)current_dynamic_space - addr;
 442
 443 #if defined(SUNOS) || defined(SOLARIS) || defined(LISP_FEATURE_HPUX)
 444     /* don't want to force whole space into swapping mode... */
 445     os_validate(addr, length);
 446 #else
 447     os_protect(addr, length, OS_VM_PROT_ALL);
 448 #endif
 449
 450     current_auto_gc_trigger = NULL;
 451 }
 452
 453 static boolean
 454 gc_trigger_hit(void *addr)
 455 {
 456     if (current_auto_gc_trigger == NULL)
 457         return 0;
 458     else{
 459         return (addr >= (void *)current_auto_gc_trigger &&
 460                 (char*)addr <((char *)current_dynamic_space + dynamic_space_size));
 461     }
 462 }
 463
 464 boolean
 465 cheneygc_handle_wp_violation(os_context_t *context, void *addr)
 466 {
 467     if(!foreign_function_call_active && gc_trigger_hit(addr)){
 468         struct thread *thread=arch_os_get_current_thread();
 469         clear_auto_gc_trigger();
 470         /* Don't flood the system with interrupts if the need to gc is
 471          * already noted. This can happen for example when SUB-GC
 472          * allocates or after a gc triggered in a WITHOUT-GCING. */
 473         if (SymbolValue(GC_PENDING,thread) == NIL) {
 474             if (SymbolValue(GC_INHIBIT,thread) == NIL) {
 475                 if (arch_pseudo_atomic_atomic(context)) {
 476                     /* set things up so that GC happens when we finish
 477                      * the PA section */
 478                     SetSymbolValue(GC_PENDING,T,thread);
 479                     arch_set_pseudo_atomic_interrupted(context);
 480                     maybe_save_gc_mask_and_block_deferrables
 481                         (os_context_sigmask_addr(context));
 482                 } else {
 483                     maybe_gc(context);
 484                 }
 485             } else {
 486                 SetSymbolValue(GC_PENDING,T,thread);
 487             }
 488         }
 489         return 1;
 490     }
 491     return 0;
 492 }