cds/gc/details/dhp.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_GC_DETAILS_DHP_H
   4 #define CDSLIB_GC_DETAILS_DHP_H
   5
   6 #include <mutex>        // unique_lock
   7 #include <cds/algo/atomic.h>
   8 #include <cds/gc/details/retired_ptr.h>
   9 #include <cds/details/aligned_allocator.h>
  10 #include <cds/details/allocator.h>
  11 #include <cds/sync/spinlock.h>
  12
  13 #if CDS_COMPILER == CDS_COMPILER_MSVC
  14 #   pragma warning(push)
  15 #   pragma warning(disable:4251)    // C4251: 'identifier' : class 'type' needs to have dll-interface to be used by clients of class 'type2'
  16 #endif
  17
  18 //@cond
  19 namespace cds { namespace gc {
  20
  21     /// Dynamic Hazard Pointer reclamation schema
  22     /**
  23         The cds::gc::dhp namespace and its members are internal representation of the GC and should not be used directly.
  24         Use cds::gc::DHP class in your code.
  25
  26         Dynamic Hazard Pointer (DHP) garbage collector is a singleton. The main user-level part of DHP schema is
  27         GC class and its nested classes. Before use any DHP-related class you must initialize DHP garbage collector
  28         by contructing cds::gc::DHP object in beginning of your main().
  29         See cds::gc::DHP class for explanation.
  30
  31         \par Implementation issues
  32             The global list of free guards (\p cds::gc::dhp::details::guard_allocator) is protected by a spin-lock (i.e. serialized).
  33             It seems that this solution should not introduce significant performance bottleneck, because each thread has its own set
  34             of guards allocated from the global list of free guards and the access to the global list is occurred only when
  35             all thread's guard is busy. In this case the thread allocates a next block of guards from the global list.
  36             Guards allocated for the thread is push back to the global list only when the thread terminates.
  37     */
  38     namespace dhp {
  39
  40         // Forward declarations
  41         class Guard;
  42         template <size_t Count> class GuardArray;
  43         class ThreadGC;
  44         class GarbageCollector;
  45
  46         /// Retired pointer type
  47         typedef cds::gc::details::retired_ptr retired_ptr;
  48
  49         using cds::gc::details::free_retired_ptr_func;
  50
  51         /// Details of Dynamic Hazard Pointer algorithm
  52         namespace details {
  53
  54             // Forward declaration
  55             class liberate_set;
  56
  57             /// Retired pointer buffer node
  58             struct retired_ptr_node {
  59                 retired_ptr         m_ptr   ;   ///< retired pointer
  60                 atomics::atomic<retired_ptr_node *>  m_pNext     ;   ///< next retired pointer in buffer
  61                 atomics::atomic<retired_ptr_node *>  m_pNextFree ;   ///< next item in free list of \p retired_ptr_node
  62             };
  63
  64             /// Internal guard representation
  65             struct guard_data {
  66                 typedef void * guarded_ptr;  ///< type of value guarded
  67
  68                 atomics::atomic<guarded_ptr>  pPost;       ///< pointer guarded
  69                 atomics::atomic<guard_data *> pGlobalNext; ///< next item of global list of allocated guards
  70                 atomics::atomic<guard_data *> pNextFree;   ///< pointer to the next item in global or thread-local free-list
  71
  72                 guard_data * pThreadNext; ///< next item of thread's local list of guards
  73
  74                 guard_data() CDS_NOEXCEPT
  75                     : pPost( nullptr )
  76                     , pGlobalNext( nullptr )
  77                     , pNextFree( nullptr )
  78                     , pThreadNext( nullptr )
  79                 {}
  80
  81                 void init() CDS_NOEXCEPT
  82                 {
  83                     pPost.store( nullptr, atomics::memory_order_relaxed );
  84                 }
  85
  86                 /// Checks if the guard is free, that is, it does not contain any pointer guarded
  87                 bool isFree() const CDS_NOEXCEPT
  88                 {
  89                     return pPost.load( atomics::memory_order_acquire ) == nullptr;
  90                 }
  91             };
  92
  93             /// Guard allocator
  94             template <class Alloc = CDS_DEFAULT_ALLOCATOR>
  95             class guard_allocator
  96             {
  97                 cds::details::Allocator<details::guard_data>  m_GuardAllocator    ;   ///< guard allocator
  98
  99                 atomics::atomic<guard_data *>  m_GuardList;     ///< Head of allocated guard list (linked by guard_data::pGlobalNext field)
 100                 atomics::atomic<guard_data *>  m_FreeGuardList; ///< Head of free guard list (linked by guard_data::pNextFree field)
 101                 cds::sync::spin                m_freeListLock;  ///< Access to m_FreeGuardList
 102
 103                 /*
 104                     Unfortunately, access to the list of free guard is lock-based.
 105                     Lock-free manipulations with guard free-list are ABA-prone.
 106                     TODO: working with m_FreeGuardList in lock-free manner.
 107                 */
 108
 109             private:
 110                 /// Allocates new guard from the heap. The function uses aligned allocator
 111                 guard_data * allocNew()
 112                 {
 113                     //TODO: the allocator should make block allocation
 114
 115                     details::guard_data * pGuard = m_GuardAllocator.New();
 116
 117                     // Link guard to the list
 118                     // m_GuardList is an accumulating list and it cannot support concurrent deletion,
 119                     // so, ABA problem is impossible for it
 120                     details::guard_data * pHead = m_GuardList.load( atomics::memory_order_acquire );
 121                     do {
 122                         pGuard->pGlobalNext.store( pHead, atomics::memory_order_relaxed );
 123                         // pHead is changed by compare_exchange_weak
 124                     } while ( !m_GuardList.compare_exchange_weak( pHead, pGuard, atomics::memory_order_release, atomics::memory_order_relaxed ));
 125
 126                     pGuard->init();
 127                     return pGuard;
 128                 }
 129
 130             public:
 131                 // Default ctor
 132                 guard_allocator() CDS_NOEXCEPT
 133                     : m_GuardList( nullptr )
 134                     , m_FreeGuardList( nullptr )
 135                 {}
 136
 137                 // Destructor
 138                 ~guard_allocator()
 139                 {
 140                     guard_data * pNext;
 141                     for ( guard_data * pData = m_GuardList.load( atomics::memory_order_relaxed ); pData != nullptr; pData = pNext ) {
 142                         pNext = pData->pGlobalNext.load( atomics::memory_order_relaxed );
 143                         m_GuardAllocator.Delete( pData );
 144                     }
 145                 }
 146
 147                 /// Allocates a guard from free list or from heap if free list is empty
 148                 guard_data * alloc()
 149                 {
 150                     // Try to pop a guard from free-list
 151                     details::guard_data * pGuard;
 152
 153                     {
 154                         std::unique_lock<cds::sync::spin> al( m_freeListLock );
 155                         pGuard = m_FreeGuardList.load(atomics::memory_order_relaxed);
 156                         if ( pGuard )
 157                             m_FreeGuardList.store( pGuard->pNextFree.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
 158                     }
 159                     if ( !pGuard )
 160                         return allocNew();
 161
 162                     pGuard->init();
 163                     return pGuard;
 164                 }
 165
 166                 /// Frees guard \p pGuard
 167                 /**
 168                     The function places the guard \p pGuard into free-list
 169                 */
 170                 void free( guard_data * pGuard ) CDS_NOEXCEPT
 171                 {
 172                     pGuard->pPost.store( nullptr, atomics::memory_order_relaxed );
 173
 174                     std::unique_lock<cds::sync::spin> al( m_freeListLock );
 175                     pGuard->pNextFree.store( m_FreeGuardList.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
 176                     m_FreeGuardList.store( pGuard, atomics::memory_order_relaxed );
 177                 }
 178
 179                 /// Allocates list of guard
 180                 /**
 181                     The list returned is linked by guard's \p pThreadNext and \p pNextFree fields.
 182
 183                     cds::gc::dhp::ThreadGC supporting method
 184                 */
 185                 guard_data * allocList( size_t nCount )
 186                 {
 187                     assert( nCount != 0 );
 188
 189                     guard_data * pHead;
 190                     guard_data * pLast;
 191
 192                     pHead =
 193                         pLast = alloc();
 194
 195                     // The guard list allocated is private for the thread,
 196                     // so, we can use relaxed memory order
 197                     while ( --nCount ) {
 198                         guard_data * p = alloc();
 199                         pLast->pNextFree.store( pLast->pThreadNext = p, atomics::memory_order_relaxed );
 200                         pLast = p;
 201                     }
 202
 203                     pLast->pNextFree.store( pLast->pThreadNext = nullptr, atomics::memory_order_relaxed );
 204
 205                     return pHead;
 206                 }
 207
 208                 /// Frees list of guards
 209                 /**
 210                     The list \p pList is linked by guard's \p pThreadNext field.
 211
 212                     cds::gc::dhp::ThreadGC supporting method
 213                 */
 214                 void freeList( guard_data * pList ) CDS_NOEXCEPT
 215                 {
 216                     assert( pList != nullptr );
 217
 218                     guard_data * pLast = pList;
 219                     while ( pLast->pThreadNext ) {
 220                         pLast->pPost.store( nullptr, atomics::memory_order_relaxed );
 221                         guard_data * p;
 222                         pLast->pNextFree.store( p = pLast->pThreadNext, atomics::memory_order_relaxed );
 223                         pLast = p;
 224                     }
 225
 226                     std::unique_lock<cds::sync::spin> al( m_freeListLock );
 227                     pLast->pNextFree.store( m_FreeGuardList.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
 228                     m_FreeGuardList.store( pList, atomics::memory_order_relaxed );
 229                 }
 230
 231                 /// Returns the list's head of guards allocated
 232                 guard_data * begin() CDS_NOEXCEPT
 233                 {
 234                     return m_GuardList.load(atomics::memory_order_acquire);
 235                 }
 236             };
 237
 238             /// Retired pointer buffer
 239             /**
 240                 The buffer of retired nodes ready for liberating.
 241                 When size of buffer exceeds a threshold the GC calls \p scan() procedure to free
 242                 retired nodes.
 243             */
 244             class retired_ptr_buffer
 245             {
 246                 atomics::atomic<retired_ptr_node *>  m_pHead     ;   ///< head of buffer
 247                 atomics::atomic<size_t>              m_nItemCount;   ///< buffer's item count
 248
 249             public:
 250                 retired_ptr_buffer() CDS_NOEXCEPT
 251                     : m_pHead( nullptr )
 252                     , m_nItemCount(0)
 253                 {}
 254
 255                 ~retired_ptr_buffer() CDS_NOEXCEPT
 256                 {
 257                     assert( m_pHead.load( atomics::memory_order_relaxed ) == nullptr );
 258                 }
 259
 260                 /// Pushes new node into the buffer. Returns current buffer size
 261                 size_t push( retired_ptr_node& node ) CDS_NOEXCEPT
 262                 {
 263                     retired_ptr_node * pHead = m_pHead.load(atomics::memory_order_acquire);
 264                     do {
 265                         node.m_pNext.store( pHead, atomics::memory_order_relaxed );
 266                         // pHead is changed by compare_exchange_weak
 267                     } while ( !m_pHead.compare_exchange_weak( pHead, &node, atomics::memory_order_release, atomics::memory_order_relaxed ));
 268
 269                     return m_nItemCount.fetch_add( 1, atomics::memory_order_relaxed ) + 1;
 270                 }
 271
 272                 /// Pushes [pFirst, pLast] list linked by pNext field.
 273                 size_t push_list( retired_ptr_node* pFirst, retired_ptr_node* pLast, size_t nSize )
 274                 {
 275                     assert( pFirst );
 276                     assert( pLast );
 277
 278                     retired_ptr_node * pHead = m_pHead.load( atomics::memory_order_acquire );
 279                     do {
 280                         pLast->m_pNext.store( pHead, atomics::memory_order_relaxed );
 281                         // pHead is changed by compare_exchange_weak
 282                     } while ( !m_pHead.compare_exchange_weak( pHead, pFirst, atomics::memory_order_release, atomics::memory_order_relaxed ) );
 283
 284                     return m_nItemCount.fetch_add( nSize, atomics::memory_order_relaxed ) + 1;
 285                 }
 286
 287                 /// Result of \ref dhp_gc_privatve "privatize" function.
 288                 /**
 289                     The \p privatize function returns retired node list as \p first and the size of that list as \p second.
 290                 */
 291                 typedef std::pair<retired_ptr_node *, size_t> privatize_result;
 292
 293                 /// Gets current list of retired pointer and clears the list
 294                 /**@anchor dhp_gc_privatve
 295                 */
 296                 privatize_result privatize() CDS_NOEXCEPT
 297                 {
 298                     privatize_result res;
 299                     res.first = m_pHead.exchange( nullptr, atomics::memory_order_acq_rel );
 300
 301                     // Item counter is needed only as a threshold for \p scan() function
 302                     // So, we may clear the item counter without synchronization with m_pHead
 303                     res.second = m_nItemCount.exchange( 0, atomics::memory_order_relaxed );
 304                     return res;
 305                 }
 306
 307                 /// Returns current size of buffer (approximate)
 308                 size_t size() const CDS_NOEXCEPT
 309                 {
 310                     return m_nItemCount.load(atomics::memory_order_relaxed);
 311                 }
 312             };
 313
 314             /// Pool of retired pointers
 315             /**
 316                 The class acts as an allocator of retired node.
 317                 Retired pointers are linked in the lock-free list.
 318             */
 319             template <class Alloc = CDS_DEFAULT_ALLOCATOR>
 320             class retired_ptr_pool {
 321                 /// Pool item
 322                 typedef retired_ptr_node    item;
 323
 324                 /// Count of items in block
 325                 static const size_t m_nItemPerBlock = 1024 / sizeof(item) - 1;
 326
 327                 /// Pool block
 328                 struct block {
 329                     atomics::atomic<block *> pNext;     ///< next block
 330                     item        items[m_nItemPerBlock]; ///< item array
 331                 };
 332
 333                 atomics::atomic<block *> m_pBlockListHead;   ///< head of of allocated block list
 334
 335                 // To solve ABA problem we use epoch-based approach
 336                 static const unsigned int c_nEpochCount = 4;    ///< Max epoch count
 337                 atomics::atomic<unsigned int> m_nCurEpoch;      ///< Current epoch
 338                 atomics::atomic<item *>  m_pEpochFree[c_nEpochCount];   ///< List of free item per epoch
 339                 atomics::atomic<item *>  m_pGlobalFreeHead;     ///< Head of unallocated item list
 340
 341                 cds::details::Allocator< block, Alloc > m_BlockAllocator    ;   ///< block allocator
 342
 343             private:
 344                 void allocNewBlock()
 345                 {
 346                     // allocate new block
 347                     block * pNew = m_BlockAllocator.New();
 348
 349                     // link items within the block
 350                     item * pLastItem = pNew->items + m_nItemPerBlock - 1;
 351                     for ( item * pItem = pNew->items; pItem != pLastItem; ++pItem ) {
 352                         pItem->m_pNextFree.store( pItem + 1, atomics::memory_order_release );
 353                         CDS_STRICT_DO( pItem->m_pNext.store( nullptr, atomics::memory_order_relaxed ));
 354                     }
 355
 356                     // links new block to the block list
 357                     {
 358                         block * pHead = m_pBlockListHead.load(atomics::memory_order_relaxed);
 359                         do {
 360                             pNew->pNext.store( pHead, atomics::memory_order_relaxed );
 361                             // pHead is changed by compare_exchange_weak
 362                         } while ( !m_pBlockListHead.compare_exchange_weak( pHead, pNew, atomics::memory_order_relaxed, atomics::memory_order_relaxed ));
 363                     }
 364
 365                     // links block's items to the free list
 366                     {
 367                         item * pHead = m_pGlobalFreeHead.load(atomics::memory_order_relaxed);
 368                         do {
 369                             pLastItem->m_pNextFree.store( pHead, atomics::memory_order_release );
 370                             // pHead is changed by compare_exchange_weak
 371                         } while ( !m_pGlobalFreeHead.compare_exchange_weak( pHead, pNew->items, atomics::memory_order_release, atomics::memory_order_relaxed ));
 372                     }
 373                 }
 374
 375                 unsigned int current_epoch() const CDS_NOEXCEPT
 376                 {
 377                     return m_nCurEpoch.load(atomics::memory_order_acquire) & (c_nEpochCount - 1);
 378                 }
 379
 380                 unsigned int next_epoch() const CDS_NOEXCEPT
 381                 {
 382                     return (m_nCurEpoch.load(atomics::memory_order_acquire) - 1) & (c_nEpochCount - 1);
 383                 }
 384
 385             public:
 386                 retired_ptr_pool()
 387                     : m_pBlockListHead( nullptr )
 388                     , m_nCurEpoch(0)
 389                     , m_pGlobalFreeHead( nullptr )
 390                 {
 391                     for (unsigned int i = 0; i < sizeof(m_pEpochFree)/sizeof(m_pEpochFree[0]); ++i )
 392                         m_pEpochFree[i].store( nullptr, atomics::memory_order_relaxed );
 393
 394                     allocNewBlock();
 395                 }
 396
 397                 ~retired_ptr_pool()
 398                 {
 399                     block * p;
 400                     for ( block * pBlock = m_pBlockListHead.load(atomics::memory_order_relaxed); pBlock; pBlock = p ) {
 401                         p = pBlock->pNext.load( atomics::memory_order_relaxed );
 402                         m_BlockAllocator.Delete( pBlock );
 403                     }
 404                 }
 405
 406                 /// Increments current epoch
 407                 void inc_epoch() CDS_NOEXCEPT
 408                 {
 409                     m_nCurEpoch.fetch_add( 1, atomics::memory_order_acq_rel );
 410                 }
 411
 412                 /// Allocates the new retired pointer
 413                 retired_ptr_node&  alloc()
 414                 {
 415                     unsigned int nEpoch;
 416                     item * pItem;
 417                     for (;;) {
 418                         pItem = m_pEpochFree[ nEpoch = current_epoch() ].load(atomics::memory_order_acquire);
 419                         if ( !pItem )
 420                             goto retry;
 421                         if ( m_pEpochFree[nEpoch].compare_exchange_weak( pItem,
 422                                                                          pItem->m_pNextFree.load(atomics::memory_order_acquire),
 423                                                                          atomics::memory_order_acquire, atomics::memory_order_relaxed ))
 424                         {
 425                             goto success;
 426                         }
 427                     }
 428
 429                     // Epoch free list is empty
 430                     // Alloc from global free list
 431                 retry:
 432                     pItem = m_pGlobalFreeHead.load( atomics::memory_order_relaxed );
 433                     do {
 434                         if ( !pItem ) {
 435                             allocNewBlock();
 436                             goto retry;
 437                         }
 438                         // pItem is changed by compare_exchange_weak
 439                     } while ( !m_pGlobalFreeHead.compare_exchange_weak( pItem,
 440                                                                         pItem->m_pNextFree.load(atomics::memory_order_acquire),
 441                                                                         atomics::memory_order_acquire, atomics::memory_order_relaxed ));
 442
 443                 success:
 444                     CDS_STRICT_DO( pItem->m_pNextFree.store( nullptr, atomics::memory_order_relaxed ));
 445                     return *pItem;
 446                 }
 447
 448                 /// Allocates and initializes new retired pointer
 449                 retired_ptr_node& alloc( const retired_ptr& p )
 450                 {
 451                     retired_ptr_node& node = alloc();
 452                     node.m_ptr = p;
 453                     return node;
 454                 }
 455
 456                 /// Places the list [pHead, pTail] of retired pointers to pool (frees retired pointers)
 457                 /**
 458                     The list is linked on the m_pNextFree field
 459                 */
 460                 void free_range( retired_ptr_node * pHead, retired_ptr_node * pTail ) CDS_NOEXCEPT
 461                 {
 462                     assert( pHead != nullptr );
 463                     assert( pTail != nullptr );
 464
 465                     unsigned int nEpoch;
 466                     item * pCurHead;
 467                     do {
 468                         pCurHead = m_pEpochFree[nEpoch = next_epoch()].load(atomics::memory_order_acquire);
 469                         pTail->m_pNextFree.store( pCurHead, atomics::memory_order_release );
 470                     } while ( !m_pEpochFree[nEpoch].compare_exchange_weak( pCurHead, pHead, atomics::memory_order_release, atomics::memory_order_relaxed ));
 471                 }
 472             };
 473
 474             /// Uninitialized guard
 475             class guard
 476             {
 477                 friend class dhp::ThreadGC;
 478             protected:
 479                 details::guard_data * m_pGuard ;    ///< Pointer to guard data
 480
 481             public:
 482                 /// Initialize empty guard.
 483                 CDS_CONSTEXPR guard() CDS_NOEXCEPT
 484                     : m_pGuard( nullptr )
 485                 {}
 486
 487                 /// Ñopy-ctor is disabled
 488                 guard( guard const& ) = delete;
 489
 490                 /// Move-ctor is disabled
 491                 guard( guard&& ) = delete;
 492
 493                 /// Object destructor, does nothing
 494                 ~guard() CDS_NOEXCEPT
 495                 {}
 496
 497                 /// Get current guarded pointer
 498                 void * get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT
 499                 {
 500                     assert( m_pGuard != nullptr );
 501                     return m_pGuard->pPost.load( order );
 502                 }
 503
 504                 /// Guards pointer \p p
 505                 void set( void * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
 506                 {
 507                     assert( m_pGuard != nullptr );
 508                     m_pGuard->pPost.store( p, order );
 509                 }
 510
 511                 /// Clears the guard
 512                 void clear( atomics::memory_order order = atomics::memory_order_relaxed ) CDS_NOEXCEPT
 513                 {
 514                     assert( m_pGuard != nullptr );
 515                     m_pGuard->pPost.store( nullptr, order );
 516                 }
 517
 518                 /// Guards pointer \p p
 519                 template <typename T>
 520                 T * operator =(T * p) CDS_NOEXCEPT
 521                 {
 522                     set( reinterpret_cast<void *>( const_cast<T *>(p) ));
 523                     return p;
 524                 }
 525
 526                 std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
 527                 {
 528                     clear();
 529                     return nullptr;
 530                 }
 531
 532             public: // for ThreadGC.
 533                 /*
 534                     GCC cannot compile code for template versions of ThreasGC::allocGuard/freeGuard,
 535                     the compiler produces error: \91cds::gc::dhp::details::guard_data* cds::gc::dhp::details::guard::m_pGuard\92 is protected
 536                     despite the fact that ThreadGC is declared as friend for guard class.
 537                     Therefore, we have to add set_guard/get_guard public functions
 538                 */
 539                 /// Set guard data
 540                 void set_guard( details::guard_data * pGuard ) CDS_NOEXCEPT
 541                 {
 542                     assert( m_pGuard == nullptr );
 543                     m_pGuard = pGuard;
 544                 }
 545
 546                 /// Get current guard data
 547                 details::guard_data * get_guard() CDS_NOEXCEPT
 548                 {
 549                     return m_pGuard;
 550                 }
 551                 /// Get current guard data
 552                 details::guard_data * get_guard() const CDS_NOEXCEPT
 553                 {
 554                     return m_pGuard;
 555                 }
 556
 557                 details::guard_data * release_guard() CDS_NOEXCEPT
 558                 {
 559                     details::guard_data * p = m_pGuard;
 560                     m_pGuard = nullptr;
 561                     return p;
 562                 }
 563
 564                 bool is_initialized() const
 565                 {
 566                     return m_pGuard != nullptr;
 567                 }
 568             };
 569
 570         } // namespace details
 571
 572         /// Guard
 573         /**
 574             This class represents auto guard: ctor allocates a guard from guard pool,
 575             dtor returns the guard back to the pool of free guard.
 576         */
 577         class Guard: public details::guard
 578         {
 579             typedef details::guard    base_class;
 580             friend class ThreadGC;
 581         public:
 582             /// Allocates a guard from \p gc GC. \p gc must be ThreadGC object of current thread
 583             Guard(); // inline in dhp_impl.h
 584
 585             /// Returns guard allocated back to pool of free guards
 586             ~Guard();    // inline in dhp_impl.h
 587
 588             /// Guards pointer \p p
 589             template <typename T>
 590             T * operator =(T * p) CDS_NOEXCEPT
 591             {
 592                 return base_class::operator =<T>( p );
 593             }
 594
 595             std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
 596             {
 597                 return base_class::operator =(nullptr);
 598             }
 599         };
 600
 601         /// Array of guards
 602         /**
 603             This class represents array of auto guards: ctor allocates \p Count guards from guard pool,
 604             dtor returns the guards allocated back to the pool.
 605         */
 606         template <size_t Count>
 607         class GuardArray
 608         {
 609             details::guard      m_arr[Count]    ;    ///< array of guard
 610             const static size_t c_nCapacity = Count ;   ///< Array capacity (equal to \p Count template parameter)
 611
 612         public:
 613             /// Rebind array for other size \p OtherCount
 614             template <size_t OtherCount>
 615             struct rebind {
 616                 typedef GuardArray<OtherCount>  other   ;   ///< rebinding result
 617             };
 618
 619         public:
 620             /// Allocates array of guards from \p gc which must be the ThreadGC object of current thread
 621             GuardArray();    // inline in dhp_impl.h
 622
 623             /// The object is not copy-constructible
 624             GuardArray( GuardArray const& ) = delete;
 625
 626             /// The object is not move-constructible
 627             GuardArray( GuardArray&& ) = delete;
 628
 629             /// Returns guards allocated back to pool
 630             ~GuardArray();    // inline in dh_impl.h
 631
 632             /// Returns the capacity of array
 633             CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT
 634             {
 635                 return c_nCapacity;
 636             }
 637
 638             /// Returns reference to the guard of index \p nIndex (0 <= \p nIndex < \p Count)
 639             details::guard& operator []( size_t nIndex ) CDS_NOEXCEPT
 640             {
 641                 assert( nIndex < capacity() );
 642                 return m_arr[nIndex];
 643             }
 644
 645             /// Returns reference to the guard of index \p nIndex (0 <= \p nIndex < \p Count) [const version]
 646             const details::guard& operator []( size_t nIndex ) const CDS_NOEXCEPT
 647             {
 648                 assert( nIndex < capacity() );
 649                 return m_arr[nIndex];
 650             }
 651
 652             /// Set the guard \p nIndex. 0 <= \p nIndex < \p Count
 653             template <typename T>
 654             void set( size_t nIndex, T * p ) CDS_NOEXCEPT
 655             {
 656                 assert( nIndex < capacity() );
 657                 m_arr[nIndex].set( p );
 658             }
 659
 660             /// Clears (sets to \p nullptr) the guard \p nIndex
 661             void clear( size_t nIndex ) CDS_NOEXCEPT
 662             {
 663                 assert( nIndex < capacity() );
 664                 m_arr[nIndex].clear();
 665             }
 666
 667             /// Clears all guards in the array
 668             void clearAll() CDS_NOEXCEPT
 669             {
 670                 for ( size_t i = 0; i < capacity(); ++i )
 671                     clear(i);
 672             }
 673         };
 674
 675         /// Memory manager (Garbage collector)
 676         class CDS_EXPORT_API GarbageCollector
 677         {
 678         private:
 679             friend class ThreadGC;
 680
 681             /// Internal GC statistics
 682             struct internal_stat
 683             {
 684                 atomics::atomic<size_t>  m_nGuardCount       ;   ///< Total guard count
 685                 atomics::atomic<size_t>  m_nFreeGuardCount   ;   ///< Count of free guard
 686
 687                 internal_stat()
 688                     : m_nGuardCount(0)
 689                     , m_nFreeGuardCount(0)
 690                 {}
 691             };
 692
 693         public:
 694             /// Exception "No GarbageCollector object is created"
 695             class not_initialized : public std::runtime_error
 696             {
 697             public:
 698                 //@cond
 699                 not_initialized()
 700                     : std::runtime_error( "Global DHP GarbageCollector is not initialized" )
 701                 {}
 702                 //@endcond
 703             };
 704
 705             /// Internal GC statistics
 706             struct InternalState
 707             {
 708                 size_t m_nGuardCount       ;   ///< Total guard count
 709                 size_t m_nFreeGuardCount   ;   ///< Count of free guard
 710
 711                 //@cond
 712                 InternalState()
 713                     : m_nGuardCount(0)
 714                     , m_nFreeGuardCount(0)
 715                 {}
 716
 717                 InternalState& operator =( internal_stat const& s )
 718                 {
 719                     m_nGuardCount = s.m_nGuardCount.load(atomics::memory_order_relaxed);
 720                     m_nFreeGuardCount = s.m_nFreeGuardCount.load(atomics::memory_order_relaxed);
 721
 722                     return *this;
 723                 }
 724                 //@endcond
 725             };
 726
 727         private:
 728             static GarbageCollector * m_pManager    ;   ///< GC global instance
 729
 730             details::guard_allocator<>      m_GuardPool         ;   ///< Guard pool
 731             details::retired_ptr_pool<>     m_RetiredAllocator  ;   ///< Pool of free retired pointers
 732             details::retired_ptr_buffer     m_RetiredBuffer     ;   ///< Retired pointer buffer for liberating
 733
 734             atomics::atomic<size_t>      m_nLiberateThreshold;   ///< Max size of retired pointer buffer to call \p scan()
 735             const size_t    m_nInitialThreadGuardCount; ///< Initial count of guards allocated for ThreadGC
 736
 737             internal_stat   m_stat  ;   ///< Internal statistics
 738             bool            m_bStatEnabled  ;   ///< Internal Statistics enabled
 739
 740         public:
 741             /// Initializes DHP memory manager singleton
 742             /**
 743                 This member function creates and initializes DHP global object.
 744                 The function should be called before using CDS data structure based on cds::gc::DHP GC. Usually,
 745                 this member function is called in the \p main() function. See cds::gc::dhp for example.
 746                 After calling of this function you may use CDS data structures based on cds::gc::DHP.
 747
 748                 \par Parameters
 749                 \li \p nLiberateThreshold - \p scan() threshold. When count of retired pointers reaches this value,
 750                     the \ref dhp_gc_liberate "scan()" member function would be called for freeing retired pointers.
 751                     If \p nLiberateThreshold <= 1, \p scan() would called after each \ref dhp_gc_retirePtr "retirePtr" call.
 752                 \li \p nInitialThreadGuardCount - initial count of guard allocated for ThreadGC. When a thread
 753                     is initialized the GC allocates local guard pool for the thread from common guard pool.
 754                     By perforce the local thread's guard pool is grown automatically from common pool.
 755                     When the thread terminated its guard pool is backed to common GC's pool.
 756
 757             */
 758             static void CDS_STDCALL Construct(
 759                 size_t nLiberateThreshold = 1024
 760                 , size_t nInitialThreadGuardCount = 8
 761             );
 762
 763             /// Destroys DHP memory manager
 764             /**
 765                 The member function destroys DHP global object. After calling of this function you may \b NOT
 766                 use CDS data structures based on cds::gc::DHP. Usually, the \p Destruct function is called
 767                 at the end of your \p main(). See cds::gc::dhp for example.
 768             */
 769             static void CDS_STDCALL Destruct();
 770
 771             /// Returns pointer to GarbageCollector instance
 772             /**
 773                 If DHP GC is not initialized, \p not_initialized exception is thrown
 774             */
 775             static GarbageCollector&   instance()
 776             {
 777                 if ( m_pManager == nullptr )
 778                     throw not_initialized();
 779                 return *m_pManager;
 780             }
 781
 782             /// Checks if global GC object is constructed and may be used
 783             static bool isUsed() CDS_NOEXCEPT
 784             {
 785                 return m_pManager != nullptr;
 786             }
 787
 788         public:
 789             //@{
 790             /// Internal interface
 791
 792             /// Allocates a guard
 793             details::guard_data * allocGuard()
 794             {
 795                 return m_GuardPool.alloc();
 796             }
 797
 798             /// Frees guard \p g for reusing in future
 799             void freeGuard(details::guard_data * pGuard )
 800             {
 801                 m_GuardPool.free( pGuard );
 802             }
 803
 804             /// Allocates guard list for a thread.
 805             details::guard_data * allocGuardList( size_t nCount )
 806             {
 807                 return m_GuardPool.allocList( nCount );
 808             }
 809
 810             /// Frees thread's guard list pointed by \p pList
 811             void freeGuardList( details::guard_data * pList )
 812             {
 813                 m_GuardPool.freeList( pList );
 814             }
 815
 816             /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
 817             /**@anchor dhp_gc_retirePtr
 818             */
 819             template <typename T>
 820             void retirePtr( T * p, void (* pFunc)(T *) )
 821             {
 822                 retirePtr( retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc ) ) );
 823             }
 824
 825             /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation
 826             void retirePtr( retired_ptr const& p )
 827             {
 828                 if ( m_RetiredBuffer.push( m_RetiredAllocator.alloc(p)) >= m_nLiberateThreshold.load(atomics::memory_order_relaxed) )
 829                     scan();
 830             }
 831
 832         protected:
 833             /// Liberate function
 834             /** @anchor dhp_gc_liberate
 835                 The main function of Dynamic Hazard Pointer algorithm. It tries to free retired pointers if they are not
 836                 trapped by any guard.
 837             */
 838             void scan();
 839             //@}
 840
 841         public:
 842             /// Get internal statistics
 843             InternalState& getInternalState(InternalState& stat) const
 844             {
 845                 return stat = m_stat;
 846             }
 847
 848             /// Checks if internal statistics enabled
 849             bool              isStatisticsEnabled() const
 850             {
 851                 return m_bStatEnabled;
 852             }
 853
 854             /// Enables/disables internal statistics
 855             bool  enableStatistics( bool bEnable )
 856             {
 857                 bool bEnabled = m_bStatEnabled;
 858                 m_bStatEnabled = bEnable;
 859                 return bEnabled;
 860             }
 861
 862         private:
 863             GarbageCollector( size_t nLiberateThreshold, size_t nInitialThreadGuardCount );
 864             ~GarbageCollector();
 865         };
 866
 867         /// Thread GC
 868         /**
 869             To use Dynamic Hazard Pointer reclamation schema each thread object must be linked with the object of ThreadGC class
 870             that interacts with GarbageCollector global object. The linkage is performed by calling \ref cds_threading "cds::threading::Manager::attachThread()"
 871             on the start of each thread that uses DHP GC. Before terminating the thread linked to DHP GC it is necessary to call
 872             \ref cds_threading "cds::threading::Manager::detachThread()".
 873
 874             The ThreadGC object maintains two list:
 875             \li Thread guard list: the list of thread-local guards (linked by \p pThreadNext field)
 876             \li Free guard list: the list of thread-local free guards (linked by \p pNextFree field)
 877             Free guard list is a subset of thread guard list.
 878         */
 879         class ThreadGC
 880         {
 881             GarbageCollector&   m_gc    ;   ///< reference to GC singleton
 882             details::guard_data *    m_pList ;   ///< Local list of guards owned by the thread
 883             details::guard_data *    m_pFree ;   ///< The list of free guard from m_pList
 884
 885         public:
 886             /// Default constructor
 887             ThreadGC()
 888                 : m_gc( GarbageCollector::instance() )
 889                 , m_pList( nullptr )
 890                 , m_pFree( nullptr )
 891             {}
 892
 893             /// The object is not copy-constructible
 894             ThreadGC( ThreadGC const& ) = delete;
 895
 896             /// Dtor calls fini()
 897             ~ThreadGC()
 898             {
 899                 fini();
 900             }
 901
 902             /// Initialization. Repeat call is available
 903             void init()
 904             {
 905                 if ( !m_pList ) {
 906                     m_pList =
 907                         m_pFree = m_gc.allocGuardList( m_gc.m_nInitialThreadGuardCount );
 908                 }
 909             }
 910
 911             /// Finalization. Repeat call is available
 912             void fini()
 913             {
 914                 if ( m_pList ) {
 915                     m_gc.freeGuardList( m_pList );
 916                     m_pList =
 917                         m_pFree = nullptr;
 918                 }
 919             }
 920
 921         public:
 922             /// Initializes guard \p g
 923             void allocGuard( dhp::details::guard& g )
 924             {
 925                 assert( m_pList != nullptr );
 926                 if ( !g.m_pGuard ) {
 927                     if ( m_pFree ) {
 928                         g.m_pGuard = m_pFree;
 929                         m_pFree = m_pFree->pNextFree.load( atomics::memory_order_relaxed );
 930                     }
 931                     else {
 932                         g.m_pGuard = m_gc.allocGuard();
 933                         g.m_pGuard->pThreadNext = m_pList;
 934                         m_pList = g.m_pGuard;
 935                     }
 936                 }
 937             }
 938
 939             /// Frees guard \p g
 940             void freeGuard( dhp::details::guard& g )
 941             {
 942                 assert( m_pList != nullptr );
 943                 if ( g.m_pGuard ) {
 944                     g.m_pGuard->pPost.store( nullptr, atomics::memory_order_relaxed );
 945                     g.m_pGuard->pNextFree.store( m_pFree, atomics::memory_order_relaxed );
 946                     m_pFree = g.m_pGuard;
 947                     g.m_pGuard = nullptr;
 948                 }
 949             }
 950
 951             /// Initializes guard array \p arr
 952             template <size_t Count>
 953             void allocGuard( GuardArray<Count>& arr )
 954             {
 955                 assert( m_pList != nullptr );
 956                 size_t nCount = 0;
 957
 958                 while ( m_pFree && nCount < Count ) {
 959                     arr[nCount].set_guard( m_pFree );
 960                     m_pFree = m_pFree->pNextFree.load(atomics::memory_order_relaxed);
 961                     ++nCount;
 962                 }
 963
 964                 while ( nCount < Count ) {
 965                     details::guard& g = arr[nCount++];
 966                     g.set_guard( m_gc.allocGuard() );
 967                     g.get_guard()->pThreadNext = m_pList;
 968                     m_pList = g.get_guard();
 969                 }
 970             }
 971
 972             /// Frees guard array \p arr
 973             template <size_t Count>
 974             void freeGuard( GuardArray<Count>& arr )
 975             {
 976                 assert( m_pList != nullptr );
 977
 978                 details::guard_data * pGuard;
 979                 for ( size_t i = 0; i < Count - 1; ++i ) {
 980                     pGuard = arr[i].get_guard();
 981                     pGuard->pPost.store( nullptr, atomics::memory_order_relaxed );
 982                     pGuard->pNextFree.store( arr[i+1].get_guard(), atomics::memory_order_relaxed );
 983                 }
 984                 pGuard = arr[Count-1].get_guard();
 985                 pGuard->pPost.store( nullptr, atomics::memory_order_relaxed );
 986                 pGuard->pNextFree.store( m_pFree, atomics::memory_order_relaxed );
 987                 m_pFree = arr[0].get_guard();
 988             }
 989
 990             /// Places retired pointer \p and its deleter \p pFunc into list of retired pointer for deferred reclamation
 991             template <typename T>
 992             void retirePtr( T * p, void (* pFunc)(T *) )
 993             {
 994                 m_gc.retirePtr( p, pFunc );
 995             }
 996
 997             /// Run retiring cycle
 998             void scan()
 999             {
1000                 m_gc.scan();
1001             }
1002         };
1003     }   // namespace dhp
1004 }}  // namespace cds::gc
1005 //@endcond
1006
1007 #if CDS_COMPILER == CDS_COMPILER_MSVC
1008 #   pragma warning(pop)
1009 #endif
1010
1011 #endif // #ifndef CDSLIB_GC_DETAILS_DHP_H