collector.c

已经移植好的java虚拟机

}

/*=========================================================================
 * FUNCTION:      getDeferredObject
 * TYPE:          scanning the heap
 * OVERVIEW:      Get the next object from the front of the queue.
 *                The user should check the value of deferredObjectCount
 *                before calling this function.
 * INTERFACE:
 *   parameters:  none
 *   returns:     The next object on the queue.
 *=======================================================================*/

static cell*
getDeferredObject(void)
{
    if (startDeferredObjects == endDeferredObjectTable) {
        startDeferredObjects = deferredObjectTable;
    }
    deferredObjectCount--;
    return *startDeferredObjects++;
}

static CHUNK
sweepTheHeap(long *maximumFreeSizeP)
{
    CHUNK firstFreeChunk = NULL;
    CHUNK newChunk;
    CHUNK* nextChunkPtr = &firstFreeChunk;
    bool_t done = FALSE;

    cell* scanner =  CurrentHeap; /* current object */
    cell* endScanPoint = CurrentHeapEnd;
    long maximumFreeSize = 0;
    long thisFreeSize;
    do {
        /* Skip over groups of live objects */
        cell *lastLive;
        while (scanner < endScanPoint && ISKEPT(*scanner)) {
            *scanner &= ~MARKBIT;
            scanner += SIZE(*scanner) + HEADERSIZE;
        }
        lastLive = scanner;
        /* Skip over all the subsequent dead objects */
        while (scanner < endScanPoint && !ISKEPT(*scanner)) {
#if INCLUDEDEBUGCODE
            if (tracememoryallocation && (TYPE(*scanner) != GCT_FREE)) {
                Log->freeObject((long)scanner,
                    (INSTANCE_CLASS)((OBJECT)(scanner + HEADERSIZE))->ofClass,
                    (long)SIZE(*scanner) + HEADERSIZE);
            }
#endif /* INCLUDEDEBUGCODE */
            scanner += SIZE(*scanner) + HEADERSIZE;
        }
        if (scanner == endScanPoint) {
            if (scanner == lastLive) {
                /* The memory ended precisely with a live object. */
                break;
            } else {
                done = TRUE;
            }
        }
        thisFreeSize = (scanner - lastLive - 1);
        newChunk = (CHUNK)lastLive;
        newChunk->size = thisFreeSize << TYPEBITS;

        *nextChunkPtr = newChunk;
        nextChunkPtr = &newChunk->next;

        if (thisFreeSize > maximumFreeSize) {
            maximumFreeSize = thisFreeSize;
        }
    } while (!done);

    *nextChunkPtr = NULL;
    *maximumFreeSizeP = maximumFreeSize;
    return firstFreeChunk;
}

#if ENABLE_HEAP_COMPACTION

static cell*
compactTheHeap(breakTableStruct *currentTable, CHUNK firstFreeChunk)
{
    cell* copyTarget = CurrentHeap; /* end of last copied object */
    cell* scanner;                  /* current object */
    int count;                      /* keeps trace of break table */
    cell* currentHeapEnd = CurrentHeapEnd; /* cache for speed */
    int lastRoll = 0;               /* value of "count" during last roll */
    CHUNK freeChunk = firstFreeChunk;

    breakTableEntryStruct *table = NULL;

    for (scanner = CurrentHeap, count = -1;  ; count++) {
        /* Skip over groups of live objects */
        cell *live, *liveEnd;

        live = scanner;
        if (freeChunk != NULL) {
            liveEnd = (cell *)freeChunk;
            scanner = liveEnd + SIZE(*liveEnd) + HEADERSIZE;
            freeChunk = freeChunk->next;
        } else {
            liveEnd = scanner = currentHeapEnd;
        }
        if (count < 0) {
            /* This is a chunk of live objects at the beginning of memory.
             * There is no need to copy them.
             */
            copyTarget = liveEnd;
        } else {
            /* The size of the chunk of live objects */
            int liveSize = PTR_DELTA(liveEnd, live);
            if (count  == 0) {
                int i;
                /* This is the first chunk of live objects to move.  There is
                 * no break table yet.  We can just move the objects into
                 * place, and indicate that the break table goes at the end.
                 */
                for (i = 0; i < liveSize; i += CELL) {
                    CELL_AT_OFFSET(copyTarget, i) = CELL_AT_OFFSET(live, i);
                }
                table = (breakTableEntryStruct*)scanner - 1;
            } else {
                /* extraSize is the total amount of dead space at the end */
                int extraSize = PTR_DELTA(scanner, liveEnd);
                /* Slide the live objects to just after copyTarget.  Move
                 * the break table out of the way, if necessary.
                 * lastRoll is set to "count" if the break table had to
                 * be gotten "out of order".
                 */
                table = slideObject(copyTarget, live, liveSize, extraSize,
                                    table, count, &lastRoll);
            }
            /* Add a new entry to the break table */
            table[count].address = live;
            table[count].offset = PTR_DELTA(live, copyTarget);

            /* And update copy target. */
            copyTarget = PTR_OFFSET(copyTarget, liveSize);
        }

        if (scanner >= currentHeapEnd) {
            if (INCLUDEDEBUGCODE && scanner > currentHeapEnd) {
                fatalVMError(KVM_MSG_SWEEPING_SCAN_WENT_PAST_HEAP_TOP);
            }
            break;
        }
    }
    if (lastRoll > 0) {
        /* The elements between 0 and lastRoll - 1 may be unsorted */
        sortBreakTable(table, lastRoll);
    }
    currentTable->table = table;
    currentTable->length = count + 1;

    /* Return the location of the first free space in memory. */
    return copyTarget;
}

static breakTableEntryStruct*
slideObject(cell* target, cell *object, int objectSize, int extraSize,
            breakTableEntryStruct *table, int tableLength, int *lastRoll)
{
    /* The size of the break table, in bytes */
    int tableSize = tableLength * sizeof(table[0]);
    int fullTableSize = tableSize + sizeof(table[0]);
    int freeSize;
    int i;

 moreFreeSpaceBeforeTable:
    /* Memory is laid out as follows:
     *    CurrentHeap
     *                        Already moved objects
     *    target
     *                        Unused #0
     *    table
     *                        Break Table
     *    table + tableSize
     *                        Unused #1
     *    object
     *                        Object to be moved (objectSize >= CELL)
     *    object + objectSize
     *                        Unused #2
     *    object + objectSize + extraSize
     *
     * The goal is to move "object" so that it begins at target.
     *
     * The break table can be relocated, if necessary, so that the object can
     * be relocated.  We must also make sure that the break table has room for
     * at least one more entry.  We return the new location of the
     * break table.
     *
     * We are guaranteed that size(Unused #0) + size(Unused #1) >= 2 * CELL,
     * so that there is sufficient space for a new break table entry.  There
     * is usually a lot more space than that.
     *
     * The first time here, we are guaranteed that objectSize >= 2*CELL.
     *
     * We maintain the following invariants:
     * Though we don't maintain that invariant, we do maintain the invariants
     *     INV0: size(Unused #0) + size(Unused #1) >= 2 * CELL
     *     INV1  objectSize >= 2 * CELL
     */

    freeSize = PTR_DELTA(table, target); /* Size of unused #0 */
    if (objectSize <= freeSize) {
        /* We can just copy the object into the space where it belongs.
         * INV1 says that there is room for the break table to expand over
         * where the object had been.
         */
        for (i = 0; i < objectSize; i += CELL) {
            CELL_AT_OFFSET(target, i) = CELL_AT_OFFSET(object, i);
        }
        return table;
    }

    /* If the expanded break table fits into extraSize, then just move it
     * there, and then copy the object to where it belongs.
     *
     * This has the added benefit of moving the break table far to end of
     * memory, where it is hopefully out of the way for subsequent moves
     */
    if (extraSize >= fullTableSize) {
        cell *newTable = PTR_OFFSET(object,
                                    objectSize + extraSize - fullTableSize);
        for (i = 0; i < tableSize; i += CELL) {
            CELL_AT_OFFSET(newTable, i) = CELL_AT_OFFSET(table, i);
        }
        for (i = 0; i < objectSize; i += CELL) {
            CELL_AT_OFFSET(target, i) = CELL_AT_OFFSET(object, i);
        }
        return (breakTableEntryStruct *)newTable;
    }

    /* Copy as much of the object into Unused #0 as we can.
     * Adjust object and objectSize.
     * This increases the size of Unused #1 by the size of Unused #0, while
     * setting the size of Unused #0 to 0.
     */
    for (i = 0; i < freeSize; i += CELL) {
        CELL_AT_OFFSET(target, i) = CELL_AT_OFFSET(object, i);
    }
    object = PTR_OFFSET(object, freeSize);
    objectSize -= freeSize;

    /* Set freeSize to be the space between the table and the object */
    freeSize = PTR_DELTA(object, table) - tableSize;

    /* Memory is now laid out as follows:
     *    CurrentHeap
     *                        Already moved objects
     *    table
     *                        Break Table
     *    table + tableSize
     *                        Unused #1 (size freeSize >= 2 * CELL)
     *    object
     *                        Object to be moved (objectSize >= CELL)
     *    object + objectSize
     *                        Unused #2 (size extraSize)
     *    object + objectSize + extraSize
     *
     * The break table is right up against the already moved objects.
     *
     * We now have
     *     INV0:  size(Unused #1) = freeSize >= 2 * CELL
     *     INV1a:  objectSize >= CELL
     */

    /* If the total size of the break table is <= the size of the
     * object, then perhaps we can just swap the break table with the initial
     * elements of the object.
     */
    if (fullTableSize <= objectSize) {
        breakTableEntryStruct *oldTable = table;
        breakTableEntryStruct *newTable = (breakTableEntryStruct*)object;
        for (i = 0; i < tableSize; i += CELL) {
            cell temp = CELL_AT_OFFSET(table, i);
            CELL_AT_OFFSET(table, i) = CELL_AT_OFFSET(object, i);
            CELL_AT_OFFSET(object, i) = temp;
        }
        object = PTR_OFFSET(object, tableSize);
        objectSize -= tableSize;
        /* The new value of objectSize >= fullTableSize - tableSize = 2 * CELL,
         * so we are okay with INV1.  We also still have the same amount of
         * free space as before, though it has been chopped up into pieces,
         * again.  So INV0 is fine.
         */
        target = PTR_OFFSET(oldTable, i);
        table = newTable;
        goto moreFreeSpaceBeforeTable;
    }

    /* If the total size of the new break table is greater than the size of
     * the object, we can move break table so that its right end is the
     * end of the object.
     * We copy the break table into its new location as the same time that
     * we copy the object into the space evacuated by the break table.
     *
     * We run into a problem only if the beginning of the copied break table
     * overwrites its own end, i.e.
     *   tableSize + fullTableSize <=
     *            tableSize + freeSize + objectSize
     *
     */
    if (fullTableSize > objectSize && fullTableSize <= objectSize + freeSize) {
        cell *oldTable = (cell *)table;
        cell *newTable = PTR_OFFSET(object, objectSize - fullTableSize);

        for (i = 0; i < objectSize; i += CELL) {
            CELL_AT_OFFSET(newTable, i) = CELL_AT_OFFSET(oldTable, i);
            CELL_AT_OFFSET(oldTable, i) = CELL_AT_OFFSET(object, i);
        }
        for ( ; i < tableSize; i += CELL) {
            CELL_AT_OFFSET(newTable, i) = CELL_AT_OFFSET(oldTable, i);
        }
        return (breakTableEntryStruct*)newTable;
    }

    /* We need to roll the break table. */
    {
        cell* endTable = PTR_OFFSET(table, tableSize);
        for (i = 0; i < objectSize; i += CELL) {
            cell temp = CELL_AT_OFFSET(table, i);
            CELL_AT_OFFSET(table, i) = CELL_AT_OFFSET(object, i);
            CELL_AT_OFFSET(endTable, i) = temp;
        }
        /* Memory is now laid out as follows:
         *    CurrentHeap
         *                        Already moved objects
         *    table
         *                        Moved object
         *    table + objectSize
         *                        table
         *    table + objectSize + tableSize
         *                        Unused
         *    table + objectSize + tableSize + freeSize + extraSize;
         */
        table = PTR_OFFSET(table, objectSize);

        if (objectSize & CELL) {
            /* We did an add number of rolls.  We need to roll one more. */
            if (freeSize + extraSize > 2 * CELL) {
                /* We can just roll one more time.  Remember that we are
                 * required that there be two free words at the end of
                 * the break table when we return */
                CELL_AT_OFFSET(table, tableSize) = CELL_AT_OFFSET(table, 0);
                table = PTR_OFFSET(table, CELL);
            } else {
                /* For the following code to be executed, we must have
                 * freeSize == 2 * CELL and extraSize == 0.  This means
                 * that all of our holes have been exactly 2 cells long,
                 * and that the objects