/* Copyright (c) 2014, 2024, Oracle and/or its affiliates.

This program is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation; version 2 of the License.

This program is designed to work with certain software (including

but not limited to OpenSSL) that is licensed under separate terms,

as designated in a particular file or component or in included license

documentation. The authors of MySQL hereby grant you an additional

permission to link the program and your derivative works with the

separately licensed software that they have either included with

the program or referenced in the documentation.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program; if not, write to the Free Software

Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */

#include <stddef.h>

#include <string.h>

#include <my_stacktrace.h>

#include "my_alloc.h"

#include "my_psi_config.h"

#include "my_thread.h"

#include "mysql/psi/psi_cond.h"

#include "mysql/psi/psi_file.h"

#include "mysql/psi/psi_idle.h"

#include "mysql/psi/psi_mutex.h"

#include "mysql/psi/psi_rwlock.h"

#include "mysql/psi/psi_statement.h"

#include "mysql/psi/psi_thread.h"

#include "mysqld.h"

#include "mysqld_error.h"

#include "sql/debug_lock_order.h"

#include "sql/debug_lo_misc.h"

#include "sql/debug_lo_parser.h"

#include "sql/debug_lo_scanner.h"

#include "mysql/components/services/log_builtins.h"

/* Old versions of bison forget to declare this in sql/debug_lo_parser.h */

int LOCK_ORDER_parse(struct LO_parser_param *param);

#ifdef HAVE_EXECINFO_H

#include <execinfo.h>

#endif

#ifdef _WIN32

#include <crtdbg.h>

#include <process.h>

#endif

#include <algorithm>

#include <list>

#include <map>

#include <set>

#include <stack>

#include <vector>

/* Sanity check for the makefile. */

#ifndef WITH_LOCK_ORDER

#error "WITH_LOCK_ORDER is not defined, this code should not be built."

#endif /* WITH_LOCK_ORDER */

/* Additional traces, to debug lock order itself. */

static bool g_internal_debug = false;

/* Helper to exclude rwlock, to debug lock order itself. */

static bool g_with_rwlock = true;

/*

** ========================================================================

** SECTION 1: DOXYGEN DOCUMENTATION

** ========================================================================

*/

/* clang-format off */

/**

@page PAGE_LOCK_ORDER Lock Order

MySQL LOCK ORDER

@section LO_MAIN_INTRO Introduction

LOCK ORDER is a debugging tool used to enforce

that no deadlocks can happen in the server.

The general idea is as follows.

Every mutex is instrumented by the performance schema,

and is assigned a name already.

There is a global, unique, oriented graph,

that describes the lock sequences allowed during runtime.

Instrumented mutexes are nodes in the graph.

When some code locks mutex A then B, there is an explicit

A -> B edge in the graph.

During runtime execution, the LOCK ORDER tool checks

whether the actual locks taken comply with the graph.

Should any test not comply,

- either the arc is considered valid, so the graph is incomplete,

and it should be amended (provided there are no cycles),

to describe more accurately actual dependencies,

- or the lock sequence is deemed illegal,

in which case the code should be changed to avoid it.

Once a state is achieved where:

- the graph has no cycle,

- the entire test suite executes within the graph constraints,

then the server is guaranteed to have no dead locks.

The beauty of this approach is that there is no need to

run tests concurrently to expose deadlocks.

When statements are executed, even alone in a single session,

any statement that causes an execution path to be not compliant

will be detected, and reported.

@section LO_BUILDING Building the code

LOCK ORDER is a debugging tool only.

It should not be used in production.

@c CMAKE contains a new build option @c WITH_LOCK_ORDER,

to build with the tool.

@section LO_RUNNING Running MySQL test with LOCK ORDER

To run a test without LOCK ORDER,

use any of the following:

@verbatim

./mtr --lock-order=0 main.parser

@endverbatim

@verbatim

export MTR_LOCK_ORDER=0

./mtr main.parser

@endverbatim

To run a test with LOCK_ORDER,

use any of the following:

@verbatim

./mtr --lock-order=1 main.parser

@endverbatim

@verbatim

export MTR_LOCK_ORDER=1

./mtr main.parser

@endverbatim

By default, LOCK ORDER is disabled in mysql-test-run.

Executing a test with LOCK_ORDER enabled will have the following effects:

- the file @c lock_order_dependencies.txt is read

by the tool, to load the graph to enforce.

- the file @c lock_order-(timestamp)-(pid).log is written

by the tool, and contains various messages.

- optionally, the file @c lock_order.txt is written,

and contains a textual representation of the graph,

with some analysis.

@section LO_FILE_FORMATS Lock order file formats

@subsection LO_DEPENDENCIES lock_order_dependencies file

The default dependencies file is

@c (root)/mysql-test/lock_order_dependencies.txt.

To use a different dependencies file,

use the @c lock_order_dependencies system variable.

The file format is text, with one line per declaration.

@subsubsection LO_DEP_MUTEX Mutex nodes

Every node is named from the performance schema instrumentation,

with a shorter prefix.

For example, the mutex @c mysql_mutex_t @c LOCK_open is named

"wait/synch/mutex/sql/LOCK_open" in the performance schema,

simplified as "mutex/sql/LOCK_open" in LOCK ORDER.

When the code locks A then B,

this arc is declared in the graph as:

@verbatim

ARC FROM "A" TO "B"

@endverbatim

For example:

@verbatim

ARC FROM "mutex/sql/LOCK_open" TO "mutex/sql/TABLE_SHARE::LOCK_ha_data"

@endverbatim

Note that arcs are not transitive in the graph.

For example, if the graph has the following arcs:

@verbatim

ARC FROM "A" TO "B"

ARC FROM "B" TO "C"

@endverbatim

Then the following code will comply:

@code

mysql_mutex_lock(A);

mysql_mutex_lock(B);

mysql_mutex_unlock(A);

mysql_mutex_lock(C);

mysql_mutex_unlock(B);

mysql_mutex_unlock(C);

@endcode

But the following code will not comply:

@code

mysql_mutex_lock(A);

mysql_mutex_lock(B);

mysql_mutex_lock(C); // <- this will raise an error.

mysql_mutex_unlock(A);

mysql_mutex_unlock(B);

mysql_mutex_unlock(C);

@endcode

This happens because the "A" -> "C" transition is not declared.

This is a desired feature: to understand contention in the server,

the real dependencies (the paths actually taken) must be documented explicitly.

The tool could, but does not, infer more arcs by transitivity.

Additional metadata can be associated with an ARC,

by adding flags to the arc declaration.

The format is

@verbatim

ARC FROM "A" TO "B" FLAGS <flag1> <flag2> ... <flagN>

@endverbatim

Individual flags are separated by spaces.

Supported arc flags are:

- TRACE

- DEBUG

- LOOP

- IGNORED

@subsubsection LO_DEP_RWLOCK Rwlock nodes

Read write locks are named from the performance schema,

with a shorter prefix.

There are three kinds of read write locks instrumented:

- read write locks (@c mysql_rwlock_t)

- priority read write lock (@c mysql_prlock_t)

- shared exclusive locks (@c rw_lock_t in innodb)

The lock @c mysql_rwlock_t @c LOCK_system_variables_hash, which is a read write lock,

is named "wait/synch/rwlock/sql/LOCK_system_variables_hash" in the performance schema,

simplified as "rwlock/sql/LOCK_system_variables_hash" in LOCK ORDER.

Read write locks are recursive, but only on read operations.

Due to the scheduling behavior in the underlying implementation,

a reader might block indirectly another reader, if a write request is present.

When a lock is held on a read write lock, it can be in two states:

- either READ,

- or WRITE.

These states are exclusive.

When a thread holds a read write lock on "L" and locks "B",

arcs are noted as follows:

@verbatim

ARC FROM "rwlock/sql/L" STATE "R" TO "B" ...

ARC FROM "rwlock/sql/L" STATE "W" TO "B" ...

@endverbatim

Operations on read write locks are:

- READ

- TRY READ

- WRITE

- TRY WRITE

When a thread holds a lock on "A" and then locks a read write lock "L",

arcs are noted as follows:

@verbatim

ARC FROM "A" ... TO "rwlock/sql/L" OP "R"

ARC FROM "A" ... TO "rwlock/sql/L" OP "TRY R"

ARC FROM "A" ... TO "rwlock/sql/L" OP "W"

ARC FROM "A" ... TO "rwlock/sql/L" OP "TRY W"

@endverbatim

Recursive locks are noted as follows:

@verbatim

ARC FROM "rwlock/sql/L" STATE "..." TO "rwlock/sql/L" RECURSIVE OP "R"

ARC FROM "rwlock/sql/L" STATE "..." TO "rwlock/sql/L" RECURSIVE OP "TRY R"

@endverbatim

The lock @c mysql_prlock_t @c MDL_context::m_LOCK_waiting_for, which is a priority read write lock,

is named "wait/synch/prlock/sql/MDL_context::LOCK_waiting_for" in the performance schema,

simplified as "prlock/sql/MDL_context::LOCK_waiting_for" in LOCK ORDER.

Priority locks are recursive.

A reader will never block another reader, even if a write request is present.

When a lock is held on a priority lock, it can be in two states:

- either READ,

- or WRITE.

These states are exclusive.

When a thread holds a priority lock on "L" and locks "B",

arcs are noted as follows:

@verbatim

ARC FROM "prlock/sql/L" STATE "R" TO "B" ...

ARC FROM "prlock/sql/L" STATE "W" TO "B" ...

@endverbatim

Operations on priority locks are:

- READ

- WRITE

Note that the READ state can be acquired recursively on the same priority lock.

When a thread holds a lock on "A" and then locks a priority lock "L",

arcs are noted as follows:

@verbatim

ARC FROM "A" ... TO "prlock/sql/L" OP "R"

ARC FROM "A" ... TO "prlock/sql/L" OP "W"

@endverbatim

Recursive locks are noted as follows:

@verbatim

ARC FROM "prlock/sql/L" STATE "..." TO "prlock/sql/L" RECURSIVE OP "R"

@endverbatim

The lock @c rw_lock_t @c dict_operation_lock, which is a shared exclusive lock,

is named "wait/synch/sxlock/innodb/dict_operation_lock" in the performance schema,

simplified as "sxlock/innodb/dict_operation_lock" in LOCK ORDER.

Shared exclusive locks are recursive.

Shared exclusive locks are implemented as spin locks, with fallback on condition variables.

When a lock is held on a shared exclusive lock, it can be in three states:

- SHARED,

- or SHARED EXCLUSIVE,

- or EXCLUSIVE.

Because the same lock can be acquired recursively,

when multiple locks are taken by the same thread on the same object,

the overall equivalent state is computed (for example, SX + X counts as X).

When a thread holds a shared exclusive lock on "L" and locks "B",

arcs are noted as follows:

@verbatim

ARC FROM "sxlock/innodb/L" STATE "S" TO "B" ...

ARC FROM "sxlock/innodb/L" STATE "SX" TO "B" ...

ARC FROM "sxlock/innodb/L" STATE "X" TO "B" ...

@endverbatim

Operations on shared exclusive locks are:

- SHARED

- TRY SHARED

- SHARED EXCLUSIVE

- TRY SHARED EXCLUSIVE

- EXCLUSIVE

- TRY EXCLUSIVE

Note that some states can be acquired recursively on the same shared exclusive lock.

When a thread holds a lock on "A" and then locks a shared exclusive lock "L",

arcs are noted as follows:

@verbatim

ARC FROM "A" ... TO "sxlock/innodb/L" OP "S"

ARC FROM "A" ... TO "sxlock/innodb/L" OP "TRY S"

ARC FROM "A" ... TO "sxlock/innodb/L" OP "SX"

ARC FROM "A" ... TO "sxlock/innodb/L" OP "TRY SX"

ARC FROM "A" ... TO "sxlock/innodb/L" OP "X"

ARC FROM "A" ... TO "sxlock/innodb/L" OP "TRY X"

@endverbatim

Recursive locks are noted as follows:

@verbatim

ARC FROM "sxlock/innodb/L" STATE "..." TO "sxlock/innodb/L" RECURSIVE OP "S"

ARC FROM "sxlock/innodb/L" STATE "..." TO "sxlock/innodb/L" RECURSIVE OP "SX"

ARC FROM "sxlock/innodb/L" STATE "..." TO "sxlock/innodb/L" RECURSIVE OP "X"

@endverbatim

@subsubsection LO_DEP_COND Cond nodes

Conditions are named from the performance schema,

with a shorter prefix.

For example, the condition @c mysql_cond_t @c COND_open is named

"wait/synch/cond/sql/COND_open" in the performance schema,

simplified as "cond/sql/COND_open" in LOCK ORDER.

Explicit arcs are declared between mutexes and associated conditions,

so that the tool also enforces that the same mutex is consistently

used for the same condition, to comply with the posix APIs.

When a condition C is associated with a mutex M,

this arc is declared in the graph as:

@verbatim

BIND "C" TO "M"

@endverbatim

For example:

@verbatim

BIND "cond/sql/COND_open" TO "mutex/sql/LOCK_open"

@endverbatim

In the following sequence of code:

@verbatim

mysql_mutex_lock(M);

mysql_cond_signal(C);

mysql_mutex_unlock(M);

@endverbatim

The tool will verify, when calling mysql_cond_signal, that condition C is bound with M, and that M is locked.

Note that holding a mutex when using signal or broadcast is recommended, but not mandatory.

To allow the following code:

@verbatim

mysql_cond_signal(C); // mutex M not locked

@endverbatim

The condition must be flagged explicitly as using 'UNFAIR' scheduling,

as in:

@verbatim

BIND "C" TO "M" FLAGS UNFAIR

@endverbatim

For example:

@verbatim

BIND "cond/sql/Source_info::start_cond" TO "mutex/sql/Source_info::run_lock" FLAGS UNFAIR

@endverbatim

@subsubsection LO_DEP_FILE File nodes

Files are named from the performance schema,

with a shorter prefix.

For example, the relay log file is named

"wait/io/file/sql/relaylog" in the performance schema,

simplified as "file/sql/relaylog" in LOCK ORDER.

File io operations (read, write, etc) on the file are not documented.

When any file io is performed while holding a lock,

the dependency is documented, for example:

@verbatim

ARC FROM "rwlock/sql/channel_lock" STATE "W" TO "file/sql/relaylog"

ARC FROM "sxlock/innodb/dict_operation_lock" STATE "X" TO "file/innodb/innodb_data_file"

@endverbatim

@subsection LO_LOG lock_order.log file

During execution, the server writes to a log file

located under the build directory,

in a sub directory named lock-order,

and named

@c lock_order-(timestamp)-(pid).log

where (pid) is the process id for mysqld.

The log file contains various messages printed

by LOCK ORDER.

@subsection LO_GRAPH_TEXT lock_order.txt file

This file is an optional output.

To print the lock_order.txt file,

two actions are required:

- enable the lock_order_print_txt system variable,

- send a COM_DEBUG command to the server, using mysqladmin.

The COM_DEBUG causes the file to be printed.

It is desirable to load dynamic plugins and components before dumping

this report, so that lock names instrumented inside the loaded code

are checked against the dependencies graph.

A helper test, lock_order.cycle, performs all the steps

required to dump the lock_order.txt report.

This command:

@verbatim

export MTR_LOCK_ORDER=1

./mtr lock_order.cycle

@endverbatim

will generate the graph dump as a side effect.

The generated file contains the following sections:

- DEPENDENCY GRAPH

- SCC ANALYSIS (full graph)

- IGNORED NODES

- LOOP ARC

- SCC ANALYSIS (revised graph)

- UNRESOLVED ARCS

The section "DEPENDENCY GRAPH" is a textual representation of the graph,

to facilitate investigations.

Each node is dumped with incoming and outgoing arcs, for example:

@verbatim

NODE: mutex/sql/LOCK_open

16 incoming arcs:

FROM: mutex/sql/tz_LOCK

FROM: mutex/p_dyn_loader/key_component_id_by_urn_mutex

FROM: mutex/sql/LOCK_plugin_install

FROM: mutex/sql/LOCK_table_cache

FROM: mutex/sql/key_mta_temp_table_LOCK

FROM: mutex/sql/LOCK_event_queue

FROM: mutex/sql/LOCK_global_system_variables

FROM: mutex/sql/LOCK_reset_gtid_table

FROM: mutex/sql/Source_info::data_lock

FROM: mutex/sql/Source_info::run_lock

FROM: mutex/sql/MYSQL_BIN_LOG::LOCK_index

FROM: mutex/sql/MYSQL_BIN_LOG::LOCK_log

FROM: mutex/sql/MYSQL_RELAY_LOG::LOCK_log

FROM: mutex/sql/Relay_log_info::data_lock

FROM: mutex/sql/Relay_log_info::run_lock

FROM: mutex/sql/TABLE_SHARE::LOCK_ha_data -- LOOP FLAG

22 outgoing arcs:

TO: mutex/blackhole/blackhole

TO: mutex/archive/Archive_share::mutex

TO: mutex/myisam/MYISAM_SHARE::intern_lock

TO: mutex/innodb/sync_array_mutex

TO: mutex/innodb/rtr_active_mutex

TO: mutex/innodb/srv_sys_mutex

TO: mutex/innodb/rw_lock_list_mutex

TO: mutex/innodb/rw_lock_debug_mutex

TO: mutex/innodb/dict_table_mutex

TO: mutex/innodb/dict_sys_mutex

TO: mutex/innodb/innobase_share_mutex

TO: mutex/csv/tina

TO: mutex/sql/LOCK_plugin

TO: cond/sql/COND_open

TO: mutex/mysys/KEY_CACHE::cache_lock

TO: mutex/mysys/THR_LOCK_heap

TO: mutex/mysys/THR_LOCK_myisam

TO: mutex/mysys/THR_LOCK_open

TO: mutex/sql/DEBUG_SYNC::mutex

TO: mutex/sql/MDL_wait::LOCK_wait_status

TO: mutex/sql/TABLE_SHARE::LOCK_ha_data

TO: mutex/sql/THD::LOCK_current_cond -- LOOP FLAG

@endverbatim

The section "SCC ANALYSIS (full graph)" is a "Strongly Connected Component"

(SCC) analysis of the entire graph.

See https://en.wikipedia.org/wiki/Strongly_connected_component

For each SCC, the report prints the nodes part of the SCCs:

@verbatim

Found SCC number 1 of size 26:

mutex/innodb/dict_sys_mutex

...

mutex/sql/LOCK_offline_mode

Found SCC number 2 of size 2:

mutex/sql/Relay_log_info::run_lock

mutex/sql/Source_info::run_lock

Number of SCC found: 2

@endverbatim

Then the arcs internal to each SCC are printed.

@verbatim

Dumping arcs for SCC 1:

SCC ARC FROM "mutex/myisam/MYISAM_SHARE::intern_lock" TO "mutex/sql/LOCK_plugin"

SCC ARC FROM "mutex/innodb/parser_mutex" TO "mutex/innodb/dict_sys_mutex"

SCC ARC FROM "mutex/innodb/dict_sys_mutex" TO "mutex/sql/LOCK_plugin"

SCC ARC FROM "mutex/sql/LOCK_plugin" TO "mutex/sql/LOCK_global_system_variables"

SCC ARC FROM "mutex/sql/LOCK_plugin" TO "mutex/sql/THD::LOCK_current_cond"

SCC ARC FROM "mutex/sql/LOCK_table_cache" TO "mutex/myisam/MYISAM_SHARE::intern_lock"

SCC ARC FROM "mutex/sql/LOCK_table_cache" TO "mutex/innodb/dict_sys_mutex"

SCC ARC FROM "mutex/sql/LOCK_table_cache" TO "mutex/sql/LOCK_plugin"

...

SCC ARC FROM "mutex/sql/MYSQL_BIN_LOG::LOCK_commit" TO "mutex/sql/LOCK_plugin"

SCC ARC FROM "mutex/sql/MYSQL_BIN_LOG::LOCK_commit" TO "mutex/sql/THD::LOCK_current_cond"

Dumping arcs for SCC 2:

SCC ARC FROM "mutex/sql/Relay_log_info::run_lock" TO "mutex/sql/Source_info::run_lock"

SCC ARC FROM "mutex/sql/Source_info::run_lock" TO "mutex/sql/Relay_log_info::run_lock"

@endverbatim

The section "IGNORED NODES" prints the nodes flagged as IGNORED

in the dependencies file:

@verbatim

IGNORED NODE: mutex/sql/LOCK_thd_list

IGNORED NODE: mutex/sql/LOCK_event_queue

IGNORED NODE: mutex/sql/LOCK_offline_mode

IGNORED NODE: mutex/sql/LOCK_global_system_variables

@endverbatim

The section "LOOP ARC" prints the arcs flagged as LOOP

in the dependencies file:

@verbatim

LOOP ARC FROM mutex/myisam/MYISAM_SHARE::intern_lock TO mutex/sql/LOCK_plugin

LOOP ARC FROM mutex/innodb/dict_sys_mutex TO mutex/sql/LOCK_plugin

LOOP ARC FROM mutex/mysys/THR_LOCK_myisam TO mutex/sql/LOCK_plugin

LOOP ARC FROM mutex/sql/LOCK_plugin TO mutex/sql/LOCK_global_system_variables

LOOP ARC FROM mutex/sql/LOCK_plugin TO mutex/sql/THD::LOCK_current_cond

LOOP ARC FROM mutex/sql/TABLE_SHARE::LOCK_ha_data TO mutex/sql/LOCK_table_cache

LOOP ARC FROM mutex/sql/LOCK_open TO mutex/sql/THD::LOCK_current_cond

LOOP ARC FROM mutex/sql/TABLE_SHARE::LOCK_ha_data TO mutex/sql/LOCK_open

LOOP ARC FROM mutex/sql/LOCK_global_system_variables TO mutex/sql/LOCK_thd_list

LOOP ARC FROM mutex/sql/TABLE_SHARE::LOCK_ha_data TO mutex/sql/THD::LOCK_thd_data

@endverbatim

The section "SCC ANALYSIS (revised graph)" prints the strongly connected

components of a sub graph, obtained by:

- ignoring nodes tagged IGNORED,

- ignoring arcs tagged LOOP.

@verbatim

Found SCC number 1 of size 14:

mutex/sql/THD::LOCK_current_cond

mutex/sql/MYSQL_RELAY_LOG::LOCK_log_end_pos

mutex/sql/Relay_log_info::log_space_lock

mutex/sql/MYSQL_RELAY_LOG::LOCK_index

mutex/sql/THD::LOCK_thd_data

mutex/sql/MYSQL_BIN_LOG::LOCK_log

mutex/sql/LOCK_reset_gtid_table

mutex/sql/MYSQL_BIN_LOG::LOCK_sync

mutex/sql/MYSQL_BIN_LOG::LOCK_commit

mutex/sql/MYSQL_BIN_LOG::LOCK_index

mutex/sql/MYSQL_RELAY_LOG::LOCK_log

mutex/sql/Relay_log_info::data_lock

mutex/sql/key_mta_temp_table_LOCK

mutex/sql/Source_info::data_lock

Found SCC number 2 of size 2:

mutex/sql/Relay_log_info::run_lock

mutex/sql/Source_info::run_lock

Number of SCC found: 2

Dumping arcs for SCC 1:

...

Dumping arcs for SCC 2:

...

@endverbatim

Finally, the section "UNRESOLVED ARCS" lists arcs found in the dependency graph

that could not be matched with actual nodes from the code.

@verbatim

UNRESOLVED ARC FROM "mutex/sql/MYSQL_BIN_LOG::LOCK_log" TO "mutex/semisync/LOCK_binlog_"

UNRESOLVED ARC FROM "mutex/sql/MYSQL_BIN_LOG::LOCK_commit" TO "mutex/semisync/LOCK_binlog_"

UNRESOLVED ARC FROM "mutex/sql/LOCK_plugin" TO "mutex/semisync/LOCK_binlog_"

UNRESOLVED ARC FROM "mutex/sql/LOCK_plugin_install" TO "mutex/semisync/LOCK_binlog_"

UNRESOLVED ARC FROM "mutex/sql/LOCK_plugin_install" TO "mutex/semisync/Ack_receiver::m_mutex"

UNRESOLVED ARC FROM "mutex/semisync/LOCK_binlog_" TO "cond/semisync/COND_binlog_send_"

UNRESOLVED ARC FROM "mutex/semisync/Ack_receiver::m_mutex" TO "cond/semisync/Ack_receiver::m_cond"

@endverbatim

Arcs can be unresolved for two reasons:

- The code changed, and a node was either removed or renamed.

The fix is to correct the dependency file accordingly.

- A node is defined in a plugin (in this example, semisync), but the plugin is not loaded

in the lock_order.cycle test script. The fix is to add the missing plugin.

@section LO_METHODOLOGY Methodology

First, the graph defining valid lock sequences should be

unique for the server.

Any attempt to use different graphs for different tests

is fundamentally flawed.

Secondly, documenting the dependencies graph helps to

document the design, as the order of locks does not happen by accident

in the code but as a result of design decisions by development.

In an ideal world, the dependency graph should be documented

up front when writing the code, and testing should only verify

that the code complies with the graph.

In practice, such a graph is -- not -- documented,

only fragments of it are "common knowledge".

As a result, the complete graph must be discovered from the code,

by performing reverse engineering, to be documented.

The LOCK_ORDER tool support both:

- discovery, to rebuild a graph from runtime execution

- enforcement, to ensure runtime execution complies with constraints

@subsection LO_PROCESS_COLLECT Collect missing arcs

Start with an empty lock_order_dependencies.txt file,

and run a test.

For example,

@verbatim

./mtr main.parser

@endverbatim

The resulting @c lock-order-(timestamp)-(pid).log file will contain numerous

messages, like:

@verbatim

MISSING: ARC FROM "mutex/sql/LOCK_table_cache" TO "mutex/sql/LOCK_open"

Trace: using missing arc mutex/sql/LOCK_table_cache (/home/malff/GIT_LOCK_ORDER/sql/table_cache.h:140)

-> mutex/sql/LOCK_open (/home/malff/GIT_LOCK_ORDER/sql/table_cache.h:319)

@endverbatim

Here, the tool detected a lock sequence (@c LOCK_table_cache then @c LOCK_open)

that is not declared in the graph.

The "MISSING:" line prints the arc definition that should be added

in the lock_order_dependencies.txt file, for easier copy and paste.

The "Trace:" message gives details about where each lock was taken in the source code.

An efficient way to add at once all the missing arcs found while running tests

is as follows:

@verbatim

cat lock_order*.log | grep MISSING | sort -u

@endverbatim

Run this script, remove the MISSING: prefix,

and add the result to the dependency graph.

Then run tests again, with the new graph,

and repeat until no more missing arcs are found.

@subsection LO_PROCESS_ANALYSIS Perform graph analysis

The tool processes the dependency graph to detect

"Strongly Connected Components".

See https://en.wikipedia.org/wiki/Strongly_connected_component

Strictly speaking, a Strongly Connected Component can be a single

node. In the context of LOCK_ORDER, "SCC" refers to Strongly Connected Components

of size greater or equal to 2, that is, an actual cluster of _several_ nodes.

This computation is done when dumping the lock_order.txt file.

A dedicated mtr test is written as a helper:

@verbatim

./mtr lock_order.cycle

@endverbatim

Then read the section named "SCC ANALYSIS (full graph)" in file lock_order.txt

At time of writing, it reads as:

@verbatim

SCC ANALYSIS (full graph):

==========================

Found SCC number 1 of size 26:

mutex/innodb/dict_sys_mutex

mutex/sql/LOCK_plugin

mutex/sql/LOCK_global_system_variables

mutex/innodb/parser_mutex

mutex/sql/LOCK_table_cache

mutex/myisam/MYISAM_SHARE::intern_lock

mutex/mysys/THR_LOCK_myisam

mutex/sql/LOCK_open

mutex/sql/TABLE_SHARE::LOCK_ha_data

mutex/sql/THD::LOCK_thd_data

mutex/sql/LOCK_event_queue

mutex/sql/MYSQL_BIN_LOG::LOCK_commit

mutex/sql/THD::LOCK_current_cond

mutex/sql/MYSQL_RELAY_LOG::LOCK_log_end_pos

mutex/sql/Relay_log_info::log_space_lock

mutex/sql/LOCK_thd_list

mutex/sql/MYSQL_RELAY_LOG::LOCK_index

mutex/sql/MYSQL_RELAY_LOG::LOCK_log

mutex/sql/Relay_log_info::data_lock

mutex/sql/key_mta_temp_table_LOCK

mutex/sql/Source_info::data_lock

mutex/sql/MYSQL_BIN_LOG::LOCK_log

mutex/sql/LOCK_reset_gtid_table

mutex/sql/MYSQL_BIN_LOG::LOCK_sync

mutex/sql/MYSQL_BIN_LOG::LOCK_index

mutex/sql/LOCK_offline_mode

Found SCC number 2 of size 2:

mutex/sql/Relay_log_info::run_lock

mutex/sql/Source_info::run_lock

Number of SCC found: 2

@endverbatim

The tool found two Strongly Connected Components (SCC).

The details about each arcs are printed:

@verbatim

Dumping arcs for SCC 1:

SCC ARC FROM "mutex/myisam/MYISAM_SHARE::intern_lock" TO "mutex/sql/LOCK_plugin"

SCC ARC FROM "mutex/innodb/parser_mutex" TO "mutex/innodb/dict_sys_mutex"

SCC ARC FROM "mutex/innodb/dict_sys_mutex" TO "mutex/sql/LOCK_plugin"

SCC ARC FROM "mutex/sql/LOCK_plugin" TO "mutex/sql/LOCK_global_system_variables"

SCC ARC FROM "mutex/sql/LOCK_plugin" TO "mutex/sql/THD::LOCK_current_cond"

SCC ARC FROM "mutex/sql/LOCK_table_cache" TO "mutex/myisam/MYISAM_SHARE::intern_lock"

SCC ARC FROM "mutex/sql/LOCK_table_cache" TO "mutex/innodb/dict_sys_mutex"

SCC ARC FROM "mutex/sql/LOCK_table_cache" TO "mutex/sql/LOCK_plugin"

...

SCC ARC FROM "mutex/sql/MYSQL_BIN_LOG::LOCK_commit" TO "mutex/sql/LOCK_plugin"

SCC ARC FROM "mutex/sql/MYSQL_BIN_LOG::LOCK_commit" TO "mutex/sql/THD::LOCK_current_cond"

Dumping arcs for SCC 2:

SCC ARC FROM "mutex/sql/Relay_log_info::run_lock" TO "mutex/sql/Source_info::run_lock"

SCC ARC FROM "mutex/sql/Source_info::run_lock" TO "mutex/sql/Relay_log_info::run_lock"

@endverbatim

Note that only arcs within the same SCC are printed here,

as they are the ones that need closer investigation.

Arcs coming in or out of this SCC are omitted, to reduce noise.

@subsection LO_PROCESS_BREAK Break Strongly Connected Components

By its very own definition, a SCC of size greater than one

is a cluster of nodes where any node is reachable, using locks,

from any other node.

Hence, SCC should not exist, and the code must be re-factored to avoid them.

In the list of SCC arcs printed, some (human) analysis is required

to decide:

- which arc is valid, and compliant with the MySQL server design

- which arc is invalid, which points to a flaw in the code.

A bug fix is required to change the server code affected,

to avoid locks, or take locks in the proper order.

Now, this is a sensitive task, for the following reasons:

- deciding which arc to remove is by itself difficult

- changing the server code and / or design to change lock order

can be even more difficult

- removing an arc alone might not even fix anything, if there is

another path in the graph that closes the same loop.

For this reason, the tool supports ways to simulate "what-if" scenarios,

and see in practice what the overall graph would look like if such and such

arc were to be removed.

First, some nodes can (temporarily) be ignored entirely,

to simplify the graph analysis, and identify smaller sub graphs in a big SCC.

By ignoring some nodes,

a big SCC can be broken down into smaller,

independent, sub graphs,

which helps to investigate, identify, and resolve

several dead lock root causes in isolation.

To ignore a node "A", use the following syntax in the dependency graph:

@verbatim

NODE "A" IGNORED

@endverbatim

For example, using

@verbatim

NODE "mutex/sql/LOCK_event_queue" IGNORED

NODE "mutex/sql/LOCK_global_system_variables" IGNORED

NODE "mutex/sql/LOCK_offline_mode" IGNORED

NODE "mutex/sql/LOCK_thd_list" IGNORED

@endverbatim

will produce a graph without these nodes,

also ignoring arcs from and to these nodes.

Secondly, arcs that are considered loops to fix in the code can be marked explicitly,

like this:

@verbatim

ARC FROM "mutex/sql/TABLE_SHARE::LOCK_ha_data" TO "mutex/sql/LOCK_open" FLAGS LOOP

ARC FROM "mutex/sql/TABLE_SHARE::LOCK_ha_data" TO "mutex/sql/LOCK_table_cache" FLAGS LOOP

ARC FROM "mutex/sql/TABLE_SHARE::LOCK_ha_data" TO "mutex/sql/THD::LOCK_thd_data" FLAGS LOOP

@endverbatim

After tagging some IGNORED nodes or LOOP arcs, generate the lock_order.txt

report again, to perform some analysis again.

The section "SCC ANALYSIS (full graph)" will be identical, as the real graph did not change.

The section "SCC ANALYSIS (revised graph)" will show what the graph would look like, with the loops fixed.

The goal is to iteratively tweak the LOOP flags in the graph,

and perform analysis on the revised graph, until:

- the list of LOOP arcs can be reasonably fixed in the code,

without causing too much re-engineering effort.

- the resulting revised graph has less complicated SCC (ideally, there should be none left),

showing progress towards the resolution of dead locks.

Once a viable set of LOOP arcs to remove is identified,

file a bug report to address the issue found.

@subsection LO_PROCESS_FIX Get reported bugs fixed

Each time a dependency is flagged as a LOOP,

a matching bug report should be filed,

and that bug should be eventually resolved.

Marking nodes are IGNORED or arcs as LOOP is equivalent

to using suppressions in valgrind to avoid error messages.

This can be convenient to investigate further other areas,

but it is by no means a satisfactory resolution in itself.

To achieve a state where the server can be declared as deadlock free

with reasonable confidence, all the following conditions are required:

- the GCOV code coverage is satisfactory,

and in particular covers all lines of code taking locks.

- all mutexes in the code are instrumented with the performance schema

- the dependency graph contains no SCC

- the dependency graph contains no LOOP arcs

- the dependency graph contains no IGNORED nodes

- the test suite passes under LOCK_ORDER without any complaints from the tool.

@section LO_TOOLS Advanced tooling

To facilitate investigations and debugging, the following features are available:

- Tracing

- Debugging

- Simulating loop arcs

- Simulating ignored nodes

@subsection LO_TOOL_TRACE Tracing dependencies

When an arc from A to B exists in the graph,

it might be sometime necessary to understand where

in the source code the A -> B dependency is actually taken.

By declaring the arc with the TRACE flag, as in

@verbatim

ARC FROM "mutex/sql/LOCK_open" TO "mutex/sql/TABLE_SHARE::LOCK_ha_data" FLAGS TRACE

@endverbatim

the tool will:

- capture the current statement text,

- capture the source code location, and the call stack,

when the first lock is taken,

- capture the source code location, and the call stack,

when the second lock is taken,

and print all the details in the log file when this arc is found

during runtime execution.

An example of trace:

@verbatim

Trace: using arc mutex/sql/LOCK_open (/home/malff/GIT_LOCK_ORDER/sql/sql_base.cc:1704) -> mutex/sql/TABLE_SHARE::LOCK_ha_data (/home/malff/GIT_LOCK_ORDER/sql/handler.cc:7764)

statement when first lock was acquired:

ALTER TABLE t1 ADD PARTITION

stack when the first lock was acquired:

[0] /home/malff/GIT_LOCK_ORDER/build/runtime_output_directory/mysqld(_ZN14LO_stack_traceC2Ev+0x28) [0x2e9f654]

[1] /home/malff/GIT_LOCK_ORDER/build/runtime_output_directory/mysqld(_ZN7LO_lock18record_stack_traceEv+0x24) [0x2e9fe52]

[2] /home/malff/GIT_LOCK_ORDER/build/runtime_output_directory/mysqld(_ZN9LO_thread14add_mutex_lockEP8LO_mutexPKci+0x18c) [0x2e9aeb4]

[3] /home/malff/GIT_LOCK_ORDER/build/runtime_output_directory/mysqld(_ZN15LO_mutex_locker3endEv+0x3e) [0x2ea02dc]

[4] /home/malff/GIT_LOCK_ORDER/build/runtime_output_directory/mysqld() [0x2e9d834]