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 <string.h>\r
   8 #include "lib.h"\r
   9 \r
  10 // === Constants ===\r
  11 #define MAGIC   0xACE55051      //AcessOS1\r
  12 #define MAGIC_FREE      (~MAGIC)\r
  13 #define BLOCK_SIZE      16      //Minimum\r
  14 #define HEAP_INIT_SIZE  0x10000\r
  15 \r
  16 typedef unsigned int Uint;\r
  17 \r
  18 // === TYPES ===\r
  19 typedef struct {\r
  20         Uint    magic;\r
  21         Uint    size;\r
  22 }       heap_head;\r
  23 typedef struct {\r
  24         heap_head       *header;\r
  25         Uint    magic;\r
  26 }       heap_foot;\r
  27 \r
  28 // === LOCAL VARIABLES ===\r
  29 static void     *_heap_start = NULL;\r
  30 static void     *_heap_end = NULL;\r
  31 \r
  32 // === PROTOTYPES ===\r
  33 EXPORT void     *malloc(size_t bytes);\r
  34 EXPORT void     *calloc(size_t bytes, size_t count);\r
  35 EXPORT void     free(void *mem);\r
  36 EXPORT void     *realloc(void *mem, Uint bytes);\r
  37 EXPORT void     *sbrk(int increment);\r
  38 LOCAL void      *extendHeap(int bytes);\r
  39 LOCAL uint      brk(Uint newpos);\r
  40 \r
  41 //Code\r
  42 \r
  43 /**\r
  44  \fn EXPORT void *malloc(size_t bytes)\r
  45  \brief Allocates memory from the heap space\r
  46  \param bytes   Integer - Size of buffer to return\r
  47  \return Pointer to buffer\r
  48 */\r
  49 EXPORT void *malloc(size_t bytes)\r
  50 {\r
  51         Uint    bestSize;\r
  52         Uint    closestMatch = 0;\r
  53         Uint    bestMatchAddr = 0;\r
  54         heap_head       *curBlock;\r
  55         \r
  56         // Initialise Heap\r
  57         if(_heap_start == NULL)\r
  58         {\r
  59                 _heap_start = sbrk(0);\r
  60                 _heap_end = _heap_start;\r
  61                 extendHeap(HEAP_INIT_SIZE);\r
  62         }\r
  63         \r
  64         curBlock = _heap_start;\r
  65         \r
  66         bestSize = bytes + sizeof(heap_head) + sizeof(heap_foot) + BLOCK_SIZE - 1;\r
  67         bestSize = (bestSize/BLOCK_SIZE)*BLOCK_SIZE;    //Round up to block size\r
  68         \r
  69         while((Uint)curBlock < (Uint)_heap_end)\r
  70         {\r
  71                 //SysDebug(" malloc: curBlock = 0x%x, curBlock->magic = 0x%x\n", curBlock, curBlock->magic);\r
  72                 if(curBlock->magic == MAGIC_FREE)\r
  73                 {\r
  74                         if(curBlock->size == bestSize)\r
  75                                 break;\r
  76                         if(bestSize < curBlock->size && (curBlock->size < closestMatch || closestMatch == 0)) {\r
  77                                 closestMatch = curBlock->size;\r
  78                                 bestMatchAddr = (Uint)curBlock;\r
  79                         }\r
  80                 }\r
  81                 else if(curBlock->magic != MAGIC)\r
  82                 {\r
  83                         //Corrupt Heap\r
  84                         //SysDebug("malloc: Corrupt Heap\n");\r
  85                         return NULL;\r
  86                 }\r
  87                 curBlock = (heap_head*)((Uint)curBlock + curBlock->size);\r
  88         }\r
  89         \r
  90         if((Uint)curBlock < (Uint)_heap_start) {\r
  91                 //SysDebug("malloc: Heap underrun for some reason\n");\r
  92                 return NULL;\r
  93         }\r
  94         \r
  95         //Found a perfect match\r
  96         if((Uint)curBlock < (Uint)_heap_end) {\r
  97                 curBlock->magic = MAGIC;\r
  98                 return (void*)((Uint)curBlock + sizeof(heap_head));\r
  99         }\r
 100         \r
 101         //Out of Heap Space\r
 102         if(!closestMatch) {\r
 103                 curBlock = extendHeap(bestSize);        //Allocate more\r
 104                 if(curBlock == NULL) {\r
 105                         //SysDebug("malloc: Out of Heap Space\n");\r
 106                         return NULL;\r
 107                 }\r
 108                 curBlock->magic = MAGIC;\r
 109                 return (void*)((Uint)curBlock + sizeof(heap_head));\r
 110         }\r
 111         \r
 112         //Split Block?\r
 113         if(closestMatch - bestSize > BLOCK_SIZE) {\r
 114                 heap_foot       *foot;\r
 115                 curBlock = (heap_head*)bestMatchAddr;\r
 116                 curBlock->magic = MAGIC;\r
 117                 curBlock->size = bestSize;\r
 118                 foot = (heap_foot*)(bestMatchAddr + bestSize - sizeof(heap_foot));\r
 119                 foot->header = curBlock;\r
 120                 foot->magic = MAGIC;\r
 121 \r
 122                 curBlock = (heap_head*)(bestMatchAddr + bestSize);\r
 123                 curBlock->magic = MAGIC_FREE;\r
 124                 curBlock->size = closestMatch - bestSize;\r
 125                 \r
 126                 foot = (heap_foot*)(bestMatchAddr + closestMatch - sizeof(heap_foot));\r
 127                 foot->header = curBlock;\r
 128                 \r
 129                 ((heap_head*)bestMatchAddr)->magic = MAGIC;     //mark as used\r
 130                 return (void*)(bestMatchAddr + sizeof(heap_head));\r
 131         }\r
 132         \r
 133         //Don't Split the block\r
 134         ((heap_head*)bestMatchAddr)->magic = MAGIC;\r
 135         return (void*)(bestMatchAddr+sizeof(heap_head));\r
 136 }\r
 137 \r
 138 /**\r
 139  * \fn EXPORT void *calloc(size_t bytes, size_t count)\r
 140  * \brief Allocate and zero a block of memory\r
 141  * \param __nmemb       Number of memeber elements\r
 142  * \param __size        Size of one element\r
 143  */\r
 144 EXPORT void *calloc(size_t __nmemb, size_t __size)\r
 145 {\r
 146         void    *ret = malloc(__size*__nmemb);\r
 147         if(!ret)        return NULL;\r
 148         memset(ret, 0, __size*__nmemb);\r
 149         return ret;\r
 150 }\r
 151 \r
 152 /**\r
 153  \fn EXPORT void free(void *mem)\r
 154  \brief Free previously allocated memory\r
 155  \param mem     Pointer - Memory to free\r
 156 */\r
 157 EXPORT void free(void *mem)\r
 158 {\r
 159         heap_head       *head = (void*)((intptr_t)mem-sizeof(heap_head));\r
 160         \r
 161         // Sanity please!\r
 162         if(!mem)        return;\r
 163         \r
 164         if(head->magic != MAGIC)        //Valid Heap Address\r
 165                 return;\r
 166         \r
 167         head->magic = MAGIC_FREE;\r
 168         \r
 169         //Unify Right\r
 170         if((intptr_t)head + head->size < (intptr_t)_heap_end)\r
 171         {\r
 172                 heap_head       *nextHead = (heap_head*)((intptr_t)head + head->size);\r
 173                 if(nextHead->magic == MAGIC_FREE) {     //Is the next block free\r
 174                         head->size += nextHead->size;   //Amalgamate\r
 175                         nextHead->magic = 0;    //For Security\r
 176                 }\r
 177         }\r
 178         //Unify Left\r
 179         if((intptr_t)head - sizeof(heap_foot) > (intptr_t)_heap_start)\r
 180         {\r
 181                 heap_head       *prevHead;\r
 182                 heap_foot       *prevFoot = (heap_foot *)((intptr_t)head - sizeof(heap_foot));\r
 183                 if(prevFoot->magic == MAGIC) {\r
 184                         prevHead = prevFoot->header;\r
 185                         if(prevHead->magic == MAGIC_FREE) {\r
 186                                 prevHead->size += head->size;   //Amalgamate\r
 187                                 head->magic = 0;        //For Security\r
 188                         }\r
 189                 }\r
 190         }\r
 191 }\r
 192 \r
 193 /**\r
 194  \fn EXPORT void *realloc(void *oldPos, size_t bytes)\r
 195  \brief Reallocate a block of memory\r
 196  \param bytes   Integer - Size of new buffer\r
 197  \param oldPos  Pointer - Old Buffer\r
 198  \return Pointer to new buffer\r
 199 */\r
 200 EXPORT void *realloc(void *oldPos, size_t bytes)\r
 201 {\r
 202         void *ret;\r
 203         heap_head       *head;\r
 204         \r
 205         if(oldPos == NULL) {\r
 206                 return malloc(bytes);\r
 207         }\r
 208         \r
 209         //Check for free space after block\r
 210         head = (heap_head*)((Uint)oldPos-sizeof(heap_head));\r
 211         \r
 212         //Hack to used free's amagamating algorithym and malloc's splitting\r
 213         free(oldPos);\r
 214         \r
 215         //Allocate new memory\r
 216         ret = malloc(bytes);\r
 217         if(ret == NULL)\r
 218                 return NULL;\r
 219         \r
 220         //Copy Old Data\r
 221         if((Uint)ret != (Uint)oldPos) {\r
 222                 memcpy(ret, oldPos, head->size-sizeof(heap_head)-sizeof(heap_foot));\r
 223         }\r
 224         \r
 225         //Return\r
 226         return ret;\r
 227 }\r
 228 \r
 229 /**\r
 230  * \fn LOCAL void *extendHeap(int bytes)\r
 231  * \brief Create a new block at the end of the heap area\r
 232  * \param bytes Integer - Size reqired\r
 233  * \return Pointer to last free block\r
 234  */\r
 235 \r
 236 LOCAL void *extendHeap(int bytes)\r
 237 {\r
 238         heap_head       *head = _heap_end;\r
 239         heap_foot       *foot;\r
 240         \r
 241         //Expand Memory Space  (Use foot as a temp pointer)\r
 242         foot = sbrk(bytes);\r
 243         if(foot == (void*)-1)\r
 244                 return NULL;\r
 245         \r
 246         \r
 247         //Create New Block\r
 248         // Header\r
 249         head->magic = MAGIC_FREE;       //Unallocated\r
 250         head->size = bytes;\r
 251         // Footer\r
 252         foot = _heap_end + bytes - sizeof(heap_foot);\r
 253         foot->header = head;\r
 254         foot->magic = MAGIC;\r
 255         \r
 256         //Combine with previous block if nessasary\r
 257         if(_heap_end != _heap_start && ((heap_foot*)((Uint)_heap_end-sizeof(heap_foot)))->magic == MAGIC) {\r
 258                 heap_head       *tmpHead = ((heap_foot*)((Uint)_heap_end-sizeof(heap_foot)))->header;\r
 259                 if(tmpHead->magic == MAGIC_FREE) {\r
 260                         tmpHead->size += bytes;\r
 261                         foot->header = tmpHead;\r
 262                         head = tmpHead;\r
 263                 }\r
 264         }\r
 265         \r
 266         _heap_end = (void*) ((Uint)foot+sizeof(heap_foot));\r
 267         return head;\r
 268 }\r
 269 \r
 270 /**\r
 271  \fn EXPORT void *sbrk(int increment)\r
 272  \brief Increases the program's memory space\r
 273  \param count   Integer - Size of heap increase\r
 274  \return Pointer to start of new region\r
 275 */\r
 276 EXPORT void *sbrk(int increment)\r
 277 {\r
 278         size_t newEnd;\r
 279         static size_t oldEnd = 0;\r
 280         static size_t curEnd = 0;\r
 281 \r
 282         //_SysDebug("sbrk: (increment=%i)\n", increment);\r
 283 \r
 284         if (oldEnd == 0)        curEnd = oldEnd = brk(0);\r
 285 \r
 286         //SysDebug(" sbrk: oldEnd = 0x%x\n", oldEnd);\r
 287         if (increment == 0)     return (void *) curEnd;\r
 288 \r
 289         newEnd = curEnd + increment;\r
 290 \r
 291         if (brk(newEnd) == curEnd)      return (void *) -1;\r
 292         oldEnd = curEnd;\r
 293         curEnd = newEnd;\r
 294         //SysDebug(" sbrk: newEnd = 0x%x\n", newEnd);\r
 295 \r
 296         return (void *) oldEnd;\r
 297 }\r
 298 \r
 299 /**\r
 300  * \fn EXPORT int IsHeap(void *ptr)\r
 301  */\r
 302 EXPORT int IsHeap(void *ptr)\r
 303 {\r
 304         #if 0\r
 305         heap_head       *head;\r
 306         heap_foot       *foot;\r
 307         #endif\r
 308         if( (Uint)ptr < (Uint)_heap_start )     return 0;\r
 309         if( (Uint)ptr > (Uint)_heap_end )       return 0;\r
 310         \r
 311         #if 0\r
 312         head = (void*)((Uint)ptr - 4);\r
 313         if( head->magic != MAGIC )      return 0;\r
 314         foot = (void*)( (Uint)ptr + head->size - sizeof(heap_foot) );\r
 315         if( foot->magic != MAGIC )      return 0;\r
 316         #endif\r
 317         return 1;\r
 318 }\r
 319 \r
 320 // === STATIC FUNCTIONS ===\r
 321 /**\r
 322  * Does the job of brk(0)\r
 323  */\r
 324 static void *FindHeapBase()\r
 325 {\r
 326         #if 0\r
 327         #define MAX             0xC0000000      // Address\r
 328         #define THRESHOLD       512     // Pages\r
 329         uint    addr;\r
 330         uint    stretch = 0;\r
 331         uint64_t        tmp;\r
 332         \r
 333         // Scan address space\r
 334         for(addr = 0;\r
 335                 addr < MAX;\r
 336                 addr += 0x1000\r
 337                 )\r
 338         {\r
 339                 tmp = _SysGetPhys(addr);\r
 340                 if( tmp != 0 ) {\r
 341                         stretch = 0;\r
 342                 } else {\r
 343                         stretch ++;\r
 344                         if(stretch > THRESHOLD)\r
 345                         {\r
 346                                 return (void*)( addr - stretch*0x1000 );\r
 347                         }\r
 348                 }\r
 349                 //__asm__ __volatile__ (\r
 350                 //      "push %%ebx;mov %%edx,%%ebx;int $0xAC;pop %%ebx"\r
 351                 //      ::"a"(256),"d"("%x"),"c"(addr));\r
 352         }\r
 353         \r
 354         return NULL;\r
 355         #else\r
 356         return (void*)0x00900000;\r
 357         #endif\r
 358 }\r
 359 \r
 360 LOCAL uint brk(Uint newpos)\r
 361 {\r
 362         static uint     curpos;\r
 363         uint    pages;\r
 364         uint    ret = curpos;\r
 365          int    delta;\r
 366         \r
 367         //_SysDebug("brk: (newpos=0x%x)", newpos);\r
 368         \r
 369         // Find initial position\r
 370         if(curpos == 0) curpos = (uint)FindHeapBase();\r
 371         \r
 372         // Get Current Position\r
 373         if(newpos == 0) return curpos;\r
 374         \r
 375         if(newpos < curpos)     return newpos;\r
 376         \r
 377         delta = newpos - curpos;\r
 378         //_SysDebug(" brk: delta = 0x%x", delta);\r
 379         \r
 380         // Do we need to add pages\r
 381         if(curpos & 0xFFF && (curpos & 0xFFF) + delta < 0x1000)\r
 382                 return curpos += delta;\r
 383         \r
 384         // Page align current position\r
 385         if(curpos & 0xFFF)      delta -= 0x1000 - (curpos & 0xFFF);\r
 386         curpos = (curpos + 0xFFF) & ~0xFFF;\r
 387         \r
 388         // Allocate Pages\r
 389         pages = (delta + 0xFFF) >> 12;\r
 390         while(pages--)\r
 391         {\r
 392                 _SysAllocate(curpos);\r
 393                 curpos += 0x1000;\r
 394                 delta -= 0x1000;\r
 395         }\r
 396         \r
 397         // Bring the current position to exactly what we want\r
 398         curpos -= ((delta + 0xFFF) & ~0xFFF) - delta;\r
 399         \r
 400         return ret;     // Return old curpos\r
 401 }\r