基于QEMU的Tcache管理策略.pdf

Computer Era No.12 20230 引言QEMU 是一款广泛使用的虚拟机软件，它支持多种体系结构和操作系统。其中，动态二进制翻译技术是QEMU的核心功能之一，它可以将一个体系结构下的二进制程序翻译成另一个体系结构下的二进制程序，并且在目标体系结构上执行。图 1 为 QEMU翻译流程。图1QEMU翻译流程QEMU的动态二进制翻译技术具有广泛的应用，包括将已经存在的程序移植到新的体系结构上，以及在不同的体系结构之间进行程序分析和优化。它可以克服不同体系结构之间的差异，可以在不同的平台上运行相同的程序，并且可以进行程序优化和分析1-2。但是，QEMU 的动态二进制翻译技术也存在性能损失、内存占用、指令准确性等问题。本文主要研究Tcache在二进制翻译中所起的作用。1 Tcache简介1.1 Tcahce作用Tcache是动态二进制翻译器中的软件代码缓存系统，它可以将已经翻译过的基本代码块存储起来，以便源程序可以轻松的从Tcache中查找，而无需重新DOI:10.16644/33-1094/tp.2023.12.033基于QEMU的Tcache管理策略*杨云1，姜佳乐1，王静1，高浏洋1，吴亚男2(1.陕西科技大学，陕西 西安 710000；2.西安计量技术研究院)摘要：QEMU是一款广泛使用的虚拟机软件，它通过Tcache对代码进行调整与控制，改善其性能。对Tcache的特性进行了详尽的研究，主要涉及命中时间、缺失率和缺失代价。引入二进制翻译系统中常用的几种替换算法，如全清空和先进先出方法，并研究了各种算法不同的技术特性。最后结合profile技术以及先进先出、全清空算法，提出一种全新的Tcache替换算法。通过修改算法前后测试nbench，迭代次数较修改前提高了很多。关键词：QEMU；Tcache；全清空；先进先出；profile技术中图分类号：TN432文献标识码：A文章编号：1006-8228(2023)12-153-05Tcache management strategy based on QEMUYang Yun1,Jiang Jiale1,Wang Jing1,Gao Liuyang1,Wu Yanan2（1.Shaanxi University of Science&Technology,Xian,Shannxi 710000,China;2.Xian Research Institute of Metrology and Technology）Abstract：QEMU is a widely used virtual machine software that adjusts and controls code through Tcache to improve itsperformance.In this paper,the characteristics of Tcache such as hit time,missing rate and missing cost are studied in detail.Several substitution algorithms commonly used in the binary translation system such as full emptying and FIFO methods areintroduced,and the different technical characteristics of various algorithms are investigated.A new Tcache substitution algorithm isproposed by combining profile technology,FIFO and full emptying algorithms.By testing nbench before and after modifying thealgorithm,the number of iterations has increased significantly compared to before the modification.Key words：QEMU;Tcache;fully emptying;first in first out(FIFO);profile technology收稿日期：2023-08-29*基金项目：国家自然科学基金资助项目（No61971272，N.61601271）；国家重点研发重点专项(No 2019YFC1520204)作者简介：杨云（1965-），女，陕西西安人，博士，教授，主要研究方向：图像处理和数据挖掘。通讯作者：姜佳乐（1999-），女，陕西西安人，硕士研究生，主要研究方向：嵌入式系统和图像处理。153计算机时代 2023年 第12期翻译，它的功能使得源程序可以快速、准确地完成翻译任务，因此Tcache的使用有效的减少了代码翻译的时间开销和程序运行时间，从而极大地提高了程序的运行效率3-4。1.2 Tcache特点在计算机系统中，CPU会使用硬件Cache来提高读取数据的效率。当CPU需要访问某个数据时，它首先会在硬件缓存中寻找，如果找到了对应的数据，那么CPU就可以直接读取，从而避免了从内存中读取数据所造成的时间浪费。反之，如果在硬件缓存中没有找到需要的数据，那么CPU就会从内存中读取，并将其所在的数据块存储在缓存中，以便未来快速访问。这样可以大大提高计算机系统的读取效率，减少读取操作对系统性能的影响5。Tcache存在的意义和硬件Cache一样，都是为了提高效率的问题。Tcache可以将翻译后的优化代码以块的形式存储，这使得它与硬件Cache相比，具有更多的独特性6，从而更好地满足用户的需求。Tcache 存储的代码是一次性的，由于 Tcache容量的局限性，无法存放一个程序的完整代码块，如果某一个块被替换掉或者Tcache全部内容被清空时，下次执行到这块代码的时候就需要重新翻译，然后才能执行。Tcache的每个指针都与其所指向的块存在着密切的关联，因此，当某个模块被移除时，其对应的连接指针也必须随之发生变化，这样一来，频繁的更新代码块将会增加指针操作的次数，从而增加系统的运行成本，造成更大的开销。Tcache中存储的代码块其大小是不固定的，而是根据需要翻译的目标块的大小而定。这是因为不同的目标代码块大小对于翻译的速度和效率都有不同的影响。因此，Tcache采用了动态调整的方式，使得其能够根据当前需要翻译的代码块大小来灵活地调整自己的存储空间大小，以达到更好的翻译效果和速度。通过这种方式，Tcache能够提高翻译效率，并减少翻译过程中的资源浪费。1.3 Tcahce性能Tcache的存在主要就是为了提高运行速度和代码执行的效率，对于硬件Cache来讲，衡量其性能可以通过以下公式来进行衡量7。平均存储器访问时间：平均存储器访问时间=命中时间+缺失率*缺失代价我们也可以使用次公式来判断Tcache的性能。平均代码块访问时间：平均代码块访问时间=命中时间+缺失率*缺失代价我们将从命中时间、缺失率和缺失代价三个因素来分析它们与性能之间的关系。命中时间Tcache 花费的时间主要由 Tcache 的大小以及Tcache 代码块的数据结构决定，数据结构即就是Tcache映射表的组织方式。一般情况下，Tcache的大小越大，那么可存储的优化翻译代码块就会越多，但是Tcache的增大导致映射表的表项也增多，在查找代码块的过程中，会增大查找的开销，造成命中时间增大，所以并不是Tcache越大越好。在数据结构的选择中，一般会选取高效的数据结构来存储代码块，能够减少查找的开销，通常情况下会选取哈希表来存储代码块，以内存地址作为关键字，通过给定的关键字的值直接访问到具体对应的内容。缺失率通常来讲，Tcache存储空间越大，缺失率越低，如果Tcache可以无限制的存储代码块，那每段代码被执行的时候，只有在第一次访问会缺失，其他任何时候，都可以在 Tcache 中找到，这样会使得缺失率达到最低。但是Tcache的存储量不能是无限制的，Tcache的存储量过大会导致命中时间变长，从而也会影响Tcache的性能，同时也会占用太多的内存空间。所以在确定了 Tcache 的大小后，选择合适的替换算法是Tcache中的一个重要决策，因为这能够有效地减少缺失率。而最优的替换算法可以保证Tcache中始终存储着当前正在执行的源代码块，这可以避免重复的优化操作并提高程序的执行效率。缺失代价缺失代价是指执行代码中Tcache缺失的情况下，需要花费大量的时间和精力来重新翻译和优化代码块，并且还需要考虑基本块指针的变化所带来的开销。并不是每次缺失都会发生替换，例如程序最开始进行时，所有的代码块都是第一次执行，在缓存中并没有所对应的代码块，但是此时缓存的存储足够大，所以并不会发生替换，只有当缓存存储发生溢出时，才会进行代码替换，产生替换过程中的开销。1.4 Tcache替换算法替换算法在Tcache中起着重要的作用，一个好的替换算法能够尽可能的保证执行频率高的代码块不154Computer Era No.12 2023被替换出去，从而降低代码块的缺失率。每次替换的代码块的替换粒度也影响着Tcache的性能，如果替换粒度过小，虽然降低了缺失率但是会造成频繁的替换次数，每次替换都会都固定的开销。但是如果替换粒度过大，虽然替换的次数减少了但是会导致缺失率增加。所以，为了使Tcache的性能足够的好，我们需要从各个方面考虑，对其的替换算法进行改进。全清空全清空算法，即Flushing，这个方法也是较为常见的，能够一次性清空全部 Tcache，它的操作方式非常简洁同时操作的时候开销也非常低，它可以避免因替换代码块而产生的大量碎片，但是这种算法由于替换粒度很大而造成Tcache的缺失率过高，需要频繁的去翻译优化代码，从而使得它的性能受到严重的影响，而且在每次替换过程中，可能会重复替换热路径，从而造成不必要的资源浪费，也无法达到优化热路径以提升程序执行速度的目的8。先进先出先进先出算法，即 FIFO，这种算法的思想是，当Tcache空间不足的时候，每次被替换掉的总是最开始的块，如果被插入的块的大小为 n，但是被替换掉的块的大小不足n，即将下一个块继续被替换出去，依次类推，直至将新块可以插入进去。这种替换方式避免了过多的碎片产生，但是由于替换的粒度比较小，每次指针更新的代价比较高，并且没有考虑到热路径的问题，有可能会将频繁执行的代码替换出去。2 QEMU的Tcache管理策略2.1 QEMU的Tcache简介在QEMU中，目前支持三种替换算法：随机替换、最近最少使用和先进先出9。图2为Tcache替换流程图。随机替换，是当存储空间不够时，每次随机的从Tcache中选择一块替换出去，因为这种替换算法的原理简单且没有考虑到代码访问的一个内部原理，所以导致命中率降低。最近最少使用，在每次代码块执行中，我们要标记每个块被执行到的次数，当存储空间不够时将执行次数最少的块替换出去。这种算法虽然考虑到了将热度高的代码留在Tcache中，但算法实现起来比较复杂，花费的时间比较多。先进先出，该算法是当存储空间不够时将最先进来的代码替换出去，这种算法避免了碎片产生，但是每次指针更新代价过高。图2Tcache替换流程图2.2 替换算法的改进 基于基本块的Profile热路径识别热路径识别在Profile中有多种实现方式，包括基于基本块、基于边和基于路径等。然而，在替换算法中，我们通常采用基于基本块的热路径识别来优化。这是因为基本块是程序执行过程中最基本的模块，是程序中的最小执行单位。通过对基本块进行热路径识别，我们可以快速地确定程序的热点，即经常执行的代码块。这有助于我们更好地管理缓存中的数据，从而提高程序的执行效率。因此，在替换算法中，我们使用基于基本块的热路径识别来进行优化，以保证程序的高效执行。所以在这里只对基于基本块做详细介绍。通过基本块的热路径识别，可以有效地提高程序的效率和可靠性。首先，我们可以通过设定一个阈值，来判断某个代码块是否为热代码块，当代码块的执行次数超过阈值时，就可以认为当前的代码块已经足够热，从而可以有效地提高程序的效率和可靠性10。改进算法针对QEMU所采取的具体的改进的算法如下：首先我们先设定一个阈值，用来判断代码的执行次数。然后QEMU给Tcache分配两块大小为32M的空间，并给这两块空间设置一个标记分别为T1，T2。T1用来存储新的代码块，将T1分成大小相等的n段，给每一段标记一个起始位置，这样每个段的起始和结束位置都可以计算出来。当 T1 中代码块的执行次数达到我们设定的阈值时，将代码块放入T2中，记录这两个块的起始位置和结束位置，然后给这两块空间设置当前的位置，用来表示当前Tcache中代码存储到了那个155计算机时代 2023年 第12期位置，当程序开始执行的时候，判断该代码的大小是否小于T1剩余的空间，剩余空间用结束位置减去当前位置，如果小于就默认空间足够，就可以将翻译后的代码放入T1，否则就认为当前的剩余空间不足够，就要进行代码块替换。替换的原则是，对T1采取粗粒度的先进先出，即就是块内全清空，块间先进先出，对T1进行粗粒度的替换原因是因为T1存储的并不是热代码，为了减少指针的管理开销，所以采取粗粒度替换。当T1中热代码过多，T2中不能存放时，对T2进行先进先出算法替换，如果T2替换出去的代码所占空间小于新增的代码空间，那么将下一个相邻的代码也替换出去，依次进行，直到新代码可以存储为止，对T2进行小粒度的替换原因是减少热代码的缺失率。算法流程图如图3所示。图3算法流程图2.3 算法的优缺点改进后的算法在每次替换时，不需要遍历整个Tcache，相较于 QEMU中的随机替换来讲，这种算法注重代码的内部原理，提高了命中率，相较于最近最少使用算法来讲，这种算法节省了遍历时间，并且没有最近最少使用实现复杂，算法的实现对程序来讲也是至关重要的。相较于先进先出算法来讲，这种算法将代码做了分类，提高命中率，粗粒度的替换减少了管理开销。相较于全齐全清空算法，这种算法降低了出错率。算法的一些缺陷在于，当要添加的块的大小超过替换块的大小时，T1会删除与其相连的下一个块，导致当前可用空间没有被充分利用，产生小碎片。而对于T2，为了减少热代码的缺失率，需要额外增加一定的指针管理开销。这些缺陷都会对算法的性能产生一定的影响。3 系统结果和性能分析本实验是在上 Intel(R)Xeon(R)Gold 6133上使用QEMU实现了ARM系统的虚拟，通过修改QEMU源码，测试nbench的运行效果如表1所示。在实验过程中，采用的配置如下：处理器 Intel(R)Xeon(R)Gold 6133、主频2.5GHz,操作系统是Ubuntu。表1测试nbench的运行效果TESTNUMERIC SORTSTRING SORTBITFIELDFP EMULATIONFP EMULATIONASSIGNMENTIDEAHUFFMANNEURAL NETLU DECOMPOSITIONOldIterations/sec.1323.41496.66.3095e+08619.585325353.945110325057.267.9092536.7New Iterations/sec.1323.61496.76.41e+08619.825325554.103110365058.367.9352538.6从表1测试结果可以看出，相对于修改前，修改后的迭代次数较之前提高了很多。4 结束语Tcache的设计旨在提高内存分配和释放的性能，以减少堆管理的开销。关于优化Tcache管理策略可选择以下几种优化思路：调整Tcache的容量大小：可以根据应用程序的内存使用情况来设置 Tcache 的容量大小。如果Tcache的容量太小，会导致频繁的内存分配和释放，从而降低性能；如果Tcache的容量太大，会占用过多的内存。调整 Tcache的预填充数量：Tcache在程序启动时会预先填充一定数量的空闲块。可以通过环境变量调整预填充数量。如果预填充数量过小，会导致频繁的内存分配和释放，从而降低性能；如果预填充数量过大，会占用过多的内存。调整 Tcache的释放阈值：Tcache的释放阈值是指当Tcache中的空闲块数超过一定数量时，就会释放一部分空闲块。如果释放阈值过小，会导致频繁的156Computer Era No.12 2023内存释放，从而降低性能；如果释放阈值过大，会占用过多的内存。调整 Tcache的分配算法：Tcache默认使用的是先进先出（FIFO）算法。但是，对于一些特殊场景，如实时系统等，可能需要使用其他算法。可以通过编写自定义的malloc/free函数来实现不同的分配算法。避免频繁的内存分配和释放：频繁的内存分配和释放会导致Tcache频繁地进行空闲块的填充和释放，从而降低性能。可以通过重用已分配的内存块，避免频繁的内存分配和释放。总之，Tcache的管理策略需要根据具体应用场景来调整。需要根据实际情况，进行实验和测试，才能找到最优的Tcache管理策略。参考文献(References):1 Daz Edel,Mateos Ral,Bueno Emilio J.,Nieto Rubn.Enabling Parallelized-QEMU for Hardware/Software Co-Simulation Virtual PlatformsJ.Electronics,2021,10(6).2 Wang Jun,Pang Jianmin,Liu Xiaonan,Yue Feng,Tan Jie,FuLiguo.Dynamic Translation Optimization Method Basedon S is Pre-TranslationJ.IEEE ACCESS,2019,7.3 Koltunov D.S.,Efimov V.Yu.,Padaryan V.A.AutomatedTesting of a TCG Frontend for QemuJ.Program-ming and Computer Software,2020,46(8).4 Koltunov D.S.,Efimov V.Y.,Padaryan V.A.Automatedtesting of a TCG frontend for QemuJ.Proceedingsof the Institute for System Programming of the RAS,2018,28(5).5 马舒兰.动态二进制翻译中的TCache替换算法J.计算机应用与软件,2008(4):273-275.6 Smith J E,Ravi N.Virtual machines:versalite platforms forsystemsandprocesseM.BeijingPublishingHouseofElectronics Industry,2006:133-139.7JohnL.Hennessy,DavidA.Patterson,ComputerArchitecture:A Quantitative Approach,pp.257-298.8 殷金彪,宋强.动态二进制翻译器qemu的Tcache管理策略J.计算机应用与软件,2012,29(9):98-100.9 James E.Smith,James R.Goodman,A Study of InstructionOrganizations and Replacement Polices.ACM,1983.10 李男,庞建民,单征.一种基于频度统计的动态二进制翻译优化方法J.计算机工程与科学,2018,40(4):602-60.要的知识点、查缺补漏、依规循矩的自主学习愿望，也可快速、方便、合理地组卷实现课程考核的目的。4 结束语试题库的建设还需要不断的优化和深入拓展。首先是知识点覆盖面，根据教学大纲的要求，习题应涵盖课程的基本章节；其次是重点要突出、难度要适当，应以专业基本技能的培养为主线。还要注重试题库界面的可视化、参数化建设，提高学生学习的自主性，以便更好的赋能教学的全过程。参考文献(References):1 高长铎.可视化编程应用Visual Basic 6.0M.第三版.北京:人民邮电出版社,2018,8:1-12.2 赵元哲.数据库技术与应用教程数据库基础、Access与Visual BASIC 开发应用M.西安:西安电子科技大学出版社,2016:103-118.3 关慧贞.机械制造装备设计M.第四版.北京:机械工业出版社,2014:目录页,81.4 张晓.机械传动系统转速图的可视化设计系统开发J.机械工程师,2015(2):71-72.(上接第152页)CECE157