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 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();
  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();
  29
  30 // === GLOBALS ===
  31 tSpinlock       glHeap;
  32 void    *gHeapStart;
  33 void    *gHeapEnd;
  34
  35 // === CODE ===
  36 void Heap_Install()
  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         // Lock Heap
 140         LOCK(&glHeap);
 141
 142         // Traverse Heap
 143         for( head = gHeapStart;
 144                 (Uint)head < (Uint)gHeapEnd;
 145                 head = (void*)((Uint)head + head->Size)
 146                 )
 147         {
 148                 // Alignment Check
 149                 if( head->Size & (BLOCK_SIZE-1) ) {
 150                         #if WARNINGS
 151                         Log_Warning("Heap", "Size of heap address %p is invalid not aligned (0x%x)", head, head->Size);
 152                         Heap_Dump();
 153                         #endif
 154                         RELEASE(&glHeap);
 155                         return NULL;
 156                 }
 157
 158                 // Check if allocated
 159                 if(head->Magic == MAGIC_USED)   continue;
 160                 // Error check
 161                 if(head->Magic != MAGIC_FREE)   {
 162                         #if WARNINGS
 163                         Log_Warning("Heap", "Magic of heap address %p is invalid (0x%x)", head, head->Magic);
 164                         Heap_Dump();
 165                         #endif
 166                         RELEASE(&glHeap);       // Release spinlock
 167                         return NULL;
 168                 }
 169
 170                 // Size check
 171                 if(head->Size < Bytes)  continue;
 172
 173                 // Perfect fit
 174                 if(head->Size == Bytes) {
 175                         head->Magic = MAGIC_USED;
 176                         RELEASE(&glHeap);       // Release spinlock
 177                         #if DEBUG_TRACE
 178                         Log("[Heap   ] Malloc'd %p (%i bytes), returning to %p", head->Data, head->Size,  __builtin_return_address(0));
 179                         #endif
 180                         return head->Data;
 181                 }
 182
 183                 // Break out of loop
 184                 #if FIRST_FIT
 185                 best = head;
 186                 bestSize = head->Size;
 187                 break;
 188                 #else
 189                 // or check if the block is the best size
 190                 if(bestSize > head->Size) {
 191                         best = head;
 192                         bestSize = head->Size;
 193                 }
 194                 #endif
 195         }
 196
 197         // If no block large enough is found, create one
 198         if(!best)
 199         {
 200                 best = Heap_Extend( Bytes );
 201                 // Check for errors
 202                 if(!best) {
 203                         RELEASE(&glHeap);       // Release spinlock
 204                         return NULL;
 205                 }
 206                 // Check size
 207                 if(best->Size == Bytes) {
 208                         RELEASE(&glHeap);       // Release spinlock
 209                         #if DEBUG_TRACE
 210                         Log("[Heap   ] Malloc'd %p (%i bytes), returning to %p", best->Data, best->Size, __builtin_return_address(0));
 211                         #endif
 212                         return best->Data;
 213                 }
 214         }
 215
 216         // Split Block
 217         newhead = (void*)( (Uint)best + Bytes );
 218         newfoot = (void*)( (Uint)best + Bytes - sizeof(tHeapFoot) );
 219         foot = (void*)( (Uint)best + best->Size - sizeof(tHeapFoot) );
 220
 221         newfoot->Head = best;   // Create new footer
 222         newfoot->Magic = MAGIC_FOOT;
 223         newhead->Size = best->Size - Bytes;     // Create new header
 224         newhead->Magic = MAGIC_FREE;
 225         foot->Head = newhead;   // Update backlink in old footer
 226         best->Size = Bytes;             // Update size in old header
 227         best->Magic = MAGIC_USED;       // Mark block as used
 228
 229         RELEASE(&glHeap);       // Release spinlock
 230         #if DEBUG_TRACE
 231         Log("[Heap   ] Malloc'd %p (%i bytes), returning to %p", best->Data, best->Size, __builtin_return_address(0));
 232         #endif
 233         return best->Data;
 234 }
 235
 236 /**
 237  * \fn void free(void *Ptr)
 238  * \brief Free an allocated memory block
 239  */
 240 void free(void *Ptr)
 241 {
 242         tHeapHead       *head;
 243         tHeapFoot       *foot;
 244
 245         #if DEBUG_TRACE
 246         Log_Log("Heap", "free: Ptr = %p", Ptr);
 247         Log_Log("Heap", "free: Returns to %p", __builtin_return_address(0));
 248         #endif
 249
 250         // Alignment Check
 251         if( (Uint)Ptr & (sizeof(Uint)-1) ) {
 252                 Log_Warning("Heap", "free - Passed a non-aligned address (%p)", Ptr);
 253                 return;
 254         }
 255
 256         // Sanity check
 257         if((Uint)Ptr < (Uint)gHeapStart || (Uint)Ptr > (Uint)gHeapEnd)
 258         {
 259                 Log_Warning("Heap", "free - Passed a non-heap address (%p < %p < %p)\n",
 260                         gHeapStart, Ptr, gHeapEnd);
 261                 return;
 262         }
 263
 264         // Check memory block - Header
 265         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 266         if(head->Magic == MAGIC_FREE) {
 267                 Log_Warning("Heap", "free - Passed a freed block (%p) by %p", head, __builtin_return_address(0));
 268                 return;
 269         }
 270         if(head->Magic != MAGIC_USED) {
 271                 Log_Warning("Heap", "free - Magic value is invalid (%p, 0x%x)\n", head, head->Magic);
 272                 return;
 273         }
 274
 275         // Check memory block - Footer
 276         foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 277         if(foot->Head != head) {
 278                 Log_Warning("Heap", "free - Footer backlink is incorrect (%p, 0x%x)\n", head, foot->Head);
 279                 return;
 280         }
 281         if(foot->Magic != MAGIC_FOOT) {
 282                 Log_Warning("Heap", "free - Footer magic is invalid (%p, %p = 0x%x)\n", head, &foot->Magic, foot->Magic);
 283                 return;
 284         }
 285
 286         // Lock
 287         LOCK( &glHeap );
 288
 289         // Mark as free
 290         head->Magic = MAGIC_FREE;
 291         // Merge blocks
 292         Heap_Merge( head );
 293
 294         // Release
 295         RELEASE( &glHeap );
 296 }
 297
 298 /**
 299  */
 300 void *realloc(void *__ptr, size_t __size)
 301 {
 302         tHeapHead       *head = (void*)( (Uint)__ptr-8 );
 303         tHeapHead       *nextHead;
 304         tHeapFoot       *foot;
 305         Uint    newSize = (__size + sizeof(tHeapFoot)+sizeof(tHeapHead)+BLOCK_SIZE-1)&~(BLOCK_SIZE-1);
 306
 307         // Check for reallocating NULL
 308         if(__ptr == NULL)       return malloc(__size);
 309
 310         // Check if resize is needed
 311         if(newSize <= head->Size)       return __ptr;
 312
 313         // Check if next block is free
 314         nextHead = (void*)( (Uint)head + head->Size );
 315
 316         // Extend into next block
 317         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 318         {
 319                 Uint    size = nextHead->Size + head->Size;
 320                 foot = (void*)( (Uint)nextHead + nextHead->Size - sizeof(tHeapFoot) );
 321                 // Exact Fit
 322                 if(size == newSize) {
 323                         head->Size = newSize;
 324                         foot->Head = head;
 325                         nextHead->Magic = 0;
 326                         nextHead->Size = 0;
 327                         return __ptr;
 328                 }
 329                 // Create a new heap block
 330                 nextHead = (void*)( (Uint)head + newSize );
 331                 nextHead->Size = size - newSize;
 332                 nextHead->Magic = MAGIC_FREE;
 333                 foot->Head = nextHead;  // Edit 2nd footer
 334                 head->Size = newSize;   // Edit first header
 335                 // Create new footer
 336                 foot = (void*)( (Uint)head + newSize - sizeof(tHeapFoot) );
 337                 foot->Head = head;
 338                 foot->Magic = MAGIC_FOOT;
 339                 return __ptr;
 340         }
 341
 342         // Extend downwards?
 343         foot = (void*)( (Uint)head - sizeof(tHeapFoot) );
 344         nextHead = foot->Head;
 345         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 346         {
 347                 Uint    size = nextHead->Size + head->Size;
 348                 // Exact fit
 349                 if(size == newSize)
 350                 {
 351                         Uint    oldDataSize;
 352                         // Set 1st (new/lower) header
 353                         nextHead->Magic = MAGIC_USED;
 354                         nextHead->Size = newSize;
 355                         // Get 2nd (old) footer
 356                         foot = (void*)( (Uint)nextHead + newSize );
 357                         foot->Head = nextHead;
 358                         // Save old data size
 359                         oldDataSize = head->Size - sizeof(tHeapFoot) - sizeof(tHeapHead);
 360                         // Clear old header
 361                         head->Size = 0;
 362                         head->Magic = 0;
 363                         memcpy(nextHead->Data, __ptr, oldDataSize);
 364                 }
 365         }
 366
 367         return NULL;
 368 }
 369
 370 /**
 371  * \fn void *calloc(size_t num, size_t size)
 372  * \brief Allocate and Zero a buffer in memory
 373  * \param num   Number of elements
 374  * \param size  Size of each element
 375  */
 376 void *calloc(size_t num, size_t size)
 377 {
 378         void    *ret = malloc(num*size);
 379         if(ret == NULL) return NULL;
 380
 381         memset( ret, 0, num*size );
 382
 383         return ret;
 384 }
 385
 386 /**
 387  * \fn int IsHeap(void *Ptr)
 388  * \brief Checks if an address is a heap pointer
 389  */
 390 int IsHeap(void *Ptr)
 391 {
 392         tHeapHead       *head;
 393         if((Uint)Ptr < (Uint)gHeapStart)        return 0;
 394         if((Uint)Ptr > (Uint)gHeapEnd)  return 0;
 395         if((Uint)Ptr & (sizeof(Uint)-1))        return 0;
 396
 397         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 398         if(head->Magic != MAGIC_USED && head->Magic != MAGIC_FREE)
 399                 return 0;
 400
 401         return 1;
 402 }
 403
 404 #if WARNINGS
 405 void Heap_Dump()
 406 {
 407         tHeapHead       *head;
 408         tHeapFoot       *foot;
 409
 410         head = gHeapStart;
 411         while( (Uint)head < (Uint)gHeapEnd )
 412         {
 413                 foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 414                 Log_Log("Heap", "%p (0x%x): 0x%08lx 0x%lx", head, MM_GetPhysAddr((Uint)head), head->Size, head->Magic);
 415                 Log_Log("Heap", "%p 0x%lx", foot->Head, foot->Magic);
 416                 Log_Log("Heap", "");
 417
 418                 // Sanity Check Header
 419                 if(head->Size == 0) {
 420                         Log_Warning("Heap", "HALTED - Size is zero");
 421                         break;
 422                 }
 423                 if(head->Size & (BLOCK_SIZE-1)) {
 424                         Log_Warning("Heap", "HALTED - Size is malaligned");
 425                         break;
 426                 }
 427                 if(head->Magic != MAGIC_FREE && head->Magic != MAGIC_USED) {
 428                         Log_Warning("Heap", "HALTED - Head Magic is Bad");
 429                         break;
 430                 }
 431
 432                 // Check footer
 433                 if(foot->Magic != MAGIC_FOOT) {
 434                         Log_Warning("Heap", "HALTED - Foot Magic is Bad");
 435                         break;
 436                 }
 437                 if(head != foot->Head) {
 438                         Log_Warning("Heap", "HALTED - Footer backlink is invalid");
 439                         break;
 440                 }
 441
 442                 // All OK? Go to next
 443                 head = foot->NextHead;
 444         }
 445 }
 446 #endif
 447
 448 // === EXPORTS ===
 449 EXPORT(malloc);
 450 EXPORT(realloc);
 451 EXPORT(free);