id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
12919,multi_index indexed with hashed_non_unique produces buffer overrun.,Alex Huszagh <ahuszagh@…>,Joaquín M López Muñoz,"Using multi_index_container on a struct indexing using hashed_non_unique (hashing a std::string) can cause a buffer overrun in unchecked_rehash(size_type,hashed_non_unique_tag), typically culminating in a segfault.

The segment below, taken from lines 1351-1372 of boost/multi_index/hash_index.hpp, can iterate between two different nodes, causing `x==end_` to never occur, causing a auto_space to be overrun, eventually leading to a segmentation fault.

{{{
#!div style=""font-size: 80%""
Code highlighting:
  {{{#!cpp
      auto_space<
        std::size_t,allocator_type>       hashes(get_allocator(),size());
      auto_space<
        node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
      std::size_t                         i=0;
      bool                                within_bucket=false;
       BOOST_TRY{
        for(;;++i){
          node_impl_pointer x=end_->prior();
          if(x==end_)break;

          /* only this can possibly throw */
          std::size_t h=hash_(key(node_type::from_impl(x)->value()));

          hashes.data()[i]=h;
          node_ptrs.data()[i]=x;
          std::pair<node_impl_pointer,bool> p=
            node_alg::unlink_last_group(end_);
          node_alg::link_range(
            p.first,x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
          within_bucket=!(p.second);
        }
      }
   }}}
}}}

The solution is quite simple, and is shown in the other implementation of unchecked_rehash(size_type,hashed_unique_tag), by ensuring the rehash does not exceed the number of elements. The proper implementation (possibly suboptimal) would look something like this:

{{{
#!div style=""font-size: 80%""
Code highlighting:
  {{{#!cpp
      auto_space<
        std::size_t,allocator_type>       hashes(get_allocator(),size());
      auto_space<
        node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
      std::size_t                         i=0, size_=size();
      bool                                within_bucket=false;
       BOOST_TRY{
        for(;i!=size_;++i){
          node_impl_pointer x=end_->prior();
          if(x==end_)break;

          /* only this can possibly throw */
          std::size_t h=hash_(key(node_type::from_impl(x)->value()));

          hashes.data()[i]=h;
          node_ptrs.data()[i]=x;
          std::pair<node_impl_pointer,bool> p=
            node_alg::unlink_last_group(end_);
          node_alg::link_range(
            p.first,x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
          within_bucket=!(p.second);
        }
      }
   }}}
}}}

As the data leading to this segfault is private, I currently do not have a minimal, verified example to reproduce the bug, however, I believe this is a rational explanation, with a straight-forward fix.

I've seen examples where an ~800 element buffer will continue until i > 15,000, culminating in a segfault. I will submit a pull request with the above diff.

Thanks,
Alex",Bugs,closed,To Be Determined,multi_index,Boost 1.63.0,Problem,invalid,multi_index,joaquin@…