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