2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_GC_IMPL_DHP_DECL_H
32 #define CDSLIB_GC_IMPL_DHP_DECL_H
34 #include <cds/gc/details/dhp.h>
35 #include <cds/details/marked_ptr.h>
36 #include <cds/details/static_functor.h>
38 namespace cds { namespace gc {
40 /// Dynamic Hazard Pointer garbage collector
41 /** @ingroup cds_garbage_collector
42 @headerfile cds/gc/dhp.h
44 Implementation of Dynamic Hazard Pointer garbage collector.
47 - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
48 - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
49 - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
51 Dynamic Hazard Pointers SMR (safe memory reclamation) provides an unbounded number of hazard pointer per thread
52 despite of classic Hazard Pointer SMR in which the count of the hazard pointef per thread is limited.
54 See \ref cds_how_to_use "How to use" section for details how to apply garbage collector.
59 /// Native guarded pointer type
61 @headerfile cds/gc/dhp.h
63 typedef void * guarded_pointer;
67 @headerfile cds/gc/dhp.h
69 template <typename T> using atomic_ref = atomics::atomic<T *>;
73 @headerfile cds/gc/dhp.h
75 template <typename T> using atomic_type = atomics::atomic<T>;
77 /// Atomic marked pointer
79 @headerfile cds/gc/dhp.h
81 template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
83 /// Thread GC implementation for internal usage
85 @headerfile cds/gc/dhp.h
87 typedef dhp::ThreadGC thread_gc_impl;
89 /// Thread-level garbage collector
91 @headerfile cds/gc/dhp.h
92 This class performs automatically attaching/detaching Dynamic Hazard Pointer GC
93 for the current thread.
95 class thread_gc: public thread_gc_impl
103 The constructor attaches the current thread to the Dynamic Hazard Pointer GC
104 if it is not yet attached.
105 The \p bPersistent parameter specifies attachment persistence:
106 - \p true - the class destructor will not detach the thread from Dynamic Hazard Pointer GC.
107 - \p false (default) - the class destructor will detach the thread from Dynamic Hazard Pointer GC.
110 bool bPersistent = false
111 ) ; // inline in dhp_impl.h
115 If the object has been created in persistent mode, the destructor does nothing.
116 Otherwise it detaches the current thread from Dynamic Hazard Pointer GC.
118 ~thread_gc() ; // inline in dhp_impl.h
120 public: // for internal use only!!!
122 static dhp::details::guard_data* alloc_guard(); // inline in dhp_impl.h
123 static void free_guard( dhp::details::guard_data* g ); // inline in dhp_impl.h
128 /// Dynamic Hazard Pointer guard
130 @headerfile cds/gc/dhp.h
132 A guard is the hazard pointer.
133 Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
135 \p %Guard object is movable but not copyable.
137 The guard object can be in two states:
138 - unlinked - the guard is not linked with any internal hazard pointer.
139 In this state no operation except \p link() and move assignment is supported.
140 - linked (default) - the guard allocates an internal hazard pointer and fully operable.
142 Due to performance reason the implementation does not check state of the guard in runtime.
144 @warning Move assignment can transfer the guard in unlinked state, use with care.
149 /// Default ctor allocates a guard (hazard pointer) from thread-private storage
151 : m_guard( thread_gc::alloc_guard())
154 /// Initilalizes an unlinked guard i.e. the guard contains no hazard pointer. Used for move semantics support
155 explicit Guard( std::nullptr_t ) CDS_NOEXCEPT
159 /// Move ctor - \p src guard becomes unlinked (transfer internal guard ownership)
160 Guard( Guard&& src ) CDS_NOEXCEPT
161 : m_guard( src.m_guard )
163 src.m_guard = nullptr;
166 /// Move assignment: the internal guards are swapped between \p src and \p this
168 @warning \p src will become in unlinked state if \p this was unlinked on entry.
170 Guard& operator=( Guard&& src ) CDS_NOEXCEPT
172 std::swap( m_guard, src.m_guard );
176 /// Copy ctor is prohibited - the guard is not copyable
177 Guard( Guard const& ) = delete;
179 /// Copy assignment is prohibited
180 Guard& operator=( Guard const& ) = delete;
185 thread_gc::free_guard( m_guard );
188 /// Checks if the guard object linked with any internal hazard pointer
189 bool is_linked() const
191 return m_guard != nullptr;
194 /// Links the guard with internal hazard pointer if the guard is in unlinked state
198 m_guard = thread_gc::alloc_guard();
201 /// Unlinks the guard from internal hazard pointer; the guard becomes in unlinked state
205 thread_gc::free_guard( m_guard );
210 /// Protects a pointer of type <tt> atomic<T*> </tt>
212 Return the value of \p toGuard
214 The function tries to load \p toGuard and to store it
215 to the HP slot repeatedly until the guard's value equals \p toGuard
217 template <typename T>
218 T protect( atomics::atomic<T> const& toGuard )
220 T pCur = toGuard.load(atomics::memory_order_acquire);
223 pRet = assign( pCur );
224 pCur = toGuard.load(atomics::memory_order_acquire);
225 } while ( pRet != pCur );
229 /// Protects a converted pointer of type <tt> atomic<T*> </tt>
231 Return the value of \p toGuard
233 The function tries to load \p toGuard and to store result of \p f functor
234 to the HP slot repeatedly until the guard's value equals \p toGuard.
236 The function is useful for intrusive containers when \p toGuard is a node pointer
237 that should be converted to a pointer to the value type before guarding.
238 The parameter \p f of type Func is a functor that makes this conversion:
241 value_type * operator()( T * p );
244 Really, the result of <tt> f( toGuard.load()) </tt> is assigned to the hazard pointer.
246 template <typename T, class Func>
247 T protect( atomics::atomic<T> const& toGuard, Func f )
249 T pCur = toGuard.load(atomics::memory_order_acquire);
254 pCur = toGuard.load(atomics::memory_order_acquire);
255 } while ( pRet != pCur );
259 /// Store \p p to the guard
261 The function is just an assignment, no loop is performed.
262 Can be used for a pointer that cannot be changed concurrently
263 or for already guarded pointer.
265 template <typename T>
268 assert( m_guard != nullptr );
269 m_guard->pPost.store( p, atomics::memory_order_release );
274 std::nullptr_t assign( std::nullptr_t )
281 /// Store marked pointer \p p to the guard
283 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
284 Can be used for a marked pointer that cannot be changed concurrently
285 or for already guarded pointer.
287 template <typename T, int BITMASK>
288 T* assign( cds::details::marked_ptr<T, BITMASK> p )
290 return assign( p.ptr());
293 /// Copy from \p src guard to \p this guard
294 void copy( Guard const& src )
296 assign( src.get_native());
299 /// Clears value of the guard
302 assert( m_guard != nullptr );
303 m_guard->pPost.store( nullptr, atomics::memory_order_release );
306 /// Gets the value currently protected (relaxed read)
307 template <typename T>
310 return reinterpret_cast<T *>( get_native());
313 /// Gets native guarded pointer stored
314 void* get_native() const
316 assert( m_guard != nullptr );
317 return m_guard->pPost.load( atomics::memory_order_acquire );
321 dhp::details::guard_data* release()
323 dhp::details::guard_data* g = m_guard;
328 dhp::details::guard_data*& guard_ref()
336 dhp::details::guard_data* m_guard;
340 /// Array of Dynamic Hazard Pointer guards
342 @headerfile cds/gc/dhp.h
343 The class is intended for allocating an array of hazard pointer guards.
344 Template parameter \p Count defines the size of the array.
346 A \p %GuardArray object is not copy- and move-constructible
347 and not copy- and move-assignable.
349 template <size_t Count>
353 /// Rebind array for other size \p OtherCount
354 template <size_t OtherCount>
356 typedef GuardArray<OtherCount> other ; ///< rebinding result
360 static CDS_CONSTEXPR const size_t c_nCapacity = Count;
363 /// Default ctor allocates \p Count hazard pointers
364 GuardArray(); // inline in dhp_impl.h
366 /// Move ctor is prohibited
367 GuardArray( GuardArray&& ) = delete;
369 /// Move assignment is prohibited
370 GuardArray& operator=( GuardArray&& ) = delete;
372 /// Copy ctor is prohibited
373 GuardArray( GuardArray const& ) = delete;
375 /// Copy assignment is prohibited
376 GuardArray& operator=( GuardArray const& ) = delete;
378 /// Frees allocated hazard pointers
379 ~GuardArray(); // inline in dhp_impl.h
381 /// Protects a pointer of type \p atomic<T*>
383 Return the value of \p toGuard
385 The function tries to load \p toGuard and to store it
386 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
388 template <typename T>
389 T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
393 pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire));
394 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
399 /// Protects a pointer of type \p atomic<T*>
401 Return the value of \p toGuard
403 The function tries to load \p toGuard and to store it
404 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
406 The function is useful for intrusive containers when \p toGuard is a node pointer
407 that should be converted to a pointer to the value type before guarding.
408 The parameter \p f of type Func is a functor to make that conversion:
411 value_type * operator()( T * p );
414 Actually, the result of <tt> f( toGuard.load()) </tt> is assigned to the hazard pointer.
416 template <typename T, class Func>
417 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
421 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire)));
422 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
427 /// Store \p p to the slot \p nIndex
429 The function is just an assignment, no loop is performed.
431 template <typename T>
432 T * assign( size_t nIndex, T * p )
434 assert( nIndex < capacity());
435 assert( m_arr[nIndex] != nullptr );
437 m_arr[nIndex]->pPost.store( p, atomics::memory_order_release );
441 /// Store marked pointer \p p to the guard
443 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
444 Can be used for a marked pointer that cannot be changed concurrently
445 or for already guarded pointer.
447 template <typename T, int Bitmask>
448 T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
450 return assign( nIndex, p.ptr());
453 /// Copy guarded value from \p src guard to slot at index \p nIndex
454 void copy( size_t nIndex, Guard const& src )
456 assign( nIndex, src.get_native());
459 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
460 void copy( size_t nDestIndex, size_t nSrcIndex )
462 assign( nDestIndex, get_native( nSrcIndex ));
465 /// Clear value of the slot \p nIndex
466 void clear( size_t nIndex )
468 assert( nIndex < capacity());
469 assert( m_arr[nIndex] != nullptr );
471 m_arr[nIndex]->pPost.store( nullptr, atomics::memory_order_release );
474 /// Get current value of slot \p nIndex
475 template <typename T>
476 T * get( size_t nIndex ) const
478 return reinterpret_cast<T *>( get_native( nIndex ));
481 /// Get native guarded pointer stored
482 guarded_pointer get_native( size_t nIndex ) const
484 assert( nIndex < capacity());
485 assert( m_arr[nIndex] != nullptr );
487 return m_arr[nIndex]->pPost.load( atomics::memory_order_acquire );
491 dhp::details::guard_data* release( size_t nIndex ) CDS_NOEXCEPT
493 assert( nIndex < capacity());
495 dhp::details::guard_data* ret = m_arr[ nIndex ];
496 m_arr[nIndex] = nullptr;
501 /// Capacity of the guard array
502 static CDS_CONSTEXPR size_t capacity()
509 dhp::details::guard_data* m_arr[c_nCapacity];
515 A guarded pointer is a pair of a pointer and GC's guard.
516 Usually, it is used for returning a pointer to the item from an lock-free container.
517 The guard prevents the pointer to be early disposed (freed) by GC.
518 After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
521 - \p GuardedType - a type which the guard stores
522 - \p ValueType - a value type
523 - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
525 For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
526 In such case the \p %guarded_ptr is:
528 typedef cds::gc::DHP::guarded_ptr< foo > intrusive_guarded_ptr;
531 For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
539 struct value_accessor {
540 std::string* operator()( foo* pFoo ) const
542 return &(pFoo->value);
547 typedef cds::gc::DHP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
550 You don't need use this class directly.
551 All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
553 template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
557 struct trivial_cast {
558 ValueType * operator()( GuardedType * p ) const
564 template <typename GT, typename VT, typename C> friend class guarded_ptr;
568 typedef GuardedType guarded_type; ///< Guarded type
569 typedef ValueType value_type; ///< Value type
571 /// Functor for casting \p guarded_type to \p value_type
572 typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
575 /// Creates empty guarded pointer
576 guarded_ptr() CDS_NOEXCEPT
581 explicit guarded_ptr( dhp::details::guard_data* g ) CDS_NOEXCEPT
585 /// Initializes guarded pointer with \p p
586 explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
590 explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
596 guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
597 : m_guard( gp.m_guard )
599 gp.m_guard = nullptr;
603 template <typename GT, typename VT, typename C>
604 guarded_ptr( guarded_ptr<GT, VT, C>&& gp ) CDS_NOEXCEPT
605 : m_guard( gp.m_guard )
607 gp.m_guard = nullptr;
610 /// Ctor from \p Guard
611 explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT
612 : m_guard( g.release())
615 /// The guarded pointer is not copy-constructible
616 guarded_ptr( guarded_ptr const& gp ) = delete;
618 /// Clears the guarded pointer
620 \ref release is called if guarded pointer is not \ref empty
622 ~guarded_ptr() CDS_NOEXCEPT
627 /// Move-assignment operator
628 guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
630 std::swap( m_guard, gp.m_guard );
634 /// Move-assignment from \p Guard
635 guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT
637 std::swap( m_guard, g.guard_ref());
641 /// The guarded pointer is not copy-assignable
642 guarded_ptr& operator=(guarded_ptr const& gp) = delete;
644 /// Returns a pointer to guarded value
645 value_type * operator ->() const CDS_NOEXCEPT
648 return value_cast()( reinterpret_cast<guarded_type *>(m_guard->get()));
651 /// Returns a reference to guarded value
652 value_type& operator *() CDS_NOEXCEPT
655 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard->get()));
658 /// Returns const reference to guarded value
659 value_type const& operator *() const CDS_NOEXCEPT
662 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard->get()));
665 /// Checks if the guarded pointer is \p nullptr
666 bool empty() const CDS_NOEXCEPT
668 return m_guard == nullptr || m_guard->get( atomics::memory_order_relaxed ) == nullptr;
671 /// \p bool operator returns <tt>!empty()</tt>
672 explicit operator bool() const CDS_NOEXCEPT
677 /// Clears guarded pointer
679 If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
680 Dereferncing the guarded pointer after \p release() is dangerous.
682 void release() CDS_NOEXCEPT
688 // For internal use only!!!
689 void reset(guarded_type * p) CDS_NOEXCEPT
703 m_guard = thread_gc::alloc_guard();
709 thread_gc::free_guard( m_guard );
717 dhp::details::guard_data* m_guard;
722 /// Initializes %DHP memory manager singleton
724 Constructor creates and initializes %DHP global object.
725 %DHP object should be created before using CDS data structure based on \p %cds::gc::DHP GC. Usually,
726 it is created in the \p main() function.
727 After creating of global object you may use CDS data structures based on \p %cds::gc::DHP.
730 - \p nLiberateThreshold - \p scan() threshold. When count of retired pointers reaches this value,
731 the \p scan() member function would be called for freeing retired pointers.
732 - \p nInitialThreadGuardCount - initial count of guard allocated for each thread.
733 When a thread is initialized the GC allocates local guard pool for the thread from common guard pool.
734 By perforce the local thread's guard pool is grown automatically from common pool.
735 When the thread terminated its guard pool is backed to common GC's pool.
736 - \p nEpochCount: internally, DHP memory manager uses epoch-based schema to solve
737 ABA problem for internal data. \p nEpochCount specifies the epoch count,
738 i.e. the count of simultaneously working threads that remove the elements
739 of DHP-based concurrent data structure. Default value is 16.
742 size_t nLiberateThreshold = 1024
743 , size_t nInitialThreadGuardCount = 8
744 , size_t nEpochCount = 16
747 dhp::GarbageCollector::Construct( nLiberateThreshold, nInitialThreadGuardCount, nEpochCount );
750 /// Destroys %DHP memory manager
752 The destructor destroys %DHP global object. After calling of this function you may \b NOT
753 use CDS data structures based on \p %cds::gc::DHP.
754 Usually, %DHP object is destroyed at the end of your \p main().
758 dhp::GarbageCollector::Destruct();
761 /// Checks if count of hazard pointer is no less than \p nCountNeeded
763 The function always returns \p true since the guard count is unlimited for
764 \p %gc::DHP garbage collector.
766 static CDS_CONSTEXPR bool check_available_guards(
767 #ifdef CDS_DOXYGEN_INVOKED
772 bool /*bRaiseException*/ = true )
777 /// Retire pointer \p p with function \p pFunc
779 The function places pointer \p p to array of pointers ready for removing.
780 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
781 Deleting the pointer is the function \p pFunc call.
783 template <typename T>
784 static void retire( T * p, void (* pFunc)(T *))
786 dhp::GarbageCollector::instance().retirePtr( p, pFunc );
789 /// Retire pointer \p p with functor of type \p Disposer
791 The function places pointer \p p to array of pointers ready for removing.
792 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
794 See \p gc::HP::retire for \p Disposer requirements.
796 template <class Disposer, typename T>
797 static void retire( T * p )
799 retire( p, cds::details::static_functor<Disposer, T>::call );
802 /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
805 return dhp::GarbageCollector::isUsed();
808 /// Forced GC cycle call for current thread
810 Usually, this function should not be called directly.
812 static void scan() ; // inline in dhp_impl.h
814 /// Synonym for \ref scan()
815 static void force_dispose()
821 }} // namespace cds::gc
823 #endif // #ifndef CDSLIB_GC_IMPL_DHP_DECL_H