From: Date: June 11 2008 3:03pm Subject: bzr commit into mysql-6.0-falcon branch (vvaintroub:2699) Bug#37251 List-Archive: http://lists.mysql.com/commits/47732 X-Bug: 37251 Message-Id: <200806111303.m5BD3pfq007632@mail.mysql.com> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit #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];