GNU Hash ELF Sections
| GNU Hash ELF Sections | |
Ali Bahrami — Tuesday October 21, 2008
The ELF object format is used by several different operating systems, all sharing a common basic design, but each sporting their own extensions. One of the nice aspects of ELF's design is that it facilitates this, defining a common core, as well as reserving space for each implementation to define its own additions. Those of us in the ELF community try to stay current with each other, as a source of new ideas and inspiration, in order to avoid reinventing the wheel, and out of curiosity.
Recently, the GNU linker developers added a new style of hash section to their objects, and I've been learning about them in fine detail. Having done the work, it only makes sense to write it down and share it.
This posting describes the layout and interpretation of GNU ELF hash sections. The GNU hash section provides a new hash section for ELF objects, with better performance than the original SYSV hash.
The information here was gathered from the following sources:
I did not look at the GNU binutils source code to gather this information.
If you spot an error, send me email (First.Last@Oracle.COM, where First and Last are replaced with my name) and I'll fix it.
uint32_t
dl_new_hash (const char *s)
{
uint32_t h = 5381;
for (unsigned char c = *s; c != '\0'; c = *++s)
h = h * 33 + c;
return h;
}
is frequently coded ash = h * 33 + c
These are equivalent statements, replacing integer multiplication with a presumably cheaper shift and add operation. Whether this is actually cheaper depends on the CPU used. There used to be a significant difference with older machines, but integer multiplication on modern machines is very fast.h = ((h << 5) + h) + c
Another variation of this algorithm clips the returned value to 31-bits:
However, GNU hash uses the full unsigned 32-bit result.return h & 0x7fffffff;
The GNU binutils implementation utilizes the uint_fast32_t type for computing the hash. This type is defined to be the fastest available integer machine type capable of representing at least 32-bits on the current system. As it might be implemented using a wider type, the result is explicitly clipped to a 32-bit unsigned value before being returned.
static uint_fast32_t
dl_new_hash (const char *s)
{
uint_fast32_t h = 5381;
for (unsigned char c = *s; c != '\0'; c = *++s)
h = h * 33 + c;
return h & 0xffffffff;
}
A standard SVR4 hash table includes all of the symbols in the dynamic symbol table. However, some of these symbols will never be looked up via the hash table:
With GNU hash, the dynamic symbol table is divided into two parts. The first part receives the symbols that can be omitted from the hash table. GNU hash does not impose any specific order for the symbols in this part of the dynamic symbol table.
The second half of the dynamic symbol table receives the symbols that are accessible from the hash table. These symbols are required to be sorted by increasing (hash % nbuckets) value, using the GNU hash function described above. The number of hash buckets (nbuckets) is recorded in the GNU hash section, described below. As a result, symbols which will be found in a single hash chain are adjacent in memory, leading to better cache performance.
The header, hash buckets, and hash chains are always 32-bit words, while the Bloom filter words can be 32 or 64-bit depending on the class of object. This means that ELFCLASS32 GNU_HASH sections consist of only 32-bit words, and therefore have their section header sh_entsize field set to 4. ELFCLASS64 GNU_HASH sections have mixed element size, and therefore set sh_entsize to 0.
- Header
- An array of (4) 32-bit words providing section parameters:
- nbuckets
- The number of hash buckets
- symndx
- The dynamic symbol table has dynsymcount symbols. symndx is the index of the first symbol in the dynamic symbol table that is to be accessible via the hash table. This implies that there are (dynsymcount - symndx) symbols accessible via the hash table.
- maskwords
- The number of ELFCLASS sized words in the Bloom filter portion of the hash table section. This value must be non-zero, and must be a power of 2 as explained below.
Note that a value of 0 could be interpreted to mean that no Bloom filter is present in the hash section. However, the GNU linkers do not do this — the GNU hash section always includes at least 1 mask word.
- shift2
- A shift count used by the Bloom filter.
- Bloom Filter
- GNU_HASH sections contain a Bloom filter. This filter is used to rapidly reject attempts to look up symbols that do not exist in the object. The Bloom filter words are 32-bit for ELFCLASS32 objects, and 64-bit for ELFCLASS64.
- Hash Buckets
- An array of nbuckets 32-bit hash buckets
- Hash Values
- An array of (dynsymcount - symndx) 32-bit hash chain values, one per symbol from the second part of the dynamic symbol table.
Assuming that the hash section is aligned properly for accessing ELFCLASS sized words, the (4) 32-bit words directly before the Bloom filter ensure that the filter mask words are always aligned properly and can be accessed directly in memory.
The filter consists of maskwords words, each of which is 32-bits (ELFCLASS32) or 64-bits (ELFCLASS64) depending on the class of object. In the following discussion, C will be used to stand for the size of one mask word in bits. Collectively, the mask words make up a logical bitmask of (C * maskwords) bits.
GNU hash uses a k=2 Bloom filter, which means that two independent hash functions are used for each symbol. The Bloom filter reference contains the following statement:
The requirement of designing k different independent hash functions can be prohibitive for large k. For a good hash function with a wide output, there should be little if any correlation between different bit-fields of such a hash, so this type of hash can be used to generate multiple "different" hash functions by slicing its output into multiple bit fields.The hash function used by the GNU hash has this property. This fact is leveraged to produce both hash functions required by the Bloom filter from the single hash function described above:
As discussed above, the link editor determines how many mask words to use (maskwords) and the amount by which the first hash result is right shifted to produce the second (shift2). The more mask words used, the larger the hash section, but the lower the rate of false positives. I was told in private email that the GNU linker primarily derives shift2 from the base 2 log of the number of symbols entered into the hash table (dynsymcount - symndx), with a minimum value of 5 for ELFCLASS32, and 6 for ELFCLASS64. These values are explicitly recorded in the hash section in order to give the link editor the flexibility to change them in the future should better heuristics emerge.H1 = dl_new_hash(name); H2 = H1 >> shift2;
The Bloom filter mask sets one bit for each of the two hash values. Based on the Bloom filter reference, the word containing each bit, and the bit to set would be calculated as:
To populate the bits when building the filter:N1 = ((H1 / C) % maskwords); N2 = ((H2 / C) % maskwords); B1 = H1 % C; B2 = H2 % C;
and to later test the filter:bloom[N1] |= (1 << B1); bloom[N2] |= (1 << B2);
The GNU hash deviates from the above in a significant way. Rather than calculate N1 and N2 separately, a single mask word is used, corresponding to N1 above. This is a conscious decision by the GNU hash developers to optimize cache behavior:(bloom[N1] & (1 << B1)) && (bloom[N2] & (1 << B2))
This makes the 2 hash functions for the Bloom filter more dependent than when two different Ns were used, but in our measurements still has very good ratio of rejecting lookups that should be rejected, and is much more cache friendly. It is very important that we touch as few cache lines during lookup as possible.
Therefore, in the GNU hash, the single mask word is actually calculated as:
The two bits set in the Bloom filter mask word N are:N = ((H1 / C) % maskwords);
The link-editor sets these bits asBITMASK = (1 << (H1 % C)) | (1 << (H2 % C));
And the test used by the runtime linker is:bloom[N] |= BITMASK;
(bloom[N] & BITMASK) == BITMASK;
to instead be written as a simple mask operation:N = ((H1 / C) % maskwords);
Note that (maskwords - 1) can be precomputed onceN = ((H1 / C) & (maskwords - 1));
and then used for every hash:MASKWORDS_BITMASK = maskwords - 1;
N = ((H1 / C) & MASKWORDS_BITMASK);
Since the dynamic symbol table is sorted by the same key (hash % nbuckets), dynsym[buckets[N]] is the first symbol in the hash chain that will contain the desired symbol if it exists.(dl_new_hash(symname) % nbuckets) == N
A bucket element will contain the index 0 if there is no symbol in the hash table for the given value of N. As index 0 of the dynsym is a reserved value, this index cannot occur for a valid symbol, and is therefore non-ambiguous.
lsb = (N == dynsymcount - 1) || ((dl_new_hash (name[N]) % nbuckets) != (dl_new_hash (name[N + 1]) % nbuckets)) hashval = (dl_new_hash(name) & ~1) | lsb;
typedef struct {
const char *os_dynstr; /* Dynamic string table */
Sym *os_dynsym; /* Dynamic symbol table */
Word os_nbuckets; /* # hash buckets */
Word os_symndx; /* Index of 1st dynsym in hash */
Word os_maskwords_bm; /* # Bloom filter words, minus 1 */
Word os_shift2; /* Bloom filter hash shift */
const BloomWord *os_bloom; /* Bloom filter words */
const Word *os_buckets; /* Hash buckets */
const Word *os_hashval; /* Hash value array */
} obj_state_t;
Given a variable containing the above information for an object, the following pseudo code returns a pointer to the desired symbol if it exists in the object, and NULL otherwise.
Sym *
symhash(obj_state_t *os, const char *symname)
{
Word c;
Word h1, h2;
Word n;
Word bitmask;
const Sym *sym;
Word *hashval;
/*
* Hash the name, generate the "second" hash
* from it for the Bloom filter.
*/
h1 = dl_new_hash(symname);
h2 = h1 >> os->os_shift2;
/* Test against the Bloom filter */
c = sizeof (BloomWord) * 8;
n = (h1 / c) & os->os_maskwords_bm;
bitmask = (1 << (h1 % c)) | (1 << (h2 % c));
if ((os->os_bloom[n] & bitmask) != bitmask)
return (NULL);
/* Locate the hash chain, and corresponding hash value element */
n = os->os_buckets[h1 % os->os_nbuckets];
if (n == 0) /* Empty hash chain, symbol not present */
return (NULL);
sym = &os->os_dynsym[n];
hashval = &os->os_hashval[n - os->os_symndx];
/*
* Walk the chain until the symbol is found or
* the chain is exhausted.
*/
for (h1 &= ~1; 1; sym++) {
h2 = *hashval++;
/*
* Compare the strings to verify match. Note that
* a given hash chain can contain different hash
* values. We'd get the right result by comparing every
* string, but comparing the hash values first lets us
* screen obvious mismatches at very low cost and avoid
* the relatively expensive string compare.
*
* We are intentionally glossing over some things here:
*
* - We could test sym->st_name for 0, which indicates
* a NULL string, and avoid a strcmp() in that case.
*
* - The real runtime linker must also take symbol
* versioning into account. This is an orthogonal
* issue to hashing, and is left out of this
* example for simplicity.
*
* A real implementation might test (h1 == (h2 & ~1), and then
* call a (possibly inline) function to validate the rest.
*/
if ((h1 == (h2 & ~1)) &&
!strcmp(symname, os->os_dynstr + sym->st_name))
return (sym);
/* Done if at end of chain */
if (h2 & 1)
break;
}
/* This object does not have the desired symbol */
return (NULL);
}
h1 = dl_new_hash(symname);
h2 = h2 >> os->os_shift2;
h2 = h1 >> os->os_shift2;
And the test used by the runtime linker is:
(bloom[N1] & BITMASK) == BITMASK;
The N1 should have been simply N:
(bloom[N] & BITMASK) == BITMASK;
Thank you for writing, and for the kind words.
Interesting stuff. It's really good to see more toolchain blogs knocking about these days. These things are a mystery to many.
Check out:
http://www.airs.com/blog/
http://nickclifton.livejournal.com/
| [12] Cost Of ELF Symbol Hashing | [14] Problems With V1 Mapfiles |