README


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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