TLSF

Atoll’s arena allocator begins with a bump pointer and promotes to a two-level segregated fit allocator when it must reuse non-tail storage. The implementation is TLSF-inspired: it uses a constant-size class index and bitmaps for normal block selection while retaining compact block headers.

This is an internal allocation mechanism. Atoll programs observe allocation success, failure, and ownership semantics, not a language guarantee that a particular request uses a particular size class.

Why promote

Bump allocation is ideal while an arena mostly grows and frees its newest blocks. Maintaining free lists during that phase would add work without creating reusable holes.

The first definite non-tail free changes that tradeoff. If the body is at least 1 KiB, the allocator walks the physical blocks, reconstructs free space, and switches permanently to TLSF mode. Smaller arenas record the block as potential garbage and delay reconstruction until enough work can be recovered.

Allocator state

The TLSF state occupies 272 bytes inside the builder header:

offset 0     class bitmap: u64
offset 8     heads[64]: [u32; 64]
remaining    free-space and garbage counters

There are 16 first-level intervals and four second-level subdivisions per interval, giving 64 classes addressable by one u64 bitmap. The first range covers block sizes 16 through 31 bytes; later ranges scale by powers of two and split each range into quarters.

For the ordinary 63 classes, finding the next nonempty acceptable class is a bitmap and trailing-zero operation. Class 63 is the catch-all for blocks at or above 1 MiB; it may require a linear walk because its sizes have no further index subdivision.

The minimum tracked free payload is 16 bytes, and blocks are aligned to eight bytes.

Block layout

A used block has an effective eight-byte header:

size_status packs the physical size and flags:

When prev_free is set, the previous block’s size can be read at offset -4 from the current header. That word overlaps tail storage of the previous free block and is not valid when prev_free is clear.

A free block reuses payload words for intrusive links:

The overlap keeps metadata small but makes state bits authoritative. Debugging tools must not interpret the +4 word as both a live refcount and a free-list link.

Allocation

TLSF allocation proceeds as follows:

1. align the requested payload and include its header;
2. map that size to the first acceptable class;
3. use the bitmap to find the next nonempty class;
4. unlink a suitable block;
5. split it if the remainder can form a trackable block;
6. mark the allocated part used, initialize its refcount to 1, and clear the exposed payload;
7. update the following block’s prev_free state.

For ordinary classes the search is constant time with respect to the number of free blocks. A catch-all-class search can inspect multiple large blocks.

Freeing

A definite free first checks for the bump-mode fast paths described above. In TLSF mode it:

1. marks the block free;
2. unlinks and merges a free next neighbor;
3. uses the boundary tag to unlink and merge a free previous neighbor;
4. rewinds total_size if the result reaches the arena tail;
5. otherwise inserts the coalesced block into its size class;
6. repairs the next physical block’s boundary metadata.

Immediate coalescing prevents adjacent reusable holes from remaining separate. It does not promise that every request succeeds whenever the sum of all free bytes is sufficient; a request still needs one suitably sized contiguous block, or arena growth.

Potential garbage

Some ownership paths know that a value is no longer a direct live reference but cannot immediately prove that reclaiming it is safe or worthwhile. free_potential marks and accounts such storage without putting it on a free list. A later rebuild or precise collection resolves those candidates.

Potential garbage is not available for allocation. It is therefore tracked separately from reusable free bytes so growth and collection policy can respond to the actual pressure.

Fragmentation

Within a regular size class, the four-way subdivision limits class rounding to roughly one quarter of the surrounding power-of-two interval. That is not a global 25 percent fragmentation guarantee. Alignment, headers, live allocation shape, the large-block catch-all, unmerged deferred garbage, and capacity growth all affect total overhead.

The useful operational measures are:

• used body bytes;
• reusable free bytes and largest reusable block;
• potential garbage bytes;
• allocation and free counts;
• growth frequency and peak capacity.

Verification

The optional arena verifier walks physical blocks and independently examines the free lists. It checks, among other properties:

• sizes are aligned and remain inside total_size;
• free blocks occur exactly once in the correct list;
• used blocks do not occur in free lists;
• link symmetry and class bitmap state agree;
• boundary tags and prev_free flags agree;
• adjacent definite-free blocks have been coalesced.

Verification is a diagnostic build mode because a full walk would defeat the normal allocator’s hot-path cost model. Failure dumps allocator context and traps with a reason code rather than allowing known-corrupt metadata to drive a later write.

Ownership

TLSF decides where storage can be reused. It does not decide when an Atoll value is dead. That decision belongs to compiler-inserted ownership operations and the precise cycle collector described in Ownership.