[patch] fix libstdc++/56267 - local iterator requirements

Jonathan Wakely jwakely.gcc@gmail.com
Fri Jan 17 15:11:00 GMT 2014


The issue in PR 56267 is that unordered_xxx::local_iterator sometimes
inherits from the user-defined hash function (via _Hash_code_base,
which inherits from the hash function to use the EBO), and
local_iterator must be DefaultConstructible and Assignable, even when
the hash function isn't.

My solution is to remove the inheritance from _Hash_code_base, and
instead construct/destroy the _Hash_code_base in a block of
uninitialized memory (via __gnu_cxx::__aligned_buffer). This would
mean we can't use the EBO and increase the size of local_iterator, and
past measurements have shown that the unordered containers'
performance is sensitive to such changes, so there's a partial
specialization that doesn't have the __aligned_buffer member for the
case where the _Hash_code_base is empty and needs no storage.

François, do you have any comments on this? Can you see a better solution?

While working on this I decided I didn't like everything in
_Local_iterator_base being public, so I added some accessors to the
only members that are needed by unrelated types.

2014-01-17  Jonathan Wakely  <jwakely@redhat.com>

    PR libstdc++/56267
    * include/bits/hashtable_policy.h (_Local_iterator_base): Give
    protected access to all existing members.
    (_Local_iterator_base::_M_curr()): New public accessor.
    (_Local_iterator_base::_M_get_bucket()): New public accessor.
    (_Local_iterator_base<..., false>::_M_init()): New function to manage
    the lifetime of the _Hash_code_base explicitly.
    (_Local_iterator_base<..., false>::_M_destroy()): Likewise.
    (_Local_iterator_base<..., false>): Define copy constructor and copy
    assignment operator that use new functions to manage _Hash_code_base.
    (operator==(const _Local_iterator_base&, const _Local_iterator_base&),
    operator==(const _Local_iterator_base&, const _Local_iterator_base&)):
    Use public API for _Local_iterator_base.
    * include/debug/safe_local_iterator.h (_Safe_local_iterator): Likewise.
    * include/debug/unordered_map (__debug::unordered_map::erase(),
    __debug::unordered_multimap::erase()): Likewise.
    * include/debug/unordered_set (__debug::unordered_set::erase(),
    __debug::unordered_multiset::erase()): Likewise.
    * testsuite/23_containers/unordered_set/56267-2.cc: New test.
-------------- next part --------------
commit f9c852223230da4e4fc761f72905c7acacfa4399
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Fri Jan 17 15:10:48 2014 +0000

    	PR libstdc++/56267
    	* include/bits/hashtable_policy.h (_Local_iterator_base): Give
    	protected access to all existing members.
    	(_Local_iterator_base::_M_curr()): New public accessor.
    	(_Local_iterator_base::_M_get_bucket()): New public accessor.
    	(operator==(const _Local_iterator_base&, const _Local_iterator_base&),
    	operator==(const _Local_iterator_base&, const _Local_iterator_base&)):
    	Use public API for _Local_iterator_base.
    	* include/debug/safe_local_iterator.h (_Safe_local_iterator): Likewise.
    	* include/debug/unordered_map (__debug::unordered_map::erase(),
    	__debug::unordered_multimap::erase()): Likewise.
    	* include/debug/unordered_set (__debug::unordered_set::erase(),
    	__debug::unordered_multiset::erase()): Likewise.
    	* testsuite/23_containers/unordered_set/56267-2.cc: New test.

diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index f64d2d3..817b190 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -1145,6 +1145,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>;
       using __ebo_h2 = _Hashtable_ebo_helper<2, _H2>;
 
+      // Gives the local iterator implementation access to _M_bucket_index().
+      friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
+					 _Default_ranged_hash, false>;
+
     public:
       typedef _H1 					hasher;
 
@@ -1225,7 +1229,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       private _Hashtable_ebo_helper<2, _H2>
     {
     private:
-      // Gives access to _M_h2() to the local iterator implementation.
+      // Gives the local iterator implementation access to _M_h2().
       friend struct _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2,
 					 _Default_ranged_hash, true>;
 
@@ -1331,7 +1335,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
   };
 
 
-  /// Specialization.
+  /// Partial specialization used when nodes contain a cached hash code.
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
@@ -1343,7 +1347,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
 					       _H1, _H2, _Hash, true>;
 
-    public:
       _Local_iterator_base() = default;
       _Local_iterator_base(const __hash_code_base& __base,
 			   _Hash_node<_Value, true>* __p,
@@ -1368,27 +1371,97 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hash_node<_Value, true>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
+
+    public:
+      const void*
+      _M_curr() const { return _M_cur; }  // for equality ops
+
+      std::size_t
+      _M_get_bucket() const { return _M_bucket; }  // for debug mode
+    };
+
+  // Uninitialized storage for a _Hash_code_base.
+  // This type is DefaultConstructible and Assignable even if the
+  // _Hash_code_base type isn't, // so that _Local_iterator_base<..., false>
+  // can be DefaultConstructible and Assignable.
+  template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
+    struct _Hash_code_storage
+    {
+      __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
+
+      _Tp*
+      _M_h() { return _M_storage._M_ptr(); }
+
+      const _Tp*
+      _M_h() const { return _M_storage._M_ptr(); }
+    };
+
+  // Empty partial specialization for empty _Hash_code_base types.
+  template<typename _Tp>
+    struct _Hash_code_storage<_Tp, true>
+    {
+      static_assert( std::is_empty<_Tp>::value, "Type must be empty" );
+
+      // As _Tp is an empty type there will be no bytes written/read through
+      // the cast pointer, so no strict-aliasing violation.
+      _Tp*
+      _M_h() { return reinterpret_cast<_Tp*>(this); }
+
+      const _Tp*
+      _M_h() const { return reinterpret_cast<const _Tp*>(this); }
     };
 
-  /// Specialization.
+  template<typename _Key, typename _Value, typename _ExtractKey,
+	   typename _H1, typename _H2, typename _Hash>
+    using __hash_code_for_local_iter
+      = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
+					   _H1, _H2, _Hash, false>>;
+
+  // Partial specialization used when hash codes are not cached
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash>
     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
 				_H1, _H2, _Hash, false>
-    : private _Hash_code_base<_Key, _Value, _ExtractKey,
-			      _H1, _H2, _Hash, false>
+    : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
     {
     protected:
       using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
 					       _H1, _H2, _Hash, false>;
 
-    public:
-      _Local_iterator_base() = default;
+      _Local_iterator_base() : _M_bucket_count(-1) { }
+
       _Local_iterator_base(const __hash_code_base& __base,
 			   _Hash_node<_Value, false>* __p,
 			   std::size_t __bkt, std::size_t __bkt_count)
-	: __hash_code_base(__base),
-	  _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
+      : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
+      { _M_init(__base); }
+
+      ~_Local_iterator_base()
+      {
+	if (_M_bucket_count != -1)
+	  _M_destroy();
+      }
+
+      _Local_iterator_base(const _Local_iterator_base& __iter)
+      : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
+        _M_bucket_count(__iter._M_bucket_count)
+      {
+	if (_M_bucket_count != -1)
+	  _M_init(*__iter._M_h());
+      }
+
+      _Local_iterator_base&
+      operator=(const _Local_iterator_base& __iter)
+      {
+	if (_M_bucket_count != -1)
+	  _M_destroy();
+	_M_cur = __iter._M_cur;
+	_M_bucket = __iter._M_bucket;
+	_M_bucket_count = __iter._M_bucket_count;
+	if (_M_bucket_count != -1)
+	  _M_init(*__iter._M_h());
+	return *this;
+      }
 
       void
       _M_incr()
@@ -1396,7 +1469,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_cur = _M_cur->_M_next();
 	if (_M_cur)
 	  {
-	    std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
+	    std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
+							      _M_bucket_count);
 	    if (__bkt != _M_bucket)
 	      _M_cur = nullptr;
 	  }
@@ -1405,6 +1479,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hash_node<_Value, false>*  _M_cur;
       std::size_t _M_bucket;
       std::size_t _M_bucket_count;
+
+      void
+      _M_init(const __hash_code_base& __base)
+      { ::new(this->_M_h()) __hash_code_base(__base); }
+
+      void
+      _M_destroy() { this->_M_h()->~__hash_code_base(); }
+
+    public:
+      const void*
+      _M_curr() const { return _M_cur; }  // for equality ops and debug mode
+
+      std::size_t
+      _M_get_bucket() const { return _M_bucket; }  // for debug mode
     };
 
   template<typename _Key, typename _Value, typename _ExtractKey,
@@ -1414,7 +1502,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 					  _H1, _H2, _Hash, __cache>& __x,
 	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
 					  _H1, _H2, _Hash, __cache>& __y)
-    { return __x._M_cur == __y._M_cur; }
+    { return __x._M_curr() == __y._M_curr(); }
 
   template<typename _Key, typename _Value, typename _ExtractKey,
 	   typename _H1, typename _H2, typename _Hash, bool __cache>
@@ -1423,7 +1511,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 					  _H1, _H2, _Hash, __cache>& __x,
 	       const _Local_iterator_base<_Key, _Value, _ExtractKey,
 					  _H1, _H2, _Hash, __cache>& __y)
-    { return __x._M_cur != __y._M_cur; }
+    { return __x._M_curr() != __y._M_curr(); }
 
   /// local iterators
   template<typename _Key, typename _Value, typename _ExtractKey,
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h
index f5e9893..77552ce 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.h
+++ b/libstdc++-v3/include/debug/safe_local_iterator.h
@@ -219,7 +219,7 @@ namespace __gnu_debug
        * @brief Return the bucket
        */
       size_type
-      bucket() const { return _M_current._M_bucket; }
+      bucket() const { return _M_current._M_get_bucket(); }
 
       /**
        * @brief Conversion to underlying non-debug iterator to allow
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index a1eccde..821bf0b 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -389,7 +389,7 @@ namespace __debug
 			    { return __it == __victim; });
 	    this->_M_invalidate_local_if(
 			    [__victim](_Base_const_local_iterator __it)
-			    { return __it._M_cur == __victim._M_cur; });
+			    { return __it._M_curr() == __victim._M_cur; });
 	    size_type __bucket_count = this->bucket_count();
 	    _Base::erase(__victim);
 	    _M_check_rehashed(__bucket_count);
@@ -407,7 +407,7 @@ namespace __debug
 			{ return __it == __victim; });
 	this->_M_invalidate_local_if(
 			[__victim](_Base_const_local_iterator __it)
-			{ return __it._M_cur == __victim._M_cur; });
+			{ return __it._M_curr() == __victim._M_cur; });
 	size_type __bucket_count = this->bucket_count();
 	_Base_iterator __next = _Base::erase(__it.base()); 
 	_M_check_rehashed(__bucket_count);
@@ -433,7 +433,7 @@ namespace __debug
 			    { return __it == __tmp; });
 	    this->_M_invalidate_local_if(
 			    [__tmp](_Base_const_local_iterator __it)
-			    { return __it._M_cur == __tmp._M_cur; });
+			    { return __it._M_curr() == __tmp._M_cur; });
 	  }
 	size_type __bucket_count = this->bucket_count();
 	_Base_iterator __next = _Base::erase(__first.base(), __last.base());
@@ -842,7 +842,7 @@ namespace __debug
 			    { return __it == __victim; });
 	    this->_M_invalidate_local_if(
 			    [__victim](_Base_const_local_iterator __it)
-			    { return __it._M_cur == __victim._M_cur; });
+			    { return __it._M_curr() == __victim._M_cur; });
 	    _Base::erase(__victim++);
 	    ++__ret;
 	  }
@@ -859,7 +859,7 @@ namespace __debug
 			{ return __it == __victim; });
 	this->_M_invalidate_local_if(
 			[__victim](_Base_const_local_iterator __it)
-			{ return __it._M_cur == __victim._M_cur; });
+			{ return __it._M_curr() == __victim._M_cur; });
 	size_type __bucket_count = this->bucket_count();
 	_Base_iterator __next = _Base::erase(__it.base());
 	_M_check_rehashed(__bucket_count);
@@ -885,7 +885,7 @@ namespace __debug
 			    { return __it == __tmp; });
 	    this->_M_invalidate_local_if(
 			    [__tmp](_Base_const_local_iterator __it)
-			    { return __it._M_cur == __tmp._M_cur; });
+			    { return __it._M_curr() == __tmp._M_cur; });
 	  }
 	size_type __bucket_count = this->bucket_count();
 	_Base_iterator __next = _Base::erase(__first.base(), __last.base());
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index 8246141..3bc3fab 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -383,7 +383,7 @@ namespace __debug
 			    { return __it == __victim; });
 	    this->_M_invalidate_local_if(
 			    [__victim](_Base_const_local_iterator __it)
-			    { return __it._M_cur == __victim._M_cur; });
+			    { return __it._M_curr() == __victim._M_cur; });
 	    size_type __bucket_count = this->bucket_count();
 	    _Base::erase(__victim);
 	    _M_check_rehashed(__bucket_count);
@@ -402,7 +402,7 @@ namespace __debug
 			{ return __it == __victim; });
 	this->_M_invalidate_local_if(
 			[__victim](_Base_const_local_iterator __it)
-			{ return __it._M_cur == __victim._M_cur; });
+			{ return __it._M_curr() == __victim._M_cur; });
 	size_type __bucket_count = this->bucket_count();
 	_Base_iterator __next = _Base::erase(__it.base());
 	_M_check_rehashed(__bucket_count);
@@ -429,7 +429,7 @@ namespace __debug
 			    { return __it == __tmp; });
 	    this->_M_invalidate_local_if(
 			    [__tmp](_Base_const_local_iterator __it)
-			    { return __it._M_cur == __tmp._M_cur; });
+			    { return __it._M_curr() == __tmp._M_cur; });
 	  }
 	size_type __bucket_count = this->bucket_count();
 	_Base_iterator __next = _Base::erase(__first.base(),
@@ -832,7 +832,7 @@ namespace __debug
 			    { return __it == __victim; });
 	    this->_M_invalidate_local_if(
 			    [__victim](_Base_const_local_iterator __it)
-			    { return __it._M_cur == __victim._M_cur; });
+			    { return __it._M_curr() == __victim._M_cur; });
 	    _Base::erase(__victim++);
 	    ++__ret;
 	  }
@@ -848,7 +848,7 @@ namespace __debug
 			{ return __it == __victim; });
 	this->_M_invalidate_local_if(
 			[__victim](_Base_const_local_iterator __it)
-			{ return __it._M_cur == __victim._M_cur; });
+			{ return __it._M_curr() == __victim._M_cur; });
 	return iterator(_Base::erase(__it.base()), this);
       }
 
@@ -871,7 +871,7 @@ namespace __debug
 			    { return __it == __tmp; });
 	    this->_M_invalidate_local_if(
 			    [__tmp](_Base_const_local_iterator __it)
-			    { return __it._M_cur == __tmp._M_cur; });
+			    { return __it._M_curr() == __tmp._M_cur; });
 	  }
 	return iterator(_Base::erase(__first.base(),
 				     __last.base()), this);
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/56267-2.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/56267-2.cc
new file mode 100644
index 0000000..cae451a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/56267-2.cc
@@ -0,0 +1,43 @@
+// Copyright (C) 2014 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11" }
+
+#include <unordered_set>
+
+struct audrey2hash : std::hash<int>
+{
+  audrey2hash() { throw "Seed me, Seymour"; } // must not use default ctor
+
+  audrey2hash(int) { }
+
+  audrey2hash&
+  operator=(const audrey2hash&) { throw "Don't assign the plants"; }
+};
+
+void test01()
+{
+  typedef std::unordered_set<int, audrey2hash> test_type;
+  test_type::local_iterator it __attribute__((unused));
+  test_type c{ {1, 2, 3}, 3u, audrey2hash{1} };
+  it = c.begin(0);
+}
+
+int main()
+{
+  test01();
+}


More information about the Gcc-patches mailing list