cds/gc/impl/dhp_decl.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_GC_IMPL_DHP_DECL_H
   4 #define __CDS_GC_IMPL_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         public: // for internal use only!!!
  93             //@cond
  94             static void alloc_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h
  95             static void free_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h
  96             //@endcond
  97         };
  98
  99
 100         /// Dynamic Hazard Pointer guard
 101         /**
 102             @headerfile cds/gc/dhp.h
 103
 104             A guard is the hazard pointer.
 105             Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
 106
 107             A \p %Guard object is not copy- and move-constructible
 108             and not copy- and move-assignable.
 109         */
 110         class Guard: public dhp::Guard
 111         {
 112             //@cond
 113             typedef dhp::Guard base_class;
 114             //@endcond
 115
 116         public: // for internal use only
 117             //@cond
 118             typedef cds::gc::dhp::details::guard native_guard;
 119             //@endcond
 120
 121         public:
 122             // Default ctor
 123             Guard()
 124             {}
 125
 126             //@cond
 127             Guard( Guard const& ) = delete;
 128             Guard( Guard&& s ) = delete;
 129             Guard& operator=(Guard const&) = delete;
 130             Guard& operator=(Guard&&) = delete;
 131             //@endcond
 132
 133             /// Protects a pointer of type <tt> atomic<T*> </tt>
 134             /**
 135                 Return the value of \p toGuard
 136
 137                 The function tries to load \p toGuard and to store it
 138                 to the HP slot repeatedly until the guard's value equals \p toGuard
 139             */
 140             template <typename T>
 141             T protect( atomics::atomic<T> const& toGuard )
 142             {
 143                 T pCur = toGuard.load(atomics::memory_order_relaxed);
 144                 T pRet;
 145                 do {
 146                     pRet = assign( pCur );
 147                     pCur = toGuard.load(atomics::memory_order_acquire);
 148                 } while ( pRet != pCur );
 149                 return pCur;
 150             }
 151
 152             /// Protects a converted pointer of type <tt> atomic<T*> </tt>
 153             /**
 154                 Return the value of \p toGuard
 155
 156                 The function tries to load \p toGuard and to store result of \p f functor
 157                 to the HP slot repeatedly until the guard's value equals \p toGuard.
 158
 159                 The function is useful for intrusive containers when \p toGuard is a node pointer
 160                 that should be converted to a pointer to the value type before guarding.
 161                 The parameter \p f of type Func is a functor that makes this conversion:
 162                 \code
 163                     struct functor {
 164                         value_type * operator()( T * p );
 165                     };
 166                 \endcode
 167                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 168             */
 169             template <typename T, class Func>
 170             T protect( atomics::atomic<T> const& toGuard, Func f )
 171             {
 172                 T pCur = toGuard.load(atomics::memory_order_relaxed);
 173                 T pRet;
 174                 do {
 175                     pRet = pCur;
 176                     assign( f( pCur ) );
 177                     pCur = toGuard.load(atomics::memory_order_acquire);
 178                 } while ( pRet != pCur );
 179                 return pCur;
 180             }
 181
 182             /// Store \p p to the guard
 183             /**
 184                 The function is just an assignment, no loop is performed.
 185                 Can be used for a pointer that cannot be changed concurrently
 186                 or for already guarded pointer.
 187             */
 188             template <typename T>
 189             T * assign( T * p )
 190             {
 191                 return base_class::operator =(p);
 192             }
 193
 194             //@cond
 195             std::nullptr_t assign( std::nullptr_t )
 196             {
 197                 return base_class::operator =(nullptr);
 198             }
 199             //@endcond
 200
 201             /// Store marked pointer \p p to the guard
 202             /**
 203                 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
 204                 Can be used for a marked pointer that cannot be changed concurrently
 205                 or for already guarded pointer.
 206             */
 207             template <typename T, int BITMASK>
 208             T * assign( cds::details::marked_ptr<T, BITMASK> p )
 209             {
 210                 return base_class::operator =( p.ptr() );
 211             }
 212
 213             /// Copy from \p src guard to \p this guard
 214             void copy( Guard const& src )
 215             {
 216                 assign( src.get_native() );
 217             }
 218
 219             /// Clears value of the guard
 220             void clear()
 221             {
 222                 base_class::clear();
 223             }
 224
 225             /// Gets the value currently protected (relaxed read)
 226             template <typename T>
 227             T * get() const
 228             {
 229                 return reinterpret_cast<T *>( get_native() );
 230             }
 231
 232             /// Gets native guarded pointer stored
 233             guarded_pointer get_native() const
 234             {
 235                 return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed);
 236             }
 237         };
 238
 239         /// Array of Dynamic Hazard Pointer guards
 240         /**
 241             @headerfile cds/gc/dhp.h
 242             The class is intended for allocating an array of hazard pointer guards.
 243             Template parameter \p Count defines the size of the array.
 244
 245             A \p %GuardArray object is not copy- and move-constructible
 246             and not copy- and move-assignable.
 247         */
 248         template <size_t Count>
 249         class GuardArray: public dhp::GuardArray<Count>
 250         {
 251             //@cond
 252             typedef dhp::GuardArray<Count> base_class;
 253             //@endcond
 254         public:
 255             /// Rebind array for other size \p OtherCount
 256             template <size_t OtherCount>
 257             struct rebind {
 258                 typedef GuardArray<OtherCount>  other   ;   ///< rebinding result
 259             };
 260
 261         public:
 262             // Default ctor
 263             GuardArray()
 264             {}
 265
 266             //@cond
 267             GuardArray( GuardArray const& ) = delete;
 268             GuardArray( GuardArray&& ) = delete;
 269             GuardArray& operator=(GuardArray const&) = delete;
 270             GuardArray& operator-(GuardArray&&) = delete;
 271             //@endcond
 272
 273             /// Protects a pointer of type \p atomic<T*>
 274             /**
 275                 Return the value of \p toGuard
 276
 277                 The function tries to load \p toGuard and to store it
 278                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 279             */
 280             template <typename T>
 281             T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
 282             {
 283                 T pRet;
 284                 do {
 285                     pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) );
 286                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 287
 288                 return pRet;
 289             }
 290
 291             /// Protects a pointer of type \p atomic<T*>
 292             /**
 293                 Return the value of \p toGuard
 294
 295                 The function tries to load \p toGuard and to store it
 296                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 297
 298                 The function is useful for intrusive containers when \p toGuard is a node pointer
 299                 that should be converted to a pointer to the value type before guarding.
 300                 The parameter \p f of type Func is a functor to make that conversion:
 301                 \code
 302                     struct functor {
 303                         value_type * operator()( T * p );
 304                     };
 305                 \endcode
 306                 Actually, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 307             */
 308             template <typename T, class Func>
 309             T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
 310             {
 311                 T pRet;
 312                 do {
 313                     assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
 314                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 315
 316                 return pRet;
 317             }
 318
 319             /// Store \p p to the slot \p nIndex
 320             /**
 321                 The function is just an assignment, no loop is performed.
 322             */
 323             template <typename T>
 324             T * assign( size_t nIndex, T * p )
 325             {
 326                 base_class::set(nIndex, p);
 327                 return p;
 328             }
 329
 330             /// Store marked pointer \p p to the guard
 331             /**
 332                 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
 333                 Can be used for a marked pointer that cannot be changed concurrently
 334                 or for already guarded pointer.
 335             */
 336             template <typename T, int Bitmask>
 337             T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
 338             {
 339                 return assign( nIndex, p.ptr() );
 340             }
 341
 342             /// Copy guarded value from \p src guard to slot at index \p nIndex
 343             void copy( size_t nIndex, Guard const& src )
 344             {
 345                 assign( nIndex, src.get_native() );
 346             }
 347
 348             /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
 349             void copy( size_t nDestIndex, size_t nSrcIndex )
 350             {
 351                 assign( nDestIndex, get_native( nSrcIndex ));
 352             }
 353
 354             /// Clear value of the slot \p nIndex
 355             void clear( size_t nIndex )
 356             {
 357                 base_class::clear( nIndex );
 358             }
 359
 360             /// Get current value of slot \p nIndex
 361             template <typename T>
 362             T * get( size_t nIndex ) const
 363             {
 364                 return reinterpret_cast<T *>( get_native( nIndex ) );
 365             }
 366
 367             /// Get native guarded pointer stored
 368             guarded_pointer get_native( size_t nIndex ) const
 369             {
 370                 return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed);
 371             }
 372
 373             /// Capacity of the guard array
 374             static CDS_CONSTEXPR size_t capacity()
 375             {
 376                 return Count;
 377             }
 378         };
 379
 380         /// Guarded pointer
 381         /**
 382             A guarded pointer is a pair of a pointer and GC's guard.
 383             Usually, it is used for returning a pointer to the item from an lock-free container.
 384             The guard prevents the pointer to be early disposed (freed) by GC.
 385             After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
 386
 387             Template arguments:
 388             - \p GuardedType - a type which the guard stores
 389             - \p ValueType - a value type
 390             - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
 391
 392             For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
 393             In such case the \p %guarded_ptr is:
 394             @code
 395             typedef cds::gc::DHP::guarded_ptr< foo > intrusive_guarded_ptr;
 396             @endcode
 397
 398             For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
 399             For example:
 400             @code
 401             struct foo {
 402                 int const   key;
 403                 std::string value;
 404             };
 405
 406             struct value_accessor {
 407                 std::string* operator()( foo* pFoo ) const
 408                 {
 409                     return &(pFoo->value);
 410                 }
 411             };
 412
 413             // Guarded ptr
 414             typedef cds::gc::DHP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
 415             @endcode
 416
 417             You don't need use this class directly.
 418             All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
 419         */
 420         template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
 421         class guarded_ptr
 422         {
 423             //@cond
 424             struct trivial_cast {
 425                 ValueType * operator()( GuardedType * p ) const
 426                 {
 427                     return p;
 428                 }
 429             };
 430             //@endcond
 431
 432         public:
 433             typedef GuardedType guarded_type; ///< Guarded type
 434             typedef ValueType   value_type;   ///< Value type
 435
 436             /// Functor for casting \p guarded_type to \p value_type
 437             typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
 438
 439             //@cond
 440             typedef cds::gc::dhp::details::guard native_guard;
 441             //@endcond
 442
 443         private:
 444             //@cond
 445             native_guard    m_guard;
 446             //@endcond
 447
 448         public:
 449             /// Creates empty guarded pointer
 450             guarded_ptr() CDS_NOEXCEPT
 451             {}
 452
 453             //@cond
 454             /// Initializes guarded pointer with \p p
 455             explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
 456             {
 457                 alloc_guard();
 458                 assert( m_guard.is_initialized() );
 459                 m_guard.set( p );
 460             }
 461             explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
 462             {}
 463             //@endcond
 464
 465             /// Move ctor
 466             guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
 467             {
 468                 m_guard.set_guard( gp.m_guard.release_guard() );
 469             }
 470
 471             /// The guarded pointer is not copy-constructible
 472             guarded_ptr( guarded_ptr const& gp ) = delete;
 473
 474             /// Clears the guarded pointer
 475             /**
 476                 \ref release is called if guarded pointer is not \ref empty
 477             */
 478             ~guarded_ptr() CDS_NOEXCEPT
 479             {
 480                 free_guard();
 481             }
 482
 483             /// Move-assignment operator
 484             guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
 485             {
 486                 free_guard();
 487                 m_guard.set_guard( gp.m_guard.release_guard() );
 488                 return *this;
 489             }
 490
 491             /// The guarded pointer is not copy-assignable
 492             guarded_ptr& operator=(guarded_ptr const& gp) = delete;
 493
 494             /// Returns a pointer to guarded value
 495             value_type * operator ->() const CDS_NOEXCEPT
 496             {
 497                 assert( !empty() );
 498                 return value_cast()( reinterpret_cast<guarded_type *>(m_guard.get()));
 499             }
 500
 501             /// Returns a reference to guarded value
 502             value_type& operator *() CDS_NOEXCEPT
 503             {
 504                 assert( !empty());
 505                 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard.get()));
 506             }
 507
 508             /// Returns const reference to guarded value
 509             value_type const& operator *() const CDS_NOEXCEPT
 510             {
 511                 assert( !empty() );
 512                 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard.get()));
 513             }
 514
 515             /// Checks if the guarded pointer is \p nullptr
 516             bool empty() const CDS_NOEXCEPT
 517             {
 518                 return !m_guard.is_initialized() || m_guard.get( atomics::memory_order_relaxed ) == nullptr;
 519             }
 520
 521             /// \p bool operator returns <tt>!empty()</tt>
 522             explicit operator bool() const CDS_NOEXCEPT
 523             {
 524                 return !empty();
 525             }
 526
 527             /// Clears guarded pointer
 528             /**
 529                 If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
 530                 Dereferncing the guarded pointer after \p release() is dangerous.
 531             */
 532             void release() CDS_NOEXCEPT
 533             {
 534                 free_guard();
 535             }
 536
 537             //@cond
 538             // For internal use only!!!
 539             native_guard& guard() CDS_NOEXCEPT
 540             {
 541                 alloc_guard();
 542                 assert( m_guard.is_initialized() );
 543                 return m_guard;
 544             }
 545             //@endcond
 546
 547         private:
 548             //@cond
 549             void alloc_guard()
 550             {
 551                 if ( !m_guard.is_initialized() )
 552                     thread_gc::alloc_guard( m_guard );
 553             }
 554
 555             void free_guard()
 556             {
 557                 if ( m_guard.is_initialized() )
 558                     thread_gc::free_guard( m_guard );
 559             }
 560             //@endcond
 561         };
 562
 563     public:
 564         /// Initializes dhp::GarbageCollector singleton
 565         /**
 566             The constructor calls GarbageCollector::Construct with passed parameters.
 567             See dhp::GarbageCollector::Construct for explanation of parameters meaning.
 568         */
 569         DHP(
 570             size_t nLiberateThreshold = 1024
 571             , size_t nInitialThreadGuardCount = 8
 572         )
 573         {
 574             dhp::GarbageCollector::Construct(
 575                 nLiberateThreshold,
 576                 nInitialThreadGuardCount
 577             );
 578         }
 579
 580         /// Terminates dhp::GarbageCollector singleton
 581         /**
 582             The destructor calls \code dhp::GarbageCollector::Destruct() \endcode
 583         */
 584         ~DHP()
 585         {
 586             dhp::GarbageCollector::Destruct();
 587         }
 588
 589         /// Checks if count of hazard pointer is no less than \p nCountNeeded
 590         /**
 591             The function always returns \p true since the guard count is unlimited for
 592             \p gc::DHP garbage collector.
 593         */
 594         static CDS_CONSTEXPR bool check_available_guards(
 595 #ifdef CDS_DOXYGEN_INVOKED
 596             size_t nCountNeeded,
 597 #else
 598             size_t,
 599 #endif
 600             bool /*bRaiseException*/ = true )
 601         {
 602             return true;
 603         }
 604
 605         /// Retire pointer \p p with function \p pFunc
 606         /**
 607             The function places pointer \p p to array of pointers ready for removing.
 608             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
 609             Deleting the pointer is the function \p pFunc call.
 610         */
 611         template <typename T>
 612         static void retire( T * p, void (* pFunc)(T *) )
 613         {
 614             dhp::GarbageCollector::instance().retirePtr( p, pFunc );
 615         }
 616
 617         /// Retire pointer \p p with functor of type \p Disposer
 618         /**
 619             The function places pointer \p p to array of pointers ready for removing.
 620             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
 621
 622             See gc::HP::retire for \p Disposer requirements.
 623         */
 624         template <class Disposer, typename T>
 625         static void retire( T * p )
 626         {
 627             retire( p, cds::details::static_functor<Disposer, T>::call );
 628         }
 629
 630         /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
 631         static bool isUsed()
 632         {
 633             return dhp::GarbageCollector::isUsed();
 634         }
 635
 636         /// Forced GC cycle call for current thread
 637         /**
 638             Usually, this function should not be called directly.
 639         */
 640         static void scan()  ;   // inline in dhp_impl.h
 641
 642         /// Synonym for \ref scan()
 643         static void force_dispose()
 644         {
 645             scan();
 646         }
 647     };
 648
 649 }} // namespace cds::gc
 650
 651 #endif // #ifndef __CDS_GC_IMPL_DHP_DECL_H