Re: [Boost-bugs] [Boost C++ Libraries] #8698: Boost.Intrusive unordered_set should use different value for end()

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #8698: Boost.Intrusive unordered_set should use different value for end()
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-06-22 22:41:05

#8698: Boost.Intrusive unordered_set should use different value for end()
-------------------------------+------------------------
  Reporter:  jody_boost@…      |      Owner:  igaztanaga
      Type:  Bugs              |     Status:  new
 Milestone:  To Be Determined  |  Component:  intrusive
   Version:  Boost 1.53.0      |   Severity:  Problem
Resolution:                    |   Keywords:
-------------------------------+------------------------

Comment (by jody_boost@…):

 Here is a contrived example to illustrate the problem.  Note that while it
 is contrived, the actual problem can occur if the memory allocator
 allocates a node in the first memory location after the buckets array...
 or both the node and the buckets array are on the stack...  the compiler
 has freedom to reorder stack objects and if it reorders the objects in
 this special arrangement, then the collection breaks.


 {{{
 #include <boost/intrusive/unordered_set.hpp>

 struct Foo
 {
   using By_Id_Hook = boost::intrusive::unordered_set_member_hook<
       boost::intrusive::link_mode<boost::intrusive::safe_link>>;
   struct Id_Equal {
     bool operator()(Foo const &lhs, Foo const &rhs) const {
       return lhs.id_ == rhs.id_;
     }
   };
   struct Id_Hash {
     std::size_t operator()(Foo const &x) const {
       return x.id_;
     }
   };
   By_Id_Hook by_id_hook_;
   std::size_t id_;

   using By_Id = boost::intrusive::unordered_set<
       Foo,
       boost::intrusive::member_hook<
           Foo,
           By_Id_Hook,
           &Foo::by_id_hook_>,
       boost::intrusive::equal<Id_Equal>,
       boost::intrusive::hash<Id_Hash>,
       boost::intrusive::power_2_buckets<true>,
       boost::intrusive::constant_time_size<true>,
       boost::intrusive::cache_begin<true>
       >;

   Foo() {
     static std::size_t nextid;
     id_ = nextid++;
   }
 };


 int main()
 {
   // This test demonstrates the problem exactly, though it is a
   // contrived use case.  The problem is that the unordered_set
   // collection uses one-past the end of the buckets array to
   // denote the end of the collection.  So, this example reproduces
   // the problem...
   constexpr size_t num_buckets = 1024;
   struct b_t {
     Foo::By_Id::bucket_type buckets[num_buckets];
     Foo f; // To force node memory location
   } b;
   Foo::By_Id by_id(Foo::By_Id::bucket_traits(b.buckets, num_buckets));

   assert(by_id.size() == 0u);
   assert(by_id.begin() == by_id.end());

   // b.f resides in memory at the same location as one-past the
   // end of the buckets array -- which is also the same value
   // used to denote the "end" of the unordered_set.  That means
   // once we insert b.f into the collection, the collection is
   // broken because the iterator to the object is the same value
   // as "end"
   assert(!b.f.by_id_hook_.is_linked());
   by_id.insert(b.f);
   assert(by_id.size() == 1u); // Collection says it has the value
   assert(b.f.by_id_hook_.is_linked()); // Node says it is linked
   // This assertion will fail...
   assert(by_id.begin() != by_id.end()); // Iterators are broken
 }

 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/8698#comment:3>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.