13 ms·
A simple heap memory allocator in about 230 lines of C
- pm215 9y agoCoincidentally, the libc malloc/free implementation in 7th Edition Unix is also about 200 lines of C: http://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/gen/malloc.c http://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/src/libc/ge...
- saurik 9y ago...and coincidentally is also under a license (or lack thereof) that does not allow its use in other projects :(.
- pm215 9y agoNobody should try to use 7th ed code in other projects, regardless of license. At this point in time it's of historical and educational interest only (it won't even compile with a modern C compiler...) As it happens I believe 7th ed is now under a bsd-ish license due to http://www.tuhs.org/Archive/Caldera-license.pdf http://www.tuhs.org/Archive/Caldera-license.pdf
- shubhamjain 9y agoIs it my unfamiliarity with C or the code is really terrible? It seems that coding practices that we have started to think of as common sense are anything but.
- gravypod 9y agoC had changed a lot over the years. It used to be much less standardized.
- deleted 9y ago[deleted]
- pm215 9y agoIt's certainly not the style I would expect C to be written these days, but I don't think it's terrible code. It was, 40 years ago, genuine shipping real-world code. There's a related quote about this in the foreword that Dennis Ritchie wrote for the reprint of the Lions commentary: "You will find linear searches, primitive data structures, C code that wouldn't compile in 1979 let alone today, and an orientation towards a machine that's little more than a memory. But you will also see in the code an underlying structure that has lasted for a long time and has managed to accommodate vast changes in the computing environment." We're still calling malloc() and free() and realloc() today with the semantics that the Unix designers assigned them in the 1970s, even if the underlying implementations are significantly different. The bones of the design are strong; the initial implementations may have been naive but they were good enough to ship (and remember there were only a fairly small group of people writing the whole OS and userland).
- hawski 9y agoIt seems that it's not entirely the same semantics: https://www.spinellis.gr/blog/20170914/ https://www.spinellis.gr/blog/20170914/ ( https://news.ycombinator.com/item?id=15246690 https://news.ycombinator.com/item?id=15246690 )
- pm215 9y agoThat blog post is talking about the kernel's internal allocator, not the libc one.
- chubot 9y agoWhat seems terrible about it? 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.
- fit2rule 9y agoIts pretty good C code. I don't share shubhamjains' point of view. 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.
- nurettin 9y agoIf the goto is ticking you off, that's because moving the loop into another function and hoping it gets inlined or placing extra flags everywhere isn't practical.
- dahart 9y agoI'd say it's your unfamiliarity with C, and perhaps with history too. You're talking about a release version of malloc() in Unix, this code was run by many many people on many platforms and sat underneath nearly all software running on Unix v7. How many computer systems globally ran successfully using this version of malloc? You can maybe say something bad about it if you can find a bug in it, but "really terrible" is just wrong, it doesn't make any common sense to say that. 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 https://news.ycombinator.com/item?id=13571159
- bjourne 9y agoThe code is indeed terrible. This for(p=allocp; ; ) { for(temp=0; ; ) { if(!testbusy(p->ptr)) { while(!testbusy((q=p->ptr)->ptr)) { ASSERT(q>p&&q<alloct); would not pass anyone's code review today. Presumably they had to write it that way to ensure that the compiler emitted adequate code.
- throwaway613834 9y agoWhat exactly do you find the most problematic with this code?
- bjourne 9y agoIsn't it self-evident? Blocks nested five levels, abused for-loop syntax, assignment in testing expressions...
- throwaway613834 9y agoIt's not evident, sorry. Despite what you might hear about having over three levels deep being a sin, five levels of nesting is perfectly fine. And that's not an abuse of for-loop syntax -- that's exactly how you're supposed to do an infinite loop. In fact, `while(1)` is the syntax that abuses loop notation, and consequently raises "conditional expression is constant" warnings. Assignment in conditional, though, I guess I can agree with you on...
- flohofwoe 9y agoMaybe because it just looks 'unfamiliar' instead of 'terrible'? Just add syntax-coloring with your favourite color-theme, your favourite tab-width, and your favourite brace-style, and it will look fine ;)
- joelthelion 9y agoCould you use this as a malloc/free replacement or is it missing something?
- alvil 9y ago+1 for this
- exikyut 9y agoSee the other comments here. It's overly simplistic, so not particularly efficient.
- masklinn 9y agoMore importantly, it's implemented in terms of malloc in the first place: > In this repository, that memory is supplied by malloc
- sitkack 9y agoMaybe one could make a LD_PRELOAD shim to re-export malloc from this lib. https://github.com/ice799/malloc_wrap https://github.com/ice799/malloc_wrap
- masklinn 9y agoAside from not being a good allocator, it's implemented on top of an existing malloc so it doesn't actually work.
- apenwarr 9y agoRemoving the calls to existing malloc on an embedded system would be trivial. Just point it at a predefined RAM area instead. It uses malloc only so you can play with it on a full featured OS, not because they left something out.
- huhtenberg 9y agoIt's not a "simple" allocator. It's an overly simplistic and largely unoptimized one. 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.
- senatorobama 9y agoIs there an allocator that uses lockless programming?
- bonzini 9y agoYou can do mostly lockless. The fast path is what matters the most, the difficult part is not wasting too much memory for the sake of not hitting the slow path.
- masklinn 9y agoIIRC jemalloc has per-thread pools & caches which I assume can be accessed locklessly. I don't think the entire thing is lossless, and neither is tcmalloc. And as far as I know these are the only significantly thread-aware allocators (or at least production-ready ones).
- bonzini 9y agoglibc has also grown a good thread-aware allocator, though that is more recent than tcmalloc or jemalloc.
- qznc 9y agoYou may find this interesting: https://concurrencyfreaks.blogspot.de/2017/08/why-is-memory-reclamation-so-important.html https://concurrencyfreaks.blogspot.de/2017/08/why-is-memory-...
- 9y ago
- Keyframe 9y agoNeat! See also TLSF https://github.com/mattconte/tlsf https://github.com/mattconte/tlsf
- senatorobama 9y agoWhat's the state of the art in memory allocation?
- krona 9y agoDepends what you mean by state of the art, but jemalloc?
- imtringued 9y agoThe application acknowledges that a general purpose allocator can't be tuned to it's specific needs and therefore implements it's own very restrictive, specialised, simple and fast allocators. 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.
- flamedoge 9y agohttps://stackoverflow.com/questions/9866145/whatre-the-differences-between-tcmalloc-jemalloc-and-memory-pool https://stackoverflow.com/questions/9866145/whatre-the-diffe...
- bjourne 9y agoI suspect that some of the functions for iterating the linked lists are a big drag on performance. Such as: https://github.com/CCareaga/heap_allocator/blob/master/llist.c#L68 https://github.com/CCareaga/heap_allocator/blob/master/llist... An optimization that most memory allocators use are to instead store the nodes in a balanced tree, such as a red-black one. Or even better, a B-tree. That turns those functions from O(n) to O(log n).
- eps 9y ago> An optimization that most memory allocators use... 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.
- bjourne 9y agoHow about the memory allocators used by Linux, Windows, BSD and Solaris? :) 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.
- eps 9y agoWhat about them? 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.
- bjourne 9y ago
- pjc50 9y agoThe implementation of malloc in K&R is about 20 lines...
- masklinn 9y agoIt's closer to 50 lines if you don't exclude the morecore helper, and that's using the pretty opaque, outdated and golfy style of K&R itself.
- vardump 9y agoGoogled it and found this: https://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book https://stackoverflow.com/questions/13159564/explain-this-im... Looks like quite a bit more than 20 lines.
- masklinn 9y ago> In order to initialize this heap, a section of memory must be provided. In this repository, that memory is supplied by malloc (yes, allocating a heap via heap). In an OS setting some pages would need to be mapped and supplied to the heap (one scenario). brk/sbrk is a bit of a pain but would it really be more complicated to use mmap?
- bjourne 9y agommap isn't available on Windows. On those platforms it is available on, there could be subtle differences. If you don't care about memory protection, there is no reason not to use malloc.
- slededit 9y agoIt's there in spirit. VirtualAlloc is extremely flexible. brk is really intended for a segmented environment but it makes it almost impossible to return commit back to the OS. 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.
- saurik 9y agoI was extremely happy to see this as I have been trying to find a single-threaded memory allocator (one which doesn't have any reliance on any form of threading primitives that I simply don't have on the platform I am dealing with, which I point out to make clear that I am not looking for this due to any delusion about performance), but since this doesn't have a license on the code it is essentially useless :(.
- jstimpfle 9y agoI don't think we need license stickers on each little piece of code (not trying to belittle OP's work). Why don't you just read and understand it and make your own? It's just 200 lines. You can then also much more easily adapt and extend. EDIT: I know it breaks the guidelines in multiple ways, and I'm past the age where I should care, but * * * * you downvoters. This is a reasonable comment, and if you disagree give some argument.
- saurik 9y agoI don't do that for the same reason no one should do that: because if I read this code and then write my own code that uses the same techniques and structure due to my having read this code, it will be a derived work of this code, but this code is not under a license that allows me to do that. The legal reality is that yes: if you want to write code that other people are to be using or reading you do need to put "license stickers on each little piece of code"; this is sadly a big problem with hackathons and classes that encourage people to put stuff haphazardly on GitHub because "yay open source" without teaching people enough about copyright to make that worthwhile.
- jstimpfle 9y agoBe sure that this is how OP made his code himself... And that you can easily find other code that your work is "derived" of, even if you did it completely on your own with only basic ideas from wikipedia. Of course, check back with your lawyer if you're that concerned. But nobody wants to live in a world where you can't make your own 200 lines of code based on ideas found somewhere else (ideas which are not owned by anybody).
- katastic 9y agoI remember years ago my friend was gong to college for CSCI and had to write a malloc for a course. He procrastinated till the last... night... and wrote it. In the free() routine, he simply wrote "return true;". The TA's unit-tested code because there were over a hundred classmates to test. Well, the unit-tests must not have been very good because he said he scored a 100.
- nightcracker 9y agofree returns void, so even the "return true;" was wrong.
- katastic 9y agoOkay, well, this was a story I was told like 8 years ago when I was back in college. So I'm bound to have mixed up the details. But the event did happen. It passed the unit tests even though he was supposed to manage and free pages.
- specialist 9y agoHa. 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.
- kristianp 9y ago"I embraced her acceptance (buyoff)". What does that mean? My understanding is that a buyoff is a bribe, but your last paragraph implies it wasn't a bribe.
- 9y ago
- samblr 9y ago..sometime ago had come across [ jemalloc, tcmalloc ] memory allocators whilst solving a performance limitation of platform (in a multithreaded environment) - I think it was jemalloc which gave real boost in performance. Worth trying them too.
- ChuckMcM 9y ago"Each chunk of memory has a node struct at the begining and a footer struct at the end." 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.
- mbrumlow 9y agoA silly allocator i wrote for fun one night is also under 200 lines of code. https://github.com/mbrumlow/toyos/blob/master/kernel/heap.c 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.
- 8fingerlouie 9y agoReminds me of an old project of mine for an embedded platform that needed a memory allocator. Also around 200 lines if you leave out the stdlib functions. https://github.com/jinie/memmgr/blob/master/memmgr.c https://github.com/jinie/memmgr/blob/master/memmgr.c