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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| static bool is_symbol_global_and_defined(const struct elf_module *m, const ElfW(Sym) *s)
{
if (ELFW(ST_BIND)(s->st_info) == STB_GLOBAL || ELFW(ST_BIND)(s->st_info) == STB_WEAK)
return s->st_shndx != SHN_UNDEF;
return false;
}
static uint32_t elfhash(const char *name)
{
const uint8_t *name_bytes = (const uint8_t *)name;
uint32_t h = 0, g;
while (*name_bytes) {
h = (h << 4) + *name_bytes++;
g = h & 0xf0000000;
h ^= g;
h ^= g >> 24;
}
return h;
}
static ElfW(Sym) *elfhash_lookup(struct elf_module *m, const char *name)
{
uint32_t n;
uint32_t hash = elfhash(name);
ElfW(Sym) *symtab = m->symtab;
const char *strtab = m->strtab;
LOG_DEBUG("SEARCH %s in %s@0x%zx %08x %zu", name, m->name, m->base, hash, hash % m->nbucket);
for (n = m->bucket[hash % m->nbucket]; n != 0; n = m->chain[n]) {
ElfW(Sym) *s = symtab + n;
if (strcmp(strtab + s->st_name, name))
continue;
if (is_symbol_global_and_defined(m, s)) {
LOG_DEBUG("FOUND %s in %s (%zx) %zu", name, m->name, s->st_value, s->st_size);
return s;
}
}
return NULL;
}
static uint32_t gnuhash(const char *name)
{
const uint8_t *name_bytes = (const uint8_t *)name;
uint32_t h = 5381;
while (*name_bytes != 0)
h += (h << 5) + *name_bytes++;
return h;
}
static ElfW(Sym) *gnuhash_lookup(struct elf_module *m, const char *name)
{
uint32_t n;
uint32_t hash = gnuhash(name);
uint32_t h2 = hash >> m->gnu_shift2;
uint32_t bloom_mask_bits = sizeof(ElfW(Addr)) * 8;
uint32_t word_num = (hash / bloom_mask_bits) & m->gnu_maskwords;
ElfW(Addr) bloom_word = m->gnu_bloom_filter[word_num];
ElfW(Sym) *symtab = m->symtab;
const char *strtab = m->strtab;
LOG_DEBUG("SEARCH %s in %s@%p (gnu)", name, m->name, (void *)m->base);
if ((1 & (bloom_word >> (hash % bloom_mask_bits)) & (bloom_word >> (h2 % bloom_mask_bits))) == 0) {
LOG_DEBUG("NOT FOUND %s in %s@%p (gnu)", name, m->name, (void *)m->base);
return NULL;
}
n = m->gnu_bucket[hash % m->gnu_nbucket];
if (n == 0) {
LOG_DEBUG("NOT FOUND %s in %s@%p (gun)", name, m->name, (void *)m->base);
return NULL;
}
do {
ElfW(Sym) *s = symtab + n;
if (((m->gnu_chain[n] ^ hash) >> 1) != 0)
continue;
if (strcmp(strtab + s->st_name, name))
continue;
if (is_symbol_global_and_defined(m, s)) {
LOG_DEBUG("FOUND %s in %s (%p) %zd", name, m->name, (void *)s->st_value, (size_t)s->st_size);
return s;
}
} while ((m->gnu_chain[n++] & 1) == 0);
return NULL;
}
ElfW(Sym) *lookup_symbol_in_module(struct elf_module *m, const char *name)
{
return (m->flags & FLAG_GNU_HASH) ? gnuhash_lookup(m, name) : elfhash_lookup(m, name);
}
|
