From: khizmax Date: Fri, 14 Nov 2014 11:38:56 +0000 (+0300) Subject: rearrange cds/gc contents X-Git-Tag: v2.0.0~97 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=9d6b5b62532cda918cde958184d346368a368142 rearrange cds/gc contents --- diff --git a/cds/container/ellen_bintree_map_dhp.h b/cds/container/ellen_bintree_map_dhp.h index 91378d43..59ed1e27 100644 --- a/cds/container/ellen_bintree_map_dhp.h +++ b/cds/container/ellen_bintree_map_dhp.h @@ -3,7 +3,7 @@ #ifndef __CDS_CONTAINER_ELLEN_BINTREE_MAP_DHP_H #define __CDS_CONTAINER_ELLEN_BINTREE_MAP_DHP_H -#include +#include #include #endif // #ifndef __CDS_CONTAINER_ELLEN_BINTREE_MAP_DHP_H diff --git a/cds/container/ellen_bintree_set_dhp.h b/cds/container/ellen_bintree_set_dhp.h index beaca96b..3bb3adf1 100644 --- a/cds/container/ellen_bintree_set_dhp.h +++ b/cds/container/ellen_bintree_set_dhp.h @@ -3,7 +3,7 @@ #ifndef __CDS_CONTAINER_ELLEN_BINTREE_SET_DHP_H #define __CDS_CONTAINER_ELLEN_BINTREE_SET_DHP_H -#include +#include #include #endif // #ifndef __CDS_CONTAINER_ELLEN_BINTREE_SET_DHP_H diff --git a/cds/gc/dhp.h b/cds/gc/dhp.h index 89abde52..819f49dc 100644 --- a/cds/gc/dhp.h +++ b/cds/gc/dhp.h @@ -1,14 +1,10 @@ //$$CDS-header$$ -#ifndef __CDS_GC_DHP_H -#define __CDS_GC_DHP_H +#ifndef __CDS_GC_PTB_H +#define __CDS_GC_PTB_H -#include +#include +#include +#include -//@cond -namespace cds { namespace gc { - typedef PTB DHP; -}} // namespace cds::gc -//@endcond - -#endif // #ifndef __CDS_GC_DHP_H +#endif // #ifndef __CDS_GC_PTB_H diff --git a/cds/gc/dhp_decl.h b/cds/gc/dhp_decl.h new file mode 100644 index 00000000..32499132 --- /dev/null +++ b/cds/gc/dhp_decl.h @@ -0,0 +1,421 @@ +//$$CDS-header$$ + +#ifndef __CDS_GC_PTB_DECL_H +#define __CDS_GC_PTB_DECL_H + +#include +#include +#include + +namespace cds { namespace gc { + + /// Pass-the-Buck garbage collector + /** @ingroup cds_garbage_collector + @headerfile cds/gc/dhp.h + This class is a wrapper for Pass-the-Buck garbage collector internal implementation. + + Sources: + - [2002] M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting + dynamic-sized lockfree data structures. Technical Report TR-2002-112, Sun Microsystems Laboratories, 2002 + - [2002] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Dynamic-sized Lockfree Data Structures. + Technical Report TR-2002-110, Sun Microsystems Laboratories, 2002 + - [2005] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking Memory Management Support + for Dynamic_Sized Data Structures. ACM Transactions on Computer Systems, Vol.23, No.2, May 2005 + + See \ref cds_how_to_use "How to use" section for details of garbage collector applying. + */ + class PTB + { + public: + /// Native guarded pointer type + typedef void * guarded_pointer; + + /// Atomic reference + /** + @headerfile cds/gc/dhp.h + */ + template using atomic_ref = atomics::atomic; + + /// Atomic type + /** + @headerfile cds/gc/dhp.h + */ + template using atomic_type = atomics::atomic; + + /// Atomic marked pointer + /** + @headerfile cds/gc/dhp.h + */ + template using atomic_marked_ptr = atomics::atomic; + + /// Thread GC implementation for internal usage + typedef ptb::ThreadGC thread_gc_impl; + + /// Wrapper for ptb::ThreadGC class + /** + @headerfile cds/gc/dhp.h + This class performs automatically attaching/detaching Pass-the-Buck 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 Pass-the-Buck 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 Pass-the-Buck GC. + - \p false (default) - the class destructor will detach the thread from Pass-the-Buck GC. + */ + thread_gc( + bool bPersistent = false + ) ; // inline in ptb_impl.h + + /// Destructor + /** + If the object has been created in persistent mode, the destructor does nothing. + Otherwise it detaches the current thread from Pass-the-Buck GC. + */ + ~thread_gc() ; // inline in ptb_impl.h + }; + + + /// Pass-the-Buck guard + /** + @headerfile cds/gc/dhp.h + This class is a wrapper for ptb::Guard. + */ + class Guard: public ptb::Guard + { + //@cond + typedef ptb::Guard base_class; + //@endcond + + public: + //@cond + Guard() ; // inline in ptb_impl.h + //@endcond + + /// Protects a pointer of type atomic + /** + 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( atomics::atomic 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 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( atomics::atomic 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; + } + + /// Store \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); + } + + //@cond + std::nullptr_t assign( std::nullptr_t ) + { + return base_class::operator =(nullptr); + } + //@endcond + + /// 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( 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 (relaxed read) + template + T * get() const + { + return reinterpret_cast( get_native() ); + } + + /// Get native guarded pointer stored + guarded_pointer get_native() const + { + return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed); + } + + }; + + /// Array of Pass-the-Buck guards + /** + @headerfile cds/gc/dhp.h + This class is a wrapper for ptb::GuardArray template. + Template parameter \p Count defines the size of PTB array. + */ + template + class GuardArray: public ptb::GuardArray + { + //@cond + typedef ptb::GuardArray base_class; + //@endcond + public: + /// Rebind array for other size \p COUNT2 + template + struct rebind { + typedef GuardArray other ; ///< rebinding result + }; + + public: + //@cond + GuardArray() ; // inline in ptb_impl.h + //@endcond + + /// 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 + */ + template + T protect(size_t nIndex, atomics::atomic const& toGuard ) + { + T pRet; + do { + pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) ); + } while ( pRet != toGuard.load(atomics::memory_order_acquire)); + + return pRet; + } + + /// 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, atomics::atomic 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; + } + + /// 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 assign( 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 reinterpret_cast( get_native( nIndex ) ); + } + + /// Get native guarded pointer stored + guarded_pointer get_native( size_t nIndex ) const + { + return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed); + } + + /// Capacity of the guard array + static CDS_CONSTEXPR size_t capacity() + { + return Count; + } + }; + + public: + /// Initializes ptb::GarbageCollector singleton + /** + The constructor calls GarbageCollector::Construct with passed parameters. + See ptb::GarbageCollector::Construct for explanation of parameters meaning. + */ + PTB( + size_t nLiberateThreshold = 1024 + , size_t nInitialThreadGuardCount = 8 + ) + { + ptb::GarbageCollector::Construct( + nLiberateThreshold, + nInitialThreadGuardCount + ); + } + + /// Terminates ptb::GarbageCollector singleton + /** + The destructor calls \code ptb::GarbageCollector::Destruct() \endcode + */ + ~PTB() + { + ptb::GarbageCollector::Destruct(); + } + + /// Checks if count of hazard pointer is no less than \p nCountNeeded + /** + The function always returns \p true since the guard count is unlimited for + PTB garbage collector. + */ + static bool check_available_guards( size_t nCountNeeded, bool /*bRaiseException*/ = true ) + { + CDS_UNUSED( nCountNeeded ); + 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 *) ) + { + ptb::GarbageCollector::instance().retirePtr( p, pFunc ); + } + + /// 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 guarded pointer points to it. + + See gc::HP::retire for \p Disposer requirements. + */ + template + static void retire( T * p ) + { + retire( p, cds::details::static_functor::call ); + } + + /// Checks if Pass-the-Buck GC is constructed and may be used + static bool isUsed() + { + return ptb::GarbageCollector::isUsed(); + } + + /// Forced GC cycle call for current thread + /** + Usually, this function should not be called directly. + */ + static void scan() ; // inline in ptb_impl.h + + /// Synonym for \ref scan() + static void force_dispose() + { + scan(); + } + }; + +}} // namespace cds::gc + +#endif // #ifndef __CDS_GC_PTB_DECL_H diff --git a/cds/gc/dhp_impl.h b/cds/gc/dhp_impl.h new file mode 100644 index 00000000..201564cf --- /dev/null +++ b/cds/gc/dhp_impl.h @@ -0,0 +1,43 @@ +//$$CDS-header$$ + +#ifndef __CDS_GC_PTB_IMPL_H +#define __CDS_GC_PTB_IMPL_H + +#include + +//@cond +namespace cds { namespace gc { + + inline PTB::thread_gc::thread_gc( + bool bPersistent + ) + : m_bPersistent( bPersistent ) + { + if ( !cds::threading::Manager::isThreadAttached() ) + cds::threading::Manager::attachThread(); + } + + inline PTB::thread_gc::~thread_gc() + { + if ( !m_bPersistent ) + cds::threading::Manager::detachThread(); + } + + inline PTB::Guard::Guard() + : Guard::base_class( cds::threading::getGC() ) + {} + + template + inline PTB::GuardArray::GuardArray() + : GuardArray::base_class( cds::threading::getGC() ) + {} + + inline void PTB::scan() + { + cds::threading::getGC().scan(); + } + +}} // namespace cds::gc +//@endcond + +#endif // #ifndef __CDS_GC_PTB_IMPL_H diff --git a/cds/gc/hp/details/hp_alloc.h b/cds/gc/hp/details/hp_alloc.h new file mode 100644 index 00000000..2dcadd25 --- /dev/null +++ b/cds/gc/hp/details/hp_alloc.h @@ -0,0 +1,324 @@ +//$$CDS-header$$ + +#ifndef __CDS_GC_HZP_DETAILS_HP_ALLOC_H +#define __CDS_GC_HZP_DETAILS_HP_ALLOC_H + +#include +#include +#include +#include + +//@cond +namespace cds { + namespace gc { namespace hzp { + /// Hazard Pointer schema implementation details + namespace details { + + /// Hazard pointer guard + /** + It is unsafe to use this class directly. + Instead, the AutoHPGuard class should be used. + + Template parameter: + \li HazardPointer - type of hazard pointer. It is \ref hazard_pointer for Michael's Hazard Pointer reclamation schema + */ + template + class HPGuardT: protected atomics::atomic + { + public: + typedef HazardPointer hazard_ptr ; ///< Hazard pointer type + private: + //@cond + typedef atomics::atomic base_class; + //@endcond + + protected: + //@cond + template friend class HPAllocator; + //@endcond + + public: + HPGuardT() CDS_NOEXCEPT + : base_class( nullptr ) + {} + ~HPGuardT() CDS_NOEXCEPT + {} + + /// Sets HP value. Guards pointer \p p from reclamation. + /** + Storing has release semantics. + */ + template + T * operator =( T * p ) CDS_NOEXCEPT + { + // We use atomic store with explicit memory order because other threads may read this hazard pointer concurrently + base_class::store( reinterpret_cast(p), atomics::memory_order_release ); + return p; + } + + //@cond + std::nullptr_t operator=( std::nullptr_t ) CDS_NOEXCEPT + { + clear(); + return nullptr; + } + //@endcond + + /// Returns current value of hazard pointer + /** + Loading has acquire semantics + */ + operator hazard_ptr() const CDS_NOEXCEPT + { + return get(); + } + + /// Returns current value of hazard pointer + /** + Loading has acquire semantics + */ + hazard_ptr get() const CDS_NOEXCEPT + { + return base_class::load( atomics::memory_order_acquire ); + } + + /// Clears HP + /** + Clearing has relaxed semantics. + */ + void clear() CDS_NOEXCEPT + { + // memory order is not necessary here + base_class::store( nullptr, atomics::memory_order_relaxed ); + //CDS_COMPILER_RW_BARRIER; + } + }; + + /// Specialization of HPGuardT for hazard_pointer type + typedef HPGuardT HPGuard; + + /// Array of hazard pointers. + /** + Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation. + Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed + GarbageCollector::getHazardPointerCount(). + + It is unsafe to use this class directly. Instead, the AutoHPArray should be used. + + While creating the object of HPArray class an array of size \p Count of hazard pointers is reserved by + the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and + returns reserved HP to the HP pool of ThreadGC. + + Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains + the HPArray object and implements interface for HP setting and freeing. + + Template parameter: + \li HazardPointer - type of hazard pointer. It is hazard_pointer usually + \li Count - capacity of array + + */ + template + class HPArrayT + { + public: + typedef HazardPointer hazard_ptr_type ; ///< Hazard pointer type + typedef HPGuardT atomic_hazard_ptr ; ///< Element type of the array + static const size_t c_nCapacity = Count ; ///< Capacity of the array + + private: + //@cond + atomic_hazard_ptr * m_arr ; ///< Hazard pointer array of size = \p Count + template friend class HPAllocator; + //@endcond + + public: + /// Constructs uninitialized array. + HPArrayT() CDS_NOEXCEPT + {} + + /// Destructs object + ~HPArrayT() CDS_NOEXCEPT + {} + + /// Returns max count of hazard pointer for this array + CDS_CONSTEXPR size_t capacity() const + { + return c_nCapacity; + } + + /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count + void set( size_t nIndex, hazard_ptr_type hzPtr ) CDS_NOEXCEPT + { + assert( nIndex < capacity() ); + m_arr[nIndex] = hzPtr; + } + + /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) + atomic_hazard_ptr& operator []( size_t nIndex ) CDS_NOEXCEPT + { + assert( nIndex < capacity() ); + return m_arr[nIndex]; + } + + /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version] + atomic_hazard_ptr& operator []( size_t nIndex ) const CDS_NOEXCEPT + { + assert( nIndex < capacity() ); + return m_arr[nIndex]; + } + + /// Clears (sets to \p nullptr) hazard pointer \p nIndex + void clear( size_t nIndex ) CDS_NOEXCEPT + { + assert( nIndex < capacity() ); + m_arr[ nIndex ].clear(); + } + }; + + /// Specialization of HPArrayT class for hazard_pointer type + template using HPArray = HPArrayT; + + /// Allocator of hazard pointers for the thread + /** + The hazard pointer array is the free-list of unused hazard pointer for the thread. + The array is managed as a stack. + The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime + + Each allocator object is thread-private. + + Template parameters: + \li HazardPointer - type of hazard pointer (hazard_pointer usually) + \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR + + This helper class should not be used directly. + */ + template < typename HazardPointer, class Allocator = CDS_DEFAULT_ALLOCATOR > + class HPAllocator + { + public: + typedef HazardPointer hazard_ptr_type ; ///< type of hazard pointer + typedef HPGuardT atomic_hazard_ptr ; ///< Atomic hazard pointer type + typedef Allocator allocator_type ; ///< allocator type + + private: + //@cond + typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl; + + atomic_hazard_ptr * m_arrHazardPtr ; ///< Array of hazard pointers + size_t m_nTop ; ///< The top of stack + const size_t m_nCapacity ; ///< Array capacity + + //@endcond + + public: + /// Default ctor + explicit HPAllocator( + size_t nCapacity ///< max count of hazard pointer per thread + ) + : m_arrHazardPtr( alloc_array( nCapacity ) ) + , m_nCapacity( nCapacity ) + { + make_free(); + } + + /// Dtor + ~HPAllocator() + { + allocator_impl().Delete( m_arrHazardPtr, capacity() ); + } + + /// Get capacity of array + size_t capacity() const CDS_NOEXCEPT + { + return m_nCapacity; + } + + /// Get size of array. The size is equal to the capacity of array + size_t size() const CDS_NOEXCEPT + { + return capacity(); + } + + /// Checks if all items are allocated + bool isFull() const CDS_NOEXCEPT + { + return m_nTop == 0; + } + + /// Allocates hazard pointer + atomic_hazard_ptr& alloc() CDS_NOEXCEPT + { + assert( m_nTop > 0 ); + --m_nTop; + return m_arrHazardPtr[m_nTop]; + } + + /// Frees previously allocated hazard pointer + void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT + { + assert( m_nTop < capacity() ); + hp.clear(); + ++m_nTop; + CDS_COMPILER_RW_BARRIER ; // ??? + } + + /// Allocates hazard pointers array + /** + Allocates \p Count hazard pointers from array \p m_arrHazardPtr + Returns initialized object \p arr + */ + template + void alloc( HPArrayT& arr ) CDS_NOEXCEPT + { + assert( m_nTop >= Count ); + m_nTop -= Count; + arr.m_arr = m_arrHazardPtr + m_nTop; + } + + /// Frees hazard pointer array + /** + Frees the array of hazard pointers allocated by previous call \p this->alloc. + */ + template + void free( const HPArrayT& arr ) CDS_NOEXCEPT + { + assert( m_nTop + Count <= capacity()); + for ( size_t i = m_nTop; i < m_nTop + Count; ++i ) + m_arrHazardPtr[ i ].clear(); + m_nTop += Count; + } + + /// Makes all HP free + void clear() CDS_NOEXCEPT + { + make_free(); + } + + /// Returns to i-th hazard pointer + atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT + { + assert( i < capacity() ); + return m_arrHazardPtr[i]; + } + + private: + //@cond + void make_free() CDS_NOEXCEPT + { + for ( size_t i = 0; i < capacity(); ++i ) + m_arrHazardPtr[ i ].clear(); + m_nTop = capacity(); + } + + atomic_hazard_ptr * alloc_array( size_t nCapacity ) + { + return allocator_impl().NewArray( nCapacity ); + } + //@endcond + }; + + }}} // namespace gc::hzp::details +} // namespace cds +//@endcond + +#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_ALLOC_H diff --git a/cds/gc/hp/details/hp_fwd.h b/cds/gc/hp/details/hp_fwd.h new file mode 100644 index 00000000..3183f47f --- /dev/null +++ b/cds/gc/hp/details/hp_fwd.h @@ -0,0 +1,15 @@ +//$$CDS-header$$ + +#ifndef __CDS_GC_HZP_DETAILS_HP_FWD_H +#define __CDS_GC_HZP_DETAILS_HP_FWD_H + +namespace cds { + namespace gc { namespace hzp { + + // forward declarations + class GarbageCollector; + class ThreadGC; + } } +} + +#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_FWD_H diff --git a/cds/gc/hp/details/hp_inline.h b/cds/gc/hp/details/hp_inline.h new file mode 100644 index 00000000..dbb561c4 --- /dev/null +++ b/cds/gc/hp/details/hp_inline.h @@ -0,0 +1,26 @@ +//$$CDS-header$$ + +#ifndef __CDS_GC_HZP_DETAILS_HP_INLINE_H +#define __CDS_GC_HZP_DETAILS_HP_INLINE_H + +namespace cds { + namespace gc{ namespace hzp { namespace details { + + /************************************************************************/ + /* INLINES */ + /************************************************************************/ + inline retired_vector::retired_vector( const cds::gc::hzp::GarbageCollector& HzpMgr ) + : m_arr( HzpMgr.getMaxRetiredPtrCount() ), + m_nSize(0) + {} + + inline HPRec::HPRec( const cds::gc::hzp::GarbageCollector& HzpMgr ) + : m_hzp( HzpMgr.getHazardPointerCount() ), + m_arrRetired( HzpMgr ) + {} + + } } } // namespace gc::hzp::details +} // namespace cds + + +#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_INLINE_H diff --git a/cds/gc/hp/details/hp_retired.h b/cds/gc/hp/details/hp_retired.h new file mode 100644 index 00000000..6b6dd4a2 --- /dev/null +++ b/cds/gc/hp/details/hp_retired.h @@ -0,0 +1,86 @@ +//$$CDS-header$$ + +#ifndef __CDS_GC_HZP_DETAILS_HP_RETIRED_H +#define __CDS_GC_HZP_DETAILS_HP_RETIRED_H + +#include +#include + +#include + +namespace cds { + namespace gc{ namespace hzp { namespace details { + + /// Retired pointer + typedef cds::gc::details::retired_ptr retired_ptr; + + /// Array of retired pointers + /** + The vector of retired pointer ready to delete. + + The Hazard Pointer schema is build on thread-static arrays. For each HP-enabled thread the HP manager allocates + array of retired pointers. The array belongs to the thread: owner thread writes to the array, other threads + just read it. + */ + class retired_vector { + /// Underlying vector implementation + typedef cds::details::bounded_array retired_vector_impl; + + retired_vector_impl m_arr ; ///< the array of retired pointers + size_t m_nSize ; ///< Current size of \p m_arr + + public: + /// Iterator + typedef retired_vector_impl::iterator iterator; + + /// Constructor + retired_vector( const cds::gc::hzp::GarbageCollector& HzpMgr ) ; // inline + ~retired_vector() + {} + + /// Vector capacity. + /** + The capacity is constant for any thread. It is defined by cds::gc::hzp::GarbageCollector. + */ + size_t capacity() const { return m_arr.capacity(); } + + /// Current vector size (count of retired pointers in the vector) + size_t size() const { return m_nSize; } + + /// Set vector size. Uses internally + void size( size_t nSize ) + { + assert( nSize <= capacity() ); + m_nSize = nSize; + } + + /// Pushes retired pointer to the vector + void push( const retired_ptr& p ) + { + assert( m_nSize < capacity() ); + m_arr[ m_nSize ] = p; + ++m_nSize; + } + + /// Checks if the vector is full (size() == capacity() ) + bool isFull() const + { + return m_nSize >= capacity(); + } + + /// Begin iterator + iterator begin() { return m_arr.begin(); } + /// End iterator + iterator end() { return m_arr.begin() + m_nSize ; } + + /// Clears the vector. After clearing, size() == 0 + void clear() + { + m_nSize = 0; + } + }; + + } } } // namespace gc::hzp::details +} // namespace cds + +#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_RETIRED_H diff --git a/cds/gc/hp/details/hp_type.h b/cds/gc/hp/details/hp_type.h new file mode 100644 index 00000000..7ff9ab35 --- /dev/null +++ b/cds/gc/hp/details/hp_type.h @@ -0,0 +1,23 @@ +//$$CDS-header$$ + +#ifndef __CDS_GC_HZP_DETAILS_HP_TYPE_H +#define __CDS_GC_HZP_DETAILS_HP_TYPE_H + +#include + +namespace cds { + namespace gc { + namespace hzp { + + /// Hazard pointer + typedef void * hazard_pointer; + + /// Pointer to function to free (destruct and deallocate) retired pointer of specific type + typedef cds::gc::details::free_retired_ptr_func free_retired_ptr_func; + } + } +} + +#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_TYPE_H + + diff --git a/cds/gc/hp/hzp.h b/cds/gc/hp/hzp.h new file mode 100644 index 00000000..7e291659 --- /dev/null +++ b/cds/gc/hp/hzp.h @@ -0,0 +1,655 @@ +//$$CDS-header$$ + +#ifndef __CDS_GC_HZP_HZP_H +#define __CDS_GC_HZP_HZP_H + +#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 + +/* + Editions: + 2007.12.24 khizmax Add statistics and CDS_GATHER_HAZARDPTR_STAT macro + 2008.03.06 khizmax Refactoring: implementation of HazardPtrMgr is moved to hazardptr.cpp + 2008.03.08 khizmax Remove HazardPtrMgr singleton. Now you must initialize/destroy HazardPtrMgr calling + HazardPtrMgr::Construct / HazardPtrMgr::Destruct before use (usually in main() function). + 2008.12.06 khizmax Refactoring. Changes class name, namespace hierarchy, all helper defs have been moved to details namespace + 2010.01.27 khizmax Introducing memory order constraint +*/ + +namespace cds { + /** + @page cds_garbage_collectors_comparison GC comparison + @ingroup cds_garbage_collector + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
Feature%cds::gc::HP%cds::gc::PTB
Implementation qualitystablestable
Performance rank (1 - slowest, 5 - fastest)54
Max number of guarded (hazard) pointers per threadlimited (specifies in GC object ctor)unlimited (dynamically allocated when needed)
Max number of retired pointers1boundedbounded
Array of retired pointerspreallocated for each thread, limited in sizeglobal for the entire process, unlimited (dynamically allocated when needed)
Support direct pointer to item of lock-free container (useful for iterators)not supportednot supported
+ + 1Unbounded count of retired pointer means a possibility of memory exhaustion. + */ + + /// Different safe memory reclamation schemas (garbage collectors) + /** @ingroup cds_garbage_collector + + This namespace specifies different safe memory reclamation (SMR) algorithms. + See \ref cds_garbage_collector "Garbage collectors" + */ + namespace gc { + + /// Michael's Hazard Pointers reclamation schema + /** + \par Sources: + - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes" + - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" + - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers" + + + The cds::gc::hzp namespace and its members are internal representation of Hazard Pointer GC and should not be used directly. + Use cds::gc::HP class in your code. + + Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is + GC class and its nested classes. Before use any HP-related class you must initialize HP garbage collector + by contructing cds::gc::HP object in beginning of your main(). + See cds::gc::HP class for explanation. + */ + namespace hzp { + + namespace details { + /// Hazard pointer record of the thread + /** + The structure of type "single writer - multiple reader": only the owner thread may write to this structure + other threads have read-only access. + */ + struct HPRec { + HPAllocator m_hzp ; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency + retired_vector m_arrRetired ; ///< Retired pointer array + + /// Ctor + HPRec( const cds::gc::hzp::GarbageCollector& HzpMgr ) ; // inline + ~HPRec() + {} + + /// Clears all hazard pointers + void clear() + { + m_hzp.clear(); + } + }; + } // namespace details + + /// GarbageCollector::Scan phase strategy + /** + See GarbageCollector::Scan for explanation + */ + enum scan_type { + classic, ///< classic scan as described in Michael's works (see GarbageCollector::classic_scan) + inplace ///< inplace scan without allocation (see GarbageCollector::inplace_scan) + }; + + /// Hazard Pointer singleton + /** + Safe memory reclamation schema by Michael "Hazard Pointers" + + \par Sources: + \li [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes" + \li [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" + \li [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers" + + */ + class CDS_EXPORT_API GarbageCollector + { + public: + typedef cds::atomicity::event_counter event_counter ; ///< event counter type + + /// Internal GC statistics + struct InternalState { + 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 nHPRecSize ; ///< Size of HP record, bytes (const) + + size_t nHPRecAllocated ; ///< Count of HP record allocations + size_t nHPRecUsed ; ///< Count of HP record used + size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers + size_t nRetiredPtrInFreeHPRecs ; ///< Count of retired pointer in free (unused) HP records + + event_counter::value_type evcAllocHPRec ; ///< Count of HPRec allocations + event_counter::value_type evcRetireHPRec ; ///< Count of HPRec retire events + event_counter::value_type evcAllocNewHPRec; ///< Count of new HPRec allocations from heap + event_counter::value_type evcDeleteHPRec ; ///< Count of HPRec deletions + + event_counter::value_type evcScanCall ; ///< Count of Scan calling + event_counter::value_type evcHelpScanCall ; ///< Count of HelpScan calling + event_counter::value_type evcScanFromHelpScan;///< Count of Scan calls from HelpScan + + event_counter::value_type evcDeletedNode ; ///< Count of deleting of retired objects + event_counter::value_type evcDeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it + }; + + /// No GarbageCollector object is created + CDS_DECLARE_EXCEPTION( HZPManagerEmpty, "Global Hazard Pointer GarbageCollector is NULL" ); + + /// Not enough required Hazard Pointer count + CDS_DECLARE_EXCEPTION( HZPTooMany, "Not enough required Hazard Pointer count" ); + + private: + /// Internal GC statistics + struct Statistics { + event_counter m_AllocHPRec ; ///< Count of HPRec allocations + event_counter m_RetireHPRec ; ///< Count of HPRec retire events + event_counter m_AllocNewHPRec ; ///< Count of new HPRec allocations from heap + event_counter m_DeleteHPRec ; ///< Count of HPRec deletions + + event_counter m_ScanCallCount ; ///< Count of Scan calling + event_counter m_HelpScanCallCount ; ///< Count of HelpScan calling + event_counter m_CallScanFromHelpScan ; ///< Count of Scan calls from HelpScan + + event_counter m_DeletedNode ; ///< Count of retired objects deleting + event_counter m_DeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it + }; + + /// Internal list of cds::gc::hzp::details::HPRec + struct hplist_node: public details::HPRec + { + hplist_node * m_pNextNode ; ///< next hazard ptr record in list + atomics::atomic m_idOwner ; ///< Owner thread id; 0 - the record is free (not owned) + atomics::atomic m_bFree ; ///< true if record if free (not owned) + + //@cond + hplist_node( const GarbageCollector& HzpMgr ) + : HPRec( HzpMgr ), + m_pNextNode( nullptr ), + m_idOwner( OS::c_NullThreadId ), + m_bFree( true ) + {} + + ~hplist_node() + { + assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId ); + assert( m_bFree.load(atomics::memory_order_relaxed) ); + } + //@endcond + }; + + atomics::atomic m_pListHead ; ///< Head of GC list + + static GarbageCollector * m_pHZPManager ; ///< GC instance pointer + + Statistics m_Stat ; ///< Internal statistics + bool m_bStatEnabled ; ///< true - statistics enabled + + 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 + scan_type m_nScanType ; ///< scan type (see \ref scan_type enum) + + + private: + /// Ctor + GarbageCollector( + size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread + size_t nMaxThreadCount = 0, ///< Max count of thread + size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects + scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum) + ); + + /// Dtor + ~GarbageCollector(); + + /// Allocate new HP record + hplist_node * NewHPRec(); + + /// Permanently deletes HPrecord \p pNode + /** + Caveat: for performance reason this function is defined as inline and cannot be called directly + */ + void DeleteHPRec( hplist_node * pNode ); + + /// Permanently deletes retired pointer \p p + /** + Caveat: for performance reason this function is defined as inline and cannot be called directly + */ + void DeletePtr( details::retired_ptr& p ); + + //@cond + void detachAllThread(); + //@endcond + + public: + /// Creates GarbageCollector singleton + /** + GC is the singleton. If GC instance is not exist then the function creates the instance. + Otherwise it does nothing. + + The Michael's HP reclamation schema depends of three parameters: + + \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from + the data structure algorithms. By default, if \p nHazardPtrCount = 0, + the function uses maximum of HP count for CDS library. + + \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100. + + \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than + \p nHazardPtrCount * \p nMaxThreadCount. + Default is 2 * \p nHazardPtrCount * \p nMaxThreadCount. + */ + static void CDS_STDCALL Construct( + size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread + size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application + size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread + scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum) + ); + + /// Destroys global instance of GarbageCollector + /** + The parameter \p bDetachAll should be used carefully: if its value is \p true, + then the destroying GC automatically detaches all attached threads. This feature + can be useful when you have no control over the thread termination, for example, + when \p libcds is injected into existing external thread. + */ + static void CDS_STDCALL Destruct( + bool bDetachAll = false ///< Detach all threads + ); + + /// Returns pointer to GarbageCollector instance + static GarbageCollector& instance() + { + if ( !m_pHZPManager ) + throw HZPManagerEmpty(); + return *m_pHZPManager; + } + + /// Checks if global GC object is constructed and may be used + static bool isUsed() + { + return m_pHZPManager != nullptr; + } + + /// Returns max Hazard Pointer count defined in construction time + size_t getHazardPointerCount() const { return m_nHazardPointerCount; } + + /// Returns max thread count defined in construction time + size_t getMaxThreadCount() const { return m_nMaxThreadCount; } + + /// Returns max size of retired objects array. It is defined in construction time + size_t getMaxRetiredPtrCount() const { return m_nMaxRetiredPtrCount; } + + // Internal statistics + + /// Get internal statistics + InternalState& getInternalState(InternalState& stat) const; + + /// Checks if internal statistics enabled + bool isStatisticsEnabled() const { return m_bStatEnabled; } + + /// Enables/disables internal statistics + bool enableStatistics( bool bEnable ) + { + bool bEnabled = m_bStatEnabled; + m_bStatEnabled = bEnable; + return bEnabled; + } + + /// 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 HZPTooMany(); + } + + /// Get current scan strategy + scan_type getScanType() const + { + return m_nScanType; + } + + /// Set current scan strategy + /** @anchor hzp_gc_setScanType + Scan strategy changing is allowed on the fly. + */ + void setScanType( + scan_type nScanType ///< new scan strategy + ) + { + m_nScanType = nScanType; + } + + public: // Internals for threads + + /// Allocates Hazard Pointer GC record. For internal use only + details::HPRec * AllocateHPRec(); + + /// Free HP record. For internal use only + void RetireHPRec( details::HPRec * pRec ); + + /// The main garbage collecting function + /** + This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers + is reached. + + There are the following scan algorithm: + - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use + - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory + + Use \ref hzp_gc_setScanType "setScanType" member function to setup appropriate scan algorithm. + */ + void Scan( details::HPRec * pRec ) + { + switch ( m_nScanType ) { + case inplace: + inplace_scan( pRec ); + break; + default: + assert(false) ; // Forgotten something?.. + case classic: + classic_scan( pRec ); + break; + } + } + + /// Helper scan routine + /** + The function guarantees that every node that is eligible for reuse is eventually freed, barring + thread failures. To do so, after executing Scan, a thread executes a HelpScan, + where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers + to thread's list of reclaimed pointers. + + The function is called internally by Scan. + */ + void HelpScan( details::HPRec * pThis ); + + protected: + /// Classic scan algorithm + /** @anchor hzp_gc_classic_scan + Classical scan algorithm as described in Michael's paper. + + A scan includes four stages. The first stage involves scanning the array HP for non-null values. + Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer. + Only stage 1 accesses shared variables. The following stages operate only on private variables. + + The second stage of a scan involves sorting local list of protected pointers to allow + binary search in the third stage. + + The third stage of a scan involves checking each reclaimed node + against the pointers in local list of protected pointers. If the binary search yields + no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list + of reclaimed pointers. + + The forth stage prepares new thread's private list of reclaimed pointers + that could not be freed during the current scan, where they remain until the next scan. + + This algorithm allocates memory for internal HP array. + + This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers + is reached. + */ + void classic_scan( details::HPRec * pRec ); + + /// In-place scan algorithm + /** @anchor hzp_gc_inplace_scan + Unlike the \ref hzp_gc_classic_scan "classic_scan" algorithm, \p inplace_scan does not allocate any memory. + All operations are performed in-place. + */ + void inplace_scan( details::HPRec * pRec ); + }; + + /// Thread's hazard pointer manager + /** + To use Hazard Pointer 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 \ref cds_threading "cds::threading::Manager::attachThread()" + on the start of each thread that uses HP GC. Before terminating the thread linked to HP GC it is necessary to call + \ref cds_threading "cds::threading::Manager::detachThread()". + */ + class ThreadGC + { + GarbageCollector& m_HzpManager ; ///< Hazard Pointer GC singleton + details::HPRec * m_pHzpRec ; ///< Pointer to thread's HZP record + + public: + /// Default constructor + ThreadGC() + : m_HzpManager( GarbageCollector::instance() ), + m_pHzpRec( nullptr ) + {} + + /// The object is not copy-constructible + ThreadGC( ThreadGC const& ) = delete; + + ~ThreadGC() + { + fini(); + } + + /// Checks if thread GC is initialized + bool isInitialized() const { return m_pHzpRec != nullptr; } + + /// Initialization. Repeat call is available + void init() + { + if ( !m_pHzpRec ) + m_pHzpRec = m_HzpManager.AllocateHPRec(); + } + + /// Finalization. Repeat call is available + void fini() + { + if ( m_pHzpRec ) { + details::HPRec * pRec = m_pHzpRec; + m_pHzpRec = nullptr; + m_HzpManager.RetireHPRec( pRec ); + } + } + + /// Initializes HP guard \p guard + details::HPGuard& allocGuard() + { + assert( m_pHzpRec ); + return m_pHzpRec->m_hzp.alloc(); + } + + /// Frees HP guard \p guard + void freeGuard( details::HPGuard& guard ) + { + assert( m_pHzpRec ); + m_pHzpRec->m_hzp.free( guard ); + } + + /// Initializes HP guard array \p arr + template + void allocGuard( details::HPArray& arr ) + { + assert( m_pHzpRec ); + m_pHzpRec->m_hzp.alloc( arr ); + } + + /// Frees HP guard array \p arr + template + void freeGuard( details::HPArray& arr ) + { + assert( m_pHzpRec ); + m_pHzpRec->m_hzp.free( arr ); + } + + /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation + template + void retirePtr( T * p, void (* pFunc)(T *) ) + { + retirePtr( details::retired_ptr( reinterpret_cast( p ), reinterpret_cast( pFunc ) ) ); + } + + /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation + void retirePtr( const details::retired_ptr& p ) + { + m_pHzpRec->m_arrRetired.push( p ); + + if ( m_pHzpRec->m_arrRetired.isFull() ) { + // Max of retired pointer count is reached. Do scan + scan(); + } + } + + //@cond + void scan() + { + m_HzpManager.Scan( m_pHzpRec ); + m_HzpManager.HelpScan( m_pHzpRec ); + } + //@endcond + }; + + /// Auto HPGuard. + /** + This class encapsulates Hazard Pointer guard to protect a pointer against deletion . + It allocates one HP from thread's HP array in constructor and free the HP allocated in destruction time. + */ + class AutoHPGuard + { + //@cond + details::HPGuard& m_hp ; ///< Hazard pointer guarded + ThreadGC& m_gc ; ///< Thread GC + //@endcond + + public: + typedef details::HPGuard::hazard_ptr hazard_ptr ; ///< Hazard pointer type + public: + /// Allocates HP guard from \p gc + AutoHPGuard( ThreadGC& gc ) + : m_hp( gc.allocGuard() ) + , m_gc( gc ) + {} + + /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T + template + AutoHPGuard( ThreadGC& gc, T * p ) + : m_hp( gc.allocGuard() ) + , m_gc( gc ) + { + m_hp = p; + } + + /// Frees HP guard. The pointer guarded may be deleted after this. + ~AutoHPGuard() + { + m_gc.freeGuard( m_hp ); + } + + /// Returns thread GC + ThreadGC& getGC() const + { + return m_gc; + } + + /// Protects the pointer \p p against reclamation (guards the pointer). + template + T * operator =( T * p ) + { + return m_hp = p; + } + + //@cond + std::nullptr_t operator =(std::nullptr_t) + { + return m_hp = nullptr; + } + + hazard_ptr get() const + { + return m_hp; + } + //@endcond + }; + + /// Auto-managed array of hazard pointers + /** + This class is wrapper around cds::gc::hzp::details::HPArray class. + \p Count is the size of HP array + */ + template + class AutoHPArray: public details::HPArray + { + ThreadGC& m_mgr ; ///< Thread GC + + public: + /// Rebind array for other size \p COUNT2 + template + struct rebind { + typedef AutoHPArray other ; ///< rebinding result + }; + + 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 hzp +}} // namespace cds::gc + +// Inlines +#include + +#if CDS_COMPILER == CDS_COMPILER_MSVC +# pragma warning(pop) +#endif + +#endif // #ifndef __CDS_GC_HZP_HZP_H diff --git a/cds/gc/hp_decl.h b/cds/gc/hp_decl.h index 2b92a540..76f0aba2 100644 --- a/cds/gc/hp_decl.h +++ b/cds/gc/hp_decl.h @@ -4,7 +4,7 @@ #define __CDS_GC_HP_DECL_H #include // overflow_error -#include +#include #include namespace cds { namespace gc { diff --git a/cds/gc/hzp/details/hp_alloc.h b/cds/gc/hzp/details/hp_alloc.h deleted file mode 100644 index 83a8772f..00000000 --- a/cds/gc/hzp/details/hp_alloc.h +++ /dev/null @@ -1,324 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HZP_DETAILS_HP_ALLOC_H -#define __CDS_GC_HZP_DETAILS_HP_ALLOC_H - -#include -#include -#include -#include - -//@cond -namespace cds { - namespace gc { namespace hzp { - /// Hazard Pointer schema implementation details - namespace details { - - /// Hazard pointer guard - /** - It is unsafe to use this class directly. - Instead, the AutoHPGuard class should be used. - - Template parameter: - \li HazardPointer - type of hazard pointer. It is \ref hazard_pointer for Michael's Hazard Pointer reclamation schema - */ - template - class HPGuardT: protected atomics::atomic - { - public: - typedef HazardPointer hazard_ptr ; ///< Hazard pointer type - private: - //@cond - typedef atomics::atomic base_class; - //@endcond - - protected: - //@cond - template friend class HPAllocator; - //@endcond - - public: - HPGuardT() CDS_NOEXCEPT - : base_class( nullptr ) - {} - ~HPGuardT() CDS_NOEXCEPT - {} - - /// Sets HP value. Guards pointer \p p from reclamation. - /** - Storing has release semantics. - */ - template - T * operator =( T * p ) CDS_NOEXCEPT - { - // We use atomic store with explicit memory order because other threads may read this hazard pointer concurrently - base_class::store( reinterpret_cast(p), atomics::memory_order_release ); - return p; - } - - //@cond - std::nullptr_t operator=( std::nullptr_t ) CDS_NOEXCEPT - { - clear(); - return nullptr; - } - //@endcond - - /// Returns current value of hazard pointer - /** - Loading has acquire semantics - */ - operator hazard_ptr() const CDS_NOEXCEPT - { - return get(); - } - - /// Returns current value of hazard pointer - /** - Loading has acquire semantics - */ - hazard_ptr get() const CDS_NOEXCEPT - { - return base_class::load( atomics::memory_order_acquire ); - } - - /// Clears HP - /** - Clearing has relaxed semantics. - */ - void clear() CDS_NOEXCEPT - { - // memory order is not necessary here - base_class::store( nullptr, atomics::memory_order_relaxed ); - //CDS_COMPILER_RW_BARRIER; - } - }; - - /// Specialization of HPGuardT for hazard_pointer type - typedef HPGuardT HPGuard; - - /// Array of hazard pointers. - /** - Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation. - Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed - GarbageCollector::getHazardPointerCount(). - - It is unsafe to use this class directly. Instead, the AutoHPArray should be used. - - While creating the object of HPArray class an array of size \p Count of hazard pointers is reserved by - the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and - returns reserved HP to the HP pool of ThreadGC. - - Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains - the HPArray object and implements interface for HP setting and freeing. - - Template parameter: - \li HazardPointer - type of hazard pointer. It is hazard_pointer usually - \li Count - capacity of array - - */ - template - class HPArrayT - { - public: - typedef HazardPointer hazard_ptr_type ; ///< Hazard pointer type - typedef HPGuardT atomic_hazard_ptr ; ///< Element type of the array - static const size_t c_nCapacity = Count ; ///< Capacity of the array - - private: - //@cond - atomic_hazard_ptr * m_arr ; ///< Hazard pointer array of size = \p Count - template friend class HPAllocator; - //@endcond - - public: - /// Constructs uninitialized array. - HPArrayT() CDS_NOEXCEPT - {} - - /// Destructs object - ~HPArrayT() CDS_NOEXCEPT - {} - - /// Returns max count of hazard pointer for this array - CDS_CONSTEXPR size_t capacity() const - { - return c_nCapacity; - } - - /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count - void set( size_t nIndex, hazard_ptr_type hzPtr ) CDS_NOEXCEPT - { - assert( nIndex < capacity() ); - m_arr[nIndex] = hzPtr; - } - - /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) - atomic_hazard_ptr& operator []( size_t nIndex ) CDS_NOEXCEPT - { - assert( nIndex < capacity() ); - return m_arr[nIndex]; - } - - /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version] - atomic_hazard_ptr& operator []( size_t nIndex ) const CDS_NOEXCEPT - { - assert( nIndex < capacity() ); - return m_arr[nIndex]; - } - - /// Clears (sets to \p nullptr) hazard pointer \p nIndex - void clear( size_t nIndex ) CDS_NOEXCEPT - { - assert( nIndex < capacity() ); - m_arr[ nIndex ].clear(); - } - }; - - /// Specialization of HPArrayT class for hazard_pointer type - template using HPArray = HPArrayT; - - /// Allocator of hazard pointers for the thread - /** - The hazard pointer array is the free-list of unused hazard pointer for the thread. - The array is managed as a stack. - The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime - - Each allocator object is thread-private. - - Template parameters: - \li HazardPointer - type of hazard pointer (hazard_pointer usually) - \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR - - This helper class should not be used directly. - */ - template < typename HazardPointer, class Allocator = CDS_DEFAULT_ALLOCATOR > - class HPAllocator - { - public: - typedef HazardPointer hazard_ptr_type ; ///< type of hazard pointer - typedef HPGuardT atomic_hazard_ptr ; ///< Atomic hazard pointer type - typedef Allocator allocator_type ; ///< allocator type - - private: - //@cond - typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl; - - atomic_hazard_ptr * m_arrHazardPtr ; ///< Array of hazard pointers - size_t m_nTop ; ///< The top of stack - const size_t m_nCapacity ; ///< Array capacity - - //@endcond - - public: - /// Default ctor - explicit HPAllocator( - size_t nCapacity ///< max count of hazard pointer per thread - ) - : m_arrHazardPtr( alloc_array( nCapacity ) ) - , m_nCapacity( nCapacity ) - { - make_free(); - } - - /// Dtor - ~HPAllocator() - { - allocator_impl().Delete( m_arrHazardPtr, capacity() ); - } - - /// Get capacity of array - size_t capacity() const CDS_NOEXCEPT - { - return m_nCapacity; - } - - /// Get size of array. The size is equal to the capacity of array - size_t size() const CDS_NOEXCEPT - { - return capacity(); - } - - /// Checks if all items are allocated - bool isFull() const CDS_NOEXCEPT - { - return m_nTop == 0; - } - - /// Allocates hazard pointer - atomic_hazard_ptr& alloc() CDS_NOEXCEPT - { - assert( m_nTop > 0 ); - --m_nTop; - return m_arrHazardPtr[m_nTop]; - } - - /// Frees previously allocated hazard pointer - void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT - { - assert( m_nTop < capacity() ); - hp.clear(); - ++m_nTop; - CDS_COMPILER_RW_BARRIER ; // ??? - } - - /// Allocates hazard pointers array - /** - Allocates \p Count hazard pointers from array \p m_arrHazardPtr - Returns initialized object \p arr - */ - template - void alloc( HPArrayT& arr ) CDS_NOEXCEPT - { - assert( m_nTop >= Count ); - m_nTop -= Count; - arr.m_arr = m_arrHazardPtr + m_nTop; - } - - /// Frees hazard pointer array - /** - Frees the array of hazard pointers allocated by previous call \p this->alloc. - */ - template - void free( const HPArrayT& arr ) CDS_NOEXCEPT - { - assert( m_nTop + Count <= capacity()); - for ( size_t i = m_nTop; i < m_nTop + Count; ++i ) - m_arrHazardPtr[ i ].clear(); - m_nTop += Count; - } - - /// Makes all HP free - void clear() CDS_NOEXCEPT - { - make_free(); - } - - /// Returns to i-th hazard pointer - atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT - { - assert( i < capacity() ); - return m_arrHazardPtr[i]; - } - - private: - //@cond - void make_free() CDS_NOEXCEPT - { - for ( size_t i = 0; i < capacity(); ++i ) - m_arrHazardPtr[ i ].clear(); - m_nTop = capacity(); - } - - atomic_hazard_ptr * alloc_array( size_t nCapacity ) - { - return allocator_impl().NewArray( nCapacity ); - } - //@endcond - }; - - }}} // namespace gc::hzp::details -} // namespace cds -//@endcond - -#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_ALLOC_H diff --git a/cds/gc/hzp/details/hp_fwd.h b/cds/gc/hzp/details/hp_fwd.h deleted file mode 100644 index 3183f47f..00000000 --- a/cds/gc/hzp/details/hp_fwd.h +++ /dev/null @@ -1,15 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HZP_DETAILS_HP_FWD_H -#define __CDS_GC_HZP_DETAILS_HP_FWD_H - -namespace cds { - namespace gc { namespace hzp { - - // forward declarations - class GarbageCollector; - class ThreadGC; - } } -} - -#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_FWD_H diff --git a/cds/gc/hzp/details/hp_inline.h b/cds/gc/hzp/details/hp_inline.h deleted file mode 100644 index dbb561c4..00000000 --- a/cds/gc/hzp/details/hp_inline.h +++ /dev/null @@ -1,26 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HZP_DETAILS_HP_INLINE_H -#define __CDS_GC_HZP_DETAILS_HP_INLINE_H - -namespace cds { - namespace gc{ namespace hzp { namespace details { - - /************************************************************************/ - /* INLINES */ - /************************************************************************/ - inline retired_vector::retired_vector( const cds::gc::hzp::GarbageCollector& HzpMgr ) - : m_arr( HzpMgr.getMaxRetiredPtrCount() ), - m_nSize(0) - {} - - inline HPRec::HPRec( const cds::gc::hzp::GarbageCollector& HzpMgr ) - : m_hzp( HzpMgr.getHazardPointerCount() ), - m_arrRetired( HzpMgr ) - {} - - } } } // namespace gc::hzp::details -} // namespace cds - - -#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_INLINE_H diff --git a/cds/gc/hzp/details/hp_retired.h b/cds/gc/hzp/details/hp_retired.h deleted file mode 100644 index fc32ec6a..00000000 --- a/cds/gc/hzp/details/hp_retired.h +++ /dev/null @@ -1,86 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HZP_DETAILS_HP_RETIRED_H -#define __CDS_GC_HZP_DETAILS_HP_RETIRED_H - -#include -#include - -#include - -namespace cds { - namespace gc{ namespace hzp { namespace details { - - /// Retired pointer - typedef cds::gc::details::retired_ptr retired_ptr; - - /// Array of retired pointers - /** - The vector of retired pointer ready to delete. - - The Hazard Pointer schema is build on thread-static arrays. For each HP-enabled thread the HP manager allocates - array of retired pointers. The array belongs to the thread: owner thread writes to the array, other threads - just read it. - */ - class retired_vector { - /// Underlying vector implementation - typedef cds::details::bounded_array retired_vector_impl; - - retired_vector_impl m_arr ; ///< the array of retired pointers - size_t m_nSize ; ///< Current size of \p m_arr - - public: - /// Iterator - typedef retired_vector_impl::iterator iterator; - - /// Constructor - retired_vector( const cds::gc::hzp::GarbageCollector& HzpMgr ) ; // inline - ~retired_vector() - {} - - /// Vector capacity. - /** - The capacity is constant for any thread. It is defined by cds::gc::hzp::GarbageCollector. - */ - size_t capacity() const { return m_arr.capacity(); } - - /// Current vector size (count of retired pointers in the vector) - size_t size() const { return m_nSize; } - - /// Set vector size. Uses internally - void size( size_t nSize ) - { - assert( nSize <= capacity() ); - m_nSize = nSize; - } - - /// Pushes retired pointer to the vector - void push( const retired_ptr& p ) - { - assert( m_nSize < capacity() ); - m_arr[ m_nSize ] = p; - ++m_nSize; - } - - /// Checks if the vector is full (size() == capacity() ) - bool isFull() const - { - return m_nSize >= capacity(); - } - - /// Begin iterator - iterator begin() { return m_arr.begin(); } - /// End iterator - iterator end() { return m_arr.begin() + m_nSize ; } - - /// Clears the vector. After clearing, size() == 0 - void clear() - { - m_nSize = 0; - } - }; - - } } } // namespace gc::hzp::details -} // namespace cds - -#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_RETIRED_H diff --git a/cds/gc/hzp/details/hp_type.h b/cds/gc/hzp/details/hp_type.h deleted file mode 100644 index 7ff9ab35..00000000 --- a/cds/gc/hzp/details/hp_type.h +++ /dev/null @@ -1,23 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HZP_DETAILS_HP_TYPE_H -#define __CDS_GC_HZP_DETAILS_HP_TYPE_H - -#include - -namespace cds { - namespace gc { - namespace hzp { - - /// Hazard pointer - typedef void * hazard_pointer; - - /// Pointer to function to free (destruct and deallocate) retired pointer of specific type - typedef cds::gc::details::free_retired_ptr_func free_retired_ptr_func; - } - } -} - -#endif // #ifndef __CDS_GC_HZP_DETAILS_HP_TYPE_H - - diff --git a/cds/gc/hzp/hzp.h b/cds/gc/hzp/hzp.h deleted file mode 100644 index b92a5a41..00000000 --- a/cds/gc/hzp/hzp.h +++ /dev/null @@ -1,655 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_HZP_HZP_H -#define __CDS_GC_HZP_HZP_H - -#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 - -/* - Editions: - 2007.12.24 khizmax Add statistics and CDS_GATHER_HAZARDPTR_STAT macro - 2008.03.06 khizmax Refactoring: implementation of HazardPtrMgr is moved to hazardptr.cpp - 2008.03.08 khizmax Remove HazardPtrMgr singleton. Now you must initialize/destroy HazardPtrMgr calling - HazardPtrMgr::Construct / HazardPtrMgr::Destruct before use (usually in main() function). - 2008.12.06 khizmax Refactoring. Changes class name, namespace hierarchy, all helper defs have been moved to details namespace - 2010.01.27 khizmax Introducing memory order constraint -*/ - -namespace cds { - /** - @page cds_garbage_collectors_comparison GC comparison - @ingroup cds_garbage_collector - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Feature%cds::gc::HP%cds::gc::PTB
Implementation qualitystablestable
Performance rank (1 - slowest, 5 - fastest)54
Max number of guarded (hazard) pointers per threadlimited (specifies in GC object ctor)unlimited (dynamically allocated when needed)
Max number of retired pointers1boundedbounded
Array of retired pointerspreallocated for each thread, limited in sizeglobal for the entire process, unlimited (dynamically allocated when needed)
Support direct pointer to item of lock-free container (useful for iterators)not supportednot supported
- - 1Unbounded count of retired pointer means a possibility of memory exhaustion. - */ - - /// Different safe memory reclamation schemas (garbage collectors) - /** @ingroup cds_garbage_collector - - This namespace specifies different safe memory reclamation (SMR) algorithms. - See \ref cds_garbage_collector "Garbage collectors" - */ - namespace gc { - - /// Michael's Hazard Pointers reclamation schema - /** - \par Sources: - - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes" - - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" - - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers" - - - The cds::gc::hzp namespace and its members are internal representation of Hazard Pointer GC and should not be used directly. - Use cds::gc::HP class in your code. - - Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is - GC class and its nested classes. Before use any HP-related class you must initialize HP garbage collector - by contructing cds::gc::HP object in beginning of your main(). - See cds::gc::HP class for explanation. - */ - namespace hzp { - - namespace details { - /// Hazard pointer record of the thread - /** - The structure of type "single writer - multiple reader": only the owner thread may write to this structure - other threads have read-only access. - */ - struct HPRec { - HPAllocator m_hzp ; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency - retired_vector m_arrRetired ; ///< Retired pointer array - - /// Ctor - HPRec( const cds::gc::hzp::GarbageCollector& HzpMgr ) ; // inline - ~HPRec() - {} - - /// Clears all hazard pointers - void clear() - { - m_hzp.clear(); - } - }; - } // namespace details - - /// GarbageCollector::Scan phase strategy - /** - See GarbageCollector::Scan for explanation - */ - enum scan_type { - classic, ///< classic scan as described in Michael's works (see GarbageCollector::classic_scan) - inplace ///< inplace scan without allocation (see GarbageCollector::inplace_scan) - }; - - /// Hazard Pointer singleton - /** - Safe memory reclamation schema by Michael "Hazard Pointers" - - \par Sources: - \li [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes" - \li [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" - \li [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers" - - */ - class CDS_EXPORT_API GarbageCollector - { - public: - typedef cds::atomicity::event_counter event_counter ; ///< event counter type - - /// Internal GC statistics - struct InternalState { - 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 nHPRecSize ; ///< Size of HP record, bytes (const) - - size_t nHPRecAllocated ; ///< Count of HP record allocations - size_t nHPRecUsed ; ///< Count of HP record used - size_t nTotalRetiredPtrCount ; ///< Current total count of retired pointers - size_t nRetiredPtrInFreeHPRecs ; ///< Count of retired pointer in free (unused) HP records - - event_counter::value_type evcAllocHPRec ; ///< Count of HPRec allocations - event_counter::value_type evcRetireHPRec ; ///< Count of HPRec retire events - event_counter::value_type evcAllocNewHPRec; ///< Count of new HPRec allocations from heap - event_counter::value_type evcDeleteHPRec ; ///< Count of HPRec deletions - - event_counter::value_type evcScanCall ; ///< Count of Scan calling - event_counter::value_type evcHelpScanCall ; ///< Count of HelpScan calling - event_counter::value_type evcScanFromHelpScan;///< Count of Scan calls from HelpScan - - event_counter::value_type evcDeletedNode ; ///< Count of deleting of retired objects - event_counter::value_type evcDeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it - }; - - /// No GarbageCollector object is created - CDS_DECLARE_EXCEPTION( HZPManagerEmpty, "Global Hazard Pointer GarbageCollector is NULL" ); - - /// Not enough required Hazard Pointer count - CDS_DECLARE_EXCEPTION( HZPTooMany, "Not enough required Hazard Pointer count" ); - - private: - /// Internal GC statistics - struct Statistics { - event_counter m_AllocHPRec ; ///< Count of HPRec allocations - event_counter m_RetireHPRec ; ///< Count of HPRec retire events - event_counter m_AllocNewHPRec ; ///< Count of new HPRec allocations from heap - event_counter m_DeleteHPRec ; ///< Count of HPRec deletions - - event_counter m_ScanCallCount ; ///< Count of Scan calling - event_counter m_HelpScanCallCount ; ///< Count of HelpScan calling - event_counter m_CallScanFromHelpScan ; ///< Count of Scan calls from HelpScan - - event_counter m_DeletedNode ; ///< Count of retired objects deleting - event_counter m_DeferredNode ; ///< Count of objects that cannot be deleted in Scan phase because of a hazard_pointer guards it - }; - - /// Internal list of cds::gc::hzp::details::HPRec - struct hplist_node: public details::HPRec - { - hplist_node * m_pNextNode ; ///< next hazard ptr record in list - atomics::atomic m_idOwner ; ///< Owner thread id; 0 - the record is free (not owned) - atomics::atomic m_bFree ; ///< true if record if free (not owned) - - //@cond - hplist_node( const GarbageCollector& HzpMgr ) - : HPRec( HzpMgr ), - m_pNextNode( nullptr ), - m_idOwner( OS::c_NullThreadId ), - m_bFree( true ) - {} - - ~hplist_node() - { - assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId ); - assert( m_bFree.load(atomics::memory_order_relaxed) ); - } - //@endcond - }; - - atomics::atomic m_pListHead ; ///< Head of GC list - - static GarbageCollector * m_pHZPManager ; ///< GC instance pointer - - Statistics m_Stat ; ///< Internal statistics - bool m_bStatEnabled ; ///< true - statistics enabled - - 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 - scan_type m_nScanType ; ///< scan type (see \ref scan_type enum) - - - private: - /// Ctor - GarbageCollector( - size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread - size_t nMaxThreadCount = 0, ///< Max count of thread - size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects - scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum) - ); - - /// Dtor - ~GarbageCollector(); - - /// Allocate new HP record - hplist_node * NewHPRec(); - - /// Permanently deletes HPrecord \p pNode - /** - Caveat: for performance reason this function is defined as inline and cannot be called directly - */ - void DeleteHPRec( hplist_node * pNode ); - - /// Permanently deletes retired pointer \p p - /** - Caveat: for performance reason this function is defined as inline and cannot be called directly - */ - void DeletePtr( details::retired_ptr& p ); - - //@cond - void detachAllThread(); - //@endcond - - public: - /// Creates GarbageCollector singleton - /** - GC is the singleton. If GC instance is not exist then the function creates the instance. - Otherwise it does nothing. - - The Michael's HP reclamation schema depends of three parameters: - - \p nHazardPtrCount - HP pointer count per thread. Usually it is small number (2-4) depending from - the data structure algorithms. By default, if \p nHazardPtrCount = 0, - the function uses maximum of HP count for CDS library. - - \p nMaxThreadCount - max count of thread with using HP GC in your application. Default is 100. - - \p nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than - \p nHazardPtrCount * \p nMaxThreadCount. - Default is 2 * \p nHazardPtrCount * \p nMaxThreadCount. - */ - static void CDS_STDCALL Construct( - size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread - size_t nMaxThreadCount = 0, ///< Max count of simultaneous working thread in your application - size_t nMaxRetiredPtrCount = 0, ///< Capacity of the array of retired objects for the thread - scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum) - ); - - /// Destroys global instance of GarbageCollector - /** - The parameter \p bDetachAll should be used carefully: if its value is \p true, - then the destroying GC automatically detaches all attached threads. This feature - can be useful when you have no control over the thread termination, for example, - when \p libcds is injected into existing external thread. - */ - static void CDS_STDCALL Destruct( - bool bDetachAll = false ///< Detach all threads - ); - - /// Returns pointer to GarbageCollector instance - static GarbageCollector& instance() - { - if ( !m_pHZPManager ) - throw HZPManagerEmpty(); - return *m_pHZPManager; - } - - /// Checks if global GC object is constructed and may be used - static bool isUsed() - { - return m_pHZPManager != nullptr; - } - - /// Returns max Hazard Pointer count defined in construction time - size_t getHazardPointerCount() const { return m_nHazardPointerCount; } - - /// Returns max thread count defined in construction time - size_t getMaxThreadCount() const { return m_nMaxThreadCount; } - - /// Returns max size of retired objects array. It is defined in construction time - size_t getMaxRetiredPtrCount() const { return m_nMaxRetiredPtrCount; } - - // Internal statistics - - /// Get internal statistics - InternalState& getInternalState(InternalState& stat) const; - - /// Checks if internal statistics enabled - bool isStatisticsEnabled() const { return m_bStatEnabled; } - - /// Enables/disables internal statistics - bool enableStatistics( bool bEnable ) - { - bool bEnabled = m_bStatEnabled; - m_bStatEnabled = bEnable; - return bEnabled; - } - - /// 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 HZPTooMany(); - } - - /// Get current scan strategy - scan_type getScanType() const - { - return m_nScanType; - } - - /// Set current scan strategy - /** @anchor hzp_gc_setScanType - Scan strategy changing is allowed on the fly. - */ - void setScanType( - scan_type nScanType ///< new scan strategy - ) - { - m_nScanType = nScanType; - } - - public: // Internals for threads - - /// Allocates Hazard Pointer GC record. For internal use only - details::HPRec * AllocateHPRec(); - - /// Free HP record. For internal use only - void RetireHPRec( details::HPRec * pRec ); - - /// The main garbage collecting function - /** - This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers - is reached. - - There are the following scan algorithm: - - \ref hzp_gc_classic_scan "classic_scan" allocates memory for internal use - - \ref hzp_gc_inplace_scan "inplace_scan" does not allocate any memory - - Use \ref hzp_gc_setScanType "setScanType" member function to setup appropriate scan algorithm. - */ - void Scan( details::HPRec * pRec ) - { - switch ( m_nScanType ) { - case inplace: - inplace_scan( pRec ); - break; - default: - assert(false) ; // Forgotten something?.. - case classic: - classic_scan( pRec ); - break; - } - } - - /// Helper scan routine - /** - The function guarantees that every node that is eligible for reuse is eventually freed, barring - thread failures. To do so, after executing Scan, a thread executes a HelpScan, - where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers - to thread's list of reclaimed pointers. - - The function is called internally by Scan. - */ - void HelpScan( details::HPRec * pThis ); - - protected: - /// Classic scan algorithm - /** @anchor hzp_gc_classic_scan - Classical scan algorithm as described in Michael's paper. - - A scan includes four stages. The first stage involves scanning the array HP for non-null values. - Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer. - Only stage 1 accesses shared variables. The following stages operate only on private variables. - - The second stage of a scan involves sorting local list of protected pointers to allow - binary search in the third stage. - - The third stage of a scan involves checking each reclaimed node - against the pointers in local list of protected pointers. If the binary search yields - no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list - of reclaimed pointers. - - The forth stage prepares new thread's private list of reclaimed pointers - that could not be freed during the current scan, where they remain until the next scan. - - This algorithm allocates memory for internal HP array. - - This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers - is reached. - */ - void classic_scan( details::HPRec * pRec ); - - /// In-place scan algorithm - /** @anchor hzp_gc_inplace_scan - Unlike the \ref hzp_gc_classic_scan "classic_scan" algorithm, \p inplace_scan does not allocate any memory. - All operations are performed in-place. - */ - void inplace_scan( details::HPRec * pRec ); - }; - - /// Thread's hazard pointer manager - /** - To use Hazard Pointer 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 \ref cds_threading "cds::threading::Manager::attachThread()" - on the start of each thread that uses HP GC. Before terminating the thread linked to HP GC it is necessary to call - \ref cds_threading "cds::threading::Manager::detachThread()". - */ - class ThreadGC - { - GarbageCollector& m_HzpManager ; ///< Hazard Pointer GC singleton - details::HPRec * m_pHzpRec ; ///< Pointer to thread's HZP record - - public: - /// Default constructor - ThreadGC() - : m_HzpManager( GarbageCollector::instance() ), - m_pHzpRec( nullptr ) - {} - - /// The object is not copy-constructible - ThreadGC( ThreadGC const& ) = delete; - - ~ThreadGC() - { - fini(); - } - - /// Checks if thread GC is initialized - bool isInitialized() const { return m_pHzpRec != nullptr; } - - /// Initialization. Repeat call is available - void init() - { - if ( !m_pHzpRec ) - m_pHzpRec = m_HzpManager.AllocateHPRec(); - } - - /// Finalization. Repeat call is available - void fini() - { - if ( m_pHzpRec ) { - details::HPRec * pRec = m_pHzpRec; - m_pHzpRec = nullptr; - m_HzpManager.RetireHPRec( pRec ); - } - } - - /// Initializes HP guard \p guard - details::HPGuard& allocGuard() - { - assert( m_pHzpRec ); - return m_pHzpRec->m_hzp.alloc(); - } - - /// Frees HP guard \p guard - void freeGuard( details::HPGuard& guard ) - { - assert( m_pHzpRec ); - m_pHzpRec->m_hzp.free( guard ); - } - - /// Initializes HP guard array \p arr - template - void allocGuard( details::HPArray& arr ) - { - assert( m_pHzpRec ); - m_pHzpRec->m_hzp.alloc( arr ); - } - - /// Frees HP guard array \p arr - template - void freeGuard( details::HPArray& arr ) - { - assert( m_pHzpRec ); - m_pHzpRec->m_hzp.free( arr ); - } - - /// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation - template - void retirePtr( T * p, void (* pFunc)(T *) ) - { - retirePtr( details::retired_ptr( reinterpret_cast( p ), reinterpret_cast( pFunc ) ) ); - } - - /// Places retired pointer \p into thread's array of retired pointer for deferred reclamation - void retirePtr( const details::retired_ptr& p ) - { - m_pHzpRec->m_arrRetired.push( p ); - - if ( m_pHzpRec->m_arrRetired.isFull() ) { - // Max of retired pointer count is reached. Do scan - scan(); - } - } - - //@cond - void scan() - { - m_HzpManager.Scan( m_pHzpRec ); - m_HzpManager.HelpScan( m_pHzpRec ); - } - //@endcond - }; - - /// Auto HPGuard. - /** - This class encapsulates Hazard Pointer guard to protect a pointer against deletion . - It allocates one HP from thread's HP array in constructor and free the HP allocated in destruction time. - */ - class AutoHPGuard - { - //@cond - details::HPGuard& m_hp ; ///< Hazard pointer guarded - ThreadGC& m_gc ; ///< Thread GC - //@endcond - - public: - typedef details::HPGuard::hazard_ptr hazard_ptr ; ///< Hazard pointer type - public: - /// Allocates HP guard from \p gc - AutoHPGuard( ThreadGC& gc ) - : m_hp( gc.allocGuard() ) - , m_gc( gc ) - {} - - /// Allocates HP guard from \p gc and protects the pointer \p p of type \p T - template - AutoHPGuard( ThreadGC& gc, T * p ) - : m_hp( gc.allocGuard() ) - , m_gc( gc ) - { - m_hp = p; - } - - /// Frees HP guard. The pointer guarded may be deleted after this. - ~AutoHPGuard() - { - m_gc.freeGuard( m_hp ); - } - - /// Returns thread GC - ThreadGC& getGC() const - { - return m_gc; - } - - /// Protects the pointer \p p against reclamation (guards the pointer). - template - T * operator =( T * p ) - { - return m_hp = p; - } - - //@cond - std::nullptr_t operator =(std::nullptr_t) - { - return m_hp = nullptr; - } - - hazard_ptr get() const - { - return m_hp; - } - //@endcond - }; - - /// Auto-managed array of hazard pointers - /** - This class is wrapper around cds::gc::hzp::details::HPArray class. - \p Count is the size of HP array - */ - template - class AutoHPArray: public details::HPArray - { - ThreadGC& m_mgr ; ///< Thread GC - - public: - /// Rebind array for other size \p COUNT2 - template - struct rebind { - typedef AutoHPArray other ; ///< rebinding result - }; - - 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 hzp -}} // namespace cds::gc - -// Inlines -#include - -#if CDS_COMPILER == CDS_COMPILER_MSVC -# pragma warning(pop) -#endif - -#endif // #ifndef __CDS_GC_HZP_HZP_H diff --git a/cds/gc/ptb.h b/cds/gc/ptb.h deleted file mode 100644 index 8096695d..00000000 --- a/cds/gc/ptb.h +++ /dev/null @@ -1,10 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_PTB_H -#define __CDS_GC_PTB_H - -#include -#include -#include - -#endif // #ifndef __CDS_GC_PTB_H diff --git a/cds/gc/ptb_decl.h b/cds/gc/ptb_decl.h deleted file mode 100644 index 34feb395..00000000 --- a/cds/gc/ptb_decl.h +++ /dev/null @@ -1,421 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_PTB_DECL_H -#define __CDS_GC_PTB_DECL_H - -#include -#include -#include - -namespace cds { namespace gc { - - /// Pass-the-Buck garbage collector - /** @ingroup cds_garbage_collector - @headerfile cds/gc/ptb.h - This class is a wrapper for Pass-the-Buck garbage collector internal implementation. - - Sources: - - [2002] M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting - dynamic-sized lockfree data structures. Technical Report TR-2002-112, Sun Microsystems Laboratories, 2002 - - [2002] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Dynamic-sized Lockfree Data Structures. - Technical Report TR-2002-110, Sun Microsystems Laboratories, 2002 - - [2005] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking Memory Management Support - for Dynamic_Sized Data Structures. ACM Transactions on Computer Systems, Vol.23, No.2, May 2005 - - See \ref cds_how_to_use "How to use" section for details of garbage collector applying. - */ - class PTB - { - public: - /// Native guarded pointer type - typedef void * guarded_pointer; - - /// Atomic reference - /** - @headerfile cds/gc/ptb.h - */ - template using atomic_ref = atomics::atomic; - - /// Atomic type - /** - @headerfile cds/gc/ptb.h - */ - template using atomic_type = atomics::atomic; - - /// Atomic marked pointer - /** - @headerfile cds/gc/ptb.h - */ - template using atomic_marked_ptr = atomics::atomic; - - /// Thread GC implementation for internal usage - typedef ptb::ThreadGC thread_gc_impl; - - /// Wrapper for ptb::ThreadGC class - /** - @headerfile cds/gc/ptb.h - This class performs automatically attaching/detaching Pass-the-Buck 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 Pass-the-Buck 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 Pass-the-Buck GC. - - \p false (default) - the class destructor will detach the thread from Pass-the-Buck GC. - */ - thread_gc( - bool bPersistent = false - ) ; // inline in ptb_impl.h - - /// Destructor - /** - If the object has been created in persistent mode, the destructor does nothing. - Otherwise it detaches the current thread from Pass-the-Buck GC. - */ - ~thread_gc() ; // inline in ptb_impl.h - }; - - - /// Pass-the-Buck guard - /** - @headerfile cds/gc/ptb.h - This class is a wrapper for ptb::Guard. - */ - class Guard: public ptb::Guard - { - //@cond - typedef ptb::Guard base_class; - //@endcond - - public: - //@cond - Guard() ; // inline in ptb_impl.h - //@endcond - - /// Protects a pointer of type atomic - /** - 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( atomics::atomic 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 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( atomics::atomic 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; - } - - /// Store \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); - } - - //@cond - std::nullptr_t assign( std::nullptr_t ) - { - return base_class::operator =(nullptr); - } - //@endcond - - /// 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( 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 (relaxed read) - template - T * get() const - { - return reinterpret_cast( get_native() ); - } - - /// Get native guarded pointer stored - guarded_pointer get_native() const - { - return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed); - } - - }; - - /// Array of Pass-the-Buck guards - /** - @headerfile cds/gc/ptb.h - This class is a wrapper for ptb::GuardArray template. - Template parameter \p Count defines the size of PTB array. - */ - template - class GuardArray: public ptb::GuardArray - { - //@cond - typedef ptb::GuardArray base_class; - //@endcond - public: - /// Rebind array for other size \p COUNT2 - template - struct rebind { - typedef GuardArray other ; ///< rebinding result - }; - - public: - //@cond - GuardArray() ; // inline in ptb_impl.h - //@endcond - - /// 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 - */ - template - T protect(size_t nIndex, atomics::atomic const& toGuard ) - { - T pRet; - do { - pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) ); - } while ( pRet != toGuard.load(atomics::memory_order_acquire)); - - return pRet; - } - - /// 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, atomics::atomic 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; - } - - /// 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 assign( 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 reinterpret_cast( get_native( nIndex ) ); - } - - /// Get native guarded pointer stored - guarded_pointer get_native( size_t nIndex ) const - { - return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed); - } - - /// Capacity of the guard array - static CDS_CONSTEXPR size_t capacity() - { - return Count; - } - }; - - public: - /// Initializes ptb::GarbageCollector singleton - /** - The constructor calls GarbageCollector::Construct with passed parameters. - See ptb::GarbageCollector::Construct for explanation of parameters meaning. - */ - PTB( - size_t nLiberateThreshold = 1024 - , size_t nInitialThreadGuardCount = 8 - ) - { - ptb::GarbageCollector::Construct( - nLiberateThreshold, - nInitialThreadGuardCount - ); - } - - /// Terminates ptb::GarbageCollector singleton - /** - The destructor calls \code ptb::GarbageCollector::Destruct() \endcode - */ - ~PTB() - { - ptb::GarbageCollector::Destruct(); - } - - /// Checks if count of hazard pointer is no less than \p nCountNeeded - /** - The function always returns \p true since the guard count is unlimited for - PTB garbage collector. - */ - static bool check_available_guards( size_t nCountNeeded, bool /*bRaiseException*/ = true ) - { - CDS_UNUSED( nCountNeeded ); - 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 *) ) - { - ptb::GarbageCollector::instance().retirePtr( p, pFunc ); - } - - /// 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 guarded pointer points to it. - - See gc::HP::retire for \p Disposer requirements. - */ - template - static void retire( T * p ) - { - retire( p, cds::details::static_functor::call ); - } - - /// Checks if Pass-the-Buck GC is constructed and may be used - static bool isUsed() - { - return ptb::GarbageCollector::isUsed(); - } - - /// Forced GC cycle call for current thread - /** - Usually, this function should not be called directly. - */ - static void scan() ; // inline in ptb_impl.h - - /// Synonym for \ref scan() - static void force_dispose() - { - scan(); - } - }; - -}} // namespace cds::gc - -#endif // #ifndef __CDS_GC_PTB_DECL_H diff --git a/cds/gc/ptb_impl.h b/cds/gc/ptb_impl.h deleted file mode 100644 index 201564cf..00000000 --- a/cds/gc/ptb_impl.h +++ /dev/null @@ -1,43 +0,0 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_PTB_IMPL_H -#define __CDS_GC_PTB_IMPL_H - -#include - -//@cond -namespace cds { namespace gc { - - inline PTB::thread_gc::thread_gc( - bool bPersistent - ) - : m_bPersistent( bPersistent ) - { - if ( !cds::threading::Manager::isThreadAttached() ) - cds::threading::Manager::attachThread(); - } - - inline PTB::thread_gc::~thread_gc() - { - if ( !m_bPersistent ) - cds::threading::Manager::detachThread(); - } - - inline PTB::Guard::Guard() - : Guard::base_class( cds::threading::getGC() ) - {} - - template - inline PTB::GuardArray::GuardArray() - : GuardArray::base_class( cds::threading::getGC() ) - {} - - inline void PTB::scan() - { - cds::threading::getGC().scan(); - } - -}} // namespace cds::gc -//@endcond - -#endif // #ifndef __CDS_GC_PTB_IMPL_H diff --git a/cds/threading/details/_common.h b/cds/threading/details/_common.h index 619a01f2..b31823a4 100644 --- a/cds/threading/details/_common.h +++ b/cds/threading/details/_common.h @@ -4,7 +4,7 @@ #define __CDS_THREADING__COMMON_H #include -#include +#include #include #include diff --git a/projects/Win/vc12/cds.vcxproj b/projects/Win/vc12/cds.vcxproj index 70e78e5c..d242c1e1 100644 --- a/projects/Win/vc12/cds.vcxproj +++ b/projects/Win/vc12/cds.vcxproj @@ -735,12 +735,18 @@ + + + + + + + + - - @@ -831,13 +837,6 @@ - - - - - - - diff --git a/projects/Win/vc12/cds.vcxproj.filters b/projects/Win/vc12/cds.vcxproj.filters index b9dcf1e0..75906e30 100644 --- a/projects/Win/vc12/cds.vcxproj.filters +++ b/projects/Win/vc12/cds.vcxproj.filters @@ -18,9 +18,6 @@ {a3c9928d-5261-4593-a8b9-728235f7056f} - - {21a6c665-7381-45b8-9f03-b21f3da5503d} - {53d28ee4-5fe9-4fa1-a617-53d8b0628eac} @@ -154,6 +151,9 @@ {0a2328b4-ff6f-4afb-8de0-9884ae172fa9} + + {043c4eba-3bd4-4226-b214-e26f18b422a1} + @@ -248,27 +248,6 @@ Header Files\cds\gc - - Header Files\cds\gc - - - Header Files\cds\gc\hzp - - - Header Files\cds\gc\hzp - - - Header Files\cds\gc\hzp - - - Header Files\cds\gc\hzp - - - Header Files\cds\gc\hzp - - - Header Files\cds\gc\hzp - Header Files\cds\gc\ptb @@ -665,12 +644,6 @@ Header Files\cds\gc - - Header Files\cds\gc - - - Header Files\cds\gc - Header Files\cds\compiler @@ -1157,9 +1130,6 @@ Header Files\cds\container\details - - Header Files\cds\gc - Header Files\cds\container @@ -1196,5 +1166,32 @@ Header Files\cds\container + + Header Files\cds\gc + + + Header Files\cds\gc + + + Header Files\cds\gc + + + Header Files\cds\gc\hp + + + Header Files\cds\gc\hp + + + Header Files\cds\gc\hp + + + Header Files\cds\gc\hp + + + Header Files\cds\gc\hp + + + Header Files\cds\gc\hp + \ No newline at end of file diff --git a/src/hzp_gc.cpp b/src/hzp_gc.cpp index e171fbcc..a8bb004d 100644 --- a/src/hzp_gc.cpp +++ b/src/hzp_gc.cpp @@ -9,7 +9,7 @@ 2008.02.10 Maxim.Khiszinsky Created */ -#include +#include #include // std::sort #include "hzp_const.h" diff --git a/tests/cppunit/test_main.cpp b/tests/cppunit/test_main.cpp index 3ae3362c..452c0503 100644 --- a/tests/cppunit/test_main.cpp +++ b/tests/cppunit/test_main.cpp @@ -28,7 +28,7 @@ #include #include -#include +#include #include #include #include