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