cds  2.3.1
cds::gc::HP Class Reference

Hazard Pointer SMR (Safe Memory Reclamation) 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...
 

Public Types

enum  scan_type { scan_type::classic = hp::classic, scan_type::inplace = hp::inplace }
 scan() type More...
 
typedef hp::hazard_ptr 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::not_enought_hazard_ptr not_enought_hazard_ptr_exception
 Exception "Not enough Hazard Pointer".
 
typedef hp::stat stat
 Internal statistics.
 

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 void check_available_guards (size_t nCountNeeded)
 Checks that required hazard pointer count nCountNeeded is less or equal then max hazard pointer count. More...
 
static void set_memory_allocator (void *(*alloc_func)(size_t size), void(*free_func)(void *p))
 Set memory management functions. 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(*func)(void *))
 Retire pointer p with function func. 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 bool isUsed ()
 Checks if Hazard Pointer GC is constructed and may be used.
 
static void scan ()
 Forces SMR call for current thread. More...
 
static void force_dispose ()
 Synonym for scan()
 
static void statistics (stat &st)
 Returns internal statistics. More...
 
static CDS_EXPORT_API stat const & postmortem_statistics ()
 Returns post-mortem statistics. More...
 

Detailed Description

Hazard Pointer SMR (Safe Memory Reclamation)

Implementation of classic Hazard Pointer SMR

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 SMR is a singleton. The main user-level part of Hazard Pointer schema is cds::gc::HP class and its nested classes. Before use any HP-related class you must initialize HP by contructing cds::gc::HP object in beginning of your main(). See How to use section for details how to apply SMR schema.

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 Hazard Pointer SMR singleton with passed parameters. If the instance does not yet 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. If nHazardPtrCount = 0, the defaul value 8 is used
  • 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 void cds::gc::HP::check_available_guards ( size_t  nCountNeeded)
inlinestatic

Checks that required hazard pointer count nCountNeeded is less or equal then max hazard pointer count.

If nRequiredCount > get_hazard_ptr_count() then the exception not_enought_hazard_ptr is thrown

◆ postmortem_statistics()

static CDS_EXPORT_API stat const& cds::gc::HP::postmortem_statistics ( )
static

Returns post-mortem statistics.

Post-mortem statistics is gathered in the HP object destructor and can be accessible after destructing the global HP object.

Note
Internal statistics is available only if you compile libcds and your program with -DCDS_ENABLE_HPSTAT.

Usage:

int main()
{
{
// Initialize HP SMR
cds::gc::HP hp;
// deal with HP-based data structured
// ...
}
// HP object destroyed
// Get total post-mortem statistics
printf( "HP statistics:\n"
" thread count = %llu\n"
" guard allocated = %llu\n"
" guard freed = %llu\n"
" retired data count = %llu\n"
" free data count = %llu\n"
" scan() call count = %llu\n"
" help_scan() call count = %llu\n",
);
}

◆ retire() [1/2]

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

Retire pointer p with function func.

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. func is a disposer: when p can be safely removed, func is called.

◆ retire() [2/2]

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

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 HP::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 ( )
inlinestatic

Forces SMR call for current thread.

Usually, this function should not be called directly.

◆ set_memory_allocator()

static void cds::gc::HP::set_memory_allocator ( void *(*)(size_t size)  alloc_func,
void(*)(void *p)  free_func 
)
inlinestatic

Set memory management functions.

Note
This function may be called BEFORE creating an instance of Hazard Pointer SMR

SMR object allocates some memory for thread-specific data and for creating SMR object. By default, a standard new and delete operators are used for this.

Parameters
alloc_funcmalloc() function
free_funcfree() function

◆ statistics()

static void cds::gc::HP::statistics ( stat st)
inlinestatic

Returns internal statistics.

The function clears st before gathering statistics.

Note
Internal statistics is available only if you compile libcds and your program with -DCDS_ENABLE_HPSTAT.

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

cds 2.3.1 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Fri Sep 1 2017 08:47:19 by Doxygen 1.8.13