My advice on implementing stuff in C: [LWN.net]

My advice on implementing stuff in C:

Posted Oct 23, 2010 1:14 UTC (Sat) by wahern (subscriber, #37304)
In reply to: My advice on implementing stuff in C: by nix
Parent article: Russell: On C Library Implementation

glib or glibc? Those are completely different libraries. If glibc is aborting on allocation error than it's non-conforming and it should be reported as a bug. There's a reason C and POSIX define ENOMEM.

As for the stack, the solution there is easy, don't recurse. Any recursive algorithm can be re-written as an iterative algorithm. Of course, if you use a language that optimizes tail-calls then you're already set. C doesn't, and therefore writing recursive algorithms is a bad idea, and it's why it's quite uncommon in C code.

As for testing error paths: if somebody isn't testing error paths than they're not testing error paths. What difference does it matter whether they're not testing malloc failure or they're not testing invalid input? It's poor design; it creates buggy code. And if you use good design habits, like RAII (not just a C++ pattern), then the places for malloc failure to occur are well isolated. It's not a very good argument to point out that most engineers write crappy code. We all know this; we all do it ourselves; but it's ridiculous to make excuses for it. If you can't handle the responsibility, then don't write applications in C or for its typical domain. If I'm writing non-critical or throw-away code, I'll use Perl or something else. Why invest the effort in using a language with features--explicit memory management--that I'm not going to use?

Using a per-process context design is in many circumstances a solid choice (not for me because I write HP embedded network server software, though I do prefer processes instead of threads for concurrency, so I might have 2 processes per cpu each handling hundreds of connections). But here's another problem w/ default Linux--because of overcommit, it's not always--perhaps not even often--that the offending process gets killed; it's the next guy paging in a small amount of memory that gets killed. It's retarded. It's a security problem. Can you imagine your SSH session getting OOMd because someone was fuzzing your website? It happens.

Why make excuses for poor design?

to post comments

My advice on implementing stuff in C:

Posted Oct 23, 2010 3:18 UTC (Sat) by foom (subscriber, #14868) [Link]

> it's not always--perhaps not even often--that the offending process gets killed; it's the next guy paging in a small amount of memory that gets killed.

Actually, the OOM-killer tries *very* hard to not simply kill the next guy paging in a small amount of memory, but to determine what the real problem process is and kill that instead. It doesn't always find the correct culprit, but it often does, and at least it tends not to kill your ssh session.

My advice on implementing stuff in C:

Posted Oct 23, 2010 18:29 UTC (Sat) by paulj (subscriber, #341) [Link] (6 responses)

Why make excuses for poor design?

Nix isn't making excuses, he's pointing out reality. Which, sadly, is always far from perfect. A programme which is designed to cope with failure *despite* the suckiness of reality should do better than one that depends on perfection underneath it...

My advice on implementing stuff in C:

Posted Oct 23, 2010 19:39 UTC (Sat) by wahern (subscriber, #37304) [Link]

Robustness, like security, should be applied in-depth. Of course I use monitor processes and dead man switches to restart processes. But I don't rely on one to the exclusion of another.

My advice on implementing stuff in C:

Posted Oct 24, 2010 15:17 UTC (Sun) by nix (subscriber, #2304) [Link] (4 responses)

Indeed. It is simply reality that nobody ever tests malloc() failure paths -- at least, they do not and cannot test every combination of malloc-fails-and-then-it-doesn't, because there is an exponential explosion of them. People do not armour most programs, even important ones, to survive malloc() failure, because it would make the code unreadable and because available memory continues to shoot upwards so most people prefer to assume that reasonably sized allocations will not fail unless something is seriously wrong with the machine. And, guess what? They're right nearly all the time.

The suggestion to avoid stack-OOM by converting recursive algorithms to iterative ones is just another example of this, because while deep recursion is more likely to stack-OOM than the function calls involved in an iterative algorithm, the latter will still happen now and then. The only way to avoid *that* is to do a deep recursion first, and then ensure that you never call functions further down in the call stack than you have already allocated, neither in your code nor in any library you may call. I know of no tools to make this painful maintenance burden less painful. So nobody at all armours against this case, either.

I think it *is* important to trap malloc() failure so that you can *log which malloc() failed* before you die (and that means your logging functions *do* have to be malloc()-failure-proof: I normally do this by having them take their allocations out of a separate, pre-mmap()ed emergency pool). Obviously this doesn't work if you are stack-OOMed, nor if the OOM-killer zaps you. Note that this *is* an argument against memory overcommit: that overcommit makes it harder to detect which of many allocations in a program is buggy and running away allocating unlimited storage. But 'we want to recover from malloc() failure' is not a good reason to not use overcommmitment, because very few programs even try, and of those that try, most are surely lethally buggy in this area in any case: and fixing this is completely impractical.

Regarding my examples above: glib always aborts on malloc() failure, so so do all programs that use it. glibc does not, but its attempts to handle malloc() failure are buggy and leaky at best, and of course it (like everything else) remains vulnerable to stack- or CoW-OOM.

My advice on implementing stuff in C:

Posted Oct 25, 2010 10:05 UTC (Mon) by hppnq (guest, #14462) [Link] (3 responses)

The only way to avoid *that* [stack-OOM] is to do a deep recursion first, and then ensure that you never call functions further down in the call stack than you have already allocated, neither in your code nor in any library you may call.

You would have to know in advance how deep you can recurse, or you should be able to handle SIGSEGV. The maximum stack size can be tuned through rlimits, and that should solve wahern's problem of some other process draining out all available memory. This problem is not the result of bad programming, but of bad systems management.

(That said, rlimits are horribly broken. Just add more memory. ;-)

My advice on implementing stuff in C:

Posted Oct 25, 2010 22:28 UTC (Mon) by paulj (subscriber, #341) [Link] (2 responses)

FWIW, it's not defined what happens if you overflow the stack. You can't rely on getting a SEGV (isn't that a very recent addition to Linux, thanks to that Xorg security hole)?

My advice on implementing stuff in C:

Posted Oct 25, 2010 22:36 UTC (Mon) by nix (subscriber, #2304) [Link] (1 responses)

Even if you do get SIGSEGV from a stack-OOM, well, you'd better hope the system supports sigaltstack() as well, or you'll not be able to call the signal handler... oh, and, btw, it is (even now) easier to make a list of the systems on which sigaltstack() works properly than the systems on which it does not :(

My advice on implementing stuff in C:

Posted Oct 26, 2010 7:55 UTC (Tue) by hppnq (guest, #14462) [Link]

The point is, you can't safely expand the stack by recursing deeply in order to prevent running out of stack.

My advice on implementing stuff in C:

Posted Oct 25, 2010 11:04 UTC (Mon) by mjthayer (guest, #39183) [Link] (4 responses)

> As for the stack, the solution there is easy, don't recurse.

Just out of interest, are there really no simple ways (as nix suggested) to allocate a fixed-size stack at programme begin in Linux userland? I can't see any theoretical reasons why it should be a problem.

> And if you use good design habits, like RAII (not just a C++ pattern), then the places for malloc failure to occur are well isolated.

Again, I am interested in how you do RAII in C. I know the (in my opinion ugly and error-prone) goto way, and I could think of ways to do at run time what C++ does at compile time (doesn't have to be a bad thing, although more manual steps would be needed). Do you have any other insights?

My advice on implementing stuff in C:

Posted Oct 25, 2010 11:52 UTC (Mon) by hppnq (guest, #14462) [Link]

Just out of interest, are there really no simple ways (as nix suggested) to allocate a fixed-size stack at programme begin in Linux userland?

ld --stack or something similar?

My advice on implementing stuff in C:

Posted Oct 25, 2010 22:41 UTC (Mon) by nix (subscriber, #2304) [Link] (2 responses)

You do RAII in C by wrapping everything up in opaque structures allocated by dedicated allocators and freed either by dedicated freers or by APR-style pool destructors. If you're using mempools, you can even get close to the automagic destructor calls of C++ (you still have to free a mempool, but if you free the pool the free cascades down all contained pools and all their destructors.)

My advice on implementing stuff in C:

Posted Oct 26, 2010 8:06 UTC (Tue) by mjthayer (guest, #39183) [Link] (1 responses)

> You do RAII in C by wrapping everything up in opaque structures allocated by dedicated allocators and freed either by dedicated freers or by APR-style pool destructors.

Right, roughly what I was thinking of. Thanks for the concrete pointers!

My advice on implementing stuff in C:

Posted Oct 26, 2010 8:18 UTC (Tue) by mjthayer (guest, #39183) [Link]

> Right, roughly what I was thinking of.

Except of course that there is no overriding need to use memory pools. You can also keep track of multiple allocations (possibly also with destructors) in some structure and free them all at one go when you are done. Freeing many allocations in one go rather than freeing each as soon as it is no longer needed might also be more efficient cache-wise.