X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=bootcensus;a=blobdiff_plain;f=src%2Flibc%2Fmalloc.c;fp=src%2Flibc%2Fmalloc.c;h=363ce030bf845d5ec4d70a9251b5b36bc9fdd248;hp=3610d2413fbab8f5683b9187e140e086a3418d6e;hb=81c11bdd80190ec319a82b0402173cfb65fcbf72;hpb=7dcd5071e600f8cf48174d1fddb3dba57ec9476d diff --git a/src/libc/malloc.c b/src/libc/malloc.c index 3610d24..363ce03 100644 --- a/src/libc/malloc.c +++ b/src/libc/malloc.c @@ -1,6 +1,6 @@ /* pcboot - bootable PC demo/game kernel -Copyright (C) 2018 John Tsiombikas +Copyright (C) 2018-2019 John Tsiombikas This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -19,20 +19,37 @@ along with this program. If not, see . #include #include #include +#include +#include "config.h" #include "mem.h" #include "panic.h" +#define SINGLE_POOL + struct mem_desc { size_t size; uint32_t magic; +#ifdef MALLOC_DEBUG + uint32_t dbg; +#endif struct mem_desc *next; }; -#define MAGIC 0xdeadf00d +#ifdef MALLOC_DEBUG +static void check_cycles(struct mem_desc *mem); +static void print_pool(void); +#endif + +#define MAGIC_USED 0xdeadf00d +#define MAGIC_FREE 0x1ee7d00d #define DESC_PTR(b) ((void*)((struct mem_desc*)(b) + 1)) #define PTR_DESC(p) ((struct mem_desc*)(p) - 1) +#ifdef SINGLE_POOL +static struct mem_desc *pool; +#else + #define NUM_POOLS 16 #define FIRST_POOL_POW2 5 /* 2**(x+5) size pools: 0->32, 1->64, 2->128 .. 15->1048576 */ @@ -53,6 +70,150 @@ static int pool_index(int sz) } return x - FIRST_POOL_POW2; } +#endif /* !SINGLE_POOL */ + + +#ifdef SINGLE_POOL +#define MIN_BLOCK_SIZE (sizeof(struct mem_desc) * 2) + +void *malloc(size_t sz) +{ + int pg0, npages; + size_t total_sz, rest_sz; + struct mem_desc *mem, *rest, *prev, dummy; + int found = 0; + + total_sz = (sz + sizeof(struct mem_desc) + 3) & 0xfffffffc; + + dummy.next = pool; + prev = &dummy; + while(prev->next) { + mem = prev->next; + /* give the whole block to the allocation if mem->size == total_sz or + * if it's larger, but not large enough to fit another mem_desc in there + * for the new block that we're going to split off + some reasonable + * amount of memory for the new block. + */ + if(mem->size >= total_sz && mem->size < total_sz + MIN_BLOCK_SIZE) { + prev->next = mem->next; + found = 1; + break; + } + /* if we have enough space, split the block and give the upper part + * to the allocation + */ + if(mem->size > total_sz) { + void *ptr = (char*)mem + mem->size - total_sz; + mem->size -= total_sz; + mem = ptr; + found = 1; + break; + } + prev = prev->next; + } + pool = dummy.next; + + if(found) { + mem->size = total_sz; + mem->magic = MAGIC_USED; + mem->next = 0; + return DESC_PTR(mem); + } + + /* did not find a free block, grab a new one */ + npages = BYTES_TO_PAGES(total_sz); + if((pg0 = alloc_ppages(npages, 0)) == -1) { + errno = ENOMEM; + return 0; + } + mem = PAGE_TO_PTR(pg0); + mem->size = total_sz; + mem->next = 0; + mem->magic = MAGIC_USED; + + /* add the rest of the block to pool */ + rest_sz = npages * 4096 - total_sz; + if(rest_sz > 0) { + rest = (struct mem_desc*)((char*)mem + total_sz); + rest->size = rest_sz; + rest->next = 0; + rest->magic = MAGIC_USED; + free(DESC_PTR(rest)); + } + + return DESC_PTR(mem); +} + +void free(void *p) +{ + struct mem_desc *mem, *prev, *cur, dummy; + char *end; + + if(!p) return; + mem = PTR_DESC(p); + + if(mem->magic != MAGIC_USED) { + if(mem->magic == MAGIC_FREE) { + panic("free(%p): double-free\n", p); + } else { + panic("free(%p): corrupted magic (%x)!\n", p, mem->magic); + } + } + mem->magic = MAGIC_FREE; + mem->next = 0; + + /* nothing in the pool, just add this one */ + if(!pool) { + pool = mem; + return; + } + + end = (char*)mem + mem->size; + + dummy.next = pool; + prev = &dummy; + + while(prev->next) { + cur = prev->next; + + /* block starts right at the end of mem: coalesce */ + if((char*)cur == end) { + mem->size += cur->size; + mem->next = cur->next; + cur->magic = 0; + prev->next = mem; + goto done; + } + + /* block starts *after* the end of mem: add in front */ + if((char*)cur > end) { + mem->next = cur; + prev->next = mem; + goto done; + } + + prev = prev->next; + } + + /* our block starts at the end of the last block in the pool: coalesce */ + if((char*)prev + prev->size == (char*)mem) { + mem->magic = 0; + prev->size += mem->size; + goto done; + } + + /* so our block starts after the end of the last block: append */ + prev->next = mem; + +done: + pool = dummy.next; + +#ifdef MALLOC_DEBUG + print_pool(); +#endif +} + +#else /* !SINGLE_POOL */ void *malloc(size_t sz) { @@ -64,12 +225,12 @@ void *malloc(size_t sz) if(total_sz > MAX_POOL_SIZE) { /*printf(" allocation too big, hitting sys_alloc directly\n");*/ - if((pg0 = alloc_ppages(BYTES_TO_PAGES(total_sz))) == -1) { + if((pg0 = alloc_ppages(BYTES_TO_PAGES(total_sz), 0)) == -1) { errno = ENOMEM; return 0; } mem = PAGE_TO_PTR(pg0); - mem->magic = MAGIC; + mem->magic = MAGIC_USED; mem->size = total_sz; mem->next = 0; return DESC_PTR(mem); @@ -94,7 +255,10 @@ void *malloc(size_t sz) add_to_pool(other); } - mem->magic = MAGIC; + if(mem->magic != MAGIC_FREE) { + panic("Trying to allocate range surrounded by an aura of wrong MAGIC\n"); + } + mem->magic = MAGIC_USED; return DESC_PTR(mem); } @@ -103,14 +267,14 @@ void *malloc(size_t sz) /* did not find a free block, add a new one */ pidx = NUM_POOLS - 1; - if((pg0 = alloc_ppages(MAX_POOL_PAGES)) == -1) { + if((pg0 = alloc_ppages(MAX_POOL_PAGES, 0)) == -1) { errno = ENOMEM; return 0; } mem = PAGE_TO_PTR(pg0); mem->size = MAX_POOL_SIZE; mem->next = pools[pidx]; - mem->magic = MAGIC; + mem->magic = MAGIC_FREE; pools[pidx] = mem; /* try again now that there is a free block */ @@ -121,10 +285,17 @@ void *malloc(size_t sz) void free(void *p) { int pg0; - struct mem_desc *mem = PTR_DESC(p); + struct mem_desc *mem; + + if(!p) return; - if(mem->magic != MAGIC) { - panic("free: corrupted magic!\n"); + mem = PTR_DESC(p); + if(mem->magic != MAGIC_USED) { + if(mem->magic == MAGIC_FREE) { + panic("free(%p): double-free\n", p); + } else { + panic("free(%p): corrupted magic (%x)!\n", p, mem->magic); + } } if(mem->size > MAX_POOL_SIZE) { @@ -139,6 +310,8 @@ void free(void *p) add_to_pool(mem); } +#endif /* !def SINGLE_POOL */ + void *calloc(size_t num, size_t size) { @@ -166,11 +339,44 @@ void *realloc(void *ptr, size_t size) if(!(newp = malloc(size))) { return 0; } + memcpy(newp, ptr, mem->size); free(ptr); return newp; } +#ifdef MALLOC_DEBUG +static void check_cycles(struct mem_desc *mem) +{ + static uint32_t dbg = 42; + uint32_t cur_dbg = dbg++; + while(mem) { + if(mem->magic != MAGIC_FREE) { + panic("check_cycles: NON-FREE MAGIC!\n"); + } + if(mem->dbg == cur_dbg) { + panic("CYCLE DETECTED\n"); + } + mem->dbg = cur_dbg; + mem = mem->next; + } +} + +static void print_pool(void) +{ + struct mem_desc *mem = pool; + + printf("DBG: malloc pool:\n"); + while(mem) { + printf(" %p (%ld) [%x]\n", mem, mem->size, mem->magic); + mem = mem->next; + + assert((uint32_t)mem != MAGIC_USED); + } +} +#endif /* MALLOC_DEBUG */ + +#ifndef SINGLE_POOL static int add_to_pool(struct mem_desc *mem) { int pidx; @@ -187,20 +393,22 @@ static int add_to_pool(struct mem_desc *mem) while(iter->next) { pnode = iter->next; if(mem->size == pnode->size) { /* only coalesce same-sized blocks */ - if((char*)mem == (char*)pnode - pnode->size) { + size_t size = mem->size; + + if((char*)mem == (char*)pnode - size) { iter->next = pnode->next; /* unlink pnode */ pools[pidx] = head.next; mem->next = 0; - mem->size += pnode->size; + mem->size += size; /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/ return add_to_pool(mem); } - if((char*)mem == (char*)pnode + pnode->size) { + if((char*)mem == (char*)pnode + size) { iter->next = pnode->next; /* unlink pnode */ pools[pidx] = head.next; pnode->next = 0; - pnode->size += mem->size; + pnode->size += size; /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/ return add_to_pool(pnode); @@ -210,8 +418,13 @@ static int add_to_pool(struct mem_desc *mem) } /* otherwise just add it to the pool */ + mem->magic = MAGIC_FREE; mem->next = pools[pidx]; pools[pidx] = mem; + +#ifdef MALLOC_DEBUG + check_cycles(pools[pidx]); +#endif return 0; } - +#endif /* !def SINGLE_POOL */