3 #ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H
4 #define CDSLIB_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/sync/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
81 nStatus.store( 0 /*op_free*/, atomics::memory_order_release );
86 /// Stack internal statistics. May be useful for debugging or profiling
88 Template argument \p Counter defines type of counter.
89 Default is cds::atomicity::event_counter.
90 You may use stronger type of counter like as cds::atomicity::item_counter,
91 or even an integral type, for example, \p int
93 template <typename Counter = cds::atomicity::event_counter >
96 typedef Counter counter_type ; ///< Counter type
98 counter_type m_PushCount ; ///< Push call count
99 counter_type m_PopCount ; ///< Pop call count
100 counter_type m_PushRace ; ///< Count of push race conditions encountered
101 counter_type m_PopRace ; ///< Count of pop race conditions encountered
102 counter_type m_ActivePushCollision ; ///< Count of active push collision for elimination back-off
103 counter_type m_ActivePopCollision ; ///< Count of active pop collision for elimination back-off
104 counter_type m_PassivePushCollision ; ///< Count of passive push collision for elimination back-off
105 counter_type m_PassivePopCollision ; ///< Count of passive pop collision for elimination back-off
106 counter_type m_EliminationFailed ; ///< Count of unsuccessful elimination back-off
109 void onPush() { ++m_PushCount; }
110 void onPop() { ++m_PopCount; }
111 void onPushRace() { ++m_PushRace; }
112 void onPopRace() { ++m_PopRace; }
113 void onActiveCollision( operation_id opId )
115 if ( opId == treiber_stack::op_push )
116 ++m_ActivePushCollision;
118 ++m_ActivePopCollision;
120 void onPassiveCollision( operation_id opId )
122 if ( opId == treiber_stack::op_push )
123 ++m_PassivePushCollision;
125 ++m_PassivePopCollision;
127 void onEliminationFailed()
129 ++m_EliminationFailed;
134 /// Empty (no overhead) stack statistics. Support interface like treiber_stack::stat
142 void onActiveCollision( operation_id ) {}
143 void onPassiveCollision( operation_id ) {}
144 void onEliminationFailed() {}
148 /// TreiberStack default type traits
151 /// Back-off strategy
152 typedef cds::backoff::Default back_off;
154 /// Hook, possible types are \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook
155 typedef treiber_stack::base_hook<> hook;
157 /// The functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only in \p TreiberStack::clear() function
158 typedef opt::v::empty_disposer disposer;
160 /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
161 typedef cds::atomicity::empty_item_counter item_counter;
163 /// C++ memory ordering model
165 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
166 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
168 typedef opt::v::relaxed_ordering memory_model;
170 /// Internal statistics (by default, disabled)
172 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
173 user-provided class that supports \p %treiber_stack::stat interface.
175 typedef treiber_stack::empty_stat stat;
177 /// Link checking, see \p cds::opt::link_checker
178 static CDS_CONSTEXPR const opt::link_check_type link_checker = opt::debug_check_link;
180 /** @name Elimination back-off traits
181 The following traits is used only if elimination enabled
185 /// Enable elimination back-off; by default, it is disabled
186 static CDS_CONSTEXPR const bool enable_elimination = false;
188 /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
189 typedef cds::backoff::delay<> elimination_backoff;
191 /// Buffer type for elimination array
193 Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
194 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
195 The size should be selected empirically for your application and hardware, there are no common rules for that.
196 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
198 typedef opt::v::static_buffer< int, 4 > buffer;
200 /// Random engine to generate a random position in elimination array
201 typedef opt::v::c_rand random_engine;
203 /// Lock type used in elimination, default is cds::sync::spin
204 typedef cds::sync::spin lock_type;
209 /// Metafunction converting option list to \p treiber_stack::traits
211 Supported \p Options are:
212 - opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook.
213 If the option is not specified, \p %treiber_stack::base_hook<> is used.
214 - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
215 - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only
216 in \p TreiberStack::clear function.
217 - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link.
218 - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
219 or \p opt::v::sequential_consistent (sequentially consisnent memory model).
220 - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
221 no item counting. Use \p cds::atomicity::item_counter to enable item counting.
222 - opt::stat - the type to gather internal statistics.
223 Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
224 user-provided class that supports \p treiber_stack::stat interface.
225 - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
227 If elimination back-off is enabled, additional options can be specified:
228 - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
229 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
230 The size should be selected empirically for your application and hardware, there are no common rules for that.
231 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
232 - opt::random_engine - a random engine to generate a random position in elimination array.
233 Default is \p opt::v::c_rand.
234 - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
235 - opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin
237 Example: declare \p %TreiberStack with elimination enabled and internal statistics
239 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
240 typename cds::intrusive::treiber_stack::make_traits<
241 cds::opt::enable_elimination< true >,
242 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
247 template <typename... Options>
249 # ifdef CDS_DOXYGEN_INVOKED
250 typedef implementation_defined type; ///< Metafunction result
252 typedef typename cds::opt::make_options<
253 typename cds::opt::find_type_traits< traits, Options... >::type
263 template <bool EnableElimination, typename T, typename Traits>
264 class elimination_backoff;
266 template <typename T, typename Traits>
267 class elimination_backoff<false, T, Traits>
269 typedef typename Traits::back_off back_off;
280 template <typename Stat>
281 bool backoff( treiber_stack::operation< T >&, Stat& )
289 elimination_backoff()
292 elimination_backoff( size_t )
295 typedef wrapper type;
302 template <typename T, typename Traits>
303 class elimination_backoff<true, T, Traits>
305 typedef typename Traits::back_off back_off;
307 /// Back-off for elimination (usually delay)
308 typedef typename Traits::elimination_backoff elimination_backoff_type;
309 /// Lock type used in elimination back-off
310 typedef typename Traits::lock_type elimination_lock_type;
311 /// Random engine used in elimination back-off
312 typedef typename Traits::random_engine elimination_random_engine;
314 /// Per-thread elimination record
315 typedef cds::algo::elimination::record elimination_rec;
317 /// Collision array record
318 struct collision_array_record {
319 elimination_rec * pRec;
320 elimination_lock_type lock;
323 /// Collision array used in elimination-backoff; each item is optimized for cache-line size
324 typedef typename Traits::buffer::template rebind<
325 typename cds::details::type_padding<collision_array_record, cds::c_nCacheLineSize >::type
326 >::other collision_array;
328 /// Operation descriptor used in elimination back-off
329 typedef treiber_stack::operation< T > operation_desc;
331 /// Elimination back-off data
332 struct elimination_data {
333 mutable elimination_random_engine randEngine; ///< random engine
334 collision_array collisions; ///< collision array
338 //TODO: check Traits::buffer must be static!
340 elimination_data( size_t nCollisionCapacity )
341 : collisions( nCollisionCapacity )
345 elimination_data m_Elimination;
347 enum operation_status {
353 typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
355 template <bool Exp2 = collision_array::c_bExp2>
356 typename std::enable_if< Exp2, size_t >::type slot_index() const
358 return m_Elimination.randEngine() & (m_Elimination.collisions.capacity() - 1);
361 template <bool Exp2 = collision_array::c_bExp2>
362 typename std::enable_if< !Exp2, size_t >::type slot_index() const
364 return m_Elimination.randEngine() % m_Elimination.collisions.capacity();
368 elimination_backoff()
370 m_Elimination.collisions.zeroize();
373 elimination_backoff( size_t nCollisionCapacity )
374 : m_Elimination( nCollisionCapacity )
376 m_Elimination.collisions.zeroize();
379 typedef elimination_backoff& type;
389 template <typename Stat>
390 bool backoff( operation_desc& op, Stat& stat )
392 elimination_backoff_type bkoff;
393 op.nStatus.store( op_busy, atomics::memory_order_release );
395 elimination_rec * myRec = cds::algo::elimination::init_record( op );
397 collision_array_record& slot = m_Elimination.collisions[ slot_index() ];
400 elimination_rec * himRec = slot.pRec;
402 operation_desc * himOp = static_cast<operation_desc *>( himRec->pOp );
404 if ( himOp->idOp != op.idOp ) {
405 if ( op.idOp == treiber_stack::op_push )
406 himOp->pVal = op.pVal;
408 op.pVal = himOp->pVal;
410 himOp->nStatus.store( op_collided, atomics::memory_order_release );
413 cds::algo::elimination::clear_record();
414 stat.onActiveCollision( op.idOp );
417 himOp->nStatus.store( op_free, atomics::memory_order_release );
423 // Wait for colliding operation
424 bkoff( [&op]() CDS_NOEXCEPT -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_busy; } );
426 slot_scoped_lock l( slot.lock );
427 if ( slot.pRec == myRec )
431 bool bCollided = op.nStatus.load( atomics::memory_order_acquire ) == op_collided;
434 stat.onEliminationFailed();
436 stat.onPassiveCollision( op.idOp );
438 cds::algo::elimination::clear_record();
443 } // namespace details
445 } // namespace treiber_stack
447 /// Treiber intrusive stack
448 /** @ingroup cds_intrusive_stack
449 Intrusive implementation of well-known Treiber's stack algorithm:
450 - R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
452 \ref cds_elimination_description "Elimination back-off technique" can be used optionally.
453 The idea of elimination algorithm is taken from:
454 - [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"
456 The elimination algorithm uses a single elimination array as a back-off schema
457 on a shared lock-free stack. If the threads fail on the stack, they attempt to eliminate
458 on the array, and if they fail in eliminating, they attempt to access the stack again and so on.
460 @note Hendler's et al paper describes a lock-free implementation of elimination back-off which is quite complex.
461 The main difficulty is the managing life-time of elimination record.
462 Our implementation uses simplified lock-based (spin-based) approach which allows
463 the elimination record allocation on thread's stack.
464 This approach demonstrates sufficient performance under high load.
467 - \p GC - garbage collector type: \p gc::HP, \p gc::DHP.
468 Garbage collecting schema must be the same as \p treiber_stack::node GC.
469 - \p T - a type the stack contains. A value of type \p T must be derived
470 from \p treiber_stack::node for \p treiber_stack::base_hook,
471 or it should have a member of type \p %treiber_stack::node for \p treiber_stack::member_hook,
472 or it should be convertible to \p %treiber_stack::node for \p treiber_stack::traits_hook.
473 - \p Traits - stack traits, default is \p treiber_stack::traits. You can use \p treiber_stack::make_traits
474 metafunction to make your traits or just derive your traits from \p %treiber_stack::traits:
476 struct myTraits: public cds::intrusive::treiber_stack::traits {
477 typedef cds::intrusive::treiber_stack::stat<> stat;
479 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo, myTraits > myStack;
481 // Equivalent make_traits example:
482 typedef cds::intrusive::TreiberStack< cds::gc::HP, Foo,
483 typename cds::intrusive::treiber_stack::make_traits<
484 cds::opt::stat< cds::intrusive::treiber_stack::stat<> >
489 @note Be careful when you want destroy an item popped, see \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
491 @anchor cds_intrusive_TreiberStack_examples
494 Example of how to use \p treiber_stack::base_hook.
495 Your class that objects will be pushed on \p %TreiberStack should be based on \p treiber_stack::node class
497 #include <cds/intrusive/treiber_stack.h>
498 #include <cds/gc/hp.h>
500 namespace ci = cds::intrusive;
501 typedef cds::gc::HP gc;
503 struct myData: public ci::treiber_stack::node< gc >
509 typedef ci::TreiberStack< gc,
511 typename cds::intrusive::treiber_stack::make_traits<
512 ci::opt::hook< ci::treiber_stack::base_hook< gc > >
516 // Stack with elimination back-off enabled
517 typedef ci::TreiberStack< gc,
519 typename ci::treiber_stack::make_traits<
520 ci::opt::hook< ci::treiber_stack::base_hook< gc > >,
521 cds::opt::enable_elimination< true >
523 > elimination_stack_t;
526 Example of how to use \p treiber_stack::base_hook with different tags.
528 #include <cds/intrusive/treiber_stack.h>
529 #include <cds/gc/hp.h>
531 namespace ci = cds::intrusive;
532 typedef cds::gc::HP gc;
534 // It is not necessary to declare complete type for tags
539 : public ci::treiber_stack::node< gc, tag1 >
540 , public ci::treiber_stack::node< gc, tag2 >
545 typedef ci::TreiberStack< gc,
547 typename ci::treiber_stack::make_traits<
548 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag1 > >
552 typedef ci::TreiberStack< gc,
554 typename ci::treiber_stack::make_traits<
555 ci::opt::hook< ci::treiber_stack::base_hook< gc, tag2 > >
559 // You may add myData objects into stack1_t and stack2_t independently
567 s2.push( i1 ) ; // i1 is now contained in s1 and s2.
571 p = s1.pop() ; // pop i1 from s1
572 p = s1.pop() ; // p == nullptr, s1 is empty
573 p = s2.pop() ; // pop i1 from s2
574 p = s2.pop() ; // pop i2 from s2
575 p = s2.pop() ; // p == nullptr, s2 is empty
579 Example of how to use \p treiber_stack::member_hook.
580 Your class should have a member of type \p treiber_stack::node
582 #include <stddef.h> // offsetof macro
583 #include <cds/intrusive/treiber_stack.h>
584 #include <cds/gc/hp.h>
586 namespace ci = cds::intrusive;
587 typedef cds::gc::HP gc;
592 ci::treiber_stack::node< gc > member_hook_;
596 typedef ci::TreiberStack< gc,
598 typename ci::treiber_stack::make_traits<
599 ci::opt::hook< ci::treiber_stack::member_hook< offsetof(myData, member_hook_), gc >>
607 typename Traits = treiber_stack::traits
612 /// Rebind template arguments
613 template <typename GC2, typename T2, typename Traits2>
615 typedef TreiberStack< GC2, T2, Traits2 > other ; ///< Rebinding result
619 typedef GC gc; ///< Garbage collector
620 typedef T value_type; ///< type of value stored in the stack
621 typedef Traits traits; ///< Stack traits
623 typedef typename traits::hook hook; ///< hook type
624 typedef typename hook::node_type node_type; ///< node type
625 typedef typename traits::disposer disposer; ///< disposer used
626 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
627 typedef typename single_link::get_link_checker< node_type, traits::link_checker >::type link_checker ; ///< link checker
628 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
629 typedef typename traits::item_counter item_counter; ///< Item counter class
630 typedef typename traits::stat stat; ///< Internal statistics
631 typedef typename traits::back_off back_off; ///< back-off strategy
633 public: // related to elimination back-off
635 /// Elimination back-off is enabled or not
636 static CDS_CONSTEXPR const bool enable_elimination = traits::enable_elimination;
637 /// back-off strategy used to wait for elimination
638 typedef typename traits::elimination_backoff elimination_backoff_type;
639 /// Lock type used in elimination back-off
640 typedef typename traits::lock_type elimination_lock_type;
641 /// Random engine used in elimination back-off
642 typedef typename traits::random_engine elimination_random_engine;
645 typename node_type::atomic_node_ptr m_Top; ///< Top of the stack
646 item_counter m_ItemCounter; ///< Item counter
647 stat m_stat; ///< Internal statistics
650 typedef treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> elimination_backoff;
651 elimination_backoff m_Backoff;
653 typedef intrusive::node_to_value<TreiberStack> node_to_value;
654 typedef treiber_stack::operation< value_type > operation_desc;
656 // GC and node_type::gc must be the same
657 static_assert( std::is_same<gc, typename node_type::gc>::value, "GC and node_type::gc must be the same");
659 static_assert( !enable_elimination || std::is_same<typename elimination_random_engine::result_type, unsigned int>::value,
660 "Random engine result type must be unsigned int");
665 void clear_links( node_type * pNode ) CDS_NOEXCEPT
667 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
670 template <bool EnableElimination>
671 struct elimination_backoff_impl;
675 /// Constructs empty stack
680 /// Constructs empty stack and initializes elimination back-off data
682 This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
683 \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
684 \p nCollisionCapacity parameter specifies the capacity of collision array.
686 TreiberStack( size_t nCollisionCapacity )
688 , m_Backoff( nCollisionCapacity )
691 /// \p %TreiberStack is not copy-constructible
692 TreiberStack( TreiberStack const& ) = delete;
694 /// Destructor calls \ref cds_intrusive_TreiberStack_clear "clear" member function
700 /// Push the item \p val on the stack
702 No copying is made since it is intrusive stack.
704 bool push( value_type& val )
706 node_type * pNew = node_traits::to_node_ptr( val );
707 link_checker::is_empty( pNew );
709 typename elimination_backoff::type bkoff = m_Backoff.init();
712 if ( enable_elimination ) {
713 op.idOp = treiber_stack::op_push;
717 node_type * t = m_Top.load(memory_model::memory_order_relaxed);
719 pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
720 if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
727 if ( bkoff.backoff( op, m_stat ))
732 /// Pop an item from the stack
734 If stack is empty, returns \p nullptr.
735 The disposer is <b>not</b> called for popped item.
736 See \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
740 typename elimination_backoff::type bkoff = m_Backoff.init();
741 typename gc::Guard guard;
744 if ( enable_elimination ) {
745 op.idOp = treiber_stack::op_pop;
749 node_type * t = guard.protect( m_Top, node_to_value() );
751 return nullptr; // stack is empty
753 node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed);
754 if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
758 return node_traits::to_value_ptr( *t );
762 if ( bkoff.backoff( op, m_stat )) {
763 // may return nullptr if stack is empty
769 /// Check if stack is empty
772 return m_Top.load( memory_model::memory_order_relaxed ) == nullptr;
776 /** @anchor cds_intrusive_TreiberStack_clear
777 For each removed item the disposer is called.
779 @note It is possible that after <tt>clear()</tt> the <tt>empty()</tt> returns \p false
780 if some other thread pushes an item into the stack during \p clear works
787 pTop = m_Top.load( memory_model::memory_order_relaxed );
788 if ( pTop == nullptr )
790 if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
791 m_ItemCounter.reset();
798 node_type * p = pTop;
799 pTop = p->m_pNext.load(memory_model::memory_order_relaxed);
801 gc::template retire<disposer>( node_traits::to_value_ptr( *p ) );
805 /// Returns stack's item count
807 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
808 this function always returns 0.
810 @warning Even if you use real item counter and it returns 0, this fact is not mean that the stack
811 is empty. To check emptyness use \ref empty() method.
815 return m_ItemCounter.value();
818 /// Returns reference to internal statistics
819 stat const& statistics() const
825 }} // namespace cds::intrusive
827 #endif // #ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H