diff options
Diffstat (limited to 'README')
-rw-r--r-- | README | 28 |
1 files changed, 28 insertions, 0 deletions
@@ -0,0 +1,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 |