+++ /dev/null
-/*\r
-AcessOS Basic LibC\r
-Malloc.c - Heap Manager\r
-*/\r
-\r
-#include "header.h"\r
-\r
-#define MAGIC 0xACE2ACED //AcessOS1\r
-#define MAGIC_FREE (~MAGIC) //AcessOS1\r
-#define BLOCK_SIZE 16 //Minimum\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;\r
-Uint endHeap;\r
-\r
-//Prototypes\r
-void *malloc(Uint bytes);\r
-void free(void *mem);\r
-void *realloc(Uint bytes, void *mem);\r
-void *extendHeap(int bytes);\r
-\r
-//Code\r
-/* Initialise Heap\r
- */\r
-void heap_init()\r
-{\r
- heap_start = (void*)( (gAxeHdr.loadto + gAxeHdr.length + 0xFFF) & 0xFFFFF000) ;\r
- heap_end = heap_start;\r
- extendHeap( gAxeHdr.maxmem );\r
- endHeap = (Uint)heap_start + gAxeHdr.maxmem;\r
-}\r
-\r
-void *malloc(Uint bytes)\r
-{\r
- Uint bestSize;\r
- Uint closestMatch = 0;\r
- Uint bestMatchAddr = 0;\r
- heap_head *curBlock = heap_start;\r
- \r
- if(heap_start == NULL) {\r
- heap_init();\r
- curBlock = heap_start;\r
- }\r
- \r
- bestSize = ((bytes+sizeof(heap_head)+sizeof(heap_foot))/BLOCK_SIZE+1)*BLOCK_SIZE; //Round up to block size\r
- \r
- while((Uint)curBlock < (Uint)heap_end)\r
- {\r
- if(curBlock->magic == MAGIC_FREE)\r
- {\r
- //foundFree = 1;\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
- } else if(curBlock->magic != MAGIC) {\r
- //Corrupt Heap\r
- return NULL;\r
- }\r
- curBlock = (heap_head*)((Uint)curBlock + curBlock->size);\r
- }\r
- \r
- if((Uint)curBlock < (Uint)heap_start) {\r
- //panic("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
- {\r
- #if 0\r
- curBlock = extendHeap(bestSize); //Allocate more\r
- if(curBlock == NULL) {\r
- //panic("malloc: Out of kernel heap memory\n");\r
- return NULL;\r
- }\r
- curBlock->magic = MAGIC;\r
- return (void*)((Uint)curBlock + sizeof(heap_head));\r
- #else\r
- return NULL;\r
- #endif\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
-/* Free previously allocated memory\r
- */\r
-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
-/* Create a new block at the end of the heap area\r
- */\r
-void *extendHeap(int bytes)\r
-{\r
- heap_head *head = heap_end;\r
- heap_foot *foot = (heap_foot*)(((Uint)heap_end) + bytes-sizeof(heap_foot));\r
- \r
- //Create New Block\r
- head->magic = MAGIC_FREE; //Unallocated\r
- head->size = bytes;\r
- \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
-/* Reallocate a block of memory\r
- */\r
-void *realloc(Uint bytes, void *oldPos)\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
- {\r
- Uint *in, *out;\r
- Uint count;\r
- count = head->size - sizeof(heap_head) - sizeof(heap_foot);\r
- if((Uint)ret < (Uint)out)\r
- {\r
- out = ret; in = oldPos;\r
- while(count--) *out++ = *in++;\r
- }\r
- else\r
- {\r
- out = ret; in = oldPos;\r
- out += count; in += count;\r
- while(count--) *--out = *--in;\r
- }\r
- }\r
- \r
- //Return\r
- return ret;\r
-}\r