Bug 116853 – ASSERTION FAILED: low in JSC::UnlinkedCodeBlock::expressionRangeForBytecodeOffset

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Renata Hodovan]

Created attachment 203028 [details]
Test case

JSC has an assertion failure on the attached test.
It seems jsc cannot handle the thrown StackOverflowError correctly (like it does in a simple infinite loop).

Backtrace:

#0  0x00000000007fa9ad in WTFCrash () at /home/reni/Data/REPOS/webkit_sec/Source/WTF/wtf/Assertions.cpp:339
#1  0x00000000004bdf5e in JSC::UnlinkedCodeBlock::expressionRangeForBytecodeOffset (this=0x7fffb395f870, bytecodeOffset=4, divot=@0x7fffffffc5fc: 0, 
    startOffset=@0x7fffffffc5f8: 0, endOffset=@0x7fffffffc5f4: 0) at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/bytecode/UnlinkedCodeBlock.cpp:279
#2  0x0000000000641a3d in JSC::StackFrame::expressionInfo (this=0x7fffb27cc010, divot=@0x7fffffffc5fc: 0, startOffset=@0x7fffffffc5f8: 0, 
    endOffset=@0x7fffffffc5f4: 0) at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/interpreter/Interpreter.cpp:631
#3  0x00000000006419cb in JSC::StackFrame::column (this=0x7fffb27cc010)
    at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/interpreter/Interpreter.cpp:625
#4  0x0000000000641b5f in JSC::StackFrame::toString (this=0x7fffb27cc010, callFrame=0x7ffff7f5fb78)
    at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/interpreter/Interpreter.cpp:649
#5  0x00000000006420d2 in JSC::Interpreter::addStackTraceIfNecessary (callFrame=0x7fffb3dc0f88, error=...)
    at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/interpreter/Interpreter.cpp:711
#6  0x000000000072eab2 in JSC::throwError (exec=0x7fffb3dc0f88, error=0x7ffff7e8ff20)
    at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/runtime/Error.cpp:165
#7  0x0000000000730093 in JSC::throwStackOverflowError (exec=0x7fffb3dc0f88)
    at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/runtime/ExceptionHelpers.cpp:141
#8  0x0000000000643d49 in JSC::Interpreter::executeCall (this=0xf40f60, callFrame=0x7fffb3dc0f88, function=0x7ffff7ecfe30, callType=JSC::CallTypeHost, 
    callData=..., thisValue=..., args=...) at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/interpreter/Interpreter.cpp:1032
#9  0x0000000000721313 in JSC::call (exec=0x7fffb3dc0f88, functionObject=..., callType=JSC::CallTypeHost, callData=..., thisValue=..., args=...)
    at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/runtime/CallData.cpp:40
#10 0x0000000000774e8e in JSC::callDefaultValueFunction (exec=0x7fffb3dc0f88, object=0x7ffff7e6feb0, propertyName=...)
    at /home/reni/Data/REPOS/webkit_sec/Source/JavaScriptCore/runtime/JSObject.cpp:1344

[Oliver Hunt]

Weirdness, my guess is we're not correctly handling the top of stack frame.

[Geoffrey Garen]

<rdar://problem/14052089>

[Mark Lam]

Here's some data from the site of the assertion failure for this test case:

1. The assertion is in UnlinkedCodeBlock::expressionRangeForBytecodeOffset() which does a binary search of the m_expressionInfo Vector to find the range that the bytecodeOffset resides in.
2. The specified bytecodeOffset in this case is 4.
3. The m_expressionInfo Vector only has 1 entry:

(gdb) p expressionInfo.size()
$2 = 1
(gdb) p expressionInfo[0].instructionOffset
$4 = 19

The binary search in (1) starts with low = 0, and high = expressionInfo.size() i.e. 1.  Since the one entry in the Vector has an instructionOffset that exceeds the bytecodeOffset, it makes sense that the resultant low value is 0.

It looks like the assertion is invalid.  When the assertion is commented out, the reported line and column number in the stack trace is also correct.

I need to do a little bit more due diligence to check how expressionInfo is generated and see if there's any reason why the expressionRangeForBytecodeOffset() should not get the 0th entry in that Vector.

[Mark Lam]

(In reply to comment #3)
> I need to do a little bit more due diligence to check how expressionInfo is generated and see if there's any reason why the expressionRangeForBytecodeOffset() should not get the 0th entry in that Vector.

Due diligence is done!

m_expressionInfo is only appended to by UnlinkedCodeBlock::addExpressionInfo().
UnlinkedCodeBlock::addExpressionInfo() is only called by BytecodeGenerator::emitExpressionInfo().
I don't see any calls to BytecodeGenerator::emitExpressionInfo() which serves the purpose of reserving the first entry of the Vector for some special purpose.

Hence, it is legal for UnlinkedCodeBlock::expressionRangeForBytecodeOffset()'s binary search to produce a vector index of 0.  In other words, the assertion is invalid.

Will fix.

[Mark Lam]

Created attachment 203637 [details]
the patch.

[Geoffrey Garen]

> I don't see any calls to BytecodeGenerator::emitExpressionInfo() which serves the purpose of reserving the first entry of the Vector for some special purpose.

The algorithm expects to compute a value for "low" that is one past the index you were looking for. If it computes 0, that means the index you were looking for wasn't found. It is, in fact, an error for the index not to be found. Every expression that can throw an exception should have a valid expressionInfo entry.

[Mark Lam]

Re-analyzing based on Geoff's feedback:

1. The bytecodes of the unlinkedCodeBlock we're trying to find the range in are:

f#B44PHi:[0x104001000->0x1017ffc70, NoneFunctionCall]: 27 m_instructions; 216 bytes; 1 parameter(s); 8 callee register(s); 0 variable(s)

Source: function g() { // if (this != 10) f(); if (this != 10) f(); }

[   0] enter
[   1] convert_this	 r-7
[   4] neq		 r0, r-7, Int32: 10(@k0)
[   8] jfalse		 r0, 17(->25)
[  11] get_scoped_var	 r0, 1, 0
[  16] mov		 r1, Undefined(@k1)
[  19] call	 r0, 1, 8 status(Not Set)
[  25] ret		 Undefined(@k1)

Constants:
   k0 = Int32: 10
   k1 = Undefined

2. The bytecodeOffset we're looking up is:

(gdb) p bytecodeOffset
$8 = 4

We should not be throwing from bytecodeOffset 4.  Next step, find out where that bad bytecodeOffset is coming from.

[Mark Lam]

Here's a dump (using printfs I added) of the frame info as seen by Interpeter::getStackTrace():

  === frame[0] 0x105bfbf88
     name 'g'
     isInlineCallFrame 0
     codeBlock 0x10480cc00
     unlinkedCodeBlock 0x10229f870
     jitType 4 <DFGJIT>
     callerFrame 0x105bfbf40
     isHostFlag 0
     argCount.Tag 0 0
     bytecodeOffset 4 4
     lineOffset 2
     lineNo 4
  === END frame[0] 0x105bfbf88
  === frame[1] 0x105bfbf40
     name 'g'
     isInlineCallFrame 0
     codeBlock 0x10480cc00
     unlinkedCodeBlock 0x10229f870
     jitType 4 <DFGJIT>
     callerFrame 0x105bfbef8
     isHostFlag 0
     argCount.Tag 1 1
     bytecodeOffset 19 13
     lineOffset 2
     lineNo 4
  === END frame[1] 0x105bfbf40
  …

Frame 0 is the top frame.  Frame 1 is the caller frame of frame 0.  Frame 2 onward all resemble Frame 1.

The difference between Frame 0 and Frame 1 is that frame 0 has a codeOriginIndex of 0 (in the argCount tag field) and frame 1 has a codeOriginIndex of 1.  The result is that frame 0 has a bytecodeOffset of 4 instead of 19 like the other frames.

[Mark Lam]

(In reply to comment #8)
> The difference between Frame 0 and Frame 1 is that frame 0 has a codeOriginIndex of 0 (in the argCount tag field) and frame 1 has a codeOriginIndex of 1.  The result is that frame 0 has a bytecodeOffset of 4 instead of 19 like the other frames.

The bytecodeOffset of 4 is legit.  Here's the stack trace of when Interpreter::getStackTrace() is called:

(gdb) bt
#0  JSC::Interpreter::getStackTrace (vm=0x101807e00, results=@0x7fff5fbfdaa8, maxStackSize=18446744073709551615) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/interpreter/Interpreter.cpp:657
#1  0x00000001002d7209 in JSC::Interpreter::addStackTraceIfNecessary (callFrame=0x105dfbf88, error={u = {asInt64 = 4319739680, ptr = 0x10179ff20, asBits = {payload = 24772384, tag = 1}}}) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/interpreter/Interpreter.cpp:749
#2  0x00000001002a5d45 in JSC::throwError (exec=0x105dfbf88, error=0x10179ff20) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/runtime/Error.cpp:165
#3  0x00000001002a7cec in JSC::throwStackOverflowError (exec=0x105dfbf88) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/runtime/ExceptionHelpers.cpp:141
#4  0x00000001002d9874 in JSC::Interpreter::executeCall (this=0x102602a00, callFrame=0x105dfbf88, function=0x1013efe30, callType=JSC::CallTypeHost, callData=@0x7fff5fbfddd0, thisValue={u = {asInt64 = 4319805104, ptr = 0x1017afeb0, asBits = {payload = 24837808, tag = 1}}}, args=@0x7fff5fbfdd98) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/interpreter/Interpreter.cpp:1086
#5  0x00000001000fcc2a in JSC::call (exec=0x105dfbf88, functionObject={u = {asInt64 = 4315872816, ptr = 0x1013efe30, asBits = {payload = 20905520, tag = 1}}}, callType=JSC::CallTypeHost, callData=@0x7fff5fbfddd0, thisValue={u = {asInt64 = 4319805104, ptr = 0x1017afeb0, asBits = {payload = 24837808, tag = 1}}}, args=@0x7fff5fbfdd98) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/runtime/CallData.cpp:40
#6  0x0000000100380983 in callDefaultValueFunction (exec=0x105dfbf88, object=0x1017afeb0, propertyName={m_impl = 0x102301770, static NotAnIndex = 4294967295}) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/runtime/JSObject.cpp:1344
#7  0x000000010037b6dd in JSC::JSObject::defaultValue (object=0x1017afeb0, exec=0x105dfbf88, hint=JSC::NoPreference) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/runtime/JSObject.cpp:1372
#8  0x0000000100348394 in JSC::JSObject::toPrimitive (this=0x1017afeb0, exec=0x105dfbf88, preferredType=JSC::NoPreference) at JSObject.h:1402
#9  0x0000000100347e4f in JSC::JSCell::toPrimitive (this=0x1017afeb0, exec=0x105dfbf88, preferredType=JSC::NoPreference) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/runtime/JSCell.cpp:145
#10 0x00000001001689f8 in JSC::JSValue::toPrimitive (this=0x7fff5fbfe038, exec=0x105dfbf88, preferredType=JSC::NoPreference) at JSCJSValueInlines.h:554
#11 0x0000000100207386 in JSC::JSValue::equalSlowCaseInline (exec=0x105dfbf88, v1={u = {asInt64 = 4319805104, ptr = 0x1017afeb0, asBits = {payload = 24837808, tag = 1}}}, v2={u = {asInt64 = -281474976710646, ptr = 0xffff00000000000a, asBits = {payload = 10, tag = -65536}}}) at JSCJSValueInlines.h:734
#12 0x0000000100202f58 in operationCompareEq (exec=0x105dfbf88, encodedOp1=4319805104, encodedOp2=-281474976710646) at /Volumes/Data/ws7/OpenSource/Source/JavaScriptCore/dfg/DFGOperations.cpp:996
#13 0x000039e7c1c01804 in ?? ()
…

The test case looks like this:
=== BEGIN ============
function test() {
    var f = function g() {
        if (this != 10) f();
    };
    var a = f();
}

test();
=== END ============

The "(this != 10)" triggers a recursion into the interpreter to presumably convert "this" into a number for the comparison.  That recursion entry into the interpreter triggered a StackOverflowError, but our BytecodeGenerator is not expecting an exception thrown from op_neq.  Hence, we did not generate a expression range for that bytecode.

[Geoffrey Garen]

> The "(this != 10)" triggers a recursion into the interpreter to presumably convert "this" into a number for the comparison.

Basically any expression can trigger recursion in this way, due to type coercion. I wonder if we should just emitExpressionInfo() unconditionally at the head of every node.

[Mark Lam]

Created attachment 206419 [details]
patch 2

[Oliver Hunt]

Comment on attachment 206419 [details]
patch 2

View in context: https://bugs.webkit.org/attachment.cgi?id=206419&action=review

r=me, but i want to know why you have made the change to BinaryOpNode::emitBytecode -- i can't see why it would be necessary and it would have  a significant memory impact

> Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp:1099
> +    generator.emitExpressionInfo(startOffset(), 0, 0, lineNo(), lineStartOffset());

Why is this necessary?

[Mark Lam]

(In reply to comment #12)
> > Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp:1099
> > +    generator.emitExpressionInfo(startOffset(), 0, 0, lineNo(), lineStartOffset());
> 
> Why is this necessary?

It was added to provide expression info for the test case that originated this bug.  However, per our offline conversation this is not the right thing to do.

Adding some quick instrumentation, I'm seeing that adding expression range info for every BinaryOp node will result in a worst case increment of 295128 bytes (for 24594 entries).  This is based our benchmarking payloads (not sure which one as my instrumentation did not record the name of the benchmark).

For comparison, the worst case expression info memory use due to UnaryOp nodes is 12396 bytes (for 1033 entries) (also from the same benchmark).
 
Based on these results, I rethink the BinaryOp part of the patch and see what alternative I can come up with.

[Oliver Hunt]

(In reply to comment #13)
> (In reply to comment #12)
> > > Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp:1099
> > > +    generator.emitExpressionInfo(startOffset(), 0, 0, lineNo(), lineStartOffset());
> > 
> > Why is this necessary?
> 
> It was added to provide expression info for the test case that originated this bug.  However, per our offline conversation this is not the right thing to do.
> 
> Adding some quick instrumentation, I'm seeing that adding expression range info for every BinaryOp node will result in a worst case increment of 295128 bytes (for 24594 entries).  This is based our benchmarking payloads (not sure which one as my instrumentation did not record the name of the benchmark).
> 
> For comparison, the worst case expression info memory use due to UnaryOp nodes is 12396 bytes (for 1033 entries) (also from the same benchmark).
> 
> Based on these results, I rethink the BinaryOp part of the patch and see what alternative I can come up with.

A significant voice in my head is saying that we should just try using zlib to do an in memory compress of this data and then decompress it if we actually use it.

[Mark Lam]

The patch consists of 2 parts:
1. Adding ExpressionRangeInfo for BinaryOpNodes.  We know this adds some significant memory usage.
2. Adding ExpressionRangeInfo before calls to emitResolveBaseForPut() when in strict mode.

Will split the emitResolveBaseForPut() case into a separate bug: https://bugs.webkit.org/show_bug.cgi?id=118997.

[Mark Lam]

Created attachment 207364 [details]
patch 3

Patch 3 adds expression info for 2 cases in BinaryOpNode::emit:
1. the strcat case
2. the general case

It does not add expression info for the "compare with null" case because that case cannot throw due to type coercion.  Hence, it does not needed the expression info.

Note: this bug original complains of an assertion failure.  That assertion was removed in http://trac.webkit.org/changeset/152494.  However, this patch does add 2 test cases to the fast/js/line-column-number.html layout test.  The fix in this patch is needed to provide more accurate line and column info for these 2 test cases.

[Geoffrey Garen]

Comment on attachment 207364 [details]
patch 3

r=me

[Mark Lam]

Thanks for the review.  This patch has passed the layout tests with no new failures.  Landed in r153073: <http://trac.webkit.org/changeset/153073>.