Usermode/Applications/axwin0_src/heap.c

   1 /*\r
   2 AcessOS Basic LibC\r
   3 Malloc.c - Heap Manager\r
   4 */\r
   5 \r
   6 #include "header.h"\r
   7 \r
   8 #define MAGIC   0xACE2ACED      //AcessOS1\r
   9 #define MAGIC_FREE      (~MAGIC)        //AcessOS1\r
  10 #define BLOCK_SIZE      16      //Minimum\r
  11 \r
  12 //Typedefs\r
  13 typedef struct {\r
  14         Uint    magic;\r
  15         Uint    size;\r
  16 }       heap_head;\r
  17 typedef struct {\r
  18         heap_head       *header;\r
  19         Uint    magic;\r
  20 }       heap_foot;\r
  21 \r
  22 //Globals\r
  23 void    *heap_start = NULL;\r
  24 void    *heap_end;\r
  25 Uint    endHeap;\r
  26 \r
  27 //Prototypes\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
  32 \r
  33 //Code\r
  34 /* Initialise Heap\r
  35  */\r
  36 void heap_init()\r
  37 {\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
  42 }\r
  43 \r
  44 void *malloc(Uint bytes)\r
  45 {\r
  46         Uint    bestSize;\r
  47         Uint    closestMatch = 0;\r
  48         Uint    bestMatchAddr = 0;\r
  49         heap_head       *curBlock = heap_start;\r
  50         \r
  51         if(heap_start == NULL) {\r
  52                 heap_init();\r
  53                 curBlock = heap_start;\r
  54         }\r
  55         \r
  56         bestSize = ((bytes+sizeof(heap_head)+sizeof(heap_foot))/BLOCK_SIZE+1)*BLOCK_SIZE;       //Round up to block size\r
  57         \r
  58         while((Uint)curBlock < (Uint)heap_end)\r
  59         {\r
  60                 if(curBlock->magic == MAGIC_FREE)\r
  61                 {\r
  62                         //foundFree = 1;\r
  63                         if(curBlock->size == bestSize)\r
  64                                 break;\r
  65                         if(bestSize < curBlock->size && (curBlock->size < closestMatch || closestMatch == 0)) {\r
  66                                 closestMatch = curBlock->size;\r
  67                                 bestMatchAddr = (Uint)curBlock;\r
  68                         }\r
  69                 } else if(curBlock->magic != MAGIC) {\r
  70                         //Corrupt Heap\r
  71                         return NULL;\r
  72                 }\r
  73                 curBlock = (heap_head*)((Uint)curBlock + curBlock->size);\r
  74         }\r
  75         \r
  76         if((Uint)curBlock < (Uint)heap_start) {\r
  77                 //panic("malloc: Heap underrun for some reason\n");\r
  78                 return NULL;\r
  79         }\r
  80         \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
  85         }\r
  86         \r
  87         //Out of Heap Space\r
  88         if(!closestMatch)\r
  89         {\r
  90                 #if 0\r
  91                 curBlock = extendHeap(bestSize);        //Allocate more\r
  92                 if(curBlock == NULL) {\r
  93                         //panic("malloc: Out of kernel heap memory\n");\r
  94                         return NULL;\r
  95                 }\r
  96                 curBlock->magic = MAGIC;\r
  97                 return (void*)((Uint)curBlock + sizeof(heap_head));\r
  98                 #else\r
  99                 return NULL;\r
 100                 #endif\r
 101         }\r
 102         \r
 103         //Split Block?\r
 104         if(closestMatch - bestSize > BLOCK_SIZE) {\r
 105                 heap_foot       *foot;\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
 112 \r
 113                 curBlock = (heap_head*)(bestMatchAddr + bestSize);\r
 114                 curBlock->magic = MAGIC_FREE;\r
 115                 curBlock->size = closestMatch - bestSize;\r
 116                 \r
 117                 foot = (heap_foot*)(bestMatchAddr + closestMatch - sizeof(heap_foot));\r
 118                 foot->header = curBlock;\r
 119                 \r
 120                 ((heap_head*)bestMatchAddr)->magic = MAGIC;     //mark as used\r
 121                 return (void*)(bestMatchAddr + sizeof(heap_head));\r
 122         }\r
 123         \r
 124         //Don't Split the block\r
 125         ((heap_head*)bestMatchAddr)->magic = MAGIC;\r
 126         return (void*)(bestMatchAddr+sizeof(heap_head));\r
 127 }\r
 128 \r
 129 /* Free previously allocated memory\r
 130  */\r
 131 void free(void *mem)\r
 132 {\r
 133         heap_head       *head = mem;\r
 134         \r
 135         if(head->magic != MAGIC)        //Valid Heap Address\r
 136                 return;\r
 137         \r
 138         head->magic = MAGIC_FREE;\r
 139         \r
 140         //Unify Right\r
 141         if((Uint)head + head->size < (Uint)heap_end)\r
 142         {\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
 147                 }\r
 148         }\r
 149         //Unify Left\r
 150         if((Uint)head - sizeof(heap_foot) > (Uint)heap_start)\r
 151         {\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
 159                         }\r
 160                 }\r
 161         }\r
 162 }\r
 163 \r
 164 /* Create a new block at the end of the heap area\r
 165  */\r
 166 void *extendHeap(int bytes)\r
 167 {\r
 168         heap_head       *head = heap_end;\r
 169         heap_foot       *foot = (heap_foot*)(((Uint)heap_end) + bytes-sizeof(heap_foot));\r
 170         \r
 171         //Create New Block\r
 172         head->magic = MAGIC_FREE;       //Unallocated\r
 173         head->size = bytes;\r
 174         \r
 175         foot->header = head;\r
 176         foot->magic = MAGIC;\r
 177         \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
 184                         head = tmpHead;\r
 185                 }\r
 186         }\r
 187         \r
 188         heap_end = (void*) ((Uint)foot+sizeof(heap_foot));\r
 189         return head;\r
 190 }\r
 191 \r
 192 /* Reallocate a block of memory\r
 193  */\r
 194 void *realloc(Uint bytes, void *oldPos)\r
 195 {\r
 196         void *ret;\r
 197         heap_head       *head;\r
 198         \r
 199         if(oldPos == NULL) {\r
 200                 return malloc(bytes);\r
 201         }\r
 202         \r
 203         //Check for free space after block\r
 204         head = (heap_head*)((Uint)oldPos-sizeof(heap_head));\r
 205         \r
 206         //Hack to used free's amagamating algorithym and malloc's splitting\r
 207         free(oldPos);\r
 208         \r
 209         //Allocate new memory\r
 210         ret = malloc(bytes);\r
 211         if(ret == NULL)\r
 212                 return NULL;\r
 213         \r
 214         //Copy Old Data\r
 215         if((Uint)ret != (Uint)oldPos)\r
 216         {\r
 217                 Uint    *in, *out;\r
 218                 Uint    count;\r
 219                 count = head->size - sizeof(heap_head) - sizeof(heap_foot);\r
 220                 if((Uint)ret < (Uint)out)\r
 221                 {\r
 222                         out = ret;              in = oldPos;\r
 223                         while(count--)  *out++ = *in++;\r
 224                 }\r
 225                 else\r
 226                 {\r
 227                         out = ret;              in = oldPos;\r
 228                         out += count;   in += count;\r
 229                         while(count--)  *--out = *--in;\r
 230                 }\r
 231         }\r
 232         \r
 233         //Return\r
 234         return ret;\r
 235 }\r