-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
-#ifndef __CDS_GC_DETAILS_HP_H
-#define __CDS_GC_DETAILS_HP_H
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
-#include <cds/cxx11_atomic.h>
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_GC_DETAILS_HP_H
+#define CDSLIB_GC_DETAILS_HP_H
+
+#include <cds/algo/atomic.h>
#include <cds/os/thread.h>
#include <cds/details/bounded_array.h>
+#include <cds/user_setup/cache_line.h>
#include <cds/gc/details/hp_type.h>
#include <cds/gc/details/hp_alloc.h>
2010.01.27 khizmax Introducing memory order constraint
*/
+//@cond
namespace cds {
- /**
- @page cds_garbage_collectors_comparison GC comparison
- @ingroup cds_garbage_collector
-
- <table>
- <tr>
- <th>Feature</th>
- <th>%cds::gc::HP</th>
- <th>%cds::gc::DHP</th>
- </tr>
- <tr>
- <td>Implementation quality</td>
- <td>stable</td>
- <td>stable</td>
- </tr>
- <tr>
- <td>Performance rank (1 - slowest, 5 - fastest)</td>
- <td>5</td>
- <td>4</td>
- </tr>
- <tr>
- <td>Max number of guarded (hazard) pointers per thread</td>
- <td>limited (specifies in GC object ctor)</td>
- <td>unlimited (dynamically allocated when needed)</td>
- </tr>
- <tr>
- <td>Max number of retired pointers<sup>1</sup></td>
- <td>bounded</td>
- <td>bounded</td>
- </tr>
- <tr>
- <td>Array of retired pointers</td>
- <td>preallocated for each thread, limited in size</td>
- <td>global for the entire process, unlimited (dynamically allocated when needed)</td>
- </tr>
- <tr>
- <td>Support direct pointer to item of lock-free container (useful for iterators)</td>
- <td>not supported</td>
- <td>not supported</td>
- </tr>
- </table>
-
- <sup>1</sup>Unbounded count of retired pointer means a possibility of memory exhaustion.
- */
-
/// Different safe memory reclamation schemas (garbage collectors)
/** @ingroup cds_garbage_collector
public:
/// Iterator
- typedef retired_vector_impl::iterator iterator;
+ typedef retired_vector_impl::iterator iterator;
/// Constructor
- retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr ) CDS_NOEXCEPT; // inline
+ retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
~retired_vector()
{}
The capacity is constant for any thread. It is defined by cds::gc::hp::GarbageCollector.
*/
size_t capacity() const CDS_NOEXCEPT
- {
- return m_arr.capacity();
+ {
+ return m_arr.capacity();
}
/// Current vector size (count of retired pointers in the vector)
size_t size() const CDS_NOEXCEPT
- {
- return m_nSize;
+ {
+ return m_nSize;
}
/// Set vector size. Uses internally
void size( size_t nSize )
{
- assert( nSize <= capacity() );
+ assert( nSize <= capacity());
m_nSize = nSize;
}
/// Pushes retired pointer to the vector
- void push( const retired_ptr& p )
+ void push( retired_ptr const& p )
{
- assert( m_nSize < capacity() );
+ assert( m_nSize < capacity());
m_arr[ m_nSize ] = p;
++m_nSize;
}
- /// Checks if the vector is full (size() == capacity() )
+ /// Checks if the vector is full (size() == capacity())
bool isFull() const CDS_NOEXCEPT
{
return m_nSize >= capacity();
/// Begin iterator
iterator begin() CDS_NOEXCEPT
- {
- return m_arr.begin();
+ {
+ return m_arr.begin();
}
/// End iterator
iterator end() CDS_NOEXCEPT
- {
- return m_arr.begin() + m_nSize ;
+ {
+ return m_arr.begin() + m_nSize;
}
/// Clears the vector. After clearing, size() == 0
other threads have read-only access.
*/
struct hp_record {
- hp_allocator<> m_hzp; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency
+ hp_allocator<> m_hzp; ///< array of hazard pointers. Implicit \ref CDS_DEFAULT_ALLOCATOR dependency
retired_vector m_arrRetired ; ///< Retired pointer array
+ char padding[cds::c_nCacheLineSize];
+ atomics::atomic<unsigned int> m_nSync; ///< dummy var to introduce synchronizes-with relationship between threads
+ char padding2[cds::c_nCacheLineSize];
+
/// Ctor
- hp_record( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
+ hp_record( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
~hp_record()
{}
{
m_hzp.clear();
}
+
+ void sync()
+ {
+ m_nSync.fetch_add( 1, atomics::memory_order_acq_rel );
+ }
};
} // namespace details
};
/// No GarbageCollector object is created
- CDS_DECLARE_EXCEPTION( HZPManagerEmpty, "Global Hazard Pointer GarbageCollector is NULL" );
+ class not_initialized : public std::runtime_error
+ {
+ public:
+ //@cond
+ not_initialized()
+ : std::runtime_error( "Global Hazard Pointer GarbageCollector is not initialized" )
+ {}
+ //@endcond
+ };
- /// Not enough required Hazard Pointer count
- CDS_DECLARE_EXCEPTION( HZPTooMany, "Not enough required Hazard Pointer count" );
+ /// Not enough Hazard Pointer
+ class too_many_hazard_ptr : public std::length_error
+ {
+ public:
+ //@cond
+ too_many_hazard_ptr()
+ : std::length_error( "Not enough Hazard Pointer" )
+ {}
+ //@endcond
+ };
private:
/// Internal GC statistics
/// Internal list of cds::gc::hp::details::hp_record
struct hplist_node : public details::hp_record
{
- hplist_node * m_pNextNode ; ///< next hazard ptr record in list
- atomics::atomic<OS::ThreadId> m_idOwner ; ///< Owner thread id; 0 - the record is free (not owned)
- atomics::atomic<bool> m_bFree ; ///< true if record if free (not owned)
+ hplist_node * m_pNextNode; ///< next hazard ptr record in list
+ atomics::atomic<OS::ThreadId> m_idOwner; ///< Owner thread id; 0 - the record is free (not owned)
+ atomics::atomic<bool> m_bFree; ///< true if record if free (not owned)
//@cond
hplist_node( const GarbageCollector& HzpMgr )
~hplist_node()
{
assert( m_idOwner.load( atomics::memory_order_relaxed ) == OS::c_NullThreadId );
- assert( m_bFree.load(atomics::memory_order_relaxed) );
+ assert( m_bFree.load(atomics::memory_order_relaxed));
}
//@endcond
};
*/
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
static GarbageCollector& instance()
{
if ( !m_pHZPManager )
- throw HZPManagerEmpty();
+ throw not_initialized();
return *m_pHZPManager;
}
/// Returns max Hazard Pointer count defined in construction time
size_t getHazardPointerCount() const CDS_NOEXCEPT
- {
- return m_nHazardPointerCount;
+ {
+ return m_nHazardPointerCount;
}
/// Returns max thread count defined in construction time
size_t getMaxThreadCount() const CDS_NOEXCEPT
- {
- return m_nMaxThreadCount;
+ {
+ return m_nMaxThreadCount;
}
/// Returns max size of retired objects array. It is defined in construction time
size_t getMaxRetiredPtrCount() const CDS_NOEXCEPT
- {
- return m_nMaxRetiredPtrCount;
+ {
+ return m_nMaxRetiredPtrCount;
}
// Internal statistics
/// 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
+ If \p nRequiredCount > getHazardPointerCount() then the exception \p too_many_hazard_ptr is thrown
*/
static void checkHPCount( unsigned int nRequiredCount )
{
if ( instance().getHazardPointerCount() < nRequiredCount )
- throw HZPTooMany();
+ throw too_many_hazard_ptr();
}
/// Get current scan strategy
public: // Internals for threads
/// Allocates Hazard Pointer GC record. For internal use only
- details::hp_record * alloc_hp_record();
+ details::hp_record* alloc_hp_record();
/// Free HP record. For internal use only
- void free_hp_record( details::hp_record * pRec );
+ void free_hp_record( details::hp_record* pRec );
/// The main garbage collecting function
/**
*/
class ThreadGC
{
- GarbageCollector& m_HzpManager; ///< Hazard Pointer GC singleton
- details::hp_record * m_pHzpRec; ///< Pointer to thread's HZP record
+ GarbageCollector& m_HzpManager; ///< Hazard Pointer GC singleton
+ details::hp_record* m_pHzpRec; ///< Pointer to thread's HZP record
public:
/// Default constructor
ThreadGC()
- : m_HzpManager( GarbageCollector::instance() ),
+ : m_HzpManager( GarbageCollector::instance()),
m_pHzpRec( nullptr )
{}
}
/// Checks if thread GC is initialized
- bool isInitialized() const { return m_pHzpRec != nullptr; }
+ bool isInitialized() const { return m_pHzpRec != nullptr; }
/// Initialization. Repeat call is available
void init()
void fini()
{
if ( m_pHzpRec ) {
- details::hp_record * pRec = m_pHzpRec;
+ details::hp_record* pRec = m_pHzpRec;
m_pHzpRec = nullptr;
m_HzpManager.free_hp_record( pRec );
}
}
/// Initializes HP guard \p guard
- details::hp_guard& allocGuard()
+ details::hp_guard* allocGuard()
{
assert( m_pHzpRec );
return m_pHzpRec->m_hzp.alloc();
}
/// Frees HP guard \p guard
- void freeGuard( details::hp_guard& guard )
+ void freeGuard( details::hp_guard* guard )
{
assert( m_pHzpRec );
m_pHzpRec->m_hzp.free( guard );
/// Initializes HP guard array \p arr
template <size_t Count>
- void allocGuard( details::hp_array<Count>& arr )
+ size_t allocGuard( details::hp_array<Count>& arr )
{
assert( m_pHzpRec );
- m_pHzpRec->m_hzp.alloc( arr );
+ return m_pHzpRec->m_hzp.alloc( arr );
}
/// Frees HP guard array \p arr
/// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
template <typename T>
- void retirePtr( T * p, void (* pFunc)(T *) )
+ void retirePtr( T * p, void (* pFunc)(T *))
{
- /*
- union {
- T * p;
- hazard_pointer hp;
- } cast_ptr;
- cast_ptr.p = p;
-
- uinion{
- void( *pFunc )(T *);
- free_retired_ptr_func hpFunc;
- } cast_func;
- cast_func.pFunc = pFunc;
-
- retirePtr( details::retired_ptr( cast_ptr.hp, cast_func.hpFunc ) );
- */
- retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc ) ) );
+ retirePtr( details::retired_ptr( reinterpret_cast<void *>( p ), reinterpret_cast<free_retired_ptr_func>( pFunc )));
}
/// Places retired pointer \p into thread's array of retired pointer for deferred reclamation
{
m_pHzpRec->m_arrRetired.push( p );
- if ( m_pHzpRec->m_arrRetired.isFull() ) {
+ if ( m_pHzpRec->m_arrRetired.isFull()) {
// Max of retired pointer count is reached. Do scan
scan();
}
}
- //@cond
+ /// Run retiring scan cycle
void scan()
{
m_HzpManager.Scan( m_pHzpRec );
m_HzpManager.HelpScan( m_pHzpRec );
}
- //@endcond
- };
-
- /// Auto hp_guard.
- /**
- 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 hazard pointer allocated
- in destructor.
- */
- class guard
- {
- //@cond
- details::hp_guard& m_hp ; ///< Hazard pointer guarded
- ThreadGC& m_gc ; ///< Thread GC
- //@endcond
-
- public:
- typedef details::hp_guard::hazard_ptr hazard_ptr ; ///< Hazard pointer type
- public:
- /// Allocates HP guard from \p gc
- guard( 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 <typename T>
- guard( 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.
- ~guard()
- {
- 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 <typename T>
- T * operator =( T * p )
- {
- return m_hp = p;
- }
-
- //@cond
- std::nullptr_t operator =(std::nullptr_t)
- {
- return m_hp = nullptr;
- }
- hazard_ptr get() const
+ void sync()
{
- return m_hp;
+ assert( m_pHzpRec != nullptr );
+ m_pHzpRec->sync();
}
- //@endcond
};
- /// Auto-managed array of hazard pointers
- /**
- This class is wrapper around cds::gc::hp::details::hp_array class.
- \p Count is the size of HP array
- */
- template <size_t Count>
- class array : public details::hp_array<Count>
- {
- ThreadGC& m_mgr ; ///< Thread GC
-
- public:
- /// Rebind array for other size \p COUNT2
- template <size_t Count2>
- struct rebind {
- typedef array<Count2> other; ///< rebinding result
- };
+ } // namespace hp
+}} // namespace cds::gc
+//@endcond
- public:
- /// Allocates array of HP guard from \p mgr
- array( ThreadGC& mgr )
- : m_mgr( mgr )
- {
- mgr.allocGuard( *this );
- }
+//@cond
+// Inlines
+namespace cds {
+ namespace gc { namespace hp { namespace details {
- /// Frees array of HP guard
- ~array()
- {
- m_mgr.freeGuard( *this );
- }
+ inline retired_vector::retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr )
+ : m_arr( HzpMgr.getMaxRetiredPtrCount()),
+ m_nSize(0)
+ {}
- /// Returns thread GC
- ThreadGC& getGC() const { return m_mgr; }
- };
+ inline hp_record::hp_record( const cds::gc::hp::GarbageCollector& HzpMgr )
+ : m_hzp( HzpMgr.getHazardPointerCount())
+ , m_arrRetired( HzpMgr )
+ , m_nSync( 0 )
+ {}
- } // namespace hp
-}} // namespace cds::gc
+ }}} // namespace gc::hp::details
+} // namespace cds
+//@endcond
-// Inlines
-#include <cds/gc/details/hp_inline.h>
#if CDS_COMPILER == CDS_COMPILER_MSVC
# pragma warning(pop)
#endif
-#endif // #ifndef __CDS_GC_DETAILS_HP_H
+#endif // #ifndef CDSLIB_GC_DETAILS_HP_H
projects / libcds.git / blobdiff