LWN: Comments on "Zeuthen: Writing a C library, part 1"

Zeuthen: Writing a C library, part 1

kabloom — Fri, 08 Jul 2011 01:41:19 +0000

Yes. ulimit is one way to get allocation errors even with overcommit enabled.

Zeuthen: Writing a C library, part 1

kabloom — Fri, 08 Jul 2011 01:40:05 +0000

Does Windows overcommit? Windows programs don't fork the way Linux programs do, so I would guess that overcommitting memory is much less of a problem on Windows.

Zeuthen: Writing a C library, part 1

jwakely — Thu, 07 Jul 2011 12:08:36 +0000

> In general, you can't return both results *and* error codes.

std::future<double> squerrt(double x)
{
  std::promise<double> p;
  if (x < 0)
    p.set_exception(copy_exception(std::domain_error("negative")));
  else
    p.set_value(sqrt(x));
  return p.get_future();
}

int main()
{
  double i = squerrt(-1).get();  // boom
}

Zeuthen: Writing a C library, part 1

cmccabe — Thu, 07 Jul 2011 00:22:36 +0000

> In general, you can't return both results *and* error codes. (As I said,
> for pointers you can return NULL, and for functions whose domain of valid
> results is limited in some sense [abs()], you can, but if you're returning
> anything other than a pointer, int-type or floating-point-type, you're
> basically hosed.
>

If we're still talking about C/C++, then you can only ever return:
* a primitive (int, float, etc.)
* a pointer
* a struct

All of those have a natural 'none of the above' value. Integer types have 0 or a negative, floats and doubles have NaN, and pointers have NULL.

If you're returning a struct by value, then you're probably using C++, since C programmers rarely return an entire structure by value. The obvious thing to do is to either return an integer error code and take a reference to the thing to be modified, or use C++ exceptions. Either way, problem solved.

Being able to return multiple values at once is nice, but it's hardly the biggest challenge when using C or C++.

Zeuthen: Writing a C library, part 1

vlovich — Wed, 06 Jul 2011 16:56:11 +0000

Same here. I mean it's been a while since I took data structures. Maybe things have changed ;).

Zeuthen: Writing a C library, part 1

jwakely — Wed, 06 Jul 2011 16:01:44 +0000

http://www.cprogramming.com/tutorial/lesson18.html

Zeuthen: Writing a C library, part 1

jwakely — Wed, 06 Jul 2011 15:56:53 +0000

I'm glad someone sensible agrees with the point I made way back in http://lwn.net/Articles/449645/ ... I was starting to think I was going mad and everyone else knew something about RB trees that I didn't

Zeuthen: Writing a C library, part 2

jwakely — Wed, 06 Jul 2011 15:54:16 +0000

> In other words, this is a gcc-specific ELF extension.

It's not gcc-specific, it's done by GNU binutils not gcc

http://sourceware.org/binutils/docs-2.21/as/Symver.html
http://sourceware.org/binutils/docs-2.21/ld/VERSION.html

Zeuthen: Writing a C library, part 1

dgm — Mon, 04 Jul 2011 00:11:56 +0000

I'm afraid your simple example got much more flak that it deserved. People, it was only an example! The truth is, if I had a dime for every time I have seen something like what you pointed out, I would be rich by now.

The problem with encapsulation (and information hiding in general) is that sometimes you _need_ to take the implementation into account. It doesn't mean that it's not a great engineering principle, it is. It's just that it sometimes makes things complicated. In this case, before you can use something in a destructor you have to be pretty sure that the implementation will not throw an exception. That's not only difficult to do, it's subject to constant change in current development paradigms.

> I get annoyed when people talk about exceptions as a panacea for error handling problems.

Me too. No amount of exceptions, garbage collectors or type inference can replace your brain. They are there you help you with the grunt work, but it doesn't mean you can forget how to properly engineer stuff, because from time to time, you need to.

> It's simple enough to avoid new and free, but once you start needing to implement transactional behavior-- either a function call succeeds or it fails, but it doesn't leave a mess-- things get difficult.

So true. I have come to the conclusion that error handling is maybe 30-50% of the effort needed to get properly done code. And regretfully is often a neglected part. For instance, what you call transactional behavior is called "class invariants" in OO programming. It's critical to well behaved long living programs, but many people haven't head about them (for those: no action should let an object in an inconsistent state).

Zeuthen: Writing a C library, part 1

nix — Sun, 03 Jul 2011 23:40:31 +0000

And then we can write a nice high-performance FUSE filesystem on top of the relational database! And then we can run MySQL on top of that! (And then we can run the FUSE filesystem atop that, and run a virtual machine inside that filesystem. And then we have a nice room heater.)

Zeuthen: Writing a C library, part 1

dgm — Sun, 03 Jul 2011 23:09:00 +0000

We can probably shortcircuit the flamewar by using a relational database. Oh, noes! PostgreSQL vs. MySQL anyone? ;-)

Zeuthen: Writing a C library, part 1

nix — Sun, 03 Jul 2011 22:04:53 +0000

I think we are in violent agreement.

Zeuthen: Writing a C library, part 1

dark — Sun, 03 Jul 2011 20:48:54 +0000

What you gain is a destructor that works in O(n) time and does no allocations. By reusing the child pointers as a linked list, you avoid having to make any allocations for it.

I think your approach can get there too, with some refinement. How are you implementing the inorder visit?

Zeuthen: Writing a C library, part 1

vlovich — Sun, 03 Jul 2011 19:39:19 +0000

Rebalancing the tree would be enormously redundant - the extra 4-6 lines of really simple code is worth it (hell, if you're lazy, provide a boolean to the internal delete function that says whether or not to rebalance).

Thread-safety is irrelevant here - if you can access the tree after the destructor is already called, you've failed at thread safety (actually you've failed at maintaining the lifetime of the object properly).

Zeuthen: Writing a C library, part 1

nix — Sun, 03 Jul 2011 18:35:37 +0000

When you're writing a tree deallocator, I'd expect it to have privileged access to the interior of the tree. There's no reason not to use a specialized high-speed node deletor in that case: rebalancing the tree between every deletion is silly, because it will never be accessed again. (Even a multithread-safe tree should probably block and warn on accesses once tree deallocation begins: any such accesses are racy and could easily access rubbish if they happened just an instant later.)

Zeuthen: Writing a C library, part 2

paulj — Sun, 03 Jul 2011 17:07:17 +0000

Symbol map files are supported by several proprietary Unix toolchains, including Suns' and (iirc) HPs'. The syntax is nearly identical twixt Solaris and GNU (there's certainly a useful common subset iirc). The ELF symbol stuff is at least very very similar in concept. It might even be standardised, and/or tools may know the differing formats. Binary compatibility across different OSes tends not to be the most important of issues though..

Zeuthen: Writing a C library, part 1

cladisch — Sun, 03 Jul 2011 11:35:22 +0000

If a generic deletion function is used, it might rebalance the tree after each step.

Zeuthen: Writing a C library, part 2

nix — Sun, 03 Jul 2011 09:39:48 +0000

Yes, its a Linuxism (and very much more useful than Solaris symbol versions), but a lot of the syntax of the file, and the underlying idea, was a Solarisism first.

Zeuthen: Writing a C library, part 1

vlovich — Sun, 03 Jul 2011 08:14:37 +0000

I'm not understanding the claims that it takes anything other than O(n) in the worst case for a tree de-allocation.

function destroy_tree(tree) {
   foreach child in tree
       delete_tree(child)
   free(tree)
}

Zeuthen: Writing a C library, part 2

cmccabe — Sun, 03 Jul 2011 06:30:49 +0000

> And you will want to use the linker symbol versioning instead of static
> versioning, otherwise, you'd break the API all the time. BTW, it is not a
> gcc thing, it is an ELF thing, and Solaris has been doing it since forever.

from http://www.airs.com/blog/archives/220

> Ulrich Drepper and Eric Youngdale introduced a much more sophisticated
> symbol versioning scheme, which is used by the glibc, the GNU linker, and
> gold. The key differences are that versions may be specified in object
> files and that shared libraries may contain multiple independent versions
> of the same symbol

In other words, this is a gcc-specific ELF extension. I wonder if LLVM supports it yet? I found a page from 2008 that said that LLVM didn't have support for this yet, but then I got tired of using the Google.

Zeuthen: Writing a C library, part 1

cmccabe — Sat, 02 Jul 2011 00:20:06 +0000

I never said that you "couldn't do anything useful in a destructor". Destructors are helpful in general for error handling in C++. I just said that std::bad_alloc is not a great way to handle the failure of small memory allocations.

It is true that printf would get you out of a jam in this case, because it doesn't throw the silly bad_alloc exception when it fails to allocate memory. You could also catch bad_alloc in your destructors whenever it pops up, and try to do something reasonable. In some cases, you can force the nothrow variant of new to be used (although not when std::vector and friends are involved.) But that is going to be very difficult in any non-trivial program.

I get annoyed when people talk about exceptions as a panacea for error handling problems. You don't have to think, just use exceptions, and your problems will magically melt away. The reality is, writing low-level code that correctly handles errors is very difficult in either C or C++. It's simple enough to avoid new and free, but once you start needing to implement transactional behavior-- either a function call succeeds or it fails, but it doesn't leave a mess-- things get difficult.

If you find yourself in a scenario where you have to undo changes that you made earlier to some data structure, your error handling may itself encounter an error. And how do you automatically handle that? Well, you have to engage your brain and structure the operation into a prepare operation followed by a commit operation. And that is not going to be trivial in either C or C++.

Zeuthen: Writing a C library, part 1

nix — Fri, 01 Jul 2011 13:40:39 +0000

Yes, probably. And then we can get into fsync() flamewars instead! Isn't POSIX fun?

Zeuthen: Writing a C library, part 1

jwakely — Fri, 01 Jul 2011 10:50:46 +0000

Exactly! (on both points)

Zeuthen: Writing a C library, part 1

dgm — Fri, 01 Jul 2011 09:46:33 +0000

I believe that what really paranoid programs have to do is keep critical state in non-volatile memory (a disk, a remote machine, etc), and do everything possible to ensure that it's always consistent. That way it doesn't matter if the program goes away because of a programming error, a kill signal or the power going down in the middle of a system call.

Zeuthen: Writing a C library, part 1

nix — Fri, 01 Jul 2011 09:37:15 +0000

OK, so my memory was faulty :) not much of a surprise there, some days it seems it consists mostly of faults.

Zeuthen: Writing a C library, part 1

whot — Fri, 01 Jul 2011 05:28:29 +0000

FTR, we discouraged dbus support mostly because the communication API was less than ideal and just talking directly to hal (now udev) was more sensible.

The abort() was extremely annoying while programming but it also lead to the code being very stable. Every small error got punished badly so we had to make sure we fixed up the code properly.

Zeuthen: Writing a C library, part 1

jwakely — Thu, 30 Jun 2011 23:44:24 +0000

but it won't throw a std::bad_alloc, or any other exception, and you were talking about the dangers of exceptions being thrown from destructors, right? and how you can't do anything useful in a destructor because it might throw, and therefore "look pretty grim for RAII"

(although I'm not sure why you were talking about that, the comment you replied to wasn't talking about exceptions *in* destructors, just exceptions *and* destructors as being helpful for error handling)

Zeuthen: Writing a C library, part 1

nix — Thu, 30 Jun 2011 21:12:01 +0000

If it's a base that you can build language bindings on top of, then the libdbus-1 authors have even *less* idea than they might have as to what the process is doing, and it's even more critical that it should never die. (But it is true that a lot of Great Big Languages have no hope of handling OOM errors: dynamic allocation is too fundamental to them. However, for others this same property is a benefit, because they often have a lot of dynamically-allocated storage that they can get rid of, and even their own allocators so they can be sure the storage finds its way back to the OS again.)

Damn good articles btw.

Zeuthen: Writing a C library, part 1

cmccabe — Thu, 30 Jun 2011 19:07:37 +0000

> So make sure your logging API supports printf-style API as
> well (or instead of) only supporting writing a single string,
> then you don't need to concatenate std::strings.

printf can also allocate memory. That is why it is not signal-safe.

Zeuthen: Writing a C library, part 1

njs — Thu, 30 Jun 2011 18:01:47 +0000

If your rebalancing algorithm doesn't require any heap allocations then right, there is no point.

Zeuthen: Writing a C library, part 1

davidz2525 — Thu, 30 Jun 2011 17:49:05 +0000

I think I even prefaced the word 'people' with 'smart' :-). But, yeah, I completely agree that we're both right which is why the guidance is to establish a policy on what to do when the programmer screws up rather than doing either A or B. I brought this up mostly to address the popular misconception that libdbus-1 is an evil library that eats babies - it's not.

(Btw, another misconception is that libdbus-1 is meant for applications to use; it's really not, it's more intended for a base that you can build language/toolkit bindings on top + the implementation used to implement dbus-daemon(1) which MUST be able to handle OOM.)

Zeuthen: Writing a C library, part 1

nix — Thu, 30 Jun 2011 15:23:30 +0000

I'm not sure you *can* completely disable overcommit. Robust Unix programs theoretically have to assume that they might get killed at any instant, either due to OOM in something like the stack (which obviously cannot be trapped), or due to a user sending it a kill signal.

Alas the latter is rare (and misbehaviour might be expected if you kill something maintaining persistent state while it is updating that state), and the former is so rare and so hard to cater to that simply nobody ever bothers. Sufficiently Paranoid Programs could avoid the stack-OOM by doing a massive deep recursion early on, to balloon their stack out to the maximum they might need. A few programs do this. You can avoid being user-killed by being installed setuid or setgid, but this has other disadvantages and is basically never done (at least not solely for this reason).

This is probably a fault of some kind in POSIX, but I have not even the faintest glimmerings of a clue as to how to fix it.

Zeuthen: Writing a C library, part 1

nix — Thu, 30 Jun 2011 15:19:30 +0000

And I see David has linked to this comment with the link text 'people sometimes fail to realize that the caller has a responsibility'. I might respond that people sometimes fail to realize that libraries have a responsibility not to shoot the whole process in the head when the caller could perfectly well recover.

(Ironically, elsewhere in the same post David comments that libraries should not manipulate signal dispositions because these are process-wide state. I'd call the continued existence of a process process-wide state, as well, but apparently David disagrees. I think his attitude leads to appalling and unnecessary instability: he thinks mine leads to unfixed bugs in callers. We are probably both right, but ne'er the twain shall meet.)

Zeuthen: Writing a C library, part 1

stevem — Thu, 30 Jun 2011 14:08:18 +0000

Absolutely. 100%.

A library should *never* call abort in an attempt at error-handling. You throw away any chance for the calling code to do sensible stuff such as clean up properly.

Zeuthen: Writing a C library, part 1

nix — Thu, 30 Jun 2011 12:55:36 +0000

I am not sure if (with overcommit disabled) you have to allocate memory space for the entire binary or not.

You don't. Overcommit does not apply to read-only file-backed regions, because they can be dropped at any time without harm.

Are you sure?

nix — Thu, 30 Jun 2011 12:53:51 +0000

Yes exactly. Generally, library functions which immediately allocate storage will be returning a pointer to that storage: they can return NULL. Library functions which *call* such functions may have more complex work to do, including possibly unwinding partially-completed work. If *this* would require memory allocation, you may need to find a different algorithm, or arrange to do all allocations first (I've done both at various times).

But saying "I won't bother, I'll just abort" is a disservice to your users, no matter *how* hard it is to handle OOM.

Zeuthen: Writing a C library, part 1

MisterIO — Thu, 30 Jun 2011 10:33:20 +0000

>That deletes everything, needs no heap storage, and it's O(n (log n)^2), not so bad.
There's no point to this, a simple remove(value_at_root)(value at root simply because it's the simplest to find) for a balanced binary tree already takes O(log(n)), so why would I create a different algorithm to achieve the same performance?

Zeuthen: Writing a C library, part 1

MisterIO — Thu, 30 Jun 2011 10:28:53 +0000

>then you can put the current node on a linked list that's threaded through the left pointers
We were discussing about the problems caused by allocations in the destructor. And what exacly would I gain by doing this instead of, like I said in the first post, find_minimum(), then next() till the end and save pointers to elements on a vector, then free them all through the vector of pointers? Also, if my assumption in my second post is correct, you don't even need to save temporaries if you do an inorder visit, you just need to free the node once you've reached the parent, checking that the children have all its own children NULL(which means that you've already visited all the grandchildren).

Zeuthen: Writing a C library, part 1

mjthayer — Thu, 30 Jun 2011 07:19:44 +0000

> large process A forks (creating A`), almost all it's memory is COW
>
> process B allocates some memory, but doesn't touch it yet
>
> process A` changes some memory (breaking COW), requiring real memory to hold the result.
>
>process B then tries to use the memory it had previously allocated and finds that it is not available.
That I do not see as a problem - when process B allocates the memory it is really allocated, and if A tries to use its COW memory later it will just not be there.

> if you could somehow define 'forked recently' in a way that could be cheap enough, then you could possibly do it.

That I do see as more of a problem. One could have some background thread gradually actually allocating the process's memory, but that is replacing one piece of complexity by another.

> but the idea that (in the general case), this will make your system more predictable is not something I believe. you have no way of knowing _which_ process (including system daemons) will need to allocate more memory at the instant that you are out, so you really don't know which process will die anyway. (and no, in general processes and libraries don't do anything except die when they run out of memory).

True, it doesn't change the fundamental problem that you need enough memory for whatever you want to do.

> in some ways, it would make it easier to DOS a system, just have your memory hog _not_ die if a malloc fails, instead sleep and try again. eventually something else in the system will need memory and die

I thought that ulimits were supposed to solve that. Do they work as intended these days?

> there's also the problem that without overcommit you need to have significantly more swap enabled in the system (since you have to have enough ram+swap to handle the peak theoretical memory use from large processes doing a fork+exec)

The idea was to disable overcommit except for forking, so that shouldn't be such an issue. Thinking about it one could also freeze the overcommitted process if it tries to actually use its memory and it isn't there (making sure there is a bit of memory left over for doing emergency process surgery).

Are you sure?

cpeterso — Thu, 30 Jun 2011 06:19:11 +0000

> Your approach (the second one) would have worked, if I could have revamped the entire source base to use it. But it is rare that one gets the opportunity to do that, and malloc() tests at least don't look strange.

If you're brave, there's always the C preprocessor:

#define malloc(size) my_xmalloc_with_msg(size, __FILE__, __LINE__, __FUNCTION__)

This approach could still be useful if your macro was only #included by a subset of .c files, leaving some object code still calling libc's malloc().