### Magic Buddy

A buddy allocator with zero metadata overhead.

Benefits are:

    1. Very good use of space compared to traditional buddy allocators,
       especially if you are frequently requesting power-of-two allocations.

    2. Still constant-time allocation and liberation.

    3. The library is small, simple, and convenient to use. It even supports
       unaligned base addresses.

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.

    4. We do not (yet) support some common allocator features, including
       realloc and reserving a specific subregion (e.g., device MMIO
       addresses). We expect to support these soon, although they may require
       adding an extra ~8 bytes to the minimum allocation size.

    5. Some advanced allocator features, e.g., iterating over allocated regions
       or attempting to dynamically improve cache locality, are not supported.

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.

### Usage

First, initialize the library by giving it both the base + size for the
allocation pool to be managed, along with some "very random" (or otherwise
secret) data. The following should work:

    // First, get some secret random data.
    uint8_t secret[MAGIC_COOKIE_BYTES];
    int fd = open("/dev/urandom", O_RDONLY);
    assert(count == read(fd, secret, count));
    close(fd);

    // Then initialize the buddy allocator.
    init_buddy(malloc(1026 * 1024), 1024 * 1024, secret);

Now, you can allocate and liberate as normal:

    // Get a region of 128 bytes
    uint8_t *x = allocate(128);
    // Write into it
    x[123] = 1234;
    // Liberate it
    liberate(x, 128);

### License

AGPLv3