3 #ifndef __CDS_GC_IMPL_HP_DECL_H
4 #define __CDS_GC_IMPL_HP_DECL_H
6 #include <stdexcept> // overflow_error
7 #include <cds/gc/details/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 Implementation of classic Hazard Pointer garbage collector.
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 how to apply garbage collector.
29 /// Native guarded pointer type
31 @headerfile cds/gc/hp.h
33 typedef gc::hp::hazard_pointer guarded_pointer;
37 @headerfile cds/gc/hp.h
39 template <typename T> using atomic_ref = atomics::atomic<T *>;
41 /// Atomic marked pointer
43 @headerfile cds/gc/hp.h
45 template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
49 @headerfile cds/gc/hp.h
51 template <typename T> using atomic_type = atomics::atomic<T>;
53 /// Thread GC implementation for internal usage
55 @headerfile cds/gc/hp.h
57 typedef hp::ThreadGC thread_gc_impl;
59 /// Wrapper for hp::ThreadGC class
61 @headerfile cds/gc/hp.h
62 This class performs automatically attaching/detaching Hazard Pointer GC
63 for the current thread.
65 class thread_gc: public thread_gc_impl
74 The constructor attaches the current thread to the Hazard Pointer GC
75 if it is not yet attached.
76 The \p bPersistent parameter specifies attachment persistence:
77 - \p true - the class destructor will not detach the thread from Hazard Pointer GC.
78 - \p false (default) - the class destructor will detach the thread from Hazard Pointer GC.
81 bool bPersistent = false
82 ) ; //inline in hp_impl.h
86 If the object has been created in persistent mode, the destructor does nothing.
87 Otherwise it detaches the current thread from Hazard Pointer GC.
89 ~thread_gc() ; // inline in hp_impl.h
92 /// Hazard Pointer guard
94 @headerfile cds/gc/hp.h
96 A guard is the hazard pointer.
97 Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
99 A \p %Guard object is not copy- and move-constructible
100 and not copy- and move-assignable.
102 class Guard : public hp::guard
105 typedef hp::guard base_class;
110 Guard() CDS_NOEXCEPT; // inline in hp_impl.h
113 Guard( Guard const& ) = delete;
114 Guard( Guard&& s ) = delete;
115 Guard& operator=(Guard const&) = delete;
116 Guard& operator=(Guard&&) = delete;
119 /// Protects a pointer of type \p atomic<T*>
121 Return the value of \p toGuard
123 The function tries to load \p toGuard and to store it
124 to the HP slot repeatedly until the guard's value equals \p toGuard
126 template <typename T>
127 T protect( atomics::atomic<T> const& toGuard ) CDS_NOEXCEPT
129 T pCur = toGuard.load(atomics::memory_order_relaxed);
132 pRet = assign( pCur );
133 pCur = toGuard.load(atomics::memory_order_acquire);
134 } while ( pRet != pCur );
138 /// Protects a converted pointer of type \p atomic<T*>
140 Return the value of \p toGuard
142 The function tries to load \p toGuard and to store result of \p f functor
143 to the HP slot repeatedly until the guard's value equals \p toGuard.
145 The function is useful for intrusive containers when \p toGuard is a node pointer
146 that should be converted to a pointer to the value type before protecting.
147 The parameter \p f of type Func is a functor that makes this conversion:
150 value_type * operator()( T * p );
153 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
155 template <typename T, class Func>
156 T protect( atomics::atomic<T> const& toGuard, Func f )
158 T pCur = toGuard.load(atomics::memory_order_relaxed);
163 pCur = toGuard.load(atomics::memory_order_acquire);
164 } while ( pRet != pCur );
168 /// Store \p p to the guard
170 The function equals to a simple assignment the value \p p to guard, no loop is performed.
171 Can be used for a pointer that cannot be changed concurrently
173 template <typename T>
174 T * assign( T * p ) CDS_NOEXCEPT
176 return base_class::operator =(p);
180 std::nullptr_t assign( std::nullptr_t ) CDS_NOEXCEPT
182 return base_class::operator =(nullptr);
186 /// Copy from \p src guard to \p this guard
187 void copy( Guard const& src ) CDS_NOEXCEPT
189 assign( src.get_native() );
192 /// Store marked pointer \p p to the guard
194 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
195 Can be used for a marked pointer that cannot be changed concurrently.
197 template <typename T, int BITMASK>
198 T * assign( cds::details::marked_ptr<T, BITMASK> p ) CDS_NOEXCEPT
200 return base_class::operator =( p.ptr() );
203 /// Clear value of the guard
204 void clear() CDS_NOEXCEPT
209 /// Get the value currently protected
210 template <typename T>
211 T * get() const CDS_NOEXCEPT
213 return reinterpret_cast<T *>( get_native() );
216 /// Get native hazard pointer stored
217 guarded_pointer get_native() const CDS_NOEXCEPT
219 return base_class::get();
223 /// Array of Hazard Pointer guards
225 @headerfile cds/gc/hp.h
226 The class is intended for allocating an array of hazard pointer guards.
227 Template parameter \p Count defines the size of the array.
229 A \p %GuardArray object is not copy- and move-constructible
230 and not copy- and move-assignable.
232 template <size_t Count>
233 class GuardArray : public hp::array<Count>
236 typedef hp::array<Count> base_class;
239 /// Rebind array for other size \p Count2
240 template <size_t Count2>
242 typedef GuardArray<Count2> other ; ///< rebinding result
247 GuardArray() CDS_NOEXCEPT; // inline in hp_impl.h
250 GuardArray( GuardArray const& ) = delete;
251 GuardArray( GuardArray&& ) = delete;
252 GuardArray& operator=(GuardArray const&) = delete;
253 GuardArray& operator-(GuardArray&&) = delete;
256 /// Protects a pointer of type \p atomic<T*>
258 Return the value of \p toGuard
260 The function tries to load \p toGuard and to store it
261 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
263 template <typename T>
264 T protect( size_t nIndex, atomics::atomic<T> const& toGuard ) CDS_NOEXCEPT
268 pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire) );
269 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
274 /// Protects a pointer of type \p atomic<T*>
276 Return the value of \p toGuard
278 The function tries to load \p toGuard and to store it
279 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
281 The function is useful for intrusive containers when \p toGuard is a node pointer
282 that should be converted to a pointer to the value type before guarding.
283 The parameter \p f of type Func is a functor that makes this conversion:
286 value_type * operator()( T * p );
289 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
291 template <typename T, class Func>
292 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
296 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire) ));
297 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
302 /// Store \p to the slot \p nIndex
304 The function equals to a simple assignment, no loop is performed.
306 template <typename T>
307 T * assign( size_t nIndex, T * p ) CDS_NOEXCEPT
309 base_class::set(nIndex, p);
313 /// Store marked pointer \p p to the guard
315 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
316 Can be used for a marked pointer that cannot be changed concurrently.
318 template <typename T, int BITMASK>
319 T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p ) CDS_NOEXCEPT
321 return assign( nIndex, p.ptr() );
324 /// Copy guarded value from \p src guard to slot at index \p nIndex
325 void copy( size_t nIndex, Guard const& src ) CDS_NOEXCEPT
327 assign( nIndex, src.get_native() );
330 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
331 void copy( size_t nDestIndex, size_t nSrcIndex ) CDS_NOEXCEPT
333 assign( nDestIndex, get_native( nSrcIndex ));
336 /// Clear value of the slot \p nIndex
337 void clear( size_t nIndex ) CDS_NOEXCEPT
339 base_class::clear( nIndex );
342 /// Get current value of slot \p nIndex
343 template <typename T>
344 T * get( size_t nIndex ) const CDS_NOEXCEPT
346 return reinterpret_cast<T *>( get_native( nIndex ) );
349 /// Get native hazard pointer stored
350 guarded_pointer get_native( size_t nIndex ) const CDS_NOEXCEPT
352 return base_class::operator[](nIndex).get();
355 /// Capacity of the guard array
356 static CDS_CONSTEXPR size_t capacity() CDS_NOEXCEPT
364 enum class scan_type {
365 classic = hp::classic, ///< classic scan as described in Michael's papers
366 inplace = hp::inplace ///< inplace scan without allocation
368 /// Initializes hp::GarbageCollector singleton
370 The constructor initializes GC singleton with passed parameters.
371 If GC instance is not exist then the function creates the instance.
372 Otherwise it does nothing.
374 The Michael's HP reclamation schema depends of three parameters:
375 - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
376 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
377 uses maximum of the hazard pointer count for CDS library.
378 - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
379 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
380 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
383 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
384 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
385 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
386 scan_type nScanType = scan_type::inplace ///< Scan type (see \p scan_type enum)
389 hp::GarbageCollector::Construct(
393 static_cast<hp::scan_type>(nScanType)
397 /// Terminates GC singleton
399 The destructor calls \code hp::GarbageCollector::Destruct( true ) \endcode
403 hp::GarbageCollector::Destruct( true );
406 /// Checks if count of hazard pointer is no less than \p nCountNeeded
408 If \p bRaiseException is \p true (that is the default), the function raises
409 an \p std::overflow_error exception "Too few hazard pointers"
410 if \p nCountNeeded is more than the count of hazard pointer per thread.
412 static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
414 if ( hp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
415 if ( bRaiseException )
416 throw std::overflow_error( "Too few hazard pointers" );
422 /// Returns max Hazard Pointer count
423 size_t max_hazard_count() const
425 return hp::GarbageCollector::instance().getHazardPointerCount();
428 /// Returns max count of thread
429 size_t max_thread_count() const
431 return hp::GarbageCollector::instance().getMaxThreadCount();
434 /// Returns capacity of retired pointer array
435 size_t retired_array_capacity() const
437 return hp::GarbageCollector::instance().getMaxRetiredPtrCount();
440 /// Retire pointer \p p with function \p pFunc
442 The function places pointer \p p to array of pointers ready for removing.
443 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
444 Deleting the pointer is the function \p pFunc call.
446 template <typename T>
447 static void retire( T * p, void (* pFunc)(T *) ) ; // inline in hp_impl.h
449 /// Retire pointer \p p with functor of type \p Disposer
451 The function places pointer \p p to array of pointers ready for removing.
452 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
454 Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
456 template <typename T>
458 void operator()( T * p ) ; // disposing operator
461 Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
462 - it should be stateless functor
463 - it should be default-constructible
464 - the result of functor call with argument \p p should not depend on where the functor will be called.
467 Operator \p delete functor:
469 template <typename T>
471 void operator ()( T * p ) {
476 // How to call GC::retire method
479 // ... use p in lock-free manner
481 cds::gc::HP::retire<disposer>( p ) ; // place p to retired pointer array of HP GC
484 Functor based on \p std::allocator :
486 template <typename ALLOC = std::allocator<int> >
488 template <typename T>
489 void operator()( T * p ) {
490 typedef typename ALLOC::templare rebind<T>::other alloc_t;
493 a.deallocate( p, 1 );
498 template <class Disposer, typename T>
499 static void retire( T * p ) ; // inline in hp_impl.h
501 /// Get current scan strategy
502 scan_type getScanType() const
504 return static_cast<scan_type>( hp::GarbageCollector::instance().getScanType());
507 /// Set current scan strategy
509 scan_type nScanType ///< new scan strategy
512 hp::GarbageCollector::instance().setScanType( static_cast<hp::scan_type>(nScanType) );
515 /// Checks if Hazard Pointer GC is constructed and may be used
518 return hp::GarbageCollector::isUsed();
521 /// Forced GC cycle call for current thread
523 Usually, this function should not be called directly.
525 static void scan() ; // inline in hp_impl.h
527 /// Synonym for \ref scan()
528 static void force_dispose()
533 }} // namespace cds::gc
535 #endif // #ifndef __CDS_GC_IMPL_HP_DECL_H