3 heap.c - Heap Manager
\r
5 #include <acess/sys.h>
\r
10 #define MAGIC 0xACE55051 //AcessOS1
\r
11 #define MAGIC_FREE (~MAGIC)
\r
12 #define BLOCK_SIZE 16 //Minimum
\r
13 #define HEAP_INIT_SIZE 0x10000
\r
15 typedef unsigned int Uint;
\r
28 void *_heap_start = NULL;
\r
29 void *_heap_end = NULL;
\r
32 EXPORT void *malloc(Uint bytes);
\r
33 EXPORT void free(void *mem);
\r
34 EXPORT void *realloc(void *mem, Uint bytes);
\r
35 EXPORT void *sbrk(int increment);
\r
36 LOCAL void *extendHeap(int bytes);
\r
37 LOCAL uint brk(Uint newpos);
\r
42 \fn EXPORT void *malloc(size_t bytes)
\r
43 \brief Allocates memory from the heap space
\r
44 \param bytes Integer - Size of buffer to return
\r
45 \return Pointer to buffer
\r
47 EXPORT void *malloc(size_t bytes)
\r
50 Uint closestMatch = 0;
\r
51 Uint bestMatchAddr = 0;
\r
52 heap_head *curBlock;
\r
55 if(_heap_start == NULL)
\r
56 {LOCAL void *sbrk(int delta);
\r
57 _heap_start = sbrk(0);
\r
58 _heap_end = _heap_start;
\r
59 extendHeap(HEAP_INIT_SIZE);
\r
62 curBlock = _heap_start;
\r
64 bestSize = bytes + sizeof(heap_head) + sizeof(heap_foot) + BLOCK_SIZE - 1;
\r
65 bestSize = (bestSize/BLOCK_SIZE)*BLOCK_SIZE; //Round up to block size
\r
67 while((Uint)curBlock < (Uint)_heap_end)
\r
69 //SysDebug(" malloc: curBlock = 0x%x, curBlock->magic = 0x%x\n", curBlock, curBlock->magic);
\r
70 if(curBlock->magic == MAGIC_FREE)
\r
72 if(curBlock->size == bestSize)
\r
74 if(bestSize < curBlock->size && (curBlock->size < closestMatch || closestMatch == 0)) {
\r
75 closestMatch = curBlock->size;
\r
76 bestMatchAddr = (Uint)curBlock;
\r
79 else if(curBlock->magic != MAGIC)
\r
82 //SysDebug("malloc: Corrupt Heap\n");
\r
85 curBlock = (heap_head*)((Uint)curBlock + curBlock->size);
\r
88 if((Uint)curBlock < (Uint)_heap_start) {
\r
89 //SysDebug("malloc: Heap underrun for some reason\n");
\r
93 //Found a perfect match
\r
94 if((Uint)curBlock < (Uint)_heap_end) {
\r
95 curBlock->magic = MAGIC;
\r
96 return (void*)((Uint)curBlock + sizeof(heap_head));
\r
100 if(!closestMatch) {
\r
101 curBlock = extendHeap(bestSize); //Allocate more
\r
102 if(curBlock == NULL) {
\r
103 //SysDebug("malloc: Out of Heap Space\n");
\r
106 curBlock->magic = MAGIC;
\r
107 return (void*)((Uint)curBlock + sizeof(heap_head));
\r
111 if(closestMatch - bestSize > BLOCK_SIZE) {
\r
113 curBlock = (heap_head*)bestMatchAddr;
\r
114 curBlock->magic = MAGIC;
\r
115 curBlock->size = bestSize;
\r
116 foot = (heap_foot*)(bestMatchAddr + bestSize - sizeof(heap_foot));
\r
117 foot->header = curBlock;
\r
118 foot->magic = MAGIC;
\r
120 curBlock = (heap_head*)(bestMatchAddr + bestSize);
\r
121 curBlock->magic = MAGIC_FREE;
\r
122 curBlock->size = closestMatch - bestSize;
\r
124 foot = (heap_foot*)(bestMatchAddr + closestMatch - sizeof(heap_foot));
\r
125 foot->header = curBlock;
\r
127 ((heap_head*)bestMatchAddr)->magic = MAGIC; //mark as used
\r
128 return (void*)(bestMatchAddr + sizeof(heap_head));
\r
131 //Don't Split the block
\r
132 ((heap_head*)bestMatchAddr)->magic = MAGIC;
\r
133 return (void*)(bestMatchAddr+sizeof(heap_head));
\r
137 \fn EXPORT void free(void *mem)
\r
138 \brief Free previously allocated memory
\r
139 \param mem Pointer - Memory to free
\r
141 EXPORT void free(void *mem)
\r
143 heap_head *head = mem;
\r
145 if(head->magic != MAGIC) //Valid Heap Address
\r
148 head->magic = MAGIC_FREE;
\r
151 if((Uint)head + head->size < (Uint)_heap_end)
\r
153 heap_head *nextHead = (heap_head*)((Uint)head + head->size);
\r
154 if(nextHead->magic == MAGIC_FREE) { //Is the next block free
\r
155 head->size += nextHead->size; //Amalgamate
\r
156 nextHead->magic = 0; //For Security
\r
160 if((Uint)head - sizeof(heap_foot) > (Uint)_heap_start)
\r
162 heap_head *prevHead;
\r
163 heap_foot *prevFoot = (heap_foot *)((Uint)head - sizeof(heap_foot));
\r
164 if(prevFoot->magic == MAGIC) {
\r
165 prevHead = prevFoot->header;
\r
166 if(prevHead->magic == MAGIC_FREE) {
\r
167 prevHead->size += head->size; //Amalgamate
\r
168 head->magic = 0; //For Security
\r
175 \fn EXPORT void *realloc(void *oldPos, size_t bytes)
\r
176 \brief Reallocate a block of memory
\r
177 \param bytes Integer - Size of new buffer
\r
178 \param oldPos Pointer - Old Buffer
\r
179 \return Pointer to new buffer
\r
181 EXPORT void *realloc(void *oldPos, size_t bytes)
\r
186 if(oldPos == NULL) {
\r
187 return malloc(bytes);
\r
190 //Check for free space after block
\r
191 head = (heap_head*)((Uint)oldPos-sizeof(heap_head));
\r
193 //Hack to used free's amagamating algorithym and malloc's splitting
\r
196 //Allocate new memory
\r
197 ret = malloc(bytes);
\r
202 if((Uint)ret != (Uint)oldPos) {
\r
203 memcpy(ret, oldPos, head->size-sizeof(heap_head)-sizeof(heap_foot));
\r
211 \fn LOCAL void *extendHeap(int bytes)
\r
212 \brief Create a new block at the end of the heap area
\r
213 \param bytes Integer - Size reqired
\r
214 \return Pointer to last free block
\r
217 LOCAL void *extendHeap(int bytes)
\r
219 heap_head *head = _heap_end;
\r
222 //Expand Memory Space (Use foot as a temp pointer)
\r
223 foot = sbrk(bytes);
\r
224 if(foot == (void*)-1)
\r
230 head->magic = MAGIC_FREE; //Unallocated
\r
231 head->size = bytes;
\r
233 foot = _heap_end + bytes - sizeof(heap_foot);
\r
234 foot->header = head;
\r
235 foot->magic = MAGIC;
\r
237 //Combine with previous block if nessasary
\r
238 if(_heap_end != _heap_start && ((heap_foot*)((Uint)_heap_end-sizeof(heap_foot)))->magic == MAGIC) {
\r
239 heap_head *tmpHead = ((heap_foot*)((Uint)_heap_end-sizeof(heap_foot)))->header;
\r
240 if(tmpHead->magic == MAGIC_FREE) {
\r
241 tmpHead->size += bytes;
\r
242 foot->header = tmpHead;
\r
247 _heap_end = (void*) ((Uint)foot+sizeof(heap_foot));
\r
252 \fn EXPORT void *sbrk(int increment)
\r
253 \brief Increases the program's memory space
\r
254 \param count Integer - Size of heap increase
\r
255 \return Pointer to start of new region
\r
257 EXPORT void *sbrk(int increment)
\r
260 static size_t oldEnd = 0;
\r
261 static size_t curEnd = 0;
\r
263 //_SysDebug("sbrk: (increment=%i)\n", increment);
\r
265 if (oldEnd == 0) curEnd = oldEnd = brk(0);
\r
267 //SysDebug(" sbrk: oldEnd = 0x%x\n", oldEnd);
\r
268 if (increment == 0) return (void *) curEnd;
\r
270 newEnd = curEnd + increment;
\r
272 if (brk(newEnd) == curEnd) return (void *) -1;
\r
275 //SysDebug(" sbrk: newEnd = 0x%x\n", newEnd);
\r
277 return (void *) oldEnd;
\r
281 * \fn EXPORT int IsHeap(void *ptr)
\r
283 EXPORT int IsHeap(void *ptr)
\r
289 if( (Uint)ptr < (Uint)_heap_start ) return 0;
\r
290 if( (Uint)ptr > (Uint)_heap_end ) return 0;
\r
293 head = (void*)((Uint)ptr - 4);
\r
294 if( head->magic != MAGIC ) return 0;
\r
295 foot = (void*)( (Uint)ptr + head->size - sizeof(heap_foot) );
\r
296 if( foot->magic != MAGIC ) return 0;
\r
301 // === STATIC FUNCTIONS ===
\r
303 * Does the job of brk(0)
\r
305 static void *FindHeapBase()
\r
307 #define MAX 0xC0000000 // Address
\r
308 #define THRESHOLD 512 // Pages
\r
312 // Scan address space
\r
318 if( _SysGetPhys(addr) == 0 ) {
\r
322 if(stretch > THRESHOLD)
\r
324 return (void*)( addr + stretch*0x1000 );
\r
331 LOCAL uint brk(Uint newpos)
\r
333 static uint curpos;
\r
338 //_SysDebug("brk: (newpos=0x%x)", newpos);
\r
340 // Find initial position
\r
341 if(curpos == 0) curpos = (uint)FindHeapBase();
\r
343 // Get Current Position
\r
344 if(newpos == 0) return curpos;
\r
346 if(newpos < curpos) return newpos;
\r
348 delta = newpos - curpos;
\r
349 //_SysDebug(" brk: delta = 0x%x", delta);
\r
351 // Do we need to add pages
\r
352 if(curpos & 0xFFF && (curpos & 0xFFF) + delta < 0x1000)
\r
353 return curpos += delta;
\r
355 // Page align current position
\r
356 if(curpos & 0xFFF) delta -= 0x1000 - (curpos & 0xFFF);
\r
357 curpos = (curpos + 0xFFF) & ~0xFFF;
\r
360 pages = (delta + 0xFFF) >> 12;
\r
363 _SysAllocate(curpos);
\r
368 // Bring the current position to exactly what we want
\r
369 curpos -= ((delta + 0xFFF) & ~0xFFF) - delta;
\r
371 return ret; // Return old curpos
\r