From ea94ea921c683a4bc41841949d867706b30f9f33 Mon Sep 17 00:00:00 2001 From: Matthew Sotoudeh Date: Thu, 16 May 2024 02:46:26 -0700 Subject: some more readme --- README | 45 ++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 44 insertions(+), 1 deletion(-) (limited to 'README') diff --git a/README b/README index f10afea..dde8ccf 100644 --- a/README +++ b/README @@ -1,6 +1,18 @@ ### Magic Buddy -A buddy allocator with zero metadata overhead. Caveats are: +A buddy allocator with zero metadata overhead. + +Benefits are: + + 1. Very good use of space compared to traditional buddy allocators, + especially if you are frequently requesting power-of-two allocations. + + 2. Still constant-time allocation and liberation. + + 3. The library is small, simple, and convenient to use. It even supports + unaligned base addresses. + +Caveats are: 1. The minimum allocation size is nontrivial, approximately 64 bytes @@ -11,6 +23,13 @@ A buddy allocator with zero metadata overhead. Caveats are: corrupted; the probability is configurable by the user. The default has a 1/2^128-chance of getting corrupted per program operation. + 4. We do not (yet) support some common allocator features, including + realloc and reserving a specific subregion (e.g., device MMIO + addresses). We expect to support these soon. + + 5. Some advanced allocator features, e.g., iterating over allocated regions + or attempting to dynamically improve cache locality, are not supported. + Traditional optimized buddy allocators (see Knuth Vol 1) require at least 1/2 extra bit per allocation region. @@ -34,6 +53,30 @@ The only sources of memory overhead are: But it retains the nice property of buddy allocators that liberation is linear in the computer's address size. +### Usage + +First, initialize the library by giving it both the base + size for the +allocation pool to be managed, along with some "very random" (or otherwise +secret) data. The following should work: + + // First, get some secret random data. + uint8_t secret[MAGIC_COOKIE_BYTES]; + int fd = open("/dev/urandom", O_RDONLY); + assert(count == read(fd, secret, count)); + close(fd); + + // Then initialize the buddy allocator. + init_buddy(malloc(1026 * 1024), 1024 * 1024, secret); + +Now, you can allocate and liberate as normal: + + // Get a region of 128 bytes + uint8_t *x = allocate(128); + // Write into it + x[123] = 1234; + // Liberate it + liberate(x, 128); + ### License AGPLv3 -- cgit v1.2.3