RFC : Heap management using TLSF

[Tim Cussins]

On Tue, 2008-07-29 at 08:25 -0500, Joel Sherrill wrote:

> I would like to make sure I understand why this algorithm
> is better.  

Ok. I've had a look through the heap code at cvs head - hopefully I can
shed a little light on what we stand to gain by using TLSF.

TLSF provides 2 primary advantages over the existing heap
implementation:

(1) Low fragmentation.

RTEMS allocates using a "first-fit" algorithm. An RTEMS heap maintains a
single linked list of free blocks. When an allocation is performed, the
list is searched until a free block is found that can satisfy the
request.

There other blocks in the free list that may a better match. If we
allocated using one of these instead, we would reduce fragmentation.
This scheme is known as "best-fit", and has strong resistance to
fragmentation.

TLSF achieves an approximation to "best-fit" called "good-fit". This is
the result of a compromise that permits a fast, O(1) response time,
while preserving fragmentation resistance.

(2) Fast, bounded response time.

The allocation time of the RTEMS first-fit method is dependent on the
length and order of free blocks in the linked list. Allocation time
could be unacceptably long or unpredictable for some realtime
applications.

TLSF strives for fast allocation. Several linked lists are maintained,
each one representing  a size range. Free blocks are kept in the
appropriate linked list for their size.

Two levels of bitmaps are maintained to indicate which linked lists are
populated.

The TLSF algorithm searches through two levels of bitmaps to find a
linked list that is (a) populated, and (b) represents a range that is
the best fit for the requested block size. This operation is both fast,
and constant-time: especially fast when employing the bit-search
instructions that are available in many ISA's.

Once the linked list is found, the first entry of the linked list is
accepted as a "good-fit", and returned to the user. As both these
operations are constant-time, we therefore have fast, O(1) allocation.

Hope everyone followed that -  if not, the website has plenty of docs to
answer any outstanding questions. As for ambiguities in my writing, let
me have it :P I've cc'd Alfons (TLSF author) in case he wants to clarify
anything.

Cheers,
Tim