cds/gc/impl/hp_decl.h

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