cds/gc/impl/dhp_decl.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_GC_DHP_DHP_DECL_H
   4 #define __CDS_GC_DHP_DHP_DECL_H
   5
   6 #include <cds/gc/details/dhp.h>
   7 #include <cds/details/marked_ptr.h>
   8 #include <cds/details/static_functor.h>
   9
  10 namespace cds { namespace gc {
  11
  12     /// Dynamic Hazard Pointer garbage collector
  13     /**  @ingroup cds_garbage_collector
  14         @headerfile cds/gc/dhp.h
  15
  16         Implementation of Dynamic Hazard Pointer garbage collector.
  17
  18         Sources:
  19             - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
  20             - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
  21             - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
  22
  23         Dynamic Hazard Pointers SMR (safe memory reclamation) provides an unbounded number of hazard pointer per thread
  24         despite of classic Hazard Pointer SMR in which the count of the hazard pointef per thread is limited.
  25
  26         See \ref cds_how_to_use "How to use" section for details how to apply garbage collector.
  27     */
  28     class DHP
  29     {
  30     public:
  31         /// Native guarded pointer type
  32         /**
  33             @headerfile cds/gc/dhp.h
  34         */
  35         typedef void * guarded_pointer;
  36
  37         /// Atomic reference
  38         /**
  39             @headerfile cds/gc/dhp.h
  40         */
  41         template <typename T> using atomic_ref = atomics::atomic<T *>;
  42
  43         /// Atomic type
  44         /**
  45             @headerfile cds/gc/dhp.h
  46         */
  47         template <typename T> using atomic_type = atomics::atomic<T>;
  48
  49         /// Atomic marked pointer
  50         /**
  51             @headerfile cds/gc/dhp.h
  52         */
  53         template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
  54
  55         /// Thread GC implementation for internal usage
  56         /**
  57             @headerfile cds/gc/dhp.h
  58         */
  59         typedef dhp::ThreadGC   thread_gc_impl;
  60
  61         /// Thread-level garbage collector
  62         /**
  63             @headerfile cds/gc/dhp.h
  64             This class performs automatically attaching/detaching Dynamic Hazard Pointer GC
  65             for the current thread.
  66         */
  67         class thread_gc: public thread_gc_impl
  68         {
  69             //@cond
  70             bool    m_bPersistent;
  71             //@endcond
  72         public:
  73             /// Constructor
  74             /**
  75                 The constructor attaches the current thread to the Dynamic Hazard Pointer GC
  76                 if it is not yet attached.
  77                 The \p bPersistent parameter specifies attachment persistence:
  78                 - \p true - the class destructor will not detach the thread from Dynamic Hazard Pointer GC.
  79                 - \p false (default) - the class destructor will detach the thread from Dynamic Hazard Pointer GC.
  80             */
  81             thread_gc(
  82                 bool    bPersistent = false
  83             )   ;   // inline in dhp_impl.h
  84
  85             /// Destructor
  86             /**
  87                 If the object has been created in persistent mode, the destructor does nothing.
  88                 Otherwise it detaches the current thread from Dynamic Hazard Pointer GC.
  89             */
  90             ~thread_gc()    ;   // inline in dhp_impl.h
  91         };
  92
  93
  94         /// Dynamic Hazard Pointer guard
  95         /**
  96             @headerfile cds/gc/dhp.h
  97
  98             A guard is the hazard pointer.
  99             Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
 100
 101             A \p %Guard object is not copy- and move-constructible
 102             and not copy- and move-assignable.
 103         */
 104         class Guard: public dhp::Guard
 105         {
 106             //@cond
 107             typedef dhp::Guard base_class;
 108             //@endcond
 109
 110         public:
 111             // Default ctor
 112             Guard() CDS_NOEXCEPT;   // inline in dhp_impl.h
 113
 114             //@cond
 115             Guard( Guard const& ) = delete;
 116             Guard( Guard&& s ) = delete;
 117             Guard& operator=(Guard const&) = delete;
 118             Guard& operator=(Guard&&) = delete;
 119             //@endcond
 120
 121             /// Protects a pointer of type <tt> atomic<T*> </tt>
 122             /**
 123                 Return the value of \p toGuard
 124
 125                 The function tries to load \p toGuard and to store it
 126                 to the HP slot repeatedly until the guard's value equals \p toGuard
 127             */
 128             template <typename T>
 129             T protect( atomics::atomic<T> const& toGuard ) CDS_NOEXCEPT
 130             {
 131                 T pCur = toGuard.load(atomics::memory_order_relaxed);
 132                 T pRet;
 133                 do {
 134                     pRet = assign( pCur );
 135                     pCur = toGuard.load(atomics::memory_order_acquire);
 136                 } while ( pRet != pCur );
 137                 return pCur;
 138             }
 139
 140             /// Protects a converted pointer of type <tt> atomic<T*> </tt>
 141             /**
 142                 Return the value of \p toGuard
 143
 144                 The function tries to load \p toGuard and to store result of \p f functor
 145                 to the HP slot repeatedly until the guard's value equals \p toGuard.
 146
 147                 The function is useful for intrusive containers when \p toGuard is a node pointer
 148                 that should be converted to a pointer to the value type before guarding.
 149                 The parameter \p f of type Func is a functor that makes this conversion:
 150                 \code
 151                     struct functor {
 152                         value_type * operator()( T * p );
 153                     };
 154                 \endcode
 155                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 156             */
 157             template <typename T, class Func>
 158             T protect( atomics::atomic<T> const& toGuard, Func f ) CDS_NOEXCEPT_( f( toGuard.load( atomics::memory_order_relaxed )))
 159             {
 160                 T pCur = toGuard.load(atomics::memory_order_relaxed);
 161                 T pRet;
 162                 do {
 163                     pRet = pCur;
 164                     assign( f( pCur ) );
 165                     pCur = toGuard.load(atomics::memory_order_acquire);
 166                 } while ( pRet != pCur );
 167                 return pCur;
 168             }
 169
 170             /// Store \p p to the guard
 171             /**
 172                 The function is just an assignment, no loop is performed.
 173                 Can be used for a pointer that cannot be changed concurrently
 174                 or for already guarded pointer.
 175             */
 176             template <typename T>
 177             T * assign( T * p ) CDS_NOEXCEPT
 178             {
 179                 return base_class::operator =(p);
 180             }
 181
 182             //@cond
 183             std::nullptr_t assign( std::nullptr_t ) CDS_NOEXCEPT
 184             {
 185                 return base_class::operator =(nullptr);
 186             }
 187             //@endcond
 188
 189             /// Store marked pointer \p p to the guard
 190             /**
 191                 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
 192                 Can be used for a marked pointer that cannot be changed concurrently
 193                 or for already guarded pointer.
 194             */
 195             template <typename T, int BITMASK>
 196             T * assign( cds::details::marked_ptr<T, BITMASK> p ) CDS_NOEXCEPT
 197             {
 198                 return base_class::operator =( p.ptr() );
 199             }
 200
 201             /// Copy from \p src guard to \p this guard
 202             void copy( Guard const& src ) CDS_NOEXCEPT
 203             {
 204                 assign( src.get_native() );
 205             }
 206
 207             /// Clears value of the guard
 208             void clear() CDS_NOEXCEPT
 209             {
 210                 base_class::clear();
 211             }
 212
 213             /// Gets the value currently protected (relaxed read)
 214             template <typename T>
 215             T * get() const CDS_NOEXCEPT
 216             {
 217                 return reinterpret_cast<T *>( get_native() );
 218             }
 219
 220             /// Gets native guarded pointer stored
 221             guarded_pointer get_native() const CDS_NOEXCEPT
 222             {
 223                 return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed);
 224             }
 225         };
 226
 227         /// Array of Dynamic Hazard Pointer guards
 228         /**
 229             @headerfile cds/gc/dhp.h
 230             The class is intended for allocating an array of hazard pointer guards.
 231             Template parameter \p Count defines the size of the array.
 232
 233             A \p %GuardArray object is not copy- and move-constructible
 234             and not copy- and move-assignable.
 235         */
 236         template <size_t Count>
 237         class GuardArray: public dhp::GuardArray<Count>
 238         {
 239             //@cond
 240             typedef dhp::GuardArray<Count> base_class;
 241             //@endcond
 242         public:
 243             /// Rebind array for other size \p OtherCount
 244             template <size_t OtherCount>
 245             struct rebind {
 246                 typedef GuardArray<OtherCount>  other   ;   ///< rebinding result
 247             };
 248
 249         public:
 250             // Default ctor
 251             GuardArray() CDS_NOEXCEPT;   // inline in dhp_impl.h
 252
 253             //@cond
 254             GuardArray( GuardArray const& ) = delete;
 255             GuardArray( GuardArray&& ) = delete;
 256             GuardArray& operator=(GuardArray const&) = delete;
 257             GuardArray& operator-(GuardArray&&) = delete;
 258             //@endcond
 259
 260             /// Protects a pointer of type \p atomic<T*>
 261             /**
 262                 Return the value of \p toGuard
 263
 264                 The function tries to load \p toGuard and to store it
 265                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 266             */
 267             template <typename T>
 268             T protect( size_t nIndex, atomics::atomic<T> const& toGuard ) CDS_NOEXCEPT
 269             {
 270                 T pRet;
 271                 do {
 272                     pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) );
 273                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 274
 275                 return pRet;
 276             }
 277
 278             /// Protects a pointer of type \p atomic<T*>
 279             /**
 280                 Return the value of \p toGuard
 281
 282                 The function tries to load \p toGuard and to store it
 283                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 284
 285                 The function is useful for intrusive containers when \p toGuard is a node pointer
 286                 that should be converted to a pointer to the value type before guarding.
 287                 The parameter \p f of type Func is a functor to make that conversion:
 288                 \code
 289                     struct functor {
 290                         value_type * operator()( T * p );
 291                     };
 292                 \endcode
 293                 Actually, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 294             */
 295             template <typename T, class Func>
 296             T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f ) CDS_NOEXCEPT_( f( toGuard.load( atomics::memory_order_relaxed )))
 297             {
 298                 T pRet;
 299                 do {
 300                     assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
 301                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 302
 303                 return pRet;
 304             }
 305
 306             /// Store \p p to the slot \p nIndex
 307             /**
 308                 The function is just an assignment, no loop is performed.
 309             */
 310             template <typename T>
 311             T * assign( size_t nIndex, T * p ) CDS_NOEXCEPT
 312             {
 313                 base_class::set(nIndex, p);
 314                 return p;
 315             }
 316
 317             /// Store marked pointer \p p to the guard
 318             /**
 319                 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
 320                 Can be used for a marked pointer that cannot be changed concurrently
 321                 or for already guarded pointer.
 322             */
 323             template <typename T, int Bitmask>
 324             T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p ) CDS_NOEXCEPT
 325             {
 326                 return assign( nIndex, p.ptr() );
 327             }
 328
 329             /// Copy guarded value from \p src guard to slot at index \p nIndex
 330             void copy( size_t nIndex, Guard const& src ) CDS_NOEXCEPT
 331             {
 332                 assign( nIndex, src.get_native() );
 333             }
 334
 335             /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
 336             void copy( size_t nDestIndex, size_t nSrcIndex ) CDS_NOEXCEPT
 337             {
 338                 assign( nDestIndex, get_native( nSrcIndex ));
 339             }
 340
 341             /// Clear value of the slot \p nIndex
 342             void clear( size_t nIndex ) CDS_NOEXCEPT
 343             {
 344                 base_class::clear( nIndex );
 345             }
 346
 347             /// Get current value of slot \p nIndex
 348             template <typename T>
 349             T * get( size_t nIndex ) const CDS_NOEXCEPT
 350             {
 351                 return reinterpret_cast<T *>( get_native( nIndex ) );
 352             }
 353
 354             /// Get native guarded pointer stored
 355             guarded_pointer get_native( size_t nIndex ) const CDS_NOEXCEPT
 356             {
 357                 return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed);
 358             }
 359
 360             /// Capacity of the guard array
 361             static CDS_CONSTEXPR size_t capacity() CDS_NOEXCEPT
 362             {
 363                 return Count;
 364             }
 365         };
 366
 367     public:
 368         /// Initializes dhp::GarbageCollector singleton
 369         /**
 370             The constructor calls GarbageCollector::Construct with passed parameters.
 371             See dhp::GarbageCollector::Construct for explanation of parameters meaning.
 372         */
 373         DHP(
 374             size_t nLiberateThreshold = 1024
 375             , size_t nInitialThreadGuardCount = 8
 376         )
 377         {
 378             dhp::GarbageCollector::Construct(
 379                 nLiberateThreshold,
 380                 nInitialThreadGuardCount
 381             );
 382         }
 383
 384         /// Terminates dhp::GarbageCollector singleton
 385         /**
 386             The destructor calls \code dhp::GarbageCollector::Destruct() \endcode
 387         */
 388         ~DHP()
 389         {
 390             dhp::GarbageCollector::Destruct();
 391         }
 392
 393         /// Checks if count of hazard pointer is no less than \p nCountNeeded
 394         /**
 395             The function always returns \p true since the guard count is unlimited for
 396             DHP garbage collector.
 397         */
 398         static CDS_CONSTEXPR bool check_available_guards( size_t nCountNeeded, bool /*bRaiseException*/ = true )
 399         {
 400             CDS_UNUSED( nCountNeeded );
 401             return true;
 402         }
 403
 404         /// Retire pointer \p p with function \p pFunc
 405         /**
 406             The function places pointer \p p to array of pointers ready for removing.
 407             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
 408             Deleting the pointer is the function \p pFunc call.
 409         */
 410         template <typename T>
 411         static void retire( T * p, void (* pFunc)(T *) )
 412         {
 413             dhp::GarbageCollector::instance().retirePtr( p, pFunc );
 414         }
 415
 416         /// Retire pointer \p p with functor of type \p Disposer
 417         /**
 418             The function places pointer \p p to array of pointers ready for removing.
 419             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
 420
 421             See gc::HP::retire for \p Disposer requirements.
 422         */
 423         template <class Disposer, typename T>
 424         static void retire( T * p )
 425         {
 426             retire( p, cds::details::static_functor<Disposer, T>::call );
 427         }
 428
 429         /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
 430         static bool isUsed()
 431         {
 432             return dhp::GarbageCollector::isUsed();
 433         }
 434
 435         /// Forced GC cycle call for current thread
 436         /**
 437             Usually, this function should not be called directly.
 438         */
 439         static void scan()  ;   // inline in dhp_impl.h
 440
 441         /// Synonym for \ref scan()
 442         static void force_dispose()
 443         {
 444             scan();
 445         }
 446     };
 447
 448 }} // namespace cds::gc
 449
 450 #endif // #ifndef __CDS_GC_DHP_DHP_DECL_H