• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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_DECODER_H_
6 #define V8_WASM_DECODER_H_
7 
8 #include <cstdarg>
9 #include <memory>
10 
11 #include "src/base/compiler-specific.h"
12 #include "src/flags.h"
13 #include "src/signature.h"
14 #include "src/v8memory.h"
15 #include "src/wasm/wasm-result.h"
16 #include "src/zone/zone-containers.h"
17 
18 namespace v8 {
19 namespace internal {
20 namespace wasm {
21 
22 #define TRACE(...)                                    \
23   do {                                                \
24     if (FLAG_trace_wasm_decoder) PrintF(__VA_ARGS__); \
25   } while (false)
26 #define TRACE_IF(cond, ...)                                     \
27   do {                                                          \
28     if (FLAG_trace_wasm_decoder && (cond)) PrintF(__VA_ARGS__); \
29   } while (false)
30 
31 // A {DecodeResult} only stores the failure / success status, but no data. Thus
32 // we use {nullptr_t} as data value, such that the only valid data stored in
33 // this type is a nullptr.
34 // Storing {void} would require template specialization.
35 using DecodeResult = Result<std::nullptr_t>;
36 
37 // A helper utility to decode bytes, integers, fields, varints, etc, from
38 // a buffer of bytes.
39 class Decoder {
40  public:
41   enum ValidateFlag : bool { kValidate = true, kNoValidate = false };
42 
43   enum AdvancePCFlag : bool { kAdvancePc = true, kNoAdvancePc = false };
44 
45   enum TraceFlag : bool { kTrace = true, kNoTrace = false };
46 
47   Decoder(const byte* start, const byte* end, uint32_t buffer_offset = 0)
Decoder(start,start,end,buffer_offset)48       : Decoder(start, start, end, buffer_offset) {}
49   explicit Decoder(const Vector<const byte> bytes, uint32_t buffer_offset = 0)
50       : Decoder(bytes.start(), bytes.start() + bytes.length(), buffer_offset) {}
51   Decoder(const byte* start, const byte* pc, const byte* end,
52           uint32_t buffer_offset = 0)
start_(start)53       : start_(start), pc_(pc), end_(end), buffer_offset_(buffer_offset) {
54     DCHECK_LE(start, pc);
55     DCHECK_LE(pc, end);
56     DCHECK_EQ(static_cast<uint32_t>(end - start), end - start);
57   }
58 
~Decoder()59   virtual ~Decoder() {}
60 
validate_size(const byte * pc,uint32_t length,const char * msg)61   inline bool validate_size(const byte* pc, uint32_t length, const char* msg) {
62     DCHECK_LE(start_, pc);
63     DCHECK_LE(pc, end_);
64     if (V8_UNLIKELY(length > static_cast<uint32_t>(end_ - pc))) {
65       error(pc, msg);
66       return false;
67     }
68     return true;
69   }
70 
71   // Reads an 8-bit unsigned integer.
72   template <ValidateFlag validate>
73   inline uint8_t read_u8(const byte* pc, const char* msg = "expected 1 byte") {
74     return read_little_endian<uint8_t, validate>(pc, msg);
75   }
76 
77   // Reads a 16-bit unsigned integer (little endian).
78   template <ValidateFlag validate>
79   inline uint16_t read_u16(const byte* pc,
80                            const char* msg = "expected 2 bytes") {
81     return read_little_endian<uint16_t, validate>(pc, msg);
82   }
83 
84   // Reads a 32-bit unsigned integer (little endian).
85   template <ValidateFlag validate>
86   inline uint32_t read_u32(const byte* pc,
87                            const char* msg = "expected 4 bytes") {
88     return read_little_endian<uint32_t, validate>(pc, msg);
89   }
90 
91   // Reads a 64-bit unsigned integer (little endian).
92   template <ValidateFlag validate>
93   inline uint64_t read_u64(const byte* pc,
94                            const char* msg = "expected 8 bytes") {
95     return read_little_endian<uint64_t, validate>(pc, msg);
96   }
97 
98   // Reads a variable-length unsigned integer (little endian).
99   template <ValidateFlag validate>
100   uint32_t read_u32v(const byte* pc, uint32_t* length,
101                      const char* name = "LEB32") {
102     return read_leb<uint32_t, validate, kNoAdvancePc, kNoTrace>(pc, length,
103                                                                 name);
104   }
105 
106   // Reads a variable-length signed integer (little endian).
107   template <ValidateFlag validate>
108   int32_t read_i32v(const byte* pc, uint32_t* length,
109                     const char* name = "signed LEB32") {
110     return read_leb<int32_t, validate, kNoAdvancePc, kNoTrace>(pc, length,
111                                                                name);
112   }
113 
114   // Reads a variable-length unsigned integer (little endian).
115   template <ValidateFlag validate>
116   uint64_t read_u64v(const byte* pc, uint32_t* length,
117                      const char* name = "LEB64") {
118     return read_leb<uint64_t, validate, kNoAdvancePc, kNoTrace>(pc, length,
119                                                                 name);
120   }
121 
122   // Reads a variable-length signed integer (little endian).
123   template <ValidateFlag validate>
124   int64_t read_i64v(const byte* pc, uint32_t* length,
125                     const char* name = "signed LEB64") {
126     return read_leb<int64_t, validate, kNoAdvancePc, kNoTrace>(pc, length,
127                                                                name);
128   }
129 
130   // Reads a 8-bit unsigned integer (byte) and advances {pc_}.
131   uint8_t consume_u8(const char* name = "uint8_t") {
132     return consume_little_endian<uint8_t>(name);
133   }
134 
135   // Reads a 16-bit unsigned integer (little endian) and advances {pc_}.
136   uint16_t consume_u16(const char* name = "uint16_t") {
137     return consume_little_endian<uint16_t>(name);
138   }
139 
140   // Reads a single 32-bit unsigned integer (little endian) and advances {pc_}.
141   uint32_t consume_u32(const char* name = "uint32_t") {
142     return consume_little_endian<uint32_t>(name);
143   }
144 
145   // Reads a LEB128 variable-length unsigned 32-bit integer and advances {pc_}.
146   uint32_t consume_u32v(const char* name = nullptr) {
147     uint32_t length = 0;
148     return read_leb<uint32_t, kValidate, kAdvancePc, kTrace>(pc_, &length,
149                                                              name);
150   }
151 
152   // Reads a LEB128 variable-length signed 32-bit integer and advances {pc_}.
153   int32_t consume_i32v(const char* name = nullptr) {
154     uint32_t length = 0;
155     return read_leb<int32_t, kValidate, kAdvancePc, kTrace>(pc_, &length, name);
156   }
157 
158   // Consume {size} bytes and send them to the bit bucket, advancing {pc_}.
159   void consume_bytes(uint32_t size, const char* name = "skip") {
160     // Only trace if the name is not null.
161     TRACE_IF(name, "  +%u  %-20s: %u bytes\n", pc_offset(), name, size);
162     if (checkAvailable(size)) {
163       pc_ += size;
164     } else {
165       pc_ = end_;
166     }
167   }
168 
169   // Check that at least {size} bytes exist between {pc_} and {end_}.
checkAvailable(uint32_t size)170   bool checkAvailable(uint32_t size) {
171     DCHECK_LE(pc_, end_);
172     if (V8_UNLIKELY(size > static_cast<uint32_t>(end_ - pc_))) {
173       errorf(pc_, "expected %u bytes, fell off end", size);
174       return false;
175     }
176     return true;
177   }
178 
error(const char * msg)179   void error(const char* msg) { errorf(pc_, "%s", msg); }
180 
error(const byte * pc,const char * msg)181   void error(const byte* pc, const char* msg) { errorf(pc, "%s", msg); }
182 
183   // Sets internal error state.
errorf(const byte * pc,const char * format,...)184   void PRINTF_FORMAT(3, 4) errorf(const byte* pc, const char* format, ...) {
185     // Only report the first error.
186     if (!ok()) return;
187 #if DEBUG
188     if (FLAG_wasm_break_on_decoder_error) {
189       base::OS::DebugBreak();
190     }
191 #endif
192     constexpr int kMaxErrorMsg = 256;
193     EmbeddedVector<char, kMaxErrorMsg> buffer;
194     va_list arguments;
195     va_start(arguments, format);
196     int len = VSNPrintF(buffer, format, arguments);
197     CHECK_LT(0, len);
198     va_end(arguments);
199     error_msg_.assign(buffer.start(), len);
200     DCHECK_GE(pc, start_);
201     error_offset_ = static_cast<uint32_t>(pc - start_) + buffer_offset_;
202     onFirstError();
203   }
204 
205   // Behavior triggered on first error, overridden in subclasses.
onFirstError()206   virtual void onFirstError() {}
207 
208   // Debugging helper to print a bytes range as hex bytes.
traceByteRange(const byte * start,const byte * end)209   void traceByteRange(const byte* start, const byte* end) {
210     DCHECK_LE(start, end);
211     for (const byte* p = start; p < end; ++p) TRACE("%02x ", *p);
212   }
213 
214   // Debugging helper to print bytes up to the end.
traceOffEnd()215   void traceOffEnd() {
216     traceByteRange(pc_, end_);
217     TRACE("<end>\n");
218   }
219 
220   // Converts the given value to a {Result}, copying the error if necessary.
221   template <typename T, typename U = typename std::remove_reference<T>::type>
toResult(T && val)222   Result<U> toResult(T&& val) {
223     Result<U> result(std::forward<T>(val));
224     if (failed()) {
225       TRACE("Result error: %s\n", error_msg_.c_str());
226       result.error(error_offset_, std::move(error_msg_));
227     }
228     return result;
229   }
230 
231   // Resets the boundaries of this decoder.
232   void Reset(const byte* start, const byte* end, uint32_t buffer_offset = 0) {
233     DCHECK_LE(start, end);
234     DCHECK_EQ(static_cast<uint32_t>(end - start), end - start);
235     start_ = start;
236     pc_ = start;
237     end_ = end;
238     buffer_offset_ = buffer_offset;
239     error_offset_ = 0;
240     error_msg_.clear();
241   }
242 
243   void Reset(Vector<const uint8_t> bytes, uint32_t buffer_offset = 0) {
244     Reset(bytes.begin(), bytes.end(), buffer_offset);
245   }
246 
ok()247   bool ok() const { return error_msg_.empty(); }
failed()248   bool failed() const { return !ok(); }
more()249   bool more() const { return pc_ < end_; }
250 
start()251   const byte* start() const { return start_; }
pc()252   const byte* pc() const { return pc_; }
position()253   uint32_t position() const { return static_cast<uint32_t>(pc_ - start_); }
pc_offset()254   uint32_t pc_offset() const {
255     return static_cast<uint32_t>(pc_ - start_) + buffer_offset_;
256   }
buffer_offset()257   uint32_t buffer_offset() const { return buffer_offset_; }
258   // Takes an offset relative to the module start and returns an offset relative
259   // to the current buffer of the decoder.
GetBufferRelativeOffset(uint32_t offset)260   uint32_t GetBufferRelativeOffset(uint32_t offset) const {
261     DCHECK_LE(buffer_offset_, offset);
262     return offset - buffer_offset_;
263   }
end()264   const byte* end() const { return end_; }
265 
266  protected:
267   const byte* start_;
268   const byte* pc_;
269   const byte* end_;
270   // The offset of the current buffer in the module. Needed for streaming.
271   uint32_t buffer_offset_;
272   uint32_t error_offset_ = 0;
273   std::string error_msg_;
274 
275  private:
276   template <typename IntType, bool validate>
read_little_endian(const byte * pc,const char * msg)277   inline IntType read_little_endian(const byte* pc, const char* msg) {
278     if (!validate) {
279       DCHECK(validate_size(pc, sizeof(IntType), msg));
280     } else if (!validate_size(pc, sizeof(IntType), msg)) {
281       return IntType{0};
282     }
283     return ReadLittleEndianValue<IntType>(reinterpret_cast<Address>(pc));
284   }
285 
286   template <typename IntType>
consume_little_endian(const char * name)287   inline IntType consume_little_endian(const char* name) {
288     TRACE("  +%u  %-20s: ", pc_offset(), name);
289     if (!checkAvailable(sizeof(IntType))) {
290       traceOffEnd();
291       pc_ = end_;
292       return IntType{0};
293     }
294     IntType val = read_little_endian<IntType, false>(pc_, name);
295     traceByteRange(pc_, pc_ + sizeof(IntType));
296     TRACE("= %d\n", val);
297     pc_ += sizeof(IntType);
298     return val;
299   }
300 
301   template <typename IntType, ValidateFlag validate, AdvancePCFlag advance_pc,
302             TraceFlag trace>
303   inline IntType read_leb(const byte* pc, uint32_t* length,
304                           const char* name = "varint") {
305     DCHECK_IMPLIES(advance_pc, pc == pc_);
306     TRACE_IF(trace, "  +%u  %-20s: ", pc_offset(), name);
307     return read_leb_tail<IntType, validate, advance_pc, trace, 0>(pc, length,
308                                                                   name, 0);
309   }
310 
311   template <typename IntType, ValidateFlag validate, AdvancePCFlag advance_pc,
312             TraceFlag trace, int byte_index>
read_leb_tail(const byte * pc,uint32_t * length,const char * name,IntType result)313   IntType read_leb_tail(const byte* pc, uint32_t* length, const char* name,
314                         IntType result) {
315     constexpr bool is_signed = std::is_signed<IntType>::value;
316     constexpr int kMaxLength = (sizeof(IntType) * 8 + 6) / 7;
317     static_assert(byte_index < kMaxLength, "invalid template instantiation");
318     constexpr int shift = byte_index * 7;
319     constexpr bool is_last_byte = byte_index == kMaxLength - 1;
320     DCHECK_LE(pc, end_);
321     const bool at_end = validate && pc == end_;
322     byte b = 0;
323     if (!at_end) {
324       DCHECK_LT(pc, end_);
325       b = *pc;
326       TRACE_IF(trace, "%02x ", b);
327       result = result | ((static_cast<IntType>(b) & 0x7f) << shift);
328     }
329     if (!is_last_byte && (b & 0x80)) {
330       // Make sure that we only instantiate the template for valid byte indexes.
331       // Compilers are not smart enough to figure out statically that the
332       // following call is unreachable if is_last_byte is false.
333       constexpr int next_byte_index = byte_index + (is_last_byte ? 0 : 1);
334       return read_leb_tail<IntType, validate, advance_pc, trace,
335                            next_byte_index>(pc + 1, length, name, result);
336     }
337     if (advance_pc) pc_ = pc + (at_end ? 0 : 1);
338     *length = byte_index + (at_end ? 0 : 1);
339     if (validate && (at_end || (b & 0x80))) {
340       TRACE_IF(trace, at_end ? "<end> " : "<length overflow> ");
341       errorf(pc, "expected %s", name);
342       result = 0;
343     }
344     if (is_last_byte) {
345       // A signed-LEB128 must sign-extend the final byte, excluding its
346       // most-significant bit; e.g. for a 32-bit LEB128:
347       //   kExtraBits = 4  (== 32 - (5-1) * 7)
348       // For unsigned values, the extra bits must be all zero.
349       // For signed values, the extra bits *plus* the most significant bit must
350       // either be 0, or all ones.
351       constexpr int kExtraBits = (sizeof(IntType) * 8) - ((kMaxLength - 1) * 7);
352       constexpr int kSignExtBits = kExtraBits - (is_signed ? 1 : 0);
353       const byte checked_bits = b & (0xFF << kSignExtBits);
354       constexpr byte kSignExtendedExtraBits = 0x7f & (0xFF << kSignExtBits);
355       bool valid_extra_bits =
356           checked_bits == 0 ||
357           (is_signed && checked_bits == kSignExtendedExtraBits);
358       if (!validate) {
359         DCHECK(valid_extra_bits);
360       } else if (!valid_extra_bits) {
361         error(pc, "extra bits in varint");
362         result = 0;
363       }
364     }
365     constexpr int sign_ext_shift =
366         is_signed ? Max(0, int{8 * sizeof(IntType)} - shift - 7) : 0;
367     // Perform sign extension.
368     result = (result << sign_ext_shift) >> sign_ext_shift;
369     if (trace && is_signed) {
370       TRACE("= %" PRIi64 "\n", static_cast<int64_t>(result));
371     } else if (trace) {
372       TRACE("= %" PRIu64 "\n", static_cast<uint64_t>(result));
373     }
374     return result;
375   }
376 };
377 
378 // Reference to a string in the wire bytes.
379 class WireBytesRef {
380  public:
WireBytesRef()381   WireBytesRef() : WireBytesRef(0, 0) {}
WireBytesRef(uint32_t offset,uint32_t length)382   WireBytesRef(uint32_t offset, uint32_t length)
383       : offset_(offset), length_(length) {
384     DCHECK_IMPLIES(offset_ == 0, length_ == 0);
385     DCHECK_LE(offset_, offset_ + length_);  // no uint32_t overflow.
386   }
387 
offset()388   uint32_t offset() const { return offset_; }
length()389   uint32_t length() const { return length_; }
end_offset()390   uint32_t end_offset() const { return offset_ + length_; }
is_empty()391   bool is_empty() const { return length_ == 0; }
is_set()392   bool is_set() const { return offset_ != 0; }
393 
394  private:
395   uint32_t offset_;
396   uint32_t length_;
397 };
398 
399 #undef TRACE
400 }  // namespace wasm
401 }  // namespace internal
402 }  // namespace v8
403 
404 #endif  // V8_WASM_DECODER_H_
405