A solution for the allocation failures problem

[Kelsey Bjarnason]

[snips]
[cross-post added; CLC can be subsequently removed]

It does not, if it did, it would explicitly state that and it does not.

Oh, but it does. It says free releases to be made available for further
allocation. The only things the standard discusses which pertain to
allocation are C functions. Not OS behaviours, not multithreading
schedulers, not network clients and database servers. Nope, it's C
functions, and only C functions, and all done exclusively in the context
of a standalone, isolated, conforming C application set against a
conforming implementation.

In fact, this is a regular topic here in CLC - that "C doesn't do that".
It doesn't do threading. It doesn't do directories. It doesn't do file
systems.

In fact, more generally, it is described in terms of a virtual machine,
whose operation is - as far as is relevant to the code - defined
specifically in terms of operations and definitions from the standard.

This is, for example, how we get the "as if" rule; the implementation
need not work exactly as documented, as long as the results are the same
_as if_ carried out on such a machine.

It's also how we can get things such as fopen to work at all; we define
it in terms _relevant to the code_, not in terms of the OS, as we have no
idea how - or if - the OS handles such things.

In every case, what matters is not the underlying OS or file system or
whether the user is at a keyboard, or a remote terminal, or even isn't a
user at all, but actually a piped-in file providing the input, but
rather, the mechanics of the code as defined by the standard.

One cannot adopt such a stand in the general case then suddenly, in the
case of free, throw up one's hands and suddenly invoke magic operations
of some hypothetical underlying OS.

No, just as we discount the underlying OS when defining how fopen or
getchar works, we must also - to be consistent - discount the underlying
OS when defining how free works. And we do: free releases memory for
subsequent allocation - and the only thing which *can* allocate memory,
the only thing which *exists* as far as the standard is capable of
defining it, is the conforming application, built with a conforming
implementation.

Which means the only thing in the universe which *can* allocate the
memory released by free *is* the application itself. Thus if free
releases the memory back to the OS, it means that free stands unique
among the standard library functions as implicitly assuming operations
beyond the standard, without bothering to document them, not even going
so far as to toss a hat at implementation defined behaviour.

Nope, free documents exactly what it does - releases the memory to be
made available for further allocation - but because of the context in
which that comment is made, the only thing which *can* allocate the
memory is a function or functions applicable to the application - meaning
malloc does qualify, but some hypothetical OS function taking that memory
back doesn't.

 

[Kelsey Bjarnason]

[snips]

C99 7.20.3.2:

The free function causes the space pointed to by ptr to be
deallocated, that is, made available for further allocation.

I'm not necessarily claiming that that's the answer to your question,
merely that if there is an answer, that's it.

The question, of course, is "further allocation" by what? Common sense
tells us that it's perfectly reasonable for the OS to reclaim free()d
memory and make it available for other programs/processes/whatever.

But
since the C standard only barely acknowledge the existence of other
programs, it's not entirely unreasonable to assume that the space must
be made available for further allocation by the same program.
Exactly.

The
standard, for the most part, describes behavior of a single executing
program. Interaction with the environment is described in its own
subsection, C99 7.20.4 (abort, atexit, exit, _Exit, getenv, system).

Making the space available for further use by the current program is
meaningful in the context of the C standard; making it available for any
other use is perhaps beyond the scope of the standard.

Exactly.

However, it's not just "beyond the scope" that's the problem. The
problem is that in doing so, an implementation of free is doing something
not allowed by the standard, which gives it *no* leeway whatsoever to
allow the memory to effectively vanish; it expressly requires the memory
be available for subsequent allocation, therefore it *cannot* hand it
back to the OS - doing so may make it unavailable for further allocation,
by the conforming application which has every right to expect the memory
is available - free's definition states this, absolutely and
unequivocally.

On the other hand, there's no way for a portable program to tell whether
free() makes the space available for the current program;

Of course there is:

void *ptr = malloc( 1024 * 1024 );

if ( ptr )
free( ptr );

Assuming the allocation worked, the application has 1024^2 bytes
available initially. The call to free thus reserves - and assures - that
there are 1024^2 bytes available for subsequent allocation.

We might grant the case that there is a bug in free or malloc somewhere
which means that the 1024^2 bytes are, in fact, reserved but cannot
actually be re-allocated for some reason, but this would be a bug.

In any case, free() is certainly not *required* to make the space
available for other programs (since there may not be any other
programs).

Actually, it is required not to. The C standard does not - cannot -
define how other programs operate. It can - and does - define how a
conforming application, with a conforming implementation, is supposed to
operate. According to its definition, free releases the memory for
subsequent allocation, and the only thing which, in the scope of the
standard, *can* do "subsequent allocation" is the program which called
free in the first place.

 

[jacob navia]

However, it's not just "beyond the scope" that's the problem. The
problem is that in doing so, an implementation of free is doing something
not allowed by the standard, which gives it *no* leeway whatsoever to
allow the memory to effectively vanish; it expressly requires the memory
be available for subsequent allocation, therefore it *cannot* hand it
back to the OS - doing so may make it unavailable for further allocation,
by the conforming application which has every right to expect the memory
is available - free's definition states this, absolutely and
unequivocally.

This means that if a program allocates temporarily an enormous quantity
of memory the OS is forced to keep that memory unused until the program
exists.

Dogmatism, doesn't work here. Imagine a server process that never
exists.

It allocates 10MB, then frees 10MB

Then it allocates 10MB+10, then frees it

Then it allocates 10MB+16, then frees it.

For the program, the allocated memory should be zero.
For the operating system however the allocated memory
would be 30MB.

In a few dozens iterations of this the program would
take all available memory for no reason.


This is unlikely.

In modern operating systems anyway, we are speaking of
virtual addresses anyway. Real memory is managed
by the MMU and the operating system. So, all this discussion
is not very useful anyway.

 

[Keith Thompson]

[snips]

On the other hand, there's no way for a portable program to tell whether
free() makes the space available for the current program;

Of course there is:

void *ptr = malloc( 1024 * 1024 );

(Quibble: the multiplication could overflow.)

if ( ptr )
free( ptr );

Assuming the allocation worked, the application has 1024^2 bytes
available initially. The call to free thus reserves - and assures - that
there are 1024^2 bytes available for subsequent allocation.

We might grant the case that there is a bug in free or malloc somewhere
which means that the 1024^2 bytes are, in fact, reserved but cannot
actually be re-allocated for some reason, but this would be a bug.

[...]

So you're saying that this program:

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
#define SIZE (1024L & 1024L)
void *p = malloc(SIZE);
if (p == NULL) {
return 0;
}
free(p);
p = malloc(SIZE);
if (p == NULL) {
puts("OOPS!\n");
}
free(p);
return 0;
}

cannot legally print "OOPS!"? That's an interesting intepretation of
the standard, but I don't think I'm willing to go quite that far.
(For one thing, I don't want to give ammunition to the folks who claim
that not all malloc() calls should be checked for failure. })

Consider an implementation in which malloc and free maintain some kind
of internal history, not accessible to the program but available for
debugging. The state of the "heap" (or whatever the implementation
uses) could easily be different after the first malloc/free pair than
it was at the beginning of the program. Even if the free()d memory is
made available for further allocation by the same program, the second
malloc() could fail (but a slightly smaller one might succeed).
Loggging all malloc and free calls might be a silly thing to do; the
question is how tight are the requirements that the standard places on
malloc and free.

 

[Kelsey Bjarnason]

[snips]

So you're saying that this program:

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
#define SIZE (1024L & 1024L)
void *p = malloc(SIZE);
if (p == NULL) {
return 0;
}
free(p);
p = malloc(SIZE);
if (p == NULL) {
puts("OOPS!\n");
}
free(p);
return 0;
}

cannot legally print "OOPS!"?

Of course it can - but *not* through failure to reserve that initial
block of memory for subsequent reallocation.

It could, for example, simply have a bug which fails to put the memory
back into the allocation area properly, which would cause a failure, but
it *cannot*, within the confines of the standard, fail on the second
malloc because the OS has taken over the memory; this is *expressly*
disallowed by the definition of free.

Consider an implementation in which malloc and free maintain some kind
of internal history, not accessible to the program but available for
debugging. The state of the "heap" (or whatever the implementation
uses) could easily be different after the first malloc/free pair than it
was at the beginning of the program.

Indeed. The second malloc can fail, no argument. It simply cannot fail
*because free returned the memory back to the OS*. The definition of
free, in the context in which it is applied, doesn't permit that.

 

[Keith Thompson]

[snips]

So you're saying that this program:

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
#define SIZE (1024L & 1024L)
void *p = malloc(SIZE);
if (p == NULL) {
return 0;
}
free(p);
p = malloc(SIZE);
if (p == NULL) {
puts("OOPS!\n");
}
free(p);
return 0;
}

cannot legally print "OOPS!"?

Of course it can - but *not* through failure to reserve that initial
block of memory for subsequent reallocation.

It could, for example, simply have a bug which fails to put the memory
back into the allocation area properly, which would cause a failure, but
it *cannot*, within the confines of the standard, fail on the second
malloc because the OS has taken over the memory; this is *expressly*
disallowed by the definition of free.

Consider an implementation in which malloc and free maintain some kind
of internal history, not accessible to the program but available for
debugging. The state of the "heap" (or whatever the implementation
uses) could easily be different after the first malloc/free pair than it
was at the beginning of the program.

Indeed. The second malloc can fail, no argument. It simply cannot fail
*because free returned the memory back to the OS*. The definition of
free, in the context in which it is applied, doesn't permit that.

I see an ambiguity in the standard's wording that you apparently don't
see (which isn't necessarily to say that I'm right and you're wrong).

The standard barely, if at all, acknowledges the possibility of other
programs executing in parallel. But it certainly doesn't forbid them.
The existence of the system() function clearly implies that, at least,
another program can execute while the current one is suspended.

The free() function "causes the space pointed to by ptr to be
deallocated, that is, made available for further allocation". It
doesn't explicitly say by whom or by what, and it's not nearly as
obvious to me as it seems to be to you that it must be available to
the current program. If I malloc() a chunk of memory, then free() it,
it doesn't seem entirely unreasonable for that space to be made
available to a program that I then invoke via system(). (But then you
could argue, I suppose, that that space must be deallocated when the
other program terminates, and made available again to the current
program.)

If my program needs a huge amount of memory during startup, but I know
it will never need it again as it continues to run, I *want* to be
able to return it to the OS rather than hogging it indefinitely.

The real question is what the authors of the standard intended, which
is why I've posted the question to comp.std.c; see the thread
"available for further allocation"?

 

[Flash Gordon]

Ian Collins wrote, On 08/02/08 19:23:
char *p3 = NULL;

But what if you acquire something here...

if ((p3 = malloc(100)) == NULL
{
ReturnCalue = ENOMEM;
goto ExitFunction;
}

and release it here?

free(p3);
p3 = NULL;

free(p3);

There, that wasn't difficult.

 

[Richard Tobin]

Indeed. The second malloc can fail, no argument. It simply cannot fail
*because free returned the memory back to the OS*. The definition of
free, in the context in which it is applied, doesn't permit that.

As I pointed out before, since there is no way for the program to
tell why it failed, it must be allowed under the as-if rule.

A program where malloc() fails because it has returned memory to
the OS behaves as if it failed for some other reason.

-- Richard

 

[Ian Collins]

Ian Collins wrote, On 08/02/08 19:23:

char *p3 = NULL;


if ((p3 = malloc(100)) == NULL
{
ReturnCalue = ENOMEM;
goto ExitFunction;
}


free(p3);
p3 = NULL;

I intended the "something" to be something other than memory, say a lock
or opening a file.

There, that wasn't difficult.

Not difficult, but oh so messy!

Try again with "something" being a file!

 

[Wolfgang Riedel]

(e-mail address removed) said:


Your hypothesis is incorrect; fgetline returns a non-zero error code for an
allocation failure (it happens to be -3, which I really ought to wrap in a
#define).

why not specific POSIX.1 [-] ENOMEM
(happens to be 12 here)

Wolfgang

 

[Richard Heathfield]

Wolfgang Riedel said:

(e-mail address removed) said:


Your hypothesis is incorrect; fgetline returns a non-zero error code for
an allocation failure (it happens to be -3, which I really ought to wrap
in a
#define).

why not specific POSIX.1 [-] ENOMEM

Because under ISO C it's not guaranteed to be present (in which case the
code won't compile unless I define it myself, in which case I invade
implementation namespace).

 

[Joachim Schmitz]

Wolfgang Riedel said:

(e-mail address removed) said:
A bonus question: what happens when malloc() fails inside
fgetline() (my hypothesis: nothing, we pretend we hit EOF. But we
don't "crash and burn", which is Good)


Your hypothesis is incorrect; fgetline returns a non-zero error
code for an allocation failure (it happens to be -3, which I really
ought to wrap in a
#define).

why not specific POSIX.1 [-] ENOMEM

Because under ISO C it's not guaranteed to be present (in which case
the code won't compile unless I define it myself, in which case I
invade implementation namespace).

#include <errno.h>
#ifndef ENOMEM
# define ENOMEM 12
#endif

And no namespace invasion takes place, does it?

Bye, Jojo

 

[Richard Heathfield]

Joachim Schmitz said:

Wolfgang Riedel said:

Richard Heathfield schrieb:

why not specific POSIX.1 [-] ENOMEM

Because under ISO C it's not guaranteed to be present (in which case
the code won't compile unless I define it myself, in which case I
invade implementation namespace).

#include <errno.h>
#ifndef ENOMEM
# define ENOMEM 12
#endif

And no namespace invasion takes place, does it?

You are making the (understandable!) assumption that any implementation
defining ENOMEM defines it to mean what POSIX defines it to mean. But
implementations are not required to do this. I consider it safest to avoid
that namespace completely.

 

[Richard Tobin]

#include <errno.h>
#ifndef ENOMEM
# define ENOMEM 12
#endif

What if errno.h contains

#ifdef _SOME_EXTENSION
#define ENOMEM 13
#endif

and the user does

#include "whatever_defines_getline"
#define _SOME_EXTENSION
#include <errno.h>

That is, can you guarantee ESOMETHING isn't going to be defined just
by including <errno.h> and doing an #ifdef?

-- Richard

 

[Flash Gordon]

Ian Collins wrote, On 11/02/08 03:57:
FILE *f1 = NULL;

if ((f1 = fopen("fred","r")) == NULL)
{
ReternValue = FILEERROR;
goto ExitFunction;
}


fclose(f1);
f1 = NULL;

I intended the "something" to be something other than memory, say a lock
or opening a file.

Not difficult, but oh so messy!

Try again with "something" being a file!

Just as easy. The same principle would work for a lock (your lock
function surely has a way of flagging that the lock was not granted). If
really necessary you can add a flag to indicate whether you have the
resource, but generally I find that this is not required.

As to messy, well, you can wrap it up in various ways to hide the mess
if you consider it messy.

 

[Kelsey Bjarnason]

[snips]

As I pointed out before, since there is no way for the program to tell
why it failed, it must be allowed under the as-if rule.

A program where malloc() fails because it has returned memory to the OS
behaves as if it failed for some other reason.

Actually, that's not applicable, strictly speaking.

Under the terms of the standard, the memory released by free is available
to the application; the OS is not allowed to poach it. Thus the
application can, in fact, rely on that memory being there.

So let's look at an example.

void *ptr = malloc( 60000 );
if ( ptr == NULL ) { bail }

/* If we get here, we have the memory allocated */
free( ptr );

....

ptr = malloc( 10000 );


Assuming that, in the intervening code - ... - there were no other
allocations, what does the code know at the point of the second malloc?

It knows that there are 60,000 bytes "reserved" for the application's
use. It knows it's requesting 10,000 of them. It knows that the
definition of free does not allow the implementation to hand off the
60,000 bytes to anything but the program.

Thus, the program knows that the malloc here "cannot" fail - there *is*
sufficient memory.

So what happens if the malloc *does* fail? It means that the
implementation's memory management is *so* bad, it imposes a 50,000+ byte
overhead on a 10,000 byte allocation - a bug so bad as to be, IMO, fatal.

So yes, under the as-if rule, you're right, the program cannot tell the
difference between a fatal implementation bug and non-conforming
behaviour... but then, does this matter? Whether it's a bug in the
memory management or a failure to reserve the memory as required, it is
*still* a conformance failure, a bug. Equivalence of failures under as-
if is, indeed, equivalence, but when both behaviours are broken, so what?

 

[Herbert Rosenau]

Indeed. The second malloc can fail, no argument. It simply cannot fail
*because free returned the memory back to the OS*. The definition of
free, in the context in which it is applied, doesn't permit that.

Does you really need an exampel where malloc() will fail you serve an
amout of memory even as ther are 90% of availkable memory is really
unused when it will never give memory given back to the OS?

malloc has you to give an continous block of memory of the requested
size. If there is none availabe it must free.

So assume that you have to malloc 10,000 blocks of memory of 1oK each.
Now the app give each second block back to malloc() using free. as now
are 500,000 blocks are unused you are now absolutel unable to get only
one single block of 15,000K because the memory holded by malloc has
only block of a maximum size of 10,000K each but not asingle one of
15,000 because the only instance that would reassign pages to such big
block if it had enough free space avilable. But as malloc() is sitting
of a high number blocks and it has no access to the OSes memory
management it can't reorganise the page table to build a continous
area that matches the required size.

When malloc gives unused blocks back to the OS because it can at any
time them again then the OS can reassign pages to any new block size
it should deliver.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!

 

[Eric Sosman]

[snips]

So you're saying that this program:

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
#define SIZE (1024L & 1024L)
void *p = malloc(SIZE);
if (p == NULL) {
return 0;
}
free(p);
p = malloc(SIZE);
if (p == NULL) {
puts("OOPS!\n");
}
free(p);
return 0;
}

cannot legally print "OOPS!"?

Of course it can - but *not* through failure to reserve that initial
block of memory for subsequent reallocation.

It could, for example, simply have a bug which fails to put the memory
back into the allocation area properly, which would cause a failure, but
it *cannot*, within the confines of the standard, fail on the second
malloc because the OS has taken over the memory; this is *expressly*
disallowed by the definition of free.

Since malloc() is not obliged to describe the reason for a
failure, how could a program detect that the failure was or was
not due to "the OS has taken over the memory?" It seems to me
your contention is untestable, hence of no practical force.

As for "expressly disallowed," I see no language that refers
to the O/S taking over memory.

 

[Richard Tobin]

Under the terms of the standard, the memory released by free is available
to the application; the OS is not allowed to poach it.

I haven't yet seen anyone else who agrees with your interpretation of
this.

So what happens if the malloc *does* fail? It means that the
implementation's memory management is *so* bad, it imposes a 50,000+ byte
overhead on a 10,000 byte allocation - a bug so bad as to be, IMO, fatal.

So yes, under the as-if rule, you're right, the program cannot tell the
difference between a fatal implementation bug and non-conforming
behaviour... but then, does this matter? Whether it's a bug in the
memory management or a failure to reserve the memory as required, it is
*still* a conformance failure, a bug. Equivalence of failures under as-
if is, indeed, equivalence, but when both behaviours are broken, so what?

Is "impos[ing] a 50,000+ byte overhead on a 10,000 byte allocation" a
conformance failure rather than very poor quality of implementation?
Chapter and verse please. If it isn't a conformance failure, then nor
is releasing memory to the OS.

-- Richard

 

[user923005]

[snips]

As I pointed out before, since there is no way for the program to tell
why it failed, it must be allowed under the as-if rule.

A program where malloc() fails because it has returned memory to the OS
behaves as if it failed for some other reason.

Actually, that's not applicable, strictly speaking.

Under the terms of the standard, the memory released by free is available
to the application; the OS is not allowed to poach it.  Thus the
application can, in fact, rely on that memory being there.

So let's look at an example.

void *ptr = malloc( 60000 );
if ( ptr == NULL ) { bail }

/* If we get here, we have the memory allocated */
free( ptr );

...

ptr = malloc( 10000 );

Assuming that, in the intervening code - ... - there were no other
allocations, what does the code know at the point of the second malloc?

It knows that there are 60,000 bytes "reserved" for the application's
use.  It knows it's requesting 10,000 of them.  It knows that the
definition of free does not allow the implementation to hand off the
60,000 bytes to anything but the program.

Thus, the program knows that the malloc here "cannot" fail - there *is*
sufficient memory.

So what happens if the malloc *does* fail?  It means that the
implementation's memory management is *so* bad, it imposes a 50,000+ byte
overhead on a 10,000 byte allocation - a bug so bad as to be, IMO, fatal.

I have absolutely, positively seen this happen.

So yes, under the as-if rule, you're right, the program cannot tell the
difference between a fatal implementation bug and non-conforming
behaviour... but then, does this matter?  Whether it's a bug in the
memory management or a failure to reserve the memory as required, it is
*still* a conformance failure, a bug.  Equivalence of failures under as-
if is, indeed, equivalence, but when both behaviours are broken, so what?

The malloc() function can fail because the operating system failed to
find a block of the right size. It may be that memory has become
fragmented by malloc()/free() calls. The locations of things change
on different calls and the required size may be unavailable. This is
a quality of implementation problem, to be sure, but I know for a fact
that it can occur.

Consider:

foo = malloc(100); /* This happens to be all of the computer's
available RAM */
if (foo == NULL) exit(EXIT_FAILURE); /* It worked, so we have this for
later */
free(foo); /* We release it */
bar = malloc(2); /* We need a tiny memory object, leaving 98 bytes
still available */
foo = malloc(50); /* fails because bar occupies bytes 49 and 50 */

Situations like the above can obviously cause problems with less
memory available than we would expect.