Vlad,
I had a good look at this change this weekend and I think it is indeed a
good idea to add this new type of waitForTransaction which searches for a
deadlock. Both of the places it is called do identical things.
I mentioned in another email that it is not good practice to declare a Sync
object in one function and send it down into a called function. It should
be unlocked where it is locked in order to keep things from getting
confusing.
So may I suggest that you declare Sync syncActiveTransactions in this new
version of waitForTransaction and take it out of getRelativeStatewhere it is
not needed for anything else in that function. In the other
waitForTransaction where your new function is called, it will need to be
unlocked as soon as the active transactions are initially searched. Then
your new waitForTransaction will get it again.
I think this approach is a little cleaner.
>-----Original Message-----
>From: Vladislav Vaintroub [mailto:vvaintroub@stripped]
>Sent: Wednesday, June 11, 2008 8:04 AM
>To: commits@stripped
>Subject: bzr commit into mysql-6.0-falcon branch (vvaintroub:2699)
Bug#37251
>
>#At bzr+ssh://bk-internal.mysql.com/bzrroot/server/mysql-6.0-falcon/
>
> 2699 Vladislav Vaintroub 2008-06-11
> Bug#37251 - Livelock between UPDATE and DELETE threads
>
> The problem was a bug in deadlock detection code.
> 2 threads with mutual dependencies doing deadlock at exactly
> same time both decide there is no deadlock, add themselves
> to waitFor list, thus building a cycle in it. Both threads
> will wait for each other until lock wait timeout happens
> (a deadlock). Meanwhile, any other thread that traverses
> waitFor list may enter the cycle described above and will
> loop until deadlock is resolved.
>
> Solution here is to modify deadlock detection to add dependency
> first, than check, then remove dependency if cycle is found.
>
> Care is taken to prevent compiler optimizations and hopefully
> the combination of volatile specifier and COMPARE_EXHANGE will
> generate a memory barrier to prevent reading elements while
> they are modified.
>
> Note, that instead of this fancy solution, plain old SyncObject
> could be used. The loop is short, the lock is cheap,
> but I can't estimate contention for the moment. If current lock-free
> implementation turns out to be buggy, this alternative can be
> considered.
>
> No testcase provided, the situation described in bug report
> can not be reliably reproduced.
>modified:
> storage/falcon/Transaction.cpp
> storage/falcon/Transaction.h
>
>per-file messages:
> storage/falcon/Transaction.cpp
> New overload for waitForTransaction, put all deadlock detection logic
> here instead of having the same code on 2 different places.
> storage/falcon/Transaction.h
> Transaction::waitingFor member has been made volatile (can be used
>concurrently by different threads)
>
> New overload for Transaction::waitForTransaction, put all deadlock
>detection logic
> here instead of having the same code on 2 different places.
>=== modified file 'storage/falcon/Transaction.cpp'
>--- a/storage/falcon/Transaction.cpp 2008-05-21 14:58:08 +0000
>+++ b/storage/falcon/Transaction.cpp 2008-06-11 13:03:37 +0000
>@@ -44,6 +44,8 @@
> #include "SRLSavepointRollback.h"
> #include "Bitmap.h"
> #include "BackLog.h"
>+#include "Interlock.h"
>+#include "Error.h"
>
> extern uint falcon_lock_wait_timeout;
>
>@@ -865,19 +867,17 @@ State Transaction::getRelativeState(Tran
> if (flags & DO_NOT_WAIT)
> return Active;
>
>- // If waiting would cause a deadlock, don't try it
>+ Sync syncActiveTransactions(
>+ &(database->transactionManager-
>>activeTransactions.syncObject),
>+ "Transaction::getRelativeState");
>
>- for (Transaction *trans = transaction->waitingFor; trans;
trans
>= trans->waitingFor)
>- if (trans == this)
>- return Deadlock;
>+ syncActiveTransactions.lock(Shared);
>
>- // OK, add a reference to the transaction to keep the object
>around, then wait for it go go away
>+ bool isDeadlock;
>+ waitForTransaction(transaction, &syncActiveTransactions,
>&isDeadlock);
>
>- transaction->addRef();
>- waitingFor = transaction;
>- transaction->waitForTransaction();
>- waitingFor = NULL;
>- transaction->release();
>+ if (isDeadlock)
>+ return Deadlock;
>
> return WasActive; // caller will need
to re-fetch
> }
>@@ -968,31 +968,69 @@ bool Transaction::waitForTransaction(Tra
> break;
>
> // If the transction is no longer active, see if it is committed
>-
>+
> if (!transaction || transaction->state == Available)
> return true;
>
> if (transaction->state == Committed)
> return true;
>
>- // If waiting would cause a deadlock, don't try it
>+ bool deadlock;
>+ State state = waitForTransaction(transaction,
&syncActiveTransactions,
>&deadlock);
>
>- for (Transaction *trans = transaction->waitingFor; trans; trans =
>trans->waitingFor)
>- if (trans == this)
>- return true;
>+ if (deadlock)
>+ return true;
>
>- // OK, add a reference to the transaction to keep the object around,
>then wait for it to go away
>+ return (state == Committed);
>
>- waitingFor = transaction;
>+}
>+
>+// Wait for transaction, unless it would lead to deadlock.
>+// Returns the state of transation.
>+//
>+// Note:
>+// Deadlock check could use locking, because there are potentially
>concurrent
>+// threads checking and modifying the waitFor list.
>+// Instead, it implements a fancy lock-free algorithm that works reliably
>only
>+// with full memory barriers. Thus "volatile"-specifier and
>COMPARE_EXCHANGE
>+// are used when traversing and modifying waitFor list. Maybe it is
better
>to
>+// use inline assembly or intrinsics to generate memory barrier instead of
>+// volatile.
>+
>+State Transaction::waitForTransaction(Transaction *transaction,Sync *sync,
>bool *deadlock)
>+{
>+
>+ *deadlock = false;
> transaction->addRef();
>- syncActiveTransactions.unlock();
>- transaction->waitForTransaction();
>+
>+ if (!COMPARE_EXCHANGE_POINTER(&waitingFor, NULL, transaction))
>+ FATAL("waitingFor was not NULL");
>+
>+ volatile Transaction *trans;
>+ for (trans = transaction->waitingFor; trans; trans = trans-
>>waitingFor)
>+ if (trans == this)
>+ {
>+ *deadlock = true;
>+ break;
>+ }
>+
>+ if (!(*deadlock))
>+ {
>+ if (sync)
>+ sync->unlock();
>+
>+ transaction->waitForTransaction();
>+ }
>+
>+ if (!COMPARE_EXCHANGE_POINTER(&waitingFor, transaction, NULL))
>+ FATAL("waitingFor was not %p",transaction);
>+
>+ State state = (State)transaction->state;
> transaction->release();
>- waitingFor = NULL;
>
>- return transaction->state == Committed;
>-}
>+ return state;
>
>+}
> void Transaction::waitForTransaction()
> {
> /***
>
>=== modified file 'storage/falcon/Transaction.h'
>--- a/storage/falcon/Transaction.h 2008-05-21 14:58:08 +0000
>+++ b/storage/falcon/Transaction.h 2008-06-11 13:03:37 +0000
>@@ -102,6 +102,7 @@ public:
> void addRef();
> void waitForTransaction();
> bool waitForTransaction (TransId transId);
>+ State waitForTransaction (Transaction *transaction, Sync
*sync,
>bool *deadlock);
> void dropTable(Table* table);
> void truncateTable(Table* table);
> bool hasUncommittedRecords(Table* table);
>@@ -145,7 +146,7 @@ public:
> int curSavePointId;
> Transaction *next; // next in database
> Transaction *prior; // next in database
>- Transaction *waitingFor;
>+ volatile Transaction *waitingFor;
> SavePoint *savePoints;
> SavePoint *freeSavePoints;
> SavePoint localSavePoints[LOCAL_SAVE_POINTS];
>
>
>--
>MySQL Code Commits Mailing List
>For list archives: http://lists.mysql.com/commits
>To unsubscribe: http://lists.mysql.com/commits?unsub=1
