3 #ifndef CDSLIB_GC_IMPL_HP_DECL_H
4 #define CDSLIB_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;
123 Guard( Guard const& ) = delete;
124 Guard( Guard&& s ) = delete;
125 Guard& operator=(Guard const&) = delete;
126 Guard& operator=(Guard&&) = delete;
129 /// Protects a pointer of type \p atomic<T*>
131 Return the value of \p toGuard
133 The function tries to load \p toGuard and to store it
134 to the HP slot repeatedly until the guard's value equals \p toGuard
136 template <typename T>
137 T protect( atomics::atomic<T> const& toGuard )
139 T pCur = toGuard.load(atomics::memory_order_acquire);
142 pRet = assign( pCur );
143 pCur = toGuard.load(atomics::memory_order_acquire);
144 } while ( pRet != pCur );
148 /// Protects a converted pointer of type \p atomic<T*>
150 Return the value of \p toGuard
152 The function tries to load \p toGuard and to store result of \p f functor
153 to the HP slot repeatedly until the guard's value equals \p toGuard.
155 The function is useful for intrusive containers when \p toGuard is a node pointer
156 that should be converted to a pointer to the value before protecting.
157 The parameter \p f of type Func is a functor that makes this conversion:
160 value_type * operator()( T * p );
163 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
165 template <typename T, class Func>
166 T protect( atomics::atomic<T> const& toGuard, Func f )
168 T pCur = toGuard.load(atomics::memory_order_acquire);
173 pCur = toGuard.load(atomics::memory_order_acquire);
174 } while ( pRet != pCur );
178 /// Store \p p to the guard
180 The function equals to a simple assignment the value \p p to guard, no loop is performed.
181 Can be used for a pointer that cannot be changed concurrently
183 template <typename T>
184 T * assign( T * p ); // inline in hp_impl.h
187 std::nullptr_t assign( std::nullptr_t )
189 return base_class::operator =(nullptr);
193 /// Copy from \p src guard to \p this guard
194 void copy( Guard const& src )
196 assign( src.get_native() );
199 /// Store marked pointer \p p to the guard
201 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
202 Can be used for a marked pointer that cannot be changed concurrently.
204 template <typename T, int BITMASK>
205 T * assign( cds::details::marked_ptr<T, BITMASK> p )
207 return base_class::operator =( p.ptr() );
210 /// Clear value of the guard
216 /// Get the value currently protected
217 template <typename T>
220 return reinterpret_cast<T *>( get_native() );
223 /// Get native hazard pointer stored
224 guarded_pointer get_native() const
226 return base_class::get();
230 /// Array of Hazard Pointer guards
232 @headerfile cds/gc/hp.h
233 The class is intended for allocating an array of hazard pointer guards.
234 Template parameter \p Count defines the size of the array.
236 A \p %GuardArray object is not copy- and move-constructible
237 and not copy- and move-assignable.
239 template <size_t Count>
240 class GuardArray : public hp::array<Count>
243 typedef hp::array<Count> base_class;
246 /// Rebind array for other size \p Count2
247 template <size_t Count2>
249 typedef GuardArray<Count2> other ; ///< rebinding result
258 GuardArray( GuardArray const& ) = delete;
259 GuardArray( GuardArray&& ) = delete;
260 GuardArray& operator=(GuardArray const&) = delete;
261 GuardArray& operator=(GuardArray&&) = delete;
264 /// Protects a pointer of type \p atomic<T*>
266 Return the value of \p toGuard
268 The function tries to load \p toGuard and to store it
269 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
271 template <typename T>
272 T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
276 pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire) );
277 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
282 /// Protects a pointer of type \p atomic<T*>
284 Return the value of \p toGuard
286 The function tries to load \p toGuard and to store it
287 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
289 The function is useful for intrusive containers when \p toGuard is a node pointer
290 that should be converted to a pointer to the value type before guarding.
291 The parameter \p f of type Func is a functor that makes this conversion:
294 value_type * operator()( T * p );
297 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
299 template <typename T, class Func>
300 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
304 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire) ));
305 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
310 /// Store \p to the slot \p nIndex
312 The function equals to a simple assignment, no loop is performed.
314 template <typename T>
315 T * assign( size_t nIndex, T * p ); // inline in hp_impl.h
317 /// Store marked pointer \p p to the guard
319 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
320 Can be used for a marked pointer that cannot be changed concurrently.
322 template <typename T, int BITMASK>
323 T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p )
325 return assign( nIndex, p.ptr() );
328 /// Copy guarded value from \p src guard to slot at index \p nIndex
329 void copy( size_t nIndex, Guard const& src )
331 assign( nIndex, src.get_native() );
334 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
335 void copy( size_t nDestIndex, size_t nSrcIndex )
337 assign( nDestIndex, get_native( nSrcIndex ));
340 /// Clear value of the slot \p nIndex
341 void clear( size_t nIndex )
343 base_class::clear( nIndex );
346 /// Get current value of slot \p nIndex
347 template <typename T>
348 T * get( size_t nIndex ) const
350 return reinterpret_cast<T *>( get_native( nIndex ) );
353 /// Get native hazard pointer stored
354 guarded_pointer get_native( size_t nIndex ) const
356 return base_class::operator[](nIndex).get();
359 /// Capacity of the guard array
360 static CDS_CONSTEXPR size_t capacity()
368 A guarded pointer is a pair of a pointer and GC's guard.
369 Usually, it is used for returning a pointer to the item from an lock-free container.
370 The guard prevents the pointer to be early disposed (freed) by GC.
371 After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
374 - \p GuardedType - a type which the guard stores
375 - \p ValueType - a value type
376 - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
378 For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
379 In such case the \p %guarded_ptr is:
381 typedef cds::gc::HP::guarded_ptr< foo > intrusive_guarded_ptr;
384 For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
392 struct value_accessor {
393 std::string* operator()( foo* pFoo ) const
395 return &(pFoo->value);
400 typedef cds::gc::HP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
403 You don't need use this class directly.
404 All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
406 template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
410 struct trivial_cast {
411 ValueType * operator()( GuardedType * p ) const
419 typedef GuardedType guarded_type; ///< Guarded type
420 typedef ValueType value_type; ///< Value type
422 /// Functor for casting \p guarded_type to \p value_type
423 typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
426 typedef cds::gc::hp::details::hp_guard native_guard;
431 native_guard * m_pGuard;
435 /// Creates empty guarded pointer
436 guarded_ptr() CDS_NOEXCEPT
443 /// Initializes guarded pointer with \p p
444 explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
445 : m_pGuard( nullptr )
449 explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
450 : m_pGuard( nullptr )
455 guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
456 : m_pGuard( gp.m_pGuard )
458 gp.m_pGuard = nullptr;
461 /// The guarded pointer is not copy-constructible
462 guarded_ptr( guarded_ptr const& gp ) = delete;
464 /// Clears the guarded pointer
466 \ref release is called if guarded pointer is not \ref empty
468 ~guarded_ptr() CDS_NOEXCEPT
473 /// Move-assignment operator
474 guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
476 // Hazard Pointer array is organized as a stack
477 if ( m_pGuard && m_pGuard > gp.m_pGuard ) {
478 m_pGuard->set( gp.m_pGuard->get(atomics::memory_order_relaxed) );
483 m_pGuard = gp.m_pGuard;
484 gp.m_pGuard = nullptr;
489 /// The guarded pointer is not copy-assignable
490 guarded_ptr& operator=(guarded_ptr const& gp) = delete;
492 /// Returns a pointer to guarded value
493 value_type * operator ->() const CDS_NOEXCEPT
496 return value_cast()( reinterpret_cast<guarded_type *>(m_pGuard->get()));
499 /// Returns a reference to guarded value
500 value_type& operator *() CDS_NOEXCEPT
503 return *value_cast()(reinterpret_cast<guarded_type *>(m_pGuard->get()));
506 /// Returns const reference to guarded value
507 value_type const& operator *() const CDS_NOEXCEPT
510 return *value_cast()(reinterpret_cast<guarded_type *>(m_pGuard->get()));
513 /// Checks if the guarded pointer is \p nullptr
514 bool empty() const CDS_NOEXCEPT
516 return !m_pGuard || m_pGuard->get( atomics::memory_order_relaxed ) == nullptr;
519 /// \p bool operator returns <tt>!empty()</tt>
520 explicit operator bool() const CDS_NOEXCEPT
525 /// Clears guarded pointer
527 If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
528 Dereferncing the guarded pointer after \p release() is dangerous.
530 void release() CDS_NOEXCEPT
536 // For internal use only!!!
537 native_guard& guard() CDS_NOEXCEPT
544 void reset(guarded_type * p) CDS_NOEXCEPT
557 m_pGuard = &thread_gc::alloc_guard();
563 thread_gc::free_guard( *m_pGuard );
572 enum class scan_type {
573 classic = hp::classic, ///< classic scan as described in Michael's papers
574 inplace = hp::inplace ///< inplace scan without allocation
576 /// Initializes %HP singleton
578 The constructor initializes GC singleton with passed parameters.
579 If GC instance is not exist then the function creates the instance.
580 Otherwise it does nothing.
582 The Michael's %HP reclamation schema depends of three parameters:
583 - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
584 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
585 uses maximum of the hazard pointer count for CDS library.
586 - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
587 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
588 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
591 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
592 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
593 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
594 scan_type nScanType = scan_type::inplace ///< Scan type (see \p scan_type enum)
597 hp::GarbageCollector::Construct(
601 static_cast<hp::scan_type>(nScanType)
605 /// Terminates GC singleton
607 The destructor destroys %HP global object. After calling of this function you may \b NOT
608 use CDS data structures based on \p %cds::gc::HP.
609 Usually, %HP object is destroyed at the end of your \p main().
613 hp::GarbageCollector::Destruct( true );
616 /// Checks if count of hazard pointer is no less than \p nCountNeeded
618 If \p bRaiseException is \p true (that is the default), the function raises
619 an \p std::overflow_error exception "Too few hazard pointers"
620 if \p nCountNeeded is more than the count of hazard pointer per thread.
622 static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
624 if ( hp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
625 if ( bRaiseException )
626 throw std::overflow_error( "Too few hazard pointers" );
632 /// Returns max Hazard Pointer count
633 static size_t max_hazard_count()
635 return hp::GarbageCollector::instance().getHazardPointerCount();
638 /// Returns max count of thread
639 static size_t max_thread_count()
641 return hp::GarbageCollector::instance().getMaxThreadCount();
644 /// Returns capacity of retired pointer array
645 static size_t retired_array_capacity()
647 return hp::GarbageCollector::instance().getMaxRetiredPtrCount();
650 /// Retire pointer \p p with function \p pFunc
652 The function places pointer \p p to array of pointers ready for removing.
653 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
654 Deleting the pointer is the function \p pFunc call.
656 template <typename T>
657 static void retire( T * p, void (* pFunc)(T *) ); // inline in hp_impl.h
659 /// Retire pointer \p p with functor of type \p Disposer
661 The function places pointer \p p to array of pointers ready for removing.
662 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
664 Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
666 template <typename T>
668 void operator()( T * p ) ; // disposing operator
671 Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
672 - it should be stateless functor
673 - it should be default-constructible
674 - the result of functor call with argument \p p should not depend on where the functor will be called.
677 Operator \p delete functor:
679 template <typename T>
681 void operator ()( T * p ) {
686 // How to call GC::retire method
689 // ... use p in lock-free manner
691 cds::gc::HP::retire<disposer>( p ) ; // place p to retired pointer array of HP GC
694 Functor based on \p std::allocator :
696 template <typename ALLOC = std::allocator<int> >
698 template <typename T>
699 void operator()( T * p ) {
700 typedef typename ALLOC::templare rebind<T>::other alloc_t;
703 a.deallocate( p, 1 );
708 template <class Disposer, typename T>
709 static void retire( T * p ); // inline in hp_impl.h
711 /// Get current scan strategy
712 static scan_type getScanType()
714 return static_cast<scan_type>( hp::GarbageCollector::instance().getScanType());
717 /// Set current scan strategy
718 static void setScanType(
719 scan_type nScanType ///< new scan strategy
722 hp::GarbageCollector::instance().setScanType( static_cast<hp::scan_type>(nScanType) );
725 /// Checks if Hazard Pointer GC is constructed and may be used
728 return hp::GarbageCollector::isUsed();
731 /// Forced GC cycle call for current thread
733 Usually, this function should not be called directly.
735 static void scan() ; // inline in hp_impl.h
737 /// Synonym for \ref scan()
738 static void force_dispose()
743 }} // namespace cds::gc
745 #endif // #ifndef CDSLIB_GC_IMPL_HP_DECL_H