granicus.if.org Git - gc/blob - 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(GC_WIN32_THREADS) && !defined(GC_PTHREADS)
 576       handle_thr_start:
 577 #   endif
 578       /* We have bad roots on the stack.  Discard mark stack.   */
 579       /* Rescan from marked objects.  Redetermine roots.        */
 580 #     ifdef REGISTER_LIBRARIES_EARLY
 581         START_WORLD();
 582         GC_cond_register_dynamic_libraries();
 583         STOP_WORLD();
 584 #     endif
 585       GC_invalidate_mark_state();
 586       scan_ptr = 0;
 587
 588       ret_val = FALSE;
 589       goto rm_handler;  /* Back to platform-specific code. */
 590   }
 591 #endif /* WRAP_MARK_SOME */
 592
 593 GC_INNER void GC_invalidate_mark_state(void)
 594 {
 595     GC_mark_state = MS_INVALID;
 596     GC_mark_stack_top = GC_mark_stack-1;
 597 }
 598
 599 GC_INNER mse * GC_signal_mark_stack_overflow(mse *msp)
 600 {
 601     GC_mark_state = MS_INVALID;
 602 #   ifdef PARALLEL_MARK
 603       /* We are using a local_mark_stack in parallel mode, so   */
 604       /* do not signal the global mark stack to be resized.     */
 605       /* That will be done if required in GC_return_mark_stack. */
 606       if (!GC_parallel)
 607         GC_mark_stack_too_small = TRUE;
 608 #   else
 609       GC_mark_stack_too_small = TRUE;
 610 #   endif
 611     GC_COND_LOG_PRINTF("Mark stack overflow; current size = %lu entries\n",
 612                        (unsigned long)GC_mark_stack_size);
 613     return(msp - GC_MARK_STACK_DISCARDS);
 614 }
 615
 616 /*
 617  * Mark objects pointed to by the regions described by
 618  * mark stack entries between mark_stack and mark_stack_top,
 619  * inclusive.  Assumes the upper limit of a mark stack entry
 620  * is never 0.  A mark stack entry never has size 0.
 621  * We try to traverse on the order of a hblk of memory before we return.
 622  * Caller is responsible for calling this until the mark stack is empty.
 623  * Note that this is the most performance critical routine in the
 624  * collector.  Hence it contains all sorts of ugly hacks to speed
 625  * things up.  In particular, we avoid procedure calls on the common
 626  * path, we take advantage of peculiarities of the mark descriptor
 627  * encoding, we optionally maintain a cache for the block address to
 628  * header mapping, we prefetch when an object is "grayed", etc.
 629  */
 630 GC_ATTR_NO_SANITIZE_ADDR GC_ATTR_NO_SANITIZE_MEMORY GC_ATTR_NO_SANITIZE_THREAD
 631 GC_INNER mse * GC_mark_from(mse *mark_stack_top, mse *mark_stack,
 632                             mse *mark_stack_limit)
 633 {
 634   signed_word credit = HBLKSIZE;  /* Remaining credit for marking work. */
 635   ptr_t current_p;      /* Pointer to current candidate ptr.            */
 636   word current;         /* Candidate pointer.                           */
 637   ptr_t limit = 0;      /* (Incl) limit of current candidate range.     */
 638   word descr;
 639   ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
 640   ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
 641   DECLARE_HDR_CACHE;
 642
 643 # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.          */
 644
 645   GC_objects_are_marked = TRUE;
 646   INIT_HDR_CACHE;
 647 # ifdef OS2 /* Use untweaked version to circumvent compiler problem.    */
 648     while ((word)mark_stack_top >= (word)mark_stack && credit >= 0)
 649 # else
 650     while (((((word)mark_stack_top - (word)mark_stack) | (word)credit)
 651             & SIGNB) == 0)
 652 # endif
 653   {
 654     current_p = mark_stack_top -> mse_start;
 655     descr = mark_stack_top -> mse_descr.w;
 656   retry:
 657     /* current_p and descr describe the current object.                 */
 658     /* (*mark_stack_top) is vacant.                                     */
 659     /* The following is 0 only for small objects described by a simple  */
 660     /* length descriptor.  For many applications this is the common     */
 661     /* case, so we try to detect it quickly.                            */
 662     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | GC_DS_TAGS)) {
 663       word tag = descr & GC_DS_TAGS;
 664
 665       GC_STATIC_ASSERT(GC_DS_TAGS == 0x3);
 666       switch(tag) {
 667         case GC_DS_LENGTH:
 668           /* Large length.                                              */
 669           /* Process part of the range to avoid pushing too much on the */
 670           /* stack.                                                     */
 671           GC_ASSERT(descr < (word)GC_greatest_plausible_heap_addr
 672                             - (word)GC_least_plausible_heap_addr
 673                 || (word)(current_p + descr)
 674                             <= (word)GC_least_plausible_heap_addr
 675                 || (word)current_p >= (word)GC_greatest_plausible_heap_addr);
 676 #         ifdef PARALLEL_MARK
 677 #           define SHARE_BYTES 2048
 678             if (descr > SHARE_BYTES && GC_parallel
 679                 && (word)mark_stack_top < (word)(mark_stack_limit - 1)) {
 680               word new_size = (descr/2) & ~(word)(sizeof(word)-1);
 681
 682               mark_stack_top -> mse_start = current_p;
 683               mark_stack_top -> mse_descr.w = new_size + sizeof(word);
 684                                         /* Makes sure we handle         */
 685                                         /* misaligned pointers.         */
 686               mark_stack_top++;
 687 #             ifdef ENABLE_TRACE
 688                 if ((word)GC_trace_addr >= (word)current_p
 689                     && (word)GC_trace_addr < (word)(current_p + descr)) {
 690                   GC_log_printf("GC #%u: large section; start %p, len %lu,"
 691                                 " splitting (parallel) at %p\n",
 692                                 (unsigned)GC_gc_no, (void *)current_p,
 693                                 (unsigned long)descr,
 694                                 (void *)(current_p + new_size));
 695                 }
 696 #             endif
 697               current_p += new_size;
 698               descr -= new_size;
 699               goto retry;
 700             }
 701 #         endif /* PARALLEL_MARK */
 702           mark_stack_top -> mse_start =
 703                 limit = current_p + WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
 704           mark_stack_top -> mse_descr.w =
 705                                 descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
 706 #         ifdef ENABLE_TRACE
 707             if ((word)GC_trace_addr >= (word)current_p
 708                 && (word)GC_trace_addr < (word)(current_p + descr)) {
 709               GC_log_printf("GC #%u: large section; start %p, len %lu,"
 710                             " splitting at %p\n",
 711                             (unsigned)GC_gc_no, (void *)current_p,
 712                             (unsigned long)descr, (void *)limit);
 713             }
 714 #         endif
 715           /* Make sure that pointers overlapping the two ranges are     */
 716           /* considered.                                                */
 717           limit += sizeof(word) - ALIGNMENT;
 718           break;
 719         case GC_DS_BITMAP:
 720           mark_stack_top--;
 721 #         ifdef ENABLE_TRACE
 722             if ((word)GC_trace_addr >= (word)current_p
 723                 && (word)GC_trace_addr < (word)(current_p
 724                                                 + WORDS_TO_BYTES(WORDSZ-2))) {
 725               GC_log_printf("GC #%u: tracing from %p bitmap descr %lu\n",
 726                             (unsigned)GC_gc_no, (void *)current_p,
 727                             (unsigned long)descr);
 728             }
 729 #         endif /* ENABLE_TRACE */
 730           descr &= ~GC_DS_TAGS;
 731           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
 732           while (descr != 0) {
 733             if ((descr & SIGNB) != 0) {
 734               current = *(word *)current_p;
 735               FIXUP_POINTER(current);
 736               if (current >= (word)least_ha && current < (word)greatest_ha) {
 737                 PREFETCH((ptr_t)current);
 738 #               ifdef ENABLE_TRACE
 739                   if (GC_trace_addr == current_p) {
 740                     GC_log_printf("GC #%u: considering(3) %p -> %p\n",
 741                                   (unsigned)GC_gc_no, (void *)current_p,
 742                                   (void *)current);
 743                   }
 744 #               endif /* ENABLE_TRACE */
 745                 PUSH_CONTENTS((ptr_t)current, mark_stack_top,
 746                               mark_stack_limit, current_p);
 747               }
 748             }
 749             descr <<= 1;
 750             current_p += sizeof(word);
 751           }
 752           continue;
 753         case GC_DS_PROC:
 754           mark_stack_top--;
 755 #         ifdef ENABLE_TRACE
 756             if ((word)GC_trace_addr >= (word)current_p
 757                 && GC_base(current_p) != 0
 758                 && GC_base(current_p) == GC_base(GC_trace_addr)) {
 759               GC_log_printf("GC #%u: tracing from %p, proc descr %lu\n",
 760                             (unsigned)GC_gc_no, (void *)current_p,
 761                             (unsigned long)descr);
 762             }
 763 #         endif /* ENABLE_TRACE */
 764           credit -= GC_PROC_BYTES;
 765           mark_stack_top = (*PROC(descr))((word *)current_p, mark_stack_top,
 766                                           mark_stack_limit, ENV(descr));
 767           continue;
 768         case GC_DS_PER_OBJECT:
 769           if ((signed_word)descr >= 0) {
 770             /* Descriptor is in the object.     */
 771             descr = *(word *)(current_p + descr - GC_DS_PER_OBJECT);
 772           } else {
 773             /* Descriptor is in type descriptor pointed to by first     */
 774             /* word in object.                                          */
 775             ptr_t type_descr = *(ptr_t *)current_p;
 776             /* type_descr is either a valid pointer to the descriptor   */
 777             /* structure, or this object was on a free list.            */
 778             /* If it was anything but the last object on the free list, */
 779             /* we will misinterpret the next object on the free list as */
 780             /* the type descriptor, and get a 0 GC descriptor, which    */
 781             /* is ideal.  Unfortunately, we need to check for the last  */
 782             /* object case explicitly.                                  */
 783             if (EXPECT(0 == type_descr, FALSE)) {
 784                 mark_stack_top--;
 785                 continue;
 786             }
 787             descr = *(word *)(type_descr
 788                               - ((signed_word)descr + (GC_INDIR_PER_OBJ_BIAS
 789                                                        - GC_DS_PER_OBJECT)));
 790           }
 791           if (0 == descr) {
 792               /* Can happen either because we generated a 0 descriptor  */
 793               /* or we saw a pointer to a free object.                  */
 794               mark_stack_top--;
 795               continue;
 796           }
 797           goto retry;
 798       }
 799     } else {
 800       /* Small object with length descriptor.   */
 801       mark_stack_top--;
 802 #     ifndef SMALL_CONFIG
 803         if (descr < sizeof(word))
 804           continue;
 805 #     endif
 806 #     ifdef ENABLE_TRACE
 807         if ((word)GC_trace_addr >= (word)current_p
 808             && (word)GC_trace_addr < (word)(current_p + descr)) {
 809           GC_log_printf("GC #%u: small object; start %p, len %lu\n",
 810                         (unsigned)GC_gc_no, (void *)current_p,
 811                         (unsigned long)descr);
 812         }
 813 #     endif
 814       limit = current_p + (word)descr;
 815     }
 816     /* The simple case in which we're scanning a range. */
 817     GC_ASSERT(!((word)current_p & (ALIGNMENT-1)));
 818     credit -= limit - current_p;
 819     limit -= sizeof(word);
 820     {
 821 #     define PREF_DIST 4
 822
 823 #     ifndef SMALL_CONFIG
 824         word deferred;
 825
 826         /* Try to prefetch the next pointer to be examined ASAP.        */
 827         /* Empirically, this also seems to help slightly without        */
 828         /* prefetches, at least on linux/X86.  Presumably this loop     */
 829         /* ends up with less register pressure, and gcc thus ends up    */
 830         /* generating slightly better code.  Overall gcc code quality   */
 831         /* for this loop is still not great.                            */
 832         for(;;) {
 833           PREFETCH(limit - PREF_DIST*CACHE_LINE_SIZE);
 834           GC_ASSERT((word)limit >= (word)current_p);
 835           deferred = *(word *)limit;
 836           FIXUP_POINTER(deferred);
 837           limit -= ALIGNMENT;
 838           if (deferred >= (word)least_ha && deferred < (word)greatest_ha) {
 839             PREFETCH((ptr_t)deferred);
 840             break;
 841           }
 842           if ((word)current_p > (word)limit) goto next_object;
 843           /* Unroll once, so we don't do too many of the prefetches     */
 844           /* based on limit.                                            */
 845           deferred = *(word *)limit;
 846           FIXUP_POINTER(deferred);
 847           limit -= ALIGNMENT;
 848           if (deferred >= (word)least_ha && deferred < (word)greatest_ha) {
 849             PREFETCH((ptr_t)deferred);
 850             break;
 851           }
 852           if ((word)current_p > (word)limit) goto next_object;
 853         }
 854 #     endif
 855
 856       while ((word)current_p <= (word)limit) {
 857         /* Empirically, unrolling this loop doesn't help a lot. */
 858         /* Since PUSH_CONTENTS expands to a lot of code,        */
 859         /* we don't.                                            */
 860         current = *(word *)current_p;
 861         FIXUP_POINTER(current);
 862         PREFETCH(current_p + PREF_DIST*CACHE_LINE_SIZE);
 863         if (current >= (word)least_ha && current < (word)greatest_ha) {
 864           /* Prefetch the contents of the object we just pushed.  It's  */
 865           /* likely we will need them soon.                             */
 866           PREFETCH((ptr_t)current);
 867 #         ifdef ENABLE_TRACE
 868             if (GC_trace_addr == current_p) {
 869               GC_log_printf("GC #%u: considering(1) %p -> %p\n",
 870                             (unsigned)GC_gc_no, (void *)current_p,
 871                             (void *)current);
 872             }
 873 #         endif /* ENABLE_TRACE */
 874           PUSH_CONTENTS((ptr_t)current, mark_stack_top,
 875                         mark_stack_limit, current_p);
 876         }
 877         current_p += ALIGNMENT;
 878       }
 879
 880 #     ifndef SMALL_CONFIG
 881         /* We still need to mark the entry we previously prefetched.    */
 882         /* We already know that it passes the preliminary pointer       */
 883         /* validity test.                                               */
 884 #       ifdef ENABLE_TRACE
 885             if (GC_trace_addr == current_p) {
 886               GC_log_printf("GC #%u: considering(2) %p -> %p\n",
 887                             (unsigned)GC_gc_no, (void *)current_p,
 888                             (void *)deferred);
 889             }
 890 #       endif /* ENABLE_TRACE */
 891         PUSH_CONTENTS((ptr_t)deferred, mark_stack_top,
 892                       mark_stack_limit, current_p);
 893         next_object:;
 894 #     endif
 895     }
 896   }
 897   return mark_stack_top;
 898 }
 899
 900 #ifdef PARALLEL_MARK
 901
 902 STATIC GC_bool GC_help_wanted = FALSE;  /* Protected by mark lock.      */
 903 STATIC unsigned GC_helper_count = 0;    /* Number of running helpers.   */
 904                                         /* Protected by mark lock.      */
 905 STATIC unsigned GC_active_count = 0;    /* Number of active helpers.    */
 906                                         /* Protected by mark lock.      */
 907                                         /* May increase and decrease    */
 908                                         /* within each mark cycle.  But */
 909                                         /* once it returns to 0, it     */
 910                                         /* stays zero for the cycle.    */
 911
 912 GC_INNER word GC_mark_no = 0;
 913
 914 static mse *main_local_mark_stack;
 915
 916 #ifdef LINT2
 917 # define LOCAL_MARK_STACK_SIZE (HBLKSIZE / 8)
 918 #else
 919 # define LOCAL_MARK_STACK_SIZE HBLKSIZE
 920         /* Under normal circumstances, this is big enough to guarantee  */
 921         /* we don't overflow half of it in a single call to             */
 922         /* GC_mark_from.                                                */
 923 #endif
 924
 925 /* Wait all markers to finish initialization (i.e. store        */
 926 /* marker_[b]sp, marker_mach_threads, GC_marker_Id).            */
 927 GC_INNER void GC_wait_for_markers_init(void)
 928 {
 929   signed_word count;
 930
 931   if (GC_markers_m1 == 0)
 932     return;
 933
 934   /* Allocate the local mark stack for the thread that holds GC lock.   */
 935 # ifndef CAN_HANDLE_FORK
 936     GC_ASSERT(NULL == main_local_mark_stack);
 937 # else
 938     if (NULL == main_local_mark_stack)
 939 # endif
 940   {
 941     size_t bytes_to_get =
 942                 ROUNDUP_PAGESIZE_IF_MMAP(LOCAL_MARK_STACK_SIZE * sizeof(mse));
 943     main_local_mark_stack = (mse *)GET_MEM(bytes_to_get);
 944     if (NULL == main_local_mark_stack)
 945       ABORT("Insufficient memory for main local_mark_stack");
 946     GC_add_to_our_memory((ptr_t)main_local_mark_stack, bytes_to_get);
 947   }
 948
 949   /* Reuse marker lock and builders count to synchronize        */
 950   /* marker threads startup.                                    */
 951   GC_acquire_mark_lock();
 952   GC_fl_builder_count += GC_markers_m1;
 953   count = GC_fl_builder_count;
 954   GC_release_mark_lock();
 955   if (count != 0) {
 956     GC_ASSERT(count > 0);
 957     GC_wait_for_reclaim();
 958   }
 959 }
 960
 961 /* Steal mark stack entries starting at mse low into mark stack local   */
 962 /* until we either steal mse high, or we have max entries.              */
 963 /* Return a pointer to the top of the local mark stack.                 */
 964 /* (*next) is replaced by a pointer to the next unscanned mark stack    */
 965 /* entry.                                                               */
 966 STATIC mse * GC_steal_mark_stack(mse * low, mse * high, mse * local,
 967                                  unsigned max, mse **next)
 968 {
 969     mse *p;
 970     mse *top = local - 1;
 971     unsigned i = 0;
 972
 973     GC_ASSERT((word)high >= (word)(low - 1)
 974               && (word)(high - low + 1) <= GC_mark_stack_size);
 975     for (p = low; (word)p <= (word)high && i <= max; ++p) {
 976         word descr = (word)AO_load(&p->mse_descr.ao);
 977         if (descr != 0) {
 978             /* Must be ordered after read of descr: */
 979             AO_store_release_write(&p->mse_descr.ao, 0);
 980             /* More than one thread may get this entry, but that's only */
 981             /* a minor performance problem.                             */
 982             ++top;
 983             top -> mse_descr.w = descr;
 984             top -> mse_start = p -> mse_start;
 985             GC_ASSERT((descr & GC_DS_TAGS) != GC_DS_LENGTH
 986                       || descr < (word)GC_greatest_plausible_heap_addr
 987                                         - (word)GC_least_plausible_heap_addr
 988                       || (word)(p->mse_start + descr)
 989                             <= (word)GC_least_plausible_heap_addr
 990                       || (word)p->mse_start
 991                             >= (word)GC_greatest_plausible_heap_addr);
 992             /* If this is a big object, count it as                     */
 993             /* size/256 + 1 objects.                                    */
 994             ++i;
 995             if ((descr & GC_DS_TAGS) == GC_DS_LENGTH) i += (int)(descr >> 8);
 996         }
 997     }
 998     *next = p;
 999     return top;
1000 }
1001
1002 /* Copy back a local mark stack.        */
1003 /* low and high are inclusive bounds.   */
1004 STATIC void GC_return_mark_stack(mse * low, mse * high)
1005 {
1006     mse * my_top;
1007     mse * my_start;
1008     size_t stack_size;
1009
1010     if ((word)high < (word)low) return;
1011     stack_size = high - low + 1;
1012     GC_acquire_mark_lock();
1013     my_top = GC_mark_stack_top; /* Concurrent modification impossible. */
1014     my_start = my_top + 1;
1015     if ((word)(my_start - GC_mark_stack + stack_size)
1016                 > (word)GC_mark_stack_size) {
1017       GC_COND_LOG_PRINTF("No room to copy back mark stack\n");
1018       GC_mark_state = MS_INVALID;
1019       GC_mark_stack_too_small = TRUE;
1020       /* We drop the local mark stack.  We'll fix things later. */
1021     } else {
1022       BCOPY(low, my_start, stack_size * sizeof(mse));
1023       GC_ASSERT((mse *)AO_load((volatile AO_t *)(&GC_mark_stack_top))
1024                 == my_top);
1025       AO_store_release_write((volatile AO_t *)(&GC_mark_stack_top),
1026                              (AO_t)(my_top + stack_size));
1027                 /* Ensures visibility of previously written stack contents. */
1028     }
1029     GC_release_mark_lock();
1030     GC_notify_all_marker();
1031 }
1032
1033 #ifndef N_LOCAL_ITERS
1034 # define N_LOCAL_ITERS 1
1035 #endif
1036
1037 /* This function is only called when the local  */
1038 /* and the main mark stacks are both empty.     */
1039 static GC_bool has_inactive_helpers(void)
1040 {
1041   GC_bool res;
1042
1043   GC_acquire_mark_lock();
1044   res = GC_active_count < GC_helper_count;
1045   GC_release_mark_lock();
1046   return res;
1047 }
1048
1049 /* Mark from the local mark stack.              */
1050 /* On return, the local mark stack is empty.    */
1051 /* But this may be achieved by copying the      */
1052 /* local mark stack back into the global one.   */
1053 /* We do not hold the mark lock.                */
1054 STATIC void GC_do_local_mark(mse *local_mark_stack, mse *local_top)
1055 {
1056     unsigned n;
1057
1058     for (;;) {
1059         for (n = 0; n < N_LOCAL_ITERS; ++n) {
1060             local_top = GC_mark_from(local_top, local_mark_stack,
1061                                      local_mark_stack + LOCAL_MARK_STACK_SIZE);
1062             if ((word)local_top < (word)local_mark_stack) return;
1063             if ((word)(local_top - local_mark_stack)
1064                         >= LOCAL_MARK_STACK_SIZE / 2) {
1065                 GC_return_mark_stack(local_mark_stack, local_top);
1066                 return;
1067             }
1068         }
1069         if ((word)AO_load((volatile AO_t *)&GC_mark_stack_top)
1070             < (word)AO_load(&GC_first_nonempty)
1071             && (word)local_top > (word)(local_mark_stack + 1)
1072             && has_inactive_helpers()) {
1073             /* Try to share the load, since the main stack is empty,    */
1074             /* and helper threads are waiting for a refill.             */
1075             /* The entries near the bottom of the stack are likely      */
1076             /* to require more work.  Thus we return those, even though */
1077             /* it's harder.                                             */
1078             mse * new_bottom = local_mark_stack
1079                                 + (local_top - local_mark_stack)/2;
1080             GC_ASSERT((word)new_bottom > (word)local_mark_stack
1081                       && (word)new_bottom < (word)local_top);
1082             GC_return_mark_stack(local_mark_stack, new_bottom - 1);
1083             memmove(local_mark_stack, new_bottom,
1084                     (local_top - new_bottom + 1) * sizeof(mse));
1085             local_top -= (new_bottom - local_mark_stack);
1086         }
1087     }
1088 }
1089
1090 #ifndef ENTRIES_TO_GET
1091 # define ENTRIES_TO_GET 5
1092 #endif
1093
1094 /* Mark using the local mark stack until the global mark stack is empty */
1095 /* and there are no active workers. Update GC_first_nonempty to reflect */
1096 /* progress.  Caller holds the mark lock.                               */
1097 /* Caller has already incremented GC_helper_count.  We decrement it,    */
1098 /* and maintain GC_active_count.                                        */
1099 STATIC void GC_mark_local(mse *local_mark_stack, int id)
1100 {
1101     mse * my_first_nonempty;
1102
1103     GC_active_count++;
1104     my_first_nonempty = (mse *)AO_load(&GC_first_nonempty);
1105     GC_ASSERT((word)GC_mark_stack <= (word)my_first_nonempty);
1106     GC_ASSERT((word)my_first_nonempty
1107         <= (word)AO_load((volatile AO_t *)&GC_mark_stack_top) + sizeof(mse));
1108     GC_VERBOSE_LOG_PRINTF("Starting mark helper %d\n", id);
1109     GC_release_mark_lock();
1110     for (;;) {
1111         size_t n_on_stack;
1112         unsigned n_to_get;
1113         mse * my_top;
1114         mse * local_top;
1115         mse * global_first_nonempty = (mse *)AO_load(&GC_first_nonempty);
1116
1117         GC_ASSERT((word)my_first_nonempty >= (word)GC_mark_stack &&
1118                   (word)my_first_nonempty <=
1119                         (word)AO_load((volatile AO_t *)&GC_mark_stack_top)
1120                         + sizeof(mse));
1121         GC_ASSERT((word)global_first_nonempty >= (word)GC_mark_stack);
1122         if ((word)my_first_nonempty < (word)global_first_nonempty) {
1123             my_first_nonempty = global_first_nonempty;
1124         } else if ((word)global_first_nonempty < (word)my_first_nonempty) {
1125             (void)AO_compare_and_swap(&GC_first_nonempty,
1126                                       (AO_t)global_first_nonempty,
1127                                       (AO_t)my_first_nonempty);
1128             /* If this fails, we just go ahead, without updating        */
1129             /* GC_first_nonempty.                                       */
1130         }
1131         /* Perhaps we should also update GC_first_nonempty, if it */
1132         /* is less.  But that would require using atomic updates. */
1133         my_top = (mse *)AO_load_acquire((volatile AO_t *)(&GC_mark_stack_top));
1134         if ((word)my_top < (word)my_first_nonempty) {
1135             GC_acquire_mark_lock();
1136             my_top = GC_mark_stack_top;
1137                 /* Asynchronous modification impossible here,   */
1138                 /* since we hold mark lock.                     */
1139             n_on_stack = my_top - my_first_nonempty + 1;
1140             if (0 == n_on_stack) {
1141                 GC_active_count--;
1142                 GC_ASSERT(GC_active_count <= GC_helper_count);
1143                 /* Other markers may redeposit objects          */
1144                 /* on the stack.                                */
1145                 if (0 == GC_active_count) GC_notify_all_marker();
1146                 while (GC_active_count > 0
1147                        && (word)AO_load(&GC_first_nonempty)
1148                                 > (word)GC_mark_stack_top) {
1149                     /* We will be notified if either GC_active_count    */
1150                     /* reaches zero, or if more objects are pushed on   */
1151                     /* the global mark stack.                           */
1152                     GC_wait_marker();
1153                 }
1154                 if (GC_active_count == 0
1155                     && (word)AO_load(&GC_first_nonempty)
1156                         > (word)GC_mark_stack_top) {
1157                     GC_bool need_to_notify = FALSE;
1158                     /* The above conditions can't be falsified while we */
1159                     /* hold the mark lock, since neither                */
1160                     /* GC_active_count nor GC_mark_stack_top can        */
1161                     /* change.  GC_first_nonempty can only be           */
1162                     /* incremented asynchronously.  Thus we know that   */
1163                     /* both conditions actually held simultaneously.    */
1164                     GC_helper_count--;
1165                     if (0 == GC_helper_count) need_to_notify = TRUE;
1166                     GC_VERBOSE_LOG_PRINTF("Finished mark helper %d\n", id);
1167                     if (need_to_notify) GC_notify_all_marker();
1168                     return;
1169                 }
1170                 /* Else there's something on the stack again, or        */
1171                 /* another helper may push something.                   */
1172                 GC_active_count++;
1173                 GC_ASSERT(GC_active_count > 0);
1174                 GC_release_mark_lock();
1175                 continue;
1176             } else {
1177                 GC_release_mark_lock();
1178             }
1179         } else {
1180             n_on_stack = my_top - my_first_nonempty + 1;
1181         }
1182         n_to_get = ENTRIES_TO_GET;
1183         if (n_on_stack < 2 * ENTRIES_TO_GET) n_to_get = 1;
1184         local_top = GC_steal_mark_stack(my_first_nonempty, my_top,
1185                                         local_mark_stack, n_to_get,
1186                                         &my_first_nonempty);
1187         GC_ASSERT((word)my_first_nonempty >= (word)GC_mark_stack &&
1188                   (word)my_first_nonempty <=
1189                         (word)AO_load((volatile AO_t *)&GC_mark_stack_top)
1190                         + sizeof(mse));
1191         GC_do_local_mark(local_mark_stack, local_top);
1192     }
1193 }
1194
1195 /* Perform Parallel mark.                       */
1196 /* We hold the GC lock, not the mark lock.      */
1197 /* Currently runs until the mark stack is       */
1198 /* empty.                                       */
1199 STATIC void GC_do_parallel_mark(void)
1200 {
1201     GC_acquire_mark_lock();
1202     GC_ASSERT(I_HOLD_LOCK());
1203     /* This could be a GC_ASSERT, but it seems safer to keep it on      */
1204     /* all the time, especially since it's cheap.                       */
1205     if (GC_help_wanted || GC_active_count != 0 || GC_helper_count != 0)
1206         ABORT("Tried to start parallel mark in bad state");
1207     GC_VERBOSE_LOG_PRINTF("Starting marking for mark phase number %lu\n",
1208                           (unsigned long)GC_mark_no);
1209     GC_first_nonempty = (AO_t)GC_mark_stack;
1210     GC_active_count = 0;
1211     GC_helper_count = 1;
1212     GC_help_wanted = TRUE;
1213     GC_notify_all_marker();
1214         /* Wake up potential helpers.   */
1215     GC_mark_local(main_local_mark_stack, 0);
1216     GC_help_wanted = FALSE;
1217     /* Done; clean up.  */
1218     while (GC_helper_count > 0) {
1219       GC_wait_marker();
1220     }
1221     /* GC_helper_count cannot be incremented while not GC_help_wanted.  */
1222     GC_VERBOSE_LOG_PRINTF("Finished marking for mark phase number %lu\n",
1223                           (unsigned long)GC_mark_no);
1224     GC_mark_no++;
1225     GC_release_mark_lock();
1226     GC_notify_all_marker();
1227 }
1228
1229
1230 /* Try to help out the marker, if it's running.         */
1231 /* We do not hold the GC lock, but the requestor does.  */
1232 /* And we hold the mark lock.                           */
1233 GC_INNER void GC_help_marker(word my_mark_no)
1234 {
1235 #   define my_id my_id_mse.mse_descr.w
1236     mse my_id_mse;  /* align local_mark_stack explicitly */
1237     mse local_mark_stack[LOCAL_MARK_STACK_SIZE];
1238                 /* Note: local_mark_stack is quite big (up to 128 KiB). */
1239
1240     GC_ASSERT(GC_parallel);
1241     while (GC_mark_no < my_mark_no
1242            || (!GC_help_wanted && GC_mark_no == my_mark_no)) {
1243       GC_wait_marker();
1244     }
1245     my_id = GC_helper_count;
1246     if (GC_mark_no != my_mark_no || my_id > (unsigned)GC_markers_m1) {
1247       /* Second test is useful only if original threads can also        */
1248       /* act as helpers.  Under Linux they can't.                       */
1249       return;
1250     }
1251     GC_helper_count = (unsigned)my_id + 1;
1252     GC_mark_local(local_mark_stack, (int)my_id);
1253     /* GC_mark_local decrements GC_helper_count. */
1254 #   undef my_id
1255 }
1256
1257 #endif /* PARALLEL_MARK */
1258
1259 GC_INNER void GC_scratch_recycle_inner(void *ptr, size_t bytes)
1260 {
1261   if (ptr != NULL) {
1262     size_t page_offset = (word)ptr & (GC_page_size - 1);
1263     size_t displ = 0;
1264     size_t recycled_bytes;
1265
1266     GC_ASSERT(bytes != 0);
1267     GC_ASSERT(GC_page_size != 0);
1268     /* TODO: Assert correct memory flags if GWW_VDB */
1269     if (page_offset != 0)
1270       displ = GC_page_size - page_offset;
1271     recycled_bytes = (bytes - displ) & ~(GC_page_size - 1);
1272     GC_COND_LOG_PRINTF("Recycle %lu scratch-allocated bytes at %p\n",
1273                        (unsigned long)recycled_bytes, ptr);
1274     if (recycled_bytes > 0)
1275       GC_add_to_heap((struct hblk *)((word)ptr + displ), recycled_bytes);
1276   }
1277 }
1278
1279 /* Allocate or reallocate space for mark stack of size n entries.  */
1280 /* May silently fail.                                              */
1281 static void alloc_mark_stack(size_t n)
1282 {
1283     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct GC_ms_entry));
1284 #   ifdef GWW_VDB
1285       /* Don't recycle a stack segment obtained with the wrong flags.   */
1286       /* Win32 GetWriteWatch requires the right kind of memory.         */
1287       static GC_bool GC_incremental_at_stack_alloc = FALSE;
1288       GC_bool recycle_old = !GC_auto_incremental
1289                             || GC_incremental_at_stack_alloc;
1290
1291       GC_incremental_at_stack_alloc = GC_auto_incremental;
1292 #   else
1293 #     define recycle_old TRUE
1294 #   endif
1295
1296     GC_mark_stack_too_small = FALSE;
1297     if (GC_mark_stack != NULL) {
1298         if (new_stack != 0) {
1299           if (recycle_old) {
1300             /* Recycle old space.       */
1301             GC_scratch_recycle_inner(GC_mark_stack,
1302                         GC_mark_stack_size * sizeof(struct GC_ms_entry));
1303           }
1304           GC_mark_stack = new_stack;
1305           GC_mark_stack_size = n;
1306           /* FIXME: Do we need some way to reset GC_mark_stack_size?    */
1307           GC_mark_stack_limit = new_stack + n;
1308           GC_COND_LOG_PRINTF("Grew mark stack to %lu frames\n",
1309                              (unsigned long)GC_mark_stack_size);
1310         } else {
1311           WARN("Failed to grow mark stack to %" WARN_PRIdPTR " frames\n", n);
1312         }
1313     } else if (NULL == new_stack) {
1314         GC_err_printf("No space for mark stack\n");
1315         EXIT();
1316     } else {
1317         GC_mark_stack = new_stack;
1318         GC_mark_stack_size = n;
1319         GC_mark_stack_limit = new_stack + n;
1320     }
1321     GC_mark_stack_top = GC_mark_stack-1;
1322 }
1323
1324 GC_INNER void GC_mark_init(void)
1325 {
1326     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
1327 }
1328
1329 /*
1330  * Push all locations between b and t onto the mark stack.
1331  * b is the first location to be checked. t is one past the last
1332  * location to be checked.
1333  * Should only be used if there is no possibility of mark stack
1334  * overflow.
1335  */
1336 GC_API void GC_CALL GC_push_all(void *bottom, void *top)
1337 {
1338     word length;
1339
1340     bottom = (void *)(((word)bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1341     top = (void *)((word)top & ~(ALIGNMENT-1));
1342     if ((word)bottom >= (word)top) return;
1343
1344     GC_mark_stack_top++;
1345     if ((word)GC_mark_stack_top >= (word)GC_mark_stack_limit) {
1346         ABORT("Unexpected mark stack overflow");
1347     }
1348     length = (word)top - (word)bottom;
1349 #   if GC_DS_TAGS > ALIGNMENT - 1
1350         length += GC_DS_TAGS;
1351         length &= ~GC_DS_TAGS;
1352 #   endif
1353     GC_mark_stack_top -> mse_start = (ptr_t)bottom;
1354     GC_mark_stack_top -> mse_descr.w = length;
1355 }
1356
1357 #ifndef GC_DISABLE_INCREMENTAL
1358
1359   /* Analogous to the above, but push only those pages h with           */
1360   /* dirty_fn(h) != 0.  We use GC_push_all to actually push the block.  */
1361   /* Used both to selectively push dirty pages, or to push a block in   */
1362   /* piecemeal fashion, to allow for more marking concurrency.          */
1363   /* Will not overflow mark stack if GC_push_all pushes a small fixed   */
1364   /* number of entries.  (This is invoked only if GC_push_all pushes    */
1365   /* a single entry, or if it marks each object before pushing it, thus */
1366   /* ensuring progress in the event of a stack overflow.)               */
1367   STATIC void GC_push_selected(ptr_t bottom, ptr_t top,
1368                                GC_bool (*dirty_fn)(struct hblk *))
1369   {
1370     struct hblk * h;
1371
1372     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1373     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
1374     if ((word)bottom >= (word)top) return;
1375
1376     h = HBLKPTR(bottom + HBLKSIZE);
1377     if ((word)top <= (word)h) {
1378         if ((*dirty_fn)(h-1)) {
1379             GC_push_all(bottom, top);
1380         }
1381         return;
1382     }
1383     if ((*dirty_fn)(h-1)) {
1384         if ((word)(GC_mark_stack_top - GC_mark_stack)
1385             > 3 * GC_mark_stack_size / 4) {
1386             GC_push_all(bottom, top);
1387             return;
1388         }
1389         GC_push_all(bottom, h);
1390     }
1391
1392     while ((word)(h+1) <= (word)top) {
1393         if ((*dirty_fn)(h)) {
1394             if ((word)(GC_mark_stack_top - GC_mark_stack)
1395                 > 3 * GC_mark_stack_size / 4) {
1396                 /* Danger of mark stack overflow.       */
1397                 GC_push_all(h, top);
1398                 return;
1399             } else {
1400                 GC_push_all(h, h + 1);
1401             }
1402         }
1403         h++;
1404     }
1405
1406     if ((ptr_t)h != top && (*dirty_fn)(h)) {
1407        GC_push_all(h, top);
1408     }
1409   }
1410
1411   GC_API void GC_CALL GC_push_conditional(void *bottom, void *top, int all)
1412   {
1413     if (!all) {
1414       GC_push_selected((ptr_t)bottom, (ptr_t)top, GC_page_was_dirty);
1415     } else {
1416 #     ifdef PROC_VDB
1417         if (GC_auto_incremental) {
1418           /* Pages that were never dirtied cannot contain pointers.     */
1419           GC_push_selected((ptr_t)bottom, (ptr_t)top, GC_page_was_ever_dirty);
1420         } else
1421 #     endif
1422       /* else */ {
1423         GC_push_all(bottom, top);
1424       }
1425     }
1426   }
1427 #else
1428   GC_API void GC_CALL GC_push_conditional(void *bottom, void *top,
1429                                           int all GC_ATTR_UNUSED)
1430   {
1431     GC_push_all(bottom, top);
1432   }
1433 #endif /* GC_DISABLE_INCREMENTAL */
1434
1435 #if defined(AMIGA) || defined(MACOS) || defined(GC_DARWIN_THREADS)
1436   void GC_push_one(word p)
1437   {
1438     GC_PUSH_ONE_STACK(p, MARKED_FROM_REGISTER);
1439   }
1440 #endif
1441
1442 #ifdef GC_WIN32_THREADS
1443   GC_INNER void GC_push_many_regs(const word *regs, unsigned count)
1444   {
1445     unsigned i;
1446     for (i = 0; i < count; i++)
1447       GC_PUSH_ONE_STACK(regs[i], MARKED_FROM_REGISTER);
1448   }
1449 #endif
1450
1451 GC_API struct GC_ms_entry * GC_CALL GC_mark_and_push(void *obj,
1452                                                 mse *mark_stack_ptr,
1453                                                 mse *mark_stack_limit,
1454                                                 void ** src GC_ATTR_UNUSED)
1455 {
1456     hdr * hhdr;
1457
1458     PREFETCH(obj);
1459     GET_HDR(obj, hhdr);
1460     if ((EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr), FALSE)
1461          && (!GC_all_interior_pointers
1462              || NULL == (hhdr = GC_find_header((ptr_t)GC_base(obj)))))
1463         || EXPECT(HBLK_IS_FREE(hhdr), FALSE)) {
1464       GC_ADD_TO_BLACK_LIST_NORMAL(obj, (ptr_t)src);
1465       return mark_stack_ptr;
1466     }
1467     return GC_push_contents_hdr((ptr_t)obj, mark_stack_ptr, mark_stack_limit,
1468                                 (ptr_t)src, hhdr, TRUE);
1469 }
1470
1471 /* Mark and push (i.e. gray) a single object p onto the main    */
1472 /* mark stack.  Consider p to be valid if it is an interior     */
1473 /* pointer.                                                     */
1474 /* The object p has passed a preliminary pointer validity       */
1475 /* test, but we do not definitely know whether it is valid.     */
1476 /* Mark bits are NOT atomically updated.  Thus this must be the */
1477 /* only thread setting them.                                    */
1478 # if defined(PRINT_BLACK_LIST) || defined(KEEP_BACK_PTRS)
1479     GC_INNER void GC_mark_and_push_stack(ptr_t p, ptr_t source)
1480 # else
1481     GC_INNER void GC_mark_and_push_stack(ptr_t p)
1482 #   define source ((ptr_t)0)
1483 # endif
1484 {
1485     hdr * hhdr;
1486     ptr_t r = p;
1487
1488     PREFETCH(p);
1489     GET_HDR(p, hhdr);
1490     if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr), FALSE)) {
1491       if (NULL == hhdr
1492             || (r = (ptr_t)GC_base(p)) == NULL
1493             || (hhdr = HDR(r)) == NULL) {
1494         GC_ADD_TO_BLACK_LIST_STACK(p, source);
1495         return;
1496       }
1497     }
1498     if (EXPECT(HBLK_IS_FREE(hhdr), FALSE)) {
1499         GC_ADD_TO_BLACK_LIST_NORMAL(p, source);
1500         return;
1501     }
1502 #   ifdef THREADS
1503       /* Pointer is on the stack.  We may have dirtied the object       */
1504       /* it points to, but have not called GC_dirty yet.                */
1505       GC_dirty(p); /* entire object */
1506 #   endif
1507     GC_mark_stack_top = GC_push_contents_hdr(r, GC_mark_stack_top,
1508                                              GC_mark_stack_limit,
1509                                              source, hhdr, FALSE);
1510     /* We silently ignore pointers to near the end of a block,  */
1511     /* which is very mildly suboptimal.                         */
1512     /* FIXME: We should probably add a header word to address   */
1513     /* this.                                                    */
1514 }
1515 # undef source
1516
1517 #ifdef TRACE_BUF
1518
1519 # ifndef TRACE_ENTRIES
1520 #   define TRACE_ENTRIES 1000
1521 # endif
1522
1523 struct trace_entry {
1524     char * kind;
1525     word gc_no;
1526     word bytes_allocd;
1527     word arg1;
1528     word arg2;
1529 } GC_trace_buf[TRACE_ENTRIES] = { { NULL, 0, 0, 0, 0 } };
1530
1531 int GC_trace_buf_ptr = 0;
1532
1533 void GC_add_trace_entry(char *kind, word arg1, word arg2)
1534 {
1535     GC_trace_buf[GC_trace_buf_ptr].kind = kind;
1536     GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
1537     GC_trace_buf[GC_trace_buf_ptr].bytes_allocd = GC_bytes_allocd;
1538     GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
1539     GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
1540     GC_trace_buf_ptr++;
1541     if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
1542 }
1543
1544 GC_API void GC_CALL GC_print_trace_inner(word gc_no)
1545 {
1546     int i;
1547
1548     for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
1549         struct trace_entry *p;
1550
1551         if (i < 0) i = TRACE_ENTRIES-1;
1552         p = GC_trace_buf + i;
1553         if (p -> gc_no < gc_no || p -> kind == 0) {
1554             return;
1555         }
1556         GC_printf("Trace:%s (gc:%u, bytes:%lu) 0x%lX, 0x%lX\n",
1557                   p -> kind, (unsigned)p -> gc_no,
1558                   (unsigned long)p -> bytes_allocd,
1559                   (long)p->arg1 ^ 0x80000000L, (long)p->arg2 ^ 0x80000000L);
1560     }
1561     GC_printf("Trace incomplete\n");
1562 }
1563
1564 GC_API void GC_CALL GC_print_trace(word gc_no)
1565 {
1566     DCL_LOCK_STATE;
1567
1568     LOCK();
1569     GC_print_trace_inner(gc_no);
1570     UNLOCK();
1571 }
1572
1573 #endif /* TRACE_BUF */
1574
1575 /* A version of GC_push_all that treats all interior pointers as valid  */
1576 /* and scans the entire region immediately, in case the contents change.*/
1577 GC_ATTR_NO_SANITIZE_ADDR GC_ATTR_NO_SANITIZE_MEMORY GC_ATTR_NO_SANITIZE_THREAD
1578 GC_API void GC_CALL GC_push_all_eager(void *bottom, void *top)
1579 {
1580     word * b = (word *)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1581     word * t = (word *)(((word) top) & ~(ALIGNMENT-1));
1582     REGISTER word *p;
1583     REGISTER word *lim;
1584     REGISTER ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1585     REGISTER ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1586 #   define GC_greatest_plausible_heap_addr greatest_ha
1587 #   define GC_least_plausible_heap_addr least_ha
1588
1589     if (top == 0) return;
1590
1591     /* Check all pointers in range and push if they appear to be valid. */
1592       lim = t - 1 /* longword */;
1593       for (p = b; (word)p <= (word)lim;
1594            p = (word *)(((ptr_t)p) + ALIGNMENT)) {
1595         REGISTER word q = *p;
1596
1597         GC_PUSH_ONE_STACK(q, p);
1598       }
1599 #   undef GC_greatest_plausible_heap_addr
1600 #   undef GC_least_plausible_heap_addr
1601 }
1602
1603 GC_INNER void GC_push_all_stack(ptr_t bottom, ptr_t top)
1604 {
1605 #   ifndef NEED_FIXUP_POINTER
1606       if (GC_all_interior_pointers
1607 #         if defined(THREADS) && defined(MPROTECT_VDB)
1608             && !GC_auto_incremental
1609 #         endif
1610           && (word)GC_mark_stack_top
1611              < (word)(GC_mark_stack_limit - INITIAL_MARK_STACK_SIZE/8)) {
1612         GC_push_all(bottom, top);
1613       } else
1614 #   endif
1615     /* else */ {
1616       GC_push_all_eager(bottom, top);
1617     }
1618 }
1619
1620 #if defined(WRAP_MARK_SOME) && defined(PARALLEL_MARK)
1621   /* Similar to GC_push_conditional but scans the whole region immediately. */
1622   GC_ATTR_NO_SANITIZE_ADDR GC_ATTR_NO_SANITIZE_MEMORY
1623   GC_ATTR_NO_SANITIZE_THREAD
1624   GC_INNER void GC_push_conditional_eager(void *bottom, void *top,
1625                                           GC_bool all)
1626   {
1627     word * b = (word *)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
1628     word * t = (word *)(((word) top) & ~(ALIGNMENT-1));
1629     REGISTER word *p;
1630     REGISTER word *lim;
1631     REGISTER ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1632     REGISTER ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1633 #   define GC_greatest_plausible_heap_addr greatest_ha
1634 #   define GC_least_plausible_heap_addr least_ha
1635
1636     if (top == NULL)
1637       return;
1638     (void)all; /* TODO: If !all then scan only dirty pages. */
1639
1640     lim = t - 1;
1641     for (p = b; (word)p <= (word)lim; p = (word *)((ptr_t)p + ALIGNMENT)) {
1642       REGISTER word q = *p;
1643
1644       GC_PUSH_ONE_HEAP(q, p, GC_mark_stack_top);
1645     }
1646 #   undef GC_greatest_plausible_heap_addr
1647 #   undef GC_least_plausible_heap_addr
1648   }
1649 #endif /* WRAP_MARK_SOME && PARALLEL_MARK */
1650
1651 #if !defined(SMALL_CONFIG) && !defined(USE_MARK_BYTES) && \
1652     defined(MARK_BIT_PER_GRANULE)
1653 # if GC_GRANULE_WORDS == 1
1654 #   define USE_PUSH_MARKED_ACCELERATORS
1655 #   define PUSH_GRANULE(q) \
1656                 do { \
1657                   word qcontents = (q)[0]; \
1658                   GC_PUSH_ONE_HEAP(qcontents, q, GC_mark_stack_top); \
1659                 } while (0)
1660 # elif GC_GRANULE_WORDS == 2
1661 #   define USE_PUSH_MARKED_ACCELERATORS
1662 #   define PUSH_GRANULE(q) \
1663                 do { \
1664                   word qcontents = (q)[0]; \
1665                   GC_PUSH_ONE_HEAP(qcontents, q, GC_mark_stack_top); \
1666                   qcontents = (q)[1]; \
1667                   GC_PUSH_ONE_HEAP(qcontents, (q)+1, GC_mark_stack_top); \
1668                 } while (0)
1669 # elif GC_GRANULE_WORDS == 4
1670 #   define USE_PUSH_MARKED_ACCELERATORS
1671 #   define PUSH_GRANULE(q) \
1672                 do { \
1673                   word qcontents = (q)[0]; \
1674                   GC_PUSH_ONE_HEAP(qcontents, q, GC_mark_stack_top); \
1675                   qcontents = (q)[1]; \
1676                   GC_PUSH_ONE_HEAP(qcontents, (q)+1, GC_mark_stack_top); \
1677                   qcontents = (q)[2]; \
1678                   GC_PUSH_ONE_HEAP(qcontents, (q)+2, GC_mark_stack_top); \
1679                   qcontents = (q)[3]; \
1680                   GC_PUSH_ONE_HEAP(qcontents, (q)+3, GC_mark_stack_top); \
1681                 } while (0)
1682 # endif
1683 #endif /* !USE_MARK_BYTES && MARK_BIT_PER_GRANULE */
1684
1685 #ifdef USE_PUSH_MARKED_ACCELERATORS
1686 /* Push all objects reachable from marked objects in the given block */
1687 /* containing objects of size 1 granule.                             */
1688 STATIC void GC_push_marked1(struct hblk *h, hdr *hhdr)
1689 {
1690     word * mark_word_addr = &(hhdr->hb_marks[0]);
1691     word *p;
1692     word *plim;
1693
1694     /* Allow registers to be used for some frequently accessed  */
1695     /* global variables.  Otherwise aliasing issues are likely  */
1696     /* to prevent that.                                         */
1697     ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1698     ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1699     mse * mark_stack_top = GC_mark_stack_top;
1700     mse * mark_stack_limit = GC_mark_stack_limit;
1701
1702 #   undef GC_mark_stack_top
1703 #   undef GC_mark_stack_limit
1704 #   define GC_mark_stack_top mark_stack_top
1705 #   define GC_mark_stack_limit mark_stack_limit
1706 #   define GC_greatest_plausible_heap_addr greatest_ha
1707 #   define GC_least_plausible_heap_addr least_ha
1708
1709     p = (word *)(h->hb_body);
1710     plim = (word *)(((word)h) + HBLKSIZE);
1711
1712     /* Go through all words in block.   */
1713         while ((word)p < (word)plim) {
1714             word mark_word = *mark_word_addr++;
1715             word *q = p;
1716
1717             while(mark_word != 0) {
1718               if (mark_word & 1) {
1719                   PUSH_GRANULE(q);
1720               }
1721               q += GC_GRANULE_WORDS;
1722               mark_word >>= 1;
1723             }
1724             p += WORDSZ*GC_GRANULE_WORDS;
1725         }
1726
1727 #   undef GC_greatest_plausible_heap_addr
1728 #   undef GC_least_plausible_heap_addr
1729 #   undef GC_mark_stack_top
1730 #   undef GC_mark_stack_limit
1731 #   define GC_mark_stack_limit GC_arrays._mark_stack_limit
1732 #   define GC_mark_stack_top GC_arrays._mark_stack_top
1733     GC_mark_stack_top = mark_stack_top;
1734 }
1735
1736
1737 #ifndef UNALIGNED_PTRS
1738
1739 /* Push all objects reachable from marked objects in the given block */
1740 /* of size 2 (granules) objects.                                     */
1741 STATIC void GC_push_marked2(struct hblk *h, hdr *hhdr)
1742 {
1743     word * mark_word_addr = &(hhdr->hb_marks[0]);
1744     word *p;
1745     word *plim;
1746
1747     ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1748     ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1749     mse * mark_stack_top = GC_mark_stack_top;
1750     mse * mark_stack_limit = GC_mark_stack_limit;
1751
1752 #   undef GC_mark_stack_top
1753 #   undef GC_mark_stack_limit
1754 #   define GC_mark_stack_top mark_stack_top
1755 #   define GC_mark_stack_limit mark_stack_limit
1756 #   define GC_greatest_plausible_heap_addr greatest_ha
1757 #   define GC_least_plausible_heap_addr least_ha
1758
1759     p = (word *)(h->hb_body);
1760     plim = (word *)(((word)h) + HBLKSIZE);
1761
1762     /* Go through all words in block.   */
1763         while ((word)p < (word)plim) {
1764             word mark_word = *mark_word_addr++;
1765             word *q = p;
1766
1767             while(mark_word != 0) {
1768               if (mark_word & 1) {
1769                   PUSH_GRANULE(q);
1770                   PUSH_GRANULE(q + GC_GRANULE_WORDS);
1771               }
1772               q += 2 * GC_GRANULE_WORDS;
1773               mark_word >>= 2;
1774             }
1775             p += WORDSZ*GC_GRANULE_WORDS;
1776         }
1777
1778 #   undef GC_greatest_plausible_heap_addr
1779 #   undef GC_least_plausible_heap_addr
1780 #   undef GC_mark_stack_top
1781 #   undef GC_mark_stack_limit
1782 #   define GC_mark_stack_limit GC_arrays._mark_stack_limit
1783 #   define GC_mark_stack_top GC_arrays._mark_stack_top
1784     GC_mark_stack_top = mark_stack_top;
1785 }
1786
1787 # if GC_GRANULE_WORDS < 4
1788 /* Push all objects reachable from marked objects in the given block */
1789 /* of size 4 (granules) objects.                                     */
1790 /* There is a risk of mark stack overflow here.  But we handle that. */
1791 /* And only unmarked objects get pushed, so it's not very likely.    */
1792 STATIC void GC_push_marked4(struct hblk *h, hdr *hhdr)
1793 {
1794     word * mark_word_addr = &(hhdr->hb_marks[0]);
1795     word *p;
1796     word *plim;
1797
1798     ptr_t greatest_ha = (ptr_t)GC_greatest_plausible_heap_addr;
1799     ptr_t least_ha = (ptr_t)GC_least_plausible_heap_addr;
1800     mse * mark_stack_top = GC_mark_stack_top;
1801     mse * mark_stack_limit = GC_mark_stack_limit;
1802
1803 #   undef GC_mark_stack_top
1804 #   undef GC_mark_stack_limit
1805 #   define GC_mark_stack_top mark_stack_top
1806 #   define GC_mark_stack_limit mark_stack_limit
1807 #   define GC_greatest_plausible_heap_addr greatest_ha
1808 #   define GC_least_plausible_heap_addr least_ha
1809
1810     p = (word *)(h->hb_body);
1811     plim = (word *)(((word)h) + HBLKSIZE);
1812
1813     /* Go through all words in block.   */
1814         while ((word)p < (word)plim) {
1815             word mark_word = *mark_word_addr++;
1816             word *q = p;
1817
1818             while(mark_word != 0) {
1819               if (mark_word & 1) {
1820                   PUSH_GRANULE(q);
1821                   PUSH_GRANULE(q + GC_GRANULE_WORDS);
1822                   PUSH_GRANULE(q + 2*GC_GRANULE_WORDS);
1823                   PUSH_GRANULE(q + 3*GC_GRANULE_WORDS);
1824               }
1825               q += 4 * GC_GRANULE_WORDS;
1826               mark_word >>= 4;
1827             }
1828             p += WORDSZ*GC_GRANULE_WORDS;
1829         }
1830 #   undef GC_greatest_plausible_heap_addr
1831 #   undef GC_least_plausible_heap_addr
1832 #   undef GC_mark_stack_top
1833 #   undef GC_mark_stack_limit
1834 #   define GC_mark_stack_limit GC_arrays._mark_stack_limit
1835 #   define GC_mark_stack_top GC_arrays._mark_stack_top
1836     GC_mark_stack_top = mark_stack_top;
1837 }
1838
1839 #endif /* GC_GRANULE_WORDS < 4 */
1840
1841 #endif /* UNALIGNED_PTRS */
1842
1843 #endif /* USE_PUSH_MARKED_ACCELERATORS */
1844
1845 /* Push all objects reachable from marked objects in the given block.   */
1846 STATIC void GC_push_marked(struct hblk *h, hdr *hhdr)
1847 {
1848     word sz = hhdr -> hb_sz;
1849     word descr = hhdr -> hb_descr;
1850     ptr_t p;
1851     word bit_no;
1852     ptr_t lim;
1853     mse * GC_mark_stack_top_reg;
1854     mse * mark_stack_limit = GC_mark_stack_limit;
1855
1856     /* Some quick shortcuts: */
1857         if ((/* 0 | */ GC_DS_LENGTH) == descr) return;
1858         if (GC_block_empty(hhdr)/* nothing marked */) return;
1859 #   if !defined(GC_DISABLE_INCREMENTAL)
1860       GC_n_rescuing_pages++;
1861 #   endif
1862     GC_objects_are_marked = TRUE;
1863     if (sz > MAXOBJBYTES) {
1864         lim = h -> hb_body;
1865     } else {
1866         lim = (ptr_t)((word)(h + 1)->hb_body - sz);
1867     }
1868
1869     switch(BYTES_TO_GRANULES(sz)) {
1870 #   if defined(USE_PUSH_MARKED_ACCELERATORS)
1871      case 1:
1872        GC_push_marked1(h, hhdr);
1873        break;
1874 #    if !defined(UNALIGNED_PTRS)
1875        case 2:
1876          GC_push_marked2(h, hhdr);
1877          break;
1878 #     if GC_GRANULE_WORDS < 4
1879        case 4:
1880          GC_push_marked4(h, hhdr);
1881          break;
1882 #     endif
1883 #    endif
1884 #   else
1885      case 1: /* to suppress "switch statement contains no case" warning */
1886 #   endif
1887      default:
1888       GC_mark_stack_top_reg = GC_mark_stack_top;
1889       for (p = h -> hb_body, bit_no = 0; (word)p <= (word)lim;
1890            p += sz, bit_no += MARK_BIT_OFFSET(sz)) {
1891         if (mark_bit_from_hdr(hhdr, bit_no)) {
1892           /* Mark from fields inside the object. */
1893           GC_mark_stack_top_reg = GC_push_obj(p, hhdr, GC_mark_stack_top_reg,
1894                                               mark_stack_limit);
1895         }
1896       }
1897       GC_mark_stack_top = GC_mark_stack_top_reg;
1898     }
1899 }
1900
1901 #ifdef ENABLE_DISCLAIM
1902 /* Unconditionally mark from all objects which have not been reclaimed. */
1903 /* This is useful in order to retain pointers which are reachable from  */
1904 /* the disclaim notifiers.                                              */
1905 /* To determine whether an object has been reclaimed, we require that   */
1906 /* any live object has a non-zero as one of the two lowest bits of the  */
1907 /* first word.  On the other hand, a reclaimed object is a members of   */
1908 /* free-lists, and thus contains a word-aligned next-pointer as the     */
1909 /* first word.                                                          */
1910  STATIC void GC_push_unconditionally(struct hblk *h, hdr *hhdr)
1911  {
1912     word sz = hhdr -> hb_sz;
1913     word descr = hhdr -> hb_descr;
1914     ptr_t p;
1915     ptr_t lim;
1916     mse * GC_mark_stack_top_reg;
1917     mse * mark_stack_limit = GC_mark_stack_limit;
1918
1919     if ((/* 0 | */ GC_DS_LENGTH) == descr)
1920         return;
1921
1922 #   if !defined(GC_DISABLE_INCREMENTAL)
1923       GC_n_rescuing_pages++;
1924 #   endif
1925     GC_objects_are_marked = TRUE;
1926     if (sz > MAXOBJBYTES)
1927         lim = h -> hb_body;
1928     else
1929         lim = (ptr_t)((word)(h + 1)->hb_body - sz);
1930
1931     GC_mark_stack_top_reg = GC_mark_stack_top;
1932     for (p = h -> hb_body; (word)p <= (word)lim; p += sz)
1933       if ((*(word *)p & 0x3) != 0)
1934         GC_mark_stack_top_reg = GC_push_obj(p, hhdr, GC_mark_stack_top_reg,
1935                                             mark_stack_limit);
1936     GC_mark_stack_top = GC_mark_stack_top_reg;
1937   }
1938 #endif /* ENABLE_DISCLAIM */
1939
1940 #ifndef GC_DISABLE_INCREMENTAL
1941   /* Test whether any page in the given block is dirty.   */
1942   STATIC GC_bool GC_block_was_dirty(struct hblk *h, hdr *hhdr)
1943   {
1944     word sz = hhdr -> hb_sz;
1945
1946     if (sz <= MAXOBJBYTES) {
1947          return(GC_page_was_dirty(h));
1948     } else {
1949          ptr_t p = (ptr_t)h;
1950          while ((word)p < (word)h + sz) {
1951              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
1952              p += HBLKSIZE;
1953          }
1954          return(FALSE);
1955     }
1956   }
1957 #endif /* GC_DISABLE_INCREMENTAL */
1958
1959 /* Similar to GC_push_marked, but skip over unallocated blocks  */
1960 /* and return address of next plausible block.                  */
1961 STATIC struct hblk * GC_push_next_marked(struct hblk *h)
1962 {
1963     hdr * hhdr = HDR(h);
1964
1965     if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr) || HBLK_IS_FREE(hhdr), FALSE)) {
1966       h = GC_next_used_block(h);
1967       if (h == 0) return(0);
1968       hhdr = GC_find_header((ptr_t)h);
1969     } else {
1970 #     ifdef LINT2
1971         if (NULL == h) ABORT("Bad HDR() definition");
1972 #     endif
1973     }
1974     GC_push_marked(h, hhdr);
1975     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
1976 }
1977
1978 #ifndef GC_DISABLE_INCREMENTAL
1979   /* Identical to above, but mark only from dirty pages.        */
1980   STATIC struct hblk * GC_push_next_marked_dirty(struct hblk *h)
1981   {
1982     hdr * hhdr = HDR(h);
1983
1984     if (!GC_incremental) ABORT("Dirty bits not set up");
1985     for (;;) {
1986         if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr)
1987                    || HBLK_IS_FREE(hhdr), FALSE)) {
1988           h = GC_next_used_block(h);
1989           if (h == 0) return(0);
1990           hhdr = GC_find_header((ptr_t)h);
1991         } else {
1992 #         ifdef LINT2
1993             if (NULL == h) ABORT("Bad HDR() definition");
1994 #         endif
1995         }
1996         if (GC_block_was_dirty(h, hhdr))
1997           break;
1998         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
1999         hhdr = HDR(h);
2000     }
2001 #   ifdef ENABLE_DISCLAIM
2002       if ((hhdr -> hb_flags & MARK_UNCONDITIONALLY) != 0) {
2003         GC_push_unconditionally(h, hhdr);
2004
2005         /* Then we may ask, why not also add the MARK_UNCONDITIONALLY   */
2006         /* case to GC_push_next_marked, which is also applied to        */
2007         /* uncollectible blocks?  But it seems to me that the function  */
2008         /* does not need to scan uncollectible (and unconditionally     */
2009         /* marked) blocks since those are already handled in the        */
2010         /* MS_PUSH_UNCOLLECTABLE phase.                                 */
2011       } else
2012 #   endif
2013     /* else */ {
2014       GC_push_marked(h, hhdr);
2015     }
2016     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
2017   }
2018 #endif /* !GC_DISABLE_INCREMENTAL */
2019
2020 /* Similar to above, but for uncollectible pages.  Needed since we      */
2021 /* do not clear marks for such pages, even for full collections.        */
2022 STATIC struct hblk * GC_push_next_marked_uncollectable(struct hblk *h)
2023 {
2024     hdr * hhdr = HDR(h);
2025
2026     for (;;) {
2027         if (EXPECT(IS_FORWARDING_ADDR_OR_NIL(hhdr)
2028                    || HBLK_IS_FREE(hhdr), FALSE)) {
2029           h = GC_next_used_block(h);
2030           if (h == 0) return(0);
2031           hhdr = GC_find_header((ptr_t)h);
2032         } else {
2033 #         ifdef LINT2
2034             if (NULL == h) ABORT("Bad HDR() definition");
2035 #         endif
2036         }
2037         if (hhdr -> hb_obj_kind == UNCOLLECTABLE) {
2038             GC_push_marked(h, hhdr);
2039             break;
2040         }
2041 #       ifdef ENABLE_DISCLAIM
2042             if ((hhdr -> hb_flags & MARK_UNCONDITIONALLY) != 0) {
2043                 GC_push_unconditionally(h, hhdr);
2044                 break;
2045             }
2046 #       endif
2047         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
2048         hhdr = HDR(h);
2049     }
2050     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
2051 }