8 ms·

Understanding Memory Management, Part 1: C

237 points by ekr____ 2y ago

samsquire 2y ago
Thanks for such a detailed article. In my spare time working with C as a hobby I am usually in "vertical mode" which is different to how I would work (carefully) at work, which is just getting things done end-to-end as fast as possible, not careful at every step that we have no memory errors. So I am just trying to get something working end-to-end so I do not actually worry about memory management when writing C. So I let the operating system handle memory freeing. I am trying to get the algorithm working in my hobby time. And since I wrote everything in Python or Javascript initially, I am usually porting from Python to C. If I were using Rust, it would force me to be careful in the same way, due to the borrow checker. I am curious: we have reference counting and we have Profile guided optimisation. Could "reference counting" be compiled into a debug/profiled build and then detect which regions of time we free things in before or after (there is a happens before relation with dropping out of scopes that reference counting needs to run) to detect where to insert frees? (We Write timing metadata from the RC build, that encapsulates the happens before relationships) Then we could recompile with a happens-before relation file that has correlations where things should be freed to be safe. EDIT: Any discussion about those stack diagrams and alignment should include a link to this wikipedia page; https://en.wikipedia.org/wiki/Data_structure_alignment https://en.wikipedia.org/wiki/Data_structure_alignment
- jvanderbot 2y ago
  > which is just getting things done end-to-end as fast as possible, not careful at every step that we have no memory errors. One horrible but fun thing a former professor of mine pointed out: If your program isn't going to live long, then you never have to deallocate memory. Once it exits, the OS will happily clean it up for you. This works in C or perhaps lazy GC languages, but for stateful objects where destructors do meaningful work, like in C++, this is dangerous. This is one of the reasons I hate C++ so much: Unintended side effects that you have to trigger. > Could "reference counting" be compiled into a debug/profiled build and then detect which regions of time we free things in before or after (there is a happens before relation with dropping out of scopes that reference counting needs to run) to detect where to insert frees? This is what Rust does, kinda. C++ also does this with "stack" allocated objects - it "frees" (calls destructor and cleans up) when they go out of scope. And in C++, heap allocated data (if you're using a smart pointer) will automatically deallocate when the last reference drops, but this is not done at compile time. Those are the only two memory management models I'm familiar with enough to comment on.
  - MarkSweep 2y ago
    There is this old chestnut about “null garbage collectors”: https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98125 https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98... > This sparked an interesting memory for me. I was once working with a customer who was producing on-board software for a missile. In my analysis of the code, I pointed out that they had a number of problems with storage leaks. Imagine my surprise when the customers chief software engineer said "Of course it leaks". He went on to point out that they had calculated the amount of memory the application would leak in the total possible flight time for the missile and then doubled that number. They added this much additional memory to the hardware to "support" the leaks. Since the missile will explode when it hits its target or at the end of its flight, the ultimate in garbage collection is performed without programmer intervention.
    - jvanderbot 2y ago
      Rapid disassembly as GC. Love it. Have you heard the related story about the patriot missile system? https://www.cs.unc.edu/~smp/COMP205/LECTURES/ERROR/lec23/node4.html https://www.cs.unc.edu/~smp/COMP205/LECTURES/ERROR/lec23/nod... Not a GC issue, but fun software bug.
    - gpderetta 2y ago
      Untill the software is reused for a newer model with longer range and they forget to increase the ram size. But of course that would never happen, wouldn't it?
  - pjmlp 2y ago
    The wonders of corrupted data, stale advisory locks and UNIX IPC leftovers, because they weren't properly flushed, or closed before process termination.
    - jvanderbot 2y ago
      I'll narrow my scope more explicitly: close(x) is not memory management - not at the user level. This should be done. free(p) has no O/S side effects like this in C - this can be not-done if you don't malloc all your memory. You can get away with not de-allocating program memory, but (as mentioned), that has nothing to do with freeing Os/ kernel / networking resources in C.
- caspper69 2y ago
  Nothing is going to tell you where to put your free() calls to guarantee memory safety (otherwise Rust wouldn't exist). There are tools that will tell you they're missing, however. Read up on Valgrind and ASAN. In C, non-global variables go out of scope when the function they are created in ends. So if you malloc() in a fn, free() at the end. If you're doing everything with globals in a short-running program, let the OS do it if that suits you (makes me feel dirty). This whole problem doesn't get crazy until your program gets more complicated. Once you have a lot of pointers among objects with different lifetimes. or you decide to add some concurrency (or parallelism), or when you have a lot of cooks in the kitchen. In the applications you say you are writing, just ask yourself if you're going to use a variable again. If not, and it is using dynamically-allocated memory, free() it. Don't psych yourself out, it's just C. And yes, there are ref-counting libraries for C. But I wouldn't want to write my program twice, once to use the ref-counting library in debug mode and another to use malloc/free in release mode. That sounds exhausting for all but the most trivial programs.
- mgaunard 2y ago
  In C, not all objects need to be their own allocated entity (like they are in other languages). They can be stored in-line within another object, which means the lifetime of that object is necessarily constrained by that of its parent. You could make every object its own allocated entity, but then you're losing most of the benefits of using C, which is the ability to control memory layout of objects.
  - pjmlp 2y ago
    As any systems programming language include those that predate C by a decade, and still it doesn't allow full control without compiler extensions, if you really want full control of memory layout of objects, Assembly is the only way.
    - gizmo686 2y ago
      In practice C let's you control memory layout just fine. You might need to use __attribute__((packed)), which is technically non standard. I've written hardware device drivers in pure C where you need need to peek and poke at specific bits on the memory bus. I defined a struct that matched the exact memory layout that the hardware specifies. Then cast an integer to a pointer to that struct type. At which point I could interact with the hardware by directly reading/writing fields if the struct (most of which were not even byte aligned). It is not quite that simple, as you also have to deal with bypassing the cache, memory barriers, possibly virtual memory, finding the erreta that clarifies the originaly published register address was completely wrong. But I don't think any of that is what people mean when they say "memory layout".
      - pjmlp 2y ago
        Now split the struct across registers in C. You are aware that some of those casting tricks are UB, right?
        gizmo686 2y ago
        Casting integers to pointers in C is implementation defined, not UB. In practice compilers define these casts as the natural thing for the architecture you are compiling to. Since mainstream CPUs don't do anything fancy with pointer tagging, that means the implementation defined behave does exactly what you expect it to do (unless you forget that you have paging enabled and cannot simply point to a hardware memory address). If you want to control register layout, then C is not going to help you, but that is not typically what is meant by "memory layout". And if you want to control cache usage ... Some architectures do expose some black magic which you would need to go to assembly to access. But for the most part controlling cache involves understanding how the cache works, then controlling the memory layout and accesses to work well with the cache.
- SkiFire13 2y ago
  > I am curious: we have reference counting and we have Profile guided optimisation. > > Could "reference counting" be compiled into a debug/profiled build and then detect which regions of time we free things in before or after (there is a happens before relation with dropping out of scopes that reference counting needs to run) to detect where to insert frees? Profile guided optimizations can only gather informations about what's most probable, but they can't give knowledge about things about what will surely happen. For freeing however you most often want that knowledge, because not freeing will result in a memory leak (and freeing too early will result in a use-aftee-free, which you definitely want to avoid so the analysis needs to be conservative!). In the end this can only be an _optimization_ (just like profile guided _optimization_s are just optimizations!) on top of a workflows that is ok with leaking everything.
jll29 2y ago
Great post for intermediary programmers, who started programming in Python, and who should now learn what's under the hood to get to the next level of their education. Sometimes (perhaps most of the time), we should ignore the nitty gritty details, but the moment comes where you need to know the "how": either because you need more performance, sort out an issue, or do something that requires low-level action. There are few sources like this post targeting that intermediate group of people: you get lots of beginner YouTube clips and Web tutorials and on HN you get discussions about borrow checking in Rust versus garbage collection in Go, how to generate the best code for it and who has the best Rope implementation; but little to educate yourself from the beginner level to the level where you can begin to grasp what the second group are talking about, so thanks for this educations piece that fills a gap.
- imbnwa 2y ago
  Which is why it sucks the top comments are pedantry over what is proper C code, or other comments are about how to optimize the article's code, all missing the point that we're learning concepts that can be corrected later
  - commandlinefan 2y ago
    > pedantry over what is proper C code As soon as I clicked on the link and saw there was C code included, I knew how the comment section was going to go...
9999_points 2y ago
Memory arenas should be taught to all programmers and become the default method of memory management.
- caspper69 2y ago
  I agree with you 100%. I think arenas are a much lighter burden for the programmer to reason about than lifetimes & access patterns. But arenas can have one big drawback, and that is if you do a lot of allocations and deallocations, especially in long-running routines, you can essentially leak memory, because arenas are not usually freed until they are going out of scope. This can vary depending on the language and the implementation, though. My thought to counteract that though is you could offer a ref-counted arena just for this scenario, but I'm not sure what exactly that would look like (automatic once refs hit 0? offer a purge() function like a GC?). I haven't wrapped my head around the ergonomics yet.
- _bohm 2y ago
  They're a great fit in many situations but certainly not all. Why not teach programmers a variety of allocation strategies and how to recognize when each might be a good fit?
  - caspper69 2y ago
    I initially read your username as boehm, and I was like wow, ok, this is a guy who knows his memory. :) What situations would an arena allocator prove problematic or non-optimal, aside from the many allocations/deallocations scenario? This is an area I'm very interested in, so any info would be appreciated.
    - _bohm 2y ago
      In general, everything allocated within an arena has its lifetime tied to that arena. In lots of situations this is a fine or even desirable property (e.g., a single request context in a server application), but can be a tough restriction to work with in situations where you need fine-grained deallocations and possibly want to reuse freed space. The lifetime property can also be a pain to work with in multithreaded scenarios, where you might have multiple threads needing to access data stored in a single arena. Another situation that comes to mind is large long-lived allocations where you might want to have some manual defragmentation in place for performance reasons.
bluetomcat 2y ago
This isn't proper usage of realloc: lines = realloc(lines, (num_lines + 1) * sizeof(char *)); In case it cannot service the reallocation and returns NULL, it will overwrite "lines" with NULL, but the memory that "lines" referred to is still there and needs to be either freed or used. The proper way to call it would be: tmp = realloc(lines, (num_lines + 1) * sizeof(char *)); if (tmp == NULL) { free(lines); lines = NULL; // ... possibly exit the program (without a memory leak) } else { lines = tmp; }
- lionkor 2y ago
  Very odd that an article trying to teach memory management would miss this, this should be common knowledge to anyone who used realloc, just like checking the return of any allocation call.
  - bluetomcat 2y ago
    They treat an OOM situation as exceptional and immediately call abort() in case any allocation function returns NULL. The specification of these functions allows you to handle OOM situations gracefully.
    - josephg 2y ago
      > The specification of these functions allows you to handle OOM situations gracefully. In theory, sure. But vanishingly little software actually deals with OOM gracefully. What do you do? Almost any interaction with the user may result in more memory allocations in turn - which presumably may also fail. It’s hard to even test OOM on modern systems because of OS disk page caching. Honestly, panicking on OOM is a totally reasonable default for most modern application software. In languages like rust, this behaviour is baked in.
      - tptacek 2y ago
        I agree. The fact that Rust and Go will panic by default in this situation is pretty close to dispositive on what the right thing to do in (most) C code is.
1970-01-01 2y ago
This was a great (re)introduction to the fundamentals. Worthy of a bookmark.
sylware 2y ago
Avoid as much as you can the C standard lib allocator, go directly to mmap system call with your own allocator if you know you won't use CPU without a MMU. If you write a library, let the user code install its own allocator.
- jeffbee 2y ago
  "malloc" is a weakly-bound symbol that can be overridden, on every system I've used. I don't know if some standard defines it to be weak. Anyway the point is that malloc is not necessarily a call to the C standard library function. It can be anything.
  - sylware 2y ago
    "weakly-bound symbol" implies your a using a complex runtime library/binary format (like ELF). A portable and clean design for a library is to allow to override the internal allocator via the API (often part of the init function call). Look at vulkan3D which does many things right and doing this very part right. On the other side, you have some parts of the ALSA lib API which still requires to use the C lib free (may be obsolete though).
    - jeffbee 2y ago
      No, it doesn't mean that, because malloc can be replaced at build-time as well. But I agree that interfaces should avoid doing their own allocations and should let the caller dictate it.
      - sylware 2y ago
        Look at vulkan3D which does it right(TM).
  - kevin_thibedeau 2y ago
    The linker doesn't try to resolve symbols it's already seen while static linking. This doesn't require a weak linkage flag for overriding system library functions since libc is linked at the end by default when static linking or at runtime when dynamic.
_bohm 2y ago
This is a fantastic post. I really feel like these concepts should be introduced to programmers much earlier on in their education and this article does a great job of presenting the info in an approachable manner.
numeromancer 2y ago
Just no. address = X length = *X address = address + 1 while length > 0 { address = address + 1 print *address }
- deleted 2y ago
  [deleted]
- ekr____ 2y ago
  Author here. You're quite right that this isn't the thing you would normally do. I'm just trying to help people work through the logic of the system with as few dependencies as possible, hence this (admittedly yucky) piece of pseudocode which isn't really C or Rust or Python or anything...
  - helothereycomb 2y ago
    At least update "length" for the for loop since it would go into an infinite loop the way it is now in any of those languages.
juanbafora 2y ago
thanks for sharing these are core concept to better understand the coding
deleted 2y ago
[deleted]
aslihana 2y ago
The comics at the beginning hahaha :D
the_arun 2y ago
> If we just concatenate the values in memory, how do we know where one line ends and the next begins? For instance, maybe the first two names are "jim" and "bob" or maybe it's one person named "jimbob", or even two people named "jimbo" and "b". Don't we have a newline character? I thought we can read newline as `0xA` in Rust?
writebetterc 2y ago
This post caused me to create an account. This C code is not good. Writing C is absolutely harder than Python, but you're making it so much harder than it has to be. Your program is buggy as heck, has very finicky cleanup code, and so on. Here's a much easier way to write the program: 1. Dump whole file into buffer as one string 2. Find newlines in buffer, replace with NULs. This also let's you find each line and save them in another buffer 3. Sort the buffer of all the lines you found 4. qsort the buffer 5. Print everything 6. Free both buffers Or, as a C program: https://godbolt.org/z/38nq1MorM https://godbolt.org/z/38nq1MorM
- commandlinefan 2y ago
  > Dump whole file into buffer as one string ... unless the file is too big to fit into memory?
  - writebetterc 2y ago
    Memory will always be the limiting factor here. A strong adversary can ensure that you must know the whole list in order to sort it. You can always mmap the file instead and let the OS page in and out parts of the file, however :-).
AdieuToLogic 2y ago
The example strdup implementation: char *strdup(const char *str) { size_t len = strlen(str); char *retval = malloc(len); if (!retval) { return NULL; } strcpy(retval, str); return retval; } Has a very common defect. The malloc call does not reserve enough space for the NUL byte required for successful use of strcpy, thus introducing heap corruption. Also, assuming a NULL pointer is bitwise equal to 0 is not portable.
- msarnoff 2y ago
  re: the bitwise representation of NULL, evaluating a pointer in a Boolean context has the intended behavior regardless of the internal representation of a null pointer. See the C FAQ questions 5-3 and 5-10, et al. https://c-faq.com/null/ https://c-faq.com/null/
- ekr____ 2y ago
  Aargh. You're totally right about the off by one error. Thanks for catching it. I don't believe you're right about the comparison to zero, however, as the comment below indicates.
erlkonig 2y ago
Using abort() every time malloc and kin fail isn't really satisfying anything except the idea that the program should crash before showing incorrect results. While the document itself is pretty good otherwise, this philosophical failing is a problem. It should give examples of COPING with memory exhaustion, instead of just imploding every time. It should also mention using "ulimit -Sd 6000" or something to lower the limit to force the problems to happen (that one happens to work well with vi). Memory management is mature when programs that should stay running - notably user programs, system daemons, things where simply restarting will lose precious user data or other important internal data - HANDLE exhaustion, clean up any partially allocated objects, then either inform the user or keep writing data out to files (or something) and freeing memory until allocation starts working again. E.g. Vi informs the user without crashing, like it should. This general philosophy is one that I've seen degrade enormously over recent years, and a trend we should actively fight against. And this trend has been greatly exacerbated by memory overcommit.
- returningfory2 2y ago
  It's a beginners article about memory management. I think it's weird that so many comments here are judging the code snippets as if they're commits to production systems. When writing articles like these there are pedagogical decisions to be made, such as simplifying the examples to make them easier to understand.
eddieh 2y ago
Too bad the first program in the article leaks its file descriptor. Memory is but one resource you need to manage. File descriptors are the first oft overlooked resource in a long list of neglected finite resources.
honzaik 2y ago
i am no C programmer, but doesnt the first pseudocode make no sense (and others after since they reuse it)? address = X length = *X address = address + 1 while length > 0 { address = address + 1 print *address } 1) length is never updated so while is infinite loop (if length is not 0) 2) the first character is never output since at address 0 (assuming X=0 at the start) is the value length but then the pointer is incremented twice so the first print *address prints the character at address 2? if I am mistaken I'd be happy if someone explained why it makes sense

237 points by ekr____ 2y ago

Thanks for such a detailed article. In my spare time working with C as a hobby I am usually in "vertical mode" which is different to how I would work (carefully) at work, which is just getting things done end-to-end as fast as possible, not careful at every step that we have no memory errors. So I am just trying to get something working end-to-end so I do not actually worry about memory management when writing C. So I let the operating system handle memory freeing. I am trying to get the algorithm working in my hobby time. And since I wrote everything in Python or Javascript initially, I am usually porting from Python to C. If I were using Rust, it would force me to be careful in the same way, due to the borrow checker. I am curious: we have reference counting and we have Profile guided optimisation. Could "reference counting" be compiled into a debug/profiled build and then detect which regions of time we free things in before or after (there is a happens before relation with dropping out of scopes that reference counting needs to run) to detect where to insert frees? (We Write timing metadata from the RC build, that encapsulates the happens before relationships) Then we could recompile with a happens-before relation file that has correlations where things should be freed to be safe. EDIT: Any discussion about those stack diagrams and alignment should include a link to this wikipedia page; https://en.wikipedia.org/wiki/Data_structure_alignment https://en.wikipedia.org/wiki/Data_structure_alignment

jvanderbot 2y ago
> which is just getting things done end-to-end as fast as possible, not careful at every step that we have no memory errors. One horrible but fun thing a former professor of mine pointed out: If your program isn't going to live long, then you never have to deallocate memory. Once it exits, the OS will happily clean it up for you. This works in C or perhaps lazy GC languages, but for stateful objects where destructors do meaningful work, like in C++, this is dangerous. This is one of the reasons I hate C++ so much: Unintended side effects that you have to trigger. > Could "reference counting" be compiled into a debug/profiled build and then detect which regions of time we free things in before or after (there is a happens before relation with dropping out of scopes that reference counting needs to run) to detect where to insert frees? This is what Rust does, kinda. C++ also does this with "stack" allocated objects - it "frees" (calls destructor and cleans up) when they go out of scope. And in C++, heap allocated data (if you're using a smart pointer) will automatically deallocate when the last reference drops, but this is not done at compile time. Those are the only two memory management models I'm familiar with enough to comment on.
- MarkSweep 2y ago
  There is this old chestnut about “null garbage collectors”: https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98125 https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98... > This sparked an interesting memory for me. I was once working with a customer who was producing on-board software for a missile. In my analysis of the code, I pointed out that they had a number of problems with storage leaks. Imagine my surprise when the customers chief software engineer said "Of course it leaks". He went on to point out that they had calculated the amount of memory the application would leak in the total possible flight time for the missile and then doubled that number. They added this much additional memory to the hardware to "support" the leaks. Since the missile will explode when it hits its target or at the end of its flight, the ultimate in garbage collection is performed without programmer intervention.
  - jvanderbot 2y ago
    Rapid disassembly as GC. Love it. Have you heard the related story about the patriot missile system? https://www.cs.unc.edu/~smp/COMP205/LECTURES/ERROR/lec23/node4.html https://www.cs.unc.edu/~smp/COMP205/LECTURES/ERROR/lec23/nod... Not a GC issue, but fun software bug.
  - gpderetta 2y ago
    Untill the software is reused for a newer model with longer range and they forget to increase the ram size. But of course that would never happen, wouldn't it?
- pjmlp 2y ago
  The wonders of corrupted data, stale advisory locks and UNIX IPC leftovers, because they weren't properly flushed, or closed before process termination.
  - jvanderbot 2y ago
    I'll narrow my scope more explicitly: close(x) is not memory management - not at the user level. This should be done. free(p) has no O/S side effects like this in C - this can be not-done if you don't malloc all your memory. You can get away with not de-allocating program memory, but (as mentioned), that has nothing to do with freeing Os/ kernel / networking resources in C.
caspper69 2y ago
Nothing is going to tell you where to put your free() calls to guarantee memory safety (otherwise Rust wouldn't exist). There are tools that will tell you they're missing, however. Read up on Valgrind and ASAN. In C, non-global variables go out of scope when the function they are created in ends. So if you malloc() in a fn, free() at the end. If you're doing everything with globals in a short-running program, let the OS do it if that suits you (makes me feel dirty). This whole problem doesn't get crazy until your program gets more complicated. Once you have a lot of pointers among objects with different lifetimes. or you decide to add some concurrency (or parallelism), or when you have a lot of cooks in the kitchen. In the applications you say you are writing, just ask yourself if you're going to use a variable again. If not, and it is using dynamically-allocated memory, free() it. Don't psych yourself out, it's just C. And yes, there are ref-counting libraries for C. But I wouldn't want to write my program twice, once to use the ref-counting library in debug mode and another to use malloc/free in release mode. That sounds exhausting for all but the most trivial programs.
mgaunard 2y ago
In C, not all objects need to be their own allocated entity (like they are in other languages). They can be stored in-line within another object, which means the lifetime of that object is necessarily constrained by that of its parent. You could make every object its own allocated entity, but then you're losing most of the benefits of using C, which is the ability to control memory layout of objects.
- pjmlp 2y ago
  As any systems programming language include those that predate C by a decade, and still it doesn't allow full control without compiler extensions, if you really want full control of memory layout of objects, Assembly is the only way.
  - gizmo686 2y ago
    In practice C let's you control memory layout just fine. You might need to use __attribute__((packed)), which is technically non standard. I've written hardware device drivers in pure C where you need need to peek and poke at specific bits on the memory bus. I defined a struct that matched the exact memory layout that the hardware specifies. Then cast an integer to a pointer to that struct type. At which point I could interact with the hardware by directly reading/writing fields if the struct (most of which were not even byte aligned). It is not quite that simple, as you also have to deal with bypassing the cache, memory barriers, possibly virtual memory, finding the erreta that clarifies the originaly published register address was completely wrong. But I don't think any of that is what people mean when they say "memory layout".
    - pjmlp 2y ago
      Now split the struct across registers in C. You are aware that some of those casting tricks are UB, right?
      - gizmo686 2y ago
        Casting integers to pointers in C is implementation defined, not UB. In practice compilers define these casts as the natural thing for the architecture you are compiling to. Since mainstream CPUs don't do anything fancy with pointer tagging, that means the implementation defined behave does exactly what you expect it to do (unless you forget that you have paging enabled and cannot simply point to a hardware memory address). If you want to control register layout, then C is not going to help you, but that is not typically what is meant by "memory layout". And if you want to control cache usage ... Some architectures do expose some black magic which you would need to go to assembly to access. But for the most part controlling cache involves understanding how the cache works, then controlling the memory layout and accesses to work well with the cache.
SkiFire13 2y ago
> I am curious: we have reference counting and we have Profile guided optimisation. > > Could "reference counting" be compiled into a debug/profiled build and then detect which regions of time we free things in before or after (there is a happens before relation with dropping out of scopes that reference counting needs to run) to detect where to insert frees? Profile guided optimizations can only gather informations about what's most probable, but they can't give knowledge about things about what will surely happen. For freeing however you most often want that knowledge, because not freeing will result in a memory leak (and freeing too early will result in a use-aftee-free, which you definitely want to avoid so the analysis needs to be conservative!). In the end this can only be an _optimization_ (just like profile guided _optimization_s are just optimizations!) on top of a workflows that is ok with leaking everything.

jll29 2y ago

Great post for intermediary programmers, who started programming in Python, and who should now learn what's under the hood to get to the next level of their education. Sometimes (perhaps most of the time), we should ignore the nitty gritty details, but the moment comes where you need to know the "how": either because you need more performance, sort out an issue, or do something that requires low-level action. There are few sources like this post targeting that intermediate group of people: you get lots of beginner YouTube clips and Web tutorials and on HN you get discussions about borrow checking in Rust versus garbage collection in Go, how to generate the best code for it and who has the best Rope implementation; but little to educate yourself from the beginner level to the level where you can begin to grasp what the second group are talking about, so thanks for this educations piece that fills a gap.

imbnwa 2y ago
Which is why it sucks the top comments are pedantry over what is proper C code, or other comments are about how to optimize the article's code, all missing the point that we're learning concepts that can be corrected later
- commandlinefan 2y ago
  > pedantry over what is proper C code As soon as I clicked on the link and saw there was C code included, I knew how the comment section was going to go...

9999_points 2y ago

Memory arenas should be taught to all programmers and become the default method of memory management.

caspper69 2y ago
I agree with you 100%. I think arenas are a much lighter burden for the programmer to reason about than lifetimes & access patterns. But arenas can have one big drawback, and that is if you do a lot of allocations and deallocations, especially in long-running routines, you can essentially leak memory, because arenas are not usually freed until they are going out of scope. This can vary depending on the language and the implementation, though. My thought to counteract that though is you could offer a ref-counted arena just for this scenario, but I'm not sure what exactly that would look like (automatic once refs hit 0? offer a purge() function like a GC?). I haven't wrapped my head around the ergonomics yet.
_bohm 2y ago
They're a great fit in many situations but certainly not all. Why not teach programmers a variety of allocation strategies and how to recognize when each might be a good fit?
- caspper69 2y ago
  I initially read your username as boehm, and I was like wow, ok, this is a guy who knows his memory. :) What situations would an arena allocator prove problematic or non-optimal, aside from the many allocations/deallocations scenario? This is an area I'm very interested in, so any info would be appreciated.
  - _bohm 2y ago
    In general, everything allocated within an arena has its lifetime tied to that arena. In lots of situations this is a fine or even desirable property (e.g., a single request context in a server application), but can be a tough restriction to work with in situations where you need fine-grained deallocations and possibly want to reuse freed space. The lifetime property can also be a pain to work with in multithreaded scenarios, where you might have multiple threads needing to access data stored in a single arena. Another situation that comes to mind is large long-lived allocations where you might want to have some manual defragmentation in place for performance reasons.

bluetomcat 2y ago

This isn't proper usage of realloc: lines = realloc(lines, (num_lines + 1) * sizeof(char *)); In case it cannot service the reallocation and returns NULL, it will overwrite "lines" with NULL, but the memory that "lines" referred to is still there and needs to be either freed or used. The proper way to call it would be: tmp = realloc(lines, (num_lines + 1) * sizeof(char *)); if (tmp == NULL) { free(lines); lines = NULL; // ... possibly exit the program (without a memory leak) } else { lines = tmp; }

lionkor 2y ago
Very odd that an article trying to teach memory management would miss this, this should be common knowledge to anyone who used realloc, just like checking the return of any allocation call.
- bluetomcat 2y ago
  They treat an OOM situation as exceptional and immediately call abort() in case any allocation function returns NULL. The specification of these functions allows you to handle OOM situations gracefully.
  - josephg 2y ago
    > The specification of these functions allows you to handle OOM situations gracefully. In theory, sure. But vanishingly little software actually deals with OOM gracefully. What do you do? Almost any interaction with the user may result in more memory allocations in turn - which presumably may also fail. It’s hard to even test OOM on modern systems because of OS disk page caching. Honestly, panicking on OOM is a totally reasonable default for most modern application software. In languages like rust, this behaviour is baked in.
    - tptacek 2y ago
      I agree. The fact that Rust and Go will panic by default in this situation is pretty close to dispositive on what the right thing to do in (most) C code is.

1970-01-01 2y ago

This was a great (re)introduction to the fundamentals. Worthy of a bookmark.

sylware 2y ago

Avoid as much as you can the C standard lib allocator, go directly to mmap system call with your own allocator if you know you won't use CPU without a MMU. If you write a library, let the user code install its own allocator.

jeffbee 2y ago
"malloc" is a weakly-bound symbol that can be overridden, on every system I've used. I don't know if some standard defines it to be weak. Anyway the point is that malloc is not necessarily a call to the C standard library function. It can be anything.
- sylware 2y ago
  "weakly-bound symbol" implies your a using a complex runtime library/binary format (like ELF). A portable and clean design for a library is to allow to override the internal allocator via the API (often part of the init function call). Look at vulkan3D which does many things right and doing this very part right. On the other side, you have some parts of the ALSA lib API which still requires to use the C lib free (may be obsolete though).
  - jeffbee 2y ago
    No, it doesn't mean that, because malloc can be replaced at build-time as well. But I agree that interfaces should avoid doing their own allocations and should let the caller dictate it.
    - sylware 2y ago
      Look at vulkan3D which does it right(TM).
- kevin_thibedeau 2y ago
  The linker doesn't try to resolve symbols it's already seen while static linking. This doesn't require a weak linkage flag for overriding system library functions since libc is linked at the end by default when static linking or at runtime when dynamic.

_bohm 2y ago

This is a fantastic post. I really feel like these concepts should be introduced to programmers much earlier on in their education and this article does a great job of presenting the info in an approachable manner.

numeromancer 2y ago

Just no. address = X length = *X address = address + 1 while length > 0 { address = address + 1 print *address }

deleted 2y ago
[deleted]
ekr____ 2y ago
Author here. You're quite right that this isn't the thing you would normally do. I'm just trying to help people work through the logic of the system with as few dependencies as possible, hence this (admittedly yucky) piece of pseudocode which isn't really C or Rust or Python or anything...
- helothereycomb 2y ago
  At least update "length" for the for loop since it would go into an infinite loop the way it is now in any of those languages.

juanbafora 2y ago

thanks for sharing these are core concept to better understand the coding

deleted 2y ago

[deleted]

aslihana 2y ago

The comics at the beginning hahaha :D

the_arun 2y ago

> If we just concatenate the values in memory, how do we know where one line ends and the next begins? For instance, maybe the first two names are "jim" and "bob" or maybe it's one person named "jimbob", or even two people named "jimbo" and "b". Don't we have a newline character? I thought we can read newline as `0xA` in Rust?

writebetterc 2y ago

This post caused me to create an account. This C code is not good. Writing C is absolutely harder than Python, but you're making it so much harder than it has to be. Your program is buggy as heck, has very finicky cleanup code, and so on. Here's a much easier way to write the program: 1. Dump whole file into buffer as one string 2. Find newlines in buffer, replace with NULs. This also let's you find each line and save them in another buffer 3. Sort the buffer of all the lines you found 4. qsort the buffer 5. Print everything 6. Free both buffers Or, as a C program: https://godbolt.org/z/38nq1MorM https://godbolt.org/z/38nq1MorM

commandlinefan 2y ago
> Dump whole file into buffer as one string ... unless the file is too big to fit into memory?
- writebetterc 2y ago
  Memory will always be the limiting factor here. A strong adversary can ensure that you must know the whole list in order to sort it. You can always mmap the file instead and let the OS page in and out parts of the file, however :-).

AdieuToLogic 2y ago

The example strdup implementation: char *strdup(const char *str) { size_t len = strlen(str); char *retval = malloc(len); if (!retval) { return NULL; } strcpy(retval, str); return retval; } Has a very common defect. The malloc call does not reserve enough space for the NUL byte required for successful use of strcpy, thus introducing heap corruption. Also, assuming a NULL pointer is bitwise equal to 0 is not portable.

msarnoff 2y ago
re: the bitwise representation of NULL, evaluating a pointer in a Boolean context has the intended behavior regardless of the internal representation of a null pointer. See the C FAQ questions 5-3 and 5-10, et al. https://c-faq.com/null/ https://c-faq.com/null/
ekr____ 2y ago
Aargh. You're totally right about the off by one error. Thanks for catching it. I don't believe you're right about the comparison to zero, however, as the comment below indicates.

erlkonig 2y ago

Using abort() every time malloc and kin fail isn't really satisfying anything except the idea that the program should crash before showing incorrect results. While the document itself is pretty good otherwise, this philosophical failing is a problem. It should give examples of COPING with memory exhaustion, instead of just imploding every time. It should also mention using "ulimit -Sd 6000" or something to lower the limit to force the problems to happen (that one happens to work well with vi). Memory management is mature when programs that should stay running - notably user programs, system daemons, things where simply restarting will lose precious user data or other important internal data - HANDLE exhaustion, clean up any partially allocated objects, then either inform the user or keep writing data out to files (or something) and freeing memory until allocation starts working again. E.g. Vi informs the user without crashing, like it should. This general philosophy is one that I've seen degrade enormously over recent years, and a trend we should actively fight against. And this trend has been greatly exacerbated by memory overcommit.

returningfory2 2y ago
It's a beginners article about memory management. I think it's weird that so many comments here are judging the code snippets as if they're commits to production systems. When writing articles like these there are pedagogical decisions to be made, such as simplifying the examples to make them easier to understand.

eddieh 2y ago

Too bad the first program in the article leaks its file descriptor. Memory is but one resource you need to manage. File descriptors are the first oft overlooked resource in a long list of neglected finite resources.

honzaik 2y ago

i am no C programmer, but doesnt the first pseudocode make no sense (and others after since they reuse it)? address = X length = *X address = address + 1 while length > 0 { address = address + 1 print *address } 1) length is never updated so while is infinite loop (if length is not 0) 2) the first character is never output since at address 0 (assuming X=0 at the start) is the value length but then the pointer is incremented twice so the first print *address prints the character at address 2? if I am mistaken I'd be happy if someone explained why it makes sense