src/ptb_gc.cpp

   1 //$$CDS-header$$
   2
   3 // Pass The Buck (PTB) Memory manager implementation
   4
   5 #include <algorithm>   // std::fill
   6 #include <functional>  // std::hash
   7
   8 #include <cds/gc/ptb/ptb.h>
   9 #include <cds/algo/int_algo.h>
  10
  11 namespace cds { namespace gc { namespace ptb {
  12
  13     namespace details {
  14
  15         class liberate_set {
  16             typedef retired_ptr_node *  item_type;
  17             typedef cds::details::Allocator<item_type, CDS_DEFAULT_ALLOCATOR>   allocator_type;
  18
  19             size_t const m_nBucketCount;
  20             item_type *  m_Buckets;
  21
  22             item_type&  bucket( retired_ptr_node& node )
  23             {
  24                 return bucket( node.m_ptr.m_p );
  25             }
  26             item_type&  bucket( guard_data::guarded_ptr p )
  27             {
  28                 return m_Buckets[ std::hash<guard_data::guarded_ptr>()( p ) & (m_nBucketCount - 1)  ];
  29             }
  30
  31         public:
  32             liberate_set( size_t nBucketCount )
  33                 : m_nBucketCount( nBucketCount )
  34             {
  35                 assert( nBucketCount > 0 );
  36                 assert( (nBucketCount & (nBucketCount - 1)) == 0 );
  37
  38                 m_Buckets = allocator_type().NewArray( nBucketCount );
  39                 std::fill( m_Buckets, m_Buckets + nBucketCount, nullptr );
  40             }
  41
  42             ~liberate_set()
  43             {
  44                 allocator_type().Delete( m_Buckets, m_nBucketCount );
  45             }
  46
  47             void insert( retired_ptr_node& node )
  48             {
  49                 node.m_pNext = nullptr;
  50
  51                 item_type& refBucket = bucket( node );
  52                 if ( refBucket ) {
  53                     item_type p = refBucket;
  54                     do {
  55                         if ( p->m_ptr.m_p == node.m_ptr.m_p ) {
  56                             assert( node.m_pNextFree == nullptr );
  57
  58                             node.m_pNextFree = p->m_pNextFree;
  59                             p->m_pNextFree = &node;
  60                             return;
  61                         }
  62                         p = p->m_pNext;
  63                     } while ( p );
  64
  65                     node.m_pNext = refBucket;
  66                 }
  67                 refBucket = &node;
  68             }
  69
  70             item_type erase( guard_data::guarded_ptr ptr )
  71             {
  72                 item_type& refBucket = bucket( ptr );
  73                 item_type p = refBucket;
  74                 item_type pPrev = nullptr;
  75
  76                 while ( p ) {
  77                     if ( p->m_ptr.m_p == ptr ) {
  78                         if ( pPrev )
  79                             pPrev->m_pNext = p->m_pNext;
  80                         else
  81                             refBucket = p->m_pNext;
  82                         p->m_pNext = nullptr;
  83                         return p;
  84                     }
  85                     pPrev = p;
  86                     p = p->m_pNext;
  87                 }
  88
  89                 return nullptr;
  90             }
  91
  92             typedef std::pair<item_type, item_type>     list_range;
  93
  94             list_range free_all()
  95             {
  96                 item_type pTail = nullptr;
  97                 list_range ret = std::make_pair( pTail, pTail );
  98
  99                 item_type const * pEndBucket = m_Buckets + m_nBucketCount;
 100                 for ( item_type * ppBucket = m_Buckets; ppBucket < pEndBucket; ++ppBucket ) {
 101                     item_type pBucket = *ppBucket;
 102                     if ( pBucket ) {
 103                         if ( !ret.first )
 104                             ret.first = pBucket;
 105                         else
 106                             pTail->m_pNextFree = pBucket;
 107
 108                         pTail = pBucket;
 109                         for (;;) {
 110                             item_type pNext = pTail->m_pNext;
 111                             pTail->m_ptr.free();
 112                             pTail->m_pNext = nullptr;
 113
 114                             while ( pTail->m_pNextFree ) {
 115                                 pTail = pTail->m_pNextFree;
 116                                 pTail->m_ptr.free();
 117                                 pTail->m_pNext = nullptr;
 118                             }
 119
 120                             if ( pNext )
 121                                 pTail = pTail->m_pNextFree = pNext;
 122                             else
 123                                 break;
 124                         }
 125                     }
 126                 }
 127
 128                 if ( pTail )
 129                     pTail->m_pNextFree = nullptr;
 130                 ret.second = pTail;
 131                 return ret;
 132             }
 133         };
 134     }
 135
 136     GarbageCollector * GarbageCollector::m_pManager = nullptr;
 137
 138     void CDS_STDCALL GarbageCollector::Construct(
 139         size_t nLiberateThreshold
 140         , size_t nInitialThreadGuardCount
 141     )
 142     {
 143         if ( !m_pManager ) {
 144             m_pManager = new GarbageCollector( nLiberateThreshold, nInitialThreadGuardCount );
 145         }
 146     }
 147
 148     void CDS_STDCALL GarbageCollector::Destruct()
 149     {
 150         if ( m_pManager ) {
 151             delete m_pManager;
 152             m_pManager = nullptr;
 153         }
 154     }
 155
 156     GarbageCollector::GarbageCollector( size_t nLiberateThreshold, size_t nInitialThreadGuardCount )
 157         : m_nLiberateThreshold( nLiberateThreshold ? nLiberateThreshold : 1024 )
 158         , m_nInitialThreadGuardCount( nInitialThreadGuardCount ? nInitialThreadGuardCount : 8 )
 159         //, m_nInLiberate(0)
 160     {
 161     }
 162
 163     GarbageCollector::~GarbageCollector()
 164     {
 165         liberate();
 166
 167 #if 0
 168         details::retired_ptr_node * pHead = nullptr;
 169         details::retired_ptr_node * pTail = nullptr;
 170
 171         for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_relaxed)) {
 172             details::guard_data::handoff_ptr h = pGuard->pHandOff;
 173             pGuard->pHandOff  = nullptr;
 174             while ( h ) {
 175                 details::guard_data::handoff_ptr pNext = h->m_pNextFree;
 176                 if ( h->m_ptr.m_p )
 177                     h->m_ptr.free();
 178                 if ( !pHead )
 179                     pTail = pHead = h;
 180                 else
 181                     pTail = pTail->m_pNextFree = h;
 182                 h = pNext;
 183             }
 184         }
 185         if ( pHead )
 186             m_RetiredAllocator.free_range( pHead, pTail );
 187 #endif
 188     }
 189
 190     void GarbageCollector::liberate()
 191     {
 192         details::retired_ptr_buffer::privatize_result retiredList = m_RetiredBuffer.privatize();
 193         if ( retiredList.first ) {
 194
 195             size_t nLiberateThreshold = m_nLiberateThreshold.load(atomics::memory_order_relaxed);
 196             details::liberate_set set( beans::ceil2( retiredList.second > nLiberateThreshold ? retiredList.second : nLiberateThreshold ) );
 197
 198             // Get list of retired pointers
 199             details::retired_ptr_node * pHead = retiredList.first;
 200             while ( pHead ) {
 201                 details::retired_ptr_node * pNext = pHead->m_pNext;
 202                 pHead->m_pNextFree = nullptr;
 203                 set.insert( *pHead );
 204                 pHead = pNext;
 205             }
 206
 207             // Liberate cycle
 208             for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) )
 209             {
 210                 // get guarded pointer
 211                 details::guard_data::guarded_ptr  valGuarded = pGuard->pPost.load(atomics::memory_order_acquire);
 212
 213                 if ( valGuarded ) {
 214                     details::retired_ptr_node * pRetired = set.erase( valGuarded );
 215                     if ( pRetired ) {
 216                         // Retired pointer is being guarded
 217                         // pRetired is the head of retired pointers list for which the m_ptr.m_p field is equal
 218                         // List is linked on m_pNextFree field
 219
 220                         do {
 221                             details::retired_ptr_node * pNext = pRetired->m_pNextFree;
 222                             m_RetiredBuffer.push( *pRetired );
 223                             pRetired = pNext;
 224                         } while ( pRetired );
 225                     }
 226                 }
 227             }
 228
 229             // Free all retired pointers
 230             details::liberate_set::list_range range = set.free_all();
 231
 232             m_RetiredAllocator.inc_epoch();
 233
 234             if ( range.first ) {
 235                 assert( range.second != nullptr );
 236                 m_RetiredAllocator.free_range( range.first, range.second );
 237             }
 238             else {
 239                 // liberate cycle did not free any retired pointer - double liberate threshold
 240                 m_nLiberateThreshold.compare_exchange_strong( nLiberateThreshold, nLiberateThreshold * 2, atomics::memory_order_release, atomics::memory_order_relaxed );
 241             }
 242         }
 243     }
 244
 245 #if 0
 246     void GarbageCollector::liberate( details::liberate_set& set )
 247     {
 248         details::guard_data::handoff_ptr const nullHandOff = nullptr;
 249
 250         for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) )
 251         {
 252             // get guarded pointer
 253             details::guard_data::guarded_ptr  valGuarded = pGuard->pPost.load(atomics::memory_order_acquire);
 254             details::guard_data::handoff_ptr h;
 255
 256             if ( valGuarded ) {
 257                 details::retired_ptr_node * pRetired = set.erase( valGuarded );
 258                 if ( pRetired ) {
 259                     // Retired pointer is being guarded
 260
 261                     // pRetired is the head of retired pointers list for which the m_ptr.m_p field is equal
 262                     // List is linked on m_pNextFree field
 263
 264                     // Now, try to set retired node pRetired as a hand-off node for the guard
 265                     cds::lock::Auto<details::guard_data::handoff_spin> al( pGuard->spinHandOff );
 266                     if ( valGuarded == pGuard->pPost.load(atomics::memory_order_acquire) ) {
 267                         if ( pGuard->pHandOff && pGuard->pHandOff->m_ptr.m_p == pRetired->m_ptr.m_p ) {
 268                             h = nullHandOff ; //nullptr;
 269                             details::retired_ptr_node * pTail = pGuard->pHandOff;
 270                             while ( pTail->m_pNextFree )
 271                                 pTail = pTail->m_pNextFree;
 272                             pTail->m_pNextFree = pRetired;
 273                         }
 274                         else {
 275                             // swap h and pGuard->pHandOff
 276                             h = pGuard->pHandOff;
 277                             pGuard->pHandOff = pRetired;
 278                         }
 279                     }
 280                     else
 281                         h = pRetired;
 282                 }
 283                 else {
 284                     cds::lock::Auto<details::guard_data::handoff_spin> al( pGuard->spinHandOff );
 285                     h = pGuard->pHandOff;
 286                     if ( h ) {
 287                         if ( h->m_ptr.m_p != valGuarded )
 288                             pGuard->pHandOff = nullHandOff;
 289                         else
 290                             h = nullHandOff;
 291                     }
 292                 }
 293             }
 294             else {
 295                 cds::lock::Auto<details::guard_data::handoff_spin> al( pGuard->spinHandOff );
 296                 h = pGuard->pHandOff;
 297                 pGuard->pHandOff = nullHandOff;
 298             }
 299
 300             // h is the head of a list linked on m_pNextFree field
 301             if ( h ) {
 302                 set.insert( *h );
 303             }
 304         }
 305     }
 306 #endif
 307 }}} // namespace cds::gc::ptb