Dynamic memory allocator

Dynamic storage allocation (DSA) algorithms increase the flexibility and functionalities of applications. However, the use of DSA has been considered a source of indeterminism in the real-time domain, due to the unconstrained response time of DSA algorithms and the fragmentation problem.

Nowadays, new real-time applications require more flexibility: the ability to adjust system configuration in response to workload changes and application reconfiguration. This aspect adds new value to the definition and implementation of dynamic storage allocation algorithms.

Considering these reasons, new DSA algorithms with a bounded and acceptable timing behaviour must be developed to be used by Real-Time Operating Systems (RTOS). The Two-Level Segregated Fit memory allocator (TLSF) algorithm is developed specifically to be used by RTOS and provides explicit allocation and deallocation of memory blocks with a temporal cost Θ(1).

TLSF

TLSF (Two-Level Segregate Fit) is a general purpose dynamic memory allocator specifically designed to meet real-time requirements:

  • Bounded Response Time: The worst-case execution time (WCET) of memory allocation and deallocation has got to be known in advance and be independent of application data. TLSF has a constant cost Θ(1).
  • Fast: Additionally to a bounded cost, the allocator has to be efficient and fast enough. TLSF executes a maximum of 168 processor instructions in a x86 architecture. Depending on the compiler version and optimisation flags, it can be slightly lower or higher.
  • Efficient Memory Use: Traditionally, real-time systems run for long periods of time and some (embedded applications), have strong constraints of memory size. Fragmentation can have a significant impact on such systems. It can increase dramatically, and degrade the system performance. A way to measure this efficiency is the memory fragmentation incurred by the allocator. TLSF has been tested in hundreds of different loads (real-time tasks, general purpose applications, etc.) obtaining an average fragmentation lower than 15 %. The maximum fragmentation measured is lower than 25%.

TLSF has been included in several Linux distributions and applications. Although TLSF works rather well in many scenarios, it stands out in applications with hard/soft real-time application which uses explicit memory allocation with high flexibility requirements due to a high variability of the data size or adaptability to new situations. Some examples are:

  • - RTOS dynamic memory management
  • - Multimedia applications
  • - Routers, Switches, ...
  • - 3D reconstruction and rendering in video system applications
  • - Games

TLSF has shown excellent experimental results with respect to both response time and fragmentation. The use of bitmaps and segregated lists to access to different free memory blocks of different size in an efficient and predictable way, permits to obtain constant cost for the basic operations malloc and free. Also, the analysis of the proposed data structures shows a low and bounded amount of internal fragmentation, dependent on the value chosen for the second level index.

The proposal has been compared with other DSA algorithms obtaining very encouraging results. This work started thanks to an EU founded project called OCERA and has continued in FRESCOR.