1290853 - /IndexedDB/transaction-lifetime-empty.html test is unstable

Status: RESOLVED FIXED

(Core :: Storage: IndexedDB, defect)

Description

[James Graham [:jgraham]]

Going to disable for now.

Comment 1

[Bevis Tseng[:bevis][:btseng](Exited)]

All the symptoms are the same in 
https://treeherder.mozilla.org/logviewer.html#?job_id=25080935&repo=try#L4052
https://treeherder.mozilla.org/#/jobs?repo=try&revision=c43f8053ce04&selectedJob=25080935
"
TEST-UNEXPECTED-FAIL | /IndexedDB/transaction-lifetime-empty.html | Multiple transactions without requests complete in the expected order - assert_array_equals: property 3, expected "tx2.oncomplete" but got "tx3.oncomplete"
"

Take this bug to follow up.

Comment 2

[Bevis Tseng[:bevis][:btseng](Exited)]

Attachment: (v1) Patch: Iterate the Blocked Transactions in the first-come, first-served order.

The root cause of this bug is that when iterating the blocking transactions of a finished one, we didn't guarantee the iterating order to be the same to the blocking order because the Iterator in nsTHashtable runs in random according to [1], and there seems no other hashtable implementation in gecko that guarantees this.

Hence, in this patch, I'd like to combine the nsTHashtable with a nsTArray to remember the blocking order for the iteration later in NoteFinishedTransaction(), then we can fix this problem without sacrificing the performance of adding entry into blocking list too much.

Hi Jan,

May I have your review for this change?

Thanks!

[1] https://developer.mozilla.org/en-US/docs/Detailed_XPCOM_hashtable_guide#nsTHashtable

Comment 3

[Jan Varga [:janv]]

Comment on attachment 8784317 [details] [diff] [review]
(v1) Patch: Iterate the Blocked Transactions in the first-come, first-served order.

Review of attachment 8784317 [details] [diff] [review]:
-----------------------------------------------------------------

Is the hash table actually needed ?
It seems to me that we only ever add stuff to it and then iterate over entries before we destroy it.
The other one mBlockedOn looks the same, although there are RemoveEntry calls for it, so a plain array can be slower in that case.
Can you double check with Kyle (if he is available) if he is ok with converting mBlocking to an array ?

Comment 4

[Jan Varga [:janv]]

PutEntry also prevents adding the same object multiple times, but I don't think that can happen.
Since I'm not 100% sure, you can add an assertion for that.
Btw, the iterator for hash tables checks chaos mode setting, so you can enable chaos mode to trigger this bug easily.

Comment 5

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Jan Varga [:janv] from comment #3)
> Comment on attachment 8784317 [details] [diff] [review]
> (v1) Patch: Iterate the Blocked Transactions in the first-come, first-served
> order.
> 
> Review of attachment 8784317 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> Is the hash table actually needed ?
> It seems to me that we only ever add stuff to it and then iterate over
> entries before we destroy it.
My fist WIP is to define mBlocking as nsTArray<TransactionInfo*>, and I immediately found that redundant entry is possible [1][2] for the scenario in test_overlapping_transactions.js. That means I have to check the redundant entry in O(n) if nsTArray is used before appending an entry. :(
> The other one mBlockedOn looks the same, although there are RemoveEntry
> calls for it, so a plain array can be slower in that case.
That's why I make this change only for mBlocking. :)
> Can you double check with Kyle (if he is available) if he is ok with
> converting mBlocking to an array ?
Will do. :)

[1] http://searchfox.org/mozilla-central/diff/630eacc28dba9cec357c1d6b05ab66ac926e98e1/dom/indexedDB/ActorsParent.cpp#9459
[2] http://searchfox.org/mozilla-central/diff/630eacc28dba9cec357c1d6b05ab66ac926e98e1/dom/indexedDB/ActorsParent.cpp#9470

Comment 6

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Jan Varga [:janv] from comment #4)
> PutEntry also prevents adding the same object multiple times, but I don't
> think that can happen.
No, it can happen in test_overlapping_transactions.js as explained in comment 5.
> Since I'm not 100% sure, you can add an assertion for that.
> Btw, the iterator for hash tables checks chaos mode setting, so you can
> enable chaos mode to trigger this bug easily.
Thanks for this information.
Actually, I can reproduce this bug easily by just refreshing the test page 3~5 times. :p

Comment 7

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Jan Varga [:janv] from comment #3)
> Can you double check with Kyle (if he is available) if he is ok with
> converting mBlocking to an array ?
I'd like to know if the explanation in comment 5 can convince you that that hashtable is still required.
I'll ping him if we still don't have conclusion on this. :)

Comment 8

[Jan Varga [:janv]]

Well, if there's no better way ... Kyle should know this code very well. I remember he implemented these hash tables to fix some performance problems.

Comment 9

[Bevis Tseng[:bevis][:btseng](Exited)]

Never mind. Let's ping him. :)

Comment 10

[Jan Varga [:janv]]

You can also try to find, how often the redundant entry case happens.

Comment 11

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Jan Varga [:janv] from comment #10)
> You can also try to find, how often the redundant entry case happens.
m... I believe this is frequent when multiple tabs of the same page are running at the same time and this is a common use case for a web user.

Comment 12

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Jan Varga [:janv] from comment #8)
> Well, if there's no better way ... Kyle should know this code very well. I
> remember he implemented these hash tables to fix some performance problems.

This was done in bug 1131766 by Ben Turner instead according to the HG log.

NI Ben for more background on this to see if simplify |mBlocking| to a plain array suggested in comment 3 is a good choice or we should keep the hashtable with additional array to remember the blocking order as explained in comment 5 instead.

Comment 13

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Bevis Tseng[:bevistseng][:btseng] from comment #12)
> (In reply to Jan Varga [:janv] from comment #8)
> > Well, if there's no better way ... Kyle should know this code very well. I
> > remember he implemented these hash tables to fix some performance problems.
> 
> This was done in bug 1131766 by Ben Turner instead according to the HG log.
> 
> NI Ben for more background on this to see if simplify |mBlocking| to a plain
> array suggested in comment 3 is a good choice or we should keep the
> hashtable with additional array to remember the blocking order as explained
> in comment 5 instead.

Sorry, my bad.

The original one was done by Kyle in bug 776800 instead and there is a test page to identify the performance of this change in bug 776800 comment 0:
http://people.mozilla.com/~jmuizelaar/indexeddb/full-text-search/fts.html

I can do the same comparison on this test page to see hashtable does improve this problem.

Comment 14

[Ben Turner (not reading bugmail, use the needinfo flag!)]

Yeah, please keep the hash tables. Using arrays it was very easy to cause performance problems.

Comment 15

[Jan Varga [:janv]]

Sure, but this patch doubles memory footprint for mBlocking, I know it's not that much, maybe 8KB for 1 thousand transactions on 64 bit platform. Java has LinkedHashMap for this case. Not sure if we have something like that in gecko.

Comment 16

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Jan Varga [:janv] from comment #15)
> Sure, but this patch doubles memory footprint for mBlocking, I know it's not
> that much, maybe 8KB for 1 thousand transactions on 64 bit platform. Java
> has LinkedHashMap for this case. Not sure if we have something like that in
> gecko.

Yes, I was looking for the same thing in gecko but haven't found something similar yet. :(

Comment 17

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Bevis Tseng[:bevistseng][:btseng] from comment #16)
> (In reply to Jan Varga [:janv] from comment #15)
> > Sure, but this patch doubles memory footprint for mBlocking, I know it's not
> > that much, maybe 8KB for 1 thousand transactions on 64 bit platform. Java
> > has LinkedHashMap for this case. Not sure if we have something like that in
> > gecko.
> 
> Yes, I was looking for the same thing in gecko but haven't found something
> similar yet. :(

Nevertheless, extra memory is still required for a HashMap to provide different accesses of searching and iterating. :(

Comment 18

[Ben Kelly [:bkelly, not reviewing]]

> Java has LinkedHashMap for this case.

You can probably effectively build one by using LinkedList.  It seems you can make your hashtable values implement LinkedListElement.

Comment 19

[Jan Varga [:janv]]

Yeah, it seems dom/animation/Animation.h uses it
And AnimationTimeline.h contains this comment:
// Animations observing this timeline
//
// We store them in (a) a hashset for quick lookup, and (b) an array
// to maintain a fixed sampling order.

They used an array first, bug 1195180 and then switched to a linked list, bug 1223445
But I think they switched to a linked list to make removing an element fast.
We don't need that AFAIK.

Comment 20

[Jan Varga [:janv]]

Ok, Bevis, do you think you can make the class a bit more generic ?
It seems this can be reused in other parts of gecko in future.
However, for now I would keep it only in IDB. A real generic class would take much more time.

What about something like this:
template<class EntryType>
class OrderedHashtable : public nsTHashtable<EntryType>
{
  ...
}

Comment 21

[Jan Varga [:janv]]

Comment on attachment 8784317 [details] [diff] [review]
(v1) Patch: Iterate the Blocked Transactions in the first-come, first-served order.

Review of attachment 8784317 [details] [diff] [review]:
-----------------------------------------------------------------

Ok, we talked about this a bit. I'm ok with the approach of this patch, but I would enhance the new class a bit to be more generic.
We might want to use the class elsewhere too.

Comment 22

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Jan Varga [:janv] from comment #21)
> Ok, we talked about this a bit. I'm ok with the approach of this patch, but
> I would enhance the new class a bit to be more generic.
> We might want to use the class elsewhere too.

While writing my WIP by refering the definition in nsTHashTable, I found that the one we used originally is named:
"
template<typename T>
class nsTHashtable<nsPtrHashKey<T>> : protected nsTHashtable<::detail::VoidPtrHashKey>
"

To align with original approach with new template, it seems that I've to define OrderedHashtable from nsTHashTable and define OrderHashtable<nsPtrHashKey<T>> inherit from OrderHashtable.

Is this the correct approach for this fix?

Or, there are 2 simpler versions I've done so far and both are workable:
1. Define OrderedHashtable as followed and let nsPtrHashKey<TransactionInfo> as the EntryType:
"
template<class EntryType>
class OrderedHashtable : public nsTHashtable<EntryType>
"
2. Define OrderHashtable as followed and let TransactionInfo as the T:
"
template<typename T>
class OrderedHashtable : public nsTHashtable<nsPtrHashKey<T>>
"

However, I am not pretty sure what should I provide in this stage to have first version of OrderedHashtable... :\

May I have some input from you to finalize this?

Comment 23

[Jan Varga [:janv]]

template<class EntryType>
class nsTOrderedHashtable
  : public nsTHashtable<EntryType>
{
  typedef typename EntryType::KeyType KeyType;
  typedef typename EntryType::KeyTypePointer KeyTypePointer;
  typedef nsTHashtable<EntryType> base_type;

  nsTArray<KeyTypePointer> mArray;

public:
  EntryType*
  PutEntry(KeyType aKey)
  {
    return base_type::PutEntry(aKey);
  }
};

Comment 24

[Jan Varga [:janv]]

I think the specialization of nsTHashtable for nsPtrHashKey should just work, no ?

Comment 25

[Jan Varga [:janv]]

Attachment: WIP

Feel free to take and finish this patch, I won't be available till Wednesday.

Comment 26

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Jan Varga [:janv] from comment #24)
> I think the specialization of nsTHashtable for nsPtrHashKey should just
> work, no ?

Yes, it worked with my WIP already which is quite similar to yours. :)
In comment 22, I just wondered if I should follow the design in nsTHashtable to have a specialized template for nsPrtHashKey but it looks not necessary now, since we have the same consciousness.
Thanks for the WIP, BTW.
I should upload mine yesterday when setting the ni flag to save your time on this. :|

I'll finalize both WIPs for the review next week.

Have a safe flight! :)

Comment 27

[Bevis Tseng[:bevis][:btseng](Exited)]

Attachment: (v3) Iterate the blocked transactions in the first-come, first-served order.

Unfortunately, inheriting from nsTHashtable in patch(v2) creates some ambiguous problems to the specialized template of nsTHashtable<nsPtrHashKey<T>> in windows build:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=40f0484b5d1c&selectedJob=26498743

In addition, all APIs in nsTHashtable are non-virtual which makes no sense to override them to prevent abusing.

Hence, I'd like to rewrite OrderedHashtable from nsTHashtable and only implement the APIs that are supported in current stage, i.e., GetEntry()/PutEntry()/ConstIter() and moving them to a standalone header for better visibility to other people who need this.

In addition, the future plan of the generic one is also explained in this new header for reference.

Comment 28

[Bevis Tseng[:bevis][:btseng](Exited)]

update treeherder result for reference:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=6042e23af02c

Comment 29

[Jan Varga [:janv]]

Comment on attachment 8786288 [details] [diff] [review]
(v3) Iterate the blocked transactions in the first-come, first-served order.

Review of attachment 8786288 [details] [diff] [review]:
-----------------------------------------------------------------

This is a bit out of scope of this bug, but if we want to use this new class in future to provide ordered behavior for all derived hash tables (for example nsClassHashtable), how would that work ?

I guess Nathan Froyd and Nicholas Nethercote could express some opinions here.

Comment 30

[Bevis Tseng[:bevis][:btseng](Exited)]

(In reply to Jan Varga [:janv] from comment #29)
> Comment on attachment 8786288 [details] [diff] [review]
> (v3) Iterate the blocked transactions in the first-come, first-served order.
> 
> Review of attachment 8786288 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> This is a bit out of scope of this bug, but if we want to use this new class
> in future to provide ordered behavior for all derived hash tables (for
> example nsClassHashtable), how would that work ?
> 
The worst case is to have similar template hierarchy of nsClassHashtable -> nsBaseHashtable -> nsTHashtable for all the ordered hashtables.

It will be easier if we could toggle the need of the insertion order by some mechanism like ALLOW_MEMMOVE in nsTHashtable to hook the linked list elements in PLDHashEntryHdr for ordering.
> I guess Nathan Froyd and Nicholas Nethercote could express some opinions
> here.

Hi Nathan,

In the patch of comment 29, I've created a very simple version of OrderedHashtable without the support of removing operation by remembering the order with nsTArray.
This is only sufficient for this bug.

If I'd like to make this a more generic ordered nsHashtable to mtbf/ that supports the insertion order as explained in OrderedHashtable.h in comment 29, do you have any suggestion of how to implement this for easier extensions of ordered versions of nsClassHashtable, nsDataHashtable, etc?

Comment 31

[Nathan Froyd [:froydnj]]

(In reply to Bevis Tseng[:bevistseng][:btseng] from comment #30)
> If I'd like to make this a more generic ordered nsHashtable to mtbf/ that
> supports the insertion order as explained in OrderedHashtable.h in comment
> 29, do you have any suggestion of how to implement this for easier
> extensions of ordered versions of nsClassHashtable, nsDataHashtable, etc?

Generalizing this is hard, because all of our hashtables don't have consistent interfaces.  I think insertion-ordered hashtables would be a useful abstraction to have, but I don't think we're currently set up to do anything about it. :(

Comment 32

[Bevis Tseng[:bevis][:btseng](Exited)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=e1955662dba0

Comment 33

[Bevis Tseng[:bevis][:btseng](Exited)]

Attachment: (v4) Patch: Iterate the blocked transactions in the first-come, first-served order.

Since creating a generic OrderedHashtable doesn't make much sense according to comment 31 and the inheritance from nsTHashtable is problematic as mentioned in comment 27,
I'd like to provide the trivial one by revising the v1 patch with iterator provided.

Comment 34

[Bevis Tseng[:bevis][:btseng](Exited)]

treeherder result for reference:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=00073ca82435

Comment 35

[Jan Varga [:janv]]

Comment on attachment 8790987 [details] [diff] [review]
(v4) Patch: Iterate the blocked transactions in the first-come, first-served order.

Review of attachment 8790987 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/indexedDB/ActorsParent.cpp
@@ +5716,5 @@
>  struct ConnectionPool::TransactionInfo final
>  {
>    friend class nsAutoPtr<TransactionInfo>;
>  
> +  class BlockingTransactionTable final

It would be better to just declare the class here and move the definition after this struct, but obviously that's not possible in this case.
However, since we basically gave up on creating generic/semi-generic ordered hashtable, I think we don't need to create any new classes.

I refactored the code a bit to safely use the hash table and the array at the same time. It also makes the code a bit more readable.

Comment 36

[Jan Varga [:janv]]

Attachment: patch

Comment 37

[Bevis Tseng[:bevis][:btseng](Exited)]

Comment on attachment 8794717 [details] [diff] [review]
patch

Review of attachment 8794717 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks, this is simpler and more readable.
Shall this bug be reassigned to you to respect the change you've made? :D

Comment 38

[Bevis Tseng[:bevis][:btseng](Exited)]

Attachment: (v5) Patch: Iterate the blocked transactions in the first-come, first-served order. r=btseng

Revised to formal patch with updated author and reviewer.

wait for treeherder result for checkin:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=09bb0e217dc3

Comment 39

[Bevis Tseng[:bevis][:btseng](Exited)]

Since the major change of the final patch is provided by :janv instead of me, I'd like to update the assignee to reflect the situation. :)

Set checkin-needed because treeherder result in comment 38 looks fine.

Comment 40

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/58fc35829a49
Iterate the blocked transactions in the first-come, first-served order. r=btseng

Comment 41

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/58fc35829a49