--- /dev/null
+/*\r
+AcessOS Basic LibC\r
+heap.c - Heap Manager\r
+*/\r
+#include <acess/sys.h>\r
+#include <stdlib.h>\r
+#include "lib.h"\r
+\r
+// === Constants ===\r
+#define MAGIC 0xACE55051 //AcessOS1\r
+#define MAGIC_FREE (~MAGIC)\r
+#define BLOCK_SIZE 16 //Minimum\r
+#define HEAP_INIT_SIZE 0x10000\r
+\r
+typedef unsigned int Uint;\r
+\r
+//Typedefs\r
+typedef struct {\r
+ Uint magic;\r
+ Uint size;\r
+} heap_head;\r
+typedef struct {\r
+ heap_head *header;\r
+ Uint magic;\r
+} heap_foot;\r
+\r
+//Globals\r
+void *_heap_start = NULL;\r
+void *_heap_end = NULL;\r
+\r
+//Prototypes\r
+EXPORT void *malloc(Uint bytes);\r
+EXPORT void free(void *mem);\r
+EXPORT void *realloc(void *mem, Uint bytes);\r
+EXPORT void *sbrk(int increment);\r
+LOCAL void *extendHeap(int bytes);\r
+LOCAL uint brk(int delta);\r
+\r
+//Code\r
+\r
+/**\r
+ \fn EXPORT void *malloc(size_t bytes)\r
+ \brief Allocates memory from the heap space\r
+ \param bytes Integer - Size of buffer to return\r
+ \return Pointer to buffer\r
+*/\r
+EXPORT void *malloc(size_t bytes)\r
+{\r
+ Uint bestSize;\r
+ Uint closestMatch = 0;\r
+ Uint bestMatchAddr = 0;\r
+ heap_head *curBlock;\r
+ \r
+ // Initialise Heap\r
+ if(_heap_start == NULL)\r
+ {LOCAL void *sbrk(int delta);\r
+ _heap_start = sbrk(0);\r
+ _heap_end = _heap_start;\r
+ extendHeap(HEAP_INIT_SIZE);\r
+ }\r
+ \r
+ curBlock = _heap_start;\r
+ \r
+ bestSize = bytes + sizeof(heap_head) + sizeof(heap_foot) + BLOCK_SIZE - 1;\r
+ bestSize = (bestSize/BLOCK_SIZE)*BLOCK_SIZE; //Round up to block size\r
+ \r
+ while((Uint)curBlock < (Uint)_heap_end)\r
+ {\r
+ //SysDebug(" malloc: curBlock = 0x%x, curBlock->magic = 0x%x\n", curBlock, curBlock->magic);\r
+ if(curBlock->magic == MAGIC_FREE)\r
+ {\r
+ if(curBlock->size == bestSize)\r
+ break;\r
+ if(bestSize < curBlock->size && (curBlock->size < closestMatch || closestMatch == 0)) {\r
+ closestMatch = curBlock->size;\r
+ bestMatchAddr = (Uint)curBlock;\r
+ }\r
+ }\r
+ else if(curBlock->magic != MAGIC)\r
+ {\r
+ //Corrupt Heap\r
+ //SysDebug("malloc: Corrupt Heap\n");\r
+ return NULL;\r
+ }\r
+ curBlock = (heap_head*)((Uint)curBlock + curBlock->size);\r
+ }\r
+ \r
+ if((Uint)curBlock < (Uint)_heap_start) {\r
+ //SysDebug("malloc: Heap underrun for some reason\n");\r
+ return NULL;\r
+ }\r
+ \r
+ //Found a perfect match\r
+ if((Uint)curBlock < (Uint)_heap_end) {\r
+ curBlock->magic = MAGIC;\r
+ return (void*)((Uint)curBlock + sizeof(heap_head));\r
+ }\r
+ \r
+ //Out of Heap Space\r
+ if(!closestMatch) {\r
+ curBlock = extendHeap(bestSize); //Allocate more\r
+ if(curBlock == NULL) {\r
+ //SysDebug("malloc: Out of Heap Space\n");\r
+ return NULL;\r
+ }\r
+ curBlock->magic = MAGIC;\r
+ return (void*)((Uint)curBlock + sizeof(heap_head));\r
+ }\r
+ \r
+ //Split Block?\r
+ if(closestMatch - bestSize > BLOCK_SIZE) {\r
+ heap_foot *foot;\r
+ curBlock = (heap_head*)bestMatchAddr;\r
+ curBlock->magic = MAGIC;\r
+ curBlock->size = bestSize;\r
+ foot = (heap_foot*)(bestMatchAddr + bestSize - sizeof(heap_foot));\r
+ foot->header = curBlock;\r
+ foot->magic = MAGIC;\r
+\r
+ curBlock = (heap_head*)(bestMatchAddr + bestSize);\r
+ curBlock->magic = MAGIC_FREE;\r
+ curBlock->size = closestMatch - bestSize;\r
+ \r
+ foot = (heap_foot*)(bestMatchAddr + closestMatch - sizeof(heap_foot));\r
+ foot->header = curBlock;\r
+ \r
+ ((heap_head*)bestMatchAddr)->magic = MAGIC; //mark as used\r
+ return (void*)(bestMatchAddr + sizeof(heap_head));\r
+ }\r
+ \r
+ //Don't Split the block\r
+ ((heap_head*)bestMatchAddr)->magic = MAGIC;\r
+ return (void*)(bestMatchAddr+sizeof(heap_head));\r
+}\r
+\r
+/**\r
+ \fn EXPORT void free(void *mem)\r
+ \brief Free previously allocated memory\r
+ \param mem Pointer - Memory to free\r
+*/\r
+EXPORT void free(void *mem)\r
+{\r
+ heap_head *head = mem;\r
+ \r
+ if(head->magic != MAGIC) //Valid Heap Address\r
+ return;\r
+ \r
+ head->magic = MAGIC_FREE;\r
+ \r
+ //Unify Right\r
+ if((Uint)head + head->size < (Uint)_heap_end)\r
+ {\r
+ heap_head *nextHead = (heap_head*)((Uint)head + head->size);\r
+ if(nextHead->magic == MAGIC_FREE) { //Is the next block free\r
+ head->size += nextHead->size; //Amalgamate\r
+ nextHead->magic = 0; //For Security\r
+ }\r
+ }\r
+ //Unify Left\r
+ if((Uint)head - sizeof(heap_foot) > (Uint)_heap_start)\r
+ {\r
+ heap_head *prevHead;\r
+ heap_foot *prevFoot = (heap_foot *)((Uint)head - sizeof(heap_foot));\r
+ if(prevFoot->magic == MAGIC) {\r
+ prevHead = prevFoot->header;\r
+ if(prevHead->magic == MAGIC_FREE) {\r
+ prevHead->size += head->size; //Amalgamate\r
+ head->magic = 0; //For Security\r
+ }\r
+ }\r
+ }\r
+}\r
+\r
+/**\r
+ \fn EXPORT void *realloc(void *oldPos, size_t bytes)\r
+ \brief Reallocate a block of memory\r
+ \param bytes Integer - Size of new buffer\r
+ \param oldPos Pointer - Old Buffer\r
+ \return Pointer to new buffer\r
+*/\r
+EXPORT void *realloc(void *oldPos, size_t bytes)\r
+{\r
+ void *ret;\r
+ heap_head *head;\r
+ \r
+ if(oldPos == NULL) {\r
+ return malloc(bytes);\r
+ }\r
+ \r
+ //Check for free space after block\r
+ head = (heap_head*)((Uint)oldPos-sizeof(heap_head));\r
+ \r
+ //Hack to used free's amagamating algorithym and malloc's splitting\r
+ free(oldPos);\r
+ \r
+ //Allocate new memory\r
+ ret = malloc(bytes);\r
+ if(ret == NULL)\r
+ return NULL;\r
+ \r
+ //Copy Old Data\r
+ if((Uint)ret != (Uint)oldPos) {\r
+ memcpy(ret, oldPos, head->size-sizeof(heap_head)-sizeof(heap_foot));\r
+ }\r
+ \r
+ //Return\r
+ return ret;\r
+}\r
+\r
+/**\r
+ \fn LOCAL void *extendHeap(int bytes)\r
+ \brief Create a new block at the end of the heap area\r
+ \param bytes Integer - Size reqired\r
+ \return Pointer to last free block\r
+ */\r
+\r
+LOCAL void *extendHeap(int bytes)\r
+{\r
+ heap_head *head = _heap_end;\r
+ heap_foot *foot;\r
+ \r
+ //Expand Memory Space (Use foot as a temp pointer)\r
+ foot = sbrk(bytes);\r
+ if(foot == (void*)-1)\r
+ return NULL;\r
+ \r
+ \r
+ //Create New Block\r
+ // Header\r
+ head->magic = MAGIC_FREE; //Unallocated\r
+ head->size = bytes;\r
+ // Footer\r
+ foot = _heap_end + bytes - sizeof(heap_foot);\r
+ foot->header = head;\r
+ foot->magic = MAGIC;\r
+ \r
+ //Combine with previous block if nessasary\r
+ if(_heap_end != _heap_start && ((heap_foot*)((Uint)_heap_end-sizeof(heap_foot)))->magic == MAGIC) {\r
+ heap_head *tmpHead = ((heap_foot*)((Uint)_heap_end-sizeof(heap_foot)))->header;\r
+ if(tmpHead->magic == MAGIC_FREE) {\r
+ tmpHead->size += bytes;\r
+ foot->header = tmpHead;\r
+ head = tmpHead;\r
+ }\r
+ }\r
+ \r
+ _heap_end = (void*) ((Uint)foot+sizeof(heap_foot));\r
+ return head;\r
+}\r
+\r
+/**\r
+ \fn EXPORT void *sbrk(int increment)\r
+ \brief Increases the program's memory space\r
+ \param count Integer - Size of heap increase\r
+ \return Pointer to start of new region\r
+*/\r
+EXPORT void *sbrk(int increment)\r
+{\r
+ size_t newEnd;\r
+ static size_t oldEnd = 0;\r
+ static size_t curEnd = 0;\r
+\r
+ //SysDebug("sbrk: (increment=%i)\n", increment);\r
+\r
+ if (oldEnd == 0) curEnd = oldEnd = brk(0);\r
+\r
+ //SysDebug(" sbrk: oldEnd = 0x%x\n", oldEnd);\r
+ if (increment == 0) return (void *) curEnd;\r
+\r
+ newEnd = curEnd + increment;\r
+\r
+ if (brk(newEnd) == curEnd) return (void *) -1;\r
+ oldEnd = curEnd;\r
+ curEnd = newEnd;\r
+ //SysDebug(" sbrk: newEnd = 0x%x\n", newEnd);\r
+\r
+ return (void *) oldEnd;\r
+}\r
+\r
+/**\r
+ * \fn EXPORT int IsHeap(void *ptr)\r
+ */\r
+EXPORT int IsHeap(void *ptr)\r
+{\r
+ #if 0\r
+ heap_head *head;\r
+ heap_foot *foot;\r
+ #endif\r
+ if( (Uint)ptr < (Uint)_heap_start ) return 0;\r
+ if( (Uint)ptr > (Uint)_heap_end ) return 0;\r
+ \r
+ #if 0\r
+ head = (void*)((Uint)ptr - 4);\r
+ if( head->magic != MAGIC ) return 0;\r
+ foot = (void*)( (Uint)ptr + head->size - sizeof(heap_foot) );\r
+ if( foot->magic != MAGIC ) return 0;\r
+ #endif\r
+ return 1;\r
+}\r
+\r
+// === STATIC FUNCTIONS ===\r
+/**\r
+ * Does the job of brk(0)\r
+ */\r
+static void *FindHeapBase()\r
+{\r
+ #define MAX 0xC0000000 // Address\r
+ #define THRESHOLD 512 // Pages\r
+ uint addr;\r
+ uint stretch = 0;\r
+ \r
+ // Scan address space\r
+ for(addr = 0;\r
+ addr < MAX;\r
+ addr += 0x1000\r
+ )\r
+ {\r
+ if( _SysGetPhys(addr) == 0 ) {\r
+ stretch = 0;\r
+ } else {\r
+ stretch ++;\r
+ if(stretch > THRESHOLD)\r
+ {\r
+ return (void*)( addr + stretch*0x1000 );\r
+ }\r
+ }\r
+ }\r
+ return NULL;\r
+}\r
+\r
+LOCAL uint brk(int delta)\r
+{\r
+ static uint curpos;\r
+ uint pages;\r
+ uint ret = curpos;\r
+ \r
+ // Find initial position\r
+ if(curpos == 0) curpos = (uint)FindHeapBase();\r
+ \r
+ // Get Current Position\r
+ if(delta == 0)\r
+ {\r
+ return curpos;\r
+ }\r
+ \r
+ // Do we need to add pages\r
+ if(curpos & 0xFFF && (curpos & 0xFFF) + delta < 0x1000)\r
+ return curpos += delta;\r
+ \r
+ // Page align current position\r
+ if(curpos & 0xFFF) delta -= 0x1000 - (curpos & 0xFFF);\r
+ curpos = (curpos + 0xFFF) & ~0xFFF;\r
+ \r
+ // Allocate Pages\r
+ pages = (delta + 0xFFF) >> 12;\r
+ while(pages--)\r
+ {\r
+ _SysAllocate(curpos);\r
+ curpos += 0x1000;\r
+ delta -= 0x1000;\r
+ }\r
+ \r
+ // Bring the current position to exactly what we want\r
+ curpos -= ((delta + 0xFFF) & ~0xFFF) - delta;\r
+ \r
+ return ret; // Return old curpos\r
+}\r
git.ucc.asn.au / tpg / acess2.git / blobdiff
UCC git Repository :: git.ucc.asn.au