Like dlmalloc and similar heaps, embedded heap uses bins to hold free chunks[1]. However, eheap bins are designed for the needs of embedded systems.
Bins
eheap permits from 1 to 32 bins. This supports a range of heaps from very small to large The former are likely to be used in partitions that require heaps and latter in systems for main heaps. A bin consists of a header, which is doubly-linked to the chunks within the bin. There are three types of bins:
- Small bin.
- Large bin.
- Top bin.
A small bin holds only one chunk size, hence block allocations from it are fast because no bin searching is required. A large bin holds a range of chunk sizes. For allocation from a large bin, the bin is searched from the start until the first large-enough chunk is found. The top bin holds all chunks above a certain size.
Bin Configurations
Bins usually start with a small bin array (SBA), which consists of small bins starting at chunk size 24, (block size 16) and going up to whatever is needed for the particular heap. Normally small blocks are most in demand. However, the SBA can be omitted, if not desired. Above the SBA is the upper bin array (UBA), which consists of a mixture of large and small bins, ending with the top bin.
A small system might have a bin-size array like the following:
For the above, the SBA consists of bins 0, 1, and 2 holding chunk sizes 24, 32, and 40, respectively; bin3 contains 10 sizes from 48 to 120; bin4 is a small bin containing only the size 136; bin 5 contains 15 sizes from 136 to 256; and bin6 is the top bin containing all sizes from 264 on up. The -1 marks the end of the bin size array. In this particular embedded system there apparently is a limited need for small chunks, some need for medium chunks, and little need for large chunks above 264 bytes.
Note that a small bin has been added for 136-byte chunks (128-byte blocks), which apparently are frequently needed in this system. Although in the UBA, this bin, like other small bins, requires no searching. This improves performance when a particular size is frequently needed, such as for packets used in a communication protocol.
The following is an example of a bin array for a smaller heap, with no SBA:
In this example, bin 0 holds chunk sizes 24 to 504 – 61 sizes, total, and bins 1 to 4 cover similar size ranges. This bin structure might work well in a partition or system where block allocation sizes are random in the range of 16 to 2040 bytes. In this example, each bin acts like a mini heap. Bin 4 is for safety, in case a 2048 byte, or larger, chunk is needed.
One bin heap example:
In this case, there is no SBA and no UBA, only the top bin. This heap approaches the serial type heap, but still offers advantages over it (see discussion below). This bin structure could be appropriate for a heap primarily used during initialization and very little after.
Bins can easily be added, removed, or resized simply by changing constants in the bin size array, binsz[] and recompiling. When the system is started, eh_Init() initializes the bins and internal heap variables from binsz[]. Thus, a heap’s bin configuration can be changed by changing a few constants in binsz[], and it is easy to experiment with different bin configurations to find the one that gives the best performance for a particular partition or system.
Allocations
For SBA allocations, the desired block size is used as an index into the SBA to find the correct bin, then, the first chunk in that bin is taken. Thus, allocations are as fast as an array of block pools, yet flexibility is that of a heap.
For a UBA allocations, the correct bin is found by means of a binary search based upon the chunk size. If the bin selected is empty, the next-larger, occupied bin is used. The bin map enables finding this bin quickly; it has a bit per bin that is set if the bin is occupied. If all higher bins are empty, allocation comes from the top chunk in the heap [see Ref 1].
A tenet of heap design is that larger blocks take longer to process, so longer allocation times for them are acceptable. Of course, an allocation cannot take so long that high-priority tasks miss their deadlines.
If a large bin is accumulating too many free chunks, it can be split into two smaller bins. Thus, there is a tradeoff between the number of bins and how many free chunks each bin holds.
Large Bin Sort
During a free operation, if a chunk is larger than a large bin’s first chunk, it is put at the end of the bin free list; otherwise, it is put at the start of the bin free list. When the idle task runs, large bins and the top bin are sorted by increasing chunk size in order to minimize search times. This also assures that the first chunk found is the best fit chunk. The sort algorithm used is bubble sort with last turtle insertion. I’ll leave explanation of that for a future article!
Bin sorting during idle periods works well, because embedded systems must have sufficient excess capacity to deal with peak activity periods. Therefore, they have frequent idle periods the rest of the time. (This is unlike IT systems, which run one job after another with no idle periods during jobs.) Since idle periods are normally more frequent than allocations, large bins are likely to be well-sorted when they are searched.
When a found chunk is more than 24 bytes larger than required, the excess amount is split off and merged with the chunk above, if it is free. If it is not free, the excess is made into a new free chunk. In either case, the resulting chunk usually must be moved into another bin – i.e. either up or down.
Free Chunk Merge
dlmalloc always merges free chunks. This undercuts the utility of bins, but it does reduce the chance of allocation failure due to heap fragmentation. eheap has a variable, cmerge, which controls merging. When cmerge is off, freed chunks are returned to their bins and not merged. When cmerge is on, freed chunks are merged with adjacent free chunks, if any. Normally this results in moving the resulting chunk to a higher bin, due to its larger size. Consequently, the chunk will not be available in the expected bin if the system needs it again. This can result in wasted action where the chunk is found and split, freed and merged, etc. Unfortunately, this is can be the case for embedded systems, which tend to be highly repetitive in nature.
IT systems must deal with a wide range of requirements due to running many different jobs, whereas embedded systems usually run a single job and thus tend to fall into repetitive patterns. Because of this, they are more predictable and less prone to excessive fragmentation. Control of cmerge allows taking advantage of this characteristic in order to improve system performance. It can be customized to system requirements based upon the amount of heap used, degree of fragmentation, or other measures. Alternatively cmerge can be turned on permanently, if that is preferred.
Conclusion
eheap bins can be customized for optimum heap performance in embedded systems. The next article in this series will discuss chunk types. The full source code for eheap can be found in eheap.c and eheap.h at www.github.com/Micro-Digital/SecureSMX.
References
1. “eheap, Part 1: Basics”, LinkedIn, Ralph Moore, April 2026.
Notes
[1] A chunk is the basic unit of a heap. It consists of a data block, a pointer to which is passed to the user, and metadata, which is used to control the heap and not accessible to the user.