/*

 * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers

 * Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved.

 * Copyright (c) 2000 by Hewlett-Packard Company.  All rights reserved.

 *

 * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED

 * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.

 *

 * Permission is hereby granted to use or copy this program

 * for any purpose,  provided the above notices are retained on all copies.

 * Permission to modify the code and to distribute modified code is granted,

 * provided the above notices are retained, and a notice that the code was

 * modified is included with the above copyright notice.

 *

 */

#if defined(__MINGW32__) && !defined(__MINGW_EXCPT_DEFINE_PSDK) \

    && defined(__i386__) /* cannot use macros from gcconfig.h */

  /* Otherwise EXCEPTION_REGISTRATION type declaration from winnt.h     */

  /* might be used.  That declaration has "handler" callback with NTAPI */

  /* attribute.  The proper type (with "handler" field compatible with  */

  /* GC mark_ex_handler) is declared in excpt.h.  The given macro is    */

  /* defined before any system header include.                          */

# define __MINGW_EXCPT_DEFINE_PSDK 1

#endif

#include "private/gc_pmark.h"

#include <stdio.h>

#if defined(MSWIN32) && defined(__GNUC__)

# include <excpt.h>

#endif

/* Make arguments appear live to compiler.  Put here to minimize the    */

/* risk of inlining.  Used to minimize junk left in registers.          */

GC_ATTR_NOINLINE

void GC_noop6(word arg1 GC_ATTR_UNUSED, word arg2 GC_ATTR_UNUSED,

              word arg3 GC_ATTR_UNUSED, word arg4 GC_ATTR_UNUSED,

              word arg5 GC_ATTR_UNUSED, word arg6 GC_ATTR_UNUSED)

{

  /* Avoid GC_noop6 calls to be optimized away. */

# if defined(GC_PTHREADS) && !defined(GC_WIN32_THREADS) \

     || defined(PARALLEL_MARK)

    AO_compiler_barrier(); /* to serve as a special side-effect */

# else

    GC_noop1(0);

# endif

}

/* Single argument version, robust against whole program analysis. */

volatile word GC_noop_sink;

GC_API void GC_CALL GC_noop1(word x)

{

    GC_noop_sink = x;

}

/* mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0} -- declared in gc_priv.h */

GC_INNER unsigned GC_n_mark_procs = GC_RESERVED_MARK_PROCS;

/* Initialize GC_obj_kinds properly and standard free lists properly.   */

/* This must be done statically since they may be accessed before       */

/* GC_init is called.                                                   */

/* It's done here, since we need to deal with mark descriptors.         */

GC_INNER struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {

/* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,

                /* 0 | */ GC_DS_LENGTH, FALSE, FALSE

                /*, */ OK_DISCLAIM_INITZ },

/* NORMAL */  { &GC_objfreelist[0], 0,

                /* 0 | */ GC_DS_LENGTH,

                                /* adjusted in GC_init for EXTRA_BYTES  */

                TRUE /* add length to descr */, TRUE

                /*, */ OK_DISCLAIM_INITZ },

/* UNCOLLECTABLE */

              { &GC_uobjfreelist[0], 0,

                /* 0 | */ GC_DS_LENGTH, TRUE /* add length to descr */, TRUE

                /*, */ OK_DISCLAIM_INITZ },

# ifdef GC_ATOMIC_UNCOLLECTABLE

              { &GC_auobjfreelist[0], 0,

                /* 0 | */ GC_DS_LENGTH, FALSE /* add length to descr */, FALSE

                /*, */ OK_DISCLAIM_INITZ },

# endif

# ifdef STUBBORN_ALLOC

              { (void **)&GC_sobjfreelist[0], 0,

                /* 0 | */ GC_DS_LENGTH, TRUE /* add length to descr */, TRUE

                /*, */ OK_DISCLAIM_INITZ },

# endif

};

# ifdef STUBBORN_ALLOC

#   define GC_N_KINDS_INITIAL_VALUE (STUBBORN+1)

# else

#   define GC_N_KINDS_INITIAL_VALUE STUBBORN

# endif

GC_INNER unsigned GC_n_kinds = GC_N_KINDS_INITIAL_VALUE;

# ifndef INITIAL_MARK_STACK_SIZE

#   define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)

                /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a    */

                /* multiple of HBLKSIZE.                                */

                /* The incremental collector actually likes a larger    */

                /* size, since it wants to push all marked dirty        */

                /* objects before marking anything new.  Currently we   */

                /* let it grow dynamically.                             */

# endif

STATIC word GC_n_rescuing_pages = 0;

                                /* Number of dirty pages we marked from */

                                /* excludes ptrfree pages, etc.         */

GC_INNER size_t GC_mark_stack_size = 0;

#ifdef PARALLEL_MARK

  STATIC volatile AO_t GC_first_nonempty = 0;

        /* Lowest entry on mark stack   */

        /* that may be nonempty.        */

        /* Updated only by initiating   */

        /* thread.                      */

#endif

GC_INNER mark_state_t GC_mark_state = MS_NONE;

GC_INNER GC_bool GC_mark_stack_too_small = FALSE;

static struct hblk * scan_ptr;

STATIC GC_bool GC_objects_are_marked = FALSE;

                /* Are there collectible marked objects in the heap?    */

/* Is a collection in progress?  Note that this can return true in the  */

/* nonincremental case, if a collection has been abandoned and the      */

/* mark state is now MS_INVALID.                                        */

GC_INNER GC_bool GC_collection_in_progress(void)

{

    return(GC_mark_state != MS_NONE);

}

/* clear all mark bits in the header */

GC_INNER void GC_clear_hdr_marks(hdr *hhdr)

{

    size_t last_bit = FINAL_MARK_BIT(hhdr -> hb_sz);

    BZERO(hhdr -> hb_marks, sizeof(hhdr->hb_marks));

    set_mark_bit_from_hdr(hhdr, last_bit);

    hhdr -> hb_n_marks = 0;

}

/* Set all mark bits in the header.  Used for uncollectible blocks. */

GC_INNER void GC_set_hdr_marks(hdr *hhdr)

{

    unsigned i;

    size_t sz = hhdr -> hb_sz;

    unsigned n_marks = (unsigned)FINAL_MARK_BIT(sz);

#   ifdef USE_MARK_BYTES

      for (i = 0; i <= n_marks; i += (unsigned)MARK_BIT_OFFSET(sz)) {

        hhdr -> hb_marks[i] = 1;

      }

#   else

      for (i = 0; i < divWORDSZ(n_marks + WORDSZ); ++i) {

        hhdr -> hb_marks[i] = ONES;

      }

#   endif

#   ifdef MARK_BIT_PER_OBJ

      hhdr -> hb_n_marks = n_marks;

#   else

      hhdr -> hb_n_marks = HBLK_OBJS(sz);

#   endif

}

/*

 * Clear all mark bits associated with block h.

 */

static void clear_marks_for_block(struct hblk *h, word dummy GC_ATTR_UNUSED)

{

    register hdr * hhdr = HDR(h);

    if (IS_UNCOLLECTABLE(hhdr -> hb_obj_kind)) return;

        /* Mark bit for these is cleared only once the object is        */

        /* explicitly deallocated.  This either frees the block, or     */

        /* the bit is cleared once the object is on the free list.      */

    GC_clear_hdr_marks(hhdr);

}

/* Slow but general routines for setting/clearing/asking about mark bits */

GC_API void GC_CALL GC_set_mark_bit(const void *p)

{

    struct hblk *h = HBLKPTR(p);

    hdr * hhdr = HDR(h);

    word bit_no = MARK_BIT_NO((ptr_t)p - (ptr_t)h, hhdr -> hb_sz);

    if (!mark_bit_from_hdr(hhdr, bit_no)) {

      set_mark_bit_from_hdr(hhdr, bit_no);

      ++hhdr -> hb_n_marks;

    }

}

GC_API void GC_CALL GC_clear_mark_bit(const void *p)

{

    struct hblk *h = HBLKPTR(p);

    hdr * hhdr = HDR(h);

    word bit_no = MARK_BIT_NO((ptr_t)p - (ptr_t)h, hhdr -> hb_sz);

    if (mark_bit_from_hdr(hhdr, bit_no)) {

      size_t n_marks = hhdr -> hb_n_marks;

      GC_ASSERT(n_marks != 0);

      clear_mark_bit_from_hdr(hhdr, bit_no);

      n_marks--;

#     ifdef PARALLEL_MARK

        if (n_marks != 0 || !GC_parallel)

          hhdr -> hb_n_marks = n_marks;

        /* Don't decrement to zero.  The counts are approximate due to  */

        /* concurrency issues, but we need to ensure that a count of    */

        /* zero implies an empty block.                                 */

#     else

          hhdr -> hb_n_marks = n_marks;

#     endif

    }

}

GC_API int GC_CALL GC_is_marked(const void *p)

{

    struct hblk *h = HBLKPTR(p);

    hdr * hhdr = HDR(h);

    word bit_no = MARK_BIT_NO((ptr_t)p - (ptr_t)h, hhdr -> hb_sz);

    return (int)mark_bit_from_hdr(hhdr, bit_no); /* 0 or 1 */

}

/*

 * Clear mark bits in all allocated heap blocks.  This invalidates

 * the marker invariant, and sets GC_mark_state to reflect this.

 * (This implicitly starts marking to reestablish the invariant.)

 */

GC_INNER void GC_clear_marks(void)

{

    GC_apply_to_all_blocks(clear_marks_for_block, (word)0);

    GC_objects_are_marked = FALSE;

    GC_mark_state = MS_INVALID;

    scan_ptr = 0;

}

#ifdef CHECKSUMS

  void GC_check_dirty(void);

#endif

/* Initiate a garbage collection.  Initiates a full collection if the   */

/* mark state is invalid.                                               */

GC_INNER void GC_initiate_gc(void)

{

#   ifndef GC_DISABLE_INCREMENTAL

        if (GC_incremental) {

            GC_read_dirty();

        }

#   endif

#   ifdef STUBBORN_ALLOC

        GC_read_changed();

#   endif

#   ifdef CHECKSUMS

        if (GC_incremental) GC_check_dirty();

#   endif

    GC_n_rescuing_pages = 0;

    if (GC_mark_state == MS_NONE) {

        GC_mark_state = MS_PUSH_RESCUERS;

    } else if (GC_mark_state != MS_INVALID) {

        ABORT("Unexpected state");

    } /* else this is really a full collection, and mark        */

      /* bits are invalid.                                      */

    scan_ptr = 0;

}

#ifdef PARALLEL_MARK

    STATIC void GC_do_parallel_mark(void); /* initiate parallel marking. */

#endif /* PARALLEL_MARK */

#ifdef GC_DISABLE_INCREMENTAL

# define GC_push_next_marked_dirty(h) GC_push_next_marked(h)

#else

  STATIC struct hblk * GC_push_next_marked_dirty(struct hblk *h);

                /* Invoke GC_push_marked on next dirty block above h.   */

                /* Return a pointer just past the end of this block.    */

#endif /* !GC_DISABLE_INCREMENTAL */

STATIC struct hblk * GC_push_next_marked(struct hblk *h);

                /* Ditto, but also mark from clean pages.       */

STATIC struct hblk * GC_push_next_marked_uncollectable(struct hblk *h);

                /* Ditto, but mark only from uncollectible pages.       */

static void alloc_mark_stack(size_t);

/* Perform a small amount of marking.                   */

/* We try to touch roughly a page of memory.            */

/* Return TRUE if we just finished a mark phase.        */

/* Cold_gc_frame is an address inside a GC frame that   */

/* remains valid until all marking is complete.         */

/* A zero value indicates that it's OK to miss some     */

/* register values.                                     */

/* We hold the allocation lock.  In the case of         */

/* incremental collection, the world may not be stopped.*/

#ifdef WRAP_MARK_SOME

  /* For win32, this is called after we establish a structured  */

  /* exception handler, in case Windows unmaps one of our root  */

  /* segments.  See below.  In either case, we acquire the      */

  /* allocator lock long before we get here.                    */

  STATIC GC_bool GC_mark_some_inner(ptr_t cold_gc_frame)

#else

  GC_INNER GC_bool GC_mark_some(ptr_t cold_gc_frame)

#endif

{

    switch(GC_mark_state) {

        case MS_NONE:

            break;

        case MS_PUSH_RESCUERS:

            if ((word)GC_mark_stack_top

                >= (word)(GC_mark_stack_limit - INITIAL_MARK_STACK_SIZE/2)) {

                /* Go ahead and mark, even though that might cause us to */

                /* see more marked dirty objects later on.  Avoid this   */

                /* in the future.                                        */

                GC_mark_stack_too_small = TRUE;

                MARK_FROM_MARK_STACK();

                break;

            } else {

                scan_ptr = GC_push_next_marked_dirty(scan_ptr);

                if (scan_ptr == 0) {

                    GC_COND_LOG_PRINTF("Marked from %lu dirty pages\n",

                                       (unsigned long)GC_n_rescuing_pages);

                    GC_push_roots(FALSE, cold_gc_frame);

                    GC_objects_are_marked = TRUE;

                    if (GC_mark_state != MS_INVALID) {

                        GC_mark_state = MS_ROOTS_PUSHED;

                    }

                }

            }

            break;

        case MS_PUSH_UNCOLLECTABLE:

            if ((word)GC_mark_stack_top

                >= (word)(GC_mark_stack + GC_mark_stack_size/4)) {

#               ifdef PARALLEL_MARK

                  /* Avoid this, since we don't parallelize the marker  */

                  /* here.                                              */

                  if (GC_parallel) GC_mark_stack_too_small = TRUE;

#               endif

                MARK_FROM_MARK_STACK();

                break;

            } else {

                scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);

                if (scan_ptr == 0) {

                    GC_push_roots(TRUE, cold_gc_frame);

                    GC_objects_are_marked = TRUE;

                    if (GC_mark_state != MS_INVALID) {

                        GC_mark_state = MS_ROOTS_PUSHED;

                    }

                }

            }

            break;

        case MS_ROOTS_PUSHED:

#           ifdef PARALLEL_MARK

              /* In the incremental GC case, this currently doesn't     */

              /* quite do the right thing, since it runs to             */

              /* completion.  On the other hand, starting a             */

              /* parallel marker is expensive, so perhaps it is         */

              /* the right thing?                                       */

              /* Eventually, incremental marking should run             */

              /* asynchronously in multiple threads, without grabbing   */

              /* the allocation lock.                                   */

                if (GC_parallel) {

                  GC_do_parallel_mark();

                  GC_ASSERT((word)GC_mark_stack_top < (word)GC_first_nonempty);

                  GC_mark_stack_top = GC_mark_stack - 1;

                  if (GC_mark_stack_too_small) {

                    alloc_mark_stack(2*GC_mark_stack_size);

                  }

                  if (GC_mark_state == MS_ROOTS_PUSHED) {

                    GC_mark_state = MS_NONE;

                    return(TRUE);

                  }

                  break;

                }

#           endif

            if ((word)GC_mark_stack_top >= (word)GC_mark_stack) {

                MARK_FROM_MARK_STACK();

                break;

            } else {

                GC_mark_state = MS_NONE;

                if (GC_mark_stack_too_small) {

                    alloc_mark_stack(2*GC_mark_stack_size);

                }

                return(TRUE);

            }

        case MS_INVALID:

        case MS_PARTIALLY_INVALID:

            if (!GC_objects_are_marked) {

                GC_mark_state = MS_PUSH_UNCOLLECTABLE;

                break;

            }

            if ((word)GC_mark_stack_top >= (word)GC_mark_stack) {

                MARK_FROM_MARK_STACK();

                break;

            }

            if (scan_ptr == 0 && GC_mark_state == MS_INVALID) {

                /* About to start a heap scan for marked objects. */

                /* Mark stack is empty.  OK to reallocate.        */

                if (GC_mark_stack_too_small) {

                    alloc_mark_stack(2*GC_mark_stack_size);

                }

                GC_mark_state = MS_PARTIALLY_INVALID;

            }

            scan_ptr = GC_push_next_marked(scan_ptr);

            if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {

                GC_push_roots(TRUE, cold_gc_frame);

                GC_objects_are_marked = TRUE;

                if (GC_mark_state != MS_INVALID) {

                    GC_mark_state = MS_ROOTS_PUSHED;

                }

            }

            break;

        default:

            ABORT("GC_mark_some: bad state");

    }

    return(FALSE);

}

#ifdef WRAP_MARK_SOME

# if (defined(MSWIN32) || defined(MSWINCE)) && defined(__GNUC__)

    typedef struct {

      EXCEPTION_REGISTRATION ex_reg;

      void *alt_path;

    } ext_ex_regn;

    static EXCEPTION_DISPOSITION mark_ex_handler(

        struct _EXCEPTION_RECORD *ex_rec,

        void *est_frame,

        struct _CONTEXT *context,

        void *disp_ctxt GC_ATTR_UNUSED)

    {

        if (ex_rec->ExceptionCode == STATUS_ACCESS_VIOLATION) {

          ext_ex_regn *xer = (ext_ex_regn *)est_frame;

          /* Unwind from the inner function assuming the standard */

          /* function prologue.                                   */

          /* Assumes code has not been compiled with              */

          /* -fomit-frame-pointer.                                */

          context->Esp = context->Ebp;

          context->Ebp = *((DWORD *)context->Esp);

          context->Esp = context->Esp - 8;

          /* Resume execution at the "real" handler within the    */

          /* wrapper function.                                    */

          context->Eip = (DWORD )(xer->alt_path);

          return ExceptionContinueExecution;

        } else {

            return ExceptionContinueSearch;

        }

    }

# endif /* __GNUC__ && MSWIN32 */

#if defined(GC_WIN32_THREADS) && !defined(GC_PTHREADS)

  GC_INNER GC_bool GC_started_thread_while_stopped(void);

  /* In win32_threads.c.  Did we invalidate mark phase with an  */

  /* unexpected thread start?                                   */

#endif

  GC_INNER GC_bool GC_mark_some(ptr_t cold_gc_frame)

  {

      GC_bool ret_val;

#   if defined(MSWIN32) || defined(MSWINCE)

#    ifndef __GNUC__

      /* Windows 98 appears to asynchronously create and remove  */

      /* writable memory mappings, for reasons we haven't yet    */

      /* understood.  Since we look for writable regions to      */

      /* determine the root set, we may try to mark from an      */

      /* address range that disappeared since we started the     */

      /* collection.  Thus we have to recover from faults here.  */

      /* This code does not appear to be necessary for Windows   */

      /* 95/NT/2000+. Note that this code should never generate  */

      /* an incremental GC write fault.                          */

      /* This code seems to be necessary for WinCE (at least in  */

      /* the case we'd decide to add MEM_PRIVATE sections to     */

      /* data roots in GC_register_dynamic_libraries()).         */

      /* It's conceivable that this is the same issue with       */

      /* terminating threads that we see with Linux and          */

      /* USE_PROC_FOR_LIBRARIES.                                 */

      __try {

          ret_val = GC_mark_some_inner(cold_gc_frame);

      } __except (GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?

                EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH) {

          goto handle_ex;

      }

#     if defined(GC_WIN32_THREADS) && !defined(GC_PTHREADS)

        /* With DllMain-based thread tracking, a thread may have        */

        /* started while we were marking.  This is logically equivalent */

        /* to the exception case; our results are invalid and we have   */

        /* to start over.  This cannot be prevented since we can't      */

        /* block in DllMain.                                            */

        if (GC_started_thread_while_stopped()) goto handle_ex;

#     endif

     rm_handler:

      return ret_val;

#    else /* __GNUC__ */

      /* Manually install an exception handler since GCC does    */

      /* not yet support Structured Exception Handling (SEH) on  */

      /* Win32.                                                  */

      ext_ex_regn er;

#     if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7) \

         || __clang_major__ > 3 \

         || (__clang_major__ == 3 && __clang_minor__ >= 3)

#       pragma GCC diagnostic push

        /* Suppress "taking the address of label is non-standard" warning. */

#       if defined(__clang__) || __GNUC__ > 6 \

           || (__GNUC__ == 6 && __GNUC_MINOR__ >= 4)

#         pragma GCC diagnostic ignored "-Wpedantic"

#       else

          /* GCC before ~4.8 does not accept "-Wpedantic" quietly.  */

#         pragma GCC diagnostic ignored "-pedantic"

#       endif

        er.alt_path = &&handle_ex;

#       pragma GCC diagnostic pop

#     else /* pragma diagnostic is not supported */

        er.alt_path = &&handle_ex;

#     endif

      er.ex_reg.handler = mark_ex_handler;

      __asm__ __volatile__ ("movl %%fs:0, %0" : "=r" (er.ex_reg.prev));

      __asm__ __volatile__ ("movl %0, %%fs:0" : : "r" (&er);;

      ret_val = GC_mark_some_inner(cold_gc_frame);

      /* Prevent GCC from considering the following code unreachable */

      /* and thus eliminating it.                                    */

        if (er.alt_path == 0)

          goto handle_ex;

#     if defined(GC_WIN32_THREADS) && !defined(GC_PTHREADS)

        if (GC_started_thread_while_stopped())

          goto handle_ex;

#     endif

    rm_handler:

      /* Uninstall the exception handler */

      __asm__ __volatile__ ("mov %0, %%fs:0" : : "r" (er.ex_reg.prev));

      return ret_val;

#    endif /* __GNUC__ */

#   else /* !MSWIN32 */

      /* Here we are handling the case in which /proc is used for root  */

      /* finding, and we have threads.  We may find a stack for a       */

      /* thread that is in the process of exiting, and disappears       */

      /* while we are marking it.  This seems extremely difficult to    */

      /* avoid otherwise.                                               */

      if (GC_incremental) {

        WARN("Incremental GC incompatible with /proc roots\n", 0);

        /* I'm not sure if this could still work ...    */

      }

      GC_setup_temporary_fault_handler();

      if(SETJMP(GC_jmp_buf) != 0) goto handle_ex;

      ret_val = GC_mark_some_inner(cold_gc_frame);

    rm_handler:

      GC_reset_fault_handler();

      return ret_val;

#   endif /* !MSWIN32 */

handle_ex:

    /* Exception handler starts here for all cases. */

      {

        static word warned_gc_no;

        /* Warn about it at most once per collection. */

        if (warned_gc_no != GC_gc_no) {

          warned_gc_no = GC_gc_no;

          WARN("Caught ACCESS_VIOLATION in marker;"

               " memory mapping disappeared\n", 0);

        }

      }

      /* We have bad roots on the stack.  Discard mark stack.   */

      /* Rescan from marked objects.  Redetermine roots.        */

#     ifdef REGISTER_LIBRARIES_EARLY

        START_WORLD();

        GC_cond_register_dynamic_libraries();

        STOP_WORLD();

#     endif

      GC_invalidate_mark_state();

      scan_ptr = 0;

      ret_val = FALSE;

      goto rm_handler;  /* Back to platform-specific code. */

  }

#endif /* WRAP_MARK_SOME */

GC_INNER void GC_invalidate_mark_state(void)

{

    GC_mark_state = MS_INVALID;

    GC_mark_stack_top = GC_mark_stack-1;

}

GC_INNER mse * GC_signal_mark_stack_overflow(mse *msp)

{

    GC_mark_state = MS_INVALID;

#   ifdef PARALLEL_MARK

      /* We are using a local_mark_stack in parallel mode, so   */

      /* do not signal the global mark stack to be resized.     */

      /* That will be done if required in GC_return_mark_stack. */

      if (!GC_parallel)

        GC_mark_stack_too_small = TRUE;

#   else

      GC_mark_stack_too_small = TRUE;

#   endif

    GC_COND_LOG_PRINTF("Mark stack overflow; current size = %lu entries\n",

                       (unsigned long)GC_mark_stack_size);

    return(msp - GC_MARK_STACK_DISCARDS);

}

/*

 * Mark objects pointed to by the regions described by

 * mark stack entries between mark_stack and mark_stack_top,

 * inclusive.  Assumes the upper limit of a mark stack entry

 * is never 0.  A mark stack entry never has size 0.

 * We try to traverse on the order of a hblk of memory before we return.

 * Caller is responsible for calling this until the mark stack is empty.

 * Note that this is the most performance critical routine in the

 * collector.  Hence it contains all sorts of ugly hacks to speed

 * things up.  In particular, we avoid procedure calls on the common

 * path, we take advantage of peculiarities of the mark descriptor

 * encoding, we optionally maintain a cache for the block address to

 * header mapping, we prefetch when an object is "grayed", etc.

 */

GC_ATTR_NO_SANITIZE_ADDR GC_ATTR_NO_SANITIZE_MEMORY

GC_INNER mse * GC_mark_from(mse *mark_stack_top, mse *mark_stack,

                            mse *mark_stack_limit)

{

  signed_word credit = HBLKSIZE;  /* Remaining credit for marking work  */

  ptr_t current_p;      /* Pointer to current candidate ptr.            */

  word current;         /* Candidate pointer.                           */

  ptr_t limit = 0;      /* (Incl) limit of current candidate range.     */

  word descr;

  ptr_t greatest_ha = GC_greatest_plausible_heap_addr;

  ptr_t least_ha = GC_least_plausible_heap_addr;

  DECLARE_HDR_CACHE;

# define SPLIT_RANGE_WORDS 128  /* Must be power of 2.          */

  GC_objects_are_marked = TRUE;

  INIT_HDR_CACHE;

# ifdef OS2 /* Use untweaked version to circumvent compiler problem */

    while ((word)mark_stack_top >= (word)mark_stack && credit >= 0)

# else

    while ((((ptr_t)mark_stack_top - (ptr_t)mark_stack) | credit) >= 0)

# endif

  {

    current_p = mark_stack_top -> mse_start;

    descr = mark_stack_top -> mse_descr.w;

  retry:

    /* current_p and descr describe the current object.         */

    /* *mark_stack_top is vacant.                               */

    /* The following is 0 only for small objects described by a simple  */

    /* length descriptor.  For many applications this is the common     */

    /* case, so we try to detect it quickly.                            */

    if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | GC_DS_TAGS)) {

      word tag = descr & GC_DS_TAGS;

      GC_STATIC_ASSERT(GC_DS_TAGS == 0x3);

      switch(tag) {

        case GC_DS_LENGTH:

          /* Large length.                                              */

          /* Process part of the range to avoid pushing too much on the */

          /* stack.                                                     */

          GC_ASSERT(descr < (word)GC_greatest_plausible_heap_addr

                            - (word)GC_least_plausible_heap_addr

                || (word)(current_p + descr)

                            <= (word)GC_least_plausible_heap_addr

                || (word)current_p >= (word)GC_greatest_plausible_heap_addr);

#         ifdef PARALLEL_MARK

#           define SHARE_BYTES 2048

            if (descr > SHARE_BYTES && GC_parallel

                && (word)mark_stack_top < (word)(mark_stack_limit - 1)) {

              word new_size = (descr/2) & ~(word)(sizeof(word)-1);

              mark_stack_top -> mse_start = current_p;

              mark_stack_top -> mse_descr.w = new_size + sizeof(word);

                                        /* makes sure we handle         */

                                        /* misaligned pointers.         */

              mark_stack_top++;

#             ifdef ENABLE_TRACE

                if ((word)GC_trace_addr >= (word)current_p

                    && (word)GC_trace_addr < (word)(current_p + descr)) {

                  GC_log_printf("GC #%u: large section; start %p, len %lu,"

                                " splitting (parallel) at %p\n",

                                (unsigned)GC_gc_no, (void *)current_p,

                                (unsigned long)descr,

                                (void *)(current_p + new_size));

                }

#             endif

              current_p += new_size;

              descr -= new_size;

              goto retry;

            }

#         endif /* PARALLEL_MARK */

          mark_stack_top -> mse_start =

                limit = current_p + WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);

          mark_stack_top -> mse_descr.w =

                                descr - WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);

#         ifdef ENABLE_TRACE

            if ((word)GC_trace_addr >= (word)current_p

                && (word)GC_trace_addr < (word)(current_p + descr)) {

              GC_log_printf("GC #%u: large section; start %p, len %lu,"

                            " splitting at %p\n",

                            (unsigned)GC_gc_no, (void *)current_p,

                            (unsigned long)descr, (void *)limit);

            }

#         endif

          /* Make sure that pointers overlapping the two ranges are     */

          /* considered.                                                */

          limit += sizeof(word) - ALIGNMENT;

          break;

        case GC_DS_BITMAP:

          mark_stack_top--;

#         ifdef ENABLE_TRACE

            if ((word)GC_trace_addr >= (word)current_p

                && (word)GC_trace_addr < (word)(current_p

                                                + WORDS_TO_BYTES(WORDSZ-2))) {

              GC_log_printf("GC #%u: tracing from %p bitmap descr %lu\n",

                            (unsigned)GC_gc_no, (void *)current_p,

                            (unsigned long)descr);

            }

#         endif /* ENABLE_TRACE */

          descr &= ~GC_DS_TAGS;

          credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */

          while (descr != 0) {

            if ((descr & SIGNB) != 0) {

              current = *(word *)current_p;

              FIXUP_POINTER(current);

              if (current >= (word)least_ha && current < (word)greatest_ha) {

                PREFETCH((ptr_t)current);

#               ifdef ENABLE_TRACE

                  if (GC_trace_addr == current_p) {

                    GC_log_printf("GC #%u: considering(3) %p -> %p\n",

                                  (unsigned)GC_gc_no, (void *)current_p,

                                  (void *)current);

                  }

#               endif /* ENABLE_TRACE */

                PUSH_CONTENTS((ptr_t)current, mark_stack_top,

                              mark_stack_limit, current_p);

              }

            }

            descr <<= 1;

            current_p += sizeof(word);

          }

          continue;

        case GC_DS_PROC:

          mark_stack_top--;

#         ifdef ENABLE_TRACE

            if ((word)GC_trace_addr >= (word)current_p

                && GC_base(current_p) != 0

                && GC_base(current_p) == GC_base(GC_trace_addr)) {

              GC_log_printf("GC #%u: tracing from %p, proc descr %lu\n",

                            (unsigned)GC_gc_no, (void *)current_p,

                            (unsigned long)descr);

            }

#         endif /* ENABLE_TRACE */

          credit -= GC_PROC_BYTES;

          mark_stack_top = (*PROC(descr))((word *)current_p, mark_stack_top,

                                          mark_stack_limit, ENV(descr));

          continue;

        case GC_DS_PER_OBJECT:

          if ((signed_word)descr >= 0) {

            /* Descriptor is in the object.     */

            descr = *(word *)(current_p + descr - GC_DS_PER_OBJECT);

          } else {

            /* Descriptor is in type descriptor pointed to by first     */

            /* word in object.                                          */

            ptr_t type_descr = *(ptr_t *)current_p;

            /* type_descr is either a valid pointer to the descriptor   */

            /* structure, or this object was on a free list.            */

            /* If it was anything but the last object on the free list, */

            /* we will misinterpret the next object on the free list as */

            /* the type descriptor, and get a 0 GC descriptor, which    */

            /* is ideal.  Unfortunately, we need to check for the last  */

            /* object case explicitly.                                  */

            if (0 == type_descr) {

                /* Rarely executed.     */

                mark_stack_top--;

                continue;

            }

            descr = *(word *)(type_descr

                              - ((signed_word)descr + (GC_INDIR_PER_OBJ_BIAS

                                                       - GC_DS_PER_OBJECT)));

          }

          if (0 == descr) {

              /* Can happen either because we generated a 0 descriptor  */

              /* or we saw a pointer to a free object.          */

              mark_stack_top--;

              continue;

          }

          goto retry;

      }

    } else /* Small object with length descriptor */ {

      mark_stack_top--;

#     ifndef SMALL_CONFIG

        if (descr < sizeof(word))

          continue;

#     endif

#     ifdef ENABLE_TRACE

        if ((word)GC_trace_addr >= (word)current_p

            && (word)GC_trace_addr < (word)(current_p + descr)) {

          GC_log_printf("GC #%u: small object; start %p, len %lu\n",

                        (unsigned)GC_gc_no, (void *)current_p,

                        (unsigned long)descr);

        }

#     endif

      limit = current_p + (word)descr;

    }

    /* The simple case in which we're scanning a range. */

    GC_ASSERT(!((word)current_p & (ALIGNMENT-1)));

    credit -= limit - current_p;

    limit -= sizeof(word);

    {

#     define PREF_DIST 4

#     ifndef SMALL_CONFIG

        word deferred;

        /* Try to prefetch the next pointer to be examined ASAP.        */

        /* Empirically, this also seems to help slightly without        */

        /* prefetches, at least on linux/X86.  Presumably this loop     */

        /* ends up with less register pressure, and gcc thus ends up    */

        /* generating slightly better code.  Overall gcc code quality   */

        /* for this loop is still not great.                            */

        for(;;) {

          PREFETCH(limit - PREF_DIST*CACHE_LINE_SIZE);

          GC_ASSERT((word)limit >= (word)current_p);

          deferred = *(word *)limit;

          FIXUP_POINTER(deferred);

          limit -= ALIGNMENT;

          if (deferred >= (word)least_ha && deferred < (word)greatest_ha) {

            PREFETCH((ptr_t)deferred);

            break;

          }

          if ((word)current_p > (word)limit) goto next_object;

          /* Unroll once, so we don't do too many of the prefetches     */

          /* based on limit.                                            */

          deferred = *(word *)limit;

          FIXUP_POINTER(deferred);

          limit -= ALIGNMENT;

          if (deferred >= (word)least_ha && deferred < (word)greatest_ha) {

            PREFETCH((ptr_t)deferred);

            break;

          }

          if ((word)current_p > (word)limit) goto next_object;

        }

#     endif

      while ((word)current_p <= (word)limit) {

        /* Empirically, unrolling this loop doesn't help a lot. */

        /* Since PUSH_CONTENTS expands to a lot of code,        */

        /* we don't.                                            */

        current = *(word *)current_p;

        FIXUP_POINTER(current);

        PREFETCH(current_p + PREF_DIST*CACHE_LINE_SIZE);

        if (current >= (word)least_ha && current < (word)greatest_ha) {

          /* Prefetch the contents of the object we just pushed.  It's  */

          /* likely we will need them soon.                             */

          PREFETCH((ptr_t)current);

#         ifdef ENABLE_TRACE

            if (GC_trace_addr == current_p) {

              GC_log_printf("GC #%u: considering(1) %p -> %p\n",

                            (unsigned)GC_gc_no, (void *)current_p,

                            (void *)current);

            }

#         endif /* ENABLE_TRACE */