pion-net
4.0.9
|
00001 // lock-free freelist 00002 // 00003 // Copyright (C) 2008, 2009 Tim Blechmann 00004 // 00005 // Distributed under the Boost Software License, Version 1.0. (See 00006 // accompanying file LICENSE_1_0.txt or copy at 00007 // http://www.boost.org/LICENSE_1_0.txt) 00008 00009 // Disclaimer: Not a Boost library. 00010 00011 #ifndef BOOST_LOCKFREE_FREELIST_HPP_INCLUDED 00012 #define BOOST_LOCKFREE_FREELIST_HPP_INCLUDED 00013 00014 #include <boost/lockfree/detail/tagged_ptr.hpp> 00015 #include <boost/lockfree/atomic_int.hpp> 00016 #include <boost/noncopyable.hpp> 00017 00018 #include <boost/mpl/map.hpp> 00019 #include <boost/mpl/apply.hpp> 00020 #include <boost/mpl/at.hpp> 00021 #include <boost/type_traits/is_pod.hpp> 00022 00023 #include <algorithm> /* for std::min */ 00024 00025 namespace boost 00026 { 00027 namespace lockfree 00028 { 00029 namespace detail 00030 { 00031 00032 template <typename T, typename Alloc = std::allocator<T> > 00033 class dummy_freelist: 00034 private boost::noncopyable, 00035 private Alloc 00036 { 00037 public: 00038 T * allocate (void) 00039 { 00040 return Alloc::allocate(1); 00041 } 00042 00043 void deallocate (T * n) 00044 { 00045 Alloc::deallocate(n, 1); 00046 } 00047 }; 00048 00049 } /* namespace detail */ 00050 00052 template <typename T, 00053 std::size_t maximum_size = 64, 00054 typename Alloc = std::allocator<T> > 00055 class freelist: 00056 private detail::dummy_freelist<T, Alloc> 00057 { 00058 struct freelist_node 00059 { 00060 lockfree::tagged_ptr<freelist_node> next; 00061 }; 00062 00063 typedef lockfree::tagged_ptr<freelist_node> tagged_ptr; 00064 00065 public: 00066 freelist(void): 00067 pool_(NULL) 00068 {} 00069 00070 explicit freelist(std::size_t initial_nodes): 00071 pool_(NULL) 00072 { 00073 for (std::size_t i = 0; i != std::min(initial_nodes, maximum_size); ++i) 00074 { 00075 T * node = detail::dummy_freelist<T, Alloc>::allocate(); 00076 deallocate(node); 00077 } 00078 } 00079 00080 ~freelist(void) 00081 { 00082 free_memory_pool(); 00083 } 00084 00085 T * allocate (void) 00086 { 00087 for(;;) 00088 { 00089 tagged_ptr old_pool(pool_); 00090 00091 if (!old_pool) 00092 return detail::dummy_freelist<T, Alloc>::allocate(); 00093 00094 freelist_node * new_pool = old_pool->next.get_ptr(); 00095 00096 if (pool_.cas(old_pool, new_pool)) 00097 { 00098 --free_list_size; 00099 return reinterpret_cast<T*>(old_pool.get_ptr()); 00100 } 00101 } 00102 } 00103 00104 void deallocate (T * n) 00105 { 00106 if (free_list_size > maximum_size) 00107 { 00108 detail::dummy_freelist<T, Alloc>::deallocate(n); 00109 return; 00110 } 00111 00112 for(;;) 00113 { 00114 tagged_ptr old_pool (pool_); 00115 00116 freelist_node * new_pool = reinterpret_cast<freelist_node*>(n); 00117 00118 new_pool->next.set_ptr(old_pool.get_ptr()); 00119 00120 if (pool_.cas(old_pool, new_pool)) 00121 { 00122 --free_list_size; 00123 return; 00124 } 00125 } 00126 } 00127 00128 private: 00129 void free_memory_pool(void) 00130 { 00131 tagged_ptr current (pool_); 00132 00133 while (current) 00134 { 00135 freelist_node * n = current.get_ptr(); 00136 current.set(current->next); 00137 detail::dummy_freelist<T, Alloc>::deallocate(reinterpret_cast<T*>(n)); 00138 } 00139 } 00140 00141 tagged_ptr pool_; 00142 atomic_int<unsigned long> free_list_size; 00143 }; 00144 00145 template <typename T, typename Alloc = std::allocator<T> > 00146 class caching_freelist: 00147 private detail::dummy_freelist<T, Alloc> 00148 { 00149 struct freelist_node 00150 { 00151 lockfree::tagged_ptr<freelist_node> next; 00152 }; 00153 00154 typedef lockfree::tagged_ptr<freelist_node> tagged_ptr; 00155 00156 public: 00157 caching_freelist(void): 00158 pool_(NULL) 00159 {} 00160 00161 explicit caching_freelist(std::size_t initial_nodes): 00162 pool_(NULL) 00163 { 00164 for (std::size_t i = 0; i != initial_nodes; ++i) 00165 { 00166 T * node = detail::dummy_freelist<T, Alloc>::allocate(); 00167 deallocate(node); 00168 } 00169 } 00170 00171 ~caching_freelist(void) 00172 { 00173 free_memory_pool(); 00174 } 00175 00176 T * allocate (void) 00177 { 00178 for(;;) 00179 { 00180 tagged_ptr old_pool(pool_); 00181 00182 if (!old_pool) 00183 return detail::dummy_freelist<T, Alloc>::allocate(); 00184 00185 freelist_node * new_pool = old_pool->next.get_ptr(); 00186 00187 if (pool_.cas(old_pool, new_pool)) 00188 return reinterpret_cast<T*>(old_pool.get_ptr()); 00189 } 00190 } 00191 00192 void deallocate (T * n) 00193 { 00194 for(;;) 00195 { 00196 tagged_ptr old_pool (pool_); 00197 00198 freelist_node * new_pool = reinterpret_cast<freelist_node*>(n); 00199 00200 new_pool->next.set_ptr(old_pool.get_ptr()); 00201 00202 if (pool_.cas(old_pool,new_pool)) 00203 return; 00204 } 00205 } 00206 00207 private: 00208 void free_memory_pool(void) 00209 { 00210 tagged_ptr current (pool_); 00211 00212 while (current) 00213 { 00214 freelist_node * n = current.get_ptr(); 00215 current.set(current->next); 00216 detail::dummy_freelist<T, Alloc>::deallocate(reinterpret_cast<T*>(n)); 00217 } 00218 } 00219 00220 tagged_ptr pool_; 00221 }; 00222 00223 template <typename T, typename Alloc = std::allocator<T> > 00224 class static_freelist: 00225 private Alloc 00226 { 00227 struct freelist_node 00228 { 00229 lockfree::tagged_ptr<freelist_node> next; 00230 }; 00231 00232 typedef lockfree::tagged_ptr<freelist_node> tagged_ptr; 00233 00234 public: 00235 explicit static_freelist(std::size_t max_nodes): 00236 pool_(NULL), total_nodes(max_nodes) 00237 { 00238 chunks = Alloc::allocate(max_nodes); 00239 for (std::size_t i = 0; i != max_nodes; ++i) 00240 { 00241 T * node = chunks + i; 00242 deallocate(node); 00243 } 00244 } 00245 00246 ~static_freelist(void) 00247 { 00248 Alloc::deallocate(chunks, total_nodes); 00249 } 00250 00251 T * allocate (void) 00252 { 00253 for(;;) 00254 { 00255 tagged_ptr old_pool(pool_); 00256 00257 if (!old_pool) 00258 return 0; /* allocation fails */ 00259 00260 freelist_node * new_pool = old_pool->next.get_ptr(); 00261 00262 if (pool_.cas(old_pool, new_pool)) 00263 return reinterpret_cast<T*>(old_pool.get_ptr()); 00264 } 00265 } 00266 00267 void deallocate (T * n) 00268 { 00269 for(;;) 00270 { 00271 tagged_ptr old_pool (pool_); 00272 00273 freelist_node * new_pool = reinterpret_cast<freelist_node*>(n); 00274 00275 new_pool->next.set_ptr(old_pool.get_ptr()); 00276 00277 if (pool_.cas(old_pool,new_pool)) 00278 return; 00279 } 00280 } 00281 00282 private: 00283 tagged_ptr pool_; 00284 00285 const std::size_t total_nodes; 00286 T* chunks; 00287 }; 00288 00289 00290 struct caching_freelist_t {}; 00291 struct static_freelist_t {}; 00292 00293 namespace detail 00294 { 00295 00296 #if 0 00297 template <typename T, typename Alloc, typename tag> 00298 struct select_freelist 00299 { 00300 private: 00301 typedef typename Alloc::template rebind<T>::other Allocator; 00302 00303 typedef typename boost::lockfree::caching_freelist<T, Allocator> cfl; 00304 typedef typename boost::lockfree::static_freelist<T, Allocator> sfl; 00305 00306 typedef typename boost::mpl::map< 00307 boost::mpl::pair < caching_freelist_t, cfl/* typename boost::lockfree::caching_freelist<T, Alloc> */ >, 00308 boost::mpl::pair < static_freelist_t, sfl/* typename boost::lockfree::static_freelist<T, Alloc> */ >, 00309 int 00310 > freelists; 00311 public: 00312 typedef typename boost::mpl::at<freelists, tag>::type type; 00313 }; 00314 #endif 00315 00316 } /* namespace detail */ 00317 } /* namespace lockfree */ 00318 } /* namespace boost */ 00319 00320 #endif /* BOOST_LOCKFREE_FREELIST_HPP_INCLUDED */