3 // Pass The Buck (PTB) Memory manager implementation
5 #include <cds/gc/ptb/ptb.h>
6 #include <cds/algo/int_algo.h>
8 #include <cds/details/hash_functor_selector.h>
9 #include <algorithm> // std::fill
11 namespace cds { namespace gc { namespace ptb {
16 typedef retired_ptr_node * item_type;
17 typedef cds::details::Allocator<item_type, CDS_DEFAULT_ALLOCATOR> allocator_type;
19 size_t const m_nBucketCount;
20 item_type * m_Buckets;
22 item_type& bucket( retired_ptr_node& node )
24 return bucket( node.m_ptr.m_p );
26 item_type& bucket( guard_data::guarded_ptr p )
28 return m_Buckets[ cds::details::hash<guard_data::guarded_ptr>()( p ) & (m_nBucketCount - 1) ];
32 liberate_set( size_t nBucketCount )
33 : m_nBucketCount( nBucketCount )
35 assert( nBucketCount > 0 );
36 assert( (nBucketCount & (nBucketCount - 1)) == 0 );
38 m_Buckets = allocator_type().NewArray( nBucketCount );
39 std::fill( m_Buckets, m_Buckets + nBucketCount, nullptr );
44 allocator_type().Delete( m_Buckets, m_nBucketCount );
47 void insert( retired_ptr_node& node )
49 node.m_pNext = nullptr;
51 item_type& refBucket = bucket( node );
53 item_type p = refBucket;
55 if ( p->m_ptr.m_p == node.m_ptr.m_p ) {
56 assert( node.m_pNextFree == nullptr );
58 node.m_pNextFree = p->m_pNextFree;
59 p->m_pNextFree = &node;
65 node.m_pNext = refBucket;
70 item_type erase( guard_data::guarded_ptr ptr )
72 item_type& refBucket = bucket( ptr );
73 item_type p = refBucket;
74 item_type pPrev = nullptr;
77 if ( p->m_ptr.m_p == ptr ) {
79 pPrev->m_pNext = p->m_pNext;
81 refBucket = p->m_pNext;
92 typedef std::pair<item_type, item_type> list_range;
96 item_type pTail = nullptr;
97 list_range ret = std::make_pair( pTail, pTail );
99 item_type const * pEndBucket = m_Buckets + m_nBucketCount;
100 for ( item_type * ppBucket = m_Buckets; ppBucket < pEndBucket; ++ppBucket ) {
101 item_type pBucket = *ppBucket;
106 pTail->m_pNextFree = pBucket;
110 item_type pNext = pTail->m_pNext;
112 pTail->m_pNext = nullptr;
114 while ( pTail->m_pNextFree ) {
115 pTail = pTail->m_pNextFree;
117 pTail->m_pNext = nullptr;
121 pTail = pTail->m_pNextFree = pNext;
129 pTail->m_pNextFree = nullptr;
136 GarbageCollector * GarbageCollector::m_pManager = NULL;
138 void CDS_STDCALL GarbageCollector::Construct(
139 size_t nLiberateThreshold
140 , size_t nInitialThreadGuardCount
144 m_pManager = new GarbageCollector( nLiberateThreshold, nInitialThreadGuardCount );
148 void CDS_STDCALL GarbageCollector::Destruct()
156 GarbageCollector::GarbageCollector( size_t nLiberateThreshold, size_t nInitialThreadGuardCount )
157 : m_nLiberateThreshold( nLiberateThreshold ? nLiberateThreshold : 1024 )
158 , m_nInitialThreadGuardCount( nInitialThreadGuardCount ? nInitialThreadGuardCount : 8 )
163 GarbageCollector::~GarbageCollector()
168 details::retired_ptr_node * pHead = nullptr;
169 details::retired_ptr_node * pTail = nullptr;
171 for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(CDS_ATOMIC::memory_order_relaxed)) {
172 details::guard_data::handoff_ptr h = pGuard->pHandOff;
173 pGuard->pHandOff = nullptr;
175 details::guard_data::handoff_ptr pNext = h->m_pNextFree;
181 pTail = pTail->m_pNextFree = h;
186 m_RetiredAllocator.free_range( pHead, pTail );
190 void GarbageCollector::liberate()
192 details::retired_ptr_buffer::privatize_result retiredList = m_RetiredBuffer.privatize();
193 if ( retiredList.first ) {
195 size_t nLiberateThreshold = m_nLiberateThreshold.load(CDS_ATOMIC::memory_order_relaxed);
196 details::liberate_set set( beans::ceil2( retiredList.second > nLiberateThreshold ? retiredList.second : nLiberateThreshold ) );
198 // Get list of retired pointers
199 details::retired_ptr_node * pHead = retiredList.first;
201 details::retired_ptr_node * pNext = pHead->m_pNext;
202 pHead->m_pNextFree = nullptr;
203 set.insert( *pHead );
208 for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(CDS_ATOMIC::memory_order_acquire) )
210 // get guarded pointer
211 details::guard_data::guarded_ptr valGuarded = pGuard->pPost.load(CDS_ATOMIC::memory_order_acquire);
214 details::retired_ptr_node * pRetired = set.erase( valGuarded );
216 // Retired pointer is being guarded
217 // pRetired is the head of retired pointers list for which the m_ptr.m_p field is equal
218 // List is linked on m_pNextFree field
221 details::retired_ptr_node * pNext = pRetired->m_pNextFree;
222 m_RetiredBuffer.push( *pRetired );
224 } while ( pRetired );
229 // Free all retired pointers
230 details::liberate_set::list_range range = set.free_all();
232 m_RetiredAllocator.inc_epoch();
235 assert( range.second != nullptr );
236 m_RetiredAllocator.free_range( range.first, range.second );
239 // liberate cycle did not free any retired pointer - double liberate threshold
240 m_nLiberateThreshold.compare_exchange_strong( nLiberateThreshold, nLiberateThreshold * 2, CDS_ATOMIC::memory_order_release, CDS_ATOMIC::memory_order_relaxed );
246 void GarbageCollector::liberate( details::liberate_set& set )
248 details::guard_data::handoff_ptr const nullHandOff = nullptr;
250 for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(CDS_ATOMIC::memory_order_acquire) )
252 // get guarded pointer
253 details::guard_data::guarded_ptr valGuarded = pGuard->pPost.load(CDS_ATOMIC::memory_order_acquire);
254 details::guard_data::handoff_ptr h;
257 details::retired_ptr_node * pRetired = set.erase( valGuarded );
259 // Retired pointer is being guarded
261 // pRetired is the head of retired pointers list for which the m_ptr.m_p field is equal
262 // List is linked on m_pNextFree field
264 // Now, try to set retired node pRetired as a hand-off node for the guard
265 cds::lock::Auto<details::guard_data::handoff_spin> al( pGuard->spinHandOff );
266 if ( valGuarded == pGuard->pPost.load(CDS_ATOMIC::memory_order_acquire) ) {
267 if ( pGuard->pHandOff && pGuard->pHandOff->m_ptr.m_p == pRetired->m_ptr.m_p ) {
268 h = nullHandOff ; //nullptr;
269 details::retired_ptr_node * pTail = pGuard->pHandOff;
270 while ( pTail->m_pNextFree )
271 pTail = pTail->m_pNextFree;
272 pTail->m_pNextFree = pRetired;
275 // swap h and pGuard->pHandOff
276 h = pGuard->pHandOff;
277 pGuard->pHandOff = pRetired;
284 cds::lock::Auto<details::guard_data::handoff_spin> al( pGuard->spinHandOff );
285 h = pGuard->pHandOff;
287 if ( h->m_ptr.m_p != valGuarded )
288 pGuard->pHandOff = nullHandOff;
295 cds::lock::Auto<details::guard_data::handoff_spin> al( pGuard->spinHandOff );
296 h = pGuard->pHandOff;
297 pGuard->pHandOff = nullHandOff;
300 // h is the head of a list linked on m_pNextFree field
307 }}} // namespace cds::gc::ptb