10 ms·

Memory management in C programs

162 points by nagriar 13y ago

jmspring 13y ago
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.
- adamnemecek 13y ago
  What's your point exactly?
  - jmspring 13y ago
    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.
    - ANTSANTS 13y ago
      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.
    - eru 13y ago
      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.
- deleted 13y ago
  [deleted]
- dllthomas 13y ago
  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".
fsloth 13y ago
Jesus Christ. Let the reader beware indeed. There are horrible suggestions here that will result in bad code if you think "Hey, that's a cool suggestion, I'll try that!". Or "Hey, I read in that blogpost this is OK in C, I'll do this". 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.
- jamesaguilar 13y ago
  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).
  - mpyne 13y ago
    On the contrary, every thread has its own stack. In fact the stack was the original "thread local storage".
    - jamesaguilar 13y ago
thepumpkin1979 13y ago
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.
- Nursie 13y ago
  IIRC while this is true and good practice, many modern OS/libc implementations will zero stuff anyway.
  - KMag 13y ago
    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".
fjarlq 13y ago
"...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.
- cturner 13y ago
  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.
  - TheCraiggers 13y ago
    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.
    - 13y ago
userbinator 13y ago
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 str = malloc(1 + sizeof "submenu"); strcpy(str, "submenu"); return str; could be replaced by a single return strdup("submenu");
- anon4 13y ago
  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
  - 0x09 13y ago
    4) `strdup` is a POSIX extension whereas NetHack is cross platform.
    - angersock 13y ago
      Easy to fix with a macro.
laichzeit0 13y ago
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.
- baruch 13y ago
  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.
malkia 13y ago
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 :)
reality_czech 13y ago
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.
- logicchains 13y ago
  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.
- deletes 13y ago
  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.
  - reality_czech 13y ago
    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.
fdej 13y ago
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.
- dTal 13y ago
  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"?
  - fdej 13y ago
    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.
- antimagic 13y ago
  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.
616c 13y ago
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.
yew 13y ago
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!
barrkel 13y ago
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.
ballard 13y ago
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;
bitwize 13y ago
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++. :)
jbert 13y ago
> 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 http://www.pipeline.com/~hbaker1/CheneyMTA.html [https://news.ycombinator.com/item?id=7417906 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().

162 points by nagriar 13y ago

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.

adamnemecek 13y ago
What's your point exactly?
- jmspring 13y ago
  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.
  - ANTSANTS 13y ago
    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.
  - eru 13y ago
    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.
deleted 13y ago
[deleted]
dllthomas 13y ago
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".

fsloth 13y ago

Jesus Christ. Let the reader beware indeed. There are horrible suggestions here that will result in bad code if you think "Hey, that's a cool suggestion, I'll try that!". Or "Hey, I read in that blogpost this is OK in C, I'll do this". 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.

jamesaguilar 13y ago
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).
- mpyne 13y ago
  On the contrary, every thread has its own stack. In fact the stack was the original "thread local storage".
  - jamesaguilar 13y ago

thepumpkin1979 13y ago

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.

Nursie 13y ago
IIRC while this is true and good practice, many modern OS/libc implementations will zero stuff anyway.
- KMag 13y ago
  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".

fjarlq 13y ago

"...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.

cturner 13y ago
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.
- TheCraiggers 13y ago
  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.
  - 13y ago

userbinator 13y ago

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 str = malloc(1 + sizeof "submenu"); strcpy(str, "submenu"); return str; could be replaced by a single return strdup("submenu");

anon4 13y ago
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
- 0x09 13y ago
  4) `strdup` is a POSIX extension whereas NetHack is cross platform.
  - angersock 13y ago
    Easy to fix with a macro.

laichzeit0 13y ago

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.

baruch 13y ago
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.

malkia 13y ago

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 :)

reality_czech 13y ago

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.

logicchains 13y ago
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.
deletes 13y ago
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.
- reality_czech 13y ago
  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.

fdej 13y ago

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.

dTal 13y ago
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"?
- fdej 13y ago
  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.
antimagic 13y ago
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.

616c 13y ago

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.

yew 13y ago

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!

barrkel 13y ago

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.

ballard 13y ago

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;

bitwize 13y ago

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++. :)

jbert 13y ago

> 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 http://www.pipeline.com/~hbaker1/CheneyMTA.html [https://news.ycombinator.com/item?id=7417906 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().