diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | README | 29 | ||||
| -rw-r--r-- | buddy.h | 2 | ||||
| -rw-r--r-- | magic_buddy.c | 2 |
4 files changed, 23 insertions, 12 deletions
@@ -2,7 +2,7 @@ CFLAGS += -g CFLAGS += -O3 -CFLAGS += -fsanitize=address +# CFLAGS += -fsanitize=address all: build/magic @@ -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. @@ -2,7 +2,7 @@ #include <stdint.h> #include <stddef.h> -#define MAGIC_COOKIE_BYTES 64 +#define MAGIC_COOKIE_BYTES 32 #define ADDRESS_BITS (8 * sizeof(void*)) void init_buddy(uint8_t *base, size_t size, diff --git a/magic_buddy.c b/magic_buddy.c index 18c4e23..1ebd25c 100644 --- a/magic_buddy.c +++ b/magic_buddy.c @@ -38,7 +38,7 @@ void init_buddy(uint8_t *base, size_t size, AVAIL[logsize] = (struct free_list *)base; AVAIL[logsize]->next = 0; AVAIL[logsize]->pprev = &(AVAIL[logsize]); - memcpy(&MAGIC, &magic, sizeof(MAGIC)); + memcpy(&MAGIC, magic, sizeof(MAGIC)); } static struct free_list *buddy_of(struct free_list *block, size_t logsize) { |