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

Discussion in 'C Programming' started by partremmaps, Mar 9, 2014.

  1. partremmaps

    partremmaps Guest

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

    I am not talking about implementations which do not support dynamic memory allocation.

    I am also not talking about cases where free() is passed as an argument something other than a current valid pointer earlier returned by a successful call to calloc, malloc, or realloc.

    I am talking about implementations and architecture which fully support malloc, calloc, and realloc, and the situation where free() has been passed a valid and current pointer to currently allocated space, having been allocated earlier by a successful call by malloc().

    A couple of people who are in the daily habit of giving C advice on IRC told me that even in these implementations and situations, free() may be an empty function and do nothing and still be standards compliant.

    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 spacehaving 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."

    I protested that if a program were to allocate and free memory repeatedly, and that if free() were allowed to perform no action, that the computer would run out of memory even though it actually had plenty of memory for the program if free() did as described.

    They responded that it was up to the user to select an implementation that did what he needed.

    The standard of course does describe free as causing the space pointed by ptr to be deallocated and made available for further allocation.

    My concern is not that somebody may try to run a program on a machine whichdoes not have enough memory, but that the program will end up needing an infinite quantity of memory if it is run for long enough, even though it waswritten in such a way as to free the memory it allocated before allocatingmore.

    If these fellows' claims are true, then this raises more questions like whether input and output functions must also do their described task even under circumstances where the C program, using only semantics of the C AbstractMachine, has no way to determine that the described side effect actually took place.

    For example, if stat and fopen and all file open/existence related functions were "optimized" in such a way to always falsely return "file not found,"then the C program, when using only the semantics of the C Abstract machine, would not be able to tell that the file did actually exist, and thus theimplementation should be considered compliant.

    For another example, what if putchar() was "optimized" to simply return thecharacter supplied to it as an argument but neglected to actually put the char to stdout - the C program could not test whether the char was actuallysent to stdout.

    These fellows responded that a human could observe that a file did indeed exist or that nothing was being sent to stdout, and that was sufficient to observe a missing side effect.

    However, they said that a human observing a memory leak was not allowed as a test but that the test of whether a side effect was performed could only be tested by the C program in question, and only within the semantics of the C Abstract machine.

    Furthermore, If said claim is true, then it raises the question of why doesthe standard describe a specific functionality if it doesn't really matterif free() does anything anyway?

    To me, memory is a finite resource, and whether free frees it as described does matter, which is why the standard specifies an action for free.

    In other words, for free() to fail to do as the standard describes, the operation of the program could be severely affected.

    They cite the standard where it talks about optimization and says "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"
    (See section "Program Execution" in the standard.)

    The value of free() may not be used, but the freed memory well could be used.

    The standard also says that modifying an object (or calling a function thatdoes so) is a side effect.
    (See section "Program Execution".)

    But does free() particularly modify an object? It does delete it, but is that considered a modification to the execution environment?

    But I guess the question is whether one ought to take a subtle technical wording in such a way as to render other explicit content of the standard to be meaningless in such a way that the program would behave drastically outside of how it was written according to the standard.

    The standard does say (in cases where there is an operating system other than the C program in question) that free() shall conform to the described specification if it is present. (See "Execution environments" and "Hosted environment.")

    To me, common sense says that it would be incorrect to construe a vague technical wording to render explicit portions of the standard meaningless.

    My view is that, according to the standard, free() must do exactly as described in the standards under the section "The free function," and that it makes no sense to construe the standard in such a way as to void its very explicitly described functionality of various functions.

    Is there a definitive answer on whether free() may be empty and void and still standards compliant, in the context of this post?

    Thanks,

    ~Jesse
     
    partremmaps, Mar 9, 2014
    #1
    1. Advertisements

  2. partremmaps

    Kaz Kylheku Guest

    Of course, this is an empty function:

    void free(void *ptr) { }

    But just to be sure, that is what you mean, right?

    I believe the answer is yes.
    This is correct. To require free to actually liberate memory would mean that
    an implementation cannot turn free into a no-op and provide garbage collection.

    However, if an implementation doesn't provide garbage collection, and its free
    function does nothing, that will obviously cause memory leaks in
    C programs, and big, runaway memory leaks in some kinds of C programs.

    This would simply count as a low quality implementation.
    However, a C program can bomb because it exhausted all memory, even though the
    program meticulously uses free, and there should be plenty of memory available
    for that program.

    In the real world, that is a visible effect.

    A C implementation can conform to the standard and be a piece of crap in all
    sorts of ways besides this. Conformance is only part of the picture.

    For instance, a compiler can be conforming, yet do things like generate code
    which passes and returns structures in a global memory area. Users who expect
    to be able to use that compiler to write re-entrant code in their OS kernel
    require a compiler to generate reentrant code for call and returns. This means
    that the compiler has to conform to an additional requirement which isn't in
    the ISO C standard. There are all kinds of requirements like that.

    Diagnostics are an obvious area. A conforming C compiler can simply stop
    translating and put out a message like "this translation unit requires a
    diagnostic according to ISO C". But, of course, users want to know what kind
    of diagnostic, and in what line of code. That is not required by the standard!

    The ISO C standard is not (and is not meant to be) a complete requirement
    specification for a useful implementation of C.
     
    Kaz Kylheku, Mar 9, 2014
    #2
    1. Advertisements

  3. partremmaps

    partremmaps Guest


    That is exactly what I mean.



    The standard does make the following statements in the following order:
    (Reading from SO/IEC 9899:TC3 Committee Draft September 7, 2007 WG14/N1256,http://www.iso-9899.info/n1256.html)

    5.1.2.2: A hosted environment need not be provided, but shall conform to the following specifications if present. (See Hosted environment)

    (A hosted environment is one where there is an operating system which benefits the C program, as apposed to a Freestanding Environment where there is no operating system that benefits the C program -- like an embedded system.(See Execution environments.))
    (Freestanding environments are allowed much more deviation from the standard as compared to hosted environments.)

    5.1.2.3p2: ... At certain specified points in the execution sequence calledsequence points, all side effects of previous evaluations shall be ompleteand no side effects of subsequent evaluations shall have taken place.

    7.20.3: The lifetime of an allocated object extends from the allocation until the deallocation. (See Memory management functions)

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

    I am talking only about "Hosted environments" here - those with an operating system benefiting the C program in question.

    So it looks to me like while no implementation must support free(), free() must conform to the standard if free() is present in the implementation. And obviously free would be present if you had void free(void *ptr) { } .

    The standard says that a lifetime of an allocated object extends from allocation until deallocation, and it says that free deallocates, making it available for further allocation.

    And as a reminder, I am talking about an implementation and platform that fully supports malloc, calloc, realloc, and has a free() function.

    Thus, it looks to me like, since the lifetime must end at deallocation, andfree() is to deallocate, then free cannot be "void free(void *ptr) { }."

    You could say "Well, what if they use a garbage collector that automatically frees the allocated space when the empty function free() is called..."
    That would be fine, except that the standard specifies that the allocated object lives up until the point of deallocation and no more and no less, andit says that free deallocates -- so if free() were an empty function, thenthe GC would have no way of knowing when free() had been called.

    Furthermore, the standard does clearly describe free as deallocating and liberating memory to make it available for further allocation.

    The concept of a garbage collector+empty free() seems a bit risky since thestandard also requires side effects to be completed before the next sequence point, so if there was a garbage collector, it would have to free the memory while the void free() was running, otherwise the side effect required by the call to free would happen outside of its sequence period and thus not be compliant.

    But are you saying then that free() may be empty as long as the implementation comes up with some other method to free the requested space during the time that free() is executing?

    Then we'd have an empty function which changed how the program worked depending on whether the call to the empty function was present or not...!




    But if the implementation provided neither a functioning free() nor some other trick to fully emulate a functioning free, would not that then fail to comply with the standard where it says "The free function causes the space pointed to by ptr to be deallocated, that is, made available for further allocation?"

    I agree that it would be a low quality implementation but I cannot see how it would still be compliant when it failed to conform to the clear description of functionality in the standard: http://www.iso-9899.info/n1256.html#7..20.3.2


    Thank you very much. I'm trying hard to understand.

    ~Jesse
     
    partremmaps, Mar 9, 2014
    #3
  4. That would be most obvious for a system with garbage collection.

    As well as I know it, the standard leaves actual limits on memory
    usage system dependent, and if not done carefully might be
    considered a low "quality of implemenation".

    If one isn't careful with garbage collection, for example with
    a circular linked list, one might expect it to be released, but
    the GC doesn't release it.

    I don't know if there is a C compiler for IBM System/38, but as
    I understand it virtual addresses aren't reused. With 64 bit
    virtual addresses (and in years past) that was reasonable.
    (It might still be that 64 bit virtual is enough.)

    -- glen
     
    glen herrmannsfeldt, Mar 9, 2014
    #4
  5. Strictly speaking, I think the lifetime issue is a red herring. The
    lifetime of an object is a guarantee of when it is usable, not a
    guarantee that it is unavailable subsequently. For example, a C
    implementation that used static allocation for automatic variables where
    that is possible (basically in functions that can't be called while they
    are active) would be conforming. Also, in code like this:

    void f(void)
    {
    ....
    if (...) {
    int i;
    ...
    }
    /* Must i really be "gone" here? */
    ...
    }

    no one would claim that an implementation that did not actually make the
    object referred by 'i' invalid after the 'if' is non-conforming. You
    can't ever tell when an object's lifetime ends, so if the standard
    merely said that free ends the lifetime of the allocated space, there
    would be nothing to debate.

    Thus, in my view, your question all revolves around the extra phrase
    "made available for further allocation". Must this happen immediately,
    or could the storage be made available some while later? Could it be
    made available right at the end of the program's execution (when it's
    too late for the program itself)?

    This is the kind of question that I have sworn off getting involved
    with, so I won't offer an opinion. But you have to ask yourself if it
    really matters. If a C library offered a free function that did not
    make some reasonable best-effort to make freed storage available, I
    would try to avoid it, regardless of whether it conforms or not.

    <snip>
     
    Ben Bacarisse, Mar 9, 2014
    #5
  6. Yeah, but if you've been around for this newsgroup for more than a week or
    so, you'd know that nobody cares about QOI here. Conformance to the
    almighty standard is the be-all and end-all of our existence. In the
    religion of CLC, conformance uber alles, and all those other things, like
    performance, stability, usability - well, you can just go discuss them
    somewhere else.

    Note that the above sounds like sarcasm, etc, but it is just the truth.

    --
    "The God of the Old Testament is arguably the most unpleasant character
    in all fiction: jealous and proud of it; a petty, unjust, unforgiving
    control-freak; a vindictive, bloodthirsty ethnic cleanser; a misogynistic,
    homophobic, racist, infanticidal, genocidal, filicidal, pestilential,
    megalomaniacal, sadomasochistic, capriciously malevolent bully."

    - Richard Dawkins, The God Delusion -
     
    Kenny McCormack, Mar 9, 2014
    #6
  7. partremmaps

    David Brown Guest

    There are (at least) two types of program for which an empty free() and
    no garbage collection would be perfectly acceptable. The first is
    programs that don't allocate heap memory at all - you can do a lot
    without it. In the world of small-system embedded programming, malloc()
    and free() are rare, and are often banned entirely by coding standards.
    The second would be programs that don't need much re-use of memory,
    and run under an OS - they can simply keep all their memory until the
    program ends and the OS frees it. There is also the combination -
    embedded programs that allocate memory initially, but never need to free
    it because they never end (until someone turns the power off).

    The few times I have used malloc() and free() in small embedded systems,
    the malloc() just used a simple index in a statically-allocated memory
    pool, and free() was empty.
     
    David Brown, Mar 9, 2014
    #7
  8. partremmaps

    partremmaps Guest


    Of course, the question was about space pointed to by a pointer and freed by free(), which i isn't in this case.

    Except perhaps the standard does spell out that free is to deallocate. In your example above, I agree, the space used by i could live outside its scope for some length of time.

    But since the standard does say that free deallocates, and since it does not have any comment that the action is allowed later, it causes me to question the correctness of assuming a "May be done later" clause when such a clause is no where to be seen (at least that I've found,) especially considering C's strong sequence point rules.

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

    Well, one thing that bothers me is an attempt to render portions of the standard to mean nothing.
    If the standard was meant to say simply that memory resources must be freedto the operating system upon program termination, then it would have said that, rather than describing free().

    Thanks!

    ~Jesse
     
    partremmaps, Mar 10, 2014
    #8
  9. partremmaps

    partremmaps Guest


    If I understand correctly, the standard makes allowance for embedded applications which it calls freestanding environment which do not benefit from an operating system.

    And indeed, if I understand correctly, in a freestanding environment, it appears that the standard allows library facilities to be implementation defined - which would allow for free() to be empty.

    I too have used C on little micros - and I agree, you don't really need malloc to manage 256 bytes of ram! And if you did, the standard does allow a lot of leeway in how those functions are implemented, so an empty free() would be allowed.

    However, the context of my original question was for a system where the program was running with the benefit of an operating system and as such, "shall conform to the following specifications...", one of which free() is. (See section Hosted Environment.)

    Thanks,

    ~Jesse
     
    partremmaps, Mar 10, 2014
    #9
  10. partremmaps

    partremmaps Guest

    <snip>

    I just had a thought on the topic.

    It's too bad the standard authors didn't put one of the following statements in the standard. If they had, then the question would be answered one wayor the other:

    Proposed statement 1:
    Any missing or unclear technical detail in the standard, even if so small it may have been over looked by the maintainers, may be used to render meaningless any sections of the standard even if said sections contain clear andverbose wording on the topic.

    Proposed statement 2:
    In the case of a question of a technicality where there are no notes to clarify, the meaning of the standard should be taken as it written keeping in mind the purpose of what is written.

    If it had one of those statements, which would it be?

    The fact is that the standard says that free is to free the space pointed to, making it available to further allocation. It doesn't spell out that it has to happen right away or that it may do it later, but then again it doesn't spell out that all of the other functions have to do theirs right away either.

    However, it does fully support the concept that side effects happen and finish within sequence points.

    The technicality is that the standard says that modifying an object is a side effect, but it doesn't say that deleting an object is a side effect, andfree deletes an object.

    However, malloc creates an object. But we certainly can't argue that mallocis allowed to create that object later - it must be ready BEFORE the ending sequence point for malloc() because otherwise the next statement might try to use unallocated memory.

    And even free() is to free space for further allocation -- what if the verynext statement was to allocate memory, and that it needed the just freed memory? The purpose of the standard's wording is clear: free the memory so it can be re allocated. Period.

    To me, it seems that creating and deleting objects would also have to be considered of the same type of thing. Obviously, creating an object with malloc() must happen before malloc()'s last sequence point, so I see no reason to say that deleting an object with free() would be any different.

    It does not make sense to me to make any assumption on lack of details thatrenders useless clearly worded sections of the standard.

    The standard says that free does certain things. If it does not do those things in a given implementation, then it sure seems like it's not standard to me.

    Thanks,

    Jesse
     
    partremmaps, Mar 10, 2014
    #10
  11. partremmaps

    Kaz Kylheku Guest

    Sure; so if you don't actually call free, you don't care if it's empty, or if
    it calls abort(), ...
    And this category can even have bugs fixed in it if free is replaced by a
    no-op.
     
    Kaz Kylheku, Mar 10, 2014
    #11
  12. partremmaps

    David Brown Guest

    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.

    Even in embedded systems, of course, these functions are usually
    implemented "sensibly" in the library. It is the choice of the user to
    overrule them with a simple implementation (such as an empty free()) if
    that suits the application.
    People writing high reliability, safety-critical, or real-time embedded
    systems will generally avoid any sort of dynamic memory if they can -
    memory size has nothing to do with it. If it is unavoidable (it is
    difficult to implement a network stack efficiently without some dynamic
    memory handling, for example), then they normally write specific and
    targeted dynamic memory handling with fixed size pools. The trouble
    with standard malloc() and free() is that it is extremely difficult to
    reason about them, it is very difficult to guess their timing, they can
    sometimes fail, and general malloc() algorithms are prone to memory
    fragmentation which can be a huge problem in embedded systems (without
    virtual memory).
    Fair enough - I was just pointing out some wider variety.

    My own reading of the standards is that an empty free() is allowed in
    hosted environments, and it could be useful since the OS will re-claim
    the memory on program termination anyway. (That assumes an
    appropriately powerful OS, of course.)
     
    David Brown, Mar 10, 2014
    #12
  13. partremmaps

    Martin Shobe Guest

    Yes, but it does show a hole in the argument that starts with "since
    lifetime must end be deallocation, ...". Lifetime has little to do with
    your question.
    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
     
    Martin Shobe, Mar 10, 2014
    #13
  14. partremmaps

    Martin Shobe Guest

    On 3/9/2014 7:39 AM, Ben Bacarisse wrote:
    [snip]
    I think it must happen as if it had occurred by the time free() returns.
    As far as I can tell, it's just another side-effect. The reason it can
    be delayed is the "as-if" rule.

    [snip]

    Martin Shobe
     
    Martin Shobe, Mar 10, 2014
    #14
  15. partremmaps

    Martin Shobe Guest

    I don't think the question is, "Can free() not deallocate the memory."
    It clearly must. The question is, "Can free() be implemented as a
    no-op." Here, the answer is clearly "yes, as long as it works as if it
    had deallocated the memory." If that deallocation doesn't result in a
    requirement that a future malloc(), et. al., succeed, then the "real"
    deallocation can be put off indefinitely via the "as-if" rule.

    Martin Shobe
     
    Martin Shobe, Mar 10, 2014
    #15
  16. [...]

    N1570 5.1.2.1:

    Any library facilities available to a freestanding program, other
    than the minimal set required by clause 4, are implementation-defined.

    A freestanding implementation needn't provide malloc() and free() at
    all. It can provide functions with those names that compute square
    roots (though that would be perverse). The headers that are required
    for freestanding implementations are the ones that don't declare any
    functions.
     
    Keith Thompson, Mar 10, 2014
    #16
  17. partremmaps

    partremmaps Guest


    I like your sample program. As to wheather malloc() and friends are allowed(in a hosted environment) to simply return NULL without attempting to allocate, the standard does clearly describe them as allocating or returning NULL if the cannot allocate. (See [Memory management functions])

    For realloc it actually uses the phrase "If memory for the new object cannot be allocated,..." and "...., or a null pointer if the new object could not be allocated."

    So while the standard does not lay out the rules for how hard malloc must try, there is no question that it must try.

    Your program (above) could return EXIT_FAILURE at Line B if another programin the hosted environment allocated the last byte, or for example if another program had allocated a billion 1-byte objects and the dynamic memory management system could only deal with a billion allocated objects, so it could fail at B even with ram left over.

    But the point is that it tried.


    Thanks,

    ~Jesse
     
    partremmaps, Mar 11, 2014
    #17
  18. partremmaps

    partremmaps Guest


    Could you explain which part of C11 would allow malloc() to always return 0and 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 hostedenvironment 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 beallocated," 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 NULLwithout attempting to allocate.



    Specifically what parts of the standard do you see as allowing free() to beempty?
    (In a hosted environment with fully functioning malloc() of course.)

    If free() is allowed to be empty, doesn't that sort of defeat the whole purpose of describing free() as deallocating memory? If all that was meant wasthat the program must free all allocated memory on exit then that's what it would have said.

    Furthermore, the standard describes free() as making the space pointed to made available for further allocation. Considering the purpose and stated functionality of free, that further allocation should include further allocation by the same program that just freed it.

    If free() is empty, then not only does it not free the memory, it is program termination which frees the memory -- not free().

    Thanks,


    ~Jesse
     
    partremmaps, Mar 11, 2014
    #18
  19. partremmaps

    partremmaps Guest


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


    Thanks,

    ~Jesse
     
    partremmaps, Mar 11, 2014
    #19
  20. partremmaps

    partremmaps Guest

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



    So I guess one could say that all standard C functions are allowed to perform no function so long as their described functionality gets executed within said function's sequence points.
    or "No function needs to actually do anything so long as for all practical purposes it behaves as described..."

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

    I have two issues with saying that deallocation can be delayed. One is thatthe 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.

    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 bebad. allocating and deallocating are the same class of side effects.

    Thanks,

    ~Jesse
     
    partremmaps, Mar 11, 2014
    #20
    1. Advertisements

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 (here). After that, you can post your question and our members will help you out.