Memory allocator for small chunks (Typ <= 16 bytes, Rare >= 64 Bytes, Max = 192) with static heap

Question

This allocator will be used inside an embedded system with static memory (ie, no system heap available, so the 'heap' will simply be 'char heap[4096]')

There seems to be lots of "small memory allocators" around, but I'm looking for one that handles REALLY small allocations. I'm talking typical sizes of 16 bytes with small CPU use and smaller memory use.

Considering the typical allocation sizes are <= 16 bytes, Rare allocations being <= 64 bytes, and the "one in a million" allocations being upto 192 bytes, I would thinking of simply chopping those 4096 bytes into 255 pages of 16 bytes each and having a bitmap and "next free chunk" pointer. So rather than searching, if the memory is available, the appropriate chunks are marked and the function returns the pointer. Only once the end is reached would it go searching for an appropriate slot of required size. Due to the nature of the system, earlier blocks 'should' have been released by the time the 'Next free chunk' arrives at the end of the 'heap'.

So,

Does anyone know something like this already exists? If not, can anyone poke holes in my theory? Or, can they suggest something better?

C only, no C++. (Entire application must fit into <= 64KB, and there's about 40K of graphics so far...)

Answer 1

OP: can anyone poke holes in my theory?

In reading the first half, I thought out a solution using a bit array to record usage and came up with effectively the same thing you outline in the 2nd half.

So here is the hole: avoid hard coding a 16-bite block. Allow your bit map to work with, say 20 or 24 byte blocks at the beginning of you development. During this time, you may want to put tag information and sentinels on the edges of the block. Thus you can more readily track down double free(), usage outside allocation, etc. Of course, the price is a smaller effective pool.

After your debug stage, go with your 16-byte solution with confidence.

Be sure to keep track of 0 <= total allocation <= (2048 - overhead) and allow a check of it versus your bitmap.

For debug, consider filling a freed block with "0xDEAD", etc. to help force inadvertent free usage errors.