 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Matthias Hofmann
Guest
|
 Posted: Mon Aug 08, 2005 7:51 pm Post subject: Using pointers as keys with std::map |
 |
|
Hello!
I am trying to implement a memory tracing mechanism which keeps an internal
database that maps pointers to allocation information, which is basically
the name and line of the file where the memory was allocated.
I want to implement that database in terms of std::map, so I would like to
use pointers to void for the key and a class or struct of allocation
information for the value. The problem is, that there might be situations
when the memory tracing mechanism has to compare pointers to storage that
has already been deallocated.
As far as I know, the only thing you can do to a singular pointer is assign
a valid pointer to it. Therefore, I have to make sure that all pointers that
are handled by the memory tracing mechanism are non-singular.
I want the code to be as portable as possible, and the only solution seems
to be a reinterpret_cast from void* to unsigned long and use unsigned long
for the key. However, this assumes that the resulting bit pattern is the
same, doesn't it? Besides, I don't know if casting a singular pointer does
not lead to undefined behaviour itself.
If this does not work, then I will have to define singular pointer values
out of existence and rely on clients of my code to avoid errors. Calling
delete twice on the same pointer would cause such problems, for example, but
this leads to undefined behaviour anyway.
Or is there an exception to that singularity-rule for pointers of type void?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Jeff Schwab
Guest
|
| Posted: Tue Aug 09, 2005 8:20 am Post subject: Re: Using pointers as keys with std::map |
|
|
Matthias Hofmann wrote:
| Quote: | Hello!
I am trying to implement a memory tracing mechanism which keeps an internal
database that maps pointers to allocation information, which is basically
the name and line of the file where the memory was allocated.
I want to implement that database in terms of std::map, so I would like to
use pointers to void for the key and a class or struct of allocation
information for the value. The problem is, that there might be situations
when the memory tracing mechanism has to compare pointers to storage that
has already been deallocated.
As far as I know, the only thing you can do to a singular pointer is assign
a valid pointer to it. Therefore, I have to make sure that all pointers that
are handled by the memory tracing mechanism are non-singular.
I want the code to be as portable as possible, and the only solution seems
to be a reinterpret_cast from void* to unsigned long and use unsigned long
for the key. However, this assumes that the resulting bit pattern is the
same, doesn't it? Besides, I don't know if casting a singular pointer does
not lead to undefined behaviour itself.
If this does not work, then I will have to define singular pointer values
out of existence and rely on clients of my code to avoid errors. Calling
delete twice on the same pointer would cause such problems, for example, but
this leads to undefined behaviour anyway.
Or is there an exception to that singularity-rule for pointers of type void?
|
Could you use pointers to singular pointers as your map keys, rather
than the singular pointers themselves? E.g:
#include <iostream>
#include <map>
#include <vector>
struct Allocation_info { /* ... */ };
struct My_malloc {
void* operator () (std::size_t size);
Allocation_info info(void**);
private:
std::vector<void*> m_returned_pointers;
std::map<void**, Allocation_info> m_map;
};
int main() {
My_malloc my_malloc;
void* p = my_malloc(42);
std::free(p);
Allocation_info ai = my_malloc.info(&p);
}
void* My_malloc::operator () (std::size_t size) {
void* p = malloc(size);
m_returned_pointers.push_back(p);
m_map[&p] = Allocation_info( /*...*/ );
return p;
}
Allocation_info My_malloc::info(void** pp) {
return m_map[pp];
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Matthias Hofmann
Guest
|
| Posted: Tue Aug 09, 2005 1:49 pm Post subject: Re: Using pointers as keys with std::map |
|
|
"Jeff Schwab" <jeffrey.schwab (AT) rcn (DOT) com> schrieb im Newsbeitrag
news:7KednVX2JfZrv2XfRVn-3A (AT) rcn (DOT) net...
| Quote: | Could you use pointers to singular pointers as your map keys, rather
than the singular pointers themselves? E.g:
|
But how would this help me? Sooner or later I would have to dereference
these pointers in order to get the singular pointer, and then I would face
the same problem again.
| Quote: | void* My_malloc::operator () (std::size_t size) {
void* p = malloc(size);
m_returned_pointers.push_back(p);
m_map[&p] = Allocation_info( /*...*/ );
return p;
}
|
I am a little confused by the following line:
m_map[&p] = Allocation_info( /*...*/ );
This will use a stack address for the key. What sense does that make?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Pete Becker
Guest
|
| Posted: Tue Aug 09, 2005 3:42 pm Post subject: Re: Using pointers as keys with std::map |
|
|
Matthias Hofmann wrote:
| Quote: |
I want the code to be as portable as possible, and the only solution seems
to be a reinterpret_cast from void* to unsigned long and use unsigned long
for the key. However, this assumes that the resulting bit pattern is the
same, doesn't it? Besides, I don't know if casting a singular pointer does
not lead to undefined behaviour itself.
|
Don't confuse "undefined behavior" with "should never be used." You're
right to want to make your code as portable as possible. Memory mangers
are inherently non-portable. Just compare the pointers.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Carlos Moreno
Guest
|
| Posted: Tue Aug 09, 2005 7:17 pm Post subject: Re: Using pointers as keys with std::map |
|
|
Matthias Hofmann wrote:
| Quote: | "Jeff Schwab" <jeffrey.schwab (AT) rcn (DOT) com> schrieb im Newsbeitrag
news:7KednVX2JfZrv2XfRVn-3A (AT) rcn (DOT) net...
Could you use pointers to singular pointers as your map keys, rather
than the singular pointers themselves? E.g:
But how would this help me? Sooner or later I would have to dereference
these pointers in order to get the singular pointer, and then I would face
the same problem again.
|
The way I understood your problem, trouble arises when looking up
an element (i.e., when using one of your pointers as a key for the
std::map), since a mere read access of the value of the pointer
involves undefined behaviour. I assumed (and still do) that you
would have a separate mechanism to know when a pointer has been
deleted (i.e., when a pointer is no longer pointing to allocated
memory), and proceed accordingly.
I mean, how else could you do? If you are given a pointer with no
other piece of information whatsoever, and the pointer may or may
not have been deleted, then there is absolutely nothing that you
can do to determine if you can use the pointer (I mean, strictly
speaking -- using platform-specific tricks, I'm sure there may be
plenty of ways).
The extra level of indirection allows your map indexing to work
without invoking UB, since *all* the pointers that you use as keys
for the map are valid pointers. Now, whether or not you dereference
them, you need to know that (but you also needed to know that in
your original formulation -- if not, then you would have to
re-think/re-design what you're doing, because it would sound to
me like an ill-formed problem).
HTH, although I may be misunderstanding part of the problem.
Carlos
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Marco Manfredini
Guest
|
| Posted: Wed Aug 10, 2005 12:15 pm Post subject: Re: Using pointers as keys with std::map |
|
|
Matthias Hofmann wrote:
| Quote: | I want the code to be as portable as possible, and the only solution
seems to be a reinterpret_cast from void* to unsigned long and use
unsigned long for the key. However, this assumes that the resulting
bit pattern is the same, doesn't it?
|
5.2.10-5 tells us that a integral type got from a reinterpret_cast can
safely be reinterpret_cast'ed back to the original pointer type. It
doesn't say however, if the integral type representation of a pointer
type is unique, only that the representation should be /unsurprising/.
| Quote: | Or is there an exception to that singularity-rule for pointers of type
void?
|
void* is defined to be a pointer to an object of unknown type, which
suggests that void*, contrary to its literal reading, may not point to
no object.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Matthias Hofmann
Guest
|
| Posted: Thu Aug 11, 2005 12:50 pm Post subject: Re: Using pointers as keys with std::map |
|
|
"Marco Manfredini" <ok_nospam_ok (AT) phoyd (DOT) net> schrieb im Newsbeitrag
news:3520805.e2i6zxtN1g (AT) technoboredom (DOT) net...
| Quote: | void* is defined to be a pointer to an object of unknown type, which
suggests that void*, contrary to its literal reading, may not point to
no object.
|
I see. But is it a good idea to use them as a key for std::map in my memory
tracing mechanism? The question is whether each pointer of type T will still
be unique after it has been cast to a pointer of type void?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Matthias Hofmann
Guest
|
| Posted: Thu Aug 11, 2005 12:51 pm Post subject: Re: Using pointers as keys with std::map |
|
|
"Pete Becker" <petebecker (AT) acm (DOT) org> schrieb im Newsbeitrag
news:WPidnTYB2u6yJGXfRVn-pA (AT) giganews (DOT) com...
| Quote: | Don't confuse "undefined behavior" with "should never be used." You're
right to want to make your code as portable as possible. Memory mangers
are inherently non-portable. Just compare the pointers.
|
I think it is possible to write a portable memory tracing mechanism.
However, its possibilities will be limited due to those portability
problems.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Matthias Hofmann
Guest
|
| Posted: Thu Aug 11, 2005 12:53 pm Post subject: Re: Using pointers as keys with std::map |
|
|
"Carlos Moreno" <moreno_at_mochima_dot_com (AT) xx (DOT) xxx> schrieb im Newsbeitrag
news:h94Ke.18340$651.903558 (AT) weber (DOT) videotron.net...
| Quote: | The way I understood your problem, trouble arises when looking up
an element (i.e., when using one of your pointers as a key for the
std::map), since a mere read access of the value of the pointer
involves undefined behaviour. I assumed (and still do) that you
would have a separate mechanism to know when a pointer has been
deleted (i.e., when a pointer is no longer pointing to allocated
memory), and proceed accordingly.
|
You got the point. However, the mechanism to know when a pointer has been
deleted is to search for it in a std::map. As you have already noticed, that
may involve undefined behaviour.
| Quote: | I mean, how else could you do? If you are given a pointer with no
other piece of information whatsoever, and the pointer may or may
not have been deleted, then there is absolutely nothing that you
can do to determine if you can use the pointer (I mean, strictly
speaking -- using platform-specific tricks, I'm sure there may be
plenty of ways).
|
Actually the only platform I am currently using is Windows on Intel or
compatible PCs, where a pointer is not too much different from other
fundamental data types. For example, read access to singular pointers does
not cause any problems, but I would still prefer a portable way.
| Quote: | The extra level of indirection allows your map indexing to work
without invoking UB, since *all* the pointers that you use as keys
for the map are valid pointers. Now, whether or not you dereference
them, you need to know that (but you also needed to know that in
your original formulation -- if not, then you would have to
re-think/re-design what you're doing, because it would sound to
me like an ill-formed problem).
|
Maybe my problem is ill-formed. If so, then it is probably because I am
trying to handle errors in client code that, according to the standard, lead
to undefined behaviour anyway. The best example would be deleting a pointer
twice: When the pointer is deleted for the first time, it is not a singular
one yet. It will still be in my database, be removed from there and finally
the memory will be deallocated. The second time the pointer is deleted,
however, it will not be in the database anymore. For that reason, I want to
write an appropriate warning to a log file. But this involves undefined
behaviour, because I cannot use the pointer as a key for std::map anymore.
It seems like the best solution would be to make everything that is
undefined behaviour in the core language be undefined behaviour in my memory
tracing mechanism as well.
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Marco Manfredini
Guest
|
| Posted: Thu Aug 11, 2005 5:41 pm Post subject: Re: Using pointers as keys with std::map |
|
|
Matthias Hofmann wrote:
| Quote: | "Marco Manfredini" <ok_nospam_ok (AT) phoyd (DOT) net> schrieb im Newsbeitrag
news:3520805.e2i6zxtN1g (AT) technoboredom (DOT) net...
void* is defined to be a pointer to an object of unknown type, which
suggests that void*, contrary to its literal reading, may not point
to no object.
I see. But is it a good idea to use them as a key for std::map in my
memory tracing mechanism? The question is whether each pointer of type
T will still be unique after it has been cast to a pointer of type
void?
|
The standard says only, that converting the integral back will work and
nothing else. So technically one could expect reinterpret_cast to
return different numbers for the same pointer. A "safe" runtime for
example might encode a location information into the integral value (of
adequate size) to make error tracking easier.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Greg
Guest
|
| Posted: Fri Aug 12, 2005 9:03 am Post subject: Re: Using pointers as keys with std::map |
|
|
Matthias Hofmann wrote:
| Quote: | "Marco Manfredini" <ok_nospam_ok (AT) phoyd (DOT) net> schrieb im Newsbeitrag
news:3520805.e2i6zxtN1g (AT) technoboredom (DOT) net...
void* is defined to be a pointer to an object of unknown type, which
suggests that void*, contrary to its literal reading, may not point to
no object.
I see. But is it a good idea to use them as a key for std::map in my memory
tracing mechanism? The question is whether each pointer of type T will still
be unique after it has been cast to a pointer of type void?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
|
There should be no problem using void pointers as keys in a std::map.
The map can freely compare a void pointer with any other void pointer
or with a pointer to an object (since such a pointer implicitly
converts to a void pointer for the comparison) when it needs to compare
and rank its keys.
Since the map's pointers are never dereferenced and all were (and still
may be) pointing to allocated memory, then the results of the
comparison will be consistent. The fact that the memory referenced by
either pointer may have been deallocated changes nothing about the
pointer comparison.
The only proviso of course is that this map is constructed at runtime
and is not saved and restored from disk.
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Matthias Hofmann
Guest
|
| Posted: Fri Aug 12, 2005 8:14 pm Post subject: Re: Using pointers as keys with std::map |
|
|
"Greg" <greghe (AT) pacbell (DOT) net> schrieb im Newsbeitrag
news:1123812644.268604.126400 (AT) g14g2000cwa (DOT) googlegroups.com...
| Quote: | There should be no problem using void pointers as keys in a std::map.
The map can freely compare a void pointer with any other void pointer
or with a pointer to an object (since such a pointer implicitly
converts to a void pointer for the comparison) when it needs to compare
and rank its keys.
|
Does that mean that all pointers are implicitly converted to void* for
comparisons? Can you please refer me to the relevant section in the
standard?
| Quote: | Since the map's pointers are never dereferenced and all were (and still
may be) pointing to allocated memory, then the results of the
comparison will be consistent. The fact that the memory referenced by
either pointer may have been deallocated changes nothing about the
pointer comparison.
|
Does that mean that there are no singular pointers of type void? If so, then
read access would always be allowed for them?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Matthias Hofmann
Guest
|
| Posted: Fri Aug 12, 2005 8:14 pm Post subject: Re: Using pointers as keys with std::map |
|
|
"Marco Manfredini" <ok_nospam_ok (AT) phoyd (DOT) net> schrieb im Newsbeitrag
news:3868800.eR0p5CecQJ (AT) technoboredom (DOT) net...
| Quote: | The standard says only, that converting the integral back will work and
nothing else. So technically one could expect reinterpret_cast to
return different numbers for the same pointer. A "safe" runtime for
example might encode a location information into the integral value (of
adequate size) to make error tracking easier.
|
And what about implicitly converting a pointer of type T to a pointer of
type void? Is it actually possible to apply std::less to compare pointers of
type void, as is required for comparisons?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Horacio J. Peņa
Guest
|
| Posted: Sat Aug 13, 2005 1:14 am Post subject: Re: Using pointers as keys with std::map |
|
|
| Quote: | Since the map's pointers are never dereferenced and all were (and still
may be) pointing to allocated memory, then the results of the
comparison will be consistent. The fact that the memory referenced by
either pointer may have been deallocated changes nothing about the
pointer comparison.
|
There were several discussions about this and the conclusion was that:
T* p = new T;
T* p2 = new T;
delete p;
if (p==p2) {
...
}
Involves undefined behaviour. I'd think that casting the pointers to
void* won't change that.
Saludos,
HoraPe
---
Horacio J. Peņa
[email]horape (AT) compendium (DOT) com.ar[/email]
[email]horape (AT) uninet (DOT) edu[/email]
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Greg
Guest
|
| Posted: Sat Aug 13, 2005 1:39 am Post subject: Re: Using pointers as keys with std::map |
|
|
Matthias Hofmann wrote:
| Quote: | "Greg" <greghe (AT) pacbell (DOT) net> schrieb im Newsbeitrag
news:1123812644.268604.126400 (AT) g14g2000cwa (DOT) googlegroups.com...
There should be no problem using void pointers as keys in a std::map.
The map can freely compare a void pointer with any other void pointer
or with a pointer to an object (since such a pointer implicitly
converts to a void pointer for the comparison) when it needs to compare
and rank its keys.
Does that mean that all pointers are implicitly converted to void* for
comparisons? Can you please refer me to the relevant section in the
standard?
|
No, not all pointers implicitly convert to void pointers. A member
function pointer in fact cannot be converted to a void pointer at all.
But all of the pointers used as keys in the map required for the memory
tracking implementation would convert to void pointers, because they
would all be object pointers (see 4.10.2 for implicit conversions, and
5.9.2 for pointer comparisons).
| Quote: | Since the map's pointers are never dereferenced and all were (and still
may be) pointing to allocated memory, then the results of the
comparison will be consistent. The fact that the memory referenced by
either pointer may have been deallocated changes nothing about the
pointer comparison.
Does that mean that there are no singular pointers of type void? If so, then
read access would always be allowed for them?
--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Klomanager
http://www.anvil-soft.de - Die Macher des Klomanagers
|
It is always safe to read the value of a void pointer, just as it is
safe to read the value of any variable. Accessing the memory address to
which a pointer points, however, is a different matter.
It is not safe to read memory at an address a pointer points to if the
memory at that address has been deallocated (or has never been
allocated). Remember that to access memory the pointer points to, it is
necessary to dereference the pointer. But comparing two pointers never
dereferences either pointer. Only the memory addresses that each
pointer stores are used to compare them. (Think about this comparison
on a logical basis: the comparison operation is compiled into the code.
The compiled code has no way of knowing whether the pointers it is
comparing point to allocated memory. The outcome of the comparison will
be the same regardless.)
It is also safe to conclude that a std::map will never dereference a
pointer used as a key. All that std::map ever does with a key is to
compare it with other keys so it can keep its stored values in a sorted
order.
The only chance that a pointer to a non-allocated memory address would
be dereferenced in this memory tracking routine, would be if the
tracking routine took it upon itself to do so. But the tracking routine
should have no motive to do so, at least as I understand its purpose.
Since the goal is simply to track allocations by their point of
allocation in the source code, the contents of each allocated block
should be irrelevant. On the other hand, if the tracking routine wishes
to dump the contents of these blocks, perhaps for diagnostic purposes,
then it would have to ensure that each block it dumped was still
allocated; or it would have to resort to OS specific facilities for
dealing with memory management and debugging.
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
