[PATCH] Fix _Hashtable::erase(iterator, iterator) (PR libstdc++/51845)

[Jakub Jelinek]

On Thu, Jan 19, 2012 at 12:16:01AM +0100, Jakub Jelinek wrote:
> As described in the PR, if two argument erase is removing the last
> element of one bucket (i.e. the one referenced in _M_buckets array
> for the next bucket) and then at least one element from the
> following bucket, but not all elements from that next bucket,
> __is_bucket_begin is initially false and in the second for (;;) iteration,
> while it is already true, __n_bkt == __bkt and thus _M_remove_bucket_begin
> doesn't do anything, and following if (__n && __n_bkt != __bkt) is
> false as well (1 && 0), thus nothing is changed in the _M_buckets array
> and we end up referencing there a removed element.  We might crash if we
> read it and if we modify it, we usually corrupt malloc data structures.

If you want a testcase that fails on x86_64-linux without the patch and
succeeds with it, here it is:

2012-01-19  Jakub Jelinek  <jakub@redhat.com>

	PR libstdc++/51845
	* testsuite/23_containers/unordered_multimap/erase/51845-multimap.cc:
	New test.

--- libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/51845-multimap.cc.jj	2012-01-19 09:23:56.667642676 +0100
+++ libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/51845-multimap.cc	2012-01-19 09:24:50.253325306 +0100
@@ -0,0 +1,72 @@
+// { dg-options "-std=gnu++0x" }
+
+// 2012-01-19  Jakub Jelinek  <jakub@redhat.com>
+//
+// 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/>.
+
+#include <unordered_map>
+#include <testsuite_hooks.h>
+
+// libstdc++/51845
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  typedef std::unordered_multimap<int, int> Mmap;
+  typedef Mmap::iterator       iterator;
+  typedef Mmap::const_iterator const_iterator;
+  typedef Mmap::value_type     value_type;
+
+  Mmap mm1;
+
+  mm1.insert(value_type(11135, 1));
+  mm1.insert(value_type(11135, 17082));
+  mm1.insert(value_type(9644, 24135));
+  mm1.insert(value_type(9644, 9644));
+  mm1.insert(value_type(13984, 19841));
+  mm1.insert(value_type(9644, 1982));
+  mm1.insert(value_type(13984, 1945));
+  mm1.insert(value_type(7, 1982));
+  mm1.insert(value_type(7, 1945));
+  VERIFY( mm1.size() == 9 );
+
+  iterator it1 = mm1.begin();
+  ++it1;
+  iterator it2 = it1;
+  ++it2;
+  ++it2;
+  iterator it3 = mm1.erase(it1, it2);
+  VERIFY( mm1.size() == 7 );
+  VERIFY( it3 == it2 );
+  VERIFY( *it3 == *it2 );
+
+  const_iterator it4 = mm1.begin();
+  ++it4;
+  const_iterator it5 = it4;
+  ++it5;
+  const_iterator it6 = mm1.erase(it4);
+  VERIFY( mm1.size() == 6 );
+  VERIFY( it6 == it5 );
+  VERIFY( *it6 == *it5 );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}

	Jakub