/*
 * 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/clz.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>
#include <errno.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, err;

    /* 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*) /
            (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: %s\n",
            size, strerror(errno));
        return false;
    }
    limit = (const Object **)mmap(NULL, size, PROT_READ | PROT_WRITE,
            MAP_PRIVATE, fd, 0);
    err = errno;
    close(fd);
    if (limit == MAP_FAILED) {
        LOGE_GC("Could not mmap %d-byte ashmem mark stack: %s\n",
            size, strerror(err));
        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);
    dvmMarkObjectNonNull(gDvm.noClassDefFoundErrorObj);
//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)
{
    if (false && clazz->refOffsets != CLASS_WALK_SUPER) {
        unsigned int refOffsets = clazz->refOffsets;
        while (refOffsets != 0) {
            const int rshift = CLZ(refOffsets);
            refOffsets &= ~(CLASS_HIGH_BIT >> rshift);
            markObject(dvmGetFieldObject((Object*)obj,
                                         CLASS_OFFSET_FROM_CLZ(rshift)), ctx);
        }
    } else {
        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

#if WITH_OBJECT_HEADERS
    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

    /* 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;
#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;
    void **origPtrs = ptrs;

    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: dvmHeapSourceFreeList has a loop, just like the above
    // does. Consider collapsing the two loops to save overhead.
    dvmHeapSourceFreeList(numPtrs, origPtrs);

    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
}