cds/gc/impl/hp_decl.h

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