1106171 - Assertion failure: live->empty(), at js/src/jit/LiveRangeAllocator.cpp:938 or Crash on Heap

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect)

Description

[Christian Holler (:decoder)]

The following testcase crashes on mozilla-central revision d103d1908a34 (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):

function f(a, b) {
    do {
        a--;
    } while (3 || this ? {} : getter = "return");
}
f(2000, 0);



Backtrace:

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xf7a1fb40 (LWP 7715)]
0x083f33bd in js::jit::LiveRangeAllocator<js::jit::LinearScanVirtualRegister, true>::buildLivenessInfo (this=this@entry=0xf7a1efc4) at js/src/jit/LiveRangeAllocator.cpp:938
938	        MOZ_ASSERT_IF(!mblock->numPredecessors(), live->empty());
#0  0x083f33bd in js::jit::LiveRangeAllocator<js::jit::LinearScanVirtualRegister, true>::buildLivenessInfo (this=this@entry=0xf7a1efc4) at js/src/jit/LiveRangeAllocator.cpp:938
#1  0x083b1125 in js::jit::LinearScanAllocator::go (this=this@entry=0xf7a1efc4) at js/src/jit/LinearScan.cpp:1288
#2  0x083b20c4 in js::jit::GenerateLIR (mir=mir@entry=0x96c1908) at js/src/jit/Ion.cpp:1634
#3  0x083b42dd in js::jit::CompileBackEnd (mir=0x96c1908) at js/src/jit/Ion.cpp:1722
#4  0x086445c4 in js::HelperThread::handleIonWorkload (this=this@entry=0x95f51c0) at js/src/vm/HelperThreads.cpp:1063
#5  0x086457da in js::HelperThread::threadLoop (this=0x95f51c0) at js/src/vm/HelperThreads.cpp:1361
#6  0x086b80e1 in nspr::Thread::ThreadRoutine (arg=0x95f9818) at js/src/vm/PosixNSPR.cpp:45
#7  0xf7fb0f70 in start_thread (arg=0xf7a1fb40) at pthread_create.c:312
#8  0xf7d944ce in clone () at ../sysdeps/unix/sysv/linux/i386/clone.S:129
eax	0x0	0
ebx	0x95bcff4	157011956
ecx	0xf7e5588c	-135964532
edx	0x0	0
esi	0x0	0
edi	0x0	0
ebp	0xf7a1ec38	4154584120
esp	0xf7a1eb30	4154583856
eip	0x83f33bd <js::jit::LiveRangeAllocator<js::jit::LinearScanVirtualRegister, true>::buildLivenessInfo()+5741>
=> 0x83f33bd <js::jit::LiveRangeAllocator<js::jit::LinearScanVirtualRegister, true>::buildLivenessInfo()+5741>:	movl   $0x7b,0x0
   0x83f33c7 <js::jit::LiveRangeAllocator<js::jit::LinearScanVirtualRegister, true>::buildLivenessInfo()+5751>:	call   0x804a990 <abort@plt>

Opt-trace:

Program received signal SIGSEGV, Segmentation fault.
0xf798f181 in ?? ()
[...]
#11 0x00000000 in ?? ()
eax	0xffffd008	-12280
ebx	0x8504478b	-2063317109
ecx	0xffffff82	-126
edx	0x0	0
esi	0x0	0
edi	0xffffff82	-126
ebp	0xffffb27e	4294947454
esp	0xffffcf4c	4294954828
eip	0xf798f181	4153995649
=> 0xf798f181:	testl  $0x100000,0x4(%ebx)
   0xf798f188:	jne    0xf798f21a



Marking s-s and sec-high based on the crash.

Comment 1

[Jan de Mooij [:jandem]]

Great, this could be causing the Nightly crashes in bug 1105543. Let's wait for autoBisect...

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/9188c8b7962b
user:        Nicolas B. Pierron
date:        Mon Nov 24 16:11:32 2014 +0100
summary:     Bug 1093674 - IonMonkey: Add Sink for instruction which can be recovered on bailout. r=sunfish

Nicolas, is bug 1093674 a likely regressor?

Comment 3

[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/9188c8b7962b
user:        Nicolas B. Pierron
date:        Mon Nov 24 16:11:32 2014 +0100
summary:     Bug 1093674 - IonMonkey: Add Sink for instruction which can be recovered on bailout. r=sunfish

This iteration took 564.992 seconds to run.

Comment 4

[Jan de Mooij [:jandem]]

[Tracking Requested - why for this release]:
It's causing browser crashes in the wild (bug 1105543).

Comment 5

[Nicolas B. Pierron [:nbp]]

The problem is the following:

 - The fold test phase, add a new blocks which has multiple predecessors, and which does not have any resume points.
 - The Sink algorithm moves the instruction into the join block which does not have any resume point and has multiple predecessors.
 - The lowering copies its latest resume point in all successors which have no resume points.
 - The moved instruction need a Snapshot, build out of a resume point which is not a resume point of a valid join block (no bytecode associated)
 - The snapshot refers to a virtual register which only exists in one of the predecessors, which cause this error to be raised.

I will fix the Lowering, to not assign any resume point to such blocks, and prevent the Sink phase to sink instruction in blocks which have multiple predecessors and no resume point.

Comment 6

[Nicolas B. Pierron [:nbp]]

Attachment: Lowering should not copy resume points to join-blocks.

Comment 7

[Nicolas B. Pierron [:nbp]]

Attachment: Sink should not move instructions to resume-point-less join-blocks.

Comment 8

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8532007 [details] [diff] [review]
Lowering should not copy resume points to join-blocks.

Note, this patch does not fix this issue, but cause similar issues fail with a null-deref instead of giving a way to an attacker to read one register.

Comment 9

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8532007 [details] [diff] [review]
Lowering should not copy resume points to join-blocks.

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

At best this only give a way to read registers, giving up pointers into the engine.

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

The comments as well as the modifications are clear identifiers of the issue.

> Which older supported branches are affected by this flaw?

Aurora

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

Bug 1093674

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

The same patches should the same for aurora, inbound.

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

Short answer, not likely, as not many optimization can fail in such cases yet.
On the other hand, this patch makes the investigation of such issues easier, by refusing bad generated code sooner  It also avoid producing potentially exploitable bad behaviour.

Comment 10

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8532008 [details] [diff] [review]
Sink should not move instructions to resume-point-less join-blocks.

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

At best this only give a way to read registers, giving up pointers into the engine.

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

The comments as well as the modifications are clear identifiers of the issue.

> Which older supported branches are affected by this flaw?

Aurora

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

Bug 1093674

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

The same patches should the same for aurora, inbound.

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

Unlikely, it just prevent Sink optimization by checking for bad cases before doing any modifications.

Comment 11

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

Comment on attachment 8532007 [details] [diff] [review]
Lowering should not copy resume points to join-blocks.

Please prepare an aurora patch or request aurora approval as well.

Comment 12

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8532007 [details] [diff] [review]
Lowering should not copy resume points to join-blocks.

Approval Request Comment
[Feature/regressing bug #]:
Bug 1093674

[User impact if declined]:
Top Crasher (Bug 1105543)

[Describe test coverage new/current, TBPL]:
https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=9e97fe7b5084
(can be applied on top of aurora without any issue)

[Risks and why]:
This patch might highlight similar issues.

[String/UUID change made/needed]:
N/A

Comment 13

[Nicolas B. Pierron [:nbp]]

Comment on attachment 8532008 [details] [diff] [review]
Sink should not move instructions to resume-point-less join-blocks.

Approval Request Comment
[Feature/regressing bug #]:
Bug 1093674

[User impact if declined]:
Top Crasher (Bug 1105543)

[Describe test coverage new/current, TBPL]:
https://treeherder.mozilla.org/ui/#/jobs?repo=try&revision=9e97fe7b5084
(can be applied on top of aurora without any issue)

[Risks and why]:
This patch prevent optimizations in broken cases.

[String/UUID change made/needed]:
N/A

Comment 14

[Nicolas B. Pierron [:nbp]]

inbound:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b95f61af93b9
https://hg.mozilla.org/integration/mozilla-inbound/rev/5d74235ea15c

aurora:
https://hg.mozilla.org/releases/mozilla-aurora/rev/c36ce4b575e9
https://hg.mozilla.org/releases/mozilla-aurora/rev/e6fb11a6a976

Comment 15

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/b95f61af93b9
https://hg.mozilla.org/mozilla-central/rev/5d74235ea15c

This is fixed on all affected branches. Can we land a test?

Comment 16

[Christian Holler (:decoder)]

JSBugMon: This bug has been automatically verified fixed.
JSBugMon: This bug has been automatically verified fixed on Fx36

Comment 17

[Nicolas B. Pierron [:nbp]]

(In reply to Ryan VanderMeulen [:RyanVM UTC-5] from comment #15)
> https://hg.mozilla.org/mozilla-central/rev/b95f61af93b9
> https://hg.mozilla.org/mozilla-central/rev/5d74235ea15c
> 
> This is fixed on all affected branches. Can we land a test?

I have a simplified test case, which is saving resources compared to the one from comment 0, I will attach a patch.

Comment 18

[Nicolas B. Pierron [:nbp]]

Attachment: Add test case.

Comment 19

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/e6d24d95226f

Comment 20

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/e6d24d95226f

Comment 21

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/e6d24d95226f