[Bug libstdc++/54296] New: using the object in the map to erase element from the map crashes

[Bug libstdc++/54296] New: using the object in the map to erase element from the map crashes

[plasmahh at gmx dot net]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

             Bug #: 54296
           Summary: using the object in the map to erase element from the
                    map crashes
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: plasmahh@gmx.net


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.

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[redi at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fdumont at gcc dot gnu.org

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> 2012-08-17 13:17:06 UTC ---
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.

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[fdumont at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

--- Comment #2 from François Dumont <fdumont at gcc dot gnu.org> 2012-08-26 10:55:43 UTC ---
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.

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-08-26
     Ever Confirmed|0                           |1

--- Comment #3 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-08-26 12:31:10 UTC ---
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)

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-08-26 12:37:50 UTC ---
In current mainline line # is 1496.

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

--- Comment #5 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-08-26 23:07:14 UTC ---
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.

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P2                          |P3

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-08-26 23:20:25 UTC ---
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.

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[fdumont at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

--- Comment #7 from François Dumont <fdumont at gcc dot gnu.org> 2012-08-27 07:58:49 UTC ---
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.

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

--- Comment #8 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-08-27 09:36:08 UTC ---
Ah, very well, thanks Francois.

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[fdumont at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

--- Comment #9 from François Dumont <fdumont at gcc dot gnu.org> 2012-09-05 19:41:21 UTC ---
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

[Bug libstdc++/54296] using the object in the map to erase element from the map crashes

[paolo.carlini at oracle dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54296

Paolo Carlini <paolo.carlini at oracle dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.8.0

--- Comment #10 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-09-07 09:34:30 UTC ---
Fixed.