A simple heap memory allocator in about 230 lines of C
github.com
github.com
Ages ago, I was told to add copy protection to one of the products I managed.
I didn't want to. Hackers posted cracked versions of our apps within a few days any way. And our legit customers hated it.
Our company's QA/Test in charge of these things signed off on my implemention. Surprising. I knew it didn't work (as expected). But what the hell. I embraced her acceptance (buyoff), and burned those gold master CDs, meeting our deadline, pleasing our dealers, and had a new release to show-off at the trade show. Woot.
About a year later, this QA/test person figured out that implementation (for that release) never worked. She wasn't very happy with me.
What does that mean? My understanding is that a buyoff is a bribe, but your last paragraph implies it wasn't a bribe.
[1] https://github.com/maniacbug/FreeRTOS/blob/1d772c834b2e5e9bf...
It looks good to me, although it certainly looks old.
Everything is squished together, but presumably they were using much smaller displays back then. Imagine writing code to be displayed on half of your phone's screen.
The C style is different, because this isn't ANSI C or C99, but that doesn't affect the readability much.
I can't think of any coding practices it breaks. It's low level code, which most people don't have to write these days.
Kind of refreshing, in my opinion.
I'm trying to think what 'proper modern C' looks like by comparison to this, but I don't think I could personally rewrite this code, modern-C style, comfortably.
There's a legendary comment by @arcfide regarding coding styles that discusses how people get on their high horses about patterns and styles they don't understand. I like to re-read it now and then, and reflect on how the things we want to think are "common sense" are mostly fads that will pass. https://news.ycombinator.com/item?id=13571159
for(p=allocp; ; ) {
for(temp=0; ; ) {
if(!testbusy(p->ptr)) {
while(!testbusy((q=p->ptr)->ptr)) {
ASSERT(q>p&&q<alloct);
As it happens I believe 7th ed is now under a bsd-ish license due to http://www.tuhs.org/Archive/Caldera-license.pdf
E.g. try and make it work well with 2 threads. Now try and make it work well with 2 threads, one - allocating, another - freeing, etc.
Writing a memory allocator is a _fantastic_ exercise in data structures and optimization. It's also an easy one, so making a reasonably fast allocator from scratch is not that hard, but in the end it's much more fun to write one than to look at someone else's results. This is also what makes these toy allocators to be a dime a dozen.
A "pointer-per-block" alone will cost you 8 bytes of overhead on 64-bit machines. Both this and the 'while' loop in 'alloc' can be optimized away with rudimentary slab allocation. There's no threading support, etc.
Actually, I disagree. Putting aside the implication you had that writing bugless software is possible, I think that memory allocation is straightforward. The interface is simple and the gotchas haven't changed since memory protection standardized. Writing a correct allocator amounts to a checklist of allocation and free behavior, plus some extra stuff like "how hard/probable is it to detect use after free" &c. Correctness, property calculation itself, and proving (theoretical) performance of your algorithm is not so hard.
Now writing a general purpose one that doesn't trigger catastrophic performance against one app of many is really hard.
Are... linked lists really that difficult to fuck up? How??
I've got 30+ years of C under my belt and I still would be very careful to make the claim that I could write a fault-free allocator on the first try. Three years ago or so this exact problem came up in one of my jobs and I reviewed the code of someone who was pretty good by most measures. The number of bugs was embarrassing.
So, maybe my experience is totally different than yours and this is all at the level of anecdotal evidence but it appears to me that writing bug free code is hard, in any language.
Have you looked at dlmalloc, which lets you build with USE_LOCKS=0 to turn off the threadsafety?
JEmalloc does locking on multiple pools, failing one it tries another. So there is a high probability it won't preform many atomic CAS ops.
As a public service announcement, if you are building a heap manager for C code, don't do this (put your heap control structures next to the allocated memory). Sure it looks elegant, however a VERY common C bug is the 'off by one' error, and when an off-by-one can corrupt the structures that define the heap, well it gets out of hand quickly.
Have your heap structures "far" away from the allocated memory. Yes you burn another N bits (where N is log2(max_address)) in your heap control structures, and yes you may have heap control structures you "don't need" pre-allocated, but your future self will thank you for doing it this way.
brk/sbrk is a bit of a pain but would it really be more complicated to use mmap?
A lot of unicies allow over commit because of this where windows will fail the alloc. The windows design is much better if you care about handling OOM.
The most simple and therefore fastest possible memory allocator usually is just a continguous byte array and an offset. On allocation you check if there is enough memory left and if not you request another very large block of memory from the general purpose allocator. Otherwise you merely return the current offset and increment the offset by the size of the allocation. Of course the restriction here is that you can only delete all allocations at once or none at all.
Generational garbage collectors go one step further. They are capable of detecting whether the object is alive or dead and thus make it possible to keep them and move them into an different memory area. Unfortunately the garbage collector has to stop all mutator threads otherwise the mark and sweep phase, copying phase and compation phase would not work. There do exist some concurrent garbage collectors but they are not widely used.
> In this repository, that memory is supplied by malloc
Got any evidence to support this claim? I call b/s, especially on the "most" part.
Balanced trees introduce an extra per-node overhead, they tend to thrash the cache and are generally inferior to a simple array of double-linked lists indexed by the block size range.
* An AVL tree doesn't have the per-node overhead, but it is very cache-unfriendly.
It doesn't matter if the allocator uses buckets (indexed by the block size range) or not, it still has to find blocks of suitable size, for some definition of "suitable." So look at his get_best_fit and add_node functions. These ensure that his alloc and free functions are O(n) at best. Clearly, we can do better.
Are you making an educated guess that there should be a blanced tree somewhere in there? If yes, then it's a wrong guess, because there are better options that aren't based on a boatload of conditional branching and that _are_ routinely used in a lot of allocators. If no, there shouldn't be hard to produce relevant code segments. Especially since these trees are virtually everywhere as per your opening remark.
Address spaces in modern operating systems. Address spaces can consist of a large number of virtual address regions. As one example, on a typical Linux desktop, GNOME applications and web browsers such as Firefox and Chrome use nearly 1,000 distinct memory regions in each process. To manage this large number of regions, most modern operating systems use structures like the ones in Figure 1 to represent an address space. Linux uses a red-black tree for the regions, FreeBSD uses a splay tree, and Solaris and Windows (prior to Windows 7) use AVL trees [18, 24].
https://people.csail.mit.edu/nickolai/papers/clements-bonsai...
If you know of any better search structures, then I'd love to hear about them. I wrote my own memory allocator for a vm project and found that storing the free list in a red-black tree was absolutely required for decent performance.
You said -
> An optimization that most memory allocators use are to instead store the nodes in a balanced tree, such as a red-black one
Yet, you still haven't shown a single memory allocator that actually does that. Except for your own.
jemalloc uses trees (off the fastpath nonetheless), but hoard doesn't, dlmalloc doesn't, etc.
Common sense derived from CS101 on data structures doesn't directly translate to what's happening in the real world. Your opening comment was pure armchair athelitics.
I have now looked at Hoard. It does use std::map which is indeed a red-black tree.
https://github.com/mbrumlow/toyos/blob/master/kernel/heap.c
Admittedly mine has no test or does any fancy stuff -- just needed a simple allocator so I could move forward with a toy kernel.
https://stackoverflow.com/questions/13159564/explain-this-im...
Looks like quite a bit more than 20 lines.