From 54c09d54c0c170f1369751f8bf5a8a0b771a167c Mon Sep 17 00:00:00 2001
From: Matthew Sotoudeh <matthew@masot.net>
Date: Thu, 16 May 2024 14:03:57 -0700
Subject: reorganize

---
 magic_buddy.c | 323 ----------------------------------------------------------
 1 file changed, 323 deletions(-)
 delete mode 100644 magic_buddy.c

(limited to 'magic_buddy.c')

diff --git a/magic_buddy.c b/magic_buddy.c
deleted file mode 100644
index 868bfd7..0000000
--- a/magic_buddy.c
+++ /dev/null
@@ -1,323 +0,0 @@
-#include <stdio.h>
-#include <string.h>
-#include <assert.h>
-#include "buddy.h"
-
-struct free_block {
-    struct free_block *next;
-    struct free_block **pprev;
-    uint8_t magic[MAGIC_COOKIE_BYTES];
-    uint8_t 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],
-                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;
-    size_t virt_buddy = virt_block ^ (1 << logsize);
-    return (void*)((uint8_t*)state->base + virt_buddy);
-}
-
-// interpret @block as a block at depth @logsize. is it free?
-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_block *block, struct buddy *state) {
-    memcpy(block->magic, state->magic, sizeof(state->magic));
-}
-
-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_block *block, size_t logsize,
-                 struct buddy *state) {
-    block->next = state->avail[logsize];
-    if (block->next) block->next->pprev = &(block->next);
-    state->avail[logsize] = block;
-    block->pprev = &(state->avail[logsize]);
-    block->logsize = logsize;
-}
-
-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_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, state->magic, sizeof(state->magic));
-    push(buddy, logsize, state);
-    return parent;
-}
-void *allocate(size_t size, struct buddy *state) {
-    if (size < sizeof(struct free_block)) size = sizeof(struct free_block);
-    return _allocate(size2log(size, 1), state);
-}
-
-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_block *buddy = buddy_of(block, logsize, state);
-    if (!isfree(buddy, logsize, state)) return;
-
-    // coalesce up!
-    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, state);
-}
-
-void liberate(void *base, size_t size, struct buddy *state) {
-    struct free_block *block = base;
-    memset(block, 0, sizeof(*block));
-    makefree(block, state);
-
-    _liberate(block, size2log(size, 1), state);
-}
-
-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)
-            printf("\t%p\n", block);
-    }
-}
-
-///////// "advanced features"
-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*)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, 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_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;
-        if (!parent_logsize--) return 0;
-    }
-    // parent is free!
-    void *parent_end = (void*)((uint8_t*)parent + (1 << parent_logsize));
-    // if the size has no chance of fitting, return 0.
-    if (parent_end < end) return 0;
-    // otherwise, split this parent
-    pop(parent);
-    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 *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 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,
-                               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, state);
-    return new;
-}
-
-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;
-
-    if (size < sizeof(struct free_block)) size = sizeof(struct free_block);
-
-    size_t old_logsize = size2log(old_size, 1);
-    size_t new_logsize = size2log(new_size, 1);
-
-    if (new_logsize == old_logsize) return old;
-
-    if (new_logsize < old_logsize) {
-        // repeatedly split, keeping lhs.
-        struct free_block *block = old;
-        while (new_logsize < old_logsize) {
-            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;
-    }
-
-    // otherwise, we must iterate up the tree and ensure that at each level:
-    // (1) we are the left-buddy, and
-    // (2) our buddy is free.
-    // up until we reach an ancestor of the proper size.
-
-    // First, just verify this claim.
-    size_t pos_logsize = old_logsize;
-    if (new_logsize > state->root_logsize) return 0;
-    struct free_block *pos = old;
-    while (pos_logsize != new_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, 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, state);
-        }
-        pos_logsize++;
-    }
-
-    // Then, revisit the path and coalesce on the way up.
-    pos_logsize = old_logsize;
-    pos = old;
-    while (pos_logsize != new_logsize) {
-        struct free_block *buddy = buddy_of(pos, pos_logsize, state);
-        pop(buddy);
-        memset(buddy, 0, sizeof(struct free_block));
-        pos_logsize++;
-    }
-    return old;
-}
-
-// grow can also be used to move the buddy's data. grow can never fail.
-void grow_buddy(uint8_t *new_base, size_t new_size, struct buddy *state) {
-    // first: make sure all pointers in @state are pointing into @new_base.
-    for (size_t i = 0; i < ADDRESS_BITS; i++) {
-        if (!state->avail[i]) continue;
-        state->avail[i] = (void*)(
-              new_base + ((uint8_t*)state->avail[i] - (uint8_t*)state->base));
-    }
-    state->base = new_base;
-
-    // then, increase the size by 1 repeatedly
-    size_t logsize = size2log(new_size, 0);
-    assert(logsize >= state->root_logsize);
-    if (logsize == state->root_logsize) return;
-    if (isfree((void*)new_base, state->root_logsize, state)) {
-        pop((void*)new_base);
-        push((void*)new_base, state->root_logsize++, state);
-    } else {
-        struct free_block *buddy
-            = buddy_of((void*)new_base, state->root_logsize, state);
-        makefree(buddy, state);
-        push(buddy, state->root_logsize++, state);
-    }
-    return grow_buddy(new_base, new_size, state);
-}
-
-// 0 -> failure
-int shrink_buddy(size_t new_size, struct buddy *state) {
-    // To divide the space in half, we need either:
-    // (1) the root is available, or
-    // (2) the root is split, with the right child being free.
-    // to divide the space by 2^k, we need that property to be true recursively
-    // along the lhs path, until the root itself is free.
-
-    size_t logsize = size2log(new_size, 0);
-
-    // First, just check whether we'll be able to do it:
-    size_t virtual_root_logsize = state->root_logsize;
-    while (virtual_root_logsize > logsize) {
-        if (!isfree(state->base, virtual_root_logsize, state)) {
-            struct free_block *rhs_child
-                = rhs_child_of(state->base, virtual_root_logsize, state);
-            if (!isfree(rhs_child, virtual_root_logsize-1, state))
-                return 0;
-        }
-        virtual_root_logsize--;
-    }
-
-    // It's possible! So go through and actually free the rhs children.
-    while (state->root_logsize > logsize) {
-        if (isfree(state->base, state->root_logsize, state)) break;
-        struct free_block *rhs_child
-            = rhs_child_of(state->base, virtual_root_logsize, state);
-        memset(rhs_child, 0, sizeof(struct free_block));
-        state->root_logsize--;
-    }
-    state->root_logsize = logsize;
-    return 1;
-}
-
-void move_buddy(struct buddy *new_state, struct buddy *old_state) {
-    memcpy(new_state, old_state, sizeof(struct buddy));
-    for (size_t i = 0; i < ADDRESS_BITS; i++) {
-        if (!new_state->avail[i]) continue;
-        new_state->avail[i]->pprev = &(new_state->avail[i]);
-    }
-}
-- 
cgit v1.2.3