-
摘要:
动态二进制翻译器中广泛使用软件代码缓存来管理翻译生成的代码块. 代码块的翻译、刷新和内存占用是软件代码缓存的一个重要指标. 目前仅有少量的针对系统级动态二进制翻译器中代码缓存的研究. 已有的系统级动态二进制翻译器为实现正确且高效的指令语义模拟，均使用了状态标签方案，但该方案会对软件代码缓存管理带来额外的问题. 通过深入分析状态标签方案，总结了其给代码缓存管理带来的2类问题：冲突和冗余. 针对这2类问题，提出了基于细粒度状态标签的代码缓存优化方法，包括多状态代码缓存和弱状态标签. 这2种方案在LATX-SYS中实现并在龙芯LoongArch平台上使用Ubuntu/x86 16.04和Windows XP/x86客户机操作系统进行了测试. 结果表明，代码块刷新次数和翻译次数分别降低了43%和18%，代码块相似率从59.63%降至5.06%，翻译开销和内存占用均得到降低. 总的来说，系统启动时间降低了20%. 最后，针对弱状态标签方案进一步测试了SPEC CPU2000，结果表明代码块数量平均减少了13%，且仅带来2%~3%的性能开销.
Abstract:Software Code Cache is widely used in dynamic binary translators to manage the dynamically generated code blocks. The translation, refresh, and memory occupancy of code blocks are key metrics for software code cache. There has been little research on software code cache for system-level dynamic binary translators. Existing system-level dynamic binary translators use state label scheme to achieve correct and efficient instruction semantic simulation, but this scheme introduces additional problems for software code cache management. Through in-depth analysis of the state label scheme, two types of problems are summarized: conflicts and redundancies. To address these two problems, two code cache optimization schemes based on fine-grained state label are proposed, including multi-state code cache scheme and weak state label scheme. These two schemes are implemented in LATX-SYS and evaluated with Ubuntu/x86 16.04 and Windows XP/x86 system booting on LoongArch platform. The evaluation results show that the code block refresh and translation are reduced by 43% and 18% respectively. The code block similarity ratio is decreased from 59.63% to 5.06%. The translation overhead and memory occupancy are both reduced. Overall, the system boot time was reduced by 20%. Finally, testing of the weak state label scheme on SPEC CPU2000 shows that the number of code blocks is reduced by an average of 13%, with only 2%-3% performance overhead introduced.
-
Keywords:
- software code cache /
- binary translation /
- virtualization /
- code block /
- dynamic optimization
-
动态二进制翻译技术可以实现程序的模拟执行. 被模拟执行的客户机程序通过动态二进制翻译器（dynamic binary translator，DBT）运行在宿主机之上. 当客户机和宿主机的指令集架构不同时，动态二进制翻译技术可以实现跨架构的程序模拟执行. 二进制翻译的基本原理是将客户机代码翻译成语义等价的宿主机代码，通常以代码块为单位进行翻译. 代码块由一段地址连续、顺序执行的代码组成，通常以控制转移指令为结尾. 一个客户机代码块通过二进制翻译生成一个语义等价的宿主机代码块，本文称之为翻译代码块. 软件代码缓存负责存储翻译代码块，以便后续重复利用，降低动态翻译开销.
根据程序模拟的层次，DBT可分为用户级和系统级2类，其代码缓存的实现相近，都是存储翻译代码块以便复用. 不同的是翻译时指令语义模拟的实现，如表1所示. 用户级DBT可以假设客户机永远处于用户态，只需支持用户态指令. 系统级DBT则需要考虑客户机的各种状态，需要支持所有指令. 为保证系统正确运行，客户机指令语义模拟需要正确的实现. 以1条特权指令为例，若客户机处于低特权级，则需要翻译生成触发客户机异常的操作，而不能直接生成该条特权指令的执行语义，否则不仅会运行出错，还可能造成安全问题.
表 1 指令语义模拟的因素Table 1. Factors in Instruction Semantics SimulationDBT 客户机状态 指令范围 用户级 单一 用户态 系统级 复杂 全部 系统级DBT中语义模拟方案有2种：一种是动态检测方案，该方案在翻译代码块中生成判断当前客户机状态的宿主机代码，从而在运行时进行检测；另一种是状态标签方案，该方案在翻译时仅依据当前客户机状态，并将生成的翻译代码块的状态标记为当前客户机状态. 在翻译代码块执行前需进行对比，确保待执行的翻译代码块的状态与客户机状态一致. 详细介绍请见本文第2节.
出于性能的考虑，目前的系统级DBT均采用了状态标签方案，避免运行时开销. 但状态标签方案也会给软件代码缓存引入额外的问题. 本文详细分析了状态标签方案，总结了2类问题：一类是冲突问题，源于不同状态的翻译代码块存储在同一个代码缓存空间，导致空间利用率的下降和不必要的刷新；一类是冗余问题，源于不同状态的翻译代码块可能包含相同的宿主机代码，意味着多余的翻译开销和额外的空间占用. 详细分析请见本文第4节.
本文的主要贡献和创新有3点：
1）深入分析了系统级动态二进制翻译器中已有的指令语义模拟方案给软件代码缓存管理带来的问题，并将其总结为冲突问题和冗余问题；
2）针对这2类问题，提出了基于细粒度状态标签的代码缓存优化方案. 其中多状态代码缓存方案可以解决代码块冲突问题，减少重复的动态翻译开销；弱状态标签方案可以解决代码块冗余问题，减少冗余的动态翻译开销；
3）在真实的系统级动态二进制翻译器 LATX-SYS 中实现了这2个方案，并进行了详细的测试与分析. LATX-SYS基于QEMU[1]开发，可以在LoongArch[2]宿主机上运行 x86 客户机操作系统.
1. 相关工作
软件代码缓存的研究如表2所示，大多集中于用户级DBT，仅有多线程共享机制是针对系统级DBT.
表 2 软件代码缓存相关研究Table 2. Relative Research on Software Code Cache1.1 缓存替换策略
文献[3]对软件代码缓存的替换策略进行了一个详细的对比分析，认为全刷新策略和先进先出（FIFO）策略都是最优的，二者的缺失率都很低并且没有碎片化问题. 文献[4-8]均提出了粗粒度的刷新方式，与FIFO策略的结合被认为是各方面权衡之下最优方案. 文献[9]提出了选择性刷新策略，平衡了内存占用和性能，但又引入了碎片化问题.
1.2 持久性缓存
持久性缓存可以在相同程序的多次执行或不同程序的执行之间进行代码缓存的共享，以降低翻译开销和内存占用. 文献[10]最早对此问题进行了分析，统计了相同程序多次运行和不同程序之间的代码复用率. 此后出现若干持久性缓存的具体实现，文献[11-12]是基于PIN的实现，主要针对相同程序多次运行. 文献[13]是基于DynamoRIO的实现，进一步研究了特权代码共享的安全问题. 文献[14]是基于QEMU的实现，总结了此前方案的不足，实现了范围更大的持久性缓存. 文献[15]进一步提出了累积式持久性缓存，在多次运行中不断增加缓存的代码块，从而不断提高持久性缓存的命中率.
1.3 工作集和热代码
根据局部性原理，程序运行期间通常会呈现出阶段性的特征，即某段时间内的工作集是有限的，这种特征可以被二进制翻译器识别. Dynamo[16]提出了抢先式刷新策略，当发现程序可能出现工作集变迁时，便主动进行1次缓存刷新. 文献[17]在FIFO策略的基础上进行工作集变迁的检测，并动态地调整软件代码缓存容量. 文献[18]结合了这2种方案，提出了静态缓存和动态缓存. 静态缓存容量固定，在工作集变迁时提前进行刷新. 动态缓存容量可变，在工作集变迁时调整容量. 文献[4, 19]依据代码块的执行热度，将热代码存储在一个独立的空间中，从而自适应地识别工作集的变迁. 但统计执行热度需要付出额外开销.
1.4 硬件辅助机制
软硬件结合是提高性能的方式之一. 文献[20-21]提出了相应的硬件缓存机制来加速指令解码. 文献[22-23]在利用了嵌入式系统中的片上便签存储器，来加速代码缓存的访问. 针对代码块查找过程的加速，文献[24]提出了基于CAM和RAM的硬件查找表. 文献[25]则利用了数据缓存的部分空间来存储代码块的映射关系，并使用特殊的指令来加速查找.
1.5 优化内存占用
软件代码缓存会占用内存空间，而内存资源是有限的，尤其在嵌入式环境中. 文献[26]优化了控制转移的翻译，减少了翻译产生的代码量. 文献[27]发现出口代码占很大空间，并提出若干方案进行优化. 文献[28]针对二进制翻译器的各类辅助代码进行优化，包括跳转、间接跳转查找、上下文切换等等，减少内存占用. 文献[29]则针对超级块的构建，提出了可以平衡内存占用和整体性能的路径选择算法. 文献[30]针对代码块重叠问题进行了研究，提出了相应的解决方案来降低内存占用.
1.6 多线程共享机制
系统级DBT中软件代码缓存的研究集中于多线程共享机制. 在多核客户机的场景下，每个客户机核心可以使用1个宿主机线程进行模拟. 文献[31]使用线程私有代码缓存来保证性能. 文献[32]则对比了线程私有代码缓存和线程共享代码缓存，研究了内存和性能之间的平衡. 在线程共享代码缓存基础上，文献[33]提出了一个更高效的共享哈希表来加速访问，文献[34]将共享代码缓存进行分区，来实现多线程并行地代码块翻译. 不同架构的存储一致性模型也不同[35]，文献[33]研究了客户机和宿主机的存储一致性模型不同时的正确性问题.
1.7 本文工作
本文的贡献体现在缓存替换策略和优化内存占用2个方面：一方面，多状态代码缓存方案区分了不同状态的代码块，各自独立进行刷新，避免了互相的冲突，减少了重复的动态翻译开销；另一方面，弱状态标签方案消除了部分状态带来的冗余代码块，降低了内存占用，减少了冗余的动态翻译开销.
2. 二进制翻译和指令语义模拟
2.1 二进制翻译
根据程序模拟的层次，可将DBT分为用户级和系统级. 图1展示了DBT所在的软硬件层次结构. 最底层为处理器等真实硬件环境，其上是宿主机操作系统，再上面是宿主机应用程序. DBT作为宿主机应用程序，向上提供客户机所需的模拟环境. 用户级DBT可以模拟客户机用户态指令，并提供客户机系统调用，实现客户机应用程序的模拟执行. 系统级DBT可以模拟所有客户机指令，并提供客户机硬件环境的模拟，实现客户机操作系统的模拟执行.
![]()
图 1 二进制翻译器的软硬件层次结构Figure 1. Software/hardware hierarchy structure of binary translators动态二进制翻译的基本执行流程如图2所示. 代码块查找阶段会搜索软件代码缓存，寻找是否已经存在所需的翻译代码块. 若找到，则进入代码块执行阶段，执行这个翻译代码块. 若未找到，则进入代码块翻译阶段，读取客户机二进制，翻译产生对应的翻译代码块，并存储到软件代码缓存中，随后回到代码块查找阶段，便可以找到刚刚产生的翻译代码块，从而继续执行. 代码块执行完成后，回到代码块查找阶段，继续寻找下一个需要执行的翻译代码块.
软件代码缓存是一块用于存储翻译代码块的内存空间. 随着程序的持续运行，翻译代码块会不断产生，而软件代码缓存的空间有限，因此需要替换策略. 表3对比了三种常见的替换策略. 全刷新策略在代码缓存空间用尽时，会清空整个空间，然后继续存储新的翻译代码块. 全刷新的优势在于实现简单、刷新操作更快，劣势是复用率较低、动态翻译开销更大. 先进先出（FIFO）策略会优先把最老的翻译代码块无效掉，腾出空间给新的翻译代码块. FIFO的优势在于可以尽可能复用已有的翻译代码块，劣势在于无效翻译代码块的操作较为复杂，且由于代码块长度不一，可能需要多次刷新才能获取足够的空间. 这2种方案共同的优势是没有碎片化问题，有利于简化逻辑、降低刷新开销. 这2种方案结合，也被认为是目前最好的方案，即粗粒度的FIFO策略. 该策略的一次刷新操作会无效掉某个地址范围内的所有翻译代码块.
表 3 替换策略的比较Table 3. Comparison of Replace Strategy替换策略 复用率 碎片化 刷新操作 全刷新 低 无 简单 FIFO 高 无 复杂 粗粒度FIFO 较高 无 适中 代码块执行阶段中一个典型的优化是代码块链接. 如果每次执行完1个翻译代码块，都需要进行1次代码块查找，那么整体性能就会很低. 而客户机基本块的结尾常常是直接跳转指令，其跳转目标是确定的，意味着在当前翻译代码块（记为A）执行完后，下一个待执行的翻译代码块（记为B）也是确定的. 代码块链接会修改A的结尾处代码，使A执行完后不再退出执行，而是跳转到B继续执行. 若客户机基本块的结尾是间接跳转指令，此时跳转目标是不确定的，只有在每次执行后才可知，此时代码块查找是必要的.
2.2 指令语义模拟
为保证正确性，DBT需要模拟客户机指令的正确语义. 指令执行语义常常与执行时的处理器状态有关，若状态不同，则指令的行为可能完全不同. 在用户级DBT中，通常认为客户机一直处于用户态，此时用户态指令的行为一般是固定的. 而在系统级DBT中，则需要考虑客户机所有可能的状态，且需要模拟所有的客户机指令，包括用户态指令和特权态指令.
系统级DBT在模拟客户机指令语义时有2种方案，即动态检测方案和状态标签方案. 动态检测方案在翻译代码块运行时对客户机状态进行动态检测. 具体来说，代码块翻译阶段负责生成读取并判断当前客户机状态的宿主机代码，以及依据判断结果执行对应宿主机代码的选择逻辑. 代码块执行阶段负责执行翻译代码块，从而动态地检测客户机状态并执行对应的指令行为. 状态标签方案在进入执行阶段之前进行检测. 具体来说，在代码块翻译阶段中，依据当前客户机状态，在翻译代码块中仅生成当前状态下客户机指令的执行行为，并将翻译代码块的状态标记为当前客户机状态. 在代码块查找阶段中，将翻译代码块的状态与客户机状态进行对比，只有相同的情况下才能进入代码块执行阶段，否则便是查找失败，进入代码块翻译阶段，生成当前客户机状态下的翻译代码块.
本文以x86客户机指令FADD和客户机状态EM为例，描述2种方案的基本原理. 当客户机状态EM=1时，FADD触发浮点异常. 当客户机状态EM=0时，FADD执行浮点加法操作. 为了便于说明和理解，本例中客户机基本块仅包含1条客户机指令FADD，且仅考虑客户机的EM状态.
图3展示了指令语义模拟的动态检测方案. 首次执行时，在代码块查找阶段查询失败，进入代码块翻译阶段，随后生成的翻译代码块的开头位置包含了读取和判断客户机状态的代码，以及2种不同的执行行为. 在代码块执行阶段，根据客户机状态不同，该翻译代码块的执行行为不同. 当客户机状态EM=1时，读取和判断当前客户机状态后，执行触发客户机异常的操作. 相应地，当客户机状态EM=0时，执行浮点加法操作. 由此可见翻译代码块中的宿主机代码模拟了该指令在不同客户机状态下的不同行为，保证了正确的客户机指令语义.
图4展示了指令语义模拟的状态标签方案. 首次执行时代码块查找失败，进入代码块翻译阶段，此时客户机状态EM=1，翻译代码块A中仅包含触发客户机异常的宿主机代码，且翻译代码块A的状态标签中EM状态会被标记为1. 在代码块查找阶段，会依据当前客户机状态进行判断. 对于翻译代码块A，当客户机状态EM=1时，二者状态一致，认为查询成功，可以执行；当客户机状态EM=0时，二者状态不同，认为查询失败，则进入代码块翻译阶段. 此时在客户机状态EM=0时会翻译生成仅包含执行浮点加法操作的翻译代码块，且其状态标签中EM会被标记为0. 由此可见，翻译代码块的状态标签描述了其所需的执行条件，从而保证正确的客户机指令语义.
动态检测方案和状态标签方案均能实现指令语义的正确模拟，但也都存在不足之处. 在代码块翻译阶段，动态检测方案总是会生成该指令的所有行为，使得代码膨胀率较高，增加软件代码缓存和硬件指令缓存的压力. 状态标签方案仅在需要执行时才会生成相应的指令行为，消除了不必要代码，但代码块的数量会更多. 在代码块执行阶段，动态检测方案下，每次执行时都会至少进行1次读取和判断操作，意味着更多的运行时开销，从而降低整体的性能表现. 状态标签方案需要在运行前进行1次额外的检查逻辑，但运行时无需额外的检测，避免了翻译代码块的运行时开销，有利于提高整体性能.
二进制翻译器所面临的一个重要问题是性能问题，尤其是系统级DBT. 目前已有的系统级DBT均采用了状态标签方案.
3. 软件代码缓存问题分析
状态标签方案通过对翻译代码块添加对应的客户机状态标签，来避免动态检测的开销. 此时对于同一个客户机代码块，软件代码缓存中可能会存在多个状态标签互不相同的翻译代码块. 本文对该现象进行深入的研究分析，总结出了2个问题：一个是冲突问题，表现为不同状态的翻译代码块存储在同一个软件代码缓存空间中，在存储、链接和刷新时会互相冲突，降低空间利用率；一个是冗余问题. 对于来自同一个客户机代码块的多个翻译代码块，尽管它们的状态标签不同，但其内部的宿主机代码可能是相同的，意味着存在额外的翻译开销和冗余的内存占用.
3.1 代码块冲突问题
冲突问题源于不同状态标签的翻译代码块存储于同一个代码缓存空间中. 典型的客户机状态是特权级. 对于一个包含特权指令的客户机基本块，在客户机状态处于用户态时，生成的翻译代码块中应当包含触发客户机异常的行为. 当客户机处于特权态时，生成的翻译代码块中应当包含该特权指令的正常执行行为. 图5展示了 Ubuntu/x86 16.04 系统在启动阶段中代码缓存中2种状态的翻译代码块的分布. 横坐标是软件代码缓存FIFO区域的编号，每个FIFO区域容量为4 MB，共有32个，总容量128 MB. 纵坐标是翻译代码块数量. 系统启动阶段最初执行的是引导程序和内核初始化程序，客户机处于特权态，因此仅包含特权级翻译代码块. 当第一个用户程序开始运行后，逐渐出现用户级翻译代码块. 此时2种翻译代码块交错地存储在软件代码缓存中. 图6展示了系统启动阶段完成后，软件代码缓存中代码块的分布情况. 随着用户程序的执行和软件代码缓存的刷新，用户级翻译代码块和特权级翻译代码块交错地分布在整个软件代码缓存空间中.
从代码块分布的角度来看，同一状态的代码块是比较分散的. 而当客户机处于某个状态下时，只能执行该状态下的翻译代码块，但这些代码块分散地存储在整个软件代码缓存空间中，程序执行的局部性不够好，增加了硬件指令缓存的压力.
从软件代码缓存的容量限制来看，同一空间中存储不同状态的翻译代码块是低效的. 在部分架构下，受限于直接跳转指令的范围，如MIPS架构中直接跳转指令的范围是±128 MB，为了支持代码块链接机制，软件代码缓存的容量被限制在128 MB. 然而不同状态的翻译代码块之间并不能直接跳转，因此将它们存储在相同的空间中反而是不必要的.
从软件代码缓存的替换策略来看，对于粗粒度的刷新策略，1次刷新操作会无效掉若干翻译代码块，其中包含多种状态的翻译代码块. 如图6所示，一个FIFO区域内既有特权级翻译代码块，也有用户级翻译代码块. 2种翻译代码块的执行情况并不相同，共同进行刷新是不合理的. 实际上，客户机操作系统在运行中，执行的用户程序数量多、种类多，而操作系统始终只有一个，且部分系统代码会经常运行，如异常和中断处理程序.
我们将翻译代码块被无效后又重新翻译生成的行为称为代码块的重翻译，并在128 MB软件代码缓存中，基于4 MB粒度的FIFO刷新策略，统计了Ubuntu/x86 16.04系统启动过程中的重翻译情况，如图7所示. 总共收集了80次FIFO刷新时的数据，每10次进行合并统计，同时也对全部80次进行了合计. 我们进一步定义了重翻译距离. 对于一个翻译代码块的重翻译行为，重翻译距离为N表示：当它所在的FIFO区域刷新后，又经过了N次FIFO刷新，然后该翻译代码块被重新生成. 重翻译距离的范围是0~31，大于等于32意味着整个软件代码缓存都被刷新过，因此不予统计. 特别地，重翻译距离为0意味着该翻译代码块被刷新后，立刻在原FIFO区域内重新翻译生成.
图7（a）（b）展示了特权级翻译代码块的重翻译情况. 图7（a）为代码块的重翻译率. 总的来看，对于被刷新的特权级翻译代码块，高达60%会在后续运行中重新翻译生成. 图7（b）展示了重翻译距离的分布. 总的来看，重翻译距离为0的情况占比高达46%，也就是说有将近一半的特权级翻译代码块在被刷新后立刻就重新生成了. 重翻译距离为1~4的情况占比 24%，重翻译距离5~12的情况占比13%. 总的来说，重翻译距离在12以内的情况占比高达83%.
图7（c）（d）展示了用户级翻译代码块的重翻译情况. 由于系统启动最初阶段均是系统代码，因此第1列并没有用户态的数据. 图7（c）展示了重翻译率. 对于被刷新的用户级翻译代码块，总共有45%会重翻译，明显低于特权级翻译代码块的重翻译率. 图7（d）展示了重翻译距离的分布. 对于被刷新的用户级翻译代码块，重翻译距离为0的情况仅占22%，而大于12的情况占比高达 41%，也就是说用户级翻译代码块被刷新后往往不会立刻重翻译，而是运行一段时间后才可能会重翻译.
3.2 代码块冗余问题
冗余问题源于同一客户机基本块对应的多个状态标签不同的翻译代码块可能包含相同的宿主机指令. 完整的状态标签中包含了多种客户机状态信息，可能会导致代码块冗余问题.
我们发现了导致x86客户机出现大量代码块冗余的客户机状态. 在x86架构的处理器中有3个与浮点和向量指令的标志位，分别是MP，EM，TS. 为了便于描述，我们将这3个标志统称为浮点向量控制状态. 当该状态开启时，浮点和向量指令的执行会触发异常. 当该状态关闭时，浮点和向量指令可以正常执行. 如表4所示.
表 4 浮点向量控制状态Table 4. Floating and Vector Control Status浮点向量控制状态 浮点向量指令行为 开启 触发异常 关闭 正常执行 x86架构通过这个机制来提供针对浮点和向量上下文的延迟处理，当客户机使用该机制时，同一段客户机程序既可能会运行在该状态启动的情况下，也可能会运行该状态关闭的情况下. 而当一个客户机代码块不包含浮点和向量指令时，其执行行为与浮点向量控制状态是无关. 在状态标签方案下，同一个客户机代码块会对应多个浮点向量控制状态不同的翻译代码块，而它们的宿主机指令可能是相同的，因此造成了代码块的冗余.
我们将来自同一个客户机基本块的多个状态标签不同的翻译代码块定义为一个相似组. 更进一步的，我们将一个相似组中宿主机代码也相同的多个翻译代码块定义为一个冗余组. 一个相似组的相似数定义为该组内翻译代码块的数量，而一个冗余组的冗余数定义为该组内翻译代码块的数量减1，即认为至少有1个翻译代码块是必要的，其余的则是冗余的. 对于某个时刻下软件代码缓存，定义相似率为所有相似组的相似数的和与代码块总数的比值，定义冗余率为所有冗余组的冗余数的和与代码块总数的比值. 根据定义可知，冗余率的上限是相似率的一半. 相应地，非冗余率即为1减去冗余率，非相似率即为1减去相似率. 同时，相似非冗余率即为相似率减去冗余率.
表5展示了一个代码缓存的示例. 客户机代码块A产生了3个翻译代码块A1，A2，A3，对应一个相似组，其相似数为3. 客户机代码块B和C均仅产生了1个翻译代码块，因此不构成相似组. 翻译代码块A1和A2的宿主机指令完全相同，构成一个冗余组，且冗余数为1. 总的来说，代码缓存的冗余率为20%，非冗余率为80%，相似率为60%，相似非冗余率为40%.
表 5 冗余率示例Table 5. Example of Redundancy Ratio客户机代码块 翻译代码块 状态标签 宿主机指令 A A1 ST1 CS1 A2 ST2 CS1 A3 ST3 CS3 B B1 ST4 CS4 C C1 ST5 CS5 图8展示了Windows XP/x86系统在启动过程中某些时刻下，软件代码缓存中的相似和冗余情况. 横坐标使用FIFO刷新次数表示系统运行时间，纵坐标为代码块数量. 平均而言，软件代码缓存的相似率达到60%，冗余率则高达28%. 此处只统计了浮点向量控制状态带来的冗余，详细介绍见4.2节.
4. 设计与实现
我们总结了状态标签方案造成的2类问题：一类是冲突问题；一类是冗余问题. 本文针对这2类问题，分别提出了2种基于细粒度状态标签的解决方案. 这2种方案并不冲突，可以共存来同时解决这2类问题. 针对冲突问题，本文主要解决了由特权级状态带来的代码块冲突情况. 针对冗余问题，本文主要解决了由浮点向量控制状态带来的代码块冗余情况. 本质上来说，本文提出的方案并不局限于特权级状态和浮点向量控制状态，对客户机也不局限于x86架构. 对于任何带来代码块冲突和冗余的客户机状态，本文的方案均被使用来解决相应的问题.
4.1 多状态代码缓存
代码块冲突问题的根源在于不同状态的翻译代码块存储在同一个软件代码缓存中，因此解决的方式是将不同状态的翻译代码块存储于不同的软件代码缓存空间，避免互相冲突. 本文提出了多状态代码缓存，支持将特权级代码块和用户级代码块存储于不同的代码块缓存空间中. 区别于其他将代码缓存空间分割的方案，该方案设计的多个代码缓存空间考虑的是系统级DBT特有的代码块状态标签，依据状态的不同来分别存储. 因此该方案与其他代码缓存空间的方案是兼容的，例如文献[2]提出的根据代码块的执行热度来分别存储生命周期较短的代码块和生命周期较长的代码块，但该方案需要付出额外的开销来统计执行热度.
图9展示了针对特权级的多状态代码缓存方案. 针对 x86的0特权级和3特权级，分别设计了特权级缓存和用户级缓存. 特权级缓存用于存储特权级翻译代码块，对应客户机的操作系统代码. 用户级缓存用于存储用户级翻译代码块，对应客户机的用户程序代码. 在多状态代码缓存的基础实现中，2个代码缓存空间的容量都是128 MB，且均采用4 MB粒度的FIFO刷新策略. 当客户机运行操作系统时，代码块的执行、查找和翻译均发生在特权级缓存中. 当客户机运行用户程序时，代码块的执行、查找和翻译均发生在用户级缓存中.
需要注意的是，x86 的特权级并不只有0和3，还有1和2. 若客户机操作系统使用了1特权级和2特权级，也可以进一步增加相应特权级的代码缓存空间. 通常来说，x86操作系统只使用了3特权级和0特权级，分别对应特权态和用户态，因此本文只处理了0和3这2个特权级. 更进一步的说，支持Intel VT-X扩展的x86处理器还拥有一个特殊的non-root模式，属于x86架构的硬件虚拟化特性. 若x86架构的客户机操作系统中运行了使用硬件虚拟化的程序，此时也可能会存在状态为non-root的翻译代码块. 在多状态代码缓存方案下，可以将此类翻译代码块存储于独立的空间，与root状态的翻译代码块区分开.
从代码块执行的角度来看，处于某个特权级状态下的客户机，例如用户态，通常只会运行用户程序代码，即运行在用户级缓存中，此时缓存空间中全部都是用户级翻译代码块，因此有着更好的指令局部性，有利于硬件的指令预取. 此外，用户级缓存中不再负责存储特权级翻译代码块，也就有了更多的空间来存储用户级翻译代码块，有利于提高代码块查找命中率，降低动态翻译开销. 相应地，多状态代码缓存方案需要更多的内存空间来支持多个软件代码缓存空间. 若受限于内存容量，或设计了过多的软件代码缓存空间，使得单个代码缓存空间的容量过低，反而可能会造成大量的代码块查找缺失，进而产生更多的动态翻译开销，总体上反而会降低性能. 因此缓存空间的数量和各自的容量需要有着合理的设计.
4.2 弱状态标签
代码块冗余问题表现为不同状态的翻译代码块却有着相同的宿主机代码. 该问题的根源在于客户机状态的不同并不一定会导致客户机指令行为的不同. 本文提出了弱状态标签方案，并针对x86架构的浮点向量控制状态进行了的实现，消除了由该状态导致的冗余代码块.
图10展示了浮点向量控制状态导致冗余代码块的示意图. 客户机基本块A包含2条客户机指令，分别是定点指令和浮点指令. 在浮点向量控制状态关闭时，基本块A会生成翻译代码块A1并将状态标签中浮点向量控制状态记录为关闭. A1中的宿主机指令负责完成对应的定点和浮点操作. 在浮点向量控制状态开启时，基本块A会生成翻译代码块A0并将状态标签中浮点向量控制状态记录为开启. A0中的宿主机指令首先完成对应的定点操作，因为定点指令的行为不受影响，而浮点指令对应的则是触发客户机异常. 可见代码块状态标签发挥了作用，正确地处理了浮点指令在不同客户机状态下的不同行为，此时翻译代码块A1和A0都是必要的.
客户机基本块B包含2条客户机定点指令. 因为定点指令不受浮点向量控制状态的影响，因此无论客户机的浮点向量控制状态是开启还是关闭，定点指令的行为是不变的，因此对应的翻译代码块B1和B0中的宿主机指令便是相同的. 此时翻译代码块B1和B0只有状态标签不同，但却有着相同的宿主机指令，因此是存在冗余的. 对于客户机的某种状态S，若一个基本块中不包含受该状态影响的指令，我们将其称之为S无关基本块，反之则称为S相关基本块. 客户机基本块B便属于浮点向量控制状态无关基本块，客户机基本块A则属于浮点向量控制状态相关基本块.
针对代码块冗余问题，我们提出了弱状态标签方案，在保证客户机指令语义模拟的正确性的前提下，可以消除由特定状态导致的冗余代码块. 弱状态标签方案的基本思想是将导致冗余的状态S*在翻译代码块的状态标签中进行弱化，从而消除客户机状态S*对S*无关基本块的影响，进而避免冗余代码块的产生. 为保证客户机指令语义模拟的正确性，弱状态标签方案引入了额外的动态检测机制来避免出错. 根据检测的粒度不同，可以分为2种实现方案：一种是基于代码块的弱状态标签方案；一种是基于指令的弱状态标签方案. 本文实现了针对浮点向量控制状态进行弱化处理的弱状态标签方案.
图11描述了基于代码块的弱状态标签方案. 仍然以基本块A和基本块B为例. 对于基本块A的翻译，仍会生成翻译代码块A1和A0且状态标签中仍然包含客户机当前的浮点向量控制状态信息. 对于基本块B的翻译，则只会生成翻译代码块B2，其状态标签中不再包含浮点向量控制状态信息. 由此实现了冗余代码块的消除.
为保证正确性，此时翻译代码块会包含一个额外的标记，来记录对应的基本块与浮点向量控制状态是相关的还是无关的. 基本块A是浮点向量控制状态相关基本块，因此源于基本块A的翻译代码块，即翻译代码块A1和A0，都会被标记为相关. 相应地，源于基本块B的翻译代码块B2会被标记为无关. 在代码块查找阶段，根据此标记来决定是否需要检查浮点向量控制状态. 若相关，则需将翻译代码块的状态标签中记录的浮点向量控制状态与客户机当前的浮点向量控制状态进行比较，不一致时认为查询失败. 若无关，则不必进行该检查.
代码块链接允许执行流从一个翻译代码块直接跳转到另一个翻译代码块，可以减少上下文切换和代码块查找的开销，是二进制翻译器提高性能的关键. 在原本的代码块状态标签方案中，为保证正确性，只允许相同状态标签的翻译代码块进行链接. 而在基于代码块的弱状态标签方案中，部分翻译代码块被消除，状态标签的含义也有所改变，因此需要新的规则来指导代码块链接.
我们以A0*，A1*，B2*表示3类翻译代码块，类比于图11中的翻译代码块A0，A1，B2，这3类分别是：1）标记相关且状态标签为开启；2）标记相关且状态标签为关闭；3）标记无关的3类翻译代码块. 表6展示了所有的代码链接情况. 从A0*直接跳转到其他翻译代码块的情况是无需关心的，因为A0*会触发客户机异常进而退出代码块执行. A1*不能直接跳转到A0*的原因是二者的状态标签不同，此规则和原状态标签方案保持一致. 值得注意的是从B2*直接跳转到A0*，A1*是不允许的，因为当B2*正在运行时，当前客户机的浮点向量控制状态是不确定的. 若代码块链接使B2*直接跳转到A0*，那么在客户机浮点向量控制状态关闭时会出错，A0*对应的浮点指令本应正常执行却错误地触发了客户机异常. 相应地，若允许B2*直接跳转到A1*，则可能使A1*对应的浮点指令在本应触发客户机异常的时候却正常执行. 反之，A1*和B2*都是可以直接跳转到B2*的，因为B2*的行为与浮点向量控制状态无关.
表 6 代码块链接情况分析Table 6. Analysis of Code Block Link Cases直接跳转 跳转情况 无需关心 A0*→A0*，A0*→A1*，A0*→B2* 允许 A1*→A1*，B2*→B2*，A1*→B2* 不允许 A1*→A0*，B2*→A0*，B2*→A1* 为在代码块链接的情况下保证正确性，我们设计了基础方案和优化方案. 基础方案只是简单地不允许可能出错的代码块链接情况，尽管这可能会带来较高的性能损失. 优化方案如图12所示，我们引入了一定程度的动态检测机制，基本思想是在翻译代码块的起始位置生成一段检查客户机浮点向量控制状态的操作，若状态检测通过则继续执行，若失败则退出执行. 实际上，只有A1*和A0*这2类翻译代码块需要动态检测，B2*不需要，而且B2*无需在翻译代码块中生成检测代码，从而减少内存占用. 进一步地，我们只需要针对B2*到A0*，A1*这2种情况进行动态检查，从而尽可能地降低动态开销，为此每个翻译代码块设置了2个入口地址，检测入口对应状态检测代码，执行入口则跳过了状态检测.
![]()
图 12 基于代码块的弱状态标签优化方案Figure 12. Optimized scheme for code block-based weak state label图13描述了基于指令的弱状态标签方案. 此方案下所有翻译代码块的状态标签中都不再包含浮点向量控制状态的信息，从根本上消除了冗余代码块. 为确保正确性，我们需要修改受影响的浮点指令和向量指令的翻译过程. 对于客户机基本块A，浮点指令的翻译结果中会首先进行客户机状态检测，此时只需检测浮点向量控制状态即可. 根据检测结果，选择正常执行浮点操作，或者触发客户机异常，从而正确地完成指令语义模拟. 在代码块链接过程中，不再关心浮点向量控制状态，只需检查其他状态是否相同即可.
尽管翻译代码块中的状态标签不再包含浮点向量控制状态的信息，但对于当前客户机状态的维护上还是需要处理该状态，以便进行动态检测. 基础方案下，我们针对每条浮点和向量指令都生成了状态检测代码，实现简单，但会带来较大的内存占用和性能开销. 通过观察指令的行为，我们进一步实现了优化方案. 对于浮点向量控制状态，其只会导致受影响指令有2种行为，要么正常执行，要么触发客户机异常. 而在触发客户机异常时，执行流会直接退出代码块执行阶段. 对于同一个基本块中的多条指令，若前面的已经进行了状态检测，那么后续指令可以不必再进行检测，从而降低代码量和动态开销. 需要说明的是，实际上本文所述的浮点向量控制状态对应x86架构中MP，EM，TS这3个标记位，不同指令的状态检测行为也有所不同，具体实现中只能针对相同的状态检测行为进行处理，才能保证正确性.
从本质上讲，弱状态标签方案是原有的2种指令语义模拟方案的结合，即在动态检测和状态标签之间寻找平衡，引入一定的动态开销的同时，可以极大地降低由部分特殊的状态标签所导致的冗余代码块，从而减少不必要的动态翻译开销，减少内存占用，缓解软件代码缓存的压力. 我们发现x86架构下的浮点向量控制状态是非常适合该方案的一种场景. 一方面，用户程序的同一段代码既可以运行在该状态开启时，也可以运行在该状态关闭时，意味着同一个客户机基本块会对应多个不同状态的翻译代码块，其中可能存在冗余情况. 另一方面，很多用户程序没有或仅有少量的浮点和向量指令，且包含浮点和向量指令的代码所在的位置通常比较接近，这就有利于我们尽可能地降低所需的动态检测开销. 相对来说，客户机的特权级状态并不适合该方案，因为不同特权级下执行的通常是不同的程序，也就不存在冗余问题.
5. 实验测试
我们在系统级动态二进制翻译器LATX-SYS中实现并测试了本文提出的2种方案. LATX-SYS基于QEMU 6.0.0开发，自研了效率更高的LATX翻译引擎，能够在LoongArch[34]宿主机平台实现完整x86架构操作系统的模拟运行. 表7展示了实验配置信息.
表 7 实验配置Table 7. Experiment Configuration系统层次结构 实验配置 客户机测试程序 系统启动、SPEC CPU2000 客户机操作系统/x86 Windows XP，Ubuntu 16.04 系统级DBT LATX-SYS 宿主机操作系统 Loongnix（Linux 4.19内核） 宿主机硬件平台 3A5000 LoongArch 处理器 所有测试的基准配置是LATX-SYS配备单个容量为128 MB的软件代码缓存. 基准的替换策略是4 MB粒度的FIFO刷新策略，优于QEMU自身所使用的简单的全刷新方案. 基准的指令语义模拟采用状态标签方案，实现上与QEMU保持一致.
针对代码块冲突问题，我们主要观察了代码块分布情况，并对关键数据进行了统计. 针对代码块冗余问题，我们主要分析了软件代码缓存的冗余率. 我们选择了Windows XP/x86和 Ubuntu/x86 16.04这2种客户机操作系统，主要测试了系统启动阶段，因为启动阶段的代码量较大，会产生大量的翻译代码块，从而对软件代码缓存管理带来较大的压力. 此外，为了进一步测试弱状态标签方案带来的动态开销，我们基于SPEC CPU2000性能测试集进行了测试.
不同的客户机操作系统在是否使用浮点向量控制状态上有所区别. 在Linux系统上我们选择了3.10和4.14这2个版本. Linux 3.10版本可以使用内核参数来配置客户机使用该状态来实现延迟上下文切换. Ubuntu 16.04默认的Linux 4.14版本中删除了这个配置选项，即不再支持延迟上下文切换. 而Windows XP系统则默认使用了该状态来实现延迟上下文切换.
5.1 代码块分布
我们在基准配置的基础上，实现了针对特权级的多状态代码缓存，包含2个软件代码缓存空间，分别是用户代码缓存和特权代码缓存，容量均为128 MB且均采用4 MB粒度的FIFO刷新策略. 我们测试了Ubuntu 16.04在使用Linux 4.14内核的启动过程，代码块的分布情况见图14和图15.
![]()
图 14 多状态缓存下的代码块分布：系统启动阶段Figure 14. Code blocks distribution with multi-state code cache: system startup stage![]()
图 15 多状态缓存下的代码块分布：系统运行阶段Figure 15. Code block distribution with multi-state code cache: system running stage相比于图5和图6所示的基准配置下代码块分布情况，多状态代码缓存中特权级翻译代码块和用户级翻译代码块互不干扰，各自拥有独立的空间. 随着系统运行，软件代码缓存的FIFO刷新也在各自的空间中进行. 当客户机执行用户程序时，软件代码缓存管理的刷新操作只会作用在用户代码缓存上，也就只会无效掉用户级翻译代码块，而不会无效掉特权级代码块. 根据前文的统计，特权级代码块具有更高的重翻译率，将其无效反而会带来额外的开销.
我们进一步统计了软件代码缓存的一些关键操作，包括刷新次数和翻译次数，详细数据见表8. 替换测试同为4 MB粒度的FIFO刷新策略，多状态代码缓存下总FIFO刷新次数降低了44%，刷新开销得到极大降低. 在翻译代码块的刷新次数上，总次数下降了43%，符合FIFO刷新次数的降低. 进一步看，用户级翻译代码块的刷新次数降低了20%，而特权级翻译代码块的刷新次数降低了100%. 因为多状态代码缓存下，用户程序执行时只会操作用户代码缓存，不会干扰特权代码缓存，且特权级翻译代码块总量不多，足以完全容纳在独立的128 MB空间中. 在代码块翻译次数上，总次数降低了18%. 得益于独立的空间，特权级翻译次数降低了48%. 用户级翻译次数只降低了6%，低于用户级刷新次数降低的20%，这是因为系统启动阶段有大量用户程序执行，因此更倾向于执行新的用户代码，被刷新的用户级翻译代码块更倾向于不被重翻译. 该结果也与图7中展示的翻译代码块的重翻译率相吻合，即特权级翻译代码块有更高的重翻译率，对其减少刷新会极大降低翻译次数，而用户级翻译代码块的重翻译率更低，对其减少刷新所带来的翻译次数的下降也会相对更少.
表 8 代码缓存操作的对比Table 8. Comparison of Code Cache Operations统计类别 基准 多状态代码缓存 降低比例/% FIFO刷新次数 87 49 44 代码块
刷新总次数 563 491 319 041 43 用户级 399 310 319 041 20 特权级 164 181 0 100 代码块
翻译总次数 769 473 633 962 18 用户级 563 021 526 799 6 特权级 206 452 107 163 48 软件代码缓存的容量是一个重要因素，而多状态代码缓存下相当于将总容量扩大了，从而极大地减少了刷新和翻译次数. 为了更好地体现不同状态代码块之间冲突降低带来的提升，我们进一步测试了在总容量相同的情况下，多状态代码缓存的具体情况. 总容量设置为128 MB与基准相同，特权代码缓存与用户代码缓存的容量比例是一个重要参数，容量调整的粒度是4 MB，与FIFO刷新的粒度一致.
图16展示了不同容量比例下，多状态代码缓存的代码块翻译次数. 横坐标为特权代码缓存的容量占比，纵坐标为代码块翻译次数. 最好的情况下，总翻译次数为728 979，此时特权代码缓存容量为40 MB，用户代码缓存容量为88 MB. 图16中2条横线来自表8，实线表示基准方案的翻译次数769 473，虚线表示多状态代码缓存的翻译次数633 962. 由此可见在总容量相同的情况下，合适比例的多状态代码缓存也会优于基准方案. 然而，如果任意一个代码缓存容量过低，都会造成严重的空间不足，进而导致代码块的刷新次数和翻译次数都很高.
![]()
图 16 特权代码缓存不同容量占比下代码块翻译次数Figure 16. Translation number of code blocks with different capacity percentage of privileged code cache5.2 代码块冗余
我们在基准配置的基础上实现了弱代码标签方案，针对浮点向量控制状态进行冗余代码块的消除. 在实际测试中，我们进一步区分了特权级翻译代码块和用户级翻译代码块，如表9所示. 在基准配置的基础上，仅针对用户级翻译代码块进行冗余消除的记为弱状态标签方案W1，而针对所有的翻译代码块进行冗余消除的记为弱状态标签方案W2.
表 9 代码块冗余测试方案Table 9. Testing Schemes for Code Block Redundancy测试方案 冗余消除范围 基准 未消除 弱状态标签方案W1 针对用户级代码块 弱状态标签方案W2 针对所有的代码块 图17展示了Windows XP系统启动过程中代码缓存的相似率，包括了3个运行阶段. 图17（a）初始阶段中，基准的相似率高达55%，其中特权级相似率达到了38%，因为初始阶段有大量系统代码. 弱状态标签方案W1下相似率降低至34%，弱状态标签方案W2进一步降低到13.73%. 因为具体实现中只处理了浮点向量控制状态，其他状态仍可能导致相似代码块，进而可能产生一定程度的冗余. 图17（b）启动桌面过程中，基准的相似率达到了60%，用户级和特权级都较高. 弱状态标签方案W1降低至18%，弱状态标签方案W2进一步降低至5%，此时用户级和系统级的相似率都很低，意味着大量的冗余是浮点向量控制状态所导致的. 图17（c）进入桌面后，用户进行的操作是点击开始菜单，此时基准的相似率达到30%，用户级，用户级相似率高达19%，意味着此时主要在执行用户程序. 弱状态标签方案W1降低至16%，用户级相似率降至1%. 弱状态标签方案W2进一步降低至3%，绝大部分冗余代码块被消除，只剩下少量由其他状态导致的相似代码块，其中存在些许冗余.
![]()
图 17 Windows XP系统启动过程代码缓存相似率Figure 17. Code cache similarity ratio on Windows XP startup system process图18展示了Windows XP启动过程中代码缓存相似率的变化情况，记录了从系统启动到进入桌面的整个过程. 横坐标为运行时间，表现为FIFO刷新次数，从而体现软件代码缓存的变化. 特别地，横坐标为0指的是软件代码缓存首次存满的时候.
![]()
图 18 Windows XP启动过程代码缓存相似率变化曲线Figure 18. Change curve of code cache similarity ratio on Windows XP startup process根据图18可知，基准方案共经历了124次FIFO刷新，代码缓存相似率明显很高，最高处接近70%. 弱状态标签方案W1已有大幅下降，共经历84次FIFO刷新，代码缓存相似率在30%左右，最终降至20%以下. 弱状态标签方案W2只在系统启动初始阶段较高，这是因为初始阶段有固件代码和初始化的系统代码，客户机状态更加复杂，而我们的实现只处理了浮点向量控制状态，其他状态仍可能导致代码块相似. 最终弱状态标签B的代码缓存相似率降低至不到5%，消除了绝大部分冗余代码块.
5.3 综合测试
多状态代码缓存可以避免不同状态代码块之间的冲突，减少不必要的刷新，从而减少了重复的翻译. 弱状态标签可以消除特定状态带来的冗余代码块，从而减少了冗余的翻译. 二者都可以减少动态翻译次数，降低软件代码缓存管理的压力，具体表现是在相同的客户机程序下，总的代码块翻译次数会有所下降. 我们对这2种方案，测试了单独和组合的情况下，系统启动过程中总的代码块翻译次数.
同时我们也统计了理想的最优情况，此时软件代码缓存的容量设定为无限大，不存在刷新，并且也不存在冗余代码块. 理想情况数据的获取方式是记录所有翻译代码块的相关操作，然后经过离线分析，从中去除因缓存刷新导致的重翻译记录，去除所有的冗余代码块的记录. 结果如图19所示.
图19（a）展示了Ubuntu 16.04系统启动过程中，不同方案的代码块翻译次数. 为了体现弱状态标签方案，我们使用了Linux 3.10内核并配置内核参数来使能浮点向量控制状态. 基准方案总翻译次数达到
1100 k. 仅采用多状态代码缓存时，总翻译次数下降至815 k，其中特权级翻译次数下降程度更高，源于独立空间带来的优势. 仅采用弱状态标签时，总翻译次数下降至669 k，用户级翻译次数有较大幅度下降，意味着大量冗余被消除了. 2种方案相结合时可以达到更好的效果，总翻译次数下降至559 k，比较接近理想的462 k. 此时系统级翻译次数已非常接近理想情况，相差的部分源于浮点向量控制状态之外的状态带来的冗余代码块. 用户级翻译次数还有一定距离，尽管消除了冗余代码块，但仍受限于缓存容量.图19（b）展示了Windows XP系统启动过程的测试结果，统计了从系统启动到关机的整个过程. 基准方案总翻译次数高达
1775 k，有大量的系统代码和用户代码，从而对缓存容量更为敏感. 因此，仅采用多状态代码缓存时总翻译次数为859 k，低于仅采用弱状态标签时的1167 k. 这2种方案的结合下总次数进一步降低至717 k，但与理想的545 k仍有较大距离，同样源于代码缓存的容量的不足.5.4 性能测试
本文所提出的2种方案均可以降低软件代码缓存管理的压力，表现为代码块刷新、翻译次数降低，减少内存占用. 多状态缓存方案具有更好的指令局部性，可以减少系统运行过程中的无效刷新，弱状态标签方案能够减少冗余代码块的翻译开销，从而提高系统的整体运行效率.
我们测试了Ubuntu 16.04系统的启动时间，内核使用的是Linux 3.10版本且使能了浮点向量控制状态. 图20展示了LATX-SYS在不同配置下相对于基准方案的运行时间. 横坐标为多状态代码缓存在总容量128 MB情况下不同容量比例. 图20（a）为原始的状态标签方案，图20（b）为弱状态标签方案. 总体趋势与图16相近，在合适的容量比例下，多状态代码缓存的运行时间更短. 图20（a）中，实线为基准方案，因此是100%. 虚线为使用了2个128 MB空间的多状态代码缓存方案，此时整体运行时间减少了10%. 图20（b）中，实线为弱状态标签方案，此时大量的冗余代码块被消除，使得翻译开销和刷新开销得到下降，整体运行时间降低了17%. 虚线为多状态代码缓存和弱状态标签的融合方案，代码块的刷新、翻译次数大大减少，使得整体运行时间降低了20%.
弱状态标签方案引入的动态检测机制，尽管可以降低冗余代码块的翻译和内存占用，但会带来更多的运行时开销，因此我们针对弱状态标签方案测试并分析了其动态开销. 如表10所示，根据动态检测的粒度不同，弱状态标签方案的具体实现可以分为2类：一类是基于代码块检测的方式；一类是基于指令检测的方式. 每种方式的实现又分为基础方案和优化方案，因此共有4种弱状态标签方案的具体实现. 我们在基准配置的基础上实现了这4种方案，针对客户机x86架构中的浮点向量控制状态进行冗余消除，而且都是针对所有的翻译代码块，包括特权级和用户级. 我们使用了SPEC CPU2000基准测试程序，客户机是Ubuntu 16.04系统，Linux 3.10内核版本使能了浮点向量控制状态. 我们将基准方案的性能表现作为基准，测试与其相对的性能表现.
表 10 4种弱状态标签方案的实现Table 10. Implement of Four Weak State Label Schemes弱状态标签 基于代码块 基于指令 基础方案 BN IC 优化方案 BC ICF 代码块无链接方案（block no-linking，BN）；代码块检测方案（block checking，BC）；指令检测方案（instruction checking，IC）；指令融合检测方案（instruction checking fusion，ICF）. 图21展示了基于代码块的弱状态标签方案的性能表现. 基础方案禁止了某些情况下的代码块链接，因此造成了严重的性能损失，根据测试结果，整数性能下降为78%，而浮点性能更是下降为55%. 因为浮点测试含有更多的浮点向量指令，因此有更多的代码块链接情况会被禁止，所以性能损失严重. 而大部分整数测试没有浮点向量指令，因此性能几乎不受影响. 优化方案下，整数性能97%，浮点性能99%，性能损失便非常低了.
![]()
图 21 基于代码块的弱状态标签方案性能测试Figure 21. Performance testing of code block-based weak state label scheme图22展示了基于指令的弱状态标签方案的性能表现. 基础方案下整数性能91%，可见翻译代码块执行中的动态检测开销远低于代码块链接被禁止所带来的开销. 以整数测试175为例，其浮点向量指令并不多，因此动态检测开销不算高，但在禁止部分代码块链接时性能损失非常严重. 此外，浮点性能仍降低为55%，因为浮点测试含有大量的浮点向量指令，所以有很高的动态检测开销. 而在优化方案下，整数性能为99%，浮点性能97%，性能损失也是非常低.
![]()
图 22 基于指令的弱状态标签方案性能测试Figure 22. Performance testing of instruction-based weak state label scheme针对浮点向量控制状态的弱状态标签方案，我们也在相同的环境配置下测试了该方案对SPEC CPU2000基准测试程序的冗余代码块消除情况. 由于测试均是用户程序，因此我们只统计了用户级翻译代码块的冗余消除情况. SPEC CPU2000通过控制输入数据集的大小来控制运行时间，但不同数据集使用的是同一个测试程序代码，因此从运行代码量的视角看来，小数据集与大数据集的差异并不大，因此我们基于test数据集进行测试和分析.
图23展示了弱状态标签方案的冗余消除效果. 图23上半为基准方案下冗余代码块的比例，平均来说，整数程序的冗余率为14%略高于浮点程序的冗余率13%. 整数程序中的最高冗余率为30%，而浮点程序最高为23%，这是因为只有包含定点指令的基本块才会产生冗余代码块，浮点测试包含大量的浮点向量指令，相对来说更不容易产生冗余. 图23下半为弱状态标签方案下总翻译代码块数与基准方案的总翻译代码块数的比值，平均来说，整数程序的代码块数量下降为86%，浮点测试的代码块数量下降为87%，这与基准方案中的非冗余代码块的比例基本一致，可见本文提出的弱状态标签方案充分发挥了作用，将冗余代码块全部消除.
总的来说，SPEC CPU2000这种处理器密集型程序在二进制翻译的运行环境中对代码块的翻译开销并不敏感，更容易受到动态运行时开销的影响. 测试结果表明，优化后的弱状态标签方案引入的运行时开销很低，仅有2%~3%.
6. 总结与展望
本文研究了系统级动态二进制翻译器的软件代码缓存，分析了指令语义模拟的状态标签方案，总结出状态标签对软件代码缓存管理带来的2类问题，即冲突问题和冗余问题. 冲突问题会导致重复的动态翻译开销，冗余问题会导致冗余的动态翻译开销. 针对这2类问题，提出了2种细粒度状态标签的代码缓存优化方法，分别是多状态代码缓存方案和弱状态标签方案，对于特定的客户机状态，解决由该状态导致的冲突问题和冗余问题. 测试结果表明，本文提出的方案可以减少代码块的翻译和刷新开销，有效降低了软件代码缓存管理的压力.
未来的工作包括2个方面：一方面是优化本文提出的方案. 对于多状态代码缓存，总容量一定时2类代码缓存的容量比例是一个关键参数，后续可以设计一个自适应算法进行动态调整. 对于弱状态标签，在不同的客户机架构和客户机系统下，定位哪种状态带来了冗余问题是十分关键的，后续可以设计一个自动化分析框架来进行冗余分析. 另一方面是进一步深入研究系统级动态二进制翻译器的软件代码缓存管理. 例如，相同的客户机可能会被多次启动和运行，后续可以研究一种软件代码缓存持久化方案，从而加快客户机系统的启动速度，提高系统运行效率.
作者贡献声明：牛根负责全文的设计和实现以及文章的撰写和修改；张福新提出实验设计和文章撰写的指导意见.
-
![]()
图 1 二进制翻译器的软硬件层次结构
Figure 1. Software/hardware hierarchy structure of binary translators
![]()
图 12 基于代码块的弱状态标签优化方案
Figure 12. Optimized scheme for code block-based weak state label
![]()
图 14 多状态缓存下的代码块分布：系统启动阶段
Figure 14. Code blocks distribution with multi-state code cache: system startup stage
![]()
图 15 多状态缓存下的代码块分布：系统运行阶段
Figure 15. Code block distribution with multi-state code cache: system running stage
![]()
图 16 特权代码缓存不同容量占比下代码块翻译次数
Figure 16. Translation number of code blocks with different capacity percentage of privileged code cache
![]()
图 17 Windows XP系统启动过程代码缓存相似率
Figure 17. Code cache similarity ratio on Windows XP startup system process
![]()
图 18 Windows XP启动过程代码缓存相似率变化曲线
Figure 18. Change curve of code cache similarity ratio on Windows XP startup process
![]()
图 21 基于代码块的弱状态标签方案性能测试
Figure 21. Performance testing of code block-based weak state label scheme
![]()
图 22 基于指令的弱状态标签方案性能测试
Figure 22. Performance testing of instruction-based weak state label scheme
表 1 指令语义模拟的因素
Table 1 Factors in Instruction Semantics Simulation
DBT 客户机状态 指令范围 用户级 单一 用户态 系统级 复杂 全部 
下载: 导出CSV
表 3 替换策略的比较
Table 3 Comparison of Replace Strategy
替换策略 复用率 碎片化 刷新操作 全刷新 低 无 简单 FIFO 高 无 复杂 粗粒度FIFO 较高 无 适中
下载: 导出CSV
表 5 冗余率示例
Table 5 Example of Redundancy Ratio
客户机代码块 翻译代码块 状态标签 宿主机指令 A A1 ST1 CS1 A2 ST2 CS1 A3 ST3 CS3 B B1 ST4 CS4 C C1 ST5 CS5
下载: 导出CSV
表 6 代码块链接情况分析
Table 6 Analysis of Code Block Link Cases
直接跳转 跳转情况 无需关心 A0*→A0*，A0*→A1*，A0*→B2* 允许 A1*→A1*，B2*→B2*，A1*→B2* 不允许 A1*→A0*，B2*→A0*，B2*→A1*
下载: 导出CSV
表 7 实验配置
Table 7 Experiment Configuration
系统层次结构 实验配置 客户机测试程序 系统启动、SPEC CPU2000 客户机操作系统/x86 Windows XP，Ubuntu 16.04 系统级DBT LATX-SYS 宿主机操作系统 Loongnix（Linux 4.19内核） 宿主机硬件平台 3A5000 LoongArch 处理器
下载: 导出CSV
表 8 代码缓存操作的对比
Table 8 Comparison of Code Cache Operations
统计类别 基准 多状态代码缓存 降低比例/% FIFO刷新次数 87 49 44 代码块
刷新总次数 563 491 319 041 43 用户级 399 310 319 041 20 特权级 164 181 0 100 代码块
翻译总次数 769 473 633 962 18 用户级 563 021 526 799 6 特权级 206 452 107 163 48
下载: 导出CSV
表 9 代码块冗余测试方案
Table 9 Testing Schemes for Code Block Redundancy
测试方案 冗余消除范围 基准 未消除 弱状态标签方案W1 针对用户级代码块 弱状态标签方案W2 针对所有的代码块
下载: 导出CSV
表 10 4种弱状态标签方案的实现
Table 10 Implement of Four Weak State Label Schemes
弱状态标签 基于代码块 基于指令 基础方案 BN IC 优化方案 BC ICF 代码块无链接方案（block no-linking，BN）；代码块检测方案（block checking，BC）；指令检测方案（instruction checking，IC）；指令融合检测方案（instruction checking fusion，ICF）.
下载: 导出CSV
-
[1] Fabrice B. QEMU: A fast and portable dynamic translator[C]//Proc of the 2005 USENIX Annual Technical Conference (USENIX ATC 05). Anaheim, CA: USENIX Association, 2005: 41−46
[2] 胡伟武,汪文祥,吴瑞阳,等. 龙芯指令系统架构技术[J]. 计算机研究与发展,2023,60(1):2−16 doi: 10.7544/issn1000-1239.202220196 Hu Weiwu, Wang Wenxiang, Wu Ruiyang, et al. Loongson Instruction Set Architecture Technology[J]. Journal of Computer Research and Development, 2023, 60(1): 2−16 (in Chinese) doi: 10.7544/issn1000-1239.202220196
[3] Kim H, Michael D S. Code cache management schemes for dynamic optimizers[C]//Proc of the 6th Annual Workshop on Interaction between Compilers and Computer Architectures. Piscataway, NJ: IEEE, 2002: 92−100
[4] Kim H, Michael D S. Managing bounded code caches in dynamic binary optimization systems[J]. ACM Transactions on Architecture and Code Optimization, 2006, 3(3): 263−294 doi: 10.1145/1162690.1162692
[5] 马舒兰. 动态二进制翻译中的TCache替换算法[J]. 计算机应用与软件,2008,25(4):273−275 doi: 10.3969/j.issn.1000-386X.2008.04.105 Ma Shulan. TCache replacement algorithm for dynamic binary translation[J]. Computer Applications and Software, 2008, 25(4): 273−275(in Chinese) doi: 10.3969/j.issn.1000-386X.2008.04.105
[6] 王楠,单征,岳峰. I386到Alpha动态二进制翻译中的代码缓存管理优化[J]. 信息工程大学学报,2010,11(6):688−691 doi: 10.3969/j.issn.1671-0673.2010.06.010 Wang Nan, Shan Zheng, Yue Feng. Optimization in code cache management from I386 to Alpha in dynamic binary translation[J]. Journal of Information Engineering University, 2010, 11(6): 688−691(in Chinese) doi: 10.3969/j.issn.1671-0673.2010.06.010
[7] 殷金彪,宋强. 动态二进制翻译器 QEMU 的 Tcache 管理策略[J]. 计算机应用与软件,2012,29(9):98−100 doi: 10.3969/j.issn.1000-386x.2012.09.026 Yin Jinbiao, Song Qiang. TCache management schemes for dynamic binary translator QEMU[J]. Computer Applications and Software, 2012, 29(9): 98−100 (in Chinese) doi: 10.3969/j.issn.1000-386x.2012.09.026
[8] 徐金龙,蒋烈辉,董卫宇,等. 动态二进制翻译缓存的分区管理机制研究[J]. 计算机工程,2012,38(2):60−62 doi: 10.3969/j.issn.1000-3428.2012.02.019 Xu Jinlong, Jiang Liehui, Dong Weiyu, et al. Research on division management mechanism of dynamic binary translation cache[J]. Computer Engineering, 2012, 38(2): 60−62(in Chinese) doi: 10.3969/j.issn.1000-3428.2012.02.019
[9] Apala G, Kim H, Mary S. Balancing memory and performance through selective flushing of software code caches[C/OL]//Proc of the 2010 Int Conf on Compilers, Architectures and Synthesis for Embedded Systems. New York: ACM 2010[2024-11-11]. https://dl.acm.org/doi/10.1145/1878921.1878923
[10] Kim H, Michael D S. Characterizing inter-execution and inter-application optimization persistence[C]//Proc of the 17th Annual Int Conf on Supercomputing Workshop on Exploring the Trace Space for Dynamic Optimization Techniques. New York: ACM, 2003: 51−58
[11] Vijay J R, Dan C, Robert S C. Persistence in dynamic code transformation systems[J]. ACM SIGARCH Computer Architecture News, 2005, 33(5): 69−74 doi: 10.1145/1127577.1127591
[12] Vijay J R, Dan C, Robert C, et al. Persistent code caching: Exploiting code reuse across executions and applications[C]//Prof of the 5th Int Symp on Code Generation and Optimization. Piscataway, NJ: IEEE, 2007: 74−88
[13] Derek B, Vladimir K. Process-shared and persistent code caches[C]//Proc of the 4th ACM SIGPLAN/SIGOPS Int Conf on Virtual Execution Environments. New York: ACM, 2008: 61−70
[14] Wang Wenwen, Yew P C, Zhai A, et al. A general persistent code caching framework for dynamic binary translation (DBT)[C]//Proc of the 2016 USENIX Conf on USENIX Annual Technical Conference (USENIX ATC '16). Berkeley, CA: USENIX Association, 2016: 591−603
[15] Lin Haoming, Dong Yong, Chi Wanqing, et al. Efficient dynamic binary translation with accumulative persistent code caching[C]//Proc of the 28th Int Conf on Parallel and Distributed Systems (ICPADS). Piscataway, NJ: IEEE, 2023: 458−466
[16] Vasanth B, Evelyn D, Sanjeev B. Dynamo: A transparent dynamic optimization system[J]. ACM SIGPLAN Notices, 2000, 35(5): 1−12 doi: 10.1145/358438.349303
[17] Derek B, Saman A. Maintaining consistency and bounding capacity of software code caches[C]//Proc of the 3rd Int Symp on Code Generation and Optimization. Piscataway, NJ: IEEE, 2005: 74−85
[18] Ma Ruhui, Guan Haibing, Zhu Erzhou, et al. Code cache management based on working set in dynamic binary translator[J]. Computer Science and Information Systems, 2011, 8(3): 653−671 doi: 10.2298/CSIS100327022M
[19] Deng Fei, Gao Feng, Yan Yuanqiang, et al. Research on code cache management strategy based on code heat in dynamic binary translator[C]//Proc of the 18th Int Conf on Software Quality, Reliability and Security Companion (QRS-C). Piscataway, NJ: IEEE, 2018: 647−651
[20] Chen Wei, Shen Li, Lu Hongyi, et al. A light-weight code cache design for dynamic binary translation[C]//Proc of the 15th Int Conf on Parallel and Distributed Systems. Piscataway, NJ: IEEE, 2009: 120−125
[21] Chen Wei, Wang Zhiying, Lu Hongyi, et al. A hardware approach for reducing interpretation overhead[C]//Proc of the 9th Int Conf on Computer and Information Technology. Piscataway, NJ: IEEE, 2009: 98−103
[22] Jose A B, Bruce R C. Heterogeneous code cache: using scratchpad and main memory in dynamic binary translators[C]//Proc of the 46th ACM/IEEE Design Automation Conference. Piscataway, NJ: IEEE, 2009: 744−749
[23] Hsieh A C, Liu C C, Hwang T T. Enhanced heterogeneous code cache management scheme for dynamic binary translation[C]//Proc of the 16th Asia and South Pacific Design Automation Conf (ASP-DAC 2011). Piscataway, NJ: IEEE, 2011: 231−236
[24] Filipe S, Tiago G, Adriano T, et al. A hardware-assisted translation cache for dynamic binary translation in embedded systems[C]//Proc of the 23rd Int Conf on Emerging Technologies and Factory Automation (ETFA). Piscataway, NJ: IEEE, 2018: 307−312
[25] 李战辉,刘畅,孟建熠,等. 基于高速缓存负荷均衡的动态二进制翻译研究[J]. 计算机研究与发展,2015,52(9):2105−2113 doi: 10.7544/issn1000-1239.2015.20140220 Li Zhanhui, Liu Chang, Meng Jianyi, et al. Cache load balancing oriented dynamic binary translation[J]. Journal of Computer Research and Development, 2015, 52(9): 2105−2113 (in Chinese) doi: 10.7544/issn1000-1239.2015.20140220
[26] Jose A B, Bruce R C, Jack W D, et al. Fragment cache management for dynamic binary translators in embedded systems with scratchpad[C]//Proc of the 2007 Int Conf on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '07). New York: ACM, 2007: 75−84
[27] Apala G, Kim H, Mary L S. Reducing exit stub memory consumption in code caches[C]//Proc of the 2nd Int Conf on High performance embedded architectures and compilers (HiPEAC'07). Berlin: Springer, 2007: 87−101
[28] José A B, Bruce R C, Jack W D, et al. Reducing pressure in bounded DBT code caches[C]//Proc of the 2008 Int Conf on Compilers, Architectures and Synthesis for Embedded Systems (CASES '08). New York: ACM, 2008: 109−118
[29] Apala G, Kim H, Mary L S. DBT path selection for holistic memory efficiency and performance[C]//Proc of the 6th ACM SIGPLAN/SIGOPS Int Conf on Virtual Execution Environments (VEE '10). New York: ACM, 2010: 145−156
[30] 刘畅,陈志坚,孟建熠,等. 利用控制流识别进行二进制翻译代码缓存压缩[J]. 计算机辅助设计与图形学学报,2014,26(6):999−1006 Liu Chang, Chen Zhijian, Meng Jianyi, et al. Compress DBT code cache using control flow identification[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(6): 999−1006 (in Chinese)
[31] Wang Zhaoguo, Liu Ran, Chen Yufei, et al. COREMU: A scalable and portable parallel full-system emulator[J]. ACM SIGPLAN Notices, 2011, 46(8): 213−222 doi: 10.1145/2038037.1941583
[32] Ding Jiun-Hung, Chang Po-Chun, Hsu Wei-Chung, et al. PQEMU: A parallel system emulator based on QEMU[C]//Proc of the 17th Int Conf on Parallel and Distributed Systems. Piscataway, NJ: IEEE, 2011: 276−283
[33] Emilio G C, Paolo B, Alex B, et al. Cross-ISA machine emulation for multicores[C]//Proc of the 15th Int Symp on Code Generation and Optimization. Piscataway, NJ: IEEE, 2017: 210−220
[34] Emilio G C, Luca P C. Cross-ISA machine instrumentation using fast and scalable dynamic binary translation[C]//Proc of the 15th ACM SIGPLAN/SIGOPS Int Conf on Virtual Execution Environments (VEE 2019). New York: ACM, 2019: 74−87
[35] 胡伟武. 共享存储系统结构[M]. 北京:高等教育出版社,2001:55−73 Hu Weiwu. Shared Memory Architecture[M]. Beijing: Higher Education Press, 2001: 55−73 (in Chinese)
计量
- 文章访问数: 26
- HTML全文浏览量: 0
- PDF下载量: 4
