Patch that changes approach to how we acquire metadata

locks for DML statements and changes the way MDL locks
are acquired/granted in contended case.

Instead of backing-off when a lock conflict is encountered
and waiting for it to go away before restarting open_tables()
process we now wait for lock to be released without releasing
any previously acquired locks. If conflicting lock goes away
we resume opening tables. If waiting leads to a deadlock we
try to resolve it by backing-off and restarting open_tables()
immediately.

As result both waiting for possibility to acquire and
acquiring of a metadata lock now always happen within the
same MDL API call. This has allowed to make release of a lock
and granting it to the most appropriate pending request an
atomic operation.
Thanks to this it became possible to wake up during release
of lock only those waiters which requests can be satisfied
at the moment as well as wake up only one waiter in case
when granting its request would prevent all other requests
from being satisfied. This solves thundering herd problem
which occured in cases when we were releasing some lock and
woke up many waiters for SNRW or X locks (this was the issue
in bug#52289 "performance regression for MyISAM in sysbench
OLTP_RW test".
This also allowed to implement more fair (FIFO) scheduling
among waiters with the same priority.
It also opens the door for introducing new types of requests
for metadata locks such as low-prio SNRW lock which is
necessary in order to support LOCK TABLES LOW_PRIORITY WRITE.

Notice that after this sometimes can report ER_LOCK_DEADLOCK
error in cases in which it has not happened before.
Particularly we will always report this error if waiting for
conflicting lock has happened in the middle of transaction
and resulted in a deadlock. Before this patch the error was
not reported if deadlock could have been resolved by backing
off all metadata locks acquired by the current statement.

mysql-test/r/mdl_sync.result:
  Added test coverage for some aspects of deadlock handling in
  metadata locking subsystem.
  Adjusted test case after removing back-off in general case
  when conflicting metadata lock is encountered during
  open_tables() (now this happens only if waiting for
  conflicting lock to go away leads to a deadlock).
mysql-test/r/sp_sync.result:
  Adjusted test case after removing back-off in general case
  when conflicting metadata lock is encountered during
  open_tables() (now this happens only if waiting for
  conflicting lock to go away leads to a deadlock).
mysql-test/suite/perfschema/r/dml_setup_instruments.result:
  Adjusted test results after renaming MDL_context::
  m_waiting_for_lock rwlock to m_LOCK_waiting_for.
mysql-test/suite/rpl/r/rpl_sp.result:
  Adjusted test case after implementing new approach to
  acquiring metadata locks in open_tables(). We no longer
  release all MDL locks acquired by statement before waiting
  for conflicting lock to go away. As result DROP FUNCTION
  statement has to wait for DML statement which managed to
  acquire metadata lock on function being dropped and now
  waits for other conflicting metadata lock to go away.
mysql-test/suite/rpl/t/rpl_sp.test:
  Adjusted test case after implementing new approach to
  acquiring metadata locks in open_tables(). We no longer
  release all MDL locks acquired by statement before waiting
  for conflicting lock to go away. As result DROP FUNCTION
  statement has to wait for DML statement which managed to
  acquire metadata lock on function being dropped and now
  waits for other conflicting metadata lock to go away.
mysql-test/t/mdl_sync.test:
  Added test coverage for some aspects of deadlock handling in
  metadata locking subsystem.
  Adjusted test case after removing back-off in general case
  when conflicting metadata lock is encountered during
  open_tables() (now this happens only if waiting for
  conflicting lock to go away leads to a deadlock).
mysql-test/t/sp_sync.test:
  Adjusted test case after removing back-off in general case
  when conflicting metadata lock is encountered during
  open_tables() (now this happens only if waiting for
  conflicting lock to go away leads to a deadlock).
sql/mdl.cc:
  Changed MDL subsystem to support new approach to acquring
  metadata locks in open tables and more fair and efficient
  scheduling of metadata locks. To implement this:
  - Made releasing of the lock and granting it to the most
    appropriate pending request atomic operation. As result it
    became possible to wake up only those waiters requests from
    which can be satisfied at the moment as well as wake-up
    only one waiter in case when granting its request would
    prevent all other requests from being satisfied.
    This solved thundering herd problem which occured in cases
    when we were releasing some lock and woke up many waiters
    for SNRW or X locks (this was the issue in Bug #52289
    "performance regression for MyISAM in sysbench OLTP_RW
    test".
    To emphasize above changes wake_up_waiters() was renamed
    to MDL_context::reschedule_waiters().
  - Changed code to add tickets for new requests to the back of
    waiters queue and to select tickets to be satisfied from
    the head of the queue if possible (this makes scheduling of
    requests with the same priority fair). To be able to do
    this efficiently we now use for waiting and granted queues
    version of I_P_List class which provides fast push_back()
    method.
  - Members and methods of MDL_context related to sending
    and waiting for signal were moved to separate MDL_wait
    class.
  - Since in order to avoid race conditions we must grant the
    lock only to the context which was not chosen as a victim
    of deadlock, killed or aborted due to timeout
    MDL_wait::set_status() (former awake()) was changed not to
    send signal if signal slot is already occupied and to
    indicate this fact through its return value. As another
    consequence MDL_wait::timed_wait() method was changed to
    handle timeout (optionally) and abort due to kill as
    signals which make signal slot occupied.
  - Renamed MDL_context::acquire_lock_impl() to acquire_lock().
    Changed it to be able correctly process requests for shared
    locks when there are open HANDLERs, made this method more
    optimized for acquisition of shared locks. As part of this
    change moved code common between try_acquire_lock() and
    acquire_lock() to new try_acquire_lock_impl() method.
    Also adjusted acquire_lock()'s code to take into account
    the fact that in cases when lock is granted as result of
    MDL_context::reschedule_waiters() call (i.e. when it is
    granted after waiting for lock conflict to go away)
    updating MDL_lock state is responsibility of the thread
    calling reschedule_waiters().
  - Changed MDL_context::find_deadlock() to send VICTIM
    signal even if victim is the context which has initiated
    deadlock detection. This is required in order to avoid
    races in cases when the same context simultaneously is
    chosen as a victim and its request for lock is satisfied.
    As result return value of this method became unnecessary
    and it was changed to return void.
    Adjusted MDL_lock::find_deadlock() method to take into
    account that now there can be a discrepancy between
    MDL_context::m_waiting_for value being set and real state
    of the ticket this member points to.
  - Renamed MDL_context::m_waiting_for_lock to m_LOCK_waiting_for
    and MDL_context::stop_waiting() to done_waiting_for().
  - Finally, removed MDL_context::wait_for_lock() method.
sql/mdl.h:
  Changed MDL subsystem to support new approach to acquring
  metadata locks in open tables and more fair and efficient
  scheduling of metadata locks. To implement this:
  - Members and methods of MDL_context related to sending
    and waiting for signal were moved to separate MDL_wait
    class.
  - Since now in order to avoid race conditions we must grant
    the lock only to the context which was not chosen as a
    victim of deadlock, killed or aborted due to timeout
    MDL_wait::set_status (former awake()) was changed not to
    send signal if signal slot is already occupied and to
    indicate this fact through its return value.
    Also NORMAL_WAKE_UP signal became GRANTED, and timeouts
    and aborts due to kill became full blown signals rather
    than simple return values.
  - MDL_wait::timed_wait() now takes extra parameter that
    indicates whether signal should be set if timeout is
    reached.
  - Enabled fast push_back() operation in MDL_context::m_tickets
    list to make move_ticket_after_trans_sentinel() method more
    efficient.
  - Removed MDL_context::wait_for_lock() method.
  - Renamed MDL_context::m_waiting_for_lock to m_LOCK_waiting_for
    and MDL_context::stop_waiting() to done_waiting_for().
  - MDL_context::acquire_lock_impl() became acquire_lock().
  - Introduced MDL_context::try_acquire_lock_impl() as a
    place for code shared by try_acquire_lock and
    acquire_lock().
  - Due to fact that now VICTIM signal is sent even if victim
    is the context which has initiated deadlock detection
    find_deadlock() no longer needs a return value.
sql/sql_base.cc:
  Implemented new approach to acquiring metadata locks in
  open_tables(). We no longer perform back-off when conflicting
  metadata lock is encountered. Instead we wait for this lock
  to go away while holding all locks which were acquired so
  far. Back-off is only used in situation when further waiting
  will cause a deadlock which could be avoided by performing
  back-off and restarting open_tables() process. Absence of
  waiting between back-off and restart of acquiring metadata
  locks can't lead to livelocks as MDL subsystem was changed
  to make release of lock and granting it to waiting lock
  an atomic action, so back-off will automatically give way
  to other participants of deadlock loop.
  Accordingly:
  - open_table_get_mdl_lock() and open_and_process_routine()
    were changed to wait for conflicting metadata lock to
    go away without back-off. Only if such wait leads to a
    deadlock back-off is requested. As part of this change
    new error handler class was introduced which converts,
    if possible, ER_LOCK_DEADLOCK error to a request for
    back-off and re-start of open_tables() process.
  - Open_table_context::recover_from_failed_open() was changed
    not to wait in case of metadata lock conflict. Instead we
    immediately proceed to re-acquiring locks.
  - Open_table_context::request_backoff_action() now always
    emits error if back-off is requested in the middle of
    transaction as we can't be sure that releasing lock
    which were acquired only by current statement will
    resolve a deadlock. Before this patch such situations were
    successfully detected thanks to the fact that we called
    MDL_context::wait_for_lock() method in
    recover_from_failed_open().
  - In order to avoid deadlocks open_tables() code was adjusted
    to flush open HANDLERs for which there are pending requests
    for X locks before restarting the process of acquiring
    metadata locks.
  - Changed close_tables_for_reopen() not to reset MDL_request
    for tables belonging to the tail of prelocking list. It is
    no longer necessary as these MDL_request objects won't be
    used for any waiting.
  - Adjusted comment in tdc_wait_for_old_version() to avoid
    mentioning removed MDL_context::wait_for_lock() method.
sql/sql_base.h:
  As we no longer wait for conflicting metadata lock away in
  Open_table_context::recover_from_failed_open() method,
  Open_table_context::OT_WAIT_MDL_LOCK action was renamed to
  OT_MDL_CONFLICT.
  Also Open_table_context::m_failed_mdl_request became
  unnecessary and was removed.
sql/sql_plist.h:
  Extended I_P_List template to support efficient push_back()
  operation if it is parameterized with an appropriate policy
  class.
sql/sql_show.cc:
  Adjusted code after removal of MDL_context::wait_for_lock()
  method. Now if one needs to acquire metadata lock with waiting
  one has to use a variant of MDL_context::acquire_lock() method.

1 files changed, 94 insertions, 1 deletions

diff --git a/mysql-test/r/mdl_sync.result b/mysql-test/r/mdl_sync.result
index f8b8d3f9d56..67d778211dd 100644
--- a/mysql-test/r/mdl_sync.result
+++ b/mysql-test/r/mdl_sync.result
@@ -1765,6 +1765,7 @@ drop tables t1, t2;
 # locking subsystem.
 #
 drop tables if exists t0, t1, t2, t3, t4, t5;
+set debug_sync= 'RESET';
 create table t1 (i int);
 create table t2 (j int);
 create table t3 (k int);
@@ -1943,6 +1944,98 @@ commit;
 # Reap ALTER TABLE ... RENAME.
 drop table t2;
 #
+# Test that in situation when MDL subsystem detects a deadlock
+# but it turns out that it can be resolved by backing-off locks
+# acquired by one of participating transactions (which is
+# possible when one of transactions consists only of currently
+# executed statement, e.g. in autocommit mode) no error is
+# reported.
+#
+create table t1 (i int);
+create table t2 (j int);
+# Ensure that the below SELECT stops once it has acquired metadata
+# lock on table 't2'.
+set debug_sync= 'after_open_table_mdl_shared SIGNAL locked WAIT_FOR finish';
+# Sending:
+select * from t2, t1;
+#
+# Switching to connection 'deadlock_con1'.
+# Wait till SELECT acquires MDL on 't2' and starts waiting for signal.
+set debug_sync= 'now WAIT_FOR locked';
+# Sending:
+lock tables t1 write, t2 write;
+#
+# Switching to connection 'deadlock_con2'.
+# Wait until LOCK TABLES acquires SNRW lock on 't1' and is blocked
+# while trying to acquire SNRW lock on 't1'.
+# Resume SELECT execution, this should eventually unblock LOCK TABLES.
+set debug_sync= 'now SIGNAL finish';
+#
+# Switching to connection 'deadlock_con1'.
+# Reaping LOCK TABLES.
+unlock tables;
+#
+# Switching to connection 'default'.
+# Reaping SELECT. It succeed and not report ER_LOCK_DEADLOCK error.
+j	i
+drop tables t1, t2;
+#
+# Test coverage for situation in which a race has happened
+# during deadlock detection process which led to unwarranted
+# ER_LOCK_DEADLOCK error.
+#
+create table t1 (i int);
+# Ensure that ALTER waits once it has acquired SNW lock.
+set debug_sync='after_open_table_mdl_shared SIGNAL parked1 WAIT_FOR go1';
+# Sending:
+alter table t1 add column j int;
+#
+# Switching to connection 'deadlock_con1'.
+# Wait till ALTER acquires SNW lock and stops.
+set debug_sync='now WAIT_FOR parked1';
+# Ensure that INSERT is paused once it detects that there is
+# a conflicting metadata lock so it has to wait, but before
+# deadlock detection is run.
+set debug_sync='mdl_acquire_lock_wait SIGNAL parked2 WAIT_FOR go2';
+# Sending:
+insert into t1 values ();
+#
+# Switching to connection 'deadlock_con2'.
+# Wait till INSERT is paused.
+set debug_sync='now WAIT_FOR parked2';
+# Resume ALTER execution. Eventually it will release its
+# metadata lock and INSERT's request for SW lock will be
+# satisified.
+set debug_sync='now SIGNAL go1';
+#
+# Switching to connection 'default'.
+# Reaping ALTER TABLE.
+# Add a new request for SNW lock to waiting graph.
+# Sending:
+alter table t1 drop column j;
+#
+# Switching to connection 'deadlock_con2'.
+# Wait until ALTER is blocked.
+# Resume INSERT so it can start deadlock detection.
+#
+# At this point there is a discrepancy between the fact that INSERT's
+# SW lock is already satisfied, but INSERT's connection is still
+# marked as waiting for it. Looking for a loop in waiters graph
+# without additional checks has detected a deadlock (INSERT waits
+# for SW lock; which is not granted because of pending SNW lock from
+# ALTER; which waits for active SW lock from INSERT). Since requests
+# for SW and SNW locks have same weight ALTER was selected as a victim
+# and ended with ER_LOCK_DEADLOCK error.
+set debug_sync='now SIGNAL go2';
+#
+# Switching to connection 'deadlock_con1'.
+# Reaping INSERT.
+#
+# Switching to connection 'default'.
+# Reaping ALTER. It should succeed and not produce ER_LOCK_DEADLOCK.
+drop table t1;
+set debug_sync= 'RESET';
+#
 # Test for bug #46748 "Assertion in MDL_context::wait_for_locks()
 # on INSERT + CREATE TRIGGER".
 #
@@ -2175,7 +2268,7 @@ alter table t1 add column e int, rename to t2;;
 #
 # Switching to connection 'default'.
 set debug_sync='now WAIT_FOR alter_table_locked';
-set debug_sync='before_open_table_wait_refresh SIGNAL alter_go';
+set debug_sync='mdl_acquire_lock_wait SIGNAL alter_go';
 # The below statement should get ER_LOCK_DEADLOCK error
 # (i.e. it should not allow ALTER to proceed, and then
 # fail due to 't1' changing its name to 't2').