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         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 )
 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_relaxed) );
 269                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 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 )
 293             {
 294                 T pRet;
 295                 do {
 296                     assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
 297                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
 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         /// \p scan() type
 364         enum class scan_type {
 365             classic = hp::classic,    ///< classic scan as described in Michael's papers
 366             inplace = hp::inplace     ///< inplace scan without allocation
 367         };
 368         /// Initializes hp::GarbageCollector singleton
 369         /**
 370             The constructor initializes GC singleton with passed parameters.
 371             If GC instance is not exist then the function creates the instance.
 372             Otherwise it does nothing.
 373
 374             The Michael's HP reclamation schema depends of three parameters:
 375             - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
 376                 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
 377                 uses maximum of the hazard pointer count for CDS library.
 378             - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
 379             - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
 380                 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
 381         */
 382         HP(
 383             size_t nHazardPtrCount = 0,     ///< Hazard pointer count per thread
 384             size_t nMaxThreadCount = 0,     ///< Max count of simultaneous working thread in your application
 385             size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
 386             scan_type nScanType = scan_type::inplace   ///< Scan type (see \p scan_type enum)
 387         )
 388         {
 389             hp::GarbageCollector::Construct(
 390                 nHazardPtrCount,
 391                 nMaxThreadCount,
 392                 nMaxRetiredPtrCount,
 393                 static_cast<hp::scan_type>(nScanType)
 394             );
 395         }
 396
 397         /// Terminates GC singleton
 398         /**
 399             The destructor calls \code hp::GarbageCollector::Destruct( true ) \endcode
 400         */
 401         ~HP()
 402         {
 403             hp::GarbageCollector::Destruct( true );
 404         }
 405
 406         /// Checks if count of hazard pointer is no less than \p nCountNeeded
 407         /**
 408             If \p bRaiseException is \p true (that is the default), the function raises
 409             an \p std::overflow_error exception "Too few hazard pointers"
 410             if \p nCountNeeded is more than the count of hazard pointer per thread.
 411         */
 412         static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
 413         {
 414             if ( hp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
 415                 if ( bRaiseException )
 416                     throw std::overflow_error( "Too few hazard pointers" );
 417                 return false;
 418             }
 419             return true;
 420         }
 421
 422         /// Returns max Hazard Pointer count
 423         static size_t max_hazard_count()
 424         {
 425             return hp::GarbageCollector::instance().getHazardPointerCount();
 426         }
 427
 428         /// Returns max count of thread
 429         static size_t max_thread_count()
 430         {
 431             return hp::GarbageCollector::instance().getMaxThreadCount();
 432         }
 433
 434         /// Returns capacity of retired pointer array
 435         static size_t retired_array_capacity()
 436         {
 437             return hp::GarbageCollector::instance().getMaxRetiredPtrCount();
 438         }
 439
 440         /// Retire pointer \p p with function \p pFunc
 441         /**
 442             The function places pointer \p p to array of pointers ready for removing.
 443             (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
 444             Deleting the pointer is the function \p pFunc call.
 445         */
 446         template <typename T>
 447         static void retire( T * p, void (* pFunc)(T *) )    ;   // inline in hp_impl.h
 448
 449         /// Retire pointer \p p with functor of type \p Disposer
 450         /**
 451             The function places pointer \p p to array of pointers ready for removing.
 452             (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
 453
 454             Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
 455             \code
 456             template <typename T>
 457             struct disposer {
 458                 void operator()( T * p )    ;   // disposing operator
 459             };
 460             \endcode
 461             Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
 462             - it should be stateless functor
 463             - it should be default-constructible
 464             - the result of functor call with argument \p p should not depend on where the functor will be called.
 465
 466             \par Examples:
 467             Operator \p delete functor:
 468             \code
 469             template <typename T>
 470             struct disposer {
 471                 void operator ()( T * p ) {
 472                     delete p;
 473                 }
 474             };
 475
 476             // How to call GC::retire method
 477             int * p = new int;
 478
 479             // ... use p in lock-free manner
 480
 481             cds::gc::HP::retire<disposer>( p ) ;   // place p to retired pointer array of HP GC
 482             \endcode
 483
 484             Functor based on \p std::allocator :
 485             \code
 486             template <typename ALLOC = std::allocator<int> >
 487             struct disposer {
 488                 template <typename T>
 489                 void operator()( T * p ) {
 490                     typedef typename ALLOC::templare rebind<T>::other   alloc_t;
 491                     alloc_t a;
 492                     a.destroy( p );
 493                     a.deallocate( p, 1 );
 494                 }
 495             };
 496             \endcode
 497         */
 498         template <class Disposer, typename T>
 499         static void retire( T * p ) ;   // inline in hp_impl.h
 500
 501         /// Get current scan strategy
 502         static scan_type getScanType()
 503         {
 504             return static_cast<scan_type>( hp::GarbageCollector::instance().getScanType());
 505         }
 506
 507         /// Set current scan strategy
 508         static void setScanType(
 509             scan_type nScanType     ///< new scan strategy
 510         )
 511         {
 512             hp::GarbageCollector::instance().setScanType( static_cast<hp::scan_type>(nScanType) );
 513         }
 514
 515         /// Checks if Hazard Pointer GC is constructed and may be used
 516         static bool isUsed()
 517         {
 518             return hp::GarbageCollector::isUsed();
 519         }
 520
 521         /// Forced GC cycle call for current thread
 522         /**
 523             Usually, this function should not be called directly.
 524         */
 525         static void scan()  ;   // inline in hp_impl.h
 526
 527         /// Synonym for \ref scan()
 528         static void force_dispose()
 529         {
 530             scan();
 531         }
 532     };
 533 }}  // namespace cds::gc
 534
 535 #endif  // #ifndef __CDS_GC_IMPL_HP_DECL_H