1 // Copyright 2015 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef V8_WASM_AST_DECODER_H_
6 #define V8_WASM_AST_DECODER_H_
7
8 #include "src/base/compiler-specific.h"
9 #include "src/globals.h"
10 #include "src/signature.h"
11 #include "src/wasm/decoder.h"
12 #include "src/wasm/wasm-opcodes.h"
13 #include "src/wasm/wasm-result.h"
14
15 namespace v8 {
16 namespace internal {
17
18 class BitVector; // forward declaration
19
20 namespace compiler { // external declarations from compiler.
21 class WasmGraphBuilder;
22 }
23
24 namespace wasm {
25
26 const uint32_t kMaxNumWasmLocals = 8000000;
27 struct WasmGlobal;
28
29 // Helpers for decoding different kinds of operands which follow bytecodes.
30 struct LocalIndexOperand {
31 uint32_t index;
32 LocalType type;
33 unsigned length;
34
LocalIndexOperandLocalIndexOperand35 inline LocalIndexOperand(Decoder* decoder, const byte* pc) {
36 index = decoder->checked_read_u32v(pc, 1, &length, "local index");
37 type = kAstStmt;
38 }
39 };
40
41 struct ImmI8Operand {
42 int8_t value;
43 unsigned length;
ImmI8OperandImmI8Operand44 inline ImmI8Operand(Decoder* decoder, const byte* pc) {
45 value = bit_cast<int8_t>(decoder->checked_read_u8(pc, 1, "immi8"));
46 length = 1;
47 }
48 };
49
50 struct ImmI32Operand {
51 int32_t value;
52 unsigned length;
ImmI32OperandImmI32Operand53 inline ImmI32Operand(Decoder* decoder, const byte* pc) {
54 value = decoder->checked_read_i32v(pc, 1, &length, "immi32");
55 }
56 };
57
58 struct ImmI64Operand {
59 int64_t value;
60 unsigned length;
ImmI64OperandImmI64Operand61 inline ImmI64Operand(Decoder* decoder, const byte* pc) {
62 value = decoder->checked_read_i64v(pc, 1, &length, "immi64");
63 }
64 };
65
66 struct ImmF32Operand {
67 float value;
68 unsigned length;
ImmF32OperandImmF32Operand69 inline ImmF32Operand(Decoder* decoder, const byte* pc) {
70 value = bit_cast<float>(decoder->checked_read_u32(pc, 1, "immf32"));
71 length = 4;
72 }
73 };
74
75 struct ImmF64Operand {
76 double value;
77 unsigned length;
ImmF64OperandImmF64Operand78 inline ImmF64Operand(Decoder* decoder, const byte* pc) {
79 value = bit_cast<double>(decoder->checked_read_u64(pc, 1, "immf64"));
80 length = 8;
81 }
82 };
83
84 struct GlobalIndexOperand {
85 uint32_t index;
86 LocalType type;
87 const WasmGlobal* global;
88 unsigned length;
89
GlobalIndexOperandGlobalIndexOperand90 inline GlobalIndexOperand(Decoder* decoder, const byte* pc) {
91 index = decoder->checked_read_u32v(pc, 1, &length, "global index");
92 global = nullptr;
93 type = kAstStmt;
94 }
95 };
96
97 struct BlockTypeOperand {
98 uint32_t arity;
99 const byte* types; // pointer to encoded types for the block.
100 unsigned length;
101
BlockTypeOperandBlockTypeOperand102 inline BlockTypeOperand(Decoder* decoder, const byte* pc) {
103 uint8_t val = decoder->checked_read_u8(pc, 1, "block type");
104 LocalType type = kAstStmt;
105 length = 1;
106 arity = 0;
107 types = nullptr;
108 if (decode_local_type(val, &type)) {
109 arity = type == kAstStmt ? 0 : 1;
110 types = pc + 1;
111 } else {
112 // Handle multi-value blocks.
113 if (!FLAG_wasm_mv_prototype) {
114 decoder->error(pc, pc + 1, "invalid block arity > 1");
115 return;
116 }
117 if (val != kMultivalBlock) {
118 decoder->error(pc, pc + 1, "invalid block type");
119 return;
120 }
121 // Decode and check the types vector of the block.
122 unsigned len = 0;
123 uint32_t count = decoder->checked_read_u32v(pc, 2, &len, "block arity");
124 // {count} is encoded as {arity-2}, so that a {0} count here corresponds
125 // to a block with 2 values. This makes invalid/redundant encodings
126 // impossible.
127 arity = count + 2;
128 length = 1 + len + arity;
129 types = pc + 1 + 1 + len;
130
131 for (uint32_t i = 0; i < arity; i++) {
132 uint32_t offset = 1 + 1 + len + i;
133 val = decoder->checked_read_u8(pc, offset, "block type");
134 decode_local_type(val, &type);
135 if (type == kAstStmt) {
136 decoder->error(pc, pc + offset, "invalid block type");
137 return;
138 }
139 }
140 }
141 }
142 // Decode a byte representing a local type. Return {false} if the encoded
143 // byte was invalid or {kMultivalBlock}.
decode_local_typeBlockTypeOperand144 bool decode_local_type(uint8_t val, LocalType* result) {
145 switch (static_cast<LocalTypeCode>(val)) {
146 case kLocalVoid:
147 *result = kAstStmt;
148 return true;
149 case kLocalI32:
150 *result = kAstI32;
151 return true;
152 case kLocalI64:
153 *result = kAstI64;
154 return true;
155 case kLocalF32:
156 *result = kAstF32;
157 return true;
158 case kLocalF64:
159 *result = kAstF64;
160 return true;
161 case kLocalS128:
162 *result = kAstS128;
163 return true;
164 default:
165 *result = kAstStmt;
166 return false;
167 }
168 }
read_entryBlockTypeOperand169 LocalType read_entry(unsigned index) {
170 DCHECK_LT(index, arity);
171 LocalType result;
172 CHECK(decode_local_type(types[index], &result));
173 return result;
174 }
175 };
176
177 struct Control;
178 struct BreakDepthOperand {
179 uint32_t depth;
180 Control* target;
181 unsigned length;
BreakDepthOperandBreakDepthOperand182 inline BreakDepthOperand(Decoder* decoder, const byte* pc) {
183 depth = decoder->checked_read_u32v(pc, 1, &length, "break depth");
184 target = nullptr;
185 }
186 };
187
188 struct CallIndirectOperand {
189 uint32_t table_index;
190 uint32_t index;
191 FunctionSig* sig;
192 unsigned length;
CallIndirectOperandCallIndirectOperand193 inline CallIndirectOperand(Decoder* decoder, const byte* pc) {
194 unsigned len = 0;
195 index = decoder->checked_read_u32v(pc, 1, &len, "signature index");
196 table_index = decoder->checked_read_u8(pc, 1 + len, "table index");
197 if (table_index != 0) {
198 decoder->error(pc, pc + 1 + len, "expected table index 0, found %u",
199 table_index);
200 }
201 length = 1 + len;
202 sig = nullptr;
203 }
204 };
205
206 struct CallFunctionOperand {
207 uint32_t index;
208 FunctionSig* sig;
209 unsigned length;
CallFunctionOperandCallFunctionOperand210 inline CallFunctionOperand(Decoder* decoder, const byte* pc) {
211 unsigned len1 = 0;
212 unsigned len2 = 0;
213 index = decoder->checked_read_u32v(pc, 1 + len1, &len2, "function index");
214 length = len1 + len2;
215 sig = nullptr;
216 }
217 };
218
219 struct MemoryIndexOperand {
220 uint32_t index;
221 unsigned length;
MemoryIndexOperandMemoryIndexOperand222 inline MemoryIndexOperand(Decoder* decoder, const byte* pc) {
223 index = decoder->checked_read_u8(pc, 1, "memory index");
224 if (index != 0) {
225 decoder->error(pc, pc + 1, "expected memory index 0, found %u", index);
226 }
227 length = 1;
228 }
229 };
230
231 struct BranchTableOperand {
232 uint32_t table_count;
233 const byte* start;
234 const byte* table;
BranchTableOperandBranchTableOperand235 inline BranchTableOperand(Decoder* decoder, const byte* pc) {
236 DCHECK_EQ(kExprBrTable, decoder->checked_read_u8(pc, 0, "opcode"));
237 start = pc + 1;
238 unsigned len1 = 0;
239 table_count = decoder->checked_read_u32v(pc, 1, &len1, "table count");
240 if (table_count > (UINT_MAX / sizeof(uint32_t)) - 1 ||
241 len1 > UINT_MAX - (table_count + 1) * sizeof(uint32_t)) {
242 decoder->error(pc, "branch table size overflow");
243 }
244 table = pc + 1 + len1;
245 }
read_entryBranchTableOperand246 inline uint32_t read_entry(Decoder* decoder, unsigned i) {
247 DCHECK(i <= table_count);
248 return table ? decoder->read_u32(table + i * sizeof(uint32_t)) : 0;
249 }
250 };
251
252 // A helper to iterate over a branch table.
253 class BranchTableIterator {
254 public:
cur_index()255 unsigned cur_index() { return index_; }
has_next()256 bool has_next() { return decoder_->ok() && index_ <= table_count_; }
next()257 uint32_t next() {
258 DCHECK(has_next());
259 index_++;
260 unsigned length = 0;
261 uint32_t result =
262 decoder_->checked_read_u32v(pc_, 0, &length, "branch table entry");
263 pc_ += length;
264 return result;
265 }
266 // length, including the length of the {BranchTableOperand}, but not the
267 // opcode.
length()268 unsigned length() {
269 while (has_next()) next();
270 return static_cast<unsigned>(pc_ - start_);
271 }
pc()272 const byte* pc() { return pc_; }
273
BranchTableIterator(Decoder * decoder,BranchTableOperand & operand)274 BranchTableIterator(Decoder* decoder, BranchTableOperand& operand)
275 : decoder_(decoder),
276 start_(operand.start),
277 pc_(operand.table),
278 index_(0),
279 table_count_(operand.table_count) {}
280
281 private:
282 Decoder* decoder_;
283 const byte* start_;
284 const byte* pc_;
285 uint32_t index_; // the current index.
286 uint32_t table_count_; // the count of entries, not including default.
287 };
288
289 struct MemoryAccessOperand {
290 uint32_t alignment;
291 uint32_t offset;
292 unsigned length;
MemoryAccessOperandMemoryAccessOperand293 inline MemoryAccessOperand(Decoder* decoder, const byte* pc,
294 uint32_t max_alignment) {
295 unsigned alignment_length;
296 alignment =
297 decoder->checked_read_u32v(pc, 1, &alignment_length, "alignment");
298 if (max_alignment < alignment) {
299 decoder->error(pc, pc + 1,
300 "invalid alignment; expected maximum alignment is %u, "
301 "actual alignment is %u",
302 max_alignment, alignment);
303 }
304 unsigned offset_length;
305 offset = decoder->checked_read_u32v(pc, 1 + alignment_length,
306 &offset_length, "offset");
307 length = alignment_length + offset_length;
308 }
309 };
310
311 typedef compiler::WasmGraphBuilder TFBuilder;
312 struct ModuleEnv; // forward declaration of module interface.
313
314 // All of the various data structures necessary to decode a function body.
315 struct FunctionBody {
316 ModuleEnv* module; // module environment
317 FunctionSig* sig; // function signature
318 const byte* base; // base of the module bytes, for error reporting
319 const byte* start; // start of the function body
320 const byte* end; // end of the function body
321 };
322
FunctionBodyForTesting(const byte * start,const byte * end)323 static inline FunctionBody FunctionBodyForTesting(const byte* start,
324 const byte* end) {
325 return {nullptr, nullptr, start, start, end};
326 }
327
328 struct DecodeStruct {
329 int unused;
330 };
331 typedef Result<DecodeStruct*> DecodeResult;
332 inline std::ostream& operator<<(std::ostream& os, const DecodeStruct& tree) {
333 return os;
334 }
335
336 V8_EXPORT_PRIVATE DecodeResult VerifyWasmCode(AccountingAllocator* allocator,
337 FunctionBody& body);
338 DecodeResult BuildTFGraph(AccountingAllocator* allocator, TFBuilder* builder,
339 FunctionBody& body);
340 bool PrintAst(AccountingAllocator* allocator, const FunctionBody& body,
341 std::ostream& os,
342 std::vector<std::tuple<uint32_t, int, int>>* offset_table);
343
344 // A simplified form of AST printing, e.g. from a debugger.
345 void PrintAstForDebugging(const byte* start, const byte* end);
346
VerifyWasmCode(AccountingAllocator * allocator,ModuleEnv * module,FunctionSig * sig,const byte * start,const byte * end)347 inline DecodeResult VerifyWasmCode(AccountingAllocator* allocator,
348 ModuleEnv* module, FunctionSig* sig,
349 const byte* start, const byte* end) {
350 FunctionBody body = {module, sig, nullptr, start, end};
351 return VerifyWasmCode(allocator, body);
352 }
353
BuildTFGraph(AccountingAllocator * allocator,TFBuilder * builder,ModuleEnv * module,FunctionSig * sig,const byte * start,const byte * end)354 inline DecodeResult BuildTFGraph(AccountingAllocator* allocator,
355 TFBuilder* builder, ModuleEnv* module,
356 FunctionSig* sig, const byte* start,
357 const byte* end) {
358 FunctionBody body = {module, sig, nullptr, start, end};
359 return BuildTFGraph(allocator, builder, body);
360 }
361
362 struct AstLocalDecls {
363 // The size of the encoded declarations.
364 uint32_t decls_encoded_size; // size of encoded declarations
365
366 // Total number of locals.
367 uint32_t total_local_count;
368
369 // List of {local type, count} pairs.
370 ZoneVector<std::pair<LocalType, uint32_t>> local_types;
371
372 // Constructor initializes the vector.
AstLocalDeclsAstLocalDecls373 explicit AstLocalDecls(Zone* zone)
374 : decls_encoded_size(0), total_local_count(0), local_types(zone) {}
375 };
376
377 V8_EXPORT_PRIVATE bool DecodeLocalDecls(AstLocalDecls& decls, const byte* start,
378 const byte* end);
379 V8_EXPORT_PRIVATE BitVector* AnalyzeLoopAssignmentForTesting(Zone* zone,
380 size_t num_locals,
381 const byte* start,
382 const byte* end);
383
384 // Computes the length of the opcode at the given address.
385 V8_EXPORT_PRIVATE unsigned OpcodeLength(const byte* pc, const byte* end);
386
387 // A simple forward iterator for bytecodes.
NON_EXPORTED_BASE(Decoder)388 class V8_EXPORT_PRIVATE BytecodeIterator : public NON_EXPORTED_BASE(Decoder) {
389 public:
390 // If one wants to iterate over the bytecode without looking at {pc_offset()}.
391 class iterator {
392 public:
393 inline iterator& operator++() {
394 DCHECK_LT(ptr_, end_);
395 ptr_ += OpcodeLength(ptr_, end_);
396 return *this;
397 }
398 inline WasmOpcode operator*() {
399 DCHECK_LT(ptr_, end_);
400 return static_cast<WasmOpcode>(*ptr_);
401 }
402 inline bool operator==(const iterator& that) {
403 return this->ptr_ == that.ptr_;
404 }
405 inline bool operator!=(const iterator& that) {
406 return this->ptr_ != that.ptr_;
407 }
408
409 private:
410 friend class BytecodeIterator;
411 const byte* ptr_;
412 const byte* end_;
413 iterator(const byte* ptr, const byte* end) : ptr_(ptr), end_(end) {}
414 };
415
416 // Create a new {BytecodeIterator}. If the {decls} pointer is non-null,
417 // assume the bytecode starts with local declarations and decode them.
418 // Otherwise, do not decode local decls.
419 BytecodeIterator(const byte* start, const byte* end,
420 AstLocalDecls* decls = nullptr);
421
422 inline iterator begin() const { return iterator(pc_, end_); }
423 inline iterator end() const { return iterator(end_, end_); }
424
425 WasmOpcode current() {
426 return static_cast<WasmOpcode>(
427 checked_read_u8(pc_, 0, "expected bytecode"));
428 }
429
430 void next() {
431 if (pc_ < end_) {
432 pc_ += OpcodeLength(pc_, end_);
433 if (pc_ >= end_) pc_ = end_;
434 }
435 }
436
437 bool has_next() { return pc_ < end_; }
438 };
439
440 } // namespace wasm
441 } // namespace internal
442 } // namespace v8
443
444 #endif // V8_WASM_AST_DECODER_H_
445