gc-mem.c

kaffe是一个java虚拟机的源代码。里面包含了一些java例程和标准的java包。

/* gc-mem.c
 * The heap manager.
 *
 * Copyright (c) 1996, 1997
 *	Transvirtual Technologies, Inc.  All rights reserved.
 *
 * See the file "license.terms" for information on usage and redistribution 
 * of this file. 
 */

#include "debug.h"
/* undefine this to revert to old tile scheme */
#define	PREDEFINED_NUMBER_OF_TILES

#include "config.h"
#include "config-std.h"
#include "config-mem.h"
#include "gtypes.h"
#include "baseClasses.h"
#include "support.h"
#include "stats.h"
#include "locks.h"
#include "thread.h"
#include "gc.h"
#include "gc-mem.h"
#include "jni.h"
#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif
#if defined(HAVE_MPROTECT) && defined(DEBUG)
#include <sys/mman.h>
#endif

extern iLock* gc_lock;

#if defined(KAFFE_STATS)
static counter gcpages;
#endif
static gc_block* gc_small_block(size_t);
static gc_block* gc_large_block(size_t);

static gc_block* gc_primitive_alloc(size_t);
void gc_primitive_free(gc_block*);
static void* gc_system_alloc(size_t);

uintp gc_heap_base;
uintp gc_block_base;
uintp gc_heap_range;

typedef struct {
	gc_block* list;
	uint16	  sz;
} gc_freelist;

static gc_freelist freelist[NR_FREELISTS+1]
#ifdef PREDEFINED_NUMBER_OF_TILES
	= {
#define	S(sz)	{ 0, sz }
	S(16),
	S(24),
	S(32),
	S(40),
	S(48),
	S(56),
	S(64),
	S(80),
	S(96),
	S(112),
	S(128),
	S(160),
	S(192),
	S(224),
	S(240),
	S(496),
	S(1000),
	S(2016),
	S(4040),
	{ (gc_block *)-1, 0 }
}
#endif /* PREDEFINED_NUMBER_OF_TILES */
;

static struct {
	uint16	list;
} sztable[MAX_SMALL_OBJECT_SIZE+1];
static int max_freelist;

static gc_block* gc_prim_freelist;
static size_t max_small_object_size;

size_t gc_heap_total;		/* current size of the heap */
size_t gc_heap_allocation_size;	/* amount of memory by which to grow heap */
size_t gc_heap_initial_size;	/* amount of memory to initially allocate */
size_t gc_heap_limit;		/* maximum size to which heap should grow */

#ifndef gc_pgsize
size_t gc_pgsize;
int gc_pgbits;
#endif

#ifdef DEBUG
int gc_system_alloc_cnt;
#endif

extern struct Hjava_lang_Thread* garbageman;

#ifdef DEBUG
/*
 * analyze the slack incurred by small objects
 */
static int totalslack;
static int totalsmallobjs;

static void 
printslack(void)
{
	dprintf(
		"allocated %d small objects, total slack %d, slack/per "
		"object %8.2f\n", 
		totalsmallobjs, totalslack, totalslack/(double)totalsmallobjs);
}

/*
 * check whether the heap is still in a consistent state
 */
static void
gc_heap_check(void)
{
	int i; 

	for (i = 0; i < NR_FREELISTS; i++) {
		gc_block* blk = freelist[i].list;
		if (blk == 0 || blk == (gc_block*)-1) {
			continue;
		} else {
			gc_freeobj* mem = blk->free;

			assert(blk->inuse);
			assert(blk->avail < blk->nr);
			assert(blk->funcs == (uint8*)GCBLOCK2BASE(blk));
			assert(blk->state == (uint8*)(blk->funcs + blk->nr));
			assert(blk->data  == (uint8*)ROUNDUPALIGN(blk->state + blk->nr));

			while (mem) {
				ASSERT_ONBLOCK(mem, blk);
				mem = mem->next;
			}
		}
	}
}

#endif /* DEBUG */

/*
 * Initialise allocator.
 */
static
void
gc_heap_initialise(void)
{
#ifndef gc_pgsize
	gc_pgsize = getpagesize();
	for (gc_pgbits = 0;
	     (1 << gc_pgbits) != gc_pgsize && gc_pgbits < 64;
	     gc_pgbits++)
		;
	assert(gc_pgbits < 64);
#endif

	gc_heap_allocation_size = Kaffe_JavaVMArgs[0].allocHeapSize;
	gc_heap_initial_size = Kaffe_JavaVMArgs[0].minHeapSize;
	gc_heap_limit = Kaffe_JavaVMArgs[0].maxHeapSize;

	/*
	 * Perform some sanity checks.
	 */
	if (gc_heap_initial_size > gc_heap_limit) {
		dprintf(
		    "Initial heap size (%dK) > Maximum heap size (%dK)\n",
		    (int) (gc_heap_initial_size/1024), (int)(gc_heap_limit/1024));
		EXIT(-1);
	}

#ifndef PREDEFINED_NUMBER_OF_TILES
    {
	int i;
	int l;
	int b;
	int t;

	/* old scheme, where number of tiles was approximated by a series
	 * of powers of two
	 */
#define	OBJSIZE(NR) \
	((gc_pgsize-GCBLOCK_OVH-ROUNDUPALIGN(1)-(NR*(2+sizeof(void*))))/NR)

	/* For a given number of tiles in a block, work out the size of
	 * the allocatable units which'll fit in them and build a translation
	 * table for the sizes.
	 */
	i = 1;
	max_small_object_size = ROUNDDOWNALIGN(OBJSIZE(i));
	l = max_small_object_size;
	for (;;) {
		b = ROUNDDOWNALIGN(OBJSIZE(i));
		if (b >= MIN_OBJECT_SIZE) {
			for (t = l; t > b; t--) {
				sztable[t].list = l;
			}
			l = t;
			i <<= 1;
		}
		else {
			for (t = l; t > MIN_OBJECT_SIZE; t--) {
				sztable[t].list = l;
			}
			for (t = 0; t <= MIN_OBJECT_SIZE; t++) {
				sztable[t].list = MIN_OBJECT_SIZE;
			}
			break;
		}
	}

	/* Translate table into list numbers */
	i = -1;
	b = -1;
	for (l = 0; l <= max_small_object_size; l++) {
		if (sztable[l].list != b) {
			b = sztable[l].list;
			i++;
			freelist[i].sz = b;
		}
		sztable[l].list = i;
	}
	max_freelist = i;
    }
#else
	/* PREDEFINED_NUMBER_OF_TILES */
	{
		/*
		 * Use the preinitialized freelist table to initialize
		 * the sztable.
		 */
		int sz = 0;
		uint16 flidx = 0;
		while (freelist[flidx].list == 0) {
			for (; sz <= freelist[flidx].sz; sz++)
				sztable[sz].list = flidx;
			flidx++;
		}
		max_small_object_size = sz - 1;
		max_freelist = flidx;
	}
#endif

DBG(SLACKANAL,
	atexit(printslack);
    )

#undef	OBJSIZE

	/* Round 'gc_heap_allocation_size' up to pagesize */
	gc_heap_allocation_size = ROUNDUPPAGESIZE(gc_heap_allocation_size);

	/* Round 'gc_heap_initial_size' up to pagesize */
	gc_heap_initial_size = ROUNDUPPAGESIZE(gc_heap_initial_size);

	/* allocate heap of initial size from system */
	gc_system_alloc(gc_heap_initial_size);
}

/*
 * gc_heap_malloc
 * Allocate a piece of memory.
 */
void*
gc_heap_malloc(size_t sz)
{
	static int gc_heap_init = 0;
	size_t lnr;
	gc_freeobj* mem;
	gc_block** mptr;
	gc_block* blk;
	size_t nsz;
	int times;
	int iLockRoot;

	/* Initialise GC heap first time in - we must assume single threaded
	 * operation here so we can do the lock initialising.
	 */
	if (gc_heap_init == 0) {
		gc_heap_initialise();
		gc_heap_init = 1;
	}

	lockStaticMutex(&gc_lock);

	times = 0;

DBG(SLACKANAL,
	if (GC_SMALL_OBJECT(sz)) {
		totalslack += (freelist[sztable[sz].list].sz - sz);
		totalsmallobjs++;
	}
    )

	rerun:;
	times++;

DBG(GCDIAG, 
	gc_heap_check();
    )

	if (GC_SMALL_OBJECT(sz)) {

		/* Translate size to object free list */
		lnr = sztable[sz].list;
		nsz = freelist[lnr].sz;

		/* No available objects? Allocate some more */
		mptr = &freelist[lnr].list;
		if (*mptr != 0) {
			blk = *mptr;
			assert(blk->free != 0);
DBG(GCALLOC,		dprintf("gc_heap_malloc: freelist %d at %p free %p\n", sz, *mptr, blk->free);)
		}
		else {
			blk = gc_small_block(nsz);
			if (blk == 0) {
				nsz = gc_pgsize;
				goto nospace;
			}
			blk->next = *mptr;
			*mptr = blk;

DBG(GCALLOC,		dprintf("gc_heap_malloc: small block %d at %p free %p\n", sz, *mptr, blk->free);)
		}

		/* Unlink free one and return it */
		mem = blk->free;

		DBG(GCDIAG,
		    assert(blk->magic == GC_MAGIC);
		    ASSERT_ONBLOCK(mem, blk);
		    if (mem->next) ASSERT_ONBLOCK(mem->next, blk));

		blk->free = mem->next;

		GC_SET_STATE(blk, GCMEM2IDX(blk, mem), GC_STATE_NORMAL);

		/* Once we use all the sub-blocks up, remove the whole block
		 * from the freelist.
		 */
		assert(blk->nr >= blk->avail);
		assert(blk->avail > 0);
		blk->avail--;
		if (blk->avail == 0) {
			*mptr = blk->next;
		}
	}
	else {
		nsz = sz;
		blk = gc_large_block(nsz);
		if (blk == 0) {
			nsz = nsz + GCBLOCK_OVH + sizeof(gcFuncs*) + ROUNDUPALIGN(1);
			nsz = ROUNDUPPAGESIZE(nsz);
			goto nospace;
		}
		mem = GCBLOCK2FREE(blk, 0);
		GC_SET_STATE(blk, 0, GC_STATE_NORMAL);
DBG(GCALLOC,	dprintf("gc_heap_malloc: large block %d at %p\n", sz, mem);	)
		blk->avail--;
		assert(blk->avail == 0);
	}

	/* Clear memory */
	memset(mem, 0, nsz);

	assert(GC_OBJECT_SIZE(mem) >= sz);

	unlockStaticMutex(&gc_lock);

	return (mem);

	/* --------------------------------------------------------------- */
	nospace:;

	/* Failed to find space in any freelists. Must try to get the
	 * memory from somewhere.
	 */

	switch (times) {
	case 1:
		/* Try invoking GC if it is available */
		if (garbageman != 0) {
			/* The other caller of invokeGC,  Runtime.gc() can't 
			 * give up this lock on its own, since it does not 
			 * hold this lock.
			 */
			unlockStaticMutex(&gc_lock);
			adviseGC();
			lockStaticMutex(&gc_lock);
		}
		break;

	case 2:
		/* Get from the system */
		if (nsz < gc_heap_allocation_size) {
			nsz = gc_heap_allocation_size;
		}
		gc_system_alloc(nsz);
		break;

	default:
		if (DBGEXPR(CATCHOUTOFMEM, true, false))
		{
			/*
			 * If we ran out of memory, a OutOfMemoryException is
			 * thrown.  If we fail to allocate memory for it, all
			 * is lost.
			 */
			static int ranout;
			assert (ranout++ == 0 || !!!"Ran out of memory!");
		}
		/* Guess we've really run out */
		unlockStaticMutex(&gc_lock);
		return (0);
	}

	/* Try again */
	goto rerun;
}

/*
 * Free a piece of memory.
 */
void
gc_heap_free(void* mem)
{
	gc_block* info;
	gc_freeobj* obj;
	int lnr;
	int msz;
	int idx;


	info = GCMEM2BLOCK(mem);
	idx = GCMEM2IDX(info, mem);

	DBG(GCDIAG,
	    gc_heap_check();
	    assert(info->magic == GC_MAGIC);
	    assert(GC_GET_COLOUR(info, idx) != GC_COLOUR_FREE));

	GC_SET_COLOUR(info, idx, GC_COLOUR_FREE);

DBG(GCFREE,
	dprintf("gc_heap_free: memory %p size %d\n", mem, info->size);	)

	if (GC_SMALL_OBJECT(info->size)) {
		lnr = sztable[info->size].list;
		/* If this block contains no free sub-blocks yet, attach
		 * it to freelist.
		 */
		if (info->avail == 0) {
			info->next = freelist[lnr].list;
			freelist[lnr].list = info;
		}
		info->avail++;
		DBG(GCDIAG,
		    /* write pattern in memory to see when live objects were
		     * freed - Note that (f4f4f4f4 == -185273100)
		     */
		    memset(mem, 0xf4, info->size));
		obj = GCMEM2FREE(mem);
		obj->next = info->free;
		info->free = obj;

		ASSERT_ONBLOCK(obj, info);

		/* If we free all sub-blocks, free the block */
		assert(info->avail <= info->nr);
		if (info->avail == info->nr) {
			gc_block** finfo = &freelist[lnr].list;
			for (;;) {
				if (*finfo == info) {
					(*finfo) = info->next;
					info->size = gc_pgsize;
					gc_primitive_free(info);
					break;
				}
				finfo = &(*finfo)->next;
				assert(*finfo != 0);
			}
		}
	}
	else {
		/* Calculate true size of block */
		msz = info->size + GCBLOCK_OVH + ROUNDUPALIGN(1);
		msz = ROUNDUPPAGESIZE(msz);
		info->size = msz;
		gc_primitive_free(info);
	}
DBG(GCDIAG,
	gc_heap_check();
    )
}

/*
 * Allocate a new block of GC'ed memory.  The block will contain 'nr' objects