/* 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 inlinevoid 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 voidregisterTypeByIndex(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 voidgcRegisterFixedTypeByIndex(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 voidgcRegisterGcTypeByIndex(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 intgc_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 voidmarkObjectDontCheck(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 voidgcMarkAddress(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 voidgcMarkObject(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));}voidKaffeGC_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. */staticuint32gcGetObjectSize(Collector* gcif UNUSED, const void* mem){	return (GCBLOCKSIZE(gc_mem2block(UTOUNIT(mem))));}staticgc_alloc_type_tgcGetObjectIndex(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. */staticvoid*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);}staticconst char*gcGetObjectDescription(Collector* gcif, const void* mem){	return (gcFunctions[gcGetObjectIndex(gcif, mem)].description);}/* * Walk a bit of memory. */voidKaffeGC_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 intgcClearCounts(Hjava_lang_Class *c, void *_ UNUSED){	c->live_count = 0;	return 0;}static intgcDumpCounts(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 NONRETURNINGgcMan(void* arg){	gc_unit* unit;	gc_block* info;	uintp idx;	Collector *gcif = (Collector*)arg;