boehm-gc/mark.c

   1
   2 /*
   3  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
   4  * Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved.
   5  *
   6  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   7  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   8  *
   9  * Permission is hereby granted to use or copy this program
  10  * for any purpose,  provided the above notices are retained on all copies.
  11  * Permission to modify the code and to distribute modified code is granted,
  12  * provided the above notices are retained, and a notice that the code was
  13  * modified is included with the above copyright notice.
  14  *
  15  */
  16
  17
  18 # include <stdio.h>
  19 # include "gc_priv.h"
  20 # include "gc_mark.h"
  21
  22 /* We put this here to minimize the risk of inlining. */
  23 /*VARARGS*/
  24 #ifdef __WATCOMC__
  25   void GC_noop(void *p, ...) {}
  26 #else
  27   void GC_noop() {}
  28 #endif
  29
  30 /* Single argument version, robust against whole program analysis. */
  31 void GC_noop1(x)
  32 word x;
  33 {
  34     static VOLATILE word sink;
  35
  36     sink = x;
  37 }
  38
  39 /* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */
  40
  41 word GC_n_mark_procs = 0;
  42
  43 /* Initialize GC_obj_kinds properly and standard free lists properly.   */
  44 /* This must be done statically since they may be accessed before       */
  45 /* GC_init is called.                                                   */
  46 /* It's done here, since we need to deal with mark descriptors.         */
  47 struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
  48 /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,
  49                 0 | DS_LENGTH, FALSE, FALSE },
  50 /* NORMAL  */ { &GC_objfreelist[0], 0,
  51 #               if defined(ADD_BYTE_AT_END) && ALIGNMENT > DS_TAGS
  52                 (word)(-ALIGNMENT) | DS_LENGTH,
  53 #               else
  54                 0 | DS_LENGTH,
  55 #               endif
  56                 TRUE /* add length to descr */, TRUE },
  57 /* UNCOLLECTABLE */
  58               { &GC_uobjfreelist[0], 0,
  59                 0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
  60 # ifdef ATOMIC_UNCOLLECTABLE
  61    /* AUNCOLLECTABLE */
  62               { &GC_auobjfreelist[0], 0,
  63                 0 | DS_LENGTH, FALSE /* add length to descr */, FALSE },
  64 # endif
  65 # ifdef STUBBORN_ALLOC
  66 /*STUBBORN*/ { &GC_sobjfreelist[0], 0,
  67                 0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
  68 # endif
  69 };
  70
  71 # ifdef ATOMIC_UNCOLLECTABLE
  72 #   ifdef STUBBORN_ALLOC
  73       int GC_n_kinds = 5;
  74 #   else
  75       int GC_n_kinds = 4;
  76 #   endif
  77 # else
  78 #   ifdef STUBBORN_ALLOC
  79       int GC_n_kinds = 4;
  80 #   else
  81       int GC_n_kinds = 3;
  82 #   endif
  83 # endif
  84
  85
  86 # ifndef INITIAL_MARK_STACK_SIZE
  87 #   define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
  88                 /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a    */
  89                 /* multiple of HBLKSIZE.                                */
  90                 /* The incremental collector actually likes a larger    */
  91                 /* size, since it want to push all marked dirty objs    */
  92                 /* before marking anything new.  Currently we let it    */
  93                 /* grow dynamically.                                    */
  94 # endif
  95
  96 /*
  97  * Limits of stack for GC_mark routine.
  98  * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
  99  * need to be marked from.
 100  */
 101
 102 word GC_n_rescuing_pages;       /* Number of dirty pages we marked from */
 103                                 /* excludes ptrfree pages, etc.         */
 104
 105 mse * GC_mark_stack;
 106
 107 word GC_mark_stack_size = 0;
 108
 109 mse * GC_mark_stack_top;
 110
 111 static struct hblk * scan_ptr;
 112
 113 mark_state_t GC_mark_state = MS_NONE;
 114
 115 GC_bool GC_mark_stack_too_small = FALSE;
 116
 117 GC_bool GC_objects_are_marked = FALSE;  /* Are there collectable marked */
 118                                         /* objects in the heap?         */
 119
 120 /* Is a collection in progress?  Note that this can return true in the  */
 121 /* nonincremental case, if a collection has been abandoned and the      */
 122 /* mark state is now MS_INVALID.                                        */
 123 GC_bool GC_collection_in_progress()
 124 {
 125     return(GC_mark_state != MS_NONE);
 126 }
 127
 128 /* clear all mark bits in the header */
 129 void GC_clear_hdr_marks(hhdr)
 130 register hdr * hhdr;
 131 {
 132     BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
 133 }
 134
 135 /* Set all mark bits in the header.  Used for uncollectable blocks. */
 136 void GC_set_hdr_marks(hhdr)
 137 register hdr * hhdr;
 138 {
 139     register int i;
 140
 141     for (i = 0; i < MARK_BITS_SZ; ++i) {
 142         hhdr -> hb_marks[i] = ONES;
 143     }
 144 }
 145
 146 /*
 147  * Clear all mark bits associated with block h.
 148  */
 149 /*ARGSUSED*/
 150 static void clear_marks_for_block(h, dummy)
 151 struct hblk *h;
 152 word dummy;
 153 {
 154     register hdr * hhdr = HDR(h);
 155
 156     if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;
 157         /* Mark bit for these is cleared only once the object is        */
 158         /* explicitly deallocated.  This either frees the block, or     */
 159         /* the bit is cleared once the object is on the free list.      */
 160     GC_clear_hdr_marks(hhdr);
 161 }
 162
 163 /* Slow but general routines for setting/clearing/asking about mark bits */
 164 void GC_set_mark_bit(p)
 165 ptr_t p;
 166 {
 167     register struct hblk *h = HBLKPTR(p);
 168     register hdr * hhdr = HDR(h);
 169     register int word_no = (word *)p - (word *)h;
 170
 171     set_mark_bit_from_hdr(hhdr, word_no);
 172 }
 173
 174 void GC_clear_mark_bit(p)
 175 ptr_t p;
 176 {
 177     register struct hblk *h = HBLKPTR(p);
 178     register hdr * hhdr = HDR(h);
 179     register int word_no = (word *)p - (word *)h;
 180
 181     clear_mark_bit_from_hdr(hhdr, word_no);
 182 }
 183
 184 GC_bool GC_is_marked(p)
 185 ptr_t p;
 186 {
 187     register struct hblk *h = HBLKPTR(p);
 188     register hdr * hhdr = HDR(h);
 189     register int word_no = (word *)p - (word *)h;
 190
 191     return(mark_bit_from_hdr(hhdr, word_no));
 192 }
 193
 194
 195 /*
 196  * Clear mark bits in all allocated heap blocks.  This invalidates
 197  * the marker invariant, and sets GC_mark_state to reflect this.
 198  * (This implicitly starts marking to reestablish the invariant.)
 199  */
 200 void GC_clear_marks()
 201 {
 202     GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
 203     GC_objects_are_marked = FALSE;
 204     GC_mark_state = MS_INVALID;
 205     scan_ptr = 0;
 206 #   ifdef GATHERSTATS
 207         /* Counters reflect currently marked objects: reset here */
 208         GC_composite_in_use = 0;
 209         GC_atomic_in_use = 0;
 210 #   endif
 211
 212 }
 213
 214 /* Initiate a garbage collection.  Initiates a full collection if the   */
 215 /* mark state is invalid.                                               */
 216 /*ARGSUSED*/
 217 void GC_initiate_gc()
 218 {
 219     if (GC_dirty_maintained) GC_read_dirty();
 220 #   ifdef STUBBORN_ALLOC
 221         GC_read_changed();
 222 #   endif
 223 #   ifdef CHECKSUMS
 224         {
 225             extern void GC_check_dirty();
 226
 227             if (GC_dirty_maintained) GC_check_dirty();
 228         }
 229 #   endif
 230 #   ifdef GATHERSTATS
 231         GC_n_rescuing_pages = 0;
 232 #   endif
 233     if (GC_mark_state == MS_NONE) {
 234         GC_mark_state = MS_PUSH_RESCUERS;
 235     } else if (GC_mark_state != MS_INVALID) {
 236         ABORT("unexpected state");
 237     } /* else this is really a full collection, and mark        */
 238       /* bits are invalid.                                      */
 239     scan_ptr = 0;
 240 }
 241
 242
 243 static void alloc_mark_stack();
 244
 245 /* Perform a small amount of marking.                   */
 246 /* We try to touch roughly a page of memory.            */
 247 /* Return TRUE if we just finished a mark phase.        */
 248 /* Cold_gc_frame is an address inside a GC frame that   */
 249 /* remains valid until all marking is complete.         */
 250 /* A zero value indicates that it's OK to miss some     */
 251 /* register values.                                     */
 252 GC_bool GC_mark_some(cold_gc_frame)
 253 ptr_t cold_gc_frame;
 254 {
 255     switch(GC_mark_state) {
 256         case MS_NONE:
 257             return(FALSE);
 258
 259         case MS_PUSH_RESCUERS:
 260             if (GC_mark_stack_top
 261                 >= GC_mark_stack + GC_mark_stack_size
 262                    - INITIAL_MARK_STACK_SIZE/2) {
 263                 /* Go ahead and mark, even though that might cause us to */
 264                 /* see more marked dirty objects later on.  Avoid this   */
 265                 /* in the future.                                        */
 266                 GC_mark_stack_too_small = TRUE;
 267                 GC_mark_from_mark_stack();
 268                 return(FALSE);
 269             } else {
 270                 scan_ptr = GC_push_next_marked_dirty(scan_ptr);
 271                 if (scan_ptr == 0) {
 272 #                   ifdef PRINTSTATS
 273                         GC_printf1("Marked from %lu dirty pages\n",
 274                                    (unsigned long)GC_n_rescuing_pages);
 275 #                   endif
 276                     GC_push_roots(FALSE, cold_gc_frame);
 277                     GC_objects_are_marked = TRUE;
 278                     if (GC_mark_state != MS_INVALID) {
 279                         GC_mark_state = MS_ROOTS_PUSHED;
 280                     }
 281                 }
 282             }
 283             return(FALSE);
 284
 285         case MS_PUSH_UNCOLLECTABLE:
 286             if (GC_mark_stack_top
 287                 >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
 288                 GC_mark_from_mark_stack();
 289                 return(FALSE);
 290             } else {
 291                 scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
 292                 if (scan_ptr == 0) {
 293                     GC_push_roots(TRUE, cold_gc_frame);
 294                     GC_objects_are_marked = TRUE;
 295                     if (GC_mark_state != MS_INVALID) {
 296                         GC_mark_state = MS_ROOTS_PUSHED;
 297                     }
 298                 }
 299             }
 300             return(FALSE);
 301
 302         case MS_ROOTS_PUSHED:
 303             if (GC_mark_stack_top >= GC_mark_stack) {
 304                 GC_mark_from_mark_stack();
 305                 return(FALSE);
 306             } else {
 307                 GC_mark_state = MS_NONE;
 308                 if (GC_mark_stack_too_small) {
 309                     alloc_mark_stack(2*GC_mark_stack_size);
 310                 }
 311                 return(TRUE);
 312             }
 313
 314         case MS_INVALID:
 315         case MS_PARTIALLY_INVALID:
 316             if (!GC_objects_are_marked) {
 317                 GC_mark_state = MS_PUSH_UNCOLLECTABLE;
 318                 return(FALSE);
 319             }
 320             if (GC_mark_stack_top >= GC_mark_stack) {
 321                 GC_mark_from_mark_stack();
 322                 return(FALSE);
 323             }
 324             if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
 325                 /* About to start a heap scan for marked objects. */
 326                 /* Mark stack is empty.  OK to reallocate.        */
 327                 if (GC_mark_stack_too_small) {
 328                     alloc_mark_stack(2*GC_mark_stack_size);
 329                 }
 330                 GC_mark_state = MS_PARTIALLY_INVALID;
 331             }
 332             scan_ptr = GC_push_next_marked(scan_ptr);
 333             if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
 334                 GC_push_roots(TRUE, cold_gc_frame);
 335                 GC_objects_are_marked = TRUE;
 336                 if (GC_mark_state != MS_INVALID) {
 337                     GC_mark_state = MS_ROOTS_PUSHED;
 338                 }
 339             }
 340             return(FALSE);
 341         default:
 342             ABORT("GC_mark_some: bad state");
 343             return(FALSE);
 344     }
 345 }
 346
 347
 348 GC_bool GC_mark_stack_empty()
 349 {
 350     return(GC_mark_stack_top < GC_mark_stack);
 351 }
 352
 353 #ifdef PROF_MARKER
 354     word GC_prof_array[10];
 355 #   define PROF(n) GC_prof_array[n]++
 356 #else
 357 #   define PROF(n)
 358 #endif
 359
 360 /* Given a pointer to someplace other than a small object page or the   */
 361 /* first page of a large object, return a pointer either to the         */
 362 /* start of the large object or NIL.                                    */
 363 /* In the latter case black list the address current.                   */
 364 /* Returns NIL without black listing if current points to a block       */
 365 /* with IGNORE_OFF_PAGE set.                                            */
 366 /*ARGSUSED*/
 367 # ifdef PRINT_BLACK_LIST
 368   word GC_find_start(current, hhdr, source)
 369   word source;
 370 # else
 371   word GC_find_start(current, hhdr)
 372 # define source 0
 373 # endif
 374 register word current;
 375 register hdr * hhdr;
 376 {
 377 #   ifdef ALL_INTERIOR_POINTERS
 378         if (hhdr != 0) {
 379             register word orig = current;
 380
 381             current = (word)HBLKPTR(current) + HDR_BYTES;
 382             do {
 383               current = current - HBLKSIZE*(word)hhdr;
 384               hhdr = HDR(current);
 385             } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
 386             /* current points to the start of the large object */
 387             if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
 388             if ((word *)orig - (word *)current
 389                  >= (ptrdiff_t)(hhdr->hb_sz)) {
 390                 /* Pointer past the end of the block */
 391                 GC_ADD_TO_BLACK_LIST_NORMAL(orig, source);
 392                 return(0);
 393             }
 394             return(current);
 395         } else {
 396             GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
 397             return(0);
 398         }
 399 #   else
 400         GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
 401         return(0);
 402 #   endif
 403 #   undef source
 404 }
 405
 406 void GC_invalidate_mark_state()
 407 {
 408     GC_mark_state = MS_INVALID;
 409     GC_mark_stack_top = GC_mark_stack-1;
 410 }
 411
 412 mse * GC_signal_mark_stack_overflow(msp)
 413 mse * msp;
 414 {
 415     GC_mark_state = MS_INVALID;
 416     GC_mark_stack_too_small = TRUE;
 417 #   ifdef PRINTSTATS
 418         GC_printf1("Mark stack overflow; current size = %lu entries\n",
 419                     GC_mark_stack_size);
 420 #    endif
 421      return(msp-INITIAL_MARK_STACK_SIZE/8);
 422 }
 423
 424
 425 /*
 426  * Mark objects pointed to by the regions described by
 427  * mark stack entries between GC_mark_stack and GC_mark_stack_top,
 428  * inclusive.  Assumes the upper limit of a mark stack entry
 429  * is never 0.  A mark stack entry never has size 0.
 430  * We try to traverse on the order of a hblk of memory before we return.
 431  * Caller is responsible for calling this until the mark stack is empty.
 432  */
 433 void GC_mark_from_mark_stack()
 434 {
 435   mse * GC_mark_stack_reg = GC_mark_stack;
 436   mse * GC_mark_stack_top_reg = GC_mark_stack_top;
 437   mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
 438   int credit = HBLKSIZE;        /* Remaining credit for marking work    */
 439   register word * current_p;    /* Pointer to current candidate ptr.    */
 440   register word current;        /* Candidate pointer.                   */
 441   register word * limit;        /* (Incl) limit of current candidate    */
 442                                 /* range                                */
 443   register word descr;
 444   register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
 445   register ptr_t least_ha = GC_least_plausible_heap_addr;
 446 # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.          */
 447
 448   GC_objects_are_marked = TRUE;
 449 # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
 450   while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) {
 451 # else
 452   while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit)
 453         >= 0) {
 454 # endif
 455     current_p = GC_mark_stack_top_reg -> mse_start;
 456   retry:
 457     descr = GC_mark_stack_top_reg -> mse_descr;
 458     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) {
 459       word tag = descr & DS_TAGS;
 460
 461       switch(tag) {
 462         case DS_LENGTH:
 463           /* Large length.                                              */
 464           /* Process part of the range to avoid pushing too much on the */
 465           /* stack.                                                     */
 466           GC_mark_stack_top_reg -> mse_start =
 467                 limit = current_p + SPLIT_RANGE_WORDS-1;
 468           GC_mark_stack_top_reg -> mse_descr -=
 469                         WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
 470           /* Make sure that pointers overlapping the two ranges are     */
 471           /* considered.                                                */
 472           limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
 473           break;
 474         case DS_BITMAP:
 475           GC_mark_stack_top_reg--;
 476           descr &= ~DS_TAGS;
 477           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
 478           while (descr != 0) {
 479             if ((signed_word)descr < 0) {
 480               current = *current_p;
 481               if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
 482                 PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit,
 483                               current_p, exit1);
 484               }
 485             }
 486             descr <<= 1;
 487             ++ current_p;
 488           }
 489           continue;
 490         case DS_PROC:
 491           GC_mark_stack_top_reg--;
 492           credit -= PROC_BYTES;
 493 #ifdef GC_DEBUG
 494           current_p = GC_debug_object_start(current_p);
 495 #endif
 496           GC_mark_stack_top_reg =
 497               (*PROC(descr))
 498                     (current_p, GC_mark_stack_top_reg,
 499                     mark_stack_limit, ENV(descr));
 500           continue;
 501         case DS_PER_OBJECT:
 502           GC_mark_stack_top_reg -> mse_descr =
 503                         *(word *)((ptr_t)current_p + descr - tag);
 504           goto retry;
 505       }
 506     } else {
 507       GC_mark_stack_top_reg--;
 508       limit = (word *)(((ptr_t)current_p) + (word)descr);
 509     }
 510     /* The simple case in which we're scanning a range. */
 511     credit -= (ptr_t)limit - (ptr_t)current_p;
 512     limit -= 1;
 513     while (current_p <= limit) {
 514       current = *current_p;
 515       if ((ptr_t)current >= least_ha && (ptr_t)current <  greatest_ha) {
 516         PUSH_CONTENTS(current, GC_mark_stack_top_reg,
 517                       mark_stack_limit, current_p, exit2);
 518       }
 519       current_p = (word *)((char *)current_p + ALIGNMENT);
 520     }
 521   }
 522   GC_mark_stack_top = GC_mark_stack_top_reg;
 523 }
 524
 525 /* Allocate or reallocate space for mark stack of size s words  */
 526 /* May silently fail.                                           */
 527 static void alloc_mark_stack(n)
 528 word n;
 529 {
 530     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry));
 531
 532     GC_mark_stack_too_small = FALSE;
 533     if (GC_mark_stack_size != 0) {
 534         if (new_stack != 0) {
 535           word displ = (word)GC_mark_stack & (GC_page_size - 1);
 536           signed_word size = GC_mark_stack_size * sizeof(struct ms_entry);
 537
 538           /* Recycle old space */
 539               if (0 != displ) displ = GC_page_size - displ;
 540               size = (size - displ) & ~(GC_page_size - 1);
 541               if (size > 0) {
 542                 GC_add_to_heap((struct hblk *)
 543                                 ((word)GC_mark_stack + displ), (word)size);
 544               }
 545           GC_mark_stack = new_stack;
 546           GC_mark_stack_size = n;
 547 #         ifdef PRINTSTATS
 548               GC_printf1("Grew mark stack to %lu frames\n",
 549                          (unsigned long) GC_mark_stack_size);
 550 #         endif
 551         } else {
 552 #         ifdef PRINTSTATS
 553               GC_printf1("Failed to grow mark stack to %lu frames\n",
 554                          (unsigned long) n);
 555 #         endif
 556         }
 557     } else {
 558         if (new_stack == 0) {
 559             GC_err_printf0("No space for mark stack\n");
 560             EXIT();
 561         }
 562         GC_mark_stack = new_stack;
 563         GC_mark_stack_size = n;
 564     }
 565     GC_mark_stack_top = GC_mark_stack-1;
 566 }
 567
 568 void GC_mark_init()
 569 {
 570     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
 571 }
 572
 573 /*
 574  * Push all locations between b and t onto the mark stack.
 575  * b is the first location to be checked. t is one past the last
 576  * location to be checked.
 577  * Should only be used if there is no possibility of mark stack
 578  * overflow.
 579  */
 580 void GC_push_all(bottom, top)
 581 ptr_t bottom;
 582 ptr_t top;
 583 {
 584     register word length;
 585
 586     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
 587     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
 588     if (top == 0 || bottom == top) return;
 589     GC_mark_stack_top++;
 590     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
 591         ABORT("unexpected mark stack overflow");
 592     }
 593     length = top - bottom;
 594 #   if DS_TAGS > ALIGNMENT - 1
 595         length += DS_TAGS;
 596         length &= ~DS_TAGS;
 597 #   endif
 598     GC_mark_stack_top -> mse_start = (word *)bottom;
 599     GC_mark_stack_top -> mse_descr = length;
 600 }
 601
 602 /*
 603  * Analogous to the above, but push only those pages that may have been
 604  * dirtied.  A block h is assumed dirty if dirty_fn(h) != 0.
 605  * We use push_fn to actually push the block.
 606  * Will not overflow mark stack if push_fn pushes a small fixed number
 607  * of entries.  (This is invoked only if push_fn pushes a single entry,
 608  * or if it marks each object before pushing it, thus ensuring progress
 609  * in the event of a stack overflow.)
 610  */
 611 void GC_push_dirty(bottom, top, dirty_fn, push_fn)
 612 ptr_t bottom;
 613 ptr_t top;
 614 int (*dirty_fn)(/* struct hblk * h */);
 615 void (*push_fn)(/* ptr_t bottom, ptr_t top */);
 616 {
 617     register struct hblk * h;
 618
 619     bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
 620     top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
 621
 622     if (top == 0 || bottom == top) return;
 623     h = HBLKPTR(bottom + HBLKSIZE);
 624     if (top <= (ptr_t) h) {
 625         if ((*dirty_fn)(h-1)) {
 626             (*push_fn)(bottom, top);
 627         }
 628         return;
 629     }
 630     if ((*dirty_fn)(h-1)) {
 631         (*push_fn)(bottom, (ptr_t)h);
 632     }
 633     while ((ptr_t)(h+1) <= top) {
 634         if ((*dirty_fn)(h)) {
 635             if ((word)(GC_mark_stack_top - GC_mark_stack)
 636                 > 3 * GC_mark_stack_size / 4) {
 637                 /* Danger of mark stack overflow */
 638                 (*push_fn)((ptr_t)h, top);
 639                 return;
 640             } else {
 641                 (*push_fn)((ptr_t)h, (ptr_t)(h+1));
 642             }
 643         }
 644         h++;
 645     }
 646     if ((ptr_t)h != top) {
 647         if ((*dirty_fn)(h)) {
 648             (*push_fn)((ptr_t)h, top);
 649         }
 650     }
 651     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
 652         ABORT("unexpected mark stack overflow");
 653     }
 654 }
 655
 656 # ifndef SMALL_CONFIG
 657 void GC_push_conditional(bottom, top, all)
 658 ptr_t bottom;
 659 ptr_t top;
 660 int all;
 661 {
 662     if (all) {
 663       if (GC_dirty_maintained) {
 664 #       ifdef PROC_VDB
 665             /* Pages that were never dirtied cannot contain pointers    */
 666             GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all);
 667 #       else
 668             GC_push_all(bottom, top);
 669 #       endif
 670       } else {
 671         GC_push_all(bottom, top);
 672       }
 673     } else {
 674         GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all);
 675     }
 676 }
 677 #endif
 678
 679 # ifdef MSWIN32
 680   void __cdecl GC_push_one(p)
 681 # else
 682   void GC_push_one(p)
 683 # endif
 684 word p;
 685 {
 686 #   ifdef NURSERY
 687       if (0 != GC_push_proc) {
 688         GC_push_proc(p);
 689         return;
 690       }
 691 #   endif
 692     GC_PUSH_ONE_STACK(p, 0);
 693 }
 694
 695 # ifdef __STDC__
 696 #   define BASE(p) (word)GC_base((void *)(p))
 697 # else
 698 #   define BASE(p) (word)GC_base((char *)(p))
 699 # endif
 700
 701 /* As above, but argument passed preliminary test. */
 702 # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
 703     void GC_push_one_checked(p, interior_ptrs, source)
 704     ptr_t source;
 705 # else
 706     void GC_push_one_checked(p, interior_ptrs)
 707 #   define source 0
 708 # endif
 709 register word p;
 710 register GC_bool interior_ptrs;
 711 {
 712     register word r;
 713     register hdr * hhdr;
 714     register int displ;
 715
 716     GET_HDR(p, hhdr);
 717     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
 718         if (hhdr != 0 && interior_ptrs) {
 719           r = BASE(p);
 720           hhdr = HDR(r);
 721           displ = BYTES_TO_WORDS(HBLKDISPL(r));
 722         } else {
 723           hhdr = 0;
 724         }
 725     } else {
 726         register map_entry_type map_entry;
 727
 728         displ = HBLKDISPL(p);
 729         map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
 730         if (map_entry == OBJ_INVALID) {
 731 #         ifndef ALL_INTERIOR_POINTERS
 732             if (interior_ptrs) {
 733               r = BASE(p);
 734               displ = BYTES_TO_WORDS(HBLKDISPL(r));
 735               if (r == 0) hhdr = 0;
 736             } else {
 737               hhdr = 0;
 738             }
 739 #         else
 740             /* map already reflects interior pointers */
 741             hhdr = 0;
 742 #         endif
 743         } else {
 744           displ = BYTES_TO_WORDS(displ);
 745           displ -= map_entry;
 746           r = (word)((word *)(HBLKPTR(p)) + displ);
 747         }
 748     }
 749     /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
 750     /* displ is the word index within the block.                 */
 751     if (hhdr == 0) {
 752         if (interior_ptrs) {
 753 #           ifdef PRINT_BLACK_LIST
 754               GC_add_to_black_list_stack(p, source);
 755 #           else
 756               GC_add_to_black_list_stack(p);
 757 #           endif
 758         } else {
 759             GC_ADD_TO_BLACK_LIST_NORMAL(p, source);
 760 #           undef source  /* In case we had to define it. */
 761         }
 762     } else {
 763         if (!mark_bit_from_hdr(hhdr, displ)) {
 764             set_mark_bit_from_hdr(hhdr, displ);
 765             GC_STORE_BACK_PTR(source, (ptr_t)r);
 766             PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
 767                      &(GC_mark_stack[GC_mark_stack_size]));
 768         }
 769     }
 770 }
 771
 772 # ifdef TRACE_BUF
 773
 774 # define TRACE_ENTRIES 1000
 775
 776 struct trace_entry {
 777     char * kind;
 778     word gc_no;
 779     word words_allocd;
 780     word arg1;
 781     word arg2;
 782 } GC_trace_buf[TRACE_ENTRIES];
 783
 784 int GC_trace_buf_ptr = 0;
 785
 786 void GC_add_trace_entry(char *kind, word arg1, word arg2)
 787 {
 788     GC_trace_buf[GC_trace_buf_ptr].kind = kind;
 789     GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
 790     GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
 791     GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
 792     GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
 793     GC_trace_buf_ptr++;
 794     if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
 795 }
 796
 797 void GC_print_trace(word gc_no, GC_bool lock)
 798 {
 799     int i;
 800     struct trace_entry *p;
 801
 802     if (lock) LOCK();
 803     for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
 804         if (i < 0) i = TRACE_ENTRIES-1;
 805         p = GC_trace_buf + i;
 806         if (p -> gc_no < gc_no || p -> kind == 0) return;
 807         printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
 808                 p -> kind, p -> gc_no, p -> words_allocd,
 809                 (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
 810     }
 811     printf("Trace incomplete\n");
 812     if (lock) UNLOCK();
 813 }
 814
 815 # endif /* TRACE_BUF */
 816
 817 /*
 818  * A version of GC_push_all that treats all interior pointers as valid
 819  * and scans the entire region immediately, in case the contents
 820  * change.
 821  */
 822 void GC_push_all_eager(bottom, top)
 823 ptr_t bottom;
 824 ptr_t top;
 825 {
 826     word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
 827     word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
 828     register word *p;
 829     register word q;
 830     register word *lim;
 831     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
 832     register ptr_t least_ha = GC_least_plausible_heap_addr;
 833 #   define GC_greatest_plausible_heap_addr greatest_ha
 834 #   define GC_least_plausible_heap_addr least_ha
 835
 836     if (top == 0) return;
 837     /* check all pointers in range and put in push if they appear */
 838     /* to be valid.                                               */
 839       lim = t - 1 /* longword */;
 840       for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
 841         q = *p;
 842         GC_PUSH_ONE_STACK(q, p);
 843       }
 844 #   undef GC_greatest_plausible_heap_addr
 845 #   undef GC_least_plausible_heap_addr
 846 }
 847
 848 #ifndef THREADS
 849 /*
 850  * A version of GC_push_all that treats all interior pointers as valid
 851  * and scans part of the area immediately, to make sure that saved
 852  * register values are not lost.
 853  * Cold_gc_frame delimits the stack section that must be scanned
 854  * eagerly.  A zero value indicates that no eager scanning is needed.
 855  */
 856 void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame)
 857 ptr_t bottom;
 858 ptr_t top;
 859 ptr_t cold_gc_frame;
 860 {
 861 # ifdef ALL_INTERIOR_POINTERS
 862 #   define EAGER_BYTES 1024
 863     /* Push the hot end of the stack eagerly, so that register values   */
 864     /* saved inside GC frames are marked before they disappear.         */
 865     /* The rest of the marking can be deferred until later.             */
 866     if (0 == cold_gc_frame) {
 867         GC_push_all_stack(bottom, top);
 868         return;
 869     }
 870 #   ifdef STACK_GROWS_DOWN
 871         GC_push_all_eager(bottom, cold_gc_frame);
 872         GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
 873 #   else /* STACK_GROWS_UP */
 874         GC_push_all_eager(cold_gc_frame, top);
 875         GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
 876 #   endif /* STACK_GROWS_UP */
 877 # else
 878     GC_push_all_eager(bottom, top);
 879 # endif
 880 # ifdef TRACE_BUF
 881       GC_add_trace_entry("GC_push_all_stack", bottom, top);
 882 # endif
 883 }
 884 #endif /* !THREADS */
 885
 886 void GC_push_all_stack(bottom, top)
 887 ptr_t bottom;
 888 ptr_t top;
 889 {
 890 # ifdef ALL_INTERIOR_POINTERS
 891     GC_push_all(bottom, top);
 892 # else
 893     GC_push_all_eager(bottom, top);
 894 # endif
 895 }
 896
 897 #ifndef SMALL_CONFIG
 898 /* Push all objects reachable from marked objects in the given block */
 899 /* of size 1 objects.                                                */
 900 void GC_push_marked1(h, hhdr)
 901 struct hblk *h;
 902 register hdr * hhdr;
 903 {
 904     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
 905     register word *p;
 906     word *plim;
 907     register int i;
 908     register word q;
 909     register word mark_word;
 910     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
 911     register ptr_t least_ha = GC_least_plausible_heap_addr;
 912 #   define GC_greatest_plausible_heap_addr greatest_ha
 913 #   define GC_least_plausible_heap_addr least_ha
 914
 915     p = (word *)(h->hb_body);
 916     plim = (word *)(((word)h) + HBLKSIZE);
 917
 918     /* go through all words in block */
 919         while( p < plim )  {
 920             mark_word = *mark_word_addr++;
 921             i = 0;
 922             while(mark_word != 0) {
 923               if (mark_word & 1) {
 924                   q = p[i];
 925                   GC_PUSH_ONE_HEAP(q, p + i);
 926               }
 927               i++;
 928               mark_word >>= 1;
 929             }
 930             p += WORDSZ;
 931         }
 932 #   undef GC_greatest_plausible_heap_addr
 933 #   undef GC_least_plausible_heap_addr
 934 }
 935
 936
 937 #ifndef UNALIGNED
 938
 939 /* Push all objects reachable from marked objects in the given block */
 940 /* of size 2 objects.                                                */
 941 void GC_push_marked2(h, hhdr)
 942 struct hblk *h;
 943 register hdr * hhdr;
 944 {
 945     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
 946     register word *p;
 947     word *plim;
 948     register int i;
 949     register word q;
 950     register word mark_word;
 951     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
 952     register ptr_t least_ha = GC_least_plausible_heap_addr;
 953 #   define GC_greatest_plausible_heap_addr greatest_ha
 954 #   define GC_least_plausible_heap_addr least_ha
 955
 956     p = (word *)(h->hb_body);
 957     plim = (word *)(((word)h) + HBLKSIZE);
 958
 959     /* go through all words in block */
 960         while( p < plim )  {
 961             mark_word = *mark_word_addr++;
 962             i = 0;
 963             while(mark_word != 0) {
 964               if (mark_word & 1) {
 965                   q = p[i];
 966                   GC_PUSH_ONE_HEAP(q, p + i);
 967                   q = p[i+1];
 968                   GC_PUSH_ONE_HEAP(q, p + i);
 969               }
 970               i += 2;
 971               mark_word >>= 2;
 972             }
 973             p += WORDSZ;
 974         }
 975 #   undef GC_greatest_plausible_heap_addr
 976 #   undef GC_least_plausible_heap_addr
 977 }
 978
 979 /* Push all objects reachable from marked objects in the given block */
 980 /* of size 4 objects.                                                */
 981 /* There is a risk of mark stack overflow here.  But we handle that. */
 982 /* And only unmarked objects get pushed, so it's not very likely.    */
 983 void GC_push_marked4(h, hhdr)
 984 struct hblk *h;
 985 register hdr * hhdr;
 986 {
 987     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
 988     register word *p;
 989     word *plim;
 990     register int i;
 991     register word q;
 992     register word mark_word;
 993     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
 994     register ptr_t least_ha = GC_least_plausible_heap_addr;
 995 #   define GC_greatest_plausible_heap_addr greatest_ha
 996 #   define GC_least_plausible_heap_addr least_ha
 997
 998     p = (word *)(h->hb_body);
 999     plim = (word *)(((word)h) + HBLKSIZE);
1000
1001     /* go through all words in block */
1002         while( p < plim )  {
1003             mark_word = *mark_word_addr++;
1004             i = 0;
1005             while(mark_word != 0) {
1006               if (mark_word & 1) {
1007                   q = p[i];
1008                   GC_PUSH_ONE_HEAP(q, p + i);
1009                   q = p[i+1];
1010                   GC_PUSH_ONE_HEAP(q, p + i + 1);
1011                   q = p[i+2];
1012                   GC_PUSH_ONE_HEAP(q, p + i + 2);
1013                   q = p[i+3];
1014                   GC_PUSH_ONE_HEAP(q, p + i + 3);
1015               }
1016               i += 4;
1017               mark_word >>= 4;
1018             }
1019             p += WORDSZ;
1020         }
1021 #   undef GC_greatest_plausible_heap_addr
1022 #   undef GC_least_plausible_heap_addr
1023 }
1024
1025 #endif /* UNALIGNED */
1026
1027 #endif /* SMALL_CONFIG */
1028
1029 /* Push all objects reachable from marked objects in the given block */
1030 void GC_push_marked(h, hhdr)
1031 struct hblk *h;
1032 register hdr * hhdr;
1033 {
1034     register int sz = hhdr -> hb_sz;
1035     register word * p;
1036     register int word_no;
1037     register word * lim;
1038     register mse * GC_mark_stack_top_reg;
1039     register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
1040
1041     /* Some quick shortcuts: */
1042         {
1043             struct obj_kind *ok = &(GC_obj_kinds[hhdr -> hb_obj_kind]);
1044             if ((0 | DS_LENGTH) == ok -> ok_descriptor
1045                 && FALSE == ok -> ok_relocate_descr)
1046                 return;
1047         }
1048         if (GC_block_empty(hhdr)/* nothing marked */) return;
1049 #   ifdef GATHERSTATS
1050         GC_n_rescuing_pages++;
1051 #   endif
1052     GC_objects_are_marked = TRUE;
1053     if (sz > MAXOBJSZ) {
1054         lim = (word *)(h + 1);
1055     } else {
1056         lim = (word *)(h + 1) - sz;
1057     }
1058
1059     switch(sz) {
1060 #   if !defined(SMALL_CONFIG)
1061      case 1:
1062        GC_push_marked1(h, hhdr);
1063        break;
1064 #   endif
1065 #   if !defined(SMALL_CONFIG) && !defined(UNALIGNED)
1066      case 2:
1067        GC_push_marked2(h, hhdr);
1068        break;
1069      case 4:
1070        GC_push_marked4(h, hhdr);
1071        break;
1072 #   endif
1073      default:
1074       GC_mark_stack_top_reg = GC_mark_stack_top;
1075       for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim;
1076          p += sz, word_no += sz) {
1077          /* This ignores user specified mark procs.  This currently     */
1078          /* doesn't matter, since marking from the whole object         */
1079          /* is always sufficient, and we will eventually use the user   */
1080          /* mark proc to avoid any bogus pointers.                      */
1081          if (mark_bit_from_hdr(hhdr, word_no)) {
1082            /* Mark from fields inside the object */
1083              PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1084 #            ifdef GATHERSTATS
1085                 /* Subtract this object from total, since it was        */
1086                 /* added in twice.                                      */
1087                 GC_composite_in_use -= sz;
1088 #            endif
1089          }
1090       }
1091       GC_mark_stack_top = GC_mark_stack_top_reg;
1092     }
1093 }
1094
1095 #ifndef SMALL_CONFIG
1096 /* Test whether any page in the given block is dirty    */
1097 GC_bool GC_block_was_dirty(h, hhdr)
1098 struct hblk *h;
1099 register hdr * hhdr;
1100 {
1101     register int sz = hhdr -> hb_sz;
1102
1103     if (sz < MAXOBJSZ) {
1104          return(GC_page_was_dirty(h));
1105     } else {
1106          register ptr_t p = (ptr_t)h;
1107          sz += HDR_WORDS;
1108          sz = WORDS_TO_BYTES(sz);
1109          while (p < (ptr_t)h + sz) {
1110              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1111              p += HBLKSIZE;
1112          }
1113          return(FALSE);
1114     }
1115 }
1116 #endif /* SMALL_CONFIG */
1117
1118 /* Similar to GC_push_next_marked, but return address of next block     */
1119 struct hblk * GC_push_next_marked(h)
1120 struct hblk *h;
1121 {
1122     register hdr * hhdr;
1123
1124     h = GC_next_used_block(h);
1125     if (h == 0) return(0);
1126     hhdr = HDR(h);
1127     GC_push_marked(h, hhdr);
1128     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1129 }
1130
1131 #ifndef SMALL_CONFIG
1132 /* Identical to above, but mark only from dirty pages   */
1133 struct hblk * GC_push_next_marked_dirty(h)
1134 struct hblk *h;
1135 {
1136     register hdr * hhdr;
1137
1138     if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
1139     for (;;) {
1140         h = GC_next_used_block(h);
1141         if (h == 0) return(0);
1142         hhdr = HDR(h);
1143 #       ifdef STUBBORN_ALLOC
1144           if (hhdr -> hb_obj_kind == STUBBORN) {
1145             if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
1146                 break;
1147             }
1148           } else {
1149             if (GC_block_was_dirty(h, hhdr)) break;
1150           }
1151 #       else
1152           if (GC_block_was_dirty(h, hhdr)) break;
1153 #       endif
1154         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1155     }
1156     GC_push_marked(h, hhdr);
1157     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1158 }
1159 #endif
1160
1161 /* Similar to above, but for uncollectable pages.  Needed since we      */
1162 /* do not clear marks for such pages, even for full collections.        */
1163 struct hblk * GC_push_next_marked_uncollectable(h)
1164 struct hblk *h;
1165 {
1166     register hdr * hhdr = HDR(h);
1167
1168     for (;;) {
1169         h = GC_next_used_block(h);
1170         if (h == 0) return(0);
1171         hhdr = HDR(h);
1172         if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
1173         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1174     }
1175     GC_push_marked(h, hhdr);
1176     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1177 }
1178
1179