[Bug libstdc++/53115] New: _Hashtable::_M_rehash_aux(false_type) is broken

[Bug libstdc++/53115] New: _Hashtable::_M_rehash_aux(false_type) is broken

[tat_13 at mail dot ru]

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

             Bug #: 53115
           Summary: _Hashtable::_M_rehash_aux(false_type) is broken
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: critical
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: tat_13@mail.ru


Function _Hashtable::_M_rehash_aux, added in rev. libstdc++/52476, is broken
for not unique keys (unordered_multiset and unordered_multimap).

Scheduled checking after series of equal elements is performed after inserting
of next different element. This can lead to invalid bucket links and broken
equal_range/count.

Below is simple example that demonstrates this bug.

#include <stdio.h>
#include <unordered_set>

typedef std::unordered_multiset<int> TMap;

int main()
{
    TMap x;

    x.insert(10);
    x.insert(10);
    x.insert(10);
    x.insert(10);
    x.insert(10);
    x.insert(24);
    x.insert(25);
    x.insert(2);
    x.insert(2);
    x.insert(1);

    printf("count=%u\n", x.count(2));

    x.insert(10);

    printf("count=%u\n", x.count(2));

    return 0;
}

Output is:

count=2
count=0

[Bug libstdc++/53115] _Hashtable::_M_rehash_aux(false_type) is broken

[paolo.carlini at oracle dot com]

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

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

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

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-04-25 14:30:49 UTC ---
Francois, can you have a look ASAP? The issue seems pretty serious. Thanks.

[Bug libstdc++/53115] [4.7/4.8 Regression] _Hashtable::_M_rehash_aux(false_type) is broken

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-04-25
            Version|4.7.0                       |4.7.1
   Target Milestone|---                         |4.7.1
            Summary|_Hashtable::_M_rehash_aux(f |[4.7/4.8 Regression]
                   |alse_type) is broken        |_Hashtable::_M_rehash_aux(f
                   |                            |alse_type) is broken
     Ever Confirmed|0                           |1
           Severity|critical                    |normal

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-04-25 14:36:19 UTC ---
But to be clear, this is a 4.7.1 *not* 4.7.0 issue. The released 4.7.0 is not
affected, we can fix the issue in time for 4.7.1.

[Bug libstdc++/53115] [4.7/4.8 Regression] _Hashtable::_M_rehash_aux(false_type) is broken

[tat_13 at mail dot ru]

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

--- Comment #3 from Timothy Tenebekov <tat_13 at mail dot ru> 2012-04-25 14:55:33 UTC ---
I got this revision of bits/hashtable.h while upgrading gcc to version 4.7.0 on
Debian using http://packages.dotdeb.org repository.

[Bug libstdc++/53115] [4.7/4.8 Regression] _Hashtable::_M_rehash_aux(false_type) is broken

[paolo.carlini at oracle dot com]

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

--- Comment #4 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-04-25 15:14:41 UTC ---
I have no idea what they are doing, definitely FSF 4.7.0 is not affected.

[Bug libstdc++/53115] [4.7/4.8 Regression] _Hashtable::_M_rehash_aux(false_type) is broken

[fdumont at gcc dot gnu.org]

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

--- Comment #5 from François Dumont <fdumont at gcc dot gnu.org> 2012-05-01 19:38:35 UTC ---
Author: fdumont
Date: Tue May  1 19:38:28 2012
New Revision: 187023

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=187023
Log:
2012-05-01  François Dumont  <fdumont@gcc.gnu.org>

    PR libstdc++/53115
    * include/bits/hashtable.h
    (_Hashtable<>::_M_rehash_aux(size_type, false_type)): Fix buckets
    after insertion of several equivalent elements.
    * testsuite/23_containers/unordered_multiset/insert/53115.cc: New.
    * testsuite/23_containers/unordered_multimap/insert/53115.cc: New.

Added:
   
branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/53115.cc
   
branches/gcc-4_7-branch/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/53115.cc
Modified:
    branches/gcc-4_7-branch/libstdc++-v3/ChangeLog
    branches/gcc-4_7-branch/libstdc++-v3/include/bits/hashtable.h

[Bug libstdc++/53115] [4.7/4.8 Regression] _Hashtable::_M_rehash_aux(false_type) is broken

[fdumont at gcc dot gnu.org]

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

--- Comment #6 from François Dumont <fdumont at gcc dot gnu.org> 2012-05-01 20:29:24 UTC ---
Author: fdumont
Date: Tue May  1 20:29:16 2012
New Revision: 187025

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=187025
Log:
2012-05-01  François Dumont  <fdumont@gcc.gnu.org>

    PR libstdc++/53115
    * include/bits/hashtable.h
    (_Hashtable<>::_M_rehash_aux(size_type, false_type)): Fix buckets
    after insertion of several equivalent elements.
    * testsuite/23_containers/unordered_multiset/insert/53115.cc: New.
    * testsuite/23_containers/unordered_multimap/insert/53115.cc: New.

Added:
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multimap/insert/53115.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/53115.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/hashtable.h

[Bug libstdc++/53115] [4.7/4.8 Regression] _Hashtable::_M_rehash_aux(false_type) is broken

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
      Known to fail|4.7.1, 4.8.0                |

--- Comment #7 from Paolo Carlini <paolo.carlini at oracle dot com> 2012-05-01 23:42:29 UTC ---
Fixed for mainline and 4.7.1.