1299147 - Assertion failure: !cycleEnd_, at js/src/jit/MoveResolver.h:278

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect, P3)

Description

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

The following testcase crashes on mozilla-central revision 4f72b1d05267 (build with --enable-debug --enable-more-deterministic --32 --enable-simulator=arm, run with --fuzzing-safe --no-threads --ion-eager):

function g(f) {
    try {
        f()
    } catch (e) {}
    f()
}
function f0() {}
function f1(x, y) {
    return (f0(y ? x : x > 0), x % 7 < 0 | Math.round(Math.atan2(y + x, x | 0)))
}
function f2(x, y) f1(Math.fround(+y), Math.fround(x))
g(f2)
f1 = function(x, y) x(Math.max(Math.fround(y >> 0), Math.fround(x)))(x ? x | 0 : x)
function f3(x) f2(x >> 0)
g(f3)


Backtrace:

0   js-dbg-32-dm-clang-armSim-darwin-4f72b1d05267	0x00511baf js::jit::MoveResolver::resolve() + 1007 (MoveResolver.h:278)
1   js-dbg-32-dm-clang-armSim-darwin-4f72b1d05267	0x003325a9 js::jit::CodeGenerator::visitMoveGroup(js::jit::LMoveGroup*) + 281 (Assembler-shared.h:741)
2   js-dbg-32-dm-clang-armSim-darwin-4f72b1d05267	0x004c0e47 js::jit::LMoveGroup::accept(js::jit::LElementVisitor*) + 87 (LIR-shared.h:116)
3   js-dbg-32-dm-clang-armSim-darwin-4f72b1d05267	0x003429e8 js::jit::CodeGenerator::generateBody() + 1736 (LIR.h:752)
4   js-dbg-32-dm-clang-armSim-darwin-4f72b1d05267	0x003620b4 js::jit::CodeGenerator::generate() + 516 (CodeGenerator.cpp:9147)
/snip

For detailed crash information, see attachment.

Comment 1

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Attachment: Detailed Crash Information

Comment 2

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   https://hg.mozilla.org/mozilla-central/rev/86019126140c
user:        Nicolas B. Pierron
date:        Wed Mar 23 19:03:40 2016 +0000
summary:     Bug 1258748 - adjustPhiInputs: Add MBox in the predecessor block instead of the definition block. r=jolesen

Nicolas, is bug 1258748 a likely regressor?

Comment 3

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Nicolas/Hannes/Jan, can someone please look at this? I spent lots of time distinguishing this from bug 1337967, it would have been nice to at least have a patch here to see if they are related.

Comment 4

[Hannes Verschore [:h4writer]]

Taking a look.

Comment 5

[Hannes Verschore [:h4writer]]

Attachment: MoveResolver tests

Two ways to get the MoveResolver/Emitter confused on ARM. I wouldn't be surprised if there are more. The MoveResolver doesn't understand enough about aliased registers.

Comment 7

[Hannes Verschore [:h4writer]]

Interestingly it might just do the right thing (unexpectedly).

The issue is that d0 can create a cycle with s0 and another with s1.
But we can only keep track of one cycle in the MoveResolver. That is the reason we are asserting here.

s2 -> s0
s3 -> s1
d0 -> d1

s0 needs to be saved when executing d0
s1 also needs to be saved when executing d0

By saving the cycle we save the out param to the stack for use lateron.
Here we keep only one cycle. (I.e. this has to be wrong).

But there is an invariant in the MoveEmitter that always saves the double overlay for floats.
I.e. - if the cycle with s0 wins, we save double overlay of s0 -> we save d0
     - if the cycle with s1 wins, we save double overlay of s1 -> we save d0

As a result unexpectedly we have all information to eventually do the d0 -> d1 move afterwards.

Comment 8

[Jan de Mooij [:jandem]]

smvv is working on the same or a similar bug, so adding him to the CC list.

Comment 9

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Also cc'ing Sean, our ARM guru.

Comment 10

[Andrew McCreight [:mccr8]]

How bad of a security issue is this? Could it result in memory corruption or what?

Comment 11

[Hannes Verschore [:h4writer]]

(In reply to Andrew McCreight [:mccr8] from comment #10)
> How bad of a security issue is this? Could it result in memory corruption or
> what?

(In reply to Hannes Verschore [:h4writer] from comment #7)
> But there is an invariant in the MoveEmitter that always saves the double
> overlay for floats.
> I.e. - if the cycle with s0 wins, we save double overlay of s0 -> we save d0
>      - if the cycle with s1 wins, we save double overlay of s1 -> we save d0
> 
> As a result unexpectedly we have all information to eventually do the d0 ->
> d1 move afterwards.

Given this, we have no security issue here. By accident (or cleverly engineered by the person creating this) this just works. In the long term we might want to find a way to clean this up.

Comment 12

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

I realise that this is causing lots of mismatch on stdout errors for compareJIT, so setting [fuzzblocker]. Jan, is there any way we can move this forward?

Comment 13

[Jan de Mooij [:jandem]]

Sean, since this is ARM, maybe you have some cycles (no pun intended) to look into this?

Comment 14

[Sean Stangl [:sstangl]]

It doesn't reproduce anymore, but the testcase in Comment 5 is sufficient. I'll take a look.

Comment 15

[Sean Stangl [:sstangl]]

(In reply to Hannes Verschore [:h4writer] from comment #11)
> Given this, we have no security issue here. By accident (or cleverly
> engineered by the person creating this) this just works. In the long term we
> might want to find a way to clean this up.

Good or bad, this appears to be the intended behavior, as evidenced by this comment:

http://searchfox.org/mozilla-central/source/js/src/jit/arm/MoveEmitter-arm.cpp#375

It doesn't look like the case where an aliased D register is the end of two cycles was considered, though. The first testcase in Comment 5 produces an incorrect assignation without crashing.

Comment 16

[Sean Stangl [:sstangl]]

Attachment: 0001-Bug-1299147-Split-double-MoveOperands-that-conflict-.patch

Based on the code, I'm not convinced that this is not a security issue. It may be possible from moves between doubles and memory to be corrupted by an intermediary float MoveOp. Just to be safe, I'm treating this bug as if it were a security issue.

The resolve() algorithm has a hard assumption that each MoveOperand can participate in at most one cycle. Removing this assumption and fixing the algorithm is a lot of work, since each platform implements its own breakCycle() handler that would also have to be fixed. So I decided not to fix the algorithm for this bug.

On ARMv7, there are 32 double registers. The lower 16 alias the 32 single-point registers. For the moment and for the foreseeable future, our implementation does not make use of the upper 16 double registers, and every double register can alias.

Because we only use aliased double registers, every PendingMove involving a double register can be split into halves, one for the lower 32 bits, and one for the upper 32 bits. If we split double moves into these halves, then the algorithm will work as currently implemented, since each half can be part of at most one cycle.

The attached patch implements this behavior in resolve(). It first checks for any double registers that conflict, and the ones that alias any float register are split.

The test cases that Hannes identified finally pass:

> TEST-PASS | testJitMoveEmitterCycles_bug1299147 | ok
> TEST-PASS | testJitMoveEmitterCycles_bug1299147_1 | ok

I didn't bother optimizing this algorithm since there are usually no more than 5 MoveOps, the most being 12, all of which run negligibly fast.

Comment 17

[Gary Kwong [:gkw] [:nth10sd] (NOT official MoCo now)]

Locking s-s because of comment 16 (treating this bug as if it were a security issue), and also because duplicate bug 1337967 is also s-s.

Comment 18

[Sean Stangl [:sstangl]]

There is a subtlety that I forgot to point out, consider the following:

> (d2, d3)
> (d0, d2)
> (s0, s1)

That will get split into the following:

> (d2, d3)
> (s0, s4)
> (s1, s5)
> (s0, s1)

The lower half of d2 is s4, which exists as a single-float move, but the splitting loop only iterates once, and so it won't pick up that d2 has been split elsewhere. I think this is safe because the only way for a MoveOp to participate in two independent cycles is for it to have had single-point references already, which would have caused it to be split. Aliasing logic will still order the moves correctly.

Comment 19

[Jan de Mooij [:jandem]]

Comment on attachment 8865019 [details] [diff] [review]
0001-Bug-1299147-Split-double-MoveOperands-that-conflict-.patch

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

Nice idea. Thanks for fixing!

::: js/src/jit/MoveResolver.cpp
@@ +106,5 @@
>      return nullptr;
>  }
>  
> +#ifdef JS_CODEGEN_ARM
> +static inline bool 

Nit: trailing whitespace

Comment 20

[Sean Stangl [:sstangl]]

Looks green on Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=4eae845149f16d25090d860927ae563045afa342

Comment 21

[Sean Stangl [:sstangl]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/8178250f3a8b58fbb48f31b0095de2c0d2af802a

Comment 23

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/8178250f3a8b

Please request Beta approval on this when you get a chance. I don't think we need this on ESR52 since it's ARM-only (unless some distro ships Desktop ARM Firefox builds).

Comment 24

[Sean Stangl [:sstangl]]

Comment on attachment 8865019 [details] [diff] [review]
0001-Bug-1299147-Split-double-MoveOperands-that-conflict-.patch

Approval Request Comment
[Feature/Bug causing the regression]: Long-standing, but some unknown change recently may have made the underlying bug more likely to occur, based on Bug 1364244 appearing in the wild.
[User impact if declined]: ARM crashes, misbehavior, or silent corruption.
[Is this code covered by automated tests?]: Yes, attached in the patch.
[Has the fix been verified in Nightly?]: Yes.
[Needs manual test from QE? If yes, steps to reproduce]: No.
[List of other uplifts needed for the feature/fix]: ()
[Is the change risky?]: No.
[Why is the change risky/not risky?]: It's a small algorithmic change, and the code was written to be as simple as possible.
[String changes made/needed]: None.

Note that the patch pushed differs slightly from the one attached in this bug (pre-review); the version that was actually pushed should be uplifted. There shouldn't be any conflicts.

Comment 26

[Gerry Chang [:gchang]]

Comment on attachment 8865019 [details] [diff] [review]
0001-Bug-1299147-Split-double-MoveOperands-that-conflict-.patch

Avoid ARM crashes and fix an assertion failure. Beta54+. Should be in 54 beta 9.

Comment 27

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-beta/rev/adb9ebd81ba2