MultiWordCompareAndSwap class is used to perform a Multi-Word Compare-and-Swap (MCAS) To execute an MCAS, call addCASTriple for each address you want to update, then call execute();. More...

#include <mcas.h>

Inheritance diagram for tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >:

Public Member Functions
	MultiWordCompareAndSwap (int max_rows)

	~MultiWordCompareAndSwap ()

bool	add_cas_triple (std::atomic< T > *address, T expected_value, T new_value)
	This function is used to add a CAS triple to the MCAS operation. More...

bool	execute ()
	This function is called after all the CAS triples have been added to the operation. More...

void	help_complete ()
	THis function overrides the virtual function in the OpRecord class It is called by the progress assurance scheme. More...

bool	on_is_watched ()
	This function overrides the virtual function in the HP::Element class It returns whether or not this mcas class is being referenced by another threaded. More...

Public Member Functions inherited from tervel::util::OpRecord
	OpRecord ()

bool	on_watch (std::atomic< void * > address, void expected)
	This function is used to achieve a strong watch on an Element. More...

bool	on_is_watched ()
	This function is used to check a strong watch on an Element. More...

void	on_unwatch ()
	This function is used to remove a strong watch on an Element. More...

Public Member Functions inherited from tervel::util::memory::hp::Element
	Element ()

virtual	~Element ()

void	safe_delete (bool no_check=false, ElementList *const element_list=tervel::tl_thread_info->get_hp_element_list())
	This function is used to free a hazard pointer protected object if it is safe to do so OR add it to a list to be freed later. More...

Static Public Attributes
static constexpr void *	MCAS_FAIL_CONST = reinterpret_cast<void *>(0x1L)

Private Types
enum	MCasState : std::int8_t { MCasState::IN_PROGRESS = 0, MCasState::PASS = 1, MCasState::FAIL = 2, MCasState::DELETED = 3 }
	This enum is used to indicate the state of an mcas operation DELETED is used in debugging procedures. More...

Private Member Functions
bool	mcas_complete (int start_pos, bool wfmode=false)
	This function is used to complete a currently executing MCAS operation It is most likely that this operation is in conflict with some other operation and that it was discover by the dereferencing of an MCH The MCH contains a reference to the row in the MCAS it is associated with and a reference to the final row in the mcas. More...

bool	mcas_complete (CasRow< T > *current_row)
	Same as above, but it calculates the start_pos based on the current row then calls the above mcas_complete. More...

void	cleanup (bool success)
	This function is used to cleanup a completed MCAS operation It removes each MCH placed during this operation, replacing it with the logical value. More...

T	mcas_remove (const int pos, T value)
	This function insures that upon its return that *(cas_rows_[pos].address) no longer equals value. More...

Private Attributes
std::unique_ptr< CasRow< T >[]>	cas_rows_

std::atomic< MCasState >	state_ {MCasState::IN_PROGRESS}

int	row_count_ {0}

int	max_rows_

friend	Helper< T >

friend	CasRow< T >

Detailed Description

template<class T>
class tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >

MultiWordCompareAndSwap class is used to perform a Multi-Word Compare-and-Swap (MCAS) To execute an MCAS, call addCASTriple for each address you want to update, then call execute();.

This function is wait-free.

Member Enumeration Documentation

template<class T >

enum tervel::algorithms::wf::mcas::MultiWordCompareAndSwap::MCasState : std::int8_t

strongprivate

This enum is used to indicate the state of an mcas operation DELETED is used in debugging procedures.

Enumerator
IN_PROGRESS
PASS
FAIL
DELETED

Constructor & Destructor Documentation

template<class T >

tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::MultiWordCompareAndSwap ( int max_rows )

inlineexplicit

template<class T >

tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::~MultiWordCompareAndSwap ( )

inline

Member Function Documentation

template<class T >

bool tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::add_cas_triple	(	std::atomic< T > *	address,
		T	expected_value,
		T	new_value
	)

This function is used to add a CAS triple to the MCAS operation.

Each Triple consistent of an address to replace the expected value with a new value iff each other address holds its expected value.

This function returns false in the event the address already exists in the MCAS operation or the passed values are not valid. A Valid value is a value which does not use one of the reserved bits or constants. See related documentation for more details

Parameters

address
expected_value
new_value

Returns: true if successfully added.

template<class T >

void tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::cleanup ( bool success )

private

This function is used to cleanup a completed MCAS operation It removes each MCH placed during this operation, replacing it with the logical value.

template<class T >

bool tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::execute ( )

This function is called after all the CAS triples have been added to the operation.

It will attempt to apply the operation.

Returns: true if it replaced the values at each address with a new value

template<class T >

void tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::help_complete ( )

inlinevirtual

THis function overrides the virtual function in the OpRecord class It is called by the progress assurance scheme.

Upon its return the MCAS operation must be completed

Implements tervel::util::OpRecord.

template<class T >

bool tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::mcas_complete	(	int	start_pos,
		bool	wfmode = `false`
	)

private

This function is used to complete a currently executing MCAS operation It is most likely that this operation is in conflict with some other operation and that it was discover by the dereferencing of an MCH The MCH contains a reference to the row in the MCAS it is associated with and a reference to the final row in the mcas.

Using these two, we can complete the remaining rows.

Parameters

start_pos	the row to begin at
wfmode	if true it ignores the fail count because the operation is in the op_table

Returns: whether or not the mcas succeeded.

Loop for each row in the op, if helping complete another thread's MCAS Start at last known completed row.

template<class T >

bool tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::mcas_complete ( CasRow< T > * current_row )

private

Same as above, but it calculates the start_pos based on the current row then calls the above mcas_complete.

Parameters

current_row the last known completed row

Returns: where or not the mcas succeeded

template<class T >

T tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::mcas_remove	(	const int	pos,
		T	value
	)

private

This function insures that upon its return that *(cas_rows_[pos].address) no longer equals value.

Where value is an object that holds an RC bit mark. If the object is not a Helper for this operation, then the standard descriptor remove function is called. This is important to prevent the case where the stack increases beyond reasonable levels when multiple threads are helping to complete the same operation.

Parameters

pos	the cas_row which is blocked from completing its operation
value	the value read at the position

Returns: the new current value

template<class T >

bool tervel::algorithms::wf::mcas::MultiWordCompareAndSwap< T >::on_is_watched ( )

inlinevirtual

This function overrides the virtual function in the HP::Element class It returns whether or not this mcas class is being referenced by another threaded.

It is being referenced if any associated descriptor has a positive reference count or if there is a hazard point watch on it.