A dynamic external memory allocator based on the TLSF (Two-Level Segregated Fit) algorithm1.
Tis an integer type used to represent region sizes. You usually use
Ais 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:
mappingthe 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
mapping(s) != mapping(S) && s > S.
- There exists a free space with a size
mapping(s) == mapping(S) && s < S.
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
Twhere each bit indicates whether a free block is available in the corresponding second-level list or not.
FLIsecond-level lists each of which consists of
1 << SLIpointers 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
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)
PS = size_of::<usize>()).
The following table shows the estimated baseline memory consumption of
SysTlsf for common configurations.
|memory consumption (bytes)|
Note that this does not include the overhead incurred by the system memory allocator.
Furthermore, each allocated/free region (represented by
consumes a certain amount of memory. The exact size of
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);
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. ↩
TLSF-based external memory allocator.
Internal data structure used by
A handle type to a region allocated in a