gc-incremental.c

java virtual machince kaffe

/* gc-incremental.c
 * The garbage collector.
 * The name is misleading.  GC is non-incremental at this point.
 *
 * Copyright (c) 1996, 1997
 *	Transvirtual Technologies, Inc.  All rights reserved.
 *
 * Copyright (c) 2003, 2004
 *	Kaffe.org contributors. See ChangeLog for details. All rights reserved.
 *   
 * See the file "license.terms" for information on usage and redistribution 
 * of this file. 
 */

/* XXX this should be controllable, somehow. */
#define	SUPPORT_VERBOSEMEM

#include "config.h"
#include "debug.h"
#include "config-std.h"
#include "config-mem.h"
#include "defs.h"
#include "gtypes.h"
#include "gc.h"
#include "gc-mem.h"
#include "locks.h"
#include "thread.h"
#include "jthread.h"
#include "errors.h"
#include "md.h"
#include "stats.h"
#include "classMethod.h"
#include "gc-incremental.h"
#include "gc-refs.h"
#include "jvmpi_kaffe.h"

#if defined(HAVE_SYS_TYPES_H)
#include <sys/types.h>
#endif /* defined(HAVE_SYS_TYPES_H) */

static struct _gcStats {
        uint32  totalmem;
        uint32  totalobj;
        uint32  freedmem;
        uint32  freedobj;
        uint32  markedobj;
        uint32  markedmem;
        uint32  allocobj;
        uint32  allocmem;
        uint32  finalobj;
        uint32  finalmem;
} gcStats;

/* Avoid recursively allocating OutOfMemoryError */
#define OOM_ALLOCATING		((void *) -1)

#define STACK_SWEEP_MARGIN      1024
#define GCSTACKSIZE		16384
#define FINALIZERSTACKSIZE	THREADSTACKSIZE

/*
 * Object implementing the collector interface.
 */
static struct CollectorImpl {
	Collector 	collector;
	/* XXX include static below here for encapsulation */
} gc_obj;

/* XXX don't use these types ! */
static Hjava_lang_Thread* garbageman;
static Hjava_lang_Thread* finalman;

static gcList gclists[6];
static const int nofin_white = 5;
static const int fin_white = 4;
static const int grey = 3;
static const int nofin_black = 2;
static const int fin_black = 1;
static const int finalise = 0;

static int gc_init = 0;
static volatile int gcDisabled = 0;
static volatile int gcRunning = -1;
static volatile bool finalRunning = false;
static volatile bool finaliserStarted = false;
#if defined(KAFFE_STATS)
static timespent gc_time;
static timespent sweep_time;
static counter gcgcablemem;
static counter gcfixedmem;
#endif /* KAFFE_STATS */

/* Is this pointer within our managed heap? */
#define IS_A_HEAP_POINTER(from) \
        ((uintp) (from) >= gc_get_heap_base() && \
	 (uintp) (from) < gc_get_heap_base() + gc_get_heap_range())

static void *outOfMem;
static void *outOfMem_allocator;

#if defined(SUPPORT_VERBOSEMEM)

static struct {
  ssize_t size;
  int count;
  uint64 total;
} objectSizes[] = {

#define OBJECTSIZE(SZ)  { SZ, 0, 0 },

  /* The smaller sizes should match what's in the
     freelist[] array defined in gc-mem.c */

  OBJECTSIZE(16)
  OBJECTSIZE(24)
  OBJECTSIZE(32)
  OBJECTSIZE(40)
  OBJECTSIZE(48)
  OBJECTSIZE(56)
  OBJECTSIZE(64)
  OBJECTSIZE(80)
  OBJECTSIZE(96)
  OBJECTSIZE(112)
  OBJECTSIZE(128)
  OBJECTSIZE(160)
  OBJECTSIZE(192)
  OBJECTSIZE(224)
  OBJECTSIZE(240)
  OBJECTSIZE(496)
  OBJECTSIZE(1000)
  OBJECTSIZE(2016)
  OBJECTSIZE(4040)
  OBJECTSIZE(8192)
  OBJECTSIZE(12288)
  OBJECTSIZE(16483)
  OBJECTSIZE(32768)
  OBJECTSIZE(65536)
  OBJECTSIZE(131072)
  OBJECTSIZE(262144)
  OBJECTSIZE(524288)
  OBJECTSIZE(1048576)
  OBJECTSIZE(0x7FFFFFFF)

#undef  OBJECTSIZE

  { -1, -1, 0 }

};

static void objectStatsChange(gc_unit*, int);
static void objectStatsPrint(void);
static void objectSizesAdd(size_t);
static void objectSizesPrint(void);

#define	OBJECTSTATSADD(M)	objectStatsChange(M, 1)
#define	OBJECTSTATSREMOVE(M)	objectStatsChange(M, -1)
#define	OBJECTSTATSPRINT()	objectStatsPrint()
#define	OBJECTSIZESADD(S)	objectSizesAdd(S)

#else

#define	OBJECTSTATSADD(M)
#define	OBJECTSTATSREMOVE(M)
#define	OBJECTSTATSPRINT()
#define	OBJECTSIZESADD(S)

#endif

/* For statistics gathering, record how many objects and how 
 * much memory was marked.
 */
static inline
void record_marked(int nr_of_objects, uint32 size)
{       
        gcStats.markedobj += nr_of_objects;
        gcStats.markedmem += size;
} 

static iStaticLock	gcman; 
static iStaticLock	finman;
static iStaticLock	gcmanend;
static iStaticLock	finmanend;
static iStaticLock	gc_lock;	/* allocator mutex */

static void gcFree(Collector* gcif, void* mem);

/* Standard GC function sets.  We call them "allocation types" now */
static gcFuncs gcFunctions[KGC_ALLOC_MAX_INDEX];

/*
 * register an allocation type under a certain index
 * NB: we could instead return a pointer to the record describing the
 * allocation type.  This would give us more flexibility, but it wouldn't
 * allow us to use compile-time constants.
 */
static void
registerTypeByIndex(gc_alloc_type_t idx, walk_func_t walk, final_func_t final,
	destroy_func_t destroy,
	const char *description)
{
	/* once only, please */
	assert (gcFunctions[idx].description == 0);
	/* don't exceed bounds */
	assert (idx < sizeof(gcFunctions)/sizeof(gcFunctions[0]));

	gcFunctions[idx].walk = walk;
	gcFunctions[idx].final = final;
	gcFunctions[idx].destroy = destroy;
	gcFunctions[idx].description = description;
}

/*
 * Register a fixed allocation type.  The only reason we tell them apart
 * is for statistical purposes.
 */
static void
gcRegisterFixedTypeByIndex(Collector* gcif UNUSED, 
	gc_alloc_type_t idx, const char *description)
{
	registerTypeByIndex(idx, NULL, KGC_OBJECT_FIXED, NULL, description);
}

/*
 * Register a allocation type that is subject to gc.  
 */
static void
gcRegisterGcTypeByIndex(Collector* gcif UNUSED,
	gc_alloc_type_t idx, walk_func_t walk, final_func_t final,
	destroy_func_t destroy,
	const char *description)
{
	registerTypeByIndex(idx, walk, final, destroy, description);
}

static void startGC(Collector *gcif);
static void finishGC(Collector *gcif);
static void startFinalizer(void);
static void markObjectDontCheck(gc_unit *unit, gc_block *info, uintp idx);

/* Return true if gc_unit is pointer to an allocated object */
static inline int
gc_heap_isobject(gc_block *info, gc_unit *unit)
{
	uintp p = (uintp) UTOMEM(unit) - gc_get_heap_base();

	if (!(p & (MEMALIGN - 1)) && p < gc_get_heap_range() && GCBLOCKINUSE(info)) {
		/* Make sure 'unit' refers to the beginning of an
		 * object.  We do this by making sure it is correctly
		 * aligned within the block.
		 */
		uint16 idx = GCMEM2IDX(info, unit);
		if (idx < info->nr &&
		    GCBLOCK2MEM(info, idx) == unit &&
		    ((KGC_GET_COLOUR(info, idx) & KGC_COLOUR_INUSE) == KGC_COLOUR_INUSE || KGC_GET_COLOUR(info, idx) == KGC_COLOUR_FIXED)) {
			return 1;
		}
	}
	return 0;
}

static void
markObjectDontCheck(gc_unit *unit, gc_block *info, uintp idx)
{
	/* If the object has been traced before, don't do it again. */
	if (KGC_GET_COLOUR(info, idx) != KGC_COLOUR_WHITE) {
		return;
	}
DBG(GCWALK,	
	dprintf("  marking @%p: %s\n", UTOMEM(unit),
			describeObject(UTOMEM(unit)));
    );

	DBG(GCSTAT,
	    switch (KGC_GET_FUNCS(info, idx)) {
	    case KGC_ALLOC_NORMALOBJECT:
	    case KGC_ALLOC_FINALIZEOBJECT:
	    case KGC_ALLOC_PRIMARRAY:
	    case KGC_ALLOC_REFARRAY: {
		    Hjava_lang_Object *obj;
		    obj = (Hjava_lang_Object *)(unit+1);
		    if (obj->vtable != NULL) {
			    Hjava_lang_Class *c;
			    c = OBJECT_CLASS(obj);
			    if (c)
				    c->live_count++;
		    }
	    default: {
	    }
	    }});
	    

	/* If we found a new white object, mark it as grey and
	 * move it into the grey list.
	 */
	KGC_SET_COLOUR(info, idx, KGC_COLOUR_GREY);
	UREMOVELIST(unit);
	UAPPENDLIST(gclists[grey], unit);
}

/*
 * Mark the memory given by an address if it really is an object.
 */
static void
gcMarkAddress(Collector* gcif UNUSED, void *gc_info UNUSED, const void* mem)
{
	gc_block* info;
	gc_unit* unit;

	/*
	 * First we check to see if the memory 'mem' is in fact the
	 * beginning of an object.  If not we just return.
	 */

	/* Get block info for this memory - if it exists */
	info = gc_mem2block(mem);
	unit = UTOUNIT(mem);
	if (gc_heap_isobject(info, unit)) {
		markObjectDontCheck(unit, info, GCMEM2IDX(info, unit));
	}
}

/*
 * Mark an object.  Argument is assumed to point to a valid object,
 * and never, ever, be null.
 */
static void
gcMarkObject(Collector* gcif UNUSED, void *gc_info UNUSED, const void* objp)
{
  gc_unit *unit = UTOUNIT(objp);
  gc_block *info = gc_mem2block(unit);
  DBG(GCDIAG, assert(gc_heap_isobject(info, unit)));
  markObjectDontCheck(unit, info, GCMEM2IDX(info, unit));
}

void
KaffeGC_WalkConservative(Collector* gcif, const void* base, uint32 size)
{
	const int8* mem;

DBG(GCWALK,	
	dprintf("scanning %d bytes conservatively from %p-%p\n", 
		size, base, ((const char *)base) + size);
    );

	record_marked(1, size);

	if (size > 0) {
		uintp alignment = ALIGNMENTOF_VOIDP_IN_STACK;

		for (mem = ((const int8*)base) + (size & -alignment) - sizeof(void*);
		     (const void*)mem >= base;
		     mem -= ALIGNMENTOF_VOIDP) {
			const void *p = *(void * const *)mem;
			if (p) {
				gcMarkAddress(gcif, NULL, p);
			}
		}
	}
}

/*
 * Like walkConservative, except that length is computed from the block size
 * of the object.  Must be called with pointer to object allocated by gc.
 */
static
uint32
gcGetObjectSize(Collector* gcif UNUSED, const void* mem)
{
	return (GCBLOCKSIZE(gc_mem2block(UTOUNIT(mem))));
}

static
gc_alloc_type_t
gcGetObjectIndex(Collector* gcif UNUSED, const void* mem)
{
	gc_unit* unit = UTOUNIT(mem);
	gc_block* info = gc_mem2block(unit);
	if (!gc_heap_isobject(info, unit)) {
		return (-1);
	} else {
		return (KGC_GET_FUNCS(info, GCMEM2IDX(info, unit)));
	}
}

/*
 * Given a pointer within an object, find the base of the object.
 * This works for both gcable and fixed object types.
 *
 * This method uses many details of the allocator implementation.
 * Specifically, it relies on the contiguous layout of block infos
 * and the way gc_mem2block and GCMEM2IDX are implemented.
 */
static
void*
gcGetObjectBase(Collector *gcif UNUSED, void* mem)
{
	int idx;
	gc_block* info;

	/* quickly reject pointers that are not part of this heap */
	if (!IS_A_HEAP_POINTER(mem)) {
		return (NULL);
	}

	lockStaticMutex(&gc_lock);
	/* the allocator initializes all block infos of a large
	   object using the address of the first page allocated
	   for the large object. Hence, simply using GCMEM2* works
	   even for large blocks
	  */

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

	/* report fixed objects as well */
	if (idx < info->nr && 
	    ((KGC_GET_COLOUR(info, idx) & KGC_COLOUR_INUSE) || 
	     (KGC_GET_COLOUR(info, idx) & KGC_COLOUR_FIXED))) 
	{
	    	mem = UTOMEM(GCBLOCK2MEM(info, idx));
		unlockStaticMutex(&gc_lock);
		return mem;
	}
	unlockStaticMutex(&gc_lock);
	return (NULL);
}

static
const char*
gcGetObjectDescription(Collector* gcif, const void* mem)
{
	return (gcFunctions[gcGetObjectIndex(gcif, mem)].description);
}

/*
 * Walk a bit of memory.
 */
void
KaffeGC_WalkMemory(Collector* gcif, void* mem)
{
	gc_block* info;
	int idx;
	gc_unit* unit;
	uint32 size;
	walk_func_t walkf;

	unit = UTOUNIT(mem);
	info = gc_mem2block(unit);
	idx = GCMEM2IDX(info, unit);

	if (KGC_GET_COLOUR(info, idx) == KGC_COLOUR_BLACK) {
		return;
	}

	UREMOVELIST(unit);

	/* if the object is about to be finalized, put it directly
	 * into the finalise list, otherwise put it into the black
	 * list.
	 */
	if (KGC_GET_STATE(info, idx) == KGC_STATE_INFINALIZE) {
		gcStats.finalobj += 1;
		gcStats.finalmem += GCBLOCKSIZE(info);
		UAPPENDLIST(gclists[finalise], unit);
	} else if (KGC_GET_STATE(info, idx) == KGC_STATE_NEEDFINALIZE) {
		UAPPENDLIST(gclists[fin_black], unit);
	} else {
		UAPPENDLIST(gclists[nofin_black], unit);
	}
	
	KGC_SET_COLOUR(info, idx, KGC_COLOUR_BLACK);

	assert(KGC_GET_FUNCS(info, idx) < 
		sizeof(gcFunctions)/sizeof(gcFunctions[0]));
	size = GCBLOCKSIZE(info);
	record_marked(1, size);
	walkf = gcFunctions[KGC_GET_FUNCS(info, idx)].walk;
	if (walkf != NULL) {
DBG(GCWALK,	
		dprintf("walking %d bytes @%p: %s\n", size, mem, 
			describeObject(mem));
    );
		walkf(gcif, NULL, mem, size);
	}
}

#if !(defined(NDEBUG) || !defined(KAFFE_VMDEBUG))
static int
gcClearCounts(Hjava_lang_Class *c, void *_ UNUSED)
{
	c->live_count = 0;
	return 0;
}

static int
gcDumpCounts(Hjava_lang_Class *c, void *_ UNUSED)
{
	if (c->live_count)
		dprintf("%7d %s\n", c->live_count,	c->name->data);
	return 0;
}
#endif /* !(defined(NDEBUG) || !defined(KAFFE_VMDEBUG)) */

/*
 * The Garbage Collector sits in a loop starting a collection, waiting
 * until it's finished incrementally, then tidying up before starting
 * another one.
 */
static void NONRETURNING
gcMan(void* arg)
{
	gc_unit* unit;
	gc_block* info;
	uintp idx;
	Collector *gcif = (Collector*)arg;