This isn't proper usage of realloc:
lines = realloc(lines, (num_lines + 1) * sizeof(char *));
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;
}I feel like this comment is misleading because it gives the impression that the code in the article is wrong or unsafe, whereas I think it's actually fine? In the article, in the case when `tmp == NULL` (in your notation) the author aborts the program. This means there's no memory leak or unsafety. I agree that one can do better of course.
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.
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.
There's another bug, related to performance - this involves a quadratic amount of memory copying unless your environment can arrange for zero-copy.
It is even flagged as such on Visual Studio analyser.
Actually, no. You've just committed one of the cardinal sins of the *alloc()'s, which is: NULL is an acceptable return, so errno != 0 is the only way to tell if things have gone awry.
The proper use of realloc is to check errno always ... because in fact it can return NULL in a case which is not considered an error: lines is not NULL but requested size is zero. This is not considered an error case.
So, in your fix, please replace all checking of tmp == NULL, instead with checking errno != 0. Only then will you have actually fixed the OP's unsafe, incorrect code.
From `malloc(3)`:
Nonportable behavior
The behavior of these functions when the requested size is zero is glibc specific; other implementations may return NULL without setting errno, and portable POSIX programs should tolerate such behavior. See realloc(3p).
POSIX requires memory allocators to set errno upon failure. However, the C standard does not require this, and applications portable to non-POSIX platforms should not assume this.As someone writing C for POSIX and embedded environments, this clarification is a super helpful.
In this case if (num_lines+1)(sizeof (char)) is zero that is certainly unintended
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;
> 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.
> 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.
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.
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.
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.
Memory arenas should be taught to all programmers and become the default method of memory management.
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.
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?
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.
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.
This was a great (re)introduction to the fundamentals. Worthy of a bookmark.
Just no.
address = X
length = *X
address = address + 1
while length > 0 {
address = address + 1
print *address
}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.
thanks for sharing these are core concept to better understand the coding
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.
"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.
"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).
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.