gc-mem.c

java virtual machince kaffe

/* 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 "gc-incremental.h"
#include "jni.h"
#if defined(HAVE_UNISTD_H)
#include <unistd.h>
#endif
#if defined(HAVE_SYS_TYPES_H)
#include <sys/types.h>
#endif
#if defined(HAVE_SYS_MMAN_H)
#include <sys/mman.h>
#endif

#ifndef MAX
#define MAX(A,B) ((A) > (B) ? (A) : (B))
#endif

static gc_block *gc_last_block;
static gc_block *gc_first_block;
static gc_block *gc_reserve_pages;
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);

/**
 * 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)	{ NULL, 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;
static size_t gc_heap_allocation_size;	/* amount of memory by which to grow heap */
static size_t gc_heap_initial_size;	/* amount of memory to initially allocate */
static size_t gc_heap_total;		/* current size of the heap */
static size_t gc_heap_limit;		/* maximum size to which heap should grow */
static uintp gc_heap_base;              /* start of the heap */
static uintp gc_heap_range;             /* last gc-able address - gc_heap_base */

#ifndef gc_pgsize
static size_t gc_pgsize;
static int gc_pgbits;
#endif

#ifdef KAFFE_VMDEBUG
int gc_system_alloc_cnt;
#endif

/**
 * rounds @V up to the next page size.
 *
 */
#define	ROUNDUPPAGESIZE(V)	(((uintp)(V) + gc_pgsize - 1) & -gc_pgsize)

static char * gc_block_base = NULL;
static size_t gc_num_blocks = 0;
static size_t gc_num_live_pages = 0;

#define KGC_BLOCKS		((gc_block *) gc_block_base)

/**
 * Evaluates to the first usable address in gc_block @B.
 *
 */ 
#define GCBLOCK2BASE(B)		(((char *)gc_heap_base) \
					 + gc_pgsize * ((B) - KGC_BLOCKS))

/**
 * Evaluates to the size of the object that contains address @M.
 *
 */
#define	KGC_OBJECT_SIZE(M)	gc_mem2block(M)->size

#define ASSERT_ONBLOCK(OBJ, BLK) assert(gc_mem2block(OBJ) == BLK)

#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; 

	gc_block *chk_blk = gc_last_block;

	while (chk_blk->pprev != NULL)
	  {
	    if (chk_blk->pprev != NULL && chk_blk->pprev->pnext != chk_blk)
	      {
		dprintf("Major failure in the Garbage Collector. Primitive block list trashed\n");
		abort();
	      }
	    chk_blk = chk_blk->pprev;
	  }

	while (chk_blk != gc_last_block)
	  {
	    if (chk_blk->pnext != NULL && chk_blk->pnext->pprev != chk_blk)
	      {
		dprintf("Major failure in the Garbage Collector (2). Primitive block list trashed\n");
		abort();
	      }
	    chk_blk = chk_blk->pnext;
	  }
	
	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)) */


static inline bool
gc_heap_is_unlimited(void)
{
  return gc_heap_limit == UNLIMITED_HEAP;
}

/*
 * Initialise allocator.
 */
void
gc_heap_initialise(void)
{
  initStaticLock(&gc_heap_lock);

#ifndef gc_pgsize
	gc_pgsize = getpagesize();
	for (gc_pgbits = 0;
	     (size_t)(1 << gc_pgbits) != gc_pgsize && gc_pgbits < 64;
	     gc_pgbits++)
		;
	assert(gc_pgbits < 64);
#endif

	gc_heap_allocation_size = Kaffe_JavaVMArgs.allocHeapSize;
	gc_heap_initial_size = Kaffe_JavaVMArgs.minHeapSize;
	gc_heap_limit = Kaffe_JavaVMArgs.maxHeapSize;

	/*
	 * Perform some sanity checks.
	 */
	if ((gc_heap_initial_size > gc_heap_limit) 
	    && !gc_heap_is_unlimited()) {
		dprintf(
		    "Initial heap size (%dK) > Maximum heap size (%dK)\n",
		    (int) (gc_heap_initial_size/1024), (int)(gc_heap_limit/1024));
		KAFFEVM_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 = NULL;
	gc_block** mptr;
	gc_block* blk;
	size_t nsz;
#if defined(KAFFE_STATS)
	static timespent heap_alloc_time;
#endif

	lockStaticMutex(&gc_heap_lock);
	startTiming(&heap_alloc_time, "gc_heap_malloc");

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

DBG(GCDIAG, 
	gc_heap_check();
    );

	if (KGC_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;

		KGC_SET_STATE(blk, GCMEM2IDX(blk, mem), KGC_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);
		KGC_SET_STATE(blk, 0, KGC_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(KGC_OBJECT_SIZE(mem) >= sz);