Does malloc() reuse addresses?

[Skarmander]

Hi all,

my question is:

if i allocate some memory with malloc() and later free it (using
free()), is there a possibility that a consequent malloc() will
allocate memort at the same starting address and will return the same
pointer as the previous malloc(). I would like to have confirmation on
whether this is practically a concern when pointers are used to
uniquely identify data structure instances - like in this example:

int isInstanceValid(myStrict* inst)
{
int i;
for (i=0; i<instCount; ++i)
if (instances == inst)
return 1;

return 0;
}

In this example, if an instance is freed, and a pointer to it becomes
non-valid, and later a new structure is allocated in the list, the
function will return that the pointer is valid, although it is actually
not the instance that was originally referred.

Aside from everything else that's already been said: don't do this.

There is no way to detect whether a pointer is valid (in any sense of the
word) in portable C, and in most cases it's not feasible to do it in
unportable C either.

If you concerned about not deallocating things before their time is up, use
a garbage collector, like http://www.hpl.hp.com/personal/Hans_Boehm/gc/.

If you're concerned about sloppy programmers (possibly including yourself as
a culprit), then audit your code more closely, using tools like valgrind
(http://valgrind.org/) and Electric Fence
(http://perens.com/FreeSoftware/ElectricFence/).

If you want a unique identifier for an object, come up with one yourself,
and don't make it depend (exclusively) on its address. This is what the
concept of a handle is all about, although handles are subject to mistakes
like these too. You may be able to devise a handle allocation scheme that
will maximimze the time before reuse and hence increase the chance of
detecting an invalid handle.

The best even most external tools can do is increase the likelihood of
detecting an allocation bug. They cannot convince you there aren't any.

S.

 

[avasilev]

avasilev wrote:
[...]

Ok I will clarify this a bit, sice some people did not get it properly.
I have a list of instance pointers. Every allocated instance is added
to this list and every freed instance is immediately removed from
there. The problem is that copies of these pointers need to be passed
around, and it may happen that when such a copy has to be used, the
instance it points to may be already gone. So a way to validate the
pointer is needed - and this pointer comparison approach was chosen -
not by me, I am kindof revising the thing. So my question was to
confirm how reliable is the current verification mechanism. My opinion
is that it is not, since pointer values for different instances (in
time) may conicide.

Well, I'm sure that many people will (rightly so) tell you that if
you free memory, that you should make sure that no pointers to it
will ever be used again.

Short of never free()ing any of your instances (a very bad idea),
or making sure to never reference a free()ed instance (a very good
idea), the only semi-bad solution I see would be to keep track of
all previously-allocated-but-now-freed addresses, and have your
allocate routine check if malloc returned one of them. If so,
keep malloc'ing until a non-previously-used address is returned,
and use that one. (And then free all of the "bad" ones, to keep
from having a memory leak.)

Of course, that "solution" just says "eww, yuck!" to me.

It sounds a little to me like the data structure is upside down, or
disconnected.

Can the list of pointers to objects manage the links to external references?

I would like to know more about the problem. Why do the external objects
have pointers to a list of things that may disappear? What do they do with
the pointers? Why are the external objects not members of the structs in
the pointer list (e.g as a linked list or something).

I think that the tracking homework is strangely designed and I think that
good answers to the questions will depend on why these foreign objects have
addresses of potentially disappearing objects. Do multiple external items
point to the same list object address? What do they use this address for?

How can an external object from the list tell the difference between a
pointer to an object originally allocated to them verses a pointer to a
similar object (allocated with the same address) but allocated for a
different set of external objects?

Er, what do you understand by external objects? If you mean the global
variable instList, this is the pointer to the whole list. When an
instance is to be freed, it is first removed from the list, and then
free()-d (see code). So all pointers in the list are always valid.
Unfortunately I cannot keep track of all copies of these pointers that
fly around in the application. Thats why the whole problem arises.

 

[avasilev]

Dann Corbit wrote: [...]

The simple act of examining the contents of the pointer that is storing
0xdeadbeef invokes undefined behavior. Your computer could dump core, or
Scott Nudds could come flying out of your left nostril. Really, it's
practically in the standard. At least comp.std.c made a similar remark
concerning demons some time ago.

No no, Im no examining the moemory that hte pointer points to, I am
simply comparing the values of the pointers themselves, i.e. I am
comparing the addresses, not the contents of the memory that is pointed
to.

Understood, but just examining the pointer value itself, without
dereferencing it, invokes undefined behavior.

Concretely:

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
void *ptr;
ptr = malloc(42);
printf("ptr = %p\n", ptr);
free(ptr);
printf("ptr = %p\n", ptr);
return 0;
}

The second printf call invokes UB (assuming the malloc() succeeded).

In real life, this is unlikely to cause any problems, but strictly
speaking a pointer to an object becomes indeterminate when the object
reaches the end of its lifetime.

Hmm, ok this means that the compiler may try to do something "hidden"
with this pointer, i.e. try to dereference it somehow? At the assembly
level a pointer is just a register value which can be manupulated just
as any other value, as long as no attempts are made to dereference it.
So do you mean that the C standard states that accessing the value of a
pointer to a freed object causes undefined behaviour?

 

[Dann Corbit]

[snip]

Unfortunately I cannot keep track of all copies of these pointers that
fly around in the application. Thats why the whole problem arises.

That is the gist of the problem, I think.

You need to devise a way so that you *can* track all of the copies of the
pointers that are flying around. Without that, you have a dangerous design.

IMO-YMMV.

 

[avasilev]

[snip]

Unfortunately I cannot keep track of all copies of these pointers that
fly around in the application. Thats why the whole problem arises.

That is the gist of the problem, I think.

You need to devise a way so that you *can* track all of the copies of the
pointers that are flying around. Without that, you have a dangerous design.

IMO-YMMV.

The design is of an already written application (not by me) and I have
to live with it. I just want to eveluate what i can expect from this
approach. If I had to implement it, I would use unique ID-s.

 

[avasilev]

Hi all,

my question is:

if i allocate some memory with malloc() and later free it (using
free()), is there a possibility that a consequent malloc() will
allocate memort at the same starting address and will return the same
pointer as the previous malloc(). I would like to have confirmation on
whether this is practically a concern when pointers are used to
uniquely identify data structure instances - like in this example:

int isInstanceValid(myStrict* inst)
{
int i;
for (i=0; i<instCount; ++i)
if (instances == inst)
return 1;

return 0;
}

In this example, if an instance is freed, and a pointer to it becomes
non-valid, and later a new structure is allocated in the list, the
function will return that the pointer is valid, although it is actually
not the instance that was originally referred.

Aside from everything else that's already been said: don't do this.

There is no way to detect whether a pointer is valid (in any sense of the
word) in portable C, and in most cases it's not feasible to do it in
unportable C either.

If you concerned about not deallocating things before their time is up, use
a garbage collector, like http://www.hpl.hp.com/personal/Hans_Boehm/gc/.

If you're concerned about sloppy programmers (possibly including yourself as
a culprit), then audit your code more closely, using tools like valgrind
(http://valgrind.org/) and Electric Fence
(http://perens.com/FreeSoftware/ElectricFence/).

If you want a unique identifier for an object, come up with one yourself,
and don't make it depend (exclusively) on its address. This is what the
concept of a handle is all about, although handles are subject to mistakes
like these too. You may be able to devise a handle allocation scheme that
will maximimze the time before reuse and hence increase the chance of
detecting an invalid handle.

The best even most external tools can do is increase the likelihood of
detecting an allocation bug. They cannot convince you there aren't any.

S.

Yes, I would use some sort of UID-s if I had to design it, but it is
already done, so I need to evaluate the current situation.

 

[Eric Sosman]

avasilev wrote On 07/14/06 16:56,:

[...]

//this is how we free an instance and remove it form the list
int delInst(myStruct* inst)
{
myStruct* cur = instList;
while (cur)
{
if (inst == cur)
{
/ /some code to remove from linked list goes here
free(cur);
return 1;
}
cur = cur->next;
}
return 0;
}

The only 100% reliable way to make this scheme work
is to remove the call to free() above. Others have pointed
out that any use of a free'd pointer, even a mere comparison,
produces undefined behavior -- and while this is correct, it
is mostly a "theoretical" concern. However, a "practical"
concern is that malloc() can and usually does re-use free'd
memory; malloc() can return the same non-NULL value N times.
(Because of the "theoretical" U.B., there is no safe way for
a program to detect this reliably, but as a "practical" matter
it does happen, and quite commonly.)

So: The only way to be sure malloc() never returns the
same value twice is never to free() anything. Of course,
this may have unwelcome consequences ...

 

[Dann Corbit]

[snip]

Unfortunately I cannot keep track of all copies of these pointers that
fly around in the application. Thats why the whole problem arises.

That is the gist of the problem, I think.

You need to devise a way so that you *can* track all of the copies of the
pointers that are flying around. Without that, you have a dangerous
design.

IMO-YMMV.

The design is of an already written application (not by me) and I have
to live with it. I just want to eveluate what i can expect from this
approach. If I had to implement it, I would use unique ID-s.

Perhaps it can be repaired.

If you can create a data structure that knows about both the object list and
all the objects that refer to it, you can do things like:
tag the non-list objects that use a particular list objects as invalid when
free() is called for that particular list object.

You could implement a reference counting scheme to know if someone is still
using an object so that it should not be freed.

 

[avasilev]

avasilev wrote On 07/14/06 16:56,:

[...]

//this is how we free an instance and remove it form the list
int delInst(myStruct* inst)
{
myStruct* cur = instList;
while (cur)
{
if (inst == cur)
{
/ /some code to remove from linked list goes here
free(cur);
return 1;
}
cur = cur->next;
}
return 0;
}

The only 100% reliable way to make this scheme work
is to remove the call to free() above. Others have pointed
out that any use of a free'd pointer, even a mere comparison,
produces undefined behavior -- and while this is correct, it
is mostly a "theoretical" concern. However, a "practical"
concern is that malloc() can and usually does re-use free'd
memory; malloc() can return the same non-NULL value N times.
(Because of the "theoretical" U.B., there is no safe way for
a program to detect this reliably, but as a "practical" matter
it does happen, and quite commonly.)

So: The only way to be sure malloc() never returns the
same value twice is never to free() anything. Of course,
this may have unwelcome consequences ...

Hm, thats the strange thing here - the code is part of a widely used
open source cross-patform library, which supports a huge diversity of
compilers and platforms. And this code works on all... So, as you say
it seems that the problem with reading a pointer to free-d memory
should be theoretical. But it is really interesting that nobody has
complained so far about this.

 

[avasilev]

[snip]
Unfortunately I cannot keep track of all copies of these pointers that
fly around in the application. Thats why the whole problem arises.

That is the gist of the problem, I think.

You need to devise a way so that you *can* track all of the copies of the
pointers that are flying around. Without that, you have a dangerous
design.

IMO-YMMV.

The design is of an already written application (not by me) and I have
to live with it. I just want to eveluate what i can expect from this
approach. If I had to implement it, I would use unique ID-s.

Perhaps it can be repaired.

If you can create a data structure that knows about both the object list and
all the objects that refer to it, you can do things like:
tag the non-list objects that use a particular list objects as invalid when
free() is called for that particular list object.

You could implement a reference counting scheme to know if someone is still
using an object so that it should not be freed.

Yes, your idea is good. However this mechanism is deeply in the core of
the library, and changing it wil lrequire a lot of efforts. Strangely
this has been working on numerous platforms and compilers - the code is
part of an opensource crosspatform library.

 

[Dann Corbit]

[snip]

Hm, thats the strange thing here - the code is part of a widely used
open source cross-patform library, which supports a huge diversity of
compilers and platforms. And this code works on all... So, as you say
it seems that the problem with reading a pointer to free-d memory
should be theoretical. But it is really interesting that nobody has
complained so far about this.

What open source tool kit did the code come from?

 

[avasilev]

[snip]

Hm, thats the strange thing here - the code is part of a widely used
open source cross-patform library, which supports a huge diversity of
compilers and platforms. And this code works on all... So, as you say
it seems that the problem with reading a pointer to free-d memory
should be theoretical. But it is really interesting that nobody has
complained so far about this.

What open source tool kit did the code come from?

iaxclient, in libiax2 - iax.c
This is the way sessions are handled.

 

[Keith Thompson]

Hmm, ok this means that the compiler may try to do something "hidden"
with this pointer, i.e. try to dereference it somehow? At the assembly
level a pointer is just a register value which can be manupulated just
as any other value, as long as no attempts are made to dereference it.
So do you mean that the C standard states that accessing the value of a
pointer to a freed object causes undefined behaviour?

Yes, exactly.

For example, suppose the CPU has special address registers and the
ability to check whether a given address is either valid or null
(i.e., a null pointer is valid, a pointer to an existing object is
valid, and any other pointer is invalid). It makes sense to do this
check as early as possible, i.e., when the address is loaded into an
address register. The standard is designed to make such an
implementation legal.

When you pass a pointer to free(), you're promising that you're
finished with it. By examining the value of the pointer later on,
you're breaking that promise, and the implementation is free to strike
down upon thee with great vengeance and furious anger -- or, if it's
in a good mood, merely to crash your program.

(Note that you can examine the *representation* of any object by
treating it as an array of unsigned char, and it's been persuasively
argued that free() cannot change the representation of a pointer --
but I wouldn't necessarily suggest taking advantage of that.)

 

[Gordon Burditt]

shouldnt be a problem, because if you're really keeping track of valid

Yes, but later I can allocate a new pointer and add it to the table, it
could happen to have the same value. Then a previously non-vaid pointer
becomes valid now.

If you keep freeing and reallocating chunks of memory, eventually
malloc() *MUST* either fail (return NULL) or return the same pointer
as it did before. Pointers have only a finite number of bits. If
pointers have 32 bits, you're guaranteed to have a repeat before
(2**32)+1 calls to malloc(), and possibly a lot sooner than that
if parts of the address space aren't used for dynamically allocated
memory.

Gordon L. Burditt

 

[Gordon Burditt]

Hmm, ok this means that the compiler may try to do something "hidden"

with this pointer, i.e. try to dereference it somehow?

On a rather obscure processor which I'm sure nobody ever heard of,
the Intel Pentium, in protected mode, if you load an invalid segment
(hint: part of a pointer in large memory model) into a segment
register, you may get a trap which likely maps to some kind of
signal or program abort.

On the other hand, it's not that unreasonable for a compiler to
generate code to load a pointer it's about to use (maybe) into a
segmentffset register pair once early since reloading it repeatedly
is expensive.

The processor might also leave a pointer around in a segment register
from when it was valid (before free() got called), then try to save
and restore the segment registers with push/pop instructions, so
you can get traps at odd times when the pointer with the invalid
value isn't apparently being used.

At the assembly
level a pointer is just a register value which can be manupulated just
as any other value, as long as no attempts are made to dereference it.

At the assembly level, you cannot put arbitrary bit patterns in the
segment registers without risking traps depending on the contents
of the corresponding segment table entry (which may well be changed
as the result of a malloc() or free() call). Get a manual on the
Intel Pentium and look it up. Oh, yes, the all-bits-zero segment
(a logical thing to use for NULL) is treated specially: it doesn't
cause a trap to load it in a segment register but it does if you
dereference it. It looks like Intel designed this with C (along
with other languages with null pointers) in mind.

So do you mean that the C standard states that accessing the value of a
pointer to a freed object causes undefined behaviour?

Yes. Guess what? The undefined behavior that happens occurs at
the assembly-language level in this case.

Gordon L. Burditt

 

[Snis Pilbor]

The design is of an already written application (not by me) and I have
to live with it. I just want to eveluate what i can expect from this
approach. If I had to implement it, I would use unique ID-s.

This might be a Herculean task for an already-written application, but
if I were writing one from scratch, rather than this unique ID
nonsense, what I like to do is write custom free functions for various
structures, for instance i have widgets and any given widget might have
pointers pointing to it from thingies or from other widgets. I might
write something like

void free_widget( struct widget *w )
{
struct widget *w2;
struct thingy *t;

for ( w2 = first_widget; w2; w2 = w2->next )
if ( w2->widgetpointer == w )
w2->widgetpointer = NULL;

for (t = first_thingy; t; t = t->next )
if ( t->widgetpointer == v )
t->widgetpointer = NULL;

free( w );
return;
}

Of course this is a very simple example since in practice it'd be more
likely that (for instance) each thingy would contain an entire linked
list of pointers to various widgets, etc. But you get the idea.

 

[robertwessel2]

On a rather obscure processor which I'm sure nobody ever heard of,
the Intel Pentium, in protected mode, if you load an invalid segment
(hint: part of a pointer in large memory model) into a segment
register, you may get a trap which likely maps to some kind of
signal or program abort.

On the other hand, it's not that unreasonable for a compiler to
generate code to load a pointer it's about to use (maybe) into a
segmentffset register pair once early since reloading it repeatedly
is expensive.

The processor might also leave a pointer around in a segment register
from when it was valid (before free() got called), then try to save
and restore the segment registers with push/pop instructions, so
you can get traps at odd times when the pointer with the invalid
value isn't apparently being used.


At the assembly level, you cannot put arbitrary bit patterns in the
segment registers without risking traps depending on the contents
of the corresponding segment table entry (which may well be changed
as the result of a malloc() or free() call). Get a manual on the
Intel Pentium and look it up. Oh, yes, the all-bits-zero segment
(a logical thing to use for NULL) is treated specially: it doesn't
cause a trap to load it in a segment register but it does if you
dereference it. It looks like Intel designed this with C (along
with other languages with null pointers) in mind.


Yes. Guess what? The undefined behavior that happens occurs at
the assembly-language level in this case.

And lest anyone think this is purely theoretical problem...

I know of a 16-bit compiler (not C) that passed the first few
parameters (of appropriate type) in registers, and the first two far
pointers were passed in es:di and ds:si (assuming those were
available). And yes, just passing a free'd pointer to a subroutine
would cause an abend.

OTOH, I don't know of any C compilers that did that. MS's 16 bit
register calling convention could pass near pointers in registers but
always passed far pointers on the stack.

 

[swengineer001]

This might be a Herculean task for an already-written application, but
if I were writing one from scratch, rather than this unique ID
nonsense, what I like to do is write custom free functions for various
structures, for instance i have widgets and any given widget might have
pointers pointing to it from thingies or from other widgets. I might
write something like

void free_widget( struct widget *w )
{
struct widget *w2;
struct thingy *t;

for ( w2 = first_widget; w2; w2 = w2->next )
if ( w2->widgetpointer == w )
w2->widgetpointer = NULL;

for (t = first_thingy; t; t = t->next )
if ( t->widgetpointer == v )
t->widgetpointer = NULL;

free( w );
return;
}

Of course this is a very simple example since in practice it'd be more
likely that (for instance) each thingy would contain an entire linked
list of pointers to various widgets, etc. But you get the idea.

I don't think this will help him. If he has multiple modules with a
pointer to an object and any one of them may free it at any time, with
a custom or non custom free, there is a design flaw that needs to be
fixed.

 

[=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?=]

Yes, but later I can allocate a new pointer and add it to the table, it
could happen to have the same value. Then a previously non-vaid pointer
becomes valid now.

And that's one of the reasons a function like you're trying to
implement is a rather futile approach.

 

[avasilev]

On a rather obscure processor which I'm sure nobody ever heard of,
the Intel Pentium, in protected mode, if you load an invalid segment
(hint: part of a pointer in large memory model) into a segment
register, you may get a trap which likely maps to some kind of
signal or program abort.

On the other hand, it's not that unreasonable for a compiler to
generate code to load a pointer it's about to use (maybe) into a
segmentffset register pair once early since reloading it repeatedly
is expensive.

The processor might also leave a pointer around in a segment register
from when it was valid (before free() got called), then try to save
and restore the segment registers with push/pop instructions, so
you can get traps at odd times when the pointer with the invalid
value isn't apparently being used.


At the assembly level, you cannot put arbitrary bit patterns in the
segment registers without risking traps depending on the contents
of the corresponding segment table entry (which may well be changed
as the result of a malloc() or free() call). Get a manual on the
Intel Pentium and look it up. Oh, yes, the all-bits-zero segment
(a logical thing to use for NULL) is treated specially: it doesn't
cause a trap to load it in a segment register but it does if you
dereference it. It looks like Intel designed this with C (along
with other languages with null pointers) in mind.


Yes. Guess what? The undefined behavior that happens occurs at
the assembly-language level in this case.

Gordon L. Burditt

Ok, I got your point - segment registers. The thing is that this
approach that I am discussing ia actually used in a opensource cross
platform library. It runs on *nix, windows and macos. Nobody had
problems with this, ar at least nobody fixed this so far. My point is -
these OS-es do not use segmentation for the memory model of user-mode
processes. So you are right in theory, but in practice this does not
happen. Dont get me wrong, I dont defent this approach, I'm very far
from it - if I had to design it I would use handles. But it is already
done.