1118894 - Assertion failure: pred->isLoopBackedge(), at js/src/jit/IonAnalysis.cpp:1962

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

The following testcase crashes on mozilla-central revision 33781a3a5201 (build with --enable-optimize --enable-posix-nspr-emulation --enable-valgrind --enable-gczeal --target=i686-pc-linux-gnu --enable-debug, run with --fuzzing-safe --thread-count=2):

testcase()
function testcase() {
  var tokenCodes  = {};
  tokenCodes['const'] = 0;
  var arr = ['const'];
  for (var p in tokenCodes) {       
      for (var p1 in arr) {                
          if (arr[p1] === p) {
            var p1 = 100 * 1000;
            for (var arr = 0; arr != p1; ++arr) {}
          }
      }
  }
}



Backtrace:

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xf7887b40 (LWP 16214)]
0x0838200d in AssertReversePostorder (graph=...) at js/src/jit/IonAnalysis.cpp:1962
1962	                MOZ_ASSERT(pred->isLoopBackedge());
#0  0x0838200d in AssertReversePostorder (graph=...) at js/src/jit/IonAnalysis.cpp:1962
#1  0x083821e0 in AssertGraphCoherency (graph=...) at js/src/jit/IonAnalysis.cpp:2034
#2  AssertGraphCoherency (graph=...) at js/src/jit/IonAnalysis.cpp:2111
#3  js::jit::AssertExtendedGraphCoherency (graph=...) at js/src/jit/IonAnalysis.cpp:2121
#4  0x083d55d1 in js::jit::OptimizeMIR (mir=0x973f030) at js/src/jit/Ion.cpp:1567
#5  0x083d5b66 in js::jit::CompileBackEnd (mir=0x973f030) at js/src/jit/Ion.cpp:1727
#6  0x086c0ea5 in js::HelperThread::handleIonWorkload (this=0x9674480) at js/src/vm/HelperThreads.cpp:1084
#7  0x086c25c9 in js::HelperThread::threadLoop (this=0x9674480) at js/src/vm/HelperThreads.cpp:1380
#8  0x0873ae35 in nspr::Thread::ThreadRoutine (arg=0x9673168) at js/src/vm/PosixNSPR.cpp:45
#9  0xf7fb8d4c in start_thread () from /lib/i386-linux-gnu/libpthread.so.0
#10 0xf7dacdde in clone () from /lib/i386-linux-gnu/libc.so.6
eax	0x0	0
ebx	0x963aff4	157528052
ecx	0xf7e648ac	-135903060
edx	0x0	0
esi	0x1	1
edi	0x9750cf8	158665976
ebp	0xf7886e98	4152913560
esp	0xf7886e60	4152913504
eip	0x838200d <AssertReversePostorder(js::jit::MIRGraph&)+157>
=> 0x838200d <AssertReversePostorder(js::jit::MIRGraph&)+157>:	movl   $0x7b,0x0
   0x8382017 <AssertReversePostorder(js::jit::MIRGraph&)+167>:	call   0x804a9d0 <abort@plt>

Comment 1

[Christian Holler (:decoder)]

JSBugMon: Bisection requested, result:
autoBisect shows this is probably related to the following changeset:

The first bad revision is:
changeset:   https://hg.mozilla.org/mozilla-central/rev/f8e5c5ed14cb
user:        Jan de Mooij
date:        Sat Dec 27 13:55:06 2014 +0100
summary:     Bug 1114574 - Refactor and improve MCompare::tryFold. r=h4writer

This iteration took 584.079 seconds to run.

Comment 2

[Christian Holler (:decoder)]

Needinfo from jandem based on comment 1.

Comment 3

[Jan de Mooij [:jandem]]

I think bug 1114574 exposed an existing bug in the MakeLoopsContiguous pass. We can now probably fold the if-condition, but I'm pretty sure it was possible to trigger this before that.

Comment 4

[Jan de Mooij [:jandem]]

Simpler testcase:

function f() {
    var arr = ["c"];
    for (var i=0; i<1; i++) {
        if (arr[0] === "c") {
	    for (var j=0; j<100000; j++) {};
        }
    }
}
f();

What's happening is probably that we don't have good type information for arr[0] because it runs in the interpreter initially, and the arr[0] === "c" is folded to false, and this confuses MakeLoopsContiguous.

Comment 5

[Dan Gohman [:sunfish]]

As mentioned in bug 1096255, it's possible that this is the same as that bug.

Restricting access to this bug out of caution. The consequence of this bug is that Ion's CFG may not satisfy RPO invariants, which a bunch of things depend on, however I haven't investigated the specifics of what could happen yet.

Comment 6

[Dan Gohman [:sunfish]]

Attachment: osr-entry-to-former-loop-blocks.patch

See the comment in the patch for an explanation of what's going on here.

Comment 7

[Jan de Mooij [:jandem]]

Comment on attachment 8546325 [details] [diff] [review]
osr-entry-to-former-loop-blocks.patch

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

::: js/src/jit/IonAnalysis.cpp
@@ +3482,5 @@
>      // Visit all the blocks from the loop header to the loop backedge.
>      size_t headerId = header->id();
>      size_t inLoopId = headerId;
>      size_t notInLoopId = inLoopId + numMarked;
> +    size_t numOSRDominated = 0;

Nit: this could be DebugOnly<size_t>, I think. May have to change ++numOSRDominated to numOSRDominated++ because it looks like DebugOnly overloads the postfix one but not the prefix one.

Comment 9

[Dan Gohman [:sunfish]]

Comment on attachment 8546325 [details] [diff] [review]
osr-entry-to-former-loop-blocks.patch

[Security approval request comment]
How easily could an exploit be constructed based on the patch?

Not easy. It would require some amount of compiler knowledge to figure out the conditions needed to actually exploit this, if it is actually exploitable.

Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem?

Comments in the patch describe how to get an assertion failure, however not to actually get an exploitable crash.

Which older supported branches are affected by this flaw?

mozilla32 and later; mozilla-release, mozilla-beta, mozilla-aurora, and mozilla-central, but not esr31.

If not all supported branches, which bug introduced the flaw?

Bug 844779.

Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be?

Backports would be easy to create, and low-risk.

How likely is this patch to cause regressions; how much testing does it need?

Unlikely. The change is pretty simple and is just disabling an optimization.

Comment 10

[Al Billings [:abillings - ex-MoCo]]

Sec-approval+ for checkin on January 26 (or later). We'll want it on Aurora and Beta after that too.

Comment 11

[Christian Holler (:decoder)]

JSBugMon: The testcase found in this bug no longer reproduces (tried revision c1f6345f2803).

Comment 12

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/946d72dae3df

Comment 13

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/946d72dae3df

Comment 14

[Christian Holler (:decoder)]

JSBugMon: This bug has been automatically verified fixed.

Comment 15

[Ryan VanderMeulen [:RyanVM]]

Whoops, forgot to ni? for Aurora/Beta approval requests :)

Comment 16

[Dan Gohman [:sunfish]]

This patch is currently under suspicion of causing bug 1125734. I'm investigating that now.

Comment 17

[Dan Gohman [:sunfish]]

Confirmed that the patch here causes bug 1125734. I've now posted patches there, including for mozilla-aurora and mozilla-beta, for sec-review which subsumes the patch here.