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 = GC_RESERVED_MARK_PROCS;
  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 #ifdef MSWIN32
 256   /* Windows 98 appears to asynchronously create and remove writable    */
 257   /* memory mappings, for reasons we haven't yet understood.  Since     */
 258   /* we look for writable regions to determine the root set, we may     */
 259   /* try to mark from an address range that disappeared since we        */
 260   /* started the collection.  Thus we have to recover from faults here. */
 261   /* This code does not appear to be necessary for Windows 95/NT/2000.  */
 262   /* Note that this code should never generate an incremental GC write  */
 263   /* fault.                                                             */
 264   __try {
 265 #endif
 266     switch(GC_mark_state) {
 267         case MS_NONE:
 268             return(FALSE);
 269
 270         case MS_PUSH_RESCUERS:
 271             if (GC_mark_stack_top
 272                 >= GC_mark_stack + GC_mark_stack_size
 273                    - INITIAL_MARK_STACK_SIZE/2) {
 274                 /* Go ahead and mark, even though that might cause us to */
 275                 /* see more marked dirty objects later on.  Avoid this   */
 276                 /* in the future.                                        */
 277                 GC_mark_stack_too_small = TRUE;
 278                 GC_mark_from_mark_stack();
 279                 return(FALSE);
 280             } else {
 281                 scan_ptr = GC_push_next_marked_dirty(scan_ptr);
 282                 if (scan_ptr == 0) {
 283 #                   ifdef PRINTSTATS
 284                         GC_printf1("Marked from %lu dirty pages\n",
 285                                    (unsigned long)GC_n_rescuing_pages);
 286 #                   endif
 287                     GC_push_roots(FALSE, cold_gc_frame);
 288                     GC_objects_are_marked = TRUE;
 289                     if (GC_mark_state != MS_INVALID) {
 290                         GC_mark_state = MS_ROOTS_PUSHED;
 291                     }
 292                 }
 293             }
 294             return(FALSE);
 295
 296         case MS_PUSH_UNCOLLECTABLE:
 297             if (GC_mark_stack_top
 298                 >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
 299                 GC_mark_from_mark_stack();
 300                 return(FALSE);
 301             } else {
 302                 scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
 303                 if (scan_ptr == 0) {
 304                     GC_push_roots(TRUE, cold_gc_frame);
 305                     GC_objects_are_marked = TRUE;
 306                     if (GC_mark_state != MS_INVALID) {
 307                         GC_mark_state = MS_ROOTS_PUSHED;
 308                     }
 309                 }
 310             }
 311             return(FALSE);
 312
 313         case MS_ROOTS_PUSHED:
 314             if (GC_mark_stack_top >= GC_mark_stack) {
 315                 GC_mark_from_mark_stack();
 316                 return(FALSE);
 317             } else {
 318                 GC_mark_state = MS_NONE;
 319                 if (GC_mark_stack_too_small) {
 320                     alloc_mark_stack(2*GC_mark_stack_size);
 321                 }
 322                 return(TRUE);
 323             }
 324
 325         case MS_INVALID:
 326         case MS_PARTIALLY_INVALID:
 327             if (!GC_objects_are_marked) {
 328                 GC_mark_state = MS_PUSH_UNCOLLECTABLE;
 329                 return(FALSE);
 330             }
 331             if (GC_mark_stack_top >= GC_mark_stack) {
 332                 GC_mark_from_mark_stack();
 333                 return(FALSE);
 334             }
 335             if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
 336                 /* About to start a heap scan for marked objects. */
 337                 /* Mark stack is empty.  OK to reallocate.        */
 338                 if (GC_mark_stack_too_small) {
 339                     alloc_mark_stack(2*GC_mark_stack_size);
 340                 }
 341                 GC_mark_state = MS_PARTIALLY_INVALID;
 342             }
 343             scan_ptr = GC_push_next_marked(scan_ptr);
 344             if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
 345                 GC_push_roots(TRUE, cold_gc_frame);
 346                 GC_objects_are_marked = TRUE;
 347                 if (GC_mark_state != MS_INVALID) {
 348                     GC_mark_state = MS_ROOTS_PUSHED;
 349                 }
 350             }
 351             return(FALSE);
 352         default:
 353             ABORT("GC_mark_some: bad state");
 354             return(FALSE);
 355     }
 356 #ifdef MSWIN32
 357   } __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
 358             EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {
 359 #   ifdef PRINTSTATS
 360         GC_printf0("Caught ACCESS_VIOLATION in marker. "
 361                    "Memory mapping disappeared.\n");
 362 #   endif /* PRINTSTATS */
 363     /* We have bad roots on the stack.  Discard mark stack.     */
 364     /* Rescan from marked objects.  Redetermine roots.          */
 365     GC_invalidate_mark_state();
 366     scan_ptr = 0;
 367     return FALSE;
 368   }
 369 #endif /* MSWIN32 */
 370 }
 371
 372
 373 GC_bool GC_mark_stack_empty()
 374 {
 375     return(GC_mark_stack_top < GC_mark_stack);
 376 }
 377
 378 #ifdef PROF_MARKER
 379     word GC_prof_array[10];
 380 #   define PROF(n) GC_prof_array[n]++
 381 #else
 382 #   define PROF(n)
 383 #endif
 384
 385 /* Given a pointer to someplace other than a small object page or the   */
 386 /* first page of a large object, return a pointer either to the         */
 387 /* start of the large object or NIL.                                    */
 388 /* In the latter case black list the address current.                   */
 389 /* Returns NIL without black listing if current points to a block       */
 390 /* with IGNORE_OFF_PAGE set.                                            */
 391 /*ARGSUSED*/
 392 # ifdef PRINT_BLACK_LIST
 393   ptr_t GC_find_start(current, hhdr, source)
 394   word source;
 395 # else
 396   ptr_t GC_find_start(current, hhdr)
 397 # define source 0
 398 # endif
 399 register ptr_t current;
 400 register hdr * hhdr;
 401 {
 402 #   ifdef ALL_INTERIOR_POINTERS
 403         if (hhdr != 0) {
 404             register ptr_t orig = current;
 405
 406             current = (ptr_t)HBLKPTR(current) + HDR_BYTES;
 407             do {
 408               current = current - HBLKSIZE*(word)hhdr;
 409               hhdr = HDR(current);
 410             } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
 411             /* current points to the start of the large object */
 412             if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
 413             if ((word *)orig - (word *)current
 414                  >= (ptrdiff_t)(hhdr->hb_sz)) {
 415                 /* Pointer past the end of the block */
 416                 GC_ADD_TO_BLACK_LIST_NORMAL(orig, source);
 417                 return(0);
 418             }
 419             return(current);
 420         } else {
 421             GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
 422             return(0);
 423         }
 424 #   else
 425         GC_ADD_TO_BLACK_LIST_NORMAL(current, source);
 426         return(0);
 427 #   endif
 428 #   undef source
 429 }
 430
 431 void GC_invalidate_mark_state()
 432 {
 433     GC_mark_state = MS_INVALID;
 434     GC_mark_stack_top = GC_mark_stack-1;
 435 }
 436
 437 mse * GC_signal_mark_stack_overflow(msp)
 438 mse * msp;
 439 {
 440     GC_mark_state = MS_INVALID;
 441     GC_mark_stack_too_small = TRUE;
 442 #   ifdef PRINTSTATS
 443         GC_printf1("Mark stack overflow; current size = %lu entries\n",
 444                     GC_mark_stack_size);
 445 #    endif
 446      return(msp-INITIAL_MARK_STACK_SIZE/8);
 447 }
 448
 449
 450 /*
 451  * Mark objects pointed to by the regions described by
 452  * mark stack entries between GC_mark_stack and GC_mark_stack_top,
 453  * inclusive.  Assumes the upper limit of a mark stack entry
 454  * is never 0.  A mark stack entry never has size 0.
 455  * We try to traverse on the order of a hblk of memory before we return.
 456  * Caller is responsible for calling this until the mark stack is empty.
 457  * Note that this is the most performance critical routine in the
 458  * collector.  Hence it contains all sorts of ugly hacks to speed
 459  * things up.  In particular, we avoid procedure calls on the common
 460  * path, we take advantage of peculiarities of the mark descriptor
 461  * encoding, we optionally maintain a cache for the block address to
 462  * header mapping, we prefetch when an object is "grayed", etc.
 463  */
 464 void GC_mark_from_mark_stack()
 465 {
 466   mse * GC_mark_stack_reg = GC_mark_stack;
 467   mse * GC_mark_stack_top_reg = GC_mark_stack_top;
 468   mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
 469   int credit = HBLKSIZE;        /* Remaining credit for marking work    */
 470   register word * current_p;    /* Pointer to current candidate ptr.    */
 471   register word current;        /* Candidate pointer.                   */
 472   register word * limit;        /* (Incl) limit of current candidate    */
 473                                 /* range                                */
 474   register word descr;
 475   register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
 476   register ptr_t least_ha = GC_least_plausible_heap_addr;
 477   DECLARE_HDR_CACHE;
 478
 479 # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.          */
 480
 481   GC_objects_are_marked = TRUE;
 482   INIT_HDR_CACHE;
 483 # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
 484   while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) {
 485 # else
 486   while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit)
 487         >= 0) {
 488 # endif
 489     current_p = GC_mark_stack_top_reg -> mse_start;
 490     descr = GC_mark_stack_top_reg -> mse_descr;
 491   retry:
 492     /* current_p and descr describe the current object.         */
 493     /* *GC_mark_stack_top_reg is vacant.                        */
 494     /* The following is 0 only for small objects described by a simple  */
 495     /* length descriptor.  For many applications this is the common     */
 496     /* case, so we try to detect it quickly.                            */
 497     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) {
 498       word tag = descr & DS_TAGS;
 499
 500       switch(tag) {
 501         case DS_LENGTH:
 502           /* Large length.                                              */
 503           /* Process part of the range to avoid pushing too much on the */
 504           /* stack.                                                     */
 505           GC_mark_stack_top_reg -> mse_start =
 506                 limit = current_p + SPLIT_RANGE_WORDS-1;
 507           GC_mark_stack_top_reg -> mse_descr =
 508                         descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
 509           /* Make sure that pointers overlapping the two ranges are     */
 510           /* considered.                                                */
 511           limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
 512           break;
 513         case DS_BITMAP:
 514           GC_mark_stack_top_reg--;
 515           descr &= ~DS_TAGS;
 516           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
 517           while (descr != 0) {
 518             if ((signed_word)descr < 0) {
 519               current = *current_p;
 520               if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
 521                 PREFETCH(current);
 522                 HC_PUSH_CONTENTS((ptr_t)current, GC_mark_stack_top_reg,
 523                               mark_stack_limit, current_p, exit1);
 524               }
 525             }
 526             descr <<= 1;
 527             ++ current_p;
 528           }
 529           continue;
 530         case DS_PROC:
 531           GC_mark_stack_top_reg--;
 532           credit -= PROC_BYTES;
 533           GC_mark_stack_top_reg =
 534               (*PROC(descr))
 535                     (current_p, GC_mark_stack_top_reg,
 536                     mark_stack_limit, ENV(descr));
 537           continue;
 538         case DS_PER_OBJECT:
 539           if ((signed_word)descr >= 0) {
 540             /* Descriptor is in the object.     */
 541             descr = *(word *)((ptr_t)current_p + descr - DS_PER_OBJECT);
 542           } else {
 543             /* Descriptor is in type descriptor pointed to by first     */
 544             /* word in object.                                          */
 545             ptr_t type_descr = *(ptr_t *)current_p;
 546             /* type_descr is either a valid pointer to the descriptor   */
 547             /* structure, or this object was on a free list.  If it     */
 548             /* it was anything but the last object on the free list,    */
 549             /* we will misinterpret the next object on the free list as */
 550             /* the type descriptor, and get a 0 GC descriptor, which    */
 551             /* is ideal.  Unfortunately, we need to check for the last  */
 552             /* object case explicitly.                                  */
 553             if (0 == type_descr) {
 554                 /* Rarely executed.     */
 555                 GC_mark_stack_top_reg--;
 556                 continue;
 557             }
 558             descr = *(word *)(type_descr
 559                               - (descr - (DS_PER_OBJECT - INDIR_PER_OBJ_BIAS)));
 560           }
 561           goto retry;
 562       }
 563     } else /* Small object with length descriptor */ {
 564       GC_mark_stack_top_reg--;
 565       limit = (word *)(((ptr_t)current_p) + (word)descr);
 566     }
 567     /* The simple case in which we're scanning a range. */
 568     credit -= (ptr_t)limit - (ptr_t)current_p;
 569     limit -= 1;
 570     {
 571 #     define PREF_DIST 4
 572
 573 #     ifndef SMALL_CONFIG
 574         word deferred;
 575
 576         /* Try to prefetch the next pointer to be examined asap.        */
 577         /* Empirically, this also seems to help slightly without        */
 578         /* prefetches, at least on linux/X86.  Presumably this loop     */
 579         /* ends up with less register pressure, and gcc thus ends up    */
 580         /* generating slightly better code.  Overall gcc code quality   */
 581         /* for this loop is still not great.                            */
 582         for(;;) {
 583           PREFETCH((ptr_t)limit - PREF_DIST*CACHE_LINE_SIZE);
 584           deferred = *limit;
 585           limit = (word *)((char *)limit - ALIGNMENT);
 586           if ((ptr_t)deferred >= least_ha && (ptr_t)deferred <  greatest_ha) {
 587             PREFETCH(deferred);
 588             break;
 589           }
 590           if (current_p > limit) goto next_object;
 591           /* Unroll once, so we don't do too many of the prefetches     */
 592           /* based on limit.                                            */
 593           deferred = *limit;
 594           limit = (word *)((char *)limit - ALIGNMENT);
 595           if ((ptr_t)deferred >= least_ha && (ptr_t)deferred <  greatest_ha) {
 596             PREFETCH(deferred);
 597             break;
 598           }
 599           if (current_p > limit) goto next_object;
 600         }
 601 #     endif
 602
 603       while (current_p <= limit) {
 604         /* Empirically, unrolling this loop doesn't help a lot. */
 605         /* Since HC_PUSH_CONTENTS expands to a lot of code,     */
 606         /* we don't.                                            */
 607         current = *current_p;
 608         PREFETCH((ptr_t)current_p + PREF_DIST*CACHE_LINE_SIZE);
 609         if ((ptr_t)current >= least_ha && (ptr_t)current <  greatest_ha) {
 610           /* Prefetch the contents of the object we just pushed.  It's  */
 611           /* likely we will need them soon.                             */
 612           PREFETCH(current);
 613           HC_PUSH_CONTENTS((ptr_t)current, GC_mark_stack_top_reg,
 614                            mark_stack_limit, current_p, exit2);
 615         }
 616         current_p = (word *)((char *)current_p + ALIGNMENT);
 617       }
 618
 619 #     ifndef SMALL_CONFIG
 620         /* We still need to mark the entry we previously prefetched.    */
 621         /* We alrady know that it passes the preliminary pointer        */
 622         /* validity test.                                               */
 623         HC_PUSH_CONTENTS((ptr_t)deferred, GC_mark_stack_top_reg,
 624                          mark_stack_limit, current_p, exit4);
 625         next_object:;
 626 #     endif
 627     }
 628   }
 629   GC_mark_stack_top = GC_mark_stack_top_reg;
 630 }
 631
 632 /* Allocate or reallocate space for mark stack of size s words  */
 633 /* May silently fail.                                           */
 634 static void alloc_mark_stack(n)
 635 word n;
 636 {
 637     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry));
 638
 639     GC_mark_stack_too_small = FALSE;
 640     if (GC_mark_stack_size != 0) {
 641         if (new_stack != 0) {
 642           word displ = (word)GC_mark_stack & (GC_page_size - 1);
 643           signed_word size = GC_mark_stack_size * sizeof(struct ms_entry);
 644
 645           /* Recycle old space */
 646               if (0 != displ) displ = GC_page_size - displ;
 647               size = (size - displ) & ~(GC_page_size - 1);
 648               if (size > 0) {
 649                 GC_add_to_heap((struct hblk *)
 650                                 ((word)GC_mark_stack + displ), (word)size);
 651               }
 652           GC_mark_stack = new_stack;
 653           GC_mark_stack_size = n;
 654 #         ifdef PRINTSTATS
 655               GC_printf1("Grew mark stack to %lu frames\n",
 656                          (unsigned long) GC_mark_stack_size);
 657 #         endif
 658         } else {
 659 #         ifdef PRINTSTATS
 660               GC_printf1("Failed to grow mark stack to %lu frames\n",
 661                          (unsigned long) n);
 662 #         endif
 663         }
 664     } else {
 665         if (new_stack == 0) {
 666             GC_err_printf0("No space for mark stack\n");
 667             EXIT();
 668         }
 669         GC_mark_stack = new_stack;
 670         GC_mark_stack_size = n;
 671     }
 672     GC_mark_stack_top = GC_mark_stack-1;
 673 }
 674
 675 void GC_mark_init()
 676 {
 677     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
 678 }
 679
 680 /*
 681  * Push all locations between b and t onto the mark stack.
 682  * b is the first location to be checked. t is one past the last
 683  * location to be checked.
 684  * Should only be used if there is no possibility of mark stack
 685  * overflow.
 686  */
 687 void GC_push_all(bottom, top)
 688 ptr_t bottom;
 689 ptr_t top;
 690 {
 691     register word length;
 692
 693     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
 694     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
 695     if (top == 0 || bottom == top) return;
 696     GC_mark_stack_top++;
 697     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
 698         ABORT("unexpected mark stack overflow");
 699     }
 700     length = top - bottom;
 701 #   if DS_TAGS > ALIGNMENT - 1
 702         length += DS_TAGS;
 703         length &= ~DS_TAGS;
 704 #   endif
 705     GC_mark_stack_top -> mse_start = (word *)bottom;
 706     GC_mark_stack_top -> mse_descr = length;
 707 }
 708
 709 /*
 710  * Analogous to the above, but push only those pages that may have been
 711  * dirtied.  A block h is assumed dirty if dirty_fn(h) != 0.
 712  * We use push_fn to actually push the block.
 713  * Will not overflow mark stack if push_fn pushes a small fixed number
 714  * of entries.  (This is invoked only if push_fn pushes a single entry,
 715  * or if it marks each object before pushing it, thus ensuring progress
 716  * in the event of a stack overflow.)
 717  */
 718 void GC_push_dirty(bottom, top, dirty_fn, push_fn)
 719 ptr_t bottom;
 720 ptr_t top;
 721 int (*dirty_fn)(/* struct hblk * h */);
 722 void (*push_fn)(/* ptr_t bottom, ptr_t top */);
 723 {
 724     register struct hblk * h;
 725
 726     bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
 727     top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
 728
 729     if (top == 0 || bottom == top) return;
 730     h = HBLKPTR(bottom + HBLKSIZE);
 731     if (top <= (ptr_t) h) {
 732         if ((*dirty_fn)(h-1)) {
 733             (*push_fn)(bottom, top);
 734         }
 735         return;
 736     }
 737     if ((*dirty_fn)(h-1)) {
 738         (*push_fn)(bottom, (ptr_t)h);
 739     }
 740     while ((ptr_t)(h+1) <= top) {
 741         if ((*dirty_fn)(h)) {
 742             if ((word)(GC_mark_stack_top - GC_mark_stack)
 743                 > 3 * GC_mark_stack_size / 4) {
 744                 /* Danger of mark stack overflow */
 745                 (*push_fn)((ptr_t)h, top);
 746                 return;
 747             } else {
 748                 (*push_fn)((ptr_t)h, (ptr_t)(h+1));
 749             }
 750         }
 751         h++;
 752     }
 753     if ((ptr_t)h != top) {
 754         if ((*dirty_fn)(h)) {
 755             (*push_fn)((ptr_t)h, top);
 756         }
 757     }
 758     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
 759         ABORT("unexpected mark stack overflow");
 760     }
 761 }
 762
 763 # ifndef SMALL_CONFIG
 764 void GC_push_conditional(bottom, top, all)
 765 ptr_t bottom;
 766 ptr_t top;
 767 int all;
 768 {
 769     if (all) {
 770       if (GC_dirty_maintained) {
 771 #       ifdef PROC_VDB
 772             /* Pages that were never dirtied cannot contain pointers    */
 773             GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all);
 774 #       else
 775             GC_push_all(bottom, top);
 776 #       endif
 777       } else {
 778         GC_push_all(bottom, top);
 779       }
 780     } else {
 781         GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all);
 782     }
 783 }
 784 #endif
 785
 786 # ifdef MSWIN32
 787   void __cdecl GC_push_one(p)
 788 # else
 789   void GC_push_one(p)
 790 # endif
 791 word p;
 792 {
 793 #   ifdef NURSERY
 794       if (0 != GC_push_proc) {
 795         GC_push_proc(p);
 796         return;
 797       }
 798 #   endif
 799     GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
 800 }
 801
 802 # ifdef __STDC__
 803 #   define BASE(p) (word)GC_base((void *)(p))
 804 # else
 805 #   define BASE(p) (word)GC_base((char *)(p))
 806 # endif
 807
 808 /* As above, but argument passed preliminary test. */
 809 # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
 810     void GC_push_one_checked(p, interior_ptrs, source)
 811     ptr_t source;
 812 # else
 813     void GC_push_one_checked(p, interior_ptrs)
 814 #   define source 0
 815 # endif
 816 register word p;
 817 register GC_bool interior_ptrs;
 818 {
 819     register word r;
 820     register hdr * hhdr;
 821     register int displ;
 822
 823     GET_HDR(p, hhdr);
 824     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
 825         if (hhdr != 0 && interior_ptrs) {
 826           r = BASE(p);
 827           hhdr = HDR(r);
 828           displ = BYTES_TO_WORDS(HBLKDISPL(r));
 829         } else {
 830           hhdr = 0;
 831         }
 832     } else {
 833         register map_entry_type map_entry;
 834
 835         displ = HBLKDISPL(p);
 836         map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
 837         if (map_entry == OBJ_INVALID) {
 838 #         ifndef ALL_INTERIOR_POINTERS
 839             if (interior_ptrs) {
 840               r = BASE(p);
 841               displ = BYTES_TO_WORDS(HBLKDISPL(r));
 842               if (r == 0) hhdr = 0;
 843             } else {
 844               hhdr = 0;
 845             }
 846 #         else
 847             /* map already reflects interior pointers */
 848             hhdr = 0;
 849 #         endif
 850         } else {
 851           displ = BYTES_TO_WORDS(displ);
 852           displ -= map_entry;
 853           r = (word)((word *)(HBLKPTR(p)) + displ);
 854         }
 855     }
 856     /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
 857     /* displ is the word index within the block.                 */
 858     if (hhdr == 0) {
 859         if (interior_ptrs) {
 860 #           ifdef PRINT_BLACK_LIST
 861               GC_add_to_black_list_stack(p, source);
 862 #           else
 863               GC_add_to_black_list_stack(p);
 864 #           endif
 865         } else {
 866             GC_ADD_TO_BLACK_LIST_NORMAL(p, source);
 867 #           undef source  /* In case we had to define it. */
 868         }
 869     } else {
 870         if (!mark_bit_from_hdr(hhdr, displ)) {
 871             set_mark_bit_from_hdr(hhdr, displ);
 872             GC_STORE_BACK_PTR(source, (ptr_t)r);
 873             PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
 874                      &(GC_mark_stack[GC_mark_stack_size]));
 875         }
 876     }
 877 }
 878
 879 # ifdef TRACE_BUF
 880
 881 # define TRACE_ENTRIES 1000
 882
 883 struct trace_entry {
 884     char * kind;
 885     word gc_no;
 886     word words_allocd;
 887     word arg1;
 888     word arg2;
 889 } GC_trace_buf[TRACE_ENTRIES];
 890
 891 int GC_trace_buf_ptr = 0;
 892
 893 void GC_add_trace_entry(char *kind, word arg1, word arg2)
 894 {
 895     GC_trace_buf[GC_trace_buf_ptr].kind = kind;
 896     GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
 897     GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
 898     GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
 899     GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
 900     GC_trace_buf_ptr++;
 901     if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
 902 }
 903
 904 void GC_print_trace(word gc_no, GC_bool lock)
 905 {
 906     int i;
 907     struct trace_entry *p;
 908
 909     if (lock) LOCK();
 910     for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
 911         if (i < 0) i = TRACE_ENTRIES-1;
 912         p = GC_trace_buf + i;
 913         if (p -> gc_no < gc_no || p -> kind == 0) return;
 914         printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
 915                 p -> kind, p -> gc_no, p -> words_allocd,
 916                 (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
 917     }
 918     printf("Trace incomplete\n");
 919     if (lock) UNLOCK();
 920 }
 921
 922 # endif /* TRACE_BUF */
 923
 924 /*
 925  * A version of GC_push_all that treats all interior pointers as valid
 926  * and scans the entire region immediately, in case the contents
 927  * change.
 928  */
 929 void GC_push_all_eager(bottom, top)
 930 ptr_t bottom;
 931 ptr_t top;
 932 {
 933     word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
 934     word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
 935     register word *p;
 936     register word q;
 937     register word *lim;
 938     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
 939     register ptr_t least_ha = GC_least_plausible_heap_addr;
 940 #   define GC_greatest_plausible_heap_addr greatest_ha
 941 #   define GC_least_plausible_heap_addr least_ha
 942
 943     if (top == 0) return;
 944     /* check all pointers in range and put in push if they appear */
 945     /* to be valid.                                               */
 946       lim = t - 1 /* longword */;
 947       for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
 948         q = *p;
 949         GC_PUSH_ONE_STACK(q, p);
 950       }
 951 #   undef GC_greatest_plausible_heap_addr
 952 #   undef GC_least_plausible_heap_addr
 953 }
 954
 955 #ifndef THREADS
 956 /*
 957  * A version of GC_push_all that treats all interior pointers as valid
 958  * and scans part of the area immediately, to make sure that saved
 959  * register values are not lost.
 960  * Cold_gc_frame delimits the stack section that must be scanned
 961  * eagerly.  A zero value indicates that no eager scanning is needed.
 962  */
 963 void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame)
 964 ptr_t bottom;
 965 ptr_t top;
 966 ptr_t cold_gc_frame;
 967 {
 968 # ifdef ALL_INTERIOR_POINTERS
 969 #   define EAGER_BYTES 1024
 970     /* Push the hot end of the stack eagerly, so that register values   */
 971     /* saved inside GC frames are marked before they disappear.         */
 972     /* The rest of the marking can be deferred until later.             */
 973     if (0 == cold_gc_frame) {
 974         GC_push_all_stack(bottom, top);
 975         return;
 976     }
 977 #   ifdef STACK_GROWS_DOWN
 978         GC_push_all_eager(bottom, cold_gc_frame);
 979         GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
 980 #   else /* STACK_GROWS_UP */
 981         GC_push_all_eager(cold_gc_frame, top);
 982         GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
 983 #   endif /* STACK_GROWS_UP */
 984 # else
 985     GC_push_all_eager(bottom, top);
 986 # endif
 987 # ifdef TRACE_BUF
 988       GC_add_trace_entry("GC_push_all_stack", bottom, top);
 989 # endif
 990 }
 991 #endif /* !THREADS */
 992
 993 void GC_push_all_stack(bottom, top)
 994 ptr_t bottom;
 995 ptr_t top;
 996 {
 997 # ifdef ALL_INTERIOR_POINTERS
 998     GC_push_all(bottom, top);
 999 # else
1000     GC_push_all_eager(bottom, top);
1001 # endif
1002 }
1003
1004 #ifndef SMALL_CONFIG
1005 /* Push all objects reachable from marked objects in the given block */
1006 /* of size 1 objects.                                                */
1007 void GC_push_marked1(h, hhdr)
1008 struct hblk *h;
1009 register hdr * hhdr;
1010 {
1011     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
1012     register word *p;
1013     word *plim;
1014     register int i;
1015     register word q;
1016     register word mark_word;
1017     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1018     register ptr_t least_ha = GC_least_plausible_heap_addr;
1019 #   define GC_greatest_plausible_heap_addr greatest_ha
1020 #   define GC_least_plausible_heap_addr least_ha
1021
1022     p = (word *)(h->hb_body);
1023     plim = (word *)(((word)h) + HBLKSIZE);
1024
1025     /* go through all words in block */
1026         while( p < plim )  {
1027             mark_word = *mark_word_addr++;
1028             i = 0;
1029             while(mark_word != 0) {
1030               if (mark_word & 1) {
1031                   q = p[i];
1032                   GC_PUSH_ONE_HEAP(q, p + i);
1033               }
1034               i++;
1035               mark_word >>= 1;
1036             }
1037             p += WORDSZ;
1038         }
1039 #   undef GC_greatest_plausible_heap_addr
1040 #   undef GC_least_plausible_heap_addr
1041 }
1042
1043
1044 #ifndef UNALIGNED
1045
1046 /* Push all objects reachable from marked objects in the given block */
1047 /* of size 2 objects.                                                */
1048 void GC_push_marked2(h, hhdr)
1049 struct hblk *h;
1050 register hdr * hhdr;
1051 {
1052     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
1053     register word *p;
1054     word *plim;
1055     register int i;
1056     register word q;
1057     register word mark_word;
1058     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1059     register ptr_t least_ha = GC_least_plausible_heap_addr;
1060 #   define GC_greatest_plausible_heap_addr greatest_ha
1061 #   define GC_least_plausible_heap_addr least_ha
1062
1063     p = (word *)(h->hb_body);
1064     plim = (word *)(((word)h) + HBLKSIZE);
1065
1066     /* go through all words in block */
1067         while( p < plim )  {
1068             mark_word = *mark_word_addr++;
1069             i = 0;
1070             while(mark_word != 0) {
1071               if (mark_word & 1) {
1072                   q = p[i];
1073                   GC_PUSH_ONE_HEAP(q, p + i);
1074                   q = p[i+1];
1075                   GC_PUSH_ONE_HEAP(q, p + i);
1076               }
1077               i += 2;
1078               mark_word >>= 2;
1079             }
1080             p += WORDSZ;
1081         }
1082 #   undef GC_greatest_plausible_heap_addr
1083 #   undef GC_least_plausible_heap_addr
1084 }
1085
1086 /* Push all objects reachable from marked objects in the given block */
1087 /* of size 4 objects.                                                */
1088 /* There is a risk of mark stack overflow here.  But we handle that. */
1089 /* And only unmarked objects get pushed, so it's not very likely.    */
1090 void GC_push_marked4(h, hhdr)
1091 struct hblk *h;
1092 register hdr * hhdr;
1093 {
1094     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
1095     register word *p;
1096     word *plim;
1097     register int i;
1098     register word q;
1099     register word mark_word;
1100     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1101     register ptr_t least_ha = GC_least_plausible_heap_addr;
1102 #   define GC_greatest_plausible_heap_addr greatest_ha
1103 #   define GC_least_plausible_heap_addr least_ha
1104
1105     p = (word *)(h->hb_body);
1106     plim = (word *)(((word)h) + HBLKSIZE);
1107
1108     /* go through all words in block */
1109         while( p < plim )  {
1110             mark_word = *mark_word_addr++;
1111             i = 0;
1112             while(mark_word != 0) {
1113               if (mark_word & 1) {
1114                   q = p[i];
1115                   GC_PUSH_ONE_HEAP(q, p + i);
1116                   q = p[i+1];
1117                   GC_PUSH_ONE_HEAP(q, p + i + 1);
1118                   q = p[i+2];
1119                   GC_PUSH_ONE_HEAP(q, p + i + 2);
1120                   q = p[i+3];
1121                   GC_PUSH_ONE_HEAP(q, p + i + 3);
1122               }
1123               i += 4;
1124               mark_word >>= 4;
1125             }
1126             p += WORDSZ;
1127         }
1128 #   undef GC_greatest_plausible_heap_addr
1129 #   undef GC_least_plausible_heap_addr
1130 }
1131
1132 #endif /* UNALIGNED */
1133
1134 #endif /* SMALL_CONFIG */
1135
1136 /* Push all objects reachable from marked objects in the given block */
1137 void GC_push_marked(h, hhdr)
1138 struct hblk *h;
1139 register hdr * hhdr;
1140 {
1141     register int sz = hhdr -> hb_sz;
1142     register int descr = hhdr -> hb_descr;
1143     register word * p;
1144     register int word_no;
1145     register word * lim;
1146     register mse * GC_mark_stack_top_reg;
1147     register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
1148
1149     /* Some quick shortcuts: */
1150         if ((0 | DS_LENGTH) == descr) return;
1151         if (GC_block_empty(hhdr)/* nothing marked */) return;
1152 #   ifdef GATHERSTATS
1153         GC_n_rescuing_pages++;
1154 #   endif
1155     GC_objects_are_marked = TRUE;
1156     if (sz > MAXOBJSZ) {
1157         lim = (word *)h + HDR_WORDS;
1158     } else {
1159         lim = (word *)(h + 1) - sz;
1160     }
1161
1162     switch(sz) {
1163 #   if !defined(SMALL_CONFIG)
1164      case 1:
1165        GC_push_marked1(h, hhdr);
1166        break;
1167 #   endif
1168 #   if !defined(SMALL_CONFIG) && !defined(UNALIGNED)
1169      case 2:
1170        GC_push_marked2(h, hhdr);
1171        break;
1172      case 4:
1173        GC_push_marked4(h, hhdr);
1174        break;
1175 #   endif
1176      default:
1177       GC_mark_stack_top_reg = GC_mark_stack_top;
1178       for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim;
1179          p += sz, word_no += sz) {
1180          if (mark_bit_from_hdr(hhdr, word_no)) {
1181            /* Mark from fields inside the object */
1182              PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1183 #            ifdef GATHERSTATS
1184                 /* Subtract this object from total, since it was        */
1185                 /* added in twice.                                      */
1186                 GC_composite_in_use -= sz;
1187 #            endif
1188          }
1189       }
1190       GC_mark_stack_top = GC_mark_stack_top_reg;
1191     }
1192 }
1193
1194 #ifndef SMALL_CONFIG
1195 /* Test whether any page in the given block is dirty    */
1196 GC_bool GC_block_was_dirty(h, hhdr)
1197 struct hblk *h;
1198 register hdr * hhdr;
1199 {
1200     register int sz = hhdr -> hb_sz;
1201
1202     if (sz < MAXOBJSZ) {
1203          return(GC_page_was_dirty(h));
1204     } else {
1205          register ptr_t p = (ptr_t)h;
1206          sz += HDR_WORDS;
1207          sz = WORDS_TO_BYTES(sz);
1208          while (p < (ptr_t)h + sz) {
1209              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1210              p += HBLKSIZE;
1211          }
1212          return(FALSE);
1213     }
1214 }
1215 #endif /* SMALL_CONFIG */
1216
1217 /* Similar to GC_push_next_marked, but return address of next block     */
1218 struct hblk * GC_push_next_marked(h)
1219 struct hblk *h;
1220 {
1221     register hdr * hhdr;
1222
1223     h = GC_next_used_block(h);
1224     if (h == 0) return(0);
1225     hhdr = HDR(h);
1226     GC_push_marked(h, hhdr);
1227     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1228 }
1229
1230 #ifndef SMALL_CONFIG
1231 /* Identical to above, but mark only from dirty pages   */
1232 struct hblk * GC_push_next_marked_dirty(h)
1233 struct hblk *h;
1234 {
1235     register hdr * hhdr;
1236
1237     if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
1238     for (;;) {
1239         h = GC_next_used_block(h);
1240         if (h == 0) return(0);
1241         hhdr = HDR(h);
1242 #       ifdef STUBBORN_ALLOC
1243           if (hhdr -> hb_obj_kind == STUBBORN) {
1244             if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
1245                 break;
1246             }
1247           } else {
1248             if (GC_block_was_dirty(h, hhdr)) break;
1249           }
1250 #       else
1251           if (GC_block_was_dirty(h, hhdr)) break;
1252 #       endif
1253         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1254     }
1255     GC_push_marked(h, hhdr);
1256     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1257 }
1258 #endif
1259
1260 /* Similar to above, but for uncollectable pages.  Needed since we      */
1261 /* do not clear marks for such pages, even for full collections.        */
1262 struct hblk * GC_push_next_marked_uncollectable(h)
1263 struct hblk *h;
1264 {
1265     register hdr * hhdr = HDR(h);
1266
1267     for (;;) {
1268         h = GC_next_used_block(h);
1269         if (h == 0) return(0);
1270         hhdr = HDR(h);
1271         if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
1272         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1273     }
1274     GC_push_marked(h, hhdr);
1275     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1276 }
1277
1278