3 #ifndef CDSLIB_INTRUSIVE_MSQUEUE_H
4 #define CDSLIB_INTRUSIVE_MSQUEUE_H
7 #include <cds/intrusive/details/single_link_struct.h>
8 #include <cds/algo/atomic.h>
10 namespace cds { namespace intrusive {
12 /// MSQueue related definitions
13 /** @ingroup cds_intrusive_helper
20 - GC - garbage collector used
21 - Tag - a \ref cds_intrusive_hook_tag "tag"
23 template <class GC, typename Tag = opt::none >
24 using node = cds::intrusive::single_link::node< GC, Tag >;
29 - opt::gc - garbage collector used.
30 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
32 template < typename... Options >
33 using base_hook = cds::intrusive::single_link::base_hook< Options...>;
37 \p MemberOffset specifies offset in bytes of \ref node member into your structure.
38 Use \p offsetof macro to define \p MemberOffset
41 - opt::gc - garbage collector used.
42 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
44 template < size_t MemberOffset, typename... Options >
45 using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
49 \p NodeTraits defines type traits for node.
50 See \ref node_traits for \p NodeTraits interface description
53 - opt::gc - garbage collector used.
54 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
56 template <typename NodeTraits, typename... Options >
57 using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >;
59 /// Queue internal statistics. May be used for debugging or profiling
61 Template argument \p Counter defines type of counter.
62 Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed
63 strict event counting.
64 You may use stronger type of counter like as \p cds::atomicity::item_counter,
65 or even integral type, for example, \p int.
67 template <typename Counter = cds::atomicity::event_counter >
70 typedef Counter counter_type; ///< Counter type
72 counter_type m_EnqueueCount ; ///< Enqueue call count
73 counter_type m_DequeueCount ; ///< Dequeue call count
74 counter_type m_EnqueueRace ; ///< Count of enqueue race conditions encountered
75 counter_type m_DequeueRace ; ///< Count of dequeue race conditions encountered
76 counter_type m_AdvanceTailError ; ///< Count of "advance tail failed" events
77 counter_type m_BadTail ; ///< Count of events "Tail is not pointed to the last item in the queue"
78 counter_type m_EmptyDequeue ; ///< Count of dequeue from empty queue
80 /// Register enqueue call
81 void onEnqueue() { ++m_EnqueueCount; }
82 /// Register dequeue call
83 void onDequeue() { ++m_DequeueCount; }
84 /// Register enqueue race event
85 void onEnqueueRace() { ++m_EnqueueRace; }
86 /// Register dequeue race event
87 void onDequeueRace() { ++m_DequeueRace; }
88 /// Register "advance tail failed" event
89 void onAdvanceTailFailed() { ++m_AdvanceTailError; }
90 /// Register event "Tail is not pointed to last item in the queue"
91 void onBadTail() { ++m_BadTail; }
92 /// Register dequeuing from empty queue
93 void onEmptyDequeue() { ++m_EmptyDequeue; }
98 m_EnqueueCount.reset();
99 m_DequeueCount.reset();
100 m_EnqueueRace.reset();
101 m_DequeueRace.reset();
102 m_AdvanceTailError.reset();
104 m_EmptyDequeue.reset();
107 stat& operator +=( stat const& s )
109 m_EnqueueCount += s.m_EnqueueCount.get();
110 m_DequeueCount += s.m_DequeueCount.get();
111 m_EnqueueRace += s.m_EnqueueRace.get();
112 m_DequeueRace += s.m_DequeueRace.get();
113 m_AdvanceTailError += s.m_AdvanceTailError.get();
114 m_BadTail += s.m_BadTail.get();
115 m_EmptyDequeue += s.m_EmptyDequeue.get();
122 /// Dummy queue statistics - no counting is performed, no overhead. Support interface like \p msqueue::stat
126 void onEnqueue() const {}
127 void onDequeue() const {}
128 void onEnqueueRace() const {}
129 void onDequeueRace() const {}
130 void onAdvanceTailFailed() const {}
131 void onBadTail() const {}
132 void onEmptyDequeue() const {}
135 empty_stat& operator +=( empty_stat const& )
142 /// MSQueue default traits
145 /// Back-off strategy
146 typedef cds::backoff::empty back_off;
148 /// Hook, possible types are \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook
149 typedef msqueue::base_hook<> hook;
151 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used for dequeuing
152 typedef opt::v::empty_disposer disposer;
154 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
155 typedef atomicity::empty_item_counter item_counter;
157 /// Internal statistics (by default, disabled)
159 Possible option value are: \p msqueue::stat, \p msqueue::empty_stat (the default),
160 user-provided class that supports \p %msqueue::stat interface.
162 typedef msqueue::empty_stat stat;
164 /// C++ memory ordering model
166 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
167 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
169 typedef opt::v::relaxed_ordering memory_model;
171 /// Link checking, see \p cds::opt::link_checker
172 static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
174 /// Padding for internal critical atomic data. Default is \p opt::cache_line_padding
175 enum { padding = opt::cache_line_padding };
178 /// Metafunction converting option list to \p msqueue::traits
180 Supported \p Options are:
182 - \p opt::hook - hook used. Possible hooks are: \p msqueue::base_hook, \p msqueue::member_hook, \p msqueue::traits_hook.
183 If the option is not specified, \p %msqueue::base_hook<> is used.
184 - \p opt::back_off - back-off strategy used, default is \p cds::backoff::empty.
185 - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used
187 - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
188 - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter (item counting disabled)
189 To enable item counting use \p cds::atomicity::item_counter
190 - \p opt::stat - the type to gather internal statistics.
191 Possible statistics types are: \p msqueue::stat, \p msqueue::empty_stat, user-provided class that supports \p %msqueue::stat interface.
192 Default is \p %msqueue::empty_stat (internal statistics disabled).
193 - \p opt::padding - padding for internal critical atomic data. Default is \p opt::cache_line_padding
194 - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
195 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
197 Example: declare \p %MSQueue with item counting and internal statistics
199 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
200 typename cds::intrusive::msqueue::make_traits<
201 cds::intrusive::opt:hook< cds::intrusive::msqueue::base_hook< cds::opt::gc<cds:gc::HP> >>,
202 cds::opt::item_counte< cds::atomicity::item_counter >,
203 cds::opt::stat< cds::intrusive::msqueue::stat<> >
208 template <typename... Options>
210 # ifdef CDS_DOXYGEN_INVOKED
211 typedef implementation_defined type; ///< Metafunction result
213 typedef typename cds::opt::make_options<
214 typename cds::opt::find_type_traits< traits, Options... >::type
219 } // namespace msqueue
221 /// Michael & Scott's intrusive lock-free queue
222 /** @ingroup cds_intrusive_queue
223 Implementation of well-known Michael & Scott's queue algorithm:
224 - [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
227 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP
228 - \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,
229 or it should have a member of type \p %msqueue::node for \p msqueue::member_hook,
230 or it should be convertible to \p %msqueue::node for \p msqueue::traits_hook.
231 - \p Traits - queue traits, default is \p msqueue::traits. You can use \p msqueue::make_traits
232 metafunction to make your traits or just derive your traits from \p %msqueue::traits:
234 struct myTraits: public cds::intrusive::msqueue::traits {
235 typedef cds::intrusive::msqueue::stat<> stat;
236 typedef cds::atomicity::item_counter item_counter;
238 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo, myTraits > myQueue;
240 // Equivalent make_traits example:
241 typedef cds::intrusive::MSQueue< cds::gc::HP, Foo,
242 typename cds::intrusive::msqueue::make_traits<
243 cds::opt::stat< cds::intrusive::msqueue::stat<> >,
244 cds::opt::item_counter< cds::atomicity::item_counter >
249 \par About item disposing
250 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
251 the standpoint of the algo. See \p dequeue() function for explanation.
255 #include <cds/intrusive/msqueue.h>
256 #include <cds/gc/hp.h>
258 namespace ci = cds::inrtusive;
259 typedef cds::gc::HP hp_gc;
261 // MSQueue with Hazard Pointer garbage collector, base hook + item disposer:
262 struct Foo: public ci::msqueue::node< hp_gc >
268 // Disposer for Foo struct just deletes the object passed in
270 void operator()( Foo * p )
276 // Declare traits for the queue
277 struct myTraits: public ci::msqueue::traits {
279 ci::msqueue::base_hook< ci::opt::gc<hp_gc> >
281 ,ci::opt::disposer< fooDisposer >
284 // At least, declare the queue type
285 typedef ci::MSQueue< hp_gc, Foo, myTraits > fooQueue;
288 // MSQueue with Hazard Pointer garbage collector,
289 // member hook + item disposer + item counter,
290 // without padding of internal queue data
291 // Use msqueue::make_traits
296 ci::msqueue::node< hp_gc > hMember;
299 typedef ci::MSQueue< hp_gc,
301 typename ci::msqueue::make_traits<
303 ci::msqueue::member_hook<
304 offsetof(Bar, hMember)
308 ,ci::opt::disposer< fooDisposer >
309 ,cds::opt::item_counter< cds::atomicity::item_counter >
310 ,cds::opt::padding< cds::opt::no_special_padding >
315 template <typename GC, typename T, typename Traits = msqueue::traits>
319 typedef GC gc; ///< Garbage collector
320 typedef T value_type; ///< type of value to be stored in the queue
321 typedef Traits traits; ///< Queue traits
323 typedef typename traits::hook hook; ///< hook type
324 typedef typename hook::node_type node_type; ///< node type
325 typedef typename traits::disposer disposer; ///< disposer used
326 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
327 typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker; ///< link checker
329 typedef typename traits::back_off back_off; ///< back-off strategy
330 typedef typename traits::item_counter item_counter; ///< Item counter class
331 typedef typename traits::stat stat; ///< Internal statistics
332 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
334 /// Rebind template arguments
335 template <typename GC2, typename T2, typename Traits2>
337 typedef MSQueue< GC2, T2, Traits2 > other; ///< Rebinding result
340 static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 2; ///< Count of hazard pointer required for the algorithm
345 // GC and node_type::gc must be the same
346 static_assert((std::is_same<gc, typename node_type::gc>::value), "GC and node_type::gc must be the same");
348 typedef typename node_type::atomic_node_ptr atomic_node_ptr;
350 atomic_node_ptr m_pHead; ///< Queue's head pointer
351 typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad1_;
352 atomic_node_ptr m_pTail; ///< Queue's tail pointer
353 typename opt::details::apply_padding< atomic_node_ptr, traits::padding >::padding_type pad2_;
354 node_type m_Dummy; ///< dummy node
355 typename opt::details::apply_padding< node_type, traits::padding >::padding_type pad3_;
356 item_counter m_ItemCounter; ///< Item counter
357 stat m_Stat; ///< Internal statistics
361 struct dequeue_result {
362 typename gc::template GuardArray<2> guards;
368 bool do_dequeue( dequeue_result& res )
375 h = res.guards.protect( 0, m_pHead, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
376 pNext = res.guards.protect( 1, h->m_pNext, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
377 if ( m_pHead.load(memory_model::memory_order_acquire) != h )
380 if ( pNext == nullptr ) {
381 m_Stat.onEmptyDequeue();
382 return false; // empty queue
385 node_type * t = m_pTail.load(memory_model::memory_order_acquire);
387 // It is needed to help enqueue
388 m_pTail.compare_exchange_strong( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
393 if ( m_pHead.compare_exchange_strong( h, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
396 m_Stat.onDequeueRace();
408 static void clear_links( node_type * pNode )
410 pNode->m_pNext.store( nullptr, memory_model::memory_order_release );
413 void dispose_result( dequeue_result& res )
415 dispose_node( res.pHead );
418 void dispose_node( node_type * p )
420 // Note about the dummy node:
421 // We cannot clear m_Dummy here since it leads to ABA.
422 // On the other hand, we cannot use deferred clear_links( &m_Dummy ) call via
423 // HP retiring cycle since m_Dummy is member of MSQueue and may be destroyed
424 // before HP retiring cycle invocation.
425 // So, we will never clear m_Dummy
427 struct disposer_thunk {
428 void operator()( value_type * p ) const
430 assert( p != nullptr );
431 MSQueue::clear_links( node_traits::to_node_ptr( p ) );
437 gc::template retire<disposer_thunk>( node_traits::to_value_ptr( p ) );
442 /// Initializes empty queue
444 : m_pHead( &m_Dummy )
445 , m_pTail( &m_Dummy )
448 /// Destructor clears the queue
450 Since the Michael & Scott queue contains at least one item even
451 if the queue is empty, the destructor may call item disposer.
457 node_type * pHead = m_pHead.load(memory_model::memory_order_relaxed);
459 assert( pHead != nullptr );
460 assert( pHead == m_pTail.load(memory_model::memory_order_relaxed) );
462 m_pHead.store( nullptr, memory_model::memory_order_relaxed );
463 m_pTail.store( nullptr, memory_model::memory_order_relaxed );
465 dispose_node( pHead );
468 /// Enqueues \p val value into the queue.
469 /** @anchor cds_intrusive_MSQueue_enqueue
470 The function always returns \p true.
472 bool enqueue( value_type& val )
474 node_type * pNew = node_traits::to_node_ptr( val );
475 link_checker::is_empty( pNew );
477 typename gc::Guard guard;
482 t = guard.protect( m_pTail, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
484 node_type * pNext = t->m_pNext.load(memory_model::memory_order_acquire);
485 if ( pNext != nullptr ) {
486 // Tail is misplaced, advance it
487 m_pTail.compare_exchange_weak( t, pNext, memory_model::memory_order_release, atomics::memory_order_relaxed );
492 node_type * tmp = nullptr;
493 if ( t->m_pNext.compare_exchange_strong( tmp, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
496 m_Stat.onEnqueueRace();
502 if ( !m_pTail.compare_exchange_strong( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed ))
503 m_Stat.onAdvanceTailFailed();
507 /// Dequeues a value from the queue
508 /** @anchor cds_intrusive_MSQueue_dequeue
509 If the queue is empty the function returns \p nullptr.
512 The queue algorithm has following feature: when \p %dequeue() is called,
513 the item returning is still queue's top, and previous top is disposed:
516 before dequeuing Dequeue after dequeuing
517 +------------------+ +------------------+
518 Top ->| Item 1 | -> Dispose Item 1 | Item 2 | <- Top
519 +------------------+ +------------------+
520 | Item 2 | -> Return Item 2 | ... |
525 \p %dequeue() function returns Item 2, that becomes new top of queue, and calls
526 the disposer for Item 1, that was queue's top on function entry.
527 Thus, you cannot manually delete item returned because it is still included in
528 item sequence and it has valuable link field that must not be zeroed.
529 The item should be deleted only in garbage collector retire cycle using the disposer.
531 value_type * dequeue()
535 if ( do_dequeue( res )) {
536 dispose_result( res );
538 return node_traits::to_value_ptr( *res.pNext );
543 /// Synonym for \ref cds_intrusive_MSQueue_enqueue "enqueue()" function
544 bool push( value_type& val )
546 return enqueue( val );
549 /// Synonym for \ref cds_intrusive_MSQueue_dequeue "dequeue()" function
555 /// Checks if the queue is empty
558 typename gc::Guard guard;
559 node_type * p = guard.protect( m_pHead, []( node_type * p ) -> value_type * { return node_traits::to_value_ptr( p );});
560 return p->m_pNext.load( memory_model::memory_order_relaxed ) == nullptr;
565 The function repeatedly calls \p dequeue() until it returns \p nullptr.
566 The disposer defined in template \p Traits is called for each item
567 that can be safely disposed.
574 /// Returns queue's item count
576 The value returned depends on \p msqueue::traits::item_counter. For \p atomicity::empty_item_counter,
577 this function always returns 0.
579 @note Even if you use real item counter and it returns 0, this fact is not mean that the queue
580 is empty. To check queue emptyness use \p empty() method.
584 return m_ItemCounter.value();
587 /// Returns reference to internal statistics
588 stat const& statistics() const
594 }} // namespace cds::intrusive
596 #endif // #ifndef CDSLIB_INTRUSIVE_MSQUEUE_H