AbstractMachine.cpp 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540
  1. /*
  2. * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <LibWasm/AbstractMachine/AbstractMachine.h>
  7. #include <LibWasm/AbstractMachine/BytecodeInterpreter.h>
  8. #include <LibWasm/AbstractMachine/Configuration.h>
  9. #include <LibWasm/AbstractMachine/Interpreter.h>
  10. #include <LibWasm/Types.h>
  11. namespace Wasm {
  12. Optional<FunctionAddress> Store::allocate(ModuleInstance& module, Module::Function const& function)
  13. {
  14. FunctionAddress address { m_functions.size() };
  15. if (function.type().value() > module.types().size())
  16. return {};
  17. auto& type = module.types()[function.type().value()];
  18. m_functions.empend(WasmFunction { type, module, function });
  19. return address;
  20. }
  21. Optional<FunctionAddress> Store::allocate(HostFunction&& function)
  22. {
  23. FunctionAddress address { m_functions.size() };
  24. m_functions.empend(HostFunction { move(function) });
  25. return address;
  26. }
  27. Optional<TableAddress> Store::allocate(TableType const& type)
  28. {
  29. TableAddress address { m_tables.size() };
  30. Vector<Optional<Reference>> elements;
  31. elements.resize(type.limits().min());
  32. m_tables.empend(TableInstance { type, move(elements) });
  33. return address;
  34. }
  35. Optional<MemoryAddress> Store::allocate(MemoryType const& type)
  36. {
  37. MemoryAddress address { m_memories.size() };
  38. m_memories.empend(MemoryInstance { type });
  39. return address;
  40. }
  41. Optional<GlobalAddress> Store::allocate(GlobalType const& type, Value value)
  42. {
  43. GlobalAddress address { m_globals.size() };
  44. m_globals.append(GlobalInstance { move(value), type.is_mutable() });
  45. return address;
  46. }
  47. Optional<ElementAddress> Store::allocate(ValueType const& type, Vector<Reference> references)
  48. {
  49. ElementAddress address { m_elements.size() };
  50. m_elements.append(ElementInstance { type, move(references) });
  51. return address;
  52. }
  53. FunctionInstance* Store::get(FunctionAddress address)
  54. {
  55. auto value = address.value();
  56. if (m_functions.size() <= value)
  57. return nullptr;
  58. return &m_functions[value];
  59. }
  60. TableInstance* Store::get(TableAddress address)
  61. {
  62. auto value = address.value();
  63. if (m_tables.size() <= value)
  64. return nullptr;
  65. return &m_tables[value];
  66. }
  67. MemoryInstance* Store::get(MemoryAddress address)
  68. {
  69. auto value = address.value();
  70. if (m_memories.size() <= value)
  71. return nullptr;
  72. return &m_memories[value];
  73. }
  74. GlobalInstance* Store::get(GlobalAddress address)
  75. {
  76. auto value = address.value();
  77. if (m_globals.size() <= value)
  78. return nullptr;
  79. return &m_globals[value];
  80. }
  81. ElementInstance* Store::get(ElementAddress address)
  82. {
  83. auto value = address.value();
  84. if (m_elements.size() <= value)
  85. return nullptr;
  86. return &m_elements[value];
  87. }
  88. InstantiationResult AbstractMachine::instantiate(Module const& module, Vector<ExternValue> externs)
  89. {
  90. auto main_module_instance_pointer = make<ModuleInstance>();
  91. auto& main_module_instance = *main_module_instance_pointer;
  92. Optional<InstantiationResult> instantiation_result;
  93. module.for_each_section_of_type<TypeSection>([&](TypeSection const& section) {
  94. main_module_instance.types() = section.types();
  95. });
  96. // FIXME: Validate stuff
  97. Vector<Value> global_values;
  98. Vector<Vector<Reference>> elements;
  99. ModuleInstance auxiliary_instance;
  100. // FIXME: Check that imports/extern match
  101. for (auto& entry : externs) {
  102. if (auto* ptr = entry.get_pointer<GlobalAddress>())
  103. auxiliary_instance.globals().append(*ptr);
  104. }
  105. BytecodeInterpreter interpreter;
  106. module.for_each_section_of_type<GlobalSection>([&](auto& global_section) {
  107. for (auto& entry : global_section.entries()) {
  108. Configuration config { m_store };
  109. if (m_should_limit_instruction_count)
  110. config.enable_instruction_count_limit();
  111. config.set_frame(Frame {
  112. auxiliary_instance,
  113. Vector<Value> {},
  114. entry.expression(),
  115. 1,
  116. });
  117. auto result = config.execute(interpreter);
  118. if (result.is_trap())
  119. instantiation_result = InstantiationError { String::formatted("Global value construction trapped: {}", result.trap().reason) };
  120. else
  121. global_values.append(result.values().first());
  122. }
  123. });
  124. if (instantiation_result.has_value())
  125. return instantiation_result.release_value();
  126. if (auto result = allocate_all_initial_phase(module, main_module_instance, externs, global_values); result.has_value())
  127. return result.release_value();
  128. module.for_each_section_of_type<ElementSection>([&](ElementSection const& section) {
  129. for (auto& segment : section.segments()) {
  130. Vector<Reference> references;
  131. for (auto& entry : segment.init) {
  132. Configuration config { m_store };
  133. if (m_should_limit_instruction_count)
  134. config.enable_instruction_count_limit();
  135. config.set_frame(Frame {
  136. main_module_instance,
  137. Vector<Value> {},
  138. entry,
  139. entry.instructions().size(),
  140. });
  141. auto result = config.execute(interpreter);
  142. if (result.is_trap()) {
  143. instantiation_result = InstantiationError { String::formatted("Element construction trapped: {}", result.trap().reason) };
  144. return IterationDecision::Continue;
  145. }
  146. for (auto& value : result.values()) {
  147. if (!value.type().is_reference()) {
  148. instantiation_result = InstantiationError { "Evaluated element entry is not a reference" };
  149. return IterationDecision::Continue;
  150. }
  151. auto reference = value.to<Reference>();
  152. if (!reference.has_value()) {
  153. instantiation_result = InstantiationError { "Evaluated element entry does not contain a reference" };
  154. return IterationDecision::Continue;
  155. }
  156. // FIXME: type-check the reference.
  157. references.prepend(reference.release_value());
  158. }
  159. }
  160. elements.append(move(references));
  161. }
  162. return IterationDecision::Continue;
  163. });
  164. if (instantiation_result.has_value())
  165. return instantiation_result.release_value();
  166. if (auto result = allocate_all_final_phase(module, main_module_instance, elements); result.has_value())
  167. return result.release_value();
  168. module.for_each_section_of_type<ElementSection>([&](ElementSection const& section) {
  169. size_t index = 0;
  170. for (auto& segment : section.segments()) {
  171. auto current_index = index;
  172. ++index;
  173. auto active_ptr = segment.mode.get_pointer<ElementSection::Active>();
  174. if (!active_ptr)
  175. continue;
  176. if (active_ptr->index.value() != 0) {
  177. instantiation_result = InstantiationError { "Non-zero table referenced by active element segment" };
  178. return IterationDecision::Break;
  179. }
  180. Configuration config { m_store };
  181. if (m_should_limit_instruction_count)
  182. config.enable_instruction_count_limit();
  183. config.set_frame(Frame {
  184. main_module_instance,
  185. Vector<Value> {},
  186. active_ptr->expression,
  187. 1,
  188. });
  189. auto result = config.execute(interpreter);
  190. if (result.is_trap()) {
  191. instantiation_result = InstantiationError { String::formatted("Element section initialisation trapped: {}", result.trap().reason) };
  192. return IterationDecision::Break;
  193. }
  194. auto d = result.values().first().to<i32>();
  195. if (!d.has_value()) {
  196. instantiation_result = InstantiationError { "Element section initialisation returned invalid table initial offset" };
  197. return IterationDecision::Break;
  198. }
  199. if (main_module_instance.tables().size() < 1) {
  200. instantiation_result = InstantiationError { "Element section initialisation references nonexistent table" };
  201. return IterationDecision::Break;
  202. }
  203. auto table_instance = m_store.get(main_module_instance.tables()[0]);
  204. if (current_index >= main_module_instance.elements().size()) {
  205. instantiation_result = InstantiationError { "Invalid element referenced by active element segment" };
  206. return IterationDecision::Break;
  207. }
  208. auto elem_instance = m_store.get(main_module_instance.elements()[current_index]);
  209. if (!table_instance || !elem_instance) {
  210. instantiation_result = InstantiationError { "Invalid element referenced by active element segment" };
  211. return IterationDecision::Break;
  212. }
  213. auto total_required_size = elem_instance->references().size() + d.value();
  214. if (table_instance->type().limits().max().value_or(total_required_size) < total_required_size) {
  215. instantiation_result = InstantiationError { "Table limit overflow in active element segment" };
  216. return IterationDecision::Break;
  217. }
  218. if (table_instance->elements().size() < total_required_size)
  219. table_instance->elements().resize(total_required_size);
  220. size_t i = 0;
  221. for (auto it = elem_instance->references().begin(); it < elem_instance->references().end(); ++i, ++it) {
  222. table_instance->elements()[i + d.value()] = *it;
  223. }
  224. }
  225. return IterationDecision::Continue;
  226. });
  227. if (instantiation_result.has_value())
  228. return instantiation_result.release_value();
  229. module.for_each_section_of_type<DataSection>([&](DataSection const& data_section) {
  230. for (auto& segment : data_section.data()) {
  231. segment.value().visit(
  232. [&](DataSection::Data::Active const& data) {
  233. Configuration config { m_store };
  234. if (m_should_limit_instruction_count)
  235. config.enable_instruction_count_limit();
  236. config.set_frame(Frame {
  237. main_module_instance,
  238. Vector<Value> {},
  239. data.offset,
  240. 1,
  241. });
  242. auto result = config.execute(interpreter);
  243. if (result.is_trap()) {
  244. instantiation_result = InstantiationError { String::formatted("Data section initialisation trapped: {}", result.trap().reason) };
  245. return;
  246. }
  247. size_t offset = 0;
  248. result.values().first().value().visit(
  249. [&](auto const& value) { offset = value; },
  250. [&](Reference const&) { instantiation_result = InstantiationError { "Data segment offset returned a reference" }; });
  251. if (instantiation_result.has_value() && instantiation_result->is_error())
  252. return;
  253. if (main_module_instance.memories().size() <= data.index.value()) {
  254. instantiation_result = InstantiationError {
  255. String::formatted("Data segment referenced out-of-bounds memory ({}) of max {} entries",
  256. data.index.value(), main_module_instance.memories().size())
  257. };
  258. return;
  259. }
  260. if (data.init.is_empty())
  261. return;
  262. auto address = main_module_instance.memories()[data.index.value()];
  263. if (auto instance = m_store.get(address)) {
  264. if (auto max = instance->type().limits().max(); max.has_value()) {
  265. if (*max < data.init.size() + offset) {
  266. instantiation_result = InstantiationError {
  267. String::formatted("Data segment attempted to write to out-of-bounds memory ({}) of max {} bytes",
  268. data.init.size() + offset, instance->type().limits().max().value())
  269. };
  270. return;
  271. }
  272. }
  273. if (instance->size() < data.init.size() + offset)
  274. instance->grow(data.init.size() + offset - instance->size());
  275. instance->data().overwrite(offset, data.init.data(), data.init.size());
  276. }
  277. },
  278. [&](DataSection::Data::Passive const&) {
  279. // FIXME: What do we do here?
  280. });
  281. }
  282. });
  283. module.for_each_section_of_type<StartSection>([&](StartSection const& section) {
  284. auto& functions = main_module_instance.functions();
  285. auto index = section.function().index();
  286. if (functions.size() <= index.value()) {
  287. instantiation_result = InstantiationError { String::formatted("Start section function referenced invalid index {} of max {} entries", index.value(), functions.size()) };
  288. return;
  289. }
  290. invoke(functions[index.value()], {});
  291. });
  292. if (instantiation_result.has_value())
  293. return instantiation_result.release_value();
  294. return InstantiationResult { move(main_module_instance_pointer) };
  295. }
  296. Optional<InstantiationError> AbstractMachine::allocate_all_initial_phase(Module const& module, ModuleInstance& module_instance, Vector<ExternValue>& externs, Vector<Value>& global_values)
  297. {
  298. Optional<InstantiationError> result;
  299. for (auto& entry : externs) {
  300. entry.visit(
  301. [&](FunctionAddress const& address) { module_instance.functions().append(address); },
  302. [&](TableAddress const& address) { module_instance.tables().append(address); },
  303. [&](MemoryAddress const& address) { module_instance.memories().append(address); },
  304. [&](GlobalAddress const& address) { module_instance.globals().append(address); });
  305. }
  306. // FIXME: What if this fails?
  307. for (auto& func : module.functions()) {
  308. auto address = m_store.allocate(module_instance, func);
  309. VERIFY(address.has_value());
  310. module_instance.functions().append(*address);
  311. }
  312. module.for_each_section_of_type<TableSection>([&](TableSection const& section) {
  313. for (auto& table : section.tables()) {
  314. auto table_address = m_store.allocate(table.type());
  315. VERIFY(table_address.has_value());
  316. module_instance.tables().append(*table_address);
  317. }
  318. });
  319. module.for_each_section_of_type<MemorySection>([&](MemorySection const& section) {
  320. for (auto& memory : section.memories()) {
  321. auto memory_address = m_store.allocate(memory.type());
  322. VERIFY(memory_address.has_value());
  323. module_instance.memories().append(*memory_address);
  324. }
  325. });
  326. module.for_each_section_of_type<GlobalSection>([&](GlobalSection const& section) {
  327. size_t index = 0;
  328. for (auto& entry : section.entries()) {
  329. auto address = m_store.allocate(entry.type(), move(global_values[index]));
  330. VERIFY(address.has_value());
  331. module_instance.globals().append(*address);
  332. index++;
  333. }
  334. });
  335. module.for_each_section_of_type<ExportSection>([&](ExportSection const& section) {
  336. for (auto& entry : section.entries()) {
  337. Variant<FunctionAddress, TableAddress, MemoryAddress, GlobalAddress, Empty> address { Empty {} };
  338. entry.description().visit(
  339. [&](FunctionIndex const& index) {
  340. if (module_instance.functions().size() > index.value())
  341. address = FunctionAddress { module_instance.functions()[index.value()] };
  342. else
  343. dbgln("Failed to export '{}', the exported address ({}) was out of bounds (min: 0, max: {})", entry.name(), index.value(), module_instance.functions().size());
  344. },
  345. [&](TableIndex const& index) {
  346. if (module_instance.tables().size() > index.value())
  347. address = TableAddress { module_instance.tables()[index.value()] };
  348. else
  349. dbgln("Failed to export '{}', the exported address ({}) was out of bounds (min: 0, max: {})", entry.name(), index.value(), module_instance.tables().size());
  350. },
  351. [&](MemoryIndex const& index) {
  352. if (module_instance.memories().size() > index.value())
  353. address = MemoryAddress { module_instance.memories()[index.value()] };
  354. else
  355. dbgln("Failed to export '{}', the exported address ({}) was out of bounds (min: 0, max: {})", entry.name(), index.value(), module_instance.memories().size());
  356. },
  357. [&](GlobalIndex const& index) {
  358. if (module_instance.globals().size() > index.value())
  359. address = GlobalAddress { module_instance.globals()[index.value()] };
  360. else
  361. dbgln("Failed to export '{}', the exported address ({}) was out of bounds (min: 0, max: {})", entry.name(), index.value(), module_instance.globals().size());
  362. });
  363. if (address.has<Empty>()) {
  364. result = InstantiationError { "An export could not be resolved" };
  365. continue;
  366. }
  367. module_instance.exports().append(ExportInstance {
  368. entry.name(),
  369. move(address).downcast<FunctionAddress, TableAddress, MemoryAddress, GlobalAddress>(),
  370. });
  371. }
  372. });
  373. return result;
  374. }
  375. Optional<InstantiationError> AbstractMachine::allocate_all_final_phase(Module const& module, ModuleInstance& module_instance, Vector<Vector<Reference>>& elements)
  376. {
  377. module.for_each_section_of_type<ElementSection>([&](ElementSection const& section) {
  378. size_t index = 0;
  379. for (auto& segment : section.segments()) {
  380. auto address = m_store.allocate(segment.type, move(elements[index]));
  381. VERIFY(address.has_value());
  382. module_instance.elements().append(*address);
  383. index++;
  384. }
  385. });
  386. return {};
  387. }
  388. Result AbstractMachine::invoke(FunctionAddress address, Vector<Value> arguments)
  389. {
  390. BytecodeInterpreter interpreter;
  391. return invoke(interpreter, address, move(arguments));
  392. }
  393. Result AbstractMachine::invoke(Interpreter& interpreter, FunctionAddress address, Vector<Value> arguments)
  394. {
  395. Configuration configuration { m_store };
  396. if (m_should_limit_instruction_count)
  397. configuration.enable_instruction_count_limit();
  398. return configuration.call(interpreter, address, move(arguments));
  399. }
  400. void Linker::link(ModuleInstance const& instance)
  401. {
  402. populate();
  403. if (m_unresolved_imports.is_empty())
  404. return;
  405. HashTable<Name> resolved_imports;
  406. for (auto& import_ : m_unresolved_imports) {
  407. auto it = instance.exports().find_if([&](auto& export_) { return export_.name() == import_.name; });
  408. if (!it.is_end()) {
  409. resolved_imports.set(import_);
  410. m_resolved_imports.set(import_, it->value());
  411. }
  412. }
  413. for (auto& entry : resolved_imports)
  414. m_unresolved_imports.remove(entry);
  415. }
  416. void Linker::link(HashMap<Linker::Name, ExternValue> const& exports)
  417. {
  418. populate();
  419. if (m_unresolved_imports.is_empty())
  420. return;
  421. if (exports.is_empty())
  422. return;
  423. HashTable<Name> resolved_imports;
  424. for (auto& import_ : m_unresolved_imports) {
  425. auto export_ = exports.get(import_);
  426. if (export_.has_value()) {
  427. resolved_imports.set(import_);
  428. m_resolved_imports.set(import_, export_.value());
  429. }
  430. }
  431. for (auto& entry : resolved_imports)
  432. m_unresolved_imports.remove(entry);
  433. }
  434. AK::Result<Vector<ExternValue>, LinkError> Linker::finish()
  435. {
  436. populate();
  437. if (!m_unresolved_imports.is_empty()) {
  438. if (!m_error.has_value())
  439. m_error = LinkError {};
  440. for (auto& entry : m_unresolved_imports)
  441. m_error->missing_imports.append(entry.name);
  442. return *m_error;
  443. }
  444. if (m_error.has_value())
  445. return *m_error;
  446. // Result must be in the same order as the module imports
  447. Vector<ExternValue> exports;
  448. exports.ensure_capacity(m_ordered_imports.size());
  449. for (auto& import_ : m_ordered_imports)
  450. exports.unchecked_append(*m_resolved_imports.get(import_));
  451. return exports;
  452. }
  453. void Linker::populate()
  454. {
  455. if (!m_ordered_imports.is_empty())
  456. return;
  457. // There better be at most one import section!
  458. bool already_seen_an_import_section = false;
  459. m_module.for_each_section_of_type<ImportSection>([&](ImportSection const& section) {
  460. if (already_seen_an_import_section) {
  461. if (!m_error.has_value())
  462. m_error = LinkError {};
  463. m_error->other_errors.append(LinkError::InvalidImportedModule);
  464. return;
  465. }
  466. already_seen_an_import_section = true;
  467. for (auto& import_ : section.imports()) {
  468. m_ordered_imports.append({ import_.module(), import_.name(), import_.description() });
  469. m_unresolved_imports.set(m_ordered_imports.last());
  470. }
  471. });
  472. }
  473. }