The transaction lock system. More...

#include <mysql/service_thd_wait.h>
#include <sys/types.h>
#include "ha_prototypes.h"
#include "lock0lock.h"
#include "lock0priv.h"
#include "os0thread-create.h"
#include "que0que.h"
#include "row0mysql.h"
#include "srv0mon.h"
#include "srv0start.h"
#include "my_dbug.h"

Classes
struct	waiting_trx_info_t
	A snapshot of information about a single slot which was in use at the moment of taking the snapshot. More...

Macros
#define	LOCK_MODULE_IMPLEMENTATION

Functions
static void	lock_wait_table_print (void)
	Print the contents of the lock_sys_t::waiting_threads array. More...

static void	lock_wait_table_release_slot (srv_slot_t *slot)
	Release a slot in the lock_sys_t::waiting_threads. More...

static srv_slot_t *	lock_wait_table_reserve_slot (que_thr_t *thr, std::chrono::steady_clock::duration wait_timeout)
	Reserves a slot in the thread table for the current user OS thread. More...

void	lock_wait_request_check_for_cycles ()
	Notifies the thread which analyzes wait-for-graph that there was at least one new edge added or modified ( trx->blocking_trx has changed ), so that the thread will know it has to analyze it. More...

void	lock_wait_suspend_thread (que_thr_t *thr)
	Puts a user OS thread to wait for a lock to be released. More...

static void	lock_wait_release_thread_if_suspended (que_thr_t *thr)
	Releases a user OS thread waiting for a lock to be released, if the thread is already suspended. More...

void	lock_reset_wait_and_release_thread_if_suspended (lock_t *lock)
	This function is a wrapper around several functions which need to be called in particular order to wake up a transaction waiting for a lock. More...

static void	lock_wait_try_cancel (trx_t *trx, bool timeout)

static void	lock_wait_check_and_cancel (const srv_slot_t *slot)
	Check if the thread lock wait has timed out. More...

bool	operator< (const waiting_trx_info_t &a, const waiting_trx_info_t &b)
	As we want to quickly find a given trx_t within the snapshot, we use a sorting criterion which is based on trx only. More...

static void	lock_wait_check_slots_for_timeouts ()
	Check all slots for user threads that are waiting on locks, and if they have exceeded the time limit. More...

static uint64_t	lock_wait_snapshot_waiting_threads (ut::vector< waiting_trx_info_t > &infos)
	Takes a snapshot of the content of slots which are in use. More...

static void	lock_wait_compute_initial_weights (const ut::vector< waiting_trx_info_t > &infos, const uint64_t table_reservations, ut::vector< trx_schedule_weight_t > &new_weights)
	Used to initialize schedule weights of nodes in wait-for-graph for the computation. More...

static void	lock_wait_build_wait_for_graph (ut::vector< waiting_trx_info_t > &infos, ut::vector< int > &outgoing)
	Analyzes content of the snapshot with information about slots in use, and builds a (subset of) list of edges from waiting transactions to blocking transactions, such that for each waiter we have one outgoing edge. More...

static void	lock_wait_rollback_deadlock_victim (trx_t *chosen_victim)
	Notifies the chosen_victim that it should roll back. More...

static size_t	lock_wait_find_latest_pos_on_cycle (const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos)
	Given the `infos` about transactions and indexes in `infos` which form a deadlock cycle, identifies the transaction with the largest `reservation_no`, that is the one which was the latest to join the cycle. More...

static ut::vector< uint >	lock_wait_rotate_so_pos_is_first (size_t first_pos, const ut::vector< uint > &cycle_ids)
	Rotates the deadlock cycle so that it starts from desired item. More...

template<typename T >
static ut::vector< T >	lock_wait_map_ids_to_trxs (const ut::vector< uint > &ids, const ut::vector< waiting_trx_info_t > &infos)
	A helper, which extracts transactions with given indexes from the `infos` array. More...

static ut::vector< trx_t * >	lock_wait_order_for_choosing_victim (const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos)
	Orders the transactions from deadlock cycle in such a backward-compatible way, from the point of view of algorithm with picks the victim. More...

static void	lock_wait_add_subtree_weight (ut::vector< trx_schedule_weight_t > &new_weights, const size_t parent_id, const size_t child_id)
	Performs new_weights[parent_id] += new_weights[child_id] with sanity checks. More...

static void	lock_wait_accumulate_weights (ut::vector< uint > &incoming_count, ut::vector< trx_schedule_weight_t > &new_weights, const ut::vector< int > &outgoing)
	Given a graph with at most one outgoing edge per node, and initial weight for each node, this function will compute for each node a partial sum of initial weights of the node and all nodes that can reach it in the graph. More...

static const srv_slot_t *	lock_wait_get_slot_if_still_reserved (const ut::vector< waiting_trx_info_t > &infos, const size_t id)
	Checks if info[id].slot is still in use and has not been freed and reserved again since we took the info snapshot ("ABA" type of race condition). More...

static void	lock_wait_publish_new_weights (const ut::vector< uint > &is_on_cycle, const ut::vector< waiting_trx_info_t > &infos, const ut::vector< trx_schedule_weight_t > &new_weights)
	Copies the newly computed schedule weights to the transactions fields. More...

static trx_t *	lock_wait_choose_victim (const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos)
	Given an array with information about all waiting transactions and indexes in it which form a deadlock cycle, picks the transaction to rollback. More...

static bool	lock_wait_trxs_are_still_in_slots (const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos)
	Given an array with information about all waiting transactions and indexes in it which form a deadlock cycle, checks if the transactions allegedly forming the deadlock have actually stayed in slots since we've last checked, as opposed to say, not leaving a slot, and/or re-entering the slot ("ABA" situation). More...

static bool	lock_wait_trxs_are_still_waiting (const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos)
	Given an array with information about all waiting transactions and indexes in it which form a deadlock cycle, checks if the transactions allegedly forming the deadlock have actually still wait for a lock, as opposed to being already notified about lock being granted or timeout, but still being present in the slot. More...

static ut::vector< uint >	lock_wait_rotate_cycle_ids_for_notification (const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos)

static ut::vector< uint >	lock_wait_rotate_cycle_ids_to_so_trx_is_first (const trx_t *trx, const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos)
	A helper function which rotates the deadlock cycle, so that the specified trx is the first one on the cycle. More...

static void	lock_wait_update_weights_on_cycle (const trx_t *chosen_victim, const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos, ut::vector< trx_schedule_weight_t > &new_weights)
	Finalizes the computation of new schedule weights, by providing missing information about transactions located on a deadlock cycle. More...

static ut::vector< const trx_t * >	lock_wait_trxs_rotated_for_notification (const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos)
	A helper function which rotates the deadlock cycle, so that the order of transactions in it is suitable for notification. More...

static void	lock_wait_handle_deadlock (trx_t *chosen_victim, const ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos, ut::vector< trx_schedule_weight_t > &new_weights)
	Handles a deadlock found, by notifying about it, rolling back the chosen victim and updating schedule weights of transactions on the deadlock cycle. More...

static bool	lock_wait_check_candidate_cycle (ut::vector< uint > &cycle_ids, const ut::vector< waiting_trx_info_t > &infos, ut::vector< trx_schedule_weight_t > &new_weights)
	Given an array with information about all waiting transactions and indexes in it which form a deadlock cycle, checks if the transactions allegedly forming the deadlock cycle, indeed are still waiting, and if so, chooses a victim and handles the deadlock. More...

static void	lock_wait_extract_cycle_ids (ut::vector< uint > &cycle_ids, const uint start, const ut::vector< int > &outgoing)
	Generates a list of `cycle_ids` by following `outgoing` edges from the `start`. More...

static void	lock_wait_find_and_handle_deadlocks (const ut::vector< waiting_trx_info_t > &infos, const ut::vector< int > &outgoing, ut::vector< trx_schedule_weight_t > &new_weights)
	Assuming that `infos` contains information about all waiting transactions, and `outgoing[i]` is the endpoint of wait-for edge going out of infos[i].trx, or -1 if the transaction is not waiting, it identifies and handles all cycles in the wait-for graph. More...

static void	lock_wait_compute_incoming_count (const ut::vector< int > &outgoing, ut::vector< uint > &incoming_count)
	Computes the number of incoming edges for each node of a given graph, in which each node has zero or one outgoing edge. More...

static void	lock_wait_compute_and_publish_weights_except_cycles (const ut::vector< waiting_trx_info_t > &infos, const uint64_t table_reservations, const ut::vector< int > &outgoing, ut::vector< trx_schedule_weight_t > &new_weights)
	Given the `infos` snapshot about transactions, the value of lock_wait_table_reservations before taking the snapshot and the edges of the wait-for-graph relation between the transactions in the snapshot, computes the schedule weight for each transaction, which is the sum of initial weight of the transaction and all transactions that are blocked by it. More...

static void	lock_wait_update_schedule_and_check_for_deadlocks ()
	Takes a snapshot of transactions in waiting currently in slots, updates their schedule weights, searches for deadlocks among them and resolves them. More...

void	lock_wait_timeout_thread ()
	A thread which wakes up threads whose lock wait may have lasted too long, analyzes wait-for-graph changes, checks for deadlocks and resolves them, and updates schedule weights. More...

Variables
static uint64_t	lock_wait_table_reservations = 0
	Counts number of calls to lock_wait_table_reserve_slot. More...

Detailed Description

The transaction lock system.

Created 25/5/2010 Sunny Bains

Macro Definition Documentation

◆ LOCK_MODULE_IMPLEMENTATION

#define LOCK_MODULE_IMPLEMENTATION

Function Documentation

◆ lock_reset_wait_and_release_thread_if_suspended()

void lock_reset_wait_and_release_thread_if_suspended ( lock_t * lock )

This function is a wrapper around several functions which need to be called in particular order to wake up a transaction waiting for a lock.

You should not call lock_wait_release_thread_if_suspended(thr) directly, but rather use this wrapper, as this makes it much easier to reason about all possible states in which lock, trx, and thr can be. It makes sure that trx is woken up exactly once, and only if it already went to sleep.

Parameters

[in,out] lock The lock for which lock->trx is waiting

◆ lock_wait_accumulate_weights()

static void lock_wait_accumulate_weights	(	ut::vector< uint > &	incoming_count,
		ut::vector< trx_schedule_weight_t > &	new_weights,
		const ut::vector< int > &	outgoing
	)

static

Given a graph with at most one outgoing edge per node, and initial weight for each node, this function will compute for each node a partial sum of initial weights of the node and all nodes that can reach it in the graph.

Parameters

[in,out]	incoming_count	The value of incoming_count[id] should match the number of edges incoming to the node id. In other words \|x : outgoing[x] == id\|. This function will modify entries in this array, so that after the call, nodes on cycles will have value 1, and others will have 0.
[in,out]	new_weights	Should contain initial weight for each node. This function will modify entries for nodes which are not on cycles, so that new_weights[id] will be the sum of initial weights of the node `id` and all nodes that can reach it by one or more outgoing[] edges.
[in]	outgoing	The ids of edge endpoints. If outgoing[id] == -1, then there is no edge going out of id, otherwise there is an edge from id to outgoing[id].

◆ lock_wait_add_subtree_weight()

static void lock_wait_add_subtree_weight	(	ut::vector< trx_schedule_weight_t > &	new_weights,
		const size_t	parent_id,
		const size_t	child_id
	)

static

Performs new_weights[parent_id] += new_weights[child_id] with sanity checks.

Parameters

[in,out]	new_weights	schedule weights of transactions initialized and perhaps partially accumulated already. This function will modify new_weights[parent_id] by adding new_weights[child_id] to it.
[in]	parent_id	index of the node to update
[in]	child_id	index of the node which weight should be added to the parent's weight.

◆ lock_wait_build_wait_for_graph()

static void lock_wait_build_wait_for_graph	(	ut::vector< waiting_trx_info_t > &	infos,
		ut::vector< int > &	outgoing
	)

static

Analyzes content of the snapshot with information about slots in use, and builds a (subset of) list of edges from waiting transactions to blocking transactions, such that for each waiter we have one outgoing edge.

Parameters

[in]	infos	information about all waiting transactions
[out]	outgoing	The outgoing[from] will contain either the index such that infos[outgoing[from]].trx is the reason infos[from].trx has to wait, or -1 if the reason for waiting is not among transactions in infos[].trx.

We are going to use int and uint to store positions within infos

◆ lock_wait_check_and_cancel()

static void lock_wait_check_and_cancel ( const srv_slot_t * slot )

static

Check if the thread lock wait has timed out.

Release its locks if the wait has actually timed out.

Parameters

slot	in: slot reserved by a user thread when the wait started

◆ lock_wait_check_candidate_cycle()

static bool lock_wait_check_candidate_cycle	(	ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos,
		ut::vector< trx_schedule_weight_t > &	new_weights
	)

static

Given an array with information about all waiting transactions and indexes in it which form a deadlock cycle, checks if the transactions allegedly forming the deadlock cycle, indeed are still waiting, and if so, chooses a victim and handles the deadlock.

Parameters

[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions
[in,out]	new_weights	schedule weights of transactions computed for all transactions except those which are on the cycle. In case it is a real deadlock cycle, this function will update the new_weights entries for transactions involved in this cycle (as it will unfold to a path, and schedule weight can be thus computed)

Returns: true if the cycle found was indeed a deadlock cycle, false if it was a false positive

◆ lock_wait_check_slots_for_timeouts()

static void lock_wait_check_slots_for_timeouts ( )

static

Check all slots for user threads that are waiting on locks, and if they have exceeded the time limit.

◆ lock_wait_choose_victim()

static trx_t * lock_wait_choose_victim	(	const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos
	)

static

Given an array with information about all waiting transactions and indexes in it which form a deadlock cycle, picks the transaction to rollback.

Parameters

[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions

Returns: the transaction chosen as a victim

◆ lock_wait_compute_and_publish_weights_except_cycles()

static void lock_wait_compute_and_publish_weights_except_cycles	(	const ut::vector< waiting_trx_info_t > &	infos,
		const uint64_t	table_reservations,
		const ut::vector< int > &	outgoing,
		ut::vector< trx_schedule_weight_t > &	new_weights
	)

static

Given the infos snapshot about transactions, the value of lock_wait_table_reservations before taking the snapshot and the edges of the wait-for-graph relation between the transactions in the snapshot, computes the schedule weight for each transaction, which is the sum of initial weight of the transaction and all transactions that are blocked by it.

This definition does not apply to transactions on deadlock cycles, thus this function will not compute the final schedule weight for transactions on the cycle, but rather leave it as the partial sum of the tree rooted at the transaction hanging off the cycle.

Parameters

[in]	infos	Information about all waiting transactions
[in]	table_reservations	value of lock_wait_table_reservations at before taking the `infos`snapshot
[in]	outgoing	The ids of edge endpoints. If outgoing[id] == -1, then there is no edge going out of id, otherwise infos[id].trx waits for infos[outgoing[id]].trx
[out]	new_weights	schedule weights of transactions computed for all transactions except those which are on a cycle. For those on cycle we only compute the partial sum of the weights in the tree hanging off the cycle.

◆ lock_wait_compute_incoming_count()

static void lock_wait_compute_incoming_count	(	const ut::vector< int > &	outgoing,
		ut::vector< uint > &	incoming_count
	)

static

Computes the number of incoming edges for each node of a given graph, in which each node has zero or one outgoing edge.

Parameters

[in]	outgoing	The ids of edge endpoints. If outgoing[id] == -1, then there is no edge going out of id, otherwise there is an edge from id to outgoing[id].
[out]	incoming_count	The place to store the results. After the call the incoming_count[id] will be the number of edges ending in id.

◆ lock_wait_compute_initial_weights()

static void lock_wait_compute_initial_weights	(	const ut::vector< waiting_trx_info_t > &	infos,
		const uint64_t	table_reservations,
		ut::vector< trx_schedule_weight_t > &	new_weights
	)

static

Used to initialize schedule weights of nodes in wait-for-graph for the computation.

Initially all nodes have weight 1, except for nodes which waited very long, for which we set the weight to WEIGHT_BOOST

Parameters

[in]	infos	information about all waiting transactions
[in]	table_reservations	value of lock_wait_table_reservations at before taking the `infos` snapshot
[out]	new_weights	place to store initial weights of nodes

◆ lock_wait_extract_cycle_ids()

static void lock_wait_extract_cycle_ids	(	ut::vector< uint > &	cycle_ids,
		const uint	start,
		const ut::vector< int > &	outgoing
	)

static

Generates a list of cycle_ids by following outgoing edges from the start.

Parameters

[in,out]	cycle_ids	will contain the list of ids on cycle
[in]	start	the first id on the cycle
[in]	outgoing	the ids of edge endpoints: id -> outgoing[id]

◆ lock_wait_find_and_handle_deadlocks()

static void lock_wait_find_and_handle_deadlocks	(	const ut::vector< waiting_trx_info_t > &	infos,
		const ut::vector< int > &	outgoing,
		ut::vector< trx_schedule_weight_t > &	new_weights
	)

static

Assuming that infos contains information about all waiting transactions, and outgoing[i] is the endpoint of wait-for edge going out of infos[i].trx, or -1 if the transaction is not waiting, it identifies and handles all cycles in the wait-for graph.

Parameters

[in]	infos	Information about all waiting transactions
[in]	outgoing	The ids of edge endpoints. If outgoing[id] == -1, then there is no edge going out of id, otherwise infos[id].trx waits for infos[outgoing[id]].trx
[in,out]	new_weights	schedule weights of transactions computed for all transactions except those which are on a cycle. In case we find a real deadlock cycle, and decide to rollback one of transactions, this function will update the new_weights entries for transactions involved in this cycle (as it will unfold to a path, and schedule weight can be thus computed)

We are going to use int and uint to store positions within infos

◆ lock_wait_find_latest_pos_on_cycle()

static size_t lock_wait_find_latest_pos_on_cycle	(	const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos
	)

static

Given the infos about transactions and indexes in infos which form a deadlock cycle, identifies the transaction with the largest reservation_no, that is the one which was the latest to join the cycle.

Parameters

[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions

Returns: position in cycle_ids, such that infos[cycle_ids[pos]].reservation_no is the largest

◆ lock_wait_get_slot_if_still_reserved()

static const srv_slot_t * lock_wait_get_slot_if_still_reserved	(	const ut::vector< waiting_trx_info_t > &	infos,
		const size_t	id
	)

static

Checks if info[id].slot is still in use and has not been freed and reserved again since we took the info snapshot ("ABA" type of race condition).

Parameters

[in]	infos	information about all waiting transactions
[in]	id	index to retrieve

Returns: info[id].slot if the slot was reserved whole time since taking the info snapshot. Otherwise: nullptr.

◆ lock_wait_handle_deadlock()

static void lock_wait_handle_deadlock	(	trx_t *	chosen_victim,
		const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos,
		ut::vector< trx_schedule_weight_t > &	new_weights
	)

static

Handles a deadlock found, by notifying about it, rolling back the chosen victim and updating schedule weights of transactions on the deadlock cycle.

Parameters

[in,out]	chosen_victim	the transaction to roll back
[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions
[in,out]	new_weights	schedule weights of transactions computed for all transactions except those which are on a cycle. This function will update the new_weights entries for transactions involved in deadlock cycle (as it will unfold to a path, and schedule weight can be thus computed)

◆ lock_wait_map_ids_to_trxs()

template<typename T >

static ut::vector< T > lock_wait_map_ids_to_trxs	(	const ut::vector< uint > &	ids,
		const ut::vector< waiting_trx_info_t > &	infos
	)

static

A helper, which extracts transactions with given indexes from the infos array.

Parameters

[in]	ids	indexes of transactions in the `infos` array to extract
[in]	infos	information about all waiting transactions

Returns: An array formed by infos[ids[i]].trx

◆ lock_wait_order_for_choosing_victim()

static ut::vector< trx_t * > lock_wait_order_for_choosing_victim	(	const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos
	)

static

Orders the transactions from deadlock cycle in such a backward-compatible way, from the point of view of algorithm with picks the victim.

From correctness point of view this could be a no-op, but we have test cases which assume some determinism in that which trx is selected as the victim. These tests usually depend on the old behaviour in which the order in which trxs attempted to wait was meaningful. In the past we have only considered two candidates for victim: (a) the transaction which closed the cycle by adding last wait-for edge (b) the transaction which is waiting for (a) and it favored to pick (a) in case of ties. To make these test pass we find the trx with most recent reservation_no (a), and the one before it in the cycle (b), and move them to the end of collection So that we consider them in order: ...,...,...,(b),(a), resolving ties by picking the latest one as victim. In other words we rotate the cycle so that the most recent waiter becomes the last.

Parameters

[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions

Returns: transactions from the deadlock cycle sorted in the optimal way for choosing a victim

◆ lock_wait_publish_new_weights()

static void lock_wait_publish_new_weights	(	const ut::vector< uint > &	is_on_cycle,
		const ut::vector< waiting_trx_info_t > &	infos,
		const ut::vector< trx_schedule_weight_t > &	new_weights
	)

static

Copies the newly computed schedule weights to the transactions fields.

Ignores transactions which take part in cycles, because for them we don't have a final value of the schedule weight yet.

Parameters

[in]	is_on_cycle	A positive value is_on_cycle[id] means that `id` is on a cycle in the graph.
[in]	infos	information about all waiting transactions
[in]	new_weights	schedule weights of transactions computed for all transactions except those which are on a cycle.

◆ lock_wait_release_thread_if_suspended()

static void lock_wait_release_thread_if_suspended ( que_thr_t * thr )

static

Releases a user OS thread waiting for a lock to be released, if the thread is already suspended.

Please do not call it directly, but rather use the lock_reset_wait_and_release_thread_if_suspended() wrapper.

Parameters

[in] thr query thread associated with the user OS thread

◆ lock_wait_request_check_for_cycles()

void lock_wait_request_check_for_cycles ( )

Notifies the thread which analyzes wait-for-graph that there was at least one new edge added or modified ( trx->blocking_trx has changed ), so that the thread will know it has to analyze it.

◆ lock_wait_rollback_deadlock_victim()

static void lock_wait_rollback_deadlock_victim ( trx_t * chosen_victim )

static

Notifies the chosen_victim that it should roll back.

Parameters

[in,out] chosen_victim the transaction that should be rolled back

◆ lock_wait_rotate_cycle_ids_for_notification()

static ut::vector< uint > lock_wait_rotate_cycle_ids_for_notification	(	const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos
	)

static

◆ lock_wait_rotate_cycle_ids_to_so_trx_is_first()

static ut::vector< uint > lock_wait_rotate_cycle_ids_to_so_trx_is_first	(	const trx_t *	trx,
		const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos
	)

static

A helper function which rotates the deadlock cycle, so that the specified trx is the first one on the cycle.

Parameters

[in]	trx	The transaction we wish to be the first after the rotation. There must exist x, such that infos[cycle_ids[x]].trx == trx.
[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions

Returns: Assuming that infos[cycle_ids[x]].trx == trx the result will be a copy of [cycle_ids[x],cycle_ids[x+1 mod N],...,cycle_ids[x-1+N mod N]].

◆ lock_wait_rotate_so_pos_is_first()

static ut::vector< uint > lock_wait_rotate_so_pos_is_first	(	size_t	first_pos,
		const ut::vector< uint > &	cycle_ids
	)

static

Rotates the deadlock cycle so that it starts from desired item.

Parameters

[in]	first_pos	the position which should become first after rotation
[in]	cycle_ids	the array to rotate

Returns: a copy of cycle_ids rotated in such a way, that the element which was at position first_pos is now the first

◆ lock_wait_snapshot_waiting_threads()

static uint64_t lock_wait_snapshot_waiting_threads ( ut::vector< waiting_trx_info_t > & infos )

static

Takes a snapshot of the content of slots which are in use.

Parameters

[out] infos Will contain the information about slots which are in use

Returns: value of lock_wait_table_reservations before taking the snapshot

◆ lock_wait_suspend_thread()

void lock_wait_suspend_thread ( que_thr_t * thr )

Puts a user OS thread to wait for a lock to be released.

If an error occurs during the wait trx->error_state associated with thr is != DB_SUCCESS when we return. DB_INTERRUPTED, DB_LOCK_WAIT_TIMEOUT and DB_DEADLOCK are possible errors. DB_DEADLOCK is returned if selective deadlock resolution chose this transaction as a victim. in: query thread associated with the user OS thread

◆ lock_wait_table_print()

static void lock_wait_table_print ( void )

static

Print the contents of the lock_sys_t::waiting_threads array.

◆ lock_wait_table_release_slot()

static void lock_wait_table_release_slot ( srv_slot_t * slot )

static

Release a slot in the lock_sys_t::waiting_threads.

Adjust the array last pointer if there are empty slots towards the end of the table.

Parameters

slot	in: slot to release

◆ lock_wait_table_reserve_slot()

static srv_slot_t * lock_wait_table_reserve_slot	(	que_thr_t *	thr,
		std::chrono::steady_clock::duration	wait_timeout
	)

static

Reserves a slot in the thread table for the current user OS thread.

Returns: reserved slot

Parameters

thr	in: query thread associated with the user OS thread
wait_timeout	in: lock wait timeout value

◆ lock_wait_timeout_thread()

void lock_wait_timeout_thread ( )

A thread which wakes up threads whose lock wait may have lasted too long, analyzes wait-for-graph changes, checks for deadlocks and resolves them, and updates schedule weights.

A thread which wakes up threads whose lock wait may have lasted too long.

The last time we've checked for timeouts.

◆ lock_wait_trxs_are_still_in_slots()

static bool lock_wait_trxs_are_still_in_slots	(	const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos
	)

static

Given an array with information about all waiting transactions and indexes in it which form a deadlock cycle, checks if the transactions allegedly forming the deadlock have actually stayed in slots since we've last checked, as opposed to say, not leaving a slot, and/or re-entering the slot ("ABA" situation).

This is done by comparing the current reservation_no for each slot, with the reservation_no from the info snapshot.

Parameters

[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions

Returns: true if all given transactions resided in their slots for the whole time since the snapshot was taken, and in particular are still there right now

◆ lock_wait_trxs_are_still_waiting()

static bool lock_wait_trxs_are_still_waiting	(	const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos
	)

static

Given an array with information about all waiting transactions and indexes in it which form a deadlock cycle, checks if the transactions allegedly forming the deadlock have actually still wait for a lock, as opposed to being already notified about lock being granted or timeout, but still being present in the slot.

This is done by checking trx->lock.wait_lock under exclusive global lock_sys latch.

Parameters

[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions

Returns: true if all given transactions are still waiting for locks

◆ lock_wait_trxs_rotated_for_notification()

static ut::vector< const trx_t * > lock_wait_trxs_rotated_for_notification	(	const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos
	)

static

A helper function which rotates the deadlock cycle, so that the order of transactions in it is suitable for notification.

From correctness perspective this could be a no-op, but we have tests which depend on deterministic output from such notifications, and we want to be backward compatible.

Parameters

[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions

Returns: the transactions from cycle_ids rotated in backward-compatible way

◆ lock_wait_try_cancel()

static void lock_wait_try_cancel	(	trx_t *	trx,
		bool	timeout
	)

static

◆ lock_wait_update_schedule_and_check_for_deadlocks()

static void lock_wait_update_schedule_and_check_for_deadlocks ( )

static

Takes a snapshot of transactions in waiting currently in slots, updates their schedule weights, searches for deadlocks among them and resolves them.

◆ lock_wait_update_weights_on_cycle()

static void lock_wait_update_weights_on_cycle	(	const trx_t *	chosen_victim,
		const ut::vector< uint > &	cycle_ids,
		const ut::vector< waiting_trx_info_t > &	infos,
		ut::vector< trx_schedule_weight_t > &	new_weights
	)

static

Finalizes the computation of new schedule weights, by providing missing information about transactions located on a deadlock cycle.

Assuming that we know the list of transactions on a cycle, which transaction will be chosen as a victim, and what are the weights of trees hanging off the cycle, it computes the final schedule weight for each of transactions to be equal to its weight in a graph with the victim's node missing

Parameters

[in]	chosen_victim	The transaction chosen to be rolled back
[in]	cycle_ids	indexes in `infos` array, of transactions forming the deadlock cycle
[in]	infos	information about all waiting transactions
[in,out]	new_weights	schedule weights of transactions computed for all transactions except those which are on a cycle. This function will update the new_weights entries for transactions involved in deadlock cycle (as it will unfold to a path, and schedule weight can be thus computed)

◆ operator<()

bool operator<	(	const waiting_trx_info_t &	a,
		const waiting_trx_info_t &	b
	)

As we want to quickly find a given trx_t within the snapshot, we use a sorting criterion which is based on trx only.

We use the pointer address, as any deterministic rule without ties will do.

Variable Documentation

◆ lock_wait_table_reservations

uint64_t lock_wait_table_reservations = 0

static

Counts number of calls to lock_wait_table_reserve_slot.

It is protected by lock_wait_mutex. Current value of this counter is stored in the slot a transaction has chosen for sleeping during suspension, and thus serves as "reservation number" which can be used to check if the owner of the slot has changed (perhaps multiple times, in "ABA" manner).

Classes

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ LOCK_MODULE_IMPLEMENTATION

Function Documentation

◆ lock_reset_wait_and_release_thread_if_suspended()

◆ lock_wait_accumulate_weights()

◆ lock_wait_add_subtree_weight()

◆ lock_wait_build_wait_for_graph()

◆ lock_wait_check_and_cancel()

◆ lock_wait_check_candidate_cycle()

◆ lock_wait_check_slots_for_timeouts()

◆ lock_wait_choose_victim()

◆ lock_wait_compute_and_publish_weights_except_cycles()

◆ lock_wait_compute_incoming_count()

◆ lock_wait_compute_initial_weights()

◆ lock_wait_extract_cycle_ids()

◆ lock_wait_find_and_handle_deadlocks()

◆ lock_wait_find_latest_pos_on_cycle()

◆ lock_wait_get_slot_if_still_reserved()

◆ lock_wait_handle_deadlock()

◆ lock_wait_map_ids_to_trxs()

◆ lock_wait_order_for_choosing_victim()

◆ lock_wait_publish_new_weights()

◆ lock_wait_release_thread_if_suspended()

◆ lock_wait_request_check_for_cycles()

◆ lock_wait_rollback_deadlock_victim()

◆ lock_wait_rotate_cycle_ids_for_notification()

◆ lock_wait_rotate_cycle_ids_to_so_trx_is_first()

◆ lock_wait_rotate_so_pos_is_first()

◆ lock_wait_snapshot_waiting_threads()

◆ lock_wait_suspend_thread()

◆ lock_wait_table_print()

◆ lock_wait_table_release_slot()

◆ lock_wait_table_reserve_slot()

◆ lock_wait_timeout_thread()

◆ lock_wait_trxs_are_still_in_slots()

◆ lock_wait_trxs_are_still_waiting()

◆ lock_wait_trxs_rotated_for_notification()

◆ lock_wait_try_cancel()

◆ lock_wait_update_schedule_and_check_for_deadlocks()

◆ lock_wait_update_weights_on_cycle()

◆ operator<()

Variable Documentation

◆ lock_wait_table_reservations