[−][src]Module xalloc::tlsf
A dynamic external memory allocator based on the TLSF (TwoLevel Segregated Fit) algorithm^{1}.
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 GoodFit 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 firstlevel list that consists of pointers to secondlevel lists and
a bit field of type
T
where each bit indicates whether a free block is available in the corresponding secondlevel list or not. FLI
secondlevel 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 hardcoded 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 (64bit 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 (32bit 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 realtime systems." RealTime Systems, 2004. ECRTS 2004. Proceedings. 16th Euromicro Conference on. IEEE, 2004. ↩
Structs
Tlsf  TLSFbased 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 