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