kernel/heap.c

   1 /*
   2 ** Copyright 2001, Travis Geiselbrecht. All rights reserved.
   3 ** Distributed under the terms of the NewOS License.
   4 */
   5 #include <kernel/kernel.h>
   6 #include <kernel/vm.h>
   7 #include <kernel/lock.h>
   8 #include <kernel/heap.h>
   9 #include <kernel/debug.h>
  10
  11 #include <kernel/arch/cpu.h>
  12
  13 #include <boot/stage2.h>
  14
  15 #include <string.h>
  16
  17 #if DEBUG > 1
  18 #define PARANOID_KFREE 1
  19 #endif
  20 #if DEBUG > 2
  21 #define WIPE_KFREE 1
  22 #endif
  23 #define MAKE_NOIZE 0
  24
  25 // heap stuff
  26 // ripped mostly from nujeffos
  27
  28 struct heap_page {
  29         unsigned short bin_index : 5;
  30         unsigned short free_count : 9;
  31         unsigned short cleaning : 1;
  32         unsigned short in_use : 1;
  33 };
  34
  35 static struct heap_page *heap_alloc_table;
  36 static addr_t heap_base_ptr;
  37 static addr_t heap_base;
  38 static addr_t heap_size;
  39
  40 struct heap_bin {
  41         unsigned int element_size;
  42         unsigned int grow_size;
  43         unsigned int alloc_count;
  44         void *free_list;
  45         unsigned int free_count;
  46         char *raw_list;
  47         unsigned int raw_count;
  48 };
  49 static struct heap_bin bins[] = {
  50         {16, PAGE_SIZE, 0, 0, 0, 0, 0},
  51         {32, PAGE_SIZE, 0, 0, 0, 0, 0},
  52         {64, PAGE_SIZE, 0, 0, 0, 0, 0},
  53         {128, PAGE_SIZE, 0, 0, 0, 0, 0},
  54         {256, PAGE_SIZE, 0, 0, 0, 0, 0},
  55         {512, PAGE_SIZE, 0, 0, 0, 0, 0},
  56         {1024, PAGE_SIZE, 0, 0, 0, 0, 0},
  57         {2048, PAGE_SIZE, 0, 0, 0, 0, 0},
  58         {0x1000, 0x1000, 0, 0, 0, 0, 0},
  59         {0x2000, 0x2000, 0, 0, 0, 0, 0},
  60         {0x3000, 0x3000, 0, 0, 0, 0, 0},
  61         {0x4000, 0x4000, 0, 0, 0, 0, 0},
  62         {0x5000, 0x5000, 0, 0, 0, 0, 0},
  63         {0x6000, 0x6000, 0, 0, 0, 0, 0},
  64         {0x7000, 0x7000, 0, 0, 0, 0, 0},
  65         {0x8000, 0x8000, 0, 0, 0, 0, 0},
  66         {0x9000, 0x9000, 0, 0, 0, 0, 0},
  67         {0xa000, 0xa000, 0, 0, 0, 0, 0},
  68         {0xb000, 0xb000, 0, 0, 0, 0, 0},
  69         {0xc000, 0xc000, 0, 0, 0, 0, 0},
  70         {0xd000, 0xd000, 0, 0, 0, 0, 0},
  71         {0xe000, 0xe000, 0, 0, 0, 0, 0},
  72         {0xf000, 0xf000, 0, 0, 0, 0, 0},
  73         {0x10000, 0x10000, 0, 0, 0, 0, 0} // 64k
  74 };
  75
  76 static const int bin_count = sizeof(bins) / sizeof(struct heap_bin);
  77 static mutex heap_lock;
  78
  79 static void dump_bin(int bin_index)
  80 {
  81         struct heap_bin *bin = &bins[bin_index];
  82         unsigned int *temp;
  83
  84         dprintf("%d:\tesize %d\tgrow_size %d\talloc_count %d\tfree_count %d\traw_count %d\traw_list %p\n",
  85                 bin_index, bin->element_size, bin->grow_size, bin->alloc_count, bin->free_count, bin->raw_count, bin->raw_list);
  86         dprintf("free_list: ");
  87         for(temp = bin->free_list; temp != NULL; temp = (unsigned int *)*temp) {
  88                 dprintf("%p ", temp);
  89         }
  90         dprintf("NULL\n");
  91 }
  92
  93 static void dump_bin_list(int argc, char **argv)
  94 {
  95         int i;
  96
  97         dprintf("%d heap bins at %p:\n", bin_count, bins);
  98
  99         for(i=0; i<bin_count; i++) {
 100                 dump_bin(i);
 101         }
 102 }
 103
 104 // called from vm_init. The heap should already be mapped in at this point, we just
 105 // do a little housekeeping to set up the data structure.
 106 int heap_init(addr_t new_heap_base, unsigned int new_heap_size)
 107 {
 108         const unsigned int page_entries = PAGE_SIZE / sizeof(struct heap_page);
 109         // set some global pointers
 110         heap_alloc_table = (struct heap_page *)new_heap_base;
 111         //heap_size = ((uint64)new_heap_size * page_entries / (page_entries + 1)) & ~(PAGE_SIZE-1);
 112         heap_size = new_heap_size - PAGE_SIZE;  // use above line instead if new_heap_size > sqr(PAGE_SIZE)/2
 113         heap_base = (unsigned int)heap_alloc_table + PAGE_ALIGN(heap_size / page_entries);
 114         heap_base_ptr = heap_base;
 115         dprintf("heap_alloc_table = %p, heap_base = 0x%lx, heap_size = 0x%lx\n", heap_alloc_table, heap_base, heap_size);
 116
 117         // zero out the heap alloc table at the base of the heap
 118         memset((void *)heap_alloc_table, 0, (heap_size / PAGE_SIZE) * sizeof(struct heap_page));
 119
 120         // pre-init the mutex to at least fall through any semaphore calls
 121         heap_lock.sem = -1;
 122         heap_lock.holder = -1;
 123
 124         // set up some debug commands
 125         dbg_add_command(&dump_bin_list, "heap_bindump", "dump stats about bin usage");
 126
 127         return 0;
 128 }
 129
 130 int heap_init_postsem(kernel_args *ka)
 131 {
 132         if(mutex_init(&heap_lock, "heap_mutex") < 0) {
 133                 panic("error creating heap mutex\n");
 134         }
 135         return 0;
 136 }
 137
 138 static char *raw_alloc(unsigned int size, int bin_index)
 139 {
 140         unsigned int new_heap_ptr;
 141         char *retval;
 142         struct heap_page *page;
 143         unsigned int addr;
 144
 145         new_heap_ptr = heap_base_ptr + PAGE_ALIGN(size);
 146         if(new_heap_ptr > heap_base + heap_size) {
 147                 panic("heap overgrew itself!\n");
 148         }
 149
 150         for(addr = heap_base_ptr; addr < new_heap_ptr; addr += PAGE_SIZE) {
 151                 page = &heap_alloc_table[(addr - heap_base) / PAGE_SIZE];
 152                 page->in_use = 1;
 153                 page->cleaning = 0;
 154                 page->bin_index = bin_index;
 155                 if (bin_index < bin_count && bins[bin_index].element_size < PAGE_SIZE)
 156                         page->free_count = PAGE_SIZE / bins[bin_index].element_size;
 157                 else
 158                         page->free_count = 1;
 159         }
 160
 161         retval = (char *)heap_base_ptr;
 162         heap_base_ptr = new_heap_ptr;
 163         return retval;
 164 }
 165
 166 void *kmalloc(unsigned int size)
 167 {
 168         void *address = NULL;
 169         int bin_index;
 170         unsigned int i;
 171         struct heap_page *page;
 172
 173 #if MAKE_NOIZE
 174         dprintf("kmalloc: asked to allocate size %d\n", size);
 175 #endif
 176
 177         mutex_lock(&heap_lock);
 178
 179         for (bin_index = 0; bin_index < bin_count; bin_index++)
 180                 if (size <= bins[bin_index].element_size)
 181                         break;
 182
 183         if (bin_index == bin_count) {
 184                 // XXX fix the raw alloc later.
 185                 //address = raw_alloc(size, bin_index);
 186                 panic("kmalloc: asked to allocate too much for now!\n");
 187                 goto out;
 188         } else {
 189                 if (bins[bin_index].free_list != NULL) {
 190                         address = bins[bin_index].free_list;
 191                         bins[bin_index].free_list = (void *)(*(unsigned int *)bins[bin_index].free_list);
 192                         bins[bin_index].free_count--;
 193                 } else {
 194                         if (bins[bin_index].raw_count == 0) {
 195                                 bins[bin_index].raw_list = raw_alloc(bins[bin_index].grow_size, bin_index);
 196                                 bins[bin_index].raw_count = bins[bin_index].grow_size / bins[bin_index].element_size;
 197                         }
 198
 199                         bins[bin_index].raw_count--;
 200                         address = bins[bin_index].raw_list;
 201                         bins[bin_index].raw_list += bins[bin_index].element_size;
 202                 }
 203
 204                 bins[bin_index].alloc_count++;
 205                 page = &heap_alloc_table[((unsigned int)address - heap_base) / PAGE_SIZE];
 206                 page[0].free_count--;
 207 #if MAKE_NOIZE
 208                 dprintf("kmalloc0: page 0x%x: bin_index %d, free_count %d\n", page, page->bin_index, page->free_count);
 209 #endif
 210                 for(i = 1; i < bins[bin_index].element_size / PAGE_SIZE; i++) {
 211                         page[i].free_count--;
 212 #if MAKE_NOIZE
 213                         dprintf("kmalloc1: page 0x%x: bin_index %d, free_count %d\n", page[i], page[i].bin_index, page[i].free_count);
 214 #endif
 215                 }
 216         }
 217
 218 out:
 219         mutex_unlock(&heap_lock);
 220
 221 #if MAKE_NOIZE
 222         dprintf("kmalloc: asked to allocate size %d, returning ptr = %p\n", size, address);
 223 #endif
 224         return address;
 225 }
 226
 227 void kfree(void *address)
 228 {
 229         struct heap_page *page;
 230         struct heap_bin *bin;
 231         unsigned int i;
 232
 233         if (address == NULL)
 234                 return;
 235
 236         if ((addr_t)address < heap_base || (addr_t)address >= (heap_base + heap_size))
 237                 panic("kfree: asked to free invalid address %p\n", address);
 238
 239         mutex_lock(&heap_lock);
 240
 241 #if MAKE_NOIZE
 242         dprintf("kfree: asked to free at ptr = %p\n", address);
 243 #endif
 244
 245         page = &heap_alloc_table[((unsigned)address - heap_base) / PAGE_SIZE];
 246
 247 #if MAKE_NOIZE
 248         dprintf("kfree: page 0x%x: bin_index %d, free_count %d\n", page, page->bin_index, page->free_count);
 249 #endif
 250
 251         if(page[0].bin_index >= bin_count)
 252                 panic("kfree: page %p: invalid bin_index %d\n", page, page->bin_index);
 253
 254         bin = &bins[page[0].bin_index];
 255
 256         if(bin->element_size <= PAGE_SIZE && (addr_t)address % bin->element_size != 0)
 257                 panic("kfree: passed invalid pointer %p! Supposed to be in bin for esize 0x%x\n", address, bin->element_size);
 258
 259         for(i = 0; i < bin->element_size / PAGE_SIZE; i++) {
 260                 if(page[i].bin_index != page[0].bin_index)
 261                         panic("kfree: not all pages in allocation match bin_index\n");
 262                 page[i].free_count++;
 263         }
 264
 265 #if PARANOID_KFREE
 266         // walk the free list on this bin to make sure this address doesn't exist already
 267         {
 268                 unsigned int *temp;
 269                 for(temp = bin->free_list; temp != NULL; temp = (unsigned int *)*temp) {
 270                         if(temp == (unsigned int *)address) {
 271                                 panic("kfree: address %p already exists in bin free list\n", address);
 272                         }
 273                 }
 274         }
 275 #endif
 276 #if WIPE_KFREE
 277         memset(address, 0x99, bin->element_size);
 278 #endif
 279
 280         *(unsigned int *)address = (unsigned int)bin->free_list;
 281         bin->free_list = address;
 282         bin->alloc_count--;
 283         bin->free_count++;
 284
 285         mutex_unlock(&heap_lock);
 286 }
 287
 288 char *kstrdup(const char *text)
 289 {
 290         char *buf = (char *)kmalloc(strlen(text) + 1);
 291
 292         if(buf != NULL)
 293                 strcpy(buf,text);
 294         return buf;
 295 }
 296