boost/lockfree/detail/freelist.hpp

   1 //  lock-free freelist
   2 //
   3 //  Copyright (C) 2008, 2009 Tim Blechmann
   4 //
   5 //  Distributed under the Boost Software License, Version 1.0. (See
   6 //  accompanying file LICENSE_1_0.txt or copy at
   7 //  http://www.boost.org/LICENSE_1_0.txt)
   8
   9 //  Disclaimer: Not a Boost library.
  10
  11 #ifndef BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
  12 #define BOOST_LOCKFREE_FREELIST_HPP_INCLUDED
  13
  14 #include <boost/version.hpp>
  15 #if (BOOST_VERSION < 104200)  && !defined(memory_order_consume)
  16 #define memory_order_consume (boost::memory_order)8
  17 #endif
  18
  19 #include <boost/lockfree/detail/tagged_ptr.hpp>
  20
  21 #include <boost/atomic.hpp>
  22 #include <boost/noncopyable.hpp>
  23
  24 #include <boost/mpl/map.hpp>
  25 #include <boost/mpl/apply.hpp>
  26 #include <boost/mpl/at.hpp>
  27 #include <boost/type_traits/is_pod.hpp>
  28
  29 #include <algorithm>            /* for std::min */
  30
  31 namespace boost
  32 {
  33 namespace lockfree
  34 {
  35 namespace detail
  36 {
  37
  38 template <typename T, typename Alloc = std::allocator<T> >
  39 class dummy_freelist:
  40     private boost::noncopyable,
  41     private Alloc
  42 {
  43 public:
  44     T * allocate (void)
  45     {
  46         return Alloc::allocate(1);
  47     }
  48
  49     void deallocate (T * n)
  50     {
  51         Alloc::deallocate(n, 1);
  52     }
  53 };
  54
  55 } /* namespace detail */
  56
  57 template <typename T, typename Alloc = std::allocator<T> >
  58 class caching_freelist:
  59     private detail::dummy_freelist<T, Alloc>
  60 {
  61     struct freelist_node
  62     {
  63         lockfree::tagged_ptr<freelist_node> next;
  64     };
  65
  66     typedef lockfree::tagged_ptr<freelist_node> tagged_ptr;
  67
  68 public:
  69     caching_freelist(void):
  70         pool_(tagged_ptr(NULL, 0))
  71     {}
  72
  73     explicit caching_freelist(std::size_t initial_nodes):
  74         pool_(tagged_ptr(NULL, 0))
  75     {
  76         for (std::size_t i = 0; i != initial_nodes; ++i)
  77         {
  78             T * node = detail::dummy_freelist<T, Alloc>::allocate();
  79             deallocate(node);
  80         }
  81     }
  82
  83     ~caching_freelist(void)
  84     {
  85         free_memory_pool();
  86     }
  87
  88     T * allocate (void)
  89     {
  90         for(;;)
  91         {
  92             tagged_ptr old_pool = pool_.load(memory_order_consume);
  93
  94             if (!old_pool.get_ptr())
  95                 return detail::dummy_freelist<T, Alloc>::allocate();
  96
  97             freelist_node * new_pool_ptr = old_pool->next.get_ptr();
  98             tagged_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
  99
 100             if (pool_.compare_exchange_strong(old_pool, new_pool)) {
 101                 void * ptr = old_pool.get_ptr();
 102                 return reinterpret_cast<T*>(ptr);
 103             }
 104         }
 105     }
 106
 107     void deallocate (T * n)
 108     {
 109         void * node = n;
 110         for(;;)
 111         {
 112             tagged_ptr old_pool = pool_.load(memory_order_consume);
 113
 114             freelist_node * new_pool_ptr = reinterpret_cast<freelist_node*>(node);
 115             tagged_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
 116
 117             new_pool->next.set_ptr(old_pool.get_ptr());
 118
 119             if (pool_.compare_exchange_strong(old_pool, new_pool))
 120                 return;
 121         }
 122     }
 123
 124 private:
 125     void free_memory_pool(void)
 126     {
 127         tagged_ptr current (pool_);
 128
 129         while (current)
 130         {
 131             void * n = current.get_ptr();
 132             current = current->next;
 133             detail::dummy_freelist<T, Alloc>::deallocate(reinterpret_cast<T*>(n));
 134         }
 135     }
 136
 137     atomic<tagged_ptr> pool_;
 138 };
 139
 140 template <typename T, typename Alloc = std::allocator<T> >
 141 class static_freelist:
 142     private Alloc
 143 {
 144     struct freelist_node
 145     {
 146         lockfree::tagged_ptr<freelist_node> next;
 147     };
 148
 149     typedef lockfree::tagged_ptr<freelist_node> tagged_ptr;
 150
 151 public:
 152     explicit static_freelist(std::size_t max_nodes):
 153         pool_(tagged_ptr(NULL, 0)), total_nodes(max_nodes)
 154     {
 155         chunks = Alloc::allocate(max_nodes);
 156         for (std::size_t i = 0; i != max_nodes; ++i)
 157         {
 158             T * node = chunks + i;
 159             deallocate(node);
 160         }
 161     }
 162
 163     ~static_freelist(void)
 164     {
 165         Alloc::deallocate(chunks, total_nodes);
 166     }
 167
 168     T * allocate (void)
 169     {
 170         for(;;)
 171         {
 172             tagged_ptr old_pool = pool_.load(memory_order_consume);
 173
 174             if (!old_pool.get_ptr())
 175                 return NULL; /* allocation fails */
 176
 177             freelist_node * new_pool_ptr = old_pool->next.get_ptr();
 178             tagged_ptr new_pool (new_pool_ptr, old_pool.get_tag() + 1);
 179
 180             if (pool_.compare_exchange_strong(old_pool, new_pool)) {
 181                 void * ptr = old_pool.get_ptr();
 182                 return reinterpret_cast<T*>(ptr);
 183             }
 184         }
 185     }
 186
 187     void deallocate (T * n)
 188     {
 189         void * node = n;
 190         for(;;)
 191         {
 192             tagged_ptr old_pool = pool_.load(memory_order_consume);
 193
 194             freelist_node * new_pool_ptr = reinterpret_cast<freelist_node*>(node);
 195             tagged_ptr new_pool (new_pool_ptr, old_pool.get_tag());
 196
 197             new_pool->next.set_ptr(old_pool.get_ptr());
 198
 199             if (pool_.compare_exchange_strong(old_pool, new_pool))
 200                 return;
 201         }
 202     }
 203
 204 private:
 205     atomic<tagged_ptr> pool_;
 206
 207     const std::size_t total_nodes;
 208     T* chunks;
 209 };
 210
 211
 212 struct caching_freelist_t {};
 213 struct static_freelist_t {};
 214
 215 namespace detail
 216 {
 217
 218 #if 0
 219 template <typename T, typename Alloc, typename tag>
 220 struct select_freelist
 221 {
 222 private:
 223     typedef typename Alloc::template rebind<T>::other Allocator;
 224
 225     typedef typename boost::lockfree::caching_freelist<T, Allocator> cfl;
 226     typedef typename boost::lockfree::static_freelist<T, Allocator> sfl;
 227
 228     typedef typename boost::mpl::map<
 229         boost::mpl::pair < caching_freelist_t, cfl/* typename boost::lockfree::caching_freelist<T, Alloc> */ >,
 230         boost::mpl::pair < static_freelist_t,  sfl/* typename boost::lockfree::static_freelist<T, Alloc> */ >,
 231         int
 232         > freelists;
 233 public:
 234     typedef typename boost::mpl::at<freelists, tag>::type type;
 235 };
 236 #endif
 237
 238 } /* namespace detail */
 239 } /* namespace lockfree */
 240 } /* namespace boost */
 241
 242 #endif /* BOOST_LOCKFREE_FREELIST_HPP_INCLUDED */