3 #ifndef __CDS_GC_HP_HP_H
4 #define __CDS_GC_HP_HP_H
7 #include <cds/cxx11_atomic.h>
8 #include <cds/os/thread.h>
9 #include <cds/gc/hp/details/hp_fwd.h>
10 #include <cds/gc/hp/details/hp_alloc.h>
11 #include <cds/gc/hp/details/hp_retired.h>
13 #if CDS_COMPILER == CDS_COMPILER_MSVC
14 # pragma warning(push)
15 // warning C4251: 'cds::gc::hp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomic::atomic<T>'
16 // needs to have dll-interface to be used by clients of class 'cds::gc::hp::GarbageCollector'
17 # pragma warning(disable: 4251)
22 2007.12.24 khizmax Add statistics and CDS_GATHER_HAZARDPTR_STAT macro
23 2008.03.06 khizmax Refactoring: implementation of HazardPtrMgr is moved to hazardptr.cpp
24 2008.03.08 khizmax Remove HazardPtrMgr singleton. Now you must initialize/destroy HazardPtrMgr calling
25 HazardPtrMgr::Construct / HazardPtrMgr::Destruct before use (usually in main() function).
26 2008.12.06 khizmax Refactoring. Changes class name, namespace hierarchy, all helper defs have been moved to details namespace
27 2010.01.27 khizmax Introducing memory order constraint
32 @page cds_garbage_collectors_comparison GC comparison
33 @ingroup cds_garbage_collector
39 <th>%cds::gc::DHP</th>
42 <td>Implementation quality</td>
47 <td>Performance rank (1 - slowest, 5 - fastest)</td>
52 <td>Max number of guarded (hazard) pointers per thread</td>
53 <td>limited (specifies in GC object ctor)</td>
54 <td>unlimited (dynamically allocated when needed)</td>
57 <td>Max number of retired pointers<sup>1</sup></td>
62 <td>Array of retired pointers</td>
63 <td>preallocated for each thread, limited in size</td>
64 <td>global for the entire process, unlimited (dynamically allocated when needed)</td>
67 <td>Support direct pointer to item of lock-free container (useful for iterators)</td>
68 <td>not supported</td>
69 <td>not supported</td>
73 <sup>1</sup>Unbounded count of retired pointer means a possibility of memory exhaustion.
76 /// Different safe memory reclamation schemas (garbage collectors)
77 /** @ingroup cds_garbage_collector
79 This namespace specifies different safe memory reclamation (SMR) algorithms.
80 See \ref cds_garbage_collector "Garbage collectors"
84 /// Michael's Hazard Pointers reclamation schema
87 - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
88 - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
89 - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
92 The cds::gc::hp namespace and its members are internal representation of Hazard Pointer GC and should not be used directly.
93 Use cds::gc::HP class in your code.
95 Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is
96 GC class and its nested classes. Before use any HP-related class you must initialize HP garbage collector
97 by contructing cds::gc::HP object in beginning of your main().
98 See cds::gc::HP class for explanation.
103 /// Hazard pointer record of the thread
105 The structure of type "single writer - multiple reader": only the owner thread may write to this structure
106 other threads have read-only access.
109 HPAllocator<hazard_pointer> m_hzp ; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency
110 retired_vector m_arrRetired ; ///< Retired pointer array
113 HPRec( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
117 /// Clears all hazard pointers
123 } // namespace details
125 /// GarbageCollector::Scan phase strategy
127 See GarbageCollector::Scan for explanation
130 classic, ///< classic scan as described in Michael's works (see GarbageCollector::classic_scan)
131 inplace ///< inplace scan without allocation (see GarbageCollector::inplace_scan)
134 /// Hazard Pointer singleton
136 Safe memory reclamation schema by Michael "Hazard Pointers"
139 \li [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
140 \li [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
141 \li [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
144 class CDS_EXPORT_API GarbageCollector
147 typedef cds::atomicity::event_counter event_counter ; ///< event counter type
149 /// Internal GC statistics
150 struct InternalState {
151 size_t nHPCount ; ///< HP count per thread (const)
152 size_t nMaxThreadCount ; ///< Max thread count (const)
153 size_t nMaxRetiredPtrCount ; ///< Max retired pointer count per thread (const)
154 size_t nHPRecSize ; ///< Size of HP record, bytes (const)
156 size_t nHPRecAllocated ; ///< Count of HP record allocations
157 size_t nHPRecUsed ; ///< Count of HP record used
158 size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers
159 size_t nRetiredPtrInFreeHPRecs ; ///< Count of retired pointer in free (unused) HP records
161 event_counter::value_type evcAllocHPRec ; ///< Count of HPRec allocations
162 event_counter::value_type evcRetireHPRec ; ///< Count of HPRec retire events
163 event_counter::value_type evcAllocNewHPRec; ///< Count of new HPRec allocations from heap
164 event_counter::value_type evcDeleteHPRec ; ///< Count of HPRec deletions
166 event_counter::value_type evcScanCall ; ///< Count of Scan calling
167 event_counter::value_type evcHelpScanCall ; ///< Count of HelpScan calling
168 event_counter::value_type evcScanFromHelpScan;///< Count of Scan calls from HelpScan
170 event_counter::value_type evcDeletedNode ; ///< Count of deleting of retired objects
171 event_counter::value_type evcDeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
174 /// No GarbageCollector object is created
175 CDS_DECLARE_EXCEPTION( HZPManagerEmpty, "Global Hazard Pointer GarbageCollector is NULL" );
177 /// Not enough required Hazard Pointer count
178 CDS_DECLARE_EXCEPTION( HZPTooMany, "Not enough required Hazard Pointer count" );
181 /// Internal GC statistics
183 event_counter m_AllocHPRec ; ///< Count of HPRec allocations
184 event_counter m_RetireHPRec ; ///< Count of HPRec retire events
185 event_counter m_AllocNewHPRec ; ///< Count of new HPRec allocations from heap
186 event_counter m_DeleteHPRec ; ///< Count of HPRec deletions
188 event_counter m_ScanCallCount ; ///< Count of Scan calling
189 event_counter m_HelpScanCallCount ; ///< Count of HelpScan calling
190 event_counter m_CallScanFromHelpScan ; ///< Count of Scan calls from HelpScan
192 event_counter m_DeletedNode ; ///< Count of retired objects deleting
193 event_counter m_DeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
196 /// Internal list of cds::gc::hp::details::HPRec
197 struct hplist_node: public details::HPRec
199 hplist_node * m_pNextNode ; ///< next hazard ptr record in list
200 atomics::atomic<OS::ThreadId> m_idOwner ; ///< Owner thread id; 0 - the record is free (not owned)
201 atomics::atomic<bool> m_bFree ; ///< true if record if free (not owned)
204 hplist_node( const GarbageCollector& HzpMgr )
206 m_pNextNode( nullptr ),
207 m_idOwner( OS::c_NullThreadId ),
213 assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId );
214 assert( m_bFree.load(atomics::memory_order_relaxed) );
219 atomics::atomic<hplist_node *> m_pListHead ; ///< Head of GC list
221 static GarbageCollector * m_pHZPManager ; ///< GC instance pointer
223 Statistics m_Stat ; ///< Internal statistics
224 bool m_bStatEnabled ; ///< true - statistics enabled
226 const size_t m_nHazardPointerCount ; ///< max count of thread's hazard pointer
227 const size_t m_nMaxThreadCount ; ///< max count of thread
228 const size_t m_nMaxRetiredPtrCount ; ///< max count of retired ptr per thread
229 scan_type m_nScanType ; ///< scan type (see \ref scan_type enum)
235 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
236 size_t nMaxThreadCount = 0, ///< Max count of thread
237 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects
238 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
244 /// Allocate new HP record
245 hplist_node * NewHPRec();
247 /// Permanently deletes HPrecord \p pNode
249 Caveat: for performance reason this function is defined as inline and cannot be called directly
251 void DeleteHPRec( hplist_node * pNode );
253 /// Permanently deletes retired pointer \p p
255 Caveat: for performance reason this function is defined as inline and cannot be called directly
257 void DeletePtr( details::retired_ptr& p );
260 void detachAllThread();
264 /// Creates GarbageCollector singleton
266 GC is the singleton. If GC instance is not exist then the function creates the instance.
267 Otherwise it does nothing.
269 The Michael's HP reclamation schema depends of three parameters:
271 \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
272 the data structure algorithms. By default, if \p nHazardPtrCount = 0,
273 the function uses maximum of HP count for CDS library.
275 \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
277 \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
278 \p nHazardPtrCount * \p nMaxThreadCount.
279 Default is 2 * \p nHazardPtrCount * \p nMaxThreadCount.
281 static void CDS_STDCALL Construct(
282 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
283 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
284 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
285 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
288 /// Destroys global instance of GarbageCollector
290 The parameter \p bDetachAll should be used carefully: if its value is \p true,
291 then the destroying GC automatically detaches all attached threads. This feature
292 can be useful when you have no control over the thread termination, for example,
293 when \p libcds is injected into existing external thread.
295 static void CDS_STDCALL Destruct(
296 bool bDetachAll = false ///< Detach all threads
299 /// Returns pointer to GarbageCollector instance
300 static GarbageCollector& instance()
302 if ( !m_pHZPManager )
303 throw HZPManagerEmpty();
304 return *m_pHZPManager;
307 /// Checks if global GC object is constructed and may be used
310 return m_pHZPManager != nullptr;
313 /// Returns max Hazard Pointer count defined in construction time
314 size_t getHazardPointerCount() const { return m_nHazardPointerCount; }
316 /// Returns max thread count defined in construction time
317 size_t getMaxThreadCount() const { return m_nMaxThreadCount; }
319 /// Returns max size of retired objects array. It is defined in construction time
320 size_t getMaxRetiredPtrCount() const { return m_nMaxRetiredPtrCount; }
322 // Internal statistics
324 /// Get internal statistics
325 InternalState& getInternalState(InternalState& stat) const;
327 /// Checks if internal statistics enabled
328 bool isStatisticsEnabled() const { return m_bStatEnabled; }
330 /// Enables/disables internal statistics
331 bool enableStatistics( bool bEnable )
333 bool bEnabled = m_bStatEnabled;
334 m_bStatEnabled = bEnable;
338 /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
340 If \p nRequiredCount > getHazardPointerCount() then the exception HZPTooMany is thrown
342 static void checkHPCount( unsigned int nRequiredCount )
344 if ( instance().getHazardPointerCount() < nRequiredCount )
348 /// Get current scan strategy
349 scan_type getScanType() const
354 /// Set current scan strategy
355 /** @anchor hzp_gc_setScanType
356 Scan strategy changing is allowed on the fly.
359 scan_type nScanType ///< new scan strategy
362 m_nScanType = nScanType;
365 public: // Internals for threads
367 /// Allocates Hazard Pointer GC record. For internal use only
368 details::HPRec * AllocateHPRec();
370 /// Free HP record. For internal use only
371 void RetireHPRec( details::HPRec * pRec );
373 /// The main garbage collecting function
375 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
378 There are the following scan algorithm:
379 - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use
380 - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory
382 Use \ref hzp_gc_setScanType "setScanType" member function to setup appropriate scan algorithm.
384 void Scan( details::HPRec * pRec )
386 switch ( m_nScanType ) {
388 inplace_scan( pRec );
391 assert(false) ; // Forgotten something?..
393 classic_scan( pRec );
398 /// Helper scan routine
400 The function guarantees that every node that is eligible for reuse is eventually freed, barring
401 thread failures. To do so, after executing Scan, a thread executes a HelpScan,
402 where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
403 to thread's list of reclaimed pointers.
405 The function is called internally by Scan.
407 void HelpScan( details::HPRec * pThis );
410 /// Classic scan algorithm
411 /** @anchor hzp_gc_classic_scan
412 Classical scan algorithm as described in Michael's paper.
414 A scan includes four stages. The first stage involves scanning the array HP for non-null values.
415 Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer.
416 Only stage 1 accesses shared variables. The following stages operate only on private variables.
418 The second stage of a scan involves sorting local list of protected pointers to allow
419 binary search in the third stage.
421 The third stage of a scan involves checking each reclaimed node
422 against the pointers in local list of protected pointers. If the binary search yields
423 no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list
424 of reclaimed pointers.
426 The forth stage prepares new thread's private list of reclaimed pointers
427 that could not be freed during the current scan, where they remain until the next scan.
429 This algorithm allocates memory for internal HP array.
431 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
434 void classic_scan( details::HPRec * pRec );
436 /// In-place scan algorithm
437 /** @anchor hzp_gc_inplace_scan
438 Unlike the \ref hzp_gc_classic_scan "classic_scan" algorithm, \p inplace_scan does not allocate any memory.
439 All operations are performed in-place.
441 void inplace_scan( details::HPRec * pRec );
444 /// Thread's hazard pointer manager
446 To use Hazard Pointer reclamation schema each thread object must be linked with the object of ThreadGC class
447 that interacts with GarbageCollector global object. The linkage is performed by calling \ref cds_threading "cds::threading::Manager::attachThread()"
448 on the start of each thread that uses HP GC. Before terminating the thread linked to HP GC it is necessary to call
449 \ref cds_threading "cds::threading::Manager::detachThread()".
453 GarbageCollector& m_HzpManager ; ///< Hazard Pointer GC singleton
454 details::HPRec * m_pHzpRec ; ///< Pointer to thread's HZP record
457 /// Default constructor
459 : m_HzpManager( GarbageCollector::instance() ),
463 /// The object is not copy-constructible
464 ThreadGC( ThreadGC const& ) = delete;
471 /// Checks if thread GC is initialized
472 bool isInitialized() const { return m_pHzpRec != nullptr; }
474 /// Initialization. Repeat call is available
478 m_pHzpRec = m_HzpManager.AllocateHPRec();
481 /// Finalization. Repeat call is available
485 details::HPRec * pRec = m_pHzpRec;
487 m_HzpManager.RetireHPRec( pRec );
491 /// Initializes HP guard \p guard
492 details::HPGuard& allocGuard()
495 return m_pHzpRec->m_hzp.alloc();
498 /// Frees HP guard \p guard
499 void freeGuard( details::HPGuard& guard )
502 m_pHzpRec->m_hzp.free( guard );
505 /// Initializes HP guard array \p arr
506 template <size_t Count>
507 void allocGuard( details::HPArray<Count>& arr )
510 m_pHzpRec->m_hzp.alloc( arr );
513 /// Frees HP guard array \p arr
514 template <size_t Count>
515 void freeGuard( details::HPArray<Count>& arr )
518 m_pHzpRec->m_hzp.free( arr );
521 /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
522 template <typename T>
523 void retirePtr( T * p, void (* pFunc)(T *) )
525 retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc ) ) );
528 /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation
529 void retirePtr( const details::retired_ptr& p )
531 m_pHzpRec->m_arrRetired.push( p );
533 if ( m_pHzpRec->m_arrRetired.isFull() ) {
534 // Max of retired pointer count is reached. Do scan
542 m_HzpManager.Scan( m_pHzpRec );
543 m_HzpManager.HelpScan( m_pHzpRec );
550 This class encapsulates Hazard Pointer guard to protect a pointer against deletion .
551 It allocates one HP from thread's HP array in constructor and free the HP allocated in destruction time.
556 details::HPGuard& m_hp ; ///< Hazard pointer guarded
557 ThreadGC& m_gc ; ///< Thread GC
561 typedef details::HPGuard::hazard_ptr hazard_ptr ; ///< Hazard pointer type
563 /// Allocates HP guard from \p gc
564 AutoHPGuard( ThreadGC& gc )
565 : m_hp( gc.allocGuard() )
569 /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T
570 template <typename T>
571 AutoHPGuard( ThreadGC& gc, T * p )
572 : m_hp( gc.allocGuard() )
578 /// Frees HP guard. The pointer guarded may be deleted after this.
581 m_gc.freeGuard( m_hp );
584 /// Returns thread GC
585 ThreadGC& getGC() const
590 /// Protects the pointer \p p against reclamation (guards the pointer).
591 template <typename T>
592 T * operator =( T * p )
598 std::nullptr_t operator =(std::nullptr_t)
600 return m_hp = nullptr;
603 hazard_ptr get() const
610 /// Auto-managed array of hazard pointers
612 This class is wrapper around cds::gc::hp::details::HPArray class.
613 \p Count is the size of HP array
615 template <size_t Count>
616 class AutoHPArray: public details::HPArray<Count>
618 ThreadGC& m_mgr ; ///< Thread GC
621 /// Rebind array for other size \p COUNT2
622 template <size_t Count2>
624 typedef AutoHPArray<Count2> other ; ///< rebinding result
628 /// Allocates array of HP guard from \p mgr
629 AutoHPArray( ThreadGC& mgr )
632 mgr.allocGuard( *this );
635 /// Frees array of HP guard
638 m_mgr.freeGuard( *this );
641 /// Returns thread GC
642 ThreadGC& getGC() const { return m_mgr; }
646 }} // namespace cds::gc
649 #include <cds/gc/hp/details/hp_inline.h>
651 #if CDS_COMPILER == CDS_COMPILER_MSVC
652 # pragma warning(pop)
655 #endif // #ifndef __CDS_GC_HP_HP_H