Memory management in C programs(nethack4.org)
nethack4.org
Memory management in C programs
http://nethack4.org/blog/memory.html
74 comments
Nethack dates back to 1987 (as the article says, predating ANSI C) and the same codebase is still in development today. You need to keep that in mind when reading the article. Nowadays, yeah, just using a garbage collected language would solve the vast majority of their problems with negligible effects on performance (it's a roguelike), but it wasn't really an option when the project started, and rewriting it now isn't acceptable either. This article still full of interesting tricks to have up your sleeve (comically unsafe things like the "ring buffer of objects" aside) in case you're in a similar situation as the Nethack devs were in the 80s and 90s, pushing the boundaries of what is possible in a video game/computer program of your choice on limited hardware.
>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.
>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.
>Nowadays, yeah, just using a garbage collected language would solve the vast majority of their problems with negligible effects on performance
The person you responded to didn't suggest this.
The person you responded to didn't suggest this.
> 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 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.
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.
It's amazing how much you can achieve without malloc and free if you're just careful to pass in the right output space and buffers as part of your function call. You rarely really need them for most functional code. (Non-trivial data structures may be different...)
And the OP is right - globals, especially if not encapsulated within a single code module, are a prime cause of opaque spaghetti code.
And the OP is right - globals, especially if not encapsulated within a single code module, are a prime cause of opaque spaghetti code.
I've written plenty of embedded code where the first rule was "Thou shall not malloc." In just about every case it turns into setting aside static buffers and doing manual structure allocation. This is such a common idiom in embedded systems that most RTOS systems have this functionality built-in.
The embedded system I'm working right now doesn't have malloc as part of its platform SDK anyway, so it's not like there's a choice :)
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!
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!
Remember vintage Fortran.
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.
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.
You are correct, discussion is always welcome. I agree that "All of these methods - and when not to use them - is very useful knowledge." would be a very valuable proposition.
Like I said, the presentation rubbed me the wrong way by first exposing antipatterns and then not taking a very strong position against them.
Like I said, the presentation rubbed me the wrong way by first exposing antipatterns and then not taking a very strong position against them.
Another example. Working "correctly" with threads is not something I would typically think of as a distinguishing feature of stack allocation. All basic c allocation techniques work equally well with threads. That is, they all work fine when only one thread attempts to perform transactions on the memory, and none of them do if more than one does (sans locks, of course).
On the contrary, every thread has its own stack. In fact the stack was the original "thread local storage".
Yes, my point is that if you try to operate on memory from another thread's stack, it is equally unsafe as operating on memory from the heap you received from another thread. The allocation method is irrelevant to whether it is safe. What is important is whether it is being accessed concurrently.
> 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.
Why? I note that the word "because" doesn't appear once in your post.
Why? I note that the word "because" doesn't appear once in your post.
> 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.
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.
"...converting NetHack's codebase to a new language would be very difficult (even one as similar as C++, which has many potentially relevant details that differ from C)."
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.
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.
A little while ago I listened to the RougeLike Radio podcast about NetHack. While the people on there, mostly developers of various clones, had plenty to say about the issues with NetHack, including its code, one thing they did agree on: NetHack is a game about exceptions. What makes it fun is exactly what makes the code is damn terrible; that is, every interaction between any two or more objects is a series of if/else if statements. For example, you can dip an object into another object if it's a potion, a fountain, a sink. If you dip it into a fountain, you may summon a jinni, or the fountain might dry up. If you dip a potion into another potion, you might make a new potion; or dilute the original; or bless or curse the original. Or you might create an explosion. This is a simple example with mostly straightforward rules. Things like interactions between thrown objects and their targets are more subtle but more complex. This is why I play NetHack: because the complexity makes it fun. A simpler game like 2048 can also be fun, but it's predictable. NetHack is different every time you play it.
I'm another NetHack fork developer (with UnNetHack leading a small team and with NetHack-De having a fun side project), so I also had to think about the issue of rewriting in a new language.
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.
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.
> 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?
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.
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.
I don't think Go is the right option here, while you can call C code from Go, last time I checked it wasn't possible to call Go from C without having it called the other way around before. I'd rather suggest going for C++ (or maaybe Rust... well, not really).
The language may not be mature yet, but C code can very easily call into Rust code (and, by proxy, any language that can call into C can call Rust code).
The spaghetti is part nethack's identity, it is accretion not architecture. Part of what's fun about it is that it works at all, despite the code being so awful.
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.
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.
I find it interesting that you claim one of Nethack's problems is that "it gives the impression of being a sandbox game but it isn't really (hunger clock, inflexible ascension goal)".
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.
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
Somehow I am sick of people taking this up all the time when some project is written in C / C++.
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.
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.
It would be interesting to hack Lua into NetHack so that some of the game logic/AI could gradually be moved over...
py, rb... js probably.
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++ 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.)
Memory management in C is really not that hard. If it's big, use malloc or calloc. If it's small and of fixed size, use the stack. Don't use globals unless you really, really have a good reason.
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.
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.
Allocating chunks over ~1024B repeatedly becomes really slow, because malloc tries to return as much memory back to the system when you free. This takes magnitudes more time than just a function call. There are some parameters you can tweak in it, but I think that is the reason many games have their custom allocator, which malloc a huge chunk of memory and then keep it until the program exists.
Some malloc() implementations return memory to the OS during free(). Many don't. For example, tcmalloc in its default configuration never returns memory to the OS.
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.
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.
"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()..."
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.
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.
Though not what it's designed for, halloc[1] Is similar to what you are talking about; if each function manually allocated its locals with halloc, and used the parent function as the parent allocator, then you would get an unbroken tree, and would free all the children upon returning from the function that had called setjmp().
[1] http://swapped.cc/#!/halloc
[1] http://swapped.cc/#!/halloc
Yeah, for sure. Wouldn't allow for cleanup of non-memory resources, though, so far as I can tell.
As someone who likes C and Go for their lack of support for exceptions, the thought that someone might actually want to implement exceptions in C is mind-blowing.
Yes. For most applications, malloc is fine and when you want to reduce mallocs (pushing them out of performance critical code) usually pushing stuff up the stack is the way to go. That said, in development where C is really the right answer, malloc being a bad choice (and/or entirely unavailable, as in some embedded work) is far more common than in other programming - I think it's still a minority, though.
Most of these techniques are extremely commonplace in embedded C programs where you might have a combination of the following: no malloc/free, no operating system or threading library (everything sits in a void main() { while (1) {} } loop, you have limited memory and you need to fix the size of your data structures, you need to reason about the correctness of your code for safety/security purposes and not doing any dynamic allocation makes this a lot easier.
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'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've been working on Storage systems with multi-gigabytes of RAM where you still reason about your memory in much the same way. These systems have lots of RAM but properly intend to make use of all of it.
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.
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.
Nearly all the time, memory management in C can be done using the following incredibly sophisticated pattern: create an object at the start of a function, and destroy it at the end of the same function. Use constructor/destructor functions or macros to hide the details (such as whether the object is a plain fixed-size struct, or has to allocate additional variable-size memory on the heap). There are situations where this pattern cannot be used, but they can be made very rare in properly structured C code.
Finally, write unit tests and run them through Valgrind. That catches almost all memory-related bugs.
Finally, write unit tests and run them through Valgrind. That catches almost all memory-related bugs.
I can see where you're going with this, but I think you're being a little glib with the "nearly all the time" bit. There are large chunks of functionality that can't be written that way. The most obvious one is graphical objects, which are typically expensive to render. You can't be destroying / recreating them on the fly, the number of graphical elements in use changes radically over the lifetime of a typical graphical application, and you generally have an event loop, which means the only function that would keep the objects alive is at the top level of the event loop.
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.
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.
Yeah, definitely a little glib. There are certainly prominent exceptions. Still, I think it's a valid general principle. At least, it works well enough for me, and I very rarely have to think consciously about memory management in C. But YMMV, different application domains, and all that.
"The most obvious one is graphical objects, which are typically expensive to render."
For me, in my current project, it's message passing between the low-latency thread and other threads.
For me, in my current project, it's message passing between the low-latency thread and other threads.
You cannot create objects in C. I tried to work out what you meant, but honestly I can't. Where do you put these "constructor/destructor" functions? In the global namespace? So you have structs, and functions that modify structs. How is this pattern different from the one we call "programming in C"?
Sure, structs and functions that modify structs are the bare mechanisms provided by C. From the higher-level point of view, structs may represent objects and a constructor is then just a piece of code (possibly implemented a function) that initializes a struct, and a destructor frees any memory it owns (if the struct does not contain any pointers, destroying it is just a no-op). Initializer and de-initializer might be better terms.
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.
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.
It most notably does not work in the case of longjmp() which nethack uses a lot.
In consoles games, often the following is found - big double-stack - predefined buffer, that takes most of the memory. Memory is allocated by bumping a pointer, for example data for levels loaded increases left -> right (up->down), and temporary data (characters, temp scene, etc.) right->left (down->up). When level unloads (or several of it's associated files), memory is put back before (left or right).
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 :)
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 :)
> but if there are no normal returns involved, nothing on the stack will ever be deallocated, and your program is effectively just one giant memory leak.
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().
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().
Detailed articles like this are great for understanding and exposing all the freedom and power you get with C's memory management philosophy. I agree with the author's view that it is sufficiently complex that it can force you to think about not allocating, i.e. "should I really be doing this?" and thus you often arrive at a simpler, more efficient solution than you would if you'd used something like Java and thought "I'll just create a new X object". I see this all the time in C code written by programmers who first learnt Java - malloc()'ing and copying objects everywhere, often with an underuse of free() and thus plenty of memory leaks.
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
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");1) that will call strlen on "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
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
I wish these kind of articles targeted to higher-level programmers would start teaching to use 'calloc' before 'malloc'. New C users will have a bad time catching random bugs when they allocate a struct via malloc and immediately check members using de-referencing in 'if' conditions which will be randomly evaluated as true because malloc doesn't initialize the memory to zero and therefore all the members of the struct through the pointer returned by malloc are full of garbage. My rules are: either use malloc if you intent to immediately initialize the memory or use calloc and pass the pointer around.
On the other hand, if it's available, Valgrind will do a better job of catching uninitialized memory use if you use malloc instead of calloc.
(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...)
(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...)
That's true. I usually initialize the struct in the stack and then assign it to the pointer, then pass the pointer around.
IIRC while this is true and good practice, many modern OS/libc implementations will zero stuff anyway.
Don't count on it.
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".
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".
... or initialize you freshly malloc'd memory to DEADBEEF for you.
Just to helpfully let you know when you're reading a bit of uninitialized RAM.
Just to helpfully let you know when you're reading a bit of uninitialized RAM.
Techniques like these are always interesting, even if you don't have much opportunity/need to apply them. The source for software like NetHack might not be a good place to look for best practices, but it can be enlightening in other ways (if you're careful to avoid copying just anything you see).
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!
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!
Re stack allocation: It requires you to know how large the object could possibly be at compile time
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 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.
I've worked on embedded C++ network stacks that restrict use of *alloc and new for various sized buffers and classes that have to be preallocated. That's one approach.
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;
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;
RAII and smart pointers pretty much make C, and the programming style typical of C programs, obsolete.
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++. :)
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++. :)
There is malloc and free.
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.
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.
There is plenty of memory management in C that has nothing to do with malloc or free.
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".
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".
[deleted]
What's your point exactly?
I welcome the down votes.
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.
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.
You're being downvoted because these comments have little to do with the content of the article, which is about "dirty" low-level memory management techniques designed to avoid naive heap allocation, not trying to abstract the problem away.
Malloc and free are not as low level as you portrait them. They actually do quite a bit of work, that could be done differently.
The article talked about different issues, though.
The article talked about different issues, though.
On a somewhat related tangent, but a tangent just the same, Ada came to my mind because people in another thread about avionics in relation to the Malaysia Air Flight were debating the efficacy and/or safety of Ada versus a language like, for example, Haskell.
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.
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.
My opinion, after thirty-some years of programming, is that you basically have it right. If you need low-level control or you need to squeeze out every possible clock cycle, use C/C++; they're designed for that sort of thing and they have the tool chains, the APIs, the pool of available expertise. If you don't need those things, use a managed language; my preference is Python, but if Haskell is what floats your boat then by all means go with that.
> Ada and memory management
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.
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.
I saw that access type information, but the docs were not clear to me.
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.
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.
I think you're using an awful lot of words to say "if all you have is a hammer, then every problem looks like a nail". Yes, if all you've ever been exposed to is C/C++/Unix like environments, then an idiomatic Ada solution to many programming problems will be conceptually difficult to grasp. That would be true of any not-C/C++ language or not-Unix environment.
Sorry, I am wordy because I was busy and overtired. To keep it brief: you seem to have some knowledge on Ada, can you point me to any interesting open source projects I can use to understand? I have tried and not found many.
I don't have any particular suggestions for open source Ada projects to examine (other than, obviously, the GNAT Ada compiler). My experience with Ada was on decidedly not open source projects, and Ada suffered in this respect in that there wasn't a good open source Ada compiler until long after interest in Ada outside of the defense industry faded. Googling for "ada open source" shows a good number of interesting (if dated) possibilities (these might be a good place to start: http://www.pegasoft.ca/resources/boblap/book.html and http://www.seas.gwu.edu/~mfeldman/ada-project-summary.html), but not to put to fine a point on it, the cool kids pretty much decided Ada was the US DoD equivalent of COBOL 20 years ago and ignored it.
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 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.
And with Ada that is the problem: not much out there. I did see some people using it for Arduino, I thought that was neat and why it came to my interest again.
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.
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.
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.