amend 8a118e97c0bec8193a46acd6d98542c573177c26: Fix a racebb-10.6-MDEV-24731

Deadlock::find_cycle(): Only return a transaction, no length.

Deadlock::report(): Re-traverse the waits-for graph from trx onwards
after re-acquiring lock_sys.wait_mutex.

1 files changed, 25 insertions, 20 deletions

diff --git a/storage/innobase/lock/lock0lock.cc b/storage/innobase/lock/lock0lock.cc
index 59b5573ca56..319a62b9638 100644
--- a/storage/innobase/lock/lock0lock.cc
+++ b/storage/innobase/lock/lock0lock.cc
@@ -87,10 +87,11 @@ namespace Deadlock
 
   /** Quickly detect a deadlock using Brent's cycle detection algorithm.
   @param trx     transaction that is waiting for another transaction
-  @return a transaction that is part of a cycle, and the length of the cycle
+  @return a transaction that is part of a cycle
   @retval nullptr if no cycle was found */
-  inline std::pair<trx_t *,unsigned> find_cycle(trx_t *trx)
+  inline trx_t *find_cycle(trx_t *trx)
   {
+    mysql_mutex_assert_owner(&lock_sys.wait_mutex);
     trx_t *tortoise= trx, *hare= trx;
     for (unsigned power= 1, l= 1; (hare= hare->lock.wait_trx) != nullptr; l++)
     {
@@ -103,7 +104,7 @@ namespace Deadlock
         in effect in the past, it is possible that trx will be waiting
         for a transaction that participates in a pre-existing deadlock
         cycle. In that case, our victim will not be trx. */
-        return {hare, l};
+        return hare;
       }
       if (l == power)
       {
@@ -116,7 +117,7 @@ namespace Deadlock
         tortoise= hare;
       }
     }
-    return {nullptr, 0};
+    return nullptr;
   }
 };
 
@@ -5754,15 +5755,22 @@ namespace Deadlock
 
   ATTRIBUTE_COLD
   /** Report a deadlock (cycle in the waits-for graph).
-  @param trx    newest transaction waiting for a lock
-  @param cycle  transaction within a deadlock cycle
-  @param length length of the deadlock cycle
+  @param trx    transaction waiting for a lock in this thread
   @return the transaction to be rolled back (unless one was committed already)
   @return nullptr if no deadlock */
-  static trx_t *report(trx_t *const trx, trx_t *cycle, unsigned length)
+  static trx_t *report(trx_t *const trx)
   {
     mysql_mutex_unlock(&lock_sys.wait_mutex);
-    ut_ad(length > 1);
+
+    /* Normally, trx should be a direct part of the deadlock
+    cycle. However, if innodb_deadlock_detect had been OFF in the
+    past, our trx may be waiting for a lock that is held by a
+    participant of a pre-existing deadlock, without being part of the
+    deadlock itself. That is, the path to the deadlock may be P-shaped
+    instead of O-shaped, with trx being at the foot of the P.
+
+    We will process the entire path leading to a cycle, and we will
+    choose the victim (to be aborted) among the cycle. */
 
     static const char rollback_msg[]= "*** WE ROLL BACK TRANSACTION (%u)\n";
     char buf[9 + sizeof rollback_msg];
@@ -5779,11 +5787,14 @@ namespace Deadlock
       unsigned l= 0;
       LockMutexGuard g;
       mysql_mutex_lock(&lock_sys.wait_mutex);
+      /* Now that we are holding lock_sys.wait_mutex again, check
+      whether a cycle still exists. */
+      trx_t *cycle= find_cycle(trx);
+      if (!cycle)
+        return nullptr; /* One of the transactions was already aborted. */
       for (trx_t *next= cycle;;)
       {
         next= next->lock.wait_trx;
-        if (!next || ++l > length)
-          return nullptr; /* The original cycle must have been resolved. */
         const undo_no_t next_weight= TRX_WEIGHT(next) |
           (next->mysql_thd && thd_has_edited_nontrans_tables(next->mysql_thd)
            ? 1ULL << 63 : 0);
@@ -5798,8 +5809,6 @@ namespace Deadlock
         if (next == cycle)
           break;
       }
-      if (l != length)
-        return nullptr; /* The original cycle must have been resolved. */
 
       if (trx_pos && trx_weight == victim_weight)
       {
@@ -5825,7 +5834,6 @@ namespace Deadlock
           ut_ad(wait_lock);
           snprintf(buf, sizeof buf, "\n*** (%u) TRANSACTION:\n", ++l);
           print(buf);
-          ut_ad(l <= length);
           print(*next);
           print("*** WAITING FOR THIS LOCK TO BE GRANTED:\n");
           print(*wait_lock);
@@ -5898,18 +5906,15 @@ static bool Deadlock::check_and_resolve(trx_t *trx)
   ut_ad(trx->state == TRX_STATE_ACTIVE);
   ut_ad(!srv_read_only_mode);
 
-
   mysql_mutex_lock(&lock_sys.wait_mutex);
 
   if (!innodb_deadlock_detect)
     return false;
 
-  auto cycle= find_cycle(trx);
-
-  if (UNIV_LIKELY(!cycle.first))
+  if (UNIV_LIKELY(!find_cycle(trx)))
     return trx->lock.was_chosen_as_deadlock_victim;
-  trx_t *victim_trx= report(trx, cycle.first, cycle.second);
-  return victim_trx == trx || trx->lock.was_chosen_as_deadlock_victim;
+
+  return report(trx) == trx || trx->lock.was_chosen_as_deadlock_victim;
 }
 
 /*************************************************************//**