Bug 29115 – Allow multiple read transactions to run concurrently on the same DB thread

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Dumitru Daniliuc]

Now that we have a notion of read only transactions and a way to deny all write operations they might attempt (bug 28918), we can change the transaction coordinator to allow multiple read transactions on the same DB thread to run concurrently, without risking running into deadlocks (no write operations == no exclusive locks on DB files). We should do it.

[Dumitru Daniliuc]

Created attachment 39490 [details]
patch

[Michael Nordman]

> m_pendingTransactions.add(dbIdentifier, pendingTransactions);
> it = m_pendingTransactions.find(dbIdentifier);

Looks like map.add() will return an iterator for you. So you don't have to call find() again.

        // does nothing if key is already present
        // return value is a pair of the iterator to the key location, 
        // and a boolean that's true if a new value was actually added
        pair<iterator, bool> add(const KeyType&, const MappedType&); 

> while ((pt_it->get() != transaction) && (pt_it->get()->isReadOnly()) && (++pt_it, 1));
> ASSERT(pt_it->get() == transaction);

Since the iteration can't fail to find your transaction, according to the ASSERT, I don't think you need to test for end() in your while loop. Also, that while loop is a bit much to parse... (hmmm, what does (foo, 1) mean :)

while ((pt_it->get() != transaction) && pt_it->get()->isReadOnly())
  ++pt_it

The logic looks good to me.

[Dumitru Daniliuc]

(In reply to comment #2)
> > m_pendingTransactions.add(dbIdentifier, pendingTransactions);
> > it = m_pendingTransactions.find(dbIdentifier);
> 
> Looks like map.add() will return an iterator for you. So you don't have to call
> find() again.

good catch! fixed.

> > while ((pt_it->get() != transaction) && (pt_it->get()->isReadOnly()) && (++pt_it, 1));
> > ASSERT(pt_it->get() == transaction);
> 
> Since the iteration can't fail to find your transaction, according to the
> ASSERT, I don't think you need to test for end() in your while loop. Also, that
> while loop is a bit much to parse... (hmmm, what does (foo, 1) mean :)

i don't think checking for end() is redundant. if we have a bug in this code and the transaction was somehow deleted before releaseLock() is called, i think it's better to fail the assertion than to get an unexpected crash in the while loop.

(a, b, ..., y, z) is equivalent to

a;
b;
...
y;
return z;

don't you love C++? :)

> while ((pt_it->get() != transaction) && pt_it->get()->isReadOnly())
>   ++pt_it
> 
> The logic looks good to me.

i changed it to this, but i kept the (pt_it != pendingTransactions.end()) check too.

[Dumitru Daniliuc]

Created attachment 39716 [details]
patch

[Dumitru Daniliuc]

Created attachment 39717 [details]
patch

Same patch, but combined 2 hash maps into 1.

[Michael Nordman]

Getting there... the introduction of the CoordinationInfo struct is good, the algorithm is easier to follow as a result... please rename the data members and types used for even greater clarity...

 50         typedef HashMap<String, TransactionsQueue> TransactionsHashMap;
 51         struct CoordinationInfo {
 52             TransactionsQueue pendingTransactions;
 53             int numPendingWriteTransactions;
 54         };
 55         typedef HashMap<String, CoordinationInfo> TransactionsHashMap;
 56         TransactionsHashMap m_pendingTransactions;

on the new struct, add a default ctor that zero-inits numPendingWriteTransactions 

add a code comment that indicates the String identifies a database file

typedef HashMap<String, CoordinationInfo> CoordinationInfoMap;
CoordinationInfoMap m_coordinationInfoMap;

89     CoordinationInfo& cInfo = it->second;

I think webkit style would have you call this either 'info' or 'coordinationInfo', the cJazz has a hungarian sounds to it.

57         CoordinationInfo cInfo;
58         cInfo.numPendingWriteTransactions = 0;
59         it = m_pendingTransactions.add(dbIdentifier, cInfo).first;

subtract two lines

it = m_coordinationInfoMap.add(dbIdentifier, CoordinationInfo()).first;


 131             if (!cInfo.pendingTransactions.first()->isReadOnly())
 132                 cInfo.pendingTransactions.first()->lockAcquired();
 133             else {
 134                 TransactionsQueue::iterator pt_it = cInfo.pendingTransactions.begin();
 135                 while ((pt_it != cInfo.pendingTransactions.end()) && (pt_it->get()->isReadOnly())) {
 136                     pt_it->get()->lockAcquired();
 137                     ++pt_it;
 138                 }
 139             }

Since the else clause requires braces, put them around the if clause too.

[Dumitru Daniliuc]

Created attachment 39725 [details]
patch

(In reply to comment #6)
> on the new struct, add a default ctor that zero-inits
> numPendingWriteTransactions 

done.

> add a code comment that indicates the String identifies a database file

done.

> typedef HashMap<String, CoordinationInfo> CoordinationInfoMap;
> CoordinationInfoMap m_coordinationInfoMap;

done.

> 89     CoordinationInfo& cInfo = it->second;
> 
> I think webkit style would have you call this either 'info' or
> 'coordinationInfo', the cJazz has a hungarian sounds to it.

changed to 'info'.

> 57         CoordinationInfo cInfo;
> 58         cInfo.numPendingWriteTransactions = 0;
> 59         it = m_pendingTransactions.add(dbIdentifier, cInfo).first;
> 
> subtract two lines

done.

>  131             if (!cInfo.pendingTransactions.first()->isReadOnly())
>  132                 cInfo.pendingTransactions.first()->lockAcquired();
>  133             else {
>  134                 TransactionsQueue::iterator pt_it =
> cInfo.pendingTransactions.begin();
>  135                 while ((pt_it != cInfo.pendingTransactions.end()) &&
> (pt_it->get()->isReadOnly())) {
>  136                     pt_it->get()->lockAcquired();
>  137                     ++pt_it;
>  138                 }
>  139             }
> 
> Since the else clause requires braces, put them around the if clause too.

i'm not sure the webkit style allows this. at the very least, they have this example that is correct according to the webkit guide:

if (condition)
    doSomething();
else {
    ...
}

[Michael Nordman]

lgtm

[Michael Nordman]

... and sorry for the bum brack steer

(buganizer, lord only knows what random bug that got posted too before)

[Michael Nordman]

> > > while ((pt_it->get() != transaction) && (pt_it->get()->isReadOnly()) && (++pt_it, 1));
> > > ASSERT(pt_it->get() == transaction);
> > 
> > Since the iteration can't fail to find your transaction, according to the
> > ASSERT, I don't think you need to test for end() in your while loop. Also, that
> > while loop is a bit much to parse... (hmmm, what does (foo, 1) mean :)
> 
> i don't think checking for end() is redundant. if we have a bug in this code
> and the transaction was somehow deleted before releaseLock() is called, i think
> it's better to fail the assertion than to get an unexpected crash in the while
> loop.

oh... wait... i missed this.

If there's a bug, we should fix it. Either the assertion holds or it doesn't, which is it? And if it doesn't hold than shouldn't there be code for that case?

 92         TransactionsQueue::iterator pt_it = info.pendingTransactions.begin();
 93         while ((pt_it != info.pendingTransactions.end()) && (pt_it->get() != transaction) && (pt_it->get()->isReadOnly()))
 94             ++pt_it;
 95         ASSERT(pt_it->get() == transaction);
 96         info.pendingTransactions.remove(pt_it);

Also webkit style issues. I'm not sure what webkit style says about parens, certainly that last condition doesn't need them. I am sure webkit style frowns upon abbr_undbr naming. I think you need to take a pass thru this patch for style'isms.  What does webkit style say about non-const references like this?
CoordinationInfo& info = it->second;

If you had a private helper method to return a CoordiationInfoMap* given a dbIdentifier, I think that could help because you'd only have one it(erator) to be concerned with, and no non-const references involved.

[Michael Nordman]

You know, in looking at this more closely, maybe you should take a stab at modifying your data structures to better match the type of logic that needs to be applied to them. Iterating over a wanna be FIFO queue is just not quite right. I think you've managed to implement the desired behavior despite the data structures, but they're not working in your favor.

struct CoordinationInfo {
  Q pendingTransactions;
  Set activeReadTransactions;
  Transaction* activeReadWriteTransaction;
};

That may be easier to reason about.

[Dumitru Daniliuc]

> If there's a bug, we should fix it. Either the assertion holds or it doesn't,
> which is it? And if it doesn't hold than shouldn't there be code for that case?
> 
>  92         TransactionsQueue::iterator pt_it =
> info.pendingTransactions.begin();
>  93         while ((pt_it != info.pendingTransactions.end()) && (pt_it->get()
> != transaction) && (pt_it->get()->isReadOnly()))
>  94             ++pt_it;
>  95         ASSERT(pt_it->get() == transaction);
>  96         info.pendingTransactions.remove(pt_it);

removed the check for pt_it != info.pendingTransactions.end(). i'm not very happy about this: if at a later time we somehow introduce a bug in this code, it will result in seg faults. however, ASSERTs are no-ops in release builds and i'm not sure if there's anything better than crashing the app that we can do when we don't find the transaction in this list.

> Also webkit style issues. I'm not sure what webkit style says about parens,
> certainly that last condition doesn't need them.

removed.

> I am sure webkit style frowns upon abbr_undbr naming. I think you need to take a pass thru this patch for
> style'isms.

done.

< What does webkit style say about non-const references like this?
> CoordinationInfo& info = it->second;
> 
> If you had a private helper method to return a CoordiationInfoMap* given a
> dbIdentifier, I think that could help because you'd only have one it(erator) to
> be concerned with, and no non-const references involved.

un-abbreviated the iterator variables.

i don't think webkit's style guide says anything about non-const references. in any case, it seems to me like a legitimate way to modify some data "in place".

[Dumitru Daniliuc]

(In reply to comment #11)
> You know, in looking at this more closely, maybe you should take a stab at
> modifying your data structures to better match the type of logic that needs to
> be applied to them. Iterating over a wanna be FIFO queue is just not quite
> right. I think you've managed to implement the desired behavior despite the
> data structures, but they're not working in your favor.
> 
> struct CoordinationInfo {
>   Q pendingTransactions;
>   Set activeReadTransactions;
>   Transaction* activeReadWriteTransaction;
> };
> 
> That may be easier to reason about.

let's talk a bit about this offline. ideally (performance-wise), i might want a list of sets of transactions: each write transaction would have its own set and all read transactions that are supposed to run concurrently would be put into the same set. and the list would really be a linked list (or similar) to allow O(1) removeFirst() operations. but that might be a bit of an overkill.

[Michael Nordman]

> let's talk a bit about this offline. ideally (performance-wise), i might want a
> list of sets of transactions: each write transaction would have its own set and
> all read transactions that are supposed to run concurrently would be put into
> the same set. and the list would really be a linked list (or similar) to allow
> O(1) removeFirst() operations. but that might be a bit of an overkill.

That sounds like a way to organize the data structures too, I think you'd lose the ordering in which reads arrive when more than one piles up while waiting on a write to complete, but not sure that really matters since they'd all get started when the write completes.

[Dumitru Daniliuc]

Created attachment 39793 [details]
patch

[Dumitru Daniliuc]

Created attachment 39803 [details]
patch

Same patch, but without the recursion.

[Dumitru Daniliuc]

Created attachment 39809 [details]
patch

Same patch with minor style changes.

[Michael Nordman]

The SQLTransactionCoordinator logic LGTM, much clearer.

My first look at the layout tests...

// Hack: wait for these transactions to finish running before terminating the test
Is this empty transaction guaranteed to finish last?

The two new layout tests start <n> transactions back to back. Would a valid way to wait for completion be to observe <n>th completion callback and signal 'done' at that point? Something like bump a  'transactionsStarted' count prior to calling db.transaction() or readTransaction(), and bump a 'transactionComplte' count in the success callback, and test if (started == complete) for done'ness.


Incidentally, unrelated to this patch, looks like sync Database.tableNames() method is a wedge-ladden land-mine waiting to get stepped on. Runs a select statement without an explicit transaction, so that puts the statement in an implicit transaction. Depending on the lock applied to the file, and on the connection which holds that lock... this can wedge the system. Database.tableNames() is only used by the inpspector, so webapp code can't get wedged by this, but the inspector can.

[Dumitru Daniliuc]

(In reply to comment #18)
> The SQLTransactionCoordinator logic LGTM, much clearer.
> 
> My first look at the layout tests...
> 
> // Hack: wait for these transactions to finish running before terminating the
> test
> Is this empty transaction guaranteed to finish last?

It is (because it is a write transactions, and the transaction coordinator will wait for all other transactions to finish executing before scheduling this one), but it is a pretty hacky way to assert termination.

> The two new layout tests start <n> transactions back to back. Would a valid way
> to wait for completion be to observe <n>th completion callback and signal
> 'done' at that point? Something like bump a  'transactionsStarted' count prior
> to calling db.transaction() or readTransaction(), and bump a
> 'transactionComplte' count in the success callback, and test if (started ==
> complete) for done'ness.

replaced the hack in both layout tests with something nicer.

> Incidentally, unrelated to this patch, looks like sync Database.tableNames()
> method is a wedge-ladden land-mine waiting to get stepped on. Runs a select
> statement without an explicit transaction, so that puts the statement in an
> implicit transaction. Depending on the lock applied to the file, and on the
> connection which holds that lock... this can wedge the system.
> Database.tableNames() is only used by the inpspector, so webapp code can't get
> wedged by this, but the inspector can.

you're right, we (or somebody else?) will have to take a look at this at some point.

[Dumitru Daniliuc]

Created attachment 39880 [details]
patch

[Michael Nordman]

lgtm... but i'm not a webkit reviewer

[Dimitri Glazkov (Google)]

Comment on attachment 39880 [details]
patch

r=me.

[WebKit Commit Bot]

Comment on attachment 39880 [details]
patch

Rejecting patch 39880 from commit-queue.

Failed to run "WebKitTools/Scripts/build-webkit" exit_code: 1

[WebKit Commit Bot]

Comment on attachment 39880 [details]
patch

Rejecting patch 39880 from commit-queue.

Failed to run "WebKitTools/Scripts/build-webkit" exit_code: 1
Last 1000 characters of output:
sr/include/libxml2 -I/Users/eseidel/Projects/build/Release/WebCoreSQLite3 -I/Users/eseidel/Projects/build/Release/DerivedSources/WebCore -I/Users/eseidel/Projects/build/WebCore.build/Release/WebCore.build/DerivedSources/i386 -I/Users/eseidel/Projects/build/WebCore.build/Release/WebCore.build/DerivedSources -include /var/folders/zz/zzzivhrRnAmviuee++2Pvk+-4yw/-Caches-/com.apple.Xcode.72687/SharedPrecompiledHeaders/WebCorePrefix-bbyywajvccdtusbqnmzotlpadxhk/WebCorePrefix.h -c /Users/eseidel/Projects/build/Release/DerivedSources/WebCore/JSDOMWindow.cpp -o /Users/eseidel/Projects/build/WebCore.build/Release/WebCore.build/Objects-normal/i386/JSDOMWindow.o
** BUILD FAILED **

The following build commands failed:
WebCore:
	Distributed-CompileC /Users/eseidel/Projects/build/WebCore.build/Release/WebCore.build/Objects-normal/i386/SQLTransactionCoordinator.o /Users/eseidel/Projects/CommitQueue/WebCore/storage/SQLTransactionCoordinator.cpp normal i386 c++ com.apple.compilers.gcc.4_2
(1 failure)

[Eric Seidel (no email)]

Sorry for the double-rejection, that's bug 28239.  At least the second one included helpful output! (Which is what I was trying to test here.)

[Dumitru Daniliuc]

(In reply to comment #25)
> Sorry for the double-rejection, that's bug 28239.

no problem. patching this patch on a mac now and will build it in release mode before re-uploading it. sorry it failed.

[Dumitru Daniliuc]

Created attachment 39946 [details]
patch

Same patch. Removed the unused 'readOnly' parameter to SQLTransactionCoordinator::acquireLock(). Should make all builders happy.

[Dimitri Glazkov (Google)]

Comment on attachment 39946 [details]
patch

Still r=me.

[WebKit Commit Bot]

Comment on attachment 39946 [details]
patch

Clearing flags on attachment: 39946

Committed r48653: <http://trac.webkit.org/changeset/48653>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.