Crate rlsf[−][src]
Expand description
This crate implements the TLSF (Two-Level Segregated Fit) dynamic memory allocation algorithm¹. Requires Rust 1.51.0 or later.
-
Allocation and deallocation operations are guaranteed to complete in constant time. TLSF is suitable for real-time applications.
-
Fast and small. You can have both. It was found to be smaller and faster² than three randomly chosen
no_std
-compatible allocator crates. -
The memory pool is provided by an application. Examples of potential memory pool sources include: a
static
array for global memory allocation, a memory block allocated by another memory allocator for arena allocation. -
This crate supports
#![no_std]
. It can be used in bare-metal and RTOS-based applications.
¹ M. Masmano, I. Ripoll, A. Crespo and J. Real, “TLSF: a new dynamic memory allocator for real-time systems,” Proceedings. 16th Euromicro Conference on Real-Time Systems, 2004. ECRTS 2004., Catania, Italy, 2004, pp. 79-88, doi: 10.1109/EMRTS.2004.1311009.
² Compiled for and measured on a STM32F401 microcontroller using FarCri.rs.
Measured Performance
Limitations
-
It does not support concurrent access. A whole pool must be locked for allocation and deallocation. If you use a FIFO lock to protect the pool, the worst-case execution time will be
O(num_contending_threads)
. You should consider using a thread-caching memory allocator (e.g., TCMalloc, jemalloc) if achieving a maximal throughput in a highly concurrent environment is desired. -
Free blocks cannot be returned to the underlying memory system efficiently.
Examples
Tlsf
: Core API
use rlsf::Tlsf; use std::{mem::MaybeUninit, alloc::Layout}; let mut pool = [MaybeUninit::uninit(); 65536]; // On 32-bit systems, the maximum block size is 16 << FLLEN = 65536 bytes. // The worst-case fragmentation is (16 << FLLEN) / SLLEN - 2 = 4094 bytes. // `'pool` represents the memory pool's lifetime (`pool` in this case). let mut tlsf: Tlsf<'_, u16, u16, 12, 16> = Tlsf::INIT; // ^^ ^^ ^^ // | | | // 'pool | SLLEN // FLLEN tlsf.insert_free_block(&mut pool); unsafe { let mut ptr1 = tlsf.allocate(Layout::new::<u64>()).unwrap().cast::<u64>(); let mut ptr2 = tlsf.allocate(Layout::new::<u64>()).unwrap().cast::<u64>(); *ptr1.as_mut() = 42; *ptr2.as_mut() = 56; assert_eq!(*ptr1.as_ref(), 42); assert_eq!(*ptr2.as_ref(), 56); tlsf.deallocate(ptr1.cast(), Layout::new::<u64>().align()); tlsf.deallocate(ptr2.cast(), Layout::new::<u64>().align()); }
GlobalTlsf
: Global Allocator
#[cfg(all(target_arch = "wasm32", not(target_feature = "atomics")))] #[global_allocator] static A: rlsf::SmallGlobalTlsf = rlsf::SmallGlobalTlsf::INIT; let mut m = std::collections::HashMap::new(); m.insert(1, 2); m.insert(5, 3); drop(m);
Details
Changes from the Original Algorithm
- The end of each memory pool is capped by a sentinel block (a permanently occupied block) instead of a normal block with a last-block-in-pool flag. This simplifies the code a bit and improves its worst-case performance and code size.
Modules
int | Provides |
Structs
FlexTlsf | A wrapper of |
GlobalAllocAsFlexSource | Wraps |
GlobalTlsf | WebAssembly and non-atomics , or Unix
|
SmallGlobalTlsfOptions | WebAssembly and non-atomics , or Unix
|
Tlsf | The TLSF header (top-level) data structure. |
Constants
GRANULARITY | The allocation granularity. |
Traits
FlexSource | The trait for dynamic storage allocators that can back |
GlobalTlsfOptions | WebAssembly and non-atomics , or UnixThe options for |
Init | Provides a constant default value. |
Type Definitions
SmallGlobalTlsf | WebAssembly and non-atomics , or UnixAn instantiation of |