@note Do not include <tt><cds/container/impl/ellen_bintree_map.h></tt> header file directly.
There are header file for each GC type:
- <tt><cds/container/ellen_bintree_map_hp.h></tt> - for Hazard Pointer GC cds::gc::HP
- - <tt><cds/container/ellen_bintree_map_dhp.h></tt> - for Pass-the-Buck GC cds::gc::DHP
+ - <tt><cds/container/ellen_bintree_map_dhp.h></tt> - for Dynamic Hazard Pointer GC cds::gc::DHP
- <tt><cds/container/ellen_bintree_map_rcu.h></tt> - for RCU GC
(see \ref cds_container_EllenBinTreeMap_rcu "RCU-based EllenBinTreeMap")
*/
before end of the map. Therefore, such iteration is more suitable for debugging purpose only
Remember, each iterator object requires 2 additional hazard pointers, that may be
- a limited resource for \p GC like \p gc::HP (for gc::PTB the count of
+ a limited resource for \p GC like \p gc::HP (for gc::DHP the count of
guards is unlimited).
The iterator class supports the following minimalistic interface:
before end of the set. Therefore, such iteration is more suitable for debugging purpose only
Remember, each iterator object requires 2 additional hazard pointers, that may be
- a limited resource for \p GC like \p gc::HP (for \p gc::PTB the count of
+ a limited resource for \p GC like \p gc::HP (for \p gc::DHP the count of
guards is unlimited).
The iterator class supports the following minimalistic interface:
quasi factor. It means that the consumer dequeues any item from the current first segment.
Template parameters:
- - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::PTB
+ - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::DHP
- \p T - the type of values stored in the queue
- \p Traits - queue type traits, default is \p segmented_queue::traits.
\p segmented_queue::make_traits metafunction can be used to construct your
//$$CDS-header$$
-#ifndef __CDS_CONTAINER_SKIP_LIST_MAP_PTB_H
-#define __CDS_CONTAINER_SKIP_LIST_MAP_PTB_H
+#ifndef __CDS_CONTAINER_SKIP_LIST_MAP_DHP_H
+#define __CDS_CONTAINER_SKIP_LIST_MAP_DHP_H
#include <cds/container/details/skip_list_base.h>
#include <cds/intrusive/skip_list_dhp.h>
#include <cds/container/details/make_skip_list_set.h>
#include <cds/container/impl/skip_list_set.h>
-#endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_PTB_H
+#endif // #ifndef __CDS_CONTAINER_SKIP_LIST_MAP_DHP_H
Now you are ready to declare our map class based on \p %SplitListMap:
\code
- typedef cc::SplitListMap< cds::gc::PTB, int, std::string, foo_set_traits > int_string_map;
+ typedef cc::SplitListMap< cds::gc::DHP, int, std::string, foo_set_traits > int_string_map;
\endcode
You may use the modern option-based declaration instead of classic type-traits-based one:
\code
typedef cc:SplitListMap<
- cs::gc::PTB // GC used
+ cs::gc::DHP // GC used
,int // key type
,std::string // value type
,cc::split_list::make_traits< // metafunction to build split-list traits
Now you are ready to declare our set class based on \p %SplitListSet:
\code
- typedef cc::SplitListSet< cds::gc::PTB, foo, foo_set_traits > foo_set;
+ typedef cc::SplitListSet< cds::gc::DHP, foo, foo_set_traits > foo_set;
\endcode
You may use the modern option-based declaration instead of classic traits-based one:
\code
typedef cc:SplitListSet<
- cs::gc::PTB // GC used
+ cs::gc::DHP // GC used
,foo // type of data stored
,cc::split_list::make_traits< // metafunction to build split-list traits
cc::split_list::ordered_list<cc::lazy_list_tag> // tag for underlying ordered list implementation
#include <cds/gc/dhp/dhp_impl.h>
#include <cds/details/lib.h>
-namespace cds { namespace gc {
- typedef PTB DHP;
-}} // namespace cds::gc
-
#endif // #ifndef __CDS_GC_DHP_H
namespace cds { namespace gc {
- /// Pass The Buck reclamation schema
+ /// Dynamic Hazard Pointer reclamation schema
/**
- \par 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
+ The cds::gc::dhp namespace and its members are internal representation of the GC and should not be used directly.
+ Use cds::gc::DHP class in your code.
-
- The cds::gc::ptb namespace and its members are internal representation of the Pass-the-Buck GC and should not be used directly.
- Use cds::gc::PTB class in your code.
-
- Pass-the-Buck (PTB) garbage collector is a singleton. The main user-level part of PTB schema is
- GC class and its nested classes. Before use any PTB-related class you must initialize PTB garbage collector
- by contructing cds::gc::PTB object in beginning of your main().
- See cds::gc::PTB class for explanation.
+ Dynamic Hazard Pointer (DHP) garbage collector is a singleton. The main user-level part of DHP schema is
+ GC class and its nested classes. Before use any DHP-related class you must initialize DHP garbage collector
+ by contructing cds::gc::DHP object in beginning of your main().
+ See cds::gc::DHP class for explanation.
\par Implementation issues
- The global list of free guards (cds::gc::ptb::details::guard_allocator) is protected by spin-lock (i.e. serialized).
- It seems that solution should not introduce significant performance bottleneck, because each thread has own set
- of guards allocated from global list of free guards and access to global list is occurred only when
- all thread's guard is busy. In this case the thread allocates next block of guards from global list.
+ The global list of free guards (\p cds::gc::dhp::details::guard_allocator) is protected by a spin-lock (i.e. serialized).
+ It seems that this solution should not introduce significant performance bottleneck, because each thread has its own set
+ of guards allocated from the global list of free guards and the access to the global list is occurred only when
+ all thread's guard is busy. In this case the thread allocates a next block of guards from the global list.
Guards allocated for the thread is push back to the global list only when the thread terminates.
*/
- namespace ptb {
+ namespace dhp {
// Forward declarations
class Guard;
using cds::gc::details::free_retired_ptr_func;
- /// Details of Pass the Buck algorithm
+ /// Details of Dynamic Hazard Pointer algorithm
namespace details {
// Forward declaration
/**
The list returned is linked by guard's \p pThreadNext and \p pNextFree fields.
- cds::gc::ptb::ThreadGC supporting method
+ cds::gc::dhp::ThreadGC supporting method
*/
guard_data * allocList( size_t nCount )
{
/**
The list \p pList is linked by guard's \p pThreadNext field.
- cds::gc::ptb::ThreadGC supporting method
+ cds::gc::dhp::ThreadGC supporting method
*/
void freeList( guard_data * pList )
{
return m_nItemCount.fetch_add( 1, atomics::memory_order_relaxed ) + 1;
}
- /// Result of \ref ptb_gc_privatve "privatize" function.
+ /// Result of \ref dhp_gc_privatve "privatize" function.
/**
The \p privatize function returns retired node list as \p first and the size of that list as \p second.
*/
typedef std::pair<retired_ptr_node *, size_t> privatize_result;
/// Gets current list of retired pointer and clears the list
- /**@anchor ptb_gc_privatve
+ /**@anchor dhp_gc_privatve
*/
privatize_result privatize()
{
public: // for ThreadGC.
/*
GCC cannot compile code for template versions of ThreasGC::allocGuard/freeGuard,
- the compiler produces error: \91cds::gc::ptb::details::guard_data* cds::gc::ptb::details::guard::m_pGuard\92 is protected
+ the compiler produces error: \91cds::gc::dhp::details::guard_data* cds::gc::dhp::details::guard::m_pGuard\92 is protected
despite the fact that ThreadGC is declared as friend for guard class.
We should not like to declare m_pGuard member as public one.
Therefore, we have to add set_guard/get_guard public functions
/// Returns guard allocated back to pool of free guards
~Guard(); // inline after GarbageCollector
- /// Returns PTB GC object
+ /// Returns DHP GC object
ThreadGC& getGC()
{
return m_gc;
return c_nCapacity;
}
- /// Returns PTB ThreadGC object
+ /// Returns DHP ThreadGC object
ThreadGC& getGC() CDS_NOEXCEPT
{
return m_gc;
public:
/// Exception "No GarbageCollector object is created"
- CDS_DECLARE_EXCEPTION( PTBManagerEmpty, "Global PTB GarbageCollector is NULL" );
+ CDS_DECLARE_EXCEPTION( DHPManagerEmpty, "Global DHP GarbageCollector is NULL" );
/// Internal GC statistics
struct InternalState
bool m_bStatEnabled ; ///< Internal Statistics enabled
public:
- /// Initializes PTB memory manager singleton
+ /// Initializes DHP memory manager singleton
/**
- This member function creates and initializes PTB global object.
- The function should be called before using CDS data structure based on cds::gc::PTB GC. Usually,
- this member function is called in the \p main() function. See cds::gc::ptb for example.
- After calling of this function you may use CDS data structures based on cds::gc::PTB.
+ This member function creates and initializes DHP global object.
+ The function should be called before using CDS data structure based on cds::gc::DHP GC. Usually,
+ this member function is called in the \p main() function. See cds::gc::dhp for example.
+ After calling of this function you may use CDS data structures based on cds::gc::DHP.
\par Parameters
\li \p nLiberateThreshold - the liberate threshold. When count of retired pointers reaches this value,
- the \ref ptb_gc_liberate "liberate" member function would be called for freeing retired pointers.
- If \p nLiberateThreshold <= 1, \p liberate would called after each \ref ptb_gc_retirePtr "retirePtr" call.
+ the \ref dhp_gc_liberate "liberate" member function would be called for freeing retired pointers.
+ If \p nLiberateThreshold <= 1, \p liberate would called after each \ref dhp_gc_retirePtr "retirePtr" call.
\li \p nInitialThreadGuardCount - initial count of guard allocated for ThreadGC. When a thread
is initialized the GC allocates local guard pool for the thread from common guard pool.
By perforce the local thread's guard pool is grown automatically from common pool.
, size_t nInitialThreadGuardCount = 8
);
- /// Destroys PTB memory manager
+ /// Destroys DHP memory manager
/**
- The member function destroys PTB global object. After calling of this function you may \b NOT
- use CDS data structures based on cds::gc::PTB. Usually, the \p Destruct function is called
- at the end of your \p main(). See cds::gc::ptb for example.
+ The member function destroys DHP global object. After calling of this function you may \b NOT
+ use CDS data structures based on cds::gc::DHP. Usually, the \p Destruct function is called
+ at the end of your \p main(). See cds::gc::dhp for example.
*/
static void CDS_STDCALL Destruct();
/// Returns pointer to GarbageCollector instance
/**
- If PTB GC is not initialized, \p PTBManagerEmpty exception is thrown
+ If DHP GC is not initialized, \p DHPManagerEmpty exception is thrown
*/
static GarbageCollector& instance()
{
if ( m_pManager == nullptr )
- throw PTBManagerEmpty();
+ throw DHPManagerEmpty();
return *m_pManager;
}
}
/// Places retired pointer \p and its deleter \p pFunc into thread's array of retired pointer for deferred reclamation
- /**@anchor ptb_gc_retirePtr
+ /**@anchor dhp_gc_retirePtr
*/
template <typename T>
void retirePtr( T * p, void (* pFunc)(T *) )
protected:
/// Liberate function
- /** @anchor ptb_gc_liberate
- The main function of Pass The Buck algorithm. It tries to free retired pointers if they are not
+ /** @anchor dhp_gc_liberate
+ The main function of Dynamic Hazard Pointer algorithm. It tries to free retired pointers if they are not
trapped by any guard.
*/
void liberate();
/// Thread GC
/**
- To use Pass The Buck reclamation schema each thread object must be linked with the object of ThreadGC class
+ To use Dynamic 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 PTB GC. Before terminating the thread linked to PTB GC it is necessary to call
+ on the start of each thread that uses DHP GC. Before terminating the thread linked to DHP GC it is necessary to call
\ref cds_threading "cds::threading::Manager::detachThread()".
The ThreadGC object maintains two list:
getGC().freeGuard( *this );
}
- } // namespace ptb
+ } // namespace dhp
}} // namespace cds::gc
#if CDS_COMPILER == CDS_COMPILER_MSVC
namespace cds { namespace gc {
- /// Pass-the-Buck garbage collector
+ /// Dynamic Hazard Pointer 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
+ This class is a wrapper for Dynamic Hazard Pointer garbage collector internal implementation.
See \ref cds_how_to_use "How to use" section for details of garbage collector applying.
*/
- class PTB
+ class DHP
{
public:
/// Native guarded pointer type
template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
/// Thread GC implementation for internal usage
- typedef ptb::ThreadGC thread_gc_impl;
+ typedef dhp::ThreadGC thread_gc_impl;
- /// Wrapper for ptb::ThreadGC class
+ /// Wrapper for dhp::ThreadGC class
/**
@headerfile cds/gc/dhp.h
- This class performs automatically attaching/detaching Pass-the-Buck GC
+ This class performs automatically attaching/detaching Dynamic Hazard Pointer GC
for the current thread.
*/
class thread_gc: public thread_gc_impl
public:
/// Constructor
/**
- The constructor attaches the current thread to the Pass-the-Buck GC
+ The constructor attaches the current thread to the Dynamic Hazard Pointer 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.
+ - \p true - the class destructor will not detach the thread from Dynamic Hazard Pointer GC.
+ - \p false (default) - the class destructor will detach the thread from Dynamic Hazard Pointer GC.
*/
thread_gc(
bool bPersistent = false
- ) ; // inline in ptb_impl.h
+ ) ; // inline in dhp_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.
+ Otherwise it detaches the current thread from Dynamic Hazard Pointer GC.
*/
- ~thread_gc() ; // inline in ptb_impl.h
+ ~thread_gc() ; // inline in dhp_impl.h
};
- /// Pass-the-Buck guard
+ /// Dynamic Hazard Pointer guard
/**
@headerfile cds/gc/dhp.h
- This class is a wrapper for ptb::Guard.
+ This class is a wrapper for dhp::Guard.
*/
- class Guard: public ptb::Guard
+ class Guard: public dhp::Guard
{
//@cond
- typedef ptb::Guard base_class;
+ typedef dhp::Guard base_class;
//@endcond
public:
//@cond
- Guard() ; // inline in ptb_impl.h
+ Guard() ; // inline in dhp_impl.h
//@endcond
/// Protects a pointer of type <tt> atomic<T*> </tt>
};
- /// Array of Pass-the-Buck guards
+ /// Array of Dynamic Hazard Pointer 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.
+ This class is a wrapper for dhp::GuardArray template.
+ Template parameter \p Count defines the size of DHP array.
*/
template <size_t Count>
- class GuardArray: public ptb::GuardArray<Count>
+ class GuardArray: public dhp::GuardArray<Count>
{
//@cond
- typedef ptb::GuardArray<Count> base_class;
+ typedef dhp::GuardArray<Count> base_class;
//@endcond
public:
/// Rebind array for other size \p COUNT2
public:
//@cond
- GuardArray() ; // inline in ptb_impl.h
+ GuardArray() ; // inline in dhp_impl.h
//@endcond
/// Protects a pointer of type \p atomic<T*>
};
public:
- /// Initializes ptb::GarbageCollector singleton
+ /// Initializes dhp::GarbageCollector singleton
/**
The constructor calls GarbageCollector::Construct with passed parameters.
- See ptb::GarbageCollector::Construct for explanation of parameters meaning.
+ See dhp::GarbageCollector::Construct for explanation of parameters meaning.
*/
- PTB(
+ DHP(
size_t nLiberateThreshold = 1024
, size_t nInitialThreadGuardCount = 8
)
{
- ptb::GarbageCollector::Construct(
+ dhp::GarbageCollector::Construct(
nLiberateThreshold,
nInitialThreadGuardCount
);
}
- /// Terminates ptb::GarbageCollector singleton
+ /// Terminates dhp::GarbageCollector singleton
/**
- The destructor calls \code ptb::GarbageCollector::Destruct() \endcode
+ The destructor calls \code dhp::GarbageCollector::Destruct() \endcode
*/
- ~PTB()
+ ~DHP()
{
- ptb::GarbageCollector::Destruct();
+ dhp::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.
+ DHP garbage collector.
*/
static bool check_available_guards( size_t nCountNeeded, bool /*bRaiseException*/ = true )
{
template <typename T>
static void retire( T * p, void (* pFunc)(T *) )
{
- ptb::GarbageCollector::instance().retirePtr( p, pFunc );
+ dhp::GarbageCollector::instance().retirePtr( p, pFunc );
}
/// Retire pointer \p p with functor of type \p Disposer
retire( p, cds::details::static_functor<Disposer, T>::call );
}
- /// Checks if Pass-the-Buck GC is constructed and may be used
+ /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
static bool isUsed()
{
- return ptb::GarbageCollector::isUsed();
+ return dhp::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
+ static void scan() ; // inline in dhp_impl.h
/// Synonym for \ref scan()
static void force_dispose()
//@cond
namespace cds { namespace gc {
- inline PTB::thread_gc::thread_gc(
+ inline DHP::thread_gc::thread_gc(
bool bPersistent
)
: m_bPersistent( bPersistent )
cds::threading::Manager::attachThread();
}
- inline PTB::thread_gc::~thread_gc()
+ inline DHP::thread_gc::~thread_gc()
{
if ( !m_bPersistent )
cds::threading::Manager::detachThread();
}
- inline PTB::Guard::Guard()
- : Guard::base_class( cds::threading::getGC<PTB>() )
+ inline DHP::Guard::Guard()
+ : Guard::base_class( cds::threading::getGC<DHP>() )
{}
template <size_t COUNT>
- inline PTB::GuardArray<COUNT>::GuardArray()
- : GuardArray::base_class( cds::threading::getGC<PTB>() )
+ inline DHP::GuardArray<COUNT>::GuardArray()
+ : GuardArray::base_class( cds::threading::getGC<DHP>() )
{}
- inline void PTB::scan()
+ inline void DHP::scan()
{
- cds::threading::getGC<PTB>().scan();
+ cds::threading::getGC<DHP>().scan();
}
}} // namespace cds::gc
//@cond
namespace cds {
- namespace gc { namespace hzp {
+ namespace gc { namespace hp {
/// Hazard Pointer schema implementation details
namespace details {
//@endcond
};
- }}} // namespace gc::hzp::details
+ }}} // namespace gc::hp::details
} // namespace cds
//@endcond
#define __CDS_GC_HP_DETAILS_HP_FWD_H
namespace cds {
- namespace gc { namespace hzp {
+ namespace gc { namespace hp {
// forward declarations
class GarbageCollector;
#define __CDS_GC_HP_DETAILS_HP_INLINE_H
namespace cds {
- namespace gc{ namespace hzp { namespace details {
+ namespace gc{ namespace hp { namespace details {
/************************************************************************/
/* INLINES */
/************************************************************************/
- inline retired_vector::retired_vector( const cds::gc::hzp::GarbageCollector& HzpMgr )
+ inline retired_vector::retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr )
: m_arr( HzpMgr.getMaxRetiredPtrCount() ),
m_nSize(0)
{}
- inline HPRec::HPRec( const cds::gc::hzp::GarbageCollector& HzpMgr )
+ inline HPRec::HPRec( const cds::gc::hp::GarbageCollector& HzpMgr )
: m_hzp( HzpMgr.getHazardPointerCount() ),
m_arrRetired( HzpMgr )
{}
- } } } // namespace gc::hzp::details
+ } } } // namespace gc::hp::details
} // namespace cds
#include <cds/details/bounded_array.h>
namespace cds {
- namespace gc{ namespace hzp { namespace details {
+ namespace gc{ namespace hp { namespace details {
/// Retired pointer
typedef cds::gc::details::retired_ptr retired_ptr;
typedef retired_vector_impl::iterator iterator;
/// Constructor
- retired_vector( const cds::gc::hzp::GarbageCollector& HzpMgr ) ; // inline
+ retired_vector( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
~retired_vector()
{}
/// Vector capacity.
/**
- The capacity is constant for any thread. It is defined by cds::gc::hzp::GarbageCollector.
+ The capacity is constant for any thread. It is defined by cds::gc::hp::GarbageCollector.
*/
size_t capacity() const { return m_arr.capacity(); }
}
};
- } } } // namespace gc::hzp::details
+ } } } // namespace gc::hp::details
} // namespace cds
#endif // #ifndef __CDS_GC_HP_DETAILS_HP_RETIRED_H
namespace cds {
namespace gc {
- namespace hzp {
+ namespace hp {
/// Hazard pointer
typedef void * hazard_pointer;
#if CDS_COMPILER == CDS_COMPILER_MSVC
# pragma warning(push)
- // warning C4251: 'cds::gc::hzp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomic::atomic<T>'
- // needs to have dll-interface to be used by clients of class 'cds::gc::hzp::GarbageCollector'
+ // warning C4251: 'cds::gc::hp::GarbageCollector::m_pListHead' : class 'cds::cxx11_atomic::atomic<T>'
+ // needs to have dll-interface to be used by clients of class 'cds::gc::hp::GarbageCollector'
# pragma warning(disable: 4251)
#endif
<tr>
<th>Feature</th>
<th>%cds::gc::HP</th>
- <th>%cds::gc::PTB</th>
+ <th>%cds::gc::DHP</th>
</tr>
<tr>
<td>Implementation quality</td>
- [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.
+ The cds::gc::hp 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
by contructing cds::gc::HP object in beginning of your main().
See cds::gc::HP class for explanation.
*/
- namespace hzp {
+ namespace hp {
namespace details {
/// Hazard pointer record of the thread
retired_vector m_arrRetired ; ///< Retired pointer array
/// Ctor
- HPRec( const cds::gc::hzp::GarbageCollector& HzpMgr ) ; // inline
+ HPRec( const cds::gc::hp::GarbageCollector& HzpMgr ); // inline
~HPRec()
{}
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
+ /// Internal list of cds::gc::hp::details::HPRec
struct hplist_node: public details::HPRec
{
hplist_node * m_pNextNode ; ///< next hazard ptr record in list
/// Auto-managed array of hazard pointers
/**
- This class is wrapper around cds::gc::hzp::details::HPArray class.
+ This class is wrapper around cds::gc::hp::details::HPArray class.
\p Count is the size of HP array
*/
template <size_t Count>
ThreadGC& getGC() const { return m_mgr; }
};
- } // namespace hzp
+ } // namespace hp
}} // namespace cds::gc
// Inlines
{
public:
/// Native guarded pointer type
- typedef gc::hzp::hazard_pointer guarded_pointer;
+ typedef gc::hp::hazard_pointer guarded_pointer;
/// Atomic reference
/**
template <typename T> using atomic_type = atomics::atomic<T>;
/// Thread GC implementation for internal usage
- typedef hzp::ThreadGC thread_gc_impl;
+ typedef hp::ThreadGC thread_gc_impl;
- /// Wrapper for hzp::ThreadGC class
+ /// Wrapper for hp::ThreadGC class
/**
@headerfile cds/gc/hp.h
This class performs automatically attaching/detaching Hazard Pointer GC
/// Hazard Pointer guard
/**
@headerfile cds/gc/hp.h
- This class is a wrapper for hzp::AutoHPGuard.
+ This class is a wrapper for hp::AutoHPGuard.
*/
- class Guard: public hzp::AutoHPGuard
+ class Guard : public hp::AutoHPGuard
{
//@cond
- typedef hzp::AutoHPGuard base_class;
+ typedef hp::AutoHPGuard base_class;
//@endcond
public:
/// Array of Hazard Pointer guards
/**
@headerfile cds/gc/hp.h
- This class is a wrapper for hzp::AutoHPArray template.
+ This class is a wrapper for hp::AutoHPArray template.
Template parameter \p Count defines the size of HP array.
*/
template <size_t Count>
- class GuardArray: public hzp::AutoHPArray<Count>
+ class GuardArray : public hp::AutoHPArray<Count>
{
//@cond
- typedef hzp::AutoHPArray<Count> base_class;
+ typedef hp::AutoHPArray<Count> base_class;
//@endcond
public:
/// Rebind array for other size \p Count2
};
public:
- /// Initializes hzp::GarbageCollector singleton
+ /// Initializes hp::GarbageCollector singleton
/**
The constructor initializes GC singleton with passed parameters.
If GC instance is not exist then the function creates the instance.
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
- hzp::scan_type nScanType = hzp::inplace ///< Scan type (see \ref hzp::scan_type enum)
+ hp::scan_type nScanType = hp::inplace ///< Scan type (see \ref hp::scan_type enum)
)
{
- hzp::GarbageCollector::Construct(
+ hp::GarbageCollector::Construct(
nHazardPtrCount,
nMaxThreadCount,
nMaxRetiredPtrCount,
/// Terminates GC singleton
/**
- The destructor calls \code hzp::GarbageCollector::Destruct( true ) \endcode
+ The destructor calls \code hp::GarbageCollector::Destruct( true ) \endcode
*/
~HP()
{
- hzp::GarbageCollector::Destruct( true );
+ hp::GarbageCollector::Destruct( true );
}
/// Checks if count of hazard pointer is no less than \p nCountNeeded
*/
static bool check_available_guards( size_t nCountNeeded, bool bRaiseException = true )
{
- if ( hzp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
+ if ( hp::GarbageCollector::instance().getHazardPointerCount() < nCountNeeded ) {
if ( bRaiseException )
throw std::overflow_error( "Too few hazard pointers" );
return false;
/// Returns max Hazard Pointer count
size_t max_hazard_count() const
{
- return hzp::GarbageCollector::instance().getHazardPointerCount();
+ return hp::GarbageCollector::instance().getHazardPointerCount();
}
/// Returns max count of thread
size_t max_thread_count() const
{
- return hzp::GarbageCollector::instance().getMaxThreadCount();
+ return hp::GarbageCollector::instance().getMaxThreadCount();
}
/// Returns capacity of retired pointer array
size_t retired_array_capacity() const
{
- return hzp::GarbageCollector::instance().getMaxRetiredPtrCount();
+ return hp::GarbageCollector::instance().getMaxRetiredPtrCount();
}
/// Retire pointer \p p with function \p pFunc
static void retire( T * p ) ; // inline in hp_impl.h
/// Get current scan strategy
- hzp::scan_type getScanType() const
+ hp::scan_type getScanType() const
{
- return hzp::GarbageCollector::instance().getScanType();
+ return hp::GarbageCollector::instance().getScanType();
}
/// Set current scan strategy
void setScanType(
- hzp::scan_type nScanType ///< new scan strategy
+ hp::scan_type nScanType ///< new scan strategy
)
{
- hzp::GarbageCollector::instance().setScanType( nScanType );
+ hp::GarbageCollector::instance().setScanType( nScanType );
}
/// Checks if Hazard Pointer GC is constructed and may be used
static bool isUsed()
{
- return hzp::GarbageCollector::isUsed();
+ return hp::GarbageCollector::isUsed();
}
@note Do not include <tt><cds/intrusive/impl/ellen_bintree.h></tt> header file explicitly.
There are header file for each GC type:
- <tt><cds/intrusive/ellen_bintree_hp.h></tt> - for Hazard Pointer GC \p cds::gc::HP
- - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Pass-the-Buck GC \p cds::gc::DHP
+ - <tt><cds/intrusive/ellen_bintree_dhp.h></tt> - for Dynamic Hazard Pointer GC \p cds::gc::DHP
- <tt><cds/intrusive/ellen_bintree_rcu.h></tt> - for RCU (see \ref cds_intrusive_EllenBinTree_rcu "RCU-based EllenBinTree")
<b>Template arguments</b> :
quasi factor. This means that the consumer dequeues <i>any</i> item from the current first segment.
Template parameters:
- - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::PTB
+ - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::DHP
- \p T - the type of values stored in the queue
- \p Traits - queue type traits, default is \p segmented_queue::traits.
\p segmented_queue::make_traits metafunction can be used to construct the
// Get cds::gc::HP thread GC implementation for current thread
static gc::HP::thread_gc_impl& getHZPGC();
- // Get cds::gc::PTB thread GC implementation for current thread;
- static gc::PTB::thread_gc_impl& getPTBGC();
+ // Get cds::gc::DHP thread GC implementation for current thread;
+ static gc::DHP::thread_gc_impl& getDHPGC();
};
\endcode
struct ThreadData {
//@cond
- char CDS_DATA_ALIGNMENT(8) m_hpManagerPlaceholder[sizeof(cds::gc::HP::thread_gc_impl)] ; ///< Michael's Hazard Pointer GC placeholder
- char CDS_DATA_ALIGNMENT(8) m_ptbManagerPlaceholder[sizeof(cds::gc::PTB::thread_gc_impl)] ; ///< Pass The Buck GC placeholder
+ char CDS_DATA_ALIGNMENT(8) m_hpManagerPlaceholder[sizeof(cds::gc::HP::thread_gc_impl)]; ///< Michael's Hazard Pointer GC placeholder
+ char CDS_DATA_ALIGNMENT(8) m_dhpManagerPlaceholder[sizeof(cds::gc::DHP::thread_gc_impl)]; ///< Dynamic Hazard Pointer GC placeholder
cds::urcu::details::thread_data< cds::urcu::general_instant_tag > * m_pGPIRCU;
cds::urcu::details::thread_data< cds::urcu::general_buffered_tag > * m_pGPBRCU;
//@endcond
cds::gc::HP::thread_gc_impl * m_hpManager ; ///< Michael's Hazard Pointer GC thread-specific data
- cds::gc::PTB::thread_gc_impl * m_ptbManager ; ///< Pass The Buck GC thread-specific data
+ cds::gc::DHP::thread_gc_impl * m_dhpManager ; ///< Dynamic Hazard Pointer GC thread-specific data
size_t m_nFakeProcessorNumber ; ///< fake "current processor" number
else
m_hpManager = nullptr;
- if ( cds::gc::PTB::isUsed() )
- m_ptbManager = new (m_ptbManagerPlaceholder) cds::gc::PTB::thread_gc_impl;
+ if ( cds::gc::DHP::isUsed() )
+ m_dhpManager = new (m_dhpManagerPlaceholder) cds::gc::DHP::thread_gc_impl;
else
- m_ptbManager = nullptr;
+ m_dhpManager = nullptr;
}
~ThreadData()
m_hpManager = nullptr;
}
- if ( m_ptbManager ) {
- typedef cds::gc::PTB::thread_gc_impl ptb_thread_gc_impl;
- m_ptbManager->~ptb_thread_gc_impl();
- m_ptbManager = nullptr;
+ if ( m_dhpManager ) {
+ typedef cds::gc::DHP::thread_gc_impl dhp_thread_gc_impl;
+ m_dhpManager->~dhp_thread_gc_impl();
+ m_dhpManager = nullptr;
}
assert( m_pGPIRCU == nullptr );
if ( m_nAttachCount++ == 0 ) {
if ( cds::gc::HP::isUsed() )
m_hpManager->init();
- if ( cds::gc::PTB::isUsed() )
- m_ptbManager->init();
+ if ( cds::gc::DHP::isUsed() )
+ m_dhpManager->init();
if ( cds::urcu::details::singleton<cds::urcu::general_instant_tag>::isUsed() )
m_pGPIRCU = cds::urcu::details::singleton<cds::urcu::general_instant_tag>::attach_thread();
bool fini()
{
if ( --m_nAttachCount == 0 ) {
- if ( cds::gc::PTB::isUsed() )
- m_ptbManager->fini();
+ if ( cds::gc::DHP::isUsed() )
+ m_dhpManager->fini();
if ( cds::gc::HP::isUsed() )
m_hpManager->fini();
return *(_threadData()->m_hpManager);
}
- /// Get gc::PTB thread GC implementation for current thread
+ /// Get gc::DHP thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::PTB.
- To initialize gc::PTB GC you must constuct cds::gc::PTB object in the beginning of your application
+ or if you did not use gc::DHP.
+ To initialize gc::DHP GC you must constuct cds::gc::DHP object in the beginning of your application
*/
- static gc::PTB::thread_gc_impl& getPTBGC()
+ static gc::DHP::thread_gc_impl& getDHPGC()
{
- assert( _threadData()->m_ptbManager != nullptr );
- return *(_threadData()->m_ptbManager);
+ assert( _threadData()->m_dhpManager != nullptr );
+ return *(_threadData()->m_dhpManager);
}
//@cond
return *(_threadData()->m_hpManager);
}
- /// Get gc::PTB thread GC implementation for current thread
+ /// Get gc::DHP thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::PTB.
- To initialize gc::PTB GC you must constuct cds::gc::PTB object in the beginning of your application
+ or if you did not use gc::DHP.
+ To initialize gc::DHP GC you must constuct cds::gc::DHP object in the beginning of your application
*/
- static gc::PTB::thread_gc_impl& getPTBGC()
+ static gc::DHP::thread_gc_impl& getDHPGC()
{
- assert( _threadData()->m_ptbManager );
- return *(_threadData()->m_ptbManager);
+ assert( _threadData()->m_dhpManager );
+ return *(_threadData()->m_dhpManager);
}
//@cond
return *(_threadData()->m_hpManager);
}
- /// Get gc::PTB thread GC implementation for current thread
+ /// Get gc::DHP thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::PTB.
- To initialize gc::PTB GC you must constuct cds::gc::PTB object in the beginning of your application
+ or if you did not use gc::DHP.
+ To initialize gc::DHP GC you must constuct cds::gc::DHP object in the beginning of your application
*/
- static gc::PTB::thread_gc_impl& getPTBGC()
+ static gc::DHP::thread_gc_impl& getDHPGC()
{
- assert( _threadData()->m_ptbManager );
- return *(_threadData()->m_ptbManager);
+ assert( _threadData()->m_dhpManager );
+ return *(_threadData()->m_dhpManager);
}
//@cond
return *(_threadData( do_getData )->m_hpManager);
}
- /// Get gc::PTB thread GC implementation for current thread
+ /// Get gc::DHP thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::PTB.
- To initialize gc::PTB GC you must constuct cds::gc::PTB object in the beginning of your application
+ or if you did not use gc::DHP.
+ To initialize gc::DHP GC you must constuct cds::gc::DHP object in the beginning of your application
*/
- static gc::PTB::thread_gc_impl& getPTBGC()
+ static gc::DHP::thread_gc_impl& getDHPGC()
{
- return *(_threadData( do_getData )->m_ptbManager);
+ return *(_threadData( do_getData )->m_dhpManager);
}
//@cond
return *(_threadData( do_getData )->m_hpManager);
}
- /// Get gc::PTB thread GC implementation for current thread
+ /// Get gc::DHP thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use gc::PTB.
- To initialize gc::PTB GC you must constuct cds::gc::PTB object in the beginning of your application
+ or if you did not use gc::DHP.
+ To initialize gc::DHP GC you must constuct cds::gc::DHP object in the beginning of your application
*/
- static gc::PTB::thread_gc_impl& getPTBGC()
+ static gc::DHP::thread_gc_impl& getDHPGC()
{
- return *(_threadData( do_getData )->m_ptbManager);
+ return *(_threadData( do_getData )->m_dhpManager);
}
//@cond
return Manager::getHZPGC();
}
- /// Get cds::gc::PTB thread GC implementation for current thread
+ /// Get cds::gc::DHP thread GC implementation for current thread
/**
The object returned may be uninitialized if you did not call attachThread in the beginning of thread execution
- or if you did not use cds::gc::PTB.
- To initialize cds::gc::PTB GC you must constuct cds::gc::PTB object in the beginning of your application,
+ or if you did not use cds::gc::DHP.
+ To initialize cds::gc::DHP GC you must constuct cds::gc::DHP object in the beginning of your application,
see \ref cds_how_to_use "How to use libcds"
*/
template <>
- inline cds::gc::PTB::thread_gc_impl& getGC<cds::gc::PTB>()
+ inline cds::gc::DHP::thread_gc_impl& getGC<cds::gc::DHP>()
{
- return Manager::getPTBGC();
+ return Manager::getDHPGC();
}
//@cond
//$$CDS-header$$
-// Pass The Buck (PTB) Memory manager implementation
+// Dynamic Hazard Pointer memory manager implementation
#include <algorithm> // std::fill
#include <functional> // std::hash
#include <cds/gc/dhp/dhp.h>
#include <cds/algo/int_algo.h>
-namespace cds { namespace gc { namespace ptb {
+namespace cds { namespace gc { namespace dhp {
namespace details {
GarbageCollector::~GarbageCollector()
{
liberate();
-
-#if 0
- details::retired_ptr_node * pHead = nullptr;
- details::retired_ptr_node * pTail = nullptr;
-
- for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_relaxed)) {
- details::guard_data::handoff_ptr h = pGuard->pHandOff;
- pGuard->pHandOff = nullptr;
- while ( h ) {
- details::guard_data::handoff_ptr pNext = h->m_pNextFree;
- if ( h->m_ptr.m_p )
- h->m_ptr.free();
- if ( !pHead )
- pTail = pHead = h;
- else
- pTail = pTail->m_pNextFree = h;
- h = pNext;
- }
- }
- if ( pHead )
- m_RetiredAllocator.free_range( pHead, pTail );
-#endif
}
void GarbageCollector::liberate()
}
}
}
-
-#if 0
- void GarbageCollector::liberate( details::liberate_set& set )
- {
- details::guard_data::handoff_ptr const nullHandOff = nullptr;
-
- for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) )
- {
- // get guarded pointer
- details::guard_data::guarded_ptr valGuarded = pGuard->pPost.load(atomics::memory_order_acquire);
- details::guard_data::handoff_ptr h;
-
- if ( valGuarded ) {
- details::retired_ptr_node * pRetired = set.erase( valGuarded );
- if ( pRetired ) {
- // Retired pointer is being guarded
-
- // pRetired is the head of retired pointers list for which the m_ptr.m_p field is equal
- // List is linked on m_pNextFree field
-
- // Now, try to set retired node pRetired as a hand-off node for the guard
- cds::lock::Auto<details::guard_data::handoff_spin> al( pGuard->spinHandOff );
- if ( valGuarded == pGuard->pPost.load(atomics::memory_order_acquire) ) {
- if ( pGuard->pHandOff && pGuard->pHandOff->m_ptr.m_p == pRetired->m_ptr.m_p ) {
- h = nullHandOff ; //nullptr;
- details::retired_ptr_node * pTail = pGuard->pHandOff;
- while ( pTail->m_pNextFree )
- pTail = pTail->m_pNextFree;
- pTail->m_pNextFree = pRetired;
- }
- else {
- // swap h and pGuard->pHandOff
- h = pGuard->pHandOff;
- pGuard->pHandOff = pRetired;
- }
- }
- else
- h = pRetired;
- }
- else {
- cds::lock::Auto<details::guard_data::handoff_spin> al( pGuard->spinHandOff );
- h = pGuard->pHandOff;
- if ( h ) {
- if ( h->m_ptr.m_p != valGuarded )
- pGuard->pHandOff = nullHandOff;
- else
- h = nullHandOff;
- }
- }
- }
- else {
- cds::lock::Auto<details::guard_data::handoff_spin> al( pGuard->spinHandOff );
- h = pGuard->pHandOff;
- pGuard->pHandOff = nullHandOff;
- }
-
- // h is the head of a list linked on m_pNextFree field
- if ( h ) {
- set.insert( *h );
- }
- }
- }
-#endif
-}}} // namespace cds::gc::ptb
+}}} // namespace cds::gc::dhp
//---------------------------------------------------------------
// Hazard Pointers reclamation schema constants
- namespace hzp {
+ namespace hp {
// Max number of threads expected
static const size_t c_nMaxThreadCount = 100;
// Number of Hazard Pointers per thread
static const size_t c_nHazardPointerPerThread = 8;
- } // namespace hzp
+ } // namespace hp
} /* namespace gc */ } /* namespace cds */
#define CDS_HAZARDPTR_STATISTIC( _x ) if ( m_bStatEnabled ) { _x; }
namespace cds { namespace gc {
- namespace hzp {
+ namespace hp {
/// Max array size of retired pointers
static const size_t c_nMaxRetireNodeCount = c_nHazardPointerPerThread * c_nMaxThreadCount * 2;
}
- } //namespace hzp
+ } //namespace hp
}} // namespace cds::gc
#endif
-std::ostream& operator << (std::ostream& s, const cds::gc::hzp::GarbageCollector::InternalState& stat)
+std::ostream& operator << (std::ostream& s, const cds::gc::hp::GarbageCollector::InternalState& stat)
{
s << "\nHZP GC internal state:"
<< "\n\t\tHP record allocated=" << stat.nHPRecAllocated
{
if ( m_bPrintGCState ) {
{
- cds::gc::hzp::GarbageCollector::InternalState stat;
- std::cout << cds::gc::hzp::GarbageCollector::instance().getInternalState( stat ) << std::endl;
+ cds::gc::hp::GarbageCollector::InternalState stat;
+ std::cout << cds::gc::hp::GarbageCollector::instance().getInternalState( stat ) << std::endl;
}
}
}
// Safe reclamation schemes
cds::gc::HP hzpGC( nHazardPtrCount );
- cds::gc::PTB ptbGC;
+ cds::gc::DHP dhpGC;
// RCU varieties
typedef cds::urcu::gc< cds::urcu::general_instant<> > rcu_gpi;
CppUnitMini::TestCfg& cfg = CppUnitMini::TestCase::m_Cfg.get( "General" );
std::string strHZPScanStrategy = cfg.get( "HZP_scan_strategy", std::string("classic") );
if ( strHZPScanStrategy == "inplace" )
- hzpGC.setScanType( cds::gc::hzp::inplace );
+ hzpGC.setScanType( cds::gc::hp::inplace );
else if ( strHZPScanStrategy == "classic" )
- hzpGC.setScanType( cds::gc::hzp::classic );
+ hzpGC.setScanType( cds::gc::hp::classic );
else {
std::cout << "Error value of HZP_scan_strategy in General section of test config\n";
}
switch (hzpGC.getScanType()) {
- case cds::gc::hzp::inplace:
+ case cds::gc::hp::inplace:
std::cout << "Use in-place scan strategy for Hazard Pointer memory reclamation algorithm\n";
break;
- case cds::gc::hzp::classic:
+ case cds::gc::hp::classic:
std::cout << "Use classic scan strategy for Hazard Pointer memory reclamation algorithm\n";
break;
default:
}
if ( CppUnitMini::TestCase::m_bPrintGCState ) {
- cds::gc::hzp::GarbageCollector::InternalState stat;
- cds::gc::hzp::GarbageCollector::instance().getInternalState( stat );
+ cds::gc::hp::GarbageCollector::InternalState stat;
+ cds::gc::hp::GarbageCollector::instance().getInternalState( stat );
std::cout << "HP constants:"
<< "\n\tHP count per thread=" << stat.nHPCount
namespace tree {
namespace ellen_bintree_dhp {
- typedef cds::intrusive::ellen_bintree::node_types<cds::gc::PTB, IntrusiveBinTreeHdrTest::key_type> node_types;
+ typedef cds::intrusive::ellen_bintree::node_types<cds::gc::DHP, IntrusiveBinTreeHdrTest::key_type> node_types;
typedef node_types::leaf_node_type leaf_node;
typedef IntrusiveBinTreeHdrTest::base_hook_value< leaf_node > base_value;
typedef node_types::internal_node_type internal_node;