cds/gc/hp/hp_decl.h

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