Fixed use-after-free bug in SkipList<HP>

[libcds.git] / cds / intrusive / details / skip_list_base.h

diff --git a/cds/intrusive/details/skip_list_base.h b/cds/intrusive/details/skip_list_base.h
index 00ddad257df6a99cdcbffe64497f0cd10fccecba..eb61006afd4c266b129fcef2c1f0964e82b95769 100644 (file)
--- a/cds/intrusive/details/skip_list_base.h
+++ b/cds/intrusive/details/skip_list_base.h
@@ -62,27 +62,29 @@ namespace cds { namespace intrusive {
             typedef typename gc::template atomic_marked_ptr< marked_ptr>  atomic_marked_ptr; ///< atomic marked pointer specific for GC
             //@cond
             typedef atomic_marked_ptr tower_item_type;
+
+            enum state {
+                clean,      // initial state
+                removed,    // final state
+                hand_off    // temp state
+            };
             //@endcond
 
         protected:
-            atomic_marked_ptr       m_pNext;   ///< Next item in bottom-list (list at level 0)
-            unsigned int            m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
-            atomic_marked_ptr *     m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
+            //@cond
+            atomic_marked_ptr           m_pNext{ nullptr };     ///< Next item in bottom-list (list at level 0)
+            unsigned int                m_nHeight{ 1 };         ///< Node height (size of \p m_arrNext array). For node at level 0 the height is 1.
+            atomic_marked_ptr *         m_arrNext{ nullptr };   ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
+            atomics::atomic< state >    m_state{ clean };
+            //@endcond
 
         public:
-            /// Constructs a node of height 1 (a bottom-list node)
-            node()
-                : m_pNext( nullptr )
-                , m_nHeight(1)
-                , m_arrNext( nullptr )
-            {}
-
-            /// Constructs a node of height \p nHeight
+            /// Constructs a node's tower of height \p nHeight
             void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower )
             {
                 assert( nHeight > 0 );
-                assert( (nHeight == 1 && nextTower == nullptr)  // bottom-list node
-                        || (nHeight > 1 && nextTower != nullptr)   // node at level of more than 0
+                assert( (nHeight == 1 && nextTower == nullptr)      // bottom-list node
+                        || (nHeight > 1 && nextTower != nullptr)    // node at level of more than 0
                 );
 
                 m_arrNext = nextTower;
@@ -160,6 +162,16 @@ namespace cds { namespace intrusive {
                     && m_arrNext == nullptr
                     && m_nHeight <= 1;
             }
+
+            bool set_state( state& cur_state, state new_state, atomics::memory_order order )
+            {
+                return m_state.compare_exchange_strong( cur_state, new_state, order, atomics::memory_order_relaxed );
+            }
+
+            void clear_state( atomics::memory_order order )
+            {
+                m_state.store( clean, order );
+            }
             //@endcond
         };
 
@@ -409,6 +421,7 @@ namespace cds { namespace intrusive {
             event_counter   m_nExtractMaxRetries    ; ///< Count of retries of \p extract_max call
             event_counter   m_nEraseWhileFind       ; ///< Count of erased item while searching
             event_counter   m_nExtractWhileFind     ; ///< Count of extracted item while searching (RCU only)
+            event_counter   m_nNodeHandOffFailed    ; ///< Cannot set "hand-off" node state
 
             //@cond
             void onAddNode( unsigned int nHeight )
@@ -454,6 +467,7 @@ namespace cds { namespace intrusive {
             void onExtractMaxSuccess()      { ++m_nExtractMaxSuccess; }
             void onExtractMaxFailed()       { ++m_nExtractMaxFailed;  }
             void onExtractMaxRetry()        { ++m_nExtractMaxRetries; }
+            void onNodeHandOffFailed()      { ++m_nNodeHandOffFailed; }
 
             //@endcond
         };
@@ -495,7 +509,7 @@ namespace cds { namespace intrusive {
             void onExtractMaxSuccess()      const {}
             void onExtractMaxFailed()       const {}
             void onExtractMaxRetry()        const {}
-
+            void onNodeHandOffFailed()      const {}
             //@endcond
         };