garbage.h

This is a java virtual machine implement in c

/*0001*//*
/*0002./ * Copyright (c) 1998-2001 Sun Microsystems, Inc. All Rights Reserved.
/*0003./ *
/*0004./ * This software is the confidential and proprietary information of Sun
/*0005./ * Microsystems, Inc. ("Confidential Information").  You shall not
/*0006./ * disclose such Confidential Information and shall use it only in
/*0007./ * accordance with the terms of the license agreement you entered into
/*0008./ * with Sun.
/*0009./ *
/*0010./ * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
/*0011./ * SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
/*0012./ * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/*0013./ * PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES
/*0014./ * SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
/*0015./ * THIS SOFTWARE OR ITS DERIVATIVES.
/*0016./ *
/*0017./ */
/*0018*/
/*0019*//*=========================================================================
/*0020./ * SYSTEM:    KVM
/*0021./ * SUBSYSTEM: Memory management
/*0022./ * FILE:      garbage.h
/*0023./ * OVERVIEW:  Memory manager/garbage collector for the KVM.
/*0024./ * AUTHOR:    Antero Taivalsaari, Sun Labs
/*0025./ *            Edited by Doug Simon 11/1998
/*0026./ *            Frank Yellin (exact collection, compaction)
/*0027./ *            Compaction based on code written by Matt Seidl
/*0028./ *=======================================================================*/
/*0029*/
/*0030*//*=========================================================================
/*0031./ * NOTE (KVM 1.0.3):
/*0032./ * The garbage collector documentation below has been revised
/*0033./ * in KVM 1.0.3.  Apart from some bug fixes, the only difference
/*0034./ * between KVM 1.0.2 and 1.0.3 garbage collectors is the addition
/*0035./ * of the new native cleanup mechanism defined at the bottom of
/*0036./ * this file. Also, the new monitor/synchronization code in 
/*0037./ * KVM 1.0.3 has caused some minor changes in the garbage collector.
/*0038./ *=======================================================================*/
/*0039*/
/*0040*//*=========================================================================
/*0041./ * COMMENTS ON GARBAGE COLLECTOR IN KVM:
/*0042./ * The original KVM (Spotless) garbage collector was based on Cheney's
/*0043./ * elegant copying collector presented in Communications of the ACM
/*0044./ * in September 1970.  Although that collector has a lot of benefits
/*0045./ * (in particular, it uses an iterative rather than recursive algorithm
/*0046./ * for collecting objects), it has the general problem of copying
/*0047./ * collectors in that it requires double the memory space than the
/*0048./ * program is actually using.  That requirement was problematic
/*0049./ * when porting the KVM to run on devices with very limited
/*0050./ * memory such as the PalmPilot.
/*0051./ *
/*0052./ * In order to make the KVM more suitable to small
/*0053./ * devices, a new garbage collector was implemented for KVM 1.0.

			//\\//\\//\\//\\//\\//\\ KVM GC疭┦
/*0054./ * This collector was based on a straightforward, handle-free,
/*0055./ * non-moving, mark-and-sweep algorithm. Since the KVM 1.0
			//\\//\\//\\//\\//\\//\\

/*0056./ * collector did not move objects, it was somewhat simpler
/*0057./ * than the original Spotless collector. However, since the 
/*0058./ * KVM 1.0 collector maintained free lists of memory rather
/*0059./ * than copying and/or compacting memory, object allocation
/*0060./ * was not as fast as in the original Spotless collector.
/*0061./ * Also, memory fragmentation could cause the the VM run
/*0062./ * out of memory more easily than with a copying or compacting
/*0063./ * collector.
/*0064./ *
/*0065./ * In KVM 1.0.2, a new compacting garbage collector,
/*0066./ * fully precise ("exact") collector was added. 
/*0067./ * Most of the documentation below has now been updated
/*0068./ * to reflect the features of the 1.0.2/1.0.3 collector.
/*0069./ *=======================================================================*/
/*0070*/
/*0071*//*=========================================================================
/*0072./ * Include files
/*0073./ *=======================================================================*/
/*0074*/
/*0075*//*=========================================================================
/*0076./ * Header word definitions and structures
/*0077./ *=======================================================================*/
/*0078*/
/*0079*//*=========================================================================
/*0080./ * OBJECT STRUCTURES:
/*0081./ * In our VM, each heap-allocated structure in memory is preceded with
/*0082./ * an object header that provides detailed information on the type and
/*0083./ * size of the object. The length of the header is one word (32 bits).
/*0084./ *
/*0085./ * The basic heap object structure is as follows:
/*0086./ *
/*0087./ *                   +---------------+
/*0088./ *                   ! gc header     ! (object length, type and other info)
/*0089./ *                   +---------------+
/*0090./ * Object pointer -> ! class ptr     !    ^
/*0091./ *                   +---------------+    !
/*0092./ *                   | mhc field     !    !  (mhc = monitorOrHashCode)
/*0093./ *                   +---------------+
/*0094./ *                   .               .    !
/*0095./ *                   .               .  data
/*0096./ *                   .               .    !
/*0097./ *                   !               !    !
/*0098./ *                   +---------------+    !
/*0099./ *                   !               !    v
/*0100./ *                   +---------------+
/*0101./ *

			//\\//\\//\\//\\//\\//\\//\\
/*0102./ * IMPORTANT:
/*0103./ * Note that there are no object handles in our VM. Thus, unlike in
/*0104./ * many other JVM implementations, all the memory references are
/*0105./ * direct rather than indirect.
			//\\//\\//\\//\\//\\//\\//\\

/*0107./ * It is important to notice that references are only allowed to
/*0108./ * memory locations that are immediately preceded by an object header;
/*0109./ * this means that you may not create a pointer that refers, e.g., to
/*0110./ * data fields of an object directly. This restriction simplifies the
/*0111./ * garbage collection process substantially (but could be removed
/*0112./ * relatively easily if necessary).
/*0113./ *=========================================================================
/*0114./ * OBJECT HEADERS:
/*0115./ * An object header is a 32-bit structure that contains important
/*0116./ * administrative information. In particular, the header stores
/*0117./ * the length of the object, the type of the object and two
/*0118./ * bits for administrative purposes.
/*0119./ *                                                             +-- Static bit
/*0120./ *                                                             | +-- Mark bit
/*0121./ * <------------------ length -------------------> <-- type--> v v
/*0122./ *|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|
/*0123./ *| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |0|0|
/*0124./ *|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|-+-+-+-+-+-+-+-|
/*0125./ *
/*0126./ * Length holds the length of the object in cells, excluding the
/*0127./ * object header. For instance, length = 1 means that the data
/*0128./ * area of the object is 4 bytes.  The minimum physical size of
/*0129./ * an object is 8 bytes (4 byte header + 4 byte data).
/*0130./ *
/*0131./ * Type field holds the garbage collection type of the object,
/*0132./ * instructing the garbage collector to scan the data fields of
/*0133./ * the object correctly upon garbage collection. Garbage collection
/*0134./ * types (GCT_*) are defined below.
/*0135./ *
/*0136./ * Static bit is unused these days except on the Palm.  In the 
/*0137./ * original KVM (Spotless) collector this bit was used for
/*0138./ * denoting that an object was allocated in the static heap,
/*0139./ * i.e., the object was immovable.
/*0140./ *
/*0141./ * Mark bit is used for marking live (non-garbage) objects during
/*0142./ * garbage collection. During normal program execution this bit
/*0143./ * should always be 0 in every heap object.
/*0144./ *=======================================================================*/
/*0145*/
/*0146*/#define MARKBIT         0x00000001
/*0147*/#define STATICBIT       0x00000002
/*0148*/#define TYPEMASK        0x000000FC
/*0149*/
/*0150*//*  HEADER */
/*0151*//*  struct headerStruct { */
/*0152*//*  int size      :24; */
/*0153*//*  int type      :6; */