tlsf-pmr is a memory resource for use with polymorphic_allocator that uses the Two-Level Segregated Fit algorithm as an allocation scheme. This algorithm is able to allocate memory in $O(1)$ time, and is thus suitable in contexts where dynamic memory allocation with deterministic latency is needed, e.g. real-time operating systems or audio applications.

The original implementation was implemented in C with a GPL license. This project is based off of a clean-room implementation by mattconte with a more permissive license, and is adapted to use C++ best practices and enable a cleaner API. It has no external dependencies aside from the standard library, so incorporating it into your project should be very straightforward.

Requirements

• C++17 compiler and standard library. As of 2024, you can use all 3 major standard library implementations (libstdc++ 9.0+, libc++ 16+ or MSVC STL 19.13+). See this page for details.
• 32-bit or 64-bit architecture. 16-bit is not supported at this time but may be added in the future.

Usage

The main class in tlsf-pmr is tlsf_resource, which has a API similar to that of std::pmr::unsynchronized_pool_resource. It can be used with any container that accepts the standard library memory allocator API when combined with std::polymorphic_allocator. This includes standard library containers such as std::vector. Note that there is memory overhead from the memory block headers. Each block header requires 32 bytes of memory.

using namespace tlsf;
{
    tlsf_resource resource(5000); //pool with 5000 bytes of memory
    std::pmr::polymorphic_allocator<int> alloc(&resource);

    //std::pmr::vector<T> is a type alias for std::vector<T, std::pmr::polymorphic_allocator<T>>
    std::pmr::vector<int> vec(alloc); //vector now uses the allocator

    vec.push_back(50);
} //all memory is automatically deallocated when tlsf_resource exits the scope.

std::pmr::vector<int> bad_unsafe_function() {
    tlsf_resource resource(5000); 
    std::pmr::polymorphic_allocator<int> alloc(&resource);

    std::pmr::vector<int> vec(alloc);

    return vec; //resource exits scope and frees memory -- attempting to use vec will result in use-after-free
}

Constructor options

The size of the pool and the upstream resource can be specified using pool_options. When the pool memory is exhausted or is unable to satisfy an allocation request, the allocator will fall back to the upstream resource to allocate memory, in a similar fashion as std::pmr::unsynchronized_pool_resource.

See this talk by Andrei Alexandrescu for more information about allocator design.

If only pool_options is specified, then the memory resource will be used to allocate the pool AND to perform upstream allocations.

using namespace tlsf;

pool_options options {
    50'000'000, //size of pool, in bytes
    std::pmr::new_delete_resource() //memory resource used to allocate the pool
};

tlsf_resource resource(options); //tlsf_resource will use new_delete_resource to allocate pool and as upstream resource

If a memory resource is specified separately from the pool_options, then this memory resource will be used as the upstream resource for fallback allocation instead. The resource specified in pool_options will still be used to allocate the TLSF memory pool.

pool_options options {
    50'000'000, //size of pool, in bytes
    std::pmr::new_delete_resource() //memory resource used to allocate the pool
};

tlsf_resource resource(options, std::pmr::null_memory_resource()); //will throw std::bad_alloc when memory pool is exhausted 

Creating new memory pools

If tlsf_resource was not initialized with a memory pool, or a new pool needs to be created, create_memory_pool will allocate a new memory pool using pool_options and optionally will also replace an underlying memory pool.

by default, create_memory_pool throws a std::runtime_error if a pre-existing pool will be replaced. This can be disabled by setting the second argument to true.

pool_options options2 {
    10'000'000,
    std::pmr::get_default_resource()
};

//allocate a new memory pool.
//will throw std::runtime_error if there is an underlying pool unless the second argument is true
resource.create_memory_pool(options2, true) 

Working with memory pools directly

If you need a TLSF allocator but do not want to use the standard library allocator API, you can work directly with the underlying memory pool, tlsf_pool. It has a lower-level API consisting of malloc_pool, free_pool, realloc_pool and memalign_pool. These have the same API as the corresponding cstdlib functions.

It is recommended that tlsf_pool be constructed through the static create method, which returns a std::optional object that is empty if the pool memory allocation has failed.

#include <optional>

// ...

std::optional<tlsf_pool> pool = tlsf_pool::create(50'000'000); //construct pool with 50M bytes - uses new and delete by default

//check if pool initialization was successful
if (pool)
    void* memory = pool->malloc_pool(5000);

tlsf_pool will also accept pool_options in the constructor.

std::pmr::monotonic_buffer_resource upstream(50'000'000); 

pool_options options {
    5'000'000,
    &upstream,
};

std::optional<tlsf_pool> pool = tlsf_pool::create(options); //use monotonic_buffer_resource to allocate pool

If you don't want to use std::optional, then you can also use the tlsf_pool constructor directly. In this case, you must manually check that the pool was successfully allocated, as tlsf_pool does not enforce it by itself:

tlsf_pool pool(5'000'000); //create pool

//Must manually check that allocation was successful. 
if (!pool.is_allocated()) { 
    //fallback if allocation fails
}

As with the create method, the tlsf_pool constructor also accepts pool_options as an argument:

pool_options options {
    5'000'000,
    &upstream,
};

tlsf_pool pool(options); //initialize using pool_options

//Allocation can still fail silently with a custom memory allocator
if (!pool.is_allocated()) {
    //...
}

Error handling

The approach to error handling depends on the abstraction level. If memory allocation fails:

• The higher-level tlsf_resource and synchronized_tlsf_resource will throw exceptions.
• The lower-level tlsf_pool will return nullptr or false values, depending on the method.

This is to maintain consistency with C++-style and C-style APIs, respectively.

Disclaimer on performance

Note that deterministic latency $\neq$ good performance! In fact, these two qualities are often (but not always) to the detriment of each other. Instrument and test your code before drawing conclusions, and make decisions on your allocation scheme based on your specific combination of hardware, operational requirements and test results. Make sure you actually need deterministic latency—in my experience, situations that truly require it are quite rare.

Thread safety

The TLSF allocator was not originally designed for multithreaded applications, and tlsf_resource is not thread-safe. Instead, synchronized_tlsf_resource should be used. The API is the same as the standard tlsf_resource. It has a very similar implementation, but uses a naive lock during allocation and deallocation, and as such it is very simple at the cost of potential performance from more finely-grained locking strategies.

Keep in mind that any kind of mutual exclusion will undermine the execution determinancy provided by the TLSF allocation scheme. In practice, the extent to which this matters depends on your specific application and requirements. It may be advisable to instead use a separate tlsf_resource for each thread, while ensuring the upstream resource (if any) is thread-safe.

Memory exhaustion

As this is a pool-based memory resource, the amount of memory available is fixed and determined upon initialization. When the pool is exhausted, the memory resource defers to a secondary memory resource to satisfy further allocations. The default resource is std::pmr::null_memory_resource, which simply throws std::bad_alloc if an allocation is attempted. In other words, if the pool is exhausted the default behavior is to throw a failure to allocate exception upon further allocation attempts. This behavior can be changed by simply providing another memory resource during allocation.

Installation

A CMakeLists.txt file is provided for easy usage. Start by adding this repository to your project in the manner of your choosing (e.g. git submodule, FetchContent, etc).

Then link against it using target_link_libraries.

target_link_libraries(
    <your-project>
    tlsf_resource
    ...
)

Contact

Any questions or suggestions can be submitted as a Github issue. However, I only check Github sporadically, so there may be a lengthy delay before you receive a response. Alternatively, you can email me at dq@liem.ca.