2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
34 #include <cds/gc/hp.h>
35 #include <cds/os/thread.h>
37 namespace cds { namespace gc { namespace hp {
40 void * default_alloc_memory( size_t size )
42 return new uintptr_t[( size + sizeof( uintptr_t ) - 1 ) / sizeof( uintptr_t) ];
45 void default_free_memory( void* p )
47 delete[] reinterpret_cast<uintptr_t*>( p );
50 void* ( *s_alloc_memory )( size_t size ) = default_alloc_memory;
51 void ( *s_free_memory )( void* p ) = default_free_memory;
60 allocator( allocator const& ) {}
62 explicit allocator( allocator<U> const& ) {}
64 static T* allocate( size_t nCount )
66 return reinterpret_cast<T*>( s_alloc_memory( sizeof( value_type ) * nCount ) );
69 static void deallocate( T* p, size_t /*nCount*/ )
71 s_free_memory( reinterpret_cast<void*>( p ) );
76 static const size_t c_nHazardPointerPerThread = 8;
77 static const size_t c_nMaxThreadCount = 100;
80 size_t calc_retired_size( size_t nSize, size_t nHPCount, size_t nThreadCount )
82 size_t const min_size = nHPCount * nThreadCount;
83 return nSize < min_size ? min_size * 2 : nSize;
86 stat s_postmortem_stat;
89 /*static*/ CDS_EXPORT_API smr* smr::instance_ = nullptr;
90 thread_local thread_data* tls_ = nullptr;
92 /*static*/ CDS_EXPORT_API thread_data* smr::tls()
94 assert( tls_ != nullptr );
98 struct smr::thread_record: thread_data
100 atomics::atomic<thread_record*> m_pNextNode; ///< next hazard ptr record in list
101 atomics::atomic<cds::OS::ThreadId> m_idOwner; ///< Owner thread id; 0 - the record is free (not owned)
102 atomics::atomic<bool> m_bFree; ///< true if record is free (not owned)
104 thread_record( guard* guards, size_t guard_count, retired_ptr* retired_arr, size_t retired_capacity )
105 : thread_data( guards, guard_count, retired_arr, retired_capacity )
110 /*static*/ CDS_EXPORT_API void smr::set_memory_allocator(
111 void* ( *alloc_func )( size_t size ),
112 void( *free_func )( void * p )
115 // The memory allocation functions may be set BEFORE initializing HP SMR!!!
116 assert( instance_ == nullptr );
118 s_alloc_memory = alloc_func;
119 s_free_memory = free_func;
123 /*static*/ CDS_EXPORT_API void smr::construct( size_t nHazardPtrCount, size_t nMaxThreadCount, size_t nMaxRetiredPtrCount, scan_type nScanType )
126 instance_ = new( s_alloc_memory(sizeof(smr))) smr( nHazardPtrCount, nMaxThreadCount, nMaxRetiredPtrCount, nScanType );
130 /*static*/ CDS_EXPORT_API void smr::destruct( bool bDetachAll )
134 instance_->detach_all_thread();
137 s_free_memory( instance_ );
142 CDS_EXPORT_API smr::smr( size_t nHazardPtrCount, size_t nMaxThreadCount, size_t nMaxRetiredPtrCount, scan_type nScanType )
143 : thread_list_( nullptr )
144 , hazard_ptr_count_( nHazardPtrCount == 0 ? defaults::c_nHazardPointerPerThread : nHazardPtrCount )
145 , max_thread_count_( nMaxThreadCount == 0 ? defaults::c_nMaxThreadCount : nMaxThreadCount )
146 , max_retired_ptr_count_( calc_retired_size( nMaxRetiredPtrCount, hazard_ptr_count_, max_thread_count_ ))
147 , scan_type_( nScanType )
148 , scan_func_( nScanType == classic ? &smr::classic_scan : &smr::inplace_scan )
151 CDS_EXPORT_API smr::~smr()
153 CDS_DEBUG_ONLY( const cds::OS::ThreadId nullThreadId = cds::OS::c_NullThreadId; )
154 CDS_DEBUG_ONLY( const cds::OS::ThreadId mainThreadId = cds::OS::get_current_thread_id();)
156 CDS_HPSTAT( statistics( s_postmortem_stat ));
158 thread_record* pHead = thread_list_.load( atomics::memory_order_relaxed );
159 thread_list_.store( nullptr, atomics::memory_order_relaxed );
161 thread_record* pNext = nullptr;
162 for ( thread_record* hprec = pHead; hprec; hprec = pNext )
164 assert( hprec->m_idOwner.load( atomics::memory_order_relaxed ) == nullThreadId
165 || hprec->m_idOwner.load( atomics::memory_order_relaxed ) == mainThreadId
166 || !cds::OS::is_thread_alive( hprec->m_idOwner.load( atomics::memory_order_relaxed ) )
169 retired_array& arr = hprec->retired_;
170 for ( retired_ptr* cur{ arr.first() }, *last{ arr.last() }; cur != last; ++cur ) {
172 CDS_HPSTAT( ++s_postmortem_stat.free_count );
176 pNext = hprec->m_pNextNode.load( atomics::memory_order_relaxed );
177 hprec->m_bFree.store( true, atomics::memory_order_relaxed );
178 destroy_thread_data( hprec );
183 CDS_EXPORT_API smr::thread_record* smr::create_thread_data()
185 size_t const guard_array_size = thread_hp_storage::calc_array_size( get_hazard_ptr_count());
186 size_t const retired_array_size = retired_array::calc_array_size( get_max_retired_ptr_count());
187 size_t const nSize = sizeof( thread_record ) + guard_array_size + retired_array_size;
190 The memory is allocated by contnuous block
192 +--------------------------+
198 | |--------------------------| |
199 | | hazard_ptr[] |<--+
202 | |--------------------------|
203 +-->| retired_ptr[] |
206 +--------------------------+
209 char* mem = reinterpret_cast<char*>( s_alloc_memory( nSize ));
210 return new( mem ) thread_record(
211 reinterpret_cast<guard*>( mem + sizeof( thread_record )), get_hazard_ptr_count(),
212 reinterpret_cast<retired_ptr*>( mem + sizeof( thread_record ) + guard_array_size ), get_max_retired_ptr_count()
216 /*static*/ CDS_EXPORT_API void smr::destroy_thread_data( thread_record* pRec )
218 // all retired pointers must be freed
219 assert( pRec->retired_.size() == 0 );
221 pRec->~thread_record();
222 s_free_memory( pRec );
226 CDS_EXPORT_API smr::thread_record* smr::alloc_thread_data()
228 //CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_AllocHPRec )
230 thread_record * hprec;
231 const cds::OS::ThreadId nullThreadId = cds::OS::c_NullThreadId;
232 const cds::OS::ThreadId curThreadId = cds::OS::get_current_thread_id();
234 // First try to reuse a free (non-active) HP record
235 for ( hprec = thread_list_.load( atomics::memory_order_acquire ); hprec; hprec = hprec->m_pNextNode.load( atomics::memory_order_relaxed ) ) {
236 cds::OS::ThreadId thId = nullThreadId;
237 if ( !hprec->m_idOwner.compare_exchange_strong( thId, curThreadId, atomics::memory_order_relaxed, atomics::memory_order_relaxed ) )
239 hprec->m_bFree.store( false, atomics::memory_order_release );
243 // No HP records available for reuse
244 // Allocate and push a new HP record
245 hprec = create_thread_data();
246 hprec->m_idOwner.store( curThreadId, atomics::memory_order_relaxed );
248 thread_record* pOldHead = thread_list_.load( atomics::memory_order_relaxed );
250 hprec->m_pNextNode.store( pOldHead, atomics::memory_order_relaxed );
251 } while ( !thread_list_.compare_exchange_weak( pOldHead, hprec, atomics::memory_order_release, atomics::memory_order_acquire ) );
256 CDS_EXPORT_API void smr::free_thread_data( smr::thread_record* pRec )
258 assert( pRec != nullptr );
259 //CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_RetireHPRec )
261 pRec->hazards_.clear();
264 pRec->m_idOwner.store( cds::OS::c_NullThreadId, atomics::memory_order_release );
267 CDS_EXPORT_API void smr::detach_all_thread()
269 thread_record * pNext = nullptr;
270 const cds::OS::ThreadId nullThreadId = cds::OS::c_NullThreadId;
272 for ( thread_record * hprec = thread_list_.load( atomics::memory_order_relaxed ); hprec; hprec = pNext ) {
273 pNext = hprec->m_pNextNode.load( atomics::memory_order_relaxed );
274 if ( hprec->m_idOwner.load( atomics::memory_order_relaxed ) != nullThreadId ) {
275 free_thread_data( hprec );
280 /*static*/ CDS_EXPORT_API void smr::attach_thread()
283 tls_ = instance().alloc_thread_data();
286 /*static*/ CDS_EXPORT_API void smr::detach_thread()
288 thread_data* rec = tls_;
291 instance().free_thread_data( static_cast<thread_record*>( rec ));
296 CDS_EXPORT_API void smr::inplace_scan( thread_data* pThreadRec )
298 thread_record* pRec = static_cast<thread_record*>( pThreadRec );
300 //CDS_HAZARDPTR_STATISTIC( ++m_Stat.m_ScanCallCount )
302 // In-place scan algo uses LSB of retired ptr as a mark for internal purposes.
303 // It is correct if all retired pointers are ar least 2-byte aligned (LSB is zero).
304 // If it is wrong, we use classic scan algorithm
306 // Check if all retired pointers has zero LSB
307 // LSB is used for marking pointers that cannot be deleted yet
308 retired_ptr* first_retired = pRec->retired_.first();
309 retired_ptr* last_retired = pRec->retired_.last();
310 if ( first_retired == last_retired )
313 for ( auto it = first_retired; it != last_retired; ++it ) {
315 // found a pointer with LSB bit set - use classic_scan
316 classic_scan( pRec );
321 CDS_HPSTAT( ++pRec->scan_count_ );
323 // Sort retired pointer array
324 std::sort( first_retired, last_retired, retired_ptr::less );
329 auto it = first_retired;
331 while ( ++it != last_retired ) {
332 assert( itPrev->m_p < it->m_p );
338 // Search guarded pointers in retired array
339 thread_record* pNode = thread_list_.load( atomics::memory_order_acquire );
342 retired_ptr dummy_retired;
344 if ( pNode->m_idOwner.load( atomics::memory_order_relaxed ) != cds::OS::c_NullThreadId ) {
345 thread_hp_storage& hpstg = pNode->hazards_;
346 for ( size_t i = 0; i < hazard_ptr_count_; ++i ) {
348 void * hptr = hpstg[i].get();
350 dummy_retired.m_p = hptr;
351 retired_ptr* it = std::lower_bound( first_retired, last_retired, dummy_retired, retired_ptr::less );
352 if ( it != last_retired && it->m_p == hptr ) {
353 // Mark retired pointer as guarded
359 pNode = pNode->m_pNextNode.load( atomics::memory_order_relaxed );
363 // Move all marked pointers to head of array
365 retired_ptr* insert_pos = first_retired;
366 for ( retired_ptr* it = first_retired; it != last_retired; ++it ) {
368 it->m_n &= ~uintptr_t(1);
369 if ( insert_pos != it )
374 // Retired pointer may be freed
376 CDS_HPSTAT( ++pRec->free_count_ );
379 const size_t nDeferred = insert_pos - first_retired;
380 pRec->retired_.reset( nDeferred );
384 // cppcheck-suppress functionConst
385 CDS_EXPORT_API void smr::classic_scan( thread_data* pThreadRec )
387 thread_record* pRec = static_cast<thread_record*>( pThreadRec );
389 CDS_HPSTAT( ++pRec->scan_count_ );
391 std::vector< void*, allocator<void*>> plist;
392 plist.reserve( get_max_thread_count() * get_hazard_ptr_count());
393 assert( plist.size() == 0 );
395 // Stage 1: Scan HP list and insert non-null values in plist
397 thread_record* pNode = thread_list_.load( atomics::memory_order_acquire );
400 if ( pNode->m_idOwner.load( std::memory_order_relaxed ) != cds::OS::c_NullThreadId ) {
401 for ( size_t i = 0; i < get_hazard_ptr_count(); ++i ) {
403 void * hptr = pNode->hazards_[i].get();
405 plist.push_back( hptr );
408 pNode = pNode->m_pNextNode.load( atomics::memory_order_relaxed );
411 // Sort plist to simplify search in
412 std::sort( plist.begin(), plist.end() );
414 // Stage 2: Search plist
415 retired_array& retired = pRec->retired_;
417 retired_ptr* first_retired = retired.first();
418 retired_ptr* last_retired = retired.last();
421 auto itBegin = plist.begin();
422 auto itEnd = plist.end();
423 retired_ptr* insert_pos = first_retired;
424 for ( retired_ptr* it = first_retired; it != last_retired; ++it ) {
425 if ( std::binary_search( itBegin, itEnd, first_retired->m_p ) ) {
426 if ( insert_pos != it )
432 CDS_HPSTAT( ++pRec->free_count_ );
436 retired.reset( insert_pos - first_retired );
440 CDS_EXPORT_API void smr::help_scan( thread_data* pThis )
442 assert( static_cast<thread_record*>( pThis )->m_idOwner.load( atomics::memory_order_relaxed ) == cds::OS::get_current_thread_id() );
444 CDS_HPSTAT( ++pThis->help_scan_count_ );
446 const cds::OS::ThreadId nullThreadId = cds::OS::c_NullThreadId;
447 const cds::OS::ThreadId curThreadId = cds::OS::get_current_thread_id();
448 for ( thread_record* hprec = thread_list_.load( atomics::memory_order_acquire ); hprec; hprec = hprec->m_pNextNode.load( atomics::memory_order_relaxed ))
450 // If m_bFree == true then hprec->retired_ is empty - we don't need to see it
451 if ( hprec->m_bFree.load( atomics::memory_order_acquire ))
454 // Owns hprec if it is empty.
455 // Several threads may work concurrently so we use atomic technique only.
457 cds::OS::ThreadId curOwner = hprec->m_idOwner.load( atomics::memory_order_relaxed );
458 if ( curOwner == nullThreadId || !cds::OS::is_thread_alive( curOwner ) ) {
459 if ( !hprec->m_idOwner.compare_exchange_strong( curOwner, curThreadId, atomics::memory_order_acquire, atomics::memory_order_relaxed ) )
466 // We own the thread record successfully. Now, we can see whether it has retired pointers.
467 // If it has ones then we move to pThis that is private for current thread.
468 retired_array& src = hprec->retired_;
469 retired_array& dest = pThis->retired_;
470 assert( !dest.full() );
472 retired_ptr* src_first = src.first();
473 retired_ptr* src_last = src.last();
475 for ( ; src_first != src_last; ++src_first ) {
476 if ( !dest.push( std::move( *src_first )))
482 hprec->m_bFree.store( true, atomics::memory_order_relaxed );
483 hprec->m_idOwner.store( nullThreadId, atomics::memory_order_release );
489 void smr::statistics( stat& st )
492 # ifdef CDS_ENABLE_HPSTAT
493 for ( thread_record* hprec = thread_list_.load( atomics::memory_order_acquire ); hprec; hprec = hprec->m_pNextNode.load( atomics::memory_order_relaxed ) )
495 ++st.thread_rec_count;
496 st.guard_allocated += hprec->hazards_.alloc_guard_count_;
497 st.guard_freed += hprec->hazards_.free_guard_count_;
498 st.retired_count += hprec->retired_.retire_call_count_;
499 st.free_count += hprec->free_count_;
500 st.scan_count += hprec->scan_count_;
501 st.help_scan_count += hprec->help_scan_count_;
506 }}} // namespace cds::gc::hp
508 /*static*/ cds::gc::HP::stat const& cds::gc::HP::postmortem_statistics()
510 return cds::gc::hp::s_postmortem_stat;