X-Git-Url: https://git.ucc.asn.au/?a=blobdiff_plain;f=Usermode%2FLibraries%2Flibc.so_src%2Fheap.c;h=779b0048d44938a80dbae3c058e93db9e85ac064;hb=8dcc3e209d0d728565a18c8dca2b0ba220b74a6f;hp=6832738cce1b83ab740991d62cefe18d574bcd4c;hpb=149b37ab41da1105db27303b38c43eb237b779da;p=tpg%2Facess2.git diff --git a/Usermode/Libraries/libc.so_src/heap.c b/Usermode/Libraries/libc.so_src/heap.c index 6832738c..779b0048 100644 --- a/Usermode/Libraries/libc.so_src/heap.c +++ b/Usermode/Libraries/libc.so_src/heap.c @@ -4,8 +4,15 @@ heap.c - Heap Manager */ #include #include +#include #include "lib.h" +#if 0 +# define DEBUGS(s...) _SysDebug(s) +#else +# define DEBUGS(s...) do{}while(0) +#endif + // === Constants === #define MAGIC 0xACE55051 //AcessOS1 #define MAGIC_FREE (~MAGIC) @@ -14,27 +21,31 @@ heap.c - Heap Manager typedef unsigned int Uint; -//Typedefs +// === TYPES === typedef struct { - Uint magic; - Uint size; + uint32_t magic; + size_t size; + char data[]; } 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(Uint newpos); +static void *FindHeapBase(); +LOCAL uint brk(uintptr_t newpos); +LOCAL void Heap_Dump(void); //Code @@ -46,67 +57,73 @@ LOCAL uint brk(Uint newpos); */ 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"); + Heap_Dump(); + _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)); + DEBUGS("malloc(0x%x) = %p (extend) 0x%x", bytes, curBlock->data, bestSize); + return curBlock->data; } + heap_head *besthead = (void*)bestMatchAddr; + //Split Block? if(closestMatch - bestSize > BLOCK_SIZE) { heap_foot *foot; @@ -124,13 +141,29 @@ EXPORT void *malloc(size_t bytes) foot = (heap_foot*)(bestMatchAddr + closestMatch - sizeof(heap_foot)); foot->header = curBlock; - ((heap_head*)bestMatchAddr)->magic = MAGIC; //mark as used - return (void*)(bestMatchAddr + sizeof(heap_head)); + besthead->magic = MAGIC; //mark as used + DEBUGS("malloc(0x%x) = %p (split) 0x%x", bytes, besthead->data, bestSize); + return besthead->data; } //Don't Split the block - ((heap_head*)bestMatchAddr)->magic = MAGIC; - return (void*)(bestMatchAddr+sizeof(heap_head)); + besthead->magic = MAGIC; + DEBUGS("malloc(0x%x) = %p (reuse) 0x%x", bytes, besthead->data, besthead->size); + return besthead->data; +} + +/** + * \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; } /** @@ -140,27 +173,31 @@ 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; head->magic = MAGIC_FREE; + DEBUGS("free(%p) : 0x%x bytes", mem, head->size); //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 +225,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 +236,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 +245,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 +261,6 @@ LOCAL void *extendHeap(int bytes) if(foot == (void*)-1) return NULL; - //Create New Block // Header head->magic = MAGIC_FREE; //Unallocated @@ -235,8 +271,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 +280,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 +292,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 +350,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 +368,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,30 +381,38 @@ 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(Uint newpos) +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); + _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(newpos == 0) return curpos; @@ -346,7 +420,7 @@ LOCAL uint brk(Uint newpos) if(newpos < curpos) return newpos; delta = newpos - curpos; - //_SysDebug(" brk: delta = 0x%x", delta); + _SysDebug(" brk: delta = 0x%x", delta); // Do we need to add pages if(curpos & 0xFFF && (curpos & 0xFFF) + delta < 0x1000) @@ -370,3 +444,25 @@ LOCAL uint brk(Uint newpos) return ret; // Return old curpos } + +void Heap_Dump(void) +{ + heap_head *cur = _heap_start; + while( cur < _heap_end ) + { + switch( cur->magic ) + { + case MAGIC: + _SysDebug("Used block %p[0x%x] - ptr=%p", cur, cur->size, cur->data); + break; + case MAGIC_FREE: + _SysDebug("Free block %p[0x%x] - ptr=%p", cur, cur->size, cur->data); + break; + default: + _SysDebug("Block %p bad magic (0x%x)", cur, cur->magic); + return ; + } + cur = (void*)( (char*)cur + cur->size ); + } +} +