#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 Osipov | 4 Aug |
