X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=src%2Fdhp_gc.cpp;h=0d08a55093250636c3fe3e47a351c9753b8c3131;hb=5b6c074304bb2881491815431764ad7fbfe14071;hp=1a2902a25295765f0c8817c0cdf45f78e2f5062c;hpb=755ecdb0ec193791bedb7e6a6308ce517ef797c5;p=libcds.git diff --git a/src/dhp_gc.cpp b/src/dhp_gc.cpp index 1a2902a2..0d08a550 100644 --- a/src/dhp_gc.cpp +++ b/src/dhp_gc.cpp @@ -1,11 +1,39 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -// Pass The Buck (PTB) Memory manager implementation + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + 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: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +// Dynamic Hazard Pointer memory manager implementation #include // std::fill #include // std::hash -#include +#include #include namespace cds { namespace gc { namespace dhp { @@ -19,11 +47,11 @@ namespace cds { namespace gc { namespace dhp { size_t const m_nBucketCount; item_type * m_Buckets; - item_type& bucket( retired_ptr_node& node ) + item_type& bucket( retired_ptr_node& node ) const { return bucket( node.m_ptr.m_p ); } - item_type& bucket( guard_data::guarded_ptr p ) + item_type& bucket( guard_data::guarded_ptr p ) const { return m_Buckets[ std::hash()( p ) & (m_nBucketCount - 1) ]; } @@ -46,47 +74,74 @@ 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; + item_type prev = nullptr; do { - if ( p->m_ptr.m_p == node.m_ptr.m_p ) { - assert( node.m_pNextFree == nullptr ); - - node.m_pNextFree = p->m_pNextFree; - p->m_pNextFree = &node; + if ( p->m_ptr.m_p >= node.m_ptr.m_p ) { + node.m_pNext.store( p, atomics::memory_order_relaxed ); + if ( prev ) + prev->m_pNext.store( &node, atomics::memory_order_relaxed ); + else + refBucket = &node; return; } - p = p->m_pNext; + prev = p; + p = p->m_pNext.load(atomics::memory_order_relaxed); } while ( p ); - node.m_pNext = refBucket; + assert( prev != nullptr ); + prev->m_pNext.store( &node, atomics::memory_order_relaxed ); } - refBucket = &node; + else + refBucket = &node; } - item_type erase( guard_data::guarded_ptr ptr ) + struct erase_result + { + item_type head; + item_type tail; + size_t size; + + erase_result() + : head( nullptr ) + , tail( nullptr ) + , size(0) + {} + }; + + erase_result erase( guard_data::guarded_ptr ptr ) { item_type& refBucket = bucket( ptr ); item_type p = refBucket; item_type pPrev = nullptr; - while ( p ) { + erase_result ret; + while ( p && p->m_ptr.m_p <= ptr ) { 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.load(atomics::memory_order_relaxed); + + if ( ret.head ) + ret.tail->m_pNext.store( p, atomics::memory_order_relaxed ); else - refBucket = p->m_pNext; - p->m_pNext = nullptr; - return p; + ret.head = p; + ret.tail = p; + ++ret.size; } - pPrev = p; - p = p->m_pNext; + else + pPrev = p; + p = p->m_pNext.load( atomics::memory_order_relaxed ); } - return nullptr; + if ( ret.tail ) + ret.tail->m_pNext.store( nullptr, atomics::memory_order_relaxed ); + return ret; } typedef std::pair list_range; @@ -100,25 +155,29 @@ namespace cds { namespace gc { namespace dhp { for ( item_type * ppBucket = m_Buckets; ppBucket < pEndBucket; ++ppBucket ) { item_type pBucket = *ppBucket; if ( pBucket ) { - if ( !ret.first ) - ret.first = pBucket; + if ( ret.first ) + pTail->m_pNextFree.store( pBucket, atomics::memory_order_relaxed ); else - pTail->m_pNextFree = pBucket; + ret.first = pBucket; 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 +185,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; } @@ -138,72 +197,80 @@ namespace cds { namespace gc { namespace dhp { void CDS_STDCALL GarbageCollector::Construct( size_t nLiberateThreshold , size_t nInitialThreadGuardCount + , size_t nEpochCount ) { if ( !m_pManager ) { - m_pManager = new GarbageCollector( nLiberateThreshold, nInitialThreadGuardCount ); + m_pManager = new GarbageCollector( nLiberateThreshold, nInitialThreadGuardCount, nEpochCount ); } } void CDS_STDCALL GarbageCollector::Destruct() { - if ( m_pManager ) { - delete m_pManager; - m_pManager = nullptr; - } + delete m_pManager; + m_pManager = nullptr; } - GarbageCollector::GarbageCollector( size_t nLiberateThreshold, size_t nInitialThreadGuardCount ) + GarbageCollector::GarbageCollector( size_t nLiberateThreshold, size_t nInitialThreadGuardCount, size_t nEpochCount ) : m_nLiberateThreshold( nLiberateThreshold ? nLiberateThreshold : 1024 ) , m_nInitialThreadGuardCount( nInitialThreadGuardCount ? nInitialThreadGuardCount : 8 ) - //, m_nInLiberate(0) - { - } + , m_RetiredAllocator( static_cast( nEpochCount ? nEpochCount : 16 )) + , m_bStatEnabled( false ) + {} GarbageCollector::~GarbageCollector() { - liberate(); + scan(); } - void GarbageCollector::liberate() + void GarbageCollector::scan() { details::retired_ptr_buffer::privatize_result retiredList = m_RetiredBuffer.privatize(); if ( retiredList.first ) { size_t nLiberateThreshold = m_nLiberateThreshold.load(atomics::memory_order_relaxed); - details::liberate_set set( beans::ceil2( retiredList.second > nLiberateThreshold ? retiredList.second : nLiberateThreshold ) ); + details::liberate_set set( beans::ceil2( retiredList.second > nLiberateThreshold ? retiredList.second : nLiberateThreshold )); // Get list of retired pointers + size_t nRetiredCount = 0; 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; + ++nRetiredCount; } // Liberate cycle - for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) ) + + details::retired_ptr_node dummy; + dummy.m_pNext.store( nullptr, atomics::memory_order_relaxed ); + details::retired_ptr_node * pBusyLast = &dummy; + size_t nBusyCount = 0; + + 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 ); - if ( pRetired ) { + auto retired = set.erase( valGuarded ); + if ( retired.head ) { // Retired pointer is being guarded - // pRetired is the head of retired pointers list for which the m_ptr.m_p field is equal - // List is linked on m_pNextFree field - - do { - details::retired_ptr_node * pNext = pRetired->m_pNextFree; - m_RetiredBuffer.push( *pRetired ); - pRetired = pNext; - } while ( pRetired ); + // [retired.head, retired.tail] is the list linked by m_pNext field + + pBusyLast->m_pNext.store( retired.head, atomics::memory_order_relaxed ); + pBusyLast = retired.tail; + nBusyCount += retired.size; } } } + // Place [dummy.m_pNext, pBusyLast] back to m_RetiredBuffer + if ( nBusyCount ) + m_RetiredBuffer.push_list( dummy.m_pNext.load(atomics::memory_order_relaxed), pBusyLast, nBusyCount ); + // Free all retired pointers details::liberate_set::list_range range = set.free_all(); @@ -213,8 +280,8 @@ namespace cds { namespace gc { namespace dhp { assert( range.second != nullptr ); m_RetiredAllocator.free_range( range.first, range.second ); } - else { - // liberate cycle did not free any retired pointer - double liberate threshold + else if ( nRetiredCount >= nLiberateThreshold ) { + // scan() cycle did not free any retired pointer - double scan() threshold m_nLiberateThreshold.compare_exchange_strong( nLiberateThreshold, nLiberateThreshold * 2, atomics::memory_order_release, atomics::memory_order_relaxed ); } }