Concurrent data structure, which allows to track concurrently performed operations which locally might be dis-ordered. More...

#include <ut0link_buf.h>

Public Types
typedef Position	Distance
	Type used to express distance between two positions. More...

Public Member Functions
	Link_buf (size_t capacity)
	Constructs the link buffer. More...

	Link_buf ()

	Link_buf (Link_buf &&rhs)

	Link_buf (const Link_buf &rhs)=delete

Link_buf &	operator= (Link_buf &&rhs)

Link_buf &	operator= (const Link_buf &rhs)=delete

	~Link_buf ()
	Destructs the link buffer. More...

void	add_link (Position from, Position to)
	Add a directed link between two given positions. More...

void	add_link_advance_tail (Position from, Position to)
	Add a directed link between two given positions. More...

template<typename Stop_condition >
bool	advance_tail_until (Stop_condition stop_condition, uint32_t max_retry=1)
	Advances the tail pointer in the buffer by following connected path created by links. More...

bool	advance_tail ()
	Advances the tail pointer in the buffer without additional condition for stop. More...

size_t	capacity () const

Position	tail () const

bool	has_space (Position position)
	Checks if there is space to add link at given position. More...

void	validate_no_links (Position begin, Position end)
	Validates (using assertions) that there are no links set in the range [begin, end). More...

void	validate_no_links ()
	Validates (using assertions) that there no links at all. More...

Private Member Functions
size_t	slot_index (Position position) const
	Translates position expressed in original unit to position in the m_links (which is a ring buffer). More...

bool	next_position (Position position, Position &next)
	Computes next position by looking into slots array and following single link which starts in provided position. More...

void	free ()
	Deallocated memory, if it was allocated. More...

Private Attributes
size_t	m_capacity
	Capacity of the buffer. More...

std::atomic< Distance > *	m_links
	Pointer to the ring buffer (unaligned). More...

std::atomic< Position >	m_tail
	Tail pointer in the buffer (expressed in original unit). More...

Detailed Description

template<typename Position = uint64_t>
class Link_buf< Position >

Concurrent data structure, which allows to track concurrently performed operations which locally might be dis-ordered.

This data structure is informed about finished concurrent operations and tracks up to which point in a total order all operations have been finished (there are no holes).

It also allows to limit the last period in which there might be holes. These holes refer to unfinished concurrent operations, which precede in the total order some operations that are already finished.

Threads might concurrently report finished operations (lock-free).

Threads might ask for maximum currently known position in total order, up to which all operations are already finished (lock-free).

Single thread might track the reported finished operations and update maximum position in total order, up to which all operations are done.

You might look at current usages of this data structure in log0buf.cc.

Member Typedef Documentation

◆ Distance

template<typename Position = uint64_t>

typedef Position Link_buf< Position >::Distance

Type used to express distance between two positions.

It could become a parameter of template if it was useful. However there is no such need currently.

Constructor & Destructor Documentation

◆ Link_buf() [1/4]

template<typename Position >

Link_buf< Position >::Link_buf ( size_t capacity )

explicit

Constructs the link buffer.

Allocated memory for the links. Initializes the tail pointer with 0.

Parameters

[in] capacity number of slots in the ring buffer

◆ Link_buf() [2/4]

template<typename Position >

Link_buf< Position >::Link_buf

◆ Link_buf() [3/4]

template<typename Position >

Link_buf< Position >::Link_buf ( Link_buf< Position > && rhs )

◆ Link_buf() [4/4]

template<typename Position = uint64_t>

Link_buf< Position >::Link_buf ( const Link_buf< Position > & rhs )

delete

◆ ~Link_buf()

template<typename Position >

Link_buf< Position >::~Link_buf

Destructs the link buffer.

Deallocates memory for the links.

Member Function Documentation

◆ add_link()

template<typename Position >

void Link_buf< Position >::add_link	(	Position	from,
		Position	to
	)

inline

Add a directed link between two given positions.

It is user's responsibility to ensure that there is space for the link. This is because it can be useful to ensure much earlier that there is space.

Parameters

[in]	from	position where the link starts
[in]	to	position where the link ends (from -> to)

◆ add_link_advance_tail()

template<typename Position >

void Link_buf< Position >::add_link_advance_tail	(	Position	from,
		Position	to
	)

inline

Add a directed link between two given positions.

It is user's responsibility to ensure that there is space for the link. This is because it can be useful to ensure much earlier that there is space. In addition, advances the tail pointer in the buffer if possible.

Parameters

[in]	from	position where the link starts
[in]	to	position where the link ends (from -> to)

◆ advance_tail()

template<typename Position >

bool Link_buf< Position >::advance_tail

inline

Advances the tail pointer in the buffer without additional condition for stop.

Stops at missing outgoing link.

See also: advance_tail_until()

Returns: true if and only if the pointer has been advanced

◆ advance_tail_until()

template<typename Position >

template<typename Stop_condition >

bool Link_buf< Position >::advance_tail_until	(	Stop_condition	stop_condition,
		uint32_t	max_retry = `1`
	)

Advances the tail pointer in the buffer by following connected path created by links.

Starts at current position of the pointer. Stops when the provided function returns true.

Parameters

[in]	stop_condition	function used as a stop condition; (lsn_t prev, lsn_t next) -> bool; returns false if we should follow the link prev->next, true to stop
[in]	max_retry	max fails to retry

Returns: true if and only if the pointer has been advanced

◆ capacity()

template<typename Position >

size_t Link_buf< Position >::capacity

inline

Returns: capacity of the ring buffer

◆ free()

template<typename Position >

void Link_buf< Position >::free

private

Deallocated memory, if it was allocated.

◆ has_space()

template<typename Position >

bool Link_buf< Position >::has_space ( Position position )

inline

Checks if there is space to add link at given position.

User has to use this function before adding the link, and should wait until the free space exists.

Parameters

[in] position position to check

Returns: true if and only if the space is free

◆ next_position()

template<typename Position >

bool Link_buf< Position >::next_position	(	Position	position,
		Position &	next
	)

inlineprivate

Computes next position by looking into slots array and following single link which starts in provided position.

Parameters

[in]	position	position to start
[out]	next	computed next position

Returns: false if there was no link, true otherwise

◆ operator=() [1/2]

template<typename Position = uint64_t>

Link_buf & Link_buf< Position >::operator= ( const Link_buf< Position > & rhs )

delete

◆ operator=() [2/2]

template<typename Position >

Link_buf< Position > & Link_buf< Position >::operator= ( Link_buf< Position > && rhs )

◆ slot_index()

template<typename Position >

size_t Link_buf< Position >::slot_index ( Position position ) const

inlineprivate

Translates position expressed in original unit to position in the m_links (which is a ring buffer).

Parameters

[in] position position in original unit

Returns: position in the m_links

◆ tail()

template<typename Position >

Position Link_buf< Position >::tail

inline

Returns: the tail pointer

◆ validate_no_links() [1/2]

template<typename Position >

void Link_buf< Position >::validate_no_links

Validates (using assertions) that there no links at all.

◆ validate_no_links() [2/2]

template<typename Position >

void Link_buf< Position >::validate_no_links	(	Position	begin,
		Position	end
	)

Validates (using assertions) that there are no links set in the range [begin, end).

Member Data Documentation

◆ m_capacity

template<typename Position = uint64_t>

size_t Link_buf< Position >::m_capacity

private

Capacity of the buffer.

◆ m_links

template<typename Position = uint64_t>

std::atomic<Distance>* Link_buf< Position >::m_links

private

Pointer to the ring buffer (unaligned).

◆ m_tail

template<typename Position = uint64_t>

std::atomic<Position> Link_buf< Position >::m_tail

private

Tail pointer in the buffer (expressed in original unit).

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

storage/innobase/include/ut0link_buf.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Distance

Constructor & Destructor Documentation

◆ Link_buf() [1/4]

◆ Link_buf() [2/4]

◆ Link_buf() [3/4]

◆ Link_buf() [4/4]

◆ ~Link_buf()

Member Function Documentation

◆ add_link()

◆ add_link_advance_tail()

◆ advance_tail()

◆ advance_tail_until()

◆ capacity()

◆ free()

◆ has_space()

◆ next_position()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ slot_index()

◆ tail()

◆ validate_no_links() [1/2]

◆ validate_no_links() [2/2]

Member Data Documentation

◆ m_capacity

◆ m_links

◆ m_tail