text: /*
   * Copyright (C) 2008 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  #include "Dalvik.h"
  #include "alloc/HeapBitmap.h"
  #include "alloc/HeapInternal.h"
  #include "alloc/HeapSource.h"
  #include "alloc/MarkSweep.h"
  #include <limits.h>     // for ULONG_MAX
  #include <sys/mman.h>   // for madvise(), mmap()
  #include <cutils/ashmem.h>
  
  #define GC_DEBUG_PARANOID   2
  #define GC_DEBUG_BASIC      1
  #define GC_DEBUG_OFF        0
  #define GC_DEBUG(l)         (GC_DEBUG_LEVEL >= (l))
  
  #if 1
  #define GC_DEBUG_LEVEL      GC_DEBUG_PARANOID
  #else
  #define GC_DEBUG_LEVEL      GC_DEBUG_OFF
  #endif
  
  #define VERBOSE_GC          0
  
  #define GC_LOG_TAG      LOG_TAG "-gc"
  
  #if LOG_NDEBUG
  #define LOGV_GC(...)    ((void)0)
  #define LOGD_GC(...)    ((void)0)
  #else
  #define LOGV_GC(...)    LOG(LOG_VERBOSE, GC_LOG_TAG, __VA_ARGS__)
  #define LOGD_GC(...)    LOG(LOG_DEBUG, GC_LOG_TAG, __VA_ARGS__)
  #endif
  
  #if VERBOSE_GC
  #define LOGVV_GC(...)   LOGV_GC(__VA_ARGS__)
  #else
  #define LOGVV_GC(...)   ((void)0)
  #endif
  
  #define LOGI_GC(...)    LOG(LOG_INFO, GC_LOG_TAG, __VA_ARGS__)
  #define LOGW_GC(...)    LOG(LOG_WARN, GC_LOG_TAG, __VA_ARGS__)
  #define LOGE_GC(...)    LOG(LOG_ERROR, GC_LOG_TAG, __VA_ARGS__)
  
  #define LOG_SCAN(...)   LOGV_GC("SCAN: " __VA_ARGS__)
  #define LOG_MARK(...)   LOGV_GC("MARK: " __VA_ARGS__)
  #define LOG_SWEEP(...)  LOGV_GC("SWEEP: " __VA_ARGS__)
  #define LOG_REF(...)    LOGV_GC("REF: " __VA_ARGS__)
  
  #define LOGV_SCAN(...)  LOGVV_GC("SCAN: " __VA_ARGS__)
  #define LOGV_MARK(...)  LOGVV_GC("MARK: " __VA_ARGS__)
  #define LOGV_SWEEP(...) LOGVV_GC("SWEEP: " __VA_ARGS__)
  #define LOGV_REF(...)   LOGVV_GC("REF: " __VA_ARGS__)
  
  #if WITH_OBJECT_HEADERS
  u2 gGeneration = 0;
  static const Object *gMarkParent = NULL;
  #endif
  
  #ifndef PAGE_SIZE
  #define PAGE_SIZE 4096
  #endif
  #define ALIGN_UP_TO_PAGE_SIZE(p) \
      (((size_t)(p) + (PAGE_SIZE - 1)) & ~(PAGE_SIZE - 1))
  
  /* Do not cast the result of this to a boolean; the only set bit
   * may be > 1<<8.
   */
  static inline long isMarked(const DvmHeapChunk *hc, const GcMarkContext *ctx)
          __attribute__((always_inline));
  static inline long isMarked(const DvmHeapChunk *hc, const GcMarkContext *ctx)
  {
      return dvmHeapBitmapIsObjectBitSetInList(ctx->bitmaps, ctx->numBitmaps, hc);
  }
  
  static bool
  createMarkStack(GcMarkStack *stack)
  {
      const Object **limit;
      size_t size;
      int fd;
  
      /* Create a stack big enough for the worst possible case,
       * where the heap is perfectly full of the smallest object.
       * TODO: be better about memory usage; use a smaller stack with
       *       overflow detection and recovery.
       */
      size = dvmHeapSourceGetIdealFootprint() /
              (sizeof(Object) + HEAP_SOURCE_CHUNK_OVERHEAD);
      size = ALIGN_UP_TO_PAGE_SIZE(size);
      fd = ashmem_create_region("dalvik-heap-markstack", size);
      if (fd < 0) {
          LOGE_GC("Could not create %d-byte ashmem mark stack\n", size);
          return false;
      }
      limit = (const Object **)mmap(NULL, size, PROT_READ | PROT_WRITE,
              MAP_PRIVATE, fd, 0);
      close(fd);
      if (limit == MAP_FAILED) {
          LOGE_GC("Could not mmap %d-byte ashmem mark stack\n", size);
          return false;
      }
  
      memset(stack, 0, sizeof(*stack));
      stack->limit = limit;
      stack->base = (const Object **)((uintptr_t)limit + size);
      stack->top = stack->base;
  
      return true;
  }
  
  static void
  destroyMarkStack(GcMarkStack *stack)
  {
      munmap((char *)stack->limit,
              (uintptr_t)stack->base - (uintptr_t)stack->limit);
      memset(stack, 0, sizeof(*stack));
  }
  
  #define MARK_STACK_PUSH(stack, obj) \
      do { \
          *--(stack).top = (obj); \
      } while (false)
  
  bool
  dvmHeapBeginMarkStep()
  {
      GcMarkContext *mc = &gDvm.gcHeap->markContext;
      HeapBitmap objectBitmaps[HEAP_SOURCE_MAX_HEAP_COUNT];
      size_t numBitmaps;
  
      if (!createMarkStack(&mc->stack)) {
          return false;
      }
  
      numBitmaps = dvmHeapSourceGetObjectBitmaps(objectBitmaps,
              HEAP_SOURCE_MAX_HEAP_COUNT);
      if (numBitmaps <= 0) {
          return false;
      }
  
      /* Create mark bitmaps that cover the same ranges as the
       * current object bitmaps.
       */
      if (!dvmHeapBitmapInitListFromTemplates(mc->bitmaps, objectBitmaps,
              numBitmaps, "mark"))
      {
          return false;
      }
  
      mc->numBitmaps = numBitmaps;
      mc->finger = NULL;
  
  #if WITH_OBJECT_HEADERS
      gGeneration++;
  #endif
  
      return true;
  }
  
  static long setAndReturnMarkBit(GcMarkContext *ctx, const DvmHeapChunk *hc)
          __attribute__((always_inline));
  static long
  setAndReturnMarkBit(GcMarkContext *ctx, const DvmHeapChunk *hc)
  {
      return dvmHeapBitmapSetAndReturnObjectBitInList(ctx->bitmaps,
          ctx->numBitmaps, hc);
  }
  
  static void _markObjectNonNullCommon(const Object *obj, GcMarkContext *ctx,
          bool checkFinger, bool forceStack)
          __attribute__((always_inline));
  static void
  _markObjectNonNullCommon(const Object *obj, GcMarkContext *ctx,
          bool checkFinger, bool forceStack)
  {
      DvmHeapChunk *hc;
  
      assert(obj != NULL);
  
  #if GC_DEBUG(GC_DEBUG_PARANOID)
  //TODO: make sure we're locked
      assert(obj != (Object *)gDvm.unlinkedJavaLangClass);
      assert(dvmIsValidObject(obj));
  #endif
  
      hc = ptr2chunk(obj);
      if (!setAndReturnMarkBit(ctx, hc)) {
          /* This object was not previously marked.
           */
          if (forceStack || (checkFinger && (void *)hc < ctx->finger)) {
              /* This object will need to go on the mark stack.
               */
              MARK_STACK_PUSH(ctx->stack, obj);
          }
  
  #if WITH_OBJECT_HEADERS
          if (hc->scanGeneration != hc->markGeneration) {
              LOGE("markObject(0x%08x): wasn't scanned last time\n", (uint)obj);
              dvmAbort();
          }
          if (hc->markGeneration == gGeneration) {
              LOGE("markObject(0x%08x): already marked this generation\n",
                      (uint)obj);
              dvmAbort();
          }
          hc->oldMarkGeneration = hc->markGeneration;
          hc->markGeneration = gGeneration;
          hc->markFingerOld = hc->markFinger;
          hc->markFinger = ctx->finger;
          if (gMarkParent != NULL) {
              hc->parentOld = hc->parent;
              hc->parent = gMarkParent;
          } else {
              hc->parent = (const Object *)((uintptr_t)hc->parent | 1);
          }
          hc->markCount++;
  #endif
  #if WITH_HPROF
          if (gDvm.gcHeap->hprofContext != NULL) {
              hprofMarkRootObject(gDvm.gcHeap->hprofContext, obj, 0);
          }
  #endif
  #if DVM_TRACK_HEAP_MARKING
          gDvm.gcHeap->markCount++;
          gDvm.gcHeap->markSize += dvmHeapSourceChunkSize((void *)hc) +
                  HEAP_SOURCE_CHUNK_OVERHEAD;
  #endif
  
          /* obj->clazz can be NULL if we catch an object between
           * dvmMalloc() and DVM_OBJECT_INIT().  This is ok.
           */
          LOGV_MARK("0x%08x %s\n", (uint)obj,
                  obj->clazz == NULL ? "<null class>" : obj->clazz->name);
      }
  }
  
  /* Used to mark objects when recursing.  Recursion is done by moving
   * the finger across the bitmaps in address order and marking child
   * objects.  Any newly-marked objects whose addresses are lower than
   * the finger won't be visited by the bitmap scan, so those objects
   * need to be added to the mark stack.
   */
  static void
  markObjectNonNull(const Object *obj, GcMarkContext *ctx)
  {
      _markObjectNonNullCommon(obj, ctx, true, false);
  }
  
  #define markObject(obj, ctx) \
      do { \
          Object *MO_obj_ = (Object *)(obj); \
          if (MO_obj_ != NULL) { \
              markObjectNonNull(MO_obj_, (ctx)); \
          } \
      } while (false)
  
  /* If the object hasn't already been marked, mark it and
   * schedule it to be scanned for references.
   *
   * obj may not be NULL.  The macro dvmMarkObject() should
   * be used in situations where a reference may be NULL.
   *
   * This function may only be called when marking the root
   * set.  When recursing, use the internal markObject[NonNull]().
   */
  void
  dvmMarkObjectNonNull(const Object *obj)
  {
      _markObjectNonNullCommon(obj, &gDvm.gcHeap->markContext, false, false);
  }
  
  /* Mark the set of root objects.
   *
   * Things we need to scan:
   * - System classes defined by root classloader
   * - For each thread:
   *   - Interpreted stack, from top to "curFrame"
   *     - Dalvik registers (args + local vars)
   *   - JNI local references
   *   - Automatic VM local references (TrackedAlloc)
   *   - Associated Thread/VMThread object
   *   - ThreadGroups (could track & start with these instead of working
   *     upward from Threads)
   *   - Exception currently being thrown, if present
   * - JNI global references
   * - Interned string table
   * - Primitive classes
   * - Special objects
   *   - gDvm.outOfMemoryObj
   * - Objects allocated with ALLOC_NO_GC
   * - Objects pending finalization (but not yet finalized)
   * - Objects in debugger object registry
   *
   * Don't need:
   * - Native stack (for in-progress stuff in the VM)
   *   - The TrackedAlloc stuff watches all native VM references.
   */
  void dvmHeapMarkRootSet()
  {
      HeapRefTable *refs;
      GcHeap *gcHeap;
      Object **op;
  
      gcHeap = gDvm.gcHeap;
  
      HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_STICKY_CLASS, 0);
  
      LOG_SCAN("root class loader\n");
      dvmGcScanRootClassLoader();
      LOG_SCAN("primitive classes\n");
      dvmGcScanPrimitiveClasses();
  
      /* dvmGcScanRootThreadGroups() sets a bunch of
       * different scan states internally.
       */
      HPROF_CLEAR_GC_SCAN_STATE();
  
      LOG_SCAN("root thread groups\n");
      dvmGcScanRootThreadGroups();
  
      HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_INTERNED_STRING, 0);
  
      LOG_SCAN("interned strings\n");
      dvmGcScanInternedStrings();
  
      HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_JNI_GLOBAL, 0);
  
      LOG_SCAN("JNI global refs\n");
      dvmGcMarkJniGlobalRefs();
  
      HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_REFERENCE_CLEANUP, 0);
  
      LOG_SCAN("pending reference operations\n");
      dvmHeapMarkLargeTableRefs(gcHeap->referenceOperations, true);
  
      HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_FINALIZING, 0);
  
      LOG_SCAN("pending finalizations\n");
      dvmHeapMarkLargeTableRefs(gcHeap->pendingFinalizationRefs, false);
  
      HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_DEBUGGER, 0);
  
      LOG_SCAN("debugger refs\n");
      dvmGcMarkDebuggerRefs();
  
      HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_VM_INTERNAL, 0);
  
      /* Mark all ALLOC_NO_GC objects.
       */
      LOG_SCAN("ALLOC_NO_GC objects\n");
      refs = &gcHeap->nonCollectableRefs;
      op = refs->table;
      while ((uintptr_t)op < (uintptr_t)refs->nextEntry) {
          dvmMarkObjectNonNull(*(op++));
      }
  
      /* Mark any special objects we have sitting around.
       */
      LOG_SCAN("special objects\n");
      dvmMarkObjectNonNull(gDvm.outOfMemoryObj);
      dvmMarkObjectNonNull(gDvm.internalErrorObj);
  //TODO: scan object references sitting in gDvm;  use pointer begin & end
  
      HPROF_CLEAR_GC_SCAN_STATE();
  }
  
  /*
   * Nothing past this point is allowed to use dvmMarkObject*().
   * Scanning/recursion must use markObject*(), which takes the
   * finger into account.
   */
  #define dvmMarkObjectNonNull __dont_use_dvmMarkObjectNonNull__
  
  
  /* Mark all of a ClassObject's interfaces.
   */
  static void markInterfaces(const ClassObject *clazz, GcMarkContext *ctx)
  {
      ClassObject **interfaces;
      int interfaceCount;
      int i;
  
      /* Mark all interfaces.
       */
      interfaces = clazz->interfaces;
      interfaceCount = clazz->interfaceCount;
      for (i = 0; i < interfaceCount; i++) {
          markObjectNonNull((Object *)*interfaces, ctx);
          interfaces++;
      }
  }
  
  /* Mark all objects referred to by a ClassObject's static fields.
   */
  static void scanStaticFields(const ClassObject *clazz, GcMarkContext *ctx)
  {
      StaticField *f;
      int i;
  
      //TODO: Optimize this with a bit vector or something
      f = clazz->sfields;
      for (i = 0; i < clazz->sfieldCount; i++) {
          char c = f->field.signature[0];
          if (c == '[' || c == 'L') {
              /* It's an array or class reference.
               */
              markObject((Object *)f->value.l, ctx);
          }
          f++;
      }
  }
  
  /* Mark all objects referred to by a DataObject's instance fields.
   */
  static void scanInstanceFields(const DataObject *obj, ClassObject *clazz,
          GcMarkContext *ctx)
  {
  //TODO: Optimize this by avoiding walking the superclass chain
      while (clazz != NULL) {
          InstField *f;
          int i;
  
          /* All of the fields that contain object references
           * are guaranteed to be at the beginning of the ifields list.
           */
          f = clazz->ifields;
          for (i = 0; i < clazz->ifieldRefCount; i++) {
              /* Mark the array or object reference.
               * May be NULL.
               *
               * Note that, per the comment on struct InstField,
               * f->byteOffset is the offset from the beginning of
               * obj, not the offset into obj->instanceData.
               */
              markObject(dvmGetFieldObject((Object*)obj, f->byteOffset), ctx);
              f++;
          }
  
          /* This will be NULL when we hit java.lang.Object
           */
          clazz = clazz->super;
      }
  }
  
  /* Mark all objects referred to by the array's contents.
   */
  static void scanObjectArray(const ArrayObject *array, GcMarkContext *ctx)
  {
      Object **contents;
      u4 length;
      u4 i;
  
      contents = (Object **)array->contents;
      length = array->length;
  
      for (i = 0; i < length; i++) {
          markObject(*contents, ctx); // may be NULL
          contents++;
      }
  }
  
  /* Mark all objects referred to by the ClassObject.
   */
  static void scanClassObject(const ClassObject *clazz, GcMarkContext *ctx)
  {
      LOGV_SCAN("---------> %s\n", clazz->name);
  
      if (IS_CLASS_FLAG_SET(clazz, CLASS_ISARRAY)) {
          /* We're an array; mark the class object of the contents
           * of the array.
           *
           * Note that we won't necessarily reach the array's element
           * class by scanning the array contents;  the array may be
           * zero-length, or may only contain null objects.
           */
          markObjectNonNull((Object *)clazz->elementClass, ctx);
      }
  
      /* We scan these explicitly in case the only remaining
       * reference to a particular class object is via a data
       * object;  we may not be guaranteed to reach all
       * live class objects via a classloader.
       */
      markObject((Object *)clazz->super, ctx);  // may be NULL (java.lang.Object)
      markObject(clazz->classLoader, ctx);      // may be NULL
  
      scanStaticFields(clazz, ctx);
      markInterfaces(clazz, ctx);
  }
  
  /* Mark all objects that obj refers to.
   *
   * Called on every object in markList.
   */
  static void scanObject(const Object *obj, GcMarkContext *ctx)
  {
      ClassObject *clazz;
  
      assert(dvmIsValidObject(obj));
      LOGV_SCAN("0x%08x %s\n", (uint)obj, obj->clazz->name);
  
  #if WITH_HPROF
      if (gDvm.gcHeap->hprofContext != NULL) {
          hprofDumpHeapObject(gDvm.gcHeap->hprofContext, obj);
      }
  #endif
  
      /* Get and mark the class object for this particular instance.
       */
      clazz = obj->clazz;
      if (clazz == NULL) {
          /* This can happen if we catch an object between
           * dvmMalloc() and DVM_OBJECT_INIT().  The object
           * won't contain any references yet, so we can
           * just skip it.
           */
          return;
      } else if (clazz == gDvm.unlinkedJavaLangClass) {
          /* This class hasn't been linked yet.  We're guaranteed
           * that the object doesn't contain any references that
           * aren't already tracked, so we can skip scanning it.
           *
           * NOTE: unlinkedJavaLangClass is not on the heap, so
           * it's very important that we don't try marking it.
           */
          return;
      }
  #if WITH_OBJECT_HEADERS
      gMarkParent = obj;
      if (ptr2chunk(obj)->scanGeneration == gGeneration) {
          LOGE("object 0x%08x was already scanned this generation\n",
                  (uintptr_t)obj);
          dvmAbort();
      }
      ptr2chunk(obj)->oldScanGeneration = ptr2chunk(obj)->scanGeneration;
      ptr2chunk(obj)->scanGeneration = gGeneration;
      ptr2chunk(obj)->scanCount++;
  #endif
  
      assert(dvmIsValidObject((Object *)clazz));
      markObjectNonNull((Object *)clazz, ctx);
  
      /* Mark any references in this object.
       */
      if (IS_CLASS_FLAG_SET(clazz, CLASS_ISARRAY)) {
          /* It's an array object.
           */
          if (IS_CLASS_FLAG_SET(clazz, CLASS_ISOBJECTARRAY)) {
              /* It's an array of object references.
               */
              scanObjectArray((ArrayObject *)obj, ctx);
          }
          // else there's nothing else to scan
      } else {
          /* It's a DataObject-compatible object.
           */
          scanInstanceFields((DataObject *)obj, clazz, ctx);
  
          if (IS_CLASS_FLAG_SET(clazz, CLASS_ISREFERENCE)) {
              GcHeap *gcHeap = gDvm.gcHeap;
              Object *referent;
  
              /* It's a subclass of java/lang/ref/Reference.
               * The fields in this class have been arranged
               * such that scanInstanceFields() did not actually
               * mark the "referent" field;  we need to handle
               * it specially.
               *
               * If the referent already has a strong mark (isMarked(referent)),
               * we don't care about its reference status.
               */
              referent = dvmGetFieldObject(obj,
                      gDvm.offJavaLangRefReference_referent);
              if (referent != NULL &&
                      !isMarked(ptr2chunk(referent), &gcHeap->markContext))
              {
                  u4 refFlags;
  
                  if (gcHeap->markAllReferents) {
                      LOG_REF("Hard-marking a reference\n");
  
                      /* Don't bother with normal reference-following
                       * behavior, just mark the referent.  This should
                       * only be used when following objects that just
                       * became scheduled for finalization.
                       */
                      markObjectNonNull(referent, ctx);
                      goto skip_reference;
                  }
  
                  /* See if this reference was handled by a previous GC.
                   */
                  if (dvmGetFieldObject(obj,
                              gDvm.offJavaLangRefReference_vmData) ==
                          SCHEDULED_REFERENCE_MAGIC)
                  {
                      LOG_REF("Skipping scheduled reference\n");
  
                      /* Don't reschedule it, but make sure that its
                       * referent doesn't get collected (in case it's
                       * a PhantomReference and wasn't cleared automatically).
                       */
                      //TODO: Mark these after handling all new refs of
                      //      this strength, in case the new refs refer
                      //      to the same referent.  Not a very common
                      //      case, though.
                      markObjectNonNull(referent, ctx);
                      goto skip_reference;
                  }
  
                  /* Find out what kind of reference is pointing
                   * to referent.
                   */
                  refFlags = GET_CLASS_FLAG_GROUP(clazz,
                      CLASS_ISREFERENCE |
                      CLASS_ISWEAKREFERENCE |
                      CLASS_ISPHANTOMREFERENCE);
  
              /* We use the vmData field of Reference objects
               * as a next pointer in a singly-linked list.
               * That way, we don't need to allocate any memory
               * while we're doing a GC.
               */
  #define ADD_REF_TO_LIST(list, ref) \
              do { \
                  Object *ARTL_ref_ = (/*de-const*/Object *)(ref); \
                  dvmSetFieldObject(ARTL_ref_, \
                          gDvm.offJavaLangRefReference_vmData, list); \
                  list = ARTL_ref_; \
              } while (false)
  
                  /* At this stage, we just keep track of all of
                   * the live references that we've seen.  Later,
                   * we'll walk through each of these lists and
                   * deal with the referents.
                   */
                  if (refFlags == CLASS_ISREFERENCE) {
                      /* It's a soft reference.  Depending on the state,
                       * we'll attempt to collect all of them, some of
                       * them, or none of them.
                       */
                      if (gcHeap->softReferenceCollectionState ==
                              SR_COLLECT_NONE)
                      {
                  sr_collect_none:
                          markObjectNonNull(referent, ctx);
                      } else if (gcHeap->softReferenceCollectionState ==
                              SR_COLLECT_ALL)
                      {
                  sr_collect_all:
                          ADD_REF_TO_LIST(gcHeap->softReferences, obj);
                      } else {
                          /* We'll only try to collect half of the
                           * referents.
                           */
                          if (gcHeap->softReferenceColor++ & 1) {
                              goto sr_collect_none;
                          }
                          goto sr_collect_all;
                      }
                  } else {
                      /* It's a weak or phantom reference.
                       * Clearing CLASS_ISREFERENCE will reveal which.
                       */
                      refFlags &= ~CLASS_ISREFERENCE;
                      if (refFlags == CLASS_ISWEAKREFERENCE) {
                          ADD_REF_TO_LIST(gcHeap->weakReferences, obj);
                      } else if (refFlags == CLASS_ISPHANTOMREFERENCE) {
                          ADD_REF_TO_LIST(gcHeap->phantomReferences, obj);
                      } else {
                          assert(!"Unknown reference type");
                      }
                  }
  #undef ADD_REF_TO_LIST
              }
          }
  
      skip_reference:
          /* If this is a class object, mark various other things that
           * its internals point to.
           *
           * All class objects are instances of java.lang.Class,
           * including the java.lang.Class class object.
           */
          if (clazz == gDvm.classJavaLangClass) {
              scanClassObject((ClassObject *)obj, ctx);
          }
      }
  
  #if WITH_OBJECT_HEADERS
      gMarkParent = NULL;
  #endif
  }
  
  static void
  processMarkStack(GcMarkContext *ctx)
  {
      const Object **const base = ctx->stack.base;
  
      /* Scan anything that's on the mark stack.
       * We can't use the bitmaps anymore, so use
       * a finger that points past the end of them.
       */
      ctx->finger = (void *)ULONG_MAX;
      while (ctx->stack.top != base) {
          scanObject(*ctx->stack.top++, ctx);
      }
  }
  
  #ifndef NDEBUG
  static uintptr_t gLastFinger = 0;
  #endif
  
  static bool
  scanBitmapCallback(size_t numPtrs, void **ptrs, const void *finger, void *arg)
  {
      GcMarkContext *ctx = (GcMarkContext *)arg;
      size_t i;
  
  #ifndef NDEBUG
      assert((uintptr_t)finger >= gLastFinger);
      gLastFinger = (uintptr_t)finger;
  #endif
  
      ctx->finger = finger;
      for (i = 0; i < numPtrs; i++) {
          /* The pointers we're getting back are DvmHeapChunks,
           * not Objects.
           */
          scanObject(chunk2ptr(*ptrs++), ctx);
      }
  
      return true;
  }
  
  /* Given bitmaps with the root set marked, find and mark all
   * reachable objects.  When this returns, the entire set of
   * live objects will be marked and the mark stack will be empty.
   */
  void dvmHeapScanMarkedObjects()
  {
      GcMarkContext *ctx = &gDvm.gcHeap->markContext;
  
      assert(ctx->finger == NULL);
  
      /* The bitmaps currently have bits set for the root set.
       * Walk across the bitmaps and scan each object.
       */
  #ifndef NDEBUG
      gLastFinger = 0;
  #endif
      dvmHeapBitmapWalkList(ctx->bitmaps, ctx->numBitmaps,
              scanBitmapCallback, ctx);
  
      /* We've walked the mark bitmaps.  Scan anything that's
       * left on the mark stack.
       */
      processMarkStack(ctx);
  
      LOG_SCAN("done with marked objects\n");
  }
  
  /** @return true if we need to schedule a call to clear().
   */
  static bool clearReference(Object *reference)
  {
      /* This is what the default implementation of Reference.clear()
       * does.  We're required to clear all references to a given
       * referent atomically, so we can't pop in and out of interp
       * code each time.
       *
       * Also, someone may have subclassed one of the basic Reference
       * types, overriding clear().  We can't trust the clear()
       * implementation to call super.clear();  we cannot let clear()
       * resurrect the referent.  If we clear it here, we can safely
       * call any overriding implementations.
       */
      dvmSetFieldObject(reference,
              gDvm.offJavaLangRefReference_referent, NULL);
  
  #if FANCY_REFERENCE_SUBCLASS
      /* See if clear() has actually been overridden.  If so,
       * we need to schedule a call to it before calling enqueue().
       */
      if (reference->clazz->vtable[gDvm.voffJavaLangRefReference_clear]->clazz !=
              gDvm.classJavaLangRefReference)
      {
          /* clear() has been overridden;  return true to indicate
           * that we need to schedule a call to the real clear()
           * implementation.
           */
          return true;
      }
  #endif
  
      return false;
  }
  
  /** @return true if we need to schedule a call to enqueue().
   */
  static bool enqueueReference(Object *reference)
  {
  #if FANCY_REFERENCE_SUBCLASS
      /* See if this reference class has overridden enqueue();
       * if not, we can take a shortcut.
       */
      if (reference->clazz->vtable[gDvm.voffJavaLangRefReference_enqueue]->clazz
              == gDvm.classJavaLangRefReference)
  #endif
      {
          Object *queue = dvmGetFieldObject(reference,
                  gDvm.offJavaLangRefReference_queue);
          Object *queueNext = dvmGetFieldObject(reference,
                  gDvm.offJavaLangRefReference_queueNext);
          if (queue == NULL || queueNext != NULL) {
              /* There is no queue, or the reference has already
               * been enqueued.  The Reference.enqueue() method
               * will do nothing even if we call it.
               */
              return false;
          }
      }
  
      /* We need to call enqueue(), but if we called it from
       * here we'd probably deadlock.  Schedule a call.
       */
      return true;
  }
  
  /* All objects for stronger reference levels have been
   * marked before this is called.
   */
  void dvmHeapHandleReferences(Object *refListHead, enum RefType refType)
  {
      Object *reference;
      GcMarkContext *markContext = &gDvm.gcHeap->markContext;
      const int offVmData = gDvm.offJavaLangRefReference_vmData;
      const int offReferent = gDvm.offJavaLangRefReference_referent;
      bool workRequired = false;
  
  size_t numCleared = 0;
  size_t numEnqueued = 0;
      reference = refListHead;
      while (reference != NULL) {
          Object *next;
          Object *referent;
  
          /* Pull the interesting fields out of the Reference object.
           */
          next = dvmGetFieldObject(reference, offVmData);
          referent = dvmGetFieldObject(reference, offReferent);
  
          //TODO: when handling REF_PHANTOM, unlink any references
          //      that fail this initial if().  We need to re-walk
          //      the list, and it would be nice to avoid the extra
          //      work.
          if (referent != NULL && !isMarked(ptr2chunk(referent), markContext)) {
              bool schedClear, schedEnqueue;
  
              /* This is the strongest reference that refers to referent.
               * Do the right thing.
               */
              switch (refType) {
              case REF_SOFT:
              case REF_WEAK:
                  schedClear = clearReference(reference);
                  schedEnqueue = enqueueReference(reference);
                  break;
              case REF_PHANTOM:
                  /* PhantomReferences are not cleared automatically.
                   * Until someone clears it (or the reference itself
                   * is collected), the referent must remain alive.
                   *
                   * It's necessary to fully mark the referent because
                   * it will still be present during the next GC, and
                   * all objects that it points to must be valid.
                   * (The referent will be marked outside of this loop,
                   * after handing all references of this strength, in
                   * case multiple references point to the same object.)
                   */
                  schedClear = false;
  
                  /* A PhantomReference is only useful with a
                   * queue, but since it's possible to create one
                   * without a queue, we need to check.
                   */
                  schedEnqueue = enqueueReference(reference);
                  break;
              default:
                  assert(!"Bad reference type");
                  schedClear = false;
                  schedEnqueue = false;
                  break;
              }
  numCleared += schedClear ? 1 : 0;
  numEnqueued += schedEnqueue ? 1 : 0;
  
              if (schedClear || schedEnqueue) {
                  uintptr_t workBits;
  
                  /* Stuff the clear/enqueue bits in the bottom of
                   * the pointer.  Assumes that objects are 8-byte
                   * aligned.
                   *
                   * Note that we are adding the *Reference* (which
                   * is by definition already marked at this point) to
                   * this list; we're not adding the referent (which
                   * has already been cleared).
                   */
                  assert(((intptr_t)reference & 3) == 0);
                  assert(((WORKER_CLEAR | WORKER_ENQUEUE) & ~3) == 0);
                  workBits = (schedClear ? WORKER_CLEAR : 0) |
                             (schedEnqueue ? WORKER_ENQUEUE : 0);
                  if (!dvmHeapAddRefToLargeTable(
                          &gDvm.gcHeap->referenceOperations,
                          (Object *)((uintptr_t)reference | workBits)))
                  {
                      LOGE_HEAP("dvmMalloc(): no room for any more "
                              "reference operations\n");
                      dvmAbort();
                  }
                  workRequired = true;
              }
  
              if (refType != REF_PHANTOM) {
                  /* Let later GCs know not to reschedule this reference.
                   */
                  dvmSetFieldObject(reference, offVmData,
                          SCHEDULED_REFERENCE_MAGIC);
              } // else this is handled later for REF_PHANTOM
  
          } // else there was a stronger reference to the referent.
  
          reference = next;
      }
  #define refType2str(r) \
      ((r) == REF_SOFT ? "soft" : ( \
       (r) == REF_WEAK ? "weak" : ( \
       (r) == REF_PHANTOM ? "phantom" : "UNKNOWN" )))
  LOGD_HEAP("dvmHeapHandleReferences(): cleared %zd, enqueued %zd %s references\n", numCleared, numEnqueued, refType2str(refType));
  
      /* Walk though the reference list again, and mark any non-clear/marked
       * referents.  Only PhantomReferences can have non-clear referents
       * at this point.
       */
      if (refType == REF_PHANTOM) {
          bool scanRequired = false;
  
          HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_REFERENCE_CLEANUP, 0);
          reference = refListHead;
          while (reference != NULL) {
              Object *next;
              Object *referent;
  
              /* Pull the interesting fields out of the Reference object.
               */
              next = dvmGetFieldObject(reference, offVmData);
              referent = dvmGetFieldObject(reference, offReferent);
  
              if (referent != NULL && !isMarked(ptr2chunk(referent), markContext)) {
                  markObjectNonNull(referent, markContext);
                  scanRequired = true;
  
                  /* Let later GCs know not to reschedule this reference.
                   */
                  dvmSetFieldObject(reference, offVmData,
                          SCHEDULED_REFERENCE_MAGIC);
              }
  
              reference = next;
          }
          HPROF_CLEAR_GC_SCAN_STATE();
  
          if (scanRequired) {
              processMarkStack(markContext);
          }
      }
  
      if (workRequired) {
          dvmSignalHeapWorker(false);
      }
  }
  
  
  /* Find unreachable objects that need to be finalized,
   * and schedule them for finalization.
   */
  void dvmHeapScheduleFinalizations()
  {
      HeapRefTable newPendingRefs;
      LargeHeapRefTable *finRefs = gDvm.gcHeap->finalizableRefs;
      Object **ref;
      Object **lastRef;
      size_t totalPendCount;
      GcMarkContext *markContext = &gDvm.gcHeap->markContext;
  
      /*
       * All reachable objects have been marked.
       * Any unmarked finalizable objects need to be finalized.
       */
  
      /* Create a table that the new pending refs will
       * be added to.
       */
      if (!dvmHeapInitHeapRefTable(&newPendingRefs, 128)) {
          //TODO: mark all finalizable refs and hope that
          //      we can schedule them next time.  Watch out,
          //      because we may be expecting to free up space
          //      by calling finalizers.
          LOGE_GC("dvmHeapScheduleFinalizations(): no room for "
                  "pending finalizations\n");
          dvmAbort();
      }
  
      /* Walk through finalizableRefs and move any unmarked references
       * to the list of new pending refs.
       */
      totalPendCount = 0;
      while (finRefs != NULL) {
          Object **gapRef;
          size_t newPendCount = 0;
  
          gapRef = ref = finRefs->refs.table;
          lastRef = finRefs->refs.nextEntry;
          while (ref < lastRef) {
              DvmHeapChunk *hc;
  
              hc = ptr2chunk(*ref);
              if (!isMarked(hc, markContext)) {
                  if (!dvmHeapAddToHeapRefTable(&newPendingRefs, *ref)) {
                      //TODO: add the current table and allocate
                      //      a new, smaller one.
                      LOGE_GC("dvmHeapScheduleFinalizations(): "
                              "no room for any more pending finalizations: %zd\n",
                              dvmHeapNumHeapRefTableEntries(&newPendingRefs));
                      dvmAbort();
                  }
                  newPendCount++;
              } else {
                  /* This ref is marked, so will remain on finalizableRefs.
                   */
                  if (newPendCount > 0) {
                      /* Copy it up to fill the holes.
                       */
                      *gapRef++ = *ref;
                  } else {
                      /* No holes yet; don't bother copying.
                       */
                      gapRef++;
                  }
              }
              ref++;
          }
          finRefs->refs.nextEntry = gapRef;
          //TODO: if the table is empty when we're done, free it.
          totalPendCount += newPendCount;
          finRefs = finRefs->next;
      }
      LOGD_GC("dvmHeapScheduleFinalizations(): %zd finalizers triggered.\n",
              totalPendCount);
      if (totalPendCount == 0) {
          /* No objects required finalization.
           * Free the empty temporary table.
           */
          dvmClearReferenceTable(&newPendingRefs);
          return;
      }
  
      /* Add the new pending refs to the main list.
       */
      if (!dvmHeapAddTableToLargeTable(&gDvm.gcHeap->pendingFinalizationRefs,
                  &newPendingRefs))
      {
          LOGE_GC("dvmHeapScheduleFinalizations(): can't insert new "
                  "pending finalizations\n");
          dvmAbort();
      }
  
      //TODO: try compacting the main list with a memcpy loop
  
      /* Mark the refs we just moved;  we don't want them or their
       * children to get swept yet.
       */
      ref = newPendingRefs.table;
      lastRef = newPendingRefs.nextEntry;
      assert(ref < lastRef);
      HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_FINALIZING, 0);
      while (ref < lastRef) {
          markObjectNonNull(*ref, markContext);
          ref++;
      }
      HPROF_CLEAR_GC_SCAN_STATE();
  
      /* Set markAllReferents so that we don't collect referents whose
       * only references are in final-reachable objects.
       * TODO: eventually provide normal reference behavior by properly
       *       marking these references.
       */
      gDvm.gcHeap->markAllReferents = true;
      processMarkStack(markContext);
      gDvm.gcHeap->markAllReferents = false;
  
      dvmSignalHeapWorker(false);
  }
  
  void dvmHeapFinishMarkStep()
  {
      HeapBitmap *markBitmap;
      HeapBitmap objectBitmap;
      GcMarkContext *markContext;
  
      markContext = &gDvm.gcHeap->markContext;
  
      /* The sweep step freed every object that appeared in the
       * HeapSource bitmaps that didn't appear in the mark bitmaps.
       * The new state of the HeapSource is exactly the final
       * mark bitmaps, so swap them in.
       *
       * The old bitmaps will be swapped into the context so that
       * we can clean them up.
       */
      dvmHeapSourceReplaceObjectBitmaps(markContext->bitmaps,
              markContext->numBitmaps);
  
      /* Clean up the old HeapSource bitmaps and anything else associated
       * with the marking process.
       */
      dvmHeapBitmapDeleteList(markContext->bitmaps, markContext->numBitmaps);
      destroyMarkStack(&markContext->stack);
  
      memset(markContext, 0, sizeof(*markContext));
  }
  
  #if WITH_HPROF && WITH_HPROF_UNREACHABLE
  static bool
  hprofUnreachableBitmapCallback(size_t numPtrs, void **ptrs,
          const void *finger, void *arg)
  {
      hprof_context_t *hctx = (hprof_context_t *)arg;
      size_t i;
  
      for (i = 0; i < numPtrs; i++) {
          Object *obj;
  
          /* The pointers we're getting back are DvmHeapChunks, not
           * Objects.
           */
          obj = (Object *)chunk2ptr(*ptrs++);
  
          hprofMarkRootObject(hctx, obj, 0);
          hprofDumpHeapObject(hctx, obj);
      }
  
      return true;
  }
  
  static void
  hprofDumpUnmarkedObjects(const HeapBitmap markBitmaps[],
          const HeapBitmap objectBitmaps[], size_t numBitmaps)
  {
      hprof_context_t *hctx = gDvm.gcHeap->hprofContext;
      if (hctx == NULL) {
          return;
      }
  
      LOGI("hprof: dumping unreachable objects\n");
  
      HPROF_SET_GC_SCAN_STATE(HPROF_UNREACHABLE, 0);
  
      dvmHeapBitmapXorWalkLists(markBitmaps, objectBitmaps, numBitmaps,
              hprofUnreachableBitmapCallback, hctx);
  
      HPROF_CLEAR_GC_SCAN_STATE();
  }
  #endif
  
  static bool
  sweepBitmapCallback(size_t numPtrs, void **ptrs, const void *finger, void *arg)
  {
      const ClassObject *const classJavaLangClass = gDvm.classJavaLangClass;
      size_t i;
  
      for (i = 0; i < numPtrs; i++) {
          DvmHeapChunk *hc;
          Object *obj;
  
          /* The pointers we're getting back are DvmHeapChunks, not
           * Objects.
           */
          hc = (DvmHeapChunk *)*ptrs++;
          obj = (Object *)chunk2ptr(hc);
  
  #if WITH_OBJECT_HEADERS
          if (hc->markGeneration == gGeneration) {
              LOGE("sweeping marked object: 0x%08x\n", (uint)obj);
              dvmAbort();
          }
  #endif
  
          /* Free the monitor associated with the object.
           */
          dvmFreeObjectMonitor(obj);
  
          /* NOTE: Dereferencing clazz is dangerous.  If obj was the last
           * one to reference its class object, the class object could be
           * on the sweep list, and could already have been swept, leaving
           * us with a stale pointer.
           */
          LOGV_SWEEP("FREE: 0x%08x %s\n", (uint)obj, obj->clazz->name);
  
          /* This assumes that java.lang.Class will never go away.
           * If it can, and we were the last reference to it, it
           * could have already been swept.  However, even in that case,
           * gDvm.classJavaLangClass should still have a useful
           * value.
           */
          if (obj->clazz == classJavaLangClass) {
              LOGV_SWEEP("---------------> %s\n", ((ClassObject *)obj)->name);
              /* dvmFreeClassInnards() may have already been called,
               * but it's safe to call on the same ClassObject twice.
               */
              dvmFreeClassInnards((ClassObject *)obj);
          }
  
  #if 0
          /* Overwrite the to-be-freed object to make stale references
           * more obvious.
           */
          {
              int chunklen;
              ClassObject *clazz = obj->clazz;
  #if WITH_OBJECT_HEADERS
              DvmHeapChunk chunk = *hc;
              chunk.header = ~OBJECT_HEADER | 1;
  #endif
              chunklen = dvmHeapSourceChunkSize(hc);
              memset(hc, 0xa5, chunklen);
              obj->clazz = (ClassObject *)((uintptr_t)clazz ^ 0xffffffff);
  #if WITH_OBJECT_HEADERS
              *hc = chunk;
  #endif
          }
  #endif
  
  //TODO: provide a heapsource function that takes a list of pointers to free
  //      and call it outside of this loop.
          dvmHeapSourceFree(hc);
      }
  
      return true;
  }
  
  /* A function suitable for passing to dvmHashForeachRemove()
   * to clear out any unmarked objects.  Clears the low bits
   * of the pointer because the intern table may set them.
   */
  static int isUnmarkedObject(void *object)
  {
      return !isMarked(ptr2chunk((uintptr_t)object & ~(HB_OBJECT_ALIGNMENT-1)),
              &gDvm.gcHeap->markContext);
  }
  
  /* Walk through the list of objects that haven't been
   * marked and free them.
   */
  void
  dvmHeapSweepUnmarkedObjects(int *numFreed, size_t *sizeFreed)
  {
      const HeapBitmap *markBitmaps;
      const GcMarkContext *markContext;
      HeapBitmap objectBitmaps[HEAP_SOURCE_MAX_HEAP_COUNT];
      size_t origObjectsAllocated;
      size_t origBytesAllocated;
      size_t numBitmaps;
  
      /* All reachable objects have been marked.
       * Detach any unreachable interned strings before
       * we sweep.
       */
      dvmGcDetachDeadInternedStrings(isUnmarkedObject);
  
      /* Free any known objects that are not marked.
       */
      origObjectsAllocated = dvmHeapSourceGetValue(HS_OBJECTS_ALLOCATED, NULL, 0);
      origBytesAllocated = dvmHeapSourceGetValue(HS_BYTES_ALLOCATED, NULL, 0);
  
      markContext = &gDvm.gcHeap->markContext;
      markBitmaps = markContext->bitmaps;
      numBitmaps = dvmHeapSourceGetObjectBitmaps(objectBitmaps,
              HEAP_SOURCE_MAX_HEAP_COUNT);
  #ifndef NDEBUG
      if (numBitmaps != markContext->numBitmaps) {
          LOGE("heap bitmap count mismatch: %zd != %zd\n",
                  numBitmaps, markContext->numBitmaps);
          dvmAbort();
      }
  #endif
  
  #if WITH_HPROF && WITH_HPROF_UNREACHABLE
      hprofDumpUnmarkedObjects(markBitmaps, objectBitmaps, numBitmaps);
  #endif
  
      dvmHeapBitmapXorWalkLists(markBitmaps, objectBitmaps, numBitmaps,
              sweepBitmapCallback, NULL);
  
      *numFreed = origObjectsAllocated -
              dvmHeapSourceGetValue(HS_OBJECTS_ALLOCATED, NULL, 0);
      *sizeFreed = origBytesAllocated -
              dvmHeapSourceGetValue(HS_BYTES_ALLOCATED, NULL, 0);
  
  #ifdef WITH_PROFILER
      if (gDvm.allocProf.enabled) {
          gDvm.allocProf.freeCount += *numFreed;
          gDvm.allocProf.freeSize += *sizeFreed;
      }
  #endif
  }
  