telamon_simulator Namespace Reference

This module encapsulates the implementation of the simulator. More...

Namespaces
	telamon_private
	This module serves as a wrapper for the private data in the telamon_simulator module.
	versioning
	This modules contains the operatios and classes related to versioning of the objects used in the simulated algorihtm.

Classes
class	OperationRecord
	A class which represents a single operation contained in a OperationRecordBox. More...
class	OperationRecordBox
	A class which represents a single operation stored in the help queue. More...
class	ContentionFailureCounter
	Measures the contention which was encountered during simulation. More...
class	WaitFreeSimulatorHandle
	A handle class which is used to obtain access to the wait-free simulator. More...

Enumerations
enum class	CasStatus : char { Pending , Success , Failure }
	Represents the status of a CAS primitive.

Variables
template<typename Commit >
concept	Commits
	Requires commit to be iterable and its items to satisfy CasWithVersioning. More...
template<typename LockFree >
concept	NormalizedRepresentation
	Here are the operations which are required to be described in the lock-free algorithm in order to use the simulation. There are 3 types which the lock-free has to define according to its specifics as well as 3 functions. More...
template<typename Cas >
concept	CasWithVersioning
	Solves the ABA problem. More...

Detailed Description

This module encapsulates the implementation of the simulator.

Variable Documentation

CasWithVersioning

template<typename Cas >

concept telamon_simulator::CasWithVersioning

Initial value:

= requires (Cas cas_, CasStatus status, ContentionFailureCounter &failures, CasStatus expected, CasStatus desired){
    { cas_.has_modified_bit() } -> std::same_as<bool>;
    { cas_.clear_bit() };
    { cas_.state() } -> std::same_as<CasStatus>;
    { cas_.set_state(status) };
    { cas_.swap_state(expected, desired) } -> std::same_as<bool>;
    { cas_.execute(failures) } -> std::same_as<nonstd::expected<bool, std::monostate>>;
}

Solves the ABA problem.

See p.15 of the paper

Template Parameters

Cas	CasDescriptor primitive

About execute: Returns either a bool marking whether the CAS was executed successfully or an error marking there was contention during the execution

Commits

template<typename Commit >

concept telamon_simulator::Commits

Initial value:

= requires (Commit desc) {
    requires std::ranges::input_range<Commit>;
    requires CasWithVersioning<std::ranges::range_value_t<Commit>>;
}

Requires commit to be iterable and its items to satisfy CasWithVersioning.

Template Parameters

Commit

Structure which represents a commit point

NormalizedRepresentation

template<typename LockFree >

concept telamon_simulator::NormalizedRepresentation

Initial value:

= requires (LockFree lf,
                                             ContentionFailureCounter &contention,
                                             const typename LockFree::Input &inp,
                                             const typename LockFree::Commit &desc,
                                             const nonstd::expected<std::monostate, std::optional<int>> &executed
){
    typename LockFree::Input;
    typename LockFree::Output;
    typename LockFree::Commit;
 
    requires Commits<typename LockFree::Commit>;
    requires std::is_copy_constructible_v<typename LockFree::Commit>;
 
    { lf.generator(inp, contention) } -> std::same_as<std::optional<typename LockFree::Commit>>;
    { lf.wrap_up(executed, desc, contention) } -> std::same_as<nonstd::expected<std::optional<typename LockFree::Output>, std::monostate>>;
    { lf.fast_path(inp, contention) } -> std::same_as<std::optional<typename LockFree::Output>>;
}

Here are the operations which are required to be described in the lock-free algorithm in order to use the simulation. There are 3 types which the lock-free has to define according to its specifics as well as 3 functions.

Template Parameters

LockFree

The lock-free algorithm which is being simulated

Thegenerator and wrap_up functions correspond to the first and third stage of the algorithm operation. The fast path represents the steps which are used when the operation in executed as lock-free.