[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2014-04-02
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
The analysis looks right. The static_cast is definitely undefined. You can't
dereference the end() iterator so we don't need a valid pointer, so the
reinterpret_cast is OK.

I'd like to be able to reproduce it though, the toy examples I've tried don't
get the ubsan error.

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[mpolacek at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mpolacek at gcc dot gnu.org

--- Comment #2 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Our ubsan does not yet detect the "downcast of address..." error.  Maybe in
next stage1.

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Thanks Marek, in that case this is less high priority IMHO

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Tue Apr 15 10:52:06 2014
New Revision: 209414

URL: http://gcc.gnu.org/viewcvs?rev=209414&root=gcc&view=rev
Log:
    PR libstdc++/60734
    * include/bits/stl_tree.h (_Rb_tree::_M_end): Fix invalid cast.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_tree.h

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed on trunk so far

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Tue Jun  3 17:26:05 2014
New Revision: 211190

URL: http://gcc.gnu.org/viewcvs?rev=211190&root=gcc&view=rev
Log:
Backport from mainline
2014-04-15  Jonathan Wakely  <jwakely@redhat.com>

    PR libstdc++/60734
    * include/bits/stl_tree.h (_Rb_tree::_M_end): Fix invalid cast.

Modified:
    branches/gcc-4_9-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_9-branch/libstdc++-v3/include/bits/stl_tree.h

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

--- Comment #7 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Tue Jun  3 17:58:51 2014
New Revision: 211197

URL: http://gcc.gnu.org/viewcvs?rev=211197&root=gcc&view=rev
Log:
Backport from mainline
2014-04-15  Jonathan Wakely  <jwakely@redhat.com>

    PR libstdc++/60734
    * include/bits/stl_tree.h (_Rb_tree::_M_end): Fix invalid cast.

Modified:
    branches/gcc-4_8-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_8-branch/libstdc++-v3/include/bits/stl_tree.h

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|---                         |4.8.4

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 4.8.4 and 4.9.1

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[bshastry at sec dot t-labs.tu-berlin.de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

Bhargava Shastry <bshastry at sec dot t-labs.tu-berlin.de> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bshastry at sec dot t-labs.tu-berl
                   |                            |in.de

--- Comment #9 from Bhargava Shastry <bshastry at sec dot t-labs.tu-berlin.de> ---
Hi. I just noticed that there are two more instances of the undefined downcast
via static_cast that are not fixed by the said patch.

### Lines borrowed from bits/stl_tree.h [gcc 5.1.0]

883.      iterator
884.      end() _GLIBCXX_NOEXCEPT
885.      { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header));
}
886.
887.      const_iterator
888.      end() const _GLIBCXX_NOEXCEPT
889.      {
890.        return const_iterator(static_cast<_Const_Link_type>
891.                              (&this->_M_impl._M_header));
892.      }

The undefined casts happen on line 885 and 890--891.

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |---

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Yes, there are a few remaining. I changed the code on trunk to avoid all those
casts completely.

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #11 from Jonathan Wakely <redi at gcc dot gnu.org> ---
In fact I also already fixed it on the gcc-5 branch, see r223811. The 5.1.0
sources are not current.

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[bshastry at sec dot t-labs.tu-berlin.de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

--- Comment #12 from Bhargava Shastry <bshastry at sec dot t-labs.tu-berlin.de> ---
Also, I noticed a couple of potentially suspicious casts not fixed upstream.
They are in _S_right [1] and elsewhere.

The problem I see is this:
a. _M_right is a pointer to an object of type _Rb_tree_node_base
b. _Link_type is a pointer to an object of type _Rb_tree_node<_Val> that is
derived from _Rb_tree_node_base
b. _M_right points to an object of type _Rb_tree_node_base in init() [2] and
reset() [3]

a) and b) together imply that it is possible that _M_right points to an object
of type _Rb_tree_node_base when cast to _Link_type in [1]. Is this a matter for
concern?


[1]:
https://gcc.gnu.org/viewcvs/gcc/branches/gcc-5-branch/libstdc%2B%2B-v3/include/bits/stl_tree.h?view=markup&pathrev=223811#l685
[2]:
https://gcc.gnu.org/viewcvs/gcc/branches/gcc-5-branch/libstdc%2B%2B-v3/include/bits/stl_tree.h?view=markup&pathrev=223811#l614
[3]:
https://gcc.gnu.org/viewcvs/gcc/branches/gcc-5-branch/libstdc%2B%2B-v3/include/bits/stl_tree.h?view=markup&pathrev=223811#l604

[Bug libstdc++/60734] Undefined behavior in g++-v4/bits/stl_tree.h

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60734

--- Comment #13 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Bhargava Shastry from comment #12)
> a) and b) together imply that it is possible that _M_right points to an
> object of type _Rb_tree_node_base when cast to _Link_type in [1]. Is this a
> matter for concern?

Not especially, because we never dereference it except when it really does
point to the derived type.

We might be able to replace those with reinterpret_cast, or just return the
base pointer and delay the cast until needed.