mark.c

   1 /*
   2  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
   3  * Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved.
   4  * Copyright (c) 2000 by Hewlett-Packard Company.  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 #if defined(__MINGW32__) && !defined(__MINGW_EXCPT_DEFINE_PSDK) \
  18     && defined(__i386__) /* cannot use macros from gcconfig.h */
  19   /* Otherwise EXCEPTION_REGISTRATION type declaration from winnt.h     */
  20   /* might be used.  That declaration has "handler" callback with NTAPI */
  21   /* attribute.  The proper type (with "handler" field compatible with  */
  22   /* GC mark_ex_handler) is declared in excpt.h.  The given macro is    */
  23   /* defined before any system header include.                          */
  24 # define __MINGW_EXCPT_DEFINE_PSDK 1
  25 #endif
  26
  27 #include "private/gc_pmark.h"
  28
  29 #include <stdio.h>
  30
  31 #if defined(MSWIN32) && defined(__GNUC__)
  32 # include <excpt.h>
  33 #endif
  34
  35 /* Make arguments appear live to compiler.  Put here to minimize the    */
  36 /* risk of inlining.  Used to minimize junk left in registers.          */
  37 GC_ATTR_NOINLINE
  38 void GC_noop6(word arg1 GC_ATTR_UNUSED, word arg2 GC_ATTR_UNUSED,
  39               word arg3 GC_ATTR_UNUSED, word arg4 GC_ATTR_UNUSED,
  40               word arg5 GC_ATTR_UNUSED, word arg6 GC_ATTR_UNUSED)
  41 {
  42   /* Avoid GC_noop6 calls to be optimized away. */
  43 # if defined(AO_HAVE_compiler_barrier) && !defined(BASE_ATOMIC_OPS_EMULATED)
  44     AO_compiler_barrier(); /* to serve as a special side-effect */
  45 # else
  46     GC_noop1(0);
  47 # endif
  48 }
  49
  50 volatile word GC_noop_sink;
  51
  52 /* Single argument version, robust against whole program analysis. */
  53 GC_ATTR_NO_SANITIZE_THREAD
  54 GC_API void GC_CALL GC_noop1(word x)
  55 {
  56     GC_noop_sink = x;
  57 }
  58
  59 /* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */
  60
  61 GC_INNER unsigned GC_n_mark_procs = GC_RESERVED_MARK_PROCS;
  62
  63 /* Initialize GC_obj_kinds properly and standard free lists properly.   */
  64 /* This must be done statically since they may be accessed before       */
  65 /* GC_init is called.                                                   */
  66 /* It's done here, since we need to deal with mark descriptors.         */
  67 GC_INNER struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
  68 /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,
  69                 /* 0 | */ GC_DS_LENGTH, FALSE, FALSE
  70                 /*, */ OK_DISCLAIM_INITZ },
  71 /* NORMAL */  { &GC_objfreelist[0], 0,
  72                 /* 0 | */ GC_DS_LENGTH,
  73                                 /* adjusted in GC_init for EXTRA_BYTES  */
  74                 TRUE /* add length to descr */, TRUE
  75                 /*, */ OK_DISCLAIM_INITZ },
  76 /* UNCOLLECTABLE */
  77               { &GC_uobjfreelist[0], 0,
  78                 /* 0 | */ GC_DS_LENGTH, TRUE /* add length to descr */, TRUE
  79                 /*, */ OK_DISCLAIM_INITZ },
  80 # ifdef GC_ATOMIC_UNCOLLECTABLE
  81               { &GC_auobjfreelist[0], 0,
  82                 /* 0 | */ GC_DS_LENGTH, FALSE /* add length to descr */, FALSE
  83                 /*, */ OK_DISCLAIM_INITZ },
  84 # endif
  85 };
  86
  87 GC_INNER unsigned GC_n_kinds = GC_N_KINDS_INITIAL_VALUE;
  88
  89 # ifndef INITIAL_MARK_STACK_SIZE
  90 #   define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
  91                 /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a    */
  92                 /* multiple of HBLKSIZE.                                */
  93                 /* The incremental collector actually likes a larger    */
  94                 /* size, since it wants to push all marked dirty        */
  95                 /* objects before marking anything new.  Currently we   */
  96                 /* let it grow dynamically.                             */
  97 # endif
  98
  99 #if !defined(GC_DISABLE_INCREMENTAL)
 100   STATIC word GC_n_rescuing_pages = 0;
 101                                 /* Number of dirty pages we marked from */
 102                                 /* excludes ptrfree pages, etc.         */
 103                                 /* Used for logging only.               */
 104 #endif
 105
 106 GC_INNER size_t GC_mark_stack_size = 0;
 107
 108 #ifdef PARALLEL_MARK
 109   STATIC volatile AO_t GC_first_nonempty = 0;
 110         /* Lowest entry on mark stack   */
 111         /* that may be nonempty.        */
 112         /* Updated only by initiating   */
 113         /* thread.                      */
 114
 115   GC_INNER GC_bool GC_parallel_mark_disabled = FALSE;
 116 #endif
 117
 118 GC_INNER mark_state_t GC_mark_state = MS_NONE;
 119
 120 GC_INNER GC_bool GC_mark_stack_too_small = FALSE;
 121
 122 static struct hblk * scan_ptr;
 123
 124 STATIC GC_bool GC_objects_are_marked = FALSE;
 125                 /* Are there collectible marked objects in the heap?    */
 126
 127 /* Is a collection in progress?  Note that this can return true in the  */
 128 /* non-incremental case, if a collection has been abandoned and the     */
 129 /* mark state is now MS_INVALID.                                        */
 130 GC_INNER GC_bool GC_collection_in_progress(void)
 131 {
 132     return(GC_mark_state != MS_NONE);
 133 }
 134
 135 /* Clear all mark bits in the header.   */
 136 GC_INNER void GC_clear_hdr_marks(hdr *hhdr)
 137 {
 138   size_t last_bit;
 139
 140 # ifdef AO_HAVE_load
 141     /* Atomic access is used to avoid racing with GC_realloc.   */
 142     last_bit = FINAL_MARK_BIT((size_t)AO_load((volatile AO_t *)&hhdr->hb_sz));
 143 # else
 144     /* No race as GC_realloc holds the lock while updating hb_sz.   */
 145     last_bit = FINAL_MARK_BIT((size_t)hhdr->hb_sz);
 146 # endif
 147
 148     BZERO(hhdr -> hb_marks, sizeof(hhdr->hb_marks));
 149     set_mark_bit_from_hdr(hhdr, last_bit);
 150     hhdr -> hb_n_marks = 0;
 151 }
 152
 153 /* Set all mark bits in the header.  Used for uncollectible blocks. */
 154 GC_INNER void GC_set_hdr_marks(hdr *hhdr)
 155 {
 156     unsigned i;
 157     size_t sz = (size_t)hhdr->hb_sz;
 158     unsigned n_marks = (unsigned)FINAL_MARK_BIT(sz);
 159
 160 #   ifdef USE_MARK_BYTES
 161       for (i = 0; i <= n_marks; i += (unsigned)MARK_BIT_OFFSET(sz)) {
 162         hhdr -> hb_marks[i] = 1;
 163       }
 164 #   else
 165       for (i = 0; i < divWORDSZ(n_marks + WORDSZ); ++i) {
 166         hhdr -> hb_marks[i] = GC_WORD_MAX;
 167       }
 168 #   endif
 169 #   ifdef MARK_BIT_PER_OBJ
 170       hhdr -> hb_n_marks = n_marks;
 171 #   else
 172       hhdr -> hb_n_marks = HBLK_OBJS(sz);
 173 #   endif
 174 }
 175
 176 /* Clear all mark bits associated with block h. */
 177 static void clear_marks_for_block(struct hblk *h, word dummy GC_ATTR_UNUSED)
 178 {
 179     hdr * hhdr = HDR(h);
 180
 181     if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;
 182         /* Mark bit for these is cleared only once the object is        */
 183         /* explicitly deallocated.  This either frees the block, or     */
 184         /* the bit is cleared once the object is on the free list.      */
 185     GC_clear_hdr_marks(hhdr);
 186 }
 187
 188 /* Slow but general routines for setting/clearing/asking about mark bits. */
 189 GC_API void GC_CALL GC_set_mark_bit(const void *p)
 190 {
 191     struct hblk *h = HBLKPTR(p);
 192     hdr * hhdr = HDR(h);
 193     word bit_no = MARK_BIT_NO((ptr_t)p - (ptr_t)h, hhdr -> hb_sz);
 194
 195     if (!mark_bit_from_hdr(hhdr, bit_no)) {
 196       set_mark_bit_from_hdr(hhdr, bit_no);
 197       ++hhdr -> hb_n_marks;
 198     }
 199 }
 200
 201 GC_API void GC_CALL GC_clear_mark_bit(const void *p)
 202 {
 203     struct hblk *h = HBLKPTR(p);
 204     hdr * hhdr = HDR(h);
 205     word bit_no = MARK_BIT_NO((ptr_t)p - (ptr_t)h, hhdr -> hb_sz);
 206
 207     if (mark_bit_from_hdr(hhdr, bit_no)) {
 208       size_t n_marks = hhdr -> hb_n_marks;
 209
 210       GC_ASSERT(n_marks != 0);
 211       clear_mark_bit_from_hdr(hhdr, bit_no);
 212       n_marks--;
 213 #     ifdef PARALLEL_MARK
 214         if (n_marks != 0 || !GC_parallel)
 215           hhdr -> hb_n_marks = n_marks;
 216         /* Don't decrement to zero.  The counts are approximate due to  */
 217         /* concurrency issues, but we need to ensure that a count of    */
 218         /* zero implies an empty block.                                 */
 219 #     else
 220           hhdr -> hb_n_marks = n_marks;
 221 #     endif
 222     }
 223 }
 224
 225 GC_API int GC_CALL GC_is_marked(const void *p)
 226 {
 227     struct hblk *h = HBLKPTR(p);
 228     hdr * hhdr = HDR(h);
 229     word bit_no = MARK_BIT_NO((ptr_t)p - (ptr_t)h, hhdr -> hb_sz);
 230
 231     return (int)mark_bit_from_hdr(hhdr, bit_no); /* 0 or 1 */
 232 }
 233
 234 /* Clear mark bits in all allocated heap blocks.  This invalidates the  */
 235 /* marker invariant, and sets GC_mark_state to reflect this.  (This     */
 236 /* implicitly starts marking to reestablish the invariant.)             */
 237 GC_INNER void GC_clear_marks(void)
 238 {
 239     GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
 240     GC_objects_are_marked = FALSE;
 241     GC_mark_state = MS_INVALID;
 242     scan_ptr = 0;
 243 }
 244
 245 /* Initiate a garbage collection.  Initiates a full collection if the   */
 246 /* mark state is invalid.                                               */
 247 GC_INNER void GC_initiate_gc(void)
 248 {
 249     GC_ASSERT(I_HOLD_LOCK());
 250 #   ifndef GC_DISABLE_INCREMENTAL
 251         if (GC_incremental) {
 252 #         ifdef CHECKSUMS
 253             GC_read_dirty(FALSE);
 254             GC_check_dirty();
 255 #         else
 256             GC_read_dirty(GC_mark_state == MS_INVALID);
 257 #         endif
 258         }
 259         GC_n_rescuing_pages = 0;
 260 #   endif
 261     if (GC_mark_state == MS_NONE) {
 262         GC_mark_state = MS_PUSH_RESCUERS;
 263     } else if (GC_mark_state != MS_INVALID) {
 264         ABORT("Unexpected state");
 265     } /* Else this is really a full collection, and mark bits are invalid. */
 266     scan_ptr = 0;
 267 }
 268
 269 #ifdef PARALLEL_MARK
 270     STATIC void GC_do_parallel_mark(void); /* Initiate parallel marking. */
 271 #endif /* PARALLEL_MARK */
 272
 273 #ifdef GC_DISABLE_INCREMENTAL
 274 # define GC_push_next_marked_dirty(h) GC_push_next_marked(h)
 275 #else
 276   STATIC struct hblk * GC_push_next_marked_dirty(struct hblk *h);
 277                 /* Invoke GC_push_marked on next dirty block above h.   */
 278                 /* Return a pointer just past the end of this block.    */
 279 #endif /* !GC_DISABLE_INCREMENTAL */
 280 STATIC struct hblk * GC_push_next_marked(struct hblk *h);
 281                 /* Ditto, but also mark from clean pages.       */
 282 STATIC struct hblk * GC_push_next_marked_uncollectable(struct hblk *h);
 283                 /* Ditto, but mark only from uncollectible pages.       */
 284
 285 static void alloc_mark_stack(size_t);
 286
 287 /* Perform a small amount of marking.                   */
 288 /* We try to touch roughly a page of memory.            */
 289 /* Return TRUE if we just finished a mark phase.        */
 290 /* Cold_gc_frame is an address inside a GC frame that   */
 291 /* remains valid until all marking is complete.         */
 292 /* A zero value indicates that it's OK to miss some     */
 293 /* register values.                                     */
 294 /* We hold the allocation lock.  In the case of         */
 295 /* incremental collection, the world may not be stopped.*/
 296 #ifdef WRAP_MARK_SOME
 297   /* For win32, this is called after we establish a structured  */
 298   /* exception handler, in case Windows unmaps one of our root  */
 299   /* segments.  See below.  In either case, we acquire the      */
 300   /* allocator lock long before we get here.                    */
 301   STATIC GC_bool GC_mark_some_inner(ptr_t cold_gc_frame)
 302 #else
 303   GC_INNER GC_bool GC_mark_some(ptr_t cold_gc_frame)
 304 #endif
 305 {
 306     switch(GC_mark_state) {
 307         case MS_NONE:
 308             break;
 309
 310         case MS_PUSH_RESCUERS:
 311             if ((word)GC_mark_stack_top
 312                 >= (word)(GC_mark_stack_limit - INITIAL_MARK_STACK_SIZE/2)) {
 313                 /* Go ahead and mark, even though that might cause us to */
 314                 /* see more marked dirty objects later on.  Avoid this   */
 315                 /* in the future.                                        */
 316                 GC_mark_stack_too_small = TRUE;
 317                 MARK_FROM_MARK_STACK();
 318                 break;
 319             } else {
 320                 scan_ptr = GC_push_next_marked_dirty(scan_ptr);
 321                 if (scan_ptr == 0) {
 322 #                 if !defined(GC_DISABLE_INCREMENTAL)
 323                     GC_COND_LOG_PRINTF("Marked from %lu dirty pages\n",
 324                                        (unsigned long)GC_n_rescuing_pages);
 325 #                 endif
 326                     GC_push_roots(FALSE, cold_gc_frame);
 327                     GC_objects_are_marked = TRUE;
 328                     if (GC_mark_state != MS_INVALID) {
 329                         GC_mark_state = MS_ROOTS_PUSHED;
 330                     }
 331                 }
 332             }
 333             break;
 334
 335         case MS_PUSH_UNCOLLECTABLE:
 336             if ((word)GC_mark_stack_top
 337                 >= (word)(GC_mark_stack + GC_mark_stack_size/4)) {
 338 #               ifdef PARALLEL_MARK
 339                   /* Avoid this, since we don't parallelize the marker  */
 340                   /* here.                                              */
 341                   if (GC_parallel) GC_mark_stack_too_small = TRUE;
 342 #               endif
 343                 MARK_FROM_MARK_STACK();
 344                 break;
 345             } else {
 346                 scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
 347                 if (scan_ptr == 0) {
 348                     GC_push_roots(TRUE, cold_gc_frame);
 349                     GC_objects_are_marked = TRUE;
 350                     if (GC_mark_state != MS_INVALID) {
 351                         GC_mark_state = MS_ROOTS_PUSHED;
 352                     }
 353                 }
 354             }
 355             break;
 356
 357         case MS_ROOTS_PUSHED:
 358 #           ifdef PARALLEL_MARK
 359               /* Eventually, incremental marking should run             */
 360               /* asynchronously in multiple threads, without grabbing   */
 361               /* the allocation lock.                                   */
 362               /* For now, parallel marker is disabled if there is       */
 363               /* a chance that marking could be interrupted by          */
 364               /* a client-supplied time limit or custom stop function.  */
 365                 if (GC_parallel && !GC_parallel_mark_disabled) {
 366                   GC_do_parallel_mark();
 367                   GC_ASSERT((word)GC_mark_stack_top < (word)GC_first_nonempty);
 368                   GC_mark_stack_top = GC_mark_stack - 1;
 369                   if (GC_mark_stack_too_small) {
 370                     alloc_mark_stack(2*GC_mark_stack_size);
 371                   }
 372                   if (GC_mark_state == MS_ROOTS_PUSHED) {
 373                     GC_mark_state = MS_NONE;
 374                     return(TRUE);
 375                   }
 376                   break;
 377                 }
 378 #           endif
 379             if ((word)GC_mark_stack_top >= (word)GC_mark_stack) {
 380                 MARK_FROM_MARK_STACK();
 381                 break;
 382             } else {
 383                 GC_mark_state = MS_NONE;
 384                 if (GC_mark_stack_too_small) {
 385                     alloc_mark_stack(2*GC_mark_stack_size);
 386                 }
 387                 return(TRUE);
 388             }
 389
 390         case MS_INVALID:
 391         case MS_PARTIALLY_INVALID:
 392             if (!GC_objects_are_marked) {
 393                 GC_mark_state = MS_PUSH_UNCOLLECTABLE;
 394                 break;
 395             }
 396             if ((word)GC_mark_stack_top >= (word)GC_mark_stack) {
 397                 MARK_FROM_MARK_STACK();
 398                 break;
 399             }
 400             if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {
 401                 /* About to start a heap scan for marked objects. */
 402                 /* Mark stack is empty.  OK to reallocate.        */
 403                 if (GC_mark_stack_too_small) {
 404                     alloc_mark_stack(2*GC_mark_stack_size);
 405                 }
 406                 GC_mark_state = MS_PARTIALLY_INVALID;
 407             }
 408             scan_ptr = GC_push_next_marked(scan_ptr);
 409             if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
 410                 GC_push_roots(TRUE, cold_gc_frame);
 411                 GC_objects_are_marked = TRUE;
 412                 if (GC_mark_state != MS_INVALID) {
 413                     GC_mark_state = MS_ROOTS_PUSHED;
 414                 }
 415             }
 416             break;
 417
 418         default:
 419             ABORT("GC_mark_some: bad state");
 420     }
 421     return(FALSE);
 422 }
 423
 424 #ifdef WRAP_MARK_SOME
 425
 426 # if (defined(MSWIN32) || defined(MSWINCE)) && defined(__GNUC__)
 427
 428     typedef struct {
 429       EXCEPTION_REGISTRATION ex_reg;
 430       void *alt_path;
 431     } ext_ex_regn;
 432
 433     static EXCEPTION_DISPOSITION mark_ex_handler(
 434         struct _EXCEPTION_RECORD *ex_rec,
 435         void *est_frame,
 436         struct _CONTEXT *context,
 437         void *disp_ctxt GC_ATTR_UNUSED)
 438     {
 439         if (ex_rec->ExceptionCode == STATUS_ACCESS_VIOLATION) {
 440           ext_ex_regn *xer = (ext_ex_regn *)est_frame;
 441
 442           /* Unwind from the inner function assuming the standard */
 443           /* function prologue.                                   */
 444           /* Assumes code has not been compiled with              */
 445           /* -fomit-frame-pointer.                                */
 446           context->Esp = context->Ebp;
 447           context->Ebp = *((DWORD *)context->Esp);
 448           context->Esp = context->Esp - 8;
 449
 450           /* Resume execution at the "real" handler within the    */
 451           /* wrapper function.                                    */
 452           context->Eip = (DWORD )(xer->alt_path);
 453
 454           return ExceptionContinueExecution;
 455
 456         } else {
 457             return ExceptionContinueSearch;
 458         }
 459     }
 460 # endif /* __GNUC__ && MSWIN32 */
 461
 462   GC_INNER GC_bool GC_mark_some(ptr_t cold_gc_frame)
 463   {
 464       GC_bool ret_val;
 465
 466 #   if defined(MSWIN32) || defined(MSWINCE)
 467 #    ifndef __GNUC__
 468       /* Windows 98 appears to asynchronously create and remove  */
 469       /* writable memory mappings, for reasons we haven't yet    */
 470       /* understood.  Since we look for writable regions to      */
 471       /* determine the root set, we may try to mark from an      */
 472       /* address range that disappeared since we started the     */
 473       /* collection.  Thus we have to recover from faults here.  */
 474       /* This code does not appear to be necessary for Windows   */
 475       /* 95/NT/2000+. Note that this code should never generate  */
 476       /* an incremental GC write fault.                          */
 477       /* This code seems to be necessary for WinCE (at least in  */
 478       /* the case we'd decide to add MEM_PRIVATE sections to     */
 479       /* data roots in GC_register_dynamic_libraries()).         */
 480       /* It's conceivable that this is the same issue with       */
 481       /* terminating threads that we see with Linux and          */
 482       /* USE_PROC_FOR_LIBRARIES.                                 */
 483
 484       __try {
 485           ret_val = GC_mark_some_inner(cold_gc_frame);
 486       } __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
 487                 EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {
 488           goto handle_ex;
 489       }
 490 #     if defined(GC_WIN32_THREADS) && !defined(GC_PTHREADS)
 491         /* With DllMain-based thread tracking, a thread may have        */
 492         /* started while we were marking.  This is logically equivalent */
 493         /* to the exception case; our results are invalid and we have   */
 494         /* to start over.  This cannot be prevented since we can't      */
 495         /* block in DllMain.                                            */
 496         if (GC_started_thread_while_stopped())
 497           goto handle_thr_start;
 498 #     endif
 499      rm_handler:
 500       return ret_val;
 501
 502 #    else /* __GNUC__ */
 503
 504       /* Manually install an exception handler since GCC does    */
 505       /* not yet support Structured Exception Handling (SEH) on  */
 506       /* Win32.                                                  */
 507
 508       ext_ex_regn er;
 509
 510 #     if GC_GNUC_PREREQ(4, 7) || GC_CLANG_PREREQ(3, 3)
 511 #       pragma GCC diagnostic push
 512         /* Suppress "taking the address of label is non-standard" warning. */
 513 #       if defined(__clang__) || GC_GNUC_PREREQ(6, 4)
 514 #         pragma GCC diagnostic ignored "-Wpedantic"
 515 #       else
 516           /* GCC before ~4.8 does not accept "-Wpedantic" quietly.  */
 517 #         pragma GCC diagnostic ignored "-pedantic"
 518 #       endif
 519         er.alt_path = &&handle_ex;
 520 #       pragma GCC diagnostic pop
 521 #     elif !defined(CPPCHECK) /* pragma diagnostic is not supported */
 522         er.alt_path = &&handle_ex;
 523 #     endif
 524       er.ex_reg.handler = mark_ex_handler;
 525       __asm__ __volatile__ ("movl %%fs:0, %0" : "=r" (er.ex_reg.prev));
 526       __asm__ __volatile__ ("movl %0, %%fs:0" : : "r" (&er));
 527       ret_val = GC_mark_some_inner(cold_gc_frame);
 528       /* Prevent GCC from considering the following code unreachable */
 529       /* and thus eliminating it.                                    */
 530         if (er.alt_path == 0)
 531           goto handle_ex;
 532 #     if defined(GC_WIN32_THREADS) && !defined(GC_PTHREADS)
 533         if (GC_started_thread_while_stopped())
 534           goto handle_thr_start;
 535 #     endif
 536     rm_handler:
 537       /* Uninstall the exception handler.       */
 538       __asm__ __volatile__ ("mov %0, %%fs:0" : : "r" (er.ex_reg.prev));
 539       return ret_val;
 540
 541 #    endif /* __GNUC__ */
 542 #   else /* !MSWIN32 */
 543       /* Here we are handling the case in which /proc is used for root  */
 544       /* finding, and we have threads.  We may find a stack for a       */
 545       /* thread that is in the process of exiting, and disappears       */
 546       /* while we are marking it.  This seems extremely difficult to    */
 547       /* avoid otherwise.                                               */
 548 #     ifndef DEFAULT_VDB
 549         if (GC_auto_incremental) {
 550           WARN("Incremental GC incompatible with /proc roots\n", 0);
 551           /* I'm not sure if this could still work ...  */
 552         }
 553 #     endif
 554       GC_setup_temporary_fault_handler();
 555       if(SETJMP(GC_jmp_buf) != 0) goto handle_ex;
 556       ret_val = GC_mark_some_inner(cold_gc_frame);
 557     rm_handler:
 558       GC_reset_fault_handler();
 559       return ret_val;
 560
 561 #   endif /* !MSWIN32 */
 562
 563 handle_ex:
 564     /* Exception handler starts here for all cases. */
 565       {
 566         static word warned_gc_no;
 567
 568         /* Warn about it at most once per collection. */
 569         if (warned_gc_no != GC_gc_no) {
 570           WARN("Caught ACCESS_VIOLATION in marker;"
 571                " memory mapping disappeared\n", 0);
 572           warned_gc_no = GC_gc_no;
 573         }
 574       }
 575 #   if (defined(MSWIN32) || defined(MSWINCE)) && defined(GC_WIN32_THREADS) \
 576        && !defined(GC_PTHREADS)
 577       handle_thr_start:
 578 #   endif
 579       /* We have bad roots on the stack.  Discard mark stack.   */
 580       /* Rescan from marked objects.  Redetermine roots.        */
 581 #     ifdef REGISTER_LIBRARIES_EARLY
 582         START_WORLD();
 583         GC_cond_register_dynamic_libraries();
 584         STOP_WORLD();
 585 #     endif
 586       GC_invalidate_mark_state();
 587       scan_ptr = 0;
 588
 589       ret_val = FALSE;
 590       goto rm_handler;  /* Back to platform-specific code. */
 591   }
 592 #endif /* WRAP_MARK_SOME */
 593
 594 GC_INNER void GC_invalidate_mark_state(void)
 595 {
 596     GC_mark_state = MS_INVALID;
 597     GC_mark_stack_top = GC_mark_stack-1;
 598 }
 599
 600 GC_INNER mse * GC_signal_mark_stack_overflow(mse *msp)
 601 {
 602     GC_mark_state = MS_INVALID;
 603 #   ifdef PARALLEL_MARK
 604       /* We are using a local_mark_stack in parallel mode, so   */
 605       /* do not signal the global mark stack to be resized.     */
 606       /* That will be done if required in GC_return_mark_stack. */
 607       if (!GC_parallel)
 608         GC_mark_stack_too_small = TRUE;
 609 #   else
 610       GC_mark_stack_too_small = TRUE;
 611 #   endif
 612     GC_COND_LOG_PRINTF("Mark stack overflow; current size = %lu entries\n",
 613                        (unsigned long)GC_mark_stack_size);
 614     return(msp - GC_MARK_STACK_DISCARDS);
 615 }
 616
 617 /*
 618  * Mark objects pointed to by the regions described by
 619  * mark stack entries between mark_stack and mark_stack_top,
 620  * inclusive.  Assumes the upper limit of a mark stack entry
 621  * is never 0.  A mark stack entry never has size 0.
 622  * We try to traverse on the order of a hblk of memory before we return.
 623  * Caller is responsible for calling this until the mark stack is empty.
 624  * Note that this is the most performance critical routine in the
 625  * collector.  Hence it contains all sorts of ugly hacks to speed
 626  * things up.  In particular, we avoid procedure calls on the common
 627  * path, we take advantage of peculiarities of the mark descriptor
 628  * encoding, we optionally maintain a cache for the block address to
 629  * header mapping, we prefetch when an object is "grayed", etc.
 630  */
 631 GC_ATTR_NO_SANITIZE_ADDR GC_ATTR_NO_SANITIZE_MEMORY GC_ATTR_NO_SANITIZE_THREAD
 632 GC_INNER mse * GC_mark_from(mse *mark_stack_top, mse *mark_stack,
 633                             mse *mark_stack_limit)
 634 {
 635   signed_word credit = HBLKSIZE;  /* Remaining credit for marking work. */
 636   ptr_t current_p;      /* Pointer to current candidate ptr.            */
 637   word current;         /* Candidate pointer.                           */
 638   ptr_t limit = 0;      /* (Incl) limit of current candidate range.     */
 639   word descr;
 640   ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
 641   ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
 642   DECLARE_HDR_CACHE;
 643
 644 # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.          */
 645
 646   GC_objects_are_marked = TRUE;
 647   INIT_HDR_CACHE;
 648 # ifdef OS2 /* Use untweaked version to circumvent compiler problem.    */
 649     while ((word)mark_stack_top >= (word)mark_stack && credit >= 0)
 650 # else
 651     while (((((word)mark_stack_top - (word)mark_stack) | (word)credit)
 652             & SIGNB) == 0)
 653 # endif
 654   {
 655     current_p = mark_stack_top -> mse_start;
 656     descr = mark_stack_top -> mse_descr.w;
 657   retry:
 658     /* current_p and descr describe the current object.                 */
 659     /* (*mark_stack_top) is vacant.                                     */
 660     /* The following is 0 only for small objects described by a simple  */
 661     /* length descriptor.  For many applications this is the common     */
 662     /* case, so we try to detect it quickly.                            */
 663     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | GC_DS_TAGS)) {
 664       word tag = descr & GC_DS_TAGS;
 665
 666       GC_STATIC_ASSERT(GC_DS_TAGS == 0x3);
 667       switch(tag) {
 668         case GC_DS_LENGTH:
 669           /* Large length.                                              */
 670           /* Process part of the range to avoid pushing too much on the */
 671           /* stack.                                                     */
 672           GC_ASSERT(descr < (word)GC_greatest_plausible_heap_addr
 673                             - (word)GC_least_plausible_heap_addr
 674                 || (word)(current_p + descr)
 675                             <= (word)GC_least_plausible_heap_addr
 676                 || (word)current_p >= (word)GC_greatest_plausible_heap_addr);
 677 #         ifdef PARALLEL_MARK
 678 #           define SHARE_BYTES 2048
 679             if (descr > SHARE_BYTES && GC_parallel
 680                 && (word)mark_stack_top < (word)(mark_stack_limit - 1)) {
 681               word new_size = (descr/2) & ~(word)(sizeof(word)-1);
 682
 683               mark_stack_top -> mse_start = current_p;
 684               mark_stack_top -> mse_descr.w = new_size + sizeof(word);
 685                                         /* Makes sure we handle         */
 686                                         /* misaligned pointers.         */
 687               mark_stack_top++;
 688 #             ifdef ENABLE_TRACE
 689                 if ((word)GC_trace_addr >= (word)current_p
 690                     && (word)GC_trace_addr < (word)(current_p + descr)) {
 691                   GC_log_printf("GC #%u: large section; start %p, len %lu,"
 692                                 " splitting (parallel) at %p\n",
 693                                 (unsigned)GC_gc_no, (void *)current_p,
 694                                 (unsigned long)descr,
 695                                 (void *)(current_p + new_size));
 696                 }
 697 #             endif
 698               current_p += new_size;
 699               descr -= new_size;
 700               goto retry;
 701             }
 702 #         endif /* PARALLEL_MARK */
 703           mark_stack_top -> mse_start =
 704                 limit = current_p + WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
 705           mark_stack_top -> mse_descr.w =
 706                                 descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
 707 #         ifdef ENABLE_TRACE
 708             if ((word)GC_trace_addr >= (word)current_p
 709                 && (word)GC_trace_addr < (word)(current_p + descr)) {
 710               GC_log_printf("GC #%u: large section; start %p, len %lu,"
 711                             " splitting at %p\n",
 712                             (unsigned)GC_gc_no, (void *)current_p,
 713                             (unsigned long)descr, (void *)limit);
 714             }
 715 #         endif
 716           /* Make sure that pointers overlapping the two ranges are     */
 717           /* considered.                                                */
 718           limit += sizeof(word) - ALIGNMENT;
 719           break;
 720         case GC_DS_BITMAP:
 721           mark_stack_top--;
 722 #         ifdef ENABLE_TRACE
 723             if ((word)GC_trace_addr >= (word)current_p
 724                 && (word)GC_trace_addr < (word)(current_p
 725                                                 + WORDS_TO_BYTES(WORDSZ-2))) {
 726               GC_log_printf("GC #%u: tracing from %p bitmap descr %lu\n",
 727                             (unsigned)GC_gc_no, (void *)current_p,
 728                             (unsigned long)descr);
 729             }
 730 #         endif /* ENABLE_TRACE */
 731           descr &= ~GC_DS_TAGS;
 732           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
 733           while (descr != 0) {
 734             if ((descr & SIGNB) != 0) {
 735               current = *(word *)current_p;
 736               FIXUP_POINTER(current);
 737               if (current >= (word)least_ha && current < (word)greatest_ha) {
 738                 PREFETCH((ptr_t)current);
 739 #               ifdef ENABLE_TRACE
 740                   if (GC_trace_addr == current_p) {
 741                     GC_log_printf("GC #%u: considering(3) %p -> %p\n",
 742                                   (unsigned)GC_gc_no, (void *)current_p,
 743                                   (void *)current);
 744                   }
 745 #               endif /* ENABLE_TRACE */
 746                 PUSH_CONTENTS((ptr_t)current, mark_stack_top,
 747                               mark_stack_limit, current_p);
 748               }
 749             }
 750             descr <<= 1;
 751             current_p += sizeof(word);
 752           }
 753           continue;
 754         case GC_DS_PROC:
 755           mark_stack_top--;
 756 #         ifdef ENABLE_TRACE
 757             if ((word)GC_trace_addr >= (word)current_p
 758                 && GC_base(current_p) != 0
 759                 && GC_base(current_p) == GC_base(GC_trace_addr)) {
 760               GC_log_printf("GC #%u: tracing from %p, proc descr %lu\n",
 761                             (unsigned)GC_gc_no, (void *)current_p,
 762                             (unsigned long)descr);
 763             }
 764 #         endif /* ENABLE_TRACE */
 765           credit -= GC_PROC_BYTES;
 766           mark_stack_top = (*PROC(descr))((word *)current_p, mark_stack_top,
 767                                           mark_stack_limit, ENV(descr));
 768           continue;
 769         case GC_DS_PER_OBJECT:
 770           if ((signed_word)descr >= 0) {
 771             /* Descriptor is in the object.     */
 772             descr = *(word *)(current_p + descr - GC_DS_PER_OBJECT);
 773           } else {
 774             /* Descriptor is in type descriptor pointed to by first     */
 775             /* word in object.                                          */
 776             ptr_t type_descr = *(ptr_t *)current_p;
 777             /* type_descr is either a valid pointer to the descriptor   */
 778             /* structure, or this object was on a free list.            */
 779             /* If it was anything but the last object on the free list, */
 780             /* we will misinterpret the next object on the free list as */
 781             /* the type descriptor, and get a 0 GC descriptor, which    */
 782             /* is ideal.  Unfortunately, we need to check for the last  */
 783             /* object case explicitly.                                  */
 784             if (EXPECT(0 == type_descr, FALSE)) {
 785                 mark_stack_top--;
 786                 continue;
 787             }
 788             descr = *(word *)(type_descr
 789                               - ((signed_word)descr + (GC_INDIR_PER_OBJ_BIAS
 790                                                        - GC_DS_PER_OBJECT)));
 791           }
 792           if (0 == descr) {
 793               /* Can happen either because we generated a 0 descriptor  */
 794               /* or we saw a pointer to a free object.                  */
 795               mark_stack_top--;
 796               continue;
 797           }
 798           goto retry;
 799       }
 800     } else {
 801       /* Small object with length descriptor.   */
 802       mark_stack_top--;
 803 #     ifndef SMALL_CONFIG
 804         if (descr < sizeof(word))
 805           continue;
 806 #     endif
 807 #     ifdef ENABLE_TRACE
 808         if ((word)GC_trace_addr >= (word)current_p
 809             && (word)GC_trace_addr < (word)(current_p + descr)) {
 810           GC_log_printf("GC #%u: small object; start %p, len %lu\n",
 811                         (unsigned)GC_gc_no, (void *)current_p,
 812                         (unsigned long)descr);
 813         }
 814 #     endif
 815       limit = current_p + (word)descr;
 816     }
 817     /* The simple case in which we're scanning a range. */
 818     GC_ASSERT(!((word)current_p & (ALIGNMENT-1)));
 819     credit -= limit - current_p;
 820     limit -= sizeof(word);
 821     {
 822 #     define PREF_DIST 4
 823
 824 #     ifndef SMALL_CONFIG
 825         word deferred;
 826
 827         /* Try to prefetch the next pointer to be examined ASAP.        */
 828         /* Empirically, this also seems to help slightly without        */
 829         /* prefetches, at least on linux/X86.  Presumably this loop     */
 830         /* ends up with less register pressure, and gcc thus ends up    */
 831         /* generating slightly better code.  Overall gcc code quality   */
 832         /* for this loop is still not great.                            */
 833         for(;;) {
 834           PREFETCH(limit - PREF_DIST*CACHE_LINE_SIZE);
 835           GC_ASSERT((word)limit >= (word)current_p);
 836           deferred = *(word *)limit;
 837           FIXUP_POINTER(deferred);
 838           limit -= ALIGNMENT;
 839           if (deferred >= (word)least_ha && deferred < (word)greatest_ha) {
 840             PREFETCH((ptr_t)deferred);
 841             break;
 842           }
 843           if ((word)current_p > (word)limit) goto next_object;
 844           /* Unroll once, so we don't do too many of the prefetches     */
 845           /* based on limit.                                            */
 846           deferred = *(word *)limit;
 847           FIXUP_POINTER(deferred);
 848           limit -= ALIGNMENT;
 849           if (deferred >= (word)least_ha && deferred < (word)greatest_ha) {
 850             PREFETCH((ptr_t)deferred);
 851             break;
 852           }
 853           if ((word)current_p > (word)limit) goto next_object;
 854         }
 855 #     endif
 856
 857       while ((word)current_p <= (word)limit) {
 858         /* Empirically, unrolling this loop doesn't help a lot. */
 859         /* Since PUSH_CONTENTS expands to a lot of code,        */
 860         /* we don't.                                            */
 861         current = *(word *)current_p;
 862         FIXUP_POINTER(current);
 863         PREFETCH(current_p + PREF_DIST*CACHE_LINE_SIZE);
 864         if (current >= (word)least_ha && current < (word)greatest_ha) {
 865           /* Prefetch the contents of the object we just pushed.  It's  */
 866           /* likely we will need them soon.                             */
 867           PREFETCH((ptr_t)current);
 868 #         ifdef ENABLE_TRACE
 869             if (GC_trace_addr == current_p) {
 870               GC_log_printf("GC #%u: considering(1) %p -> %p\n",
 871                             (unsigned)GC_gc_no, (void *)current_p,
 872                             (void *)current);
 873             }
 874 #         endif /* ENABLE_TRACE */
 875           PUSH_CONTENTS((ptr_t)current, mark_stack_top,
 876                         mark_stack_limit, current_p);
 877         }
 878         current_p += ALIGNMENT;
 879       }
 880
 881 #     ifndef SMALL_CONFIG
 882         /* We still need to mark the entry we previously prefetched.    */
 883         /* We already know that it passes the preliminary pointer       */
 884         /* validity test.                                               */
 885 #       ifdef ENABLE_TRACE
 886             if (GC_trace_addr == current_p) {
 887               GC_log_printf("GC #%u: considering(2) %p -> %p\n",
 888                             (unsigned)GC_gc_no, (void *)current_p,
 889                             (void *)deferred);
 890             }
 891 #       endif /* ENABLE_TRACE */
 892         PUSH_CONTENTS((ptr_t)deferred, mark_stack_top,
 893                       mark_stack_limit, current_p);
 894         next_object:;
 895 #     endif
 896     }
 897   }
 898   return mark_stack_top;
 899 }
 900
 901 #ifdef PARALLEL_MARK
 902
 903 STATIC GC_bool GC_help_wanted = FALSE;  /* Protected by mark lock.      */
 904 STATIC unsigned GC_helper_count = 0;    /* Number of running helpers.   */
 905                                         /* Protected by mark lock.      */
 906 STATIC unsigned GC_active_count = 0;    /* Number of active helpers.    */
 907                                         /* Protected by mark lock.      */
 908                                         /* May increase and decrease    */
 909                                         /* within each mark cycle.  But */
 910                                         /* once it returns to 0, it     */
 911                                         /* stays zero for the cycle.    */
 912
 913 GC_INNER word GC_mark_no = 0;
 914
 915 static mse *main_local_mark_stack;
 916
 917 #ifdef LINT2
 918 # define LOCAL_MARK_STACK_SIZE (HBLKSIZE / 8)
 919 #else
 920 # define LOCAL_MARK_STACK_SIZE HBLKSIZE
 921         /* Under normal circumstances, this is big enough to guarantee  */
 922         /* we don't overflow half of it in a single call to             */
 923         /* GC_mark_from.                                                */
 924 #endif
 925
 926 /* Wait all markers to finish initialization (i.e. store        */
 927 /* marker_[b]sp, marker_mach_threads, GC_marker_Id).            */
 928 GC_INNER void GC_wait_for_markers_init(void)
 929 {
 930   signed_word count;
 931
 932   if (GC_markers_m1 == 0)
 933     return;
 934
 935   /* Allocate the local mark stack for the thread that holds GC lock.   */
 936 # ifndef CAN_HANDLE_FORK
 937     GC_ASSERT(NULL == main_local_mark_stack);
 938 # else
 939     if (NULL == main_local_mark_stack)
 940 # endif
 941   {
 942     size_t bytes_to_get =
 943                 ROUNDUP_PAGESIZE_IF_MMAP(LOCAL_MARK_STACK_SIZE * sizeof(mse));
 944     main_local_mark_stack = (mse *)GET_MEM(bytes_to_get);
 945     if (NULL == main_local_mark_stack)
 946       ABORT("Insufficient memory for main local_mark_stack");
 947     GC_add_to_our_memory((ptr_t)main_local_mark_stack, bytes_to_get);
 948   }
 949
 950   /* Reuse marker lock and builders count to synchronize        */
 951   /* marker threads startup.                                    */
 952   GC_acquire_mark_lock();
 953   GC_fl_builder_count += GC_markers_m1;
 954   count = GC_fl_builder_count;
 955   GC_release_mark_lock();
 956   if (count != 0) {
 957     GC_ASSERT(count > 0);
 958     GC_wait_for_reclaim();
 959   }
 960 }
 961
 962 /* Steal mark stack entries starting at mse low into mark stack local   */
 963 /* until we either steal mse high, or we have max entries.              */
 964 /* Return a pointer to the top of the local mark stack.                 */
 965 /* (*next) is replaced by a pointer to the next unscanned mark stack    */
 966 /* entry.                                                               */
 967 STATIC mse * GC_steal_mark_stack(mse * low, mse * high, mse * local,
 968                                  unsigned max, mse **next)
 969 {
 970     mse *p;
 971     mse *top = local - 1;
 972     unsigned i = 0;
 973
 974     GC_ASSERT((word)high >= (word)(low - 1)
 975               && (word)(high - low + 1) <= GC_mark_stack_size);
 976     for (p = low; (word)p <= (word)high && i <= max; ++p) {
 977         word descr = (word)AO_load(&p->mse_descr.ao);
 978         if (descr != 0) {
 979             /* Must be ordered after read of descr: */
 980             AO_store_release_write(&p->mse_descr.ao, 0);
 981             /* More than one thread may get this entry, but that's only */
 982             /* a minor performance problem.                             */
 983             ++top;
 984             top -> mse_descr.w = descr;
 985             top -> mse_start = p -> mse_start;
 986             GC_ASSERT((descr & GC_DS_TAGS) != GC_DS_LENGTH
 987                       || descr < (word)GC_greatest_plausible_heap_addr
 988                                         - (word)GC_least_plausible_heap_addr
 989                       || (word)(p->mse_start + descr)
 990                             <= (word)GC_least_plausible_heap_addr
 991                       || (word)p->mse_start
 992                             >= (word)GC_greatest_plausible_heap_addr);
 993             /* If this is a big object, count it as                     */
 994             /* size/256 + 1 objects.                                    */
 995             ++i;
 996             if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) i += (int)(descr >> 8);
 997         }
 998     }
 999     *next = p;
1000     return top;
1001 }
1002
1003 /* Copy back a local mark stack.        */
1004 /* low and high are inclusive bounds.   */
1005 STATIC void GC_return_mark_stack(mse * low, mse * high)
1006 {
1007     mse * my_top;
1008     mse * my_start;
1009     size_t stack_size;
1010
1011     if ((word)high < (word)low) return;
1012     stack_size = high - low + 1;
1013     GC_acquire_mark_lock();
1014     my_top = GC_mark_stack_top; /* Concurrent modification impossible. */
1015     my_start = my_top + 1;
1016     if ((word)(my_start - GC_mark_stack + stack_size)
1017                 > (word)GC_mark_stack_size) {
1018       GC_COND_LOG_PRINTF("No room to copy back mark stack\n");
1019       GC_mark_state = MS_INVALID;
1020       GC_mark_stack_too_small = TRUE;
1021       /* We drop the local mark stack.  We'll fix things later. */
1022     } else {
1023       BCOPY(low, my_start, stack_size * sizeof(mse));
1024       GC_ASSERT((mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top))
1025                 == my_top);
1026       AO_store_release_write((volatile AO_t *)(&GC_mark_stack_top),
1027                              (AO_t)(my_top + stack_size));
1028                 /* Ensures visibility of previously written stack contents. */
1029     }
1030     GC_release_mark_lock();
1031     GC_notify_all_marker();
1032 }
1033
1034 #ifndef N_LOCAL_ITERS
1035 # define N_LOCAL_ITERS 1
1036 #endif
1037
1038 /* This function is only called when the local  */
1039 /* and the main mark stacks are both empty.     */
1040 static GC_bool has_inactive_helpers(void)
1041 {
1042   GC_bool res;
1043
1044   GC_acquire_mark_lock();
1045   res = GC_active_count < GC_helper_count;
1046   GC_release_mark_lock();
1047   return res;
1048 }
1049
1050 /* Mark from the local mark stack.              */
1051 /* On return, the local mark stack is empty.    */
1052 /* But this may be achieved by copying the      */
1053 /* local mark stack back into the global one.   */
1054 /* We do not hold the mark lock.                */
1055 STATIC void GC_do_local_mark(mse *local_mark_stack, mse *local_top)
1056 {
1057     unsigned n;
1058
1059     for (;;) {
1060         for (n = 0; n < N_LOCAL_ITERS; ++n) {
1061             local_top = GC_mark_from(local_top, local_mark_stack,
1062                                      local_mark_stack + LOCAL_MARK_STACK_SIZE);
1063             if ((word)local_top < (word)local_mark_stack) return;
1064             if ((word)(local_top - local_mark_stack)
1065                         >= LOCAL_MARK_STACK_SIZE / 2) {
1066                 GC_return_mark_stack(local_mark_stack, local_top);
1067                 return;
1068             }
1069         }
1070         if ((word)AO_load((volatile AO_t *)&GC_mark_stack_top)
1071             < (word)AO_load(&GC_first_nonempty)
1072             && (word)local_top > (word)(local_mark_stack + 1)
1073             && has_inactive_helpers()) {
1074             /* Try to share the load, since the main stack is empty,    */
1075             /* and helper threads are waiting for a refill.             */
1076             /* The entries near the bottom of the stack are likely      */
1077             /* to require more work.  Thus we return those, even though */
1078             /* it's harder.                                             */
1079             mse * new_bottom = local_mark_stack
1080                                 + (local_top - local_mark_stack)/2;
1081             GC_ASSERT((word)new_bottom > (word)local_mark_stack
1082                       && (word)new_bottom < (word)local_top);
1083             GC_return_mark_stack(local_mark_stack, new_bottom - 1);
1084             memmove(local_mark_stack, new_bottom,
1085                     (local_top - new_bottom + 1) * sizeof(mse));
1086             local_top -= (new_bottom - local_mark_stack);
1087         }
1088     }
1089 }
1090
1091 #ifndef ENTRIES_TO_GET
1092 # define ENTRIES_TO_GET 5
1093 #endif
1094
1095 /* Mark using the local mark stack until the global mark stack is empty */
1096 /* and there are no active workers. Update GC_first_nonempty to reflect */
1097 /* progress.  Caller holds the mark lock.                               */
1098 /* Caller has already incremented GC_helper_count.  We decrement it,    */
1099 /* and maintain GC_active_count.                                        */
1100 STATIC void GC_mark_local(mse *local_mark_stack, int id)
1101 {
1102     mse * my_first_nonempty;
1103
1104     GC_active_count++;
1105     my_first_nonempty = (mse *)AO_load(&GC_first_nonempty);
1106     GC_ASSERT((word)GC_mark_stack <= (word)my_first_nonempty);
1107     GC_ASSERT((word)my_first_nonempty
1108         <= (word)AO_load((volatile AO_t *)&GC_mark_stack_top) + sizeof(mse));
1109     GC_VERBOSE_LOG_PRINTF("Starting mark helper %d\n", id);
1110     GC_release_mark_lock();
1111     for (;;) {
1112         size_t n_on_stack;
1113         unsigned n_to_get;
1114         mse * my_top;
1115         mse * local_top;
1116         mse * global_first_nonempty = (mse *)AO_load(&GC_first_nonempty);
1117
1118         GC_ASSERT((word)my_first_nonempty >= (word)GC_mark_stack &&
1119                   (word)my_first_nonempty <=
1120                         (word)AO_load((volatile AO_t *)&GC_mark_stack_top)
1121                         + sizeof(mse));
1122         GC_ASSERT((word)global_first_nonempty >= (word)GC_mark_stack);
1123         if ((word)my_first_nonempty < (word)global_first_nonempty) {
1124             my_first_nonempty = global_first_nonempty;
1125         } else if ((word)global_first_nonempty < (word)my_first_nonempty) {
1126             (void)AO_compare_and_swap(&GC_first_nonempty,
1127                                       (AO_t)global_first_nonempty,
1128                                       (AO_t)my_first_nonempty);
1129             /* If this fails, we just go ahead, without updating        */
1130             /* GC_first_nonempty.                                       */
1131         }
1132         /* Perhaps we should also update GC_first_nonempty, if it */
1133         /* is less.  But that would require using atomic updates. */
1134         my_top = (mse *)AO_load_acquire((volatile AO_t *)(&GC_mark_stack_top));
1135         if ((word)my_top < (word)my_first_nonempty) {
1136             GC_acquire_mark_lock();
1137             my_top = GC_mark_stack_top;
1138                 /* Asynchronous modification impossible here,   */
1139                 /* since we hold mark lock.                     */
1140             n_on_stack = my_top - my_first_nonempty + 1;
1141             if (0 == n_on_stack) {
1142                 GC_active_count--;
1143                 GC_ASSERT(GC_active_count <= GC_helper_count);
1144                 /* Other markers may redeposit objects          */
1145                 /* on the stack.                                */
1146                 if (0 == GC_active_count) GC_notify_all_marker();
1147                 while (GC_active_count > 0
1148                        && (word)AO_load(&GC_first_nonempty)
1149                                 > (word)GC_mark_stack_top) {
1150                     /* We will be notified if either GC_active_count    */
1151                     /* reaches zero, or if more objects are pushed on   */
1152                     /* the global mark stack.                           */
1153                     GC_wait_marker();
1154                 }
1155                 if (GC_active_count == 0
1156                     && (word)AO_load(&GC_first_nonempty)
1157                         > (word)GC_mark_stack_top) {
1158                     GC_bool need_to_notify = FALSE;
1159                     /* The above conditions can't be falsified while we */
1160                     /* hold the mark lock, since neither                */
1161                     /* GC_active_count nor GC_mark_stack_top can        */
1162                     /* change.  GC_first_nonempty can only be           */
1163                     /* incremented asynchronously.  Thus we know that   */
1164                     /* both conditions actually held simultaneously.    */
1165                     GC_helper_count--;
1166                     if (0 == GC_helper_count) need_to_notify = TRUE;
1167                     GC_VERBOSE_LOG_PRINTF("Finished mark helper %d\n", id);
1168                     if (need_to_notify) GC_notify_all_marker();
1169                     return;
1170                 }
1171                 /* Else there's something on the stack again, or        */
1172                 /* another helper may push something.                   */
1173                 GC_active_count++;
1174                 GC_ASSERT(GC_active_count > 0);
1175                 GC_release_mark_lock();
1176                 continue;
1177             } else {
1178                 GC_release_mark_lock();
1179             }
1180         } else {
1181             n_on_stack = my_top - my_first_nonempty + 1;
1182         }
1183         n_to_get = ENTRIES_TO_GET;
1184         if (n_on_stack < 2 * ENTRIES_TO_GET) n_to_get = 1;
1185         local_top = GC_steal_mark_stack(my_first_nonempty, my_top,
1186                                         local_mark_stack, n_to_get,
1187                                         &my_first_nonempty);
1188         GC_ASSERT((word)my_first_nonempty >= (word)GC_mark_stack &&
1189                   (word)my_first_nonempty <=
1190                         (word)AO_load((volatile AO_t *)&GC_mark_stack_top)
1191                         + sizeof(mse));
1192         GC_do_local_mark(local_mark_stack, local_top);
1193     }
1194 }
1195
1196 /* Perform Parallel mark.                       */
1197 /* We hold the GC lock, not the mark lock.      */
1198 /* Currently runs until the mark stack is       */
1199 /* empty.                                       */
1200 STATIC void GC_do_parallel_mark(void)
1201 {
1202     GC_acquire_mark_lock();
1203     GC_ASSERT(I_HOLD_LOCK());
1204     /* This could be a GC_ASSERT, but it seems safer to keep it on      */
1205     /* all the time, especially since it's cheap.                       */
1206     if (GC_help_wanted || GC_active_count != 0 || GC_helper_count != 0)
1207         ABORT("Tried to start parallel mark in bad state");
1208     GC_VERBOSE_LOG_PRINTF("Starting marking for mark phase number %lu\n",
1209                           (unsigned long)GC_mark_no);
1210     GC_first_nonempty = (AO_t)GC_mark_stack;
1211     GC_active_count = 0;
1212     GC_helper_count = 1;
1213     GC_help_wanted = TRUE;
1214     GC_notify_all_marker();
1215         /* Wake up potential helpers.   */
1216     GC_mark_local(main_local_mark_stack, 0);
1217     GC_help_wanted = FALSE;
1218     /* Done; clean up.  */
1219     while (GC_helper_count > 0) {
1220       GC_wait_marker();
1221     }
1222     /* GC_helper_count cannot be incremented while not GC_help_wanted.  */
1223     GC_VERBOSE_LOG_PRINTF("Finished marking for mark phase number %lu\n",
1224                           (unsigned long)GC_mark_no);
1225     GC_mark_no++;
1226     GC_release_mark_lock();
1227     GC_notify_all_marker();
1228 }
1229
1230
1231 /* Try to help out the marker, if it's running.         */
1232 /* We do not hold the GC lock, but the requestor does.  */
1233 /* And we hold the mark lock.                           */
1234 GC_INNER void GC_help_marker(word my_mark_no)
1235 {
1236 #   define my_id my_id_mse.mse_descr.w
1237     mse my_id_mse;  /* align local_mark_stack explicitly */
1238     mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
1239                 /* Note: local_mark_stack is quite big (up to 128 KiB). */
1240
1241     GC_ASSERT(GC_parallel);
1242     while (GC_mark_no < my_mark_no
1243            || (!GC_help_wanted && GC_mark_no == my_mark_no)) {
1244       GC_wait_marker();
1245     }
1246     my_id = GC_helper_count;
1247     if (GC_mark_no != my_mark_no || my_id > (unsigned)GC_markers_m1) {
1248       /* Second test is useful only if original threads can also        */
1249       /* act as helpers.  Under Linux they can't.                       */
1250       return;
1251     }
1252     GC_helper_count = (unsigned)my_id + 1;
1253     GC_mark_local(local_mark_stack, (int)my_id);
1254     /* GC_mark_local decrements GC_helper_count. */
1255 #   undef my_id
1256 }
1257
1258 #endif /* PARALLEL_MARK */
1259
1260 GC_INNER void GC_scratch_recycle_inner(void *ptr, size_t bytes)
1261 {
1262   if (ptr != NULL) {
1263     size_t page_offset = (word)ptr & (GC_page_size - 1);
1264     size_t displ = 0;
1265     size_t recycled_bytes;
1266
1267     GC_ASSERT(bytes != 0);
1268     GC_ASSERT(GC_page_size != 0);
1269     /* TODO: Assert correct memory flags if GWW_VDB */
1270     if (page_offset != 0)
1271       displ = GC_page_size - page_offset;
1272     recycled_bytes = (bytes - displ) & ~(GC_page_size - 1);
1273     GC_COND_LOG_PRINTF("Recycle %lu scratch-allocated bytes at %p\n",
1274                        (unsigned long)recycled_bytes, ptr);
1275     if (recycled_bytes > 0)
1276       GC_add_to_heap((struct hblk *)((word)ptr + displ), recycled_bytes);
1277   }
1278 }
1279
1280 /* Allocate or reallocate space for mark stack of size n entries.  */
1281 /* May silently fail.                                              */
1282 static void alloc_mark_stack(size_t n)
1283 {
1284     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct GC_ms_entry));
1285 #   ifdef GWW_VDB
1286       /* Don't recycle a stack segment obtained with the wrong flags.   */
1287       /* Win32 GetWriteWatch requires the right kind of memory.         */
1288       static GC_bool GC_incremental_at_stack_alloc = FALSE;
1289       GC_bool recycle_old = !GC_auto_incremental
1290                             || GC_incremental_at_stack_alloc;
1291
1292       GC_incremental_at_stack_alloc = GC_auto_incremental;
1293 #   else
1294 #     define recycle_old TRUE
1295 #   endif
1296
1297     GC_mark_stack_too_small = FALSE;
1298     if (GC_mark_stack != NULL) {
1299         if (new_stack != 0) {
1300           if (recycle_old) {
1301             /* Recycle old space.       */
1302             GC_scratch_recycle_inner(GC_mark_stack,
1303                         GC_mark_stack_size * sizeof(struct GC_ms_entry));
1304           }
1305           GC_mark_stack = new_stack;
1306           GC_mark_stack_size = n;
1307           /* FIXME: Do we need some way to reset GC_mark_stack_size?    */
1308           GC_mark_stack_limit = new_stack + n;
1309           GC_COND_LOG_PRINTF("Grew mark stack to %lu frames\n",
1310                              (unsigned long)GC_mark_stack_size);
1311         } else {
1312           WARN("Failed to grow mark stack to %" WARN_PRIdPTR " frames\n", n);
1313         }
1314     } else if (NULL == new_stack) {
1315         GC_err_printf("No space for mark stack\n");
1316         EXIT();
1317     } else {
1318         GC_mark_stack = new_stack;
1319         GC_mark_stack_size = n;
1320         GC_mark_stack_limit = new_stack + n;
1321     }
1322     GC_mark_stack_top = GC_mark_stack-1;
1323 }
1324
1325 GC_INNER void GC_mark_init(void)
1326 {
1327     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
1328 }
1329
1330 /*
1331  * Push all locations between b and t onto the mark stack.
1332  * b is the first location to be checked. t is one past the last
1333  * location to be checked.
1334  * Should only be used if there is no possibility of mark stack
1335  * overflow.
1336  */
1337 GC_API void GC_CALL GC_push_all(void *bottom, void *top)
1338 {
1339     word length;
1340
1341     bottom = (void *)(((word)bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1342     top = (void *)((word)top & ~(ALIGNMENT-1));
1343     if ((word)bottom >= (word)top) return;
1344
1345     GC_mark_stack_top++;
1346     if ((word)GC_mark_stack_top >= (word)GC_mark_stack_limit) {
1347         ABORT("Unexpected mark stack overflow");
1348     }
1349     length = (word)top - (word)bottom;
1350 #   if GC_DS_TAGS > ALIGNMENT - 1
1351         length += GC_DS_TAGS;
1352         length &= ~GC_DS_TAGS;
1353 #   endif
1354     GC_mark_stack_top -> mse_start = (ptr_t)bottom;
1355     GC_mark_stack_top -> mse_descr.w = length;
1356 }
1357
1358 #ifndef GC_DISABLE_INCREMENTAL
1359
1360   /* Analogous to the above, but push only those pages h with           */
1361   /* dirty_fn(h) != 0.  We use GC_push_all to actually push the block.  */
1362   /* Used both to selectively push dirty pages, or to push a block in   */
1363   /* piecemeal fashion, to allow for more marking concurrency.          */
1364   /* Will not overflow mark stack if GC_push_all pushes a small fixed   */
1365   /* number of entries.  (This is invoked only if GC_push_all pushes    */
1366   /* a single entry, or if it marks each object before pushing it, thus */
1367   /* ensuring progress in the event of a stack overflow.)               */
1368   STATIC void GC_push_selected(ptr_t bottom, ptr_t top,
1369                                GC_bool (*dirty_fn)(struct hblk *))
1370   {
1371     struct hblk * h;
1372
1373     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1374     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
1375     if ((word)bottom >= (word)top) return;
1376
1377     h = HBLKPTR(bottom + HBLKSIZE);
1378     if ((word)top <= (word)h) {
1379         if ((*dirty_fn)(h-1)) {
1380             GC_push_all(bottom, top);
1381         }
1382         return;
1383     }
1384     if ((*dirty_fn)(h-1)) {
1385         if ((word)(GC_mark_stack_top - GC_mark_stack)
1386             > 3 * GC_mark_stack_size / 4) {
1387             GC_push_all(bottom, top);
1388             return;
1389         }
1390         GC_push_all(bottom, h);
1391     }
1392
1393     while ((word)(h+1) <= (word)top) {
1394         if ((*dirty_fn)(h)) {
1395             if ((word)(GC_mark_stack_top - GC_mark_stack)
1396                 > 3 * GC_mark_stack_size / 4) {
1397                 /* Danger of mark stack overflow.       */
1398                 GC_push_all(h, top);
1399                 return;
1400             } else {
1401                 GC_push_all(h, h + 1);
1402             }
1403         }
1404         h++;
1405     }
1406
1407     if ((ptr_t)h != top && (*dirty_fn)(h)) {
1408        GC_push_all(h, top);
1409     }
1410   }
1411
1412   GC_API void GC_CALL GC_push_conditional(void *bottom, void *top, int all)
1413   {
1414     if (!all) {
1415       GC_push_selected((ptr_t)bottom, (ptr_t)top, GC_page_was_dirty);
1416     } else {
1417 #     ifdef PROC_VDB
1418         if (GC_auto_incremental) {
1419           /* Pages that were never dirtied cannot contain pointers.     */
1420           GC_push_selected((ptr_t)bottom, (ptr_t)top, GC_page_was_ever_dirty);
1421         } else
1422 #     endif
1423       /* else */ {
1424         GC_push_all(bottom, top);
1425       }
1426     }
1427   }
1428 #else
1429   GC_API void GC_CALL GC_push_conditional(void *bottom, void *top,
1430                                           int all GC_ATTR_UNUSED)
1431   {
1432     GC_push_all(bottom, top);
1433   }
1434 #endif /* GC_DISABLE_INCREMENTAL */
1435
1436 #if defined(AMIGA) || defined(MACOS) || defined(GC_DARWIN_THREADS)
1437   void GC_push_one(word p)
1438   {
1439     GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
1440   }
1441 #endif
1442
1443 #ifdef GC_WIN32_THREADS
1444   GC_INNER void GC_push_many_regs(const word *regs, unsigned count)
1445   {
1446     unsigned i;
1447     for (i = 0; i < count; i++)
1448       GC_PUSH_ONE_STACK(regs[i], MARKED_FROM_REGISTER);
1449   }
1450 #endif
1451
1452 GC_API struct GC_ms_entry * GC_CALL GC_mark_and_push(void *obj,
1453                                                 mse *mark_stack_ptr,
1454                                                 mse *mark_stack_limit,
1455                                                 void ** src GC_ATTR_UNUSED)
1456 {
1457     hdr * hhdr;
1458
1459     PREFETCH(obj);
1460     GET_HDR(obj, hhdr);
1461     if ((EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr), FALSE)
1462          && (!GC_all_interior_pointers
1463              || NULL == (hhdr = GC_find_header((ptr_t)GC_base(obj)))))
1464         || EXPECT(HBLK_IS_FREE(hhdr), FALSE)) {
1465       GC_ADD_TO_BLACK_LIST_NORMAL(obj, (ptr_t)src);
1466       return mark_stack_ptr;
1467     }
1468     return GC_push_contents_hdr((ptr_t)obj, mark_stack_ptr, mark_stack_limit,
1469                                 (ptr_t)src, hhdr, TRUE);
1470 }
1471
1472 /* Mark and push (i.e. gray) a single object p onto the main    */
1473 /* mark stack.  Consider p to be valid if it is an interior     */
1474 /* pointer.                                                     */
1475 /* The object p has passed a preliminary pointer validity       */
1476 /* test, but we do not definitely know whether it is valid.     */
1477 /* Mark bits are NOT atomically updated.  Thus this must be the */
1478 /* only thread setting them.                                    */
1479 # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
1480     GC_INNER void GC_mark_and_push_stack(ptr_t p, ptr_t source)
1481 # else
1482     GC_INNER void GC_mark_and_push_stack(ptr_t p)
1483 #   define source ((ptr_t)0)
1484 # endif
1485 {
1486     hdr * hhdr;
1487     ptr_t r = p;
1488
1489     PREFETCH(p);
1490     GET_HDR(p, hhdr);
1491     if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr), FALSE)) {
1492       if (NULL == hhdr
1493             || (r = (ptr_t)GC_base(p)) == NULL
1494             || (hhdr = HDR(r)) == NULL) {
1495         GC_ADD_TO_BLACK_LIST_STACK(p, source);
1496         return;
1497       }
1498     }
1499     if (EXPECT(HBLK_IS_FREE(hhdr), FALSE)) {
1500         GC_ADD_TO_BLACK_LIST_NORMAL(p, source);
1501         return;
1502     }
1503 #   ifdef THREADS
1504       /* Pointer is on the stack.  We may have dirtied the object       */
1505       /* it points to, but have not called GC_dirty yet.                */
1506       GC_dirty(p); /* entire object */
1507 #   endif
1508     GC_mark_stack_top = GC_push_contents_hdr(r, GC_mark_stack_top,
1509                                              GC_mark_stack_limit,
1510                                              source, hhdr, FALSE);
1511     /* We silently ignore pointers to near the end of a block,  */
1512     /* which is very mildly suboptimal.                         */
1513     /* FIXME: We should probably add a header word to address   */
1514     /* this.                                                    */
1515 }
1516 # undef source
1517
1518 #ifdef TRACE_BUF
1519
1520 # ifndef TRACE_ENTRIES
1521 #   define TRACE_ENTRIES 1000
1522 # endif
1523
1524 struct trace_entry {
1525     char * kind;
1526     word gc_no;
1527     word bytes_allocd;
1528     word arg1;
1529     word arg2;
1530 } GC_trace_buf[TRACE_ENTRIES] = { { NULL, 0, 0, 0, 0 } };
1531
1532 int GC_trace_buf_ptr = 0;
1533
1534 void GC_add_trace_entry(char *kind, word arg1, word arg2)
1535 {
1536     GC_trace_buf[GC_trace_buf_ptr].kind = kind;
1537     GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
1538     GC_trace_buf[GC_trace_buf_ptr].bytes_allocd = GC_bytes_allocd;
1539     GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
1540     GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
1541     GC_trace_buf_ptr++;
1542     if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
1543 }
1544
1545 GC_API void GC_CALL GC_print_trace_inner(word gc_no)
1546 {
1547     int i;
1548
1549     for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
1550         struct trace_entry *p;
1551
1552         if (i < 0) i = TRACE_ENTRIES-1;
1553         p = GC_trace_buf + i;
1554         if (p -> gc_no < gc_no || p -> kind == 0) {
1555             return;
1556         }
1557         GC_printf("Trace:%s (gc:%u, bytes:%lu) 0x%lX, 0x%lX\n",
1558                   p -> kind, (unsigned)p -> gc_no,
1559                   (unsigned long)p -> bytes_allocd,
1560                   (long)p->arg1 ^ 0x80000000L, (long)p->arg2 ^ 0x80000000L);
1561     }
1562     GC_printf("Trace incomplete\n");
1563 }
1564
1565 GC_API void GC_CALL GC_print_trace(word gc_no)
1566 {
1567     DCL_LOCK_STATE;
1568
1569     LOCK();
1570     GC_print_trace_inner(gc_no);
1571     UNLOCK();
1572 }
1573
1574 #endif /* TRACE_BUF */
1575
1576 /* A version of GC_push_all that treats all interior pointers as valid  */
1577 /* and scans the entire region immediately, in case the contents change.*/
1578 GC_ATTR_NO_SANITIZE_ADDR GC_ATTR_NO_SANITIZE_MEMORY GC_ATTR_NO_SANITIZE_THREAD
1579 GC_API void GC_CALL GC_push_all_eager(void *bottom, void *top)
1580 {
1581     word * b = (word *)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1582     word * t = (word *)(((word) top) & ~(ALIGNMENT-1));
1583     REGISTER word *p;
1584     REGISTER word *lim;
1585     REGISTER ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1586     REGISTER ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1587 #   define GC_greatest_plausible_heap_addr greatest_ha
1588 #   define GC_least_plausible_heap_addr least_ha
1589
1590     if (top == 0) return;
1591
1592     /* Check all pointers in range and push if they appear to be valid. */
1593       lim = t - 1 /* longword */;
1594       for (p = b; (word)p <= (word)lim;
1595            p = (word *)(((ptr_t)p) + ALIGNMENT)) {
1596         REGISTER word q = *p;
1597
1598         GC_PUSH_ONE_STACK(q, p);
1599       }
1600 #   undef GC_greatest_plausible_heap_addr
1601 #   undef GC_least_plausible_heap_addr
1602 }
1603
1604 GC_INNER void GC_push_all_stack(ptr_t bottom, ptr_t top)
1605 {
1606 #   ifndef NEED_FIXUP_POINTER
1607       if (GC_all_interior_pointers
1608 #         if defined(THREADS) && defined(MPROTECT_VDB)
1609             && !GC_auto_incremental
1610 #         endif
1611           && (word)GC_mark_stack_top
1612              < (word)(GC_mark_stack_limit - INITIAL_MARK_STACK_SIZE/8)) {
1613         GC_push_all(bottom, top);
1614       } else
1615 #   endif
1616     /* else */ {
1617       GC_push_all_eager(bottom, top);
1618     }
1619 }
1620
1621 #if defined(WRAP_MARK_SOME) && defined(PARALLEL_MARK)
1622   /* Similar to GC_push_conditional but scans the whole region immediately. */
1623   GC_ATTR_NO_SANITIZE_ADDR GC_ATTR_NO_SANITIZE_MEMORY
1624   GC_ATTR_NO_SANITIZE_THREAD
1625   GC_INNER void GC_push_conditional_eager(void *bottom, void *top,
1626                                           GC_bool all)
1627   {
1628     word * b = (word *)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1629     word * t = (word *)(((word) top) & ~(ALIGNMENT-1));
1630     REGISTER word *p;
1631     REGISTER word *lim;
1632     REGISTER ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1633     REGISTER ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1634 #   define GC_greatest_plausible_heap_addr greatest_ha
1635 #   define GC_least_plausible_heap_addr least_ha
1636
1637     if (top == NULL)
1638       return;
1639     (void)all; /* TODO: If !all then scan only dirty pages. */
1640
1641     lim = t - 1;
1642     for (p = b; (word)p <= (word)lim; p = (word *)((ptr_t)p + ALIGNMENT)) {
1643       REGISTER word q = *p;
1644
1645       GC_PUSH_ONE_HEAP(q, p, GC_mark_stack_top);
1646     }
1647 #   undef GC_greatest_plausible_heap_addr
1648 #   undef GC_least_plausible_heap_addr
1649   }
1650 #endif /* WRAP_MARK_SOME && PARALLEL_MARK */
1651
1652 #if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES) && \
1653     defined(MARK_BIT_PER_GRANULE)
1654 # if GC_GRANULE_WORDS == 1
1655 #   define USE_PUSH_MARKED_ACCELERATORS
1656 #   define PUSH_GRANULE(q) \
1657                 do { \
1658                   word qcontents = (q)[0]; \
1659                   GC_PUSH_ONE_HEAP(qcontents, q, GC_mark_stack_top); \
1660                 } while (0)
1661 # elif GC_GRANULE_WORDS == 2
1662 #   define USE_PUSH_MARKED_ACCELERATORS
1663 #   define PUSH_GRANULE(q) \
1664                 do { \
1665                   word qcontents = (q)[0]; \
1666                   GC_PUSH_ONE_HEAP(qcontents, q, GC_mark_stack_top); \
1667                   qcontents = (q)[1]; \
1668                   GC_PUSH_ONE_HEAP(qcontents, (q)+1, GC_mark_stack_top); \
1669                 } while (0)
1670 # elif GC_GRANULE_WORDS == 4
1671 #   define USE_PUSH_MARKED_ACCELERATORS
1672 #   define PUSH_GRANULE(q) \
1673                 do { \
1674                   word qcontents = (q)[0]; \
1675                   GC_PUSH_ONE_HEAP(qcontents, q, GC_mark_stack_top); \
1676                   qcontents = (q)[1]; \
1677                   GC_PUSH_ONE_HEAP(qcontents, (q)+1, GC_mark_stack_top); \
1678                   qcontents = (q)[2]; \
1679                   GC_PUSH_ONE_HEAP(qcontents, (q)+2, GC_mark_stack_top); \
1680                   qcontents = (q)[3]; \
1681                   GC_PUSH_ONE_HEAP(qcontents, (q)+3, GC_mark_stack_top); \
1682                 } while (0)
1683 # endif
1684 #endif /* !USE_MARK_BYTES && MARK_BIT_PER_GRANULE */
1685
1686 #ifdef USE_PUSH_MARKED_ACCELERATORS
1687 /* Push all objects reachable from marked objects in the given block */
1688 /* containing objects of size 1 granule.                             */
1689 STATIC void GC_push_marked1(struct hblk *h, hdr *hhdr)
1690 {
1691     word * mark_word_addr = &(hhdr->hb_marks[0]);
1692     word *p;
1693     word *plim;
1694
1695     /* Allow registers to be used for some frequently accessed  */
1696     /* global variables.  Otherwise aliasing issues are likely  */
1697     /* to prevent that.                                         */
1698     ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1699     ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1700     mse * mark_stack_top = GC_mark_stack_top;
1701     mse * mark_stack_limit = GC_mark_stack_limit;
1702
1703 #   undef GC_mark_stack_top
1704 #   undef GC_mark_stack_limit
1705 #   define GC_mark_stack_top mark_stack_top
1706 #   define GC_mark_stack_limit mark_stack_limit
1707 #   define GC_greatest_plausible_heap_addr greatest_ha
1708 #   define GC_least_plausible_heap_addr least_ha
1709
1710     p = (word *)(h->hb_body);
1711     plim = (word *)(((word)h) + HBLKSIZE);
1712
1713     /* Go through all words in block.   */
1714         while ((word)p < (word)plim) {
1715             word mark_word = *mark_word_addr++;
1716             word *q = p;
1717
1718             while(mark_word != 0) {
1719               if (mark_word & 1) {
1720                   PUSH_GRANULE(q);
1721               }
1722               q += GC_GRANULE_WORDS;
1723               mark_word >>= 1;
1724             }
1725             p += WORDSZ*GC_GRANULE_WORDS;
1726         }
1727
1728 #   undef GC_greatest_plausible_heap_addr
1729 #   undef GC_least_plausible_heap_addr
1730 #   undef GC_mark_stack_top
1731 #   undef GC_mark_stack_limit
1732 #   define GC_mark_stack_limit GC_arrays._mark_stack_limit
1733 #   define GC_mark_stack_top GC_arrays._mark_stack_top
1734     GC_mark_stack_top = mark_stack_top;
1735 }
1736
1737
1738 #ifndef UNALIGNED_PTRS
1739
1740 /* Push all objects reachable from marked objects in the given block */
1741 /* of size 2 (granules) objects.                                     */
1742 STATIC void GC_push_marked2(struct hblk *h, hdr *hhdr)
1743 {
1744     word * mark_word_addr = &(hhdr->hb_marks[0]);
1745     word *p;
1746     word *plim;
1747
1748     ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1749     ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1750     mse * mark_stack_top = GC_mark_stack_top;
1751     mse * mark_stack_limit = GC_mark_stack_limit;
1752
1753 #   undef GC_mark_stack_top
1754 #   undef GC_mark_stack_limit
1755 #   define GC_mark_stack_top mark_stack_top
1756 #   define GC_mark_stack_limit mark_stack_limit
1757 #   define GC_greatest_plausible_heap_addr greatest_ha
1758 #   define GC_least_plausible_heap_addr least_ha
1759
1760     p = (word *)(h->hb_body);
1761     plim = (word *)(((word)h) + HBLKSIZE);
1762
1763     /* Go through all words in block.   */
1764         while ((word)p < (word)plim) {
1765             word mark_word = *mark_word_addr++;
1766             word *q = p;
1767
1768             while(mark_word != 0) {
1769               if (mark_word & 1) {
1770                   PUSH_GRANULE(q);
1771                   PUSH_GRANULE(q + GC_GRANULE_WORDS);
1772               }
1773               q += 2 * GC_GRANULE_WORDS;
1774               mark_word >>= 2;
1775             }
1776             p += WORDSZ*GC_GRANULE_WORDS;
1777         }
1778
1779 #   undef GC_greatest_plausible_heap_addr
1780 #   undef GC_least_plausible_heap_addr
1781 #   undef GC_mark_stack_top
1782 #   undef GC_mark_stack_limit
1783 #   define GC_mark_stack_limit GC_arrays._mark_stack_limit
1784 #   define GC_mark_stack_top GC_arrays._mark_stack_top
1785     GC_mark_stack_top = mark_stack_top;
1786 }
1787
1788 # if GC_GRANULE_WORDS < 4
1789 /* Push all objects reachable from marked objects in the given block */
1790 /* of size 4 (granules) objects.                                     */
1791 /* There is a risk of mark stack overflow here.  But we handle that. */
1792 /* And only unmarked objects get pushed, so it's not very likely.    */
1793 STATIC void GC_push_marked4(struct hblk *h, hdr *hhdr)
1794 {
1795     word * mark_word_addr = &(hhdr->hb_marks[0]);
1796     word *p;
1797     word *plim;
1798
1799     ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1800     ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1801     mse * mark_stack_top = GC_mark_stack_top;
1802     mse * mark_stack_limit = GC_mark_stack_limit;
1803
1804 #   undef GC_mark_stack_top
1805 #   undef GC_mark_stack_limit
1806 #   define GC_mark_stack_top mark_stack_top
1807 #   define GC_mark_stack_limit mark_stack_limit
1808 #   define GC_greatest_plausible_heap_addr greatest_ha
1809 #   define GC_least_plausible_heap_addr least_ha
1810
1811     p = (word *)(h->hb_body);
1812     plim = (word *)(((word)h) + HBLKSIZE);
1813
1814     /* Go through all words in block.   */
1815         while ((word)p < (word)plim) {
1816             word mark_word = *mark_word_addr++;
1817             word *q = p;
1818
1819             while(mark_word != 0) {
1820               if (mark_word & 1) {
1821                   PUSH_GRANULE(q);
1822                   PUSH_GRANULE(q + GC_GRANULE_WORDS);
1823                   PUSH_GRANULE(q + 2*GC_GRANULE_WORDS);
1824                   PUSH_GRANULE(q + 3*GC_GRANULE_WORDS);
1825               }
1826               q += 4 * GC_GRANULE_WORDS;
1827               mark_word >>= 4;
1828             }
1829             p += WORDSZ*GC_GRANULE_WORDS;
1830         }
1831 #   undef GC_greatest_plausible_heap_addr
1832 #   undef GC_least_plausible_heap_addr
1833 #   undef GC_mark_stack_top
1834 #   undef GC_mark_stack_limit
1835 #   define GC_mark_stack_limit GC_arrays._mark_stack_limit
1836 #   define GC_mark_stack_top GC_arrays._mark_stack_top
1837     GC_mark_stack_top = mark_stack_top;
1838 }
1839
1840 #endif /* GC_GRANULE_WORDS < 4 */
1841
1842 #endif /* UNALIGNED_PTRS */
1843
1844 #endif /* USE_PUSH_MARKED_ACCELERATORS */
1845
1846 /* Push all objects reachable from marked objects in the given block.   */
1847 STATIC void GC_push_marked(struct hblk *h, hdr *hhdr)
1848 {
1849     word sz = hhdr -> hb_sz;
1850     word descr = hhdr -> hb_descr;
1851     ptr_t p;
1852     word bit_no;
1853     ptr_t lim;
1854     mse * GC_mark_stack_top_reg;
1855     mse * mark_stack_limit = GC_mark_stack_limit;
1856
1857     /* Some quick shortcuts: */
1858         if ((/* 0 | */ GC_DS_LENGTH) == descr) return;
1859         if (GC_block_empty(hhdr)/* nothing marked */) return;
1860 #   if !defined(GC_DISABLE_INCREMENTAL)
1861       GC_n_rescuing_pages++;
1862 #   endif
1863     GC_objects_are_marked = TRUE;
1864     if (sz > MAXOBJBYTES) {
1865         lim = h -> hb_body;
1866     } else {
1867         lim = (ptr_t)((word)(h + 1)->hb_body - sz);
1868     }
1869
1870     switch(BYTES_TO_GRANULES(sz)) {
1871 #   if defined(USE_PUSH_MARKED_ACCELERATORS)
1872      case 1:
1873        GC_push_marked1(h, hhdr);
1874        break;
1875 #    if !defined(UNALIGNED_PTRS)
1876        case 2:
1877          GC_push_marked2(h, hhdr);
1878          break;
1879 #     if GC_GRANULE_WORDS < 4
1880        case 4:
1881          GC_push_marked4(h, hhdr);
1882          break;
1883 #     endif
1884 #    endif
1885 #   else
1886      case 1: /* to suppress "switch statement contains no case" warning */
1887 #   endif
1888      default:
1889       GC_mark_stack_top_reg = GC_mark_stack_top;
1890       for (p = h -> hb_body, bit_no = 0; (word)p <= (word)lim;
1891            p += sz, bit_no += MARK_BIT_OFFSET(sz)) {
1892         if (mark_bit_from_hdr(hhdr, bit_no)) {
1893           /* Mark from fields inside the object. */
1894           GC_mark_stack_top_reg = GC_push_obj(p, hhdr, GC_mark_stack_top_reg,
1895                                               mark_stack_limit);
1896         }
1897       }
1898       GC_mark_stack_top = GC_mark_stack_top_reg;
1899     }
1900 }
1901
1902 #ifdef ENABLE_DISCLAIM
1903 /* Unconditionally mark from all objects which have not been reclaimed. */
1904 /* This is useful in order to retain pointers which are reachable from  */
1905 /* the disclaim notifiers.                                              */
1906 /* To determine whether an object has been reclaimed, we require that   */
1907 /* any live object has a non-zero as one of the two lowest bits of the  */
1908 /* first word.  On the other hand, a reclaimed object is a members of   */
1909 /* free-lists, and thus contains a word-aligned next-pointer as the     */
1910 /* first word.                                                          */
1911  STATIC void GC_push_unconditionally(struct hblk *h, hdr *hhdr)
1912  {
1913     word sz = hhdr -> hb_sz;
1914     word descr = hhdr -> hb_descr;
1915     ptr_t p;
1916     ptr_t lim;
1917     mse * GC_mark_stack_top_reg;
1918     mse * mark_stack_limit = GC_mark_stack_limit;
1919
1920     if ((/* 0 | */ GC_DS_LENGTH) == descr)
1921         return;
1922
1923 #   if !defined(GC_DISABLE_INCREMENTAL)
1924       GC_n_rescuing_pages++;
1925 #   endif
1926     GC_objects_are_marked = TRUE;
1927     if (sz > MAXOBJBYTES)
1928         lim = h -> hb_body;
1929     else
1930         lim = (ptr_t)((word)(h + 1)->hb_body - sz);
1931
1932     GC_mark_stack_top_reg = GC_mark_stack_top;
1933     for (p = h -> hb_body; (word)p <= (word)lim; p += sz)
1934       if ((*(word *)p & 0x3) != 0)
1935         GC_mark_stack_top_reg = GC_push_obj(p, hhdr, GC_mark_stack_top_reg,
1936                                             mark_stack_limit);
1937     GC_mark_stack_top = GC_mark_stack_top_reg;
1938   }
1939 #endif /* ENABLE_DISCLAIM */
1940
1941 #ifndef GC_DISABLE_INCREMENTAL
1942   /* Test whether any page in the given block is dirty.   */
1943   STATIC GC_bool GC_block_was_dirty(struct hblk *h, hdr *hhdr)
1944   {
1945     word sz = hhdr -> hb_sz;
1946
1947     if (sz <= MAXOBJBYTES) {
1948          return(GC_page_was_dirty(h));
1949     } else {
1950          ptr_t p = (ptr_t)h;
1951          while ((word)p < (word)h + sz) {
1952              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1953              p += HBLKSIZE;
1954          }
1955          return(FALSE);
1956     }
1957   }
1958 #endif /* GC_DISABLE_INCREMENTAL */
1959
1960 /* Similar to GC_push_marked, but skip over unallocated blocks  */
1961 /* and return address of next plausible block.                  */
1962 STATIC struct hblk * GC_push_next_marked(struct hblk *h)
1963 {
1964     hdr * hhdr = HDR(h);
1965
1966     if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr) || HBLK_IS_FREE(hhdr), FALSE)) {
1967       h = GC_next_used_block(h);
1968       if (h == 0) return(0);
1969       hhdr = GC_find_header((ptr_t)h);
1970     } else {
1971 #     ifdef LINT2
1972         if (NULL == h) ABORT("Bad HDR() definition");
1973 #     endif
1974     }
1975     GC_push_marked(h, hhdr);
1976     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1977 }
1978
1979 #ifndef GC_DISABLE_INCREMENTAL
1980   /* Identical to above, but mark only from dirty pages.        */
1981   STATIC struct hblk * GC_push_next_marked_dirty(struct hblk *h)
1982   {
1983     hdr * hhdr = HDR(h);
1984
1985     if (!GC_incremental) ABORT("Dirty bits not set up");
1986     for (;;) {
1987         if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr)
1988                    || HBLK_IS_FREE(hhdr), FALSE)) {
1989           h = GC_next_used_block(h);
1990           if (h == 0) return(0);
1991           hhdr = GC_find_header((ptr_t)h);
1992         } else {
1993 #         ifdef LINT2
1994             if (NULL == h) ABORT("Bad HDR() definition");
1995 #         endif
1996         }
1997         if (GC_block_was_dirty(h, hhdr))
1998           break;
1999         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
2000         hhdr = HDR(h);
2001     }
2002 #   ifdef ENABLE_DISCLAIM
2003       if ((hhdr -> hb_flags & MARK_UNCONDITIONALLY) != 0) {
2004         GC_push_unconditionally(h, hhdr);
2005
2006         /* Then we may ask, why not also add the MARK_UNCONDITIONALLY   */
2007         /* case to GC_push_next_marked, which is also applied to        */
2008         /* uncollectible blocks?  But it seems to me that the function  */
2009         /* does not need to scan uncollectible (and unconditionally     */
2010         /* marked) blocks since those are already handled in the        */
2011         /* MS_PUSH_UNCOLLECTABLE phase.                                 */
2012       } else
2013 #   endif
2014     /* else */ {
2015       GC_push_marked(h, hhdr);
2016     }
2017     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
2018   }
2019 #endif /* !GC_DISABLE_INCREMENTAL */
2020
2021 /* Similar to above, but for uncollectible pages.  Needed since we      */
2022 /* do not clear marks for such pages, even for full collections.        */
2023 STATIC struct hblk * GC_push_next_marked_uncollectable(struct hblk *h)
2024 {
2025     hdr * hhdr = HDR(h);
2026
2027     for (;;) {
2028         if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr)
2029                    || HBLK_IS_FREE(hhdr), FALSE)) {
2030           h = GC_next_used_block(h);
2031           if (h == 0) return(0);
2032           hhdr = GC_find_header((ptr_t)h);
2033         } else {
2034 #         ifdef LINT2
2035             if (NULL == h) ABORT("Bad HDR() definition");
2036 #         endif
2037         }
2038         if (hhdr -> hb_obj_kind == UNCOLLECTABLE) {
2039             GC_push_marked(h, hhdr);
2040             break;
2041         }
2042 #       ifdef ENABLE_DISCLAIM
2043             if ((hhdr -> hb_flags & MARK_UNCONDITIONALLY) != 0) {
2044                 GC_push_unconditionally(h, hhdr);
2045                 break;
2046             }
2047 #       endif
2048         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
2049         hhdr = HDR(h);
2050     }
2051     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
2052 }