前言
ELF格式的.gnu.hash節(jié)在設(shè)計(jì)上比較復(fù)雜，直接從glibc源碼進(jìn)行分析的難度也比較大。今天靜下心來(lái)看了這篇精彩的文章，終于將布隆濾波器、算數(shù)運(yùn)算轉(zhuǎn)為位運(yùn)算等一系列細(xì)節(jié)搞懂了（值得一提的是，這篇博客十分值得花一些時(shí)間讀懂，它不僅對(duì)總體有一個(gè)較好的描述，而且還涉及了許多有益的實(shí)現(xiàn)細(xì)節(jié)）。但本人愚鈍異常，沒(méi)有一個(gè)完整的walkthrough就不能覺(jué)得自己真的搞懂了一個(gè)東西。所以本文從查找一個(gè)符號(hào)的真實(shí)情況出發(fā)，把ELF格式是如何組織一個(gè)符號(hào)，以及動(dòng)態(tài)鏈接器如何讀取并處理這些信息以進(jìn)行符號(hào)查詢的全過(guò)程詳細(xì)地講清楚。
本文假定讀者已經(jīng)讀過(guò)上文中提到的博客，并理解布隆濾波器，GNU hash采用的單一哈希策略，把取模轉(zhuǎn)為取與這些名詞。在后續(xù)有時(shí)間時(shí)我可能會(huì)對(duì)它們進(jìn)行簡(jiǎn)單介紹，但珠玉在前讓人確實(shí)不想獻(xiàn)丑。
本文的實(shí)現(xiàn)以及so文件均以glibc 2.31為準(zhǔn)。
符號(hào)哈希，符號(hào)表與字符表
一個(gè)符號(hào)的相關(guān)信息會(huì)在ELF文件中dynamic section的三塊出現(xiàn)：.gnu.hash對(duì)應(yīng)的符號(hào)哈希，.dynsym對(duì)應(yīng)的動(dòng)態(tài)符號(hào)表，.dynstr對(duì)應(yīng)的字符表。在查找符號(hào)時(shí)，動(dòng)態(tài)鏈接器首先從.gnu.hash中進(jìn)行查詢，得到該符號(hào)在動(dòng)態(tài)符號(hào)表中的偏移。動(dòng)態(tài)鏈接器根據(jù)這個(gè)偏移讀出一個(gè)符號(hào)，并找到這個(gè)符號(hào)的名字在字符表中的偏移。從字符表中讀出符號(hào)的名稱如果與要查找的符號(hào)匹配，則找到了這個(gè)符號(hào)，再?gòu)姆?hào)表中讀出符號(hào)的相關(guān)信息并返回。
64位ELF格式的符號(hào)定義如下：
// in elf.h>
typedef struct
{
// 32 bits
Elf64_Word st_name; /* Symbol name (string tbl index) */
// 8 bit
unsigned char st_info; /* Symbol type and binding */
// 8 bit
unsigned char st_other; /* Symbol visibility */
// 16 bits
Elf64_Section st_shndx; /* Section index */
// 64 bits
Elf64_Addr st_value; /* Symbol value */
// 64 bits
Elf64_Xword st_size; /* Symbol size */
} Elf64_Sym;
這個(gè)數(shù)據(jù)結(jié)構(gòu)占用內(nèi)存的大小為24B，這也是合理安排成員順序以節(jié)約文件大小的一個(gè)例子。
.gnu.hash的結(jié)構(gòu)
glibc使用如下函數(shù)從ELF文件中讀取符號(hào)哈希相關(guān)信息：
// in elf/dl-lookup.c
void
_dl_setup_hash (struct link_map *map)
{
Elf_Symndx *hash;
if (__glibc_likely (map->l_info[ELF_MACHINE_GNU_HASH_ADDRIDX] != NULL))
{
// 一個(gè)指向32位長(zhǎng)內(nèi)存的指針，用來(lái)讀取哈希相關(guān)變量，故名hash32
Elf32_Word *hash32
= (void *) D_PTR (map, l_info[ELF_MACHINE_GNU_HASH_ADDRIDX]);
map->l_nbuckets = *hash32++;
Elf32_Word symbias = *hash32++;
Elf32_Word bitmask_nwords = *hash32++;
/* Must be a power of two. */
assert ((bitmask_nwords (bitmask_nwords - 1)) == 0);
map->l_gnu_bitmask_idxbits = bitmask_nwords - 1;
map->l_gnu_shift = *hash32++;
map->l_gnu_bitmask = (ElfW(Addr) *) hash32;
hash32 += __ELF_NATIVE_CLASS / 32 * bitmask_nwords;
map->l_gnu_buckets = hash32;
hash32 += map->l_nbuckets;
map->l_gnu_chain_zero = hash32 - symbias;
/* Initialize MIPS xhash translation table. */
ELF_MACHINE_XHASH_SETUP (hash32, symbias, map);
return;
}
// 以下處理古老的DT_HASH項(xiàng)，現(xiàn)已不用
if (!map->l_info[DT_HASH])
return;
hash = (void *) D_PTR (map, l_info[DT_HASH]);//Q: what about some non-GNU ELFs
map->l_nbuckets = *hash++;
/* Skip nchain. */
hash++;
map->l_buckets = hash;
hash += map->l_nbuckets;
map->l_chain = hash;
}
上述代碼讀取了關(guān)鍵變量賦值：l_nbuckets，symbias，bitmask_nwords，l_gnu_shift，l_gnu_buckets，l_gnu_chain_zero。其中，以“l(fā)”開頭的變量存儲(chǔ)在ELF文件的link_map中，具體定義見(jiàn)link.h>。還有不是從文件中讀出的變量l_gnu_bitmask_idxbits，它們的具體含義為：
- l_nbuckets：使用哈希桶的數(shù)量
- symbias：動(dòng)態(tài)符號(hào)表中外部不能訪問(wèn)的符號(hào)數(shù)量，但它們?nèi)匀徽加昧藙?dòng)態(tài)符號(hào)表項(xiàng)
- bitmask_nwords：使用bitmask_nwords個(gè)字作為布隆濾波器的向量
- l_gnu_shift：為使用同一哈希函數(shù)實(shí)現(xiàn)k=2的布隆濾波器，需要右移的位數(shù)
- l_gnu_buckets：哈希桶的開始地址
- l_gnu_chain_zero：符號(hào)哈希值的開始地址
- l_gnu_bitmask_idxbits：為對(duì)bitmask_nwords取模化為取與，由bitmask_nwords-1而來(lái)
為了便于理解，將.gnu.hash節(jié)中的內(nèi)容畫成示意圖：
以libc為例。檢查對(duì)應(yīng)字段的值：
$ objdump -s /lib/x86_64-linux-gnu/libc.so.6 | grep .gnu.hash -A 5
Contents of section .gnu.hash:
38a0 (f3030000) (0c000000) (00010000) (0e000000) ................
->l_nbuckets=1011 ->symbias=12 ->bitmask_nwords=256 ->l_gnu_shift=14
38b0 (00301044 a0200201) (8803e690 c5458c00) .0.D. .......E..
->第一個(gè)bloom word 0x010220a044103000
38c0 c4005800 07840070 c280010d 8a0c4104 ..X....p......A.
38d0 10008840 32082a40 88543c2d 200e3248 ...@2.*@.T- .2H
38e0 2684c08c 04080002 020ea1ac 1a0666c8 .............f.
可以看到symbias=12，即有12個(gè)內(nèi)部符號(hào)：
$ readelf -s /lib/x86_64-linux-gnu/libc.so.6 | head -n 20
Symbol table '.dynsym' contains 2367 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
1: 0000000000000000 0 NOTYPE WEAK DEFAULT UND __libpthread_freeres
2: 0000000000000000 0 OBJECT GLOBAL DEFAULT UND _rtld_global@GLIBC_PRIVATE (33)
3: 0000000000000000 0 OBJECT GLOBAL DEFAULT UND __libc_enable_secure@GLIBC_PRIVATE (33)
4: 0000000000000000 0 FUNC GLOBAL DEFAULT UND __tls_get_addr@GLIBC_2.3 (34)
5: 0000000000000000 0 FUNC GLOBAL DEFAULT UND _dl_exception_create@GLIBC_PRIVATE (33)
6: 0000000000000000 0 OBJECT GLOBAL DEFAULT UND _rtld_global_ro@GLIBC_PRIVATE (33)
7: 0000000000000000 0 FUNC GLOBAL DEFAULT UND __tunable_get_val@GLIBC_PRIVATE (33)
8: 0000000000000000 0 FUNC GLOBAL DEFAULT UND _dl_find_dso_for_object@GLIBC_PRIVATE (33)
9: 0000000000000000 0 NOTYPE WEAK DEFAULT UND _dl_starting_up
10: 0000000000000000 0 NOTYPE WEAK DEFAULT UND __libdl_freeres
11: 0000000000000000 0 OBJECT GLOBAL DEFAULT UND _dl_argv@GLIBC_PRIVATE (33)
12: 00000000000ab970 33 FUNC GLOBAL DEFAULT 16 __strspn_c1@GLIBC_2.2.5
13: 0000000000089260 352 FUNC GLOBAL DEFAULT 16 putwchar@@GLIBC_2.2.5
14: 00000000001324f0 20 FUNC GLOBAL DEFAULT 16 __gethostname_chk@@GLIBC_2.4
15: 00000000000ab9a0 44 FUNC GLOBAL DEFAULT 16 __strspn_c2@GLIBC_2.2.5
16: 000000000014f580 218 FUNC GLOBAL DEFAULT 16 setrpcent@@GLIBC_2.2.5
可見(jiàn)符號(hào)0-11為內(nèi)部符號(hào)。
查找符號(hào)
下面以查找符號(hào)printf為例，介紹符號(hào)查找的過(guò)程。
首先使用下面的哈希函數(shù)生成符號(hào)的32位哈希：
// in elf/dl-lookup.c
static uint_fast32_t
dl_new_hash (const char *s)
{
uint_fast32_t h = 5381;
for (unsigned char c = *s; c != '\0'; c = *++s)
h = h * 33 + c;
return h 0xffffffff;
}
得到printf的哈希值為0x156b2bb8。
隨后計(jì)算布隆濾波器需要的兩個(gè)hashbit：
unsigned int hashbit1 = new_hash (__ELF_NATIVE_CLASS - 1);
unsigned int hashbit2 = ((new_hash >> l->l_gnu_shift) (__ELF_NATIVE_CLASS - 1));
得到hashbit1 = 56，hashbit2 = 44。
找到該hash對(duì)應(yīng)的bloom word：
const Elf64_Addr *bitmask = l->l_gnu_bitmask;
// l->l_gnu_bitmask_idxbits = bitmask_nwords - 1，將取模變?yōu)槿∨c
// (new_hash / __ELF_NATIVE_CLASS) l->l_gnu_bitmask_idxbits = 174
Elf64_Addr bitmask_word = bitmask[(new_hash / __ELF_NATIVE_CLASS) l->l_gnu_bitmask_idxbits];
printf對(duì)應(yīng)的hash在第174個(gè)bloom word處，它的值位于bloom word的開始地址0x38b0+174*8=3e20
檢查3e20處對(duì)應(yīng)的值：
$ objdump -s /lib/x86_64-linux-gnu/libc.so.6 | grep " 3e20 "
3e20 d0884a41 c0703429 10ec4303 92003103 ..JA.p4)..C...1.
其bloom word為0x293470c0414a88d0。
將其右移56位：0b0010 1001
將其右移44位：0b10 1001 0011 0100 0111
二者的最后一位均為1，說(shuō)明布隆濾波器不能拒絕這個(gè)哈希值。
這時(shí)在對(duì)應(yīng)的哈希桶上進(jìn)行尋找：
Elf32_Word bucket = l->l_gnu_buckets[new_hash % l->l_nbuckets];
由于0x156b2bb8 % 1011 = 295，需要找到第296個(gè)哈希桶。
而哈希桶的起始地址為l_gnu_bitmask + 64 / 32 * bitmask_nwords = 0x40b0，對(duì)應(yīng)哈希桶的地址為0x40b0+295*4=0x454c。
查看0x454c處對(duì)應(yīng)的哈希桶內(nèi)容：
$ objdump -s /lib/x86_64-linux-gnu/libc.so.6 | grep " 4540 "
4540 77020000 00000000 7a020000 **7c020000** w.......z...|...
哈希桶的內(nèi)容為0x27c。
而l_gnu_chain_zero的地址為：
l_gnu_chain_zero = l_gnu_buckets + l_nbuckets - symbias;
可計(jì)算出l_gnu_chain_zero的地址為0x504c，所以第296個(gè)哈希桶包含的真正哈希位于0x504c+27c*4=0x5a3c
查看具體的哈希內(nèi)容：
$ objdump -s /lib/x86_64-linux-gnu/libc.so.6 | grep " 5a30 " -A 2
5a30 ade8dbbb 142dcb13 bb86f85f e6952000 .....-....._.. .
5a40 **b82b6b15** 0a05f1d5 deb6427f 856177fd .+k.......B..aw.
5a50 1ae585e7 ec296fa8 1ae585e7 29ce248f .....)o.....).$.
于0x5a40處找到我們之前計(jì)算的哈希0x156b2bb8（注意小端序）。
此時(shí)，這個(gè)符號(hào)在.gnu.hash的下標(biāo)，就是它在動(dòng)態(tài)符號(hào)表中的(下標(biāo)-symbias)。但由于之前l(fā)_gnu_chain_zero已經(jīng)整體減掉了symbias，所以此處用該符號(hào)的地址減掉l_gnu_chain_zero可直接得到符號(hào)在符號(hào)表中的下標(biāo)。
0x5a40 - 0x504c = 0x9f4 = 2548，由于一個(gè)哈希值為4字節(jié)，故下標(biāo)為2548 / 4 = 637
找到動(dòng)態(tài)符號(hào)表的起始地址：
$ objdump -s /lib/x86_64-linux-gnu/libc.so.6 | grep .dynsym -A 1
Contents of section .dynsym:
07548 00000000 00000000 00000000 00000000 ................
上文中提到，64位ELF文件中一個(gè)符號(hào)的長(zhǎng)度位24字節(jié)，故符號(hào)在符號(hào)表上的起始地址應(yīng)當(dāng)為0x7548 + 24*637 = 0xb100
找到動(dòng)態(tài)符號(hào)表對(duì)應(yīng)位置的內(nèi)容：
$ objdump -s /lib/x86_64-linux-gnu/libc.so.6 | grep " 0b0f8 " -A 1
0b0f8 16000000 00000000 **f3040000** 12001000 ................
0b108 104e0600 00000000 cc000000 00000000 .N..............
讀出符號(hào)在字符表上的偏移量為0x4f3。
找到字符表的起始地址：
$ objdump -s /lib/x86_64-linux-gnu/libc.so.6 | grep .dynstr -A 1
Contents of section .dynstr:
15330 00786472 5f755f6c 6f6e6700 5f5f7763 .xdr_u_long.__wc
起始地址為0x15330，故該符號(hào)的地址為0x15330 + 0x4f3 = 0x15823
讀出字符表對(duì)應(yīng)位置的值：
$ objdump -s /lib/x86_64-linux-gnu/libc.so.6 | grep " 15820 " -A 1
15820 494f5f**70** 72696e74 66007265 67697374 IO_printf.regist
15830 65725f70 72696e74 665f6675 6e637469 er_printf_functi
查找到了符號(hào)printf，它是IO_printf的別名，在字符表中為了節(jié)省空間將二者合并了。
這樣，就完成了一次符號(hào)查詢的全過(guò)程。
以上就是從實(shí)例分析ELF格式的.gnu.hash區(qū)與glibc的符號(hào)查找的詳細(xì)內(nèi)容，更多關(guān)于ELF格式的.gnu.hash區(qū)與glibc的符號(hào)查找的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
