### Magic Buddy

A buddy allocator with zero metadata overhead. Caveats are:

    1. The minimum allocation size is nontrivial, approximately 64 bytes

    2. Your application must keep track of allocation sizes, and provide them
       when liberating a region.

    3. There is a miniscule-but-nonzero chance the buddy allocator gets
       corrupted; the probability is configurable by the user. The default has
       a 1/2^128-chance of getting corrupted per program operation.

Traditional optimized buddy allocators (see Knuth Vol 1) require at least 1/2
extra bit per allocation region.

But this means (as Akshay Srivatsan pointed out to me recently) that an
allocation of size 2^k might cause an actual allocation of size 2^k + 1/8,
rounding up to 2^{k+1} because buddy allocators can only allocate in
powers-of-two byte amounts. This is surprisingly wasteful.

Instead, this repo has a buddy allocator that requires no extra metadata
overhead. It stores the "freed-or-not bit" implicitly: a block is considered
freed iff its first 128 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 bytes.

But it retains the nice property of buddy allocators that liberation is linear
in the computer's address size.

### License

AGPLv3