#At file:///home/dlenev/src/bzr/mysql-next-4284-nl-review/ based on revid:kostja@stripped
3058 Dmitry Lenev 2010-01-25
Tentative patch implementing new type-of-operation-aware metadata locks.
Fixes bug #46272 "MySQL 5.4.4, new MDL: unnecessary deadlock" and bug
#37346 "innodb does not detect deadlock between update and alter table".
After review fixes in progress.
Changed metadata locking code to use compatibility matrices specified
through bitmaps rather than hard-coded by switch() statements.
modified:
sql/mdl.cc
sql/mdl.h
=== modified file 'sql/mdl.cc'
--- a/sql/mdl.cc 2010-01-22 09:38:20 +0000
+++ b/sql/mdl.cc 2010-01-25 12:45:01 +0000
@@ -51,6 +51,14 @@ private:
/**
+ Get a bit corresponding to enum_mdl_type value in a granted/waiting bitmaps
+ and compatibility matrices.
+*/
+
+#define MDL_BIT(A) (1 << A)
+
+
+/**
The lock context. Created internally for an acquired lock.
For a given name, there exists only one MDL_lock instance,
and it exists only when the lock has been granted.
@@ -82,78 +90,87 @@ public:
bool is_empty() const
{
- return (granted.is_empty() && waiting.is_empty());
+ return (m_granted.is_empty() && m_waiting.is_empty());
}
+ virtual const uchar* get_incompatible_granted_types_bitmap() const = 0;
+ virtual const uchar* get_incompatible_waiting_types_bitmap() const = 0;
+
bool has_pending_conflicting_lock(enum_mdl_type type);
- virtual bool can_grant_lock(const MDL_context *requestor_ctx,
- enum_mdl_type type, bool is_upgrade)= 0;
+ bool can_grant_lock(enum_mdl_type type, bool is_upgrade) const;
inline static MDL_lock *create(const MDL_key *key);
- bool has_pending_lock(enum_mdl_type type) const
- {
- Ticket_iterator it(waiting);
- MDL_ticket *ticket;
-
- safe_mutex_assert_owner(&m_mutex);
-
- /*
- QQ: Should we add counters for pending/granted lock
- types to speed up this and other similar methods?
- */
-
- while ((ticket= it++))
- if (ticket->get_type() == type)
- return TRUE;
- return FALSE;
- }
-
- bool has_granted_lock(enum_mdl_type type) const
- {
- Ticket_iterator it(granted);
- MDL_ticket *ticket;
-
- safe_mutex_assert_owner(&m_mutex);
-
- while ((ticket= it++))
- if (ticket->get_type() == type)
- return TRUE;
- return FALSE;
- }
-
void add_pending(MDL_ticket *ticket)
{
safe_mutex_assert_owner(&m_mutex);
- waiting.push_front(ticket);
+ m_waiting.push_front(ticket);
+ m_waiting_bitmap|= (uchar) MDL_BIT(ticket->get_type());
}
void remove_pending(MDL_ticket *ticket)
{
safe_mutex_assert_owner(&m_mutex);
- waiting.remove(ticket);
+ m_waiting.remove(ticket);
+
+ Ticket_iterator it(m_waiting);
+ MDL_ticket *remaining_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
+ removed last ticket of particular type, then we need to update
+ bitmap of waiting ticket's types.
+ Note that in most common case, i.e. when shared lock is removed
+ from waiting queue, we are likely to find ticket of the same
+ type early without performing full iteration through the list.
+ So this method should not be too expensive.
+ */
+ while ((remaining_ticket= it++))
+ if (remaining_ticket->get_type() == ticket->get_type())
+ return;
+ m_waiting_bitmap&= ~(uchar) MDL_BIT(ticket->get_type());
}
void add_granted(MDL_ticket *ticket)
{
safe_mutex_assert_owner(&m_mutex);
- granted.push_front(ticket);
+ m_granted.push_front(ticket);
+ m_granted_bitmap|= (uchar) MDL_BIT(ticket->get_type());
}
void remove_granted(MDL_ticket *ticket)
{
safe_mutex_assert_owner(&m_mutex);
- granted.remove(ticket);
+ m_granted.remove(ticket);
+
+ Ticket_iterator it(m_granted);
+ MDL_ticket *remaining_ticket;
+
+ while ((remaining_ticket= it++))
+ if (remaining_ticket->get_type() == ticket->get_type())
+ return;
+ /*
+ Check if granted queue has another ticket with the same type as
+ one which was removed. If there is no such ticket, i.e. we have
+ removed last ticket of particular type, then we need to update
+ bitmap of granted ticket's types.
+ Note that in most common case, i.e. when shared lock is
+ released, we are likely to find ticket of the same type early
+ without performing full iteration through the list. So this
+ method should not be too expensive.
+ */
+ m_granted_bitmap&= ~(uchar) MDL_BIT(ticket->get_type());
}
void notify_shared_locks(MDL_context *ctx)
{
- Ticket_iterator it(granted);
+ Ticket_iterator it(m_granted);
MDL_ticket *conflicting_ticket;
safe_mutex_assert_owner(&m_mutex);
@@ -174,7 +191,7 @@ public:
*/
void wake_up_waiters()
{
- MDL_lock::Ticket_iterator it(waiting);
+ MDL_lock::Ticket_iterator it(m_waiting);
MDL_ticket *awake_ticket;
safe_mutex_assert_owner(&m_mutex);
@@ -183,15 +200,24 @@ public:
awake_ticket->get_ctx()->awake();
}
+private:
/** List of granted tickets for this lock. */
- Ticket_list granted;
+ Ticket_list m_granted;
/** Tickets for contexts waiting to acquire a lock. */
- Ticket_list waiting;
+ Ticket_list m_waiting;
+ /** Bitmap of types of granted tickets for this lock. */
+ uchar m_granted_bitmap;
+ /** Bitmap of types of waiting tickets for this lock. */
+ uchar m_waiting_bitmap;
+
+public:
MDL_lock(const MDL_key *key_arg)
: key(key_arg),
cached_object(NULL),
cached_object_release_hook(NULL),
+ m_granted_bitmap(0),
+ m_waiting_bitmap(0),
m_ref_usage(0),
m_ref_release(0),
m_is_destroyed(FALSE)
@@ -244,8 +270,18 @@ public:
: MDL_lock(key_arg)
{ }
- virtual bool can_grant_lock(const MDL_context *requestor_ctx,
- enum_mdl_type type, bool is_upgrade);
+ virtual const uchar* get_incompatible_granted_types_bitmap() const
+ {
+ return m_granted_incompatible;
+ }
+ virtual const uchar* get_incompatible_waiting_types_bitmap() const
+ {
+ return m_waiting_incompatible;
+ }
+
+private:
+ static const uchar m_granted_incompatible[MDL_TYPE_END];
+ static const uchar m_waiting_incompatible[MDL_TYPE_END];
};
@@ -261,8 +297,18 @@ public:
: MDL_lock(key_arg)
{ }
- virtual bool can_grant_lock(const MDL_context *requestor_ctx,
- enum_mdl_type type, bool is_upgrade);
+ virtual const uchar* get_incompatible_granted_types_bitmap() const
+ {
+ return m_granted_incompatible;
+ }
+ virtual const uchar* get_incompatible_waiting_types_bitmap() const
+ {
+ return m_waiting_incompatible;
+ }
+
+private:
+ static const uchar m_granted_incompatible[MDL_TYPE_END];
+ static const uchar m_waiting_incompatible[MDL_TYPE_END];
};
@@ -729,17 +775,9 @@ static inline void mdl_exit_cond(THD *th
/**
- Check if request for the global metadata lock can be satisfied given
- its current state,
-
- @param requestor_ctx The context that identifies the owner of the request.
- @param type_arg The requested type of global lock. Usually derived
- from the type of lock on individual object to be
- requested. See table below.
- @param is_upgrade TRUE if we are performing lock upgrade (not unused).
-
- @retval TRUE - Lock request can be satisfied
- @retval FALSE - There is some conflicting lock
+ Compatibility (or rather "incompatibility") matrices for global metadata
+ lock. Arrays of bitmaps which elements specify which granted/waiting locks
+ are incompatible with type of lock being requested.
Here is how types of individual locks are translated to type of global lock:
@@ -771,59 +809,23 @@ static inline void mdl_exit_cond(THD *th
type of locks we don't even have any accounting for them.
*/
-bool
-MDL_global_lock::can_grant_lock(const MDL_context *requestor_ctx,
- enum_mdl_type type_arg,
- bool is_upgrade)
-{
- switch (type_arg)
- {
- case MDL_SHARED:
- if (! granted.is_empty() &&
- granted.front()->get_type() == MDL_INTENTION_EXCLUSIVE)
- {
- /*
- We are going to obtain global shared lock and there is active
- intention exclusive lock. Have to wait.
- */
- return FALSE;
- }
- return TRUE;
- break;
- case MDL_INTENTION_EXCLUSIVE:
- if ((! granted.is_empty() && granted.front()->get_type() == MDL_SHARED) ||
- has_pending_lock(MDL_SHARED))
- {
- /*
- We are going to obtain intention exclusive global lock and
- there is active or pending shared global lock. Have to wait.
- */
- return FALSE;
- }
- else
- return TRUE;
- break;
- default:
- DBUG_ASSERT(0);
- break;
- }
- return FALSE;
-}
-
+const uchar MDL_global_lock::m_granted_incompatible[MDL_TYPE_END] =
+{
+ MDL_BIT(MDL_INTENTION_EXCLUSIVE), 0, 0, 0, 0, 0, MDL_BIT(MDL_SHARED), 0
+};
-/**
- Check if request for the per-object lock can be satisfied given current
- state of the lock.
+const uchar MDL_global_lock::m_waiting_incompatible[MDL_TYPE_END] =
+{
+ 0, 0, 0, 0, 0, 0, MDL_BIT(MDL_SHARED), 0
+};
- @param requestor_ctx The context that identifies the owner of the request.
- @param type_arg The requested lock type.
- @param is_upgrade Must be set to TRUE when we are upgrading an
- upgradable lock to exclusive.
- @retval TRUE Lock request can be satisfied
- @retval FALSE There is some conflicting lock.
+/**
+ Compatibility (or rather "incompatibility") matrices for per-object
+ metadata lock. Arrays of bitmaps which elements specify which granted/
+ waiting locks are incompatible with type of lock being requested.
- This function defines the following compatibility matrix for metadata locks:
+ Here is compatibility matrix defined by these arrays:
| Satisfied or pending requests for the MDL_lock |
Request | Active | Pending |
@@ -850,111 +852,91 @@ MDL_global_lock::can_grant_lock(const MD
thanks to usage of the MDL_context::find_ticket() method.
*/
-bool
-MDL_object_lock::can_grant_lock(const MDL_context *requestor_ctx,
- enum_mdl_type type_arg,
- bool is_upgrade)
+const uchar MDL_object_lock::m_granted_incompatible[MDL_TYPE_END] =
{
- bool can_grant= FALSE;
+ MDL_BIT(MDL_EXCLUSIVE),
+ MDL_BIT(MDL_EXCLUSIVE),
+ MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE),
+ MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE) |
+ MDL_BIT(MDL_UPGRADABLE_NO_WRITE),
+ MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE) |
+ MDL_BIT(MDL_UPGRADABLE_NO_WRITE) | MDL_BIT(MDL_SHARED_WRITE),
+ MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE) |
+ MDL_BIT(MDL_UPGRADABLE_NO_WRITE) | MDL_BIT(MDL_SHARED_WRITE) |
+ MDL_BIT(MDL_SHARED_READ),
+ 0,
+ MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE) |
+ MDL_BIT(MDL_UPGRADABLE_NO_WRITE) | MDL_BIT(MDL_SHARED_WRITE) |
+ MDL_BIT(MDL_SHARED_READ) | MDL_BIT(MDL_SHARED_HIGH_PRIO) |
+ MDL_BIT(MDL_SHARED)
+};
- switch (type_arg) {
- case MDL_SHARED:
- case MDL_SHARED_HIGH_PRIO:
- if (granted.is_empty() || granted.front()->is_shared())
- {
- /* Pending exclusive locks have higher priority over shared locks. */
- if (! has_pending_lock(MDL_EXCLUSIVE) || type_arg == MDL_SHARED_HIGH_PRIO)
- can_grant= TRUE;
- }
- break;
- case MDL_SHARED_READ:
- if (granted.is_empty() ||
- (granted.front()->is_shared() &&
- ! has_granted_lock(MDL_UPGRADABLE_NO_READ_WRITE)))
- {
- if (! has_pending_lock(MDL_EXCLUSIVE) &&
- ! has_pending_lock(MDL_UPGRADABLE_NO_READ_WRITE))
- can_grant= TRUE;
- }
- break;
- case MDL_SHARED_WRITE:
- if (granted.is_empty() ||
- (granted.front()->is_shared() &&
- ! has_granted_lock(MDL_UPGRADABLE_NO_WRITE) &&
- ! has_granted_lock(MDL_UPGRADABLE_NO_READ_WRITE)))
- {
- if (! has_pending_lock(MDL_EXCLUSIVE) &&
- ! has_pending_lock(MDL_UPGRADABLE_NO_READ_WRITE) &&
- ! has_pending_lock(MDL_UPGRADABLE_NO_WRITE))
- can_grant= TRUE;
- }
- break;
- case MDL_UPGRADABLE_NO_WRITE:
- if (granted.is_empty() ||
- (granted.front()->is_shared() &&
- ! has_granted_lock(MDL_UPGRADABLE_NO_WRITE) &&
- ! has_granted_lock(MDL_UPGRADABLE_NO_READ_WRITE)))
- {
- if (! has_pending_lock(MDL_EXCLUSIVE) &&
- ! has_pending_lock(MDL_UPGRADABLE_NO_READ_WRITE) &&
- ! has_granted_lock(MDL_SHARED_WRITE))
- can_grant= TRUE;
- }
- break;
- case MDL_UPGRADABLE_NO_READ_WRITE:
- if (granted.is_empty() ||
- (granted.front()->is_shared() &&
- ! has_granted_lock(MDL_UPGRADABLE_NO_WRITE) &&
- ! has_granted_lock(MDL_UPGRADABLE_NO_READ_WRITE)))
- {
- if (! has_pending_lock(MDL_EXCLUSIVE) &&
- ! has_granted_lock(MDL_SHARED_READ) &&
- ! has_granted_lock(MDL_SHARED_WRITE))
- can_grant= TRUE;
- }
- break;
- case MDL_EXCLUSIVE:
- if (is_upgrade)
- {
- MDL_ticket *conflicting_ticket;
- MDL_lock::Ticket_iterator it(granted);
+const uchar MDL_object_lock::m_waiting_incompatible[MDL_TYPE_END] =
+{
+ MDL_BIT(MDL_EXCLUSIVE),
+ 0,
+ MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE),
+ MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE) |
+ MDL_BIT(MDL_UPGRADABLE_NO_WRITE),
+ MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE),
+ MDL_BIT(MDL_EXCLUSIVE) ,
+ 0,
+ 0
+};
- DBUG_ASSERT(has_granted_lock(MDL_UPGRADABLE_NO_WRITE) ||
- has_granted_lock(MDL_UPGRADABLE_NO_READ_WRITE));
- /*
- Check if there are other contexts which hold locks on this object.
+/**
+ Check if request for the metadata lock can be satisfied given its
+ current state.
- Note that thanks to the fact that UNW and UNRW locks are always
- acquired before shared locks the below check is actually equivalent
- to checking if MDL_lock has any active tickets besides of ticket
- being upgraded.
+ @param type_arg The requested lock type.
+ @param is_upgrade Must be set to TRUE when we are upgrading an
+ upgradable lock to exclusive.
- QQ: Should we change API to pass ticket being upgraded instead of
- "requestor_ctx" to simplify the below check?
- */
+ @retval TRUE Lock request can be satisfied
+ @retval FALSE There is some conflicting lock.
- while ((conflicting_ticket= it++))
- {
- if (conflicting_ticket->get_ctx() != requestor_ctx)
- break;
- }
- /* Grant lock if there are no conflicting shared locks. */
- if (conflicting_ticket == NULL)
- can_grant= TRUE;
- break;
- }
- else if (granted.is_empty())
- {
- /*
- We are trying to acquire fresh MDL_EXCLUSIVE and there are no active
- shared or exclusive locks.
- */
+ @note In cases then current context already has "stronger" type
+ of lock on the object it will be automatically granted
+ thanks to usage of the MDL_context::find_ticket() method.
+*/
+
+bool
+MDL_lock::can_grant_lock(enum_mdl_type type_arg, bool is_upgrade) const
+{
+ bool can_grant= FALSE;
+
+ if (is_upgrade)
+ {
+ DBUG_ASSERT(m_granted_bitmap & (MDL_BIT(MDL_UPGRADABLE_NO_WRITE) |
+ MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE)));
+
+ /*
+ Thanks to the fact that we always acquire upgradable locks before
+ any other locks here we can assume that all non-upgradable locks
+ are held by context other than performing upgrade. So we only need
+ to take into account lock being upgraded (i.e. substract it from
+ the granted locks bitmap) when looking at granted locks incompatible
+ with lock being requested.
+ */
+ if (!((m_granted_bitmap & ~(MDL_BIT(MDL_UPGRADABLE_NO_WRITE) |
+ MDL_BIT(MDL_UPGRADABLE_NO_READ_WRITE))) &
+ get_incompatible_granted_types_bitmap()[type_arg]))
+ can_grant= TRUE;
+ }
+ else
+ {
+ /*
+ New lock request can be satisfied iff:
+ - There are no incompatible types of satisfied requests
+ - There are no waiting requests which have higher priority
+ than this request.
+ */
+ if (! (m_granted_bitmap &
+ get_incompatible_granted_types_bitmap()[type_arg]) &&
+ ! (m_waiting_bitmap &
+ get_incompatible_waiting_types_bitmap()[type_arg]))
can_grant= TRUE;
- }
- break;
- default:
- DBUG_ASSERT(0);
}
return can_grant;
}
@@ -976,30 +958,7 @@ bool MDL_lock::has_pending_conflicting_l
safe_mutex_assert_not_owner(&LOCK_open);
pthread_mutex_lock(&m_mutex);
- switch (type)
- {
- case MDL_SHARED:
- case MDL_SHARED_HIGH_PRIO:
- result= has_pending_lock(MDL_EXCLUSIVE);
- break;
- case MDL_SHARED_READ:
- result= has_pending_lock(MDL_EXCLUSIVE) ||
- has_pending_lock(MDL_UPGRADABLE_NO_READ_WRITE);
- break;
- case MDL_SHARED_WRITE:
- result= has_pending_lock(MDL_EXCLUSIVE) ||
- has_pending_lock(MDL_UPGRADABLE_NO_WRITE) ||
- has_pending_lock(MDL_UPGRADABLE_NO_READ_WRITE);
- break;
- case MDL_UPGRADABLE_NO_WRITE:
- case MDL_UPGRADABLE_NO_READ_WRITE:
- case MDL_INTENTION_EXCLUSIVE:
- case MDL_EXCLUSIVE:
- default:
- /* This method should not be used for these types of tickets. */
- DBUG_ASSERT(0);
- break;
- }
+ result= (m_waiting_bitmap & get_incompatible_granted_types_bitmap()[type]);
pthread_mutex_unlock(&m_mutex);
return result;
}
@@ -1125,7 +1084,7 @@ MDL_context::acquire_lock_impl(MDL_reque
old_msg= MDL_ENTER_COND(m_thd, mysys_var, &m_ctx_wakeup_cond,
&lock->m_mutex);
- if (! lock->can_grant_lock(this, mdl_request->type, FALSE))
+ if (! lock->can_grant_lock(mdl_request->type, FALSE))
{
lock->add_pending(ticket);
@@ -1133,7 +1092,7 @@ MDL_context::acquire_lock_impl(MDL_reque
{
pthread_cond_wait(&m_ctx_wakeup_cond, &lock->m_mutex);
}
- while (! lock->can_grant_lock(this, mdl_request->type, FALSE) &&
+ while (! lock->can_grant_lock(mdl_request->type, FALSE) &&
! mysys_var->abort);
if (mysys_var->abort)
@@ -1282,9 +1241,9 @@ MDL_context::try_acquire_lock_impl(MDL_r
return TRUE;
}
- if (lock->can_grant_lock(this, mdl_request->type, FALSE))
+ if (lock->can_grant_lock(mdl_request->type, FALSE))
{
- lock->granted.push_front(ticket);
+ lock->add_granted(ticket);
pthread_mutex_unlock(&lock->m_mutex);
ticket->m_state= MDL_ACQUIRED;
@@ -1470,7 +1429,7 @@ bool MDL_context::acquire_exclusive_lock
old_msg= MDL_ENTER_COND(m_thd, mysys_var, &m_ctx_wakeup_cond,
&lock->m_mutex);
- while (!lock->can_grant_lock(this, mdl_request->type, FALSE))
+ while (!lock->can_grant_lock(mdl_request->type, FALSE))
{
if (m_lt_or_ha_sentinel)
{
@@ -1738,7 +1697,7 @@ MDL_context::upgrade_shared_lock_to_excl
while (1)
{
- if (mdl_lock->can_grant_lock(this, MDL_EXCLUSIVE, TRUE))
+ if (mdl_lock->can_grant_lock(MDL_EXCLUSIVE, TRUE))
break;
mdl_lock->notify_shared_locks(this);
@@ -1777,8 +1736,14 @@ MDL_context::upgrade_shared_lock_to_excl
}
}
- /* Set the new type of lock in the ticket. */
+ /*
+ Set the new type of lock in the ticket. To update state of MDL_lock object
+ correctly we need to temporarily exclude ticket from the granted queue and
+ then include it back.
+ */
+ mdl_lock->remove_granted(mdl_ticket);
mdl_ticket->m_type= MDL_EXCLUSIVE;
+ mdl_lock->add_granted(mdl_ticket);
mdl_lock->remove_pending(pending_ticket);
@@ -1956,7 +1921,7 @@ MDL_context::wait_for_lock(MDL_request *
if (! (lock= mdl_locks.find(key)))
return FALSE;
- if (lock->can_grant_lock(this, mdl_request->type, FALSE))
+ if (lock->can_grant_lock(mdl_request->type, FALSE))
{
pthread_mutex_unlock(&lock->m_mutex);
return FALSE;
@@ -2122,8 +2087,12 @@ void MDL_ticket::downgrade_exclusive_loc
QQ: What about CREATE TABLE SELECT, what kind of lock should we
use there?
+ To update state of MDL_lock object correctly we need to temporarily
+ exclude ticket from the granted queue and then include it back.
*/
+ m_lock->remove_granted(this);
m_type= MDL_UPGRADABLE_NO_READ_WRITE;
+ m_lock->add_granted(this);
m_lock->wake_up_waiters();
pthread_mutex_unlock(&m_lock->m_mutex);
}
=== modified file 'sql/mdl.h'
--- a/sql/mdl.h 2010-01-22 09:38:20 +0000
+++ b/sql/mdl.h 2010-01-25 12:45:01 +0000
@@ -140,7 +140,9 @@ enum enum_mdl_type {
To be used for CREATE/DROP/RENAME TABLE statements and for execution of
certain phases of other DDL statements.
*/
- MDL_EXCLUSIVE};
+ MDL_EXCLUSIVE,
+ /* This should be the last !!! */
+ MDL_TYPE_END};
/** States which a metadata lock ticket can have. */
Attachment: [text/bzr-bundle] bzr/dlenev@mysql.com-20100125124501-9bjrvvd3iqjyl1no.bundle
| Thread |
|---|
| • bzr commit into mysql-5.6-next-mr branch (dlenev:3058) Bug#46272 | Dmitry Lenev | 25 Jan |
