3 Malloc.c - Heap Manager
\r
8 #define MAGIC 0xACE2ACED //AcessOS1
\r
9 #define MAGIC_FREE (~MAGIC) //AcessOS1
\r
10 #define BLOCK_SIZE 16 //Minimum
\r
23 void *heap_start = NULL;
\r
28 void *malloc(Uint bytes);
\r
29 void free(void *mem);
\r
30 void *realloc(Uint bytes, void *mem);
\r
31 void *extendHeap(int bytes);
\r
38 heap_start = (void*)( (gAxeHdr.loadto + gAxeHdr.length + 0xFFF) & 0xFFFFF000) ;
\r
39 heap_end = heap_start;
\r
40 extendHeap( gAxeHdr.maxmem );
\r
41 endHeap = (Uint)heap_start + gAxeHdr.maxmem;
\r
44 void *malloc(Uint bytes)
\r
47 Uint closestMatch = 0;
\r
48 Uint bestMatchAddr = 0;
\r
49 heap_head *curBlock = heap_start;
\r
51 if(heap_start == NULL) {
\r
53 curBlock = heap_start;
\r
56 bestSize = ((bytes+sizeof(heap_head)+sizeof(heap_foot))/BLOCK_SIZE+1)*BLOCK_SIZE; //Round up to block size
\r
58 while((Uint)curBlock < (Uint)heap_end)
\r
60 if(curBlock->magic == MAGIC_FREE)
\r
63 if(curBlock->size == bestSize)
\r
65 if(bestSize < curBlock->size && (curBlock->size < closestMatch || closestMatch == 0)) {
\r
66 closestMatch = curBlock->size;
\r
67 bestMatchAddr = (Uint)curBlock;
\r
69 } else if(curBlock->magic != MAGIC) {
\r
73 curBlock = (heap_head*)((Uint)curBlock + curBlock->size);
\r
76 if((Uint)curBlock < (Uint)heap_start) {
\r
77 //panic("malloc: Heap underrun for some reason\n");
\r
81 //Found a perfect match
\r
82 if((Uint)curBlock < (Uint)heap_end) {
\r
83 curBlock->magic = MAGIC;
\r
84 return (void*)((Uint)curBlock + sizeof(heap_head));
\r
91 curBlock = extendHeap(bestSize); //Allocate more
\r
92 if(curBlock == NULL) {
\r
93 //panic("malloc: Out of kernel heap memory\n");
\r
96 curBlock->magic = MAGIC;
\r
97 return (void*)((Uint)curBlock + sizeof(heap_head));
\r
104 if(closestMatch - bestSize > BLOCK_SIZE) {
\r
106 curBlock = (heap_head*)bestMatchAddr;
\r
107 curBlock->magic = MAGIC;
\r
108 curBlock->size = bestSize;
\r
109 foot = (heap_foot*)(bestMatchAddr + bestSize - sizeof(heap_foot));
\r
110 foot->header = curBlock;
\r
111 foot->magic = MAGIC;
\r
113 curBlock = (heap_head*)(bestMatchAddr + bestSize);
\r
114 curBlock->magic = MAGIC_FREE;
\r
115 curBlock->size = closestMatch - bestSize;
\r
117 foot = (heap_foot*)(bestMatchAddr + closestMatch - sizeof(heap_foot));
\r
118 foot->header = curBlock;
\r
120 ((heap_head*)bestMatchAddr)->magic = MAGIC; //mark as used
\r
121 return (void*)(bestMatchAddr + sizeof(heap_head));
\r
124 //Don't Split the block
\r
125 ((heap_head*)bestMatchAddr)->magic = MAGIC;
\r
126 return (void*)(bestMatchAddr+sizeof(heap_head));
\r
129 /* Free previously allocated memory
\r
131 void free(void *mem)
\r
133 heap_head *head = mem;
\r
135 if(head->magic != MAGIC) //Valid Heap Address
\r
138 head->magic = MAGIC_FREE;
\r
141 if((Uint)head + head->size < (Uint)heap_end)
\r
143 heap_head *nextHead = (heap_head*)((Uint)head + head->size);
\r
144 if(nextHead->magic == MAGIC_FREE) { //Is the next block free
\r
145 head->size += nextHead->size; //Amalgamate
\r
146 nextHead->magic = 0; //For Security
\r
150 if((Uint)head - sizeof(heap_foot) > (Uint)heap_start)
\r
152 heap_head *prevHead;
\r
153 heap_foot *prevFoot = (heap_foot *)((Uint)head - sizeof(heap_foot));
\r
154 if(prevFoot->magic == MAGIC) {
\r
155 prevHead = prevFoot->header;
\r
156 if(prevHead->magic == MAGIC_FREE) {
\r
157 prevHead->size += head->size; //Amalgamate
\r
158 head->magic = 0; //For Security
\r
164 /* Create a new block at the end of the heap area
\r
166 void *extendHeap(int bytes)
\r
168 heap_head *head = heap_end;
\r
169 heap_foot *foot = (heap_foot*)(((Uint)heap_end) + bytes-sizeof(heap_foot));
\r
172 head->magic = MAGIC_FREE; //Unallocated
\r
173 head->size = bytes;
\r
175 foot->header = head;
\r
176 foot->magic = MAGIC;
\r
178 //Combine with previous block if nessasary
\r
179 if(heap_end != heap_start && ((heap_foot*)((Uint)heap_end-sizeof(heap_foot)))->magic == MAGIC) {
\r
180 heap_head *tmpHead = ((heap_foot*)((Uint)heap_end-sizeof(heap_foot)))->header;
\r
181 if(tmpHead->magic == MAGIC_FREE) {
\r
182 tmpHead->size += bytes;
\r
183 foot->header = tmpHead;
\r
188 heap_end = (void*) ((Uint)foot+sizeof(heap_foot));
\r
192 /* Reallocate a block of memory
\r
194 void *realloc(Uint bytes, void *oldPos)
\r
199 if(oldPos == NULL) {
\r
200 return malloc(bytes);
\r
203 //Check for free space after block
\r
204 head = (heap_head*)((Uint)oldPos-sizeof(heap_head));
\r
206 //Hack to used free's amagamating algorithym and malloc's splitting
\r
209 //Allocate new memory
\r
210 ret = malloc(bytes);
\r
215 if((Uint)ret != (Uint)oldPos)
\r
219 count = head->size - sizeof(heap_head) - sizeof(heap_foot);
\r
220 if((Uint)ret < (Uint)out)
\r
222 out = ret; in = oldPos;
\r
223 while(count--) *out++ = *in++;
\r
227 out = ret; in = oldPos;
\r
228 out += count; in += count;
\r
229 while(count--) *--out = *--in;
\r