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_HP_SMR_H
32 #define CDSLIB_GC_HP_SMR_H
35 #include <cds/gc/details/hp_common.h>
36 #include <cds/details/lib.h>
37 #include <cds/threading/model.h>
38 #include <cds/details/throw_exception.h>
39 #include <cds/details/static_functor.h>
40 #include <cds/details/marked_ptr.h>
41 #include <cds/user_setup/cache_line.h>
44 @page cds_garbage_collectors_comparison Hazard Pointer SMR implementations
45 @ingroup cds_garbage_collector
51 <th>%cds::gc::DHP</th>
54 <td>Max number of guarded (hazard) pointers per thread</td>
55 <td>limited (specified at construction time)</td>
56 <td>unlimited (dynamically allocated when needed)</td>
59 <td>Max number of retired pointers<sup>1</sup></td>
60 <td>bounded, specified at construction time</td>
61 <td>bounded, adaptive, depends on current thread count and number of hazard pointer for each thread</td>
65 <td>bounded, upper bound is specified at construction time</td>
70 <sup>1</sup>Unbounded count of retired pointers means a possibility of memory exhaustion.
74 /// @defgroup cds_garbage_collector Garbage collectors
77 /// Different safe memory reclamation schemas (garbage collectors)
78 /** @ingroup cds_garbage_collector
80 This namespace specifies different safe memory reclamation (SMR) algorithms.
81 See \ref cds_garbage_collector "Garbage collectors"
89 namespace cds { namespace gc {
90 /// Hazard pointer implementation details
92 using namespace cds::gc::hp::common;
94 /// Exception "Not enough Hazard Pointer"
95 class not_enought_hazard_ptr: public std::length_error
99 not_enought_hazard_ptr()
100 : std::length_error( "Not enough Hazard Pointer" )
105 /// Exception "Hazard Pointer SMR is not initialized"
106 class not_initialized: public std::runtime_error
111 : std::runtime_error( "Global Hazard Pointer SMR object is not initialized" )
117 /// Per-thread hazard pointer storage
118 class thread_hp_storage {
120 thread_hp_storage( guard* arr, size_t nSize ) CDS_NOEXCEPT
124 # ifdef CDS_ENABLE_HPSTAT
125 , alloc_guard_count_(0)
126 , free_guard_count_(0)
130 new( arr ) guard[nSize];
132 for ( guard* pEnd = arr + nSize - 1; arr < pEnd; ++arr )
133 arr->next_ = arr + 1;
134 arr->next_ = nullptr;
137 thread_hp_storage() = delete;
138 thread_hp_storage( thread_hp_storage const& ) = delete;
139 thread_hp_storage( thread_hp_storage&& ) = delete;
141 size_t capacity() const CDS_NOEXCEPT
146 bool full() const CDS_NOEXCEPT
148 return free_head_ == nullptr;
153 # ifdef CDS_DISABLE_SMR_EXCEPTION
157 CDS_THROW_EXCEPTION( not_enought_hazard_ptr());
159 guard* g = free_head_;
160 free_head_ = g->next_;
161 CDS_HPSTAT( ++alloc_guard_count_ );
165 void free( guard* g ) CDS_NOEXCEPT
167 assert( g >= array_ && g < array_ + capacity() );
171 g->next_ = free_head_;
173 CDS_HPSTAT( ++free_guard_count_ );
177 template< size_t Capacity>
178 size_t alloc( guard_array<Capacity>& arr )
181 guard* g = free_head_;
182 for ( i = 0; i < Capacity && g; ++i ) {
187 # ifdef CDS_DISABLE_SMR_EXCEPTION
188 assert( i == Capacity );
191 CDS_THROW_EXCEPTION( not_enought_hazard_ptr());
194 CDS_HPSTAT( alloc_guard_count_ += Capacity );
198 template <size_t Capacity>
199 void free( guard_array<Capacity>& arr ) CDS_NOEXCEPT
201 guard* gList = free_head_;
202 for ( size_t i = 0; i < Capacity; ++i ) {
208 CDS_HPSTAT( ++free_guard_count_ );
214 // cppcheck-suppress functionConst
217 for ( guard* cur = array_, *last = array_ + capacity(); cur < last; ++cur )
221 guard& operator[]( size_t idx )
223 assert( idx < capacity() );
228 static size_t calc_array_size( size_t capacity )
230 return sizeof( guard ) * capacity;
234 guard* free_head_; ///< Head of free guard list
235 guard* const array_; ///< HP array
236 size_t const capacity_; ///< HP array capacity
237 # ifdef CDS_ENABLE_HPSTAT
239 size_t alloc_guard_count_;
240 size_t free_guard_count_;
246 /// Per-thread retired array
250 retired_array( retired_ptr* arr, size_t capacity ) CDS_NOEXCEPT
252 , last_( arr + capacity )
254 # ifdef CDS_ENABLE_HPSTAT
255 , retire_call_count_(0)
259 retired_array() = delete;
260 retired_array( retired_array const& ) = delete;
261 retired_array( retired_array&& ) = delete;
263 size_t capacity() const CDS_NOEXCEPT
265 return last_ - retired_;
268 size_t size() const CDS_NOEXCEPT
270 return current_ - retired_;
273 bool push( retired_ptr&& p ) CDS_NOEXCEPT
276 CDS_HPSTAT( ++retire_call_count_ );
277 return ++current_ < last_;
280 retired_ptr* first() const CDS_NOEXCEPT
285 retired_ptr* last() const CDS_NOEXCEPT
290 void reset( size_t nSize ) CDS_NOEXCEPT
292 current_ = first() + nSize;
295 bool full() const CDS_NOEXCEPT
297 return current_ == last_;
300 static size_t calc_array_size( size_t capacity )
302 return sizeof( retired_ptr ) * capacity;
306 retired_ptr* current_;
307 retired_ptr* const last_;
308 retired_ptr* const retired_;
309 # ifdef CDS_ENABLE_HPSTAT
311 size_t retire_call_count_;
316 /// Internal statistics
318 size_t guard_allocated; ///< Count of allocated HP guards
319 size_t guard_freed; ///< Count of freed HP guards
320 size_t retired_count; ///< Count of retired pointers
321 size_t free_count; ///< Count of free pointers
322 size_t scan_count; ///< Count of \p scan() call
323 size_t help_scan_count; ///< Count of \p help_scan() call
325 size_t thread_rec_count; ///< Count of thread records
333 /// Clears all counters
342 thread_rec_count = 0;
349 thread_hp_storage hazards_; ///< Hazard pointers private to the thread
350 retired_array retired_; ///< Retired data private to the thread
352 char pad1_[cds::c_nCacheLineSize];
353 atomics::atomic<unsigned int> sync_; ///< dummy var to introduce synchronizes-with relationship between threads
354 char pad2_[cds::c_nCacheLineSize];
356 # ifdef CDS_ENABLE_HPSTAT
357 // Internal statistics:
360 size_t help_scan_count_;
363 // CppCheck warn: pad1_ and pad2_ is uninitialized in ctor
364 // cppcheck-suppress uninitMemberVar
365 thread_data( guard* guards, size_t guard_count, retired_ptr* retired_arr, size_t retired_capacity )
366 : hazards_( guards, guard_count )
367 , retired_( retired_arr, retired_capacity )
369 # ifdef CDS_ENABLE_HPSTAT
372 , help_scan_count_(0)
376 thread_data() = delete;
377 thread_data( thread_data const& ) = delete;
378 thread_data( thread_data&& ) = delete;
382 sync_.fetch_add( 1, atomics::memory_order_acq_rel );
387 /// \p smr::scan() strategy
389 classic, ///< classic scan as described in Michael's works (see smr::classic_scan() )
390 inplace ///< inplace scan without allocation (see smr::inplace_scan() )
394 /// Hazard Pointer SMR (Safe Memory Reclamation)
397 struct thread_record;
400 /// Returns the instance of Hazard Pointer \ref smr
401 static smr& instance()
403 # ifdef CDS_DISABLE_SMR_EXCEPTION
404 assert( instance_ != nullptr );
407 CDS_THROW_EXCEPTION( not_initialized());
412 /// Creates Hazard Pointer SMR singleton
414 Hazard Pointer SMR is a singleton. If HP instance is not initialized then the function creates the instance.
415 Otherwise it does nothing.
417 The Michael's HP reclamation schema depends of three parameters:
418 - \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
419 the data structure algorithms. By default, if \p nHazardPtrCount = 0,
420 the function uses maximum of HP count for CDS library
421 - \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
422 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
423 <tt> nHazardPtrCount * nMaxThreadCount </tt>
424 Default is <tt>2 * nHazardPtrCount * nMaxThreadCount</tt>
426 static CDS_EXPORT_API void construct(
427 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
428 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
429 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
430 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
433 // for back-copatibility
434 static void Construct(
435 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
436 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
437 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
438 scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum)
441 construct( nHazardPtrCount, nMaxThreadCount, nMaxRetiredPtrCount, nScanType );
444 /// Destroys global instance of \ref smr
446 The parameter \p bDetachAll should be used carefully: if its value is \p true,
447 then the object destroyed automatically detaches all attached threads. This feature
448 can be useful when you have no control over the thread termination, for example,
449 when \p libcds is injected into existing external thread.
451 static CDS_EXPORT_API void destruct(
452 bool bDetachAll = false ///< Detach all threads
455 // for back-compatibility
456 static void Destruct(
457 bool bDetachAll = false ///< Detach all threads
460 destruct( bDetachAll );
463 /// Checks if global SMR object is constructed and may be used
464 static bool isUsed() CDS_NOEXCEPT
466 return instance_ != nullptr;
469 /// Set memory management functions
471 @note This function may be called <b>BEFORE</b> creating an instance
472 of Hazard Pointer SMR
474 SMR object allocates some memory for thread-specific data and for
476 By default, a standard \p new and \p delete operators are used for this.
478 static CDS_EXPORT_API void set_memory_allocator(
479 void* ( *alloc_func )( size_t size ),
480 void (*free_func )( void * p )
483 /// Returns max Hazard Pointer count per thread
484 size_t get_hazard_ptr_count() const CDS_NOEXCEPT
486 return hazard_ptr_count_;
489 /// Returns max thread count
490 size_t get_max_thread_count() const CDS_NOEXCEPT
492 return max_thread_count_;
495 /// Returns max size of retired objects array
496 size_t get_max_retired_ptr_count() const CDS_NOEXCEPT
498 return max_retired_ptr_count_;
501 /// Get current scan strategy
502 scan_type get_scan_type() const
507 /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
509 If <tt> nRequiredCount > get_hazard_ptr_count()</tt> then the exception \p not_enought_hazard_ptr is thrown
511 static void check_hazard_ptr_count( size_t nRequiredCount )
513 if ( instance().get_hazard_ptr_count() < nRequiredCount ) {
514 # ifdef CDS_DISABLE_SMR_EXCEPTION
515 assert( false ); // not enough hazard ptr
517 CDS_THROW_EXCEPTION( not_enought_hazard_ptr() );
522 /// Returns thread-local data for the current thread
523 static CDS_EXPORT_API thread_data* tls();
525 static CDS_EXPORT_API void attach_thread();
526 static CDS_EXPORT_API void detach_thread();
528 /// Get internal statistics
529 CDS_EXPORT_API void statistics( stat& st );
531 public: // for internal use only
532 /// The main garbage collecting function
534 This function is called internally when upper bound of thread's list of reclaimed pointers
537 There are the following scan algorithm:
538 - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use
539 - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory
541 Use \p set_scan_type() member function to setup appropriate scan algorithm.
543 void scan( thread_data* pRec )
545 ( this->*scan_func_ )( pRec );
548 /// Helper scan routine
550 The function guarantees that every node that is eligible for reuse is eventually freed, barring
551 thread failures. To do so, after executing \p scan(), a thread executes a \p %help_scan(),
552 where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
553 to thread's list of reclaimed pointers.
555 The function is called internally by \p scan().
557 CDS_EXPORT_API void help_scan( thread_data* pThis );
561 size_t nHazardPtrCount, ///< Hazard pointer count per thread
562 size_t nMaxThreadCount, ///< Max count of simultaneous working thread in your application
563 size_t nMaxRetiredPtrCount, ///< Capacity of the array of retired objects for the thread
564 scan_type nScanType ///< Scan type (see \ref scan_type enum)
567 CDS_EXPORT_API ~smr();
569 CDS_EXPORT_API void detach_all_thread();
571 /// Classic scan algorithm
572 /** @anchor hzp_gc_classic_scan
573 Classical scan algorithm as described in Michael's paper.
575 A scan includes four stages. The first stage involves scanning the array HP for non-null values.
576 Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer.
577 Only stage 1 accesses shared variables. The following stages operate only on private variables.
579 The second stage of a scan involves sorting local list of protected pointers to allow
580 binary search in the third stage.
582 The third stage of a scan involves checking each reclaimed node
583 against the pointers in local list of protected pointers. If the binary search yields
584 no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list
585 of reclaimed pointers.
587 The forth stage prepares new thread's private list of reclaimed pointers
588 that could not be freed during the current scan, where they remain until the next scan.
590 This algorithm allocates memory for internal HP array.
592 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
595 CDS_EXPORT_API void classic_scan( thread_data* pRec );
597 /// In-place scan algorithm
598 /** @anchor hzp_gc_inplace_scan
599 Unlike the \p classic_scan() algorithm, \p %inplace_scan() does not allocate any memory.
600 All operations are performed in-place.
602 CDS_EXPORT_API void inplace_scan( thread_data* pRec );
605 CDS_EXPORT_API thread_record* create_thread_data();
606 static CDS_EXPORT_API void destroy_thread_data( thread_record* pRec );
608 /// Allocates Hazard Pointer SMR thread private data
609 CDS_EXPORT_API thread_record* alloc_thread_data();
611 /// Free HP SMR thread-private data
612 CDS_EXPORT_API void free_thread_data( thread_record* pRec );
615 static CDS_EXPORT_API smr* instance_;
617 atomics::atomic< thread_record*> thread_list_; ///< Head of thread list
619 size_t const hazard_ptr_count_; ///< max count of thread's hazard pointer
620 size_t const max_thread_count_; ///< max count of thread
621 size_t const max_retired_ptr_count_; ///< max count of retired ptr per thread
622 scan_type const scan_type_; ///< scan type (see \ref scan_type enum)
623 void ( smr::*scan_func_ )( thread_data* pRec );
628 // for backward compatibility
629 typedef smr GarbageCollector;
634 /// Hazard Pointer SMR (Safe Memory Reclamation)
635 /** @ingroup cds_garbage_collector
637 Implementation of classic Hazard Pointer SMR
640 - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
641 - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
642 - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
644 Hazard Pointer SMR is a singleton. The main user-level part of Hazard Pointer schema is
645 \p %cds::gc::HP class and its nested classes. Before use any HP-related class you must initialize \p %HP
646 by contructing \p %cds::gc::HP object in beginning of your \p main().
647 See \ref cds_how_to_use "How to use" section for details how to apply SMR schema.
652 /// Native guarded pointer type
653 typedef hp::hazard_ptr guarded_pointer;
656 template <typename T> using atomic_ref = atomics::atomic<T *>;
658 /// Atomic marked pointer
659 template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
662 template <typename T> using atomic_type = atomics::atomic<T>;
664 /// Exception "Not enough Hazard Pointer"
665 typedef hp::not_enought_hazard_ptr not_enought_hazard_ptr_exception;
667 /// Internal statistics
668 typedef hp::stat stat;
670 /// Hazard Pointer guard
672 A guard is a hazard pointer.
673 Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer.
675 \p %Guard object is movable but not copyable.
677 The guard object can be in two states:
678 - unlinked - the guard is not linked with any internal hazard pointer.
679 In this state no operation except \p link() and move assignment is supported.
680 - linked (default) - the guard allocates an internal hazard pointer and completely operable.
682 Due to performance reason the implementation does not check state of the guard in runtime.
684 @warning Move assignment transfers the guard in unlinked state, use with care.
689 /// Default ctor allocates a guard (hazard pointer) from thread-private storage
691 @warning Can throw \p too_many_hazard_ptr_exception if internal hazard pointer objects are exhausted.
694 : guard_( hp::smr::tls()->hazards_.alloc() )
697 /// Initilalizes an unlinked guard i.e. the guard contains no hazard pointer. Used for move semantics support
698 explicit Guard( std::nullptr_t ) CDS_NOEXCEPT
702 /// Move ctor - \p src guard becomes unlinked (transfer internal guard ownership)
703 Guard( Guard&& src ) CDS_NOEXCEPT
704 : guard_( src.guard_ )
706 src.guard_ = nullptr;
709 /// Move assignment: the internal guards are swapped between \p src and \p this
711 @warning \p src will become in unlinked state if \p this was unlinked on entry.
713 Guard& operator=( Guard&& src ) CDS_NOEXCEPT
715 std::swap( guard_, src.guard_ );
719 /// Copy ctor is prohibited - the guard is not copyable
720 Guard( Guard const& ) = delete;
722 /// Copy assignment is prohibited
723 Guard& operator=( Guard const& ) = delete;
725 /// Frees the internal hazard pointer if the guard is in linked state
731 /// Checks if the guard object linked with any internal hazard pointer
732 bool is_linked() const
734 return guard_ != nullptr;
737 /// Links the guard with internal hazard pointer if the guard is in unlinked state
739 @warning Can throw \p not_enought_hazard_ptr_exception if internal hazard pointer array is exhausted.
744 guard_ = hp::smr::tls()->hazards_.alloc();
747 /// Unlinks the guard from internal hazard pointer; the guard becomes in unlinked state
751 hp::smr::tls()->hazards_.free( guard_ );
756 /// Protects a pointer of type \p atomic<T*>
758 Return the value of \p toGuard
760 The function tries to load \p toGuard and to store it
761 to the HP slot repeatedly until the guard's value equals \p toGuard
763 @warning The guad object should be in linked state, otherwise the result is undefined
765 template <typename T>
766 T protect( atomics::atomic<T> const& toGuard )
768 assert( guard_ != nullptr );
770 T pCur = toGuard.load(atomics::memory_order_acquire);
773 pRet = assign( pCur );
774 pCur = toGuard.load(atomics::memory_order_acquire);
775 } while ( pRet != pCur );
779 /// Protects a converted pointer of type \p atomic<T*>
781 Return the value of \p toGuard
783 The function tries to load \p toGuard and to store result of \p f functor
784 to the HP slot repeatedly until the guard's value equals \p toGuard.
786 The function is useful for intrusive containers when \p toGuard is a node pointer
787 that should be converted to a pointer to the value before protecting.
788 The parameter \p f of type Func is a functor that makes this conversion:
791 value_type * operator()( T * p );
794 Actually, the result of <tt> f( toGuard.load()) </tt> is assigned to the hazard pointer.
796 @warning The guad object should be in linked state, otherwise the result is undefined
798 template <typename T, class Func>
799 T protect( atomics::atomic<T> const& toGuard, Func f )
801 assert( guard_ != nullptr );
803 T pCur = toGuard.load(atomics::memory_order_acquire);
808 pCur = toGuard.load(atomics::memory_order_acquire);
809 } while ( pRet != pCur );
813 /// Store \p p to the guard
815 The function equals to a simple assignment the value \p p to guard, no loop is performed.
816 Can be used for a pointer that cannot be changed concurrently or if the pointer is already
817 guarded by another guard.
819 @warning The guad object should be in linked state, otherwise the result is undefined
821 template <typename T>
824 assert( guard_ != nullptr );
827 hp::smr::tls()->sync();
832 std::nullptr_t assign( std::nullptr_t )
834 assert( guard_ != nullptr );
841 /// Copy a value guarded from \p src guard to \p this guard (valid only in linked state)
842 void copy( Guard const& src )
844 assign( src.get_native());
847 /// Store marked pointer \p p to the guard
849 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
850 Can be used for a marked pointer that cannot be changed concurrently or if the marked pointer
851 is already guarded by another guard.
853 @warning The guard object should be in linked state, otherwise the result is undefined
855 template <typename T, int BITMASK>
856 T * assign( cds::details::marked_ptr<T, BITMASK> p )
858 return assign( p.ptr());
861 /// Clear value of the guard (valid only in linked state)
867 /// Get the value currently protected (valid only in linked state)
868 template <typename T>
871 assert( guard_ != nullptr );
872 return guard_->get_as<T>();
875 /// Get native hazard pointer stored (valid only in linked state)
876 guarded_pointer get_native() const
878 assert( guard_ != nullptr );
879 return guard_->get();
885 hp::guard* g = guard_;
890 hp::guard*& guard_ref()
902 /// Array of Hazard Pointer guards
904 The class is intended for allocating an array of hazard pointer guards.
905 Template parameter \p Count defines the size of the array.
907 template <size_t Count>
911 /// Rebind array for other size \p Count2
912 template <size_t Count2>
914 typedef GuardArray<Count2> other; ///< rebinding result
918 static CDS_CONSTEXPR const size_t c_nCapacity = Count;
921 /// Default ctor allocates \p Count hazard pointers
924 hp::smr::tls()->hazards_.alloc( guards_ );
927 /// Move ctor is prohibited
928 GuardArray( GuardArray&& ) = delete;
930 /// Move assignment is prohibited
931 GuardArray& operator=( GuardArray&& ) = delete;
933 /// Copy ctor is prohibited
934 GuardArray( GuardArray const& ) = delete;
936 /// Copy assignment is prohibited
937 GuardArray& operator=( GuardArray const& ) = delete;
939 /// Frees allocated hazard pointers
942 hp::smr::tls()->hazards_.free( guards_ );
945 /// Protects a pointer of type \p atomic<T*>
947 Return the value of \p toGuard
949 The function tries to load \p toGuard and to store it
950 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
952 template <typename T>
953 T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
955 assert( nIndex < capacity());
959 pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire));
960 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
965 /// Protects a pointer of type \p atomic<T*>
967 Return the value of \p toGuard
969 The function tries to load \p toGuard and to store it
970 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
972 The function is useful for intrusive containers when \p toGuard is a node pointer
973 that should be converted to a pointer to the value type before guarding.
974 The parameter \p f of type Func is a functor that makes this conversion:
977 value_type * operator()( T * p );
980 Really, the result of <tt> f( toGuard.load()) </tt> is assigned to the hazard pointer.
982 template <typename T, class Func>
983 T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
985 assert( nIndex < capacity());
989 assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire)));
990 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
995 /// Store \p to the slot \p nIndex
997 The function equals to a simple assignment, no loop is performed.
999 template <typename T>
1000 T * assign( size_t nIndex, T * p )
1002 assert( nIndex < capacity() );
1004 guards_.set( nIndex, p );
1005 hp::smr::tls()->sync();
1009 /// Store marked pointer \p p to the guard
1011 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
1012 Can be used for a marked pointer that cannot be changed concurrently.
1014 template <typename T, int BITMASK>
1015 T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p )
1017 return assign( nIndex, p.ptr());
1020 /// Copy guarded value from \p src guard to slot at index \p nIndex
1021 void copy( size_t nIndex, Guard const& src )
1023 assign( nIndex, src.get_native());
1026 /// Copy guarded value from slot \p nSrcIndex to the slot \p nDestIndex
1027 void copy( size_t nDestIndex, size_t nSrcIndex )
1029 assign( nDestIndex, get_native( nSrcIndex ));
1032 /// Clear value of the slot \p nIndex
1033 void clear( size_t nIndex )
1035 guards_.clear( nIndex );
1038 /// Get current value of slot \p nIndex
1039 template <typename T>
1040 T * get( size_t nIndex ) const
1042 assert( nIndex < capacity() );
1043 return guards_[nIndex]->template get_as<T>();
1046 /// Get native hazard pointer stored
1047 guarded_pointer get_native( size_t nIndex ) const
1049 assert( nIndex < capacity());
1050 return guards_[nIndex]->get();
1054 hp::guard* release( size_t nIndex ) CDS_NOEXCEPT
1056 return guards_.release( nIndex );
1060 /// Capacity of the guard array
1061 static CDS_CONSTEXPR size_t capacity()
1068 hp::guard_array<c_nCapacity> guards_;
1074 A guarded pointer is a pair of a pointer and GC's guard.
1075 Usually, it is used for returning a pointer to an element of a lock-free container.
1076 The guard prevents the pointer to be early disposed (freed) by SMR.
1077 After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
1080 - \p GuardedType - a type which the guard stores
1081 - \p ValueType - a value type
1082 - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
1084 For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
1085 In such case the \p %guarded_ptr is:
1087 typedef cds::gc::HP::guarded_ptr< foo > intrusive_guarded_ptr;
1090 For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
1098 struct value_accessor {
1099 std::string* operator()( foo* pFoo ) const
1101 return &(pFoo->value);
1106 typedef cds::gc::HP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
1109 You don't need use this class directly.
1110 All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
1112 template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
1116 struct trivial_cast {
1117 ValueType * operator()( GuardedType * p ) const
1123 template <typename GT, typename VT, typename C> friend class guarded_ptr;
1127 typedef GuardedType guarded_type; ///< Guarded type
1128 typedef ValueType value_type; ///< Value type
1130 /// Functor for casting \p guarded_type to \p value_type
1131 typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
1134 /// Creates empty guarded pointer
1135 guarded_ptr() CDS_NOEXCEPT
1140 explicit guarded_ptr( hp::guard* g ) CDS_NOEXCEPT
1144 /// Initializes guarded pointer with \p p
1145 explicit guarded_ptr( guarded_type* p ) CDS_NOEXCEPT
1150 explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
1156 guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
1157 : guard_( gp.guard_ )
1159 gp.guard_ = nullptr;
1163 template <typename GT, typename VT, typename C>
1164 guarded_ptr( guarded_ptr<GT, VT, C>&& gp ) CDS_NOEXCEPT
1165 : guard_( gp.guard_ )
1167 gp.guard_ = nullptr;
1170 /// Ctor from \p Guard
1171 explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT
1172 : guard_( g.release())
1175 /// The guarded pointer is not copy-constructible
1176 guarded_ptr( guarded_ptr const& gp ) = delete;
1178 /// Clears the guarded pointer
1180 \ref release() is called if guarded pointer is not \ref empty()
1182 ~guarded_ptr() CDS_NOEXCEPT
1187 /// Move-assignment operator
1188 guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
1190 std::swap( guard_, gp.guard_ );
1194 /// Move-assignment from \p Guard
1195 guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT
1197 std::swap( guard_, g.guard_ref());
1201 /// The guarded pointer is not copy-assignable
1202 guarded_ptr& operator=(guarded_ptr const& gp) = delete;
1204 /// Returns a pointer to guarded value
1205 value_type * operator ->() const CDS_NOEXCEPT
1208 return value_cast()( guard_->get_as<guarded_type>());
1211 /// Returns a reference to guarded value
1212 value_type& operator *() CDS_NOEXCEPT
1215 return *value_cast()( guard_->get_as<guarded_type>());
1218 /// Returns const reference to guarded value
1219 value_type const& operator *() const CDS_NOEXCEPT
1222 return *value_cast()( guard_->get_as<guarded_type>());
1225 /// Checks if the guarded pointer is \p nullptr
1226 bool empty() const CDS_NOEXCEPT
1228 return !guard_ || guard_->get( atomics::memory_order_relaxed ) == nullptr;
1231 /// \p bool operator returns <tt>!empty()</tt>
1232 explicit operator bool() const CDS_NOEXCEPT
1237 /// Clears guarded pointer
1239 If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
1240 Dereferncing the guarded pointer after \p release() is dangerous.
1242 void release() CDS_NOEXCEPT
1248 // For internal use only!!!
1249 void reset(guarded_type * p) CDS_NOEXCEPT
1262 guard_ = hp::smr::tls()->hazards_.alloc();
1268 hp::smr::tls()->hazards_.free( guard_ );
1282 enum class scan_type {
1283 classic = hp::classic, ///< classic scan as described in Michael's papers
1284 inplace = hp::inplace ///< inplace scan without allocation
1287 /// Initializes %HP singleton
1289 The constructor initializes Hazard Pointer SMR singleton with passed parameters.
1290 If the instance does not yet exist then the function creates the instance.
1291 Otherwise it does nothing.
1293 The Michael's %HP reclamation schema depends of three parameters:
1294 - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
1295 the data structure algorithms. If \p nHazardPtrCount = 0, the defaul value 8 is used
1296 - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
1297 - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
1298 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
1301 size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread
1302 size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application
1303 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
1304 scan_type nScanType = scan_type::inplace ///< Scan type (see \p scan_type enum)
1310 nMaxRetiredPtrCount,
1311 static_cast<hp::scan_type>(nScanType)
1315 /// Terminates GC singleton
1317 The destructor destroys %HP global object. After calling of this function you may \b NOT
1318 use CDS data structures based on \p %cds::gc::HP.
1319 Usually, %HP object is destroyed at the end of your \p main().
1323 hp::smr::destruct( true );
1326 /// Checks that required hazard pointer count \p nCountNeeded is less or equal then max hazard pointer count
1328 If <tt> nRequiredCount > get_hazard_ptr_count()</tt> then the exception \p not_enought_hazard_ptr is thrown
1330 static void check_available_guards( size_t nCountNeeded )
1332 hp::smr::check_hazard_ptr_count( nCountNeeded );
1335 /// Set memory management functions
1337 @note This function may be called <b>BEFORE</b> creating an instance
1338 of Hazard Pointer SMR
1340 SMR object allocates some memory for thread-specific data and for
1341 creating SMR object.
1342 By default, a standard \p new and \p delete operators are used for this.
1344 static void set_memory_allocator(
1345 void* ( *alloc_func )( size_t size ), ///< \p malloc() function
1346 void( *free_func )( void * p ) ///< \p free() function
1349 hp::smr::set_memory_allocator( alloc_func, free_func );
1352 /// Returns max Hazard Pointer count
1353 static size_t max_hazard_count()
1355 return hp::smr::instance().get_hazard_ptr_count();
1358 /// Returns max count of thread
1359 static size_t max_thread_count()
1361 return hp::smr::instance().get_max_thread_count();
1364 /// Returns capacity of retired pointer array
1365 static size_t retired_array_capacity()
1367 return hp::smr::instance().get_max_retired_ptr_count();
1370 /// Retire pointer \p p with function \p func
1372 The function places pointer \p p to array of pointers ready for removing.
1373 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
1374 \p func is a disposer: when \p p can be safely removed, \p func is called.
1376 template <typename T>
1377 static void retire( T * p, void( *func )( T * ))
1379 hp::thread_data* rec = hp::smr::tls();
1380 if ( !rec->retired_.push( hp::retired_ptr( p, func )))
1381 hp::smr::instance().scan( rec );
1384 /// Retire pointer \p p with functor of type \p Disposer
1386 The function places pointer \p p to array of pointers ready for removing.
1387 (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
1389 Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
1391 template <typename T>
1393 void operator()( T * p ) ; // disposing operator
1396 Since the functor call can happen at any time after \p retire() call, additional restrictions are imposed to \p Disposer type:
1397 - it should be stateless functor
1398 - it should be default-constructible
1399 - the result of functor call with argument \p p should not depend on where the functor will be called.
1402 Operator \p delete functor:
1404 template <typename T>
1406 void operator ()( T * p ) {
1411 // How to call HP::retire method
1414 // ... use p in lock-free manner
1416 cds::gc::HP::retire<disposer>( p ) ; // place p to retired pointer array of HP GC
1419 Functor based on \p std::allocator :
1421 template <typename Alloc = std::allocator<int> >
1423 template <typename T>
1424 void operator()( T * p ) {
1425 typedef typename Alloc::templare rebind<T>::other alloc_t;
1428 a.deallocate( p, 1 );
1433 template <class Disposer, typename T>
1434 static void retire( T * p )
1436 if ( !hp::smr::tls()->retired_.push( hp::retired_ptr( p, cds::details::static_functor<Disposer, T>::call )))
1440 /// Get current scan strategy
1441 static scan_type getScanType()
1443 return static_cast<scan_type>( hp::smr::instance().get_scan_type());
1446 /// Checks if Hazard Pointer GC is constructed and may be used
1447 static bool isUsed()
1449 return hp::smr::isUsed();
1452 /// Forces SMR call for current thread
1454 Usually, this function should not be called directly.
1458 hp::smr::instance().scan( hp::smr::tls());
1461 /// Synonym for \p scan()
1462 static void force_dispose()
1467 /// Returns internal statistics
1469 The function clears \p st before gathering statistics.
1471 @note Internal statistics is available only if you compile
1472 \p libcds and your program with \p -DCDS_ENABLE_HPSTAT.
1474 static void statistics( stat& st )
1476 hp::smr::instance().statistics( st );
1479 /// Returns post-mortem statistics
1481 Post-mortem statistics is gathered in the \p %HP object destructor
1482 and can be accessible after destructing the global \p %HP object.
1484 @note Internal statistics is available only if you compile
1485 \p libcds and your program with \p -DCDS_ENABLE_HPSTAT.
1493 // Initialize HP SMR
1496 // deal with HP-based data structured
1500 // HP object destroyed
1501 // Get total post-mortem statistics
1502 cds::gc::HP::stat const& st = cds::gc::HP::postmortem_statistics();
1504 printf( "HP statistics:\n"
1505 " thread count = %llu\n"
1506 " guard allocated = %llu\n"
1507 " guard freed = %llu\n"
1508 " retired data count = %llu\n"
1509 " free data count = %llu\n"
1510 " scan() call count = %llu\n"
1511 " help_scan() call count = %llu\n",
1512 st.thread_rec_count,
1513 st.guard_allocated, st.guard_freed,
1514 st.retired_count, st.free_count,
1515 st.scan_count, st.help_scan_count
1522 CDS_EXPORT_API static stat const& postmortem_statistics();
1525 }} // namespace cds::gc
1527 #endif // #ifndef CDSLIB_GC_HP_SMR_H