cds  2.2.0
cds::gc::HP Class Reference

Hazard Pointer garbage collector. More...

#include <cds/gc/hp.h>

Data Structures

class  Guard
 Hazard Pointer guard. More...
 
class  GuardArray
 Array of Hazard Pointer guards. More...
 
class  guarded_ptr
 Guarded pointer. More...
 
class  thread_gc
 Wrapper for hp::ThreadGC class. More...
 

Public Types

enum  scan_type { scan_type::classic = hp::classic, scan_type::inplace = hp::inplace }
 scan() type More...
 
typedef gc::hp::hazard_pointer guarded_pointer
 Native guarded pointer type.
 
template<typename T >
using atomic_ref = atomics::atomic< T * >
 Atomic reference.
 
template<typename MarkedPtr >
using atomic_marked_ptr = atomics::atomic< MarkedPtr >
 Atomic marked pointer.
 
template<typename T >
using atomic_type = atomics::atomic< T >
 Atomic type.
 
typedef hp::ThreadGC thread_gc_impl
 Thread GC implementation for internal usage.
 
typedef hp::GarbageCollector::too_many_hazard_ptr too_many_hazard_ptr_exception
 Exception "Too many Hazard Pointer".
 

Public Member Functions

 HP (size_t nHazardPtrCount=0, size_t nMaxThreadCount=0, size_t nMaxRetiredPtrCount=0, scan_type nScanType=scan_type::inplace)
 Initializes HP singleton. More...
 
 ~HP ()
 Terminates GC singleton. More...
 

Static Public Member Functions

static bool check_available_guards (size_t nCountNeeded, bool bRaiseException=true)
 Checks if count of hazard pointer is no less than nCountNeeded. More...
 
static size_t max_hazard_count ()
 Returns max Hazard Pointer count.
 
static size_t max_thread_count ()
 Returns max count of thread.
 
static size_t retired_array_capacity ()
 Returns capacity of retired pointer array.
 
template<typename T >
static void retire (T *p, void(*pFunc)(T *))
 Retire pointer p with function pFunc. More...
 
template<class Disposer , typename T >
static void retire (T *p)
 Retire pointer p with functor of type Disposer. More...
 
static scan_type getScanType ()
 Get current scan strategy.
 
static void setScanType (scan_type nScanType)
 Set current scan strategy. More...
 
static bool isUsed ()
 Checks if Hazard Pointer GC is constructed and may be used.
 
static void scan ()
 Forced GC cycle call for current thread. More...
 
static void force_dispose ()
 Synonym for scan()
 

Detailed Description

Hazard Pointer garbage collector.

Implementation of classic Hazard Pointer garbage collector.

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"

Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is GC class cds::gc::HP 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 How to use section for details how to apply garbage collector.

Member Enumeration Documentation

§ scan_type

scan() type

Enumerator
classic 

classic scan as described in Michael's papers

inplace 

inplace scan without allocation

Constructor & Destructor Documentation

§ HP()

cds::gc::HP::HP ( size_t  nHazardPtrCount = 0,
size_t  nMaxThreadCount = 0,
size_t  nMaxRetiredPtrCount = 0,
scan_type  nScanType = scan_type::inplace 
)
inline

Initializes HP singleton.

The constructor initializes GC singleton with passed parameters. 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:

  • nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from the data structure algorithms. By default, if nHazardPtrCount = 0, the function uses maximum of the hazard pointer count for CDS library.
  • nMaxThreadCount - max count of thread with using Hazard Pointer GC in your application. Default is 100.
  • nMaxRetiredPtrCount - capacity of array of retired pointers for each thread. Must be greater than nHazardPtrCount * nMaxThreadCount . Default is 2 * nHazardPtrCount * nMaxThreadCount .
Parameters
nHazardPtrCountHazard pointer count per thread
nMaxThreadCountMax count of simultaneous working thread in your application
nMaxRetiredPtrCountCapacity of the array of retired objects for the thread
nScanTypeScan type (see scan_type enum)

§ ~HP()

cds::gc::HP::~HP ( )
inline

Terminates GC singleton.

The destructor destroys HP global object. After calling of this function you may NOT use CDS data structures based on cds::gc::HP. Usually, HP object is destroyed at the end of your main().

Member Function Documentation

§ check_available_guards()

static bool cds::gc::HP::check_available_guards ( size_t  nCountNeeded,
bool  bRaiseException = true 
)
inlinestatic

Checks if count of hazard pointer is no less than nCountNeeded.

If bRaiseException is true (that is the default), the function raises an std::overflow_error exception "Too few hazard pointers" if nCountNeeded is more than the count of hazard pointer per thread.

§ retire() [1/2]

template<typename T >
static void cds::gc::HP::retire ( T *  p,
void(*)(T *)  pFunc 
)
static

Retire pointer p with function pFunc.

The function places pointer p to array of pointers ready for removing. (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it. Deleting the pointer is the function pFunc call.

§ retire() [2/2]

template<class Disposer , typename T >
static void cds::gc::HP::retire ( T *  p)
static

Retire pointer p with functor of type Disposer.

The function places pointer p to array of pointers ready for removing. (so called retired pointer array). The pointer can be safely removed when no hazard pointer points to it.

Deleting the pointer is an invocation of some object of type Disposer; the interface of Disposer is:

template <typename T>
struct disposer {
void operator()( T * p ) ; // disposing operator
};

Since the functor call can happen at any time after retire call, additional restrictions are imposed to Disposer type:

  • it should be stateless functor
  • it should be default-constructible
  • the result of functor call with argument p should not depend on where the functor will be called.
Examples:
Operator delete functor:
template <typename T>
struct disposer {
void operator ()( T * p ) {
delete p;
}
};
// How to call GC::retire method
int * p = new int;
// ... use p in lock-free manner
cds::gc::HP::retire<disposer>( p ) ; // place p to retired pointer array of HP GC

Functor based on std::allocator :

template <typename ALLOC = std::allocator<int> >
struct disposer {
template <typename T>
void operator()( T * p ) {
typedef typename ALLOC::templare rebind<T>::other alloc_t;
alloc_t a;
a.destroy( p );
a.deallocate( p, 1 );
}
};

§ scan()

static void cds::gc::HP::scan ( )
static

Forced GC cycle call for current thread.

Usually, this function should not be called directly.

§ setScanType()

static void cds::gc::HP::setScanType ( scan_type  nScanType)
inlinestatic

Set current scan strategy.

Parameters
nScanTypenew scan strategy

The documentation for this class was generated from the following file:

cds 2.2.0 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Wed Jan 4 2017 08:49:49 by Doxygen 1.8.12