TLSF Dynamic Memory Allocation

Overview

TLSF (Two-Level Segregated Fit) is a dynamic memory allocator suited for real-time systems. It is a good-fit algorithm with a bound response time O(1) for any number of managed memory blocks.

Free blocks of memory are organized in lists each containing blocks of a specific size range. Requested blocks are searched in the list with sizes equal or greater the requested size, remaining memory is split up if neccessary and sorted back into the list. Freed blocks are merged with neighboring free blocks and also put back into the list.

The remaining memory from the end of global declared variables to the start of the stack spaces and also external memory (Xram), if available, is managed by the library (configurable).

How to use it

Setup

Create an inc subfolder to your project and copy the files os_common.inc, os_memory.inc and os_malloc_tlsf.inc into the folder.

Include the library:

' any const option must be placed above the file include
Const Os_mem_free_start = ###                         ' mandatory
$include "inc\os_malloc_tlsf.inc"

The start adress of the free memory area can not be determined automatically (Bascom-AVR 2.0.8.1). It can be found by examining the compile report (with setting Options->Compiler->Output->Show internal variables enabled), the last variable (with the highest adress) plus the byte size is the adress of the first unused byte.

Compiler report example

Here is a (shortened) example of a compiler report, and where the address could be found. In this example, the RAM start address should be set to at least 169 dec.

Report       : chronos
Date         : 05-20-2013
Time         : 01:54:06

Compiler     : BASCOM-AVR LIBRARY V 2.0.7.6
Processor    : M32
SRAM         : 800 hex
EEPROM       : 400 hex
ROMSIZE      : 8000 hex

...

--------------------------------------------------------------------------------
Variable                         Type            Address(hex)   Address(dec)
--------------------------------------------------------------------------------

...

OS_CRITICAL_NESTING_LEVEL        Byte              0060          96
OS_EVENT_TASK                    Word              0061          97
MALLOC_FREE_POINTER              Word              0063          99
OS_SCHED_RUNNING_WEIGHT          Byte              0065          101
OS_SCHED_LIST_HEAD               Word              0066          102
OS_SCHED_PREEMPTED_TASK          Word              0068          104
OS_TASK_ACTIVE                   Word              006A          106
OS_TASK_TEMPBYTE_ISR             Byte              006C          108
OS_TASK_TEMPWORD_ISR             Word              006D          109
OS_TASK_TEMPWORD2_ISR            Word              006F          111
OS_TIMER_SYSTEMTIME              Dword             0071          113
OS_TIMER_LISTHEAD                Word              0075          117
OS_TIMER_NEXT_EVENT              Word              0077          119
OS_TIMER_ELAPSED_TIME            Word              0079          121
OS_TIMER_ENABLE_KERNEL           Byte              007B          123
OS_INT_TABLE                     Word (20)         007C          124
TASKOBJECT                       Word              00A4          164
TASK_1_COUNTER                   Byte              00A6          166
TASK_2_COUNTER                   Byte              00A7          167
___LCDCOUNTER                    Byte              00A8          168     <---

--------------------------------------------------------------------------------
Constant                         Value
--------------------------------------------------------------------------------
SREG                             &H3F
SPH                              &H3E
SPL                              &H3D

...

Managing memory

The library works with memory adresses. If a memory request of given size can be served (consecutive block of free memory has been found), the adress of the start of the block is returned. For a size request bigger than what is managed by the algorithm, as fallback a simple search for a block of suitable size through the last list will be performed (O(n)). If the request can't be fullfilled, the value 0 is returned. The application has to check for that return value and react accordingly, it is also responsible not to write outside of the requested block of memory. Allocated memory is NOT cleared (set to 0) by the library.

With no external memory, 16 bit adress width (Word variable type) is used, with external memory 24 bits are used (DWord type).

Dim Myblockofmemory As [Word/Dword]
Myblockofmemory = Malloc([Size])
If Myblockofmemory = 0 Then
   ' memory allocation error handling (not enough free memory)
End If

When the block is no longer needed, it must be returned to the free memory pool by calling:

Free Myblockofmemory

Interface description

The following constants have to be defined prior to including the library. The values shown here are default values if the constant is not defined by the user.

Const Os_mem_free_start = [&H200/with XRAM: &H2000]

MANDATORY parameter, as described in Setup. For reasons, it has also default values.

Const Os_tlsf_fli_offset = 4

Start of first level block size ranges in powers of 2. Size = 2 ^ (Os_tlsf_fli_offset + 1); with a default value of 4, first level sizes start at 32.

Const Os_tlsf_max_fli = [10/with XRAM: 12]

End of first level block size ranges. Size = 2 ^ Os_tlsf_max_fli; defaults without XRAM to 1024, with XRAM to 4096.

Const Os_tlsf_max_log2_sli = 3

Log2 of Second level range count (max. 3). Since the search process is speed up by using bitmaps, this value should match the platform's word width. For 8-Bit AVR it is 2 ^ 3 = 8.

These 3 parameters result in the following block size ranges (default values, no XRAM):

First level | Second level
(+4+1)      |   0       1       2       3       4       5       6       7
--------------------------------------------------------------------------
0 |    32   |   0       4       8      12      16      20      24      28
1 |    64   |  32      36      40      44      48      52      56      60
2 |   128   |  64      72      80      88      96     104     112     120
3 |   256   | 128     144     160     176     192     208     224     240
4 |   512   | 256     288     320     352     384     416     448     480
5 |  1024   | 512     576     640     704     768     832     896     960

Index 0 is not used, Index 1 is a list containing blocks up to a size of 4 Bytes, Index 2 list has sizes from 4 to 8 Bytes, Index 8 contains 16-32 Byte blocks, ...

Const Debug_level_tlsf = 0

Set debug output verbosity, 0 = no debug, 1 = Print out available memory each Malloc/Free, 2 = Print out memory pool overview, 3 = Print additional info during Malloc/Free. If debug outputs are activated, option Os_task_debug_metrics is also declared.

Const Os_task_dbg_metrics = 0

Declare Const (value doesn't matter) to enable tracking of available memory. If activated, a variable will be created:

#if Os_big_ram = False
   Dim Available_memory As Word
#else
   Dim Available_memory As Dword
#endif

#if Os_big_ram = False
Function Malloc(byval Size As Word) As Word
#else
Function Malloc(byval Size As Dword) As Dword
#endif

Request a block of memory of given size. Returns the starting memory adress or zero if not enough free memory left.

#if Os_big_ram = False
Sub Free(byref Block As Word)
#else
Sub Free(byref Block As Dword)
#endif

Returns a previously allocated block to the free memory pool.

#if Os_big_ram = False
Function Os_malloc_blocksize(byref Block As Word) As Word
#else
Function Os_malloc_blocksize(byref Block As Dword) As Dword
#endif

Returns the size of a block.

Sub Os_malloc_clear()

Empties all lists, resets the allocator

Sub Os_malloc_init()

Initializes the allocator. This is done when the library is included, in standard applications, it is not needed to call. However, to reset the allocator, use Os_malloc_clear before calling Os_malloc_init.

Samples

WIP

Download

• Memory Allocators version 0.1

Change log

Version 0.1 (##.##.2019)

• Initial release.