Barnsley fern fractal

Thoughts on software architecture and development, and methods and techniques for improving the quality thereof.

David B. Robins (home)


Code Visions: Improving software quality
Buddy allocator

By David B. Robins tags: C++, Development, Embedded Saturday, January 24, 2015 09:32 EST (link)

Dynamic memory allocation is generally to be avoided on memory-constrained embedded devices, and we are very constrained: after the vendor's "soft device" we only get 6K of the total 16K RAM to use (a future chip upgrade will provide 32K, but we're months from getting it and will likely have to support the 16K chips for a while). However, we got to a point where it was necessary to allocate and deallocate buffers since we couldn't afford having them all exist statically at the same time. I had concerns about the built-in malloc being a first-fit allocator due to hard to predict fragmentation, so decided to go with a buddy allocator.

I have posted the source to GitHub with permission of my employer; it is buildable using SCons, and by default builds a project that runs a test suite using GoogleTest. Currently it is set to build for MinGW on Windows (patches to make more general welcome), and I build it using GNU tools for ARM embedded processors (GCC 4.8 and 4.9) on the device. The documentation there explains how to use in a project. I quote from the implementation notes:

The implementation sacrifices some speed to save memory by not using free lists; instead, a bitmap representing a contiguous array of the smallest block is used to track allocations, with 2 bits per smallest block (see above). The first (high) bit is set if the block is in-use; the second is set if it is the end of a logical block. For example, the initial state is 00 00 00 ... 00 01, meaning one free block the size of the whole arena. It can then be split recursively down to the minimum size by flagging the appropriate smallest-block as an end-block.

It does make use of C++11 features, and I appreciate some embedded projects may be stuck using ancient compilers stuck on C++98 or worse; I make no apologies for using modern tools; being able to use std::unique_ptr and RAII helps avoid leaks.

Note that I'm only using "copyright" to stop someone else from claiming the work and copyrighting it and causing problems for me; otherwise I'd make it public domain. I don't care what you do with the code, although attribution would be appreciated. I hope it is useful to someone out there.

Content on this site is licensed under a Creative Commons Attribution 3.0 License and is copyrighted by the authors.