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             /// Store marked pointer \p p to the guard
 228             /**
 229                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 230                 Can be used for a marked pointer that cannot be changed concurrently.
 231             */
 232             template <typename T, int BITMASK>
 233             T * assign( cds::details::marked_ptr<T, BITMASK> p )
 234             {
 235                 return base_class::operator =( p.ptr() );
 236             }
 237
 238             /// Copy from \p src guard to \p this guard
 239             void copy( Guard const& src )
 240             {
 241                 assign( src.get_native() );
 242             }
 243
 244             /// Clear value of the guard
 245             void clear()
 246             {
 247                 base_class::clear();
 248             }
 249
 250             /// Get the value currently protected (relaxed read)
 251             template <typename T>
 252             T * get() const
 253             {
 254                 return reinterpret_cast<T *>( get_native() );
 255             }
 256
 257             /// Get native guarded pointer stored
 258             guarded_pointer get_native() const
 259             {
 260                 return base_class::get_guard()->pPost.load(CDS_ATOMIC::memory_order_relaxed);
 261             }
 262
 263         };
 264
 265         /// Array of Pass-the-Buck guards
 266         /**
 267             @headerfile cds/gc/ptb.h
 268             This class is a wrapper for ptb::GuardArray template.
 269             Template parameter \p Count defines the size of PTB array.
 270         */
 271         template <size_t Count>
 272         class GuardArray: public ptb::GuardArray<Count>
 273         {
 274             //@cond
 275             typedef ptb::GuardArray<Count> base_class;
 276             //@endcond
 277         public:
 278             /// Rebind array for other size \p COUNT2
 279             template <size_t OtherCount>
 280             struct rebind {
 281                 typedef GuardArray<OtherCount>  other   ;   ///< rebinding result
 282             };
 283
 284         public:
 285             //@cond
 286             GuardArray()    ;   // inline in ptb_impl.h
 287             //@endcond
 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             template <typename T>
 297             T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard )
 298             {
 299                 T pRet;
 300                 do {
 301                     pRet = assign( nIndex, toGuard.load(CDS_ATOMIC::memory_order_relaxed) );
 302                 } while ( pRet != toGuard.load(CDS_ATOMIC::memory_order_acquire));
 303
 304                 return pRet;
 305             }
 306
 307             /// Protects a pointer of type \p atomic<T*>
 308             /**
 309                 Return the value of \p toGuard
 310
 311                 The function tries to load \p toGuard and to store it
 312                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 313
 314                 The function is useful for intrusive containers when \p toGuard is a node pointer
 315                 that should be converted to a pointer to the value type before guarding.
 316                 The parameter \p f of type Func is a functor that makes this conversion:
 317                 \code
 318                     struct functor {
 319                         value_type * operator()( T * p );
 320                     };
 321                 \endcode
 322                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 323             */
 324             template <typename T, class Func>
 325             T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard, Func f )
 326             {
 327                 T pRet;
 328                 do {
 329                     assign( nIndex, f( pRet = toGuard.load(CDS_ATOMIC::memory_order_relaxed) ));
 330                 } while ( pRet != toGuard.load(CDS_ATOMIC::memory_order_acquire));
 331
 332                 return pRet;
 333             }
 334
 335             /// Store \p to the slot \p nIndex
 336             /**
 337                 The function equals to a simple assignment, no loop is performed.
 338             */
 339             template <typename T>
 340             T * assign( size_t nIndex, T * p )
 341             {
 342                 base_class::set(nIndex, p);
 343                 return p;
 344             }
 345
 346             /// Store marked pointer \p p to the guard
 347             /**
 348                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 349                 Can be used for a marked pointer that cannot be changed concurrently.
 350             */
 351             template <typename T, int Bitmask>
 352             T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
 353             {
 354                 return assign( nIndex, p.ptr() );
 355             }
 356
 357             /// Copy guarded value from \p src guard to slot at index \p nIndex
 358             void copy( size_t nIndex, Guard const& src )
 359             {
 360                 assign( nIndex, src.get_native() );
 361             }
 362
 363             /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
 364             void copy( size_t nDestIndex, size_t nSrcIndex )
 365             {
 366                 assign( nDestIndex, get_native( nSrcIndex ));
 367             }
 368
 369             /// Clear value of the slot \p nIndex
 370             void clear( size_t nIndex)
 371             {
 372                 base_class::clear( nIndex );
 373             }
 374
 375             /// Get current value of slot \p nIndex
 376             template <typename T>
 377             T * get( size_t nIndex) const
 378             {
 379                 return reinterpret_cast<T *>( get_native( nIndex ) );
 380             }
 381
 382             /// Get native guarded pointer stored
 383             guarded_pointer get_native( size_t nIndex ) const
 384             {
 385                 return base_class::operator[](nIndex).get_guard()->pPost.load(CDS_ATOMIC::memory_order_relaxed);
 386             }
 387
 388             /// Capacity of the guard array
 389             static CDS_CONSTEXPR size_t capacity()
 390             {
 391                 return Count;
 392             }
 393         };
 394
 395     public:
 396         /// Initializes ptb::GarbageCollector singleton
 397         /**
 398             The constructor calls GarbageCollector::Construct with passed parameters.
 399             See ptb::GarbageCollector::Construct for explanation of parameters meaning.
 400         */
 401         PTB(
 402             size_t nLiberateThreshold = 1024
 403             , size_t nInitialThreadGuardCount = 8
 404         )
 405         {
 406             ptb::GarbageCollector::Construct(
 407                 nLiberateThreshold,
 408                 nInitialThreadGuardCount
 409             );
 410         }
 411
 412         /// Terminates ptb::GarbageCollector singleton
 413         /**
 414             The destructor calls \code ptb::GarbageCollector::Destruct() \endcode
 415         */
 416         ~PTB()
 417         {
 418             ptb::GarbageCollector::Destruct();
 419         }
 420
 421         /// Checks if count of hazard pointer is no less than \p nCountNeeded
 422         /**
 423             The function always returns \p true since the guard count is unlimited for
 424             PTB garbage collector.
 425         */
 426         static bool check_available_guards( size_t nCountNeeded, bool /*bRaiseException*/ = true )
 427         {
 428             CDS_UNUSED( nCountNeeded );
 429             return true;
 430         }
 431
 432         /// Retire pointer \p p with function \p pFunc
 433         /**
 434             The function places pointer \p p to array of pointers ready for removing.
 435             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
 436             Deleting the pointer is the function \p pFunc call.
 437         */
 438         template <typename T>
 439         static void retire( T * p, void (* pFunc)(T *) )
 440         {
 441             ptb::GarbageCollector::instance().retirePtr( p, pFunc );
 442         }
 443
 444         /// Retire pointer \p p with functor of type \p Disposer
 445         /**
 446             The function places pointer \p p to array of pointers ready for removing.
 447             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
 448
 449             See gc::HP::retire for \p Disposer requirements.
 450         */
 451         template <class Disposer, typename T>
 452         static void retire( T * p )
 453         {
 454             retire( p, cds::details::static_functor<Disposer, T>::call );
 455         }
 456
 457         /// Checks if Pass-the-Buck GC is constructed and may be used
 458         static bool isUsed()
 459         {
 460             return ptb::GarbageCollector::isUsed();
 461         }
 462
 463         /// Forced GC cycle call for current thread
 464         /**
 465             Usually, this function should not be called directly.
 466         */
 467         static void scan()  ;   // inline in ptb_impl.h
 468
 469         /// Synonym for \ref scan()
 470         static void force_dispose()
 471         {
 472             scan();
 473         }
 474     };
 475
 476 }} // namespace cds::gc
 477
 478 #endif // #ifndef __CDS_GC_PTB_DECL_H