A dynamic loader is given several libraries and a name, and must find the definition in time to patch a call site. It cannot scan, because scanning is linear and a process resolves thousands of names. It needs a lookup structure, and ELF has had two answers to this question for thirty years — and the one your compiler emits today is not the one most textbooks describe.
$ clang -O1 -o prog tiny.c $ readelf -SW prog | grep -E '\.hash' [ 3] .gnu.hash GNU_HASH ... $ readelf -SW prog | grep -cE ' \.hash ' 0 <-- .hash is ABSENT. Not deprecated, absent.
So any course text that says “the hash table” and then walks you through .hash is describing a section your ld will not produce unless you ask. The three build styles:
$ for s in sysv gnu both; do
clang -O1 -Wl,--hash-style=$s -o hs_$s tiny.c
printf "%-5s %s\n" $s "$(readelf -SW hs_$s | grep -oE '\.gnu\.hash|\.hash' | sort -u | tr '\n' ' ')"
done
sysv .hash
gnu .gnu.hash
both .gnu.hash .hash
Both tables do the same job and both use the same hash function. They differ in how much they store and therefore in what a lookup costs.
THE HASH (identical in both, and reused a third time
in .gnu.version_d -- see the Versioned Symbols concept)
h = 0
for each byte c of the name:
h = (h << 4) + c
g = h & 0xf0000000
if g: h ^= g >> 24
h &= ~g
return h
.hash (SysV) .gnu.hash
------------ ----------
nbucket, nchain nbuckets, symoffset,
bucket[] bloom_size, bloom_shift
chain[] bloom[]
bucket[]
chain[]
The same function in three unrelated tables — .hash, .gnu.hash, and the version-definition name hash — is one of those accidents that turns out to be load-bearing. It means a loader can compare a 32-bit number instead of a string when matching a version requirement, and it means the two hash tables agree about which symbols collide, so a name that lands in the same bucket in one lands in the same bucket in the other.
The structural difference is the interesting part. .hash stores an entry for every exported symbol, including the ones nobody will ever look up. .gnu.hash stores nothing per symbol except one chain word, plus a Bloom filter in front to reject most misses without touching the chain at all. That is the entire optimisation: a lookup that misses should not have to read a symbol table entry to find out it missed.
Decode .gnu.hash from a real binary and check the structure:
$ python3 symtables.py /bin/ls
-- .gnu.hash --
nbuckets=3 symoffset=268 bloom_size=1 bloom_shift=6
bloom words: 0x3819400128c10084
buckets : [268, 272, 275]
5 invariants hold, 0 broken
MEASURED: 268 of 268 adjacent bucket pairs are out of index order
That last line is Finding 20, and it is the surprise in this concept. With three buckets and symoffset = 268 the heads look sorted, which is what makes the false intuition so easy to form. Now try a real library:
$ python3 symtables.py /lib/x86_64-linux-gnu/libc.so.6 | grep -A6 'gnu.hash --'
nbuckets=1017 symoffset=262
buckets : [2620, 977, 267, 1613, 568, 3084, ...]
Bucket 0’s head is 2620. Bucket 1’s head is 977. The heads are wildly out of index order, and this is normal, not corruption.
The reason is worth stating precisely, because it is the thing the intuition gets wrong. Each bucket is a contiguous run of adjacent .dynsym indices — that part is true, and it is why the walk is just i, i+1, i+2, ... until a chain word with its low bit set. But the runs are laid out one after another in bucket order, and bucket order is hash order, not index order. The two orderings coincide only when the number of buckets is small enough that the sortedness is an accident.
Now the .hash verification, which is the one that can be checked completely. Rebuild every symbol’s bucket from the hash and walk the chains:
$ python3 symtables.py /lib/x86_64-linux-gnu/libc.so.6 | grep -A3 'hash (SysV)'
nbucket=1017 nchain=3189
3188 symbols consistent, 0 inconsistent
3188 of 3188. Every exported symbol in glibc lands in exactly the bucket elf_hash(name) % 1017 predicts, with @version stripped from the name first. That last part is the detail that makes versioning work at all, and it is the next concept.
Why the hash is computed over the base name, stripped of its version. glibc exports the same function under two version names, and the loader has to find the right one:
$ readelf --dyn-syms -W /lib/x86_64-linux-gnu/libc.so.6 | grep -E ' (abort|bcopy)@' 132: ... FUNC GLOBAL DEFAULT UND abort@GLIBC_2.2.5 (5) 185: ... FUNC GLOBAL DEFAULT UND bcopy@GLIBC_2.2.5 (5)
In a library that defines versioned symbols, one base name has several versioned entries. The hash is over printf, not printf@@GLIBC_2.2.5 — and that is not a simplification, it is the design. All versions of one name share a single chain. The lookup walks the chain comparing the base name, and only after it has a match does it check the version index.
The alternative would be one chain per versioned name, which would mean the loader had to know the version before it could hash anything — and the version is a property of the reference, not of the definition. A reference to printf@@GLIBC_2.2.5 and a reference to printf@@GLIBC_2.38 must both be able to find the same chain and then differ on the version check. Stripping first is what makes that possible with one structure.
The cost is that the chains are longer than they need to be, and the loader does a version comparison for every candidate it walks past. For a name with a dozen historical versions that is a dozen comparisons on a hit. Correct and slightly wasteful, chosen once, twenty-five years ago, and still the right trade — because the alternative is not slightly wasteful, it is structurally impossible.
$ cd courses/sym/assets/samples $ ./build_samples.sh 2>&1 | sed -n '/Finding 18/,/Findings 11/p' $ python3 symtables.py /bin/ls | sed -n '/gnu.hash --/,$p' $ python3 symtables.py /lib/x86_64-linux-gnu/libc.so.6 | grep -A3 'SysV'
Then check the invariants yourself, and try to break Finding 20:
1. symtables.py checks five structural invariants of
.gnu.hash. Name them, and say which one is the reason
a lookup is O(1) rather than O(chain).
2. For each of these, is the bloom filter useful?
a binary with 4 exported symbols
a library with 3000
a binary that looks up 1 name and exits
3. The out-of-order heads: find the SMALLEST library on
this machine where buckets[0] > buckets[1]. Why is
there a threshold below which you never notice?
4. symoffset=268 in /bin/ls and 262 in libc. What are
entries 0..symoffset-1, and why must they be excluded
from the hash?
Question 4 has the answer that ties this concept to the previous module: the entries below symoffset are the ones with no business being found by name — undefined symbols, mostly, plus the bookkeeping entries. Undefined symbols are the demands the static linker failed to satisfy, and the loader is their last chance. They are deliberately outside the lookup table because a lookup that could only return an undefined symbol would be a lookup that cannot fail, and the loader needs it to be able to fail.
This opens the runtime module, and the reason the module exists is the gap this concept sits in. The Algorithm, Measured gave a linker that sees every file at once and can therefore afford a linear pass. The loader sees a set of libraries that did not exist at link time, so it needs an index, and that index is what this concept decoded. The whole module is one question asked twice: which definition of this name? — once by ld against every file, once by ld.so against a hash table of whatever got mapped.
Within the module the chain is direct. This concept builds the index; The PLT and the GOT is how a call site reaches that index, and reading those six instructions is much easier once you know what is on the other end of the jump. Lazy, Eager, and the Flag That Does Nothing is about when the index is consulted, and the experiment in that concept only works because this one established that the index is a data structure rather than a scan. Who Owns the Storage is the case where the loader’s answer has to disagree with the linker’s.
The versioning connection is the strongest in the course and it is a direct consequence of the base-name rule. Because the hash strips @version, one chain holds every version of a name, and the second half of a versioned lookup is a comparison against .gnu.version rather than a second table walk. Versioned Symbols is where that comparison happens, and it reuses the same hash function for a third purpose — which is why Finding 12 there is really a continuation of this concept rather than a separate fact.
One connection outside the course, because it is a design lesson rather than a mechanism. This is the only place in a program where a data structure is chosen for a workload that is 99% misses. Symbol lookup is overwhelmingly a miss — most names in a table are never looked up, and most lookups are for names that resolve immediately. The SysV design optimises for build time (one word per symbol, no build cost). The GNU design optimises for the miss. Both are shipped, because “which is better” depends on how many libraries are loaded, and that changed from one to ten over the lifetime of the format. That is a recurring pattern: an ABI outlives the workload it was designed for, so it keeps both answers and lets a flag choose.