508711 - TM: Prevent stack-after-exit bugs

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[David Mandelin [:dmandelin]]

This is from bug 508187, repeated and cleaned up for convenience. The same bug is currently latent for other ops (such as INCELEM), so we should try to prevent it systematically.

* The Bug: there is an easy-to-violate implicit rule in using nanojit with StackFilter:

    Let S be the LIR sequence for a given JS bytecode.
    Within S, a stack store must not precede a side exit.

Why? Consider this LIR:

    # current stack height = k
    # LIR for bytecode A, which pushes one value
    ...
    store to stack SA
    ...
    side exit XA          # stack height == k at this PC
    ...
    # current stack height = k+1
    # LIR for bytecode B, which consumes the value pushed by A
    ...
    side exit XB          # stack height == k+1 at this PC
    ...

The StackFilter works backward across the trace. At all times, it maintains a variable |top| which is the stack height at the last side exit seen (i.e., the first side exit after the current point). Any store to the stack at position |top| or higher thus cannot reach the interpreter (supposedly, but not really, as this example will show) and so is deleted from the LIR stream as an optimization.

In the example above, store SA is eliminated because |top == k| at exit XA. And in fact, that's fine if we take exit XA, because that exit will cause the interpreter to restart bytecode A, recomputing the value that was not stacked. But if we take exit XB, bytecode B will restart in the interpreter. The interpreter will then need to use the value stored at SA, but because it wasn't stored, we get junk instead.

* Preventative Measures: I see 3 approaches here, which I list in order of (IMO) general desirability:

- Redesign StackFilter to remove this temporal constraint. Temporal constraints (requirements on the order of events) are well-known to be yucky, i.e., hard to understand, hard to avoid violating, and hard to check automatically. There's no fundamental reason for this constraint. We can get rid of it if we make |top| be the height after the current op.

Another reason to get rid of the constraint is that it means the stores have to go after all the exits, instead of right after the value is created, increasing register pressure.

- Prevent violations by design pattern. There are several ways to do this. One would be to make an API that creates a pending store-to-stack. Recording functions would call that API. Then, the monitor would flush pending stores-to-stack after the rest of the op has been recorded.

- Check for violations with static analysis.

Comment 1

[Brendan Eich [:brendan]]

This seems important -- I wonder if we have latent bugs lurking.

/be

Comment 2

[David Mandelin [:dmandelin]]

(In reply to comment #1)
> This seems important -- I wonder if we have latent bugs lurking.

I believe so. For example, TraceRecorder::incElem can produce dense array guards and then store to the stack after that.

Comment 3

[Ryan VanderMeulen [:RyanVM]]

Obsolete with the removal of tracejit.