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         // Alignment Check
 238         if( (Uint)Ptr & (sizeof(Uint)-1) ) {
 239                 Warning("free - Passed a non-aligned address (%p)\n", Ptr);
 240                 return;
 241         }
 242
 243         // Sanity check
 244         if((Uint)Ptr < (Uint)gHeapStart || (Uint)Ptr > (Uint)gHeapEnd)
 245         {
 246                 Warning("free - Passed a non-heap address (%p)\n", Ptr);
 247                 return;
 248         }
 249
 250         // Check memory block - Header
 251         head = (void*)( (Uint)Ptr - sizeof(tHeapHead) );
 252         if(head->Magic == MAGIC_FREE) {
 253                 Warning("free - Passed a freed block (%p)\n", head);
 254                 return;
 255         }
 256         if(head->Magic != MAGIC_USED) {
 257                 Warning("free - Magic value is invalid (%p, 0x%x)\n", head, head->Magic);
 258                 return;
 259         }
 260
 261         // Check memory block - Footer
 262         foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 263         if(foot->Head != head) {
 264                 Warning("free - Footer backlink is incorrect (%p, 0x%x)\n", head, foot->Head);
 265                 return;
 266         }
 267         if(foot->Magic != MAGIC_FOOT) {
 268                 Warning("free - Footer magic is invalid (%p, 0x%x)\n", head, foot->Magic);
 269                 return;
 270         }
 271
 272         // Lock
 273         LOCK( &giHeapSpinlock );
 274
 275         // Mark as free
 276         head->Magic = MAGIC_FREE;
 277         // Merge blocks
 278         Heap_Merge( head );
 279
 280         // Release
 281         RELEASE( &giHeapSpinlock );
 282 }
 283
 284 /**
 285  */
 286 void *realloc(void *__ptr, size_t __size)
 287 {
 288         tHeapHead       *head = (void*)( (Uint)__ptr-8 );
 289         tHeapHead       *nextHead;
 290         tHeapFoot       *foot;
 291         Uint    newSize = (__size + sizeof(tHeapFoot)+sizeof(tHeapHead)+BLOCK_SIZE-1)&~(BLOCK_SIZE-1);
 292
 293         // Check for reallocating NULL
 294         if(__ptr == NULL)       return malloc(__size);
 295
 296         // Check if resize is needed
 297         if(newSize <= head->Size)       return __ptr;
 298
 299         // Check if next block is free
 300         nextHead = (void*)( (Uint)head + head->Size );
 301
 302         // Extend into next block
 303         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 304         {
 305                 Uint    size = nextHead->Size + head->Size;
 306                 foot = (void*)( (Uint)nextHead + nextHead->Size - sizeof(tHeapFoot) );
 307                 // Exact Fit
 308                 if(size == newSize) {
 309                         head->Size = newSize;
 310                         foot->Head = head;
 311                         nextHead->Magic = 0;
 312                         nextHead->Size = 0;
 313                         return __ptr;
 314                 }
 315                 // Create a new heap block
 316                 nextHead = (void*)( (Uint)head + newSize );
 317                 nextHead->Size = size - newSize;
 318                 nextHead->Magic = MAGIC_FREE;
 319                 foot->Head = nextHead;  // Edit 2nd footer
 320                 head->Size = newSize;   // Edit first header
 321                 // Create new footer
 322                 foot = (void*)( (Uint)head + newSize - sizeof(tHeapFoot) );
 323                 foot->Head = head;
 324                 foot->Magic = MAGIC_FOOT;
 325                 return __ptr;
 326         }
 327
 328         // Extend downwards?
 329         foot = (void*)( (Uint)head - sizeof(tHeapFoot) );
 330         nextHead = foot->Head;
 331         if(nextHead->Magic == MAGIC_FREE && nextHead->Size+head->Size >= newSize)
 332         {
 333                 Uint    size = nextHead->Size + head->Size;
 334                 // Exact fit
 335                 if(size == newSize)
 336                 {
 337                         Uint    oldDataSize;
 338                         // Set 1st (new/lower) header
 339                         nextHead->Magic = MAGIC_USED;
 340                         nextHead->Size = newSize;
 341                         // Get 2nd (old) footer
 342                         foot = (void*)( (Uint)nextHead + newSize );
 343                         foot->Head = nextHead;
 344                         // Save old data size
 345                         oldDataSize = head->Size - sizeof(tHeapFoot) - sizeof(tHeapHead);
 346                         // Clear old header
 347                         head->Size = 0;
 348                         head->Magic = 0;
 349                         memcpy(nextHead->Data, __ptr, oldDataSize);
 350                 }
 351         }
 352
 353         return NULL;
 354 }
 355
 356 #if WARNINGS
 357 void Heap_Dump()
 358 {
 359         tHeapHead       *head;
 360         tHeapFoot       *foot;
 361
 362         head = gHeapStart;
 363         while( (Uint)head < (Uint)gHeapEnd )
 364         {
 365                 foot = (void*)( (Uint)head + head->Size - sizeof(tHeapFoot) );
 366                 Log("%p (0x%x): 0x%08lx 0x%lx", head, MM_GetPhysAddr((Uint)head), head->Size, head->Magic);
 367                 Log("%p 0x%lx", foot->Head, foot->Magic);
 368                 Log("");
 369
 370                 // Sanity Check Header
 371                 if(head->Size == 0) {
 372                         Log("HALTED - Size is zero");
 373                         break;
 374                 }
 375                 if(head->Size & (BLOCK_SIZE-1)) {
 376                         Log("HALTED - Size is malaligned");
 377                         break;
 378                 }
 379                 if(head->Magic != MAGIC_FREE && head->Magic != MAGIC_USED) {
 380                         Log("HALTED - Head Magic is Bad");
 381                         break;
 382                 }
 383
 384                 // Check footer
 385                 if(foot->Magic != MAGIC_FOOT) {
 386                         Log("HALTED - Foot Magic is Bad");
 387                         break;
 388                 }
 389                 if(head != foot->Head) {
 390                         Log("HALTED - Footer backlink is invalid");
 391                         break;
 392                 }
 393
 394                 // All OK? Go to next
 395                 head = foot->NextHead;
 396         }
 397 }
 398 #endif