摘 要: DWARF格式是一種常用的調(diào)試信息格式。DWARF格式使用多種方法壓縮存儲(chǔ)調(diào)試信息,以減少對(duì)可執(zhí)行文件存儲(chǔ)空間的占用。DWARF使用變長(zhǎng)數(shù)據(jù)LEB128存儲(chǔ)整型數(shù)。DWARF使用相鄰行調(diào)試信息的變化存儲(chǔ)行號(hào)調(diào)試信息,并利用該信息的特點(diǎn)將其進(jìn)一步壓縮至1 B。DWARF把相同的內(nèi)部格式定義數(shù)據(jù)存儲(chǔ)在單獨(dú)的節(jié)區(qū)。DWARF格式定義的這些數(shù)據(jù)壓縮方式值得數(shù)據(jù)壓縮相關(guān)領(lǐng)域?qū)W習(xí)和借鑒。
關(guān)鍵詞: DWARF;調(diào)試信息;數(shù)據(jù)壓縮;LEB128
0 引言
數(shù)據(jù)壓縮是計(jì)算機(jī)領(lǐng)域一項(xiàng)廣泛使用的技術(shù),在多媒體、通信、存儲(chǔ)等領(lǐng)域得到廣泛應(yīng)用[1-3]。數(shù)據(jù)壓縮技術(shù)分為兩大類(lèi):無(wú)損壓縮和有損壓縮。無(wú)損壓縮指壓縮過(guò)程不丟失信息的壓縮方法,可以由壓縮數(shù)據(jù)完整恢復(fù)壓縮前的數(shù)據(jù)。有損壓縮指壓縮過(guò)程丟失部分信息的壓縮方法,一般應(yīng)用于多媒體領(lǐng)域。常用的無(wú)損壓縮方法包括哈夫曼編碼方法、算術(shù)編碼方法、基于字典的壓縮方法(如LZ78算法、LZW算法)等。只要涉及數(shù)據(jù)的存儲(chǔ)、傳輸,都可應(yīng)用數(shù)據(jù)壓縮方法。
調(diào)試信息指在可執(zhí)行文件中存儲(chǔ)的關(guān)于源代碼的信息。調(diào)試信息使程序員可以由程序執(zhí)行狀態(tài)追蹤至其源代碼,也使在源代碼的級(jí)別對(duì)程序進(jìn)行調(diào)試成為可能。所以,調(diào)試信息是源代碼級(jí)調(diào)試功能實(shí)現(xiàn)必不可少的重要部分。調(diào)試信息以固定的格式存儲(chǔ)在被調(diào)試可執(zhí)行文件中,常用的調(diào)試信息格式包括STABS、COFF、DWARF等。其中DWARF(Debugging with Attributed Record Formats)格式是最常用的調(diào)試信息格式,它具有表達(dá)功能豐富、內(nèi)容緊湊等優(yōu)點(diǎn)[4]。DWARF格式有DWARF1、DWARF2、DWARF3三個(gè)版本,最常見(jiàn)的是DWARF2版本,本文介紹的內(nèi)容是基于DWARF2格式的。
相比于其他調(diào)試信息格式,DWARF格式最大的優(yōu)點(diǎn)就是內(nèi)容高度緊湊。為了減少調(diào)試信息在可執(zhí)行文件中占用的空間,DWARF格式使用各種方法來(lái)壓縮調(diào)試信息數(shù)據(jù)。DWARF格式幾乎把調(diào)試信息的可壓縮特點(diǎn)利用到極致,是存儲(chǔ)空間最小的調(diào)試信息格式。由DWARF格式可以完整解析得到所有調(diào)試信息,所以DWARF格式使用的數(shù)據(jù)壓縮方法是一種無(wú)損數(shù)據(jù)壓縮方法。
目前,國(guó)內(nèi)幾乎還沒(méi)有研究機(jī)構(gòu)對(duì)DWARF格式調(diào)試信息進(jìn)行深入研究。本文對(duì)DWARF格式中使用的數(shù)據(jù)壓縮方法進(jìn)行了歸納、總結(jié)、分析,供數(shù)據(jù)壓縮、調(diào)試信息生成、分析領(lǐng)域及相關(guān)領(lǐng)域?qū)W習(xí)參考。
1 LEB128數(shù)
LEB128(Little Endian Base 128)數(shù)是一種變長(zhǎng)的存儲(chǔ)整數(shù)的數(shù)據(jù)結(jié)構(gòu),它僅僅存儲(chǔ)整數(shù)的有效位,可以表示任意范圍內(nèi)的有符號(hào)或無(wú)符號(hào)整型數(shù)。LEB128數(shù)的存儲(chǔ)空間與整數(shù)的有效位成正比。若整數(shù)的有效位很少,相對(duì)于普通整型數(shù)的存儲(chǔ)方式,LEB128數(shù)可以顯著減小存儲(chǔ)空間。
一些整數(shù)在大多數(shù)情況下只取很小的值,可以用1 B存儲(chǔ)。但由于該數(shù)可能取很大的值,不能將其存儲(chǔ)空間限制為1 B。若為了存儲(chǔ)個(gè)別情況下出現(xiàn)的大值而分配4 B或8 B的空間,大多數(shù)情況下會(huì)造成存儲(chǔ)空間的浪費(fèi)。LEB128的優(yōu)點(diǎn)在于其存儲(chǔ)空間是可變的。若整數(shù)很小,最少1 B即可儲(chǔ)存LEB128數(shù)。若數(shù)字很大,LEB128數(shù)可以用多個(gè)字節(jié)表示。LEB128數(shù)既可以編碼小端存儲(chǔ)的數(shù)據(jù),也可以編碼大端存儲(chǔ)的數(shù)據(jù)。
有符號(hào)數(shù)與無(wú)符號(hào)數(shù)轉(zhuǎn)化為L(zhǎng)EB128數(shù)的過(guò)程不同。編碼與解析程序必須知道該LEB128數(shù)是有符號(hào)數(shù)還是無(wú)符號(hào)數(shù),否則就會(huì)編碼或解析錯(cuò)誤。
把一個(gè)整數(shù)編碼為L(zhǎng)EB128數(shù)的過(guò)程抽象描述如下:
?。?)把該數(shù)的二進(jìn)制有效位分割為若干段,每段7 bit;
(2)把這些7 bit的數(shù)放入LEB128的各字節(jié)中,最高一位補(bǔ)1;
?。?)位于有效位最高位的7 bit,最高一位補(bǔ)0,標(biāo)志數(shù)的結(jié)束。
若整數(shù)的二進(jìn)制有效數(shù)位小于7 bit,只需1 B的LEB128數(shù)即可表示。對(duì)于調(diào)試信息,大多數(shù)情況下整數(shù)的取值范圍在-128和255之間,可以用1 B的有符號(hào)或無(wú)符號(hào)LEB128數(shù)表示。相對(duì)于正常的整數(shù)存儲(chǔ)方式,節(jié)省了3/4的存儲(chǔ)空間。
圖1、圖2分別為把無(wú)符號(hào)整數(shù)和有符號(hào)整數(shù)編碼為L(zhǎng)EB128數(shù)的算法流程圖。
2 行號(hào)調(diào)試信息壓縮方法
2.1 行號(hào)調(diào)試信息簡(jiǎn)介
行號(hào)調(diào)試信息是最基本的調(diào)試信息,它描述了源代碼中每一行代碼經(jīng)編譯鏈接后定位到的程序地址。它可以幫助調(diào)試系統(tǒng)由程序地址定位到源代碼中的位置,也可以由源代碼中的位置定位到程序地址。插入斷點(diǎn)、單步調(diào)試、暫停等調(diào)試功能都需要行號(hào)調(diào)試信息。常規(guī)的調(diào)試信息存儲(chǔ)方式把行號(hào)調(diào)試信息存儲(chǔ)為“行號(hào),程序地址”對(duì),每對(duì)記錄源代碼中一行代碼的行號(hào)和程序地址。例如,STABS格式調(diào)試信息以“行”為單位存儲(chǔ)行號(hào)調(diào)試信息,每個(gè)“行號(hào),程序地址”對(duì)占用相等的存儲(chǔ)空間,擁有相同的格式[5]。該存儲(chǔ)方法的優(yōu)點(diǎn)是簡(jiǎn)單易分析,缺點(diǎn)是占用空間較大。一般行號(hào)需要使用4 B存儲(chǔ),程序地址也需要4 B存儲(chǔ),一個(gè)“行號(hào),程序地址”對(duì)至少需要8 B存儲(chǔ)。實(shí)際上,STABS格式需要15 B來(lái)存儲(chǔ)一個(gè)“行號(hào),程序地址”對(duì)。
一般的源代碼中,兩相鄰行源代碼的行號(hào)差距不會(huì)太大,兩行源代碼的程序地址也不會(huì)相差太大。如果使用相鄰行的行號(hào)差和程序地址差來(lái)記錄行號(hào)調(diào)試信息,并通過(guò)某種方式把這個(gè)信息壓縮存儲(chǔ),將會(huì)大大減少行號(hào)調(diào)試信息的存儲(chǔ)空間。
2.2 DWARF格式行號(hào)調(diào)試信息簡(jiǎn)介
DWARF格式利用相鄰行的行號(hào)調(diào)試信息相差不大的特點(diǎn),使用與傳統(tǒng)方法完全不同的方式存儲(chǔ)行號(hào)調(diào)試信息。DWARF格式的行號(hào)調(diào)試信息存儲(chǔ)于.debug_line節(jié)區(qū)。DWARF格式首先定義了一個(gè)狀態(tài)機(jī),該狀態(tài)機(jī)包含文件名、行號(hào)、程序地址等信息。DWARF格式還定義了一些精簡(jiǎn)的操作碼,這些操作碼可以改變?cè)摖顟B(tài)機(jī)的狀態(tài),每存儲(chǔ)一個(gè)操作碼,就相當(dāng)于存儲(chǔ)了一個(gè)“行號(hào),程序地址”對(duì)。
DWARF格式定義的操作碼分為三類(lèi),可以對(duì)行號(hào)調(diào)試信息狀態(tài)機(jī)進(jìn)行全面的操作。表1分別介紹這三類(lèi)操作碼。
三類(lèi)操作碼中,最常用的是特殊操作碼,其存儲(chǔ)空間固定為1 B,可以改變行號(hào)調(diào)試信息狀態(tài)機(jī)中的行號(hào)和程序地址,并生成一個(gè)“行號(hào),程序地址”對(duì)調(diào)試信息。
標(biāo)準(zhǔn)操作碼可以對(duì)狀態(tài)機(jī)執(zhí)行一些特殊操作碼無(wú)法執(zhí)行的命令,如設(shè)置程序地址、改變文件名等。標(biāo)準(zhǔn)操作碼的范圍為從1開(kāi)始的一段連續(xù)整數(shù)。例如,DWARF2格式預(yù)定義了9種標(biāo)準(zhǔn)操作碼,其操作碼編號(hào)分別為1、2、3…8、9。調(diào)試信息生成程序可以自定義標(biāo)準(zhǔn)操作碼。
擴(kuò)展操作碼用來(lái)執(zhí)行一些標(biāo)準(zhǔn)操作碼也無(wú)法描述的命令。
2.3 特殊操作碼的數(shù)據(jù)壓縮機(jī)制
特殊操作碼用1 B記錄行號(hào)改變量和程序地址改變量,并且還可以由該字節(jié)準(zhǔn)確地計(jì)算得到行號(hào)改變量和程序地址改變量的原值。
特殊操作碼的計(jì)算可以用下式抽象描述:
特殊操作碼=程序地址改變量×行號(hào)改變量范圍+行號(hào)改變量(1)
其中,行號(hào)改變量范圍為行號(hào)改變量的取值范圍,行號(hào)改變量應(yīng)取大于或等于0并小于行號(hào)改變量范圍的值。
由特殊操作碼計(jì)算得到行號(hào)改變量和程序地址改變量的過(guò)程可以抽象描述為:
行號(hào)改變量=特殊操作碼%行號(hào)改變量范圍(2)
程序地址改變量=特殊操作碼/行號(hào)改變量范圍(3)
由取模算術(shù)運(yùn)算的特點(diǎn)可知,由一個(gè)特殊操作碼可以確定唯一的行號(hào)改變量和程序地址改變量,而且這個(gè)行號(hào)改變量和程序地址改變量就是計(jì)算該特殊操作碼的輸入。
在DWARF格式的實(shí)際定義中,根據(jù)行號(hào)調(diào)試信息的特點(diǎn)對(duì)上述公式進(jìn)行了修正。行號(hào)調(diào)試信息的特點(diǎn)包括:
?。?)行號(hào)改變量可能是負(fù)數(shù)。對(duì)于高級(jí)語(yǔ)言(如C語(yǔ)言),其一行源代碼產(chǎn)生的程序可能分散在若干個(gè)位置,如for、while循環(huán)語(yǔ)句。這樣的一行源代碼會(huì)產(chǎn)生若干條行號(hào)調(diào)試信息,其中混夾著其他行源代碼的行號(hào)調(diào)試信息。所以,相鄰的行號(hào)調(diào)試信息的行號(hào)改變量可能是負(fù)數(shù)。而由取模算術(shù)運(yùn)算的特點(diǎn)可知,要準(zhǔn)確由特殊操作碼解壓縮得到行號(hào)調(diào)試信息,行號(hào)改變必須為正數(shù)。所以,式(1)中“行號(hào)改變量”應(yīng)改為行號(hào)實(shí)際改變量與行號(hào)改變量最小可能值之差。
(2)程序地址改變量一定是最小指令長(zhǎng)度的倍數(shù)。程序段是由指令組成的,所以程序地址改變量實(shí)際上是本行源代碼生成的指令長(zhǎng)度之和。而指令的長(zhǎng)度有可能并不為1,例如,對(duì)某些機(jī)器,其指令長(zhǎng)度只能為4,其程序地址改變量一定是4的倍數(shù)。所以,為了擴(kuò)大特殊操作碼可描述的程序地址改變范圍,上述公式中的“程序地址改變量”應(yīng)改為程序地址實(shí)際改變量除以最小指令長(zhǎng)度。
?。?)特殊操作碼的取值范圍受限制。操作碼的第一個(gè)字節(jié)必須可以區(qū)分該操作碼的種類(lèi),否則調(diào)試信息解析程序無(wú)法判斷第一個(gè)字節(jié)是特殊操作碼還是其他兩類(lèi)操作碼。所以特殊操作碼的取值應(yīng)大于標(biāo)準(zhǔn)操作碼最大編號(hào),并小于或等于255。例如,若標(biāo)準(zhǔn)操作碼編號(hào)的取值范圍為1~9,則特殊操作碼的最小可能值為10。所以,由上述公式計(jì)算得到的特殊操作碼應(yīng)加上特殊操作碼的最小可能值。
根據(jù)行號(hào)調(diào)試信息的以上特點(diǎn),DWARF2中定義的實(shí)際特殊操作碼計(jì)算公式如下:
特殊操作碼=(行號(hào)改變量-行號(hào)改變量最小值)+(行號(hào)改變范圍×程序地址改變量/最小指令長(zhǎng)度)+特殊操作碼最小值(4)
由特殊操作碼得到行號(hào)改變量和程序地址改變量的公式如下:
行號(hào)改變量=(特殊操作碼-特殊操作碼最小值)%行號(hào)改變范圍+行號(hào)改變量最小值(5)
程序地址改變量=(特殊操作碼-特殊操作碼最小值)/行號(hào)改變范圍×最小指令長(zhǎng)度(6)
可見(jiàn),式(4)、(5)、(6)與式(1)、(2)、(3)本質(zhì)上是一樣的,只是在數(shù)據(jù)壓縮前后進(jìn)行了一些算術(shù)處理,它們都可以由特殊操作碼準(zhǔn)確得到行號(hào)調(diào)試信息。若一個(gè)行號(hào)調(diào)試信息經(jīng)過(guò)式(4)計(jì)算后超過(guò)特殊操作碼的取值范圍,則說(shuō)明特殊操作碼無(wú)法描述該行號(hào)調(diào)試信息。可以使用標(biāo)準(zhǔn)操作碼或擴(kuò)展操作碼來(lái)描述特殊操作碼不能描述的行號(hào)調(diào)試信息。
式(4)中的行號(hào)改變量最小值、行號(hào)改變范圍、最小指令長(zhǎng)度、特殊操作碼最小值都可以在解析行號(hào)調(diào)試信息之前從.debug_line節(jié)區(qū)獲取。其中“行號(hào)改變范圍”并不是一個(gè)源文件中行號(hào)改變量的實(shí)際最大范圍,而是一個(gè)適中的可以包含大部分行號(hào)改變范圍的值。使用太大的“行號(hào)改變范圍”雖然能夠增加特殊操作碼來(lái)描述的行號(hào)改變量,但是也會(huì)減少特殊操作碼可以描述的程序地址改變量。對(duì)于大于“行號(hào)改變范圍”的行號(hào)改變量,可以使用標(biāo)準(zhǔn)操作碼來(lái)存儲(chǔ)。
若式(4)中的“行號(hào)改變量最小值”、“行號(hào)改變范圍”選取得當(dāng),絕大多數(shù)行號(hào)信息都可以通過(guò)特殊操作碼描述。實(shí)際經(jīng)驗(yàn)表明,一個(gè)代碼書(shū)寫(xiě)規(guī)范的C語(yǔ)言文件,80%以上的行號(hào)調(diào)試信息都可以通過(guò)特殊操作碼來(lái)記錄。一個(gè)特殊操作碼占用1 B,相比STABS格式,至少可以節(jié)省90%以上的存儲(chǔ)空間。
3 節(jié)點(diǎn)縮略信息
DWARF格式中,除行號(hào)調(diào)試信息外,其他調(diào)試信息主要以節(jié)點(diǎn)的形式存放在.debug_info節(jié)區(qū)中。節(jié)點(diǎn)可以描述源文件、函數(shù)、變量、類(lèi)型等調(diào)試信息。調(diào)試信息節(jié)點(diǎn)之間存在父子節(jié)點(diǎn)或兄弟節(jié)點(diǎn)的關(guān)系。一個(gè)源文件的所有調(diào)試信息節(jié)點(diǎn)構(gòu)成一個(gè)調(diào)試信息節(jié)點(diǎn)樹(shù),描述源文件本身調(diào)試信息的節(jié)點(diǎn)是這個(gè)樹(shù)的根節(jié)點(diǎn)。節(jié)點(diǎn)具有各種屬性,調(diào)試信息一般存儲(chǔ)為節(jié)點(diǎn)的屬性值。節(jié)點(diǎn)可以有多種類(lèi)型,屬性也有多種類(lèi)型。一種類(lèi)型的節(jié)點(diǎn)具有的屬性類(lèi)型是不固定的,由調(diào)試信息生成程序定義。表2為常見(jiàn)的節(jié)點(diǎn)類(lèi)型與可能的屬性類(lèi)型。
同一種屬性可以存儲(chǔ)為不同的格式。節(jié)點(diǎn)屬性的格式也是不固定的,由調(diào)試信息生成程序定義。表3為常見(jiàn)的節(jié)點(diǎn)屬性格式。
按照常規(guī)的存儲(chǔ)方法,.debug_info中存儲(chǔ)一個(gè)節(jié)點(diǎn)的調(diào)試信息時(shí),至少需要存儲(chǔ)如下幾類(lèi)信息:
?。?)節(jié)點(diǎn)類(lèi)型;
?。?)節(jié)點(diǎn)是否有子節(jié)點(diǎn);
?。?)節(jié)點(diǎn)的所有屬性的類(lèi)型;
(4)節(jié)點(diǎn)的各個(gè)屬性的格式。
這些信息稱(chēng)為節(jié)點(diǎn)的縮略信息。根據(jù)DWARF格式的定義,存儲(chǔ)節(jié)點(diǎn)類(lèi)型、屬性類(lèi)型、屬性格式至少各需要1 B。若一個(gè)節(jié)點(diǎn)具有N個(gè)屬性,至少需要2+2×N個(gè)字節(jié)來(lái)存儲(chǔ)節(jié)點(diǎn)縮略信息。
對(duì)大多數(shù)程序來(lái)說(shuō),其多數(shù)調(diào)試信息節(jié)點(diǎn)的縮略信息是相同的。例如,若一個(gè)可執(zhí)行文件由若干個(gè)源文件編譯而成,則其包含的若干個(gè)節(jié)點(diǎn)都是源文件調(diào)試信息節(jié)點(diǎn)。若一個(gè)源文件中有若干個(gè)函數(shù),則該源文件調(diào)試信息節(jié)點(diǎn)的若干個(gè)子節(jié)點(diǎn)都是函數(shù)調(diào)試信息節(jié)點(diǎn)類(lèi)型。若函數(shù)中包含若干個(gè)局部變量,則該函數(shù)調(diào)試信息節(jié)點(diǎn)的若干個(gè)子節(jié)點(diǎn)都是變量類(lèi)型。DWARF格式利用調(diào)試信息的這個(gè)特點(diǎn),把節(jié)點(diǎn)的縮略信息抽取出來(lái),放到.debug_abbrev節(jié)區(qū)中。在.debug_info節(jié)區(qū)中只需要引用節(jié)點(diǎn)的縮略信息,并存儲(chǔ)節(jié)點(diǎn)屬性的值即可。圖3為一個(gè)源文件節(jié)點(diǎn)類(lèi)型在.debug_abbrev節(jié)區(qū)中存儲(chǔ)的縮略信息內(nèi)容示意,圖4為這個(gè)節(jié)點(diǎn)的值在.debug_info節(jié)區(qū)中的存儲(chǔ)內(nèi)容示意。
通過(guò)這種方法,可以節(jié)省重復(fù)類(lèi)型節(jié)點(diǎn)縮略信息的存儲(chǔ)空間。例如,若源文件中包括L個(gè)變量,一般每個(gè)變量調(diào)試信息節(jié)點(diǎn)有5個(gè)屬性,這些變量的節(jié)點(diǎn)縮略信息只需存儲(chǔ)一個(gè)即可,可以節(jié)省約10×L字節(jié)存儲(chǔ)空間。顯然,編譯生成可執(zhí)行文件的源文件越多、源文件中的代碼量越多,通過(guò)這種方法節(jié)省的空間就越多。
4 結(jié)論
數(shù)據(jù)壓縮技術(shù)是計(jì)算機(jī)領(lǐng)域廣泛使用的技術(shù)。只要存在數(shù)據(jù)的存儲(chǔ),就可應(yīng)用數(shù)據(jù)壓縮技術(shù)。DWARF格式是一種常用的調(diào)試信息格式,它把調(diào)試信息存儲(chǔ)于可執(zhí)行文件中。為了減少調(diào)試信息占用的可執(zhí)行文件存儲(chǔ)空間,DWARF格式使用了各種方法來(lái)壓縮數(shù)據(jù)。由于DWARF格式可以完整地還原調(diào)試信息,因此這些數(shù)據(jù)壓縮方法是無(wú)損壓縮方法。本文介紹的DWARF格式數(shù)據(jù)壓縮方法對(duì)數(shù)據(jù)壓縮領(lǐng)域有重要的借鑒意義,對(duì)調(diào)試信息生成、分析領(lǐng)域也有重要的參考價(jià)值。
參考文獻(xiàn)
[1] 鄭翠芳.幾種常用無(wú)損數(shù)據(jù)壓縮算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(9):73-76.
[2] 曾玲,饒志宏.幾種數(shù)據(jù)壓縮算法的比較[J].通信技術(shù),2002(9):12-15.
[3] 袁玫,袁文.數(shù)據(jù)壓縮技術(shù)及其應(yīng)用[M].北京:電子工業(yè)出版社,1994.
[4] Unix International Programming Languages SIG. DWARF debugging information format[S]. UNIX International, 1993.
[5] MENAPACE J, KINGDON J, MacKenzie D. The “stabs” debug format[S]. Free Software Foundation, 2003.