PageAllocator
Description
Typed page-backed allocator. Carries Allocator base at offset 0 so (Allocator *)&page is well-defined.
Fields
| Name | Description |
|---|---|
base |
Generic allocator base (function pointers, alignment, …). |
cached_page_size |
Lazily-cached system page size in bytes, 0 until first query. |
entries |
Descriptor array for live mmap’d regions, sorted by ptr ascending; managed via direct mmap/munmap (POSIX) or VirtualAlloc/VirtualFree (Windows) – not through the public Allocator dispatch, which would recurse. |
len |
Number of live entries. |
cap |
Capacity of entries (geometric growth). |
entries_bytes |
Rounded mmap length of the entries table itself, retained so PageAllocatorDeinit can unmap it. |
free_entries |
Retained (user-freed but not yet returned to the OS) descriptor array, sorted by bytes ascending so the alloc-side exact-size match is a binary search. Page-level release policy is: once mmap’d, regions are kept until PageAllocatorDeinit; deallocate moves an entry from entries[] to free_entries[], allocate first searches free_entries[] for an exact-size match before going to the kernel. The freed mmap regions themselves are never written into (allocator data lives in this sibling table only – see CODING-CONVENTIONS: user-handed memory is opaque even after reclaim). Double-free detection on this table reduces to “ptr is missing from entries[]”; the error message is the combined “foreign or already-freed”, same as before. |
free_len |
Number of retained entries. |
free_cap |
Capacity of free_entries (geometric growth, separate from cap since the two tables grow independently). |
free_entries_bytes |
Rounded mmap length of the free_entries table itself. |
Usage example (Cross-references)
Usage examples (Cross-references)
- In
Allocator.h:32:
typedef struct Allocator Allocator;
typedef struct HeapAllocator HeapAllocator;
typedef struct PageAllocator PageAllocator;
typedef struct ArenaAllocator ArenaAllocator;
typedef struct SlabAllocator SlabAllocator;- In
Allocator.h:296:
size heap_allocator_deallocate(HeapAllocator *self, void *ptr);
void *page_allocator_allocate(PageAllocator *self, size bytes, i8 zeroed);
i8 page_allocator_resize(PageAllocator *self, void *ptr, size new_size);
void *page_allocator_remap(PageAllocator *self, void *ptr, size new_size);- In
Allocator.h:297:
void *page_allocator_allocate(PageAllocator *self, size bytes, i8 zeroed);
i8 page_allocator_resize(PageAllocator *self, void *ptr, size new_size);
void *page_allocator_remap(PageAllocator *self, void *ptr, size new_size);
size page_allocator_deallocate(PageAllocator *self, void *ptr);- In
Allocator.h:298:
void *page_allocator_allocate(PageAllocator *self, size bytes, i8 zeroed);
i8 page_allocator_resize(PageAllocator *self, void *ptr, size new_size);
void *page_allocator_remap(PageAllocator *self, void *ptr, size new_size);
size page_allocator_deallocate(PageAllocator *self, void *ptr);- In
Allocator.h:299:
i8 page_allocator_resize(PageAllocator *self, void *ptr, size new_size);
void *page_allocator_remap(PageAllocator *self, void *ptr, size new_size);
size page_allocator_deallocate(PageAllocator *self, void *ptr);
void *arena_allocator_allocate(ArenaAllocator *self, size bytes, i8 zeroed);- In
Allocator.h:392:
Allocator *: (allocator_ptr), \
HeapAllocator *: (Allocator *)(allocator_ptr), \
PageAllocator *: (Allocator *)(allocator_ptr), \
ArenaAllocator *: (Allocator *)(allocator_ptr), \
SlabAllocator *: (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
Page.h:88:
u32 free_cap;
size free_entries_bytes;
} PageAllocator;
///
- In
Page.h:106:
/// TAGS: Allocator, Page, Memory, Allocation
///
void *page_allocator_allocate(PageAllocator *self, size bytes, i8 zeroed);
///
- In
Page.h:122:
/// TAGS: Allocator, Page, Memory, InPlace
///
i8 page_allocator_resize(PageAllocator *self, void *ptr, size new_size);
///
- In
Page.h:139:
/// TAGS: Allocator, Page, Memory, Reallocation
///
void *page_allocator_remap(PageAllocator *self, void *ptr, size new_size);
///
- In
Page.h:158:
/// TAGS: Allocator, Page, Memory, Deallocation
///
size page_allocator_deallocate(PageAllocator *self, void *ptr);
///
- In
Page.h:213:
/// TAGS: Allocator, Page, Query
///
size PageAllocatorPageSize(PageAllocator *self);
///
- In
Page.h:231:
/// TAGS: Allocator, Page, Cleanup
///
void PageAllocatorDeinit(PageAllocator *self);
#ifdef __cplusplus- In
Page.h:266:
///
#define PageAllocatorInit() \
((PageAllocator) { \
.base = \
{.allocate = (AllocatorAllocateFn)page_allocator_allocate, \- In
Page.h:300:
///
#define PageAllocatorInitAligned(N) \
((PageAllocator) { \
.base = \
{.allocate = (AllocatorAllocateFn)page_allocator_allocate, \- In
Debug.h:167:
HeapAllocator heap;
HeapAllocator meta;
PageAllocator page;
DebugAllocatorConfig config;
DebugRecordMap live;- In
Page.c:51:
#define PAGE_MARK_DIRTY(p) MAGIC_MARK_DIRTY(&(p)->base)
static void page_validate_self_structural(const PageAllocator *pg) {
if (!pg->base.allocate || !pg->base.resize || !pg->base.remap || !pg->base.deallocate) {
LOG_FATAL("PageAllocator: vtable function pointer is NULL");- In
Page.c:53:
static void page_validate_self_structural(const PageAllocator *pg) {
if (!pg->base.allocate || !pg->base.resize || !pg->base.remap || !pg->base.deallocate) {
LOG_FATAL("PageAllocator: vtable function pointer is NULL");
}
if (pg->base.alignment == 0 || (pg->base.alignment & (pg->base.alignment - 1)) != 0) {- In
Page.c:56:
}
if (pg->base.alignment == 0 || (pg->base.alignment & (pg->base.alignment - 1)) != 0) {
LOG_FATAL("PageAllocator: alignment {} is not a positive power of two", (u64)pg->base.alignment);
}
if (pg->len > pg->cap) {- In
Page.c:59:
}
if (pg->len > pg->cap) {
LOG_FATAL("PageAllocator: len {} exceeds cap {}", (u64)pg->len, (u64)pg->cap);
}
if ((pg->entries == NULL) != (pg->cap == 0)) {- In
Page.c:62:
}
if ((pg->entries == NULL) != (pg->cap == 0)) {
LOG_FATAL("PageAllocator: entries / cap mismatch (entries={x}, cap={})", (u64)pg->entries, (u64)pg->cap);
}
if (pg->len > 0 && !pg->entries) {- In
Page.c:65:
}
if (pg->len > 0 && !pg->entries) {
LOG_FATAL("PageAllocator: len {} with NULL entries", (u64)pg->len);
}
if ((pg->entries == NULL) != (pg->entries_bytes == 0)) {- In
Page.c:68:
}
if ((pg->entries == NULL) != (pg->entries_bytes == 0)) {
LOG_FATAL("PageAllocator: entries / entries_bytes mismatch");
}
if (pg->entries && pg->entries_bytes < (size)pg->cap * sizeof(PageEntry)) {- In
Page.c:72:
if (pg->entries && pg->entries_bytes < (size)pg->cap * sizeof(PageEntry)) {
LOG_FATAL(
"PageAllocator: entries_bytes {} too small for cap {} (need {})",
(u64)pg->entries_bytes,
(u64)pg->cap,- In
Page.c:85:
// Same invariants for the retention table.
if (pg->free_len > pg->free_cap) {
LOG_FATAL("PageAllocator: free_len {} exceeds free_cap {}", (u64)pg->free_len, (u64)pg->free_cap);
}
if ((pg->free_entries == NULL) != (pg->free_cap == 0)) {- In
Page.c:89:
if ((pg->free_entries == NULL) != (pg->free_cap == 0)) {
LOG_FATAL(
"PageAllocator: free_entries / free_cap mismatch ({x} / {})",
(u64)pg->free_entries,
(u64)pg->free_cap- In
Page.c:95:
}
if (pg->free_len > 0 && !pg->free_entries) {
LOG_FATAL("PageAllocator: free_len {} with NULL free_entries", (u64)pg->free_len);
}
if ((pg->free_entries == NULL) != (pg->free_entries_bytes == 0)) {- In
Page.c:98:
}
if ((pg->free_entries == NULL) != (pg->free_entries_bytes == 0)) {
LOG_FATAL("PageAllocator: free_entries / free_entries_bytes mismatch");
}
if (pg->free_entries) {- In
Page.c:105:
}
static void page_validate_self(const PageAllocator *pg) {
if (!pg) {
LOG_FATAL("PageAllocator: NULL self");- In
Page.c:107:
static void page_validate_self(const PageAllocator *pg) {
if (!pg) {
LOG_FATAL("PageAllocator: NULL self");
}
if (!MAGIC_MATCHES(pg->base.__magic, PAGE_ALLOCATOR_MAGIC)) {- In
Page.c:110:
}
if (!MAGIC_MATCHES(pg->base.__magic, PAGE_ALLOCATOR_MAGIC)) {
LOG_FATAL("type-confusion: allocator passed to page_allocator_* is not a PageAllocator");
}
if (!(pg->base.__magic & MAGIC_VALIDATED_BIT)) {- In
Page.c:116:
}
page_validate_self_structural(pg);
((PageAllocator *)(void *)pg)->base.__magic &= ~MAGIC_VALIDATED_BIT;
}- In
Page.c:119:
}
size PageAllocatorPageSize(PageAllocator *self) {
if (self && self->cached_page_size) {
return self->cached_page_size;- In
Page.c:134:
}
static size page_effective_alignment(PageAllocator *self) {
size requested = self ? self->base.alignment : 0;
size page_size = PageAllocatorPageSize(self);- In
Page.c:146:
}
static size page_rounded_size(PageAllocator *self, size bytes) {
size align = page_effective_alignment(self);
size page_size = PageAllocatorPageSize(self);- In
Page.c:185:
// field pointers so the same helper grows either `entries` or
// `free_entries`. Returns false on OS-allocation failure or overflow.
static bool page_table_grow_into(PageAllocator *page, PageEntry **arr_p, u32 *len_p, u32 *cap_p, size *bytes_p) {
size page_size = PageAllocatorPageSize(page);
size want_bytes;- In
Page.c:217:
// Grows the table if full. Returns false on grow failure.
static bool page_table_insert_sorted(
PageAllocator *page,
PageEntry **arr_p,
u32 *len_p,- In
Page.c:265:
// Exact-match policy: don't return a 64 KiB entry for a 16 KiB request
// (would track the wrong size and waste memory on the next free).
static u32 page_free_find_size_match(const PageAllocator *page, size bytes) {
u32 lo = 0, hi = page->free_len;
while (lo < hi) {- In
Page.c:284:
// Grows the table if full. Returns false on grow failure (caller falls
// back to immediate munmap rather than leak the live entry).
static bool page_free_insert_sorted(PageAllocator *page, void *ptr, size bytes) {
if (page->free_len == page->free_cap &&
!page_table_grow_into(page, &page->free_entries, &page->free_len, &page->free_cap, &page->free_entries_bytes)) {- In
Page.c:314:
// Public alloc / resize / remap / free.
void *page_allocator_allocate(PageAllocator *self, size bytes, i8 zeroed) {
page_validate_self(self);
if (!bytes) {- In
Page.c:405:
// neighbouring VMA blocks growth. Either way, we don't attempt it --
// the caller can fall back to remap, which alloc+copy+frees.
i8 page_allocator_resize(PageAllocator *self, void *ptr, size new_size) {
page_validate_self(self);
u32 idx = page_find_idx_sorted(self->entries, self->len, ptr);- In
Page.c:427:
}
void *page_allocator_remap(PageAllocator *self, void *ptr, size new_size) {
page_validate_self(self);- In
Page.c:469:
}
size page_allocator_deallocate(PageAllocator *self, void *ptr) {
page_validate_self(self);
if (!ptr) {- In
Page.c:508:
void PageAllocatorDeinit(PageAllocator *self) {
if (!self) {
return;- In
PageProtect.c:7:
bool test_page_protect_roundtrip(void) {
PageAllocator page = PageAllocatorInit();
Allocator *base = ALLOCATOR_OF(&page);
static bool test_basic_alloc_and_free(void) {
PageAllocator alloc = PageAllocatorInit();
Allocator *alloc_base = ALLOCATOR_OF(&alloc);
void *ptr = AllocatorAlloc(alloc_base, 128, true);
static bool test_realloc_grow_then_shrink(void) {
PageAllocator alloc = PageAllocatorInit();
Allocator *alloc_base = ALLOCATOR_OF(&alloc);
size page = PageAllocatorPageSize(&alloc); // PageAllocator backs Vec via the generic Allocator dispatch.
// Exercises the internal descriptor table across multiple grows.
PageAllocator alloc = PageAllocatorInit();
typedef Vec(int) IntVec;
IntVec v = VecInit(&alloc); // assert page-alignment here since that is what mmap guarantees
// portably.
PageAllocator alloc = PageAllocatorInitAligned(64);
Allocator *alloc_base = ALLOCATOR_OF(&alloc);
size page = PageAllocatorPageSize(&alloc); // both, plus the descriptor tables.
bool ok = true;
PageAllocator alloc = PageAllocatorInit();
Allocator *alloc_base = ALLOCATOR_OF(&alloc);
size page = PageAllocatorPageSize(&alloc);- In
Graph.Mut.c:42:
static bool deadend_commit_aborts_on_non_pow2_alignment(void) {
PageAllocator alloc = PageAllocatorInitAligned(3);
IntGraph graph = GraphInit(&alloc);
Last updated on