List:Commits« Previous MessageNext Message »
From:Konstantin Osipov Date:August 4 2010 3:37pm
Subject:bzr commit into mysql-trunk-runtime branch (kostja:3091)
View as plain text  
#At file:///opt/local/work/trunk-runtime-lenev/ based on revid:kostja@stripped

 3091 Konstantin Osipov	2010-08-04
      Bug 52044, a review comment.
      Turn the wait-for graph visitor into an abstract class.
      Renames. Simplify the algorithm that chooses the deadlock
      victim.

    modified:
      sql/mdl.cc
      sql/mdl.h
      sql/sql_base.cc
      sql/table.cc
      sql/table.h
=== modified file 'sql/mdl.cc'
--- a/sql/mdl.cc	2010-08-02 20:12:33 +0000
+++ b/sql/mdl.cc	2010-08-04 15:37:20 +0000
@@ -99,6 +99,68 @@ private:
 
 
 /**
+  A context of the recursive traversal through all contexts
+  in all sessions in search for deadlock.
+*/
+
+class Deadlock_detection_visitor: public MDL_wait_for_graph_visitor
+{
+public:
+  Deadlock_detection_visitor(MDL_context *start_node_arg)
+    : m_start_node(start_node_arg),
+      m_victim(NULL),
+      m_current_search_depth(0),
+      m_found_deadlock(FALSE)
+  {
+    m_table_shares_visited= 0;
+  }
+  virtual bool enter_node(MDL_context *node);
+  virtual void leave_node(MDL_context *node);
+
+  virtual bool inspect_edge(MDL_context *dest);
+
+  MDL_context *get_victim() const { return m_victim; }
+private:
+  /**
+    Change the deadlock victim to a new one if it has lower deadlock
+    weight.
+  */
+  void opt_change_victim_to(MDL_context *new_victim);
+private:
+  /**
+    The context which has initiated the search. There
+    can be multiple searches happening in parallel at the same time.
+  */
+  MDL_context *m_start_node;
+  /** If a deadlock is found, the context that identifies the victim. */
+  MDL_context *m_victim;
+  /** Set to the 0 at start. Increased whenever
+    we descend into another MDL context (aka traverse to the next
+    wait-for graph node). When MAX_SEARCH_DEPTH is reached, we
+    assume that a deadlock is found, even if we have not found a
+    loop.
+  */
+  uint m_current_search_depth;
+  /** TRUE if we found a deadlock. */
+  bool m_found_deadlock;
+  /**
+    Maximum depth for deadlock searches. After this depth is
+    achieved we will unconditionally declare that there is a
+    deadlock.
+
+    @note This depth should be small enough to avoid stack
+          being exhausted by recursive search algorithm.
+
+    TODO: Find out what is the optimal value for this parameter.
+          Current value is safe, but probably sub-optimal,
+          as there is an anecdotal evidence that real-life
+          deadlocks are even shorter typically.
+  */
+  static const uint MAX_SEARCH_DEPTH= 32;
+};
+
+
+/**
   Enter a node of a wait-for graph. After
   a node is entered, inspect_edge() will be called
   for all wait-for destinations of this node. Then
@@ -110,11 +172,15 @@ private:
   @retval  FALSE OK.
 */
 
-bool Deadlock_detection_visitor::enter_node(MDL_context * /* unused */)
+bool Deadlock_detection_visitor::enter_node(MDL_context *node)
 {
-  if (++m_current_search_depth >= MAX_SEARCH_DEPTH)
-    return TRUE;
-  return FALSE;
+  m_found_deadlock= ++m_current_search_depth >= MAX_SEARCH_DEPTH;
+  if (m_found_deadlock)
+  {
+    DBUG_ASSERT(! m_victim);
+    opt_change_victim_to(node);
+  }
+  return m_found_deadlock;
 }
 
 
@@ -123,9 +189,11 @@ bool Deadlock_detection_visitor::enter_n
   depth. Clear the node for debug safety.
 */
 
-void Deadlock_detection_visitor::leave_node(MDL_context * /* unused */)
+void Deadlock_detection_visitor::leave_node(MDL_context *node)
 {
   --m_current_search_depth;
+  if (m_found_deadlock)
+    opt_change_victim_to(node);
 }
 
 
@@ -138,7 +206,8 @@ void Deadlock_detection_visitor::leave_n
 
 bool Deadlock_detection_visitor::inspect_edge(MDL_context *node)
 {
-  return node == m_start_node;
+  m_found_deadlock= node == m_start_node;
+  return m_found_deadlock;
 }
 
 
@@ -150,7 +219,7 @@ bool Deadlock_detection_visitor::inspect
   @retval !new_victim New victim became the current.
 */
 
-MDL_context *
+void
 Deadlock_detection_visitor::opt_change_victim_to(MDL_context *new_victim)
 {
   if (m_victim == NULL ||
@@ -159,10 +228,10 @@ Deadlock_detection_visitor::opt_change_v
     /* Swap victims, unlock the old one. */
     MDL_context *tmp= m_victim;
     m_victim= new_victim;
-    return tmp;
+    m_victim->lock_deadlock_victim();
+    if (tmp)
+      tmp->unlock_deadlock_victim();
   }
-  /* No change, unlock the current context. */
-  return new_victim;
 }
 
 
@@ -285,8 +354,8 @@ public:
 
   void remove_ticket(Ticket_list MDL_lock::*queue, MDL_ticket *ticket);
 
-  bool find_deadlock(MDL_ticket *waiting_ticket,
-                     Deadlock_detection_visitor *dvisitor);
+  bool visit_subgraph(MDL_ticket *waiting_ticket,
+                      MDL_wait_for_graph_visitor *gvisitor);
 
   /** List of granted tickets for this lock. */
   Ticket_list m_granted;
@@ -813,7 +882,7 @@ uint MDL_ticket::get_deadlock_weight() c
 {
   return (m_lock->key.mdl_namespace() == MDL_key::GLOBAL ||
           m_type >= MDL_SHARED_NO_WRITE ?
-          MDL_DEADLOCK_WEIGHT_DDL : MDL_DEADLOCK_WEIGHT_DML);
+          DEADLOCK_WEIGHT_DDL : DEADLOCK_WEIGHT_DML);
 }
 
 
@@ -1316,7 +1385,12 @@ bool MDL_lock::has_pending_conflicting_l
 }
 
 
-Wait_for_edge::~Wait_for_edge()
+MDL_wait_for_graph_visitor::~MDL_wait_for_graph_visitor()
+{
+}
+
+
+MDL_wait_for_subgraph::~MDL_wait_for_subgraph()
 {
 }
 
@@ -1900,8 +1974,8 @@ MDL_context::upgrade_shared_lock_to_excl
   a deadlock is found when the same node is seen twice.
 */
 
-bool MDL_lock::find_deadlock(MDL_ticket *waiting_ticket,
-                             Deadlock_detection_visitor *dvisitor)
+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();
@@ -1970,7 +2044,7 @@ bool MDL_lock::find_deadlock(MDL_ticket 
     are visiting it but this is OK: in the worst case we might do some
     extra work and one more context might be chosen as a victim.
   */
-  if (dvisitor->enter_node(src_ctx))
+  if (gvisitor->enter_node(src_ctx))
     goto end;
 
   /*
@@ -1984,7 +2058,7 @@ bool MDL_lock::find_deadlock(MDL_ticket 
     /* Filter out edges that point to the same node. */
     if (ticket->get_ctx() != src_ctx &&
         ticket->is_incompatible_when_granted(waiting_ticket->get_type()) &&
-        dvisitor->inspect_edge(ticket->get_ctx()))
+        gvisitor->inspect_edge(ticket->get_ctx()))
     {
       goto end_leave_node;
     }
@@ -1995,7 +2069,7 @@ bool MDL_lock::find_deadlock(MDL_ticket 
     /* Filter out edges that point to the same node. */
     if (ticket->get_ctx() != src_ctx &&
         ticket->is_incompatible_when_waiting(waiting_ticket->get_type()) &&
-        dvisitor->inspect_edge(ticket->get_ctx()))
+        gvisitor->inspect_edge(ticket->get_ctx()))
     {
       goto end_leave_node;
     }
@@ -2007,7 +2081,7 @@ bool MDL_lock::find_deadlock(MDL_ticket 
   {
     if (ticket->get_ctx() != src_ctx &&
         ticket->is_incompatible_when_granted(waiting_ticket->get_type()) &&
-        ticket->get_ctx()->find_deadlock(dvisitor))
+        ticket->get_ctx()->visit_subgraph(gvisitor))
     {
       goto end_leave_node;
     }
@@ -2018,7 +2092,7 @@ bool MDL_lock::find_deadlock(MDL_ticket 
   {
     if (ticket->get_ctx() != src_ctx &&
         ticket->is_incompatible_when_waiting(waiting_ticket->get_type()) &&
-        ticket->get_ctx()->find_deadlock(dvisitor))
+        ticket->get_ctx()->visit_subgraph(gvisitor))
     {
       goto end_leave_node;
     }
@@ -2027,7 +2101,7 @@ bool MDL_lock::find_deadlock(MDL_ticket 
   result= FALSE;
 
 end_leave_node:
-  dvisitor->leave_node(src_ctx);
+  gvisitor->leave_node(src_ctx);
 
 end:
   mysql_prlock_unlock(&m_rwlock);
@@ -2045,9 +2119,9 @@ end:
   @retval FALSE
 */
 
-bool MDL_ticket::find_deadlock(Deadlock_detection_visitor *dvisitor)
+bool MDL_ticket::accept_visitor(MDL_wait_for_graph_visitor *gvisitor)
 {
-  return m_lock->find_deadlock(this, dvisitor);
+  return m_lock->visit_subgraph(this, gvisitor);
 }
 
 
@@ -2067,7 +2141,7 @@ bool MDL_ticket::find_deadlock(Deadlock_
   @retval FALSE
 */
 
-bool MDL_context::find_deadlock(Deadlock_detection_visitor *dvisitor)
+bool MDL_context::visit_subgraph(MDL_wait_for_graph_visitor *gvisitor)
 {
   MDL_context *m_unlock_ctx= this;
   bool result= FALSE;
@@ -2075,19 +2149,9 @@ bool MDL_context::find_deadlock(Deadlock
   mysql_prlock_rdlock(&m_LOCK_waiting_for);
 
   if (m_waiting_for)
-  {
-    result= m_waiting_for->find_deadlock(dvisitor);
-    if (result)
-      m_unlock_ctx= dvisitor->opt_change_victim_to(this);
-  }
-  /*
-    We may recurse into the same MDL_context more than once
-    in case this is not the starting node. Make sure we release the
-    read lock as it's been taken, except for 1 read lock for
-    the deadlock victim.
-  */
-  if (m_unlock_ctx)
-    mysql_prlock_unlock(&m_unlock_ctx->m_LOCK_waiting_for);
+    result= m_waiting_for->accept_visitor(gvisitor);
+
+  mysql_prlock_unlock(&m_unlock_ctx->m_LOCK_waiting_for);
 
   return result;
 }
@@ -2109,14 +2173,14 @@ void MDL_context::find_deadlock()
   while (1)
   {
     /*
-      The fact that we use fresh instance of dvisitor for each
+      The fact that we use fresh instance of gvisitor for each
       search performed by find_deadlock() below is important,
       the code responsible for victim selection relies on this.
     */
     Deadlock_detection_visitor dvisitor(this);
     MDL_context *victim;
 
-    if (! find_deadlock(&dvisitor))
+    if (! visit_subgraph(&dvisitor))
     {
       /* No deadlocks are found! */
       break;
@@ -2137,7 +2201,7 @@ void MDL_context::find_deadlock()
       context was waiting is concurrently satisfied.
     */
     (void) victim->m_wait.set_status(MDL_wait::VICTIM);
-    mysql_prlock_unlock(&victim->m_LOCK_waiting_for);
+    victim->unlock_deadlock_victim();
 
     if (victim == this)
       break;

=== modified file 'sql/mdl.h'
--- a/sql/mdl.h	2010-08-02 20:12:33 +0000
+++ b/sql/mdl.h	2010-08-04 15:37:20 +0000
@@ -360,95 +360,49 @@ public:
 typedef void (*mdl_cached_object_release_hook)(void *);
 
 
-enum enum_mdl_deadlock_weight
-{
-  MDL_DEADLOCK_WEIGHT_DML= 0,
-  MDL_DEADLOCK_WEIGHT_DDL= 100
-};
-
-
 /**
-  A context of the recursive traversal through all contexts
-  in all sessions in search for deadlock.
+  An abstract class for inspection of a connected
+  subgraph of the wait-for graph.
 */
 
-class Deadlock_detection_visitor
+class MDL_wait_for_graph_visitor
 {
 public:
-  Deadlock_detection_visitor(MDL_context *start_node_arg)
-    : m_start_node(start_node_arg),
-      m_victim(NULL),
-      m_current_search_depth(0),
-      m_table_shares_visited(0)
-  {}
-  bool enter_node(MDL_context * /* unused */);
-  void leave_node(MDL_context * /* unused */);
-
-  bool inspect_edge(MDL_context *dest);
-
-  MDL_context *get_victim() const { return m_victim; }
-
-  /**
-    Change the deadlock victim to a new one if it has lower deadlock
-    weight.
-  */
-  MDL_context *opt_change_victim_to(MDL_context *new_victim);
-private:
-  /**
-    The context which has initiated the search. There
-    can be multiple searches happening in parallel at the same time.
-  */
-  MDL_context *m_start_node;
-  /** If a deadlock is found, the context that identifies the victim. */
-  MDL_context *m_victim;
-  /** Set to the 0 at start. Increased whenever
-    we descend into another MDL context (aka traverse to the next
-    wait-for graph node). When MAX_SEARCH_DEPTH is reached, we
-    assume that a deadlock is found, even if we have not found a
-    loop.
-  */
-  uint m_current_search_depth;
-  /**
-    Maximum depth for deadlock searches. After this depth is
-    achieved we will unconditionally declare that there is a
-    deadlock.
-
-    @note This depth should be small enough to avoid stack
-          being exhausted by recursive search algorithm.
-
-    TODO: Find out what is the optimal value for this parameter.
-          Current value is safe, but probably sub-optimal,
-          as there is an anecdotal evidence that real-life
-          deadlocks are even shorter typically.
-  */
-  static const uint MAX_SEARCH_DEPTH= 32;
+  virtual bool enter_node(MDL_context *node) = 0;
+  virtual void leave_node(MDL_context *node) = 0;
 
+  virtual bool inspect_edge(MDL_context *dest) = 0;
+  virtual ~MDL_wait_for_graph_visitor();
 public:
   /**
     Number of TABLE_SHARE objects visited by deadlock detector so far.
-    Used by TABLE_SHARE::find_deadlock() method to implement recursive
-    locking for LOCK_open mutex.
+    Used by TABLE_SHARE::accept_visitor() method to implement
+    recursive locking for LOCK_open mutex.
   */
   uint m_table_shares_visited;
 };
 
-
 /**
   Abstract class representing an edge in the waiters graph
   to be traversed by deadlock detection algorithm.
 */
 
-class Wait_for_edge
+class MDL_wait_for_subgraph
 {
 public:
-  virtual ~Wait_for_edge();
+  virtual ~MDL_wait_for_subgraph();
 
   /**
     Accept a wait-for graph visitor to inspect the node
     this edge is leading to.
   */
-  virtual bool find_deadlock(Deadlock_detection_visitor *dvisitor) = 0;
+  virtual bool accept_visitor(MDL_wait_for_graph_visitor *gvisitor) = 0;
 
+  enum enum_deadlock_weight
+  {
+    DEADLOCK_WEIGHT_DML= 0,
+    DEADLOCK_WEIGHT_DDL= 100
+  };
   /* A helper used to determine which lock request should be aborted. */
   virtual uint get_deadlock_weight() const = 0;
 };
@@ -474,7 +428,7 @@ public:
           threads/contexts.
 */
 
-class MDL_ticket : public Wait_for_edge
+class MDL_ticket : public MDL_wait_for_subgraph
 {
 public:
   /**
@@ -508,7 +462,8 @@ public:
   bool is_incompatible_when_granted(enum_mdl_type type) const;
   bool is_incompatible_when_waiting(enum_mdl_type type) const;
 
-  virtual bool find_deadlock(Deadlock_detection_visitor *dvisitor);
+  /** Implement MDL_wait_for_subgraph interface. */
+  virtual bool accept_visitor(MDL_wait_for_graph_visitor *dvisitor);
   virtual uint get_deadlock_weight() const;
 private:
   friend class MDL_context;
@@ -676,8 +631,6 @@ public:
   {
     return m_needs_thr_lock_abort;
   }
-
-  bool find_deadlock(Deadlock_detection_visitor *dvisitor);
 public:
   /**
     If our request for a lock is scheduled, or aborted by the deadlock
@@ -775,7 +728,7 @@ private:
     by inspecting waiting queues, but we'd very much like it to be
     readily available to the wait-for graph iterator.
    */
-  Wait_for_edge *m_waiting_for;
+  MDL_wait_for_subgraph *m_waiting_for;
 private:
   MDL_ticket *find_ticket(MDL_request *mdl_req,
                           bool *is_transactional);
@@ -786,8 +739,10 @@ private:
 public:
   void find_deadlock();
 
+  bool visit_subgraph(MDL_wait_for_graph_visitor *dvisitor);
+
   /** Inform the deadlock detector there is an edge in the wait-for graph. */
-  void will_wait_for(Wait_for_edge *waiting_for_arg)
+  void will_wait_for(MDL_wait_for_subgraph *waiting_for_arg)
   {
     mysql_prlock_wrlock(&m_LOCK_waiting_for);
     m_waiting_for=  waiting_for_arg;
@@ -801,6 +756,14 @@ public:
     m_waiting_for= NULL;
     mysql_prlock_unlock(&m_LOCK_waiting_for);
   }
+  void lock_deadlock_victim()
+  {
+    mysql_prlock_rdlock(&m_LOCK_waiting_for);
+  }
+  void unlock_deadlock_victim()
+  {
+    mysql_prlock_unlock(&m_LOCK_waiting_for);
+  }
 private:
   MDL_context(const MDL_context &rhs);          /* not implemented */
   MDL_context &operator=(MDL_context &rhs);     /* not implemented */

=== modified file 'sql/sql_base.cc'
--- a/sql/sql_base.cc	2010-08-02 18:51:03 +0000
+++ b/sql/sql_base.cc	2010-08-04 15:37:20 +0000
@@ -1085,7 +1085,7 @@ bool close_cached_tables(THD *thd, TABLE
     {
       /* The below method will unlock LOCK_open and frees share's memory. */
       if (share->wait_until_flushed(&thd->mdl_context, &abstime,
-                                    MDL_DEADLOCK_WEIGHT_DDL))
+                                    MDL_wait_for_subgraph::DEADLOCK_WEIGHT_DDL))
       {
         mysql_mutex_unlock(&LOCK_open);
         result= TRUE;

=== modified file 'sql/table.cc'
--- a/sql/table.cc	2010-08-02 20:12:33 +0000
+++ b/sql/table.cc	2010-08-04 15:37:20 +0000
@@ -3038,9 +3038,9 @@ Table_check_intact::check(TABLE *table, 
   @retval FALSE
 */
 
-bool Wait_for_flush::find_deadlock(Deadlock_detection_visitor *dvisitor)
+bool Wait_for_flush::accept_visitor(MDL_wait_for_graph_visitor *gvisitor)
 {
-  return m_share->find_deadlock(this, dvisitor);
+  return m_share->visit_subgraph(this, gvisitor);
 }
 
 
@@ -3062,11 +3062,11 @@ uint Wait_for_flush::get_deadlock_weight
   @retval FALSE
 */
 
-bool TABLE_SHARE::find_deadlock(Wait_for_flush *waiting_ticket,
-                                Deadlock_detection_visitor *dvisitor)
+bool TABLE_SHARE::visit_subgraph(Wait_for_flush *wait_for_flush,
+                                 MDL_wait_for_graph_visitor *dvisitor)
 {
   TABLE *table;
-  MDL_context *src_ctx= waiting_ticket->get_ctx();
+  MDL_context *src_ctx= wait_for_flush->get_ctx();
   bool result= TRUE;
 
   /*
@@ -3132,7 +3132,7 @@ bool TABLE_SHARE::find_deadlock(Wait_for
   tables_it.rewind();
   while ((table= tables_it++))
   {
-    if (table->in_use->mdl_context.find_deadlock(dvisitor))
+    if (table->in_use->mdl_context.visit_subgraph(dvisitor))
     {
       goto end_leave_node;
     }

=== modified file 'sql/table.h'
--- a/sql/table.h	2010-08-02 20:12:33 +0000
+++ b/sql/table.h	2010-08-04 15:37:20 +0000
@@ -515,7 +515,7 @@ public:
   such waits in MDL deadlock detector.
 */
 
-class Wait_for_flush : public Wait_for_edge
+class Wait_for_flush : public MDL_wait_for_subgraph
 {
   MDL_context *m_ctx;
   TABLE_SHARE *m_share;
@@ -529,9 +529,9 @@ public:
 
   MDL_context *get_ctx() const { return m_ctx; }
 
-  bool find_deadlock(Deadlock_detection_visitor *dvisitor);
+  virtual bool accept_visitor(MDL_wait_for_graph_visitor *dvisitor);
 
-  uint get_deadlock_weight() const;
+  virtual uint get_deadlock_weight() const;
 
   /**
     Pointers for participating in the list of waiters for table share.
@@ -882,8 +882,8 @@ struct TABLE_SHARE
     return (tmp_table == SYSTEM_TMP_TABLE || is_view) ? 0 : table_map_id;
   }
 
-  bool find_deadlock(Wait_for_flush *waiting_ticket,
-                     Deadlock_detection_visitor *dvisitor);
+   bool visit_subgraph(Wait_for_flush *waiting_ticket,
+                       MDL_wait_for_graph_visitor *gvisitor);
 
   bool wait_until_flushed(MDL_context *mdl_context,
                           struct timespec *abstime,


Attachment: [text/bzr-bundle] bzr/kostja@sun.com-20100804153720-3hffclwiz4h19asl.bundle
Thread
bzr commit into mysql-trunk-runtime branch (kostja:3091)Konstantin Osipov4 Aug