vm/alloc/MarkSweep.c

/*
 * 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 "alloc/Visit.h"
#include <limits.h>     // for ULONG_MAX
#include <sys/mman.h>   // for madvise(), mmap()
#include <cutils/ashmem.h>
#include <errno.h>

#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

#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 ALIGN_UP_TO_PAGE_SIZE(p) \
    (((size_t)(p) + (SYSTEM_PAGE_SIZE - 1)) & ~(SYSTEM_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 void *obj, const GcMarkContext *ctx)
{
    return dvmHeapBitmapIsObjectBitSet(ctx->bitmap, obj);
}

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(GcMode mode)
{
    GcMarkContext *mc = &gDvm.gcHeap->markContext;

    if (!createMarkStack(&mc->stack)) {
        return false;
    }
    mc->finger = NULL;
    mc->immuneLimit = dvmHeapSourceGetImmuneLimit(mode);
    return true;
}

static long
setAndReturnMarkBit(GcMarkContext *ctx, const void *obj)
{
    return dvmHeapBitmapSetAndReturnObjectBit(ctx->bitmap, obj);
}

static void
markObjectNonNull(const Object *obj, GcMarkContext *ctx,
        bool checkFinger, bool forceStack)
{
    assert(ctx != NULL);
    assert(obj != NULL);
    assert(dvmIsValidObject(obj));

    if (obj < (Object *)ctx->immuneLimit) {
        assert(isMarked(obj, ctx));
        return;
    }
    if (!setAndReturnMarkBit(ctx, obj)) {
        /* This object was not previously marked.
         */
        if (forceStack || (checkFinger && (void *)obj < ctx->finger)) {
            /* This object will need to go on the mark stack.
             */
            MARK_STACK_PUSH(ctx->stack, obj);
        }

#if WITH_HPROF
        if (gDvm.gcHeap->hprofContext != NULL) {
            hprofMarkRootObject(gDvm.gcHeap->hprofContext, obj, 0);
        }
#endif
    }
}

/* 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 markObject(const Object *obj, GcMarkContext *ctx)
{
    if (obj != NULL) {
        markObjectNonNull(obj, ctx, true, 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().
 */
void
dvmMarkObjectNonNull(const Object *obj)
{
    assert(obj != NULL);
    markObjectNonNull(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()
{
    GcHeap *gcHeap = gDvm.gcHeap;

    HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_STICKY_CLASS, 0);

    LOG_SCAN("immune objects");
    dvmMarkImmuneObjects(gcHeap->markContext.immuneLimit);

    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);

    HPROF_SET_GC_SCAN_STATE(HPROF_ROOT_FINALIZING, 0);

    LOG_SCAN("pending finalizations\n");
    dvmHeapMarkLargeTableRefs(gcHeap->pendingFinalizationRefs);

    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 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() or
 * dvmMarkObjectNonNull(), which are for root-marking only.
 * Scanning/recursion must use markObject(), which takes the finger
 * into account.
 */
#undef dvmMarkObject
#define dvmMarkObject __dont_use_dvmMarkObject__
#define dvmMarkObjectNonNull __dont_use_dvmMarkObjectNonNull__

/*
 * Scans instance fields.
 */
static void scanInstanceFields(const Object *obj, GcMarkContext *ctx)
{
    assert(obj != NULL);
    assert(obj->clazz != NULL);
    assert(ctx != NULL);

    if (obj->clazz->refOffsets != CLASS_WALK_SUPER) {
        unsigned int refOffsets = obj->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 {
        ClassObject *clazz;
        int i;
        for (clazz = obj->clazz; clazz != NULL; clazz = clazz->super) {
            InstField *field = clazz->ifields;
            for (i = 0; i < clazz->ifieldRefCount; ++i, ++field) {
                void *addr = BYTE_OFFSET((Object *)obj, field->byteOffset);
                markObject(((JValue *)addr)->l, ctx);
            }
        }
    }
}

/*
 * Scans the header, static field references, and interface
 * pointers of a class object.
 */
static void scanClassObject(const ClassObject *obj, GcMarkContext *ctx)
{
    int i;

    assert(obj != NULL);
    assert(obj->obj.clazz == gDvm.classJavaLangClass);
    assert(ctx != NULL);

    markObject((Object *)obj->obj.clazz, ctx);
    if (IS_CLASS_FLAG_SET(obj, CLASS_ISARRAY)) {
        markObject((Object *)obj->elementClass, ctx);
    }
    /* Do super and the interfaces contain Objects and not dex idx values? */
    if (obj->status > CLASS_IDX) {
        markObject((Object *)obj->super, ctx);
    }
    markObject(obj->classLoader, ctx);
    /* Scan static field references. */
    for (i = 0; i < obj->sfieldCount; ++i) {
        char ch = obj->sfields[i].field.signature[0];
        if (ch == '[' || ch == 'L') {
            markObject(obj->sfields[i].value.l, ctx);
        }
    }
    /* Scan the instance fields. */
    scanInstanceFields((const Object *)obj, ctx);
    /* Scan interface references. */
    if (obj->status > CLASS_IDX) {
        for (i = 0; i < obj->interfaceCount; ++i) {
            markObject((Object *)obj->interfaces[i], ctx);
        }
    }
}

/*
 * Scans the header of all array objects.  If the array object is
 * specialized to a reference type, scans the array data as well.
 */
static void scanArrayObject(const ArrayObject *obj, GcMarkContext *ctx)
{
    size_t i;

    assert(obj != NULL);
    assert(obj->obj.clazz != NULL);
    assert(ctx != NULL);
    /* Scan the class object reference. */
    markObject((Object *)obj->obj.clazz, ctx);
    if (IS_CLASS_FLAG_SET(obj->obj.clazz, CLASS_ISOBJECTARRAY)) {
        /* Scan the array contents. */
        Object **contents = (Object **)obj->contents;
        for (i = 0; i < obj->length; ++i) {
            markObject(contents[i], ctx);
        }
    }
}

/*
 * Process the "referent" field in a java.lang.ref.Reference.  If the
 * referent has not yet been marked, put it on the appropriate list in
 * the gcHeap for later processing.
 */
static void delayReferenceReferent(Object *obj, GcMarkContext *ctx)
{
    assert(obj != NULL);
    assert(obj->clazz != NULL);
    assert(ctx != NULL);

    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(referent, ctx))
    {
        u4 refFlags;

        /* Find out what kind of reference is pointing
         * to referent.
         */
        refFlags = GET_CLASS_FLAG_GROUP(obj->clazz,
                                        CLASS_ISREFERENCE |
                                        CLASS_ISWEAKREFERENCE |
                                        CLASS_ISPHANTOMREFERENCE);

#define ADD_REF_TO_LIST(list, ref)                                      \
        do {                                                            \
            Object *ARTL_ref_ = ref;                                    \
            assert(dvmGetFieldObject(ARTL_ref_,                         \
                gDvm.offJavaLangRefReference_queueNext) == NULL);       \
            dvmSetFieldObject(ARTL_ref_,                                \
                gDvm.offJavaLangRefReference_queueNext, 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.
             */
            ADD_REF_TO_LIST(gcHeap->softReferences, obj);
        } 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
    }
}

/*
 * Scans the header and field references of a data object.
 */
static void scanDataObject(DataObject *obj, GcMarkContext *ctx)
{
    assert(obj != NULL);
    assert(obj->obj.clazz != NULL);
    assert(ctx != NULL);
    /* Scan the class object. */
    markObject((Object *)obj->obj.clazz, ctx);
    /* Scan the instance fields. */
    scanInstanceFields((const Object *)obj, ctx);
    if (IS_CLASS_FLAG_SET(obj->obj.clazz, CLASS_ISREFERENCE)) {
        delayReferenceReferent((Object *)obj, ctx);
    }
}

/*
 * Scans an object reference.  Determines the type of the reference
 * and dispatches to a specialized scanning routine.
 */
static void scanObject(const Object *obj, GcMarkContext *ctx)
{
    assert(obj != NULL);
    assert(ctx != NULL);
    assert(obj->clazz != NULL);
#if WITH_HPROF
    if (gDvm.gcHeap->hprofContext != NULL) {
        hprofDumpHeapObject(gDvm.gcHeap->hprofContext, obj);
    }
#endif
    /* Dispatch a type-specific scan routine. */
    if (obj->clazz == gDvm.classJavaLangClass) {
        scanClassObject((ClassObject *)obj, ctx);
    } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISARRAY)) {
        scanArrayObject((ArrayObject *)obj, ctx);
    } else {
        scanDataObject((DataObject *)obj, ctx);
    }
}

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++) {
        scanObject(*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(void)
{
    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
    dvmHeapBitmapWalk(ctx->bitmap, 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");
}

static void dirtyObjectVisitor(void *ptr, void *arg)
{
    markObject(*(Object **)ptr, (GcMarkContext *)arg);
}

/*
 * Callback applied to each gray object to blacken it.
 */
static bool dirtyObjectCallback(size_t numPtrs, void **ptrs,
                                const void *finger, void *arg)
{
    GcMarkContext *ctx;
    size_t i;

    ctx = (GcMarkContext *)arg;
    for (i = 0; i < numPtrs; ++i) {
        dvmVisitObject(dirtyObjectVisitor, ptrs[i], ctx);
    }
    return true;
}

/*
 * Re-mark dirtied objects.  Iterates through all blackened objects
 * looking for references to white objects.
 */
void dvmMarkDirtyObjects(void)
{
    HeapBitmap markBits[HEAP_SOURCE_MAX_HEAP_COUNT];
    HeapBitmap liveBits[HEAP_SOURCE_MAX_HEAP_COUNT];
    GcMarkContext *ctx;
    size_t numBitmaps;
    size_t i;

    ctx = &gDvm.gcHeap->markContext;
    /*
     * The finger must have been set to the maximum value to ensure
     * that gray objects will be pushed onto the mark stack.
     */
    assert(ctx->finger == (void *)ULONG_MAX);
    numBitmaps = dvmHeapSourceGetNumHeaps();
    dvmHeapSourceGetObjectBitmaps(liveBits, markBits, numBitmaps);
    for (i = 0; i < numBitmaps; i++) {
        dvmHeapBitmapWalk(&markBits[i], dirtyObjectCallback, ctx);
    }
    processMarkStack(ctx);
}

/** Clear the referent field.
 */
static void 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.
     *
     * We don't ever actaully call overriding implementations of
     * Reference.clear().
     */
    dvmSetFieldObject(reference,
            gDvm.offJavaLangRefReference_referent, NULL);
}

/*
 * Returns true if the reference was registered with a reference queue
 * and has not yet been enqueued.
 */
static bool isEnqueuable(const Object *reference)
{
    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;
}

/*
 * Schedules a reference to be appended to its reference queue.
 */
static void enqueueReference(Object *ref)
{
    assert(ref != NULL);
    assert(dvmGetFieldObject(ref, gDvm.offJavaLangRefReference_queue) != NULL);
    assert(dvmGetFieldObject(ref, gDvm.offJavaLangRefReference_queueNext) == NULL);
    if (!dvmHeapAddRefToLargeTable(&gDvm.gcHeap->referenceOperations, ref)) {
        LOGE_HEAP("enqueueReference(): no room for any more "
                  "reference operations\n");
        dvmAbort();
    }
}

/*
 * Walks the reference list marking any references subject to the
 * reference clearing policy.  References with a black referent are
 * removed from the list.  References with white referents biased
 * toward saving are blackened and also removed from the list.
 */
void dvmHandleSoftRefs(Object **list)
{
    GcMarkContext *markContext;
    Object *ref, *referent;
    Object *prev, *next;
    size_t referentOffset, queueNextOffset;
    unsigned counter;
    bool marked;

    markContext = &gDvm.gcHeap->markContext;
    queueNextOffset = gDvm.offJavaLangRefReference_queueNext;
    referentOffset = gDvm.offJavaLangRefReference_referent;
    counter = 0;
    prev = next = NULL;
    ref = *list;
    while (ref != NULL) {
        referent = dvmGetFieldObject(ref, referentOffset);
        next = dvmGetFieldObject(ref, queueNextOffset);
        assert(referent != NULL);
        marked = isMarked(referent, markContext);
        if (!marked && ((++counter) & 1)) {
            /* Referent is white and biased toward saving, mark it. */
            assert(referent != NULL);
            markObject(referent, markContext);
            marked = true;
        }
        if (marked) {
            /* Referent is black, unlink it. */
            if (prev != NULL) {
                dvmSetFieldObject(ref, queueNextOffset, NULL);
                dvmSetFieldObject(prev, queueNextOffset, next);
            }
        } else {
            /* Referent is white, skip over it. */
            prev = ref;
        }
        ref = next;
    }
    /*
     * Restart the mark with the newly black references added to the
     * root set.
     */
    processMarkStack(markContext);
}

/*
 * Walks the reference list and clears references with an unmarked
 * (white) referents.  Cleared references registered to a reference
 * queue are scheduled for appending by the heap worker thread.
 */
void dvmClearWhiteRefs(Object **list)
{
    GcMarkContext *markContext;
    Object *ref, *referent;
    size_t referentOffset, queueNextOffset;
    bool doSignal;

    markContext = &gDvm.gcHeap->markContext;
    queueNextOffset = gDvm.offJavaLangRefReference_queueNext;
    referentOffset = gDvm.offJavaLangRefReference_referent;
    doSignal = false;
    while (*list != NULL) {
        ref = *list;
        referent = dvmGetFieldObject(ref, referentOffset);
        *list = dvmGetFieldObject(ref, queueNextOffset);
        dvmSetFieldObject(ref, queueNextOffset, NULL);
        assert(referent != NULL);
        if (!isMarked(referent, markContext)) {
            /* Referent is "white", clear it. */
            clearReference(ref);
            if (isEnqueuable(ref)) {
                enqueueReference(ref);
                doSignal = true;
            }
        }
    }
    /*
     * If we cleared a reference with a reference queue we must notify
     * the heap worker to append the reference.
     */
    if (doSignal) {
        dvmSignalHeapWorker(false);
    }
    assert(*list == NULL);
}

/* 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)) {
        //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) {
            if (!isMarked(*ref, 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) {
        assert(*ref != NULL);
        markObject(*ref, markContext);
        ref++;
    }
    HPROF_CLEAR_GC_SCAN_STATE();
    processMarkStack(markContext);
    dvmSignalHeapWorker(false);
}

void dvmHeapFinishMarkStep()
{
    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.
     */
    dvmHeapSourceSwapBitmaps();

    /* Clean up everything else associated with the marking process.
     */
    destroyMarkStack(&markContext->stack);

    markContext->finger = NULL;
}

static bool
sweepBitmapCallback(size_t numPtrs, void **ptrs, const void *finger, void *arg)
{
    const ClassObject *const classJavaLangClass = gDvm.classJavaLangClass;
    const bool overwriteFree = gDvm.overwriteFree;
    size_t i;
    void **origPtrs = ptrs;

    for (i = 0; i < numPtrs; i++) {
        Object *obj;

        obj = (Object *)*ptrs++;

        /* 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) {
            /* dvmFreeClassInnards() may have already been called,
             * but it's safe to call on the same ClassObject twice.
             */
            dvmFreeClassInnards((ClassObject *)obj);
        }

        /* Overwrite the to-be-freed object to make stale references
         * more obvious.
         */
        if (overwriteFree) {
            int objlen;
            ClassObject *clazz = obj->clazz;
            objlen = dvmHeapSourceChunkSize(obj);
            memset(obj, 0xa5, objlen);
            obj->clazz = (ClassObject *)((uintptr_t)clazz ^ 0xffffffff);
        }
    }
    // TODO: dvmHeapSourceFreeList has a loop, just like the above
    // does. Consider collapsing the two loops to save overhead.
    dvmHeapSourceFreeList(numPtrs, origPtrs);

    return true;
}

/* Returns true if the given object is unmarked.  Ignores the low bits
 * of the pointer because the intern table may set them.
 */
static int isUnmarkedObject(void *object)
{
    return !isMarked((void *)((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(GcMode mode, int *numFreed, size_t *sizeFreed)
{
    HeapBitmap markBits[HEAP_SOURCE_MAX_HEAP_COUNT];
    HeapBitmap liveBits[HEAP_SOURCE_MAX_HEAP_COUNT];
    size_t origObjectsAllocated;
    size_t origBytesAllocated;
    size_t numBitmaps, numSweepBitmaps;
    size_t i;

    /* 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);

    dvmSweepMonitorList(&gDvm.monitorList, isUnmarkedObject);

    numBitmaps = dvmHeapSourceGetNumHeaps();
    dvmHeapSourceGetObjectBitmaps(liveBits, markBits, numBitmaps);
    if (mode == GC_PARTIAL) {
        numSweepBitmaps = 1;
        assert((uintptr_t)gDvm.gcHeap->markContext.immuneLimit == liveBits[0].base);
    } else {
        numSweepBitmaps = numBitmaps;
    }
    for (i = 0; i < numSweepBitmaps; i++) {
        dvmHeapBitmapXorWalk(&markBits[i], &liveBits[i],
                             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
}