ChronOS Memory Management: TLSF

Overview

The TLSF (Two Level Segregated Fit) memory allocator is an algorithm for dynamic allocation/deallocation of memory blocks with a runtime of O(1) (bounded response time). That means, the number of blocks managed by the algorithm has no effect on the time it takes to perform a (de-)allocation procedure. It uses two hierarchically bitmaps to store lists of blocks with specific sizes.

On allocation, it searches for the first a free block in a list at least one size class greater (=> good fit allocator). If possible, the block is splitted up, the remaining free memory is put back in the free lists. On deallocation, the freed block is coalesced with neighboring free blocks, the resulting block is put back in the free lists.

It also has a low memory fragmentation (15%) and a low block overhead (4 to 8 bytes, 4 bytes header and 4 byte block align).

Further Reading

• TLSF main page
• Public Domain implementation