3 #ifndef __CDS_GC_IMPL_HP_DECL_H
4 #define __CDS_GC_IMPL_HP_DECL_H
6 #include <stdexcept> // overflow_error
7 #include <cds/gc/details/hp.h>
8 #include <cds/details/marked_ptr.h>
10 namespace cds { namespace gc {
11 /// @defgroup cds_garbage_collector Garbage collectors
13 /// Hazard Pointer garbage collector
14 /** @ingroup cds_garbage_collector
15 @headerfile cds/gc/hp.h
17 Implementation of classic Hazard Pointer garbage collector.
20 - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
21 - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
22 - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
24 Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is
25 GC class \p %cds::gc::HP and its nested classes. Before use any HP-related class you must initialize HP garbage collector
26 by contructing \p %cds::gc::HP object in beginning of your \p main().
27 See \ref cds_how_to_use "How to use" section for details how to apply garbage collector.
32 /// Native guarded pointer type
34 @headerfile cds/gc/hp.h
36 typedef gc::hp::hazard_pointer guarded_pointer;
40 @headerfile cds/gc/hp.h
42 template <typename T> using atomic_ref = atomics::atomic<T *>;
44 /// Atomic marked pointer
46 @headerfile cds/gc/hp.h
48 template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
52 @headerfile cds/gc/hp.h
54 template <typename T> using atomic_type = atomics::atomic<T>;
56 /// Thread GC implementation for internal usage
58 @headerfile cds/gc/hp.h
60 typedef hp::ThreadGC thread_gc_impl;
62 /// Wrapper for hp::ThreadGC class
64 @headerfile cds/gc/hp.h
65 This class performs automatically attaching/detaching Hazard Pointer GC
66 for the current thread.
68 class thread_gc: public thread_gc_impl
77 The constructor attaches the current thread to the Hazard Pointer GC
78 if it is not yet attached.
79 The \p bPersistent parameter specifies attachment persistence:
80 - \p true - the class destructor will not detach the thread from Hazard Pointer GC.
81 - \p false (default) - the class destructor will detach the thread from Hazard Pointer GC.
84 bool bPersistent = false
85 ) ; //inline in hp_impl.h
89 If the object has been created in persistent mode, the destructor does nothing.
90 Otherwise it detaches the current thread from Hazard Pointer GC.
92 ~thread_gc() ; // inline in hp_impl.h
94 public: // for internal use only!!!
96 static cds::gc::hp::details::hp_guard& alloc_guard(); // inline in hp_impl.h
97 static void free_guard( cds::gc::hp::details::hp_guard& g ); // inline in hp_impl.h
101 /// Hazard Pointer guard
103 @headerfile cds/gc/hp.h
105 A guard is the hazard pointer.
106 Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
108 A \p %Guard object is not copy- and move-constructible
109 and not copy- and move-assignable.
111 class Guard : public hp::guard
114 typedef hp::guard base_class;
119 Guard(); // inline in hp_impl.h
122 Guard( Guard const& ) = delete;
123 Guard( Guard&& s ) = delete;
124 Guard& operator=(Guard const&) = delete;
125 Guard& operator=(Guard&&) = delete;
128 /// Protects a pointer of type \p atomic<T*>
130 Return the value of \p toGuard
132 The function tries to load \p toGuard and to store it
133 to the HP slot repeatedly until the guard's value equals \p toGuard
135 template <typename T>
136 T protect( atomics::atomic<T> const& toGuard )
138 T pCur = toGuard.load(atomics::memory_order_relaxed);
141 pRet = assign( pCur );
142 pCur = toGuard.load(atomics::memory_order_acquire);
143 } while ( pRet != pCur );
147 /// Protects a converted pointer of type \p atomic<T*>
149 Return the value of \p toGuard
151 The function tries to load \p toGuard and to store result of \p f functor
152 to the HP slot repeatedly until the guard's value equals \p toGuard.
154 The function is useful for intrusive containers when \p toGuard is a node pointer
155 that should be converted to a pointer to the value before protecting.
156 The parameter \p f of type Func is a functor that makes this conversion:
159 value_type * operator()( T * p );
162 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
164 template <typename T, class Func>
165 T protect( atomics::atomic<T> const& toGuard, Func f )
167 T pCur = toGuard.load(atomics::memory_order_relaxed);
172 pCur = toGuard.load(atomics::memory_order_acquire);
173 } while ( pRet != pCur );
177 /// Store \p p to the guard
179 The function equals to a simple assignment the value \p p to guard, no loop is performed.
180 Can be used for a pointer that cannot be changed concurrently
182 template <typename T>
185 return base_class::operator =(p);
189 std::nullptr_t assign( std::nullptr_t )
191 return base_class::operator =(nullptr);
195 /// Copy from \p src guard to \p this guard
196 void copy( Guard const& src )
198 assign( src.get_native() );
201 /// Store marked pointer \p p to the guard
203 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
204 Can be used for a marked pointer that cannot be changed concurrently.
206 template <typename T, int BITMASK>
207 T * assign( cds::details::marked_ptr<T, BITMASK> p )
209 return base_class::operator =( p.ptr() );
212 /// Clear value of the guard
218 /// Get the value currently protected
219 template <typename T>
222 return reinterpret_cast<T *>( get_native() );
225 /// Get native hazard pointer stored
226 guarded_pointer get_native() const
228 return base_class::get();
232 /// Array of Hazard Pointer guards
234 @headerfile cds/gc/hp.h
235 The class is intended for allocating an array of hazard pointer guards.
236 Template parameter \p Count defines the size of the array.
238 A \p %GuardArray object is not copy- and move-constructible
239 and not copy- and move-assignable.
241 template <size_t Count>
242 class GuardArray : public hp::array<Count>
245 typedef hp::array<Count> base_class;
248 /// Rebind array for other size \p Count2
249 template <size_t Count2>
251 typedef GuardArray<Count2> other ; ///< rebinding result
256 GuardArray(); // inline in hp_impl.h
259 GuardArray( GuardArray const& ) = delete;
260 GuardArray( GuardArray&& ) = delete;
261 GuardArray& operator=(GuardArray const&) = delete;
262 GuardArray& operator-(GuardArray&&) = delete;
265 /// Protects a pointer of type \p atomic<T*>
267 Return the value of \p toGuard
269 The function tries to load \p toGuard and to store it
270 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
272 template <typename T>
273 T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
277 pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) );
278 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
283 /// Protects a pointer of type \p atomic<T*>
285 Return the value of \p toGuard
287 The function tries to load \p toGuard and to store it
288 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
290 The function is useful for intrusive containers when \p toGuard is a node pointer
291 that should be converted to a pointer to the value type before guarding.
292 The parameter \p f of type Func is a functor that makes this conversion:
295 value_type * operator()( T * p );
298 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
300 template <typename T, class Func>
301 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
305 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
306 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
311 /// Store \p to the slot \p nIndex
313 The function equals to a simple assignment, no loop is performed.
315 template <typename T>
316 T * assign( size_t nIndex, T * p )
318 base_class::set(nIndex, p);
322 /// Store marked pointer \p p to the guard
324 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
325 Can be used for a marked pointer that cannot be changed concurrently.
327 template <typename T, int BITMASK>
328 T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p )
330 return assign( nIndex, p.ptr() );
333 /// Copy guarded value from \p src guard to slot at index \p nIndex
334 void copy( size_t nIndex, Guard const& src )
336 assign( nIndex, src.get_native() );
339 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
340 void copy( size_t nDestIndex, size_t nSrcIndex )
342 assign( nDestIndex, get_native( nSrcIndex ));
345 /// Clear value of the slot \p nIndex
346 void clear( size_t nIndex )
348 base_class::clear( nIndex );
351 /// Get current value of slot \p nIndex
352 template <typename T>
353 T * get( size_t nIndex ) const
355 return reinterpret_cast<T *>( get_native( nIndex ) );
358 /// Get native hazard pointer stored
359 guarded_pointer get_native( size_t nIndex ) const
361 return base_class::operator[](nIndex).get();
364 /// Capacity of the guard array
365 static CDS_CONSTEXPR size_t capacity()
373 A guarded pointer is a pair of a pointer and GC's guard.
374 Usually, it is used for returning a pointer to the item from an lock-free container.
375 The guard prevents the pointer to be early disposed (freed) by GC.
376 After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
379 - \p GuardedType - a type which the guard stores
380 - \p ValueType - a value type
381 - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
383 For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
384 In such case the \p %guarded_ptr is:
386 typedef cds::gc::HP::guarded_ptr< foo > intrusive_guarded_ptr;
389 For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
397 struct value_accessor {
398 std::string* operator()( foo* pFoo ) const
400 return &(pFoo->value);
405 typedef cds::gc::HP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
408 You don't need use this class directly.
409 All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
411 template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
415 struct trivial_cast {
416 ValueType * operator()( GuardedType * p ) const
424 typedef GuardedType guarded_type; ///< Guarded type
425 typedef ValueType value_type; ///< Value type
427 /// Functor for casting \p guarded_type to \p value_type
428 typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
431 typedef cds::gc::hp::details::hp_guard native_guard;
436 native_guard * m_pGuard;
440 /// Creates empty guarded pointer
441 guarded_ptr() CDS_NOEXCEPT
446 /// Initializes guarded pointer with \p p
447 explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
453 explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
454 : m_pGuard( nullptr )
459 guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
460 : m_pGuard( gp.m_pGuard )
462 gp.m_pGuard = nullptr;
465 /// The guarded pointer is not copy-constructible
466 guarded_ptr( guarded_ptr const& gp ) = delete;
468 /// Clears the guarded pointer
470 \ref release is called if guarded pointer is not \ref empty
472 ~guarded_ptr() CDS_NOEXCEPT
477 /// Move-assignment operator
478 guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
480 // Hazard Pointer array is organized as a stack
481 if ( m_pGuard && m_pGuard > gp.m_pGuard ) {
482 m_pGuard->set( gp.m_pGuard->get(atomics::memory_order_relaxed) );
487 m_pGuard = gp.m_pGuard;
488 gp.m_pGuard = nullptr;
493 /// The guarded pointer is not copy-assignable
494 guarded_ptr& operator=(guarded_ptr const& gp) = delete;
496 /// Returns a pointer to guarded value
497 value_type * operator ->() const CDS_NOEXCEPT
500 return value_cast()( reinterpret_cast<guarded_type *>(m_pGuard->get()));
503 /// Returns a reference to guarded value
504 value_type& operator *() CDS_NOEXCEPT
507 return *value_cast()(reinterpret_cast<guarded_type *>(m_pGuard->get()));
510 /// Returns const reference to guarded value
511 value_type const& operator *() const CDS_NOEXCEPT
514 return *value_cast()(reinterpret_cast<guarded_type *>(m_pGuard->get()));
517 /// Checks if the guarded pointer is \p nullptr
518 bool empty() const CDS_NOEXCEPT
520 return !m_pGuard || m_pGuard->get( atomics::memory_order_relaxed ) == nullptr;
523 /// \p bool operator returns <tt>!empty()</tt>
524 explicit operator bool() const CDS_NOEXCEPT
529 /// Clears guarded pointer
531 If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
532 Dereferncing the guarded pointer after \p release() is dangerous.
534 void release() CDS_NOEXCEPT
540 // For internal use only!!!
541 native_guard& guard() CDS_NOEXCEPT
554 m_pGuard = &thread_gc::alloc_guard();
560 thread_gc::free_guard( *m_pGuard );
569 enum class scan_type {
570 classic = hp::classic, ///< classic scan as described in Michael's papers
571 inplace = hp::inplace ///< inplace scan without allocation
573 /// Initializes hp::GarbageCollector singleton
575 The constructor initializes GC singleton with passed parameters.
576 If GC instance is not exist then the function creates the instance.
577 Otherwise it does nothing.
579 The Michael's HP reclamation schema depends of three parameters:
580 - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
581 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
582 uses maximum of the hazard pointer count for CDS library.
583 - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
584 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
585 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
588 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
589 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
590 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
591 scan_type nScanType = scan_type::inplace ///< Scan type (see \p scan_type enum)
594 hp::GarbageCollector::Construct(
598 static_cast<hp::scan_type>(nScanType)
602 /// Terminates GC singleton
604 The destructor calls \code hp::GarbageCollector::Destruct( true ) \endcode
608 hp::GarbageCollector::Destruct( true );
611 /// Checks if count of hazard pointer is no less than \p nCountNeeded
613 If \p bRaiseException is \p true (that is the default), the function raises
614 an \p std::overflow_error exception "Too few hazard pointers"
615 if \p nCountNeeded is more than the count of hazard pointer per thread.
617 static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
619 if ( hp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
620 if ( bRaiseException )
621 throw std::overflow_error( "Too few hazard pointers" );
627 /// Returns max Hazard Pointer count
628 static size_t max_hazard_count()
630 return hp::GarbageCollector::instance().getHazardPointerCount();
633 /// Returns max count of thread
634 static size_t max_thread_count()
636 return hp::GarbageCollector::instance().getMaxThreadCount();
639 /// Returns capacity of retired pointer array
640 static size_t retired_array_capacity()
642 return hp::GarbageCollector::instance().getMaxRetiredPtrCount();
645 /// Retire pointer \p p with function \p pFunc
647 The function places pointer \p p to array of pointers ready for removing.
648 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
649 Deleting the pointer is the function \p pFunc call.
651 template <typename T>
652 static void retire( T * p, void (* pFunc)(T *) ); // inline in hp_impl.h
654 /// Retire pointer \p p with functor of type \p Disposer
656 The function places pointer \p p to array of pointers ready for removing.
657 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
659 Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
661 template <typename T>
663 void operator()( T * p ) ; // disposing operator
666 Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
667 - it should be stateless functor
668 - it should be default-constructible
669 - the result of functor call with argument \p p should not depend on where the functor will be called.
672 Operator \p delete functor:
674 template <typename T>
676 void operator ()( T * p ) {
681 // How to call GC::retire method
684 // ... use p in lock-free manner
686 cds::gc::HP::retire<disposer>( p ) ; // place p to retired pointer array of HP GC
689 Functor based on \p std::allocator :
691 template <typename ALLOC = std::allocator<int> >
693 template <typename T>
694 void operator()( T * p ) {
695 typedef typename ALLOC::templare rebind<T>::other alloc_t;
698 a.deallocate( p, 1 );
703 template <class Disposer, typename T>
704 static void retire( T * p ); // inline in hp_impl.h
706 /// Get current scan strategy
707 static scan_type getScanType()
709 return static_cast<scan_type>( hp::GarbageCollector::instance().getScanType());
712 /// Set current scan strategy
713 static void setScanType(
714 scan_type nScanType ///< new scan strategy
717 hp::GarbageCollector::instance().setScanType( static_cast<hp::scan_type>(nScanType) );
720 /// Checks if Hazard Pointer GC is constructed and may be used
723 return hp::GarbageCollector::isUsed();
726 /// Forced GC cycle call for current thread
728 Usually, this function should not be called directly.
730 static void scan() ; // inline in hp_impl.h
732 /// Synonym for \ref scan()
733 static void force_dispose()
738 }} // namespace cds::gc
740 #endif // #ifndef __CDS_GC_IMPL_HP_DECL_H