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