565184 - Corrupt ABC can cause execution to fall of the end of JIT-ed method

Status: RESOLVED FIXED

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[William Maddox]

Attachment: Corrupt ABC crashing while executing garbage past the end of compiled method

The exception dispatch code consists of a skip chain comparing the desired exception handler offset with the one associated with the exception caught.
There is no default case.  For example:


  catch:                         catch vars env methodFrame _save_eip env_scope _ef 
  ld131 = ld 6382488[0]          vars env ld131 methodFrame _save_eip env_scope _ef 
  ld132 = ld ld131[0]            vars env ld131 methodFrame ld132 _save_eip env_scope _ef 
  sti vars[456] = ld132          vars env ld131 methodFrame _save_eip env_scope _ef 
  ld133 = ld _save_eip[0]        vars env ld131 methodFrame _save_eip ld133 env_scope _ef 
  beginCatch1 = icall #beginCatch ( 6381608 _ef 7332616 ld133 ld131 )
                                 beginCatch1 vars env methodFrame _save_eip env_scope _ef 
  ld134 = ld beginCatch1[8]      ld134 vars env methodFrame _save_eip env_scope _ef 
  eq13 = eq ld134, 64            ld134 vars env eq13 methodFrame _save_eip env_scope _ef 
  jt eq13 -> B64                 ld134 vars env jt12 methodFrame _save_eip env_scope _ef 

  eq14 = eq ld134, 96            ld134 vars env methodFrame eq14 _save_eip env_scope _ef 
  jt eq14 -> B96                 ld134 vars env methodFrame jt13 _save_eip env_scope _ef 

  eq15 = eq ld134, 223           ld134 vars env methodFrame eq15 _save_eip env_scope _ef 
  jt eq15 -> B223                ld134 vars env methodFrame _save_eip jt14 env_scope _ef 

  eq16 = eq ld134, 255           eq16 ld134 vars env methodFrame _save_eip env_scope _ef 
  jt eq16 -> B255                ld134 jt15 vars env methodFrame _save_eip env_scope _ef 

  eq17 = eq ld134, 382           ld134 vars env eq17 methodFrame _save_eip env_scope _ef 
  jt eq17 -> B382                ld134 vars env jt16 methodFrame _save_eip env_scope _ef 

  eq18 = eq ld134, 414           ld134 vars env methodFrame eq18 _save_eip env_scope _ef 
  jt eq18 -> B414                ld134 vars env methodFrame jt17 _save_eip env_scope _ef 

  eq19 = eq ld134, 541           ld134 vars env methodFrame eq19 _save_eip env_scope _ef 
  jt eq19 -> B541                ld134 vars env methodFrame _save_eip jt18 env_scope _ef 

  eq20 = eq ld134, 573           eq20 vars env methodFrame _save_eip env_scope _ef 
  jt eq20 -> B573                jt19 vars env methodFrame _save_eip env_scope _ef 

  live _ef                       live32 vars env methodFrame _save_eip env_scope 
  live _save_eip                 live33 vars env methodFrame env_scope 
  live env_scope                 vars env live34 methodFrame 
  live methodFrame               vars env live35 
  live env                       vars live36 
  live 6381608                   vars live37 
  live vars                      live38 
  live 4                         live39 

Fuzzed ABC's can fall off the end of the skip chain.  There should be a default case, and possibly further static validation of the ABC.

See Watson 2616279.

Comment 1

[William Maddox]

The function of the skip chain is to map the target offset of the exception handler in the ABC to the native code address in the JIT-ed code.

In CodegenLIR::writeEpilogue, a case is added to the skip chain only if the handler target offset (the offset of the code for the catch block) has been assigned frame state by the verifier, i.e, the verifier believes it to be a branch target.  If not, the case is omitted, and the possibility exists to fall off the end if an exception is actually caught by that handler. 

In the example .swf, the failure occurs while attempting to locate the native code address corresponding to offset 735, which is a legitimate target according to the handler table, but to which no framestate is assigned by the verifier.  The frame state should be assigned by a call to Verifier::checkTarget() in Verifier::verifyBlock().  This is where the verifier analyzes the implicit edge from each an instruction that may throw an exception to each of its possible handlers.  I have determined that offset 735 is not checked here.

In the fuzzed .swf, the code within the range for this handler consists entirely of nop instructions.  Since these cannot throw exceptions, it appears that the verifier is justified in ignoring the "impossible" exception edge.
By code instrumentation, however, I have found that the pc value passed to AvmCore::beginCatch() is 703, which is a noop. The pc value comes from _save_eip, which supposedly tracks the ABC instruction offsets during the execution of compiled methods with exception handlers.

My current working hypothesis is that _save_eip is corrupt.

Comment 2

[William Maddox]

It turns out that offset 703 is the target of another exception handler.  Thus, while the instruction at that location in the ABC is a nop, the verifier, treating it as the start of a handler, injects a coercion from the exception atom to the correct type to unbox it.  See Verifier::verifyBlock(), excerpt below:

            if (tryFrom >= code_pos && tryTo <= (code_pos + code_length) && pc >= tryFrom) {
                // all catch targets must be after the earliest try range since from <= to <= catch
                for (int i=0, n=exTable->exception_count; i < n; i++) {
                    ExceptionHandler* handler = &exTable->exceptions[i];
                    if (pc == code_pos + handler->target) {
                        AvmAssert(sp == stackBase); // if not, a VerifyError should have already occurred.
                        // FIXME: bug 538639: At the top of a catch block, we generate coerce when an unbox is all that is needed
                        emitCoerce(handler->traits, sp);
                        coder->writeOpcodeVerified(state, pc, opcode);
                    }
                }
            }

Control falls into this code with some unexpected value on the stack (remember, the code is corrupt) and the coercion throws an unexpected exception.  The actual machine code looks like this:

0x00759da4:	movl   $0x2ba,-0x318(%ebp)
0x00759dae:	movl   $0x2bb,-0x318(%ebp)
0x00759db8:	movl   $0x2bc,-0x318(%ebp)
0x00759dc2:	movl   $0x2bd,-0x318(%ebp)
0x00759dcc:	movl   $0x2be,-0x318(%ebp)
0x00759dd6:	movl   $0x2bf,-0x318(%ebp)
0x00759de0:	jmp    0x759de0
0x00759de5:	sub    $0x4,%esp
0x00759de8:	push   $0x647c48
0x00759ded:	push   %esi
0x00759dee:	pushl  -0x390(%ebp)
0x00759df4:	call   0x166af2 <_ZN7avmplus14coerceobj_atomEPNS_9MethodEnvEiPNS_6TraitsE>
0x00759df9:	add    $0x10,%esp
0x00759dfc:	and    $0xfffffff8,%esi
0x00759dff:	movl   $0x2c0,-0x318(%ebp)
0x00759e09:	movl   $0x2c1,-0x318(%ebp)
0x00759e13:	movl   $0x2c2,-0x318(%ebp)
0x00759e1d:	movl   $0x2c3,-0x318(%ebp)
0x00759e27:	movl   $0x2c4,-0x318(%ebp)
0x00759e31:	movl   $0x2c5,-0x318(%ebp)

The MOVLs are updating _save_eip for each of the NOPs.   The branch to self at 0x00759de0 is a hack I inserted to get the code to hang and let me debug at ABC offset 703 and should be ignored.  Here we can see the call to coerceobj, injected into the stream of nops.

Comment 3

[William Maddox]

Nested try-catch is permissable, afaik, so the problem is not that a catch target appears within the range of another handler.  From the FIXME comment in the verifier snippet above, I infer that the runtime null check that is failing should not even be performed here.

Possible fixes:

1) Treat the coercion as an exception-throwing instruction.  The result of
execution is nonsense, but it's type-safe, and the semantics fall out of the
nature of the corruption.  I don't really like this idea, however.

2) Forbid execution from falling into an exception handler.  Require that all handlers be entered only via the exception dispatch mechanism.  The coercion then cannot fail, and it will be safe to replace it by a simple unboxing as suggested in the FIXME.  This will complicate the verifier, as we must also disallow explicit (non-exception) branches as well as fallthrough.

3) Always handle all cases in the skip chain, whether the exception target appears reachable in the expected way or not.  Unfortunately, this prevents catch handlers that should be unreachable from being treated as dead code, as well as generating extra instructions useless for well-formed ABCs.

4) Add an explicit default at the end of the skip chain that signals the moral equivalent of a verifier error.  This would result in divergent behavior in interpreted vs. compiled code.

Option 2 seems to be the cleanest, but I have not evaluated how intrusive the required verifier change would be.

Comment 4

[William Maddox]

If we implemented option 2 by forbidding branches/fallthrough to the exception target, i.e., the entry label to the handler, we would not protect against attempts to jump into the middle of the handler.  In general, the verifier treats code as a graph of instructions, and doesn't impose the sort of structure on the code that would clearly distinguish handler code from non-handler code.

We need only protect the entry label, however, as from the ABC point of view, the exception raised by the implicitly-inserted coerce_atom call looks as if it were thrown instead by the first real ABC instruction in the handler, which appears at that label.

Rather than a structural check on where branches to handlers are allowed to occur, we can also view this explicitly as type-checking problem.   We need to verify that the value on top of the stack just before the coercion is specifically a boxed Exception object, not just any atom.  An object of the correct type would be generated only by instructions that can throw, and thus would be propagated to the handler's framestate only via exception edges.

Although option 4 is a hack, I still find that an unterminated skip chain gives me the willies, and treating the default as an assert rather than a shortcut for the final test seems wise.

Comment 5

[William Maddox]

After discussion with Rick, it appears that a structural check forbidding branches and fallthroughs to exception targets is the best fix going forward.
An explicit runtime fallthrough check is the safest short-term fix in the 10.1 timeframe.  This remains typesafe as long as the unboxing of the exception atom continues to be done with coerce_atom.

Comment 6

[William Maddox]

Attachment: Require that exception handlers be reachable only via exception dispatch

This patch extends the verifier to enforce the constraint that exception handler entry points be reachable only via exception dispatch.  It is forbidden to fall into an exception handler or to branch to it directly. The intent is to protect the private contract between the dispatch mechanism and the code inserted at the handler entry point to unbox the exception atom.  This makes it impossible for verifiable code to observe that the coerce_atom presently used for this purpose can throw an exception, and makes it sound to replace the coerce_atom with a simpler type-specific unboxing.

There are three major components of the patch:

1) Identify blocks that are targets of ordinary branches, i.e., non-exceptional edges.  By design, the logic very closely parallels the existing logic for identifying the targets of backward branches.

2) In verifyBlock, when checking whether the current address is a handler target, we check that any targets are the first instruction of the block (no fallthrough) and that the block is not the target of an ordinary branch.

3) As a backstop, a loop-to-self is inserted after the skip chain in the epilog. This could be replaced in future to optimize the last case of the chain with an unconditional branch.  I really didn't want to leave it unterminated.

Note that it remains possible for multiple exception handler table entries to point to the same target.  If we replace the coerce_obj with a simpler unboxing, we will need to change the type that we record when we push the exception atom to reflect the expected type at the handler, not the actual type '*' of the atom, and finesse the unboxing to deal with this.  Normal typechecking rules should then apply, relieving us of the need to force uniqueness of handler targets.

Comment 7

[William Maddox]

Oops!  This is really bad.  On reflection, the last paragraph above is nonsense.
The existing code (including prior to this patch) will generate multiple copies of the unboxing code if more than one exception targets the current code position.  It is only correct to allow multiple handler table entries to share the same target when the types are the same, as we may emit only a single coercion to a single expected type.

Comment 8

[William Maddox]

Attachment: Example with two handlers with different types and same target

Verbose output shows the first coercion compiling as a call to 'number',
followed by another coercing the number, not the original exception atom,
to a string via 'doubleToString'.
 
  55: B15:
  56: 15 = int 15
  57: sti _save_eip[0] = 15
  58: ld5 = ld vars[8]
  59: number1 = fcall #number ( ld5 )
  60: 7 = int 7
  61: doubleToString1 = icall #doubleToString ( 6381608 number1 )
  62: sti vars[8] = doubleToString1
  63: 1 = int 1
  64: stb tags[1] = 1
  65: j -> B19

Comment 9

[William Maddox]

Attachment: Source code for the example of duplicate targets

Comment 10

[William Maddox]

Attachment: 445248: Require that exception handlers be reachable only via exception dispatch (revised)

Revised patch to check for incompatible sharing of handler code between multiple exception handler table entries.  Assures that the coercion of the exception atom is not garbled (duplicated), and may never itself throw an exception.

Comment 11

[Rick Reitmaier]

Comment on attachment 445272 [details] [diff] [review]
445248: Require that exception handlers be reachable only via exception dispatch (revised)

I'm mostly ok with the patch but have a couple of points that lead me to reject it:

(1) CodegenLIR change for falling off the chain is to infinite loop?   I'm not a fan, can we throw an exception or something less likely to gum up the system?

(2) The verifier change slightly alters behaviour in that we used to be able (or at least it appears that we could) have multiple types for each handler.   
Not exactly sure that we want to preserve those mechanics but it is a change.

Comment 12

[William Maddox]

(In reply to comment #11)

> (1) CodegenLIR change for falling off the chain is to infinite loop?   I'm not
> a fan, can we throw an exception or something less likely to gum up the system?

This is just a backstop because I don't like leaving the skip chain unterminated, and it would be a larger change to replace the final jump with an unconditional one.

I investigated throwing an exception here.  Unfortunately, we are already in the middle of dispatching an exception.  The result is an infinite loop of throwing and catching.  It may be possible to avoid this by forcibly unwinding the stack and throwing in the caller, but things are starting to get complicated at this point.

> (2) The verifier change slightly alters behaviour in that we used to be able
> (or at least it appears that we could) have multiple types for each handler.  
> Not exactly sure that we want to preserve those mechanics but it is a change.

If we have multiple exception table entries with the same target, then a chain of coercions is generated at the target.  The result is likely nonsense.  On entry to the handler, what is the inferred type of the thrown value on the top of the stack?  In the present case, it is always that specified by the applicable handler table entry that occurs last.  A sensible definition would require that it be the least common supertype of all of the exception types that could be handled at the shared target.

Comment 13

[William Maddox]

Attachment: Account for possible throw by unboxing coercion in malformed code

The previous patch implements a strong structural constraint on exception handlers that protects the contract between the exception dispatch machinery and the ABC code at the exception handler target.  This makes the means by which the thrown value is transmitted opaque at the ABC level, which is clean, easy to explain, offers the most flexibility for the implementation (e.g., replacing coercions with simple unboxing), and in agreement with an assumption that we appear to have been making tacitly all along.  Most significantly, from a semantic viewpoint, by allowing the implicitly-generated coercions to be observed, we end up with ABC code in which exceptions appear to be thrown by instructions that cannot ordinarily throw.

Most of this is semantic nicety, however.  For the immediate purpose at hand, the interesting property of the structural constraints is simply that we guarantee that the hidden coercions cannot throw.  Alternatively, we can embrace the fact that the coercions are inserted, and allow that they can be observed, and indeed must be accounted for.  We simply assert that, contrary to usual expectations, the first instruction of a handler, by special dispensation, *can* throw, and while code that causes this to happen is probably not what the user/compiler intended to write, it remains typesafe and properly sandboxed.  As long as the VM's handler reachability analysis takes the "anomalous" throw into account, the exception will be properly handled, and indeed the behavior will be as the user expects *if* we choose to consider the implicit insertion of the unboxing coercion as specified behavior.

The attached patch implements this semantics.  Note that the order of a pair of paragraphs of code are reversed, leading to a larger diff than the actual change would imply.

Comment 14

[William Maddox]

Attachment: Optimize exception handler boilerplate, including skip chain (draft, not final)

The right way to avoid the unterminated skip chain is to optmize the last branch to be an unconditional one.  In some cases, however, no exceptions at all may be reachable, but the logic to insert the exception-handling boilerplate, including the skip chain, does not recognize this.  Thus it is possible to branch to the catch label in the epilogue and fall off the end, because there is not case to optimize to the unconditional branch.  Thus, a complete fix requires that we test for an actual reachable exception, rather than the mere presence of an exception handler table for the method.  The attached patch implements this logic.  Unfortunately, it fails one of the
regression tests:

FAILURES:
  as3/Definitions/Classes/ClassDef/Bug118272Package.abc : unexpected exit code expected:0 actual:1 Signal Name: SIGHUP FAILED!
  as3/Definitions/Classes/ClassDef/Bug118272Package.abc : captured output: ReferenceError: Error #1056

In this case, an exception was not caught.  At present, I'd bet even money that I've exposed a pre-existing fault, such as an incorrect canThrow bit on an opcode.  Continuing to investigate.

Comment 15

[William Maddox]

To be clear, the unterminated skip chain is largely an aesthetic concern, and the patch above, while prevents a crash, will not exhibit correct semantics without addressing the issue of non-exceptional entry to a handler in the verifier.

Comment 16

[William Maddox]

Attachment: Optimize exception handler boilerplate, including skip chain (draft, revised)

In general, the results of the first phase of the verifier are retained for the use of the second phase, including codegen.  There are some non-obvious/undocumented constraints on hasFrameState(), however, stemming from the fact that it translates bytecode offsets to absolute abc pointers "under the covers" using code_pos.  Unfortunately, code_pos is not fixed, but may be changed later during verification by OP_abs_jump.  Any analysis done prior to such a change is fragile to say the least.  Presumably, we get away with this because OP_abs_jump is only used internally in VM-generated code, and this code, which gets verified before code_pos gets its final value, is of a stylized form.  In any case, it is apparently not safe to invoke Verifier::hasFrameState() during the phase 2 call to writePrologue().

Comment 17

[Edwin Smith]

(In reply to comment #3)

> 1) Treat the coercion as an exception-throwing instruction.  The result of
> execution is nonsense, but it's type-safe, and the semantics fall out of the
> nature of the corruption.  I don't really like this idea, however.
> 
> 3) Always handle all cases in the skip chain, whether the exception target
> appears reachable in the expected way or not.  Unfortunately, this prevents
> catch handlers that should be unreachable from being treated as dead code, as
> well as generating extra instructions useless for well-formed ABCs.

To me, only solution #1 and #3 seem correct, and #1 seems more optimal since it won't prevent dead code from being eliminated.  

When an exception block can be reached by a non exception edge, we should just verify it like any other fall through block; if exception edges can reach there then it must have stack-depth 1, and the value at stack[0] should be coerced, and if this can trigger an exception, so be it.  (it doesn't seem wrong to me).

The contract required by beginCatch() is that the handler returned must be correct for the type of the exception value; therefore the only way the implicit coerce can throw is the fall-through case.

A secondary problem is this: what if multiple catch blocks with different types specify the same catch handler location?  the multiple implicitly generated coersions seem wrong; if the order is dictated by the ABC exception handler order, then as long as they don't do anything bad (cast pointers to the wrong type, etc) AND as long as they are modeled as posssibly throwing exceptions, the right semantics should result.

Comment 18

[Edwin Smith]

arguably, the inserted coersions should occur in the if-else chain, and be simple unboxing operations instead of calls to coerce() at the catch target site.  if multiple colliding types are possilble, the SST_mask should reflect the possibility.  Then no code needs to be inserted at the catch target site and multiple catch blocks at the same site won't result in a chain of coersions that produce & consume illegal values.

Comment 19

[Edwin Smith]

(In reply to comment #12)
> (In reply to comment #11)
> 
> > (1) CodegenLIR change for falling off the chain is to infinite loop?   I'm not
> > a fan, can we throw an exception or something less likely to gum up the system?
> 
> This is just a backstop because I don't like leaving the skip chain
> unterminated, and it would be a larger change to replace the final jump with an
> unconditional one.

Another idea for a backstop is calling a helper that throws an uncatchable exception, similar to the one used for a second-chance timeout.

Comment 20

[Edwin Smith]

(In reply to comment #16)
> Created an attachment (id=445907) [details]
> Optimize exception handler boilerplate, including skip chain (draft, revised) 
> 
> In general, the results of the first phase of the verifier are retained for the
> use of the second phase, including codegen.  There are some
> non-obvious/undocumented constraints on hasFrameState(), however, stemming from
> the fact that it translates bytecode offsets to absolute abc pointers "under
> the covers" using code_pos.  Unfortunately, code_pos is not fixed, but may be
> changed later during verification by OP_abs_jump.  Any analysis done prior to
> such a change is fragile to say the least.  Presumably, we get away with this
> because OP_abs_jump is only used internally in VM-generated code, and this
> code, which gets verified before code_pos gets its final value, is of a
> stylized form.  In any case, it is apparently not safe to invoke
> Verifier::hasFrameState() during the phase 2 call to writePrologue().

I ran into this problem working on OSR too, and have a patch that changes the hasFrameState api's (and a few others) to use byte* pc instead of int pc_off, eliminating this ambiguity due to phases.

Comment 21

[Edwin Smith]

(In reply to comment #20)

> I ran into this problem working on OSR too, and have a patch that changes the
> hasFrameState api's (and a few others) to use byte* pc instead of int pc_off,
> eliminating this ambiguity due to phases.

See bug 561912

Comment 22

[Edwin Smith]

Comment on attachment 445272 [details] [diff] [review]
445248: Require that exception handlers be reachable only via exception dispatch (revised)

See previous comments

Comment 23

[Edwin Smith]

Comment on attachment 445450 [details] [diff] [review]
Account for possible throw by unboxing coercion in malformed code

See previous comments; I think we can fix this by inserting unbox (not coerce) code in the if-else dispatch chain, which would eliminate inserted coersions at the catch target.

Comment 24

[William Maddox]

This would address all of the issues that I had with allowing branches/fallthrough to a handler, namely, that 1) a semantically anomalous exception could be thrown, 2) the coercion would have to continue to duplicate a type check done implicitly by exception dispatch, without the proposed unboxing optimization, and 3) multiple catches of different types dispatching to the same target are allowed but not given sensible semantics.

Presumably, the framestate at the head of an exception edge will now represent the actual type being caught by that edge, and normal framestate checking will reconcile multiple types arriving at a shared target.  Presently, the framestate always reflects the generic atom that is currently passed to the handler.

Comment 25

[William Maddox]

Attachment: Minimal interim fix for crash -- make exception uncatchable and rethrow

This avoids a crash, and gives the host a chance to deal with the problem.
Rather than throwing a verify error, the original exception is rethrown.
It is made uncatchable to avoid looping in the catch handler already known to
be broken.  For what it's worth, this preserves the identity of the original
exception thrown.  This strategy was proposed by Edwin in a private discussion.

Comment 26

[Edwin Smith]

Apart from the review, one design question about the patch:  should we make it catchable?  I can think of two ways to avoid the infinite throw/catch loop

1. refactor the jit's call to AvmCore::beginCatch, so we rethrow the exception before calling beginTry again.  This will have the effect of bypassing any handlers of the current method.  (beginTry re-installs the current ExceptionFrame, which re-enables the current handlers).

2. set the _save_eip variable to -1 or 0xffffffff before rethrowing, which will make us skip any current handlers. (hacky but probably works fine)

If the exception is catchable by callers, then the overall effect of the bug is a try/catch "disappearing", but calling code still can catch and continue.

Comment 27

[Edwin Smith]

Comment on attachment 446074 [details] [diff] [review]
Minimal interim fix for crash -- make exception uncatchable and rethrow

R+ with two caveats:

can we declassify this?  I think we can since the injection was recent.

if we decide to allow the re-thrown exception to be catchable, thats a slight change.  (setting _save_eip to -1 is easy in exception_dispatch_fallthrough)

Comment 28

[William Maddox]

Attachment: Minimal interim fix for crash -- rethrow with catch in current method disabled

Option 1 in comment #26 is a bit intrusive -- I want to make it blindingly obvious that the patch does not affect cases where the if-then-else chain
does not fall through.

This patch implements option 2.  It turns out that the helper function really serves no purpose anymore, so I removed it in favor of calling AvmCore::throwException() directly.

Comment 29

[William Maddox]

Attachment: Minimal interim fix for crash -- rethrow with catch in current method disabled (revised)

Support 64-bit platforms correctly.

Comment 30

[Edwin Smith]

Comment on attachment 446317 [details] [diff] [review]
Minimal interim fix for crash -- rethrow with catch in current method disabled (revised)

Looks good to me.  Still needs to be declassified unless there is a dissenter.

Comment 31

[Dan Smith]

Declassify.

Comment 32

[William Maddox]

Attachment: Optimize exception handling and remove verification anomalies

This patch implements the scheme proposed in comment #23.  I am not proposing it to land at this time, because I believe it can be substantially improved by exploiting the forthcoming solution to Bug 561912, which alleviates the difficulties caused by OP_abs_jump.  Also, the patch needs additional directed testing at the abcasm level, because the ASC-generated acceptance tests do not adequately test many of the corner cases we now expect to handle correctly.

Comment 33

[Rick Reitmaier]

Comment on attachment 445450 [details] [diff] [review]
Account for possible throw by unboxing coercion in malformed code

removing feedback until comments addressed

Comment 34

[Edwin Smith]

Looks nice.  especially nice to see the inserted coerce's go away.  When this lands we can mark bug 538639 as fixed, so i made it depend on this bug.

The new branchovers in the exception dispatch code are visible to VarTracker, but the final jump to the catch target isn't.  Probably all the branches should be visible, or none; and I think none based on the rational used previously (no as3 variable state is affected by code inside these branches).

Catch blocks are considered reachable if there is a "can throw" opcode in the try block, without considering the type of the value thrown.  Since the type is not considered, reachability cannot change during phase 1.  So, you could set hasReachableExceptions in the block that checks the handler range and calls checkTarget().  This would eliminate the loop at the end of phase 1 and avoid the awkwardness from OP_abs_jump, I think (but I still want to land the patch from bug 561912 anyway).

nits:
* for clarity, I'd suggest renaming Verifier::hasExceptions() to hasReachableExceptions()

* CodegenLIR::writeEpilogue(): I was initially confused by the use of 'i' to find the last handler.  I'd suggest "last_ordinal" or something like that.

Comment 35

[William Maddox]

Interim fix pushed to tr-argo:

http://asteam.macromedia.com/hg/tamarin-redux-argo/rev/18e7ea9d4420

Comment 36

[Rick Reitmaier]

argo gmc cl 674107

Comment 37

[William Maddox]

(In reply to comment #34)
> The new branchovers in the exception dispatch code are visible to VarTracker,
> but the final jump to the catch target isn't.  Probably all the branches should
> be visible, or none; and I think none based on the rational used previously (no
> as3 variable state is affected by code inside these branches).

I coded it this way because the localSet calls are also visible to VarTracker.
Even if I avoided localSet, VarTracker works by overriding insLoad in the pipeline, so even directly setting the vars array would be noticed.  localSet also takes care of setting the tags.  While it's a bit sneaky to branch out of the if-then-else chain with an invisble branch, the labels reset the VarTracker state so that the localSets don't appear to be a sequence of assignments overwriting the previous, thus VarTracker's model remains accurate. Not that it really matters, as there are no further variable loads in the method for the VarTracker to eliminate.  Is it worth moving the tracking logic for stores out of the LirWriter pipline and into a higher-level layer as we did for branches with  branchToLabel and emitLabel?

The patch does does not properly account for exceptions with different types but a shared target, passing the thrown value in a machine representation suitable for the exception type rather than the merged type at the target.  This was easy enough to fix, but the investigation pointed out another issue: Dead tag stores are not optimized away, presumably due to the backward branches.

It appears that this problem may be finessed in the following way: If the merged type at the target has multiple machine representations (i.e., multiple bits are set in the sst_mask), then the tag must be set before control enters the handler.  Otherwise, the setting of the tag may be deferred until entry to the handler block.  I suspect that this is a more practical path forward than improving dead store elimination, but comments are welcome before I invest more time in the patch.

Comment 38

[William Maddox]

The new approach, without the coercion injected in the handler block, seems to be a much cleaner solution in principle, but I notice that it leads to a substantial increase in the size of the generated code.  While some redundancy is removed, and thus the code may execute somewhat faster, this benefits only the exceptional case.  My concern in the previous comment regarding elimination of dead tag stores arises from code size concerns, not exception dispatch speed.

We might instead pass a pointer to both the vars and tag slot into beginCatch(),
and allow it to do the both the unboxing and tagging interpretively.  It would then be necessary to emit code inline only to map the exception target from an ABC offset to a machine code address.  This approach would yield a small decrease in code size over the origina scheme, trading a couple of parameters for a call to an out-of-line coercion function, while avoiding the need to inject VM-generated code into the handler block.

Comment 39

[Dan Smith]

Bill Maddox on FP 9 backport:  The exception dispatch is done in an entirely different way than in Argo, and is not subject to the same failure mode.

Comment 40

[Edwin Smith]

seconded; the old system did not delete unreachable handlers and could not fall off the end.  at worse it would invoke the last handler wrongly, but we've never seen that in practice or with fuzzing.

Comment 41

[William Maddox]

(In reply to comment #37)

> The patch does does not properly account for exceptions with different types
> but a shared target, passing the thrown value in a machine representation
> suitable for the exception type rather than the merged type at the target.
 
On further reflection, I realize this statement is nonsense.  The intuition behind it is that conflicting types must be coerced to a common type (a tagged union if necessary) where incompatibly-represented values join.  This is not actually what we do.  Instead, we represent all values in tagged form, and optimize away the tags when we don't need to query them.  This is muddled by the fact that we currently query the tags only to construct an atom, thus the effect is similar, except that the union is constructed lazily at the join point rather than eagerly along the incoming edges.

Comment 42

[William Maddox]

Attachment: Optimize exception handling and remove verification anomalies (semi-interpretive)

This patch implements the scheme proposed in comment #38.

Here, beginCatch() is responsible for seting slot 0 and its tag appropriately for the exception value thrown.  We try to move as much of the exceptional-case logic as possible into the helper function to minimize the amount of boilerplate code that needs to be generated for exception handling.  We don't attempt to eliminate dead tag stores.  We retain the use of an ordinal values rather than the target offset to determine the handler block address, as it allows us to drop an additional instruction.

Comment 43

[Edwin Smith]

Comment on attachment 446852 [details] [diff] [review]
Optimize exception handling and remove verification anomalies (semi-interpretive)

I see, it makes sense to bury as much boilerplate as we can in beginCatch().  Since beginCatch() was already jit specific, I'd propose moving it to jit-calls.h; the tag/value representation, and access to vars[] and tags[], is logically private to the jit.  setThrownAtom is doing the opposite of makeAtom() defined in jit-calls.h; putting them near each other would be handy.

in setThrownValue(), why not switch on valueStorageType(bt)?

now that beginCatch is mutating vars[] and tags[], I think we're in good shape as far as VarTracker is concerned.  For dead-store elimination to work right, analyze_call() needs to be extended to model a call to beginCatch as a store to both vars[i] and tags[i], since that's what it does, and deadvars() depends on knowing about all the loads and stores from tags[] and vars[].

... or, is the whole point to hide the side effects of beginCatch()'s stores from view from deadvars()?  it seems sketchy to do that, but if its convincingly correct/safe, then we just need a comment.

Comment 44

[Dan Smith]

Re-targeting full fix 10.2; issue is resolved for 10.1.

Comment 45

[William Maddox]

Attachment: Optimize exception handling and remove verification anomalies (revised)

Incorporated Edwin's comments, including moving beginCatch() to jit-calls.h.
Live variable analysis now knows about the stores performed by beginCatch().

Comment 46

[William Maddox]

Attachment: Optimize exception handling and remove verification anomalies (revised)

Remove unnecessary line left over from prior work in progress.

Comment 47

[Edwin Smith]

Comment on attachment 448682 [details] [diff] [review]
 Optimize exception handling and remove verification anomalies (revised)

CodegenLIR.cpp:5781: new FIXME in code should get a bug # in the comment, to track future work, if its actionable, or be downgraded (remove "fixme") otherwise.   Agree about dodgyness; that we analyze the addp in isolation is dodgy in itself -- we should be analyzing actual loads and stores, or calls that do them, and only pick up addp(vars) as it is passed as an argument to such a call or load/store.

annother nice followup, if you choose to create it, is to replace the dispatch with LIR_jtbl on backends that support that opcode.

Comment 48

[William Maddox]

Pushed to tr:

http://hg.mozilla.org/tamarin-redux/rev/509efc64f316

Comment 49

[Brent Baker]

(In reply to comment #48)
> Pushed to tr:
> 
> http://hg.mozilla.org/tamarin-redux/rev/509efc64f316

This change has introduced failures on SPARC. There are a handful of failures but here is the dump from running ecma3/Statements/etry_007.abc

@1 (l@1) signal SEGV (no mapping at the fault address) in avmplus::AvmCore::atomWriteBarrier at line 4308 in file "AvmCore.cpp"
 4308           decr_atom(*address);
(dbx) where
current thread: t@1
=>[1] avmplus::AvmCore::atomWriteBarrier(gc = 0x77d030, container = 0x85d8, address = 0x8600, atomNew = 9340186), line 4308 in "AvmCore.cpp"
  [2] 0x90e238(0x1, 0x1, 0xffbfd7f0, 0xffbfd7f4, 0x8ba038, 0xffbfd498), at 0x90e238 
  [3] avmplus::MethodEnv::endCoerce(this = 0x8e6e00, argc = 1, ap = 0xffbfd7f0, ms = 0x8b7948), line 312 in "MethodEnv.cpp"
  [4] avmplus::MethodEnv::coerceEnter_generic(env = 0x8e6e00, argc = 1, atomv = 0xffbfdbc0), line 488 in "MethodEnv.cpp"
  [5] avmplus::InvokerCompiler::jitInvokerNext(env = 0x8e6e00, argc = 1, args = 0xffbfdbc0), line 6417 in "CodegenLIR.cpp"
  [6] avmplus::MethodInfoProcHolder::invoke(this = 0x895108, env = 0x8e6e00, argc = 1, args = 0xffbfdbc0), line 107 in "MethodInfo-inlines.h"

I am not sure if this is a simple fix or if it should have a new bug to track the issue and block this bug.

Comment 50

[Brent Baker]

I just ran another failing test and it is producing a different stack:

(dbx) runargs spidermonkey/js1_5/Regress/regress-407323.abc
(dbx) run
Running: avmshell_d spidermonkey/js1_5/Regress/regress-407323.abc 
(process id 16712)
STATUS: XML, XMLList, QName are mutable, Namespace is not.
t@1 (l@1) signal SEGV (no mapping at the fault address) in avmplus::ScopeTypeChain::getScopeIsWithAt at line 67 in file "ScopeChain-inlines.h"
   67       return (_scopes[i] & ISWITH) != 0;
(dbx) where
current thread: t@1
=>[1] avmplus::ScopeTypeChain::getScopeIsWithAt(this = 0x8af9f0, i = 8425639U), line 67 in "ScopeChain-inlines.h"
  [2] avmplus::MethodEnv::findproperty(this = 0x8afa18, outer = 0x8afa18, scopes = 0xffbfd5f0, extraScopes = 2, multiname = 0x8a93c8, strict = false, withBase = (nil)), line 1725 in "MethodEnv.cpp"
  [3] 0x90c44c(0xffbfd601, 0x804088, 0x1, 0xffbfd7dc, 0x8ba038, 0xffbfd480), at 0x90c44c

Comment 51

[Edwin Smith]

if it's only on sparc, and only when jit-compiling (must be since it was a jit change right?) then i suspect the sparc backend.

Comment 52

[Rick Reitmaier]

Probably best to open a new bug to track this particular failure; assuming sparc only.