DT_HASH and DT_GNU_HASH preparation by linker

Example of linker development reflecting loader implementation

Here, I will show you how to prepare codes to resolve API dynamically on linker through reading elf loader codes(musl libc :: ldso/dynlink.c).

On elf format, either of two API hash tables needs to be prepared to provide export symbols as a shared library to other demanding libraries or executables.

Simpler one is called DT_HASH and daily-used, rather sophisticated one is DT_GNU_HASH.

Both shares a basic role. It is to minimise the computational cost of calling strcmp when resolving own export symbols.

When an import symbol comes, 32bit hash is calculated in its own way, and if the hash is in the hash table, it provides dynamic symbol table index.

DT_HASH function is

static uint32_t sysv_hash(const char *s0)
{
    const unsigned char *s = (void *)s0;
    uint_fast32_t h = 0;
    while (*s) {
        h = 16*h + *s++;
        h ^= h>>24 & 0xf0;
    }
    return h & 0xfffffff;
}

GNU_HASH function is

static uint32_t gnu_hash(const char *s0)
{
    const unsigned char *s = (void *)s0;
    uint_fast32_t h = 5381;
    for (; *s; s++)
        h += h*32 + *s;
    return h;
}

DT_HASH

typedef struct /*dt_hash_table */{
  uint32_t nbucket;
  uint32_t nchain;
  // it depends on above 2.
  uint32_t bucket[nbucket];
  uint32_t chain[nchain];
} DtHashTable;

The computed hash is used for accessing hash table index, Starting thinking things naively, suppose you prepare 4byte array(assuming dynamic symbol table index is represented as 4byte) in a range of 32bit hash, you need 4byte times 2³² (Since every hash value store distinct values.), which is too much to allocate.

You cannot change hash function and the output bit range, but you can adjust the size of hash table by setting your own bucket size as modular of a hash value.

Actually, 4bytes on each hash value are not enough considering possibility of hash collision. For instance, you need to store a chain to trace when a given symbol is not matched with the element stored in the table index and two hash values are shared between multiple API strings.

If a hash collides, then the index of the array stores an index of next symbol table index. The last element of the chain means index is 0.

static Sym *sysv_lookup(const char *s, uint32_t h, struct dso *dso)
{
    size_t i;
    Sym *syms = dso->syms;
    Elf_Symndx *hashtab = dso->hashtab;
    char *strings = dso->strings;
    for (i=hashtab[2+h%hashtab[0]]; i; i=hashtab[2+hashtab[0]+i]) {
        if ((!dso->versym || dso->versym[i] >= 0)
            && (!strcmp(s, strings+syms[i].st_name)))
            return syms+i;
    }
    return 0;
}

Considering these, a linker needs to prepare a code for generating corresponding output.

static void check_collision(uint32_t* bucket, uint32_t* chain, uint32_t mod, uint32_t sym_index) {

  uint32_t* p = 0;
  if (*(bucket + mod)) {   
    for (p = chain + *(bucket + mod) ; *p ; p = chain + *p);
    *p = sym_index;
  } else {
    // no collision
    *(bucket + mod) = sym_index;
  }
}

First, you take a look at bucket *(bucket + mod). If it does not collide, insert symbol table index. If it does, then trace the chain which stores next symbol information, for (p = chain + *(bucket + mod) ; *p ; p = chain + *p); and set symbol index at the tail of it.

DT_GNU_HASH

typedef struct {
  uint32_t nbuckets;
  uint32_t symoffset;
  uint32_t bloom_size;
  uint32_t bloom_shift;
  size_t bloom[/*bloom_size*/];
  uint32_t buckets[/*nbuckets*/];
  uint32_t chain[];
} gnu_hash_table;

After all, you have to call strcmp to validate if the chain matches the input, and DT_HASH does so often. It is much less than calling all of it if bucket is big enough and hash values are distributed rather equally.

Most cases, an import API wants to find just one export API on multiple dynamic symbol tables on each dynamic shared objects. And the cost depends on number of all export symbols on every shared library before matched one because elf loader does not remember any tags of API and shared library name unlike on windows. People started introducing bloom filter which prevents iterating hash table on hash collision.

The idea sounds difficult, but code is not as difficult as it sounds.

static inline struct symdef find_sym2(struct dso *dso, const char *s, int need_def, int use_deps)
{
    uint32_t h = 0, gh = gnu_hash(s), gho = gh / (8*sizeof(size_t)), *ght;
    size_t ghm = 1ul << gh % (8*sizeof(size_t));
    struct symdef def = {0};
    struct dso **deps = use_deps ? dso->deps : 0;
    for (; dso; dso=use_deps ? *deps++ : dso->syms_next) {
        Sym *sym;
        if ((ght = dso->ghashtab)) {
            sym = gnu_lookup_filtered(gh, ght, dso, s, gho, ghm);

static Sym *gnu_lookup_filtered(uint32_t h1, uint32_t *hashtab, struct dso *dso, const char *s, uint32_t fofs, size_t fmask)
{
    const size_t *bloomwords = (const void *)(hashtab+4);
    size_t f = bloomwords[fofs & (hashtab[2]-1)];
    if (!(f & fmask)) return 0;

    f >>= (h1 >> hashtab[3]) % (8 * sizeof f);
    if (!(f & 1)) return 0;

    return gnu_lookup(h1, hashtab, dso, s);
}

GNU_HASH_TABLE manages so called bloom bits to record if a given symbol exists on the entire hash table.

From the above code, you can see next interpretation.

Set a bit vector named bloomword

const size_t *bloomwords = (const void *)(hashtab+4);
Pick up an index of bit vectors chunked by 8 * sizeof(size_t).
gho = gh / (8*sizeof(size_t))
size_t f = bloomwords[fofs & (hashtab[2]-1)];
Set two bits on it.
// 1 << (hash % (8 * sizeof(size_t)))
size_t ghm = 1ul << gh % (8*sizeof(size_t));
// (hash >> bloom shift) % (8 * sizeof(size_t))
f >>= (h1 >> hashtab[3]) % (8 * sizeof f);
If the one of bits is not set. you can make sure the symbol is not on the hash table.
if (!(f & fmask)) return 0;
if (!(f & 1)) return 0;

Given this, linker should prepare the bloom bits together with storing an export symbol.

static void set_bloom_bits(uint32_t gh) {

  gnu_hash_table* hash_table_p = D[GNU_HASH_INDEX].data_p;
  size_t shift1 = gh % (8*sizeof(size_t));
  size_t shift2 = (gh >> hash_table_p->bloom_shift) % (8 * sizeof (size_t));
  size_t bit1 = 1ul << shift1;
  size_t bit2 = 1ul << shift2;

  // 32bit hash is devided by 64 or 32 and get the index of bloom vector.
  uint32_t index = gh / (8*sizeof(size_t));
  size_t* vector = &hash_table_p->bloom_array + (index & (hash_table_p->bloom_size-1));
  *vector = *vector | bit1 | bit2;
}

Argument gh is a value coputed by the hash function.

Bit vector is &hash_table_p->bloom_array.
Index of bit vector is (hash value % 64(or 32)) & (bloomsize - 1).

After you know which 64bit vector needs to be modified, compute bit in a following way.
- original hash value % 64(or 32)
- shifted hash value %64 (or 32)
  amount of shift is specified by bloom_shift parameter.
  And the two bits wake up specified by *vector = *vector | bit1 | bit2; unless they had been set already.

Note if bloom shift is zero, only 1 bit is set.

Implementing this filter, I confirmed export symbol was successfully not filtered by previous dynamic loader provided by musl libc when it was called from others because the bits which suggest its existance is set.

After passing through bloom filter, computed hash will be addressed by GNU HASH.

Loader code is as follows.

static Sym *gnu_lookup(uint32_t h1, uint32_t *hashtab, struct dso *dso, const char *s)
{
    uint32_t nbuckets = hashtab[0];
    uint32_t *buckets = hashtab + 4 + hashtab[2]*(sizeof(size_t)/4);
    uint32_t i = buckets[h1 % nbuckets];

    if (!i) return 0;

    uint32_t *hashval = buckets + nbuckets + (i - hashtab[1]);

    for (h1 |= 1; ; i++) {
        uint32_t h2 = *hashval++;
        if ((h1 == (h2|1)) && (!dso->versym || dso->versym[i] >= 0)
            && !strcmp(s, dso->strings + dso->syms[i].st_name))
            return dso->syms+i;
        if (h2 & 1) break;
    }

    return 0;
}

It is not exactly like DT HASH.
Common thing is * both bucket contains symbol index on its bucket.
* When collision, you do not update any bucket but only chain. (this makes sense since the bucket was full)

But, how chains are filled up and traced are different.

DT HASH represents a chain as index of next symbol table terminated by zero. Bucket stores current symbol table index. Do not confuse.

GNU HASH instead store almost hash value itself on chain. uint32_t *hashval = buckets + nbuckets + (i - hashtab[1]);

This hash comparison is operated before every strcmp to call it less often. if ((h1 == (h2|1)) && (!dso->versym || dso->versym[i] >= 0)

When hash collision occurred, which means the loop iterates nexts, two values are incremented.

symbol table index i which are stored on first encountered bucket.
Array which stores chain (uint32_t*)hashval Do not confuse with
- hash value itself (uint32_t*)hashval
- bucket array &buckets[i]
  This comes after bucket array.

That says, when hash collision occurred for storing a symbol, you should take following two values and increments them. In fact, 1 & 2 are in a sense shared because a symbol table index corresponds to an index of chain array as there are as many numbers of elements as the index of symbols.

2 is understandable. I have stumbled on 1 and considered heavily what is meant by incrementing symbol table index. After all, I implemented generation code in something like below. And it seems to work.

static void check_gnu_hash_collision
(
 uint32_t* bucket, uint32_t* chain,
 uint32_t gh, uint32_t mod,
 uint32_t sym_index, uint32_t sym_offset) {

  uint32_t* p = bucket + mod;
  if (*p) {
    p = chain + *p - sym_offset;
    for (;*p;p++);
    *p = gh & -2;
  } else {
    *p = sym_index;
    *(chain + sym_index - sym_offset) = gh & -2;
     }
}

When hash collision occurred if (*p) {},

I only update(for (;*p;p++);) pointer to chain array p = chain + *p - sym_offset;.
If it comes an emptiness, fill the almost hash value *p = gh & -2;.

gh & -2 is rightest 1bit is used for checking emptiness of chain, not for validating hash value.

This seems to depend how symbols are stored on the hash table. If you try to store a symbol whose symbol table index is maximum of the symbol table, then obviously, it might not work when a value which shares same hash comes, as it will exceed maximum index of chain.

But, so far, it works as a symbol which has younger index comes forward on my linker.

https://github.com/Hiroshi123/bin_tools/blob/master/src/core/link/elf/dynamic.c

If you find a bug, tell me anything.

Notes

Do not read codes but patch binary.

DT_HASH and DT_GNU_HASH preparation by linker

Example of linker development reflecting loader implementation

DT_HASH

DT_GNU_HASH