cds/gc/details/hp.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_GC_DETAILS_HP_H
   4 #define CDSLIB_GC_DETAILS_HP_H
   5
   6 #include <cds/algo/atomic.h>
   7 #include <cds/os/thread.h>
   8 #include <cds/details/bounded_array.h>
   9 #include <cds/user_setup/cache_line.h>
  10
  11 #include <cds/gc/details/hp_type.h>
  12 #include <cds/gc/details/hp_alloc.h>
  13
  14 #if CDS_COMPILER == CDS_COMPILER_MSVC
  15 #   pragma warning(push)
  16     // warning C4251: 'cds::gc::hp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomic::atomic<T>'
  17     // needs to have dll-interface to be used by clients of class 'cds::gc::hp::GarbageCollector'
  18 #   pragma warning(disable: 4251)
  19 #endif
  20
  21 /*
  22     Editions:
  23         2007.12.24  khizmax Add statistics and CDS_GATHER_HAZARDPTR_STAT macro
  24         2008.03.06  khizmax Refactoring: implementation of HazardPtrMgr is moved to hazardptr.cpp
  25         2008.03.08  khizmax Remove HazardPtrMgr singleton. Now you must initialize/destroy HazardPtrMgr calling
  26                             HazardPtrMgr::Construct / HazardPtrMgr::Destruct before use (usually in main() function).
  27         2008.12.06  khizmax Refactoring. Changes class name, namespace hierarchy, all helper defs have been moved to details namespace
  28         2010.01.27  khizmax Introducing memory order constraint
  29 */
  30
  31 //@cond
  32 namespace cds {
  33     /// Different safe memory reclamation schemas (garbage collectors)
  34     /** @ingroup cds_garbage_collector
  35
  36         This namespace specifies different safe memory reclamation (SMR) algorithms.
  37         See \ref cds_garbage_collector "Garbage collectors"
  38     */
  39     namespace gc {
  40
  41     /// Michael's Hazard Pointers reclamation schema
  42     /**
  43     \par Sources:
  44         - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
  45         - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
  46         - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
  47
  48         The \p cds::gc::hp namespace and its members are internal representation of Hazard Pointer GC and should not be used directly.
  49         Use \p cds::gc::HP class in your code.
  50
  51         Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is
  52         GC class and its nested classes. Before use any HP-related class you must initialize HP garbage collector
  53         by contructing \p cds::gc::HP object in beginning of your \p main().
  54         See \p cds::gc::HP class for explanation.
  55     */
  56     namespace hp {
  57
  58         // forwards
  59         class GarbageCollector;
  60         class ThreadGC;
  61
  62         namespace details {
  63
  64             /// Retired pointer
  65             typedef cds::gc::details::retired_ptr   retired_ptr;
  66
  67             /// Array of retired pointers
  68             /**
  69                 The vector of retired pointer ready to delete.
  70
  71                 The Hazard Pointer schema is build on thread-static arrays. For each HP-enabled thread the HP manager allocates
  72                 array of retired pointers. The array belongs to the thread: owner thread writes to the array, other threads
  73                 just read it.
  74             */
  75             class retired_vector {
  76                 /// Underlying vector implementation
  77                 typedef cds::details::bounded_array<retired_ptr>    retired_vector_impl;
  78
  79                 retired_vector_impl m_arr   ;   ///< the array of retired pointers
  80                 size_t              m_nSize ;   ///< Current size of \p m_arr
  81
  82             public:
  83                 /// Iterator
  84                 typedef retired_vector_impl::iterator  iterator;
  85
  86                 /// Constructor
  87                 retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
  88                 ~retired_vector()
  89                 {}
  90
  91                 /// Vector capacity.
  92                 /**
  93                     The capacity is constant for any thread. It is defined by cds::gc::hp::GarbageCollector.
  94                 */
  95                 size_t capacity() const CDS_NOEXCEPT
  96                 {
  97                     return m_arr.capacity();
  98                 }
  99
 100                 /// Current vector size (count of retired pointers in the vector)
 101                 size_t size() const CDS_NOEXCEPT
 102                 {
 103                     return m_nSize;
 104                 }
 105
 106                 /// Set vector size. Uses internally
 107                 void size( size_t nSize )
 108                 {
 109                     assert( nSize <= capacity() );
 110                     m_nSize = nSize;
 111                 }
 112
 113                 /// Pushes retired pointer to the vector
 114                 void push( retired_ptr const& p )
 115                 {
 116                     assert( m_nSize < capacity() );
 117                     m_arr[ m_nSize ] = p;
 118                     ++m_nSize;
 119                 }
 120
 121                 /// Checks if the vector is full (size() == capacity() )
 122                 bool isFull() const CDS_NOEXCEPT
 123                 {
 124                     return m_nSize >= capacity();
 125                 }
 126
 127                 /// Begin iterator
 128                 iterator    begin() CDS_NOEXCEPT
 129                 {
 130                     return m_arr.begin();
 131                 }
 132
 133                 /// End iterator
 134                 iterator    end() CDS_NOEXCEPT
 135                 {
 136                     return m_arr.begin() +  m_nSize;
 137                 }
 138
 139                 /// Clears the vector. After clearing, size() == 0
 140                 void clear() CDS_NOEXCEPT
 141                 {
 142                     m_nSize = 0;
 143                 }
 144             };
 145
 146             /// Hazard pointer record of the thread
 147             /**
 148                 The structure of type "single writer - multiple reader": only the owner thread may write to this structure
 149                 other threads have read-only access.
 150             */
 151             struct hp_record {
 152                 hp_allocator<>    m_hzp;         ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency
 153                 retired_vector    m_arrRetired ; ///< Retired pointer array
 154
 155                 char padding[cds::c_nCacheLineSize];
 156                 atomics::atomic<unsigned int> m_nSync; ///< dummy var to introduce synchronizes-with relationship between threads
 157
 158                 /// Ctor
 159                 hp_record( const cds::gc::hp::GarbageCollector& HzpMgr );    // inline
 160                 ~hp_record()
 161                 {}
 162
 163                 /// Clears all hazard pointers
 164                 void clear()
 165                 {
 166                     m_hzp.clear();
 167                 }
 168
 169                 void sync()
 170                 {
 171                     m_nSync.fetch_add( 1, atomics::memory_order_acq_rel );
 172                 }
 173             };
 174         }    // namespace details
 175
 176         /// GarbageCollector::Scan phase strategy
 177         /**
 178             See GarbageCollector::Scan for explanation
 179         */
 180         enum scan_type {
 181             classic,    ///< classic scan as described in Michael's works (see GarbageCollector::classic_scan)
 182             inplace     ///< inplace scan without allocation (see GarbageCollector::inplace_scan)
 183         };
 184
 185         /// Hazard Pointer singleton
 186         /**
 187             Safe memory reclamation schema by Michael "Hazard Pointers"
 188
 189         \par Sources:
 190             \li [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
 191             \li [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
 192             \li [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
 193
 194         */
 195         class CDS_EXPORT_API GarbageCollector
 196         {
 197         public:
 198             typedef cds::atomicity::event_counter  event_counter   ;   ///< event counter type
 199
 200             /// Internal GC statistics
 201             struct InternalState {
 202                 size_t              nHPCount                ;   ///< HP count per thread (const)
 203                 size_t              nMaxThreadCount         ;   ///< Max thread count (const)
 204                 size_t              nMaxRetiredPtrCount     ;   ///< Max retired pointer count per thread (const)
 205                 size_t              nHPRecSize              ;   ///< Size of HP record, bytes (const)
 206
 207                 size_t              nHPRecAllocated         ;   ///< Count of HP record allocations
 208                 size_t              nHPRecUsed              ;   ///< Count of HP record used
 209                 size_t              nTotalRetiredPtrCount   ;   ///< Current total count of retired pointers
 210                 size_t              nRetiredPtrInFreeHPRecs ;   ///< Count of retired pointer in free (unused) HP records
 211
 212                 event_counter::value_type   evcAllocHPRec   ;   ///< Count of \p hp_record allocations
 213                 event_counter::value_type   evcRetireHPRec  ;   ///< Count of \p hp_record retire events
 214                 event_counter::value_type   evcAllocNewHPRec;   ///< Count of new \p hp_record allocations from heap
 215                 event_counter::value_type   evcDeleteHPRec  ;   ///< Count of \p hp_record deletions
 216
 217                 event_counter::value_type   evcScanCall     ;   ///< Count of Scan calling
 218                 event_counter::value_type   evcHelpScanCall ;   ///< Count of HelpScan calling
 219                 event_counter::value_type   evcScanFromHelpScan;///< Count of Scan calls from HelpScan
 220
 221                 event_counter::value_type   evcDeletedNode  ;   ///< Count of deleting of retired objects
 222                 event_counter::value_type   evcDeferredNode ;   ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
 223             };
 224
 225             /// No GarbageCollector object is created
 226             class not_initialized : public std::runtime_error
 227             {
 228             public:
 229                 //@cond
 230                 not_initialized()
 231                     : std::runtime_error( "Global Hazard Pointer GarbageCollector is not initialized" )
 232                 {}
 233                 //@endcond
 234             };
 235
 236             /// Not enough required Hazard Pointer count
 237             class too_many_hazard_ptr : public std::length_error
 238             {
 239             public:
 240                 //@cond
 241                 too_many_hazard_ptr()
 242                     : std::length_error( "Not enough required Hazard Pointer count" )
 243                 {}
 244                 //@endcond
 245             };
 246
 247         private:
 248             /// Internal GC statistics
 249             struct Statistics {
 250                 event_counter  m_AllocHPRec            ;    ///< Count of \p hp_record allocations
 251                 event_counter  m_RetireHPRec            ;    ///< Count of \p hp_record retire events
 252                 event_counter  m_AllocNewHPRec            ;    ///< Count of new \p hp_record allocations from heap
 253                 event_counter  m_DeleteHPRec            ;    ///< Count of \p hp_record deletions
 254
 255                 event_counter  m_ScanCallCount            ;    ///< Count of Scan calling
 256                 event_counter  m_HelpScanCallCount        ;    ///< Count of HelpScan calling
 257                 event_counter  m_CallScanFromHelpScan    ;    ///< Count of Scan calls from HelpScan
 258
 259                 event_counter  m_DeletedNode            ;    ///< Count of retired objects deleting
 260                 event_counter  m_DeferredNode            ;    ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it
 261             };
 262
 263             /// Internal list of cds::gc::hp::details::hp_record
 264             struct hplist_node : public details::hp_record
 265             {
 266                 hplist_node *                    m_pNextNode; ///< next hazard ptr record in list
 267                 atomics::atomic<OS::ThreadId>    m_idOwner;   ///< Owner thread id; 0 - the record is free (not owned)
 268                 atomics::atomic<bool>            m_bFree;     ///< true if record if free (not owned)
 269
 270                 //@cond
 271                 hplist_node( const GarbageCollector& HzpMgr )
 272                     : hp_record( HzpMgr ),
 273                     m_pNextNode( nullptr ),
 274                     m_idOwner( OS::c_NullThreadId ),
 275                     m_bFree( true )
 276                 {}
 277
 278                 ~hplist_node()
 279                 {
 280                     assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId );
 281                     assert( m_bFree.load(atomics::memory_order_relaxed) );
 282                 }
 283                 //@endcond
 284             };
 285
 286             atomics::atomic<hplist_node *>   m_pListHead  ;  ///< Head of GC list
 287
 288             static GarbageCollector *    m_pHZPManager  ;   ///< GC instance pointer
 289
 290             Statistics              m_Stat              ;   ///< Internal statistics
 291             bool                    m_bStatEnabled      ;   ///< true - statistics enabled
 292
 293             const size_t            m_nHazardPointerCount   ;   ///< max count of thread's hazard pointer
 294             const size_t            m_nMaxThreadCount       ;   ///< max count of thread
 295             const size_t            m_nMaxRetiredPtrCount   ;   ///< max count of retired ptr per thread
 296             scan_type               m_nScanType             ;   ///< scan type (see \ref scan_type enum)
 297
 298
 299         private:
 300             /// Ctor
 301             GarbageCollector(
 302                 size_t nHazardPtrCount = 0,         ///< Hazard pointer count per thread
 303                 size_t nMaxThreadCount = 0,         ///< Max count of thread
 304                 size_t nMaxRetiredPtrCount = 0,     ///< Capacity of the array of retired objects
 305                 scan_type nScanType = inplace       ///< Scan type (see \ref scan_type enum)
 306             );
 307
 308             /// Dtor
 309             ~GarbageCollector();
 310
 311             /// Allocate new HP record
 312             hplist_node * NewHPRec();
 313
 314             /// Permanently deletes HPrecord \p pNode
 315             /**
 316                 Caveat: for performance reason this function is defined as inline and cannot be called directly
 317             */
 318             void                DeleteHPRec( hplist_node * pNode );
 319
 320             void detachAllThread();
 321
 322         public:
 323             /// Creates GarbageCollector singleton
 324             /**
 325                 GC is the singleton. If GC instance is not exist then the function creates the instance.
 326                 Otherwise it does nothing.
 327
 328                 The Michael's HP reclamation schema depends of three parameters:
 329
 330                 \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from
 331                                      the data structure algorithms. By default, if \p nHazardPtrCount = 0,
 332                                      the function uses maximum of HP count for CDS library.
 333
 334                 \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100.
 335
 336                 \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than
 337                                     \p nHazardPtrCount * \p nMaxThreadCount.
 338                                     Default is 2 * \p nHazardPtrCount * \p nMaxThreadCount.
 339             */
 340             static void    CDS_STDCALL Construct(
 341                 size_t nHazardPtrCount = 0,     ///< Hazard pointer count per thread
 342                 size_t nMaxThreadCount = 0,     ///< Max count of simultaneous working thread in your application
 343                 size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread
 344                 scan_type nScanType = inplace   ///< Scan type (see \ref scan_type enum)
 345             );
 346
 347             /// Destroys global instance of GarbageCollector
 348             /**
 349                 The parameter \p bDetachAll should be used carefully: if its value is \p true,
 350                 then the destroying GC automatically detaches all attached threads. This feature
 351                 can be useful when you have no control over the thread termination, for example,
 352                 when \p libcds is injected into existing external thread.
 353             */
 354             static void CDS_STDCALL Destruct(
 355                 bool bDetachAll = false     ///< Detach all threads
 356             );
 357
 358             /// Returns pointer to GarbageCollector instance
 359             static GarbageCollector&   instance()
 360             {
 361                 if ( !m_pHZPManager )
 362                     throw not_initialized();
 363                 return *m_pHZPManager;
 364             }
 365
 366             /// Checks if global GC object is constructed and may be used
 367             static bool isUsed() CDS_NOEXCEPT
 368             {
 369                 return m_pHZPManager != nullptr;
 370             }
 371
 372             /// Returns max Hazard Pointer count defined in construction time
 373             size_t            getHazardPointerCount() const CDS_NOEXCEPT
 374             {
 375                 return m_nHazardPointerCount;
 376             }
 377
 378             /// Returns max thread count defined in construction time
 379             size_t            getMaxThreadCount() const CDS_NOEXCEPT
 380             {
 381                 return m_nMaxThreadCount;
 382             }
 383
 384             /// Returns max size of retired objects array. It is defined in construction time
 385             size_t            getMaxRetiredPtrCount() const CDS_NOEXCEPT
 386             {
 387                 return m_nMaxRetiredPtrCount;
 388             }
 389
 390             // Internal statistics
 391
 392             /// Get internal statistics
 393             InternalState& getInternalState(InternalState& stat) const;
 394
 395             /// Checks if internal statistics enabled
 396             bool              isStatisticsEnabled() const { return m_bStatEnabled; }
 397
 398             /// Enables/disables internal statistics
 399             bool              enableStatistics( bool bEnable )
 400             {
 401                 bool bEnabled = m_bStatEnabled;
 402                 m_bStatEnabled = bEnable;
 403                 return bEnabled;
 404             }
 405
 406             /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
 407             /**
 408                 If \p nRequiredCount > getHazardPointerCount() then the exception \p too_many_hazard_ptr is thrown
 409             */
 410             static void checkHPCount( unsigned int nRequiredCount )
 411             {
 412                 if ( instance().getHazardPointerCount() < nRequiredCount )
 413                     throw too_many_hazard_ptr();
 414             }
 415
 416             /// Get current scan strategy
 417             scan_type getScanType() const
 418             {
 419                 return m_nScanType;
 420             }
 421
 422             /// Set current scan strategy
 423             /** @anchor hzp_gc_setScanType
 424                 Scan strategy changing is allowed on the fly.
 425             */
 426             void setScanType(
 427                 scan_type nScanType     ///< new scan strategy
 428             )
 429             {
 430                 m_nScanType = nScanType;
 431             }
 432
 433         public:    // Internals for threads
 434
 435             /// Allocates Hazard Pointer GC record. For internal use only
 436             details::hp_record * alloc_hp_record();
 437
 438             /// Free HP record. For internal use only
 439             void free_hp_record( details::hp_record * pRec );
 440
 441             /// The main garbage collecting function
 442             /**
 443                 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
 444                 is reached.
 445
 446                 There are the following scan algorithm:
 447                 - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use
 448                 - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory
 449
 450                 Use \ref hzp_gc_setScanType "setScanType" member function to setup appropriate scan algorithm.
 451             */
 452             void Scan( details::hp_record * pRec )
 453             {
 454                 switch ( m_nScanType ) {
 455                     case inplace:
 456                         inplace_scan( pRec );
 457                         break;
 458                     default:
 459                         assert(false)   ;   // Forgotten something?..
 460                     case classic:
 461                         classic_scan( pRec );
 462                         break;
 463                 }
 464             }
 465
 466             /// Helper scan routine
 467             /**
 468                 The function guarantees that every node that is eligible for reuse is eventually freed, barring
 469                 thread failures. To do so, after executing Scan, a thread executes a HelpScan,
 470                 where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers
 471                 to thread's list of reclaimed pointers.
 472
 473                 The function is called internally by Scan.
 474             */
 475             void HelpScan( details::hp_record * pThis );
 476
 477         protected:
 478             /// Classic scan algorithm
 479             /** @anchor hzp_gc_classic_scan
 480                 Classical scan algorithm as described in Michael's paper.
 481
 482                 A scan includes four stages. The first stage involves scanning the array HP for non-null values.
 483                 Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer.
 484                 Only stage 1 accesses shared variables. The following stages operate only on private variables.
 485
 486                 The second stage of a scan involves sorting local list of protected pointers to allow
 487                 binary search in the third stage.
 488
 489                 The third stage of a scan involves checking each reclaimed node
 490                 against the pointers in local list of protected pointers. If the binary search yields
 491                 no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list
 492                 of reclaimed pointers.
 493
 494                 The forth stage prepares new thread's private list of reclaimed pointers
 495                 that could not be freed during the current scan, where they remain until the next scan.
 496
 497                 This algorithm allocates memory for internal HP array.
 498
 499                 This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers
 500                 is reached.
 501             */
 502             void classic_scan( details::hp_record * pRec );
 503
 504             /// In-place scan algorithm
 505             /** @anchor hzp_gc_inplace_scan
 506                 Unlike the \ref hzp_gc_classic_scan "classic_scan" algorithm, \p inplace_scan does not allocate any memory.
 507                 All operations are performed in-place.
 508             */
 509             void inplace_scan( details::hp_record * pRec );
 510         };
 511
 512         /// Thread's hazard pointer manager
 513         /**
 514             To use Hazard Pointer reclamation schema each thread object must be linked with the object of ThreadGC class
 515             that interacts with GarbageCollector global object. The linkage is performed by calling \ref cds_threading "cds::threading::Manager::attachThread()"
 516             on the start of each thread that uses HP GC. Before terminating the thread linked to HP GC it is necessary to call
 517             \ref cds_threading "cds::threading::Manager::detachThread()".
 518         */
 519         class ThreadGC
 520         {
 521             GarbageCollector&    m_HzpManager; ///< Hazard Pointer GC singleton
 522             details::hp_record * m_pHzpRec;    ///< Pointer to thread's HZP record
 523
 524         public:
 525             /// Default constructor
 526             ThreadGC()
 527                 : m_HzpManager( GarbageCollector::instance() ),
 528                 m_pHzpRec( nullptr )
 529             {}
 530
 531             /// The object is not copy-constructible
 532             ThreadGC( ThreadGC const& ) = delete;
 533
 534             ~ThreadGC()
 535             {
 536                 fini();
 537             }
 538
 539             /// Checks if thread GC is initialized
 540             bool    isInitialized() const   { return m_pHzpRec != nullptr; }
 541
 542             /// Initialization. Repeat call is available
 543             void init()
 544             {
 545                 if ( !m_pHzpRec )
 546                     m_pHzpRec = m_HzpManager.alloc_hp_record();
 547             }
 548
 549             /// Finalization. Repeat call is available
 550             void fini()
 551             {
 552                 if ( m_pHzpRec ) {
 553                     details::hp_record * pRec = m_pHzpRec;
 554                     m_pHzpRec = nullptr;
 555                     m_HzpManager.free_hp_record( pRec );
 556                 }
 557             }
 558
 559             /// Initializes HP guard \p guard
 560             details::hp_guard& allocGuard()
 561             {
 562                 assert( m_pHzpRec );
 563                 return m_pHzpRec->m_hzp.alloc();
 564             }
 565
 566             /// Frees HP guard \p guard
 567             void freeGuard( details::hp_guard& guard )
 568             {
 569                 assert( m_pHzpRec );
 570                 m_pHzpRec->m_hzp.free( guard );
 571             }
 572
 573             /// Initializes HP guard array \p arr
 574             template <size_t Count>
 575             void allocGuard( details::hp_array<Count>& arr )
 576             {
 577                 assert( m_pHzpRec );
 578                 m_pHzpRec->m_hzp.alloc( arr );
 579             }
 580
 581             /// Frees HP guard array \p arr
 582             template <size_t Count>
 583             void freeGuard( details::hp_array<Count>& arr )
 584             {
 585                 assert( m_pHzpRec );
 586                 m_pHzpRec->m_hzp.free( arr );
 587             }
 588
 589             /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
 590             template <typename T>
 591             void retirePtr( T * p, void (* pFunc)(T *) )
 592             {
 593                 /*
 594                 union {
 595                     T * p;
 596                     hazard_pointer hp;
 597                 } cast_ptr;
 598                 cast_ptr.p = p;
 599
 600                 union{
 601                     void( *pFunc )(T *);
 602                     free_retired_ptr_func hpFunc;
 603                 } cast_func;
 604                 cast_func.pFunc = pFunc;
 605
 606                 retirePtr( details::retired_ptr( cast_ptr.hp, cast_func.hpFunc ) );
 607                 */
 608                 retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc )));
 609             }
 610
 611             /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation
 612             void retirePtr( details::retired_ptr const& p )
 613             {
 614                 m_pHzpRec->m_arrRetired.push( p );
 615
 616                 if ( m_pHzpRec->m_arrRetired.isFull() ) {
 617                     // Max of retired pointer count is reached. Do scan
 618                     scan();
 619                 }
 620             }
 621
 622             /// Run retiring scan cycle
 623             void scan()
 624             {
 625                 m_HzpManager.Scan( m_pHzpRec );
 626                 m_HzpManager.HelpScan( m_pHzpRec );
 627             }
 628
 629             void sync()
 630             {
 631                 assert( m_pHzpRec != nullptr );
 632                 m_pHzpRec->sync();
 633             }
 634         };
 635
 636         /// Auto hp_guard.
 637         /**
 638             This class encapsulates Hazard Pointer guard to protect a pointer against deletion.
 639             It allocates one HP from thread's HP array in constructor and free the hazard pointer allocated
 640             in destructor.
 641         */
 642         class guard
 643         {
 644             details::hp_guard&  m_hp    ; ///< Hazard pointer guarded
 645
 646         public:
 647             typedef details::hp_guard::hazard_ptr hazard_ptr ;  ///< Hazard pointer type
 648
 649         public:
 650             /// Allocates HP guard
 651             guard(); // inline in hp_impl.h
 652
 653             /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T
 654             template <typename T>
 655             explicit guard( T * p ); // inline in hp_impl.h
 656
 657             /// Frees HP guard. The pointer guarded may be deleted after this.
 658             ~guard(); // inline in hp_impl.h
 659
 660             /// Protects the pointer \p p against reclamation (guards the pointer).
 661             template <typename T>
 662             T * operator =( T * p )
 663             {
 664                 return m_hp = p;
 665             }
 666
 667             //@cond
 668             std::nullptr_t operator =(std::nullptr_t)
 669             {
 670                 return m_hp = nullptr;
 671             }
 672             //@endcond
 673
 674             /// Get raw guarded pointer
 675             hazard_ptr get() const
 676             {
 677                 return m_hp;
 678             }
 679         };
 680
 681         /// Auto-managed array of hazard pointers
 682         /**
 683             This class is wrapper around cds::gc::hp::details::hp_array class.
 684             \p Count is the size of HP array
 685         */
 686         template <size_t Count>
 687         class array : public details::hp_array<Count>
 688         {
 689         public:
 690             /// Rebind array for other size \p COUNT2
 691             template <size_t Count2>
 692             struct rebind {
 693                 typedef array<Count2>  other;   ///< rebinding result
 694             };
 695
 696         public:
 697             /// Allocates array of HP guard
 698             array(); // inline in hp_impl.h
 699
 700             /// Frees array of HP guard
 701             ~array(); //inline in hp_impl.h
 702         };
 703
 704     }   // namespace hp
 705 }}  // namespace cds::gc
 706 //@endcond
 707
 708 //@cond
 709 // Inlines
 710 namespace cds {
 711     namespace gc { namespace hp { namespace details {
 712
 713         inline retired_vector::retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr )
 714             : m_arr( HzpMgr.getMaxRetiredPtrCount() ),
 715             m_nSize(0)
 716         {}
 717
 718         inline hp_record::hp_record( const cds::gc::hp::GarbageCollector& HzpMgr )
 719             : m_hzp( HzpMgr.getHazardPointerCount() )
 720             , m_arrRetired( HzpMgr )
 721             , m_nSync( 0 )
 722         {}
 723
 724     }}} // namespace gc::hp::details
 725 } // namespace cds
 726 //@endcond
 727
 728
 729 #if CDS_COMPILER == CDS_COMPILER_MSVC
 730 #   pragma warning(pop)
 731 #endif
 732
 733 #endif  // #ifndef CDSLIB_GC_DETAILS_HP_H