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_BASE       0xE0800000
  14 #define HEAP_MAX        0xF0000000      // 120MiB, Plenty
  15 #define HEAP_INIT_SIZE  0x8000  // 32 KiB
  16 #define BLOCK_SIZE      (sizeof(void*)) // 8 Machine Words
  17 #define COMPACT_HEAP    0       // Use 4 byte header?
  18 #define FIRST_FIT       0
  19
  20 #define MAGIC_FOOT      0x2ACE5505
  21 #define MAGIC_FREE      0xACE55000
  22 #define MAGIC_USED      0x862B0505      // MAGIC_FOOT ^ MAGIC_FREE
  23
  24 // === PROTOTYPES ===
  25 void    Heap_Install();
  26 void    *Heap_Extend(int Bytes);
  27 void    *Heap_Merge(tHeapHead *Head);
  28 void    *malloc(size_t Bytes);
  29 void    free(void *Ptr);
  30 void    Heap_Dump();
  31
  32 // === GLOBALS ===
  33  int    glHeap;
  34 void    *gHeapStart;
  35 void    *gHeapEnd;
  36
  37 // === CODE ===
  38 void Heap_Install()
  39 {
  40         gHeapStart      = (void*)MM_KHEAP_BASE;
  41         gHeapEnd        = (void*)MM_KHEAP_BASE;
  42         Heap_Extend(HEAP_INIT_SIZE);
  43 }
  44
  45 /**
  46  * \fn void *Heap_Extend(int Bytes)
  47  * \brief Extend the size of the heap
  48  */
  49 void *Heap_Extend(int Bytes)
  50 {
  51         Uint    i;
  52         tHeapHead       *head = gHeapEnd;
  53         tHeapFoot       *foot;
  54
  55         // Bounds Check
  56         if( (Uint)gHeapEnd == MM_KHEAP_MAX )
  57                 return NULL;
  58
  59         // Bounds Check
  60         if( (Uint)gHeapEnd + ((Bytes+0xFFF)&~0xFFF) > MM_KHEAP_MAX ) {
  61                 Bytes = MM_KHEAP_MAX - (Uint)gHeapEnd;
  62                 return NULL;
  63         }
  64
  65         // Heap expands in pages
  66         for(i=0;i<(Bytes+0xFFF)>>12;i++)
  67                 MM_Allocate( (Uint)gHeapEnd+(i<<12) );
  68
  69         // Increas heap end
  70         gHeapEnd += i << 12;
  71
  72         // Create Block
  73         head->Size = (Bytes+0xFFF)&~0xFFF;
  74         head->Magic = MAGIC_FREE;
  75         foot = (void*)( (Uint)gHeapEnd - sizeof(tHeapFoot) );
  76         foot->Head = head;
  77         foot->Magic = MAGIC_FOOT;
  78
  79         //Log(" Heap_Extend: head = %p", head);
  80         return Heap_Merge(head);        // Merge with previous block
  81 }
  82
  83 /**
  84  * \fn void *Heap_Merge(tHeapHead *Head)
  85  * \brief Merges two ajacent heap blocks
  86  */
  87 void *Heap_Merge(tHeapHead *Head)
  88 {
  89         tHeapFoot       *foot;
  90         tHeapFoot       *thisFoot;
  91         tHeapHead       *head;
  92
  93         //Log("Heap_Merge: (Head=%p)", Head);
  94
  95         thisFoot = (void*)( (Uint)Head + Head->Size - sizeof(tHeapFoot) );
  96         if((Uint)thisFoot > (Uint)gHeapEnd)     return NULL;
  97
  98         // Merge Left (Down)
  99         foot = (void*)( (Uint)Head - sizeof(tHeapFoot) );
 100         if( ((Uint)foot < (Uint)gHeapEnd && (Uint)foot > HEAP_BASE)
 101         && foot->Head->Magic == MAGIC_FREE) {
 102                 foot->Head->Size += Head->Size; // Increase size
 103                 thisFoot->Head = foot->Head;    // Change backlink
 104                 Head->Magic = 0;        // Clear old head
 105                 Head->Size = 0;
 106                 Head = foot->Head;      // Save new head address
 107                 foot->Head = NULL;      // Clear central footer
 108                 foot->Magic = 0;
 109         }
 110
 111         // Merge Right (Upwards)
 112         head = (void*)( (Uint)Head + Head->Size );
 113         if((Uint)head < (Uint)gHeapEnd && head->Magic == MAGIC_FREE)
 114         {
 115                 Head->Size += head->Size;
 116                 foot = (void*)( (Uint)Head + Head->Size - sizeof(tHeapFoot) );
 117                 foot->Head = Head;      // Update Backlink
 118                 thisFoot->Head = NULL;  // Clear old footer
 119                 thisFoot->Magic = 0;
 120                 head->Size = 0;         // Clear old header
 121                 head->Magic = 0;
 122         }
 123
 124         // Return new address
 125         return Head;
 126 }
 127
 128 /**
 129  * \fn void *malloc(size_t Bytes)
 130  * \brief Allocate memory from the heap
 131  */
 132 void *malloc(size_t Bytes)
 133 {
 134         tHeapHead       *head, *newhead;
 135         tHeapFoot       *foot, *newfoot;
 136         tHeapHead       *best = NULL;
 137         Uint    bestSize = 0;   // Speed hack
 138
 139         // Get required size
 140         Bytes = (Bytes + sizeof(tHeapHead) + sizeof(tHeapFoot) + BLOCK_SIZE-1) & ~(BLOCK_SIZE-1);
 141
 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                         #if WARNINGS
 154                         Warning("Size of heap address %p is invalid not aligned (0x%x)", head, head->Size);
 155                         Heap_Dump();
 156                         #endif
 157                         RELEASE(&glHeap);
 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                         #if WARNINGS
 166                         Warning("Magic of heap address %p is invalid (0x%x)", head, head->Magic);
 167                         Heap_Dump();
 168                         #endif
 169                         RELEASE(&glHeap);       // Release spinlock
 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("RETURN %p, to %p", best->Data, __builtin_return_address(0));
 182                         #endif
 183                         return best->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                         RELEASE(&glHeap);       // Release spinlock
 212                         #if DEBUG_TRACE
 213                         LOG("RETURN %p, to %p", best->Data, __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("RETURN %p, to %p", best->Data, __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("Ptr = %p", Ptr);
 250         LOG("Returns to %p", __builtin_return_address(0));
 251         #endif
 252
 253         // Alignment Check
 254         if( (Uint)Ptr & (sizeof(Uint)-1) ) {
 255                 Warning("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                 Warning("free - Passed a non-heap address (%p)\n", Ptr);
 263                 return;
 264         }
 265
 266         // Check memory block - Header
 267         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 268         if(head->Magic == MAGIC_FREE) {
 269                 Warning("free - Passed a freed block (%p) by %p", head, __builtin_return_address(0));
 270                 return;
 271         }
 272         if(head->Magic != MAGIC_USED) {
 273                 Warning("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                 Warning("free - Footer backlink is incorrect (%p, 0x%x)\n", head, foot->Head);
 281                 return;
 282         }
 283         if(foot->Magic != MAGIC_FOOT) {
 284                 Warning("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                 // Exact fit
 351                 if(size == newSize)
 352                 {
 353                         Uint    oldDataSize;
 354                         // Set 1st (new/lower) header
 355                         nextHead->Magic = MAGIC_USED;
 356                         nextHead->Size = newSize;
 357                         // Get 2nd (old) footer
 358                         foot = (void*)( (Uint)nextHead + newSize );
 359                         foot->Head = nextHead;
 360                         // Save old data size
 361                         oldDataSize = head->Size - sizeof(tHeapFoot) - sizeof(tHeapHead);
 362                         // Clear old header
 363                         head->Size = 0;
 364                         head->Magic = 0;
 365                         memcpy(nextHead->Data, __ptr, oldDataSize);
 366                 }
 367         }
 368
 369         return NULL;
 370 }
 371
 372 /**
 373  * \fn void *calloc(size_t num, size_t size)
 374  * \brief Allocate and Zero a buffer in memory
 375  * \param num   Number of elements
 376  * \param size  Size of each element
 377  */
 378 void *calloc(size_t num, size_t size)
 379 {
 380         void    *ret = malloc(num*size);
 381         if(ret == NULL) return NULL;
 382
 383         memset( ret, 0, num*size );
 384
 385         return ret;
 386 }
 387
 388 /**
 389  * \fn int IsHeap(void *Ptr)
 390  * \brief Checks if an address is a heap address
 391  */
 392 int IsHeap(void *Ptr)
 393 {
 394         tHeapHead       *head;
 395         if((Uint)Ptr < (Uint)gHeapStart)        return 0;
 396         if((Uint)Ptr > (Uint)gHeapEnd)  return 0;
 397
 398         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 399         if(head->Magic != MAGIC_USED && head->Magic != MAGIC_FREE)
 400                 return 0;
 401
 402         return 1;
 403 }
 404
 405 #if WARNINGS
 406 void Heap_Dump()
 407 {
 408         tHeapHead       *head;
 409         tHeapFoot       *foot;
 410
 411         head = gHeapStart;
 412         while( (Uint)head < (Uint)gHeapEnd )
 413         {
 414                 foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 415                 Log("%p (0x%x): 0x%08lx 0x%lx", head, MM_GetPhysAddr((Uint)head), head->Size, head->Magic);
 416                 Log("%p 0x%lx", foot->Head, foot->Magic);
 417                 Log("");
 418
 419                 // Sanity Check Header
 420                 if(head->Size == 0) {
 421                         Log("HALTED - Size is zero");
 422                         break;
 423                 }
 424                 if(head->Size & (BLOCK_SIZE-1)) {
 425                         Log("HALTED - Size is malaligned");
 426                         break;
 427                 }
 428                 if(head->Magic != MAGIC_FREE && head->Magic != MAGIC_USED) {
 429                         Log("HALTED - Head Magic is Bad");
 430                         break;
 431                 }
 432
 433                 // Check footer
 434                 if(foot->Magic != MAGIC_FOOT) {
 435                         Log("HALTED - Foot Magic is Bad");
 436                         break;
 437                 }
 438                 if(head != foot->Head) {
 439                         Log("HALTED - Footer backlink is invalid");
 440                         break;
 441                 }
 442
 443                 // All OK? Go to next
 444                 head = foot->NextHead;
 445         }
 446 }
 447 #endif
 448
 449 // === EXPORTS ===
 450 EXPORT(malloc);
 451 EXPORT(realloc);
 452 EXPORT(free);