FreeRTOS also has a nice collection of different heap implementations with varying degrees of sophistication. They are a good read for those interested in such things.<p><a href="https://www.freertos.org/a00111.html" rel="nofollow">https://www.freertos.org/a00111.html</a><p><a href="https://github.com/aws/amazon-freertos/tree/master/lib/FreeRTOS/portable/MemMang" rel="nofollow">https://github.com/aws/amazon-freertos/tree/master/lib/FreeR...</a>
Please don't write custom memory allocators for production code without seriously considering the security implications of doing so. The glibc allocator has benefited from years of security hardening against very creative attack vectors.<p>You don't want a simple double-free to lead to an RCE bug, do you...
K&R includes an example memory allocator as well: <a href="https://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book" rel="nofollow">https://stackoverflow.com/questions/13159564/explain-this-im...</a><p>To me, the K&R one seems much less readable and also doesn't include the global malloc lock, since even the updated edition of K&R predates standardised threading.<p>I note it also does the "bp = (Header *)ap - 1;" trick, so if that's undefined behaviour then it's a good example of how hard it is to write C without relying on UB.
Good timing. I literally had to do this on a whiteboard in an interview about 11 hours ago.<p>Interesting things to consider: Fragmentation prevention, real-time performance, minimizing locking(lock-free techniques, or per-thread free lists), and reusing the freed memory to contain the free list structure. I basically started out whiteboarding what the article lays out and by the end of the interview realized everything wrong with it. It's a good starting point though.
I gotta say this is a very topical read. Was messing around last week or so trying to learn some x86 Assembly from scratch (Linux subsystem on Windows,) and memory was very much a sticking point. Seeing this is helping me grok just what is sorta going on, which is the best way for me to learn I think.
While I strongly support the idea that no one should write a generic allocator in production, writing it as an exercise is a very good idea.<p>The article looks at lot like the tutorial I wrote a long time ago ... (Every now and then, I see my old PDF in post about implementing allocators, which is disturbing since I wrote it in a hurry as a quick support for a lecture and I found it very poorly written ... )<p>I think it's interesting to note that using sbrk(2) is a bit deprecated, it's way easier to implement malloc(3) using mmap(2) ...<p>There's also better ways to handle pointers arithmetic and list management. Someday I'll put only cleaner version only ... Someday ...
It's worth noting that<p><pre><code> realloc(ptr, 0)
</code></pre>
behavior is undefined. The vast majority of modern C libraries will implement it as<p><pre><code> return free(ptr), NULL;
</code></pre>
and it will be documented on man pages as such, but there <i>are</i> systems where this will be equivalent to<p><pre><code> return free(ptr), malloc(0);
</code></pre>
Furthermore, in theory, this is also permitted:<p><pre><code> return NULL;
</code></pre>
so as tempting as realloc() might be as a single override for implementing custom allocators, there are some worms.