Add mem allocator, remove listpool.

2 files changed, 417 insertions, 0 deletions

diff --git a/mem/test/mem_test.c b/mem/test/mem_test.c
new file mode 100644
index 0000000..6ab4c7c
--- /dev/null
+++ b/mem/test/mem_test.c
@@ -0,0 +1,232 @@
+#include "mem.h"
+
+#include "test.h"
+
+#define NUM_BLOCKS 10
+
+DEF_MEM(test_mem, int, NUM_BLOCKS);
+
+static int count(test_mem* mem) {
+  int count = 0;
+  mem_foreach(mem, n, { count++; });
+  return count;
+}
+
+static int sum(test_mem* mem) {
+  int sum = 0;
+  mem_foreach(mem, n, { sum += *n; });
+  return sum;
+}
+
+// Create a statically-backed allocator.
+TEST_CASE(mem_create) {
+  test_mem mem;
+  mem_make(&mem);
+}
+
+// Create a dynamically-backed allocator.
+TEST_CASE(mem_create_dyn) {
+  DEF_MEM_DYN(dyn_mem, int);
+  
+  dyn_mem mem;
+  mem_make_dyn(&mem, NUM_BLOCKS, sizeof(int));
+}
+
+// Allocate N chunks of 1 block each.
+TEST_CASE(mem_fully_allocate) {
+  test_mem mem;
+  mem_make(&mem);
+
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    const int* block = mem_alloc(&mem, 1);
+    TEST_TRUE(block != 0);
+  }
+}
+
+// Allocate N chunks of 1 block each, then free them.
+TEST_CASE(mem_fill_then_free) {
+  test_mem mem;
+  mem_make(&mem);
+
+  int* blocks[NUM_BLOCKS] = {0};
+  for (int i = 0; i < NUM_BLOCKS; i++) {
+    blocks[i] = mem_alloc(&mem, 1);
+    TEST_TRUE(blocks[i] != 0);
+  }
+
+  for (int i = 0; i < NUM_BLOCKS; i++) {
+    mem_free(&mem, &blocks[i]);
+    TEST_EQUAL(blocks[i], 0); // Pointer should be set to 0 on free.
+  }
+
+  TEST_EQUAL(count(&mem), 0);
+}
+
+// Attempt to allocate blocks past the maximum allocator size.
+// The allocator should handle the failed allocations gracefully.
+TEST_CASE(mem_allocate_beyond_max_size) {
+  test_mem mem;
+  mem_make(&mem);
+
+  // Fully allocate the mem.
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    TEST_TRUE(mem_alloc(&mem, 1) != 0);
+  }
+
+  // Past the end.
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    TEST_EQUAL(mem_alloc(&mem, 1), 0);
+  }
+}
+
+// Free blocks should always remain zeroed out.
+// This tests the invariant right after creating the allocator.
+TEST_CASE(mem_zero_free_blocks_after_creation) {
+  test_mem mem;
+  mem_make(&mem);
+
+  const int zero = 0;
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    const int* block = (const int*)(mem.blocks) + i;
+    TEST_EQUAL(memcmp(block, &zero, sizeof(int)), 0);
+  }
+}
+
+// Free blocks should always remain zeroed out.
+// This tests the invariant after freeing a block.
+TEST_CASE(mem_zero_free_block_after_free) {
+  test_mem mem;
+  mem_make(&mem);
+
+  int* val = mem_alloc(&mem, 1);
+  TEST_TRUE(val != 0);
+  *val = 177;
+
+  int* old_val = val;
+  mem_free(&mem, &val);    // val pointer is set to 0.
+  TEST_EQUAL(*old_val, 0); // Block is zeroed out after free.
+}
+
+// Traverse an empty allocator.
+TEST_CASE(mem_traverse_empty) {
+  test_mem mem;
+  mem_make(&mem);
+
+  TEST_EQUAL(count(&mem), 0);
+}
+
+// Traverse a partially full allocator.
+TEST_CASE(mem_traverse_partially_full) {
+  const int N = NUM_BLOCKS / 2;
+
+  test_mem mem;
+  mem_make(&mem);
+
+  for (int i = 0; i < N; ++i) {
+    int* val = mem_alloc(&mem, 1);
+    TEST_TRUE(val != 0);
+    *val = i + 1;
+  }
+
+  TEST_EQUAL(sum(&mem), (N) * (N + 1) / 2);
+}
+
+// Traverse a full allocator.
+TEST_CASE(mem_traverse_full) {
+  test_mem mem;
+  mem_make(&mem);
+
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    int* val = mem_alloc(&mem, 1);
+    TEST_TRUE(val != 0);
+    *val = i + 1;
+  }
+
+  TEST_EQUAL(sum(&mem), (NUM_BLOCKS) * (NUM_BLOCKS + 1) / 2);
+}
+
+// Get the ith (allocated) chunk.
+TEST_CASE(mem_get_block) {
+  test_mem mem;
+  mem_make(&mem);
+
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    int* block = mem_alloc(&mem, 1);
+    TEST_TRUE(block != 0);
+    *block = i;
+    TEST_EQUAL(mem_get_chunk_handle(&mem, block), (size_t)i);
+  }
+
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    TEST_EQUAL(*mem_get_chunk(&mem, i), i);
+  }
+}
+
+// Test merging.
+// 1. Allocate chunks of variable sizes.
+// 2. Free them in a different order.
+// 3. Then we should be able to allocate 1 chunk of N blocks.
+TEST_CASE(mem_fragmentation) {
+  test_mem mem;
+  mem_make(&mem);
+
+  int* blocks[NUM_BLOCKS] = {0};
+  int  next_block         = 0;
+
+#define ALLOC(num_blocks)                           \
+  blocks[next_block] = mem_alloc(&mem, num_blocks); \
+  TEST_TRUE(blocks[next_block] != 0);               \
+  next_block++;
+
+#define FREE(block_idx) mem_free(&mem, &blocks[block_idx])
+
+  // 5 total allocations of variable chunk sizes.
+  ALLOC(2); // 2;  idx = 0
+  ALLOC(3); // 5;  idx = 1
+  ALLOC(1); // 6;  idx = 2
+  ALLOC(3); // 9;  idx = 3
+  ALLOC(1); // 10; idx = 4
+
+  // Free the 5 allocations in a different order.
+  FREE(1);
+  FREE(3);
+  FREE(4);
+  FREE(2);
+  FREE(0);
+
+  // Should be able to allocate 1 chunk of N blocks.
+  const void* chunk = mem_alloc(&mem, NUM_BLOCKS);
+  TEST_TRUE(chunk != 0);
+}
+
+// Clear and re-use an allocator.
+TEST_CASE(mem_clear_then_reuse) {
+  test_mem mem;
+  mem_make(&mem);
+
+  // Allocate chunks, contents not important.
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    int* chunk = mem_alloc(&mem, 1);
+    TEST_TRUE(chunk != 0);
+  }
+
+  mem_clear(&mem);
+
+  // Allocate chunks and assign values 0..N.
+  for (int i = 0; i < NUM_BLOCKS; ++i) {
+    int* chunk = mem_alloc(&mem, 1);
+    TEST_TRUE(chunk != 0);
+    *chunk = i + 1;
+  }
+
+  TEST_EQUAL(sum(&mem), NUM_BLOCKS * (NUM_BLOCKS + 1) / 2);
+}
+
+// Stress test.
+//
+// 1. Allocate the mem, either fully or partially. If fully, attempt to
+//    allocate some items past the end.
+//
+// 2. Free all allocated items in some random order.
+
+int main() { return 0; }
diff --git a/mem/test/test.h b/mem/test/test.h
new file mode 100644
index 0000000..fd8dc22
--- /dev/null
+++ b/mem/test/test.h
@@ -0,0 +1,185 @@
+// SPDX-License-Identifier: MIT
+#pragma once
+
+#ifdef UNIT_TEST
+
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#if defined(__DragonFly__) || defined(__FreeBSD__) || defined(__FreeBSD_kernel__) ||     \
+    defined(__NetBSD__) || defined(__OpenBSD__)
+#define USE_SYSCTL_FOR_ARGS 1
+// clang-format off
+#include <sys/types.h>
+#include <sys/sysctl.h>
+// clang-format on
+#include <unistd.h>        // getpid
+#endif
+
+struct test_file_metadata;
+
+struct test_failure {
+        bool present;
+        const char *message;
+        const char *file;
+        int line;
+};
+
+struct test_case_metadata {
+        void (*fn)(struct test_case_metadata *, struct test_file_metadata *);
+        struct test_failure failure;
+        const char *name;
+        struct test_case_metadata *next;
+};
+
+struct test_file_metadata {
+        bool registered;
+        const char *name;
+        struct test_file_metadata *next;
+        struct test_case_metadata *tests;
+};
+
+struct test_file_metadata __attribute__((weak)) * test_file_head;
+
+#define SET_FAILURE(_message)                                                             \
+        metadata->failure = (struct test_failure) {                                       \
+                .message = _message, .file = __FILE__, .line = __LINE__, .present = true, \
+        }
+
+#define TEST_EQUAL(a, b)                                                                 \
+        do {                                                                             \
+                if ((a) != (b)) {                                                        \
+                        SET_FAILURE(#a " != " #b);                                       \
+                        return;                                                          \
+                }                                                                        \
+        } while (0)
+
+#define TEST_TRUE(a)                                                                     \
+        do {                                                                             \
+                if (!(a)) {                                                              \
+                        SET_FAILURE(#a " is not true");                                  \
+                        return;                                                          \
+                }                                                                        \
+        } while (0)
+
+#define TEST_STREQUAL(a, b)                                                              \
+        do {                                                                             \
+                if (strcmp(a, b) != 0) {                                                 \
+                        SET_FAILURE(#a " != " #b);                                       \
+                        return;                                                          \
+                }                                                                        \
+        } while (0)
+
+#define TEST_CASE(_name)                                                                  \
+        static void __test_h_##_name(struct test_case_metadata *,                         \
+                                     struct test_file_metadata *);                        \
+        static struct test_file_metadata __test_h_file;                                   \
+        static struct test_case_metadata __test_h_meta_##_name = {                        \
+            .name = #_name,                                                               \
+            .fn = __test_h_##_name,                                                       \
+        };                                                                                \
+        static void __attribute__((constructor(101))) __test_h_##_name##_register(void) { \
+                __test_h_meta_##_name.next = __test_h_file.tests;                         \
+                __test_h_file.tests = &__test_h_meta_##_name;                             \
+                if (!__test_h_file.registered) {                                          \
+                        __test_h_file.name = __FILE__;                                    \
+                        __test_h_file.next = test_file_head;                              \
+                        test_file_head = &__test_h_file;                                  \
+                        __test_h_file.registered = true;                                  \
+                }                                                                         \
+        }                                                                                 \
+        static void __test_h_##_name(                                                     \
+            struct test_case_metadata *metadata __attribute__((unused)),                  \
+            struct test_file_metadata *file_metadata __attribute__((unused)))
+
+extern void __attribute__((weak)) (*test_h_unittest_setup)(void);
+/// Run defined tests, return true if all tests succeeds
+/// @param[out] tests_run if not NULL, set to whether tests were run
+static inline void __attribute__((constructor(102))) run_tests(void) {
+        bool should_run = false;
+#ifdef USE_SYSCTL_FOR_ARGS
+        int mib[] = {
+                CTL_KERN,
+#if defined(__NetBSD__) || defined(__OpenBSD__)
+                KERN_PROC_ARGS,
+                getpid(),
+                KERN_PROC_ARGV,
+#else
+                KERN_PROC,
+                KERN_PROC_ARGS,
+                getpid(),
+#endif
+        };
+        char *arg = NULL;
+        size_t arglen;
+        sysctl(mib, sizeof(mib) / sizeof(mib[0]), NULL, &arglen, NULL, 0);
+        arg = malloc(arglen);
+        sysctl(mib, sizeof(mib) / sizeof(mib[0]), arg, &arglen, NULL, 0);
+#else
+        FILE *cmdlinef = fopen("/proc/self/cmdline", "r");
+        char *arg = NULL;
+        int arglen;
+        fscanf(cmdlinef, "%ms%n", &arg, &arglen);
+        fclose(cmdlinef);
+#endif
+        for (char *pos = arg; pos < arg + arglen; pos += strlen(pos) + 1) {
+                if (strcmp(pos, "--unittest") == 0) {
+                        should_run = true;
+                        break;
+                }
+        }
+        free(arg);
+
+        if (!should_run) {
+                return;
+        }
+
+        if (&test_h_unittest_setup) {
+                test_h_unittest_setup();
+        }
+
+        struct test_file_metadata *i = test_file_head;
+        int failed = 0, success = 0;
+        while (i) {
+                fprintf(stderr, "Running tests from %s:\n", i->name);
+                struct test_case_metadata *j = i->tests;
+                while (j) {
+                        fprintf(stderr, "\t%s ... ", j->name);
+                        j->failure.present = false;
+                        j->fn(j, i);
+                        if (j->failure.present) {
+                                fprintf(stderr, "failed (%s at %s:%d)\n", j->failure.message,
+                                        j->failure.file, j->failure.line);
+                                failed++;
+                        } else {
+                                fprintf(stderr, "passed\n");
+                                success++;
+                        }
+                        j = j->next;
+                }
+                fprintf(stderr, "\n");
+                i = i->next;
+        }
+        int total = failed + success;
+        fprintf(stderr, "Test results: passed %d/%d, failed %d/%d\n", success, total,
+                failed, total);
+        exit(failed == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
+}
+
+#else
+
+#include <stdbool.h>
+
+#define TEST_CASE(name) static void __attribute__((unused)) __test_h_##name(void)
+
+#define TEST_EQUAL(a, b)                                                                 \
+        (void)(a);                                                                       \
+        (void)(b)
+#define TEST_TRUE(a) (void)(a)
+#define TEST_STREQUAL(a, b)                                                              \
+        (void)(a);                                                                       \
+        (void)(b)
+
+#endif