Closed Bug 991457 Opened 6 years ago Closed 6 years ago

Array lookup gives incorrect boolean results when JIT is enabled

Categories

(Core :: JavaScript Engine: JIT, defect)

29 Branch
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla31
Tracking Status
firefox28 --- wontfix
firefox29 + fixed
firefox30 + fixed
firefox31 + fixed

People

(Reporter: david+bugzilla, Assigned: jandem)

References

Details

(Keywords: regression, testcase)

Attachments

(2 files)

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.
Forgot to mention this fails on both Windows and Mac OS X.
OS: Mac OS X → All
Attached file 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
Summary: Array lookup gives incorrect boolean results in certain conditions → Array lookup gives incorrect boolean results when JIT is enabled
Component: Untriaged → JavaScript Engine: JIT
Keywords: testcase
Product: Firefox → Core
Attachment #8401531 - Attachment mime type: text/plain → text/html
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...)
Status: UNCONFIRMED → NEW
Ever confirmed: true
Flags: needinfo?(jdemooij)
Hardware: x86 → All
Attached patch PatchSplinter Review
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.
Assignee: nobody → jdemooij
Status: NEW → ASSIGNED
Attachment #8403283 - Flags: review?(hv1989)
Flags: needinfo?(jdemooij)
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.
(In reply to Jan de Mooij [:jandem] from comment #4)
> (!object is always true)

Er, always *false*, of course.
Duplicate of this bug: 987644
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.
Attachment #8403283 - Flags: review?(hv1989) → review+
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
Flags: needinfo?(jdemooij)
(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...
Flags: needinfo?(jdemooij)
Flags: needinfo?(jdemooij)
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.
Attachment #8403283 - Flags: approval-mozilla-beta?
Attachment #8403283 - Flags: approval-mozilla-aurora?
Attachment #8403283 - Flags: approval-mozilla-beta?
Attachment #8403283 - Flags: approval-mozilla-beta+
Attachment #8403283 - Flags: approval-mozilla-aurora?
Attachment #8403283 - Flags: approval-mozilla-aurora+
https://hg.mozilla.org/mozilla-central/rev/7ac91d7d6269
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Flags: in-testsuite+
Resolution: --- → FIXED
Target Milestone: --- → mozilla31
Duplicate of this bug: 996895
You need to log in before you can comment on or make changes to this bug.