[發明專利]移動終端操作系統基于全系統擴展調用圖的自動優化方法

有效

• 申請號: 201210495453.7
• 申請日: 2012-11-28
• 公開（公告）號: CN103034486A
• 公開（公告）日: 2013-04-10
• 發明（設計）人: 董淵;王生原;李疊;駱歡
• 申請（專利權）人: 清華大學
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 樓艮基

1.一種移動終端操作系統基于全系統擴展調用圖的自動優化方法，其特征在于，是在計算機中依次按以下步驟實現的：

步驟（1）：編譯移動終端操作系統的源代碼，生成可重定位的目標文件；

從源代碼服務器中下載源代碼，修改相關的Makefile，向CFLAGS添加“-ffunction-sections”參數和“-fdata-sections”參數以使編譯器將每個函數和數據對象編譯到單獨的段中，再運行make命令自動編譯所述源代碼生成可重定位的目標文件，其中函數和數據對象統稱為“實體”，所述數據對象既包括源代碼中定義的全局和靜態變量，也至少包括虛函數表在內的編譯器生成的數據對象；

步驟（2）：按以下步驟構造有向的全系統擴展調用圖：

步驟（2.1）：對步驟（1）得到的目標文件，讀取以下信息，其中包括SS、GS、AF和AU：

SS，所述目標文件中所有包含有所述實體的段的名稱集合，

GS，所述目標文件中定義的所有全局符號及其名稱，并以關聯表的形式存儲，以便從全局符號的名稱迅速查找所在的段的名稱，

AF，頭和尾都屬于同一個所述目標文件的有向邊形成的集合，

AU，頭屬于一個所述目標文件，尾為暫未解析的符號的有向邊，其中每一個元素表示為(u,sym)，其中u屬于SS，是所述目標文件中的一個所述實體，sym為一個外部符號的名，表示被實體u引用，但不在同一個所述目標文件中定義的實體，

步驟（2.2），根據步驟（2.1）中所得到的信息，合并為一個系統全局的有向圖，從而得到所述擴展調用圖的V和E，其中：

V為所有所述目標文件SS的并集，是一個結點集，其中每一個結點的名稱用所對應的一個二元組表示，其中包括目標文件名和段名，

E為有向邊集，它包括兩部分：E=E₁∪E₂，其中E₁為所有所述目標文件的AF的并集，代表了頭和尾都屬于同一個所述目標文件的有向邊所形成的集合，E₂為頭和尾屬于不同的所述目標文件的有向邊形成的集合，按以下方法得到：首先，令再遍歷每個所述目標文件的AU集合，對其中的每一個元素(u，sym)，查找所有所述目標文件的GS集，得到所有名稱為sym的全局符號的所述實體集合S[sym]，將所有二元組(u,v)｜_v∈S[sym]加入集合E₂，并將E₁與E₂取并集得到E，其中每一個元素是一對結點(u,v)，對應所述系統擴展調用圖中一條從u到v的有向邊，當且僅當u的重定位數據中有相對v的重定位記錄時，在所述系統擴展調用圖中存在一條從u到v的邊，

步驟（2.3），按以下步驟得到入口點集R：

步驟（2.3.1），令

步驟（2.3.2），把同程序啟動代碼對應的所述實體作為一個結點加入所述入口點集R，在Android中_start符號所對應的實體即為程序啟動代碼，

步驟（2.3.3），把可能通過動態綁定使用的所述實體作為一個結點加入所述入口點集R，

步驟（2.3.4），把位于不以.text、.data、.rodata、.bss打頭的段中的所述實體作為一個結點加入所述入口點集R，

步驟（2.4），從步驟（2.1）至步驟（2.3）得到的V、E、R表示為一個所述的系統調用圖G=(V，E,R)；

步驟（3），按以下步驟從步驟（2）得到的所述系統擴展調用圖G中得到有效子圖G_s=(V_s,E_s,R)，其中V_s為有效結點集，E_s為有效的有向邊集，表示為：

Vs=∪u∈RDesc(u)]]>

E_s＝E∩(V_s×V_s)

其中Desc(u)表示u在擴展調用圖G中包括u自身在內的子孫結點的集合，

步驟（3.1），令V_s＝R，Q＝R表示待訪問的結點集，表示已訪問的結點集，

步驟（3.2），從待訪問的結點集Q中任取一個結點u加入VisitedV，再把結點u在所述系統擴展調用圖G中的所有直接后繼結點加入所述V_s中，把述結點u的不屬于所述已訪問過的結點集VisitedV的直接后繼結點加入待訪問的結點集Q中，并從所述待訪問的結點集Q中刪除訪問過的結點u，

步驟（3.3），重復步驟（3.2），直到所述待訪問的結點集Q為空，得到有效結點集V_s，

步驟（3.4），令E_s為空集，遍歷E中的所有有向邊(u,v)，若結點u和結點v都屬于所述有效結點集V_s，把從所述結點u到所述結點v的有向邊加入E_s，

步驟（3.5），根據步驟（2）及步驟（3.1）至步驟（3.4）的結果得到有效子圖G_s=(V_s,E_s,R)；

步驟（4），按以下步驟重寫所述目標文件，更新時間戳：

步驟（4.1），每一個所述目標文件中的實體都帶有一個可見性屬性，包括默認default、受保護protected、內部internal、隱藏hidden四種，對每一個不屬于有效結點集V_s的實體，若其可見性屬性為默認default，則改為隱藏hidden，

步驟（4.2），對每一個所述不屬于有效結點集V_s的實體，清除其重定位數據，

步驟（4.3），遍歷所述目標文件的符號表，清除不再被任何段引用的符號，

步驟（4.4），根據步驟（4.1）至（4.3）的結果，對所述目標文件進行二進制重寫，對于有修改的所述目標文件，其時間戳被自動更新，

步驟（5），按以下步驟鏈接得到優化化的Android鏡像文件：

在所述Makefile中添加用于鏈接時對段進行垃圾收集的鏈接選項“--gc-sections”，運行make命令，自動重新鏈接生成優化后的可執行文件、動態庫文件并生成相應的Android鏡像文件。