umm_malloc: very efficient memory allocator for embedded systems
I just want to share the efficient memory allocator I've found and tested: https://github.com/dimonomid/umm_malloc. I use it on PIC32 processor, but it should work on any 16- and 8-bit device (it was initially written for ARM7 embedded processor).
I was seriously beaten by fragmentation with default allocator that comes with XC32 compiler (which is GCC-based) : my project often allocates blocks of various size, from several bytes to several hundreds of bytes, and sometimes I faced “out of memory” error. My PIC32 device has total 32K of RAM, and 8K from it is used for heap. At the particular moment there is more than 5K of free memory, but default allocator has maximum non-fragmented memory block just of about 700 bytes, because of fragmentation. This is too bad, so I decided to look for more efficient solution.
I already was aware of some allocators, but all of them have some limitations (such as block size should be a power or 2, and starting not from 2 but from, say, 128 bytes), or were just plain buggy. Every time before, I had to switch back to the default allocator.
But this time, I'm lucky: I've found this one: http://hempeldesigngroup.com/embedded/stories/memorymanager/ by Ralph Hempel.
When I tried this memory allocator, in exactly the same situation with 5K of free memory, maximum non-fragmented memory block is more than 3800 bytes! It was so unbelievable to me (comparing to 700 bytes), and I performed hard test: device worked heavily more than 30 hours. No memory leaks, everything works as it should work.
So I completely switched to umm_malloc, and I'm quite happy with it.
I just had to perform a couple of minor changes: configuration was a bit buggy when macro
UMM_TEST_MAIN is not defined, so, I've created the github repository (the link is at the top of this post). Now, user dependent configuration is stored in separate file
I haven't got deeply yet in the algorithms applied in this allocator, but it has very detailed explanation of algorithms, so anyone who is interested can look at the top of the file
umm_malloc.c. At least, “binning” approach should give huge benefit in less-fragmentation: http://g.oswego.edu/dl/html/malloc.html
I believe that anyone who needs for efficient memory allocator for microcontrollers, should at least try this one.
Great thanks to Ralph Hempel.