xref: /dalvik/vm/alloc/Copying.cpp

/*
 * Copyright (C) 2009 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 <errno.h>
#include <limits.h>
#include <sys/mman.h>

#include "Dalvik.h"
#include "alloc/Heap.h"
#include "alloc/HeapBitmap.h"
#include "alloc/HeapInternal.h"
#include "alloc/HeapSource.h"
#include "alloc/Verify.h"

/*
 * A "mostly copying", generational, garbage collector.
 *
 * TODO: we allocate our own contiguous tract of page frames to back
 * object allocations.  To cooperate with other heaps active in the
 * virtual machine we need to move the responsibility of allocating
 * pages someplace outside of this code.
 *
 * The other major data structures that maintain the state of the heap
 * are the block space table and the block queue.
 *
 * The block space table records the state of a block.  We must track
 * whether a block is:
 *
 * - Free or allocated in some space.
 *
 * - If the block holds part of a large object allocation, whether the
 *   block is the initial or a continued block of the allocation.
 *
 * - Whether the block is pinned, that is to say whether at least one
 *   object in the block must remain stationary.  Only needed during a
 *   GC.
 *
 * - Which space the object belongs to.  At present this means
 *   from-space or to-space.
 *
 * The block queue is used during garbage collection.  Unlike Cheney's
 * algorithm, from-space and to-space are not contiguous.  Therefore,
 * one cannot maintain the state of the copy with just two pointers.
 * The block queue exists to thread lists of blocks from the various
 * spaces together.
 *
 * Additionally, we record the free space frontier of the heap, as
 * well as the address of the first object within a block, which is
 * required to copy objects following a large object (not currently
 * implemented).  This is stored in the heap source structure.  This
 * should be moved elsewhere to support in-line allocations from Java
 * threads.
 *
 * Allocation requests are satisfied by reserving storage from one or
 * more contiguous blocks.  Objects that are small enough to fit
 * inside a block are packed together within a block.  Objects that
 * are larger than a block are allocated from contiguous sequences of
 * blocks.  When half the available blocks are filled, a garbage
 * collection occurs.  We "flip" spaces (exchange from- and to-space),
 * copy live objects into to space, and perform pointer adjustment.
 *
 * Copying is made more complicated by the requirement that some
 * objects must not be moved.  This property is known as "pinning".
 * These objects must be dealt with specially.  We use Bartlett's
 * scheme; blocks containing such objects are grayed (promoted) at the
 * start of a garbage collection.  By virtue of this trick, tracing
 * from the roots proceeds as usual but all objects on those pages are
 * considered promoted and therefore not moved.
 *
 * TODO: there is sufficient information within the garbage collector
 * to implement Attardi's scheme for evacuating unpinned objects from
 * a page that is otherwise pinned.  This would eliminate false
 * retention caused by the large pinning granularity.
 *
 * We need a scheme for medium and large objects.  Ignore that for
 * now, we can return to this later.
 *
 * Eventually we need to worry about promoting objects out of the
 * copy-collected heap (tenuring) into a less volatile space.  Copying
 * may not always be the best policy for such spaces.  We should
 * consider a variant of mark, sweep, compact.
 *
 * The block scheme allows us to use VM page faults to maintain a
 * write barrier.  Consider having a special leaf state for a page.
 *
 * Bibliography:
 *
 * C. J. Cheney. 1970. A non-recursive list compacting
 * algorithm. CACM. 13-11 pp677--678.
 *
 * Joel F. Bartlett. 1988. Compacting Garbage Collection with
 * Ambiguous Roots. Digital Equipment Corporation.
 *
 * Joel F. Bartlett. 1989. Mostly-Copying Garbage Collection Picks Up
 * Generations and C++. Digital Equipment Corporation.
 *
 * G. May Yip. 1991. Incremental, Generational Mostly-Copying Garbage
 * Collection in Uncooperative Environments. Digital Equipment
 * Corporation.
 *
 * Giuseppe Attardi, Tito Flagella. 1994. A Customisable Memory
 * Management Framework. TR-94-010
 *
 * Giuseppe Attardi, Tito Flagella, Pietro Iglio. 1998. A customisable
 * memory management framework for C++. Software -- Practice and
 * Experience. 28(11), 1143-1183.
 *
 */

#define ARRAYSIZE(x) (sizeof(x) / sizeof(x[0]))

#if 0
#define LOG_ALLOC ALOGI
#define LOG_PIN ALOGI
#define LOG_PROM ALOGI
#define LOG_REF ALOGI
#define LOG_SCAV ALOGI
#define LOG_TRAN ALOGI
#define LOG_VER ALOGI
#else
#define LOG_ALLOC(...) ((void)0)
#define LOG_PIN(...) ((void)0)
#define LOG_PROM(...) ((void)0)
#define LOG_REF(...) ((void)0)
#define LOG_SCAV(...) ((void)0)
#define LOG_TRAN(...) ((void)0)
#define LOG_VER(...) ((void)0)
#endif

static void enqueueBlock(HeapSource *heapSource, size_t block);
static void scavengeReference(Object **obj);
static bool toSpaceContains(const void *addr);
static bool fromSpaceContains(const void *addr);
static size_t sumHeapBitmap(const HeapBitmap *bitmap);
static size_t objectSize(const Object *obj);
static void scavengeDataObject(Object *obj);
static void scavengeBlockQueue();

/*
 * We use 512-byte blocks.
 */
enum { BLOCK_SHIFT = 9 };
enum { BLOCK_SIZE = 1 << BLOCK_SHIFT };

/*
 * Space identifiers, stored into the blockSpace array.
 */
enum {
    BLOCK_FREE = 0,
    BLOCK_FROM_SPACE = 1,
    BLOCK_TO_SPACE = 2,
    BLOCK_CONTINUED = 7
};

/*
 * Alignment for all allocations, in bytes.
 */
enum { ALLOC_ALIGNMENT = 8 };

/*
 * Sentinel value for the queue end.
 */
#define QUEUE_TAIL (~(size_t)0)

struct HeapSource {

    /* The base address of backing store. */
    u1 *blockBase;

    /* Total number of blocks available for allocation. */
    size_t totalBlocks;
    size_t allocBlocks;

    /*
     * The scavenger work queue.  Implemented as an array of index
     * values into the queue.
     */
    size_t *blockQueue;

    /*
     * Base and limit blocks.  Basically the shifted start address of
     * the block.  We convert blocks to a relative number when
     * indexing in the block queue.  TODO: make the block queue base
     * relative rather than the index into the block queue.
     */
    size_t baseBlock, limitBlock;

    size_t queueHead;
    size_t queueTail;
    size_t queueSize;

    /* The space of the current block 0 (free), 1 or 2. */
    char *blockSpace;

    /* Start of free space in the current block. */
    u1 *allocPtr;
    /* Exclusive limit of free space in the current block. */
    u1 *allocLimit;

    HeapBitmap allocBits;

    /*
     * The starting size of the heap.  This value is the same as the
     * value provided to the -Xms flag.
     */
    size_t minimumSize;

    /*
     * The maximum size of the heap.  This value is the same as the
     * -Xmx flag.
     */
    size_t maximumSize;

    /*
     * The current, committed size of the heap.  At present, this is
     * equivalent to the maximumSize.
     */
    size_t currentSize;

    size_t bytesAllocated;
};

static unsigned long alignDown(unsigned long x, unsigned long n)
{
    return x & -n;
}

static unsigned long alignUp(unsigned long x, unsigned long n)
{
    return alignDown(x + (n - 1), n);
}

static void describeBlocks(const HeapSource *heapSource)
{
    for (size_t i = 0; i < heapSource->totalBlocks; ++i) {
        if ((i % 32) == 0) putchar('\n');
        printf("%d ", heapSource->blockSpace[i]);
    }
    putchar('\n');
}

/*
 * Virtual memory interface.
 */

static void *virtualAlloc(size_t length)
{
    int flags = MAP_PRIVATE | MAP_ANONYMOUS;
    int prot = PROT_READ | PROT_WRITE;
    void *addr = mmap(NULL, length, prot, flags, -1, 0);
    if (addr == MAP_FAILED) {
        LOGE_HEAP("mmap: %s", strerror(errno));
        addr = NULL;
    }
    return addr;
}

static void virtualFree(void *addr, size_t length)
{
    assert(addr != NULL);
    assert((uintptr_t)addr % SYSTEM_PAGE_SIZE == 0);
    int res = munmap(addr, length);
    if (res == -1) {
        LOGE_HEAP("munmap: %s", strerror(errno));
    }
}

#ifndef NDEBUG
static int isValidAddress(const HeapSource *heapSource, const u1 *addr)
{
    size_t block;

    block = (uintptr_t)addr >> BLOCK_SHIFT;
    return heapSource->baseBlock <= block &&
           heapSource->limitBlock > block;
}
#endif

/*
 * Iterate over the block map looking for a contiguous run of free
 * blocks.
 */
static void *allocateBlocks(HeapSource *heapSource, size_t blocks)
{
    size_t allocBlocks = heapSource->allocBlocks;
    size_t totalBlocks = heapSource->totalBlocks;
    /* Check underflow. */
    assert(blocks != 0);
    /* Check overflow. */
    if (allocBlocks + blocks > totalBlocks / 2) {
        return NULL;
    }
    /* Scan block map. */
    for (size_t i = 0; i < totalBlocks; ++i) {
        /* Check fit. */
        for (size_t j = 0; j < blocks; ++j) { /* runs over totalBlocks */
            if (heapSource->blockSpace[i+j] != BLOCK_FREE) {
                break;
            }
        }
        /* No fit? */
        if (j != blocks) {
            i += j;
            continue;
        }
        /* Fit, allocate. */
        heapSource->blockSpace[i] = BLOCK_TO_SPACE; /* why to-space? */
        for (size_t j = 1; j < blocks; ++j) {
            heapSource->blockSpace[i+j] = BLOCK_CONTINUED;
        }
        heapSource->allocBlocks += blocks;
        void *addr = &heapSource->blockBase[i*BLOCK_SIZE];
        memset(addr, 0, blocks*BLOCK_SIZE);
        /* Collecting? */
        if (heapSource->queueHead != QUEUE_TAIL) {
            LOG_ALLOC("allocateBlocks allocBlocks=%zu,block#=%zu", heapSource->allocBlocks, i);
            /*
             * This allocated was on behalf of the transporter when it
             * shaded a white object gray.  We enqueue the block so
             * the scavenger can further shade the gray objects black.
             */
            enqueueBlock(heapSource, i);
        }

        return addr;
    }
    /* Insufficient space, fail. */
    ALOGE("Insufficient space, %zu blocks, %zu blocks allocated and %zu bytes allocated",
         heapSource->totalBlocks,
         heapSource->allocBlocks,
         heapSource->bytesAllocated);
    return NULL;
}

/* Converts an absolute address to a relative block number. */
static size_t addressToBlock(const HeapSource *heapSource, const void *addr)
{
    assert(heapSource != NULL);
    assert(isValidAddress(heapSource, addr));
    return (((uintptr_t)addr) >> BLOCK_SHIFT) - heapSource->baseBlock;
}

/* Converts a relative block number to an absolute address. */
static u1 *blockToAddress(const HeapSource *heapSource, size_t block)
{
    u1 *addr;

    addr = (u1 *) (((uintptr_t) heapSource->baseBlock + block) * BLOCK_SIZE);
    assert(isValidAddress(heapSource, addr));
    return addr;
}

static void clearBlock(HeapSource *heapSource, size_t block)
{
    assert(heapSource != NULL);
    assert(block < heapSource->totalBlocks);
    u1 *addr = heapSource->blockBase + block*BLOCK_SIZE;
    memset(addr, 0xCC, BLOCK_SIZE);
    for (size_t i = 0; i < BLOCK_SIZE; i += 8) {
        dvmHeapBitmapClearObjectBit(&heapSource->allocBits, addr + i);
    }
}

static void clearFromSpace(HeapSource *heapSource)
{
    assert(heapSource != NULL);
    size_t i = 0;
    size_t count = 0;
    while (i < heapSource->totalBlocks) {
        if (heapSource->blockSpace[i] != BLOCK_FROM_SPACE) {
            ++i;
            continue;
        }
        heapSource->blockSpace[i] = BLOCK_FREE;
        clearBlock(heapSource, i);
        ++i;
        ++count;
        while (i < heapSource->totalBlocks &&
               heapSource->blockSpace[i] == BLOCK_CONTINUED) {
            heapSource->blockSpace[i] = BLOCK_FREE;
            clearBlock(heapSource, i);
            ++i;
            ++count;
        }
    }
    LOG_SCAV("freed %zu blocks (%zu bytes)", count, count*BLOCK_SIZE);
}

/*
 * Appends the given block to the block queue.  The block queue is
 * processed in-order by the scavenger.
 */
static void enqueueBlock(HeapSource *heapSource, size_t block)
{
    assert(heapSource != NULL);
    assert(block < heapSource->totalBlocks);
    if (heapSource->queueHead != QUEUE_TAIL) {
        heapSource->blockQueue[heapSource->queueTail] = block;
    } else {
        heapSource->queueHead = block;
    }
    heapSource->blockQueue[block] = QUEUE_TAIL;
    heapSource->queueTail = block;
    ++heapSource->queueSize;
}

/*
 * Grays all objects within the block corresponding to the given
 * address.
 */
static void promoteBlockByAddr(HeapSource *heapSource, const void *addr)
{
    size_t block;

    block = addressToBlock(heapSource, (const u1 *)addr);
    if (heapSource->blockSpace[block] != BLOCK_TO_SPACE) {
        // LOG_PROM("promoting block %zu %d @ %p", block, heapSource->blockSpace[block], obj);
        heapSource->blockSpace[block] = BLOCK_TO_SPACE;
        enqueueBlock(heapSource, block);
        /* TODO(cshapiro): count continued blocks?*/
        heapSource->allocBlocks += 1;
    } else {
        // LOG_PROM("NOT promoting block %zu %d @ %p", block, heapSource->blockSpace[block], obj);
    }
}

GcHeap *dvmHeapSourceStartup(size_t startSize, size_t absoluteMaxSize)
{
    GcHeap* gcHeap;
    HeapSource *heapSource;

    assert(startSize <= absoluteMaxSize);

    heapSource = calloc(1, sizeof(*heapSource));
    assert(heapSource != NULL);

    heapSource->minimumSize = alignUp(startSize, BLOCK_SIZE);
    heapSource->maximumSize = alignUp(absoluteMaxSize, BLOCK_SIZE);

    heapSource->currentSize = heapSource->maximumSize;

    /* Allocate underlying storage for blocks. */
    heapSource->blockBase = virtualAlloc(heapSource->maximumSize);
    assert(heapSource->blockBase != NULL);
    heapSource->baseBlock = (uintptr_t) heapSource->blockBase >> BLOCK_SHIFT;
    heapSource->limitBlock = ((uintptr_t) heapSource->blockBase + heapSource->maximumSize) >> BLOCK_SHIFT;

    heapSource->allocBlocks = 0;
    heapSource->totalBlocks = (heapSource->limitBlock - heapSource->baseBlock);

    assert(heapSource->totalBlocks = heapSource->maximumSize / BLOCK_SIZE);

    {
        size_t size = sizeof(heapSource->blockQueue[0]);
        heapSource->blockQueue = malloc(heapSource->totalBlocks*size);
        assert(heapSource->blockQueue != NULL);
        memset(heapSource->blockQueue, 0xCC, heapSource->totalBlocks*size);
        heapSource->queueHead = QUEUE_TAIL;
    }

    /* Byte indicating space residence or free status of block. */
    {
        size_t size = sizeof(heapSource->blockSpace[0]);
        heapSource->blockSpace = calloc(1, heapSource->totalBlocks*size);
        assert(heapSource->blockSpace != NULL);
    }

    dvmHeapBitmapInit(&heapSource->allocBits,
                      heapSource->blockBase,
                      heapSource->maximumSize,
                      "blockBase");

    /* Initialize allocation pointers. */
    heapSource->allocPtr = allocateBlocks(heapSource, 1);
    heapSource->allocLimit = heapSource->allocPtr + BLOCK_SIZE;

    gcHeap = calloc(1, sizeof(*gcHeap));
    assert(gcHeap != NULL);
    gcHeap->heapSource = heapSource;

    return gcHeap;
}

/*
 * Perform any required heap initializations after forking from the
 * zygote process.  This is a no-op for the time being.  Eventually
 * this will demarcate the shared region of the heap.
 */
bool dvmHeapSourceStartupAfterZygote()
{
    return true;
}

bool dvmHeapSourceStartupBeforeFork()
{
    assert(!"implemented");
    return false;
}

void dvmHeapSourceShutdown(GcHeap **gcHeap)
{
    if (*gcHeap == NULL || (*gcHeap)->heapSource == NULL)
        return;
    free((*gcHeap)->heapSource->blockQueue);
    free((*gcHeap)->heapSource->blockSpace);
    virtualFree((*gcHeap)->heapSource->blockBase,
                (*gcHeap)->heapSource->maximumSize);
    free((*gcHeap)->heapSource);
    (*gcHeap)->heapSource = NULL;
    free(*gcHeap);
    *gcHeap = NULL;
}

size_t dvmHeapSourceGetValue(HeapSourceValueSpec spec,
                             size_t perHeapStats[],
                             size_t arrayLen)
{
    HeapSource *heapSource;
    size_t value;

    heapSource = gDvm.gcHeap->heapSource;
    switch (spec) {
    case HS_FOOTPRINT:
        value = heapSource->maximumSize;
        break;
    case HS_ALLOWED_FOOTPRINT:
        value = heapSource->maximumSize;
        break;
    case HS_BYTES_ALLOCATED:
        value = heapSource->bytesAllocated;
        break;
    case HS_OBJECTS_ALLOCATED:
        value = sumHeapBitmap(&heapSource->allocBits);
        break;
    default:
        assert(!"implemented");
        value = 0;
    }
    if (perHeapStats) {
        *perHeapStats = value;
    }
    return value;
}

/*
 * Performs a shallow copy of the allocation bitmap into the given
 * vector of heap bitmaps.
 */
void dvmHeapSourceGetObjectBitmaps(HeapBitmap objBits[], HeapBitmap markBits[],
                                   size_t numHeaps)
{
    assert(!"implemented");
}

HeapBitmap *dvmHeapSourceGetLiveBits()
{
    return &gDvm.gcHeap->heapSource->allocBits;
}

/*
 * Allocate the specified number of bytes from the heap.  The
 * allocation cursor points into a block of free storage.  If the
 * given allocation fits in the remaining space of the block, we
 * advance the cursor and return a pointer to the free storage.  If
 * the allocation cannot fit in the current block but is smaller than
 * a block we request a new block and allocate from it instead.  If
 * the allocation is larger than a block we must allocate from a span
 * of contiguous blocks.
 */
void *dvmHeapSourceAlloc(size_t length)
{
    HeapSource *heapSource;
    unsigned char *addr;
    size_t aligned, available, blocks;

    heapSource = gDvm.gcHeap->heapSource;
    assert(heapSource != NULL);
    assert(heapSource->allocPtr != NULL);
    assert(heapSource->allocLimit != NULL);

    aligned = alignUp(length, ALLOC_ALIGNMENT);
    available = heapSource->allocLimit - heapSource->allocPtr;

    /* Try allocating inside the current block. */
    if (aligned <= available) {
        addr = heapSource->allocPtr;
        heapSource->allocPtr += aligned;
        heapSource->bytesAllocated += aligned;
        dvmHeapBitmapSetObjectBit(&heapSource->allocBits, addr);
        return addr;
    }

    /* Try allocating in a new block. */
    if (aligned <= BLOCK_SIZE) {
        addr =  allocateBlocks(heapSource, 1);
        if (addr != NULL) {
            heapSource->allocLimit = addr + BLOCK_SIZE;
            heapSource->allocPtr = addr + aligned;
            heapSource->bytesAllocated += aligned;
            dvmHeapBitmapSetObjectBit(&heapSource->allocBits, addr);
            /* TODO(cshapiro): pad out the current block. */
        }
        return addr;
    }

    /* Try allocating in a span of blocks. */
    blocks = alignUp(aligned, BLOCK_SIZE) / BLOCK_SIZE;

    addr = allocateBlocks(heapSource, blocks);
    /* Propagate failure upward. */
    if (addr != NULL) {
        heapSource->bytesAllocated += aligned;
        dvmHeapBitmapSetObjectBit(&heapSource->allocBits, addr);
        /* TODO(cshapiro): pad out free space in the last block. */
    }
    return addr;
}

void *dvmHeapSourceAllocAndGrow(size_t size)
{
    return dvmHeapSourceAlloc(size);
}

/* TODO: refactor along with dvmHeapSourceAlloc */
void *allocateGray(size_t size)
{
    HeapSource *heapSource;
    void *addr;
    size_t block;

    /* TODO: add a check that we are in a GC. */
    heapSource = gDvm.gcHeap->heapSource;
    addr = dvmHeapSourceAlloc(size);
    assert(addr != NULL);
    block = addressToBlock(heapSource, (const u1 *)addr);
    if (heapSource->queueHead == QUEUE_TAIL) {
        /*
         * Forcibly append the underlying block to the queue.  This
         * condition occurs when referents are transported following
         * the initial trace.
         */
        enqueueBlock(heapSource, block);
        LOG_PROM("forced promoting block %zu %d @ %p", block, heapSource->blockSpace[block], addr);
    }
    return addr;
}

bool dvmHeapSourceContainsAddress(const void *ptr)
{
    HeapSource *heapSource = gDvm.gcHeap->heapSource;
    return dvmHeapBitmapCoversAddress(&heapSource->allocBits, ptr);
}

/*
 * Returns true if the given address is within the heap and points to
 * the header of a live object.
 */
bool dvmHeapSourceContains(const void *addr)
{
    HeapSource *heapSource;
    HeapBitmap *bitmap;

    heapSource = gDvm.gcHeap->heapSource;
    bitmap = &heapSource->allocBits;
    if (!dvmHeapBitmapCoversAddress(bitmap, addr)) {
        return false;
    } else {
        return dvmHeapBitmapIsObjectBitSet(bitmap, addr);
    }
}

bool dvmHeapSourceGetPtrFlag(const void *ptr, HeapSourcePtrFlag flag)
{
    assert(!"implemented");
    return false;
}

size_t dvmHeapSourceChunkSize(const void *ptr)
{
    assert(!"implemented");
    return 0;
}

size_t dvmHeapSourceFootprint()
{
    assert(!"implemented");
    return 0;
}

/*
 * Returns the "ideal footprint" which appears to be the number of
 * bytes currently committed to the heap.  This starts out at the
 * start size of the heap and grows toward the maximum size.
 */
size_t dvmHeapSourceGetIdealFootprint()
{
    return gDvm.gcHeap->heapSource->currentSize;
}

float dvmGetTargetHeapUtilization()
{
    return 0.5f;
}

void dvmSetTargetHeapUtilization(float newTarget)
{
    assert(newTarget > 0.0f && newTarget < 1.0f);
}

/*
 * Expands the size of the heap after a collection.  At present we
 * commit the pages for maximum size of the heap so this routine is
 * just a no-op.  Eventually, we will either allocate or commit pages
 * on an as-need basis.
 */
void dvmHeapSourceGrowForUtilization()
{
    /* do nothing */
}

void dvmHeapSourceWalk(void(*callback)(void* start, void* end,
                                       size_t used_bytes, void* arg),
                       void *arg)
{
    assert(!"implemented");
}

size_t dvmHeapSourceGetNumHeaps()
{
    return 1;
}

bool dvmTrackExternalAllocation(size_t n)
{
    /* do nothing */
    return true;
}

void dvmTrackExternalFree(size_t n)
{
    /* do nothing */
}

size_t dvmGetExternalBytesAllocated()
{
    assert(!"implemented");
    return 0;
}

void dvmHeapSourceFlip()
{
    HeapSource *heapSource = gDvm.gcHeap->heapSource;

    /* Reset the block queue. */
    heapSource->allocBlocks = 0;
    heapSource->queueSize = 0;
    heapSource->queueHead = QUEUE_TAIL;

    /* TODO(cshapiro): pad the current (prev) block. */

    heapSource->allocPtr = NULL;
    heapSource->allocLimit = NULL;

    /* Whiten all allocated blocks. */
    for (size_t i = 0; i < heapSource->totalBlocks; ++i) {
        if (heapSource->blockSpace[i] == BLOCK_TO_SPACE) {
            heapSource->blockSpace[i] = BLOCK_FROM_SPACE;
        }
    }
}

static void room(size_t *alloc, size_t *avail, size_t *total)
{
    HeapSource *heapSource = gDvm.gcHeap->heapSource;
    *total = heapSource->totalBlocks*BLOCK_SIZE;
    *alloc = heapSource->allocBlocks*BLOCK_SIZE;
    *avail = *total - *alloc;
}

static bool isSpaceInternal(u1 *addr, int space)
{
    HeapSource *heapSource;
    u1 *base, *limit;
    size_t offset;
    char space2;

    heapSource = gDvm.gcHeap->heapSource;
    base = heapSource->blockBase;
    assert(addr >= base);
    limit = heapSource->blockBase + heapSource->maximumSize;
    assert(addr < limit);
    offset = addr - base;
    space2 = heapSource->blockSpace[offset >> BLOCK_SHIFT];
    return space == space2;
}

static bool fromSpaceContains(const void *addr)
{
    return isSpaceInternal((u1 *)addr, BLOCK_FROM_SPACE);
}

static bool toSpaceContains(const void *addr)
{
    return isSpaceInternal((u1 *)addr, BLOCK_TO_SPACE);
}

/*
 * Notifies the collector that the object at the given address must
 * remain stationary during the current collection.
 */
static void pinObject(const Object *obj)
{
    promoteBlockByAddr(gDvm.gcHeap->heapSource, obj);
}

static size_t sumHeapBitmap(const HeapBitmap *bitmap)
{
    size_t sum = 0;
    for (size_t i = 0; i < bitmap->bitsLen >> 2; ++i) {
        sum += CLZ(bitmap->bits[i]);
    }
    return sum;
}

/*
 * Miscellaneous functionality.
 */

static int isForward(const void *addr)
{
    return (uintptr_t)addr & 0x1;
}

static void setForward(const void *toObj, void *fromObj)
{
    *(unsigned long *)fromObj = (uintptr_t)toObj | 0x1;
}

static void* getForward(const void *fromObj)
{
    return (void *)((uintptr_t)fromObj & ~0x1);
}

/* Beware, uses the same encoding as a forwarding pointers! */
static int isPermanentString(const StringObject *obj) {
    return (uintptr_t)obj & 0x1;
}

static void* getPermanentString(const StringObject *obj)
{
    return (void *)((uintptr_t)obj & ~0x1);
}


/*
 * Scavenging and transporting routines follow.  A transporter grays
 * an object.  A scavenger blackens an object.  We define these
 * routines for each fundamental object type.  Dispatch is performed
 * in scavengeObject.
 */

/*
 * Class object scavenging.
 */
static void scavengeClassObject(ClassObject *obj)
{
    LOG_SCAV("scavengeClassObject(obj=%p)", obj);
    assert(obj != NULL);
    assert(obj->obj.clazz != NULL);
    assert(obj->obj.clazz->descriptor != NULL);
    assert(!strcmp(obj->obj.clazz->descriptor, "Ljava/lang/Class;"));
    assert(obj->descriptor != NULL);
    LOG_SCAV("scavengeClassObject: descriptor='%s',vtableCount=%zu",
             obj->descriptor, obj->vtableCount);
    /* Delegate class object and instance field scavenging. */
    scavengeDataObject((Object *)obj);
    /* Scavenge the array element class object. */
    if (IS_CLASS_FLAG_SET(obj, CLASS_ISARRAY)) {
        scavengeReference((Object **)(void *)&obj->elementClass);
    }
    /* Scavenge the superclass. */
    scavengeReference((Object **)(void *)&obj->super);
    /* Scavenge the class loader. */
    scavengeReference(&obj->classLoader);
    /* Scavenge static fields. */
    for (int i = 0; i < obj->sfieldCount; ++i) {
        char ch = obj->sfields[i].field.signature[0];
        if (ch == '[' || ch == 'L') {
            scavengeReference((Object **)(void *)&obj->sfields[i].value.l);
        }
    }
    /* Scavenge interface class objects. */
    for (int i = 0; i < obj->interfaceCount; ++i) {
        scavengeReference((Object **) &obj->interfaces[i]);
    }
}

/*
 * Array object scavenging.
 */
static size_t scavengeArrayObject(ArrayObject *array)
{
    LOG_SCAV("scavengeArrayObject(array=%p)", array);
    /* Scavenge the class object. */
    assert(toSpaceContains(array));
    assert(array != NULL);
    assert(array->obj.clazz != NULL);
    scavengeReference((Object **) array);
    size_t length = dvmArrayObjectSize(array);
    /* Scavenge the array contents. */
    if (IS_CLASS_FLAG_SET(array->obj.clazz, CLASS_ISOBJECTARRAY)) {
        Object **contents = (Object **)array->contents;
        for (size_t i = 0; i < array->length; ++i) {
            scavengeReference(&contents[i]);
        }
    }
    return length;
}

/*
 * Reference object scavenging.
 */

static int getReferenceFlags(const Object *obj)
{
    int flags;

    flags = CLASS_ISREFERENCE |
            CLASS_ISWEAKREFERENCE |
            CLASS_ISPHANTOMREFERENCE;
    return GET_CLASS_FLAG_GROUP(obj->clazz, flags);
}

static int isSoftReference(const Object *obj)
{
    return getReferenceFlags(obj) == CLASS_ISREFERENCE;
}

static int isWeakReference(const Object *obj)
{
    return getReferenceFlags(obj) & CLASS_ISWEAKREFERENCE;
}

#ifndef NDEBUG
static bool isPhantomReference(const Object *obj)
{
    return getReferenceFlags(obj) & CLASS_ISPHANTOMREFERENCE;
}
#endif

/*
 * Returns true if the reference was registered with a reference queue
 * but has not yet been appended to it.
 */
static bool isReferenceEnqueuable(const Object *ref)
{
    Object *queue, *queueNext;

    queue = dvmGetFieldObject(ref, gDvm.offJavaLangRefReference_queue);
    queueNext = dvmGetFieldObject(ref, 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)) {
        ALOGE("no room for any more reference operations");
        dvmAbort();
    }
}

/*
 * Sets the referent field of a reference object to NULL.
 */
static void clearReference(Object *obj)
{
    dvmSetFieldObject(obj, gDvm.offJavaLangRefReference_referent, NULL);
}

/*
 * Clears reference objects with white referents.
 */
void clearWhiteReferences(Object **list)
{
    size_t referentOffset, queueNextOffset;
    bool doSignal;

    queueNextOffset = gDvm.offJavaLangRefReference_queueNext;
    referentOffset = gDvm.offJavaLangRefReference_referent;
    doSignal = false;
    while (*list != NULL) {
        Object *ref = *list;
        JValue *field = dvmFieldPtr(ref, referentOffset);
        Object *referent = field->l;
        *list = dvmGetFieldObject(ref, queueNextOffset);
        dvmSetFieldObject(ref, queueNextOffset, NULL);
        assert(referent != NULL);
        if (isForward(referent->clazz)) {
            field->l = referent = getForward(referent->clazz);
            continue;
        }
        if (fromSpaceContains(referent)) {
            /* Referent is white, clear it. */
            clearReference(ref);
            if (isReferenceEnqueuable(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);
}

/*
 * Blackens referents subject to the soft reference preservation
 * policy.
 */
void preserveSoftReferences(Object **list)
{
    Object *ref;
    Object *prev, *next;
    size_t referentOffset, queueNextOffset;
    unsigned counter;
    bool white;

    queueNextOffset = gDvm.offJavaLangRefReference_queueNext;
    referentOffset = gDvm.offJavaLangRefReference_referent;
    counter = 0;
    prev = next = NULL;
    ref = *list;
    while (ref != NULL) {
        JValue *field = dvmFieldPtr(ref, referentOffset);
        Object *referent = field->l;
        next = dvmGetFieldObject(ref, queueNextOffset);
        assert(referent != NULL);
        if (isForward(referent->clazz)) {
            /* Referent is black. */
            field->l = referent = getForward(referent->clazz);
            white = false;
        } else {
            white = fromSpaceContains(referent);
        }
        if (!white && ((++counter) & 1)) {
            /* Referent is white and biased toward saving, gray it. */
            scavengeReference((Object **)(void *)&field->l);
            white = true;
        }
        if (white) {
            /* 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 trace with the newly gray references added to the
     * root set.
     */
    scavengeBlockQueue();
}

void processFinalizableReferences()
{
    HeapRefTable newPendingRefs;
    LargeHeapRefTable *finRefs = gDvm.gcHeap->finalizableRefs;
    Object **ref;
    Object **lastRef;
    size_t totalPendCount;

    /*
     * All strongly, reachable objects are black.
     * Any white 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.
        LOG_REF("no room for pending finalizations");
        dvmAbort();
    }

    /*
     * Walk through finalizableRefs and move any white 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 (fromSpaceContains(*ref)) {
                if (!dvmHeapAddToHeapRefTable(&newPendingRefs, *ref)) {
                    //TODO: add the current table and allocate
                    //      a new, smaller one.
                    LOG_REF("no room for any more pending finalizations: %zd",
                            dvmHeapNumHeapRefTableEntries(&newPendingRefs));
                    dvmAbort();
                }
                newPendCount++;
            } else {
                /* This ref is black, 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;
    }
    LOG_REF("%zd finalizers triggered.", 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))
    {
        LOG_REF("can't insert new pending finalizations");
        dvmAbort();
    }

    //TODO: try compacting the main list with a memcpy loop

    /* Blacken 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) {
        scavengeReference(ref);
        ref++;
    }
    HPROF_CLEAR_GC_SCAN_STATE();
    scavengeBlockQueue();
    dvmSignalHeapWorker(false);
}

/*
 * If a reference points to from-space and has been forwarded, we snap
 * the pointer to its new to-space address.  If the reference points
 * to an unforwarded from-space address we must enqueue the reference
 * for later processing.  TODO: implement proper reference processing
 * and move the referent scavenging elsewhere.
 */
static void scavengeReferenceObject(Object *obj)
{
    Object *referent;
    Object **queue;
    size_t referentOffset, queueNextOffset;

    assert(obj != NULL);
    LOG_SCAV("scavengeReferenceObject(obj=%p),'%s'", obj, obj->clazz->descriptor);
    scavengeDataObject(obj);
    referentOffset = gDvm.offJavaLangRefReference_referent;
    referent = dvmGetFieldObject(obj, referentOffset);
    if (referent == NULL || toSpaceContains(referent)) {
        return;
    }
    if (isSoftReference(obj)) {
        queue = &gDvm.gcHeap->softReferences;
    } else if (isWeakReference(obj)) {
        queue = &gDvm.gcHeap->weakReferences;
    } else {
        assert(isPhantomReference(obj));
        queue = &gDvm.gcHeap->phantomReferences;
    }
    queueNextOffset = gDvm.offJavaLangRefReference_queueNext;
    dvmSetFieldObject(obj, queueNextOffset, *queue);
    *queue = obj;
    LOG_SCAV("scavengeReferenceObject: enqueueing %p", obj);
}

/*
 * Data object scavenging.
 */
static void scavengeDataObject(Object *obj)
{
    // LOG_SCAV("scavengeDataObject(obj=%p)", obj);
    assert(obj != NULL);
    assert(obj->clazz != NULL);
    assert(obj->clazz->objectSize != 0);
    assert(toSpaceContains(obj));
    /* Scavenge the class object. */
    ClassObject *clazz = obj->clazz;
    scavengeReference((Object **) obj);
    /* Scavenge instance fields. */
    if (clazz->refOffsets != CLASS_WALK_SUPER) {
        size_t refOffsets = clazz->refOffsets;
        while (refOffsets != 0) {
            size_t rshift = CLZ(refOffsets);
            size_t offset = CLASS_OFFSET_FROM_CLZ(rshift);
            Object **ref = (Object **)((u1 *)obj + offset);
            scavengeReference(ref);
            refOffsets &= ~(CLASS_HIGH_BIT >> rshift);
        }
    } else {
        for (; clazz != NULL; clazz = clazz->super) {
            InstField *field = clazz->ifields;
            for (int i = 0; i < clazz->ifieldRefCount; ++i, ++field) {
                size_t offset = field->byteOffset;
                Object **ref = (Object **)((u1 *)obj + offset);
                scavengeReference(ref);
            }
        }
    }
}

static Object *transportObject(const Object *fromObj)
{
    Object *toObj;
    size_t allocSize, copySize;

    LOG_TRAN("transportObject(fromObj=%p) allocBlocks=%zu",
                  fromObj,
                  gDvm.gcHeap->heapSource->allocBlocks);
    assert(fromObj != NULL);
    assert(fromSpaceContains(fromObj));
    allocSize = copySize = objectSize(fromObj);
    if (LW_HASH_STATE(fromObj->lock) != LW_HASH_STATE_UNHASHED) {
        /*
         * The object has been hashed or hashed and moved.  We must
         * reserve an additional word for a hash code.
         */
        allocSize += sizeof(u4);
    }
    if (LW_HASH_STATE(fromObj->lock) == LW_HASH_STATE_HASHED_AND_MOVED) {
        /*
         * The object has its hash code allocated.  Ensure the hash
         * code is copied along with the instance data.
         */
        copySize += sizeof(u4);
    }
    /* TODO(cshapiro): don't copy, re-map large data objects. */
    assert(copySize <= allocSize);
    toObj = allocateGray(allocSize);
    assert(toObj != NULL);
    assert(toSpaceContains(toObj));
    memcpy(toObj, fromObj, copySize);
    if (LW_HASH_STATE(fromObj->lock) == LW_HASH_STATE_HASHED) {
        /*
         * The object has had its hash code exposed.  Append it to the
         * instance and set a bit so we know to look for it there.
         */
        *(u4 *)(((char *)toObj) + copySize) = (u4)fromObj >> 3;
        toObj->lock |= LW_HASH_STATE_HASHED_AND_MOVED << LW_HASH_STATE_SHIFT;
    }
    LOG_TRAN("transportObject: from %p/%zu to %p/%zu (%zu,%zu) %s",
             fromObj, addressToBlock(gDvm.gcHeap->heapSource,fromObj),
             toObj, addressToBlock(gDvm.gcHeap->heapSource,toObj),
             copySize, allocSize, copySize < allocSize ? "DIFFERENT" : "");
    return toObj;
}

/*
 * Generic reference scavenging.
 */

/*
 * Given a reference to an object, the scavenge routine will gray the
 * reference.  Any objects pointed to by the scavenger object will be
 * transported to new space and a forwarding pointer will be installed
 * in the header of the object.
 */

/*
 * Blacken the given pointer.  If the pointer is in from space, it is
 * transported to new space.  If the object has a forwarding pointer
 * installed it has already been transported and the referent is
 * snapped to the new address.
 */
static void scavengeReference(Object **obj)
{
    ClassObject *clazz;
    Object *fromObj, *toObj;

    assert(obj);

    if (*obj == NULL) return;

    assert(dvmIsValidObject(*obj));

    /* The entire block is black. */
    if (toSpaceContains(*obj)) {
        LOG_SCAV("scavengeReference skipping pinned object @ %p", *obj);
        return;
    }
    LOG_SCAV("scavengeReference(*obj=%p)", *obj);

    assert(fromSpaceContains(*obj));

    clazz = (*obj)->clazz;

    if (isForward(clazz)) {
        // LOG_SCAV("forwarding %p @ %p to %p", *obj, obj, (void *)((uintptr_t)clazz & ~0x1));
        *obj = (Object *)getForward(clazz);
        return;
    }
    fromObj = *obj;
    if (clazz == NULL) {
        // LOG_SCAV("scavangeReference %p has a NULL class object", fromObj);
        assert(!"implemented");
        toObj = NULL;
    } else {
        toObj = transportObject(fromObj);
    }
    setForward(toObj, fromObj);
    *obj = (Object *)toObj;
}

/*
 * Generic object scavenging.
 */
static void scavengeObject(Object *obj)
{
    ClassObject *clazz;

    assert(obj != NULL);
    assert(obj->clazz != NULL);
    assert(!((uintptr_t)obj->clazz & 0x1));
    clazz = obj->clazz;
    if (dvmIsTheClassClass(clazz)) {
        scavengeClassObject((ClassObject *)obj);
    } else if (IS_CLASS_FLAG_SET(clazz, CLASS_ISARRAY)) {
        scavengeArrayObject((ArrayObject *)obj);
    } else if (IS_CLASS_FLAG_SET(clazz, CLASS_ISREFERENCE)) {
        scavengeReferenceObject(obj);
    } else {
        scavengeDataObject(obj);
    }
}

/*
 * External root scavenging routines.
 */

static void pinHashTableEntries(HashTable *table)
{
    LOG_PIN(">>> pinHashTableEntries(table=%p)", table);
    if (table == NULL) {
        return;
    }
    dvmHashTableLock(table);
    for (int i = 0; i < table->tableSize; ++i) {
        HashEntry *entry = &table->pEntries[i];
        void *obj = entry->data;
        if (obj == NULL || obj == HASH_TOMBSTONE) {
            continue;
        }
        pinObject(entry->data);
    }
    dvmHashTableUnlock(table);
    LOG_PIN("<<< pinHashTableEntries(table=%p)", table);
}

static void pinPrimitiveClasses()
{
    size_t length = ARRAYSIZE(gDvm.primitiveClass);
    for (size_t i = 0; i < length; i++) {
        if (gDvm.primitiveClass[i] != NULL) {
            pinObject((Object *)gDvm.primitiveClass[i]);
        }
    }
}

/*
 * Scavenge interned strings.  Permanent interned strings will have
 * been pinned and are therefore ignored.  Non-permanent strings that
 * have been forwarded are snapped.  All other entries are removed.
 */
static void scavengeInternedStrings()
{
    HashTable *table = gDvm.internedStrings;
    if (table == NULL) {
        return;
    }
    dvmHashTableLock(table);
    for (int i = 0; i < table->tableSize; ++i) {
        HashEntry *entry = &table->pEntries[i];
        Object *obj = (Object *)entry->data;
        if (obj == NULL || obj == HASH_TOMBSTONE) {
            continue;
        } else if (!isPermanentString((StringObject *)obj)) {
            // LOG_SCAV("entry->data=%p", entry->data);
            LOG_SCAV(">>> string obj=%p", entry->data);
            /* TODO(cshapiro): detach white string objects */
            scavengeReference((Object **)(void *)&entry->data);
            LOG_SCAV("<<< string obj=%p", entry->data);
        }
    }
    dvmHashTableUnlock(table);
}

static void pinInternedStrings()
{
    HashTable *table = gDvm.internedStrings;
    if (table == NULL) {
        return;
    }
    dvmHashTableLock(table);
    for (int i = 0; i < table->tableSize; ++i) {
        HashEntry *entry = &table->pEntries[i];
        Object *obj = (Object *)entry->data;
        if (obj == NULL || obj == HASH_TOMBSTONE) {
            continue;
        } else if (isPermanentString((StringObject *)obj)) {
            obj = (Object *)getPermanentString((StringObject*)obj);
            LOG_PROM(">>> pin string obj=%p", obj);
            pinObject(obj);
            LOG_PROM("<<< pin string obj=%p", obj);
        }
     }
    dvmHashTableUnlock(table);
}

/*
 * At present, reference tables contain references that must not be
 * moved by the collector.  Instead of scavenging each reference in
 * the table we pin each referenced object.
 */
static void pinReferenceTable(const ReferenceTable *table)
{
    assert(table != NULL);
    assert(table->table != NULL);
    assert(table->nextEntry != NULL);
    for (Object **entry = table->table; entry < table->nextEntry; ++entry) {
        assert(entry != NULL);
        assert(!isForward(*entry));
        pinObject(*entry);
    }
}

static void scavengeLargeHeapRefTable(LargeHeapRefTable *table)
{
    for (; table != NULL; table = table->next) {
        Object **ref = table->refs.table;
        for (; ref < table->refs.nextEntry; ++ref) {
            scavengeReference(ref);
        }
    }
}

/* This code was copied from Thread.c */
static void scavengeThreadStack(Thread *thread)
{
    const u4 *framePtr;
#if WITH_EXTRA_GC_CHECKS > 1
    bool first = true;
#endif

    framePtr = (const u4 *)thread->interpSave.curFrame;
    while (framePtr != NULL) {
        const StackSaveArea *saveArea;
        const Method *method;

        saveArea = SAVEAREA_FROM_FP(framePtr);
        method = saveArea->method;
        if (method != NULL && !dvmIsNativeMethod(method)) {
#ifdef COUNT_PRECISE_METHODS
            /* the GC is running, so no lock required */
            if (dvmPointerSetAddEntry(gDvm.preciseMethods, method))
                LOG_SCAV("PGC: added %s.%s %p",
                             method->clazz->descriptor, method->name, method);
#endif
#if WITH_EXTRA_GC_CHECKS > 1
            /*
             * May also want to enable the memset() in the "invokeMethod"
             * goto target in the portable interpreter.  That sets the stack
             * to a pattern that makes referring to uninitialized data
             * very obvious.
             */

            if (first) {
                /*
                 * First frame, isn't native, check the "alternate" saved PC
                 * as a sanity check.
                 *
                 * It seems like we could check the second frame if the first
                 * is native, since the PCs should be the same.  It turns out
                 * this doesn't always work.  The problem is that we could
                 * have calls in the sequence:
                 *   interp method #2
                 *   native method
                 *   interp method #1
                 *
                 * and then GC while in the native method after returning
                 * from interp method #2.  The currentPc on the stack is
                 * for interp method #1, but thread->currentPc2 is still
                 * set for the last thing interp method #2 did.
                 *
                 * This can also happen in normal execution:
                 * - sget-object on not-yet-loaded class
                 * - class init updates currentPc2
                 * - static field init is handled by parsing annotations;
                 *   static String init requires creation of a String object,
                 *   which can cause a GC
                 *
                 * Essentially, any pattern that involves executing
                 * interpreted code and then causes an allocation without
                 * executing instructions in the original method will hit
                 * this.  These are rare enough that the test still has
                 * some value.
                 */
                if (saveArea->xtra.currentPc != thread->currentPc2) {
                    ALOGW("PGC: savedPC(%p) != current PC(%p), %s.%s ins=%p",
                        saveArea->xtra.currentPc, thread->currentPc2,
                        method->clazz->descriptor, method->name, method->insns);
                    if (saveArea->xtra.currentPc != NULL)
                        ALOGE("  pc inst = 0x%04x", *saveArea->xtra.currentPc);
                    if (thread->currentPc2 != NULL)
                        ALOGE("  pc2 inst = 0x%04x", *thread->currentPc2);
                    dvmDumpThread(thread, false);
                }
            } else {
                /*
                 * It's unusual, but not impossible, for a non-first frame
                 * to be at something other than a method invocation.  For
                 * example, if we do a new-instance on a nonexistent class,
                 * we'll have a lot of class loader activity on the stack
                 * above the frame with the "new" operation.  Could also
                 * happen while we initialize a Throwable when an instruction
                 * fails.
                 *
                 * So there's not much we can do here to verify the PC,
                 * except to verify that it's a GC point.
                 */
            }
            assert(saveArea->xtra.currentPc != NULL);
#endif

            const RegisterMap* pMap;
            const u1* regVector;

            Method* nonConstMethod = (Method*) method;  // quiet gcc
            pMap = dvmGetExpandedRegisterMap(nonConstMethod);

            //LOG_SCAV("PGC: %s.%s", method->clazz->descriptor, method->name);

            if (pMap != NULL) {
                /* found map, get registers for this address */
                int addr = saveArea->xtra.currentPc - method->insns;
                regVector = dvmRegisterMapGetLine(pMap, addr);
                /*
                if (regVector == NULL) {
                    LOG_SCAV("PGC: map but no entry for %s.%s addr=0x%04x",
                                 method->clazz->descriptor, method->name, addr);
                } else {
                    LOG_SCAV("PGC: found map for %s.%s 0x%04x (t=%d)",
                                 method->clazz->descriptor, method->name, addr,
                                 thread->threadId);
                }
                */
            } else {
                /*
                 * No map found.  If precise GC is disabled this is
                 * expected -- we don't create pointers to the map data even
                 * if it's present -- but if it's enabled it means we're
                 * unexpectedly falling back on a conservative scan, so it's
                 * worth yelling a little.
                 */
                if (gDvm.preciseGc) {
                    LOG_SCAV("PGC: no map for %s.%s", method->clazz->descriptor, method->name);
                }
                regVector = NULL;
            }
            if (regVector == NULL) {
                /*
                 * There are no roots to scavenge.  Skip over the entire frame.
                 */
                framePtr += method->registersSize;
            } else {
                /*
                 * Precise scan.  v0 is at the lowest address on the
                 * interpreted stack, and is the first bit in the register
                 * vector, so we can walk through the register map and
                 * memory in the same direction.
                 *
                 * A '1' bit indicates a live reference.
                 */
                u2 bits = 1 << 1;
                for (int i = method->registersSize - 1; i >= 0; i--) {
                    u4 rval = *framePtr;

                    bits >>= 1;
                    if (bits == 1) {
                        /* set bit 9 so we can tell when we're empty */
                        bits = *regVector++ | 0x0100;
                    }

                    if (rval != 0 && (bits & 0x01) != 0) {
                        /*
                         * Non-null, register marked as live reference.  This
                         * should always be a valid object.
                         */
#if WITH_EXTRA_GC_CHECKS > 0
                        if ((rval & 0x3) != 0 || !dvmIsValidObject((Object*) rval)) {
                            /* this is very bad */
                            ALOGE("PGC: invalid ref in reg %d: 0x%08x",
                                method->registersSize-1 - i, rval);
                        } else
#endif
                        {

                            // LOG_SCAV("stack reference %u@%p", *framePtr, framePtr);
                            /* dvmMarkObjectNonNull((Object *)rval); */
                            scavengeReference((Object **) framePtr);
                        }
                    } else {
                        /*
                         * Null or non-reference, do nothing at all.
                         */
#if WITH_EXTRA_GC_CHECKS > 1
                        if (dvmIsValidObject((Object*) rval)) {
                            /* this is normal, but we feel chatty */
                            ALOGD("PGC: ignoring valid ref in reg %d: 0x%08x",
                                 method->registersSize-1 - i, rval);
                        }
#endif
                    }
                    ++framePtr;
                }
                dvmReleaseRegisterMapLine(pMap, regVector);
            }
        }
        /* else this is a break frame and there is nothing to gray, or
         * this is a native method and the registers are just the "ins",
         * copied from various registers in the caller's set.
         */

#if WITH_EXTRA_GC_CHECKS > 1
        first = false;
#endif

        /* Don't fall into an infinite loop if things get corrupted.
         */
        assert((uintptr_t)saveArea->prevFrame > (uintptr_t)framePtr ||
               saveArea->prevFrame == NULL);
        framePtr = saveArea->prevFrame;
    }
}

static void scavengeThread(Thread *thread)
{
    // LOG_SCAV("scavengeThread(thread=%p)", thread);

    // LOG_SCAV("Scavenging threadObj=%p", thread->threadObj);
    scavengeReference(&thread->threadObj);

    // LOG_SCAV("Scavenging exception=%p", thread->exception);
    scavengeReference(&thread->exception);

    scavengeThreadStack(thread);
}

static void scavengeThreadList()
{
    Thread *thread;

    dvmLockThreadList(dvmThreadSelf());
    thread = gDvm.threadList;
    while (thread) {
        scavengeThread(thread);
        thread = thread->next;
    }
    dvmUnlockThreadList();
}

static void pinThreadStack(const Thread *thread)
{
    const u4 *framePtr;
    const StackSaveArea *saveArea;
    Method *method;
    const char *shorty;
    Object *obj;

    saveArea = NULL;
    framePtr = (const u4 *)thread->interpSave.curFrame;
    for (; framePtr != NULL; framePtr = saveArea->prevFrame) {
        saveArea = SAVEAREA_FROM_FP(framePtr);
        method = (Method *)saveArea->method;
        if (method != NULL && dvmIsNativeMethod(method)) {
            /*
             * This is native method, pin its arguments.
             *
             * For purposes of graying references, we don't need to do
             * anything here, because all of the native "ins" were copied
             * from registers in the caller's stack frame and won't be
             * changed (an interpreted method can freely use registers
             * with parameters like any other register, but natives don't
             * work that way).
             *
             * However, we need to ensure that references visible to
             * native methods don't move around.  We can do a precise scan
             * of the arguments by examining the method signature.
             */
            LOG_PIN("+++ native scan %s.%s",
                    method->clazz->descriptor, method->name);
            assert(method->registersSize == method->insSize);
            if (!dvmIsStaticMethod(method)) {
                /* grab the "this" pointer */
                obj = (Object *)*framePtr++;
                if (obj == NULL) {
                    /*
                     * This can happen for the "fake" entry frame inserted
                     * for threads created outside the VM.  There's no actual
                     * call so there's no object.  If we changed the fake
                     * entry method to be declared "static" then this
                     * situation should never occur.
                     */
                } else {
                    assert(dvmIsValidObject(obj));
                    pinObject(obj);
                }
            }
            shorty = method->shorty+1;      // skip return value
            for (int i = method->registersSize - 1; i >= 0; i--, framePtr++) {
                switch (*shorty++) {
                case 'L':
                    obj = (Object *)*framePtr;
                    if (obj != NULL) {
                        assert(dvmIsValidObject(obj));
                        pinObject(obj);
                    }
                    break;
                case 'D':
                case 'J':
                    framePtr++;
                    break;
                default:
                    /* 32-bit non-reference value */
                    obj = (Object *)*framePtr;          // debug, remove
                    if (dvmIsValidObject(obj)) {        // debug, remove
                        /* if we see a lot of these, our scan might be off */
                        LOG_PIN("+++ did NOT pin obj %p", obj);
                    }
                    break;
                }
            }
        } else if (method != NULL && !dvmIsNativeMethod(method)) {
            const RegisterMap* pMap = dvmGetExpandedRegisterMap(method);
            const u1* regVector = NULL;

            ALOGI("conservative : %s.%s", method->clazz->descriptor, method->name);

            if (pMap != NULL) {
                int addr = saveArea->xtra.currentPc - method->insns;
                regVector = dvmRegisterMapGetLine(pMap, addr);
            }
            if (regVector == NULL) {
                /*
                 * No register info for this frame, conservatively pin.
                 */
                for (int i = 0; i < method->registersSize; ++i) {
                    u4 regValue = framePtr[i];
                    if (regValue != 0 && (regValue & 0x3) == 0 && dvmIsValidObject((Object *)regValue)) {
                        pinObject((Object *)regValue);
                    }
                }
            }
        }
        /*
         * Don't fall into an infinite loop if things get corrupted.
         */
        assert((uintptr_t)saveArea->prevFrame > (uintptr_t)framePtr ||
               saveArea->prevFrame == NULL);
    }
}

static void pinThread(const Thread *thread)
{
    assert(thread != NULL);
    LOG_PIN("pinThread(thread=%p)", thread);

    LOG_PIN("Pin native method arguments");
    pinThreadStack(thread);

    LOG_PIN("Pin internalLocalRefTable");
    pinReferenceTable(&thread->internalLocalRefTable);

    LOG_PIN("Pin jniLocalRefTable");
    pinReferenceTable(&thread->jniLocalRefTable);

    /* Can the check be pushed into the promote routine? */
    if (thread->jniMonitorRefTable.table) {
        LOG_PIN("Pin jniMonitorRefTable");
        pinReferenceTable(&thread->jniMonitorRefTable);
    }
}

static void pinThreadList()
{
    Thread *thread;

    dvmLockThreadList(dvmThreadSelf());
    thread = gDvm.threadList;
    while (thread) {
        pinThread(thread);
        thread = thread->next;
    }
    dvmUnlockThreadList();
}

/*
 * Heap block scavenging.
 */

/*
 * Scavenge objects in the current block.  Scavenging terminates when
 * the pointer reaches the highest address in the block or when a run
 * of zero words that continues to the highest address is reached.
 */
static void scavengeBlock(HeapSource *heapSource, size_t block)
{
    u1 *cursor;
    u1 *end;
    size_t size;

    LOG_SCAV("scavengeBlock(heapSource=%p,block=%zu)", heapSource, block);

    assert(heapSource != NULL);
    assert(block < heapSource->totalBlocks);
    assert(heapSource->blockSpace[block] == BLOCK_TO_SPACE);

    cursor = blockToAddress(heapSource, block);
    end = cursor + BLOCK_SIZE;
    LOG_SCAV("scavengeBlock start=%p, end=%p", cursor, end);

    /* Parse and scavenge the current block. */
    size = 0;
    while (cursor < end) {
        u4 word = *(u4 *)cursor;
        if (word != 0) {
            scavengeObject((Object *)cursor);
            size = objectSize((Object *)cursor);
            size = alignUp(size, ALLOC_ALIGNMENT);
            cursor += size;
        } else {
            /* Check for padding. */
            while (*(u4 *)cursor == 0) {
                cursor += 4;
                if (cursor == end) break;
            }
            /* Punt if something went wrong. */
            assert(cursor == end);
        }
    }
}

static size_t objectSize(const Object *obj)
{
    size_t size;

    assert(obj != NULL);
    assert(obj->clazz != NULL);
    if (obj->clazz == gDvm.classJavaLangClass) {
        size = dvmClassObjectSize((ClassObject *)obj);
    } else if (IS_CLASS_FLAG_SET(obj->clazz, CLASS_ISARRAY)) {
        size = dvmArrayObjectSize((ArrayObject *)obj);
    } else {
        assert(obj->clazz->objectSize != 0);
        size = obj->clazz->objectSize;
    }
    if (LW_HASH_STATE(obj->lock) == LW_HASH_STATE_HASHED_AND_MOVED) {
        size += sizeof(u4);
    }
    return size;
}

static void verifyBlock(HeapSource *heapSource, size_t block)
{
    u1 *cursor;
    u1 *end;
    size_t size;

    // LOG_VER("verifyBlock(heapSource=%p,block=%zu)", heapSource, block);

    assert(heapSource != NULL);
    assert(block < heapSource->totalBlocks);
    assert(heapSource->blockSpace[block] == BLOCK_TO_SPACE);

    cursor = blockToAddress(heapSource, block);
    end = cursor + BLOCK_SIZE;
    // LOG_VER("verifyBlock start=%p, end=%p", cursor, end);

    /* Parse and scavenge the current block. */
    size = 0;
    while (cursor < end) {
        u4 word = *(u4 *)cursor;
        if (word != 0) {
            dvmVerifyObject((Object *)cursor);
            size = objectSize((Object *)cursor);
            size = alignUp(size, ALLOC_ALIGNMENT);
            cursor += size;
        } else {
            /* Check for padding. */
            while (*(unsigned long *)cursor == 0) {
                cursor += 4;
                if (cursor == end) break;
            }
            /* Punt if something went wrong. */
            assert(cursor == end);
        }
    }
}

static void describeBlockQueue(const HeapSource *heapSource)
{
    size_t block, count;
    char space;

    block = heapSource->queueHead;
    count = 0;
    LOG_SCAV(">>> describeBlockQueue(heapSource=%p)", heapSource);
    /* Count the number of blocks enqueued. */
    while (block != QUEUE_TAIL) {
        block = heapSource->blockQueue[block];
        ++count;
    }
    LOG_SCAV("blockQueue %zu elements, enqueued %zu",
                 count, heapSource->queueSize);
    block = heapSource->queueHead;
    while (block != QUEUE_TAIL) {
        space = heapSource->blockSpace[block];
        LOG_SCAV("block=%zu@%p,space=%zu", block, blockToAddress(heapSource,block), space);
        block = heapSource->blockQueue[block];
    }

    LOG_SCAV("<<< describeBlockQueue(heapSource=%p)", heapSource);
}

/*
 * Blackens promoted objects.
 */
static void scavengeBlockQueue()
{
    HeapSource *heapSource;
    size_t block;

    LOG_SCAV(">>> scavengeBlockQueue()");
    heapSource = gDvm.gcHeap->heapSource;
    describeBlockQueue(heapSource);
    while (heapSource->queueHead != QUEUE_TAIL) {
        block = heapSource->queueHead;
        LOG_SCAV("Dequeueing block %zu", block);
        scavengeBlock(heapSource, block);
        heapSource->queueHead = heapSource->blockQueue[block];
        LOG_SCAV("New queue head is %zu", heapSource->queueHead);
    }
    LOG_SCAV("<<< scavengeBlockQueue()");
}

/*
 * Scan the block list and verify all blocks that are marked as being
 * in new space.  This should be parametrized so we can invoke this
 * routine outside of the context of a collection.
 */
static void verifyNewSpace()
{
    HeapSource *heapSource = gDvm.gcHeap->heapSource;
    size_t c0 = 0, c1 = 0, c2 = 0, c7 = 0;
    for (size_t i = 0; i < heapSource->totalBlocks; ++i) {
        switch (heapSource->blockSpace[i]) {
        case BLOCK_FREE: ++c0; break;
        case BLOCK_TO_SPACE: ++c1; break;
        case BLOCK_FROM_SPACE: ++c2; break;
        case BLOCK_CONTINUED: ++c7; break;
        default: assert(!"reached");
        }
    }
    LOG_VER("Block Demographics: "
            "Free=%zu,ToSpace=%zu,FromSpace=%zu,Continued=%zu",
            c0, c1, c2, c7);
    for (size_t i = 0; i < heapSource->totalBlocks; ++i) {
        if (heapSource->blockSpace[i] != BLOCK_TO_SPACE) {
            continue;
        }
        verifyBlock(heapSource, i);
    }
}

void describeHeap()
{
    HeapSource *heapSource = gDvm.gcHeap->heapSource;
    describeBlocks(heapSource);
}

/*
 * The collection interface.  Collection has a few distinct phases.
 * The first is flipping AKA condemning AKA whitening the heap.  The
 * second is to promote all objects which are pointed to by pinned or
 * ambiguous references.  The third phase is tracing from the stacks,
 * registers and various globals.  Lastly, a verification of the heap
 * is performed.  The last phase should be optional.
 */
void dvmScavengeRoots()  /* Needs a new name badly */
{
    GcHeap *gcHeap;

    {
        size_t alloc, unused, total;

        room(&alloc, &unused, &total);
        LOG_SCAV("BEFORE GC: %zu alloc, %zu free, %zu total.",
                     alloc, unused, total);
    }

    gcHeap = gDvm.gcHeap;
    dvmHeapSourceFlip();

    /*
     * Promote blocks with stationary objects.
     */
    pinThreadList();
    pinReferenceTable(&gDvm.jniGlobalRefTable);
    pinReferenceTable(&gDvm.jniPinRefTable);
    pinHashTableEntries(gDvm.loadedClasses);
    pinHashTableEntries(gDvm.dbgRegistry);
    pinPrimitiveClasses();
    pinInternedStrings();

    // describeBlocks(gcHeap->heapSource);

    /*
     * Create first, open new-space page right here.
     */

    /* Reset allocation to an unallocated block. */
    gDvm.gcHeap->heapSource->allocPtr = allocateBlocks(gDvm.gcHeap->heapSource, 1);
    gDvm.gcHeap->heapSource->allocLimit = gDvm.gcHeap->heapSource->allocPtr + BLOCK_SIZE;
    /*
     * Hack: promote the empty block allocated above.  If the
     * promotions that occurred above did not actually gray any
     * objects, the block queue may be empty.  We must force a
     * promotion to be safe.
     */
    promoteBlockByAddr(gDvm.gcHeap->heapSource, gDvm.gcHeap->heapSource->allocPtr);

    /*
     * Scavenge blocks and relocate movable objects.
     */

    LOG_SCAV("Scavenging gDvm.threadList");
    scavengeThreadList();

    LOG_SCAV("Scavenging gDvm.gcHeap->referenceOperations");
    scavengeLargeHeapRefTable(gcHeap->referenceOperations);

    LOG_SCAV("Scavenging gDvm.gcHeap->pendingFinalizationRefs");
    scavengeLargeHeapRefTable(gcHeap->pendingFinalizationRefs);

    LOG_SCAV("Scavenging random global stuff");
    scavengeReference(&gDvm.outOfMemoryObj);
    scavengeReference(&gDvm.internalErrorObj);
    scavengeReference(&gDvm.noClassDefFoundErrorObj);

    // LOG_SCAV("Scavenging gDvm.internedString");
    scavengeInternedStrings();

    LOG_SCAV("Root scavenge has completed.");

    scavengeBlockQueue();

    // LOG_SCAV("Re-snap global class pointers.");
    // scavengeGlobals();

    LOG_SCAV("New space scavenge has completed.");

    /*
     * Process reference objects in strength order.
     */

    LOG_REF("Processing soft references...");
    preserveSoftReferences(&gDvm.gcHeap->softReferences);
    clearWhiteReferences(&gDvm.gcHeap->softReferences);

    LOG_REF("Processing weak references...");
    clearWhiteReferences(&gDvm.gcHeap->weakReferences);

    LOG_REF("Finding finalizations...");
    processFinalizableReferences();

    LOG_REF("Processing f-reachable soft references...");
    clearWhiteReferences(&gDvm.gcHeap->softReferences);

    LOG_REF("Processing f-reachable weak references...");
    clearWhiteReferences(&gDvm.gcHeap->weakReferences);

    LOG_REF("Processing phantom references...");
    clearWhiteReferences(&gDvm.gcHeap->phantomReferences);

    /*
     * Verify the stack and heap.
     */
    dvmVerifyRoots();
    verifyNewSpace();

    //describeBlocks(gcHeap->heapSource);

    clearFromSpace(gcHeap->heapSource);

    {
        size_t alloc, rem, total;

        room(&alloc, &rem, &total);
        LOG_SCAV("AFTER GC: %zu alloc, %zu free, %zu total.", alloc, rem, total);
    }
}

/*
 * Interface compatibility routines.
 */

void dvmClearWhiteRefs(Object **list)
{
    /* do nothing */
    assert(*list == NULL);
}

void dvmHandleSoftRefs(Object **list)
{
    /* do nothing */
    assert(*list == NULL);
}

bool dvmHeapBeginMarkStep(GcMode mode)
{
    /* do nothing */
    return true;
}

void dvmHeapFinishMarkStep()
{
    /* do nothing */
}

void dvmHeapMarkRootSet()
{
    /* do nothing */
}

void dvmHeapScanMarkedObjects()
{
    dvmScavengeRoots();
}

void dvmHeapScheduleFinalizations()
{
    /* do nothing */
}

void dvmHeapSweepUnmarkedObjects(GcMode mode, int *numFreed, size_t *sizeFreed)
{
    *numFreed = 0;
    *sizeFreed = 0;
    /* do nothing */
}

void dvmMarkDirtyObjects()
{
    assert(!"implemented");
}

void dvmHeapSourceThreadShutdown()
{
    /* do nothing */
}