diff options
| -rw-r--r-- | README | 2 | ||||
| -rw-r--r-- | imc/checker.c | 15 | ||||
| -rw-r--r-- | magic_buddy/magic_buddy.c | 42 |
3 files changed, 41 insertions, 18 deletions
@@ -66,7 +66,7 @@ Current status of the test harness(es): - [X] liberate - [X] reallocate - [X] move_buddy - - [ ] reserve + - [X] reserve - [ ] grow_buddy - [ ] shrink_buddy diff --git a/imc/checker.c b/imc/checker.c index 2bde59f..2ddf978 100644 --- a/imc/checker.c +++ b/imc/checker.c @@ -42,6 +42,17 @@ void check_main() { get_random(magic, MAGIC_COOKIE_BYTES); init_buddy(pool, pool_size, magic, curr_buddy); + void *redzone_start = 0; + void *redzone_end = 0; + if (choose(2, 0)) { + redzone_start = (uint8_t*)pool + 1365; + redzone_end = (uint8_t*)redzone_start + (1024 * 2); + verbose("Reserving %p -- %p\n", redzone_start, redzone_end); + assert(reserve(redzone_start, + (uint8_t*)redzone_end - (uint8_t*)redzone_start, + curr_buddy)); + } + size_t size_options[] = {1, 128, 1024, 5, 167, 10500}; const size_t n_size_options = sizeof(size_options) / sizeof(size_options[0]); @@ -82,6 +93,7 @@ void check_main() { p->data_size = size_options[action]; size_t new_size = p->data_size + sizeof(struct ll); p = reallocate(p, new_size, old_size, curr_buddy); + assert(!(redzone_start <= (void*)p && (void*)p < redzone_end)); for (size_t i = 0; i < p->data_size; i++) p->data[i] = (uint8_t)p->data_size; int lifetime = choose(n_timesteps - t, 0) + 1; @@ -97,6 +109,9 @@ void check_main() { size_t size = size_options[choose(n_size_options, 0)]; struct ll *ll = allocate(size + sizeof(struct ll), curr_buddy); if (!ll) continue; + verbose("Got allocation: %p\n", ll); + assert(!(redzone_start <= (void*)ll && (void*)ll < redzone_end)); + assert((void*)ll >= pool); assert((uint8_t*)ll + size + sizeof(struct ll) < (uint8_t*)pool + pool_size); 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, |