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 #if CDS_COMPILER == CDS_COMPILER_MSVC
21 # pragma warning(push)
22 // warning C4251: 'cds::gc::hzp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomic::atomic<T>'
23 // needs to have dll-interface to be used by clients of class 'cds::gc::hzp::GarbageCollector'
24 # pragma warning(disable: 4251)
28 namespace cds { namespace gc {
33 /// Gidenstam's memory reclamation schema (HRC)
37 - [2006] A.Gidenstam "Algorithms for synchronization and consistency
38 in concurrent system services", Chapter 5 "Lock-Free Memory Reclamation"
39 Thesis for the degree of Doctor of Philosophy
40 - [2005] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas "Allocating
41 memory in a lock-free manner", Proceedings of the 13th Annual European
42 Symposium on Algorithms (ESA 2005), Lecture Notes in Computer
43 Science Vol. 3669, pages 229
\96 242, Springer-Verlag, 2005
46 The \p %cds::gc::hrc namespace and its members are internal representation of the GC and should not be used directly.
47 Use \p cds::gc::HRC class in your code.
49 This reclamation schema combines Michael's Hazard Pointer schema (see \p cds::gc::hzp)
50 for deferred safe reclamation of unused objects and the reference counting
51 for controlling lifetime of the objects.
53 HRC garbage collector is a singleton. The main user-level part of HRC schema is
54 GC class and its nested classes. Before use any HRC-related class you must initialize HRC garbage collector
55 by contructing \p %cds::gc::HRC object in beginning of your <tt>main()</tt>.
56 See \p cds::gc::HRC class for explanation.
60 /// Base class for all HRC-based container's node
62 This interface is placed to the separate class since in the presence of a garbage collector
63 the lifetime of the node is greater than lifetime of its container.
64 Reclaimed node may be physically deleted later than its container.
65 So, the ContainerNode must be smarter than the usual.
71 friend class GarbageCollector;
72 friend class ThreadGC;
75 unsigned_ref_counter m_RC ; ///< reference counter
76 atomics::atomic<bool> m_bTrace ; ///< \p true - node is tracing by Scan
77 atomics::atomic<bool> m_bDeleted ; ///< \p true - node is deleted
81 ContainerNode() ; // inline, see hrc_inline.h
82 virtual ~ContainerNode() ; // inline, see hrc_inline.h
86 /// Returns count of reference for the node
87 unsigned_ref_counter::ref_counter_type getRefCount() const CDS_NOEXCEPT
92 /// Increments the reference counter of the node
93 void incRefCount() CDS_NOEXCEPT
98 /// Decrements the reference counter of the node. Returns \p true if ref counter is 0.
99 bool decRefCount() CDS_NOEXCEPT
104 /// Returns the mark whether the node is deleted
105 bool isDeleted() const CDS_NOEXCEPT
107 return m_bDeleted.load( atomics::memory_order_acquire );
112 void clean( atomics::memory_order order ) CDS_NOEXCEPT
114 m_bDeleted.store( false, order );
115 m_bTrace.store( false, order );
119 protected: // GC interface
121 [Gidenstam 2006]: "The procedure \p CleanUpNode will make sure that all claimed references from
122 the links of the given node will only point to active nodes, thus removing redundant
123 passages through an arbitrary number of deleted nodes"
125 The pseudocode of this method must be like following:
127 void cleanUp( ThreadGC * pGC )
128 for all x where link[x] of node is reference-counted do
131 if node1 != nullptr and node1.m_bDeleted then
132 node2 := node1->link[x];
133 pGC->CASRef( this->link[x], node1, node2 );
134 pGC->releaseRef( node2 );
135 pGC->releaseRef( node1 );
137 pGC->releaseRef(node1);
140 Be aware to use hazard pointers inside implementation of this method. cleanUp is called from
141 the container's method when deleting the nodes. However, some hazard pointers may be occupied
142 by container's method. You should allocate new hazard pointers inside \p cleanUp method, for example:
144 gc::hrc::AutoHPArray<2> hpArr( *pGC );
147 virtual void cleanUp( ThreadGC * pGC ) = 0;
150 [Gidenstam 2006]: "The procedure \p TerminateNode will make sure that none of the links in the
151 given node will have any claim on any other node. TerminateNode is called on
152 a deleted node when there are no claims from any other node or thread to the
155 The pseudocode of this method must be like following:
157 void terminate( ThreadGC * pGC, bool bConcurrent)
159 for all this->link where link is reference-counted do
162 for all this->link where link is reference-counted do
163 repeat node1 := link;
164 until pGC->CASRef(link,node1,nullptr);
167 virtual void terminate( ThreadGC * pGC, bool bConcurrent ) = 0;
170 /// Method to destroy (deallocate) node. Depends on node's allocator
171 //virtual void destroy() = 0;
175 /// HRC GC implementation details
178 /// Hazard pointer guard
179 typedef gc::hzp::details::HPGuardT<ContainerNode *> HPGuard;
181 /// Array of hazard pointers.
183 This is wrapper for cds::gc::hzp::details::HPArray class
185 template <size_t Count> using HPArray = gc::hzp::details::HPArrayT<ContainerNode *, Count >;
187 /// HP record of the thread
189 This structure is single writer - multiple reader type. The writer is the thread owned the record
191 struct thread_descriptor {
192 typedef ContainerNode * hazard_ptr ; ///< base type of hazard pointer
194 hzp::details::HPAllocator<hazard_ptr> m_hzp ; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependence
195 details::retired_vector m_arrRetired ; ///< array of retired pointers
198 thread_descriptor( const GarbageCollector& HzpMgr ) ; // inline
203 /// clear all hazard pointers
209 } // namespace details
212 /// Gidenstam's Garbage Collector
214 This GC combines Hazard Pointers (HP) reclamation method by Michael's and the well-known reference counting
215 reclamation schema. The HP method is light-weight algorithm guarding local references only. Reference counting
216 schema is harder than HP with relation to the performance but can guard global references too.
217 Using Gidenstam's GC it can be possible to safely introduce to the lock-free data structures
218 very useful concepts like iterators.
220 GarbageCollector is the singleton.
222 class CDS_EXPORT_API GarbageCollector
225 typedef cds::atomicity::event_counter event_counter ; ///< event counter type
227 /// GC internal statistics
228 struct internal_state {
229 size_t nHPCount ; ///< HP count per thread (const)
230 size_t nMaxThreadCount ; ///< Max thread count (const)
231 size_t nMaxRetiredPtrCount ; ///< Max retired pointer count per thread (const)
232 size_t nHRCRecSize ; ///< Size of HRC record, bytes (const)
234 size_t nHRCRecAllocated ; ///< Count of HRC record allocations
235 size_t nHRCRecUsed ; ///< Count of HRC record used
236 size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers
237 size_t nRetiredPtrInFreeHRCRecs; ///< Count of retired pointer in free (unused) HP records
240 event_counter::value_type evcAllocHRCRec ; ///< Event count of thread descriptor allocation
241 event_counter::value_type evcRetireHRCRec ; ///< Event count of thread descriptor reclamation
242 event_counter::value_type evcAllocNewHRCRec ; ///< Event count of new thread descriptor allocation
243 event_counter::value_type evcDeleteHRCRec ; ///< Event count of thread descriptor deletion
244 event_counter::value_type evcScanCall ; ///< Number of calls Scan
245 event_counter::value_type evcHelpScanCalls ; ///< Number of calls HelpScan
246 event_counter::value_type evcCleanUpAllCalls ; ///< Number of calls CleanUpAll
247 event_counter::value_type evcDeletedNode ; ///< Node deletion event counter
248 event_counter::value_type evcScanGuarded ; ///< Count of retired nodes that could not be deleted on Scan phase
249 event_counter::value_type evcScanClaimGuarded ; ///< Count of retired node that could not be deleted on Scan phase because of m_nClaim != 0
252 event_counter::value_type evcNodeConstruct ; ///< Count of constructed ContainerNode
253 event_counter::value_type evcNodeDestruct ; ///< Count of destructed ContainerNode
257 /// "Global GC object is nullptr" exception
258 CDS_DECLARE_EXCEPTION( HRCGarbageCollectorEmpty, "Global cds::gc::hrc::GarbageCollector is NULL" );
260 /// Not enough required Hazard Pointer count
261 CDS_DECLARE_EXCEPTION( HRCTooMany, "Not enough required Hazard Pointer count" );
264 /// Internal statistics by events
266 event_counter m_AllocHRCThreadDesc ; ///< Event count of thread descriptor allocation
267 event_counter m_RetireHRCThreadDesc ; ///< Event count of thread descriptor reclamation
268 event_counter m_AllocNewHRCThreadDesc ; ///< Event count of new thread descriptor allocation
269 event_counter m_DeleteHRCThreadDesc ; ///< Event count of deletion of thread descriptor
270 event_counter m_ScanCalls ; ///< Number of calls Scan
271 event_counter m_HelpScanCalls ; ///< Number of calls HelpScan
272 event_counter m_CleanUpAllCalls ; ///< Number of calls CleanUpAll
274 event_counter m_DeletedNode ; ///< Node deletion event counter
275 event_counter m_ScanGuarded ; ///< Count of retired nodes that could not be deleted on Scan phase
276 event_counter m_ScanClaimGuarded ; ///< Count of retired node that could not be deleted on Scan phase because of m_nClaim != 0
279 event_counter m_NodeConstructed ; ///< Count of ContainerNode constructed
280 event_counter m_NodeDestructed ; ///< Count of ContainerNode destructed
284 /// HRC control structure of global thread list
285 struct thread_list_node: public details::thread_descriptor
287 thread_list_node * m_pNext ; ///< next list record
288 ThreadGC * m_pOwner ; ///< Owner of record
289 atomics::atomic<cds::OS::ThreadId> m_idOwner ; ///< Id of thread owned; 0 - record is free
290 bool m_bFree ; ///< Node is help-scanned
293 thread_list_node( const GarbageCollector& HzpMgr )
294 : thread_descriptor( HzpMgr ),
297 m_idOwner(cds::OS::c_NullThreadId),
303 assert( m_pOwner == nullptr );
304 assert( m_idOwner.load( atomics::memory_order_relaxed ) == cds::OS::c_NullThreadId );
310 atomics::atomic<thread_list_node *> m_pListHead ; ///< Head of thread list
312 static GarbageCollector * m_pGC ; ///< HRC garbage collector instance
314 statistics m_Stat ; ///< Internal statistics
315 bool m_bStatEnabled ; ///< @a true - accumulate internal statistics
317 const size_t m_nHazardPointerCount ; ///< max count of thread's hazard pointer
318 const size_t m_nMaxThreadCount ; ///< max count of thread
319 const size_t m_nMaxRetiredPtrCount ; ///< max count of retired ptr per thread
324 size_t nHazardPtrCount, ///< number of hazard pointers
325 size_t nMaxThreadCount, ///< max number of threads
326 size_t nRetiredNodeArraySize ///< size of array of retired node
331 /// Allocates new HRC control structure from the heap (using operator new)
332 thread_list_node * newHRCThreadDesc();
334 /// Deletes \p pNode control structure
335 void deleteHRCThreadDesc( thread_list_node * pNode );
337 /// Clears retired nodes of \p pNode control structure
338 void clearHRCThreadDesc( thread_list_node * pNode );
340 /// Finds HRC control structure for current thread
341 thread_list_node * getHRCThreadDescForCurrentThread() const;
344 /// Create global instance of GarbageCollector
345 static void CDS_STDCALL Construct(
346 size_t nHazardPtrCount = 0, ///< number of hazard pointers
347 size_t nMaxThreadCount = 0, ///< max threads count
348 size_t nMaxNodeLinkCount = 0, ///< max number of links a @ref ContainerNode can contain
349 size_t nMaxTransientLinks = 0 ///< max number of links in live nodes that may transiently point to a deleted node
352 /// Destroy global instance of GarbageCollector
353 static void CDS_STDCALL Destruct();
355 /// Get global instance of GarbageCollector
356 static GarbageCollector& instance()
359 throw HRCGarbageCollectorEmpty();
363 /// Checks if global GC object is constructed and may be used
366 return m_pGC != nullptr;
369 /// Get max count of hazard pointers as defined in @ref Construct call
370 size_t getHazardPointerCount() const
372 return m_nHazardPointerCount;
375 /// Get max thread count as defined in @ref Construct call
376 size_t getMaxThreadCount() const
378 return m_nMaxThreadCount;
381 /// Get max retired pointers count. It is calculated by the parameters of @ref Construct call
382 size_t getMaxRetiredPtrCount() const
384 return m_nMaxRetiredPtrCount;
387 /// Get internal statistics
388 internal_state& getInternalState( internal_state& stat) const;
390 /// Check if statistics enabled
391 bool isStatisticsEnabled() const
393 return m_bStatEnabled;
396 /// Enable internal statistics
397 bool enableStatistics( bool bEnable )
399 bool bCurEnabled = m_bStatEnabled;
400 m_bStatEnabled = bEnable;
404 /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
406 If \p nRequiredCount > getHazardPointerCount() then the exception HZPTooMany is thrown
408 static void checkHPCount( unsigned int nRequiredCount )
410 if ( instance().getHazardPointerCount() < nRequiredCount )
414 public: // Internals for threads
416 /// Allocates HRC thread descriptor (thread interface)
417 details::thread_descriptor * allocateHRCThreadDesc( ThreadGC * pThreadGC );
419 /// Retires HRC thread descriptor (thread interface)
420 void retireHRCThreadDesc( details::thread_descriptor * pRec );
422 /// The main method of GC
424 The procedure searches through all not yet reclaimed nodes deleted by this thread
425 and reclaim only those that does not have any matching hazard pointers and do not have any
426 counted references from any links inside of nodes.
427 @a Scan is called in context of thread owned \p pRec.
429 void Scan( ThreadGC * pThreadGC );
431 /// Manage free thread_descriptor records and move all retired pointers to \p pThreadGC
432 void HelpScan( ThreadGC * pThreadGC );
436 The procedure try to remove redundant claimed references from links in deleted nodes
437 that has been deleted by any thread. \p pThreadGC - ThreadGC of calling thread
439 void CleanUpAll( ThreadGC * pThreadGC );
442 void try_retire( ThreadGC * pThreadGC ) ; // inline in hrc_inline.h
448 void dbgNodeConstructed() { ++m_Stat.m_NodeConstructed; }
449 void dbgNodeDestructed() { ++m_Stat.m_NodeDestructed; }
457 /// Thread's Garbage collector
459 To use HRC reclamation schema each thread object must be linked with the object of ThreadGC class
460 that interacts with GarbageCollector global object. The linkage is performed by calling cds::threading \p Manager::attachThread()
461 on the start of each thread that uses HRC GC. Before terminating the thread linked to HRC GC it is necessary to call
462 cds::threading \p Manager::detachThread().
466 GarbageCollector& m_gc ; ///< master garbage collector
467 details::thread_descriptor * m_pDesc ; ///< descriptor of GC data for the thread
469 friend class GarbageCollector;
474 : m_gc( GarbageCollector::instance() )
478 ThreadGC( ThreadGC const& ) = delete;
486 /// Checks if thread GC is initialized
487 bool isInitialized() const { return m_pDesc != nullptr; }
489 /// Initialization. Multiple calls is allowed
493 m_pDesc = m_gc.allocateHRCThreadDesc( this );
496 /// Finalization. Multiple calls is allowed
502 details::thread_descriptor * pRec = m_pDesc;
505 m_gc.retireHRCThreadDesc( pRec );
508 public: // HRC garbage collector methods
510 /// Initializes HP guard \p guard
511 details::HPGuard& allocGuard()
513 assert( m_pDesc != nullptr );
514 return m_pDesc->m_hzp.alloc();
517 /// Frees HP guard \p guard
518 void freeGuard( details::HPGuard& guard )
520 assert( m_pDesc != nullptr );
521 m_pDesc->m_hzp.free( guard );
524 /// Initializes HP guard array \p arr
525 template <size_t Count>
526 void allocGuard( details::HPArray<Count>& arr )
528 assert( m_pDesc != nullptr );
529 m_pDesc->m_hzp.alloc( arr );
532 /// Frees HP guard array \p arr
533 template <size_t Count>
534 void freeGuard( details::HPArray<Count>& arr )
536 assert( m_pDesc != nullptr );
537 m_pDesc->m_hzp.free( arr );
540 /// Retire (deferred delete) node \p pNode guarded by \p hp hazard pointer
541 void retireNode( ContainerNode * pNode, details::HPGuard& hp, details::free_retired_ptr_func pFunc )
543 assert( !pNode->m_bDeleted.load( atomics::memory_order_relaxed ) );
544 assert( pNode == hp );
546 retireNode( pNode, pFunc );
550 /// Retire (deferred delete) node \p pNode. Do not use this function directly!
551 void retireNode( ContainerNode * pNode, details::free_retired_ptr_func pFunc )
553 assert( !pNode->m_bDeleted.load( atomics::memory_order_relaxed ) );
555 pNode->m_bDeleted.store( true, atomics::memory_order_release );
556 pNode->m_bTrace.store( false, atomics::memory_order_release );
558 m_pDesc->m_arrRetired.push( pNode, pFunc );
560 if ( m_pDesc->m_arrRetired.isFull() )
561 m_gc.try_retire( this );
567 m_gc.try_retire( this );
572 /// The procedure will try to remove redundant claimed references from link in deleted nodes that has been deleted by this thread
575 details::retired_vector::iterator itEnd = m_pDesc->m_arrRetired.end();
576 for ( details::retired_vector::iterator it = m_pDesc->m_arrRetired.begin(); it != itEnd; ++it ) {
577 details::retired_node& node = *it;
578 ContainerNode * pNode = node.m_pNode.load(atomics::memory_order_acquire);
579 if ( pNode && !node.m_bDone.load(atomics::memory_order_acquire) )
580 pNode->cleanUp( this );
589 details::HPGuard& m_hp ; ///< hazard pointer
590 ThreadGC& m_mgr ; ///< Thread GC.
593 typedef details::HPGuard::hazard_ptr hazard_ptr ; ///< Hazard pointer type
596 /// Allocates HP guard from \p mgr
597 AutoHPGuard( ThreadGC& mgr )
598 : m_hp( mgr.allocGuard() )
602 /// Allocates HP guard from \p mgr and protects the pointer \p p of type \p T
603 template <typename T>
604 AutoHPGuard( ThreadGC& mgr, T * p )
605 : m_hp( mgr.allocGuard() )
614 m_mgr.freeGuard( m_hp );
617 /// Returns thread GC
618 ThreadGC& getGC() const CDS_NOEXCEPT
624 template <typename T>
625 T * operator =( T * p ) CDS_NOEXCEPT
632 hazard_ptr get() const CDS_NOEXCEPT
638 /// Clears the hazard pointer
639 void clear() CDS_NOEXCEPT
645 /// Auto-managed array of hazard pointers
647 This class is wrapper around gc::hzp::details::HPArray class.
649 template <size_t Count>
650 class AutoHPArray: public details::HPArray<Count>
652 ThreadGC& m_mgr ; ///< Thread GC
655 /// Allocates array of HP guard from \p mgr
656 AutoHPArray( ThreadGC& mgr )
659 mgr.allocGuard( *this );
662 /// Frees array of HP guard
665 m_mgr.freeGuard( *this );
668 /// Returns thread GC
669 ThreadGC& getGC() const
677 }} // namespace cds::gc
679 #include <cds/gc/hrc/details/hrc_inline.h>
681 #if CDS_COMPILER == CDS_COMPILER_MSVC
682 # pragma warning(pop)
685 #endif // #ifndef __CDS_GC_HRC_HRC_H