Implement bulk memory in the interpreter (#1074)

* Implement bulk memory in interpreter

* Read/Write elem_type in element segments
  * Binary format
  * Text format (`(elem passive funcref...)`)
* Add DataSegment runtime objects
* Only initialize active data segments when instantiating

1 files changed, 272 insertions, 48 deletions

diff --git a/src/interp/binary-reader-interp.cc b/src/interp/binary-reader-interp.cc
index 7a5ecc00..6757f252 100644
--- a/src/interp/binary-reader-interp.cc
+++ b/src/interp/binary-reader-interp.cc
@@ -51,19 +51,23 @@ Label::Label(IstreamOffset offset, IstreamOffset fixup_offset)
     : offset(offset), fixup_offset(fixup_offset) {}
 
 struct ElemSegmentInfo {
-  ElemSegmentInfo(Index* dst, Index func_index)
-      : dst(dst), func_index(func_index) {}
+  ElemSegmentInfo(Table* table, Index dst) : table(table), dst(dst) {}
 
-  Index* dst;
-  Index func_index;
+  Table* table;
+  Index dst;
+  std::vector<Index> src;
 };
 
 struct DataSegmentInfo {
-  DataSegmentInfo(void* dst_data, const void* src_data, IstreamOffset size)
-      : dst_data(dst_data), src_data(src_data), size(size) {}
-
-  void* dst_data;        // Not owned.
-  const void* src_data;  // Not owned.
+  DataSegmentInfo(Memory* memory,
+                  Address dst,
+                  const void* src,
+                  IstreamOffset size)
+      : memory(memory), dst(dst), src(src), size(size) {}
+
+  Memory* memory;
+  Address dst;
+  const void* src;  // Not owned.
   IstreamOffset size;
 };
 
@@ -79,11 +83,11 @@ class BinaryReaderInterp : public BinaryReaderNop {
 
   std::unique_ptr<OutputBuffer> ReleaseOutputBuffer();
 
+  wabt::Result InitializeSegments();
+
   // Implement BinaryReader.
   bool OnError(const Error&) override;
 
-  wabt::Result EndModule() override;
-
   wabt::Result OnTypeCount(Index count) override;
   wabt::Result OnType(Index index,
                       Index param_count,
@@ -187,7 +191,11 @@ class BinaryReaderInterp : public BinaryReaderNop {
   wabt::Result OnLocalSetExpr(Index local_index) override;
   wabt::Result OnLocalTeeExpr(Index local_index) override;
   wabt::Result OnLoopExpr(Type sig_type) override;
+  wabt::Result OnMemoryCopyExpr() override;
+  wabt::Result OnDataDropExpr(Index segment_index) override;
   wabt::Result OnMemoryGrowExpr() override;
+  wabt::Result OnMemoryFillExpr() override;
+  wabt::Result OnMemoryInitExpr(Index segment_index) override;
   wabt::Result OnMemorySizeExpr() override;
   wabt::Result OnNopExpr() override;
   wabt::Result OnReturnExpr() override;
@@ -196,18 +204,30 @@ class BinaryReaderInterp : public BinaryReaderNop {
                            uint32_t alignment_log2,
                            Address offset) override;
   wabt::Result OnUnaryExpr(wabt::Opcode opcode) override;
+  wabt::Result OnTableCopyExpr() override;
+  wabt::Result OnElemDropExpr(Index segment_index) override;
+  wabt::Result OnTableInitExpr(Index segment_index) override;
   wabt::Result OnTernaryExpr(wabt::Opcode opcode) override;
   wabt::Result OnUnreachableExpr() override;
   wabt::Result EndFunctionBody(Index index) override;
   wabt::Result OnSimdLaneOpExpr(wabt::Opcode opcode, uint64_t value) override;
   wabt::Result OnSimdShuffleOpExpr(wabt::Opcode opcode, v128 value) override;
 
+  wabt::Result OnElemSegmentCount(Index count) override;
+  wabt::Result BeginElemSegment(Index index,
+                                Index table_index,
+                                bool passive,
+                                Type elem_type) override;
   wabt::Result EndElemSegmentInitExpr(Index index) override;
   wabt::Result OnElemSegmentElemExprCount(Index index, Index count) override;
   wabt::Result OnElemSegmentElemExpr_RefNull(Index segment_index) override;
   wabt::Result OnElemSegmentElemExpr_RefFunc(Index segment_index,
                                              Index func_index) override;
 
+  wabt::Result OnDataCount(Index count) override;
+  wabt::Result BeginDataSegment(Index index,
+                                Index memory_index,
+                                bool passive) override;
   wabt::Result OnDataSegmentData(Index index,
                                  const void* data,
                                  Address size) override;
@@ -241,6 +261,8 @@ class BinaryReaderInterp : public BinaryReaderNop {
   Type GetGlobalTypeByModuleIndex(Index global_index);
   Index TranslateLocalIndex(Index local_index);
   Type GetLocalTypeByIndex(Func* func, Index local_index);
+  Index TranslateDataSegmentIndexToEnv(Index data_segment_index);
+  Index TranslateElemSegmentIndexToEnv(Index elem_segment_index);
 
   IstreamOffset GetIstreamOffset();
 
@@ -270,10 +292,13 @@ class BinaryReaderInterp : public BinaryReaderNop {
 
   wabt::Result CheckLocal(Index local_index);
   wabt::Result CheckGlobal(Index global_index);
+  wabt::Result CheckDataSegment(Index data_segment_index);
+  wabt::Result CheckElemSegment(Index elem_segment_index);
   wabt::Result CheckImportKind(Import* import, ExternalKind expected_kind);
   wabt::Result CheckImportLimits(const Limits* declared_limits,
                                  const Limits* actual_limits);
   wabt::Result CheckHasMemory(wabt::Opcode opcode);
+  wabt::Result CheckHasTable(wabt::Opcode opcode);
   wabt::Result CheckAlign(uint32_t alignment_log2, Address natural_alignment);
   wabt::Result CheckAtomicAlign(uint32_t alignment_log2,
                                 Address natural_alignment);
@@ -304,6 +329,8 @@ class BinaryReaderInterp : public BinaryReaderNop {
   IndexVector sig_index_mapping_;
   IndexVector func_index_mapping_;
   IndexVector global_index_mapping_;
+  IndexVector data_segment_index_mapping_;
+  IndexVector elem_segment_index_mapping_;
 
   Index num_func_imports_ = 0;
   Index num_global_imports_ = 0;
@@ -311,12 +338,19 @@ class BinaryReaderInterp : public BinaryReaderNop {
   // Changes to linear memory and tables should not apply if a validation error
   // occurs; these vectors cache the changes that must be applied after we know
   // that there are no validation errors.
+  //
+  // Note that this behavior changed after the bulk memory proposal; in that
+  // case each segment is initialized as it is encountered. If one fails, then
+  // no further segments are processed.
   std::vector<ElemSegmentInfo> elem_segment_infos_;
   std::vector<DataSegmentInfo> data_segment_infos_;
 
   // Values cached so they can be shared between callbacks.
   TypedValue init_expr_value_;
   IstreamOffset table_offset_ = 0;
+  bool segment_is_passive_ = false;
+  ElemSegment* elem_segment_ = nullptr;
+  ElemSegmentInfo* elem_segment_info_ = nullptr;
 };
 
 BinaryReaderInterp::BinaryReaderInterp(Environment* env,
@@ -406,6 +440,14 @@ Type BinaryReaderInterp::GetLocalTypeByIndex(Func* func, Index local_index) {
   return cast<DefinedFunc>(func)->param_and_local_types[local_index];
 }
 
+Index BinaryReaderInterp::TranslateDataSegmentIndexToEnv(Index index) {
+  return data_segment_index_mapping_[index];
+}
+
+Index BinaryReaderInterp::TranslateElemSegmentIndexToEnv(Index index) {
+  return elem_segment_index_mapping_[index];
+}
+
 IstreamOffset BinaryReaderInterp::GetIstreamOffset() {
   return istream_offset_;
 }
@@ -597,6 +639,26 @@ wabt::Result BinaryReaderInterp::CheckGlobal(Index global_index) {
   return wabt::Result::Ok;
 }
 
+wabt::Result BinaryReaderInterp::CheckDataSegment(Index data_segment_index) {
+  Index max_data_segment_index = data_segment_index_mapping_.size();
+  if (data_segment_index >= max_data_segment_index) {
+    PrintError("invalid data_segment_index: %" PRIindex " (max %" PRIindex ")",
+               data_segment_index, max_data_segment_index);
+    return wabt::Result::Error;
+  }
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::CheckElemSegment(Index elem_segment_index) {
+  Index max_elem_segment_index = elem_segment_index_mapping_.size();
+  if (elem_segment_index >= max_elem_segment_index) {
+    PrintError("invalid elem_segment_index: %" PRIindex " (max %" PRIindex ")",
+               elem_segment_index, max_elem_segment_index);
+    return wabt::Result::Error;
+  }
+  return wabt::Result::Ok;
+}
+
 wabt::Result BinaryReaderInterp::CheckImportKind(Import* import,
                                                  ExternalKind actual_kind) {
   if (import->kind != actual_kind) {
@@ -970,7 +1032,23 @@ wabt::Result BinaryReaderInterp::OnStartFunction(Index func_index) {
   return wabt::Result::Ok;
 }
 
+wabt::Result BinaryReaderInterp::OnElemSegmentCount(Index count) {
+  for (Index i = 0; i < count; ++i) {
+    elem_segment_index_mapping_.push_back(env_->GetElemSegmentCount() + i);
+  }
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::BeginElemSegment(Index index,
+                                                  Index table_index,
+                                                  bool passive,
+                                                  Type elem_type) {
+  segment_is_passive_ = passive;
+  return wabt::Result::Ok;
+}
+
 wabt::Result BinaryReaderInterp::EndElemSegmentInitExpr(Index index) {
+  assert(segment_is_passive_ == false);
   assert(init_expr_value_.type == Type::I32);
   table_offset_ = init_expr_value_.value.i32;
   return wabt::Result::Ok;
@@ -978,23 +1056,28 @@ wabt::Result BinaryReaderInterp::EndElemSegmentInitExpr(Index index) {
 
 wabt::Result BinaryReaderInterp::OnElemSegmentElemExprCount(Index index,
                                                             Index count) {
-  assert(module_->table_index != kInvalidIndex);
-  Table* table = env_->GetTable(module_->table_index);
-  // Check both cases, as table_offset_ + count may overflow.
-  if (table_offset_ > table->func_indexes.size() ||
-      table_offset_ + count > table->func_indexes.size()) {
-    PrintError("elem segment is out of bounds: [%u, %u) >= max value %" PRIzd,
-               table_offset_, table_offset_ + count,
-               table->func_indexes.size());
-    return wabt::Result::Error;
+  elem_segment_ = env_->EmplaceBackElemSegment();
+  if (segment_is_passive_) {
+    elem_segment_info_ = nullptr;
+  } else {
+    // An active segment still is present in the segment index space, but
+    // cannot be used with `table.init` (it's as if it has already been
+    // dropped).
+    elem_segment_->dropped = true;
+
+    assert(module_->table_index != kInvalidIndex);
+    Table* table = env_->GetTable(module_->table_index);
+    elem_segment_infos_.emplace_back(table, table_offset_);
+    elem_segment_info_ = &elem_segment_infos_.back();
   }
   return wabt::Result::Ok;
 }
 
 wabt::Result BinaryReaderInterp::OnElemSegmentElemExpr_RefNull(
     Index segment_index) {
-  // TODO(binji): implement
-  return wabt::Result::Error;
+  assert(segment_is_passive_);
+  elem_segment_->elems.push_back(kInvalidIndex);
+  return wabt::Result::Ok;
 }
 
 wabt::Result BinaryReaderInterp::OnElemSegmentElemExpr_RefFunc(
@@ -1007,32 +1090,51 @@ wabt::Result BinaryReaderInterp::OnElemSegmentElemExpr_RefFunc(
     return wabt::Result::Error;
   }
 
-  Table* table = env_->GetTable(module_->table_index);
-  elem_segment_infos_.emplace_back(&table->func_indexes[table_offset_++],
-                                   TranslateFuncIndexToEnv(func_index));
+  func_index = TranslateFuncIndexToEnv(func_index);
+
+  if (segment_is_passive_) {
+    elem_segment_->elems.push_back(func_index);
+  } else {
+    elem_segment_info_->src.push_back(func_index);
+  }
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::OnDataCount(Index count) {
+  for (Index i = 0; i < count; ++i) {
+    data_segment_index_mapping_.push_back(env_->GetDataSegmentCount() + i);
+  }
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::BeginDataSegment(Index index,
+                                                  Index memory_index,
+                                                  bool passive) {
+  segment_is_passive_ = passive;
   return wabt::Result::Ok;
 }
 
 wabt::Result BinaryReaderInterp::OnDataSegmentData(Index index,
                                                    const void* src_data,
                                                    Address size) {
-  assert(module_->memory_index != kInvalidIndex);
-  Memory* memory = env_->GetMemory(module_->memory_index);
-  assert(init_expr_value_.type == Type::I32);
-  Address address = init_expr_value_.value.i32;
-  uint64_t end_address =
-      static_cast<uint64_t>(address) + static_cast<uint64_t>(size);
-  if (end_address > memory->data.size()) {
-    PrintError("data segment is out of bounds: [%" PRIaddress ", %" PRIu64
-               ") >= max value %" PRIzd,
-               address, end_address, memory->data.size());
-    return wabt::Result::Error;
-  }
-
-  if (size > 0) {
-    data_segment_infos_.emplace_back(&memory->data[address], src_data, size);
+  DataSegment* segment = env_->EmplaceBackDataSegment();
+  if (segment_is_passive_) {
+    segment->data.resize(size);
+    if (size > 0) {
+      memcpy(segment->data.data(), src_data, size);
+    }
+  } else {
+    // An active segment still is present in the segment index space, but
+    // cannot be used with `memory.init` (it's as if it has already been
+    // dropped).
+    segment->dropped = true;
+
+    assert(module_->memory_index != kInvalidIndex);
+    Memory* memory = env_->GetMemory(module_->memory_index);
+    assert(init_expr_value_.type == Type::I32);
+    Address address = init_expr_value_.value.i32;
+    data_segment_infos_.emplace_back(memory, address, src_data, size);
   }
-
   return wabt::Result::Ok;
 }
 
@@ -1121,6 +1223,14 @@ wabt::Result BinaryReaderInterp::CheckHasMemory(wabt::Opcode opcode) {
   return wabt::Result::Ok;
 }
 
+wabt::Result BinaryReaderInterp::CheckHasTable(wabt::Opcode opcode) {
+  if (module_->table_index == kInvalidIndex) {
+    PrintError("%s requires an imported or defined table.", opcode.GetName());
+    return wabt::Result::Error;
+  }
+  return wabt::Result::Ok;
+}
+
 wabt::Result BinaryReaderInterp::CheckAlign(uint32_t alignment_log2,
                                             Address natural_alignment) {
   if (alignment_log2 >= 32 || (1U << alignment_log2) > natural_alignment) {
@@ -1593,13 +1703,117 @@ wabt::Result BinaryReaderInterp::OnAtomicNotifyExpr(Opcode opcode,
   return wabt::Result::Ok;
 }
 
-wabt::Result BinaryReaderInterp::EndModule() {
-  for (ElemSegmentInfo& info : elem_segment_infos_) {
-    *info.dst = info.func_index;
-  }
-  for (DataSegmentInfo& info : data_segment_infos_) {
-    memcpy(info.dst_data, info.src_data, info.size);
+wabt::Result BinaryReaderInterp::OnMemoryCopyExpr() {
+  CHECK_RESULT(CheckHasMemory(Opcode::MemoryCopy));
+  CHECK_RESULT(typechecker_.OnMemoryCopy());
+  CHECK_RESULT(EmitOpcode(Opcode::MemoryCopy));
+  CHECK_RESULT(EmitI32(module_->memory_index));
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::OnDataDropExpr(Index segment_index) {
+  CHECK_RESULT(CheckDataSegment(segment_index));
+  CHECK_RESULT(typechecker_.OnDataDrop(segment_index));
+  CHECK_RESULT(EmitOpcode(Opcode::DataDrop));
+  CHECK_RESULT(EmitI32(TranslateDataSegmentIndexToEnv(segment_index)));
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::OnMemoryFillExpr() {
+  CHECK_RESULT(CheckHasMemory(Opcode::MemoryFill));
+  CHECK_RESULT(typechecker_.OnMemoryFill());
+  CHECK_RESULT(EmitOpcode(Opcode::MemoryFill));
+  CHECK_RESULT(EmitI32(module_->memory_index));
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::OnMemoryInitExpr(Index segment_index) {
+  CHECK_RESULT(CheckHasMemory(Opcode::MemoryInit));
+  CHECK_RESULT(CheckDataSegment(segment_index));
+  CHECK_RESULT(typechecker_.OnMemoryInit(segment_index));
+  CHECK_RESULT(EmitOpcode(Opcode::MemoryInit));
+  CHECK_RESULT(EmitI32(module_->memory_index));
+  CHECK_RESULT(EmitI32(TranslateDataSegmentIndexToEnv(segment_index)));
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::OnTableCopyExpr() {
+  CHECK_RESULT(CheckHasTable(Opcode::TableCopy));
+  CHECK_RESULT(typechecker_.OnTableCopy());
+  CHECK_RESULT(EmitOpcode(Opcode::TableCopy));
+  CHECK_RESULT(EmitI32(module_->table_index));
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::OnElemDropExpr(Index segment_index) {
+  CHECK_RESULT(CheckElemSegment(segment_index));
+  CHECK_RESULT(typechecker_.OnElemDrop(segment_index));
+  CHECK_RESULT(EmitOpcode(Opcode::ElemDrop));
+  CHECK_RESULT(EmitI32(TranslateElemSegmentIndexToEnv(segment_index)));
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::OnTableInitExpr(Index segment_index) {
+  CHECK_RESULT(CheckHasTable(Opcode::TableInit));
+  CHECK_RESULT(CheckElemSegment(segment_index));
+  CHECK_RESULT(typechecker_.OnTableInit(segment_index));
+  CHECK_RESULT(EmitOpcode(Opcode::TableInit));
+  CHECK_RESULT(EmitI32(module_->table_index));
+  CHECK_RESULT(EmitI32(TranslateElemSegmentIndexToEnv(segment_index)));
+  return wabt::Result::Ok;
+}
+
+wabt::Result BinaryReaderInterp::InitializeSegments() {
+  // The MVP requires that all segments are bounds-checked before being copied
+  // into the table or memory. The bulk memory proposal changes this behavior;
+  // instead, each segment is copied in order. If any segment fails, then no
+  // further segments are copied. Any data that was written persists.
+  enum Pass { Check = 0, Init = 1 };
+  int pass = features_.bulk_memory_enabled() ? Init : Check;
+
+  for (; pass <= Init; ++pass) {
+    for (const ElemSegmentInfo& info : elem_segment_infos_) {
+      uint32_t table_size = info.table->func_indexes.size();
+      uint32_t segment_size = info.src.size();
+      uint32_t copy_size = segment_size;
+      bool ok = ClampToBounds(info.dst, &copy_size, table_size);
+
+      if (pass == Init && copy_size > 0) {
+        std::copy(info.src.begin(), info.src.begin() + copy_size,
+                  info.table->func_indexes.begin() + info.dst);
+      }
+
+      if (!ok) {
+        PrintError("elem segment is out of bounds: [%u, %" PRIu64
+                   ") >= max value %u",
+                   info.dst, static_cast<uint64_t>(info.dst) + segment_size,
+                   table_size);
+        return wabt::Result::Error;
+      }
+    }
+
+    for (const DataSegmentInfo& info : data_segment_infos_) {
+      uint32_t memory_size = info.memory->data.size();
+      uint32_t segment_size = info.size;
+      uint32_t copy_size = segment_size;
+      bool ok = ClampToBounds(info.dst, &copy_size, memory_size);
+
+      if (pass == Init && copy_size > 0) {
+        const char* src_data = static_cast<const char*>(info.src);
+        std::copy(src_data, src_data + copy_size,
+                  info.memory->data.begin() + info.dst);
+      }
+
+      if (!ok) {
+        PrintError("data segment is out of bounds: [%u, %" PRIu64
+                   ") >= max value %u",
+                   info.dst, static_cast<uint64_t>(info.dst) + segment_size,
+                   memory_size);
+        return wabt::Result::Error;
+      }
+    }
   }
+
   return wabt::Result::Ok;
 }
 
@@ -1628,11 +1842,21 @@ wabt::Result ReadBinaryInterp(Environment* env,
   if (Succeeded(result)) {
     module->istream_start = istream_offset;
     module->istream_end = env->istream().size();
-    *out_module = module;
+
+    result = reader.InitializeSegments();
+    if (Succeeded(result)) {
+      *out_module = module;
+    } else {
+      // We failed to initialize data and element segments, but we can't reset
+      // to the mark point. An element segment may have initialized an imported
+      // table with a function from this module, which is still callable.
+      *out_module = nullptr;
+    }
   } else {
     env->ResetToMarkPoint(mark);
     *out_module = nullptr;
   }
+
   return result;
 }