hang in js::jit::AssertBasicGraphCoherency on google maps

RESOLVED FIXED in mozilla36

Status

()

RESOLVED FIXED
4 years ago
4 years ago

People

(Reporter: dbaron, Assigned: nbp)

Tracking

unspecified
mozilla36
x86_64
Linux
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(URL)

Attachments

(4 attachments)

Created attachment 8507191 [details]
gdb session

I just went to Google Maps in a debug build and ended up hanging in js::jit::AssertBasicGraphCoherency.  I gave it a few minutes to resolve -- it sure seems like an infinite loop.

https://www.google.com/maps/preview

See attached gdb session.  I can debug more if you're quick.
Can you determine which loop it's in? Any line number in IonAnalysis.cpp ought to be enough to be interesting.
Also, the output of running 'p graph.dump()' in gdb when inside AssertBasicGraphCoherency could be useful, if you still have it up.
Ah, in the gdb session it's apparently stuck in the loop at lines 1832-1841.

        for (MResumePointIterator iter(block->resumePointsBegin()); iter != block->resumePointsEnd(); iter++) {

nbp, is it possible that the resumePoints_ list could have become circular?
Created attachment 8507230 [details]
output of graph.dump()
So a few days ago I let it run for longer and it finished after about 5 minutes, I think.  (I was looking at it in gdb during that time too, so I suppose there's a chance gdb changed something that allowed it to finish.)

But this basically makes it impossible to use google maps in a debug build.
(Note that steps to reproduce are, I think, either searching for a location or asking for directions between two locations.)
(Assignee)

Updated

4 years ago
Flags: needinfo?(nicolas.b.pierron)
(Assignee)

Comment 7

4 years ago
I can reproduce this issue, I do not think this is an infinite loop at all, this might only be that the predicate (CheckOperandImpliesUse) for the graph sanity has to iterates over half of 429560 uses to find one which has the right consumer.  So, our graph validation procedure has a complexity of O(n²) (≃ 92,260,896,800 iterations) which might be miss interpreted as an infinite loop.

I will look if I can invert the verification of this predicate, knowing that we are likely to be doing that already in some way.
Assignee: nobody → nicolas.b.pierron
Status: NEW → ASSIGNED
Flags: needinfo?(nicolas.b.pierron)
(Assignee)

Comment 8

4 years ago
Created attachment 8521419 [details] [diff] [review]
Ion/Odin: Reduce the complexity of the assertion of the graph coherency.

This patch removes the lookup of the corresponding MUse by counting the
number of time we visit the MUse.  These assertions will no longer catch the
symmetric aspect of the relation, but on the other hand, we will catch
assymetry about the number of uses / operands.
Attachment #8521419 - Flags: review?(sunfish)
Created attachment 8522589 [details] [diff] [review]
checking.patch

I like your patch, though I wonder if we shouldn't take it a step further. Attached is a patch which takes some of the ideas from your patch, but keeps a HashSet of the uses, so that we can do even more precise checking, and so that the crash will indicate where the problem is (no awk required! ;-)). This does require a second pass through the graph though. What do you think?
Attachment #8522589 - Flags: feedback?(nicolas.b.pierron)
(Assignee)

Comment 10

4 years ago
Comment on attachment 8522589 [details] [diff] [review]
checking.patch

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

I like the idea that we do not need external program reporting the wrong uses.  On the other hand, I am not convinced by that having extra allocations in debug mode is a good thing.

So I thought that I could use #ifdef as in the previous patch.

Do you want to make 2 different patches, one with the awk instrumentation as-is, and then you make a follow-up patch for replacing it by an HashSet / HashMap ?

::: js/src/jit/IonAnalysis.cpp
@@ +1818,5 @@
>  
>      if (MResumePoint *resumePoint = graph.entryResumePoint())
>          MOZ_ASSERT(resumePoint->block() == graph.entryBlock());
>  
> +    typedef HashSet<MUse *, DefaultHasher<MUse *>, IonAllocPolicy> UsesSet;

Use the SystemAllocPolicy for temporary data structure, otherwise add a new scope for the LifoAlloc of the IonAllocPolicy, in order to reclaim any allocations made by the HashSet.

@@ +1911,5 @@
> +
> +    // Now that we've populated the uses set with all the MUses in use lists of
> +    // definitions that we know are in the graph, check that every operand in
> +    // the graph is in that set.
> +    for (MBasicBlockIterator block(graph.begin()); block != graph.end(); ++block) {

We do not need 2 iterations if we use a HashMap and a counter, as it was done in the awk script.  In which case such instrumentation for adding / removing can be added inside CheckOperand / CheckUse.
Attachment #8522589 - Flags: feedback?(nicolas.b.pierron) → feedback+
Comment on attachment 8521419 [details] [diff] [review]
Ion/Odin: Reduce the complexity of the assertion of the graph coherency.

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

(In reply to Nicolas B. Pierron [:nbp] from comment #10)
> Do you want to make 2 different patches, one with the awk instrumentation
> as-is, and then you make a follow-up patch for replacing it by an HashSet /
> HashMap ?

That works for me. Let's proceed with your patch for now, and I'll submit a separate patch on top of it to use a hash set undef an #ifdef.

> ::: js/src/jit/IonAnalysis.cpp
> @@ +1818,5 @@
> >  
> >      if (MResumePoint *resumePoint = graph.entryResumePoint())
> >          MOZ_ASSERT(resumePoint->block() == graph.entryBlock());
> >  
> > +    typedef HashSet<MUse *, DefaultHasher<MUse *>, IonAllocPolicy> UsesSet;
> 
> Use the SystemAllocPolicy for temporary data structure, otherwise add a new
> scope for the LifoAlloc of the IonAllocPolicy, in order to reclaim any
> allocations made by the HashSet.

Ok, I updated my local copy of the patch to do this.
Attachment #8521419 - Flags: review?(sunfish) → review+
(Assignee)

Comment 13

4 years ago
(In reply to Nicolas B. Pierron [:nbp] from comment #12)
> https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=3342d2f61a26

There is no reason for this patch to create any rooting hazards.

https://hg.mozilla.org/integration/mozilla-inbound/rev/24a68796eb6e
https://hg.mozilla.org/mozilla-central/rev/24a68796eb6e
Status: ASSIGNED → RESOLVED
Last Resolved: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla36
You need to log in before you can comment on or make changes to this bug.