Kernel/heap.c

   1 /*
   2  * AcessOS Microkernel Version
   3  * heap.c
   4  */
   5 #include <common.h>
   6 #include <mm_virt.h>
   7 #include <heap.h>
   8
   9 #define WARNINGS        1
  10
  11 // === CONSTANTS ===
  12 #define HEAP_BASE       0xE0800000
  13 #define HEAP_MAX        0xF0000000      // 120MiB, Plenty
  14 #define HEAP_INIT_SIZE  0x8000  // 32 KiB
  15 #define BLOCK_SIZE      (sizeof(void*)) // 8 Machine Words
  16 #define COMPACT_HEAP    0       // Use 4 byte header?
  17 #define FIRST_FIT       0
  18
  19 #define MAGIC_FOOT      0x2ACE5505
  20 #define MAGIC_FREE      0xACE55000
  21 #define MAGIC_USED      0x862B0505      // MAGIC_FOOT ^ MAGIC_FREE
  22
  23 // === PROTOTYPES ===
  24 void    Heap_Install();
  25 void    *Heap_Extend(int Bytes);
  26 void    *Heap_Merge(tHeapHead *Head);
  27 void    *malloc(size_t Bytes);
  28 void    free(void *Ptr);
  29 void    Heap_Dump();
  30
  31 // === GLOBALS ===
  32  int    giHeapSpinlock;
  33 void    *gHeapStart;
  34 void    *gHeapEnd;
  35
  36 // === CODE ===
  37 void Heap_Install()
  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( (Uint)gHeapEnd == MM_KHEAP_MAX )
  56                 return NULL;
  57
  58         // Bounds Check
  59         if( (Uint)gHeapEnd + ((Bytes+0xFFF)&~0xFFF) > MM_KHEAP_MAX ) {
  60                 Bytes = MM_KHEAP_MAX - (Uint)gHeapEnd;
  61                 return NULL;
  62         }
  63
  64         // Heap expands in pages
  65         for(i=0;i<(Bytes+0xFFF)>>12;i++)
  66                 MM_Allocate( (Uint)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         //Log(" Heap_Extend: head = %p", head);
  79         return Heap_Merge(head);        // Merge with previous block
  80 }
  81
  82 /**
  83  * \fn void *Heap_Merge(tHeapHead *Head)
  84  * \brief Merges two ajacent heap blocks
  85  */
  86 void *Heap_Merge(tHeapHead *Head)
  87 {
  88         tHeapFoot       *foot;
  89         tHeapFoot       *thisFoot;
  90         tHeapHead       *head;
  91
  92         //Log("Heap_Merge: (Head=%p)", Head);
  93
  94         thisFoot = (void*)( (Uint)Head + Head->Size - sizeof(tHeapFoot) );
  95         if((Uint)thisFoot > (Uint)gHeapEnd)     return NULL;
  96
  97         // Merge Left (Down)
  98         foot = (void*)( (Uint)Head - sizeof(tHeapFoot) );
  99         if( ((Uint)foot < (Uint)gHeapEnd && (Uint)foot > HEAP_BASE)
 100         && foot->Head->Magic == MAGIC_FREE) {
 101                 foot->Head->Size += Head->Size; // Increase size
 102                 thisFoot->Head = foot->Head;    // Change backlink
 103                 Head->Magic = 0;        // Clear old head
 104                 Head->Size = 0;
 105                 Head = foot->Head;      // Save new head address
 106                 foot->Head = NULL;      // Clear central footer
 107                 foot->Magic = 0;
 108         }
 109
 110         // Merge Right (Upwards)
 111         head = (void*)( (Uint)Head + Head->Size );
 112         if((Uint)head < (Uint)gHeapEnd && head->Magic == MAGIC_FREE)
 113         {
 114                 Head->Size += head->Size;
 115                 foot = (void*)( (Uint)Head + Head->Size - sizeof(tHeapFoot) );
 116                 foot->Head = Head;      // Update Backlink
 117                 thisFoot->Head = NULL;  // Clear old footer
 118                 thisFoot->Magic = 0;
 119                 head->Size = 0;         // Clear old header
 120                 head->Magic = 0;
 121         }
 122
 123         // Return new address
 124         return Head;
 125 }
 126
 127 /**
 128  * \fn void *malloc(size_t Bytes)
 129  * \brief Allocate memory from the heap
 130  */
 131 void *malloc(size_t Bytes)
 132 {
 133         tHeapHead       *head, *newhead;
 134         tHeapFoot       *foot, *newfoot;
 135         tHeapHead       *best = NULL;
 136         Uint    bestSize = 0;   // Speed hack
 137
 138         // Get required size
 139         Bytes = (Bytes + sizeof(tHeapHead) + sizeof(tHeapFoot) + BLOCK_SIZE-1) & ~(BLOCK_SIZE-1);
 140
 141         // Lock Heap
 142         LOCK(&giHeapSpinlock);
 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                         #if WARNINGS
 153                         Warning("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                         #if WARNINGS
 164                         Warning("Magic of heap address %p is invalid (0x%x)", head, head->Magic);
 165                         Heap_Dump();
 166                         #endif
 167                         RELEASE(&giHeapSpinlock);       // Release spinlock
 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(&giHeapSpinlock);       // Release spinlock
 178                         LOG("RETURN %p, to %p", best->Data, __builtin_return_address(0));
 179                         return best->Data;
 180                 }
 181
 182                 // Break out of loop
 183                 #if FIRST_FIT
 184                 best = head;
 185                 bestSize = head->Size;
 186                 break;
 187                 #else
 188                 // or check if the block is the best size
 189                 if(bestSize > head->Size) {
 190                         best = head;
 191                         bestSize = head->Size;
 192                 }
 193                 #endif
 194         }
 195
 196         // If no block large enough is found, create one
 197         if(!best)
 198         {
 199                 best = Heap_Extend( Bytes );
 200                 // Check for errors
 201                 if(!best) {
 202                         RELEASE(&giHeapSpinlock);       // Release spinlock
 203                         return NULL;
 204                 }
 205                 // Check size
 206                 if(best->Size == Bytes) {
 207                         RELEASE(&giHeapSpinlock);       // Release spinlock
 208                         LOG("RETURN %p, to %p", best->Data, __builtin_return_address(0));
 209                         return best->Data;
 210                 }
 211         }
 212
 213         // Split Block
 214         newhead = (void*)( (Uint)best + Bytes );
 215         newfoot = (void*)( (Uint)best + Bytes - sizeof(tHeapFoot) );
 216         foot = (void*)( (Uint)best + best->Size - sizeof(tHeapFoot) );
 217
 218         newfoot->Head = best;   // Create new footer
 219         newfoot->Magic = MAGIC_FOOT;
 220         newhead->Size = best->Size - Bytes;     // Create new header
 221         newhead->Magic = MAGIC_FREE;
 222         foot->Head = newhead;   // Update backlink in old footer
 223         best->Size = Bytes;             // Update size in old header
 224         best->Magic = MAGIC_USED;       // Mark block as used
 225
 226         RELEASE(&giHeapSpinlock);       // Release spinlock
 227         LOG("RETURN %p, to %p", best->Data, __builtin_return_address(0));
 228         return best->Data;
 229 }
 230
 231 /**
 232  * \fn void free(void *Ptr)
 233  * \brief Free an allocated memory block
 234  */
 235 void free(void *Ptr)
 236 {
 237         tHeapHead       *head;
 238         tHeapFoot       *foot;
 239
 240         LOG("Ptr = %p", Ptr);
 241         LOG("Returns to %p", __builtin_return_address(0));
 242
 243         // Alignment Check
 244         if( (Uint)Ptr & (sizeof(Uint)-1) ) {
 245                 Warning("free - Passed a non-aligned address (%p)\n", Ptr);
 246                 return;
 247         }
 248
 249         // Sanity check
 250         if((Uint)Ptr < (Uint)gHeapStart || (Uint)Ptr > (Uint)gHeapEnd)
 251         {
 252                 Warning("free - Passed a non-heap address (%p)\n", Ptr);
 253                 return;
 254         }
 255
 256         // Check memory block - Header
 257         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 258         if(head->Magic == MAGIC_FREE) {
 259                 Warning("free - Passed a freed block (%p)\n", head);
 260                 return;
 261         }
 262         if(head->Magic != MAGIC_USED) {
 263                 Warning("free - Magic value is invalid (%p, 0x%x)\n", head, head->Magic);
 264                 return;
 265         }
 266
 267         // Check memory block - Footer
 268         foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 269         if(foot->Head != head) {
 270                 Warning("free - Footer backlink is incorrect (%p, 0x%x)\n", head, foot->Head);
 271                 return;
 272         }
 273         if(foot->Magic != MAGIC_FOOT) {
 274                 Warning("free - Footer magic is invalid (%p, 0x%x)\n", head, foot->Magic);
 275                 return;
 276         }
 277
 278         // Lock
 279         LOCK( &giHeapSpinlock );
 280
 281         // Mark as free
 282         head->Magic = MAGIC_FREE;
 283         // Merge blocks
 284         Heap_Merge( head );
 285
 286         // Release
 287         RELEASE( &giHeapSpinlock );
 288 }
 289
 290 /**
 291  */
 292 void *realloc(void *__ptr, size_t __size)
 293 {
 294         tHeapHead       *head = (void*)( (Uint)__ptr-8 );
 295         tHeapHead       *nextHead;
 296         tHeapFoot       *foot;
 297         Uint    newSize = (__size + sizeof(tHeapFoot)+sizeof(tHeapHead)+BLOCK_SIZE-1)&~(BLOCK_SIZE-1);
 298
 299         // Check for reallocating NULL
 300         if(__ptr == NULL)       return malloc(__size);
 301
 302         // Check if resize is needed
 303         if(newSize <= head->Size)       return __ptr;
 304
 305         // Check if next block is free
 306         nextHead = (void*)( (Uint)head + head->Size );
 307
 308         // Extend into next block
 309         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 310         {
 311                 Uint    size = nextHead->Size + head->Size;
 312                 foot = (void*)( (Uint)nextHead + nextHead->Size - sizeof(tHeapFoot) );
 313                 // Exact Fit
 314                 if(size == newSize) {
 315                         head->Size = newSize;
 316                         foot->Head = head;
 317                         nextHead->Magic = 0;
 318                         nextHead->Size = 0;
 319                         return __ptr;
 320                 }
 321                 // Create a new heap block
 322                 nextHead = (void*)( (Uint)head + newSize );
 323                 nextHead->Size = size - newSize;
 324                 nextHead->Magic = MAGIC_FREE;
 325                 foot->Head = nextHead;  // Edit 2nd footer
 326                 head->Size = newSize;   // Edit first header
 327                 // Create new footer
 328                 foot = (void*)( (Uint)head + newSize - sizeof(tHeapFoot) );
 329                 foot->Head = head;
 330                 foot->Magic = MAGIC_FOOT;
 331                 return __ptr;
 332         }
 333
 334         // Extend downwards?
 335         foot = (void*)( (Uint)head - sizeof(tHeapFoot) );
 336         nextHead = foot->Head;
 337         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 338         {
 339                 Uint    size = nextHead->Size + head->Size;
 340                 // Exact fit
 341                 if(size == newSize)
 342                 {
 343                         Uint    oldDataSize;
 344                         // Set 1st (new/lower) header
 345                         nextHead->Magic = MAGIC_USED;
 346                         nextHead->Size = newSize;
 347                         // Get 2nd (old) footer
 348                         foot = (void*)( (Uint)nextHead + newSize );
 349                         foot->Head = nextHead;
 350                         // Save old data size
 351                         oldDataSize = head->Size - sizeof(tHeapFoot) - sizeof(tHeapHead);
 352                         // Clear old header
 353                         head->Size = 0;
 354                         head->Magic = 0;
 355                         memcpy(nextHead->Data, __ptr, oldDataSize);
 356                 }
 357         }
 358
 359         return NULL;
 360 }
 361
 362 /**
 363  * \fn int IsHeap(void *Ptr)
 364  * \brief Checks if an address is a heap address
 365  */
 366 int IsHeap(void *Ptr)
 367 {
 368         tHeapHead       *head;
 369         if((Uint)Ptr < (Uint)gHeapStart)        return 0;
 370         if((Uint)Ptr > (Uint)gHeapEnd)  return 0;
 371
 372         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 373         if(head->Magic != MAGIC_USED && head->Magic != MAGIC_FREE)
 374                 return 0;
 375
 376         return 1;
 377 }
 378
 379 #if WARNINGS
 380 void Heap_Dump()
 381 {
 382         tHeapHead       *head;
 383         tHeapFoot       *foot;
 384
 385         head = gHeapStart;
 386         while( (Uint)head < (Uint)gHeapEnd )
 387         {
 388                 foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 389                 Log("%p (0x%x): 0x%08lx 0x%lx", head, MM_GetPhysAddr((Uint)head), head->Size, head->Magic);
 390                 Log("%p 0x%lx", foot->Head, foot->Magic);
 391                 Log("");
 392
 393                 // Sanity Check Header
 394                 if(head->Size == 0) {
 395                         Log("HALTED - Size is zero");
 396                         break;
 397                 }
 398                 if(head->Size & (BLOCK_SIZE-1)) {
 399                         Log("HALTED - Size is malaligned");
 400                         break;
 401                 }
 402                 if(head->Magic != MAGIC_FREE && head->Magic != MAGIC_USED) {
 403                         Log("HALTED - Head Magic is Bad");
 404                         break;
 405                 }
 406
 407                 // Check footer
 408                 if(foot->Magic != MAGIC_FOOT) {
 409                         Log("HALTED - Foot Magic is Bad");
 410                         break;
 411                 }
 412                 if(head != foot->Head) {
 413                         Log("HALTED - Footer backlink is invalid");
 414                         break;
 415                 }
 416
 417                 // All OK? Go to next
 418                 head = foot->NextHead;
 419         }
 420 }
 421 #endif