garbage.h

一个操作系统源代码 用于嵌入式设备 在Vc++环境下仿真 成功移植到多款处理器上

/*
 * Copyright (c) 1998-2001 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.
 *
 */

/*=========================================================================
 * SYSTEM:    KVM
 * SUBSYSTEM: Memory management
 * FILE:      garbage.h
 * OVERVIEW:  Memory manager/garbage collector for the KVM.
 * AUTHOR:    Antero Taivalsaari, Sun Labs
 *            Edited by Doug Simon 11/1998
 *            Frank Yellin (exact collection, compaction)
 *            Compaction based on code written by Matt Seidl
 *=======================================================================*/

/*=========================================================================
 * NOTE (KVM 1.0.3):
 * The garbage collector documentation below has been revised
 * in KVM 1.0.3.  Apart from some bug fixes, the only difference
 * between KVM 1.0.2 and 1.0.3 garbage collectors is the addition
 * of the new native cleanup mechanism defined at the bottom of
 * this file. Also, the new monitor/synchronization code in 
 * KVM 1.0.3 has caused some minor changes in the garbage collector.
 *=======================================================================*/

/*=========================================================================
 * COMMENTS ON GARBAGE COLLECTOR IN KVM:
 * The original KVM (Spotless) garbage collector was based on Cheney's
 * elegant copying collector presented in Communications of the ACM
 * in September 1970.  Although that collector has a lot of benefits
 * (in particular, it uses an iterative rather than recursive algorithm
 * for collecting objects), it has the general problem of copying
 * collectors in that it requires double the memory space than the
 * program is actually using.  That requirement was problematic
 * when porting the KVM to run on devices with very limited
 * memory such as the PalmPilot.
 *
 * In order to make the KVM more suitable to small
 * devices, a new garbage collector was implemented for KVM 1.0.
 * This collector was based on a straightforward, handle-free,
 * non-moving, mark-and-sweep algorithm. Since the KVM 1.0
 * collector did not move objects, it was somewhat simpler
 * than the original Spotless collector. However, since the 
 * KVM 1.0 collector maintained free lists of memory rather
 * than copying and/or compacting memory, object allocation
 * was not as fast as in the original Spotless collector.
 * Also, memory fragmentation could cause the the VM run
 * out of memory more easily than with a copying or compacting
 * collector.
 *
 * In KVM 1.0.2, a new compacting garbage collector,
 * fully precise ("exact") collector was added. 
 * Most of the documentation below has now been updated
 * to reflect the features of the 1.0.2/1.0.3 collector.
 *=======================================================================*/

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

/*=========================================================================
 * Header word definitions and structures
 *=======================================================================*/

/*=========================================================================
 * OBJECT STRUCTURES:
 * In our VM, each heap-allocated structure in memory is preceded with
 * an object header that provides detailed information on the type and
 * size of the object. The length of the header is one word (32 bits).
 *
 * The basic heap object structure is as follows:
 *
 *                   +---------------+
 *                   ! gc header     ! (object length, type and other info)
 *                   +---------------+
 * Object pointer -> ! class ptr     !    ^
 *                   +---------------+    !
 *                   | mhc field     !    !  (mhc = monitorOrHashCode)
 *                   +---------------+
 *                   .               .    !
 *                   .               .  data
 *                   .               .    !
 *                   !               !    !
 *                   +---------------+    !
 *                   !               !    v
 *                   +---------------+
 *
 * IMPORTANT:
 * Note that there are no object handles in our VM. Thus, unlike in
 * many other JVM implementations, all the memory references are
 * direct rather than indirect.
 *
 * It is important to notice that references are only allowed to
 * memory locations that are immediately preceded by an object header;
 * this means that you may not create a pointer that refers, e.g., to
 * data fields of an object directly. This restriction simplifies the
 * garbage collection process substantially (but could be removed
 * relatively easily if necessary).
 *=========================================================================
 * OBJECT HEADERS:
 * An object header is a 32-bit structure that contains important
 * administrative information. In particular, the header stores
 * the length of the object, the type of the object and two
 * bits for administrative purposes.
 *                                                             +-- Static bit
 *                                                             | +-- Mark bit
 * <------------------ length -------------------> <-- type--> v v
 *|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|
 *| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |0|0|
 *|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|
 *
 * Length holds the length of the object in cells, excluding the
 * object header. For instance, length = 1 means that the data
 * area of the object is 4 bytes.  The minimum physical size of
 * an object is 8 bytes (4 byte header + 4 byte data).
 *
 * Type field holds the garbage collection type of the object,
 * instructing the garbage collector to scan the data fields of
 * the object correctly upon garbage collection. Garbage collection
 * types (GCT_*) are defined below.
 *
 * Static bit is unused these days except on the Palm.  In the 
 * original KVM (Spotless) collector this bit was used for
 * denoting that an object was allocated in the static heap,
 * i.e., the object was immovable.
 *
 * Mark bit is used for marking live (non-garbage) objects during
 * garbage collection. During normal program execution this bit
 * should always be 0 in every heap object.
 *=======================================================================*/

#define MARKBIT         0x00000001
#define STATICBIT       0x00000002
#define TYPEMASK        0x000000FC

/*  HEADER */
/*  struct headerStruct { */
/*  int size      :24; */
/*  int type      :6; */
/*  int markBit   :1; */
/*  int staticBit :1; */
/*  }; */

/*  The amount of bits that will have to be shifted away
 *  in order to read the object length correctly
 */

#define inAnyHeap(ptr) \
     (((cell *)ptr >= AllHeapStart) && ((cell *)ptr < AllHeapEnd))

#define inCurrentHeap(ptr) \
      (((cell *)ptr >= CurrentHeap) && ((cell *)ptr < CurrentHeapEnd))

#define TYPEBITS        8

/* The number of bits that we have to shift to get the type */
#define TYPE_SHIFT      2

/*=========================================================================
 * Operations on header words
 *=======================================================================*/

#define ISMARKED(n)     ((n) & MARKBIT)
#define ISSTATIC(n)     ((n) & STATICBIT)
#define SIZE(n)         (((cell)(n)) >> TYPEBITS)
#define TYPE(n)         (GCT_ObjectType)(((n) & TYPEMASK) >> TYPE_SHIFT)
#define ISFREECHUNK(n)  (((n) & (TYPEMASK | MARKBIT | STATICBIT)) == 0)

/*  Header is 1 word long */
#define HEADERSIZE      1

/*=========================================================================
 * FREE LIST STRUCTURES:
 * The garbage collector maintains a free list of available memory.
 * Every available memory chunk is preceded by a free list header with
 * the following information:
 *
 *     +--------------+
 *     !     size     ! (the amount of memory in this chunk)
 *     +--------------+
 *     !     next     ! (pointer to the next chunk in the free list)
 *     +--------------+
 *
 * The size information is stored in cells (32 bit words). The size
 * information is stored in the same format as in regular object headers,
 * i.e., only the highest 24 bits are used (see above). The 6 low bits
 * must all be zero for a word to be recognized as a chunk header. The size
 * excludes the size field (HEADERSIZE) itself, i.e., if the physical
 * size of the chunk is 3 words, the size field actually contains 2.
 *
 * As obvious, the next field is NIL (0) if this is the last
 * free chunk in memory.
 *
 * Chunks are always at least 2 words (64 bits) long, because this
 * is the minimum size needed for allocating new objects. Free memory
 * areas smaller than this are automatically merged with other objects
 * (thus creating permanent garbage). In practice this happens rarely,
 * though.
 *=======================================================================*/

/*  CHUNK */
struct chunkStruct {
    long  size;     /*  The size of the chunk in words (including the header) */
    CHUNK next;     /*  Pointer to the next chunk (NIL if none) */
};

/*=========================================================================
 * As a Palm specific option, the static portion of a Palm device's memory
 * can be used to store relatively static structures such as the constant
 * pool and code of a class. By storing these structures in static memory
 * a substantial amount of room is freed up for use by the garbage
 * collected heap. Given that we expect anything put into static memory to
 * live for the lifetime of a VM execution, we can implement the management
 * of any static memory chunks simply as a list of chunks that are all
 * freed upon the end of execution. As such the basic structure of a
 * statically allocated chunk will be as follows:
 *
 *                   +---------------+
 *                   ! prev chunk ptr! (bit 0: bump bit)
 *                   +---------------+
 * Object pointer -> !               !    ^
 *                   +---------------+    !
 *                   .               .    !
 *                   .               .  data
 *                   .               .    !
 *                   !               !    !
 *                   +---------------+    !
 *                   !               !    v
 *                   +---------------+
 *
 * These chunks are allocated via the mallocStaticBytes operation and are
 * all collected at once by the FinalizeStaticMemory operation.
 *=======================================================================*/

/* Since the PalmOS memory returns two-byte aligned addresses, */
/* we must occasionally bump the statically allocated object */
/* addresses upwards in the memory (by two bytes). This is  */
/* indicated by raising a special "bump bit" stored in the */
/* least significant bit in the previous chunk pointer field  */
/* (shown above). */

#define STATICBUMPBIT  0x00000001
#define STATICBUMPMASK 0xFFFFFFFE

/*=========================================================================
 * Garbage collection types of objects (GCT_* types)
 *=========================================================================
 * These types are used for instructing the garbage collector to
 * scan the data fields of objects correctly upon garbage collection.
 * Since two low-end bits of the first header field are used for
 * flags, we don't use these in type declarations.
 *=======================================================================*/

typedef enum {
    GCT_FREE = 0,
    /*  Objects which have no pointers inside them */
    /*  (can be ignored safely during garbage collection) */
    GCT_NOPOINTERS,

    /*  Java-level objects which may have mutable pointers inside them */
    GCT_INSTANCE,
    GCT_ARRAY,
    GCT_OBJECTARRAY,

    /* Only if we have static roots */
    GCT_METHODTABLE ,

    /*  Internal VM objects which may have mutable pointers inside them */
    GCT_POINTERLIST,
    GCT_EXECSTACK,
    GCT_THREAD,
    GCT_MONITOR,
    /* A weak pointer list gets marked/copied after all other objects */
    GCT_WEAKPOINTERLIST
} GCT_ObjectType;

#define GCT_FIRSTVALIDTAG GCT_NOPOINTERS
#define GCT_LASTVALIDTAG  GCT_WEAKPOINTERLIST

#define GCT_TYPENAMES  { \
        "FREE",          \
        "NOPOINTERS",    \
        "INSTANCE",      \
        "ARRAY",         \
        "OBJECTARRAY",   \
        "METHODTABLE",   \
        "POINTERLIST",   \
        "EXECSTACK",     \
        "THREAD",        \
        "MONITOR",       \
        "WEAK POINTERLIST", \
    }

/*=========================================================================
 * Dynamic heap variables
 *=======================================================================*/

extern cell* AllHeapStart;   /* Lower limits of any heap space */
extern cell* AllHeapEnd;

extern cell* CurrentHeap;    /* Current limits of heap space */
extern cell* CurrentHeapEnd; /* Current heap top */