3 #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H
4 #define __CDS_INTRUSIVE_TREIBER_STACK_H
7 #include <cds/intrusive/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/lock/scoped_lock.h>
13 #include <cds/details/type_padding.h>
15 namespace cds { namespace intrusive {
17 /// TreiberStack related definitions
18 /** @ingroup cds_intrusive_helper
20 namespace treiber_stack {
23 /// Operation id for the \ref cds_elimination_description "elimination back-off"
25 op_push, ///< push op id
29 /// Operation descriptor for the \ref cds_elimination_description "elimination back-off"
31 struct operation: public cds::algo::elimination::operation_desc
33 operation_id idOp; ///< Op id
34 T * pVal; ///< for push: pointer to argument; for pop: accepts a return value
35 CDS_ATOMIC::atomic<unsigned int> nStatus; ///< Internal elimination status
44 /// Stack internal statistics. May be useful for debugging or profiling
46 Template argument \p Counter defines type of counter.
47 Default is cds::atomicity::event_counter.
48 You may use stronger type of counter like as cds::atomicity::item_counter,
49 or even an integral type, for example, \p int
51 template <typename Counter = cds::atomicity::event_counter >
54 typedef Counter counter_type ; ///< Counter type
56 counter_type m_PushCount ; ///< Push call count
57 counter_type m_PopCount ; ///< Pop call count
58 counter_type m_PushRace ; ///< Count of push race conditions encountered
59 counter_type m_PopRace ; ///< Count of pop race conditions encountered
60 counter_type m_ActivePushCollision ; ///< Count of active push collision for elimination back-off
61 counter_type m_ActivePopCollision ; ///< Count of active pop collision for elimination back-off
62 counter_type m_PassivePushCollision ; ///< Count of passive push collision for elimination back-off
63 counter_type m_PassivePopCollision ; ///< Count of passive pop collision for elimination back-off
64 counter_type m_EliminationFailed ; ///< Count of unsuccessful elimination back-off
67 void onPush() { ++m_PushCount; }
68 void onPop() { ++m_PopCount; }
69 void onPushRace() { ++m_PushRace; }
70 void onPopRace() { ++m_PopRace; }
71 void onActiveCollision( operation_id opId )
73 if ( opId == treiber_stack::op_push )
74 ++m_ActivePushCollision;
76 ++m_ActivePopCollision;
78 void onPassiveCollision( operation_id opId )
80 if ( opId == treiber_stack::op_push )
81 ++m_PassivePushCollision;
83 ++m_PassivePopCollision;
85 void onEliminationFailed() { ++m_EliminationFailed;}
89 /// Empty (no overhead) stack statistics. Support interface like treiber_stack::stat
97 void onActiveCollision( operation_id ) {}
98 void onPassiveCollision( operation_id ) {}
99 void onEliminationFailed() {}
106 template <bool EnableElimination, typename T, typename Traits>
107 class elimination_backoff;
109 template <typename T, typename Traits>
110 class elimination_backoff<false, T, Traits>
112 typedef typename Traits::back_off back_off;
116 elimination_backoff()
119 elimination_backoff( size_t )
127 template <typename Stat>
128 bool backoff(treiber_stack::operation< T >&, Stat& )
135 template <typename T, typename Traits>
136 class elimination_backoff<true, T, Traits>
138 typedef typename Traits::back_off back_off;
140 /// Back-off for elimination (usually delay)
141 typedef typename Traits::elimination_backoff elimination_backoff_type;
142 /// Lock type used in elimination back-off
143 typedef typename Traits::lock_type elimination_lock_type;
144 /// Random engine used in elimination back-off
145 typedef typename Traits::random_engine elimination_random_engine;
147 /// Per-thread elimination record
148 typedef cds::algo::elimination::record elimination_rec;
150 /// Collision array record
151 struct collision_array_record {
152 elimination_rec * pRec;
153 elimination_lock_type lock;
156 /// Collision array used in elimination-backoff; each item is optimized for cache-line size
157 typedef typename Traits::buffer::template rebind<
158 typename cds::details::type_padding<collision_array_record, cds::c_nCacheLineSize >::type
159 >::other collision_array;
161 /// Operation descriptor used in elimination back-off
162 typedef treiber_stack::operation< T > operation_desc;
164 # if !(defined(CDS_CXX11_LAMBDA_SUPPORT) && !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10))
165 struct bkoff_predicate {
166 operation_desc * pOp;
167 bkoff_predicate( operation_desc * p ): pOp(p) {}
168 bool operator()() { return pOp->nStatus.load( CDS_ATOMIC::memory_order_acquire ) != op_busy; }
172 /// Elimination back-off data
173 struct elimination_data {
174 elimination_random_engine randEngine; ///< random engine
175 collision_array collisions; ///< collision array
179 //TODO: check Traits::buffer must be static!
181 elimination_data( size_t nCollisionCapacity )
182 : collisions( nCollisionCapacity )
186 elimination_data m_Elimination;
188 enum operation_status {
194 typedef cds::lock::scoped_lock< elimination_lock_type > slot_scoped_lock;
197 elimination_backoff()
199 m_Elimination.collisions.zeroize();
202 elimination_backoff( size_t nCollisionCapacity )
203 : m_Elimination( nCollisionCapacity )
205 m_Elimination.collisions.zeroize();
211 template <typename Stat>
212 bool backoff( operation_desc& op, Stat& stat )
214 elimination_backoff_type bkoff;
215 op.nStatus.store( op_busy, CDS_ATOMIC::memory_order_relaxed );
217 elimination_rec * myRec = cds::algo::elimination::init_record( op );
219 collision_array_record& slot = m_Elimination.collisions[m_Elimination.randEngine() % m_Elimination.collisions.capacity()];
222 elimination_rec * himRec = slot.pRec;
224 operation_desc * himOp = static_cast<operation_desc *>( himRec->pOp );
226 if ( himOp->idOp != op.idOp ) {
227 if ( op.idOp == treiber_stack::op_push )
228 himOp->pVal = op.pVal;
230 op.pVal = himOp->pVal;
234 himOp->nStatus.store( op_collided, CDS_ATOMIC::memory_order_release );
235 cds::algo::elimination::clear_record();
236 stat.onActiveCollision( op.idOp );
239 himOp->nStatus.store( op_free, CDS_ATOMIC::memory_order_release );
245 // Wait for colliding operation
246 # if defined(CDS_CXX11_LAMBDA_SUPPORT) && !(CDS_COMPILER == CDS_COMPILER_MSVC && CDS_COMPILER_VERSION == CDS_COMPILER_MSVC10)
247 // MSVC++ 2010 compiler error C2065: 'op_busy' : undeclared identifier
248 bkoff( [&op]() -> bool { return op.nStatus.load( CDS_ATOMIC::memory_order_acquire ) != op_busy; } );
250 // Local structs is not supported by old compilers (for example, GCC 4.3)
251 //struct bkoff_predicate {
252 // operation_desc * pOp;
253 // bkoff_predicate( operation_desc * p ): pOp(p) {}
254 // bool operator()() { return pOp->nStatus.load( CDS_ATOMIC::memory_order_acquire ) != op_busy; }
256 bkoff( bkoff_predicate(&op) );
260 slot_scoped_lock l( slot.lock );
261 if ( slot.pRec == myRec )
265 bool bCollided = op.nStatus.load( CDS_ATOMIC::memory_order_acquire ) == op_collided;
268 stat.onEliminationFailed();
270 stat.onPassiveCollision( op.idOp );
272 cds::algo::elimination::clear_record();
277 } // namespace details
279 } // namespace treiber_stack
282 /** @ingroup cds_intrusive_stack
283 Intrusive implementation of well-known Treiber's stack algorithm:
284 - R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
286 \ref cds_elimination_description "Elimination back-off technique" can be used optionally.
287 The idea of elimination algorithm is taken from:
288 - [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm"
290 The elimination algorithm uses a single elimination array as a back-off schema
291 on a shared lock-free stack. If the threads fail on the stack, they attempt to eliminate
292 on the array, and if they fail in eliminating, they attempt to access the stack again and so on.
294 @note Hendler's et al paper describes a lock-free implementation of elimination back-off which is quite complex.
295 The main difficulty is the managing life-time of elimination record.
296 Our implementation uses simplified lock-based (spin-based) approach which allows
297 the elimination record allocation on thread's stack.
298 This approach demonstrates sufficient performance under high load.
301 - \p GC - garbage collector type: gc::HP, gc::HRC, gc::PTB
302 - \p T - type to be inserted into the stack
303 - \p Options - options
306 - opt::hook - hook used. Possible values are: single_link::base_hook, single_link::member_hook, single_link::traits_hook.
307 If the option is not specified, <tt>single_link::base_hook<></tt> is used.
308 For Gidenstam's gc::HRC, only single_link::base_hook is supported.
309 - opt::back_off - back-off strategy used. If the option is not specified, the cds::backoff::Default is used.
310 - opt::disposer - the functor used for dispose removed items. Default is opt::v::empty_disposer. This option is used only
311 in \ref clear function.
312 - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link.
313 Note: for gc::HRC garbage collector, link checking policy is always selected as \ref opt::always_check_link.
314 - opt::memory_model - C++ memory ordering model. Can be opt::v::relaxed_ordering (relaxed memory model, the default)
315 or opt::v::sequential_consistent (sequentially consisnent memory model).
316 - opt::item_counter - the type of item counting feature. Default is \ref atomicity::empty_item_counter
317 - opt::stat - the type to gather internal statistics.
318 Possible option value are: \ref treiber_stack::stat, \ref treiber_stack::empty_stat (the default),
319 user-provided class that supports treiber_stack::stat interface.
320 - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p valse.
322 If elimination back-off is enabled (\p %cds::opt::enable_elimination< true >) additional options can be specified:
323 - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
324 The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
325 The size should be selected empirically for your application and hardware, there are no common rules for that.
326 Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
327 - opt::random_engine - a random engine to generate a random position in elimination array.
328 Default is opt::v::c_rand.
329 - opt::elimination_backoff - back-off strategy to wait for elimination, default is cds::backoff::delay<>
330 - opt::lock_type - a lock type used in elimination back-off, default is cds::lock::Spin.
332 Garbage collecting schema \p GC must be consistent with the single_link::node GC.
334 Be careful when you want destroy an item popped, see \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
336 @anchor cds_intrusive_TreiberStack_examples
339 Example of how to use \p single_link::base_hook.
340 Your class that objects will be pushed on \p %TreiberStack should be based on \p single_link::node class
342 #include <cds/intrusive/stack/treiber_stack.h>
343 #include <cds/gc/hp.h>
345 namespace ci = cds::intrusive;
346 typedef cds::gc::HP gc;
348 struct myData: public ci::single_link::node< gc >
354 typedef ci::TreiberStack< gc,
356 ci::opt::hook< ci::single_link::base_hook< gc > >
359 // Stack with elimination back-off enabled
360 typedef ci::TreiberStack< gc,
362 ci::opt::hook< ci::single_link::base_hook< gc > >,
363 cds::opt::enable_elimination<true>
364 > elimination_stack_t;
367 Example of how to use \p base_hook with different tags.
369 #include <cds/intrusive/stack/treiber_stack.h>
370 #include <cds/gc/hp.h>
372 namespace ci = cds::intrusive;
373 typedef cds::gc::HP gc;
375 // It is not necessary to declare complete type for tags
380 : public ci::single_link::node< gc, tag1 >
381 , public ci::single_link::node< gc, tag2 >
386 typedef ci::TreiberStack< gc, myData, ci::opt::hook< ci::single_link::base_hook< gc, tag1 > > stack1_t;
387 typedef ci::TreiberStack< gc, myData, ci::opt::hook< ci::single_link::base_hook< gc, tag2 > > stack2_t;
389 // You may add myData objects in the objects of type stack1_t and stack2_t independently
397 s2.push( i1 ) ; // i1 is now contained in s1 and s2.
401 p = s1.pop() ; // pop i1 from s1
402 p = s1.pop() ; // p == NULL, s1 is empty
403 p = s2.pop() ; // pop i1 from s2
404 p = s2.pop() ; // pop i2 from s2
405 p = s2.pop() ; // p == NULL, s2 is empty
409 Example of how to use \p member_hook.
410 Your class that will be pushed on \p %TreiberStack should have a member of type \p single_link::node
412 #include <cds/intrusive/stack/treiber_stack.h>
413 #include <cds/gc/hp.h>
414 #include <stddef.h> // offsetof macro
416 namespace ci = cds::intrusive;
417 typedef cds::gc::HP gc;
422 ci::single_link::node< gc > member_hook_;
426 typedef ci::TreiberStack< gc, myData,
428 ci::single_link::member_hook< offsetof(myData, member_hook_),
434 template <typename GC, typename T, CDS_DECL_OPTIONS13>
438 struct default_options
440 typedef cds::backoff::Default back_off;
441 typedef single_link::base_hook<> hook;
442 typedef opt::v::empty_disposer disposer;
443 typedef atomicity::empty_item_counter item_counter;
444 typedef opt::v::relaxed_ordering memory_model;
445 typedef treiber_stack::empty_stat stat;
446 static CDS_CONSTEXPR_CONST opt::link_check_type link_checker = opt::debug_check_link;
448 // Elimination back-off options
449 static CDS_CONSTEXPR_CONST bool enable_elimination = false;
450 typedef cds::backoff::delay<> elimination_backoff;
451 typedef opt::v::static_buffer< int, 4 > buffer;
452 typedef opt::v::c_rand random_engine;
453 typedef cds::lock::Spin lock_type;
459 typedef typename opt::make_options<
460 typename cds::opt::find_type_traits< default_options, CDS_OPTIONS13 >::type
466 /// Rebind template arguments
467 template <typename GC2, typename T2, CDS_DECL_OTHER_OPTIONS13>
469 typedef TreiberStack< GC2, T2, CDS_OTHER_OPTIONS13> other ; ///< Rebinding result
473 typedef T value_type ; ///< type of value stored in the stack
474 typedef typename options::hook hook ; ///< hook type
475 typedef typename hook::node_type node_type ; ///< node type
476 typedef typename options::disposer disposer ; ///< disposer used
477 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ; ///< node traits
478 typedef typename single_link::get_link_checker< node_type, options::link_checker >::type link_checker ; ///< link checker
479 typedef typename options::memory_model memory_model ; ///< Memory ordering. See cds::opt::memory_model option
480 typedef typename options::item_counter item_counter ; ///< Item counting policy used
481 typedef typename options::stat stat ; ///< Internal statistics policy used
483 typedef GC gc ; ///< Garbage collector
484 typedef typename options::back_off back_off ; ///< back-off strategy
486 public: // related to elimination back-off
488 /// Elimination back-off is enabled or not
489 static CDS_CONSTEXPR_CONST bool enable_elimination = options::enable_elimination;
490 /// back-off strategy used to wait for elimination
491 typedef typename options::elimination_backoff elimination_backoff_type;
492 /// Lock type used in elimination back-off
493 typedef typename options::lock_type elimination_lock_type;
494 /// Random engine used in elimination back-off
495 typedef typename options::random_engine elimination_random_engine;
499 typename node_type::atomic_node_ptr m_Top ; ///< Top of the stack
500 item_counter m_ItemCounter ; ///< Item counter
501 stat m_stat ; ///< Internal statistics
504 treiber_stack::details::elimination_backoff<enable_elimination, value_type, options> m_Backoff;
506 typedef intrusive::node_to_value<TreiberStack> node_to_value;
507 typedef treiber_stack::operation< value_type > operation_desc;
512 void clear_links( node_type * pNode ) CDS_NOEXCEPT
514 pNode->m_pNext.store( nullptr, memory_model::memory_order_relaxed );
517 template <bool EnableElimination>
518 struct elimination_backoff_impl;
522 // GC and node_type::gc must be the same
523 static_assert(( std::is_same<gc, typename node_type::gc>::value ), "GC and node_type::gc must be the same");
525 // For cds::gc::HRC, only base_hook is allowed
528 std::is_same<gc, cds::gc::HRC>::value,
529 std::is_same< typename hook::hook_type, opt::base_hook_tag >,
532 ), "For cds::gc::HRC, only base_hook is allowed");
534 static_assert( (!enable_elimination || std::is_same<typename elimination_random_engine::result_type, unsigned int>::value),
535 "Random engine result type must be unsigned int" );
541 /// Constructs empty stack
548 /// Constructs empty stack and initializes elimination back-off data
550 This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
551 \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
552 \p nCollisionCapacity parameter specifies the capacity of collision array.
554 TreiberStack( size_t nCollisionCapacity )
556 , m_Backoff( nCollisionCapacity )
561 /// Destructor calls \ref cds_intrusive_TreiberStack_clear "clear" member function
567 /// Push the item \p val on the stack
569 No copying is made since it is intrusive stack.
571 bool push( value_type& val )
573 node_type * pNew = node_traits::to_node_ptr( val );
574 link_checker::is_empty( pNew );
579 if ( enable_elimination ) {
580 op.idOp = treiber_stack::op_push;
584 node_type * t = m_Top.load(memory_model::memory_order_relaxed);
586 pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
587 if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, CDS_ATOMIC::memory_order_relaxed )) { // #1 sync-with #2
594 if ( m_Backoff.backoff( op, m_stat ))
599 /// Pop an item from the stack
601 If stack is empty, returns \p NULL.
602 The disposer is <b>not</b> called for popped item.
603 See \ref cds_intrusive_item_destroying "Destroying items of intrusive containers".
608 typename gc::Guard guard;
611 if ( enable_elimination ) {
612 op.idOp = treiber_stack::op_pop;
616 node_type * t = guard.protect( m_Top, node_to_value() );
618 return nullptr; // stack is empty
620 node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed);
621 if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, CDS_ATOMIC::memory_order_relaxed )) { // #2
625 return node_traits::to_value_ptr( *t );
629 if ( m_Backoff.backoff( op, m_stat )) {
630 // may return NULL if stack is empty
636 /// Check if stack is empty
639 // http://www.manning-sandbox.com/thread.jspa?threadID=46245&tstart=0
640 return m_Top.load( memory_model::memory_order_relaxed ) == nullptr;
644 /** @anchor cds_intrusive_TreiberStack_clear
645 For each removed item the disposer is called.
648 It is possible that after <tt>clear()</tt> the <tt>empty()</tt> returns \p false
649 if some other thread pushes an item into the stack during \p clear works
656 pTop = m_Top.load( memory_model::memory_order_relaxed );
657 if ( pTop == nullptr )
659 if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acq_rel, CDS_ATOMIC::memory_order_relaxed ) ) { // sync-with #1 and #2
660 m_ItemCounter.reset();
667 node_type * p = pTop;
668 pTop = p->m_pNext.load(memory_model::memory_order_relaxed);
670 gc::template retire<disposer>( node_traits::to_value_ptr( *p ) );
674 /// Returns stack's item count
676 The value returned depends on opt::item_counter option. For atomicity::empty_item_counter,
677 this function always returns 0.
679 <b>Warning</b>: even if you use real item counter and it returns 0, this fact is not mean that the stack
680 is empty. To check emptyness use \ref empty() method.
684 return m_ItemCounter.value();
687 /// Returns reference to internal statistics
688 stat const& statistics() const
694 }} // namespace cds::intrusive
696 #endif // #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H