git.mutantstargoat.com Git - bootcensus/blob - src/libc/malloc.c

   1 /*
   2 pcboot - bootable PC demo/game kernel
   3 Copyright (C) 2018-2019  John Tsiombikas <nuclear@member.fsf.org>
   4
   5 This program is free software: you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation, either version 3 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY, without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program.  If not, see <https://www.gnu.org/licenses/>.
  17 */
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <errno.h>
  22 #include <assert.h>
  23 #include "config.h"
  24 #include "mem.h"
  25 #include "panic.h"
  26
  27 #define SINGLE_POOL
  28
  29 struct mem_desc {
  30         size_t size;
  31         uint32_t magic;
  32 #ifdef MALLOC_DEBUG
  33         uint32_t dbg;
  34 #endif
  35         struct mem_desc *next;
  36 };
  37
  38 #ifdef MALLOC_DEBUG
  39 static void check_cycles(struct mem_desc *mem);
  40 static void print_pool(void);
  41 #endif
  42
  43 #define MAGIC_USED      0xdeadf00d
  44 #define MAGIC_FREE      0x1ee7d00d
  45
  46 #define DESC_PTR(b)     ((void*)((struct mem_desc*)(b) + 1))
  47 #define PTR_DESC(p)     ((struct mem_desc*)(p) - 1)
  48
  49 #ifdef SINGLE_POOL
  50 static struct mem_desc *pool;
  51 #else
  52
  53 #define NUM_POOLS       16
  54 #define FIRST_POOL_POW2 5
  55 /* 2**(x+5) size pools: 0->32, 1->64, 2->128 .. 15->1048576 */
  56 #define POOL_SIZE(x)    (1 << ((x) + FIRST_POOL_POW2))
  57 #define MAX_POOL_SIZE   (1 << ((NUM_POOLS - 1) + FIRST_POOL_POW2))
  58 #define MAX_POOL_PAGES  BYTES_TO_PAGES(MAX_POOL_SIZE)
  59 static struct mem_desc *pools[NUM_POOLS];
  60
  61 static int add_to_pool(struct mem_desc *b);
  62
  63 static int pool_index(int sz)
  64 {
  65         int x = 0;
  66         --sz;
  67         while(sz) {
  68                 sz >>= 1;
  69                 ++x;
  70         }
  71         return x - FIRST_POOL_POW2;
  72 }
  73 #endif  /* !SINGLE_POOL */
  74
  75
  76 #ifdef SINGLE_POOL
  77 #define MIN_BLOCK_SIZE          (sizeof(struct mem_desc) * 2)
  78
  79 void *malloc(size_t sz)
  80 {
  81         int pg0, npages;
  82         size_t total_sz, rest_sz;
  83         struct mem_desc *mem, *rest, *prev, dummy;
  84         int found = 0;
  85
  86         total_sz = (sz + sizeof(struct mem_desc) + 3) & 0xfffffffc;
  87
  88         dummy.next = pool;
  89         prev = &dummy;
  90         while(prev->next) {
  91                 mem = prev->next;
  92                 /* give the whole block to the allocation if mem->size == total_sz or
  93                  * if it's larger, but not large enough to fit another mem_desc in there
  94                  * for the new block that we're going to split off + some reasonable
  95                  * amount of memory for the new block.
  96                  */
  97                 if(mem->size >= total_sz && mem->size < total_sz + MIN_BLOCK_SIZE) {
  98                         prev->next = mem->next;
  99                         found = 1;
 100                         break;
 101                 }
 102                 /* if we have enough space, split the block and give the upper part
 103                  * to the allocation
 104                  */
 105                 if(mem->size > total_sz) {
 106                         void *ptr = (char*)mem + mem->size - total_sz;
 107                         mem->size -= total_sz;
 108                         mem = ptr;
 109                         found = 1;
 110                         break;
 111                 }
 112                 prev = prev->next;
 113         }
 114         pool = dummy.next;
 115
 116         if(found) {
 117                 mem->size = total_sz;
 118                 mem->magic = MAGIC_USED;
 119                 mem->next = 0;
 120                 return DESC_PTR(mem);
 121         }
 122
 123         /* did not find a free block, grab a new one */
 124         npages = BYTES_TO_PAGES(total_sz);
 125         if((pg0 = alloc_ppages(npages, 0)) == -1) {
 126                 errno = ENOMEM;
 127                 return 0;
 128         }
 129         mem = PAGE_TO_PTR(pg0);
 130         mem->size = total_sz;
 131         mem->next = 0;
 132         mem->magic = MAGIC_USED;
 133
 134         /* add the rest of the block to pool */
 135         rest_sz = npages * 4096 - total_sz;
 136         if(rest_sz > 0) {
 137                 rest = (struct mem_desc*)((char*)mem + total_sz);
 138                 rest->size = rest_sz;
 139                 rest->next = 0;
 140                 rest->magic = MAGIC_USED;
 141                 free(DESC_PTR(rest));
 142         }
 143
 144         return DESC_PTR(mem);
 145 }
 146
 147 void free(void *p)
 148 {
 149         struct mem_desc *mem, *prev, *cur, dummy;
 150         char *end;
 151
 152         if(!p) return;
 153         mem = PTR_DESC(p);
 154
 155         if(mem->magic != MAGIC_USED) {
 156                 if(mem->magic == MAGIC_FREE) {
 157                         panic("free(%p): double-free\n", p);
 158                 } else {
 159                         panic("free(%p): corrupted magic (%x)!\n", p, mem->magic);
 160                 }
 161         }
 162         mem->magic = MAGIC_FREE;
 163         mem->next = 0;
 164
 165         /* nothing in the pool, just add this one */
 166         if(!pool) {
 167                 pool = mem;
 168                 return;
 169         }
 170
 171         end = (char*)mem + mem->size;
 172
 173         dummy.next = pool;
 174         prev = &dummy;
 175
 176         while(prev->next) {
 177                 cur = prev->next;
 178
 179                 /* block starts right at the end of mem: coalesce */
 180                 if((char*)cur == end) {
 181                         mem->size += cur->size;
 182                         mem->next = cur->next;
 183                         cur->magic = 0;
 184                         prev->next = mem;
 185                         goto done;
 186                 }
 187
 188                 /* block starts *after* the end of mem: add in front */
 189                 if((char*)cur > end) {
 190                         mem->next = cur;
 191                         prev->next = mem;
 192                         goto done;
 193                 }
 194
 195                 prev = prev->next;
 196         }
 197
 198         /* our block starts at the end of the last block in the pool: coalesce */
 199         if((char*)prev + prev->size == (char*)mem) {
 200                 mem->magic = 0;
 201                 prev->size += mem->size;
 202                 goto done;
 203         }
 204
 205         /* so our block starts after the end of the last block: append */
 206         prev->next = mem;
 207
 208 done:
 209         pool = dummy.next;
 210
 211 #ifdef MALLOC_DEBUG
 212         print_pool();
 213 #endif
 214 }
 215
 216 #else   /* !SINGLE_POOL */
 217
 218 void *malloc(size_t sz)
 219 {
 220         int pidx, pg0;
 221         size_t total_sz, halfsz;
 222         struct mem_desc *mem, *other;
 223
 224         total_sz = sz + sizeof(struct mem_desc);
 225
 226         if(total_sz > MAX_POOL_SIZE) {
 227                 /*printf("  allocation too big, hitting sys_alloc directly\n");*/
 228                 if((pg0 = alloc_ppages(BYTES_TO_PAGES(total_sz), 0)) == -1) {
 229                         errno = ENOMEM;
 230                         return 0;
 231                 }
 232                 mem = PAGE_TO_PTR(pg0);
 233                 mem->magic = MAGIC_USED;
 234                 mem->size = total_sz;
 235                 mem->next = 0;
 236                 return DESC_PTR(mem);
 237         }
 238
 239         pidx = pool_index(total_sz);
 240         while(pidx < NUM_POOLS) {
 241                 if(pools[pidx]) {
 242                         /* found a pool with a free block that fits */
 243                         mem = pools[pidx];
 244                         pools[pidx] = mem->next;
 245                         mem->next = 0;
 246
 247                         /*printf("  using pool %d (size %ld)\n", pidx, (unsigned long)mem->size);*/
 248
 249                         /* while the mem size is larger than twice the allocation, split it */
 250                         while(pidx-- > 0 && total_sz <= (halfsz = mem->size / 2)) {
 251                                 /*printf("  splitting %ld block in half and ", (unsigned long)mem->size);*/
 252                                 other = (struct mem_desc*)((char*)mem + halfsz);
 253                                 mem->size = other->size = halfsz;
 254
 255                                 add_to_pool(other);
 256                         }
 257
 258                         if(mem->magic != MAGIC_FREE) {
 259                                 panic("Trying to allocate range surrounded by an aura of wrong MAGIC\n");
 260                         }
 261                         mem->magic = MAGIC_USED;
 262                         return DESC_PTR(mem);
 263                 }
 264
 265                 ++pidx;
 266         }
 267
 268         /* did not find a free block, add a new one */
 269         pidx = NUM_POOLS - 1;
 270         if((pg0 = alloc_ppages(MAX_POOL_PAGES, 0)) == -1) {
 271                 errno = ENOMEM;
 272                 return 0;
 273         }
 274         mem = PAGE_TO_PTR(pg0);
 275         mem->size = MAX_POOL_SIZE;
 276         mem->next = pools[pidx];
 277         mem->magic = MAGIC_FREE;
 278         pools[pidx] = mem;
 279
 280         /* try again now that there is a free block */
 281         return malloc(sz);
 282 }
 283
 284
 285 void free(void *p)
 286 {
 287         int pg0;
 288         struct mem_desc *mem;
 289
 290         if(!p) return;
 291
 292         mem = PTR_DESC(p);
 293         if(mem->magic != MAGIC_USED) {
 294                 if(mem->magic == MAGIC_FREE) {
 295                         panic("free(%p): double-free\n", p);
 296                 } else {
 297                         panic("free(%p): corrupted magic (%x)!\n", p, mem->magic);
 298                 }
 299         }
 300
 301         if(mem->size > MAX_POOL_SIZE) {
 302                 /*printf("foo_free(%p): %ld bytes. block too large for pools, returning to system\n",
 303                                 (void*)p, (unsigned long)mem->size);*/
 304                 pg0 = ADDR_TO_PAGE(mem);
 305                 free_ppages(pg0, BYTES_TO_PAGES(mem->size));
 306                 return;
 307         }
 308
 309         /*printf("foo_free(%p): block of %ld bytes and ", (void*)p, (unsigned long)mem->size);*/
 310         add_to_pool(mem);
 311 }
 312
 313 #endif  /* !def SINGLE_POOL */
 314
 315
 316 void *calloc(size_t num, size_t size)
 317 {
 318         void *ptr = malloc(num * size);
 319         if(ptr) {
 320                 memset(ptr, 0, num * size);
 321         }
 322         return ptr;
 323 }
 324
 325 void *realloc(void *ptr, size_t size)
 326 {
 327         struct mem_desc *mem;
 328         void *newp;
 329
 330         if(!ptr) {
 331                 return malloc(size);
 332         }
 333
 334         mem = PTR_DESC(ptr);
 335         if(mem->size >= size) {
 336                 return ptr;     /* TODO: shrink */
 337         }
 338
 339         if(!(newp = malloc(size))) {
 340                 return 0;
 341         }
 342         memcpy(newp, ptr, mem->size);
 343         free(ptr);
 344         return newp;
 345 }
 346
 347 #ifdef MALLOC_DEBUG
 348 static void check_cycles(struct mem_desc *mem)
 349 {
 350         static uint32_t dbg = 42;
 351         uint32_t cur_dbg = dbg++;
 352
 353         while(mem) {
 354                 if(mem->magic != MAGIC_FREE) {
 355                         panic("check_cycles: NON-FREE MAGIC!\n");
 356                 }
 357                 if(mem->dbg == cur_dbg) {
 358                         panic("CYCLE DETECTED\n");
 359                 }
 360                 mem->dbg = cur_dbg;
 361                 mem = mem->next;
 362         }
 363 }
 364
 365 static void print_pool(void)
 366 {
 367         struct mem_desc *mem = pool;
 368
 369         printf("DBG: malloc pool:\n");
 370         while(mem) {
 371                 printf(" %p (%ld) [%x]\n", mem, mem->size, mem->magic);
 372                 mem = mem->next;
 373
 374                 assert((uint32_t)mem != MAGIC_USED);
 375         }
 376 }
 377 #endif  /* MALLOC_DEBUG */
 378
 379 #ifndef SINGLE_POOL
 380 static int add_to_pool(struct mem_desc *mem)
 381 {
 382         int pidx;
 383         struct mem_desc head;
 384         struct mem_desc *iter, *pnode;
 385
 386         pidx = pool_index(mem->size);
 387
 388         /*printf("adding %ld block to pool %d\n", (unsigned long)mem->size, pidx);*/
 389
 390         iter = &head;
 391         head.next = pools[pidx];
 392
 393         while(iter->next) {
 394                 pnode = iter->next;
 395                 if(mem->size == pnode->size) {  /* only coalesce same-sized blocks */
 396                         size_t size = mem->size;
 397
 398                         if((char*)mem == (char*)pnode - size) {
 399                                 iter->next = pnode->next;       /* unlink pnode */
 400                                 pools[pidx] = head.next;
 401                                 mem->next = 0;
 402                                 mem->size += size;
 403
 404                                 /*printf("  coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
 405                                 return add_to_pool(mem);
 406                         }
 407                         if((char*)mem == (char*)pnode + size) {
 408                                 iter->next = pnode->next;       /* unlink pnode */
 409                                 pools[pidx] = head.next;
 410                                 pnode->next = 0;
 411                                 pnode->size += size;
 412
 413                                 /*printf("  coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
 414                                 return add_to_pool(pnode);
 415                         }
 416                 }
 417                 iter = iter->next;
 418         }
 419
 420         /* otherwise just add it to the pool */
 421         mem->magic = MAGIC_FREE;
 422         mem->next = pools[pidx];
 423         pools[pidx] = mem;
 424
 425 #ifdef MALLOC_DEBUG
 426         check_cycles(pools[pidx]);
 427 #endif
 428         return 0;
 429 }
 430 #endif  /* !def SINGLE_POOL */