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
32 /// Different safe memory reclamation schemas (garbage collectors)
33 /** @ingroup cds_garbage_collector
35 This namespace specifies different safe memory reclamation (SMR) algorithms.
36 See \ref cds_garbage_collector "Garbage collectors"
40 /// Michael's Hazard Pointers reclamation schema
43 - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
44 - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
45 - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
47 The \p cds::gc::hp namespace and its members are internal representation of Hazard Pointer GC and should not be used directly.
48 Use \p cds::gc::HP class in your code.
50 Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is
51 GC class and its nested classes. Before use any HP-related class you must initialize HP garbage collector
52 by contructing \p cds::gc::HP object in beginning of your \p main().
53 See \p cds::gc::HP class for explanation.
58 class GarbageCollector;
64 typedef cds::gc::details::retired_ptr retired_ptr;
66 /// Array of retired pointers
68 The vector of retired pointer ready to delete.
70 The Hazard Pointer schema is build on thread-static arrays. For each HP-enabled thread the HP manager allocates
71 array of retired pointers. The array belongs to the thread: owner thread writes to the array, other threads
74 class retired_vector {
75 /// Underlying vector implementation
76 typedef cds::details::bounded_array<retired_ptr> retired_vector_impl;
78 retired_vector_impl m_arr ; ///< the array of retired pointers
79 size_t m_nSize ; ///< Current size of \p m_arr
83 typedef retired_vector_impl::iterator iterator;
86 retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
92 The capacity is constant for any thread. It is defined by cds::gc::hp::GarbageCollector.
94 size_t capacity() const CDS_NOEXCEPT
96 return m_arr.capacity();
99 /// Current vector size (count of retired pointers in the vector)
100 size_t size() const CDS_NOEXCEPT
105 /// Set vector size. Uses internally
106 void size( size_t nSize )
108 assert( nSize <= capacity() );
112 /// Pushes retired pointer to the vector
113 void push( retired_ptr const& p )
115 assert( m_nSize < capacity() );
116 m_arr[ m_nSize ] = p;
120 /// Checks if the vector is full (size() == capacity() )
121 bool isFull() const CDS_NOEXCEPT
123 return m_nSize >= capacity();
127 iterator begin() CDS_NOEXCEPT
129 return m_arr.begin();
133 iterator end() CDS_NOEXCEPT
135 return m_arr.begin() + m_nSize ;
138 /// Clears the vector. After clearing, size() == 0
139 void clear() CDS_NOEXCEPT
145 /// Hazard pointer record of the thread
147 The structure of type "single writer - multiple reader": only the owner thread may write to this structure
148 other threads have read-only access.
151 hp_allocator<> m_hzp; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency
152 retired_vector m_arrRetired ; ///< Retired pointer array
155 hp_record( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
159 /// Clears all hazard pointers
165 } // namespace details
167 /// GarbageCollector::Scan phase strategy
169 See GarbageCollector::Scan for explanation
172 classic, ///< classic scan as described in Michael's works (see GarbageCollector::classic_scan)
173 inplace ///< inplace scan without allocation (see GarbageCollector::inplace_scan)
176 /// Hazard Pointer singleton
178 Safe memory reclamation schema by Michael "Hazard Pointers"
181 \li [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
182 \li [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
183 \li [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
186 class CDS_EXPORT_API GarbageCollector
189 typedef cds::atomicity::event_counter event_counter ; ///< event counter type
191 /// Internal GC statistics
192 struct InternalState {
193 size_t nHPCount ; ///< HP count per thread (const)
194 size_t nMaxThreadCount ; ///< Max thread count (const)
195 size_t nMaxRetiredPtrCount ; ///< Max retired pointer count per thread (const)
196 size_t nHPRecSize ; ///< Size of HP record, bytes (const)
198 size_t nHPRecAllocated ; ///< Count of HP record allocations
199 size_t nHPRecUsed ; ///< Count of HP record used
200 size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers
201 size_t nRetiredPtrInFreeHPRecs ; ///< Count of retired pointer in free (unused) HP records
203 event_counter::value_type evcAllocHPRec ; ///< Count of \p hp_record allocations
204 event_counter::value_type evcRetireHPRec ; ///< Count of \p hp_record retire events
205 event_counter::value_type evcAllocNewHPRec; ///< Count of new \p hp_record allocations from heap
206 event_counter::value_type evcDeleteHPRec ; ///< Count of \p hp_record deletions
208 event_counter::value_type evcScanCall ; ///< Count of Scan calling
209 event_counter::value_type evcHelpScanCall ; ///< Count of HelpScan calling
210 event_counter::value_type evcScanFromHelpScan;///< Count of Scan calls from HelpScan
212 event_counter::value_type evcDeletedNode ; ///< Count of deleting of retired objects
213 event_counter::value_type evcDeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
216 /// No GarbageCollector object is created
217 CDS_DECLARE_EXCEPTION( HZPManagerEmpty, "Global Hazard Pointer GarbageCollector is NULL" );
219 /// Not enough required Hazard Pointer count
220 CDS_DECLARE_EXCEPTION( HZPTooMany, "Not enough required Hazard Pointer count" );
223 /// Internal GC statistics
225 event_counter m_AllocHPRec ; ///< Count of \p hp_record allocations
226 event_counter m_RetireHPRec ; ///< Count of \p hp_record retire events
227 event_counter m_AllocNewHPRec ; ///< Count of new \p hp_record allocations from heap
228 event_counter m_DeleteHPRec ; ///< Count of \p hp_record deletions
230 event_counter m_ScanCallCount ; ///< Count of Scan calling
231 event_counter m_HelpScanCallCount ; ///< Count of HelpScan calling
232 event_counter m_CallScanFromHelpScan ; ///< Count of Scan calls from HelpScan
234 event_counter m_DeletedNode ; ///< Count of retired objects deleting
235 event_counter m_DeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
238 /// Internal list of cds::gc::hp::details::hp_record
239 struct hplist_node : public details::hp_record
241 hplist_node * m_pNextNode; ///< next hazard ptr record in list
242 atomics::atomic<OS::ThreadId> m_idOwner; ///< Owner thread id; 0 - the record is free (not owned)
243 atomics::atomic<bool> m_bFree; ///< true if record if free (not owned)
245 hplist_node( const GarbageCollector& HzpMgr )
246 : hp_record( HzpMgr ),
247 m_pNextNode( nullptr ),
248 m_idOwner( OS::c_NullThreadId ),
254 assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId );
255 assert( m_bFree.load(atomics::memory_order_relaxed) );
259 atomics::atomic<hplist_node *> m_pListHead ; ///< Head of GC list
261 static GarbageCollector * m_pHZPManager ; ///< GC instance pointer
263 Statistics m_Stat ; ///< Internal statistics
264 bool m_bStatEnabled ; ///< true - statistics enabled
266 const size_t m_nHazardPointerCount ; ///< max count of thread's hazard pointer
267 const size_t m_nMaxThreadCount ; ///< max count of thread
268 const size_t m_nMaxRetiredPtrCount ; ///< max count of retired ptr per thread
269 scan_type m_nScanType ; ///< scan type (see \ref scan_type enum)
275 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
276 size_t nMaxThreadCount = 0, ///< Max count of thread
277 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects
278 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
284 /// Allocate new HP record
285 hplist_node * NewHPRec();
287 /// Permanently deletes HPrecord \p pNode
289 Caveat: for performance reason this function is defined as inline and cannot be called directly
291 void DeleteHPRec( hplist_node * pNode );
293 /// Permanently deletes retired pointer \p p
295 Caveat: for performance reason this function is defined as inline and cannot be called directly
297 void DeletePtr( details::retired_ptr& p );
299 void detachAllThread();
302 /// Creates GarbageCollector singleton
304 GC is the singleton. If GC instance is not exist then the function creates the instance.
305 Otherwise it does nothing.
307 The Michael's HP reclamation schema depends of three parameters:
309 \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
310 the data structure algorithms. By default, if \p nHazardPtrCount = 0,
311 the function uses maximum of HP count for CDS library.
313 \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
315 \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
316 \p nHazardPtrCount * \p nMaxThreadCount.
317 Default is 2 * \p nHazardPtrCount * \p nMaxThreadCount.
319 static void CDS_STDCALL Construct(
320 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
321 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
322 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
323 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
326 /// Destroys global instance of GarbageCollector
328 The parameter \p bDetachAll should be used carefully: if its value is \p true,
329 then the destroying GC automatically detaches all attached threads. This feature
330 can be useful when you have no control over the thread termination, for example,
331 when \p libcds is injected into existing external thread.
333 static void CDS_STDCALL Destruct(
334 bool bDetachAll = false ///< Detach all threads
337 /// Returns pointer to GarbageCollector instance
338 static GarbageCollector& instance()
340 if ( !m_pHZPManager )
341 throw HZPManagerEmpty();
342 return *m_pHZPManager;
345 /// Checks if global GC object is constructed and may be used
346 static bool isUsed() CDS_NOEXCEPT
348 return m_pHZPManager != nullptr;
351 /// Returns max Hazard Pointer count defined in construction time
352 size_t getHazardPointerCount() const CDS_NOEXCEPT
354 return m_nHazardPointerCount;
357 /// Returns max thread count defined in construction time
358 size_t getMaxThreadCount() const CDS_NOEXCEPT
360 return m_nMaxThreadCount;
363 /// Returns max size of retired objects array. It is defined in construction time
364 size_t getMaxRetiredPtrCount() const CDS_NOEXCEPT
366 return m_nMaxRetiredPtrCount;
369 // Internal statistics
371 /// Get internal statistics
372 InternalState& getInternalState(InternalState& stat) const;
374 /// Checks if internal statistics enabled
375 bool isStatisticsEnabled() const { return m_bStatEnabled; }
377 /// Enables/disables internal statistics
378 bool enableStatistics( bool bEnable )
380 bool bEnabled = m_bStatEnabled;
381 m_bStatEnabled = bEnable;
385 /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
387 If \p nRequiredCount > getHazardPointerCount() then the exception HZPTooMany is thrown
389 static void checkHPCount( unsigned int nRequiredCount )
391 if ( instance().getHazardPointerCount() < nRequiredCount )
395 /// Get current scan strategy
396 scan_type getScanType() const
401 /// Set current scan strategy
402 /** @anchor hzp_gc_setScanType
403 Scan strategy changing is allowed on the fly.
406 scan_type nScanType ///< new scan strategy
409 m_nScanType = nScanType;
412 public: // Internals for threads
414 /// Allocates Hazard Pointer GC record. For internal use only
415 details::hp_record * alloc_hp_record();
417 /// Free HP record. For internal use only
418 void free_hp_record( details::hp_record * pRec );
420 /// The main garbage collecting function
422 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
425 There are the following scan algorithm:
426 - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use
427 - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory
429 Use \ref hzp_gc_setScanType "setScanType" member function to setup appropriate scan algorithm.
431 void Scan( details::hp_record * pRec )
433 switch ( m_nScanType ) {
435 inplace_scan( pRec );
438 assert(false) ; // Forgotten something?..
440 classic_scan( pRec );
445 /// Helper scan routine
447 The function guarantees that every node that is eligible for reuse is eventually freed, barring
448 thread failures. To do so, after executing Scan, a thread executes a HelpScan,
449 where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
450 to thread's list of reclaimed pointers.
452 The function is called internally by Scan.
454 void HelpScan( details::hp_record * pThis );
457 /// Classic scan algorithm
458 /** @anchor hzp_gc_classic_scan
459 Classical scan algorithm as described in Michael's paper.
461 A scan includes four stages. The first stage involves scanning the array HP for non-null values.
462 Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer.
463 Only stage 1 accesses shared variables. The following stages operate only on private variables.
465 The second stage of a scan involves sorting local list of protected pointers to allow
466 binary search in the third stage.
468 The third stage of a scan involves checking each reclaimed node
469 against the pointers in local list of protected pointers. If the binary search yields
470 no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list
471 of reclaimed pointers.
473 The forth stage prepares new thread's private list of reclaimed pointers
474 that could not be freed during the current scan, where they remain until the next scan.
476 This algorithm allocates memory for internal HP array.
478 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
481 void classic_scan( details::hp_record * pRec );
483 /// In-place scan algorithm
484 /** @anchor hzp_gc_inplace_scan
485 Unlike the \ref hzp_gc_classic_scan "classic_scan" algorithm, \p inplace_scan does not allocate any memory.
486 All operations are performed in-place.
488 void inplace_scan( details::hp_record * pRec );
491 /// Thread's hazard pointer manager
493 To use Hazard Pointer reclamation schema each thread object must be linked with the object of ThreadGC class
494 that interacts with GarbageCollector global object. The linkage is performed by calling \ref cds_threading "cds::threading::Manager::attachThread()"
495 on the start of each thread that uses HP GC. Before terminating the thread linked to HP GC it is necessary to call
496 \ref cds_threading "cds::threading::Manager::detachThread()".
500 GarbageCollector& m_HzpManager; ///< Hazard Pointer GC singleton
501 details::hp_record * m_pHzpRec; ///< Pointer to thread's HZP record
504 /// Default constructor
506 : m_HzpManager( GarbageCollector::instance() ),
510 /// The object is not copy-constructible
511 ThreadGC( ThreadGC const& ) = delete;
518 /// Checks if thread GC is initialized
519 bool isInitialized() const { return m_pHzpRec != nullptr; }
521 /// Initialization. Repeat call is available
525 m_pHzpRec = m_HzpManager.alloc_hp_record();
528 /// Finalization. Repeat call is available
532 details::hp_record * pRec = m_pHzpRec;
534 m_HzpManager.free_hp_record( pRec );
538 /// Initializes HP guard \p guard
539 details::hp_guard& allocGuard()
542 return m_pHzpRec->m_hzp.alloc();
545 /// Frees HP guard \p guard
546 void freeGuard( details::hp_guard& guard )
549 m_pHzpRec->m_hzp.free( guard );
552 /// Initializes HP guard array \p arr
553 template <size_t Count>
554 void allocGuard( details::hp_array<Count>& arr )
557 m_pHzpRec->m_hzp.alloc( arr );
560 /// Frees HP guard array \p arr
561 template <size_t Count>
562 void freeGuard( details::hp_array<Count>& arr )
565 m_pHzpRec->m_hzp.free( arr );
568 /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
569 template <typename T>
570 void retirePtr( T * p, void (* pFunc)(T *) )
581 free_retired_ptr_func hpFunc;
583 cast_func.pFunc = pFunc;
585 retirePtr( details::retired_ptr( cast_ptr.hp, cast_func.hpFunc ) );
587 retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc )));
590 /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation
591 void retirePtr( details::retired_ptr const& p )
593 m_pHzpRec->m_arrRetired.push( p );
595 if ( m_pHzpRec->m_arrRetired.isFull() ) {
596 // Max of retired pointer count is reached. Do scan
603 m_HzpManager.Scan( m_pHzpRec );
604 m_HzpManager.HelpScan( m_pHzpRec );
610 This class encapsulates Hazard Pointer guard to protect a pointer against deletion .
611 It allocates one HP from thread's HP array in constructor and free the hazard pointer allocated
616 details::hp_guard& m_hp ; ///< Hazard pointer guarded
617 ThreadGC& m_gc ; ///< Thread GC
620 typedef details::hp_guard::hazard_ptr hazard_ptr ; ///< Hazard pointer type
623 /// Allocates HP guard from \p gc
624 guard( ThreadGC& gc )
625 : m_hp( gc.allocGuard() )
629 /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T
630 template <typename T>
631 guard( ThreadGC& gc, T * p )
632 : m_hp( gc.allocGuard() )
638 /// Frees HP guard. The pointer guarded may be deleted after this.
641 m_gc.freeGuard( m_hp );
644 /// Returns thread GC
645 ThreadGC& getGC() const
650 /// Protects the pointer \p p against reclamation (guards the pointer).
651 template <typename T>
652 T * operator =( T * p )
657 std::nullptr_t operator =(std::nullptr_t)
659 return m_hp = nullptr;
662 hazard_ptr get() const
668 /// Auto-managed array of hazard pointers
670 This class is wrapper around cds::gc::hp::details::hp_array class.
671 \p Count is the size of HP array
673 template <size_t Count>
674 class array : public details::hp_array<Count>
676 ThreadGC& m_mgr ; ///< Thread GC
679 /// Rebind array for other size \p COUNT2
680 template <size_t Count2>
682 typedef array<Count2> other; ///< rebinding result
686 /// Allocates array of HP guard from \p mgr
687 array( ThreadGC& mgr )
690 mgr.allocGuard( *this );
693 /// Frees array of HP guard
696 m_mgr.freeGuard( *this );
699 /// Returns thread GC
700 ThreadGC& getGC() const { return m_mgr; }
704 }} // namespace cds::gc
710 namespace gc { namespace hp { namespace details {
712 inline retired_vector::retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr )
713 : m_arr( HzpMgr.getMaxRetiredPtrCount() ),
717 inline hp_record::hp_record( const cds::gc::hp::GarbageCollector& HzpMgr )
718 : m_hzp( HzpMgr.getHazardPointerCount() ),
719 m_arrRetired( HzpMgr )
722 }}} // namespace gc::hp::details
727 #if CDS_COMPILER == CDS_COMPILER_MSVC
728 # pragma warning(pop)
731 #endif // #ifndef __CDS_GC_DETAILS_HP_H