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