There are two problems involved in this PR.
First, as Clang's ubsan detects, we are using static_cast to convert
from _Rb_tree_node_base* to _Rb_tree_node<_Val>* in cases where there
is no _Rb_tree_node<_Val> at that address (_M_impl._M_header is just
an _Rb_tree_node_base). That's undefined behaviour, and shows up here
when alignof(_Rb_tree_node_base) != alignof(_Rb_tree_node<_Val>)
because we end up with a misaligned _Rb_tree_node<_Val>* (which we
never dereference, because it's the past-the-end iterator, but it's
still UB to do the cast).
The second problem is that alignof(_Rb_tree_node<long long>) changes
depending on whether it's compiled as c++98 or c++11. This is because
in C++11 mode I replaced the member _M_value_field with uninitialized
storage aligned as alignof(_Val), using __aligned_buffer, but for
targets that define the ADJUST_FIELD_ALIGN target macro it's wrong to
assume that alignof(_M_value_field) == alignof(_Val), because the type
might have weaker alignment when it's a member of a structure. This
means the __aligned_buffer in C++11 mode is not aligned the same as
the _M_value_field member it was meant to replace. Ouch.
The first problem can be fixed by simply removing the casts, I don't
see why we need them. They are there because the _Rb_tree_iterator and
_Rb_tree_const_iterator constructors take a pointer-to-derived, but
then they upcast to pointer-to-base and store that type instead. So if
we just make the constructors take pointer-to-base instead then we
don't need the possibly-invalid casts. This way we only do the
downcast when dereferencing an iterator, which only happens for real
nodes where the downcast is valid, not for _M_impl._M_header.
The second problem can be fixed by making __aligned_buffer use the
alignment of struct _Tp2 { Tp t; } instead of alignof(_Tp).
patch.txt fixes those two problems. That is needed on trunk and the
gcc-5 branch.
patch2.txt then takes the idea further and gets rid of some more casts
that aren't actually necessary. The pointer returned by _M_end() is
never dereferenced, so there's no reason it can't be a _Base_ptr
rather than a _Link_type (i.e. _Rb_tree_node_base* rather than
_Rb_tree_node<_Val>*). While making that change I realised that the
_M_xxx_tr() functions for heterogeneous lookup can be simplified, so
the non-const versions use const ones and then call _M_const_cast() on
the results. Any objections to this additional change going in to
trunk? We could take it even further and have _M_begin() return a
_Base_ptr and then only downcast it as needed, but I'm not proposing
that for now.
commit d57e7058e821664735e0118f8e37b8cbc37e49fb
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Thu May 21 14:41:16 2015 +0100
PR libstdc++/66017
* include/bits/stl_tree.h (_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_buffer): Use alignment of
_Tp as a member subobject, not as a complete object.
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 5ca8e28..2dc95df 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -188,7 +188,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
: _M_node() { }
explicit
- _Rb_tree_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT
+ _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
: _M_node(__x) { }
reference
@@ -260,7 +260,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
: _M_node() { }
explicit
- _Rb_tree_const_iterator(_Link_type __x) _GLIBCXX_NOEXCEPT
+ _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
: _M_node(__x) { }
_Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
@@ -268,8 +268,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
_M_const_cast() const _GLIBCXX_NOEXCEPT
- { return iterator(static_cast<typename iterator::_Link_type>
- (const_cast<typename iterator::_Base_ptr>(_M_node))); }
+ { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
reference
operator*() const _GLIBCXX_NOEXCEPT
@@ -868,28 +867,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
begin() _GLIBCXX_NOEXCEPT
- {
- return iterator(static_cast<_Link_type>
- (this->_M_impl._M_header._M_left));
- }
+ { return iterator(this->_M_impl._M_header._M_left); }
const_iterator
begin() const _GLIBCXX_NOEXCEPT
- {
- return const_iterator(static_cast<_Const_Link_type>
- (this->_M_impl._M_header._M_left));
- }
+ { return const_iterator(this->_M_impl._M_header._M_left); }
iterator
end() _GLIBCXX_NOEXCEPT
- { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
+ { return iterator(&this->_M_impl._M_header); }
const_iterator
end() const _GLIBCXX_NOEXCEPT
- {
- return const_iterator(static_cast<_Const_Link_type>
- (&this->_M_impl._M_header));
- }
+ { return const_iterator(&this->_M_impl._M_header); }
reverse_iterator
rbegin() _GLIBCXX_NOEXCEPT
diff --git a/libstdc++-v3/include/ext/aligned_buffer.h b/libstdc++-v3/include/ext/aligned_buffer.h
index 01f5729..9cd5760 100644
--- a/libstdc++-v3/include/ext/aligned_buffer.h
+++ b/libstdc++-v3/include/ext/aligned_buffer.h
@@ -31,21 +31,23 @@
#pragma GCC system_header
-#if __cplusplus >= 201103L
-# include <type_traits>
-#else
+#if __cplusplus < 201103L
# include <bits/c++0x_warning.h>
#endif
+#include <cstddef>
+
namespace __gnu_cxx
{
template<typename _Tp>
struct __aligned_buffer
- : std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value>
{
- typename
- std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value>::type
- _M_storage;
+ // Target macro ADJUST_FIELD_ALIGN can produce different alignment for
+ // types when used as class members. __aligned_buffer is intended for
+ // use as a class member, so align the buffer as for a class member.
+ struct _Tp2 { _Tp _M_t; };
+
+ alignas(alignof(_Tp2)) unsigned char _M_storage[sizeof(_Tp)];
__aligned_buffer() = default;
@@ -54,15 +56,11 @@ namespace __gnu_cxx
void*
_M_addr() noexcept
- {
- return static_cast<void*>(&_M_storage);
- }
+ { return static_cast<void*>(&_M_storage); }
const void*
_M_addr() const noexcept
- {
- return static_cast<const void*>(&_M_storage);
- }
+ { return static_cast<const void*>(&_M_storage); }
_Tp*
_M_ptr() noexcept
commit 28afd0343f14df56b9b0e8c5f8311b07b6e5f5d4
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Fri May 22 13:54:50 2015 +0100
make _Rb_tree::_M_end() return base ptr
diff --git a/libstdc++-v3/include/bits/stl_tree.h
b/libstdc++-v3/include/bits/stl_tree.h
index 2dc95df..fee2c57 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -658,13 +658,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
(this->_M_impl._M_header._M_parent);
}
- _Link_type
+ _Base_ptr
_M_end() _GLIBCXX_NOEXCEPT
- { return reinterpret_cast<_Link_type>(&this->_M_impl._M_header); }
+ { return &this->_M_impl._M_header; }
- _Const_Link_type
+ _Const_Base_ptr
_M_end() const _GLIBCXX_NOEXCEPT
- { return reinterpret_cast<_Const_Link_type>(&this->_M_impl._M_header); }
+ { return &this->_M_impl._M_header; }
static const_reference
_S_value(_Const_Link_type __x)
@@ -774,10 +774,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _NodeGen>
_Link_type
- _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen&);
+ _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
_Link_type
- _M_copy(_Const_Link_type __x, _Link_type __p)
+ _M_copy(_Const_Link_type __x, _Base_ptr __p)
{
_Alloc_node __an(*this);
return _M_copy(__x, __p, __an);
@@ -787,19 +787,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_erase(_Link_type __x);
iterator
- _M_lower_bound(_Link_type __x, _Link_type __y,
+ _M_lower_bound(_Link_type __x, _Base_ptr __y,
const _Key& __k);
const_iterator
- _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
+ _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
const _Key& __k) const;
iterator
- _M_upper_bound(_Link_type __x, _Link_type __y,
+ _M_upper_bound(_Link_type __x, _Base_ptr __y,
const _Key& __k);
const_iterator
- _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
+ _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
const _Key& __k) const;
public:
@@ -1117,43 +1117,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__is_transparent<_Cmp, _Kt, __void_t<typename _Cmp::is_transparent>>
{ typedef void type; };
- static auto _S_iter(_Link_type __x) { return iterator(__x); }
-
- static auto _S_iter(_Const_Link_type __x) { return const_iterator(__x); }
-
- template<typename _Cmp, typename _Link, typename _Kt>
- static auto
- _S_lower_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
- {
- while (__x != 0)
- if (!__cmp(_S_key(__x), __k))
- __y = __x, __x = _S_left(__x);
- else
- __x = _S_right(__x);
- return _S_iter(__y);
- }
-
- template<typename _Cmp, typename _Link, typename _Kt>
- static auto
- _S_upper_bound_tr(_Cmp& __cmp, _Link __x, _Link __y, const _Kt& __k)
- {
- while (__x != 0)
- if (__cmp(__k, _S_key(__x)))
- __y = __x, __x = _S_left(__x);
- else
- __x = _S_right(__x);
- return _S_iter(__y);
- }
-
template<typename _Kt,
typename _Req = typename __is_transparent<_Compare, _Kt>::type>
iterator
_M_find_tr(const _Kt& __k)
{
- auto& __cmp = _M_impl._M_key_compare;
- auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
- return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
- ? end() : __j;
+ const _Rb_tree* __const_this = this;
+ return __const_this->_M_find_tr(__k)._M_const_cast();
}
template<typename _Kt,
@@ -1161,10 +1131,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const_iterator
_M_find_tr(const _Kt& __k) const
{
- auto& __cmp = _M_impl._M_key_compare;
- auto __j = _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
- return (__j == end() || __cmp(__k, _S_key(__j._M_node)))
- ? end() : __j;
+ auto __j = _M_lower_bound_tr(__k);
+ if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
+ __j = end();
+ return __j;
}
template<typename _Kt,
@@ -1181,8 +1151,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
_M_lower_bound_tr(const _Kt& __k)
{
- auto& __cmp = _M_impl._M_key_compare;
- return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+ const _Rb_tree* __const_this = this;
+ return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
}
template<typename _Kt,
@@ -1190,8 +1160,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const_iterator
_M_lower_bound_tr(const _Kt& __k) const
{
- auto& __cmp = _M_impl._M_key_compare;
- return _S_lower_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+ auto __x = _M_begin();
+ auto __y = _M_end();
+ while (__x != 0)
+ if (!_M_impl._M_key_compare(_S_key(__x), __k))
+ {
+ __y = __x;
+ __x = _S_left(__x);
+ }
+ else
+ __x = _S_right(__x);
+ return const_iterator(__y);
}
template<typename _Kt,
@@ -1199,8 +1178,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
iterator
_M_upper_bound_tr(const _Kt& __k)
{
- auto& __cmp = _M_impl._M_key_compare;
- return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+ const _Rb_tree* __const_this = this;
+ return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
}
template<typename _Kt,
@@ -1208,8 +1187,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const_iterator
_M_upper_bound_tr(const _Kt& __k) const
{
- auto& __cmp = _M_impl._M_key_compare;
- return _S_upper_bound_tr(__cmp, _M_begin(), _M_end(), __k);
+ auto __x = _M_begin();
+ auto __y = _M_end();
+ while (__x != 0)
+ if (_M_impl._M_key_compare(__k, _S_key(__x)))
+ {
+ __y = __x;
+ __x = _S_left(__x);
+ }
+ else
+ __x = _S_right(__x);
+ return const_iterator(__y);
}
template<typename _Kt,
@@ -1217,12 +1205,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
pair<iterator, iterator>
_M_equal_range_tr(const _Kt& __k)
{
- auto __low = _M_lower_bound_tr(__k);
- auto __high = __low;
- auto& __cmp = _M_impl._M_key_compare;
- while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
- ++__high;
- return { __low, __high };
+ const _Rb_tree* __const_this = this;
+ auto __ret = __const_this->_M_equal_range_tr(__k);
+ return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
}
template<typename _Kt,
@@ -1553,7 +1538,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
{
_Link_type __x = _M_begin();
- _Link_type __y = _M_end();
+ _Base_ptr __y = _M_end();
while (__x != 0)
{
__y = __x;
@@ -1568,7 +1553,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _NodeGen>
typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
_Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
- _M_copy(_Const_Link_type __x, _Link_type __p, _NodeGen& __node_gen)
+ _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
{
// Structural copy. __x and __p must be non-null.
_Link_type __top = _M_clone_node(__x, __node_gen);
@@ -1621,7 +1606,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_lower_bound(_Link_type __x, _Link_type __y,
+ _M_lower_bound(_Link_type __x, _Base_ptr __y,
const _Key& __k)
{
while (__x != 0)
@@ -1637,7 +1622,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::const_iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
+ _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
const _Key& __k) const
{
while (__x != 0)
@@ -1653,7 +1638,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_upper_bound(_Link_type __x, _Link_type __y,
+ _M_upper_bound(_Link_type __x, _Base_ptr __y,
const _Key& __k)
{
while (__x != 0)
@@ -1669,7 +1654,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename _Rb_tree<_Key, _Val, _KeyOfValue,
_Compare, _Alloc>::const_iterator
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
+ _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
const _Key& __k) const
{
while (__x != 0)
@@ -1690,7 +1675,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
equal_range(const _Key& __k)
{
_Link_type __x = _M_begin();
- _Link_type __y = _M_end();
+ _Base_ptr __y = _M_end();
while (__x != 0)
{
if (_M_impl._M_key_compare(_S_key(__x), __k))
@@ -1699,7 +1684,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__y = __x, __x = _S_left(__x);
else
{
- _Link_type __xu(__x), __yu(__y);
+ _Link_type __xu(__x);
+ _Base_ptr __yu(__y);
__y = __x, __x = _S_left(__x);
__xu = _S_right(__xu);
return pair<iterator,
@@ -1721,7 +1707,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
equal_range(const _Key& __k) const
{
_Const_Link_type __x = _M_begin();
- _Const_Link_type __y = _M_end();
+ _Const_Base_ptr __y = _M_end();
while (__x != 0)
{
if (_M_impl._M_key_compare(_S_key(__x), __k))
@@ -1730,7 +1716,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__y = __x, __x = _S_left(__x);
else
{
- _Const_Link_type __xu(__x), __yu(__y);
+ _Const_Link_type __xu(__x);
+ _Const_Base_ptr __yu(__y);
__y = __x, __x = _S_left(__x);
__xu = _S_right(__xu);
return pair<const_iterator,
@@ -1802,7 +1789,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
typedef pair<_Base_ptr, _Base_ptr> _Res;
_Link_type __x = _M_begin();
- _Link_type __y = _M_end();
+ _Base_ptr __y = _M_end();
bool __comp = true;
while (__x != 0)
{
@@ -1834,7 +1821,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
typedef pair<_Base_ptr, _Base_ptr> _Res;
_Link_type __x = _M_begin();
- _Link_type __y = _M_end();
+ _Base_ptr __y = _M_end();
while (__x != 0)
{
__y = __x;
@@ -2102,7 +2089,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert_equal_lower_node(_Link_type __z)
{
_Link_type __x = _M_begin();
- _Link_type __y = _M_end();
+ _Base_ptr __y = _M_end();
while (__x != 0)
{
__y = __x;
