#include <mutex> // unique_lock
#include <cds/algo/atomic.h>
+#include <cds/algo/int_algo.h>
#include <cds/gc/details/retired_ptr.h>
#include <cds/details/aligned_allocator.h>
#include <cds/details/allocator.h>
/// 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<retired_ptr_node *> m_pNext ; ///< next retired pointer in buffer
+ atomics::atomic<retired_ptr_node *> m_pNextFree ; ///< next item in free list of \p retired_ptr_node
};
/// Internal guard representation
{
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 ));
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 ) );
return m_nItemCount.fetch_add( nSize, atomics::memory_order_relaxed ) + 1;
}
- /// Result of \ref dhp_gc_privatve "privatize" function.
+ /// Result of \ref dhp_gc_privatize "privatize" function.
/**
The \p privatize function returns retired node list as \p first and the size of that list as \p second.
*/
typedef std::pair<retired_ptr_node *, size_t> privatize_result;
/// Gets current list of retired pointer and clears the list
- /**@anchor dhp_gc_privatve
+ /**@anchor dhp_gc_privatize
*/
privatize_result privatize() CDS_NOEXCEPT
{
privatize_result res;
- res.first = m_pHead.exchange( nullptr, atomics::memory_order_acq_rel );
// Item counter is needed only as a threshold for \p scan() function
// So, we may clear the item counter without synchronization with m_pHead
res.second = m_nItemCount.exchange( 0, atomics::memory_order_relaxed );
+
+ res.first = m_pHead.exchange( nullptr, atomics::memory_order_acq_rel );
+
return res;
}
/// Pool block
struct block {
- block * pNext; ///< next block
- item items[m_nItemPerBlock]; ///< item array
+ atomics::atomic<block *> pNext; ///< next block
+ item items[m_nItemPerBlock]; ///< item array
};
atomics::atomic<block *> 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
+ unsigned int const m_nEpochBitmask; ///< Epoch bitmask (log2( m_nEpochCount))
atomics::atomic<unsigned int> m_nCurEpoch; ///< Current epoch
- atomics::atomic<item *> m_pEpochFree[c_nEpochCount]; ///< List of free item per epoch
+ atomics::atomic<item *>* m_pEpochFree; ///< List of free item per epoch
atomics::atomic<item *> m_pGlobalFreeHead; ///< Head of unallocated item list
- cds::details::Allocator< block, Alloc > m_BlockAllocator ; ///< block allocator
+ typedef cds::details::Allocator< block, Alloc > block_allocator;
+ typedef cds::details::Allocator< atomics::atomic<item *>, Alloc > epoch_array_alloc;
private:
void allocNewBlock()
{
// allocate new block
- block * pNew = m_BlockAllocator.New();
+ block * pNew = block_allocator().New();
// 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 ));
}
unsigned int current_epoch() const CDS_NOEXCEPT
{
- return m_nCurEpoch.load(atomics::memory_order_acquire) & (c_nEpochCount - 1);
+ return m_nCurEpoch.load(atomics::memory_order_acquire) & m_nEpochBitmask;
}
unsigned int next_epoch() const CDS_NOEXCEPT
{
- return (m_nCurEpoch.load(atomics::memory_order_acquire) - 1) & (c_nEpochCount - 1);
+ return (m_nCurEpoch.load(atomics::memory_order_acquire) - 1) & m_nEpochBitmask;
}
public:
- retired_ptr_pool()
+ retired_ptr_pool( unsigned int nEpochCount = 8 )
: m_pBlockListHead( nullptr )
+ , m_nEpochBitmask( static_cast<unsigned int>(beans::ceil2(nEpochCount)) - 1 )
, m_nCurEpoch(0)
+ , m_pEpochFree( epoch_array_alloc().NewArray( m_nEpochBitmask + 1))
, m_pGlobalFreeHead( nullptr )
{
- for (unsigned int i = 0; i < sizeof(m_pEpochFree)/sizeof(m_pEpochFree[0]); ++i )
+
+ for (unsigned int i = 0; i <= m_nEpochBitmask; ++i )
m_pEpochFree[i].store( nullptr, atomics::memory_order_relaxed );
allocNewBlock();
~retired_ptr_pool()
{
+ block_allocator a;
block * p;
for ( block * pBlock = m_pBlockListHead.load(atomics::memory_order_relaxed); pBlock; pBlock = p ) {
- p = pBlock->pNext;
- m_BlockAllocator.Delete( pBlock );
+ p = pBlock->pNext.load( atomics::memory_order_relaxed );
+ a.Delete( pBlock );
}
+
+ epoch_array_alloc().Delete( m_pEpochFree, m_nEpochBitmask + 1 );
}
/// Increments current epoch
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;
}
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 ));
}
};
: m_pGuard( nullptr )
{}
- /// Ñopy-ctor is disabled
+ /// Copy-ctor is disabled
guard( guard const& ) = delete;
/// Move-ctor is disabled
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: \91cds::gc::dhp::details::guard_data* cds::gc::dhp::details::guard::m_pGuard\92 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
private:
static GarbageCollector * m_pManager ; ///< GC global instance
+ atomics::atomic<size_t> m_nLiberateThreshold; ///< Max size of retired pointer buffer to call \p scan()
+ const size_t m_nInitialThreadGuardCount; ///< Initial count of guards allocated for ThreadGC
+
details::guard_allocator<> m_GuardPool ; ///< Guard pool
details::retired_ptr_pool<> m_RetiredAllocator ; ///< Pool of free retired pointers
details::retired_ptr_buffer m_RetiredBuffer ; ///< Retired pointer buffer for liberating
- atomics::atomic<size_t> m_nLiberateThreshold; ///< Max size of retired pointer buffer to call \p scan()
- const size_t m_nInitialThreadGuardCount; ///< Initial count of guards allocated for ThreadGC
-
internal_stat m_stat ; ///< Internal statistics
bool m_bStatEnabled ; ///< Internal Statistics enabled
After calling of this function you may use CDS data structures based on cds::gc::DHP.
\par Parameters
- \li \p nLiberateThreshold - \p scan() threshold. When count of retired pointers reaches this value,
+ - \p nLiberateThreshold - \p scan() threshold. When count of retired pointers reaches this value,
the \ref dhp_gc_liberate "scan()" member function would be called for freeing retired pointers.
If \p nLiberateThreshold <= 1, \p scan() would called after each \ref dhp_gc_retirePtr "retirePtr" call.
- \li \p nInitialThreadGuardCount - initial count of guard allocated for ThreadGC. When a thread
+ - \p nInitialThreadGuardCount - initial count of guard allocated for ThreadGC. When a thread
is initialized the GC allocates local guard pool for the thread from common guard pool.
By perforce the local thread's guard pool is grown automatically from common pool.
When the thread terminated its guard pool is backed to common GC's pool.
+ - \p nEpochCount: internally, DHP memory manager uses epoch-based schema to solve
+ ABA problem for internal data. \p nEpochCount specifies the epoch count,
+ i.e. the count of simultaneously working threads that remove the elements
+ of DHP-based concurrent data structure. Default value is 8.
*/
static void CDS_STDCALL Construct(
size_t nLiberateThreshold = 1024
, size_t nInitialThreadGuardCount = 8
+ , size_t nEpochCount = 8
);
/// Destroys DHP memory manager
}
private:
- GarbageCollector( size_t nLiberateThreshold, size_t nInitialThreadGuardCount );
+ GarbageCollector( size_t nLiberateThreshold, size_t nInitialThreadGuardCount, size_t nEpochCount );
~GarbageCollector();
};
projects / libcds.git / blobdiff