openEuler 中C 標(biāo)準(zhǔn)庫替換的兼容性分析

吳亦澤 于佳耕 鄭 晨 武延軍,3

1 （中國科學(xué)院軟件研究所 北京 100190）

2 （中國科學(xué)院大學(xué) 北京 101408）

3 （計算機(jī)科學(xué)國家重點實驗室（中國科學(xué)院軟件研究所）北京 100190）

應(yīng)用程序編程接口（application programming interface，API）是為其他軟件提供服務(wù)的軟件接口[1]，將計算機(jī)與軟件或軟件與軟件連接，為軟件開發(fā)者提供幫助.應(yīng)用軟件使用操作系統(tǒng)提供的功能時，需要調(diào)用操作系統(tǒng)提供的API.在Linux 各發(fā)行版中，為了讓應(yīng)用開發(fā)者能更方便地使用系統(tǒng)API 以實現(xiàn)更復(fù)雜的功能，系統(tǒng)將API 進(jìn)一步封裝至C 標(biāo)準(zhǔn)庫（本文簡稱C 庫）中，并將C 庫的API 供用戶調(diào)用.C 庫連接了應(yīng)用軟件和操作系統(tǒng)，C 庫的接口實現(xiàn)影響應(yīng)用軟件對系統(tǒng)功能的使用.如果應(yīng)用軟件不能通過調(diào)用C庫接口來和系統(tǒng)建立聯(lián)系，很多關(guān)鍵的應(yīng)用功能也將無法實現(xiàn).

常見的GNU/Linux 類桌面和服務(wù)器系統(tǒng)都采用GNU C library（glibc）這套C 語言標(biāo)準(zhǔn)庫，它實現(xiàn)了多種多樣的C 庫接口，支持各類系統(tǒng)平臺，功能十分齊全.glibc 使用LGPL v2.1（GNU Lesser General Public License v2.1）協(xié)議.與GPL（GNU General Public License）協(xié)議要求“任何使用、修改和衍生GPL 庫的軟件必須采用GPL 協(xié)議并開源”不同的是，LGPL 允許軟件通過類庫引用的方式使用LGPL 庫而無需開源，但對于系統(tǒng)開發(fā)者而言，在對庫進(jìn)行修改或衍生時LGPL仍具有限制性和傳染性.因此，在商業(yè)化系統(tǒng)中使用glibc 存在強(qiáng)制開源的不便和安全問題.

為了避免系統(tǒng)搭載的C 庫因開源協(xié)議而在商業(yè)化場景下帶來問題，開源歐拉（openEuler）操作系統(tǒng)商業(yè)發(fā)行版的開發(fā)者正在考慮用musl libc 替換glibc.musl libc 是一個使用MIT 許可證的輕量級C 庫，MIT許可證在有版權(quán)聲明的條件下允許任意地使用、復(fù)制、修改和散布軟件而無需開源.musl libc 可用于從小型嵌入式系統(tǒng)到通用桌面、服務(wù)器系統(tǒng)的很多場景，具有體量小、魯棒性和安全性強(qiáng)、易于裝載等優(yōu)勢.因其基礎(chǔ)架構(gòu)較為成熟，使用的協(xié)議也適用于商業(yè)場景，故musl libc 成為替換glibc 的首要選擇.

新C 庫對原有應(yīng)用軟件的兼容是C 庫替換工作的關(guān)鍵——新C 庫應(yīng)當(dāng)保證在原有C 庫下能正確運行的應(yīng)用軟件在替換后也能正確運行.目前，musl libc 相比glibc 有較多功能缺失，如果直接進(jìn)行替換，將導(dǎo)致C 庫對應(yīng)用軟件的兼容性較低，而低兼容性嚴(yán)重影響操作系統(tǒng)提供的服務(wù)質(zhì)量，降低商業(yè)系統(tǒng)的市場競爭力.因此，在替換前需要通過補(bǔ)全開發(fā)將musl libc 的兼容性提高到足夠高的水平.

兼容性分析對新C 庫的開發(fā)很有幫助[2]，然而現(xiàn)有的兼容性分析方法并不適用于openEuler 對musl libc 的補(bǔ)全工作（見1.3 節(jié)和6.3 節(jié)）.針對這個問題，本文提出新的兼容性分析算法來研究openEuler 的4 種主要軟件生態(tài)中的musl libc 兼容性和缺失API 優(yōu)先級.本文的研究目的是幫助openEuler 的C 庫開發(fā)者了解musl libc 在openEuler 操作系統(tǒng)上的兼容性，并參照優(yōu)先級順序補(bǔ)全開發(fā)接口，合理安排開發(fā)工作.

本文的主要貢獻(xiàn)有4 個方面：

1）量化對比了musl libc 與glibc 的接口.根據(jù)接口開發(fā)現(xiàn)狀，將全部接口劃分為主要接口和非主要接口，并分別進(jìn)行接口對比分析，量化了musl libc 和glibc 的接口差異和重合率，論證了對musl libc 進(jìn)行補(bǔ)全的必要性和可行性.

2）量化分析了musl libc 對應(yīng)用軟件生態(tài)的兼容情況.根據(jù)應(yīng)用軟件對缺失API 的調(diào)用情況和應(yīng)用之間的依賴關(guān)系提出了兼容的定義，將依賴關(guān)系構(gòu)建為圖模型，將兼容的定義形式化，并統(tǒng)計分析了應(yīng)用軟件生態(tài)的兼容情況.

3）提出了兼容性度量算法——PackageRank.PackageRank 在圖模型上為應(yīng)用軟件賦分，并通過計算兼容應(yīng)用的得分占比來度量兼容性.

4）提出了缺失API 優(yōu)先級算法——APIRank.APIRank 是PackageRank 的延伸，根據(jù)缺失API 被應(yīng)用軟件調(diào)用的情況，對圖模型作出進(jìn)一步擴(kuò)展，并在新的圖模型上為API 賦分，以度量缺失API 的優(yōu)先級.

1 相關(guān)工作

1.1 C 標(biāo)準(zhǔn)庫

除glibc 和musl libc 外，還有多種其他C 標(biāo)準(zhǔn)庫的實現(xiàn)，如eglibc，uClibc，dietlibc 等.eglibc 是glibc 的一個分支，專為嵌入式場景設(shè)計，嚴(yán)格兼容二進(jìn)制的glibc，使用LGPL v2.1 協(xié)議，2014 年初停止開發(fā)；uClibc為嵌入式Linux 系統(tǒng)開發(fā)，其迎合小型C 庫需求，使用LGPL v2.1 協(xié)議，自2012 年5 月以來未有新發(fā)行版本；dietlibc 適用于小型場景，可以為多種體系結(jié)構(gòu)的Linux系統(tǒng)提供靜態(tài)鏈接二進(jìn)制庫，使用GPL v2 協(xié)議，最新版本于2018 年9 月發(fā)行，版本間隔為4～5 年.相較之下，musl libc 使用MIT 協(xié)議，版本更新周期為6～12個月，最新版本發(fā)布于2022 年4 月.

musl libc 官方發(fā)布了對自己C 庫的兼容性分析報告[3]，將musl libc（1.1.24）與多種C 語言標(biāo)準(zhǔn)和其他C 庫進(jìn)行了比較.分析顯示，musl libc 對POSIX 2008，C99，C11 標(biāo)準(zhǔn)的兼容性良好，分別有12 個、2 個、88個API 未實現(xiàn)，對比POSIX 2008 標(biāo)準(zhǔn)有2 個API 有函數(shù)原型但沒有實現(xiàn).在與glibc，uClibc，dietlibc 進(jìn)行對比時，musl libc 的魯棒性、安全性、構(gòu)建環(huán)境適配性均優(yōu)于其他C 庫；性能和體系結(jié)構(gòu)適配性略低于glibc 而遠(yuǎn)優(yōu)于uClibc 和dietlibc；體量略大于dietlibc，略小于uClibc，遠(yuǎn)小于glibc.此外，musl libc 在I/O、信號處理、正則表達(dá)式功能和動態(tài)鏈接等方面與glibc存在功能性差異.

我們在Ubuntu 20.04 桌面版（Intel?Core? i7-8550U CPU @ 1.80GHz 2.00 GHz）上使用libc-bench-20110206[4]測試集分別對glibc（2.34）和musl libc（1.2.2）作了性能和內(nèi)存占有量的測試，測試結(jié)果展示在圖1中，其中測試用例和測試項目的含義見libc-bench[4].

Fig.1 Experimental results of performance and memory usage on glibc and musl libc圖1 glibc 與musl libc 的性能和內(nèi)存占有量實驗結(jié)果

數(shù)據(jù)顯示，musl libc 在27 個測試中僅有3 個的性能比glibc 更高（運行時間更短），而內(nèi)存占有量則有24 個更?。ㄇ一径加忻黠@的優(yōu)勢）.這表明，雖然musl libc 的性能仍需提升，但其內(nèi)存占有量低，因此補(bǔ)全開發(fā)工作將更為方便和靈活.

綜合以上分析，musl libc 架構(gòu)成熟，許可協(xié)議對商用友好，適合進(jìn)行補(bǔ)全開發(fā)和C 庫替換.另一方面，性能較低、功能有差別和缺陷等問題使得直接替換并不可行，補(bǔ)全開發(fā)工作是必要的.

1.2 openEuler

openEuler 是一個開源、免費的Linux 發(fā)行版平臺，它通過開放形式的社區(qū)與全球的開發(fā)者共同構(gòu)建一個開放、多元和架構(gòu)包容的軟件生態(tài)體系.2020年3 月，openEuler 社區(qū)正式發(fā)布了首個長期支持版本——openEuler 20.03 LTS，并與多家操作系統(tǒng)廠商共同發(fā)布了基于openEuler 的商業(yè)系統(tǒng)發(fā)行版.openEuler每6 個月發(fā)布一個社區(qū)創(chuàng)新版本，提供6 個月社區(qū)支持，而LTS 版本的發(fā)布間隔周期為2 年，提供4 年社區(qū)支持.目前，openEuler 22.03 LTS 已經(jīng)發(fā)布，有多家國內(nèi)外機(jī)構(gòu)宣布將推出基于openEuler 22.03 LTS 的商業(yè)發(fā)行版.

1.3 兼容性研究

在兼容性度量方法中，一種簡單而直接的方法是計數(shù)滿足兼容條件的API 個數(shù)[5-8].其算法比較容易實現(xiàn)，但缺乏準(zhǔn)確性，即只關(guān)注API 本身是否兼容，并未考慮真實場景的API 調(diào)用情況.

一些兼容性研究者已經(jīng)意識到應(yīng)當(dāng)在度量方法中引入應(yīng)用軟件對API 調(diào)用情況進(jìn)行考量，而單一內(nèi)核（unikernel）的出現(xiàn)也啟發(fā)了他們做出這樣的改變.單一內(nèi)核由應(yīng)用程序與其依賴的系統(tǒng)組件的最小集打包制成，具有單一地址空間，可以直接在管理程序（hypervisor）或硬件層面運行[9].由于單一內(nèi)核是根據(jù)應(yīng)用需求搭建的最小集，它必須確保囊括的API 足夠兼容應(yīng)用.一種搭建思路是以現(xiàn)有通用系統(tǒng)的構(gòu)件為基礎(chǔ)進(jìn)一步開發(fā)，例如Rumprun[10]和OSv[11]是由BSD 模塊重組生成，Lupine Linux[12]則采用了Linux內(nèi)核的特殊配置和Kernel Mode Linux 補(bǔ)丁.另外還可以設(shè)計API 兼容層來增強(qiáng)自己系統(tǒng)的兼容性[13-14].這樣搭建的單一內(nèi)核仍在使用通用系統(tǒng)的API 標(biāo)準(zhǔn)，因此兼容性是其開發(fā)過程的關(guān)鍵，它們的兼容性度量也應(yīng)當(dāng)從API 調(diào)用的角度出發(fā).

文獻(xiàn)[2]以Ubuntu 15.04 為基準(zhǔn)，分析了其他一些Linux 類系統(tǒng)或構(gòu)件（系統(tǒng)調(diào)用、C 庫、文件系統(tǒng)等）的API 重要性（API importance）和加權(quán)完整性（weighted completeness）.文獻(xiàn)[2]的作者認(rèn)為“產(chǎn)生兼容性度量不準(zhǔn)確問題的根本原因是缺乏對系統(tǒng)API 在實際中被調(diào)用情況的數(shù)據(jù)統(tǒng)計和分析”.該文獻(xiàn)利用Ubuntu/Debian 的應(yīng)用軟件安裝次數(shù)統(tǒng)計，從概率角度度量其他系統(tǒng)或構(gòu)件的兼容性.該文提出2個度量概念：

1）API 重要性.一部操作系統(tǒng)上會安裝多個應(yīng)用軟件，這樣的一個“安裝集”是該文獻(xiàn)統(tǒng)計的基本單位.API 的重要性定義為“調(diào)用該API 的應(yīng)用被安裝的概率”.一個應(yīng)用軟件被安裝的概率是包含該應(yīng)用的安裝集個數(shù)（該應(yīng)用的安裝次數(shù)）與所有安裝集個數(shù)（即系統(tǒng)總安裝次數(shù)）的比值，將不同應(yīng)用軟件的安裝視為獨立事件，便可以通過將所有調(diào)用某個API 的應(yīng)用軟件的安裝概率相乘，來計算API 重要性.

2）加權(quán)完整性.加權(quán)完整性用于度量系統(tǒng)或構(gòu)件對應(yīng)用的兼容性.應(yīng)用軟件分為被支持的（supported）和不被支持的（unsupported），而加權(quán)完整性的定義為“安裝集中被支持應(yīng)用數(shù)量占該集中所有應(yīng)用數(shù)量的比值的數(shù)學(xué)期望”.仍將不同應(yīng)用軟件的安裝視為獨立事件，便能計算出加權(quán)完整性的估計值.

許多有待進(jìn)一步開發(fā)的系統(tǒng)構(gòu)件都有API 兼容性上的不足，但也有研究表明Linux API 提供的功能是溢出的.Quach 等人[15]認(rèn)為現(xiàn)代Linux 內(nèi)核中無用的二進(jìn)制內(nèi)容可能引發(fā)棧膨脹（stack bloating），而DeMarinis 等人[16]指出多余的API 為系統(tǒng)黑客留下了更大的攻擊面.這些研究也從另一個角度辯證地解讀了兼容性：兼容作用應(yīng)當(dāng)貼合應(yīng)用的需求，盲目地追求兼容可能帶來負(fù)面效果，提升API 兼容性的開發(fā)工作需要有的放矢.

本文采用靜態(tài)分析度量兼容性，此外還可以采用動態(tài)分析或靜態(tài)和動態(tài)分析結(jié)合的方法.文獻(xiàn)[2]也采用了靜態(tài)分析度量系統(tǒng)和構(gòu)件的兼容性，Cui 等人[17]利用動態(tài)二進(jìn)制翻譯（dynamic binary translation）技術(shù)分析了Intel SGX Enclaves 的系統(tǒng)調(diào)用的兼容性，Atlidakis 等人[18]將靜態(tài)和動態(tài)結(jié)合來分析POSIX標(biāo)準(zhǔn)是否仍符合現(xiàn)代應(yīng)用的需求.鄭煒等人[19]總結(jié)了近年來安卓移動應(yīng)用兼容性的靜態(tài)和動態(tài)分析方法.動態(tài)分析收集程序的運行時數(shù)據(jù)，比靜態(tài)分析更加接近實際場景，但往往又無法準(zhǔn)確模擬程序?qū)嶋H工作時的行為.在兼容性研究中，測試用例的選取不當(dāng)會導(dǎo)致兼容問題不能在測試中暴露，降低兼容性分析的準(zhǔn)確性.

2 musl libc 與glibc 的接口對比

本節(jié)將進(jìn)行musl libc 與glibc 的接口對比分析.本節(jié)的結(jié)果是本文后續(xù)內(nèi)容的基礎(chǔ)和依據(jù).

在本文的研究中，musl libc 和glibc 均由官方倉庫源碼編譯并安裝，見表1.編譯C 庫時使用的編譯器是x86_64-linux-gnu-gcc 9.4.0，安裝C 庫的系統(tǒng)是Ubuntu 20.04 桌面版.

Table 1 Versions and Repository Addresses of C Libraries表1 C 庫的版本號與倉庫地址

2.1 接口名稱提取

鏈接器在鏈接時需要知道庫文件內(nèi)部定義了哪些接口，這要求被鏈接接口的信息必須完整保存在庫文件的符號表中.因此，可以從庫文件的符號表內(nèi)提取接口名稱.

本文研究中的接口名稱提取自C 庫中的可執(zhí)行文件（executable and linkable format，ELF）.具體方法為：遍歷C 庫所在目錄中的所有文件，讀取其中每個ELF的符號表.對于每個符號表項，如果其類型（type）為FUNC 或IFUNC 且可見度（bind）為GLOBAL 或 WEAK，則提取其符號名（name）.這樣提取的接口名稱僅包含可被鏈接的接口，而不可鏈接的接口與C 庫的兼容無關(guān)（僅定義在內(nèi)部，不能被應(yīng)用軟件調(diào)用），故不在本文的研究范圍內(nèi).

經(jīng)過提取，glibc 共有6 466 個接口，musl libc 共有1 898 個.

2.2 主要接口

C 庫的接口有這樣的命名習(xí)慣：以字母起始的接口供用戶調(diào)用，以下劃線起始的接口實現(xiàn)內(nèi)部和底層的功能（與操作系統(tǒng)交互、初始化和退出、編譯優(yōu)化等）.例如，printf 是標(biāo)準(zhǔn)輸出的常用接口，而__libc_start_main 是C 程序初始化啟動的一部分，gcc 在編譯時可能會將printf 替換為_printf_chk 以防止棧溢出[2].本文將名稱以字母起始的接口稱為主要接口.

應(yīng)用軟件開發(fā)者應(yīng)該避免直接調(diào)用非主要接口[20]，故C 庫的底層差異不會導(dǎo)致兼容問題.然而，在靜態(tài)分析應(yīng)用軟件對接口的調(diào)用情況時，非主要接口可能會帶來兼容性的誤判.例如，應(yīng)用軟件調(diào)用的printf在gcc 編譯時被替換為_printf_chk，由于musl libc 未實現(xiàn)_printf_chk，所以分析結(jié)果將顯示該應(yīng)用軟件調(diào)用了未實現(xiàn)的接口，從而存在兼容問題.但是，如果使用musl-gcc 編譯，程序可以正確鏈接musl libc 的printf 接口，所以兼容問題實際上并不存在.

雖然本文的研究角度是二進(jìn)制兼容，但這樣的誤判將導(dǎo)致兼容性分析結(jié)果不準(zhǔn)確，這是我們希望避免的.因此，本文在兼容性度量時只對主要接口做統(tǒng)計和分析.除特別注明外，后文中所述的結(jié)果均以主要接口為研究對象.

經(jīng)篩選，glibc 有2 883 個主要接口，musl libc 有1 516 個.

2.3 接口對比分析

全部接口和主要接口的統(tǒng)計結(jié)果見表2.除接口數(shù)量外，為比較C 庫的接口實現(xiàn)相似度，表2 還統(tǒng)計了接口重合率，即C 庫的共同接口數(shù)與該C 庫在該項的總接口數(shù)的比值.

Table 2 APIs Comparison of musl libc and glibc表2 musl libc 和glibc 的接口對比

結(jié)果顯示，2 個C 庫的主要接口重合率均遠(yuǎn)高于各自的非主要接口重合率（glibc：52.2%和5.6%；musl libc：99.2%和52.1%）.這表明C 庫頂層接口的相似度較高，而底層實現(xiàn)區(qū)別較大.此外，glibc 中55%（3 583/6 466）的接口為非主要接口，可見其底層實現(xiàn)十分復(fù)雜，大量的非主要接口將嚴(yán)重影響接口對比結(jié)果的準(zhǔn)確性，對后續(xù)的分析也不利，而只分析主要接口便能避免這個問題.

musl libc 的主要接口集幾乎完全包含在glibc 的主要接口集中（重合率為99.2%）.因此，從主要接口的角度來看，musl libc 可以基本被視為glibc 的子集.這表明musl libc 充分遵從了glibc 的接口命名習(xí)慣，為open-Euler 的C 庫移植和替代工作帶來了很大便利.但同時，musl libc 的主要接口僅覆蓋glibc 主要接口的一半左右（52.2%），這也勢必降低了musl libc 對應(yīng)用軟件的兼容性.

表3 列出的12 個主要接口是musl libc 獨有的.我們在統(tǒng)計應(yīng)用軟件調(diào)用接口的情況（具體方法見第3 節(jié)）后發(fā)現(xiàn)，這12 個接口均未被任何應(yīng)用軟件調(diào)用.值得一提的是，接口strlcat 和strlcpy 其實在應(yīng)用軟件中十分常見，雖然glibc 并未實現(xiàn)這2 個接口，但應(yīng)用開發(fā)者仍會想辦法使用它們：有些開發(fā)者將它們實現(xiàn)在自己的鏈接庫中（例如x86_64 的multipathtools-0.8.5-7，strlcpy），有些靜態(tài)鏈接了他們自己編寫的函數(shù)（例如aarch64 的entr-4.5-1，strlcpy）.也正因如此，這些應(yīng)用軟件才能夠在glibc 下正確調(diào)用這2 個接口.

Table 3 Main APIs Owned by musl libc表3 musl libc 獨有的主要接口

musl libc 相比glibc 有1 379 個主要接口尚未實現(xiàn)，但它們的情況與musl libc 獨有的12 個接口截然不同.由于glibc 的廣泛使用，應(yīng)用軟件開發(fā)者一般都遵循glibc 的規(guī)范而進(jìn)行相應(yīng)的編程適配.如果開發(fā)者認(rèn)為glibc 已經(jīng)實現(xiàn)了某個接口，他們大多會選擇直接調(diào)用它而不會再自行實現(xiàn)該接口，因為非標(biāo)準(zhǔn)實現(xiàn)不僅帶來了更大的工作量，而且存在安全性隱患，也不利于代碼復(fù)用和移植.然而，開發(fā)者想要調(diào)用的接口可能是musl libc 未實現(xiàn)的，這便引發(fā)了musl libc 的兼容性問題.

“接口重合率”是度量兼容性的一種思路.如果將其用于本文的研究，能得到結(jié)論：musl libc 的兼容性是52.2%.然而，這種思路并未考慮被兼容的應(yīng)用軟件所包含的信息.C 庫通過實現(xiàn)接口來為應(yīng)用軟件提供功能支持，而應(yīng)用軟件通過調(diào)用接口來滿足自身的功能需求.在兼容的過程中，主體是C 庫，客體是應(yīng)用軟件，而用接口重合率來度量兼容性的方法僅考慮了主體，而忽略了客體.由此可見，應(yīng)用軟件對C 庫接口的調(diào)用情況也應(yīng)當(dāng)被納入兼容性的度量中.我們將在第4～5 節(jié)中提出了相應(yīng)的算法，更加全面而準(zhǔn)確地度量兼容性，并進(jìn)一步度量了每個缺失API 的優(yōu)先級.

3 應(yīng)用軟件生態(tài)兼容分析

應(yīng)用軟件生態(tài)是指系統(tǒng)上可運行的所有應(yīng)用軟件的集合，本文中簡稱為軟件生態(tài)或生態(tài).不同系統(tǒng)的應(yīng)用軟件生態(tài)不同，故C 庫的兼容情況也有區(qū)別.本文研究musl libc 在openEuler 操作系統(tǒng)的4 種軟件生態(tài)中的兼容性，軟件生態(tài)分別為aarch64 服務(wù)器、x86_64 服務(wù)器、aarch64 嵌入式和x86_64 嵌入式.

openEuler 軟件生態(tài)中的應(yīng)用軟件均可通過RPM（RedHat package manager）格式的軟件包安裝.RPM 包中含有應(yīng)用軟件安裝所需的文件和信息，包括ELF、文檔、協(xié)議等.為提高結(jié)果的準(zhǔn)確性，本文所統(tǒng)計和分析的應(yīng)用軟件生態(tài)均排除了glibc 和musl libc 的基本包與擴(kuò)展包，如表4 所示.

Table 4 Basic Package and Extended Package of C Libraries表4 C 庫的基本包與擴(kuò)展包

本節(jié)將介紹C 庫兼容應(yīng)用軟件的定義，并依照此定義分析4 種生態(tài)中的應(yīng)用軟件兼容情況.

3.1 直接兼容的定義

兼容的直觀判定標(biāo)準(zhǔn)是，新C 庫能否保證應(yīng)用軟件的全部可執(zhí)行文件正確運行.C 庫無法支持可執(zhí)行文件正確運行的原因有很多，被調(diào)用的接口未實現(xiàn)、實現(xiàn)的功能有缺陷或錯誤、應(yīng)用開發(fā)者編程錯誤、鏈接器有漏洞等都是可能的原因.本文只考慮C庫未實現(xiàn)需要調(diào)用的接口的情況，即只要C 庫實現(xiàn)了應(yīng)用軟件調(diào)用的接口，就認(rèn)為該調(diào)用不會發(fā)生錯誤.另一方面，如果C 庫未實現(xiàn)需要調(diào)用的接口，本文也假設(shè)應(yīng)用軟件開發(fā)者未在別處（如自行開發(fā)的鏈接庫中）實現(xiàn)這些接口（2.3 節(jié)中解釋了這樣假設(shè)的合理性）.

既然C 庫接口不會被自行實現(xiàn)，那么應(yīng)用軟件調(diào)用的庫接口便完全依賴C 庫提供.因此，如果C 庫要保證應(yīng)用軟件不出現(xiàn)錯誤，就必須實現(xiàn)應(yīng)用軟件調(diào)用的全部接口.這種“保證”是C 庫對應(yīng)用軟件的直接支持，本文將其稱為直接兼容.

定義1.C 庫直接不兼容應(yīng)用軟件.如果在該應(yīng)用軟件的RPM 包中存在某個ELF，該ELF 調(diào)用了C庫缺失的接口，則C 庫直接不兼容該應(yīng)用軟件.如果不滿足上述條件，則C 庫直接兼容該應(yīng)用軟件.

上述的接口“調(diào)用”指的是靜態(tài)調(diào)用，即ELF 的符號表中存在能夠動態(tài)鏈接該接口的條目.提取符號表中動態(tài)鏈接項的符號名，便提取出了所調(diào)用接口的名稱.

然而，即使“調(diào)用”了C 庫缺失的接口，ELF 運行時也未必會發(fā)生錯誤，因為執(zhí)行流可能并不會經(jīng)過這個接口.例如，某個負(fù)責(zé)崩潰處理功能的接口在符號表中有相應(yīng)的項，但若程序未遇到崩潰，便不會真正調(diào)用它.因此，即使存在對缺失接口的“調(diào)用”，應(yīng)用軟件在運行時也未必出現(xiàn)錯誤.

本文不考慮動態(tài)調(diào)用引起的偏差，即應(yīng)用軟件對任何C 庫缺失接口的靜態(tài)調(diào)用都會被判定為直接不兼容.事實上，可以充分信任應(yīng)用軟件開發(fā)者的編程能力，從而相信這些極少或從未被真正調(diào)用過的接口并非冗余，而是開發(fā)者希望該應(yīng)用實現(xiàn)的功能（如崩潰處理功能）的一部分，它們的缺失也會使應(yīng)用的正確運行不再得到保證.

3.2 不兼容的傳遞性

RPM 包中還記錄著應(yīng)用軟件對其他應(yīng)用軟件的依賴關(guān)系，這種顯式的依賴關(guān)系是功能上的依賴.除此之外，應(yīng)用之間還存在隱性的依賴關(guān)系，例如用戶在使用一個后端應(yīng)用時必須搭配某個前端應(yīng)用才能獲得良好體驗.本文只考慮RPM 包中顯式標(biāo)注的依賴關(guān)系，不考慮其他隱性依賴關(guān)系.

應(yīng)用軟件的兼容與否和它所依賴的其他應(yīng)用軟件有關(guān).對于某個應(yīng)用軟件，即使它所依賴的應(yīng)用軟件使用C 庫時都能正確運行，它也未必能正確運行，故“應(yīng)用是否被兼容”和“所依賴應(yīng)用是否被兼容”沒有直接關(guān)系.但反之，如果所依賴的應(yīng)用不能正確運行，應(yīng)用軟件本身的正確運行便也無法得到保證，則是一個因果關(guān)系.

因此，不兼容具有傳遞性，即C 庫如果不兼容某個應(yīng)用軟件，則也不兼容依賴該應(yīng)用軟件的其他應(yīng)用軟件，即使這些應(yīng)用軟件自身是被直接兼容的.圖2 是一個例子：A，B，C，D這4 個應(yīng)用中，C依賴A，D依賴A和B，E依賴C和D，箭頭表示依賴關(guān)系.庫直接兼容應(yīng)用A，C，D，E，直接不兼容B.雖然D被直接兼容，但因為B是直接不兼容的，而D依賴B，所以B的不兼容傳遞到D，D也不被兼容.同理，D再將不兼容性傳遞到E，E也不被兼容.

Fig.2 Illustration of transitivity of incompatibility圖2 不兼容的傳遞性示意圖

3.3 兼容的定義

從3.1 節(jié)的直接兼容和3.2 節(jié)中的不兼容傳遞性出發(fā)，可以對C 庫兼容應(yīng)用軟件做出定義.

定義2.C 庫是否兼容應(yīng)用軟件.

1）如果C 庫直接不兼容一個應(yīng)用軟件，則C 庫不兼容該應(yīng)用軟件.

2）如果C 庫不兼容一個應(yīng)用軟件所依賴的某個應(yīng)用軟件，則C 庫不兼容該應(yīng)用軟件.

3）如果無法通過以上2 條定義證明C 庫不兼容一個應(yīng)用軟件，則C 庫兼容該應(yīng)用軟件.

定義2是遞歸的.首先有一些應(yīng)用是直接不兼容的，從而依賴它們的應(yīng)用是不兼容的.不兼容性沿著依賴關(guān)系網(wǎng)傳遞，直至所有不兼容的應(yīng)用都被傳遞到，而未被傳遞到的應(yīng)用就是兼容的.

定義2也是無歧義的.該定義將應(yīng)用軟件嚴(yán)格分為兼容的和不兼容的，不存在一個應(yīng)用可以同時被判定為兼容和不兼容的情況.這是非常重要的，因為模糊的定義將從根本上降低兼容性分析結(jié)果的準(zhǔn)確性.

3.4 軟件生態(tài)圖

定義2是自然語言表述的兼容定義，不利于直接用于判定應(yīng)用軟件是否兼容.數(shù)學(xué)化的模型在判定時將更為有效.

應(yīng)用軟件之間的依賴關(guān)系存在方向性.由此，可以將整個軟件生態(tài)視為一張有向圖，應(yīng)用軟件與圖中的點一一對應(yīng)，而依賴關(guān)系與圖中的有向邊也一一對應(yīng).我們把這樣的圖模型稱為軟件生態(tài)圖.

定義3.軟件生態(tài)圖.它是一張表示軟件生態(tài)中的應(yīng)用軟件及其之間依賴關(guān)系的有向圖.圖中的每個點對應(yīng)生態(tài)中的一個應(yīng)用軟件，每條邊對應(yīng)一個依賴關(guān)系，邊的方向規(guī)定為：應(yīng)用A依賴應(yīng)用B，對應(yīng)從A指向B的邊.

在軟件生態(tài)圖中，我們把被兼容的應(yīng)用稱為兼容點，不被兼容的應(yīng)用稱為不兼容點，同理也有直接兼容點和直接不兼容點.我們提出定義2 在軟件生態(tài)圖模型下的一個等價定義，并證明其等價性.

定義4.軟件生態(tài)圖中的不兼容點.它是那些可通過圖中的路徑到達(dá)直接不兼容點的結(jié)點（路徑長度可以為0），即

其中Sdi是直接不兼容（directly incompatible）的結(jié)點集，(v,vn,vn1,…,v1,v0)表示從v經(jīng)過vn,vn-1，…，v1到v0的路徑.

定義4與定義2 的等價性證明為：

1）對于可通過一條路徑到達(dá)直接不兼容點的點，如果這條路徑長度為0，則該點是直接不兼容點，當(dāng)然也是不兼容點；否則，可以將該點記為a，路徑記為（a,an,an-1, …,a1,a0），n≥0，a0是直接不兼容點.根據(jù)定義2，a0是不兼容點，a1因為依賴了不兼容點a0，也是不兼容點.反復(fù)進(jìn)行推理可知，a1, …,an-1,an,a都是不兼容點.

2）對于一個不兼容點b，現(xiàn)在要找到一條從它到某個不兼容點的路徑.根據(jù)定義2 第3 條，一定存在證明b是不兼容點的方法.也就是說，通過某種方法運用定義2 的第1 條和第2 條，最終可以推導(dǎo)出b不兼容.如果運用了定義2 的第1 條，即b是直接不兼容點，則長度為0 的路徑即為所求；否則，它依賴另一個不兼容點（第2 條），即存在從它到另一個不兼容點b0的邊.如果b0是直接不兼容點，則證明完成；否則，又存在b0到另一個不兼容點b1的邊.反復(fù)進(jìn)行這樣的推理，如果一直沒有訪問直接不兼容點，將不斷訪問b,b0,b1, …點序列，點序列與推理過程是一一對應(yīng)的.也就是說，既然存在b是不兼容點的證明方法，就存在相應(yīng)的點序列.可以認(rèn)為證明方法對應(yīng)的點序列是無重復(fù)的（序列中每個點都是不同的），因為出現(xiàn)重復(fù)點意味著推理過程遍歷了一個環(huán)，而這又意味著循環(huán)論證.循環(huán)論證本身不能作為證明方法，故最終還是需要從某個點跳出這個環(huán)才能完成證明，故不妨第一次訪問“跳出點”時就跳出，訪問過程便沒有了環(huán).又由于圖中點的個數(shù)有限，故無重復(fù)的點序列只能是有限長度的，因而可以把證明方法對應(yīng)的點序列記作b,b0,b1, …,bn,n≥0.這表明，整個推理過程只會重復(fù)有限次便停止在bn，而推理停止的唯一原因為bn是直接不兼容點.（b,b0,b1, …,bn）就是所求路徑.

根據(jù)定義4，只要遍歷某個應(yīng)用結(jié)點的所有無環(huán)路徑，就可以判定該應(yīng)用是否被兼容.

3.5 應(yīng)用軟件生態(tài)兼容分析結(jié)果

表5 展示了openEuler 的4 種軟件生態(tài)的musl libc 兼容情況，其中第n級不兼容數(shù)的含義為在第n輪傳遞后新增加的不兼容應(yīng)用個數(shù)，兼容率為被兼容的應(yīng)用個數(shù)占全部應(yīng)用個數(shù)的比例.

Table 5 Statistics of Compatible Applications in the Four Ecosystems表5 4 種生態(tài)中的兼容的應(yīng)用軟件統(tǒng)計

比較表5 中數(shù)據(jù)發(fā)現(xiàn)，C 庫在相同應(yīng)用場景（服務(wù)器或嵌入式）、不同體系結(jié)構(gòu)下有著相近的直接兼容率和不兼容傳遞模式，而在相同體系結(jié)構(gòu)、不同應(yīng)用場景下數(shù)據(jù)的差異很大：服務(wù)器場景中兼容率分別為31.89%和31.87%，其各級不兼容傳遞的應(yīng)用個數(shù)分別為537/547，6 936/6 985，4 721/4 727，198/190，7/10；嵌入式場景中兼容率分別為45.24%和44.58%，其各級不兼容傳遞的應(yīng)用個數(shù)分別為33/33，13/13.而在不同應(yīng)用場景下，兼容率的差值分別為13.35%（aarch64）和12.71%（x86_64），不兼容傳遞模式也有明顯區(qū)別.

這表明，軟件生態(tài)兼容情況受應(yīng)用場景的影響很明顯，而受硬件體系結(jié)構(gòu)的影響很微弱.

4 兼容性算法

兼容性的度量是許多系統(tǒng)開發(fā)者的需求，而好的度量方法是獲得優(yōu)質(zhì)度量結(jié)果的關(guān)鍵所在.

3.5 節(jié)中提到的兼容率是一種樸素的度量方法，它基于一個簡單的數(shù)學(xué)原理——計數(shù).每個應(yīng)用軟件都在計數(shù)時被同等地視作“1”，兼容應(yīng)用的個數(shù)和所有應(yīng)用的個數(shù)的比值就是度量結(jié)果.因此，兼容率不能體現(xiàn)不同應(yīng)用軟件之間的差別.

應(yīng)用軟件在生態(tài)中的重要性并不等同，這種差異體現(xiàn)在：

1）系統(tǒng)用戶的角度.生態(tài)中的一些應(yīng)用提供的功能十分基礎(chǔ)，很多其他應(yīng)用都依賴有基礎(chǔ)功能的應(yīng)用，這些“基礎(chǔ)應(yīng)用”往往存在于不同用戶所使用的應(yīng)用軟件的交集中.例如，所有的Python 擴(kuò)展包都需要Python 解釋器來運行，故Python 解釋器便時常存在于交集中.用戶樂于身處能滿足他們個性化需求的軟件生態(tài)中，而這源于基礎(chǔ)應(yīng)用對生態(tài)中其他應(yīng)用的廣泛支持.對整個用戶群體而言，基礎(chǔ)應(yīng)用正常工作時的收益和崩潰時的損失都比其他應(yīng)用更大，這便是應(yīng)用重要性差異的體現(xiàn).

2）應(yīng)用軟件開發(fā)者的角度.應(yīng)用軟件開發(fā)者大多選擇以那些已經(jīng)廣泛支持其他應(yīng)用的應(yīng)用為基礎(chǔ)，開發(fā)自己的應(yīng)用軟件，因為基礎(chǔ)應(yīng)用的功能豐富，正確性和安全性得到廣泛的實踐驗證，一般能得到持續(xù)穩(wěn)定的維護(hù)，從而使得開發(fā)工作更加便捷、產(chǎn)品穩(wěn)定性更佳、產(chǎn)品便于和其他應(yīng)用互通或適配，等等.這些優(yōu)勢使得開發(fā)者的產(chǎn)品更受用戶青睞，而這又促使更多開發(fā)者在這些基礎(chǔ)應(yīng)用之上開展工作，形成以基礎(chǔ)應(yīng)用為中心、其他應(yīng)用對其依賴的生態(tài)結(jié)構(gòu)，這是應(yīng)用重要性差異的又一體現(xiàn).

本節(jié)基于3.4 節(jié)中的軟件生態(tài)圖模型，提出了利用PackageRank 算法計算應(yīng)用軟件的重要性和C 庫的兼容性，以在兼容性度量時體現(xiàn)重要性差異.

4.1 影響應(yīng)用軟件重要性的因素

應(yīng)用軟件之間的依賴關(guān)系能反映其重要性差異.不論是從系統(tǒng)用戶還是應(yīng)用軟件開發(fā)者的角度，依賴關(guān)系都和應(yīng)用軟件重要性有著緊密的聯(lián)系.

被大量應(yīng)用軟件依賴的應(yīng)用軟件相對更加重要.然而，把被依賴次數(shù)當(dāng)作應(yīng)用軟件的重要性也有失偏頗，如某個“只被一個很重要的應(yīng)用依賴”的應(yīng)用可能比“被多個很不重要的應(yīng)用依賴”的應(yīng)用更重要，因為它事關(guān)生態(tài)中的重要應(yīng)用軟件的正常運行.

綜上所述，應(yīng)用軟件的重要性受2 種因素影響：

1）被其他應(yīng)用依賴的次數(shù)；

2）依賴它的應(yīng)用的重要性.

4.2 PackageRank 算法

PackageRank 算法是本文提出的兼容性度量算法.該算法分為2 個部分：計算應(yīng)用軟件的重要性、計算C 庫的兼容性.

4.2.1 計算應(yīng)用軟件的重要性

PackageRank 算法同時考慮了4.1 節(jié)所述的影響應(yīng)用軟件重要性的2 種因素.它的思想基于Page 等人[21]提出的PageRank 算法，即PageRank 算法應(yīng)用于代表互聯(lián)網(wǎng)的有向圖中，而PackageRank 算法則是將其應(yīng)用到軟件生態(tài)圖.

圖3 展示了經(jīng)過簡化的PackageRank 算法，它是一個迭代過程：每個結(jié)點將它現(xiàn)有的得分沿所有“出邊”平均分發(fā)，并將所有“入邊”的得分求和，作為新一輪迭代之前的得分.本文將PackageRank 算法經(jīng)過多次迭代得到的穩(wěn)定結(jié)果作為應(yīng)用軟件的重要性度量值.

Fig.3 Illustration of PackageRank algorithm圖3 PackageRank 算法示意圖

Package Rank 算法的含義是：

1）“入邊得分求和”使得被更多應(yīng)用依賴的應(yīng)用因為有更多得分來源而獲得更高得分；

2）“出邊平均分發(fā)”使得被更高得分的應(yīng)用依賴的應(yīng)用能獲得更高得分.

由此可見，PackageRank 算法兼顧了影響應(yīng)用軟件重要性的2 個因素.

簡化的PackageRank 存在2 個問題，Page 等人[21]將它們分別稱為排序沉沒（rank sink）和懸鏈接（dangling link），本文也采用這2 個稱呼.

1）排序沉沒.軟件生態(tài)圖中可能存在環(huán)，即應(yīng)用之間可以環(huán)形依賴.當(dāng)環(huán)中的全部應(yīng)用都被兼容時，它們都能正確運行，否則便都不能正確運行.如果存在指向環(huán)中某個點的邊，所有的點又均沒有指向環(huán)外其他點的邊，則得分可以進(jìn)入環(huán)但不能排出，從而在環(huán)中無限積累，如圖4 所示.可能存在1 個或多個這樣的環(huán)，而不在這些環(huán)內(nèi)的點最終都將沒有得分.

Fig.4 Illustration of rank sink圖4 排序沉沒示意圖

2）懸鏈接.有些應(yīng)用不依賴任何其他應(yīng)用，即它對應(yīng)的點在軟件生態(tài)圖中沒有出邊.在迭代過程中，賦予這些點的分?jǐn)?shù)將從圖中泄漏，如圖5 所示.

為了解決排序沉沒和懸鏈接，算法在每次迭代后令每個結(jié)點都“流失”一定比例的得分，同時向所有結(jié)點補(bǔ)充分配分?jǐn)?shù)以維持總得分恒定.其中，得分流失和補(bǔ)充使得所有得分不會全部流入閉環(huán)中，而得分補(bǔ)充還可以補(bǔ)足因懸鏈接而泄漏的得分.

考慮到上述問題和解決方法，我們把由Package-Rank 計算的應(yīng)用軟件重要性定義.

定義5.應(yīng)用軟件的重要性.重要性度量結(jié)果為向量R，滿足：

其中R(i)是應(yīng)用i的得分，流失因子ε ＜1，Bi是依賴應(yīng)用i的應(yīng)用軟件集合，E是重新分配和補(bǔ)充得分的方法，并且通過方法E來保持‖R‖1=1，E(i)是為應(yīng)用i補(bǔ)充的得分的初值（或稱為補(bǔ)充方案，εE(i)是真實的補(bǔ)充值）.

可以根據(jù)軟件生態(tài)圖構(gòu)造矩陣An×n（n是生態(tài)中應(yīng)用的個數(shù)）：將所有應(yīng)用軟件編號為1～n.對于1≤i≤n和1≤j≤n，如果應(yīng)用i被應(yīng)用j依賴，則Aij= 1 /Nj，Nj是應(yīng)用j依賴的應(yīng)用個數(shù)（點j的出度）；否則Aij=0.算法收斂后的向量R（第i維上的值是應(yīng)用i的得分）滿足R=AR.An×n稱為依賴關(guān)系矩陣.

算法1 展示了PackageRank 計算應(yīng)用軟件重要性的過程.

算法1.PackageRank 計算應(yīng)用軟件重要性R.

初始向量R0可以是任何滿足‖R‖1=1的向量，它并不影響最終收斂時的結(jié)果.本文采用等值向量作為初始向量，即

流失因子ε的大小會影響算法的計算結(jié)果.如果ε過大，依賴關(guān)系網(wǎng)在算法中的作用將被減弱，導(dǎo)致結(jié)果不準(zhǔn)確；如果過小，算法收斂速度更慢.Page 等人[21]建議ε=0.15，以表征網(wǎng)絡(luò)用戶隨機(jī)跳轉(zhuǎn)訪問網(wǎng)頁的概率；而由于ε在此處僅為避免排序沉沒，選取的值太大將帶來較大誤差，故本文設(shè)定ε=0.001.重新補(bǔ)充分配得分的方法是平均分配，這是因為open Euler 缺乏其他與應(yīng)用軟件相關(guān)的統(tǒng)計數(shù)據(jù)或信息.

圖6 展示了排名前N的應(yīng)用軟件重要性（PackageRank 得分）之和隨N的變化曲線.相同應(yīng)用場景、不同體系結(jié)構(gòu)的軟件生態(tài)得到了形狀相似的結(jié)果曲線，但不同應(yīng)用場景的結(jié)果有明顯差異，這和第3 節(jié)中兼容分析的結(jié)論是相同的.

Fig.6 Importance of applications computed by PackageRank圖6 PackageRank 計算的應(yīng)用軟件重要性

不同應(yīng)用軟件的重要性得分差距很大，少量的應(yīng)用聚集了大量的重要性得分，同時很大一部分應(yīng)用的得分是極小的.圖6（a）（b）顯示，服務(wù)器生態(tài)中7 個應(yīng)用的重要性得分之和已經(jīng)達(dá)到全部應(yīng)用的25%，28 個應(yīng)用達(dá)到了50%，近800 個達(dá)到了75%，而生態(tài)中共有1.8 萬余個應(yīng)用軟件；嵌入式生態(tài)的得分分布相對更加均衡，但也存在明顯的差距.

這一軟件生態(tài)的特點符合自然界生態(tài)系統(tǒng)的規(guī)律.少數(shù)食物鏈頂端的物種能得到大量的能量輸入，在系統(tǒng)中也更具支配性；而底端的低級生物只能靠更多的數(shù)量來維持平衡.軟件生態(tài)和自然界生態(tài)系統(tǒng)的發(fā)展過程有所相似，依賴關(guān)系網(wǎng)和食物鏈網(wǎng)也是類似的結(jié)構(gòu)，而PackageRank 的結(jié)果也正是自然界的生態(tài)規(guī)律在軟件生態(tài)中的延伸，這體現(xiàn)了算法的合理性.此外，嵌入式生態(tài)中的得分分布更為均衡的原因則是其生態(tài)規(guī)模更小、復(fù)雜度更低，重要的應(yīng)用不能積累足夠的分?jǐn)?shù)而與其他應(yīng)用拉開差距.

4.2.2 計算C 庫的兼容性

兼容性的度量方法應(yīng)當(dāng)體現(xiàn)應(yīng)用軟件重要性的差異.C 庫兼容更重要的應(yīng)用軟件，對生態(tài)的積極作用更顯著，C 庫的兼容性便得到更大幅度的提升；C庫不兼容重要應(yīng)用，對生態(tài)造成的破壞也更大，兼容性將受到更大的影響.因此，通過對被兼容應(yīng)用的重要性評價（PackageRank 得分）來計算兼容性是十分合適的.

雖然PackageRank 為每個應(yīng)用軟件輸出一個確定的得分，但如果將所有應(yīng)用軟件的得分縮放同樣的比例，得到的結(jié)果仍是穩(wěn)定的.通過改變定義5 中‖R‖1的值，就能實現(xiàn)得分的縮放.因此，得分的比值更具意義，它反映的是生態(tài)中各個應(yīng)用的“相對重要性”.這個屬性是應(yīng)用軟件生態(tài)的固有屬性，與得分的縮放無關(guān).我們采用所有被兼容應(yīng)用的重要性得分之和與全部應(yīng)用得分之和的比值來度量C 庫的兼容性.由于‖R‖1=1，故只需將所有被兼容應(yīng)用的得分求和便能得到這個比值.

定義6.C 庫在軟件生態(tài)內(nèi)的兼容性.兼容性定義為所有被兼容應(yīng)用的重要性得分之和與全部應(yīng)用得分之和的比值，即為所有被兼容應(yīng)用的得分之和.

表6 展示了musl libc 在openEuler 的4 種生態(tài)中的兼容性度量結(jié)果.

Table 6 Compatibility of musl libc表6 musl libc 的兼容性%

不同應(yīng)用場景的兼容性差別很大，而體系結(jié)構(gòu)對兼容性的影響很小.嵌入式生態(tài)的C 庫兼容性較服務(wù)器生態(tài)高出26%左右，而實際情況也確實如此，即嵌入式生態(tài)的應(yīng)用多為主流應(yīng)用，它們更多地調(diào)用常用的API，而缺失API 普遍是不常用且功能特殊的，因此應(yīng)用軟件調(diào)用缺失API 的概率更低.

至此，我們發(fā)現(xiàn)musl libc 對應(yīng)用軟件的兼容性仍有很大的提升空間，在替換前需要進(jìn)一步補(bǔ)全開發(fā)工作.

5 缺失API 優(yōu)先級算法

C 庫的開發(fā)者不僅需要了解C 庫的兼容性，而且更需要獲知缺失API 的優(yōu)先級，以便按序進(jìn)行補(bǔ)全.

缺失API 的優(yōu)先級差異體現(xiàn)在兼容性價值上：C庫通過補(bǔ)全API 而兼容更多應(yīng)用軟件運行，不同API被應(yīng)用軟件調(diào)用的情況有差別，應(yīng)用軟件的重要性又有差別，從而補(bǔ)全不同的API 對生態(tài)的兼容性價值也有高低之分.

本節(jié)提出了有接口的軟件生態(tài)圖模型，并在該模型上提出了APIRank 算法以度量缺失API 優(yōu)先級，然后按照優(yōu)先級次序進(jìn)行了API 補(bǔ)全模擬.

5.1 影響缺失API 優(yōu)先級的因素

與4.1 節(jié)類似，缺失API 的優(yōu)先級也受多重因素的影響.被大量應(yīng)用軟件調(diào)用的缺失API 應(yīng)優(yōu)先實現(xiàn)，以滿足眾多應(yīng)用的功能需求；重要的應(yīng)用軟件調(diào)用的缺失API 應(yīng)優(yōu)先實現(xiàn)，以保證重要應(yīng)用的正常運行.此外，如果一個應(yīng)用軟件調(diào)用的缺失API 數(shù)量過多，要兼容該應(yīng)用就需要大量的工作，兼容性提升效率降低，且開發(fā)過程不易調(diào)試[21]，故這些API 的優(yōu)先級降低.因此，缺失API 的優(yōu)先級受3 種因素的影響：

1）調(diào)用它的應(yīng)用軟件的數(shù)量；

2）調(diào)用它的應(yīng)用軟件的重要性；

3）調(diào)用它的應(yīng)用軟件所調(diào)用的缺失API 總數(shù).

5.2 APIRank 算法

為綜合考慮5.1 節(jié)所述的3 個因素，我們基于軟件生態(tài)圖和PackageRank 算法作進(jìn)一步延伸，提出了有接口的軟件生態(tài)圖模型和APIRank 算法以度量缺失API 的優(yōu)先級.

在軟件生態(tài)圖中，應(yīng)用軟件之間的依賴關(guān)系對應(yīng)著圖中的有向邊.這種將依賴關(guān)系模型化的思路在有接口的軟件生態(tài)圖中得到了延續(xù).應(yīng)用軟件對API 的調(diào)用可以被視作一種廣義的“依賴”關(guān)系.應(yīng)用軟件“依賴”API，正如應(yīng)用軟件依賴其他應(yīng)用一樣.依照這個思路，可以構(gòu)造一張由應(yīng)用軟件和缺失API 共同組成的有向圖，并根據(jù)廣義依賴關(guān)系在圖中連接對應(yīng)的邊.我們把這樣的有向圖稱為有接口的軟件生態(tài)圖.

定義7.有接口的軟件生態(tài)圖.它是一張表示軟件生態(tài)中應(yīng)用軟件和缺失API 及其之間廣義依賴關(guān)系的有向圖.圖中的每個點對應(yīng)生態(tài)中的一個應(yīng)用軟件或一個缺失API，每條邊對應(yīng)一個廣義依賴關(guān)系，邊的方向規(guī)定為：應(yīng)用A依賴應(yīng)用B，對應(yīng)一條從A指向B的邊；應(yīng)用C調(diào)用缺失APID，對應(yīng)一條從C指向D的邊.

算法1 中的PackageRank 的計算過程同樣可以用于有接口的軟件生態(tài)圖，收斂后圖中每個結(jié)點也會有一個穩(wěn)定的得分.本文將收斂后代表缺失API 的結(jié)點的得分視為缺失API 的優(yōu)先級，這個算法稱為APIRank，如圖7 所示，它是圖4 添加了缺失的API 而生成的.

Fig.7 Illustration of APIRank圖7 APIRank 示意圖

APIRank 算法的含義是：

1）被更多應(yīng)用軟件調(diào)用的缺失API 有更多的分?jǐn)?shù)來源，從而獲得更高的分?jǐn)?shù)；

2）更重要的應(yīng)用有更高的分?jǐn)?shù)，它調(diào)用的缺失API 也能獲得更高的分?jǐn)?shù)；

3）調(diào)用多個缺失API 的應(yīng)用有更多的出邊，每個缺失API 能從出邊獲得的分?jǐn)?shù)更低.

由此可見，APIRank 算法兼顧了影響接口優(yōu)先級的3 個因素.

同樣地，可以根據(jù)有接口的軟件生態(tài)圖構(gòu)造矩陣A（n+m）×（n+m）（n是應(yīng)用個數(shù)，m是缺失API 個數(shù)）：所有應(yīng)用編號為1～n，所有缺失API 編號為n+1～n+m.對于1≤i≤n+m和1≤j≤n+m，如果點j有指向點i的邊，則Aij= 1 /Nj，Nj是點j的出度；否則Aij= 0.A（n+m）×（n+m）稱為廣義依賴關(guān)系矩陣.

算法2 展示了APIRank 計算缺失API 優(yōu)先級的過程.

算法2.APIRank 計算缺失API 優(yōu)先級.

同樣地，APIRank 也采用等值向量作為初始向量，流失因子ε=0.001.

根據(jù)缺失API 的得分R的高低，可以對其優(yōu)先級進(jìn)行排序.

5.3 接口補(bǔ)全模擬

我們模擬了按照缺失API 優(yōu)先級排序進(jìn)行補(bǔ)全時，musl libc 兼容性隨著每個API 的補(bǔ)全而逐步提升的過程，如圖8 所示.

Fig.8 Increase of compatibility in simulations process of API complementation圖8 API 補(bǔ)全模擬過程中兼容性的提升過程

圖8 的結(jié)果顯示，musl libc 兼容性的提升呈階梯型，這是因為在開發(fā)過程中往往需要實現(xiàn)多個API才能兼容某一個應(yīng)用軟件，而該應(yīng)用軟件的兼容能夠（或許會大幅度地）提升C 庫的兼容性.同一應(yīng)用場景、不同體系結(jié)構(gòu)的兼容性提升過程相似，而不同應(yīng)用場景的過程區(qū)別較大，這也完全符合我們的預(yù)期.

注意到，當(dāng)C 庫達(dá)到完全兼容（兼容性為100%）時，并非所有的缺失API 均已被補(bǔ)全，即代表完全兼容的點的橫坐標(biāo)值均小于表2 中的主要接口缺失總數(shù)（1 379）.這表明有些缺失API 未被生態(tài)中的任何應(yīng)用軟件調(diào)用.根據(jù)本文對兼容的定義，這些缺失API 沒有對應(yīng)用軟件生態(tài)提供任何有效的兼容支持，目前并不需要補(bǔ)全它們就能達(dá)到完全兼容，它們也不包含在有接口的軟件生態(tài)圖中，從而不存在APIRank 算法得分（無優(yōu)先級）.

圖9 展示了被調(diào)用和未被調(diào)用的缺失API 數(shù)量和占比.我們發(fā)現(xiàn)未被調(diào)用的API 所占的比例很高：嵌入式生態(tài)中有95.9%的缺失接口未被應(yīng)用軟件調(diào)用過；服務(wù)器生態(tài)中，aarch64 和x86_64 的數(shù)據(jù)分別是85.3%和85.1%.API 未被任何應(yīng)用軟件調(diào)用，一般是因為其功能過于特殊而缺乏實用場景，或存在與其功能類似但更受應(yīng)用開發(fā)者喜愛（性能更好，更符合編程習(xí)慣等原因）的其他API.嵌入式生態(tài)的比例比服務(wù)器生態(tài)低10%，而這也和嵌入式生態(tài)的兼容性更高（見表6）相呼應(yīng).

Fig.9 Proportion of called missing API and not called missing API圖9 被調(diào)用和未被調(diào)用的缺失API 占比

openEuler 的C 庫開發(fā)者當(dāng)前無需擔(dān)心這些未被調(diào)用的API 會帶來兼容性問題.而且，目前未被調(diào)用的API 短期內(nèi)也很可能不會被應(yīng)用軟件的開發(fā)者使用，因此C 庫開發(fā)者有較長的時間來逐一補(bǔ)全它們（如果需要），同時該C 庫又能不受影響地提供服務(wù).

6 評 估

本節(jié)評估了PackageRank 算法和APIRank 算法的效果，分析算法誤差，對比其他現(xiàn)有算法，展望算法的延伸，以及闡明本文研究的局限.

6.1 算法效果

6.1.1 PackageRank 算法效果

PackageRank 算法的評估采用aarch64 體系結(jié)構(gòu)的結(jié)果作為例子.表7 給出了在aarch64 的2 種應(yīng)用場景下PackageRank 得分排名較高的應(yīng)用的分值.為了更清晰地顯示結(jié)果，表7 中的得分是經(jīng)過等比例放大的，這樣的放大并不影響算法結(jié)果的穩(wěn)定和準(zhǔn)確.

Table 7 Statistics of High-ranked Applications of PackageRank in aarch64表7 aarch64 體系結(jié)構(gòu)下PackageRank 高優(yōu)先級應(yīng)用的統(tǒng)計

PackageRank 考慮了影響應(yīng)用軟件重要性的2 個因素：被依賴次數(shù)、依賴應(yīng)用的重要性.由表7 可知，這2 個因素實際都對結(jié)果產(chǎn)生了影響.服務(wù)器生態(tài)中，bash，texlive-base 都既被大量應(yīng)用依賴（入邊數(shù)很高），又被高分應(yīng)用依賴并獲得了大量得分（最大入邊分?jǐn)?shù)高，最大入邊分?jǐn)?shù)來源的分?jǐn)?shù)和排名高）；texlivekpathsea 是典型的僅因大量應(yīng)用依賴而積累出高分的例子，有3 190 個依賴它的應(yīng)用，但其中最高得分的應(yīng)用也僅排名65；ncurses-base 則完全因為高分應(yīng)用的依賴才成為了排名第3 的應(yīng)用，它只有2 個依賴者，而其中ncurse-libs 為它輸送了96.9%（3 487.70/3 598.00）的高額分?jǐn)?shù).嵌入式生態(tài)中，bash 受2 種因素影響而排名第1，zlib，libselinux 主要因為被依賴次數(shù)高，而libsepol 則主要因為從libselinux（排名第4）處獲得大量分?jǐn)?shù)而排在第3 位.

此外，服務(wù)器生態(tài)中的perl-libs 和perl-Exporter存在雙向依賴，這是排序沉沒問題出現(xiàn)的例子，在算法中已經(jīng)解決了這個問題（4.2 節(jié)）.

應(yīng)當(dāng)指出，平均入邊分?jǐn)?shù)與入邊數(shù)的乘積并不等于得分，而是約等于得分減1（存在微小誤差）.這是因為PackageRank 在迭代時對每個點進(jìn)行了等額的得分補(bǔ)充（4.2 節(jié)）.補(bǔ)充的得分并不來自入邊，而表7 中的得分就是將這部分補(bǔ)充的得分縮放為1.00后的結(jié)果.

上述分析表明PackageRank 算法有效地實現(xiàn)了對應(yīng)用軟件重要性的多重影響因素的兼顧.

6.1.2 APIRank 算法效果

APIRank 算法的評估采用x86_64 體系結(jié)構(gòu)的結(jié)果作為例子.表8 列出了在x86_64 的2 種應(yīng)用場景下APIRank 算法中優(yōu)先級較高的API 的分值.

Table 8 Statistics of High-ranked APIs of APIRank in x86_64表8 x86_64 體系結(jié)構(gòu)下APIRank 高優(yōu)先級API 的統(tǒng)計

服務(wù)器生態(tài)中，應(yīng)用軟件的高分對其所調(diào)用的缺失API 的優(yōu)先級提升作用明顯：PackageRank 中排名第1 的coreutils 調(diào)用了6 個缺失API，它們均排在前7 名中.另一方面，被大量應(yīng)用軟件調(diào)用也能提升API 優(yōu)先級，fcntl64 有遠(yuǎn)超其他API 的被調(diào)用數(shù)（入邊數(shù)），這也使得它排在第2 名.另外一個例子則能體現(xiàn)這2 個因素對優(yōu)先級的共同影響：dlvsym 和argz_add 得分接近，但分別主要受被調(diào)用數(shù)和調(diào)用者重要性的因素影響，表明在不同主要因素影響下缺失API 也能得到相近的分?jǐn)?shù).

嵌入式生態(tài)結(jié)構(gòu)比較簡單，且其應(yīng)用軟件調(diào)用的缺失API 數(shù)量更少，因此API 優(yōu)先級得分比較接近，但仍能看出多個因素共同影響優(yōu)先級的效果.特別地，mallinfo 和obstack_vprintf 的得分接近，前者的被調(diào)用數(shù)和調(diào)用者最高得分都更高（3 對1，3.26 對1.00），但其調(diào)用者（e2fsprogs）所調(diào)用的總?cè)笔PI 數(shù)更多（4 個，另外1 條出邊是應(yīng)用依賴關(guān)系），故其得分與后者接近，這體現(xiàn)了第3 個因素對結(jié)果的影響.

上述分析表明APIRank 算法有效地實現(xiàn)了對缺失API 優(yōu)先級的多重影響因素的兼顧.

6.2 算法誤差

本文算法的誤差有2 個來源：

1）流失因子ε和得分補(bǔ)充.本文中ε=0.001，得分補(bǔ)充方法為平均分配，因此在每輪迭代后有0.1%的分?jǐn)?shù)從各個結(jié)點中流失，并平均分配到所有結(jié)點.因此，兼容性誤差在0.1%以內(nèi)；缺失API 優(yōu)先級的數(shù)值存在誤差，但排序不存在誤差，即按比例流失和平均分配不影響得分之間的大小關(guān)系.

2）收斂極限的設(shè)定.本文收斂極限設(shè)定為“迭代向量差的2-范數(shù)不超過10-5”，因此兼容性的誤差在0.001%以內(nèi)，缺失API 優(yōu)先級的平均誤差在10-7以內(nèi).

綜上，兼容性誤差在0.1%以內(nèi)，缺失API 優(yōu)先級的平均誤差在10-7以內(nèi).由于在4 種生態(tài)內(nèi)的所有缺失API 的優(yōu)先級得分均高于10-5，故APIRank 的平均誤差低于1%.

6.3 算法對比

第4 節(jié)提出了本文的兼容性算法PackageRank，而1.3 節(jié)中也提到了其他2 種兼容性度量方法.

1）算法A：已實現(xiàn)的API 個數(shù)；

2）算法B：文獻(xiàn)[2]的加權(quán)完整性.

算法A的度量方式因缺乏應(yīng)用軟件所包含的信息而不準(zhǔn)確，在本節(jié)中不再討論.

算法B是將其他系統(tǒng)與Ubuntu 15.04 作比較，或模擬將系統(tǒng)構(gòu)件安裝在Ubuntu 15.04 上并研究其兼容性.之所以選擇Ubuntu 15.04 為基準(zhǔn)系統(tǒng)，是因為它是“管理良好的、廣泛支持應(yīng)用軟件的、統(tǒng)計軟件包安裝數(shù)據(jù)的Linux 發(fā)行版”.文獻(xiàn)[2]統(tǒng)計API 調(diào)用情況時使用Ubuntu 的RPM 包，API 重要性和加權(quán)完整性的計算也均采用Ubuntu 的安裝次數(shù)統(tǒng)計.

我們認(rèn)為算法B不適用于openEuler 對musl libc兼容性分析的原因是：

1）openEuler 的應(yīng)用軟件生態(tài)與Ubuntu 有區(qū)別，RPM 包的內(nèi)容也有所不同；

2）openEuler 不具備像Ubuntu 一樣完備的應(yīng)用軟件安裝記錄；

3）應(yīng)用軟件的安裝并非獨立事件，而是存在互相依賴關(guān)系.

表9 列出了通過各種算法計算的musl libc 兼容性.其中，“算法B”一欄是文獻(xiàn)[2]給出的度量結(jié)果，而“算法B*”一欄是將算法B的基準(zhǔn)系統(tǒng)設(shè)定為open-Euler 得到的結(jié)果.由于不具備安裝次數(shù)統(tǒng)計，我們在算法B*中將下載次數(shù)設(shè)為相同.按照算法2 的定義，此時計算的兼容性值即為應(yīng)用軟件的兼容率.如第4節(jié)所言，兼容率不能準(zhǔn)確地反映兼容性，因此在缺乏數(shù)據(jù)統(tǒng)計時，本文提出的兼容性算法比算法B更為準(zhǔn)確.

對比其他算法，本文提出的PackageRank 算法的優(yōu)勢和特點在于：

1）為系統(tǒng)提供從自身應(yīng)用軟件生態(tài)出發(fā)的、個性化的兼容性評估.不同系統(tǒng)能夠搭載的應(yīng)用軟件范圍（即生態(tài)）不同（Ubuntu/Debian 生態(tài)中有30 976 個應(yīng)用[2]，openEuler x86_64 服務(wù)器生態(tài)有18 288 個，open-Euler x86_64 嵌入式生態(tài)有83 個），很難為多種多樣的系統(tǒng)確定統(tǒng)一的“基準(zhǔn)生態(tài)”.本文的算法以每種系統(tǒng)或構(gòu)件各自的應(yīng)用軟件生態(tài)信息作為輸入，反映API 在其真實應(yīng)用場景的兼容性，為開發(fā)者提供準(zhǔn)確的、個性化的評估結(jié)果.

2）適用于缺乏應(yīng)用軟件安裝統(tǒng)計的系統(tǒng).包括openEuler 在內(nèi)的大多數(shù)操作系統(tǒng)的發(fā)行版都不具備像Ubuntu/Debian 一樣完備的應(yīng)用軟件安裝記錄.即使存在統(tǒng)計數(shù)據(jù)，如果數(shù)據(jù)量不足而不能視為滿足“大數(shù)定律”，那么“用頻率估計概率”也并不準(zhǔn)確.在統(tǒng)計數(shù)據(jù)缺失時，本文提出的算法既能夠利用有限的信息，又能緊密結(jié)合API 的調(diào)用情況，準(zhǔn)確地度量兼容性.算法所需的信息僅是應(yīng)用軟件的RPM 包.對于大多數(shù)系統(tǒng)而言，它們的生態(tài)中應(yīng)用軟件的RPM包都是完整且容易獲取的.

APIRank 的優(yōu)勢和特點除包含前述內(nèi)容外還有：面向仍有開發(fā)需求的系統(tǒng)和構(gòu)件，為API 的補(bǔ)全實現(xiàn)工作提供幫助.現(xiàn)有研究大多面向已經(jīng)完整實現(xiàn)的系統(tǒng)和構(gòu)件，分析已有API，而本文的算法僅度量缺失API 的優(yōu)先級，為仍需開發(fā)的系統(tǒng)和構(gòu)件提供補(bǔ)全順序的建議.本文算法并非為Linux API 的全局現(xiàn)狀和生態(tài)環(huán)境做分析，而是為系統(tǒng)和構(gòu)件開發(fā)者提供方案建議.

6.4 展 望

1）目前并沒有將PackageRank 和APIRank 應(yīng)用于完整開發(fā)過程的例子，但openEuler 已經(jīng)開始按照APIRank 計算出的優(yōu)先級順序開展補(bǔ)全工作.在開發(fā)過程中發(fā)現(xiàn)，有些高優(yōu)先級API 并非在musl libc 中實現(xiàn)，而是以別名實現(xiàn)（如error）或在其他分支庫中實現(xiàn)（如backtrace），這表明高優(yōu)先級API 在musl libc 的開發(fā)者看來也十分重要，因此他們沒有拒絕實現(xiàn)這些API，只是其實現(xiàn)細(xì)節(jié)與glibc 存在區(qū)別.APIRank的分析結(jié)果和musl libc 開發(fā)者的觀點存在一致，有望為補(bǔ)全工作提供準(zhǔn)確的信息和實質(zhì)性的幫助.

2）在PackageRank 和APIRank 中，除應(yīng)用軟件全集外，系統(tǒng)開發(fā)者還可以選擇將某個目標(biāo)應(yīng)用集作為研究對象，從而獲知系統(tǒng)或構(gòu)件對該目標(biāo)集的兼容性和缺失API 優(yōu)先級.

3）PackageRank 和APIRank 不針對某種特定系統(tǒng)或構(gòu)件，因此它們有望適用于其他場景下的API兼容性分析，如其他C 庫、系統(tǒng)調(diào)用、向量化參數(shù)等.此外，還有望將它們應(yīng)用于系統(tǒng)模擬器的兼容性度量.

6.5 局 限

1）有2 處假設(shè)存在不準(zhǔn)確性：應(yīng)用的可執(zhí)行文件存在可鏈接API 的符號表條目，即視為API 被調(diào)用；API 存在即視為API 能正確工作.在3.1 節(jié)中，已經(jīng)對它們的不準(zhǔn)確性做出說明.

2）僅采用靜態(tài)分析而未考慮API 調(diào)用頻率等其他有關(guān)API 調(diào)用的信息，而靜態(tài)分析方法也無法準(zhǔn)確給出這些信息.

3）沒有參考用戶對應(yīng)用軟件的使用喜好和傾向，包括應(yīng)用軟件之間的其他隱性關(guān)聯(lián).

4）未全面考慮編譯環(huán)境和源碼對API 調(diào)用情況的影響，即應(yīng)用軟件的開發(fā)者可能會通過宏命令，根據(jù)編譯環(huán)境的不同而調(diào)用不同的接口（特別是那些不在ANSI/ISO C 標(biāo)準(zhǔn)中的接口）.應(yīng)用軟件的編譯環(huán)境會影響接口調(diào)用，接口缺失仍存在誤判.

5）實驗對象單一.本文的算法僅在openEuler 上的musl libc 兼容性研究中使用，未曾在其他系統(tǒng)或構(gòu)件上開展工作.

7 結(jié)束語

本文研究了openEuler 的4 種軟件生態(tài)中的musl libc 兼容性和缺失API 優(yōu)先級，以幫助openEuler 的C 庫開發(fā)者進(jìn)行接口補(bǔ)全工作.

本文的分析結(jié)果表明：一方面，musl libc 目前的兼容性仍有待提高，若要用其替代glibc 則需要進(jìn)一步開發(fā)；另一方面，開發(fā)者可以根據(jù)本文的缺失API優(yōu)先級按序而高效地開展工作.

本文基于應(yīng)用之間的依賴關(guān)系和應(yīng)用對API 的調(diào)用關(guān)系進(jìn)行兼容性和缺失API 優(yōu)先級的度量.從依賴關(guān)系和調(diào)用關(guān)系到兼容性和優(yōu)先級的轉(zhuǎn)化，是本文的核心思想和成果.

作者貢獻(xiàn)聲明：吳亦澤提出算法、完成實驗并撰寫論文；于佳耕提出算法思路和指導(dǎo)意見并修改論文；鄭晨提出指導(dǎo)意見并修改論文；武延軍給出選題、提出指導(dǎo)意見并修改論文.