From eb0bb6e38beff1517453502f78c1df994e4bb48c Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Thu, 16 May 2024 10:08:06 -0700 Subject: no globals --- buddy.h | 24 ++++--- magic_buddy.c | 215 ++++++++++++++++++++++++++++++---------------------------- main.c | 12 ++-- 3 files changed, 133 insertions(+), 118 deletions(-) diff --git a/buddy.h b/buddy.h index c1da8eb..0b4de09 100644 --- a/buddy.h +++ b/buddy.h @@ -5,14 +5,22 @@ #define MAGIC_COOKIE_BYTES 32 #define ADDRESS_BITS (8 * sizeof(void*)) -void init_buddy(uint8_t *base, size_t size, - uint8_t magic[MAGIC_COOKIE_BYTES]); +struct buddy { + uint8_t magic[MAGIC_COOKIE_BYTES]; + struct free_block *(avail[ADDRESS_BITS]); + size_t root_logsize; + void *base; +}; -void *allocate(size_t size); -void liberate(void *base, size_t size); +// NOTE: after init_buddy, *state should never move. +void init_buddy(uint8_t *base, size_t size, uint8_t magic[MAGIC_COOKIE_BYTES], + struct buddy *state); -void debug_buddy(void); +void *allocate(size_t size, struct buddy *state); +void liberate(void *base, size_t size, struct buddy *state); -// "advanced features" -void *reallocate(void *old, size_t old_size, size_t new_size); -int reserve(void *start, size_t size); +void debug_buddy(struct buddy *state); + +void *reallocate(void *old, size_t old_size, size_t new_size, + struct buddy *state); +int reserve(void *start, size_t size, struct buddy *state); diff --git a/magic_buddy.c b/magic_buddy.c index 93e2ef3..f87ae35 100644 --- a/magic_buddy.c +++ b/magic_buddy.c @@ -3,19 +3,13 @@ #include #include "buddy.h" -static uint8_t MAGIC[MAGIC_COOKIE_BYTES]; - -struct free_list { - struct free_list *next; - struct free_list **pprev; +struct free_block { + struct free_block *next; + struct free_block **pprev; uint8_t magic[MAGIC_COOKIE_BYTES]; uint8_t logsize; }; -static struct free_list *(AVAIL[ADDRESS_BITS]); -static size_t ROOT_LOGSIZE; -static void *BASE; - // log2 of size rounded up (ceil) or down (!ceil) to the nearest power of 2 static size_t size2log(size_t size, int ceil) { int bitcnt = 0; @@ -29,127 +23,131 @@ static size_t size2log(size_t size, int ceil) { return ceil ? 1 : 0; } -void init_buddy(uint8_t *base, size_t size, - uint8_t magic[MAGIC_COOKIE_BYTES]) { - BASE = base; +void init_buddy(uint8_t *base, size_t size, uint8_t magic[MAGIC_COOKIE_BYTES], + struct buddy *state) { + memset(state, 0, sizeof(*state)); + state->base = base; size_t logsize = size2log(size, 0); - ROOT_LOGSIZE = logsize; + state->root_logsize = logsize; - AVAIL[logsize] = (struct free_list *)base; - AVAIL[logsize]->next = 0; - AVAIL[logsize]->pprev = &(AVAIL[logsize]); - memcpy(MAGIC, magic, sizeof(MAGIC)); + state->avail[logsize] = (struct free_block *)base; + state->avail[logsize]->next = 0; + state->avail[logsize]->pprev = &(state->avail[logsize]); + memcpy(state->magic, magic, sizeof(state->magic)); } -static struct free_list *buddy_of(struct free_list *block, size_t logsize) { - size_t virt_block = (size_t)block - (size_t)BASE; +static struct free_block *buddy_of(struct free_block *block, size_t logsize, + struct buddy *state) { + size_t virt_block = (size_t)block - (size_t)state->base; size_t virt_buddy = virt_block ^ (1 << logsize); - return (void*)((uint8_t*)BASE + virt_buddy); -} - -static int isfree(struct free_list *block) { - return !memcmp(block->magic, MAGIC, sizeof(MAGIC)); + return (void*)((uint8_t*)state->base + virt_buddy); } // interpret @block as a block at depth @logsize. is it free? -static int isfree_at_logsize(struct free_list *block, size_t logsize) { - return isfree(block) && block->logsize == logsize; +static int isfree(struct free_block *block, size_t logsize, + struct buddy *state) { + return !memcmp(block->magic, state->magic, sizeof(state->magic)) + && block->logsize == logsize; } -static void makefree(struct free_list *block) { - memcpy(block->magic, MAGIC, sizeof(MAGIC)); +static void makefree(struct free_block *block, struct buddy *state) { + memcpy(block->magic, state->magic, sizeof(state->magic)); } -static struct free_list *pop(struct free_list *block) { +static struct free_block *pop(struct free_block *block) { *(block->pprev) = block->next; if (block->next) block->next->pprev = block->pprev; return block; } -static void push(struct free_list *block, size_t logsize) { - block->next = AVAIL[logsize]; +static void push(struct free_block *block, size_t logsize, + struct buddy *state) { + block->next = state->avail[logsize]; if (block->next) block->next->pprev = &(block->next); - AVAIL[logsize] = block; - block->pprev = &(AVAIL[logsize]); + state->avail[logsize] = block; + block->pprev = &(state->avail[logsize]); block->logsize = logsize; } -static void *_allocate(size_t logsize) { - if (logsize > ROOT_LOGSIZE) return 0; - if (AVAIL[logsize]) { - struct free_list *block = pop(AVAIL[logsize]); - memset(block, 0, sizeof(struct free_list)); +static void *_allocate(size_t logsize, struct buddy *state) { + if (logsize > state->root_logsize) return 0; + if (state->avail[logsize]) { + struct free_block *block = pop(state->avail[logsize]); + memset(block, 0, sizeof(struct free_block)); return block; } - struct free_list *parent = _allocate(logsize + 1); - struct free_list *buddy = buddy_of(parent, logsize); + struct free_block *parent = _allocate(logsize + 1, state); + struct free_block *buddy = buddy_of(parent, logsize, state); // split @parent in half and place the buddy on the avail list. - memcpy(buddy->magic, MAGIC, sizeof(MAGIC)); - push(buddy, logsize); + memcpy(buddy->magic, state->magic, sizeof(state->magic)); + push(buddy, logsize, state); return parent; } -void *allocate(size_t size) { - size = (size < sizeof(struct free_list)) ? sizeof(struct free_list) : size; - return _allocate(size2log(size, 1)); +void *allocate(size_t size, struct buddy *state) { + size = (size < sizeof(struct free_block)) ? sizeof(struct free_block) : size; + return _allocate(size2log(size, 1), state); } -static void _liberate(struct free_list *block, size_t logsize) { - push(block, logsize); - if (logsize == ROOT_LOGSIZE) return; +static void _liberate(struct free_block *block, size_t logsize, + struct buddy *state) { + push(block, logsize, state); + if (logsize == state->root_logsize) return; - struct free_list *buddy = buddy_of(block, logsize); - if (!isfree_at_logsize(buddy, logsize)) return; + struct free_block *buddy = buddy_of(block, logsize, state); + if (!isfree(buddy, logsize, state)) return; // coalesce up! - struct free_list *smaller = (buddy < block) ? buddy : block; - struct free_list *bigger = (buddy < block) ? block : buddy; + struct free_block *smaller = (buddy < block) ? buddy : block; + struct free_block *bigger = (buddy < block) ? block : buddy; pop(bigger); memset(bigger, 0, sizeof(*bigger)); pop(smaller); - _liberate(smaller, logsize + 1); + _liberate(smaller, logsize + 1, state); } -void liberate(void *base, size_t size) { - struct free_list *block = base; +void liberate(void *base, size_t size, struct buddy *state) { + struct free_block *block = base; memset(block, 0, sizeof(*block)); - makefree(block); + makefree(block, state); - _liberate(block, size2log(size, 1)); + _liberate(block, size2log(size, 1), state); } -void debug_buddy(void) { - for (size_t i = 0; i <= ROOT_LOGSIZE; i++) { +void debug_buddy(struct buddy *state) { + for (size_t i = 0; i <= state->root_logsize; i++) { printf("Free blocks at size 2^%lu = %lu:\n", i, 1ul << i); - for (struct free_list *block = AVAIL[i]; block; block = block->next) { + for (struct free_block *block = state->avail[i]; + block; block = block->next) printf("\t%p\n", block); - } } } ///////// "advanced features" -static struct free_list *rhs_child_of(struct free_list *block, size_t logsize) { - size_t virt_block = (size_t)block - (size_t)BASE; +static struct free_block *rhs_child_of(struct free_block *block, size_t logsize, + struct buddy *state) { + size_t virt_block = (size_t)block - (size_t)state->base; size_t virt_child = virt_block | (1 << (logsize - 1)); - return (void*)((uint8_t*)BASE + virt_child); + return (void*)((uint8_t*)state->base + virt_child); } // NOTE: this method is perhaps more complicated than it needs to be because we // take great pains to avoid writing to the region that is being reserved // (e.g., in case it is device MMIO). -int reserve(void *start, size_t size) { +int reserve(void *start, size_t size, struct buddy *state) { assert(size); void *end = (void*)((uint8_t*)start + size); // (1) iterate down to find the first free node to the left of @start - struct free_list *parent = (void*)BASE; - size_t parent_logsize = ROOT_LOGSIZE; - while (!isfree_at_logsize(parent, parent_logsize)) { + struct free_block *parent = (void*)state->base; + size_t parent_logsize = state->root_logsize; + while (!isfree(parent, parent_logsize, state)) { // pick the proper child and recurse - struct free_list *rhs_child = rhs_child_of(parent, parent_logsize); + struct free_block *rhs_child + = rhs_child_of(parent, parent_logsize, state); if ((void*)rhs_child <= start) parent = rhs_child; if (!parent_logsize--) return 0; } @@ -161,42 +159,48 @@ int reserve(void *start, size_t size) { pop(parent); while (1) { // check whether the child could fit it. - struct free_list *rhs_child = rhs_child_of(parent, parent_logsize); - struct free_list *next_child = ((void*)rhs_child <= start) ? parent : rhs_child; - void *child_end = (void*)((uint8_t*)next_child + (1 << (parent_logsize - 1))); - if (child_end < end) { - // the child *cannot* fit it, so allocate this parent. - return 1; + struct free_block *rhs_child + = rhs_child_of(parent, parent_logsize, state); + struct free_block *next_child + = ((void*)rhs_child <= start) ? parent : rhs_child; + void *child_end + = (void*)((uint8_t*)next_child + (1 << (parent_logsize - 1))); + + // if the child *cannot* fit it, stop by leaving this parent allocated. + if (child_end < end) return 1; + + // if the child *can* fit it, split this parent into two children. + struct free_block *lhs_child = parent; + if ((void*)rhs_child <= start) { + // the lhs child will be free + makefree(lhs_child, state); + push(lhs_child, parent_logsize - 1, state); + parent = rhs_child; } else { - // the child *can* fit it, so split this parent into two children. - struct free_list *lhs_child = parent; - if ((void*)rhs_child <= start) { - // the lhs child will be free - makefree(lhs_child); - push(lhs_child, parent_logsize - 1); - parent = rhs_child; - } else { - // the rhs child will be free - makefree(rhs_child); - push(rhs_child, parent_logsize - 1); - parent = lhs_child; - } + // the rhs child will be free + makefree(rhs_child, state); + push(rhs_child, parent_logsize - 1, state); + parent = lhs_child; } parent_logsize--; } return 0; } -static void *_naive_reallocate(void *old, size_t old_size, size_t new_size) { - void *new = allocate(new_size); - if (!new) return 0; +static void *_naive_reallocate(void *old, size_t old_size, size_t new_size, + struct buddy *state) { assert(old_size < new_size); + void *new = allocate(new_size, state); + if (!new) return 0; memcpy(new, old, old_size); - liberate(old, old_size); + liberate(old, old_size, state); return new; } -void *reallocate(void *old, size_t old_size, size_t new_size) { +void *reallocate(void *old, size_t old_size, size_t new_size, + struct buddy *state) { + if (new_size == 0) return liberate(old, old_size, state), (void*)0; + size_t old_logsize = size2log(old_size, 1); size_t new_logsize = size2log(new_size, 1); @@ -204,12 +208,13 @@ void *reallocate(void *old, size_t old_size, size_t new_size) { if (new_logsize < old_logsize) { // repeatedly split, keeping lhs. - struct free_list *block = old; + struct free_block *block = old; while (new_logsize < old_logsize) { old_logsize--; - struct free_list *right_half = buddy_of(block, old_logsize); - makefree(right_half); - push(right_half, old_logsize); + struct free_block *right_half + = buddy_of(block, old_logsize, state); + makefree(right_half, state); + push(right_half, old_logsize, state); } return old; } @@ -221,16 +226,16 @@ void *reallocate(void *old, size_t old_size, size_t new_size) { // First, just verify this claim. size_t pos_logsize = old_logsize; - if (new_logsize > ROOT_LOGSIZE) return 0; - struct free_list *pos = old; + if (new_logsize > state->root_logsize) return 0; + struct free_block *pos = old; while (pos_logsize != new_logsize) { - struct free_list *buddy = buddy_of(pos, pos_logsize); + struct free_block *buddy = buddy_of(pos, pos_logsize, state); if (pos > buddy) { // oh no, we're the right buddy! - return _naive_reallocate(old, old_size, new_size); - } else if (!isfree_at_logsize(buddy, pos_logsize)) { + return _naive_reallocate(old, old_size, new_size, state); + } else if (!isfree(buddy, pos_logsize, state)) { // oh no, our buddy at this level isn't free! - return _naive_reallocate(old, old_size, new_size); + return _naive_reallocate(old, old_size, new_size, state); } pos_logsize++; } @@ -239,9 +244,9 @@ void *reallocate(void *old, size_t old_size, size_t new_size) { pos_logsize = old_logsize; pos = old; while (pos_logsize != new_logsize) { - struct free_list *buddy = buddy_of(pos, pos_logsize); + struct free_block *buddy = buddy_of(pos, pos_logsize, state); pop(buddy); - memset(buddy, 0, sizeof(struct free_list)); + memset(buddy, 0, sizeof(struct free_block)); pos_logsize++; } return old; diff --git a/main.c b/main.c index e3b62bd..a288f1c 100644 --- a/main.c +++ b/main.c @@ -13,18 +13,20 @@ void get_random(uint8_t *dst, size_t count) { } void main() { + struct buddy buddy; + size_t region_size = 1024 * 1024; uint8_t magic[MAGIC_COOKIE_BYTES]; get_random(magic, MAGIC_COOKIE_BYTES); - init_buddy(malloc(region_size), region_size, magic); + init_buddy(malloc(region_size), region_size, magic, &buddy); memset(magic, 0, sizeof(magic)); - void *x = allocate(1024); + void *x = allocate(1024, &buddy); printf("Just allocated %p...\n", x); - debug_buddy(); + debug_buddy(&buddy); printf("Now liberating %p...\n", x); - liberate(x, 1024); - debug_buddy(); + liberate(x, 1024, &buddy); + debug_buddy(&buddy); } -- cgit v1.2.3