X-Git-Url: https://git.ucc.asn.au/?a=blobdiff_plain;f=Usermode%2FLibraries%2Flibc.so_src%2Fheap.c;h=4fcc8bed3a5b446d3a2bda1e6b8a10af1ac8ebef;hb=05abefc2a27a08f381bca41524a5d299c4839ff2;hp=23df92a73f83e5f468c31e5f3b653ecf8cf31c15;hpb=17e16b3110b4c5124b0707435e0427993d696545;p=tpg%2Facess2.git diff --git a/Usermode/Libraries/libc.so_src/heap.c b/Usermode/Libraries/libc.so_src/heap.c index 23df92a7..4fcc8bed 100644 --- a/Usermode/Libraries/libc.so_src/heap.c +++ b/Usermode/Libraries/libc.so_src/heap.c @@ -4,6 +4,7 @@ heap.c - Heap Manager */ #include #include +#include #include "lib.h" // === Constants === @@ -14,27 +15,29 @@ heap.c - Heap Manager typedef unsigned int Uint; -//Typedefs +// === TYPES === typedef struct { - Uint magic; - Uint size; + uint32_t magic; + size_t size; } heap_head; typedef struct { heap_head *header; - Uint magic; + uint32_t magic; } heap_foot; -//Globals -void *_heap_start = NULL; -void *_heap_end = NULL; +// === LOCAL VARIABLES === +static void *_heap_start = NULL; +static void *_heap_end = NULL; -//Prototypes -EXPORT void *malloc(Uint bytes); +// === PROTOTYPES === +EXPORT void *malloc(size_t bytes); +EXPORT void *calloc(size_t bytes, size_t count); EXPORT void free(void *mem); -EXPORT void *realloc(void *mem, Uint bytes); +EXPORT void *realloc(void *mem, size_t bytes); EXPORT void *sbrk(int increment); LOCAL void *extendHeap(int bytes); -LOCAL uint brk(int delta); +static void *FindHeapBase(); +LOCAL uint brk(uintptr_t newpos); //Code @@ -46,65 +49,67 @@ LOCAL uint brk(int delta); */ EXPORT void *malloc(size_t bytes) { - Uint bestSize; - Uint closestMatch = 0; - Uint bestMatchAddr = 0; + size_t bestSize; + size_t closestMatch = 0; + void *bestMatchAddr = 0; heap_head *curBlock; +// _SysDebug("&_heap_start = %p, _heap_start = %p", &_heap_start, _heap_start); // Initialise Heap if(_heap_start == NULL) - {LOCAL void *sbrk(int delta); + { _heap_start = sbrk(0); _heap_end = _heap_start; extendHeap(HEAP_INIT_SIZE); } curBlock = _heap_start; +// _SysDebug("_heap_start = %p", _heap_start); bestSize = bytes + sizeof(heap_head) + sizeof(heap_foot) + BLOCK_SIZE - 1; bestSize = (bestSize/BLOCK_SIZE)*BLOCK_SIZE; //Round up to block size - while((Uint)curBlock < (Uint)_heap_end) + while( (uintptr_t)curBlock < (uintptr_t)_heap_end) { - //SysDebug(" malloc: curBlock = 0x%x, curBlock->magic = 0x%x\n", curBlock, curBlock->magic); + //_SysDebug(" malloc: curBlock = 0x%x, curBlock->magic = 0x%x\n", curBlock, curBlock->magic); if(curBlock->magic == MAGIC_FREE) { if(curBlock->size == bestSize) break; if(bestSize < curBlock->size && (curBlock->size < closestMatch || closestMatch == 0)) { closestMatch = curBlock->size; - bestMatchAddr = (Uint)curBlock; + bestMatchAddr = curBlock; } } else if(curBlock->magic != MAGIC) { //Corrupt Heap - //SysDebug("malloc: Corrupt Heap\n"); + _SysDebug("malloc: Corrupt Heap\n"); return NULL; } - curBlock = (heap_head*)((Uint)curBlock + curBlock->size); + curBlock = (heap_head*)((uintptr_t)curBlock + curBlock->size); } - if((Uint)curBlock < (Uint)_heap_start) { - //SysDebug("malloc: Heap underrun for some reason\n"); + if((uintptr_t)curBlock < (uintptr_t)_heap_start) { + _SysDebug("malloc: Heap underrun for some reason\n"); return NULL; } //Found a perfect match - if((Uint)curBlock < (Uint)_heap_end) { + if((uintptr_t)curBlock < (uintptr_t)_heap_end) { curBlock->magic = MAGIC; - return (void*)((Uint)curBlock + sizeof(heap_head)); + return (void*)((uintptr_t)curBlock + sizeof(heap_head)); } //Out of Heap Space if(!closestMatch) { curBlock = extendHeap(bestSize); //Allocate more if(curBlock == NULL) { - //SysDebug("malloc: Out of Heap Space\n"); + _SysDebug("malloc: Out of Heap Space\n"); return NULL; } curBlock->magic = MAGIC; - return (void*)((Uint)curBlock + sizeof(heap_head)); + return (void*)((uintptr_t)curBlock + sizeof(heap_head)); } //Split Block? @@ -133,6 +138,20 @@ EXPORT void *malloc(size_t bytes) return (void*)(bestMatchAddr+sizeof(heap_head)); } +/** + * \fn EXPORT void *calloc(size_t bytes, size_t count) + * \brief Allocate and zero a block of memory + * \param __nmemb Number of memeber elements + * \param __size Size of one element + */ +EXPORT void *calloc(size_t __nmemb, size_t __size) +{ + void *ret = malloc(__size*__nmemb); + if(!ret) return NULL; + memset(ret, 0, __size*__nmemb); + return ret; +} + /** \fn EXPORT void free(void *mem) \brief Free previously allocated memory @@ -140,7 +159,10 @@ EXPORT void *malloc(size_t bytes) */ EXPORT void free(void *mem) { - heap_head *head = mem; + heap_head *head = (void*)((intptr_t)mem-sizeof(heap_head)); + + // Sanity please! + if(!mem) return; if(head->magic != MAGIC) //Valid Heap Address return; @@ -148,19 +170,19 @@ EXPORT void free(void *mem) head->magic = MAGIC_FREE; //Unify Right - if((Uint)head + head->size < (Uint)_heap_end) + if((intptr_t)head + head->size < (intptr_t)_heap_end) { - heap_head *nextHead = (heap_head*)((Uint)head + head->size); + heap_head *nextHead = (heap_head*)((intptr_t)head + head->size); if(nextHead->magic == MAGIC_FREE) { //Is the next block free head->size += nextHead->size; //Amalgamate nextHead->magic = 0; //For Security } } //Unify Left - if((Uint)head - sizeof(heap_foot) > (Uint)_heap_start) + if((intptr_t)head - sizeof(heap_foot) > (intptr_t)_heap_start) { heap_head *prevHead; - heap_foot *prevFoot = (heap_foot *)((Uint)head - sizeof(heap_foot)); + heap_foot *prevFoot = (heap_foot *)((intptr_t)head - sizeof(heap_foot)); if(prevFoot->magic == MAGIC) { prevHead = prevFoot->header; if(prevHead->magic == MAGIC_FREE) { @@ -188,7 +210,7 @@ EXPORT void *realloc(void *oldPos, size_t bytes) } //Check for free space after block - head = (heap_head*)((Uint)oldPos-sizeof(heap_head)); + head = (heap_head*)((uintptr_t)oldPos-sizeof(heap_head)); //Hack to used free's amagamating algorithym and malloc's splitting free(oldPos); @@ -199,7 +221,7 @@ EXPORT void *realloc(void *oldPos, size_t bytes) return NULL; //Copy Old Data - if((Uint)ret != (Uint)oldPos) { + if(ret != oldPos) { memcpy(ret, oldPos, head->size-sizeof(heap_head)-sizeof(heap_foot)); } @@ -208,10 +230,10 @@ EXPORT void *realloc(void *oldPos, size_t bytes) } /** - \fn LOCAL void *extendHeap(int bytes) - \brief Create a new block at the end of the heap area - \param bytes Integer - Size reqired - \return Pointer to last free block + * \fn LOCAL void *extendHeap(int bytes) + * \brief Create a new block at the end of the heap area + * \param bytes Integer - Size reqired + * \return Pointer to last free block */ LOCAL void *extendHeap(int bytes) @@ -224,7 +246,6 @@ LOCAL void *extendHeap(int bytes) if(foot == (void*)-1) return NULL; - //Create New Block // Header head->magic = MAGIC_FREE; //Unallocated @@ -235,8 +256,8 @@ LOCAL void *extendHeap(int bytes) foot->magic = MAGIC; //Combine with previous block if nessasary - if(_heap_end != _heap_start && ((heap_foot*)((Uint)_heap_end-sizeof(heap_foot)))->magic == MAGIC) { - heap_head *tmpHead = ((heap_foot*)((Uint)_heap_end-sizeof(heap_foot)))->header; + if(_heap_end != _heap_start && ((heap_foot*)((uintptr_t)_heap_end-sizeof(heap_foot)))->magic == MAGIC) { + heap_head *tmpHead = ((heap_foot*)((uintptr_t)_heap_end-sizeof(heap_foot)))->header; if(tmpHead->magic == MAGIC_FREE) { tmpHead->size += bytes; foot->header = tmpHead; @@ -244,7 +265,7 @@ LOCAL void *extendHeap(int bytes) } } - _heap_end = (void*) ((Uint)foot+sizeof(heap_foot)); + _heap_end = (void*) ((uintptr_t)foot+sizeof(heap_foot)); return head; } @@ -256,24 +277,52 @@ LOCAL void *extendHeap(int bytes) */ EXPORT void *sbrk(int increment) { - size_t newEnd; - static size_t oldEnd = 0; - static size_t curEnd = 0; + static uintptr_t oldEnd = 0; + static uintptr_t curEnd = 0; - //SysDebug("sbrk: (increment=%i)\n", increment); + //_SysDebug("sbrk: (increment=%i)", increment); - if (oldEnd == 0) curEnd = oldEnd = brk(0); + if (curEnd == 0) { + oldEnd = curEnd = (uintptr_t)FindHeapBase(); + //_SysAllocate(curEnd); // Allocate the first page + } - //SysDebug(" sbrk: oldEnd = 0x%x\n", oldEnd); + //_SysDebug(" sbrk: oldEnd = 0x%x", oldEnd); if (increment == 0) return (void *) curEnd; - newEnd = curEnd + increment; - - if (brk(newEnd) == curEnd) return (void *) -1; oldEnd = curEnd; - curEnd = newEnd; - //SysDebug(" sbrk: newEnd = 0x%x\n", newEnd); + // Single Page + if( (curEnd & 0xFFF) && (curEnd & 0xFFF) + increment < 0x1000 ) + { + //if( curEnd & 0xFFF == 0 ) + //{ + // if( !_SysAllocate(curEnd) ) + // { + // _SysDebug("sbrk - Error allocating memory"); + // return (void*)-1; + // } + //} + curEnd += increment; + //_SysDebug("sbrk: RETURN %p (single page, no alloc)", (void *) oldEnd); + return (void *)oldEnd; + } + + increment -= curEnd & 0xFFF; + curEnd += 0xFFF; curEnd &= ~0xFFF; + while( increment > 0 ) + { + if( !_SysAllocate(curEnd) ) + { + // Error? + _SysDebug("sbrk - Error allocating memory"); + return (void*)-1; + } + increment -= 0x1000; + curEnd += 0x1000; + } + + //_SysDebug("sbrk: RETURN %p", (void *) oldEnd); return (void *) oldEnd; } @@ -286,8 +335,8 @@ EXPORT int IsHeap(void *ptr) heap_head *head; heap_foot *foot; #endif - if( (Uint)ptr < (Uint)_heap_start ) return 0; - if( (Uint)ptr > (Uint)_heap_end ) return 0; + if( (uintptr_t)ptr < (uintptr_t)_heap_start ) return 0; + if( (uintptr_t)ptr > (uintptr_t)_heap_end ) return 0; #if 0 head = (void*)((Uint)ptr - 4); @@ -304,10 +353,12 @@ EXPORT int IsHeap(void *ptr) */ static void *FindHeapBase() { + #if 0 #define MAX 0xC0000000 // Address #define THRESHOLD 512 // Pages uint addr; uint stretch = 0; + uint64_t tmp; // Scan address space for(addr = 0; @@ -315,33 +366,46 @@ static void *FindHeapBase() addr += 0x1000 ) { - if( _SysGetPhys(addr) == 0 ) { + tmp = _SysGetPhys(addr); + if( tmp != 0 ) { stretch = 0; } else { stretch ++; if(stretch > THRESHOLD) { - return (void*)( addr + stretch*0x1000 ); + return (void*)( addr - stretch*0x1000 ); } } + //__asm__ __volatile__ ( + // "push %%ebx;mov %%edx,%%ebx;int $0xAC;pop %%ebx" + // ::"a"(256),"d"("%x"),"c"(addr)); } + return NULL; + #else + return (void*)0x00900000; + #endif } -LOCAL uint brk(int delta) +LOCAL uint brk(uintptr_t newpos) { - static uint curpos; + static uintptr_t curpos; uint pages; uint ret = curpos; + int delta; + + _SysDebug("brk: (newpos=0x%x)", newpos); // Find initial position - if(curpos == 0) curpos = (uint)FindHeapBase(); + if(curpos == 0) curpos = (uintptr_t)FindHeapBase(); // Get Current Position - if(delta == 0) - { - return curpos; - } + if(newpos == 0) return curpos; + + if(newpos < curpos) return newpos; + + delta = newpos - curpos; + _SysDebug(" brk: delta = 0x%x", delta); // Do we need to add pages if(curpos & 0xFFF && (curpos & 0xFFF) + delta < 0x1000)