I found a crash in my program, which boils down to the following code. (Note that this does usually not crash, but will be reported by valgrind with invalid read after free. Also note that depending no possible internals of the bucket hashing stuff, the value for i where it crashes might change, so you can use the random part multiple times to figure out a new one) #include <unordered_map> #include <cstddef> #include <cstdlib> #include <cassert> #include <ctime> #include <iostream> struct A { int x; }; int main ( ) { srand(time(0)); std::unordered_map<int,A> map; map.max_load_factor(2.0); for (size_t i = 0; i < 50; ++i) { A a; a.x = i; map.insert({i,a}); } // int i = rand() % map.size(); int i = 47; std::cout << "i = " << i << "\n"; const A& a = map[i]; map.erase(a.x); } // vim: tabstop=4 shiftwidth=4 noexpandtab ft=cpp This seems to be due to the while condition in hashtable.h:1526 accessing __k after the _M_deallocate_node(__p) of line 1517 while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n)); I think it is better that after the erase of the node, __k should not be touched anymore as it migh be part of the object being erased.
Francois, could you take a look please? Thanks. It reminds me of PR 51866, it might be good to review all the code for similar lifetime issues following deallocation or moving.
I will have a closer look but what I can say for the moment is that the tested source code doesn't seem to match the latest trunk state, the line numbers don't match. Can you have a check with latest version ? For info, there is a check on the address of the key to avoid just what you describe that is to say deallocate a node and keep on using the key part of it.
I can confirm the valgrind error: ==7930== Memcheck, a memory error detector ==7930== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al. ==7930== Using Valgrind-3.6.1 and LibVEX; rerun with -h for copyright info ==7930== Command: ./a.out ==7930== i = 47 ==7930== Invalid read of size 4 ==7930== at 0x40344C: std::equal_to<int>::operator()(int const&, int const&) const (in /home/paolo/Work/a.out) ==7930== by 0x402F6D: std::__detail::_Equal_helper<int, std::pair<int const, A>, std::__detail::_Select1st, std::equal_to<int>, unsigned long, false>::_S_equals(std::equal_to<int> const&, std::__detail::_Select1st const&, int const&, unsigned long, std::__detail::_Hash_node<std::pair<int const, A>, false>*) (in /home/paolo/Work/a.out) ==7930== by 0x4027D5: std::__detail::_Hashtable_base<int, std::pair<int const, A>, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<false, false, true> >::_M_equals(int const&, unsigned long, std::__detail::_Hash_node<std::pair<int const, A>, false>*) const (in /home/paolo/Work/a.out) ==7930== by 0x401D8C: std::_Hashtable<int, std::pair<int const, A>, std::allocator<std::pair<int const, A> >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::erase(int const&) (in /home/paolo/Work/a.out) ==7930== by 0x400EB6: main (in /home/paolo/Work/a.out) ==7930== Address 0x5d6130c is 12 bytes inside a block of size 16 free'd ==7930== at 0x4C285BC: operator delete(void*) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so) ==7930== by 0x402D85: __gnu_cxx::new_allocator<std::__detail::_Hash_node<std::pair<int const, A>, false> >::deallocate(std::__detail::_Hash_node<std::pair<int const, A>, false>*, unsigned long) (in /home/paolo/Work/a.out) ==7930== by 0x402756: std::_Hashtable<int, std::pair<int const, A>, std::allocator<std::pair<int const, A> >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::_M_deallocate_node(std::__detail::_Hash_node<std::pair<int const, A>, false>*) (in /home/paolo/Work/a.out) ==7930== by 0x401D29: std::_Hashtable<int, std::pair<int const, A>, std::allocator<std::pair<int const, A> >, std::__detail::_Select1st, std::equal_to<int>, std::hash<int>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<false, false, true> >::erase(int const&) (in /home/paolo/Work/a.out) ==7930== by 0x400EB6: main (in /home/paolo/Work/a.out) ==7930== ==7930== ==7930== HEAP SUMMARY: ==7930== in use at exit: 0 bytes in 0 blocks ==7930== total heap usage: 55 allocs, 55 frees, 1,488 bytes allocated ==7930== ==7930== All heap blocks were freed -- no leaks are possible ==7930== ==7930== For counts of detected and suppressed errors, rerun with: -v ==7930== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 6 from 6)
In current mainline line # is 1496.
Interestingly, however, I'm seeing a *very* similar valgrind error with 4.6.2 and 4.5.4 (which had the "old" implementation). Dennis, which is the oldest GCC version which worked fine with your code? Because the snippet attached here, whatever it shows in terms of valgrind, doesn't look like a regression, frankly. Maybe it's a serious issue, we should investigate further - false alarms are possible, though - but it's something which isn't new. Dennis, likely we need a snippet closer to the code actually crashing for you to make further progress.
And of course I concur with Francois about the weird line number: current 4.8.0 doesn't have that line of code at that line number, it looks like Dennis you are not using 4.8.0 but something else. But more importantly we badly need a snippet actually crashing and also it would be very useful to know which older version worked for you.
I confirm that it is an old issue, it has surely always be there. I managed to reproduce it from the testsuite. The problem is that the current code works fine when the key instance is taken from the container keys but doesn't work when it is extracted from the container values. The current address check is not reliable because the passed key instance could be anywhere within the mapped value. I am preparing a patch to separate the loop used to find the nodes to erase from the loop used to deallocate them.
Ah, very well, thanks Francois.
Author: fdumont Date: Wed Sep 5 19:41:16 2012 New Revision: 190991 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=190991 Log: 2012-09-05 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 the new member functions. * testsuite/23_containers/unordered_map/erase/54296.cc: New. * testsuite/23_containers/unordered_multimap/erase/54296.cc: New. Added: trunk/libstdc++-v3/testsuite/23_containers/unordered_map/erase/54276.cc trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/erase/54276.cc Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/bits/hashtable.h
Fixed.