Memory allocation in C
(This article first appeared in the August 1989 issue of Embedded Systems Programming magazine.)
The high cost of RAM ensures that most embedded systems will continue to experience a shortage of memory, The software you use to implement these systems will use queues, linked lists, task-control blocks, messages, I/O buffers, and other structures that require memory only for a short time and that may return it to serve other functions. This is known as dynamic memory allocation. If you're programming in C, this probably means using the memory allocation and release functions, malloc() and free().
Dynamic memory allocation and the structures that implement it in C are so universal that they're usually treated as a black box. In the real world of embedded systems, however, that may not always be desirable or even possible. Not all vendors of C compilers for embedded systems provide the memory allocation and release functions. We recently encountered a compiler that purported to have them but didn't document their interfaces. Because we needed tight control over the memory allocation process, we decided to write our own routines.
Rather than start from scratch, the simplest solution seemed to be to copy the allocator from Kernighan and Ritchie's The C Programming Language (Englewood Cliffs, N.J.: Prentice-Hall, 1988). Unfortunately, the functions presented in that inestimable resource are meant to interface to an operating system that will supply large blocks of memory on request. The algorithm we'll use here doesn't differ drastically from K&R's version, but it's clearer and better suited to an embedded system environment. The code works for twobyte address pointers but can easily be modified to handle any size.
A dynamic memory allocator should meet certain minimum requirements:
• All internal structures and linkage must be hidden from the call-only the number of bytes required should have to be specified.
• The order of calls to malloc() and free() shouldn't matter (the order of calls to free() need not be the reverse of the order of calls to malloc()).
• free() must prevent fragmentation of freed memory; all small, freed blocks must be combined into larger, contiguous blocks where possible.
• Overhead in memory and execution time must be minimized.
• An error condition must be returned if no memory is available.