991457 - Array lookup gives incorrect boolean results when JIT is enabled

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[David Caldwell]

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:29.0) Gecko/20100101 Firefox/29.0 (Beta/Release)
Build ID: 20140331125246

Steps to reproduce:

The symptom presents itself in this JavaScript game:

http://greenfelt.net/hopeless

Click on blobs of colors to remove them. When a whole column is removed the blocks should slide to the left to fill in the column.

In Firefox 28, 29 beta, and Aurora, sometimes they do not not slide to the left and the game leaves an empty column. The bug only appeared recently, but I can't confirm that Firefox 27 works. I do know that our users only started reporting this recently and the underlying code hasn't changed from June of 2013, where I tested it heavily in whatever the current Firefox beta was at that time.

Attempting to add too many debug statements or step through the code causes the bug to go away.

The code is simple enough to look at. The unminified source may be viewed here: http://greenfelt.net/hopeless.js

The offending function is this:

Hopeless.prototype.collapse_blocks = function() {
    var didSomething=0;
    do { // Loop 1
        didSomething=0;
        for (var x=0; x<this.blocks.length; x++)
            for (var y=1; y<this.blocks[x].length; y++) {
                if (!this.blocks[x][y] && this.blocks[x][y-1]) {
                    this.move_block(x,y,x,y-1);
                    didSomething=1;
                }
            }
    } while (didSomething);

    do { // Loop 2
        didSomething = 0;
        for (var x=0; x<this.blocks.length-1; x++)
            if (!this.blocks[x][10-1] && this.blocks[x+1][10-1]) {
                for (var y=0; y<this.blocks[x].length; y++)
                    this.move_block(x,y,x+1,y);
                didSomething = 1;
            }
    } while (didSomething);
}

// move_block, for reference:
Hopeless.prototype.move_block = function(x,y,x1,y1) {
    this.blocks[x][y] = this.blocks[x1][y1];
    if (this.blocks[x][y]) {
        this.blocks[x][y].move(x,y); // updates the canvas
        delete this.blocks[x1][y1];
    }
}

The contents of each cell of the 2d array "this.blocks" is either an object or undefined.

The first while loop moves blocks down and the second moves rows to the left. It is not possible for "Loop 1" to run and not "Loop 2" (I've confirmed there are no exceptions happening).

Which means the problem is that the second loops if statement "if (!this.blocks[x][10-1] && this.blocks[x+1][10-1])" is evaluating to false when it should evaluate to true. I have actually verified this with debug prints (again, trying to step through the code causes it to work).

I confirmed this with the following code added right before the if statement in question:
             printf("column %d: %j %j \n", x,
                    !!this.blocks[x  ][10-1],
                    !!this.blocks[x+1][10-1]);

(Apologies for using a print command that isn't built-in: %j does JSON.stringify). The code outputted this:
column 0: true true 
column 1: true true 
column 2: true true 
column 3: true true 
column 4: true true 
column 5: true true 
column 6: true true 
column 7: true true 
column 8: true true 
column 9: true true 
column 10: true true 
column 11: true true 
column 12: true true 
column 13: true true 
column 14: true true 
column 15: true true 
column 16: true true 
column 17: true true 
column 18: true true 

The problem was that one of the columns was actually empty. Jumping into the debugger and manually looking at the array showed that it was empty (length was 10, no array indexes were defined).

Trying to call JSON.stringify on the contents of the cell caused the bug to disappear, so I can't tell why Firefox thought the cell was true when it was really false.

I suspect some sort of Javascript JIT error or something very subtle.

I'm not sure how to reduce this problem into a shorter, repeatable test case, because when I touch anything it seems to start working again. Even as is, it does not fail ever single time, it seems to be dependent on the contents of the array, or something else.

I'm open to suggestions about how to debug this further.

Comment 1

[David Caldwell]

Forgot to mention this fails on both Windows and Mac OS X.

Comment 2

[David Caldwell]

Attachment: Testcase

I've distilled the problem down to a smallish test case. The page runs the test once per page load.

On error, the page background will turn red on failure and print "Detected a hole! x=11".

On success, the page background will turn green and print "Success".

The bug doesn't happen 100% of the time. You might have to reload the page about 30 times before it fails.

In Aurora, turning either of these options to fails causes the test to succeed consistently (50 reloads in a row):
  javascript.options.ion
  javascript.options.baselinejit
In 29 beta, it's these:
  javascript.options.ion.content
  javascript.options.baselinejit.content

Comment 3

[:Gijs (he/him)]

I can confirm this against b3 and b5 on OS X 10.9. Jan, can you look at what's going on here? (feel free to redirect if there are better people to ask...)

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Patch

The problem is here:

    if (!this.blocks[x][y] && ...) {

We assume this.blocks[x][y] always reads an object, and we fold away the MNot based on that (!object is always true). However, this is only valid as long as the element read is not dead-code-eliminated and will bail when we do read a hole.

I looked at other instructions with hole checks:

* MLoadElementHole: does not have this issue because it's only added when we have read |undefined| before.
* MArrayPopShift, MStoreElement: effectful; won't be eliminated anyway.
* MInArray: returns a boolean; safe to eliminate even if it needs a hole check.

So MLoadElement is the only one that has this problem.

Comment 5

[Jan de Mooij [:jandem]]

David, thanks a lot for filing this and for the testcase. Excellent bug report!

Just FYI: Ion compilation happens on a background thread so it's non-deterministic, that's probably why it didn't fail consistently. The "javascript.options.ion.parallel_compilation" pref disables background compilation.

This is an older IonMonkey bug; not sure why it only showed up now.

Comment 6

[Jan de Mooij [:jandem]]

(In reply to Jan de Mooij [:jandem] from comment #4)
> (!object is always true)

Er, always *false*, of course.

Comment 8

[Hannes Verschore [:h4writer]]

Comment on attachment 8403283 [details] [diff] [review]
Patch

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

Good find (but scary we only found this now).
Doesn't look like something special fuzzers shouldn't have found!

::: js/src/jit/MIR.h
@@ +5808,5 @@
>          needsHoleCheck_(needsHoleCheck),
>          loadDoubles_(loadDoubles)
>      {
> +        if (needsHoleCheck) {
> +            // Don't DCE this instruction. Other MIR instructions may be

// Its operands may be optimized away based on its result type, making it possible to DCE this instruction. But we need to invalidate when we read a hole. So set as guard.

Comment 9

[Sylvestre Ledru [:Sylvestre]]

Jan, could you check in the patch and fill the uplift request to make sure this goes with beta8 ? (gtb today around 12 pdt). Thanks

Comment 10

[Jan de Mooij [:jandem]]

(In reply to Sylvestre Ledru [:sylvestre] from comment #9)
> Jan, could you check in the patch and fill the uplift request to make sure
> this goes with beta8 ? (gtb today around 12 pdt). Thanks

Yes I'll land it when the tree is open...

Comment 11

[Jan de Mooij [:jandem]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/7ac91d7d6269

Comment 12

[Jan de Mooij [:jandem]]

Comment on attachment 8403283 [details] [diff] [review]
Patch

[Approval Request Comment]
Bug caused by (feature/regressing bug #): Unknown, older Ion bug.
User impact if declined: Broken websites/games, like this bug or the bug marked as duplicate.
Testing completed (on m-c, etc.): On m-i.
Risk to taking this patch (and alternatives if risky): Very low; it disables a particular optimization in some cases.
String or IDL/UUID changes made by this patch: None.

Comment 13

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/7ac91d7d6269

Comment 14

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/12171cfe5ded
https://hg.mozilla.org/releases/mozilla-beta/rev/3437e5663d9e