Open source implementations of malloc

On (very) small embedded systems without a full OS (e.g. because there is only a scheduler), one can (and should) usually live without dynamic memory allocation. But sometimes, it is really needed or it is just more convenient. It is possible to write your own simple dynamic allocator on top of a pre-defined memory region, or you can look around for freely available public domain implementations. We will list a few possibilities here.

dlmalloc

One of the best and most used public domain versions available, is the one from Doug Lea at ftp://gee.cs.oswego.edu/pub/misc/malloc.c This is very usable if you have somewhat more memory (starting from about a 100KB in our opinion, and it can go up to the gigabyte range) to divide and conquer. It is quite advanced and thus has some management overhead which makes it somewhat less usable if managing only a few tens (or less) kilobytes.

Tlsf

There is also a “tlsf” (two level segregated fit) memory allocator implementation here: http://tlsf.baisoku.org/ which features:

• O(1) cost for malloc, free, realloc, memalign, which could be important for real-time systems,
• Extremely low overhead per allocation (4 bytes),
• Low overhead per pool (~3kB),
• Low fragmentation,
• And it compiles to only a few kB of code and data,
• But if you have only a few KB to work with, this RAM memory overhead is still too much…

Freertos samples

Freertos (version 8 at the time of writing) also provides 2 example implementations that can be very useful:

• heap_2.c (does not combine adjacent free blocks) and
• heap_4.c (does indeed combine adjacent free blocks).

The overhead is very limited and the code is clearly suitable for smaller memory amounts. There is also a special version heap_1.c which does not implement “free” which is useful only in particular cases.

Ralph Hempel also wrote a possible candidate which can be retrieved from http://hempeldesigngroup.com/embedded/stories/memorymanager/. The overhead is also small and the targeted applications are indeed systems with smaller memory capacities.

Simple Malloc / Free

Another simple (and our personal favorite) implementation, we stumbled upon – loosely based upon the K & R book 2nd edition, Chapter 8, Section 7, Example Storage Allocator – can be found here:
http://www.flipcode.com/archives/Simple_Malloc_Free_Functions.shtml

It is

• simple,
• small,
• has very low overhead (the lowest we encountered),
• implements a “first-fit”
• it compacts (aggregates free memory) by scanning the entire region on request or when an allocation request does not find sufficient free memory,
• it fits our purpose.

but it

• does not have a strategy to avoid memory fragmentation (not a “best-fit”),
• does not implement a time deterministic strategy to find a free memory block,
• does not have protection or detection against memory boundary overwrites.