From 2623dbaf1b8653c6ad49fa9fbcf99c5039086eb6 Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Thu, 16 May 2024 02:33:39 -0700 Subject: fix small memcpy bug --- README | 29 ++++++++++++++++++++--------- 1 file changed, 20 insertions(+), 9 deletions(-) (limited to 'README') diff --git a/README b/README index bf7dbcb..f10afea 100644 --- a/README +++ b/README @@ -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. -- cgit v1.2.3