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