[Bug libstdc++/55911] New: Segfault in unordered_map with max_load_factor > 1

[Bug libstdc++/55911] New: Segfault in unordered_map with max_load_factor > 1

[timj at gtk dot org]

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

             Bug #: 55911
           Summary: Segfault in unordered_map with max_load_factor > 1
    Classification: Unclassified
           Product: gcc
           Version: 4.7.2
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: timj@gtk.org


Created attachment 29114
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29114
C++11 unordered_map segfault example

The attached test program segfaults when compiled and executed with the
following g++ versions:
g++-4.7 (Ubuntu/Linaro 4.7.2-11precise2) 4.7.2
g++-4.6 (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

The program inserts values into an unordered_map and iterates over it's bucket
stats. Removing the line
> pmap.max_load_factor (50);
does not cause a segfault.

Example output:
$ g++ -g -Wall -O2 -std=gnu++0x -pthread umap-bug.cc && dbg ./a.out         
unordered_map:        max_size: 768614336404564650
unordered_map:            size: 10352716
unordered_map:    bucket_count: 218971
unordered_map:     load_factor: 47.278938
unordered_map: max_load_factor: 50.000000

Program received signal SIGSEGV, Segmentation fault.
__distance<std::__detail::_Node_const_iterator<std::pair<long const, double>,
false, false> > (__last=..., __first=...)
    at /usr/include/c++/4.6/bits/stl_iterator_base_funcs.h:82
82                ++__first;
(gdb) bt
#0  __distance<std::__detail::_Node_const_iterator<std::pair<long const,
double>, false, false> > (__last=..., __first=...)
    at /usr/include/c++/4.6/bits/stl_iterator_base_funcs.h:82
#1  distance<std::__detail::_Node_const_iterator<std::pair<long const, double>,
false, false> > (__last=..., __first=...)
    at /usr/include/c++/4.6/bits/stl_iterator_base_funcs.h:117
#2  bucket_size (__n=218971, this=0x7fffffffde30) at
/usr/include/c++/4.6/bits/hashtable.h:299
#3  unordered_map_bucket_stats<std::unordered_map<long, double, HashPtrdiff> >
(umap=...) at umap-bug.cc:16
#4  main (argc=<optimized out>, argv=<optimized out>) at umap-bug.cc:55

[Bug libstdc++/55911] Segfault in unordered_map with max_load_factor > 1

[paolo.carlini at oracle dot com]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-01-09
                 CC|                            |fdumont at gcc dot gnu.org,
                   |                            |frs.dumont at gmail dot com
     Ever Confirmed|0                           |1

--- Comment #1 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-09 10:08:19 UTC ---
I can reproduce this.

Francois can you have a look ASAP? Thanks in advance.

[Bug libstdc++/55911] Segfault in unordered_map with max_load_factor > 1

[paolo.carlini at oracle dot com]

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

--- Comment #2 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-09 11:38:03 UTC ---
Important note: I can reproduce the Segmentation fault way back to 4_5-branch,
in other terms, whatever it is, happened also with the old implementation very
close to the TR1 containers.

[Bug libstdc++/55911] Segfault in unordered_map with max_load_factor > 1

[redi at gcc dot gnu.org]

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-01-09 12:15:39 UTC ---
This is invalid if size() > bucket_count(), which is very likely:

  for (size_t i = 0; i < umap.size(); i++)
    {
      const size_t bs = umap.bucket_size (i);

Shouldn't the loop condition be i < umap.bucket_count() instead?

[Bug libstdc++/55911] Segfault in unordered_map with max_load_factor > 1

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-01-09 12:16:51 UTC ---
Debug Mode even catches it:

unordered_map:        max_size: 576460752303423487
unordered_map:            size: 10352716
unordered_map:    bucket_count: 218971
unordered_map:     load_factor: 47.278938
unordered_map: max_load_factor: 50.000000
/home/wakelj/tools/Linux-f12-x86_64/4.8/include/c++/4.8.0/debug/unordered_map:229:
    error: attempt to access container with out-of-bounds bucket index
    218971, container only holds 218971 buckets.

Objects involved in the operation:
sequence "this" @ 0x0x7fffd8ae2810 {
  type = NSt7__debug13unordered_mapIld11HashPtrdiffSt8equal_toIlESaIlEEE;
}
Aborted (core dumped)

[Bug libstdc++/55911] Segfault in unordered_map with max_load_factor > 1

[redi at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|major                       |normal

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-01-09 12:19:11 UTC ---
When load_factor > 1 there will be more than 1 element in some buckets,
implying fewer buckets than elements, so the loop accesses non-existent
buckets.

When load_factor==1 the bucket_count() == size() so the loop succeeds (but is
still potentially wrong because the load_factor is only the *average* number of
elements per bucket.)

[Bug libstdc++/55911] Segfault in unordered_map with max_load_factor > 1

[paolo.carlini at oracle dot com]

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

--- Comment #6 from Paolo Carlini <paolo.carlini at oracle dot com> 2013-01-09 14:47:12 UTC ---
Thanks Jon.

[Bug libstdc++/55911] Segfault in unordered_map with max_load_factor > 1

[timj at gtk dot org]

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

--- Comment #7 from Tim Janik <timj at gtk dot org> 2013-01-28 01:13:04 UTC ---
(In reply to comment #4)
> Debug Mode even catches it:
> 
> unordered_map:        max_size: 576460752303423487
> unordered_map:            size: 10352716
> unordered_map:    bucket_count: 218971
> unordered_map:     load_factor: 47.278938
> unordered_map: max_load_factor: 50.000000
> /home/wakelj/tools/Linux-f12-x86_64/4.8/include/c++/4.8.0/debug/unordered_map:229:
>     error: attempt to access container with out-of-bounds bucket index
>     218971, container only holds 218971 buckets.
> 
> Objects involved in the operation:
> sequence "this" @ 0x0x7fffd8ae2810 {
>   type = NSt7__debug13unordered_mapIld11HashPtrdiffSt8equal_toIlESaIlEEE;
> }
> Aborted (core dumped)

Thanks, I'm impressed to see that.
How did you get that message? Just using g++-4.7 -D_GLIBCXX_DEBUG still gives
me the segfault.

[Bug libstdc++/55911] Segfault in unordered_map with max_load_factor > 1

[redi at gcc dot gnu.org]

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

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> 2013-01-28 01:29:11 UTC ---
I think there are extra debug checks in unordered_map on the GCC trunk that
aren't in the 4.7 release.