summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--buddy.h24
-rw-r--r--magic_buddy.c215
-rw-r--r--main.c12
3 files changed, 133 insertions, 118 deletions
diff --git a/buddy.h b/buddy.h
index c1da8eb..0b4de09 100644
--- a/buddy.h
+++ b/buddy.h
@@ -5,14 +5,22 @@
#define MAGIC_COOKIE_BYTES 32
#define ADDRESS_BITS (8 * sizeof(void*))
-void init_buddy(uint8_t *base, size_t size,
- uint8_t magic[MAGIC_COOKIE_BYTES]);
+struct buddy {
+ uint8_t magic[MAGIC_COOKIE_BYTES];
+ struct free_block *(avail[ADDRESS_BITS]);
+ size_t root_logsize;
+ void *base;
+};
-void *allocate(size_t size);
-void liberate(void *base, size_t size);
+// NOTE: after init_buddy, *state should never move.
+void init_buddy(uint8_t *base, size_t size, uint8_t magic[MAGIC_COOKIE_BYTES],
+ struct buddy *state);
-void debug_buddy(void);
+void *allocate(size_t size, struct buddy *state);
+void liberate(void *base, size_t size, struct buddy *state);
-// "advanced features"
-void *reallocate(void *old, size_t old_size, size_t new_size);
-int reserve(void *start, size_t size);
+void debug_buddy(struct buddy *state);
+
+void *reallocate(void *old, size_t old_size, size_t new_size,
+ struct buddy *state);
+int reserve(void *start, size_t size, struct buddy *state);
diff --git a/magic_buddy.c b/magic_buddy.c
index 93e2ef3..f87ae35 100644
--- a/magic_buddy.c
+++ b/magic_buddy.c
@@ -3,19 +3,13 @@
#include <assert.h>
#include "buddy.h"
-static uint8_t MAGIC[MAGIC_COOKIE_BYTES];
-
-struct free_list {
- struct free_list *next;
- struct free_list **pprev;
+struct free_block {
+ struct free_block *next;
+ struct free_block **pprev;
uint8_t magic[MAGIC_COOKIE_BYTES];
uint8_t logsize;
};
-static struct free_list *(AVAIL[ADDRESS_BITS]);
-static size_t ROOT_LOGSIZE;
-static void *BASE;
-
// 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;
@@ -29,127 +23,131 @@ 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]) {
- BASE = base;
+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);
- ROOT_LOGSIZE = logsize;
+ state->root_logsize = logsize;
- AVAIL[logsize] = (struct free_list *)base;
- AVAIL[logsize]->next = 0;
- AVAIL[logsize]->pprev = &(AVAIL[logsize]);
- memcpy(MAGIC, magic, sizeof(MAGIC));
+ 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_list *buddy_of(struct free_list *block, size_t logsize) {
- size_t virt_block = (size_t)block - (size_t)BASE;
+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*)BASE + virt_buddy);
-}
-
-static int isfree(struct free_list *block) {
- return !memcmp(block->magic, MAGIC, sizeof(MAGIC));
+ return (void*)((uint8_t*)state->base + virt_buddy);
}
// interpret @block as a block at depth @logsize. is it free?
-static int isfree_at_logsize(struct free_list *block, size_t logsize) {
- return isfree(block) && block->logsize == logsize;
+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_list *block) {
- memcpy(block->magic, MAGIC, sizeof(MAGIC));
+static void makefree(struct free_block *block, struct buddy *state) {
+ memcpy(block->magic, state->magic, sizeof(state->magic));
}
-static struct free_list *pop(struct free_list *block) {
+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_list *block, size_t logsize) {
- block->next = AVAIL[logsize];
+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);
- AVAIL[logsize] = block;
- block->pprev = &(AVAIL[logsize]);
+ state->avail[logsize] = block;
+ block->pprev = &(state->avail[logsize]);
block->logsize = 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));
+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_list *parent = _allocate(logsize + 1);
- struct free_list *buddy = buddy_of(parent, logsize);
+ 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, MAGIC, sizeof(MAGIC));
- push(buddy, logsize);
+ memcpy(buddy->magic, state->magic, sizeof(state->magic));
+ push(buddy, logsize, state);
return parent;
}
-void *allocate(size_t size) {
- size = (size < sizeof(struct free_list)) ? sizeof(struct free_list) : size;
- return _allocate(size2log(size, 1));
+void *allocate(size_t size, struct buddy *state) {
+ size = (size < sizeof(struct free_block)) ? sizeof(struct free_block) : size;
+ return _allocate(size2log(size, 1), state);
}
-static void _liberate(struct free_list *block, size_t logsize) {
- push(block, logsize);
- if (logsize == ROOT_LOGSIZE) return;
+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_list *buddy = buddy_of(block, logsize);
- if (!isfree_at_logsize(buddy, logsize)) return;
+ struct free_block *buddy = buddy_of(block, logsize, state);
+ if (!isfree(buddy, logsize, state)) return;
// coalesce up!
- struct free_list *smaller = (buddy < block) ? buddy : block;
- struct free_list *bigger = (buddy < block) ? block : buddy;
+ 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);
+ _liberate(smaller, logsize + 1, state);
}
-void liberate(void *base, size_t size) {
- struct free_list *block = base;
+void liberate(void *base, size_t size, struct buddy *state) {
+ struct free_block *block = base;
memset(block, 0, sizeof(*block));
- makefree(block);
+ makefree(block, state);
- _liberate(block, size2log(size, 1));
+ _liberate(block, size2log(size, 1), state);
}
-void debug_buddy(void) {
- for (size_t i = 0; i <= ROOT_LOGSIZE; i++) {
+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_list *block = AVAIL[i]; block; block = block->next) {
+ for (struct free_block *block = state->avail[i];
+ block; block = block->next)
printf("\t%p\n", block);
- }
}
}
///////// "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;
+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*)BASE + virt_child);
+ 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) {
+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_list *parent = (void*)BASE;
- size_t parent_logsize = ROOT_LOGSIZE;
- while (!isfree_at_logsize(parent, parent_logsize)) {
+ 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_list *rhs_child = rhs_child_of(parent, parent_logsize);
+ 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;
}
@@ -161,42 +159,48 @@ int reserve(void *start, size_t size) {
pop(parent);
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 = ((void*)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;
+ 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 child *can* fit it, so split this parent into two children.
- struct free_list *lhs_child = parent;
- if ((void*)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;
- }
+ // 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) {
- void *new = allocate(new_size);
- if (!new) 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);
+ liberate(old, old_size, state);
return new;
}
-void *reallocate(void *old, size_t old_size, size_t new_size) {
+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;
+
size_t old_logsize = size2log(old_size, 1);
size_t new_logsize = size2log(new_size, 1);
@@ -204,12 +208,13 @@ void *reallocate(void *old, size_t old_size, size_t new_size) {
if (new_logsize < old_logsize) {
// repeatedly split, keeping lhs.
- struct free_list *block = old;
+ struct free_block *block = old;
while (new_logsize < old_logsize) {
old_logsize--;
- struct free_list *right_half = buddy_of(block, old_logsize);
- makefree(right_half);
- push(right_half, 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;
}
@@ -221,16 +226,16 @@ void *reallocate(void *old, size_t old_size, size_t new_size) {
// First, just verify this claim.
size_t pos_logsize = old_logsize;
- if (new_logsize > ROOT_LOGSIZE) return 0;
- struct free_list *pos = old;
+ if (new_logsize > state->root_logsize) return 0;
+ struct free_block *pos = old;
while (pos_logsize != new_logsize) {
- struct free_list *buddy = buddy_of(pos, pos_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);
- } else if (!isfree_at_logsize(buddy, pos_logsize)) {
+ 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);
+ return _naive_reallocate(old, old_size, new_size, state);
}
pos_logsize++;
}
@@ -239,9 +244,9 @@ void *reallocate(void *old, size_t old_size, size_t new_size) {
pos_logsize = old_logsize;
pos = old;
while (pos_logsize != new_logsize) {
- struct free_list *buddy = buddy_of(pos, pos_logsize);
+ struct free_block *buddy = buddy_of(pos, pos_logsize, state);
pop(buddy);
- memset(buddy, 0, sizeof(struct free_list));
+ memset(buddy, 0, sizeof(struct free_block));
pos_logsize++;
}
return old;
diff --git a/main.c b/main.c
index e3b62bd..a288f1c 100644
--- a/main.c
+++ b/main.c
@@ -13,18 +13,20 @@ void get_random(uint8_t *dst, size_t count) {
}
void main() {
+ struct buddy buddy;
+
size_t region_size = 1024 * 1024;
uint8_t magic[MAGIC_COOKIE_BYTES];
get_random(magic, MAGIC_COOKIE_BYTES);
- init_buddy(malloc(region_size), region_size, magic);
+ init_buddy(malloc(region_size), region_size, magic, &buddy);
memset(magic, 0, sizeof(magic));
- void *x = allocate(1024);
+ void *x = allocate(1024, &buddy);
printf("Just allocated %p...\n", x);
- debug_buddy();
+ debug_buddy(&buddy);
printf("Now liberating %p...\n", x);
- liberate(x, 1024);
- debug_buddy();
+ liberate(x, 1024, &buddy);
+ debug_buddy(&buddy);
}
generated by cgit on debian on lair
contact matthew@masot.net with questions or feedback