This code was integrated into the Zig Standard Library in Pull Request #5998.
This repository is no longer maintained.
This is the code for my Zig Live Coding Stream.
This is a work-in-progress general purpose allocator intended to be eventually merged into the Zig standard library, with the focus on these goals:
Detect double free, and print stack trace of:
Detect leaks and print stack trace of:
When a page of memory is no longer needed, give it back to resident memory, but keep it mapped with no permissions (read/write/exec) so that it causes page faults when used.
Make pointer math errors unlikely to harm memory from unrelated allocations
It's OK for these mechanisms to cost some extra bytes and for memory to become a little fragmented.
OK for performance cost for these mechanisms.
Rogue memory writes should not harm the allocator's state.
Cross platform. Allowed to take advatage of a specific operating system's features, but should work everywhere, even freestanding, by wrapping an existing allocator.
Compile-time configuration, including:
ReleaseFast and ReleaseSmall Modes:
ReleaseSafe Mode:
Memory leak detection:
Double free detection:
Small allocations are divided into buckets:
index obj_size
0 1
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024
11 2048
The main allocator state has an array of all the "current" buckets for each size class. Each slot in the array can be null, meaning the bucket for that size class is not allocated. When the first object is allocated for a given size class, it allocates 1 page of memory from the OS. This page is divided into "slots" - one per allocated object. Along with the page of memory for object slots, as many pages as necessary are allocated to store the BucketHeader, followed by "used bits", and two stack traces for each slot (allocation trace and free trace).
The "used bits" are 1 bit per slot representing whether the slot is used. Allocations use the data to iterate to find a free slot. Frees assert that the corresponding bit is 1 and set it to 0.
The memory for the allocator goes on its own page, with no write permissions. On call to reallocFn and shrinkFn, the allocator uses mprotect to make its own state writable, and then removes write permissions before returning. However bucket metadata is not protected in this way yet.
Buckets have prev and next pointers. When there is only one bucket for a given size class, both prev and next point to itself. When all slots of a bucket are used, a new bucket is allocated, and enters the doubly linked list. The main allocator state tracks the "current" bucket for each size class. Leak detection currently only checks the current bucket.
Reallocation detects if the size class is unchanged, in which case the same pointer is returned unmodified. If a different size class is required, the allocator attempts to allocate a new slot, copy the bytes, and then free the old slot.
Large objects are allocated directly using mmap
and their metadata is stored
in a std.HashMap
backed by a simple direct allocator. The hash map's data
is memory protected with the same strategy as the allocator's state.
std.HashMap
return bytes back to the allocator when the hash map gets0xdd
.old_align
or old_mem.len
.