src/mm/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  * Copyright (c) 2000 by Hewlett-Packard Company.  All rights reserved.
   6  *
   7  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
   8  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
   9  *
  10  * Permission is hereby granted to use or copy this program
  11  * for any purpose,  provided the above notices are retained on all copies.
  12  * Permission to modify the code and to distribute modified code is granted,
  13  * provided the above notices are retained, and a notice that the code was
  14  * modified is included with the above copyright notice.
  15  *
  16  */
  17
  18 #include "config.h"
  19
  20 # include <stdio.h>
  21 # include "private/gc_pmark.h"
  22
  23 #if defined(MSWIN32) && defined(__GNUC__)
  24 # include <excpt.h>
  25 #endif
  26
  27 /* We put this here to minimize the risk of inlining. */
  28 /*VARARGS*/
  29 #ifdef __WATCOMC__
  30   void GC_noop(void *p, ...) {}
  31 #else
  32   void GC_noop() {}
  33 #endif
  34
  35 /* Single argument version, robust against whole program analysis. */
  36 void GC_noop1(x)
  37 word x;
  38 {
  39     static VOLATILE word sink;
  40
  41     sink = x;
  42 }
  43
  44 /* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */
  45
  46 word GC_n_mark_procs = GC_RESERVED_MARK_PROCS;
  47
  48 /* Initialize GC_obj_kinds properly and standard free lists properly.   */
  49 /* This must be done statically since they may be accessed before       */
  50 /* GC_init is called.                                                   */
  51 /* It's done here, since we need to deal with mark descriptors.         */
  52 struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
  53 /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,
  54                 0 | GC_DS_LENGTH, FALSE, FALSE },
  55 /* NORMAL  */ { &GC_objfreelist[0], 0,
  56                 0 | GC_DS_LENGTH,  /* Adjusted in GC_init_inner for EXTRA_BYTES */
  57                 TRUE /* add length to descr */, TRUE },
  58 /* UNCOLLECTABLE */
  59               { &GC_uobjfreelist[0], 0,
  60                 0 | GC_DS_LENGTH, TRUE /* add length to descr */, TRUE },
  61 # ifdef ATOMIC_UNCOLLECTABLE
  62    /* AUNCOLLECTABLE */
  63               { &GC_auobjfreelist[0], 0,
  64                 0 | GC_DS_LENGTH, FALSE /* add length to descr */, FALSE },
  65 # endif
  66 # ifdef STUBBORN_ALLOC
  67 /*STUBBORN*/ { &GC_sobjfreelist[0], 0,
  68                 0 | GC_DS_LENGTH, TRUE /* add length to descr */, TRUE },
  69 # endif
  70 };
  71
  72 # ifdef ATOMIC_UNCOLLECTABLE
  73 #   ifdef STUBBORN_ALLOC
  74       int GC_n_kinds = 5;
  75 #   else
  76       int GC_n_kinds = 4;
  77 #   endif
  78 # else
  79 #   ifdef STUBBORN_ALLOC
  80       int GC_n_kinds = 4;
  81 #   else
  82       int GC_n_kinds = 3;
  83 #   endif
  84 # endif
  85
  86
  87 # ifndef INITIAL_MARK_STACK_SIZE
  88 #   define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
  89                 /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a    */
  90                 /* multiple of HBLKSIZE.                                */
  91                 /* The incremental collector actually likes a larger    */
  92                 /* size, since it want to push all marked dirty objs    */
  93                 /* before marking anything new.  Currently we let it    */
  94                 /* grow dynamically.                                    */
  95 # endif
  96
  97 /*
  98  * Limits of stack for GC_mark routine.
  99  * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
 100  * need to be marked from.
 101  */
 102
 103 word GC_n_rescuing_pages;       /* Number of dirty pages we marked from */
 104                                 /* excludes ptrfree pages, etc.         */
 105
 106 mse * GC_mark_stack;
 107
 108 mse * GC_mark_stack_limit;
 109
 110 word GC_mark_stack_size = 0;
 111
 112 #ifdef PARALLEL_MARK
 113   mse * VOLATILE GC_mark_stack_top;
 114 #else
 115   mse * GC_mark_stack_top;
 116 #endif
 117
 118 static struct hblk * scan_ptr;
 119
 120 mark_state_t GC_mark_state = MS_NONE;
 121
 122 GC_bool GC_mark_stack_too_small = FALSE;
 123
 124 GC_bool GC_objects_are_marked = FALSE;  /* Are there collectable marked */
 125                                         /* objects in the heap?         */
 126
 127 /* Is a collection in progress?  Note that this can return true in the  */
 128 /* nonincremental case, if a collection has been abandoned and the      */
 129 /* mark state is now MS_INVALID.                                        */
 130 GC_bool GC_collection_in_progress()
 131 {
 132     return(GC_mark_state != MS_NONE);
 133 }
 134
 135 /* clear all mark bits in the header */
 136 void GC_clear_hdr_marks(hhdr)
 137 register hdr * hhdr;
 138 {
 139 #   ifdef USE_MARK_BYTES
 140       BZERO(hhdr -> hb_marks, MARK_BITS_SZ);
 141 #   else
 142       BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
 143 #   endif
 144 }
 145
 146 /* Set all mark bits in the header.  Used for uncollectable blocks. */
 147 void GC_set_hdr_marks(hhdr)
 148 register hdr * hhdr;
 149 {
 150     register int i;
 151
 152     for (i = 0; i < MARK_BITS_SZ; ++i) {
 153 #     ifdef USE_MARK_BYTES
 154         hhdr -> hb_marks[i] = 1;
 155 #     else
 156         hhdr -> hb_marks[i] = ONES;
 157 #     endif
 158     }
 159 }
 160
 161 /*
 162  * Clear all mark bits associated with block h.
 163  */
 164 /*ARGSUSED*/
 165 # if defined(__STDC__) || defined(__cplusplus)
 166     static void clear_marks_for_block(struct hblk *h, word dummy)
 167 # else
 168     static void clear_marks_for_block(h, dummy)
 169     struct hblk *h;
 170     word dummy;
 171 # endif
 172 {
 173     register hdr * hhdr = HDR(h);
 174
 175     if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;
 176         /* Mark bit for these is cleared only once the object is        */
 177         /* explicitly deallocated.  This either frees the block, or     */
 178         /* the bit is cleared once the object is on the free list.      */
 179     GC_clear_hdr_marks(hhdr);
 180 }
 181
 182 /* Slow but general routines for setting/clearing/asking about mark bits */
 183 void GC_set_mark_bit(p)
 184 ptr_t p;
 185 {
 186     register struct hblk *h = HBLKPTR(p);
 187     register hdr * hhdr = HDR(h);
 188     register int word_no = (word *)p - (word *)h;
 189
 190     set_mark_bit_from_hdr(hhdr, word_no);
 191 }
 192
 193 void GC_clear_mark_bit(p)
 194 ptr_t p;
 195 {
 196     register struct hblk *h = HBLKPTR(p);
 197     register hdr * hhdr = HDR(h);
 198     register int word_no = (word *)p - (word *)h;
 199
 200     clear_mark_bit_from_hdr(hhdr, word_no);
 201 }
 202
 203 GC_bool GC_is_marked(p)
 204 ptr_t p;
 205 {
 206     register struct hblk *h = HBLKPTR(p);
 207     register hdr * hhdr = HDR(h);
 208     register int word_no = (word *)p - (word *)h;
 209
 210     return(mark_bit_from_hdr(hhdr, word_no));
 211 }
 212
 213
 214 /*
 215  * Clear mark bits in all allocated heap blocks.  This invalidates
 216  * the marker invariant, and sets GC_mark_state to reflect this.
 217  * (This implicitly starts marking to reestablish the invariant.)
 218  */
 219 void GC_clear_marks()
 220 {
 221     GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
 222     GC_objects_are_marked = FALSE;
 223     GC_mark_state = MS_INVALID;
 224     scan_ptr = 0;
 225 #   ifdef GATHERSTATS
 226         /* Counters reflect currently marked objects: reset here */
 227         GC_composite_in_use = 0;
 228         GC_atomic_in_use = 0;
 229 #   endif
 230
 231 }
 232
 233 /* Initiate a garbage collection.  Initiates a full collection if the   */
 234 /* mark state is invalid.                                               */
 235 /*ARGSUSED*/
 236 void GC_initiate_gc()
 237 {
 238     if (GC_dirty_maintained) GC_read_dirty();
 239 #   ifdef STUBBORN_ALLOC
 240         GC_read_changed();
 241 #   endif
 242 #   ifdef CHECKSUMS
 243         {
 244             extern void GC_check_dirty();
 245
 246             if (GC_dirty_maintained) GC_check_dirty();
 247         }
 248 #   endif
 249     GC_n_rescuing_pages = 0;
 250     if (GC_mark_state == MS_NONE) {
 251         GC_mark_state = MS_PUSH_RESCUERS;
 252     } else if (GC_mark_state != MS_INVALID) {
 253         ABORT("unexpected state");
 254     } /* else this is really a full collection, and mark        */
 255       /* bits are invalid.                                      */
 256     scan_ptr = 0;
 257 }
 258
 259
 260 static void alloc_mark_stack();
 261
 262 /* Perform a small amount of marking.                   */
 263 /* We try to touch roughly a page of memory.            */
 264 /* Return TRUE if we just finished a mark phase.        */
 265 /* Cold_gc_frame is an address inside a GC frame that   */
 266 /* remains valid until all marking is complete.         */
 267 /* A zero value indicates that it's OK to miss some     */
 268 /* register values.                                     */
 269 /* We hold the allocation lock.  In the case of         */
 270 /* incremental collection, the world may not be stopped.*/
 271 #ifdef MSWIN32
 272   /* For win32, this is called after we establish a structured  */
 273   /* exception handler, in case Windows unmaps one of our root  */
 274   /* segments.  See below.  In either case, we acquire the      */
 275   /* allocator lock long before we get here.                    */
 276   GC_bool GC_mark_some_inner(cold_gc_frame)
 277   ptr_t cold_gc_frame;
 278 #else
 279   GC_bool GC_mark_some(cold_gc_frame)
 280   ptr_t cold_gc_frame;
 281 #endif
 282 {
 283     switch(GC_mark_state) {
 284         case MS_NONE:
 285             return(FALSE);
 286
 287         case MS_PUSH_RESCUERS:
 288             if (GC_mark_stack_top
 289                 >= GC_mark_stack_limit - INITIAL_MARK_STACK_SIZE/2) {
 290                 /* Go ahead and mark, even though that might cause us to */
 291                 /* see more marked dirty objects later on.  Avoid this   */
 292                 /* in the future.                                        */
 293                 GC_mark_stack_too_small = TRUE;
 294                 MARK_FROM_MARK_STACK();
 295                 return(FALSE);
 296             } else {
 297                 scan_ptr = GC_push_next_marked_dirty(scan_ptr);
 298                 if (scan_ptr == 0) {
 299 #                   ifdef CONDPRINT
 300                       if (GC_print_stats) {
 301                         GC_printf1("Marked from %lu dirty pages\n",
 302                                    (unsigned long)GC_n_rescuing_pages);
 303                       }
 304 #                   endif
 305                     GC_push_roots(FALSE, cold_gc_frame);
 306                     GC_objects_are_marked = TRUE;
 307                     if (GC_mark_state != MS_INVALID) {
 308                         GC_mark_state = MS_ROOTS_PUSHED;
 309                     }
 310                 }
 311             }
 312             return(FALSE);
 313
 314         case MS_PUSH_UNCOLLECTABLE:
 315             if (GC_mark_stack_top
 316                 >= GC_mark_stack + GC_mark_stack_size/4) {
 317 #               ifdef PARALLEL_MARK
 318                   /* Avoid this, since we don't parallelize the marker  */
 319                   /* here.                                              */
 320                   if (GC_parallel) GC_mark_stack_too_small = TRUE;
 321 #               endif
 322                 MARK_FROM_MARK_STACK();
 323                 return(FALSE);
 324             } else {
 325                 scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
 326                 if (scan_ptr == 0) {
 327                     GC_push_roots(TRUE, cold_gc_frame);
 328                     GC_objects_are_marked = TRUE;
 329                     if (GC_mark_state != MS_INVALID) {
 330                         GC_mark_state = MS_ROOTS_PUSHED;
 331                     }
 332                 }
 333             }
 334             return(FALSE);
 335
 336         case MS_ROOTS_PUSHED:
 337 #           ifdef PARALLEL_MARK
 338               /* In the incremental GC case, this currently doesn't     */
 339               /* quite do the right thing, since it runs to             */
 340               /* completion.  On the other hand, starting a             */
 341               /* parallel marker is expensive, so perhaps it is         */
 342               /* the right thing?                                       */
 343               /* Eventually, incremental marking should run             */
 344               /* asynchronously in multiple threads, without grabbing   */
 345               /* the allocation lock.                                   */
 346                 if (GC_parallel) {
 347                   GC_do_parallel_mark();
 348                   GC_ASSERT(GC_mark_stack_top < GC_first_nonempty);
 349                   GC_mark_stack_top = GC_mark_stack - 1;
 350                   if (GC_mark_stack_too_small) {
 351                     alloc_mark_stack(2*GC_mark_stack_size);
 352                   }
 353                   if (GC_mark_state == MS_ROOTS_PUSHED) {
 354                     GC_mark_state = MS_NONE;
 355                     return(TRUE);
 356                   } else {
 357                     return(FALSE);
 358                   }
 359                 }
 360 #           endif
 361             if (GC_mark_stack_top >= GC_mark_stack) {
 362                 MARK_FROM_MARK_STACK();
 363                 return(FALSE);
 364             } else {
 365                 GC_mark_state = MS_NONE;
 366                 if (GC_mark_stack_too_small) {
 367                     alloc_mark_stack(2*GC_mark_stack_size);
 368                 }
 369                 return(TRUE);
 370             }
 371
 372         case MS_INVALID:
 373         case MS_PARTIALLY_INVALID:
 374             if (!GC_objects_are_marked) {
 375                 GC_mark_state = MS_PUSH_UNCOLLECTABLE;
 376                 return(FALSE);
 377             }
 378             if (GC_mark_stack_top >= GC_mark_stack) {
 379                 MARK_FROM_MARK_STACK();
 380                 return(FALSE);
 381             }
 382             if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
 383                 /* About to start a heap scan for marked objects. */
 384                 /* Mark stack is empty.  OK to reallocate.        */
 385                 if (GC_mark_stack_too_small) {
 386                     alloc_mark_stack(2*GC_mark_stack_size);
 387                 }
 388                 GC_mark_state = MS_PARTIALLY_INVALID;
 389             }
 390             scan_ptr = GC_push_next_marked(scan_ptr);
 391             if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
 392                 GC_push_roots(TRUE, cold_gc_frame);
 393                 GC_objects_are_marked = TRUE;
 394                 if (GC_mark_state != MS_INVALID) {
 395                     GC_mark_state = MS_ROOTS_PUSHED;
 396                 }
 397             }
 398             return(FALSE);
 399         default:
 400             ABORT("GC_mark_some: bad state");
 401             return(FALSE);
 402     }
 403 }
 404
 405
 406 #ifdef MSWIN32
 407
 408 # ifdef __GNUC__
 409
 410     typedef struct {
 411       EXCEPTION_REGISTRATION ex_reg;
 412       void *alt_path;
 413     } ext_ex_regn;
 414
 415
 416     static EXCEPTION_DISPOSITION mark_ex_handler(
 417         struct _EXCEPTION_RECORD *ex_rec,
 418         void *est_frame,
 419         struct _CONTEXT *context,
 420         void *disp_ctxt)
 421     {
 422         if (ex_rec->ExceptionCode == STATUS_ACCESS_VIOLATION) {
 423           ext_ex_regn *xer = (ext_ex_regn *)est_frame;
 424
 425           /* Unwind from the inner function assuming the standard */
 426           /* function prologue.                                   */
 427           /* Assumes code has not been compiled with              */
 428           /* -fomit-frame-pointer.                                */
 429           context->Esp = context->Ebp;
 430           context->Ebp = *((DWORD *)context->Esp);
 431           context->Esp = context->Esp - 8;
 432
 433           /* Resume execution at the "real" handler within the    */
 434           /* wrapper function.                                    */
 435           context->Eip = (DWORD )(xer->alt_path);
 436
 437           return ExceptionContinueExecution;
 438
 439         } else {
 440             return ExceptionContinueSearch;
 441         }
 442     }
 443 # endif /* __GNUC__ */
 444
 445
 446   GC_bool GC_mark_some(cold_gc_frame)
 447   ptr_t cold_gc_frame;
 448   {
 449       GC_bool ret_val;
 450
 451 #   ifndef __GNUC__
 452       /* Windows 98 appears to asynchronously create and remove  */
 453       /* writable memory mappings, for reasons we haven't yet    */
 454       /* understood.  Since we look for writable regions to      */
 455       /* determine the root set, we may try to mark from an      */
 456       /* address range that disappeared since we started the     */
 457       /* collection.  Thus we have to recover from faults here.  */
 458       /* This code does not appear to be necessary for Windows   */
 459       /* 95/NT/2000. Note that this code should never generate   */
 460       /* an incremental GC write fault.                          */
 461
 462       __try {
 463
 464 #   else /* __GNUC__ */
 465
 466       /* Manually install an exception handler since GCC does    */
 467       /* not yet support Structured Exception Handling (SEH) on  */
 468       /* Win32.                                                  */
 469
 470       ext_ex_regn er;
 471
 472       er.alt_path = &&handle_ex;
 473       er.ex_reg.handler = mark_ex_handler;
 474       asm volatile ("movl %%fs:0, %0" : "=r" (er.ex_reg.prev));
 475       asm volatile ("movl %0, %%fs:0" : : "r" (&er));
 476
 477 #   endif /* __GNUC__ */
 478
 479           ret_val = GC_mark_some_inner(cold_gc_frame);
 480
 481 #   ifndef __GNUC__
 482
 483       } __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
 484                 EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {
 485
 486 #   else /* __GNUC__ */
 487
 488           /* Prevent GCC from considering the following code unreachable */
 489           /* and thus eliminating it.                                    */
 490           if (er.alt_path != 0)
 491               goto rm_handler;
 492
 493 handle_ex:
 494           /* Execution resumes from here on an access violation. */
 495
 496 #   endif /* __GNUC__ */
 497
 498 #         ifdef CONDPRINT
 499             if (GC_print_stats) {
 500               GC_printf0("Caught ACCESS_VIOLATION in marker. "
 501                          "Memory mapping disappeared.\n");
 502             }
 503 #         endif /* CONDPRINT */
 504
 505           /* We have bad roots on the stack.  Discard mark stack.  */
 506           /* Rescan from marked objects.  Redetermine roots.     */
 507           GC_invalidate_mark_state();
 508           scan_ptr = 0;
 509
 510           ret_val = FALSE;
 511
 512 #   ifndef __GNUC__
 513
 514       }
 515
 516 #   else /* __GNUC__ */
 517
 518 rm_handler:
 519       /* Uninstall the exception handler */
 520       asm volatile ("mov %0, %%fs:0" : : "r" (er.ex_reg.prev));
 521
 522 #   endif /* __GNUC__ */
 523
 524       return ret_val;
 525   }
 526 #endif /* MSWIN32 */
 527
 528
 529 GC_bool GC_mark_stack_empty()
 530 {
 531     return(GC_mark_stack_top < GC_mark_stack);
 532 }
 533
 534 #ifdef PROF_MARKER
 535     word GC_prof_array[10];
 536 #   define PROF(n) GC_prof_array[n]++
 537 #else
 538 #   define PROF(n)
 539 #endif
 540
 541 /* Given a pointer to someplace other than a small object page or the   */
 542 /* first page of a large object, either:                                */
 543 /*      - return a pointer to somewhere in the first page of the large  */
 544 /*        object, if current points to a large object.                  */
 545 /*        In this case *hhdr is replaced with a pointer to the header   */
 546 /*        for the large object.                                         */
 547 /*      - just return current if it does not point to a large object.   */
 548 /*ARGSUSED*/
 549 ptr_t GC_find_start(current, hhdr, new_hdr_p)
 550 register ptr_t current;
 551 register hdr *hhdr, **new_hdr_p;
 552 {
 553     if (GC_all_interior_pointers) {
 554         if (hhdr != 0) {
 555             register ptr_t orig = current;
 556
 557             current = (ptr_t)HBLKPTR(current);
 558             do {
 559               current = current - HBLKSIZE*(word)hhdr;
 560               hhdr = HDR(current);
 561             } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
 562             /* current points to near the start of the large object */
 563             if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(orig);
 564             if ((word *)orig - (word *)current
 565                  >= (ptrdiff_t)(hhdr->hb_sz)) {
 566                 /* Pointer past the end of the block */
 567                 return(orig);
 568             }
 569             *new_hdr_p = hhdr;
 570             return(current);
 571         } else {
 572             return(current);
 573         }
 574     } else {
 575         return(current);
 576     }
 577 }
 578
 579 void GC_invalidate_mark_state()
 580 {
 581     GC_mark_state = MS_INVALID;
 582     GC_mark_stack_top = GC_mark_stack-1;
 583 }
 584
 585 mse * GC_signal_mark_stack_overflow(msp)
 586 mse * msp;
 587 {
 588     GC_mark_state = MS_INVALID;
 589     GC_mark_stack_too_small = TRUE;
 590 #   ifdef CONDPRINT
 591       if (GC_print_stats) {
 592         GC_printf1("Mark stack overflow; current size = %lu entries\n",
 593                     GC_mark_stack_size);
 594       }
 595 #   endif
 596     return(msp - GC_MARK_STACK_DISCARDS);
 597 }
 598
 599 /*
 600  * Mark objects pointed to by the regions described by
 601  * mark stack entries between GC_mark_stack and GC_mark_stack_top,
 602  * inclusive.  Assumes the upper limit of a mark stack entry
 603  * is never 0.  A mark stack entry never has size 0.
 604  * We try to traverse on the order of a hblk of memory before we return.
 605  * Caller is responsible for calling this until the mark stack is empty.
 606  * Note that this is the most performance critical routine in the
 607  * collector.  Hence it contains all sorts of ugly hacks to speed
 608  * things up.  In particular, we avoid procedure calls on the common
 609  * path, we take advantage of peculiarities of the mark descriptor
 610  * encoding, we optionally maintain a cache for the block address to
 611  * header mapping, we prefetch when an object is "grayed", etc.
 612  */
 613 mse * GC_mark_from(mark_stack_top, mark_stack, mark_stack_limit)
 614 mse * mark_stack_top;
 615 mse * mark_stack;
 616 mse * mark_stack_limit;
 617 {
 618   int credit = HBLKSIZE;        /* Remaining credit for marking work    */
 619   register word * current_p;    /* Pointer to current candidate ptr.    */
 620   register word current;        /* Candidate pointer.                   */
 621   register word * limit;        /* (Incl) limit of current candidate    */
 622                                 /* range                                */
 623   register word descr;
 624   register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
 625   register ptr_t least_ha = GC_least_plausible_heap_addr;
 626   DECLARE_HDR_CACHE;
 627
 628 # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.          */
 629
 630   GC_objects_are_marked = TRUE;
 631   INIT_HDR_CACHE;
 632 # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
 633   while (mark_stack_top >= mark_stack && credit >= 0) {
 634 # else
 635   while ((((ptr_t)mark_stack_top - (ptr_t)mark_stack) | credit)
 636         >= 0) {
 637 # endif
 638     current_p = mark_stack_top -> mse_start;
 639     descr = mark_stack_top -> mse_descr;
 640   retry:
 641     /* current_p and descr describe the current object.         */
 642     /* *mark_stack_top is vacant.                               */
 643     /* The following is 0 only for small objects described by a simple  */
 644     /* length descriptor.  For many applications this is the common     */
 645     /* case, so we try to detect it quickly.                            */
 646     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | GC_DS_TAGS)) {
 647       word tag = descr & GC_DS_TAGS;
 648
 649       switch(tag) {
 650         case GC_DS_LENGTH:
 651           /* Large length.                                              */
 652           /* Process part of the range to avoid pushing too much on the */
 653           /* stack.                                                     */
 654           GC_ASSERT(descr < (word)GC_greatest_plausible_heap_addr
 655                             - (word)GC_least_plausible_heap_addr);
 656 #         ifdef PARALLEL_MARK
 657 #           define SHARE_BYTES 2048
 658             if (descr > SHARE_BYTES && GC_parallel
 659                 && mark_stack_top < mark_stack_limit - 1) {
 660               int new_size = (descr/2) & ~(sizeof(word)-1);
 661               mark_stack_top -> mse_start = current_p;
 662               mark_stack_top -> mse_descr = new_size + sizeof(word);
 663                                         /* makes sure we handle         */
 664                                         /* misaligned pointers.         */
 665               mark_stack_top++;
 666               current_p = (word *) ((char *)current_p + new_size);
 667               descr -= new_size;
 668               goto retry;
 669             }
 670 #         endif /* PARALLEL_MARK */
 671           mark_stack_top -> mse_start =
 672                 limit = current_p + SPLIT_RANGE_WORDS-1;
 673           mark_stack_top -> mse_descr =
 674                         descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
 675           /* Make sure that pointers overlapping the two ranges are     */
 676           /* considered.                                                */
 677           limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
 678           break;
 679         case GC_DS_BITMAP:
 680           mark_stack_top--;
 681           descr &= ~GC_DS_TAGS;
 682           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
 683           while (descr != 0) {
 684             if ((signed_word)descr < 0) {
 685               current = *current_p;
 686               FIXUP_POINTER(current);
 687               if ((ptr_t)current >= least_ha && (ptr_t)current < greatest_ha) {
 688                 PREFETCH((ptr_t)current);
 689                 HC_PUSH_CONTENTS((ptr_t)current, mark_stack_top,
 690                               mark_stack_limit, current_p, exit1);
 691               }
 692             }
 693             descr <<= 1;
 694             ++ current_p;
 695           }
 696           continue;
 697         case GC_DS_PROC:
 698           mark_stack_top--;
 699           credit -= GC_PROC_BYTES;
 700           mark_stack_top =
 701               (*PROC(descr))
 702                     (current_p, mark_stack_top,
 703                     mark_stack_limit, ENV(descr));
 704           continue;
 705         case GC_DS_PER_OBJECT:
 706           if ((signed_word)descr >= 0) {
 707             /* Descriptor is in the object.     */
 708             descr = *(word *)((ptr_t)current_p + descr - GC_DS_PER_OBJECT);
 709           } else {
 710             /* Descriptor is in type descriptor pointed to by first     */
 711             /* word in object.                                          */
 712             ptr_t type_descr = *(ptr_t *)current_p;
 713             /* type_descr is either a valid pointer to the descriptor   */
 714             /* structure, or this object was on a free list.  If it     */
 715             /* it was anything but the last object on the free list,    */
 716             /* we will misinterpret the next object on the free list as */
 717             /* the type descriptor, and get a 0 GC descriptor, which    */
 718             /* is ideal.  Unfortunately, we need to check for the last  */
 719             /* object case explicitly.                                  */
 720             if (0 == type_descr) {
 721                 /* Rarely executed.     */
 722                 mark_stack_top--;
 723                 continue;
 724             }
 725             descr = *(word *)(type_descr
 726                               - (descr - (GC_DS_PER_OBJECT
 727                                           - GC_INDIR_PER_OBJ_BIAS)));
 728           }
 729           if (0 == descr) {
 730               /* Can happen either because we generated a 0 descriptor  */
 731               /* or we saw a pointer to a free object.                  */
 732               mark_stack_top--;
 733               continue;
 734           }
 735           goto retry;
 736       }
 737     } else /* Small object with length descriptor */ {
 738       mark_stack_top--;
 739       limit = (word *)(((ptr_t)current_p) + (word)descr);
 740     }
 741     /* The simple case in which we're scanning a range. */
 742     GC_ASSERT(!((word)current_p & (ALIGNMENT-1)));
 743     credit -= (ptr_t)limit - (ptr_t)current_p;
 744     limit -= 1;
 745     {
 746 #     define PREF_DIST 4
 747
 748 #     ifndef SMALL_CONFIG
 749         word deferred;
 750
 751         /* Try to prefetch the next pointer to be examined asap.        */
 752         /* Empirically, this also seems to help slightly without        */
 753         /* prefetches, at least on linux/X86.  Presumably this loop     */
 754         /* ends up with less register pressure, and gcc thus ends up    */
 755         /* generating slightly better code.  Overall gcc code quality   */
 756         /* for this loop is still not great.                            */
 757         for(;;) {
 758           PREFETCH((ptr_t)limit - PREF_DIST*CACHE_LINE_SIZE);
 759           GC_ASSERT(limit >= current_p);
 760           deferred = *limit;
 761           FIXUP_POINTER(deferred);
 762           limit = (word *)((char *)limit - ALIGNMENT);
 763           if ((ptr_t)deferred >= least_ha && (ptr_t)deferred <  greatest_ha) {
 764             PREFETCH((ptr_t)deferred);
 765             break;
 766           }
 767           if (current_p > limit) goto next_object;
 768           /* Unroll once, so we don't do too many of the prefetches     */
 769           /* based on limit.                                            */
 770           deferred = *limit;
 771           FIXUP_POINTER(deferred);
 772           limit = (word *)((char *)limit - ALIGNMENT);
 773           if ((ptr_t)deferred >= least_ha && (ptr_t)deferred <  greatest_ha) {
 774             PREFETCH((ptr_t)deferred);
 775             break;
 776           }
 777           if (current_p > limit) goto next_object;
 778         }
 779 #     endif
 780
 781       while (current_p <= limit) {
 782         /* Empirically, unrolling this loop doesn't help a lot. */
 783         /* Since HC_PUSH_CONTENTS expands to a lot of code,     */
 784         /* we don't.                                            */
 785         current = *current_p;
 786         FIXUP_POINTER(current);
 787         PREFETCH((ptr_t)current_p + PREF_DIST*CACHE_LINE_SIZE);
 788         if ((ptr_t)current >= least_ha && (ptr_t)current <  greatest_ha) {
 789           /* Prefetch the contents of the object we just pushed.  It's  */
 790           /* likely we will need them soon.                             */
 791           PREFETCH((ptr_t)current);
 792           HC_PUSH_CONTENTS((ptr_t)current, mark_stack_top,
 793                            mark_stack_limit, current_p, exit2);
 794         }
 795         current_p = (word *)((char *)current_p + ALIGNMENT);
 796       }
 797
 798 #     ifndef SMALL_CONFIG
 799         /* We still need to mark the entry we previously prefetched.    */
 800         /* We alrady know that it passes the preliminary pointer        */
 801         /* validity test.                                               */
 802         HC_PUSH_CONTENTS((ptr_t)deferred, mark_stack_top,
 803                          mark_stack_limit, current_p, exit4);
 804         next_object:;
 805 #     endif
 806     }
 807   }
 808   return mark_stack_top;
 809 }
 810
 811 #ifdef PARALLEL_MARK
 812
 813 /* We assume we have an ANSI C Compiler.        */
 814 GC_bool GC_help_wanted = FALSE;
 815 unsigned GC_helper_count = 0;
 816 unsigned GC_active_count = 0;
 817 mse * VOLATILE GC_first_nonempty;
 818 word GC_mark_no = 0;
 819
 820 #define LOCAL_MARK_STACK_SIZE HBLKSIZE
 821         /* Under normal circumstances, this is big enough to guarantee  */
 822         /* We don't overflow half of it in a single call to             */
 823         /* GC_mark_from.                                                */
 824
 825
 826 /* Steal mark stack entries starting at mse low into mark stack local   */
 827 /* until we either steal mse high, or we have max entries.              */
 828 /* Return a pointer to the top of the local mark stack.                 */
 829 /* *next is replaced by a pointer to the next unscanned mark stack      */
 830 /* entry.                                                               */
 831 mse * GC_steal_mark_stack(mse * low, mse * high, mse * local,
 832                           unsigned max, mse **next)
 833 {
 834     mse *p;
 835     mse *top = local - 1;
 836     unsigned i = 0;
 837
 838     /* Make sure that prior writes to the mark stack are visible. */
 839     /* On some architectures, the fact that the reads are         */
 840     /* volatile should suffice.                                   */
 841 #   if !defined(IA64) && !defined(HP_PA) && !defined(I386)
 842       GC_memory_barrier();
 843 #   endif
 844     GC_ASSERT(high >= low-1 && high - low + 1 <= GC_mark_stack_size);
 845     for (p = low; p <= high && i <= max; ++p) {
 846         word descr = *(volatile word *) &(p -> mse_descr);
 847         /* In the IA64 memory model, the following volatile store is    */
 848         /* ordered after this read of descr.  Thus a thread must read   */
 849         /* the original nonzero value.  HP_PA appears to be similar,    */
 850         /* and if I'm reading the P4 spec correctly, X86 is probably    */
 851         /* also OK.  In some other cases we need a barrier.             */
 852 #       if !defined(IA64) && !defined(HP_PA) && !defined(I386)
 853           GC_memory_barrier();
 854 #       endif
 855         if (descr != 0) {
 856             *(volatile word *) &(p -> mse_descr) = 0;
 857             /* More than one thread may get this entry, but that's only */
 858             /* a minor performance problem.                             */
 859             ++top;
 860             top -> mse_descr = descr;
 861             top -> mse_start = p -> mse_start;
 862             GC_ASSERT(  (top -> mse_descr & GC_DS_TAGS) != GC_DS_LENGTH ||
 863                         top -> mse_descr < (ptr_t)GC_greatest_plausible_heap_addr
 864                                            - (ptr_t)GC_least_plausible_heap_addr);
 865             /* If this is a big object, count it as                     */
 866             /* size/256 + 1 objects.                                    */
 867             ++i;
 868             if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) i += (descr >> 8);
 869         }
 870     }
 871     *next = p;
 872     return top;
 873 }
 874
 875 /* Copy back a local mark stack.        */
 876 /* low and high are inclusive bounds.   */
 877 void GC_return_mark_stack(mse * low, mse * high)
 878 {
 879     mse * my_top;
 880     mse * my_start;
 881     size_t stack_size;
 882
 883     if (high < low) return;
 884     stack_size = high - low + 1;
 885     GC_acquire_mark_lock();
 886     my_top = GC_mark_stack_top;
 887     my_start = my_top + 1;
 888     if (my_start - GC_mark_stack + stack_size > GC_mark_stack_size) {
 889 #     ifdef CONDPRINT
 890         if (GC_print_stats) {
 891           GC_printf0("No room to copy back mark stack.");
 892         }
 893 #     endif
 894       GC_mark_state = MS_INVALID;
 895       GC_mark_stack_too_small = TRUE;
 896       /* We drop the local mark stack.  We'll fix things later. */
 897     } else {
 898       BCOPY(low, my_start, stack_size * sizeof(mse));
 899       GC_ASSERT(GC_mark_stack_top = my_top);
 900 #     if !defined(IA64) && !defined(HP_PA)
 901         GC_memory_barrier();
 902 #     endif
 903         /* On IA64, the volatile write acts as a release barrier. */
 904       GC_mark_stack_top = my_top + stack_size;
 905     }
 906     GC_release_mark_lock();
 907     GC_notify_all_marker();
 908 }
 909
 910 /* Mark from the local mark stack.              */
 911 /* On return, the local mark stack is empty.    */
 912 /* But this may be achieved by copying the      */
 913 /* local mark stack back into the global one.   */
 914 void GC_do_local_mark(mse *local_mark_stack, mse *local_top)
 915 {
 916     unsigned n;
 917 #   define N_LOCAL_ITERS 1
 918
 919 #   ifdef GC_ASSERTIONS
 920       /* Make sure we don't hold mark lock. */
 921         GC_acquire_mark_lock();
 922         GC_release_mark_lock();
 923 #   endif
 924     for (;;) {
 925         for (n = 0; n < N_LOCAL_ITERS; ++n) {
 926             local_top = GC_mark_from(local_top, local_mark_stack,
 927                                      local_mark_stack + LOCAL_MARK_STACK_SIZE);
 928             if (local_top < local_mark_stack) return;
 929             if (local_top - local_mark_stack >= LOCAL_MARK_STACK_SIZE/2) {
 930                 GC_return_mark_stack(local_mark_stack, local_top);
 931                 return;
 932             }
 933         }
 934         if (GC_mark_stack_top < GC_first_nonempty &&
 935             GC_active_count < GC_helper_count
 936             && local_top > local_mark_stack + 1) {
 937             /* Try to share the load, since the main stack is empty,    */
 938             /* and helper threads are waiting for a refill.             */
 939             /* The entries near the bottom of the stack are likely      */
 940             /* to require more work.  Thus we return those, eventhough  */
 941             /* it's harder.                                             */
 942             mse * p;
 943             mse * new_bottom = local_mark_stack
 944                                 + (local_top - local_mark_stack)/2;
 945             GC_ASSERT(new_bottom > local_mark_stack
 946                       && new_bottom < local_top);
 947             GC_return_mark_stack(local_mark_stack, new_bottom - 1);
 948             memmove(local_mark_stack, new_bottom,
 949                     (local_top - new_bottom + 1) * sizeof(mse));
 950             local_top -= (new_bottom - local_mark_stack);
 951         }
 952     }
 953 }
 954
 955 #define ENTRIES_TO_GET 5
 956
 957 long GC_markers = 2;            /* Normally changed by thread-library-  */
 958                                 /* -specific code.                      */
 959
 960 /* Mark using the local mark stack until the global mark stack is empty */
 961 /* and there are no active workers. Update GC_first_nonempty to reflect */
 962 /* progress.                                                            */
 963 /* Caller does not hold mark lock.                                      */
 964 /* Caller has already incremented GC_helper_count.  We decrement it,    */
 965 /* and maintain GC_active_count.                                        */
 966 void GC_mark_local(mse *local_mark_stack, int id)
 967 {
 968     mse * my_first_nonempty;
 969
 970     GC_acquire_mark_lock();
 971     GC_active_count++;
 972     my_first_nonempty = GC_first_nonempty;
 973     GC_ASSERT(GC_first_nonempty >= GC_mark_stack &&
 974               GC_first_nonempty <= GC_mark_stack_top + 1);
 975 #   ifdef PRINTSTATS
 976         GC_printf1("Starting mark helper %lu\n", (unsigned long)id);
 977 #   endif
 978     GC_release_mark_lock();
 979     for (;;) {
 980         size_t n_on_stack;
 981         size_t n_to_get;
 982         mse *next;
 983         mse * my_top;
 984         mse * local_top;
 985         mse * global_first_nonempty = GC_first_nonempty;
 986
 987         GC_ASSERT(my_first_nonempty >= GC_mark_stack &&
 988                   my_first_nonempty <= GC_mark_stack_top + 1);
 989         GC_ASSERT(global_first_nonempty >= GC_mark_stack &&
 990                   global_first_nonempty <= GC_mark_stack_top + 1);
 991         if (my_first_nonempty < global_first_nonempty) {
 992             my_first_nonempty = global_first_nonempty;
 993         } else if (global_first_nonempty < my_first_nonempty) {
 994             GC_compare_and_exchange((word *)(&GC_first_nonempty),
 995                                    (word) global_first_nonempty,
 996                                    (word) my_first_nonempty);
 997             /* If this fails, we just go ahead, without updating        */
 998             /* GC_first_nonempty.                                       */
 999         }
1000         /* Perhaps we should also update GC_first_nonempty, if it */
1001         /* is less.  But that would require using atomic updates. */
1002         my_top = GC_mark_stack_top;
1003         n_on_stack = my_top - my_first_nonempty + 1;
1004         if (0 == n_on_stack) {
1005             GC_acquire_mark_lock();
1006             my_top = GC_mark_stack_top;
1007             n_on_stack = my_top - my_first_nonempty + 1;
1008             if (0 == n_on_stack) {
1009                 GC_active_count--;
1010                 GC_ASSERT(GC_active_count <= GC_helper_count);
1011                 /* Other markers may redeposit objects  */
1012                 /* on the stack.                                */
1013                 if (0 == GC_active_count) GC_notify_all_marker();
1014                 while (GC_active_count > 0
1015                        && GC_first_nonempty > GC_mark_stack_top) {
1016                     /* We will be notified if either GC_active_count    */
1017                     /* reaches zero, or if more objects are pushed on   */
1018                     /* the global mark stack.                           */
1019                     GC_wait_marker();
1020                 }
1021                 if (GC_active_count == 0 &&
1022                     GC_first_nonempty > GC_mark_stack_top) {
1023                     GC_bool need_to_notify = FALSE;
1024                     /* The above conditions can't be falsified while we */
1025                     /* hold the mark lock, since neither                */
1026                     /* GC_active_count nor GC_mark_stack_top can        */
1027                     /* change.  GC_first_nonempty can only be           */
1028                     /* incremented asynchronously.  Thus we know that   */
1029                     /* both conditions actually held simultaneously.    */
1030                     GC_helper_count--;
1031                     if (0 == GC_helper_count) need_to_notify = TRUE;
1032 #                   ifdef PRINTSTATS
1033                       GC_printf1(
1034                         "Finished mark helper %lu\n", (unsigned long)id);
1035 #                   endif
1036                     GC_release_mark_lock();
1037                     if (need_to_notify) GC_notify_all_marker();
1038                     return;
1039                 }
1040                 /* else there's something on the stack again, or        */
1041                 /* another helper may push something.                   */
1042                 GC_active_count++;
1043                 GC_ASSERT(GC_active_count > 0);
1044                 GC_release_mark_lock();
1045                 continue;
1046             } else {
1047                 GC_release_mark_lock();
1048             }
1049         }
1050         n_to_get = ENTRIES_TO_GET;
1051         if (n_on_stack < 2 * ENTRIES_TO_GET) n_to_get = 1;
1052         local_top = GC_steal_mark_stack(my_first_nonempty, my_top,
1053                                         local_mark_stack, n_to_get,
1054                                         &my_first_nonempty);
1055         GC_ASSERT(my_first_nonempty >= GC_mark_stack &&
1056                   my_first_nonempty <= GC_mark_stack_top + 1);
1057         GC_do_local_mark(local_mark_stack, local_top);
1058     }
1059 }
1060
1061 /* Perform Parallel mark.                       */
1062 /* We hold the GC lock, not the mark lock.      */
1063 /* Currently runs until the mark stack is       */
1064 /* empty.                                       */
1065 void GC_do_parallel_mark()
1066 {
1067     mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
1068     mse * local_top;
1069     mse * my_top;
1070
1071     GC_acquire_mark_lock();
1072     GC_ASSERT(I_HOLD_LOCK());
1073     /* This could be a GC_ASSERT, but it seems safer to keep it on      */
1074     /* all the time, especially since it's cheap.                       */
1075     if (GC_help_wanted || GC_active_count != 0 || GC_helper_count != 0)
1076         ABORT("Tried to start parallel mark in bad state");
1077 #   ifdef PRINTSTATS
1078         GC_printf1("Starting marking for mark phase number %lu\n",
1079                    (unsigned long)GC_mark_no);
1080 #   endif
1081     GC_first_nonempty = GC_mark_stack;
1082     GC_active_count = 0;
1083     GC_helper_count = 1;
1084     GC_help_wanted = TRUE;
1085     GC_release_mark_lock();
1086     GC_notify_all_marker();
1087         /* Wake up potential helpers.   */
1088     GC_mark_local(local_mark_stack, 0);
1089     GC_acquire_mark_lock();
1090     GC_help_wanted = FALSE;
1091     /* Done; clean up.  */
1092     while (GC_helper_count > 0) GC_wait_marker();
1093     /* GC_helper_count cannot be incremented while GC_help_wanted == FALSE */
1094 #   ifdef PRINTSTATS
1095         GC_printf1(
1096             "Finished marking for mark phase number %lu\n",
1097             (unsigned long)GC_mark_no);
1098 #   endif
1099     GC_mark_no++;
1100     GC_release_mark_lock();
1101     GC_notify_all_marker();
1102 }
1103
1104
1105 /* Try to help out the marker, if it's running.         */
1106 /* We do not hold the GC lock, but the requestor does.  */
1107 void GC_help_marker(word my_mark_no)
1108 {
1109     mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
1110     unsigned my_id;
1111     mse * my_first_nonempty;
1112
1113     if (!GC_parallel) return;
1114     GC_acquire_mark_lock();
1115     while (GC_mark_no < my_mark_no
1116            || !GC_help_wanted && GC_mark_no == my_mark_no) {
1117       GC_wait_marker();
1118     }
1119     my_id = GC_helper_count;
1120     if (GC_mark_no != my_mark_no || my_id >= GC_markers) {
1121       /* Second test is useful only if original threads can also        */
1122       /* act as helpers.  Under Linux they can't.                       */
1123       GC_release_mark_lock();
1124       return;
1125     }
1126     GC_helper_count = my_id + 1;
1127     GC_release_mark_lock();
1128     GC_mark_local(local_mark_stack, my_id);
1129     /* GC_mark_local decrements GC_helper_count. */
1130 }
1131
1132 #endif /* PARALLEL_MARK */
1133
1134 /* Allocate or reallocate space for mark stack of size s words  */
1135 /* May silently fail.                                           */
1136 static void alloc_mark_stack(n)
1137 word n;
1138 {
1139     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct GC_ms_entry));
1140
1141     GC_mark_stack_too_small = FALSE;
1142     if (GC_mark_stack_size != 0) {
1143         if (new_stack != 0) {
1144           word displ = (word)GC_mark_stack & (GC_page_size - 1);
1145           signed_word size = GC_mark_stack_size * sizeof(struct GC_ms_entry);
1146
1147           /* Recycle old space */
1148               if (0 != displ) displ = GC_page_size - displ;
1149               size = (size - displ) & ~(GC_page_size - 1);
1150               if (size > 0) {
1151                 GC_add_to_heap((struct hblk *)
1152                                 ((word)GC_mark_stack + displ), (word)size);
1153               }
1154           GC_mark_stack = new_stack;
1155           GC_mark_stack_size = n;
1156           GC_mark_stack_limit = new_stack + n;
1157 #         ifdef CONDPRINT
1158             if (GC_print_stats) {
1159               GC_printf1("Grew mark stack to %lu frames\n",
1160                          (unsigned long) GC_mark_stack_size);
1161             }
1162 #         endif
1163         } else {
1164 #         ifdef CONDPRINT
1165             if (GC_print_stats) {
1166               GC_printf1("Failed to grow mark stack to %lu frames\n",
1167                          (unsigned long) n);
1168             }
1169 #         endif
1170         }
1171     } else {
1172         if (new_stack == 0) {
1173             GC_err_printf0("No space for mark stack\n");
1174             EXIT();
1175         }
1176         GC_mark_stack = new_stack;
1177         GC_mark_stack_size = n;
1178         GC_mark_stack_limit = new_stack + n;
1179     }
1180     GC_mark_stack_top = GC_mark_stack-1;
1181 }
1182
1183 void GC_mark_init()
1184 {
1185     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
1186 }
1187
1188 /*
1189  * Push all locations between b and t onto the mark stack.
1190  * b is the first location to be checked. t is one past the last
1191  * location to be checked.
1192  * Should only be used if there is no possibility of mark stack
1193  * overflow.
1194  */
1195 void GC_push_all(bottom, top)
1196 ptr_t bottom;
1197 ptr_t top;
1198 {
1199     register word length;
1200
1201     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1202     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
1203     if (top == 0 || bottom == top) return;
1204     GC_mark_stack_top++;
1205     if (GC_mark_stack_top >= GC_mark_stack_limit) {
1206         ABORT("unexpected mark stack overflow");
1207     }
1208     length = top - bottom;
1209 #   if GC_DS_TAGS > ALIGNMENT - 1
1210         length += GC_DS_TAGS;
1211         length &= ~GC_DS_TAGS;
1212 #   endif
1213     GC_mark_stack_top -> mse_start = (word *)bottom;
1214     GC_mark_stack_top -> mse_descr = length;
1215 }
1216
1217 /*
1218  * Analogous to the above, but push only those pages h with dirty_fn(h) != 0.
1219  * We use push_fn to actually push the block.
1220  * Used both to selectively push dirty pages, or to push a block
1221  * in piecemeal fashion, to allow for more marking concurrency.
1222  * Will not overflow mark stack if push_fn pushes a small fixed number
1223  * of entries.  (This is invoked only if push_fn pushes a single entry,
1224  * or if it marks each object before pushing it, thus ensuring progress
1225  * in the event of a stack overflow.)
1226  */
1227 void GC_push_selected(bottom, top, dirty_fn, push_fn)
1228 ptr_t bottom;
1229 ptr_t top;
1230 int (*dirty_fn) GC_PROTO((struct hblk * h));
1231 void (*push_fn) GC_PROTO((ptr_t bottom, ptr_t top));
1232 {
1233     register struct hblk * h;
1234
1235     bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1236     top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
1237
1238     if (top == 0 || bottom == top) return;
1239     h = HBLKPTR(bottom + HBLKSIZE);
1240     if (top <= (ptr_t) h) {
1241         if ((*dirty_fn)(h-1)) {
1242             (*push_fn)(bottom, top);
1243         }
1244         return;
1245     }
1246     if ((*dirty_fn)(h-1)) {
1247         (*push_fn)(bottom, (ptr_t)h);
1248     }
1249     while ((ptr_t)(h+1) <= top) {
1250         if ((*dirty_fn)(h)) {
1251             if ((word)(GC_mark_stack_top - GC_mark_stack)
1252                 > 3 * GC_mark_stack_size / 4) {
1253                 /* Danger of mark stack overflow */
1254                 (*push_fn)((ptr_t)h, top);
1255                 return;
1256             } else {
1257                 (*push_fn)((ptr_t)h, (ptr_t)(h+1));
1258             }
1259         }
1260         h++;
1261     }
1262     if ((ptr_t)h != top) {
1263         if ((*dirty_fn)(h)) {
1264             (*push_fn)((ptr_t)h, top);
1265         }
1266     }
1267     if (GC_mark_stack_top >= GC_mark_stack_limit) {
1268         ABORT("unexpected mark stack overflow");
1269     }
1270 }
1271
1272 # ifndef SMALL_CONFIG
1273
1274 #ifdef PARALLEL_MARK
1275     /* Break up root sections into page size chunks to better spread    */
1276     /* out work.                                                        */
1277     GC_bool GC_true_func(struct hblk *h) { return TRUE; }
1278 #   define GC_PUSH_ALL(b,t) GC_push_selected(b,t,GC_true_func,GC_push_all);
1279 #else
1280 #   define GC_PUSH_ALL(b,t) GC_push_all(b,t);
1281 #endif
1282
1283
1284 void GC_push_conditional(bottom, top, all)
1285 ptr_t bottom;
1286 ptr_t top;
1287 int all;
1288 {
1289     if (all) {
1290       if (GC_dirty_maintained) {
1291 #       ifdef PROC_VDB
1292             /* Pages that were never dirtied cannot contain pointers    */
1293             GC_push_selected(bottom, top, GC_page_was_ever_dirty, GC_push_all);
1294 #       else
1295             GC_push_all(bottom, top);
1296 #       endif
1297       } else {
1298         GC_push_all(bottom, top);
1299       }
1300     } else {
1301         GC_push_selected(bottom, top, GC_page_was_dirty, GC_push_all);
1302     }
1303 }
1304 #endif
1305
1306 # if defined(MSWIN32) || defined(MSWINCE)
1307   void __cdecl GC_push_one(p)
1308 # else
1309   void GC_push_one(p)
1310 # endif
1311 word p;
1312 {
1313     GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
1314 }
1315
1316 struct GC_ms_entry *GC_mark_and_push(obj, mark_stack_ptr, mark_stack_limit, src)
1317 GC_PTR obj;
1318 struct GC_ms_entry * mark_stack_ptr;
1319 struct GC_ms_entry * mark_stack_limit;
1320 GC_PTR *src;
1321 {
1322    PREFETCH(obj);
1323    PUSH_CONTENTS(obj, mark_stack_ptr /* modified */, mark_stack_limit, src,
1324                  was_marked /* internally generated exit label */);
1325    return mark_stack_ptr;
1326 }
1327
1328 # ifdef __STDC__
1329 #   define BASE(p) (word)GC_base((void *)(p))
1330 # else
1331 #   define BASE(p) (word)GC_base((char *)(p))
1332 # endif
1333
1334 /* Mark and push (i.e. gray) a single object p onto the main    */
1335 /* mark stack.  Consider p to be valid if it is an interior     */
1336 /* pointer.                                                     */
1337 /* The object p has passed a preliminary pointer validity       */
1338 /* test, but we do not definitely know whether it is valid.     */
1339 /* Mark bits are NOT atomically updated.  Thus this must be the */
1340 /* only thread setting them.                                    */
1341 # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
1342     void GC_mark_and_push_stack(p, source)
1343     ptr_t source;
1344 # else
1345     void GC_mark_and_push_stack(p)
1346 #   define source 0
1347 # endif
1348 register word p;
1349 {
1350     register word r;
1351     register hdr * hhdr;
1352     register int displ;
1353
1354     GET_HDR(p, hhdr);
1355     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
1356         if (hhdr != 0) {
1357           r = BASE(p);
1358           hhdr = HDR(r);
1359           displ = BYTES_TO_WORDS(HBLKDISPL(r));
1360         }
1361     } else {
1362         register map_entry_type map_entry;
1363
1364         displ = HBLKDISPL(p);
1365         map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
1366         if (map_entry >= MAX_OFFSET) {
1367           if (map_entry == OFFSET_TOO_BIG || !GC_all_interior_pointers) {
1368               r = BASE(p);
1369               displ = BYTES_TO_WORDS(HBLKDISPL(r));
1370               if (r == 0) hhdr = 0;
1371           } else {
1372               /* Offset invalid, but map reflects interior pointers     */
1373               hhdr = 0;
1374           }
1375         } else {
1376           displ = BYTES_TO_WORDS(displ);
1377           displ -= map_entry;
1378           r = (word)((word *)(HBLKPTR(p)) + displ);
1379         }
1380     }
1381     /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
1382     /* displ is the word index within the block.                 */
1383     if (hhdr == 0) {
1384 #       ifdef PRINT_BLACK_LIST
1385           GC_add_to_black_list_stack(p, source);
1386 #       else
1387           GC_add_to_black_list_stack(p);
1388 #       endif
1389 #       undef source  /* In case we had to define it. */
1390     } else {
1391         if (!mark_bit_from_hdr(hhdr, displ)) {
1392             set_mark_bit_from_hdr(hhdr, displ);
1393             GC_STORE_BACK_PTR(source, (ptr_t)r);
1394             PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
1395                      GC_mark_stack_limit);
1396         }
1397     }
1398 }
1399
1400 # ifdef TRACE_BUF
1401
1402 # define TRACE_ENTRIES 1000
1403
1404 struct trace_entry {
1405     char * kind;
1406     word gc_no;
1407     word words_allocd;
1408     word arg1;
1409     word arg2;
1410 } GC_trace_buf[TRACE_ENTRIES];
1411
1412 int GC_trace_buf_ptr = 0;
1413
1414 void GC_add_trace_entry(char *kind, word arg1, word arg2)
1415 {
1416     GC_trace_buf[GC_trace_buf_ptr].kind = kind;
1417     GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
1418     GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
1419     GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
1420     GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
1421     GC_trace_buf_ptr++;
1422     if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
1423 }
1424
1425 void GC_print_trace(word gc_no, GC_bool lock)
1426 {
1427     int i;
1428     struct trace_entry *p;
1429
1430     if (lock) LOCK();
1431     for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
1432         if (i < 0) i = TRACE_ENTRIES-1;
1433         p = GC_trace_buf + i;
1434         if (p -> gc_no < gc_no || p -> kind == 0) return;
1435         printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
1436                 p -> kind, p -> gc_no, p -> words_allocd,
1437                 (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
1438     }
1439     printf("Trace incomplete\n");
1440     if (lock) UNLOCK();
1441 }
1442
1443 # endif /* TRACE_BUF */
1444
1445 /*
1446  * A version of GC_push_all that treats all interior pointers as valid
1447  * and scans the entire region immediately, in case the contents
1448  * change.
1449  */
1450 void GC_push_all_eager(bottom, top)
1451 ptr_t bottom;
1452 ptr_t top;
1453 {
1454     word * b = (word *)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1455     word * t = (word *)(((word) top) & ~(ALIGNMENT-1));
1456     register word *p;
1457     register word q;
1458     register word *lim;
1459     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1460     register ptr_t least_ha = GC_least_plausible_heap_addr;
1461 #   define GC_greatest_plausible_heap_addr greatest_ha
1462 #   define GC_least_plausible_heap_addr least_ha
1463
1464     if (top == 0) return;
1465     /* check all pointers in range and push if they appear      */
1466     /* to be valid.                                             */
1467       lim = t - 1 /* longword */;
1468       for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
1469         q = *p;
1470         GC_PUSH_ONE_STACK(q, p);
1471       }
1472 #   undef GC_greatest_plausible_heap_addr
1473 #   undef GC_least_plausible_heap_addr
1474 }
1475
1476 #ifndef THREADS
1477 /*
1478  * A version of GC_push_all that treats all interior pointers as valid
1479  * and scans part of the area immediately, to make sure that saved
1480  * register values are not lost.
1481  * Cold_gc_frame delimits the stack section that must be scanned
1482  * eagerly.  A zero value indicates that no eager scanning is needed.
1483  */
1484 void GC_push_all_stack_partially_eager(bottom, top, cold_gc_frame)
1485 ptr_t bottom;
1486 ptr_t top;
1487 ptr_t cold_gc_frame;
1488 {
1489   if (!NEED_FIXUP_POINTER && GC_all_interior_pointers) {
1490     /* Push the hot end of the stack eagerly, so that register values   */
1491     /* saved inside GC frames are marked before they disappear.         */
1492     /* The rest of the marking can be deferred until later.             */
1493     if (0 == cold_gc_frame) {
1494         GC_push_all_stack(bottom, top);
1495         return;
1496     }
1497     GC_ASSERT(bottom <= cold_gc_frame && cold_gc_frame <= top);
1498 #   ifdef STACK_GROWS_DOWN
1499         GC_push_all(cold_gc_frame - sizeof(ptr_t), top);
1500         GC_push_all_eager(bottom, cold_gc_frame);
1501 #   else /* STACK_GROWS_UP */
1502         GC_push_all(bottom, cold_gc_frame + sizeof(ptr_t));
1503         GC_push_all_eager(cold_gc_frame, top);
1504 #   endif /* STACK_GROWS_UP */
1505   } else {
1506     GC_push_all_eager(bottom, top);
1507   }
1508 # ifdef TRACE_BUF
1509       GC_add_trace_entry("GC_push_all_stack", bottom, top);
1510 # endif
1511 }
1512 #endif /* !THREADS */
1513
1514 void GC_push_all_stack(bottom, top)
1515 ptr_t bottom;
1516 ptr_t top;
1517 {
1518   if (!NEED_FIXUP_POINTER && GC_all_interior_pointers) {
1519     GC_push_all(bottom, top);
1520   } else {
1521     GC_push_all_eager(bottom, top);
1522   }
1523 }
1524
1525 #if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1526 /* Push all objects reachable from marked objects in the given block */
1527 /* of size 1 objects.                                                */
1528 void GC_push_marked1(h, hhdr)
1529 struct hblk *h;
1530 register hdr * hhdr;
1531 {
1532     word * mark_word_addr = &(hhdr->hb_marks[0]);
1533     register word *p;
1534     word *plim;
1535     register int i;
1536     register word q;
1537     register word mark_word;
1538     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1539     register ptr_t least_ha = GC_least_plausible_heap_addr;
1540     register mse * mark_stack_top = GC_mark_stack_top;
1541     register mse * mark_stack_limit = GC_mark_stack_limit;
1542 #   define GC_mark_stack_top mark_stack_top
1543 #   define GC_mark_stack_limit mark_stack_limit
1544 #   define GC_greatest_plausible_heap_addr greatest_ha
1545 #   define GC_least_plausible_heap_addr least_ha
1546
1547     p = (word *)(h->hb_body);
1548     plim = (word *)(((word)h) + HBLKSIZE);
1549
1550     /* go through all words in block */
1551         while( p < plim )  {
1552             mark_word = *mark_word_addr++;
1553             i = 0;
1554             while(mark_word != 0) {
1555               if (mark_word & 1) {
1556                   q = p[i];
1557                   GC_PUSH_ONE_HEAP(q, p + i);
1558               }
1559               i++;
1560               mark_word >>= 1;
1561             }
1562             p += WORDSZ;
1563         }
1564 #   undef GC_greatest_plausible_heap_addr
1565 #   undef GC_least_plausible_heap_addr
1566 #   undef GC_mark_stack_top
1567 #   undef GC_mark_stack_limit
1568     GC_mark_stack_top = mark_stack_top;
1569 }
1570
1571
1572 #ifndef UNALIGNED
1573
1574 /* Push all objects reachable from marked objects in the given block */
1575 /* of size 2 objects.                                                */
1576 void GC_push_marked2(h, hhdr)
1577 struct hblk *h;
1578 register hdr * hhdr;
1579 {
1580     word * mark_word_addr = &(hhdr->hb_marks[0]);
1581     register word *p;
1582     word *plim;
1583     register int i;
1584     register word q;
1585     register word mark_word;
1586     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1587     register ptr_t least_ha = GC_least_plausible_heap_addr;
1588     register mse * mark_stack_top = GC_mark_stack_top;
1589     register mse * mark_stack_limit = GC_mark_stack_limit;
1590 #   define GC_mark_stack_top mark_stack_top
1591 #   define GC_mark_stack_limit mark_stack_limit
1592 #   define GC_greatest_plausible_heap_addr greatest_ha
1593 #   define GC_least_plausible_heap_addr least_ha
1594
1595     p = (word *)(h->hb_body);
1596     plim = (word *)(((word)h) + HBLKSIZE);
1597
1598     /* go through all words in block */
1599         while( p < plim )  {
1600             mark_word = *mark_word_addr++;
1601             i = 0;
1602             while(mark_word != 0) {
1603               if (mark_word & 1) {
1604                   q = p[i];
1605                   GC_PUSH_ONE_HEAP(q, p + i);
1606                   q = p[i+1];
1607                   GC_PUSH_ONE_HEAP(q, p + i);
1608               }
1609               i += 2;
1610               mark_word >>= 2;
1611             }
1612             p += WORDSZ;
1613         }
1614 #   undef GC_greatest_plausible_heap_addr
1615 #   undef GC_least_plausible_heap_addr
1616 #   undef GC_mark_stack_top
1617 #   undef GC_mark_stack_limit
1618     GC_mark_stack_top = mark_stack_top;
1619 }
1620
1621 /* Push all objects reachable from marked objects in the given block */
1622 /* of size 4 objects.                                                */
1623 /* There is a risk of mark stack overflow here.  But we handle that. */
1624 /* And only unmarked objects get pushed, so it's not very likely.    */
1625 void GC_push_marked4(h, hhdr)
1626 struct hblk *h;
1627 register hdr * hhdr;
1628 {
1629     word * mark_word_addr = &(hhdr->hb_marks[0]);
1630     register word *p;
1631     word *plim;
1632     register int i;
1633     register word q;
1634     register word mark_word;
1635     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
1636     register ptr_t least_ha = GC_least_plausible_heap_addr;
1637     register mse * mark_stack_top = GC_mark_stack_top;
1638     register mse * mark_stack_limit = GC_mark_stack_limit;
1639 #   define GC_mark_stack_top mark_stack_top
1640 #   define GC_mark_stack_limit mark_stack_limit
1641 #   define GC_greatest_plausible_heap_addr greatest_ha
1642 #   define GC_least_plausible_heap_addr least_ha
1643
1644     p = (word *)(h->hb_body);
1645     plim = (word *)(((word)h) + HBLKSIZE);
1646
1647     /* go through all words in block */
1648         while( p < plim )  {
1649             mark_word = *mark_word_addr++;
1650             i = 0;
1651             while(mark_word != 0) {
1652               if (mark_word & 1) {
1653                   q = p[i];
1654                   GC_PUSH_ONE_HEAP(q, p + i);
1655                   q = p[i+1];
1656                   GC_PUSH_ONE_HEAP(q, p + i + 1);
1657                   q = p[i+2];
1658                   GC_PUSH_ONE_HEAP(q, p + i + 2);
1659                   q = p[i+3];
1660                   GC_PUSH_ONE_HEAP(q, p + i + 3);
1661               }
1662               i += 4;
1663               mark_word >>= 4;
1664             }
1665             p += WORDSZ;
1666         }
1667 #   undef GC_greatest_plausible_heap_addr
1668 #   undef GC_least_plausible_heap_addr
1669 #   undef GC_mark_stack_top
1670 #   undef GC_mark_stack_limit
1671     GC_mark_stack_top = mark_stack_top;
1672 }
1673
1674 #endif /* UNALIGNED */
1675
1676 #endif /* SMALL_CONFIG */
1677
1678 /* Push all objects reachable from marked objects in the given block */
1679 void GC_push_marked(h, hhdr)
1680 struct hblk *h;
1681 register hdr * hhdr;
1682 {
1683     register int sz = hhdr -> hb_sz;
1684     register int descr = hhdr -> hb_descr;
1685     register word * p;
1686     register int word_no;
1687     register word * lim;
1688     register mse * GC_mark_stack_top_reg;
1689     register mse * mark_stack_limit = GC_mark_stack_limit;
1690
1691     /* Some quick shortcuts: */
1692         if ((0 | GC_DS_LENGTH) == descr) return;
1693         if (GC_block_empty(hhdr)/* nothing marked */) return;
1694     GC_n_rescuing_pages++;
1695     GC_objects_are_marked = TRUE;
1696     if (sz > MAXOBJSZ) {
1697         lim = (word *)h;
1698     } else {
1699         lim = (word *)(h + 1) - sz;
1700     }
1701
1702     switch(sz) {
1703 #   if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES)
1704      case 1:
1705        GC_push_marked1(h, hhdr);
1706        break;
1707 #   endif
1708 #   if !defined(SMALL_CONFIG) && !defined(UNALIGNED) && \
1709        !defined(USE_MARK_BYTES)
1710      case 2:
1711        GC_push_marked2(h, hhdr);
1712        break;
1713      case 4:
1714        GC_push_marked4(h, hhdr);
1715        break;
1716 #   endif
1717      default:
1718       GC_mark_stack_top_reg = GC_mark_stack_top;
1719       for (p = (word *)h, word_no = 0; p <= lim; p += sz, word_no += sz) {
1720          if (mark_bit_from_hdr(hhdr, word_no)) {
1721            /* Mark from fields inside the object */
1722              PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
1723 #            ifdef GATHERSTATS
1724                 /* Subtract this object from total, since it was        */
1725                 /* added in twice.                                      */
1726                 GC_composite_in_use -= sz;
1727 #            endif
1728          }
1729       }
1730       GC_mark_stack_top = GC_mark_stack_top_reg;
1731     }
1732 }
1733
1734 #ifndef SMALL_CONFIG
1735 /* Test whether any page in the given block is dirty    */
1736 GC_bool GC_block_was_dirty(h, hhdr)
1737 struct hblk *h;
1738 register hdr * hhdr;
1739 {
1740     register int sz = hhdr -> hb_sz;
1741
1742     if (sz <= MAXOBJSZ) {
1743          return(GC_page_was_dirty(h));
1744     } else {
1745          register ptr_t p = (ptr_t)h;
1746          sz = WORDS_TO_BYTES(sz);
1747          while (p < (ptr_t)h + sz) {
1748              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1749              p += HBLKSIZE;
1750          }
1751          return(FALSE);
1752     }
1753 }
1754 #endif /* SMALL_CONFIG */
1755
1756 /* Similar to GC_push_next_marked, but return address of next block     */
1757 struct hblk * GC_push_next_marked(h)
1758 struct hblk *h;
1759 {
1760     register hdr * hhdr;
1761
1762     h = GC_next_used_block(h);
1763     if (h == 0) return(0);
1764     hhdr = HDR(h);
1765     GC_push_marked(h, hhdr);
1766     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1767 }
1768
1769 #ifndef SMALL_CONFIG
1770 /* Identical to above, but mark only from dirty pages   */
1771 struct hblk * GC_push_next_marked_dirty(h)
1772 struct hblk *h;
1773 {
1774     register hdr * hhdr;
1775
1776     if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
1777     for (;;) {
1778         h = GC_next_used_block(h);
1779         if (h == 0) return(0);
1780         hhdr = HDR(h);
1781 #       ifdef STUBBORN_ALLOC
1782           if (hhdr -> hb_obj_kind == STUBBORN) {
1783             if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
1784                 break;
1785             }
1786           } else {
1787             if (GC_block_was_dirty(h, hhdr)) break;
1788           }
1789 #       else
1790           if (GC_block_was_dirty(h, hhdr)) break;
1791 #       endif
1792         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1793     }
1794     GC_push_marked(h, hhdr);
1795     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1796 }
1797 #endif
1798
1799 /* Similar to above, but for uncollectable pages.  Needed since we      */
1800 /* do not clear marks for such pages, even for full collections.        */
1801 struct hblk * GC_push_next_marked_uncollectable(h)
1802 struct hblk *h;
1803 {
1804     register hdr * hhdr = HDR(h);
1805
1806     for (;;) {
1807         h = GC_next_used_block(h);
1808         if (h == 0) return(0);
1809         hhdr = HDR(h);
1810         if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
1811         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1812     }
1813     GC_push_marked(h, hhdr);
1814     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1815 }
1816
1817