By: Ali Bahrami | Principal Software Engineer
半年前研究ELF期间看了很多优质的资源，这一篇文章是我从oracle的博客上翻译过来的。这是我近期见过的讲解最细致、五脏皆全的关于.gnu.hash的文章。我将它翻译了过来，鉴于本人英语渣渣，词不达意处，诸君海涵。原文链接 0xmuhe师傅的钻石矿 。本文同步于我的博客
ELF对象格式在多个不同的操作系统中使用，它们虽同享一个通用的基本设计，但各自又做了自身的扩展。在ELF设计中，有一个很好的特点促进了扩展：它定义一个通用核心，同时储备了空间使得每个实现体可以定义自身的扩展。我们在ELF团体中尝试相互流通，作为新的想法和灵感的源泉，以便于避免重复造轮子，以及失去好奇。
近期，GNU linker开发者为他们的对象增加了一种新风格hash section，并且我已通过优良的详细说明中学习了他们。在完成这样的工作时，我仅仅想要把它写下来并分享。
该文章描述了GNU ELF hash sections的布局和解释。GNU hash section为ELF对象提供了新的hash section，较之原始的SYSV hash具有更好的性能。
这里收集的信息来源如下：
收集这些信息时，我没有看过GNU binutils源码。
如果你发现了一个错误，发送邮件（First.Last@Oracle.COM, First和Last替换成我的姓名）给我，我会修正它。
GNU哈希函数使用DJB(Daniel J Bernstein)哈希，该哈希算法由Bernstein教授在多年以前发表在comp.lang.c 世界性新闻组网络新闻组:
如果你在线查找该算法，你会找到该哈希表达式：
经常被编码成：
它们是等价的语句，将整型乘法运算替换成成本更低的移位及加法运算。实际中是否能够降低成本取决于使用的CPU。对旧机器来说这是个具有象征意义的差异，但是对当代机器来说整型乘法运算相当的快。
另一个算法的变化围绕着一个31位的返回值。
然而，GNU哈希使用完全的无符号32位整型数作为结果。
GNU binutils implementation利用uint_fast32_t类型来计算哈希。这一类型被定义成最快的可用整型——当前系统上机器至少能表示32位。它可以用更宽的类型实现，结果在返回前被显式的修剪成一个32位无符号值。
GNU hash sections在动态符号表中放置了一些额外的有序需求。这和标准的SVR4 hash sections形成对照，SVR4允许符号以任意顺序放置，这被ELF标准所允许。
对一个标准的SVR4 hash table来说，动态符号表中包含其所有符号。然而，动态符号表中的某些符号在哈希表中永远找不到：
哈希表节忽略这些符号对于正确性来说没有任何影响，且结果上来看还会减轻哈希表的拥塞，缩短哈希链，达成更好的哈希性能。
有了GNU哈希，动态符号表被分割成两部分。第一部分接受那些哈希表可以忽略的符号。GNU哈希不会对这一部分符号强加某种特定的顺序。
第二部分接受可从哈希表访问的符号。这些符号需要升序排列（hash % nbuckets），用上面描述的GNU hash函数。哈希桶(nbuckets)的个数在GNU hash section中记录，下面会有所描述。结果上来看，在单一哈希链中找到的符号在内存中是毗邻的，这也是为了更好的缓存性能。
一个GNU_HASH节由四个分离的部分组成，按顺序如下：
Header
注意到值0可以被解释成哈希节中不存在Bloom filter。然而，GNU linkers不会做此处理——GNU哈希节永远至少包含1个掩码。
Header，哈希桶以及哈希链永远都是32位字，而Bloom filter可能是32或64位，这取决于对象的类别。这意味着ELFCLASS32 GNU_HASH节仅包含32位字，因此他们节头的sh_entsize域被设置为4。ELFCLASS64 GNU_HASH节包含混合元素尺寸，因此sh_entsize被设置成0。
假设哈希节是对齐的、可正确访问ELFCLASS尺寸的字，在Bloom filter前面的(4)32位字直接确保了filter的掩码永远是对齐的，并且可以在内存中被正确的直接访问。
GNU hash sections包含一个Bloom filter。Bloom filters是概率性的，意味着可能会错检，但是不可能误检（简单来说，就是通过布隆过滤器的不一定在hash表中，但不通过的一定不在表中）。filter用来快速拒绝不在对象中的符号名，避免更多昂贵的哈希查找操作。通常地，只有一个对象在进程中拥有给定的符号。跳过对其他所有对象的哈希操作可以显著地增快符号查询。
filter由maskwords个字组成，每一个字都是32位（ELFCLASS32）或64位(ELFCLASS64)，这取决于对象的类别。在下面的讨论中，C将被用来表示一个掩码的尺寸，单位是位(bits)。所有掩码共同组成一个逻辑的(C * maskwords)的bitmask。
GNU hash使用一个k=2的Bloom filter，这意味着会有两个独立的哈希函数为每个符号所使用。Bloom filter参考包含下面的陈述：
设计k个不同的独立哈希函数的需求，当k较大时应被禁止。对一个良好的具有宽输出的哈希函数来说，哈希的不同bit-fields之间的关联应该很小，所以这类哈希可以用来生成多重“不同的”哈希函数，其通过对输出进行切片操作做成多重位域。
GNU哈希使用的哈希函数具有这一特性。事实上，正是利用上面描述的单一哈希函数生成了两个Bloom filter所需要的哈希函数。
如上面讨论，链接编辑器决定使用多少个掩码（maskwords），以及第一个哈希结果右移产生的第二个哈希(shift2)的量。掩码用得越多，hash section就越大、漏检率越低。在私人email中我被告知GNU linker首先从哈希表（dynsymcount-symndx）符号数以2为底的对数得到shift2，对ELFCLASS32最小值为5，对ELFCLASS64最小值为6。这些值显式的记录在hash section中，以便于让链接编辑器可以在未来灵活的修改它们，应更好的去实现启发式。
Bloom filter掩码对两个哈希值的每一个都设置一位。基于Bloom filter参考，该字包含每一位，设置位的计算方法应该如下：
构筑filter时构造位：
并且在随后的测试filter：
GNU hash以一种有意义的方式偏离了上述的定义。并非分别计算N1和N2，而是使用单一掩码计算的和前者中N1一致的值。这是个清醒的决定，GNU hash开发组旨在优化缓存表现：
比起使用两个不同的Ns，这使得Bloom filter的2个哈希函数依赖性更强，但在我们的测算中对于那些该拒绝的查询仍然具有非常好的拒绝率，且缓存更加友好。在查找中我们尽可能的触碰最少的缓存行，这一点尤为重要。
因此，在GNU hash中，单一掩码实际上计算如此：
Bloom filter掩码N的两个位设置如下：
链接编辑器设置这些位的方法：
运行时链接器使用的测试如下：
通常来讲，一个Bloom filter可以使用一个任意的字数构成。然而，如同前面提到的，GNU hash的maskwords必须是2的幂次数。这一需求允许下面的模操作：
可以写成简单的掩码操作替代：
注意到(maskwords-1)可以预计算一次
且被每个哈希使用：
Bloom filters有一对有趣的特殊情况：
跟随Bloom filter的是哈希桶(nbuckets个)，以32位为单位。数组中第N位置处的值是到动态符号表最低的索引：
既然动态符号表由相同的键排序（hash % nbuckets），那么dynsym[buckets[N]]就是哈希链中的第一个符号，哈希链将包含所期望的符号如果存在的话。
一个桶元素会包含索引0如果在哈希表中对于给定的值N没有任何符号。dynsym的索引0是一个保留值，该索引在一个合法的符号上不会出现，也因此没有歧义。
GNU hash section的最后一部分包含(dynsymcount-symndx)个32位字，每个条目都是动态符号表第二部分中的每个符号。每个字的前31位包含和符号表值一致的31位值。最后一位用做阻塞位。当符号是给定哈希链中最后一个或者两个桶的边界时其置1。
下列展示了一个符号怎样在使用了GNU hash section的对象中查找的过程。我们假设包含需要信息的内存记录是存在的。
为了简化因素，我们省略控制不同ELF classes的细节。上面的情景中，Word是32位无符号数，BloomWord是32或64位数，取决于ELFCLASS，Sym相应就是Elf32_Sym和Elf64_Sym。
把包含上述信息的变量给一个对象，下列的伪代码返回一个指针，如果对象中期望的符号存在，则指向它，否则指向NULL。
2010年8月26日
2011年9月19日
第二行应该是h2 = h1 >> os->os_shift2;。
在翻阅这篇旧文章时，我发现了一些''字符被转义成了'\ '。我仅能推测这是当Oracle转换我们Sun的博文时发生的。我修复了原本的字符。我也借此机会更新了我的邮箱地址成当前的Oracle.COM格式。
2013年8月15日
运行时连接器使用的测试如下：
N1应该是简单的N:
谢谢你善意的文字。
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
