Usermode/Libraries/libc.so_src/heap.c

   1 /*\r
   2 AcessOS Basic LibC\r
   3 heap.c - Heap Manager\r
   4 */\r
   5 #include <acess/sys.h>\r
   6 #include <stdlib.h>\r
   7 #include "lib.h"\r
   8 \r
   9 // === Constants ===\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
  14 \r
  15 typedef unsigned int Uint;\r
  16 \r
  17 //Typedefs\r
  18 typedef struct {\r
  19         Uint    magic;\r
  20         Uint    size;\r
  21 }       heap_head;\r
  22 typedef struct {\r
  23         heap_head       *header;\r
  24         Uint    magic;\r
  25 }       heap_foot;\r
  26 \r
  27 //Globals\r
  28 void    *_heap_start = NULL;\r
  29 void    *_heap_end = NULL;\r
  30 \r
  31 //Prototypes\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(int delta);\r
  38 \r
  39 //Code\r
  40 \r
  41 /**\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
  46 */\r
  47 EXPORT void *malloc(size_t bytes)\r
  48 {\r
  49         Uint    bestSize;\r
  50         Uint    closestMatch = 0;\r
  51         Uint    bestMatchAddr = 0;\r
  52         heap_head       *curBlock;\r
  53         \r
  54         // Initialise Heap\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
  60         }\r
  61         \r
  62         curBlock = _heap_start;\r
  63         \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
  66         \r
  67         while((Uint)curBlock < (Uint)_heap_end)\r
  68         {\r
  69                 //SysDebug(" malloc: curBlock = 0x%x, curBlock->magic = 0x%x\n", curBlock, curBlock->magic);\r
  70                 if(curBlock->magic == MAGIC_FREE)\r
  71                 {\r
  72                         if(curBlock->size == bestSize)\r
  73                                 break;\r
  74                         if(bestSize < curBlock->size && (curBlock->size < closestMatch || closestMatch == 0)) {\r
  75                                 closestMatch = curBlock->size;\r
  76                                 bestMatchAddr = (Uint)curBlock;\r
  77                         }\r
  78                 }\r
  79                 else if(curBlock->magic != MAGIC)\r
  80                 {\r
  81                         //Corrupt Heap\r
  82                         //SysDebug("malloc: Corrupt Heap\n");\r
  83                         return NULL;\r
  84                 }\r
  85                 curBlock = (heap_head*)((Uint)curBlock + curBlock->size);\r
  86         }\r
  87         \r
  88         if((Uint)curBlock < (Uint)_heap_start) {\r
  89                 //SysDebug("malloc: Heap underrun for some reason\n");\r
  90                 return NULL;\r
  91         }\r
  92         \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
  97         }\r
  98         \r
  99         //Out of Heap Space\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
 104                         return NULL;\r
 105                 }\r
 106                 curBlock->magic = MAGIC;\r
 107                 return (void*)((Uint)curBlock + sizeof(heap_head));\r
 108         }\r
 109         \r
 110         //Split Block?\r
 111         if(closestMatch - bestSize > BLOCK_SIZE) {\r
 112                 heap_foot       *foot;\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
 119 \r
 120                 curBlock = (heap_head*)(bestMatchAddr + bestSize);\r
 121                 curBlock->magic = MAGIC_FREE;\r
 122                 curBlock->size = closestMatch - bestSize;\r
 123                 \r
 124                 foot = (heap_foot*)(bestMatchAddr + closestMatch - sizeof(heap_foot));\r
 125                 foot->header = curBlock;\r
 126                 \r
 127                 ((heap_head*)bestMatchAddr)->magic = MAGIC;     //mark as used\r
 128                 return (void*)(bestMatchAddr + sizeof(heap_head));\r
 129         }\r
 130         \r
 131         //Don't Split the block\r
 132         ((heap_head*)bestMatchAddr)->magic = MAGIC;\r
 133         return (void*)(bestMatchAddr+sizeof(heap_head));\r
 134 }\r
 135 \r
 136 /**\r
 137  \fn EXPORT void free(void *mem)\r
 138  \brief Free previously allocated memory\r
 139  \param mem     Pointer - Memory to free\r
 140 */\r
 141 EXPORT void free(void *mem)\r
 142 {\r
 143         heap_head       *head = mem;\r
 144         \r
 145         if(head->magic != MAGIC)        //Valid Heap Address\r
 146                 return;\r
 147         \r
 148         head->magic = MAGIC_FREE;\r
 149         \r
 150         //Unify Right\r
 151         if((Uint)head + head->size < (Uint)_heap_end)\r
 152         {\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
 157                 }\r
 158         }\r
 159         //Unify Left\r
 160         if((Uint)head - sizeof(heap_foot) > (Uint)_heap_start)\r
 161         {\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
 169                         }\r
 170                 }\r
 171         }\r
 172 }\r
 173 \r
 174 /**\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
 180 */\r
 181 EXPORT void *realloc(void *oldPos, size_t bytes)\r
 182 {\r
 183         void *ret;\r
 184         heap_head       *head;\r
 185         \r
 186         if(oldPos == NULL) {\r
 187                 return malloc(bytes);\r
 188         }\r
 189         \r
 190         //Check for free space after block\r
 191         head = (heap_head*)((Uint)oldPos-sizeof(heap_head));\r
 192         \r
 193         //Hack to used free's amagamating algorithym and malloc's splitting\r
 194         free(oldPos);\r
 195         \r
 196         //Allocate new memory\r
 197         ret = malloc(bytes);\r
 198         if(ret == NULL)\r
 199                 return NULL;\r
 200         \r
 201         //Copy Old Data\r
 202         if((Uint)ret != (Uint)oldPos) {\r
 203                 memcpy(ret, oldPos, head->size-sizeof(heap_head)-sizeof(heap_foot));\r
 204         }\r
 205         \r
 206         //Return\r
 207         return ret;\r
 208 }\r
 209 \r
 210 /**\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
 215  */\r
 216 \r
 217 LOCAL void *extendHeap(int bytes)\r
 218 {\r
 219         heap_head       *head = _heap_end;\r
 220         heap_foot       *foot;\r
 221         \r
 222         //Expand Memory Space  (Use foot as a temp pointer)\r
 223         foot = sbrk(bytes);\r
 224         if(foot == (void*)-1)\r
 225                 return NULL;\r
 226         \r
 227         \r
 228         //Create New Block\r
 229         // Header\r
 230         head->magic = MAGIC_FREE;       //Unallocated\r
 231         head->size = bytes;\r
 232         // Footer\r
 233         foot = _heap_end + bytes - sizeof(heap_foot);\r
 234         foot->header = head;\r
 235         foot->magic = MAGIC;\r
 236         \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
 243                         head = tmpHead;\r
 244                 }\r
 245         }\r
 246         \r
 247         _heap_end = (void*) ((Uint)foot+sizeof(heap_foot));\r
 248         return head;\r
 249 }\r
 250 \r
 251 /**\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
 256 */\r
 257 EXPORT void *sbrk(int increment)\r
 258 {\r
 259         size_t newEnd;\r
 260         static size_t oldEnd = 0;\r
 261         static size_t curEnd = 0;\r
 262 \r
 263         //SysDebug("sbrk: (increment=%i)\n", increment);\r
 264 \r
 265         if (oldEnd == 0)        curEnd = oldEnd = brk(0);\r
 266 \r
 267         //SysDebug(" sbrk: oldEnd = 0x%x\n", oldEnd);\r
 268         if (increment == 0)     return (void *) curEnd;\r
 269 \r
 270         newEnd = curEnd + increment;\r
 271 \r
 272         if (brk(newEnd) == curEnd)      return (void *) -1;\r
 273         oldEnd = curEnd;\r
 274         curEnd = newEnd;\r
 275         //SysDebug(" sbrk: newEnd = 0x%x\n", newEnd);\r
 276 \r
 277         return (void *) oldEnd;\r
 278 }\r
 279 \r
 280 /**\r
 281  * \fn EXPORT int IsHeap(void *ptr)\r
 282  */\r
 283 EXPORT int IsHeap(void *ptr)\r
 284 {\r
 285         #if 0\r
 286         heap_head       *head;\r
 287         heap_foot       *foot;\r
 288         #endif\r
 289         if( (Uint)ptr < (Uint)_heap_start )     return 0;\r
 290         if( (Uint)ptr > (Uint)_heap_end )       return 0;\r
 291         \r
 292         #if 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
 297         #endif\r
 298         return 1;\r
 299 }\r
 300 \r
 301 // === STATIC FUNCTIONS ===\r
 302 /**\r
 303  * Does the job of brk(0)\r
 304  */\r
 305 static void *FindHeapBase()\r
 306 {\r
 307         #define MAX             0xC0000000      // Address\r
 308         #define THRESHOLD       512     // Pages\r
 309         uint    addr;\r
 310         uint    stretch = 0;\r
 311         \r
 312         // Scan address space\r
 313         for(addr = 0;\r
 314                 addr < MAX;\r
 315                 addr += 0x1000\r
 316                 )\r
 317         {\r
 318                 if( _SysGetPhys(addr) == 0 ) {\r
 319                         stretch = 0;\r
 320                 } else {\r
 321                         stretch ++;\r
 322                         if(stretch > THRESHOLD)\r
 323                         {\r
 324                                 return (void*)( addr + stretch*0x1000 );\r
 325                         }\r
 326                 }\r
 327         }\r
 328         return NULL;\r
 329 }\r
 330 \r
 331 LOCAL uint brk(int delta)\r
 332 {\r
 333         static uint     curpos;\r
 334         uint    pages;\r
 335         uint    ret = curpos;\r
 336         \r
 337         // Find initial position\r
 338         if(curpos == 0) curpos = (uint)FindHeapBase();\r
 339         \r
 340         // Get Current Position\r
 341         if(delta == 0)\r
 342         {\r
 343                 return curpos;\r
 344         }\r
 345         \r
 346         // Do we need to add pages\r
 347         if(curpos & 0xFFF && (curpos & 0xFFF) + delta < 0x1000)\r
 348                 return curpos += delta;\r
 349         \r
 350         // Page align current position\r
 351         if(curpos & 0xFFF)      delta -= 0x1000 - (curpos & 0xFFF);\r
 352         curpos = (curpos + 0xFFF) & ~0xFFF;\r
 353         \r
 354         // Allocate Pages\r
 355         pages = (delta + 0xFFF) >> 12;\r
 356         while(pages--)\r
 357         {\r
 358                 _SysAllocate(curpos);\r
 359                 curpos += 0x1000;\r
 360                 delta -= 0x1000;\r
 361         }\r
 362         \r
 363         // Bring the current position to exactly what we want\r
 364         curpos -= ((delta + 0xFFF) & ~0xFFF) - delta;\r
 365         \r
 366         return ret;     // Return old curpos\r
 367 }\r