MySQL Bugs: #35538: Falcon three-way deadlock between scavenger, gopher and an insert

Bug #35538	Falcon three-way deadlock between scavenger, gopher and an insert
Submitted:	24 Mar 2008 22:11	Modified:	8 Jan 2009 10:00
Reporter:	Kevin Lewis	Email Updates:
Status:	Closed	Impact on me:	None
Category:	MySQL Server: Falcon storage engine	Severity:	S3 (Non-critical)
Version:	6.04	OS:	Any
Assigned to:	Kevin Lewis	CPU Architecture:	Any

Description:
Both Chris Powers and Kevin Lewis have reproduced a deadlock between three threads in Falcon.

>> Chris Powers wrote:
>> The deadlock seems due to inconsistent coordination between
>> the record section and data section trees in Table.
>>
>> Gopher updates begin with DBB, descend through Section into BDB, and
>> then call in to Table and access RecordLeaf.
>>
>> Scavenging starts with Table, descends through RecordGroup and
>> RecordLeaf into Record, then calls back into Table to access Section.
>>
>> In this case, the logical-to-physical interaction resulted in a
>> deadlock between the Gopher and Scavenger with a hapless Insert caught
>> in between. The Gopher locks a BDB then goes after the RecordLeaf. The
>> Scavenger locks a RecordLeaf and goes after Section::syncInsert.
>> Section is held by an Insert waiting for the BDB.
>>
>> In general, the logical-to-physical interactions are governed by
>> Section::syncInsert, Bdb::syncObject and RecordLeaf::syncObject. At
>> the higher end is Table::syncObject, which is common to both trees but
>> not really a factor here.
>>
>> What are (or should be) the rules of engagement for Table::records and
>> Table::dataSection interactions?
>>

>Jim Starkey wrote;
>Would it make sense for Section::updateRecord to call
>Table::validateRecord *before* it got any bdbs?  If there's a subsequent
>committed record there's a subsequent committed record, after all.

Jim and Chris,  

I just happened to get this same three-way deadlock while running the test
for 34890.  I've run this test dozens of times and this is the first time
I've seen it. But yes, the gopher thread is doing things out of order by
getting the exclusive lock on the BDB he intends to update first, and then
calling Table::validateUpdate() -> Table::treeFetch() -> RecordLeaf::fetch()
which must lock the RecordLeaf::syncObject.

It is a simple matter to validate the update first in Section::updateRecord() and then go after the various BDBs.

How to repeat:
There is no deterministic test to cause this.  But when it occurs, a foregraound thread, a gopher thread, and the one and only scavenger all lock up.  In short order, most other threads will also lock up.  I will attach a set of call stacks.

The threads will be something like this;

Thread 1: Gopher
   Section::updateRecord(), BDB::syncObject EXCLUSIVE
   Table::treeFetch(), Table::syncObject SHARED
   RecordLeaf::fetch(), RecordLeaf::syncObject SHARED (WAIT on Thread 2)

Thread 2: retireRecords
   Table::retireRecords(), Table::syncObject SHARED
   RecordLeaf::retireRecords(), RecordLeaf::syncObject EXCLUSIVE
   Section::expungeRecord(), Section::syncInsert EXCLUSIVE (WAIT on Thread 3)

Thread 3: Table::insert
   Section::insertStub(), Section::syncInsert EXCLUSIVE   
   Cache::fetchPage(), BDB::syncObject EXCLUSIVE (WAIT on Thread 1)

Suggested fix:
Validate the update first in Section::updateRecord() and then go after the various BDBs.

Setting priority to P1 because it locks up everything.  I think it happens more often than is being reported since it is hard to diagnose.

Move the call to Table::validateUpdate() up to the top of Section::updateRecord() so that it does not hold and locks on any BDBs.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/44371

ChangeSet@1.2608, 2008-03-24 22:55:03-05:00, klewis@klewis-mysql. +10 -0
  Bug#35538 - Fix three-way deadlock between scavenger, gopher and 
  an insert by moving the call to Table::validateUpdate() up to the 
  top of Section::updateRecord() so that it does not hold any locks 
  on any BDBs.
  
  Also, prevent an inadvertent wakeup of an active gopher thread 
  waiting on another syncObject.

I now doubt if this is the right way to avoid the deadlock.  

section::updateRecord is run by a gopher thread which is about to put a record update from the serial log into a data page.  Since gopher threads can run in parallel, and a change by large earlier transaction may not get applied until after a change to the same record by a short transaction, Table::validateUpdate was added to make sure that the older record does not overwrite the newer record in the page.  

It makes sense to hold a lock on the page while you are doing this check.  

Otherwise one gopher thread could check for a newer record and not find one, then find the page and write the change, only to discover that another gopher added a newer version after your check.

Putting this change back into 'In Progress'.

While two concurrent gopher threads are putting sequential changes into the data page, the associated transactions are still active, not completed, so both of those record versions will be seen in the record's prior version chain.  So I no longer think this solution is a problem.  The only time both these record versions are not in the record chain is during recovery.  Fortunately, there is only one recovery thread, which processes these in transaction completion order.

Pushed into 6.0.5-alpha

Internal change only. No documentation needed.