TSan exam:

[libcds.git] / cds / intrusive / treiber_stack.h

diff --git a/cds/intrusive/treiber_stack.h b/cds/intrusive/treiber_stack.h
index d4ee4e3ba6ea9cf1b404f4b700a60480125e90ad..74ca175cd168e6a6d07059b290efebaf1069dd27 100644 (file)
--- a/cds/intrusive/treiber_stack.h
+++ b/cds/intrusive/treiber_stack.h
@@ -1,7 +1,7 @@
 //$$CDS-header$$
 
-#ifndef __CDS_INTRUSIVE_TREIBER_STACK_H
-#define __CDS_INTRUSIVE_TREIBER_STACK_H
+#ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H
+#define CDSLIB_INTRUSIVE_TREIBER_STACK_H
 
 #include <type_traits>
 #include <mutex>        // unique_lock
@@ -77,8 +77,9 @@ namespace cds { namespace intrusive {
 
             operation()
                 : pVal( nullptr )
-                , nStatus(0)
-            {}
+            {
+                nStatus.store( 0 /*op_free*/, atomics::memory_order_release );
+            }
         };
         //@endcond
 
@@ -267,7 +268,23 @@ namespace cds { namespace intrusive {
             {
                 typedef typename Traits::back_off   back_off;
 
-                back_off    m_bkoff;
+                struct wrapper
+                {
+                    back_off m_bkoff;
+
+                    void reset()
+                    {
+                        m_bkoff.reset();
+                    }
+
+                    template <typename Stat>
+                    bool backoff( treiber_stack::operation< T >&, Stat& )
+                    {
+                        m_bkoff();
+                        return false;
+                    }
+                };
+
             public:
                 elimination_backoff()
                 {}
@@ -275,16 +292,10 @@ namespace cds { namespace intrusive {
                 elimination_backoff( size_t )
                 {}
 
-                void reset()
-                {
-                    m_bkoff.reset();
-                }
-
-                template <typename Stat>
-                bool backoff(treiber_stack::operation< T >&, Stat& )
+                typedef wrapper type;
+                type init()
                 {
-                    m_bkoff();
-                    return false;
+                    return wrapper();
                 }
             };
 
@@ -319,8 +330,8 @@ namespace cds { namespace intrusive {
 
                 /// Elimination back-off data
                 struct elimination_data {
-                    elimination_random_engine   randEngine; ///< random engine
-                    collision_array             collisions; ///< collision array
+                    mutable elimination_random_engine randEngine; ///< random engine
+                    collision_array                   collisions; ///< collision array
 
                     elimination_data()
                     {
@@ -341,6 +352,18 @@ namespace cds { namespace intrusive {
 
                 typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
 
+                template <bool Exp2 = collision_array::c_bExp2>
+                typename std::enable_if< Exp2, size_t >::type slot_index() const
+                {
+                    return m_Elimination.randEngine() & (m_Elimination.collisions.capacity() - 1);
+                }
+
+                template <bool Exp2 = collision_array::c_bExp2>
+                typename std::enable_if< !Exp2, size_t >::type slot_index() const
+                {
+                    return m_Elimination.randEngine() % m_Elimination.collisions.capacity();
+                }
+
             public:
                 elimination_backoff()
                 {
@@ -353,6 +376,13 @@ namespace cds { namespace intrusive {
                     m_Elimination.collisions.zeroize();
                 }
 
+                typedef elimination_backoff& type;
+
+                type init()
+                {
+                    return *this;
+                }
+
                 void reset()
                 {}
 
@@ -360,11 +390,11 @@ namespace cds { namespace intrusive {
                 bool backoff( operation_desc& op, Stat& stat )
                 {
                     elimination_backoff_type bkoff;
-                    op.nStatus.store( op_busy, atomics::memory_order_relaxed );
+                    op.nStatus.store( op_busy, atomics::memory_order_release );
 
                     elimination_rec * myRec = cds::algo::elimination::init_record( op );
 
-                    collision_array_record& slot = m_Elimination.collisions[m_Elimination.randEngine() % m_Elimination.collisions.capacity()];
+                    collision_array_record& slot = m_Elimination.collisions[ slot_index() ];
                     {
                         slot.lock.lock();
                         elimination_rec * himRec = slot.pRec;
@@ -377,9 +407,9 @@ namespace cds { namespace intrusive {
                                 else
                                     op.pVal = himOp->pVal;
                                 slot.pRec = nullptr;
+                                himOp->nStatus.store( op_collided, atomics::memory_order_release );
                                 slot.lock.unlock();
 
-                                himOp->nStatus.store( op_collided, atomics::memory_order_release );
                                 cds::algo::elimination::clear_record();
                                 stat.onActiveCollision( op.idOp );
                                 return true;
@@ -617,7 +647,8 @@ namespace cds { namespace intrusive {
         stat                m_stat;                 ///< Internal statistics
 
         //@cond
-        treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> m_Backoff;
+        typedef treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> elimination_backoff;
+        elimination_backoff m_Backoff;
 
         typedef intrusive::node_to_value<TreiberStack>  node_to_value;
         typedef treiber_stack::operation< value_type >  operation_desc;
@@ -675,7 +706,7 @@ namespace cds { namespace intrusive {
             node_type * pNew = node_traits::to_node_ptr( val );
             link_checker::is_empty( pNew );
 
-            m_Backoff.reset();
+            typename elimination_backoff::type bkoff = m_Backoff.init();
 
             operation_desc op;
             if ( enable_elimination ) {
@@ -686,14 +717,14 @@ namespace cds { namespace intrusive {
             node_type * t = m_Top.load(memory_model::memory_order_relaxed);
             while ( true ) {
                 pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
-                if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) {     // #1 sync-with #2
+                if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
                     ++m_ItemCounter;
                     m_stat.onPush();
                     return true;
                 }
                 m_stat.onPushRace();
 
-                if ( m_Backoff.backoff( op, m_stat ))
+                if ( bkoff.backoff( op, m_stat ))
                     return true;
             }
         }
@@ -706,7 +737,7 @@ namespace cds { namespace intrusive {
         */
         value_type * pop()
         {
-            m_Backoff.reset();
+            typename elimination_backoff::type bkoff = m_Backoff.init();
             typename gc::Guard  guard;
 
             operation_desc op;
@@ -720,7 +751,7 @@ namespace cds { namespace intrusive {
                     return nullptr;    // stack is empty
 
                 node_type * pNext = t->m_pNext.load(memory_model::memory_order_relaxed);
-                if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {              // #2
+                if ( m_Top.compare_exchange_weak( t, pNext, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
                     clear_links( t );
                     --m_ItemCounter;
                     m_stat.onPop();
@@ -728,7 +759,7 @@ namespace cds { namespace intrusive {
                 }
 
                 m_stat.onPopRace();
-                if ( m_Backoff.backoff( op, m_stat )) {
+                if ( bkoff.backoff( op, m_stat )) {
                     // may return nullptr if stack is empty
                     return op.pVal;
                 }
@@ -738,7 +769,6 @@ namespace cds { namespace intrusive {
         /// Check if stack is empty
         bool empty() const
         {
-            // http://www.manning-sandbox.com/thread.jspa?threadID=46245&tstart=0
             return m_Top.load( memory_model::memory_order_relaxed ) == nullptr;
         }
 
@@ -757,7 +787,7 @@ namespace cds { namespace intrusive {
                 pTop = m_Top.load( memory_model::memory_order_relaxed );
                 if ( pTop == nullptr )
                     return;
-                if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ) ) {    // sync-with #1 and #2
+                if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
                     m_ItemCounter.reset();
                     break;
                 }
@@ -794,4 +824,4 @@ namespace cds { namespace intrusive {
 
 }} // namespace cds::intrusive
 
-#endif  // #ifndef __CDS_INTRUSIVE_TREIBER_STACK_H
+#endif  // #ifndef CDSLIB_INTRUSIVE_TREIBER_STACK_H