图片起源：https://unsplash.com/photos/N...

本文作者：伍六一

Wasm 解释器我的项目地址：

https://github.com/mcuking/wasmc

背景

从去年年底开始笔者决定深刻 WebAssembly（为了书写不便，接下来简称为 Wasm）这门技术，在读《WebAssembly 原理与核心技术》这本书的过程中（这本书具体解说了 Wasm 的解释器和虚拟机的工作原理以及实现思路），萌发了实现一个 Wasm 解释器的想法，于是就有了这个我的项目。接下来咱们就直奔主题，看下到底如何实现一个 Wasm 解释器。

Wasm 背景常识

在具体论述解释器实现过程之前，首先介绍下 Wasm 相干的背景常识。

Wasm 是什么

Wasm 是一种底层类汇编语言，能在 Web 平台上以趋近原生利用的速度运行。C/C++/Rust 等语言将 Wasm 作为编译目标语言，能够将已有的代码移植到 Web 平台中运行，以晋升代码复用度。

而 Wasm 官网给出的定义是 —— WebAssembly（缩写为 Wasm）是一种基于栈式虚拟机的二进制指令格局。Wasm 被设计成为一种编程语言的可移植编译指标，能够通过将其部署到 Web 平台上，使其为客户端和服务端应用程序提供服务。

其中将 Wasm 定义为一种虚构指令集架构 V-ISA（Virtual-Instruction Set Architecture），对于这方面的解读，请参考上面执行阶段的内容。

接着来看下 Wasm 的一些特点：

  1. 档次必须低，尽量靠近机器语言，这样解释器才更容易进行 AOT/JIT 编译，以趋近原生利用的速度运行 Wasm 程序；
  2. 作为指标代码，由其余高级语言编译器生成；
  3. 代码平安可控，不能像真正的汇编语言那样能够执行任意操作；
  4. 代码必须是平台无关的（不能是平台相干的机器码），这样才能够跨平台执行，所以采纳了虚拟机/字节码技术。
Tip: 对于 Wasm 的更多具体介绍可参考笔者翻译的文章 《WebAssembly 的后 MVP 时代的将来：一棵卡通技能树（译）》

Wasm 能做什么

Wasm 目前曾经在浏览器端的图像处理、音视频解决、游戏、IDE、可视化、科学计算等，以及非浏览器端的Serverless、区块链、IoT 等畛域有肯定的利用。如果想要理解更多无关 Wasm 利用的内容，能够关注笔者的另一个 GitHub 仓库：

https://github.com/mcuking/Awesome-WebAssembly-Applications

Wasm 标准

Wasm 技术目前有 4 份标准：

  • 外围标准 —— 定义了独立于具体嵌入（即平台无关）的 Wasm 模块的语义。
  • JavaScript API —— 定义用于从 JavaScript 外部拜访 Wasm 的 JavaScript 类和对象。
  • Web API —— 定义了专门在 Web 浏览器中可用的 JavaScript API 扩大。
  • WASI API —— 定义了一个模块化的零碎接口来在 Web 之外运行 Wasm，例如拜访文件、网络链接等能力。

本文次要介绍的 Wasm 解释器次要是运行在非浏览器环境，因而无需关注 JavaScript API 和 Web API 标准。

另外目前实现的版本并没有波及到 WASI（后续有打算反对），所以目前只须要关注 外围标准 即可。

Wasm 模块

Wasm 模块次要有以下 4 种表现形式：

  • 二进制格局 —— Wasm 的次要编码格局，以 .wasm 后缀结尾。
  • 文本格式 —— 次要是为了不便开发者了解 Wasm 模块，或者编写小型的测试代码，以 .wat 后缀结尾，相当于汇编语言程序。
  • 内存格局 —— 模块加载到内存的体现，该表现形式与具体的 Wasm 虚拟机的实现无关，不同 Wasm 虚拟机的实现有不同的内存示意。
  • 模块实例 —— 如果将内存格局了解为面向对象语言中的类，那模块实例就相当于“对象”。

下图就是应用 C 语言编写的阶乘函数，以及对应的 Wasm 文本格式和二进制格局。

而内存格局和具体的 Wasm 解释器的实现无关，例如本我的项目的内存格局大抵如下（在前面执行阶段局部会具体解说）：

各个格局之间的关联如下：

  • 二进制格局次要由高级编程语言编译器生成，也可通过文本格式编译生成。
  • 文本格式能够有开发者个间接编写，也可由二进制反编译生成。
  • Wasm 解释器通常会将二进制模块解码为外部模式，即内存格局（比方 C/C++ 构造体），而后再进行后续解决。

最初举荐一个名为 WebAssembly Code Explorer 的站点，能够更直观地查看 Wasm 二进制格局和文本格式之间的关联。

https://wasdk.github.io/wasmc...

解释器实现原理

通过下面的介绍，置信大家对 Wasm 技术曾经有了大抵的理解。接下来咱们从剖析 Wasm 二进制文件的执行流程开始，探讨解释器的实现思路。

Wasm 二进制文件被执行次要分 3 个阶段：解码、验证、执行

  1. 解码阶段：将二进制格局解码为内存格局。
  2. 验证阶段：对模块进行动态剖析，确保模块的构造满足标准要求，且函数的字节码没有不良行为（例如调用不存在的函数）。
  3. 执行阶段：进一步分为实例化和函数调用两个阶段。

Tip: 本我的项目实现的解释器，并没有一个独自的验证阶段。而是将具体的验证散布在解码阶段或执行阶段中进行，例如在解码阶段验证是否存在非法的段 ID，在执行阶段验证函数的参数或返回值的类型或数量是否和函数签名匹配等。

另外实例化过程在解码阶段就实现了，执行阶段仅须要进行函数调用即可。
所谓实例化，次要内容就是为内存段、表段等申请空间，记录所有函数(自定义的函数和导入的函数)的入口地址，而后将模块的所有信息记录到一个对立的数据结构 module 中。

接下来咱们就别离对解码阶段和执行阶段的实现细节进行具体论述。

解码阶段

Wasm 二进制文件构造

和其余二进制格局（例如 Java 类文件）一样，Wasm 二进制格局也是以魔数和版本号结尾，之后就是模块的主体内容，这些内容依据不同用处被别离放在不同的段（Section） 中。一共定义了 12 种段，每种段调配了 ID（从 0 到 11）。除了自定义段之外，其余所有段都最多只能呈现一次，且须依照 ID 递增的程序呈现。ID 从 0 到 11 顺次有如下 12 个段：

自定义段、类型段、导入段、函数段、表段、内存段、全局段、导出段、起始段、元素段、代码段、数据段

Tip: 其中不同段之间的排序是有肯定根据的，次要目标是为了进行流编译 —— 即一边下载 Wasm 模块一边将其编译到机器码，详细信息可查阅文章 《Making WebAssembly even faster: Firefox’s new streaming and tiering compiler》

换句话说，每一个不同的段都形容了这个 Wasm 模块的一部分信息。而模块内的所有段放在一起，便形容了这个 Wasm 模块的全副信息：

  • 内存段和数据段：内存段用于存储程序的运行时动态数据。数据段用于存储初始化内存的静态数据。内存能够从内部宿主导入，同时内存对象也能够导出到内部宿主环境。
  • 表段和元素段：表段用于存储对象援用，目前对象只能是函数，因而能够通过表段实现函数指针的性能。元素段用于存储初始化表段的数据。表对象能够从内部宿主导入，同时表对象也能够导出到内部宿主环境。
  • 起始段：起始段用于存储起始函数的索引，即指定了一个在加载时主动运行的函数。起始函数次要作用：1. 在模块加载后进行初始化工作； 2. 将模块变成可执行文件。
  • 全局段：全局段用于存储全局变量的信息（全局变量的值类型、可变性、初始化表达式等）。
  • 函数段、代码段和类型段：这三个段均是用于存储表白函数的数据。其中
    类型段：类型段用于存储模块内所有的函数签名（函数签名记录了函数的参数和返回值的类型和数量），留神若存在多个函数的函数签名雷同，则存储一份即可。
    函数段：函数段用于存储函数对应的函数签名索引，留神是函数签名的索引，而不是函数索引。
    代码段：代码段用于存储函数的字节码和局部变量，也就是函数体内的局部变量和代码所对应的字节码。
  • 导入段和导出段：导出段用于存储导出项信息（导出项的成员名、类型，以及在对应段中的索引等）。导入段用于存储导入项信息（导入项的成员名、类型，以及从哪个模块导入等）。导出/导入项类型有 4 种：函数、表、内存、全局变量。
  • 自定义段：自定义段次要用于保留调试符号等和运行无关的信息。
Tip: 在下面的 Wasm 二进制格局的段中，表段应该比会较难以了解，这里顺便对其阐明下。
在 Wasm 设计思维中，与执行过程相干的代码段/栈等元素和内存是齐全拆散的，这与通常的体系结构中代码段/数据段/堆/栈全都处在对立编址内存空间状况齐全不同，函数地址对 Wasm 程序来说是不可见的，更不要说将函数当作变量一样传递、批改和调用。
表是实现这一机制的要害，表用于存储对象援用，目前对象只能是函数，也就是说目前表中只是用来存储函数索引值。Wasm 程序只能通过表中的索引，找到对应函数索引值来调用函数，并且运行时的栈数据也不保留在内存对象中。由此彻底杜绝了 Wasm 代码越界执行的可能，最蹩脚状况不过是在内存对象中产生一堆谬误数据而已。

晓得了每个段对应的用处以及每个段的具体编码格局（具体的编码格局可查看 module.c 中的 load_module 函数中的正文），咱们就能够对 Wasm 二进制文件进行解码，将其“翻译”成内存格局，也就是将模块的所有信息记录到一个对立的数据结构中 —— module，module 构造如下图所示：

Tip: 为了节约空间，让二进制文件更加紧凑，Wasm 二进制格局采纳 LEB128(Little Endian Base 128) 来编码列表长度、索引等整数值。LEB128 是一种变长编码格局，32 位整数编码后会占 1 到 5 个字节，64 位整数编码后会占 1 到 10 个字节。越小的整数编码后占用的字节数越少。因为像列表长度、索引这样的整数通常都比拟小，所以采纳 LEB128 编码就能够起到节约空间的作用。
LEB128 有两个特点：1. 采纳小端序示意，即低位字节在前，高位字节在后；2. 采纳 128 进制，即每 7 位为一组（一个字节的后 7 位），空进去的最高位是标识位，1 示意还有后续字节，0 示意没有。
LEB128 有两个变体，别离用来编码无符号整数和有符号整数，具体实现可查阅 https://github.com/mcuking/wasmc/blob/master/source/utils.c 中的 read_LEB 函数。

最初展现下解码阶段对应的局部理论代码截图如下：

更多细节倡议查阅 https://github.com/mcuking/wasmc/blob/master/source/module.c 中的 load_module 函数，其中有丰盛的正文解说。

执行阶段

通过了下面的解码阶段，咱们能够从 Wasm 二进制文件中失去涵盖执行阶段所须要的全副信息的内存格局，接下来咱们来一起摸索如何基于下面的内存格局实现执行阶段。在正式开始之前，首先须要介绍下栈式虚拟机的相干常识作为铺垫。

官网对 Wasm 的定义 —— Wasm 是基于栈式虚拟机的二进制指令格局。也就是说 Wasm 不仅仅是一门编程语言，也是一套虚拟机体系结构标准。那么什么是虚拟机，什么又是栈式虚拟机呢？

虚拟机概念

虚拟机是软件对硬件的模仿，借助操作系统和编译器提供的性能模仿硬件的工作，这里次要指对硬件 CPU 的模仿。虚拟机执行指令次要有以下 3 个步骤：

  1. 取指—从程序计数器 PC 指向指令流中的地址获取指令
  2. 译码—判断指令的类型，进入相应的解决流程
  3. 执行—依照指令的含意执行相应的函数

执行指令流中的一条条指令，就是一直循环执行下面的三个步骤。循环执行的过程中须要有一个标记来记录以后曾经执行到哪一条指令，也就是程序计数器 PC (Program Count) —— 用于保留下一条待执行指令的地址。

Tip: 提供给 Wasm 虚拟机解释执行的不是平台相干的机器码，而是由 Wasm 自定义的一套指令集所形成的字节码，次要是为了实现跨平台的目标 —— 用软件去模仿 CPU，并定义一套相似 CPU 指令集的自定义指令集，这样只须要虚拟机自身的程序针对不同平台适配即可，而运行在虚拟机上的程序则无需关怀跑在哪个平台上。

Wasm 指令集

Wasm 指令次要分为 5 大类：

  1. 控制指令—函数调用/跳转/循环等
  2. 参数指令—抛弃栈顶等
  3. 变量指令—读写全局/局部变量
  4. 内存指令—内存加载/存储
  5. 数值指令—数值计算

每条指令蕴含两局部信息：操作码和操作数。

  • 操作码（Opcode）：是指令的 ID，决定指令将执行的操作，固定为 1 个字节，因而指令集最多蕴含 256 种指令，这种代码又被称为字节码。Wasm 标准共定义了 178 种指令。因为操作码是一个整数，便于机器解决但对人不敌对，因而 Wasm 标准给每个操作码定义了助记符。

下图是 Wasm 局部指令的操作码助记符的枚举，实现版请查阅 https://github.com/mcuking/wasmc/blob/master/source/opcode.h。

另外 GitHub 上有一个可视化表格比拟直观地展现了 Wasm 所有的操作码，感兴趣的同学能够点击查看下。

https://pengowray.github.io/w...

对于操作数的内容会在上面的栈式虚拟机局部介绍。

栈式虚拟机

虚拟机又大抵分为两种：寄存器虚拟机和栈式虚拟机。

  • 寄存器式虚拟机：齐全依照硬件 CPU 实现思路，虚拟机外部也模仿了寄存器，操作数和指令执行的后果均可寄存在寄存器中。理论案例有 V8 / Lua 虚拟机。
    因为寄存器个数是无限的，如何将有限的变量调配到无限的寄存器中而不抵触，须要寄存器调配算法，例如经典的图着色算法。所以寄存器式虚拟机实现难度略大，但优化后劲更大。
  • 栈式虚拟机：指令的后果存储在模仿的操作数栈（Operand Stack）中，和寄存器式虚拟机相比实现更简略。理论案例有 JVM / QuickJs / Wasmer。

接下来咱们就具体介绍下栈式虚拟机的工作机制。

操作数

栈式虚拟机次要特点是领有一个操作数栈，Wasm 绝大部分指令都是在操作数栈上执行某种操作，例如上面的指令：

f32.sub：示意从操作数栈弹出 2 个 32 位浮点数，计算它们的差并将后果压入到操作数栈顶。

其中从操作数栈弹出的 2 个 32 位浮点数就是操作数，上面是具体定义：

操作数，也称动静操作数，是指在运行时位于操作数栈顶并被指令操纵的数。

立刻数

咱们再看另一个指令的例子：

i32.const 3：示意压入索引为 3 的 32 位整数类型的局部变量到操作数栈顶。

而这个数值 3 就是立刻数，上面是具体定义：

立刻数，也称动态立刻参数 / 动态操作数，立刻数是间接硬编码在指令里的（也就是字节码里），紧跟在操作码前面。大部分 Wasm 指令是没有立刻数的，欲知 Wasm 指令中具体哪些指令是带有立刻数的，请查阅 https://github.com/mcuking/wasmc/blob/master/source/module.c 中的 skip_immediate 函数。

下面探讨的仅仅是一条指令的执行，上面咱们在看下一个函数在栈式虚拟机上是如何被执行的：

  1. 调用方将参数压入到操作数栈中
  2. 进入函数后，初始化参数
  3. 执行函数体中的指令
  4. 将函数的执行后果压入到操作数栈顶并返回
  5. 调用方从操作数栈上获取函数的返回值

如下图所示：

由此可见，函数调用时参数传递和返回值获取，以及函数体中的指令执行，都是通过操作数栈来实现的。

调用栈和栈帧

从下面的形容中能够看出，函数调用常常是嵌套的，例如函数 A 调用函数 B，函数 B 调用函数 C。因而须要另外一个栈来保护函数之间的调用关系信息 —— 调用栈（Call Stack）。

调用栈是由一个个独立的栈帧组成，每次函数调用，都会向调用栈压入一个栈帧（留神：为了论述的简洁明了，仅探讨函数状况，其余例如 If / Loop 等管制块暂不在本文探讨中）。每次函数执行完结，都会从调用栈弹出对应栈帧并销毁。一连串的函数调用，就是不停创立和销毁栈帧的过程。但在任一时刻，只有位于调用栈顶的栈帧是沉闷的，也就是所谓的以后栈帧。

每个栈帧包含以下内容：

  1. 栈帧关联的函数构造体变量，用于存储该函数的所有信息。
  2. 操作数栈，用于存储参数、局部变量、以及函数体指令执行过程中的操作数。
    须要揭示的是，所有函数关联的栈帧是共用一个残缺的操作数栈，每个栈帧会占用这个操作数栈中的某一部分，每个栈帧只须要一个指针保留本人那局部操作数栈栈底地址，用以和其余栈帧的操作数栈局部做辨别即可。
    这样做的益处是：调用方函数和被调用函数所关联的栈帧的操作数栈局部在整个操作数栈中是相邻的，便于调用方函数将参数传递给被调用函数，也便于被调用函数执行实现后将返回值传递给调用函数。
  3. 函数返回地址，用于存储该栈帧调用指令的下一条指令的地址，当该栈帧从调用栈弹出时，会返回到该栈帧调用指令的下一条指令继续执行，换句话说就是以后栈帧对应的函数执行完退出后，返回到调用该函数的中央继续执行前面的指令。

Tip: 目前这个解释器定义的栈帧中比没有相似 JVM 虚拟机栈帧中的局部变量表，而是将参数、局部变量和操作数都放在了操作数栈上，次要目标有两个：

  1. 实现简略，不须要额定定义局部变量表，能够很大水平简化代码。
  2. 让参数传递变成无操作 NOP，能够让两个栈帧的操作数栈有一部分数据是重叠的，这部分数据就是参数，这样天然就起到了参数在不同函数之间传递的作用。

理论示例

通过下面的铺垫，置信大家对栈式虚拟机有了肯定的意识。最初咱们用一个理论示例来论述下整个执行过程：

上面这个 Wasm 文本格式中的有两个函数：compute 函数和 add 函数，其中 add 函数次要是接管两个数（类型别离是 32 位整数和 32 位浮点数），计算两数之和。compute 函数中调用了两次 add 函数，留神第二次调用 add 函数时，操作数栈上曾经保留了上次调用 add 函数时的返回后果（再一次印证了两个函数关联的栈帧是共用同一个残缺的操作数栈的，能够很便捷地实现函数之间参数的传递），所以这次仅须要传入第二个参数即可。

(module    (func $compute (result i32)        i32.const 13    ;; 向操作数栈压入 13        f32.const 42.0  ;; 向操作数栈压入 42.0        call $add       ;; 调用 $add 函数失去 55        f32.const 10.0  ;; 向操作数栈压入 10.0        call $add       ;; 再调用 $add 函数失去 65    )    (func $add(param $a i32) (param $b f32) (result i32)        i32.get_local $a  ;; 将类型为 32 位整数的局部变量 $a 压入到操作数栈        f32.get_local $b  ;; 将类型为 32 位浮点数的局部变量 $b 压入到操作数栈        i32.trunc_f32_s   ;; 将以后操作数栈顶的 32 位浮点数 $b 截断为 32 有符号位整数（截掉小数局部）        i32.add           ;; 将操作数栈顶和次栈顶的 32 位整数从操作数栈弹出，并计算两者之和而后将和压入操作数栈    )    (export "compute" (func $compute))    (export "add" (func $add)))

对应的就是其执行过程的示意图如下：

最初展现下执行阶段对应的局部理论代码截图如下：

能够看到虚拟机的取指、译码、执行三个阶段，能够应用 while 循环和 switch-case 语句来简略地实现。更多细节倡议查阅 https://github.com/mcuking/wasmc/blob/master/source/interpreter.c 中的 interpreter 函数，其中有丰盛的正文解说。

结束语

以上就是 Wasm 解释器实现中的核心内容，当然这仅仅是 Wasm 解释器的最根本的性能 —— 简略地逐条解析并执行指令，没有像其余业余的解释器那样提供 JIT 性能 —— 即先解释执行字节码来疾速启动，而后再通过 JIT 将其编译成平台相干的机器码，以晋升前面代码执行的速度（注：JIT 的具体实现过程因解释器而异）。

所以用本我的项目的解释器解释执行 Wasm 文件，速度上并没有太多劣势。但也正是因为其实现比较简单，所以源码更易读，并且其中有丰盛的正文，所以非常适合对 Wasm 有趣味的读者疾速理解该技术的外围原理。

须要指出的是，本篇文章并没有波及到如何应用 Wasm 技术。而恰好笔者正在基于 Wasm 和 FFmpeg 开发反对 H256 编码的视频播放器，相干文章链接如下：

《深刻 WebAssembly 之视频播放器利用篇》

预计在视频播放器投入到理论生产环境后，逐步完善文章内容 —— 重点论述如何在前端我的项目中更好地利用 Wasm 技术，敬请期待～

https://github.com/mcuking/blog

参考资料

  • 《WebAssembly 原理与核心技术》
  • 《WebAssembly 实战》
  • 《WebAssembly 规范入门》
  • https://github.com/kanaka/wac
  • https://github.com/wasm3/wasm3
本文公布自 网易云音乐大前端团队，文章未经受权禁止任何模式的转载。咱们长年招收前端、iOS、Android，如果你筹备换工作，又恰好喜爱云音乐，那就退出咱们 grp.music-fe(at)corp.netease.com！