自己动手实现一个WebAssembly解释器_UTF_8

见贤思齐

1. 前言课程的 WebAssembly 工作原理一章已经详细介绍了基于栈结构的指令执行原理和过程，然而，了解 WebAssembly 原理最有效的方式仍然是自己动手实现一个执行引擎；本文将从零开始实现一个简单的 WebAssembly 解释器 WAInterp (WebAssembly Interpreter)，通过这一过程来进一步掌握和实践 WebAssembly 虚拟机技术。本文将介绍最基本的虚拟机实现技术，高级优化虚拟机相关技术请阅读参考文献 [2~5] 中列出的相关专业书籍和文档。2. WAInterp 解析器流程从语义上讲，一个 WebAssembly 模块的生命周期可以分为"编译"、"解码"、"验证"、"实例化"、"指令执行" 几个阶段，而各个阶段分别创建和使用了 WebAssembly 模块的不同变体:编译阶段: 将高级语言编译为 WebAssembly 规范定义的二进制或者文本两种模块格式，如果和传统汇编语言类比，模块的二进制格式相当于目标文件或可执行文件格式，文本格式则相当于汇编语言；解码阶段: 将二进制模块解码为内存格式，内存格式是模块加载到内存之后的内部数据结构表示 (与实现相关)；验证阶段: 对模块进行静态分析，确保模块的结构满足规范要求，且函数的字节码没有不良行为 (比如调用不存在的函数等)；实例化阶段: 完成内存中函数、Table，线性内存，全局变量的链接及初始化工作；执行阶段: 则完成函数的指令序列执行。WebAssembly 模块生命周期流程如下图 1 所示。图 1. WebAssembly 模块生命周期流程图本文将从零开始实现一个简单的基于 IR (Intermediate Representation) 树遍历的 WebAssembly 二进制解释器 "WAInterp"；该解析器的执行主要包括二进制模块的"解码"、"实例化"、"执行"等几个阶段。接下来各个小节将逐一介绍每个阶段的详细设计和实现，以便读者可以循序渐进地构建 WAInterp 解析器。由于本文的主要目的是更好的理解 WebAssembly 底层原理、实践 WebAssembly 虚拟机相关技术，因此，我们采用相对简单和便于发布、共享的 Typescript 作为解析器的开发语言，并以 NPM 包的形式发布至 NPM Registery[6]，以便开发者能够方便的集成。3. WAInterp 解码器WAInterp 解释器的输入是 WebAssembly 二进制格式文件，实现二进制模块的加载和解码是模块实例化和指令执行的前提和必要条件；因此，本节先简要回顾下 WebAssembly 二进制格式相关内容，然后，实现一个二进制文件解码器；从而完成 WebAssembly 文件加载并转换为运行环境中对应的数据结构。3.1 WAInterp 模块结构定义与其他很多二进制格式 (比如 Java 类文件、ELF二进制文件) 类似，WebAssembly 二进制文件也是以魔数 (Magic Number )和版本号开头。在魔数和版本号之后是模块的主体内容，这些内容以段 (Section) 的形式进行组织。WebAssembly MVP 规范一共定义了12种段，并给每种段分配了 ID (从0到11)，除了自定义段以外，其他所有的段都最多只能出现一次，且必须按照段 ID 递增的顺序出现 (本文中暂不实现自定义段相关功能)。WebAssembly 模块结构如下图 2 所示。图 2. WebAssembly 模块文件结构根据 WebAssembly 模块的规范和格式定义 (如上图2所示)，我们为二进制模块定义如下的模块数据类型。typeBinaryModule={Magic:uint32,Version:uint32,TypeSec:Array,ImportSec:Array,FuncSec:Array,TableSec:Array,MemSec:Array,GlobalSec:Array,ExportSec:Array,StartFunc:Funcidx,ElemSec:Array,CodeSec:Array>,DataSec:Array}在详细描述 BinaryModule 各段 (Segment) 的表示和解码之前，我们先为 WebAssembly 内置的值类型定义对应的数据结构。WebAssembly 规范中定义了 4 种基本的值类型：32 位整数 (简称 i32)、64 位整数 (简称 i64)、32 位浮点数 (简称 f32) 和 64 位浮点数 (简称 f64)，与高级语言中的整数类型有所不同，WebAssembly 底层的整数类型是不区分符号的。高级语言所支持的一切类型 (比如布 尔值、数值、指针、数组、结构体等)，都必须由编译器翻译成这 4 种基本类型或者组合。按照二进制规范，我们定义如下的 valtypes 来表示模块中定义的基本类型编码。constvaltypes={0x7f:"i32",0x7e:"i64",0x7d:"f32",0x7c:"f64",0x7b:"v128",};在 BinaryModule 中的大部分段都包含结构化的项目，运行环境中这些结构化项目的容器被称呼为 "索引空间"。函数签名、函数、表、内存、全局变量等类型在模块内有各自的索引空间；局部变量和跳转标签在函数内有各自的索引空间。模块的各类索引空间及其作用可以总结如下：类型索引空间: 不管是外部导入的函数还是内部定义的函数，其签名全都存储在类型段中，因此类型段的有效索引范围就是类型索引空间。函数索引空间: 函数索引空间由外部函数和内部函数共同构成；当调用某函数时，需要给定该函数的索引。全局变量索引空间: 和函数一样，全局变量索引空间也是由外部全局变量和内部全局变量共同构成的；当读写某全局变量时，需要给定该全局变量的索引。表和内存索引: 表和内存也可以从外部导入，所以索引空间的情况和函数索引空间类似；由于 WebAssembly MVP 规范的限制，最多只能导入或定义一个表和内存，所以索引空间内的唯一有效索引只能是 0。局部变量索引: 函数的局部变量索引空间由函数的参数和局部变量构成；当读写某参数或局部变量时，需要给定该参数或局部变量的索引。跳转标签索引: 和局部变量索引一样，每个函数有自己的跳转标签索引空间；结构化控制指令和跳转指令需要指定跳转标签索引。为了提高代码的可读性，我们给这些索引分别定义了类型别名，如下代码所示。typeU32Literal=NumberLiteral;typeTypeidx=U32Literal;typeFuncidx=U32Literal;typeTableidx=U32Literal;typeMemidx=U32Literal;typeGlobalidx=U32Literal;typeLocalidx=U32Literal;typeLabelidx=U32Literal;typeIndex=|Typeidx|Funcidx|Tableidx|Memidx|Globalidx|Localidx|Labelidx3.2 WAInterp 段解码模块解码是将 WebAssembly 二进制文件中各个段的编码数据解析为运行时环境中的数据结构的过程。为了便于理解，我们对 WebAssembly 二进制模块的的形式化表示[7] 做了简化，其中，id 表示各个段的识别号，byte_count 表示对应段的字节数，vec表示元素类型为 T 的向量，leb(T) 用于表示对应类型 T 的 LEB128 编码值，竖线 "|" 作为各个语义域的分隔符；采用简化的形式化描述，WebAssembly 中二进制格式中段编码可以见如下的描述。sec:id|byte_count|vecbyte_count:leb(u32)#LEB128编码的32位无符号整数上面我们已经简要地介绍了 WebAssembly 的内置类型及段结构描述，接下来，我们将逐一实现各个段的二进制数据编码，将它们转换为运行环境中的对象"内存格式"数据结构。类型段 (ID = 1)类型段记录了模块中使用到的所有函数类型，函数类型包括参数数量和类型，以及返回值数量和类型。在 WebAssembly 二进制格式里，函数类型以 0x60 开头，后跟参数数量、参数类型、返回值数量和返回值类型，函数类型的二进制编码格式如下所示。type_section:id|byte_count|vectorfunc_type:0x60|vec|vec针对类型段及函数类型编码，我们定义如下的数据结构；其中 FuncSig 表示函数类型签名，其中 params 描述函数的参数数量和类型，result 描述返回值数量和类型。consttypesInModule:ArraytypeTypeInstruction={type:"TypeInstruction";id:Index;functype:FuncSig;};typeFuncSig={params:Array,result:Array,};typeFuncParam={id:string,valtype:Valtype,};基于类型段和函数类型的定义，WAInterp 定义 parseTypeSection 函数实现类型段的二进制解析；其中，typesInModule 为模块中函数类型集合。functionparseTypeSection(numberOfTypes:number){consttypesInModule:Array=[];for(leti=0;i=parseVec((b)=>constants.valtypes[b]);constparams=paramValtypes.map((v)=>t.funcParam(/*Valtype*/v,undefined));constresult:Array=parseVec((b)=>constants.valtypes[b]);typesInModule.push(t.typeInstruction(undefined,t.signature(params,result)),);}else{thrownewError("Unsupportedtype:"+toHex(type));}}returntypesInModule;}导入段 (ID = 2)一个模块可以导入函数、表、内存、全局变量 4 种类型的外部对象；这些导入对象通过模块名、成员名，以及具体描述信息在模块的导入段进行声明，导入段的二进制编码格式如下所示。import_sec:0x02|byte_count|vecimport:module_name|member_name|import_descimport_desc:tag|[type_idx,table_type,mem_type,global_type]针对导入段及导入项的结构，我们定义如下的数据结构；其中 ModuleImport 为导入项，module 和 name 分别表示导入的模块名和符号名；ImportDescr 用于表示实际导入的函数、表、内存、 全局变量的详细信息。为了表示 4 种不同的导入项， ImportDescr 数据类型为 GlobalType，Table，Memory，FuncImportDescr 的组合类型；其中 GlobalType 用于描述全局变量类型信息；Table 用于描述表类型信息，元素类型可以为 funcref 和 externref；Memory 用于描述内存类型信息；FuncImportDescr 用户描述导入的外部函数签名信息，如下代码所示。constimportsInModule:ArraytypeModuleImport={type:"ModuleImport";module:string;name:string;descr:ImportDescr;};typeImportDescr=GlobalType|Table|Memory|FuncImportDescr;typeGlobalType={type:"GlobalType";valtype:Valtype;mutability:Mutability;};typeTable={type:"Table";elementType:TableElementType;limitsimit;name:Identifier;elements:Array;};typeTableElementType="funcref"|"externref"typeMemory={type:"Memory";limitsimit;id:Index;};typeFuncImportDescr={type:"FuncImportDescr";id:Identifier;signature:Signature;};基于导入段二进制格式和数据结构定义，WAInterp 定义 parseImportSection 函数实现导入段的二进制解析，其中， importsInModule 为模块中的导入项集合。functionparseImportSection(numberOfImports:number){constimportsInModule:Array=[];for(leti=0;i函数段实际声明了模块内部定义的函数类型，我们定义如下的数据结构来表示模块中的函数类型。typeFuncType={id:Identifier,signature:Signature,isExternal:boolean,};typeFuncSig={params:Array,result:Array,};基于函数段的二进制格式及数据结构，WAInterp 定义 parseFuncSection 函数实现导入段的二进制解析；其中， functionsInModule 为模块中函数集合。functionparseFuncSection(numberOfFunctions:number){letfunctionsInModule:Array=[];for(leti=0;i#MVPvec长度只能是1table_type:0x70|limitslimits:tag|min|max针对 Table 段的编码，我们定义如下的数据结构，其中 TableElementType 描述表中元素类型，当前只能为 funcref；Limit 用于描述表元素大小的限制。consttablesInModule:ArraytypeTable={type:"Table";elementType:TableElementType;limitsimit;name:Identifier;elements:Array;};typeTableElementType="funcref"|"externref"typeLimit={type:"Limit";min:number;max:number;};基于表段的二进制格式和数据结构定义，WAInterp 定义 parseTableSection 函数实现表段的二进制解析；其中，tablesInModule 为模块中表的集合。functionparseTableSection(numberOfElements:number){consttablesInModule:Array=[];for(leti=0;i#MVPvec长度只能是1mem_type:limits针对内存段和内存类型编码，我们定义如下的数据结构，其中 Limits 用于描述指定内存页数限制。constmemoriesInModule:ArraytypeMemory={type:"Memory";limitsimit;id:Index;};typeLimit={type:"Limit";min:number;max:number;};基于内存段的二进制格式和数据结构定义，WAInterp 定义 parseTableSection 函数实现内存段的二进制解析；其中，memoriesInModule 为模块中的内存集合。functionparseMemorySection(numberOfElements:number){constmemoriesInModule:Array=[];for(leti=0;iglobal:global_type|init_exprglobal_type:val_type|mutinit_expr:vec|0x0B针对全局段和全局变量类型编码，我们定义如下的数据结构，其中 GlobalType 描述全局变量类型及其可变性；init 是初始化表达式，用指令序列 Array 来表示。constglobalsInModule:Array;typeGlobal={type:"Global";globalType:GlobalType;init:Array;name:Identifier;};typeGlobalType={type:"GlobalType";valtype:Valtype;mutability:Mutability;};typeValtype="i32"|"i64"|"f32"|"f64";typeMutability="const"|"var";基于全局段的二进制格式和数据结构定义，WAInterp 定义 parseTableSection 函数实现全局段的二进制解析；其中，globalsInModule 为模块中全局变量集合。functionparseGlobalSection(numberOfGlobals:number){constglobalsInModule:Array=[];for(leti=0;i=[];parseInstructionBlock(init);constglobalDescr:Global=t.global(globalType,init,undefined);globalsInModule.push(globalDescr);}returnglobalsInModule;}导出段 (ID = 7)导出段列出模块所有导出成员，只有被导出的成员才能被外界访问，其他成员被很好地“封装”在模块内部。与模块导入类似，一个模块也可以导出 "函数"、"表"、"内存"、 "全局变量" 4 种类型的成员；导出项除了指定导出的符号名，还需要指定实际导出的元素内容，而元素的内容仅指定对应索引空间中成员索引即可，因为通过索引即可从对应的索引空间中获取需要的数据。导出段及其导出项二进制编码格式如下所示。export_sec:0x07|byte_count|vecexport:name|export_descexport_desc:tag|[func_idx,table_idx,mem_idx,global_idx]针对导出段编码，我们定义如下的数据结构，其中 name 为导出的符号名，ModuleExportDescr 用于描述导出的类型以及导出项在各自所以空间中的索引值。constexportsInModule:ArraytypeModuleExport={type:"ModuleExport";name:string;descr:ModuleExportDescr;};typeModuleExportDescr={type:"ModuleExportDescr";exportType:ExportDescrType;id:Index;};typeExportDescrType="Func"|"Table"|"Memory"|"Global";基于导出段的二进制格式和数据结构定义，WAInterp 定义 parseTableSection 函数实现全局段的二进制解析；其中，exportsInModule 为导出对象集合。functionparseExportSection(numberOfExport:number){constexportsInModule:Array;for(leti=0;ielem:table_idx|offset_expr|vecoffset_expr:vec|0x0B针对元素段编码格式，我们定义如下的数据结构；其中，offset 为初始化表达式描述的表初始化偏移量，funcs 为函数索引列表。constelemsInModule:Array;typeElem={type:"Elem";table:Index;//tableindexoffset:Array;//offsetintablefuncs:Array;//funcindice};基于元素段的二进制格式和数据结构定义，WAInterp 定义 parseElemSection 函数实现元素段的二进制解析。functionparseElemSection(numberOfElements:number){constelemsInTable:Array=[];for(leti=0;i=[];parseInstructionBlock(instr);//offsetexpressionconstindicesu32=readU32();//funcindexnumberconstindices=indicesu32.value;skipBytes(indicesu32.nextIndex);constindexValues:Arrany=[];for(leti=0;icode:byte_count|vec|exprlocals:local_count|val_type针对代码段的编码格式，我们定义如下的数据结构，其中 code 为函数体的指令序列，locals 为局部变量列表。const funcBodiesInModule : Array；typeFuncBody={code:Array,locals:Array,bodySize:number,}基于代码段的二进制格式和数据结构定义，WAInterp 定义 parseCodeSection 函数实现元素段的二进制解析，其中 funcBodiesInModule 为模块中的函数体集合。functionparseCodeSection(numberOfFuncs:number){for(leti=0;i=[];constfuncLocalNumU32=readU32();//localgroupcountconstfuncLocalNum=funcLocalNumU32.value;skipBytes(funcLocalNumU32.nextIndex);constlocals:Array=[];constlocalsTypes:Array=[];for(leti=0;i=[];for(leti=0;idata:mem_idx|offset_expr|vec针对数据段的编码规范，我们定义如下的数据结构；其中，memoryIndex 描述需要初始化的内存块；offset 描述内存中的数据区域的起始偏移量；initData 指定内存区域的初始化数据。constdataInModule:Array;typeData={type:"Data";memoryIndex:Memidx;offset:Array;initData:Array;};基于数据段的二进制格式和数据结构定义，WAInterp 定义 parseDataSection 函数实现元素段的二进制解析。functionparseDataSection(numberOfElements:number){constdataInModule:Array=[];for(leti=0;i=[];//offsetexprparseInstructionBlock(instrs);constbytes:Array=parseVec((b)=>b);//initdatadataInModule.push(t.data(t.memIndexLiteral(memoryIndex),instrs,t.byteArray(bytes)));}returndataInModule;}自定义段 (ID = 0)自定义段用于存放自定义功能数据，当前阶段主要用于保存调试符号信息。自定义段与其他段有如下两方面的差异，首先，自定义段不参与模块语义，自定义段存放的都是额外信息 (比如，函数名和局部变量名等调试信息，第三方扩展信息等)，即使完全忽略这些信息也不影响模块的执行；其次，自定义段可以出现在任何一个非自定义段前后，而且出现的次数不受限制。由于自定义段为定制化的需求服务，所以对于 WebAssembly 规范来说它的数据是非结构化的，即，对于自定义段中字节数组的结构化解析由对应的自定义功能模块负责。自定义段二进制编码格式如下所示。custom_sec:0x00|byte_count|name|vec针对自定义段的编码规范，我们定义如下的数据结构来表示；其中，Bytes 用于保存原始的字节数据，提供给自定义功能解析和使用。typeCustomSec={Name:stringBytes:Array}WAInterp 暂不考虑实现自定义段功能，因此，后续不再展开讨论自定义段，相关功能和详细的规范请参阅WebAssembly 核心规范[8]。3.3 WAInterp 模块解码在上一小节中，我们对模块中各个段的二进制编码格式做了详细分析，并为各段定义了对应的数据结构和解析函数。基于各段的解析函数和数据结构，WAInterp 定义 decode 函数来实现模块的二进制格式解析并转换为运行时环境中的对象实例；在 decode 函数中的，参数 buffer 是原始的模块二进制字节数组，返回值 Program 是解码后的运行时对象表示。解码的主要过程分为三个部分，第一部分是模块的文件头解析，包括模数和版本号；第二部分是各个段的解析及各个索引空间的创建；第三部分是运行时对象实例 Program 的创建和初始化。typeProgram={type:"Program";body:Array;};exportfunctiondecode(buffer:ArrayBuffer,optsecoderOpts)rogram魔数和版本号WebAssembly 模块二进制格式中魔数占 4 个字节，内容是\0asm；版本号也占 4 个字节，当前版本是 1。decode 函数中如下部分代码展示了魔数和版本号解码和校验过程，其中，解码失败后会直接抛出异常。exportfunctiondecode(buffer:ArrayBuffer,optsecoderOpts)rogram{constbuf:Uint8Array=newUint8Array(buffer);//skipirrelevantcode...parseModuleHeader();parseVersion();//skipirrelevantcode...}constmagicModuleHeader=[0x00,0x61,0x73,0x6d];//`\0asm`constmoduleVersion=[0x01,0x00,0x00,0x00];//1functionparseModuleHeader(){constheader=readBytes(4);skipBytes(4);if(byteArrayEq(constants.magicModuleHeader,header)===false){thrownewCompileError("magicheadernotdetected");}}functionparseVersion(){constversion=readBytes(4);skipBytes(4);if(byteArrayEq(constants.moduleVersion,version)===false){thrownewCompileError("unknownbinaryversion");}}段解析段解码是整个模块解码的核心，为了统一表示各个段的数据类型，定义 Node 作为各段类型的组合类型来统一表示；其中，Module 表示解码后的模块对象类型，fields 用于记录模块解码后各个段的实例对象，SectionMetadata 用于记录各个段的元信息，其他各个段的类型定义如上各个小节所述。typeNode=|Module|SectionMetadata|TypeInstruction|ModuleImport|Func|Global|Table|Memory|Elem|Data|ModuleExport|StarttypeModule={type:"Module";id:string;fields:Array;sectionMetas:Array;};typeSectionMetadata={type:"SectionMetadata";section:SectionName;startOffset:number;size:number;};decode 函数中对各个段的解析实现，如下代码片段所示。exportfunctiondecode(ab:ArrayBuffer,optsecoderOpts)rogram{constbuf=newUint8Array(ab);//skipirrelevantcode...letoffset:number=0;letsectionIndex:number=0;constmoduleFields:Array=[];while(offset;metadata:SectionMetadata|Array;nextSectionIndex:number;}{//skipnon-cricitalcode...constsectionId=readByte();//sectionidskipBytes(1);sectionIndex=sectionId+1;constnextSectionIndex=sectionIndex;constu32=readU32();//sectionsizeconstsectionSizeInBytes=u32.value;skipBytes(u32.nextIndex);switch(sectionId){caseconstants.sections.type:{//skipnon-cricitalcode...constu32=readU32();constnumberOfTypes=u32.value;skipBytes(u32.nextIndex);constmetadata=t.sectionMetadata("type",...);constnodes=parseTypeSection(numberOfTypes);return{nodes,metadata,nextSectionIndex};}caseconstants.sections.table:{//skipnon-cricitalcode...constu32=readU32();constnumberOfTable=u32.value;skipBytes(u32.nextIndex);constmetadata=t.sectionMetadata("table",...);constnodes=parseTableSection(numberOfTable);return{nodes,metadata,nextSectionIndex};}caseconstants.sections.import:{//skipnon-cricitalcode...constnumberOfImportsu32=readU32();constnumberOfImports=numberOfImportsu32.value;skipBytes(numberOfImportsu32.nextIndex);constmetadata=t.sectionMetadata("import",...);constnodes=parseImportSection(numberOfImports);return{nodes,metadata,nextSectionIndex};}caseconstants.sections.func:{//skipnon-cricitalcode...constnumberOfFunctionsu32=readU32();constnumberOfFunctions=numberOfFunctionsu32.value;skipBytes(numberOfFunctionsu32.nextIndex);constmetadata=t.sectionMetadata("func",...);constndoes=parseFuncSection(numberOfFunctions);return{nodes,metadata,nextSectionIndex};}caseconstants.sections.export:{//skipnon-cricitalcode...constu32=readU32();constnumberOfExport=u32.value;skipBytes(u32.nextIndex);constmetadata=t.sectionMetadata("export",...);constnodes=parseExportSection(numberOfExport);return{nodes,metadata,nextSectionIndex};}caseconstants.sections.code:{//skipnon-cricitalcode...constu32=readU32();constnumberOfFuncs=u32.value;skipBytes(u32.nextIndex);constmetadata=t.sectionMetadata("code",...);constnodes=parseCodeSection(numberOfFuncs)return{nodes,metadata,nextSectionIndex};caseconstants.sections.start:{//skipnon-cricitalcode...constmetadata=t.sectionMetadata("start",...);constnodes=[parseStartSection()];return{nodes,metadata,nextSectionIndex};}caseconstants.sections.element:{//skipnon-cricitalcode...constnumberOfElementsu32=readU32();constnumberOfElements=numberOfElementsu32.value;skipBytes(numberOfElementsu32.nextIndex);constmetadata=t.sectionMetadata("element",...)constnodes=parseElemSection(numberOfElements);return{nodes,metadata,nextSectionIndex};}caseconstants.sections.global:{//skipnon-cricitalcode...constnumberOfGlobalsu32=readU32();constnumberOfGlobals=numberOfGlobalsu32.value;skipBytes(numberOfGlobalsu32.nextIndex);constmetadata=t.sectionMetadata("global",...);constnodes=parseGlobalSection(numberOfGlobals);return{nodes,metadata,nextSectionIndex};}caseconstants.sections.memory:{//skipnon-cricitalcode...constnumberOfElementsu32=readU32();constnumberOfElements=numberOfElementsu32.value;skipBytes(numberOfElementsu32.nextIndex);constmetadata=t.sectionMetadata("memory",...);constnodes=parseMemorySection(numberOfElements);return{nodes,metadata,nextSectionIndex};}caseconstants.sections.data:{//skipnon-cricitalcode...constnumberOfElementsu32=readU32();constnumberOfElements=numberOfElementsu32.value;skipBytes(numberOfElementsu32.nextIndex);constmetadata=t.sectionMetadata("data",...);constnodes=parseDataSection(numberOfElements);return{nodes,metadata,nextSectionIndex};}caseconstants.sections.custom:{skipBytes(sectionSizeInBytes);//ignorecusomsectionreturn{nodes:[],metadata,nextSectionIndex};}}Program 构造上述过程已基本完了模块解码工作，最后 WAInterp 通过 module 和 program 函数来完成运行环境中 Module 和 Program 对象构造，如下代码所示。typeProgram={type:"Program";body:Array;};typeModule={type:"Module";id:string;fields:Array;metadata:ModuleMetadata;}exportfunctiondecode(ab:ArrayBuffer,optsecoderOpts)rogram//skipirrelevantcode...constmoduleFields:Array=[];//skipirrelevantcode...constmodule=t.module(...,moduleFields,...);returnt.program([module]);}exportfunctionmodule(id:string,fields:Array,...):Module{//skipirrelevantcode...constnode:Module={type:"Module",id,fields,};returnnode;}exportfunctionprogram(body:Array)rogram{//skipnon-cricitalcode...constnoderogram={type:"Program",body,};returnnode;}至此，我们已经完成了 WAInterp 的解码器的全部内容，接下来，我们基于解码后的 program 对象来完成模块的实例化工作。4. WAInterp 实例化WebAssembly 模块的实例化过程包括创建模块实例空间，实例构造并初始化索引空间，执行起始函数三个阶段。在本节中，我们将分别从这三个阶段来描述是和实现 WAInterp 实例化。4.1 创建实例空间实例空间是可以由 WebAssembly 程序操作的所有全局状态，它由实例化过程中分配的函数、表、内存和全局变量等所有实例的运行时表示组成；WAInterp 定义 Store 数据结构来表示实例空间。从语义上讲，Store 被定义为模块中各种类型实例的记录 _store 以及访问记录的各方法。exportconstNULL=0x0;typeInstType=FuncInstance|GlobalInstance|TableInstance|MemoryInstance|NULLinterfaceStore{_store:Array;malloc(Bytes):Addr;get(Addr):InstType;set(Addr,InstType):void;free(Addr):void;}基于 Store 的类型定义，WAInterp 定义 createStore 函数来创建实例空间；其中，_store 用于保存各种全局状态的记录；malloc，free，get，set 为实例空间操作和管理全局状态的方法。exportfunctioncreateStore():Store{const_store:Array=[];letindex:number=0;//mallocmemoryandreturnmemoryaddressfunctionmalloc(size:number):Addr{index+=size;return{index,size,};}//gettheinstanceofInstTypefrommemoryaddresspfunctionget(p:Addr):InstType{return_store[p.index];}//settheinstanceofInstTypeintomemoryaddresspfunctionset(p:Addr,value:InstType){_store[p.index]=value;}//freethememorywithmemoryaddresspfunctionfree(p:Addr){_store[p.index]=NULL;}return{_store,malloc,free,get,set,};}4.2 模块实例化当 WAInterp 完成实例空间创建后，运行时环境需要为模块中各种全局类型对象创建实例，并完成索引空间初始化，包括函数索引空间，表索引空间，内存索引空间，全局变量索引空间以及导出符号索引空间。WAInterp 定义 ModuleInstance 用于表示模块实例的数据结构；其中，Addr 表示实例对象在 Store 中的地址偏移量；funcaddrs 为函数索引表，用于表示函数实例在 Store 中的内存地址；tableaddrs 为表索引表，用于表示表实例在 Store 中的内存地址；memaddrs 为内存索引表，用于表示内存实例在 Store 中的内存地址；globaladdrs 为全局变量索引表，用于表示全局变量实例在 Store 中的内存地址；exports 为导出对象索引表，用于表示导出实例在 Store 中的内存地址。typeAddr={index:number,size:number,};interfaceExternalVal{type:string;addr:Addr;}typeExportInstance={name:string,value:ExternalVal,};typeModuleInstance={funcaddrs:Array,tableaddrs:Array,memaddrs:Array,globaladdrs:Array,exports:Array,};基于模块实例和索引空间的数据结构，WAInterp 定义 createInstance 函数来完成对象实例化以及索引空间的初始化；其中，funcTable 为模块中定义的函数对象，包括函数名，函数体指令序列；store 为模块运行时的实例空间，用于实际存储模块全局对象实例；module 为解码后模块的内存数据结构表示；externalElements 为实例化过程中指定的外部导入对象实例，当前只支持了函数实例的导入，如下代码所示。typeIRFunc={name:string,startAt:number,instructions:Array;};exportfunctioncreateInstance(funcTable:Array,store:Store,module:Module,externalElements:any={}):ModuleInstance{constmoduleInstance:ModuleInstance={...};//skipnon-cricitalcode...instantiateImports(module,store,externalElements,...,moduleInstance);instantiateInternals(funcTable,module,store,...,moduleInstance);instantiateDataSections(module,store,moduleInstance);instantiateExports(module,store,...,moduleInstance);returnmoduleInstance;}根据不同的对象类型，WAInterp 定义了不同的实例化过程，接下来，我们分别进行详细的阐述。导入对象实例化一个模块可以导入函数、表、内存、全局变量这四种类型的外部符号，这些外部导入的符号需要在模块实例化过程中完成符号解析和和链接过程，如下图 3 所示；模块链接原理和过程请阅读课程的如下两篇文章 WebAssembly 模块化与动态链接和 WebAssembly工作原理浅析，文中对动态链接的的设计、原理和实现有详细的介绍和示例。图 3. 实例化导入成员链接示意图基于链接过程和导入对象数据结构定义，WAInterp 定义 instantiateImports 函数来完成实例化导入对象和链接过程；其中，module 为解码后模块的内存数据结构表示；store 为模块运行时的实例空间，用于实际存储模块导入对象实例；externalElements 为导入符号所在的外部模块实例对象。instantiateImports 函数通过 traverse 函数遍历查找模块中 ModuleImport 类型的对象，并针对不同的导入类型采用不同的处理函数进行处理，如下代码所示。functioninstantiateImports(module:Module,store:Store,externalElements:Object,moduleInstance:ModuleInstance):void{functiongetExternalElementOrThrow(key:string,key2:string):any{//skipnon-cricitalcode...returnexternalElements[key][key2];}//skipnon-cricitalcode...traverse(module,{ModuleImport({node}:NodePath){constnode_desc_type=node.descr.type;switch(node.descr.type){case"FuncImportDescr":returnhandleFuncImport(node,node.descr);case"GlobalType":returnhandleGlobalImport(node,node.descr);case"Memory":returnhandleMemoryImport(node);case"Table":returnhandleTableImport(node);default:thrownewError("Unsupportedimportoftype:"+node_desc_type);}},});}instantiateImports 函数为了处理不同的导入类型定义了不同的处理函数；其中，handleFuncImport 函数用于在 Store 中创建导入的函数对象，并在模块实例的函数索引空间 funcaddrs 中保存函数对象在 Store 中的地址，如下代码所示。functionhandleFuncImport(node:ModuleImport,descr:FuncImportDescr){constelement=getExternalElementOrThrow(node.module,node.name);constparams=descr.signature.params!=nulldescr.signature.params:[];constresults=descr.signature.results!=nulldescr.signature.results:[];constfunc_params:Array=[];params.forEach((p:FuncParam)=>func_params.push(p.valtype));constexternFuncinstance:FuncInstance=createFuncInstance(element,func_params,results);constexternFuncinstanceAddr:Addr=store.malloc(1);store.set(externFuncinstanceAddr,externFuncinstance);moduleInstance.funcaddrs.push(externFuncinstanceAddr);}exportfunctioncreateFuncInstance(func:Function,params:Array,results:Array):FuncInstance{consttype:Functype=[params,results];return{type,code:func,module:undefined,isExternal:true,};}handleGlobalImport 函数用于在 Store 中创建导入的全局变量对象，并在模块实例的全局变量索引空间 globaladdrs 中保存全局变量对象在 Store 中的地址；其中 i32 是 NumericOperations 子类型，用于封装 32 位整数及其操作函数，如下代码所示。interfaceNumericOperations{add(operand:T):T;sub(operand:T):T;mul(operand:T):T;div(operand:T):T;//skipnon-cricitalcode...}functionhandleGlobalImport(node:ModuleImport,descr:GlobalType){constelement=getExternalElementOrThrow(node.module,node.name);constexternglobalinstance:GlobalInstance=createGlobalInstance(newi32(element),descr.valtype,descr.mutability);constaddr=store.malloc(1);store.set(addr,externglobalinstance);moduleInstance.globaladdrs.push(addr);}exportfunctioncreateGlobalInstance(value:NumericOperations,type:Valtype,mutability:Mutability):GlobalInstance{return{type,mutability,value,};}与其他导入类型处理函数相似，handleMemoryImport 和 handleTableImport 分别在 Store 中创建各自的实例对象，并在模块实例的对应的索引空间中保存对象在 Store 中的地址，如下代码所示。functionhandleMemoryImport(node:ModuleImport){constmemoryinstance=getExternalElementOrThrow(node.module,node.name);constaddr=store.malloc(1);store.set(addr,memoryinstance);moduleInstance.memaddrs.push(addr);}functionhandleTableImport(node:ModuleImport){consttableinstance=getExternalElementOrThrow(node.module,node.name);constaddr=store.malloc(1);store.set(addr,tableinstance);moduleInstance.tableaddrs.push(addr);}模块内部对象实例化除了导入对象，模块会各自定义内部函数、表、内存、全局变量。在完成导入对象初始化后，我们需要为模块中自定义的各类对象实例化，并初始化对应类型的索引空间；与导入类型对象相似，内部对象实例化主要在 Store 中创建各自的实例对象，并在模块实例的对应的索引空间中保存对象在 Store 中的地址，如下代码所示。functioninstantiateInternals(funcTable:Array,n:Module,store:Store,internals:Object,moduleInstance:ModuleInstance){letfuncIndex=0;traverse(n,{Func({node}:NodePath){//skipnon-cricitalcode...constatOffset=funcTable[funcIndex].startAt;constfuncinstance:FuncInstance=func.createInstance(atOffset,node,moduleInstance);constaddr=store.malloc(1);store.set(addr,funcinstance);moduleInstance.funcaddrs.push(addr);funcIndex++;},Table({node}:NodePath){//skipnon-cricitalcode...constinitial=node.limits.min;constelement=node.elementType;consttableinstance:TableInstance=newTableInstance({initial,element});constaddr=store.malloc(1);store.set(addr,tableinstance);moduleInstance.tableaddrs.push(addr);},Memory({node}:NodePath){//skipnon-cricitalcode...const{min,max}=node.limits;constmemoryDescriptor:MemoryDescriptor={initial:min,};if(typeofmax==="number"){memoryDescriptor.maximum=max;}constmemoryinstance=newMemory(memoryDescriptor);constaddr=store.malloc(1);store.set(addr,memoryinstance);moduleInstance.memaddrs.push(addr);},Global({node}:NodePath){constglobalinstance=global.createInstance(store,node);constaddr=store.malloc(1);store.set(addr,globalinstance);moduleInstance.globaladdrs.push(addr);},});}内存和表初始化WebAssembly 模块中的元素段和数据段用于初始化对应的内存和表内容。当完成模块对象实例化后，内存实例和表实例仍处于未初始化状态；WAInterp 定义 instantiateElemSections 和 instantiateDataSections 函数分别初始化表和线性内存空间；instantiateElemSections 遍历元素段中的所有元素项，并将对应的元素填入 Table 中以完成表的初始化过程；和表的初始化类似，instantiateDataSections 根据数据段把初始数据写入指定的内存地址即可，代码如下所示。functioninstantiateElemSections(n:Module,store:Store,moduleInstance:ModuleInstance){traverse(n,{Elem({node}:NodePath){//skipnon-cricitalcode...constaddr=moduleInstance.tableaddrs[node.table.value];lettable=store.get(addr);constfuncs:Array=node.funcs;letoffset:number=evalExpression();//evalinitexpressionfuncs.forEach((func)=>{//writeelementintotabletable[offset]=moduleInstance.funcaddrs[func.value];});},});}functioninstantiateDataSections(n:Module,store:Store,moduleInstance:ModuleInstance){traverse(n,{Data({node}:NodePath){constmemIndex=node.memoryIndex.value;constmemoryAddr=moduleInstance.memaddrs[memIndex];constmemory=store.get(memoryAddr);constbuffer=newUint8Array(memory.buffer);letoffset=evalExpress(node);//evalinitexpressionfor(leti=0;i){switch(node.descr.exportType){case"Func":{createModuleExport(node,...,moduleInstance.funcaddrs,...);break;}case"Global":{createModuleExport(node,...,moduleInstance.globaladdrs,...);break;}case"Table":{createModuleExport(node,...,moduleInstance.tableaddrs,...);break;}case"Memory":{createModuleExport(node,...,moduleInstance.memaddrs,...);break;}default:{thrownewCompileError("unknownexport:"+node.descr.exportType);}}}});}createModuleExport 函数主要负责创建和初始化 ExportInstance 实例；其主要逻辑是利用 ModuleExport 结构保留的导出符号名和对应类型的索引空间中的已实例化对象创建 ExportInstance 实例，并保存至模块实例 moduleInstance 的 exports 对象中提供给外部模块使用，代码如下所示。typeExportInstance={name:string,value:ExternalVal,};functioncreateModuleExport(node:ModuleExport,instancesArray:Array,):void{//skipnon-cricitalcode...constinstantiatedItem={instanceArray[node.descr.id.value]};moduleInstance.exports.push({name:node.name,value:{type:node.descr.exportType,addr:instantiatedItem.addr,},});//skipnon-cricitalcode...}至此，模块实例化及索引空间创建和初始化均已完成，WAInterp 实例化的最后步骤是调用起始函数，执行用户自定义的初始化逻辑。4.3 模块起始函数执行模块的起始函数是一个可选的模块入口函数，类似于高级编程语言中的 "main" 函数，由 Start 中的 index 属性指定；执行该函数可以完成模块自定义数据的初始化。WAInterp 定义 executeStartFunc 用于执行起始函数，其中，IR 为实例化代码在内存中的表示，offset 为起始函数指令在代码段 program 中的偏移量。typeStart={type:"Start";index:Index;};typeIR={/***name:functionname*startAtffsetinprogram*/funcTable:Array,/*.textsegment(codesegment)*/program:{[offset:number]:Instruction,},};executeStartFunc(ir:IR,offset:number){conststackFrame=createStackFrame(params,this._moduleInstance,this._store);//IgnoretheresultexecuteStackFrameAndGetResult(ir,offset,stackFrame,true/*returnStackLocal*/);}如上代码所示，实际的 WebAssembly 函数执行首先由 createStackFrame 创建栈帧，然后调用 executeStackFrameAndGetResult 执行具体的字节码并返回执行结果。由于起始函数的执行和普通函数执行并没有差别，因此，本文将不单独介绍其执行流程，而统一在下一节 WAInterp 解释执行中进行说明。5. WAInterp 解释执行经过了解码和实例化阶段，WebAssembly 二进制模块已经转换为内存索引空间中的函数、Table、内存(堆)和全局变量实例以及相关辅助信息。函数实例中是一个指令序列，WAInterp 执行流程的主要工作是获取函数的指令序列，并逐一执行指令流中的指令完成每个指令对应的操作。当虚拟机执行的时候，虚拟机维护操作数栈 (Operand stack) 和控制帧栈 (Control stack)，分别存储参数、局部变量、操作数 (values) 和控制结构 (labels)。虚拟机中每个函数调用都会产生一个函数调用帧 (Frame)，用于存储函数的参数、局部变量。WebAssembly 解释器指令执行全景如下图 4 所示，关于 WebAssembly 执行原理请参阅课程的 "WebAssembly 工作原理浅析" 一文。图 4. WebAssembly 解释器指令执行示意图和大多数解释型语言类似，WebAssembly 定义自己的一套指令集，按功能可以分为五类，他们分别是控制指令、参数指令、变量指令、内存指令和数值指令。接下来内容，我们将基于 "Switch-Dispatch" 指令分发模式，详细介绍 WebAssembly 指令在 WAInterp 解释器中的实现 (解释器的常见实现方式及结构请阅读参考文献[3])，WAInterp 解释执行代码结构如下所示；其中，program 模块中所有函数代码组成的代码段；offset 为函数的指令序列在代码段中的起始偏移；StackFrame 为函数调用栈帧，其中与函数执行相关的内容将在函数调用小节进行详细介绍。exportfunctionexecuteStackFrame({program}:IR,offset:number,firstFrame:StackFrame):StackLocal{constcallStack:Array=[firstFrame];letpc=program[String(offset)]//skipnon-criticalcode...while(true){constframe=getActiveStackFrame();constinstruction:Instruction=program[parseInt(offsets[pc])];//skipnon-criticalcode...pc++;switch(instruction.id){//Parametricoperatorscase"drop":{...}case"select":{...}//Variableaccesscase"get_local":{...}case"set_local":{...}case"get_global":{...}case"set_global":{...}...//memory-relatedoperatorscase"store":{...}...case"load":{...}...//Numericoperatorscase"add":{...}case"mul":{...}case"sub":{...}...//Comparisonoperationscase"eq":case"ne":...//ControlInstructionscase"call":{...}case"loop":{...}case"block":{...}case"br":{...}case"br_if":{...}//AdministrativeInstructionscase"unreachable":{...}case"trap":{...}case"return":{...}}}WAInterp 在 "Switch-Dispatch" 执行模式中展示了解释器的整体框架和常用指令集，接下面我们将分别介绍各类常用指令的语义及执行逻辑。5.1 参数指令(Parametric Instructions)参数指令包括 drop 和 select，其中 drop 指令从栈顶弹出一个操作数并把它 "丢弃"；而 select 指令类似于 " :" 三目运算符， 它从栈顶弹出 3 个操作数，然后根据最先弹出的操作数从其他两个操作数中选择一个压栈；下图 5 展示了参数指令的执行逻辑示例。图 5. 参数指令执行示例5.2 变量指令(Variable Instructions)变量指令包括局部变量指令和全局变量指令，其中局部变量指令用于读写函数的参数和局部变量，全局变量指令用于读写模块实例的全局变量；变量指令格式如下所示。local.get:0x20|local_idxlocal.set:0x21|local_idxlocal.tee:0x22|local_idxglobal.get:0x23|global_idxglobal.set:0x24|global_idx下面我们介绍这两种变量指令的逻辑及其实现。局部变量指令local.get 指令用于获取局部变量的值，也就是把局部变量的值压栈；该指令带有一个立即数，给出局部变量索引；和 local.get 指令相反，local.set 指令用于设置局部变量的值；局部变量的索引由立即数指定，新的值从栈 顶弹出；local.tee 指令与 local.set 指令类似，唯一吧不同是在用栈顶操作数设置局部变量后，仍然在栈顶保留了原来操作数的值；下图 6 展示了局部变量指令的执行逻辑示例。图 6. 局部变量指令执行示例全局变量指令全局变量指令与局部变量指令很类似，只不过操作对象是全局变量。global.get 指令把全局变量的值压栈，全局变量的索引由立即数指定；而 global.set 指令设置全局变量的值，全局变量的索引由立即数指定，新的值从栈顶弹出；下图 7 展示了全局变量指令的执行逻辑示例。图 7. 全局变量指令执行示例5.3 内存指令(Memory Instructions)内存指令按操作类型分为三类，他们分别是加载指令、存储指令、内存 size 和 grow 指令；其中，加载指令从内存中读取数据，压入操作数栈；存储指令从栈顶弹出数值，写入内存；内存 size 和 grow 指令只获取或者增 长内存页数；内存指令格式如下所示。load_instrpcode|align|offset#align:u32,offset:u32store_instrpcode|align|offsetmemory.size:0x3f|0x00memory.grow:0x40|0x00下面我们分别介绍这三种内存指令的逻辑及其实现。加载指令加载指令编码格式中带有对齐方式和内存偏移量两个立即数，加载指令首先从操作数栈上弹出一个 i32 类型的数，把它和偏移量立即数相加得到实际线性内存地址，此时，加载指令便从线性内存地址加载数据并转换为类型 "T" 的值压入操作数栈；其中类型 "T" 可以为 i32，i64，f32，f64；下图 8 展示了加载指令的执行逻辑示例。图 8. 内存加载指令执行示例存储指令和加载指令类似，存储指令也带有对齐方式和内存偏移量两个立即数，存储指令首先从操作数栈上弹出需要写入内存的操作数值和一个 i32 类型的内存基址，然后，把内存基址和偏移量立即数相加得到实际线性内存地址，此时，存储指令便可以将需要保持的操作数转换为类型 "T" 的值保存至内存地址处；其中类型 "T" 可以为 i32，i64，f32，f64；下图 9 展示了存储指令的执行逻辑示例。图 9. 内存存储指令执行示例内存 size 和 grow 指令memory.size 指令把内存的当前页数以 i32 类型压栈，指令立即数用来指代操作的内存；WebAssembly MVP 规范规定最多只能导入或者定义一块内存，立即数必须为0。memory.grow 指令用于扩展内存若干页，并获取原始内存页(增长前的页数)。执行时，该指令需要从栈顶弹出一个 i32 类型的数，代表要增长的页数；如果增长成功，指令把增长之前的页数以 i32 类型压栈；否则，把 -1 压栈；memory.grow 指令也带有一个单字节立即数，当前必须为 0。内存 size 和 grow 指令执行逻辑示例如下图 10 所示。图 10. 内存 size 和 grow 指令执行示例5.4 数值指令(Numeric Instructions)数值指令是 WebAssembly 指令集中数量最多的一类。按照操作类型，数值指令又可以分为常量指令、测试指令、比较指令、算术指令和类型转换指令。下面我们分别介绍各类数值指令的逻辑实现。常量指令常量指令将指令中的立即数常量作为指定类型的操作数压入操作数栈；其中类型 "T" 可以为 i32，i64，f32，f64 四种；常量指令执行逻辑示例如下图 11 所示。图 11. 常量指令执行示例测试指令测试指令从栈顶弹出一个操作数，先“测试”它是否为 0，然后把 i32 类型的布尔值测试结果压栈；测试指令类型 "T" 只针对整数类型 i32 和 i64；测试指令执行逻辑示例如下图 12 所示。图 12. 常量指令执行示例比较指令比较指令从栈顶弹出 2 个同类型的操作数进行比较，然后把 i32 类型的布尔值比较结果压栈；比较指令数量比较多，除了操作数类型和比较方式外，所有比较指令的逻辑都是相似的。以 i64.It_s 指令为例的比较指令示意图，其中类型 "T" 可以为 i32，i64，f32，f64 四种；比较指令执行逻辑示例如下图 13 所示。图 13. 比较指令执行示例WAInterp 定义 compare 函数用于统一实现比较和测试指令逻辑，如下代码所示。typeOperation=|"eq"|"ne"|"lt_s"|"lt_u"|"le_s"|"le_u"|"gt"|"gt_s"|"gt_u"|"ge_s"|"ge_u";exportfunctioncompare({value:value1}:StackLocal,{value:value2}:StackLocal,op:Operation):StackLocal{switch(op){case"eq":returni32.createValue(value1.eq(value2));case"ne":returni32.createValue(value1.ne(value2));case"lt_s":returni32.createValue(value1.lt_s(value2));case"le_s":returni32.createValue(value1.le_s(value2));case"gt":returni32.createValue(value1.gt(value2));case...}thrownewError("Unsupportedbinop:"+op);}算数指令算数指令根据操作数的数量可以进一步分为一元算术指令和二元算术指令。一元算术指令从栈顶弹出一个操作数进行计算，然后将同类型的结果压栈，除了操作数的类型和指令功能外，所有的一元算术指令的逻辑都是相似的；二元算术指令从栈顶弹出2个相同类型的操作数进行计算，然后将同类型结果压栈，与一元算数指令类似，抛开操作数的类型和计算，二元算术指令的逻辑也都是相似的。其中类型 "T" 可以为 i32，i64，f32，f64 四种；算数指令执行逻辑示例如下图 14 所示。图 14. 算数指令执行示例WAInterp 定义 unop 和 binop 函数分别用于实现一元和二元算术指令，如下代码所示。typeOperation="abs"|"neg"|"clz"|"ctz"|"popcnt"|"eqz"functionunop({value:value}:StackLocal,operation:Operation,createValuearg:any)=>StackLocal):StackLocal{switch(operation){case"abs":returncreateValue(value.abs());case"neg":returncreateValue(value.neg());case"clz":returncreateValue(value.clz());case"ctz":returncreateValue(value.ctz());case"popcnt":returncreateValue(value.popcnt());case"eqz":returni32.createValue(value.eqz());case...}thrownewError("Unsupportedunop:"+operation);}typeSign="add"|"sub"|"div"|"div_s"|"div_u"|"mul"|"and"|"or"|"xor"|"~"|"min"|"max"|"copysign"|"rem_s"|"rem_u"|"shl"|"shr_s"|"shr_u"|"rotl"|"rotr";functionbinop({value:value1}:StackLocal,{value:value2}:StackLocal,sign:Sign,createValuearg:any)=>StackLocal):StackLocal{switch(sign){case"add":returncreateValue(value1.add(value2));case"sub":returncreateValue(value1.sub(value2));case"mul":returncreateValue(value1.mul(value2));case"shl":returncreateValue(value1.shl(value2));case"shr_s":returncreateValue(value1.shr_s(value2));case"div":returncreateValue(value1.div(value2));case"and":returncreateValue(value1.and(value2));case"or":returncreateValue(value1.or(value2));case...}thrownewError("Unsupportedbinop:"+sign);}类型转换类型转换指令从栈顶弹出一个操作数进行类型转换，然后把结果压栈。按照转换方式，类型转换指令可以分为整数截断 (wrap)、整数扩展 (extend)、浮点数截断 (trunc)、整数转换 (convert)、浮点数精度调整 (demote、promote) 以及比特位重新解释 (reinterpret)。除了操作数类型和转换逻辑，所有的类型转换指令的逻辑也都是相似的，以 i32.wrap_i64 指令为例，其执行逻辑示例如下图 15 所示。图 15. i32.wrap_i64 类型转换指令执行示例至此，我们已经介绍了常用的数值指令及核心执行逻辑，完整指令列表及详细信息请参见 WebAssembly 指令列表[10]，不在此一一讨论和介绍。接下来，我们介绍最后一类和控制流相关的控制指令。5.5 控制指令(Control Instructions)控制指令是程序控制流管理的关键指令，主要包括结构化控制指令、跳转指令、函数调用指令、伪指令等类型。下面我将分别介绍各控制指令的逻辑功能及实现。伪指令伪指令是控制指令中最简单的一类，其中，unreachable 指令引发一个运行时错误；nop(No Operation 的缩写) 指令表示空操作，什么都不做；实现代码如下所示。exportfunctionexecuteStackFrame({program}:IR,offset:number,firstFrame:StackFrame):StackLocal{//skipnon-cricitalcode...while(true){//skipnon-cricitalcode...pc++;switch(instruction.id){case"nop":{break;}//donothingcase"unreachable":case"trap":{thrownewRuntimeError();}case...:}}结构化控制指令程序中最基本的控制结构有顺序结构、分支结构、循环结构三种，组合使用这三种控制结构就可以构造出其他控制结构和复杂的程序。WebAssembly 提供了 block、loop、if 三条控制指令来生成对应的控制结构，由于控制指令有良好的结构化特征，因此被称为结构化控制指令；控制指令格式如下所示。block_instr:0x02|block_type|instr*|0x0bloop_instr:0x03|block_type|instr*|0x0bif_instr:0x04|block_type|instr*|(0x05|instr*)|0x0bblock_type:s32从指令的语义上来看，除了跳转目标不同，block 指令和 loop 指令的结构和执行逻辑是基本一致的。针对结构化控制指令的编码规范，WAInterp 定义如下的数据结构来表示，如下代码所示。typeBlockInstruction={type:"BlockInstruction";id:string;label:Identifier;instr:Array;result:Valtype;};typeLoopInstruction=BlockInstruction&{type:"LoopInstruction";};结构化控制指令在语义上与函数调用类似，指令的块类型相当于函数的签名，内部指令相当于函数的字节码序列。当进入结构化控制指令时，操作数栈顶指定数目和类型的值作为控制指令参数；当指令结束时，栈顶生成指定数目和类型的执行结果。以如下的 block 和 loop 示例程序为例，对应的执行逻辑如图 16 所示。(module(func$add(param$ai64)(param$bi64)(resulti64)(local.get$a)(local.get$b)(block(parami64i64)(resulti64)(i64.add))))图 16. block/loop 指令执行示例block 和 loop 指令主要维护控制栈并为跳转指令提供目标地址；因此，WAInterp 解释器对于 block 和 loop 的处理就比较简单，执行指令时，在栈帧的标签栈 frame.labels 中创建标签 label 对象；实际的跳转逻辑将在后续的详细介绍，不在此赘述。typeLabel={arity:number,value:any,id:Identifier,};exportfunctionexecuteStackFrame({program}:IR,offset:number,frame:StackFrame):StackLocal{//skipirrelevantcode...while(true){//skipirrelevantcode...switch(instruction.id){case"loop":case"block":{frame.labels.push({//controlstackvalue:instruction,arity:0,id:instruction.label,});pushResult(frame,label.createValue(instruction.label.value));break;}}}相比 block 和 loop 指令，if 指令相对复杂一些，其内部的指令序列被 "else" 指令一分为二；针对结构化控制指令的编码规范，WAInterp 定义如下的数据结构来表示，如下代码所示。typeIfInstruction={type:"IfInstruction";id:string;test:Array;result:Valtype;consequent:Array;alternate:Array;};if 指令携带 consequent 和 alternate 两个相同类型的指令序列，其中 alternate 是可选的；当指令执行时，会先从操作数栈顶弹出一个 i32 类型布尔值，如果该值为真就执行 consequent 指令序列，否则执行 alternate，这样就起到了分支的效果。以如下的示例程序为例，if 指令对应的执行逻辑如图 17 所示。(module(func$calc(param$opi32)(param$ai64)(param$bi64)(resulti64)(local.get$a)(local.get$b)(if(parami64i64)(resulti64)(i32.eqz(local.get$op))(then(i64.add))(else(i64.sub)))))图 17. if 指令执行示例由于 if 指令实际上是定义了两个 block 块，我们在函数实例化阶段已经对 if 指令进行的预处理，将其转换为独立的 block IR 同时添加跳转指令以维护 if 指令的执行语义；因此，WAInterp 不需要对 if 指令进行单独处理，而直接复用 block 指令的执行逻辑。跳转指令为了形成完整的控制流，WebAssembly 定义了 4 条跳转指令，它们分别是无条件跳转指令 br，条件跳转指令 br_if，查表跳转指令 br_table，函数返回指令 return。下面我们分别介绍各跳转指令的执行逻辑和实现。br 指令进行无条件跳转，该指令带有一个立即数指定跳转的目标标签索引。从语义上看，不同的控制块类型 br 指令表现不同的行为。由于 block 指令控制块的标签在尾部，br 指令导致这个控制块提前结束；而 loop 指令控制块的标签在头部，br 指令导致这个控制块重新开始执行；br 指令执行语义如下图 18 所示。图 18. br 指令跳转语义WAInterp 在执行 br 指令时执行栈变化如下图 19 所示，其中 btr (block type result) 表示对应 block 的返回值，黑色三角形表示这个位置对应一个新的控制帧；br 指令执行前操作数栈的状态左侧所示，当函数准备执行 br 2 指令时，操作数栈上有 4 个整数对应每个 block 指令的返回值，对应的控制栈上也应该有 4 个控制帧。执行 br 2 指令时，控制栈顶的 3 个控制帧被弹出，与这 3 个控制帧对应的操作数栈也应该被清理。由于标签索引 2 指向的控制块有一个结果，所以应该先从栈顶弹出一个操作数，暂存起来。对栈进行清理之后，再把暂存的结果压栈。图 19. br 指令执行示例exportfunctionexecuteStackFrame({program}:IR,offset:number,frame:StackFrame):StackLocal{//skipnon-cricitalcode...while(true){//skipnon-cricitalcode...switch(instruction.id){//skipnon-cricitalcode...case"br":{constlabel=instruction.args[0];letresult:Valtype=frame.values[frame.values.length-1];while(label.id!=frame.labels[frame.labels.length-1].id){frame.labels.pop()if(frame.labels[frame.labels.length-1].arity!=0){frame.values.pop();}}if(label.arity!=0){frame.values.push(result)}GOTO(label.value);break;}}}在实现了 br 指令后，其他跳转指令就非常容易理解和实现了；其中 br_if 指令进行条件跳转，当执行 br_if 指令执行时，先从操作数栈顶弹出一个 i32 类型布尔值 c；如果该值为真，则接着执行和 br 指令完全一样的逻辑；否则，只相当于执行一次 drop 操作；br_if 指令的执行栈变化如下图 20 所示：图 20. br_if 指令执行示例br_table 指令进行无条件查表跳转；与 br 和 br_if 指令不同，br_table 指令可以指定多个跳转目标，最终使用哪个跳转目标要到运行期间才能决定；br_table 指令的立即数给定了 n + 1 个跳转标签索引；其中前 n 个标签索引构成了一个索引表，后一个标签索引是默认索引；当 br_table 指令执行时，要先从操作数栈顶弹出一个 i32 类型的值m；如果 m 小于等于 n，则跳转到索引表第 m 个索引指向的标签处；否则，跳转到默认索引指定的标签处，br_table 指令执行示例如下图 21 所示。图 21. br_table 指令执行示例函数体本身也是一个隐式的控制块，结构化控制指令 return 直接跳出最外层的块，并根据函数返回值清理操作数栈和函数调用栈，return 指令最终效果就是导致函数返回，代码如下所示。exportfunctionexecuteStackFrame({program}:IR,offset:number,frame:StackFrame):StackLocal{//skipirrelevantcode...while(true){//skipirrelevantcode...switch(instruction.id){//skipirrelevantcode...case"return":{if(frame.returnAddress!==-1){pc=frame.returnAddress;//rawgotoPOP_STACK_FRAME();}returnRETURN();}}}函数调用指令函数是 WebAssembly 的基本执行单位，为了执行函数，WebAssembly 定义了直接函数调用 call 指令和间接函数调用 call_indirect 指令；除了函数索引的确定时机不同，直接函数调用和间接函数调用执行逻辑是一致的；其中，call 指令的立即数指定的函数索引；call_indirect指令需要运行时的操作数栈提供函数表中的索引值实现动态函数调用。函数调用是一类特殊的结构化控制指令，为了记录函数执行过程中的状态和数据，WAInterp 为每个函数调用创建函数栈帧 StackFrame。typeStackFrame={values:Array,//operandsstackofcurrentstackframelocals:Array,//localvariableofcurrentstackframelabels:Array,//LabelsarenamedblockofcurrentstackframereturnAddress:number,//calleraddressmodule:ModuleInstance,//referencetoitsoriginatingmodule.store:Store,//sharedmemorystorage};typeStackLocal={type:Valtype,value:any,};如上代码所述，每个栈帧包括如下关键内容。模块实例 module: 包含栈帧关联的函数的所有信息，包括模块索引空间，函数类型，函数指令序列等。操作数栈 values: 用于存储参数、局部变量、以及函数体指令执行过程中的操作数；为了简化实现，每个栈帧维护自己专有的操作数栈。控制栈 labels: 前面小节中，我们已经详细介绍了 WebAssembly 的控制结构和控制指令；由于 WebAssembly 不支持任意跳转指令，只支持受限的结构化跳转，其核心的设计是通过block, loop, if结构化控制指令将函数分割为一系列嵌套的代码块，每个代码块拥有一个标签 label，跳转指令按照约定在跳转到嵌套代码块的外层标签处，如下图 22 所示。这种结构和逻辑类似于函数调用栈，因此，我们可以通过定义控制栈和控制帧来实现结构化控制指令和跳转指令，其中 CSP 与 SP 类似，表示 Control Stack Pointer，如下图 22 所示。图 22. WebAssembly 控制帧栈和控制结构图函数返回地址 returnAddress: 用于存储该栈帧调用指令的下一条指令的地址，当该栈帧从调用栈弹出时，会返回到该栈帧调用指令的下一条指令继续执行；换句话说，就是当前栈帧对应的函数执行完退出后，返回到调用该函数的地方继续执行后面的指令，即 returnAddress 所指定的指令处开始执行。函数调用帧 CallFrame 需要记录函数被调用过程中的运行时信息，虚拟机执行过程中，每调用一个函数就会创建上述定义的栈帧，当函数执行结束后再把调用帧销毁；而函数的嵌套调用就形成了栈式结构 - 函数调用栈 (Call Stack)，如下图 23 所示。图 23. WebAssembly 函数调用栈示意图至此，我们已经分析和定义了函数调用帧和函数调用栈所必须的基础结构，接下来就让我们来实现函数调用指令。Call 指令执行时，首先从指令立即数获取被调用函数的索引，并根据被调用函数的类型从栈顶弹出参数，指令执行结束后，被调用函数的返回值会出现在栈顶，如下图 24 所示，其中函数参数类型为 U，V，返回值类型为 T。图 24. call 指令执行示例图基于 call 指令语义和栈相关数据结构，WAInterp 定义 executeStackFrame 用于实际执行目标函数的指令序列，如下代码片段所示。exportfunctionexecuteStackFrame({program}:IR,offset:number,frame:StackFrame):StackLocal{//skipirrelevantcode...while(true){constcallStack:Array=[firstFrame];constoffsets=Object.keys(program);letpc=offsets.indexOf(String(offset));letframepointer:number=0;//skipirrelevantcode...switch(instruction.id){case"call":{PUSH_NEW_STACK_FRAME(pc);constindex=instruction.index.value;//calleefuncindexGOTO(index);break;}//skipirrelevantcode...case"return":{if(frame.returnAddress!==-1){POP_STACK_FRAME();pc=frame.returnAddress;//rawgotobreak;}else{returnRETURN();}}}}如上述代码所示，函数调用主要分为执行 call 指令和函数返回 return 两个过程。call 指令执行时，首先通过函数 PUSH_NEW_STACK_FRAME 为被调用函数创建栈帧并压入调用栈 callStack，然后从 call 指令立即数获取目标函数索引并跳转至目标指令处执行；当函数返回时会即执行 return 指令，首先调用 POP_STACK_FRAME 函数销毁栈帧并将返回值压入返回函数的操作数栈中，最后从当前栈获取返回地址并跳转到目标地址执行；函数调用和返回过程中的栈帧管理函数如下代码所示。functionPUSH_NEW_STACK_FRAME(pc:number):void{constactiveFrame=getActiveStackFrame();constnewStackFrame=createChildStackFrame(activeFrame,pc);framepointer++;//moveactiveframecallStack[framepointer]=newStackFrame;//Pushtheframeontopofthestack}functionPOP_STACK_FRAME():void{constactiveFrame=getActiveStackFrame();letres;//passtheresultofthepreviouscallintothenewactivefameif(activeFrame.values.length>0){res=pop1(activeFrame);callStack.pop();//Popactiveframefromthestackframepointer--;constnewStackFrame=getActiveStackFrame();if(res!==undefined&newStackFrame!==undefined){pushResult(newStackFrame,res);}}}对于 call_indirect 指令而言，编译期只能确定被调用函数的类型并保存在 call_indirect 指令的立即数里，具体调用哪个函数只有在运行期间根据栈顶操作数才能确定；call_indirect 指令首先从指令立即数获取被调用函数所保存的表索引和函数类型，然后指令从栈顶弹出一个 i32 类型的操作数，该操作数指定了需要执行的函数在表中的索引值；如果表中的函数对应的函数类型与指令立即数指定的函数类型不匹配，那么执行非法，否则，call_indirect 可以根据索引查表找到函数引用，完成调用函数；call_indirect 指令执行示例如下图 25 所示。由于 call 指令和 call_indirect 除了函数索引确定的时机之外，执行逻辑基本是一致的，因此，call_indirect 指令实现与 call 指令基本类似，不再此赘述。图 25. call_indirect 指令执行示例图6. WAInterp 运行实例在以上各小节，我们详细阐述了 WAInterp 解析器的工作原理及基于 Typescript 的实现，本节我们利用上述过程中实现的 WAInterp 来运行实际的示例程序，来验证解释器的正确性。示例程序的源代码如下所示，其中 printstr 为外部导入函数用于打印字符串，hello 函数接收一个整数参数，根据不同的参数会打印不同的字符串， 而 hello 函数会进一步通过调用 iadd 函数获取结果并返回。//hello-world.cWASM_IMPORT("env","printstr")intprintstr(char*);WASM_EXPORT("iadd")intiadd(inta,intb){returna+b;}WASM_EXPORT("main")inthello(intoption){if(option==1){printstr("helloworld!");}else{printstr("seeyouagain!");}returniadd(option,100);}以上源代码生成的 WebAssembly 文本格式如下所示(module(type(;0;)(func(parami32)))(type(;1;)(func))(type(;2;)(func(parami32)(resulti32)))(type(;3;)(func(parami32i32)(resulti32)))(import"env""printstr"(func$printstr(type2)))(func$iadd(type3)(parami32i32)(resulti32)local.get0local.get1i32.add)(func$hello(type2)(parami32)(resulti32)(locali32)i32.const1local.set1block;;label=@1block;;label=@2local.get0local.get1i32.eqbr_if0(;@2;)i32.const1037local.set1local.get1call$printstrbr1(;@1;)dropendi32.const1024local.set1local.get1call$printstrdropendlocal.get0i32.const100call$iaddreturn)(memory(;0;)1)(global$__stack_pointer(muti32)(i32.const2064))(export"memory"(memory0))(export"main"(func$hello))(export"iadd"(func$iadd))(export"stack_pointer"(global$__stack_pointer))(data$.rodata(i32.const1024)"helloworld!\00seeyouagain!\00"))基于 WAInterp 解释器，我们实现了执行 WebAssembly 二进制文件的命令行工具 wasmrun.ts；通过如下命令行，可以在运行示例程序的过程中观察指令执行过程及执行结果，其中控制台输出为 [printstr] see you again!，返回结果为输入参数与 100 之和，如下所示。npxts-nodesrc/cli/bin/wasmrun.tstest/wasm/hello.wasmmain2Executing...->main(2):->Instr(local)->debug:newlocali32->Instr(const)->Instr(set_local)->BlockInstruction(block)->enteringblockblock_1->BlockInstruction(block)->enteringblockblock_0->Instr(get_local)->Instr(get_local)->Instr(eq)->Instr(br_if)->Instr(const)->Instr(set_local)->Instr(get_local)->InternalCallExtern()[printstr]seeyouagain!->Instr(br)->Instr(end)->exitingblockblock_0->Instr(get_local)->Instr(const)->CallInstruction(call)->Instr(get_local)->Instr(get_local)->Instr(add)->InternalEndAndReturn()->Instr(return)exitedwithcode{type:'i32',value:i32{_value:102}}7. 总结至此，我们已经完整地实现了 WAInterp 虚拟机的最基础的能力，其中包括 WebAssembly 模块的加载和解码，模块的实例化以及指令执行；本文从零开始实现一个简单的 WebAssembly 解释器，通过这一过程不仅帮助我们进一步了解和掌握 WebAssembly 基本原理，还实实在在的构建一个可用的 WebAssembly 虚拟机。虽然我们只实现了 WebAssembly 规范的最小 MVP 子集，但 WAInterp 提供了一个 WebAssembly 虚拟机框架和运行时基座，可以基于此来进一步扩展和补充 WebAssembly 规范的功能和特性。由于篇幅有限，我们仅在文中展示了 WAInterp 的核心实现代码，完整实现可以通过源码仓库 WARuntime[12] 进行获取；此外，JavaScript 工程可以通过添加 @zhongxiao/waruntime[6] 依赖获取 WARuntime NPM 依赖包。基于 WARuntime，读者可以方便的按照指引快速重建和运行本文中所有的示例程序。8. 参考文献[1]. WebAssembly工作原理浅析[2]. Crafting Interpreters: https://craftinginterpreters.com/[3]. Dispatch Techniques: http://www.cs.toronto.edu/~matz/dissertation/matzDissertation-latex2html/node6.html[4]. Principles of Just-In-Time Compilers: https://nbp.github.io/slides/GlobalScope/2021-07/#intro,0[5]. 计算机程序的构造和解释: https://book.douban.com/subject/1148282/[6]. @zhongxiao/waruntime: https://www.npmjs.com/package/@zhongxiao/waruntime[7]. Binary Module: https://WebAssembly.github.io/spec/core/binary/modules.html[8]. Custom Sections: https://WebAssembly.github.io/spec/core/appendix/custom.html[9]. Index of Instructions: https://WebAssembly.github.io/spec/core/appendix/index-instructions.html[10]. WebAssembly Opcodes: https://pengowray.github.io/wasm-ops/[11]. Binary Encoding: https://github.com/WebAssembly/design/blob/main/BinaryEncoding.md[12]. WARuntime: https://github.com/yaozhongxiao/WebAssemblyToolkit点击上方关注 · 我们下期再见点击左下方“阅读原文”，或扫描上方二维码，进入专栏阅读《走进 WebAssembly 的世界》完整版。