2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_GC_DETAILS_HP_H
32 #define CDSLIB_GC_DETAILS_HP_H
34 #include <cds/algo/atomic.h>
35 #include <cds/os/thread.h>
36 #include <cds/details/bounded_array.h>
37 #include <cds/user_setup/cache_line.h>
39 #include <cds/gc/details/hp_type.h>
40 #include <cds/gc/details/hp_alloc.h>
42 #if CDS_COMPILER == CDS_COMPILER_MSVC
43 # pragma warning(push)
44 // warning C4251: 'cds::gc::hp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomic::atomic<T>'
45 // needs to have dll-interface to be used by clients of class 'cds::gc::hp::GarbageCollector'
46 # pragma warning(disable: 4251)
51 2007.12.24 khizmax Add statistics and CDS_GATHER_HAZARDPTR_STAT macro
52 2008.03.06 khizmax Refactoring: implementation of HazardPtrMgr is moved to hazardptr.cpp
53 2008.03.08 khizmax Remove HazardPtrMgr singleton. Now you must initialize/destroy HazardPtrMgr calling
54 HazardPtrMgr::Construct / HazardPtrMgr::Destruct before use (usually in main() function).
55 2008.12.06 khizmax Refactoring. Changes class name, namespace hierarchy, all helper defs have been moved to details namespace
56 2010.01.27 khizmax Introducing memory order constraint
61 /// Different safe memory reclamation schemas (garbage collectors)
62 /** @ingroup cds_garbage_collector
64 This namespace specifies different safe memory reclamation (SMR) algorithms.
65 See \ref cds_garbage_collector "Garbage collectors"
69 /// Michael's Hazard Pointers reclamation schema
72 - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
73 - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
74 - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
76 The \p cds::gc::hp namespace and its members are internal representation of Hazard Pointer GC and should not be used directly.
77 Use \p cds::gc::HP class in your code.
79 Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is
80 GC class and its nested classes. Before use any HP-related class you must initialize HP garbage collector
81 by contructing \p cds::gc::HP object in beginning of your \p main().
82 See \p cds::gc::HP class for explanation.
87 class GarbageCollector;
93 typedef cds::gc::details::retired_ptr retired_ptr;
95 /// Array of retired pointers
97 The vector of retired pointer ready to delete.
99 The Hazard Pointer schema is build on thread-static arrays. For each HP-enabled thread the HP manager allocates
100 array of retired pointers. The array belongs to the thread: owner thread writes to the array, other threads
103 class retired_vector {
104 /// Underlying vector implementation
105 typedef cds::details::bounded_array<retired_ptr> retired_vector_impl;
107 retired_vector_impl m_arr ; ///< the array of retired pointers
108 size_t m_nSize ; ///< Current size of \p m_arr
112 typedef retired_vector_impl::iterator iterator;
115 explicit retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
121 The capacity is constant for any thread. It is defined by cds::gc::hp::GarbageCollector.
123 size_t capacity() const CDS_NOEXCEPT
125 return m_arr.capacity();
128 /// Current vector size (count of retired pointers in the vector)
129 size_t size() const CDS_NOEXCEPT
134 /// Set vector size. Uses internally
135 void size( size_t nSize )
137 assert( nSize <= capacity());
141 /// Pushes retired pointer to the vector
142 void push( retired_ptr const& p )
144 assert( m_nSize < capacity());
145 m_arr[ m_nSize ] = p;
149 /// Checks if the vector is full (size() == capacity())
150 bool isFull() const CDS_NOEXCEPT
152 return m_nSize >= capacity();
156 iterator begin() CDS_NOEXCEPT
158 return m_arr.begin();
162 iterator end() CDS_NOEXCEPT
164 return m_arr.begin() + m_nSize;
167 /// Clears the vector. After clearing, size() == 0
168 void clear() CDS_NOEXCEPT
174 /// Hazard pointer record of the thread
176 The structure of type "single writer - multiple reader": only the owner thread may write to this structure
177 other threads have read-only access.
180 hp_allocator<> m_hzp; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency
181 retired_vector m_arrRetired ; ///< Retired pointer array
183 char padding[cds::c_nCacheLineSize];
184 atomics::atomic<unsigned int> m_nSync; ///< dummy var to introduce synchronizes-with relationship between threads
185 char padding2[cds::c_nCacheLineSize];
188 explicit hp_record( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
192 /// Clears all hazard pointers
200 m_nSync.fetch_add( 1, atomics::memory_order_acq_rel );
203 } // namespace details
205 /// GarbageCollector::Scan phase strategy
207 See GarbageCollector::Scan for explanation
210 classic, ///< classic scan as described in Michael's works (see GarbageCollector::classic_scan)
211 inplace ///< inplace scan without allocation (see GarbageCollector::inplace_scan)
214 /// Hazard Pointer singleton
216 Safe memory reclamation schema by Michael "Hazard Pointers"
219 \li [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
220 \li [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
221 \li [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
224 class CDS_EXPORT_API GarbageCollector
227 typedef cds::atomicity::event_counter event_counter ; ///< event counter type
229 /// Internal GC statistics
230 struct InternalState {
231 size_t nHPCount ; ///< HP count per thread (const)
232 size_t nMaxThreadCount ; ///< Max thread count (const)
233 size_t nMaxRetiredPtrCount ; ///< Max retired pointer count per thread (const)
234 size_t nHPRecSize ; ///< Size of HP record, bytes (const)
236 size_t nHPRecAllocated ; ///< Count of HP record allocations
237 size_t nHPRecUsed ; ///< Count of HP record used
238 size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers
239 size_t nRetiredPtrInFreeHPRecs ; ///< Count of retired pointer in free (unused) HP records
241 event_counter::value_type evcAllocHPRec ; ///< Count of \p hp_record allocations
242 event_counter::value_type evcRetireHPRec ; ///< Count of \p hp_record retire events
243 event_counter::value_type evcAllocNewHPRec; ///< Count of new \p hp_record allocations from heap
244 event_counter::value_type evcDeleteHPRec ; ///< Count of \p hp_record deletions
246 event_counter::value_type evcScanCall ; ///< Count of Scan calling
247 event_counter::value_type evcHelpScanCall ; ///< Count of HelpScan calling
248 event_counter::value_type evcScanFromHelpScan;///< Count of Scan calls from HelpScan
250 event_counter::value_type evcDeletedNode ; ///< Count of deleting of retired objects
251 event_counter::value_type evcDeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
254 /// No GarbageCollector object is created
255 class not_initialized : public std::runtime_error
259 : std::runtime_error( "Global Hazard Pointer GarbageCollector is not initialized" )
263 /// Not enough Hazard Pointer
264 class too_many_hazard_ptr : public std::length_error
267 too_many_hazard_ptr()
268 : std::length_error( "Not enough Hazard Pointer" )
273 /// Internal GC statistics
275 event_counter m_AllocHPRec ; ///< Count of \p hp_record allocations
276 event_counter m_RetireHPRec ; ///< Count of \p hp_record retire events
277 event_counter m_AllocNewHPRec ; ///< Count of new \p hp_record allocations from heap
278 event_counter m_DeleteHPRec ; ///< Count of \p hp_record deletions
280 event_counter m_ScanCallCount ; ///< Count of Scan calling
281 event_counter m_HelpScanCallCount ; ///< Count of HelpScan calling
282 event_counter m_CallScanFromHelpScan ; ///< Count of Scan calls from HelpScan
284 event_counter m_DeletedNode ; ///< Count of retired objects deleting
285 event_counter m_DeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
288 /// Internal list of cds::gc::hp::details::hp_record
289 struct hplist_node : public details::hp_record
291 atomics::atomic<hplist_node*> m_pNextNode; ///< next hazard ptr record in list
292 atomics::atomic<OS::ThreadId> m_idOwner; ///< Owner thread id; 0 - the record is free (not owned)
293 atomics::atomic<bool> m_bFree; ///< true if record is free (not owned)
295 explicit hplist_node( const GarbageCollector& HzpMgr )
296 : hp_record( HzpMgr ),
297 m_pNextNode( nullptr ),
298 m_idOwner( OS::c_NullThreadId ),
302 hplist_node( const GarbageCollector& HzpMgr, OS::ThreadId owner )
303 : hp_record( HzpMgr ),
304 m_pNextNode( nullptr ),
311 assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId );
312 assert( m_bFree.load(atomics::memory_order_relaxed));
316 atomics::atomic<hplist_node *> m_pListHead ; ///< Head of GC list
318 static GarbageCollector * m_pHZPManager ; ///< GC instance pointer
320 Statistics m_Stat ; ///< Internal statistics
321 bool m_bStatEnabled ; ///< true - statistics enabled
323 const size_t m_nHazardPointerCount ; ///< max count of thread's hazard pointer
324 const size_t m_nMaxThreadCount ; ///< max count of thread
325 const size_t m_nMaxRetiredPtrCount ; ///< max count of retired ptr per thread
326 scan_type m_nScanType ; ///< scan type (see \ref scan_type enum)
332 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
333 size_t nMaxThreadCount = 0, ///< Max count of thread
334 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects
335 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
341 /// Allocate new HP record
342 hplist_node * NewHPRec( OS::ThreadId owner );
344 /// Permanently deletes HPrecord \p pNode
346 Caveat: for performance reason this function is defined as inline and cannot be called directly
348 void DeleteHPRec( hplist_node * pNode );
350 void detachAllThread();
353 /// Creates GarbageCollector singleton
355 GC is the singleton. If GC instance is not exist then the function creates the instance.
356 Otherwise it does nothing.
358 The Michael's HP reclamation schema depends of three parameters:
360 \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
361 the data structure algorithms. By default, if \p nHazardPtrCount = 0,
362 the function uses maximum of HP count for CDS library.
364 \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
366 \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
367 \p nHazardPtrCount * \p nMaxThreadCount.
368 Default is 2 * \p nHazardPtrCount * \p nMaxThreadCount.
370 static void CDS_STDCALL Construct(
371 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
372 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
373 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
374 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
377 /// Destroys global instance of GarbageCollector
379 The parameter \p bDetachAll should be used carefully: if its value is \p true,
380 then the destroying GC automatically detaches all attached threads. This feature
381 can be useful when you have no control over the thread termination, for example,
382 when \p libcds is injected into existing external thread.
384 static void CDS_STDCALL Destruct(
385 bool bDetachAll = false ///< Detach all threads
388 /// Returns pointer to GarbageCollector instance
389 static GarbageCollector& instance()
391 if ( !m_pHZPManager )
392 throw not_initialized();
393 return *m_pHZPManager;
396 /// Checks if global GC object is constructed and may be used
397 static bool isUsed() CDS_NOEXCEPT
399 return m_pHZPManager != nullptr;
402 /// Returns max Hazard Pointer count defined in construction time
403 size_t getHazardPointerCount() const CDS_NOEXCEPT
405 return m_nHazardPointerCount;
408 /// Returns max thread count defined in construction time
409 size_t getMaxThreadCount() const CDS_NOEXCEPT
411 return m_nMaxThreadCount;
414 /// Returns max size of retired objects array. It is defined in construction time
415 size_t getMaxRetiredPtrCount() const CDS_NOEXCEPT
417 return m_nMaxRetiredPtrCount;
420 // Internal statistics
422 /// Get internal statistics
423 InternalState& getInternalState(InternalState& stat) const;
425 /// Checks if internal statistics enabled
426 bool isStatisticsEnabled() const { return m_bStatEnabled; }
428 /// Enables/disables internal statistics
429 bool enableStatistics( bool bEnable )
431 bool bEnabled = m_bStatEnabled;
432 m_bStatEnabled = bEnable;
436 /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
438 If \p nRequiredCount > getHazardPointerCount() then the exception \p too_many_hazard_ptr is thrown
440 static void checkHPCount( unsigned int nRequiredCount )
442 if ( instance().getHazardPointerCount() < nRequiredCount )
443 throw too_many_hazard_ptr();
446 /// Get current scan strategy
447 scan_type getScanType() const
452 /// Set current scan strategy
453 /** @anchor hzp_gc_setScanType
454 Scan strategy changing is allowed on the fly.
457 scan_type nScanType ///< new scan strategy
460 m_nScanType = nScanType;
463 public: // Internals for threads
465 /// Allocates Hazard Pointer GC record. For internal use only
466 details::hp_record* alloc_hp_record();
468 /// Free HP record. For internal use only
469 void free_hp_record( details::hp_record* pRec );
471 /// The main garbage collecting function
473 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
476 There are the following scan algorithm:
477 - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use
478 - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory
480 Use \ref hzp_gc_setScanType "setScanType" member function to setup appropriate scan algorithm.
482 void Scan( details::hp_record * pRec )
484 switch ( m_nScanType ) {
486 inplace_scan( pRec );
489 assert(false) ; // Forgotten something?..
491 classic_scan( pRec );
496 /// Helper scan routine
498 The function guarantees that every node that is eligible for reuse is eventually freed, barring
499 thread failures. To do so, after executing Scan, a thread executes a HelpScan,
500 where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
501 to thread's list of reclaimed pointers.
503 The function is called internally by Scan.
505 void HelpScan( details::hp_record * pThis );
508 /// Classic scan algorithm
509 /** @anchor hzp_gc_classic_scan
510 Classical scan algorithm as described in Michael's paper.
512 A scan includes four stages. The first stage involves scanning the array HP for non-null values.
513 Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer.
514 Only stage 1 accesses shared variables. The following stages operate only on private variables.
516 The second stage of a scan involves sorting local list of protected pointers to allow
517 binary search in the third stage.
519 The third stage of a scan involves checking each reclaimed node
520 against the pointers in local list of protected pointers. If the binary search yields
521 no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list
522 of reclaimed pointers.
524 The forth stage prepares new thread's private list of reclaimed pointers
525 that could not be freed during the current scan, where they remain until the next scan.
527 This algorithm allocates memory for internal HP array.
529 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
532 void classic_scan( details::hp_record * pRec );
534 /// In-place scan algorithm
535 /** @anchor hzp_gc_inplace_scan
536 Unlike the \ref hzp_gc_classic_scan "classic_scan" algorithm, \p inplace_scan does not allocate any memory.
537 All operations are performed in-place.
539 void inplace_scan( details::hp_record * pRec );
542 /// Thread's hazard pointer manager
544 To use Hazard Pointer reclamation schema each thread object must be linked with the object of ThreadGC class
545 that interacts with GarbageCollector global object. The linkage is performed by calling \ref cds_threading "cds::threading::Manager::attachThread()"
546 on the start of each thread that uses HP GC. Before terminating the thread linked to HP GC it is necessary to call
547 \ref cds_threading "cds::threading::Manager::detachThread()".
551 GarbageCollector& m_HzpManager; ///< Hazard Pointer GC singleton
552 details::hp_record* m_pHzpRec; ///< Pointer to thread's HZP record
555 /// Default constructor
557 : m_HzpManager( GarbageCollector::instance()),
561 /// The object is not copy-constructible
562 ThreadGC( ThreadGC const& ) = delete;
569 /// Checks if thread GC is initialized
570 bool isInitialized() const { return m_pHzpRec != nullptr; }
572 /// Initialization. Repeat call is available
576 m_pHzpRec = m_HzpManager.alloc_hp_record();
579 /// Finalization. Repeat call is available
583 details::hp_record* pRec = m_pHzpRec;
585 m_HzpManager.free_hp_record( pRec );
589 /// Initializes HP guard \p guard
590 details::hp_guard* allocGuard()
593 return m_pHzpRec->m_hzp.alloc();
596 /// Frees HP guard \p guard
597 void freeGuard( details::hp_guard* guard )
600 m_pHzpRec->m_hzp.free( guard );
603 /// Initializes HP guard array \p arr
604 template <size_t Count>
605 size_t allocGuard( details::hp_array<Count>& arr )
608 return m_pHzpRec->m_hzp.alloc( arr );
611 /// Frees HP guard array \p arr
612 template <size_t Count>
613 void freeGuard( details::hp_array<Count>& arr )
616 m_pHzpRec->m_hzp.free( arr );
619 /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
620 template <typename T>
621 void retirePtr( T * p, void (* pFunc)(T *))
623 retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc )));
626 /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation
627 void retirePtr( details::retired_ptr const& p )
629 m_pHzpRec->m_arrRetired.push( p );
631 if ( m_pHzpRec->m_arrRetired.isFull()) {
632 // Max of retired pointer count is reached. Do scan
637 /// Run retiring scan cycle
640 m_HzpManager.Scan( m_pHzpRec );
641 m_HzpManager.HelpScan( m_pHzpRec );
646 assert( m_pHzpRec != nullptr );
652 }} // namespace cds::gc
658 namespace gc { namespace hp { namespace details {
660 inline retired_vector::retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr )
661 : m_arr( HzpMgr.getMaxRetiredPtrCount()),
665 inline hp_record::hp_record( const cds::gc::hp::GarbageCollector& HzpMgr )
666 : m_hzp( HzpMgr.getHazardPointerCount())
667 , m_arrRetired( HzpMgr )
671 }}} // namespace gc::hp::details
676 #if CDS_COMPILER == CDS_COMPILER_MSVC
677 # pragma warning(pop)
680 #endif // #ifndef CDSLIB_GC_DETAILS_HP_H