Denys Vlasenko vda.linux at googlemail.com
Sun Jun 8 22:28:01 UTC 2008

Hi Bernhard,

thanks for joining the discussion.

I fully realize that the notion of using malloc in libc
is strange. It was strange to me too. It took some time,
thinking and experimenting (by repeatedly running machines
into OOM condition and observing) to realize that
perception of what is "the right thing to do" in this case
and what is actually the right thing to do are not the same.

Non-obviously wrong part of it is that "malloc can fail" and
"<something else> cannot fail".

A small story. I wrote a glibc's nscd replacement last year.
glibc's nscd, when run on Google machines (and not only on them),
was crashing or locking up, and since it was broken by design,
I rewrote it. It become six times smaller, but the best part was,
it wasn't crashing and locking up.

Some guys took it and run some testing and one of their responses was
"wow, it doesn't even overflow the stack!" - to which I responded
"wtf? why original one did? why it was using so much stack?!??"

It turned out that nscd authors minimised use of malloc
"because malloc can fail". They used alloca which "never fails".
Guess what - if UNIX group has 500000 members and you
try to process the result of getgrnam() in alloca buffer,
you blow ENTIRE 8 MEG STACK on i386. alloca can fail.

My program was stupid. Extremely. I am not a genius, unlike
nscd authors. I was using malloc, straightforwardly.
My program was allocating space for UNIX group
with 500000 members just fine.

Alloca was failing while malloc was not! This is not obvious,
but true.

On Sunday 08 June 2008 21:15, Bernhard Fischer wrote:
> On Sun, Jun 08, 2008 at 05:35:22PM +0200, Denys Vlasenko wrote:
> >On Sunday 08 June 2008 16:21, Bernd Schmidt wrote:
> >> Denys Vlasenko wrote:
> >> > In both cases user's experience is essentially the same - [s]he cannot
> >> > run the program because there is not enough memory.
> >> 
> >> Except the program that called crypt may have left some state - 
> >> temporary files, partial modifications in other files, whatever - 
> >> because it did not expect to fail at this point.
> >
> >If this program wants to not be killed by OOM, it needs to install
> >the handler for this situation. It is not difficult at all.
> The problem is that this is not the expected behaviour and is absolutely
> not standard confirming (in contrast, it breaks established standards
> and expectations silently).
> We can't do that.

I have to say it - if we are going to admit that reality
trumps standard legalese - then yes, we can.

Established expectation in this case is that certain libc functions
never fail. NEVER. Which is practically not attainable.

Ok, imagine that crypt() uses static buffers.
If you call crypt() while you are low on stack, it will crash,
despite the assumption that "crypt never fails". On MMU machine,
if you call crypt() while your machine is in OOM state -
it may crash because crypt touches static buffers which are
allocated on request and also can be swapped out, and in OOM
crunch kernel simply CANNOT satisfy your request "give me
that zeroed page in my bss". IT IS NOWHERE TO BE TAKEN FROM.
On Linux, this will either invoke oom killer or will leave
the machine locked up in OOM if oom killer is disabled.

IOW: crypt() which uses static buffers is as likely
to die/lock up on OOMing machine as malloc() based one.

Let me go back and again enumerate negative sides of
"malloc avoidance" in libc.

First, we lose the benefits of more resource-efficient
nature of malloc - it allocates memory on demand,
not beforehand as static buffers do.

Second, it allocates as much as you ask for, you
do not need to size malloced block to maximum possible size.

Third, some algoritms simply require dynamic memory.
When developer is seeing malloc as ultimate evil, and then
he _has to_ use it in libc, he has to do SOMETHING on malloc
failure. Typical end result (/// are mine):

struct mntent *getmntent(FILE * filep)
    struct mntent *tmp;
    static char *buff = NULL;
    static struct mntent mnt;

    if (!buff) {
            buff = malloc(BUFSIZ); /// I am so lame :(
                if (!buff)
                    abort(); /// Lets hope no one will notice my sin

It looks like using malloc was felt as a sin, and abort()ing
could not possibly make developer's karma dirtier, so why not.

Another similar case was glibc' obstack. It was also using malloc
(because it HAD TO HAVE dynamically allocated storage,
static buffers won't do), was ashamed of it and was committing
seppuku via abort() similarly to above code.

I just looked and glibc 2.6.1 apparently saw the light:

/* The functions allocating more room by calling `obstack_chunk_alloc'
   jump to the handler pointed to by `obstack_alloc_failed_handler'.
   This can be set to a user defined function which should either
   abort gracefully or use longjump - but shouldn't return.  This
   variable by default points to the internal function
   `print_and_abort'.  */
static void print_and_abort (void);
void (*obstack_alloc_failed_handler) (void) = print_and_abort;

Looks familiar? Yes, this is very similar ti __uc_malloc.

Back to abort() in getmntent().
This code was living in getmntent() for almost four years -
there were no floods of angry user emails.
I suppose this says something of the frequency of abort()
being triggered here in real world usage.

Why users did not complain? getmntent() was "horribly buggy",
it was "aborting unexpectedly" and no one was bitten by it?

Well, actually I think yes, nobody was bitten by it because
nobody in their right mind is running machines
on the brink of OOM. Why? This is actually quite clear,
if you recall how OOMed machine looks like:

Even if libc would be perfect and not crash on OOM, and all
libraries and programs would be similarly perfect and not crash
on OOM (fat chance), you still CANNOT do anything useful on
OOMing machine - yes, programs maybe don't crash, they "only"
refuse to do what you ask them to do, they error out:
$ ls
cannot exec ls: Cannot allocate memory
$ cat httpd.log
cannot exec cat: Cannot allocate memory

Same goes for your init, httpd, crond, etc - they all error out
internally, can't fork porcesses, can't process data, in other words -
the system is unusable, and the fact that "no program is crashing"
does not help one iota.

IOW: in real world, OOMs are accidental, they are not planned for.
Most programs are not tested to not crash in this situation, partly
because they can't be useful in that state anyway, so why bother.

Therefore I claim that concerns about "improper" behavior
of libc on OOM condition are not warranted - when OOM hits,
no one will care where or how exactly programs started failing.
Programs were DOOMED to fail - if you need 120 megs and you
have only 100, you can't make it work. Period.
People will rightly look into fixing OOM instead.

That's why I am saying "let's rehabilitate malloc". malloc
is not a sin. Let's use it where appropriate, but
giving users ability to detect libc-internal malloc failures.

In all practical uses it will work just fine, and people who
insist on not crashing in the OOM will not be left out in the cold -
a few #ifdefs and they are happy campers (ok maybe a bit grumpy).

This actually _improves_ our performance in near-OOM conditions.
How? Going back to crypt(). If we will go back and reinstate
static buffers there, busybox's data+bss size will jump from 8k
to 80k - tenfold increase. On NOMMU, if you have N running
busybox daemons, you already have additional N*72k bytes
allocated and sitting there, totally unused.

This will be a measurable, real drop in memory utilisation
efficiency. Just start 1000 copies of "busybox sleep 10"
and measure how many more megabytes that would require.
This is a real world effect.
OTOH, "stability against OOM" is a myth, it can't be achieved.

More information about the uClibc mailing list