From: khizmax Date: Mon, 3 Oct 2016 06:04:57 +0000 (+0300) Subject: Fixed IterableList ordering violation X-Git-Tag: v2.2.0~104 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=8a0d82a3a88b3b88acd1014abdd40702cf7afcea;ds=sidebyside Fixed IterableList ordering violation --- diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h index 198b5d59..e9c27fd7 100644 --- a/cds/intrusive/details/iterable_list_base.h +++ b/cds/intrusive/details/iterable_list_base.h @@ -50,9 +50,10 @@ namespace cds { namespace intrusive { struct node { typedef T value_type; ///< Value type + typedef cds::details::marked_ptr marked_data_ptr; ///< marked pointer to the value - atomics::atomic< node* > next; ///< pointer to next node in the list - atomics::atomic< value_type* > data; ///< pointer to user data, \p nullptr if the node is free + atomics::atomic< node* > next; ///< pointer to next node in the list + atomics::atomic< marked_data_ptr > data; ///< pointer to user data, \p nullptr if the node is free //@cond node() @@ -75,6 +76,8 @@ namespace cds { namespace intrusive { event_counter m_nInsertSuccess; ///< Number of success \p insert() operations event_counter m_nInsertFailed; ///< Number of failed \p insert() operations event_counter m_nInsertRetry; ///< Number of attempts to insert new item + event_counter m_nInsertReuse; ///< Number of reusing empty node when inserting + event_counter m_nInsertReuseFailed; ///< Number of failed attempsof reusing free node when inserting event_counter m_nUpdateNew; ///< Number of new item inserted for \p update() event_counter m_nUpdateExisting; ///< Number of existing item updates event_counter m_nUpdateFailed; ///< Number of failed \p update() call @@ -92,6 +95,8 @@ namespace cds { namespace intrusive { void onInsertSuccess() { ++m_nInsertSuccess; } void onInsertFailed() { ++m_nInsertFailed; } void onInsertRetry() { ++m_nInsertRetry; } + void onInsertReuse() { ++m_nInsertReuse; } + void onInsertReuseFailed() { ++m_nInsertReuseFailed; } void onUpdateNew() { ++m_nUpdateNew; } void onUpdateExisting() { ++m_nUpdateExisting; } void onUpdateFailed() { ++m_nUpdateFailed; } @@ -113,6 +118,8 @@ namespace cds { namespace intrusive { void onInsertSuccess() const {} void onInsertFailed() const {} void onInsertRetry() const {} + void onInsertReuse() const {} + void onInsertReuseFailed() const {} void onUpdateNew() const {} void onUpdateExisting() const {} void onUpdateFailed() const {} @@ -140,6 +147,8 @@ namespace cds { namespace intrusive { void onInsertSuccess() { m_stat.onInsertSuccess(); } void onInsertFailed() { m_stat.onInsertFailed(); } void onInsertRetry() { m_stat.onInsertRetry(); } + void onInsertReuse() { m_stat.onInsertReuse(); } + void onInsertReuseFailed() { m_stat.onInsertReuseFailed(); } void onUpdateNew() { m_stat.onUpdateNew(); } void onUpdateExisting() { m_stat.onUpdateExisting();} void onUpdateFailed() { m_stat.onUpdateFailed(); } diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h index fe85cc98..129104fc 100644 --- a/cds/intrusive/impl/iterable_list.h +++ b/cds/intrusive/impl/iterable_list.h @@ -163,6 +163,7 @@ namespace cds { namespace intrusive { //@cond typedef atomics::atomic< node_type* > atomic_node_ptr; ///< Atomic node pointer typedef atomic_node_ptr auxiliary_head; ///< Auxiliary head type (for split-list support) + typedef typename node_type::marked_data_ptr marked_data_ptr; atomic_node_ptr m_pHead; ///< Head pointer item_counter m_ItemCounter; ///< Item counter @@ -189,7 +190,7 @@ namespace cds { namespace intrusive { friend class IterableList; protected: - node_type* m_pNode; + node_type* m_pNode; typename gc::Guard m_Guard; // data guard void next() @@ -200,7 +201,7 @@ namespace cds { namespace intrusive { m_Guard.clear(); break; } - if ( m_Guard.protect( m_pNode->data )) + if ( m_Guard.protect( m_pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr()) break; } } @@ -209,7 +210,7 @@ namespace cds { namespace intrusive { : m_pNode( pNode.load( memory_model::memory_order_acquire )) { if ( m_pNode ) { - if ( !m_Guard.protect( m_pNode->data )) + if ( !m_Guard.protect( m_pNode->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr()) next(); } } @@ -775,7 +776,7 @@ namespace cds { namespace intrusive { position pos; for ( pos.pCur = m_pHead.load( memory_model::memory_order_relaxed ); pos.pCur; pos.pCur = pos.pCur->next.load( memory_model::memory_order_relaxed )) { while ( true ) { - pos.pFound = pos.guard.protect( pos.pCur->data ); + pos.pFound = pos.guard.protect( pos.pCur->data, []( marked_data_ptr p ) { return p.ptr(); }).ptr(); if ( !pos.pFound ) break; if ( cds_likely( unlink_node( pos ))) { @@ -893,7 +894,10 @@ namespace cds { namespace intrusive { assert( pos.pFound != nullptr ); assert( key_comparator()(*pos.pFound, val) == 0 ); - if ( cds_likely( pos.pCur->data.compare_exchange_strong( pos.pFound, &val, memory_model::memory_order_release, atomics::memory_order_relaxed ))) { + marked_data_ptr pFound( pos.pFound ); + if ( cds_likely( pos.pCur->data.compare_exchange_strong( pFound, marked_data_ptr( &val ), + memory_model::memory_order_release, atomics::memory_order_relaxed ))) + { if ( pos.pFound != &val ) { retire_data( pos.pFound ); func( val, pos.pFound ); @@ -1080,7 +1084,11 @@ namespace cds { namespace intrusive { return false; } - value_type * pVal = pos.guard.protect( pCur->data ); + value_type * pVal = pos.guard.protect( pCur->data, + []( marked_data_ptr p ) -> value_type* + { + return p.ptr(); + }).ptr(); if ( pVal ) { int nCmp = cmp( *pVal, val ); @@ -1123,7 +1131,7 @@ namespace cds { namespace intrusive { { node_type * pNode = m_pHead.load( memory_model::memory_order_relaxed ); while ( pNode ) { - value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ); + value_type * pVal = pNode->data.load( memory_model::memory_order_relaxed ).ptr(); if ( pVal ) retire_data( pVal ); node_type * pNext = pNode->next.load( memory_model::memory_order_relaxed ); @@ -1135,10 +1143,31 @@ namespace cds { namespace intrusive { bool link_node( value_type * pVal, position& pos ) { if ( pos.pPrev ) { - if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) { + if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == marked_data_ptr() ) { // reuse pPrev - value_type * p = nullptr; - return pos.pPrev->data.compare_exchange_strong( p, pVal, memory_model::memory_order_release, atomics::memory_order_relaxed ); + + // We need pos.pCur data should be unchanged, otherwise ordering violation can be possible + // if current thread will be preempted and another thread deletes pos.pCur data + // and then set it to another. + // To prevent this we mark pos.pCur data as undeletable by setting LSB + marked_data_ptr val( pos.pFound ); + if ( !pos.pCur->data.compare_exchange_strong( val, val | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { + // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data + m_Stat.onInsertReuseFailed(); + return false; + } + + // Set pos.pPrev data if it is null + marked_data_ptr p; + bool result = pos.pPrev->data.compare_exchange_strong( p, marked_data_ptr( pVal ), + memory_model::memory_order_release, atomics::memory_order_relaxed ); + + // Clear pos.pCur data mark + pos.pCur->data.store( val, memory_model::memory_order_relaxed ); + + if ( result ) + m_Stat.onInsertReuse(); + return result; } else { // insert new node between pos.pPrev and pos.pCur @@ -1167,7 +1196,8 @@ namespace cds { namespace intrusive { assert( pos.pCur != nullptr ); assert( pos.pFound != nullptr ); - if ( pos.pCur->data.compare_exchange_strong( pos.pFound, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) { + marked_data_ptr val( pos.pFound ); + if ( pos.pCur->data.compare_exchange_strong( val, marked_data_ptr(), memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) { retire_data( pos.pFound ); return true; } diff --git a/test/include/cds_test/stat_iterable_list_out.h b/test/include/cds_test/stat_iterable_list_out.h index a61449c3..c14f204e 100644 --- a/test/include/cds_test/stat_iterable_list_out.h +++ b/test/include/cds_test/stat_iterable_list_out.h @@ -5,7 +5,7 @@ Source code repo: http://github.com/khizmax/libcds/ Download: http://sourceforge.net/projects/libcds/files/ - + Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: @@ -46,6 +46,8 @@ namespace cds_test { << CDSSTRESS_STAT_OUT( s, m_nInsertSuccess ) << CDSSTRESS_STAT_OUT( s, m_nInsertFailed ) << CDSSTRESS_STAT_OUT( s, m_nInsertRetry ) + << CDSSTRESS_STAT_OUT( s, m_nInsertReuse ) + << CDSSTRESS_STAT_OUT( s, m_nInsertReuseFailed ) << CDSSTRESS_STAT_OUT( s, m_nUpdateNew ) << CDSSTRESS_STAT_OUT( s, m_nUpdateExisting ) << CDSSTRESS_STAT_OUT( s, m_nUpdateFailed )