Re: hashtable exception safety patch

[Paolo Carlini <paolo dot carlini at oracle dot com>]

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.

Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 178778)
+++ 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 __next_resize on exception.
+      void _M_rehash(size_type __n, size_type __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);
@@ -920,14 +922,14 @@
 	    __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
 	  }
 
-	// 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
 	  {
+	    // Allocate the new node before doing the rehash so that we
+	    // don't do a rehash if the allocation throws.
+	    __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 +941,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 +986,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 +1030,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 +1191,11 @@
 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
     rehash(size_type __n)
     {
+      const 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 +1205,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 __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 +1228,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 = __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 <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,67 @@
+// { 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 178778)
+++ 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 178778)
+++ 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;
     };
@@ -441,14 +441,98 @@
       ExplicitConsAlloc() { }
 
       template<typename Up>
-        explicit
-        ExplicitConsAlloc(const ExplicitConsAlloc<Up>&) { }
+ 	explicit
+ 	ExplicitConsAlloc(const ExplicitConsAlloc<Up>&) { }
 
       template<typename Up>
         struct rebind
-        { typedef ExplicitConsAlloc<Up> other; };
+ 	{ typedef ExplicitConsAlloc<Up> other; };
     };
 
+
+  class throwing_allocator_manager
+  {
+    public:
+      // Number of allocations before throwing
+      static int scheduled_counter;
+  };
+
+  template <typename T>
+    class throwing_allocator
+    {
+    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<class U> struct rebind
+      { typedef throwing_allocator<U> 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)
+	      std::__throw_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