Home | History | Annotate | Download | only in wasm 
      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 
     35   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;
     44   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;
     53   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;
     61   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;
     69   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;
     78   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 
     90   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 
    102   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}.
    144   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   }
    169   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;
    182   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;
    193   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;
    210   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;
    222   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;
    235   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   }
    246   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:
    255   unsigned cur_index() { return index_; }
    256   bool has_next() { return decoder_->ok() && index_ <= table_count_; }
    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.
    268   unsigned length() {
    269     while (has_next()) next();
    270     return static_cast<unsigned>(pc_ - start_);
    271   }
    272   const byte* pc() { return pc_; }
    273 
    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;
    293   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 
    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 
    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 
    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.
    373   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.
    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