blob: f10afeac994a8dfba760e9e5f472768fda7b79bd (
plain)
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
29
30
31
32
33
34
35
36
37
38
39
|
### 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
|
