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;
123 Guard(); // inline in dhp_impl.h
126 Guard( Guard const& ) = delete;
127 Guard( Guard&& s ) = delete;
128 Guard& operator=(Guard const&) = delete;
129 Guard& operator=(Guard&&) = delete;
132 /// Protects a pointer of type <tt> atomic<T*> </tt>
134 Return the value of \p toGuard
136 The function tries to load \p toGuard and to store it
137 to the HP slot repeatedly until the guard's value equals \p toGuard
139 template <typename T>
140 T protect( atomics::atomic<T> const& toGuard )
142 T pCur = toGuard.load(atomics::memory_order_relaxed);
145 pRet = assign( pCur );
146 pCur = toGuard.load(atomics::memory_order_acquire);
147 } while ( pRet != pCur );
151 /// Protects a converted pointer of type <tt> atomic<T*> </tt>
153 Return the value of \p toGuard
155 The function tries to load \p toGuard and to store result of \p f functor
156 to the HP slot repeatedly until the guard's value equals \p toGuard.
158 The function is useful for intrusive containers when \p toGuard is a node pointer
159 that should be converted to a pointer to the value type before guarding.
160 The parameter \p f of type Func is a functor that makes this conversion:
163 value_type * operator()( T * p );
166 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
168 template <typename T, class Func>
169 T protect( atomics::atomic<T> const& toGuard, Func f )
171 T pCur = toGuard.load(atomics::memory_order_relaxed);
176 pCur = toGuard.load(atomics::memory_order_acquire);
177 } while ( pRet != pCur );
181 /// Store \p p to the guard
183 The function is just an assignment, no loop is performed.
184 Can be used for a pointer that cannot be changed concurrently
185 or for already guarded pointer.
187 template <typename T>
190 return base_class::operator =(p);
194 std::nullptr_t assign( std::nullptr_t )
196 return base_class::operator =(nullptr);
200 /// Store marked pointer \p p to the guard
202 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
203 Can be used for a marked pointer that cannot be changed concurrently
204 or for already guarded pointer.
206 template <typename T, int BITMASK>
207 T * assign( cds::details::marked_ptr<T, BITMASK> p )
209 return base_class::operator =( p.ptr() );
212 /// Copy from \p src guard to \p this guard
213 void copy( Guard const& src )
215 assign( src.get_native() );
218 /// Clears value of the guard
224 /// Gets the value currently protected (relaxed read)
225 template <typename T>
228 return reinterpret_cast<T *>( get_native() );
231 /// Gets native guarded pointer stored
232 guarded_pointer get_native() const
234 return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed);
238 /// Array of Dynamic Hazard Pointer guards
240 @headerfile cds/gc/dhp.h
241 The class is intended for allocating an array of hazard pointer guards.
242 Template parameter \p Count defines the size of the array.
244 A \p %GuardArray object is not copy- and move-constructible
245 and not copy- and move-assignable.
247 template <size_t Count>
248 class GuardArray: public dhp::GuardArray<Count>
251 typedef dhp::GuardArray<Count> base_class;
254 /// Rebind array for other size \p OtherCount
255 template <size_t OtherCount>
257 typedef GuardArray<OtherCount> other ; ///< rebinding result
262 GuardArray(); // inline in dhp_impl.h
265 GuardArray( GuardArray const& ) = delete;
266 GuardArray( GuardArray&& ) = delete;
267 GuardArray& operator=(GuardArray const&) = delete;
268 GuardArray& operator-(GuardArray&&) = delete;
271 /// Protects a pointer of type \p atomic<T*>
273 Return the value of \p toGuard
275 The function tries to load \p toGuard and to store it
276 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
278 template <typename T>
279 T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
283 pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) );
284 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
289 /// Protects a pointer of type \p atomic<T*>
291 Return the value of \p toGuard
293 The function tries to load \p toGuard and to store it
294 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
296 The function is useful for intrusive containers when \p toGuard is a node pointer
297 that should be converted to a pointer to the value type before guarding.
298 The parameter \p f of type Func is a functor to make that conversion:
301 value_type * operator()( T * p );
304 Actually, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
306 template <typename T, class Func>
307 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
311 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
312 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
317 /// Store \p p to the slot \p nIndex
319 The function is just an assignment, no loop is performed.
321 template <typename T>
322 T * assign( size_t nIndex, T * p )
324 base_class::set(nIndex, p);
328 /// Store marked pointer \p p to the guard
330 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
331 Can be used for a marked pointer that cannot be changed concurrently
332 or for already guarded pointer.
334 template <typename T, int Bitmask>
335 T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
337 return assign( nIndex, p.ptr() );
340 /// Copy guarded value from \p src guard to slot at index \p nIndex
341 void copy( size_t nIndex, Guard const& src )
343 assign( nIndex, src.get_native() );
346 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
347 void copy( size_t nDestIndex, size_t nSrcIndex )
349 assign( nDestIndex, get_native( nSrcIndex ));
352 /// Clear value of the slot \p nIndex
353 void clear( size_t nIndex )
355 base_class::clear( nIndex );
358 /// Get current value of slot \p nIndex
359 template <typename T>
360 T * get( size_t nIndex ) const
362 return reinterpret_cast<T *>( get_native( nIndex ) );
365 /// Get native guarded pointer stored
366 guarded_pointer get_native( size_t nIndex ) const
368 return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed);
371 /// Capacity of the guard array
372 static CDS_CONSTEXPR size_t capacity()
380 A guarded pointer is a pair of a pointer and GC's guard.
381 Usually, it is used for returning a pointer to the item from an lock-free container.
382 The guard prevents the pointer to be early disposed (freed) by GC.
383 After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
386 - \p GuardedType - a type which the guard stores
387 - \p ValueType - a value type
388 - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
390 For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
391 In such case the \p %guarded_ptr is:
393 typedef cds::gc::DHP::guarded_ptr< foo > intrusive_guarded_ptr;
396 For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
404 struct value_accessor {
405 std::string* operator()( foo* pFoo ) const
407 return &(pFoo->value);
412 typedef cds::gc::DHP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
415 You don't need use this class directly.
416 All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
418 template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
422 struct trivial_cast {
423 ValueType * operator()( GuardedType * p ) const
431 typedef GuardedType guarded_type; ///< Guarded type
432 typedef ValueType value_type; ///< Value type
434 /// Functor for casting \p guarded_type to \p value_type
435 typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
438 typedef cds::gc::dhp::details::guard native_guard;
443 native_guard m_guard;
447 /// Creates empty guarded pointer
448 guarded_ptr() CDS_NOEXCEPT
452 /// Initializes guarded pointer with \p p
453 explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
456 assert( m_guard.is_initialized() );
459 explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
464 guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
466 m_guard.set_guard( gp.m_guard.release_guard() );
469 /// The guarded pointer is not copy-constructible
470 guarded_ptr( guarded_ptr const& gp ) = delete;
472 /// Clears the guarded pointer
474 \ref release is called if guarded pointer is not \ref empty
476 ~guarded_ptr() CDS_NOEXCEPT
481 /// Move-assignment operator
482 guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
485 m_guard.set_guard( gp.m_guard.release_guard() );
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_guard.get()));
499 /// Returns a reference to guarded value
500 value_type& operator *() CDS_NOEXCEPT
503 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard.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_guard.get()));
513 /// Checks if the guarded pointer is \p nullptr
514 bool empty() const CDS_NOEXCEPT
516 return !m_guard.is_initialized() || m_guard.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
540 assert( m_guard.is_initialized() );
549 if ( !m_guard.is_initialized() )
550 thread_gc::alloc_guard( m_guard );
555 if ( m_guard.is_initialized() )
556 thread_gc::free_guard( m_guard );
562 /// Initializes dhp::GarbageCollector singleton
564 The constructor calls GarbageCollector::Construct with passed parameters.
565 See dhp::GarbageCollector::Construct for explanation of parameters meaning.
568 size_t nLiberateThreshold = 1024
569 , size_t nInitialThreadGuardCount = 8
572 dhp::GarbageCollector::Construct(
574 nInitialThreadGuardCount
578 /// Terminates dhp::GarbageCollector singleton
580 The destructor calls \code dhp::GarbageCollector::Destruct() \endcode
584 dhp::GarbageCollector::Destruct();
587 /// Checks if count of hazard pointer is no less than \p nCountNeeded
589 The function always returns \p true since the guard count is unlimited for
590 \p gc::DHP garbage collector.
592 static CDS_CONSTEXPR bool check_available_guards(
593 #ifdef CDS_DOXYGEN_INVOKED
598 bool /*bRaiseException*/ = true )
603 /// Retire pointer \p p with function \p pFunc
605 The function places pointer \p p to array of pointers ready for removing.
606 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
607 Deleting the pointer is the function \p pFunc call.
609 template <typename T>
610 static void retire( T * p, void (* pFunc)(T *) )
612 dhp::GarbageCollector::instance().retirePtr( p, pFunc );
615 /// Retire pointer \p p with functor of type \p Disposer
617 The function places pointer \p p to array of pointers ready for removing.
618 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
620 See gc::HP::retire for \p Disposer requirements.
622 template <class Disposer, typename T>
623 static void retire( T * p )
625 retire( p, cds::details::static_functor<Disposer, T>::call );
628 /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
631 return dhp::GarbageCollector::isUsed();
634 /// Forced GC cycle call for current thread
636 Usually, this function should not be called directly.
638 static void scan() ; // inline in dhp_impl.h
640 /// Synonym for \ref scan()
641 static void force_dispose()
647 }} // namespace cds::gc
649 #endif // #ifndef __CDS_GC_IMPL_DHP_DECL_H