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