/* gc-mem.c
 * The heap manager.
 *
 * Copyright (c) 1997 T. J. Wilkinson & Associates, London, UK.
 *
 * See the file "license.terms" for information on usage and redistribution
 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
 *
 * Written by Tim Wilkinson <tim@tjwassoc.co.uk>
 */

#define	ADBG(s)
#define	FDBG(s)
#define	SADBG(s)
#define	FSDBG(s)
#define	SYSDBG(s)
#define	SDBG(s)

#include "config.h"
#include "config-std.h"
#include "config-mem.h"
#include "gtypes.h"
#include "locks.h"
#include "gc-mem.h"
#include "gc.h"

static gc_block* gc_small_block(size_t);
static gc_block* gc_large_block(size_t);

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

static gc_block* freelist[NR_FREELISTS+1];
static struct {
	uint16	list;
	uint16	sz;
} sztable[MAX_SMALL_OBJECT_SIZE+1];
static int max_freelist;

static gc_block* gc_prim_freelist;
static gc_block* gc_objecthash[GC_OBJECT_HASHSIZE];
static size_t max_small_object_size;

size_t gc_heap_total;
size_t gc_heap_allocation_size;
size_t gc_heap_limit;
size_t gc_pgsize;

extern struct Hjava_lang_Thread* garbageman;

static void* pagealloc(size_t);
extern void throwOutOfMemory(void);


/*
 * Initialise allocator.
 */
static
void
gc_heap_initialise(void)
{
	int i;
	int l;
	int b;
	int t;

	gc_pgsize = getpagesize();
	gc_heap_allocation_size = ALLOC_HEAPSIZE;
	gc_heap_limit = MAX_HEAPSIZE;

#define	OBJSIZE(NR) \
	((gc_pgsize - sizeof(gc_block) - ROUNDUPALIGN(1) - (NR * (1+sizeof(gcFuncs*)))) / 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].sz = l;
			}
			l = t;
			i <<= 1;
		}
		else {
			for (t = l; t > MIN_OBJECT_SIZE; t--) {
				sztable[t].sz = l;
			}
			for (t = 0; t <= MIN_OBJECT_SIZE; t++) {
				sztable[t].sz = 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].sz != b) {
			b = sztable[l].sz;
			i++;
		}
		sztable[l].list = i;
	}
	max_freelist = i;

#undef	OBJSIZE

	/* Round 'gc_heap_allocation_size' up to pagesize */
	gc_heap_allocation_size = ROUNDUPPAGESIZE(gc_heap_allocation_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;

	/* Initialise GC heap first time in */
	if (gc_heap_init == 0) {
		gc_heap_init = 1;
		gc_heap_initialise();
	}

	times = 0;

	rerun:;
	times++;

	if (GC_SMALL_OBJECT(sz)) {

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

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

ADBG(			printf("gc_heap_malloc: small block %d at %p\n", sz, *mptr);)
		}

		/* Unlink free one and return it */
		mem = blk->free;
#if defined(GC_DEBUG)
		assert(blk->magic == GC_MAGIC);
		assert((uintp)mem >= (uintp)blk &&
			(uintp)mem < (uintp)blk + gc_pgsize);
		assert(mem->next == 0 || ((uintp)mem->next >= (uintp)blk &&
			(uintp)mem->next < (uintp)blk + gc_pgsize));
#endif
		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->avail > 0);
		blk->avail--;
		if (blk->avail == 0) {
			*mptr = blk->nfree;
		}
	}
	else {
		nsz = sz;
		blk = gc_large_block(nsz);
		if (blk == 0) {
			nsz = nsz + sizeof(gc_block) + sizeof(gcFuncs*) + ROUNDUPALIGN(1);
			nsz = ROUNDUPPAGESIZE(nsz);
			goto nospace;
		}
		mem = GCBLOCK2FREE(blk, 0);
		GC_SET_STATE(blk, 0, GC_STATE_NORMAL);
ADBG(		printf("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);
	return (mem);

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

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

SDBG(	printf("Demanding %d ...\n", sz);				)

	switch (times) {
	case 1:
		/* Try invoking GC, but only if we've got some heap and
		 * the GC is available.
		 */
		if (gc_heap_total > 0 && garbageman != 0) {
			invokeGC();
		}
		break;

	case 2:
		/* Get from the system */
		if (nsz < gc_heap_allocation_size) {
			nsz = gc_heap_allocation_size;
		}
		blk = gc_system_alloc(nsz);
		if (blk != 0) {
			/* Place block into the freelist for subsequent use */
#if defined(GC_DEBUG)
			blk->magic = GC_MAGIC;
#endif
			blk->size = nsz;

			/* Attach block to object hash */
			lnr = GC_OBJECT_HASHIDX(blk);
			blk->next = gc_objecthash[lnr];
			gc_objecthash[lnr] = blk;

			/* Free block into the system */
			gc_primitive_free(blk);
		}
SDBG(		objectStatsPrint();	/* XXX */			)
		break;

	default:
		/* Guess we've really run out */
		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);
#if defined(GC_DEBUG)
	assert(info->magic == GC_MAGIC);
#endif
	GC_SET_COLOUR(info, idx, GC_COLOUR_FREE);

FDBG(	printf("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->nfree = freelist[lnr];
			freelist[lnr] = info;
		}
		info->avail++;
		obj = GCMEM2FREE(mem);
		obj->next = info->free;
		info->free = obj;

#if defined(GC_DEBUG)
		assert((uintp)obj >= (uintp)info &&
			(uintp)obj < (uintp)info + gc_pgsize);
#endif

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

/*
 * 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 - sizeof(gc_block) - ROUNDUPALIGN(1)) / (sz + sizeof(gcFuncs*) + 1);

	/* Setup the meta-data for the block */
#if defined(GC_DEBUG)
	info->magic = GC_MAGIC;
#endif
	info->size = sz;
	info->nr = nr;
	info->avail = nr;
	info->funcs = (gcFuncs**)(info + 1);
	info->state = (uint8*)(info->funcs + nr);
	info->data = (uint8*)ROUNDUPALIGN(info->state + nr);
	info->cprev = 0;
	info->cnext = 0;

#if defined(GC_DEBUG)
	memset(info->data, 0, sz * nr);
#endif

	/* Build the objects into a free list */
	for (i = nr-1; i >= 0; i--) {
		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;
	info->free = GCBLOCK2FREE(info, 0);

	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 + sizeof(gc_block) + sizeof(gcFuncs*) + 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 */
#if defined(GC_DEBUG)
	info->magic = GC_MAGIC;
#endif
	info->size = sz;
	info->nr = 1;
	info->avail = 1;
	info->funcs = (gcFuncs**)(info + 1);
	info->state = (uint8*)(info->funcs + 1);
	info->data = (uint8*)ROUNDUPALIGN(info->state + 1);
	info->cprev = 0;
	info->cnext = 0;
	info->free = 0;

#if defined(GC_DEBUG)
	memset(info->data, 0, sz);
#endif

	GCBLOCK2FREE(info, 0)->next = 0;
	GC_SET_COLOUR(info, 0, GC_COLOUR_FREE);
	GC_SET_STATE(info, 0, GC_STATE_NORMAL);

	return (info);
}

/*
 * Allocate a block of memory from the free list or, failing that, the
 * system pool.
 */
static
gc_block*
gc_primitive_alloc(size_t sz)
{
	gc_block* ptr;
	gc_block** pptr;
	int hidx;
	size_t bsz;

	assert(sz % gc_pgsize == 0);

	for (pptr = &gc_prim_freelist; *pptr != 0; pptr = &ptr->next) {
		ptr = *pptr;
		/* First fit */
		if (sz <= ptr->size) {
			size_t left;
			/* If there's more than a page left, split it */
			left = ptr->size - sz;
			if (left >= gc_pgsize) {
				gc_block* nptr;

				ptr->size = sz;
				nptr = GCBLOCKEND(ptr);
				nptr->size = left;
#if defined(GC_DEBUG)
				nptr->magic = GC_MAGIC;
#endif
				nptr->next = ptr->next;
				ptr->next = nptr;
			}
			*pptr = ptr->next;
SADBG(			printf("gc_primitive_alloc: %d bytes from freelist @ %p\n", ptr->size, ptr); )
			hidx = GC_OBJECT_HASHIDX(ptr);
			ptr->next = gc_objecthash[hidx];
			gc_objecthash[hidx] = ptr;
			return (ptr);
		}
	}

	/* Nothing found on free list */
	return (0);
}

/*
 * Return a block of memory to the free list.
 */
static
void
gc_primitive_free(gc_block* mem)
{
	gc_block* lptr;
	gc_block* nptr;
	int hidx;

	assert(mem->size % gc_pgsize == 0);

	/* Remove from object hash */
	hidx = GC_OBJECT_HASHIDX(mem);
	if (gc_objecthash[hidx] == mem) {
		gc_objecthash[hidx] = mem->next;
	}
	else {
		for (lptr = gc_objecthash[hidx]; lptr->next != 0; lptr = lptr->next) {
			if (lptr->next == mem) {
				lptr->next = mem->next;
				goto found;
			}
		}
		assert("Failed to find freeing block in object hash" == 0);
		found:;
	}
	mem->next = 0;

	if(mem < gc_prim_freelist || gc_prim_freelist == 0) {
		/* If this block is directly before the first block on the
		 * freelist, merge it into that block.  Otherwise just
		 * attached it to the beginning.
		 */
		if (GCBLOCKEND(mem) == gc_prim_freelist) {
FSDBG(			printf("gc_primitive_free: Merging (%d,%p) beginning of freelist\n", mem->size, mem); )
			mem->size += gc_prim_freelist->size;
			mem->next = gc_prim_freelist->next;
		}
		else {
FSDBG(			printf("gc_primitive_free: Prepending (%d,%p) beginning of freelist\n", mem->size, mem); )
			mem->next = gc_prim_freelist;
		}
		gc_prim_freelist = mem;
		return;
	}

	/* Search the freelist for the logical place to put this block */
	lptr = gc_prim_freelist;
	while (lptr->next != 0) {
		nptr = lptr->next;
		if (mem > lptr && mem < nptr) {
			/* Block goes here in the logical scheme of things.
			 * Work out how to merge it with those which come
			 * before and after.
			 */
			if (GCBLOCKEND(lptr) == mem) {
				if (GCBLOCKEND(mem) == nptr) {
					/* Merge with last and next */
FSDBG(					printf("gc_primitive_free: Merging (%d,%p) into list\n", mem->size, mem); )
					lptr->size += mem->size + nptr->size;
					lptr->next = nptr->next;
				}
				else {
					/* Merge with last but not next */
FSDBG(					printf("gc_primitive_free: Merging (%d,%p) with last in list\n", mem->size, mem); )
					lptr->size += mem->size;
				}
			}
			else {
				if (GCBLOCKEND(mem) == nptr) {
					/* Merge with next but not last */
FSDBG(					printf("gc_primitive_free: Merging (%d,%p) with next in list\n", mem->size, mem); )
					mem->size += nptr->size;
					mem->next = nptr->next;
					lptr->next = mem;
				}
				else {
					/* Wont merge with either */
FSDBG(					printf("gc_primitive_free: Inserting (%d,%p) into list\n", mem->size, mem); )
					mem->next = nptr;
					lptr->next = mem;
				}
			}
			return;
		}
		lptr = nptr;
	}

	/* If 'mem' goes directly after the last block, merge it in.
	 * Otherwise, just add in onto the list at the end.
	 */
	if (GCBLOCKEND(lptr) == mem) {
FSDBG(		printf("gc_primitive_free: Merge (%d,%p) onto last in list\n", mem->size, mem); )
		lptr->size += mem->size;
	}
	else {
FSDBG(		printf("gc_primitive_free: Append (%d,%p) onto last in list\n", mem->size, mem); )
		lptr->next = mem;
	}
}

/*
 * Is object a valid bit of GC'ed memory?
 */
bool
gc_heap_isobject(void* mem)
{
	gc_block* info;
	gc_block* hptr;
	uintp hidx;

	/* Get block info for this memory - if it exists */
	info = GCMEM2BLOCK(mem);

	/* Get hash index for this block */
	hidx = GC_OBJECT_HASHIDX(info);
	for (hptr = gc_objecthash[hidx]; hptr != 0; hptr = hptr->next) {
		if (hptr == info) {
			/* Make sure 'mem' refers to the beginning of an
			 * object.  We do this by making sure it is correctly
			 * aligned within the block.
			 */
			hidx = GCMEM2IDX(info, mem);
			if (hidx < info->nr && GCBLOCK2MEM(info, hidx) == mem && (GC_GET_COLOUR(info, hidx) & GC_COLOUR_INUSE) == GC_COLOUR_INUSE) {
				return (true);
			}
			else {
				return (false);
			}
		}
	}

	/* Not found */
	return (false);
}

static
void*
gc_system_alloc(size_t sz)
{
	void* mem;

	assert(sz % gc_pgsize == 0);

	/* If we will pass the heap boundary, return 0 to indicate that
	 * we're run out.
	 */
	if (gc_heap_total <= gc_heap_limit && gc_heap_total + sz > gc_heap_limit) {
		gc_heap_total += sz;
		return (0);
	}
	gc_heap_total += sz;

	mem = pagealloc(sz);

SYSDBG(	printf("gc_system_alloc: %d byte at %p\n", sz, mem);		)

	return (mem);
}

/* --------------------------------------------------------------------- */

void*
pagealloc(size_t size)
{
	void* ptr;

#define	CHECK_OUT_OF_MEMORY(P)	if ((P) == 0) throwOutOfMemory();

#if defined(HAVE_SBRK)

	/* Our primary choice for basic memory allocation is sbrk() which
	 * should avoid any unsee space overheads.
	 */
	for (;;) {
		int missed;
		ptr = sbrk(size);
		if ((uintp)ptr % gc_pgsize == 0) {
			break;
		}
		missed = gc_pgsize - ((uintp)ptr % gc_pgsize);
		sbrk(-size + missed);
	}
	CHECK_OUT_OF_MEMORY(ptr);

#elif defined(HAVE_MEMALIGN)

        ptr = memalign(gc_pgsize, size);
	CHECK_OUT_OF_MEMORY(ptr);

#elif defined(HAVE_VALLOC)

        ptr = valloc(size);
	CHECK_OUT_OF_MEMORY(ptr);

#else

	/* Fallback ...
	 * Allocate memory using malloc and align by hand.
	 */
	size += gc_pgsize;
        ptr = malloc(size);
	CHECK_OUT_OF_MEMORY(ptr);
	ptr = (void*)((((uintp)ptr) + gc_pgsize - 1) & -gc_pgsize);

#endif

	return (ptr);
}