[][src]Module xalloc::tlsf

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 use u32 or u64 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 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>()Tsizememory consumption (bytes)
8 (64-bit system)u3216186
u321 << 10 (1KiB)1,110
u321 << 24 (16MiB)3,266
u321 << 30 (1GiB)4,190
u6416194
u641 << 10 (1KiB)1,118
u641 << 24 (16MiB)3,274
u641 << 30 (1GiB)4,198
u641 << 36 (64GiB)5,122
4 (32-bit system)u321698
u321 << 10 (1KiB)566
u321 << 24 (16MiB)1,658
u321 << 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.


  1. 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 Tlsf that represents a free/occpied memory block.

TlsfRegion

A handle type to a region allocated in a Tlsf.

Type Definitions

SafeTlsf

Tlsf that uses CheckedArena for rigorous memory safety check.

SafeTlsfRegion

Type alias of TlsfRegion for SafeTlsf.

SysTlsf

Tlsf that uses the system allocator for the internal storage allocation.

SysTlsfRegion

Type alias of TlsfRegion for SysTlsf.