cds/gc/ptb_decl.h

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