I 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.
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.
Slight tangent here, but this is intriguing to me - the concept of devs ignoring known bugs until they are found by testers. Do other devs struggle with this? Are there certain working conditions that foster this behavior?
Okay, 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.
Is 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.
It'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).
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.
Its 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.
I'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
If 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.
Maybe 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 ;)
It'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...
Nobody 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...)
It'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.
Are you implying that this ^ 40-year old piece of code is somehow suitable for modern use?
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.
You stated that the example was "overly simplistic and largely optimized". I made no claim as to what system this code is optimized for, I was simply stating that it is possible to have an allocater the same size that is (or was) suitable for production use.
I agree with all of your comment except for the bit where you write that it is also an easy one. Writing a memory allocator without obvious (and not so obvious) bugs is really hard.
> Writing a memory allocator without obvious (and not so obvious) bugs is really hard.
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.
I'm going to have to disagree with you. Your average programmer isn't going to be able to write a linked list implementation that is correct, let alone a whole allocator and free mechanism. I've seen enough code by now to be strongly convinced of this and it will take something fairly momentous to get me convinced of the opposite.
> Your average programmer isn't going to be able to write a linked list implementation that is correct, let alone a whole allocator and free mechanism.
Are... linked lists really that difficult to fuck up? How??
Well, that seems to be more of a problem with C familiarity than memory allocation. If you can write correct data structures in C, you have rudimentary knowledge of linkers and mprotect (or whatever is analagous on Windows), you'll be fine.
That's what you'd think. And then you go and review code written by people who know their stuff. And you find fault after fault after fault. A well known HN'er commisioned a very simple little bit of code as a test and got sent a lot of submissions to evaluate (100+). A very large number of those contained obvious bugs, and this is from a group that would likely consider themselves to be 'above average'.
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.
Sure. I meant that writing a reasonably fast non-reentrant allocator is easy. Getting it to work well in a threaded environment is where all the worms are.
I have had an absolute hell of a time finding a memory allocator that will work in a fundamentally single-threaded environment (where I need compliant C only with no library functions or processor features that offer anything for threads); do you have a suggestion? Everyone seems to care a lot about how to "make it work well with 2 threads", at which point the very premise tends to make the allocator unusable for me :(.
Thank you so much! I had stared at a few malloc implementations (both standalone and from a few libcs), and I had finally gotten to the point (after seeing how thouroughly integrated the threading often is, with not just atomic variables and locks but sometimes thread local storage) that I had largely given up on any implementation that even mentioned multithreading as a feature, but I clearly should have kept going: I just managed to get dlmalloc compiled using nothing but mmap, munmap, abort, memcpy, memset, sysconf (which should be fine), and time (which also should be fine). That just did not seem to be plausible with TCMalloc or jemalloc. Again: thanks so much!!
NetBSD and Musl libc are good sources for simpler implementations. From memory the NetBSD jemalloc is an early simple single file version that is pretty easy to adapt.
Look up "buddy system allocator." The algorithm is super fast and easy to understand and implement. It was also the one used in the very first Linux kernels (probably for those reasons).
IIRC 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).
You 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.
"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.
> 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?
mmap 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.
It'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.
The 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.
..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.
Removing 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.
I 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... 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).
> 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.
How 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.
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].
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.
This is unrelated, you are switching the subject. The context is an application-level memory allocators, not the underpinnings of the virtual memory systems.
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.
Now I'm beginning to think that you are trolling me. Memory allocators within the kernel works exactly the same as those outside of it. But for one stand-alone library using balanced trees, look at jemalloc.
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 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 :(.
I 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.
Be 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).
The legal reality of copyright is that the color of the bits matters: unlike with a patent, if you independently somehow manage to come to a similar result and can prove that, you are supposed to be fine (though there was one devastating ruling with respect to photographs that I think most people consider to have been a mistake that may lend some precedent to such an argument, I think you would still have a difficult time pulling it off). This just isn't about the world in which I want to live: it is about the world in which I actually live.
> This just isn't about the world in which I want to live: it is about the world in which I actually live.
Based on your own arguments, I think you are theoreticizing. It's also your own decision in what world you live. I would not want to spend my time this way. But again, your own decision.
(It would be of course a nice gesture to drop the author a thank you, or whatever)
Do you seriously believe that you can ignore laws by simply deciding to live in a world where they somehow don't apply?
FWIW, if you want a reference for "even with seemingly no causality a related work was classified as a derivative work for copyright", here is the particular case:
No, as I said I think you are theoreticizing. Why are you not asking me whether I avoid leaving my house just because there could be some crazy guy shooting at me?
Here's why I still leave my house most days. My life would not be worth living. I have a moral right to leave my house. I have good faith in the state to protect this right, although I know some people have indeed been shot (even by policemen!). It's not worth my time theoreticizing about this possibility.
Note that the situation is different if you move to advanced engineering projects and parties involved with huge amounts of money. The possibility of a mean-spirited lawsuit there is a lot more realistic (while probably still as unrealistic as batshit crazy).
I definitely do not copy code from Stack Overflow that is more complex than a line or two (and so will be under the deminimus threshold for copyright); are you?
No, if you write your own code it is _not_ a derived work of this. Copyright is not on the idea ("use this or that data structure"), only on the expression.
Because in a lot of cases the most logical expression of a given idea in tech will be quite similar, and in that case having clear documentation that shows that your implementation is an independent expression of a description may help prevent allegations that you just copied someone elses code and changed it a bit.
That just means it was copied without permission... like this code, which is by default All Rights Reserved. For maybe more on-topic examples, though, note companies that are very careful about employees looking at open source code.
While this code is "all rights reserved", you do have the right to view it according to the GitHub terms of service. This is not true for Windows.
Alleging that Wine authors have participated in illegal sharing of source code would be a powerful accusation, and the authors clearly want to avoid it.
No, if you read someone else's book and write your own with the same overall plot you are considered a derivative work, and people have absolutely lost copyright lawsuits over photographs with the same composition as an existing one that they were copying. The idea here is "memory allocator", and the "expression" is the order and structure used to implement that idea.
