Module xalloc::tlsf

Expand description

A dynamic external memory allocator based on the TLSF (Two-Level Segregated Fit) algorithm¹.

Type parameters

T is an integer type used to represent region sizes. You usually use u32 or u64 for this.
A is a memory arena type used to allocate internal block structures.

This TLSF allocator implements a Good-Fit strategy. In order to achieve the O(1) execution time, only the first element of each free space list is examined. As a result, allocations are not guaranteed to succeed even if there is an enough free space if the following condition is met:

There is no free space that is larger than the requested size by a certain amount.
There is a free space that is almost as large as the requested size.

Or more strictly:

Let S, mapping the number of bytes to allocate and the mapping function that calculates the indexes into the TLSF data structure given the size of a block, respectively. There exists no free space with a size s where mapping(s) != mapping(S) && s > S.
There exists a free space with a size s where mapping(s) == mapping(S) && s < S.

Memory Overhead

A TLSF allocator requires the following internal storage to operate (some details are excluded):

A variable storing the size of the heap.
One first-level list that consists of pointers to second-level lists and a bit field of type T where each bit indicates whether a free block is available in the corresponding second-level list or not.
FLI second-level lists each of which consists of 1 << SLI pointers to free blocks and a bit field of SLI-bit wide where each bit indicates whether the corresponding entry of the free block is valid or not.

When the heap size size is a power of two and larger than 1 << SLI, FLI can be written as log2(size) + 1 - SLI. SLI is hard-coded to 4 in this implementation. Using these, the baseline memory consumption can be calculated by the formula 2 * T + 3 * PS + FLI * (3 * PS + SLI * P + SLI / 8) (where PS = size_of::<usize>()).

The following table shows the estimated baseline memory consumption of SysTlsf for common configurations.

`size_of::<usize>()`	`T`	`size`	memory consumption (bytes)
`8` (64-bit system)	`u32`	`16`	186
	`u32`	`1 << 10` (1KiB)	1,110
	`u32`	`1 << 24` (16MiB)	3,266
	`u32`	`1 << 30` (1GiB)	4,190
	`u64`	`16`	194
	`u64`	`1 << 10` (1KiB)	1,118
	`u64`	`1 << 24` (16MiB)	3,274
	`u64`	`1 << 30` (1GiB)	4,198
	`u64`	`1 << 36` (64GiB)	5,122
`4` (32-bit system)	`u32`	`16`	98
	`u32`	`1 << 10` (1KiB)	566
	`u32`	`1 << 24` (16MiB)	1,658
	`u32`	`1 << 30` (1GiB)	2,126

Note that this does not include the overhead incurred by the system memory allocator.

Furthermore, each allocated/free region (represented by TlsfBlock) consumes a certain amount of memory. The exact size of TlsfBlock might differ among compiler versions due to structure layout optimizations, but we can know the lower bound:

use xalloc::tlsf::TlsfBlock;
use std::mem::size_of;
assert!(size_of::<TlsfBlock<u32, u32>>() >= 25);
assert!(size_of::<TlsfBlock<u32, u64>>() >= 41);
assert!(size_of::<TlsfBlock<u64, u64>>() >= 49);

Performance

The allocation throughput is mostly equivalent to that of jemalloc.

Masmano, Miguel, et al. “TLSF: A new dynamic memory allocator for real-time systems.” Real-Time Systems, 2004. ECRTS 2004. Proceedings. 16th Euromicro Conference on. IEEE, 2004. ↩