From affa5e2933186970d0a3dac38d2ca8f02190e4d9 Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Wed, 15 May 2024 20:15:45 -0700 Subject: basic magic buddy allocator --- .gitignore | 3 ++ Makefile | 14 +++++++ README | 28 ++++++++++++++ buddy.h | 14 +++++++ magic_buddy.c | 119 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ main.c | 39 +++++++++++++++++++ 6 files changed, 217 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 README create mode 100644 buddy.h create mode 100644 magic_buddy.c create mode 100644 main.c diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..29c963b --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +.*.sw* +.sw* +build diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..22c011a --- /dev/null +++ b/Makefile @@ -0,0 +1,14 @@ +.PHONY: all clean + +CFLAGS += -g +CFLAGS += -O3 +CFLAGS += -fsanitize=address + +all: build/magic + +build/magic: main.c magic_buddy.c + @ mkdir -p build + $(CC) $(CFLAGS) $^ -o $@ + +clean: + rm -rf build diff --git a/README b/README new file mode 100644 index 0000000..bf7dbcb --- /dev/null +++ b/README @@ -0,0 +1,28 @@ +### Magic Buddy + +Traditional optimized buddy allocators (see Knuth Vol 1) require at least 1 +extra bit on each allocation region. + +But this means (as Akshay Srivatsan pointed out to me recently) that an +allocation of size 2^k will cause an actual allocation of size 2^k + 1/8, +rounds up to 2^{k+1} because buddy allocators can only allocate in +powers-of-two byte amounts. This is wasteful. + +Instead, this repo has a buddy allocator that requires no extra allocation +overhead. It stores the "freed-or-not bit" implicitly: a block is considered +freed iff its first 512 bits is some magic cookie value determined randomly and +kept secret from the application. + +The only sources of memory overhead are: + + 1. Fragmentation from allocations being forced to be powers of 2 + + 2. Fragmentation from a (rather large) minimum allowed allocation size of + ~64+16 bytes. + +But it retains the nice property of buddy allocators that liberation is linear +in the computer's address size. + +### License + +AGPLv3 diff --git a/buddy.h b/buddy.h new file mode 100644 index 0000000..b335019 --- /dev/null +++ b/buddy.h @@ -0,0 +1,14 @@ +#pragma once +#include +#include + +#define MAGIC_COOKIE_BYTES 64 +#define ADDRESS_BITS (8 * sizeof(void*)) + +void init_buddy(uint8_t *base, size_t size, + uint8_t magic[MAGIC_COOKIE_BYTES]); + +void *allocate(size_t size); +void liberate(void *base, size_t size); + +void debug_buddy(void); diff --git a/magic_buddy.c b/magic_buddy.c new file mode 100644 index 0000000..52cf764 --- /dev/null +++ b/magic_buddy.c @@ -0,0 +1,119 @@ +#include +#include +#include +#include "buddy.h" + +static uint8_t MAGIC[MAGIC_COOKIE_BYTES]; + +struct free_list { + uint8_t magic[MAGIC_COOKIE_BYTES]; + struct free_list *next; + struct free_list **pprev; +}; + +static struct free_list *(AVAIL[ADDRESS_BITS]); +static size_t ROOT_LOGSIZE; + +// 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; + for (int i = 0; size; i++) { + bitcnt += size & 1; + size >>= 1; + if (size) continue; + if (ceil) return (bitcnt > 1) ? (i + 1) : i; + return i; + } + return ceil ? 1 : 0; +} + +void init_buddy(uint8_t *base, size_t size, + uint8_t magic[MAGIC_COOKIE_BYTES]) { + size_t logsize = size2log(size, 0); + ROOT_LOGSIZE = logsize; + assert(((size_t)base & ((1 << logsize) - 1)) == 0); + AVAIL[logsize] = (struct free_list *)base; + AVAIL[logsize]->next = 0; + AVAIL[logsize]->pprev = &(AVAIL[logsize]); + memcpy(&MAGIC, &magic, sizeof(MAGIC)); +} + +static struct free_list *buddy_of(struct free_list *block, size_t logsize) { + return (void *)((size_t)block ^ (1 << logsize)); +} + +static int isfree(struct free_list *block) { + return !memcmp(block->magic, MAGIC, sizeof(MAGIC)); +} + +static void makefree(struct free_list *block) { + memcpy(block->magic, MAGIC, sizeof(MAGIC)); +} + +static struct free_list *pop(struct free_list *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]; + if (block->next) block->next->pprev = &(block->next); + AVAIL[logsize] = block; + block->pprev = &(AVAIL[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)); + return block; + } + + struct free_list *parent = _allocate(logsize + 1); + struct free_list *buddy = buddy_of(parent, logsize); + // split @parent in half and place the buddy on the avail list. + memcpy(buddy->magic, MAGIC, sizeof(MAGIC)); + push(buddy, logsize); + return parent; +} +void *allocate(size_t size) { + size = (size < sizeof(struct free_list)) ? sizeof(struct free_list) : size; + return _allocate(size2log(size, 1)); +} + +static void _liberate(struct free_list *block, size_t logsize) { + push(block, logsize); + if (logsize == ROOT_LOGSIZE) return; + + struct free_list *buddy = buddy_of(block, logsize); + if (!isfree(buddy)) return; + + // coalesce up! + struct free_list *smaller = (buddy < block) ? buddy : block; + struct free_list *bigger = (buddy < block) ? block : buddy; + pop(bigger); + memset(bigger, 0, sizeof(*bigger)); + + pop(smaller); + + _liberate(smaller, logsize + 1); +} + +void liberate(void *base, size_t size) { + struct free_list *block = base; + memset(block, 0, sizeof(*block)); + makefree(block); + + _liberate(block, size2log(size, 1)); +} + +void debug_buddy(void) { + for (size_t i = 0; i <= 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) { + printf("\t%p\n", block); + } + } +} diff --git a/main.c b/main.c new file mode 100644 index 0000000..b84e958 --- /dev/null +++ b/main.c @@ -0,0 +1,39 @@ +#include "buddy.h" +#include +#include +#include +#include +#include +#include + +void get_random(uint8_t *dst, size_t count) { + int fd = open("/dev/urandom", O_RDONLY); + assert(count == read(fd, dst, count)); + close(fd); +} + +// helper for getting an aligned allocation +static void *malloc_aligned(size_t size) { + uint8_t *data = malloc(size); + if (!((size_t)data % size)) return data; + data = realloc(data, size * 2); + data = data + (size - ((size_t)data % size)); + return data; +} + +void main() { + size_t region_size = 1024 * 1024; + + uint8_t magic[MAGIC_COOKIE_BYTES]; + get_random(magic, MAGIC_COOKIE_BYTES); + init_buddy(malloc_aligned(region_size), region_size, magic); + memset(magic, 0, sizeof(magic)); + + void *x = allocate(1024); + printf("Just allocated %p...\n", x); + debug_buddy(); + + printf("Now liberating %p...\n", x); + liberate(x, 1024); + debug_buddy(); +} -- cgit v1.2.3