3 #ifndef __CDS_GC_HP_DECL_H
4 #define __CDS_GC_HP_DECL_H
6 #include <cds/gc/hzp/hzp.h>
7 #include <cds/details/marked_ptr.h>
9 namespace cds { namespace gc {
10 /// @defgroup cds_garbage_collector Garbage collectors
12 /// Hazard Pointer garbage collector
13 /** @ingroup cds_garbage_collector
14 @headerfile cds/gc/hp.h
16 This class realizes a wrapper for Hazard Pointer garbage collector internal implementation.
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 See \ref cds_how_to_use "How to use" section for details of garbage collector applying.
28 /// Native guarded pointer type
29 typedef gc::hzp::hazard_pointer guarded_pointer;
33 @headerfile cds/gc/hp.h
35 template <typename T> using atomic_ref = atomics::atomic<T *>;
37 /// Atomic marked pointer
39 @headerfile cds/gc/hp.h
41 template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
45 @headerfile cds/gc/hp.h
47 template <typename T> using atomic_type = atomics::atomic<T>;
49 /// Thread GC implementation for internal usage
50 typedef hzp::ThreadGC thread_gc_impl;
52 /// Wrapper for hzp::ThreadGC class
54 @headerfile cds/gc/hp.h
55 This class performs automatically attaching/detaching Hazard Pointer GC
56 for the current thread.
58 class thread_gc: public thread_gc_impl
67 The constructor attaches the current thread to the Hazard Pointer GC
68 if it is not yet attached.
69 The \p bPersistent parameter specifies attachment persistence:
70 - \p true - the class destructor will not detach the thread from Hazard Pointer GC.
71 - \p false (default) - the class destructor will detach the thread from Hazard Pointer GC.
74 bool bPersistent = false
75 ) ; //inline in hp_impl.h
79 If the object has been created in persistent mode, the destructor does nothing.
80 Otherwise it detaches the current thread from Hazard Pointer GC.
82 ~thread_gc() ; // inline in hp_impl.h
85 /// Base for container node
87 @headerfile cds/gc/hp.h
88 This struct is empty for Hazard Pointer GC
93 /// Hazard Pointer guard
95 @headerfile cds/gc/hp.h
96 This class is a wrapper for hzp::AutoHPGuard.
98 class Guard: public hzp::AutoHPGuard
101 typedef hzp::AutoHPGuard base_class;
106 Guard() ; // inline in hp_impl.h
109 /// Protects a pointer of type \p atomic<T*>
111 Return the value of \p toGuard
113 The function tries to load \p toGuard and to store it
114 to the HP slot repeatedly until the guard's value equals \p toGuard
116 template <typename T>
117 T protect( atomics::atomic<T> const& toGuard )
119 T pCur = toGuard.load(atomics::memory_order_relaxed);
122 pRet = assign( pCur );
123 pCur = toGuard.load(atomics::memory_order_acquire);
124 } while ( pRet != pCur );
128 /// Protects a converted pointer of type \p atomic<T*>
130 Return the value of \p toGuard
132 The function tries to load \p toGuard and to store result of \p f functor
133 to the HP slot repeatedly until the guard's value equals \p toGuard.
135 The function is useful for intrusive containers when \p toGuard is a node pointer
136 that should be converted to a pointer to the value type before protecting.
137 The parameter \p f of type Func is a functor that makes this conversion:
140 value_type * operator()( T * p );
143 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
145 template <typename T, class Func>
146 T protect( atomics::atomic<T> const& toGuard, Func f )
148 T pCur = toGuard.load(atomics::memory_order_relaxed);
153 pCur = toGuard.load(atomics::memory_order_acquire);
154 } while ( pRet != pCur );
158 /// Store \p p to the guard
160 The function equals to a simple assignment the value \p p to guard, no loop is performed.
161 Can be used for a pointer that cannot be changed concurrently
163 template <typename T>
166 return base_class::operator =(p);
170 std::nullptr_t assign( std::nullptr_t )
172 return base_class::operator =(nullptr);
176 /// Copy from \p src guard to \p this guard
177 void copy( Guard const& src )
179 assign( src.get_native() );
182 /// Store marked pointer \p p to the guard
184 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
185 Can be used for a marked pointer that cannot be changed concurrently.
187 template <typename T, int BITMASK>
188 T * assign( cds::details::marked_ptr<T, BITMASK> p )
190 return base_class::operator =( p.ptr() );
193 /// Clear value of the guard
199 /// Get the value currently protected
200 template <typename T>
203 return reinterpret_cast<T *>( get_native() );
206 /// Get native hazard pointer stored
207 guarded_pointer get_native() const
209 return base_class::get();
213 /// Array of Hazard Pointer guards
215 @headerfile cds/gc/hp.h
216 This class is a wrapper for hzp::AutoHPArray template.
217 Template parameter \p Count defines the size of HP array.
219 template <size_t Count>
220 class GuardArray: public hzp::AutoHPArray<Count>
223 typedef hzp::AutoHPArray<Count> base_class;
226 /// Rebind array for other size \p Count2
227 template <size_t Count2>
229 typedef GuardArray<Count2> other ; ///< rebinding result
234 GuardArray() ; // inline in hp_impl.h
236 /// Protects a pointer of type \p atomic<T*>
238 Return the value of \p toGuard
240 The function tries to load \p toGuard and to store it
241 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
243 template <typename T>
244 T protect(size_t nIndex, atomics::atomic<T> const& toGuard )
248 pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire) );
249 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
254 /// Protects a pointer of type \p atomic<T*>
256 Return the value of \p toGuard
258 The function tries to load \p toGuard and to store it
259 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
261 The function is useful for intrusive containers when \p toGuard is a node pointer
262 that should be converted to a pointer to the value type before guarding.
263 The parameter \p f of type Func is a functor that makes this conversion:
266 value_type * operator()( T * p );
269 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
271 template <typename T, class Func>
272 T protect(size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
276 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire) ));
277 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
282 /// Store \p to the slot \p nIndex
284 The function equals to a simple assignment, no loop is performed.
286 template <typename T>
287 T * assign( size_t nIndex, T * p )
289 base_class::set(nIndex, p);
293 /// Store marked pointer \p p to the guard
295 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
296 Can be used for a marked pointer that cannot be changed concurrently.
298 template <typename T, int BITMASK>
299 T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p )
301 return assign( nIndex, p.ptr() );
304 /// Copy guarded value from \p src guard to slot at index \p nIndex
305 void copy( size_t nIndex, Guard const& src )
307 assign( nIndex, src.get_native() );
310 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
311 void copy( size_t nDestIndex, size_t nSrcIndex )
313 assign( nDestIndex, get_native( nSrcIndex ));
316 /// Clear value of the slot \p nIndex
317 void clear( size_t nIndex)
319 base_class::clear( nIndex );
322 /// Get current value of slot \p nIndex
323 template <typename T>
324 T * get( size_t nIndex) const
326 return reinterpret_cast<T *>( get_native( nIndex ) );
329 /// Get native hazard pointer stored
330 guarded_pointer get_native( size_t nIndex ) const
332 return base_class::operator[](nIndex).get();
335 /// Capacity of the guard array
336 static CDS_CONSTEXPR size_t capacity()
343 /// Initializes hzp::GarbageCollector singleton
345 The constructor initializes GC singleton with passed parameters.
346 If GC instance is not exist then the function creates the instance.
347 Otherwise it does nothing.
349 The Michael's HP reclamation schema depends of three parameters:
350 - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
351 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
352 uses maximum of the hazard pointer count for CDS library.
353 - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
354 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
355 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
358 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
359 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
360 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
361 hzp::scan_type nScanType = hzp::inplace ///< Scan type (see \ref hzp::scan_type enum)
364 hzp::GarbageCollector::Construct(
372 /// Terminates GC singleton
374 The destructor calls \code hzp::GarbageCollector::Destruct( true ) \endcode
378 hzp::GarbageCollector::Destruct( true );
381 /// Checks if count of hazard pointer is no less than \p nCountNeeded
383 If \p bRaiseException is \p true (that is the default), the function raises an exception gc::too_few_hazard_pointers
384 if \p nCountNeeded is more than the count of hazard pointer per thread.
386 static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
388 if ( hzp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
389 if ( bRaiseException )
390 throw cds::gc::too_few_hazard_pointers();
396 /// Returns max Hazard Pointer count
397 size_t max_hazard_count() const
399 return hzp::GarbageCollector::instance().getHazardPointerCount();
402 /// Returns max count of thread
403 size_t max_thread_count() const
405 return hzp::GarbageCollector::instance().getMaxThreadCount();
408 /// Returns capacity of retired pointer array
409 size_t retired_array_capacity() const
411 return hzp::GarbageCollector::instance().getMaxRetiredPtrCount();
414 /// Retire pointer \p p with function \p pFunc
416 The function places pointer \p p to array of pointers ready for removing.
417 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
418 Deleting the pointer is the function \p pFunc call.
420 template <typename T>
421 static void retire( T * p, void (* pFunc)(T *) ) ; // inline in hp_impl.h
423 /// Retire pointer \p p with functor of type \p Disposer
425 The function places pointer \p p to array of pointers ready for removing.
426 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
428 Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
430 template <typename T>
432 void operator()( T * p ) ; // disposing operator
435 Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
436 - it should be stateless functor
437 - it should be default-constructible
438 - the result of functor call with argument \p p should not depend on where the functor will be called.
441 Operator \p delete functor:
443 template <typename T>
445 void operator ()( T * p ) {
450 // How to call GC::retire method
453 // ... use p in lock-free manner
455 cds::gc::HP::retire<disposer>( p ) ; // place p to retired pointer array of HP GC
458 Functor based on \p std::allocator :
460 template <typename ALLOC = std::allocator<int> >
462 template <typename T>
463 void operator()( T * p ) {
464 typedef typename ALLOC::templare rebind<T>::other alloc_t;
467 a.deallocate( p, 1 );
472 template <class Disposer, typename T>
473 static void retire( T * p ) ; // inline in hp_impl.h
475 /// Get current scan strategy
476 /**@anchor hrc_gc_HP_getScanType
477 See hzp::GarbageCollector::Scan for scan algo description
479 hzp::scan_type getScanType() const
481 return hzp::GarbageCollector::instance().getScanType();
484 /// Set current scan strategy
486 Scan strategy changing is allowed on the fly.
488 About scan strategy see \ref hrc_gc_HP_getScanType "getScanType"
491 hzp::scan_type nScanType ///< new scan strategy
494 hzp::GarbageCollector::instance().setScanType( nScanType );
497 /// Checks if Hazard Pointer GC is constructed and may be used
500 return hzp::GarbageCollector::isUsed();
504 /// Forced GC cycle call for current thread
506 Usually, this function should not be called directly.
508 static void scan() ; // inline in hp_impl.h
510 /// Synonym for \ref scan()
511 static void force_dispose()
516 }} // namespace cds::gc
518 #endif // #ifndef __CDS_GC_HP_DECL_H