Bug 61270

Summary: IndexedDB: Support LevelDB transactions.
Product: WebKit Reporter: Hans Wennborg <hans>
Component: New BugsAssignee: Hans Wennborg <hans>
Status: RESOLVED FIXED    
Severity: Normal CC: andreip, dglazkov, dgrogan, steveblock, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
Patch
webkit.review.bot: commit-queue-
manual patch
webkit-ews: commit-queue-
patch
none
patch
none
patch
none
patch steveblock: review+

Description Hans Wennborg 2011-05-23 04:05:34 PDT
IndexedDB: Support LevelDB transactions.
Comment 1 Hans Wennborg 2011-05-23 04:10:40 PDT
Created attachment 94397 [details]
Patch
Comment 2 WebKit Review Bot 2011-05-23 04:14:11 PDT
Attachment 94397 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/ChangeLog', u'Source/WebCor..." exit_code: 1

Source/WebCore/platform/leveldb/LevelDBTransaction.h:80:  get_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:81:  set_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:82:  get_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:83:  set_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:85:  get_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:86:  set_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:88:  compare_key_key is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:89:  compare_key_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:90:  compare_node_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Total errors found: 9 in 10 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 3 Hans Wennborg 2011-05-23 04:16:45 PDT
The AVLTree code was modeled after the old IDBKeyTree class which can be seen here: http://trac.webkit.org/browser/trunk/WebCore/storage/IDBKeyTree.h?rev=65873

The style warnings for get_less, set_less, etc. are hard to avoid since AVLTree expects the functions to be named like that.

The trickiest part of this patch is probably the TransactionIterator class.
Comment 4 WebKit Review Bot 2011-05-23 04:40:23 PDT
Comment on attachment 94397 [details]
Patch

Attachment 94397 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/8732046
Comment 5 Hans Wennborg 2011-05-23 04:46:23 PDT
Created attachment 94399 [details]
manual patch

Manual upload; looks like the script failed to upload LevelDBWriteBatch.* for some reason.
Comment 6 WebKit Review Bot 2011-05-23 04:48:29 PDT
Attachment 94399 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/ChangeLog', u'Source/WebCor..." exit_code: 1

Source/WebCore/platform/leveldb/LevelDBTransaction.h:80:  get_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:81:  set_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:82:  get_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:83:  set_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:85:  get_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:86:  set_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:88:  compare_key_key is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:89:  compare_key_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:90:  compare_node_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Total errors found: 9 in 10 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 7 Early Warning System Bot 2011-05-23 05:14:18 PDT
Comment on attachment 94399 [details]
manual patch

Attachment 94399 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/8723787
Comment 8 WebKit Review Bot 2011-05-23 05:16:41 PDT
Comment on attachment 94397 [details]
Patch

Attachment 94397 [details] did not pass cr-mac-ews (chromium):
Output: http://queues.webkit.org/results/8722875
Comment 9 Hans Wennborg 2011-05-23 06:22:05 PDT
Created attachment 94415 [details]
patch

Forgot to update project files for the other ports.
Comment 10 WebKit Review Bot 2011-05-23 06:24:17 PDT
Attachment 94415 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/CMakeLists.txt', u'Source/W..." exit_code: 1

Source/WebCore/platform/leveldb/LevelDBTransaction.h:80:  get_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:81:  set_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:82:  get_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:83:  set_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:85:  get_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:86:  set_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:88:  compare_key_key is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:89:  compare_key_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:90:  compare_node_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Total errors found: 9 in 14 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 11 Andrei Popescu 2011-05-23 12:31:35 PDT
Comment on attachment 94415 [details]
patch

Great stuff Hans, thanks a lot!

View in context: https://bugs.webkit.org/attachment.cgi?id=94415&action=review

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:57
> +        delete *iterator;

I wonder if you could store OwnPtr<AVLTreeNode> in your AVLTree (so the handle would be an OwnPtr instead of a raw pointer)? You wouldn't have to worry about iterating the tree and manually deleting every node.

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:113
> +    return true;

Seems to me that put() and remove() are very similar, the only differences being in how the 'deleted' flag is being set and in the fact that the key must be fabricated from a LevelDBSlice in the remove case. Can we factor out the common bits into a helper function?

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:143
> +            writeBatch->put(node->key, node->value);

Maybe a silly idea, but what exactly is a LevelDB WriteBatch? Can we not make our transaction own one and have put() and remove() operations work directly on the batch?

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:306
> +                m_treeIterator->next();

is the next in the tree iterator guaranteed to have a non-equal key to the current key?

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:312
> +                m_dbIterator->next();

ditto...I am asking because in 'handleConflictsAndDeletes()' you seem to take into account the situation where several calls to next() will yield records with the same key.

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:336
> +                m_treeIterator->prev(); // Iterator is at first entry >= key(). Step back once to entry < key.

Maybe add: "this is why we don't check for the keys being the same before stepping, like we do in next() above" ?

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:396
> +void LevelDBTransaction::TransactionIterator::findSmallest()

Are 'findSmallest/Largets' best names for these methods? What happens here is that we set m_current to the relevant iterator based on which of them has the smallest/largest key value. I would therefore call them something like 'setCurrentIteratorToSmallest/LargestKey()" or similar..

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:406
> +        else if (m_comparator->compare(m_dbIterator->key(), smallest->key()) < 0)

Do you need the else? You can just combine the two conditions in the if above?
Comment 12 Hans Wennborg 2011-05-24 03:32:00 PDT
(In reply to comment #11)
> (From update of attachment 94415 [details])
Thanks very much for the review, Andrei.

> Great stuff Hans, thanks a lot!
> 
> View in context: https://bugs.webkit.org/attachment.cgi?id=94415&action=review
> 
> > Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:57
> > +        delete *iterator;
> 
> I wonder if you could store OwnPtr<AVLTreeNode> in your AVLTree (so the handle would be an OwnPtr instead of a raw pointer)? You wouldn't have to worry about iterating the tree and manually deleting every node.

I think it would be hard to do this. It seems the way AVLTree works, there can sometimes be more than one handle to a node (as a function argument, return value, etc.), but with OwnPtr, that wouldn't work. RefPtr would work fine, but then we'd introduce unnecessary overhead.

> 
> > Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:113
> > +    return true;
> 
> Seems to me that put() and remove() are very similar, the only differences being in how the 'deleted' flag is being set and in the fact that the key must be fabricated from a LevelDBSlice in the remove case. Can we factor out the common bits into a helper function?

You're right. Doing this.

> 
> > Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:143
> > +            writeBatch->put(node->key, node->value);
> 
> Maybe a silly idea, but what exactly is a LevelDB WriteBatch? Can we not make our transaction own one and have put() and remove() operations work directly on the batch?

Yes, this was my first idea too: to just use the WriteBatch instead of a tree. However, the WriteBatch is just a list of operations, and doesn't allow for fast get-operations or iterators in key-order.

> 
> > Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:306
> > +                m_treeIterator->next();
> 
> is the next in the tree iterator guaranteed to have a non-equal key to the current key?

Yes. We will never have two nodes in the tree with the same key (same goes for the database).

> 
> > Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:312
> > +                m_dbIterator->next();
> 
> ditto...I am asking because in 'handleConflictsAndDeletes()' you seem to take into account the situation where several calls to next() will yield records with the same key.

No, the reason that handleConflictsAndDeletes() is a loop is that e.g. the two iterators may be equal, we would step the database iterator, but it may also be that the tree iterator is on a delete marker, so then that gets stepped, and now the two iterators may be equal again, and so on and so forth.

> 
> > Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:336
> > +                m_treeIterator->prev(); // Iterator is at first entry >= key(). Step back once to entry < key.
> 
> Maybe add: "this is why we don't check for the keys being the same before stepping, like we do in next() above" ?

Done.

> 
> > Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:396
> > +void LevelDBTransaction::TransactionIterator::findSmallest()
> 
> Are 'findSmallest/Largets' best names for these methods? What happens here is that we set m_current to the relevant iterator based on which of them has the smallest/largest key value. I would therefore call them something like 'setCurrentIteratorToSmallest/LargestKey()" or similar..

Yeah, that's probably better.

> 
> > Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:406
> > +        else if (m_comparator->compare(m_dbIterator->key(), smallest->key()) < 0)
> 
> Do you need the else? You can just combine the two conditions in the if above?

Done.
Comment 13 Hans Wennborg 2011-05-24 03:33:44 PDT
Created attachment 94589 [details]
patch

manual upload
Comment 14 WebKit Review Bot 2011-05-24 03:36:03 PDT
Attachment 94589 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/CMakeLists.txt', u'Source/W..." exit_code: 1

Source/WebCore/platform/leveldb/LevelDBTransaction.h:80:  get_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:81:  set_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:82:  get_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:83:  set_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:85:  get_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:86:  set_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:88:  compare_key_key is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:89:  compare_key_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:90:  compare_node_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Total errors found: 9 in 14 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 15 Andrei Popescu 2011-05-24 07:03:55 PDT
Thanks Hans. LGTM!
Comment 16 Hans Wennborg 2011-05-24 07:16:13 PDT
(In reply to comment #15)
> Thanks Hans. LGTM!

Thanks. Steve, can you take a look?
Comment 17 Steve Block 2011-05-24 15:41:55 PDT
Comment on attachment 94589 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=94589&action=review

Some trivial drive-by comments. I think you'll need to walk me through this patch in person!

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:72
> +        v.append(*cp);

Does Vector have a method to allow you to do a memcpy and a blanket set, rather than this loop?

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:237
> +};

Spurious ;

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:326
> +                m_treeIterator->prev(); // Iterator is at first entry >= key(). Step back once to entry < key. This is why we don't check for the keys being the same before stepping, like we do in next() above.

Usually put comments this long on a line by themselves, and probably wrap to 80 lines

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:364
> +    for (;;) {

Usually use 'while (true)'

> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:394
> +        if (!smallest || m_comparator->compare(m_dbIterator->key(), smallest->key()) < 0)

Why not combine these 'if's ?

> Source/WebCore/platform/leveldb/LevelDBTransaction.h:78
> +        typedef LevelDBSlice key;

Do you need these typedefs? In any case, I think they should use a leading capital, as they're effectively type names.

> Source/WebCore/platform/leveldb/LevelDBWriteBatch.cpp:51
> +static leveldb::Slice makeSlice(const LevelDBSlice& s)

Which header is this defined in? Is this the best place for it?

> Source/WebCore/platform/leveldb/LevelDBWriteBatch.h:42
> +class LevelDBWriteBatch {

This is a rather opaque name - it might be good to have class-level comment here explaining conceptually what a 'batch' is.

> Source/WebCore/platform/leveldb/LevelDBWriteBatch.h:61
> +#endif

Should probably comment endifs, particularly when two appear together like this.

> Source/WebCore/storage/IDBLevelDBBackingStore.cpp:53
> +template <typename DbOrTransaction>

'DBOrTransaction' or 'DatabaseOrTransaction' I think

> Source/WebCore/storage/IDBLevelDBBackingStore.cpp:810
> +    ASSERT(m_currentTransaction);

Pattern is to not use asserts where we'd crash immediately afterwards anyway
Comment 18 Hans Wennborg 2011-05-25 03:10:21 PDT
Comment on attachment 94589 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=94589&action=review

>> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:72
>> +        v.append(*cp);
> 
> Does Vector have a method to allow you to do a memcpy and a blanket set, rather than this loop?

Yes, one can append a whole chunk of data at once. Doing that.

>> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:237
>> +};
> 
> Spurious ;

Removed.

>> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:326
>> +                m_treeIterator->prev(); // Iterator is at first entry >= key(). Step back once to entry < key. This is why we don't check for the keys being the same before stepping, like we do in next() above.
> 
> Usually put comments this long on a line by themselves, and probably wrap to 80 lines

Done.

>> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:364
>> +    for (;;) {
> 
> Usually use 'while (true)'

Done.

>> Source/WebCore/platform/leveldb/LevelDBTransaction.cpp:394
>> +        if (!smallest || m_comparator->compare(m_dbIterator->key(), smallest->key()) < 0)
> 
> Why not combine these 'if's ?

That would become if (m_dbIterator->isValid() && (!smallest || m_comparator->compare(m_dbIterator->key(), smallest->key()) < 0))
I personally find it easier to read as it is..

>> Source/WebCore/platform/leveldb/LevelDBTransaction.h:78
>> +        typedef LevelDBSlice key;
> 
> Do you need these typedefs? In any case, I think they should use a leading capital, as they're effectively type names.

AVLTree needs them, and expects them to be named like this.

>> Source/WebCore/platform/leveldb/LevelDBWriteBatch.cpp:51
>> +static leveldb::Slice makeSlice(const LevelDBSlice& s)
> 
> Which header is this defined in? Is this the best place for it?

We don't want to define this in any header, since it uses leveldb::Slice which we're trying to keep inside the wrappers..

>> Source/WebCore/platform/leveldb/LevelDBWriteBatch.h:42
>> +class LevelDBWriteBatch {
> 
> This is a rather opaque name - it might be good to have class-level comment here explaining conceptually what a 'batch' is.

Done.

>> Source/WebCore/platform/leveldb/LevelDBWriteBatch.h:61
>> +#endif
> 
> Should probably comment endifs, particularly when two appear together like this.

Done.

>> Source/WebCore/storage/IDBLevelDBBackingStore.cpp:53

> 
> 'DBOrTransaction' or 'DatabaseOrTransaction' I think

Done.

>> Source/WebCore/storage/IDBLevelDBBackingStore.cpp:810
>> +    ASSERT(m_currentTransaction);
> 
> Pattern is to not use asserts where we'd crash immediately afterwards anyway

If you don't feel strongly about it, I'd like to keep these. I see it more as documentation saying "this function operates within a transaction"..
Comment 19 Hans Wennborg 2011-05-25 03:10:55 PDT
Created attachment 94762 [details]
patch
Comment 20 WebKit Review Bot 2011-05-25 03:13:24 PDT
Attachment 94762 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/WebCore/CMakeLists.txt', u'Source/W..." exit_code: 1

Source/WebCore/platform/leveldb/LevelDBTransaction.h:80:  get_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:81:  set_less is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:82:  get_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:83:  set_greater is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:85:  get_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:86:  set_balance_factor is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:88:  compare_key_key is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:89:  compare_key_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Source/WebCore/platform/leveldb/LevelDBTransaction.h:90:  compare_node_node is incorrectly named. Don't use underscores in your identifier names.  [readability/naming] [4]
Total errors found: 9 in 14 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 21 Hans Wennborg 2011-05-25 09:51:15 PDT
Created attachment 94797 [details]
patch

Some changes after walking through the code with Steve:

- Simplify TransactionIterator::next() and prev() by introducing a nonCurrent variable
- Use a variable to determine whether to keep looping in TransactionIterator::handleConflictsAndDeletes()
- Add comment about LevelDBWriteBatch::remove()
Comment 22 Steve Block 2011-05-25 09:59:54 PDT
Comment on attachment 94797 [details]
patch

r=me
Comment 23 Hans Wennborg 2011-05-26 01:48:32 PDT
Committed r87370: <http://trac.webkit.org/changeset/87370>