diff options
Diffstat (limited to 'README')
| -rw-r--r-- | README | 29 |
1 files changed, 20 insertions, 9 deletions
@@ -1,24 +1,35 @@ ### Magic Buddy -Traditional optimized buddy allocators (see Knuth Vol 1) require at least 1 -extra bit on each allocation region. +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 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. +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 allocation +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 512 bits is some magic cookie value determined randomly and +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 + 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. + ~64 bytes. But it retains the nice property of buddy allocators that liberation is linear in the computer's address size. |