A solution for the allocation failures problem

M

Morris Dovey

Kelsey said:
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.

There is no such guarantee - [7.20.3] states that "If the space
cannot be allocated, a null pointer is returned."

The C program can expect to receive either a pointer to the
requested allocation on success, or NULL on failure. /That/ is
what the standard guarantees.
 
K

Kelsey Bjarnason

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.
 
D

Douglas A. Gwyn

Kelsey said:
[snips]
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, ...

The region of memory returned by invoking free() is potentially
reallocatable, but until it is reallocated, access to it results
in undefined behavior, and in fact a conforming C implementation
*can* remove it from the program's address space if it wishes.
 
R

Randy Howard

[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.

Is this really a guarantee from the standard? I don't recall ever
reading such a guarantee, but I might have overlooked it. C&V please?
 
R

Richard Heathfield

Randy Howard said:
Is this really a guarantee from the standard? I don't recall ever
reading such a guarantee, but I might have overlooked it. C&V please?

Kelsey's text is of course from the description of free():

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

What is at issue here is not C&V, but the interpretation thereof.

Kelsey makes the most convincing case I have ever read for implementations
being required to make freed memory available to the program. Richard
Tobin said that nobody else has posted a view that supports Kelsey, but
let us not forget that ISO C conformance is not a democratic process. It
doesn't matter how many people write void main programs - it doesn't make
void main right, does it? Well, if Kelsey is right, it doesn't matter how
many people disagree with him. But if he's wrong, he's wrong.

Personally, I think he's right. But of course I could be wrong about that.
 
R

Randy Howard

Randy Howard said:


Kelsey's text is of course from the description of free():

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

What is at issue here is not C&V, but the interpretation thereof.

Quite. If it said "for further allocation by the same program" maybe.
As is, I'm not sure I agree.
 
R

Richard Tobin

I haven't yet seen anyone else who agrees with your interpretation of
this.
[/QUOTE]
Can you find anything in the standard which *allows* this behaviour?

The difference in interpretation is that you're the only one who thinks
the standard would have to explicitly allow it.
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.

Again, you're the only one who interprets it that way.

As you say, the standard can't be expected to define the details
of the operating system. If it can't do that, and it can't prevent
memory being returned to the operating system without talking
explicitly about the operating system, you are led to the absurd
conclusion that a programming language standard *can't* allow
memory to be return to the operating system.
So someone brings up the as-if rule, to wit, the implementation can
behave "as-if" the OS stole the memory.

No, that's not what I said. It can return it to the operating system
because that is behaving as if malloc() failed for some other (allowable)
reason.
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?
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

So is either of these "possibly fatal bugs" a conformance failure?
If so, which bit of the standard do they not conform to?
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.

And the obvious interpretation, corresponding to reality, is that
these allocations may be under the control of the operating system.

There are three possibilities:

(1) The standard means, and is intended to mean, what you believe.
(2) The standard means what you believe, but this is due to poor
wording, and does not reflect the intent of the authors.
(3) The standard doesn't mean what you think.

Which of (1) and (2) do you think it is?

-- Richard
 
R

Richard Tobin

Richard Heathfield said:
Richard
Tobin said that nobody else has posted a view that supports Kelsey, but
let us not forget that ISO C conformance is not a democratic process.

Nor is the standard an inerrant document. The standard is written
in human language, and there is no proceduure for determining
absolutely what it means.

If the language of the standard does not convery the intention of
the authors, then it is the standard that's wrong. The solution is
a clarification of the standard, not that we all switch to the
unintended intetrpretation.

-- Richard
 
M

Morris Dovey

Kelsey said:
Well, thank you for that, but for some reason consensus seems to be
"Never mind what the standard says, ignore than and do what it means,
instead" - without stopping to realize that the only way we can determine
"what it means" is from "what it says".

Agreed. The diversity of viewpoints would seem to indicate that
there's a certain amount of ambiguity in the wording.

At the program level, of course, we'd like to be reassured that
the resources we want will be available - and at the system level
we'd like to see a maximum of resource sharing to facilitate cost
containment. Depending on which way your hat is turned, you might
read the standard either way. :)
Oh well. Someone, somewhere, other than me might at some point care that
the wording and the intention are completely at odds with each other. I
give up.

Don't give up. Take the problem to c.l.c.m and suggest that a
clearer statement is appropriate. IMO, there shouldn't be a need
to debate the /meaning/ of the standard.
 
K

Kelsey Bjarnason

[snips]

Again, you're the only one who interprets it that way.

Because that's what it says, in black and white.
As you say, the standard can't be expected to define the details of the
operating system. If it can't do that, and it can't prevent memory
being returned to the operating system without talking explicitly about
the operating system, you are led to the absurd conclusion that a
programming language standard *can't* allow memory to be return to the
operating system.

No, I'm led to the conclusion that the standard, which defines the
behaviour of a C program, actually *defines the behaviour of a C
program*. Part of that definition, right there in black and white, is
that free releases the memory for subsequent allocation.

That is the behaviour defined, that is the behaviour defined *in defining
the behaviour of a C program*.
 
K

Kelsey Bjarnason

[snips]

Kelsey makes the most convincing case I have ever read for
implementations being required to make freed memory available to the
program.

Well, thank you for that, but for some reason consensus seems to be
"Never mind what the standard says, ignore than and do what it means,
instead" - without stopping to realize that the only way we can determine
"what it means" is from "what it says".

Oh well. Someone, somewhere, other than me might at some point care that
the wording and the intention are completely at odds with each other. I
give up.
 
M

Morris Dovey

Richard said:
IMHO this belongs in comp.std.c, since it's a discussion about the Standard
rather than the language.

Oops/thanks! (Having trouble saying what I mean [not a good
sign])
 
R

Richard Heathfield

Morris Dovey said:
Kelsey Bjarnason wrote:

Don't give up. Take the problem to c.l.c.m and suggest that a
clearer statement is appropriate.

IMHO this belongs in comp.std.c, since it's a discussion about the Standard
rather than the language.
IMO, there shouldn't be a need to debate the /meaning/ of the standard.

Agreed - so when there is such a need (i.e. when people who are fairly
conversant with the Standard can't agree about what it means), it is an
indication that the Standard is, or at least may be, at fault.
 
K

Keith Thompson

Kelsey Bjarnason said:
[snips]

Again, you're the only one who interprets it that way.

Because that's what it says, in black and white.
As you say, the standard can't be expected to define the details of the
operating system. If it can't do that, and it can't prevent memory
being returned to the operating system without talking explicitly about
the operating system, you are led to the absurd conclusion that a
programming language standard *can't* allow memory to be return to the
operating system.

No, I'm led to the conclusion that the standard, which defines the
behaviour of a C program, actually *defines the behaviour of a C
program*. Part of that definition, right there in black and white, is
that free releases the memory for subsequent allocation.

That is the behaviour defined, that is the behaviour defined *in defining
the behaviour of a C program*.

That's not the only way to interpret the black and white wording of
the standard.

free() makes the space "available for further allocation". If the
space is made available for further allocation *by other programs*,
then it's been made available for further allocation.

Similarly, when a program creates a file, that file becomes available
for use by other programs; another program opening the file might make
it unavailable to the current program. Would you argue that that
behavior would violate the standard?

Over in comp.std.c, Doug Gywn, a member of the ISO C committee, has
said that memory deallocated by free() can be reclaimed by the OS (you
can find the article for his exact words). I'm not saying his
statement has the force of law, but it does imply something about the
intent. In my opinion, the words of the standard are uncomfortably
ambiguous, but they are consistent with the intent.
 
K

Keith Thompson

Richard Heathfield said:
Morris Dovey said:

IMHO this belongs in comp.std.c, since it's a discussion about the Standard
rather than the language.
[...]

Agreed -- which is why I started a thread there, with the subject

"available for further allocation"?
 
F

Flash Gordon

Kelsey Bjarnason wrote, On 12/02/08 18:40:
[snips]

Kelsey makes the most convincing case I have ever read for
implementations being required to make freed memory available to the
program.

Well, thank you for that, but for some reason consensus seems to be
"Never mind what the standard says, ignore than and do what it means,
instead" - without stopping to realize that the only way we can determine
"what it means" is from "what it says".

No, there is another way. You can raise a DR to query the standards body.
Oh well. Someone, somewhere, other than me might at some point care that
the wording and the intention are completely at odds with each other. I
give up.

Another point is that is does not say that it is made available for
allocation by malloc/calloc/realloc. So if the program uses one byte of
the space that was freed to allocate space for a char variable and thus
does not have the full amount available for allocation with malloc is it
non-conforming? There have been implementations where the stack grows
towards the heap, so it is possible.
 
K

Kenneth Brody

Keith said:
That's not the only way to interpret the black and white wording of
the standard.

free() makes the space "available for further allocation". If the
space is made available for further allocation *by other programs*,
then it's been made available for further allocation.

I believe Kelsey's argument (and I'm sure he'll correct me if I'm
wrong) is that the Standard doesn't acknowledge the existence of
"other programs", and therefore any "further allocation" would by
necessity refer to "the current program".

The problem, as others have pointed out, is the ambiguity of the
statement as worded. If the memory were to be made "available for
further allocation" by "another program", have you violated the
Standard or not?

[...]
Over in comp.std.c, Doug Gywn, a member of the ISO C committee, has
said that memory deallocated by free() can be reclaimed by the OS (you
can find the article for his exact words). I'm not saying his
statement has the force of law, but it does imply something about the
intent. In my opinion, the words of the standard are uncomfortably
ambiguous, but they are consistent with the intent.

I think this is a case for comp.std.c's input, though I am hardly
an expert in such matters.

Now, suppose you were to have a memory manager implementation where
free space is grouped according to the size of the block. For
example, less than 2K, 2K to 4K, 4K to 8K, and so on. When the
free(block_of_60K) call is made, the memory is put in the 32K to
64K pool. Now, further suppose that this memory manager were very
poorly written, such that when malloc(10000) is called, and the
8K to 16K pool is full, it does not bother checking the larger
pools. Finally, suppose that it asks the O/S for more memory and
this call fails.

Is this implementation non-conforming, or is it simply a very poor
(yet still conforming) implementation? After all, the memory has
been made "available for further allocation", as any malloc() in
the 32K to 60K range would have succeeded.

--
+-------------------------+--------------------+-----------------------+
| Kenneth J. Brody | www.hvcomputer.com | #include |
| kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------+
Don't e-mail me at: <mailto:[email protected]>
 
R

Richard Tobin

Kelsey Bjarnason said:
Well, thank you for that, but for some reason consensus seems to be
"Never mind what the standard says, ignore than and do what it means,
instead" - without stopping to realize that the only way we can determine
"what it means" is from "what it says".

No. If that were the case, I doubt you could interpret it at all.
The standard is written in English, and relies on a huge amount of
background knowledge about computers as well as the everyday pragmatic
interpretation of English.

You yourself are using a (rather bizarre) pragmatic rule in your own
interpretation: that because the standard does not acknowledge the
existence of other programs, then we must interpret everything as if
there weren't another program. This rule is doubly wrong: the
standard does acknowledge the existence of other programs (for
example, do you think it would bother providing files otherwise?), and
the inference itself it not justified either by common sense or
explicit wording in the standard.

-- Richard
 
K

Kelsey Bjarnason

[snips]

I believe Kelsey's argument (and I'm sure he'll correct me if I'm wrong)
is that the Standard doesn't acknowledge the existence of "other
programs", and therefore any "further allocation" would by necessity
refer to "the current program".

Exactly. I've said it repeatedly - the only thing in the entire universe
which *can* do "further allocation", as far as the standard is concerned,
*is* the program.
The problem, as others have pointed out, is the ambiguity of the
statement as worded.

No ambiguity at all. The memory is made available for further
allocation: the behaviour is defined. And the entire *purpose* for
defining behaviour? The entire *purpose* for the document? To tell you
what your program can expect and rely upon - in this case, that the
memory is available.
I think this is a case for comp.std.c's input, though I am hardly an
expert in such matters.

He said it; he couldn't thus far show where, in the standard, this
behaviour is allowed.
 
K

Kelsey Bjarnason

No. If that were the case, I doubt you could interpret it at all. The
standard is written in English, and relies on a huge amount of
background knowledge about computers as well as the everyday pragmatic
interpretation of English.

You yourself are using a (rather bizarre) pragmatic rule in your own
interpretation: that because the standard does not acknowledge the
existence of other programs, then we must interpret everything as if
there weren't another program. This rule is doubly wrong: the standard
does acknowledge the existence of other programs (for example, do you
think it would bother providing files otherwise?), and the inference
itself it not justified either by common sense or explicit wording in
the standard.

Picture two boxes. One is labelled "Defining behaviour of a C program",
the other is labelled "everything else". Into which box does the
definition of free go?

If it goes into the first box, then the *defining behaviour of a C
program* is that the memory released by free is available for further
allocation - *by the C program*. Period. That is where and how it is
defined to work.

If it belongs in the other box, that the definition of free does *not*
actually define the behaviour of a C program, then free has no business
being in the standard.

Of course we need something like free, to make C as useful as it is, but
in defining how free operates, we must also remember that we are defining
not just the operation of free, but we are, in fact, creating the entire
operational definition of a C program, free simply being a part of that
definition. Which means that whatever free is defined as doing, applies
in and to the C program. Not to an OS, not to a remote server, not to
Mars, God of War; to the C program.

Free defines a behaviour *for the C program*. Not for those other
things. The defined behaviour is to make the memory available for
further allocation. Thus the memory, by the definition of free, is
available - *to the C program*. Not to the OS, not to a remote server,
not to Mars.

Nor does the standard acknowledge other programs as you assert. Your own
example fails. It does not, for example, define files in any
particularly meaningful way - it does not, for example, tell us that the
file will be stored on a disk rather than on a tape. For all that "file"
is defined, it could cause the data to be read aloud, then re-entered by
a typist on reading it.

Let's use fopen as an example. Fopen can be used to open or create a
"file", and to set certain operational modes such as "binary" mode or
"text" mode. Note, though, that it says nothing at all about what
effects any of this have on the "file" itself; these define the modes of
operation of the C program interacting with that "file".

So take text mode. It tells us nothing of how the data is stored in the
file, nor even what "file" means, other than being some external means of
recording and recalling data. When you write to the file, the standard
does not define how that data gets read or translated nor where the data
is stored; it simply defines the behaviour of the C program: a block of
data written _here_ using _this_ mode should be later readable at that
same place, in that same file, using the same mode, as the same data.
*How* this is accomplished, the standard does not say, nor does it care -
it defines the behaviour of the C program, not of files, file systems,
OSen or other creatures.

So even in your example of files, the C standard does exactly what the C
standard is for - it defines the behaviour of C programs. Not of OSen,
not of remote servers, not of gods of war, no, it defines C programs and
only C programs.

What does free do, again? It releases a portion of previously allocated
space, which is made available for further allocation. And exactly what
can the standard define such a behaviour for? Right, the C program. And
what is the defined behaviour for the C program? That the memory is
available for further allocation.

So. Do we keep free's definition within our "defining behaviour of a C
program" box? Do we toss free out of the standard and move it to the
other box? Do we - as seems to be the argument here - keep free in the C
box, but kinda, sorta, without description, definition, or indeed any
justification, decide to put half of the definition of free into the
other box?

If the latter, well, fine, let's do so. Shall we do so with other
functions, too? Shall we say, for example, that fclose, which we will
presumably agree releases resources, should be allowed to release *all*
resources, up to and including killing the entire program? Is that an
acceptable behaviour? No? But if we're going to randomly toss half our
function definitions into the other box where we have no way to define
expected behaviours, then this would be an acceptable behaviour.

We can go even further. We can note that while we define an operation
such as addition with certain requirements, if half our definitions
belong inside the other box then as far as our code is concerned, 1+1 may
actually equal 17,395 - hey, we can't define what's going on in the other
box, this is a legitimate result.

It's silly, of course, but that's the point: the whole notion of randomly
tossing half our definitions into the other box *is* silly. I am simply
pointing out that we should not do so, cannot afford to do so. Yet if we
don't, then we're left with the obvious conclusion: by the definition of
free, the C program has every right to assume the memory in question is
available, as free *guarantees* this.

If someone wants to give an actual rationale for tossing half our
definitions into the other box, of introducing chaos into our programs,
feel free, I'd love to see the reasoning behind it. Personally, I don't
think it makes much sense to do so; I prefer a standard which actually
defines, as far as possible, predictable and useful behaviour sets. The
C standard, by and large, does this now, but it does so by *not* randomly
tossing things into the other box, it does so by actually defining the
behaviours. In the case of free, it does - it defines it as making the
memory available for further allocation, and it does this in the only
context it can: the context of the C program. The C program thus *has*
the memory available for further allocation; the standard guarantees it.


That said, this will be my last post on the matter. One can only bang
one's head on the wall so long. The standard quite clearly defines a
required behaviour. That behaviour is, also quite clearly, *not* the
intended behaviour - I'm sure we all agree that the memory should, where
possible, be handed back to the OS for whatever purposes it may have. It
simply is not allowed for this to happen, though, under the current
wording.

I suspect this also means there's likely not a conforming implementation
anywhere in the known universe, but that's another matter. We've already
got people arguing for the random switching of "boxes" halfway through
the definition of a function's behaviour; I can hardly see them caring
whether an implementation is conforming or not.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,769
Messages
2,569,581
Members
45,056
Latest member
GlycogenSupporthealth

Latest Threads

Top