3 #ifndef __CDS_GC_DETAILS_HP_H
4 #define __CDS_GC_DETAILS_HP_H
6 #include <cds/cxx11_atomic.h>
7 #include <cds/os/thread.h>
8 #include <cds/details/bounded_array.h>
10 #include <cds/gc/details/hp_type.h>
11 #include <cds/gc/details/hp_alloc.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
33 @page cds_garbage_collectors_comparison GC comparison
34 @ingroup cds_garbage_collector
40 <th>%cds::gc::DHP</th>
43 <td>Implementation quality</td>
48 <td>Performance rank (1 - slowest, 5 - fastest)</td>
53 <td>Max number of guarded (hazard) pointers per thread</td>
54 <td>limited (specifies in GC object ctor)</td>
55 <td>unlimited (dynamically allocated when needed)</td>
58 <td>Max number of retired pointers<sup>1</sup></td>
63 <td>Array of retired pointers</td>
64 <td>preallocated for each thread, limited in size</td>
65 <td>global for the entire process, unlimited (dynamically allocated when needed)</td>
68 <td>Support direct pointer to item of lock-free container (useful for iterators)</td>
69 <td>not supported</td>
70 <td>not supported</td>
74 <sup>1</sup>Unbounded count of retired pointer means a possibility of memory exhaustion.
77 /// Different safe memory reclamation schemas (garbage collectors)
78 /** @ingroup cds_garbage_collector
80 This namespace specifies different safe memory reclamation (SMR) algorithms.
81 See \ref cds_garbage_collector "Garbage collectors"
85 /// Michael's Hazard Pointers reclamation schema
88 - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
89 - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
90 - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
92 The \p cds::gc::hp namespace and its members are internal representation of Hazard Pointer GC and should not be used directly.
93 Use \p 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 \p cds::gc::HP object in beginning of your \p main().
98 See \p cds::gc::HP class for explanation.
103 class GarbageCollector;
109 typedef cds::gc::details::retired_ptr retired_ptr;
111 /// Array of retired pointers
113 The vector of retired pointer ready to delete.
115 The Hazard Pointer schema is build on thread-static arrays. For each HP-enabled thread the HP manager allocates
116 array of retired pointers. The array belongs to the thread: owner thread writes to the array, other threads
119 class retired_vector {
120 /// Underlying vector implementation
121 typedef cds::details::bounded_array<retired_ptr> retired_vector_impl;
123 retired_vector_impl m_arr ; ///< the array of retired pointers
124 size_t m_nSize ; ///< Current size of \p m_arr
128 typedef retired_vector_impl::iterator iterator;
131 retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr ) CDS_NOEXCEPT; // inline
137 The capacity is constant for any thread. It is defined by cds::gc::hp::GarbageCollector.
139 size_t capacity() const CDS_NOEXCEPT
141 return m_arr.capacity();
144 /// Current vector size (count of retired pointers in the vector)
145 size_t size() const CDS_NOEXCEPT
150 /// Set vector size. Uses internally
151 void size( size_t nSize )
153 assert( nSize <= capacity() );
157 /// Pushes retired pointer to the vector
158 void push( const retired_ptr& p )
160 assert( m_nSize < capacity() );
161 m_arr[ m_nSize ] = p;
165 /// Checks if the vector is full (size() == capacity() )
166 bool isFull() const CDS_NOEXCEPT
168 return m_nSize >= capacity();
172 iterator begin() CDS_NOEXCEPT
174 return m_arr.begin();
178 iterator end() CDS_NOEXCEPT
180 return m_arr.begin() + m_nSize ;
183 /// Clears the vector. After clearing, size() == 0
184 void clear() CDS_NOEXCEPT
190 /// Hazard pointer record of the thread
192 The structure of type "single writer - multiple reader": only the owner thread may write to this structure
193 other threads have read-only access.
196 hp_allocator<> m_hzp; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency
197 retired_vector m_arrRetired ; ///< Retired pointer array
200 hp_record( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
204 /// Clears all hazard pointers
210 } // namespace details
212 /// GarbageCollector::Scan phase strategy
214 See GarbageCollector::Scan for explanation
217 classic, ///< classic scan as described in Michael's works (see GarbageCollector::classic_scan)
218 inplace ///< inplace scan without allocation (see GarbageCollector::inplace_scan)
221 /// Hazard Pointer singleton
223 Safe memory reclamation schema by Michael "Hazard Pointers"
226 \li [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
227 \li [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
228 \li [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
231 class CDS_EXPORT_API GarbageCollector
234 typedef cds::atomicity::event_counter event_counter ; ///< event counter type
236 /// Internal GC statistics
237 struct InternalState {
238 size_t nHPCount ; ///< HP count per thread (const)
239 size_t nMaxThreadCount ; ///< Max thread count (const)
240 size_t nMaxRetiredPtrCount ; ///< Max retired pointer count per thread (const)
241 size_t nHPRecSize ; ///< Size of HP record, bytes (const)
243 size_t nHPRecAllocated ; ///< Count of HP record allocations
244 size_t nHPRecUsed ; ///< Count of HP record used
245 size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers
246 size_t nRetiredPtrInFreeHPRecs ; ///< Count of retired pointer in free (unused) HP records
248 event_counter::value_type evcAllocHPRec ; ///< Count of \p hp_record allocations
249 event_counter::value_type evcRetireHPRec ; ///< Count of \p hp_record retire events
250 event_counter::value_type evcAllocNewHPRec; ///< Count of new \p hp_record allocations from heap
251 event_counter::value_type evcDeleteHPRec ; ///< Count of \p hp_record deletions
253 event_counter::value_type evcScanCall ; ///< Count of Scan calling
254 event_counter::value_type evcHelpScanCall ; ///< Count of HelpScan calling
255 event_counter::value_type evcScanFromHelpScan;///< Count of Scan calls from HelpScan
257 event_counter::value_type evcDeletedNode ; ///< Count of deleting of retired objects
258 event_counter::value_type evcDeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
261 /// No GarbageCollector object is created
262 CDS_DECLARE_EXCEPTION( HZPManagerEmpty, "Global Hazard Pointer GarbageCollector is NULL" );
264 /// Not enough required Hazard Pointer count
265 CDS_DECLARE_EXCEPTION( HZPTooMany, "Not enough required Hazard Pointer count" );
268 /// Internal GC statistics
270 event_counter m_AllocHPRec ; ///< Count of \p hp_record allocations
271 event_counter m_RetireHPRec ; ///< Count of \p hp_record retire events
272 event_counter m_AllocNewHPRec ; ///< Count of new \p hp_record allocations from heap
273 event_counter m_DeleteHPRec ; ///< Count of \p hp_record deletions
275 event_counter m_ScanCallCount ; ///< Count of Scan calling
276 event_counter m_HelpScanCallCount ; ///< Count of HelpScan calling
277 event_counter m_CallScanFromHelpScan ; ///< Count of Scan calls from HelpScan
279 event_counter m_DeletedNode ; ///< Count of retired objects deleting
280 event_counter m_DeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
283 /// Internal list of cds::gc::hp::details::hp_record
284 struct hplist_node : public details::hp_record
286 hplist_node * m_pNextNode ; ///< next hazard ptr record in list
287 atomics::atomic<OS::ThreadId> m_idOwner ; ///< Owner thread id; 0 - the record is free (not owned)
288 atomics::atomic<bool> m_bFree ; ///< true if record if free (not owned)
290 hplist_node( const GarbageCollector& HzpMgr )
291 : hp_record( HzpMgr ),
292 m_pNextNode( nullptr ),
293 m_idOwner( OS::c_NullThreadId ),
299 assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId );
300 assert( m_bFree.load(atomics::memory_order_relaxed) );
304 atomics::atomic<hplist_node *> m_pListHead ; ///< Head of GC list
306 static GarbageCollector * m_pHZPManager ; ///< GC instance pointer
308 Statistics m_Stat ; ///< Internal statistics
309 bool m_bStatEnabled ; ///< true - statistics enabled
311 const size_t m_nHazardPointerCount ; ///< max count of thread's hazard pointer
312 const size_t m_nMaxThreadCount ; ///< max count of thread
313 const size_t m_nMaxRetiredPtrCount ; ///< max count of retired ptr per thread
314 scan_type m_nScanType ; ///< scan type (see \ref scan_type enum)
320 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
321 size_t nMaxThreadCount = 0, ///< Max count of thread
322 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects
323 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
329 /// Allocate new HP record
330 hplist_node * NewHPRec();
332 /// Permanently deletes HPrecord \p pNode
334 Caveat: for performance reason this function is defined as inline and cannot be called directly
336 void DeleteHPRec( hplist_node * pNode );
338 /// Permanently deletes retired pointer \p p
340 Caveat: for performance reason this function is defined as inline and cannot be called directly
342 void DeletePtr( details::retired_ptr& p );
344 void detachAllThread();
347 /// Creates GarbageCollector singleton
349 GC is the singleton. If GC instance is not exist then the function creates the instance.
350 Otherwise it does nothing.
352 The Michael's HP reclamation schema depends of three parameters:
354 \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
355 the data structure algorithms. By default, if \p nHazardPtrCount = 0,
356 the function uses maximum of HP count for CDS library.
358 \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
360 \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
361 \p nHazardPtrCount * \p nMaxThreadCount.
362 Default is 2 * \p nHazardPtrCount * \p nMaxThreadCount.
364 static void CDS_STDCALL Construct(
365 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
366 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
367 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
368 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
371 /// Destroys global instance of GarbageCollector
373 The parameter \p bDetachAll should be used carefully: if its value is \p true,
374 then the destroying GC automatically detaches all attached threads. This feature
375 can be useful when you have no control over the thread termination, for example,
376 when \p libcds is injected into existing external thread.
378 static void CDS_STDCALL Destruct(
379 bool bDetachAll = false ///< Detach all threads
382 /// Returns pointer to GarbageCollector instance
383 static GarbageCollector& instance()
385 if ( !m_pHZPManager )
386 throw HZPManagerEmpty();
387 return *m_pHZPManager;
390 /// Checks if global GC object is constructed and may be used
391 static bool isUsed() CDS_NOEXCEPT
393 return m_pHZPManager != nullptr;
396 /// Returns max Hazard Pointer count defined in construction time
397 size_t getHazardPointerCount() const CDS_NOEXCEPT
399 return m_nHazardPointerCount;
402 /// Returns max thread count defined in construction time
403 size_t getMaxThreadCount() const CDS_NOEXCEPT
405 return m_nMaxThreadCount;
408 /// Returns max size of retired objects array. It is defined in construction time
409 size_t getMaxRetiredPtrCount() const CDS_NOEXCEPT
411 return m_nMaxRetiredPtrCount;
414 // Internal statistics
416 /// Get internal statistics
417 InternalState& getInternalState(InternalState& stat) const;
419 /// Checks if internal statistics enabled
420 bool isStatisticsEnabled() const { return m_bStatEnabled; }
422 /// Enables/disables internal statistics
423 bool enableStatistics( bool bEnable )
425 bool bEnabled = m_bStatEnabled;
426 m_bStatEnabled = bEnable;
430 /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
432 If \p nRequiredCount > getHazardPointerCount() then the exception HZPTooMany is thrown
434 static void checkHPCount( unsigned int nRequiredCount )
436 if ( instance().getHazardPointerCount() < nRequiredCount )
440 /// Get current scan strategy
441 scan_type getScanType() const
446 /// Set current scan strategy
447 /** @anchor hzp_gc_setScanType
448 Scan strategy changing is allowed on the fly.
451 scan_type nScanType ///< new scan strategy
454 m_nScanType = nScanType;
457 public: // Internals for threads
459 /// Allocates Hazard Pointer GC record. For internal use only
460 details::hp_record * alloc_hp_record();
462 /// Free HP record. For internal use only
463 void free_hp_record( details::hp_record * pRec );
465 /// The main garbage collecting function
467 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
470 There are the following scan algorithm:
471 - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use
472 - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory
474 Use \ref hzp_gc_setScanType "setScanType" member function to setup appropriate scan algorithm.
476 void Scan( details::hp_record * pRec )
478 switch ( m_nScanType ) {
480 inplace_scan( pRec );
483 assert(false) ; // Forgotten something?..
485 classic_scan( pRec );
490 /// Helper scan routine
492 The function guarantees that every node that is eligible for reuse is eventually freed, barring
493 thread failures. To do so, after executing Scan, a thread executes a HelpScan,
494 where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
495 to thread's list of reclaimed pointers.
497 The function is called internally by Scan.
499 void HelpScan( details::hp_record * pThis );
502 /// Classic scan algorithm
503 /** @anchor hzp_gc_classic_scan
504 Classical scan algorithm as described in Michael's paper.
506 A scan includes four stages. The first stage involves scanning the array HP for non-null values.
507 Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer.
508 Only stage 1 accesses shared variables. The following stages operate only on private variables.
510 The second stage of a scan involves sorting local list of protected pointers to allow
511 binary search in the third stage.
513 The third stage of a scan involves checking each reclaimed node
514 against the pointers in local list of protected pointers. If the binary search yields
515 no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list
516 of reclaimed pointers.
518 The forth stage prepares new thread's private list of reclaimed pointers
519 that could not be freed during the current scan, where they remain until the next scan.
521 This algorithm allocates memory for internal HP array.
523 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
526 void classic_scan( details::hp_record * pRec );
528 /// In-place scan algorithm
529 /** @anchor hzp_gc_inplace_scan
530 Unlike the \ref hzp_gc_classic_scan "classic_scan" algorithm, \p inplace_scan does not allocate any memory.
531 All operations are performed in-place.
533 void inplace_scan( details::hp_record * pRec );
536 /// Thread's hazard pointer manager
538 To use Hazard Pointer reclamation schema each thread object must be linked with the object of ThreadGC class
539 that interacts with GarbageCollector global object. The linkage is performed by calling \ref cds_threading "cds::threading::Manager::attachThread()"
540 on the start of each thread that uses HP GC. Before terminating the thread linked to HP GC it is necessary to call
541 \ref cds_threading "cds::threading::Manager::detachThread()".
545 GarbageCollector& m_HzpManager; ///< Hazard Pointer GC singleton
546 details::hp_record * m_pHzpRec; ///< Pointer to thread's HZP record
549 /// Default constructor
551 : m_HzpManager( GarbageCollector::instance() ),
555 /// The object is not copy-constructible
556 ThreadGC( ThreadGC const& ) = delete;
563 /// Checks if thread GC is initialized
564 bool isInitialized() const { return m_pHzpRec != nullptr; }
566 /// Initialization. Repeat call is available
570 m_pHzpRec = m_HzpManager.alloc_hp_record();
573 /// Finalization. Repeat call is available
577 details::hp_record * pRec = m_pHzpRec;
579 m_HzpManager.free_hp_record( pRec );
583 /// Initializes HP guard \p guard
584 details::hp_guard& allocGuard()
587 return m_pHzpRec->m_hzp.alloc();
590 /// Frees HP guard \p guard
591 void freeGuard( details::hp_guard& guard )
594 m_pHzpRec->m_hzp.free( guard );
597 /// Initializes HP guard array \p arr
598 template <size_t Count>
599 void allocGuard( details::hp_array<Count>& arr )
602 m_pHzpRec->m_hzp.alloc( arr );
605 /// Frees HP guard array \p arr
606 template <size_t Count>
607 void freeGuard( details::hp_array<Count>& arr )
610 m_pHzpRec->m_hzp.free( arr );
613 /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
614 template <typename T>
615 void retirePtr( T * p, void (* pFunc)(T *) )
626 free_retired_ptr_func hpFunc;
628 cast_func.pFunc = pFunc;
630 retirePtr( details::retired_ptr( cast_ptr.hp, cast_func.hpFunc ) );
632 retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc )));
635 /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation
636 void retirePtr( details::retired_ptr const& p )
638 m_pHzpRec->m_arrRetired.push( p );
640 if ( m_pHzpRec->m_arrRetired.isFull() ) {
641 // Max of retired pointer count is reached. Do scan
648 m_HzpManager.Scan( m_pHzpRec );
649 m_HzpManager.HelpScan( m_pHzpRec );
655 This class encapsulates Hazard Pointer guard to protect a pointer against deletion .
656 It allocates one HP from thread's HP array in constructor and free the hazard pointer allocated
661 details::hp_guard& m_hp ; ///< Hazard pointer guarded
662 ThreadGC& m_gc ; ///< Thread GC
665 typedef details::hp_guard::hazard_ptr hazard_ptr ; ///< Hazard pointer type
668 /// Allocates HP guard from \p gc
669 guard( ThreadGC& gc )
670 : m_hp( gc.allocGuard() )
674 /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T
675 template <typename T>
676 guard( ThreadGC& gc, T * p )
677 : m_hp( gc.allocGuard() )
683 /// Frees HP guard. The pointer guarded may be deleted after this.
686 m_gc.freeGuard( m_hp );
689 /// Returns thread GC
690 ThreadGC& getGC() const
695 /// Protects the pointer \p p against reclamation (guards the pointer).
696 template <typename T>
697 T * operator =( T * p )
702 std::nullptr_t operator =(std::nullptr_t)
704 return m_hp = nullptr;
707 hazard_ptr get() const
713 /// Auto-managed array of hazard pointers
715 This class is wrapper around cds::gc::hp::details::hp_array class.
716 \p Count is the size of HP array
718 template <size_t Count>
719 class array : public details::hp_array<Count>
721 ThreadGC& m_mgr ; ///< Thread GC
724 /// Rebind array for other size \p COUNT2
725 template <size_t Count2>
727 typedef array<Count2> other; ///< rebinding result
731 /// Allocates array of HP guard from \p mgr
732 array( ThreadGC& mgr )
735 mgr.allocGuard( *this );
738 /// Frees array of HP guard
741 m_mgr.freeGuard( *this );
744 /// Returns thread GC
745 ThreadGC& getGC() const { return m_mgr; }
749 }} // namespace cds::gc
755 namespace gc{ namespace hp { namespace details {
757 inline retired_vector::retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr ) CDS_NOEXCEPT
758 : m_arr( HzpMgr.getMaxRetiredPtrCount() ),
762 inline hp_record::hp_record( const cds::gc::hp::GarbageCollector& HzpMgr )
763 : m_hzp( HzpMgr.getHazardPointerCount() ),
764 m_arrRetired( HzpMgr )
767 }}} // namespace gc::hp::details
772 #if CDS_COMPILER == CDS_COMPILER_MSVC
773 # pragma warning(pop)
776 #endif // #ifndef __CDS_GC_DETAILS_HP_H