garbage.h

java 1.1 gemini 08_16

/*****************************************************************************
*  Copyright Statement:
*  --------------------
*  This software is protected by Copyright and the information contained
*  herein is confidential. The software may not be copied and the information
*  contained herein may not be used or disclosed except with the written
*  permission of MediaTek Inc. (C) 2005
*
*  BY OPENING THIS FILE, BUYER HEREBY UNEQUIVOCALLY ACKNOWLEDGES AND AGREES
*  THAT THE SOFTWARE/FIRMWARE AND ITS DOCUMENTATIONS ("MEDIATEK SOFTWARE")
*  RECEIVED FROM MEDIATEK AND/OR ITS REPRESENTATIVES ARE PROVIDED TO BUYER ON
*  AN "AS-IS" BASIS ONLY. MEDIATEK EXPRESSLY DISCLAIMS ANY AND ALL WARRANTIES,
*  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF
*  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE OR NONINFRINGEMENT.
*  NEITHER DOES MEDIATEK PROVIDE ANY WARRANTY WHATSOEVER WITH RESPECT TO THE
*  SOFTWARE OF ANY THIRD PARTY WHICH MAY BE USED BY, INCORPORATED IN, OR
*  SUPPLIED WITH THE MEDIATEK SOFTWARE, AND BUYER AGREES TO LOOK ONLY TO SUCH
*  THIRD PARTY FOR ANY WARRANTY CLAIM RELATING THERETO. MEDIATEK SHALL ALSO
*  NOT BE RESPONSIBLE FOR ANY MEDIATEK SOFTWARE RELEASES MADE TO BUYER'S
*  SPECIFICATION OR TO CONFORM TO A PARTICULAR STANDARD OR OPEN FORUM.
*
*  BUYER'S SOLE AND EXCLUSIVE REMEDY AND MEDIATEK'S ENTIRE AND CUMULATIVE
*  LIABILITY WITH RESPECT TO THE MEDIATEK SOFTWARE RELEASED HEREUNDER WILL BE,
*  AT MEDIATEK'S OPTION, TO REVISE OR REPLACE THE MEDIATEK SOFTWARE AT ISSUE,
*  OR REFUND ANY SOFTWARE LICENSE FEES OR SERVICE CHARGE PAID BY BUYER TO
*  MEDIATEK FOR SUCH MEDIATEK SOFTWARE AT ISSUE. 
*
*  THE TRANSACTION CONTEMPLATED HEREUNDER SHALL BE CONSTRUED IN ACCORDANCE
*  WITH THE LAWS OF THE STATE OF CALIFORNIA, USA, EXCLUDING ITS CONFLICT OF
*  LAWS PRINCIPLES.  ANY DISPUTES, CONTROVERSIES OR CLAIMS ARISING THEREOF AND
*  RELATED THERETO SHALL BE SETTLED BY ARBITRATION IN SAN FRANCISCO, CA, UNDER
*  THE RULES OF THE INTERNATIONAL CHAMBER OF COMMERCE (ICC).
*
*****************************************************************************/

/*******************************************************************************
 * Filename:
 * ---------
 *  garbage.h
 *
 * Project:
 * --------
 *  MAUI
 *
 * Description:
 * ------------
 *  
 *
 * Author:
 * -------
 *  
 *
 *==============================================================================
 * 				HISTORY
 * Below this line, this part is controlled by PVCS VM. DO NOT MODIFY!! 
 *------------------------------------------------------------------------------
 * removed!
 *
 * removed!
 * removed!
 * removed!
 *
 *------------------------------------------------------------------------------
 * Upper this line, this part is controlled by PVCS VM. DO NOT MODIFY!! 
 *==============================================================================
 *******************************************************************************/


/*
 * Copyright ?2003 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 */

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

/*=========================================================================
 * 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
 *=======================================================================*/

/*=========================================================================
 * Global execution modes
 *=======================================================================*/

#ifndef CLDC11
/*  Flags for toggling certain global modes on and off */
#if EXCESSIVE_GARBAGE_COLLECTION
extern bool_t excessivegc;
#endif /* EXCESSIVE_GARBAGE_COLLECTION */
#endif /* !CLDC11 */

/*=========================================================================
 * 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 adding "dead" space to objects). 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

#ifdef CLDC11
    /* Added for java.lang.ref.WeakReference support in CLDC 1.1 */
    ,GCT_WEAKREFERENCE
#endif /* CLDC11 */
} GCT_ObjectType;

#define GCT_FIRSTVALIDTAG GCT_NOPOINTERS
#ifdef CLDC11
#define GCT_LASTVALIDTAG  GCT_WEAKREFERENCE