[Bug libstdc++/66017] New: Undefined behaviour in std::set<long long>

[Bug libstdc++/66017] New: Undefined behaviour in std::set<long long>

[public at hansmi dot ch]

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

            Bug ID: 66017
           Summary: Undefined behaviour in std::set<long long>
           Product: gcc
           Version: 5.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: public at hansmi dot ch
  Target Milestone: ---

Created attachment 35463
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35463&action=edit
Test program and output after building with Clang 3.6 (using GCC toolchain
5.1.0)

When building for Linux x86 (Debian 8 (Jessie), 32 bit) using `long long' as
std::set's value type causes UBSan as included in Clang 3.5 and 3.6 to report
an downcast/upcast of a misaligned address at runtime and ASan to report
undefined behaviour, all of them in _Rb_tree.

The simplest example I could find:

---
#include <set>

int main(int, char **)
{
  std::set<long long> foo {1LL};
}
---

std::set::begin, std::set::end, set::set::empty cause reports too.

This is not reproducible when compiling with GCC 5.1.0 (with the same options
sans those specific to Clang) and neither when building for x86-64 with either
compiler.

Reproduced using:

- Clang 3.5 w/ GCC toolchain 4.9
- Clang 3.6 w/ GCC toolchain 4.9
- Clang 3.6 w/ GCC toolchain 5.1.0

Shorter value types for std::set, e.g. `long' or `char', work. Packaging the
`long long' in another type, e.g. a struct, works too. The issue does not occur
with libc++.

Bug 60734 reported something similar, though there seem to be more issues. I'm
uncertain as to whether it's an issue in _Rb_tree, __aligned_buffer or another
place altogether.

Original report at LLVM/Clang: https://llvm.org/bugs/show_bug.cgi?id=23413

[Bug libstdc++/66017] Undefined behaviour in std::set<long long>

[public at hansmi dot ch]

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

--- Comment #1 from M. Hanselmann <public at hansmi dot ch> ---
Forgot to add that A. Bougacha has analyzed the issue. According to him it's a
cast (or casts) invoking undefined behaviour.

https://llvm.org/bugs/show_bug.cgi?id=23413#c2

[Bug libstdc++/66017] Undefined behaviour in std::set<long long>

[public at hansmi dot ch]

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

--- Comment #2 from M. Hanselmann <public at hansmi dot ch> ---
This may be related to bug 63345.

[Bug libstdc++/66017] Undefined behaviour in std::set<long long>

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I think this would solve it (I'm still trying to build a clang that will allow
me to reproduce the error):


--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -869,25 +869,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       iterator
       begin() _GLIBCXX_NOEXCEPT
       { 
+       if (_M_impl._M_header._M_left == &_M_impl._M_header)
+         return end();
        return iterator(static_cast<_Link_type>
                        (this->_M_impl._M_header._M_left));
       }

       const_iterator
       begin() const _GLIBCXX_NOEXCEPT
-      { 
+      {
+       if (_M_impl._M_header._M_left == &_M_impl._M_header)
+         return end();
        return const_iterator(static_cast<_Const_Link_type>
                              (this->_M_impl._M_header._M_left));
       }

       iterator
       end() _GLIBCXX_NOEXCEPT
-      { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
+      {
+       return iterator(reinterpret_cast<_Link_type>
+                       (&this->_M_impl._M_header));
+      }

       const_iterator
       end() const _GLIBCXX_NOEXCEPT
       { 
-       return const_iterator(static_cast<_Const_Link_type>
+       return const_iterator(reinterpret_cast<_Const_Link_type>
                              (&this->_M_impl._M_header));
       }


When the tree is empty begin() performs an invalid cast too, but I don't like
the branch this introduces.

[Bug libstdc++/66017] Undefined behaviour in std::set<long long>

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2015-05-22
           Assignee|unassigned at gcc dot gnu.org      |redi at gcc dot gnu.org
     Ever confirmed|0                           |1

[Bug libstdc++/66017] Undefined behaviour in std::set<long long>

[redi at gcc dot gnu.org]

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

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Wed May 27 11:18:37 2015
New Revision: 223745

URL: https://gcc.gnu.org/viewcvs?rev=223745&root=gcc&view=rev
Log:
        PR libstdc++/66017
        * include/bits/stl_tree.h (_Rb_tree_node): Use __aligned_membuf.
        (_Rb_tree_iterator, _Rb_tree_const_iterator): Support construction
        from _Base_ptr.
        (_Rb_tree_const_iterator::_M_const_cast): Remove static_cast.
        (_Rb_tree::begin, _Rb_tree::end): Remove static_cast.
        * include/ext/aligned_buffer.h (__aligned_membuf): New type using
        alignment of _Tp as a member subobject, not as a complete object.
        * python/libstdcxx/v6/printers.py (StdRbtreeIteratorPrinter): Lookup
        _Link_type manually as it might not be in the debug info.

Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_tree.h
    trunk/libstdc++-v3/include/ext/aligned_buffer.h
    trunk/libstdc++-v3/python/libstdcxx/v6/printers.py

[Bug libstdc++/66017] Undefined behaviour in std::set<long long>

[redi at gcc dot gnu.org]

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

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Thu May 28 12:33:36 2015
New Revision: 223811

URL: https://gcc.gnu.org/viewcvs?rev=223811&root=gcc&view=rev
Log:
        PR libstdc++/66017
        * include/bits/stl_tree.h (_Rb_tree_node): Use __aligned_membuf.
        (_Rb_tree_iterator, _Rb_tree_const_iterator): Support construction
        from _Base_ptr.
        (_Rb_tree_const_iterator::_M_const_cast): Remove static_cast.
        (_Rb_tree::begin, _Rb_tree::end): Remove static_cast.
        * include/ext/aligned_buffer.h (__aligned_membuf): New type using
        alignment of _Tp as a member subobject, not as a complete object.
        * python/libstdcxx/v6/printers.py (StdRbtreeIteratorPrinter): Lookup
        _Link_type manually as it might not be in the debug info.

Modified:
    branches/gcc-5-branch/libstdc++-v3/ChangeLog
    branches/gcc-5-branch/libstdc++-v3/include/bits/stl_tree.h
    branches/gcc-5-branch/libstdc++-v3/include/ext/aligned_buffer.h
    branches/gcc-5-branch/libstdc++-v3/python/libstdcxx/v6/printers.py

[Bug libstdc++/66017] Undefined behaviour in std::set<long long>

[redi at gcc dot gnu.org]

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

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

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

--- Comment #6 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Fixed for 5.2 and 6.0

[Bug libstdc++/66017] Undefined behaviour in std::set<long long>

[public at hansmi dot ch]

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

--- Comment #7 from M. Hanselmann <public at hansmi dot ch> ---
Confirmed for revision 223846 in gcc-5-branch. Thank you!

[Bug libstdc++/66017] Undefined behaviour in std::set<long long>

[ctice at gcc dot gnu.org]

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

--- Comment #8 from ctice at gcc dot gnu.org ---
Author: ctice
Date: Thu Sep 24 20:53:27 2015
New Revision: 228098

URL: https://gcc.gnu.org/viewcvs?rev=228098&root=gcc&view=rev
Log:

Backport r223811 from gcc-5-branch:

    PR libstdc++/66017
    * include/bits/stl_tree.h (_Rb_tree_node): Use __aligned_membuf.
    (_Rb_tree_iterator, _Rb_tree_const_iterator): Support construction
    from _Base_ptr.
    (_Rb_tree_const_iterator::_M_const_cast): Remove static_cast.
    (_Rb_tree::begin, _Rb_tree::end): Remove static_cast.
    * include/ext/aligned_buffer.h (__aligned_membuf): New type using
    alignment of _Tp as a member subobject, not as a complete object.
    * python/libstdcxx/v6/printers.py (StdRbtreeIteratorPrinter): Lookup
    _Link_type manually as it might not be in the debug info.



Modified:
    branches/google/gcc-4_9-mobile/libstdc++-v3/include/bits/stl_tree.h
    branches/google/gcc-4_9-mobile/libstdc++-v3/include/ext/aligned_buffer.h
    branches/google/gcc-4_9-mobile/libstdc++-v3/python/libstdcxx/v6/printers.py