2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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 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
187 hp_record( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
191 /// Clears all hazard pointers
199 m_nSync.fetch_add( 1, atomics::memory_order_acq_rel );
202 } // namespace details
204 /// GarbageCollector::Scan phase strategy
206 See GarbageCollector::Scan for explanation
209 classic, ///< classic scan as described in Michael's works (see GarbageCollector::classic_scan)
210 inplace ///< inplace scan without allocation (see GarbageCollector::inplace_scan)
213 /// Hazard Pointer singleton
215 Safe memory reclamation schema by Michael "Hazard Pointers"
218 \li [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
219 \li [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
220 \li [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
223 class CDS_EXPORT_API GarbageCollector
226 typedef cds::atomicity::event_counter event_counter ; ///< event counter type
228 /// Internal GC statistics
229 struct InternalState {
230 size_t nHPCount ; ///< HP count per thread (const)
231 size_t nMaxThreadCount ; ///< Max thread count (const)
232 size_t nMaxRetiredPtrCount ; ///< Max retired pointer count per thread (const)
233 size_t nHPRecSize ; ///< Size of HP record, bytes (const)
235 size_t nHPRecAllocated ; ///< Count of HP record allocations
236 size_t nHPRecUsed ; ///< Count of HP record used
237 size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers
238 size_t nRetiredPtrInFreeHPRecs ; ///< Count of retired pointer in free (unused) HP records
240 event_counter::value_type evcAllocHPRec ; ///< Count of \p hp_record allocations
241 event_counter::value_type evcRetireHPRec ; ///< Count of \p hp_record retire events
242 event_counter::value_type evcAllocNewHPRec; ///< Count of new \p hp_record allocations from heap
243 event_counter::value_type evcDeleteHPRec ; ///< Count of \p hp_record deletions
245 event_counter::value_type evcScanCall ; ///< Count of Scan calling
246 event_counter::value_type evcHelpScanCall ; ///< Count of HelpScan calling
247 event_counter::value_type evcScanFromHelpScan;///< Count of Scan calls from HelpScan
249 event_counter::value_type evcDeletedNode ; ///< Count of deleting of retired objects
250 event_counter::value_type evcDeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
253 /// No GarbageCollector object is created
254 class not_initialized : public std::runtime_error
259 : std::runtime_error( "Global Hazard Pointer GarbageCollector is not initialized" )
264 /// Not enough required Hazard Pointer count
265 class too_many_hazard_ptr : public std::length_error
269 too_many_hazard_ptr()
270 : std::length_error( "Not enough required Hazard Pointer count" )
276 /// Internal GC statistics
278 event_counter m_AllocHPRec ; ///< Count of \p hp_record allocations
279 event_counter m_RetireHPRec ; ///< Count of \p hp_record retire events
280 event_counter m_AllocNewHPRec ; ///< Count of new \p hp_record allocations from heap
281 event_counter m_DeleteHPRec ; ///< Count of \p hp_record deletions
283 event_counter m_ScanCallCount ; ///< Count of Scan calling
284 event_counter m_HelpScanCallCount ; ///< Count of HelpScan calling
285 event_counter m_CallScanFromHelpScan ; ///< Count of Scan calls from HelpScan
287 event_counter m_DeletedNode ; ///< Count of retired objects deleting
288 event_counter m_DeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
291 /// Internal list of cds::gc::hp::details::hp_record
292 struct hplist_node : public details::hp_record
294 hplist_node * m_pNextNode; ///< next hazard ptr record in list
295 atomics::atomic<OS::ThreadId> m_idOwner; ///< Owner thread id; 0 - the record is free (not owned)
296 atomics::atomic<bool> m_bFree; ///< true if record if free (not owned)
299 hplist_node( const GarbageCollector& HzpMgr )
300 : hp_record( HzpMgr ),
301 m_pNextNode( nullptr ),
302 m_idOwner( OS::c_NullThreadId ),
308 assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId );
309 assert( m_bFree.load(atomics::memory_order_relaxed) );
314 atomics::atomic<hplist_node *> m_pListHead ; ///< Head of GC list
316 static GarbageCollector * m_pHZPManager ; ///< GC instance pointer
318 Statistics m_Stat ; ///< Internal statistics
319 bool m_bStatEnabled ; ///< true - statistics enabled
321 const size_t m_nHazardPointerCount ; ///< max count of thread's hazard pointer
322 const size_t m_nMaxThreadCount ; ///< max count of thread
323 const size_t m_nMaxRetiredPtrCount ; ///< max count of retired ptr per thread
324 scan_type m_nScanType ; ///< scan type (see \ref scan_type enum)
330 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
331 size_t nMaxThreadCount = 0, ///< Max count of thread
332 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects
333 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
339 /// Allocate new HP record
340 hplist_node * NewHPRec();
342 /// Permanently deletes HPrecord \p pNode
344 Caveat: for performance reason this function is defined as inline and cannot be called directly
346 void DeleteHPRec( hplist_node * pNode );
348 void detachAllThread();
351 /// Creates GarbageCollector singleton
353 GC is the singleton. If GC instance is not exist then the function creates the instance.
354 Otherwise it does nothing.
356 The Michael's HP reclamation schema depends of three parameters:
358 \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
359 the data structure algorithms. By default, if \p nHazardPtrCount = 0,
360 the function uses maximum of HP count for CDS library.
362 \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
364 \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
365 \p nHazardPtrCount * \p nMaxThreadCount.
366 Default is 2 * \p nHazardPtrCount * \p nMaxThreadCount.
368 static void CDS_STDCALL Construct(
369 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
370 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
371 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
372 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
375 /// Destroys global instance of GarbageCollector
377 The parameter \p bDetachAll should be used carefully: if its value is \p true,
378 then the destroying GC automatically detaches all attached threads. This feature
379 can be useful when you have no control over the thread termination, for example,
380 when \p libcds is injected into existing external thread.
382 static void CDS_STDCALL Destruct(
383 bool bDetachAll = false ///< Detach all threads
386 /// Returns pointer to GarbageCollector instance
387 static GarbageCollector& instance()
389 if ( !m_pHZPManager )
390 throw not_initialized();
391 return *m_pHZPManager;
394 /// Checks if global GC object is constructed and may be used
395 static bool isUsed() CDS_NOEXCEPT
397 return m_pHZPManager != nullptr;
400 /// Returns max Hazard Pointer count defined in construction time
401 size_t getHazardPointerCount() const CDS_NOEXCEPT
403 return m_nHazardPointerCount;
406 /// Returns max thread count defined in construction time
407 size_t getMaxThreadCount() const CDS_NOEXCEPT
409 return m_nMaxThreadCount;
412 /// Returns max size of retired objects array. It is defined in construction time
413 size_t getMaxRetiredPtrCount() const CDS_NOEXCEPT
415 return m_nMaxRetiredPtrCount;
418 // Internal statistics
420 /// Get internal statistics
421 InternalState& getInternalState(InternalState& stat) const;
423 /// Checks if internal statistics enabled
424 bool isStatisticsEnabled() const { return m_bStatEnabled; }
426 /// Enables/disables internal statistics
427 bool enableStatistics( bool bEnable )
429 bool bEnabled = m_bStatEnabled;
430 m_bStatEnabled = bEnable;
434 /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
436 If \p nRequiredCount > getHazardPointerCount() then the exception \p too_many_hazard_ptr is thrown
438 static void checkHPCount( unsigned int nRequiredCount )
440 if ( instance().getHazardPointerCount() < nRequiredCount )
441 throw too_many_hazard_ptr();
444 /// Get current scan strategy
445 scan_type getScanType() const
450 /// Set current scan strategy
451 /** @anchor hzp_gc_setScanType
452 Scan strategy changing is allowed on the fly.
455 scan_type nScanType ///< new scan strategy
458 m_nScanType = nScanType;
461 public: // Internals for threads
463 /// Allocates Hazard Pointer GC record. For internal use only
464 details::hp_record * alloc_hp_record();
466 /// Free HP record. For internal use only
467 void free_hp_record( details::hp_record * pRec );
469 /// The main garbage collecting function
471 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
474 There are the following scan algorithm:
475 - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use
476 - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory
478 Use \ref hzp_gc_setScanType "setScanType" member function to setup appropriate scan algorithm.
480 void Scan( details::hp_record * pRec )
482 switch ( m_nScanType ) {
484 inplace_scan( pRec );
487 assert(false) ; // Forgotten something?..
489 classic_scan( pRec );
494 /// Helper scan routine
496 The function guarantees that every node that is eligible for reuse is eventually freed, barring
497 thread failures. To do so, after executing Scan, a thread executes a HelpScan,
498 where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
499 to thread's list of reclaimed pointers.
501 The function is called internally by Scan.
503 void HelpScan( details::hp_record * pThis );
506 /// Classic scan algorithm
507 /** @anchor hzp_gc_classic_scan
508 Classical scan algorithm as described in Michael's paper.
510 A scan includes four stages. The first stage involves scanning the array HP for non-null values.
511 Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer.
512 Only stage 1 accesses shared variables. The following stages operate only on private variables.
514 The second stage of a scan involves sorting local list of protected pointers to allow
515 binary search in the third stage.
517 The third stage of a scan involves checking each reclaimed node
518 against the pointers in local list of protected pointers. If the binary search yields
519 no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list
520 of reclaimed pointers.
522 The forth stage prepares new thread's private list of reclaimed pointers
523 that could not be freed during the current scan, where they remain until the next scan.
525 This algorithm allocates memory for internal HP array.
527 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
530 void classic_scan( details::hp_record * pRec );
532 /// In-place scan algorithm
533 /** @anchor hzp_gc_inplace_scan
534 Unlike the \ref hzp_gc_classic_scan "classic_scan" algorithm, \p inplace_scan does not allocate any memory.
535 All operations are performed in-place.
537 void inplace_scan( details::hp_record * pRec );
540 /// Thread's hazard pointer manager
542 To use Hazard Pointer reclamation schema each thread object must be linked with the object of ThreadGC class
543 that interacts with GarbageCollector global object. The linkage is performed by calling \ref cds_threading "cds::threading::Manager::attachThread()"
544 on the start of each thread that uses HP GC. Before terminating the thread linked to HP GC it is necessary to call
545 \ref cds_threading "cds::threading::Manager::detachThread()".
549 GarbageCollector& m_HzpManager; ///< Hazard Pointer GC singleton
550 details::hp_record * m_pHzpRec; ///< Pointer to thread's HZP record
553 /// Default constructor
555 : m_HzpManager( GarbageCollector::instance() ),
559 /// The object is not copy-constructible
560 ThreadGC( ThreadGC const& ) = delete;
567 /// Checks if thread GC is initialized
568 bool isInitialized() const { return m_pHzpRec != nullptr; }
570 /// Initialization. Repeat call is available
574 m_pHzpRec = m_HzpManager.alloc_hp_record();
577 /// Finalization. Repeat call is available
581 details::hp_record * pRec = m_pHzpRec;
583 m_HzpManager.free_hp_record( pRec );
587 /// Initializes HP guard \p guard
588 details::hp_guard& allocGuard()
591 return m_pHzpRec->m_hzp.alloc();
594 /// Frees HP guard \p guard
595 void freeGuard( details::hp_guard& guard )
598 m_pHzpRec->m_hzp.free( guard );
601 /// Initializes HP guard array \p arr
602 template <size_t Count>
603 void allocGuard( details::hp_array<Count>& arr )
606 m_pHzpRec->m_hzp.alloc( arr );
609 /// Frees HP guard array \p arr
610 template <size_t Count>
611 void freeGuard( details::hp_array<Count>& arr )
614 m_pHzpRec->m_hzp.free( arr );
617 /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
618 template <typename T>
619 void retirePtr( T * p, void (* pFunc)(T *) )
630 free_retired_ptr_func hpFunc;
632 cast_func.pFunc = pFunc;
634 retirePtr( details::retired_ptr( cast_ptr.hp, cast_func.hpFunc ) );
636 retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc )));
639 /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation
640 void retirePtr( details::retired_ptr const& p )
642 m_pHzpRec->m_arrRetired.push( p );
644 if ( m_pHzpRec->m_arrRetired.isFull() ) {
645 // Max of retired pointer count is reached. Do scan
650 /// Run retiring scan cycle
653 m_HzpManager.Scan( m_pHzpRec );
654 m_HzpManager.HelpScan( m_pHzpRec );
659 assert( m_pHzpRec != nullptr );
666 This class encapsulates Hazard Pointer guard to protect a pointer against deletion.
667 It allocates one HP from thread's HP array in constructor and free the hazard pointer allocated
672 details::hp_guard& m_hp ; ///< Hazard pointer guarded
675 typedef details::hp_guard::hazard_ptr hazard_ptr ; ///< Hazard pointer type
678 /// Allocates HP guard
679 guard(); // inline in hp_impl.h
681 /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T
682 template <typename T>
683 explicit guard( T * p ); // inline in hp_impl.h
685 /// Frees HP guard. The pointer guarded may be deleted after this.
686 ~guard(); // inline in hp_impl.h
688 /// Protects the pointer \p p against reclamation (guards the pointer).
689 template <typename T>
690 T * operator =( T * p )
696 std::nullptr_t operator =(std::nullptr_t)
698 return m_hp = nullptr;
702 /// Get raw guarded pointer
703 hazard_ptr get() const
709 /// Auto-managed array of hazard pointers
711 This class is wrapper around cds::gc::hp::details::hp_array class.
712 \p Count is the size of HP array
714 template <size_t Count>
715 class array : public details::hp_array<Count>
718 /// Rebind array for other size \p COUNT2
719 template <size_t Count2>
721 typedef array<Count2> other; ///< rebinding result
725 /// Allocates array of HP guard
726 array(); // inline in hp_impl.h
728 /// Frees array of HP guard
729 ~array(); //inline in hp_impl.h
733 }} // namespace cds::gc
739 namespace gc { namespace hp { namespace details {
741 inline retired_vector::retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr )
742 : m_arr( HzpMgr.getMaxRetiredPtrCount() ),
746 inline hp_record::hp_record( const cds::gc::hp::GarbageCollector& HzpMgr )
747 : m_hzp( HzpMgr.getHazardPointerCount() )
748 , m_arrRetired( HzpMgr )
752 }}} // namespace gc::hp::details
757 #if CDS_COMPILER == CDS_COMPILER_MSVC
758 # pragma warning(pop)
761 #endif // #ifndef CDSLIB_GC_DETAILS_HP_H