[v3] libstdc++/54296

[François Dumont <frs dot dumont at gmail dot com>]

Hi

    Here is the patch for this issue. I introduced 2 distinct methods 
to erase elements from a key. The one when keys are unique is rather 
simple and now use the same underlying code that the erase method from 
iterator. The other one when keys are not unique first look for nodes 
matching the key and deallocate those in a second loop so that it 
doesn't invalidate the key while looking for nodes. I considered 
checking if the key instance address was inside the node address space 
but the key instance might also be referenced as a pointer in the value 
type free when the value instance is destroyed. Separating is the only 
way to be sure that the key won't be broken while looking for matching 
nodes.

    I check that _Rb_tree is not impacted by this issue as it is using 
a call to equal_range first and erase the range after. I considered 
doing the same in _Hashtable implementation but finally preferred not to 
do so because it would imply re-computing hash code and add useless checks.

2012-08-28  François Dumont <fdumont@gcc.gnu.org>

    PR libstdc++/54296
    * include/bits/hashtable.h (_M_erase(size_type, __node_base*,
    __node_type*)): New.
    (erase(const_iterator)): Use latter.
    (_M_erase(std::true_type, const key_type&)): New, likewise.
    (_M_erase(std::false_type, const key_type&)): New. Find all nodes
    matching the key before deallocating them so that the key doesn't
    get invalidated.
    (erase(const key_type&)): Use latters.
    * testsuite/23_containers/unordered_map/erase/54296.cc: New.
    * testsuite/23_containers/unordered_multimap/erase/54296.cc: New.

Tested under linux x86_64.

Ok for trunk ? As it is an old issue I don't think it needs to be apply 
to any branch, tell me otherwise.

François

Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 190703)
+++ include/bits/hashtable.h	(working copy)
@@ -612,6 +612,15 @@
 	iterator
 	_M_insert(_Arg&&, std::false_type);
 
+      size_type
+      _M_erase(std::true_type, const key_type&);
+
+      size_type
+      _M_erase(std::false_type, const key_type&);
+
+      iterator
+      _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
+
     public:
       // Emplace
       template<typename... _Args>
@@ -636,7 +645,8 @@
       { return erase(const_iterator(__it)); }
 
       size_type
-      erase(const key_type&);
+      erase(const key_type& __k)
+      { return _M_erase(__unique_keys(), __k); }
 
       iterator
       erase(const_iterator, const_iterator);
@@ -1430,7 +1440,21 @@
       // is why we need buckets to contain the before begin to make
       // this research fast.
       __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
-      if (__n == _M_bucket_begin(__bkt))
+      return _M_erase(__bkt, __prev_n, __n);
+    }
+
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+			_H1, _H2, _Hash, _RehashPolicy,
+			_Traits>::iterator
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
+    {
+      if (__prev_n == _M_buckets[__bkt])
 	_M_remove_bucket_begin(__bkt, __n->_M_next(),
 	   __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
       else if (__n->_M_nxt)
@@ -1457,7 +1481,7 @@
 			_Traits>::size_type
     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
-    erase(const key_type& __k)
+    _M_erase(std::true_type, const key_type& __k)
     {
       __hash_code __code = this->_M_hash_code(__k);
       std::size_t __bkt = _M_bucket_index(__k, __code);
@@ -1466,43 +1490,67 @@
       __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
       if (!__prev_n)
 	return 0;
+
+      // We found a matching node, erase it.
       __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
-      bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
+      _M_erase(__bkt, __prev_n, __n);
+      return 1;
+    }
 
-      // We found a matching node, start deallocation loop from it
-      std::size_t __next_bkt = __bkt;
-      __node_type* __next_n = __n;
+  template<typename _Key, typename _Value,
+	   typename _Alloc, typename _ExtractKey, typename _Equal,
+	   typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
+	   typename _Traits>
+    typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+			_H1, _H2, _Hash, _RehashPolicy,
+			_Traits>::size_type
+    _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+	       _H1, _H2, _Hash, _RehashPolicy, _Traits>::
+    _M_erase(std::false_type, const key_type& __k)
+    {
+      __hash_code __code = this->_M_hash_code(__k);
+      std::size_t __bkt = _M_bucket_index(__k, __code);
+
+      // Look for the node before the first matching node.
+      __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
+      if (!__prev_n)
+	return 0;
+
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 526. Is it undefined if a function in the standard changes
+      // in parameters?
+      // We use one loop to find all matching nodes and another to deallocate
+      // them so that the key stays valid during the first loop. It might be
+      // invalidated indirectly when destroying nodes.
+      __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
+      __node_type* __n_last = __n;
+      std::size_t __n_last_bkt = __bkt;
+      do
+	{
+	  __n_last = __n_last->_M_next();
+	  if (!__n_last)
+	    break;
+	  __n_last_bkt = _M_bucket_index(__n_last);
+	}
+      while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
+
+      // Deallocate nodes.
       size_type __result = 0;
-      __node_type* __saved_n = nullptr;
       do
 	{
-	  __node_type* __p = __next_n;
-	  __next_n = __p->_M_next();
-
-	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
-	  // 526. Is it undefined if a function in the standard changes
-	  // in parameters?
-	  if (std::__addressof(this->_M_extract()(__p->_M_v))
-	      != std::__addressof(__k))
-	    _M_deallocate_node(__p);
-	  else
-	    __saved_n = __p;
+	  __node_type* __p = __n->_M_next();
+	  _M_deallocate_node(__n);
+	  __n = __p;
+	  ++__result;
 	  --_M_element_count;
-	  ++__result;
-	  if (!__next_n)
-	    break;
-	  __next_bkt = _M_bucket_index(__next_n);
 	}
-      while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
+      while (__n != __n_last);
 
-      if (__saved_n)
-	_M_deallocate_node(__saved_n);
-      if (__is_bucket_begin)
-	_M_remove_bucket_begin(__bkt, __next_n, __next_bkt);
-      else if (__next_n && __next_bkt != __bkt)
-	_M_buckets[__next_bkt] = __prev_n;
-      if (__prev_n)
-	__prev_n->_M_nxt = __next_n;
+      if (__prev_n == _M_buckets[__bkt])
+	_M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
+      else if (__n_last && __n_last_bkt != __bkt)
+	_M_buckets[__n_last_bkt] = __prev_n;
+      __prev_n->_M_nxt = __n_last;
       return __result;
     }
 
Index: testsuite/23_containers/unordered_multimap/erase/54276.cc
===================================================================
--- testsuite/23_containers/unordered_multimap/erase/54276.cc	(revision 0)
+++ testsuite/23_containers/unordered_multimap/erase/54276.cc	(revision 0)
@@ -0,0 +1,101 @@
+// Copyright (C) 2012 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++0x" }
+
+#include <set>
+#include <unordered_map>
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+struct A
+{
+  int x;
+  static std::set<const A*> destroyed;
+
+  A()
+  { destroyed.erase(this); }
+
+  A(const A& a)
+    : x(a.x)
+  { destroyed.erase(this); }
+
+  ~A()
+  { destroyed.insert(this); }
+
+  bool
+  operator==(const A& other) const
+  {
+    VERIFY( destroyed.find(this) == destroyed.end() );
+    VERIFY( destroyed.find(&other) == destroyed.end() );
+    return x == other.x;
+  }
+};
+
+std::set<const A*> A::destroyed;
+
+struct hasher
+{
+  std::size_t operator()(const A& a) const
+  {
+    VERIFY( A::destroyed.find(&a) == A::destroyed.end() );
+    return a.x / 10;
+  }
+};
+
+void test01()
+{
+  typedef std::unordered_multimap<A, A, hasher> UMMap;
+  UMMap map;
+
+  A::destroyed.clear();
+  A a;
+  a.x = 0;
+  map.insert({a, a});
+  map.insert({a, a});
+  VERIFY( map.size() == 2 );
+  std::size_t bkt = map.bucket(a);
+  VERIFY( map.bucket_size(bkt) == 2 );
+
+  VERIFY( map.erase( map.begin(bkt)->first ) == 2 );
+}
+
+void test02()
+{
+  typedef std::unordered_multimap<A, A, hasher> UMMap;
+  UMMap map;
+
+  A::destroyed.clear();
+  A a;
+  a.x = 0;
+  map.insert({a, a});
+  map.insert({a, a});
+  VERIFY( map.size() == 2 );
+  std::size_t bkt = map.bucket(a);
+  VERIFY( map.bucket_size(bkt) == 2 );
+
+  VERIFY( map.erase( map.begin(bkt)->second ) == 2 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}
Index: testsuite/23_containers/unordered_map/erase/54276.cc
===================================================================
--- testsuite/23_containers/unordered_map/erase/54276.cc	(revision 0)
+++ testsuite/23_containers/unordered_map/erase/54276.cc	(revision 0)
@@ -0,0 +1,103 @@
+// Copyright (C) 2012 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++0x" }
+
+#include <set>
+#include <unordered_map>
+#include <testsuite_hooks.h>
+
+bool test __attribute__((unused)) = true;
+
+struct A
+{
+  int x;
+  static std::set<const A*> destroyed;
+
+  A()
+  { destroyed.erase(this); }
+
+  A(const A& a)
+    : x(a.x)
+  { destroyed.erase(this); }
+
+  ~A()
+  { destroyed.insert(this); }
+
+  bool
+  operator==(const A& other) const
+  {
+    VERIFY( destroyed.find(this) == destroyed.end() );
+    VERIFY( destroyed.find(&other) == destroyed.end() );
+    return x == other.x;
+  }
+};
+
+std::set<const A*> A::destroyed;
+
+struct hasher
+{
+  std::size_t operator()(const A& a) const
+  {
+    VERIFY( A::destroyed.find(&a) == A::destroyed.end() );
+    return a.x / 10;
+  }
+};
+
+void test01()
+{
+  typedef std::unordered_map<A, A, hasher> UMap;
+  UMap map;
+
+  A::destroyed.clear();
+  A a;
+  a.x = 0;
+  map.insert({a, a});
+  a.x = 1;
+  map.insert({a, a});
+  VERIFY( map.size() == 2 );
+  std::size_t bkt = map.bucket(a);
+  VERIFY( map.bucket_size(bkt) == 2 );
+
+  VERIFY( map.erase( map.begin(bkt)->first ) == 1 );
+}
+
+void test02()
+{
+  typedef std::unordered_map<A, A, hasher> UMap;
+  UMap map;
+
+  A::destroyed.clear();
+  A a;
+  a.x = 0;
+  map.insert({a, a});
+  a.x = 1;
+  map.insert({a, a});
+  VERIFY( map.size() == 2 );
+  std::size_t bkt = map.bucket(a);
+  VERIFY( map.bucket_size(bkt) == 2 );
+
+  VERIFY( map.erase( map.begin(bkt)->second ) == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}