Always safe to free() a pointer one byte past the end of an allocatedblock?

Discussion in 'C Programming' started by mathog, Aug 3, 2013.

  1. mathog

    mathog Guest

    The title says it all.

    Many loops start with a pointer at the beginning of an allocated block,
    and when the loop completes the pointer is one byte past the end of the
    allocated block. As far as I can remember, a free() operating on the
    pointer with that value has always released the memory.

    Does free() work like that because the language standard mandates it, or
    is it just something that pretty much all of the compilers do?

    This code fragment illustrates the issue:

    int count = 100;
    int *block = (int *) malloc(count * sizeof(int));
    memset(block,1,count*sizeof(int)); /* put some data in */
    for(; count; count--, block++){
    printf("%d ",*block);
    }
    /* block is now 1 byte past the end of the allocated memory */
    free(block); /* <-- Language says what about this??? */

    Storing the first value of block and then using free() with that later
    is not hard to do - I just wonder if it is necessary in this case.

    Thanks,

    David Mathog
     
    mathog, Aug 3, 2013
    #1
    1. Advertisements

  2. mathog

    Eric Sosman Guest

    The valid arguments to free() are:

    - Values returned by malloc() and not yet given to free(), or

    - NULL, or

    - Nothing else whatsoever. "There is no third thing."

    (Adjust for calloc(), realloc(), and aligned_alloc() as needed.)

    Passing any other pointer value to free() -- a pointer one
    past the block end, or into the middle of a block, or to a block
    already freed, or to static or auto storage -- yields undefined
    behavior. Pass a pointer to the beginning of a still-allocated
    block, or don't pass Go.
    Language says: "You're sneezing demons." 7.22.3.3p2.
     
    Eric Sosman, Aug 3, 2013
    #2
    1. Advertisements

  3. It is neither something mandated by the language standard nor
    something that pretty much all the compilers (actually runtime
    libraries) do. I'm very surprised that it appears to work for you.

    When I run it on my systems (Windows/Cygwin, Linux 32-bit, and
    Linux 64-bit) I consistently get a crash and a core dump, with a
    lot of diagnostic information on the Linux systems, starting with:

    *** glibc detected *** ./c: double free or corruption (out): 0x087ed198 ***

    Calling free() with any value other than (a) something returned by
    malloc() or equivalent and not already freed, or (b) a null pointer
    has undefined behavior.

    I'm curious where you got the impression that passing a pointer past
    the end of an allocated array to free() would deallocate the array.
     
    Keith Thompson, Aug 3, 2013
    #3
  4. mathog

    mathog Guest

    From a bug, of course. The entire test routine was never entered - so
    no allocating, no deallocating, no blowing up,
    and no leak in valgrind. (The printf's were ending up buried in a huge
    file, so I didn't notice them not showing up.)

    As E.S. noted, if the pointer is not at the beginning of the block, it
    blows up on Linux.:
    *** glibc detected *** ./memtest1: free(): invalid pointer: 0x08a5b00c ***

    Sorry, and never mind!

    David Mathog
     
    mathog, Aug 3, 2013
    #4
  5. mathog

    Eric Sosman Guest

    Despite "never mind," for the benefit of onlookers:

    "It blows up" is not the only possible manifestation of
    undefined behavior. It may well be the most fortunate outcome,
    but it's by no means guaranteed.

    If you're unlucky, a faulty free() may sail through without
    so much as a whiff of trouble, but corrupt the program's data
    structures in a way that causes mysterious misbehavior elsewhere.
    "Unlucky," because such bugs are the very devil to find: The code
    that crashes or otherwise misbehaves may be entirely blameless, a
    victim of a fault that occurred miles away. Your attention is thus
    drawn away from the fault and toward the victim, and working from
    effect backward to cause can be nearly impossible. "He died from
    eating an apple laced with cyanide." "How did the cyanide get
    there?" "Sorry, guv, no way to tell."

    You should consider "it blows up" as a stroke of luck: Things
    could be much, much, much worse.
     
    Eric Sosman, Aug 4, 2013
    #5
  6. My news reader truncates long titles, so I don't know what it says.
    It might be convenient to allow the pointer to be anywhere within
    the allocated block, but C doesn't do that. It would make free()
    more complicated than it usually is.

    Note for a contrasting possibility, the OS/360 (and successor)
    allocation routine (GETMAIN/FREEMAIN) allows one to release part
    of an allocated block. For FREEMAIN you pass not only the address,
    but the length you want to release.

    But back to C. Popular implementations of malloc() and free()
    store the information needed to keep track of the allocated memory
    in the bytes just before the value returned by malloc().
    (Most likely in a linked list.) So, free can just subtract and
    find the list node, and then process accordingly.

    A free() that allowed one to specify an address within the range
    would have to search through the list to find the appropriate node.
    Not impossible, but more overhead than many would like.
    -- glen
     
    glen herrmannsfeldt, Aug 4, 2013
    #6
  7. mathog

    James Kuyper Guest

    On 08/04/2013 12:22 AM, glen herrmannsfeldt wrote:
    ....
    Some implementations round all requested allocation sizes up to the next
    power of 2, and allocate all requests for a given power of 2 from
    particular blocks of memory. Such an implementation can figure out the
    amount of space allocated (but not the amount of space requested) just
    from the address passed to free(). This sounds wasteful and an
    inefficient use of space. However, it doesn't need to store as much
    heap-management information as other methods, which can make up for the
    wastefulness, at least for small allocations.

    Such an implementation could be set up to tolerate pointers to other
    locations within the allocated block, because it knows to round the
    address down to the appropriate power of 2. However, a pointer
    one-past-the-end of requested allocation could also be one-past-the-end
    of the actual allocation, in which case free()ing it would actually
    free() the next block, rather than the current one. So it's still a bad
    idea, even on such an implementation, to pass a one-past-the-end pointer
    to free().
     
    James Kuyper, Aug 4, 2013
    #7
  8. If your allocation is a round unit of eight, which is quite likely, and
    the allocation system is typical, then freeing one past the end of the
    block will be a valid free on the block following. The data won't be shredded,
    so the code using the allocation that was really freed will appear to work,
    until there's another allocation which fits, and overwrites it. That might
    be never in the life of a program.
     
    Malcolm McLean, Aug 4, 2013
    #8
  9. No, it wont. In a typical allocation system, malloc keeps its book-
    keeping data adjacent to the block it returns to you (typically before
    it). This means that if you have a pointer to the first byte past your
    allocation, that pointer would point at the book-keeping data that is
    stored in between allocations, not the start of the next block.

    Bart v Ingen Schenau
     
    Bart van Ingen Schenau, Aug 4, 2013
    #9
  10. Small allocations are often from an array of fixed-size blocks, with the
    only bookkeeping data a bitmask at one end of the array--not between the
    blocks.

    S
     
    Stephen Sprunk, Aug 4, 2013
    #10
  11. That makes a lot of questionable assumptions about how malloc() and
    friends work. As I posted recently, the systems I've tried don't seem
    to work that way; the program crashes (which is really the best possible
    outcome). (But I just tried it on Solaris 9, and it ran without error
    -- though I seriously doubt that it actually deallocated the memory.)
     
    Keith Thompson, Aug 4, 2013
    #11
  12. Yes, but allocating 2048 bytes for a 1025-byte request is wasteful.
    Such a scheme could save space *if* most allocations are either small
    (as you point out) or close to powers of 2 without going over.
     
    Keith Thompson, Aug 4, 2013
    #12
  13. mathog

    Geoff Guest

    But why didn't you investigate further? It seems to me that if you are
    going to criticize someone's assumptions you would want to make sure
    you weren't making any questionable assumptions of your own.

    I suspect Solaris checks the argument to free() and does nothing if
    the value isn't in it's known list of allocated blocks, but that's
    just my questionable assumption. :)
     
    Geoff, Aug 4, 2013
    #13
  14. mathog

    Ian Collins Guest

    I don't have anything as ancient as Solaris 9, butf you were to try this:

    #include <stdio.h>
    #include <stdlib.h>

    int
    main(void)
    {
    char* p = malloc(8);
    char* p1 = malloc(8);

    printf( "%x %x\n", p, p1 );

    free(p+8);

    return EXIT_SUCCESS;
    }

    in the debugger:

    8060d00 8060d20
    Bad free (baf):
    Attempting to free an unallocated block at address 0x8060d08
    which is into the heap; no blocks allocated
    stopped in main at line 12 in file "x.c"

    Or with a debugging allocator:

    c99 x.c -g -lumem; ./a.out
    8081fd8 8081fc8
    Abort (core dumped)
     
    Ian Collins, Aug 4, 2013
    #14
  15. I didn't investigate further because I do not particularly care.

    The behavior of calling free() with a non-null pointer that's not
    the result of a previous allocation call is undefined. I've already
    demonstrated that the behavior on some systems is a crash of the
    program. I'm very well aware that doing nothing is another valid
    instance of undefined behavior.

    The only "assumption" I made is that the free() call in question
    doesn't actually deallocate the memory, and I acknowledged my
    uncertainty on that point. To do so, free() would probably have to
    do substantial extra work that would be of no benefit to programs
    that use free() correctly.

    A full investigation would require examining the source code for
    the Solaris 9 C runtime library. I lack sufficient motivation to
    track it down, even assuming it's available.

    But now that you bring it up, this:

    free((void*)1);

    causes the program to die with a bus error, so the Solaris free()
    doesn't check its argument in all cases (unless the bus error is the
    result of failing that check).
     
    Keith Thompson, Aug 4, 2013
    #15
  16. In the short run it may appear wasteful, but over the long term it will
    tend to reduce fragmentation and therefore peak memory usage.

    There are many such well-known tricks for implementing malloc(), and a
    decent implementation will use several to achieve optimal long-term
    performance, averaged across a wide range of scenarios.

    S
     
    Stephen Sprunk, Aug 5, 2013
    #16
    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.