位金弈, 梁洪亮

(北京郵電大學(xué) 計(jì)算機(jī)學(xué)院, 北京 100876)

1 引言

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

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

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

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

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

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

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

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

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

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

2.2 間接跳轉(zhuǎn)

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

圖2 QEMU的翻譯塊查找流程

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

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

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

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

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

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

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

3 觀察與討論

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

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

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

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

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

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

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

4 基于地址空間標(biāo)識(shí)符的動(dòng)態(tài)跳轉(zhuǎn)機(jī)制

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

4.1 地址空間標(biāo)識(shí)符的定義與維護(hù)

4.1.1 地址空間標(biāo)識(shí)符的定義

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

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

4.1.2 地址空間標(biāo)識(shí)符的維護(hù)

與QEMU中代碼頁(yè)寫保護(hù)的建立過(guò)程類似, 我們采用如下方式對(duì)頁(yè)表頁(yè)進(jìn)行寫保護(hù): 維護(hù)新的物理頁(yè)狀態(tài)位圖DIRTY_MEMORY_PTE, 并在softMMU因?yàn)橹噶畹刂贩g的需要而訪問(wèn)各級(jí)頁(yè)表頁(yè)時(shí)標(biāo)記此位圖中代表相應(yīng)頁(yè)面的比特. 當(dāng)QEMU為softTLB添加新的地址映射條目時(shí), 將根據(jù)頁(yè)面在前述位圖中的狀態(tài)對(duì)應(yīng)設(shè)置TLB表項(xiàng)的TLB_NOTDIRTY標(biāo)志位, 從而截獲后續(xù)所有對(duì)受保護(hù)頁(yè)表頁(yè)的寫操作.

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

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

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

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

4.1.3 vCPU線程對(duì)地址空間標(biāo)識(shí)符的獲取

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

4.2 地址空間標(biāo)識(shí)符在動(dòng)態(tài)跳轉(zhuǎn)處理中的應(yīng)用

4.2.1 間接跳轉(zhuǎn)

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

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

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

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

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

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

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

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

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

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

圖5 跨頁(yè)直接跳轉(zhuǎn)對(duì)應(yīng)的IR指令序列

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

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

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

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

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

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

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

跨頁(yè)直接跳轉(zhuǎn)的重鏈接過(guò)程比較復(fù)雜, 因?yàn)関CPU線程共享翻譯塊, 我們需要保證各線程對(duì)共享翻譯塊的跳轉(zhuǎn)目標(biāo)達(dá)成一致. 為此本文對(duì)翻譯塊鏈接的過(guò)程增加如下同步機(jī)制:

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

(2)引入新翻譯塊字段link_resolving并使用jmp_lock保護(hù). 具體而言, 我們?cè)跀嚅_(kāi)鏈接時(shí)設(shè)置link_resolving字段中對(duì)應(yīng)當(dāng)前線程的比特位, 以表明vCPU線程對(duì)當(dāng)前翻譯塊的鏈接意圖, 嘗試對(duì)翻譯塊進(jìn)行鏈接時(shí)清除link_resolving中對(duì)應(yīng)當(dāng)前線程的比特位, 且僅當(dāng)這一字段為零時(shí)才真正進(jìn)行鏈接.

在上述同步機(jī)制的保護(hù)下, 翻譯塊的重鏈接過(guò)程可以對(duì)以下兩種場(chǎng)景進(jìn)行甄別.

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

(2)跳轉(zhuǎn)目標(biāo)同時(shí)存在多個(gè)對(duì)應(yīng)物理地址.

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

偽代碼1. 多跳轉(zhuǎn)目標(biāo)物理地址的檢測(cè)輸入: 翻譯塊tb, 跳轉(zhuǎn)方向n, 目標(biāo)翻譯塊tb_next輸出: 翻譯塊跳轉(zhuǎn)是否存在多個(gè)目標(biāo)物理地址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 實(shí)驗(yàn)評(píng)估

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

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

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

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

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

圖7 usertests 測(cè)試程序運(yùn)行時(shí)間節(jié)選

圖8 usertests測(cè)試程序正則化運(yùn)行時(shí)間

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

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

6 相關(guān)工作

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

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

7 結(jié)語(yǔ)

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

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