gc-mem.c

基于LWVCL开发的库

gc_primitive_free(gc_block* mem)
{
	gc_block *blk;

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

	/* Remove from object hash */
	gc_block_rm(mem);

	DBG(GCPRIM, dprintf ("\ngc_primitive_free: freeing block %p (%x bytes, %x)\n", mem, mem->size, mem->size >> gc_pgbits); );

	/*
	 * Test whether this block is mergable with its successor.
	 * We need to do the gc_block_end check, since the heap may not be a continuous
	 * memory area and thus two consecutive blocks need not be mergable. 
	 */
	
        blk = mem->pnext;
	if ((blk != NULL) &&
	    !GCBLOCKINUSE(blk) &&
	    gc_block_end(mem)==blk) {
		DBG(GCPRIM, dprintf ("gc_primitive_free: merging %p with its successor (%p, %u)\n", mem, blk, blk->size););

		gc_remove_from_prim_freelist(blk);

		gc_merge_with_successor (mem);
	}

	blk = mem->pprev;
	if ((blk != NULL) &&
	    !GCBLOCKINUSE(blk) &&
	    gc_block_end(blk)==mem) {
		DBG(GCPRIM, dprintf ("gc_primitive_free: merging %p with its predecessor (%p, %u)\n", mem, blk, blk->size); );

		gc_remove_from_prim_freelist(blk);
		  
		mem = blk;

		gc_merge_with_successor (mem);
	}
	
	gc_add_to_prim_freelist (mem);

	DBG(GCPRIM, dprintf ("gc_primitive_free: added 0x%x bytes @ %p to freelist %u @ %p\n", mem->size, mem,
			     (unsigned int)(gc_get_prim_freelist(mem)-&gc_prim_freelist[0]), gc_get_prim_freelist(mem)); );
}

/*
 * Try to reserve some memory for OOM exception handling.  Gc once at
 * the beginning.  We start out looking for an arbitrary number of
 * pages, and cut our expectations in half until we are able to
 * meet them.
 */
void
gc_primitive_reserve(size_t numpages)
{
	gc_block *r = NULL;
	size_t size = numpages * gc_pgsize;

	if (gc_reserve_pages != NULL)
	        return;
	
	while (size >= gc_pgsize && !(r = gc_primitive_alloc(size))) {
		if (size == gc_pgsize) {
			break;
		}
		size /= 2;
	}
	/* As it is done just at the initialization it is expected to have at 
	 * least one page free */
	assert(r != NULL);
	gc_reserve_pages = r;
}

/*
 * We return the reserve to the heap if it has not been already used.
 * This function returns true if some reserve was still available.
 */
bool
gc_primitive_use_reserve()
{
        if (gc_reserve_pages == NULL)
	        return false;
	gc_primitive_free(gc_reserve_pages);
	gc_reserve_pages = NULL;

	return true;
}


/*
 * System memory management:  Obtaining additional memory from the
 * OS.  This looks more complicated than it is, since it does not require
 * sbrk.
 */
/* Get some page-aligned memory from the system. */
static uintp
pagealloc(size_t size)
{
	void* ptr;

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

#if defined(HAVE_SBRK) && !defined(DARWIN)

	/* Our primary choice for basic memory allocation is sbrk() which
	 * should avoid any unsee space overheads.
	 */
	for (;;) {
		int missed;
		ptr = sbrk((intp)size);
		if (ptr == (void*)-1) {
			ptr = NULL;
			break;
		}
		if ((uintp)ptr % gc_pgsize == 0) {
			break;
		}
		missed = gc_pgsize - ((uintp)ptr % gc_pgsize);
		DBG(GCSYSALLOC,
		    dprintf("unaligned sbrk %p, missed %d bytes\n",
			    ptr, missed));
		sbrk((intp)(-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) & (uintp)-gc_pgsize);

#endif
	mprotect(ptr, size, ALL_PROT);

	addToCounter(&gcpages, "gcmem-system pages", 1, size);
	return ((uintp) ptr);
}

/* Free memory allocated with pagealloc */
#ifdef HAVE_SBRK
static void pagefree(uintp base UNUSED, size_t size)
{
	sbrk((intp)-size);
}
#else
static void pagefree(uintp base, size_t size UNUSED)
{
	/* it must have been allocated with memalign, valloc or malloc */
	free((void *)base);
}
#endif

/*
 * Determine if ptr points inside the array of gc_block structures.
 *
 * @param ptr the pointer to check for
 * @param base a pointer to the start of the array
 * @param count the number of elements in the array
 */
static int
inside(void* ptr, gc_block* base, int count) {
        return ((gc_block*)ptr >= base && (gc_block*)ptr < base + count);
}


/*
 * Allocate size bytes of heap memory, and return the corresponding
 * gc_block *.
 */
static void *
gc_block_alloc(size_t size)
{
	int size_pg = (size>>gc_pgbits);
	uintp heap_addr;
	static uintp last_addr;

	if (!gc_block_base) {
		gc_num_blocks = (size+gc_pgsize-1)>>gc_pgbits;

		gc_block_base = malloc(gc_num_blocks * sizeof(gc_block));
		if (!gc_block_base) return NULL;
		memset(gc_block_base, 0, gc_num_blocks * sizeof(gc_block));
	}

	DBG(GCSYSALLOC, dprintf("pagealloc(%ld)", (long) size));
	heap_addr = pagealloc(size);
	DBG(GCSYSALLOC, dprintf(" => %p\n", (void *) heap_addr));

	if (!heap_addr) return NULL;
	
	if (!gc_heap_base) {
		gc_heap_base = heap_addr;
	}

	if (gc_mem2block((void *) (heap_addr + size))
	    > ((gc_block *)gc_block_base) + gc_num_blocks
	    || heap_addr < gc_heap_base) {
		char * old_blocks = gc_block_base;
		int onb = gc_num_blocks;
		unsigned int min_nb;	/* minimum size of array to hold heap_addr */
#if defined(KAFFE_STATS)
		static timespent growtime;
#endif

		startTiming(&growtime, "gctime-blockrealloc");
		/* Pick a new size for the gc_block array.  Remember,
		   malloc does not simply grow a memory segment.

		   We can extrapolate how many gc_blocks we need for
		   the entire heap based on how many heap pages
		   currently fit in the gc_block array.  But, we must
		   also make sure to allocate enough blocks to cover
		   the current allocation */
		gc_num_blocks = (gc_num_blocks * ((gc_heap_total + size) >> gc_pgbits))
			/ gc_num_live_pages;
		if (heap_addr < gc_heap_base) 
			min_nb = gc_num_blocks
			  + ((gc_heap_base - heap_addr) >> gc_pgbits);
		else
			min_nb = ((heap_addr + size) - gc_heap_base) >>
			  gc_pgbits;
		gc_num_blocks = MAX(gc_num_blocks, min_nb);
		DBG(GCSYSALLOC,
		    dprintf("growing block array from %d to %zu elements\n",
			    onb, gc_num_blocks));

		KTHREAD(spinon)(NULL);
		gc_block_base = realloc(old_blocks,
					gc_num_blocks * sizeof(gc_block));
		if (!gc_block_base) {
			/* In some implementations, realloc is not smart enough to acquire new block
			 * in a non-contiguous region. Even if internally it calls some malloc procedure
			 * it fails evenly. A countermeasure is to use slow real malloc if realloc fails
			 * and only if that call also fails we put throw a OOM.
			 */
			DBG(GCSYSALLOC, dprintf("realloc has failed. Trying malloc.\n"));
			gc_block_base = malloc(gc_num_blocks * sizeof(gc_block));
			if (!gc_block_base) {
				/* roll back this call */
				DBG(GCSYSALLOC, dprintf("failed to grow the block list\n"));
				pagefree(heap_addr, size);
				gc_block_base = old_blocks;
				gc_num_blocks = onb;
				KTHREAD(spinoff)(NULL);
				return NULL;
			}
			memcpy(gc_block_base, old_blocks, onb * sizeof(gc_block));
			free(old_blocks);
		}
		DBG(GCSYSALLOC, dprintf("old block_base = %p, new block_base = %p\n", old_blocks, gc_block_base));
		if (heap_addr < gc_heap_base) {
		  int32 i, j, oldBase;
		  gc_block *b = (gc_block *) gc_block_base;

		  oldBase = (gc_heap_base - heap_addr) >> gc_pgbits;

		  for (i=(onb-1),j=(oldBase+onb-1); i >= 0; i--,j--)
		  	memcpy(&b[j], &b[i], sizeof(gc_block));

		  memset((gc_block *)gc_block_base, 0,
		         (gc_num_blocks - onb) * sizeof(gc_block));
		} else {
		  memset(((gc_block *)gc_block_base) + onb, 0,
		         (gc_num_blocks - onb) * sizeof(gc_block));
		}
		/* If the array's address has changed, we have to fix
		   up the pointers in the gc_blocks, as well as all
		   external pointers to the gc_blocks.  We can only
		   fix gc_prim_freelist and the size-freelist array.
		   There should be no gc_block *'s on any stack
		   now. */ 
		if (gc_block_base != old_blocks) {
			int i;
			gc_block *b = (gc_block *) gc_block_base;
			uintp delta = gc_block_base - old_blocks;
#define R(type,X) if (X) X = (type*)((uintp)X + delta)

			DBG(GCSYSALLOC,
			    dprintf("relocating gc_block array\n"));
			for (i = 0; i < onb; i++) 
			  {
			    R(gc_block, b[i].next);
			    R(gc_block, b[i].pprev);
			    R(gc_block, b[i].pnext);
                            if (inside(b[i].free, (gc_block*)old_blocks, onb))
				R(gc_freeobj, b[i].free);
			  }

			for (i = 0; i<=KGC_PRIM_LIST_COUNT; i++)
				R(gc_block, gc_prim_freelist[i]);

			for (i = 0; freelist[i].list != (void*)-1; i++) 
				R(gc_block, freelist[i].list);

			R(gc_block, gc_reserve_pages);
			R(gc_block, gc_last_block);
			R(gc_block, gc_first_block);
#undef R
		}
		KTHREAD(spinoff)(NULL);
		stopTiming(&growtime);
	}
	gc_num_live_pages += size_pg;
	last_addr = MAX(last_addr, heap_addr + size);
	gc_heap_range = last_addr - gc_heap_base;
	if (gc_heap_base > heap_addr)
	  gc_heap_base = heap_addr;

	DBG(GCSYSALLOC, dprintf("%ld unused bytes in heap addr range\n",
				(long) (gc_heap_range - gc_heap_total)));
#if defined(KAFFE_VMDEBUG)
	mprotect((void *) heap_addr, size, NO_PROT);
#endif
	return gc_mem2block((void *) heap_addr);
}

/**
 * Grows the heap.
 *
 * @param sz minimum number of bytes to grow.
 * @return 0 in case of an error, otherwise != 0
 */
void *
gc_heap_grow(size_t sz)
{
	gc_block* blk;

	if (KGC_SMALL_OBJECT(sz)) {
		sz = gc_pgsize;
	} else {
		sz = sz + 2 + ROUNDUPALIGN(1);
		sz = ROUNDUPPAGESIZE(sz);
	}

	if (sz < gc_heap_allocation_size) {
		sz = gc_heap_allocation_size;
	}

	assert(sz % gc_pgsize == 0);

	lockStaticMutex(&gc_heap_lock);

	if (gc_heap_total == gc_heap_limit) {
		unlockStaticMutex(&gc_heap_lock);
		return (NULL);
	} else if (gc_heap_total + sz > gc_heap_limit && !gc_heap_is_unlimited()) {
		/* take as much memory as we can */
		sz = gc_heap_limit - gc_heap_total;
		assert(sz % gc_pgsize == 0);
		DBG(GCSYSALLOC, dprintf("allocating up to limit\n"));
	}
#ifdef KAFFE_VMDEBUG
	gc_system_alloc_cnt++;
#endif

	blk = gc_block_alloc(sz);

	DBG(GCSYSALLOC,
	    dprintf("gc_system_alloc: %ld byte at %p\n", (long) sz, blk); );

	if (blk == NULL) {
		unlockStaticMutex(&gc_heap_lock);
		return (NULL);
	}

	gc_heap_total += sz;
	assert(gc_heap_total <= gc_heap_limit || gc_heap_is_unlimited());

	/* Place block into the freelist for subsequent use */
	DBG(GCDIAG, gc_set_magic_marker(blk));
	blk->size = sz;

	/* maintain list of primitive blocks */
	if (gc_last_block) {
		if (gc_last_block < blk) {
			gc_last_block->pnext = blk;
			blk->pprev = gc_last_block;
		} else {
			assert(gc_first_block->pprev == NULL);
			gc_first_block->pprev = blk;
			blk->pnext = gc_first_block;
			gc_first_block = blk;
		}
	}
	
	gc_last_block = blk;

	/* Free block into the system */
	blk->nr = 1;
	gc_primitive_free(blk);

	unlockStaticMutex(&gc_heap_lock);

	return (blk);
}

/**
 * Evaluates to the gc_block that contains address @mem.
 *
 */
gc_block *
gc_mem2block(const void * mem) 
{
  return (KGC_BLOCKS + ( ( ((uintp) (mem)) - gc_heap_base) >> gc_pgbits));
}

/**
 * Gets current heap size.
 */
size_t
gc_get_heap_total(void)
{
  return gc_heap_total;
}

/**
 * Gets maximum size to which heap should grow.
 */
size_t
gc_get_heap_limit(void)
{
  return gc_heap_limit;
}

/**
 * Gets start of the heap.
 */
uintp
gc_get_heap_base(void)
{
  return gc_heap_base;
}

/**
 * Gets last gc-able address - start of the heap.
 */
uintp
gc_get_heap_range(void)
{
  return gc_heap_range;
}