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             /// Copy from \p src guard to \p this guard
 226             void copy( Guard const& src )
 227             {
 228                 assign( src.get_native() );
 229             }
 230
 231             /// Store marked pointer \p p to the guard
 232             /**
 233                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 234                 Can be used for a marked pointer that cannot be changed concurrently.
 235             */
 236             template <typename T, int BITMASK>
 237             T * assign( cds::details::marked_ptr<T, BITMASK> p )
 238             {
 239                 return base_class::operator =( p.ptr() );
 240             }
 241
 242             /// Clear value of the guard
 243             void clear()
 244             {
 245                 assign( reinterpret_cast<void *>(NULL) );
 246             }
 247
 248             /// Get the value currently protected
 249             template <typename T>
 250             T * get() const
 251             {
 252                 return reinterpret_cast<T *>( get_native() );
 253             }
 254
 255             /// Get native hazard pointer stored
 256             guarded_pointer get_native() const
 257             {
 258                 return base_class::get();
 259             }
 260         };
 261
 262         /// Array of Hazard Pointer guards
 263         /**
 264             @headerfile cds/gc/hp.h
 265             This class is a wrapper for hzp::AutoHPArray template.
 266             Template parameter \p Count defines the size of HP array.
 267         */
 268         template <size_t Count>
 269         class GuardArray: public hzp::AutoHPArray<Count>
 270         {
 271             //@cond
 272             typedef hzp::AutoHPArray<Count> base_class;
 273             //@endcond
 274         public:
 275             /// Rebind array for other size \p Count2
 276             template <size_t Count2>
 277             struct rebind {
 278                 typedef GuardArray<Count2>  other   ;   ///< rebinding result
 279             };
 280
 281         public:
 282             //@cond
 283             GuardArray()    ;   // inline in hp_impl.h
 284             //@endcond
 285             /// Protects a pointer of type \p atomic<T*>
 286             /**
 287                 Return the value of \p toGuard
 288
 289                 The function tries to load \p toGuard and to store it
 290                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 291             */
 292             template <typename T>
 293             T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard )
 294             {
 295                 T pRet;
 296                 do {
 297                     pRet = assign( nIndex, toGuard.load(CDS_ATOMIC::memory_order_acquire) );
 298                 } while ( pRet != toGuard.load(CDS_ATOMIC::memory_order_relaxed));
 299
 300                 return pRet;
 301             }
 302
 303             /// Protects a pointer of type \p atomic<T*>
 304             /**
 305                 Return the value of \p toGuard
 306
 307                 The function tries to load \p toGuard and to store it
 308                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
 309
 310                 The function is useful for intrusive containers when \p toGuard is a node pointer
 311                 that should be converted to a pointer to the value type before guarding.
 312                 The parameter \p f of type Func is a functor that makes this conversion:
 313                 \code
 314                     struct functor {
 315                         value_type * operator()( T * p );
 316                     };
 317                 \endcode
 318                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
 319             */
 320             template <typename T, class Func>
 321             T protect(size_t nIndex, CDS_ATOMIC::atomic<T> const& toGuard, Func f )
 322             {
 323                 T pRet;
 324                 do {
 325                     assign( nIndex, f( pRet = toGuard.load(CDS_ATOMIC::memory_order_acquire) ));
 326                 } while ( pRet != toGuard.load(CDS_ATOMIC::memory_order_relaxed));
 327
 328                 return pRet;
 329             }
 330
 331             /// Store \p to the slot \p nIndex
 332             /**
 333                 The function equals to a simple assignment, no loop is performed.
 334             */
 335             template <typename T>
 336             T * assign( size_t nIndex, T * p )
 337             {
 338                 base_class::set(nIndex, p);
 339                 return p;
 340             }
 341
 342             /// Store marked pointer \p p to the guard
 343             /**
 344                 The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
 345                 Can be used for a marked pointer that cannot be changed concurrently.
 346             */
 347             template <typename T, int BITMASK>
 348             T * assign( size_t nIndex, cds::details::marked_ptr<T, BITMASK> p )
 349             {
 350                 return assign( nIndex, p.ptr() );
 351             }
 352
 353             /// Copy guarded value from \p src guard to slot at index \p nIndex
 354             void copy( size_t nIndex, Guard const& src )
 355             {
 356                 assign( nIndex, src.get_native() );
 357             }
 358
 359             /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
 360             void copy( size_t nDestIndex, size_t nSrcIndex )
 361             {
 362                 assign( nDestIndex, get_native( nSrcIndex ));
 363             }
 364
 365             /// Clear value of the slot \p nIndex
 366             void clear( size_t nIndex)
 367             {
 368                 base_class::clear( nIndex );
 369             }
 370
 371             /// Get current value of slot \p nIndex
 372             template <typename T>
 373             T * get( size_t nIndex) const
 374             {
 375                 return reinterpret_cast<T *>( get_native( nIndex ) );
 376             }
 377
 378             /// Get native hazard pointer stored
 379             guarded_pointer get_native( size_t nIndex ) const
 380             {
 381                 return base_class::operator[](nIndex).get();
 382             }
 383
 384             /// Capacity of the guard array
 385             static CDS_CONSTEXPR size_t capacity()
 386             {
 387                 return Count;
 388             }
 389         };
 390
 391     public:
 392         /// Initializes hzp::GarbageCollector singleton
 393         /**
 394             The constructor initializes GC singleton with passed parameters.
 395             If GC instance is not exist then the function creates the instance.
 396             Otherwise it does nothing.
 397
 398             The Michael's HP reclamation schema depends of three parameters:
 399             - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from
 400                 the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function
 401                 uses maximum of the hazard pointer count for CDS library.
 402             - \p nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
 403             - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
 404                 <tt> nHazardPtrCount * nMaxThreadCount </tt>. Default is <tt>2 * nHazardPtrCount * nMaxThreadCount </tt>.
 405         */
 406         HP(
 407             size_t nHazardPtrCount = 0,     ///< Hazard pointer count per thread
 408             size_t nMaxThreadCount = 0,     ///< Max count of simultaneous working thread in your application
 409             size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
 410             hzp::scan_type nScanType = hzp::inplace   ///< Scan type (see \ref hzp::scan_type enum)
 411         )
 412         {
 413             hzp::GarbageCollector::Construct(
 414                 nHazardPtrCount,
 415                 nMaxThreadCount,
 416                 nMaxRetiredPtrCount,
 417                 nScanType
 418             );
 419         }
 420
 421         /// Terminates GC singleton
 422         /**
 423             The destructor calls \code hzp::GarbageCollector::Destruct( true ) \endcode
 424         */
 425         ~HP()
 426         {
 427             hzp::GarbageCollector::Destruct( true );
 428         }
 429
 430         /// Checks if count of hazard pointer is no less than \p nCountNeeded
 431         /**
 432             If \p bRaiseException is \p true (that is the default), the function raises an exception gc::too_few_hazard_pointers
 433             if \p nCountNeeded is more than the count of hazard pointer per thread.
 434         */
 435         static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
 436         {
 437             if ( hzp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
 438                 if ( bRaiseException )
 439                     throw cds::gc::too_few_hazard_pointers();
 440                 return false;
 441             }
 442             return true;
 443         }
 444
 445         /// Returns max Hazard Pointer count
 446         size_t max_hazard_count() const
 447         {
 448             return hzp::GarbageCollector::instance().getHazardPointerCount();
 449         }
 450
 451         /// Returns max count of thread
 452         size_t max_thread_count() const
 453         {
 454             return hzp::GarbageCollector::instance().getMaxThreadCount();
 455         }
 456
 457         /// Returns capacity of retired pointer array
 458         size_t retired_array_capacity() const
 459         {
 460             return hzp::GarbageCollector::instance().getMaxRetiredPtrCount();
 461         }
 462
 463         /// Retire pointer \p p with function \p pFunc
 464         /**
 465             The function places pointer \p p to array of pointers ready for removing.
 466             (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
 467             Deleting the pointer is the function \p pFunc call.
 468         */
 469         template <typename T>
 470         static void retire( T * p, void (* pFunc)(T *) )    ;   // inline in hp_impl.h
 471
 472         /// Retire pointer \p p with functor of type \p Disposer
 473         /**
 474             The function places pointer \p p to array of pointers ready for removing.
 475             (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.
 476
 477             Deleting the pointer is an invocation of some object of type \p Disposer; the interface of \p Disposer is:
 478             \code
 479             template <typename T>
 480             struct disposer {
 481                 void operator()( T * p )    ;   // disposing operator
 482             };
 483             \endcode
 484             Since the functor call can happen at any time after \p retire call, additional restrictions are imposed to \p Disposer type:
 485             - it should be stateless functor
 486             - it should be default-constructible
 487             - the result of functor call with argument \p p should not depend on where the functor will be called.
 488
 489             \par Examples:
 490             Operator \p delete functor:
 491             \code
 492             template <typename T>
 493             struct disposer {
 494                 void operator ()( T * p ) {
 495                     delete p;
 496                 }
 497             };
 498
 499             // How to call GC::retire method
 500             int * p = new int;
 501
 502             // ... use p in lock-free manner
 503
 504             cds::gc::HP::retire<disposer>( p ) ;   // place p to retired pointer array of HP GC
 505             \endcode
 506
 507             Functor based on \p std::allocator :
 508             \code
 509             template <typename ALLOC = std::allocator<int> >
 510             struct disposer {
 511                 template <typename T>
 512                 void operator()( T * p ) {
 513                     typedef typename ALLOC::templare rebind<T>::other   alloc_t;
 514                     alloc_t a;
 515                     a.destroy( p );
 516                     a.deallocate( p, 1 );
 517                 }
 518             };
 519             \endcode
 520         */
 521         template <class Disposer, typename T>
 522         static void retire( T * p ) ;   // inline in hp_impl.h
 523
 524         /// Get current scan strategy
 525         /**@anchor hrc_gc_HP_getScanType
 526             See hzp::GarbageCollector::Scan for scan algo description
 527         */
 528         hzp::scan_type getScanType() const
 529         {
 530             return hzp::GarbageCollector::instance().getScanType();
 531         }
 532
 533         /// Set current scan strategy
 534         /**
 535             Scan strategy changing is allowed on the fly.
 536
 537             About scan strategy see \ref hrc_gc_HP_getScanType "getScanType"
 538         */
 539         void setScanType(
 540             hzp::scan_type nScanType     ///< new scan strategy
 541         )
 542         {
 543             hzp::GarbageCollector::instance().setScanType( nScanType );
 544         }
 545
 546         /// Checks if Hazard Pointer GC is constructed and may be used
 547         static bool isUsed()
 548         {
 549             return hzp::GarbageCollector::isUsed();
 550         }
 551
 552
 553         /// Forced GC cycle call for current thread
 554         /**
 555             Usually, this function should not be called directly.
 556         */
 557         static void scan()  ;   // inline in hp_impl.h
 558
 559         /// Synonym for \ref scan()
 560         static void force_dispose()
 561         {
 562             scan();
 563         }
 564     };
 565 }}  // namespace cds::gc
 566
 567 #endif  // #ifndef __CDS_GC_HP_DECL_H