AbstractMachine.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369
  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/Configuration.h>
  8. #include <LibWasm/Types.h>
  9. namespace Wasm {
  10. Optional<FunctionAddress> Store::allocate(ModuleInstance& module, const Module::Function& function)
  11. {
  12. FunctionAddress address { m_functions.size() };
  13. if (function.type().value() > module.types().size())
  14. return {};
  15. auto& type = module.types()[function.type().value()];
  16. m_functions.empend(WasmFunction { type, module, function });
  17. return address;
  18. }
  19. Optional<FunctionAddress> Store::allocate(HostFunction&& function)
  20. {
  21. FunctionAddress address { m_functions.size() };
  22. m_functions.empend(HostFunction { move(function) });
  23. return address;
  24. }
  25. Optional<TableAddress> Store::allocate(const TableType& type)
  26. {
  27. TableAddress address { m_tables.size() };
  28. Vector<Optional<Reference>> elements;
  29. elements.resize(type.limits().min());
  30. m_tables.empend(TableInstance { type, move(elements) });
  31. return address;
  32. }
  33. Optional<MemoryAddress> Store::allocate(const MemoryType& type)
  34. {
  35. MemoryAddress address { m_memories.size() };
  36. m_memories.empend(MemoryInstance { type });
  37. return address;
  38. }
  39. Optional<GlobalAddress> Store::allocate(const GlobalType& type, Value value)
  40. {
  41. GlobalAddress address { m_globals.size() };
  42. m_globals.append(GlobalInstance { move(value), type.is_mutable() });
  43. return address;
  44. }
  45. FunctionInstance* Store::get(FunctionAddress address)
  46. {
  47. auto value = address.value();
  48. if (m_functions.size() <= value)
  49. return nullptr;
  50. return &m_functions[value];
  51. }
  52. TableInstance* Store::get(TableAddress address)
  53. {
  54. auto value = address.value();
  55. if (m_tables.size() <= value)
  56. return nullptr;
  57. return &m_tables[value];
  58. }
  59. MemoryInstance* Store::get(MemoryAddress address)
  60. {
  61. auto value = address.value();
  62. if (m_memories.size() <= value)
  63. return nullptr;
  64. return &m_memories[value];
  65. }
  66. GlobalInstance* Store::get(GlobalAddress address)
  67. {
  68. auto value = address.value();
  69. if (m_globals.size() <= value)
  70. return nullptr;
  71. return &m_globals[value];
  72. }
  73. InstantiationResult AbstractMachine::instantiate(const Module& module, Vector<ExternValue> externs)
  74. {
  75. auto main_module_instance_pointer = make<ModuleInstance>();
  76. auto& main_module_instance = *main_module_instance_pointer;
  77. Optional<InstantiationResult> instantiation_result;
  78. module.for_each_section_of_type<TypeSection>([&](const TypeSection& section) {
  79. main_module_instance.types() = section.types();
  80. });
  81. // FIXME: Validate stuff
  82. Vector<Value> global_values;
  83. ModuleInstance auxiliary_instance;
  84. // FIXME: Check that imports/extern match
  85. for (auto& entry : externs) {
  86. if (auto* ptr = entry.get_pointer<GlobalAddress>())
  87. auxiliary_instance.globals().append(*ptr);
  88. }
  89. module.for_each_section_of_type<GlobalSection>([&](auto& global_section) {
  90. for (auto& entry : global_section.entries()) {
  91. auto frame = make<Frame>(
  92. auxiliary_instance,
  93. Vector<Value> {},
  94. entry.expression(),
  95. 1);
  96. Configuration config { m_store };
  97. config.set_frame(move(frame));
  98. auto result = config.execute();
  99. // What if this traps?
  100. if (result.is_trap())
  101. instantiation_result = InstantiationError { "Global value construction trapped" };
  102. else
  103. global_values.append(result.values().first());
  104. }
  105. });
  106. if (auto result = allocate_all(module, main_module_instance, externs, global_values); result.has_value()) {
  107. return result.release_value();
  108. }
  109. module.for_each_section_of_type<ElementSection>([&](const ElementSection&) {
  110. // FIXME: Implement me
  111. // https://webassembly.github.io/spec/core/bikeshed/#element-segments%E2%91%A0
  112. // https://webassembly.github.io/spec/core/bikeshed/#instantiation%E2%91%A1 step 9
  113. });
  114. module.for_each_section_of_type<DataSection>([&](const DataSection& data_section) {
  115. for (auto& segment : data_section.data()) {
  116. segment.value().visit(
  117. [&](const DataSection::Data::Active& data) {
  118. auto frame = make<Frame>(
  119. main_module_instance,
  120. Vector<Value> {},
  121. data.offset,
  122. 1);
  123. Configuration config { m_store };
  124. config.set_frame(move(frame));
  125. auto result = config.execute();
  126. size_t offset = 0;
  127. result.values().first().value().visit(
  128. [&](const auto& value) { offset = value; },
  129. [&](const FunctionAddress&) { instantiation_result = InstantiationError { "Data segment offset returned an address" }; },
  130. [&](const ExternAddress&) { instantiation_result = InstantiationError { "Data segment offset returned an address" }; });
  131. if (instantiation_result.has_value() && instantiation_result->is_error())
  132. return;
  133. if (main_module_instance.memories().size() <= data.index.value()) {
  134. instantiation_result = InstantiationError { String::formatted("Data segment referenced out-of-bounds memory ({}) of max {} entries", data.index.value(), main_module_instance.memories().size()) };
  135. return;
  136. }
  137. auto address = main_module_instance.memories()[data.index.value()];
  138. if (auto instance = m_store.get(address)) {
  139. if (instance->type().limits().max().value_or(data.init.size() + offset + 1) <= data.init.size() + offset) {
  140. instantiation_result = InstantiationError { String::formatted("Data segment attempted to write to out-of-bounds memory ({}) of max {} bytes", data.init.size() + offset, instance->type().limits().max().value()) };
  141. return;
  142. }
  143. if (instance->size() < data.init.size() + offset)
  144. instance->grow(data.init.size() + offset - instance->size());
  145. instance->data().overwrite(offset, data.init.data(), data.init.size());
  146. }
  147. },
  148. [&](const DataSection::Data::Passive&) {
  149. // FIXME: What do we do here?
  150. });
  151. }
  152. });
  153. module.for_each_section_of_type<StartSection>([&](const StartSection& section) {
  154. auto& functions = main_module_instance.functions();
  155. auto index = section.function().index();
  156. if (functions.size() <= index.value()) {
  157. instantiation_result = InstantiationError { String::formatted("Start section function referenced invalid index {} of max {} entries", index.value(), functions.size()) };
  158. return;
  159. }
  160. invoke(functions[index.value()], {});
  161. });
  162. if (instantiation_result.has_value())
  163. return instantiation_result.release_value();
  164. return InstantiationResult { move(main_module_instance_pointer) };
  165. }
  166. Optional<InstantiationError> AbstractMachine::allocate_all(const Module& module, ModuleInstance& module_instance, Vector<ExternValue>& externs, Vector<Value>& global_values)
  167. {
  168. Optional<InstantiationError> result;
  169. for (auto& entry : externs) {
  170. entry.visit(
  171. [&](const FunctionAddress& address) { module_instance.functions().append(address); },
  172. [&](const TableAddress& address) { module_instance.tables().append(address); },
  173. [&](const MemoryAddress& address) { module_instance.memories().append(address); },
  174. [&](const GlobalAddress& address) { module_instance.globals().append(address); });
  175. }
  176. // FIXME: What if this fails?
  177. for (auto& func : module.functions()) {
  178. auto address = m_store.allocate(module_instance, func);
  179. VERIFY(address.has_value());
  180. module_instance.functions().append(*address);
  181. }
  182. module.for_each_section_of_type<TableSection>([&](const TableSection& section) {
  183. for (auto& table : section.tables()) {
  184. auto table_address = m_store.allocate(table.type());
  185. VERIFY(table_address.has_value());
  186. module_instance.tables().append(*table_address);
  187. }
  188. });
  189. module.for_each_section_of_type<MemorySection>([&](const MemorySection& section) {
  190. for (auto& memory : section.memories()) {
  191. auto memory_address = m_store.allocate(memory.type());
  192. VERIFY(memory_address.has_value());
  193. module_instance.memories().append(*memory_address);
  194. }
  195. });
  196. module.for_each_section_of_type<GlobalSection>([&](const GlobalSection& section) {
  197. size_t index = 0;
  198. for (auto& entry : section.entries()) {
  199. auto address = m_store.allocate(entry.type(), global_values[index]);
  200. VERIFY(address.has_value());
  201. module_instance.globals().append(*address);
  202. index++;
  203. }
  204. });
  205. module.for_each_section_of_type<ExportSection>([&](const ExportSection& section) {
  206. for (auto& entry : section.entries()) {
  207. Variant<FunctionAddress, TableAddress, MemoryAddress, GlobalAddress, Empty> address { Empty {} };
  208. entry.description().visit(
  209. [&](const FunctionIndex& index) {
  210. if (module_instance.functions().size() > index.value())
  211. address = FunctionAddress { module_instance.functions()[index.value()] };
  212. else
  213. dbgln("Failed to export '{}', the exported address ({}) was out of bounds (min: 0, max: {})", entry.name(), index.value(), module_instance.functions().size());
  214. },
  215. [&](const TableIndex& index) {
  216. if (module_instance.tables().size() > index.value())
  217. address = TableAddress { module_instance.tables()[index.value()] };
  218. else
  219. dbgln("Failed to export '{}', the exported address ({}) was out of bounds (min: 0, max: {})", entry.name(), index.value(), module_instance.tables().size());
  220. },
  221. [&](const MemoryIndex& index) {
  222. if (module_instance.memories().size() > index.value())
  223. address = MemoryAddress { module_instance.memories()[index.value()] };
  224. else
  225. dbgln("Failed to export '{}', the exported address ({}) was out of bounds (min: 0, max: {})", entry.name(), index.value(), module_instance.memories().size());
  226. },
  227. [&](const GlobalIndex& index) {
  228. if (module_instance.globals().size() > index.value())
  229. address = GlobalAddress { module_instance.globals()[index.value()] };
  230. else
  231. dbgln("Failed to export '{}', the exported address ({}) was out of bounds (min: 0, max: {})", entry.name(), index.value(), module_instance.globals().size());
  232. });
  233. if (address.has<Empty>()) {
  234. result = InstantiationError { "An export could not be resolved" };
  235. continue;
  236. }
  237. module_instance.exports().append(ExportInstance {
  238. entry.name(),
  239. move(address).downcast<FunctionAddress, TableAddress, MemoryAddress, GlobalAddress>(),
  240. });
  241. }
  242. });
  243. return result;
  244. }
  245. Result AbstractMachine::invoke(FunctionAddress address, Vector<Value> arguments)
  246. {
  247. return Configuration { m_store }.call(address, move(arguments));
  248. }
  249. void Linker::link(const ModuleInstance& instance)
  250. {
  251. populate();
  252. if (m_unresolved_imports.is_empty())
  253. return;
  254. HashTable<Name> resolved_imports;
  255. for (auto& import_ : m_unresolved_imports) {
  256. auto it = instance.exports().find_if([&](auto& export_) { return export_.name() == import_.name; });
  257. if (!it.is_end()) {
  258. resolved_imports.set(import_);
  259. m_resolved_imports.set(import_, it->value());
  260. }
  261. }
  262. for (auto& entry : resolved_imports)
  263. m_unresolved_imports.remove(entry);
  264. }
  265. void Linker::link(const HashMap<Linker::Name, ExternValue>& exports)
  266. {
  267. populate();
  268. if (m_unresolved_imports.is_empty())
  269. return;
  270. HashTable<Name> resolved_imports;
  271. for (auto& import_ : m_unresolved_imports) {
  272. auto export_ = exports.get(import_);
  273. if (export_.has_value()) {
  274. resolved_imports.set(import_);
  275. m_resolved_imports.set(import_, export_.value());
  276. }
  277. }
  278. for (auto& entry : resolved_imports)
  279. m_unresolved_imports.remove(entry);
  280. }
  281. AK::Result<Vector<ExternValue>, LinkError> Linker::finish()
  282. {
  283. populate();
  284. if (!m_unresolved_imports.is_empty()) {
  285. if (!m_error.has_value())
  286. m_error = LinkError {};
  287. for (auto& entry : m_unresolved_imports)
  288. m_error->missing_imports.append(entry.name);
  289. return *m_error;
  290. }
  291. if (m_error.has_value())
  292. return *m_error;
  293. // Result must be in the same order as the module imports
  294. Vector<ExternValue> exports;
  295. exports.ensure_capacity(m_ordered_imports.size());
  296. for (auto& import_ : m_ordered_imports)
  297. exports.unchecked_append(*m_resolved_imports.get(import_));
  298. return exports;
  299. }
  300. void Linker::populate()
  301. {
  302. if (!m_ordered_imports.is_empty())
  303. return;
  304. // There better be at most one import section!
  305. bool already_seen_an_import_section = false;
  306. m_module.for_each_section_of_type<ImportSection>([&](const ImportSection& section) {
  307. if (already_seen_an_import_section) {
  308. if (!m_error.has_value())
  309. m_error = LinkError {};
  310. m_error->other_errors.append(LinkError::InvalidImportedModule);
  311. return;
  312. }
  313. already_seen_an_import_section = true;
  314. for (auto& import_ : section.imports()) {
  315. m_ordered_imports.append({ import_.module(), import_.name(), import_.description() });
  316. m_unresolved_imports.set(m_ordered_imports.last());
  317. }
  318. });
  319. }
  320. }