2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_INTRUSIVE_MSQUEUE_H
32 #define CDSLIB_INTRUSIVE_MSQUEUE_H
34 #include <type_traits>
35 #include <cds/intrusive/details/single_link_struct.h>
36 #include <cds/algo/atomic.h>
38 namespace cds { namespace intrusive {
40 /// MSQueue related definitions
41 /** @ingroup cds_intrusive_helper
48 - GC - garbage collector used
49 - Tag - a \ref cds_intrusive_hook_tag "tag"
51 template <class GC, typename Tag = opt::none >
52 using node = cds::intrusive::single_link::node< GC, Tag >;
57 - opt::gc - garbage collector used.
58 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
60 template < typename... Options >
61 using base_hook = cds::intrusive::single_link::base_hook< Options...>;
65 \p MemberOffset specifies offset in bytes of \ref node member into your structure.
66 Use \p offsetof macro to define \p MemberOffset
69 - opt::gc - garbage collector used.
70 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
72 template < size_t MemberOffset, typename... Options >
73 using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
77 \p NodeTraits defines type traits for node.
78 See \ref node_traits for \p NodeTraits interface description
81 - opt::gc - garbage collector used.
82 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
84 template <typename NodeTraits, typename... Options >
85 using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >;
87 /// Queue internal statistics. May be used for debugging or profiling
89 Template argument \p Counter defines type of counter.
90 Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
91 strict event counting.
92 You may use stronger type of counter like as \p cds::atomicity::item_counter,
93 or even integral type, for example, \p int.
95 template <typename Counter = cds::atomicity::event_counter >
98 typedef Counter counter_type; ///< Counter type
100 counter_type m_EnqueueCount ; ///< Enqueue call count
101 counter_type m_DequeueCount ; ///< Dequeue call count
102 counter_type m_EnqueueRace ; ///< Count of enqueue race conditions encountered
103 counter_type m_DequeueRace ; ///< Count of dequeue race conditions encountered
104 counter_type m_AdvanceTailError ; ///< Count of "advance tail failed" events
105 counter_type m_BadTail ; ///< Count of events "Tail is not pointed to the last item in the queue"
106 counter_type m_EmptyDequeue ; ///< Count of dequeue from empty queue
108 /// Register enqueue call
109 void onEnqueue() { ++m_EnqueueCount; }
110 /// Register dequeue call
111 void onDequeue() { ++m_DequeueCount; }
112 /// Register enqueue race event
113 void onEnqueueRace() { ++m_EnqueueRace; }
114 /// Register dequeue race event
115 void onDequeueRace() { ++m_DequeueRace; }
116 /// Register "advance tail failed" event
117 void onAdvanceTailFailed() { ++m_AdvanceTailError; }
118 /// Register event "Tail is not pointed to last item in the queue"
119 void onBadTail() { ++m_BadTail; }
120 /// Register dequeuing from empty queue
121 void onEmptyDequeue() { ++m_EmptyDequeue; }
126 m_EnqueueCount.reset();
127 m_DequeueCount.reset();
128 m_EnqueueRace.reset();
129 m_DequeueRace.reset();
130 m_AdvanceTailError.reset();
132 m_EmptyDequeue.reset();
135 stat& operator +=( stat const& s )
137 m_EnqueueCount += s.m_EnqueueCount.get();
138 m_DequeueCount += s.m_DequeueCount.get();
139 m_EnqueueRace += s.m_EnqueueRace.get();
140 m_DequeueRace += s.m_DequeueRace.get();
141 m_AdvanceTailError += s.m_AdvanceTailError.get();
142 m_BadTail += s.m_BadTail.get();
143 m_EmptyDequeue += s.m_EmptyDequeue.get();
150 /// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p msqueue::stat
154 void onEnqueue() const {}
155 void onDequeue() const {}
156 void onEnqueueRace() const {}
157 void onDequeueRace() const {}
158 void onAdvanceTailFailed() const {}
159 void onBadTail() const {}
160 void onEmptyDequeue() const {}
163 empty_stat& operator +=( empty_stat const& )
170 /// MSQueue default traits
173 /// Back-off strategy
174 typedef cds::backoff::empty back_off;
176 /// Hook, possible types are \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook
177 typedef msqueue::base_hook<> hook;
179 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
180 typedef opt::v::empty_disposer disposer;
182 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
183 typedef atomicity::empty_item_counter item_counter;
185 /// Internal statistics (by default, disabled)
187 Possible option value are: \p msqueue::stat, \p msqueue::empty_stat (the default),
188 user-provided class that supports \p %msqueue::stat interface.
190 typedef msqueue::empty_stat stat;
192 /// C++ memory ordering model
194 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
195 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
197 typedef opt::v::relaxed_ordering memory_model;
199 /// Link checking, see \p cds::opt::link_checker
200 static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
202 /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding
203 enum { padding = opt::cache_line_padding };
206 /// Metafunction converting option list to \p msqueue::traits
208 Supported \p Options are:
210 - \p opt::hook - hook used. Possible hooks are: \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook.
211 If the option is not specified, \p %msqueue::base_hook<> is used.
212 - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
213 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
215 - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
216 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
217 To enable item counting use \p cds::atomicity::item_counter
218 - \p opt::stat - the type to gather internal statistics.
219 Possible statistics types are: \p msqueue::stat, \p msqueue::empty_stat, user-provided class that supports \p %msqueue::stat interface.
220 Default is \p %msqueue::empty_stat (internal statistics disabled).
221 - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
222 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
223 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
225 Example: declare \p %MSQueue with item counting and internal statistics
227 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
228 typename cds::intrusive::msqueue::make_traits<
229 cds::intrusive::opt:hook< cds::intrusive::msqueue::base_hook< cds::opt::gc<cds:gc::HP> >>,
230 cds::opt::item_counte< cds::atomicity::item_counter >,
231 cds::opt::stat< cds::intrusive::msqueue::stat<> >
236 template <typename... Options>
238 # ifdef CDS_DOXYGEN_INVOKED
239 typedef implementation_defined type; ///< Metafunction result
241 typedef typename cds::opt::make_options<
242 typename cds::opt::find_type_traits< traits, Options... >::type
247 } // namespace msqueue
249 /// Michael & Scott's intrusive lock-free queue
250 /** @ingroup cds_intrusive_queue
251 Implementation of well-known Michael & Scott's queue algorithm:
252 - [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
255 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
256 - \p T - type of value to be stored in the queue. A value of type \p T must be derived from \p msqueue::node for \p msqueue::base_hook,
257 or it should have a member of type \p %msqueue::node for \p msqueue::member_hook,
258 or it should be convertible to \p %msqueue::node for \p msqueue::traits_hook.
259 - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
260 metafunction to make your traits or just derive your traits from \p %msqueue::traits:
262 struct myTraits: public cds::intrusive::msqueue::traits {
263 typedef cds::intrusive::msqueue::stat<> stat;
264 typedef cds::atomicity::item_counter item_counter;
266 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo, myTraits > myQueue;
268 // Equivalent make_traits example:
269 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
270 typename cds::intrusive::msqueue::make_traits<
271 cds::opt::stat< cds::intrusive::msqueue::stat<> >,
272 cds::opt::item_counter< cds::atomicity::item_counter >
277 \par About item disposing
278 The Michael & Scott's queue algo has a key feature: even if the queue is empty it contains one item that is "dummy" one from
279 the standpoint of the algo. See \p dequeue() function for explanation.
283 #include <cds/intrusive/msqueue.h>
284 #include <cds/gc/hp.h>
286 namespace ci = cds::inrtusive;
287 typedef cds::gc::HP hp_gc;
289 // MSQueue with Hazard Pointer garbage collector, base hook + item disposer:
290 struct Foo: public ci::msqueue::node< hp_gc >
296 // Disposer for Foo struct just deletes the object passed in
298 void operator()( Foo * p )
304 // Declare traits for the queue
305 struct myTraits: public ci::msqueue::traits {
307 ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
309 ,ci::opt::disposer< fooDisposer >
312 // At least, declare the queue type
313 typedef ci::MSQueue< hp_gc, Foo, myTraits > fooQueue;
316 // MSQueue with Hazard Pointer garbage collector,
317 // member hook + item disposer + item counter,
318 // without padding of internal queue data
319 // Use msqueue::make_traits
324 ci::msqueue::node< hp_gc > hMember;
327 typedef ci::MSQueue< hp_gc,
329 typename ci::msqueue::make_traits<
331 ci::msqueue::member_hook<
332 offsetof(Bar, hMember)
336 ,ci::opt::disposer< fooDisposer >
337 ,cds::opt::item_counter< cds::atomicity::item_counter >
338 ,cds::opt::padding< cds::opt::no_special_padding >
343 template <typename GC, typename T, typename Traits = msqueue::traits>
347 typedef GC gc; ///< Garbage collector
348 typedef T value_type; ///< type of value to be stored in the queue
349 typedef Traits traits; ///< Queue traits
351 typedef typename traits::hook hook; ///< hook type
352 typedef typename hook::node_type node_type; ///< node type
353 typedef typename traits::disposer disposer; ///< disposer used
354 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
355 typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
357 typedef typename traits::back_off back_off; ///< back-off strategy
358 typedef typename traits::item_counter item_counter; ///< Item counter class
359 typedef typename traits::stat stat; ///< Internal statistics
360 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
362 /// Rebind template arguments
363 template <typename GC2, typename T2, typename Traits2>
365 typedef MSQueue< GC2, T2, Traits2 > other; ///< Rebinding result
368 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 2; ///< Count of hazard pointer required for the algorithm
373 // GC and node_type::gc must be the same
374 static_assert((std::is_same<gc, typename node_type::gc>::value), "GC and node_type::gc must be the same");
376 typedef typename node_type::atomic_node_ptr atomic_node_ptr;
378 atomic_node_ptr m_pHead; ///< Queue's head pointer
379 typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad1_;
380 atomic_node_ptr m_pTail; ///< Queue's tail pointer
381 typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad2_;
382 node_type m_Dummy; ///< dummy node
383 typename opt::details::apply_padding< node_type, traits::padding >::padding_type pad3_;
384 item_counter m_ItemCounter; ///< Item counter
385 stat m_Stat; ///< Internal statistics
389 struct dequeue_result {
390 typename gc::template GuardArray<2> guards;
396 bool do_dequeue( dequeue_result& res )
403 h = res.guards.protect( 0, m_pHead, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
404 pNext = res.guards.protect( 1, h->m_pNext, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
405 if ( m_pHead.load(memory_model::memory_order_acquire) != h )
408 if ( pNext == nullptr ) {
409 m_Stat.onEmptyDequeue();
410 return false; // empty queue
413 node_type * t = m_pTail.load(memory_model::memory_order_acquire);
415 // It is needed to help enqueue
416 m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
421 if ( m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
424 m_Stat.onDequeueRace();
436 static void clear_links( node_type * pNode )
438 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
441 void dispose_result( dequeue_result& res )
443 dispose_node( res.pHead );
446 void dispose_node( node_type * p )
448 // Note about the dummy node:
449 // We cannot clear m_Dummy here since it leads to ABA.
450 // On the other hand, we cannot use deferred clear_links( &m_Dummy ) call via
451 // HP retiring cycle since m_Dummy is member of MSQueue and may be destroyed
452 // before HP retiring cycle invocation.
453 // So, we will never clear m_Dummy
455 struct disposer_thunk {
456 void operator()( value_type * p ) const
458 assert( p != nullptr );
459 MSQueue::clear_links( node_traits::to_node_ptr( p ) );
465 gc::template retire<disposer_thunk>( node_traits::to_value_ptr( p ) );
470 /// Initializes empty queue
472 : m_pHead( &m_Dummy )
473 , m_pTail( &m_Dummy )
476 /// Destructor clears the queue
478 Since the Michael & Scott queue contains at least one item even
479 if the queue is empty, the destructor may call item disposer.
485 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
487 assert( pHead != nullptr );
488 assert( pHead == m_pTail.load(memory_model::memory_order_relaxed) );
490 m_pHead.store( nullptr, memory_model::memory_order_relaxed );
491 m_pTail.store( nullptr, memory_model::memory_order_relaxed );
493 dispose_node( pHead );
496 /// Enqueues \p val value into the queue.
497 /** @anchor cds_intrusive_MSQueue_enqueue
498 The function always returns \p true.
500 bool enqueue( value_type& val )
502 node_type * pNew = node_traits::to_node_ptr( val );
503 link_checker::is_empty( pNew );
505 typename gc::Guard guard;
510 t = guard.protect( m_pTail, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
512 node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire);
513 if ( pNext != nullptr ) {
514 // Tail is misplaced, advance it
515 m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
520 node_type * tmp = nullptr;
521 if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
524 m_Stat.onEnqueueRace();
530 if ( !m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
531 m_Stat.onAdvanceTailFailed();
535 /// Dequeues a value from the queue
536 /** @anchor cds_intrusive_MSQueue_dequeue
537 If the queue is empty the function returns \p nullptr.
540 The queue algorithm has following feature: when \p %dequeue() is called,
541 the item returning is still queue's top, and previous top is disposed:
544 before dequeuing Dequeue after dequeuing
545 +------------------+ +------------------+
546 Top ->| Item 1 | -> Dispose Item 1 | Item 2 | <- Top
547 +------------------+ +------------------+
548 | Item 2 | -> Return Item 2 | ... |
553 \p %dequeue() function returns Item 2, that becomes new top of queue, and calls
554 the disposer for Item 1, that was queue's top on function entry.
555 Thus, you cannot manually delete item returned because it is still included in
556 item sequence and it has valuable link field that must not be zeroed.
557 The item should be deleted only in garbage collector retire cycle using the disposer.
559 value_type * dequeue()
563 if ( do_dequeue( res )) {
564 dispose_result( res );
566 return node_traits::to_value_ptr( *res.pNext );
571 /// Synonym for \ref cds_intrusive_MSQueue_enqueue "enqueue()" function
572 bool push( value_type& val )
574 return enqueue( val );
577 /// Synonym for \ref cds_intrusive_MSQueue_dequeue "dequeue()" function
583 /// Checks if the queue is empty
586 typename gc::Guard guard;
587 node_type * p = guard.protect( m_pHead, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
588 return p->m_pNext.load( memory_model::memory_order_relaxed ) == nullptr;
593 The function repeatedly calls \p dequeue() until it returns \p nullptr.
594 The disposer defined in template \p Traits is called for each item
595 that can be safely disposed.
602 /// Returns queue's item count
604 The value returned depends on \p msqueue::traits::item_counter. For \p atomicity::empty_item_counter,
605 this function always returns 0.
607 @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
608 is empty. To check queue emptyness use \p empty() method.
612 return m_ItemCounter.value();
615 /// Returns reference to internal statistics
616 stat const& statistics() const
622 }} // namespace cds::intrusive
624 #endif // #ifndef CDSLIB_INTRUSIVE_MSQUEUE_H