3 #ifndef __CDS_GC_IMPL_DHP_DECL_H
4 #define __CDS_GC_IMPL_DHP_DECL_H
6 #include <cds/gc/details/dhp.h>
7 #include <cds/details/marked_ptr.h>
8 #include <cds/details/static_functor.h>
10 namespace cds { namespace gc {
12 /// Dynamic Hazard Pointer garbage collector
13 /** @ingroup cds_garbage_collector
14 @headerfile cds/gc/dhp.h
16 Implementation of Dynamic Hazard Pointer garbage collector.
19 - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
20 - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
21 - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
23 Dynamic Hazard Pointers SMR (safe memory reclamation) provides an unbounded number of hazard pointer per thread
24 despite of classic Hazard Pointer SMR in which the count of the hazard pointef per thread is limited.
26 See \ref cds_how_to_use "How to use" section for details how to apply garbage collector.
31 /// Native guarded pointer type
33 @headerfile cds/gc/dhp.h
35 typedef void * guarded_pointer;
39 @headerfile cds/gc/dhp.h
41 template <typename T> using atomic_ref = atomics::atomic<T *>;
45 @headerfile cds/gc/dhp.h
47 template <typename T> using atomic_type = atomics::atomic<T>;
49 /// Atomic marked pointer
51 @headerfile cds/gc/dhp.h
53 template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
55 /// Thread GC implementation for internal usage
57 @headerfile cds/gc/dhp.h
59 typedef dhp::ThreadGC thread_gc_impl;
61 /// Thread-level garbage collector
63 @headerfile cds/gc/dhp.h
64 This class performs automatically attaching/detaching Dynamic Hazard Pointer GC
65 for the current thread.
67 class thread_gc: public thread_gc_impl
75 The constructor attaches the current thread to the Dynamic Hazard Pointer GC
76 if it is not yet attached.
77 The \p bPersistent parameter specifies attachment persistence:
78 - \p true - the class destructor will not detach the thread from Dynamic Hazard Pointer GC.
79 - \p false (default) - the class destructor will detach the thread from Dynamic Hazard Pointer GC.
82 bool bPersistent = false
83 ) ; // inline in dhp_impl.h
87 If the object has been created in persistent mode, the destructor does nothing.
88 Otherwise it detaches the current thread from Dynamic Hazard Pointer GC.
90 ~thread_gc() ; // inline in dhp_impl.h
92 public: // for internal use only!!!
94 static void alloc_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h
95 static void free_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h
100 /// Dynamic Hazard Pointer guard
102 @headerfile cds/gc/dhp.h
104 A guard is the hazard pointer.
105 Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
107 A \p %Guard object is not copy- and move-constructible
108 and not copy- and move-assignable.
110 class Guard: public dhp::Guard
113 typedef dhp::Guard base_class;
116 public: // for internal use only
118 typedef cds::gc::dhp::details::guard native_guard;
127 Guard( Guard const& ) = delete;
128 Guard( Guard&& s ) = delete;
129 Guard& operator=(Guard const&) = delete;
130 Guard& operator=(Guard&&) = delete;
133 /// Protects a pointer of type <tt> atomic<T*> </tt>
135 Return the value of \p toGuard
137 The function tries to load \p toGuard and to store it
138 to the HP slot repeatedly until the guard's value equals \p toGuard
140 template <typename T>
141 T protect( atomics::atomic<T> const& toGuard )
143 T pCur = toGuard.load(atomics::memory_order_relaxed);
146 pRet = assign( pCur );
147 pCur = toGuard.load(atomics::memory_order_acquire);
148 } while ( pRet != pCur );
152 /// Protects a converted pointer of type <tt> atomic<T*> </tt>
154 Return the value of \p toGuard
156 The function tries to load \p toGuard and to store result of \p f functor
157 to the HP slot repeatedly until the guard's value equals \p toGuard.
159 The function is useful for intrusive containers when \p toGuard is a node pointer
160 that should be converted to a pointer to the value type before guarding.
161 The parameter \p f of type Func is a functor that makes this conversion:
164 value_type * operator()( T * p );
167 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
169 template <typename T, class Func>
170 T protect( atomics::atomic<T> const& toGuard, Func f )
172 T pCur = toGuard.load(atomics::memory_order_relaxed);
177 pCur = toGuard.load(atomics::memory_order_acquire);
178 } while ( pRet != pCur );
182 /// Store \p p to the guard
184 The function is just an assignment, no loop is performed.
185 Can be used for a pointer that cannot be changed concurrently
186 or for already guarded pointer.
188 template <typename T>
191 return base_class::operator =(p);
195 std::nullptr_t assign( std::nullptr_t )
197 return base_class::operator =(nullptr);
201 /// Store marked pointer \p p to the guard
203 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
204 Can be used for a marked pointer that cannot be changed concurrently
205 or for already guarded pointer.
207 template <typename T, int BITMASK>
208 T * assign( cds::details::marked_ptr<T, BITMASK> p )
210 return base_class::operator =( p.ptr() );
213 /// Copy from \p src guard to \p this guard
214 void copy( Guard const& src )
216 assign( src.get_native() );
219 /// Clears value of the guard
225 /// Gets the value currently protected (relaxed read)
226 template <typename T>
229 return reinterpret_cast<T *>( get_native() );
232 /// Gets native guarded pointer stored
233 guarded_pointer get_native() const
235 return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed);
239 /// Array of Dynamic Hazard Pointer guards
241 @headerfile cds/gc/dhp.h
242 The class is intended for allocating an array of hazard pointer guards.
243 Template parameter \p Count defines the size of the array.
245 A \p %GuardArray object is not copy- and move-constructible
246 and not copy- and move-assignable.
248 template <size_t Count>
249 class GuardArray: public dhp::GuardArray<Count>
252 typedef dhp::GuardArray<Count> base_class;
255 /// Rebind array for other size \p OtherCount
256 template <size_t OtherCount>
258 typedef GuardArray<OtherCount> other ; ///< rebinding result
267 GuardArray( GuardArray const& ) = delete;
268 GuardArray( GuardArray&& ) = delete;
269 GuardArray& operator=(GuardArray const&) = delete;
270 GuardArray& operator-(GuardArray&&) = delete;
273 /// Protects a pointer of type \p atomic<T*>
275 Return the value of \p toGuard
277 The function tries to load \p toGuard and to store it
278 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
280 template <typename T>
281 T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
285 pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) );
286 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
291 /// Protects a pointer of type \p atomic<T*>
293 Return the value of \p toGuard
295 The function tries to load \p toGuard and to store it
296 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
298 The function is useful for intrusive containers when \p toGuard is a node pointer
299 that should be converted to a pointer to the value type before guarding.
300 The parameter \p f of type Func is a functor to make that conversion:
303 value_type * operator()( T * p );
306 Actually, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
308 template <typename T, class Func>
309 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
313 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
314 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
319 /// Store \p p to the slot \p nIndex
321 The function is just an assignment, no loop is performed.
323 template <typename T>
324 T * assign( size_t nIndex, T * p )
326 base_class::set(nIndex, p);
330 /// Store marked pointer \p p to the guard
332 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
333 Can be used for a marked pointer that cannot be changed concurrently
334 or for already guarded pointer.
336 template <typename T, int Bitmask>
337 T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
339 return assign( nIndex, p.ptr() );
342 /// Copy guarded value from \p src guard to slot at index \p nIndex
343 void copy( size_t nIndex, Guard const& src )
345 assign( nIndex, src.get_native() );
348 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
349 void copy( size_t nDestIndex, size_t nSrcIndex )
351 assign( nDestIndex, get_native( nSrcIndex ));
354 /// Clear value of the slot \p nIndex
355 void clear( size_t nIndex )
357 base_class::clear( nIndex );
360 /// Get current value of slot \p nIndex
361 template <typename T>
362 T * get( size_t nIndex ) const
364 return reinterpret_cast<T *>( get_native( nIndex ) );
367 /// Get native guarded pointer stored
368 guarded_pointer get_native( size_t nIndex ) const
370 return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed);
373 /// Capacity of the guard array
374 static CDS_CONSTEXPR size_t capacity()
382 A guarded pointer is a pair of a pointer and GC's guard.
383 Usually, it is used for returning a pointer to the item from an lock-free container.
384 The guard prevents the pointer to be early disposed (freed) by GC.
385 After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
388 - \p GuardedType - a type which the guard stores
389 - \p ValueType - a value type
390 - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
392 For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
393 In such case the \p %guarded_ptr is:
395 typedef cds::gc::DHP::guarded_ptr< foo > intrusive_guarded_ptr;
398 For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
406 struct value_accessor {
407 std::string* operator()( foo* pFoo ) const
409 return &(pFoo->value);
414 typedef cds::gc::DHP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
417 You don't need use this class directly.
418 All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
420 template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
424 struct trivial_cast {
425 ValueType * operator()( GuardedType * p ) const
433 typedef GuardedType guarded_type; ///< Guarded type
434 typedef ValueType value_type; ///< Value type
436 /// Functor for casting \p guarded_type to \p value_type
437 typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
440 typedef cds::gc::dhp::details::guard native_guard;
445 native_guard m_guard;
449 /// Creates empty guarded pointer
450 guarded_ptr() CDS_NOEXCEPT
454 /// Initializes guarded pointer with \p p
455 explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
458 assert( m_guard.is_initialized() );
461 explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
466 guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
468 m_guard.set_guard( gp.m_guard.release_guard() );
471 /// The guarded pointer is not copy-constructible
472 guarded_ptr( guarded_ptr const& gp ) = delete;
474 /// Clears the guarded pointer
476 \ref release is called if guarded pointer is not \ref empty
478 ~guarded_ptr() CDS_NOEXCEPT
483 /// Move-assignment operator
484 guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
487 m_guard.set_guard( gp.m_guard.release_guard() );
491 /// The guarded pointer is not copy-assignable
492 guarded_ptr& operator=(guarded_ptr const& gp) = delete;
494 /// Returns a pointer to guarded value
495 value_type * operator ->() const CDS_NOEXCEPT
498 return value_cast()( reinterpret_cast<guarded_type *>(m_guard.get()));
501 /// Returns a reference to guarded value
502 value_type& operator *() CDS_NOEXCEPT
505 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard.get()));
508 /// Returns const reference to guarded value
509 value_type const& operator *() const CDS_NOEXCEPT
512 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard.get()));
515 /// Checks if the guarded pointer is \p nullptr
516 bool empty() const CDS_NOEXCEPT
518 return !m_guard.is_initialized() || m_guard.get( atomics::memory_order_relaxed ) == nullptr;
521 /// \p bool operator returns <tt>!empty()</tt>
522 explicit operator bool() const CDS_NOEXCEPT
527 /// Clears guarded pointer
529 If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
530 Dereferncing the guarded pointer after \p release() is dangerous.
532 void release() CDS_NOEXCEPT
538 // For internal use only!!!
539 native_guard& guard() CDS_NOEXCEPT
542 assert( m_guard.is_initialized() );
551 if ( !m_guard.is_initialized() )
552 thread_gc::alloc_guard( m_guard );
557 if ( m_guard.is_initialized() )
558 thread_gc::free_guard( m_guard );
564 /// Initializes dhp::GarbageCollector singleton
566 The constructor calls GarbageCollector::Construct with passed parameters.
567 See dhp::GarbageCollector::Construct for explanation of parameters meaning.
570 size_t nLiberateThreshold = 1024
571 , size_t nInitialThreadGuardCount = 8
574 dhp::GarbageCollector::Construct(
576 nInitialThreadGuardCount
580 /// Terminates dhp::GarbageCollector singleton
582 The destructor calls \code dhp::GarbageCollector::Destruct() \endcode
586 dhp::GarbageCollector::Destruct();
589 /// Checks if count of hazard pointer is no less than \p nCountNeeded
591 The function always returns \p true since the guard count is unlimited for
592 \p gc::DHP garbage collector.
594 static CDS_CONSTEXPR bool check_available_guards(
595 #ifdef CDS_DOXYGEN_INVOKED
600 bool /*bRaiseException*/ = true )
605 /// Retire pointer \p p with function \p pFunc
607 The function places pointer \p p to array of pointers ready for removing.
608 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
609 Deleting the pointer is the function \p pFunc call.
611 template <typename T>
612 static void retire( T * p, void (* pFunc)(T *) )
614 dhp::GarbageCollector::instance().retirePtr( p, pFunc );
617 /// Retire pointer \p p with functor of type \p Disposer
619 The function places pointer \p p to array of pointers ready for removing.
620 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
622 See gc::HP::retire for \p Disposer requirements.
624 template <class Disposer, typename T>
625 static void retire( T * p )
627 retire( p, cds::details::static_functor<Disposer, T>::call );
630 /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
633 return dhp::GarbageCollector::isUsed();
636 /// Forced GC cycle call for current thread
638 Usually, this function should not be called directly.
640 static void scan() ; // inline in dhp_impl.h
642 /// Synonym for \ref scan()
643 static void force_dispose()
649 }} // namespace cds::gc
651 #endif // #ifndef __CDS_GC_IMPL_DHP_DECL_H