Sign in to follow this  
mfawcett

Unity Dangling pointers in containers (undefined behavior)

Recommended Posts

mfawcett    373
This is just a nit-picky post, mostly to Zahlman and MaulingMonkey. I have rated both of you up in the past as I have always found you two to be very helpful, so don't take offense to the post, I'm merely trying to get to the bottom of this. I would have replied to the original thread that started this discussion but I was away on business and it was closed by the time I got back. I recently saw a new post on c.l.c++.m that again discusses the fact that leaving a dangling pointer in a std container is undefined behavior (I say "again discussing" because, like I brought up in the original thread, this comes up rather often there, always with the same result - "it is undefined behavior"). Now in practice I almost always use smart pointers within my containers, so I never have to worry about this, and when there are raw pointers, yes, I use the function object and std::for_each idiom. In reply to MaulingMonkey's last post, where he stated "given that dangling pointers within containers are legal and well defined behavior so long as they are not dereferenced", I believe the issue is that the standard says the only legal thing you can do with a dangling pointer is assign it a new (valid) value. Any other "use" of the pointer is undefned, and even an rvalue to lvalue conversion is considered use, it does not have to be dereferenced, merely used. Thoughts? [Edited by - mfawcett on March 19, 2007 9:37:44 AM]

Share this post


Link to post
Share on other sites
Vorpy    869
After reading that last thread, I was under the impression that this "dangling pointers in containers result in undefined behavior" was possibly a misunderstanding of the standard. The standard talks about uninitialized pointers having a "singular value" or something like that. Unless you're putting uninitialized pointers in your container, the result isn't going to be undefined. You end up with a well defined dangling pointer. As far as I know, copying a dangling pointer is a well defined operation.

The issue is this: Is copying an invalid pointer an undefined operation? The standard (according to a post in the other thread) says that use of an invalid pointer is undefined, but I don't believe that copying the value of the pointer counts as use of that pointer. An invalid pointer is not necessarily a "singular value" (undefined value).

Share this post


Link to post
Share on other sites
mfawcett    373
Well, the singular value thing was my fault. I posted an irrelevant section of the standard. The second quote was the correct one, I believe.

3.7.3.2 paragraph 4
"...The effect of using an invalid pointer value (including passing it to a deallocation function) is undefined.33)"

"Using" does not only mean dereferencing in my understanding. It means any use other than:

my_dangling_ptr = 0;
// or
my_dangling_ptr = valid_ptr;

which, as far as I can tell, is the only legal thing you can do with a dangling pointer.

Share this post


Link to post
Share on other sites
rip-off    10979
I'm not going to quote standards, as I don't have access to a copy, but I cannot see the point you are making in that thread.

Even the pendant in me cannot see the point you are making. [smile] The deletion of each pointer in the container would only result in undefined behaviour were it not cleared afterwards.


Whatever about a small thinking point at the end of that other thread, but to devote an entire thread to this "topic"...

I think I could sleep at night were I to use the delete-the-pointers-then-clear method. [grin]

Share this post


Link to post
Share on other sites
mfawcett    373
Quote:
Original post by rip-off
Whatever about a small thinking point at the end of that other thread, but to devote an entire thread to this "topic"...

I think I could sleep at night were I to use the delete-the-pointers-then-clear method. [grin]


I know, I know, but I couldn't reply since the thread was dead. Defintely didn't deserve an entire thread, sorry about that.

Share this post


Link to post
Share on other sites
MaulingMonkey    1730
I'd much rather completely waste my time on something else than revisit this.

Or do something useful like working on my replacement for the FUBAR that is C++.

Presuming for a second that it is undefined behavior, I'm going to propose that each of the following is more likely to be a problem:

1) The workaround to avoid the behavior accidentally invoking significant undefined behavior
2) Death due to bus collision related injuries
3) Death due to llama related injuries
4) Death due to a world war caused by significant undefined behavior

In conclusion, the issue at stake would be a defect in the standard rather than that of any code IMO. Regardless, this has since fallen out of my Cone of Caring.

Share this post


Link to post
Share on other sites
Washu    7829
This is actually a problem throughout the standard, it has a tendency to be relatively vuage about certain points that leads to questionably defined behavior (and questionably undefined behavior). One thing we can note though is how it deals with pointers that are explicitly outside of the range of valid values for an object: that is, given an object o, and a pointer p such that p = &o, then p+1 points one past o and is a valid pointer, but p+2 is not only an invalid pointer, but results in undefined behavior. Applying this same context to a dangling pointer, one could show that doing anything with the dangling pointer (with the exception of reassignment) is also undefined behavior, since it points outside of the range of legal values.

In reality, C++0x should hopefully clear this up somewhat, but I haven't actually seen any efforts to do such (mostly just library work with a little language work to get the libraries working).

Share this post


Link to post
Share on other sites
mfawcett    373
I agree with you MaulingMonkey, which is why I tried to caveat every post with "in practice it's not an issue", or "in my own code I don't even worry about this" type phrases. Your tone is less than pleasant, however.

Thank you, Washu, for a very nice reply.

Share this post


Link to post
Share on other sites
Enigma    1410
Quote:
Original post by mfawcett
Well, the singular value thing was my fault. I posted an irrelevant section of the standard. The second quote was the correct one, I believe.

3.7.3.2 paragraph 4
"...The effect of using an invalid pointer value (including passing it to a deallocation function) is undefined.33)"

"Using" does not only mean dereferencing in my understanding. It means any use other than:

my_dangling_ptr = 0;
// or
my_dangling_ptr = valid_ptr;

which, as far as I can tell, is the only legal thing you can do with a dangling pointer.


So your argument against dangling pointers in SC++L containers is (correct me if I'm wrong) that the containers are allowed to copy contained values at any time and that copying an invalid pointer value is undefined behaviour:
int * i = new int;
delete i;
int * j = i; // undefined behaviour.

Now riddle me this. If copying an invalid pointer value is undefined behaviour then why does the quoted section of the standard explicitly highlight that passing an invalid pointer value to a deallocation function is undefined? All of the standard deallocation functions take their parameters by value, so if copying an invalid pointer value was undefined behaviour then passing an invalid pointer value to a deallocation function would implicitly by undefined behaviour due to the pass-by-value. Furthermore, passing an invalid pointer value to any function that tooks its parameter by value would be undefined behaviour. So why did the standards committee feel it necessary to explicitly state "including passing it to a deallocation function"?

Nowhere does the C++ standard define "use", in the context of the above quote from the standard. Neither can I find any reasonable argument, based on any conceivable machine architecture, for copying an invalid pointer value to be undefined behaviour. Significant parts of the C++ standard are based on possible underlying architectures. The argument for pointers outside the [array, array + size] range being undefined can be seen in architectures with segment/offset based pointers and in pointer under/overflow. The argument about pointers with singular values is harder to see, but one can envisage an architecture where pointers are specially handled on the hardware level and as such have certain constraints which may be violated by copying an uninitialised pointer. I can see no reasonable argument for copying a pointer value which was known to be valid at a previous point in time to be undefined behaviour, nor can I find any clear justification in the standard for it to be.

I'm quite prepared to be proven wrong, but I'm afraid I'm going to require you to be far more persuasive than you have been so far.

Σnigma

Share this post


Link to post
Share on other sites
mfawcett    373
Quote:
Original post by Enigma
Neither can I find any reasonable argument, based on any conceivable machine architecture, for copying an invalid pointer value to be undefined behaviour.

Nor I, and I doubt anyone could. This wasn't a discussion about it being sensible or not, merely whether it was so.

Quote:
Original post by Enigma
I'm quite prepared to be proven wrong, but I'm afraid I'm going to require you to be far more persuasive than you have been so far.


I'm not enough of an expert to persuade you. My evidence would simply be to point you at the newsgroups to view what the experts there have said, but there seems to be a bit of contention there too, with a few parties arguing that it's not UB.

For instance, here is a quote from James Kanze:

"Formally, I think that even those have undefined behavior. You
have to remove the pointer from the container in some way
(removing the element or changing its value) *before* the
delete. The simple presence of the pointer in the container
after delete is undefined behavior..."

and Seungbeom Kim:

"Except when the pointer is in a container, in which case you have to
explicitly set the pointer to null to avoid undefined behaviour..."


Do you see any harm in simply defining a delete_ptr struct as so?

struct delete_ptr
{
template <typename T>
void operator()(const T *&ptr) const
{
delete ptr;
ptr = 0;
}
};
std::for_each(vec.begin(), vec.end(), delete_ptr());


Regardless, I really tried to preface all my posts saying that "in practice this is not an issue", so I'm not sure where all of the aggressiveness is coming from.

Signed,

Merely Interested In The Standard, Not Interested In A Fight.

Share this post


Link to post
Share on other sites
MaulingMonkey    1730
Quote:
Original post by mfawcett
I agree with you MaulingMonkey, which is why I tried to caveat every post with "in practice it's not an issue", or "in my own code I don't even worry about this" type phrases. Your tone is less than pleasant, however.


If you've expected pleasantries from me, it's clear you've confused me with some other monkey. Monkey Jesus, prehaps. Or Monkey Budah.


There's a reason my nick isn't MassagingMonkey.


That said, given that I've linked one of my favorite webcomics for relevant humor, sharing this possibly previously unknown (to you) gem of humor (as it is in my opinion), I'm left wondering why my above-par jollyness is interpreted as sub-par compared to the expected.


I replied to this post as a result of being named in the original post. I felt a post detailing why I would not continue the discussion to be relevant, and so it was supplied. Do with it what you will. I've already stated what I'll do.

Share this post


Link to post
Share on other sites
Sharlin    864
I'm not sure whether the Standard can specify any stronger guarantees regarding singular/dangling pointers without needlessly limiting the range of potential hardware on which a C++ program can be run.

For instance, I can certainly imagine a security-enhanced CPU where the mere act of loading an invalid(* pointer to a register triggers a hardware trap or an interrupt, specifically to catch unitialized pointers before doing something much worse, such as using them as jump addresses.

*) an invalid bit pattern, or a value outside of the memory allocated for the process.

Share this post


Link to post
Share on other sites
Winograd    380
Quote:
Original post by Sharlin
I'm not sure whether the Standard can specify any stronger guarantees regarding singular/dangling pointers without needlessly limiting the range of potential hardware on which a C++ program can be run.

For instance, I can certainly imagine a security-enhanced CPU where the mere act of loading an invalid(* pointer to a register triggers a hardware trap or an interrupt, specifically to catch unitialized pointers before doing something much worse, such as using them as jump addresses.

*) an invalid bit pattern, or a value outside of the memory allocated for the process.


As far as I see, such register would have to be dedicated to memory addresses only and thus needed to be used only when accessing memory indirectly through it. A compiler backend could store the pointer in a general purpose register until the pointer would actually be dereferenced.

Share this post


Link to post
Share on other sites
Julian90    736
Look up the section on reinterprete_cast<>() in the standard im pretty sure it uses the same wording, however i dont have a copy to check, and its a similar context hence since im pretty sure its valid to copy the result of reinterprete_cast id say copying a dangling pointer is valid.

Of course if im wrong about what the standard says on reinterprete_cast<>() then just ignore me :)

Share this post


Link to post
Share on other sites
mfawcett    373
Quote:
Original post by Julian90
Look up the section on reinterprete_cast<>() in the standard im pretty sure it uses the same wording, however i dont have a copy to check, and its a similar context hence since im pretty sure its valid to copy the result of reinterprete_cast id say copying a dangling pointer is valid.

Of course if im wrong about what the standard says on reinterprete_cast<>() then just ignore me :)


I looked up the section. From what I can tell, the result of reinterpret_cast can either be specified, unspecified, implementation defined, or result in UB. It says nothing about what happens when you copy those values, just that the cast will result in one of the 4 behaviors.

Share this post


Link to post
Share on other sites
mfawcett    373
Quote:
Original post by MaulingMonkey
That said, given that I've linked one of my favorite webcomics for relevant humor, sharing this possibly previously unknown (to you) gem of humor (as it is in my opinion), I'm left wondering why my above-par jollyness is interpreted as sub-par compared to the expected.


I replied to this post as a result of being named in the original post. I felt a post detailing why I would not continue the discussion to be relevant, and so it was supplied. Do with it what you will. I've already stated what I'll do.


Apologies, I must have read into something from your post that wasn't there. That's the Internet for you...

Share this post


Link to post
Share on other sites
mfawcett    373
Quote:
Original post by Enigma
So your argument against dangling pointers in SC++L containers is (correct me if I'm wrong) that the containers are allowed to copy contained values at any time and that copying an invalid pointer value is undefined behaviour:
int * i = new int;
delete i;
int * j = i; // undefined behaviour.



Yes, apparently even the C standard says so.
This thread details it.

*Any* use other than assignment is UB. That means that an invalid pointer is not copyable.

Apparently there have also been architectures that existed(still exist?) where copying an invalid pointer did lead to a hardware trap. (I did not know about this until recently).

Quote:
Original post by Enigma
I'm quite prepared to be proven wrong, but I'm afraid I'm going to require you to be far more persuasive than you have been so far.


STD Containers require their elements be Copyable and Assignable. They do not specify time constraints as to when that might be, so that means the elements must be Copyable and Assignable always (when in the container). The moment you delete a pointer that still exists in a container, you have UB, regardless if immediately after you do a clear().

The temporary in my code was for that specific reason.

T *ptr = vec.back();
vec.pop_back();
delete ptr;


It *did* serve a purpose.

Share this post


Link to post
Share on other sites
Enigma    1410
I agree with you that SC++L containers require CopyConstructible and Assignable elements. I disagree that the C++ Standard states that a deleted pointer value is not CopyConstructible or Assignable. The thread you linked to quotes from the C99 standard. In C99 it seems quite clear that copying a deleted pointer value is undefined behaviour. In C89 it could be argued that copying a deleted pointer value is undefined behaviour (based on the draft copy I read). The C++ Standard, which was based on the C89 standard contains nothing that I can find to suggest that copying a deleted pointer value is undefined behaviour. This may be a defect in the C++ Standard, but I have yet to see a convincing argument for copying a pointer with indeterminate value to be undefined behaviour in C++.

In fact just looking again the C++ standard even contains an example when an object (not a pointer) with indeterminate value is copied, and no reference is made to this being undefined behaviour:
Quote:
C++ Standard, Section 3.3.1, Paragraph 1
The point of declaration for a name is immediately after its complete declarator (clause 8) and before its initializer (if any), except as noted below. [Example:

   int x = 12;
   { int x = x; }

Here the second x is initialized with its own (indeterminate) value. ]

Σnigma

Share this post


Link to post
Share on other sites
mfawcett    373
4.1p1 (Lvalue to rvalue conversions): "If the object to which the lvalue refers ... is uninitialized, a program that necessitates this conversion has undefined behavior."

That's only in reference to your latest post. I don't think it has bearing on invalid pointers, but I could be mistaken.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this