ELF 动态链接中的符号查找

概述

在程序进行动态链接的时候，需要通过符号名字进行符号的查找。ELF 动态链接库中，动态链接所需的符号（动态符号）及字符串位于 .dynsym 节(section)和 .dynstr 节中，可以通过动态节(Dynamic Section)获取地址。由于这些节都位于需要被加载到内存的段(segment)中，因此 ELF 被映射到内存后即可直接从内存中访问动态符号的信息。

在加载 ELF 后，ELF 基址指向的就是 ELF Header （这也是 ELF 文件头部），其中包含程序头表(Program Header Table) 地址，而动态节的地址偏移可以从程序头表中获得(类型为 PT_DYNAMIC)。其中动态符号表(.dynsym)偏移的类型为 DT_SYMTAB ，字符串表(.dynstr)偏移类型为 DT_STRTAB 。

查找符号即通过符号名字，找到其在动态符号表的位置的过程。这个位置可能是 0 ，表示没有找到符号。动态符号表的第 0 个符号一般不表示任何实际的符号(类型是 NOTYPE ，value 是 0)，可以认为是逻辑上的 NULL 。

由于 ELF 中可能包含大量的动态符号，为了加快查找速度，可以使用预先制作好的 hash 表，以空间换时间提高效率。有两种被广泛使用的 hash 方式，即 ELF hash 和 GNU hash 。下面我们借助 Android Bionic Linker 源码理解通过这两种 hash 方式查找符号的方法和原理。

ELF hash

ELF hash 是相对简单的方法。它使用将符号按照名字的 hash 分散到若干桶中，并用链表解决冲突的问题。

hash 信息包含在 .hash 节中（SHT_HASH），通过动态节表可以访问(类型为 DT_HASH)。

可以使用 -Wl,--hash-style=sysv 编译出使用 elf hash 的 elf 。

hash 节开头包含两个长度，即桶(bucket)长和链(chain)长，它们都是 uint32 ，随后依次是 bucket 和 chain 数组

// https://cs.android.com/android/platform/superproject/main/+/main:bionic/linker/linker_soinfo.h;l=191;drc=2a901e69373c09d5563a5c0a24a3083ff7f6808a
  size_t nbucket_;
  size_t nchain_;
  uint32_t* bucket_;
  uint32_t* chain_;
// https://cs.android.com/android/platform/superproject/main/+/main:bionic/linker/linker.cpp;l=2893;drc=f5e21d931c2d3c25af7be54bfa6e2d708c4c9f96
      case DT_HASH:
        nbucket_ = reinterpret_cast<uint32_t*>(load_bias + d->d_un.d_ptr)[0];
        nchain_ = reinterpret_cast<uint32_t*>(load_bias + d->d_un.d_ptr)[1];
        bucket_ = reinterpret_cast<uint32_t*>(load_bias + d->d_un.d_ptr + 8);
        chain_ = reinterpret_cast<uint32_t*>(load_bias + d->d_un.d_ptr + 8 + nbucket_ * 4);
        break;

elf hash 通过以下算法计算：

// https://cs.android.com/android/platform/superproject/main/+/main:bionic/linker/linker_soinfo.cpp;l=880;drc=9fb81ab49413b5751c857479c908f6607e029f3b
uint32_t calculate_elf_hash(const char* name) {
  const uint8_t* name_bytes = reinterpret_cast<const uint8_t*>(name);
  uint32_t h = 0, g;

  while (*name_bytes) {
    h = (h << 4) + *name_bytes++;
    g = h & 0xf0000000;
    h ^= g;
    h ^= g >> 24;
  }

  return h;
}

这个算法根据符号名字计算 hash ，最终得到最多 28 位的 hash ，算法确保 hash 结果与每一位相关。

通过 elf hash 进行查找的简化代码如下：

// https://cs.android.com/android/platform/superproject/main/+/main:bionic/linker/linker_soinfo.cpp;l=352;drc=9fb81ab49413b5751c857479c908f6607e029f3b
const ElfW(Sym)* soinfo::elf_lookup(SymbolName& symbol_name, const version_info* vi) const {
  uint32_t hash = symbol_name.elf_hash();

  for (uint32_t n = bucket_[hash % nbucket_]; n != 0; n = chain_[n]) {
    ElfW(Sym)* s = symtab_ + n;

    if (strcmp(get_string(s->st_name), symbol_name.get_name()) == 0) {
      return symtab_ + n;
    }
  }

  return nullptr;
}

简单来说，通过符号名字 hash 除以桶长的余数确定符号位于哪个桶，bucket 数组中每一个元素都是符号在动态符号表的 index ，即冲突链的开始，而 chain 数组与动态符号表的长度相等，每一个元素指向所在桶的冲突链的下一个符号的 index ，这样遍历整个冲突链，找到符号名字相等的那个符号即可。

GNU hash

GNU hash 相比 ELF hash 更为复杂，但也具有更快的速度。

GNU hash 的信息位于 .gnu.hash 节(SHT_GNU_HASH)中，动态节表的类型为 DT_GNU_HASH 。

由于它使用 bloom filter 更快地过滤不属于符号表的内容，因此 gnu hash 的结构更加复杂，具体如下表（内容是紧密排列的）：

名字	类型和大小	说明
gnu_nbucket	(uint32)4	桶大小
symndx	(uint32)4	可以使用 gnu hash 查找的符号的最小 index ，即内部（未 gnu hash 的）符号的个数。内部符号一般是导入符号和第 0 个符号(NULL)
gnu_maskwords	(uint32)4	bloom filter words （桶）的个数
gnu_shift2	(uint32)4	用于计算 bloom filter 第二个测试位的偏移
gnu_bloom_filter	(ElfW(Addr)[])gnu_maskwords*sizeof(uintptr)	bloom filter words 桶数组
gnu_bucket	(uint32[])gnu_nbucket*4	hash 桶数组，长度为 gnu_nbucket
gnu_chain	(uint32[])symbols_count-symndx	冲突链表，与可用符号的长度相等，值为每个符号的 hash （最低位为结束符）

linker 中解析的代码如下：

// https://cs.android.com/android/platform/superproject/main/+/main:bionic/linker/linker.cpp;l=2900;drc=f5e21d931c2d3c25af7be54bfa6e2d708c4c9f96
      case DT_GNU_HASH:
        gnu_nbucket_ = reinterpret_cast<uint32_t*>(load_bias + d->d_un.d_ptr)[0];
        // skip symndx
        gnu_maskwords_ = reinterpret_cast<uint32_t*>(load_bias + d->d_un.d_ptr)[2];
        gnu_shift2_ = reinterpret_cast<uint32_t*>(load_bias + d->d_un.d_ptr)[3];

        gnu_bloom_filter_ = reinterpret_cast<ElfW(Addr)*>(load_bias + d->d_un.d_ptr + 16);
        gnu_bucket_ = reinterpret_cast<uint32_t*>(gnu_bloom_filter_ + gnu_maskwords_);
        // amend chain for symndx = header[1]
        gnu_chain_ = gnu_bucket_ + gnu_nbucket_ -
            reinterpret_cast<uint32_t*>(load_bias + d->d_un.d_ptr)[1];

        if (!powerof2(gnu_maskwords_)) {
          DL_ERR("invalid maskwords for gnu_hash = 0x%x, in \"%s\" expecting power to two",
              gnu_maskwords_, get_realpath());
          return false;
        }
        --gnu_maskwords_;

        flags_ |= FLAG_GNU_HASH;
        break;

gnu hash 的算法：

// https://cs.android.com/android/platform/superproject/main/+/main:bionic/linker/linker_gnu_hash.h;l=46;drc=339ecef22d17748ae7c289d974a59b97484f6896
static std::pair<uint32_t, uint32_t> calculate_gnu_hash_simple(const char* name) {
  uint32_t h = 5381;
  const uint8_t* name_bytes = reinterpret_cast<const uint8_t*>(name);
  #pragma unroll 8
  while (*name_bytes != 0) {
    h += (h << 5) + *name_bytes++; // h*33 + c = h + h * 32 + c = h + h << 5 + c
  }
  return { h, reinterpret_cast<const char*>(name_bytes) - name };
}

以下是 gnu hash 查找符号的简化代码：

// https://cs.android.com/android/platform/superproject/main/+/main:bionic/linker/linker_soinfo.cpp;l=312;drc=9fb81ab49413b5751c857479c908f6607e029f3b
const ElfW(Sym)* soinfo::gnu_lookup(SymbolName& symbol_name, const version_info* vi) const {
  const uint32_t hash = symbol_name.gnu_hash();

  constexpr uint32_t kBloomMaskBits = sizeof(ElfW(Addr)) * 8;
  const uint32_t word_num = (hash / kBloomMaskBits) & gnu_maskwords_;
  const ElfW(Addr) bloom_word = gnu_bloom_filter_[word_num];
  const uint32_t h1 = hash % kBloomMaskBits;
  const uint32_t h2 = (hash >> gnu_shift2_) % kBloomMaskBits;

  // test against bloom filter
  if ((1 & (bloom_word >> h1) & (bloom_word >> h2)) == 0) {
    return nullptr;
  }

  // bloom test says "probably yes"...
  uint32_t n = gnu_bucket_[hash % gnu_nbucket_];

  if (n == 0) {
    return nullptr;
  }

  do {
    ElfW(Sym)* s = symtab_ + n;
    if (((gnu_chain_[n] ^ hash) >> 1) == 0 &&
        strcmp(get_string(s->st_name), symbol_name.get_name()) == 0) {
      return symtab_ + n;
    }
  } while ((gnu_chain_[n++] & 1) == 0);

  return nullptr;
}

gnu hash 会被按照位分为几个部分用于接下来的查找，如下表（表中第一个元素从第 0 位开始）：

名字	位长度	说明
h1	log2(kBloomMaskBits)	用于 bloom filter 的第一个位位置，通过 hash & kBloomMaskBits 取得。范围为 [0,处理器位长)，这是因为 bloom filter 数组的元素长度为处理器位长。
word_num	log2(maskwords)	指向 bloom_filter 数组的 index ，因此取值范围为 [0,maskwords)
未使用		+shift2
h2	log2(kBloomMaskBits)	用于 bloom filter 的第二个位位置，通过 (hash >> shift2) & kBloomMaskBits 取得。
未使用	剩余长度	未使用

gnu hash 通过 bloom filter 来测试一个符号是否可能存在于符号表。它也利用了 hash 桶的思想，选取 hash 中一段作为桶编号(word_num)，将符号分散到不同的 bloom filter words 桶中。又选取 hash 的另外两段作为两个测试比特位的位置(h1, h2)，检查对应 bloom filter word 的位置是否都置位，如果都置位则认为符号可能存在，否则排除。一般来说，bloom filter 桶的长度(即 maskwords)是 2 的幂，在之前的代码中已经检查了这一点。需要注意，bloom filter 只保证被排除的一定是不存在的，而未被排除的可能存在也可能不存在，但是不存在的概率就会小很多。

如果符号通过了 bloom filter 测试，则进行进一步查找，这里类似 ELF hash ，使用 hash % gnu_nbucket 计算桶编号，然后在冲突链表中查询，找到名字相等的那个符号。但是这里的冲突链表和 ELF hash 有些不一样，它实际上是一个顺序表，gnu_bucket 指向对应桶的冲突表的头部的 index （或者 0 ，如果桶中没有元素），这个 index 实际上是动态符号表的 index ，也是 gnu_chain 的 index （修正后 ^1）。这样只需要从这个头部 index 开始按顺序访问之后的元素即可遍历链表，这样每次迭代省去了一次访存操作（index 自增在寄存器中完成，无需从内存中获取下一个结点的地址）。冲突链的元素值是符号的 hash （除去最低位），而最低位表示该桶的冲突链是否结束（1 表示结束），利用最低位可以判断是否需要停止迭代，借助 hash 还可以快速判断是否是需要查找的符号，省去比较字符串的时间。

^1: gnu_chain 本来应该紧跟在 gnu_bucket 后，但是由于 chain 不含内部符号，因此给这个地址赋值的时候减去 symndx 修正，这样就可以通过 gnu_chain_ + index 访问对应 index 的 hash 了。

// amend chain for symndx = header[1]
gnu_chain_ = gnu_bucket_ + gnu_nbucket_ -
    reinterpret_cast<uint32_t*>(load_bias + d->d_un.d_ptr)[1];

为了使用 gnu hash ，动态符号表需要按照特定的顺序存放符号，即：

1. 内部符号（NULL 及导入符号）由于不可 gnu hash ，因此总是位于符号表前端（即 symndx 之前）
2. 剩下的符号必须按照桶编号排序。

GNU Hash 优化的意义

比起 ELF Hash ，GNU Hash 更加复杂，首先它使用 bloom filter 来快速拒绝可能失败的查找，并且通过按照桶编号顺序排列符号优化访存次数。这样做的目的是什么呢？

我们知道 Linux 的动态链接中，导入符号可以来自任意一个动态库，一般来说会从其声明的依赖的动态库中查找，所以一个符号会在不同的动态库中进行查找，直到找到为止，因此查找失败是常见的。

如果使用 ELF Hash ，则桶编号碰撞的概率取决于桶个数(1/nbucket) ，而桶个数一般随着符号个数增多而增加；随着符号数量增加，碰撞概率越大，因此不存在的符号的桶编号存在的概率也越大，这样就会导致额外的访存，降低效率。

而 GNU Hash 使用了 bloom filter 的思想，并且充分利用了 hash 的信息（使用更多位而非取余），进一步降低了碰撞概率。我们假定 hash 的每一位都是独立的均匀分布，则单个测试位碰撞的概率是 p=1/(gnu_maskwords*kBloomMaskBits) ，两个测试位都碰撞的概率就是 p^2 ，一般 maskwords 取决于符号个数， kBloomMaskBits 是处理器位长，在同等符号个数情况下，GNU Hash 使用 bloom filter 的碰撞概率比 ELF Hash 直接对 hash 取余小得多，这样可以将大多数不存在的符号排除在外，而按照桶编号顺序存放符号也避免了链表的多次访存。总之，使用 GNU Hash 能够大大提高动态链接的效率。

实例

以系统 libc 为例，观察动态符号表：

$ readelf -s /system/lib64/libc.so -W | head -n 50

Symbol table '.dynsym' contains 1457 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND dlsym@LIBC (14)
     2: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND dlopen@LIBC (14)
     3: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND dlerror@LIBC (14)
     4: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND android_dlopen_ext@LIBC (14)
     5: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND dlclose@LIBC (14)
     6: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND __loader_shared_globals
     7: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND dladdr@LIBC (14)
     8: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND android_get_application_target_sdk_version@LIBC_N (15)
     9: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __loader_add_thread_local_dtor
    10: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __loader_remove_thread_local_dtor
    11: 0000000000000000     0 FUNC    GLOBAL DEFAULT  UND dl_iterate_phdr@LIBC (14)
    12: 0000000000000000     0 FUNC    WEAK   DEFAULT  UND __loader_android_get_exported_namespace
    13: 00000000000a921c    92 FUNC    GLOBAL DEFAULT   15 mtx_unlock@@LIBC_R
    14: 00000000000e81e0    28 FUNC    GLOBAL DEFAULT   15 setpriority@@LIBC
    15: 00000000000e8660    28 FUNC    GLOBAL DEFAULT   15 munlockall@@LIBC
    16: 00000000000fdfac    48 FUNC    GLOBAL DEFAULT   15 pthread_mutexattr_setprotocol@@LIBC_P
    17: 0000000000096d3c    32 FUNC    GLOBAL DEFAULT   15 isalnum@@LIBC
    18: 00000000000b9454    12 FUNC    GLOBAL DEFAULT   15 __dn_comp@@LIBC

读取 gnu hash section 可知：

$ objdump -s /system/lib64/libc.so | grep .gnu.hash -A 10
Contents of section .gnu.hash:
 9908 69010000 0d000000 00020000 1a000000  i...............

gnu_nbucket=0x169=361
symndx=0x0d=13
gnu_maskwords=0x200
gnu_shift2=0x1a=26

可见 symndx=13 ，在这之前是导入符号，之后是导出符号。

使用以下 python 程序计算 gnu hash 和桶编号，可以发现符号 num (index) 是按照桶编号递增的：

def gnuhash(s: bytes):
  r = 5381
  for b in s:
    r = ((r * 33) + b) & 0xffffffff
  return r

gnu_nbucket = 0x169
h = gnuhash(b'mtx_unlock'); print(hex(h), h % gnu_nbucket)
h = gnuhash(b'setpriority'); print(hex(h), h % gnu_nbucket)
h = gnuhash(b'munlockall'); print(hex(h), h % gnu_nbucket)
h = gnuhash(b'pthread_mutexattr_setprotocol'); print(hex(h), h % gnu_nbucket)
h = gnuhash(b'isalnum'); print(hex(h), h % gnu_nbucket)
h = gnuhash(b'__dn_comp'); print(hex(h), h % gnu_nbucket)

0x1f386b29 0
0xd5e07633 0
0x3310d917 0
0xe4d80f7 1
0xa9bc2e1e 2
0xf1fef223 2

看到 gnu_chain ，偏移为 +16+gnu_maskwords*8+gnu_nbucket*4 即 0x9908+16+0x200*8+0x169*4=0xaebc

可以发现，中括号开始后即第 0 个可用符号（第 13 个符号）的 hash ，除了最低位为 0 其余位都和 hash 相等，其他符号的 hash 除了第零位也分别相等。前三个符号都属于 0 号桶的冲突链，只有最后一个符号的 hash 最低位是 1 ，表示冲突链结束，其余最低位为 0 ，表示冲突链未结束。

aeb8 ae050000[286b381f 3276e0d5 17d91033  ....(k8.2v.....3
aec8 f7804d0e 1e2ebca9 22f2fef1]1e1641a0  ..M.....".....A.
aed8 adb9724d 82dfb394 49b441ff 921c8641  ..rM....I.A....A

线性查找

实际上，动态符号也可以通过线性的方式查找，即通过遍历整个动态符号表，对比符号字符串是否与要查找的相等。

然而这种方法效率极低，并且所需的关键信息即动态符号表长度（或符号个数），仅存在于 section table 中，而不存在于动态段中。由于 section table 不会被加载到内存，因此获取长度需要额外的操作。因此实际上动态链接器进行符号查找都是使用上述两种 hash 方式，而不使用线性查找。线性查找仅用于 readelf 这样的解析 elf 文件的工具中。

显然两种 elf hash 都包含了符号个数的信息，因此解析这些信息自然可用于线性查找，但是这样做对于动态链接来说意义何在呢？

由于 elf hash 节中包含链长，因此容易得知动态符号的个数就是链的长度。那么，请读者思考：如何仅通过 gnu hash 节的信息得知动态符号的个数？

参考答案

找编号最大的包含冲突链的 bucket ，遍历其冲突链得到最大的 index ，加上 symndx+1 即可