2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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;
331 dhp::details::guard_data* m_guard;
335 /// Array of Dynamic Hazard Pointer guards
337 @headerfile cds/gc/dhp.h
338 The class is intended for allocating an array of hazard pointer guards.
339 Template parameter \p Count defines the size of the array.
341 A \p %GuardArray object is not copy- and move-constructible
342 and not copy- and move-assignable.
344 template <size_t Count>
348 /// Rebind array for other size \p OtherCount
349 template <size_t OtherCount>
351 typedef GuardArray<OtherCount> other ; ///< rebinding result
355 static CDS_CONSTEXPR const size_t c_nCapacity = Count;
358 /// Default ctor allocates \p Count hazard pointers
359 GuardArray(); // inline in dhp_impl.h
361 /// Move ctor is prohibited
362 GuardArray( GuardArray&& ) = delete;
364 /// Move assignment is prohibited
365 GuardArray& operator=( GuardArray&& ) = delete;
367 /// Copy ctor is prohibited
368 GuardArray( GuardArray const& ) = delete;
370 /// Copy assignment is prohibited
371 GuardArray& operator=( GuardArray const& ) = delete;
373 /// Frees allocated hazard pointers
374 ~GuardArray(); // inline in dhp_impl.h
376 /// Protects a pointer of type \p atomic<T*>
378 Return the value of \p toGuard
380 The function tries to load \p toGuard and to store it
381 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
383 template <typename T>
384 T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
388 pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire) );
389 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
394 /// Protects a pointer of type \p atomic<T*>
396 Return the value of \p toGuard
398 The function tries to load \p toGuard and to store it
399 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
401 The function is useful for intrusive containers when \p toGuard is a node pointer
402 that should be converted to a pointer to the value type before guarding.
403 The parameter \p f of type Func is a functor to make that conversion:
406 value_type * operator()( T * p );
409 Actually, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
411 template <typename T, class Func>
412 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
416 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire) ));
417 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
422 /// Store \p p to the slot \p nIndex
424 The function is just an assignment, no loop is performed.
426 template <typename T>
427 T * assign( size_t nIndex, T * p )
429 assert( nIndex < capacity());
430 assert( m_arr[nIndex] != nullptr );
432 m_arr[nIndex]->pPost.store( p, atomics::memory_order_release );
436 /// Store marked pointer \p p to the guard
438 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
439 Can be used for a marked pointer that cannot be changed concurrently
440 or for already guarded pointer.
442 template <typename T, int Bitmask>
443 T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
445 return assign( nIndex, p.ptr() );
448 /// Copy guarded value from \p src guard to slot at index \p nIndex
449 void copy( size_t nIndex, Guard const& src )
451 assign( nIndex, src.get_native() );
454 /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
455 void copy( size_t nDestIndex, size_t nSrcIndex )
457 assign( nDestIndex, get_native( nSrcIndex ));
460 /// Clear value of the slot \p nIndex
461 void clear( size_t nIndex )
463 assert( nIndex < capacity() );
464 assert( m_arr[nIndex] != nullptr );
466 m_arr[nIndex]->pPost.store( nullptr, atomics::memory_order_release );
469 /// Get current value of slot \p nIndex
470 template <typename T>
471 T * get( size_t nIndex ) const
473 return reinterpret_cast<T *>( get_native( nIndex ) );
476 /// Get native guarded pointer stored
477 guarded_pointer get_native( size_t nIndex ) const
479 assert( nIndex < capacity() );
480 assert( m_arr[nIndex] != nullptr );
482 return m_arr[nIndex]->pPost.load( atomics::memory_order_acquire );
486 dhp::details::guard_data* release( size_t nIndex ) CDS_NOEXCEPT
488 assert( nIndex < capacity() );
490 dhp::details::guard_data* ret = m_arr[ nIndex ];
491 m_arr[nIndex] = nullptr;
496 /// Capacity of the guard array
497 static CDS_CONSTEXPR size_t capacity()
504 dhp::details::guard_data* m_arr[c_nCapacity];
510 A guarded pointer is a pair of a pointer and GC's guard.
511 Usually, it is used for returning a pointer to the item from an lock-free container.
512 The guard prevents the pointer to be early disposed (freed) by GC.
513 After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
516 - \p GuardedType - a type which the guard stores
517 - \p ValueType - a value type
518 - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
520 For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
521 In such case the \p %guarded_ptr is:
523 typedef cds::gc::DHP::guarded_ptr< foo > intrusive_guarded_ptr;
526 For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
534 struct value_accessor {
535 std::string* operator()( foo* pFoo ) const
537 return &(pFoo->value);
542 typedef cds::gc::DHP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
545 You don't need use this class directly.
546 All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
548 template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
552 struct trivial_cast {
553 ValueType * operator()( GuardedType * p ) const
559 template <typename GT, typename VT, typename C> friend class guarded_ptr;
563 typedef GuardedType guarded_type; ///< Guarded type
564 typedef ValueType value_type; ///< Value type
566 /// Functor for casting \p guarded_type to \p value_type
567 typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
570 /// Creates empty guarded pointer
571 guarded_ptr() CDS_NOEXCEPT
576 explicit guarded_ptr( dhp::details::guard_data* g ) CDS_NOEXCEPT
580 /// Initializes guarded pointer with \p p
581 explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
585 explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
591 guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
592 : m_guard( gp.m_guard )
594 gp.m_guard = nullptr;
598 template <typename GT, typename VT, typename C>
599 guarded_ptr( guarded_ptr<GT, VT, C>&& gp ) CDS_NOEXCEPT
600 : m_guard( gp.m_guard )
602 gp.m_guard = nullptr;
605 /// Ctor from \p Guard
606 explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT
607 : m_guard( g.release() )
610 /// The guarded pointer is not copy-constructible
611 guarded_ptr( guarded_ptr const& gp ) = delete;
613 /// Clears the guarded pointer
615 \ref release is called if guarded pointer is not \ref empty
617 ~guarded_ptr() CDS_NOEXCEPT
622 /// Move-assignment operator
623 guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
625 std::swap( m_guard, gp.m_guard );
629 /// Move-assignment from \p Guard
630 guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT
632 std::swap( m_guard, g.m_guard );
636 /// The guarded pointer is not copy-assignable
637 guarded_ptr& operator=(guarded_ptr const& gp) = delete;
639 /// Returns a pointer to guarded value
640 value_type * operator ->() const CDS_NOEXCEPT
643 return value_cast()( reinterpret_cast<guarded_type *>(m_guard->get()));
646 /// Returns a reference to guarded value
647 value_type& operator *() CDS_NOEXCEPT
650 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard->get()));
653 /// Returns const reference to guarded value
654 value_type const& operator *() const CDS_NOEXCEPT
657 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard->get()));
660 /// Checks if the guarded pointer is \p nullptr
661 bool empty() const CDS_NOEXCEPT
663 return m_guard == nullptr || m_guard->get( atomics::memory_order_relaxed ) == nullptr;
666 /// \p bool operator returns <tt>!empty()</tt>
667 explicit operator bool() const CDS_NOEXCEPT
672 /// Clears guarded pointer
674 If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
675 Dereferncing the guarded pointer after \p release() is dangerous.
677 void release() CDS_NOEXCEPT
683 // For internal use only!!!
684 void reset(guarded_type * p) CDS_NOEXCEPT
698 m_guard = thread_gc::alloc_guard();
704 thread_gc::free_guard( m_guard );
712 dhp::details::guard_data* m_guard;
717 /// Initializes %DHP memory manager singleton
719 Constructor creates and initializes %DHP global object.
720 %DHP object should be created before using CDS data structure based on \p %cds::gc::DHP GC. Usually,
721 it is created in the \p main() function.
722 After creating of global object you may use CDS data structures based on \p %cds::gc::DHP.
725 - \p nLiberateThreshold - \p scan() threshold. When count of retired pointers reaches this value,
726 the \p scan() member function would be called for freeing retired pointers.
727 - \p nInitialThreadGuardCount - initial count of guard allocated for each thread.
728 When a thread is initialized the GC allocates local guard pool for the thread from common guard pool.
729 By perforce the local thread's guard pool is grown automatically from common pool.
730 When the thread terminated its guard pool is backed to common GC's pool.
731 - \p nEpochCount: internally, DHP memory manager uses epoch-based schema to solve
732 ABA problem for internal data. \p nEpochCount specifies the epoch count,
733 i.e. the count of simultaneously working threads that remove the elements
734 of DHP-based concurrent data structure. Default value is 16.
737 size_t nLiberateThreshold = 1024
738 , size_t nInitialThreadGuardCount = 8
739 , size_t nEpochCount = 16
742 dhp::GarbageCollector::Construct( nLiberateThreshold, nInitialThreadGuardCount, nEpochCount );
745 /// Destroys %DHP memory manager
747 The destructor destroys %DHP global object. After calling of this function you may \b NOT
748 use CDS data structures based on \p %cds::gc::DHP.
749 Usually, %DHP object is destroyed at the end of your \p main().
753 dhp::GarbageCollector::Destruct();
756 /// Checks if count of hazard pointer is no less than \p nCountNeeded
758 The function always returns \p true since the guard count is unlimited for
759 \p %gc::DHP garbage collector.
761 static CDS_CONSTEXPR bool check_available_guards(
762 #ifdef CDS_DOXYGEN_INVOKED
767 bool /*bRaiseException*/ = true )
772 /// Retire pointer \p p with function \p pFunc
774 The function places pointer \p p to array of pointers ready for removing.
775 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
776 Deleting the pointer is the function \p pFunc call.
778 template <typename T>
779 static void retire( T * p, void (* pFunc)(T *) )
781 dhp::GarbageCollector::instance().retirePtr( p, pFunc );
784 /// Retire pointer \p p with functor of type \p Disposer
786 The function places pointer \p p to array of pointers ready for removing.
787 (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
789 See \p gc::HP::retire for \p Disposer requirements.
791 template <class Disposer, typename T>
792 static void retire( T * p )
794 retire( p, cds::details::static_functor<Disposer, T>::call );
797 /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
800 return dhp::GarbageCollector::isUsed();
803 /// Forced GC cycle call for current thread
805 Usually, this function should not be called directly.
807 static void scan() ; // inline in dhp_impl.h
809 /// Synonym for \ref scan()
810 static void force_dispose()
816 }} // namespace cds::gc
818 #endif // #ifndef CDSLIB_GC_IMPL_DHP_DECL_H