MDEV-19749 MDL scalability regression after backup locks

use ilist instread of I_P_List because it's generally
slightly faster on inserting, removing and iterating

4 files changed, 78 insertions, 115 deletions

diff --git a/sql/mdl.cc b/sql/mdl.cc
index 287e0cb5f65..51387fb0f9a 100644
--- a/sql/mdl.cc
+++ b/sql/mdl.cc
@@ -1,4 +1,5 @@
 /* Copyright (c) 2007, 2012, Oracle and/or its affiliates.
+   Copyright (c) 2020, MariaDB
 
    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
@@ -27,6 +28,7 @@
 #include <tpool.h>
 #include <pfs_metadata_provider.h>
 #include <mysql/psi/mysql_mdl.h>
+#include <algorithm>
 
 static PSI_memory_key key_memory_MDL_context_acquire_locks;
 
@@ -340,21 +342,16 @@ public:
 
   class Ticket_list
   {
+    using List= ilist<MDL_ticket>;
   public:
-    typedef I_P_List<MDL_ticket,
-                     I_P_List_adapter<MDL_ticket,
-                                      &MDL_ticket::next_in_lock,
-                                      &MDL_ticket::prev_in_lock>,
-                     I_P_List_null_counter,
-                     I_P_List_fast_push_back<MDL_ticket> >
-            List;
-    operator const List &() const { return m_list; }
     Ticket_list() :m_bitmap(0) {}
 
     void add_ticket(MDL_ticket *ticket);
     void remove_ticket(MDL_ticket *ticket);
-    bool is_empty() const { return m_list.is_empty(); }
+    bool is_empty() const { return m_list.empty(); }
     bitmap_t bitmap() const { return m_bitmap; }
+    List::const_iterator begin() const { return m_list.begin(); }
+    List::const_iterator end() const { return m_list.end(); }
   private:
     void clear_bit_if_not_in_list(enum_mdl_type type);
   private:
@@ -364,8 +361,6 @@ public:
     bitmap_t m_bitmap;
   };
 
-  typedef Ticket_list::List::Iterator Ticket_iterator;
-
 
   /**
     Helper struct which defines how different types of locks are handled
@@ -574,14 +569,12 @@ public:
   { return m_strategy->needs_notification(ticket); }
   void notify_conflicting_locks(MDL_context *ctx)
   {
-    Ticket_iterator it(m_granted);
-    MDL_ticket *conflicting_ticket;
-    while ((conflicting_ticket= it++))
+    for (const auto &conflicting_ticket : m_granted)
     {
-      if (conflicting_ticket->get_ctx() != ctx &&
-          m_strategy->conflicting_locks(conflicting_ticket))
+      if (conflicting_ticket.get_ctx() != ctx &&
+          m_strategy->conflicting_locks(&conflicting_ticket))
       {
-        MDL_context *conflicting_ctx= conflicting_ticket->get_ctx();
+        MDL_context *conflicting_ctx= conflicting_ticket.get_ctx();
 
         ctx->get_owner()->
           notify_shared_lock(conflicting_ctx->get_owner(),
@@ -723,21 +716,21 @@ struct mdl_iterate_arg
 
 static my_bool mdl_iterate_lock(MDL_lock *lock, mdl_iterate_arg *arg)
 {
-  int res= FALSE;
   /*
     We can skip check for m_strategy here, becase m_granted
     must be empty for such locks anyway.
   */
   mysql_prlock_rdlock(&lock->m_rwlock);
-  MDL_lock::Ticket_iterator granted_it(lock->m_granted);
-  MDL_lock::Ticket_iterator waiting_it(lock->m_waiting);
-  MDL_ticket *ticket;
-  while ((ticket= granted_it++) && !(res= arg->callback(ticket, arg->argument, true)))
-    /* no-op */;
-  while ((ticket= waiting_it++) && !(res= arg->callback(ticket, arg->argument, false)))
-    /* no-op */;
+  bool res= std::any_of(lock->m_granted.begin(), lock->m_granted.end(),
+                        [arg](MDL_ticket &ticket) {
+                          return arg->callback(&ticket, arg->argument, true);
+                        });
+  res= std::any_of(lock->m_waiting.begin(), lock->m_waiting.end(),
+                   [arg](MDL_ticket &ticket) {
+                     return arg->callback(&ticket, arg->argument, false);
+                   });
   mysql_prlock_unlock(&lock->m_rwlock);
-  return MY_TEST(res);
+  return res;
 }
 
 
@@ -1214,11 +1207,8 @@ MDL_wait::timed_wait(MDL_context_owner *owner, struct timespec *abs_timeout,
 
 void MDL_lock::Ticket_list::clear_bit_if_not_in_list(enum_mdl_type type)
 {
-  MDL_lock::Ticket_iterator it(m_list);
-  const MDL_ticket *ticket;
-
-  while ((ticket= it++))
-    if (ticket->get_type() == type)
+  for (const auto &ticket : m_list)
+    if (ticket.get_type() == type)
       return;
   m_bitmap&= ~ MDL_BIT(type);
 }
@@ -1241,30 +1231,15 @@ void MDL_lock::Ticket_list::add_ticket(MDL_ticket *ticket)
   if ((this == &(ticket->get_lock()->m_waiting)) &&
       wsrep_thd_is_BF(ticket->get_ctx()->get_thd(), false))
   {
-    Ticket_iterator itw(ticket->get_lock()->m_waiting);
-    MDL_ticket *waiting;
-    MDL_ticket *prev=NULL;
-    bool added= false;
-
     DBUG_ASSERT(WSREP(ticket->get_ctx()->get_thd()));
 
-    while ((waiting= itw++) && !added)
-    {
-      if (!wsrep_thd_is_BF(waiting->get_ctx()->get_thd(), true))
-      {
-        WSREP_DEBUG("MDL add_ticket inserted before: %lu %s",
-                    thd_get_thread_id(waiting->get_ctx()->get_thd()),
-                    wsrep_thd_query(waiting->get_ctx()->get_thd()));
-        /* Insert the ticket before the first non-BF waiting thd. */
-        m_list.insert_after(prev, ticket);
-        added= true;
-      }
-      prev= waiting;
-    }
-
-    /* Otherwise, insert the ticket at the back of the waiting list. */
-    if (!added)
-      m_list.push_back(ticket);
+    m_list.insert(std::find_if(ticket->get_lock()->m_waiting.begin(),
+                               ticket->get_lock()->m_waiting.end(),
+                               [](const MDL_ticket &waiting) {
+                                 return !wsrep_thd_is_BF(
+                                     waiting.get_ctx()->get_thd(), true);
+                               }),
+                  *ticket);
   }
   else
 #endif /* WITH_WSREP */
@@ -1273,7 +1248,7 @@ void MDL_lock::Ticket_list::add_ticket(MDL_ticket *ticket)
       Add ticket to the *back* of the queue to ensure fairness
       among requests with the same priority.
     */
-    m_list.push_back(ticket);
+    m_list.push_back(*ticket);
   }
   m_bitmap|= MDL_BIT(ticket->get_type());
 }
@@ -1286,7 +1261,7 @@ void MDL_lock::Ticket_list::add_ticket(MDL_ticket *ticket)
 
 void MDL_lock::Ticket_list::remove_ticket(MDL_ticket *ticket)
 {
-  m_list.remove(ticket);
+  m_list.remove(*ticket);
   /*
     Check if waiting queue has another ticket with the same type as
     one which was removed. If there is no such ticket, i.e. we have
@@ -1314,8 +1289,6 @@ void MDL_lock::Ticket_list::remove_ticket(MDL_ticket *ticket)
 
 void MDL_lock::reschedule_waiters()
 {
-  MDL_lock::Ticket_iterator it(m_waiting);
-  MDL_ticket *ticket;
   bool skip_high_priority= false;
   bitmap_t hog_lock_types= hog_lock_types_bitmap();
 
@@ -1370,20 +1343,20 @@ void MDL_lock::reschedule_waiters()
                   grant SNRW lock and there are no pending S or
                   SH locks.
   */
-  while ((ticket= it++))
+  for (auto it= m_waiting.begin(); it != m_waiting.end(); ++it)
   {
     /*
       Skip high-prio, strong locks if earlier we have decided to give way to
       low-prio, weaker locks.
     */
     if (skip_high_priority &&
-        ((MDL_BIT(ticket->get_type()) & hog_lock_types) != 0))
+        ((MDL_BIT(it->get_type()) & hog_lock_types) != 0))
       continue;
 
-    if (can_grant_lock(ticket->get_type(), ticket->get_ctx(),
+    if (can_grant_lock(it->get_type(), it->get_ctx(),
                        skip_high_priority))
     {
-      if (! ticket->get_ctx()->m_wait.set_status(MDL_wait::GRANTED))
+      if (!it->get_ctx()->m_wait.set_status(MDL_wait::GRANTED))
       {
         /*
           Satisfy the found request by updating lock structures.
@@ -1393,15 +1366,19 @@ void MDL_lock::reschedule_waiters()
           when manages to do so, already sees an updated state of the
           MDL_lock object.
         */
-        m_waiting.remove_ticket(ticket);
-        m_granted.add_ticket(ticket);
+        auto prev_it= std::prev(it); // this might be begin()-- but the hack
+                                     // works because list is circular
+        m_waiting.remove_ticket(&*it);
+        m_granted.add_ticket(&*it);
 
         /*
           Increase counter of successively granted high-priority strong locks,
           if we have granted one.
         */
-        if ((MDL_BIT(ticket->get_type()) & hog_lock_types) != 0)
+        if ((MDL_BIT(it->get_type()) & hog_lock_types) != 0)
           m_hog_lock_count++;
+
+        it= prev_it;
       }
       /*
         If we could not update the wait slot of the waiter,
@@ -1774,14 +1751,13 @@ MDL_lock::can_grant_lock(enum_mdl_type type_arg,
 
   if (m_granted.bitmap() & granted_incompat_map)
   {
-    Ticket_iterator it(m_granted);
     bool can_grant= true;
 
     /* Check that the incompatible lock belongs to some other context. */
-    while (auto ticket= it++)
+    for (const auto &ticket : m_granted)
     {
-      if (ticket->get_ctx() != requestor_ctx &&
-          ticket->is_incompatible_when_granted(type_arg))
+      if (ticket.get_ctx() != requestor_ctx &&
+          ticket.is_incompatible_when_granted(type_arg))
       {
         can_grant= false;
 #ifdef WITH_WSREP
@@ -1793,12 +1769,12 @@ MDL_lock::can_grant_lock(enum_mdl_type type_arg,
             requestor_ctx->get_thd()->wsrep_cs().mode() ==
             wsrep::client_state::m_rsu)
         {
-          wsrep_handle_mdl_conflict(requestor_ctx, ticket, &key);
+          wsrep_handle_mdl_conflict(requestor_ctx, &ticket, &key);
           if (wsrep_log_conflicts)
           {
-            auto key= ticket->get_key();
+            auto key= ticket.get_key();
             WSREP_INFO("MDL conflict db=%s table=%s ticket=%d solved by abort",
-                       key->db_name(), key->name(), ticket->get_type());
+                       key->db_name(), key->name(), ticket.get_type());
           }
           continue;
         }
@@ -1820,12 +1796,10 @@ MDL_lock::can_grant_lock(enum_mdl_type type_arg,
 inline unsigned long
 MDL_lock::get_lock_owner() const
 {
-  Ticket_iterator it(m_granted);
-  MDL_ticket *ticket;
+  if (m_granted.is_empty())
+    return 0;
 
-  if ((ticket= it++))
-    return ticket->get_ctx()->get_thread_id();
-  return 0;
+  return m_granted.begin()->get_ctx()->get_thread_id();
 }
 
 
@@ -2234,18 +2208,16 @@ MDL_context::clone_ticket(MDL_request *mdl_request)
 #ifndef DBUG_OFF
 bool MDL_lock::check_if_conflicting_replication_locks(MDL_context *ctx)
 {
-  Ticket_iterator it(m_granted);
-  MDL_ticket *conflicting_ticket;
   rpl_group_info *rgi_slave= ctx->get_thd()->rgi_slave;
 
   if (!rgi_slave->gtid_sub_id)
     return 0;
 
-  while ((conflicting_ticket= it++))
+  for (const auto &conflicting_ticket : m_granted)
   {
-    if (conflicting_ticket->get_ctx() != ctx)
+    if (conflicting_ticket.get_ctx() != ctx)
     {
-      MDL_context *conflicting_ctx= conflicting_ticket->get_ctx();
+      MDL_context *conflicting_ctx= conflicting_ticket.get_ctx();
       rpl_group_info *conflicting_rgi_slave;
       conflicting_rgi_slave= conflicting_ctx->get_thd()->rgi_slave;
 
@@ -2622,16 +2594,11 @@ MDL_context::upgrade_shared_lock(MDL_ticket *mdl_ticket,
 bool MDL_lock::visit_subgraph(MDL_ticket *waiting_ticket,
                               MDL_wait_for_graph_visitor *gvisitor)
 {
-  MDL_ticket *ticket;
   MDL_context *src_ctx= waiting_ticket->get_ctx();
   bool result= TRUE;
 
   mysql_prlock_rdlock(&m_rwlock);
 
-  /* Must be initialized after taking a read lock. */
-  Ticket_iterator granted_it(m_granted);
-  Ticket_iterator waiting_it(m_waiting);
-
   /*
     MDL_lock's waiting and granted queues and MDL_context::m_waiting_for
     member are updated by different threads when the lock is granted
@@ -2698,46 +2665,44 @@ bool MDL_lock::visit_subgraph(MDL_ticket *waiting_ticket,
     node. In workloads that involve wait-for graph loops this
     has proven to be a more efficient strategy [citation missing].
   */
-  while ((ticket= granted_it++))
+  for (const auto& ticket : m_granted)
   {
     /* Filter out edges that point to the same node. */
-    if (ticket->get_ctx() != src_ctx &&
-        ticket->is_incompatible_when_granted(waiting_ticket->get_type()) &&
-        gvisitor->inspect_edge(ticket->get_ctx()))
+    if (ticket.get_ctx() != src_ctx &&
+        ticket.is_incompatible_when_granted(waiting_ticket->get_type()) &&
+        gvisitor->inspect_edge(ticket.get_ctx()))
     {
       goto end_leave_node;
     }
   }
 
-  while ((ticket= waiting_it++))
+  for (const auto &ticket : m_waiting)
   {
     /* Filter out edges that point to the same node. */
-    if (ticket->get_ctx() != src_ctx &&
-        ticket->is_incompatible_when_waiting(waiting_ticket->get_type()) &&
-        gvisitor->inspect_edge(ticket->get_ctx()))
+    if (ticket.get_ctx() != src_ctx &&
+        ticket.is_incompatible_when_waiting(waiting_ticket->get_type()) &&
+        gvisitor->inspect_edge(ticket.get_ctx()))
     {
       goto end_leave_node;
     }
   }
 
   /* Recurse and inspect all adjacent nodes. */
-  granted_it.rewind();
-  while ((ticket= granted_it++))
+  for (const auto &ticket : m_granted)
   {
-    if (ticket->get_ctx() != src_ctx &&
-        ticket->is_incompatible_when_granted(waiting_ticket->get_type()) &&
-        ticket->get_ctx()->visit_subgraph(gvisitor))
+    if (ticket.get_ctx() != src_ctx &&
+        ticket.is_incompatible_when_granted(waiting_ticket->get_type()) &&
+        ticket.get_ctx()->visit_subgraph(gvisitor))
     {
       goto end_leave_node;
     }
   }
 
-  waiting_it.rewind();
-  while ((ticket= waiting_it++))
+  for (const auto &ticket : m_waiting)
   {
-    if (ticket->get_ctx() != src_ctx &&
-        ticket->is_incompatible_when_waiting(waiting_ticket->get_type()) &&
-        ticket->get_ctx()->visit_subgraph(gvisitor))
+    if (ticket.get_ctx() != src_ctx &&
+        ticket.is_incompatible_when_waiting(waiting_ticket->get_type()) &&
+        ticket.get_ctx()->visit_subgraph(gvisitor))
     {
       goto end_leave_node;
     }
@@ -3286,7 +3251,7 @@ const char *wsrep_get_mdl_namespace_name(MDL_key::enum_mdl_namespace ns)
   return "UNKNOWN";
 }
 
-void MDL_ticket::wsrep_report(bool debug)
+void MDL_ticket::wsrep_report(bool debug) const
 {
   if (!debug) return;
 
diff --git a/sql/mdl.h b/sql/mdl.h
index 4659238e9f2..dd10b3a45d0 100644
--- a/sql/mdl.h
+++ b/sql/mdl.h
@@ -1,6 +1,7 @@
 #ifndef MDL_H
 #define MDL_H
 /* Copyright (c) 2009, 2012, Oracle and/or its affiliates. All rights reserved.
+   Copyright (c) 2020, MariaDB
 
    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
@@ -16,6 +17,7 @@
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
 
 #include "sql_plist.h"
+#include "ilist.h"
 #include <my_sys.h>
 #include <m_string.h>
 #include <mysql_com.h>
@@ -685,7 +687,7 @@ public:
           threads/contexts.
 */
 
-class MDL_ticket : public MDL_wait_for_subgraph
+class MDL_ticket : public MDL_wait_for_subgraph, public ilist_node<>
 {
 public:
   /**
@@ -694,15 +696,9 @@ public:
   */
   MDL_ticket *next_in_context;
   MDL_ticket **prev_in_context;
-  /**
-    Pointers for participating in the list of satisfied/pending requests
-    for the lock. Externally accessible.
-  */
-  MDL_ticket *next_in_lock;
-  MDL_ticket **prev_in_lock;
 public:
 #ifdef WITH_WSREP
-  void wsrep_report(bool debug);
+  void wsrep_report(bool debug) const;
 #endif /* WITH_WSREP */
   bool has_pending_conflicting_lock() const;
 
diff --git a/sql/wsrep_mysqld.cc b/sql/wsrep_mysqld.cc
index e818d577768..0c31631d19b 100644
--- a/sql/wsrep_mysqld.cc
+++ b/sql/wsrep_mysqld.cc
@@ -1,4 +1,5 @@
 /* Copyright 2008-2015 Codership Oy <http://www.codership.com>
+   Copyright (c) 2020, MariaDB
 
    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
@@ -2368,7 +2369,7 @@ void wsrep_to_isolation_end(THD *thd)
 */
 
 void wsrep_handle_mdl_conflict(MDL_context *requestor_ctx,
-                               MDL_ticket *ticket,
+                               const MDL_ticket *ticket,
                                const MDL_key *key)
 {
   /* Fallback to the non-wsrep behaviour */
diff --git a/sql/wsrep_mysqld.h b/sql/wsrep_mysqld.h
index 6d1ff1d1ed0..3347a94cdd6 100644
--- a/sql/wsrep_mysqld.h
+++ b/sql/wsrep_mysqld.h
@@ -1,4 +1,5 @@
 /* Copyright 2008-2017 Codership Oy <http://www.codership.com>
+   Copyright (c) 2020, MariaDB
 
    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
@@ -527,7 +528,7 @@ void wsrep_keys_free(wsrep_key_arr_t* key_arr);
 
 extern void
 wsrep_handle_mdl_conflict(MDL_context *requestor_ctx,
-                          MDL_ticket *ticket,
+                          const MDL_ticket *ticket,
                           const MDL_key *key);
 
 enum wsrep_thread_type {