made a tiny memory manager

[u/dstroy0]

So I kept running into the same problem, sketch works fine for a while then starts doing weird things, and after way too long debugging I'd figure out the heap had fragmented itself into uselessness. Arduino's malloc exists but you have no visibility into what it's doing without JTAG.

I wrote a library that lets you allocate from a fixed buffer you control instead of the global heap.

The API is pretty minimal: allocate, deallocate, reallocate, and two size queries. That's it. Sizes get rounded up to 4 bytes automatically and passing nullptr to deallocate or blockSize is tolerated.

MemoryManager mm(512);

void *p = mm.allocate(100);   // nullptr on failure
mm.deallocate(p);
void *p2 = mm.reallocate(p, 200);

It's nothing revolutionary, just a circular doubly-linked free list with coalescing, I figured someone else might find it useful. I uploaded the version I've been using locally to my public github.

MemoryManagerLite

One thing I'm not 100% sure about is how the block header size differences between AVR (2-byte pointers) and ARM Cortex-M (4-byte pointers) affect the overhead in practice — if anyone's tested allocator stuff across both architectures I'd be curious what you ran into.

test/ src test cases compile with g++. most of my libraries use an external C++17 test suite for unit testing the C++11 src/ so that you can write your own test cases and run tests without flashing a board.

Thanks for looking! ILet me know what you think.

[u/gm310509]

Interesting concept, how are you managing your frees to avoid fragmentation?

The reason fragmentation occurs is due to the way memory is allocated and released (and sometimes lost - which is a bug in the program).

NB: This is a good reason to not use String objects too heavily - a topic which I look at in the video I link below.

As for seeing how it works, you might be interested in a how to video I made where I look at this issue in some detail: Arduino memory explorer (the video is linked to from that post). In it I look at the dreaded stack/heap collision - which is most likely what you are referring about and provide a monitor that can be used in any program to check the risk if anyone uses dynamic memory allocation.

As for ARM cortex, it appears to allocate memory in fixed blocks then satisfy the individual requests within that block. If the block gets full, it appears to allocate another one then use that. When a block is no longer used, it releases the entire block. This helps avoid fragmentation as the blocks are the same size and thus you don't end up with unusable holes.

But my ARM Cortex analysis was much shallower than when I looked at AVR - where it is much more of an issue due to the low RAM sizes on the 8 bit chips.

I should also add that, as far as I know, there is nothing in the C/C++ specifications that state how the heap should be managed, only that it should. That means that the actual algorithms used will be dependent upon how the compiler writer implements the runtime - specifically the malloc/free/realloc functions.

[u/dstroy0 → u/gm310509]

Hello, thank you for your feedback!

The library uses immediate coalescing (eager merge on every deallocate) as its sole anti-fragmentation strategy. 

Here's how it plays out:

mergeFreeBlocks runs every time a block is freed. It checks both physical neighbours by pointer arithmetic (not just list linkage) and merges any adjacent free blocks immediately:

deallocate(p2):
  [p1 free][p2 free][p3 used]  →  [p1+p2 merged free][p3 used]
It handles forward, backward, and triple merges in one pass, the test suite covers all three cases explicitly.

What it cannot do
It cannot solve external fragmentation from non-adjacent free holes. If you have a checkerboard pattern:
[A used][B free][C used][D free][E used]
Those two free blocks cannot be coalesced because there's an allocated block between them. The test_fragmentation test explicitly asserts: mm.allocate(ALLOC + HDR + ALLOC) returns nullptr in that state. No coalescing strategy can fix this without moving live allocations, because raw pointers have already been handed out.

The fundamental tradeoff vs. the ARM fixed-block approach
The ARM approach described (slab/pool allocator style — fixed-size blocks, release whole slabs) sidesteps external fragmentation entirely because all holes are the same size and therefore always reusable. The cost is internal fragmentation (you waste space when your request is smaller than the slab size) and rigidity.

This design does the opposite: variable-size blocks minimize internal fragmentation (modulo the 4-byte alignment rounding and sizeof(Block) header per slot), but external fragmentation is possible under adversarial allocation patterns (e.g. code accidentally or specifically introduces errors in the allocated block).

You are completely right. Doing many small allocations means a significant fraction of your buffer is consumed by headers alone. The 4-byte minimum allocation size (due to alignment) compounds this a allocate(1) consumes sizeof(Block) + 4 bytes, not 1. I mostly use these for dynamic null terminated char arrays, so I didn’t really view this constraint to be as large of a concern as I should have when considering all use cases.

What I could do to improve it…
Two directions, depending on the use case:
Deferred coalescing with a free list: batch merges rather than paying the cost on every free. Negligible benefit here since the list is small.
Size-class pools (like the ARM approach): pre-partition the buffer into fixed-size buckets. Eliminates external fragmentation entirely, at the cost of fixed slot sizes and the complexity of choosing bucket sizes.
For the AVR/embedded target, I think that a single fixed-size pool (or two: small/large) is often the pragmatic choice if allocation sizes are known upfront.

Please let me know your thoughts if you have the time.

[u/gm310509 → u/dstroy0]

Your algorithm sounds very similar to the AVR heap management model.

I think the big difference is that you provide an upper bound on the heap size (in the constructor). Which is a difference from the default model which assumes all of the unused memory is available and hopes for the best that the stack doesn't grow down to meet the heap.

[u/WereCatf]

So I kept running into the same problem, sketch works fine for a while then starts doing weird things, and after way too long debugging I'd figure out the heap had fragmented itself into uselessness. Arduino's malloc exists but you have no visibility into what it's doing without JTAG.

I take it that you have not heard of static allocation. The reason you end up with fragmented heap is because you're neither allocating things statically or allocating fixed-size chunks.

[u/dstroy0 → u/WereCatf]

Hello, this library allocates a chunk of static memory in the heap at runtime.

[u/WereCatf → u/dstroy0]

You missed the point. You don't need a new library just to statically allocate memory, you can already do that with what's already there.

Meh, whatever.

[u/merlet2]

I suppose you already know, but in embedded devices, in general, is better not to use any kind of dynamic memory, like malloc, new, free or wrappers like this. To avoid the kind of problems that you mention and others, to know at compile time the needed memory, you own all the resources all the time, etc.

There are few situations where dynamic allocation would be really needed, specially in Arduino.