Re: [Boost-bugs] [Boost C++ Libraries] #10777: unordered_map treats operator== on stateful allocators as stateless

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #10777: unordered_map treats operator== on stateful allocators as stateless
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-11-09 23:49:31

#10777: unordered_map treats operator== on stateful allocators as stateless
-------------------------------+-------------------------
  Reporter:  anonymous         |      Owner:  danieljames
      Type:  Bugs              |     Status:  assigned
 Milestone:  To Be Determined  |  Component:  unordered
   Version:  Boost 1.56.0      |   Severity:  Problem
Resolution:                    |   Keywords:
-------------------------------+-------------------------
Changes (by danieljames):

 * status:  new => assigned


Old description:

> Hi,
>
> here is my problem: I have a stateful allocator that has a bunch of stuff
> inside of it. It can be move-assigned. The problem is that
> boost::unordered_map does this when you have
> propagate_on_container_move_assign typedeffed to true_type:
>
> my_alloc a;
> my_alloc b;
> a = std::move(b);
> ASSERT(a == b);
>
> That assert can obviously never be true if my_alloc is stateful, but this
> sequence of events currently happens in boost::unordered_map.
>
> Here is an allocator that shows the problem:
>
> #pragma once
>
> #include <memory>
> #include <vector>
>
> template<typename T>
> struct plalloc
> {
>     typedef T value_type;
>
>     plalloc() = default;
>     template<typename U>
>     plalloc(const plalloc<U> &) {}
>     plalloc(const plalloc &) {}
>     plalloc & operator=(const plalloc &) { return *this; }
>     plalloc(plalloc &&) = default;
>     plalloc & operator=(plalloc &&) = default;
>
>     typedef std::true_type propagate_on_container_copy_assignment;
>     typedef std::true_type propagate_on_container_move_assignment;
>     typedef std::true_type propagate_on_container_swap;
>
>     bool operator==(const plalloc & other) const
>     {
>         return this == &other;
>     }
>     bool operator!=(const plalloc & other) const
>     {
>         return !(*this == other);
>     }
>
>     T * allocate(size_t num_to_allocate)
>     {
>         if (num_to_allocate != 1)
>         {
>             return static_cast<T *>(::operator new(sizeof(T) *
> num_to_allocate));
>         }
>         else if (available.empty())
>         {
>             // first allocate 8, then double whenever
>             // we run out of memory
>             size_t to_allocate = 8 << memory.size();
>             available.reserve(to_allocate);
>             std::unique_ptr<value_holder[]> allocated(new
> value_holder[to_allocate]);
>             value_holder * first_new = allocated.get();
>             memory.emplace_back(std::move(allocated));
>             size_t to_return = to_allocate - 1;
>             for (size_t i = 0; i < to_return; ++i)
>             {
>                 available.push_back(std::addressof(first_new[i].value));
>             }
>             return std::addressof(first_new[to_return].value);
>         }
>         else
>         {
>             T * result = available.back();
>             available.pop_back();
>             return result;
>         }
>     }
>     void deallocate(T * ptr, size_t num_to_free)
>     {
>         if (num_to_free == 1)
>         {
>             available.push_back(ptr);
>         }
>         else
>         {
>             ::operator delete(ptr);
>         }
>     }
>
>     // boilerplate that shouldn't be needed, except
>     // libstdc++ doesn't use allocator_traits yet
>     template<typename U>
>     struct rebind
>     {
>         typedef plalloc<U> other;
>     };
>     typedef T * pointer;
>     typedef const T * const_pointer;
>     typedef T & reference;
>     typedef const T & const_reference;
>     template<typename U, typename... Args>
>     void construct(U * object, Args &&... args)
>     {
>         new (object) U(std::forward<Args>(args)...);
>     }
>     template<typename U, typename... Args>
>     void construct(const U * object, Args &&... args) = delete;
>     template<typename U>
>     void destroy(U * object)
>     {
>         object->~U();
>     }
>
> private:
>     union value_holder
>     {
>         value_holder() {}
>         ~value_holder() {}
>         T value;
>     };
>
>     std::vector<std::unique_ptr<value_holder[]>> memory;
>     std::vector<T *> available;
> };
>

> And here is a sequence of events with which you can get it:
>
> boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
> plalloc<int>> a = { { 1, 2 } };
> boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
> plalloc<int>> b = { { 3, 4 } };
> boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
> plalloc<int>> c = { { 5, 6 } };
> a = std::move(b);
> a = c;

New description:

 Hi,

 here is my problem: I have a stateful allocator that has a bunch of stuff
 inside of it. It can be move-assigned. The problem is that
 boost::unordered_map does this when you have
 propagate_on_container_move_assign typedeffed to true_type:

 {{{
 my_alloc a;
 my_alloc b;
 a = std::move(b);
 ASSERT(a == b);
 }}}

 That assert can obviously never be true if my_alloc is stateful, but this
 sequence of events currently happens in boost::unordered_map.

 Here is an allocator that shows the problem:

 {{{
 #pragma once

 #include <memory>
 #include <vector>

 template<typename T>
 struct plalloc
 {
     typedef T value_type;

     plalloc() = default;
     template<typename U>
     plalloc(const plalloc<U> &) {}
     plalloc(const plalloc &) {}
     plalloc & operator=(const plalloc &) { return *this; }
     plalloc(plalloc &&) = default;
     plalloc & operator=(plalloc &&) = default;

     typedef std::true_type propagate_on_container_copy_assignment;
     typedef std::true_type propagate_on_container_move_assignment;
     typedef std::true_type propagate_on_container_swap;

     bool operator==(const plalloc & other) const
     {
         return this == &other;
     }
     bool operator!=(const plalloc & other) const
     {
         return !(*this == other);
     }

     T * allocate(size_t num_to_allocate)
     {
         if (num_to_allocate != 1)
         {
             return static_cast<T *>(::operator new(sizeof(T) *
 num_to_allocate));
         }
         else if (available.empty())
         {
             // first allocate 8, then double whenever
             // we run out of memory
             size_t to_allocate = 8 << memory.size();
             available.reserve(to_allocate);
             std::unique_ptr<value_holder[]> allocated(new
 value_holder[to_allocate]);
             value_holder * first_new = allocated.get();
             memory.emplace_back(std::move(allocated));
             size_t to_return = to_allocate - 1;
             for (size_t i = 0; i < to_return; ++i)
             {
                 available.push_back(std::addressof(first_new[i].value));
             }
             return std::addressof(first_new[to_return].value);
         }
         else
         {
             T * result = available.back();
             available.pop_back();
             return result;
         }
     }
     void deallocate(T * ptr, size_t num_to_free)
     {
         if (num_to_free == 1)
         {
             available.push_back(ptr);
         }
         else
         {
             ::operator delete(ptr);
         }
     }

     // boilerplate that shouldn't be needed, except
     // libstdc++ doesn't use allocator_traits yet
     template<typename U>
     struct rebind
     {
         typedef plalloc<U> other;
     };
     typedef T * pointer;
     typedef const T * const_pointer;
     typedef T & reference;
     typedef const T & const_reference;
     template<typename U, typename... Args>
     void construct(U * object, Args &&... args)
     {
         new (object) U(std::forward<Args>(args)...);
     }
     template<typename U, typename... Args>
     void construct(const U * object, Args &&... args) = delete;
     template<typename U>
     void destroy(U * object)
     {
         object->~U();
     }

 private:
     union value_holder
     {
         value_holder() {}
         ~value_holder() {}
         T value;
     };

     std::vector<std::unique_ptr<value_holder[]>> memory;
     std::vector<T *> available;
 };
 }}}

 And here is a sequence of events with which you can get it:

 {{{
 boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
 plalloc<int>> a = { { 1, 2 } };
 boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
 plalloc<int>> b = { { 3, 4 } };
 boost::unordered_map<int, int, std::hash<int>, std::equal_to<int>,
 plalloc<int>> c = { { 5, 6 } };
 a = std::move(b);
 a = c;
 }}}

--
Comment:
 I've removed the assertion in develop.

 https://github.com/boostorg/unordered/commit/31211a607f1c294f973eed10e54e461a8ef920ba
-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/10777#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.