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