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         //if(glHeap)
 141         //      Debug("glHeap = %i", glHeap);
 142         // Lock Heap
 143         LOCK(&glHeap);
 144
 145         // Traverse Heap
 146         for( head = gHeapStart;
 147                 (Uint)head < (Uint)gHeapEnd;
 148                 head = (void*)((Uint)head + head->Size)
 149                 )
 150         {
 151                 // Alignment Check
 152                 if( head->Size & (BLOCK_SIZE-1) ) {
 153                         RELEASE(&glHeap);       // Release spinlock
 154                         #if WARNINGS
 155                         Log_Warning("Heap", "Size of heap address %p is invalid not aligned (0x%x)", head, head->Size);
 156                         Heap_Dump();
 157                         #endif
 158                         return NULL;
 159                 }
 160
 161                 // Check if allocated
 162                 if(head->Magic == MAGIC_USED)   continue;
 163                 // Error check
 164                 if(head->Magic != MAGIC_FREE)   {
 165                         RELEASE(&glHeap);       // Release spinlock
 166                         #if WARNINGS
 167                         Log_Warning("Heap", "Magic of heap address %p is invalid (0x%x)", head, head->Magic);
 168                         Heap_Dump();
 169                         #endif
 170                         return NULL;
 171                 }
 172
 173                 // Size check
 174                 if(head->Size < Bytes)  continue;
 175
 176                 // Perfect fit
 177                 if(head->Size == Bytes) {
 178                         head->Magic = MAGIC_USED;
 179                         RELEASE(&glHeap);       // Release spinlock
 180                         #if DEBUG_TRACE
 181                         Log("[Heap   ] Malloc'd %p (%i bytes), returning to %p", head->Data, head->Size,  __builtin_return_address(0));
 182                         #endif
 183                         return head->Data;
 184                 }
 185
 186                 // Break out of loop
 187                 #if FIRST_FIT
 188                 best = head;
 189                 bestSize = head->Size;
 190                 break;
 191                 #else
 192                 // or check if the block is the best size
 193                 if(bestSize > head->Size) {
 194                         best = head;
 195                         bestSize = head->Size;
 196                 }
 197                 #endif
 198         }
 199
 200         // If no block large enough is found, create one
 201         if(!best)
 202         {
 203                 best = Heap_Extend( Bytes );
 204                 // Check for errors
 205                 if(!best) {
 206                         RELEASE(&glHeap);       // Release spinlock
 207                         return NULL;
 208                 }
 209                 // Check size
 210                 if(best->Size == Bytes) {
 211                         best->Magic = MAGIC_USED;       // Mark block as used
 212                         RELEASE(&glHeap);       // Release spinlock
 213                         #if DEBUG_TRACE
 214                         Log("[Heap   ] Malloc'd %p (%i bytes), returning to %p", best->Data, best->Size, __builtin_return_address(0));
 215                         #endif
 216                         return best->Data;
 217                 }
 218         }
 219
 220         // Split Block
 221         newhead = (void*)( (Uint)best + Bytes );
 222         newfoot = (void*)( (Uint)best + Bytes - sizeof(tHeapFoot) );
 223         foot = (void*)( (Uint)best + best->Size - sizeof(tHeapFoot) );
 224
 225         newfoot->Head = best;   // Create new footer
 226         newfoot->Magic = MAGIC_FOOT;
 227         newhead->Size = best->Size - Bytes;     // Create new header
 228         newhead->Magic = MAGIC_FREE;
 229         foot->Head = newhead;   // Update backlink in old footer
 230         best->Size = Bytes;             // Update size in old header
 231         best->Magic = MAGIC_USED;       // Mark block as used
 232
 233         RELEASE(&glHeap);       // Release spinlock
 234         #if DEBUG_TRACE
 235         Log("[Heap   ] Malloc'd %p (%i bytes), returning to %p", best->Data, best->Size, __builtin_return_address(0));
 236         #endif
 237         return best->Data;
 238 }
 239
 240 /**
 241  * \fn void free(void *Ptr)
 242  * \brief Free an allocated memory block
 243  */
 244 void free(void *Ptr)
 245 {
 246         tHeapHead       *head;
 247         tHeapFoot       *foot;
 248
 249         #if DEBUG_TRACE
 250         Log_Log("Heap", "free: Ptr = %p", Ptr);
 251         Log_Log("Heap", "free: Returns to %p", __builtin_return_address(0));
 252         #endif
 253
 254         // Alignment Check
 255         if( (Uint)Ptr & (sizeof(Uint)-1) ) {
 256                 Log_Warning("Heap", "free - Passed a non-aligned address (%p)", Ptr);
 257                 return;
 258         }
 259
 260         // Sanity check
 261         if((Uint)Ptr < (Uint)gHeapStart || (Uint)Ptr > (Uint)gHeapEnd)
 262         {
 263                 Log_Warning("Heap", "free - Passed a non-heap address (%p < %p < %p)\n",
 264                         gHeapStart, Ptr, gHeapEnd);
 265                 return;
 266         }
 267
 268         // Check memory block - Header
 269         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 270         if(head->Magic == MAGIC_FREE) {
 271                 Log_Warning("Heap", "free - Passed a freed block (%p) by %p", head, __builtin_return_address(0));
 272                 return;
 273         }
 274         if(head->Magic != MAGIC_USED) {
 275                 Log_Warning("Heap", "free - Magic value is invalid (%p, 0x%x)\n", head, head->Magic);
 276                 return;
 277         }
 278
 279         // Check memory block - Footer
 280         foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 281         if(foot->Head != head) {
 282                 Log_Warning("Heap", "free - Footer backlink is incorrect (%p, 0x%x)\n", head, foot->Head);
 283                 return;
 284         }
 285         if(foot->Magic != MAGIC_FOOT) {
 286                 Log_Warning("Heap", "free - Footer magic is invalid (%p, %p = 0x%x)\n", head, &foot->Magic, foot->Magic);
 287                 return;
 288         }
 289
 290         // Lock
 291         LOCK( &glHeap );
 292
 293         // Mark as free
 294         head->Magic = MAGIC_FREE;
 295         // Merge blocks
 296         Heap_Merge( head );
 297
 298         // Release
 299         RELEASE( &glHeap );
 300 }
 301
 302 /**
 303  */
 304 void *realloc(void *__ptr, size_t __size)
 305 {
 306         tHeapHead       *head = (void*)( (Uint)__ptr-8 );
 307         tHeapHead       *nextHead;
 308         tHeapFoot       *foot;
 309         Uint    newSize = (__size + sizeof(tHeapFoot)+sizeof(tHeapHead)+BLOCK_SIZE-1)&~(BLOCK_SIZE-1);
 310
 311         // Check for reallocating NULL
 312         if(__ptr == NULL)       return malloc(__size);
 313
 314         // Check if resize is needed
 315         if(newSize <= head->Size)       return __ptr;
 316
 317         // Check if next block is free
 318         nextHead = (void*)( (Uint)head + head->Size );
 319
 320         // Extend into next block
 321         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 322         {
 323                 Uint    size = nextHead->Size + head->Size;
 324                 foot = (void*)( (Uint)nextHead + nextHead->Size - sizeof(tHeapFoot) );
 325                 // Exact Fit
 326                 if(size == newSize) {
 327                         head->Size = newSize;
 328                         foot->Head = head;
 329                         nextHead->Magic = 0;
 330                         nextHead->Size = 0;
 331                         return __ptr;
 332                 }
 333                 // Create a new heap block
 334                 nextHead = (void*)( (Uint)head + newSize );
 335                 nextHead->Size = size - newSize;
 336                 nextHead->Magic = MAGIC_FREE;
 337                 foot->Head = nextHead;  // Edit 2nd footer
 338                 head->Size = newSize;   // Edit first header
 339                 // Create new footer
 340                 foot = (void*)( (Uint)head + newSize - sizeof(tHeapFoot) );
 341                 foot->Head = head;
 342                 foot->Magic = MAGIC_FOOT;
 343                 return __ptr;
 344         }
 345
 346         // Extend downwards?
 347         foot = (void*)( (Uint)head - sizeof(tHeapFoot) );
 348         nextHead = foot->Head;
 349         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 350         {
 351                 Uint    size = nextHead->Size + head->Size;
 352                 // Inexact fit, split things up
 353                 if(size > newSize)
 354                 {
 355                         // TODO
 356                         Warning("[Heap   ] TODO: Space efficient realloc when new size is smaller");
 357                 }
 358
 359                 // Exact fit
 360                 if(size >= newSize)
 361                 {
 362                         Uint    oldDataSize;
 363                         // Set 1st (new/lower) header
 364                         nextHead->Magic = MAGIC_USED;
 365                         nextHead->Size = newSize;
 366                         // Get 2nd (old) footer
 367                         foot = (void*)( (Uint)nextHead + newSize );
 368                         foot->Head = nextHead;
 369                         // Save old data size
 370                         oldDataSize = head->Size - sizeof(tHeapFoot) - sizeof(tHeapHead);
 371                         // Clear old header
 372                         head->Size = 0;
 373                         head->Magic = 0;
 374                         // Copy data
 375                         memcpy(nextHead->Data, __ptr, oldDataSize);
 376                         // Return
 377                         return nextHead->Data;
 378                 }
 379                 // On to the expensive then
 380         }
 381
 382         // Well, darn
 383         nextHead = malloc( __size );
 384         nextHead -= 1;
 385
 386         memcpy(
 387                 nextHead->Data,
 388                 __ptr,
 389                 head->Size - sizeof(tHeapFoot) - sizeof(tHeapHead)
 390                 );
 391
 392         free(__ptr);
 393
 394         return nextHead->Data;
 395 }
 396
 397 /**
 398  * \fn void *calloc(size_t num, size_t size)
 399  * \brief Allocate and Zero a buffer in memory
 400  * \param num   Number of elements
 401  * \param size  Size of each element
 402  */
 403 void *calloc(size_t num, size_t size)
 404 {
 405         void    *ret = malloc(num*size);
 406         if(ret == NULL) return NULL;
 407
 408         memset( ret, 0, num*size );
 409
 410         return ret;
 411 }
 412
 413 /**
 414  * \fn int IsHeap(void *Ptr)
 415  * \brief Checks if an address is a heap pointer
 416  */
 417 int IsHeap(void *Ptr)
 418 {
 419         tHeapHead       *head;
 420         if((Uint)Ptr < (Uint)gHeapStart)        return 0;
 421         if((Uint)Ptr > (Uint)gHeapEnd)  return 0;
 422         if((Uint)Ptr & (sizeof(Uint)-1))        return 0;
 423
 424         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 425         if(head->Magic != MAGIC_USED && head->Magic != MAGIC_FREE)
 426                 return 0;
 427
 428         return 1;
 429 }
 430
 431 #if WARNINGS
 432 void Heap_Dump(void)
 433 {
 434         tHeapHead       *head;
 435         tHeapFoot       *foot;
 436
 437         head = gHeapStart;
 438         while( (Uint)head < (Uint)gHeapEnd )
 439         {
 440                 foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 441                 Log_Log("Heap", "%p (0x%x): 0x%08lx 0x%lx",
 442                         head, MM_GetPhysAddr((Uint)head), head->Size, head->Magic);
 443                 Log_Log("Heap", "%p 0x%lx", foot->Head, foot->Magic);
 444                 Log_Log("Heap", "");
 445
 446                 // Sanity Check Header
 447                 if(head->Size == 0) {
 448                         Log_Warning("Heap", "HALTED - Size is zero");
 449                         break;
 450                 }
 451                 if(head->Size & (BLOCK_SIZE-1)) {
 452                         Log_Warning("Heap", "HALTED - Size is malaligned");
 453                         break;
 454                 }
 455                 if(head->Magic != MAGIC_FREE && head->Magic != MAGIC_USED) {
 456                         Log_Warning("Heap", "HALTED - Head Magic is Bad");
 457                         break;
 458                 }
 459
 460                 // Check footer
 461                 if(foot->Magic != MAGIC_FOOT) {
 462                         Log_Warning("Heap", "HALTED - Foot Magic is Bad");
 463                         break;
 464                 }
 465                 if(head != foot->Head) {
 466                         Log_Warning("Heap", "HALTED - Footer backlink is invalid");
 467                         break;
 468                 }
 469
 470                 // All OK? Go to next
 471                 head = foot->NextHead;
 472         }
 473 }
 474 #endif
 475
 476 #if 1
 477 void Heap_Stats(void)
 478 {
 479         tHeapHead       *head;
 480          int    nBlocks = 0;
 481          int    nFree = 0;
 482          int    totalBytes = 0;
 483          int    freeBytes = 0;
 484          int    maxAlloc=0, minAlloc=-1;
 485          int    avgAlloc, frag, overhead;
 486
 487         for(head = gHeapStart;
 488                 (Uint)head < (Uint)gHeapEnd;
 489                 head = (void*)( (Uint)head + head->Size )
 490                 )
 491         {
 492                 nBlocks ++;
 493                 totalBytes += head->Size;
 494                 if( head->Magic == MAGIC_FREE )
 495                 {
 496                         nFree ++;
 497                         freeBytes += head->Size;
 498                 }
 499                 else {
 500                         if(maxAlloc < head->Size)       maxAlloc = head->Size;
 501                         if(minAlloc == -1 || minAlloc > head->Size)
 502                                 minAlloc = head->Size;
 503                 }
 504         }
 505
 506         Log_Log("Heap", "%i blocks (0x%x bytes)", nBlocks, totalBytes);
 507         Log_Log("Heap", "%i free blocks (0x%x bytes)", nFree, freeBytes);
 508         frag = (nFree-1)*10000/nBlocks;
 509         Log_Log("Heap", "%i.%02i%% Heap Fragmentation", frag/100, frag%100);
 510         avgAlloc = (totalBytes-freeBytes)/(nBlocks-nFree);
 511         overhead = (sizeof(tHeapFoot)+sizeof(tHeapHead))*10000/avgAlloc;
 512         Log_Log("Heap", "Average allocation: %i bytes, Average Overhead: %i.%02i%%",
 513                 avgAlloc, overhead/100, overhead%100
 514                 );
 515         Log_Log("Heap", "Smallest Block: %i bytes, Largest: %i bytes",
 516                 minAlloc, maxAlloc);
 517
 518         // Scan and get distribution
 519         #if 1
 520         {
 521                 struct {
 522                         Uint    Size;
 523                         Uint    Count;
 524                 }       sizeCounts[nBlocks];
 525                  int    i;
 526
 527                 memset(sizeCounts, 0, nBlocks*sizeof(sizeCounts[0]));
 528
 529                 for(head = gHeapStart;
 530                         (Uint)head < (Uint)gHeapEnd;
 531                         head = (void*)( (Uint)head + head->Size )
 532                         )
 533                 {
 534                         for( i = 0; i < nBlocks; i ++ ) {
 535                                 if( sizeCounts[i].Size == 0 )
 536                                         break;
 537                                 if( sizeCounts[i].Size == head->Size )
 538                                         break;
 539                         }
 540                         // Should never reach this part (in a non-concurrent case)
 541                         if( i == nBlocks )      continue;
 542                         sizeCounts[i].Size = head->Size;
 543                         sizeCounts[i].Count ++;
 544                         #if 1
 545                         //Log("Heap_Stats: %i %p - 0x%x bytes (%s) (%i)", nBlocks, head,
 546                         //      head->Size, (head->Magic==MAGIC_FREE?"FREE":"used"), i
 547                         //      );
 548                         //Log("Heap_Stats: sizeCounts[%i] = {Size:0x%x, Count: %i}", i,
 549                         //      sizeCounts[i].Size, sizeCounts[i].Count);
 550                         #endif
 551                 }
 552
 553                 for( i = 0; i < nBlocks && sizeCounts[i].Count; i ++ )
 554                 {
 555                         Log("Heap_Stats: 0x%x - %i blocks",
 556                                 sizeCounts[i].Size, sizeCounts[i].Count
 557                                 );
 558                 }
 559         }
 560         #endif
 561 }
 562 #endif
 563
 564 // === EXPORTS ===
 565 EXPORT(malloc);
 566 EXPORT(realloc);
 567 EXPORT(free);