2023, Vol. 32
以QEMU[1]为代表的系统模拟器通过模拟CPU、内存、外设等硬件资源创建一个完整的虚拟计算机环境, 支持运行和调试不同架构的软件. 模拟器在芯片设计和验证阶段被广泛使用, 相比各类硬件仿真平台具有明显的速度优势, 这主要得益于其高度抽象的实现方式: 在模拟一个目标设备时, 模拟器可以根据需要对其行为进行抽象建模并实现. 例如, QEMU忽略了CPU的部分微架构实现, 仅对指令集的语义进行建模, 大大加快模拟速度的同时保证了上层软件的跨架构运行, 能够显著缩短跨架构的软件开发周期[2, 3].
模拟器的调试模块通常具有指令追踪功能, 可记录程序运行的指令序列以用于进一步分析. 例如: (1)通过统计指令序列中各类型指令的数目粗略评估程序的实际运行时间; (2)通过程序各时间段的基本块采样分析程序的行为模式[4,5]; (3)通过对程序热点片段的标记和提取进行软硬件的联合仿真等. 利用模拟器准确和高效地对目标程序进行指令追踪, 是进行各类分析的基础. 在硬件层面, 芯片通常会提供硬件性能计数器、追踪和调试模块等机制帮助用户进行性能分析[6], 模拟器的调试和追踪模块是对相应硬件抽象模拟, 从而实现跨架构的性能分析. 在软件层面, 可利用插桩技术(如Intel Pin[7]和DynamoRIO[8,9]等)实现指令追踪和性能分析, 相比之下, 模拟器的指令追踪无需修改程序, 不受硬件平台的限制, 可在芯片设计初期实现跨指令集架构的模拟运行. 本文拟研究基于模拟器的程序指令级的追踪和分析. 在系统层面, 用户可利用OpenTracing[10], OpenTelemetry[11]等技术对分布式系统中的各组件进行追踪和性能监测.
近年来, RISC-V架构[12]凭借其精简、开放、模块化的设计和高可定制的特点在工业界和教育界广受欢迎. 面向RISC-V的处理器接连问世, 支持RISC-V的系统模拟器也被广泛使用, 如Spike[13], QEMU[1]等. 本研究实现了基于QEMU的高效指令追踪, 并面向RISC-V架构实现了多种基于指令序列的分析.
1.2 研究现状支持RISC-V架构的模拟器QEMU和Spike均具备指令追踪功能. Spike是专门面向RISC-V架构的模拟器, 能够模拟一个或多个硬件线程. 相较于其他模拟器, Spike更专注于对RISC-V指令集的准确模拟, 而非对多架构以及各类设备的虚拟化, 常作为参考模型用于芯片的测试和验证. Spike支持追踪程序执行的指令信息, 它会将模拟的硬件线程号、指令地址、指令编码及反汇编信息按照指令执行的顺序记录下来, 以供用户分析.
QEMU是一个面向多种架构的开源模拟器和虚拟机管理工具, 通过动态二进制翻译机制模拟不同的指令集架构. QEMU会按块翻译、缓存和执行目标架构的代码, 并支持将翻译和执行过程中处理的指令地址、编码和反汇编信息以日志的形式输出.
Spike受限于自身的模拟速度和日志记录方式, 其指令追踪功能相比QEMU的要慢很多. 图1对比了在模拟NPB基准套件中的bt.S.x时二者的时间(详细实验配置见第5.1节). 可以看出, 在该目标应用下Spike的模拟效率仅为QEMU的30%, 开启指令追踪后效率更是不足QEMU的3%.
|
图 1 比较QEMU和Spike的指令追踪效率 |
虽然QEMU的指令追踪效率优于Spike, 但仍然无法应对较长的指令序列, 如某些大型软件或循环次数较多的基准测试程序. 仍以bt.S.x为例, 在数据规模仅为S(数组大小仅为12×12×12)的情况下, QEMU在开启指令追踪后的模拟时间变为2.5倍, 记录的日志文件高达300 MB, 这并不利于后续基于指令序列的各类分析.
1.3 需求与挑战通过分析和实践, 我们认为用户对于模拟器的指令追踪功能有至少以下3点需求: (1)序列完整. 指令序列的正确性和完整性是后续分析的基础, 指令追踪应支持记录程序从开始到结束的完整指令序列; (2)信息多元. 用户对于指令序列分析的需求是多样的, 但所需的信息各不相同. 例如, 指令分类统计需要记录指令的类型和频次, 程序热点分析需要记录指令的地址和频次, 而程序的行为分析需要记录不同执行阶段的指令序列; (3)执行高效. 指令追踪的时间开销和空间开销要在可接受的范围内, 尤其是空间开销, 如果指令序列占用空间过大将不利于后续的分析.
开发满足需求的指令追踪功能面临的主要挑战是: 难以在保证指令序列完整性和信息多元性的同时降低时间和空间开销. 按需进行指令追踪能够一定程度降低开销, 例如, 当用户只需统计指令数目时, 模拟器无需为其提供完整的指令序列, 只需要统计指令频次, 这将大大降低空间开销. 然而, 指令追踪应按需提供多种信息而无需为各类应用单独开发不同的指令追踪程序. 为特定的应用场景开发特定的指令追踪方法难以适应用户多样化的分析需求.
1.4 基于QEMU的高效指令追踪技术本研究提出了一种基于QEMU模拟器的指令追踪技术, 将程序中的基本块、控制流图等静态信息与分支选择等动态信息解耦, 在保证指令序列不失真的同时高效追踪执行序列. 相比QEMU原生实现的指令追踪, 本文提出的指令追踪技术的时间开销平均降低了80%以上, 空间开销平均降低了95%以上. 此外, 本文面向RISC-V架构, 实现了多种场景下的指令序列离线分析, 包括指令分类统计、程序热点标记、行为模式分析等. 对于不同的序列分析, 可按需还原指令序列, 降低分析开销.
本文第2节简要介绍了QEMU原生的指令追踪实现, 包括块翻译机制、日志系统和插件机制. 第3节介绍了一种基于信息解耦的高效指令追踪技术. 第4节介绍了技术的具体实现. 第5节介绍了实验设计、结果以及案例分析. 第6节进行了总结.
2 QEMU指令追踪QEMU原生的指令追踪[14]可以基于块翻译和日志系统实现. 例如, 通过开启“in_asm, exec, nochain”调试选项, 可以翻译块为单位记录指令信息以及目标程序的PC序列, 经过处理可还原出完整的指令序列.
2.1 块翻译机制QEMU的高效模拟得益于其块翻译机制, 它以程序的基本块为单位, 通过在两种架构之间建立TCG (tiny code generator)翻译层, 将目标架构的指令翻译成宿主机指令. TCG可分为前端和后端, 前端将目标架构的指令翻译成中间表示(TCG IR), 后端再将TCG IR翻译成宿主机的指令. 图2展示了TCG翻译的流程示意. 与编译器类似, 将翻译过程分成前后端的优势在于: (1)服务于目标架构的前端翻译和面向宿主机架构的后端翻译可以独立实现, 避免前后架构的组合爆炸; (2) TCG IR不与任何指令集架构相关, 将通用的优化技术应用于TCG IR, 各个架构都将从中受益.
|
图 2 TCG代码翻译示意 |
QEMU以基本块为单位翻译代码. 当QEMU第1次翻译一段代码时, 会将连续的目标指令翻译成宿主机指令, 直到遇见跳转指令才停止翻译. 翻译得到的代码块被称作翻译块(translation block, TB).
QEMU将翻译好的TB缓存并用哈希表进行维护. 在每次执行完一个TB时, QEMU根据需要执行的下一个PC值在哈希表中查找对应的TB并加载运行. 为了降低查表的开销, QEMU在TB之间建立链接, 使得一个TB执行后, 直接跳转并执行下一个TB, 而无需查找TB. 这些链接在一起的TB被称为扩展的翻译块. TB的缓存技术和链接技术大大提高了QEMU的模拟性能.
2.2 日志系统QEMU内部具有功能强大的日志系统, 支持记录TB的执行顺序、指令反汇编、中断等. 通过分析QEMU产生的日志信息, 开发人员可以了解应用程序的运行行为, 快速定位缺陷. 表1 给出了QEMU支持的常用日志类型. QEMU的日志信息由各自独自的开关管理, 在启动时通过调试选项开启一个或多个日志类型.
2.3 插件机制QEMU提供了插件机制以观察记录目标程序的运行, 可在启动时通过动态链接库的形式加载运行一个或多个插件. 通过插件, 用户可在QEMU模拟运行目标程序的多个阶段(如CPU实例化、执行、TB翻译、系统调用等)注册回调函数, 分析提取感兴趣的信息. 例如, 可在TB执行阶段注册插件函数, 根据作为参数传入的TB信息分析记录TB包含的指令数目、指令类型、TB的执行次数等. 该函数会在TB的执行阶段被调用, 伴随TB的每次执行而执行. 利用QEMU的插件机制可以实现指令级别的观测记录.
|
表 1 QEMU常用日志类型 |
插件的实现独立于QEMU内部的模拟执行, 并且只能观测、分析和记录QEMU暴露的信息(如TB), 无法修改机器状态, 保证了程序的模拟执行不受影响.
3 基于信息解耦的指令追踪方法 3.1 解耦静态基本块信息和动态指令序列程序中的基本块[15]指的是一段连续的代码, 程序的执行只能从基本块的第1条语句进入, 从基本块的最后一条语句离开. 图3展示了一个简单的基于基本块的控制流图. 如果基本块的第1条指令被执行, 则后续的指令必然被执行, 换言之, 程序运行结束后, 一个基本块内所有指令的执行次数是相同的. 基于以上性质, 指令追踪只需记录基本块的ID, 后续根据每个基本块的指令信息即可还原完整的指令序列. 例如, 通过记录序列“B0-B1-B4”并通过后续解析这3个基本块内部的指令序列即可按需还原完整的指令序列. 该方法的核心思想是: 解耦静态的基本块信息和动态的指令序列, 加快指令追踪的过程, 后续按需还原指令序列, 可大大降低指令追踪的时间和空间开销.
3.2 解耦静态控制流图和动态分支选择通过分析发现, 在控制流图[15]中存在部分基本块仅有一个出边(即指向其他基本块的边), 例如图3中的B1, B2和B3. 对于仅有一个出边的基本块, 当其被执行时, 其唯一后继的基本块一定被执行, 记录其后继的基本块信息是冗余的. 例如, 对于执行序列“B0-B2-B3-B4”, B2的执行必然伴随着B3和B4的执行. 此外, B0作为入口基本块也必然被执行. 因此, 序列“B0-B2-B3-B4”可压缩为“B2”.
|
图 3 基于基本块的控制流图示意 |
上述方法的核心思想是: 将静态的控制流图与动态的分支选择解耦, 仅记录程序在运行至分支点时的选择(即具有一个以上出边的基本块), 后续通过遍历控制流图对序列进行还原.
3.3 面向需求的指令序列还原通过前文介绍的两种信息解耦技术, 指令序列分为静态和动态两部分信息分别记录. 静态信息包括程序的控制流图、各个基本块的指令信息等; 动态信息包括程序执行的分支选择. 通过遍历控制流图并根据记录的分支选择序列恢复完整的基本块序列, 并可进一步通过检索基本块信息还原完整的指令序列. 然而, 并非所有的后续分析都需要完整的指令序列, 为了提高序列分析的效率, 可按需对指令序列进行还原. 图4展示了上述流程的示意图.
|
图 4 指令序列的追踪与分析流程示意图 |
以热点片段提取为例, 用户希望将程序中执行频率较高的片段提取出来, 图5展示了如何通过记录的序列还原提取需要的信息. 首先, 根据记录的仅包含分支信息的序列“B1-B1”以及左侧的控制流图对基本块序列进行还原. 自起始基本块B0开始, 沿着图中的边依次搜索, 当遇到具有一个以上出边的基本块时(如B3), 在记录的分支选择序列中依次选择对应的基本块(如B1), 直至还原出基本块序列. 实际上, 该应用无需维护基本块的执行顺序, 仅记录执行频率即可, 尤其无需对基本块包含的指令信息进行展开. 经过简单统计, 可以得出各基本块的执行频次, 之后可根据需要筛选出热点片段.
|
图 5 热点片段提取分析流程示意 |
可见, 该过程是按需对指令序列进行还原, 一次指令追踪的结果可支持多种离线的指令序列分析.
4 基于QEMU的指令追踪实现实现上述指令追踪技术有两个关键点: (1)控制流图和基本块等静态信息的生成; (2)动态分支选择序列的记录. 在本研究中, 上述操作均基于QEMU的插件机制实现.
4.1 控制流图生成QEMU的块翻译和块链接机制自然构成了程序的控制流图. 依托于QEMU的插件机制, 在TB翻译时注册函数记录控制图的节点信息, 在TB执行时注册函数记录TB的跳转信息作为控制流图的边信息. 当程序运行结束时, 通过记录的节点信息和边信息构造出程序的控制流图. 此外, 为了方便频次统计, 在输出控制流图时将各个基本块的执行频次也一并输出.
与传统的控制流图的不同之处在于: (1) QEMU建立的TB及其链接是动态建立的, 相当于在静态控制流图的基础上进行了动态切片. 由于用户对于未被运行的代码并不感兴趣, 该特性并不妨碍指令序列的跟踪; (2) TB有别于传统基本块的定义. 传统的基本块是静态建立的, 能够确定程序不会跳转到基本块中间, 而TB的建立是动态的, 一般是从第1条语句一直到分支或跳转语句, 此刻无法确定程序之后不会跳转到基本块中间. 图6 展示一个简单的循环体建立TB的过程, 涉及的3条指令中第1条为变量初始化(PC为0x10), 后两条为循环的主体(PC为0x14和0x18). 当第1次块翻译时, TB1被建立, 3条指令均被包含在内. 当执行到0x18时, 程序产生分支跳转, 目标地址为0x14, 此时并不存在起始位置为0x14的基本块, QEMU新建了TB2, 包含0x14和0x18两条指令, 之后再次跳转到0x14时, 存在起始位置为0x14的基本块TB2, 并不会新建TB. 可见, TB的概念与基本块并不完全一致, TB之间可能存在重叠的区域(如TB1和TB2). 然而, 含有重叠的TB并不会影响控制流图的建立和指令追踪的正确性. 例如, 序列“TB0-TB1-TB2”记录的是真实的指令序列. 需要注意的是, 当统计程序热点区域时, 需要对重叠的部分重复计数, 例如0x14–0x18这一区域的执行频次应该由TB1和TB2的频次相加.
|
图 6 循环体建立TB的过程示意 |
4.2 基本块信息提取
通过在TB翻译阶段注册插件函数, 可记录TB的ID、PC、指令条数、指令反汇编等信息. 该过程仅在TB的首次翻译时进行, 每个TB只执行一次, 不受动态执行次数的影响.
4.3 序列记录程序的执行序列指的是TB的执行序列. 虽然静态控制流图已经包含了所有的TB节点和TB间的跳转信息, 但是缺少了程序执行的动态分支选择. 当TB可跳转至多个TB时, 需要按顺序记录其每一次的分支选择. 由于控制流图是动态建立的, 在程序运行结束之前无法确定TB是否存在一个以上的跳转目标, 因此需要暂时记录完整的TB序列, 待程序运行完毕后, 只需线性扫描控制流图中的TB, 输出分支处选择的TB而忽略其他TB.
5 实验与结果 5.1 实验环境本研究中的代码基于QEMU v7.2, 采用插件的形式实现. 实验基于RISC-V用户态QEMU开展, 实验平台采用Intel Core i7-9750H处理器, 内存16 GB, 运行Ubuntu 20.04. 图表绘制基于gnuplot[16]实现.
实验测试程序选取自常用的基准测试, 包括Dhrystone[17]、whetstone[18]以及NPB[19]. 其中, Dhrystone的循环次数为106, whetstone循环次数为105, NPB采取串行版本中的S和W规模. 程序均由RISC-V的gcc工具链编译, 目标指令为RV64GC.
5.2 实验结果表2 给出了基于常用基准测试的指令追踪实验结果. 其中, 本研究所生成的日志文件包括静态和动态信息两部分, 其中静态控制流图输出为JSON格式, 动态指令序列输出为二进制文件, 每个基本块ID由32位整型表示, 表2中所列日志大小是二者相加的结果.
|
|
表 2 基于常用基准测试的指令追踪实验结果 |
对比QEMU原生的指令追踪实现, 本研究提出的指令追踪技术在运行时间和日志空间占用上均有明显的提升, 其中运行时间平均仅为QEMU原生实现的17.0% (3.6%–44.0%), 日志空间占用平均仅为3.7% (1.7%–4.9%). 值得注意的是, 在本实验环境下程序dc.W.x未在可接受的时间内基于原生实现完成指令追踪, 手动结束运行时其日志大小超过2 TB, 运行时间超过10 h.
为了预估在给定时间/空间限制下指令追踪的最大长度, 实验选取了部分耗时较长的测试统计了时间/空间开销和指令序列长度的关系. 图7给出了指令序列长度与运行时间的关系. 整体上, 二者为线性正相关, 各用例的时间增长率因其热点片段的指令特点不同而有所差异. 例如, 对于ep.S.x每记录108条指令耗时约2 s, 而ua.S.x耗时约1 s. 图8给出了指令序列长度与日志空间的关系. 类似地, 二者为线性正相关, 各用例的日志空间增长率因其热点片段的基本块大小等因素而有所差异(见第3.1节). 例如, 对于ep.S.x每记录108条指令占用25 MB, 而cg.S.x需要50 MB. 此外, 由于程序起始和结束阶段的行为区别于热点区域(见第5.5节), 时间和空间开销的规律可能也有所不同.
|
图 7 指令序列长度与运行时间的关系 |
|
图 8 指令序列长度与日志空间的关系 |
5.3 热点标记
基于bt.S.x的指令追踪结果进行热点基本块的提取(方法参见图5), 可根据基本块执行频率迅速定位程序的热点区域. 经分析, 函数binvchr包含了执行频次最高的几个基本块(执行频次20000以上). 图9 展示了bt.S.x的热点区域的汇编代码. 由于该应用无需对完整的指令序列进行分析, 仅统计基本块频次即可, 分析过程仅耗时1 s.
5.4 指令统计基于bt.S.x的指令追踪结果进行指令统计并绘制直方图(图10). 其中, 横轴是指令的频次, 纵轴是高频指令的名称(由RV64GC组成). 经统计, 该程序以浮点运算为主, 使用频次最高的指令是双精度乘减取反指令(fnmsub.d).
该应用与热点片段提取类似(参见图5), 无需考虑指令的相对顺序, 可通过先统计基本块频次和基本块中各指令的频次, 二者相乘即可得到指令统计信息. 由于该应用可按需恢复指令序列, 无需对完整的指令序列进行分析, 分析和绘制过程仅耗时1 s.
|
图 9 bt.S.x热点区域汇编代码 |
|
图 10 基于bt.S.x指令序列的指令统计 |
5.5 行为分析
按照指令序列的先后顺序, 标记执行的基本块, 有助于分析程序运行过程中的行为模式. 该过程可通过区间采样和聚类算法进一步分析[4,5]. 进行基本块序列恢复过程仅耗时2 s, 图表绘制需要额外40 s.
图11给出了程序在执行各个阶段的基本块分布, 其中横轴为程序执行的指令数(截取了前3.5×107条指令), 纵轴为基本块ID (按照频次选取前300个基本块). 经过分析可见, 程序运行起始阶段的行为与后续有所不同, 起始阶段可能在进行程序的初始化, 后续阶段是有规律的循环运行某一任务.
5.6 问题与不足本研究存在4点问题需要进一步改进: (1)虽然本研究所提技术相比QEMU原生实现在时间和空间效率上均有明显提升, 但对于超大型应用程序依旧无能为力, 未来可通过限定跟踪范围(通过目标程序前后插入全局符号或限定PC值)对部分程序片段进行指令跟踪; (2)暂未实现多核处理器的指令序列跟踪, 该功能未来可通过增加线程ID将指令序列按线程记录; (3)暂未考虑指令动态更新. 如果在程序运行中代码段被修改(如Linux Kernel中的动态指令注入), 目前的实现无法对前后的TB进行区分. 未来可通过保存更新前后的TB进行优化; (4)实验基于QEMU用户态模拟器, 并未跟踪系统调用的指令序列. 通常, 用户仅对系统调用号感兴趣, 未来可通过补充系统调用号进一步完善指令序列追踪. 追踪系统调用的具体指令序列, 可使用QEMU全系统模拟器.
|
图 11 基于bt.S.x指令序列的程序行为分析 |
6 总结
本研究提出了一种基于QEMU的高效指令追踪技术, 通过动态和静态信息解耦的方式对指令序列进行高效的记录. 实验表明, 本研究提出的指令追踪技术相比QEMU的原生实现, 时间开销平均降低了80%以上, 空间开销平均降低了95%以上. 此外, 本研究面向RISC-V实现了多种指令序列分析应用. 实验表明, 基于生成的静态和动态信息可高效地按需还原指令序列满足不同分析的需求.
| [1] |
Bellard F. QEMU, a fast and portable dynamic translator. Proceedings of the 2005 Annual Conference on USENIX Annual Technical Conference. Anaheim: USENIX Association, 2005. 41.
|
| [2] |
徐学政, 王涛, 方健, 等. 面向RISC-V的汇编程序语义等价性自动化测试系统. 计算机系统应用, 2021, 30(11): 33-40. DOI:10.15888/j.cnki.csa.008348 |
| [3] |
刘阳, 汪丹, 方林伟, 等. 基于RISC-V的数据安全指令. 计算机系统应用, 2023, 32(1): 392-398. DOI:10.15888/j.cnki.csa.008896 |
| [4] |
Weaver VM, McKee SA. Using dynamic binary instrumentation to generate multi-platform simpoints: Methodology and accuracy. Proceedings of the 3rd International Conference on High Performance Embedded Architectures and Compilers. Göteborg: Springer, 2008. 305–319.
|
| [5] |
Sherwood T, Perelman E, Hamerly G, et al. Automatically characterizing large scale program behavior. ACM SIGPLAN Notices, 2002, 37(10): 45-57. DOI:10.1145/605432.605403 |
| [6] |
Matraszek M, Banaszek M, Ciszewski W, et al. FrankenTrace: Low-cost, cycle-level, widely applicable program execution tracing for ARM cortex-M SoC. Proceedings of the 2023 Cyber-physical Systems and Internet of Things Week. San Antonio: Association for Computing Machinery, 2023. 72–77.
|
| [7] |
Patil H, Cohn R, Charney M, et al. Pinpointing representative portions of large Intel® Itanium® programs with dynamic instrumentation. Proceedings of the 37th International Symposium on Microarchitecture. Portland: IEEE, 2004. 81–92.
|
| [8] |
Bruening DL, Amarasinghe S. Efficient, transparent, and comprehensive runtime code manipulation [Ph.D. Thesis]. Cambridge: Massachusetts Institute of Technology, 2004.
|
| [9] |
Bruening D, Amarasinghe S. Maintaining consistency and bounding capacity of software code caches. Proceedings of the 2005 International Symposium on Code Generation and Optimization. San Jose: IEEE, 2005. 74–85.
|
| [10] |
OpenTracing. https://opentracing.io/. (2023-03-23)[2023-03-29].
|
| [11] |
Boten A, Majors C. Cloud-native Observability with OpenTelemetry. Birmingham: Packt Publishing, 2022. 42–45.
|
| [12] |
RISC-V规范. https://github.com/riscv/riscv-isa-manual. (2023-03-21)[2023-03-29].
|
| [13] |
Spike simulator. https://github.com/riscv/riscv-isa-sim. (2023-03-16)[2023-03-29].
|
| [14] |
Velea R, Togan M. Instruction tracing and application profiling with QEMU. MTA Review, 2017, 27(2): 73-76. |
| [15] |
Aho AV, Lam MS, Sethi R, et al. Compilers: Principles, Techniques, and Tools. 2nd ed., Addison-Wesley Pub., 2006.
|
| [16] |
Williams T, Kelley C. gnuplot: An interactive plotting program. http://www.gnuplot.info/docs_4.0/gnuplot.html. (1998-12-03).
|
| [17] |
Weicker RP. Dhrystone: A synthetic systems programming benchmark. Communications of the ACM, 1984, 27(10): 1013-1030. DOI:10.1145/358274.358283 |
| [18] |
Curnow HJ, Wichmann BA. A synthetic benchmark. The Computer Journal, 1976, 19(1): 43-49. DOI:10.1093/comjnl/19.1.43 |
| [19] |
Bailey DH, Barszcz E, Barton JT, et al. The NAS parallel benchmarks. Technical Report, Moffett Field: NASA, 1991.
|