Bug 61270 – IndexedDB: Support LevelDB transactions.

• Component: New Bugs
• Status: RESOLVED FIXED

[Hans Wennborg]

IndexedDB: Support LevelDB transactions.

[Hans Wennborg]

Created attachment 94397 [details]
Patch

[WebKit Review Bot]

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.

[Hans Wennborg]

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.

[WebKit Review Bot]

Comment on attachment 94397 [details]
Patch

Attachment 94397 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/8732046

[Hans Wennborg]

Created attachment 94399 [details]
manual patch

Manual upload; looks like the script failed to upload LevelDBWriteBatch.* for some reason.

[WebKit Review Bot]

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.

[Early Warning System Bot]

Comment on attachment 94399 [details]
manual patch

Attachment 94399 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/8723787

[WebKit Review Bot]

Comment on attachment 94397 [details]
Patch

Attachment 94397 [details] did not pass cr-mac-ews (chromium):
Output: http://queues.webkit.org/results/8722875

[Hans Wennborg]

Created attachment 94415 [details]
patch

Forgot to update project files for the other ports.

[WebKit Review Bot]

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.

[Andrei Popescu]

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?

[Hans Wennborg]

(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.

[Hans Wennborg]

Created attachment 94589 [details]
patch

manual upload

[WebKit Review Bot]

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.

[Andrei Popescu]

Thanks Hans. LGTM!

[Hans Wennborg]

(In reply to comment #15)
> Thanks Hans. LGTM!

Thanks. Steve, can you take a look?

[Steve Block]

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

[Hans Wennborg]

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"..

[Hans Wennborg]

Created attachment 94762 [details]
patch

[WebKit Review Bot]

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.

[Hans Wennborg]

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()

[Steve Block]

Comment on attachment 94797 [details]
patch

r=me

[Hans Wennborg]

Committed r87370: <http://trac.webkit.org/changeset/87370>