Bug 29115 - Allow multiple read transactions to run concurrently on the same DB thread
Summary: Allow multiple read transactions to run concurrently on the same DB thread
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: New Bugs (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2009-09-09 18:27 PDT by Dumitru Daniliuc
Modified: 2009-09-22 15:25 PDT (History)
7 users (show)

See Also:


Attachments
patch (18.20 KB, patch)
2009-09-11 16:40 PDT, Dumitru Daniliuc
no flags Details | Formatted Diff | Diff
patch (18.14 KB, patch)
2009-09-17 11:58 PDT, Dumitru Daniliuc
no flags Details | Formatted Diff | Diff
patch (18.10 KB, patch)
2009-09-17 12:47 PDT, Dumitru Daniliuc
no flags Details | Formatted Diff | Diff
patch (18.83 KB, patch)
2009-09-17 14:35 PDT, Dumitru Daniliuc
no flags Details | Formatted Diff | Diff
patch (17.10 KB, patch)
2009-09-18 15:02 PDT, Dumitru Daniliuc
no flags Details | Formatted Diff | Diff
patch (17.37 KB, patch)
2009-09-18 16:35 PDT, Dumitru Daniliuc
no flags Details | Formatted Diff | Diff
patch (17.28 KB, patch)
2009-09-18 18:44 PDT, Dumitru Daniliuc
no flags Details | Formatted Diff | Diff
patch (17.28 KB, patch)
2009-09-21 14:43 PDT, Dumitru Daniliuc
dglazkov: review+
commit-queue: commit-queue-
Details | Formatted Diff | Diff
patch (17.96 KB, patch)
2009-09-22 14:50 PDT, Dumitru Daniliuc
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Dumitru Daniliuc 2009-09-09 18:27:19 PDT
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.
Comment 1 Dumitru Daniliuc 2009-09-11 16:40:47 PDT
Created attachment 39490 [details]
patch
Comment 2 Michael Nordman 2009-09-16 19:46:05 PDT
> 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.
Comment 3 Dumitru Daniliuc 2009-09-17 11:05:22 PDT
(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.
Comment 4 Dumitru Daniliuc 2009-09-17 11:58:47 PDT
Created attachment 39716 [details]
patch
Comment 5 Dumitru Daniliuc 2009-09-17 12:47:36 PDT
Created attachment 39717 [details]
patch

Same patch, but combined 2 hash maps into 1.
Comment 6 Michael Nordman 2009-09-17 13:48:59 PDT
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.
Comment 7 Dumitru Daniliuc 2009-09-17 14:35:34 PDT
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 {
    ...
}
Comment 8 Michael Nordman 2009-09-17 15:15:18 PDT
lgtm
Comment 9 Michael Nordman 2009-09-17 15:18:45 PDT
... and sorry for the bum brack steer

(buganizer, lord only knows what random bug that got posted too before)
Comment 10 Michael Nordman 2009-09-17 21:54:24 PDT
> > > 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.
Comment 11 Michael Nordman 2009-09-17 22:22:44 PDT
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.
Comment 12 Dumitru Daniliuc 2009-09-18 11:47:58 PDT
> 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".
Comment 13 Dumitru Daniliuc 2009-09-18 11:54:05 PDT
(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.
Comment 14 Michael Nordman 2009-09-18 12:35:48 PDT
> 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.
Comment 15 Dumitru Daniliuc 2009-09-18 15:02:23 PDT
Created attachment 39793 [details]
patch
Comment 16 Dumitru Daniliuc 2009-09-18 16:35:42 PDT
Created attachment 39803 [details]
patch

Same patch, but without the recursion.
Comment 17 Dumitru Daniliuc 2009-09-18 18:44:22 PDT
Created attachment 39809 [details]
patch

Same patch with minor style changes.
Comment 18 Michael Nordman 2009-09-20 11:17:10 PDT
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.
Comment 19 Dumitru Daniliuc 2009-09-21 14:42:47 PDT
(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.
Comment 20 Dumitru Daniliuc 2009-09-21 14:43:22 PDT
Created attachment 39880 [details]
patch
Comment 21 Michael Nordman 2009-09-21 14:49:12 PDT
lgtm... but i'm not a webkit reviewer
Comment 22 Dimitri Glazkov (Google) 2009-09-22 12:24:46 PDT
Comment on attachment 39880 [details]
patch

r=me.
Comment 23 WebKit Commit Bot 2009-09-22 13:09:11 PDT
Comment on attachment 39880 [details]
patch

Rejecting patch 39880 from commit-queue.

Failed to run "WebKitTools/Scripts/build-webkit" exit_code: 1
Comment 24 WebKit Commit Bot 2009-09-22 13:16:20 PDT
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)
Comment 25 Eric Seidel (no email) 2009-09-22 13:19:02 PDT
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.)
Comment 26 Dumitru Daniliuc 2009-09-22 13:20:21 PDT
(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.
Comment 27 Dumitru Daniliuc 2009-09-22 14:50:14 PDT
Created attachment 39946 [details]
patch

Same patch. Removed the unused 'readOnly' parameter to SQLTransactionCoordinator::acquireLock(). Should make all builders happy.
Comment 28 Dimitri Glazkov (Google) 2009-09-22 15:03:40 PDT
Comment on attachment 39946 [details]
patch

Still r=me.
Comment 29 WebKit Commit Bot 2009-09-22 15:25:03 PDT
Comment on attachment 39946 [details]
patch

Clearing flags on attachment: 39946

Committed r48653: <http://trac.webkit.org/changeset/48653>
Comment 30 WebKit Commit Bot 2009-09-22 15:25:09 PDT
All reviewed patches have been landed.  Closing bug.