傅立國(guó) 龐建民 王 軍 張家豪 岳 峰

(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室 鄭州 450001)

動(dòng)態(tài)二進(jìn)制翻譯技術(shù)作為一種特殊的即時(shí)編譯技術(shù)，既可以用于跨架構(gòu)的程序移植，也能夠用于程序特征分析和性能調(diào)優(yōu)，因而在體系結(jié)構(gòu)優(yōu)化、程序性能優(yōu)化、安全分析以及軟件移植的研究中備受關(guān)注.隨著虛擬化技術(shù)的興起，在跨指令集架構(gòu)的虛擬化以及全軟件虛擬化的項(xiàng)目中，二進(jìn)制翻譯技術(shù)得到了更廣泛的應(yīng)用[1].

然而較低的效率限制了該技術(shù)解決跨架構(gòu)無(wú)源移植問(wèn)題的實(shí)用性.為了提高動(dòng)態(tài)二進(jìn)制翻譯的效率，針對(duì)源平臺(tái)的體系架構(gòu)特征，充分利用宿主平臺(tái)的軟硬件資源成為相關(guān)研究的核心點(diǎn).

不論是使用指令模擬技術(shù)，還是使用軟硬件協(xié)同又或者是純軟件模擬，翻譯的正確性和翻譯的效率總是各種翻譯方法研究的要點(diǎn)[2-3].在動(dòng)態(tài)二進(jìn)制翻譯效率優(yōu)化的研究中，主要針對(duì)2部分內(nèi)容進(jìn)行展開：1)提高翻譯過(guò)程的效率，即加快源指令的分析和本地指令的生成；2)改善翻譯方法，使生成的本地代碼執(zhí)行更加高效[4-6].

2類優(yōu)化既相互聯(lián)系也相互制約.簡(jiǎn)單的翻譯方式所生成的代碼執(zhí)行效率相較而言比較低，而翻譯過(guò)程中優(yōu)化本地代碼生成的開銷也會(huì)削減執(zhí)行時(shí)代碼質(zhì)量提高獲取的收益[7].

針對(duì)這種情況，使用庫(kù)函數(shù)處理的方法可以有效地提高動(dòng)態(tài)二進(jìn)制翻譯執(zhí)行的效率[8-9].該方法對(duì)源程序中庫(kù)函數(shù)的執(zhí)行進(jìn)行了本地函數(shù)的封裝和替換處理.該方法精簡(jiǎn)了原有的翻譯過(guò)程，將函數(shù)指令序列翻譯代價(jià)轉(zhuǎn)換為一條函數(shù)調(diào)用指令的代價(jià)，并且利用源碼編譯優(yōu)化的優(yōu)勢(shì).相較于動(dòng)態(tài)翻譯中基于指令語(yǔ)義解析生成的代碼，本地編譯優(yōu)化的代碼具有更高的執(zhí)行效率.因此，作為一種動(dòng)靜結(jié)合的翻譯方式，庫(kù)函數(shù)處理可以有效地提高動(dòng)態(tài)二進(jìn)制的效率.

本質(zhì)上，庫(kù)函數(shù)處理過(guò)程類似于共享庫(kù)函數(shù)的動(dòng)態(tài)鏈接過(guò)程.當(dāng)源程序中調(diào)用的庫(kù)函數(shù)數(shù)量以及翻譯器支持的庫(kù)函數(shù)數(shù)量較多時(shí)，這種查詢鏈接過(guò)程的開銷會(huì)降低庫(kù)函數(shù)處理應(yīng)有的收益，從而影響動(dòng)態(tài)二進(jìn)制翻譯的整體效率和實(shí)際應(yīng)用效果.

針對(duì)當(dāng)源程序中庫(kù)函數(shù)調(diào)用次數(shù)以及翻譯器支持的庫(kù)函數(shù)數(shù)量較多時(shí)，庫(kù)函數(shù)處理機(jī)制中查詢鏈接過(guò)程的開銷過(guò)大問(wèn)題，本文基于庫(kù)函數(shù)處理的性質(zhì)，提出了靜態(tài)預(yù)處理散列查詢表的優(yōu)化方法.基于動(dòng)態(tài)二進(jìn)制翻譯器QEMU實(shí)現(xiàn)了庫(kù)函數(shù)處理的機(jī)制，然后在此基礎(chǔ)上進(jìn)行了優(yōu)化方法的實(shí)現(xiàn)，最后通過(guò)實(shí)驗(yàn)驗(yàn)證了該優(yōu)化方法的有效性[10].

1 動(dòng)態(tài)二進(jìn)制翻譯中的庫(kù)函數(shù)處理

1.1 共享庫(kù)函數(shù)的動(dòng)態(tài)鏈接

程序執(zhí)行時(shí)共享庫(kù)函數(shù)的動(dòng)態(tài)連接過(guò)程如圖1所示:

Fig. 1 The dynamic connection process of shared library functions圖1 共享庫(kù)函數(shù)的動(dòng)態(tài)連接過(guò)程

圖1中的粗實(shí)線和虛線描述了第1次重定位和調(diào)用函數(shù)func的過(guò)程.二進(jìn)制程序執(zhí)行到callfunc@plt指令時(shí)，指令中的目標(biāo)地址func@plt指向PLT(procedure linkage table)段的第n個(gè)入口即地址plt[n].進(jìn)入PLT段對(duì)應(yīng)的入口后，程序執(zhí)行指令jmp*got[n]，跳轉(zhuǎn)的目標(biāo)地址取決于GOT(global offset table)段第n個(gè)項(xiàng)中存儲(chǔ)的地址.

若是第1次調(diào)用該入口對(duì)應(yīng)的函數(shù)，got[n]中存儲(chǔ)的是jmp *got[n]指令下一條指令的地址，此時(shí)程序按照地址連續(xù)執(zhí)行，準(zhǔn)備函數(shù)名解析相關(guān)的參數(shù)，然后通過(guò)執(zhí)行指令jmpplt[0]，調(diào)用解釋鏈接器(即函數(shù)_dl_runtime_resolve)解釋器不僅會(huì)完成函數(shù)func的首次調(diào)用，也會(huì)將其在LIB段中實(shí)際的存儲(chǔ)地址回填got[n].

此后程序?qū)瘮?shù)func的調(diào)用，當(dāng)執(zhí)行到PLT段入口的jmp *got[n]指令時(shí)，即可直接跳轉(zhuǎn)到函數(shù)func在LIB中的入口地址，實(shí)現(xiàn)對(duì)函數(shù)的有效調(diào)用.函數(shù)重定位后的執(zhí)行過(guò)程由圖1中粗實(shí)線和細(xì)實(shí)線構(gòu)成.

綜上可知，共享庫(kù)函數(shù)的動(dòng)態(tài)鏈接過(guò)程完成了一次基于外部鏈接函數(shù)PLT段入口地址的查詢，即實(shí)現(xiàn)了函數(shù)func入口地址func@plt到其在LIB段中實(shí)際存儲(chǔ)入口地址的映射.

1.2 動(dòng)態(tài)二進(jìn)制翻譯中的庫(kù)函數(shù)處理

類似于處理器的執(zhí)行過(guò)程，動(dòng)態(tài)二進(jìn)制翻譯過(guò)程可以概括為查找、翻譯、執(zhí)行3個(gè)子過(guò)程[11].而庫(kù)函數(shù)處理區(qū)別于一般的二進(jìn)制翻譯過(guò)程主要體現(xiàn)在查找和翻譯2個(gè)過(guò)程中.

圖2給出了動(dòng)態(tài)二進(jìn)制翻譯過(guò)程中庫(kù)函數(shù)2種不同的翻譯處理方式.

Fig. 2 Dynamic translation of shared library functions圖2 共享庫(kù)函數(shù)的翻譯過(guò)程

圖2右側(cè)描述了圖1中庫(kù)函數(shù)func第1次被調(diào)用時(shí)的指令序列；圖2左側(cè)是對(duì)右側(cè)指令序列的動(dòng)態(tài)翻譯處理過(guò)程.

左側(cè)虛線箭頭描述的是對(duì)指令call一般的動(dòng)態(tài)二進(jìn)制翻譯處理過(guò)程，先將call指令解釋成右上的5條中間指令，然后由后端代碼生成器將中間指令轉(zhuǎn)換為本地代碼。執(zhí)行完生成的本地代碼后，會(huì)繼續(xù)獲取待翻譯的指令進(jìn)行翻譯，以此反復(fù).

左側(cè)實(shí)線箭頭描述的是使用庫(kù)函數(shù)處理方法對(duì)指令call的翻譯處理過(guò)程.對(duì)函數(shù)調(diào)用地址func@plt進(jìn)行分析，可以將其解釋成特殊的中間表示.在翻譯器執(zhí)行時(shí)，解釋中間表示gen_helper_func需要調(diào)用翻譯器內(nèi)建的模板函數(shù)helper_func，該模板函數(shù)是與源平臺(tái)函數(shù)func功能相同的本地實(shí)現(xiàn)，但同時(shí)也封裝了對(duì)應(yīng)的傳參和返回值回寫機(jī)制，以此作為對(duì)左側(cè)func函數(shù)指令序列本地翻譯的結(jié)果.

圖2右側(cè)的指令序列從功能上可以分為函數(shù)解析重定位和函數(shù)執(zhí)行2部分.從指令callfunc@plt開始到函數(shù)func之前，這部分指令完成了函數(shù)解析重定位的運(yùn)行環(huán)境的維護(hù)工作，與原應(yīng)用的邏輯功能無(wú)關(guān).按照一般的翻譯處理方式，序列中的每條指令都會(huì)被翻譯成中間語(yǔ)言表示，然后再被后端轉(zhuǎn)換成本地代碼.而庫(kù)函數(shù)處理的翻譯方式，在翻譯器內(nèi)部實(shí)現(xiàn)了函數(shù)的解析重定位，再調(diào)用翻譯器提供的模板函數(shù)(即封裝好的函數(shù))作為函數(shù)func在本地翻譯結(jié)果的執(zhí)行.

在使用庫(kù)函數(shù)處理的方式翻譯call指令時(shí)，需要使用基于共享庫(kù)函數(shù)PLT段入口地址的語(yǔ)義信息.因此，在翻譯時(shí)需要先解析該地址的語(yǔ)義，查詢對(duì)應(yīng)的函數(shù)名，然后在翻譯器支持的模板函數(shù)中查找相應(yīng)的處理函數(shù)，最終完成共享庫(kù)函數(shù)調(diào)用全過(guò)程的翻譯.

由于語(yǔ)義分析的層次更高，使用本地編譯優(yōu)化的模板處理函數(shù)，其代碼的執(zhí)行效率遠(yuǎn)遠(yuǎn)超過(guò)一般指令序列動(dòng)態(tài)翻譯所生成代碼的執(zhí)行效率，同時(shí)還節(jié)約了相應(yīng)指令序列的翻譯時(shí)間.

綜上可知，在庫(kù)函數(shù)處理的翻譯過(guò)程中，有2次查詢的操作：1)根據(jù)call指令的目標(biāo)地址判斷是否是PLT段的入口，并根據(jù)入口的序號(hào)查詢函數(shù)的名稱；2)根據(jù)函數(shù)的名稱查詢翻譯器模板函數(shù)中是否有對(duì)應(yīng)函數(shù)的處理函數(shù).當(dāng)源程序中call指令的數(shù)量或者翻譯器模板函數(shù)的數(shù)量增長(zhǎng)時(shí)，查詢開銷會(huì)隨之增長(zhǎng).最差的情況就是，翻譯器模板函數(shù)沒有對(duì)應(yīng)的處理函數(shù)時(shí)，此時(shí)沒有任何收益卻額外添加了2次查詢的開銷.

2 庫(kù)函數(shù)處理過(guò)程的解析

一般的翻譯處理方法和庫(kù)函數(shù)處理的翻譯方法，其差異性主要體現(xiàn)在2個(gè)方面:

1) 語(yǔ)義解析的層次不同.一般的翻譯處理是基于指令的語(yǔ)義解析；庫(kù)函數(shù)處理的翻譯過(guò)程是基于函數(shù)的語(yǔ)義解析，即在翻譯call指令時(shí)需要結(jié)合跳轉(zhuǎn)指令的目標(biāo)地址解析調(diào)用的函數(shù)，繼而完成函數(shù)語(yǔ)義的解析.

2) 指令流的執(zhí)行語(yǔ)義有所改變.在一般的翻譯過(guò)程中，源程序函數(shù)解釋鏈接重定位的過(guò)程中對(duì)應(yīng)的指令序列是被逐一翻譯的；在基于函數(shù)語(yǔ)義的翻譯過(guò)程中，源程序鏈接重定位過(guò)程的指令序列并未被翻譯，函數(shù)的解析過(guò)程被當(dāng)做call指令解析的一部分，翻譯執(zhí)行的代碼是模板函數(shù)中已經(jīng)本地化封裝的處理函數(shù).

使用庫(kù)函數(shù)處理的動(dòng)態(tài)二進(jìn)制翻譯模式，在翻譯call指令時(shí)，結(jié)合跳轉(zhuǎn)目標(biāo)地址的解析以確定調(diào)用函數(shù)的名稱，然后根據(jù)翻譯器對(duì)該函數(shù)的支持情況確定翻譯的方式.

因此庫(kù)函數(shù)處理即在普通翻譯模式中對(duì)call指令的翻譯添加了一類特殊處理.

2.1 庫(kù)函數(shù)處理的call指令翻譯

庫(kù)函數(shù)處理中call指令的翻譯流程如圖3所示:

Fig. 3 Translation of call instruction in library function disposing圖3庫(kù)函數(shù)處理中call指令的翻譯

在圖3中，B表示源程序中外部鏈接共享函數(shù)的PLT段入口地址的集合，C表示翻譯器中支持庫(kù)函數(shù)處理的庫(kù)函數(shù)集合名稱集合.如圖3所示，在一次完整庫(kù)函數(shù)處理的翻譯過(guò)程中，需要2次查詢判斷：

1) 查詢addr對(duì)應(yīng)的函數(shù)名func_name；

2) 查詢名為func_name的庫(kù)函數(shù)對(duì)應(yīng)的處理函數(shù)func_helper.

不論哪次查詢失敗，該call指令的翻譯都會(huì)采用一般的翻譯模式.查詢的本質(zhì)即完成了從跳轉(zhuǎn)指令目標(biāo)地址到翻譯處理函數(shù)的映射.

設(shè)源程序中指令call調(diào)用的目標(biāo)地址集合為A，設(shè)一般翻譯執(zhí)行模式的處理函數(shù)為d,那么庫(kù)函數(shù)處理的查詢過(guò)程完成了集合A到集合C∪ikgsqia的映射.該映射過(guò)程用函數(shù)SA表示.則有:

?a∈A,SA(a)∈(C∪oww0go0).

(1)

根據(jù)式(1)中元素a映射的結(jié)果可以對(duì)集合A中的元素劃分：

(2)

其中，SA表示call指令跳轉(zhuǎn)目標(biāo)地址到call指令翻譯處理函數(shù)的映射，因?yàn)閹?kù)函數(shù)翻譯處理函數(shù)和其處理的庫(kù)函數(shù)名稱是一一對(duì)應(yīng)的，式(2)中C表示的是翻譯器中庫(kù)函數(shù)翻譯處理函數(shù)的集合.

2.2 庫(kù)函數(shù)名稱的解析

集合B中的庫(kù)函數(shù)的名稱作為集合A向集合C映射的過(guò)渡，是動(dòng)態(tài)二進(jìn)制翻譯過(guò)程中源程序地址語(yǔ)義和翻譯處理函數(shù)語(yǔ)義的唯一標(biāo)識(shí).

因此從集合A向集合B映射的過(guò)程，實(shí)質(zhì)上是對(duì)call指令地址語(yǔ)義的解析.除了需要判斷目標(biāo)地址是否屬于PLT段的入口，還需要解析其對(duì)應(yīng)的函數(shù)名.

在確定應(yīng)用二進(jìn)制接口(application binary interface, ABI)規(guī)范下，外部鏈接函數(shù)名稱的解析過(guò)程是固定的.以elf(executable and linkable format)格式為例，其共享庫(kù)函數(shù)名稱解析過(guò)程如圖4所示[12].

首先根據(jù)函數(shù)func在PLT段入口序號(hào)n在RELA.PLT段中索引查詢符號(hào)名的索引，然后依次在DYN.SYM段、SYM.TAB段和STR段中索引查詢，最終得到外部鏈接函數(shù)func名稱的字符串.

Fig. 4 The name analyzing of shared library function圖4 共享庫(kù)函數(shù)的名稱解析

3 優(yōu)化的分析及實(shí)現(xiàn)

庫(kù)函數(shù)處理使用本地庫(kù)函數(shù)封裝，在不改變封裝方式和實(shí)現(xiàn)方法的情況下，這部分過(guò)程的執(zhí)行代價(jià)是固定不變的.因此本文的分析和優(yōu)化主要針對(duì)call指令翻譯處理的判斷確認(rèn)過(guò)程.

根據(jù)以上的分析，在使用庫(kù)函數(shù)處理的翻譯過(guò)程中，查詢過(guò)程主要完成了函數(shù)名稱的解析以及對(duì)應(yīng)處理函數(shù)的查詢.

因此查詢的優(yōu)化主要從2個(gè)方面進(jìn)行：1)優(yōu)化查詢表的組織結(jié)構(gòu)；2)優(yōu)化查詢實(shí)現(xiàn)的方法.

3.1 查詢表的優(yōu)化

對(duì)于查詢成功的跳轉(zhuǎn)目標(biāo)地址而言，在2次查詢(PLT段入口地址查詢、翻譯器支持庫(kù)函數(shù)處理的函數(shù)名稱查詢)以及一次解析(使用PLT段入口地址解析函數(shù)名稱)過(guò)程中，需要使用若干張查詢表.特別是共享庫(kù)函數(shù)名稱解析的過(guò)程中，需要基于文件規(guī)范從多個(gè)表格中進(jìn)行多次索引查詢獲取函數(shù)名稱.

針對(duì)一個(gè)確定的源程序，其外部鏈接函數(shù)名稱解析所需的數(shù)據(jù)是靜態(tài)可得的.因此，PLT段入口地址和函數(shù)名稱的對(duì)應(yīng)關(guān)系是能夠進(jìn)行靜態(tài)分析的.靜態(tài)的解析過(guò)程與動(dòng)態(tài)鏈接重定位的解析過(guò)程相同，使用文件中若干個(gè)段中的索引和數(shù)據(jù)獲取描述函數(shù)名稱的字符串.類似的解析過(guò)程在類似objdump的反匯編工具中均有實(shí)現(xiàn)和應(yīng)用.

針對(duì)一個(gè)確定的翻譯器，其支持庫(kù)函數(shù)處理的共享庫(kù)函數(shù)也是確定的.這些函數(shù)的名稱和其處理函數(shù)的名稱也是一一對(duì)應(yīng)且靜態(tài)可知的.

Fig. 5 Optimized query table and query processing圖5 優(yōu)化的查詢表及查詢過(guò)程

在翻譯執(zhí)行前，通過(guò)靜態(tài)預(yù)分析源程序和翻譯器的相關(guān)信息，就可以獲取庫(kù)函數(shù)處理過(guò)程中所需的若干查詢表.因此，可以在預(yù)分析的基礎(chǔ)上對(duì)查詢表進(jìn)行合并.最終獲得PLT段入口地址到call指令翻譯處理函數(shù)的查詢表.

按照匹配的查詢方式，查詢的平均開銷和每次查詢表中項(xiàng)目的規(guī)模成正比.將查詢表合并后，查詢表的規(guī)模始終和PLT段的入口數(shù)相同，避免了之前查詢過(guò)程中匹配查詢中的額外的開銷.

3.2 查詢方法的優(yōu)化

在程序執(zhí)行過(guò)程中，call指令調(diào)用的目標(biāo)地址是隨機(jī)且離散的.然而對(duì)于任意符合相應(yīng)規(guī)范的二進(jìn)制可執(zhí)行文件，其PLT段的構(gòu)成總是有規(guī)律的.

通過(guò)源程序的靜態(tài)預(yù)分析，每個(gè)源程序中的PLT段入口地址是靜態(tài)可知且地址偏移相等.設(shè)源程序PLT段中有m個(gè)入口，可以通過(guò)構(gòu)建一個(gè)簡(jiǎn)單的散列函數(shù)將任意調(diào)用地址addr散列到m+1個(gè)槽中.

由于庫(kù)函數(shù)處理過(guò)程對(duì)被處理的庫(kù)函數(shù)具有較為嚴(yán)格的限制，對(duì)于大部分的源程序而言，查詢失敗的概率遠(yuǎn)大于查詢成功并進(jìn)行處理的概率.因此在構(gòu)建查詢算法的過(guò)程中，應(yīng)當(dāng)優(yōu)先針對(duì)查詢失敗的情況進(jìn)行處理，從整體上降低平均的查詢開銷.

根據(jù)之前的分析，調(diào)用外部鏈結(jié)函數(shù)的call指令其目標(biāo)地址一定是PLT段入口，因此跳轉(zhuǎn)目標(biāo)地址不在PLT段內(nèi)的地址一定會(huì)查詢失敗.其次，跳轉(zhuǎn)目標(biāo)地址減去PLT段首地址不能整除一個(gè)記錄長(zhǎng)度的地址一定查詢失敗.最后，將整除PLT段記錄長(zhǎng)度的結(jié)果作為PLT段入口地址查詢的索引值.為保持查詢的完備性，將查詢失敗的索引值置為-1.

根據(jù)索引值，可以獲取該call指令翻譯的處理函數(shù).在靜態(tài)預(yù)處理的查詢表中，根據(jù)翻譯器的支持情況，將處理函數(shù)的函數(shù)指針填到相應(yīng)索引對(duì)應(yīng)的值中，而翻譯器不支持的PLT段入口地址索引以及索引-1對(duì)應(yīng)的值則為普通call指令翻譯處理的函數(shù)指針.

3.3 優(yōu)化的查詢實(shí)現(xiàn)及其算法描述

查詢表的優(yōu)化及查詢算法的優(yōu)化實(shí)現(xiàn)如圖5所示.

圖5描述了查詢表的優(yōu)化，即將TAB_A，TAB_B，TAB_C，TAB_D合并成TAB_E的過(guò)程.其中表TAB_A可通過(guò)對(duì)二進(jìn)制程序靜態(tài)分析獲?。槐鞹AB_B描述了可封裝翻譯處理函數(shù)名func_name和翻譯器模板函數(shù)入口helper_pointer的對(duì)應(yīng)關(guān)系；通過(guò)TAB_A和TAB_B即可實(shí)現(xiàn)庫(kù)函數(shù)處理的2次查詢.

TAB_C對(duì)PLT段的入口plt_entry進(jìn)行了排序，目的是為了可以實(shí)現(xiàn)指令call目標(biāo)地址變量addr在plt_entry中的快速查詢；TAB_D則是對(duì)模板函數(shù)入口helper_pointer進(jìn)行了排序，因?yàn)樵诜g器執(zhí)行期間表TAB_D是常駐內(nèi)存的，并且翻譯器自身構(gòu)建的一些特殊指令輔助翻譯的實(shí)現(xiàn)也是通過(guò)查詢?cè)摫碚{(diào)用對(duì)應(yīng)模板函數(shù)實(shí)現(xiàn)的，構(gòu)建使用模板函數(shù)調(diào)用號(hào)op_num實(shí)現(xiàn)模板函數(shù)的調(diào)用可以與實(shí)驗(yàn)翻譯器自身的執(zhí)行機(jī)制更好的融合.

通過(guò)索引表的合并，最終得到表TAB_E，完成了入口地址索引index到模板函數(shù)地址索引號(hào)的對(duì)應(yīng)表.索引index中記錄值-1表示無(wú)效的索引號(hào)；對(duì)應(yīng)項(xiàng)op_num中的記錄值-1，表示無(wú)對(duì)應(yīng)的模板函數(shù)，需要調(diào)用一般的動(dòng)態(tài)翻譯處理過(guò)程.查詢表的合并過(guò)程可以在翻譯器加載源平臺(tái)二進(jìn)制程序的過(guò)程中完成，進(jìn)而減少了原本在翻譯過(guò)程中進(jìn)行動(dòng)態(tài)查詢的開銷.

經(jīng)過(guò)查詢表和查詢過(guò)程的優(yōu)化，將原有的多次查詢過(guò)程轉(zhuǎn)換為1次計(jì)算和2次索引取值的過(guò)程，即對(duì)指令call的目標(biāo)地址變量addr使用函數(shù)hash進(jìn)行計(jì)算，使用函數(shù)tab_e和函數(shù)tab_d實(shí)現(xiàn)對(duì)表TAB_E和表TAB_D的索引取值，整個(gè)映射過(guò)程為

helper_pointer=tab_d[tab_e[hash(addr)]].

(3)

使用變量index表示翻譯過(guò)程中模板函數(shù)的調(diào)用號(hào)，優(yōu)化的查詢算法描述如算法1所示：

算法1.優(yōu)化的查詢算法.

功能：構(gòu)造源程序地址到目標(biāo)平臺(tái)程序地址的映射表；

輸入：call指令目標(biāo)地址addr；

輸出：對(duì)應(yīng)模板函數(shù)入口地址helper_pointer.

① 初始化數(shù)組tab_e，獲取plt_start起始地址數(shù)值和長(zhǎng)度length；

② for eachaddr

③ ifaddr不在plt段范圍內(nèi)

④index=-1；

⑤ else

⑥index=tab_e[(addr-plt_start)length]；

⑦ end if

⑧ ifindex=-1

⑨ 使用一般方式翻譯指令call；

⑩ else

4 實(shí)驗(yàn)與結(jié)果

靜態(tài)預(yù)處理動(dòng)態(tài)查詢的查詢表，將匹配查詢替換為計(jì)算查詢，針對(duì)動(dòng)態(tài)二進(jìn)制翻譯中庫(kù)函數(shù)處理中查詢過(guò)程優(yōu)化的有效性是具有理論依據(jù)的.為了進(jìn)一步驗(yàn)證優(yōu)化的效果，在動(dòng)態(tài)二進(jìn)制翻譯器QEMU上實(shí)現(xiàn)了庫(kù)函數(shù)處理的翻譯機(jī)制，再在此基礎(chǔ)上實(shí)現(xiàn)了本文提出的優(yōu)化方法，最后在課題研究所使用的SW平臺(tái)上進(jìn)行了實(shí)驗(yàn)驗(yàn)證.關(guān)于庫(kù)函數(shù)處理機(jī)制的正確性驗(yàn)證在課題組之前的研究中已經(jīng)通過(guò)了相關(guān)的正確性測(cè)試[13-14].

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)測(cè)試環(huán)境的環(huán)境如表1所示：

Table 1 Binary Translation Environments表1 二進(jìn)制翻譯環(huán)境

測(cè)試平臺(tái)采用的是國(guó)產(chǎn)申威SW410處理器，是一款面向桌面平臺(tái)場(chǎng)景應(yīng)用的處理器，是神威太湖之光系統(tǒng)采用的處理器SW20610[15]的精簡(jiǎn)版.SW410較SW20610只保留了4個(gè)主頻為1.4 GHz主核，精簡(jiǎn)了對(duì)應(yīng)的從核架構(gòu).

實(shí)驗(yàn)使用的翻譯器為qemu-2.5.1，通過(guò)修改，支持標(biāo)準(zhǔn)C庫(kù)中math.h，stdio.h，string.h下定義的大部分函數(shù)以及其他部分庫(kù)函數(shù)的翻譯處理.

實(shí)驗(yàn)使用的測(cè)試集包括qemu官網(wǎng)推薦的性能評(píng)測(cè)用例nbench以及標(biāo)準(zhǔn)性能測(cè)試集spec cpu2006.具體的測(cè)試用例包括nbench-2.2.3 benchmark suite中的所有用例，如表2所示[16]；以及spec cpu2006中所有的C語(yǔ)言程序，如表3所示[17]:

Table 2 nbench Description表2 nbench 測(cè)試用例簡(jiǎn)介

Table 3 spec cpu2006 Description表3 spec cpu2006 測(cè)試用例簡(jiǎn)介

4.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)對(duì)每個(gè)測(cè)試用例翻譯執(zhí)行的時(shí)間進(jìn)行3組測(cè)試，分別為一般的翻譯方式、未經(jīng)優(yōu)化查詢的庫(kù)函數(shù)處理翻譯方式和使用優(yōu)化查詢的庫(kù)函數(shù)處理翻譯方式.通過(guò)計(jì)算可得無(wú)優(yōu)化查詢庫(kù)函數(shù)處理翻譯方式的加速比用Original表示，優(yōu)化查詢過(guò)后庫(kù)函數(shù)處理翻譯方式的加速比用Optimized表示.

Fig. 6 Speed-up ratio contrast of nbench圖6 nbench加速比對(duì)照

測(cè)試結(jié)果如圖6和圖7所示.在未優(yōu)化查詢過(guò)程時(shí)，部分用例庫(kù)函數(shù)處理的收益小于查詢開銷，因此整體呈現(xiàn)負(fù)加速.為了形成鮮明對(duì)比，圖6和圖7中的縱軸使用自然數(shù)指數(shù)為坐標(biāo).當(dāng)數(shù)據(jù)柱高于1時(shí)未正加速，低于時(shí)為負(fù)加速.對(duì)比圖6和圖7中的測(cè)試結(jié)果，從整體上看，本文優(yōu)化方法對(duì)spec測(cè)試用例的效果要優(yōu)于對(duì)nbench測(cè)試用例的優(yōu)化效果，這是測(cè)試集自身的特性造成的.nbench測(cè)試集主要是針對(duì)處理器性能進(jìn)行了的測(cè)試，其中需要函數(shù)處理翻譯實(shí)現(xiàn)的代碼較少，因此查詢的次數(shù)較少，可優(yōu)化的空間也小.spec測(cè)試集針對(duì)的是一些典型算法實(shí)現(xiàn)效率，調(diào)用函數(shù)的次數(shù)較多，庫(kù)函數(shù)處理查詢的次數(shù)較多，優(yōu)化的空間更大.

Fig. 7 Speed-up ratio contrast of spec2006圖7 spec2006加速比對(duì)照

4.3 結(jié)果分析

通過(guò)nbench和spec2006中2組加速比的對(duì)照，可以發(fā)現(xiàn)，經(jīng)過(guò)查詢優(yōu)化的庫(kù)函數(shù)處理翻譯方式，相較于未優(yōu)化的翻譯方式，平均加速比有明顯的提升.對(duì)于部分有負(fù)加速的測(cè)試用例，其提升效果更佳明顯.例如nbench中的nueural_net和lu_decomposition用例以及spec2006中的sjeng用例.

查詢優(yōu)化的效果對(duì)于負(fù)加速的例子優(yōu)化較為明顯.這是對(duì)本文優(yōu)化方法有效性的有力佐證.因?yàn)樵谖磧?yōu)化的庫(kù)函數(shù)處理翻譯模式下，因?yàn)椴樵兊拈_銷過(guò)大，當(dāng)查詢失敗時(shí)，庫(kù)函數(shù)處理過(guò)程完全成為翻譯過(guò)程的額外開銷，此時(shí)相較于一般的翻譯處理方式，庫(kù)函數(shù)處理過(guò)程會(huì)顯現(xiàn)出負(fù)加速.因此，降低庫(kù)函數(shù)處理過(guò)程中查詢的開銷，使得即使查詢失敗額外開銷也不明顯，這樣可以使得有限的庫(kù)函數(shù)處理獲得的收益盡可能地不被查詢開銷消耗.

而其他例子的加速效果和用例的2個(gè)特征有關(guān)：1)庫(kù)函數(shù)調(diào)用次數(shù)以可以處理的庫(kù)函數(shù)比例；2)用例程序整體的指令規(guī)模.

測(cè)試結(jié)果中，npb中string_sort和fourier用例以及spec2006中的mcf和hmmer用例具有較好的加速比.相較于其他用例，這幾個(gè)用例在翻譯執(zhí)行的過(guò)程中，可處理庫(kù)函數(shù)指令的規(guī)模在程序整體的指令規(guī)模中占比較高.spec006中翻譯可處理庫(kù)函數(shù)在源程序執(zhí)行過(guò)程中指令數(shù)占源程序執(zhí)行的指令總數(shù)比例如圖8所示：

Fig. 8 Instruction ratio of disposing library functions to whole圖8 可處理庫(kù)函數(shù)指令占比

由此可見，庫(kù)函數(shù)處理的優(yōu)化加速類似于并行加速，執(zhí)行過(guò)程中可處理庫(kù)函數(shù)的翻譯執(zhí)行過(guò)程屬于可優(yōu)化的部分，因此這部分程序的比例決定了庫(kù)函數(shù)處理優(yōu)化加速的效果.而查詢過(guò)程的優(yōu)化即降低了庫(kù)函數(shù)處理決策的開銷，從而保證了此翻譯方式的優(yōu)化效果.

5 相關(guān)研究

動(dòng)態(tài)二進(jìn)制翻譯中的庫(kù)函數(shù)處理在函數(shù)解析的層面上和軟件逆向技術(shù)的需求是一致的；在語(yǔ)義解析的基礎(chǔ)上完成本地代碼生成，因此動(dòng)態(tài)二進(jìn)制翻譯可以歸類于即時(shí)編譯技術(shù)的一類具體應(yīng)用.

在語(yǔ)義解析時(shí)，由于庫(kù)函數(shù)處理進(jìn)行了函數(shù)級(jí)的語(yǔ)義解析，因此可以實(shí)現(xiàn)更有效的即使編譯以達(dá)到更高效的翻譯效率.

在同架構(gòu)跨操作系統(tǒng)的移植系統(tǒng)中，比較知名的應(yīng)用有wine.在跨架構(gòu)的aa軟件移植以及虛擬化系統(tǒng)中，QEMU成為研究的主流平臺(tái)[18-19].

然而，在相關(guān)研究中，源程序語(yǔ)義的解析，語(yǔ)義元素在本地實(shí)現(xiàn)的優(yōu)化始終是研究的重點(diǎn).庫(kù)函數(shù)處理的翻譯方式在解析和本地實(shí)現(xiàn)2個(gè)層面都有所優(yōu)化，因此具有較好的應(yīng)用前景[20-21].

6 總 結(jié)

本文針對(duì)動(dòng)態(tài)二進(jìn)制翻譯中庫(kù)函數(shù)處理翻譯模式中的查詢開銷，給出了一種優(yōu)化的查詢方法.該方法充分解析了庫(kù)函數(shù)處理過(guò)程內(nèi)在動(dòng)靜結(jié)合的性質(zhì)，通過(guò)將查詢信息靜態(tài)預(yù)處理，使用散列函數(shù)實(shí)現(xiàn)查詢過(guò)程等手段，實(shí)現(xiàn)了源程序中庫(kù)函數(shù)地址到相對(duì)應(yīng)處理函數(shù)的快速映射，降低了查詢開銷.通過(guò)基于動(dòng)態(tài)二進(jìn)制翻譯器QEMU的實(shí)驗(yàn)驗(yàn)證，該方法針對(duì)庫(kù)函數(shù)查詢開銷的優(yōu)化是有效的.