操作系统：CentOS Linux release 7.7.1908
内核版本：3.10.0-1062.1.1.el7.x86_64
运行平台：x86_64
参考文献：http://refspecs.linuxfoundation.org/
本文根据/usr/include/elf.h文件和程序编译的详细过程文中所述的tanglinux.c源码来分析可执行文件中与符号（symbol）相关section的构成。
本文中的可执行程序tanglinux都是通过执行$ gcc -m32 -Wl,--hash-style=both tanglinux.c -o tanglinux命令所生成。
变量和函数在链接层面它们被统称为符号，它们的名称也就是符号名。一个函数原型为int func(void) 的函数，func就是它的名称，但它的符号名可能为func（C程序），也可能为_Z4funcv（C++程序），因为C++语言为支持函数重载等特性，将编译后的函数名进行了修饰，以区分不同的函数版本。
在ELF文件中，与符号有关的section大概有四大类，它们是SHT_SYMTAB（符号表）、SHT_DYNSYM（动态链接符号表）、SHT_HASH（或SHT_GNU_HASH，动态链接符号散列表）、SHT_GNU_versym（SHT_GNU_verdef和SHT_GNU_verneed，动态链接符号版本控制信息）。在可执行文件tanglinux中，它们的section header信息如下所示：
$ readelf -S tanglinux
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 4] .hash HASH 080481ac 0001ac 000024 04 A 6 0 4
[ 5] .gnu.hash GNU_HASH 080481d0 0001d0 000020 04 A 6 0 4
[ 6] .dynsym DYNSYM 080481f0 0001f0 000040 10 A 7 1 4
[ 8] .gnu.version VERSYM 08048276 000276 000008 02 A 6 0 2
[ 9] .gnu.version_r VERNEED 08048280 000280 000020 00 A 7 1 4
[29] .symtab SYMTAB 00000000 001044 000420 10 30 48 4一、符号表和动态链接符号表
32位程序的符号表采用以下所示的数据结构来定义：
typedef struct
{
Elf32_Word st_name; /* Symbol name (string tbl index) */
Elf32_Addr st_value; /* Symbol value */
Elf32_Word st_size; /* Symbol size */
unsigned char st_info; /* Symbol type and binding */
unsigned char st_other; /* Symbol visibility */
Elf32_Section st_shndx; /* Section index */
} Elf32_Sym;符号表所有项的大小相同，都为16个字节，所以.dynsym section和.symtab section也被叫做符号表，并且每个表项都有一个索引值，而符号表的第一个表项必须是索引值STN_UNDEF（即0）的无效项。索引值STN_UNDEF在符号的散列算法中可以被当做链尾，即表示它不引用有效的符号。
1、st_name表示符号名，这里的值是它在相应字符串表中的索引号。如.dynsym section中所有表项的符号名要从.dynstr section中获取，而.symtab是从.strtab中获取。而.dynstr和.strtab都是字符串表。
2、st_value表示符号的值。一般为虚拟地址。
3、st_size表示符号的大小。比如对于变量，它的值就是变量的数据类型（如int则它的值可能为4个字节）的大小。如果为0则表示该符号无需大小或大小未知。
4、st_info表示符号的类型和绑定特征。成员st_info的大小为一个字节，低4位表示符号类型，高4位表示符号的绑定特征。在/usr/include/elf.h文件中，有定义以下三个宏来获取类型或绑定特征的值或将它俩合成st_info的值：
#define ELF32_ST_BIND(val) (((unsigned char) (val)) >> 4)
#define ELF32_ST_TYPE(val) ((val) & 0xf)
#define ELF32_ST_INFO(bind, type) (((bind) << 4) + ((type) & 0xf))（1）、绑定特征的可能取值如下所示：
#define STB_LOCAL 0 /* Local symbol */
#define STB_GLOBAL 1 /* Global symbol */
#define STB_WEAK 2 /* Weak symbol */
#define STB_NUM 3 /* Number of defined types. */
#define STB_LOOS 10 /* Start of OS-specific */
#define STB_GNU_UNIQUE 10 /* Unique symbol. */
#define STB_HIOS 12 /* End of OS-specific */
#define STB_LOPROC 13 /* Start of processor-specific */
#define STB_HIPROC 15 /* End of processor-specific */STB_LOCAL表示局部符号，STB_GLOBAL表示全局符号，STB_WEAK表示弱符号。弱符号是全局符号，但它们的优先级相对全局符号低。
局部符号，顾名思义，它只被局限在定义它的目标文件之内，多个目标文件定义的同名局部符号互不影响，全局符号则与之相反。
相对弱符号，其它的就是强符号。两个同名的强符号会导致重复定义的错误，但如果同名的是一个强符号和多个弱符号，则不报错，链接器会选择其中的强符号。
（2）、符号类型的可能取值如下所示：
#define STT_NOTYPE 0 /* Symbol type is unspecified */
#define STT_OBJECT 1 /* Symbol is a data object */
#define STT_FUNC 2 /* Symbol is a code object */
#define STT_SECTION 3 /* Symbol associated with a section */
#define STT_FILE 4 /* Symbol's name is file name */
#define STT_COMMON 5 /* Symbol is a common data object */
#define STT_TLS 6 /* Symbol is thread-local data object*/
#define STT_NUM 7 /* Number of defined types. */
#define STT_LOOS 10 /* Start of OS-specific */
#define STT_GNU_IFUNC 10 /* Symbol is indirect code object */
#define STT_HIOS 12 /* End of OS-specific */
#define STT_LOPROC 13 /* Start of processor-specific */
#define STT_HIPROC 15 /* End of processor-specific */STT_NOTYPE表示未指定类型。每个符号表开头都有一个该类型的表项。
STT_OBJECT表示数据，如变量、数组等。
STT_FUNC表示函数或可执行代码。
STT_SECTION表示一个section，该类型符号的绑定特征是STB_LOCAL。
STT_FILE表示文件名。该类型符号的绑定特征是STB_LOCAL，st_shndx的值为SHN_ABS。
5、st_other表示符号的可见性，只使用了该成员的低2位。它的可能取值如下所示：
#define STV_DEFAULT 0 /* Default symbol visibility rules */
#define STV_INTERNAL 1 /* Processor specific hidden class */
#define STV_HIDDEN 2 /* Sym unavailable in other modules */
#define STV_PROTECTED 3 /* Not preemptible, not exported */6、st_shndx表示符号所在的section对应的section header的索引号。它有以下三个特殊值：
#define SHN_UNDEF 0 /* Undefined section */
#define SHN_ABS 0xfff1 /* Associated symbol is absolute */
#define SHN_COMMON 0xfff2 /* Associated symbol is common */SHN_UNDEF表示该符号是未定义的，也就是说它可能定义在其他目标文件中，只有在程序执行时才能实际确定。对于索引值为STN_UNDEF的表项，st_shndx的值也是SHN_UNDEF。
SHN_ABS表示该符号的值在重定位时不会改变。
SHN_COMMON表示该符号尚未被分配空间，它的值st_value为地址对齐字节数。
通过执行$ readelf -s tanglinux命令可获得tanglinux文件中的符号表和动态符号表，而执行$ readelf --dyn-syms tanglinux命令只获取动态符号表，如下所示：
Symbol table '.dynsym' contains 4 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 00000000 0 NOTYPE LOCAL DEFAULT UND
1: 00000000 0 NOTYPE WEAK DEFAULT UND __gmon_start__
2: 00000000 0 FUNC GLOBAL DEFAULT UND __libc_start_main@GLIBC_2.0 (2)
3: 080484ac 4 OBJECT GLOBAL DEFAULT 17 _IO_stdin_used二、动态链接符号的版本控制信息
符号的版本控制机制并没有被广泛应用，主要使用在GNU的C库中，用来提供符号的版本信息，以实现共享库的后向兼容。简单的说，一个符号可能有一个或多个版本的实现，多个实现在源码层次就有多段不同的代码，但在链接层次只向外提供一个相同的符号名，然后用版本信息（如@ GLIBC_2.0，两个@表示默认版本）以示区别不同的实现。至于程序执行时使用哪个版本的实现跟该程序在编译时所引用的版本有关。
对于动态链接符号的版本信息，当前系统的链接器共使用三个section来支持，分别为SHT_GNU_versym（.gnu.version）、SHT_GNU_verdef（.gnu.version_d）和SHT_GNU_verneed（.gnu.version_r）。动态库定义符号的版本信息（保存在.gnu.version_d section），可执行程序和动态库引用（其它）动态库所定义的符号版本信息（保存在.gnu.version_r section）。
1、.gnu.version section中包含一个版本信息索引表，每个表项的长度为Elf32_Half（16）个字节，表项的数量与动态符号表.dynsym中所有符号的数目相同，并且一一对应。表项中的值由Elf32_Vernaux.vna_other或Elf32_Verdef.vd_ndx所提供。它的表项有两个特殊值，0和1，0表示局部符号，1表示定义在当前可执行文件或动态库中的全局符号，它们不表示版本信息。除这两个特殊值之外，其他值表示是在.gnu.version_d或.gnu.version_r中的版本信息的索引值。
2、.gnu.version_r section存在于可执行文件和动态库（动态库也会引用其他动态库中的符号）中，表示所引用的符号的版本信息。其中项的数目存储在.dynamic section中DT_VERNEEDNUM类型的表项中。它由以下两个数据结构所定义：
typedef struct
{
Elf32_Half vn_version; /* Version of structure */
Elf32_Half vn_cnt; /* Number of associated aux entries */
Elf32_Word vn_file; /* Offset of filename for this dependency */
Elf32_Word vn_aux; /* Offset in bytes to vernaux array */
Elf32_Word vn_next; /* Offset in bytes to next verneed entry */
} Elf32_Verneed;
typedef struct
{
Elf32_Word vna_hash; /* Hash value of dependency name */
Elf32_Half vna_flags; /* Dependency specific information */
Elf32_Half vna_other; /* Unused */
Elf32_Word vna_name; /* Dependency name string offset */
Elf32_Word vna_next; /* Offset in bytes to next vernaux entry */
} Elf32_Vernaux;其中，vn_version的有效值目前只有1，表示数据自身的版本；vn_cnt表示辅助信息的数量，也就是紧随其后Elf32_Vernaux项的总数，也就是说该动态库中有vn_cnt数量的版本信息被引用；vn_file表示文件名（符号所在的动态库文件）在相关字符串表中的索引；vn_aux表示Elf32_Vernaux元素的数组相对当前Elf32_Verneed的偏移量（字节数，也就是Elf32_Verneed的大小）； vn_next表示下一个Elf32_Verneed相对当前Elf32_Verneed的偏移量（字节数，也就是Elf32_Verneed加上vn_cnt个Elf32_Vernaux的总大小），0表示它是最后一个。
vna_hash表示vna_name对应的版本名字的散列值（使用sysv风格的散列算法）；vna_flags基本为零，或者为VER_FLG_WEAK（0x2）表示弱符号；vna_other表示该版本信息的索引值，被.gnu.version section所使用；vna_name表示版本信息（也就是字符串）在相关字符串表中的索引；vna_next表示下一个Elf32_Vernaux相对当前Elf32_Vernaux的偏移量（字节数，也就是Elf32_Vernaux的大小），0表示它是最后一个。
在.gnu.version_r section中，可执行文件或动态库引用了多少个其他动态库文件则有多少个Elf32_Verneed结构体的数据，如果这个其他动态库文件中有多少个版本信息被引用则紧随其后就有多少个Elf32_Vernaux结构体的数据。
执行readelf可查看可执行文件tanglinux中的版本信息，如下所示：
$ readelf -V tanglinux
Version symbols section '.gnu.version' contains 4 entries:
Addr: 0000000008048276 Offset: 0x000276 Link: 6 (.dynsym)
000: 0 (*local*) 0 (*local*) 2 (GLIBC_2.0) 1 (*global*)
Version needs section '.gnu.version_r' contains 1 entries:
Addr: 0x0000000008048280 Offset: 0x000280 Link: 7 (.dynstr)
000000: Version: 1 File: libc.so.6 Cnt: 1
0x0010: Name: GLIBC_2.0 Flags: none Version: 2这里，readelf程序针对.gnu.version_d section的打印信息有点小问题，第一行没有换行。
3、.gnu.version_d section只存在于动态库文件中，表示自身所定义的符号的版本信息。其中项的数目存储在.dynamic section中DT_VERDEFNUM类型的表项中。它由以下两个数据结构所定义：
typedef struct
{
Elf32_Half vd_version; /* Version revision */
Elf32_Half vd_flags; /* Version information */
Elf32_Half vd_ndx; /* Version Index */
Elf32_Half vd_cnt; /* Number of associated aux entries */
Elf32_Word vd_hash; /* Version name hash value */
Elf32_Word vd_aux; /* Offset in bytes to verdaux array */
Elf32_Word vd_next; /* Offset in bytes to next verdef entry */
} Elf32_Verdef;
typedef struct
{
Elf32_Word vda_name; /* Version or dependency names */
Elf32_Word vda_next; /* Offset in bytes to next verdaux entry */
} Elf32_Verdaux;
其中，vd_version的有效值为目前只有1，表示数据自身的版本；vd_cnt表示辅助信息的数量，也就是紧随其后Elf32_Verdaux项的总数，也就是说同一符号可能有多个版本；vd_hash表示第一个Elf32_Verdaux之中的vda_name对应的版本名字的散列值（使用sysv风格的散列算法）；vd_aux表示Elf32_Verdaux元素的数组相对当前Elf32_Verdef的偏移量（字节数，也就是Elf32_Verdef的大小）； vd_next表示下一个Elf32_Verdef相对当前Elf32_Verdef的偏移量（字节数，也就是Elf32_Verdef加上vd_cnt个Elf32_Verdaux的总大小），0表示它是最后一个。
vd_flags的默认值为0，还有两个特殊的值如下所示：
#define VER_FLG_BASE 0x1 /* Version definition of file itself */
#define VER_FLG_WEAK 0x2 /* Weak version identifier */VER_FLG_BASE表示定义动态库自身的版本；VER_FLG_WEAK表示弱符号。
vd_ndx表示该版本信息的索引值，被.gnu.version section所使用，它还有以下特殊值：
#define VER_NDX_LOCAL 0 /* Symbol is local. */
#define VER_NDX_GLOBAL 1 /* Symbol is global. */
#define VER_NDX_LORESERVE 0xff00 /* Beginning of reserved entries. */
#define VER_NDX_ELIMINATE 0xff01 /* Symbol is to be eliminated. */VER_NDX_LOCAL表示局部符号，VER_NDX_GLOBAL表示全局符号，它们跟.gnu.version section中所使用的两个特殊值的意义相同。
Elf32_Verdaux数据结构中的vda_name表示版本信息（也就是字符串）在相关字符串表中的索引；vda_next表示下一个Elf32_Verdaux相对当前Elf32_Verdaux的偏移量（字节数，也就是Elf32_Verdaux的大小），0表示它是最后一个。
使用readelf命令可查看/lib/libdl-2.17.so中的版本信息，如下所示：
$ readelf -V /lib/libdl-2.17.so
Version symbols section '.gnu.version' contains 42 entries:
Addr: 00000000000006be Offset: 0x0006be Link: 4 (.dynsym)
000: 0 (*local*) 0 (*local*) 0 (*local*) 7 (GLIBC_2.0)
004: 0 (*local*) 7 (GLIBC_2.0) 8 (GLIBC_2.1) 9 (GLIBC_2.1.3)
008: 7 (GLIBC_2.0) 7 (GLIBC_2.0) 0 (*local*) a (GLIBC_PRIVATE)
00c: 7 (GLIBC_2.0) b (GLIBC_PRIVATE) 7 (GLIBC_2.0) 0 (*local*)
010: 7 (GLIBC_2.0) b (GLIBC_PRIVATE) b (GLIBC_PRIVATE) 0 (*local*)
014: a (GLIBC_PRIVATE) 0 (*local*) 0 (*local*) 7 (GLIBC_2.0)
018: a (GLIBC_PRIVATE) 7 (GLIBC_2.0) 2 (GLIBC_2.0) 5 (GLIBC_2.3.4)
01c: 3 (GLIBC_2.1) 3 (GLIBC_2.1) 2h(GLIBC_2.0) 4 (GLIBC_2.3.3)
020: 6 (GLIBC_PRIVATE) 2 (GLIBC_2.0) 2 (GLIBC_2.0) 3 (GLIBC_2.1)
024: 2 (GLIBC_2.0) 4 (GLIBC_2.3.3) 5 (GLIBC_2.3.4) 4 (GLIBC_2.3.3)
028: 2 (GLIBC_2.0) 6 (GLIBC_PRIVATE)
Version definition section '.gnu.version_d' contains 6 entries:
Addr: 0x0000000000000714 Offset: 0x000714 Link: 5 (.dynstr)
000000: Rev: 1 Flags: BASE Index: 1 Cnt: 1 Name: libdl.so.2
0x001c: Rev: 1 Flags: none Index: 2 Cnt: 1 Name: GLIBC_2.0
0x0038: Rev: 1 Flags: none Index: 3 Cnt: 2 Name: GLIBC_2.1
0x0054: Parent 1: GLIBC_2.0
0x005c: Rev: 1 Flags: none Index: 4 Cnt: 2 Name: GLIBC_2.3.3
0x0078: Parent 1: GLIBC_2.1
0x0080: Rev: 1 Flags: none Index: 5 Cnt: 2 Name: GLIBC_2.3.4
0x009c: Parent 1: GLIBC_2.3.3
0x00a4: Rev: 1 Flags: none Index: 6 Cnt: 2 Name: GLIBC_PRIVATE
0x00c0: Parent 1: GLIBC_2.3.4
Version definition past end of section
Version needs section '.gnu.version_r' contains 2 entries:
Addr: 0x00000000000007dc Offset: 0x0007dc Link: 5 (.dynstr)
000000: Version: 1 File: ld-linux.so.2 Cnt: 1
0x0010: Name: GLIBC_PRIVATE Flags: none Version: 10
0x0020: Version: 1 File: libc.so.6 Cnt: 4
0x0030: Name: GLIBC_PRIVATE Flags: none Version: 11
0x0040: Name: GLIBC_2.1.3 Flags: none Version: 9
0x0050: Name: GLIBC_2.1 Flags: none Version: 8
0x0060: Name: GLIBC_2.0 Flags: none Version: 7在.gnu.version_r的打印信息中，Version是索引值。从中可以看出，在同一动态库中，Elf32_Vernaux.vna_other和Elf32_Verdef.vd_ndx的值是连续的，并且没有重复值。
当程序执行时，动态链接器会检索该程序中所有的Elf32_Vernaux数据，以确定所引用的符号所在的动态库是否已加载并且该符号是否已被它定义（在它的Elf32_Verdef中），如果符号缺失并且Elf32_Vernaux.vna_flags没有设置为VER_FLG_WEAK，则该程序返回错误并退出，如果Elf32_Vernaux.vna_flags有设置为VER_FLG_WEAK，则该程序打印警告信息并继续执行。
最后，还要解释一下.gnu.version、.gnu.version_d和.gnu.version_r等对应的section header中sh_link和sh_info值的意义，如下所示：
$ readelf -S /lib/libdl-2.17.so
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 4] .dynsym DYNSYM 00000210 000210 0002a0 10 A 5 1 4
[ 5] .dynstr STRTAB 000004b0 0004b0 00020e 00 A 0 0 1
[ 6] .gnu.version VERSYM 000006be 0006be 000054 02 A 4 0 2
[ 7] .gnu.version_d VERDEF 00000714 000714 0000c8 00 A 5 6 4
[ 8] .gnu.version_r VERNEED 000007dc 0007dc 000070 00 A 5 2 4其中，sh_link是所使用的section header的索引值，如下图所示：
三、动态链接符号的散列表
这里的散列算法是用来提高符号的查询效率。散列算法必须提供散列函数和冲突解决方法。
在当前的操作系统中，链接器支持两种风格的散列算法，编译程序时可以任选一种，也可以两种都选。默认情况下，链接器通过给命令行选项--hash-style指定gnu值来生成SHT_GNU_HASH类型的符号散列表。如果想生成SHT_HASH类型的散列表，则需要在编译器的命令行中给链接器的--hash-style选项指定sysv值（两种风格都想支持的话则指定both值）。这里暂时用--hash-style=both命令行选项来编译tanglinux.c，如下所示：
$ gcc -m32 -Wl,--hash-style=both tanglinux.c -o tanglinux
$ readelf -S tanglinux
Section Headers:
[Nr] Name Type Addr Off Size ES Flg Lk Inf Al
[ 0] NULL 00000000 000000 000000 00 0 0 0
[ 4] .hash HASH 080481ac 0001ac 000024 04 A 6 0 4
[ 5] .gnu.hash GNU_HASH 080481d0 0001d0 000020 04 A 6 0 4通过执行readelf命令可以查看散列表中的关键数据以及与动态符号表的关系，如下所示：
$ readelf -sD tanglinux
Symbol table for image:
Num Buc: Value Size Type Bind Vis Ndx Name
1 0: 00000000 0 NOTYPE WEAK DEFAULT UND __gmon_start__
2 1: 00000000 0 FUNC GLOBAL DEFAULT UND __libc_start_main
3 2: 080484ac 4 OBJECT GLOBAL DEFAULT 17 _IO_stdin_used
Symbol table of `.gnu.hash' for image:
Num Buc: Value Size Type Bind Vis Ndx Name
3 1: 080484ac 4 OBJECT GLOBAL DEFAULT 17 _IO_stdin_used其中，Num表示该符号在动态符号表（如.dynsym）中的索引值，Buc表示槽的位置（类似数组的下标值）。其他值就是通过符号索引值从符号表中获得（符号名中@及其后的所有字符都不参与散列计算）。
1、.hash section
.hash section的数据格式如下图所示（每个项的数据类型都为Elf32_Word字节）：
nbucket表示散列表的槽数量（根据动态链接符号的数量来获得，如1、3、17、37、67、97、131等等），nchain表示链数量，它必须与动态链接符号的数量一致（这个要求非常重要，保证有足够的存储空间）。bucket[0]至bucket[nbucket-1]，chain[0]至chain[nchain-1]，它们之中保存的都是符号表的索引值，默认值STN_UNDEF（即0）用来表示链尾（这也是符号表开头为什么有一个索引值为STN_UNDEF的无效的表项的意义）。
执行$ hexdump -C tanglinux | more命令获取.hash section中的数据，该section的文件偏移量为0x1ac，长度为0x24个字节，如下图所示：
从上图可知，槽数量为3，链数量为4，bucket[0]至bucket[2]的值依次为1、2、3（这是巧合，不是规律），chain[0]至chain[3]中的值都为0。如下图所示：
该散列算法解决冲突的方法仍然是常见的链地址法，但代码的实现令人拍案叫绝（每次读到这样的代码都兴奋得不得了，感谢开源先辈们的付出）。
可执行文件tanglinux中没有发生冲突的情况。对于同一槽位来说，新产生的散列值从链头插入，链尾的散列值为STN_UNDEF（0）。从查找的角度看，链表中的散列值是先进后出的。图中箭头所指的位置也是该槽位的链尾。
2、.gnu.hash section
GNU散列算法相关信息可参考网页GNU Hash ELF Sections，其中说明了散列函数的定义、.gnu.hash section的数据结构、查找算法等等。
动态链接符号表中的局部符号和未定义符号不参与GNU散列运算。
每个.gnu.hash section的开头都有一个16个字节的头，共4成员，每个成员4个字节，如下所示：
typedef struct
{
Elf32_Word nbuckets; /* The number of hash buckets */
Elf32_Word symndx; /* the index of the first symbol in the dynamic symbol table that is to be accessible via the hash table */
Elf32_Word maskwords; /* The number of ELFCLASS sized words in the Bloom filter portion of the hash table section */
Elf32_Word shift2; /* A shift count used by the Bloom filter */
} Elf32_Hashdr;其中，nbuckets为槽数量（跟SYSV散列算法的计算方法相同，但最少值为2）；symndx为动态符号表中第一个通过散列表查询的符号的索引值（通过符号表中符号的总数（假设为dynsymcount）减去该值可确定有多少个符号参与散列查询）；maskwords为Bloom filter掩码的大小（单位为字长的字节数），它的值必须是1或2的倍数；shift2表示位移量，为Bloom filter模拟第二个散列函数的值。
紧接着依次是Bloom filter掩码的数据、槽的数据以及链的数据。链的数量为dynsymcount减去symndx，也就是说它跟参与散列运算的符号的总数相等。
在槽数据和链数据中，它们的元素的长度都是4个字节。而Bloom filter掩码数据中的元素的长度跟ELF的类型有关， ELFCLASS32类型的为4个字节（这时Elf32_Shdr. sh_entsize的值为4），ELFCLASS64类型的为8个字节（这时Elf32_Shdr.sh_entsize的值为0，表示该section中的项不是等长的）。
.gnu.hash section的总体结构如下图所示：
如果.dynsym section中没有符号参与散列计算，则会在ELF文件中生成一个24个字节（ELFCLASS32类型）的特殊的.gnu.hash section，它们的值依次为1、1、1、0、0、0，没有链数据。
执行$ hexdump -C tanglinux | more命令获取.gnu.hash section中的数据，该section的文件偏移量为0x1d0，长度为0x20个字节，如下图所示：
从上图可知，槽数量为2，链数量为1，bucket[0]和bucket[1]的值依次为0和3，chain[0]的值为符号的散列值（bucket[1]中索引值对应的符号）。其中，散列值的最后一位（即bit[0]）用来表示是否是该槽位的链数组的最后一个，bit[0]为1表示是最后一个，否则不是。如下图所示：
GNU散列算法包含Bloom filter掩码，是为了提供更高的查询效率。Bloom filter掩码查询方法的伪代码如下所示：
h1 = dl_new_hash(symname); //求符号的散列值
h2 = h1 >> shift2;
c = sizeof(bloom[0]) * 8;
n = (h1 / c) & (maskwords - 1);
bitmask = (1 << (h1 % c)) | (1 << (h2 % c));
if ((bloom[n] & bitmask) != bitmask)
return FALSE; //表示不可能存在两个比特位的值都为1时才能确定符号表中可能存在该符号，后续还要通过比较散列值、比较符号名才能真正确定。
GNU散列算法解决冲突的方法非常奇特，是通过更改参与散列的符号的索引值来实现的（在将这些符号的数据保存到ELF文件之前），相同槽位值的所有符号的散列值依次保存，它们的索引值依次递增，而槽位置（如bucket[]）保存它们首元素的索引值。如下例所示：
$ readelf --dyn-syms /lib/ld-linux.so.2
Symbol table '.dynsym' contains 30 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 00000000 0 NOTYPE LOCAL DEFAULT UND
1: 00017150 18 FUNC GLOBAL DEFAULT 12 __get_cpu_features@@GLIBC_PRIVATE
2: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.1
3: 000126b0 30 FUNC GLOBAL DEFAULT 12 _dl_get_tls_static_info@@GLIBC_PRIVATE
4: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_PRIVATE
5: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.3
6: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.4
7: 00017fb0 80 FUNC WEAK DEFAULT 12 free@@GLIBC_2.0
8: 00018000 108 FUNC WEAK DEFAULT 12 realloc@@GLIBC_2.0
9: 00023838 4 OBJECT WEAK DEFAULT 21 _dl_starting_up@@GLIBC_PRIVATE
10: 000129d0 266 FUNC GLOBAL DEFAULT 12 _dl_allocate_tls@@GLIBC_PRIVATE
11: 000238e4 20 OBJECT GLOBAL DEFAULT 21 _r_debug@@GLIBC_2.0
12: 00022eec 4 OBJECT GLOBAL DEFAULT 17 __libc_stack_end@@GLIBC_2.1
13: 00017e20 260 FUNC WEAK DEFAULT 12 __libc_memalign@@GLIBC_2.0
14: 00012ae0 133 FUNC GLOBAL DEFAULT 12 _dl_deallocate_tls@@GLIBC_PRIVATE
15: 00017f60 74 FUNC WEAK DEFAULT 12 calloc@@GLIBC_2.0
16: 00022ec0 4 OBJECT GLOBAL DEFAULT 17 _dl_argv@@GLIBC_PRIVATE
17: 000120d0 574 FUNC GLOBAL DEFAULT 12 _dl_mcount@@GLIBC_2.1
18: 00012650 95 FUNC GLOBAL DEFAULT 12 _dl_tls_setup@@GLIBC_PRIVATE
19: 00010800 2 FUNC GLOBAL DEFAULT 12 _dl_debug_state@@GLIBC_PRIVATE
20: 00012e30 75 FUNC GLOBAL DEFAULT 12 ___tls_get_addr@@GLIBC_2.3
21: 00023000 2100 OBJECT GLOBAL DEFAULT 20 _rtld_global@@GLIBC_PRIVATE
22: 00012e80 6 FUNC GLOBAL DEFAULT 12 __tls_get_addr@@GLIBC_2.3
23: 000131c0 150 FUNC GLOBAL DEFAULT 12 _dl_make_stack_executable@@GLIBC_PRIVATE
24: 00017f30 40 FUNC WEAK DEFAULT 12 malloc@@GLIBC_2.0
25: 000127b0 533 FUNC GLOBAL DEFAULT 12 _dl_allocate_tls_init@@GLIBC_PRIVATE
26: 00022ca0 536 OBJECT GLOBAL DEFAULT 17 _rtld_global_ro@@GLIBC_PRIVATE
27: 00022ef0 4 OBJECT GLOBAL DEFAULT 17 __libc_enable_secure@@GLIBC_PRIVATE
28: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.0
29: 000093b0 1614 FUNC GLOBAL DEFAULT 12 _dl_rtld_di_serinfo@@GLIBC_PRIVATE在/lib/ld-linux.so.2文件的.dynsym section中，索引值1至29对应的符号都参与GNU散列，它们存储的位置实际上已经是按照GNU散列的槽位置从小（如0）到大（如16）的次序依次确定。为了实现该目的，链接器在计算GNU散列时，符号原有的索引值被更改。所有参与GNU散列的符号依次保存在所有不参与散列的符号的后面。
通过执行$ readelf -sD /lib/ld-linux.so.2命令打印该文件中所有散列算法的输出，如下所示：
$ readelf -sD /lib/ld-linux.so.2
Symbol table for image:
Num Buc: Value Size Type Bind Vis Ndx Name
3 0: 000126b0 30 FUNC GLOBAL DEFAULT 12 _dl_get_tls_static_info
1 0: 00017150 18 FUNC GLOBAL DEFAULT 12 __get_cpu_features
28 1: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.0
26 2: 00022ca0 536 OBJECT GLOBAL DEFAULT 17 _rtld_global_ro
25 2: 000127b0 533 FUNC GLOBAL DEFAULT 12 _dl_allocate_tls_init
2 2: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.1
23 2: 000131c0 150 FUNC GLOBAL DEFAULT 12 _dl_make_stack_executable
15 3: 00017f60 74 FUNC WEAK DEFAULT 12 calloc
5 4: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.3
19 4: 00010800 2 FUNC GLOBAL DEFAULT 12 _dl_debug_state
14 4: 00012ae0 133 FUNC GLOBAL DEFAULT 12 _dl_deallocate_tls
13 4: 00017e20 260 FUNC WEAK DEFAULT 12 __libc_memalign
6 5: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.4
27 5: 00022ef0 4 OBJECT GLOBAL DEFAULT 17 __libc_enable_secure
8 6: 00018000 108 FUNC WEAK DEFAULT 12 realloc
4 6: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_PRIVATE
22 7: 00012e80 6 FUNC GLOBAL DEFAULT 12 __tls_get_addr
9 8: 00023838 4 OBJECT WEAK DEFAULT 21 _dl_starting_up
18 10: 00012650 95 FUNC GLOBAL DEFAULT 12 _dl_tls_setup
24 10: 00017f30 40 FUNC WEAK DEFAULT 12 malloc
11 11: 000238e4 20 OBJECT GLOBAL DEFAULT 21 _r_debug
7 12: 00017fb0 80 FUNC WEAK DEFAULT 12 free
10 13: 000129d0 266 FUNC GLOBAL DEFAULT 12 _dl_allocate_tls
29 13: 000093b0 1614 FUNC GLOBAL DEFAULT 12 _dl_rtld_di_serinfo
20 14: 00012e30 75 FUNC GLOBAL DEFAULT 12 ___tls_get_addr
17 14: 000120d0 574 FUNC GLOBAL DEFAULT 12 _dl_mcount
16 15: 00022ec0 4 OBJECT GLOBAL DEFAULT 17 _dl_argv
21 15: 00023000 2100 OBJECT GLOBAL DEFAULT 20 _rtld_global
12 16: 00022eec 4 OBJECT GLOBAL DEFAULT 17 __libc_stack_end
Symbol table of `.gnu.hash' for image:
Num Buc: Value Size Type Bind Vis Ndx Name
1 0: 00017150 18 FUNC GLOBAL DEFAULT 12 __get_cpu_features
2 0: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.1
3 1: 000126b0 30 FUNC GLOBAL DEFAULT 12 _dl_get_tls_static_info
4 2: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_PRIVATE
5 2: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.3
6 3: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.4
7 3: 00017fb0 80 FUNC WEAK DEFAULT 12 free
8 5: 00018000 108 FUNC WEAK DEFAULT 12 realloc
9 5: 00023838 4 OBJECT WEAK DEFAULT 21 _dl_starting_up
10 5: 000129d0 266 FUNC GLOBAL DEFAULT 12 _dl_allocate_tls
11 5: 000238e4 20 OBJECT GLOBAL DEFAULT 21 _r_debug
12 6: 00022eec 4 OBJECT GLOBAL DEFAULT 17 __libc_stack_end
13 7: 00017e20 260 FUNC WEAK DEFAULT 12 __libc_memalign
14 8: 00012ae0 133 FUNC GLOBAL DEFAULT 12 _dl_deallocate_tls
15 9: 00017f60 74 FUNC WEAK DEFAULT 12 calloc
16 9: 00022ec0 4 OBJECT GLOBAL DEFAULT 17 _dl_argv
17 10: 000120d0 574 FUNC GLOBAL DEFAULT 12 _dl_mcount
18 11: 00012650 95 FUNC GLOBAL DEFAULT 12 _dl_tls_setup
19 12: 00010800 2 FUNC GLOBAL DEFAULT 12 _dl_debug_state
20 12: 00012e30 75 FUNC GLOBAL DEFAULT 12 ___tls_get_addr
21 13: 00023000 2100 OBJECT GLOBAL DEFAULT 20 _rtld_global
22 14: 00012e80 6 FUNC GLOBAL DEFAULT 12 __tls_get_addr
23 15: 000131c0 150 FUNC GLOBAL DEFAULT 12 _dl_make_stack_executable
24 15: 00017f30 40 FUNC WEAK DEFAULT 12 malloc
25 15: 000127b0 533 FUNC GLOBAL DEFAULT 12 _dl_allocate_tls_init
26 15: 00022ca0 536 OBJECT GLOBAL DEFAULT 17 _rtld_global_ro
27 16: 00022ef0 4 OBJECT GLOBAL DEFAULT 17 __libc_enable_secure
28 16: 00000000 0 OBJECT GLOBAL DEFAULT ABS GLIBC_2.0
29 16: 000093b0 1614 FUNC GLOBAL DEFAULT 12 _dl_rtld_di_serinfo从中可以看出，槽位置（Buc列）是从0到16依次排列，相应的符号的索引值（Num列）是从1到29依次排列。
下面通过实例说明SYSV和GNU两种散列算法的实现（大部分源码来自binutils-2.27.tar.bz2项目，参与计算的符号来自执行$ readelf --dyn-syms /lib/ld-linux.so.2命令的输出），代码如下所示：
/* hash.c utf-8 without BOM */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 根据执行$ readelf --dyn-syms /lib/ld-linux.so.2命令获得，它们跟符号表中的顺序一致 */
static char *symbolTable[] = {
"",
"__get_cpu_features@@GLIBC_PRIVATE",
"GLIBC_2.1",
"_dl_get_tls_static_info@@GLIBC_PRIVATE",
"GLIBC_PRIVATE",
"GLIBC_2.3",
"GLIBC_2.4",
"free@@GLIBC_2.0",
"realloc@@GLIBC_2.0",
"_dl_starting_up@@GLIBC_PRIVATE",
"_dl_allocate_tls@@GLIBC_PRIVATE",
"_r_debug@@GLIBC_2.0",
"__libc_stack_end@@GLIBC_2.1",
"__libc_memalign@@GLIBC_2.0",
"_dl_deallocate_tls@@GLIBC_PRIVATE",
"calloc@@GLIBC_2.0",
"_dl_argv@@GLIBC_PRIVATE",
"_dl_mcount@@GLIBC_2.1",
"_dl_tls_setup@@GLIBC_PRIVATE",
"_dl_debug_state@@GLIBC_PRIVATE",
"___tls_get_addr@@GLIBC_2.3",
"_rtld_global@@GLIBC_PRIVATE",
"__tls_get_addr@@GLIBC_2.3",
"_dl_make_stack_executable@@GLIBC_PRIVATE",
"malloc@@GLIBC_2.0",
"_dl_allocate_tls_init@@GLIBC_PRIVATE",
"_rtld_global_ro@@GLIBC_PRIVATE",
"__libc_enable_secure@@GLIBC_PRIVATE",
"GLIBC_2.0",
"_dl_rtld_di_serinfo@@GLIBC_PRIVATE",
};
/* 代码来自binutils-2.27/bfd/elflink.c文件 */
static const size_t elf_buckets[] =
{
1, 3, 17, 37, 67, 97, 131, 197, 263,
521, 1031, 2053, 4099, 8209, 16411, 32771, 0
};
static size_t compute_bucket_count(unsigned long int nsyms, int gnu_hash)
{
size_t best_size = 0;
unsigned long int i;
for (i = 0; elf_buckets[i] != 0; i++)
{
best_size = elf_buckets[i];
if (nsyms < elf_buckets[i + 1])
break;
}
if (gnu_hash && best_size < 2)
best_size = 2;
return best_size;
}
/* sysv散列函数，来自binutils-2.27/bfd/elf.c文件 */
unsigned long bfd_elf_hash(const char *namearg)
{
const unsigned char *name = (const unsigned char *)namearg;
unsigned long h = 0;
unsigned long g;
int ch;
while ((ch = *name++) != '\0')
{
h = (h << 4) + ch;
if ((g = (h & 0xf0000000)) != 0)
{
h ^= g >> 24;
/* The ELF ABI says `h &= ~g', but this is equivalent in
this case and on some machines one insn instead of two. */
h ^= g;
}
}
return h & 0xffffffff;
}
/* GNU散列函数，来自binutils-2.27/bfd/elf.c */
unsigned long bfd_elf_gnu_hash(const char *namearg)
{
const unsigned char *name = (const unsigned char *)namearg;
unsigned long h = 5381;
unsigned char ch;
while ((ch = *name++) != '\0')
h = (h << 5) + h + ch;
return h & 0xffffffff;
}
static int copy_name(const char *name, char **result)
{
char *p;
size_t size = strlen(name);
p = strchr (name, '@');
if (p != NULL)
size = p - name;
*result = (char *)malloc(size + 1);
if (*result == NULL)
return -1;
memcpy(*result, name, size);
(*result)[size] = '\0';
return 0;
}
static void print_symbol(const char *name)
{
char *symname;
if (copy_name(name, &symname) < 0)
return ;
printf("%s", symname);
free(symname);
return ;
}
int main()
{
unsigned long int dynsymcount;
size_t bucketcount;
unsigned long int *hashcodes;
size_t hash_entry_size = 4;
size_t size;
/* .hash section */
dynsymcount = sizeof(symbolTable) / sizeof(char *);
bucketcount = compute_bucket_count(dynsymcount, 0);
if (bucketcount == 0)
return -1;
size = (2 + dynsymcount + bucketcount) * hash_entry_size;
hashcodes = (unsigned long int *)malloc(size);
if (hashcodes == NULL)
return -1;
memset(hashcodes, 0, size); //这里必须清零
//设置.hash section中的槽数量和链数量
hashcodes[0] = bucketcount;
hashcodes[1] = dynsymcount;
unsigned long int i;
unsigned long int bucket;
unsigned char *bucketpos;
unsigned long int chain;
unsigned long int ha;
char *symname;
//创建.hash section中的数据，包含解决散列冲突的方法
for (i = 0; i < dynsymcount; ++i)
{
if (copy_name(symbolTable[i], &symname) < 0) //去掉符号名中@及其后所有的字符
return -1;
bucket = bfd_elf_hash(symname) % bucketcount; //获取槽位置的索引
free(symname);
bucketpos = (unsigned char *)hashcodes + (bucket + 2) * hash_entry_size; //获取槽位置
chain = *(unsigned long int *)bucketpos; //暂存该槽位置中的值（可能为0，也可能为上一个符号的索引值）
*(unsigned long int *)bucketpos = i; //将新的符号表的索引值保存在该槽位置
//奇妙的地方在此，符号表的索引（即这里的i值）也成为了链位置的索引，如此不管冲突怎么发生，都不会覆盖以前保存的有效值
bucketpos = (unsigned char *)hashcodes + (bucketcount + 2 + i) * hash_entry_size;
*(unsigned long int *)bucketpos = chain; //将旧的符号表的索引值保存在该链位置
}
unsigned long int hn, si;
unsigned long int *buckets = hashcodes + 2;
unsigned long int *chains = hashcodes + 2 + bucketcount;
//打印.hash section中的数据，查询数据的方法也与此相同
printf("\nSymbol table for image:\n");
printf (" Num Buc: Name\n");
for (hn = 0; hn < bucketcount; ++hn)
{
if (!buckets[hn])
continue;
for (si = buckets[hn]; si < dynsymcount && si > 0; si = chains[si])
{
printf("%5lu %3lu: ", si, hn);
print_symbol(symbolTable[si]);
printf("\n");
}
}
//以链表形式打印各个元素的值
int count;
unsigned long int bsi;
printf("\n.hash %d buckets:\n", bucketcount);
for (hn = 0; hn < bucketcount; ++hn)
{
if (!buckets[hn])
{
printf(" bucket[%2lu](%2lu) no element\n", hn, buckets[hn]);
continue;
}
count = 0;
for (si = buckets[hn]; si < dynsymcount && si > 0; si = chains[si])
{
if (count == 0)
printf(" bucket[%2lu](%2lu) --> ", hn, si);
else
printf("chain[%2lu](%2lu) --> ", bsi, si);
bsi = si;
++count;
}
printf("chain[%2lu](%lu)\n", bsi, si);
}
free(hashcodes);
/* .gnu.hash section */
dynsymcount = sizeof(symbolTable) / sizeof(char *);
size = dynsymcount * 2 * sizeof(unsigned long int); //2个符号总数
hashcodes = (unsigned int long *)malloc(size);
if (hashcodes == NULL)
return -1;
unsigned long int *hashval = hashcodes + dynsymcount;
unsigned long int nsyms = 0;
//求每个符号名的散列值，并保存两份，第一份（hashcodes所指向）依次保存，
//第二份（hashval所指向）按符号的索引值保存。
for (i = 0; i < dynsymcount; ++i)
{
if (i == 0) //头个元素是未定义符号，不参与散列
continue;
if (copy_name(symbolTable[i], &symname) < 0) //去掉符号名中@及其后所有的字符
return -1;
ha = bfd_elf_gnu_hash(symname);
free(symname);
hashcodes[nsyms] = ha;
hashval[i] = ha;
++nsyms;
}
// 如果nsyms等于0，则在可执行文件中会生成一个24个字节（ELFCLASS32类型）的特殊.gnu.hash section
bucketcount = compute_bucket_count(nsyms, 1); //至少2个槽位
if (bucketcount == 0)
{
free(hashcodes);
return -1;
}
unsigned long int maskwords, maskbitslog2, x;
x = nsyms;
maskbitslog2 = 1;
while ((x >>= 1) != 0)
++maskbitslog2;
if (maskbitslog2 < 3)
maskbitslog2 = 5;
else if ((1 << (maskbitslog2 - 2)) & nsyms)
maskbitslog2 = maskbitslog2 + 3;
else
maskbitslog2 = maskbitslog2 + 2;
long int shift1, shift2;
unsigned long int mask;
unsigned long int maskbits;
shift1 = 5; //ELFCLASS32类型
mask = (1 << shift1) - 1; //0x1f
shift2 = maskbitslog2; //.gnu.hash section中数据头的shift2，根据参与的符号数决定
maskbits = 1 << maskbitslog2; //maskwords相应的位数
maskwords = 1 << (maskbitslog2 - shift1); //.gnu.hash section中数据头的maskwords
size = bucketcount * sizeof(unsigned long int) * 2; //2个槽数量
size += maskwords * hash_entry_size; //Bloom Filter数据的数量
unsigned long int *bitmask = (unsigned long int *)malloc(size);
if (bitmask == NULL)
{
free(hashcodes);
return -1;
}
//bitmask指向的内存分三段，第一段保存Bloom filter掩码，第二段（counts所指向）保存每个槽位中符号的数量，
//第三段（indx所指向）保存符号的索引值。
unsigned long int *counts = bitmask + maskwords;
unsigned long int *indx = counts + bucketcount;
unsigned long int symindx = dynsymcount - nsyms; //第一个参与散列的符号的索引值
unsigned long int cnt;
memset(bitmask, 0, maskwords * hash_entry_size);
memset(counts, 0, bucketcount * hash_entry_size);
for (i = 0; i < nsyms; ++i)
++counts[hashcodes[i] % bucketcount]; //统计每个槽位符号的数量，且保存在counts[槽位值]中
for (i = 0, cnt = symindx; i < bucketcount; ++i)
{
if (counts[i] != 0) //该槽位有符号散列
{
indx[i] = cnt; //则把首个符号的索引值保存在该槽位
cnt += counts[i]; //跳过counts[i]个槽位值相同的符号
}
}
unsigned char *contents, *ptr, *printdata;
size = (4 + bucketcount + nsyms) * 4; //(数据头+槽数量+链数量)*4
size += maskbits / 8; //Bloom Filter数据的数量
printdata = contents = (unsigned char *)malloc(size);
if (contents == NULL)
{
free (bitmask);
free (hashcodes);
return -1;
}
ptr = contents;
//创建.gnu.hash section中的数据
*(unsigned long int *)contents = bucketcount;
*(unsigned long int *)(contents + 4) = symindx;
*(unsigned long int *)(contents + 8) = maskwords;
*(unsigned long int *)(contents + 12) = shift2;
contents += 16 + maskbits / 8;
for (i = 0; i < bucketcount; ++i) //存储槽数据
{
if (counts[i] == 0)
*(unsigned long int *)contents = 0; //表示该槽位无符号
else
*(unsigned long int *)contents = indx[i]; //该槽位首个符号的索引值
contents += 4;
}
unsigned long int val;
for (i = 0; i < dynsymcount; ++i)
{
if (i == 0)
continue;
bucket = hashval[i] % bucketcount;
//Bloom filter掩码中的两个比特位置位
val = (hashval[i] >> shift1) & ((maskbits >> shift1) - 1);
bitmask[val] |= ((unsigned long int)1) << (hashval[i] & mask);
bitmask[val] |= ((unsigned long int)1) << ((hashval[i] >> shift2) & mask);
val = hashval[i] & ~(unsigned long int)1;
if (counts[bucket] == 1) //链表中最后一个元素的散列值最后位置1，其它元素的最后位置0
val |= 1;
*(unsigned long int *)(contents + (indx[bucket] - symindx) * 4) = val; //保存链数据
--counts[bucket];
indx[bucket]++; //符号的索引值依次递增
// h->dynindx = s->indx[bucket]++; //在binutils-2.27/bfd/elflink.c文件的elf_renumber_gnu_hash_syms函数中，
//更新符号的索引值，让它们按照槽位值从小到大的次序依次递增
}
contents = ptr + 16;
for (i = 0; i < maskwords; ++i) //保存Bloom filter的掩码值
{
*(unsigned long int *)contents = bitmask[i];
contents += hash_entry_size;
}
free(bitmask);
free(hashcodes);
contents = printdata;
unsigned long int nchain = dynsymcount - symindx;
buckets = (unsigned long int *)(contents + (4 + maskwords) * 4);
chains = (unsigned long int *)(contents + (4 + maskwords + bucketcount) * 4);
//打印.gnu.hash中的数据
printf ("\nSymbol table of `.gnu.hash' for image:\n");
printf (" Num Buc: Name\n");
for (hn = 0; hn < bucketcount; ++hn)
{
if (buckets[hn] != 0)
{
si = buckets[hn];
unsigned long int off = si - symindx;
do
{
printf("%5lu %3lu: ", si, hn);
print_symbol(symbolTable[si]);
printf("\n");
si++;
} while (off < nchain && (chains[off++] & 1) == 0);
}
}
//打印所有槽数据和链数据
printf("\n.gnu.hash %d buckets:\n", bucketcount);
for (hn = 0; hn < bucketcount; ++hn)
{
if (!buckets[hn])
{
printf(" bucket[%2lu](%2lu) no element\n", hn, buckets[hn]);
continue;
}
si = buckets[hn];
unsigned long int off = si - symindx;
printf(" bucket[%2lu](%2lu)", hn, si);
count = 0;
do
{
if (count == 0)
printf(" --> chain[%2lu](%#lx)\n", off, chains[off]);
else
{
printf(" ");
printf(" --> chain[%2lu](%#lx)\n", off, chains[off]);
}
++count;
si++;
} while (off < nchain && (chains[off++] & 1) == 0);
}
free(contents);
return 0;
}
编译并执行，如下所示：
$ gcc -m32 hash.c -o hash
$ ./hash
Symbol table for image:
Num Buc: Name
3 0: _dl_get_tls_static_info
1 0: __get_cpu_features
28 1: GLIBC_2.0
26 2: _rtld_global_ro
25 2: _dl_allocate_tls_init
23 2: _dl_make_stack_executable
2 2: GLIBC_2.1
15 3: calloc
19 4: _dl_debug_state
14 4: _dl_deallocate_tls
13 4: __libc_memalign
5 4: GLIBC_2.3
27 5: __libc_enable_secure
6 5: GLIBC_2.4
8 6: realloc
4 6: GLIBC_PRIVATE
22 7: __tls_get_addr
9 8: _dl_starting_up
24 10: malloc
18 10: _dl_tls_setup
11 11: _r_debug
7 12: free
29 13: _dl_rtld_di_serinfo
10 13: _dl_allocate_tls
20 14: ___tls_get_addr
17 14: _dl_mcount
21 15: _rtld_global
16 15: _dl_argv
12 16: __libc_stack_end
.hash 17 buckets:
bucket[ 0]( 3) --> chain[ 3]( 1) --> chain[ 1](0)
bucket[ 1](28) --> chain[28](0)
bucket[ 2](26) --> chain[26](25) --> chain[25](23) --> chain[23]( 2) --> chain[ 2](0)
bucket[ 3](15) --> chain[15](0)
bucket[ 4](19) --> chain[19](14) --> chain[14](13) --> chain[13]( 5) --> chain[ 5](0)
bucket[ 5](27) --> chain[27]( 6) --> chain[ 6](0)
bucket[ 6]( 8) --> chain[ 8]( 4) --> chain[ 4](0)
bucket[ 7](22) --> chain[22](0)
bucket[ 8]( 9) --> chain[ 9](0)
bucket[ 9]( 0) no element
bucket[10](24) --> chain[24](18) --> chain[18](0)
bucket[11](11) --> chain[11](0)
bucket[12]( 7) --> chain[ 7](0)
bucket[13](29) --> chain[29](10) --> chain[10](0)
bucket[14](20) --> chain[20](17) --> chain[17](0)
bucket[15](21) --> chain[21](16) --> chain[16](0)
bucket[16](12) --> chain[12](0)
Symbol table of `.gnu.hash' for image:
Num Buc: Name
1 0: __get_cpu_features
2 0: GLIBC_2.1
3 1: _dl_get_tls_static_info
4 2: GLIBC_PRIVATE
5 2: GLIBC_2.3
6 3: GLIBC_2.4
7 3: free
8 5: realloc
9 5: _dl_starting_up
10 5: _dl_allocate_tls
11 5: _r_debug
12 6: __libc_stack_end
13 7: __libc_memalign
14 8: _dl_deallocate_tls
15 9: calloc
16 9: _dl_argv
17 10: _dl_mcount
18 11: _dl_tls_setup
19 12: _dl_debug_state
20 12: ___tls_get_addr
21 13: _rtld_global
22 14: __tls_get_addr
23 15: _dl_make_stack_executable
24 15: malloc
25 15: _dl_allocate_tls_init
26 15: _rtld_global_ro
27 16: __libc_enable_secure
28 16: GLIBC_2.0
29 16: _dl_rtld_di_serinfo
.gnu.hash 17 buckets:
bucket[ 0]( 1) --> chain[ 0](0x9f051bc8)
--> chain[ 1](0xf66c3dd7)
bucket[ 1]( 3) --> chain[ 2](0xa1fa6ad7)
bucket[ 2]( 4) --> chain[ 3](0x692a260)
--> chain[ 4](0xf66c3dd9)
bucket[ 3]( 6) --> chain[ 5](0xf66c3dd8)
--> chain[ 6](0x7c96f087)
bucket[ 4]( 0) no element
bucket[ 5]( 8) --> chain[ 7](0x3de00ec6)
--> chain[ 8](0xf05dbda2)
--> chain[ 9](0x24bbd60a)
--> chain[10](0x5475103d)
bucket[ 6](12) --> chain[11](0xb54a3769)
bucket[ 7](13) --> chain[12](0x914347a7)
bucket[ 8](14) --> chain[13](0xed70d193)
bucket[ 9](15) --> chain[14](0xf5e616f2)
--> chain[15](0x3cbc6423)
bucket[10](17) --> chain[16](0x7858de49)
bucket[11](18) --> chain[17](0xb1df6b97)
bucket[12](19) --> chain[18](0x1ceb853a)
--> chain[19](0xa0cbc62f)
bucket[13](21) --> chain[20](0xb23c806b)
bucket[14](22) --> chain[21](0x7c8ad2ef)
bucket[15](23) --> chain[22](0x866d3a46)
--> chain[23](0xd39ad3c)
--> chain[24](0x9fd7b9dc)
--> chain[25](0x9f28436b)
bucket[16](27) --> chain[26](0xf01494a8)
--> chain[27](0xf66c3dd4)
--> chain[28](0x884601eb)从打印信息中可知，SYSV散列算法打印的符号的顺序与通过执行readelf命令打印的顺序不一致，这是因为这个例子中所使用的符号的顺序已经是GNU散列算法排序之后的，但从中更能看出同一槽位的符号是先进后出的。
以链表的形式打印SYSV散列算法各个符号的值，如bucket[ 0]( 3) --> chain[ 3]( 1) --> chain[ 1]( 0)，bucket[ 0]、chain[ 3]和chain[ 1]表示元素的位置，其后小括号中的数字就是该位置中的值。bucket[ 9]中没有元素，每个链表都以0值为结尾。可以看出，它们是通过上一个位置的值来确定一下位置的。
打印GNU散列算法中所有槽数据和链数据的值，如bucket[ 9](15) --> chain[14](0xf5e616f2) --> chain[15](0x3cbc6423)，bucket[ 9]、chain[14]和chain[15]表示元素的位置，其后小括号中的数字就是该位置中的值。其中，chain[14]和chain[15]可以看作一个数组，bucket[ 9]中的值可以索引到该数组的头元素（即chain[14]），chain[15]中的值的最后比特位可以确认它是该数组的最后一个元素。如下图所示：
图中红字的散列值表示的是该数组的最后一个元素。
3、SYSV和GNU散列算法的直方图
执行readelf可获得散列算法的直方图，如下所示：
$ readelf -I tanglinux
Histogram for bucket list length (total of 3 buckets):
Length Number % of total Coverage
0 1 ( 33.3%)
1 2 ( 66.7%) 100.0%
Histogram for `.gnu.hash' bucket list length (total of 2 buckets):
Length Number % of total Coverage
0 1 ( 50.0%)
1 1 ( 50.0%) 100.0%
Number列所有数字相加即等于槽的数量。每行表示有Length个链元素的槽有多少个，所以每行Length和Number的值相乘，然后所有行相加则可得链的数量。.gnu.hash的直方图能准确反应这种关系。通过直方图可以了解散列算法均匀分布的状况。
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
