From affa5e2933186970d0a3dac38d2ca8f02190e4d9 Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Wed, 15 May 2024 20:15:45 -0700 Subject: basic magic buddy allocator --- README | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 README (limited to 'README') 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 -- cgit v1.2.3