basic magic buddy allocator

6 files changed, 217 insertions, 0 deletions

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 <stdint.h>
+#include <stddef.h>
+
+#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 <stdio.h>
+#include <string.h>
+#include <assert.h>
+#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 <stdlib.h>
+#include <string.h>
+#include <fcntl.h>
+#include <assert.h>
+#include <unistd.h>
+#include <stdio.h>
+
+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();
+}