cds/gc/details/hp.h

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