dvander@2226: #include <KePlatform.h>
dvander@2226: #include <assert.h>
dvander@2226: #include <string.h>
dvander@2226: 
dvander@2226: #if defined KE_PLATFORM_WINDOWS
dvander@2226: #include <windows.h>
dvander@2226: #elif defined KE_PLATFORM_POSIX
dvander@2226: #include <unistd.h>
dvander@2226: #include <stdlib.h>
dvander@2226: #include <sys/mman.h>
dvander@2226: #else
dvander@2226: #error "TODO"
dvander@2226: #endif
dvander@2226: 
dvander@2226: #include "KeCodeAllocator.h"
dvander@2226: 
dvander@2226: #define ALIGNMENT	16
dvander@2226: 
dvander@2226: using namespace Knight;
dvander@2226: 
dvander@2226: struct KeFreedCode;
dvander@2226: 
dvander@2226: /**
dvander@2226:  * Defines a region of memory that is made of pages. 
dvander@2226:  */
dvander@2226: struct KeCodeRegion
dvander@2226: {
dvander@2226: 	KeCodeRegion *next;
dvander@2226: 	unsigned char *block_start;
dvander@2226: 	unsigned char *block_pos;
dvander@2226: 	KeFreedCode *free_list;
dvander@2226: 	size_t total_size;
dvander@2226: 	size_t end_free;
dvander@2226: 	size_t total_free;
dvander@2226: };
dvander@2226: 
dvander@2226: /**
dvander@2226:  * Defines freed code.  We keep the size here because 
dvander@2226:  * when we touch the linked list we don't want to dirty pages.
dvander@2226:  */
dvander@2226: struct KeFreedCode
dvander@2226: {
dvander@2226: 	KeCodeRegion *region;
dvander@2226: 	unsigned char *block_start;
dvander@2226: 	size_t size;
dvander@2226: 	KeFreedCode *next;
dvander@2226: };
dvander@2226: 
dvander@2226: struct KeSecret
dvander@2226: {
dvander@2226: 	KeCodeRegion *region;
dvander@2226: 	size_t size;
dvander@2226: };
dvander@2226: 
dvander@2226: class Knight::KeCodeCache
dvander@2226: {
dvander@2226: public:
dvander@2226: 	/**
dvander@2226: 	 * First region that is live for use.
dvander@2226: 	 */
dvander@2226: 	KeCodeRegion *first_live;
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * First region that is full but has free entries.
dvander@2226: 	 */
dvander@2226: 	KeCodeRegion *first_partial;
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * First region that is full.
dvander@2226: 	 */
dvander@2226: 	KeCodeRegion *first_full;
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * Page granularity and size.
dvander@2226: 	 */
dvander@2226: 	unsigned int page_size;
dvander@2226: 	unsigned int page_granularity;
dvander@2226: 
dvander@2226: 	/**
dvander@2226: 	 * This isn't actually for code, this is the node cache.
dvander@2226: 	 */
dvander@2226: 	KeCodeRegion *node_cache;
dvander@2226: 	KeFreedCode *free_node_list;
dvander@2226: };
dvander@2226: 
dvander@2226: KeCodeCache *Knight::KE_CreateCodeCache()
dvander@2226: {
dvander@2226: 	KeCodeCache *cache;
dvander@2226: 
dvander@2226: 	cache = new KeCodeCache;
dvander@2226: 
dvander@2226: 	memset(cache, 0, sizeof(KeCodeCache));
dvander@2226: 
dvander@2226: #if defined KE_PLATFORM_WINDOWS
dvander@2226: 	SYSTEM_INFO info;
dvander@2226: 
dvander@2226: 	GetSystemInfo(&info);
dvander@2226: 	cache->page_size = info.dwPageSize;
dvander@2226: 	cache->page_granularity = info.dwAllocationGranularity;
dvander@2226: #else
dvander@2226: 	cache->page_size = cache->page_granularity = sysconf(_SC_PAGESIZE);
dvander@2226: #endif
dvander@2226: 
dvander@2226: 	return cache;
dvander@2226: }
dvander@2226: 
dvander@2226: inline size_t MinAllocSize()
dvander@2226: {
dvander@2226: 	size_t size;
dvander@2226: 
dvander@2226: 	size = sizeof(KeSecret);
dvander@2226: 	size += ALIGNMENT;
dvander@2226: 	size -= size % ALIGNMENT;
dvander@2226: 
dvander@2226: 	return size;
dvander@2226: }
dvander@2226: 
dvander@2226: inline size_t ke_GetAllocSize(size_t size)
dvander@2226: {
dvander@2226: 	size += sizeof(KeSecret);
dvander@2226: 	size += ALIGNMENT;
dvander@2226: 	size -= size % ALIGNMENT;
dvander@2226: 
dvander@2226: 	return size;
dvander@2226: }
dvander@2226: 
dvander@2226: void *ke_AllocInRegion(KeCodeCache *cache,
dvander@2226: 					   KeCodeRegion **prev,
dvander@2226: 					   KeCodeRegion *region,
dvander@2226: 					   unsigned char *ptr,
dvander@2226: 					   size_t alloc_size,
dvander@2226: 					   bool is_live)
dvander@2226: {
dvander@2226: 	KeSecret *secret;
dvander@2226: 
dvander@2226: 	/* Squirrel some info in the alloc. */
dvander@2226: 	secret = (KeSecret *)ptr;
dvander@2226: 	secret->region = region;
dvander@2226: 	secret->size = alloc_size;
dvander@2226: 	ptr += sizeof(KeSecret);
dvander@2226: 
dvander@2226: 	region->total_free -= alloc_size;
dvander@2226: 
dvander@2226: 	/* Check if we can't use the fast-path anymore. */
dvander@2226: 	if ((is_live && region->end_free < MinAllocSize())
dvander@2226: 		|| (!is_live && region->total_free < MinAllocSize()))
dvander@2226: 	{
dvander@2226: 		KeCodeRegion **start;
dvander@2226: 
dvander@2226: 		*prev = region->next;
dvander@2226: 
dvander@2226: 		/* Select the appropriate arena. */
dvander@2226: 		if (is_live)
dvander@2226: 		{
dvander@2226: 			if (region->total_free < MinAllocSize())
dvander@2226: 			{
dvander@2226: 				start = &cache->first_full;
dvander@2226: 			}
dvander@2226: 			else
dvander@2226: 			{
dvander@2226: 				start = &cache->first_partial;
dvander@2226: 			}
dvander@2226: 		}
dvander@2226: 		else
dvander@2226: 		{
dvander@2226: 			start = &cache->first_full;
dvander@2226: 		}
dvander@2226: 		
dvander@2226: 		region->next = *start;
dvander@2226: 		*start = region;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	return ptr;
dvander@2226: }
dvander@2226: 
dvander@2226: void *ke_AllocFromLive(KeCodeCache *cache, size_t size)
dvander@2226: {
dvander@2226: 	void *ptr;
dvander@2226: 	size_t alloc_size;
dvander@2226: 	KeCodeRegion *region, **prev;
dvander@2226: 
dvander@2226: 	region = cache->first_live;
dvander@2226: 	prev = &cache->first_live;
dvander@2226: 	alloc_size = ke_GetAllocSize(size);
dvander@2226: 
dvander@2226: 	while (region != NULL)
dvander@2226: 	{
dvander@2226: 		if (region->end_free >= alloc_size)
dvander@2226: 		{
dvander@2226: 			/* Yay! We can do a simple alloc here. */
dvander@2226: 			ptr = ke_AllocInRegion(cache, prev, region, region->block_pos, alloc_size, true);
dvander@2226: 
dvander@2226: 			/* Update our counters. */
dvander@2226: 			region->block_pos += alloc_size;
dvander@2226: 			region->end_free -= alloc_size;
dvander@2226: 
dvander@2226: 			return ptr;
dvander@2226: 		}
dvander@2226: 		prev = &region->next;
dvander@2226: 		region = region->next;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	return NULL;
dvander@2226: }
dvander@2226: 
dvander@2226: void *ke_AllocFromPartial(KeCodeCache *cache, size_t size)
dvander@2226: {
dvander@2226: 	void *ptr;
dvander@2226: 	size_t alloc_size;
dvander@2226: 	KeCodeRegion *region, **prev;
dvander@2226: 
dvander@2226: 	region = cache->first_partial;
dvander@2226: 	prev = &cache->first_partial;
dvander@2226: 	alloc_size = ke_GetAllocSize(size);
dvander@2226: 
dvander@2226: 	while (region != NULL)
dvander@2226: 	{
dvander@2226: 		if (region->total_free >= alloc_size)
dvander@2226: 		{
dvander@2226: 			KeFreedCode *node, **last;
dvander@2226: 
dvander@2226: 			assert(region->free_list != NULL);
dvander@2226: 
dvander@2226: 			last = &region->free_list;
dvander@2226: 			node = region->free_list;
dvander@2226: 			while (node != NULL)
dvander@2226: 			{
dvander@2226: 				if (node->size >= alloc_size)
dvander@2226: 				{
dvander@2226: 					/* Use this node */
dvander@2226: 					ptr = ke_AllocInRegion(cache, prev, region, node->block_start, alloc_size, false);
dvander@2226: 
dvander@2226: 					region->total_free -= node->size;
dvander@2226: 					*last = node->next;
dvander@2226: 
dvander@2226: 					/* Make sure bookkeepping is correct. */
dvander@2226: 					assert((region->free_list == NULL && region->total_free == 0)
dvander@2226: 						   || (region->free_list != NULL && region->total_free != 0));
dvander@2226: 
dvander@2226: 					/* Link us back into the free node list. */
dvander@2226: 					node->next = cache->free_node_list;
dvander@2226: 					cache->free_node_list = node->next;
dvander@2226: 
dvander@2226: 					return ptr;
dvander@2226: 				}
dvander@2226: 				last = &node->next;
dvander@2226: 				node = node->next;
dvander@2226: 			}
dvander@2226: 		}
dvander@2226: 		prev = &region->next;
dvander@2226: 		region = region->next;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	return NULL;
dvander@2226: }
dvander@2226: 
dvander@2226: KeCodeRegion *ke_AddRegionForSize(KeCodeCache *cache, size_t size)
dvander@2226: {
dvander@2226: 	KeCodeRegion *region;
dvander@2226: 
dvander@2226: 	region = new KeCodeRegion;
dvander@2226: 
dvander@2226: 	size = ke_GetAllocSize(size);
dvander@2226: 	size += cache->page_granularity * 2;
dvander@2226: 	size -= size % cache->page_granularity;
dvander@2226: 
dvander@2226: #if defined KE_PLATFORM_WINDOWS
dvander@2226: 	region->block_start = (unsigned char *)VirtualAlloc(NULL, size, MEM_COMMIT|MEM_RESERVE, PAGE_EXECUTE_READWRITE);
dvander@2226: #elif defined KE_PLATFORM_POSIX
dvander@2226: 	region->block_start = (unsigned char *)valloc(size);
dvander@2226: 	if (mprotect(region->block_start, size, PROT_READ|PROT_WRITE|PROT_EXEC) == -1)
dvander@2226: 	{
dvander@2226: 		free(region->block_start);
dvander@2226: 		delete region;
dvander@2226: 		return NULL;
dvander@2226: 	}
dvander@2226: #else
dvander@2226: #error "TODO"
dvander@2226: #endif
dvander@2226: 
dvander@2226: 	if (region->block_start == NULL)
dvander@2226: 	{
dvander@2226: 		delete region;
dvander@2226: 		return NULL;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	region->block_pos = region->block_start;
dvander@2226: 	region->end_free = region->total_free = region->total_size = size;
dvander@2226: 	region->next = cache->first_live;
dvander@2226: 	cache->first_live = region;
dvander@2226: 	region->free_list = NULL;
dvander@2226: 
dvander@2226: 	return region;
dvander@2226: }
dvander@2226: 
dvander@2226: void *Knight::KE_AllocCode(KeCodeCache *cache, size_t size)
dvander@2226: {
dvander@2226: 	void *ptr;
dvander@2226: 
dvander@2226: 	/* Check live easy-adds */
dvander@2226: 	if (cache->first_live != NULL)
dvander@2226: 	{
dvander@2226: 		if ((ptr = ke_AllocFromLive(cache, size)) != NULL)
dvander@2226: 		{
dvander@2226: 			return ptr;
dvander@2226: 		}
dvander@2226: 	}
dvander@2226: 	
dvander@2226: 	/* Try looking in the free lists */
dvander@2226: 	if (cache->first_partial != NULL)
dvander@2226: 	{
dvander@2226: 		if ((ptr = ke_AllocFromPartial(cache, size)) != NULL)
dvander@2226: 		{
dvander@2226: 			return ptr;
dvander@2226: 		}
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* Create a new region */
dvander@2226: 	if (ke_AddRegionForSize(cache, size) == NULL)
dvander@2226: 	{
dvander@2226: 		return NULL;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	return ke_AllocFromLive(cache, size);
dvander@2226: }
dvander@2226: 
dvander@2226: KeFreedCode *ke_GetFreeNode(KeCodeCache *cache)
dvander@2226: {
dvander@2226: 	KeFreedCode *ret;
dvander@2226: 
dvander@2226: 	if (cache->free_node_list != NULL)
dvander@2226: 	{
dvander@2226: 		ret = cache->free_node_list;
dvander@2226: 		cache->free_node_list = ret->next;
dvander@2226: 
dvander@2226: 		return ret;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* See if the current free node region has space. */
dvander@2226: 	if (cache->node_cache != NULL
dvander@2226: 		&& cache->node_cache->end_free >= sizeof(KeFreedCode))
dvander@2226: 	{
dvander@2226: 		ret = (KeFreedCode *)cache->node_cache->block_pos;
dvander@2226: 		cache->node_cache->block_pos += sizeof(KeFreedCode);
dvander@2226: 		cache->node_cache->total_free -= sizeof(KeFreedCode);
dvander@2226: 		cache->node_cache->end_free -= sizeof(KeFreedCode);
dvander@2226: 
dvander@2226: 		return ret;
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	/* Otherwise, we need to alloc a new region. */
dvander@2226: 	KeCodeRegion *region = new KeCodeRegion;
dvander@2226: 	
dvander@2226: 	region->block_start = new unsigned char[cache->page_size / sizeof(KeFreedCode)];
dvander@2226: 	region->block_pos = region->block_start + sizeof(KeFreedCode);
dvander@2226: 	region->total_size = cache->page_size / sizeof(KeFreedCode);
dvander@2226: 	region->total_free = region->end_free = (region->total_size - sizeof(KeFreedCode));
dvander@2226: 	region->free_list = NULL;
dvander@2226: 	region->next = cache->node_cache;
dvander@2226: 	cache->node_cache = region;
dvander@2226: 
dvander@2226: 	return (KeFreedCode *)region->block_start;
dvander@2226: }
dvander@2226: 
dvander@2226: void Knight::KE_FreeCode(KeCodeCache *cache, void *code)
dvander@2226: {
dvander@2226: 	KeSecret *secret;
dvander@2226: 	KeFreedCode *node;
dvander@2226: 	unsigned char *ptr;
dvander@2226: 	KeCodeRegion *region;
dvander@2226: 
dvander@2226: 	ptr = (unsigned char *)code;
dvander@2226: 	secret = (KeSecret *)(ptr - sizeof(KeSecret));
dvander@2226: 	region = secret->region;
dvander@2226: 	node = ke_GetFreeNode(cache);
dvander@2226: 	node->block_start = (unsigned char *)code;
dvander@2226: 	node->next = region->free_list;
dvander@2226: 	region->free_list = node;
dvander@2226: 	node->region = region;
dvander@2226: 	node->size = secret->size;
dvander@2226: }
dvander@2226: 
dvander@2226: KeCodeRegion *ke_DestroyRegion(KeCodeRegion *region)
dvander@2226: {
dvander@2226: 	KeCodeRegion *next;
dvander@2226: 
dvander@2226: 	next = region->next;
dvander@2226: 
dvander@2226: #if defined KE_PLATFORM_WINDOWS
dvander@2226: 	VirtualFree(region->block_start, 0, MEM_RELEASE);
dvander@2226: #else
dvander@2226: 	free(region->block_start);
dvander@2226: #endif
dvander@2226: 
dvander@2226: 	delete region;
dvander@2226: 
dvander@2226: 	return next;
dvander@2226: }
dvander@2226: 
dvander@2226: void ke_DestroyRegionChain(KeCodeRegion *first)
dvander@2226: {
dvander@2226: 	while (first != NULL)
dvander@2226: 	{
dvander@2226: 		first = ke_DestroyRegion(first);
dvander@2226: 	}
dvander@2226: }
dvander@2226: 
dvander@2226: void Knight::KE_DestroyCodeCache(KeCodeCache *cache)
dvander@2226: {
dvander@2226: 	/* Destroy every region and call it a day. */
dvander@2226: 	ke_DestroyRegionChain(cache->first_full);
dvander@2226: 	ke_DestroyRegionChain(cache->first_live);
dvander@2226: 	ke_DestroyRegionChain(cache->first_partial);
dvander@2226: 
dvander@2226: 	/* We use normal malloc for node cache regions */
dvander@2226: 	KeCodeRegion *region, *next;
dvander@2226: 	
dvander@2226: 	region = cache->node_cache;
dvander@2226: 	while (region != NULL)
dvander@2226: 	{
dvander@2226: 		next = region->next;
dvander@2226: 		delete [] region->block_start;
dvander@2226: 		delete region;
dvander@2226: 		region = next;
dvander@2226: 	}
dvander@2226: 	
dvander@2226: 	delete cache;
dvander@2226: }