Kernel/heap.c

   1 /*
   2  * AcessOS Microkernel Version
   3  * heap.c
   4  */
   5 #include <acess.h>
   6 #include <mm_virt.h>
   7 #include <heap.h>
   8
   9 #define WARNINGS        1
  10 #define DEBUG_TRACE     0
  11
  12 // === CONSTANTS ===
  13 #define HEAP_INIT_SIZE  0x8000  // 32 KiB
  14 #define BLOCK_SIZE      (sizeof(void*))*8       // 8 Machine Words
  15 #define COMPACT_HEAP    0       // Use 4 byte header?
  16 #define FIRST_FIT       0
  17
  18 #define MAGIC_FOOT      0x2ACE5505
  19 #define MAGIC_FREE      0xACE55000
  20 #define MAGIC_USED      0x862B0505      // MAGIC_FOOT ^ MAGIC_FREE
  21
  22 // === PROTOTYPES ===
  23 void    Heap_Install(void);
  24 void    *Heap_Extend(int Bytes);
  25 void    *Heap_Merge(tHeapHead *Head);
  26 void    *malloc(size_t Bytes);
  27 void    free(void *Ptr);
  28 void    Heap_Dump(void);
  29 void    Heap_Stats(void);
  30
  31 // === GLOBALS ===
  32 tSpinlock       glHeap;
  33 void    *gHeapStart;
  34 void    *gHeapEnd;
  35
  36 // === CODE ===
  37 void Heap_Install(void)
  38 {
  39         gHeapStart      = (void*)MM_KHEAP_BASE;
  40         gHeapEnd        = (void*)MM_KHEAP_BASE;
  41         Heap_Extend(HEAP_INIT_SIZE);
  42 }
  43
  44 /**
  45  * \fn void *Heap_Extend(int Bytes)
  46  * \brief Extend the size of the heap
  47  */
  48 void *Heap_Extend(int Bytes)
  49 {
  50         Uint    i;
  51         tHeapHead       *head = gHeapEnd;
  52         tHeapFoot       *foot;
  53
  54         // Bounds Check
  55         if( (tVAddr)gHeapEnd == MM_KHEAP_MAX )
  56                 return NULL;
  57
  58         // Bounds Check
  59         if( (tVAddr)gHeapEnd + ((Bytes+0xFFF)&~0xFFF) > MM_KHEAP_MAX ) {
  60                 Bytes = MM_KHEAP_MAX - (tVAddr)gHeapEnd;
  61                 return NULL;
  62         }
  63
  64         // Heap expands in pages
  65         for(i=0;i<(Bytes+0xFFF)>>12;i++)
  66                 MM_Allocate( (tVAddr)gHeapEnd+(i<<12) );
  67
  68         // Increas heap end
  69         gHeapEnd += i << 12;
  70
  71         // Create Block
  72         head->Size = (Bytes+0xFFF)&~0xFFF;
  73         head->Magic = MAGIC_FREE;
  74         foot = (void*)( (Uint)gHeapEnd - sizeof(tHeapFoot) );
  75         foot->Head = head;
  76         foot->Magic = MAGIC_FOOT;
  77
  78         return Heap_Merge(head);        // Merge with previous block
  79 }
  80
  81 /**
  82  * \fn void *Heap_Merge(tHeapHead *Head)
  83  * \brief Merges two ajacent heap blocks
  84  */
  85 void *Heap_Merge(tHeapHead *Head)
  86 {
  87         tHeapFoot       *foot;
  88         tHeapFoot       *thisFoot;
  89         tHeapHead       *head;
  90
  91         //Log("Heap_Merge: (Head=%p)", Head);
  92
  93         thisFoot = (void*)( (Uint)Head + Head->Size - sizeof(tHeapFoot) );
  94         if((Uint)thisFoot > (Uint)gHeapEnd)     return NULL;
  95
  96         // Merge Left (Down)
  97         foot = (void*)( (Uint)Head - sizeof(tHeapFoot) );
  98         if( ((Uint)foot < (Uint)gHeapEnd && (Uint)foot > (Uint)gHeapStart)
  99         && foot->Head->Magic == MAGIC_FREE) {
 100                 foot->Head->Size += Head->Size; // Increase size
 101                 thisFoot->Head = foot->Head;    // Change backlink
 102                 Head->Magic = 0;        // Clear old head
 103                 Head->Size = 0;
 104                 Head = foot->Head;      // Save new head address
 105                 foot->Head = NULL;      // Clear central footer
 106                 foot->Magic = 0;
 107         }
 108
 109         // Merge Right (Upwards)
 110         head = (void*)( (Uint)Head + Head->Size );
 111         if((Uint)head < (Uint)gHeapEnd && head->Magic == MAGIC_FREE)
 112         {
 113                 Head->Size += head->Size;
 114                 foot = (void*)( (Uint)Head + Head->Size - sizeof(tHeapFoot) );
 115                 foot->Head = Head;      // Update Backlink
 116                 thisFoot->Head = NULL;  // Clear old footer
 117                 thisFoot->Magic = 0;
 118                 head->Size = 0;         // Clear old header
 119                 head->Magic = 0;
 120         }
 121
 122         // Return new address
 123         return Head;
 124 }
 125
 126 /**
 127  * \fn void *malloc(size_t Bytes)
 128  * \brief Allocate memory from the heap
 129  */
 130 void *malloc(size_t Bytes)
 131 {
 132         tHeapHead       *head, *newhead;
 133         tHeapFoot       *foot, *newfoot;
 134         tHeapHead       *best = NULL;
 135         Uint    bestSize = 0;   // Speed hack
 136
 137         // Get required size
 138         Bytes = (Bytes + sizeof(tHeapHead) + sizeof(tHeapFoot) + BLOCK_SIZE-1) & ~(BLOCK_SIZE-1);
 139
 140         // Lock Heap
 141         LOCK(&glHeap);
 142
 143         // Traverse Heap
 144         for( head = gHeapStart;
 145                 (Uint)head < (Uint)gHeapEnd;
 146                 head = (void*)((Uint)head + head->Size)
 147                 )
 148         {
 149                 // Alignment Check
 150                 if( head->Size & (BLOCK_SIZE-1) ) {
 151                         RELEASE(&glHeap);       // Release spinlock
 152                         #if WARNINGS
 153                         Log_Warning("Heap", "Size of heap address %p is invalid not aligned (0x%x)", head, head->Size);
 154                         Heap_Dump();
 155                         #endif
 156                         return NULL;
 157                 }
 158
 159                 // Check if allocated
 160                 if(head->Magic == MAGIC_USED)   continue;
 161                 // Error check
 162                 if(head->Magic != MAGIC_FREE)   {
 163                         RELEASE(&glHeap);       // Release spinlock
 164                         #if WARNINGS
 165                         Log_Warning("Heap", "Magic of heap address %p is invalid (0x%x)", head, head->Magic);
 166                         Heap_Dump();
 167                         #endif
 168                         return NULL;
 169                 }
 170
 171                 // Size check
 172                 if(head->Size < Bytes)  continue;
 173
 174                 // Perfect fit
 175                 if(head->Size == Bytes) {
 176                         head->Magic = MAGIC_USED;
 177                         RELEASE(&glHeap);       // Release spinlock
 178                         #if DEBUG_TRACE
 179                         Log("[Heap   ] Malloc'd %p (%i bytes), returning to %p", head->Data, head->Size,  __builtin_return_address(0));
 180                         #endif
 181                         return head->Data;
 182                 }
 183
 184                 // Break out of loop
 185                 #if FIRST_FIT
 186                 best = head;
 187                 bestSize = head->Size;
 188                 break;
 189                 #else
 190                 // or check if the block is the best size
 191                 if(bestSize > head->Size) {
 192                         best = head;
 193                         bestSize = head->Size;
 194                 }
 195                 #endif
 196         }
 197
 198         // If no block large enough is found, create one
 199         if(!best)
 200         {
 201                 best = Heap_Extend( Bytes );
 202                 // Check for errors
 203                 if(!best) {
 204                         RELEASE(&glHeap);       // Release spinlock
 205                         return NULL;
 206                 }
 207                 // Check size
 208                 if(best->Size == Bytes) {
 209                         best->Magic = MAGIC_USED;       // Mark block as used
 210                         RELEASE(&glHeap);       // Release spinlock
 211                         #if DEBUG_TRACE
 212                         Log("[Heap   ] Malloc'd %p (%i bytes), returning to %p", best->Data, best->Size, __builtin_return_address(0));
 213                         #endif
 214                         return best->Data;
 215                 }
 216         }
 217
 218         // Split Block
 219         newhead = (void*)( (Uint)best + Bytes );
 220         newfoot = (void*)( (Uint)best + Bytes - sizeof(tHeapFoot) );
 221         foot = (void*)( (Uint)best + best->Size - sizeof(tHeapFoot) );
 222
 223         newfoot->Head = best;   // Create new footer
 224         newfoot->Magic = MAGIC_FOOT;
 225         newhead->Size = best->Size - Bytes;     // Create new header
 226         newhead->Magic = MAGIC_FREE;
 227         foot->Head = newhead;   // Update backlink in old footer
 228         best->Size = Bytes;             // Update size in old header
 229         best->Magic = MAGIC_USED;       // Mark block as used
 230
 231         RELEASE(&glHeap);       // Release spinlock
 232         #if DEBUG_TRACE
 233         Log("[Heap   ] Malloc'd %p (%i bytes), returning to %p", best->Data, best->Size, __builtin_return_address(0));
 234         #endif
 235         return best->Data;
 236 }
 237
 238 /**
 239  * \fn void free(void *Ptr)
 240  * \brief Free an allocated memory block
 241  */
 242 void free(void *Ptr)
 243 {
 244         tHeapHead       *head;
 245         tHeapFoot       *foot;
 246
 247         #if DEBUG_TRACE
 248         Log_Log("Heap", "free: Ptr = %p", Ptr);
 249         Log_Log("Heap", "free: Returns to %p", __builtin_return_address(0));
 250         #endif
 251
 252         // Alignment Check
 253         if( (Uint)Ptr & (sizeof(Uint)-1) ) {
 254                 Log_Warning("Heap", "free - Passed a non-aligned address (%p)", Ptr);
 255                 return;
 256         }
 257
 258         // Sanity check
 259         if((Uint)Ptr < (Uint)gHeapStart || (Uint)Ptr > (Uint)gHeapEnd)
 260         {
 261                 Log_Warning("Heap", "free - Passed a non-heap address (%p < %p < %p)\n",
 262                         gHeapStart, Ptr, gHeapEnd);
 263                 return;
 264         }
 265
 266         // Check memory block - Header
 267         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 268         if(head->Magic == MAGIC_FREE) {
 269                 Log_Warning("Heap", "free - Passed a freed block (%p) by %p", head, __builtin_return_address(0));
 270                 return;
 271         }
 272         if(head->Magic != MAGIC_USED) {
 273                 Log_Warning("Heap", "free - Magic value is invalid (%p, 0x%x)\n", head, head->Magic);
 274                 return;
 275         }
 276
 277         // Check memory block - Footer
 278         foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 279         if(foot->Head != head) {
 280                 Log_Warning("Heap", "free - Footer backlink is incorrect (%p, 0x%x)\n", head, foot->Head);
 281                 return;
 282         }
 283         if(foot->Magic != MAGIC_FOOT) {
 284                 Log_Warning("Heap", "free - Footer magic is invalid (%p, %p = 0x%x)\n", head, &foot->Magic, foot->Magic);
 285                 return;
 286         }
 287
 288         // Lock
 289         LOCK( &glHeap );
 290
 291         // Mark as free
 292         head->Magic = MAGIC_FREE;
 293         // Merge blocks
 294         Heap_Merge( head );
 295
 296         // Release
 297         RELEASE( &glHeap );
 298 }
 299
 300 /**
 301  */
 302 void *realloc(void *__ptr, size_t __size)
 303 {
 304         tHeapHead       *head = (void*)( (Uint)__ptr-8 );
 305         tHeapHead       *nextHead;
 306         tHeapFoot       *foot;
 307         Uint    newSize = (__size + sizeof(tHeapFoot)+sizeof(tHeapHead)+BLOCK_SIZE-1)&~(BLOCK_SIZE-1);
 308
 309         // Check for reallocating NULL
 310         if(__ptr == NULL)       return malloc(__size);
 311
 312         // Check if resize is needed
 313         if(newSize <= head->Size)       return __ptr;
 314
 315         // Check if next block is free
 316         nextHead = (void*)( (Uint)head + head->Size );
 317
 318         // Extend into next block
 319         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 320         {
 321                 Uint    size = nextHead->Size + head->Size;
 322                 foot = (void*)( (Uint)nextHead + nextHead->Size - sizeof(tHeapFoot) );
 323                 // Exact Fit
 324                 if(size == newSize) {
 325                         head->Size = newSize;
 326                         foot->Head = head;
 327                         nextHead->Magic = 0;
 328                         nextHead->Size = 0;
 329                         return __ptr;
 330                 }
 331                 // Create a new heap block
 332                 nextHead = (void*)( (Uint)head + newSize );
 333                 nextHead->Size = size - newSize;
 334                 nextHead->Magic = MAGIC_FREE;
 335                 foot->Head = nextHead;  // Edit 2nd footer
 336                 head->Size = newSize;   // Edit first header
 337                 // Create new footer
 338                 foot = (void*)( (Uint)head + newSize - sizeof(tHeapFoot) );
 339                 foot->Head = head;
 340                 foot->Magic = MAGIC_FOOT;
 341                 return __ptr;
 342         }
 343
 344         // Extend downwards?
 345         foot = (void*)( (Uint)head - sizeof(tHeapFoot) );
 346         nextHead = foot->Head;
 347         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 348         {
 349                 Uint    size = nextHead->Size + head->Size;
 350                 // Inexact fit, split things up
 351                 if(size > newSize)
 352                 {
 353                         // TODO
 354                         Warning("[Heap   ] TODO: Space efficient realloc when new size is smaller");
 355                 }
 356
 357                 // Exact fit
 358                 if(size >= newSize)
 359                 {
 360                         Uint    oldDataSize;
 361                         // Set 1st (new/lower) header
 362                         nextHead->Magic = MAGIC_USED;
 363                         nextHead->Size = newSize;
 364                         // Get 2nd (old) footer
 365                         foot = (void*)( (Uint)nextHead + newSize );
 366                         foot->Head = nextHead;
 367                         // Save old data size
 368                         oldDataSize = head->Size - sizeof(tHeapFoot) - sizeof(tHeapHead);
 369                         // Clear old header
 370                         head->Size = 0;
 371                         head->Magic = 0;
 372                         // Copy data
 373                         memcpy(nextHead->Data, __ptr, oldDataSize);
 374                         // Return
 375                         return nextHead->Data;
 376                 }
 377                 // On to the expensive then
 378         }
 379
 380         // Well, darn
 381         nextHead = malloc( __size );
 382         nextHead -= 1;
 383
 384         memcpy(
 385                 nextHead->Data,
 386                 __ptr,
 387                 head->Size - sizeof(tHeapFoot) - sizeof(tHeapHead)
 388                 );
 389
 390         free(__ptr);
 391
 392         return nextHead->Data;
 393 }
 394
 395 /**
 396  * \fn void *calloc(size_t num, size_t size)
 397  * \brief Allocate and Zero a buffer in memory
 398  * \param num   Number of elements
 399  * \param size  Size of each element
 400  */
 401 void *calloc(size_t num, size_t size)
 402 {
 403         void    *ret = malloc(num*size);
 404         if(ret == NULL) return NULL;
 405
 406         memset( ret, 0, num*size );
 407
 408         return ret;
 409 }
 410
 411 /**
 412  * \fn int IsHeap(void *Ptr)
 413  * \brief Checks if an address is a heap pointer
 414  */
 415 int IsHeap(void *Ptr)
 416 {
 417         tHeapHead       *head;
 418         if((Uint)Ptr < (Uint)gHeapStart)        return 0;
 419         if((Uint)Ptr > (Uint)gHeapEnd)  return 0;
 420         if((Uint)Ptr & (sizeof(Uint)-1))        return 0;
 421
 422         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 423         if(head->Magic != MAGIC_USED && head->Magic != MAGIC_FREE)
 424                 return 0;
 425
 426         return 1;
 427 }
 428
 429 #if WARNINGS
 430 void Heap_Dump(void)
 431 {
 432         tHeapHead       *head;
 433         tHeapFoot       *foot;
 434
 435         head = gHeapStart;
 436         while( (Uint)head < (Uint)gHeapEnd )
 437         {
 438                 foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 439                 Log_Log("Heap", "%p (0x%x): 0x%08lx 0x%lx",
 440                         head, MM_GetPhysAddr((Uint)head), head->Size, head->Magic);
 441                 Log_Log("Heap", "%p 0x%lx", foot->Head, foot->Magic);
 442                 Log_Log("Heap", "");
 443
 444                 // Sanity Check Header
 445                 if(head->Size == 0) {
 446                         Log_Warning("Heap", "HALTED - Size is zero");
 447                         break;
 448                 }
 449                 if(head->Size & (BLOCK_SIZE-1)) {
 450                         Log_Warning("Heap", "HALTED - Size is malaligned");
 451                         break;
 452                 }
 453                 if(head->Magic != MAGIC_FREE && head->Magic != MAGIC_USED) {
 454                         Log_Warning("Heap", "HALTED - Head Magic is Bad");
 455                         break;
 456                 }
 457
 458                 // Check footer
 459                 if(foot->Magic != MAGIC_FOOT) {
 460                         Log_Warning("Heap", "HALTED - Foot Magic is Bad");
 461                         break;
 462                 }
 463                 if(head != foot->Head) {
 464                         Log_Warning("Heap", "HALTED - Footer backlink is invalid");
 465                         break;
 466                 }
 467
 468                 // All OK? Go to next
 469                 head = foot->NextHead;
 470         }
 471 }
 472 #endif
 473
 474 #if 1
 475 void Heap_Stats(void)
 476 {
 477         tHeapHead       *head;
 478          int    nBlocks = 0;
 479          int    nFree = 0;
 480          int    totalBytes = 0;
 481          int    freeBytes = 0;
 482          int    maxAlloc=0, minAlloc=-1;
 483          int    avgAlloc, frag, overhead;
 484
 485         for(head = gHeapStart;
 486                 (Uint)head < (Uint)gHeapEnd;
 487                 head = (void*)( (Uint)head + head->Size )
 488                 )
 489         {
 490                 nBlocks ++;
 491                 totalBytes += head->Size;
 492                 if( head->Magic == MAGIC_FREE )
 493                 {
 494                         nFree ++;
 495                         freeBytes += head->Size;
 496                 }
 497                 else {
 498                         if(maxAlloc < head->Size)       maxAlloc = head->Size;
 499                         if(minAlloc == -1 || minAlloc > head->Size)
 500                                 minAlloc = head->Size;
 501                 }
 502         }
 503
 504         Log_Log("Heap", "%i blocks (0x%x bytes)", nBlocks, totalBytes);
 505         Log_Log("Heap", "%i free blocks (0x%x bytes)", nFree, freeBytes);
 506         frag = (nFree-1)*10000/nBlocks;
 507         Log_Log("Heap", "%i.%02i%% Heap Fragmentation", frag/100, frag%100);
 508         avgAlloc = (totalBytes-freeBytes)/(nBlocks-nFree);
 509         overhead = (sizeof(tHeapFoot)+sizeof(tHeapHead))*10000/avgAlloc;
 510         Log_Log("Heap", "Average allocation: %i bytes, Average Overhead: %i.%02i%%",
 511                 avgAlloc, overhead/100, overhead%100
 512                 );
 513         Log_Log("Heap", "Smallest Block: %i bytes, Largest: %i bytes",
 514                 minAlloc, maxAlloc);
 515
 516         // Scan and get distribution
 517         #if 1
 518         {
 519                 struct {
 520                         Uint    Size;
 521                         Uint    Count;
 522                 }       sizeCounts[nBlocks];
 523                  int    i;
 524
 525                 memset(sizeCounts, 0, nBlocks*sizeof(sizeCounts[0]));
 526
 527                 for(head = gHeapStart;
 528                         (Uint)head < (Uint)gHeapEnd;
 529                         head = (void*)( (Uint)head + head->Size )
 530                         )
 531                 {
 532                         for( i = 0; i < nBlocks; i ++ ) {
 533                                 if( sizeCounts[i].Size == 0 )
 534                                         break;
 535                                 if( sizeCounts[i].Size == head->Size )
 536                                         break;
 537                         }
 538                         // Should never reach this part (in a non-concurrent case)
 539                         if( i == nBlocks )      continue;
 540                         sizeCounts[i].Size = head->Size;
 541                         sizeCounts[i].Count ++;
 542                         #if 1
 543                         //Log("Heap_Stats: %i %p - 0x%x bytes (%s) (%i)", nBlocks, head,
 544                         //      head->Size, (head->Magic==MAGIC_FREE?"FREE":"used"), i
 545                         //      );
 546                         //Log("Heap_Stats: sizeCounts[%i] = {Size:0x%x, Count: %i}", i,
 547                         //      sizeCounts[i].Size, sizeCounts[i].Count);
 548                         #endif
 549                 }
 550
 551                 for( i = 0; i < nBlocks && sizeCounts[i].Count; i ++ )
 552                 {
 553                         Log("Heap_Stats: 0x%x - %i blocks",
 554                                 sizeCounts[i].Size, sizeCounts[i].Count
 555                                 );
 556                 }
 557         }
 558         #endif
 559 }
 560 #endif
 561
 562 // === EXPORTS ===
 563 EXPORT(malloc);
 564 EXPORT(realloc);
 565 EXPORT(free);