Dynamic memory Allocator
Dynamic Storage Allocation or Dynamic memory management [WP] or simply the "malloc()/free()" problem.
Why we did it?
While improving the today extincted RTLinux operating system in the framework of the working on the OCERA project (2004, EU FP6) we faced the problem of handling dynamic memory, i.e. malloc() and free(), in a real-time environment.
At that time, it was generally accepted that dynamic memory management was intrinsically a "dynamic" and so unbounded problem. Both, the temporal cost of the fragmentation would depend mostly on the sequence of malloc/free operations, which is basically "unpredictable". It would be possible to construct (craft) a sequence of requests and releases of memory blocks such that it causes a large fragmentation and also a very long delay on a malloc operation.
It is important to point out that our design goal was to have a O(1) allocator. We shift our focus from the common goal of improving the average case or increase the throughput to the very different goal of minimising the worst case. Obviously, there are other allocators (for example, the very good DLmalloc done by Douglas Lee) which is faster in the mean time than TSLF.
The nice fact about TLSF is that the code DOES NOT HAVE LOOPS, of any kind. That is, the program counter always moves forward!.
To be honest, when handling multiple areas of memory we decided to use a loop for simplicity, because this feature is only used in non-real-time applications. By the way, it is also possible to handle multiple areas in O(1).
Is it possible to have a O(1) malloc?
Yes. But the most surprising fact is that the price to be paid is to have a "Low Fragmentation". Yes, you have read it correctly.
Internal data structures example.
Most researchers had focused on the "fragmentation problem". There was a common misconception that the fragmentation and the time cost are inversely related. That is, the less fragmentation the more complex (costly) would be the allocation algorithm.
Where is it used and What others say
We released the code under open source (GPL and others); there is a porting of the code released under the BSD; there are several variants to improve cache efficiency and other issues. It is almost impossible to know where the TLSF is used.
We know just some products: the Xen hypervisor, the ZRAM device of Linux (which is a key element of the ZRAM device).
Valtteri HeikkilÃ¤: "Our results confirm that TLSF is one of the best allocators for real-time systems in terms of performance and fragmentation."
Philippe Stellwag: "Preliminary tests show that we can outperform established DSA implementations in terms of predictability, like the famous TLSF memory allocator."
What is next?
Dynamic memory is a fascinating topic. Although it is an old computer issue, there is still a lot of research to be done and new solutions to be discovered. For example, the idea of "fragmentation" is still ill-defined and incorrectly understood, which impedes further advances in that line.