This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

hashtable exception safety patch


On 09/01/2011 08:36 PM, Paolo Carlini wrote:
Hi,
     After some additional time spent on hashtable I prefer to do this
new proposal. It fixes
- I deal with allocation failure directly in _M_rehash method to avoid
introducing new try/catch blocks. I also reset hash policy next resize
value when the container is emptied on a hash functor exception.

For points 3 and 4 above, I would like to see separate patches and
separate testcases. Is it possible?

Also, please be more descriptive in the ChangeLog entry, saying which
specific functions are touched. Then, splitting the big patch will also
help clarifying the rationale behind each smaller one.

Paolo.

Hi

Here is the patch regarding exception safety issues. Writing dedicated tests I even found an other situation where the _M_next_resize was not correctly restored on exception. It was in _M_insert_bucket method if the node allocation fails. I also considered using some kind of guard object that would automatically restore hash policy previous resize value on exception but as it is not the case when the exception is raised by the hash functor the code wouldn't have been simpler.

2011-09-07 François Dumont <fdumont@gcc.gnu.org>

* include/bits/hashtable.h (_Hashtable<>::_M_rehash): Take and restore
hash policy _M_prev_resize on bad_alloc exception.
(_Hashtable<>::_M_insert_bucket): Capture hash policy next resize
before using it and use latter method to have it restore on exception.
(_Hashtable<>::_M_insert(_Arg&& __v, std::false_type): Likewise.
(_Hashtable<>::insert(_InputIterator, _InputIterator): Likewise.
(_Hashtable<>::rehash): Likewise.
* testsuite/util/testsuite_allocators.h: Add throw_allocator
std::allocator implementation that offer controls on generation of
std::bad_alloc exceptions.
* testsuite/23_containers/unordered_set/insert/hash_policy.cc: New.
* testsuite/23_containers/unordered_multiset/insert/hash_policy.cc:
Likewise.


François

Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 178658)
+++ include/bits/hashtable.h	(working copy)
@@ -458,8 +458,9 @@
       // reserve, if present, comes from _Rehash_base.
 
     private:
-      // Unconditionally change size of bucket array to n.
-      void _M_rehash(size_type __n);
+      // Unconditionally change size of bucket array to n, restore hash policy
+      // resize value to prev_resize on exception.
+      void _M_rehash(size_type __n, size_type __prev_resize);
     };
 
 
@@ -743,7 +744,7 @@
       _M_rehash_policy = __pol;
       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
       if (__n_bkt > _M_bucket_count)
-	_M_rehash(__n_bkt);
+	_M_rehash(__n_bkt, __pol._M_next_resize);
     }
 
   template<typename _Key, typename _Value,
@@ -910,6 +911,7 @@
       _M_insert_bucket(_Arg&& __v, size_type __n,
 		       typename _Hashtable::_Hash_code_type __code)
       {
+	const size_type __prev_resize = _M_rehash_policy._M_next_resize;
 	std::pair<bool, std::size_t> __do_rehash
 	  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
 					    _M_element_count, 1);
@@ -922,12 +924,13 @@
 
 	// Allocate the new node before doing the rehash so that we don't
 	// do a rehash if the allocation throws.
-	_Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v));
+	_Node* __new_node = 0;
 
 	__try
 	  {
+	    __new_node = _M_allocate_node(std::forward<_Arg>(__v));
 	    if (__do_rehash.first)
-	      _M_rehash(__do_rehash.second);
+	      _M_rehash(__do_rehash.second, __prev_resize);
 
 	    __new_node->_M_next = _M_buckets[__n];
 	    this->_M_store_code(__new_node, __code);
@@ -939,7 +942,10 @@
 	  }
 	__catch(...)
 	  {
-	    _M_deallocate_node(__new_node);
+	    if (!__new_node)
+	      _M_rehash_policy._M_next_resize = __prev_resize;
+	    else
+	      _M_deallocate_node(__new_node);
 	    __throw_exception_again;
 	  }
       }
@@ -981,11 +987,12 @@
 		 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
       _M_insert(_Arg&& __v, std::false_type)
       {
+	const size_type __prev_resize = _M_rehash_policy._M_next_resize;
 	std::pair<bool, std::size_t> __do_rehash
 	  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
 					    _M_element_count, 1);
 	if (__do_rehash.first)
-	  _M_rehash(__do_rehash.second);
+	  _M_rehash(__do_rehash.second, __prev_resize);
 
 	const key_type& __k = this->_M_extract(__v);
 	typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
@@ -1024,11 +1031,12 @@
       insert(_InputIterator __first, _InputIterator __last)
       {
 	size_type __n_elt = __detail::__distance_fw(__first, __last);
+	const size_type __prev_resize = _M_rehash_policy._M_next_resize;
 	std::pair<bool, std::size_t> __do_rehash
 	  = _M_rehash_policy._M_need_rehash(_M_bucket_count,
 					    _M_element_count, __n_elt);
 	if (__do_rehash.first)
-	  _M_rehash(__do_rehash.second);
+	  _M_rehash(__do_rehash.second, __prev_resize);
 
 	for (; __first != __last; ++__first)
 	  this->insert(*__first);
@@ -1184,9 +1192,11 @@
 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     rehash(size_type __n)
     {
+      size_type __prev_resize = _M_rehash_policy._M_next_resize;
       _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
 			 _M_rehash_policy._M_bkt_for_elements(_M_element_count
-							      + 1)));
+							      + 1)),
+		__prev_resize);
     }
 
   template<typename _Key, typename _Value,
@@ -1196,11 +1206,12 @@
     void
     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
-    _M_rehash(size_type __n)
+    _M_rehash(size_type __n, size_type __prev_resize)
     {
-      _Node** __new_array = _M_allocate_buckets(__n);
+      _Node** __new_array = 0;
       __try
 	{
+	  __new_array = _M_allocate_buckets(__n);
 	  _M_begin_bucket_index = __n;
 	  for (size_type __i = 0; __i < _M_bucket_count; ++__i)
 	    while (_Node* __p = _M_buckets[__i])
@@ -1218,15 +1229,23 @@
 	}
       __catch(...)
 	{
-	  // A failure here means that a hash function threw an exception.
-	  // We can't restore the previous state without calling the hash
-	  // function again, so the only sensible recovery is to delete
-	  // everything.
-	  _M_deallocate_nodes(__new_array, __n);
-	  _M_deallocate_buckets(__new_array, __n);
-	  _M_deallocate_nodes(_M_buckets, _M_bucket_count);
-	  _M_element_count = 0;
-	  _M_begin_bucket_index = _M_bucket_count;
+	  if (__new_array)
+	    {
+	      // A failure here means that a hash function threw an exception.
+	      // We can't restore the previous state without calling the hash
+	      // function again, so the only sensible recovery is to delete
+	      // everything.
+	      _M_deallocate_nodes(__new_array, __n);
+	      _M_deallocate_buckets(__new_array, __n);
+	      _M_deallocate_nodes(_M_buckets, _M_bucket_count);
+	      _M_element_count = 0;
+	      _M_begin_bucket_index = _M_bucket_count;
+	      _M_rehash_policy._M_next_resize = 0;
+	    }
+	  else
+	    // A failure here means that buckets allocation failed. We only
+	    // have to restore hash policy previous state.
+	    _M_rehash_policy._M_next_resize = __prev_resize;
 	  __throw_exception_again;
 	}
     }
Index: testsuite/23_containers/unordered_set/insert/hash_policy.cc
===================================================================
--- testsuite/23_containers/unordered_set/insert/hash_policy.cc	(revision 0)
+++ testsuite/23_containers/unordered_set/insert/hash_policy.cc	(revision 0)
@@ -0,0 +1,102 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+#include <unordered_set>
+#include <vector>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+		     __gnu_test::throwing_allocator<int> > us;
+  const int nb = 100;
+  int scheduled_throw_counter = 0;
+  for (int i = 0; i != nb; ++i)
+    {
+      if ((float)(us.size() + 1) / (float)us.bucket_count() >= us.max_load_factor())
+	{
+	  // We are going to need a rehash, lets introduce allocation issues:
+	  __gnu_test::throwing_allocator_manager::scheduled_counter = ++scheduled_throw_counter;
+	}
+      try
+	{
+	  VERIFY(us.insert(i).second);
+	  scheduled_throw_counter = 0;
+	}
+      catch (const std::bad_alloc&)
+	{
+	  --i;
+	}
+      VERIFY( us.load_factor() <= us.max_load_factor() );
+      __gnu_test::throwing_allocator_manager::scheduled_counter = 0;
+    }
+
+  // Check that all values have been inserted:
+  for (int i = 0; i != nb; ++i)
+    {
+      VERIFY( us.count(i) == 1 );
+    }
+}
+
+void test02()
+{
+  bool test __attribute__((unused)) = true;
+
+  std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+		     __gnu_test::throwing_allocator<int> > us;
+  const int nb = 100;
+  int scheduled_throw_counter = 0;
+  for (int i = 0; i != nb; ++i)
+    {
+      if ((float)(us.size() + 2) / (float)us.bucket_count() >= us.max_load_factor())
+	{
+	  // We are going to need a rehash, lets introduce allocation issues:
+	  __gnu_test::throwing_allocator_manager::scheduled_counter = ++scheduled_throw_counter;
+	}
+      try
+	{
+	  std::vector<int> v = { i, i };
+	  // Check the insert range robustness
+	  us.insert(v.begin(), v.end());
+	  scheduled_throw_counter = 0;
+	}
+      catch (const std::bad_alloc&)
+	{
+	  --i;
+	}
+      VERIFY( us.load_factor() <= us.max_load_factor() );
+      __gnu_test::throwing_allocator_manager::scheduled_counter = 0;
+    }
+
+  // Check that all values have been inserted:
+  for (int i = 0; i != nb; ++i)
+    {
+      VERIFY( us.count(i) == 1 );
+    }
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_multiset/insert/hash_policy.cc
===================================================================
--- testsuite/23_containers/unordered_multiset/insert/hash_policy.cc	(revision 0)
+++ testsuite/23_containers/unordered_multiset/insert/hash_policy.cc	(revision 0)
@@ -0,0 +1,65 @@
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2011 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/>.
+
+#include <iostream>
+#include <unordered_set>
+#include <testsuite_hooks.h>
+#include <testsuite_allocator.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+			  __gnu_test::throwing_allocator<int> > us;
+  const int nb = 100;
+  int scheduled_throw_counter = 0;
+  for (int i = 0; i != nb; ++i)
+    {
+      if ((float)(us.size() + 1) / (float)us.bucket_count() >= us.max_load_factor())
+	{
+	  // We are going to need a rehash, lets introduce allocation issues:
+	  __gnu_test::throwing_allocator_manager::scheduled_counter = ++scheduled_throw_counter;
+	}
+      try
+	{
+	  us.insert(i / 2);
+	  scheduled_throw_counter = 0;
+	}
+      catch (const std::bad_alloc&)
+	{
+	  std::cout << "exception thrown at " << i << std::endl;
+	  --i;
+	}
+      VERIFY( us.load_factor() <= us.max_load_factor() );
+      __gnu_test::throwing_allocator_manager::scheduled_counter = 0;
+    }
+
+  // Check that all values have been inserted:
+  for (int i = 0; i != nb / 2; ++i)
+    {
+      VERIFY( us.count(i) == 2 );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
Index: testsuite/util/testsuite_allocator.cc
===================================================================
--- testsuite/util/testsuite_allocator.cc	(revision 178658)
+++ testsuite/util/testsuite_allocator.cc	(working copy)
@@ -52,5 +52,8 @@
       }
     return ret;
   }
+
+  int
+  throwing_allocator_manager::scheduled_counter = 0;
 } // namespace __cxx_test
 
Index: testsuite/util/testsuite_allocator.h
===================================================================
--- testsuite/util/testsuite_allocator.h	(revision 178658)
+++ testsuite/util/testsuite_allocator.h	(working copy)
@@ -258,7 +258,7 @@
       typedef Tp                                  value_type;
       
       template<typename Tp1>
-        struct rebind
+	struct rebind
 	{ typedef uneq_allocator<Tp1> other; };
 
       uneq_allocator() _GLIBCXX_USE_NOEXCEPT
@@ -268,7 +268,7 @@
       : personality(person) { }
       
       template<typename Tp1>
-        uneq_allocator(const uneq_allocator<Tp1>& b) _GLIBCXX_USE_NOEXCEPT
+	uneq_allocator(const uneq_allocator<Tp1>& b) _GLIBCXX_USE_NOEXCEPT
 	: personality(b.get_personality()) { }
 
       ~uneq_allocator() _GLIBCXX_USE_NOEXCEPT
@@ -328,8 +328,8 @@
 
 #ifdef __GXX_EXPERIMENTAL_CXX0X__
       template<typename U, typename... Args>
-        void
-        construct(U* p, Args&&... args) 
+	void
+	construct(U* p, Args&&... args) 
 	{ ::new((void *)p) U(std::forward<Args>(args)...); }
 
       template<typename U>
@@ -361,14 +361,14 @@
       { std::swap(a.personality, b.personality); } 
       
       template<typename Tp1>
-        friend inline bool
-        operator==(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
-        { return a.personality == b.personality; }
+	friend inline bool
+	operator==(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
+	{ return a.personality == b.personality; }
 
       template<typename Tp1>
-        friend inline bool
-        operator!=(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
-        { return !(a == b); }
+	friend inline bool
+	operator!=(const uneq_allocator& a, const uneq_allocator<Tp1>& b)
+	{ return !(a == b); }
       
       int personality;
     };
@@ -435,20 +435,88 @@
 
 #endif
 
-  template<typename Tp>
-    struct ExplicitConsAlloc : std::allocator<Tp>
+  class throwing_allocator_manager
+  {
+    public:
+      // Number of allocations before throwing
+      static int scheduled_counter;
+  };
+
+  template <typename T>
+    class throwing_allocator
     {
-      ExplicitConsAlloc() { }
+    public:
+      typedef T              value_type;
+      typedef T*             pointer;
+      typedef const T*       const_pointer;
+      typedef T&             reference;
+      typedef const T&       const_reference;
+      typedef std::size_t    size_type;
+      typedef std::ptrdiff_t difference_type;
 
-      template<typename Up>
-        explicit
-        ExplicitConsAlloc(const ExplicitConsAlloc<Up>&) { }
+      template<class U> struct rebind
+      { typedef throwing_allocator<U> other; };
 
-      template<typename Up>
-        struct rebind
-        { typedef ExplicitConsAlloc<Up> other; };
+      pointer
+      address(reference value) const _GLIBCXX_NOEXCEPT
+      { return std::__addressof(value); }
+
+      const_pointer
+      address(const_reference value) const _GLIBCXX_NOEXCEPT
+      { return std::__addressof(value); }
+
+      throwing_allocator() _GLIBCXX_USE_NOEXCEPT
+      { }
+
+      throwing_allocator(const throwing_allocator&) _GLIBCXX_USE_NOEXCEPT
+      { }
+
+      template<class U>
+      throwing_allocator(const throwing_allocator<U>&) _GLIBCXX_USE_NOEXCEPT
+      { }
+
+      ~throwing_allocator() _GLIBCXX_USE_NOEXCEPT
+      { }
+
+      size_type
+      max_size() const _GLIBCXX_USE_NOEXCEPT
+      { return size_type(-1) / sizeof(T); }
+
+      pointer
+      allocate(size_type n, const void* = 0)
+      {
+	if (throwing_allocator_manager::scheduled_counter)
+	{
+	  if (--throwing_allocator_manager::scheduled_counter == 0)
+	    throw std::bad_alloc();
+	}
+	return static_cast<pointer>(::operator new(n * sizeof(T)));
+      }
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+      template<typename U, typename... Args>
+	void
+	construct(U* p, Args&&... args)
+	{ ::new((void *)p) U(std::forward<Args>(args)...); }
+
+      template<typename U>
+	void
+	destroy(U* p)
+	{ p->~U(); }
+#else
+      void
+      construct(pointer p, const T& value)
+      { ::new ((void *)p) T(value); }
+
+      void
+      destroy(pointer p)
+      {	p->~T(); }
+#endif
+
+      void
+      deallocate(pointer p, size_type num)
+      { ::operator delete(p); }
     };
-
 } // namespace __gnu_test
 
 #endif // _GLIBCXX_TESTSUITE_ALLOCATOR_H

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]