gc-mem.c

kaffe 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

static iStaticLock	gc_heap_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*);

/**
 * A preallocated block for small objects.
 *
 * @list list of gc_blocks available for objects of the same size
 * @sz   the size of the objects that can be stored in @list. 
 */
typedef struct {
	gc_block* list;
	uint16	  sz;
} gc_freelist;

/**
 * Array of preallocated blocks.
 *  
 */
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 */
;

/**
 * Maps a given size to a freelist entry. 
 *
 */
static struct {
	uint16	list;
} sztable[MAX_SMALL_OBJECT_SIZE+1];
static int max_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 */
uintp gc_heap_base;
uintp gc_heap_range;

#ifndef gc_pgsize
size_t gc_pgsize;
int gc_pgbits;
#endif

#ifdef KAFFE_VMDEBUG
int gc_system_alloc_cnt;
#endif

extern struct Hjava_lang_Thread* garbageman;

#if !(defined(NDEBUG) || !defined(KAFFE_VMDEBUG))
/* Magic constant used to mark blocks under gc's management */
static const uint32 gc_magic = 0xD0DECADE;

/* Set the magic marker of a block */
static inline void
gc_set_magic_marker(gc_block *b)
{
  b->magic = gc_magic;
}

/* Check the magic marker of a block */
static inline bool
gc_check_magic_marker(gc_block *b)
{
  return b->magic == gc_magic;
}

/*
 * 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(GCBLOCKINUSE(blk));
			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 /* !(defined(NDEBUG) || !defined(KAFFE_VMDEBUG)) */

/*
 * Initialise allocator.
 */
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-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_heap_grow(gc_heap_initial_size);
}

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

	lockStaticMutex(&gc_heap_lock);

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

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 %ld at %p free %p\n", 
				(long) sz, *mptr, blk->free);)
		}
		else {
			blk = gc_small_block(nsz);
			if (blk == 0) {
				goto out;
			}
			blk->next = *mptr;
			*mptr = blk;

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

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

		DBG(GCDIAG,
		    assert(gc_check_magic_marker(blk));
		    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) {
			goto out;
		}
		mem = GCBLOCK2FREE(blk, 0);
		GC_SET_STATE(blk, 0, GC_STATE_NORMAL);
DBG(GCALLOC,	dprintf("gc_heap_malloc: large block %ld at %p\n", 
			(long) sz, mem);	)
		blk->avail--;
		assert(blk->avail == 0);
	}

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

	assert(GC_OBJECT_SIZE(mem) >= sz);

	out:
	unlockStaticMutex(&gc_heap_lock);

	return (mem);
}

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

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

	DBG(GCDIAG,
	    gc_heap_check();
	    assert(gc_check_magic_marker(info));
	    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);	)

	lockStaticMutex(&gc_heap_lock);

	if (GC_SMALL_OBJECT(info->size)) {
		lnr = sztable[info->size].list;
	
		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) {
			/*
			 * note that *finfo==0 is ok if we free a block
			 * whose small object is so large that it can
			 * only contain one object.
			 */
			gc_block** finfo = &freelist[lnr].list;
			for (;*finfo;) {
				if (*finfo == info) {
					(*finfo) = info->next;
					break;
				}
				finfo = &(*finfo)->next;
			}

			info->size = gc_pgsize;
			gc_primitive_free(info);
		} else if (info->avail==1) {
			/*
			 * If this block contains no free sub-blocks yet, attach
			 * it to freelist. 
			 */
			gc_block **finfo = &freelist[lnr].list;

			info->next = *finfo; 
			*finfo = info;
		}

	}
	else {
		/* Calculate true size of block */
		msz = info->size + 2 + ROUNDUPALIGN(1);
		msz = ROUNDUPPAGESIZE(msz);
		info->size = msz;
		gc_primitive_free(info);
	}

	unlockStaticMutex(&gc_heap_lock);

DBG(GCDIAG,
	gc_heap_check();
    )

}

/*
 * Allocate a new block of GC'ed memory.  The block will contain 'nr' objects
 * each of 'sz' bytes.
 */
static
gc_block*
gc_small_block(size_t sz)
{
	gc_block* info;
	int i;
	int nr;

	info = gc_primitive_alloc(gc_pgsize);
	if (info == 0) {
		return (0);
	}

	/* Calculate number of objects in this block */
	nr = (gc_pgsize-ROUNDUPALIGN(1))/(sz+2);

	/* Setup the meta-data for the block */
	DBG(GCDIAG, gc_set_magic_marker(info));

	info->size = sz;
	info->nr = nr;
	info->avail = nr;
	info->funcs = (uint8*)GCBLOCK2BASE(info);
	info->state = (uint8*)(info->funcs + nr);
	info->data = (uint8*)ROUNDUPALIGN(info->state + nr);

	DBG(GCDIAG, memset(info->data, 0, sz * nr));

	/* Build the objects into a free list */
	for (i = nr-1; i-- > 0;) {
		GCBLOCK2FREE(info, i)->next = GCBLOCK2FREE(info, i+1);
		GC_SET_COLOUR(info, i, GC_COLOUR_FREE);
		GC_SET_STATE(info, i, GC_STATE_NORMAL);
	}
	GCBLOCK2FREE(info, nr-1)->next = 0;
	GC_SET_COLOUR(info, nr-1, GC_COLOUR_FREE);
	GC_SET_STATE(info, nr-1, GC_STATE_NORMAL);
	info->free = GCBLOCK2FREE(info, 0);
DBG(SLACKANAL,
	int slack = ((void *)info) 
		+ gc_pgsize - (void *)(GCBLOCK2MEM(info, nr));
	totalslack += slack;
    )
	return (info);
}

/*
 * Allocate a new block of GC'ed memory.  The block will contain one object
 */
static
gc_block*
gc_large_block(size_t sz)
{
	gc_block* info;
	size_t msz;

	/* Add in management overhead */
	msz = sz+2+ROUNDUPALIGN(1);
	/* Round size up to a number of pages */
	msz = ROUNDUPPAGESIZE(msz);

	info = gc_primitive_alloc(msz);
	if (info == 0) {
		return (0);
	}

	/* Setup the meta-data for the block */
	DBG(GCDIAG, gc_set_magic_marker(info));

	info->size = sz;
	info->nr = 1;
	info->avail = 1;
	info->funcs = (uint8*)GCBLOCK2BASE(info);
	info->state = (uint8*)(info->funcs + 1);
	info->data = (uint8*)ROUNDUPALIGN(info->state + 1);