cds/gc/hp_decl.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_GC_HP_DECL_H
   4 #define __CDS_GC_HP_DECL_H
   5
   6 #include <cds/gc/hzp/hzp.h>
   7 #include <cds/details/marked_ptr.h>
   8
   9 namespace cds { namespace gc {
  10     /// @defgroup cds_garbage_collector Garbage collectors
  11
  12     /// Hazard Pointer garbage collector
  13     /**  @ingroup cds_garbage_collector
  14         @headerfile cds/gc/hp.h
  15
  16         This class realizes a wrapper for Hazard Pointer garbage collector internal implementation.
  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         See \ref cds_how_to_use "How to use" section for details of garbage collector applying.
  24     */
  25     class HP
  26     {
  27     public:
  28         /// Native guarded pointer type
  29         typedef gc::hzp::hazard_pointer guarded_pointer;
  30
  31         /// Atomic reference
  32         /**
  33             @headerfile cds/gc/hp.h
  34         */
  35         template <typename T> using atomic_ref = atomics::atomic<T *>;
  36
  37         /// Atomic marked pointer
  38         /**
  39             @headerfile cds/gc/hp.h
  40         */
  41         template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
  42
  43         /// Atomic type
  44         /**
  45             @headerfile cds/gc/hp.h
  46         */
  47         template <typename T> using atomic_type = atomics::atomic<T>;
  48
  49         /// Thread GC implementation for internal usage
  50         typedef hzp::ThreadGC   thread_gc_impl;
  51
  52         /// Wrapper for hzp::ThreadGC class
  53         /**
  54             @headerfile cds/gc/hp.h
  55             This class performs automatically attaching/detaching Hazard Pointer GC
  56             for the current thread.
  57         */
  58         class thread_gc: public thread_gc_impl
  59         {
  60             //@cond
  61             bool    m_bPersistent;
  62             //@endcond
  63         public:
  64
  65             /// Constructor
  66             /**
  67                 The constructor attaches the current thread to the Hazard Pointer GC
  68                 if it is not yet attached.
  69                 The \p bPersistent parameter specifies attachment persistence:
  70                 - \p true - the class destructor will not detach the thread from Hazard Pointer GC.
  71                 - \p false (default) - the class destructor will detach the thread from Hazard Pointer GC.
  72             */
  73             thread_gc(
  74                 bool    bPersistent = false
  75             ) ;     //inline in hp_impl.h
  76
  77             /// Destructor
  78             /**
  79                 If the object has been created in persistent mode, the destructor does nothing.
  80                 Otherwise it detaches the current thread from Hazard Pointer GC.
  81             */
  82             ~thread_gc() ;  // inline in hp_impl.h
  83         };
  84
  85         /// Base for container node
  86         /**
  87             @headerfile cds/gc/hp.h
  88             This struct is empty for Hazard Pointer GC
  89         */
  90         struct container_node
  91         {};
  92
  93         /// Hazard Pointer guard
  94         /**
  95             @headerfile cds/gc/hp.h
  96             This class is a wrapper for hzp::AutoHPGuard.
  97         */
  98         class Guard: public hzp::AutoHPGuard
  99         {
 100             //@cond
 101             typedef hzp::AutoHPGuard base_class;
 102             //@endcond
 103
 104         public:
 105             //@cond
 106             Guard() ;   // inline in hp_impl.h
 107             //@endcond
 108
 109             /// Protects a pointer of type \p atomic<T*>
 110             /**
 111                 Return the value of \p toGuard
 112
 113                 The function tries to load \p toGuard and to store it
 114                 to the HP slot repeatedly until the guard's value equals \p toGuard
 115             */
 116             template <typename T>
 117             T protect( atomics::atomic<T> const& toGuard )
 118             {
 119                 T pCur = toGuard.load(atomics::memory_order_relaxed);
 120                 T pRet;
 121                 do {
 122                     pRet = assign( pCur );
 123                     pCur = toGuard.load(atomics::memory_order_acquire);
 124                 } while ( pRet != pCur );
 125                 return pCur;
 126             }
 127
 128             /// Protects a converted pointer of type \p atomic<T*>
 129             /**
 130                 Return the value of \p toGuard
 131
 132                 The function tries to load \p toGuard and to store result of \p f functor
 133                 to the HP slot repeatedly until the guard's value equals \p toGuard.
 134
 135                 The function is useful for intrusive containers when \p toGuard is a node pointer
 136                 that should be converted to a pointer to the value type before protecting.
 137                 The parameter \p f of type Func is a functor that makes this conversion:
 138                 \code
 139                     struct functor {
 140                         value_type * operator()( T * p );
 141                     };
 142                 \endcode
 143                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 144             */
 145             template <typename T, class Func>
 146             T protect( atomics::atomic<T> const& toGuard, Func f )
 147             {
 148                 T pCur = toGuard.load(atomics::memory_order_relaxed);
 149                 T pRet;
 150                 do {
 151                     pRet = pCur;
 152                     assign( f( pCur ) );
 153                     pCur = toGuard.load(atomics::memory_order_acquire);
 154                 } while ( pRet != pCur );
 155                 return pCur;
 156             }
 157
 158             /// Store \p p to the guard
 159             /**
 160                 The function equals to a simple assignment the value \p p to guard, no loop is performed.
 161                 Can be used for a pointer that cannot be changed concurrently
 162             */
 163             template <typename T>
 164             T * assign( T * p )
 165             {
 166                 return base_class::operator =(p);
 167             }
 168
 169             //@cond
 170             std::nullptr_t assign( std::nullptr_t )
 171             {
 172                 return base_class::operator =(nullptr);
 173             }
 174             //@endcond
 175
 176             /// Copy from \p src guard to \p this guard
 177             void copy( Guard const& src )
 178             {
 179                 assign( src.get_native() );
 180             }
 181
 182             /// Store marked pointer \p p to the guard
 183             /**
 184                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 185                 Can be used for a marked pointer that cannot be changed concurrently.
 186             */
 187             template <typename T, int BITMASK>
 188             T * assign( cds::details::marked_ptr<T, BITMASK> p )
 189             {
 190                 return base_class::operator =( p.ptr() );
 191             }
 192
 193             /// Clear value of the guard
 194             void clear()
 195             {
 196                 assign( nullptr );
 197             }
 198
 199             /// Get the value currently protected
 200             template <typename T>
 201             T * get() const
 202             {
 203                 return reinterpret_cast<T *>( get_native() );
 204             }
 205
 206             /// Get native hazard pointer stored
 207             guarded_pointer get_native() const
 208             {
 209                 return base_class::get();
 210             }
 211         };
 212
 213         /// Array of Hazard Pointer guards
 214         /**
 215             @headerfile cds/gc/hp.h
 216             This class is a wrapper for hzp::AutoHPArray template.
 217             Template parameter \p Count defines the size of HP array.
 218         */
 219         template <size_t Count>
 220         class GuardArray: public hzp::AutoHPArray<Count>
 221         {
 222             //@cond
 223             typedef hzp::AutoHPArray<Count> base_class;
 224             //@endcond
 225         public:
 226             /// Rebind array for other size \p Count2
 227             template <size_t Count2>
 228             struct rebind {
 229                 typedef GuardArray<Count2>  other   ;   ///< rebinding result
 230             };
 231
 232         public:
 233             //@cond
 234             GuardArray()    ;   // inline in hp_impl.h
 235             //@endcond
 236             /// Protects a pointer of type \p atomic<T*>
 237             /**
 238                 Return the value of \p toGuard
 239
 240                 The function tries to load \p toGuard and to store it
 241                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 242             */
 243             template <typename T>
 244             T protect(size_t nIndex, atomics::atomic<T> const& toGuard )
 245             {
 246                 T pRet;
 247                 do {
 248                     pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire) );
 249                 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
 250
 251                 return pRet;
 252             }
 253
 254             /// Protects a pointer of type \p atomic<T*>
 255             /**
 256                 Return the value of \p toGuard
 257
 258                 The function tries to load \p toGuard and to store it
 259                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 260
 261                 The function is useful for intrusive containers when \p toGuard is a node pointer
 262                 that should be converted to a pointer to the value type before guarding.
 263                 The parameter \p f of type Func is a functor that makes this conversion:
 264                 \code
 265                     struct functor {
 266                         value_type * operator()( T * p );
 267                     };
 268                 \endcode
 269                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 270             */
 271             template <typename T, class Func>
 272             T protect(size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
 273             {
 274                 T pRet;
 275                 do {
 276                     assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire) ));
 277                 } while ( pRet != toGuard.load(atomics::memory_order_relaxed));
 278
 279                 return pRet;
 280             }
 281
 282             /// Store \p to the slot \p nIndex
 283             /**
 284                 The function equals to a simple assignment, no loop is performed.
 285             */
 286             template <typename T>
 287             T * assign( size_t nIndex, T * p )
 288             {
 289                 base_class::set(nIndex, p);
 290                 return p;
 291             }
 292
 293             /// Store marked pointer \p p to the guard
 294             /**
 295                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 296                 Can be used for a marked pointer that cannot be changed concurrently.
 297             */
 298             template <typename T, int BITMASK>
 299             T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p )
 300             {
 301                 return assign( nIndex, p.ptr() );
 302             }
 303
 304             /// Copy guarded value from \p src guard to slot at index \p nIndex
 305             void copy( size_t nIndex, Guard const& src )
 306             {
 307                 assign( nIndex, src.get_native() );
 308             }
 309
 310             /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
 311             void copy( size_t nDestIndex, size_t nSrcIndex )
 312             {
 313                 assign( nDestIndex, get_native( nSrcIndex ));
 314             }
 315
 316             /// Clear value of the slot \p nIndex
 317             void clear( size_t nIndex)
 318             {
 319                 base_class::clear( nIndex );
 320             }
 321
 322             /// Get current value of slot \p nIndex
 323             template <typename T>
 324             T * get( size_t nIndex) const
 325             {
 326                 return reinterpret_cast<T *>( get_native( nIndex ) );
 327             }
 328
 329             /// Get native hazard pointer stored
 330             guarded_pointer get_native( size_t nIndex ) const
 331             {
 332                 return base_class::operator[](nIndex).get();
 333             }
 334
 335             /// Capacity of the guard array
 336             static CDS_CONSTEXPR size_t capacity()
 337             {
 338                 return Count;
 339             }
 340         };
 341
 342     public:
 343         /// Initializes hzp::GarbageCollector singleton
 344         /**
 345             The constructor initializes GC singleton with passed parameters.
 346             If GC instance is not exist then the function creates the instance.
 347             Otherwise it does nothing.
 348
 349             The Michael's HP reclamation schema depends of three parameters:
 350             - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
 351                 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
 352                 uses maximum of the hazard pointer count for CDS library.
 353             - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
 354             - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
 355                 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
 356         */
 357         HP(
 358             size_t nHazardPtrCount = 0,     ///< Hazard pointer count per thread
 359             size_t nMaxThreadCount = 0,     ///< Max count of simultaneous working thread in your application
 360             size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
 361             hzp::scan_type nScanType = hzp::inplace   ///< Scan type (see \ref hzp::scan_type enum)
 362         )
 363         {
 364             hzp::GarbageCollector::Construct(
 365                 nHazardPtrCount,
 366                 nMaxThreadCount,
 367                 nMaxRetiredPtrCount,
 368                 nScanType
 369             );
 370         }
 371
 372         /// Terminates GC singleton
 373         /**
 374             The destructor calls \code hzp::GarbageCollector::Destruct( true ) \endcode
 375         */
 376         ~HP()
 377         {
 378             hzp::GarbageCollector::Destruct( true );
 379         }
 380
 381         /// Checks if count of hazard pointer is no less than \p nCountNeeded
 382         /**
 383             If \p bRaiseException is \p true (that is the default), the function raises an exception gc::too_few_hazard_pointers
 384             if \p nCountNeeded is more than the count of hazard pointer per thread.
 385         */
 386         static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
 387         {
 388             if ( hzp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
 389                 if ( bRaiseException )
 390                     throw cds::gc::too_few_hazard_pointers();
 391                 return false;
 392             }
 393             return true;
 394         }
 395
 396         /// Returns max Hazard Pointer count
 397         size_t max_hazard_count() const
 398         {
 399             return hzp::GarbageCollector::instance().getHazardPointerCount();
 400         }
 401
 402         /// Returns max count of thread
 403         size_t max_thread_count() const
 404         {
 405             return hzp::GarbageCollector::instance().getMaxThreadCount();
 406         }
 407
 408         /// Returns capacity of retired pointer array
 409         size_t retired_array_capacity() const
 410         {
 411             return hzp::GarbageCollector::instance().getMaxRetiredPtrCount();
 412         }
 413
 414         /// Retire pointer \p p with function \p pFunc
 415         /**
 416             The function places pointer \p p to array of pointers ready for removing.
 417             (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
 418             Deleting the pointer is the function \p pFunc call.
 419         */
 420         template <typename T>
 421         static void retire( T * p, void (* pFunc)(T *) )    ;   // inline in hp_impl.h
 422
 423         /// Retire pointer \p p with functor of type \p Disposer
 424         /**
 425             The function places pointer \p p to array of pointers ready for removing.
 426             (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
 427
 428             Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
 429             \code
 430             template <typename T>
 431             struct disposer {
 432                 void operator()( T * p )    ;   // disposing operator
 433             };
 434             \endcode
 435             Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
 436             - it should be stateless functor
 437             - it should be default-constructible
 438             - the result of functor call with argument \p p should not depend on where the functor will be called.
 439
 440             \par Examples:
 441             Operator \p delete functor:
 442             \code
 443             template <typename T>
 444             struct disposer {
 445                 void operator ()( T * p ) {
 446                     delete p;
 447                 }
 448             };
 449
 450             // How to call GC::retire method
 451             int * p = new int;
 452
 453             // ... use p in lock-free manner
 454
 455             cds::gc::HP::retire<disposer>( p ) ;   // place p to retired pointer array of HP GC
 456             \endcode
 457
 458             Functor based on \p std::allocator :
 459             \code
 460             template <typename ALLOC = std::allocator<int> >
 461             struct disposer {
 462                 template <typename T>
 463                 void operator()( T * p ) {
 464                     typedef typename ALLOC::templare rebind<T>::other   alloc_t;
 465                     alloc_t a;
 466                     a.destroy( p );
 467                     a.deallocate( p, 1 );
 468                 }
 469             };
 470             \endcode
 471         */
 472         template <class Disposer, typename T>
 473         static void retire( T * p ) ;   // inline in hp_impl.h
 474
 475         /// Get current scan strategy
 476         /**@anchor hrc_gc_HP_getScanType
 477             See hzp::GarbageCollector::Scan for scan algo description
 478         */
 479         hzp::scan_type getScanType() const
 480         {
 481             return hzp::GarbageCollector::instance().getScanType();
 482         }
 483
 484         /// Set current scan strategy
 485         /**
 486             Scan strategy changing is allowed on the fly.
 487
 488             About scan strategy see \ref hrc_gc_HP_getScanType "getScanType"
 489         */
 490         void setScanType(
 491             hzp::scan_type nScanType     ///< new scan strategy
 492         )
 493         {
 494             hzp::GarbageCollector::instance().setScanType( nScanType );
 495         }
 496
 497         /// Checks if Hazard Pointer GC is constructed and may be used
 498         static bool isUsed()
 499         {
 500             return hzp::GarbageCollector::isUsed();
 501         }
 502
 503
 504         /// Forced GC cycle call for current thread
 505         /**
 506             Usually, this function should not be called directly.
 507         */
 508         static void scan()  ;   // inline in hp_impl.h
 509
 510         /// Synonym for \ref scan()
 511         static void force_dispose()
 512         {
 513             scan();
 514         }
 515     };
 516 }}  // namespace cds::gc
 517
 518 #endif  // #ifndef __CDS_GC_HP_DECL_H