3 heap.c - Heap Manager
\r
5 #include <acess/sys.h>
\r
11 # define DEBUGS(s...) _SysDebug(s)
\r
13 # define DEBUGS(s...) do{}while(0)
\r
16 // === Constants ===
\r
17 #define MAGIC 0xACE55051 //AcessOS1
\r
18 #define MAGIC_FREE (~MAGIC)
\r
19 #define BLOCK_SIZE 16 //Minimum
\r
20 #define HEAP_INIT_SIZE 0x10000
\r
22 typedef unsigned int Uint;
\r
35 // === LOCAL VARIABLES ===
\r
36 static void *_heap_start = NULL;
\r
37 static void *_heap_end = NULL;
\r
39 // === PROTOTYPES ===
\r
40 EXPORT void *malloc(size_t bytes);
\r
41 EXPORT void *calloc(size_t bytes, size_t count);
\r
42 EXPORT void free(void *mem);
\r
43 EXPORT void *realloc(void *mem, size_t bytes);
\r
44 EXPORT void *sbrk(int increment);
\r
45 LOCAL void *extendHeap(int bytes);
\r
46 static void *FindHeapBase();
\r
47 LOCAL uint brk(uintptr_t newpos);
\r
48 LOCAL void Heap_Dump(void);
\r
53 \fn EXPORT void *malloc(size_t bytes)
\r
54 \brief Allocates memory from the heap space
\r
55 \param bytes Integer - Size of buffer to return
\r
56 \return Pointer to buffer
\r
58 EXPORT void *malloc(size_t bytes)
\r
61 size_t closestMatch = 0;
\r
62 void *bestMatchAddr = 0;
\r
63 heap_head *curBlock;
\r
65 // _SysDebug("&_heap_start = %p, _heap_start = %p", &_heap_start, _heap_start);
\r
67 if(_heap_start == NULL)
\r
69 _heap_start = sbrk(0);
\r
70 _heap_end = _heap_start;
\r
71 extendHeap(HEAP_INIT_SIZE);
\r
74 curBlock = _heap_start;
\r
75 // _SysDebug("_heap_start = %p", _heap_start);
\r
77 bestSize = bytes + sizeof(heap_head) + sizeof(heap_foot) + BLOCK_SIZE - 1;
\r
78 bestSize = (bestSize/BLOCK_SIZE)*BLOCK_SIZE; //Round up to block size
\r
80 while( (uintptr_t)curBlock < (uintptr_t)_heap_end)
\r
82 //_SysDebug(" malloc: curBlock = 0x%x, curBlock->magic = 0x%x\n", curBlock, curBlock->magic);
\r
83 if(curBlock->magic == MAGIC_FREE)
\r
85 if(curBlock->size == bestSize)
\r
87 if(bestSize < curBlock->size && (curBlock->size < closestMatch || closestMatch == 0)) {
\r
88 closestMatch = curBlock->size;
\r
89 bestMatchAddr = curBlock;
\r
92 else if(curBlock->magic != MAGIC)
\r
96 _SysDebug("malloc: Corrupt Heap\n");
\r
100 curBlock = (heap_head*)((uintptr_t)curBlock + curBlock->size);
\r
103 if((uintptr_t)curBlock < (uintptr_t)_heap_start) {
\r
105 _SysDebug("malloc: Heap underrun for some reason\n");
\r
110 //Found a perfect match
\r
111 if((uintptr_t)curBlock < (uintptr_t)_heap_end) {
\r
112 curBlock->magic = MAGIC;
\r
113 return (void*)((uintptr_t)curBlock + sizeof(heap_head));
\r
116 //Out of Heap Space
\r
117 if(!closestMatch) {
\r
118 curBlock = extendHeap(bestSize); //Allocate more
\r
119 if(curBlock == NULL) {
\r
120 _SysDebug("malloc: Out of Heap Space\n");
\r
123 curBlock->magic = MAGIC;
\r
124 DEBUGS("malloc(0x%x) = %p (extend) 0x%x", bytes, curBlock->data, bestSize);
\r
125 return curBlock->data;
\r
128 heap_head *besthead = (void*)bestMatchAddr;
\r
131 if(closestMatch - bestSize > BLOCK_SIZE) {
\r
133 curBlock = (heap_head*)bestMatchAddr;
\r
134 curBlock->magic = MAGIC;
\r
135 curBlock->size = bestSize;
\r
136 foot = (heap_foot*)(bestMatchAddr + bestSize - sizeof(heap_foot));
\r
137 foot->header = curBlock;
\r
138 foot->magic = MAGIC;
\r
140 curBlock = (heap_head*)(bestMatchAddr + bestSize);
\r
141 curBlock->magic = MAGIC_FREE;
\r
142 curBlock->size = closestMatch - bestSize;
\r
144 foot = (heap_foot*)(bestMatchAddr + closestMatch - sizeof(heap_foot));
\r
145 foot->header = curBlock;
\r
147 besthead->magic = MAGIC; //mark as used
\r
148 DEBUGS("malloc(0x%x) = %p (split) 0x%x", bytes, besthead->data, bestSize);
\r
149 return besthead->data;
\r
152 //Don't Split the block
\r
153 besthead->magic = MAGIC;
\r
154 DEBUGS("malloc(0x%x) = %p (reuse) 0x%x", bytes, besthead->data, besthead->size);
\r
155 return besthead->data;
\r
159 * \fn EXPORT void *calloc(size_t bytes, size_t count)
\r
160 * \brief Allocate and zero a block of memory
\r
161 * \param __nmemb Number of memeber elements
\r
162 * \param __size Size of one element
\r
164 EXPORT void *calloc(size_t __nmemb, size_t __size)
\r
166 void *ret = malloc(__size*__nmemb);
\r
167 if(!ret) return NULL;
\r
168 memset(ret, 0, __size*__nmemb);
\r
173 \fn EXPORT void free(void *mem)
\r
174 \brief Free previously allocated memory
\r
175 \param mem Pointer - Memory to free
\r
177 EXPORT void free(void *mem)
\r
179 heap_head *head = (void*)((intptr_t)mem-sizeof(heap_head));
\r
184 if(head->magic != MAGIC) //Valid Heap Address
\r
187 head->magic = MAGIC_FREE;
\r
188 DEBUGS("free(%p) : 0x%x bytes", mem, head->size);
\r
191 if((uintptr_t)head + head->size < (uintptr_t)_heap_end)
\r
193 heap_head *nextHead = (heap_head*)((intptr_t)head + head->size);
\r
194 if(nextHead->magic == MAGIC_FREE) { //Is the next block free
\r
195 head->size += nextHead->size; //Amalgamate
\r
196 nextHead->magic = 0; //For Security
\r
200 if((uintptr_t)head - sizeof(heap_foot) > (uintptr_t)_heap_start)
\r
202 heap_head *prevHead;
\r
203 heap_foot *prevFoot = (heap_foot *)((intptr_t)head - sizeof(heap_foot));
\r
204 if(prevFoot->magic == MAGIC) {
\r
205 prevHead = prevFoot->header;
\r
206 if(prevHead->magic == MAGIC_FREE) {
\r
207 prevHead->size += head->size; //Amalgamate
\r
208 head->magic = 0; //For Security
\r
215 \fn EXPORT void *realloc(void *oldPos, size_t bytes)
\r
216 \brief Reallocate a block of memory
\r
217 \param bytes Integer - Size of new buffer
\r
218 \param oldPos Pointer - Old Buffer
\r
219 \return Pointer to new buffer
\r
221 EXPORT void *realloc(void *oldPos, size_t bytes)
\r
226 if(oldPos == NULL) {
\r
227 return malloc(bytes);
\r
230 //Check for free space after block
\r
231 head = (heap_head*)((uintptr_t)oldPos-sizeof(heap_head));
\r
233 //Hack to used free's amagamating algorithym and malloc's splitting
\r
236 //Allocate new memory
\r
237 ret = malloc(bytes);
\r
242 if(ret != oldPos) {
\r
243 memcpy(ret, oldPos, head->size-sizeof(heap_head)-sizeof(heap_foot));
\r
251 * \fn LOCAL void *extendHeap(int bytes)
\r
252 * \brief Create a new block at the end of the heap area
\r
253 * \param bytes Integer - Size reqired
\r
254 * \return Pointer to last free block
\r
257 LOCAL void *extendHeap(int bytes)
\r
259 heap_head *head = _heap_end;
\r
262 //Expand Memory Space (Use foot as a temp pointer)
\r
263 foot = sbrk(bytes);
\r
264 if(foot == (void*)-1)
\r
269 head->magic = MAGIC_FREE; //Unallocated
\r
270 head->size = bytes;
\r
272 foot = _heap_end + bytes - sizeof(heap_foot);
\r
273 foot->header = head;
\r
274 foot->magic = MAGIC;
\r
276 //Combine with previous block if nessasary
\r
277 if(_heap_end != _heap_start && ((heap_foot*)((uintptr_t)_heap_end-sizeof(heap_foot)))->magic == MAGIC) {
\r
278 heap_head *tmpHead = ((heap_foot*)((uintptr_t)_heap_end-sizeof(heap_foot)))->header;
\r
279 if(tmpHead->magic == MAGIC_FREE) {
\r
280 tmpHead->size += bytes;
\r
281 foot->header = tmpHead;
\r
286 _heap_end = (void*) ((uintptr_t)foot+sizeof(heap_foot));
\r
291 \fn EXPORT void *sbrk(int increment)
\r
292 \brief Increases the program's memory space
\r
293 \param count Integer - Size of heap increase
\r
294 \return Pointer to start of new region
\r
296 EXPORT void *sbrk(int increment)
\r
298 static uintptr_t oldEnd = 0;
\r
299 static uintptr_t curEnd = 0;
\r
301 //_SysDebug("sbrk: (increment=%i)", increment);
\r
304 oldEnd = curEnd = (uintptr_t)FindHeapBase();
\r
305 //_SysAllocate(curEnd); // Allocate the first page
\r
308 //_SysDebug(" sbrk: oldEnd = 0x%x", oldEnd);
\r
309 if (increment == 0) return (void *) curEnd;
\r
314 if( (curEnd & 0xFFF) && (curEnd & 0xFFF) + increment < 0x1000 )
\r
316 //if( curEnd & 0xFFF == 0 )
\r
318 // if( !_SysAllocate(curEnd) )
\r
320 // _SysDebug("sbrk - Error allocating memory");
\r
321 // return (void*)-1;
\r
324 curEnd += increment;
\r
325 //_SysDebug("sbrk: RETURN %p (single page, no alloc)", (void *) oldEnd);
\r
326 return (void *)oldEnd;
\r
329 increment -= curEnd & 0xFFF;
\r
330 curEnd += 0xFFF; curEnd &= ~0xFFF;
\r
331 while( increment > 0 )
\r
333 if( !_SysAllocate(curEnd) )
\r
336 _SysDebug("sbrk - Error allocating memory");
\r
339 increment -= 0x1000;
\r
343 //_SysDebug("sbrk: RETURN %p", (void *) oldEnd);
\r
344 return (void *) oldEnd;
\r
348 * \fn EXPORT int IsHeap(void *ptr)
\r
350 EXPORT int IsHeap(void *ptr)
\r
356 if( (uintptr_t)ptr < (uintptr_t)_heap_start ) return 0;
\r
357 if( (uintptr_t)ptr > (uintptr_t)_heap_end ) return 0;
\r
360 head = (void*)((Uint)ptr - 4);
\r
361 if( head->magic != MAGIC ) return 0;
\r
362 foot = (void*)( (Uint)ptr + head->size - sizeof(heap_foot) );
\r
363 if( foot->magic != MAGIC ) return 0;
\r
368 // === STATIC FUNCTIONS ===
\r
370 * Does the job of brk(0)
\r
372 static void *FindHeapBase()
\r
375 #define MAX 0xC0000000 // Address
\r
376 #define THRESHOLD 512 // Pages
\r
381 // Scan address space
\r
387 tmp = _SysGetPhys(addr);
\r
392 if(stretch > THRESHOLD)
\r
394 return (void*)( addr - stretch*0x1000 );
\r
397 //__asm__ __volatile__ (
\r
398 // "push %%ebx;mov %%edx,%%ebx;int $0xAC;pop %%ebx"
\r
399 // ::"a"(256),"d"("%x"),"c"(addr));
\r
404 return (void*)0x00900000;
\r
408 LOCAL uint brk(uintptr_t newpos)
\r
410 static uintptr_t curpos;
\r
415 _SysDebug("brk: (newpos=0x%x)", newpos);
\r
417 // Find initial position
\r
418 if(curpos == 0) curpos = (uintptr_t)FindHeapBase();
\r
420 // Get Current Position
\r
421 if(newpos == 0) return curpos;
\r
423 if(newpos < curpos) return newpos;
\r
425 delta = newpos - curpos;
\r
426 _SysDebug(" brk: delta = 0x%x", delta);
\r
428 // Do we need to add pages
\r
429 if(curpos & 0xFFF && (curpos & 0xFFF) + delta < 0x1000)
\r
430 return curpos += delta;
\r
432 // Page align current position
\r
433 if(curpos & 0xFFF) delta -= 0x1000 - (curpos & 0xFFF);
\r
434 curpos = (curpos + 0xFFF) & ~0xFFF;
\r
437 pages = (delta + 0xFFF) >> 12;
\r
440 _SysAllocate(curpos);
\r
445 // Bring the current position to exactly what we want
\r
446 curpos -= ((delta + 0xFFF) & ~0xFFF) - delta;
\r
448 return ret; // Return old curpos
\r
451 void Heap_Dump(void)
\r
453 heap_head *cur = _heap_start;
\r
454 while( cur < (heap_head*)_heap_end )
\r
456 if( cur->magic == MAGIC ) {
\r
457 _SysDebug("Used block %p[0x%x] - ptr=%p", cur, cur->size, cur->data);
\r
459 else if( cur->magic == MAGIC_FREE ) {
\r
460 _SysDebug("Free block %p[0x%x] - ptr=%p", cur, cur->size, cur->data);
\r
463 _SysDebug("Block %p bad magic (0x%x)", cur, cur->magic);
\r
466 cur = (void*)( (char*)cur + cur->size );
\r