collector.c

Nucleus_2_kvm_Hello 是kvm移植到Nucleus系统的源代码。。。好东西啊

/*
 * Copyright (c) 1998-2002 Sun Microsystems, Inc. All Rights Reserved.
 *
 * This software is the confidential and proprietary information of Sun
 * Microsystems, Inc. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Sun.
 *
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
 * SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 * PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES
 * SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
 * THIS SOFTWARE OR ITS DERIVATIVES.
 *
 * Use is subject to license terms.
 */

/*=========================================================================
 * SYSTEM:    KVM
 * SUBSYSTEM: Memory management
 * FILE:      collector.c
 * OVERVIEW:  Exact, compacting garbage collector.
 * AUTHOR:    Antero Taivalsaari, Sun Labs
 *            Edited by Doug Simon 11/1998 (made collection more precise)
 *            Frank Yellin (removed excessive recursion)
 *            Frank Yellin, Matt Seidl (exact, compacting GC)
 *=======================================================================*/

/*=========================================================================
 * For detailed explanation of the memory system, see Garbage.h
 *=======================================================================*/

/*=========================================================================
 * Include files
 *=======================================================================*/

#include "global.h"

/*=========================================================================
 * Definitions and declarations
 *=======================================================================*/

#define PTR_OFFSET(ptr, offset) ((void *)((char *)ptr + offset))
#define PTR_DELTA(ptr1, ptr2) ((char *)(ptr1) - (char *)ptr2)

#define CELL_AT_OFFSET(ptr, offset) (*(cell *)PTR_OFFSET(ptr, offset))

#if ENABLE_HEAP_COMPACTION
# define ISKEPT(n) ((n) & MARKBIT)
#else
# define ISKEPT(n) ((n) & (MARKBIT|STATICBIT))
#endif

typedef struct breakTableStruct {
    int length;                 /* in entries */
    struct breakTableEntryStruct *table;
} breakTableStruct;

typedef struct breakTableEntryStruct {
    cell *address;
    int offset;
} breakTableEntryStruct;

/*=========================================================================
 * Variables
 *=======================================================================*/

void* TheHeap;
long  VMHeapSize;               /* Heap size */

cell* AllHeapStart;             /* Heap bottom */
cell* CurrentHeap;              /* Same as AllHeapStart*/
cell* CurrentHeapEnd;           /* End of heap */
cell* AllHeapEnd;

WEAKPOINTERLIST WeakPointers;
CHUNK FirstFreeChunk;

#if ENABLE_HEAP_COMPACTION
cell* PermanentSpaceFreePtr;
#endif

#if EXCESSIVE_GARBAGE_COLLECTION
bool_t excessivegc;
#endif /* EXCESSIVE_GARBAGE_COLLECTION */

#define DEFERRED_OBJECT_TABLE_SIZE 40
static cell *deferredObjectTable[DEFERRED_OBJECT_TABLE_SIZE];
#define endDeferredObjectTable (deferredObjectTable + DEFERRED_OBJECT_TABLE_SIZE)
static cell **startDeferredObjects,  **endDeferredObjects;
static int deferredObjectCount;
static int deferredObjectTableOverflow;

/*=========================================================================
 * Static functions (private to this file)
 *=======================================================================*/

static void putDeferredObject(cell *c);
static cell* getDeferredObject(void);
static void initializeDeferredObjectTable(void);
static void markChildren(cell* object, cell* limit, int remainingDepth);
static void checkMonitorAndMark(OBJECT object);

static cell* allocateFreeChunk(long size);

static CHUNK sweepTheHeap(long *maximumFreeSizeP);

#if ENABLE_HEAP_COMPACTION
static cell* compactTheHeap(breakTableStruct *currentTable, CHUNK);

static breakTableEntryStruct*
slideObject(cell* deadSpace, cell *object, int objectSize, int extraSize,
            breakTableEntryStruct *table, int tableLength, int *lastRoll);

static void sortBreakTable(breakTableEntryStruct *, int length);
static void updateRootObjects(breakTableStruct *currentTable);
static void updateHeapObjects(breakTableStruct *currentTable, cell *endScan);
static void updatePointer(void *address, breakTableStruct *currentTable);
static void updateMonitor(OBJECT object, breakTableStruct *currentTable);
static void updateThreadAndStack(THREAD thread, breakTableStruct *currentTable);

void printBreakTable(breakTableEntryStruct *table, int length) ;

#endif /* ENABLE_HEAP_COMPACTION */

#if INCLUDEDEBUGCODE
static void checkValidHeapPointer(cell *number);
int NoAllocation = 0;
#else
#define checkValidHeapPointer(number)
#define NoAllocation 0
#endif

#if ASYNCHRONOUS_NATIVE_FUNCTIONS
#include "async.h"
extern ASYNCIOCB IocbRoots[];
#endif

static void markRootObjects(void);
static void markNonRootObjects(void);
static void markWeakPointerLists(void);

static void markThreadStack(THREAD thisThread);

/*=========================================================================
 * Helper macros
 *=======================================================================*/

#define OBJECT_HEADER(object) ((cell *)(object))[-HEADERSIZE]

#define MARK_OBJECT(object) \
    if (inHeapSpaceFast(object)) { OBJECT_HEADER((object)) |= MARKBIT; }

#define MARK_OBJECT_IF_NON_NULL(object) \
    if (inHeapSpaceFast((object))) { OBJECT_HEADER((object)) |= MARKBIT; }

#define inHeapSpaceFast(ptr) \
     (((cell *)(ptr) >= heapSpace) && ((cell *)(ptr) < heapSpaceEnd))

/*=========================================================================
 * Heap initialization operations
 *=======================================================================*/

void InitializeHeap(void)
{
    VMHeapSize = RequestedHeapSize;
    AllHeapStart = allocateHeap(&VMHeapSize, &TheHeap);

    if (TheHeap == NIL) {
        fatalVMError(KVM_MSG_NOT_ENOUGH_MEMORY);
    }

    /* Initially, don't create any permanent space.  It'll grow as needed */
    CurrentHeap    = AllHeapStart;
    CurrentHeapEnd = PTR_OFFSET(AllHeapStart, VMHeapSize);

#if !CHUNKY_HEAP
    FirstFreeChunk = (CHUNK)CurrentHeap;
    FirstFreeChunk->size =
           (CurrentHeapEnd -CurrentHeap - HEADERSIZE) << TYPEBITS;
    FirstFreeChunk->next = NULL;
#endif

    /* Permanent space goes from CurrentHeapEnd to AllHeapEnd.  It currently
     * has zero size.
     */
#if ENABLE_HEAP_COMPACTION
    PermanentSpaceFreePtr = CurrentHeapEnd;
#endif
    AllHeapEnd            = CurrentHeapEnd;

#if INCLUDEDEBUGCODE
    if (tracememoryallocation) {
        Log->allocateHeap(VMHeapSize, (long)AllHeapStart, (long)AllHeapEnd);
    }
    NoAllocation = 0;
#endif
}

void FinalizeHeap(void)
{
    freeHeap(TheHeap);
}

/*=========================================================================
 * Memory allocation operations
 *=======================================================================*/

/*=========================================================================
 * FUNCTION:      mallocHeapObject()
 * TYPE:          public memory allocation operation
 * OVERVIEW:      Allocate a contiguous area of n cells in the dynamic heap.
 * INTERFACE:
 *   parameters:  size: the requested object size in cells,
 *                type: garbage collection type of the object
 *   returns:     pointer to newly allocated area, or
 *                NIL is allocation fails.
 * COMMENTS:      Allocated data area is not initialized, so it
 *                may contain invalid heap references. If you do
 *                not intend to initialize data area right away,
 *                you must use 'callocObject' instead (or otherwise
 *                the garbage collector will get confused next time)!
 *=======================================================================*/

cell* mallocHeapObject(long size, GCT_ObjectType type)
/* Remember: size is given in CELLs rather than bytes */
{
    cell* thisChunk;
    long realSize;

    if (size == 0) size = 1;
    realSize = size + HEADERSIZE;

#if INCLUDEDEBUGCODE
    if (NoAllocation > 0) {
        fatalError(KVM_MSG_CALLED_ALLOCATOR_WHEN_FORBIDDEN);
    }
#endif /* INCLUDEDEBUGCODE */

#if EXCESSIVE_GARBAGE_COLLECTION
    if (excessivegc) {
        garbageCollect(0);
    }
#endif /* EXCESSIVE_GARBAGE_COLLECTION */

    thisChunk = allocateFreeChunk(realSize);
    if (thisChunk == NULL) {
        garbageCollect(realSize); /* So it knows what we need */
        thisChunk = allocateFreeChunk(realSize);
        if (thisChunk == NULL) {
            return NULL;
        }
    }

    /* Augment the object header with gc type information */
    /* NOTE: This operation does not set the size of the object!! */
    /* You must initialize the size elsewhere, or otherwise the */
    /* memory system will be corrupted! */
    *thisChunk |= (type << TYPE_SHIFT);

#if INCLUDEDEBUGCODE
    if (tracememoryallocation) {
        Log->allocateObject((long)thisChunk,
                            (long)size+HEADERSIZE,
                            (int)type,
                            (long)thisChunk, memoryFree());
    }
#endif /* INCLUDEDEBUGCODE */

#if ENABLEPROFILING
    DynamicObjectCounter     += 1;
    DynamicAllocationCounter += (size+HEADERSIZE)*CELL;
#endif /* ENABLEPROFILING */

    return thisChunk + HEADERSIZE;
}

static cell* allocateFreeChunk(long size)
{
    CHUNK thisChunk = FirstFreeChunk;
    CHUNK* nextChunkPtr = &FirstFreeChunk;
    cell* dataArea  = NIL;

    for (thisChunk = FirstFreeChunk, nextChunkPtr = &FirstFreeChunk;
         thisChunk != NULL;
         nextChunkPtr = &thisChunk->next, thisChunk = thisChunk->next) {

        /* Calculate how much bigger or smaller the */
        /* chunk is than the requested size */
        long overhead = SIZE(thisChunk->size) + HEADERSIZE - size;

        if (overhead > HEADERSIZE) {
            thisChunk->size = (overhead - HEADERSIZE) << TYPEBITS;
            dataArea = (cell *)thisChunk + overhead;
            *dataArea = (size - HEADERSIZE) << TYPEBITS;
            return dataArea;
        } else if (overhead >= 0) {
            /* There was an exact match or overhead is too small to be useful.
             * Remove this chunk from the free list, and if there is extra
             * space at the end of the chunk, it becomes wasted space for the
             * lifetime of the allocated object
             */
            *nextChunkPtr = thisChunk->next;
            dataArea = (cell *)thisChunk;
            /* Store the size of the object in the object header */
            *dataArea = (size + overhead - HEADERSIZE) << TYPEBITS;
            return dataArea;
        }
    }
    /* If we got here, there was no chunk with enough memory available */
    return NULL;
}

/*=========================================================================
 * FUNCTION:      callocPermanentObject()
 * TYPE:          public memory allocation operation
 * OVERVIEW:      Allocate a contiguous area of n cells in the permanent heap
 * INTERFACE:
 *   parameters:  size: the requested object size in cells,
 *   returns:     pointer to newly allocated area,
 *=======================================================================*/

cell*
callocPermanentObject(long size) {
    cell *result;
#if ENABLE_HEAP_COMPACTION
    result = PermanentSpaceFreePtr - size;
    PermanentSpaceFreePtr = result;
    if (result < CurrentHeapEnd) {
        /* We have to expand permanent memory */
        cell* newPermanentSpace = CurrentHeapEnd;
        do {
            newPermanentSpace = PTR_OFFSET(newPermanentSpace, -0x800);
        } while (newPermanentSpace > result);
        /* We need to expand permanent memory to include the memory between
         * newPermanentSpace and CurrentHeapEnd
         */

        /* We pass GC a request that is larger than it could possibly
         * fulfill, so as to force a GC.
         */
        garbageCollect(AllHeapEnd - AllHeapStart);

        if (newPermanentSpace < (cell *)FirstFreeChunk + 2 * HEADERSIZE) {
            fatalError(KVM_MSG_UNABLE_TO_EXPAND_PERMANENT_MEMORY);
        } else {
            int newFreeSize =
                (newPermanentSpace - (cell *)FirstFreeChunk - HEADERSIZE);
            memset(newPermanentSpace, 0,
                   PTR_DELTA(CurrentHeapEnd, newPermanentSpace));
            CurrentHeapEnd = newPermanentSpace;
            FirstFreeChunk->size =  newFreeSize << TYPEBITS;
        }