src/dhp_gc.cpp

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 // Dynamic Hazard Pointer memory manager implementation
  32
  33 #include <algorithm>   // std::fill
  34 #include <functional>  // std::hash
  35
  36 #include <cds/gc/details/dhp.h>
  37 #include <cds/algo/int_algo.h>
  38
  39 namespace cds { namespace gc { namespace dhp {
  40
  41     namespace details {
  42
  43         class liberate_set {
  44             typedef retired_ptr_node *  item_type;
  45             typedef cds::details::Allocator<item_type, CDS_DEFAULT_ALLOCATOR>   allocator_type;
  46
  47             size_t const m_nBucketCount;
  48             item_type *  m_Buckets;
  49
  50             item_type&  bucket( retired_ptr_node& node ) const
  51             {
  52                 return bucket( node.m_ptr.m_p );
  53             }
  54             item_type&  bucket( guard_data::guarded_ptr p ) const
  55             {
  56                 return m_Buckets[ std::hash<guard_data::guarded_ptr>()( p ) & (m_nBucketCount - 1)  ];
  57             }
  58
  59         public:
  60             liberate_set( size_t nBucketCount )
  61                 : m_nBucketCount( nBucketCount )
  62             {
  63                 assert( nBucketCount > 0 );
  64                 assert( (nBucketCount & (nBucketCount - 1)) == 0 );
  65
  66                 m_Buckets = allocator_type().NewArray( nBucketCount );
  67                 std::fill( m_Buckets, m_Buckets + nBucketCount, nullptr );
  68             }
  69
  70             ~liberate_set()
  71             {
  72                 allocator_type().Delete( m_Buckets, m_nBucketCount );
  73             }
  74
  75             void insert( retired_ptr_node& node )
  76             {
  77                 node.m_pNext.store( nullptr, atomics::memory_order_relaxed );
  78
  79                 item_type& refBucket = bucket( node );
  80                 if ( refBucket ) {
  81                     item_type p = refBucket;
  82                     item_type prev = nullptr;
  83                     do {
  84                         if ( p->m_ptr.m_p >= node.m_ptr.m_p ) {
  85                             node.m_pNext.store( p, atomics::memory_order_relaxed );
  86                             if ( prev )
  87                                 prev->m_pNext.store( &node, atomics::memory_order_relaxed );
  88                             else
  89                                 refBucket = &node;
  90                             return;
  91                         }
  92                         prev = p;
  93                         p = p->m_pNext.load(atomics::memory_order_relaxed);
  94                     } while ( p );
  95
  96                     assert( prev != nullptr );
  97                     prev->m_pNext.store( &node, atomics::memory_order_relaxed );
  98                 }
  99                 else
 100                     refBucket = &node;
 101             }
 102
 103             struct erase_result
 104             {
 105                 item_type head;
 106                 item_type tail;
 107                 size_t    size;
 108
 109                 erase_result()
 110                     : head( nullptr )
 111                     , tail( nullptr )
 112                     , size(0)
 113                 {}
 114             };
 115
 116             erase_result erase( guard_data::guarded_ptr ptr )
 117             {
 118                 item_type& refBucket = bucket( ptr );
 119                 item_type p = refBucket;
 120                 item_type pPrev = nullptr;
 121
 122                 erase_result ret;
 123                 while ( p && p->m_ptr.m_p <= ptr ) {
 124                     if ( p->m_ptr.m_p == ptr ) {
 125                         if ( pPrev )
 126                             pPrev->m_pNext.store( p->m_pNext.load(atomics::memory_order_relaxed ), atomics::memory_order_relaxed );
 127                         else
 128                             refBucket = p->m_pNext.load(atomics::memory_order_relaxed);
 129
 130                         if ( ret.head )
 131                             ret.tail->m_pNext.store( p, atomics::memory_order_relaxed );
 132                         else
 133                             ret.head = p;
 134                         ret.tail = p;
 135                         ++ret.size;
 136                     }
 137                     else
 138                         pPrev = p;
 139                     p = p->m_pNext.load( atomics::memory_order_relaxed );
 140                 }
 141
 142                 if ( ret.tail )
 143                     ret.tail->m_pNext.store( nullptr, atomics::memory_order_relaxed );
 144                 return ret;
 145             }
 146
 147             typedef std::pair<item_type, item_type>     list_range;
 148
 149             list_range free_all()
 150             {
 151                 item_type pTail = nullptr;
 152                 list_range ret = std::make_pair( pTail, pTail );
 153
 154                 item_type const * pEndBucket = m_Buckets + m_nBucketCount;
 155                 for ( item_type * ppBucket = m_Buckets; ppBucket < pEndBucket; ++ppBucket ) {
 156                     item_type pBucket = *ppBucket;
 157                     if ( pBucket ) {
 158                         if ( ret.first )
 159                             pTail->m_pNextFree.store( pBucket, atomics::memory_order_relaxed );
 160                         else
 161                             ret.first = pBucket;
 162
 163                         pTail = pBucket;
 164                         for (;;) {
 165                             item_type pNext = pTail->m_pNext.load( atomics::memory_order_relaxed );
 166                             pTail->m_ptr.free();
 167                             pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed );
 168
 169                             /*
 170                             while ( pTail->m_pNextFree.load( atomics::memory_order_relaxed )) {
 171                                 pTail = pTail->m_pNextFree.load( atomics::memory_order_relaxed );
 172                                 pTail->m_ptr.free();
 173                                 pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed );
 174                             }
 175                             */
 176
 177                             if ( pNext ) {
 178                                 pTail->m_pNextFree.store( pNext, atomics::memory_order_relaxed );
 179                                 pTail = pNext;
 180                             }
 181                             else
 182                                 break;
 183                         }
 184                     }
 185                 }
 186
 187                 if ( pTail )
 188                     pTail->m_pNextFree.store( nullptr, atomics::memory_order_relaxed );
 189                 ret.second = pTail;
 190                 return ret;
 191             }
 192         };
 193     }
 194
 195     GarbageCollector * GarbageCollector::m_pManager = nullptr;
 196
 197     void CDS_STDCALL GarbageCollector::Construct(
 198         size_t nLiberateThreshold
 199         , size_t nInitialThreadGuardCount
 200         , size_t nEpochCount
 201     )
 202     {
 203         if ( !m_pManager ) {
 204             m_pManager = new GarbageCollector( nLiberateThreshold, nInitialThreadGuardCount, nEpochCount );
 205         }
 206     }
 207
 208     void CDS_STDCALL GarbageCollector::Destruct()
 209     {
 210         delete m_pManager;
 211         m_pManager = nullptr;
 212     }
 213
 214     GarbageCollector::GarbageCollector( size_t nLiberateThreshold, size_t nInitialThreadGuardCount, size_t nEpochCount )
 215         : m_nLiberateThreshold( nLiberateThreshold ? nLiberateThreshold : 1024 )
 216         , m_nInitialThreadGuardCount( nInitialThreadGuardCount ? nInitialThreadGuardCount : 8 )
 217         , m_RetiredAllocator( static_cast<unsigned int>( nEpochCount ? nEpochCount : 16 ))
 218         , m_bStatEnabled( false )
 219     {}
 220
 221     GarbageCollector::~GarbageCollector()
 222     {
 223         scan();
 224     }
 225
 226     void GarbageCollector::scan()
 227     {
 228         details::retired_ptr_buffer::privatize_result retiredList = m_RetiredBuffer.privatize();
 229         if ( retiredList.first ) {
 230
 231             size_t nLiberateThreshold = m_nLiberateThreshold.load(atomics::memory_order_relaxed);
 232             details::liberate_set set( beans::ceil2( retiredList.second > nLiberateThreshold ? retiredList.second : nLiberateThreshold ));
 233
 234             // Get list of retired pointers
 235             size_t nRetiredCount = 0;
 236             details::retired_ptr_node * pHead = retiredList.first;
 237             while ( pHead ) {
 238                 details::retired_ptr_node * pNext = pHead->m_pNext.load( atomics::memory_order_relaxed );
 239                 pHead->m_pNextFree.store( nullptr, atomics::memory_order_relaxed );
 240                 set.insert( *pHead );
 241                 pHead = pNext;
 242                 ++nRetiredCount;
 243             }
 244
 245             // Liberate cycle
 246
 247             details::retired_ptr_node dummy;
 248             dummy.m_pNext.store( nullptr, atomics::memory_order_relaxed );
 249             details::retired_ptr_node * pBusyLast = &dummy;
 250             size_t nBusyCount = 0;
 251
 252             for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) )
 253             {
 254                 // get guarded pointer
 255                 details::guard_data::guarded_ptr valGuarded = pGuard->pPost.load(atomics::memory_order_acquire);
 256
 257                 if ( valGuarded ) {
 258                     auto retired = set.erase( valGuarded );
 259                     if ( retired.head ) {
 260                         // Retired pointer is being guarded
 261                         // [retired.head, retired.tail] is the list linked by m_pNext field
 262
 263                         pBusyLast->m_pNext.store( retired.head, atomics::memory_order_relaxed );
 264                         pBusyLast = retired.tail;
 265                         nBusyCount += retired.size;
 266                     }
 267                 }
 268             }
 269
 270             // Place [dummy.m_pNext, pBusyLast] back to m_RetiredBuffer
 271             if ( nBusyCount )
 272                 m_RetiredBuffer.push_list( dummy.m_pNext.load(atomics::memory_order_relaxed), pBusyLast, nBusyCount );
 273
 274             // Free all retired pointers
 275             details::liberate_set::list_range range = set.free_all();
 276
 277             m_RetiredAllocator.inc_epoch();
 278
 279             if ( range.first ) {
 280                 assert( range.second != nullptr );
 281                 m_RetiredAllocator.free_range( range.first, range.second );
 282             }
 283             else if ( nRetiredCount >= nLiberateThreshold ) {
 284                 // scan() cycle did not free any retired pointer - double scan() threshold
 285                 m_nLiberateThreshold.compare_exchange_strong( nLiberateThreshold, nLiberateThreshold * 2, atomics::memory_order_release, atomics::memory_order_relaxed );
 286             }
 287         }
 288     }
 289 }}} // namespace cds::gc::dhp