From 32abbe4c72f99dae9bf2a6148032e5d6554c29d3 Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 17 Apr 2017 22:34:50 +0300 Subject: [PATCH] Fixed memory ordering (by TSan reports) --- cds/intrusive/details/ellen_bintree_base.h | 11 +++++---- cds/intrusive/ellen_bintree_rcu.h | 28 +++++++++++----------- cds/intrusive/impl/ellen_bintree.h | 26 ++++++++++---------- 3 files changed, 34 insertions(+), 31 deletions(-) diff --git a/cds/intrusive/details/ellen_bintree_base.h b/cds/intrusive/details/ellen_bintree_base.h index 39b03cc0..75c6da8a 100644 --- a/cds/intrusive/details/ellen_bintree_base.h +++ b/cds/intrusive/details/ellen_bintree_base.h @@ -119,8 +119,9 @@ namespace cds { namespace intrusive { /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node explicit basic_node( bool bInternal ) - : m_nFlags( bInternal ? internal : 0 ) - {} + { + m_nFlags.store( bInternal ? internal: 0, atomics::memory_order_release ); + } /// Checks if the node is a leaf bool is_leaf() const @@ -168,6 +169,7 @@ namespace cds { namespace intrusive { typedef basic_node base_class; typedef GC gc ; ///< Garbage collector + /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node explicit base_node( bool bInternal ) : base_class( bInternal ) @@ -241,8 +243,9 @@ namespace cds { namespace intrusive { , m_pLeft( nullptr ) , m_pRight( nullptr ) , m_pUpdate( update_ptr()) - , m_nEmptyUpdate(0) - {} + { + m_nEmptyUpdate.store( 0, atomics::memory_order_release ); + } //@cond update_ptr null_update_desc() diff --git a/cds/intrusive/ellen_bintree_rcu.h b/cds/intrusive/ellen_bintree_rcu.h index b948cc8e..5d7ec110 100644 --- a/cds/intrusive/ellen_bintree_rcu.h +++ b/cds/intrusive/ellen_bintree_rcu.h @@ -53,7 +53,7 @@ namespace cds { namespace intrusive { /// Constructs leaf (bIntrenal == false) or internal (bInternal == true) node explicit base_node( bool bInternal ) - : basic_node( bInternal ? internal : 0 ) + : basic_node( bInternal ) , m_pNextRetired( nullptr ) {} }; @@ -1395,16 +1395,16 @@ namespace cds { namespace intrusive { tree_node * pLeaf = static_cast( pOp->iInfo.pLeaf ); if ( pOp->iInfo.bRightLeaf ) { pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast( pOp->iInfo.pNew ), - memory_model::memory_order_relaxed, atomics::memory_order_relaxed ); + memory_model::memory_order_release, atomics::memory_order_relaxed ); } else { pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast( pOp->iInfo.pNew ), - memory_model::memory_order_relaxed, atomics::memory_order_relaxed ); + memory_model::memory_order_release, atomics::memory_order_relaxed ); } update_ptr cur( pOp, update_desc::IFlag ); pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(), - memory_model::memory_order_release, atomics::memory_order_relaxed ); + memory_model::memory_order_acquire, atomics::memory_order_relaxed ); } bool check_delete_precondition( search_result& res ) @@ -1423,7 +1423,7 @@ namespace cds { namespace intrusive { update_ptr pUpdate( pOp->dInfo.pUpdateParent ); update_ptr pMark( pOp, update_desc::Mark ); if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) + memory_model::memory_order_release, atomics::memory_order_relaxed )) { help_marked( pOp ); retire_node( pOp->dInfo.pParent, rl ); @@ -1447,7 +1447,7 @@ namespace cds { namespace intrusive { // Undo grandparent dInfo update_ptr pDel( pOp, update_desc::DFlag ); if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(), - memory_model::memory_order_release, atomics::memory_order_relaxed )) + memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { retire_update_desc( pOp, rl, false ); } @@ -1473,7 +1473,7 @@ namespace cds { namespace intrusive { update_ptr upd( pOp, update_desc::DFlag ); pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(), - memory_model::memory_order_release, atomics::memory_order_relaxed ); + memory_model::memory_order_acquire, atomics::memory_order_relaxed ); } template @@ -1660,7 +1660,7 @@ namespace cds { namespace intrusive { update_ptr updGP( res.updGrandParent.ptr()); if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) + memory_model::memory_order_release, atomics::memory_order_acquire )) { if ( help_delete( pOp, updRetire )) { // res.pLeaf is not deleted yet since RCU is blocked @@ -1738,7 +1738,7 @@ namespace cds { namespace intrusive { update_ptr updGP( res.updGrandParent.ptr()); if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) + memory_model::memory_order_release, atomics::memory_order_acquire )) { if ( help_delete( pOp, updRetire )) { pResult = node_traits::to_value_ptr( res.pLeaf ); @@ -1803,7 +1803,7 @@ namespace cds { namespace intrusive { update_ptr updGP( res.updGrandParent.ptr()); if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) + memory_model::memory_order_release, atomics::memory_order_acquire )) { if ( help_delete( pOp, updRetire )) { pResult = node_traits::to_value_ptr( res.pLeaf ); @@ -1867,7 +1867,7 @@ namespace cds { namespace intrusive { update_ptr updGP( res.updGrandParent.ptr()); if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) + memory_model::memory_order_release, atomics::memory_order_acquire )) { if ( help_delete( pOp, updRetire )) { pResult = node_traits::to_value_ptr( res.pLeaf ); @@ -1970,7 +1970,7 @@ namespace cds { namespace intrusive { pNewInternal->infinite_key( 1 ); } pNewInternal->m_pLeft.store( static_cast(pNewLeaf), memory_model::memory_order_relaxed ); - pNewInternal->m_pRight.store( static_cast(res.pLeaf), memory_model::memory_order_release ); + pNewInternal->m_pRight.store( static_cast(res.pLeaf), memory_model::memory_order_relaxed ); } else { assert( !res.pLeaf->is_internal()); @@ -1978,7 +1978,7 @@ namespace cds { namespace intrusive { key_extractor()( pNewInternal->m_Key, val ); pNewInternal->m_pLeft.store( static_cast(res.pLeaf), memory_model::memory_order_relaxed ); - pNewInternal->m_pRight.store( static_cast(pNewLeaf), memory_model::memory_order_release ); + pNewInternal->m_pRight.store( static_cast(pNewLeaf), memory_model::memory_order_relaxed ); assert( !res.pLeaf->infinite_key()); } @@ -1991,7 +1991,7 @@ namespace cds { namespace intrusive { update_ptr updCur( res.updParent.ptr()); if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) + memory_model::memory_order_release, atomics::memory_order_acquire )) { // do insert help_insert( pOp ); diff --git a/cds/intrusive/impl/ellen_bintree.h b/cds/intrusive/impl/ellen_bintree.h index f935c13f..48154282 100644 --- a/cds/intrusive/impl/ellen_bintree.h +++ b/cds/intrusive/impl/ellen_bintree.h @@ -1149,17 +1149,17 @@ namespace cds { namespace intrusive { tree_node * pLeaf = static_cast( pOp->iInfo.pLeaf ); if ( pOp->iInfo.bRightLeaf ) { CDS_VERIFY( pOp->iInfo.pParent->m_pRight.compare_exchange_strong( pLeaf, static_cast( pOp->iInfo.pNew ), - memory_model::memory_order_relaxed, atomics::memory_order_relaxed )); + memory_model::memory_order_release, atomics::memory_order_relaxed )); } else { CDS_VERIFY( pOp->iInfo.pParent->m_pLeft.compare_exchange_strong( pLeaf, static_cast( pOp->iInfo.pNew ), - memory_model::memory_order_relaxed, atomics::memory_order_relaxed )); + memory_model::memory_order_release, atomics::memory_order_relaxed )); } // Unflag parent update_ptr cur( pOp, update_desc::IFlag ); CDS_VERIFY( pOp->iInfo.pParent->m_pUpdate.compare_exchange_strong( cur, pOp->iInfo.pParent->null_update_desc(), - memory_model::memory_order_release, atomics::memory_order_relaxed )); + memory_model::memory_order_acquire, atomics::memory_order_relaxed )); } bool check_delete_precondition( search_result& res ) const @@ -1179,7 +1179,7 @@ namespace cds { namespace intrusive { update_ptr pUpdate( pOp->dInfo.pUpdateParent ); update_ptr pMark( pOp, update_desc::Mark ); if ( pOp->dInfo.pParent->m_pUpdate.compare_exchange_strong( pUpdate, pMark, // * - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) + memory_model::memory_order_release, atomics::memory_order_relaxed )) { help_marked( pOp ); @@ -1198,7 +1198,7 @@ namespace cds { namespace intrusive { // Undo grandparent dInfo update_ptr pDel( pOp, update_desc::DFlag ); if ( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( pDel, pOp->dInfo.pGrandParent->null_update_desc(), - memory_model::memory_order_release, atomics::memory_order_relaxed )) + memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { retire_update_desc( pOp ); } @@ -1234,7 +1234,7 @@ namespace cds { namespace intrusive { update_ptr upd( pOp, update_desc::DFlag ); CDS_VERIFY( pOp->dInfo.pGrandParent->m_pUpdate.compare_exchange_strong( upd, pOp->dInfo.pGrandParent->null_update_desc(), - memory_model::memory_order_release, atomics::memory_order_relaxed )); + memory_model::memory_order_acquire, atomics::memory_order_relaxed )); } bool try_insert( value_type& val, internal_node * pNewInternal, search_result& res ) @@ -1258,7 +1258,7 @@ namespace cds { namespace intrusive { pNewInternal->infinite_key( 1 ); } pNewInternal->m_pLeft.store( static_cast(pNewLeaf), memory_model::memory_order_relaxed ); - pNewInternal->m_pRight.store( static_cast(res.pLeaf), memory_model::memory_order_release ); + pNewInternal->m_pRight.store( static_cast(res.pLeaf), memory_model::memory_order_relaxed ); } else { assert( !res.pLeaf->is_internal()); @@ -1266,7 +1266,7 @@ namespace cds { namespace intrusive { pNewInternal->infinite_key( 0 ); key_extractor()(pNewInternal->m_Key, val); pNewInternal->m_pLeft.store( static_cast(res.pLeaf), memory_model::memory_order_relaxed ); - pNewInternal->m_pRight.store( static_cast(pNewLeaf), memory_model::memory_order_release ); + pNewInternal->m_pRight.store( static_cast(pNewLeaf), memory_model::memory_order_relaxed ); assert( !res.pLeaf->infinite_key()); } @@ -1281,7 +1281,7 @@ namespace cds { namespace intrusive { update_ptr updCur( res.updParent.ptr()); if ( res.pParent->m_pUpdate.compare_exchange_strong( updCur, update_ptr( pOp, update_desc::IFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { + memory_model::memory_order_release, atomics::memory_order_relaxed )) { // do insert help_insert( pOp ); retire_update_desc( pOp ); @@ -1327,7 +1327,7 @@ namespace cds { namespace intrusive { update_ptr updGP( res.updGrandParent.ptr()); if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { + memory_model::memory_order_release, atomics::memory_order_relaxed )) { if ( help_delete( pOp )) { // res.pLeaf is not deleted yet since it is guarded f( *node_traits::to_value_ptr( res.pLeaf )); @@ -1378,7 +1378,7 @@ namespace cds { namespace intrusive { update_ptr updGP( res.updGrandParent.ptr()); if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { + memory_model::memory_order_release, atomics::memory_order_relaxed )) { if ( help_delete( pOp )) break; pOp = nullptr; @@ -1445,7 +1445,7 @@ namespace cds { namespace intrusive { update_ptr updGP( res.updGrandParent.ptr()); if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) + memory_model::memory_order_release, atomics::memory_order_relaxed )) { if ( help_delete( pOp )) break; @@ -1494,7 +1494,7 @@ namespace cds { namespace intrusive { update_ptr updGP( res.updGrandParent.ptr()); if ( res.pGrandParent->m_pUpdate.compare_exchange_strong( updGP, update_ptr( pOp, update_desc::DFlag ), - memory_model::memory_order_acquire, atomics::memory_order_relaxed )) + memory_model::memory_order_release, atomics::memory_order_relaxed )) { if ( help_delete( pOp )) break; -- 2.34.1