Re: A solution for the allocation failures problem

On Tue, 12 Feb 2008 00:01:37 +0000, Richard Tobin wrote:

In article <7fj685-0o6.ln1@xxxxxxxxxxxxxxxxxxxx>, Kelsey Bjarnason
<kbjarnason@xxxxxxxxx> wrote:

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.

Can you find anything in the standard which *allows* this behaviour?

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.

Awright, let's try it this way.

What, exactly, is the standard defining?

It is defining how a program, written against the standard and used with
an implementation, also written against the standard, is expected to
behave.

Simplified, it defines how your C program is supposed to behave.

Part of that definition is what your C program can expect from the
implementation. When the program calls fopen, the standard doesn't say
*how* fopen works, it simply tells the program what it can expect - a
pointer to a FILE structure, usable with some other functions such as
fread and fclose, or a NULL.

The standard says nothing whatsoever about what the call to fopen means
in terms of directory structures or file systems or what have you, it
defines the behaviour *solely* in terms of what the program can expect.

In fact, the standard *cannot* be expected to define anything beyond what
the program can expect, as the standard cannot mandate that a system use
a particular file system, or directory structure, or require that it
actually use a keyboard, screen and the like.

Further, it takes some great pains to *not* make any assumptions - or
assurances - about the underlying mechanics of the library. It does not
tell the program that getchar() *only* talks to keyboards, or that printf
*must* go out to a monitor. Instead, it defines the behaviours of these
things solely and exclusively within its own domain: the behaviour of the
C program.

So we come to free. Free, which is defined, in part, as making
previously allocated memory available for further allocation. What does
this tell us?

Context, always context. Is the context of the C standard sufficient to
define the behaviour of the underlying OS? Or to even require an
underlying OS? No. Is it sufficient to define all the mechanics of how
the system manages its memory? No.

It *is*, however, sufficient to define what the C program can expect, and
it does so, right there. In defining the behaviour of free in the only
context which it *can* define things - that of the program - it expressly
says the memory will be made available for further allocation.

It has thus *guaranteed* this memory *will* be available. The OS cannot
poach it, this is expressly against what free guarantees.

So someone brings up the as-if rule, to wit, the implementation can
behave "as-if" the OS stole the memory.

No, it cannot. The as-if rule does not allow an implementation to behave
in a non-conforming manner, to violate the guarantees of the standard,
*unless* undefined behaviour is invoked. Without UB being invoked, the
implementation is expected - required - to behave according to the
guarantees of the standard, which quite clearly state that the memory
will be available.

So, if the as-if rule doesn't apply, what's left? Under what other
conditions can an allocation request fail, despite the guarantees of the
memory being available?

Basically, there are three cases where this can happen. I'll re-post
the example for clarity:

void *ptr = malloc( 60000 );
if ( ! ptr ) { crash and burn }
free( ptr );
ptr = malloc( 10000 );

Here are, as I see it, the only possible conditions under which the
second call to malloc can ever fail:

1) Your implementation is non-conforming and it gives the memory back to
the OS

2) Your implementation's memory management is so bad that when it has a
pool of 60,000 bytes available it can't manage the memory pool well
enough to actually hand back 10,000 bytes worth - your implementation has
a serious, possibly fatal bug

3) Your implementation's memory management is so bad that it imposes an
overhead of more than 50,000 bytes on a 10,000 byte allocation, so the
allocation plus overhead won't fit in the 60,000 byte space available -
your implementation has a serious, possibly fatal bug


Why is any of this even a discussion point, though? It's pretty cut and
dried; the definition of free says the memory is made available for
further allocation, the whole point to the standard is to define the
behaviour of the program, and it does so - it tells it, flat out, no ifs,
ands or buts, *no options whatsoever*, the memory is made available for
further allocations.

The only option an implementation has to allow a subsequent allocation to
fail is to abuse QOI issues, such as imposing massive overhead on
allocations, or simply being really, stinkingly bad at managing the
memory pool.

.

Relevant Pages

  • Re: Freeing memory - will it be available immediately
    ... Your interpretation of "as the standard defines it" is ... Your interpretation of "for further allocation" as "for futher ... Except that this ignores the very reason for the standard, ... return the memory back to the OS in the manner you describe. ...
    (comp.lang.c)
  • Re: malloc under linux
    ... It means what it says, i.e., even if malloc returns a non-null ... memory might not actually be allocated. ... Standard even when some other process is killed and sufficient memory is ... I can't see how the Standard does not permit lazy allocation, ...
    (comp.lang.c)
  • Re: Freeing memory - will it be available immediately
    ... Earlier you did seem to stress the fact that the standard does nothing ... further allocation" as returning the memory to the place it came from. ... word "allocate" can be taken to be a change of ownership. ...
    (comp.lang.c)
  • Re: calloc/free: a preplexing observation
    ... > that any program that writes to stdout can be strictly conforming): ... > whether lazy allocation is conforming or not, ... > The requirement for mallocis that it has to behave as the standard ... > recursive function call attempts to allocate a terabyte of memory, ...
    (comp.lang.c)
  • Re: How to release heap memory that is marked as free
    ... As I said, fragmentation is a very serious problem, and one of the most serious problems ... my allocator was accused of using massive amounts of memory. ... I'm going to have to re-think the memory allocation that I'm ... process's 'working set'. ...
    (microsoft.public.vc.mfc)