TLSF: two-level segregated fit O(1) allocator
TLSF: two-level segregated fit allocator which guarantees O(1) time. This implementation provides two variations: TLSF-INT which inlines the block headers and TLSF-EXT which uses externalised block header allocation. Therefore, TLSF-EXT can be used to manage arbitrary resources, e.g. address or disk space, unique IDs within a limited range, etc.
Reference:
M. Masmano, I. Ripoll, A. Crespo, and J. Real.
TLSF: a new dynamic memory allocator for real-time systems.
In Proc. ECRTS (2004), IEEE Computer Society, pp. 79-86.
The implementation is written in C99 and distributed under the 2-clause BSD license.
tlsf_t *tlsf_create(uintptr_t baseptr, size_t size, unsigned mbs, tlsf_mode_t mode)
NULL
is returned.TLSF_INT
, then the given base pointer is treated as
accessible memory area and the block headers will be inlined within the
allocated blocks of memory.TLSF_EXT
, then the block headers will be externalised
and allocations can be made only through the tlsf_ext_alloc
and
tlsf_ext_free
functions. The allocator will not attempt to access the
given space and malloc(3) will be used to allocate the block headers.void tlsf_destroy(tlsf_t *tlsf)
void *tlsf_alloc(tlsf_t *tlsf, size_t size)
size
bytes of memory and returns a
pointer to it. On failure, returns NULL
.void tlsf_free(tlsf_t *tlsf, void *ptr)
tlsf_blk_t *tlsf_ext_alloc(tlsf_t *tlsf, size_t size)
size
of space and returns a reference
(pointer to an opaque tlsf_blk_t
type). On failure, returns NULL
.void tlsf_ext_free(tlsf_t *tlsf, tlsf_blk_t *blk)
uintptr_t tlsf_ext_getaddr(const tlsf_blk_t *blk, size_t *length)
The TLSF-INT requires at least word-aligned base pointer; it also guarantees the word-aligned allocations. The allocator uses a minimum allocation unit of 32. That is, any given sizes will be rounded up to the minimum block size (MBS) of 32 bytes/units.
The maximum allocation size is limited to the half of the space represented by the word size of the CPU architecture. On 32-bit systems, it is 2^31 (~2 billion) and on 64-bit systems it is 2^63.
The following is an illustration of using TLSF as a memory allocator backed by a memory-mapped area:
#include <tlsf.h>
tlsf_t *tlsf;
void *baseptr;
struct obj *obj;
baseptr = mmap(...);
if (baseptr == MAP_FAILED)
err(EXIT_FAILURE, "mmap");
tlsf = tlsf_create(baseptr, space_size, 0, TLSF_INT);
if (!tlsf)
err(EXIT_FAILURE, "tlsf_create");
obj = tlsf_alloc(tlsf, sizeof(struct obj));
...
tlsf_free(tlsf, obj);
The following is an illustration of TLSF-EXT use:
tlsf_t *tlsf;
tlsf_blk_t *blk;
uintptr_t base_addr;
base_addr = get_some_address_space();
tlsf = tlsf_create(base_addr, space_size, 0, TLSF_EXT);
if (!tlsf)
err(EXIT_FAILURE, "tlsf_create");
blk = tlsf_ext_alloc(tlsf, size);
if (blk) {
uintptr_t off;
size_t len;
off = tlsf_ext_getaddr(blk, &len);
do_something(base_addr, off, len);
...
tlsf_ext_free(tlsf, blk);
}
Just build the package, install it and link the library using the
-ltlsf
flag.
cd pkg && make rpm
cd pkg && make deb