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 --- Makefile | 2 +- README | 29 ++++++++++++++++++++--------- buddy.h | 2 +- magic_buddy.c | 2 +- 4 files changed, 23 insertions(+), 12 deletions(-) diff --git a/Makefile b/Makefile index 22c011a..35aba2c 100644 --- a/Makefile +++ b/Makefile @@ -2,7 +2,7 @@ CFLAGS += -g CFLAGS += -O3 -CFLAGS += -fsanitize=address +# CFLAGS += -fsanitize=address all: build/magic 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. diff --git a/buddy.h b/buddy.h index b335019..8a2ccac 100644 --- a/buddy.h +++ b/buddy.h @@ -2,7 +2,7 @@ #include #include -#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) { -- cgit v1.2.3