3 #ifndef __CDS_GC_HRC_HRC_H
4 #define __CDS_GC_HRC_HRC_H
8 2008.03.08 Maxim.Khiszinsky Created
11 #include <cds/refcounter.h>
12 #include <cds/lock/spinlock.h>
13 #include <cds/gc/exception.h>
15 #include <cds/gc/hrc/details/hrc_fwd.h>
16 #include <cds/gc/hrc/details/hrc_retired.h>
18 #include <cds/gc/hzp/details/hp_alloc.h>
20 #include <cds/details/noncopyable.h>
22 #if CDS_COMPILER == CDS_COMPILER_MSVC
23 # pragma warning(push)
24 // warning C4251: 'cds::gc::hzp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomics::atomic<T>'
25 // needs to have dll-interface to be used by clients of class 'cds::gc::hzp::GarbageCollector'
26 # pragma warning(disable: 4251)
30 namespace cds { namespace gc {
35 /// Gidenstam's memory reclamation schema (HRC)
39 - [2006] A.Gidenstam "Algorithms for synchronization and consistency
40 in concurrent system services", Chapter 5 "Lock-Free Memory Reclamation"
41 Thesis for the degree of Doctor of Philosophy
42 - [2005] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas "Allocating
43 memory in a lock-free manner", Proceedings of the 13th Annual European
44 Symposium on Algorithms (ESA 2005), Lecture Notes in Computer
45 Science Vol. 3669, pages 229
\96 242, Springer-Verlag, 2005
48 The \p %cds::gc::hrc namespace and its members are internal representation of the GC and should not be used directly.
49 Use \p cds::gc::HRC class in your code.
51 This reclamation schema combines Michael's Hazard Pointer schema (see \p cds::gc::hzp)
52 for deferred safe reclamation of unused objects and the reference counting
53 for controlling lifetime of the objects.
55 HRC garbage collector is a singleton. The main user-level part of HRC schema is
56 GC class and its nested classes. Before use any HRC-related class you must initialize HRC garbage collector
57 by contructing \p %cds::gc::HRC object in beginning of your <tt>main()</tt>.
58 See \p cds::gc::HRC class for explanation.
62 /// Base class for all HRC-based container's node
64 This interface is placed to the separate class since in the presence of a garbage collector
65 the lifetime of the node is greater than lifetime of its container.
66 Reclaimed node may be physically deleted later than its container.
67 So, the ContainerNode must be smarter than the usual.
73 friend class GarbageCollector;
74 friend class ThreadGC;
77 unsigned_ref_counter m_RC ; ///< reference counter
78 CDS_ATOMIC::atomic<bool> m_bTrace ; ///< \p true - node is tracing by Scan
79 CDS_ATOMIC::atomic<bool> m_bDeleted ; ///< \p true - node is deleted
83 ContainerNode() ; // inline, see hrc_inline.h
84 virtual ~ContainerNode() ; // inline, see hrc_inline.h
88 /// Returns count of reference for the node
89 unsigned_ref_counter::ref_counter_type getRefCount() const CDS_NOEXCEPT
94 /// Increments the reference counter of the node
95 void incRefCount() CDS_NOEXCEPT
100 /// Decrements the reference counter of the node. Returns \p true if ref counter is 0.
101 bool decRefCount() CDS_NOEXCEPT
106 /// Returns the mark whether the node is deleted
107 bool isDeleted() const CDS_NOEXCEPT
109 return m_bDeleted.load( CDS_ATOMIC::memory_order_acquire );
114 void clean( CDS_ATOMIC::memory_order order ) CDS_NOEXCEPT
116 m_bDeleted.store( false, order );
117 m_bTrace.store( false, order );
121 protected: // GC interface
123 [Gidenstam 2006]: "The procedure \p CleanUpNode will make sure that all claimed references from
124 the links of the given node will only point to active nodes, thus removing redundant
125 passages through an arbitrary number of deleted nodes"
127 The pseudocode of this method must be like following:
129 void cleanUp( ThreadGC * pGC )
130 for all x where link[x] of node is reference-counted do
133 if node1 != NULL and node1.m_bDeleted then
134 node2 := node1->link[x];
135 pGC->CASRef( this->link[x], node1, node2 );
136 pGC->releaseRef( node2 );
137 pGC->releaseRef( node1 );
139 pGC->releaseRef(node1);
142 Be aware to use hazard pointers inside implementation of this method. cleanUp is called from
143 the container's method when deleting the nodes. However, some hazard pointers may be occupied
144 by container's method. You should allocate new hazard pointers inside \p cleanUp method, for example:
146 gc::hrc::AutoHPArray<2> hpArr( *pGC );
149 virtual void cleanUp( ThreadGC * pGC ) = 0;
152 [Gidenstam 2006]: "The procedure \p TerminateNode will make sure that none of the links in the
153 given node will have any claim on any other node. TerminateNode is called on
154 a deleted node when there are no claims from any other node or thread to the
157 The pseudocode of this method must be like following:
159 void terminate( ThreadGC * pGC, bool bConcurrent)
161 for all this->link where link is reference-counted do
164 for all this->link where link is reference-counted do
165 repeat node1 := link;
166 until pGC->CASRef(link,node1,NULL);
169 virtual void terminate( ThreadGC * pGC, bool bConcurrent ) = 0;
172 /// Method to destroy (deallocate) node. Depends on node's allocator
173 //virtual void destroy() = 0;
177 /// HRC GC implementation details
180 /// Hazard pointer guard
181 typedef gc::hzp::details::HPGuardT<ContainerNode *> HPGuard;
183 /// Array of hazard pointers.
185 This is wrapper for cds::gc::hzp::details::HPArray class
187 #ifdef CDS_CXX11_TEMPLATE_ALIAS_SUPPORT
188 template <size_t Count> using HPArray = gc::hzp::details::HPArrayT<ContainerNode *, Count >;
190 template <size_t Count>
191 class HPArray: public gc::hzp::details::HPArrayT<ContainerNode *, Count>
195 /// HP record of the thread
197 This structure is single writer - multiple reader type. The writer is the thread owned the record
199 struct thread_descriptor {
200 typedef ContainerNode * hazard_ptr ; ///< base type of hazard pointer
202 hzp::details::HPAllocator<hazard_ptr> m_hzp ; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependence
203 details::retired_vector m_arrRetired ; ///< array of retired pointers
206 thread_descriptor( const GarbageCollector& HzpMgr ) ; // inline
211 /// clear all hazard pointers
217 } // namespace details
220 /// Gidenstam's Garbage Collector
222 This GC combines Hazard Pointers (HP) reclamation method by Michael's and the well-known reference counting
223 reclamation schema. The HP method is light-weight algorithm guarding local references only. Reference counting
224 schema is harder than HP with relation to the performance but can guard global references too.
225 Using Gidenstam's GC it can be possible to safely introduce to the lock-free data structures
226 very useful concepts like iterators.
228 GarbageCollector is the singleton.
230 class CDS_EXPORT_API GarbageCollector
233 typedef cds::atomicity::event_counter event_counter ; ///< event counter type
235 /// GC internal statistics
236 struct internal_state {
237 size_t nHPCount ; ///< HP count per thread (const)
238 size_t nMaxThreadCount ; ///< Max thread count (const)
239 size_t nMaxRetiredPtrCount ; ///< Max retired pointer count per thread (const)
240 size_t nHRCRecSize ; ///< Size of HRC record, bytes (const)
242 size_t nHRCRecAllocated ; ///< Count of HRC record allocations
243 size_t nHRCRecUsed ; ///< Count of HRC record used
244 size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers
245 size_t nRetiredPtrInFreeHRCRecs; ///< Count of retired pointer in free (unused) HP records
248 event_counter::value_type evcAllocHRCRec ; ///< Event count of thread descriptor allocation
249 event_counter::value_type evcRetireHRCRec ; ///< Event count of thread descriptor reclamation
250 event_counter::value_type evcAllocNewHRCRec ; ///< Event count of new thread descriptor allocation
251 event_counter::value_type evcDeleteHRCRec ; ///< Event count of thread descriptor deletion
252 event_counter::value_type evcScanCall ; ///< Number of calls Scan
253 event_counter::value_type evcHelpScanCalls ; ///< Number of calls HelpScan
254 event_counter::value_type evcCleanUpAllCalls ; ///< Number of calls CleanUpAll
255 event_counter::value_type evcDeletedNode ; ///< Node deletion event counter
256 event_counter::value_type evcScanGuarded ; ///< Count of retired nodes that could not be deleted on Scan phase
257 event_counter::value_type evcScanClaimGuarded ; ///< Count of retired node that could not be deleted on Scan phase because of m_nClaim != 0
260 event_counter::value_type evcNodeConstruct ; ///< Count of constructed ContainerNode
261 event_counter::value_type evcNodeDestruct ; ///< Count of destructed ContainerNode
265 /// "Global GC object is NULL" exception
266 CDS_DECLARE_EXCEPTION( HRCGarbageCollectorEmpty, "Global cds::gc::hrc::GarbageCollector is NULL" );
268 /// Not enough required Hazard Pointer count
269 CDS_DECLARE_EXCEPTION( HRCTooMany, "Not enough required Hazard Pointer count" );
272 /// Internal statistics by events
274 event_counter m_AllocHRCThreadDesc ; ///< Event count of thread descriptor allocation
275 event_counter m_RetireHRCThreadDesc ; ///< Event count of thread descriptor reclamation
276 event_counter m_AllocNewHRCThreadDesc ; ///< Event count of new thread descriptor allocation
277 event_counter m_DeleteHRCThreadDesc ; ///< Event count of deletion of thread descriptor
278 event_counter m_ScanCalls ; ///< Number of calls Scan
279 event_counter m_HelpScanCalls ; ///< Number of calls HelpScan
280 event_counter m_CleanUpAllCalls ; ///< Number of calls CleanUpAll
282 event_counter m_DeletedNode ; ///< Node deletion event counter
283 event_counter m_ScanGuarded ; ///< Count of retired nodes that could not be deleted on Scan phase
284 event_counter m_ScanClaimGuarded ; ///< Count of retired node that could not be deleted on Scan phase because of m_nClaim != 0
287 event_counter m_NodeConstructed ; ///< Count of ContainerNode constructed
288 event_counter m_NodeDestructed ; ///< Count of ContainerNode destructed
292 /// HRC control structure of global thread list
293 struct thread_list_node: public details::thread_descriptor
295 thread_list_node * m_pNext ; ///< next list record
296 ThreadGC * m_pOwner ; ///< Owner of record
297 CDS_ATOMIC::atomic<cds::OS::ThreadId> m_idOwner ; ///< Id of thread owned; 0 - record is free
298 bool m_bFree ; ///< Node is help-scanned
301 thread_list_node( const GarbageCollector& HzpMgr )
302 : thread_descriptor( HzpMgr ),
303 m_pNext(null_ptr<thread_list_node *>()),
304 m_pOwner( null_ptr<ThreadGC *>() ),
305 m_idOwner( cds::OS::nullThreadId() ),
311 assert( m_pOwner == null_ptr<ThreadGC *>() );
312 assert( m_idOwner.load(CDS_ATOMIC::memory_order_relaxed) == cds::OS::nullThreadId() );
318 CDS_ATOMIC::atomic<thread_list_node *> m_pListHead ; ///< Head of thread list
320 static GarbageCollector * m_pGC ; ///< HRC garbage collector instance
322 statistics m_Stat ; ///< Internal statistics
323 bool m_bStatEnabled ; ///< @a true - accumulate internal statistics
325 const size_t m_nHazardPointerCount ; ///< max count of thread's hazard pointer
326 const size_t m_nMaxThreadCount ; ///< max count of thread
327 const size_t m_nMaxRetiredPtrCount ; ///< max count of retired ptr per thread
332 size_t nHazardPtrCount, ///< number of hazard pointers
333 size_t nMaxThreadCount, ///< max number of threads
334 size_t nRetiredNodeArraySize ///< size of array of retired node
339 /// Allocates new HRC control structure from the heap (using operator new)
340 thread_list_node * newHRCThreadDesc();
342 /// Deletes \p pNode control structure
343 void deleteHRCThreadDesc( thread_list_node * pNode );
345 /// Clears retired nodes of \p pNode control structure
346 void clearHRCThreadDesc( thread_list_node * pNode );
348 /// Finds HRC control structure for current thread
349 thread_list_node * getHRCThreadDescForCurrentThread() const;
352 /// Create global instance of GarbageCollector
353 static void CDS_STDCALL Construct(
354 size_t nHazardPtrCount = 0, ///< number of hazard pointers
355 size_t nMaxThreadCount = 0, ///< max threads count
356 size_t nMaxNodeLinkCount = 0, ///< max number of links a @ref ContainerNode can contain
357 size_t nMaxTransientLinks = 0 ///< max number of links in live nodes that may transiently point to a deleted node
360 /// Destroy global instance of GarbageCollector
361 static void CDS_STDCALL Destruct();
363 /// Get global instance of GarbageCollector
364 static GarbageCollector& instance()
367 throw HRCGarbageCollectorEmpty();
371 /// Checks if global GC object is constructed and may be used
374 return m_pGC != null_ptr<GarbageCollector *>();
377 /// Get max count of hazard pointers as defined in @ref Construct call
378 size_t getHazardPointerCount() const
380 return m_nHazardPointerCount;
383 /// Get max thread count as defined in @ref Construct call
384 size_t getMaxThreadCount() const
386 return m_nMaxThreadCount;
389 /// Get max retired pointers count. It is calculated by the parameters of @ref Construct call
390 size_t getMaxRetiredPtrCount() const
392 return m_nMaxRetiredPtrCount;
395 /// Get internal statistics
396 internal_state& getInternalState( internal_state& stat) const;
398 /// Check if statistics enabled
399 bool isStatisticsEnabled() const
401 return m_bStatEnabled;
404 /// Enable internal statistics
405 bool enableStatistics( bool bEnable )
407 bool bCurEnabled = m_bStatEnabled;
408 m_bStatEnabled = bEnable;
412 /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
414 If \p nRequiredCount > getHazardPointerCount() then the exception HZPTooMany is thrown
416 static void checkHPCount( unsigned int nRequiredCount )
418 if ( instance().getHazardPointerCount() < nRequiredCount )
422 public: // Internals for threads
424 /// Allocates HRC thread descriptor (thread interface)
425 details::thread_descriptor * allocateHRCThreadDesc( ThreadGC * pThreadGC );
427 /// Retires HRC thread descriptor (thread interface)
428 void retireHRCThreadDesc( details::thread_descriptor * pRec );
430 /// The main method of GC
432 The procedure searches through all not yet reclaimed nodes deleted by this thread
433 and reclaim only those that does not have any matching hazard pointers and do not have any
434 counted references from any links inside of nodes.
435 @a Scan is called in context of thread owned \p pRec.
437 void Scan( ThreadGC * pThreadGC );
439 /// Manage free thread_descriptor records and move all retired pointers to \p pThreadGC
440 void HelpScan( ThreadGC * pThreadGC );
444 The procedure try to remove redundant claimed references from links in deleted nodes
445 that has been deleted by any thread. \p pThreadGC - ThreadGC of calling thread
447 void CleanUpAll( ThreadGC * pThreadGC );
450 void try_retire( ThreadGC * pThreadGC ) ; // inline in hrc_inline.h
456 void dbgNodeConstructed() { ++m_Stat.m_NodeConstructed; }
457 void dbgNodeDestructed() { ++m_Stat.m_NodeDestructed; }
465 /// Thread's Garbage collector
467 To use HRC reclamation schema each thread object must be linked with the object of ThreadGC class
468 that interacts with GarbageCollector global object. The linkage is performed by calling cds::threading \p Manager::attachThread()
469 on the start of each thread that uses HRC GC. Before terminating the thread linked to HRC GC it is necessary to call
470 cds::threading \p Manager::detachThread().
472 class ThreadGC: cds::details::noncopyable
474 GarbageCollector& m_gc ; ///< master garbage collector
475 details::thread_descriptor * m_pDesc ; ///< descriptor of GC data for the thread
477 friend class GarbageCollector;
482 : m_gc( GarbageCollector::instance() )
483 , m_pDesc( null_ptr<details::thread_descriptor *>() )
491 /// Checks if thread GC is initialized
492 bool isInitialized() const { return m_pDesc != null_ptr<details::thread_descriptor *>() ; }
494 /// Initialization. Multiple calls is allowed
498 m_pDesc = m_gc.allocateHRCThreadDesc( this );
501 /// Finalization. Multiple calls is allowed
507 details::thread_descriptor * pRec = m_pDesc;
508 m_pDesc = null_ptr<details::thread_descriptor *>();
510 m_gc.retireHRCThreadDesc( pRec );
513 public: // HRC garbage collector methods
515 /// Initializes HP guard \p guard
516 details::HPGuard& allocGuard()
518 assert( m_pDesc != null_ptr<details::thread_descriptor *>() );
519 return m_pDesc->m_hzp.alloc();
522 /// Frees HP guard \p guard
523 void freeGuard( details::HPGuard& guard )
525 assert( m_pDesc != null_ptr<details::thread_descriptor *>() );
526 m_pDesc->m_hzp.free( guard );
529 /// Initializes HP guard array \p arr
530 template <size_t Count>
531 void allocGuard( details::HPArray<Count>& arr )
533 assert( m_pDesc != null_ptr<details::thread_descriptor *>() );
534 m_pDesc->m_hzp.alloc( arr );
537 /// Frees HP guard array \p arr
538 template <size_t Count>
539 void freeGuard( details::HPArray<Count>& arr )
541 assert( m_pDesc != null_ptr<details::thread_descriptor *>() );
542 m_pDesc->m_hzp.free( arr );
545 /// Retire (deferred delete) node \p pNode guarded by \p hp hazard pointer
546 void retireNode( ContainerNode * pNode, details::HPGuard& hp, details::free_retired_ptr_func pFunc )
548 assert( !pNode->m_bDeleted.load( CDS_ATOMIC::memory_order_relaxed ) );
549 assert( pNode == hp );
551 retireNode( pNode, pFunc );
555 /// Retire (deferred delete) node \p pNode. Do not use this function directly!
556 void retireNode( ContainerNode * pNode, details::free_retired_ptr_func pFunc )
558 assert( !pNode->m_bDeleted.load( CDS_ATOMIC::memory_order_relaxed ) );
560 pNode->m_bDeleted.store( true, CDS_ATOMIC::memory_order_release );
561 pNode->m_bTrace.store( false, CDS_ATOMIC::memory_order_release );
563 m_pDesc->m_arrRetired.push( pNode, pFunc );
565 if ( m_pDesc->m_arrRetired.isFull() )
566 m_gc.try_retire( this );
572 m_gc.try_retire( this );
577 /// The procedure will try to remove redundant claimed references from link in deleted nodes that has been deleted by this thread
580 details::retired_vector::iterator itEnd = m_pDesc->m_arrRetired.end();
581 for ( details::retired_vector::iterator it = m_pDesc->m_arrRetired.begin(); it != itEnd; ++it ) {
582 details::retired_node& node = *it;
583 ContainerNode * pNode = node.m_pNode.load(CDS_ATOMIC::memory_order_acquire);
584 if ( pNode && !node.m_bDone.load(CDS_ATOMIC::memory_order_acquire) )
585 pNode->cleanUp( this );
594 details::HPGuard& m_hp ; ///< hazard pointer
595 ThreadGC& m_mgr ; ///< Thread GC.
598 typedef details::HPGuard::hazard_ptr hazard_ptr ; ///< Hazard pointer type
601 /// Allocates HP guard from \p mgr
602 AutoHPGuard( ThreadGC& mgr )
603 : m_hp( mgr.allocGuard() )
607 /// Allocates HP guard from \p mgr and protects the pointer \p p of type \p T
608 template <typename T>
609 AutoHPGuard( ThreadGC& mgr, T * p )
610 : m_hp( mgr.allocGuard() )
619 m_mgr.freeGuard( m_hp );
622 /// Returns thread GC
623 ThreadGC& getGC() const CDS_NOEXCEPT
629 template <typename T>
630 T * operator =( T * p ) CDS_NOEXCEPT
637 hazard_ptr get() const CDS_NOEXCEPT
643 /// Clears the hazard pointer
644 void clear() CDS_NOEXCEPT
650 /// Auto-managed array of hazard pointers
652 This class is wrapper around gc::hzp::details::HPArray class.
654 template <size_t Count>
655 class AutoHPArray: public details::HPArray<Count>
657 ThreadGC& m_mgr ; ///< Thread GC
660 /// Allocates array of HP guard from \p mgr
661 AutoHPArray( ThreadGC& mgr )
664 mgr.allocGuard( *this );
667 /// Frees array of HP guard
670 m_mgr.freeGuard( *this );
673 /// Returns thread GC
674 ThreadGC& getGC() const
682 }} // namespace cds::gc
684 #include <cds/gc/hrc/details/hrc_inline.h>
686 #if CDS_COMPILER == CDS_COMPILER_MSVC
687 # pragma warning(pop)
690 #endif // #ifndef __CDS_GC_HRC_HRC_H