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

enum cds::gc::HP::scan_type

strong

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

nHazardPtrCount	Hazard pointer count per thread
nMaxThreadCount	Max count of simultaneous working thread in your application
nMaxRetiredPtrCount	Capacity of the array of retired objects for the thread
nScanType	Scan 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()
{
    cds::Initialize();
    {
        // Initialize HP SMR
        cds::gc::HP hp;
        // deal with HP-based data structured
        // ...
    }
    // HP object destroyed
    // Get total post-mortem statistics
    cds::gc::HP::stat const& st = cds::gc::HP::postmortem_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",
        st.thread_rec_count,
        st.guard_allocated, st.guard_freed,
        st.retired_count, st.free_count,
        st.scan_count, st.help_scan_count
    );
    cds::Terminate();
}

◆ 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_func	`malloc()` function
free_func	`free()` 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/gc/hp.h

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ scan_type

Constructor & Destructor Documentation

◆ HP()

◆ ~HP()

Member Function Documentation

◆ check_available_guards()

◆ postmortem_statistics()

◆ retire() [1/2]

◆ retire() [2/2]

◆ scan()

◆ set_memory_allocator()

◆ statistics()