dvander@2226: #include "KePlatform.h"
dvander@2226: #include <KeLumpAllocator.h>
dvander@2226: #include <KeVector.h>
dvander@2226: 
dvander@2226: using namespace Knight;
dvander@2226: 
dvander@2226: /**
dvander@2226:  * :TODO: don't make this part of the page, because touching it means 
dvander@2226:  * dirtying a page.  Instead, we should have a separate linked list.
dvander@2226:  * Maybe that linked list itself could be marshalled from one page.
dvander@2226:  */
dvander@2226: struct KeLumpRegion
dvander@2226: {
dvander@2226: 	char *base;
dvander@2226: 	char *cur;
dvander@2226: 	size_t size;
dvander@2226: 	size_t avail;
dvander@2226: 	KeLumpRegion *next;
dvander@2226: 	KeLumpRegion *prev;
dvander@2226: };
dvander@2226: 
dvander@2226: class KeLumpAllocator
dvander@2226: {
dvander@2226: public:
dvander@2226: 	KeLumpAllocator() : m_pUsableRegions(NULL), m_pUnusableRegions(NULL)
dvander@2226: 	{
dvander@2226: 		m_DefLumpSize = 65536;
dvander@2226: 
dvander@2226: #if defined KE_PLATFORM_WINDOWS
dvander@2226: 		SYSTEM_INFO info;
dvander@2226: 
dvander@2226: 		GetSystemInfo(&info);
dvander@2226: 		if (info.dwAllocationGranularity > m_DefLumpSize)
dvander@2226: 		{
dvander@2226: 			m_DefLumpSize = info.dwAllocationGranularity;
dvander@2226: 		}
dvander@2226: #endif
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	~KeLumpAllocator()
dvander@2226: 	{
dvander@2226: 		FreeRegionChain(m_pUsableRegions);
dvander@2226: 		FreeRegionChain(m_pUnusableRegions);
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	void Reset()
dvander@2226: 	{
dvander@2226: 		KeLumpRegion *region;
dvander@2226: 
dvander@2226: 		/* Find the tail of the usable regions. */
dvander@2226: 		region = m_pUsableRegions;
dvander@2226: 		while (region != NULL)
dvander@2226: 		{
dvander@2226: 			if (region->next == NULL)
dvander@2226: 			{
dvander@2226: 				break;
dvander@2226: 			}
dvander@2226: 		}
dvander@2226: 
dvander@2226: 		/* Link the unusable chain into the usable chain. */
dvander@2226: 		if (region == NULL)
dvander@2226: 		{
dvander@2226: 			m_pUsableRegions = m_pUnusableRegions;
dvander@2226: 		}
dvander@2226: 		else
dvander@2226: 		{
dvander@2226: 			region->next = m_pUnusableRegions;
dvander@2226: 			m_pUnusableRegions->prev = region;
dvander@2226: 		}
dvander@2226: 		m_pUnusableRegions = NULL;
dvander@2226: 
dvander@2226: 		region = m_pUsableRegions;
dvander@2226: 		while (region != NULL)
dvander@2226: 		{
dvander@2226: 			region->avail = region->size;
dvander@2226: 			region->cur = region->base;
dvander@2226: 			region = region->next;
dvander@2226: 		}
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	void FreeRegionChain(KeLumpRegion *region)
dvander@2226: 	{
dvander@2226: 		KeLumpRegion *next;
dvander@2226: 
dvander@2226: 		while (region != NULL)
dvander@2226: 		{
dvander@2226: 			next = region->next;
dvander@2226: 			
dvander@2226: #if defined KE_PLATFORM_WINDOWS
dvander@2226: 			VirtualFree(region, 0, MEM_RELEASE);
dvander@2541: #else
dvander@2541:             free(region);
dvander@2226: #endif
dvander@2226: 			region = next;
dvander@2226: 		}
dvander@2226: 	}
dvander@2226: 
dvander@2226: 	void *Alloc(size_t size)
dvander@2226: 	{
dvander@2226: 		char *blob;
dvander@2226: 		KeLumpRegion *region;
dvander@2226: 
dvander@2226: 		if (size % 8 != 0)
dvander@2226: 		{
dvander@2226: 			size += 8;
dvander@2226: 			size -= size % 8;
dvander@2226: 		}
dvander@2226: 
dvander@2226: 		region = FindRegionForSize(size);
dvander@2226: 
dvander@2226: 		blob = region->cur;
dvander@2226: 		region->avail -= size;
dvander@2226: 		region->cur += size;
dvander@2226: 
dvander@2226: 		/** 
dvander@2226: 		 * Technically we could make one last small allocation, but 
dvander@2226: 		 * this edge case is not worth the extra work.
dvander@2226: 		 */
dvander@2226: 		if (region->avail < 8)
dvander@2226: 		{
dvander@2226: 			/* Unlink us from the usable list */
dvander@2226: 			if (region == m_pUsableRegions)
dvander@2226: 			{
dvander@2226: 				m_pUsableRegions = m_pUsableRegions->next;
dvander@2226: 				m_pUsableRegions->prev = NULL;
dvander@2226: 			}
dvander@2226: 			else
dvander@2226: 			{
dvander@2226: 				region->prev->next = region->next;
dvander@2226: 				if (region->next != NULL)
dvander@2226: 				{
dvander@2226: 					region->next->prev = region->prev;
dvander@2226: 				}
dvander@2226: 			}
dvander@2226: 
dvander@2226: 			/* Link us into the unusable list */
dvander@2226: 			region->prev = NULL;
dvander@2226: 			region->next = m_pUnusableRegions;
dvander@2226: 
dvander@2226: 			if (m_pUnusableRegions != NULL)
dvander@2226: 			{
dvander@2226: 				m_pUnusableRegions->prev = region;
dvander@2226: 			}
dvander@2226: 
dvander@2226: 			m_pUnusableRegions = region;
dvander@2226: 		}
dvander@2226: 
dvander@2226: 		return blob;
dvander@2226: 	}
dvander@2226: 
dvander@2226: private:
dvander@2226: 	KeLumpRegion *FindRegionForSize(size_t size)
dvander@2226: 	{
dvander@2226: 		char *base;
dvander@2226: 		KeLumpRegion *region;
dvander@2226: 		size_t size_of_region;
dvander@2226: 
dvander@2226: 		/**
dvander@2226: 		 * :TODO: replace this with a priority queue or something 
dvander@2226: 		 * that's actually fast.  Even worse is we dirty pages by 
dvander@2226: 		 * doing this.  Ouch!
dvander@2226: 		 */
dvander@2226: 		region = m_pUsableRegions;
dvander@2226: 		while (region != NULL)
dvander@2226: 		{
dvander@2226: 			if (region->avail >= size)
dvander@2226: 			{
dvander@2226: 				return region;
dvander@2226: 			}
dvander@2226: 			region = region->next;
dvander@2226: 		}
dvander@2226: 
dvander@2226: 		/* Make sure regions end at 8-byte alignment. */
dvander@2226: 		size_of_region = sizeof(KeLumpRegion);
dvander@2226: 		if (size_of_region % 8 != 0)
dvander@2226: 		{
dvander@2226: 			size_of_region += 8;
dvander@2226: 			size_of_region -= size_of_region % 8;
dvander@2226: 		}
dvander@2226: 
dvander@2226: 		/* If the size is too big, fix that. */
dvander@2226: 		if (size > m_DefLumpSize - size_of_region)
dvander@2226: 		{
dvander@2226: 			size += m_DefLumpSize;
dvander@2226: 			size -= size % m_DefLumpSize;
dvander@2226: 		}
dvander@2226: 		else
dvander@2226: 		{
dvander@2226: 			size = m_DefLumpSize;
dvander@2226: 		}
dvander@2226: 
dvander@2226: #if defined KE_PLATFORM_WINDOWS
dvander@2226: 		base = (char *)VirtualAlloc(
dvander@2226: 			NULL,
dvander@2226: 			m_DefLumpSize,
dvander@2226: 			MEM_COMMIT|MEM_RESERVE,
dvander@2226: 			PAGE_READWRITE);
dvander@2541: #else
dvander@2541:         base = (char*)valloc(m_DefLumpSize);
dvander@2226: #endif
dvander@2226: 
dvander@2226: 		/* Initialize the region */
dvander@2226: 		region = (KeLumpRegion *)base;
dvander@2226: 		region->base = &base[size_of_region];
dvander@2226: 		region->size = size - size_of_region;
dvander@2226: 		region->cur = region->base;
dvander@2226: 		region->avail = region->size;
dvander@2226: 		region->prev = NULL;
dvander@2226: 		region->next = m_pUsableRegions;
dvander@2226: 
dvander@2226: 		if (m_pUsableRegions != NULL)
dvander@2226: 		{
dvander@2226: 			m_pUsableRegions->prev = region;
dvander@2226: 		}
dvander@2226: 
dvander@2226: 		m_pUsableRegions = region;
dvander@2226: 
dvander@2226: 		return region;
dvander@2226: 	}
dvander@2226: 
dvander@2226: private:
dvander@2226: 	KeLumpRegion *m_pUsableRegions;
dvander@2226: 	KeLumpRegion *m_pUnusableRegions;
dvander@2226: 	size_t m_DefLumpSize;
dvander@2226: };
dvander@2226: 
dvander@2226: inline KeLumpAllocator *ke_LumpFromAllocator(ke_allocator_t *arena)
dvander@2226: {
dvander@2226: 	return (KeLumpAllocator *)arena->user;
dvander@2226: }
dvander@2226: 
dvander@2226: void *ke_LumpAlloc(ke_allocator_t *arena, size_t size)
dvander@2226: {
dvander@2226: 	return ke_LumpFromAllocator(arena)->Alloc(size);
dvander@2226: }
dvander@2226: 
dvander@2226: void ke_LumpFree(ke_allocator_t *arena, void *ptr)
dvander@2226: {
dvander@2226: }
dvander@2226: 
dvander@2226: ke_allocator_t * KE_LINK Knight::KE_CreateLumpAllocator()
dvander@2226: {
dvander@2226: 	ke_allocator_t *alloc;
dvander@2226: 
dvander@2226: 	alloc = new ke_allocator_t;
dvander@2226: 	alloc->alloc = ke_LumpAlloc;
dvander@2226: 	alloc->dealloc = ke_LumpFree;
dvander@2226: 	alloc->user = new KeLumpAllocator();
dvander@2226: 
dvander@2226: 	return alloc;
dvander@2226: }
dvander@2226: 
dvander@2226: void KE_LINK Knight::KE_DestroyLumpAllocator(ke_allocator_t *alloc)
dvander@2226: {
dvander@2226: 	delete ke_LumpFromAllocator(alloc);
dvander@2226: 	delete alloc;
dvander@2226: }
dvander@2226: 
dvander@2226: void KE_LINK Knight::KE_ResetLumpAllocator(ke_allocator_t *alloc)
dvander@2226: {
dvander@2226: 	ke_LumpFromAllocator(alloc)->Reset();
dvander@2226: }
dvander@2541: