From b48327d357e0818d1a6ae2a064cfa7d1567e1242 Mon Sep 17 00:00:00 2001 From: Nicholas Noll Date: Sun, 5 Dec 2021 15:17:44 -0800 Subject: feat(huge): huge refactor (in progress). Commented out libc includes to uncover all explicit dependencies. A large fraction has now been ported over (no testing). I did not port over the command line tools, such as the rc shell. These will be done independently - as of now I just want the library to stand independent. Compilation currently fails due to the lack of math functions. --- src/base/mem/arena.c | 6 +- src/base/mem/interface.c | 4 +- src/base/mem/pool.c | 193 +++++++++++++++++++++++++++++++++++++++++++++++ src/base/mem/pool.h | 66 ++++++++++++++++ src/base/mem/rfind.c | 14 ++++ 5 files changed, 278 insertions(+), 5 deletions(-) create mode 100644 src/base/mem/pool.c create mode 100644 src/base/mem/pool.h create mode 100644 src/base/mem/rfind.c (limited to 'src/base/mem') diff --git a/src/base/mem/arena.c b/src/base/mem/arena.c index 7fe036a..cb1af74 100644 --- a/src/base/mem/arena.c +++ b/src/base/mem/arena.c @@ -26,13 +26,13 @@ struct mem·Arena }; static void* -·arenaalloc(void *heap, uint n, ulong size) +·arenaalloc(void *heap, long n, uintptr size) { return mem·arenaalloc(heap, n, size); } static void* -·arenarealloc(void *heap, void *old, uint n, ulong size) +·arenarealloc(void *heap, void *old, long n, uintptr size) { /* does not free */ return mem·arenaalloc(heap, n, size); @@ -99,7 +99,7 @@ mem·freearena(mem·Arena *a) } void* -mem·arenaalloc(mem·Arena *a, uint n, ulong size) +mem·arenaalloc(mem·Arena *a, long n, uintptr size) { if(!n) { return nil; diff --git a/src/base/mem/interface.c b/src/base/mem/interface.c index 99cb774..aa76c85 100644 --- a/src/base/mem/interface.c +++ b/src/base/mem/interface.c @@ -11,12 +11,12 @@ static void * } static void * -·calloc(void *_, uint n, ulong size) { +·calloc(void *_, long n, ulong size) { return calloc(n, size); } static void * -·realloc(void *_, void *ptr, uint n, ulong size) { +·realloc(void *_, void *ptr, long n, ulong size) { return realloc(ptr, n*size); } diff --git a/src/base/mem/pool.c b/src/base/mem/pool.c new file mode 100644 index 0000000..bf6f2b5 --- /dev/null +++ b/src/base/mem/pool.c @@ -0,0 +1,193 @@ +#include +#include + +#include "pool.h" + +// ----------------------------------------------------------------------- +// globals/macros + +#define NOMAGIC 0xDEADFA11u +#define DEADMAGIC 0xDEADDEADu +#define TAILMAGIC0 0xBEu +#define TAILMAGIC1 0xEFu +#define FREEMAGIC 0xBA5EBA11u +#define USEDMAGIC 0x0A110C09u +#define UNUSEDMAGIC (0xCAB00D1Eu+1) +#define COREMAGIC (0xC0A1E5CEu+1) +#define CORETAILMAGIC (0xEC5E1A0Cu+1) +#define ALIGNMAGIC 0xA1F1D1C1u + +#define POISON ((void*)0xCAFEBABEu) + +// ----------------------------------------------------------------------- +// hunk maintenance + +#define HUNKTAIL(h) ((Tail*)((uchar*)(h)+(h)->size-sizeof(Tail))) + +static uintptr +gethunksize(mem·Pool *pool, uintptr size) +{ + size += sizeof(Head) + sizeof(Tail); + if(size < pool->minhunk) + size = pool->minhunk; + size = (size+pool->quantum) & ~(pool->quantum-1); // aligns to quantum + return size; +} + +static Head * +sethunksize(Head *h, uintptr size) +{ + Tail *t; + + assert(h->magic != FREEMAGIC); + + h->size = size; + + t = HUNKTAIL(h); + t->size = size; + t->magic0 = TAILMAGIC0; + t->magic1 = TAILMAGIC1; + + return h; +} + +static void +checkhunk(mem·Pool *p, Head *h) +{ + switch(h->magic){ + default: + abort(); + case FREEMAGIC: + case UNUSEDMAGIC: + case DEADMAGIC: + case COREMAGIC: + case CORETAILMAGIC: + case USEDMAGIC: + ; + } +} + +// ----------------------------------------------------------------------- +// core maintenance + +#define COREHEAD(c) ((Head*)((uchar*)(c)+(c)->len -sizeof(Head))) + +static uintptr +getcoresize(mem·Pool *pool, uintptr size) +{ + size += sizeof(Core) + sizeof(Tail); + if(size < pool->mincore) + size = pool->mincore; + size = (size+pool->quantum) & ~(pool->quantum-1); + return size; +} + +static Core * +setcoresize(Core *c, uintptr size) +{ + Head *h; + + c->len = size; + + h = COREHEAD(c); + h->size = 0; + h->magic = CORETAILMAGIC; + + return c; +} + +static void +newcore(mem·Pool *pool, uintptr size) +{ + Core *c; + + // XXX: check for size overflow + + if(!(c = pool->mem.alloc(pool->heap, 1, size))) + return; + + pool->cursize += size; + + /* core header */ + c->magic = COREMAGIC; + sethunksize((Head*)c, sizeof(Core)); + setcoresize(c, size); + checkhunk(pool, (Head*)c); +} + +// ----------------------------------------------------------------------- +// free list maintenance + +static Free * +findgreater(Free *root, uintptr size) +{ + Free *last; + + last = nil; + for(;;){ + if(!root) + return last; + if(size == root->size) + return root; + if(size < root->size){ + last = root; + root = root->left; + }else + root = root->right; + } +} + +// ----------------------------------------------------------------------- +// exported functions + +/* constructors / destructors */ +mem·Pool* +mem·makepool(mem·Allocator mem, void *heap, char *name, int flags, intptr maxsize, intptr mincore) +{ + mem·Pool *pool = mem.alloc(heap, 1, sizeof(*pool)); + mem·set(pool, sizeof(*pool), 0); + + pool->mem = mem; + pool->heap = heap; + pool->name = name; + pool->flags = flags; + pool->mincore = mincore; + pool->maxsize = maxsize; + + return pool; +} + +void +mem·freepool(mem·Pool *pool) +{ + void *heap = pool->heap; + mem·Allocator mem = pool->mem; + + mem.free(heap, pool); +} + +/* base functions */ + +void * +mem·poolalloc(mem·Pool *pool, long n, uintptr eltsize) +{ + Free *node; + uintptr size, bksz; + + if((size = n*eltsize) >= 0x80000000UL){ + errorf("allocation overflow"); + return nil; + } + + bksz = gethunksize(pool, size); + node = findgreater(pool->free, bksz); + if(!node){ + newcore(pool, getcoresize(pool, bksz)); + if(!(node = findgreater(pool->free, bksz))) + return nil; + } + + + + return nil; +} diff --git a/src/base/mem/pool.h b/src/base/mem/pool.h new file mode 100644 index 0000000..d5e9952 --- /dev/null +++ b/src/base/mem/pool.h @@ -0,0 +1,66 @@ +#pragma once + +typedef struct Head Head; +typedef struct Tail Tail; +typedef struct Free Free; +typedef struct Used Used; +typedef struct Core Core; + +struct Head +{ + ulong magic; + ulong size; +}; + +struct Tail +{ + ulong magic0; + uchar datasize[2]; + ulong magic1; + ulong size; +}; + +struct Free +{ + Head; + Free *left, *right; + Free *next, *prev; +}; + +struct Used +{ + Head; +}; + +struct Core +{ + Head; + Core *up, *down; + ulong len, pad; +}; + +struct mem·Pool +{ + char *name; + ulong maxsize; + + void *heap; + mem·Allocator mem; + + ulong cursize; + ulong curfree; + ulong curused; + + ulong mincore; /* smallest size of new core */ + ulong quantum; /* allocated hunks should be multiple of */ + ulong minhunk; /* smallest newly allocated hunk */ + + Free *free; + Core *core; + + int flags; + int nfree; + int lastcompact; + + void* private; +}; diff --git a/src/base/mem/rfind.c b/src/base/mem/rfind.c new file mode 100644 index 0000000..ed45086 --- /dev/null +++ b/src/base/mem/rfind.c @@ -0,0 +1,14 @@ +#include "internal.h" + +void * +mem·rfindc(void *addr, uintptr len, int c) +{ + char *s = addr; + c = (uchar)c; + + while(len--){ + if(s[len]==c) + return(s+len); + } + return nil; +} -- cgit v1.2.1