Real-time memory-manager

Heap

I've written a real-time memory-manager for FreeRTOS. Allocations and deletions are done in constant low time. Fragmentation is no problem, the heap won't overflow.

Creation

heap_handle_t heap_create(size_t offset, size_t size);

A small header get’s stored right at the beginning:

typedef struct
{
size_t free;
size_t used;
size_t size;
size_t free_block;
block_map_t map_free;
}heap_t;

Allocation

void* heap_alloc(heap_handle_t heap, size_t size);

If there is a gap big enough, it is found in the map. Else a new heap_block is created at the end of the heap.

The size and a flag if it is free are stored twice at the head and the foot. This is neccessary to combine free blocks next to each other.

Deletion

void heap_free(heap_handle_t heap, void* buf);

The block is added to the map. If there are free blocks left or right of it, those get removed from the map and a combined block is added.

Map

Free blocks are sorted by size and by offset. When allocating from the map, the smallest gap top most of the heap is returned.

Internal Allocation

Adding a free block to the map can cause an internal allocation, the opposite when removing. I've made it by caching releases in free blocks, and by making allocations passive without moving anything in the map.

Implementation

I've spent my whole holidays on this memory-manager last year. A few more days on the weekend and i think it is perfect now. You can find it on GitHub.

Best regards,

Sven Bieg

1 Like

Do you have a link?

Sounds great, I’d love to have a look!

1 Like

I can’t post it here because i’m new in the forum.

My account is svenbieg, the repository is Heap.

Sounds interesting… have you made any measurements about the footprint required by your management structure? Since (in my understanding) many small fragmented clusters require more pyramidal levels of cluster buckets, would’t traditionally fragmented memory usages add up more and more buckets and thus end up eating more memory? Is that process reversible (ie can your system remove buckets once the number of entries drops below the 10 count which caused the system to introduce another level)?

Do I understand it correctly that parts of your management structure are stored (“invisibly”) in the maintained memory blocks themselves, meaning that application code that inadvertantly overtramples memory behind its allocation size will destroy management information and thus confuse the manager (very frequent cause for trouble in the standard C implementation afair)?

I’ve bumped your forum status up a notch - hopefully you will be able to post the link now.

1 Like

To Your first question, You are right.
Fragmentation lets the map grow, but this shouldn’t be a problem. A large map means a lot of free blocks available. I don’t allocate from the foot as long as there is a gap large enough in the map. The only problem could be tons of 12 byte gaps that will never be allocated, this would cause a big map but not slow down the application. I already thought about increasing the mimimal block-size to 16 bytes. In my applications i have a lot of small objects that will fill up the gaps and reduce fragmentation over time.
To Your second question, this is true. Any application can crash the heap. This isn’t really a security reason, modern C++ will prevent this.

Thank You for Your response.

The only measurement i made is stability.

Ok, another question - please don’t mistake this as looking for shortcomings, I am very grateful for folks thinking out of the box, just want to get a grip on the issues -

your management data structures obviously have some need for dynamic memory allocation as well, eg if you need to extend your pyramid if the number of nodes in one bucket gets too high. This obviously introduces new issues. First, you could allocate these buckets from a dedicated fixed pool, meaning that your manager must fail when no more free buckets are available, even though your heap itself may still have enough memory to serve the request! The alternative would be to use the heap itself when allocating new buckets, meaning you may have recursive calls into your management routines, which may lead to very subtle differences in run time scenarios under low memory conditions. Have you tested all of those scenarios thoroughly?

1 Like

This in fact was the biggest challenge. Like i mentioned, i’ve made it by caching releases in free blocks and by making allocations passive without moving anything in the map.
In the header there is a free_block, in the free block itself is a pointer to the next one. When releasing internally, the free block simply gets added to this chain. These blocks get added to the map when the initial allocation is done.
When allocating internally the map is locked by the initial release. I still can remove an entry passive by setting it to zero and a dirty flag in the group. The initial call then cleans up when it is done.

Thank You!

I think it’s too late to post my link now, but here it is:

https://github.com/svenbieg/Heap

Probably this the only way You can get Your certificate.

Happy Easter!

Sure, groups get combined and released when removing an entry. If the root only has one child, this child gets the new root.
This is also done when releasing and the group is dirty.

Best regards,

Sven Bieg

Interesting implementation of a heap manager. I assume that the wrappers for the standard library calls (eg, malloc(), free(), new(), delete()) handle concurrency protection as well as providing the heap handle parameter. I’ve never written a heap allocator for FreeRTOS, though I have written ones for other RTOSs and bare metal, but none of them use a tree structure to store free memory segments. Interesting concept.

1 Like

Yes, You will need a critical section to prevent a task-switch and a lock.
The pyramidal tree structure is an invention i made about 20 years ago, i call it Clusters. This structure gives me an overview, better than IBMs btree.
My memory-manager should make any C++ application run smoothly until the hardware strikes.
Please feel free to have Your own implementation, but not for sale!
You may have to use it in Your commercial product, but my memory-manager is free.

Good luck!

Thanks. If I am working on a new application where the pyramidal heap manager might help with performance, I will consider it. Most of the stuff I do these days has to conform to MISRA or DO-178B DAL A, so it may only allocate/reserve memory during initialization and configuration, and must not allocate additional memory or free/release memory from that point on, so anything more than a wrapper around setbrk() is overkill. My last 2 projects have not had any dynamic memory allocation at all - every object was statically allocated at build time. That’s not to say that there was no reserve/release mechanism - each object type (list entries, buffers) were maintained with separate free lists (linked list of free items of that type), but these pools were populated at start-up with pre-allocated storage elements. The code was provably tolerant to resource exhaustion, which was how certain flow-control was maintained. There’s more to it than that, but I can’t go into detail beyond that.

1 Like

I don’t have those restrictions. :wink:

I’m working with Objects, Handles and Events.

The only question i have is, may i link Your FreeRTOS on GitHub if i get Your memory-manager?