[Container] Strange flat_set crash with std::inserter

6 Sep 2013

      ...
::operator() (this=0x7fffffffd598, lhs=@0x7ffff61c6320: 61595138,
rhs=@0x454000: <error reading variable>) at
../yy/build/boost/boost/container/detail/flat_tree.hpp:66
#2  0x0000000000404367 in
boost::container::container_detail::flat_tree
...
::priv_insert (this=0x7fffffffd598, p=...,
x=@0x7ffff61c6320: 61595138) at
../yy/build/boost/boost/container/flat_set.hpp:688
#5  0x00000000004041bd in boost::container::flat_set
Hi all

It seems that when I copy a sorted but non-unique range of randomly
generated numbers to an output iterator generated from std::inserter to
a boost::flat_set it crashes.

At first I assumed it was because boost::flat_set doesn't have stable
iterators, but it seems that the implementation of std::insert_iterator
does the right thing by reassigning its internal iterator to the result
of the insert operation before incrementing it.

Apologies for not being able to reduce the problem further, but this one
is a little strange, the following code demonstrates the problem (and
some variations that do work) in boost 1.54:

#include 
#include <algorithm>
#include <iterator>
#include <numeric>
#include <vector>

template<typename ContainerT>
void Populate(std::vector const& input) {
   ContainerT container;
   std::copy(
      std::begin(input),
      std::end(input),
      std::inserter(container, std::end(container)));
}

int main() {
   const size_t Count = 1000000;

   std::vector random_numbers;
   random_numbers.reserve(Count);
   std::generate_n(
      std::back_inserter(random_numbers),
      Count,
      &std::rand);

   std::vector sorted_numbers(random_numbers);
   std::sort(std::begin(sorted_numbers), std::end(sorted_numbers));

   std::vector unique_sorted_numbers;
   unique_sorted_numbers.reserve(Count);
   std::unique_copy(
      std::begin(sorted_numbers),
      std::end(sorted_numbers),
      std::back_inserter(unique_sorted_numbers));

   using namespace boost::container;
   Populate>(unique_sorted_numbers); // ok
   Populate>(sorted_numbers); // ok
   Populate>(sorted_numbers); // segfault, line 39
}

It might be a little hard to reproduce with the rand() in there, I'm on
64bit Ubuntu 13.04 and it's reproducible with Clang 3.3 with libc++ and
GCC 4.8.1.

Here's the backtrace from Clang:

#0  0x0000000000403aec in operator() (this=0x7fffffffd598,
__x=@0x7ffff61c6320: 61595138, __y=@0x454000: <error reading variable>)
at /usr/include/c++/v1/__functional_base:61
#1
boost::container::container_detail::flat_tree_value_compare
...
...
...
(__i=..., __first=..., __last=..., __result=...) at
/usr/include/c++/v1/algorithm:1717
#8  end >
(__c=..., __x=..., __i=..., __first=..., __last=..., __result=...) at
/usr/include/c++/v1/algorithm:1741
#9  Populate >
(input=...) at flat_set_crash.cpp:13
#10 0x00000000004017a6 in main () at flat_set_crash.cpp:39
or from GCC if you prefer:

#0  0x0000000000404bed in std::less<unsigned long>::operator()
(this=0x7fffffffdd10, __x=@0x7ffff62e7320: 61595138, __y=@0x453000:
<error reading variable>) at /usr/include/c++/4.8/bits/stl_function.h:235
#1  0x00000000004047f9 in
boost::container::container_detail::flat_tree_value_compare
...
::operator() (this=0x7fffffffdd10, lhs=@0x7ffff62e7320: 61595138,
rhs=@0x453000: <error reading variable>) at
../yy/build/boost/boost/container/detail/flat_tree.hpp:66
#2  0x0000000000404389 in
boost::container::container_detail::flat_tree::insert_unique
(this=0x7fffffffdd10, pos=..., val=@0x7ffff62e7320: 61595138) at
../yy/build/boost/boost/container/detail/flat_tree.hpp:354
#4  0x00000000004040ef in boost::container::flat_set (this=0x7fffffffdd10, p=...,
x=@0x7ffff62e7320: 61595138) at
../yy/build/boost/boost/container/flat_set.hpp:688
#5  0x0000000000403fa5 in boost::container::flat_set::insert
(this=0x7fffffffdd10, arg1=..., x=@0x7ffff62e7320: 61595138) at
../yy/build/boost/boost/container/flat_set.hpp:508
#6  0x0000000000403b71 in
std::insert_iterator >::operator=
(this=0x7fffffffdbd0, __value=@0x7ffff62e7320: 61595138) at
/usr/include/c++/4.8/bits/stl_iterator.h:640
#7  0x000000000040350a in std::__copy_move::__copy_m > >
(__first=0x7ffff62e7320, __last=0x7ffff6a50210, __result=...) at
/usr/include/c++/4.8/bits/stl_algobase.h:335
#8  0x0000000000402c2f in std::__copy_move_a > >
(__first=0x7ffff62af010, __last=0x7ffff6a50210, __result=...) at
/usr/include/c++/4.8/bits/stl_algobase.h:390
#9  0x000000000040237f in std::__copy_move_a2 >,
std::insert_iterator > >
(__first=1210, __last=0, __result=...) at
/usr/include/c++/4.8/bits/stl_algobase.h:428
#10 0x0000000000401b70 in
std::copy<__gnu_cxx::__normal_iterator >,
std::insert_iterator > >
(__first=1210, __last=0, __result=...) at
/usr/include/c++/4.8/bits/stl_algobase.h:460
#11 0x000000000040120f in Populate >
(input=std::vector of length 1000000, capacity 1000000 = {...}) at
flat_set_crash.cpp:10
#12 0x0000000000400c50 in main () at flat_set_crash.cpp:39
(gdb)
Since my refactoring of the code above, the crash location has changed,
it used to be in:
boost::container::vector::priv_forward_range_insert_at_end_expand_forward
boost/container/vector.hpp:2205

unique_sorted_numbers.size() is 999752.  Unfortunately producing a
sequential list of numbers with std::iota and then changing one of them
to the proceeding value didn't repro the problem.

Ben

Ben Pope

Ion Gaztañaga

tags

participants (2)