From: khizmax Date: Mon, 10 Nov 2014 09:55:31 +0000 (+0300) Subject: cds::gc::HRC has been removed X-Git-Tag: v2.0.0~122 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=e4c3bdf5ffc8ee1b49c79bd1f3ad462f58e8ab53 cds::gc::HRC has been removed --- diff --git a/cds/container/impl/michael_kvlist.h b/cds/container/impl/michael_kvlist.h index c6d94c87..8c0a5f53 100644 --- a/cds/container/impl/michael_kvlist.h +++ b/cds/container/impl/michael_kvlist.h @@ -246,7 +246,7 @@ namespace cds { namespace container { 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 diff --git a/cds/container/impl/michael_list.h b/cds/container/impl/michael_list.h index 16e306a2..c47bfeb4 100644 --- a/cds/container/impl/michael_list.h +++ b/cds/container/impl/michael_list.h @@ -234,7 +234,7 @@ namespace cds { namespace container { 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 diff --git a/cds/container/optimistic_queue.h b/cds/container/optimistic_queue.h index 6f34bba5..bd304a34 100644 --- a/cds/container/optimistic_queue.h +++ b/cds/container/optimistic_queue.h @@ -140,7 +140,7 @@ namespace cds { namespace container { - [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 not 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: diff --git a/cds/details/defs.h b/cds/details/defs.h index ff482c17..943129e9 100644 --- a/cds/details/defs.h +++ b/cds/details/defs.h @@ -42,9 +42,7 @@ 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. @@ -118,7 +116,6 @@ 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 diff --git a/cds/gc/all.h b/cds/gc/all.h index f5a79732..7e4e9256 100644 --- a/cds/gc/all.h +++ b/cds/gc/all.h @@ -4,7 +4,6 @@ #define __CDS_GC_ALL_H #include -#include #include #endif // #ifndef __CDS_GC_ALL_H diff --git a/cds/gc/gc_fwd.h b/cds/gc/gc_fwd.h index 7a6d5b1a..365569f3 100644 --- a/cds/gc/gc_fwd.h +++ b/cds/gc/gc_fwd.h @@ -8,7 +8,6 @@ //@cond namespace cds { namespace gc { class HP; - class HRC; class PTB; class nogc; diff --git a/cds/gc/hp_decl.h b/cds/gc/hp_decl.h index 3b274db6..800b7c39 100644 --- a/cds/gc/hp_decl.h +++ b/cds/gc/hp_decl.h @@ -473,20 +473,12 @@ namespace cds { namespace gc { 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 ) diff --git a/cds/gc/hrc.h b/cds/gc/hrc.h deleted file mode 100644 index 344ef31f..00000000 --- a/cds/gc/hrc.h +++ /dev/null @@ -1,10 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HRC_H -#define __CDS_GC_HRC_H - -#include -#include -#include - -#endif // #ifndef __CDS_GC_HRC_H diff --git a/cds/gc/hrc/details/hrc_fwd.h b/cds/gc/hrc/details/hrc_fwd.h deleted file mode 100644 index 7d44e77d..00000000 --- a/cds/gc/hrc/details/hrc_fwd.h +++ /dev/null @@ -1,16 +0,0 @@ -//$$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 diff --git a/cds/gc/hrc/details/hrc_inline.h b/cds/gc/hrc/details/hrc_inline.h deleted file mode 100644 index 32df5258..00000000 --- a/cds/gc/hrc/details/hrc_inline.h +++ /dev/null @@ -1,64 +0,0 @@ -//$$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 diff --git a/cds/gc/hrc/details/hrc_retired.h b/cds/gc/hrc/details/hrc_retired.h deleted file mode 100644 index 90a3df6b..00000000 --- a/cds/gc/hrc/details/hrc_retired.h +++ /dev/null @@ -1,193 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HRC_SCHEMA_RETIRED_H -#define __CDS_GC_HRC_SCHEMA_RETIRED_H - -#include -#include -#include -#include - -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 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 m_nClaim ; ///< Access to reclaimed node - atomics::atomic 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 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 diff --git a/cds/gc/hrc/gc_fwd.h b/cds/gc/hrc/gc_fwd.h deleted file mode 100644 index 09170552..00000000 --- a/cds/gc/hrc/gc_fwd.h +++ /dev/null @@ -1,15 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HRC_SCHEMA_GC_FWD_H -#define __CDS_GC_HRC_SCHEMA_GC_FWD_H - -#include - -//@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 diff --git a/cds/gc/hrc/hrc.h b/cds/gc/hrc/hrc.h deleted file mode 100644 index 4ba20e74..00000000 --- a/cds/gc/hrc/hrc.h +++ /dev/null @@ -1,685 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HRC_HRC_H -#define __CDS_GC_HRC_HRC_H - -/* - Editions: - 2008.03.08 Maxim.Khiszinsky Created -*/ - -#include -#include -#include - -#include -#include - -#include - -#if CDS_COMPILER == CDS_COMPILER_MSVC -# pragma warning(push) -// warning C4251: 'cds::gc::hzp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomic::atomic' -// 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 – 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 main(). - 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 m_bTrace ; ///< \p true - node is tracing by Scan - atomics::atomic 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 HPGuard; - - /// Array of hazard pointers. - /** - This is wrapper for cds::gc::hzp::details::HPArray class - */ - template using HPArray = gc::hzp::details::HPArrayT; - - /// 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 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 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 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 - void allocGuard( details::HPArray& arr ) - { - assert( m_pDesc != nullptr ); - m_pDesc->m_hzp.alloc( arr ); - } - - /// Frees HP guard array \p arr - template - void freeGuard( details::HPArray& 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 - 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 - 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 - class AutoHPArray: public details::HPArray - { - 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 - -#if CDS_COMPILER == CDS_COMPILER_MSVC -# pragma warning(pop) -#endif - -#endif // #ifndef __CDS_GC_HRC_HRC_H diff --git a/cds/gc/hrc_decl.h b/cds/gc/hrc_decl.h deleted file mode 100644 index ecf5e915..00000000 --- a/cds/gc/hrc_decl.h +++ /dev/null @@ -1,834 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HRC_DECL_H -#define __CDS_GC_HRC_DECL_H - -#include -#include - -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 – 242, Springer-Verlag, 2005 - - Note that HRC schema does not support cyclic references that significantly limits the applicability of this GC. - -

Usage

- In your \p main function you declare a object of class cds::gc::HRC. This declaration - initializes internal hrc::GarbageCollector singleton. - \code - #include // for cds::Initialize and cds::Terminate - #include - - 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 - - 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 - - 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 - class atomic_ref: protected atomics::atomic - { - //@cond - typedef atomics::atomic 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 - 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 - T * protect( atomic_ref 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 - /** - 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 f( toGuard.load() ) is assigned to the hazard pointer. - */ - template - T * protect( atomic_ref 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 atomic_marked_ptr::marked_ptr protect( atomic_marked_ptr const& link ) - { - typename atomic_marked_ptr::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 f( link.load() ) is assigned to the hazard pointer. - */ - template - typename atomic_marked_ptr::marked_ptr protect( atomic_marked_ptr const& link, Func f ) - { - typename atomic_marked_ptr::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 - 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 p.ptr(), no loop is performed. - Can be used for a marked pointer that cannot be changed concurrently. - */ - template - T * assign( cds::details::marked_ptr 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 - T * get() const - { - return static_cast( 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 - class GuardArray: public hrc::AutoHPArray - { - //@cond - typedef hrc::AutoHPArray base_class; - //@endcond - public: - /// Rebind array for other size \p OtherLimit - template - struct rebind { - typedef GuardArray 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 - T * protect( size_t nIndex, atomic_ref 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 atomic_marked_ptr::marked_ptr protect( size_t nIndex, atomic_marked_ptr const& link ) - { - typename atomic_marked_ptr::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 - /** - 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 f( toGuard.load() ) is assigned to the hazard pointer. - */ - template - T * protect(size_t nIndex, atomic_ref 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 f( link.load() ) is assigned to the hazard pointer. - */ - template - typename atomic_marked_ptr::marked_ptr protect( size_t nIndex, atomic_marked_ptr const& link, Func f ) - { - typename atomic_marked_ptr::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 - 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 p.ptr(), no loop is performed. - Can be used for a marked pointer that cannot be changed concurrently. - */ - template - T * assign( size_t nIndex, cds::details::marked_ptr 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 - T * get( size_t nIndex) const - { - return static_cast( 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 - 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 - 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 diff --git a/cds/gc/hrc_impl.h b/cds/gc/hrc_impl.h deleted file mode 100644 index db45a5bc..00000000 --- a/cds/gc/hrc_impl.h +++ /dev/null @@ -1,57 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HRC_IMPL_H -#define __CDS_GC_HRC_IMPL_H - -#include -#include - -//@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() ) - {} - - template - inline HRC::GuardArray::GuardArray() - : GuardArray::base_class( threading::getGC() ) - {} - - template - inline void HRC::retire( T * p, void (* pFunc)(T *) ) - { - cds::threading::getGC().retireNode( p, reinterpret_cast(pFunc) ); - } - - template - inline void HRC::retire( T * p ) - { - cds::threading::getGC().retireNode( p, reinterpret_cast( cds::details::static_functor::call )); - } - - inline void HRC::scan() - { - cds::threading::getGC().scan(); - } - - -}} // namespace cds::gc -//@endcond - -#endif // #ifndef __CDS_GC_HRC_IMPL_H diff --git a/cds/gc/hzp/hzp.h b/cds/gc/hzp/hzp.h index 59f50d9f..a3ccf66c 100644 --- a/cds/gc/hzp/hzp.h +++ b/cds/gc/hzp/hzp.h @@ -37,43 +37,36 @@ namespace cds { Feature %cds::gc::HP - %cds::gc::HRC %cds::gc::PTB Implementation quality stable - unstable stable Performance rank (1 - slowest, 5 - fastest) 5 - 1 4 Max number of guarded (hazard) pointers per thread limited (specifies in GC object ctor) - limited (specifies in GC object ctor) unlimited (dynamically allocated when needed) Max number of retired pointers1 bounded bounded - bounded Array of retired pointers preallocated for each thread, limited in size - preallocated for each thread, limited in size global for the entire process, unlimited (dynamically allocated when needed) Support direct pointer to item of lock-free container (useful for iterators) not supported - potentially supported (not implemented) not supported diff --git a/cds/intrusive/optimistic_queue.h b/cds/intrusive/optimistic_queue.h index ca0216ac..812c2433 100644 --- a/cds/intrusive/optimistic_queue.h +++ b/cds/intrusive/optimistic_queue.h @@ -18,8 +18,8 @@ namespace cds { namespace intrusive { /// 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 struct node: public GC::container_node diff --git a/cds/opt/options.h b/cds/opt/options.h index ecd6ea68..55d05dc4 100644 --- a/cds/opt/options.h +++ b/cds/opt/options.h @@ -196,8 +196,7 @@ namespace opt { /** 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 diff --git a/cds/threading/details/_common.h b/cds/threading/details/_common.h index 1d60b66e..619a01f2 100644 --- a/cds/threading/details/_common.h +++ b/cds/threading/details/_common.h @@ -4,7 +4,6 @@ #define __CDS_THREADING__COMMON_H #include -#include #include #include @@ -75,9 +74,6 @@ namespace cds { // 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(); }; @@ -114,7 +110,6 @@ namespace cds { //@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; @@ -128,7 +123,6 @@ namespace cds { //@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 @@ -162,11 +156,6 @@ namespace cds { 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 @@ -181,12 +170,6 @@ namespace cds { 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(); @@ -207,8 +190,6 @@ namespace cds { 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(); @@ -232,8 +213,6 @@ namespace cds { 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(); diff --git a/cds/threading/details/cxx11_manager.h b/cds/threading/details/cxx11_manager.h index c2f05a1a..625380a6 100644 --- a/cds/threading/details/cxx11_manager.h +++ b/cds/threading/details/cxx11_manager.h @@ -107,18 +107,6 @@ namespace cds { namespace threading { 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 diff --git a/cds/threading/details/gcc_manager.h b/cds/threading/details/gcc_manager.h index dbf1588f..0c0c7e2a 100644 --- a/cds/threading/details/gcc_manager.h +++ b/cds/threading/details/gcc_manager.h @@ -107,18 +107,6 @@ namespace cds { namespace threading { 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 diff --git a/cds/threading/details/msvc_manager.h b/cds/threading/details/msvc_manager.h index c2f4ef05..c6660a01 100644 --- a/cds/threading/details/msvc_manager.h +++ b/cds/threading/details/msvc_manager.h @@ -107,18 +107,6 @@ namespace cds { namespace threading { 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 diff --git a/cds/threading/details/pthread_manager.h b/cds/threading/details/pthread_manager.h index fbc97059..99fadd5a 100644 --- a/cds/threading/details/pthread_manager.h +++ b/cds/threading/details/pthread_manager.h @@ -204,17 +204,6 @@ namespace cds { namespace threading { 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 diff --git a/cds/threading/details/wintls_manager.h b/cds/threading/details/wintls_manager.h index f6bb3efb..47b2de3c 100644 --- a/cds/threading/details/wintls_manager.h +++ b/cds/threading/details/wintls_manager.h @@ -207,17 +207,6 @@ namespace cds { namespace threading { 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 diff --git a/cds/threading/model.h b/cds/threading/model.h index bbc1c47a..3a7bd340 100644 --- a/cds/threading/model.h +++ b/cds/threading/model.h @@ -31,19 +31,6 @@ namespace cds { namespace threading { 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() - { - 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 diff --git a/projects/Win/vc12/cds.vcxproj b/projects/Win/vc12/cds.vcxproj index 373bc40f..c82a2cb9 100644 --- a/projects/Win/vc12/cds.vcxproj +++ b/projects/Win/vc12/cds.vcxproj @@ -620,7 +620,6 @@ - @@ -742,8 +741,6 @@ - - @@ -835,7 +832,6 @@ - @@ -844,11 +840,6 @@ - - - - - diff --git a/projects/Win/vc12/cds.vcxproj.filters b/projects/Win/vc12/cds.vcxproj.filters index ef76ea7f..e7b7f7ea 100644 --- a/projects/Win/vc12/cds.vcxproj.filters +++ b/projects/Win/vc12/cds.vcxproj.filters @@ -21,9 +21,6 @@ {21a6c665-7381-45b8-9f03-b21f3da5503d} - - {695568b2-b136-4b80-bd18-6e3e13c22301} - {53d28ee4-5fe9-4fa1-a617-53d8b0628eac} @@ -162,9 +159,6 @@ Source Files - - Source Files - Source Files @@ -251,9 +245,6 @@ Header Files\cds\gc - - Header Files\cds\gc - Header Files\cds\gc @@ -278,21 +269,6 @@ Header Files\cds\gc\hzp - - Header Files\cds\gc\hrc - - - Header Files\cds\gc\hrc - - - Header Files\cds\gc\hrc - - - Header Files\cds\gc\hrc - - - Header Files\cds\gc\hrc - Header Files\cds\gc\ptb @@ -689,12 +665,6 @@ Header Files\cds\gc - - Header Files\cds\gc - - - Header Files\cds\gc - Header Files\cds\gc diff --git a/projects/source.libcds.mk b/projects/source.libcds.mk index 20061824..b823c3af 100644 --- a/projects/source.libcds.mk +++ b/projects/source.libcds.mk @@ -1,6 +1,5 @@ CDS_SOURCES=src/hzp_gc.cpp \ src/init.cpp \ - src/hrc_gc.cpp \ src/ptb_gc.cpp \ src/urcu_gp.cpp \ src/urcu_sh.cpp \ diff --git a/src/hrc_gc.cpp b/src/hrc_gc.cpp deleted file mode 100644 index f6f7877e..00000000 --- a/src/hrc_gc.cpp +++ /dev/null @@ -1,408 +0,0 @@ -//$$CDS-header$$ - -/* - File: hrc_gc.cpp - - Implementation of cds::gc::hrc::HRCGarbageCollector - - Editions: - 2008.03.10 Maxim.Khiszinsky Created -*/ - -#include - -#include "hzp_const.h" -#include -#include // 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( 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 diff --git a/src/hzp_const.h b/src/hzp_const.h index 4d3291bc..af10977e 100644 --- a/src/hzp_const.h +++ b/src/hzp_const.h @@ -25,21 +25,6 @@ namespace cds { namespace 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 diff --git a/tests/cppunit/test_main.cpp b/tests/cppunit/test_main.cpp index 62718278..3ae3362c 100644 --- a/tests/cppunit/test_main.cpp +++ b/tests/cppunit/test_main.cpp @@ -28,7 +28,6 @@ #include #include -#include #include #include #include @@ -74,33 +73,6 @@ std::ostream& operator << (std::ostream& s, const cds::gc::hzp::GarbageCollector 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; @@ -149,11 +121,6 @@ namespace CppUnitMini 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; - } } } @@ -364,7 +331,6 @@ int main(int argc, char** argv) // Safe reclamation schemes cds::gc::HP hzpGC( nHazardPtrCount ); - cds::gc::HRC hrcGC( nHazardPtrCount ); cds::gc::PTB ptbGC; // RCU varieties diff --git a/tests/data/test-express.conf b/tests/data/test-express.conf index e4f7da07..8b285e8d 100644 --- a/tests/data/test-express.conf +++ b/tests/data/test-express.conf @@ -1,7 +1,7 @@ [General] # HZP scan strategy, possible values are "classic", "inplace". Default is "classic" HZP_scan_strategy=inplace -# Hazard pointer count per thread, for gc::HP and gc::HRC +# Hazard pointer count per thread, for gc::HP hazard_pointer_count=72 [Atomic_ST] diff --git a/tests/unit/stack/intrusive_stack_defs.h b/tests/unit/stack/intrusive_stack_defs.h index 2e52a334..06e0a2bc 100644 --- a/tests/unit/stack/intrusive_stack_defs.h +++ b/tests/unit/stack/intrusive_stack_defs.h @@ -10,7 +10,6 @@ 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 > ) \