BudgetAllocator
Description
Caller-buffer fixed-budget bitmap allocator. Carries Allocator base at offset 0 so (Allocator *)&bp is well-defined.
The caller-provided buffer is partitioned at init into a bitmap region followed by a slot region. User pointers returned by Alloc always lie in the slot region; on Free the allocator validates the pointer against the slot range, alignment, and the bitmap state (catches foreign / misaligned / double-free without writing through the pointer).
Fields
| Name | Description |
|---|---|
base |
Generic allocator base (function pointers, alignment, …). |
buf |
Pointer to the caller-owned memory region. |
buf_bytes |
Size of buf in bytes. |
bitmap |
u64 bitmap (allocator-owned region inside buf). |
bitmap_words |
Number of u64 words in bitmap. |
slots |
Start of the slot region inside buf. |
slot_size |
Slot size in bytes (rounded up to base.alignment). |
slot_count |
Number of slots carved out of buf. |
Usage example (Cross-references)
Usage examples (Cross-references)
- In
Allocator.h:35:
typedef struct ArenaAllocator ArenaAllocator;
typedef struct SlabAllocator SlabAllocator;
typedef struct BudgetAllocator BudgetAllocator;
typedef struct DebugAllocator DebugAllocator;- In
Allocator.h:311:
size slab_allocator_deallocate(SlabAllocator *self, void *ptr);
void *budget_allocator_allocate(BudgetAllocator *self, size bytes, i8 zeroed);
i8 budget_allocator_resize(BudgetAllocator *self, void *ptr, size new_size);
void *budget_allocator_remap(BudgetAllocator *self, void *ptr, size new_size);- In
Allocator.h:312:
void *budget_allocator_allocate(BudgetAllocator *self, size bytes, i8 zeroed);
i8 budget_allocator_resize(BudgetAllocator *self, void *ptr, size new_size);
void *budget_allocator_remap(BudgetAllocator *self, void *ptr, size new_size);
size budget_allocator_deallocate(BudgetAllocator *self, void *ptr);- In
Allocator.h:313:
void *budget_allocator_allocate(BudgetAllocator *self, size bytes, i8 zeroed);
i8 budget_allocator_resize(BudgetAllocator *self, void *ptr, size new_size);
void *budget_allocator_remap(BudgetAllocator *self, void *ptr, size new_size);
size budget_allocator_deallocate(BudgetAllocator *self, void *ptr);- In
Allocator.h:314:
i8 budget_allocator_resize(BudgetAllocator *self, void *ptr, size new_size);
void *budget_allocator_remap(BudgetAllocator *self, void *ptr, size new_size);
size budget_allocator_deallocate(BudgetAllocator *self, void *ptr);
void *debug_allocator_allocate(DebugAllocator *self, size bytes, i8 zeroed);- In
Allocator.h:395:
ArenaAllocator *: (Allocator *)(allocator_ptr), \
SlabAllocator *: (Allocator *)(allocator_ptr), \
BudgetAllocator *: (Allocator *)(allocator_ptr), \
DebugAllocator *: (Allocator *)(allocator_ptr) \
)- In
Allocator.h:424:
///
#define AllocatorAlloc(self, bytes, zeroed) \
_Generic((self), HeapAllocator *: heap_allocator_allocate, PageAllocator *: page_allocator_allocate, ArenaAllocator *: arena_allocator_allocate, SlabAllocator *: slab_allocator_allocate, BudgetAllocator *: budget_allocator_allocate, DebugAllocator *: debug_allocator_allocate, Allocator *: AllocatorAlloc_dyn)( \
(self), \
(bytes), \- In
Allocator.h:447:
///
#define AllocatorResize(self, ptr, new_size) \
_Generic((self), HeapAllocator *: heap_allocator_resize, PageAllocator *: page_allocator_resize, ArenaAllocator *: arena_allocator_resize, SlabAllocator *: slab_allocator_resize, BudgetAllocator *: budget_allocator_resize, DebugAllocator *: debug_allocator_resize, Allocator *: AllocatorResize_dyn)( \
(self), \
(ptr), \- In
Allocator.h:471:
///
#define AllocatorRemap(self, ptr, new_size) \
_Generic((self), HeapAllocator *: heap_allocator_remap, PageAllocator *: page_allocator_remap, ArenaAllocator *: arena_allocator_remap, SlabAllocator *: slab_allocator_remap, BudgetAllocator *: budget_allocator_remap, DebugAllocator *: debug_allocator_remap, Allocator *: AllocatorRemap_dyn)( \
(self), \
(ptr), \- In
Allocator.h:525:
///
#define AllocatorFree(self, ptr) \
_Generic((self), HeapAllocator *: heap_allocator_deallocate, PageAllocator *: page_allocator_deallocate, ArenaAllocator *: arena_allocator_deallocate, SlabAllocator *: slab_allocator_deallocate, BudgetAllocator *: budget_allocator_deallocate, DebugAllocator *: debug_allocator_deallocate, Allocator *: AllocatorFree_dyn)( \
(self), \
(ptr) \- In
Budget.h:85:
size slot_size;
size slot_count;
} BudgetAllocator;
///
- In
Budget.h:101:
/// TAGS: Allocator, Budget, Memory, Allocation
///
void *budget_allocator_allocate(BudgetAllocator *self, size bytes, i8 zeroed);
///
- In
Budget.h:114:
/// TAGS: Allocator, Budget, Memory, InPlace
///
i8 budget_allocator_resize(BudgetAllocator *self, void *ptr, size new_size);
///
- In
Budget.h:132:
/// TAGS: Allocator, Budget, Memory, Reallocation
///
void *budget_allocator_remap(BudgetAllocator *self, void *ptr, size new_size);
///
- In
Budget.h:146:
/// TAGS: Allocator, Budget, Memory, Deallocation
///
size budget_allocator_deallocate(BudgetAllocator *self, void *ptr);
///
- In
Budget.h:212:
) * sizeof(u64) \
), \
((BudgetAllocator) { \
.base = \
{.allocate = (AllocatorAllocateFn)budget_allocator_allocate, \
- In
Budget.h:278:
/// TAGS: Allocator, Budget, Cleanup
///
void BudgetAllocatorDeinit(BudgetAllocator *self);
#ifdef __cplusplus- In
Budget.c:40:
// memoization holds for the rest of the allocator's life.
static void budget_validate_self_structural(const BudgetAllocator *self) {
if (!self->base.allocate || !self->base.resize || !self->base.remap || !self->base.deallocate) {
LOG_FATAL("BudgetAllocator: vtable function pointer is NULL");- In
Budget.c:42:
static void budget_validate_self_structural(const BudgetAllocator *self) {
if (!self->base.allocate || !self->base.resize || !self->base.remap || !self->base.deallocate) {
LOG_FATAL("BudgetAllocator: vtable function pointer is NULL");
}
if (self->base.alignment == 0 || (self->base.alignment & (self->base.alignment - 1)) != 0) {- In
Budget.c:45:
}
if (self->base.alignment == 0 || (self->base.alignment & (self->base.alignment - 1)) != 0) {
LOG_FATAL("BudgetAllocator: alignment {} is not a positive power of two", (u64)self->base.alignment);
}
if (!self->buf || self->buf_bytes == 0) {- In
Budget.c:48:
}
if (!self->buf || self->buf_bytes == 0) {
LOG_FATAL("BudgetAllocator: NULL or zero-byte backing buffer");
}
if (!self->bitmap || self->bitmap_words == 0) {- In
Budget.c:51:
}
if (!self->bitmap || self->bitmap_words == 0) {
LOG_FATAL("BudgetAllocator: NULL or zero-word bitmap");
}
if (!self->slots || self->slot_count == 0) {- In
Budget.c:54:
}
if (!self->slots || self->slot_count == 0) {
LOG_FATAL("BudgetAllocator: NULL or zero-count slot region");
}
if (self->slot_size == 0) {- In
Budget.c:57:
}
if (self->slot_size == 0) {
LOG_FATAL("BudgetAllocator: slot_size is 0");
}
// Bitmap covers at least slot_count bits.
- In
Budget.c:62:
if ((u64)self->bitmap_words * 64u < (u64)self->slot_count) {
LOG_FATAL(
"BudgetAllocator: bitmap_words {} too small for slot_count {} (need {})",
(u64)self->bitmap_words,
(u64)self->slot_count,- In
Budget.c:71:
const u8 *buf_end = self->buf + self->buf_bytes;
if ((const u8 *)self->bitmap < self->buf || (const u8 *)self->bitmap >= buf_end) {
LOG_FATAL("BudgetAllocator: bitmap pointer outside buf region");
}
if (self->slots < self->buf || self->slots > buf_end) {- In
Budget.c:74:
}
if (self->slots < self->buf || self->slots > buf_end) {
LOG_FATAL("BudgetAllocator: slots pointer outside buf region");
}
if ((u64)self->slot_count * (u64)self->slot_size > (u64)(buf_end - self->slots)) {- In
Budget.c:78:
if ((u64)self->slot_count * (u64)self->slot_size > (u64)(buf_end - self->slots)) {
LOG_FATAL(
"BudgetAllocator: slots region overruns buf (need {} bytes, have {})",
(u64)self->slot_count * (u64)self->slot_size,
(u64)(buf_end - self->slots)- In
Budget.c:85:
// Bitmap region must precede the slot region (init lays them out that way).
if ((const u8 *)self->bitmap >= self->slots) {
LOG_FATAL("BudgetAllocator: bitmap region must precede slot region");
}
}- In
Budget.c:89:
}
static void budget_validate_self(const BudgetAllocator *self) {
if (!self) {
LOG_FATAL("BudgetAllocator: NULL self");- In
Budget.c:91:
static void budget_validate_self(const BudgetAllocator *self) {
if (!self) {
LOG_FATAL("BudgetAllocator: NULL self");
}
if (!MAGIC_MATCHES(self->base.__magic, BUDGET_ALLOCATOR_MAGIC)) {- In
Budget.c:94:
}
if (!MAGIC_MATCHES(self->base.__magic, BUDGET_ALLOCATOR_MAGIC)) {
LOG_FATAL("type-confusion: allocator passed to budget_allocator_* is not a BudgetAllocator");
}
if (!(self->base.__magic & MAGIC_VALIDATED_BIT)) {- In
Budget.c:100:
}
budget_validate_self_structural(self);
((BudgetAllocator *)(void *)self)->base.__magic &= ~MAGIC_VALIDATED_BIT;
}- In
Budget.c:124:
// Public alloc / resize / remap / free.
void *budget_allocator_allocate(BudgetAllocator *self, size bytes, i8 zeroed) {
budget_validate_self(self);
if (bytes == 0 || bytes > self->slot_size) {- In
Budget.c:148:
u32 b = (u32)((u64)idx & 63u);
if (self->bitmap[w] & ((u64)1 << b)) {
LOG_FATAL("BudgetAllocator bitmap corruption: idx {} bit unexpectedly set", (u64)idx);
}
self->bitmap[w] |= ((u64)1 << b);- In
Budget.c:170:
}
i8 budget_allocator_resize(BudgetAllocator *self, void *ptr, size new_size) {
budget_validate_self(self);
(void)ptr;- In
Budget.c:185:
}
void *budget_allocator_remap(BudgetAllocator *self, void *ptr, size new_size) {
budget_validate_self(self);
if (!ptr)- In
Budget.c:207:
}
size budget_allocator_deallocate(BudgetAllocator *self, void *ptr) {
budget_validate_self(self);
if (!ptr)- In
Budget.c:250:
// [bitmap | pad | slots] -- matching the validator's invariant checks above.
void BudgetAllocatorDeinit(BudgetAllocator *self) {
if (!self)
return; static bool test_basic_alloc_and_free(void) {
u8 buf[1024] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
Allocator *alloc = ALLOCATOR_OF(&bp);
Node *a = (Node *)AllocatorAlloc(alloc, sizeof(Node), true); static bool test_zero_byte_alloc_returns_null(void) {
u8 buf[256] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
Allocator *alloc = ALLOCATOR_OF(&bp);
void *p = AllocatorAlloc(alloc, 0, false); static bool test_free_null_is_noop(void) {
u8 buf[256] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
Allocator *alloc = ALLOCATOR_OF(&bp);
AllocatorFree(alloc, NULL); static bool test_fails_when_empty(void) {
u8 buf[256] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
Allocator *alloc = ALLOCATOR_OF(&bp); static bool test_free_then_alloc_recycles(void) {
u8 buf[1024] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
Allocator *alloc = ALLOCATOR_OF(&bp); static bool test_alloc_distinct_pointers(void) {
u8 buf[1024] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
Allocator *alloc = ALLOCATOR_OF(&bp); static bool test_oversized_request_fails(void) {
u8 buf[256] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(int));
Allocator *alloc = ALLOCATOR_OF(&bp);
void *big = AllocatorAlloc(alloc, 4096, true); static u8 buf[1024];
MemSet(buf, 0, sizeof(buf));
BudgetAllocator bp = BudgetAllocatorInitAligned(buf, sizeof(buf), sizeof(int), 64);
Allocator *alloc = ALLOCATOR_OF(&bp);
int *p1 = (int *)AllocatorAlloc(alloc, sizeof(int), true); // line. A passing deadend is one where the abort fired.
u8 buf[4] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
BudgetAllocatorDeinit(&bp);
return false; u8 buf1[1024] = {0};
u8 buf2[1024] = {0};
BudgetAllocator bp1 = BudgetAllocatorInit(buf1, sizeof(buf1), sizeof(Node));
BudgetAllocator bp2 = BudgetAllocatorInit(buf2, sizeof(buf2), sizeof(Node));
Allocator *alloc1 = ALLOCATOR_OF(&bp1); u8 buf2[1024] = {0};
BudgetAllocator bp1 = BudgetAllocatorInit(buf1, sizeof(buf1), sizeof(Node));
BudgetAllocator bp2 = BudgetAllocatorInit(buf2, sizeof(buf2), sizeof(Node));
Allocator *alloc1 = ALLOCATOR_OF(&bp1);
Allocator *alloc2 = ALLOCATOR_OF(&bp2); // Pointer to bitmap region (front of buf) must be rejected as foreign.
u8 buf[1024] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
Allocator *alloc = ALLOCATOR_OF(&bp); static bool test_reject_misaligned_pointer(void) {
u8 buf[1024] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
Allocator *alloc = ALLOCATOR_OF(&bp);
char *p = (char *)AllocatorAlloc(alloc, sizeof(Node), false); static bool test_reject_double_free(void) {
u8 buf[1024] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), sizeof(Node));
Allocator *alloc = ALLOCATOR_OF(&bp);
Node *p = (Node *)AllocatorAlloc(alloc, sizeof(Node), false); // is far too small for the string's backing buffer, so allocation fails.
u8 buf[64] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), 8);
Str s = StrInit(&bp);
u8 buf[64] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), 8);
Str s = StrInit(&bp);
u8 buf[512] = {0};
BudgetAllocator bp = BudgetAllocatorInit(buf, sizeof(buf), 8);
Str s = StrInit(&bp);
Last updated on