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