 |
MySQL 9.1.0
Source Code Documentation
|
|
MySQL 9.1.0
Source Code Documentation
|
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... | |
The transaction lock system.
Created 25/5/2010 Sunny Bains
| #define LOCK_MODULE_IMPLEMENTATION |
| 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.
| [in,out] | lock | The lock for which lock->trx is waiting |
|
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.
| [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]. |
|
static |
Performs new_weights[parent_id] += new_weights[child_id] with sanity checks.
| [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. |
|
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.
| [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
|
static |
Check if the thread lock wait has timed out.
Release its locks if the wait has actually timed out.
| slot | in: slot reserved by a user thread when the wait started |
|
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.
| [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) |
|
static |
Check all slots for user threads that are waiting on locks, and if they have exceeded the time limit.
|
static |
Given an array with information about all waiting transactions and indexes in it which form a deadlock cycle, picks the transaction to rollback.
| [in] | cycle_ids | indexes in infos array, of transactions forming the deadlock cycle |
| [in] | infos | information about all waiting transactions |
|
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.
| [in] | infos | Information about all waiting transactions |
| [in] | table_reservations | value of lock_wait_table_reservations at before taking the infossnapshot |
| [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. |
|
static |
Computes the number of incoming edges for each node of a given graph, in which each node has zero or one outgoing edge.
| [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. |
|
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
| [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 |
|
static |
Generates a list of cycle_ids by following outgoing edges from the start.
| [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] |
|
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.
| [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
|
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.
| [in] | cycle_ids | indexes in infos array, of transactions forming the deadlock cycle |
| [in] | infos | information about all waiting transactions |
|
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).
| [in] | infos | information about all waiting transactions |
| [in] | id | index to retrieve |
|
static |
Handles a deadlock found, by notifying about it, rolling back the chosen victim and updating schedule weights of transactions on the deadlock cycle.
| [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) |
|
static |
A helper, which extracts transactions with given indexes from the infos array.
| [in] | ids | indexes of transactions in the infos array to extract |
| [in] | infos | information about all waiting transactions |
|
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.
| [in] | cycle_ids | indexes in infos array, of transactions forming the deadlock cycle |
| [in] | infos | information about all waiting transactions |
|
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.
| [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. |
|
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.
| [in] | thr | query thread associated with the user OS thread |
| 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.
|
static |
Notifies the chosen_victim that it should roll back.
| [in,out] | chosen_victim | the transaction that should be rolled back |
|
static |
|
static |
A helper function which rotates the deadlock cycle, so that the specified trx is the first one on the cycle.
| [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 |
|
static |
Rotates the deadlock cycle so that it starts from desired item.
| [in] | first_pos | the position which should become first after rotation |
| [in] | cycle_ids | the array to rotate |
first_pos is now the first
|
static |
Takes a snapshot of the content of slots which are in use.
| [out] | infos | Will contain the information about slots which are in use |
| 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
|
static |
Print the contents of the lock_sys_t::waiting_threads array.
|
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.
| slot | in: slot to release |
|
static |
Reserves a slot in the thread table for the current user OS thread.
| thr | in: query thread associated with the user OS thread |
| wait_timeout | in: lock wait timeout value |
| 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.
|
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.
| [in] | cycle_ids | indexes in infos array, of transactions forming the deadlock cycle |
| [in] | infos | information about all waiting transactions |
|
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.
| [in] | cycle_ids | indexes in infos array, of transactions forming the deadlock cycle |
| [in] | infos | information about all waiting transactions |
|
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.
| [in] | cycle_ids | indexes in infos array, of transactions forming the deadlock cycle |
| [in] | infos | information about all waiting transactions |
|
static |
|
static |
Takes a snapshot of transactions in waiting currently in slots, updates their schedule weights, searches for deadlocks among them and resolves them.
|
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
| [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) |
| 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.
|
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).
1.9.2