attempt at a preallocation feature

3 files changed, 71 insertions, 2 deletions

diff --git a/README b/README
index 627e531..ed6ef3b 100644
--- a/README
+++ b/README
@@ -25,8 +25,7 @@ Caveats are:
 
     4. We do not (yet) support some common allocator features, including
        realloc and reserving a specific subregion (e.g., device MMIO
-       addresses). We expect to support these soon, although they may require
-       adding an extra ~8 bytes to the minimum allocation size.
+       addresses).
 
     5. Some advanced allocator features, e.g., iterating over allocated regions
        or attempting to dynamically improve cache locality, are not supported.
diff --git a/buddy.h b/buddy.h
index 8a2ccac..45e62a7 100644
--- a/buddy.h
+++ b/buddy.h
@@ -12,3 +12,7 @@ void *allocate(size_t size);
 void  liberate(void *base, size_t size);
 
 void debug_buddy(void);
+
+// "advanced features"
+void *reallocate(void *old, size_t old_size, size_t new_size);
+void preallocate(void *start, size_t size);
diff --git a/magic_buddy.c b/magic_buddy.c
index a4874fe..4529e7d 100644
--- a/magic_buddy.c
+++ b/magic_buddy.c
@@ -122,3 +122,69 @@ void debug_buddy(void) {
         }
     }
 }
+
+///////// "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;
+    size_t virt_child = virt_block | (1 << (logsize - 1));
+    return (void*)((uint8_t*)BASE + virt_buddy);
+}
+
+// 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 preallocated
+// (e.g., in case it is device MMIO).
+int preallocate(void *start, size_t size) {
+    assert(size);
+    void *end = (void*)((uint8_t*)start + size);
+
+    // (1) check if BASE itself is a free node
+    struct free_list *parent = (void*)BASE;
+    size_t parent_logsize = ROOT_LOGSIZE;
+    while (!isfree(parent)) {
+        // pick the proper child and recurse
+        struct free_list *rhs_child = rhs_child_of(parent, parent_logsize);
+        if (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, parent_logsize);
+    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 = (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;
+        } else {
+            // the child *can* fit it, so split this parent into two children.
+            struct free_list *lhs_child = parent;
+            if (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;
+            }
+        }
+        parent_logsize--;
+    }
+    return 0;
+}
+
+void *reallocate(void *old, size_t old_size, size_t new_size) {
+    // if new_size < old_size, repeatedly split ourself. TODO: does this mess
+    // with fragmentation?
+
+    // otherwise, basically identical to preallocate, except what we want to
+    // allocate is roughly @old + old_size (with proper rounding to
+    // boundaries).
+}