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