基于QEMU的Tcache管理策略

摘" 要： QEMU是一款廣泛使用的虛擬機軟件，它通過Tcache對代碼進行調整與控制，改善其性能。對Tcache的特性進行了詳盡的研究，主要涉及命中時間、缺失率和缺失代價。引入二進制翻譯系統中常用的幾種替換算法，如全清空和先進先出方法，并研究了各種算法不同的技術特性。最后結合profile技術以及先進先出、全清空算法，提出一種全新的Tcache替換算法。通過修改算法前后測試nbench，迭代次數較修改前提高了很多。

關鍵詞： QEMU； Tcache； 全清空； 先進先出； profile技術

中圖分類號：TN432" " " " " 文獻標識碼：A" " "文章編號：1006-8228（2023）12-153-05

Tcache management strategy based on QEMU

Yang Yun1， Jiang Jiale1， Wang Jing1， Gao Liuyang1， Wu Yanan2

（1. Shaanxi University of Science amp; Technology， Xi'an， Shannxi 710000， China; 2. Xi'an Research Institute of Metrology and Technology）

Abstract： QEMU is a widely used virtual machine software that adjusts and controls code through Tcache to improve its performance. 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 are introduced， and the different technical characteristics of various algorithms are investigated. A new Tcache substitution algorithm is proposed by combining profile technology， FIFO and full emptying algorithms. By testing nbench before and after modifying the algorithm， 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

0 引言

QEMU是一款廣泛使用的虛擬機軟件，它支持多種體系結構和操作系統。其中，動態二進制翻譯技術是QEMU的核心功能之一，它可以將一個體系結構下的二進制程序翻譯成另一個體系結構下的二進制程序，并且在目標體系結構上執行。

QEMU的動態二進制翻譯技術具有廣泛的應用， 包括將已經存在的程序移植到新的體系結構上，以及在不同的體系結構之間進行程序分析和優化。它可以克服不同體系結構之間的差異，可以在不同的平臺上運行相同的程序，并且可以進行程序優化和分析[1-2]。但是，QEMU的動態二進制翻譯技術也存在性能損失、內存占用、指令準確性等問題。本文主要研究Tcache在二進制翻譯中所起的作用。

1 Tcache簡介

1.1 Tcahce作用

Tcache是動態二進制翻譯器中的軟件代碼緩存系統，它可以將已經翻譯過的基本代碼塊存儲起來，以便源程序可以輕松的從Tcache中查找，而無需重新翻譯，它的功能使得源程序可以快速、準確地完成翻譯任務，因此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中起著重要的作用，一個好的替換算法能夠盡可能的保證執行頻率高的代碼塊不被替換出去，從而降低代碼塊的缺失率。每次替換的代碼塊的替換粒度也影響著Tcache的性能，如果替換粒度過小，雖然降低了缺失率但是會造成頻繁的替換次數，每次替換都會都固定的開銷。但是如果替換粒度過大，雖然替換的次數減少了但是會導致缺失率增加。所以，為了使Tcache的性能足夠的好，我們需要從各個方面考慮，對其的替換算法進行改進。

⑴ 全清空

全清空算法，即Flushing，這個方法也是較為常見的，能夠一次性清空全部Tcache，它的操作方式非常簡潔同時操作的時候開銷也非常低，它可以避免因替換代碼塊而產生的大量碎片，但是這種算法由于替換粒度很大而造成Tcache的缺失率過高，需要頻繁的去翻譯優化代碼，從而使得它的性能受到嚴重的影響，而且在每次替換過程中，可能會重復替換熱路徑，從而造成不必要的資源浪費，也無法達到優化熱路徑以提升程序執行速度的目的[8]。

⑵ 先進先出

先進先出算法，即FIFO，這種算法的思想是，當Tcache空間不足的時候，每次被替換掉的總是最開始的塊，如果被插入的塊的大小為n，但是被替換掉的塊的大小不足n，即將下一個塊繼續被替換出去，依次類推，直至將新塊可以插入進去。這種替換方式避免了過多的碎片產生，但是由于替換的粒度比較小，每次指針更新的代價比較高，并且沒有考慮到熱路徑的問題，有可能會將頻繁執行的代碼替換出去。

2 QEMU的Tcache管理策略

2.1 QEMU的Tcache簡介

在QEMU中，目前支持三種替換算法：隨機替換、最近最少使用和先進先出[9]。圖2為Tcache替換流程圖。①隨機替換，是當存儲空間不夠時，每次隨機的從Tcache中選擇一塊替換出去，因為這種替換算法的原理簡單且沒有考慮到代碼訪問的一個內部原理，所以導致命中率降低。②最近最少使用，在每次代碼塊執行中，我們要標記每個塊被執行到的次數，當存儲空間不夠時將執行次數最少的塊替換出去。這種算法雖然考慮到了將熱度高的代碼留在Tcache中，但算法實現起來比較復雜，花費的時間比較多。③先進先出，該算法是當存儲空間不夠時將最先進來的代碼替換出去，這種算法避免了碎片產生，但是每次指針更新代價過高。

2.2 替換算法的改進

⑴ 基于基本塊的Profile熱路徑識別

熱路徑識別在Profile中有多種實現方式，包括基于基本塊、基于邊和基于路徑等。然而，在替換算法中，我們通常采用基于基本塊的熱路徑識別來優化。這是因為基本塊是程序執行過程中最基本的模塊，是程序中的最小執行單位。通過對基本塊進行熱路徑識別，我們可以快速地確定程序的熱點，即經常執行的代碼塊。這有助于我們更好地管理緩存中的數據，從而提高程序的執行效率。因此，在替換算法中，我們使用基于基本塊的熱路徑識別來進行優化，以保證程序的高效執行。所以在這里只對基于基本塊做詳細介紹。

通過基本塊的熱路徑識別，可以有效地提高程序的效率和可靠性。首先，我們可以通過設定一個閾值，來判斷某個代碼塊是否為熱代碼塊，當代碼塊的執行次數超過閾值時，就可以認為當前的代碼塊已經足夠熱，從而可以有效地提高程序的效率和可靠性[10]。

⑵ 改進算法

針對QEMU所采取的具體的改進的算法如下：首先我們先設定一個閾值，用來判斷代碼的執行次數。然后QEMU給Tcache分配兩塊大小為32M的空間，并給這兩塊空間設置一個標記分別為T1，T2。T1用來存儲新的代碼塊，將T1分成大小相等的n段，給每一段標記一個起始位置，這樣每個段的起始和結束位置都可以計算出來。當T1中代碼塊的執行次數達到我們設定的閾值時，將代碼塊放入T2中，記錄這兩個塊的起始位置和結束位置，然后給這兩塊空間設置當前的位置，用來表示當前Tcache中代碼存儲到了那個位置，當程序開始執行的時候，判斷該代碼的大小是否小于T1剩余的空間，剩余空間用結束位置減去當前位置，如果小于就默認空間足夠，就可以將翻譯后的代碼放入T1，否則就認為當前的剩余空間不足夠，就要進行代碼塊替換。替換的原則是，對T1采取粗粒度的先進先出，即就是塊內全清空，塊間先進先出，對T1進行粗粒度的替換原因是因為T1存儲的并不是熱代碼，為了減少指針的管理開銷，所以采取粗粒度替換。當T1中熱代碼過多，T2中不能存放時，對T2進行先進先出算法替換，如果T2替換出去的代碼所占空間小于新增的代碼空間，那么將下一個相鄰的代碼也替換出去，依次進行，直到新代碼可以存儲為止，對T2進行小粒度的替換原因是減少熱代碼的缺失率。算法流程圖如圖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測試結果可以看出，相對于修改前，修改后的迭代次數較之前提高了很多。

4 結束語

Tcache的設計旨在提高內存分配和釋放的性能，以減少堆管理的開銷。關于優化Tcache管理策略可選擇以下幾種優化思路：

⑴ 調整Tcache的容量大小：可以根據應用程序的內存使用情況來設置Tcache的容量大小。如果Tcache的容量太小，會導致頻繁的內存分配和釋放，從而降低性能；如果Tcache的容量太大，會占用過多的內存。

⑵ 調整Tcache的預填充數量：Tcache在程序啟動時會預先填充一定數量的空閑塊。可以通過環境變量調整預填充數量。如果預填充數量過小，會導致頻繁的內存分配和釋放，從而降低性能；如果預填充數量過大，會占用過多的內存。

⑶ 調整Tcache的釋放閾值：Tcache的釋放閾值是指當Tcache中的空閑塊數超過一定數量時，就會釋放一部分空閑塊。如果釋放閾值過小，會導致頻繁的內存釋放，從而降低性能；如果釋放閾值過大，會占用過多的內存。

⑷ 調整Tcache的分配算法：Tcache默認使用的是先進先出（FIFO）算法。但是，對于一些特殊場景，如實時系統等，可能需要使用其他算法。可以通過編寫自定義的malloc/free函數來實現不同的分配算法。

⑸ 避免頻繁的內存分配和釋放：頻繁的內存分配和釋放會導致Tcache頻繁地進行空閑塊的填充和釋放，從而降低性能。可以通過重用已分配的內存塊，避免頻繁的內存分配和釋放。

總之，Tcache的管理策略需要根據具體應用場景來調整。需要根據實際情況，進行實驗和測試，才能找到最優的Tcache管理策略。

參考文獻（References）：

[1] Díaz Edel， Mateos Raúl， Bueno Emilio J.， Nieto Rubén.

Enabling Parallelized-QEMU for Hardware/Software Co-Simulation Virtual Platforms[J]. Electronics，2021，10（6）.

[2] Wang Jun，Pang Jianmin，Liu Xiaonan，Yue Feng，Tan Jie，Fu

Liguo.Dynamic Translation Optimization Method Based on S is Pre-Translation[J]. IEEE ACCESS，2019，7.

[3] Koltunov D. S.，Efimov V. Yu.，Padaryan V. A.. Automated

Testing of a TCG Frontend for Qemu[J]. Programming and Computer Software，2020，46（8）.

[4] Koltunov D.S.，Efimov V.Y.，Padaryan V.A.. Automated

testing of a TCG frontend for Qemu[J]. Proceedings of 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 for

systems and processe[M].Beijing Publishing House of Electronics Industry，2006：133-139.

[7] John L.Hennessy， David A.Patterson， Computer

Architecture：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 Instruction

Organizations and Replacement Polices. ACM，1983.

[10] 李男，龐建民，單征.一種基于頻度統計的動態二進制翻譯

優化方法[J].計算機工程與科學，2018，40（4）：602-60.