Memory management in C programs
nethack4.org
nethack4.org
For instance: Stack allocation. It's seldom OK to use static variables even with accessor functions. Wrap the state that the functions operate in structs that you pass to functions. There are a few places where you cannot avoid effectively global variables (usually external resources like sockets, window handles etc) but those should be wrapped in their own subsystems and not leaked all around the place in global variables. "Still, this is one of the better reasons to use a global variable." - congratulations, you are on your way to Spaghetti Code land. Would you like some black pepper with your Complexity Bolognese? Protip: Wrap it in a struct and pass it as a variable. Or redesign your module dependencies.
Too much state in your God-Object. Getting confused? Need better design. C is not an excuse not to write modular, understandable code where the program flow is obvious.
Yes, it can get really verbose. If verbosity is an objection, then do not write in C.
Or, if you dislike verbosity, do what so many others have done. Write your core routines in C and then write the high level logic in Lua.
Please excuse me my theatricality. I'm not assaulting the author. I'm rather agravated that this post has this level of visibility and the potential damage it can do.
>I'm rather agravated that this post has this level of visibility and the potential damage it can do.
Potential damage, really? The people naive enough to try everything listed in this article probably aren't programming in C to begin with these days. The average Fancy New Web Framework That Will Change Everything Again article hurts way more than this.
The person you responded to didn't suggest this.
Why? I note that the word "because" doesn't appear once in your post.
Sorry, my rant was a fairly long to begin with :D
To clarify my position, I'm maintaining and developing as my day job a few MLOC CAD application that is two decades old which has core written partly in C. This is one of the most painfull antipatterns plaguing that codebase.
It's seldom OK to use static variables even with accessor functions. Because:
1) Understandability. Suddenly it's non obvious what the state actually is that your code modifies. Functions are not functions that get input and process output, but become detached nodes in a non-obvious call graph. Yes, it's embedded in the stack, and, yes, you can figure out ways to figure out what is actually happening but it's not obvious from the code. There are quite a few non-obvious things affecting a real world production code. It does not help to add a few non-obvious patterns which are not necessary. I.e. this pattern creates unnecessary accidental complexity that hinders all velocity.
2) Suddenly it's impossible to structure the code to parallellize it. The explanation is fairly long but if it's non obvious I can return to this point.
I thought it was a good post and provides a good overview of different methods along with a discussion why you should or shouldn't do some of these things.
I'm pretty certain that in the Linux kernel you can find each and every one of these methods used more than once and for a good reason.
Maybe in a normal user space app you have the luxury of being able to malloc/free everything and have nice high level containers, etc available but when writing C code, the assumption of normal user space apps is not necessarily true.
All of these methods - and when not to use them - is very useful knowledge.
And the OP is right - globals, especially if not encapsulated within a single code module, are a prime cause of opaque spaghetti code.
So I made once had the displeasure of doubling the performance of a fission reactor safety simulator by disabling win32's swap... 30 years and 2e7 LoC codebase. >.<. The working set was nowhere near smart, but it did work faster than AIX, HP-UX, SCO & Solaris/SunOS ports.
I guess it depends on what exactly you're working on, but passing in a stack-declared for a function to fill with its results seems better to me anyway, as general practice. Preferable to allocating a new structure in the function and then returning it, that is. There are no ownership issues and nobody has to remember to free anything.
Heap emulation with static buffers comes with its own costs - either you end up writing an allocation engine or you just use a large buffer with an advancing pointer, free() does nothing and the whole thing has to be reset every so often, which means that you have to convince the other developers on the team that it's not to be used like normal malloc and please be careful and ... that's a whole other can of worms!
Like I said, the presentation rubbed me the wrong way by first exposing antipatterns and then not taking a very strong position against them.
I was a NetHack devteam member for a few years in the late 1980s and early 1990s, so I got to know the code pretty well... it's pretty hairy, and that may be putting it mildly.
I wish the NetHack 4 folks would reconsider and explore a complete reimplementation in a new language. Yes, it would be a much more significant project, but I think it would be the best thing for the game in the long run. And it would be a lot of fun, but I'm biased.
I wonder what language would be the best choice at this point, for such a project.
Even beyond the code, there's plenty wrong with nethack as a game: arduous inventory management, it gives the impression of being a sandbox game but it isn't really (hunger clock, inflexible ascension goal).
Rather than reform that, it'd be more straightforward to just create a new roguelike. Brogue is an example of this.
It's never made that claim. For one, I don't think sandbox games even existed in form, and certainly not in name, in the 80's. Secondly, it has always been a rogue/hack clone, solidly in the 'roguelike' category. Most people would not associate roguelikes with sandbox games, although I might agree that more recent games like Minecraft with perma-death mode may blur the lines somewhat if your sole definition of roguelike is "can't load your game after you die."
In fact, Nethack and its brethren are more of a breath of fresh air in the current gaming world. They have one goal, and that's it. For Nethack, it's get to the bottom, grab grab Zot, get out alive. That's about as far from a sandbox game as you can get.
> grab Zot, get out alive
But this is just a huge undertaking for very little gain. You rewrite the 110K LOC of the core game engine in a new language so it works the same as before (which will be difficult because no tests) for having ... what exactly?
If you don't have years to spare, an incremental rewrite would be a viable option. But do Objective-C or C++ really look like a good choice nowadays?
Then there's also some big non-technical issue. With a rewrite in a different language you lose the connection to the old code that dates back to the 80s. It would no longer be a NetHack fork but a NetHack clone. For a fork developer who already has to fight an uphill battle as the DevTeam is dormant for 10 years but is still claiming that they are working on $NEXT_VERSION, this would be another of those arguments for "it's not the real thing, I'd rather play vanilla".
BTW, for a reimagination of NetHack that did something similar, take a look at http://www.wazhack.com/ . They weren't that exactly replicate the NetHack functionality but it at least feels close.
I was a NetHack DevTeam member for a few years in the late 1980s and early 1990s, so I got to know the code pretty well... it's pretty hairy, and that may be putting it mildly.
For the time it was written in and with the organizational structure it was developed with, I think it's surprisingly good. After all, it is still C, so it is not for the faint of heart anyway. Sure, there are things that could be better, like that monster attacking monster, monster attacking player or player attacking monster is usually coded in three different places. But for a code base of this size, it's overall not bad. I find myself cursing more often about the limitations of C than of NetHack's code itself. :)
I wonder what language would be the best choice at this point, for such a project.
Depending on what your goals are, C could still be the best choice for such a project.
If you want a program that runs on as many different systems as NetHack does, C is still hard to beat. Heck, it even works on Android and iOS.
Maybe something like Rust or Go, but we're still not there that C has been clearly superseded in all domains.
Anything that compiles to native modules and has a clean C FFI would work. You could encapsulate the current code into a black-box set of APIs, and then transition those APIs module-by-module from being calls into the old crufty code, to being calls into shiny new rewritten code. (This is the strategy recommended at http://laputan.org/mud/).
Go is pretty perfect for your use-case, though; it produces portable, low-ish level application code, and while it's a bit less performant than C, you don't really need every scrap of C's performance in the way an OS or a 3D game does. Besides all that, it's very easy for grumpy, staid old C developers to learn, in the same way that Plan9 is easy for grumpy, staid old Unix administrators to learn: it's all the same ideas, just streamlined for newer use-cases.
C++ is almost equivalent of Latin today, which is kind of good and kind of sad. It takes arcane experience at scale to know which obscure traps not to fall into, making it inaccessible to casual hacking. Which is the point.... The codebase includes a cultural zeitgeist. (And fun.)
C for example isn't really that complex language and using C++ well isn't that hard. Somehow I feel that users of the "easier" languages decide that c++ is impossible to learn before they even bother trying it.
Yes, you can get leaks with malloc. But valgrind is actually really good at finding them. So if you have reasonable unit tests, you can just run valgrind on all of them and get a lot of coverage.
The problems that Nethack is having are basically self-inflicted. They opted to use setjmp and longjmp to emulate exceptions. So they don't have a good way of cleaning up things they malloc'ed. setjmp and longjmp are basically a way of implementing a cross-function "goto". it's just as bad as it sounds. Not to mention, they use a lot of functions like sprintf that have basically been banned by everyone else in the world. Hopefully they're not using gets()...
You don't need to implement crazygonuts memory management unless you're writing a high-performance database or kernel or something. Certainly not for a text adventure! Just. Use. Malloc. So this whole thing is just an exercise in making something really simple into something really complicated. Which I guess is what Nethack is, anyway.
Also, what is "really slow" in the context of nethack? I'm willing to bet that you could malloc and free till the cows come home and never even notice in nethack. I bet the whole program doesn't take up more than a few megs of memory anyway.
Not that I'd actually recommend it without significantly more investigation, but it's occurred to me that one could probably build a usable and reasonably safe framework around setjmp and longjmp where when you setjmp you create a context with which you can register cleanup actions (possibly coupled with a region allocator) to be run when something longjmps. I'm not actually sure the kind of constraints that would motivate this, though, without a clearer picture of what the code would look like.
I've had to code on embedded devices (where RAM is anything from 4kb to 512kb) where all the above have been true at some point.
I tend to prefer to allocate on the stack when possible and when the context is right and that works when working in threads or user-space-threads (aka coroutines) that are all hierarchical. It makes some things simpler though you need to care about the stack size and its usage. The places that do need dynamic memory allocations would normally use a memory pool for same sized objects to be allocated from.
Finally, write unit tests and run them through Valgrind. That catches almost all memory-related bugs.
There are certainly non-examples of this pattern (with legitimate uses, for sure, but they can be avoided as a general rule). One is global variables. Another is creating an object in one part of a program and destroying it in another (as opposed to the start/end of the same function or block), or worse, in multiple possible locations.
I personally tend to look at malloc/free in the same way that I look at if statements. I generally consider code to be cleaner without them, so where possible I will avoid them, but sometimes that's not possible, which is why malloc / free (or if statements) exist.
For me, in my current project, it's message passing between the low-latency thread and other threads.
But there are always other heaps (that might or might not work like the stack above, or have say dmalloc's mspace api used there for other uses), and some space should be left to CRT itself, nowadays even more with lambda's in C++11 and for other library functions.
For Tools I started to not care, simply because it does not matter that much. Just make sure _NO_DEBUG_HEAP=1 is set when you run through the Visual Studio debugger :)
This is true, but there is the glorious exception which is "Cheney on the MTA": http://www.pipeline.com/~hbaker1/CheneyMTA.html [https://news.ycombinator.com/item?id=7417906]
This describes a way of implementing a scheme->C compiler using CPS which allows the C functions to never return, and doesn't blow the stack. When the stack gets big enough, you do a garbage collection run, copying live data to a new stack. Then, you reset the stack pointer using a judiciously chosen argument to alloca().
My personal preference is for not using fixed-length buffers for storing things like (non-static) strings, unless I know for certain that they won't ever grow past a certain length (and document it clearly, so if something ever needs a length check I can go back and find them); strings of user input and other possibly indeterminately long things get documented as "limited by available memory" (i.e. they're dynamically allocated) or "limited to X bytes" (usually due to a fixed-length buffer somewhere).
As a note, the fragment
str = malloc(1 + sizeof "submenu");
strcpy(str, "submenu");
return str;
return strdup("submenu");2) the writer may be using a different malloc than the libc one
3) there is an argument to be made that using malloc plainly like this instead of hiding it with strdup makes it easy to see the sites in your program where heap memory is allocated
(IMO, explicit initialization is better than just zeroing stuff out, because there's no guarantee that zeroed memory is valid. Especially when pointers are involved—dereferencing a null pointer in C is undefined behavior, so compilers are free to wreak havoc on any code that it can prove attempts to do that...)
Modern OSes will zero out pages when your process brk()/ mmap()/etc. them into your address space, to avoid security problems. However, unless you're using a debugging version of libc/LD_PRELOAD'ing malloc/free implementations, etc., I don't believe most malloc/free implementations will necessarily hand you memory containing a known pattern. Certainly the main selling point of non-default malloc/free implementations is performance. Zeroing out memory between uses by the same process has some overhead, and the benefits are more of a mixed bag than the case of accidentally leaking sensitive data a programmer has forgotten to zero out (or doesn't think is sensitive) between processes.
Your free() implementation can't return partial pages[0], and in general will only return multi-page contiguous blocks to the OS, due to memory fragmentation, anticipation of soon needing to malloc() again, and a desire to keep system call overhead down. The consequence is that if you do a lot of malloc()ing and free()ing, you're likely to sometimes get zero'd out pages, and sometimes get garbage that your process has previously written to memory, but you should never get garbage that another process has written to memory. (Unless, of course, it's shared memory or copy-on-write shared with a parent process.)
[0] Well, if your CPU/MMU supports segment registers or you're willing to do unsafe things that can't be enforced by the MMU, then your OS could support returning partial pages to the OS. However, modern desktop/tablet/smartphone OSes don't work this way.
EDIT: Too lazy to read how to get asterisks to show up consistently. I changed *aloc to "malloc".
Just to helpfully let you know when you're reading a bit of uninitialized RAM.
On that note, while the article doesn't (explicitly) mention it, it would be wise to remember that VLAs of unbounded size will end up overflowing the stack eventually. They have their uses, but can be tricky to apply safely. Be careful!
Just wanted to point out that alloca exists pretty much everywhere, so you don't need to know the exact size at compile time. You still need to know you're not going to overflow your stack, of course.
There are also variable-sized stack allocated arrays, as in C99 and gcc extension.
Though IMO the value of a consistent approach outweighs the small performance advantages of dynamic stack allocation - it would very very rare for me to use either approach today.
Just wondering why tcmalloc or boheme GC weren't discussed. Rewriting from scratch often equivocates to reinventing wheels, and avoidable typing, testing and maintenance. --effort && ++quality == awesome;
C will always be here for historical reasons and because of all the code written in it that would be difficult to convert. But new development should be in C++. Yes, Linus, if you were starting Linux today I'd take you to task for not using C++. :)
Anything you do above that to make your life easier is up to you.
C is pretty darn simple in terms of memory management -- you own it, deal with it. If that is too hard, find a higher level language.
My point - I read the article and agree as described are typical ways of dealing with memory in C (and in particular within Nethack). At the end of the day, dynamic memory allocation comes down to tracking mallocs and frees and whatever extra book keeping you put on top of them.
Reference counting came up. There are libraries that help with such, but you better understand what that actually means.
Wrapping primitives in higher level abstractions can lead many developers to wondering why there is a memory leak. Before you embrace the abstractions, you better darn well understand what is going on under the hood.
I've seen many inexperienced devs get lost in simple valgrind dumps.
The article talked about different issues, though.
More accurate (on POSIX systems), although not terribly useful, would be:
There is mmap and there is munmap and there is brk.
Anything you do above that (including malloc, static allocation, and the stack) to make your life easier is probably built upon things provided by libc and the C runtime.
On an embedded system, all you might have is "there is RAM".
When I looked into Ada and memory management, out of curiosity, I did not find a lot of information about pointers. Or a garbage collection system, and casual reading confirms that Ada has a less manual version of pointers (from what I gather) and manual memory management, and no garbage collection. Given its syntax and semantics, which remind me very, very vaguely of Haskell (which I am sure is bound to insult someone on HN, specifically Haskellers), I could not imagine this as a systems language. Then again, even though I am ignorant of such things and do not know C/C++ (the latter I only took briefly in undergrad, and I have mixed reactions), I am product of the C/C++ generations and the stand of the shoulders of Unix and Linux giants, as I have looked into computer science and Linux application source code in attempt to understand. Not even write the code mind you, just understand. Perhaps others were exposed to Pascal and BLISS, so the alternative perspectives made it seem possible. I do not have that perspective, so I feel dazed and confused by alternative offerings when reading them. I get the idea generally, but still whisper to myself with a concerned "How!?", even though it should be more obvious.
In short, I cannot really conceive of manual memory management without pointers and pointer arithmetic as it presented in C and/or C++. I was terrible at it, granted, but everything else I see from Rust to other system languages which promise a systems language without GC and offer some equivalent of memory management done manually do not click. They seem foreign and impossible because I have always assumed, for better or worse, C is the way you interface with a modern PC or embedded system by managing each and every pointer, or you are on your way to assembly and then memory is one of many complicated underpinnings you must understand intimately, not just the must troublesome one.
But I am an amateur programmer. I recently the saw the threads on FORTH. I want to look because, as much as I "know computers" the idea of this kind of very low level stack language is very foreign to me, just from looking at it I feel odd and not sure how it could possibly work. The same would be true of writing low level code in Haskell. I like it a lot, for all its beauty and warts, but I have just assumed you must learn to manage such things manually and in an ugly fashion a la C/C++ to learn system management in a programming language in our generation, and no amount of screaming or holding your breath until in the red face will change that.
However, a lot of this is conditioning. Maybe others can share other observations to counter my admittedly very naive experience.
Ada does not specify GC. Ada does have pointers; it calls them "access types". It supports unconstrained types, which are allocated on the stack when declared (no need for malloc/new). It also supports more sophisticated memory management abstractions, like Storage Pools and Controlled Types.
> I could not imagine this as a systems language.
Ada was designed to be a systems language, provides all the facilities one would need, and is extensively used as one. So beyond "it's not C" I don't really know how you could come to that conclusion.
What you question is the central point of my comment: maybe I am biased by learning C++ on SunOS, then playing with Linux, then using FreeBSD at work, but it is hard for me to imagine systems programming without C/C++-colored glasses in terms of memory.
I have no doubt it is possible in Ada. It is just less ugly and dangerous than C, so I thought you are just forced to deal with pointer management in your own brain with rough syntactic constraints because that is the highest you can go wo systems programming on the metal without going to assembly.
I know it seems silly, but that I think drives people to embrace C completely as the only answer, and not just the preferred answer. Fortunately, forcing many to deal mean there has been good progress since the OP article was first published.
As an aside, Ada was intended for large numbers of programmers of varying, often mediocre skill to cooperate on large programs while minimizing errors and preventing localized programming errors from propagating too far. That's something a lot of OSS projects could use.
I also think it's important to understand that Ada was one branch of a family of languages descended from ALGOL that looked at the problem through a similar lens (a very not-C/C++ lens). Pascal is the direct ancestor, of course, but in a addition to Ada, Pascal evolved into a number of other systems programming languages like Modula-2 & -3 and the various Oberons. Close cousins Mesa & Cedar were Xerox PARC systems programming languages. There's not a lot left of the Modula's or Mesa/Cedar (regrettably...Modula-2 was much better than Pascal for non-academic programming and Modula-3 was a really comfortable all-around language), but there's a reasonable amount of OSS Oberon laying about.
EDIT: How could I forget...if systems programming is your kink, be sure to check out UCSD p-code and ETH m-code. These are Pascal/Modula virtual machine environments and the direct ancestor of the Java VM and M$ CLR.
As for Pascal and Oberon, when I saw the computer and OS of the same name written in Oberon (I think), my mind was blown with how advanced it was. Thanks for the good comment.