基于地址空間標識符的QEMU動態(tài)跳轉(zhuǎn)優(yōu)化①

位金弈, 梁洪亮

(北京郵電大學 計算機學院, 北京 100876)

1 引言

指令集架構(gòu)仿真技術(shù)能夠在缺少對應硬件設備的情況下輔助完成相關(guān)軟件的開發(fā)和測試工作, 以及方便硬件設計者更早地對設計方案進行評估. 以近年來新興的RISC-V[1]指令集架構(gòu)和開源領(lǐng)域主流的指令集架構(gòu)仿真器QEMU[2]為例, RISC-V指令集中對應向量指令的V擴展[3]和對應硬件加速虛擬化的H擴展[4]等指令擴展模塊均是先在QEMU中以0.x版本進行實現(xiàn), 經(jīng)過軟硬件磨合迭代到1.0版本后才由RISC-V基金會批準并正式寫入指令集規(guī)范.

隨著硬件技術(shù)的不斷演進和軟件需求的持續(xù)增長,人們對仿真器的執(zhí)行性能也提出了更高的要求. 間接跳轉(zhuǎn)的處理方式是決定仿真器執(zhí)行效率的關(guān)鍵因素[5],特別是在全系統(tǒng)仿真的場景下, 目標架構(gòu)處理器的虛擬內(nèi)存功能允許跳轉(zhuǎn)目標的物理地址在運行時動態(tài)變化, 這一特性為仿真器正確和高效地實現(xiàn)間接跳轉(zhuǎn)和跨頁直接跳轉(zhuǎn)(后統(tǒng)稱為動態(tài)跳轉(zhuǎn))的語義帶來了許多挑戰(zhàn).

本文分析了仿真目標架構(gòu)支持虛擬內(nèi)存的場景中QEMU翻譯塊間跳轉(zhuǎn)機制的不足, 并結(jié)合常見虛擬內(nèi)存模型的特點提出了基于地址空間標識符的動態(tài)跳轉(zhuǎn)改進方案. 該方案將地址翻譯從動態(tài)跳轉(zhuǎn)執(zhí)行的關(guān)鍵路徑中移除, 在保證正確解析跳轉(zhuǎn)目標的前提下提升仿真執(zhí)行性能. 本文在QEMU主線6.2.0版本中實現(xiàn)了這一方案, 并以RISC-V架構(gòu)的操作系統(tǒng)xv6-riscv[6]為例對方案的有效性進行評估, 實驗結(jié)果表明, 改進后的QEMU在8個測試程序中實現(xiàn)了約12%的平均運行性能提升.

2 QEMU的現(xiàn)有翻譯塊間跳轉(zhuǎn)機制

為了避免重復的取指譯碼開銷, QEMU使用動態(tài)二進制翻譯技術(shù), 以基本塊為單位將目標架構(gòu)的匯編指令翻譯成對應的宿主機指令并進行緩存, 由此得到的仿真執(zhí)行單元被稱為翻譯塊(translation block). 系統(tǒng)仿真模式下, 執(zhí)行流在翻譯塊間的轉(zhuǎn)移分為3類: 頁內(nèi)直接跳轉(zhuǎn)、間接跳轉(zhuǎn)和跨頁直接跳轉(zhuǎn).

2.1 頁內(nèi)直接跳轉(zhuǎn)

對通過直接跳轉(zhuǎn)連接的目標架構(gòu)基本塊而言, 其對應的翻譯塊擁有固定的前驅(qū)后繼關(guān)系. 作為優(yōu)化,QEMU通過翻譯塊直接鏈接的方式將前驅(qū)翻譯塊的退出操作重定向到后繼翻譯塊的入口處, 以消除后續(xù)執(zhí)行中動態(tài)查找后繼翻譯塊的運行時開銷.

該機制借助QEMU的中間表示(intermediate representation, IR)指令goto_tb和exit_tb完成. 以64位RISC-V架構(gòu)為例, 當允許翻譯塊直接鏈接時, QEMU的翻譯前端為直接跳轉(zhuǎn)生成的IR指令和對應的x86_64宿主機代碼示例如圖1所示.

圖1 直接跳轉(zhuǎn)IR序列在x86_64后端生成代碼舉例

翻譯塊tb首次執(zhí)行時, 執(zhí)行流將通過goto_tb對應的空跳轉(zhuǎn)指令, 更新程序計數(shù)器(PC)后經(jīng)exit_tb返回QEMU查找或生成后繼翻譯塊, 并將tb中對應分支的空跳轉(zhuǎn)指令重定向到后繼翻譯塊的宿主機指令入口處. 后續(xù)執(zhí)行翻譯塊tb時將在goto_tb處完成直接跳轉(zhuǎn), 不再更新PC或進行翻譯塊查找.

2.2 間接跳轉(zhuǎn)

間接跳轉(zhuǎn)的目標地址不能在QEMU進行指令翻譯時確定, 且在運行時有多種可能(如相同函數(shù)的不同返回地址和面向?qū)ο竽Ｊ街邢嗤惖牟煌摲椒ǖ?, 故無法使用翻譯塊直接鏈接的方式進行優(yōu)化, 需要借助運行時的翻譯塊查找機制確定當次跳轉(zhuǎn)的目標.這一查找過程涉及兩級翻譯塊緩存, 即: 1)以PC地址通過哈希直接映射方式索引的vCPU線程私有緩存數(shù)組tb_jmp_cache; 2)以翻譯塊的虛擬地址和物理地址等信息作為鍵的全局共享哈希表QHT[7,8], QHT緩存了由QEMU翻譯得到且依然有效的所有翻譯塊. 為了后續(xù)敘述的方便, 本文以H0和H2分別指代QEMU現(xiàn)有的兩級翻譯塊緩存, 前述查找過程的具體流程如圖2所示, 其中虛線框代表對應環(huán)節(jié)的輸入.

圖2 QEMU的翻譯塊查找流程

翻譯塊執(zhí)行間接跳轉(zhuǎn)時, 需要更新PC后再通過上述翻譯塊查找機制獲取跳轉(zhuǎn)目標翻譯塊的入口地址(調(diào)用輔助函數(shù)helper_lookup_tb_ptr), 并通過goto_ptr對應的宿主機間接跳轉(zhuǎn)指令完成跳轉(zhuǎn). 以64位RISC-V架構(gòu)為例, QEMU的翻譯前端為間接跳轉(zhuǎn)生成的IR指令和對應的x86_64宿主機代碼示例如圖3所示.

圖3 間接跳轉(zhuǎn)IR序列在x86_64后端生成代碼舉例

2.3 跨頁直接跳轉(zhuǎn)

跨頁直接跳轉(zhuǎn)擁有翻譯時可獲知的目標地址, 但其跳轉(zhuǎn)目標與當前基本塊位于目標架構(gòu)的不同虛擬內(nèi)存頁面上. 在全系統(tǒng)仿真模式下, 運行在QEMU中的特權(quán)軟件可以通過修改頁表等方式?jīng)Q定任意內(nèi)存頁的映射物理地址和訪問權(quán)限, 導致運行時跳轉(zhuǎn)目標發(fā)生變更, 這使得跨頁直接跳轉(zhuǎn)擁有了與間接跳轉(zhuǎn)類似的動態(tài)特性. 因此, QEMU保守地禁止對跨頁直接跳轉(zhuǎn)使用翻譯塊直接鏈接的優(yōu)化, 轉(zhuǎn)而使用與間接跳轉(zhuǎn)完全相同的動態(tài)查找機制完成跳轉(zhuǎn).

2.4 現(xiàn)有跳轉(zhuǎn)機制存在的不足

H0本身的查找開銷較低, 但其基于直接映射的組織方式使得緩存沖突的概率較大; 由于H0僅使用虛擬地址進行索引, QEMU必須在內(nèi)存映射發(fā)生改變時刷新H0以避免歧義. 上述因素導致翻譯塊查找的流程需要相對頻繁地訪問H2, 并使用物理地址確定跳轉(zhuǎn)的目標翻譯塊. 然而, QEMU中目標架構(gòu)地址翻譯過程本身所依賴的softTLB同樣不能在內(nèi)存映射改變后保持有效, 往往需要重新訪問softMMU獲取PC對應的物理地址. 因為QEMU不區(qū)分數(shù)據(jù)TLB與指令TLB, 仿真運行過程中由翻譯塊查找需求導致的地址翻譯還將與翻譯塊本身的數(shù)據(jù)讀寫操作爭用TLB, 帶來反復的頁表查詢開銷, 降低仿真執(zhí)行的效率.

另一方面, QEMU保守地使用運行時查找翻譯塊的方式確?？珥撝苯犹D(zhuǎn)的正確性. 單次翻譯塊查找的運行時開銷為數(shù)十條至數(shù)千條宿主機匯編指令(取決于H0和TLB是否命中), 且需要占用相應的緩存空間, 故代價遠高于頁內(nèi)直接跳轉(zhuǎn)(鏈接后通過單條宿主機跳轉(zhuǎn)指令即可完成). 而且, 對于任何稍具規(guī)模的軟件而言, 絕大多數(shù)由某一模塊發(fā)起, 以位于其他模塊中函數(shù)為目標的調(diào)用行為都會是跨越虛擬內(nèi)存頁面直接跳轉(zhuǎn), 且相關(guān)內(nèi)存映射在軟件的整個執(zhí)行過程中不會改變. 因此, 我們認為, 基于簡化程序執(zhí)行常見路徑的原則, 這一不足是有改進空間的.

3 觀察與討論

虛擬內(nèi)存是現(xiàn)代通用處理器的一項關(guān)鍵特性, 通過對內(nèi)存訪問進行抽象, 使特權(quán)軟件可以在運行時配置任意虛擬地址的映射內(nèi)存位置和訪問權(quán)限. 虛擬內(nèi)存機制的運作依賴軟硬件的配合, 包含以基數(shù)樹形式存在于內(nèi)存中的頁目錄、用于在頁目錄中查找虛擬地址對應映射描述條目的硬件單元MMU和用于緩存MMU查找結(jié)果的地址翻譯緩存TLB. 針對這一虛擬內(nèi)存的主流實現(xiàn)模型(單頁目錄、MMU、TLB), 關(guān)于虛擬內(nèi)存存在場景下內(nèi)存映射的不確定性對動態(tài)跳轉(zhuǎn)帶來的影響, 本文有以下3點觀察.

3.1 翻譯塊查找無需使用完整物理地址

為了區(qū)分虛擬地址相同而物理地址不同的翻譯塊,H2使用翻譯塊的物理地址輔助翻譯塊的索引和比對,而這也正是目前翻譯塊查找需要物理地址的原因. 對于前文提到的虛擬內(nèi)存的主流實現(xiàn)模型, 內(nèi)存映射完全由vCPU所使用的頁目錄(包含其下各級頁表)所決定, 因此我們可以嘗試為“頁目錄整體”建立一個地址空間標識符, 并將其作為額外的索引替代物理地址對翻譯塊進行標識, 免去查找時的地址翻譯開銷.

3.2 TLB刷新本身不涉及內(nèi)存映射內(nèi)部的改變

一般而言, TLB刷新只是為了迫使MMU重新訪問頁表, 使用更新后的頁目錄進行地址翻譯, 對頁目錄本身的修改或切換操作并不是由TLB刷新導致的. 但QEMU目前并不維護頁表頁相關(guān)的狀態(tài), 因而在TLB刷新后默認內(nèi)存映射可能發(fā)生任何變化, 無法區(qū)分地址空間的整體切換和局部修改. 一種改進方法是: 在仿真運行時監(jiān)測對頁目錄的寫入操作, 并據(jù)此修正已經(jīng)建立的地址空間標識符. 如果決定內(nèi)存映射的頁目錄在切換間隙未發(fā)生變化, 則之前運行過程中為其建立的地址空間標識符亦不需改變.

3.3 對頁目錄的監(jiān)測只需關(guān)注被使用過的部分

QEMU翻譯基本塊時, 需要首先根據(jù)當前PC進行地址翻譯以獲取取指使用的物理地址, 該過程會通過softMMU訪問當前頁目錄中的相關(guān)頁表頁. 另一方面,頁目錄中那些從未因指令地址翻譯的需求而被訪問的頁表頁可以被視為尚未加入當前地址空間, 對這些頁面的修改并不會影響該地址空間下翻譯塊查找的結(jié)果, 以及任何跨頁直接跳轉(zhuǎn)的有效性. 由此, 我們可以將監(jiān)測范圍局限于已生效的頁表頁, 從而消除主動探測頁目錄完整結(jié)構(gòu)所帶來的開銷. 當已生效頁表頁被修改時, 先前建立的地址空間標識符不再有效, 需要為其分配新的標識符以指代經(jīng)過內(nèi)部修改后得到的新地址空間.

4 基于地址空間標識符的動態(tài)跳轉(zhuǎn)機制

基于上述觀察與討論, 我們?yōu)镼EMU引入地址空間標識符的概念, 并對其動態(tài)跳轉(zhuǎn)處理機制進行優(yōu)化.

4.1 地址空間標識符的定義與維護

4.1.1 地址空間標識符的定義

本文使用頁目錄的物理頁號和一個單調(diào)遞增的版本號共同作為由該頁目錄所決定內(nèi)存映射的地址空間標識符. 版本號的值初始化為零, 并在每次檢測到頁目錄變化時增一以示區(qū)別. 在頁目錄部分相同的情況下,若vCPU線程記錄的地址空間標識符版本號高于先前存儲于某處的標識符版本號, 則說明對應地址空間的內(nèi)存映射在仿真運行期間發(fā)生了改變.

由此, 地址空間標識符提供了可用于區(qū)分不同內(nèi)存映射和檢測地址空間內(nèi)存映射是否發(fā)生改變的簡單機制. 在后續(xù)描述中, 將以QASID代指此處引入的地址空間標識符以簡化行文, 并區(qū)別于一般意義上的硬件ASID.

4.1.2 地址空間標識符的維護

與QEMU中代碼頁寫保護的建立過程類似, 我們采用如下方式對頁表頁進行寫保護: 維護新的物理頁狀態(tài)位圖DIRTY_MEMORY_PTE, 并在softMMU因為指令地址翻譯的需要而訪問各級頁表頁時標記此位圖中代表相應頁面的比特. 當QEMU為softTLB添加新的地址映射條目時, 將根據(jù)頁面在前述位圖中的狀態(tài)對應設置TLB表項的TLB_NOTDIRTY標志位, 從而截獲后續(xù)所有對受保護頁表頁的寫操作.

頁表頁修改導致的版本號更新代表著對相應舊QASID的棄用, 在一些情況下, 修改并不會影響對動態(tài)跳轉(zhuǎn)目標的解析, 作為這類場景中寫保護觸發(fā)時的剪枝優(yōu)化, 我們進一步做如下3點設計:

1)若被修改位置并非目標架構(gòu)中所規(guī)定的有效的頁表項, 則不需要更新版本號. 該方式可以過濾部分由動態(tài)內(nèi)存分配或進程按需調(diào)頁引起的頁表頁修改, 減少無謂的QASID棄用.

2)保護頁表頁時記錄頁目錄的版本號, 若寫保護發(fā)生時, 頁目錄版本號已經(jīng)大于先前記錄的版本號, 則不需要繼續(xù)作更新. 版本號不同代表先前內(nèi)存映射對應的QASID已被丟棄, 而新的內(nèi)存映射尚未包含該頁表頁.

3)目標架構(gòu)的有效頁表項被修改時, 立即取消對頁面的保護. 單個頁表項變化導致的內(nèi)存映射改變足以使原本的地址空間失效, 故其余的映射條目也不需要繼續(xù)被保護. 在原物理頁面不再作為頁表使用后, 該方法可以減少清空頁面導致的重復寫保護開銷.

4.1.3 vCPU線程對地址空間標識符的獲取

我們把vCPU當前使用的QASID作為vCPU線程私有數(shù)據(jù)存儲在vCPU的控制結(jié)構(gòu)中. 其中, 頁目錄物理頁號在目標軟件設置頁目錄(如寫入RISC-V 架構(gòu)中的SATP 寄存器)時同步作更新. 版本號在TLB刷新時設為非法值, 并按需從頁目錄的頁描述符PageDesc中獲取, 無需隨頁表頁修改而更新. 其原因在于TLB與頁表頁內(nèi)存的數(shù)據(jù)一致性是由軟件手動維護的, 而QASID作為對內(nèi)存映射的整體描述應具有相同的特性.

4.2 地址空間標識符在動態(tài)跳轉(zhuǎn)處理中的應用

4.2.1 間接跳轉(zhuǎn)

QASID唯一決定了當前的內(nèi)存映射, 因而可以在翻譯塊的查找過程中替換原本使用的物理地址, 以省去地址翻譯的開銷. 為此, 本文修改QEMU現(xiàn)有的兩級翻譯塊緩存結(jié)構(gòu), 引入另外一個借助QASID進行索引的共享翻譯塊緩存H1, 并在查找間接跳轉(zhuǎn)目標時優(yōu)先查詢該緩存.

H1亦基于QHT實現(xiàn), 其與H2的區(qū)別主要在于鍵值對的選取上. 對于鍵, 我們將H2中原本使用的物理地址替換為QASID的頁目錄物理頁號; 對于值, 我們把原本H2中指向翻譯塊的指針改為指向翻譯塊包裝的指針. 翻譯塊包裝(translation block wrapper)由翻譯塊指針和對應QASID構(gòu)成. 不在H1中直接插入翻譯塊的原因是翻譯塊可能被多個地址空間所共享, 此時單一的翻譯塊數(shù)據(jù)結(jié)構(gòu)無法存儲多個QASID, 因而基于哈希表的查找也就無從談起. 引入修改后QEMU對翻譯塊間接跳轉(zhuǎn)目標的查找流程如圖4所示.

查找H1的過程不涉及版本號信息, 因而在命中后還需要與vCPU中記錄的QASID版本號進行比對. 版本號相等代表內(nèi)存映射未發(fā)生改變, 視為翻譯塊查找命中, 而版本號不相等的場景可以分為3類, 其中(1)和(2)對應圖4中檢查版本號不通過的情形, 需要進一步根據(jù)物理地址查詢H2以判斷跳轉(zhuǎn)目標是否發(fā)生改變.

圖4 引入哈希表H1后的間接跳轉(zhuǎn)目標查找流程

(1)翻譯塊包裝版本號小于vCPU版本號, 但H2中使用物理地址查找到相同的翻譯塊——說明地址空間的內(nèi)存映射發(fā)生改變, 但并未影響當前跳轉(zhuǎn)的目標地址, 因此我們只需更新翻譯塊包裝中的版本號信息.

(2)翻譯塊包裝版本號小于vCPU版本號, 且H2中使用物理地址未查找到或查找到不同的翻譯塊——說明地址空間發(fā)生改變且影響了當前跳轉(zhuǎn)的目標地址,因此我們需要創(chuàng)建新的翻譯塊包裝替換H1中的原有元素.

(3)翻譯塊包裝版本號大于vCPU版本號——說明內(nèi)存映射發(fā)生改變但當前vCPU尚未刷新 TLB, 較高的版本號來自并行執(zhí)行的其他vCPU線程, 因此我們視為翻譯塊查找命中.

4.2.2 跨頁直接跳轉(zhuǎn)

目前QEMU跨頁直接跳轉(zhuǎn)的主要困境在于缺乏高效的手段在運行時驗證跳轉(zhuǎn)目標的正確性, 因而其現(xiàn)有實現(xiàn)方案放棄對翻譯塊進行鏈接, 轉(zhuǎn)向使用徹底的動態(tài)查找. 我們提出的地址空間標識符(QASID)提供了檢驗跳轉(zhuǎn)目標正確性的輕量級方法, 基于QASID和第4.2.1節(jié)中引入的哈希表H1, 可以實現(xiàn)更加高效且語義相同的跨頁直接跳轉(zhuǎn).

新方案為每個包含跨頁直接跳轉(zhuǎn)的翻譯塊分配用于存儲QASID的額外緩存空間, 并引入一條用于檢查內(nèi)存映射是否改變的IR指令asid_check, 配合頁內(nèi)翻譯塊直接鏈接機制中原有的goto_tb和exit_tb完成跨頁場景中的翻譯塊直接鏈接, 跨頁直接跳轉(zhuǎn)對應的IR指令序列如圖5所示.

圖5 跨頁直接跳轉(zhuǎn)對應的IR指令序列

asid_check讀取當前vCPU的QASID并與翻譯塊內(nèi)緩存的QASID進行比較以檢測內(nèi)存映射是否發(fā)生改變. 二者相等時執(zhí)行后續(xù)goto_tb和exit_tb對應的指令, 流程與頁內(nèi)直接跳轉(zhuǎn)相同; 二者不等時代表內(nèi)存映射可能發(fā)生變化, 執(zhí)行流進入slow path, 調(diào)用asid_check對應的輔助函數(shù)asid_check_helper做進一步處理. 以x86_64后端為例, asid_check對應的宿主機代碼如圖6.

圖6 IR指令asid_check在x86_64后端生成代碼示例

我們設計QASID的寬度為8字節(jié)以便在64位宿主機上通過單條匯編指令完成QASID的比較操作, 其中頁目錄物理頁號和版本號分別占據(jù)4字節(jié), 可以處理至多16 TB的物理地址空間. QASID緩存分配在翻譯塊尾部, 其基地址可由%rip作偏移得到. 由于多線程場景下可能出現(xiàn)多個vCPU使用不同QASID并行執(zhí)行相同翻譯塊的場景, 需要避免緩存爭用導致的slow path開銷, 因而緩存的大小由vCPU線程的數(shù)量決定, 在運行時使用vCPU編號進行索引. 另一方面, vCPU的編號和當前QASID可以從位于%rbp低地址的CPUNegativeOffsetState結(jié)構(gòu)體中讀取, 這一結(jié)構(gòu)體用于存儲仿真運行時需要頻繁使用的架構(gòu)無關(guān)數(shù)據(jù)(如softTLB和外設中斷請求等), 我們在其中增加vCPU編號和QASID兩個字段以簡化asid_check的實現(xiàn).

當asid_check的執(zhí)行流進入slow path時, 輔助函數(shù)使用vCPU當前的QASID和傳入的跳轉(zhuǎn)目標虛擬地址查找H1, 根據(jù)查找H1的結(jié)果和當前翻譯塊的鏈接狀態(tài), 有以下兩種處理方式:

(1) H1查找命中, 且翻譯塊包裝中記錄的版本號匹配, 且后繼goto_tb已經(jīng)鏈接了H1查找所返回的翻譯塊——此時可以看作翻譯塊共享導致的緩存沖突,因此我們只需更新翻譯塊的QASID緩存并直接返回.

(2)其余情況——表明內(nèi)存映射發(fā)生變化, 或翻譯塊被多個地址空間所共享且在其中擁有若干個不同的后繼翻譯塊, 或翻譯塊尚未鏈接, 此時后繼跳轉(zhuǎn)的合法性有待進一步確認, 因此我們需要將翻譯塊中的goto_tb重置后返回.

輔助函數(shù)asid_check_helper結(jié)束后, slow path將返回與其相鄰的goto_tb指令處, 根據(jù)輔助函數(shù)是否斷開了記錄在goto_tb中的直接鏈接, 執(zhí)行流將會在此處完成跳轉(zhuǎn), 或通過exit_tb回到QEMU查找后繼翻譯塊并嘗試重新鏈接.

跨頁直接跳轉(zhuǎn)的重鏈接過程比較復雜, 因為vCPU線程共享翻譯塊, 我們需要保證各線程對共享翻譯塊的跳轉(zhuǎn)目標達成一致. 為此本文對翻譯塊鏈接的過程增加如下同步機制:

(1)使用翻譯塊本身的jmp_lock保護翻譯塊的鏈接過程. 原本的翻譯塊鏈接機制只需要獲取跳轉(zhuǎn)目標翻譯塊的jmp_lock, 并結(jié)合了一些無鎖編程技巧.我們將其修改為一并獲取目標翻譯塊和跳轉(zhuǎn)翻譯塊本身的jmp_lock, 為避免可能導致的死鎖問題, 加鎖通過trylock的方式進行, 在失敗時釋放已有鎖并作重試.

(2)引入新翻譯塊字段link_resolving并使用jmp_lock保護. 具體而言, 我們在斷開鏈接時設置link_resolving字段中對應當前線程的比特位, 以表明vCPU線程對當前翻譯塊的鏈接意圖, 嘗試對翻譯塊進行鏈接時清除link_resolving中對應當前線程的比特位, 且僅當這一字段為零時才真正進行鏈接.

在上述同步機制的保護下, 翻譯塊的重鏈接過程可以對以下兩種場景進行甄別.

(1)內(nèi)存映射發(fā)生改變導致翻譯塊跳轉(zhuǎn)目標變化;

(2)跳轉(zhuǎn)目標同時存在多個對應物理地址.

其中第2種情況無法由被共享翻譯塊末尾的直接跳轉(zhuǎn)語義處理, 需要將其丟棄, 并使用原本基于動態(tài)查找完成跳轉(zhuǎn)的方式重新翻譯. 我們通過維護翻譯塊的跳轉(zhuǎn)候選對象jmp_candidate完成對多跳轉(zhuǎn)目標物理地址的檢測, 具體流程如偽代碼1所示.

偽代碼1. 多跳轉(zhuǎn)目標物理地址的檢測輸入: 翻譯塊tb, 跳轉(zhuǎn)方向n, 目標翻譯塊tb_next輸出: 翻譯塊跳轉(zhuǎn)是否存在多個目標物理地址if (tb→asid_cache[n]僅包含單一地址空間)tb→jmp_candidate[n] = RAM_ADDR_INVALID endif if (tb→jmp_candidate[n] == RAM_ADDR_INVALID)tb→jmp_candidate[n] = tb_next→phys_pc else if (tb→jmp_candidate[n] != tb_next→phys_pc)return TRUE endif return FALSE

5 實驗評估

本節(jié)以64位RISC-V架構(gòu)的教學用UNIX操作系統(tǒng)xv6-riscv及其用戶程序為測試對象, 對本文設計并實現(xiàn)的QEMU動態(tài)跳轉(zhuǎn)優(yōu)化算法進行評估. 我們的實現(xiàn)基于QEMU主線6.2.0版本, 測試操作系統(tǒng)內(nèi)核與用戶程序均使用前綴為riscv64-elf-的交叉編譯器和二進制工具進行編譯, 其中GCC版本為11.1.0, binutils版本為2.36.1. 編譯C語言文件時所使用的代碼生成相關(guān)編譯選項為-O -fno-omit-frame-pointer -mcmodel=medany -ffreestanding -fno-common -fno-pie -no-pie -nostdlib -fno-stack-protector, 需要說明的是, 我們?nèi)コ?mno-relax選項以啟用鏈接器的松弛化(linker relaxation)操作, 以便將RISC-V編譯器生成的函數(shù)調(diào)用指令序列auipc+jalr按照鏈接時地址盡可能轉(zhuǎn)換成對應直接跳轉(zhuǎn)的jal指令.

測試使用的用戶程序為xv6-riscv自帶的測試用例集usertests, 該測試集共包含61個測試程序, 涵蓋了用戶進程管理、虛擬內(nèi)存管理、文件系統(tǒng)等諸多方面,其中運行時間較長的8個測試程序如表1所示.

表1 測試集usertests中部分程序的名稱與邏輯描述

我們以連續(xù)模式(對應命令行選項-c)執(zhí)行usertests測試集兩次, 并將收集到的執(zhí)行時長累加作為各測試用例的最終運行時間. 為了記錄單個測試用例的執(zhí)行時長, 我們在usertests的代碼中插樁, 使用xv6的uptime系統(tǒng)調(diào)用獲取每個測試測試用例執(zhí)行前后的時間戳,取其差值作為程序的運行時間, 另外將xv6內(nèi)核中的時鐘中斷周期調(diào)整為10 ms以獲取相對精確的計時.前述設定下usertests測試集中測試程序的運行時間節(jié)選如圖7所示.

圖7中QEMU代表使用主線6.2.0版本運行時記錄的各測試用例的運行時間, QEMU-PTE代表加入頁表頁保護時各測試用例的運行時間, QEMU-H1表示實現(xiàn)了完整的動態(tài)跳轉(zhuǎn)優(yōu)化算法時各測試用例的運行時間, 所有數(shù)據(jù)均保留一位小數(shù). 圖8是將上述數(shù)據(jù)以原生QEMU運行時間做正則化后得到的相對比例.

圖7 usertests 測試程序運行時間節(jié)選

圖8 usertests測試程序正則化運行時間

分析QEMU-PTE的運行時間可以得出, 引入頁表頁寫保護并未對測試程序的整體執(zhí)行時間造成很大影響——最差情況下在execout這一測試用例中引入了6%的執(zhí)行開銷. 進一步分析可以發(fā)現(xiàn), execout在執(zhí)行過程中需要反復使用sbrk系統(tǒng)調(diào)用將系統(tǒng)擁有的虛擬內(nèi)存全部分配完畢, 而OS為應用程序分配內(nèi)存的過程即是將物理頁地址寫入應用程序頁表頁的過程, 因而execout的運行過程涉及到較多對已受保護頁表頁的寫操作, 引入了一定的開銷. 本測試中仿真環(huán)境使用RISC-V的Sv39虛擬內(nèi)存模型, 共包含三級頁表頁, 由于保護代碼映射同時需要保護涉及到的所有非葉節(jié)點高層頁表頁, 因此, 當頁表級數(shù)隨著虛擬地址空間的擴大而增加時, 對高層頁表頁的保護會引入更多的開銷.

另一方面, 圖8表明 QEMU-H1在選取的8個測試用例中實現(xiàn)了約12%的平均運行性能提升, 在涉及大量文件操作的bigdir, manywrites, concreate和createdelete四個測試用例上表現(xiàn)尤為明顯, 而在reparent2, twochildren和sbrkfail上帶來的變化則并不顯著. 我們通過分析xv6-riscv相關(guān)內(nèi)核功能實現(xiàn), 認為上述性能變化的原因如下: 文件操作的完成過程涉及較多的對代碼規(guī)模較小函數(shù)的調(diào)用, 包含文件系統(tǒng)日志、inode管理與查找、用戶空間數(shù)據(jù)交換和磁盤塊讀寫等, 相關(guān)函數(shù)的實現(xiàn)分散在內(nèi)核的不同模塊中, 因而產(chǎn)生了數(shù)量較多的函數(shù)返回與跨頁直接跳轉(zhuǎn); 與此相對地, 其余測試用例中大量使用的fork, wait, exit, sbrk系統(tǒng)調(diào)用的實現(xiàn)相對獨立, 僅使用少量接口與外部模塊交互. 我們反匯編內(nèi)核二進制文件發(fā)現(xiàn), 相關(guān)接口函數(shù)的代碼規(guī)模較大且數(shù)量少, 對應跳轉(zhuǎn)目標及返回地址可以被很好地緩存在H0中, 故QEMU-H1中額外引入的動態(tài)跳轉(zhuǎn)優(yōu)化沒有對其產(chǎn)生明顯的影響.

6 相關(guān)工作

目標架構(gòu)虛擬內(nèi)存特性的仿真對模擬器的整體設計和運行效率有深刻影響. Tong等人[9]在特定工作負載上定量研究了QEMU中內(nèi)存仿真模塊的運行開銷,并探索了softTLB的若干改進設計方案, 包含自適應擴容的動態(tài)大小TLB和為TLB額外添加全相聯(lián)后備緩沖等. Cota等人[10]改進了QEMU中TLB的擴容策略, 根據(jù)時間窗口內(nèi)的TLB占用率選擇合適的TLB大小以平衡TLB的命中率與刷新開銷. Hong等人[11]提出使用內(nèi)聯(lián)緩存的方式加速Q(mào)EMU的動態(tài)跳轉(zhuǎn), 對應目前QEMU中使用的lookup_and_goto_ptr邏輯.

以上工作旨在優(yōu)化QEMU仿真過程中與地址翻譯相關(guān)的緩存結(jié)構(gòu)以增加命中概率, 但由軟件實現(xiàn)的緩存查詢操作本身亦導致了一定的開銷. 對此, Chang等人[12]提出了嵌入式影子頁表(ESPT)的方案, 將目標架構(gòu)的頁表嵌入QEMU進程自身的頁表中, 從而利用x86_64宿主機的地址翻譯硬件完成單指令的目標架構(gòu)內(nèi)存訪問. 在ESPT的基礎(chǔ)上, Wang等人[13]通過Linux系統(tǒng)的mmap系統(tǒng)調(diào)用完成對QEMU自身頁表的操作, 去除了對內(nèi)核模塊的依賴. Huang等人[14]借助龍芯3A4000處理器的對偶硬件TLB實現(xiàn)了更加通用的跨指令集架構(gòu)內(nèi)存虛擬化, 解決了ESPT方案中目標架構(gòu)地址空間需要嚴格小于宿主架構(gòu)地址空間的局限,且可以處理目標架構(gòu)與宿主架構(gòu)內(nèi)存頁面大小不匹配的情形.

7 結(jié)語

本文介紹了QEMU中翻譯塊間跳轉(zhuǎn)機制的原理,詳細分析了仿真目標架構(gòu)支持虛擬內(nèi)存的場景下現(xiàn)有跳轉(zhuǎn)機制的不足之處, 并針對常見的單頁目錄虛擬內(nèi)存模型提出和實現(xiàn)了基于地址空間標識符的動態(tài)跳轉(zhuǎn)改進方案. 該方案通過監(jiān)視對頁表頁的寫操作維護QEMU內(nèi)部的地址空間標識符, 并利用該標識符優(yōu)化動態(tài)跳轉(zhuǎn)目標的查找過程. 最后, 本文使用運行在RISC-V架構(gòu)上的教學用UNIX操作系統(tǒng)xv6-riscv對提出的方案進行了性能評估, 驗證了本文工作的有效性: 引入頁表頁寫保護對程序的執(zhí)行時間開銷影響較小, 動態(tài)跳轉(zhuǎn)優(yōu)化方案實現(xiàn)了約12%的平均運行性能提升.

本文方案的局限在于QASID由頁目錄唯一決定,因而不能高效處理內(nèi)存映射受頁目錄以外因素影響的場景, 如RISC-V中可能開啟的物理內(nèi)存保護機制PMP和由H-擴展引入的兩階段地址翻譯等. 后續(xù)可以考慮設計綜合各項因素的QASID分配算法, 以提高方案的泛用性.