X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fgc%2Fdetails%2Fdhp.h;h=3a882e9c3fb180da942ab0c19073be06ef0923ca;hp=3f30422d35858bd08fb7806abc6bce5433888ea3;hb=d5080a8e05bbdc0db483fbe13b3c236d49ba6262;hpb=79598e544ba2a25fe0877458a00223e29ae87487 diff --git a/cds/gc/details/dhp.h b/cds/gc/details/dhp.h index 3f30422d..3a882e9c 100644 --- a/cds/gc/details/dhp.h +++ b/cds/gc/details/dhp.h @@ -1,14 +1,14 @@ //$$CDS-header$$ -#ifndef __CDS_GC_DETAILS_DHP_H -#define __CDS_GC_DETAILS_DHP_H +#ifndef CDSLIB_GC_DETAILS_DHP_H +#define CDSLIB_GC_DETAILS_DHP_H #include // unique_lock #include #include #include #include -#include +#include #if CDS_COMPILER == CDS_COMPILER_MSVC # pragma warning(push) @@ -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 @@ -96,9 +96,9 @@ namespace cds { namespace gc { { cds::details::Allocator m_GuardAllocator ; ///< guard allocator - atomics::atomic m_GuardList ; ///< Head of allocated guard list (linked by guard_data::pGlobalNext field) - atomics::atomic m_FreeGuardList ; ///< Head of free guard list (linked by guard_data::pNextFree field) - SpinLock m_freeListLock ; ///< Access to m_FreeGuardList + atomics::atomic m_GuardList; ///< Head of allocated guard list (linked by guard_data::pGlobalNext field) + atomics::atomic m_FreeGuardList; ///< Head of free guard list (linked by guard_data::pNextFree field) + cds::sync::spin m_freeListLock; ///< Access to m_FreeGuardList /* Unfortunately, access to the list of free guard is lock-based. @@ -151,7 +151,7 @@ namespace cds { namespace gc { details::guard_data * pGuard; { - std::unique_lock al( m_freeListLock ); + std::unique_lock al( m_freeListLock ); pGuard = m_FreeGuardList.load(atomics::memory_order_relaxed); if ( pGuard ) m_FreeGuardList.store( pGuard->pNextFree.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed ); @@ -171,7 +171,7 @@ namespace cds { namespace gc { { pGuard->pPost.store( nullptr, atomics::memory_order_relaxed ); - std::unique_lock al( m_freeListLock ); + std::unique_lock al( m_freeListLock ); pGuard->pNextFree.store( m_FreeGuardList.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed ); m_FreeGuardList.store( pGuard, atomics::memory_order_relaxed ); } @@ -223,7 +223,7 @@ namespace cds { namespace gc { pLast = p; } - std::unique_lock al( m_freeListLock ); + std::unique_lock al( m_freeListLock ); pLast->pNextFree.store( m_FreeGuardList.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed ); m_FreeGuardList.store( pList, atomics::memory_order_relaxed ); } @@ -262,13 +262,28 @@ 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 )); return m_nItemCount.fetch_add( 1, atomics::memory_order_relaxed ) + 1; } + /// Pushes [pFirst, pLast] list linked by pNext field. + size_t push_list( retired_ptr_node* pFirst, retired_ptr_node* pLast, size_t nSize ) + { + assert( pFirst ); + assert( pLast ); + + retired_ptr_node * pHead = m_pHead.load( atomics::memory_order_acquire ); + do { + 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 ) ); + + return m_nItemCount.fetch_add( nSize, atomics::memory_order_relaxed ) + 1; + } + /// Result of \ref dhp_gc_privatve "privatize" function. /** The \p privatize function returns retired node list as \p first and the size of that list as \p second. @@ -311,17 +326,17 @@ 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 + atomics::atomic m_pBlockListHead; ///< head of of allocated block list // To solve ABA problem we use epoch-based approach - static const unsigned int c_nEpochCount = 4 ; ///< Max epoch count - atomics::atomic m_nCurEpoch ; ///< Current epoch - atomics::atomic m_pEpochFree[c_nEpochCount] ; ///< List of free item per epoch - atomics::atomic m_pGlobalFreeHead ; ///< Head of unallocated item list + static const unsigned int c_nEpochCount = 4; ///< Max epoch count + atomics::atomic m_nCurEpoch; ///< Current epoch + atomics::atomic m_pEpochFree[c_nEpochCount]; ///< List of free item per epoch + atomics::atomic m_pGlobalFreeHead; ///< Head of unallocated item list cds::details::Allocator< block, Alloc > m_BlockAllocator ; ///< block allocator @@ -334,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 )); } - // link new block to block list + // 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 )); } - // link block's items to free list + // 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 )); } @@ -383,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 ); } } @@ -394,7 +409,7 @@ namespace cds { namespace gc { m_nCurEpoch.fetch_add( 1, atomics::memory_order_acq_rel ); } - /// Allocates new retired pointer + /// Allocates the new retired pointer retired_ptr_node& alloc() { unsigned int nEpoch; @@ -403,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; } @@ -432,7 +453,7 @@ namespace cds { namespace gc { return node; } - /// Places the list (pHead, pTail) of retired pointers to pool (frees retired pointers) + /// Places the list [pHead, pTail] of retired pointers to pool (frees retired pointers) /** The list is linked on the m_pNextFree field */ @@ -445,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 )); } }; @@ -463,7 +484,7 @@ namespace cds { namespace gc { : m_pGuard( nullptr ) {} - /// Ñopy-ctor is disabled + /// Copy-ctor is disabled guard( guard const& ) = delete; /// Move-ctor is disabled @@ -510,7 +531,7 @@ namespace cds { namespace gc { public: // for ThreadGC. /* - GCC cannot compile code for template versions of ThreasGC::allocGuard/freeGuard, + GCC cannot compile code for template versions of ThreadGC::allocGuard/freeGuard, the compiler produces error: ‘cds::gc::dhp::details::guard_data* cds::gc::dhp::details::guard::m_pGuard’ is protected despite the fact that ThreadGC is declared as friend for guard class. Therefore, we have to add set_guard/get_guard public functions @@ -687,6 +708,7 @@ namespace cds { namespace gc { size_t m_nGuardCount ; ///< Total guard count size_t m_nFreeGuardCount ; ///< Count of free guard + //@cond InternalState() : m_nGuardCount(0) , m_nFreeGuardCount(0) @@ -699,6 +721,7 @@ namespace cds { namespace gc { return *this; } + //@endcond }; private: @@ -971,6 +994,7 @@ namespace cds { namespace gc { m_gc.retirePtr( p, pFunc ); } + /// Run retiring cycle void scan() { m_gc.scan(); @@ -984,4 +1008,4 @@ namespace cds { namespace gc { # pragma warning(pop) #endif -#endif // #ifndef __CDS_GC_DETAILS_DHP_H +#endif // #ifndef CDSLIB_GC_DETAILS_DHP_H