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

RESOLVED FIXED in Firefox 52

Status

()

Core
DOM: IndexedDB
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: jgraham, Assigned: janv)

Tracking

(Blocks: 1 bug)

unspecified
mozilla52
Points:
---

Firefox Tracking Flags

(firefox52 fixed)

Details

Attachments

(1 attachment, 5 obsolete attachments)

(Reporter)

Description

2 years ago
Going to disable for now.
No longer blocks: 1178829
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.
Assignee: nobody → btseng
Component: web-platform-tests → DOM: IndexedDB
Product: Testing → Core
Created attachment 8784317 [details] [diff] [review]
(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
Attachment #8784317 - Flags: review?(jvarga)
(Assignee)

Comment 3

2 years ago
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 ?
(Assignee)

Comment 4

2 years ago
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.
(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
(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
(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. :)
(Assignee)

Comment 8

2 years ago
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.
Never mind. Let's ping him. :)
(Assignee)

Comment 10

2 years ago
You can also try to find, how often the redundant entry case happens.
(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.
(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.
Flags: needinfo?(bent.mozilla)
(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.
Flags: needinfo?(bent.mozilla)
Yeah, please keep the hash tables. Using arrays it was very easy to cause performance problems.
(Assignee)

Comment 15

2 years ago
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.
(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. :(
(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. :(
> 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.
(Assignee)

Comment 19

2 years ago
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.
(Assignee)

Comment 20

2 years ago
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>
{
  ...
}
(Assignee)

Comment 21

2 years ago
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.
Attachment #8784317 - Flags: review?(jvarga)
(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?
Flags: needinfo?(jvarga)
(Assignee)

Comment 23

2 years ago
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);
  }
};
Flags: needinfo?(jvarga)
(Assignee)

Comment 24

2 years ago
I think the specialization of nsTHashtable for nsPtrHashKey should just work, no ?
(Assignee)

Comment 25

2 years ago
Created attachment 8785565 [details] [diff] [review]
WIP

Feel free to take and finish this patch, I won't be available till Wednesday.
(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! :)
Created attachment 8786288 [details] [diff] [review]
(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.
Attachment #8784317 - Attachment is obsolete: true
Attachment #8785565 - Attachment is obsolete: true
Attachment #8786288 - Flags: review?(jvarga)
(Assignee)

Comment 29

2 years ago
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.
Attachment #8786288 - Flags: review?(jvarga)
(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?
Flags: needinfo?(nfroyd)
(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. :(
Flags: needinfo?(nfroyd)
Created attachment 8790987 [details] [diff] [review]
(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.
Attachment #8786288 - Attachment is obsolete: true
Attachment #8790987 - Flags: review?(jvarga)
(Assignee)

Comment 35

2 years ago
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.
Attachment #8790987 - Flags: review?(jvarga)
(Assignee)

Comment 36

2 years ago
Created attachment 8794717 [details] [diff] [review]
patch
Attachment #8794717 - Flags: review?(btseng)
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
Attachment #8794717 - Flags: review?(btseng) → review+
Created attachment 8794767 [details] [diff] [review]
(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
Attachment #8790987 - Attachment is obsolete: true
Attachment #8794717 - Attachment is obsolete: true
Attachment #8794767 - Flags: review+
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.
Assignee: btseng → jvarga
Keywords: checkin-needed

Comment 40

2 years ago
Pushed by cbook@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/58fc35829a49
Iterate the blocked transactions in the first-come, first-served order. r=btseng
Keywords: checkin-needed

Comment 41

2 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/58fc35829a49
Status: NEW → RESOLVED
Last Resolved: 2 years ago
status-firefox52: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla52
You need to log in before you can comment on or make changes to this bug.