Module xalloc::tlsf
[−]
[src]
A dynamic external memory allocator based on the TLSF (Two-Level Segregated Fit) algorithm1.
Type parameters
T
is an integer type used to represent region sizes. You usually useu32
oru64
for this.A
is a memory arena type used to allocate internal block structures.
A Caveat
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 sizes
wheremapping(s) != mapping(S) && s > S
. - There exists a free space with a size
s
wheremapping(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 of1 << SLI
pointers to free blocks and a bit field ofSLI
-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 lower than jemalloc by roughly 10%.
-
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. ↩
Structs
Tlsf |
TLSF-based external memory allocator. |
TlsfBlock |
Internal data structure used by |
TlsfRegion |
A handle type to a region allocated in a |
Type Definitions
SafeTlsf |
|
SafeTlsfRegion |
Type alias of |
SysTlsf |
|
SysTlsfRegion |
Type alias of |