ELF: symbol lookup via DT_HASH
Several weeks ago I asked myself how dynamic linker finds printf in libc.so to apply relocations in my "Hello, world!" program.
libc.so contains tons of dynamic symbols exported to the outer world (nm -D /lib/libc.so.6 | wc -l gives 2246 symbols on my machine). And quite a few of them will be imported in any relatively big program.
Obviously, doing linear search would be a bad idea. Some sort of a hash table can be used to optimize the searching through thousands of strings. There're two options. The first is to create a hash table from a plain symbol list during the binary loading. This would introduce a lot of work and allocations during dynamic linking, so it's not such a good solution. The second option is to create a hash table during static linking and save it inside the binary in some serialized format. And this is exactly what happens in the ELF.
Every ELF binary has a hash table filled with symbol names baked into the binary itself. The binary layout of such table and hashing function are briefly defined in the section Hash Table of chapter 5.
I'd like to give some examples of how this table works.
The hashing function is "hard-coded" in the standard so every compiler, static linker, and dynamic linker can use the same one. Otherwise, nothing would work. Here's what the function looks like:
#include <stdint.h>
uint32_t elf_hash(const uint8_t* name) {
uint32_t h = 0, g;
for (; *name; name++) {
h = (h << 4) + *name;
if (g = h & 0xf0000000) {
h ^= g >> 24;
}
h &= ~g;
}
return h;
}
elf_hash("") // 0x00000000
elf_hash("printf") // 0x077905a6
elf_hash("exit") // 0x0006cf04
elf_hash("syscall") // 0x0b09985c
elf_hash("flapenguin.me") // 0x03987915
Once the string, symbol, and hash tables are located via section headers (or program headers, or _DYNAMIC) they can be used to find a symbol by its name.
The hash table looks like this (this is of course not a valid C structure declaration, but it should give an idea of how things are stored):
struct elf_hash_table {
uint32_t nbucket;
uint32_t nchain;
uint32_t bucket[nbucket];
uint32_t chain[nchain];
};
chain array contains chains (very unexpected) of symbol indexes within the same bucket. A chain starts at bucket[hash % nbucket] index. You should walk through the chain by interpreting chain[ix] value as the index of the next symbol and the next chain element. Finally you’ll bump into the STN_UNDEF symbol (dummy “undefined” symbol), which is always the last symbol of any chain.
The ELF obligates the Symbol Table to hold the STN_UNDEF symbol at 0 index. So effectively a chain breaks when current index is 0.
Since the chain array values are indexes for not only the chain array itself, but also for the symbol table, the chain array must be the same size as the symbol table. This makes nchain equal to the length of the symbol table, which designers of the ELF seem to have forgotten to add to the dynamic program information.
To visualize a hash table I've taken the first 15 definitely public (not beginning with an underscore) symbols from libc.so and constructed a hash table from them.
nbucket = 4 (because I decided that there will be four buckets)
nchain = 16 (16 symbols, including the SHT_UNDEF at index 0)
ix bucket[ix] name of first symbol in chain
-- ---------- -----------------------------
0 2 freelocal
1 8 setrlimi
2 1 isnan
3 3 hcreate_
Two asterisks ** and parens () indicate the start of a chain, so it's
easier to see.
SYMBOL TABLE | HASH TABLE
|
name = | hash = hash %
ix symtab[ix].st_name | elf_hash(name) nbucket chain[ix]
-- ------------------ | -------------- ------- ---------
0 <STN_UNDEF> |
1 isnan | 0x0070a47e 2 ** /------(5)
2 freelocal | 0x0bc334fc 0 ** | /----(4)
3 hcreate_ | 0x0a8b8c4f 3 ** | | (6)-----\
4 getopt_long_onl | 0x0f256dbc 0 | \--> 12 -----|-\
5 endrpcen | 0x04b96f7e 2 \-----> 7 ---\ | |
6 pthread_mutex_lock | 0x0de6a18b 3 0 <--|-/ |
7 isinf | 0x0070a046 2 /--- 9 <--/ |
8 setrlimi | 0x0cb929a9 1 ** | (11)-----\ |
9 getspen | 0x0dcba6de 2 \-> 10 ---\ | |
10 umoun | 0x007c46be 2 /---- 13 <--/ | |
11 strsigna | 0x0b99fbe1 1 | 0 <----/ |
12 listxatt | 0x00abef84 0 | /-- 15 <------/
13 getttyen | 0x0cbbb96e 2 \-|-> 14 ---\
14 uselib | 0x07c9c2f2 2 | 0 <--/
15 cfsetispeed | 0x0b63b274 0 \--> 0
Now that we have this table, let's try to find some symbols by hand:
freelocal:hash = elf_hash("freelocal") = 0x0bc334fc chain starts at bucket[0x0bc334fc % 4] = bucket[0] = 2 symbols[2] (= "freelocal") == "freelocal"? yep => found at index 2getspen:hash = elf_hash("getspen") = 0x0dcba6de chain starts at bucket[0x0dcba6de % 4] = bucket[2] = 1 symbols[2] (= "isnan") == "getspen"? nope => chain continues at 5 symbols[4] (= "endrpcen") == "getspen"? nope => chain continues at 7 symbols[8] (= "setrlimi") == "getspen"? nope => chain continues at 9 symbols[9] (= "getspen") == "getspen"? yep => found at index 9foobar:hash = elf_hash("foobar") = 0x06d65882 chain starts at bucket[0x06d65882 % 4] = bucket[2] = 1 symbols[ 1] (= "isnan") == "foobar"? nope => chain continues at 5 symbols[ 5] (= "endrpcen") == "foobar"? nope => chain continues at 7 symbols[ 7] (= "isinf") == "foobar"? nope => chain continues at 9 symbols[ 9] (= "getspen") == "foobar"? nope => chain continues at 10 symbols[10] (= "umoun") == "foobar"? nope => chain continues at 13 symbols[13] (= "getttyen") == "foobar"? nope => chain continues at 14 symbols[14] (= "uselib") == "foobar"? nope => chain continues at 0 symbols[ 0] is STN_UNDEF => not found
And now that we can do a lookup manually, let's actually code it. It should be self-explanatory:
/* Different architecture have different symbol structure size. */
typedef Elf64_Sym Elf_Sym;
/* typedef Elf32_Sym Elf_Sym; */
const Elf_Sym* elf_lookup(
const char* strtab, /* string table */
const Elf_Sym* symtab, /* symbol table */
const uint32_t* hashtab, /* hash table */
const char* symname /* name to look up */
) {
const uint32_t hash = elf_hash(symname);
const uint32_t nbucket = hashtab[0];
const uint32_t nchain = hashtab[1];
const uint32_t* bucket = &hashtab[2];
const uint32_t* chain = &bucket[nbucket];
for (uint32_t i = bucket[hash % nbucket]; i; i = chain[i]) {
if (strcmp(symname, strtab + symtab[i].st_name) == 0) {
return &symtab[i];
}
}
return NULL;
}
Note that ideally we shouldn't have used the symbol table as a simple array. The standard doesn't say that the symbol structure size will remain the same after amendments, so it requires us to use
sh_entsizefrom section header instead of simplesizeof(Elf_Sym)(which is what array indexing is based on).So
symtab[i]should be*(const Elf_Sym*)((char*)symtab + i*sh_entsize).But in reality the symbol structure never grew and won't do so in any near future. Otherwise it'll break a lot of applications and libraries, which already use simple array indexing.
I want to mention that while DT_HASH is very good at finding existing symbols, it performs badly with the missing ones. As you could see in the example with searching for "foobar", you need to walk through a random chain and compare strings only to bump into the STN_UNDEF. This becomes even worse in real life because symbols are searched in multiple shared libraries, so you'll have to walk multiple random chains.
Smart people noticed that problem and created a new hash table called DT_GNU_HASH, which is nowadays used almost everywhere instead of DT_HASH. The sad part is that DT_GNU_HASH is not in fact standardized, nor is it even described anywhere but in the BFD (Binary File Descriptor library) source code.
Next time I'll dig into DT_GNU_HASH and show how to use and construct it by hand.
Thanks to Windel Bouwman who noticed that hashes in the example table were incorrect. It's fixed now.