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