Symbol Versioning and the Two Hash Tables Behind Every Lookup

A symbol name in ELF is not a single string. The linker and the dynamic linker both operate on a triple: the name, the object that defines it, and a version. The version component is invisible in source code and usually invisible in tool output, yet it is the mechanism that lets a library fix a bug in a widely used function without breaking every program compiled against the old behaviour, and it is the reason a binary built on one system can refuse to start on another with a message naming a version rather than a function.

The versioning machinery is built on top of the hash tables that make symbol lookup fast. Both pieces share a property that makes them hard to reason about from the outside: they are optional in the specification, redundant in practice, and selected by flags in the dynamic section. A reader that knows only one of the two hash formats will fail on binaries produced by the other toolchain.

What a version actually is

A versioned symbol has a name, an index into the version definition table, and a hidden or default flag. When a library exports memcpy with a version tag such as GLIBC_2.14, the symbol table entry’s name remains memcpy, and a parallel array indexed by symbol number, held in the .gnu.version section, gives the version index for each symbol. A third structure, .gnu.version_r for required versions and .gnu.version_d for defined ones, holds the version names and their dependencies.

At lookup time the dynamic linker computes the effective name by appending @ and the version string, unless the reference is to the default version, in which case the name is used alone. The default version is marked by a flag bit in the version entry, and it is the one a newly compiled program gets when it references the symbol without specifying a version. The non-default versions remain available for programs linked against older behaviour, which is how a single library can present two incompatible implementations under one name.

The source-level syntax makes this explicit. Writing memcpy@GLIBC_2.2.5 in an assembly reference, or using an .symver directive, binds to a specific version. Writing plain memcpy binds to the default. A program linked against the old version continues to receive the old implementation after the library introduces a new default, and that is the entire purpose: binary compatibility is preserved without maintaining two function names.

The failure mode is equally specific. If a binary requires GLIBC_2.28 and the system provides GLIBC_2.17, the loader refuses to start the process and prints a message naming the version, not the function. The check happens before any user code runs, because the loader verifies every required version against the version definitions of the objects it has loaded. A missing version is a startup failure with no partial execution, which is preferable to a missing symbol discovered mid-run but makes the error message opaque to anyone who does not know the mechanism.

The version definition section

.gnu.version_d is a sequence of Elf64_Verdef structures, each with a version number, a count of auxiliary entries, a hash of the version name, flags, and offsets to the next definition and to the auxiliary array. The auxiliary entries are Elf64_Verdaux records holding a name offset into the dynamic string table, and they can chain: the first auxiliary entry is the version’s own name, and subsequent ones name the versions this one inherits from.

The VER_FLG_BASE flag marks the definition that corresponds to the object’s own soname, which is why a library’s base version carries its filename rather than a number. The VER_FLG_WEAK flag marks a version that the object defines but does not require, used for compatibility with older systems that lack the symbol entirely. The version index zero is reserved and means “local”, applied to symbols that are not exported at all.

A hash of the version name is stored in each definition so that the loader can compare hashes before comparing strings. The hash is the standard ELF symbol hash, a simple shift-and-add over the name’s bytes, and it is the same function used by the SysV hash table. A collision is resolved by string comparison, so the hash is a filter rather than an identity.

Two hash tables with different economics

.hash, the SysV table, begins with nbucket and nchain counts, followed by an array of nbucket 32-bit bucket entries and an array of nchain 32-bit chain entries. A lookup hashes the name, takes the remainder modulo nbucket, and follows the chain from that bucket: each chain entry is the index of a symbol, and the value at that index in the chain array gives the next index, with zero terminating the walk. The number of chain entries equals the number of symbols, so the table size grows linearly with the symbol count and the chain array is one word per symbol.

.gnu.hash restructures this for the common case of a name that is absent or found quickly. It begins with nbuckets, symoffset, bloom_size, and bloom_shift, followed by a Bloom filter of bloom_size words, then the bucket array, then an array of hash values. A lookup hashes the name, tests two bits in the Bloom filter derived from the hash and bloom_shift, and rejects the lookup immediately if either bit is clear. Otherwise it reads the bucket, which gives the index of the first symbol in that bucket’s run, and walks forward comparing the stored hash values with the computed one before comparing the names themselves.

The Bloom filter is the key difference. A program importing many symbols from a library with a large export set spends most of its lookups on names that are absent, because the loader searches every object in dependency order. Rejecting an absent name with two bit tests avoids touching the chain entirely. When the filter does not reject, the bucket gives a starting point relative to symoffset, and the walk continues over consecutive symbol indices until the lowest bit of a stored hash is set, which marks the end of the run. That encoding is why .gnu.hash cannot be repaired by falling back to a linear scan when it is malformed: the run boundaries are part of the data.

/* SysV lookup: hash, bucket, then follow chain indices to the sentinel. */
#include <elf.h>
#include <stdint.h>
#include <string.h>

static uint32_t elf_hash(const char *s) {
    uint32_t h = 0, g;
    while (*s) {
        h = (h << 4) + (unsigned char)*s++;
        g = h & 0xf0000000u;
        if (g) h ^= g >> 24;
        h &= ~g;
    }
    return h;
}

uint32_t sysv_lookup(const uint32_t *hash, const char *name,
                     const char *strtab, const Elf64_Sym *sym) {
    uint32_t nbucket = hash[0];
    const uint32_t *bucket = hash + 2;
    const uint32_t *chain  = bucket + nbucket;
    if (nbucket == 0) return 0;                  /* malformed table */
    for (uint32_t i = bucket[elf_hash(name) % nbucket]; i != 0; i = chain[i])
        if (strcmp(strtab + sym[i].st_name, name) == 0) return i;
    return 0;
}

The elf_hash function’s shift-and-xor structure is deliberate: it was designed to spread short, similar identifiers across buckets on the machines of the era, and it is weak by modern standards. The GNU hash uses a different function, a multiply-based one derived from a known string-hashing family, and the two produce different bucket assignments for the same name. A reader must therefore select the hash function by which table it is reading, not by the platform.

Which table is present, and what that implies

A binary may carry .hash, .gnu.hash, or both. Both being present is the compatible choice: old loaders that know only SysV can still use the file, and newer loaders prefer the GNU table because it is smaller and faster for misses. The dynamic section advertises the tables through DT_HASH and DT_GNU_HASH entries, and a reader should check those tags rather than assuming a section name.

The absence of DT_HASH in a binary built for a modern glibc is normal, and a tool that requires the SysV table will report the file as having no hash. The absence of DT_GNU_HASH indicates an older binary or a deliberate compatibility build. Neither absence is an error, and code that treats one as corruption is enforcing a policy the format does not. Like the relocation tables that sit beside them in the dynamic section, these are reached through dynamic entries rather than through section headers, so they survive a strip that removes the section table entirely, as described in Section Headers, String Tables, and the Bookkeeping a Linker Needs.

The two tables also differ in what they can express about symbol ordering. .gnu.hash requires that the symbols it indexes be sorted by bucket, with each bucket’s run contiguous in the symbol table. That is why symoffset exists: it is the index of the first symbol the table describes, and the parallel array of stored hash values is indexed by the symbol index minus symoffset rather than by the symbol index itself. A reader that indexes that array directly, or that assumes it is as long as the symbol table, reads the wrong hashes for every symbol below the offset.

Interposition, versions, and search order

The version rules interact with the object search order in a way that produces the most confusing failures in dynamic linking. When the loader resolves a name, it walks the loaded objects in breadth-first order from the executable through its dependencies, and it accepts the first definition that matches both name and version. A definition with the right name but the wrong version is skipped, and the search continues, which means a symbol can be found in an object further down the dependency list than the one that appeared to define it.

This is why LD_PRELOAD interposition works at all: a preloaded object appears before the library in the search order, so its definition wins. The mechanism that consumes this lookup result on a per-call basis is the PLT slot patching described in The PLT and GOT Protocol That Defers Symbol Resolution. It is also why preloading a library that defines a symbol without a version can fail to interpose a call that the executable made against a versioned reference, because the preloaded definition carries no matching version. Interposing a versioned symbol requires either defining the same version or using a mechanism that ignores versioning.

The RTLD_DEEPBIND flag changes the rule for a single dlopen call, causing the loaded object’s own definitions to be preferred over those of objects already loaded. It exists because a plugin that bundles a library can otherwise be broken by the process’s copy of a different version, and it is dangerous for the same reason: the plugin’s symbols no longer participate in the global order, so two copies of a library’s state can coexist in one process.

Where the machinery leaks into ordinary debugging

Two symptoms recur often enough to be worth naming. A binary that fails at startup with a message about a version not being found is not missing a symbol; it is missing a version definition, and the fix is a newer library or a rebuild against an older one. A binary that fails with a message about an undefined symbol, naming a version, has found a definition with the right name and the wrong version, which usually indicates two libraries exporting the same name with different version sets.

The versioning tables are also the reason a stripped binary can still reveal part of its ABI requirements. Even with the section table removed, .gnu.version_r is reachable through DT_VERNEED, and the version names it lists are a precise record of which library versions the binary was built against. That is a more reliable compatibility signal than the symbol list, because the symbol list is a superset: it includes symbols that would be resolved by any version of the library that has ever exported them.