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;
31 #ifdef CDS_CXX11_TEMPLATE_ALIAS_SUPPORT
34 @headerfile cds/gc/hp.h
36 template <typename T> using atomic_ref = CDS_ATOMIC::atomic<T *>;
38 /// Atomic marked pointer
40 @headerfile cds/gc/hp.h
42 template <typename MarkedPtr> using atomic_marked_ptr = CDS_ATOMIC::atomic<MarkedPtr>;
46 @headerfile cds/gc/hp.h
48 template <typename T> using atomic_type = CDS_ATOMIC::atomic<T>;
51 class atomic_ref: public CDS_ATOMIC::atomic<T *>
53 typedef CDS_ATOMIC::atomic<T *> base_class;
55 # ifdef CDS_CXX11_EXPLICITLY_DEFAULTED_FUNCTION_SUPPORT
56 atomic_ref() = default;
62 explicit CDS_CONSTEXPR atomic_ref(T * p) CDS_NOEXCEPT
68 class atomic_type: public CDS_ATOMIC::atomic<T>
70 typedef CDS_ATOMIC::atomic<T> base_class;
72 # ifdef CDS_CXX11_EXPLICITLY_DEFAULTED_FUNCTION_SUPPORT
73 atomic_type() = default;
75 atomic_type() CDS_NOEXCEPT
79 explicit CDS_CONSTEXPR atomic_type(T const & v) CDS_NOEXCEPT
84 template <typename MarkedPtr>
85 class atomic_marked_ptr: public CDS_ATOMIC::atomic<MarkedPtr>
87 typedef CDS_ATOMIC::atomic<MarkedPtr> base_class;
89 # ifdef CDS_CXX11_EXPLICITLY_DEFAULTED_FUNCTION_SUPPORT
90 atomic_marked_ptr() CDS_NOEXCEPT_DEFAULTED_( noexcept(base_class()) ) = default;
92 atomic_marked_ptr() CDS_NOEXCEPT_( noexcept(base_class()) )
96 explicit CDS_CONSTEXPR atomic_marked_ptr(MarkedPtr val) CDS_NOEXCEPT_( noexcept(base_class( val )) )
99 explicit CDS_CONSTEXPR atomic_marked_ptr(typename MarkedPtr::value_type * p) CDS_NOEXCEPT_( noexcept(base_class( p )) )
105 /// Thread GC implementation for internal usage
106 typedef hzp::ThreadGC thread_gc_impl;
108 /// Wrapper for hzp::ThreadGC class
110 @headerfile cds/gc/hp.h
111 This class performs automatically attaching/detaching Hazard Pointer GC
112 for the current thread.
114 class thread_gc: public thread_gc_impl
123 The constructor attaches the current thread to the Hazard Pointer GC
124 if it is not yet attached.
125 The \p bPersistent parameter specifies attachment persistence:
126 - \p true - the class destructor will not detach the thread from Hazard Pointer GC.
127 - \p false (default) - the class destructor will detach the thread from Hazard Pointer GC.
130 bool bPersistent = false
131 ) ; //inline in hp_impl.h
135 If the object has been created in persistent mode, the destructor does nothing.
136 Otherwise it detaches the current thread from Hazard Pointer GC.
138 ~thread_gc() ; // inline in hp_impl.h
141 /// Base for container node
143 @headerfile cds/gc/hp.h
144 This struct is empty for Hazard Pointer GC
146 struct container_node
149 /// Hazard Pointer guard
151 @headerfile cds/gc/hp.h
152 This class is a wrapper for hzp::AutoHPGuard.
154 class Guard: public hzp::AutoHPGuard
157 typedef hzp::AutoHPGuard base_class;
162 Guard() ; // inline in hp_impl.h
165 /// Protects a pointer of type \p atomic<T*>
167 Return the value of \p toGuard
169 The function tries to load \p toGuard and to store it
170 to the HP slot repeatedly until the guard's value equals \p toGuard
172 template <typename T>
173 T protect( CDS_ATOMIC::atomic<T> const& toGuard )
175 T pCur = toGuard.load(CDS_ATOMIC::memory_order_relaxed);
178 pRet = assign( pCur );
179 pCur = toGuard.load(CDS_ATOMIC::memory_order_acquire);
180 } while ( pRet != pCur );
184 /// Protects a converted pointer of type \p atomic<T*>
186 Return the value of \p toGuard
188 The function tries to load \p toGuard and to store result of \p f functor
189 to the HP slot repeatedly until the guard's value equals \p toGuard.
191 The function is useful for intrusive containers when \p toGuard is a node pointer
192 that should be converted to a pointer to the value type before protecting.
193 The parameter \p f of type Func is a functor that makes this conversion:
196 value_type * operator()( T * p );
199 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
201 template <typename T, class Func>
202 T protect( CDS_ATOMIC::atomic<T> const& toGuard, Func f )
204 T pCur = toGuard.load(CDS_ATOMIC::memory_order_relaxed);
209 pCur = toGuard.load(CDS_ATOMIC::memory_order_acquire);
210 } while ( pRet != pCur );
214 /// Store \p p to the guard
216 The function equals to a simple assignment the value \p p to guard, no loop is performed.
217 Can be used for a pointer that cannot be changed concurrently
219 template <typename T>
222 return base_class::operator =(p);
226 std::nullptr_t assign( std::nullptr_t )
228 return base_class::operator =(nullptr);
232 /// Copy from \p src guard to \p this guard
233 void copy( Guard const& src )
235 assign( src.get_native() );
238 /// Store marked pointer \p p to the guard
240 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
241 Can be used for a marked pointer that cannot be changed concurrently.
243 template <typename T, int BITMASK>
244 T * assign( cds::details::marked_ptr<T, BITMASK> p )
246 return base_class::operator =( p.ptr() );
249 /// Clear value of the guard
255 /// Get the value currently protected
256 template <typename T>
259 return reinterpret_cast<T *>( get_native() );
262 /// Get native hazard pointer stored
263 guarded_pointer get_native() const
265 return base_class::get();
269 /// Array of Hazard Pointer guards
271 @headerfile cds/gc/hp.h
272 This class is a wrapper for hzp::AutoHPArray template.
273 Template parameter \p Count defines the size of HP array.
275 template <size_t Count>
276 class GuardArray: public hzp::AutoHPArray<Count>
279 typedef hzp::AutoHPArray<Count> base_class;
282 /// Rebind array for other size \p Count2
283 template <size_t Count2>
285 typedef GuardArray<Count2> other ; ///< rebinding result
290 GuardArray() ; // inline in hp_impl.h
292 /// Protects a pointer of type \p atomic<T*>
294 Return the value of \p toGuard
296 The function tries to load \p toGuard and to store it
297 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
299 template <typename T>
300 T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard )
304 pRet = assign( nIndex, toGuard.load(CDS_ATOMIC::memory_order_acquire) );
305 } while ( pRet != toGuard.load(CDS_ATOMIC::memory_order_relaxed));
310 /// Protects a pointer of type \p atomic<T*>
312 Return the value of \p toGuard
314 The function tries to load \p toGuard and to store it
315 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
317 The function is useful for intrusive containers when \p toGuard is a node pointer
318 that should be converted to a pointer to the value type before guarding.
319 The parameter \p f of type Func is a functor that makes this conversion:
322 value_type * operator()( T * p );
325 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
327 template <typename T, class Func>
328 T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard, Func f )
332 assign( nIndex, f( pRet = toGuard.load(CDS_ATOMIC::memory_order_acquire) ));
333 } while ( pRet != toGuard.load(CDS_ATOMIC::memory_order_relaxed));
338 /// Store \p to the slot \p nIndex
340 The function equals to a simple assignment, no loop is performed.
342 template <typename T>
343 T * assign( size_t nIndex, T * p )
345 base_class::set(nIndex, p);
349 /// Store marked pointer \p p to the guard
351 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
352 Can be used for a marked pointer that cannot be changed concurrently.
354 template <typename T, int BITMASK>
355 T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p )
357 return assign( nIndex, p.ptr() );
360 /// Copy guarded value from \p src guard to slot at index \p nIndex
361 void copy( size_t nIndex, Guard const& src )
363 assign( nIndex, src.get_native() );
366 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
367 void copy( size_t nDestIndex, size_t nSrcIndex )
369 assign( nDestIndex, get_native( nSrcIndex ));
372 /// Clear value of the slot \p nIndex
373 void clear( size_t nIndex)
375 base_class::clear( nIndex );
378 /// Get current value of slot \p nIndex
379 template <typename T>
380 T * get( size_t nIndex) const
382 return reinterpret_cast<T *>( get_native( nIndex ) );
385 /// Get native hazard pointer stored
386 guarded_pointer get_native( size_t nIndex ) const
388 return base_class::operator[](nIndex).get();
391 /// Capacity of the guard array
392 static CDS_CONSTEXPR size_t capacity()
399 /// Initializes hzp::GarbageCollector singleton
401 The constructor initializes GC singleton with passed parameters.
402 If GC instance is not exist then the function creates the instance.
403 Otherwise it does nothing.
405 The Michael's HP reclamation schema depends of three parameters:
406 - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
407 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
408 uses maximum of the hazard pointer count for CDS library.
409 - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
410 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
411 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
414 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
415 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
416 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
417 hzp::scan_type nScanType = hzp::inplace ///< Scan type (see \ref hzp::scan_type enum)
420 hzp::GarbageCollector::Construct(
428 /// Terminates GC singleton
430 The destructor calls \code hzp::GarbageCollector::Destruct( true ) \endcode
434 hzp::GarbageCollector::Destruct( true );
437 /// Checks if count of hazard pointer is no less than \p nCountNeeded
439 If \p bRaiseException is \p true (that is the default), the function raises an exception gc::too_few_hazard_pointers
440 if \p nCountNeeded is more than the count of hazard pointer per thread.
442 static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
444 if ( hzp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
445 if ( bRaiseException )
446 throw cds::gc::too_few_hazard_pointers();
452 /// Returns max Hazard Pointer count
453 size_t max_hazard_count() const
455 return hzp::GarbageCollector::instance().getHazardPointerCount();
458 /// Returns max count of thread
459 size_t max_thread_count() const
461 return hzp::GarbageCollector::instance().getMaxThreadCount();
464 /// Returns capacity of retired pointer array
465 size_t retired_array_capacity() const
467 return hzp::GarbageCollector::instance().getMaxRetiredPtrCount();
470 /// Retire pointer \p p with function \p pFunc
472 The function places pointer \p p to array of pointers ready for removing.
473 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
474 Deleting the pointer is the function \p pFunc call.
476 template <typename T>
477 static void retire( T * p, void (* pFunc)(T *) ) ; // inline in hp_impl.h
479 /// Retire pointer \p p with functor of type \p Disposer
481 The function places pointer \p p to array of pointers ready for removing.
482 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
484 Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
486 template <typename T>
488 void operator()( T * p ) ; // disposing operator
491 Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
492 - it should be stateless functor
493 - it should be default-constructible
494 - the result of functor call with argument \p p should not depend on where the functor will be called.
497 Operator \p delete functor:
499 template <typename T>
501 void operator ()( T * p ) {
506 // How to call GC::retire method
509 // ... use p in lock-free manner
511 cds::gc::HP::retire<disposer>( p ) ; // place p to retired pointer array of HP GC
514 Functor based on \p std::allocator :
516 template <typename ALLOC = std::allocator<int> >
518 template <typename T>
519 void operator()( T * p ) {
520 typedef typename ALLOC::templare rebind<T>::other alloc_t;
523 a.deallocate( p, 1 );
528 template <class Disposer, typename T>
529 static void retire( T * p ) ; // inline in hp_impl.h
531 /// Get current scan strategy
532 /**@anchor hrc_gc_HP_getScanType
533 See hzp::GarbageCollector::Scan for scan algo description
535 hzp::scan_type getScanType() const
537 return hzp::GarbageCollector::instance().getScanType();
540 /// Set current scan strategy
542 Scan strategy changing is allowed on the fly.
544 About scan strategy see \ref hrc_gc_HP_getScanType "getScanType"
547 hzp::scan_type nScanType ///< new scan strategy
550 hzp::GarbageCollector::instance().setScanType( nScanType );
553 /// Checks if Hazard Pointer GC is constructed and may be used
556 return hzp::GarbageCollector::isUsed();
560 /// Forced GC cycle call for current thread
562 Usually, this function should not be called directly.
564 static void scan() ; // inline in hp_impl.h
566 /// Synonym for \ref scan()
567 static void force_dispose()
572 }} // namespace cds::gc
574 #endif // #ifndef __CDS_GC_HP_DECL_H