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