90445 - Crash compiling bloated function while loading page.

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[John Morrison]

I hit a page with the following, uh, sub-optimally-coded function. 
However, mozilla shouldn't crash. We do.

Here's the top of the stack. Will attach full stack trace and the 
offending function definition.


PatchGotos(JSContext * 0x022e56b0, JSCodeGenerator * 0x0012f078, JSStmtInfo * 
0x0012c748, int 33129, unsigned char * 0x035331a3, unsigned char 6) line 406 + 
2 bytes
js_PopStatementCG(JSContext * 0x022e56b0, JSCodeGenerator * 0x0012f078) line 
442 + 25 bytes
js_EmitTree(JSContext * 0x000003df, JSCodeGenerator * 0x03501680, JSParseNode * 
0x03501650) line 1680 + 7 bytes
js_EmitTree(JSContext * 0x022e56b0, JSCodeGenerator * 0x00000000, JSParseNode * 
0x03501130) line 2135 + 8 bytes
js_EmitTree(JSContext * 0x000003d4, JSCodeGenerator * 0x00000000, JSParseNode * 
0x03500e20) line 1056 + 10 bytes
js_EmitTree(JSContext * 0x022e56b0, JSCodeGenerator * 0x00000000, JSParseNode * 
0x03500d30) line 2135 + 8 bytes
js_EmitTree(JSContext * 0x000003cf, JSCodeGenerator * 0x00000000, JSParseNode * 
0x034fe750) line 1056 + 10 bytes
js_EmitTree(JSContext * 0x022e56b0, JSCodeGenerator * 0x00000000, JSParseNode * 
0x034fe720) line 2135 + 8 bytes
js_EmitTree(JSContext * 0x00000375, JSCodeGenerator * 0x034fe6f0, JSParseNode * 
0x034fe510) line 1630 + 10 bytes
js_EmitTree(JSContext * 0x022e56b0, JSCodeGenerator * 0x00000000, JSParseNode * 
0x023594f0) line 2135 + 8 bytes
js_EmitFunctionBody(JSContext * 0x022e56b0, JSCodeGenerator * 0x0012f078, 
JSParseNode * 0x023594f0, JSFunction * 0x03496110) line 850 + 12 bytes
js_EmitTree(JSContext * 0x03496110, JSCodeGenerator * 0x023594f0, JSParseNode * 
0x023594c0) line 930 + 20 bytes
Statements(JSContext * 0x00000001, JSTokenStream * 0x023594c0, JSTreeContext * 
0x0012f218) line 911 + 42 bytes
js_CompileTokenStream(JSContext * 0x00000000, JSObject * 0x02291a20, 
JSTokenStream * 0x02359148, JSCodeGenerator * 0x0012f218) line 391 + 13 bytes
CompileTokenStream(JSContext * 0x022e56b0, JSObject * 0x02291a20, JSTokenStream 
* 0x02359148, void * 0x022e5730, int * 0x00000000) line 2784 + 19 bytes
JS_CompileUCScriptForPrincipals(JSContext * 0x022e56b0, JSObject * 0x02291a20, 
JSPrincipals * 0x034b7ea0, const unsigned short * 0x0350ce00, unsigned int 
17577, const char * 0x034bea78, unsigned int 3) line 2863 + 13 bytes
JS_EvaluateUCScriptForPrincipals(JSContext * 0x022e56b0, JSObject * 0x02291a20, 
JSPrincipals * 0x034b7ea0, const unsigned short * 0x0350ce00, unsigned int 
17577, const char * 0x034bea78, unsigned int 3, long * 0x0012f33c) line 3270 + 
27 bytes
nsJSContext::EvaluateString(nsJSContext * const 0x00000000, const nsAString & 
{...}, void * 0x02291a20, nsIPrincipal * 0x00000000, const char * 0x034bea78, 
unsigned int 3, const char * 0x00e12284 `string', nsAString & {...}, int * 
0x0012f428) line 608 + 56 bytes
nsScriptLoader::EvaluateScript(nsScriptLoader * const 0xffff8174, 
nsScriptLoadRequest * 0x03447bf0, const nsAFlatString & {...}) line 565
nsScriptLoader::ProcessRequest(nsScriptLoader * const 0xffff8174, 
nsScriptLoadRequest * 0x03447bf0) line 477 + 9 bytes
nsScriptLoader::ProcessScriptElement(nsScriptLoader * const 0x00000000, 
nsIDOMHTMLScriptElement * 0x034b7da4, nsIScriptLoaderObserver * 0x034bb204) 
line 420 + 11 bytes
nsHTMLScriptElement::SetDocument(nsHTMLScriptElement * const 0x034bb1d8, 
nsIDocument * 0x03494bc0, int 0, int 55278960) line 143 + 31 bytes

...

Comment 1

[John Morrison]

Attachment: full stack trace, win2k.

Comment 2

[John Morrison]

Attachment: offending function in an html page; ready for crashing.

Comment 3

[Phil Schwartau]

The function in question uses a very large array and loops through it.
Here is part of the code: 


for (i=0; i<nbVillages; i++) {
  if ((((mois   == 0) && (1==V[i][0])) || ((mois >= V[i][1]) && (mois <= 
V[i][2]))) &&
      ((region  == 0)  || (region  == V[i][3] )) &&
      ((confort == 0)  || (confort == V[i][4] )) &&
      ((encadrement == 0)                                               ||
      ((encadrement==3)&&((V[i][5]==1)||(V[i][5]==2)||(V[i][5] == 3))) ||
      ((encadrement==2)&&((V[i][5]==1)||(V[i][5]==2))) ||
      ((encadrement==1)&&(encadrement==V[i][5])) ||
      ((encadrement>3)&&(encadrement==V[i][5]) )) &&
      ((typeVillage == 0) || (typeVillage == V[i][6] ))   &&
      ((budget == 0)      || (budget      == V[i][7] ))) {

Comment 4

[Phil Schwartau]

Attachment: WinNT stack trace from the standalone JS shell -

Comment 5

[Phil Schwartau]

Reassigning to Kenton. cc'ing Brendan on the off chance that this is
simply a duplicate of bug 89443, "Browser crashes on large PAC files".
i.e. I'm wondering if it's the || operators here that are the culprit, 
just as in bug 89443 - 

Comment 6

[Phil Schwartau]

Testcase added to JS testsuite: 

                   js1_5/Regress/regress-90445.js

Comment 7

[Phil Schwartau]

On second thought, I don't suppose this bug is a duplicate of bug 89443.
In the latter bug the crash is due to stack overflow; whereas here, it's not.

Comment 8

[Brendan Eich [:brendan]]

Shaver loves backpatching too.  Any news?

/be

Comment 9

[Kenton Hanson (gone)]

In file “jsemit.c” the crash is caused by “pc jump offset” being larger than 2^15 
and subsequently being altered by “GET_JUMP_OFFSET” in “PatchGotos” when 
calculating “delta”.  Note, “top” is never used in “PatchGotos”.  This jump 
offset gets set by macro EMIT_CHAINED_JUMP that does not range check delta.  A 
range checking version is included.

If delta is always positive it might be more generous to allow this jump to be 
coded as unsigned jump, still doing the range checking and creating a 
“GET_JUMP_OFFSET_UNSIGNED” macro for “PatchGotos”.

Any help would be appreciated.



PatchGotos(JSContext *cx, JSCodeGenerator *cg, JSStmtInfo *stmt,
           ptrdiff_t last, jsbytecode *target, jsbytecode op)
{
    jsbytecode *pc, *top;
    ptrdiff_t delta, jumpOffset;

    pc = CG_CODE(cg, last);
    top = CG_CODE(cg, stmt->top);
    while (pc != CG_CODE(cg, -1)) {
        JS_ASSERT(*pc == op);
        delta = GET_JUMP_OFFSET(pc);
        jumpOffset = PTRDIFF(target, pc, jsbytecode);
        CHECK_AND_SET_JUMP_OFFSET(cx, cg, pc, jumpOffset);
        pc -= delta;
    }
    return JS_TRUE;
}





/*
 * Emit a jump op with offset pointing to the previous jump of this type,
 * so that we can walk back up the chain fixing up the final destination.
 */
#define EMIT_CHAINED_JUMP(cx, cg, last, op, jmp)                              \
    JS_BEGIN_MACRO                                                            \
        ptrdiff_t offset, delta;                                              \
        offset = CG_OFFSET(cg);                                               \
        delta = offset - (last);                                              \
        last = offset;                                                        \
        jmp = js_Emit3((cx), (cg), (op), JUMP_OFFSET_HI(delta),               \
                       JUMP_OFFSET_LO(delta));                                \
    JS_END_MACRO





/*
 * Emit a jump op with offset pointing to the previous jump of this type,
 * so that we can walk back up the chain fixing up the final destination.
 */
#define EMIT_CHAINED_JUMP(cx, cg, last, op, jmp)                              \
    JS_BEGIN_MACRO                                                            \
        ptrdiff_t offset, delta;                                              \
        offset = CG_OFFSET(cg);                                               \
        delta = offset - (last);                                              \
        last = offset;                                                        \
        if (delta < JUMP_OFFSET_MIN || JUMP_OFFSET_MAX < delta) {             \
            ReportStatementTooLarge(cx, cg);                                  \
            jmp = -1;                                                         \
        }                                                                     \
        else                                                                  \
            jmp = js_Emit3((cx), (cg), (op), JUMP_OFFSET_HI(delta),           \
                       JUMP_OFFSET_LO(delta));                                \
    JS_END_MACRO

Comment 10

[Brendan Eich [:brendan]]

Attachment: diff -u of khanson's inline patch, with comment tweak and dead var (top) removal

Comment 11

[Brendan Eich [:brendan]]

The top variable in PatchGotos became dead in rev 3.7, fur's big landing.  Long
time past, and no one noticed.  I believe the engine has *always* failed to
bounds-check delta when emitting a chained goto :-(.  BTW, the question of
whether two byte signed immediate jump offset operand format is too restrictive
is addressed by bug 80981.

Anyway, thanks for fixing this -- I say sr=[e-mail], and shaver
should sr= too.

/be

Comment 12

[Brendan Eich [:brendan]]

Trying to fix crash bugs for 0.9.4, will mail drivers once shaver records his
sr= here.

/be

Comment 13

[Mike Shaver (:shaver emeritus)]

sr=shaver, though I'd prefer

+ if (delta < JS_OFFSET_MIN || delta > JS_OFFSET_MAX)

because it seems more natural to me to think about the relations that way.

Comment 14

[Brendan Eich [:brendan]]

shaver: you should visualize the number line, then you'll agree with the orders
of operands that I used!

Come to think of it, though, I added a JS_ASSERT(delta > 0), so there should be
only an 'if (delta > JUMP_OFFSET_MAX)' test (and I do generally spell single
relationals with that operand order).

/be

Comment 15

[Kenton Hanson (gone)]

If delta is always positive why not allow this jump to be 
coded as an unsigned jump”.  The delta in PatchGotos” is not restricted by the 
signed 16-bit integer range.  BTW the example code did not crash when a 
“GET_JUMP_OFFSET_UNSIGNED” macro for “PatchGotos” was tested (I don’t know if it 
ran correctly).  Phil also successfully tested this patch.

If all this makes sense, it would seem more friendly to let the users code run 
successfully rather than causing an over cautious error.


Still trying to understand.

Comment 16

[Brendan Eich [:brendan]]

khanson: my point is that all backpatched, chained jumps jump to a target
bytecode before or after the first such jump (no gotos in JS -- these are all
upward continues or downward breaks, IIRC -- I'm hand-waving about the catch
clause jumps).  So if the distance between any two jump bytecodes is too great
for a signed 16-bit immediate jump offset encoding, then the distance from the
earlier or later (depending on jump direction) to the jump target must be too
great.  So we are not reporting any errors with the latest patch, the one I
attached, that would not be reported with the unsigned-for-backpatching-only
jump offset.

Check my argument by inspection and testing, it needs it.

/be

Comment 17

[Brendan Eich [:brendan]]

argh: "... before the first or after the last such jump", I should have written.

/be

Comment 18

[Asa Dotzler [:asa]]

a=asa on behalf of [e-mail]

Comment 19

[Brendan Eich [:brendan]]

Fix is in for 0.9.4.  Please keep asking/reviewing here, until you're satisfied
with the patch.

/be

Comment 20

[Phil Schwartau]

Marking Verified Fixed. The testcase above no longer crashes,
but errors gracefully instead:

[//d/JS_TRUNK/mozilla/js/src/WINNT4.0_DBG.OBJ]./js

js> load('../../tests/js1_5/shell.js')
js> load('../../tests/js1_5/Regress/regress-90445.js')
InternalError: block too large


I have the same question here as in bug 89443, however. 
Shouldn't the JS exit code be non-0 when this testcase exits?
Currently it is 0, so the test driver never detects the InternalError.
I only found it by loading the testcase manually in the JS shell.

Comment 21

[Phil Schwartau]

The exit code issue was filed in bug 97646...

Note: due to the recent fix for bug 97646, the testcase above now errors,
because we are now getting exit code 3 from its too-large script:

           js/tests/js1_5/Regress/regress-90445.js


This is all correct behavior with the current jump bytecode limitation. 

Once the fix for bug 80981 is checked in, however, the JS Engine
will no longer produce an InternalError on large scripts, thus
this test should no longer produce exit code 3.