basic magic buddy allocator

1 files changed, 28 insertions, 0 deletions

diff --git a/README b/README
new file mode 100644
index 0000000..bf7dbcb
--- /dev/null
+++ b/README
@@ -0,0 +1,28 @@
+### Magic Buddy
+
+Traditional optimized buddy allocators (see Knuth Vol 1) require at least 1
+extra bit on each allocation region.
+
+But this means (as Akshay Srivatsan pointed out to me recently) that an
+allocation of size 2^k will cause an actual allocation of size 2^k + 1/8,
+rounds up to 2^{k+1} because buddy allocators can only allocate in
+powers-of-two byte amounts. This is wasteful.
+
+Instead, this repo has a buddy allocator that requires no extra allocation
+overhead. It stores the "freed-or-not bit" implicitly: a block is considered
+freed iff its first 512 bits is some magic cookie value determined randomly and
+kept secret from the application.
+
+The only sources of memory overhead are:
+
+    1. Fragmentation from allocations being forced to be powers of 2
+
+    2. Fragmentation from a (rather large) minimum allowed allocation size of
+       ~64+16 bytes.
+
+But it retains the nice property of buddy allocators that liberation is linear
+in the computer's address size.
+
+### License
+
+AGPLv3