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, 77 insertions, 23 deletions

diff --git a/sql/sql_plist.h b/sql/sql_plist.h
index eb239a63467..051fd216587 100644
--- a/sql/sql_plist.h
+++ b/sql/sql_plist.h
@@ -18,8 +18,10 @@
 
 #include <my_global.h>
 
-template <typename T, typename B, typename C> class I_P_List_iterator;
+template <typename T, typename B, typename C, typename I>
+class I_P_List_iterator;
 class I_P_List_null_counter;
+template <typename T> class I_P_List_no_push_back;
 
 
 /**
@@ -52,10 +54,17 @@ class I_P_List_null_counter;
              should be done. Instance of this class is also used as a place
              where information about number of list elements is stored.
              @sa I_P_List_null_counter, I_P_List_counter
+   @param I  Policy class specifying whether I_P_List should support
+             efficient push_back() operation. Instance of this class
+             is used as place where we store information to support
+             this operation.
+             @sa I_P_List_no_push_back, I_P_List_fast_push_back.
 */
 
-template <typename T, typename B, typename C = I_P_List_null_counter>
-class I_P_List : public C
+template <typename T, typename B,
+          typename C = I_P_List_null_counter,
+          typename I = I_P_List_no_push_back<T> >
+class I_P_List : public C, public I
 {
   T *first;
 
@@ -65,31 +74,27 @@ class I_P_List : public C
     is a bad idea.
   */
 public:
-  I_P_List() : first(NULL) { };
-  inline void empty()      { first= NULL; C::reset(); }
+  I_P_List() : I(&first), first(NULL) {};
+  inline void empty()      { first= NULL; C::reset(); I::set_last(&first); }
   inline bool is_empty() const { return (first == NULL); }
   inline void push_front(T* a)
   {
     *B::next_ptr(a)= first;
     if (first)
       *B::prev_ptr(first)= B::next_ptr(a);
+    else
+      I::set_last(B::next_ptr(a));
     first= a;
     *B::prev_ptr(a)= &first;
     C::inc();
   }
   inline void push_back(T *a)
   {
-    insert_after(back(), a);
-  }
-  inline T *back()
-  {
-    T *t= front();
-    if (t)
-    {
-      while (*B::next_ptr(t))
-        t= *B::next_ptr(t);
-    }
-    return t;
+    T **last= I::get_last();
+    *B::next_ptr(a)= *last;
+    *last= a;
+    *B::prev_ptr(a)= last;
+    I::set_last(B::next_ptr(a));
   }
   inline void insert_after(T *pos, T *a)
   {
@@ -105,6 +110,8 @@ public:
         T *old_next= *B::next_ptr(a);
         *B::prev_ptr(old_next)= B::next_ptr(a);
       }
+      else
+        I::set_last(B::next_ptr(a));
     }
   }
   inline void remove(T *a)
@@ -112,6 +119,8 @@ public:
     T *next= *B::next_ptr(a);
     if (next)
       *B::prev_ptr(next)= *B::prev_ptr(a);
+    else
+      I::set_last(*B::prev_ptr(a));
     **B::prev_ptr(a)= next;
     C::dec();
   }
@@ -120,16 +129,21 @@ public:
   void swap(I_P_List<T, B, C> &rhs)
   {
     swap_variables(T *, first, rhs.first);
+    I::swap(rhs);
     if (first)
       *B::prev_ptr(first)= &first;
+    else
+      I::set_last(&first);
     if (rhs.first)
       *B::prev_ptr(rhs.first)= &rhs.first;
+    else
+      I::set_last(&rhs.first);
     C::swap(rhs);
   }
 #ifndef _lint
-  friend class I_P_List_iterator<T, B, C>;
+  friend class I_P_List_iterator<T, B, C, I>;
 #endif
-  typedef I_P_List_iterator<T, B, C> Iterator;
+  typedef I_P_List_iterator<T, B, C, I> Iterator;
 };
 
 
@@ -137,15 +151,19 @@ public:
    Iterator for I_P_List.
 */
 
-template <typename T, typename B, typename C = I_P_List_null_counter>
+template <typename T, typename B,
+          typename C = I_P_List_null_counter,
+          typename I = I_P_List_no_push_back<T> >
 class I_P_List_iterator
 {
-  const I_P_List<T, B, C> *list;
+  const I_P_List<T, B, C, I> *list;
   T *current;
 public:
-  I_P_List_iterator(const I_P_List<T, B, C> &a) : list(&a), current(a.first) {}
-  I_P_List_iterator(const I_P_List<T, B, C> &a, T* current_arg) : list(&a), current(current_arg) {}
-  inline void init(const I_P_List<T, B, C> &a)
+  I_P_List_iterator(const I_P_List<T, B, C, I> &a)
+    : list(&a), current(a.first) {}
+  I_P_List_iterator(const I_P_List<T, B, C, I> &a, T* current_arg)
+    : list(&a), current(current_arg) {}
+  inline void init(const I_P_List<T, B, C, I> &a)
   {
     list= &a;
     current= a.first;
@@ -203,4 +221,40 @@ public:
   uint elements() const { return m_counter; }
 };
 
+
+/**
+  A null insertion policy class for I_P_List to be used
+  in cases when push_back() operation is not necessary.
+*/
+
+template <typename T> class I_P_List_no_push_back
+{
+protected:
+  I_P_List_no_push_back(T **a) {};
+  void set_last(T **a) {}
+  /*
+    T** get_last() const method is intentionally left unimplemented
+    in order to prohibit usage of push_back() method in lists which
+    use this policy.
+  */
+  void swap(I_P_List_no_push_back<T> &rhs) {}
+};
+
+
+/**
+  An insertion policy class for I_P_List which can
+  be used when fast push_back() operation is required.
+*/
+
+template <typename T> class I_P_List_fast_push_back
+{
+  T **last;
+protected:
+  I_P_List_fast_push_back(T **a) : last(a) { };
+  void set_last(T **a) { last= a; }
+  T** get_last() const { return last; }
+  void swap(I_P_List_fast_push_back<T> &rhs)
+  { swap_variables(T**, last, rhs.last); }
+};
+
 #endif