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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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):

1
2
3
4
5
6
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.

1
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  1           isnan
 1  2           freelocal
 2  3           hcreate_
 3  6           pthread_mutex_lock

Two asterisks (**) 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              | 0x070a484c      0 **     /------ 5
 2  freelocal          | 0x0c335095      1 **     |  /--- 4
 3  hcreate_           | 0x08b8c5c2      2 **     |  |    7 ---\
 4  getopt_long_onl    | 0x0256dcc9      1        |  \--> 0    |
 5  endrpcen           | 0x0b96f814      0        \-----> 8 ---|-\
 6  pthread_mutex_lock | 0x0de6a18b      3 **             0    | |
 7  isinf              | 0x070a04c6      2        /----- 12 <--/ |
 8  setrlimi           | 0x0b929bc4      0        |  /--- 9 <----/
 9  getspen            | 0x0cba6e84      0        |  \-> 10 --\
10  umoun              | 0x07c46c54      0        |  /-- 11 <-/
11  strsigna           | 0x099fbecc      0        |  \-> 13 ----\
12  listxatt           | 0x0abef8b2      2        \----> 14 --\ |
13  getttyen           | 0x0bbb9794      0           /-- 15 <-|-/
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:

  1. freelocal:

    1
    hash = elf_hash("freelocal") = 0x0c335095
    chain starts at bucket[0x0c335095 % 4] = bucket[1] = 2
    
    symbols[2] ("freelocal") == "freelocal"? yep => found at index 2
  2. getspen:

    1
    hash = elf_hash("getspen") = 0cba6e84
    chain starts at bucket[0cba6e84 % 4] = bucket[0] = 1
    
    symbols[1] ("isnan")    == "getspen"? nope  => chain continues at 5
    symbols[5] ("endrpcen") == "getspen"? nope  => chain continues at 8
    symbols[8] ("setrlimi") == "getspen"? nope  => chain continues at 9
    symbols[9] ("getspen")  == "getspen"? yep   => found at index 9
  3. foobar

    1
    hash = elf_hash("foobar") = 0x06d65882
    chain starts at bucket[0x06d65882 % 4] = bucket[2] = 3
    
    symbols[ 3] ("hcreate_") == "foobar"? nope  => chains continues at  7
    symbols[ 7] ("isinf")    == "foobar"? nope  => chains continues at 12
    symbols[12] ("listxatt") == "foobar"? nope  => chains continues at 14
    symbols[14] ("uselib")   == "foobar"? nope  => chains 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:

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
/* 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_entsize from section header instead of simple sizeof(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.