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                         return best->Data;
 179                 }
 180
 181                 // Break out of loop
 182                 #if FIRST_FIT
 183                 best = head;
 184                 bestSize = head->Size;
 185                 break;
 186                 #else
 187                 // or check if the block is the best size
 188                 if(bestSize > head->Size) {
 189                         best = head;
 190                         bestSize = head->Size;
 191                 }
 192                 #endif
 193         }
 194
 195         // If no block large enough is found, create one
 196         if(!best)
 197         {
 198                 best = Heap_Extend( Bytes );
 199                 // Check for errors
 200                 if(!best) {
 201                         RELEASE(&giHeapSpinlock);       // Release spinlock
 202                         return NULL;
 203                 }
 204                 // Check size
 205                 if(best->Size == Bytes) {
 206                         RELEASE(&giHeapSpinlock);       // Release spinlock
 207                         return best->Data;
 208                 }
 209         }
 210
 211         // Split Block
 212         newhead = (void*)( (Uint)best + Bytes );
 213         newfoot = (void*)( (Uint)best + Bytes - sizeof(tHeapFoot) );
 214         foot = (void*)( (Uint)best + best->Size - sizeof(tHeapFoot) );
 215
 216         newfoot->Head = best;   // Create new footer
 217         newfoot->Magic = MAGIC_FOOT;
 218         newhead->Size = best->Size - Bytes;     // Create new header
 219         newhead->Magic = MAGIC_FREE;
 220         foot->Head = newhead;   // Update backlink in old footer
 221         best->Size = Bytes;             // Update size in old header
 222         best->Magic = MAGIC_USED;       // Mark block as used
 223
 224         RELEASE(&giHeapSpinlock);       // Release spinlock
 225         return best->Data;
 226 }
 227
 228 /**
 229  * \fn void free(void *Ptr)
 230  * \brief Free an allocated memory block
 231  */
 232 void free(void *Ptr)
 233 {
 234         tHeapHead       *head;
 235         tHeapFoot       *foot;
 236
 237         LOG("Ptr = %p", Ptr);
 238         LOG("Returns to %p", __builtin_return_address(0));
 239
 240         // Alignment Check
 241         if( (Uint)Ptr & (sizeof(Uint)-1) ) {
 242                 Warning("free - Passed a non-aligned address (%p)\n", Ptr);
 243                 return;
 244         }
 245
 246         // Sanity check
 247         if((Uint)Ptr < (Uint)gHeapStart || (Uint)Ptr > (Uint)gHeapEnd)
 248         {
 249                 Warning("free - Passed a non-heap address (%p)\n", Ptr);
 250                 return;
 251         }
 252
 253         // Check memory block - Header
 254         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 255         if(head->Magic == MAGIC_FREE) {
 256                 Warning("free - Passed a freed block (%p)\n", head);
 257                 return;
 258         }
 259         if(head->Magic != MAGIC_USED) {
 260                 Warning("free - Magic value is invalid (%p, 0x%x)\n", head, head->Magic);
 261                 return;
 262         }
 263
 264         // Check memory block - Footer
 265         foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 266         if(foot->Head != head) {
 267                 Warning("free - Footer backlink is incorrect (%p, 0x%x)\n", head, foot->Head);
 268                 return;
 269         }
 270         if(foot->Magic != MAGIC_FOOT) {
 271                 Warning("free - Footer magic is invalid (%p, 0x%x)\n", head, foot->Magic);
 272                 return;
 273         }
 274
 275         // Lock
 276         LOCK( &giHeapSpinlock );
 277
 278         // Mark as free
 279         head->Magic = MAGIC_FREE;
 280         // Merge blocks
 281         Heap_Merge( head );
 282
 283         // Release
 284         RELEASE( &giHeapSpinlock );
 285 }
 286
 287 /**
 288  */
 289 void *realloc(void *__ptr, size_t __size)
 290 {
 291         tHeapHead       *head = (void*)( (Uint)__ptr-8 );
 292         tHeapHead       *nextHead;
 293         tHeapFoot       *foot;
 294         Uint    newSize = (__size + sizeof(tHeapFoot)+sizeof(tHeapHead)+BLOCK_SIZE-1)&~(BLOCK_SIZE-1);
 295
 296         // Check for reallocating NULL
 297         if(__ptr == NULL)       return malloc(__size);
 298
 299         // Check if resize is needed
 300         if(newSize <= head->Size)       return __ptr;
 301
 302         // Check if next block is free
 303         nextHead = (void*)( (Uint)head + head->Size );
 304
 305         // Extend into next block
 306         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 307         {
 308                 Uint    size = nextHead->Size + head->Size;
 309                 foot = (void*)( (Uint)nextHead + nextHead->Size - sizeof(tHeapFoot) );
 310                 // Exact Fit
 311                 if(size == newSize) {
 312                         head->Size = newSize;
 313                         foot->Head = head;
 314                         nextHead->Magic = 0;
 315                         nextHead->Size = 0;
 316                         return __ptr;
 317                 }
 318                 // Create a new heap block
 319                 nextHead = (void*)( (Uint)head + newSize );
 320                 nextHead->Size = size - newSize;
 321                 nextHead->Magic = MAGIC_FREE;
 322                 foot->Head = nextHead;  // Edit 2nd footer
 323                 head->Size = newSize;   // Edit first header
 324                 // Create new footer
 325                 foot = (void*)( (Uint)head + newSize - sizeof(tHeapFoot) );
 326                 foot->Head = head;
 327                 foot->Magic = MAGIC_FOOT;
 328                 return __ptr;
 329         }
 330
 331         // Extend downwards?
 332         foot = (void*)( (Uint)head - sizeof(tHeapFoot) );
 333         nextHead = foot->Head;
 334         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 335         {
 336                 Uint    size = nextHead->Size + head->Size;
 337                 // Exact fit
 338                 if(size == newSize)
 339                 {
 340                         Uint    oldDataSize;
 341                         // Set 1st (new/lower) header
 342                         nextHead->Magic = MAGIC_USED;
 343                         nextHead->Size = newSize;
 344                         // Get 2nd (old) footer
 345                         foot = (void*)( (Uint)nextHead + newSize );
 346                         foot->Head = nextHead;
 347                         // Save old data size
 348                         oldDataSize = head->Size - sizeof(tHeapFoot) - sizeof(tHeapHead);
 349                         // Clear old header
 350                         head->Size = 0;
 351                         head->Magic = 0;
 352                         memcpy(nextHead->Data, __ptr, oldDataSize);
 353                 }
 354         }
 355
 356         return NULL;
 357 }
 358
 359 #if WARNINGS
 360 void Heap_Dump()
 361 {
 362         tHeapHead       *head;
 363         tHeapFoot       *foot;
 364
 365         head = gHeapStart;
 366         while( (Uint)head < (Uint)gHeapEnd )
 367         {
 368                 foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 369                 Log("%p (0x%x): 0x%08lx 0x%lx", head, MM_GetPhysAddr((Uint)head), head->Size, head->Magic);
 370                 Log("%p 0x%lx", foot->Head, foot->Magic);
 371                 Log("");
 372
 373                 // Sanity Check Header
 374                 if(head->Size == 0) {
 375                         Log("HALTED - Size is zero");
 376                         break;
 377                 }
 378                 if(head->Size & (BLOCK_SIZE-1)) {
 379                         Log("HALTED - Size is malaligned");
 380                         break;
 381                 }
 382                 if(head->Magic != MAGIC_FREE && head->Magic != MAGIC_USED) {
 383                         Log("HALTED - Head Magic is Bad");
 384                         break;
 385                 }
 386
 387                 // Check footer
 388                 if(foot->Magic != MAGIC_FOOT) {
 389                         Log("HALTED - Foot Magic is Bad");
 390                         break;
 391                 }
 392                 if(head != foot->Head) {
 393                         Log("HALTED - Footer backlink is invalid");
 394                         break;
 395                 }
 396
 397                 // All OK? Go to next
 398                 head = foot->NextHead;
 399         }
 400 }
 401 #endif