From 92996a3671732b6c883b325414a1e313786d48d6 Mon Sep 17 00:00:00 2001
From: Matthew Sotoudeh <matthew@masot.net>
Date: Thu, 16 May 2024 15:15:40 -0700
Subject: checker

---
 imc/checker.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)
 create mode 100644 imc/checker.c

(limited to 'imc/checker.c')

diff --git a/imc/checker.c b/imc/checker.c
new file mode 100644
index 0000000..d3f09cc
--- /dev/null
+++ b/imc/checker.c
@@ -0,0 +1,81 @@
+#include <unistd.h>
+#include <sys/fcntl.h>
+#include "libimc.h"
+#include "magic_buddy.h"
+
+// #define verbose(...) printf(__VA_ARGS__)
+#define verbose(...)
+
+void get_random(uint8_t *dst, size_t count) {
+    int fd = open("/dev/urandom", O_RDONLY);
+    assert(count == read(fd, dst, count));
+    close(fd);
+}
+struct ll {
+    size_t data_size;
+    struct ll *next;
+    uint8_t data[];
+};
+
+// basically the simulation described by Knuth on pg 445
+void check_main() {
+    size_t n_timesteps = 10;
+    size_t pool_size = 1024 * 1024 * 1024;
+
+    static void *raw_pool = 0;
+    static struct ll **time_to_dielist = 0;
+    if (!raw_pool)
+        raw_pool = malloc(pool_size + 55);
+    if (!time_to_dielist)
+        time_to_dielist = calloc(n_timesteps + 1, sizeof(struct ll *));
+    else
+        memset(time_to_dielist, 0, (n_timesteps + 1) * sizeof(struct ll *));
+
+    void *pool = raw_pool;
+    if (choose(2, 0)) pool_size += 11;
+    if (choose(2, 0)) pool = (void*)((uint8_t*)pool + 11);
+
+    struct buddy buddy;
+    uint8_t magic[MAGIC_COOKIE_BYTES];
+    get_random(magic, MAGIC_COOKIE_BYTES);
+    init_buddy(pool, pool_size, magic, &buddy);
+
+    size_t size_options[] = {1, 128, 1024, 5, 167, 10500};
+    const size_t n_size_options = sizeof(size_options) / sizeof(size_options[0]);
+
+    for (int t = 0; t < n_timesteps; t++) {
+        // 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++) {
+                verbose("Checking %p->data[%d] = %u versus %u\n",
+                        p, i, (unsigned)p->data[i],
+                        (unsigned)(uint8_t)p->data_size);
+                assert(p->data[i] == (uint8_t)p->data_size);
+            }
+            struct ll *next = p->next;
+            liberate(p, p->data_size + sizeof(struct ll), &buddy);
+            p = next;
+        }
+
+        // try allocating a region
+        size_t size = size_options[choose(n_size_options, 0)];
+        struct ll *ll = allocate(size + sizeof(struct ll), &buddy);
+        if (!ll) continue;
+        assert((void*)ll >= pool);
+        assert((uint8_t*)ll + size + sizeof(struct ll)
+                < (uint8_t*)pool + pool_size);
+
+        ll->data_size = size;
+        for (size_t i = 0; i < ll->data_size; i++) {
+            verbose("Writing %p->data[%d] = %u\n",
+                    ll, i, (unsigned)(uint8_t)size);
+            ll->data[i] = (uint8_t)size;
+        }
+        // pick a death time
+        int lifetime = choose(n_timesteps - t, 0) + 1;
+        ll->next = time_to_dielist[t + lifetime];
+        time_to_dielist[t + lifetime] = ll;
+        verbose("Allocated %p, which should die at time %lu\n",
+                ll, t + lifetime);
+    }
+}
-- 
cgit v1.2.3