3 #ifndef __CDS_GC_HP_HP_DECL_H
4 #define __CDS_GC_HP_HP_DECL_H
6 #include <stdexcept> // overflow_error
7 #include <cds/gc/hp/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 This class realizes a wrapper for Hazard Pointer garbage collector internal implementation.
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 See \ref cds_how_to_use "How to use" section for details of garbage collector applying.
29 /// Native guarded pointer type
30 typedef gc::hzp::hazard_pointer guarded_pointer;
34 @headerfile cds/gc/hp.h
36 template <typename T> using atomic_ref = atomics::atomic<T *>;
38 /// Atomic marked pointer
40 @headerfile cds/gc/hp.h
42 template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
46 @headerfile cds/gc/hp.h
48 template <typename T> using atomic_type = atomics::atomic<T>;
50 /// Thread GC implementation for internal usage
51 typedef hzp::ThreadGC thread_gc_impl;
53 /// Wrapper for hzp::ThreadGC class
55 @headerfile cds/gc/hp.h
56 This class performs automatically attaching/detaching Hazard Pointer GC
57 for the current thread.
59 class thread_gc: public thread_gc_impl
68 The constructor attaches the current thread to the Hazard Pointer GC
69 if it is not yet attached.
70 The \p bPersistent parameter specifies attachment persistence:
71 - \p true - the class destructor will not detach the thread from Hazard Pointer GC.
72 - \p false (default) - the class destructor will detach the thread from Hazard Pointer GC.
75 bool bPersistent = false
76 ) ; //inline in hp_impl.h
80 If the object has been created in persistent mode, the destructor does nothing.
81 Otherwise it detaches the current thread from Hazard Pointer GC.
83 ~thread_gc() ; // inline in hp_impl.h
86 /// Hazard Pointer guard
88 @headerfile cds/gc/hp.h
89 This class is a wrapper for hzp::AutoHPGuard.
91 class Guard: public hzp::AutoHPGuard
94 typedef hzp::AutoHPGuard base_class;
99 Guard() ; // inline in hp_impl.h
102 /// Protects a pointer of type \p atomic<T*>
104 Return the value of \p toGuard
106 The function tries to load \p toGuard and to store it
107 to the HP slot repeatedly until the guard's value equals \p toGuard
109 template <typename T>
110 T protect( atomics::atomic<T> const& toGuard )
112 T pCur = toGuard.load(atomics::memory_order_relaxed);
115 pRet = assign( pCur );
116 pCur = toGuard.load(atomics::memory_order_acquire);
117 } while ( pRet != pCur );
121 /// Protects a converted pointer of type \p atomic<T*>
123 Return the value of \p toGuard
125 The function tries to load \p toGuard and to store result of \p f functor
126 to the HP slot repeatedly until the guard's value equals \p toGuard.
128 The function is useful for intrusive containers when \p toGuard is a node pointer
129 that should be converted to a pointer to the value type before protecting.
130 The parameter \p f of type Func is a functor that makes this conversion:
133 value_type * operator()( T * p );
136 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
138 template <typename T, class Func>
139 T protect( atomics::atomic<T> const& toGuard, Func f )
141 T pCur = toGuard.load(atomics::memory_order_relaxed);
146 pCur = toGuard.load(atomics::memory_order_acquire);
147 } while ( pRet != pCur );
151 /// Store \p p to the guard
153 The function equals to a simple assignment the value \p p to guard, no loop is performed.
154 Can be used for a pointer that cannot be changed concurrently
156 template <typename T>
159 return base_class::operator =(p);
163 std::nullptr_t assign( std::nullptr_t )
165 return base_class::operator =(nullptr);
169 /// Copy from \p src guard to \p this guard
170 void copy( Guard const& src )
172 assign( src.get_native() );
175 /// Store marked pointer \p p to the guard
177 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
178 Can be used for a marked pointer that cannot be changed concurrently.
180 template <typename T, int BITMASK>
181 T * assign( cds::details::marked_ptr<T, BITMASK> p )
183 return base_class::operator =( p.ptr() );
186 /// Clear value of the guard
192 /// Get the value currently protected
193 template <typename T>
196 return reinterpret_cast<T *>( get_native() );
199 /// Get native hazard pointer stored
200 guarded_pointer get_native() const
202 return base_class::get();
206 /// Array of Hazard Pointer guards
208 @headerfile cds/gc/hp.h
209 This class is a wrapper for hzp::AutoHPArray template.
210 Template parameter \p Count defines the size of HP array.
212 template <size_t Count>
213 class GuardArray: public hzp::AutoHPArray<Count>
216 typedef hzp::AutoHPArray<Count> base_class;
219 /// Rebind array for other size \p Count2
220 template <size_t Count2>
222 typedef GuardArray<Count2> other ; ///< rebinding result
227 GuardArray() ; // inline in hp_impl.h
229 /// Protects a pointer of type \p atomic<T*>
231 Return the value of \p toGuard
233 The function tries to load \p toGuard and to store it
234 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
236 template <typename T>
237 T protect(size_t nIndex, atomics::atomic<T> const& toGuard )
241 pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire) );
242 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
247 /// Protects a pointer of type \p atomic<T*>
249 Return the value of \p toGuard
251 The function tries to load \p toGuard and to store it
252 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
254 The function is useful for intrusive containers when \p toGuard is a node pointer
255 that should be converted to a pointer to the value type before guarding.
256 The parameter \p f of type Func is a functor that makes this conversion:
259 value_type * operator()( T * p );
262 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
264 template <typename T, class Func>
265 T protect(size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
269 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire) ));
270 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
275 /// Store \p to the slot \p nIndex
277 The function equals to a simple assignment, no loop is performed.
279 template <typename T>
280 T * assign( size_t nIndex, T * p )
282 base_class::set(nIndex, p);
286 /// Store marked pointer \p p to the guard
288 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
289 Can be used for a marked pointer that cannot be changed concurrently.
291 template <typename T, int BITMASK>
292 T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p )
294 return assign( nIndex, p.ptr() );
297 /// Copy guarded value from \p src guard to slot at index \p nIndex
298 void copy( size_t nIndex, Guard const& src )
300 assign( nIndex, src.get_native() );
303 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
304 void copy( size_t nDestIndex, size_t nSrcIndex )
306 assign( nDestIndex, get_native( nSrcIndex ));
309 /// Clear value of the slot \p nIndex
310 void clear( size_t nIndex)
312 base_class::clear( nIndex );
315 /// Get current value of slot \p nIndex
316 template <typename T>
317 T * get( size_t nIndex) const
319 return reinterpret_cast<T *>( get_native( nIndex ) );
322 /// Get native hazard pointer stored
323 guarded_pointer get_native( size_t nIndex ) const
325 return base_class::operator[](nIndex).get();
328 /// Capacity of the guard array
329 static CDS_CONSTEXPR size_t capacity()
336 /// Initializes hzp::GarbageCollector singleton
338 The constructor initializes GC singleton with passed parameters.
339 If GC instance is not exist then the function creates the instance.
340 Otherwise it does nothing.
342 The Michael's HP reclamation schema depends of three parameters:
343 - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
344 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
345 uses maximum of the hazard pointer count for CDS library.
346 - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
347 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
348 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
351 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
352 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
353 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
354 hzp::scan_type nScanType = hzp::inplace ///< Scan type (see \ref hzp::scan_type enum)
357 hzp::GarbageCollector::Construct(
365 /// Terminates GC singleton
367 The destructor calls \code hzp::GarbageCollector::Destruct( true ) \endcode
371 hzp::GarbageCollector::Destruct( true );
374 /// Checks if count of hazard pointer is no less than \p nCountNeeded
376 If \p bRaiseException is \p true (that is the default), the function raises
377 an \p std::overflow_error exception "Too few hazard pointers"
378 if \p nCountNeeded is more than the count of hazard pointer per thread.
380 static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
382 if ( hzp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
383 if ( bRaiseException )
384 throw std::overflow_error( "Too few hazard pointers" );
390 /// Returns max Hazard Pointer count
391 size_t max_hazard_count() const
393 return hzp::GarbageCollector::instance().getHazardPointerCount();
396 /// Returns max count of thread
397 size_t max_thread_count() const
399 return hzp::GarbageCollector::instance().getMaxThreadCount();
402 /// Returns capacity of retired pointer array
403 size_t retired_array_capacity() const
405 return hzp::GarbageCollector::instance().getMaxRetiredPtrCount();
408 /// Retire pointer \p p with function \p pFunc
410 The function places pointer \p p to array of pointers ready for removing.
411 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
412 Deleting the pointer is the function \p pFunc call.
414 template <typename T>
415 static void retire( T * p, void (* pFunc)(T *) ) ; // inline in hp_impl.h
417 /// Retire pointer \p p with functor of type \p Disposer
419 The function places pointer \p p to array of pointers ready for removing.
420 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
422 Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
424 template <typename T>
426 void operator()( T * p ) ; // disposing operator
429 Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
430 - it should be stateless functor
431 - it should be default-constructible
432 - the result of functor call with argument \p p should not depend on where the functor will be called.
435 Operator \p delete functor:
437 template <typename T>
439 void operator ()( T * p ) {
444 // How to call GC::retire method
447 // ... use p in lock-free manner
449 cds::gc::HP::retire<disposer>( p ) ; // place p to retired pointer array of HP GC
452 Functor based on \p std::allocator :
454 template <typename ALLOC = std::allocator<int> >
456 template <typename T>
457 void operator()( T * p ) {
458 typedef typename ALLOC::templare rebind<T>::other alloc_t;
461 a.deallocate( p, 1 );
466 template <class Disposer, typename T>
467 static void retire( T * p ) ; // inline in hp_impl.h
469 /// Get current scan strategy
470 hzp::scan_type getScanType() const
472 return hzp::GarbageCollector::instance().getScanType();
475 /// Set current scan strategy
477 hzp::scan_type nScanType ///< new scan strategy
480 hzp::GarbageCollector::instance().setScanType( nScanType );
483 /// Checks if Hazard Pointer GC is constructed and may be used
486 return hzp::GarbageCollector::isUsed();
490 /// Forced GC cycle call for current thread
492 Usually, this function should not be called directly.
494 static void scan() ; // inline in hp_impl.h
496 /// Synonym for \ref scan()
497 static void force_dispose()
502 }} // namespace cds::gc
504 #endif // #ifndef __CDS_GC_HP_HP_DECL_H