From: Date: June 16 2008 5:39pm Subject: bzr commit into mysql-6.0-falcon branch (vvaintroub:2704) Bug#37251 List-Archive: http://lists.mysql.com/commits/47917 X-Bug: 37251 Message-Id: <200806161539.m5GFdev4009576@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/ 2704 Vladislav Vaintroub 2008-06-16 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 === 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-16 15:39:33 +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,20 +867,12 @@ State Transaction::getRelativeState(Tran if (flags & DO_NOT_WAIT) return Active; - // If waiting would cause a deadlock, don't try it + bool isDeadlock; + waitForTransaction(transaction, 0 , &isDeadlock); - for (Transaction *trans = transaction->waitingFor; trans; trans = trans->waitingFor) - if (trans == this) + if (isDeadlock) return Deadlock; - // OK, add a reference to the transaction to keep the object around, then wait for it go go away - - transaction->addRef(); - waitingFor = transaction; - transaction->waitForTransaction(); - waitingFor = NULL; - transaction->release(); - return WasActive; // caller will need to re-fetch } @@ -956,43 +950,89 @@ void Transaction::writeComplete(void) bool Transaction::waitForTransaction(TransId transId) { + bool deadlock; + State state = waitForTransaction(NULL, transId, &deadlock); + return (deadlock || state == Committed || state == Available); + +} + +// 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, TransId transId, + bool *deadlock) +{ + + + *deadlock = false; + State state; + + if(transaction) + transaction->addRef(); + TransactionManager *transactionManager = database->transactionManager; - Sync syncActiveTransactions(&transactionManager->activeTransactions.syncObject, "Transaction::waitForTransaction"); + Sync syncActiveTransactions(&transactionManager->activeTransactions.syncObject, + "Transaction::waitForTransaction"); syncActiveTransactions.lock(Shared); - Transaction *transaction; - - // If the transaction is still active, find it - for (transaction = transactionManager->activeTransactions.first; transaction; transaction = transaction->next) - if (transaction->transactionId == transId) - 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 (!transaction) + { + // transaction parameter is not given, find transaction using its ID. + for (transaction = transactionManager->activeTransactions.first; transaction; + transaction = transaction->next) + if (transaction->transactionId == transId) + { + transaction->addRef(); + break; + } + } - // If waiting would cause a deadlock, don't try it + if (!transaction) + return Committed; + + if (transaction->state == Available || transaction->state == Committed) + { + state = (State)transaction->state; + transaction->release(); + return state; + } - for (Transaction *trans = transaction->waitingFor; trans; trans = trans->waitingFor) + + 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) - return true; + { + *deadlock = true; + break; + } - // OK, add a reference to the transaction to keep the object around, then wait for it to go away + if (!(*deadlock)) + { + syncActiveTransactions.unlock(); + transaction->waitForTransaction(); + } - waitingFor = transaction; - transaction->addRef(); - syncActiveTransactions.unlock(); - transaction->waitForTransaction(); + if (!COMPARE_EXCHANGE_POINTER(&waitingFor, transaction, NULL)) + FATAL("waitingFor was not %p",transaction); + + 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-16 15:39:33 +0000 @@ -102,6 +102,7 @@ public: void addRef(); void waitForTransaction(); bool waitForTransaction (TransId transId); + State waitForTransaction (Transaction *transaction, TransId transId, 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];