Hazard Pointer singleton. More...

#include <cds/gc/hzp/hzp.h>

Data Structures
struct	hplist_node
	Internal list of cds::gc::hzp::details::HPRec. More...

struct	InternalState
	Internal GC statistics. More...

struct	Statistics
	Internal GC statistics. More...

Public Types
typedef cds::atomicity::event_counter	event_counter
	event counter type

Public Member Functions
	CDS_DECLARE_EXCEPTION (HZPManagerEmpty,"Global Hazard Pointer GarbageCollector is NULL")
	No GarbageCollector object is created.

	CDS_DECLARE_EXCEPTION (HZPTooMany,"Not enough required Hazard Pointer count")
	Not enough required Hazard Pointer count.

size_t	getHazardPointerCount () const
	Returns max Hazard Pointer count defined in construction time.

size_t	getMaxThreadCount () const
	Returns max thread count defined in construction time.

size_t	getMaxRetiredPtrCount () const
	Returns max size of retired objects array. It is defined in construction time.

InternalState &	getInternalState (InternalState &stat) const
	Get internal statistics.

bool	isStatisticsEnabled () const
	Checks if internal statistics enabled.

bool	enableStatistics (bool bEnable)
	Enables/disables internal statistics.

scan_type	getScanType () const
	Get current scan strategy.

void	setScanType (scan_type nScanType)
	Set current scan strategy. More...

details::HPRec *	AllocateHPRec ()
	Allocates Hazard Pointer GC record. For internal use only.

void	RetireHPRec (details::HPRec *pRec)
	Free HP record. For internal use only.

void	Scan (details::HPRec *pRec)
	The main garbage collecting function. More...

void	HelpScan (details::HPRec *pThis)
	Helper scan routine. More...

Static Public Member Functions
static void CDS_STDCALL	Construct (size_t nHazardPtrCount=0, size_t nMaxThreadCount=0, size_t nMaxRetiredPtrCount=0, scan_type nScanType=inplace)
	Creates GarbageCollector singleton. More...

static void CDS_STDCALL	Destruct (bool bDetachAll=false)
	Destroys global instance of GarbageCollector. More...

static GarbageCollector &	instance ()
	Returns pointer to GarbageCollector instance.

static bool	isUsed ()
	Checks if global GC object is constructed and may be used.

static void	checkHPCount (unsigned int nRequiredCount)
	Checks that required hazard pointer count `nRequiredCount` is less or equal then max hazard pointer count. More...

Protected Member Functions
void	classic_scan (details::HPRec *pRec)
	Classic scan algorithm. More...

void	inplace_scan (details::HPRec *pRec)
	In-place scan algorithm. More...

Private Member Functions
	GarbageCollector (size_t nHazardPtrCount=0, size_t nMaxThreadCount=0, size_t nMaxRetiredPtrCount=0, scan_type nScanType=inplace)
	Ctor. More...

	~GarbageCollector ()
	Dtor.

hplist_node *	NewHPRec ()
	Allocate new HP record.

void	DeleteHPRec (hplist_node *pNode)
	Permanently deletes HPrecord `pNode`. More...

void	DeletePtr (details::retired_ptr &p)
	Permanently deletes retired pointer `p`. More...

Private Attributes
std::atomic< hplist_node * >	m_pListHead
	Head of GC list.

Statistics	m_Stat
	Internal statistics.

bool	m_bStatEnabled
	true - statistics enabled

const size_t	m_nHazardPointerCount
	max count of thread's hazard pointer

const size_t	m_nMaxThreadCount
	max count of thread

const size_t	m_nMaxRetiredPtrCount
	max count of retired ptr per thread

scan_type	m_nScanType
	scan type (see scan_type enum)

Static Private Attributes
static GarbageCollector *	m_pHZPManager
	GC instance pointer.

Detailed Description

Hazard Pointer singleton.

Safe memory reclamation schema by Michael "Hazard Pointers"

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"

Constructor & Destructor Documentation

cds::gc::hzp::GarbageCollector::GarbageCollector	(	size_t	nHazardPtrCount = `0`,
		size_t	nMaxThreadCount = `0`,
		size_t	nMaxRetiredPtrCount = `0`,
		scan_type	nScanType = `inplace`
	)

private

Ctor.

Parameters

nHazardPtrCount	Hazard pointer count per thread
nMaxThreadCount	Max count of thread
nMaxRetiredPtrCount	Capacity of the array of retired objects
nScanType	Scan type (see scan_type enum)

Member Function Documentation

static void cds::gc::hzp::GarbageCollector::checkHPCount ( unsigned int nRequiredCount )

inlinestatic

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

If nRequiredCount > getHazardPointerCount() then the exception HZPTooMany is thrown

void cds::gc::hzp::GarbageCollector::classic_scan ( details::HPRec * pRec )

protected

Classic scan algorithm.

Classical scan algorithm as described in Michael's paper.

A scan includes four stages. The first stage involves scanning the array HP for non-null values. Whenever a non-null value is encountered, it is inserted in a local list of currently protected pointer. Only stage 1 accesses shared variables. The following stages operate only on private variables.

The second stage of a scan involves sorting local list of protected pointers to allow binary search in the third stage.

The third stage of a scan involves checking each reclaimed node against the pointers in local list of protected pointers. If the binary search yields no match, the node is freed. Otherwise, it cannot be deleted now and must kept in thread's list of reclaimed pointers.

The forth stage prepares new thread's private list of reclaimed pointers that could not be freed during the current scan, where they remain until the next scan.

This algorithm allocates memory for internal HP array.

This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers is reached.

static void CDS_STDCALL cds::gc::hzp::GarbageCollector::Construct	(	size_t	nHazardPtrCount = `0`,
		size_t	nMaxThreadCount = `0`,
		size_t	nMaxRetiredPtrCount = `0`,
		scan_type	nScanType = `inplace`
	)

static

Creates GarbageCollector singleton.

GC is the singleton. 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 - HP pointer count per thread. Usually it is small number (2-4) depending from the data structure algorithms. By default, if nHazardPtrCount = 0, the function uses maximum of HP count for CDS library.

nMaxThreadCount - max count of thread with using HP 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)

void cds::gc::hzp::GarbageCollector::DeleteHPRec ( hplist_node * pNode )

private

Permanently deletes HPrecord pNode.

Caveat: for performance reason this function is defined as inline and cannot be called directly

void cds::gc::hzp::GarbageCollector::DeletePtr ( details::retired_ptr & p )

private

Permanently deletes retired pointer p.

Caveat: for performance reason this function is defined as inline and cannot be called directly

static void CDS_STDCALL cds::gc::hzp::GarbageCollector::Destruct ( bool bDetachAll = false )

static

Destroys global instance of GarbageCollector.

The parameter bDetachAll should be used carefully: if its value is true, then the destroying GC automatically detaches all attached threads. This feature can be useful when you have no control over the thread termination, for example, when libcds is injected into existing external thread.

Parameters

bDetachAll Detach all threads

void cds::gc::hzp::GarbageCollector::HelpScan ( details::HPRec * pThis )

Helper scan routine.

The function guarantees that every node that is eligible for reuse is eventually freed, barring thread failures. To do so, after executing Scan, a thread executes a HelpScan, where it checks every HP record. If an HP record is inactive, the thread moves all "lost" reclaimed pointers to thread's list of reclaimed pointers.

The function is called internally by Scan.

void cds::gc::hzp::GarbageCollector::inplace_scan ( details::HPRec * pRec )

protected

In-place scan algorithm.

Unlike the classic_scan algorithm, inplace_scan does not allocate any memory. All operations are performed in-place.

void cds::gc::hzp::GarbageCollector::Scan ( details::HPRec * pRec )

inline

The main garbage collecting function.

This function is called internally by ThreadGC object when upper bound of thread's list of reclaimed pointers is reached.

There are the following scan algorithm:

classic_scan allocates memory for internal use
inplace_scan does not allocate any memory

Use setScanType function to setup appropriate scan algorithm.

void cds::gc::hzp::GarbageCollector::setScanType ( scan_type nScanType )

inline

Set current scan strategy.

Scan strategy changing is allowed on the fly.

Parameters

nScanType new scan strategy

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

cds/gc/hzp/hzp.h

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation