Here is a handy way to manage buffers, using a singly linked list. It works for small embedded systems where there is no heap.
With no heap, we don’t have malloc() and free() to get buffers. Also, we don’t want a performance penalty if we call malloc() when we need to get a buffer. So, the buffer pool is super fast, low overhead and statically allocated.
First we need a static array of buffers. The array works if all of the buffers are the same size. So we declare a struct with, for example, 256 bytes array for data storage. Next we make an array of 256 byte structures. We could do a two dimensional array. I always worried the compiler would do something weird in the array layout, but it may be fine and I’m just paranoid.
The trick happens at initialization time. The buffer pool gets initialized at startup. The init code iterates over the array and adds each item to a linked list as the data. The linked list is our “free buffer” list. At startup, all of the buffers are free to use.
When the application needs a buffer, one gets allocated using alloc_buffer(). The call is fast, just unlinking the item from the linked list and returning the buffer.
Why not just use the array and track array indexes? Seems OK, but, at some point, maybe a the application using a buffer finds an error, aborts a task, or something I can’t imagine. The buffers get returned to the free list out of order. That means we have used an unused buffers mixed together in the array. Now we need some meta information to track that. If it gets all mixed up, we may pay for an array walk to find a free buffer in the array. Suddenly the highly deterministic code timing is random.
There is still a problem, did you catch it? In the linked list implementation the elements are malloc’ed and free’d using the heap. The structure with the pointer to next and data lives on the heap. We said there is no heap. So, now what?
We have linked lists, let’s make a pool of elements, then initialize them into a free list, and allocate them from that list. Solved! No, same problem as above, moved down one paragraph. The fix is simple. The linked list is storing elements. They don’t have to be allocated, it is a list of pointers to next. Use the elements to build their own free list. It will be a specialized list, the code is not exactly the same as a linked list, so we have to build it custom.
If different size buffers are needed, we create small, medium and large buffers with separate free lists. The number of elements needed matches the number of buffers. All of the lists can get elements from a shared pool.
I have used this data structure a lot in the past for networking code, audio processing, and resource handling. It is useful to add some instrumentation to keep the minimum free list size. After running stress tests, you check the minimum free list size to know how many buffers were used at one time. We also had an “idle” test. When the system would be idle, we checked the free list size. No buffers should be used, so size should match the initial size. If one is missing, we lost it someplace, go find it.
Using the above blog post as a specification, I let Claude code implement the code and test. The results are on GitHub.
Leave a Reply