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

diff --git a/cds/container/details/make_skip_list_map.h b/cds/container/details/make_skip_list_map.h
index 8e456fe07bbded2621616c223e076f875240dbfc..c4941393bd36dd736263a563e31491d708787c2c 100644 (file)
--- a/cds/container/details/make_skip_list_map.h
+++ b/cds/container/details/make_skip_list_map.h
@@ -57,22 +57,15 @@ namespace cds { namespace container { namespace details {
             //atomic_marked_ptr m_arrTower[] ;  // allocated together with node_type in single memory block
 
             template <typename Q>
             //atomic_marked_ptr m_arrTower[] ;  // allocated together with node_type in single memory block
 
             template <typename Q>

-            node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q const& key )
-                : m_Value( std::make_pair( key, mapped_type()))
-            {
-                init_tower( nHeight, pTower );
-            }
-
-            template <typename Q, typename U>
-            node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q const& key, U const& val )
-                : m_Value( std::make_pair( key, val ))
+            node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q&& key )
+                : m_Value( std::make_pair( std::forward<Q>( key ), mapped_type()))

             {
                 init_tower( nHeight, pTower );
             }
 
             template <typename Q, typename... Args>
             node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q&& key, Args&&... args )
             {
                 init_tower( nHeight, pTower );
             }
 
             template <typename Q, typename... Args>
             node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q&& key, Args&&... args )

-                : m_Value( std::forward<Q>(key), std::move( mapped_type( std::forward<Args>(args)... )))
+                : m_Value( std::forward<Q>(key), mapped_type( std::forward<Args>(args)... ))

             {
                 init_tower( nHeight, pTower );
             }
             {
                 init_tower( nHeight, pTower );
             }

diff --git a/cds/container/details/make_skip_list_set.h b/cds/container/details/make_skip_list_set.h
index e63bbe83fb14c86bdac2bcc97c0778896f7fa956..658c523373477eee619fe52095966fb0e4c1b3f0 100644 (file)
--- a/cds/container/details/make_skip_list_set.h
+++ b/cds/container/details/make_skip_list_set.h
@@ -55,30 +55,32 @@ namespace cds { namespace container { namespace details {
             //atomic_marked_ptr m_arrTower[] ;  // allocated together with node_type in single memory block
 
             template <typename Q>
             //atomic_marked_ptr m_arrTower[] ;  // allocated together with node_type in single memory block
 
             template <typename Q>

-            node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q const& v )
-                : m_Value(v)
+            node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q&& v )
+                : m_Value( std::forward<Q>( v ))

             {
             {

-                if ( nHeight > 1 ) {
-                    // TSan: make_tower() issues atomic_thread_fence( release )
-                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
-                    new (pTower) atomic_marked_ptr[ nHeight - 1 ];
-                    base_class::make_tower( nHeight, pTower );
-                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
-                }
+                init_tower( nHeight, pTower );

             }
 
             template <typename Q, typename... Args>
             node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q&& q, Args&&... args )
                 : m_Value( std::forward<Q>(q), std::forward<Args>(args)... )
             }
 
             template <typename Q, typename... Args>
             node_type( unsigned int nHeight, atomic_marked_ptr * pTower, Q&& q, Args&&... args )
                 : m_Value( std::forward<Q>(q), std::forward<Args>(args)... )

+            {
+                init_tower( nHeight, pTower );
+            }
+
+            node_type() = delete;
+
+        private:
+            void init_tower( unsigned nHeight, atomic_marked_ptr* pTower )

             {
                 if ( nHeight > 1 ) {
             {
                 if ( nHeight > 1 ) {

-                    new (pTower) atomic_marked_ptr[ nHeight - 1 ];
+                    // TSan: make_tower() issues atomic_thread_fence( release )
+                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
+                    new ( pTower ) atomic_marked_ptr[nHeight - 1];

                     base_class::make_tower( nHeight, pTower );
                     base_class::make_tower( nHeight, pTower );

+                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;

                 }
             }
                 }
             }

-
-        private:
-            node_type() ;   // no default ctor

         };
 
         typedef skip_list::details::node_allocator< node_type, traits> node_allocator;
         };
 
         typedef skip_list::details::node_allocator< node_type, traits> node_allocator;

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;
             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:
             //@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:
 
         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 );
             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;
                 );
 
                 m_arrNext = nextTower;


@@ -160,6 +162,16 @@ namespace cds { namespace intrusive {
                     && m_arrNext == nullptr
                     && m_nHeight <= 1;
             }
                     && 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
         };
 
             //@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_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 )
 
             //@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 onExtractMaxSuccess()      { ++m_nExtractMaxSuccess; }
             void onExtractMaxFailed()       { ++m_nExtractMaxFailed;  }
             void onExtractMaxRetry()        { ++m_nExtractMaxRetries; }

+            void onNodeHandOffFailed()      { ++m_nNodeHandOffFailed; }

 
             //@endcond
         };
 
             //@endcond
         };


@@ -495,7 +509,7 @@ namespace cds { namespace intrusive {
             void onExtractMaxSuccess()      const {}
             void onExtractMaxFailed()       const {}
             void onExtractMaxRetry()        const {}
             void onExtractMaxSuccess()      const {}
             void onExtractMaxFailed()       const {}
             void onExtractMaxRetry()        const {}

-
+            void onNodeHandOffFailed()      const {}

             //@endcond
         };
 
             //@endcond
         };
 

diff --git a/cds/intrusive/impl/skip_list.h b/cds/intrusive/impl/skip_list.h
index 4f7d1eaf3b9e03072ac54dae47f460c0bda2d5ef..c72c5e8068811b9db46cf2d37affe0c46bd8c0fe 100644 (file)
--- a/cds/intrusive/impl/skip_list.h
+++ b/cds/intrusive/impl/skip_list.h
@@ -394,7 +394,8 @@ namespace cds { namespace intrusive {
         // c_nMaxHeight * 2 - pPred/pSucc guards
         // + 1 - for erase, unlink
         // + 1 - for clear
         // c_nMaxHeight * 2 - pPred/pSucc guards
         // + 1 - for erase, unlink
         // + 1 - for clear

-        static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 2; ///< Count of hazard pointer required for the skip-list
+        // + 1 - for help_remove
+        static size_t const c_nHazardPtrCount = c_nMaxHeight * 2 + 3; ///< Count of hazard pointer required for the skip-list

 
     protected:
         typedef typename node_type::atomic_marked_ptr   atomic_node_ptr;   ///< Atomic marked node pointer
 
     protected:
         typedef typename node_type::atomic_marked_ptr   atomic_node_ptr;   ///< Atomic marked node pointer


@@ -639,7 +640,7 @@ namespace cds { namespace intrusive {
             node_type * pNode = node_traits::to_node_ptr( val );
             scoped_node_ptr scp( pNode );
             unsigned int nHeight = pNode->height();
             node_type * pNode = node_traits::to_node_ptr( val );
             scoped_node_ptr scp( pNode );
             unsigned int nHeight = pNode->height();

-            bool bTowerOk = pNode->has_tower(); // nHeight > 1 && pNode->get_tower() != nullptr;
+            bool bTowerOk = pNode->has_tower();

             bool bTowerMade = false;
 
             position pos;
             bool bTowerMade = false;
 
             position pos;


@@ -1147,6 +1148,32 @@ namespace cds { namespace intrusive {
             disposer()( pVal );
         }
 
             disposer()( pVal );
         }
 

+        void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur, marked_node_ptr pSucc )
+        {
+            typename gc::Guard succ_guard;
+            marked_node_ptr succ = succ_guard.protect( pCur->next( nLevel ), gc_protect );
+
+            typename node_type::state state = node_type::clean;
+            if ( succ == pSucc && ( succ.ptr() == nullptr ||
+                succ.ptr()->set_state( state, node_type::hand_off, memory_model::memory_order_acquire )))
+            {
+                marked_node_ptr p( pCur.ptr() );
+                if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( succ.ptr()),
+                    memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
+                {
+                    if ( nLevel == 0 ) {
+                        gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
+                        m_Stat.onEraseWhileFind();
+                    }
+                }
+
+                if ( succ.ptr() )
+                    succ.ptr()->clear_state( memory_model::memory_order_release );
+            }
+            else
+                m_Stat.onNodeHandOffFailed();
+        }
+

         template <typename Q, typename Compare >
         bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
         {
         template <typename Q, typename Compare >
         bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound )
         {


@@ -1183,16 +1210,9 @@ namespace cds { namespace intrusive {
                         goto retry;
 
                     if ( pSucc.bits() ) {
                         goto retry;
 
                     if ( pSucc.bits() ) {

-                        // pCur is marked, i.e. logically deleted.
-                        marked_node_ptr p( pCur.ptr() );
-                        if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
-                            memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
-                        {
-                            if ( nLevel == 0 ) {
-                                gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
-                                m_Stat.onEraseWhileFind();
-                            }
-                        }
+                        // pCur is marked, i.e. logically deleted
+                        // try to help deleting pCur if pSucc is not being deleted
+                        help_remove( nLevel, pPred, pCur, pSucc );

                         goto retry;
                     }
                     else {
                         goto retry;
                     }
                     else {


@@ -1252,15 +1272,8 @@ namespace cds { namespace intrusive {
 
                     if ( pSucc.bits() ) {
                         // pCur is marked, i.e. logically deleted.
 
                     if ( pSucc.bits() ) {
                         // pCur is marked, i.e. logically deleted.

-                        marked_node_ptr p( pCur.ptr() );
-                        if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
-                            memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
-                        {
-                            if ( nLevel == 0 ) {
-                                gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
-                                m_Stat.onEraseWhileFind();
-                            }
-                        }
+                        // try to help deleting pCur if pSucc is not being deleted
+                        help_remove( nLevel, pPred, pCur, pSucc );

                         goto retry;
                     }
                 }
                         goto retry;
                     }
                 }


@@ -1308,15 +1321,8 @@ namespace cds { namespace intrusive {
 
                     if ( pSucc.bits() ) {
                         // pCur is marked, i.e. logically deleted.
 
                     if ( pSucc.bits() ) {
                         // pCur is marked, i.e. logically deleted.

-                        marked_node_ptr p( pCur.ptr() );
-                        if ( pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ),
-                            memory_model::memory_order_acquire, atomics::memory_order_relaxed ) )
-                        {
-                            if ( nLevel == 0 ) {
-                                gc::retire( node_traits::to_value_ptr( pCur.ptr() ), dispose_node );
-                                m_Stat.onEraseWhileFind();
-                            }
-                        }
+                        // try to help deleting pCur if pSucc is not being deleted
+                        help_remove( nLevel, pPred, pCur, pSucc );

                         goto retry;
                     }
                     else {
                         goto retry;
                     }
                     else {


@@ -1346,11 +1352,21 @@ namespace cds { namespace intrusive {
 
             // Insert at level 0
             {
 
             // Insert at level 0
             {

-                marked_node_ptr p( pos.pSucc[0] );
+                node_type* succ = pos.pSucc[0];
+                typename node_type::state state = node_type::clean;
+                if ( succ != nullptr && !succ->set_state( state, node_type::hand_off, memory_model::memory_order_acquire ) )
+                    return false;
+
+                marked_node_ptr p( succ );

                 pNode->next( 0 ).store( p, memory_model::memory_order_release );
                 pNode->next( 0 ).store( p, memory_model::memory_order_release );

-                if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) )
+                if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) ) {
+                    if ( succ )
+                        succ->clear_state( memory_model::memory_order_release );

                     return false;
                     return false;

+                }

 
 

+                if ( succ )
+                    succ->clear_state( memory_model::memory_order_release );

                 f( val );
             }
 
                 f( val );
             }
 


@@ -1358,17 +1374,30 @@ namespace cds { namespace intrusive {
             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
                 marked_node_ptr p;
                 while ( true ) {
             for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
                 marked_node_ptr p;
                 while ( true ) {

-                    marked_node_ptr q( pos.pSucc[nLevel] );
-                    if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed ) ) {
-                        // pNode has been marked as removed while we are inserting it
-                        // Stop inserting
-                        assert( p.bits() );
-                        m_Stat.onLogicDeleteWhileInsert();
-                        return true;
+                    typename node_type::state state = node_type::clean;
+                    node_type* succ = pos.pSucc[nLevel];
+                    if ( succ == nullptr ||
+                        succ->set_state( state, node_type::hand_off, memory_model::memory_order_acquire ) ) 
+                    {
+                        marked_node_ptr q( succ );
+                        if ( !pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
+                            // pNode has been marked as removed while we are inserting it
+                            // Stop inserting
+                            if ( succ )
+                                succ->clear_state( memory_model::memory_order_release );
+                            assert( p.bits() );
+                            m_Stat.onLogicDeleteWhileInsert();
+                            return true;
+                        }
+
+                        p = q;
+                        bool const result = pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( q, marked_node_ptr( pNode ),
+                            memory_model::memory_order_release, atomics::memory_order_relaxed );
+                        if ( succ )
+                            succ->clear_state( memory_model::memory_order_release );
+                        if ( result )
+                            break;

                     }
                     }

-                    p = q;
-                    if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( q, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed ) )
-                        break;

 
                     // Renew insert position
                     m_Stat.onRenewInsertPosition();
 
                     // Renew insert position
                     m_Stat.onRenewInsertPosition();


@@ -1387,6 +1416,17 @@ namespace cds { namespace intrusive {
         {
             assert( pDel != nullptr );
 
         {
             assert( pDel != nullptr );
 

+            // set "removed" node state
+            {
+                back_off bkoff;
+                typename node_type::state state = node_type::clean;
+                while ( !( pDel->set_state( state, node_type::removed, memory_model::memory_order_release )
+                    || state == node_type::removed ))
+                {
+                    bkoff();
+                }
+            }
+

             marked_node_ptr pSucc;
 
             // logical deletion (marking)
             marked_node_ptr pSucc;
 
             // logical deletion (marking)


@@ -1574,7 +1614,7 @@ namespace cds { namespace intrusive {
             position pos;
 
             guarded_ptr gp;
             position pos;
 
             guarded_ptr gp;

-            for ( ;;) {
+            for (;;) {

                 if ( !find_position( val, pos, cmp, false ) ) {
                     m_Stat.onExtractFailed();
                     return guarded_ptr();
                 if ( !find_position( val, pos, cmp, false ) ) {
                     m_Stat.onExtractFailed();
                     return guarded_ptr();

diff --git a/test/include/cds_test/stat_skiplist_out.h b/test/include/cds_test/stat_skiplist_out.h
index 8e5b22e4d4576a4027d0adc80c269a9ad3d8b050..66ecdaebea49dcd007a871797e46b60b260979a0 100644 (file)
--- a/test/include/cds_test/stat_skiplist_out.h
+++ b/test/include/cds_test/stat_skiplist_out.h
@@ -81,7 +81,8 @@ namespace cds_test {
             << CDSSTRESS_STAT_OUT( s, m_nFastExtract )
             << CDSSTRESS_STAT_OUT( s, m_nSlowExtract )
             << CDSSTRESS_STAT_OUT( s, m_nEraseWhileFind )
             << CDSSTRESS_STAT_OUT( s, m_nFastExtract )
             << CDSSTRESS_STAT_OUT( s, m_nSlowExtract )
             << CDSSTRESS_STAT_OUT( s, m_nEraseWhileFind )

-            << CDSSTRESS_STAT_OUT( s, m_nExtractWhileFind );
+            << CDSSTRESS_STAT_OUT( s, m_nExtractWhileFind )
+            << CDSSTRESS_STAT_OUT( s, m_nNodeHandOffFailed );

     }
 
 } // namespace cds_test
     }
 
 } // namespace cds_test