1/*
2 * Copyright (C) 2016 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "WasmValidate.h"
28
29#if ENABLE(WEBASSEMBLY)
30
31#include "WasmFunctionParser.h"
32#include <wtf/CommaPrinter.h>
33
34namespace JSC { namespace Wasm {
35
36class Validate {
37public:
38 class ControlData {
39 public:
40 ControlData(BlockType type, Type signature)
41 : m_blockType(type)
42 , m_signature(signature)
43 {
44 }
45
46 ControlData()
47 {
48 }
49
50 void dump(PrintStream& out) const
51 {
52 switch (type()) {
53 case BlockType::If:
54 out.print("If: ");
55 break;
56 case BlockType::Block:
57 out.print("Block: ");
58 break;
59 case BlockType::Loop:
60 out.print("Loop: ");
61 break;
62 case BlockType::TopLevel:
63 out.print("TopLevel: ");
64 break;
65 }
66 out.print(makeString(signature()));
67 }
68
69 bool hasNonVoidSignature() const { return m_signature != Void; }
70
71 BlockType type() const { return m_blockType; }
72 Type signature() const { return m_signature; }
73 Type branchTargetSignature() const { return type() == BlockType::Loop ? Void : signature(); }
74 private:
75 BlockType m_blockType;
76 Type m_signature;
77 };
78 typedef String ErrorType;
79 typedef Unexpected<ErrorType> UnexpectedResult;
80 typedef Expected<void, ErrorType> Result;
81 typedef Type ExpressionType;
82 typedef ControlData ControlType;
83 typedef Vector<ExpressionType, 1> ExpressionList;
84 typedef FunctionParser<Validate>::ControlEntry ControlEntry;
85
86 static constexpr ExpressionType emptyExpression() { return Void; }
87
88 template <typename ...Args>
89 NEVER_INLINE UnexpectedResult WARN_UNUSED_RETURN fail(Args... args) const
90 {
91 using namespace FailureHelper; // See ADL comment in WasmParser.h.
92 return UnexpectedResult(makeString("WebAssembly.Module doesn't validate: "_s, makeString(args)...));
93 }
94#define WASM_VALIDATOR_FAIL_IF(condition, ...) do { \
95 if (UNLIKELY(condition)) \
96 return fail(__VA_ARGS__); \
97 } while (0)
98
99 Result WARN_UNUSED_RETURN addArguments(const Signature&);
100 Result WARN_UNUSED_RETURN addLocal(Type, uint32_t);
101 ExpressionType addConstant(Type type, uint64_t) { return type; }
102
103 // Locals
104 Result WARN_UNUSED_RETURN getLocal(uint32_t index, ExpressionType& result);
105 Result WARN_UNUSED_RETURN setLocal(uint32_t index, ExpressionType value);
106
107 // Globals
108 Result WARN_UNUSED_RETURN getGlobal(uint32_t index, ExpressionType& result);
109 Result WARN_UNUSED_RETURN setGlobal(uint32_t index, ExpressionType value);
110
111 // Memory
112 Result WARN_UNUSED_RETURN load(LoadOpType, ExpressionType pointer, ExpressionType& result, uint32_t offset);
113 Result WARN_UNUSED_RETURN store(StoreOpType, ExpressionType pointer, ExpressionType value, uint32_t offset);
114
115 // Basic operators
116 template<OpType>
117 Result WARN_UNUSED_RETURN addOp(ExpressionType arg, ExpressionType& result);
118 template<OpType>
119 Result WARN_UNUSED_RETURN addOp(ExpressionType left, ExpressionType right, ExpressionType& result);
120 Result WARN_UNUSED_RETURN addSelect(ExpressionType condition, ExpressionType nonZero, ExpressionType zero, ExpressionType& result);
121
122 // Control flow
123 ControlData WARN_UNUSED_RETURN addTopLevel(Type signature);
124 ControlData WARN_UNUSED_RETURN addBlock(Type signature);
125 ControlData WARN_UNUSED_RETURN addLoop(Type signature);
126 Result WARN_UNUSED_RETURN addIf(ExpressionType condition, Type signature, ControlData& result);
127 Result WARN_UNUSED_RETURN addElse(ControlData&, const ExpressionList&);
128 Result WARN_UNUSED_RETURN addElseToUnreachable(ControlData&);
129
130 Result WARN_UNUSED_RETURN addReturn(ControlData& topLevel, const ExpressionList& returnValues);
131 Result WARN_UNUSED_RETURN addBranch(ControlData&, ExpressionType condition, const ExpressionList& expressionStack);
132 Result WARN_UNUSED_RETURN addSwitch(ExpressionType condition, const Vector<ControlData*>& targets, ControlData& defaultTarget, const ExpressionList& expressionStack);
133 Result WARN_UNUSED_RETURN endBlock(ControlEntry&, ExpressionList& expressionStack);
134 Result WARN_UNUSED_RETURN addEndToUnreachable(ControlEntry&);
135 Result WARN_UNUSED_RETURN addGrowMemory(ExpressionType delta, ExpressionType& result);
136 Result WARN_UNUSED_RETURN addCurrentMemory(ExpressionType& result);
137
138 Result WARN_UNUSED_RETURN addUnreachable() { return { }; }
139
140 // Calls
141 Result WARN_UNUSED_RETURN addCall(unsigned calleeIndex, const Signature&, const Vector<ExpressionType>& args, ExpressionType& result);
142 Result WARN_UNUSED_RETURN addCallIndirect(const Signature&, const Vector<ExpressionType>& args, ExpressionType& result);
143
144 ALWAYS_INLINE void didKill(ExpressionType) { }
145
146 bool hasMemory() const { return !!m_module.memory; }
147
148 Validate(const ModuleInformation& module)
149 : m_module(module)
150 {
151 }
152
153 void dump(const Vector<ControlEntry>&, const ExpressionList*);
154 void setParser(FunctionParser<Validate>*) { }
155
156private:
157 Result WARN_UNUSED_RETURN unify(const ExpressionList&, const ControlData&);
158
159 Result WARN_UNUSED_RETURN checkBranchTarget(ControlData& target, const ExpressionList& expressionStack);
160
161 Vector<Type> m_locals;
162 const ModuleInformation& m_module;
163};
164
165auto Validate::addArguments(const Signature& signature) -> Result
166{
167 for (size_t i = 0; i < signature.argumentCount(); ++i)
168 WASM_FAIL_IF_HELPER_FAILS(addLocal(signature.argument(i), 1));
169 return { };
170}
171
172auto Validate::addLocal(Type type, uint32_t count) -> Result
173{
174 size_t size = m_locals.size() + count;
175 WASM_VALIDATOR_FAIL_IF(!m_locals.tryReserveCapacity(size), "can't allocate memory for ", size, " locals");
176
177 for (uint32_t i = 0; i < count; ++i)
178 m_locals.uncheckedAppend(type);
179 return { };
180}
181
182auto Validate::getLocal(uint32_t index, ExpressionType& result) -> Result
183{
184 WASM_VALIDATOR_FAIL_IF(index >= m_locals.size(), "attempt to use unknown local ", index, " last one is ", m_locals.size());
185 result = m_locals[index];
186 return { };
187}
188
189auto Validate::setLocal(uint32_t index, ExpressionType value) -> Result
190{
191 ExpressionType localType;
192 WASM_FAIL_IF_HELPER_FAILS(getLocal(index, localType));
193 WASM_VALIDATOR_FAIL_IF(localType != value, "set_local to type ", value, " expected ", localType);
194 return { };
195}
196
197auto Validate::getGlobal(uint32_t index, ExpressionType& result) -> Result
198{
199 WASM_VALIDATOR_FAIL_IF(index >= m_module.globals.size(), "get_global ", index, " of unknown global, limit is ", m_module.globals.size());
200 result = m_module.globals[index].type;
201 ASSERT(isValueType(result));
202 return { };
203}
204
205auto Validate::setGlobal(uint32_t index, ExpressionType value) -> Result
206{
207 WASM_VALIDATOR_FAIL_IF(index >= m_module.globals.size(), "set_global ", index, " of unknown global, limit is ", m_module.globals.size());
208 WASM_VALIDATOR_FAIL_IF(m_module.globals[index].mutability == Global::Immutable, "set_global ", index, " is immutable");
209
210 ExpressionType globalType = m_module.globals[index].type;
211 ASSERT(isValueType(globalType));
212 WASM_VALIDATOR_FAIL_IF(globalType != value, "set_global ", index, " with type ", globalType, " with a variable of type ", value);
213 return { };
214}
215
216Validate::ControlType Validate::addTopLevel(Type signature)
217{
218 return ControlData(BlockType::TopLevel, signature);
219}
220
221Validate::ControlType Validate::addBlock(Type signature)
222{
223 return ControlData(BlockType::Block, signature);
224}
225
226Validate::ControlType Validate::addLoop(Type signature)
227{
228 return ControlData(BlockType::Loop, signature);
229}
230
231auto Validate::addSelect(ExpressionType condition, ExpressionType nonZero, ExpressionType zero, ExpressionType& result) -> Result
232{
233 WASM_VALIDATOR_FAIL_IF(condition != I32, "select condition must be i32, got ", condition);
234 WASM_VALIDATOR_FAIL_IF(nonZero != zero, "select result types must match, got ", nonZero, " and ", zero);
235 result = zero;
236 return { };
237}
238
239auto Validate::addIf(ExpressionType condition, Type signature, ControlType& result) -> Result
240{
241 WASM_VALIDATOR_FAIL_IF(condition != I32, "if condition must be i32, got ", condition);
242 result = ControlData(BlockType::If, signature);
243 return { };
244}
245
246auto Validate::addElse(ControlType& current, const ExpressionList& values) -> Result
247{
248 WASM_FAIL_IF_HELPER_FAILS(unify(values, current));
249 return addElseToUnreachable(current);
250}
251
252auto Validate::addElseToUnreachable(ControlType& current) -> Result
253{
254 WASM_VALIDATOR_FAIL_IF(current.type() != BlockType::If, "else block isn't associated to an if");
255 current = ControlData(BlockType::Block, current.signature());
256 return { };
257}
258
259auto Validate::addReturn(ControlType& topLevel, const ExpressionList& returnValues) -> Result
260{
261 ASSERT(topLevel.type() == BlockType::TopLevel);
262 if (topLevel.signature() == Void)
263 return { };
264 ASSERT(returnValues.size() == 1);
265 WASM_VALIDATOR_FAIL_IF(topLevel.signature() != returnValues[0], "return type ", returnValues[0], " doesn't match function's return type ", topLevel.signature());
266 return { };
267}
268
269auto Validate::checkBranchTarget(ControlType& target, const ExpressionList& expressionStack) -> Result
270{
271 if (target.branchTargetSignature() == Void)
272 return { };
273
274 WASM_VALIDATOR_FAIL_IF(expressionStack.isEmpty(), target.type() == BlockType::TopLevel ? "branch out of function" : "branch to block", " on empty expression stack, but expected ", target.signature());
275 WASM_VALIDATOR_FAIL_IF(target.branchTargetSignature() != expressionStack.last(), "branch's stack type doesn't match block's type");
276
277 return { };
278}
279
280auto Validate::addBranch(ControlType& target, ExpressionType condition, const ExpressionList& stack) -> Result
281{
282 // Void means this is an unconditional branch.
283 WASM_VALIDATOR_FAIL_IF(condition != Void && condition != I32, "conditional branch with non-i32 condition ", condition);
284 return checkBranchTarget(target, stack);
285}
286
287auto Validate::addSwitch(ExpressionType condition, const Vector<ControlData*>& targets, ControlData& defaultTarget, const ExpressionList& expressionStack) -> Result
288{
289 WASM_VALIDATOR_FAIL_IF(condition != I32, "br_table with non-i32 condition ", condition);
290
291 for (auto target : targets)
292 WASM_VALIDATOR_FAIL_IF(defaultTarget.branchTargetSignature() != target->branchTargetSignature(), "br_table target type mismatch");
293
294 return checkBranchTarget(defaultTarget, expressionStack);
295}
296
297auto Validate::addGrowMemory(ExpressionType delta, ExpressionType& result) -> Result
298{
299 WASM_VALIDATOR_FAIL_IF(delta != I32, "grow_memory with non-i32 delta");
300 result = I32;
301 return { };
302}
303
304auto Validate::addCurrentMemory(ExpressionType& result) -> Result
305{
306 result = I32;
307 return { };
308}
309
310auto Validate::endBlock(ControlEntry& entry, ExpressionList& stack) -> Result
311{
312 WASM_FAIL_IF_HELPER_FAILS(unify(stack, entry.controlData));
313 return addEndToUnreachable(entry);
314}
315
316auto Validate::addEndToUnreachable(ControlEntry& entry) -> Result
317{
318 auto block = entry.controlData;
319 if (block.signature() != Void) {
320 WASM_VALIDATOR_FAIL_IF(block.type() == BlockType::If, "If-block had a non-void result type: ", block.signature(), " but had no else-block");
321 entry.enclosedExpressionStack.append(block.signature());
322 }
323 return { };
324}
325
326auto Validate::addCall(unsigned, const Signature& signature, const Vector<ExpressionType>& args, ExpressionType& result) -> Result
327{
328 WASM_VALIDATOR_FAIL_IF(signature.argumentCount() != args.size(), "arity mismatch in call, got ", args.size(), " arguments, expected ", signature.argumentCount());
329
330 for (unsigned i = 0; i < args.size(); ++i)
331 WASM_VALIDATOR_FAIL_IF(args[i] != signature.argument(i), "argument type mismatch in call, got ", args[i], ", expected ", signature.argument(i));
332
333 result = signature.returnType();
334 return { };
335}
336
337auto Validate::addCallIndirect(const Signature& signature, const Vector<ExpressionType>& args, ExpressionType& result) -> Result
338{
339 const auto argumentCount = signature.argumentCount();
340 WASM_VALIDATOR_FAIL_IF(argumentCount != args.size() - 1, "arity mismatch in call_indirect, got ", args.size() - 1, " arguments, expected ", argumentCount);
341
342 for (unsigned i = 0; i < argumentCount; ++i)
343 WASM_VALIDATOR_FAIL_IF(args[i] != signature.argument(i), "argument type mismatch in call_indirect, got ", args[i], ", expected ", signature.argument(i));
344
345 WASM_VALIDATOR_FAIL_IF(args.last() != I32, "non-i32 call_indirect index ", args.last());
346
347 result = signature.returnType();
348 return { };
349}
350
351auto Validate::unify(const ExpressionList& values, const ControlType& block) -> Result
352{
353 if (block.signature() == Void) {
354 WASM_VALIDATOR_FAIL_IF(!values.isEmpty(), "void block should end with an empty stack");
355 return { };
356 }
357
358 WASM_VALIDATOR_FAIL_IF(values.size() != 1, "block with type: ", block.signature(), " ends with a stack containing more than one value");
359 WASM_VALIDATOR_FAIL_IF(values[0] != block.signature(), "control flow returns with unexpected type");
360 return { };
361}
362
363static void dumpExpressionStack(const CommaPrinter& comma, const Validate::ExpressionList& expressionStack)
364{
365 dataLog(comma, " ExpressionStack:");
366 for (const auto& expression : expressionStack)
367 dataLog(comma, makeString(expression));
368}
369
370void Validate::dump(const Vector<ControlEntry>& controlStack, const ExpressionList* expressionStack)
371{
372 for (size_t i = controlStack.size(); i--;) {
373 dataLog(" ", controlStack[i].controlData);
374 CommaPrinter comma(", ", "");
375 dumpExpressionStack(comma, *expressionStack);
376 expressionStack = &controlStack[i].enclosedExpressionStack;
377 dataLogLn();
378 }
379 dataLogLn();
380}
381
382Expected<void, String> validateFunction(const uint8_t* source, size_t length, const Signature& signature, const ModuleInformation& module)
383{
384 Validate context(module);
385 FunctionParser<Validate> validator(context, source, length, signature, module);
386 WASM_FAIL_IF_HELPER_FAILS(validator.parse());
387 return { };
388}
389
390} } // namespace JSC::Wasm
391
392#include "WasmValidateInlines.h"
393
394#endif // ENABLE(WEBASSEMBLY)
395