1 // lock-free queue from
2 // Michael, M. M. and Scott, M. L.,
3 // "simple, fast and practical non-blocking and blocking concurrent queue algorithms"
5 // Copyright (C) 2008-2013 Tim Blechmann
7 // Distributed under the Boost Software License, Version 1.0. (See
8 // accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
11 #ifndef BOOST_LOCKFREE_FIFO_HPP_INCLUDED
12 #define BOOST_LOCKFREE_FIFO_HPP_INCLUDED
14 #include <boost/assert.hpp>
15 #include <boost/static_assert.hpp>
16 #include <boost/type_traits/has_trivial_assign.hpp>
17 #include <boost/type_traits/has_trivial_destructor.hpp>
18 #include <boost/config.hpp> // for BOOST_LIKELY & BOOST_ALIGNMENT
20 #include <boost/lockfree/detail/atomic.hpp>
21 #include <boost/lockfree/detail/copy_payload.hpp>
22 #include <boost/lockfree/detail/freelist.hpp>
23 #include <boost/lockfree/detail/parameter.hpp>
24 #include <boost/lockfree/detail/tagged_ptr.hpp>
26 #include <boost/lockfree/lockfree_forward.hpp>
28 #ifdef BOOST_HAS_PRAGMA_ONCE
35 #pragma warning(disable: 4324) // structure was padded due to __declspec(align())
43 typedef parameter::parameters<boost::parameter::optional<tag::allocator>,
44 boost::parameter::optional<tag::capacity>
47 } /* namespace detail */
50 /** The queue class provides a multi-writer/multi-reader queue, pushing and popping is lock-free,
51 * construction/destruction has to be synchronized. It uses a freelist for memory management,
52 * freed nodes are pushed to the freelist and not returned to the OS before the queue is destroyed.
55 * - \ref boost::lockfree::fixed_sized, defaults to \c boost::lockfree::fixed_sized<false> \n
56 * Can be used to completely disable dynamic memory allocations during push in order to ensure lockfree behavior. \n
57 * If the data structure is configured as fixed-sized, the internal nodes are stored inside an array and they are addressed
58 * by array indexing. This limits the possible size of the queue to the number of elements that can be addressed by the index
59 * type (usually 2**16-2), but on platforms that lack double-width compare-and-exchange instructions, this is the best way
60 * to achieve lock-freedom.
62 * - \ref boost::lockfree::capacity, optional \n
63 * If this template argument is passed to the options, the size of the queue is set at compile-time.\n
64 * It this option implies \c fixed_sized<true>
66 * - \ref boost::lockfree::allocator, defaults to \c boost::lockfree::allocator<std::allocator<void>> \n
67 * Specifies the allocator that is used for the internal freelist
70 * - T must have a copy constructor
71 * - T must have a trivial assignment operator
72 * - T must have a trivial destructor
75 #ifdef BOOST_NO_CXX11_VARIADIC_TEMPLATES
76 template <typename T, class A0, class A1, class A2>
78 template <typename T, typename ...Options>
83 #ifndef BOOST_DOXYGEN_INVOKED
85 #ifdef BOOST_HAS_TRIVIAL_DESTRUCTOR
86 BOOST_STATIC_ASSERT((boost::has_trivial_destructor<T>::value));
89 #ifdef BOOST_HAS_TRIVIAL_ASSIGN
90 BOOST_STATIC_ASSERT((boost::has_trivial_assign<T>::value));
93 #ifdef BOOST_NO_CXX11_VARIADIC_TEMPLATES
94 typedef typename detail::queue_signature::bind<A0, A1, A2>::type bound_args;
96 typedef typename detail::queue_signature::bind<Options...>::type bound_args;
99 static const bool has_capacity = detail::extract_capacity<bound_args>::has_capacity;
100 static const size_t capacity = detail::extract_capacity<bound_args>::capacity + 1; // the queue uses one dummy node
101 static const bool fixed_sized = detail::extract_fixed_sized<bound_args>::value;
102 static const bool node_based = !(has_capacity || fixed_sized);
103 static const bool compile_time_sized = has_capacity;
105 struct BOOST_ALIGNMENT(BOOST_LOCKFREE_CACHELINE_BYTES) node
107 typedef typename detail::select_tagged_handle<node, node_based>::tagged_handle_type tagged_node_handle;
108 typedef typename detail::select_tagged_handle<node, node_based>::handle_type handle_type;
110 node(T const & v, handle_type null_handle):
111 data(v)//, next(tagged_node_handle(0, 0))
113 /* increment tag to avoid ABA problem */
114 tagged_node_handle old_next = next.load(memory_order_relaxed);
115 tagged_node_handle new_next (null_handle, old_next.get_next_tag());
116 next.store(new_next, memory_order_release);
119 node (handle_type null_handle):
120 next(tagged_node_handle(null_handle, 0))
126 atomic<tagged_node_handle> next;
130 typedef typename detail::extract_allocator<bound_args, node>::type node_allocator;
131 typedef typename detail::select_freelist<node, node_allocator, compile_time_sized, fixed_sized, capacity>::type pool_t;
132 typedef typename pool_t::tagged_node_handle tagged_node_handle;
133 typedef typename detail::select_tagged_handle<node, node_based>::handle_type handle_type;
135 void initialize(void)
137 node * n = pool.template construct<true, false>(pool.null_handle());
138 tagged_node_handle dummy_node(pool.get_handle(n), 0);
139 head_.store(dummy_node, memory_order_relaxed);
140 tail_.store(dummy_node, memory_order_release);
143 struct implementation_defined
145 typedef node_allocator allocator;
146 typedef std::size_t size_type;
151 BOOST_DELETED_FUNCTION(queue(queue const&))
152 BOOST_DELETED_FUNCTION(queue& operator= (queue const&))
155 typedef T value_type;
156 typedef typename implementation_defined::allocator allocator;
157 typedef typename implementation_defined::size_type size_type;
160 * \return true, if implementation is lock-free.
162 * \warning It only checks, if the queue head and tail nodes and the freelist can be modified in a lock-free manner.
163 * On most platforms, the whole implementation is lock-free, if this is true. Using c++0x-style atomics, there is
164 * no possibility to provide a completely accurate implementation, because one would need to test every internal
165 * node, which is impossible if further nodes will be allocated from the operating system.
167 bool is_lock_free (void) const
169 return head_.is_lock_free() && tail_.is_lock_free() && pool.is_lock_free();
175 head_(tagged_node_handle(0, 0)),
176 tail_(tagged_node_handle(0, 0)),
177 pool(node_allocator(), capacity)
179 BOOST_ASSERT(has_capacity);
183 template <typename U>
184 explicit queue(typename node_allocator::template rebind<U>::other const & alloc):
185 head_(tagged_node_handle(0, 0)),
186 tail_(tagged_node_handle(0, 0)),
187 pool(alloc, capacity)
189 BOOST_STATIC_ASSERT(has_capacity);
193 explicit queue(allocator const & alloc):
194 head_(tagged_node_handle(0, 0)),
195 tail_(tagged_node_handle(0, 0)),
196 pool(alloc, capacity)
198 BOOST_ASSERT(has_capacity);
203 //! Construct queue, allocate n nodes for the freelist.
205 explicit queue(size_type n):
206 head_(tagged_node_handle(0, 0)),
207 tail_(tagged_node_handle(0, 0)),
208 pool(node_allocator(), n + 1)
210 BOOST_ASSERT(!has_capacity);
214 template <typename U>
215 queue(size_type n, typename node_allocator::template rebind<U>::other const & alloc):
216 head_(tagged_node_handle(0, 0)),
217 tail_(tagged_node_handle(0, 0)),
220 BOOST_STATIC_ASSERT(!has_capacity);
225 /** \copydoc boost::lockfree::stack::reserve
227 void reserve(size_type n)
229 pool.template reserve<true>(n);
232 /** \copydoc boost::lockfree::stack::reserve_unsafe
234 void reserve_unsafe(size_type n)
236 pool.template reserve<false>(n);
239 /** Destroys queue, free all nodes from freelist.
244 while(unsynchronized_pop(dummy))
247 pool.template destruct<false>(head_.load(memory_order_relaxed));
250 /** Check if the queue is empty
252 * \return true, if the queue is empty, false otherwise
253 * \note The result is only accurate, if no other thread modifies the queue. Therefore it is rarely practical to use this
254 * value in program logic.
256 bool empty(void) const
258 return pool.get_handle(head_.load()) == pool.get_handle(tail_.load());
261 /** Pushes object t to the queue.
263 * \post object will be pushed to the queue, if internal node can be allocated
264 * \returns true, if the push operation is successful.
266 * \note Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
267 * from the OS. This may not be lock-free.
269 bool push(T const & t)
271 return do_push<false>(t);
274 /** Pushes object t to the queue.
276 * \post object will be pushed to the queue, if internal node can be allocated
277 * \returns true, if the push operation is successful.
279 * \note Thread-safe and non-blocking. If internal memory pool is exhausted, operation will fail
280 * \throws if memory allocator throws
282 bool bounded_push(T const & t)
284 return do_push<true>(t);
289 #ifndef BOOST_DOXYGEN_INVOKED
290 template <bool Bounded>
291 bool do_push(T const & t)
293 node * n = pool.template construct<true, Bounded>(t, pool.null_handle());
294 handle_type node_handle = pool.get_handle(n);
300 tagged_node_handle tail = tail_.load(memory_order_acquire);
301 node * tail_node = pool.get_pointer(tail);
302 tagged_node_handle next = tail_node->next.load(memory_order_acquire);
303 node * next_ptr = pool.get_pointer(next);
305 tagged_node_handle tail2 = tail_.load(memory_order_acquire);
306 if (BOOST_LIKELY(tail == tail2)) {
308 tagged_node_handle new_tail_next(node_handle, next.get_next_tag());
309 if ( tail_node->next.compare_exchange_weak(next, new_tail_next) ) {
310 tagged_node_handle new_tail(node_handle, tail.get_next_tag());
311 tail_.compare_exchange_strong(tail, new_tail);
316 tagged_node_handle new_tail(pool.get_handle(next_ptr), tail.get_next_tag());
317 tail_.compare_exchange_strong(tail, new_tail);
326 /** Pushes object t to the queue.
328 * \post object will be pushed to the queue, if internal node can be allocated
329 * \returns true, if the push operation is successful.
331 * \note Not Thread-safe. If internal memory pool is exhausted and the memory pool is not fixed-sized, a new node will be allocated
332 * from the OS. This may not be lock-free.
333 * \throws if memory allocator throws
335 bool unsynchronized_push(T const & t)
337 node * n = pool.template construct<false, false>(t, pool.null_handle());
343 tagged_node_handle tail = tail_.load(memory_order_relaxed);
344 tagged_node_handle next = tail->next.load(memory_order_relaxed);
345 node * next_ptr = next.get_ptr();
348 tail->next.store(tagged_node_handle(n, next.get_next_tag()), memory_order_relaxed);
349 tail_.store(tagged_node_handle(n, tail.get_next_tag()), memory_order_relaxed);
353 tail_.store(tagged_node_handle(next_ptr, tail.get_next_tag()), memory_order_relaxed);
357 /** Pops object from queue.
359 * \post if pop operation is successful, object will be copied to ret.
360 * \returns true, if the pop operation is successful, false if queue was empty.
362 * \note Thread-safe and non-blocking
369 /** Pops object from queue.
371 * \pre type U must be constructible by T and copyable, or T must be convertible to U
372 * \post if pop operation is successful, object will be copied to ret.
373 * \returns true, if the pop operation is successful, false if queue was empty.
375 * \note Thread-safe and non-blocking
377 template <typename U>
381 tagged_node_handle head = head_.load(memory_order_acquire);
382 node * head_ptr = pool.get_pointer(head);
384 tagged_node_handle tail = tail_.load(memory_order_acquire);
385 tagged_node_handle next = head_ptr->next.load(memory_order_acquire);
386 node * next_ptr = pool.get_pointer(next);
388 tagged_node_handle head2 = head_.load(memory_order_acquire);
389 if (BOOST_LIKELY(head == head2)) {
390 if (pool.get_handle(head) == pool.get_handle(tail)) {
394 tagged_node_handle new_tail(pool.get_handle(next), tail.get_next_tag());
395 tail_.compare_exchange_strong(tail, new_tail);
399 /* this check is not part of the original algorithm as published by michael and scott
401 * however we reuse the tagged_ptr part for the freelist and clear the next part during node
402 * allocation. we can observe a null-pointer here.
405 detail::copy_payload(next_ptr->data, ret);
407 tagged_node_handle new_head(pool.get_handle(next), head.get_next_tag());
408 if (head_.compare_exchange_weak(head, new_head)) {
409 pool.template destruct<true>(head);
417 /** Pops object from queue.
419 * \post if pop operation is successful, object will be copied to ret.
420 * \returns true, if the pop operation is successful, false if queue was empty.
422 * \note Not thread-safe, but non-blocking
425 bool unsynchronized_pop (T & ret)
427 return unsynchronized_pop<T>(ret);
430 /** Pops object from queue.
432 * \pre type U must be constructible by T and copyable, or T must be convertible to U
433 * \post if pop operation is successful, object will be copied to ret.
434 * \returns true, if the pop operation is successful, false if queue was empty.
436 * \note Not thread-safe, but non-blocking
439 template <typename U>
440 bool unsynchronized_pop (U & ret)
443 tagged_node_handle head = head_.load(memory_order_relaxed);
444 node * head_ptr = pool.get_pointer(head);
445 tagged_node_handle tail = tail_.load(memory_order_relaxed);
446 tagged_node_handle next = head_ptr->next.load(memory_order_relaxed);
447 node * next_ptr = pool.get_pointer(next);
449 if (pool.get_handle(head) == pool.get_handle(tail)) {
453 tagged_node_handle new_tail(pool.get_handle(next), tail.get_next_tag());
454 tail_.store(new_tail);
457 /* this check is not part of the original algorithm as published by michael and scott
459 * however we reuse the tagged_ptr part for the freelist and clear the next part during node
460 * allocation. we can observe a null-pointer here.
463 detail::copy_payload(next_ptr->data, ret);
464 tagged_node_handle new_head(pool.get_handle(next), head.get_next_tag());
465 head_.store(new_head);
466 pool.template destruct<false>(head);
472 /** consumes one element via a functor
474 * pops one element from the queue and applies the functor on this object
476 * \returns true, if one element was consumed
478 * \note Thread-safe and non-blocking, if functor is thread-safe and non-blocking
480 template <typename Functor>
481 bool consume_one(Functor & f)
484 bool success = pop(element);
491 /// \copydoc boost::lockfree::queue::consume_one(Functor & rhs)
492 template <typename Functor>
493 bool consume_one(Functor const & f)
496 bool success = pop(element);
503 /** consumes all elements via a functor
505 * sequentially pops all elements from the queue and applies the functor on each object
507 * \returns number of elements that are consumed
509 * \note Thread-safe and non-blocking, if functor is thread-safe and non-blocking
511 template <typename Functor>
512 size_t consume_all(Functor & f)
514 size_t element_count = 0;
515 while (consume_one(f))
518 return element_count;
521 /// \copydoc boost::lockfree::queue::consume_all(Functor & rhs)
522 template <typename Functor>
523 size_t consume_all(Functor const & f)
525 size_t element_count = 0;
526 while (consume_one(f))
529 return element_count;
533 #ifndef BOOST_DOXYGEN_INVOKED
534 atomic<tagged_node_handle> head_;
535 static const int padding_size = BOOST_LOCKFREE_CACHELINE_BYTES - sizeof(tagged_node_handle);
536 char padding1[padding_size];
537 atomic<tagged_node_handle> tail_;
538 char padding2[padding_size];
544 } /* namespace lockfree */
545 } /* namespace boost */
547 #if defined(_MSC_VER)
551 #endif /* BOOST_LOCKFREE_FIFO_HPP_INCLUDED */