Bug 226012 – [JSC] Fix consistency check during stack splitting in Wasm::LLIntGenerator::addLoop

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Frédéric Wang (:fredw)]

Created attachment 429159 [details]
Testcase

ASSERTION FAILED: static_cast<unsigned>(expression.toLocal()) < m_codeBlock->m_numVars in LLIntGenerator::checkConsistency()

See attached testcase.

Reproduced with JSC on debug builds r277716, for both Linux and macos.

ASAN release build completes without problem. This happens also in debug build once removing the debug assert. I'm however, reporting it as a security bug for now as it was found by a fuzze.

./wasm/WasmLLIntGenerator.cpp(377) : auto JSC::Wasm::LLIntGenerator::checkConsistency()::(anonymous class)::operator()(JSC::VirtualRegister, JSC::VirtualRegister) const
1   0x100f6c2ac WTFCrash
2   0x101e01434 WTFCrashWithInfo(int, char const*, char const*, int)
3   0x105e6ddd8 JSC::Wasm::LLIntGenerator::checkConsistency()::'lambda0'(JSC::VirtualRegister, JSC::VirtualRegister)::operator()(JSC::VirtualRegister, JSC::VirtualRegister) const
4   0x105e6d9d4 void JSC::Wasm::LLIntGenerator::walkExpressionStack<JSC::Wasm::LLIntGenerator::checkConsistency()::'lambda0'(JSC::VirtualRegister, JSC::VirtualRegister)>(WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&, unsigned int, JSC::Wasm::LLIntGenerator::checkConsistency()::'lambda0'(JSC::VirtualRegister, JSC::VirtualRegister) const&)
5   0x105e6cd58 void JSC::Wasm::LLIntGenerator::walkExpressionStack<JSC::Wasm::LLIntGenerator::checkConsistency()::'lambda0'(JSC::VirtualRegister, JSC::VirtualRegister)>(WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&, JSC::Wasm::LLIntGenerator::checkConsistency()::'lambda0'(JSC::VirtualRegister, JSC::VirtualRegister) const&)
6   0x105e260a4 JSC::Wasm::LLIntGenerator::checkConsistency()
7   0x105e2b520 JSC::Wasm::LLIntGenerator::materializeConstantsAndLocals(WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&)
8   0x105e2aa7c JSC::Wasm::LLIntGenerator::addLoop(JSC::Wasm::Signature const*, WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&, JSC::Wasm::LLIntGenerator::ControlType&, WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&, unsigned int)
9   0x105ed0194 JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::parseExpression()
10  0x105ea4668 JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::parseBody()
11  0x105ddfc44 JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::parse()
12  0x105dded9c JSC::Wasm::parseAndCompileBytecode(unsigned char const*, unsigned long, JSC::Wasm::Signature const&, JSC::Wasm::ModuleInformation const&, unsigned int)
13  0x105e53154 JSC::Wasm::LLIntPlan::compileFunction(unsigned int)
14  0x105dafb60 JSC::Wasm::EntryPlan::compileFunctions(JSC::Wasm::Plan::CompilationEffort)
15  0x105e56e50 JSC::Wasm::LLIntPlan::work(JSC::Wasm::Plan::CompilationEffort)
16  0x10628f1fc JSC::Wasm::Worklist::Thread::work()
17  0x100f9fe54 WTF::AutomaticThread::start(WTF::AbstractLocker const&)::$_0::operator()() const
18  0x100f9f2d4 WTF::Detail::CallableWrapper<WTF::AutomaticThread::start(WTF::AbstractLocker const&)::$_0, void>::call()
19  0x100fcebd4 WTF::Function<void ()>::operator()() const
20  0x1011b7734 WTF::Thread::entryPoint(WTF::Thread::NewThreadContext*)
21  0x1011d6eb8 WTF::wtfThreadEntryPoint(void*)
22  0x18de2efd4 _pthread_start
23  0x18de29d3c thread_start

[Radar WebKit Bug Importer]

<rdar://problem/78254747>

[Frédéric Wang (:fredw)]

Created attachment 430742 [details]
Reduced testcase

Testcase reduced to a Webassembly program.

[Frédéric Wang (:fredw)]

This is the disassembled output. func[0] is invalid since the function body and loop must end with an END instruction.

$ wasm-objdump -dsxh  b.wasm 

b.wasm:	file format wasm 0x1
000001e: error: function body must end with END opcode

Sections:

     Type start=0x0000000a end=0x0000000f (size=0x00000005) count: 1
 Function start=0x00000011 end=0x00000013 (size=0x00000002) count: 1
     Code start=0x00000015 end=0x0000001e (size=0x00000009) count: 1

Section Details:

Type[1]:
 - type[0] (i32) -> nil
Function[1]:
 - func[0] sig=0
Code[1]:
 - func[0] size=7

Code Disassembly:

000017 func[0]:
 000018: 20 00                      | local.get 0
 00001a: 20 00                      | local.get 0
 00001c: 03 00                      | loop type[0]

Contents of section Type:
000000a: 0160 017f 00                             .`...

Contents of section Function:
0000011: 0100                                     ..

Contents of section Code:
0000015: 0107 0020 0020 0003 00                   ... . ...

[Frédéric Wang (:fredw)]

Created attachment 430848 [details]
Reduced testcase

Same testcase with added end ops for loop/func blocks as well as drop instructions at the end of the execution to match the function signature. This still causes the assert. Preliminary debugging suggests the issue is related to having a non-void loop's block type (which leads to a splitStack call in LLIntGenerator::addLoop). wasm2wat generates an "error: expected valid block signature type" but I can't find where this is specified. Changing block type to 0x40 (void) makes wasm2wat happy and does not cause the assert.

Type[1]:
 - type[0] (i32) -> nil
Function[1]:
 - func[0] sig=0
Code[1]:
 - func[0] size=11

000017 func[0]:
 000018: 20 00                      | local.get 0
 00001a: 20 00                      | local.get 0
 00001c: 03 00                      | loop type[0]
 00001e: 0b                         | end
 00001f: 1a                         | drop
 000020: 1a                         | drop
 000021: 0b                         | end

[Frédéric Wang (:fredw)]

Created attachment 430856 [details]
Reduced testcase

[Frédéric Wang (:fredw)]

Created attachment 430871 [details]
Testcase

OK, I was using an obsolete version of wasm2wat for my testing... This new testcase is now properly converted by wasm2wat and still produces the ASSERT.

Type[1]:
 - type[0] (i32) -> nil
Function[1]:
 - func[0] sig=0
Code[1]:
 - func[0] size=11

000017 func[0]:
 000018: 20 00                      | local.get 0
 00001a: 20 00                      | local.get 0
 00001c: 03 00                      | loop type[0]
 00001e: 1a                         |   drop
 00001f: 0b                         | end
 000020: 1a                         | drop
 000021: 0b                         | end


(module
  (type (;0;) (func (param i32)))
  (func (;0;) (type 0) (param i32)
    local.get 0
    local.get 0
    loop (param i32)  ;; label = @1
      drop
    end
    drop))

[Frédéric Wang (:fredw)]

I did more debugging this morning. LLIntGenerator::addLoop starts with the following instructions:

    splitStack(signature, enclosingStack, newStack);
    materializeConstantsAndLocals(newStack);

where splitStack ends with the following instructions:

    checkConsistency();
    m_stackSize += newStack.size();

and materializeConstantsAndLocals starts with the following ones:

    if (expressionStack.isEmpty())
        return;
    checkConsistency();

So the only difference between the two checkConsistency() calls is that m_stackSize was increased back to the original size. Since walkExpressionStack relies on m_stackSize to calculate the slot index associated to an expression in the stack, this is enough to make the ASSERT fails. See reverse debugging below for details.

I'm not sure I'm familiar with the wasm code to understand the intention here. Can someone please explain and suggest how to fix that behavior?

(rr) b Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:362
(rr) rc
(rr) bt
#0  0x00007f1bfc8323c9 in JSC::Wasm::LLIntGenerator::checkConsistency()
    (this=0x7f1ba6f78ae0) at ../../Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:376
#1  0x00007f1bfc832b4a in JSC::Wasm::LLIntGenerator::materializeConstantsAndLocals(WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&) (this=0x7f1ba6f78ae0, expressionStack=...)
    at ../../Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:387
#2  0x00007f1bfc80cd31 in JSC::Wasm::LLIntGenerator::addLoop(JSC::Wasm::Signature const*, WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&, JSC::Wasm::LLIntGenerator::ControlType&, WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&, unsigned int)
(this=0x7f1ba6f78ae0, signature=0x603000379450, enclosingStack=..., block=..., newStack=..., loopIndex=0) at ../../Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:87
...
(rr) p m_parser->expressionStack().size()
$1 = 1
(rr) p m_parser->expressionStack()[0].value().isLocal()
$2 = true
(rr) p m_parser->expressionStack()[0].value().toLocal()
$3 = 16
(rr) p m_codeBlock->m_numVars
$4 = 16
(rr) p m_parser->expressionStack()[0].value() == virtualRegisterForLocal(m_stackSize.m_value - 1)
$5 = false
(rr) rc
(rr) bt
#0  JSC::Wasm::LLIntGenerator::checkConsistency() (this=0x7f1ba6f78ae0)
    at ../../Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:371
#1  0x00007f1bfc83349a in JSC::Wasm::LLIntGenerator::splitStack(JSC::Wasm::Signature const*, WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&, WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&)
    (this=0x7f1ba6f78ae0, signature=0x603000379450, enclosingStack=..., newStack=...)
    at ../../Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:411
#2  0x00007f1bfc80cd18 in JSC::Wasm::LLIntGenerator::addLoop(JSC::Wasm::Signature const*, WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&, JSC::Wasm::LLIntGenerator::ControlType&, WTF::Vector<JSC::Wasm::FunctionParser<JSC::Wasm::LLIntGenerator>::TypedExpression, 16ul, WTF::UnsafeVectorOverflow, 16ul, WTF::FastMalloc>&, unsigned int)
    (this=0x7f1ba6f78ae0, signature=0x603000379450, enclosingStack=..., block=..., newStack=..., loopIndex=0) at ../../Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:873
...
(rr) p m_parser->expressionStack().size()
$6 = 1
(rr) p m_parser->expressionStack()[0].value().isLocal()
$7 = true
(rr) p m_parser->expressionStack()[0].value().toLocal()
$8 = 16
(rr) p m_codeBlock->m_numVars
$9 = 16
(rr) p m_parser->expressionStack()[0].value() == virtualRegisterForLocal(m_stackSize.m_value - 1)
$10 = true

[Tadeu Zagallo]

Here’s some context that you might already know, but I had to page it back to understand what was going on, so I figured I might as well write it down:
- `splitStack` basically pops the arguments for the loop from the stack
- `checkConsistency` verifies that everything on the stack is either a virtual register that points to that stack position or a valid optimization. We perform 2 optimizations:
    - `move $const, tX; op tX, tY => op $const, tY`: we try to elide constant moves by keeping track of which constant is at that stack location. This is valid everywhere according to `checkConsistency`.
    - `move tX, tY; ...; op tY, tZ => op tX, tZ`: we try to elide moves from one local into another similar to what we do to constants. This requires being careful with `set_local`s to tX in between the two operations. We only do this within a block to avoid the cost of walking up the control stack on every set_local.
- `materializeConstantsAndLocals`: This is used as described above, but seems too conservative, since we don’t really need to materialize constants when we pushing a new block. We do need it for loops though, since we’ll move to those slots on back edges, otherwise we end up something like `move tX, $const` in the bytecode.

I think the issue here is that the semantics of the loop are the following:
- Pop N arguments from the stack: that’s the loop label position
- Push N arguments back to the stack: that’s the initial state to evaluate the loop body

And what the code is trying to do:
- use `splitStack` to get the arguments into newStack
- Materialize the constants and aliases in the loop arguments, since back edges will write to those slots

The issue is that we’re checking consistency as if we had added the arguments back in the stack, because that’s the loop semantics, but that will only be done by the FunctionParser when we return from addLoop, so we’re technically at an invalid state. `checkConsistency` is also not doing what we want here, since the goal is to check that the arguments we just materialized are valid, but it’s currently sort of in limbo, it’s neither in the expression stack nor in the control stack, so it won’t get validate by `checkConsistency`.

One possible way to fix this would be to have a version of `materializeConstantsAndLocals` that doesn’t check consistency (similar to what we do for `push`), but then we probably want to explicitly check the consistency of `newStack`. That could be done factoring out of the code in `checkConsistency` and explicitly passing a stack size.

[Xan Lopez]

Created attachment 431765 [details]
v1

Thanks a lot for the detailed explanation. Being optimistic I was halfway through figuring it out (already had noticed that by moving some consistency checks later on things would work, and wondering if it made sense to check the expression stack in *that* state), but your explanation saved me a lot of time. Let me know if this patch is in the good direction.

[Tadeu Zagallo]

Comment on attachment 431765 [details]
v1

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

> Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:365
> +            ASSERT(expression == slot || expression.isConstant() || expression.isArgument() || static_cast<unsigned>(expression.toLocal()) < m_codeBlock->m_numVars);

I know this is what I suggested, but I wonder if this is relevant. Because we already do the same check inside `materializeConstantsAndLocals`, and the only valid state when this is called from `addLoop` is `expression == slot`. Maybe we should just skip the consistency check for `addLoop`, wdyt? Otherwise, maybe we can inline this into `addLoop` and check only `expression == slot`?

[Xan Lopez]

Created attachment 431792 [details]
v2

v2,

yeah, that makes perfect sense, makes the patch a bit simpler and the invariants we check more clear. I changed the code and ChangeLog accordingly.

(btw, since this is not a security bug, should we unflag it as such?)

[Tadeu Zagallo]

Comment on attachment 431792 [details]
v2

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

The patch looks good to me, just a couple nits. Did you mean to r? it or is it missing anything? I think it's ok to unflag the bug.

> Source/JavaScriptCore/ChangeLog:17
> +        we'll ASSERT. To workaround this, we create a variant of

just a nit, but should it be "we'll fail the assertion"?

> Source/JavaScriptCore/wasm/WasmLLIntGenerator.cpp:880
> +    // The only valid state here is expression == slot, and we cannot

Might be worth adding a quick word here about why this is the only valid state here, since it's different than the other two assertions we have in `checkConsistency`.

[Xan Lopez]

Created attachment 431893 [details]
v3

Great, thanks, tried to fix the couple nits.

[Xan Lopez]

Created attachment 431897 [details]
v4

v4, a tiny change to the comment.

[Xan Lopez]

Created attachment 431898 [details]
v5

v5, and of course there was a typo.

[EWS]

Committed r279082 (239001@main): <https://commits.webkit.org/239001@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 431898 [details].