3 #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H
4 #define __CDS_INTRUSIVE_TREIBER_STACK_H
7 #include <mutex> // unique_lock
8 #include <cds/intrusive/details/single_link_struct.h>
9 #include <cds/algo/elimination.h>
10 #include <cds/opt/buffer.h>
11 #include <cds/lock/spinlock.h>
12 #include <cds/details/type_padding.h>
14 namespace cds { namespace intrusive {
16 /// TreiberStack related definitions
17 /** @ingroup cds_intrusive_helper
19 namespace treiber_stack {
24 - GC - garbage collector used
25 - Tag - a \ref cds_intrusive_hook_tag "tag"
27 template <class GC, typename Tag = opt::none >
28 using node = cds::intrusive::single_link::node< GC, Tag > ;
33 - opt::gc - garbage collector used.
34 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
36 template < typename... Options >
37 using base_hook = cds::intrusive::single_link::base_hook< Options...>;
41 \p MemberOffset specifies offset in bytes of \ref node member into your structure.
42 Use \p offsetof macro to define \p MemberOffset
45 - opt::gc - garbage collector used.
46 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
48 template < size_t MemberOffset, typename... Options >
49 using member_hook = cds::intrusive::single_link::member_hook< MemberOffset, Options... >;
53 \p NodeTraits defines type traits for node.
54 See \ref node_traits for \p NodeTraits interface description
57 - opt::gc - garbage collector used.
58 - opt::tag - a \ref cds_intrusive_hook_tag "tag"
60 template <typename NodeTraits, typename... Options >
61 using traits_hook = cds::intrusive::single_link::traits_hook< NodeTraits, Options... >;
64 /// Operation id for the \ref cds_elimination_description "elimination back-off"
66 op_push, ///< push op id
70 /// Operation descriptor for the \ref cds_elimination_description "elimination back-off"
72 struct operation: public cds::algo::elimination::operation_desc
74 operation_id idOp; ///< Op id
75 T * pVal; ///< for push: pointer to argument; for pop: accepts a return value
76 atomics::atomic<unsigned int> nStatus; ///< Internal elimination status
85 /// Stack internal statistics. May be useful for debugging or profiling
87 Template argument \p Counter defines type of counter.
88 Default is cds::atomicity::event_counter.
89 You may use stronger type of counter like as cds::atomicity::item_counter,
90 or even an integral type, for example, \p int
92 template <typename Counter = cds::atomicity::event_counter >
95 typedef Counter counter_type ; ///< Counter type
97 counter_type m_PushCount ; ///< Push call count
98 counter_type m_PopCount ; ///< Pop call count
99 counter_type m_PushRace ; ///< Count of push race conditions encountered
100 counter_type m_PopRace ; ///< Count of pop race conditions encountered
101 counter_type m_ActivePushCollision ; ///< Count of active push collision for elimination back-off
102 counter_type m_ActivePopCollision ; ///< Count of active pop collision for elimination back-off
103 counter_type m_PassivePushCollision ; ///< Count of passive push collision for elimination back-off
104 counter_type m_PassivePopCollision ; ///< Count of passive pop collision for elimination back-off
105 counter_type m_EliminationFailed ; ///< Count of unsuccessful elimination back-off
108 void onPush() { ++m_PushCount; }
109 void onPop() { ++m_PopCount; }
110 void onPushRace() { ++m_PushRace; }
111 void onPopRace() { ++m_PopRace; }
112 void onActiveCollision( operation_id opId )
114 if ( opId == treiber_stack::op_push )
115 ++m_ActivePushCollision;
117 ++m_ActivePopCollision;
119 void onPassiveCollision( operation_id opId )
121 if ( opId == treiber_stack::op_push )
122 ++m_PassivePushCollision;
124 ++m_PassivePopCollision;
126 void onEliminationFailed()
128 ++m_EliminationFailed;
133 /// Empty (no overhead) stack statistics. Support interface like treiber_stack::stat
141 void onActiveCollision( operation_id ) {}
142 void onPassiveCollision( operation_id ) {}
143 void onEliminationFailed() {}
147 /// TreiberStack default type traits
150 /// Back-off strategy
151 typedef cds::backoff::Default back_off;
153 /// Hook, possible types are \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook
154 typedef treiber_stack::base_hook<> hook;
156 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p TreiberStack::clear() function
157 typedef opt::v::empty_disposer disposer;
159 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
160 typedef cds::atomicity::empty_item_counter item_counter;
162 /// C++ memory ordering model
164 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
165 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
167 typedef opt::v::relaxed_ordering memory_model;
169 /// Internal statistics (by default, disabled)
171 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
172 user-provided class that supports \p %treiber_stack::stat interface.
174 typedef treiber_stack::empty_stat stat;
176 /// Link checking, see \p cds::opt::link_checker
177 static CDS_CONSTEXPR_CONST opt::link_check_type link_checker = opt::debug_check_link;
179 /** @name Elimination back-off traits
180 The following traits is used only if elimination enabled
184 /// Enable elimination back-off; by default, it is disabled
185 static CDS_CONSTEXPR_CONST bool enable_elimination = false;
187 /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
188 typedef cds::backoff::delay<> elimination_backoff;
190 /// Buffer type for elimination array
192 Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
193 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
194 The size should be selected empirically for your application and hardware, there are no common rules for that.
195 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
197 typedef opt::v::static_buffer< int, 4 > buffer;
199 /// Random engine to generate a random position in elimination array
200 typedef opt::v::c_rand random_engine;
202 /// Lock type used in elimination, default is cds::lock::Spin
203 typedef cds::lock::Spin lock_type;
208 /// Metafunction converting option list to \p treiber_stack::traits
210 This is a wrapper for <tt> cds::opt::make_options< type_traits, Options...> </tt>
211 Supported \p Options are:
213 - opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook.
214 If the option is not specified, \p %treiber_stack::base_hook<> is used.
215 - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
216 - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only
217 in \p TreiberStack::clear function.
218 - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link.
219 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
220 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
221 - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
222 no item counting. Use \p cds::atomicity::item_counter to enable item counting.
223 - opt::stat - the type to gather internal statistics.
224 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
225 user-provided class that supports \p treiber_stack::stat interface.
226 - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
228 If elimination back-off is enabled, additional options can be specified:
229 - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
230 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
231 The size should be selected empirically for your application and hardware, there are no common rules for that.
232 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
233 - opt::random_engine - a random engine to generate a random position in elimination array.
234 Default is \p opt::v::c_rand.
235 - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
236 - opt::lock_type - a lock type used in elimination back-off, default is \p cds::lock::Spin.
238 Example: declare \p %TreiberStack with elimination enabled and internal statistics
240 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
241 typename cds::intrusive::treiber_stack::make_traits<
242 cds::opt::enable_elimination< true >,
243 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
248 template <typename... Options>
250 # ifdef CDS_DOXYGEN_INVOKED
251 typedef implementation_defined type; ///< Metafunction result
253 typedef typename cds::opt::make_options<
254 typename cds::opt::find_type_traits< traits, Options... >::type
264 template <bool EnableElimination, typename T, typename Traits>
265 class elimination_backoff;
267 template <typename T, typename Traits>
268 class elimination_backoff<false, T, Traits>
270 typedef typename Traits::back_off back_off;
274 elimination_backoff()
277 elimination_backoff( size_t )
285 template <typename Stat>
286 bool backoff(treiber_stack::operation< T >&, Stat& )
293 template <typename T, typename Traits>
294 class elimination_backoff<true, T, Traits>
296 typedef typename Traits::back_off back_off;
298 /// Back-off for elimination (usually delay)
299 typedef typename Traits::elimination_backoff elimination_backoff_type;
300 /// Lock type used in elimination back-off
301 typedef typename Traits::lock_type elimination_lock_type;
302 /// Random engine used in elimination back-off
303 typedef typename Traits::random_engine elimination_random_engine;
305 /// Per-thread elimination record
306 typedef cds::algo::elimination::record elimination_rec;
308 /// Collision array record
309 struct collision_array_record {
310 elimination_rec * pRec;
311 elimination_lock_type lock;
314 /// Collision array used in elimination-backoff; each item is optimized for cache-line size
315 typedef typename Traits::buffer::template rebind<
316 typename cds::details::type_padding<collision_array_record, cds::c_nCacheLineSize >::type
317 >::other collision_array;
319 /// Operation descriptor used in elimination back-off
320 typedef treiber_stack::operation< T > operation_desc;
322 /// Elimination back-off data
323 struct elimination_data {
324 elimination_random_engine randEngine; ///< random engine
325 collision_array collisions; ///< collision array
329 //TODO: check Traits::buffer must be static!
331 elimination_data( size_t nCollisionCapacity )
332 : collisions( nCollisionCapacity )
336 elimination_data m_Elimination;
338 enum operation_status {
344 typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
347 elimination_backoff()
349 m_Elimination.collisions.zeroize();
352 elimination_backoff( size_t nCollisionCapacity )
353 : m_Elimination( nCollisionCapacity )
355 m_Elimination.collisions.zeroize();
361 template <typename Stat>
362 bool backoff( operation_desc& op, Stat& stat )
364 elimination_backoff_type bkoff;
365 op.nStatus.store( op_busy, atomics::memory_order_relaxed );
367 elimination_rec * myRec = cds::algo::elimination::init_record( op );
369 collision_array_record& slot = m_Elimination.collisions[m_Elimination.randEngine() % m_Elimination.collisions.capacity()];
372 elimination_rec * himRec = slot.pRec;
374 operation_desc * himOp = static_cast<operation_desc *>( himRec->pOp );
376 if ( himOp->idOp != op.idOp ) {
377 if ( op.idOp == treiber_stack::op_push )
378 himOp->pVal = op.pVal;
380 op.pVal = himOp->pVal;
384 himOp->nStatus.store( op_collided, atomics::memory_order_release );
385 cds::algo::elimination::clear_record();
386 stat.onActiveCollision( op.idOp );
389 himOp->nStatus.store( op_free, atomics::memory_order_release );
395 // Wait for colliding operation
396 bkoff( [&op]() -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_busy; } );
398 slot_scoped_lock l( slot.lock );
399 if ( slot.pRec == myRec )
403 bool bCollided = op.nStatus.load( atomics::memory_order_acquire ) == op_collided;
406 stat.onEliminationFailed();
408 stat.onPassiveCollision( op.idOp );
410 cds::algo::elimination::clear_record();
415 } // namespace details
417 } // namespace treiber_stack
419 /// Treiber intrusive stack
420 /** @ingroup cds_intrusive_stack
421 Intrusive implementation of well-known Treiber's stack algorithm:
422 - R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
424 \ref cds_elimination_description "Elimination back-off technique" can be used optionally.
425 The idea of elimination algorithm is taken from:
426 - [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"
428 The elimination algorithm uses a single elimination array as a back-off schema
429 on a shared lock-free stack. If the threads fail on the stack, they attempt to eliminate
430 on the array, and if they fail in eliminating, they attempt to access the stack again and so on.
432 @note Hendler's et al paper describes a lock-free implementation of elimination back-off which is quite complex.
433 The main difficulty is the managing life-time of elimination record.
434 Our implementation uses simplified lock-based (spin-based) approach which allows
435 the elimination record allocation on thread's stack.
436 This approach demonstrates sufficient performance under high load.
439 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP.
440 Garbage collecting schema must be the same as \p treiber_stack::node GC.
441 - \p T - a type the stack contains. A value of type \p T must be derived
442 from \p treiber_stack::node for \p treiber_stack::base_hook,
443 or it should have a member of type \p %treiber_stack::node for \p treiber_stack::member_hook,
444 or it should be convertible to \p %treiber_stack::node for \p treiber_stack::traits_hook.
445 - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
446 metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
448 struct myTraits: public cds::intrusive::treiber_stack::traits {
449 typedef cds::intrusive::treiber_stack::stat<> stat;
451 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
453 // Equivalent make_traits example:
454 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
455 typename cds::intrusive::treiber_stack::make_traits<
456 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
461 @note Be careful when you want destroy an item popped, see \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
463 @anchor cds_intrusive_TreiberStack_examples
466 Example of how to use \p treiber_stack::base_hook.
467 Your class that objects will be pushed on \p %TreiberStack should be based on \p treiber_stack::node class
469 #include <cds/intrusive/treiber_stack.h>
470 #include <cds/gc/hp.h>
472 namespace ci = cds::intrusive;
473 typedef cds::gc::HP gc;
475 struct myData: public ci::treiber_stack::node< gc >
481 typedef ci::TreiberStack< gc,
483 typename cds::intrusive::treiber_stack::make_traits<
484 ci::opt::hook< ci::treiber_stack::base_hook< gc > >
488 // Stack with elimination back-off enabled
489 typedef ci::TreiberStack< gc,
491 typename ci::treiber_stack::make_traits<
492 ci::opt::hook< ci::treiber_stack::base_hook< gc > >,
493 cds::opt::enable_elimination< true >
495 > elimination_stack_t;
498 Example of how to use \p treiber_stack::base_hook with different tags.
500 #include <cds/intrusive/treiber_stack.h>
501 #include <cds/gc/hp.h>
503 namespace ci = cds::intrusive;
504 typedef cds::gc::HP gc;
506 // It is not necessary to declare complete type for tags
511 : public ci::treiber_stack::node< gc, tag1 >
512 , public ci::treiber_stack::node< gc, tag2 >
517 typedef ci::TreiberStack< gc,
519 typename ci::treiber_stack::make_traits<
520 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag1 > >
524 typedef ci::TreiberStack< gc,
526 typename ci::treiber_stack::make_traits<
527 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag2 > >
531 // You may add myData objects into stack1_t and stack2_t independently
539 s2.push( i1 ) ; // i1 is now contained in s1 and s2.
543 p = s1.pop() ; // pop i1 from s1
544 p = s1.pop() ; // p == nullptr, s1 is empty
545 p = s2.pop() ; // pop i1 from s2
546 p = s2.pop() ; // pop i2 from s2
547 p = s2.pop() ; // p == nullptr, s2 is empty
551 Example of how to use \p treiber_stack::member_hook.
552 Your class should have a member of type \p treiber_stack::node
554 #include <stddef.h> // offsetof macro
555 #include <cds/intrusive/treiber_stack.h>
556 #include <cds/gc/hp.h>
558 namespace ci = cds::intrusive;
559 typedef cds::gc::HP gc;
564 ci::treiber_stack::node< gc > member_hook_;
568 typedef ci::TreiberStack< gc,
570 typename ci::treiber_stack::make_traits<
571 ci::opt::hook< ci::treiber_stack::member_hook< offsetof(myData, member_hook_), gc >>
579 typename Traits = treiber_stack::traits
584 /// Rebind template arguments
585 template <typename GC2, typename T2, typename Traits2>
587 typedef TreiberStack< GC2, T2, Traits2 > other ; ///< Rebinding result
591 typedef GC gc; ///< Garbage collector
592 typedef T value_type; ///< type of value stored in the stack
593 typedef Traits traits; ///< Stack traits
595 typedef typename traits::hook hook; ///< hook type
596 typedef typename hook::node_type node_type; ///< node type
597 typedef typename traits::disposer disposer; ///< disposer used
598 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
599 typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker ; ///< link checker
600 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
601 typedef typename traits::item_counter item_counter; ///< Item counter class
602 typedef typename traits::stat stat; ///< Internal statistics
603 typedef typename traits::back_off back_off; ///< back-off strategy
605 public: // related to elimination back-off
607 /// Elimination back-off is enabled or not
608 static CDS_CONSTEXPR_CONST bool enable_elimination = traits::enable_elimination;
609 /// back-off strategy used to wait for elimination
610 typedef typename traits::elimination_backoff elimination_backoff_type;
611 /// Lock type used in elimination back-off
612 typedef typename traits::lock_type elimination_lock_type;
613 /// Random engine used in elimination back-off
614 typedef typename traits::random_engine elimination_random_engine;
617 typename node_type::atomic_node_ptr m_Top; ///< Top of the stack
618 item_counter m_ItemCounter; ///< Item counter
619 stat m_stat; ///< Internal statistics
622 treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> m_Backoff;
624 typedef intrusive::node_to_value<TreiberStack> node_to_value;
625 typedef treiber_stack::operation< value_type > operation_desc;
627 // GC and node_type::gc must be the same
628 static_assert( std::is_same<gc, typename node_type::gc>::value, "GC and node_type::gc must be the same");
630 static_assert( !enable_elimination || std::is_same<typename elimination_random_engine::result_type, unsigned int>::value,
631 "Random engine result type must be unsigned int");
636 void clear_links( node_type * pNode ) CDS_NOEXCEPT
638 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
641 template <bool EnableElimination>
642 struct elimination_backoff_impl;
646 /// Constructs empty stack
651 /// Constructs empty stack and initializes elimination back-off data
653 This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
654 \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
655 \p nCollisionCapacity parameter specifies the capacity of collision array.
657 TreiberStack( size_t nCollisionCapacity )
659 , m_Backoff( nCollisionCapacity )
662 /// \p %TreiberStack is not copy-constructible
663 TreiberStack( TreiberStack const& ) = delete;
665 /// Destructor calls \ref cds_intrusive_TreiberStack_clear "clear" member function
671 /// Push the item \p val on the stack
673 No copying is made since it is intrusive stack.
675 bool push( value_type& val )
677 node_type * pNew = node_traits::to_node_ptr( val );
678 link_checker::is_empty( pNew );
683 if ( enable_elimination ) {
684 op.idOp = treiber_stack::op_push;
688 node_type * t = m_Top.load(memory_model::memory_order_relaxed);
690 pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
691 if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) { // #1 sync-with #2
698 if ( m_Backoff.backoff( op, m_stat ))
703 /// Pop an item from the stack
705 If stack is empty, returns \p nullptr.
706 The disposer is <b>not</b> called for popped item.
707 See \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
712 typename gc::Guard guard;
715 if ( enable_elimination ) {
716 op.idOp = treiber_stack::op_pop;
720 node_type * t = guard.protect( m_Top, node_to_value() );
722 return nullptr; // stack is empty
724 node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed);
725 if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { // #2
729 return node_traits::to_value_ptr( *t );
733 if ( m_Backoff.backoff( op, m_stat )) {
734 // may return nullptr if stack is empty
740 /// Check if stack is empty
743 // http://www.manning-sandbox.com/thread.jspa?threadID=46245&tstart=0
744 return m_Top.load( memory_model::memory_order_relaxed ) == nullptr;
748 /** @anchor cds_intrusive_TreiberStack_clear
749 For each removed item the disposer is called.
751 @note It is possible that after <tt>clear()</tt> the <tt>empty()</tt> returns \p false
752 if some other thread pushes an item into the stack during \p clear works
759 pTop = m_Top.load( memory_model::memory_order_relaxed );
760 if ( pTop == nullptr )
762 if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ) ) { // sync-with #1 and #2
763 m_ItemCounter.reset();
770 node_type * p = pTop;
771 pTop = p->m_pNext.load(memory_model::memory_order_relaxed);
773 gc::template retire<disposer>( node_traits::to_value_ptr( *p ) );
777 /// Returns stack's item count
779 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
780 this function always returns 0.
782 @warning Even if you use real item counter and it returns 0, this fact is not mean that the stack
783 is empty. To check emptyness use \ref empty() method.
787 return m_ItemCounter.value();
790 /// Returns reference to internal statistics
791 stat const& statistics() const
797 }} // namespace cds::intrusive
799 #endif // #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H