From 2589f17978030080daba1af2ac639e39bad282e4 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 19 Apr 2015 20:32:56 +0300 Subject: [PATCH] Fixed memor orderding (tsan) --- cds/container/details/bronson_avltree_base.h | 4 +- cds/container/impl/bronson_avltree_map_rcu.h | 2 +- cds/gc/details/dhp.h | 44 +++++++++------- cds/intrusive/impl/michael_list.h | 8 +-- src/dhp_gc.cpp | 54 +++++++++++--------- 5 files changed, 61 insertions(+), 51 deletions(-) diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h index 85e220d9..178e0bd3 100644 --- a/cds/container/details/bronson_avltree_base.h +++ b/cds/container/details/bronson_avltree_base.h @@ -73,10 +73,10 @@ namespace cds { namespace container { m_pParent.store( p, order ); } - atomics::atomic const& child( int nDirection ) const + node_type * child( int nDirection, atomics::memory_order order ) const { assert( nDirection != 0 ); - return nDirection < 0 ? m_pLeft : m_pRight; + return nDirection < 0 ? m_pLeft.load( order ) : m_pRight.load( order ); } void child( node_type * pChild, int nDirection, atomics::memory_order order ) diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index 494bf2ca..515f289f 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -154,7 +154,7 @@ namespace cds { namespace container { static node_type * child( node_type * pNode, int nDir, atomics::memory_order order ) { - return pNode->child( nDir ).load( order ); + return pNode->child( nDir, order ); } static node_type * parent( node_type * pNode, atomics::memory_order order ) diff --git a/cds/gc/details/dhp.h b/cds/gc/details/dhp.h index c4566f52..ecf61c3b 100644 --- a/cds/gc/details/dhp.h +++ b/cds/gc/details/dhp.h @@ -57,8 +57,8 @@ namespace cds { namespace gc { /// Retired pointer buffer node struct retired_ptr_node { retired_ptr m_ptr ; ///< retired pointer - retired_ptr_node * m_pNext ; ///< next retired pointer in buffer - retired_ptr_node * m_pNextFree ; ///< next item in free list of retired_ptr_node + atomics::atomic m_pNext ; ///< next retired pointer in buffer + atomics::atomic m_pNextFree ; ///< next item in free list of \p retired_ptr_node }; /// Internal guard representation @@ -262,7 +262,7 @@ namespace cds { namespace gc { { retired_ptr_node * pHead = m_pHead.load(atomics::memory_order_acquire); do { - node.m_pNext = pHead; + node.m_pNext.store( pHead, atomics::memory_order_relaxed ); // pHead is changed by compare_exchange_weak } while ( !m_pHead.compare_exchange_weak( pHead, &node, atomics::memory_order_release, atomics::memory_order_relaxed )); @@ -277,7 +277,7 @@ namespace cds { namespace gc { retired_ptr_node * pHead = m_pHead.load( atomics::memory_order_acquire ); do { - pLast->m_pNext = pHead; + pLast->m_pNext.store( pHead, atomics::memory_order_relaxed ); // pHead is changed by compare_exchange_weak } while ( !m_pHead.compare_exchange_weak( pHead, pFirst, atomics::memory_order_release, atomics::memory_order_relaxed ) ); @@ -326,8 +326,8 @@ namespace cds { namespace gc { /// Pool block struct block { - block * pNext; ///< next block - item items[m_nItemPerBlock]; ///< item array + atomics::atomic pNext; ///< next block + item items[m_nItemPerBlock]; ///< item array }; atomics::atomic m_pBlockListHead; ///< head of of allocated block list @@ -349,24 +349,24 @@ namespace cds { namespace gc { // link items within the block item * pLastItem = pNew->items + m_nItemPerBlock - 1; for ( item * pItem = pNew->items; pItem != pLastItem; ++pItem ) { - pItem->m_pNextFree = pItem + 1; - CDS_STRICT_DO( pItem->m_pNext = nullptr ); + pItem->m_pNextFree.store( pItem + 1, atomics::memory_order_release ); + CDS_STRICT_DO( pItem->m_pNext.store( nullptr, atomics::memory_order_relaxed )); } // links new block to the block list { - block * pHead = m_pBlockListHead.load(atomics::memory_order_acquire); + block * pHead = m_pBlockListHead.load(atomics::memory_order_relaxed); do { - pNew->pNext = pHead; + pNew->pNext.store( pHead, atomics::memory_order_relaxed ); // pHead is changed by compare_exchange_weak - } while ( !m_pBlockListHead.compare_exchange_weak( pHead, pNew, atomics::memory_order_release, atomics::memory_order_relaxed )); + } while ( !m_pBlockListHead.compare_exchange_weak( pHead, pNew, atomics::memory_order_relaxed, atomics::memory_order_relaxed )); } // links block's items to the free list { - item * pHead = m_pGlobalFreeHead.load(atomics::memory_order_acquire); + item * pHead = m_pGlobalFreeHead.load(atomics::memory_order_relaxed); do { - pLastItem->m_pNextFree = pHead; + pLastItem->m_pNextFree.store( pHead, atomics::memory_order_release ); // pHead is changed by compare_exchange_weak } while ( !m_pGlobalFreeHead.compare_exchange_weak( pHead, pNew->items, atomics::memory_order_release, atomics::memory_order_relaxed )); } @@ -398,7 +398,7 @@ namespace cds { namespace gc { { block * p; for ( block * pBlock = m_pBlockListHead.load(atomics::memory_order_relaxed); pBlock; pBlock = p ) { - p = pBlock->pNext; + p = pBlock->pNext.load( atomics::memory_order_relaxed ); m_BlockAllocator.Delete( pBlock ); } } @@ -418,24 +418,30 @@ namespace cds { namespace gc { pItem = m_pEpochFree[ nEpoch = current_epoch() ].load(atomics::memory_order_acquire); if ( !pItem ) goto retry; - if ( m_pEpochFree[nEpoch].compare_exchange_weak( pItem, pItem->m_pNextFree, atomics::memory_order_release, atomics::memory_order_relaxed )) + if ( m_pEpochFree[nEpoch].compare_exchange_weak( pItem, + pItem->m_pNextFree.load(atomics::memory_order_acquire), + atomics::memory_order_acquire, atomics::memory_order_relaxed )) + { goto success; + } } // Epoch free list is empty // Alloc from global free list retry: - pItem = m_pGlobalFreeHead.load( atomics::memory_order_acquire ); + pItem = m_pGlobalFreeHead.load( atomics::memory_order_relaxed ); do { if ( !pItem ) { allocNewBlock(); goto retry; } // pItem is changed by compare_exchange_weak - } while ( !m_pGlobalFreeHead.compare_exchange_weak( pItem, pItem->m_pNextFree, atomics::memory_order_release, atomics::memory_order_relaxed )); + } while ( !m_pGlobalFreeHead.compare_exchange_weak( pItem, + pItem->m_pNextFree.load(atomics::memory_order_acquire), + atomics::memory_order_acquire, atomics::memory_order_relaxed )); success: - CDS_STRICT_DO( pItem->m_pNextFree = nullptr ); + CDS_STRICT_DO( pItem->m_pNextFree.store( nullptr, atomics::memory_order_relaxed )); return *pItem; } @@ -460,7 +466,7 @@ namespace cds { namespace gc { item * pCurHead; do { pCurHead = m_pEpochFree[nEpoch = next_epoch()].load(atomics::memory_order_acquire); - pTail->m_pNextFree = pCurHead; + pTail->m_pNextFree.store( pCurHead, atomics::memory_order_release ); } while ( !m_pEpochFree[nEpoch].compare_exchange_weak( pCurHead, pHead, atomics::memory_order_release, atomics::memory_order_relaxed )); } }; diff --git a/cds/intrusive/impl/michael_list.h b/cds/intrusive/impl/michael_list.h index 3f1548a4..e4dc7901 100644 --- a/cds/intrusive/impl/michael_list.h +++ b/cds/intrusive/impl/michael_list.h @@ -1077,19 +1077,19 @@ try_again: while ( true ) { if ( pCur.ptr() == nullptr ) { pos.pPrev = pPrev; - pos.pCur = pCur.ptr(); - pos.pNext = pNext.ptr(); + pos.pCur = nullptr; + pos.pNext = nullptr; return false; } pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed); pos.guards.assign( position::guard_next_item, node_traits::to_value_ptr( pNext.ptr() )); - if ( pCur->m_pNext.load(memory_model::memory_order_relaxed).all() != pNext.all() ) { + if ( pCur->m_pNext.load(memory_model::memory_order_acquire).all() != pNext.all() ) { bkoff(); goto try_again; } - if ( pPrev->load(memory_model::memory_order_relaxed).all() != pCur.ptr() ) { + if ( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr() ) { bkoff(); goto try_again; } diff --git a/src/dhp_gc.cpp b/src/dhp_gc.cpp index ea41aa14..cd965982 100644 --- a/src/dhp_gc.cpp +++ b/src/dhp_gc.cpp @@ -46,23 +46,23 @@ namespace cds { namespace gc { namespace dhp { void insert( retired_ptr_node& node ) { - node.m_pNext = nullptr; + node.m_pNext.store( nullptr, atomics::memory_order_relaxed ); item_type& refBucket = bucket( node ); if ( refBucket ) { item_type p = refBucket; do { if ( p->m_ptr.m_p == node.m_ptr.m_p ) { - assert( node.m_pNextFree == nullptr ); + assert( node.m_pNextFree.load( atomics::memory_order_relaxed ) == nullptr ); - node.m_pNextFree = p->m_pNextFree; - p->m_pNextFree = &node; + node.m_pNextFree.store( p->m_pNextFree.load( atomics::memory_order_relaxed ), atomics::memory_order_relaxed ); + p->m_pNextFree.store( &node, atomics::memory_order_relaxed ); return; } - p = p->m_pNext; + p = p->m_pNext.load(atomics::memory_order_relaxed); } while ( p ); - node.m_pNext = refBucket; + node.m_pNext.store( refBucket, atomics::memory_order_relaxed ); } refBucket = &node; } @@ -76,14 +76,14 @@ namespace cds { namespace gc { namespace dhp { while ( p ) { if ( p->m_ptr.m_p == ptr ) { if ( pPrev ) - pPrev->m_pNext = p->m_pNext; + pPrev->m_pNext.store( p->m_pNext.load(atomics::memory_order_relaxed ), atomics::memory_order_relaxed ); else - refBucket = p->m_pNext; - p->m_pNext = nullptr; + refBucket = p->m_pNext.load(atomics::memory_order_relaxed); + p->m_pNext.store( nullptr, atomics::memory_order_relaxed ); return p; } pPrev = p; - p = p->m_pNext; + p = p->m_pNext.load( atomics::memory_order_relaxed ); } return nullptr; @@ -103,22 +103,24 @@ namespace cds { namespace gc { namespace dhp { if ( !ret.first ) ret.first = pBucket; else - pTail->m_pNextFree = pBucket; + pTail->m_pNextFree.store( pBucket, atomics::memory_order_relaxed ); pTail = pBucket; for (;;) { - item_type pNext = pTail->m_pNext; + item_type pNext = pTail->m_pNext.load( atomics::memory_order_relaxed ); pTail->m_ptr.free(); - pTail->m_pNext = nullptr; + pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed ); - while ( pTail->m_pNextFree ) { - pTail = pTail->m_pNextFree; + while ( pTail->m_pNextFree.load( atomics::memory_order_relaxed )) { + pTail = pTail->m_pNextFree.load( atomics::memory_order_relaxed ); pTail->m_ptr.free(); - pTail->m_pNext = nullptr; + pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed ); } - if ( pNext ) - pTail = pTail->m_pNextFree = pNext; + if ( pNext ) { + pTail->m_pNextFree.store( pNext, atomics::memory_order_relaxed ); + pTail = pNext; + } else break; } @@ -126,7 +128,7 @@ namespace cds { namespace gc { namespace dhp { } if ( pTail ) - pTail->m_pNextFree = nullptr; + pTail->m_pNextFree.store( nullptr, atomics::memory_order_relaxed ); ret.second = pTail; return ret; } @@ -174,8 +176,8 @@ namespace cds { namespace gc { namespace dhp { // Get list of retired pointers details::retired_ptr_node * pHead = retiredList.first; while ( pHead ) { - details::retired_ptr_node * pNext = pHead->m_pNext; - pHead->m_pNextFree = nullptr; + details::retired_ptr_node * pNext = pHead->m_pNext.load( atomics::memory_order_relaxed ); + pHead->m_pNextFree.store( nullptr, atomics::memory_order_relaxed ); set.insert( *pHead ); pHead = pNext; } @@ -189,7 +191,7 @@ namespace cds { namespace gc { namespace dhp { for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) ) { // get guarded pointer - details::guard_data::guarded_ptr valGuarded = pGuard->pPost.load(atomics::memory_order_acquire); + details::guard_data::guarded_ptr valGuarded = pGuard->pPost.load(atomics::memory_order_acquire); if ( valGuarded ) { details::retired_ptr_node * pRetired = set.erase( valGuarded ); @@ -199,13 +201,15 @@ namespace cds { namespace gc { namespace dhp { // List is linked on m_pNextFree field if ( pBusyLast ) - pBusyLast->m_pNext = pRetired; + pBusyLast->m_pNext.store( pRetired, atomics::memory_order_relaxed ); else pBusyFirst = pRetired; pBusyLast = pRetired; ++nBusyCount; - while ( pBusyLast->m_pNextFree ) { - pBusyLast = pBusyLast->m_pNext = pBusyLast->m_pNextFree; + details::retired_ptr_node * p = pBusyLast->m_pNextFree.load(atomics::memory_order_relaxed); + while ( p != nullptr ) { + pBusyLast->m_pNext.store( p, atomics::memory_order_relaxed ); + pBusyLast = p; ++nBusyCount; } } -- 2.34.1