The forward iterator for Michael's list has some features:
- it has no post-increment operator
- to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
- For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
+ For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
may be thrown if a limit of guard count per thread is exceeded.
- The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
- Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
The forward iterator for Michael's list has some features:
- it has no post-increment operator
- to protect the value, the iterator contains a GC-specific guard + another guard is required locally for increment operator.
- For some GC (gc::HP, gc::HRC), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
+ For some GC (\p gc::HP), a guard is limited resource per thread, so an exception (or assertion) "no free guard"
may be thrown if a limit of guard count per thread is exceeded.
- The iterator cannot be moved across thread boundary since it contains GC's guard that is thread-private GC data.
- Iterator ensures thread-safety even if you delete the item that iterator points to. However, in case of concurrent
- [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
Template arguments:
- - \p GC - garbage collector type: gc::HP, gc::PTB. Note that gc::HRC is <b>not</b> supported
+ - \p GC - garbage collector type: \p gc::HP, \p gc::DHP.
- \p T - type of values to be stored in the queue
- \p Traits - queue traits, default is \p optimistic_queue::traits. You can use \p optimistic_queue::make_traits
metafunction to make your traits or just derive your traits from \p %optimistic_queue::traits:
The main part of lock-free data structs is garbage collecting. The garbage collector (GC) solves the problem of safe
memory reclamation that is one of the main problems for lock-free programming.
The library contains the implementations of several light-weight \ref cds_garbage_collector "memory reclamation schemes":
- - M.Michael's Hazard Pointer - see cds::gc::HP for more explanation
- - Gidenstam's memory reclamation schema based on Hazard Pointer and reference counting - see cds::gc::HRC
- - M.Herlihy and M.Moir's Pass The Buck algorithm - see cds::gc::PTB
+ - M.Michael's Hazard Pointer - \p see cds::gc::HP, \p cds::gc::DHP for more explanation
- User-space Read-Copy Update (RCU) - see cds::urcu namespace
- there is cds::gc::nogc "GC" for containers that do not support item reclamation.
Usually, the application is based on only one type of GC.
In the next example we mean that your application uses Hazard Pointer (cds::gc::HP) - based containers.
- Other GCs (cds::gc::HRC, cds::gc::PTB) are applied analogously.
First, in your code you should initialize \p cds library and a garbage collector in \p main function:
\code
#define __CDS_GC_ALL_H
#include <cds/gc/hp.h>
-#include <cds/gc/hrc.h>
#include <cds/gc/ptb.h>
#endif // #ifndef __CDS_GC_ALL_H
//@cond
namespace cds { namespace gc {
class HP;
- class HRC;
class PTB;
class nogc;
static void retire( T * p ) ; // inline in hp_impl.h
/// Get current scan strategy
- /**@anchor hrc_gc_HP_getScanType
- See hzp::GarbageCollector::Scan for scan algo description
- */
hzp::scan_type getScanType() const
{
return hzp::GarbageCollector::instance().getScanType();
}
/// Set current scan strategy
- /**
- Scan strategy changing is allowed on the fly.
-
- About scan strategy see \ref hrc_gc_HP_getScanType "getScanType"
- */
void setScanType(
hzp::scan_type nScanType ///< new scan strategy
)
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_GC_HRC_H
-#define __CDS_GC_HRC_H
-
-#include <cds/gc/hrc_decl.h>
-#include <cds/gc/hrc_impl.h>
-#include <cds/details/lib.h>
-
-#endif // #ifndef __CDS_GC_HRC_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_GC_HRC_SCHEMA_FWD_H
-#define __CDS_GC_HRC_SCHEMA_FWD_H
-
-namespace cds { namespace gc { namespace hrc {
-
- // forward declaration
- class GarbageCollector;
- class ThreadGC;
-
- class ContainerNode;
- class Container;
-}}}
-
-#endif // #ifndef __CDS_GC_HRC_SCHEMA_FWD_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_GC_HRC_SCHEMA_INLINE_H
-#define __CDS_GC_HRC_SCHEMA_INLINE_H
-
-//@cond
-namespace cds { namespace gc { namespace hrc {
-
- //-------------------------------------------------------------------
- // Inlines
- //-------------------------------------------------------------------
-
- namespace details {
- inline retired_vector::retired_vector( const GarbageCollector& gc )
- : m_nFreeList(0)
- , m_arr( gc.getMaxRetiredPtrCount() )
- {
- for ( size_t i = 0; i < m_arr.capacity(); ++i )
- m_arr[i].m_nNextFree = i + 1;
- m_arr[ m_arr.capacity() - 1 ].m_nNextFree = m_nEndFreeList;
- }
-
- inline thread_descriptor::thread_descriptor( const GarbageCollector& gc )
- : m_hzp( gc.getHazardPointerCount() )
- , m_arrRetired( gc )
- {}
-
- } // namespace details
-
- inline ContainerNode::ContainerNode()
- : m_bTrace( false )
- , m_bDeleted( false )
- {
- CDS_DEBUG_ONLY( GarbageCollector::instance().dbgNodeConstructed() ; )
- }
-
- inline ContainerNode::~ContainerNode()
- {
- assert( m_RC == 0 );
- CDS_DEBUG_ONLY( GarbageCollector::instance().dbgNodeDestructed() ; )
- }
-
- inline void GarbageCollector::try_retire( ThreadGC * pThreadGC )
- {
- CDS_DEBUG_ONLY( unsigned int nAttempt = 0 );
-
- do {
- pThreadGC->cleanUpLocal();
- Scan( pThreadGC );
- HelpScan( pThreadGC );
-
- if ( pThreadGC->m_pDesc->m_arrRetired.isFull() )
- CleanUpAll( pThreadGC );
-
- // infinite loop?
- assert( ++nAttempt <= 3 );
- } while ( pThreadGC->m_pDesc->m_arrRetired.isFull() );
- }
-
-
-} } } // namespace cds::gc::hrc
-//@endcond
-
-#endif // #ifndef __CDS_GC_HRC_SCHEMA_INLINE_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_GC_HRC_SCHEMA_RETIRED_H
-#define __CDS_GC_HRC_SCHEMA_RETIRED_H
-
-#include <cds/gc/hrc/details/hrc_fwd.h>
-#include <cds/gc/details/retired_ptr.h>
-#include <cds/cxx11_atomic.h>
-#include <cds/details/bounded_array.h>
-
-namespace cds { namespace gc { namespace hrc {
- namespace details {
-
- /// Pointer to function to free (destruct and deallocate) retired pointer of specific type
- typedef gc::details::free_retired_ptr_func free_retired_ptr_func;
-
- /// Retired node descriptor
- struct retired_node {
- atomics::atomic<ContainerNode *> m_pNode ; ///< node to destroy
- free_retired_ptr_func m_funcFree ; ///< pointer to the destructor function
- size_t m_nNextFree ; ///< Next free item in retired array
- atomics::atomic<unsigned int> m_nClaim ; ///< Access to reclaimed node
- atomics::atomic<bool> m_bDone ; ///< the record is in work (concurrent access flag)
-
- /// Default ctor
- retired_node()
- : m_pNode( nullptr )
- , m_funcFree( nullptr )
- , m_nNextFree(0)
- , m_nClaim(0)
- , m_bDone( false )
- {}
-
- /// Assignment ctor
- retired_node(
- ContainerNode * pNode ///< Node to retire
- ,free_retired_ptr_func func ///< Destructor function
- )
- : m_pNode( pNode )
- , m_funcFree( func )
- , m_nClaim(0)
- , m_bDone( false )
- {}
-
- /// Compares two \ref retired_node
- static bool Less( const retired_node& p1, const retired_node& p2 )
- {
- return p1.m_pNode.load( atomics::memory_order_relaxed ) < p2.m_pNode.load( atomics::memory_order_relaxed );
- }
-
- /// Assignment operator
- retired_node& set( ContainerNode * pNode, free_retired_ptr_func func )
- {
- m_bDone.store( false, atomics::memory_order_relaxed );
- m_nClaim.store( 0, atomics::memory_order_relaxed );
- m_funcFree = func;
- m_pNode.store( pNode, atomics::memory_order_release );
- CDS_COMPILER_RW_BARRIER;
- return *this;
- }
-
- /// Invokes destructor function for the pointer
- void free()
- {
- assert( m_funcFree != nullptr );
- m_funcFree( m_pNode.load( atomics::memory_order_relaxed ));
- }
- };
-
- /// Compare two retired node
- /**
- This comparison operator is needed for sorting pointers on
- deallocation step
- */
- static inline bool operator <( const retired_node& p1, const retired_node& p2 )
- {
- return retired_node::Less( p1, p2 );
- }
-
- /// Array of ready for destroying pointers
- /**
- The array object is belonged to one thread: only owner thread may write to this array,
- any other thread can read one.
- */
- class retired_vector
- {
- typedef cds::details::bounded_array<retired_node> vector_type ; ///< type of vector of retired pointer (implicit CDS_DEFAULT_ALLOCATOR dependency)
-
- //@cond
- static const size_t m_nEndFreeList = size_t(0) - 1 ; ///< End of free list
- //@endcond
- size_t m_nFreeList ; ///< Index of first free item in m_arr
- vector_type m_arr ; ///< Array of retired pointers (implicit \ref CDS_DEFAULT_ALLOCATOR dependence)
-
- public:
- /// Iterator over retired pointer vector
- typedef vector_type::iterator iterator;
- /// Const iterator type
- typedef vector_type::const_iterator const_iterator;
-
- public:
- /// Ctor
- retired_vector( const GarbageCollector& mgr ) ; // inline
- ~retired_vector()
- {}
-
- ///@anchor hrc_gc_retired_vector_capacity Capacity (max available size) of array
- size_t capacity() const
- {
- return m_arr.capacity();
- }
-
- /// Returns count of retired node in array. This function is intended for debug purposes only
- size_t retiredNodeCount() const
- {
- size_t nCount = 0;
- const size_t nCapacity = capacity();
- for ( size_t i = 0; i < nCapacity; ++i ) {
- if ( m_arr[i].m_pNode.load( atomics::memory_order_relaxed ) != nullptr )
- ++nCount;
- }
- return nCount;
- }
-
- /// Push a new item into the array
- void push( ContainerNode * p, free_retired_ptr_func pFunc )
- {
- assert( !isFull());
-
- size_t n = m_nFreeList;
- assert( m_arr[n].m_pNode.load( atomics::memory_order_relaxed ) == nullptr );
- m_nFreeList = m_arr[n].m_nNextFree;
- CDS_DEBUG_ONLY( m_arr[n].m_nNextFree = m_nEndFreeList ; )
- m_arr[n].set( p, pFunc );
- }
-
- /// Pops the item by index \p n from the array
- void pop( size_t n )
- {
- assert( n < capacity() );
- m_arr[n].m_pNode.store( nullptr, atomics::memory_order_release );
- m_arr[n].m_nNextFree = m_nFreeList;
- m_nFreeList = n;
- }
-
- /// Checks if array is full
- bool isFull() const
- {
- return m_nFreeList == m_nEndFreeList;
- }
-
- /// Get the item by index \p i
- retired_node& operator []( size_t i )
- {
- assert( i < capacity() );
- return m_arr[i];
- }
-
- /// Returns a random-access iterator to the first element in the retired pointer vector
- /**
- If the vector is empty, end() == begin().
- */
- iterator begin()
- {
- return m_arr.begin();
- }
-
- /// Const version of begin()
- const_iterator begin() const
- {
- return m_arr.begin();
- }
-
- /// A random-access iterator to the end of the vector object.
- /**
- If the vector is empty, end() == begin().
- */
- iterator end()
- {
- return m_arr.end();
- }
-
- /// Const version of end()
- const_iterator end() const
- {
- return m_arr.end();
- }
- };
-
- } // namespace details
-}}} // namespace cds::gc::hrc
-
-#endif // #ifndef __CDS_GC_HRC_SCHEMA_RETIRED_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_GC_HRC_SCHEMA_GC_FWD_H
-#define __CDS_GC_HRC_SCHEMA_GC_FWD_H
-
-#include <cds/details/defs.h>
-
-//@cond
-namespace cds { namespace gc { namespace hrc {
- // Forward declaration
- class GC;
-}}} // namespace cds::gc::hrc
-//@endcond
-
-#endif // #ifndef __CDS_GC_HRC_SCHEMA_GC_FWD_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_GC_HRC_HRC_H
-#define __CDS_GC_HRC_HRC_H
-
-/*
- Editions:
- 2008.03.08 Maxim.Khiszinsky Created
-*/
-
-#include <cds/refcounter.h>
-#include <cds/lock/spinlock.h>
-#include <cds/gc/exception.h>
-
-#include <cds/gc/hrc/details/hrc_fwd.h>
-#include <cds/gc/hrc/details/hrc_retired.h>
-
-#include <cds/gc/hzp/details/hp_alloc.h>
-
-#if CDS_COMPILER == CDS_COMPILER_MSVC
-# pragma warning(push)
-// warning C4251: 'cds::gc::hzp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomic::atomic<T>'
-// needs to have dll-interface to be used by clients of class 'cds::gc::hzp::GarbageCollector'
-# pragma warning(disable: 4251)
-#endif
-
-
-namespace cds { namespace gc {
-
- // forwards
- class HRC;
-
- /// Gidenstam's memory reclamation schema (HRC)
- /**
-
- \par Sources:
- - [2006] A.Gidenstam "Algorithms for synchronization and consistency
- in concurrent system services", Chapter 5 "Lock-Free Memory Reclamation"
- Thesis for the degree of Doctor of Philosophy
- - [2005] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas "Allocating
- memory in a lock-free manner", Proceedings of the 13th Annual European
- Symposium on Algorithms (ESA 2005), Lecture Notes in Computer
- Science Vol. 3669, pages 229 \96 242, Springer-Verlag, 2005
-
-
- The \p %cds::gc::hrc namespace and its members are internal representation of the GC and should not be used directly.
- Use \p cds::gc::HRC class in your code.
-
- This reclamation schema combines Michael's Hazard Pointer schema (see \p cds::gc::hzp)
- for deferred safe reclamation of unused objects and the reference counting
- for controlling lifetime of the objects.
-
- HRC garbage collector is a singleton. The main user-level part of HRC schema is
- GC class and its nested classes. Before use any HRC-related class you must initialize HRC garbage collector
- by contructing \p %cds::gc::HRC object in beginning of your <tt>main()</tt>.
- See \p cds::gc::HRC class for explanation.
- */
- namespace hrc {
-
- /// Base class for all HRC-based container's node
- /**
- This interface is placed to the separate class since in the presence of a garbage collector
- the lifetime of the node is greater than lifetime of its container.
- Reclaimed node may be physically deleted later than its container.
- So, the ContainerNode must be smarter than the usual.
- */
- class ContainerNode
- {
- protected:
-
- friend class GarbageCollector;
- friend class ThreadGC;
- friend class gc::HRC;
-
- unsigned_ref_counter m_RC ; ///< reference counter
- atomics::atomic<bool> m_bTrace ; ///< \p true - node is tracing by Scan
- atomics::atomic<bool> m_bDeleted ; ///< \p true - node is deleted
-
- protected:
- //@cond
- ContainerNode() ; // inline, see hrc_inline.h
- virtual ~ContainerNode() ; // inline, see hrc_inline.h
- //@endcond
-
- public:
- /// Returns count of reference for the node
- unsigned_ref_counter::ref_counter_type getRefCount() const CDS_NOEXCEPT
- {
- return m_RC.value();
- }
-
- /// Increments the reference counter of the node
- void incRefCount() CDS_NOEXCEPT
- {
- m_RC.inc();
- }
-
- /// Decrements the reference counter of the node. Returns \p true if ref counter is 0.
- bool decRefCount() CDS_NOEXCEPT
- {
- return m_RC.dec();
- }
-
- /// Returns the mark whether the node is deleted
- bool isDeleted() const CDS_NOEXCEPT
- {
- return m_bDeleted.load( atomics::memory_order_acquire );
- }
-
- protected:
- //@cond
- void clean( atomics::memory_order order ) CDS_NOEXCEPT
- {
- m_bDeleted.store( false, order );
- m_bTrace.store( false, order );
- }
- //@endcond
-
- protected: // GC interface
- /**
- [Gidenstam 2006]: "The procedure \p CleanUpNode will make sure that all claimed references from
- the links of the given node will only point to active nodes, thus removing redundant
- passages through an arbitrary number of deleted nodes"
-
- The pseudocode of this method must be like following:
- \code
- void cleanUp( ThreadGC * pGC )
- for all x where link[x] of node is reference-counted do
- retry:
- node1 := link[x];
- if node1 != nullptr and node1.m_bDeleted then
- node2 := node1->link[x];
- pGC->CASRef( this->link[x], node1, node2 );
- pGC->releaseRef( node2 );
- pGC->releaseRef( node1 );
- goto retry;
- pGC->releaseRef(node1);
- \endcode
-
- Be aware to use hazard pointers inside implementation of this method. cleanUp is called from
- the container's method when deleting the nodes. However, some hazard pointers may be occupied
- by container's method. You should allocate new hazard pointers inside \p cleanUp method, for example:
- \code
- gc::hrc::AutoHPArray<2> hpArr( *pGC );
- \endcode
- */
- virtual void cleanUp( ThreadGC * pGC ) = 0;
-
- /**
- [Gidenstam 2006]: "The procedure \p TerminateNode will make sure that none of the links in the
- given node will have any claim on any other node. TerminateNode is called on
- a deleted node when there are no claims from any other node or thread to the
- node"
-
- The pseudocode of this method must be like following:
- \code
- void terminate( ThreadGC * pGC, bool bConcurrent)
- if !bConcurrent
- for all this->link where link is reference-counted do
- link := nullptr;
- else
- for all this->link where link is reference-counted do
- repeat node1 := link;
- until pGC->CASRef(link,node1,nullptr);
- \endcode
- */
- virtual void terminate( ThreadGC * pGC, bool bConcurrent ) = 0;
-
- public:
- /// Method to destroy (deallocate) node. Depends on node's allocator
- //virtual void destroy() = 0;
- };
-
- //@cond
- /// HRC GC implementation details
- namespace details {
-
- /// Hazard pointer guard
- typedef gc::hzp::details::HPGuardT<ContainerNode *> HPGuard;
-
- /// Array of hazard pointers.
- /**
- This is wrapper for cds::gc::hzp::details::HPArray class
- */
- template <size_t Count> using HPArray = gc::hzp::details::HPArrayT<ContainerNode *, Count >;
-
- /// HP record of the thread
- /**
- This structure is single writer - multiple reader type. The writer is the thread owned the record
- */
- struct thread_descriptor {
- typedef ContainerNode * hazard_ptr ; ///< base type of hazard pointer
-
- hzp::details::HPAllocator<hazard_ptr> m_hzp ; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependence
- details::retired_vector m_arrRetired ; ///< array of retired pointers
-
- //@cond
- thread_descriptor( const GarbageCollector& HzpMgr ) ; // inline
- ~thread_descriptor()
- {}
- //@endcond
-
- /// clear all hazard pointers
- void clear()
- {
- m_hzp.clear();
- }
- };
- } // namespace details
- //@endcond
-
- /// Gidenstam's Garbage Collector
- /**
- This GC combines Hazard Pointers (HP) reclamation method by Michael's and the well-known reference counting
- reclamation schema. The HP method is light-weight algorithm guarding local references only. Reference counting
- schema is harder than HP with relation to the performance but can guard global references too.
- Using Gidenstam's GC it can be possible to safely introduce to the lock-free data structures
- very useful concepts like iterators.
-
- GarbageCollector is the singleton.
- */
- class CDS_EXPORT_API GarbageCollector
- {
- public:
- typedef cds::atomicity::event_counter event_counter ; ///< event counter type
-
- /// GC internal statistics
- struct internal_state {
- size_t nHPCount ; ///< HP count per thread (const)
- size_t nMaxThreadCount ; ///< Max thread count (const)
- size_t nMaxRetiredPtrCount ; ///< Max retired pointer count per thread (const)
- size_t nHRCRecSize ; ///< Size of HRC record, bytes (const)
-
- size_t nHRCRecAllocated ; ///< Count of HRC record allocations
- size_t nHRCRecUsed ; ///< Count of HRC record used
- size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers
- size_t nRetiredPtrInFreeHRCRecs; ///< Count of retired pointer in free (unused) HP records
-
-
- event_counter::value_type evcAllocHRCRec ; ///< Event count of thread descriptor allocation
- event_counter::value_type evcRetireHRCRec ; ///< Event count of thread descriptor reclamation
- event_counter::value_type evcAllocNewHRCRec ; ///< Event count of new thread descriptor allocation
- event_counter::value_type evcDeleteHRCRec ; ///< Event count of thread descriptor deletion
- event_counter::value_type evcScanCall ; ///< Number of calls Scan
- event_counter::value_type evcHelpScanCalls ; ///< Number of calls HelpScan
- event_counter::value_type evcCleanUpAllCalls ; ///< Number of calls CleanUpAll
- event_counter::value_type evcDeletedNode ; ///< Node deletion event counter
- event_counter::value_type evcScanGuarded ; ///< Count of retired nodes that could not be deleted on Scan phase
- event_counter::value_type evcScanClaimGuarded ; ///< Count of retired node that could not be deleted on Scan phase because of m_nClaim != 0
-
-#ifdef CDS_DEBUG
- event_counter::value_type evcNodeConstruct ; ///< Count of constructed ContainerNode
- event_counter::value_type evcNodeDestruct ; ///< Count of destructed ContainerNode
-#endif
- };
-
- /// "Global GC object is nullptr" exception
- CDS_DECLARE_EXCEPTION( HRCGarbageCollectorEmpty, "Global cds::gc::hrc::GarbageCollector is NULL" );
-
- /// Not enough required Hazard Pointer count
- CDS_DECLARE_EXCEPTION( HRCTooMany, "Not enough required Hazard Pointer count" );
-
- private:
- /// Internal statistics by events
- struct statistics {
- event_counter m_AllocHRCThreadDesc ; ///< Event count of thread descriptor allocation
- event_counter m_RetireHRCThreadDesc ; ///< Event count of thread descriptor reclamation
- event_counter m_AllocNewHRCThreadDesc ; ///< Event count of new thread descriptor allocation
- event_counter m_DeleteHRCThreadDesc ; ///< Event count of deletion of thread descriptor
- event_counter m_ScanCalls ; ///< Number of calls Scan
- event_counter m_HelpScanCalls ; ///< Number of calls HelpScan
- event_counter m_CleanUpAllCalls ; ///< Number of calls CleanUpAll
-
- event_counter m_DeletedNode ; ///< Node deletion event counter
- event_counter m_ScanGuarded ; ///< Count of retired nodes that could not be deleted on Scan phase
- event_counter m_ScanClaimGuarded ; ///< Count of retired node that could not be deleted on Scan phase because of m_nClaim != 0
-
-# ifdef CDS_DEBUG
- event_counter m_NodeConstructed ; ///< Count of ContainerNode constructed
- event_counter m_NodeDestructed ; ///< Count of ContainerNode destructed
-# endif
- };
-
- /// HRC control structure of global thread list
- struct thread_list_node: public details::thread_descriptor
- {
- thread_list_node * m_pNext ; ///< next list record
- ThreadGC * m_pOwner ; ///< Owner of record
- atomics::atomic<cds::OS::ThreadId> m_idOwner ; ///< Id of thread owned; 0 - record is free
- bool m_bFree ; ///< Node is help-scanned
-
- //@cond
- thread_list_node( const GarbageCollector& HzpMgr )
- : thread_descriptor( HzpMgr ),
- m_pNext( nullptr ),
- m_pOwner( nullptr ),
- m_idOwner(cds::OS::c_NullThreadId),
- m_bFree( false )
- {}
-
- ~thread_list_node()
- {
- assert( m_pOwner == nullptr );
- assert( m_idOwner.load( atomics::memory_order_relaxed ) == cds::OS::c_NullThreadId );
- }
- //@endcond
- };
-
- private:
- atomics::atomic<thread_list_node *> m_pListHead ; ///< Head of thread list
-
- static GarbageCollector * m_pGC ; ///< HRC garbage collector instance
-
- statistics m_Stat ; ///< Internal statistics
- bool m_bStatEnabled ; ///< @a true - accumulate internal statistics
-
- const size_t m_nHazardPointerCount ; ///< max count of thread's hazard pointer
- const size_t m_nMaxThreadCount ; ///< max count of thread
- const size_t m_nMaxRetiredPtrCount ; ///< max count of retired ptr per thread
-
- private:
- //@cond
- GarbageCollector(
- size_t nHazardPtrCount, ///< number of hazard pointers
- size_t nMaxThreadCount, ///< max number of threads
- size_t nRetiredNodeArraySize ///< size of array of retired node
- );
- ~GarbageCollector();
- //@endcond
-
- /// Allocates new HRC control structure from the heap (using operator new)
- thread_list_node * newHRCThreadDesc();
-
- /// Deletes \p pNode control structure
- void deleteHRCThreadDesc( thread_list_node * pNode );
-
- /// Clears retired nodes of \p pNode control structure
- void clearHRCThreadDesc( thread_list_node * pNode );
-
- /// Finds HRC control structure for current thread
- thread_list_node * getHRCThreadDescForCurrentThread() const;
-
- public:
- /// Create global instance of GarbageCollector
- static void CDS_STDCALL Construct(
- size_t nHazardPtrCount = 0, ///< number of hazard pointers
- size_t nMaxThreadCount = 0, ///< max threads count
- size_t nMaxNodeLinkCount = 0, ///< max number of links a @ref ContainerNode can contain
- size_t nMaxTransientLinks = 0 ///< max number of links in live nodes that may transiently point to a deleted node
- );
-
- /// Destroy global instance of GarbageCollector
- static void CDS_STDCALL Destruct();
-
- /// Get global instance of GarbageCollector
- static GarbageCollector& instance()
- {
- if ( !m_pGC )
- throw HRCGarbageCollectorEmpty();
- return *m_pGC;
- }
-
- /// Checks if global GC object is constructed and may be used
- static bool isUsed()
- {
- return m_pGC != nullptr;
- }
-
- /// Get max count of hazard pointers as defined in @ref Construct call
- size_t getHazardPointerCount() const
- {
- return m_nHazardPointerCount;
- }
-
- /// Get max thread count as defined in @ref Construct call
- size_t getMaxThreadCount() const
- {
- return m_nMaxThreadCount;
- }
-
- /// Get max retired pointers count. It is calculated by the parameters of @ref Construct call
- size_t getMaxRetiredPtrCount() const
- {
- return m_nMaxRetiredPtrCount;
- }
-
- /// Get internal statistics
- internal_state& getInternalState( internal_state& stat) const;
-
- /// Check if statistics enabled
- bool isStatisticsEnabled() const
- {
- return m_bStatEnabled;
- }
-
- /// Enable internal statistics
- bool enableStatistics( bool bEnable )
- {
- bool bCurEnabled = m_bStatEnabled;
- m_bStatEnabled = bEnable;
- return bCurEnabled;
- }
-
- /// Checks that required hazard pointer count \p nRequiredCount is less or equal then max hazard pointer count
- /**
- If \p nRequiredCount > getHazardPointerCount() then the exception HZPTooMany is thrown
- */
- static void checkHPCount( unsigned int nRequiredCount )
- {
- if ( instance().getHazardPointerCount() < nRequiredCount )
- throw HRCTooMany();
- }
-
- public: // Internals for threads
-
- /// Allocates HRC thread descriptor (thread interface)
- details::thread_descriptor * allocateHRCThreadDesc( ThreadGC * pThreadGC );
-
- /// Retires HRC thread descriptor (thread interface)
- void retireHRCThreadDesc( details::thread_descriptor * pRec );
-
- /// The main method of GC
- /**
- The procedure searches through all not yet reclaimed nodes deleted by this thread
- and reclaim only those that does not have any matching hazard pointers and do not have any
- counted references from any links inside of nodes.
- @a Scan is called in context of thread owned \p pRec.
- */
- void Scan( ThreadGC * pThreadGC );
-
- /// Manage free thread_descriptor records and move all retired pointers to \p pThreadGC
- void HelpScan( ThreadGC * pThreadGC );
-
- /// Global clean up
- /**
- The procedure try to remove redundant claimed references from links in deleted nodes
- that has been deleted by any thread. \p pThreadGC - ThreadGC of calling thread
- */
- void CleanUpAll( ThreadGC * pThreadGC );
-
- //@cond
- void try_retire( ThreadGC * pThreadGC ) ; // inline in hrc_inline.h
- //@endcond
-
-# ifdef CDS_DEBUG
- public:
- //@cond
- void dbgNodeConstructed() { ++m_Stat.m_NodeConstructed; }
- void dbgNodeDestructed() { ++m_Stat.m_NodeDestructed; }
- //@endcond
-# endif
-
- };
-
- class AutoHPGuard;
-
- /// Thread's Garbage collector
- /**
- To use HRC reclamation schema each thread object must be linked with the object of ThreadGC class
- that interacts with GarbageCollector global object. The linkage is performed by calling cds::threading \p Manager::attachThread()
- on the start of each thread that uses HRC GC. Before terminating the thread linked to HRC GC it is necessary to call
- cds::threading \p Manager::detachThread().
- */
- class ThreadGC
- {
- GarbageCollector& m_gc ; ///< master garbage collector
- details::thread_descriptor * m_pDesc ; ///< descriptor of GC data for the thread
-
- friend class GarbageCollector;
-
- public:
- //@cond
- ThreadGC()
- : m_gc( GarbageCollector::instance() )
- , m_pDesc( nullptr )
- {}
-
- ThreadGC( ThreadGC const& ) = delete;
-
- ~ThreadGC()
- {
- fini();
- }
- //@endcond
-
- /// Checks if thread GC is initialized
- bool isInitialized() const { return m_pDesc != nullptr; }
-
- /// Initialization. Multiple calls is allowed
- void init()
- {
- if ( !m_pDesc )
- m_pDesc = m_gc.allocateHRCThreadDesc( this );
- }
-
- /// Finalization. Multiple calls is allowed
- void fini()
- {
- if ( m_pDesc ) {
- cleanUpLocal();
- m_gc.Scan( this );
- details::thread_descriptor * pRec = m_pDesc;
- m_pDesc = nullptr;
- if ( pRec )
- m_gc.retireHRCThreadDesc( pRec );
- }
- }
- public: // HRC garbage collector methods
-
- /// Initializes HP guard \p guard
- details::HPGuard& allocGuard()
- {
- assert( m_pDesc != nullptr );
- return m_pDesc->m_hzp.alloc();
- }
-
- /// Frees HP guard \p guard
- void freeGuard( details::HPGuard& guard )
- {
- assert( m_pDesc != nullptr );
- m_pDesc->m_hzp.free( guard );
- }
-
- /// Initializes HP guard array \p arr
- template <size_t Count>
- void allocGuard( details::HPArray<Count>& arr )
- {
- assert( m_pDesc != nullptr );
- m_pDesc->m_hzp.alloc( arr );
- }
-
- /// Frees HP guard array \p arr
- template <size_t Count>
- void freeGuard( details::HPArray<Count>& arr )
- {
- assert( m_pDesc != nullptr );
- m_pDesc->m_hzp.free( arr );
- }
-
- /// Retire (deferred delete) node \p pNode guarded by \p hp hazard pointer
- void retireNode( ContainerNode * pNode, details::HPGuard& hp, details::free_retired_ptr_func pFunc )
- {
- assert( !pNode->m_bDeleted.load( atomics::memory_order_relaxed ) );
- assert( pNode == hp );
-
- retireNode( pNode, pFunc );
- hp.clear();
- }
-
- /// Retire (deferred delete) node \p pNode. Do not use this function directly!
- void retireNode( ContainerNode * pNode, details::free_retired_ptr_func pFunc )
- {
- assert( !pNode->m_bDeleted.load( atomics::memory_order_relaxed ) );
-
- pNode->m_bDeleted.store( true, atomics::memory_order_release );
- pNode->m_bTrace.store( false, atomics::memory_order_release );
-
- m_pDesc->m_arrRetired.push( pNode, pFunc );
-
- if ( m_pDesc->m_arrRetired.isFull() )
- m_gc.try_retire( this );
- }
-
- //@cond
- void scan()
- {
- m_gc.try_retire( this );
- }
- //@endcond
-
- protected:
- /// The procedure will try to remove redundant claimed references from link in deleted nodes that has been deleted by this thread
- void cleanUpLocal()
- {
- details::retired_vector::iterator itEnd = m_pDesc->m_arrRetired.end();
- for ( details::retired_vector::iterator it = m_pDesc->m_arrRetired.begin(); it != itEnd; ++it ) {
- details::retired_node& node = *it;
- ContainerNode * pNode = node.m_pNode.load(atomics::memory_order_acquire);
- if ( pNode && !node.m_bDone.load(atomics::memory_order_acquire) )
- pNode->cleanUp( this );
- }
- }
- };
-
- /// Auto HPGuard.
- class AutoHPGuard
- {
- //@cond
- details::HPGuard& m_hp ; ///< hazard pointer
- ThreadGC& m_mgr ; ///< Thread GC.
- //@endcond
- public:
- typedef details::HPGuard::hazard_ptr hazard_ptr ; ///< Hazard pointer type
-
- public:
- /// Allocates HP guard from \p mgr
- AutoHPGuard( ThreadGC& mgr )
- : m_hp( mgr.allocGuard() )
- , m_mgr( mgr )
- {}
-
- /// Allocates HP guard from \p mgr and protects the pointer \p p of type \p T
- template <typename T>
- AutoHPGuard( ThreadGC& mgr, T * p )
- : m_hp( mgr.allocGuard() )
- , m_mgr( mgr )
- {
- m_hp = p;
- }
-
- /// Frees HP guard
- ~AutoHPGuard()
- {
- m_mgr.freeGuard( m_hp );
- }
-
- /// Returns thread GC
- ThreadGC& getGC() const CDS_NOEXCEPT
- {
- return m_mgr;
- }
-
- //@cond
- template <typename T>
- T * operator =( T * p ) CDS_NOEXCEPT
- {
- return m_hp = p;
- }
- //@endcond
-
- //@cond
- hazard_ptr get() const CDS_NOEXCEPT
- {
- return m_hp;
- }
- //@endcond
-
- /// Clears the hazard pointer
- void clear() CDS_NOEXCEPT
- {
- m_hp.clear();
- }
- };
-
- /// Auto-managed array of hazard pointers
- /**
- This class is wrapper around gc::hzp::details::HPArray class.
- */
- template <size_t Count>
- class AutoHPArray: public details::HPArray<Count>
- {
- ThreadGC& m_mgr ; ///< Thread GC
-
- public:
- /// Allocates array of HP guard from \p mgr
- AutoHPArray( ThreadGC& mgr )
- : m_mgr( mgr )
- {
- mgr.allocGuard( *this );
- }
-
- /// Frees array of HP guard
- ~AutoHPArray()
- {
- m_mgr.freeGuard( *this );
- }
-
- /// Returns thread GC
- ThreadGC& getGC() const
- {
- return m_mgr;
- }
- };
-
-
- } // namespace hrc
-}} // namespace cds::gc
-
-#include <cds/gc/hrc/details/hrc_inline.h>
-
-#if CDS_COMPILER == CDS_COMPILER_MSVC
-# pragma warning(pop)
-#endif
-
-#endif // #ifndef __CDS_GC_HRC_HRC_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_GC_HRC_DECL_H
-#define __CDS_GC_HRC_DECL_H
-
-#include <cds/gc/hrc/hrc.h>
-#include <cds/details/marked_ptr.h>
-
-namespace cds { namespace gc {
-
- /// Gidenstam's garbage collector
- /** @ingroup cds_garbage_collector
- @headerfile cds/gc/hrc.h
-
- This class is a wrapper for Gidenstam's memory reclamation schema (HRC - Hazard pointer + Reference Counting)
- internal implementation.
-
- Sources:
- - [2006] A.Gidenstam "Algorithms for synchronization and consistency
- in concurrent system services", Chapter 5 "Lock-Free Memory Reclamation"
- Thesis for the degree of Doctor of Philosophy
- - [2005] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas "Allocating
- memory in a lock-free manner", Proceedings of the 13th Annual European
- Symposium on Algorithms (ESA 2005), Lecture Notes in Computer
- Science Vol. 3669, pages 229 \96 242, Springer-Verlag, 2005
-
- Note that HRC schema does not support cyclic references that significantly limits the applicability of this GC.
-
- <h1>Usage</h1>
- In your \p main function you declare a object of class cds::gc::HRC. This declaration
- initializes internal hrc::GarbageCollector singleton.
- \code
- #include <cds/init.h> // for cds::Initialize and cds::Terminate
- #include <cds/gc/hrc.h>
-
- int main(int argc, char** argv)
- {
- // Initialize libcds
- cds::Initialize();
-
- {
- // Initialize HRC singleton
- cds::gc::HRC hpGC();
-
- // Some useful work
- ...
- }
-
- // Terminate libcds
- cds::Terminate();
- }
- \endcode
-
- Each thread that uses cds::gc::HRC -based containers must be attached to HRC
- singleton. To make attachment you should declare a object of class HRC::thread_gc:
- \code
- #include <cds/gc/hrc.h>
-
- int myThreadEntryPoint()
- {
- // Attach the thread to HRC singleton
- cds::gc::HRC::thread_gc myThreadGC();
-
- // Do some work
- ...
-
- // The destructor of myThreadGC object detaches the thread from HRC singleton
- }
- \endcode
-
- In some cases, you should work in a external thread. For example, your application
- is a plug-in for a server that calls your code in the threads that has been created by server.
- In this case, you may use persistent mode of HRC::thread_gc. In this mode, the thread attaches
- to the HRC singleton only if it is not yet attached and never call detaching:
- \code
- #include <cds/gc/hrc.h>
-
- int myThreadEntryPoint()
- {
- // Attach the thread in persistent mode
- cds::gc::HRC::thread_gc myThreadGC( true );
-
- // Do some work
- ...
-
- // The destructor of myThreadGC object does NOT detach the thread from HRC singleton
- }
- \endcode
-
- */
- class HRC
- {
- public:
-
- /// Thread GC implementation for internal usage
- typedef hrc::ThreadGC thread_gc_impl;
-
- /// Wrapper for hrc::ThreadGC class
- /**
- @headerfile cds/gc/hrc.h
- This class performs automatically attaching/detaching Gidenstam's GC
- for the current thread.
- */
- class thread_gc: public thread_gc_impl
- {
- //@cond
- bool m_bPersistent;
- //@endcond
- public:
- /// Constructor
- /**
- The constructor attaches the current thread to the Gidenstam's GC
- if it is not yet attached.
- The \p bPersistent parameter specifies attachment persistence:
- - \p true - the class destructor will not detach the thread from Gidenstam's GC.
- - \p false (default) - the class destructor will detach the thread from Gidenstam's GC.
- */
- thread_gc(
- bool bPersistent = false
- ) ; // inline in hrc_impl.h
-
- /// Destructor
- /**
- If the object has been created in persistent mode, the destructor does nothing.
- Otherwise it detaches the current thread from HRC GC.
- */
- ~thread_gc() ; // inline in hrc_impl.h
- };
-
- ///@anchor hrc_gc_HRC_container_node Base for container node
- typedef hrc::ContainerNode container_node;
-
- /// Native hazard pointer type
- typedef container_node * guarded_pointer;
-
- /// Atomic reference
- /**
- @headerfile cds/gc/hrc.h
- */
- template <typename T>
- class atomic_ref: protected atomics::atomic<T *>
- {
- //@cond
- typedef atomics::atomic<T *> base_class;
- //@endcond
- public:
- //@cond
- atomic_ref() = default;
- explicit CDS_CONSTEXPR atomic_ref(T * p) CDS_NOEXCEPT
- : base_class( p )
- {}
- //@endcond
-
- /// Read reference value
- T * load( atomics::memory_order order ) const CDS_NOEXCEPT
- {
- return base_class::load( order );
- }
- //@cond
- T * load( atomics::memory_order order ) const volatile CDS_NOEXCEPT
- {
- return base_class::load( order );
- }
- //@endcond
-
- /// Store new value to reference
- void store( T * pNew, atomics::memory_order order ) CDS_NOEXCEPT
- {
- before_store( pNew );
- T * pOld = base_class::exchange( pNew, order );
- after_store( pOld, pNew );
- }
- //@cond
- void store( T * pNew, atomics::memory_order order ) volatile CDS_NOEXCEPT
- {
- before_store( pNew );
- T * pOld = base_class::exchange( pNew, order );
- after_store( pOld, pNew );
- }
- //@endcond
-
- /// Updates atomic reference from current value \p pOld to new value \p pNew (strong CAS)
- /**
- May be used when concurrent updates are possible
-
- \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
- */
- bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
- {
- before_cas( pNew );
- bool bSuccess = base_class::compare_exchange_strong( pOld, pNew, mo_success, mo_fail );
- after_cas( bSuccess, pOld, pNew );
- return bSuccess;
- }
- //@cond
- bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) volatile CDS_NOEXCEPT
- {
- before_cas( pNew );
- bool bSuccess = base_class::compare_exchange_strong( pOld, pNew, mo_success, mo_fail );
- after_cas( bSuccess, pOld, pNew );
- return bSuccess;
- }
- bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
- {
- return compare_exchange_strong( pOld, pNew, mo_success, atomics::memory_order_relaxed );
- }
- bool compare_exchange_strong( T *& pOld, T * pNew, atomics::memory_order mo_success ) volatile CDS_NOEXCEPT
- {
- return compare_exchange_strong( pOld, pNew, mo_success, atomics::memory_order_relaxed );
- }
- //@endcond
-
- /// Updates atomic reference from current value \p pOld to new value \p pNew (weak CAS)
- /**
- May be used when concurrent updates are possible
-
- \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
- */
- bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
- {
- before_cas( pNew );
- bool bSuccess = base_class::compare_exchange_weak( pOld, pNew, mo_success, mo_fail );
- after_cas( bSuccess, pOld, pNew );
- return bSuccess;
- }
- //@cond
- bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) volatile CDS_NOEXCEPT
- {
- before_cas( pNew );
- bool bSuccess = base_class::compare_exchange_weak( pOld, pNew, mo_success, mo_fail );
- after_cas( bSuccess, pOld, pNew );
- return bSuccess;
- }
- bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
- {
- return compare_exchange_weak( pOld, pNew, mo_success, atomics::memory_order_relaxed );
- }
- bool compare_exchange_weak( T *& pOld, T * pNew, atomics::memory_order mo_success ) volatile CDS_NOEXCEPT
- {
- return compare_exchange_weak( pOld, pNew, mo_success, atomics::memory_order_relaxed );
- }
- //@endcond
-
- private:
- //@cond
- static void before_store( T * pNew ) CDS_NOEXCEPT
- {
- if ( pNew )
- ++pNew->m_RC;
- }
- static void after_store( T * pOld, T * pNew ) CDS_NOEXCEPT
- {
- if ( pNew )
- pNew->m_bTrace.store( false, atomics::memory_order_release );
- if ( pOld )
- --pOld->m_RC;
- }
- static void before_cas( T * p ) CDS_NOEXCEPT
- {
- if ( p ) {
- ++p->m_RC;
- p->m_bTrace.store( false, atomics::memory_order_release );
- }
- }
- static void after_cas( bool bSuccess, T * pOld, T * pNew ) CDS_NOEXCEPT
- {
- if ( bSuccess ) {
- if ( pOld )
- --pOld->m_RC;
- }
- else {
- if ( pNew )
- --pNew->m_RC;
- }
- }
- //@endcond
- };
-
- /// Atomic marked pointer
- /**
- @headerfile cds/gc/hrc.h
- */
- template <typename MarkedPtr>
- class atomic_marked_ptr
- {
- //@cond
- atomics::atomic< MarkedPtr > m_a;
- //@endcond
- public:
- /// Marked pointer type
- typedef MarkedPtr marked_ptr;
-
- //@cond
- atomic_marked_ptr() CDS_NOEXCEPT
- : m_a( marked_ptr() )
- {}
-
- explicit CDS_CONSTEXPR atomic_marked_ptr( typename marked_ptr::value_type * p ) CDS_NOEXCEPT
- : m_a( marked_ptr(p) )
- {}
-
- atomic_marked_ptr( typename marked_ptr::value_type * ptr, int nMask ) CDS_NOEXCEPT
- : m_a( marked_ptr(ptr, nMask) )
- {}
-
- explicit atomic_marked_ptr( marked_ptr const& ptr ) CDS_NOEXCEPT
- : m_a( ptr )
- {}
- //@endcond
-
-
- /// Read reference value
- marked_ptr load(atomics::memory_order order) const CDS_NOEXCEPT
- {
- return m_a.load(order);
- }
-
- /// Store new value to reference
- void store( marked_ptr pNew, atomics::memory_order order ) CDS_NOEXCEPT
- {
- before_store( pNew.ptr() );
- marked_ptr pOld = m_a.exchange( pNew, order );
- after_store( pOld.ptr(), pNew.ptr() );
- }
-
- /// Store new value to reference
- void store( typename marked_ptr::pointer_type pNew, atomics::memory_order order ) CDS_NOEXCEPT
- {
- before_store( pNew );
- marked_ptr pOld = m_a.exchange( marked_ptr(pNew), order );
- after_store( pOld.ptr(), pNew );
- }
-
- /// Updates atomic reference from current value \p pOld to new value \p pNew (weak CAS)
- /**
- May be used when concurrent updates are possible
-
- \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
- */
- bool compare_exchange_weak( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
- {
- before_cas( pNew.ptr() );
- bool bSuccess = m_a.compare_exchange_weak( pOld, pNew, mo_success, mo_fail );
- after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
- return bSuccess;
- }
- //@cond
- bool compare_exchange_weak( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
- {
- before_cas( pNew.ptr() );
- bool bSuccess = m_a.compare_exchange_weak( pOld, pNew, mo_success );
- after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
- return bSuccess;
- }
- //@endcond
-
- /// Updates atomic reference from current value \p pOld to new value \p pNew (strong CAS)
- /**
- May be used when concurrent updates are possible
-
- \p T - class derived from \ref hrc_gc_HRC_container_node "container_node" type
- */
- bool compare_exchange_strong( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success, atomics::memory_order mo_fail ) CDS_NOEXCEPT
- {
- // protect pNew
- before_cas( pNew.ptr() );
- bool bSuccess = m_a.compare_exchange_strong( pOld, pNew, mo_success, mo_fail );
- after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
- return bSuccess;
- }
- //@cond
- bool compare_exchange_strong( marked_ptr& pOld, marked_ptr pNew, atomics::memory_order mo_success ) CDS_NOEXCEPT
- {
- before_cas( pNew.ptr() );
- bool bSuccess = m_a.compare_exchange_strong( pOld, pNew, mo_success );
- after_cas( bSuccess, pOld.ptr(), pNew.ptr() );
- return bSuccess;
- }
- //@endcond
-
- private:
- //@cond
- static void before_store( typename marked_ptr::pointer_type p ) CDS_NOEXCEPT
- {
- if ( p )
- ++p->m_RC;
- }
- static void after_store( typename marked_ptr::pointer_type pOld, typename marked_ptr::pointer_type pNew ) CDS_NOEXCEPT
- {
- if ( pNew )
- pNew->m_bTrace.store( false, atomics::memory_order_release );
- if ( pOld )
- --pOld->m_RC;
- }
- static void before_cas( typename marked_ptr::pointer_type p ) CDS_NOEXCEPT
- {
- if ( p ) {
- ++p->m_RC;
- p->m_bTrace.store( false, atomics::memory_order_release );
- }
- }
- static void after_cas( bool bSuccess, typename marked_ptr::pointer_type pOld, typename marked_ptr::pointer_type pNew ) CDS_NOEXCEPT
- {
- if ( bSuccess ) {
- if ( pOld )
- --pOld->m_RC;
- }
- else {
- if ( pNew )
- --pNew->m_RC;
- }
- }
- //@endcond
- };
-
- /// HRC guard
- /**
- @headerfile cds/gc/hrc.h
- This class is a wrapper for hrc::AutoHPGuard.
- */
- class Guard: public hrc::AutoHPGuard
- {
- //@cond
- typedef hrc::AutoHPGuard base_class;
- //@endcond
-
- public:
- /// Default constructor
- Guard() ; // inline in hrc_impl.h
-
- /// Protects atomic pointer
- /**
- Return the value of \p toGuard
-
- The function tries to load \p toGuard and to store it
- to the HP slot repeatedly until the guard's value equals \p toGuard
- */
- template <typename T>
- T * protect( atomic_ref<T> const& toGuard )
- {
- T * pCur = toGuard.load(atomics::memory_order_relaxed);
- T * pRet;
- do {
- pRet = assign( pCur );
- pCur = toGuard.load(atomics::memory_order_acquire);
- } while ( pRet != pCur );
- return pCur;
- }
-
- /// Protects a converted pointer of type \p atomic<T*>
- /**
- Return the value of \p toGuard
-
- The function tries to load \p toGuard and to store result of \p f functor
- to the HP slot repeatedly until the guard's value equals \p toGuard.
-
- The function is useful for intrusive containers when \p toGuard is a node pointer
- that should be converted to a pointer to the value type before guarding.
- The parameter \p f of type Func is a functor that makes this conversion:
- \code
- struct functor {
- value_type * operator()( T * p );
- };
- \endcode
- Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
- */
- template <typename T, class Func>
- T * protect( atomic_ref<T> const& toGuard, Func f )
- {
- T * pCur = toGuard.load(atomics::memory_order_relaxed);
- T * pRet;
- do {
- pRet = pCur;
- assign( f( pCur ) );
- pCur = toGuard.load(atomics::memory_order_acquire);
- } while ( pRet != pCur );
- return pCur;
- }
-
- /// Protects a atomic marked reference \p link
- /**
- Returns current value of \p link.
-
- The function tries to load \p link and to store it
- to the guard repeatedly until the guard's value equals \p link
- */
- template <typename T>
- typename atomic_marked_ptr<T>::marked_ptr protect( atomic_marked_ptr<T> const& link )
- {
- typename atomic_marked_ptr<T>::marked_ptr p;
- do {
- assign( ( p = link.load(atomics::memory_order_relaxed)).ptr() );
- } while ( p != link.load(atomics::memory_order_acquire) );
- return p;
- }
-
- /// Protects a atomic marked reference \p link
- /**
- Returns current value of \p link.
-
- The function tries to load \p link and to store it
- to the guard repeatedly until the guard's value equals \p link
-
- The function is useful for intrusive containers when \p link is a node pointer
- that should be converted to a pointer to the value type before guarding.
- The parameter \p f of type Func is a functor that makes this conversion:
- \code
- struct functor {
- value_type * operator()( T p );
- };
- \endcode
- Really, the result of <tt> f( link.load() ) </tt> is assigned to the hazard pointer.
- */
- template <typename T, typename Func>
- typename atomic_marked_ptr<T>::marked_ptr protect( atomic_marked_ptr<T> const& link, Func f )
- {
- typename atomic_marked_ptr<T>::marked_ptr pCur;
- do {
- pCur = link.load(atomics::memory_order_relaxed);
- assign( f( pCur ));
- } while ( pCur != link.load(atomics::memory_order_acquire) );
- return pCur;
- }
-
- /// Stores \p p to the guard
- /**
- The function equals to a simple assignment, no loop is performed.
- Can be used for a pointer that cannot be changed concurrently.
- */
- template <typename T>
- T * assign( T * p )
- {
- return base_class::operator =(p);
- }
-
- /// Stores marked pointer \p p to the guard
- /**
- The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
- Can be used for a marked pointer that cannot be changed concurrently.
- */
- template <typename T, int Bitmask>
- T * assign( cds::details::marked_ptr<T, Bitmask> p )
- {
- return base_class::operator =( p.ptr() );
- }
-
- /// Copy from \p src guard to \p this guard
- void copy( Guard const& src )
- {
- assign( src.get_native() );
- }
-
- /// Clear value of the guard
- void clear()
- {
- base_class::clear();
- }
-
- /// Get the value currently protected
- template <typename T>
- T * get() const
- {
- return static_cast<T *>( get_native());
- }
-
- /// Get native hazard pointer stored
- guarded_pointer get_native() const
- {
- return base_class::get();
- }
- };
-
- /// Array of guards
- /**
- @headerfile cds/gc/hrc.h
- This class is a wrapper for AutoHPArray template.
- Template parameter \p Limit defines the size of HP array.
- */
- template <size_t Limit>
- class GuardArray: public hrc::AutoHPArray<Limit>
- {
- //@cond
- typedef hrc::AutoHPArray<Limit> base_class;
- //@endcond
- public:
- /// Rebind array for other size \p OtherLimit
- template <size_t OtherLimit>
- struct rebind {
- typedef GuardArray<OtherLimit> other ; ///< rebinding result
- };
-
- public:
- //@cond
- GuardArray() ; // inline in hrc_impl.h
- GuardArray( thread_gc_impl& threadGC )
- : base_class( threadGC )
- {}
- //@endcond
-
- /// Protects an atomic reference \p link in slot \p nIndex
- /**
- Returns current value of \p link.
-
- The function tries to load \p pToGuard and to store it
- to the slot \p nIndex repeatedly until the guard's value equals \p pToGuard
- */
- template <typename T>
- T * protect( size_t nIndex, atomic_ref<T> const& link )
- {
- T * p;
- do {
- p = assign( nIndex, link.load(atomics::memory_order_relaxed) );
- } while ( p != link.load(atomics::memory_order_acquire) );
- return p;
- }
-
- /// Protects a atomic marked reference \p link in slot \p nIndex
- /**
- Returns current value of \p link.
-
- The function tries to load \p link and to store it
- to the slot \p nIndex repeatedly until the guard's value equals \p link
- */
- template <typename T>
- typename atomic_marked_ptr<T>::marked_ptr protect( size_t nIndex, atomic_marked_ptr<T> const& link )
- {
- typename atomic_marked_ptr<T>::marked_ptr p;
- do {
- assign( nIndex, ( p = link.load(atomics::memory_order_relaxed)).ptr() );
- } while ( p != link.load(atomics::memory_order_acquire) );
- return p;
- }
-
- /// Protects a pointer of type \p atomic<T*>
- /**
- Return the value of \p toGuard
-
- The function tries to load \p toGuard and to store it
- to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
-
- The function is useful for intrusive containers when \p toGuard is a node pointer
- that should be converted to a pointer to the value type before guarding.
- The parameter \p f of type Func is a functor that makes this conversion:
- \code
- struct functor {
- value_type * operator()( T * p );
- };
- \endcode
- Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
- */
- template <typename T, class Func>
- T * protect(size_t nIndex, atomic_ref<T> const& toGuard, Func f )
- {
- T * pRet;
- do {
- assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
- } while ( pRet != toGuard.load(atomics::memory_order_acquire));
-
- return pRet;
- }
-
- /// Protects a atomic marked reference \p link in slot \p nIndex
- /**
- Returns current value of \p link.
-
- The function tries to load \p link and to store it
- to the slot \p nIndex repeatedly until the guard's value equals \p link
-
- The function is useful for intrusive containers when \p link is a node pointer
- that should be converted to a pointer to the value type before guarding.
- The parameter \p f of type Func is a functor that makes this conversion:
- \code
- struct functor {
- value_type * operator()( T p );
- };
- \endcode
- Really, the result of <tt> f( link.load() ) </tt> is assigned to the hazard pointer.
- */
- template <typename T, typename Func>
- typename atomic_marked_ptr<T>::marked_ptr protect( size_t nIndex, atomic_marked_ptr<T> const& link, Func f )
- {
- typename atomic_marked_ptr<T>::marked_ptr p;
- do {
- p = link.load(atomics::memory_order_relaxed);
- assign( nIndex, f( p ) );
- } while ( p != link.load(atomics::memory_order_acquire) );
- return p;
- }
-
- /// Store \p to the slot \p nIndex
- /**
- The function equals to a simple assignment, no loop is performed.
- */
- template <typename T>
- T * assign( size_t nIndex, T * p )
- {
- base_class::set(nIndex, p);
- return p;
- }
-
- /// Store marked pointer \p p to the guard
- /**
- The function equals to a simple assignment of <tt>p.ptr()</tt>, no loop is performed.
- Can be used for a marked pointer that cannot be changed concurrently.
- */
- template <typename T, int Bitmask>
- T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
- {
- return base_class::set( nIndex, p.ptr() );
- }
-
- /// Copy guarded value from \p src guard to slot at index \p nIndex
- void copy( size_t nIndex, Guard const& src )
- {
- assign( nIndex, src.get_native() );
- }
-
- /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
- void copy( size_t nDestIndex, size_t nSrcIndex )
- {
- assign( nDestIndex, get_native( nSrcIndex ));
- }
-
- /// Clear value of the slot \p nIndex
- void clear( size_t nIndex)
- {
- base_class::clear( nIndex );
- }
-
- /// Get current value of slot \p nIndex
- template <typename T>
- T * get( size_t nIndex) const
- {
- return static_cast<T *>( get_native( nIndex ) );
- }
-
- /// Get native hazard pointer stored
- guarded_pointer get_native( size_t nIndex ) const
- {
- return base_class::operator[](nIndex).get();
- }
-
- /// Capacity of the guard array
- static CDS_CONSTEXPR size_t capacity()
- {
- return Limit;
- }
- };
-
- public:
- /// Initializes hrc::GarbageCollector singleton
- /**
- The constructor calls hrc::GarbageCollector::Construct with passed parameters.
- See hrc::GarbageCollector::Construct for explanation of parameters meaning.
- */
- HRC(
- size_t nHazardPtrCount = 0, ///< number of hazard pointers
- size_t nMaxThreadCount = 0, ///< max threads count
- size_t nMaxNodeLinkCount = 0, ///< max number of links a @ref hrc::ContainerNode can contain
- size_t nMaxTransientLinks = 0 ///< max number of links in live nodes that may transiently point to a deleted node
- )
- {
- hrc::GarbageCollector::Construct(
- nHazardPtrCount,
- nMaxThreadCount,
- nMaxNodeLinkCount,
- nMaxTransientLinks
- );
- }
-
- /// Terminates hrc::GarbageCollector singleton
- /**
- The destructor calls \code hrc::GarbageCollector::Destruct() \endcode
- */
- ~HRC()
- {
- hrc::GarbageCollector::Destruct();
- }
-
- /// Checks if count of hazard pointer is no less than \p nCountNeeded
- /**
- If \p bRaiseException is \p true (that is the default), the function raises an exception gc::too_few_hazard_pointers
- if \p nCountNeeded is more than the count of hazard pointer per thread.
- */
- static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
- {
- if ( hrc::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
- if ( bRaiseException )
- throw cds::gc::too_few_hazard_pointers();
- return false;
- }
- return true;
- }
-
- /// Retire pointer \p p with function \p pFunc
- /**
- The function places pointer \p p to array of pointers ready for removing.
- (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
- Deleting the pointer is the function \p pFunc call.
- */
- template <typename T>
- static void retire( T * p, void (* pFunc)(T *) ) ; // inline in hrc_impl.h
-
- /// Retire pointer \p p with functor of type \p Disposer
- /**
- The function places pointer \p p to array of pointers ready for removing.
- (so called retired pointer array). The pointer can be safely removed when no guard points to it.
-
- See gc::HP::retire for \p Disposer requirements.
- */
- template <class Disposer, typename T>
- static void retire( T * p ) ; // inline in hrc_impl.h
-
- /// Checks if HRC GC is constructed and may be used
- static bool isUsed()
- {
- return hrc::GarbageCollector::isUsed();
- }
-
- /// Forced GC cycle call for current thread
- /**
- Usually, this function should not be called directly.
- */
- static void scan() ; // inline in hrc_impl.h
-
- /// Synonym for \ref scan()
- static void force_dispose()
- {
- scan();
- }
- };
-}} // namespace cds::gc
-
-#endif // #ifndef __CDS_GC_HRC_DECL_H
+++ /dev/null
-//$$CDS-header$$
-
-#ifndef __CDS_GC_HRC_IMPL_H
-#define __CDS_GC_HRC_IMPL_H
-
-#include <cds/threading/model.h>
-#include <cds/details/static_functor.h>
-
-//@cond
-namespace cds { namespace gc {
-
- inline HRC::thread_gc::thread_gc(
- bool bPersistent
- )
- : m_bPersistent( bPersistent )
- {
- if ( !cds::threading::Manager::isThreadAttached() )
- cds::threading::Manager::attachThread();
- }
-
- inline HRC::thread_gc::~thread_gc()
- {
- if ( !m_bPersistent )
- cds::threading::Manager::detachThread();
- }
-
- inline HRC::Guard::Guard()
- : Guard::base_class( cds::threading::getGC<HRC>() )
- {}
-
- template <size_t COUNT>
- inline HRC::GuardArray<COUNT>::GuardArray()
- : GuardArray::base_class( threading::getGC<HRC>() )
- {}
-
- template <typename T>
- inline void HRC::retire( T * p, void (* pFunc)(T *) )
- {
- cds::threading::getGC<HRC>().retireNode( p, reinterpret_cast<details::free_retired_ptr_func>(pFunc) );
- }
-
- template <class Disposer, typename T>
- inline void HRC::retire( T * p )
- {
- cds::threading::getGC<HRC>().retireNode( p, reinterpret_cast<details::free_retired_ptr_func>( cds::details::static_functor<Disposer, T>::call ));
- }
-
- inline void HRC::scan()
- {
- cds::threading::getGC<HRC>().scan();
- }
-
-
-}} // namespace cds::gc
-//@endcond
-
-#endif // #ifndef __CDS_GC_HRC_IMPL_H
<tr>
<th>Feature</th>
<th>%cds::gc::HP</th>
- <th>%cds::gc::HRC</th>
<th>%cds::gc::PTB</th>
</tr>
<tr>
<td>Implementation quality</td>
<td>stable</td>
- <td>unstable</td>
<td>stable</td>
</tr>
<tr>
<td>Performance rank (1 - slowest, 5 - fastest)</td>
<td>5</td>
- <td>1</td>
<td>4</td>
</tr>
<tr>
<td>Max number of guarded (hazard) pointers per thread</td>
<td>limited (specifies in GC object ctor)</td>
- <td>limited (specifies in GC object ctor)</td>
<td>unlimited (dynamically allocated when needed)</td>
</tr>
<tr>
<td>Max number of retired pointers<sup>1</sup></td>
<td>bounded</td>
<td>bounded</td>
- <td>bounded</td>
</tr>
<tr>
<td>Array of retired pointers</td>
<td>preallocated for each thread, limited in size</td>
- <td>preallocated for each thread, limited in size</td>
<td>global for the entire process, unlimited (dynamically allocated when needed)</td>
</tr>
<tr>
<td>Support direct pointer to item of lock-free container (useful for iterators)</td>
<td>not supported</td>
- <td>potentially supported (not implemented)</td>
<td>not supported</td>
</tr>
</table>
/// Optimistic queue node
/**
Template parameters:
- - GC - garbage collector used. gc::HRC is not supported.
- - Tag - a tag used to distinguish between different implementation
+ - \p GC - garbage collector
+ - \p Tag - a \ref cds_intrusive_hook_tag "tag"
*/
template <class GC, typename Tag = opt::none>
struct node: public GC::container_node
/**
Possible values of \p GC template parameter are:
- cds::gc::HP - Hazard Pointer garbage collector
- - cds::gc::HRC - Gidenstam's garbage collector
- - cds::gc::PTB - Pass-the-Buck garbage collector
+ - cds::gc::DHP - Dynamic Hazard Pointer garbage collector
- cds::gc::none::GC - No garbage collector (not supported for some containers)
*/
template <typename GC>
#define __CDS_THREADING__COMMON_H
#include <cds/gc/hp_decl.h>
-#include <cds/gc/hrc_decl.h>
#include <cds/gc/ptb_decl.h>
#include <cds/urcu/details/gp_decl.h>
// Get cds::gc::HP thread GC implementation for current thread
static gc::HP::thread_gc_impl& getHZPGC();
- // Get cds::gc::HRC thread GC implementation for current thread
- static gc::HRC::thread_gc_impl& getHRCGC();
-
// Get cds::gc::PTB thread GC implementation for current thread;
static gc::PTB::thread_gc_impl& getPTBGC();
};
//@cond
char CDS_DATA_ALIGNMENT(8) m_hpManagerPlaceholder[sizeof(cds::gc::HP::thread_gc_impl)] ; ///< Michael's Hazard Pointer GC placeholder
- char CDS_DATA_ALIGNMENT(8) m_hrcManagerPlaceholder[sizeof(cds::gc::HRC::thread_gc_impl)] ; ///< Gidenstam's GC placeholder
char CDS_DATA_ALIGNMENT(8) m_ptbManagerPlaceholder[sizeof(cds::gc::PTB::thread_gc_impl)] ; ///< Pass The Buck GC placeholder
cds::urcu::details::thread_data< cds::urcu::general_instant_tag > * m_pGPIRCU;
//@endcond
cds::gc::HP::thread_gc_impl * m_hpManager ; ///< Michael's Hazard Pointer GC thread-specific data
- cds::gc::HRC::thread_gc_impl * m_hrcManager ; ///< Gidenstam's GC thread-specific data
cds::gc::PTB::thread_gc_impl * m_ptbManager ; ///< Pass The Buck GC thread-specific data
size_t m_nFakeProcessorNumber ; ///< fake "current processor" number
else
m_hpManager = nullptr;
- if ( cds::gc::HRC::isUsed() )
- m_hrcManager = new (m_hrcManagerPlaceholder) cds::gc::HRC::thread_gc_impl;
- else
- m_hrcManager = nullptr;
-
if ( cds::gc::PTB::isUsed() )
m_ptbManager = new (m_ptbManagerPlaceholder) cds::gc::PTB::thread_gc_impl;
else
m_hpManager = nullptr;
}
- if ( m_hrcManager ) {
- typedef cds::gc::HRC::thread_gc_impl hrc_thread_gc_impl;
- m_hrcManager->~hrc_thread_gc_impl();
- m_hrcManager = nullptr;
- }
-
if ( m_ptbManager ) {
typedef cds::gc::PTB::thread_gc_impl ptb_thread_gc_impl;
m_ptbManager->~ptb_thread_gc_impl();
if ( m_nAttachCount++ == 0 ) {
if ( cds::gc::HP::isUsed() )
m_hpManager->init();
- if ( cds::gc::HRC::isUsed() )
- m_hrcManager->init();
if ( cds::gc::PTB::isUsed() )
m_ptbManager->init();
if ( --m_nAttachCount == 0 ) {
if ( cds::gc::PTB::isUsed() )
m_ptbManager->fini();
- if ( cds::gc::HRC::isUsed() )
- m_hrcManager->fini();
if ( cds::gc::HP::isUsed() )
m_hpManager->fini();
return *(_threadData()->m_hpManager);
}
- /// Get gc::HRC thread GC implementation for current thread
- /**
- The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::HRC.
- To initialize gc::HRC GC you must constuct cds::gc::HRC object in the beginning of your application
- */
- static gc::HRC::thread_gc_impl& getHRCGC()
- {
- assert( _threadData()->m_hrcManager != nullptr );
- return *(_threadData()->m_hrcManager);
- }
-
/// Get gc::PTB thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
return *(_threadData()->m_hpManager);
}
- /// Get gc::HRC thread GC implementation for current thread
- /**
- The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::HRC.
- To initialize gc::HRC GC you must constuct cds::gc::HRC object in the beginning of your application
- */
- static gc::HRC::thread_gc_impl& getHRCGC()
- {
- assert( _threadData()->m_hrcManager );
- return *(_threadData()->m_hrcManager);
- }
-
/// Get gc::PTB thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
return *(_threadData()->m_hpManager);
}
- /// Get gc::HRC thread GC implementation for current thread
- /**
- The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::HRC.
- To initialize gc::HRC GC you must constuct cds::gc::HRC object in the beginning of your application
- */
- static gc::HRC::thread_gc_impl& getHRCGC()
- {
- assert( _threadData()->m_hrcManager );
- return *(_threadData()->m_hrcManager);
- }
-
/// Get gc::PTB thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
return *(_threadData( do_getData )->m_hpManager);
}
- /// Get gc::HRC thread GC implementation for current thread
- /**
- The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::HRC.
- To initialize gc::HRC GC you must constuct cds::gc::HRC object in the beginning of your application
- */
- static gc::HRC::thread_gc_impl& getHRCGC()
- {
- return *(_threadData( do_getData )->m_hrcManager);
- }
-
/// Get gc::PTB thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
return *(_threadData( do_getData )->m_hpManager);
}
- /// Get gc::HRC thread GC implementation for current thread
- /**
- The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::HRC.
- To initialize gc::HRC GC you must constuct cds::gc::HRC object in the beginning of your application
- */
- static gc::HRC::thread_gc_impl& getHRCGC()
- {
- return *(_threadData( do_getData )->m_hrcManager);
- }
-
/// Get gc::PTB thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
return Manager::getHZPGC();
}
- /// Get cds::gc::HRC thread GC implementation for current thread
- /**
- The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use cds::gc::HRC.
- To initialize cds::gc::HRC GC you must constuct cds::gc::HRC object in the beginning of your application,
- see \ref cds_how_to_use "How to use libcds"
- */
- template <>
- inline cds::gc::HRC::thread_gc_impl& getGC<cds::gc::HRC>()
- {
- return Manager::getHRCGC();
- }
-
/// Get cds::gc::PTB thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
</ItemDefinitionGroup>\r
<ItemGroup>\r
<ClCompile Include="..\..\..\src\dllmain.cpp" />\r
- <ClCompile Include="..\..\..\src\hrc_gc.cpp" />\r
<ClCompile Include="..\..\..\src\hzp_gc.cpp" />\r
<ClCompile Include="..\..\..\src\init.cpp" />\r
<ClCompile Include="..\..\..\src\michael_heap.cpp" />\r
<ClInclude Include="..\..\..\cds\gc\guarded_ptr.h" />\r
<ClInclude Include="..\..\..\cds\gc\hp_decl.h" />\r
<ClInclude Include="..\..\..\cds\gc\hp_impl.h" />\r
- <ClInclude Include="..\..\..\cds\gc\hrc_decl.h" />\r
- <ClInclude Include="..\..\..\cds\gc\hrc_impl.h" />\r
<ClInclude Include="..\..\..\cds\gc\ptb_decl.h" />\r
<ClInclude Include="..\..\..\cds\gc\ptb_impl.h" />\r
<ClInclude Include="..\..\..\cds\intrusive\basket_queue.h" />\r
<ClInclude Include="..\..\..\cds\details\type_padding.h" />\r
<ClInclude Include="..\..\..\cds\gc\default_gc.h" />\r
<ClInclude Include="..\..\..\cds\gc\hp.h" />\r
- <ClInclude Include="..\..\..\cds\gc\hrc.h" />\r
<ClInclude Include="..\..\..\cds\gc\nogc.h" />\r
<ClInclude Include="..\..\..\cds\gc\ptb.h" />\r
<ClInclude Include="..\..\..\cds\gc\hzp\details\hp_alloc.h" />\r
<ClInclude Include="..\..\..\cds\gc\hzp\details\hp_retired.h" />\r
<ClInclude Include="..\..\..\cds\gc\hzp\details\hp_type.h" />\r
<ClInclude Include="..\..\..\cds\gc\hzp\hzp.h" />\r
- <ClInclude Include="..\..\..\cds\gc\hrc\gc_fwd.h" />\r
- <ClInclude Include="..\..\..\cds\gc\hrc\hrc.h" />\r
- <ClInclude Include="..\..\..\cds\gc\hrc\details\hrc_fwd.h" />\r
- <ClInclude Include="..\..\..\cds\gc\hrc\details\hrc_inline.h" />\r
- <ClInclude Include="..\..\..\cds\gc\hrc\details\hrc_retired.h" />\r
<ClInclude Include="..\..\..\cds\gc\ptb\ptb.h" />\r
<ClInclude Include="..\..\..\cds\gc\details\retired_ptr.h" />\r
<ClInclude Include="..\..\..\cds\user_setup\allocator.h" />\r
<Filter Include="Header Files\cds\gc\hzp">\r
<UniqueIdentifier>{21a6c665-7381-45b8-9f03-b21f3da5503d}</UniqueIdentifier>\r
</Filter>\r
- <Filter Include="Header Files\cds\gc\hrc">\r
- <UniqueIdentifier>{695568b2-b136-4b80-bd18-6e3e13c22301}</UniqueIdentifier>\r
- </Filter>\r
<Filter Include="Header Files\cds\gc\ptb">\r
<UniqueIdentifier>{53d28ee4-5fe9-4fa1-a617-53d8b0628eac}</UniqueIdentifier>\r
</Filter>\r
<ClCompile Include="..\..\..\src\dllmain.cpp">\r
<Filter>Source Files</Filter>\r
</ClCompile>\r
- <ClCompile Include="..\..\..\src\hrc_gc.cpp">\r
- <Filter>Source Files</Filter>\r
- </ClCompile>\r
<ClCompile Include="..\..\..\src\hzp_gc.cpp">\r
<Filter>Source Files</Filter>\r
</ClCompile>\r
<ClInclude Include="..\..\..\cds\gc\hp.h">\r
<Filter>Header Files\cds\gc</Filter>\r
</ClInclude>\r
- <ClInclude Include="..\..\..\cds\gc\hrc.h">\r
- <Filter>Header Files\cds\gc</Filter>\r
- </ClInclude>\r
<ClInclude Include="..\..\..\cds\gc\nogc.h">\r
<Filter>Header Files\cds\gc</Filter>\r
</ClInclude>\r
<ClInclude Include="..\..\..\cds\gc\hzp\hzp.h">\r
<Filter>Header Files\cds\gc\hzp</Filter>\r
</ClInclude>\r
- <ClInclude Include="..\..\..\cds\gc\hrc\gc_fwd.h">\r
- <Filter>Header Files\cds\gc\hrc</Filter>\r
- </ClInclude>\r
- <ClInclude Include="..\..\..\cds\gc\hrc\hrc.h">\r
- <Filter>Header Files\cds\gc\hrc</Filter>\r
- </ClInclude>\r
- <ClInclude Include="..\..\..\cds\gc\hrc\details\hrc_fwd.h">\r
- <Filter>Header Files\cds\gc\hrc</Filter>\r
- </ClInclude>\r
- <ClInclude Include="..\..\..\cds\gc\hrc\details\hrc_inline.h">\r
- <Filter>Header Files\cds\gc\hrc</Filter>\r
- </ClInclude>\r
- <ClInclude Include="..\..\..\cds\gc\hrc\details\hrc_retired.h">\r
- <Filter>Header Files\cds\gc\hrc</Filter>\r
- </ClInclude>\r
<ClInclude Include="..\..\..\cds\gc\ptb\ptb.h">\r
<Filter>Header Files\cds\gc\ptb</Filter>\r
</ClInclude>\r
<ClInclude Include="..\..\..\cds\gc\hp_impl.h">\r
<Filter>Header Files\cds\gc</Filter>\r
</ClInclude>\r
- <ClInclude Include="..\..\..\cds\gc\hrc_decl.h">\r
- <Filter>Header Files\cds\gc</Filter>\r
- </ClInclude>\r
- <ClInclude Include="..\..\..\cds\gc\hrc_impl.h">\r
- <Filter>Header Files\cds\gc</Filter>\r
- </ClInclude>\r
<ClInclude Include="..\..\..\cds\gc\ptb_decl.h">\r
<Filter>Header Files\cds\gc</Filter>\r
</ClInclude>\r
CDS_SOURCES=src/hzp_gc.cpp \\r
src/init.cpp \\r
- src/hrc_gc.cpp \\r
src/ptb_gc.cpp \\r
src/urcu_gp.cpp \\r
src/urcu_sh.cpp \\r
+++ /dev/null
-//$$CDS-header$$
-
-/*
- File: hrc_gc.cpp
-
- Implementation of cds::gc::hrc::HRCGarbageCollector
-
- Editions:
- 2008.03.10 Maxim.Khiszinsky Created
-*/
-
-#include <cds/gc/hrc/hrc.h>
-
-#include "hzp_const.h"
-#include <vector>
-#include <algorithm> // std::sort
-
-#define CDS_HRC_STATISTIC( _x ) if ( m_bStatEnabled ) { _x; }
-
-namespace cds { namespace gc {
- namespace hrc {
-
- GarbageCollector * GarbageCollector::m_pGC = nullptr;
-
- GarbageCollector::GarbageCollector(
- size_t nHazardPtrCount,
- size_t nMaxThreadCount,
- size_t nRetiredNodeArraySize
- )
- : m_pListHead( nullptr ),
- m_bStatEnabled( true ),
- m_nHazardPointerCount( nHazardPtrCount ),
- m_nMaxThreadCount( nMaxThreadCount ),
- m_nMaxRetiredPtrCount( nRetiredNodeArraySize )
- {}
-
- GarbageCollector::~GarbageCollector()
- {
- thread_list_node * pNode = m_pListHead.load( atomics::memory_order_relaxed );
- while ( pNode ) {
- assert( pNode->m_idOwner.load( atomics::memory_order_relaxed ) == cds::OS::c_NullThreadId );
- clearHRCThreadDesc( pNode );
- thread_list_node * pNext = pNode->m_pNext;
- deleteHRCThreadDesc( pNode );
- pNode = pNext;
- }
- }
-
- void CDS_STDCALL GarbageCollector::Construct(
- size_t nHazardPtrCount, // hazard pointers count
- size_t nMaxThreadCount, // max thread count
- size_t nMaxNodeLinkCount, // max HRC-pointer count in the HRC-container's item
- size_t nMaxTransientLinks // max HRC-container's item count that can point to deleting item of container
- )
- {
- if ( !m_pGC ) {
- if ( nHazardPtrCount == 0 )
- nHazardPtrCount = c_nHazardPointerPerThread + c_nCleanUpHazardPointerPerThread;
- if ( nMaxThreadCount == 0 )
- nMaxThreadCount = c_nMaxThreadCount;
- if ( nMaxNodeLinkCount == 0 )
- nMaxNodeLinkCount = c_nHRCMaxNodeLinkCount;
- if ( nMaxTransientLinks == 0 )
- nMaxTransientLinks = c_nHRCMaxTransientLinks;
-
- size_t nRetiredNodeArraySize = nMaxThreadCount * ( nHazardPtrCount + nMaxNodeLinkCount + nMaxTransientLinks + 1 );
-
- m_pGC = new GarbageCollector( nHazardPtrCount, nMaxThreadCount, nRetiredNodeArraySize );
- }
- }
-
- void CDS_STDCALL GarbageCollector::Destruct()
- {
- if ( m_pGC ) {
- {
- ThreadGC tgc;
- tgc.init();
- m_pGC->HelpScan( &tgc );
- m_pGC->Scan( &tgc );
- // tgc dtor calls fini()
- }
-
- delete m_pGC;
- m_pGC = nullptr;
- }
- }
-
- inline GarbageCollector::thread_list_node * GarbageCollector::newHRCThreadDesc()
- {
- CDS_HRC_STATISTIC( ++m_Stat.m_AllocNewHRCThreadDesc );
- return new thread_list_node( *this );
- }
-
- inline void GarbageCollector::deleteHRCThreadDesc( thread_list_node * pNode )
- {
- assert( pNode->m_hzp.size() == pNode->m_hzp.capacity() );
- CDS_HRC_STATISTIC( ++m_Stat.m_DeleteHRCThreadDesc );
- delete pNode;
- }
-
- void GarbageCollector::clearHRCThreadDesc( thread_list_node * pNode )
- {
- assert( pNode->m_hzp.size() == pNode->m_hzp.capacity() );
- ContainerNode * pItem;
- for ( size_t n = 0; n < pNode->m_arrRetired.capacity(); ++n ) {
- if ( (pItem = pNode->m_arrRetired[n].m_pNode.load( atomics::memory_order_relaxed )) != nullptr ) {
- pNode->m_arrRetired[n].m_funcFree( pItem );
- //pItem->destroy();
- pNode->m_arrRetired[n].m_pNode.store( nullptr, atomics::memory_order_relaxed );
- }
- }
- assert( pNode->m_hzp.size() == pNode->m_hzp.capacity() );
- }
-
- GarbageCollector::thread_list_node * GarbageCollector::getHRCThreadDescForCurrentThread() const
- {
- thread_list_node * hprec;
- const cds::OS::ThreadId curThreadId = cds::OS::getCurrentThreadId();
-
- for ( hprec = m_pListHead.load( atomics::memory_order_acquire ); hprec; hprec = hprec->m_pNext ) {
- if ( hprec->m_idOwner.load( atomics::memory_order_acquire ) == curThreadId ) {
- assert( !hprec->m_bFree );
- return hprec;
- }
- }
- return nullptr;
- }
-
- details::thread_descriptor * GarbageCollector::allocateHRCThreadDesc( ThreadGC * pThreadGC )
- {
- CDS_HRC_STATISTIC( ++m_Stat.m_AllocHRCThreadDesc );
-
- thread_list_node * hprec;
- const cds::OS::ThreadId nullThreadId = cds::OS::c_NullThreadId;
- const cds::OS::ThreadId curThreadId = cds::OS::getCurrentThreadId();
-
- // First try to reuse a retired (non-active) HP record
- for ( hprec = m_pListHead.load( atomics::memory_order_acquire ); hprec; hprec = hprec->m_pNext ) {
- cds::OS::ThreadId expectedThreadId = nullThreadId;
- if ( !hprec->m_idOwner.compare_exchange_strong( expectedThreadId, curThreadId, atomics::memory_order_acq_rel, atomics::memory_order_relaxed ) )
- continue;
- hprec->m_pOwner = pThreadGC;
- hprec->m_bFree = false;
- assert( hprec->m_hzp.size() == hprec->m_hzp.capacity() );
- return hprec;
- }
-
- // No HP records available for reuse
- // Allocate and push a new HP record
- hprec = newHRCThreadDesc();
- assert( hprec->m_hzp.size() == hprec->m_hzp.capacity() );
- hprec->m_idOwner.store( curThreadId, atomics::memory_order_relaxed );
- hprec->m_pOwner = pThreadGC;
- hprec->m_bFree = false;
- thread_list_node * pOldHead;
-
- pOldHead = m_pListHead.load( atomics::memory_order_relaxed );
- do {
- hprec->m_pNext = pOldHead;
- } while ( !m_pListHead.compare_exchange_weak( pOldHead, hprec, atomics::memory_order_release, atomics::memory_order_relaxed ));
-
- assert( hprec->m_hzp.size() == hprec->m_hzp.capacity() );
- return hprec;
- }
-
- void GarbageCollector::retireHRCThreadDesc( details::thread_descriptor * pRec )
- {
- CDS_HRC_STATISTIC( ++m_Stat.m_RetireHRCThreadDesc );
-
- pRec->clear();
- thread_list_node * pNode = static_cast<thread_list_node *>( pRec );
- assert( pNode->m_hzp.size() == pNode->m_hzp.capacity() );
- /*
- It is possible that
- pNode->m_idOwner.value() != cds::OS::getCurrentThreadId()
- if the destruction of thread object is called by the destructor
- after thread termination
- */
- assert( pNode->m_idOwner.load( atomics::memory_order_relaxed ) != cds::OS::c_NullThreadId );
- pNode->m_pOwner = nullptr;
- pNode->m_idOwner.store( cds::OS::c_NullThreadId, atomics::memory_order_release );
- assert( pNode->m_hzp.size() == pNode->m_hzp.capacity() );
- }
-
- void GarbageCollector::Scan( ThreadGC * pThreadGC )
- {
- CDS_HRC_STATISTIC( ++m_Stat.m_ScanCalls );
-
- typedef std::vector< ContainerNode * > hazard_ptr_list;
-
- details::thread_descriptor * pRec = pThreadGC->m_pDesc;
- assert( static_cast< thread_list_node *>( pRec )->m_idOwner.load(atomics::memory_order_relaxed) == cds::OS::getCurrentThreadId() );
-
- // Step 1: mark all pRec->m_arrRetired items as "traced"
- {
- details::retired_vector::const_iterator itEnd = pRec->m_arrRetired.end();
-
- for ( details::retired_vector::const_iterator it = pRec->m_arrRetired.begin() ; it != itEnd; ++it ) {
- ContainerNode * pNode = it->m_pNode.load( atomics::memory_order_acquire );
- if ( pNode ) {
- if ( pNode->m_RC.value() == 0 ) {
- pNode->m_bTrace.store( true, atomics::memory_order_release );
- if ( pNode->m_RC.value() != 0 )
- pNode->m_bTrace.store( false, atomics::memory_order_release );
- }
- }
- }
- }
-
- // Array of hazard pointers for all threads
- hazard_ptr_list plist;
- plist.reserve( m_nMaxThreadCount * m_nHazardPointerCount );
- assert( plist.size() == 0 );
-
- // Stage 2: Scan HP list and insert non-null values to plist
- {
- thread_list_node * pNode = m_pListHead.load( atomics::memory_order_acquire );
-
- while ( pNode ) {
- for ( size_t i = 0; i < m_nHazardPointerCount; ++i ) {
- ContainerNode * hptr = pNode->m_hzp[i];
- if ( hptr )
- plist.push_back( hptr );
- }
- pNode = pNode->m_pNext;
- }
- }
-
- // Sort plist to simplify search in
- std::sort( plist.begin(), plist.end() );
-
- // Stage 3: Deletes all nodes for refCount == 0 and that do not declare as Hazard in other thread
- {
- details::retired_vector& arr = pRec->m_arrRetired;
-
- hazard_ptr_list::iterator itHPBegin = plist.begin();
- hazard_ptr_list::iterator itHPEnd = plist.end();
-
- details::retired_vector::iterator itEnd = arr.end();
- details::retired_vector::iterator it = arr.begin();
-
- for ( size_t nRetired = 0; it != itEnd; ++nRetired, ++it ) {
- details::retired_node& node = *it;
- ContainerNode * pNode = node.m_pNode.load(atomics::memory_order_acquire);
- if ( !pNode )
- continue;
-
- if ( pNode->m_RC.value() == 0 && pNode->m_bTrace.load(atomics::memory_order_acquire) && !std::binary_search( itHPBegin, itHPEnd, pNode ) ) {
- // pNode may be destructed safely
-
- node.m_bDone.store( true, atomics::memory_order_release );
- if ( node.m_nClaim.load( atomics::memory_order_acquire ) == 0 ) {
- pNode->terminate( pThreadGC, false );
- pNode->clean( atomics::memory_order_relaxed );
- node.m_funcFree( pNode );
-
- arr.pop( nRetired );
- CDS_HRC_STATISTIC( ++m_Stat.m_DeletedNode );
- continue;
- }
-
- pNode->terminate( pThreadGC, true );
- //node.m_bDone.store( true, atomics::memory_order_release );
- CDS_HRC_STATISTIC( ++m_Stat.m_ScanClaimGuarded );
- }
- else {
- CDS_HRC_STATISTIC( ++m_Stat.m_ScanGuarded );
- }
- }
- }
- }
-
- void GarbageCollector::HelpScan( ThreadGC * pThis )
- {
- if ( pThis->m_pDesc->m_arrRetired.isFull() )
- return;
-
- CDS_HRC_STATISTIC( ++m_Stat.m_HelpScanCalls );
-
- const cds::OS::ThreadId nullThreadId = cds::OS::c_NullThreadId;
- const cds::OS::ThreadId curThreadId = cds::OS::getCurrentThreadId();
-
- for ( thread_list_node * pRec = m_pListHead.load(atomics::memory_order_acquire); pRec; pRec = pRec->m_pNext )
- {
- // If threadDesc is free then own its
- cds::OS::ThreadId expectedThreadId = nullThreadId;
- if ( !pRec->m_idOwner.compare_exchange_strong(expectedThreadId, curThreadId, atomics::memory_order_acquire, atomics::memory_order_relaxed) )
- {
- continue;
- }
-
- // We own threadDesc.
- assert( pRec->m_pOwner == nullptr );
-
- if ( !pRec->m_bFree ) {
- // All undeleted pointers is moved to pThis (it is private for the current thread)
-
- details::retired_vector& src = pRec->m_arrRetired;
- details::retired_vector& dest = pThis->m_pDesc->m_arrRetired;
- assert( !dest.isFull());
-
- details::retired_vector::iterator itEnd = src.end();
- details::retired_vector::iterator it = src.begin();
-
- for ( size_t nRetired = 0; it != itEnd; ++nRetired, ++it ) {
- if ( it->m_pNode.load( atomics::memory_order_relaxed ) == nullptr )
- continue;
-
- dest.push( it->m_pNode.load(atomics::memory_order_relaxed), it->m_funcFree );
- src.pop( nRetired );
-
- while ( dest.isFull() ) {
- pThis->cleanUpLocal();
- if ( dest.isFull() )
- Scan( pThis );
- if ( dest.isFull() )
- CleanUpAll( pThis );
- else
- break;
- }
- }
- pRec->m_bFree = true;
- }
- pRec->m_idOwner.store( nullThreadId, atomics::memory_order_release );
- }
- }
-
- void GarbageCollector::CleanUpAll( ThreadGC * pThis )
- {
- CDS_HRC_STATISTIC( ++m_Stat.m_CleanUpAllCalls );
-
- //const cds::OS::ThreadId nullThreadId = cds::OS::c_NullThreadId;
- thread_list_node * pThread = m_pListHead.load(atomics::memory_order_acquire);
- while ( pThread ) {
- for ( size_t i = 0; i < pThread->m_arrRetired.capacity(); ++i ) {
- details::retired_node& rRetiredNode = pThread->m_arrRetired[i];
- ContainerNode * pNode = rRetiredNode.m_pNode.load(atomics::memory_order_acquire);
- if ( pNode && !rRetiredNode.m_bDone.load(atomics::memory_order_acquire) ) {
- rRetiredNode.m_nClaim.fetch_add( 1, atomics::memory_order_release );
- if ( !rRetiredNode.m_bDone.load(atomics::memory_order_acquire)
- && pNode == rRetiredNode.m_pNode.load(atomics::memory_order_acquire) )
- {
- pNode->cleanUp( pThis );
- }
- rRetiredNode.m_nClaim.fetch_sub( 1, atomics::memory_order_release );
- }
- }
- pThread = pThread->m_pNext;
- }
- }
-
- GarbageCollector::internal_state& GarbageCollector::getInternalState( GarbageCollector::internal_state& stat) const
- {
- // Const
- stat.nHPCount = m_nHazardPointerCount;
- stat.nMaxThreadCount = m_nMaxThreadCount;
- stat.nMaxRetiredPtrCount = m_nMaxRetiredPtrCount;
- stat.nHRCRecSize = sizeof( thread_list_node )
- + sizeof( details::retired_node) * m_nMaxRetiredPtrCount;
- stat.nHRCRecAllocated =
- stat.nHRCRecUsed =
- stat.nTotalRetiredPtrCount =
- stat.nRetiredPtrInFreeHRCRecs = 0;
-
- // Walk through HRC records
- for ( thread_list_node *hprec = m_pListHead.load(atomics::memory_order_acquire); hprec; hprec = hprec->m_pNext ) {
- ++stat.nHRCRecAllocated;
- size_t nRetiredNodeCount = hprec->m_arrRetired.retiredNodeCount();
- if ( hprec->m_bFree ) {
- stat.nRetiredPtrInFreeHRCRecs += nRetiredNodeCount;
- }
- else {
- ++stat.nHRCRecUsed;
- }
- stat.nTotalRetiredPtrCount += nRetiredNodeCount;
- }
-
- // Events
- stat.evcAllocHRCRec = m_Stat.m_AllocHRCThreadDesc;
- stat.evcRetireHRCRec = m_Stat.m_RetireHRCThreadDesc;
- stat.evcAllocNewHRCRec = m_Stat.m_AllocNewHRCThreadDesc;
- stat.evcDeleteHRCRec = m_Stat.m_DeleteHRCThreadDesc;
- stat.evcScanCall = m_Stat.m_ScanCalls;
- stat.evcHelpScanCalls = m_Stat.m_HelpScanCalls;
- stat.evcCleanUpAllCalls = m_Stat.m_CleanUpAllCalls;
- stat.evcDeletedNode = m_Stat.m_DeletedNode;
- stat.evcScanGuarded = m_Stat.m_ScanGuarded;
- stat.evcScanClaimGuarded = m_Stat.m_ScanClaimGuarded;
-
-# ifdef CDS_DEBUG
- stat.evcNodeConstruct = m_Stat.m_NodeConstructed;
- stat.evcNodeDestruct = m_Stat.m_NodeDestructed;
-# endif
-
- return stat;
- }
-
- void ContainerNode::cleanUp( ThreadGC * /*pGC*/ )
- {
- CDS_PURE_VIRTUAL_FUNCTION_CALLED_("cds::gc::hrc::ContainerNode::cleanUp");
- }
- void ContainerNode::terminate( ThreadGC * /*pGC*/, bool /*bConcurrent*/ )
- {
- CDS_PURE_VIRTUAL_FUNCTION_CALLED_("cds::gc::hrc::ContainerNode::terminate");
- }
-
- } // namespace hrc
-}} // namespace cds::gc
static const size_t c_nHazardPointerPerThread = 8;
} // namespace hzp
- //---------------------------------------------------------------
- // HRC (Gidenstam) reclamation schema constants
- namespace hrc {
- using cds::gc::hzp::c_nMaxThreadCount;
- using cds::gc::hzp::c_nHazardPointerPerThread;
-
- /// Number of Hazard Pointers per thread for Node::CleanUp methods
- static const size_t c_nCleanUpHazardPointerPerThread = 2;
-
- /// Max number of links for HRC node
- static const size_t c_nHRCMaxNodeLinkCount = 4;
-
- /// Max number of links in live node that may transiently point to a deleted node
- static const size_t c_nHRCMaxTransientLinks = c_nHRCMaxNodeLinkCount;
- } // namespace hrc
} /* namespace gc */ } /* namespace cds */
#endif // #ifndef __CDSIMPL_HZP_CONST_H
#include <cds/init.h>
#include <cds/gc/hp.h>
-#include <cds/gc/hrc.h>
#include <cds/gc/ptb.h>
#include <cds/urcu/general_instant.h>
#include <cds/urcu/general_buffered.h>
return s;
}
-std::ostream& operator << (std::ostream& s, const cds::gc::hrc::GarbageCollector::internal_state& stat)
-{
- s << "\nHRC GC internal state:"
- << "\n\t\tHRC record allocated=" << stat.nHRCRecAllocated
- << "\n\t\tHRC records used=" << stat.nHRCRecUsed
- << "\n\t\tTotal retired ptr count=" << stat.nTotalRetiredPtrCount
- << "\n\t\tRetired ptr in free HRC records=" << stat.nRetiredPtrInFreeHRCRecs
- << "\n\tEvents:"
- << "\n\t\tHRCrec allocations=" << stat.evcAllocHRCRec
- << "\n\t\tHRCrec retire events=" << stat.evcRetireHRCRec
- << "\n\t\tnew HRCrec allocations from heap=" << stat.evcAllocNewHRCRec
- << "\n\t\tHRCrec deletions=" << stat.evcDeleteHRCRec
- << "\n\t\tScan calling=" << stat.evcScanCall
- << "\n\t\tHelpScan calling=" << stat.evcHelpScanCalls
- << "\n\t\tCleanUpAll calling=" << stat.evcCleanUpAllCalls
- << "\n\t\tretired objects deleting=" << stat.evcDeletedNode
- << "\n\t\tguarded nodes on Scan=" << stat.evcScanGuarded
- << "\n\t\tclaimed node on Scan=" << stat.evcScanClaimGuarded
-#ifdef _DEBUG
- << "\n\t\tnode constructed count=" << stat.evcNodeConstruct
- << "\n\t\tnode destructed count=" << stat.evcNodeDestruct
-#endif
- << std::endl;
-
- return s;
-}
-
namespace CppUnitMini
{
int TestCase::m_numErrors = 0;
cds::gc::hzp::GarbageCollector::InternalState stat;
std::cout << cds::gc::hzp::GarbageCollector::instance().getInternalState( stat ) << std::endl;
}
-
- {
- cds::gc::hrc::GarbageCollector::internal_state stat;
- std::cout << cds::gc::hrc::GarbageCollector::instance().getInternalState( stat ) << std::endl;
- }
}
}
// Safe reclamation schemes
cds::gc::HP hzpGC( nHazardPtrCount );
- cds::gc::HRC hrcGC( nHazardPtrCount );
cds::gc::PTB ptbGC;
// RCU varieties
[General]\r
# HZP scan strategy, possible values are "classic", "inplace". Default is "classic"\r
HZP_scan_strategy=inplace\r
-# Hazard pointer count per thread, for gc::HP and gc::HRC\r
+# Hazard pointer count per thread, for gc::HP\r
hazard_pointer_count=72\r
\r
[Atomic_ST]\r
TEST_CASE( Treiber_HP_pause, cds::intrusive::treiber_stack::node< cds::gc::HP > ) \
TEST_CASE( Treiber_HP_exp, cds::intrusive::treiber_stack::node< cds::gc::HP > ) \
TEST_CASE( Treiber_HP_stat, cds::intrusive::treiber_stack::node< cds::gc::HP > ) \
- /*TEST_CASE( Treiber_HRC_yield, cds::intrusive::treiber_stack::node< cds::gc::HRC > )*/ \
TEST_CASE( Treiber_DHP, cds::intrusive::treiber_stack::node< cds::gc::DHP > ) \
/*TEST_CASE( Treiber_DHP_yield, cds::intrusive::treiber_stack::node< cds::gc::DHP > )*/ \
TEST_CASE( Treiber_DHP_pause, cds::intrusive::treiber_stack::node< cds::gc::DHP > ) \
projects / libcds.git / commitdiff