Freeing memory - will it be available immediately

[Kelsey Bjarnason]

Kelsey wrote:
) One needs to consider context. The C standard defines the behaviour
of a ) C program, which in turn means it also defines how the standard
library ) functions define _as relates to that C program_.

I believe this is the point of contention.

Oh? The C standard has been extended to defining the behaviour of OSen
and toasters, cars and cabbages? When did this happen? Last I checked,
it defined C, or, more specifically, the behaviour of a C program.

 

[Kelsey Bjarnason]

[snips]

Why do you say that giving the memory back to the operating system is a
"failure to make the memory available for further allocation" ?

I don't. Obviously, if the memory is subsequently allocated by, oh,
notepad, it has been "further allocated".

Again, this is a question of context. In the context of "your computer
as a whole", obviously certain rules apply, and yes, equally obviously,
memory handed to the OS by free could be "further allocated" by some
program such as notepad.

However, the C standard does not define the general operation of a
general computing system, it defines the C language. *In that context* -
the context which is the whole point of the document - it defines how
free operates. It does so, as with all the other things it defines, in a
manner which your C program, written to the standard, is supposed to be
able to rely upon.

Part of the defined behaviour - again, of *C*, and of the program written
in C - is that memory released with free is made available for further
allocation.

Not handed to the OS, where it may be consumed and thus *not* available
for further allocation by the C program whose behaviour is defined by the
standard.

You seem to be making at least two assumptions:

1) That it is not the operating system that is responsible for the
allocation of memory within a running program; and

I make no such assumption. I merely point out that an implementation, to
be conforming according to the definition of free, cannot release the
memory back to the OS, or, if it does, it must do so in some manner which
keeps the memory "reserved" for further allocation by the C program.

2) That memory given back to the operating system will not be available
to the program when the program requests more memory.

It may or may not be; the standard mandates that it *will* be.

It turn, (2) breaks down into several cases:

(2a) that the -exact same- physical memory gets re-allocated by the
operating system in the -exact same- virtual address (2b) that the
-exact same- physical memory gets re-allocated by the operating system
in a -different- virtual address (2c) that -different- physical memory
gets allocated by the operating system into the -exact same- virtual
address as the original allocation (2d) that -different- physical memory
gets allocated by the operating system into a -different- virtual
address

The specific addresses involved are irrelevant; nothing mandates anything
about the addresses involved.

IMHO, the only situation in which it makes a difference as to whether
memory is given back to the operating system or not, is the case in
which the operating system is unable to return to the program as much
memory as was free()'d (e.g., if resources ran low and there was no
longer enough for the program to get back what it once had.)
Exactly.

I could see
that as a potential violation of the wording of the standard, but if the
memory is available again from the operating system for the asking, I
see no violation.

Correct; *if* the memory is available, there's no problem. However, the
implementation cannot guarantee that this will be the case; the OS may
well hand the memory off to some other process. Thus, to be conforming,
the implementation *cannot* hand the memory back to the OS; it must
retain it, reserve it, for further allocation by the program.

I realize this is probably not the *intent* of the definition of free,
but so far the only arguments I've seen against this interpretation
assume that somehow the C standard either does not define the behaviour
of a C program, or that the C standard defines behaviours above and
beyond the scope of the C language. Neither is the case.

 

[Kelsey Bjarnason]

Kelsey wrote:
) Ooh, no, I would *not* want such a setup either. If I free memory, I
) would much rather have it go back into the pool for all applications
to ) use; this strikes me as the most reasonable possible behaviour.
It's ) simply not a behaviour allowed by the standard.

So all you're really saying is that the wording used in the standard is
not quite what it should be.

I *suspect* the intent of "made available for further allocation" is "by
any process which requests it" or some such - i.e. *do* hand it back to
the OS and let it sort out who gets it. The wording, as written, just
doesn't allow this. If that is the intent, the wording is incorrect; if
that's not the intent, if the wording is correct, then I suspect there's
a whole lot of non-conforming implementations out there.

 

[Gordon Burditt]

Is it? I see nothing whatsoever in the definition of free which allows
Nowhere does the standard distinguish between freed memory that is held
by the program vs. memory that has been returned to the OS.

One needs to consider context. The C standard defines the behaviour of a
C program, which in turn means it also defines how the standard library
functions define _as relates to that C program_.

The definition of free says that the memory freed is made available for
further allocation.

Tell me what prohibits this implementation:

One block of physical memory is not distinguishable from another
block. It is not necessary that the same physical memory block be
made available for reallocation, as long as a block to replace it
is. Presuming the implementation has memory-mapping hardware,
contiguity of physical blocks is not an issue, as they can be mapped
to be contiguous in virtual space even if the physical blocks aren't.

A C program may free memory and the implementation may return it
to the OS. The OS may then let a non-C program (or a C program
running in non-standard-compliant mode) have it. If the C program
subsequently wants it back, the OS will _wait until it is available_,
for as long as necessary, then give it back.

Now all I have to do is prove this won't result in deadlocks involving
the C program of interest. The implementation will run only one C
program in standards mode at a time, although that program may run
others with system(). *Other* programs may get refused memory
because of possible deadlock. The C program may get refused memory
if it's asking for more memory than it ever had before. If only
non-C-standard-mode programs and programs not run by C-standard-mode
programs get killed when the system gets bitten by overcommitting
memory, there's no violation of the requirements of the standard.

Thus, in context, it defines, _for the C program_ that the memory remains
available; it cannot, therefore, hand it back to the OS, as the memory
would then _not_ be available for further allocation.

Yes, it would, if it's possible to eventually get it back, regardless
of how long it takes, as long as it's less than infinite time.

 

[Gordon Burditt]

Correct; *if* the memory is available, there's no problem. However, the

implementation cannot guarantee that this will be the case; the OS may
well hand the memory off to some other process.

There's nothing wrong with that unless the memory is handed off to
some other process *PERMANENTLY*. And since one freshly-allocated
block of memory is indistinguishable from another, to get into
trouble you need growing processes that run forever, or deadlock.

Thus, to be conforming,
the implementation *cannot* hand the memory back to the OS; it must
retain it, reserve it, for further allocation by the program.

No, if the C program wants it back, the OS can simply wait until
the memory is available again. If the OS only runs one program in
C standard mode at a time, then it can kill other (non-C-standard)
processes to get back memory if needed and it decides there's a
possible deadlock.

 

[Gordon Burditt]

I *suspect* the intent of "made available for further allocation" is "by

any process which requests it" or some such - i.e. *do* hand it back to
the OS and let it sort out who gets it.

Suppose for the moment that it really does mean "made available for
further allocation by *THIS* program", but it does not mean "made
available for further *immediate* allocation by *THIS* program".
If the memory is not now available, WAIT UNTIL IT IS.

(and if you hit a deadlock, the C-standard-mode program isn't the one
to get killed or have malloc() fail).

The wording, as written, just
doesn't allow this.

Yes, it does. Wait for the other program that got the memory to
finish, then give it to the C program of concern. There is nothing
in the standard that says that malloc() can't take years to get the
memory back.

If that is the intent, the wording is incorrect; if
that's not the intent, if the wording is correct, then I suspect there's
a whole lot of non-conforming implementations out there.

There probably are. And you probably have to limit the system to
running at most one C-standard-mode program and an arbitrary number
of non-C-standard-mode programs simultaneously.

 

[Kelsey Bjarnason]

[snips]

Show us where the standard says that an implementation in which storage
deallocated by free() is made available for further allocation by
another program invoked via the standard system() function would be
non-conforming.

I'll turn that around: where in the definition of, say, the pre-increment
operator as applied to a variable of type int, does it say that if the
variable's value before increment was 3 and the value after increment is
19,471, the implementation is non-conforming? Now try again, but for
values of 97 before and 65 after.

Right; there's no such definition. Doesn't exist. There's a reason for
this; it's pointless.

What matters is not that there is a clause for every possible case, but
that there is a rule, or set of rules, for determining what to expect.
There is; the standard goes to some length to differentiate between
defined, undefined, unspecified and implementation defined behaviours,
with the assumption the reader will apply those rules when determining
the implications of the rest of the document.

Thus, for example, one need not have a specific clause which disallows
the pre-increment operator to produce a result of 19,471 from a previous
value of 3; it is sufficient to have a definition of how pre-increment is
defined to work, plus the rules for determining what to expect: the
behaviour is defined _thus_, any implementation which does otherwise is
non-conforming.

Therefore, by defining a behaviour for free, the standard defines what
free is expected to do, how it is expected to behave. The up-front rules
about interpreting the behaviour do not need to expressly disallow the
case you mention, as the defined behaviour of free does not include such
a case *nor* does it include any allowance for implementation-defined
behaviour or the like; it behaves as documented, or the implementation
fails to meet the requirements of the standard and thus is non-conforming.

And what *is* the defined behaviour? Right - to make the memory
available for further allocation.

Ah, but wait. To *whom* does it define this behaviour? Is the C
standard suddenly the defining document for POSIX-based OSen? How about
non-POSIX-based OSen? How about process management in general? Cars?
Toaster ovens?

Nope, none of these apply. The behaviour defined is the contract between
implementation and developer, in the context of writing C programs to be
used in conjunction with a C implementation. That is *it*. No OSen, no
cars, no toaster ovens, just C, all C, nothing but C.

And what is the defined behaviour granted by the standard to the C
programmer using a conforming implementation? Right - that the memory is
made available for further allocation.

Not handed to the OS. Not handed to another process; the standard does
not define these things, in fact goes to some pains to avoid the whole
concept of these things. No, the context is the C program, and the
behaviour is clearly defined, without so much as an "implementation
defined" to even allow any other behaviour.

Where in the standard does it decree the case you mention is non-
conforming? In the definition of free, which defines the behaviour, and
the definition of the rules which determine whether an implementation is
conforming or not: if it fails to provide the defined behaviour, it is
non-conforming, the behaviour here is defined, the case cited involves
behaviour *other* than what is defined, voila; the implementation is non-
conforming.

Unless, that is, you can point out where, exactly, in the definition of
free it allows for an implementation-defined behaviour such as *not*
making the memory available for further allocation, as is required by the
wording.

 

[Micah Cowan]

Is it? I see nothing whatsoever in the definition of free which allows
for any implementation-defined behaviour; its behaviour, quite the
contrary, is absolutely and clearly defined, and *does not permit*
handing the memory back to the OS.

Those who didn't follow the recent thread on the subject should note
that this is merely a theory recently advanced by Kelsey[/QUOTE]

This is not an accurate statement, in that the theory is neither
recent, nor
original to Kelsey. While watching this thread, I've had the
very strong feeling that I'd seen Kelsey's argument before, and that
it was
accepted by respected regulars to this list (which was why I was
somewhat
surprised to find it largely spurned by the same).

It appears I'm right: Lawrence Kirby and Dan Pop both held this
opinion, or at
least held it to be quite credible. The standards committee was asked
about it,
and the reply was that returning memory to the system is permitted:

http://groups.google.com/group/comp.std.c/browse_thread/thread/930b55c2892df2f1/8510e07d4d24034d

For my part, I believe I quite agree with Pop's summary of the
situation:

From http://groups.google.com/group/comp.lang.c/msg/8c93163a9fa6033d :

Indeed (and I thought, for years, that such an implementation would be
non-conforming). Unfortunately, the committee members didn't mean "made
available for further allocation" when they wrote "made available
for further allocation". Don't ask me what they actually meant ;-(

Lawrence Kirby also has something to say about it, way back in 1996:
http://groups.google.com/group/comp.lang.c/msg/5f56cb7e08d330f9

(Back to Richard Tobin):

it does not
reflect any consensus on the subject; it is contrary to previous
interpretation of the standard; and at most implies the need for a
correction to the standard, rather than having any implication for
users or implementors of C.

All of these, in light of the above, appear to remain accurate. While
we may
lament the rather poor wording of the Standard, perhaps given that the
committee
has clarified the matter, we can let it drop?

 

[Micah Cowan]

This is not an accurate statement, in that the theory is neither
recent, nor
original to Kelsey. While watching this thread, I've had the
very strong feeling that I'd seen Kelsey's argument before, and that
it was
accepted by respected regulars to this list (which was why I was
somewhat
surprised to find it largely spurned by the same).

Arg. Apologies for the nasty formatting. I guess I wasn't confident that
Google would break my lines, so I did it by hand, which was apparently
shooting myself in the foot.

 

[user923005]

Arg. Apologies for the nasty formatting. I guess I wasn't confident that
Google would break my lines, so I did it by hand, which was apparently
shooting myself in the foot.

The links you provided are adequate proof that even experts are not
agreed on as to the definite meaning of the wording.

I think that the DR should have been followed through. After all,
here we are in a big debate again over the same thing.

I guess that three years hence we will see another cycle. When it is
something as important as "How does this computer language work?" it
seems to me that we should make it totally unambiguous.

IMO-YMMV

 

[Micah Cowan]

The links you provided are adequate proof that even experts are not
agreed on as to the definite meaning of the wording.

I think that the DR should have been followed through. After all,
here we are in a big debate again over the same thing.

I guess that three years hence we will see another cycle. When it is
something as important as "How does this computer language work?" it
seems to me that we should make it totally unambiguous.

Well, given that my system, a commonly-used development platform,
violates the standard's guarantees wrt allocated memory in a rather more
egregious way - namely, to allow malloc() to return a pointer, and then
decide later, upon that pointer's use, whether it should actually make
memory available through that pointer or simply kill the process for
attempting to use a "valid" pointer... the text of the standard in this
matter ends up not distressing me too much, given that, any way you look
at it, my implementation's busted.

(I'm speaking, of course, of Linux's OOM killer.)

Still, yeah, seems like it should be addressed. By someone other than
me, of course - I'm too lazy.

 

[Walter Roberson]

On Tue, 26 Feb 2008 18:31:45 +0000, Walter Roberson wrote:

I make no such assumption. I merely point out that an implementation, to
be conforming according to the definition of free, cannot release the
memory back to the OS, or, if it does, it must do so in some manner which
keeps the memory "reserved" for further allocation by the C program.

If the implementation relies upon the operating system to manage
memory, then releasing the memory back to the OS would be the proper
thing to do for that implementation. After all, if the implementation
relies upon the operating system to manage memory and it does -not-
release the memory back to the operating system, then the operating
system is not going to be allocate that memory to the program in
response to a further malloc()/calloc() call, since the operating
system will not know that the memory is free. Thus if the
implementation does not have a memory allocator that is independant
of the OS (and there is no requirement that it does) then your
interpretation (that memory is never released back to the OS) would
render the implementation non-conformant.

 

[ymuntyan]

[snips]

Show us where the standard says that an implementation in which storage
deallocated by free() is made available for further allocation by
another program invoked via the standard system() function would be
non-conforming.

I'll turn that around: where in the definition of, say, the pre-increment
operator as applied to a variable of type int, does it say that if the
variable's value before increment was 3 and the value after increment is
19,471, the implementation is non-conforming? Now try again, but for
values of 97 before and 65 after.

Right; there's no such definition. Doesn't exist. There's a reason for
this; it's pointless.

What matters is not that there is a clause for every possible case, but
that there is a rule, or set of rules, for determining what to expect.
There is; the standard goes to some length to differentiate between
defined, undefined, unspecified and implementation defined behaviours,
with the assumption the reader will apply those rules when determining
the implications of the rest of the document.

Thus, for example, one need not have a specific clause which disallows
the pre-increment operator to produce a result of 19,471 from a previous
value of 3; it is sufficient to have a definition of how pre-increment is
defined to work, plus the rules for determining what to expect: the
behaviour is defined _thus_, any implementation which does otherwise is
non-conforming.

Therefore, by defining a behaviour for free, the standard defines what
free is expected to do, how it is expected to behave. The up-front rules
about interpreting the behaviour do not need to expressly disallow the
case you mention, as the defined behaviour of free does not include such
a case *nor* does it include any allowance for implementation-defined
behaviour or the like; it behaves as documented, or the implementation
fails to meet the requirements of the standard and thus is non-conforming.

And what *is* the defined behaviour? Right - to make the memory
available for further allocation.

Ah, but wait. To *whom* does it define this behaviour? Is the C
standard suddenly the defining document for POSIX-based OSen? How about
non-POSIX-based OSen? How about process management in general? Cars?
Toaster ovens?

Nope, none of these apply. The behaviour defined is the contract between
implementation and developer, in the context of writing C programs to be
used in conjunction with a C implementation. That is *it*. No OSen, no
cars, no toaster ovens, just C, all C, nothing but C.

And what is the defined behaviour granted by the standard to the C
programmer using a conforming implementation? Right - that the memory is
made available for further allocation.

If two subsequent malloc() calls never succeed (both of them, that
is), is it a conforming implementation? "Further allocations" are
fine, it's just the very next that doesn't work. And to break the
Dan Pop's example: two subsequent malloc() calls do not succeed
if they have the same argument. And now the "as if" rule kicks in.

To make it easier for you, here's a simpler example:
objects are stored in toasters which are delivered to the
program in cars when it calls malloc(), and are carried
away when the program calls free(). The toasters are
of different size and shape, and if one is being carried
away, it can't be returned until it's been delivered back
to the toasters store. But they are "available" for further
allocation. For further allocation at some point later,
that is. Can you quote the standard saying such an
implementation would be non-conforming?

You make an important assumption here, that an implementation
must behave as conventional implementation do (at least
for small N, since conventional implementations do not actually
always behave this way): the sequence p = malloc(N); free(p);
*immediately* returns the program to its original state as it
was before the malloc() call. But the standard doesn't demand
that, does it?

Yevgen

 

[santosh]

Herbert Rosenau wrote:

So, look on:

1 mashine will run only one single program. This single program
(commonly known as operation system) loads many different extensions -
you sees them as differen programs, but they are nothing else than
plugins like modern browsers use to extend theyr abilities.

This isn't true for microkernel based systems and those with
virtualisation.

<snip>

 

[Richard Bos]

If I'm wrong, please point out the clause which allows the defined
behaviour to work other than as the standard defines it

There is none. Your interpretation of "as the standard defines it" is
wrong.

Richard

 

[Kelsey Bjarnason]

[snips]

Tell me what prohibits this implementation:

[irrelevances snipped]

A C program may free memory and the implementation may return it to the
OS. The OS may then let a non-C program (or a C program running in
non-standard-compliant mode)

Non-conforming mode? Yes, well, you just answered your question: you're
using a non-conforming implementation, which means it's either broken, or
non-conforming by intent; if the former, file a bug report. If the
latter, consider it a QoI issue.

 

[Kelsey Bjarnason]

There is none. Your interpretation of "as the standard defines it" is
wrong.

You keep saying that, why is it you seem unable to demonstrate it?

 

[Kelsey Bjarnason]

[snips]

If two subsequent malloc() calls never succeed (both of them, that is),
is it a conforming implementation?

We cannot tell from this.

"Further allocations" are fine, it's
just the very next that doesn't work. And to break the Dan Pop's
example: two subsequent malloc() calls do not succeed if they have the
same argument. And now the "as if" rule kicks in.

void *ptra = malloc(100);
void *ptrb = malloc(100);

You're saying that if either allocation fails, there's a problem? Aside
from the simple lack of available memory, what, exactly, is the problem?

To make it easier for you, here's a simpler example: objects are stored
in toasters which are delivered to the program in cars when it calls
malloc(), and are carried away when the program calls free().

No, they're not; if this occurred, the implementation cannot meet the
behaviour mandated by the definition of free, as the car may not return.
Thus the objects - the blocks of memory - are not allowed to be carried
away when free is called.

further allocation at some point later, that is. Can you quote the
standard saying such an implementation would be non-conforming?

I can point out that the implementation does not know how many toasters
are at the toaster store, thus it cannot guarantee there are - or ever
will be - enough to meet the requests, therefore it has no choice, under
the wording of the standard but to store them itself.

The definition of free says *nothing* about the memory being made
available for later allocation *if available* or *if not consumed by some
other process*. There is zero - *zero* - allowance in the wording for
any wiggle room whatsoever.

You make an important assumption here, that an implementation must
behave as conventional implementation do (at least for small N, since
conventional implementations do not actually always behave this way):
the sequence p = malloc(N); free(p); *immediately* returns the program
to its original state as it was before the malloc() call. But the
standard doesn't demand that, does it?

I make no such assumption, and nothing I've said thus far requires such
an assumption. The standard says the memory is made available for
further allocation, it does not say when - it could be next Tuesday.

The point at hand is that once a piece of memory has been allocated by
the program, free cannot release it back to the OS, because, even if the
implementation's memory management is so inefficient it cannot make the
memory available for further allocation until Tuesday, it nevertheless is
required to do so, while handing the memory back to the OS means it
cannot ensure that it meets the requirements of the standard, no matter
how inefficiently.

 

[Kelsey Bjarnason]

There's nothing wrong with that unless the memory is handed off to some
other process *PERMANENTLY*.

Which it may well be. Since the implementation is *required* to make the
memory available for further allocation, it cannot therefore rely on the
OS which may well hand that memory off to something else until the end of
time.

No, if the C program wants it back, the OS can simply wait until the
memory is available again.

Which it may never be, thus violating the requirements of the standard.

 

[Kelsey Bjarnason]

If the implementation relies upon the operating system to manage memory,
then releasing the memory back to the OS would be the proper thing to do
for that implementation.

Careful, "proper" here is the very issue of contention.

You and I (presumably) think that "proper" behaviour is that if memory is
freed, it should go back to the OS to be used by whatever may need
memory; this is certainly the desirable operation, especially in a
multitasking environment.

However, "proper" behaviour as defined by the standard is that the memory
is made available for further allocation, in the context of defining the
behaviour of a C program and the libraries upon which it depends - thus
"proper" is that it can only hand the memory back to the OS if the
implementation can guarantee the memory will, in fact, be available for
later allocation, something which, in the general case, it cannot
guarantee. Thus "proper" here mandates that the implementation _not_
return the memory back to the OS.

After all, if the implementation relies upon
the operating system to manage memory and it does -not- release the
memory back to the operating system, then the operating system is not
going to be allocate that memory to the program in response to a further
malloc()/calloc() call, since the operating system will not know that
the memory is free.

This is an implementation detail. There's nothing to prevent an
implementation using OS services to allocate blocks of memory, then using
its own memory manager to handle subsequent reallocations. The same sort
of thing is sometimes done when the provided allocator is known to be
excessively slow; rather that constantly calling it, the application
instead retains the allocated memory, doling out portions as needed,
going back to the OS only when the previously allocated pool is empty.
This is the same sort of thing, just the implementation doing it.

Put it this way. Suppose the first thing I do on program startup is to
allocate 100MB of memory. I immediately free the memory. The
implementation, knowing that the OS's allocation system is painfully
slow, does *not* give the 100MB back to the OS, it keeps it reserved for
itself. A later allocation - say of 1MB - comes from the previously
allocated pool, quickly and efficiently. When the pool is exhausted,
then the implementation goes back to the OS for more.

The OS need not know the 100MB was ever freed; indeed, as far as it's
concerned, it wasn't freed.

All of which, however, is essentially beside the point - implementation
details. However the implementation does it, as long as it ensures the
memory *is* available, all's good. In the general case, this means it
cannot ever return the memory back to the OS, as there's no way to tag
the memory as "reserved for this program", but again, it's an
implementation detail.