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 Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is
25 GC class \p %cds::gc::HP and its nested classes. Before use any HP-related class you must initialize HP garbage collector
26 by contructing \p %cds::gc::HP object in beginning of your \p main().
27 See \ref cds_how_to_use "How to use" section for details how to apply garbage collector.
32 /// Native guarded pointer type
34 @headerfile cds/gc/hp.h
36 typedef gc::hp::hazard_pointer guarded_pointer;
40 @headerfile cds/gc/hp.h
42 template <typename T> using atomic_ref = atomics::atomic<T *>;
44 /// Atomic marked pointer
46 @headerfile cds/gc/hp.h
48 template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
52 @headerfile cds/gc/hp.h
54 template <typename T> using atomic_type = atomics::atomic<T>;
56 /// Thread GC implementation for internal usage
58 @headerfile cds/gc/hp.h
60 typedef hp::ThreadGC thread_gc_impl;
62 /// Wrapper for hp::ThreadGC class
64 @headerfile cds/gc/hp.h
65 This class performs automatically attaching/detaching Hazard Pointer GC
66 for the current thread.
68 class thread_gc: public thread_gc_impl
77 The constructor attaches the current thread to the Hazard Pointer GC
78 if it is not yet attached.
79 The \p bPersistent parameter specifies attachment persistence:
80 - \p true - the class destructor will not detach the thread from Hazard Pointer GC.
81 - \p false (default) - the class destructor will detach the thread from Hazard Pointer GC.
84 bool bPersistent = false
85 ) ; //inline in hp_impl.h
89 If the object has been created in persistent mode, the destructor does nothing.
90 Otherwise it detaches the current thread from Hazard Pointer GC.
92 ~thread_gc() ; // inline in hp_impl.h
95 /// Hazard Pointer guard
97 @headerfile cds/gc/hp.h
99 A guard is the hazard pointer.
100 Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
102 A \p %Guard object is not copy- and move-constructible
103 and not copy- and move-assignable.
105 class Guard : public hp::guard
108 typedef hp::guard base_class;
113 Guard() CDS_NOEXCEPT; // inline in hp_impl.h
116 Guard( Guard const& ) = delete;
117 Guard( Guard&& s ) = delete;
118 Guard& operator=(Guard const&) = delete;
119 Guard& operator=(Guard&&) = delete;
122 /// Protects a pointer of type \p atomic<T*>
124 Return the value of \p toGuard
126 The function tries to load \p toGuard and to store it
127 to the HP slot repeatedly until the guard's value equals \p toGuard
129 template <typename T>
130 T protect( atomics::atomic<T> const& toGuard ) CDS_NOEXCEPT
132 T pCur = toGuard.load(atomics::memory_order_relaxed);
135 pRet = assign( pCur );
136 pCur = toGuard.load(atomics::memory_order_acquire);
137 } while ( pRet != pCur );
141 /// Protects a converted pointer of type \p atomic<T*>
143 Return the value of \p toGuard
145 The function tries to load \p toGuard and to store result of \p f functor
146 to the HP slot repeatedly until the guard's value equals \p toGuard.
148 The function is useful for intrusive containers when \p toGuard is a node pointer
149 that should be converted to a pointer to the value before protecting.
150 The parameter \p f of type Func is a functor that makes this conversion:
153 value_type * operator()( T * p );
156 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
158 template <typename T, class Func>
159 T protect( atomics::atomic<T> const& toGuard, Func f )
161 T pCur = toGuard.load(atomics::memory_order_relaxed);
166 pCur = toGuard.load(atomics::memory_order_acquire);
167 } while ( pRet != pCur );
171 /// Store \p p to the guard
173 The function equals to a simple assignment the value \p p to guard, no loop is performed.
174 Can be used for a pointer that cannot be changed concurrently
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 /// Copy from \p src guard to \p this guard
190 void copy( Guard const& src ) CDS_NOEXCEPT
192 assign( src.get_native() );
195 /// Store marked pointer \p p to the guard
197 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
198 Can be used for a marked pointer that cannot be changed concurrently.
200 template <typename T, int BITMASK>
201 T * assign( cds::details::marked_ptr<T, BITMASK> p ) CDS_NOEXCEPT
203 return base_class::operator =( p.ptr() );
206 /// Clear value of the guard
207 void clear() CDS_NOEXCEPT
212 /// Get the value currently protected
213 template <typename T>
214 T * get() const CDS_NOEXCEPT
216 return reinterpret_cast<T *>( get_native() );
219 /// Get native hazard pointer stored
220 guarded_pointer get_native() const CDS_NOEXCEPT
222 return base_class::get();
226 /// Array of Hazard Pointer guards
228 @headerfile cds/gc/hp.h
229 The class is intended for allocating an array of hazard pointer guards.
230 Template parameter \p Count defines the size of the array.
232 A \p %GuardArray object is not copy- and move-constructible
233 and not copy- and move-assignable.
235 template <size_t Count>
236 class GuardArray : public hp::array<Count>
239 typedef hp::array<Count> base_class;
242 /// Rebind array for other size \p Count2
243 template <size_t Count2>
245 typedef GuardArray<Count2> other ; ///< rebinding result
250 GuardArray() CDS_NOEXCEPT; // inline in hp_impl.h
253 GuardArray( GuardArray const& ) = delete;
254 GuardArray( GuardArray&& ) = delete;
255 GuardArray& operator=(GuardArray const&) = delete;
256 GuardArray& operator-(GuardArray&&) = delete;
259 /// Protects a pointer of type \p atomic<T*>
261 Return the value of \p toGuard
263 The function tries to load \p toGuard and to store it
264 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
266 template <typename T>
267 T protect( size_t nIndex, atomics::atomic<T> const& toGuard ) CDS_NOEXCEPT
271 pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) );
272 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
277 /// Protects a pointer of type \p atomic<T*>
279 Return the value of \p toGuard
281 The function tries to load \p toGuard and to store it
282 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
284 The function is useful for intrusive containers when \p toGuard is a node pointer
285 that should be converted to a pointer to the value type before guarding.
286 The parameter \p f of type Func is a functor that makes this conversion:
289 value_type * operator()( T * p );
292 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
294 template <typename T, class Func>
295 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
299 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
300 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
305 /// Store \p to the slot \p nIndex
307 The function equals to a simple assignment, no loop is performed.
309 template <typename T>
310 T * assign( size_t nIndex, T * p ) CDS_NOEXCEPT
312 base_class::set(nIndex, p);
316 /// Store marked pointer \p p to the guard
318 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
319 Can be used for a marked pointer that cannot be changed concurrently.
321 template <typename T, int BITMASK>
322 T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p ) CDS_NOEXCEPT
324 return assign( nIndex, p.ptr() );
327 /// Copy guarded value from \p src guard to slot at index \p nIndex
328 void copy( size_t nIndex, Guard const& src ) CDS_NOEXCEPT
330 assign( nIndex, src.get_native() );
333 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
334 void copy( size_t nDestIndex, size_t nSrcIndex ) CDS_NOEXCEPT
336 assign( nDestIndex, get_native( nSrcIndex ));
339 /// Clear value of the slot \p nIndex
340 void clear( size_t nIndex ) CDS_NOEXCEPT
342 base_class::clear( nIndex );
345 /// Get current value of slot \p nIndex
346 template <typename T>
347 T * get( size_t nIndex ) const CDS_NOEXCEPT
349 return reinterpret_cast<T *>( get_native( nIndex ) );
352 /// Get native hazard pointer stored
353 guarded_pointer get_native( size_t nIndex ) const CDS_NOEXCEPT
355 return base_class::operator[](nIndex).get();
358 /// Capacity of the guard array
359 static CDS_CONSTEXPR size_t capacity() CDS_NOEXCEPT
367 enum class scan_type {
368 classic = hp::classic, ///< classic scan as described in Michael's papers
369 inplace = hp::inplace ///< inplace scan without allocation
371 /// Initializes hp::GarbageCollector singleton
373 The constructor initializes GC singleton with passed parameters.
374 If GC instance is not exist then the function creates the instance.
375 Otherwise it does nothing.
377 The Michael's HP reclamation schema depends of three parameters:
378 - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
379 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
380 uses maximum of the hazard pointer count for CDS library.
381 - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
382 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
383 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
386 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
387 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
388 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
389 scan_type nScanType = scan_type::inplace ///< Scan type (see \p scan_type enum)
392 hp::GarbageCollector::Construct(
396 static_cast<hp::scan_type>(nScanType)
400 /// Terminates GC singleton
402 The destructor calls \code hp::GarbageCollector::Destruct( true ) \endcode
406 hp::GarbageCollector::Destruct( true );
409 /// Checks if count of hazard pointer is no less than \p nCountNeeded
411 If \p bRaiseException is \p true (that is the default), the function raises
412 an \p std::overflow_error exception "Too few hazard pointers"
413 if \p nCountNeeded is more than the count of hazard pointer per thread.
415 static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
417 if ( hp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
418 if ( bRaiseException )
419 throw std::overflow_error( "Too few hazard pointers" );
425 /// Returns max Hazard Pointer count
426 static size_t max_hazard_count()
428 return hp::GarbageCollector::instance().getHazardPointerCount();
431 /// Returns max count of thread
432 static size_t max_thread_count()
434 return hp::GarbageCollector::instance().getMaxThreadCount();
437 /// Returns capacity of retired pointer array
438 static size_t retired_array_capacity()
440 return hp::GarbageCollector::instance().getMaxRetiredPtrCount();
443 /// Retire pointer \p p with function \p pFunc
445 The function places pointer \p p to array of pointers ready for removing.
446 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
447 Deleting the pointer is the function \p pFunc call.
449 template <typename T>
450 static void retire( T * p, void (* pFunc)(T *) ) ; // inline in hp_impl.h
452 /// Retire pointer \p p with functor of type \p Disposer
454 The function places pointer \p p to array of pointers ready for removing.
455 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
457 Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
459 template <typename T>
461 void operator()( T * p ) ; // disposing operator
464 Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
465 - it should be stateless functor
466 - it should be default-constructible
467 - the result of functor call with argument \p p should not depend on where the functor will be called.
470 Operator \p delete functor:
472 template <typename T>
474 void operator ()( T * p ) {
479 // How to call GC::retire method
482 // ... use p in lock-free manner
484 cds::gc::HP::retire<disposer>( p ) ; // place p to retired pointer array of HP GC
487 Functor based on \p std::allocator :
489 template <typename ALLOC = std::allocator<int> >
491 template <typename T>
492 void operator()( T * p ) {
493 typedef typename ALLOC::templare rebind<T>::other alloc_t;
496 a.deallocate( p, 1 );
501 template <class Disposer, typename T>
502 static void retire( T * p ) ; // inline in hp_impl.h
504 /// Get current scan strategy
505 static scan_type getScanType()
507 return static_cast<scan_type>( hp::GarbageCollector::instance().getScanType());
510 /// Set current scan strategy
511 static void setScanType(
512 scan_type nScanType ///< new scan strategy
515 hp::GarbageCollector::instance().setScanType( static_cast<hp::scan_type>(nScanType) );
518 /// Checks if Hazard Pointer GC is constructed and may be used
521 return hp::GarbageCollector::isUsed();
524 /// Forced GC cycle call for current thread
526 Usually, this function should not be called directly.
528 static void scan() ; // inline in hp_impl.h
530 /// Synonym for \ref scan()
531 static void force_dispose()
536 }} // namespace cds::gc
538 #endif // #ifndef __CDS_GC_IMPL_HP_DECL_H