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

[mathog]

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

 

[Eric Sosman]

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.

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.

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??? */

Language says: "You're sneezing demons." 7.22.3.3p2.

 

[Keith Thompson]

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.

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.

 

[mathog]

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.

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

 

[Eric Sosman]

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!

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.

 

[glen herrmannsfeldt]

The title says it all.

My news reader truncates long titles, so I don't know what it says.

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.

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.

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

-- glen

 

[James Kuyper]

On 08/04/2013 12:22 AM, glen herrmannsfeldt wrote:
....

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.

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().

 

[Malcolm McLean]

On 8/3/2013 6:37 PM, mathog wrote:


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.

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.

 

[Bart van Ingen Schenau]

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.

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

 

[Stephen Sprunk]

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.

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

 

[Keith Thompson]

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.

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]

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.

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.

 

[Geoff]

(But I just tried it on Solaris 9, and it ran without error
-- though I seriously doubt that it actually deallocated the memory.)

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.

 

[Ian Collins]

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

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)

 

[Keith Thompson]

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.

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

 

[Stephen Sprunk]

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.

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