From c41f015e77eb37f55a99c5af953a246f91ddef94 Mon Sep 17 00:00:00 2001
From: Matthew Sotoudeh <matthew@masot.net>
Date: Thu, 16 May 2024 20:23:16 -0700
Subject: Grow & shrink model checking

---
 README                    |  4 ++--
 imc/checker.c             | 17 +++++++++++++++--
 magic_buddy/magic_buddy.c | 14 ++++++++++----
 3 files changed, 27 insertions(+), 8 deletions(-)

diff --git a/README b/README
index 72e385e..0717846 100644
--- a/README
+++ b/README
@@ -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;
-- 
cgit v1.2.3