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]

Re: hashtable exception safety patch


On 09/12/2011 12:48 PM, Paolo Carlini wrote:
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.
The patch is largely Ok, I'm attaching below what I have been testing here (formatting fixes in the testcases; resolved a diffing error in testsuite_allocator.h which had removed ExplicitConsAlloc; naming fixes (__prev_resize is not ok because wrongly gives the impression to be the opposite of next_resize), etc).

However, before going ahead, can you see whether you can use instead the existing ext/throw_allocator.h? Or extend / adapt it, I see redundancy here.

Thanks,
Paolo.
Hi

Yes, ext/throw_allocator.h was just what I needed, with even better type names. Here is the patch again with the same ChangeLog entry. Tested under linux x86_64.

Ok to commit ?

François
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 178792)
+++ 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
+      // next resize value to saved_next_resize on exception.
+      void _M_rehash(size_type __n, size_type __saved_next_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 __saved_next_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, __saved_next_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 = __saved_next_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 __saved_next_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, __saved_next_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 __saved_next_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, __saved_next_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 __saved_next_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)),
+		__saved_next_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 __saved_next_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 = __saved_next_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,106 @@
+// { 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 <ext/throw_allocator.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  typedef std::numeric_limits<std::size_t> nl_size_t;
+  std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+		     __gnu_cxx::throw_allocator_limit<int> > us;
+  const int nb = 100;
+  std::size_t 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_cxx::limit_condition::set_limit(scheduled_throw_counter++);
+	}
+      try
+	{
+	  VERIFY(us.insert(i).second);
+	  scheduled_throw_counter = 0;
+	}
+      catch (__gnu_cxx::forced_error)
+	{
+	  --i;
+	}
+      VERIFY( us.load_factor() <= us.max_load_factor() );
+      __gnu_cxx::limit_condition::set_limit(nl_size_t::max());
+    }
+
+  // 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;
+
+  typedef std::numeric_limits<std::size_t> nl_size_t;
+  std::unordered_set<int, std::hash<int>, std::equal_to<int>,
+		     __gnu_cxx::throw_allocator_limit<int> > us;
+  const int nb = 100;
+  std::size_t 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_cxx::limit_condition::set_limit(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 (__gnu_cxx::forced_error)
+	{
+	  --i;
+	}
+      VERIFY( us.load_factor() <= us.max_load_factor() );
+      __gnu_cxx::limit_condition::set_limit(nl_size_t::max());
+    }
+
+  // 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 <unordered_set>
+#include <ext/throw_allocator.h>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  typedef std::numeric_limits<std::size_t> nl_size_t;
+  std::unordered_multiset<int, std::hash<int>, std::equal_to<int>,
+			  __gnu_cxx::throw_allocator_limit<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_cxx::limit_condition::set_limit(scheduled_throw_counter++);
+	}
+      try
+	{
+	  us.insert(i / 2);
+	  scheduled_throw_counter = 0;
+	}
+      catch (__gnu_cxx::forced_error)
+	{
+	  --i;
+	}
+      VERIFY( us.load_factor() <= us.max_load_factor() );
+      __gnu_cxx::limit_condition::set_limit(nl_size_t::max());
+    }
+
+  // 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 Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]