mdl.cc 61.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
/* Copyright (C) 2007-2008 MySQL AB

   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
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */


#include "mdl.h"
Konstantin Osipov's avatar
Konstantin Osipov committed
18
#include "debug_sync.h"
Konstantin Osipov's avatar
Konstantin Osipov committed
19 20
#include <hash.h>
#include <mysqld_error.h>
21

22 23 24 25

void notify_shared_lock(THD *thd, MDL_ticket *conflicting_ticket);


Konstantin Osipov's avatar
Konstantin Osipov committed
26
static bool mdl_initialized= 0;
27

28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

/**
  A collection of all MDL locks. A singleton,
  there is only one instance of the map in the server.
  Maps MDL_key to MDL_lock instances.
*/

class MDL_map
{
public:
  void init();
  void destroy();
  MDL_lock *find(const MDL_key *key);
  MDL_lock *find_or_insert(const MDL_key *key);
  void remove(MDL_lock *lock);
private:
  bool move_from_hash_to_lock_mutex(MDL_lock *lock);
private:
  /** All acquired locks in the server. */
  HASH m_locks;
  /* Protects access to m_locks hash. */
  pthread_mutex_t m_mutex;
};


53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
enum enum_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.
*/

class Deadlock_detection_context
{
public:
  Deadlock_detection_context(MDL_context *start_arg)
    : start(start_arg),
      victim(NULL),
      current_search_depth(0)
  { }
  MDL_context *start;
  MDL_context *victim;
  uint current_search_depth;
  static const uint MAX_SEARCH_DEPTH= 1000;
};


/**
  Get a bit corresponding to enum_mdl_type value in a granted/waiting bitmaps
  and compatibility matrices.
*/

#define MDL_BIT(A) static_cast<MDL_lock::bitmap_t>(1U << A)

88
/**
Konstantin Osipov's avatar
Konstantin Osipov committed
89
  The lock context. Created internally for an acquired lock.
Konstantin Osipov's avatar
Konstantin Osipov committed
90
  For a given name, there exists only one MDL_lock instance,
Konstantin Osipov's avatar
Konstantin Osipov committed
91 92
  and it exists only when the lock has been granted.
  Can be seen as an MDL subsystem's version of TABLE_SHARE.
93 94 95 96

  This is an abstract class which lacks information about
  compatibility rules for lock types. They should be specified
  in its descendants.
97 98
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
99
class MDL_lock
100
{
Konstantin Osipov's avatar
Konstantin Osipov committed
101
public:
102
  typedef uchar bitmap_t;
Konstantin Osipov's avatar
Konstantin Osipov committed
103

104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
  class Ticket_list
  {
  public:
    typedef I_P_List<MDL_ticket,
                     I_P_List_adapter<MDL_ticket,
                                      &MDL_ticket::next_in_lock,
                                      &MDL_ticket::prev_in_lock> >
            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(); }
    bitmap_t bitmap() const { return m_bitmap; }
  private:
    void clear_bit_if_not_in_list(enum_mdl_type type);
  private:
    /** List of tickets. */
    List m_list;
    /** Bitmap of types of tickets in this list. */
    bitmap_t m_bitmap;
  };

  typedef Ticket_list::List::Iterator Ticket_iterator;
Konstantin Osipov's avatar
Konstantin Osipov committed
129

130
public:
Konstantin Osipov's avatar
Konstantin Osipov committed
131
  /** The key of the object (data) being protected. */
Konstantin Osipov's avatar
Konstantin Osipov committed
132
  MDL_key key;
133 134
  void   *cached_object;
  mdl_cached_object_release_hook cached_object_release_hook;
135 136 137 138 139 140 141
  /**
    Read-write lock protecting this lock context.

    TODO/FIXME: Replace with RW-lock which will prefer readers
                on all platforms and not only on Linux.
  */
  rw_lock_t m_rwlock;
142

Konstantin Osipov's avatar
Konstantin Osipov committed
143
  bool is_empty() const
144
  {
145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166
    return (m_granted.is_empty() && m_waiting.is_empty());
  }

  virtual const bitmap_t *incompatible_granted_types_bitmap() const = 0;
  virtual const bitmap_t *incompatible_waiting_types_bitmap() const = 0;

  bool has_pending_conflicting_lock(enum_mdl_type type);

  bool can_grant_lock(enum_mdl_type type, MDL_context *requstor_ctx) const;

  inline static MDL_lock *create(const MDL_key *key);

  void notify_shared_locks(MDL_context *ctx)
  {
    Ticket_iterator it(m_granted);
    MDL_ticket *conflicting_ticket;

    while ((conflicting_ticket= it++))
    {
      if (conflicting_ticket->get_ctx() != ctx)
        notify_shared_lock(ctx->get_thd(), conflicting_ticket);
    }
167 168
  }

169 170 171 172 173 174 175 176
  /**
    Wake up contexts which are waiting to acquire lock on the object and
    which may succeed now, when we released some lock on it or removed
    some pending request from its waiters list (the latter can happen,
    for example, when context trying to acquire exclusive on the object
    lock is killed).
  */
  void wake_up_waiters()
177
  {
178 179 180 181 182
    MDL_lock::Ticket_iterator it(m_waiting);
    MDL_ticket *awake_ticket;

    while ((awake_ticket= it++))
      awake_ticket->get_ctx()->awake(MDL_context::NORMAL_WAKE_UP);
183
  }
184
  void remove_ticket(Ticket_list MDL_lock::*queue, MDL_ticket *ticket);
Konstantin Osipov's avatar
Konstantin Osipov committed
185

186 187 188 189 190 191 192 193
  bool find_deadlock(MDL_ticket *waiting_ticket,
                     Deadlock_detection_context *deadlock_ctx);

  /** List of granted tickets for this lock. */
  Ticket_list m_granted;
  /** Tickets for contexts waiting to acquire a lock. */
  Ticket_list m_waiting;
public:
194

Konstantin Osipov's avatar
Konstantin Osipov committed
195
  MDL_lock(const MDL_key *key_arg)
196
  : key(key_arg),
Konstantin Osipov's avatar
Konstantin Osipov committed
197
    cached_object(NULL),
198 199 200 201
    cached_object_release_hook(NULL),
    m_ref_usage(0),
    m_ref_release(0),
    m_is_destroyed(FALSE)
202
  {
203
    my_rwlock_init(&m_rwlock, NULL);
204 205
  }

206 207
  virtual ~MDL_lock()
  {
208
    rwlock_destroy(&m_rwlock);
209 210 211 212 213
  }
  inline static void destroy(MDL_lock *lock);
public:
  /**
    These three members are used to make it possible to separate
214
    the mdl_locks.m_mutex mutex and MDL_lock::m_rwlock in
215 216
    MDL_map::find_or_insert() for increased scalability.
    The 'm_is_destroyed' member is only set by destroyers that
217
    have both the mdl_locks.m_mutex and MDL_lock::m_rwlock, thus
218 219 220
    holding any of the mutexes is sufficient to read it.
    The 'm_ref_usage; is incremented under protection by
    mdl_locks.m_mutex, but when 'm_is_destroyed' is set to TRUE, this
221
    member is moved to be protected by the MDL_lock::m_rwlock.
222
    This means that the MDL_map::find_or_insert() which only
223
    holds the MDL_lock::m_rwlock can compare it to 'm_ref_release'
224 225 226
    without acquiring mdl_locks.m_mutex again and if equal it can also
    destroy the lock object safely.
    The 'm_ref_release' is incremented under protection by
227
    MDL_lock::m_rwlock.
228 229 230 231 232 233 234 235 236
    Note since we are only interested in equality of these two
    counters we don't have to worry about overflows as long as
    their size is big enough to hold maximum number of concurrent
    threads on the system.
  */
  uint m_ref_usage;
  uint m_ref_release;
  bool m_is_destroyed;
};
237 238


Konstantin Osipov's avatar
Konstantin Osipov committed
239
/**
240 241
  An implementation of the global metadata lock. The only locking modes
  which are supported at the moment are SHARED and INTENTION EXCLUSIVE.
Konstantin Osipov's avatar
Konstantin Osipov committed
242 243
*/

244
class MDL_global_lock : public MDL_lock
Konstantin Osipov's avatar
Konstantin Osipov committed
245
{
Konstantin Osipov's avatar
Konstantin Osipov committed
246
public:
247 248 249
  MDL_global_lock(const MDL_key *key_arg)
    : MDL_lock(key_arg)
  { }
Konstantin Osipov's avatar
Konstantin Osipov committed
250

251 252 253 254 255 256 257 258 259 260 261 262
  virtual const bitmap_t *incompatible_granted_types_bitmap() const
  {
    return m_granted_incompatible;
  }
  virtual const bitmap_t *incompatible_waiting_types_bitmap() const
  {
    return m_waiting_incompatible;
  }

private:
  static const bitmap_t m_granted_incompatible[MDL_TYPE_END];
  static const bitmap_t m_waiting_incompatible[MDL_TYPE_END];
Konstantin Osipov's avatar
Konstantin Osipov committed
263
};
264 265


266 267 268 269 270 271 272 273 274 275 276 277
/**
  An implementation of a per-object lock. Supports SHARED, SHARED_UPGRADABLE,
  SHARED HIGH PRIORITY and EXCLUSIVE locks.
*/

class MDL_object_lock : public MDL_lock
{
public:
  MDL_object_lock(const MDL_key *key_arg)
    : MDL_lock(key_arg)
  { }

278 279 280 281 282 283 284 285 286 287 288 289
  virtual const bitmap_t *incompatible_granted_types_bitmap() const
  {
    return m_granted_incompatible;
  }
  virtual const bitmap_t *incompatible_waiting_types_bitmap() const
  {
    return m_waiting_incompatible;
  }

private:
  static const bitmap_t m_granted_incompatible[MDL_TYPE_END];
  static const bitmap_t m_waiting_incompatible[MDL_TYPE_END];
290 291
};

Konstantin Osipov's avatar
Konstantin Osipov committed
292

293
static MDL_map mdl_locks;
Konstantin Osipov's avatar
Konstantin Osipov committed
294 295 296 297

extern "C"
{
static uchar *
Konstantin Osipov's avatar
Konstantin Osipov committed
298 299
mdl_locks_key(const uchar *record, size_t *length,
              my_bool not_used __attribute__((unused)))
300
{
Konstantin Osipov's avatar
Konstantin Osipov committed
301 302 303
  MDL_lock *lock=(MDL_lock*) record;
  *length= lock->key.length();
  return (uchar*) lock->key.ptr();
304
}
Konstantin Osipov's avatar
Konstantin Osipov committed
305
} /* extern "C" */
306 307 308


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
309
  Initialize the metadata locking subsystem.
310

Konstantin Osipov's avatar
Konstantin Osipov committed
311
  This function is called at server startup.
312

Konstantin Osipov's avatar
Konstantin Osipov committed
313 314 315 316
  In particular, initializes the new global mutex and
  the associated condition variable: LOCK_mdl and COND_mdl.
  These locking primitives are implementation details of the MDL
  subsystem and are private to it.
317

Konstantin Osipov's avatar
Konstantin Osipov committed
318 319 320 321 322
  Note, that even though the new implementation adds acquisition
  of a new global mutex to the execution flow of almost every SQL
  statement, the design capitalizes on that to later save on
  look ups in the table definition cache. This leads to reduced
  contention overall and on LOCK_open in particular.
Konstantin Osipov's avatar
Konstantin Osipov committed
323 324
  Please see the description of MDL_context::acquire_shared_lock()
  for details.
325 326 327 328
*/

void mdl_init()
{
Konstantin Osipov's avatar
Konstantin Osipov committed
329 330
  DBUG_ASSERT(! mdl_initialized);
  mdl_initialized= TRUE;
331
  mdl_locks.init();
332 333 334 335
}


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
336
  Release resources of metadata locking subsystem.
337

Konstantin Osipov's avatar
Konstantin Osipov committed
338 339
  Destroys the global mutex and the condition variable.
  Called at server shutdown.
340 341 342 343
*/

void mdl_destroy()
{
Konstantin Osipov's avatar
Konstantin Osipov committed
344 345 346
  if (mdl_initialized)
  {
    mdl_initialized= FALSE;
347
    mdl_locks.destroy();
Konstantin Osipov's avatar
Konstantin Osipov committed
348
  }
349 350 351
}


352 353 354 355 356 357 358 359 360 361
/** Initialize the global hash containing all MDL locks. */

void MDL_map::init()
{
  pthread_mutex_init(&m_mutex, NULL);
  my_hash_init(&m_locks, &my_charset_bin, 16 /* FIXME */, 0, 0,
               mdl_locks_key, 0, 0);
}


362
/**
363 364 365
  Destroy the global hash containing all MDL locks.
  @pre It must be empty.
*/
366

367 368 369 370 371 372 373 374 375 376 377 378 379
void MDL_map::destroy()
{
  DBUG_ASSERT(!m_locks.records);
  pthread_mutex_destroy(&m_mutex);
  my_hash_free(&m_locks);
}


/**
  Find MDL_lock object corresponding to the key, create it
  if it does not exist.

  @retval non-NULL - Success. MDL_lock instance for the key with
380
                     locked MDL_lock::m_rwlock.
381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413
  @retval NULL     - Failure (OOM).
*/

MDL_lock* MDL_map::find_or_insert(const MDL_key *mdl_key)
{
  MDL_lock *lock;

retry:
  pthread_mutex_lock(&m_mutex);
  if (!(lock= (MDL_lock*) my_hash_search(&m_locks,
                                         mdl_key->ptr(),
                                         mdl_key->length())))
  {
    lock= MDL_lock::create(mdl_key);
    if (!lock || my_hash_insert(&m_locks, (uchar*)lock))
    {
      pthread_mutex_unlock(&m_mutex);
      MDL_lock::destroy(lock);
      return NULL;
    }
  }

  if (move_from_hash_to_lock_mutex(lock))
    goto retry;

  return lock;
}


/**
  Find MDL_lock object corresponding to the key.

  @retval non-NULL - MDL_lock instance for the key with locked
414
                     MDL_lock::m_rwlock.
415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439
  @retval NULL     - There was no MDL_lock for the key.
*/

MDL_lock* MDL_map::find(const MDL_key *mdl_key)
{
  MDL_lock *lock;

retry:
  pthread_mutex_lock(&m_mutex);
  if (!(lock= (MDL_lock*) my_hash_search(&m_locks,
                                         mdl_key->ptr(),
                                         mdl_key->length())))
  {
    pthread_mutex_unlock(&m_mutex);
    return NULL;
  }

  if (move_from_hash_to_lock_mutex(lock))
    goto retry;

  return lock;
}


/**
440
  Release mdl_locks.m_mutex mutex and lock MDL_lock::m_rwlock for lock
441 442 443 444 445 446
  object from the hash. Handle situation when object was released
  while the held no mutex.

  @retval FALSE - Success.
  @retval TRUE  - Object was released while we held no mutex, caller
                  should re-try looking up MDL_lock object in the hash.
447 448
*/

449
bool MDL_map::move_from_hash_to_lock_mutex(MDL_lock *lock)
450
{
451 452 453
  DBUG_ASSERT(! lock->m_is_destroyed);
  safe_mutex_assert_owner(&m_mutex);

Konstantin Osipov's avatar
Konstantin Osipov committed
454
  /*
455 456 457
    We increment m_ref_usage which is a reference counter protected by
    mdl_locks.m_mutex under the condition it is present in the hash and
    m_is_destroyed is FALSE.
Konstantin Osipov's avatar
Konstantin Osipov committed
458
  */
459 460 461
  lock->m_ref_usage++;
  pthread_mutex_unlock(&m_mutex);

462
  rw_wrlock(&lock->m_rwlock);
463 464 465 466 467 468 469 470 471 472 473 474 475 476
  lock->m_ref_release++;
  if (unlikely(lock->m_is_destroyed))
  {
    /*
      Object was released while we held no mutex, we need to
      release it if no others hold references to it, while our own
      reference count ensured that the object as such haven't got
      its memory released yet. We can also safely compare
      m_ref_usage and m_ref_release since the object is no longer
      present in the hash so no one will be able to find it and
      increment m_ref_usage anymore.
    */
    uint ref_usage= lock->m_ref_usage;
    uint ref_release= lock->m_ref_release;
477
    rw_unlock(&lock->m_rwlock);
478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504
    if (ref_usage == ref_release)
      MDL_lock::destroy(lock);
    return TRUE;
  }
  return FALSE;
}


/**
  Destroy MDL_lock object or delegate this responsibility to
  whatever thread that holds the last outstanding reference to
  it.
*/

void MDL_map::remove(MDL_lock *lock)
{
  uint ref_usage, ref_release;

  if (lock->cached_object)
    (*lock->cached_object_release_hook)(lock->cached_object);

  /*
    Destroy the MDL_lock object, but ensure that anyone that is
    holding a reference to the object is not remaining, if so he
    has the responsibility to release it.

    Setting of m_is_destroyed to TRUE while holding _both_
505
    mdl_locks.m_mutex and MDL_lock::m_rwlock mutexes transfers the
506
    protection of m_ref_usage from mdl_locks.m_mutex to
507 508
    MDL_lock::m_rwlock while removal of object from the hash makes
    it read-only.  Therefore whoever acquires MDL_lock::m_rwlock next
509 510 511
    will see most up to date version of m_ref_usage.

    This means that when m_is_destroyed is TRUE and we hold the
512
    MDL_lock::m_rwlock we can safely read the m_ref_usage
513 514 515 516 517 518 519
    member.
  */
  pthread_mutex_lock(&m_mutex);
  my_hash_delete(&m_locks, (uchar*) lock);
  lock->m_is_destroyed= TRUE;
  ref_usage= lock->m_ref_usage;
  ref_release= lock->m_ref_release;
520
  rw_unlock(&lock->m_rwlock);
521 522 523 524 525 526 527 528 529 530 531 532 533
  pthread_mutex_unlock(&m_mutex);
  if (ref_usage == ref_release)
    MDL_lock::destroy(lock);
}


/**
  Initialize a metadata locking context.

  This is to be called when a new server connection is created.
*/

MDL_context::MDL_context()
534 535 536 537 538 539
  :m_trans_sentinel(NULL),
  m_thd(NULL),
  m_needs_thr_lock_abort(FALSE),
  m_waiting_for(NULL),
  m_deadlock_weight(0),
  m_signal(NO_WAKE_UP)
540
{
541 542 543
  my_rwlock_init(&m_waiting_for_lock, NULL);
  pthread_mutex_init(&m_signal_lock, NULL);
  pthread_cond_init(&m_signal_cond, NULL);
544 545 546 547
}


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
548
  Destroy metadata locking context.
549

Konstantin Osipov's avatar
Konstantin Osipov committed
550 551
  Assumes and asserts that there are no active or pending locks
  associated with this context at the time of the destruction.
552

Konstantin Osipov's avatar
Konstantin Osipov committed
553 554 555 556
  Currently does nothing. Asserts that there are no pending
  or satisfied lock requests. The pending locks must be released
  prior to destruction. This is a new way to express the assertion
  that all tables are closed before a connection is destroyed.
557 558
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
559
void MDL_context::destroy()
560
{
Konstantin Osipov's avatar
Konstantin Osipov committed
561
  DBUG_ASSERT(m_tickets.is_empty());
562 563 564 565

  rwlock_destroy(&m_waiting_for_lock);
  pthread_mutex_destroy(&m_signal_lock);
  pthread_cond_destroy(&m_signal_cond);
566 567 568 569
}


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
570
  Initialize a lock request.
571

Konstantin Osipov's avatar
Konstantin Osipov committed
572
  This is to be used for every lock request.
573

Konstantin Osipov's avatar
Konstantin Osipov committed
574 575 576 577 578 579
  Note that initialization and allocation are split into two
  calls. This is to allow flexible memory management of lock
  requests. Normally a lock request is stored in statement memory
  (e.g. is a member of struct TABLE_LIST), but we would also like
  to allow allocation of lock requests in other memory roots,
  for example in the grant subsystem, to lock privilege tables.
Konstantin Osipov's avatar
Konstantin Osipov committed
580

Konstantin Osipov's avatar
Konstantin Osipov committed
581
  The MDL subsystem does not own or manage memory of lock requests.
Konstantin Osipov's avatar
Konstantin Osipov committed
582

583 584 585 586
  @param  mdl_namespace  Id of namespace of object to be locked
  @param  db             Name of database to which the object belongs
  @param  name           Name of of the object
  @param  mdl_type       The MDL lock type for the request.
587 588
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
589
void MDL_request::init(MDL_key::enum_mdl_namespace mdl_namespace,
Konstantin Osipov's avatar
Konstantin Osipov committed
590
                       const char *db_arg,
Konstantin Osipov's avatar
Konstantin Osipov committed
591 592
                       const char *name_arg,
                       enum enum_mdl_type mdl_type_arg)
593
{
594
  key.mdl_key_init(mdl_namespace, db_arg, name_arg);
Konstantin Osipov's avatar
Konstantin Osipov committed
595
  type= mdl_type_arg;
Konstantin Osipov's avatar
Konstantin Osipov committed
596
  ticket= NULL;
597 598 599
}


Konstantin Osipov's avatar
Konstantin Osipov committed
600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617
/**
  Initialize a lock request using pre-built MDL_key.

  @sa MDL_request::init(namespace, db, name, type).

  @param key_arg       The pre-built MDL key for the request.
  @param mdl_type_arg  The MDL lock type for the request.
*/

void MDL_request::init(const MDL_key *key_arg,
                       enum enum_mdl_type mdl_type_arg)
{
  key.mdl_key_init(key_arg);
  type= mdl_type_arg;
  ticket= NULL;
}


618
/**
Konstantin Osipov's avatar
Konstantin Osipov committed
619
  Allocate and initialize one lock request.
620

Konstantin Osipov's avatar
Konstantin Osipov committed
621 622 623
  Same as mdl_init_lock(), but allocates the lock and the key buffer
  on a memory root. Necessary to lock ad-hoc tables, e.g.
  mysql.* tables of grant and data dictionary subsystems.
624

625 626 627 628
  @param  mdl_namespace  Id of namespace of object to be locked
  @param  db             Name of database to which object belongs
  @param  name           Name of of object
  @param  root           MEM_ROOT on which object should be allocated
629

Konstantin Osipov's avatar
Konstantin Osipov committed
630
  @note The allocated lock request will have MDL_SHARED type.
631

Konstantin Osipov's avatar
Konstantin Osipov committed
632 633
  @retval 0      Error if out of memory
  @retval non-0  Pointer to an object representing a lock request
634 635
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
636
MDL_request *
Konstantin Osipov's avatar
Konstantin Osipov committed
637
MDL_request::create(MDL_key::enum_mdl_namespace mdl_namespace, const char *db,
Konstantin Osipov's avatar
Konstantin Osipov committed
638 639
                    const char *name, enum_mdl_type mdl_type,
                    MEM_ROOT *root)
640
{
Konstantin Osipov's avatar
Konstantin Osipov committed
641
  MDL_request *mdl_request;
642

Konstantin Osipov's avatar
Konstantin Osipov committed
643
  if (!(mdl_request= (MDL_request*) alloc_root(root, sizeof(MDL_request))))
644 645
    return NULL;

646
  mdl_request->init(mdl_namespace, db, name, mdl_type);
647

Konstantin Osipov's avatar
Konstantin Osipov committed
648
  return mdl_request;
649 650 651
}


652 653 654 655 656 657 658
uint MDL_request::get_deadlock_weight() const
{
  return key.mdl_namespace() == MDL_key::GLOBAL ||
         type > MDL_SHARED_NO_WRITE ?
    MDL_DEADLOCK_WEIGHT_DDL : MDL_DEADLOCK_WEIGHT_DML;
}

659
/**
Konstantin Osipov's avatar
Konstantin Osipov committed
660
  Auxiliary functions needed for creation/destruction of MDL_lock objects.
661

662 663
  @note Also chooses an MDL_lock descendant appropriate for object namespace.

Konstantin Osipov's avatar
Konstantin Osipov committed
664 665
  @todo This naive implementation should be replaced with one that saves
        on memory allocation by reusing released objects.
666 667
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
668
inline MDL_lock *MDL_lock::create(const MDL_key *mdl_key)
669
{
670 671 672 673 674 675 676
  switch (mdl_key->mdl_namespace())
  {
    case MDL_key::GLOBAL:
      return new MDL_global_lock(mdl_key);
    default:
      return new MDL_object_lock(mdl_key);
  }
677 678 679
}


Konstantin Osipov's avatar
Konstantin Osipov committed
680
void MDL_lock::destroy(MDL_lock *lock)
681 682 683 684 685
{
  delete lock;
}


Konstantin Osipov's avatar
Konstantin Osipov committed
686
/**
Konstantin Osipov's avatar
Konstantin Osipov committed
687
  Auxiliary functions needed for creation/destruction of MDL_ticket
Konstantin Osipov's avatar
Konstantin Osipov committed
688
  objects.
Konstantin Osipov's avatar
Konstantin Osipov committed
689

Konstantin Osipov's avatar
Konstantin Osipov committed
690 691
  @todo This naive implementation should be replaced with one that saves
        on memory allocation by reusing released objects.
Konstantin Osipov's avatar
Konstantin Osipov committed
692 693
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
694
MDL_ticket *MDL_ticket::create(MDL_context *ctx_arg, enum_mdl_type type_arg)
Konstantin Osipov's avatar
Konstantin Osipov committed
695
{
Konstantin Osipov's avatar
Konstantin Osipov committed
696
  return new MDL_ticket(ctx_arg, type_arg);
Konstantin Osipov's avatar
Konstantin Osipov committed
697 698 699
}


Konstantin Osipov's avatar
Konstantin Osipov committed
700
void MDL_ticket::destroy(MDL_ticket *ticket)
Konstantin Osipov's avatar
Konstantin Osipov committed
701 702 703 704 705
{
  delete ticket;
}


Konstantin Osipov's avatar
Konstantin Osipov committed
706
/**
Konstantin Osipov's avatar
Konstantin Osipov committed
707 708
  Helper functions and macros to be used for killable waiting in metadata
  locking subsystem.
Konstantin Osipov's avatar
Konstantin Osipov committed
709

Konstantin Osipov's avatar
Konstantin Osipov committed
710
  @sa THD::enter_cond()/exit_cond()/killed.
Konstantin Osipov's avatar
Konstantin Osipov committed
711

Konstantin Osipov's avatar
Konstantin Osipov committed
712
  @note We can't use THD::enter_cond()/exit_cond()/killed directly here
713
        since this will make metadata subsystem dependent on THD class
Konstantin Osipov's avatar
Konstantin Osipov committed
714 715 716
        and thus prevent us from writing unit tests for it. And usage of
        wrapper functions to access THD::killed/enter_cond()/exit_cond()
        will probably introduce too much overhead.
Konstantin Osipov's avatar
Konstantin Osipov committed
717 718
*/

719 720
#define MDL_ENTER_COND(A, B, C, D) \
        mdl_enter_cond(A, B, C, D, __func__, __FILE__, __LINE__)
Konstantin Osipov's avatar
Konstantin Osipov committed
721

Konstantin Osipov's avatar
Konstantin Osipov committed
722
static inline const char *mdl_enter_cond(THD *thd,
Konstantin Osipov's avatar
Konstantin Osipov committed
723
                                         st_my_thread_var *mysys_var,
724 725
                                         pthread_cond_t *cond,
                                         pthread_mutex_t *mutex,
Konstantin Osipov's avatar
Konstantin Osipov committed
726 727 728 729
                                         const char *calling_func,
                                         const char *calling_file,
                                         const unsigned int calling_line)
{
730
  safe_mutex_assert_owner(mutex);
Konstantin Osipov's avatar
Konstantin Osipov committed
731

732 733
  mysys_var->current_mutex= mutex;
  mysys_var->current_cond= cond;
Konstantin Osipov's avatar
Konstantin Osipov committed
734

Konstantin Osipov's avatar
Konstantin Osipov committed
735 736 737
  DEBUG_SYNC(thd, "mdl_enter_cond");

  return set_thd_proc_info(thd, "Waiting for table",
Konstantin Osipov's avatar
Konstantin Osipov committed
738 739 740
                           calling_func, calling_file, calling_line);
}

741 742
#define MDL_EXIT_COND(A, B, C, D) \
        mdl_exit_cond(A, B, C, D, __func__, __FILE__, __LINE__)
Konstantin Osipov's avatar
Konstantin Osipov committed
743

Konstantin Osipov's avatar
Konstantin Osipov committed
744
static inline void mdl_exit_cond(THD *thd,
Konstantin Osipov's avatar
Konstantin Osipov committed
745
                                 st_my_thread_var *mysys_var,
746
                                 pthread_mutex_t *mutex,
Konstantin Osipov's avatar
Konstantin Osipov committed
747 748 749 750 751
                                 const char* old_msg,
                                 const char *calling_func,
                                 const char *calling_file,
                                 const unsigned int calling_line)
{
752
  DBUG_ASSERT(mutex == mysys_var->current_mutex);
Konstantin Osipov's avatar
Konstantin Osipov committed
753

754
  pthread_mutex_unlock(mutex);
Konstantin Osipov's avatar
Konstantin Osipov committed
755 756 757 758 759
  pthread_mutex_lock(&mysys_var->mutex);
  mysys_var->current_mutex= 0;
  mysys_var->current_cond= 0;
  pthread_mutex_unlock(&mysys_var->mutex);

Konstantin Osipov's avatar
Konstantin Osipov committed
760 761 762
  DEBUG_SYNC(thd, "mdl_exit_cond");

  (void) set_thd_proc_info(thd, old_msg, calling_func,
Konstantin Osipov's avatar
Konstantin Osipov committed
763 764 765 766
                           calling_file, calling_line);
}


767 768 769 770 771
MDL_context::mdl_signal_type MDL_context::wait()
{
  const char *old_msg;
  st_my_thread_var *mysys_var= my_thread_var;
  mdl_signal_type result;
Konstantin Osipov's avatar
Konstantin Osipov committed
772

773
  pthread_mutex_lock(&m_signal_lock);
Konstantin Osipov's avatar
Konstantin Osipov committed
774

775
  old_msg= MDL_ENTER_COND(m_thd, mysys_var, &m_signal_cond, &m_signal_lock);
Konstantin Osipov's avatar
Konstantin Osipov committed
776

777 778 779 780 781 782 783 784 785 786 787 788
  while (! m_signal && !mysys_var->abort)
    pthread_cond_wait(&m_signal_cond, &m_signal_lock);

  result= m_signal;

  MDL_EXIT_COND(m_thd, mysys_var, &m_signal_lock, old_msg);

  return result;
}


MDL_context::mdl_signal_type MDL_context::timed_wait(ulong timeout)
Konstantin Osipov's avatar
Konstantin Osipov committed
789
{
790 791 792 793 794 795 796 797 798 799
  struct timespec abstime;
  const char *old_msg;
  mdl_signal_type result;
  st_my_thread_var *mysys_var= my_thread_var;

  pthread_mutex_lock(&m_signal_lock);

  old_msg= MDL_ENTER_COND(m_thd, mysys_var, &m_signal_cond, &m_signal_lock);

  if (! m_signal)
Konstantin Osipov's avatar
Konstantin Osipov committed
800
  {
801 802
    set_timespec(abstime, timeout);
    pthread_cond_timedwait(&m_signal_cond, &m_signal_lock, &abstime);
Konstantin Osipov's avatar
Konstantin Osipov committed
803
  }
804 805 806 807 808 809

  result= (m_signal != NO_WAKE_UP) ? m_signal : TIMEOUT_WAKE_UP;

  MDL_EXIT_COND(m_thd, mysys_var, &m_signal_lock, old_msg);

  return result;
Konstantin Osipov's avatar
Konstantin Osipov committed
810 811 812 813
}


/**
814 815 816 817 818 819
  Clear bit corresponding to the type of metadata lock in bitmap representing
  set of such types if list of tickets does not contain ticket with such type.

  @param[in,out]  bitmap  Bitmap representing set of types of locks.
  @param[in]      list    List to inspect.
  @param[in]      type    Type of metadata lock to look up in the list.
820 821
*/

822
void MDL_lock::Ticket_list::clear_bit_if_not_in_list(enum_mdl_type type)
823
{
824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849
  MDL_lock::Ticket_iterator it(m_list);
  const MDL_ticket *ticket;

  while ((ticket= it++))
    if (ticket->get_type() == type)
      return;
  m_bitmap&= ~ MDL_BIT(type);
}


/**
  Add ticket to MDL_lock's list of waiting requests and
  update corresponding bitmap of lock types.
*/

void MDL_lock::Ticket_list::add_ticket(MDL_ticket *ticket)
{
  m_list.push_front(ticket);
  m_bitmap|= MDL_BIT(ticket->get_type());
}


/**
  Remove ticket from MDL_lock's list of requests and
  update corresponding bitmap of lock types.
*/
850

851 852 853
void MDL_lock::Ticket_list::remove_ticket(MDL_ticket *ticket)
{
  m_list.remove(ticket);
854
  /*
855 856 857 858 859 860 861 862
    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.
863
  */
864
  clear_bit_if_not_in_list(ticket->get_type());
865 866 867 868
}


/**
869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904
  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:

    ----------------+-------------+
    Type of request | Correspond. |
    for indiv. lock | global lock |
    ----------------+-------------+
    S, SH, SR, SW   |   IS        |
    SNW, SNRW, X    |   IX        |
    SNW, SNRW -> X  |   IX (*)    |

  The first array specifies if particular type of request can be satisfied
  if there is granted global lock of certain type.

             | Type of active |
     Request |   global lock  |
      type   | IS(**) IX   S  |
    ---------+----------------+
    IS       |  +      +   +  |
    IX       |  +      +   -  |
    S        |  +      -   +  |

  The second array specifies if particular type of request can be satisfied
  if there is already waiting request for the global lock of certain type.
  I.e. it specifies what is the priority of different lock types.

             |    Pending   |
     Request |  global lock |
      type   | IS(**) IX  S |
    ---------+--------------+
    IS       |  +      +  + |
    IX       |  +      +  - |
    S        |  +      +  + |
Konstantin Osipov's avatar
Konstantin Osipov committed
905

906 907
  Here: "+" -- means that request can be satisfied
        "-" -- means that request can't be satisfied and should wait
Konstantin Osipov's avatar
Konstantin Osipov committed
908

909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924
  (*)   Since for upgradable locks we always take intention exclusive global
        lock at the same time when obtaining the shared lock, there is no
        need to obtain such lock during the upgrade itself.
  (**)  Since intention shared global locks are compatible with all other
        type of locks we don't even have any accounting for them.
*/

const MDL_lock::bitmap_t MDL_global_lock::m_granted_incompatible[MDL_TYPE_END] =
{
  MDL_BIT(MDL_SHARED), MDL_BIT(MDL_INTENTION_EXCLUSIVE), 0, 0, 0, 0, 0, 0
};

const MDL_lock::bitmap_t MDL_global_lock::m_waiting_incompatible[MDL_TYPE_END] =
{
  MDL_BIT(MDL_SHARED), 0, 0, 0, 0, 0, 0, 0
};
Konstantin Osipov's avatar
Konstantin Osipov committed
925 926


927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963
/**
  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.

  The first array specifies if particular type of request can be satisfied
  if there is granted lock of certain type.

     Request  |  Granted requests for lock   |
      type    | S  SH  SR  SW  SNW  SNRW  X  |
    ----------+------------------------------+
    S         | +   +   +   +   +    +    -  |
    SH        | +   +   +   +   +    +    -  |
    SR        | +   +   +   +   +    -    -  |
    SW        | +   +   +   +   -    -    -  |
    SNW       | +   +   +   -   -    -    -  |
    SNRW      | +   +   -   -   -    -    -  |
    X         | -   -   -   -   -    -    -  |
    SNW -> X  | -   -   -   0   0    0    0  |
    SNRW -> X | -   -   0   0   0    0    0  |

  The second array specifies if particular type of request can be satisfied
  if there is waiting request for the same lock of certain type. In other
  words it specifies what is the priority of different lock types.

     Request  |  Pending requests for lock  |
      type    | S  SH  SR  SW  SNW  SNRW  X |
    ----------+-----------------------------+
    S         | +   +   +   +   +     +   - |
    SH        | +   +   +   +   +     +   + |
    SR        | +   +   +   +   +     -   - |
    SW        | +   +   +   +   -     -   - |
    SNW       | +   +   +   +   +     +   - |
    SNRW      | +   +   +   +   +     +   - |
    X         | +   +   +   +   +     +   + |
    SNW -> X  | +   +   +   +   +     +   + |
    SNRW -> X | +   +   +   +   +     +   + |
Konstantin Osipov's avatar
Konstantin Osipov committed
964

Konstantin Osipov's avatar
Konstantin Osipov committed
965 966 967
  Here: "+" -- means that request can be satisfied
        "-" -- means that request can't be satisfied and should wait
        "0" -- means impossible situation which will trigger assert
Konstantin Osipov's avatar
Konstantin Osipov committed
968

969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022
  @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.
*/

const MDL_lock::bitmap_t
MDL_object_lock::m_granted_incompatible[MDL_TYPE_END] =
{
  0,
  MDL_BIT(MDL_EXCLUSIVE),
  MDL_BIT(MDL_EXCLUSIVE),
  MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_SHARED_NO_READ_WRITE),
  MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_SHARED_NO_READ_WRITE) |
    MDL_BIT(MDL_SHARED_NO_WRITE),
  MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_SHARED_NO_READ_WRITE) |
    MDL_BIT(MDL_SHARED_NO_WRITE) | MDL_BIT(MDL_SHARED_WRITE),
  MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_SHARED_NO_READ_WRITE) |
    MDL_BIT(MDL_SHARED_NO_WRITE) | MDL_BIT(MDL_SHARED_WRITE) |
    MDL_BIT(MDL_SHARED_READ),
  MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_SHARED_NO_READ_WRITE) |
    MDL_BIT(MDL_SHARED_NO_WRITE) | MDL_BIT(MDL_SHARED_WRITE) |
    MDL_BIT(MDL_SHARED_READ) | MDL_BIT(MDL_SHARED_HIGH_PRIO) |
    MDL_BIT(MDL_SHARED)
};


const MDL_lock::bitmap_t
MDL_object_lock::m_waiting_incompatible[MDL_TYPE_END] =
{
  0,
  MDL_BIT(MDL_EXCLUSIVE),
  0,
  MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_SHARED_NO_READ_WRITE),
  MDL_BIT(MDL_EXCLUSIVE) | MDL_BIT(MDL_SHARED_NO_READ_WRITE) |
    MDL_BIT(MDL_SHARED_NO_WRITE),
  MDL_BIT(MDL_EXCLUSIVE),
  MDL_BIT(MDL_EXCLUSIVE),
  0
};


/**
  Check if request for the metadata lock can be satisfied given its
  current state.

  @param  type_arg       The requested lock type.
  @param  requestor_ctx  The MDL context of the requestor.

  @retval TRUE   Lock request can be satisfied
  @retval FALSE  There is some conflicting lock.

  @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.
Konstantin Osipov's avatar
Konstantin Osipov committed
1023 1024
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
1025
bool
1026 1027
MDL_lock::can_grant_lock(enum_mdl_type type_arg,
                         MDL_context *requestor_ctx) const
Konstantin Osipov's avatar
Konstantin Osipov committed
1028
{
Konstantin Osipov's avatar
Konstantin Osipov committed
1029
  bool can_grant= FALSE;
1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041
  bitmap_t waiting_incompat_map= incompatible_waiting_types_bitmap()[type_arg];
  bitmap_t granted_incompat_map= incompatible_granted_types_bitmap()[type_arg];
  /*
    New lock request can be satisfied iff:
    - There are no incompatible types of satisfied requests
    in other contexts
    - There are no waiting requests which have higher priority
    than this request.
  */
  if (! (m_waiting.bitmap() & waiting_incompat_map))
  {
    if (! (m_granted.bitmap() & granted_incompat_map))
Konstantin Osipov's avatar
Konstantin Osipov committed
1042
      can_grant= TRUE;
1043
    else
Konstantin Osipov's avatar
Konstantin Osipov committed
1044
    {
1045 1046
      Ticket_iterator it(m_granted);
      MDL_ticket *ticket;
Konstantin Osipov's avatar
Konstantin Osipov committed
1047

1048 1049
      /* Check that the incompatible lock belongs to some other context. */
      while ((ticket= it++))
Konstantin Osipov's avatar
Konstantin Osipov committed
1050
      {
1051 1052
        if (ticket->get_ctx() != requestor_ctx &&
            ticket->is_incompatible_when_granted(type_arg))
Konstantin Osipov's avatar
Konstantin Osipov committed
1053
          break;
Konstantin Osipov's avatar
Konstantin Osipov committed
1054
      }
1055
      if (ticket == NULL)             /* Incompatible locks are our own. */
Konstantin Osipov's avatar
Konstantin Osipov committed
1056
        can_grant= TRUE;
Konstantin Osipov's avatar
Konstantin Osipov committed
1057 1058
    }
  }
Konstantin Osipov's avatar
Konstantin Osipov committed
1059 1060 1061 1062
  return can_grant;
}


1063
/** Remove a ticket from waiting or pending queue and wakeup up waiters. */
1064

1065
void MDL_lock::remove_ticket(Ticket_list MDL_lock::*list, MDL_ticket *ticket)
1066
{
1067 1068 1069 1070 1071
  rw_wrlock(&m_rwlock);
  (this->*list).remove_ticket(ticket);
  if (is_empty())
    mdl_locks.remove(this);
  else
1072
  {
1073 1074 1075 1076 1077 1078
    /*
      There can be some contexts waiting to acquire a lock
      which now might be able to do it. Wake them up!
    */
    wake_up_waiters();
    rw_unlock(&m_rwlock);
1079
  }
1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150
}


/**
  Check if we have any pending locks which conflict with existing
  shared lock.

  @pre The ticket must match an acquired lock.

  @return TRUE if there is a conflicting lock request, FALSE otherwise.
*/

bool MDL_lock::has_pending_conflicting_lock(enum_mdl_type type)
{
  bool result;

  safe_mutex_assert_not_owner(&LOCK_open);

  rw_rdlock(&m_rwlock);
  result= (m_waiting.bitmap() & incompatible_granted_types_bitmap()[type]);
  rw_unlock(&m_rwlock);
  return result;
}


/**
  Check if ticket represents metadata lock of "stronger" or equal type
  than specified one. I.e. if metadata lock represented by ticket won't
  allow any of locks which are not allowed by specified type of lock.

  @return TRUE  if ticket has stronger or equal type
          FALSE otherwise.
*/

bool MDL_ticket::has_stronger_or_equal_type(enum_mdl_type type) const
{
  const MDL_lock::bitmap_t *
    granted_incompat_map= m_lock->incompatible_granted_types_bitmap();

  return ! (granted_incompat_map[type] & ~(granted_incompat_map[m_type]));
}


bool MDL_ticket::is_incompatible_when_granted(enum_mdl_type type) const
{
  return (MDL_BIT(m_type) &
          m_lock->incompatible_granted_types_bitmap()[type]);
}


bool MDL_ticket::is_incompatible_when_waiting(enum_mdl_type type) const
{
  return (MDL_BIT(m_type) &
          m_lock->incompatible_waiting_types_bitmap()[type]);
}


/**
  Acquire global intention exclusive lock.

  @param[in]  mdl_request  Lock request object for lock to be acquired

  @retval  FALSE   Success. The lock has been acquired.
  @retval  TRUE    Error.
*/

bool
MDL_context::acquire_global_intention_exclusive_lock(MDL_request *mdl_request)
{
  DBUG_ASSERT(mdl_request->key.mdl_namespace() == MDL_key::GLOBAL &&
              mdl_request->type == MDL_INTENTION_EXCLUSIVE);
1151 1152

  /*
1153 1154 1155 1156 1157
    If this is a non-recursive attempt to acquire global intention
    exclusive lock we might have to wait until active global shared
    lock or pending requests will go away. Since we won't hold any
    resources (except associated with open HANDLERs) while doing it
    deadlocks are not possible.
1158
  */
1159 1160 1161 1162 1163
  DBUG_ASSERT(is_lock_owner(MDL_key::GLOBAL, "", "", MDL_INTENTION_EXCLUSIVE) ||
              ! has_locks() ||
              (m_trans_sentinel && m_tickets.front() == m_trans_sentinel));

  return acquire_lock(mdl_request);
1164 1165 1166
}


Konstantin Osipov's avatar
Konstantin Osipov committed
1167
/**
Konstantin Osipov's avatar
Konstantin Osipov committed
1168
  Check whether the context already holds a compatible lock ticket
Konstantin Osipov's avatar
Konstantin Osipov committed
1169
  on an object.
1170 1171 1172
  Start searching the transactional locks. If not
  found in the list of transactional locks, look at LOCK TABLES
  and HANDLER locks.
Konstantin Osipov's avatar
Konstantin Osipov committed
1173

Konstantin Osipov's avatar
Konstantin Osipov committed
1174
  @param mdl_request  Lock request object for lock to be acquired
1175 1176 1177 1178 1179
  @param[out] is_transactional FALSE if we pass beyond m_trans_sentinel
                      while searching for ticket, otherwise TRUE.

  @note Tickets which correspond to lock types "stronger" than one
        being requested are also considered compatible.
Konstantin Osipov's avatar
Konstantin Osipov committed
1180

Konstantin Osipov's avatar
Konstantin Osipov committed
1181
  @return A pointer to the lock ticket for the object or NULL otherwise.
Konstantin Osipov's avatar
Konstantin Osipov committed
1182 1183
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
1184
MDL_ticket *
1185
MDL_context::find_ticket(MDL_request *mdl_request,
1186
                         bool *is_transactional)
Konstantin Osipov's avatar
Konstantin Osipov committed
1187
{
Konstantin Osipov's avatar
Konstantin Osipov committed
1188 1189
  MDL_ticket *ticket;
  Ticket_iterator it(m_tickets);
Konstantin Osipov's avatar
Konstantin Osipov committed
1190

1191
  *is_transactional= TRUE;
1192

Konstantin Osipov's avatar
Konstantin Osipov committed
1193 1194
  while ((ticket= it++))
  {
1195 1196
    if (ticket == m_trans_sentinel)
      *is_transactional= FALSE;
1197

1198 1199
    if (mdl_request->key.is_equal(&ticket->m_lock->key) &&
        ticket->has_stronger_or_equal_type(mdl_request->type))
Konstantin Osipov's avatar
Konstantin Osipov committed
1200 1201 1202 1203
      break;
  }

  return ticket;
Konstantin Osipov's avatar
Konstantin Osipov committed
1204 1205 1206
}


1207
/**
1208
  Acquire one lock with waiting for conflicting locks to go away if needed.
1209

1210 1211 1212
  @note This is an internal method which should not be used outside of MDL
        subsystem as in most cases simply waiting for conflicting locks to
        go away will lead to deadlock.
1213 1214 1215 1216 1217 1218 1219 1220 1221

  @param mdl_request [in/out] Lock request object for lock to be acquired

  @retval  FALSE   Success. MDL_request::ticket points to the ticket
                   for the lock.
  @retval  TRUE    Failure (Out of resources or waiting is aborted),
*/

bool
1222
MDL_context::acquire_lock(MDL_request *mdl_request)
1223
{
1224
  return acquire_lock_impl(mdl_request);
1225 1226 1227 1228
}


/**
1229
  Try to acquire one lock.
1230

1231 1232 1233 1234 1235
  Unlike exclusive locks, shared locks are acquired one by
  one. This is interface is chosen to simplify introduction of
  the new locking API to the system. MDL_context::try_acquire_lock()
  is currently used from open_table(), and there we have only one
  table to work with.
1236

1237 1238
  This function may also be used to try to acquire an exclusive
  lock on a destination table, by ALTER TABLE ... RENAME.
1239

1240 1241
  Returns immediately without any side effect if encounters a lock
  conflict. Otherwise takes the lock.
1242

1243 1244
  FIXME: Compared to lock_table_name_if_not_cached() (from 5.1)
         it gives slightly more false negatives.
1245

Konstantin Osipov's avatar
Konstantin Osipov committed
1246
  @param mdl_request [in/out] Lock request object for lock to be acquired
1247

Konstantin Osipov's avatar
Konstantin Osipov committed
1248 1249
  @retval  FALSE   Success. The lock may have not been acquired.
                   Check the ticket, if it's NULL, a conflicting lock
1250 1251 1252
                   exists and another attempt should be made after releasing
                   all current locks and waiting for conflicting lock go
                   away (using MDL_context::wait_for_lock()).
Konstantin Osipov's avatar
Konstantin Osipov committed
1253
  @retval  TRUE    Out of resources, an error has been reported.
1254 1255
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
1256
bool
1257
MDL_context::try_acquire_lock(MDL_request *mdl_request)
1258
{
Konstantin Osipov's avatar
Konstantin Osipov committed
1259 1260 1261
  MDL_lock *lock;
  MDL_key *key= &mdl_request->key;
  MDL_ticket *ticket;
1262
  bool is_transactional;
1263

1264 1265 1266
  DBUG_ASSERT(mdl_request->type < MDL_SHARED_NO_WRITE ||
              (is_lock_owner(MDL_key::GLOBAL, "", "",
                             MDL_INTENTION_EXCLUSIVE)));
1267
  DBUG_ASSERT(mdl_request->ticket == NULL);
Konstantin Osipov's avatar
Konstantin Osipov committed
1268

Konstantin Osipov's avatar
Konstantin Osipov committed
1269 1270
  /* Don't take chances in production. */
  mdl_request->ticket= NULL;
1271 1272
  safe_mutex_assert_not_owner(&LOCK_open);

Konstantin Osipov's avatar
Konstantin Osipov committed
1273 1274 1275 1276
  /*
    Check whether the context already holds a shared lock on the object,
    and if so, grant the request.
  */
1277
  if ((ticket= find_ticket(mdl_request, &is_transactional)))
Konstantin Osipov's avatar
Konstantin Osipov committed
1278
  {
1279 1280
    DBUG_ASSERT(ticket->m_lock);
    DBUG_ASSERT(ticket->m_type >= mdl_request->type);
1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297
    /*
      If the request is for a transactional lock, and we found
      a transactional lock, just reuse the found ticket.

      It's possible that we found a transactional lock,
      but the request is for a HANDLER lock. In that case HANDLER
      code will clone the ticket (see below why it's needed).

      If the request is for a transactional lock, and we found
      a HANDLER lock, create a copy, to make sure that when user
      does HANDLER CLOSE, the transactional lock is not released.

      If the request is for a handler lock, and we found a
      HANDLER lock, also do the clone. HANDLER CLOSE for one alias
      should not release the lock on the table HANDLER opened through
      a different alias.
    */
Konstantin Osipov's avatar
Konstantin Osipov committed
1298
    mdl_request->ticket= ticket;
1299
    if (!is_transactional && clone_ticket(mdl_request))
1300 1301 1302 1303 1304
    {
      /* Clone failed. */
      mdl_request->ticket= NULL;
      return TRUE;
    }
Konstantin Osipov's avatar
Konstantin Osipov committed
1305 1306 1307
    return FALSE;
  }

Konstantin Osipov's avatar
Konstantin Osipov committed
1308
  if (!(ticket= MDL_ticket::create(this, mdl_request->type)))
Konstantin Osipov's avatar
Konstantin Osipov committed
1309 1310
    return TRUE;

1311
  /* The below call implicitly locks MDL_lock::m_rwlock on success. */
1312
  if (!(lock= mdl_locks.find_or_insert(key)))
Konstantin Osipov's avatar
Konstantin Osipov committed
1313
  {
1314 1315
    MDL_ticket::destroy(ticket);
    return TRUE;
Konstantin Osipov's avatar
Konstantin Osipov committed
1316 1317
  }

1318
  if (lock->can_grant_lock(mdl_request->type, this))
Konstantin Osipov's avatar
Konstantin Osipov committed
1319
  {
1320 1321
    lock->m_granted.add_ticket(ticket);
    rw_unlock(&lock->m_rwlock);
1322

Konstantin Osipov's avatar
Konstantin Osipov committed
1323
    ticket->m_lock= lock;
1324 1325 1326 1327

    m_tickets.push_front(ticket);

    mdl_request->ticket= ticket;
1328 1329 1330
  }
  else
  {
Konstantin Osipov's avatar
Konstantin Osipov committed
1331 1332
    /* We can't get here if we allocated a new lock. */
    DBUG_ASSERT(! lock->is_empty());
1333
    rw_unlock(&lock->m_rwlock);
Konstantin Osipov's avatar
Konstantin Osipov committed
1334
    MDL_ticket::destroy(ticket);
1335 1336
  }

Konstantin Osipov's avatar
Konstantin Osipov committed
1337
  return FALSE;
1338 1339 1340
}


1341
/**
1342
  Create a copy of a granted ticket.
1343 1344
  This is used to make sure that HANDLER ticket
  is never shared with a ticket that belongs to
1345
  a transaction, so that when we HANDLER CLOSE,
1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359
  we don't release a transactional ticket, and
  vice versa -- when we COMMIT, we don't mistakenly
  release a ticket for an open HANDLER.

  @retval TRUE   Out of memory.
  @retval FALSE  Success.
*/

bool
MDL_context::clone_ticket(MDL_request *mdl_request)
{
  MDL_ticket *ticket;

  safe_mutex_assert_not_owner(&LOCK_open);
1360 1361 1362 1363 1364
  /*
    By submitting mdl_request->type to MDL_ticket::create()
    we effectively downgrade the cloned lock to the level of
    the request.
  */
1365 1366 1367
  if (!(ticket= MDL_ticket::create(this, mdl_request->type)))
    return TRUE;

1368 1369 1370
  /* clone() is not supposed to be used to get a stronger lock. */
  DBUG_ASSERT(ticket->m_type <= mdl_request->ticket->m_type);

1371 1372 1373
  ticket->m_lock= mdl_request->ticket->m_lock;
  mdl_request->ticket= ticket;

1374 1375 1376
  rw_wrlock(&ticket->m_lock->m_rwlock);
  ticket->m_lock->m_granted.add_ticket(ticket);
  rw_unlock(&ticket->m_lock->m_rwlock);
1377 1378 1379 1380 1381 1382

  m_tickets.push_front(ticket);

  return FALSE;
}

1383

1384 1385 1386 1387 1388 1389 1390 1391 1392 1393
/**
  Notify a thread holding a shared metadata lock which
  conflicts with a pending exclusive lock.

  @param thd               Current thread context
  @param conflicting_ticket  Conflicting metadata lock
*/

void notify_shared_lock(THD *thd, MDL_ticket *conflicting_ticket)
{
1394 1395
  /* Only try to abort locks on which we back off. */
  if (conflicting_ticket->get_type() < MDL_SHARED_NO_WRITE)
1396
  {
1397 1398
    MDL_context *conflicting_ctx= conflicting_ticket->get_ctx();
    THD *conflicting_thd= conflicting_ctx->get_thd();
1399 1400 1401
    DBUG_ASSERT(thd != conflicting_thd); /* Self-deadlock */

    /*
1402 1403 1404
      If thread which holds conflicting lock is waiting on table-level
      lock or some other non-MDL resource we might need to wake it up
      by calling code outside of MDL.
1405
    */
1406 1407
    mysql_notify_thread_having_shared_lock(thd, conflicting_thd,
                               conflicting_ctx->get_needs_thr_lock_abort());
1408 1409 1410 1411 1412 1413 1414 1415 1416
  }
}


/**
  Auxiliary method for acquiring an exclusive lock.

  @param mdl_request  Request for the lock to be acqured.

1417 1418 1419 1420
  @note Should not be used outside of MDL subsystem. Instead one
        should call acquire_lock() or acquire_locks()
        methods which ensure that conditions for deadlock-free
        lock acquisition are fulfilled.
1421 1422 1423 1424 1425

  @retval FALSE  Success
  @retval TRUE   Failure
*/

1426
bool MDL_context::acquire_lock_impl(MDL_request *mdl_request)
1427 1428 1429 1430 1431 1432 1433 1434 1435
{
  MDL_lock *lock;
  MDL_ticket *ticket;
  bool not_used;
  st_my_thread_var *mysys_var= my_thread_var;
  MDL_key *key= &mdl_request->key;

  safe_mutex_assert_not_owner(&LOCK_open);

1436
  DBUG_ASSERT(mdl_request->ticket == NULL);
1437 1438 1439 1440 1441 1442 1443 1444 1445
  /* Don't take chances in production. */
  mdl_request->ticket= NULL;

  /*
    Check whether the context already holds an exclusive lock on the object,
    and if so, grant the request.
  */
  if ((ticket= find_ticket(mdl_request, &not_used)))
  {
1446
    DBUG_ASSERT(ticket->m_lock);
1447 1448 1449 1450
    mdl_request->ticket= ticket;
    return FALSE;
  }

1451 1452
  DBUG_ASSERT(mdl_request->type < MDL_SHARED_NO_WRITE ||
              is_lock_owner(MDL_key::GLOBAL, "", "", MDL_INTENTION_EXCLUSIVE));
1453 1454 1455 1456 1457

  /* Early allocation: ticket will be needed in any case. */
  if (!(ticket= MDL_ticket::create(this, mdl_request->type)))
    return TRUE;

1458
  /* The below call implicitly locks MDL_lock::m_rwlock on success. */
1459 1460 1461 1462 1463 1464
  if (!(lock= mdl_locks.find_or_insert(key)))
  {
    MDL_ticket::destroy(ticket);
    return TRUE;
  }

1465
  ticket->m_lock= lock;
1466

1467
  lock->m_waiting.add_ticket(ticket);
1468

1469
  while (!lock->can_grant_lock(mdl_request->type, this))
1470
  {
1471
    wait_reset();
1472

1473 1474
    if (ticket->is_upgradable_or_exclusive())
      lock->notify_shared_locks(this);
1475

1476
    rw_unlock(&lock->m_rwlock);
1477

1478 1479
    set_deadlock_weight(mdl_request->get_deadlock_weight());
    will_wait_for(ticket);
1480 1481

    /* There is a shared or exclusive lock on the object. */
1482
    DEBUG_SYNC(m_thd, "mdl_acquire_lock_wait");
1483

1484
    bool is_deadlock= (find_deadlock() || timed_wait(1) == VICTIM_WAKE_UP);
1485

1486
    stop_waiting();
1487

1488 1489 1490
    if (is_deadlock || mysys_var->abort)
    {
      lock->remove_ticket(&MDL_lock::m_waiting, ticket);
1491
      MDL_ticket::destroy(ticket);
1492 1493
      if (is_deadlock)
        my_error(ER_LOCK_DEADLOCK, MYF(0));
1494 1495
      return TRUE;
    }
1496
    rw_wrlock(&lock->m_rwlock);
1497 1498
  }

1499 1500
  lock->m_waiting.remove_ticket(ticket);
  lock->m_granted.add_ticket(ticket);
1501

1502
  if (ticket->get_type() == MDL_EXCLUSIVE && lock->cached_object)
1503 1504 1505
    (*lock->cached_object_release_hook)(lock->cached_object);
  lock->cached_object= NULL;

1506
  rw_unlock(&lock->m_rwlock);
1507 1508 1509

  m_tickets.push_front(ticket);

1510 1511
  mdl_request->ticket= ticket;

1512 1513 1514
  return FALSE;
}

1515 1516

extern "C" int mdl_request_ptr_cmp(const void* ptr1, const void* ptr2)
Konstantin Osipov's avatar
Konstantin Osipov committed
1517
{
1518 1519 1520
  MDL_request *req1= *(MDL_request**)ptr1;
  MDL_request *req2= *(MDL_request**)ptr2;
  return req1->key.cmp(&req2->key);
Konstantin Osipov's avatar
Konstantin Osipov committed
1521 1522 1523
}


1524
/**
1525
  Acquire exclusive locks. There must be no granted locks in the
Konstantin Osipov's avatar
Konstantin Osipov committed
1526
  context.
1527

Konstantin Osipov's avatar
Konstantin Osipov committed
1528 1529
  This is a replacement of lock_table_names(). It is used in
  RENAME, DROP and other DDL SQL statements.
1530

1531 1532 1533 1534 1535 1536
  @param  mdl_requests  List of requests for locks to be acquired.

  @note The list of requests should not contain non-exclusive lock requests.
        There should not be any acquired locks in the context.

  @note Assumes that one already owns global intention exclusive lock.
1537

Konstantin Osipov's avatar
Konstantin Osipov committed
1538 1539
  @retval FALSE  Success
  @retval TRUE   Failure
1540 1541
*/

1542
bool MDL_context::acquire_locks(MDL_request_list *mdl_requests)
1543
{
Konstantin Osipov's avatar
Konstantin Osipov committed
1544
  MDL_request_list::Iterator it(*mdl_requests);
1545
  MDL_request **sort_buf, **p_req;
1546
  ssize_t req_count= static_cast<ssize_t>(mdl_requests->elements());
1547 1548 1549

  if (req_count == 0)
    return FALSE;
1550

1551
  /*
1552 1553 1554
    To reduce deadlocks, the server acquires all exclusive
    locks at once. For shared locks, try_acquire_lock() is
    used instead.
1555
  */
1556
  DBUG_ASSERT(m_tickets.is_empty() || m_tickets.front() == m_trans_sentinel);
Konstantin Osipov's avatar
Konstantin Osipov committed
1557

1558
  /* Sort requests according to MDL_key. */
1559 1560
  if (! (sort_buf= (MDL_request **)my_malloc(req_count *
                                             sizeof(MDL_request*),
1561 1562
                                             MYF(MY_WME))))
    return TRUE;
Konstantin Osipov's avatar
Konstantin Osipov committed
1563

1564 1565
  for (p_req= sort_buf; p_req < sort_buf + req_count; p_req++)
    *p_req= it++;
Konstantin Osipov's avatar
Konstantin Osipov committed
1566

1567
  my_qsort(sort_buf, req_count, sizeof(MDL_request*),
1568
           mdl_request_ptr_cmp);
1569

1570
  for (p_req= sort_buf; p_req < sort_buf + req_count; p_req++)
1571
  {
1572
    if (acquire_lock_impl(*p_req))
Konstantin Osipov's avatar
Konstantin Osipov committed
1573
      goto err;
1574
  }
1575
  my_free(sort_buf, MYF(0));
Konstantin Osipov's avatar
Konstantin Osipov committed
1576
  return FALSE;
Konstantin Osipov's avatar
Konstantin Osipov committed
1577 1578

err:
1579
  /* Release locks we have managed to acquire so far. */
1580 1581
  for (req_count= p_req - sort_buf, p_req= sort_buf;
       p_req < sort_buf + req_count; p_req++)
Konstantin Osipov's avatar
Konstantin Osipov committed
1582
  {
1583
    release_lock((*p_req)->ticket);
Konstantin Osipov's avatar
Konstantin Osipov committed
1584
    /* Reset lock request back to its initial state. */
1585
    (*p_req)->ticket= NULL;
Konstantin Osipov's avatar
Konstantin Osipov committed
1586
  }
1587
  my_free(sort_buf, MYF(0));
Konstantin Osipov's avatar
Konstantin Osipov committed
1588
  return TRUE;
1589 1590 1591 1592
}


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
1593
  Upgrade a shared metadata lock to exclusive.
1594

Konstantin Osipov's avatar
Konstantin Osipov committed
1595 1596
  Used in ALTER TABLE, when a copy of the table with the
  new definition has been constructed.
1597

Konstantin Osipov's avatar
Konstantin Osipov committed
1598 1599 1600
  @note In case of failure to upgrade lock (e.g. because upgrader
        was killed) leaves lock in its original state (locked in
        shared mode).
1601

Konstantin Osipov's avatar
Konstantin Osipov committed
1602 1603 1604 1605
  @note There can be only one upgrader for a lock or we will have deadlock.
        This invariant is ensured by code outside of metadata subsystem usually
        by obtaining some sort of exclusive table-level lock (e.g. TL_WRITE,
        TL_WRITE_ALLOW_READ) before performing upgrade of metadata lock.
Konstantin Osipov's avatar
Konstantin Osipov committed
1606

Konstantin Osipov's avatar
Konstantin Osipov committed
1607 1608
  @retval FALSE  Success
  @retval TRUE   Failure (thread was killed)
1609 1610
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
1611
bool
1612
MDL_context::upgrade_shared_lock_to_exclusive(MDL_ticket *mdl_ticket)
1613
{
1614 1615 1616
  MDL_request mdl_xlock_request;
  MDL_ticket *mdl_svp= mdl_savepoint();
  bool is_new_ticket;
1617

Konstantin Osipov's avatar
Konstantin Osipov committed
1618
  DBUG_ENTER("MDL_ticket::upgrade_shared_lock_to_exclusive");
1619
  DEBUG_SYNC(get_thd(), "mdl_upgrade_shared_lock_to_exclusive");
1620

1621 1622 1623 1624 1625
  /*
    Do nothing if already upgraded. Used when we FLUSH TABLE under
    LOCK TABLES and a table is listed twice in LOCK TABLES list.
  */
  if (mdl_ticket->m_type == MDL_EXCLUSIVE)
Konstantin Osipov's avatar
Konstantin Osipov committed
1626 1627
    DBUG_RETURN(FALSE);

1628 1629 1630
  /* Only allow upgrades from MDL_SHARED_NO_WRITE/NO_READ_WRITE */
  DBUG_ASSERT(mdl_ticket->m_type == MDL_SHARED_NO_WRITE ||
              mdl_ticket->m_type == MDL_SHARED_NO_READ_WRITE);
1631

1632
  mdl_xlock_request.init(&mdl_ticket->m_lock->key, MDL_EXCLUSIVE);
1633

1634
  if (acquire_lock_impl(&mdl_xlock_request))
1635 1636
    DBUG_RETURN(TRUE);

1637
  is_new_ticket= ! has_lock(mdl_svp, mdl_xlock_request.ticket);
1638

1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650
  /* Merge the acquired and the original lock. @todo: move to a method. */
  rw_wrlock(&mdl_ticket->m_lock->m_rwlock);
  if (is_new_ticket)
    mdl_ticket->m_lock->m_granted.remove_ticket(mdl_xlock_request.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_ticket->m_lock->m_granted.remove_ticket(mdl_ticket);
  mdl_ticket->m_type= MDL_EXCLUSIVE;
  mdl_ticket->m_lock->m_granted.add_ticket(mdl_ticket);
1651

1652
  rw_unlock(&mdl_ticket->m_lock->m_rwlock);
1653

1654
  if (is_new_ticket)
1655
  {
1656 1657 1658
    m_tickets.remove(mdl_xlock_request.ticket);
    MDL_ticket::destroy(mdl_xlock_request.ticket);
  }
Konstantin Osipov's avatar
Konstantin Osipov committed
1659

1660 1661
  DBUG_RETURN(FALSE);
}
1662

1663

1664 1665 1666 1667 1668
bool MDL_lock::find_deadlock(MDL_ticket *waiting_ticket,
                             Deadlock_detection_context *deadlock_ctx)
{
  MDL_ticket *ticket;
  bool result= FALSE;
Konstantin Osipov's avatar
Konstantin Osipov committed
1669

1670
  rw_rdlock(&m_rwlock);
1671

1672 1673
  Ticket_iterator granted_it(m_granted);
  Ticket_iterator waiting_it(m_waiting);
1674

1675 1676 1677 1678 1679
  while ((ticket= granted_it++))
  {
    if (ticket->is_incompatible_when_granted(waiting_ticket->get_type()) &&
        ticket->get_ctx() != waiting_ticket->get_ctx() &&
        ticket->get_ctx() == deadlock_ctx->start)
1680
    {
1681 1682
      result= TRUE;
      goto end;
1683 1684 1685
    }
  }

1686 1687 1688 1689 1690 1691 1692 1693 1694 1695
  while ((ticket= waiting_it++))
  {
    if (ticket->is_incompatible_when_waiting(waiting_ticket->get_type()) &&
        ticket->get_ctx() != waiting_ticket->get_ctx() &&
        ticket->get_ctx() == deadlock_ctx->start)
    {
      result= TRUE;
      goto end;
    }
  }
1696

1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707
  granted_it.rewind();
  while ((ticket= granted_it++))
  {
    if (ticket->is_incompatible_when_granted(waiting_ticket->get_type()) &&
        ticket->get_ctx() != waiting_ticket->get_ctx() &&
        ticket->get_ctx()->find_deadlock(deadlock_ctx))
    {
      result= TRUE;
      goto end;
    }
  }
1708

1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719
  waiting_it.rewind();
  while ((ticket= waiting_it++))
  {
    if (ticket->is_incompatible_when_waiting(waiting_ticket->get_type()) &&
        ticket->get_ctx() != waiting_ticket->get_ctx() &&
        ticket->get_ctx()->find_deadlock(deadlock_ctx))
    {
      result= TRUE;
      goto end;
    }
  }
1720

1721 1722 1723
end:
  rw_unlock(&m_rwlock);
  return result;
1724 1725 1726
}


1727
bool MDL_context::find_deadlock(Deadlock_detection_context *deadlock_ctx)
1728
{
1729
  bool result= FALSE;
1730

1731
  rw_rdlock(&m_waiting_for_lock);
1732

1733 1734 1735 1736
  if (m_waiting_for)
  {
    /*
      QQ: should we rather be checking for NO_WAKE_UP ?
1737

1738 1739 1740 1741 1742
      We want to do check signal only when m_waiting_for is set
      to avoid reading left-overs from previous kills.
    */
    if (peek_signal() != VICTIM_WAKE_UP)
    {
1743

1744 1745 1746 1747 1748 1749 1750 1751 1752
      if (++deadlock_ctx->current_search_depth >
          deadlock_ctx->MAX_SEARCH_DEPTH)
        result= TRUE;
      else
        result= m_waiting_for->m_lock->find_deadlock(m_waiting_for,
                                                     deadlock_ctx);
      --deadlock_ctx->current_search_depth;
    }
  }
1753

1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767
  if (result)
  {
    if (! deadlock_ctx->victim)
      deadlock_ctx->victim= this;
    else if (deadlock_ctx->victim->m_deadlock_weight >= m_deadlock_weight)
    {
      rw_unlock(&deadlock_ctx->victim->m_waiting_for_lock);
      deadlock_ctx->victim= this;
    }
    else
      rw_unlock(&m_waiting_for_lock);
  }
  else
    rw_unlock(&m_waiting_for_lock);
1768

1769
  return result;
1770 1771 1772
}


1773
bool MDL_context::find_deadlock()
1774
{
1775
  Deadlock_detection_context deadlock_ctx(this);
1776

1777
  while (1)
1778
  {
1779 1780 1781 1782 1783
    if (! find_deadlock(&deadlock_ctx))
    {
      /* No deadlocks are found! */
      break;
    }
1784

1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801
    if (deadlock_ctx.victim != this)
    {
      deadlock_ctx.victim->awake(VICTIM_WAKE_UP);
      rw_unlock(&deadlock_ctx.victim->m_waiting_for_lock);
      /*
        After adding new arc to waiting graph we found that it participates
        in some loop (i.e. there is a deadlock). We decided to destroy this
        loop by removing some arc other than newly added. Since this doesn't
        guarantee that all loops created by addition of this arc are
        destroyed we have to repeat search.
      */
      continue;
    }
    else
    {
      DBUG_ASSERT(&deadlock_ctx.victim->m_waiting_for_lock == &m_waiting_for_lock);
      rw_unlock(&deadlock_ctx.victim->m_waiting_for_lock);
1802
      return TRUE;
1803
    }
1804 1805 1806 1807 1808
  }
  return FALSE;
}


1809
/**
Konstantin Osipov's avatar
Konstantin Osipov committed
1810
  Wait until there will be no locks that conflict with lock requests
Konstantin Osipov's avatar
Konstantin Osipov committed
1811
  in the given list.
1812

Konstantin Osipov's avatar
Konstantin Osipov committed
1813 1814
  This is a part of the locking protocol and must be used by the
  acquirer of shared locks after a back-off.
1815

Konstantin Osipov's avatar
Konstantin Osipov committed
1816
  Does not acquire the locks!
1817

Konstantin Osipov's avatar
Konstantin Osipov committed
1818
  @retval FALSE  Success. One can try to obtain metadata locks.
1819
  @retval TRUE   Failure (thread was killed or deadlock is possible).
1820 1821
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
1822
bool
1823
MDL_context::wait_for_lock(MDL_request *mdl_request)
1824
{
Konstantin Osipov's avatar
Konstantin Osipov committed
1825
  MDL_lock *lock;
Konstantin Osipov's avatar
Konstantin Osipov committed
1826
  st_my_thread_var *mysys_var= my_thread_var;
1827 1828 1829

  safe_mutex_assert_not_owner(&LOCK_open);

1830 1831
  DBUG_ASSERT(mdl_request->ticket == NULL);

Konstantin Osipov's avatar
Konstantin Osipov committed
1832
  while (!mysys_var->abort)
1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843
  {
    /*
      We have to check if there are some HANDLERs open by this thread
      which conflict with some pending exclusive locks. Otherwise we
      might have a deadlock in situations when we are waiting for
      pending writer to go away, which in its turn waits for HANDLER
      open by our thread.

      TODO: investigate situations in which we need to broadcast on
            COND_mdl because of above scenario.
    */
Konstantin Osipov's avatar
Konstantin Osipov committed
1844
    mysql_ha_flush(m_thd);
1845

1846 1847 1848 1849 1850 1851 1852
    MDL_key *key= &mdl_request->key;

    /* The below call implicitly locks MDL_lock::m_rwlock on success. */
    if (! (lock= mdl_locks.find(key)))
      return FALSE;

    if (lock->can_grant_lock(mdl_request->type, this))
1853
    {
1854 1855
      rw_unlock(&lock->m_rwlock);
      return FALSE;
1856 1857
    }

1858 1859
    MDL_ticket *pending_ticket;
    if (! (pending_ticket= MDL_ticket::create(this, mdl_request->type)))
1860
    {
1861 1862
      rw_unlock(&lock->m_rwlock);
      return TRUE;
1863
    }
1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881

    pending_ticket->m_lock= lock;

    lock->m_waiting.add_ticket(pending_ticket);

    wait_reset();
    rw_unlock(&lock->m_rwlock);

    set_deadlock_weight(MDL_DEADLOCK_WEIGHT_DML);
    will_wait_for(pending_ticket);

    bool is_deadlock= (find_deadlock() || wait() == VICTIM_WAKE_UP);

    stop_waiting();

    lock->remove_ticket(&MDL_lock::m_waiting, pending_ticket);
    MDL_ticket::destroy(pending_ticket);
    if (is_deadlock)
1882
    {
1883 1884
      my_error(ER_LOCK_DEADLOCK, MYF(0));
      return TRUE;
1885 1886
    }
  }
Konstantin Osipov's avatar
Konstantin Osipov committed
1887
  return mysys_var->abort;
1888 1889 1890 1891
}


/**
1892 1893 1894
  Release lock.

  @param ticket Ticket for lock to be released.
1895 1896
*/

1897
void MDL_context::release_lock(MDL_ticket *ticket)
1898
{
Konstantin Osipov's avatar
Konstantin Osipov committed
1899
  MDL_lock *lock= ticket->m_lock;
1900
  DBUG_ENTER("MDL_context::release_lock");
Konstantin Osipov's avatar
Konstantin Osipov committed
1901
  DBUG_PRINT("enter", ("db=%s name=%s", lock->key.db_name(),
Konstantin Osipov's avatar
Konstantin Osipov committed
1902
                                        lock->key.name()));
1903

1904
  DBUG_ASSERT(this == ticket->get_ctx());
1905
  safe_mutex_assert_not_owner(&LOCK_open);
Konstantin Osipov's avatar
Konstantin Osipov committed
1906

1907 1908
  if (ticket == m_trans_sentinel)
    m_trans_sentinel= ++Ticket_list::Iterator(m_tickets, ticket);
1909

1910
  lock->remove_ticket(&MDL_lock::m_granted, ticket);
1911

1912 1913 1914
  m_tickets.remove(ticket);
  MDL_ticket::destroy(ticket);

1915 1916 1917 1918 1919
  DBUG_VOID_RETURN;
}


/**
1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933
  Release all locks associated with the context. If the sentinel
  is not NULL, do not release locks stored in the list after and
  including the sentinel.

  Transactional locks are added to the beginning of the list, i.e.
  stored in reverse temporal order. This allows to employ this
  function to:
  - back off in case of a lock conflict.
  - release all locks in the end of a transaction
  - rollback to a savepoint.

  The sentinel semantics is used to support LOCK TABLES
  mode and HANDLER statements: locks taken by these statements
  survive COMMIT, ROLLBACK, ROLLBACK TO SAVEPOINT.
1934 1935
*/

1936
void MDL_context::release_locks_stored_before(MDL_ticket *sentinel)
1937
{
Konstantin Osipov's avatar
Konstantin Osipov committed
1938 1939
  MDL_ticket *ticket;
  Ticket_iterator it(m_tickets);
1940
  DBUG_ENTER("MDL_context::release_locks_stored_before");
1941

Konstantin Osipov's avatar
Konstantin Osipov committed
1942
  if (m_tickets.is_empty())
Konstantin Osipov's avatar
Konstantin Osipov committed
1943 1944
    DBUG_VOID_RETURN;

1945
  while ((ticket= it++) && ticket != sentinel)
1946
  {
Konstantin Osipov's avatar
Konstantin Osipov committed
1947
    DBUG_PRINT("info", ("found lock to release ticket=%p", ticket));
1948
    release_lock(ticket);
1949
  }
1950 1951 1952 1953 1954 1955
  /*
    If all locks were released, then the sentinel was not present
    in the list. It must never happen because the sentinel was
    bogus, i.e. pointed to a ticket that no longer exists.
  */
  DBUG_ASSERT(! m_tickets.is_empty() || sentinel == NULL);
Konstantin Osipov's avatar
Konstantin Osipov committed
1956

1957 1958 1959 1960 1961
  DBUG_VOID_RETURN;
}


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
1962
  Release all locks in the context which correspond to the same name/
Konstantin Osipov's avatar
Konstantin Osipov committed
1963
  object as this lock request.
Konstantin Osipov's avatar
Konstantin Osipov committed
1964

Konstantin Osipov's avatar
Konstantin Osipov committed
1965 1966
  @param ticket    One of the locks for the name/object for which all
                   locks should be released.
1967 1968
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
1969
void MDL_context::release_all_locks_for_name(MDL_ticket *name)
1970
{
1971
  /* Use MDL_ticket::m_lock to identify other locks for the same object. */
Konstantin Osipov's avatar
Konstantin Osipov committed
1972
  MDL_lock *lock= name->m_lock;
Konstantin Osipov's avatar
Konstantin Osipov committed
1973 1974

  /* Remove matching lock tickets from the context. */
Konstantin Osipov's avatar
Konstantin Osipov committed
1975 1976
  MDL_ticket *ticket;
  Ticket_iterator it_ticket(m_tickets);
Konstantin Osipov's avatar
Konstantin Osipov committed
1977

Konstantin Osipov's avatar
Konstantin Osipov committed
1978
  while ((ticket= it_ticket++))
Konstantin Osipov's avatar
Konstantin Osipov committed
1979
  {
1980
    DBUG_ASSERT(ticket->m_lock);
Konstantin Osipov's avatar
Konstantin Osipov committed
1981 1982 1983 1984 1985 1986
    /*
      We rarely have more than one ticket in this loop,
      let's not bother saving on pthread_cond_broadcast().
    */
    if (ticket->m_lock == lock)
      release_lock(ticket);
Konstantin Osipov's avatar
Konstantin Osipov committed
1987 1988 1989 1990 1991
  }
}


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
1992
  Downgrade an exclusive lock to shared metadata lock.
Konstantin Osipov's avatar
Konstantin Osipov committed
1993

1994
  @param type  Type of lock to which exclusive lock should be downgraded.
1995 1996
*/

1997
void MDL_ticket::downgrade_exclusive_lock(enum_mdl_type type)
1998 1999 2000
{
  safe_mutex_assert_not_owner(&LOCK_open);

2001
  /*
2002 2003
    Do nothing if already downgraded. Used when we FLUSH TABLE under
    LOCK TABLES and a table is listed twice in LOCK TABLES list.
2004
  */
2005 2006
  if (m_type != MDL_EXCLUSIVE)
    return;
2007

2008 2009 2010 2011 2012 2013 2014 2015 2016 2017
  rw_wrlock(&m_lock->m_rwlock);
  /*
    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->m_granted.remove_ticket(this);
  m_type= type;
  m_lock->m_granted.add_ticket(this);
  m_lock->wake_up_waiters();
  rw_unlock(&m_lock->m_rwlock);
2018 2019 2020 2021
}


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
2022
  Auxiliary function which allows to check if we have some kind of lock on
2023
  a object. Returns TRUE if we have a lock of a given or stronger type.
2024

2025 2026 2027
  @param mdl_namespace Id of object namespace
  @param db            Name of the database
  @param name          Name of the object
2028 2029
  @param mdl_type      Lock type. Pass in the weakest type to find
                       out if there is at least some lock.
2030

Konstantin Osipov's avatar
Konstantin Osipov committed
2031 2032
  @return TRUE if current context contains satisfied lock for the object,
          FALSE otherwise.
2033 2034
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
2035
bool
Konstantin Osipov's avatar
Konstantin Osipov committed
2036
MDL_context::is_lock_owner(MDL_key::enum_mdl_namespace mdl_namespace,
2037 2038
                           const char *db, const char *name,
                           enum_mdl_type mdl_type)
2039
{
2040 2041 2042 2043
  MDL_request mdl_request;
  bool is_transactional_unused;
  mdl_request.init(mdl_namespace, db, name, mdl_type);
  MDL_ticket *ticket= find_ticket(&mdl_request, &is_transactional_unused);
2044

2045
  DBUG_ASSERT(ticket == NULL || ticket->m_lock);
2046

Konstantin Osipov's avatar
Konstantin Osipov committed
2047
  return ticket;
2048 2049 2050 2051
}


/**
2052
  Check if we have any pending locks which conflict with existing shared lock.
2053

Konstantin Osipov's avatar
Konstantin Osipov committed
2054 2055
  @pre The ticket must match an acquired lock.

2056 2057
  @return TRUE if there is a conflicting lock request, FALSE otherwise.
*/
2058

Konstantin Osipov's avatar
Konstantin Osipov committed
2059
bool MDL_ticket::has_pending_conflicting_lock() const
2060
{
2061
  return m_lock->has_pending_conflicting_lock(m_type);
2062 2063 2064 2065
}


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088
  Associate pointer to an opaque object with a lock.

  @param cached_object Pointer to the object
  @param release_hook  Cleanup function to be called when MDL subsystem
                       decides to remove lock or associate another object.

  This is used to cache a pointer to TABLE_SHARE in the lock
  structure. Such caching can save one acquisition of LOCK_open
  and one table definition cache lookup for every table.

  Since the pointer may be stored only inside an acquired lock,
  the caching is only effective when there is more than one lock
  granted on a given table.

  This function has the following usage pattern:
    - try to acquire an MDL lock
    - when done, call for mdl_get_cached_object(). If it returns NULL, our
      thread has the only lock on this table.
    - look up TABLE_SHARE in the table definition cache
    - call mdl_set_cache_object() to assign the share to the opaque pointer.

 The release hook is invoked when the last shared metadata
 lock on this name is released.
2089 2090
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
2091 2092 2093
void
MDL_ticket::set_cached_object(void *cached_object,
                              mdl_cached_object_release_hook release_hook)
2094 2095
{
  DBUG_ENTER("mdl_set_cached_object");
Konstantin Osipov's avatar
Konstantin Osipov committed
2096
  DBUG_PRINT("enter", ("db=%s name=%s cached_object=%p",
Konstantin Osipov's avatar
Konstantin Osipov committed
2097
                        m_lock->key.db_name(), m_lock->key.name(),
Konstantin Osipov's avatar
Konstantin Osipov committed
2098
                        cached_object));
2099
  /*
Konstantin Osipov's avatar
Konstantin Osipov committed
2100 2101
    TODO: This assumption works now since we do get_cached_object()
          and set_cached_object() in the same critical section. Once
2102 2103 2104
          this becomes false we will have to call release_hook here and
          use additional mutex protecting 'cached_object' member.
  */
Konstantin Osipov's avatar
Konstantin Osipov committed
2105
  DBUG_ASSERT(!m_lock->cached_object);
2106

Konstantin Osipov's avatar
Konstantin Osipov committed
2107 2108
  m_lock->cached_object= cached_object;
  m_lock->cached_object_release_hook= release_hook;
2109 2110 2111 2112 2113 2114

  DBUG_VOID_RETURN;
}


/**
Konstantin Osipov's avatar
Konstantin Osipov committed
2115
  Get a pointer to an opaque object that associated with the lock.
2116

Konstantin Osipov's avatar
Konstantin Osipov committed
2117
  @param ticket  Lock ticket for the lock which the object is associated to.
2118

Konstantin Osipov's avatar
Konstantin Osipov committed
2119
  @return Pointer to an opaque object associated with the lock.
2120 2121
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
2122
void *MDL_ticket::get_cached_object()
2123
{
Konstantin Osipov's avatar
Konstantin Osipov committed
2124
  return m_lock->cached_object;
2125
}
Konstantin Osipov's avatar
Konstantin Osipov committed
2126 2127 2128 2129 2130 2131 2132 2133 2134 2135


/**
  Releases metadata locks that were acquired after a specific savepoint.

  @note Used to release tickets acquired during a savepoint unit.
  @note It's safe to iterate and unlock any locks after taken after this
        savepoint because other statements that take other special locks
        cause a implicit commit (ie LOCK TABLES).

Konstantin Osipov's avatar
Konstantin Osipov committed
2136 2137
  @param mdl_savepont  The last acquired MDL lock when the
                       savepoint was set.
Konstantin Osipov's avatar
Konstantin Osipov committed
2138 2139
*/

Konstantin Osipov's avatar
Konstantin Osipov committed
2140
void MDL_context::rollback_to_savepoint(MDL_ticket *mdl_savepoint)
Konstantin Osipov's avatar
Konstantin Osipov committed
2141
{
Konstantin Osipov's avatar
Konstantin Osipov committed
2142
  DBUG_ENTER("MDL_context::rollback_to_savepoint");
Konstantin Osipov's avatar
Konstantin Osipov committed
2143

2144 2145
  /* If savepoint is NULL, it is from the start of the transaction. */
  release_locks_stored_before(mdl_savepoint ?
2146
                              mdl_savepoint : m_trans_sentinel);
2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163

  DBUG_VOID_RETURN;
}


/**
  Release locks acquired by normal statements (SELECT, UPDATE,
  DELETE, etc) in the course of a transaction. Do not release
  HANDLER locks, if there are any.

  This method is used at the end of a transaction, in
  implementation of COMMIT (implicit or explicit) and ROLLBACK.
*/

void MDL_context::release_transactional_locks()
{
  DBUG_ENTER("MDL_context::release_transactional_locks");
2164
  release_locks_stored_before(m_trans_sentinel);
2165 2166 2167 2168 2169 2170 2171 2172
  DBUG_VOID_RETURN;
}


/**
  Does this savepoint have this lock?
  
  @retval TRUE  The ticket is older than the savepoint and
2173 2174
                is not LT, HA or GLR ticket. Thus it belongs
                to the savepoint.
2175
  @retval FALSE The ticket is newer than the savepoint
2176
                or is an LT, HA or GLR ticket.
2177 2178 2179 2180 2181 2182
*/

bool MDL_context::has_lock(MDL_ticket *mdl_savepoint,
                           MDL_ticket *mdl_ticket)
{
  MDL_ticket *ticket;
2183
  /* Start from the beginning, most likely mdl_ticket's been just acquired. */
2184 2185 2186
  MDL_context::Ticket_iterator it(m_tickets);
  bool found_savepoint= FALSE;

2187
  while ((ticket= it++) && ticket != m_trans_sentinel)
Konstantin Osipov's avatar
Konstantin Osipov committed
2188
  {
2189 2190 2191 2192
    /*
      First met the savepoint. The ticket must be
      somewhere after it.
    */
Konstantin Osipov's avatar
Konstantin Osipov committed
2193
    if (ticket == mdl_savepoint)
2194 2195 2196 2197 2198 2199 2200
      found_savepoint= TRUE;
    /*
      Met the ticket. If we haven't yet met the savepoint,
      the ticket is newer than the savepoint.
    */
    if (ticket == mdl_ticket)
      return found_savepoint;
Konstantin Osipov's avatar
Konstantin Osipov committed
2201
  }
2202
  /* Reached m_trans_sentinel. The ticket must be LT, HA or GRL ticket. */
2203
  return FALSE;
Konstantin Osipov's avatar
Konstantin Osipov committed
2204 2205 2206
}


2207 2208
/**
  Rearrange the ticket to reside in the part of the list that's
2209
  beyond m_trans_sentinel. This effectively changes the ticket
2210 2211 2212 2213 2214
  life cycle, from automatic to manual: i.e. the ticket is no
  longer released by MDL_context::release_transactional_locks() or
  MDL_context::rollback_to_savepoint(), it must be released manually.
*/

2215
void MDL_context::move_ticket_after_trans_sentinel(MDL_ticket *mdl_ticket)
2216 2217
{
  m_tickets.remove(mdl_ticket);
2218
  if (m_trans_sentinel == NULL)
2219
  {
2220
    m_trans_sentinel= mdl_ticket;
2221 2222 2223 2224
    /* sic: linear from the number of transactional tickets acquired so-far! */
    m_tickets.push_back(mdl_ticket);
  }
  else
2225
    m_tickets.insert_after(m_trans_sentinel, mdl_ticket);
2226
}