diff options
| -rw-r--r-- | README | 4 | ||||
| -rw-r--r-- | imc/checker.c | 17 | ||||
| -rw-r--r-- | magic_buddy/magic_buddy.c | 14 |
3 files changed, 27 insertions, 8 deletions
@@ -67,8 +67,8 @@ Current status of the test harness(es): - [X] reallocate - [X] move_buddy - [X] reserve - - [ ] grow_buddy - - [ ] shrink_buddy + - [X] grow_buddy + - [X] shrink_buddy ### Usage diff --git a/imc/checker.c b/imc/checker.c index 2ddf978..a7f62ff 100644 --- a/imc/checker.c +++ b/imc/checker.c @@ -20,7 +20,8 @@ struct ll { // basically the simulation described by Knuth on pg 445 void check_main() { size_t n_timesteps = 10; - size_t pool_size = 1024 * 1024 * 1024; + size_t real_pool_size = 1024 * 1024 * 1024; + size_t pool_size = real_pool_size; static void *raw_pool = 0; static struct ll **time_to_dielist = 0; @@ -66,6 +67,18 @@ void check_main() { curr_buddy = &buddy2; } + int shrink_grow_nop = choose(3, 0); + if (shrink_grow_nop == 0) { + if (shrink_buddy(pool_size / 2, curr_buddy)) + pool_size = pool_size / 2; + assert(pool_size); + } else if (shrink_grow_nop == 1) { + if ((2 * pool_size) <= real_pool_size) { + pool_size *= 2; + grow_buddy(pool, pool_size, curr_buddy); + } + } + // free the regions at this timestep, and ensure its contents are good for (struct ll *p = time_to_dielist[t]; p;) { for (size_t i = 0; i < p->data_size; i++) { @@ -114,7 +127,7 @@ void check_main() { assert((void*)ll >= pool); assert((uint8_t*)ll + size + sizeof(struct ll) - < (uint8_t*)pool + pool_size); + <= (uint8_t*)pool + pool_size); ll->data_size = size; for (size_t i = 0; i < ll->data_size; i++) { diff --git a/magic_buddy/magic_buddy.c b/magic_buddy/magic_buddy.c index 6f9851b..f3dac00 100644 --- a/magic_buddy/magic_buddy.c +++ b/magic_buddy/magic_buddy.c @@ -78,6 +78,7 @@ static void *_allocate(size_t logsize, struct buddy *state) { memset(block, 0, sizeof(struct free_block)); return block; } + if (logsize == state->root_logsize) return 0; struct free_block *parent = _allocate(logsize + 1, state); struct free_block *buddy = buddy_of(parent, logsize, state); @@ -298,6 +299,7 @@ int shrink_buddy(size_t new_size, struct buddy *state) { // along the lhs path, until the root itself is free. size_t logsize = size2log(new_size, 0); + if ((1 << logsize) <= sizeof(struct free_block)) return 0; // First, just check whether we'll be able to do it: size_t virtual_root_logsize = state->root_logsize; @@ -313,10 +315,14 @@ int shrink_buddy(size_t new_size, struct buddy *state) { // 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)); + if (isfree(state->base, state->root_logsize, state)) { + pop(state->base); + push(state->base, state->root_logsize - 1, state); + } else { + struct free_block *rhs_child + = rhs_child_of(state->base, state->root_logsize, state); + memset(rhs_child, 0, sizeof(struct free_block)); + } state->root_logsize--; } state->root_logsize = logsize; |