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
94 /// Dynamic Hazard Pointer guard
96 @headerfile cds/gc/dhp.h
98 A guard is the hazard pointer.
99 Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
101 A \p %Guard object is not copy- and move-constructible
102 and not copy- and move-assignable.
104 class Guard: public dhp::Guard
107 typedef dhp::Guard base_class;
112 Guard() CDS_NOEXCEPT; // inline in dhp_impl.h
115 Guard( Guard const& ) = delete;
116 Guard( Guard&& s ) = delete;
117 Guard& operator=(Guard const&) = delete;
118 Guard& operator=(Guard&&) = delete;
121 /// Protects a pointer of type <tt> atomic<T*> </tt>
123 Return the value of \p toGuard
125 The function tries to load \p toGuard and to store it
126 to the HP slot repeatedly until the guard's value equals \p toGuard
128 template <typename T>
129 T protect( atomics::atomic<T> const& toGuard ) CDS_NOEXCEPT
131 T pCur = toGuard.load(atomics::memory_order_relaxed);
134 pRet = assign( pCur );
135 pCur = toGuard.load(atomics::memory_order_acquire);
136 } while ( pRet != pCur );
140 /// Protects a converted pointer of type <tt> atomic<T*> </tt>
142 Return the value of \p toGuard
144 The function tries to load \p toGuard and to store result of \p f functor
145 to the HP slot repeatedly until the guard's value equals \p toGuard.
147 The function is useful for intrusive containers when \p toGuard is a node pointer
148 that should be converted to a pointer to the value type before guarding.
149 The parameter \p f of type Func is a functor that makes this conversion:
152 value_type * operator()( T * p );
155 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
157 template <typename T, class Func>
158 T protect( atomics::atomic<T> const& toGuard, Func f ) CDS_NOEXCEPT_( f( toGuard.load( atomics::memory_order_relaxed )))
160 T pCur = toGuard.load(atomics::memory_order_relaxed);
165 pCur = toGuard.load(atomics::memory_order_acquire);
166 } while ( pRet != pCur );
170 /// Store \p p to the guard
172 The function is just an assignment, no loop is performed.
173 Can be used for a pointer that cannot be changed concurrently
174 or for already guarded pointer.
176 template <typename T>
177 T * assign( T * p ) CDS_NOEXCEPT
179 return base_class::operator =(p);
183 std::nullptr_t assign( std::nullptr_t ) CDS_NOEXCEPT
185 return base_class::operator =(nullptr);
189 /// Store marked pointer \p p to the guard
191 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
192 Can be used for a marked pointer that cannot be changed concurrently
193 or for already guarded pointer.
195 template <typename T, int BITMASK>
196 T * assign( cds::details::marked_ptr<T, BITMASK> p ) CDS_NOEXCEPT
198 return base_class::operator =( p.ptr() );
201 /// Copy from \p src guard to \p this guard
202 void copy( Guard const& src ) CDS_NOEXCEPT
204 assign( src.get_native() );
207 /// Clears value of the guard
208 void clear() CDS_NOEXCEPT
213 /// Gets the value currently protected (relaxed read)
214 template <typename T>
215 T * get() const CDS_NOEXCEPT
217 return reinterpret_cast<T *>( get_native() );
220 /// Gets native guarded pointer stored
221 guarded_pointer get_native() const CDS_NOEXCEPT
223 return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed);
227 /// Array of Dynamic Hazard Pointer guards
229 @headerfile cds/gc/dhp.h
230 The class is intended for allocating an array of hazard pointer guards.
231 Template parameter \p Count defines the size of the array.
233 A \p %GuardArray object is not copy- and move-constructible
234 and not copy- and move-assignable.
236 template <size_t Count>
237 class GuardArray: public dhp::GuardArray<Count>
240 typedef dhp::GuardArray<Count> base_class;
243 /// Rebind array for other size \p OtherCount
244 template <size_t OtherCount>
246 typedef GuardArray<OtherCount> other ; ///< rebinding result
251 GuardArray() CDS_NOEXCEPT; // inline in dhp_impl.h
254 GuardArray( GuardArray const& ) = delete;
255 GuardArray( GuardArray&& ) = delete;
256 GuardArray& operator=(GuardArray const&) = delete;
257 GuardArray& operator-(GuardArray&&) = delete;
260 /// Protects a pointer of type \p atomic<T*>
262 Return the value of \p toGuard
264 The function tries to load \p toGuard and to store it
265 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
267 template <typename T>
268 T protect( size_t nIndex, atomics::atomic<T> const& toGuard ) CDS_NOEXCEPT
272 pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) );
273 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
278 /// Protects a pointer of type \p atomic<T*>
280 Return the value of \p toGuard
282 The function tries to load \p toGuard and to store it
283 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
285 The function is useful for intrusive containers when \p toGuard is a node pointer
286 that should be converted to a pointer to the value type before guarding.
287 The parameter \p f of type Func is a functor to make that conversion:
290 value_type * operator()( T * p );
293 Actually, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
295 template <typename T, class Func>
296 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f ) CDS_NOEXCEPT_( f( toGuard.load( atomics::memory_order_relaxed )))
300 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
301 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
306 /// Store \p p to the slot \p nIndex
308 The function is just an assignment, no loop is performed.
310 template <typename T>
311 T * assign( size_t nIndex, T * p ) CDS_NOEXCEPT
313 base_class::set(nIndex, p);
317 /// Store marked pointer \p p to the guard
319 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
320 Can be used for a marked pointer that cannot be changed concurrently
321 or for already guarded pointer.
323 template <typename T, int Bitmask>
324 T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p ) CDS_NOEXCEPT
326 return assign( nIndex, p.ptr() );
329 /// Copy guarded value from \p src guard to slot at index \p nIndex
330 void copy( size_t nIndex, Guard const& src ) CDS_NOEXCEPT
332 assign( nIndex, src.get_native() );
335 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
336 void copy( size_t nDestIndex, size_t nSrcIndex ) CDS_NOEXCEPT
338 assign( nDestIndex, get_native( nSrcIndex ));
341 /// Clear value of the slot \p nIndex
342 void clear( size_t nIndex ) CDS_NOEXCEPT
344 base_class::clear( nIndex );
347 /// Get current value of slot \p nIndex
348 template <typename T>
349 T * get( size_t nIndex ) const CDS_NOEXCEPT
351 return reinterpret_cast<T *>( get_native( nIndex ) );
354 /// Get native guarded pointer stored
355 guarded_pointer get_native( size_t nIndex ) const CDS_NOEXCEPT
357 return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed);
360 /// Capacity of the guard array
361 static CDS_CONSTEXPR size_t capacity() CDS_NOEXCEPT
368 /// Initializes dhp::GarbageCollector singleton
370 The constructor calls GarbageCollector::Construct with passed parameters.
371 See dhp::GarbageCollector::Construct for explanation of parameters meaning.
374 size_t nLiberateThreshold = 1024
375 , size_t nInitialThreadGuardCount = 8
378 dhp::GarbageCollector::Construct(
380 nInitialThreadGuardCount
384 /// Terminates dhp::GarbageCollector singleton
386 The destructor calls \code dhp::GarbageCollector::Destruct() \endcode
390 dhp::GarbageCollector::Destruct();
393 /// Checks if count of hazard pointer is no less than \p nCountNeeded
395 The function always returns \p true since the guard count is unlimited for
396 DHP garbage collector.
398 static CDS_CONSTEXPR bool check_available_guards( size_t nCountNeeded, bool /*bRaiseException*/ = true )
400 CDS_UNUSED( nCountNeeded );
404 /// Retire pointer \p p with function \p pFunc
406 The function places pointer \p p to array of pointers ready for removing.
407 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
408 Deleting the pointer is the function \p pFunc call.
410 template <typename T>
411 static void retire( T * p, void (* pFunc)(T *) )
413 dhp::GarbageCollector::instance().retirePtr( p, pFunc );
416 /// Retire pointer \p p with functor of type \p Disposer
418 The function places pointer \p p to array of pointers ready for removing.
419 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
421 See gc::HP::retire for \p Disposer requirements.
423 template <class Disposer, typename T>
424 static void retire( T * p )
426 retire( p, cds::details::static_functor<Disposer, T>::call );
429 /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
432 return dhp::GarbageCollector::isUsed();
435 /// Forced GC cycle call for current thread
437 Usually, this function should not be called directly.
439 static void scan() ; // inline in dhp_impl.h
441 /// Synonym for \ref scan()
442 static void force_dispose()
448 }} // namespace cds::gc
450 #endif // #ifndef __CDS_GC_IMPL_DHP_DECL_H