cds/gc/details/hp.h

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