From: khizmax Date: Mon, 2 Jan 2017 09:17:35 +0000 (+0300) Subject: SkipList: fixed infinite loop when one thread inserts a key and another remove the... X-Git-Tag: v2.2.0~9 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=83a75b81d1a6baac3d4441c5c1a6a67699659705 SkipList: fixed infinite loop when one thread inserts a key and another remove the same key --- diff --git a/cds/details/defs.h b/cds/details/defs.h index 34f3b499..d43bedbe 100644 --- a/cds/details/defs.h +++ b/cds/details/defs.h @@ -337,10 +337,12 @@ namespace cds {} // CDS_VERIFY: Debug - assert(_expr); Release - _expr #ifdef CDS_DEBUG -# define CDS_VERIFY( _expr ) assert( _expr ) +# define CDS_VERIFY( _expr ) assert( _expr ) +# define CDS_VERIFY_FALSE( _expr ) assert( !( _expr )) # define CDS_DEBUG_ONLY( _expr ) _expr #else # define CDS_VERIFY( _expr ) _expr +# define CDS_VERIFY_FALSE( _expr ) _expr # define CDS_DEBUG_ONLY( _expr ) #endif diff --git a/cds/intrusive/details/skip_list_base.h b/cds/intrusive/details/skip_list_base.h index e2174f53..00c5676f 100644 --- a/cds/intrusive/details/skip_list_base.h +++ b/cds/intrusive/details/skip_list_base.h @@ -92,7 +92,7 @@ namespace cds { namespace intrusive { m_arrNext = nextTower; m_nHeight = nHeight; - m_nUnlink.store( nHeight, atomics::memory_order_relaxed ); + m_nUnlink.store( nHeight, atomics::memory_order_release ); } //@cond @@ -408,7 +408,7 @@ namespace cds { namespace intrusive { event_counter m_nFindSlowFailed ; ///< Count of failed call of \p find and all derivatives (via slow-path) event_counter m_nRenewInsertPosition ; ///< Count of renewing position events while inserting event_counter m_nLogicDeleteWhileInsert; ///< Count of events "The node has been logically deleted while inserting" - event_counter m_nNotFoundWhileInsert ; ///< Count of events "Inserting node is not found" + event_counter m_nRemoveWhileInsert ; ///< Count of evnts "The node is removing while inserting" event_counter m_nFastErase ; ///< Fast erase event counter event_counter m_nFastExtract ; ///< Fast extract event counter event_counter m_nSlowErase ; ///< Slow erase event counter @@ -457,7 +457,7 @@ namespace cds { namespace intrusive { void onExtractWhileFind() { ++m_nExtractWhileFind ; } void onRenewInsertPosition() { ++m_nRenewInsertPosition; } void onLogicDeleteWhileInsert() { ++m_nLogicDeleteWhileInsert; } - void onNotFoundWhileInsert() { ++m_nNotFoundWhileInsert; } + void onRemoveWhileInsert() { ++m_nRemoveWhileInsert; } void onFastErase() { ++m_nFastErase; } void onFastExtract() { ++m_nFastExtract; } void onSlowErase() { ++m_nSlowErase; } @@ -499,7 +499,7 @@ namespace cds { namespace intrusive { void onExtractWhileFind() const {} void onRenewInsertPosition() const {} void onLogicDeleteWhileInsert() const {} - void onNotFoundWhileInsert() const {} + void onRemoveWhileInsert() const {} void onFastErase() const {} void onFastExtract() const {} void onSlowErase() const {} diff --git a/cds/intrusive/impl/skip_list.h b/cds/intrusive/impl/skip_list.h index ccab53ce..13eddcb8 100644 --- a/cds/intrusive/impl/skip_list.h +++ b/cds/intrusive/impl/skip_list.h @@ -1148,13 +1148,14 @@ namespace cds { namespace intrusive { disposer()( pVal ); } - void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur, marked_node_ptr pSucc ) + void help_remove( int nLevel, node_type* pPred, marked_node_ptr pCur ) { - marked_node_ptr p( pCur.ptr() ); - if ( pCur->is_upper_level( nLevel )) { + marked_node_ptr p( pCur.ptr() ); typename gc::Guard hp; - if ( hp.protect( pCur->next( nLevel ), gc_protect ) == pSucc && + marked_node_ptr pSucc = hp.protect( pCur->next( nLevel ), gc_protect ); + + if ( pSucc.bits() && pPred->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) { @@ -1204,7 +1205,7 @@ namespace cds { namespace intrusive { if ( pSucc.bits() ) { // pCur is marked, i.e. logically deleted // try to help deleting pCur - help_remove( nLevel, pPred, pCur, pSucc ); + help_remove( nLevel, pPred, pCur ); goto retry; } else { @@ -1265,7 +1266,7 @@ namespace cds { namespace intrusive { if ( pSucc.bits() ) { // pCur is marked, i.e. logically deleted. // try to help deleting pCur - help_remove( nLevel, pPred, pCur, pSucc ); + help_remove( nLevel, pPred, pCur ); goto retry; } } @@ -1314,7 +1315,7 @@ namespace cds { namespace intrusive { if ( pSucc.bits() ) { // pCur is marked, i.e. logically deleted. // try to help deleting pCur - help_remove( nLevel, pPred, pCur, pSucc ); + help_remove( nLevel, pPred, pCur ); goto retry; } else { @@ -1334,6 +1335,70 @@ namespace cds { namespace intrusive { return ( pos.pCur = pCur.ptr() ) != nullptr; } + bool renew_insert_position( value_type& val, node_type * pNode, position& pos ) + { + node_type * pPred; + marked_node_ptr pSucc; + marked_node_ptr pCur; + key_comparator cmp; + + // Hazard pointer array: + // pPred: [nLevel * 2] + // pSucc: [nLevel * 2 + 1] + + retry: + pPred = m_Head.head(); + int nCmp = 1; + + for ( int nLevel = static_cast( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) { + pos.guards.assign( nLevel * 2, node_traits::to_value_ptr( pPred ) ); + while ( true ) { + pCur = pos.guards.protect( nLevel * 2 + 1, pPred->next( nLevel ), gc_protect ); + if ( pCur.bits() ) { + // pCur.bits() means that pPred is logically deleted + goto retry; + } + + if ( pCur.ptr() == nullptr ) { + // end of list at level nLevel - goto next level + break; + } + + // pSucc contains deletion mark for pCur + pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire ); + + if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() ) + goto retry; + + if ( pSucc.bits()) { + // pCur is marked, i.e. logically deleted + if ( pCur.ptr() == pNode ) { + // Node is removing while we are inserting it + return false; + } + // try to help deleting pCur + help_remove( nLevel, pPred, pCur ); + goto retry; + } + else { + nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr()), val ); + if ( nCmp < 0 ) { + pPred = pCur.ptr(); + pos.guards.copy( nLevel * 2, nLevel * 2 + 1 ); // pPrev guard := cur guard + } + else + break; + } + } + + // Next level + pos.pPrev[nLevel] = pPred; + pos.pSucc[nLevel] = pCur.ptr(); + } + + return nCmp == 0; + } + template bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f ) { @@ -1359,15 +1424,21 @@ namespace cds { namespace intrusive { marked_node_ptr pSucc( pos.pSucc[nLevel] ); // Set pNode->next - // pNode->next can have a "logical deleted" flag if another thread is removing pNode right now + // pNode->next can have "logical deleted" flag if another thread is removing pNode right now if ( !pNode->next( nLevel ).compare_exchange_strong( p, pSucc, memory_model::memory_order_acq_rel, atomics::memory_order_acquire ) ) { // pNode has been marked as removed while we are inserting it // Stop inserting assert( p.bits() != 0 ); - if ( pNode->level_unlinked( nHeight - nLevel )) - gc::retire( &val, dispose_node ); + + // Here pNode is linked at least level 0 so level_unlinked() cannot returns true + CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel )); + + // pNode is linked up to nLevel - 1 + // Remove it via find_position() + find_position( val, pos, key_comparator(), false ); + m_Stat.onLogicDeleteWhileInsert(); return true; } @@ -1383,9 +1454,16 @@ namespace cds { namespace intrusive { // Renew insert position m_Stat.onRenewInsertPosition(); - if ( !find_position( val, pos, key_comparator(), false )) { + + if ( !renew_insert_position( val, pNode, pos )) { // The node has been deleted while we are inserting it - m_Stat.onNotFoundWhileInsert(); + // Update current height for concurent removing + CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel )); + + m_Stat.onRemoveWhileInsert(); + + // help to removing val + find_position( val, pos, key_comparator(), false ); return true; } } @@ -1428,15 +1506,20 @@ namespace cds { namespace intrusive { for ( int nLevel = static_cast( pDel->height() - 1 ); nLevel >= 0; --nLevel ) { - pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed ); + pSucc = pDel->next( nLevel ).load( memory_model::memory_order_acquire ); if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) + memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ) ) { pDel->level_unlinked(); } else { // Make slow erase +# ifdef CDS_DEBUG + if ( find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false ) ) + assert( pDel != pos.pCur ); +# else find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false ); +# endif m_Stat.onSlowErase(); return true; } diff --git a/cds/intrusive/skip_list_rcu.h b/cds/intrusive/skip_list_rcu.h index dfe81717..afd0d3f8 100644 --- a/cds/intrusive/skip_list_rcu.h +++ b/cds/intrusive/skip_list_rcu.h @@ -1581,6 +1581,67 @@ namespace cds { namespace intrusive { return ( pos.pCur = pCur.ptr() ) != nullptr; } + bool renew_insert_position( value_type& val, node_type * pNode, position& pos ) + { + assert( gc::is_locked() ); + + node_type * pPred; + marked_node_ptr pSucc; + marked_node_ptr pCur; + key_comparator cmp; + int nCmp = 1; + + retry: + pPred = m_Head.head(); + + for ( int nLevel = static_cast( c_nMaxHeight - 1 ); nLevel >= 0; --nLevel ) { + + while ( true ) { + pCur = pPred->next( nLevel ).load( memory_model::memory_order_acquire ); + if ( pCur.bits() ) { + // pCur.bits() means that pPred is logically deleted + goto retry; + } + + if ( pCur.ptr() == nullptr ) { + // end of the list at level nLevel - goto next level + break; + } + + // pSucc contains deletion mark for pCur + pSucc = pCur->next( nLevel ).load( memory_model::memory_order_acquire ); + + if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ).all() != pCur.ptr() ) + goto retry; + + if ( pSucc.bits() ) { + // pCur is marked, i.e. logically deleted. + if ( pCur.ptr() == pNode ) { + // Node is removing while we are inserting it + return false; + } + + // try to help deleting pCur + help_remove( nLevel, pPred, pCur, pSucc, pos ); + goto retry; + } + else { + nCmp = cmp( *node_traits::to_value_ptr( pCur.ptr() ), val ); + if ( nCmp < 0 ) + pPred = pCur.ptr(); + else + break; + } + } + + // Next level + pos.pPrev[nLevel] = pPred; + pos.pSucc[nLevel] = pCur.ptr(); + } + + return nCmp == 0; + } + template bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f ) { @@ -1613,8 +1674,14 @@ namespace cds { namespace intrusive { // pNode has been marked as removed while we are inserting it // Stop inserting assert( p.bits() != 0 ); - if ( pNode->level_unlinked( nHeight - nLevel )) - pos.dispose( pNode ); + + // Here pNode is linked at least level 0 so level_unlinked() cannot returns true + CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel )); + + // pNode is linked up to nLevel - 1 + // Remove it via find_position() + find_position( val, pos, key_comparator(), false ); + m_Stat.onLogicDeleteWhileInsert(); return true; } @@ -1630,9 +1697,16 @@ namespace cds { namespace intrusive { // Renew insert position m_Stat.onRenewInsertPosition(); - if ( !find_position( val, pos, key_comparator(), false ) ) { + + if ( !renew_insert_position( val, pNode, pos )) { // The node has been deleted while we are inserting it - m_Stat.onNotFoundWhileInsert(); + // Update current height for concurent removing + CDS_VERIFY_FALSE( pNode->level_unlinked( nHeight - nLevel ) ); + + m_Stat.onRemoveWhileInsert(); + + // help to removing val + find_position( val, pos, key_comparator(), false ); return true; } } @@ -1680,15 +1754,20 @@ namespace cds { namespace intrusive { p = pDel; for ( int nLevel = static_cast( pDel->height() - 1 ); nLevel >= 0; --nLevel ) { - pSucc = pDel->next( nLevel ).load( memory_model::memory_order_relaxed ); + pSucc = pDel->next( nLevel ).load( memory_model::memory_order_acquire ); if ( pos.pPrev[nLevel]->next( nLevel ).compare_exchange_strong( p, marked_node_ptr( pSucc.ptr() ), - memory_model::memory_order_acq_rel, atomics::memory_order_acquire ) ) + memory_model::memory_order_acq_rel, atomics::memory_order_relaxed ) ) { pDel->level_unlinked(); } else { // Make slow erase +# ifdef CDS_DEBUG + if ( find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false ) ) + assert( pDel != pos.pCur ); +# else find_position( *node_traits::to_value_ptr( pDel ), pos, key_comparator(), false ); +# endif if ( bExtract ) m_Stat.onSlowExtract(); else diff --git a/test/include/cds_test/stat_skiplist_out.h b/test/include/cds_test/stat_skiplist_out.h index 30f51373..d867127a 100644 --- a/test/include/cds_test/stat_skiplist_out.h +++ b/test/include/cds_test/stat_skiplist_out.h @@ -75,7 +75,7 @@ namespace cds_test { << CDSSTRESS_STAT_OUT( s, m_nFindSlowFailed ) << CDSSTRESS_STAT_OUT( s, m_nRenewInsertPosition ) << CDSSTRESS_STAT_OUT( s, m_nLogicDeleteWhileInsert ) - << CDSSTRESS_STAT_OUT( s, m_nNotFoundWhileInsert ) + << CDSSTRESS_STAT_OUT( s, m_nRemoveWhileInsert ) << CDSSTRESS_STAT_OUT( s, m_nFastErase ) << CDSSTRESS_STAT_OUT( s, m_nSlowErase ) << CDSSTRESS_STAT_OUT( s, m_nFastExtract )