ELF的hash算法

Posted on | In

..1. 目录

ELF HASH

ELF的哈希表提供了对符号表的访问
组织结构如下:

labels
nbucket
nchain
bucket[0]
…
bucket[nbucket-1]
chain[0]
…
chain[nchain-1]
说明
  • bucket和chain的数量是相等的
  • 每个符号值对应一个字符串
  • 基本查找流程
    • 使用elf_hash得到hash值
    • 对hash值取模计算存放的符号值的桶
    • 如果该桶内没有数据则结束
    • 如果桶内内有数据不匹配
      • 以该符号值为下标的 chain 中存在下一个符号值
      • 重复该步骤直到找到和目标字符串匹配
    • 找到符号值对应的字符串以及符号加载时的偏移信息和符号地址信息
结论
  • chain 的数量必然大于符号的数量
  • 不考虑性能, 桶的数量可以小于符号的数量 也可以同时小于chain的数量
  • 遇到冲突后从 chain 表中查找以出现冲突的符号值为下标位置的chain, 如果该chain无内容则从符号表中查找匹配的符号的值填充该chain
    • 如果有内容并且符号值依然冲突, 则用该冲突的符号值为索引继续查找下一个
    • 最差情况则相当于直接遍历符号表

ELF HASH源码

linux 2.4.0 -> irqueue.c
linux main 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 *    This function hash the input string ''name'' using the ELF hash
 *    function for strings.
 */
static unsigned int hash(char* name)
{
    unsigned int h = 0;
    unsigned int g;

    while(*name) {
        h = (h<<4) + *name++;
        if ((g = (h & 0xf0000000)))
            h ^=g>>24;
        h &=~g;
    }
    return h;
}

vDSO/parse_vdso.c
使用elf hash获取符号所在的偏移地址 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void *vdso_sym(const char *version, const char *name)
{
	unsigned long ver_hash;
	if (!vdso_info.valid)
		return 0;

	ver_hash = elf_hash(version);
	ELF(Word) chain = vdso_info.bucket[elf_hash(name) % vdso_info.nbucket];

	for (; chain != STN_UNDEF; chain = vdso_info.chain[chain]) {
		ELF(Sym) *sym = &vdso_info.symtab[chain];

		/* Check for a defined global or weak function w/ right name. */
		if (ELF64_ST_TYPE(sym->st_info) != STT_FUNC)
			continue;
		if (ELF64_ST_BIND(sym->st_info) != STB_GLOBAL &&
		    ELF64_ST_BIND(sym->st_info) != STB_WEAK)
			continue;
		if (sym->st_shndx == SHN_UNDEF)
			continue;
		if (strcmp(name, vdso_info.symstrings + sym->st_name))
			continue;

		/* Check symbol version. */
		if (vdso_info.versym
		    && !vdso_match_version(vdso_info.versym[chain],
					   version, ver_hash))
			continue;

		return (void *)(vdso_info.load_offset + sym->st_value);
	}

	return 0;
}