From 2e7e1c12a74c64c1f908e7f071af8d2286537e95 Mon Sep 17 00:00:00 2001
From: Matthew Sotoudeh <matthew@masot.net>
Date: Thu, 16 May 2024 19:31:52 -0700
Subject: check "reserve", fix bugs

---
 magic_buddy/magic_buddy.c | 42 +++++++++++++++++++++++++-----------------
 1 file changed, 25 insertions(+), 17 deletions(-)

(limited to 'magic_buddy/magic_buddy.c')

diff --git a/magic_buddy/magic_buddy.c b/magic_buddy/magic_buddy.c
index 9deaa8f..6f9851b 100644
--- a/magic_buddy/magic_buddy.c
+++ b/magic_buddy/magic_buddy.c
@@ -23,20 +23,6 @@ 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],
-                struct buddy *state) {
-    memset(state, 0, sizeof(*state));
-    state->base = base;
-
-    size_t logsize = size2log(size, 0);
-    state->root_logsize = logsize;
-
-    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_block *buddy_of(struct free_block *block, size_t logsize,
                                    struct buddy *state) {
     size_t virt_block = (size_t)block - (size_t)state->base;
@@ -70,6 +56,21 @@ static void push(struct free_block *block, size_t logsize,
     block->logsize = logsize;
 }
 
+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);
+    state->root_logsize = logsize;
+
+    memcpy(state->magic, magic, sizeof(state->magic));
+
+    memset(base, 0, sizeof(struct free_block));
+    makefree((void*)base, state);
+    push((void*)base, logsize, state);
+}
+
 static void *_allocate(size_t logsize, struct buddy *state) {
     if (logsize > state->root_logsize) return 0;
     if (state->avail[logsize]) {
@@ -121,8 +122,10 @@ 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_block *block = state->avail[i];
-                block; block = block->next)
+                block; block = block->next) {
+            assert(isfree(block, block->logsize, state));
             printf("\t%p\n", block);
+        }
     }
 }
 
@@ -144,11 +147,13 @@ int reserve(void *start, size_t size, struct buddy *state) {
     // (1) iterate down to find the first free node to the left of @start
     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_block *rhs_child
             = rhs_child_of(parent, parent_logsize, state);
         if ((void*)rhs_child <= start) parent = rhs_child;
+        // TODO: make sure they don't try to reserve below the min size here?
         if (!parent_logsize--) return 0;
     }
     // parent is free!
@@ -157,12 +162,15 @@ int reserve(void *start, size_t size, struct buddy *state) {
     if (parent_end < end) return 0;
     // otherwise, split this parent
     pop(parent);
+    // TODO: any way to avoid this write? wouldn't be necessary if we're on the
+    // rhs of the parent ...
+    memset(parent, 0, sizeof(struct free_block));
     while (1) {
         // check whether the child could fit it.
         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*)rhs_child <= start) ? rhs_child : parent;
         void *child_end
             = (void*)((uint8_t*)next_child + (1 << (parent_logsize - 1)));
 
@@ -184,7 +192,7 @@ int reserve(void *start, size_t size, struct buddy *state) {
         }
         parent_logsize--;
     }
-    return 0;
+    assert(!"unreachable");
 }
 
 static void *_naive_reallocate(void *old, size_t old_size, size_t new_size,
-- 
cgit v1.2.3