3 #ifndef __CDS_GC_HZP_HZP_H
4 #define __CDS_GC_HZP_HZP_H
6 #include <cds/cxx11_atomic.h>
7 #include <cds/os/thread.h>
8 #include <cds/gc/exception.h>
10 #include <cds/gc/hzp/details/hp_fwd.h>
11 #include <cds/gc/hzp/details/hp_alloc.h>
12 #include <cds/gc/hzp/details/hp_retired.h>
15 #include <cds/details/noncopyable.h>
17 #if CDS_COMPILER == CDS_COMPILER_MSVC
18 # pragma warning(push)
19 // warning C4251: 'cds::gc::hzp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomic::atomic<T>'
20 // needs to have dll-interface to be used by clients of class 'cds::gc::hzp::GarbageCollector'
21 # pragma warning(disable: 4251)
26 2007.12.24 khizmax Add statistics and CDS_GATHER_HAZARDPTR_STAT macro
27 2008.03.06 khizmax Refactoring: implementation of HazardPtrMgr is moved to hazardptr.cpp
28 2008.03.08 khizmax Remove HazardPtrMgr singleton. Now you must initialize/destroy HazardPtrMgr calling
29 HazardPtrMgr::Construct / HazardPtrMgr::Destruct before use (usually in main() function).
30 2008.12.06 khizmax Refactoring. Changes class name, namespace hierarchy, all helper defs have been moved to details namespace
31 2010.01.27 khizmax Introducing memory order constraint
36 @page cds_garbage_collectors_comparison GC comparison
37 @ingroup cds_garbage_collector
43 <th>%cds::gc::HRC</th>
44 <th>%cds::gc::PTB</th>
47 <td>Implementation quality</td>
53 <td>Performance rank (1 - slowest, 5 - fastest)</td>
59 <td>Max number of guarded (hazard) pointers per thread</td>
60 <td>limited (specifies in GC object ctor)</td>
61 <td>limited (specifies in GC object ctor)</td>
62 <td>unlimited (dynamically allocated when needed)</td>
65 <td>Max number of retired pointers<sup>1</sup></td>
71 <td>Array of retired pointers</td>
72 <td>preallocated for each thread, limited in size</td>
73 <td>preallocated for each thread, limited in size</td>
74 <td>global for the entire process, unlimited (dynamically allocated when needed)</td>
77 <td>Support direct pointer to item of lock-free container (useful for iterators)</td>
78 <td>not supported</td>
79 <td>potentially supported (not implemented)</td>
80 <td>not supported</td>
84 <sup>1</sup>Unbounded count of retired pointer means a possibility of memory exhaustion.
87 /// Different safe memory reclamation schemas (garbage collectors)
88 /** @ingroup cds_garbage_collector
90 This namespace specifies different safe memory reclamation (SMR) algorithms.
91 See \ref cds_garbage_collector "Garbage collectors"
95 /// Michael's Hazard Pointers reclamation schema
98 - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
99 - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
100 - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
103 The cds::gc::hzp namespace and its members are internal representation of Hazard Pointer GC and should not be used directly.
104 Use cds::gc::HP class in your code.
106 Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is
107 GC class and its nested classes. Before use any HP-related class you must initialize HP garbage collector
108 by contructing cds::gc::HP object in beginning of your main().
109 See cds::gc::HP class for explanation.
114 /// Hazard pointer record of the thread
116 The structure of type "single writer - multiple reader": only the owner thread may write to this structure
117 other threads have read-only access.
120 HPAllocator<hazard_pointer> m_hzp ; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency
121 retired_vector m_arrRetired ; ///< Retired pointer array
124 HPRec( const cds::gc::hzp::GarbageCollector& HzpMgr ) ; // inline
128 /// Clears all hazard pointers
134 } // namespace details
136 /// GarbageCollector::Scan phase strategy
138 See GarbageCollector::Scan for explanation
141 classic, ///< classic scan as described in Michael's works (see GarbageCollector::classic_scan)
142 inplace ///< inplace scan without allocation (see GarbageCollector::inplace_scan)
145 /// Hazard Pointer singleton
147 Safe memory reclamation schema by Michael "Hazard Pointers"
150 \li [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
151 \li [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
152 \li [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
155 class CDS_EXPORT_API GarbageCollector
158 typedef cds::atomicity::event_counter event_counter ; ///< event counter type
160 /// Internal GC statistics
161 struct InternalState {
162 size_t nHPCount ; ///< HP count per thread (const)
163 size_t nMaxThreadCount ; ///< Max thread count (const)
164 size_t nMaxRetiredPtrCount ; ///< Max retired pointer count per thread (const)
165 size_t nHPRecSize ; ///< Size of HP record, bytes (const)
167 size_t nHPRecAllocated ; ///< Count of HP record allocations
168 size_t nHPRecUsed ; ///< Count of HP record used
169 size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers
170 size_t nRetiredPtrInFreeHPRecs ; ///< Count of retired pointer in free (unused) HP records
172 event_counter::value_type evcAllocHPRec ; ///< Count of HPRec allocations
173 event_counter::value_type evcRetireHPRec ; ///< Count of HPRec retire events
174 event_counter::value_type evcAllocNewHPRec; ///< Count of new HPRec allocations from heap
175 event_counter::value_type evcDeleteHPRec ; ///< Count of HPRec deletions
177 event_counter::value_type evcScanCall ; ///< Count of Scan calling
178 event_counter::value_type evcHelpScanCall ; ///< Count of HelpScan calling
179 event_counter::value_type evcScanFromHelpScan;///< Count of Scan calls from HelpScan
181 event_counter::value_type evcDeletedNode ; ///< Count of deleting of retired objects
182 event_counter::value_type evcDeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
185 /// No GarbageCollector object is created
186 CDS_DECLARE_EXCEPTION( HZPManagerEmpty, "Global Hazard Pointer GarbageCollector is NULL" );
188 /// Not enough required Hazard Pointer count
189 CDS_DECLARE_EXCEPTION( HZPTooMany, "Not enough required Hazard Pointer count" );
192 /// Internal GC statistics
194 event_counter m_AllocHPRec ; ///< Count of HPRec allocations
195 event_counter m_RetireHPRec ; ///< Count of HPRec retire events
196 event_counter m_AllocNewHPRec ; ///< Count of new HPRec allocations from heap
197 event_counter m_DeleteHPRec ; ///< Count of HPRec deletions
199 event_counter m_ScanCallCount ; ///< Count of Scan calling
200 event_counter m_HelpScanCallCount ; ///< Count of HelpScan calling
201 event_counter m_CallScanFromHelpScan ; ///< Count of Scan calls from HelpScan
203 event_counter m_DeletedNode ; ///< Count of retired objects deleting
204 event_counter m_DeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
207 /// Internal list of cds::gc::hzp::details::HPRec
208 struct hplist_node: public details::HPRec
210 hplist_node * m_pNextNode ; ///< next hazard ptr record in list
211 atomics::atomic<OS::ThreadId> m_idOwner ; ///< Owner thread id; 0 - the record is free (not owned)
212 atomics::atomic<bool> m_bFree ; ///< true if record if free (not owned)
215 hplist_node( const GarbageCollector& HzpMgr )
217 m_pNextNode( nullptr ),
218 m_idOwner( OS::c_NullThreadId ),
224 assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId );
225 assert( m_bFree.load(atomics::memory_order_relaxed) );
230 atomics::atomic<hplist_node *> m_pListHead ; ///< Head of GC list
232 static GarbageCollector * m_pHZPManager ; ///< GC instance pointer
234 Statistics m_Stat ; ///< Internal statistics
235 bool m_bStatEnabled ; ///< true - statistics enabled
237 const size_t m_nHazardPointerCount ; ///< max count of thread's hazard pointer
238 const size_t m_nMaxThreadCount ; ///< max count of thread
239 const size_t m_nMaxRetiredPtrCount ; ///< max count of retired ptr per thread
240 scan_type m_nScanType ; ///< scan type (see \ref scan_type enum)
246 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
247 size_t nMaxThreadCount = 0, ///< Max count of thread
248 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects
249 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
255 /// Allocate new HP record
256 hplist_node * NewHPRec();
258 /// Permanently deletes HPrecord \p pNode
260 Caveat: for performance reason this function is defined as inline and cannot be called directly
262 void DeleteHPRec( hplist_node * pNode );
264 /// Permanently deletes retired pointer \p p
266 Caveat: for performance reason this function is defined as inline and cannot be called directly
268 void DeletePtr( details::retired_ptr& p );
271 void detachAllThread();
275 /// Creates GarbageCollector singleton
277 GC is the singleton. If GC instance is not exist then the function creates the instance.
278 Otherwise it does nothing.
280 The Michael's HP reclamation schema depends of three parameters:
282 \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
283 the data structure algorithms. By default, if \p nHazardPtrCount = 0,
284 the function uses maximum of HP count for CDS library.
286 \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
288 \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
289 \p nHazardPtrCount * \p nMaxThreadCount.
290 Default is 2 * \p nHazardPtrCount * \p nMaxThreadCount.
292 static void CDS_STDCALL Construct(
293 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
294 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
295 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
296 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
299 /// Destroys global instance of GarbageCollector
301 The parameter \p bDetachAll should be used carefully: if its value is \p true,
302 then the destroying GC automatically detaches all attached threads. This feature
303 can be useful when you have no control over the thread termination, for example,
304 when \p libcds is injected into existing external thread.
306 static void CDS_STDCALL Destruct(
307 bool bDetachAll = false ///< Detach all threads
310 /// Returns pointer to GarbageCollector instance
311 static GarbageCollector& instance()
313 if ( !m_pHZPManager )
314 throw HZPManagerEmpty();
315 return *m_pHZPManager;
318 /// Checks if global GC object is constructed and may be used
321 return m_pHZPManager != nullptr;
324 /// Returns max Hazard Pointer count defined in construction time
325 size_t getHazardPointerCount() const { return m_nHazardPointerCount; }
327 /// Returns max thread count defined in construction time
328 size_t getMaxThreadCount() const { return m_nMaxThreadCount; }
330 /// Returns max size of retired objects array. It is defined in construction time
331 size_t getMaxRetiredPtrCount() const { return m_nMaxRetiredPtrCount; }
333 // Internal statistics
335 /// Get internal statistics
336 InternalState& getInternalState(InternalState& stat) const;
338 /// Checks if internal statistics enabled
339 bool isStatisticsEnabled() const { return m_bStatEnabled; }
341 /// Enables/disables internal statistics
342 bool enableStatistics( bool bEnable )
344 bool bEnabled = m_bStatEnabled;
345 m_bStatEnabled = bEnable;
349 /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
351 If \p nRequiredCount > getHazardPointerCount() then the exception HZPTooMany is thrown
353 static void checkHPCount( unsigned int nRequiredCount )
355 if ( instance().getHazardPointerCount() < nRequiredCount )
359 /// Get current scan strategy
360 scan_type getScanType() const
365 /// Set current scan strategy
366 /** @anchor hzp_gc_setScanType
367 Scan strategy changing is allowed on the fly.
370 scan_type nScanType ///< new scan strategy
373 m_nScanType = nScanType;
376 public: // Internals for threads
378 /// Allocates Hazard Pointer GC record. For internal use only
379 details::HPRec * AllocateHPRec();
381 /// Free HP record. For internal use only
382 void RetireHPRec( details::HPRec * pRec );
384 /// The main garbage collecting function
386 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
389 There are the following scan algorithm:
390 - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use
391 - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory
393 Use \ref hzp_gc_setScanType "setScanType" member function to setup appropriate scan algorithm.
395 void Scan( details::HPRec * pRec )
397 switch ( m_nScanType ) {
399 inplace_scan( pRec );
402 assert(false) ; // Forgotten something?..
404 classic_scan( pRec );
409 /// Helper scan routine
411 The function guarantees that every node that is eligible for reuse is eventually freed, barring
412 thread failures. To do so, after executing Scan, a thread executes a HelpScan,
413 where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
414 to thread's list of reclaimed pointers.
416 The function is called internally by Scan.
418 void HelpScan( details::HPRec * pThis );
421 /// Classic scan algorithm
422 /** @anchor hzp_gc_classic_scan
423 Classical scan algorithm as described in Michael's paper.
425 A scan includes four stages. The first stage involves scanning the array HP for non-null values.
426 Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer.
427 Only stage 1 accesses shared variables. The following stages operate only on private variables.
429 The second stage of a scan involves sorting local list of protected pointers to allow
430 binary search in the third stage.
432 The third stage of a scan involves checking each reclaimed node
433 against the pointers in local list of protected pointers. If the binary search yields
434 no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list
435 of reclaimed pointers.
437 The forth stage prepares new thread's private list of reclaimed pointers
438 that could not be freed during the current scan, where they remain until the next scan.
440 This algorithm allocates memory for internal HP array.
442 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
445 void classic_scan( details::HPRec * pRec );
447 /// In-place scan algorithm
448 /** @anchor hzp_gc_inplace_scan
449 Unlike the \ref hzp_gc_classic_scan "classic_scan" algorithm, \p inplace_scan does not allocate any memory.
450 All operations are performed in-place.
452 void inplace_scan( details::HPRec * pRec );
455 /// Thread's hazard pointer manager
457 To use Hazard Pointer reclamation schema each thread object must be linked with the object of ThreadGC class
458 that interacts with GarbageCollector global object. The linkage is performed by calling \ref cds_threading "cds::threading::Manager::attachThread()"
459 on the start of each thread that uses HP GC. Before terminating the thread linked to HP GC it is necessary to call
460 \ref cds_threading "cds::threading::Manager::detachThread()".
462 class ThreadGC: cds::details::noncopyable
464 GarbageCollector& m_HzpManager ; ///< Hazard Pointer GC singleton
465 details::HPRec * m_pHzpRec ; ///< Pointer to thread's HZP record
469 : m_HzpManager( GarbageCollector::instance() ),
477 /// Checks if thread GC is initialized
478 bool isInitialized() const { return m_pHzpRec != nullptr; }
480 /// Initialization. Repeat call is available
484 m_pHzpRec = m_HzpManager.AllocateHPRec();
487 /// Finalization. Repeat call is available
491 details::HPRec * pRec = m_pHzpRec;
493 m_HzpManager.RetireHPRec( pRec );
497 /// Initializes HP guard \p guard
498 details::HPGuard& allocGuard()
501 return m_pHzpRec->m_hzp.alloc();
504 /// Frees HP guard \p guard
505 void freeGuard( details::HPGuard& guard )
508 m_pHzpRec->m_hzp.free( guard );
511 /// Initializes HP guard array \p arr
512 template <size_t Count>
513 void allocGuard( details::HPArray<Count>& arr )
516 m_pHzpRec->m_hzp.alloc( arr );
519 /// Frees HP guard array \p arr
520 template <size_t Count>
521 void freeGuard( details::HPArray<Count>& arr )
524 m_pHzpRec->m_hzp.free( arr );
527 /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
528 template <typename T>
529 void retirePtr( T * p, void (* pFunc)(T *) )
531 retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc ) ) );
534 /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation
535 void retirePtr( const details::retired_ptr& p )
537 m_pHzpRec->m_arrRetired.push( p );
539 if ( m_pHzpRec->m_arrRetired.isFull() ) {
540 // Max of retired pointer count is reached. Do scan
548 m_HzpManager.Scan( m_pHzpRec );
549 m_HzpManager.HelpScan( m_pHzpRec );
556 This class encapsulates Hazard Pointer guard to protect a pointer against deletion .
557 It allocates one HP from thread's HP array in constructor and free the HP allocated in destruction time.
562 details::HPGuard& m_hp ; ///< Hazard pointer guarded
563 ThreadGC& m_gc ; ///< Thread GC
567 typedef details::HPGuard::hazard_ptr hazard_ptr ; ///< Hazard pointer type
569 /// Allocates HP guard from \p gc
570 AutoHPGuard( ThreadGC& gc )
571 : m_hp( gc.allocGuard() )
575 /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T
576 template <typename T>
577 AutoHPGuard( ThreadGC& gc, T * p )
578 : m_hp( gc.allocGuard() )
584 /// Frees HP guard. The pointer guarded may be deleted after this.
587 m_gc.freeGuard( m_hp );
590 /// Returns thread GC
591 ThreadGC& getGC() const
596 /// Protects the pointer \p p against reclamation (guards the pointer).
597 template <typename T>
598 T * operator =( T * p )
604 std::nullptr_t operator =(std::nullptr_t)
606 return m_hp = nullptr;
609 hazard_ptr get() const
616 /// Auto-managed array of hazard pointers
618 This class is wrapper around cds::gc::hzp::details::HPArray class.
619 \p Count is the size of HP array
621 template <size_t Count>
622 class AutoHPArray: public details::HPArray<Count>
624 ThreadGC& m_mgr ; ///< Thread GC
627 /// Rebind array for other size \p COUNT2
628 template <size_t Count2>
630 typedef AutoHPArray<Count2> other ; ///< rebinding result
634 /// Allocates array of HP guard from \p mgr
635 AutoHPArray( ThreadGC& mgr )
638 mgr.allocGuard( *this );
641 /// Frees array of HP guard
644 m_mgr.freeGuard( *this );
647 /// Returns thread GC
648 ThreadGC& getGC() const { return m_mgr; }
652 }} // namespace cds::gc
655 #include <cds/gc/hzp/details/hp_inline.h>
657 #if CDS_COMPILER == CDS_COMPILER_MSVC
658 # pragma warning(pop)
661 #endif // #ifndef __CDS_GC_HZP_HZP_H