Does ANSI C allow free() to always be empty?

[glen herrmannsfeldt]

On Monday, March 10, 2014 5:43:18 AM UTC-7, Martin Shobe wrote:
(snip)
(snip)

But, the question that I am asking is whether free is allowed to
not deallocate memory. The person who prompted me to ask this
question in the first place claimed that because the program in
question could not, using only the semantics of the C Abstract
machine, determine whether free() had done anything, and therefore,
free() need not do anything, even if it meant a massive memory
leak on a program which did appropriately call free() for all
memory it allocated.

and the standard leaves the amount of available memory up to the
implementation, and often on whatever else the machine is doing
at the time.

I have two issues with saying that deallocation can be delayed.
One is that the standard says that all side effects must be
completed before the last sequence point of a full expression.
Thus, for the side effect of free to be delayed seems outside
of the standard.

As far as I know, that is for side effects visible to the program.

Note that printf() has the side effect of printing something somewhere,
such as a terminal or line printer, but that effect usually happens
much later, if ever.

Secondly, the standard does say that free() makes the space
available for further allocation. However, if the implementation
for example delayed freeing until it ran out of memory then freed
on demand, (Android style LOL) then, for all practical purposes,
all calls to free() would have the same effect as if free had
fully freed within its own sequence points.

However, I do not see the letter or the spirit of the standard
allowing free() to have a delayed effect. Obviously, malloc() is
not allowed to postpone its creation of an object otherwise
immediate use of that object would be bad.

Seems that many systems now have lazy allocation, also known as
overcommit, where malloc() never returns NULL. Similar to the way
airlines overbook expecting some no-shows, lazy allocation assumes
that you malloc() more than you really need.

allocating and deallocating are the same class of side effects.

On many systems, the available memory depends on what other programs
are using, so the side effects of malloc() and free() are, to some
extent, outside the control of the program. Seems to me that makes
them different.

-- glen

 

[David Brown]

Yes. I think there are some restrictions about what the library

facilities should do, even in a freestanding environment - but you
don't

need to implement everything. In particular, a freestanding

implementation does not have to include <stdlib.h>.



As far as I read the wording in the C11 standards, a conforming
hosted

implementation /could/ have malloc() always return 0, and free() be
empty.

Could you explain which part of C11 would allow malloc() to always
return 0 and free() to be empty?


I see in the standard:

5.1.2.2 [Hosted environment]

1 A hosted environment need not be provided, but shall conform to
the following specifications if present.

then the description of malloc() and free() are below that at 7.22.3
[Memory management functions].


Doesn't that look like a hosted environment shall conform if
present?

(At first when I read 5.1.2.2, I thought it meant that the following
functions were optional in a hosted environment, but that any
function present must conform. However, it really looks like the
wording says that if a hosted environment is provided, it shall
conform to all of the following specifications.)

And the description of malloc() and friends clearly all describe a
general effort to allocate, and "7.22.3 [Memory management
functions]" says "The pointer returned if the allocation succeeds is
suitably aligned so that it may be ...."

Notice "if the allocation succeeds." One cannot have the chance to
succeed if they do not attempt, and simply returning NULL is not
attempting anything.

Also, realloc uses both the phrases "If memory for the new object
cannot be allocated," and "or a null pointer if the new object could
not be allocated."

I really don't see how the standard allows for malloc to simply
return NULL without attempting to allocate.

Under 7.22.3.4:

"The malloc function returns either a null pointer or a pointer to the
allocated space."


I believe that this can be interpreted as allowing malloc() to return a
null pointer for every invocation.

Of course, such an implementation would be useless, and a toolchain that
had such an implementation would be unpopular. And I don't think the
standards document intended such an "implementation" to be considered
conforming - but I think the language of the standard allows it.


It is also worth noting that there is no way (with just the
standard-required library) for a program to distinguish between an
"always null" malloc() and a real malloc that cannot allocate the memory
that was asked for. Similarly, there is no way for a program to
distinguish between an empty free() and one that does useful work.

 

[Martin Shobe]

On 3/10/2014 12:28 AM, (e-mail address removed) wrote:

There is a very strong wording for free that it is to free the space for further allocation. That can't be ignored.

But is the wording strong enough to require that a subsequent malloc(1),

or similar, actually succeed? If it's not, then the "as-if" rule would

apply, and you can have free() do nothing.



[snip]



Martin Shobe

Could you expound on the "as-if" rule (or reference standard section)?

Take a look at 5.1.2.3.1, 5.1.2.3.4, and 5.1.2.3.6 in N1570. Part of
5.1.2.3.4 says that side-effects can be omitted if they aren't needed.
5.1.2.3.6 tells you what's needed.

Martin Shobe

 

[partremmaps]

On 3/10/2014 10:55 PM, (e-mail address removed) wrote:





Take a look at 5.1.2.3.1, 5.1.2.3.4, and 5.1.2.3.6 in N1570. Part of

5.1.2.3.4 says that side-effects can be omitted if they aren't needed.

5.1.2.3.6 tells you what's needed.



Martin Shobe

Thanks Martin.

5.1.2.3.1p4 reads:
4 In the abstract machine, all expressions are evaluated as specified by the semantics. An
actual implementation need not evaluate part of an expression if it candeduce that its
value is not used and that no needed side effects are produced


There is a difference between saying that the evaluation of an expression may be skipped if the implementation can deduce that there is no need, and saying that it may skip anything if it can't prove the need for it.

It's hard to word.

But let me try again:

The standard says that the evaluation of an expression need not take place IF it can deduce that there's no need. However, by default, if it cannot deduce whether or not there is a need, then it must evaluate the expression.

Thus, if the implementation can deduce that a given call to free() would not free anything, then by all means optimize it out. However, the question is about a case where free() in a hosted environment is passed as an argument a pointed to valid space earlier allocated by malloc().


It would sort of be OK to say that if the implementation could deduce that the current program and no other program would ever need the memory, that it need not be freed.

But, since the implementation cannot know the future of other programs thenit seems to me that it must not fail to free memory as described.


It is true that 5.1.2.3.1p6 does not list any memory allocation stuff but it is only a very brief listing of the minimum requirements.

I don't think that's a good argument that free may therefore be empty and neglect to free memory, if we take 5.1.2.3.1p6 to mean that, then would it not also mean that the vast majority of the standard was also not required to be complied with?

For a hosted environment (See 5.1.2.2p1), the implementation "shall conformto the following specifications." And one of those following specifications is the specification of how free() works.

I'm not saying that 5.1.2.3.1p6 is not a requirement, but that it is not the only requirement for a hosted system.




I don't know if I dare try an analogy.

But let's say the boss says "Jesse, go to the back and get box of oranges."
I might say "Sir, I was just back there 30 seconds ago to get Apples and weare out or oranges."

If what I said is true, then that's a fine form of optimization.

However, if I had not been back there recently and did not actually know whether we had more oranges, (Or even if I did know we had more oranges) but if I knew that I had the only key to the back, I could tell the boss that we did not have oranges because I knew he had no way of knowing whether it was true. See the difference?

I am likening the user's program code to the boss, and the implementation to the worker.

There is a difference between knowing that a step can be skipped with no change in outcome, and allowing a change in outcome because it can be hidden from the program.

Or do you really think the standard's authors intended for the standard to not require free() to ever actually free memory, for all practical purposes?

Thanks,

~Jesse

 

[partremmaps]

On Tuesday, March 11, 2014 4:52:39 AM UTC-7, David Brown wrote:

Under 7.22.3.4:



"The malloc function returns either a null pointer or a pointer to the

allocated space."





I believe that this can be interpreted as allowing malloc() to return a

null pointer for every invocation.

If that were the whole story, then I would completely agree. All it says is that it does one or the other - a pointer to allocated space or NULL.

However, it is important to note that not every paragraph provides all supporting context for itself. Most paragraph's rely on intention and context from previous paragraphs.

For example, in 7.22.3 [Memory management functions] there is general information that provides context to all of the memory management functions.
It clearly uses the phrase "The pointer returned if the allocation succeeds is..." and "If the space cannot be allocated, a null pointer is returned."

One cannot succeed with out attempting. And notice the very explicit sentence "If the space cannot be allocated, a null pointer is returned."

Furthermore, [The realloc function] specifically uses the phrase "... or a null pointer if the new object could not be allocated."

Now technically, the section specific to malloc() does not specify under what circumstances malloc() is to return NULL or a valid pointer to space.

Again, technically speaking, the standard says that if the space cannot be allocated, then it returns NULL. However, you could say that it doesn't say that realloc can't also return NULL on success.

Now we have to realize that any two or three words taken out of context from a massive document can be made to say just about anything one wants, including claims which are completely contrary to the purpose and meaning of that document.

When we read the standard's section on malloc(), we must also read the standard's section on Memory managed functions.

Any construing of the standard in a way that contradicts the obvious intent and wording seems improper to me.

Of course, such an implementation would be useless, and a toolchain that

had such an implementation would be unpopular. And I don't think the

standards document intended such an "implementation" to be considered

conforming - but I think the language of the standard allows it.

So the authors of the standards document failed to make themselves clear?

To me it looks more like the idea that the "language that allows" free to be no-op is actually missing language that doesn't prevent it.

100% of the language that IS there completely describes free() as performing the described act of freeing memory.

What would the standard have to say? Currently it says that free frees memory. Do they need to add a note to every sentence that says "Note: This means what it says. Free actually must free memory to be compliant."?

It is also worth noting that there is no way (with just the

standard-required library) for a program to distinguish between an

"always null" malloc() and a real malloc that cannot allocate the memory

that was asked for. Similarly, there is no way for a program to

distinguish between an empty free() and one that does useful work.

I see noplace in the standard where a requested action can be skipped just because the result of that cannot be tested from within the program.

The whole point of optimization is that the program still do what it was written to do according to the functions in the standard.

And from the context standard's description of malloc() and free() is that it allows memory to be allocated and freed then reallocated again.



Am I thoroughly confused? Do I not understand the standard's intention or purpose? What am I lacking?


Thank you very much,

~Jesse

 

[David Brown]

On Tuesday, March 11, 2014 4:52:39 AM UTC-7, David Brown wrote:

I see noplace in the standard where a requested action can be skipped
just because the result of that cannot be tested from within the
program.

The action of the program is determined by its observable results - if
you cannot confirm that the malloc() implementation is doing something
non-conforming, then you cannot claim that it /is/ non-conforming.

The whole point of optimization is that the program still do what it
was written to do according to the functions in the standard.

True, but not relevant.

And from the context standard's description of malloc() and free() is
that it allows memory to be allocated and freed then reallocated
again.

That is the intention - and any C library will implement it this way if
people are going to use it (except perhaps for very special cases). I
just don't think the wording of the C standard actually requires this
behaviour in order to be conforming.

Am I thoroughly confused? Do I not understand the standard's
intention or purpose? What am I lacking?

I don't know whether you are confused or not - but if you have to ask
the question, then I guess you are!

However, I cannot say here that /I/ am right and /you/ are wrong. This
is just my reading of words of the standard - it has no more authority
than /your/ reading (and certainly less authority than the opinions of
others in this group who have been "language lawyers" for decades). So
you must feel entirely free to reject my opinion here if you don't agree
with it. I am just trying to give you ideas based to what I hope was a
hypothetical question.

 

[Martin Shobe]

Thanks Martin.

5.1.2.3.1p4 reads:
4 In the abstract machine, all expressions are evaluated as specified by the semantics. An
actual implementation need not evaluate part of an expression if it can deduce that its
value is not used and that no needed side effects are produced

I'm going to assume you meant 5.1.2.3p4 (or 5.1.2.3.4 as I put it) here
instead of 5.1.2.3.1p4 which N1570 doesn't have.

The key phrase here is "needed side effects". So, what exactly are the
"needed side effect". That is detailed in 5.1.2.3p6.

There is a difference between saying that the evaluation of an expression may be skipped if the implementation can deduce that there is no need, and saying that it may skip anything if it can't prove the need for it.

That's a straw man. I didn't say it could skip something if it couldn't
prove a need for it. It is indeed required to prove that the
side-effects of free() isn't needed for that implementation, and I've
never disputed that. However, that isn't enough to rule out that free()
can be implemented as a no-op.

It's hard to word.

But let me try again:

The standard says that the evaluation of an expression need not take place IF it can deduce that there's no need. However, by default, if it cannot deduce whether or not there is a need, then it must evaluate the expression.

Or something that produces the same observable behavior as that
expression in the context it appears in.

Thus, if the implementation can deduce that a given call to free() would not free anything, then by all means optimize it out. However, the question is about a case where free() in a hosted environment is passed as an argument a pointed to valid space earlier allocated by malloc().

It would sort of be OK to say that if the implementation could deduce that the current program and no other program would ever need the memory, that it need not be freed.

Just the current program, C doesn't place any restrictions at all on how
more than one program interacts.

But, since the implementation cannot know the future of other programs then it seems to me that it must not fail to free memory as described.


It is true that 5.1.2.3.1p6 does not list any memory allocation stuff but it is only a very brief listing of the minimum requirements.

It's a listing of what behavior must be preserved between the abstract
machine and the actual implementation.

I don't think that's a good argument that free may therefore be empty and neglect to free memory, if we take 5.1.2.3.1p6 to mean that, then would it not also mean that the vast majority of the standard was also not required to be complied with?

Compliance is still required, but the standard isn't as strict as you
seem to think.

For a hosted environment (See 5.1.2.2p1), the implementation "shall conform to the following specifications." And one of those following specifications is the specification of how free() works.

I'm not saying that 5.1.2.3.1p6 is not a requirement, but that it is not the only requirement for a hosted system.

[snip analogy]

There is a difference between knowing that a step can be skipped with no change in outcome, and allowing a change in outcome because it can be hidden from the program.

Or do you really think the standard's authors intended for the standard to not require free() to ever actually free memory, for all practical purposes?

Of course not, and I've even said that. However, I've also said that
it's ok for free() to be implemented as a no-op. Those aren't mutually
exclusive positions.

Martin Shobe

 

[James Kuyper]

On 03/12/2014 09:09 AM, Martin Shobe wrote:
....

I'm going to assume you meant 5.1.2.3p4 (or 5.1.2.3.4 as I put it) here

That's not a good idea. For example, 5.2.1p2 and 5.2.1.2 refer to two
different things. If you change the 'p' to a '.', you discard the
ability to distinguish between them.

 

[partremmaps]

According to the ANSI C Standard, may free() be an empty function?




Their reasoning is thus:



"Because the C program cannot, using only semantics of the C Abstract Machine, determine that free() did nothing, it is therefore compliant for free() to do nothing even though it was passed a pointer to valid allocated space having earlier been allocated by malloc()."



and



"On a system where malloc and free are fully supported by hardware and software, free() still may be void and empty and always do nothing while still being ANSI C compliant because free() never has a measurable effect, so nothing need be done to produce a measurable effect."

<snip>



This discussion has been most fascinating to me because I sort of expected that several thinking people would look at the same evidence (the written standard) and come to pretty close the same conclusion.

My desire for some level of agreement is that as long as we seem to disagree it means some of us don't understand the topic, and chances are that it's me since by far I'm sure you're all smarter than I. However, I'm trying my very best to understand the standard and it generally makes sense, and yet the conclusion I arrive at seems different.

Putting aside technical wording traps,

Do we at least agree that it is most likely that the standard authors did fully intend (for a hosted environment) for malloc() and friends to allocateif they can, and for free() to free the pointed to memory further allocation?

One of you did make reference to the phrase "language lawyer" which did getme to thinking: In a court of law, it is not uncommon for a lawyer to bearheavily on some fine technical detail or specific word or even the absentsof a specific word the law in order to construe the law in such a way thatany commoner would see as the exact opposite of what the law was actually intended to cover, and even contrary to the bulk of the wording of the law.

But I don't see why anyone would be motivated to do that with the C standard - it's not like someone goes to jail on a technical reading of C11!
*bang bang* "I hereby find the accused guilty of allocating more memory than was available and sentence him to 30 seconds of trying to use swapspace for ram..."


Anyway, I can't really think of any particular answer to this perplexing question so shall probably soon cease from bothering ya'll.
(I obviously may respond further - but I just don't see there being much more to say on the topic.)


But do let me sincerely thank you for trying to help me understand!


~Jesse


PS: I would have posted this sooner but my newsreader was having issues.

 

[Kaz Kylheku]

My desire for some level of agreement is that as long as we seem to disagree
it means some of us don't understand the topic, and chances are that it's me
since by far I'm sure you're all smarter than I. However, I'm trying my very
best to understand the standard and it generally makes sense, and yet the
conclusion I arrive at seems different.

It is not enough to understand the standrad, but to understand what and who the
standard is for and how it can be put to use.

The standard is ideally suited to one thing: describing the behavior of features.

The standard is less suited to dictating what is actually present or not.

If a free function does nothing, it's basically a matter of word semantics
whether that situation is a case of something missing or a something deviating
from specified behavior.

Users and implementors can negotiate with each other that it is okay not to
have a fully working free function.

People can take the standard and customize it how they see fit, to interpret
how they see fit and and also to prioritize the requirements.

Putting aside technical wording traps,

Do we at least agree that it is most likely that the standard authors did
fully intend (for a hosted environment) for malloc() and friends to allocate
if they can, and for free() to free the pointed to memory further allocation?

This is obviously what the function is for.

For instance, it would probaby not be acceptable for free to be implemented,
but to have some side effect which is completely different from freeing memory
that came from {ma,ca,re}alloc. Like, say, closing all stdio streams.

Doing such things would interfere with some correct programs which call free in
a proper way.

Even if some implementors duck out of implementing free, and their users
accept that, the standard's job remains giving a description of free when
it is implemented in earnest.

 

[glen herrmannsfeldt]

(e-mail address removed) wrote:

(snip)

Do we at least agree that it is most likely that the standard
authors did fully intend (for a hosted environment) for malloc()
and friends to allocate if they can, and for free() to free the
pointed to memory further allocation?

(snip)

As defined by K&R, it was intended for smaller machines without
garbage collection. Some other languages popular on those machines
provided no dynamic allocation at all.

Now, by the time that the ANSI standard was written, machines were
getting larger, and garbage collection was known, though maybe not
so efficient. Even though machines were larger, they weren't so large
that you could ignore memory usage and not so fast that you could
ignore efficiency.

We now have many languages designed to be interpreted, and to allow
the user not to have to worry about memory usage. (Mathematica,
R, Matlab, to name a few). C isn't one of them. Presumably one
could write a C interpreter, but it isn't usual.

-- glen

 

[Tim Rentsch]

This discussion has been most fascinating to me because I sort of
expected that several thinking people would look at the same
evidence (the written standard) and come to pretty close the same
conclusion.

My desire for some level of agreement is that as long as we seem
to disagree it means some of us don't understand the topic, and
chances are that it's me since by far I'm sure you're all smarter
than I. However, I'm trying my very best to understand the
standard and it generally makes sense, and yet the conclusion I
arrive at seems different.

Putting aside technical wording traps,

Do we at least agree that it is most likely that the standard
authors did fully intend (for a hosted environment) for malloc()
and friends to allocate if they can, and for free() to free the
pointed to memory further allocation?

I'd like to offer a different kind of answer, in hopes of getting
at what I think it the real underlying issue here.

How you're thinking about the question is off in an essential
way, namely, you think the Standard is meant to address the
question you're asking, whereas it really isn't. The authors of
the C standard (IIANM going all the way back to the original ANSI
committee) made a conscious choice /not/ to address questions
regarding "quality of implementation" but only hard-edged
questions with yes/no answers. Furthermore whether or not an
implementation is conforming depends only on its behavior (plus
the required supporting documentation), not on any internal
details, except insofar as they have an impact on the required
behavior.

Your question about free() (and indirectly about malloc()) is a
quality-of-implementation question, not a conformance question.
There is no requirement that malloc() succeed at allocating
memory, under any circumstances. It's perfectly legal for
malloc() to consult a random number generator, even one that
isn't deterministic, and always return NULL if the random number
is, say, even. Similarly, it's perfectly legal for malloc() to
initialize all free space as "not yet been allocated", and then
let an allocation fail if memory that it otherwise would allocate
has been marked as previously allocated. Obviously the effect is
just the same as what would happen if free() had an empty
function body. Your question about free() is a QOI question
because really what it boils down to is, is how free() and
malloc() are implemented "good enough"? The Standard chooses
deliberately not to address such questions.

So in answer to your question above, whatever various authors and
WG14 committee members, not to mention other people who may have
participated in meetings of WG14, might think about how free()
will or should be implemented, they are essentially unanimous in
the opinion that this question is one the Standard simply _does
not address_, and in fact has chosen consciously not to address,
because that purpose isn't one the Standard is meant to serve.

The above may be summarized briefly as: The Standard does not
define what constitutes a /good/ implementation, only what
constitutes a /conforming/ implementation. Your question about
free() and malloc() is really a question about how good their
impelementations are, and therefore is outside what the
Standard attempts to define.

 

[Tim Rentsch]

It has been interesting reading the arguments here about what free
can or can not do. Thinking about it, I realize that the C
standard has no power, in and of itself, to force free to do
anything, or even make any program do anything. If I write a C
compiler, and if it fails to issue a required diagnostic, or write
a C program that dereferences a NULL pointer, no one from the
standard committee or ISO is going to show up to take away my
programming license or arrest me and send me to the dilithium
mines. The C standard just isn't that kind of standard.

What the C standard does do, is provide a definition (actually a
number of them), so that people can talk about C programing and
have something solid in agreement. For example, if you are hiring
a programmer to write a program, you can write specification based
on the standard. This also means that in most places, to
advertise that you implementation meets the C standard, when it
doesn't could get you into trouble for false advertising.

My feeling is that based on this, if an vendor provided an
implementation that claimed to conform to the C standard, and in
the implementation free was always vacuous (and provided no other
way in background to recover the memory), it would probably be
found guilty of false advertising as the standard does say that
free will make the memory available for future allocations.

An attorney arguing that point of view would have a significant
uphill battle. Section 5.1.2.3 p6 spells out pretty clearly what
the bar is for being a conforming implementation, and it depends
only on externally observable behavior, not on any implementation
internal details. Moreover if any member of the WG14 committee
were called to offer expert testimony in the case, I'm confident
their testimony would be that such questions are concerned only
with quality of implementation, and so are deliberately outside
of what the Standard considers in defining conformance.

 

[Tim Rentsch]

Ok, put another way: Can the following program ever return
EXIT_FAILURE at Line B when run in a hosted environment?

#include <stdlib.h>

int main(int argc, char **argv)
{
char *p;

p = malloc(1);
if (p == NULL)
{
/* dummy malloc() implementation */
return EXIT_SUCCESS; /* Line A */
}
while (1)
{
free(p);
p = malloc(1);
if (p == NULL)
{
return EXIT_FAILURE; /* Line B */
}
}
/* not reached */
}

Notes: if malloc() is a dummy implementation that always returns
NULL, then it will return EXIT_SUCCESS at Line A. The maximum
amount of dynamic memory that this program requires is 1 byte, plus
any alignment and bookkeeping overhead.

Very nice way of phrasing the question. The answer is YES, the
return at point B may conformingly occur. The Standard imposes
no requirements on when an attempted allocation must, or if ever,
succeed. Since there are no circumstances under which a call to
malloc() is required to succeed, it may fail at any time and
still be conforming.

 

[glen herrmannsfeldt]

(e-mail address removed) writes:
(snip)

I'd like to offer a different kind of answer, in hopes of getting
at what I think it the real underlying issue here.

How you're thinking about the question is off in an essential
way, namely, you think the Standard is meant to address the
question you're asking, whereas it really isn't. The authors of
the C standard (IIANM going all the way back to the original ANSI
committee) made a conscious choice /not/ to address questions
regarding "quality of implementation" but only hard-edged
questions with yes/no answers. Furthermore whether or not an
implementation is conforming depends only on its behavior (plus
the required supporting documentation), not on any internal
details, except insofar as they have an impact on the required
behavior.

which allows for a variety of possible implementations.

Your question about free() (and indirectly about malloc()) is a
quality-of-implementation question, not a conformance question.
There is no requirement that malloc() succeed at allocating
memory, under any circumstances. It's perfectly legal for
malloc() to consult a random number generator, even one that
isn't deterministic, and always return NULL if the random number
is, say, even.

More commonly, run on a system where other programs are randomly
allocating memory, such that the available memory changes randomly.

Similarly, it's perfectly legal for malloc() to
initialize all free space as "not yet been allocated", and then
let an allocation fail if memory that it otherwise would allocate
has been marked as previously allocated. Obviously the effect is
just the same as what would happen if free() had an empty
function body. Your question about free() is a QOI question
because really what it boils down to is, is how free() and
malloc() are implemented "good enough"? The Standard chooses
deliberately not to address such questions.

As I previously noted, though I haven't personally noticed, it
seems that some systems now have "lazy allocation" where malloc()
always returns non-null (with a 64 bit address space, you can do
that for a long time) and later figures out if there is enough
memory to allocate. That is, similar to the way airlines overbook,
hoping that not everyone will show up.

Early virtual memory systems allocated in virtual memory, such
that they would return null even if plenty of real memory was
available. Most now (even though disks are now bigger) aren't
that restrictive.

So in answer to your question above, whatever various authors and
WG14 committee members, not to mention other people who may have
participated in meetings of WG14, might think about how free()
will or should be implemented, they are essentially unanimous in
the opinion that this question is one the Standard simply _does
not address_, and in fact has chosen consciously not to address,
because that purpose isn't one the Standard is meant to serve.

The above may be summarized briefly as: The Standard does not
define what constitutes a /good/ implementation, only what
constitutes a /conforming/ implementation. Your question about
free() and malloc() is really a question about how good their
impelementations are, and therefore is outside what the
Standard attempts to define.

-- glen

 

[Tim Rentsch]

Actually, since that clause specifies that the output be correct
according to what the abstract semantics would have produced, and
the definition of free is to make the memory available for further
allocations, this clause can NOT be used to excuse a reasonable
reading to require free to at least attempt something.

The key point is that whether an implementation is conforming
depends only on its behavior. If we have two implementations
that exhibit the same behavior, then if one is conforming the
other is also, regardless of how they are coded. It's easy to
sketch out an implementation that obviously does try to conform
to the spirit of the free()/malloc() descriptions, and be
conforming otherwise, yet would exhibit the same behavior as an
implementation with an empty free() body. Because conformance is
determined solely by behavior, we can't say one is conforming and
the other isn't - either both are or neither is. Do you mean to
say that the Standard requires malloc() must succeed under some
circumstances? If so then which portions of the Standard provide
such requirement? If not then the "sincere" implementation is
conforming and so must also the "insincere" implementation be.

As to being merely quality of implementations, most jurisdictions
have laws that require products to have at least certain very
minimal levels of quality to be offered.

I won't disagree, but that doesn't have anything to do with
the question of false advertising as regards being a conforming
implementation.

After all, would YOU allow someone to say the following is a C
compiler: a shell script that checked if a file matches a
specific sample, if it matches copy another file to a specified
place, and if not print a message?

By a strict reading of the standard, such a script (with
appropriate documentation) seems to meet all that the standard
requires. After all, 5.2.4.1 only requires the ability to execute
"at least one program ...", and may (because there is no other
requirement) indicate that any other program for any reason
doesn't meet the translation limits. There is a footnote
(non-normative) to avoid fixed limits whenever possible, but that
is 1) not normative, and 2) doesn't actually require anything.

Your analysis is incomplete. There are two other significant
requirements of a conforming implementation, namely, it must
"accept" any strictly conforming program, and it must "reject" any
program with a (non-skipped) #error directive. These additional
requirements actually raise the bar quite a bit, and it isn't
nearly so easy to provide a conforming implementation as the
script outlined above. However let me ignore those details and
respond to your question as if that didn't matter.

If someone provided such an (extremely limited) implementation, and
claimed it was a conforming implementation, which is the question
under discussion, I would /agree/ that it is conforming. The
reason I would agree is that I believe this is what the authors
of the Standard intented. This point is discussed at some length
in the Rationale document. The authors are fully aware that such
contrivances are possible, yet still chose to define conformance
as they did, knowing full well that the definition adopted allows
such subterfuges. I believe it is appropriate to take the word
conforming to mean what is both stated and intended by the authors
as its meaning; to do otherwise would go against both the letter
and the spirit of what the Standard embodies.

Thus, you may perhaps be able to claim that you conform to the C
standard (quoting a specific standard number), but to call it also
a "C Compiler" may well impose some "higher" standards (namely
that it at least sort of does what it says it does).

The question of whether such an implementation is conforming
is exactly the question under discussion. That comes straight
out of your posting at the start of this subthread (and still
appearing in the quoted portion above).

 

[Stefan Ram]

Note that the memory allocation function, are defined at the abstract
machine level to allocated memory or null if it CANNOT be allocated.
This would imply that the implementation needs to actually attempt to
return the requested block, so an implementation that returns a null
when it could return a request block has failed to meet a requirement of
the standard. It doesn't matter if the program can detect that it could
have.

»CANNOT« - according to some readers - might include that it
cannot do this, because it was not programmed to do so,
while more effort during development might have enabled it
to do this.

Another problem with looking at behavior (at least as a black box) is
that it is impossible to prove conformance. A conforming implementation
has required behavior on every possible conforming program, with every
possible input. As this is an infinite job, it will take an infinite
time. Also, some parts of observable behavior might not be really

Even when there is only a finite number of possible inputs,
it will not help to try every of those inputs in the case of
a black box. When there are 10^10 possible inputs, the black
box might contain a counter that will give a wrong result
only after 10^10^10 inputs. Or it might give a wrong result
only for a certain input and only between 10:00:00.00000
and 10:00:00.00001 o'clock.

 

[James Kuyper]

On 3/29/14, 7:11 PM, Tim Rentsch wrote: ....

Actually, since that clause specifies that the output be correct
according to what the abstract semantics would have produced, and the
definition of free is to make the memory available for further
allocations, this clause can NOT be used to excuse a reasonable reading
to require free to at least attempt something.

As to being merely quality of implementations, most jurisdictions have
laws that require products to have at least certain very minimal levels
of quality to be offered.

A conforming implementation of C might might have quality so low that it
violates a particular jurisdiction's legal requirements for
merchantability; but that implementation could not be correctly
described as having falsely claimed to be a fully conforming.

After all, would YOU allow someone to say the following is a C compiler:
a shell script that checked if a file matches a specific sample, if it
matches copy another file to a specified place, and if not print a message?

By a strict reading of the standard, such a script (with appropriate
documentation) seems to meet all that the standard requires. After all,
5.2.4.1 only requires the ability to execute "at least one program ...",
and may (because there is no other requirement) indicate that any other
program for any reason doesn't meet the translation limits. There is a
footnote (non-normative) to avoid fixed limits whenever possible, but
that is 1) not normative, and 2) doesn't actually require anything.

Not quite: a #error directive that survives conditional compilation must
result in a diagnostic message that contains precisely specified
contents (6.10.5). Since conforming implementations are prohibited from
successfully translating such a translation unit (4p4), the fact that
they are only required to successfully translate and execute one program
does not exempt them from the requirements of 6.10.5.
Whether or not the #error directive survives conditional compilation,
and the exact text of that message, can only be determined with
certainty by implementing fully translation phases 1-4. In particular,
evaluation of #if conditions requires also implementing an extremely
limited subset of phase 7 processing.

Still, your basic point remains. Primarily due to 5.2.4.1, a minimally
conforming implementation of C can be far too minimal to be of any
practical use.

 

[Tim Rentsch]

First, this statement is false, because an important part of the
equation that needs to be considered is the documentation for the
implementation, it is quite possible for two implementation to
behave identically and one to conform and one to not, because one
might document implementation differently.

I didn't mention this because I thought it was obvious. Of
course what I'm talking about is implementations that share
the same values for implementation-defined parameters, etc.
We might call such implementations "simpatico".

The definition of /observable behavior/ refers back to the
abstract machine, and says, in essence, that observable outputs
must match that of the abstract machine, so it is allowed to do
things differently in the real machine than the abstract machine,
as long as we can't "see" the difference on the outside.

Note that the memory allocation function, are defined at the
abstract machine level to allocated memory or null if it CANNOT
be allocated. This would imply that the implementation needs to
actually attempt to return the requested block, so an
implementation that returns a null when it could return a request
block has failed to meet a requirement of the standard. It
doesn't matter if the program can detect that it could have.

This conclusion is not consistent with 5.1.2.3 p6 (or p5 in
n1256), which starts "The least requirements on a conforming
implementation are: ...".

Another problem with looking at behavior (at least as a black
box) is that it is impossible to prove conformance. A conforming
implementation has required behavior on every possible conforming
program, with every possible input. As this is an infinite job,
it will take an infinite time. Also, some parts of observable
behavior might not be really observable in practice. For
instance, the standard requires that ALL volatile objects be
accessed in accordance to the virtual machine, including those in
"normal" memory. On many machines, this is impossible to do.
Also, some behavior is allowed in the case of "failure", and
(unless you want to allow to arbitrary fail on any or every
case), it is often impossible for the program to determine that
something really failed, and it could be claimed that for an
implementation to call something a failure, when there really
wasn't a failure, is a deviation from the abstract machine, and
thus a non-conformity.

This says that conformance determination MUST be "White Box",
where we can look at how it does things, so we can abstractly
determine what will happen in the infinitely large case. This
says that we CAN know internal details about if a failure really
did happen or not,and thus insincerity (declaring a failure when
there wasn't) is possible.

You have the burden of proof here backwards. The person making a
claim of false advertising has to prove the implementation is not
conforming, not the other way around. The only way to do this is
to supply a program whose output could _not_ have been produced by
a conforming "simpatico" implementation. This is quite a high
bar. Furthermore, since it is easy to demonstrate an alternative
simpatico implementation that clearly is conforming and has the
same behavior, there is an affirmative defense to any such program
offered.

The problem with that distinction is that then I suspect that NO
implementation is conforming, as, if you can't stop based on
implementation limits, it is possible to create an arbitrary
large program that must be parsed to determine if a #error is
skipped or not.

This conflates two different items, namely, an implementation and
the data processing system on which the implementation might be
run. There is no requirement, for example, that an implementation
must be runnable on a system with 512 bytes of RAM, or any fixed
amount of RAM. What is required of an implementation is only that
it would behave appropriately if run on a system with sufficient
resources available. Such concerns are explictly outside the
scope of the Standard (section 1 paragraph 2).

Since we MUST allow an implementation to declare a translation
limit before the accept/reject decision (or our set of conforming
implementations is empty), the script passes just as well as
Clang or GCC (maybe even better,as it is much less likely to have
a bug causing it to make the wrong determination, or accept and
then miss-translate a program).

Again a distinction needs to be made between an implementation
and the data processing system on which the implementation might
be run. Limitations that arise as a consequence of lack of
resources in the data processing system are not translation
limits but just limitations in the surrounding environment. For
example, an implementation won't be able to compile a program
if there is zero disk space available, but that's not a
translation limit.

Note, the message I replied to brought up the concept of a court
of law and a "language lawyer", so I suspect that the script
implementation could be found guilty of not being a conforming C
compiler, not be cause it isn't conforming, but because it isn't
a C compiler in the first place (so conformance doesn't really
matter).

In the case of free, (and a number of other functions), the
standard provides a (crude) description of the behavior of the
abstract machine. It says what the function should attempt to
do, while allowing it to fail, for unspecified reasons. I would
claim that an implementation that gratuitously fails has not met
the requirements of the abstract machine, and thus has hit
non-conformance. An environment might not provide for a heap,
and thus an implementation might be able to legitimately have a
malloc() that always returns NULL and be conforming. Once the
implementation admits that malloc() can in fact allocate some
memory, free is described as returning that memory for the
possibility of further allocation, so to not do this is
non-conforming.

The problem is the Standard imposes no requirements for what
constitutes "attempting" to allocate memory, and certainly none
that are detectable through observable behavior. In effect what
you are arguing is that the implementor's state of mind makes a
difference in whether an implementation is conforming. How the
Standard defines conformance makes it clear that it does not.