[ELF] Add ability to get a symbol by name from the GNU_HASH table section

[jhuber6]

Summary

The SHT_GNU_HASH section contains information used to identify symbols
using only their name. Previous support was added for the sys-V hash
table section. This patch expands this support to apply to the GNU hash
table as well. So now this function works with both hash table methods.
Implementation derived from description at
https://flapenguin.me/elf-dt-gnu-hash.

Depends on D132696

[jhuber6]

This implements the GNU support that @MaskRay wanted. I would heavily prefer supporting both as is done in this patch.

[jhenderson]

I was going to start reviewing this, and made a couple of initial nitpick comments (there will be more if I come back to this), but if the patch series gets abandoned due to @MaskRay's opposition, there's little point in me wasting the time on the review, so I'll hold off for a while.

llvm/include/llvm/Object/ELF.h

537

From a pure readability perspective, it might be worth breaking the two "modes" of this function (SHT_GNU_HASH vs SHT_HASH) into helper functions. This function is otherwise getting quite long and half of it is irrelevant to any given usage.

llvm/unittests/Object/ELFObjectFileTest.cpp

945–947

Nit: This should be fixed in the prerequisite patch.

[jhuber6]

Abandoning this patch as its functionality has been moved into D131309. This loses us the test coverage, but it passed the suite here so we can conclude it was correctly implemented.

llvm/include/llvm/Object/ELF.h

return createError("unable to get symbol from section " +
                        ": invalid symbol index (" + Twine(Index) + ")");
   return &Symbols[Index];
 }
 
 template <class ELFT>
 Expected<const typename ELFT::Sym *>
 ELFFile<ELFT>::getSymbolFromHashTable(const Elf_Shdr &Sec,
                                       StringRef Name) const {
-  if (Sec.sh_type != ELF::SHT_HASH)
-    return createError("invalid sh_type for hash table, expected SHT_HASH");
+  if (Sec.sh_type != ELF::SHT_HASH && Sec.sh_type != ELF::SHT_GNU_HASH)
+    return createError(
+        "invalid sh_type for hash table, expected SHT_HASH or SHT_GNU_HASH");
   Expected<Elf_Shdr_Range> SectionsOrError = sections();
   if (!SectionsOrError)
     return SectionsOrError.takeError();
 
   auto SymTabOrErr = object::getSection<ELFT>(*SectionsOrError, Sec.sh_link);
   if (!SymTabOrErr)
     return SymTabOrErr.takeError();
 
   auto StrTabOrErr = getStringTableForSymtab(**SymTabOrErr, *SectionsOrError);
   if (!StrTabOrErr)
     return StrTabOrErr.takeError();
   StringRef StrTab = *StrTabOrErr;
 
   auto SymsOrErr = symbols(*SymTabOrErr);
   if (!SymsOrErr)
     return SymsOrErr.takeError();
   ArrayRef<Elf_Sym> SymTab = *SymsOrErr;
 
   const Elf_Hash *HashTab =
       reinterpret_cast<const Elf_Hash *>(base() + Sec.sh_offset);
 
   if (Sec.sh_offset + Sec.sh_size >= Buf.size())
     return createError("section " + getSecIndexForError(*this, Sec) +
                        " has invalid sh_offset: " + Twine(Sec.sh_offset));
   if (Sec.sh_size < sizeof(Elf_Hash) ||
       Sec.sh_size < sizeof(Elf_Hash) + sizeof(Elf_Word) * HashTab->nbucket +
                         sizeof(Elf_Word) * HashTab->nchain)
     return createError("section " + getSecIndexForError(*this, Sec) +
                        " has invalid sh_size: " + Twine(Sec.sh_size));
 
+  if (Sec.sh_type == ELF::SHT_HASH) {
+    const Elf_Hash *HashTab =
+        reinterpret_cast<const Elf_Hash *>(base() + Sec.sh_offset);
+    if (Sec.sh_offset + Sec.sh_size >= Buf.size())
+      return createError("section " + getSecIndexForError(*this, Sec) +
+                         " has invalid sh_offset: " + Twine(Sec.sh_offset));
+    if (Sec.sh_size < sizeof(Elf_Hash) ||
+        Sec.sh_size < sizeof(Elf_Hash) + sizeof(Elf_Word) * HashTab->nbucket +
+                          sizeof(Elf_Word) * HashTab->nchain)
+      return createError("section " + getSecIndexForError(*this, Sec) +
+                         " has invalid sh_size: " + Twine(Sec.sh_size));
+
     const uint32_t Hash = hashSysV(Name);
     const Elf_Word NBucket = HashTab->nbucket;
     ArrayRef<Elf_Word> Bucket = HashTab->buckets();
     ArrayRef<Elf_Word> Chain = HashTab->chains();
-
-  for (Elf_Word I = Bucket[Hash % NBucket]; I != ELF::STN_UNDEF; I = Chain[I]) {
+    for (Elf_Word I = Bucket[Hash % NBucket]; I != ELF::STN_UNDEF;
+         I = Chain[I]) {
       if (I >= SymTab.size())
-      return createError("symbol [index " + Twine(I) +
-                         "] is greater than the number of symbols: " +
-                         Twine(SymTab.size()));
+        return createError(
+            "symbol [index " + Twine(I) +
+            "] is greater than the number of symbols: " + Twine(SymTab.size()));
       if (SymTab[I].st_name >= StrTab.size())
-      return createError("symbol [index " + Twine(I) +
-                         "] has invalid st_name: " + Twine(SymTab[I].st_name));
+        return createError(
+            "symbol [index " + Twine(I) +
 
       if (StrTab.drop_front(SymTab[I].st_name).data() == Name)
         return &SymTab[I];
     }
+  } else if (Sec.sh_type == ELF::SHT_GNU_HASH) {
+    const Elf_GnuHash *HashTab =
+        reinterpret_cast<const Elf_GnuHash *>(base() + Sec.sh_offset);
+    if (Sec.sh_offset + Sec.sh_size >= Buf.size())
+      return createError("section " + getSecIndexForError(*this, Sec) +
+                         " has invalid sh_offset: " + Twine(Sec.sh_offset));
+    if (Sec.sh_size < sizeof(Elf_GnuHash) ||
+        Sec.sh_size < sizeof(Elf_GnuHash) +
+                          sizeof(Elf_Word) * HashTab->maskwords +
+                          sizeof(Elf_Word) * HashTab->nbuckets +
+                          sizeof(Elf_Word) * (SymTab.size() - HashTab->symndx))
+      return createError("section " + getSecIndexForError(*this, Sec) +
+                         " has invalid sh_size: " + Twine(Sec.sh_size));
+
+    const uint32_t NameHash = hashGnu(Name);
+    const Elf_Word NBucket = HashTab->nbuckets;
+    const Elf_Word SymOffset = HashTab->symndx;
+    ArrayRef<Elf_Off> Filter = HashTab->filter();
+    ArrayRef<Elf_Word> Bucket = HashTab->buckets();
+    ArrayRef<Elf_Word> Chain = HashTab->values(SymTab.size());
+
+    // Check the bloom filter and exit early if the symbol is not present.
+    uint64_t ElfClassBits = ELFT::Is64Bits ? 64 : 32;
+    Elf_Off Word = Filter[(NameHash / ElfClassBits) % HashTab->maskwords];
+    uint64_t Mask = (0x1ull << (NameHash % ElfClassBits)) |
+                    (0x1ull << ((NameHash >> HashTab->shift2) % ElfClassBits));
+    if ((Word & Mask) != Mask)
+      return nullptr;
+
+    for (Elf_Word I = Bucket[NameHash % NBucket];
+         I >= SymOffset && I < SymTab.size(); I = I + 1) {
+      const uint32_t ChainHash = Chain[I - SymOffset];
+
+      if ((NameHash | 0x1) != (ChainHash | 0x1))
+        continue;
+
+      if (SymTab[I].st_name >= StrTab.size())
+        return createError(
+            "symbol [index " + Twine(I) +
+            "] has invalid st_name: " + Twine(SymTab[I].st_name));
+      if (StrTab.drop_front(SymTab[I].st_name).data() == Name)
+        return &SymTab[I];
+
+      if (ChainHash & 0x1)
+        break;
+    }
+  }
 
   return nullptr;
 }
 
 template <class ELFT>
 template <typename T>
 Expected<ArrayRef<T>>
 ELFFile<ELFT>::getSectionContentsAsArray(const Elf_Shdr &Sec) const {

llvm/unittests/Object/ELFObjectFileTest.cpp

)");
   auto MissingOrErr = Elf.getSymbolFromHashTable(**HashOrErr, "not_in_object");
   ASSERT_THAT_EXPECTED(MissingOrErr, Succeeded());
   ASSERT_TRUE(!*MissingOrErr);
 
   // Check that we return an error if the section is not ST_HASH.
   auto SymOrErr = Elf.getSymbolFromHashTable(**StrTabOrErr, "x");
   EXPECT_THAT_EXPECTED(
       SymOrErr,
-      FailedWithMessage("invalid sh_type for hash table, expected SHT_HASH"));
+      FailedWithMessage(
+          "invalid sh_type for hash table, expected SHT_HASH or SHT_GNU_HASH"));
 }
 
 // Test for getSymbolFromHashTable: check that it fails with an invalid offset.
 TEST(ELFObjectFileTest, SymbolFromHashTableTestOffset) {
   SmallString<0> Storage;
   Expected<ELFObjectFile<ELF64LE>> ElfOrErr = toBinary<ELF64LE>(Storage, R"(
 --- !ELF
 FileHeader:
)");
   const ELFFile<ELF64LE> &Elf = ElfOrErr->getELFFile();
 
   auto HashOrErr = Elf.getSection(/*SHT_HASH=*/1);
   ASSERT_THAT_EXPECTED(HashOrErr, Succeeded());
 
   auto SymOrErr = Elf.getSymbolFromHashTable(**HashOrErr, "x");
   EXPECT_THAT_EXPECTED(
       SymOrErr,
-      FailedWithMessage("section [index 2] has a sh_offset (0x270f) + sh_size (0x18) that is greater than the file size (0x218)"));
+      FailedWithMessage("section [index 2] has a sh_offset (0x270f) + sh_size "
+                        "(0x18) that is greater than the file size (0x218)"));
 }
 
 // Test for getSymbolFromHashTable: check that it fails with an invalid size.
 TEST(ELFObjectFileTest, SymbolFromHashTableTestSize) {
   SmallString<0> Storage;
   Expected<ELFObjectFile<ELF64LE>> ElfOrErr = toBinary<ELF64LE>(Storage, R"(
 --- !ELF
 FileHeader:
   Class:           ELFCLASS64
)");
 
   // Mutate this directly, otherwise it would fail to parse the ELF above.
   const_cast<typename ELF64LE::Ehdr *>(&Elf.getHeader())->e_shoff = 9999;
   auto SymOrErr = Elf.getSymbolFromHashTable(**HashOrErr, "x");
   EXPECT_THAT_EXPECTED(SymOrErr,
                        FailedWithMessage("section header table goes past the "
                                          "end of the file: e_shoff = 0x270f"));
 }
+
+// Test for getSymbolFromHashTable: check that it returns the expected symbol
+// using its associated name using the GNU_HASH table.
+TEST(ELFObjectFileTest, SymbolFromGnuHashTableTest) {
+  SmallString<0> Storage;
+  Expected<ELFObjectFile<ELF64LE>> ElfOrErr = toBinary<ELF64LE>(Storage, R"(
+--- !ELF
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_DYN
+Sections:
+  - Name:            .gnu.hash
+    Type:            SHT_GNU_HASH
+    Link:            .dynsym
+    Header:
+      SymNdx:          0x1
+      Shift2:          0x1A
+    BloomFilter:     [ 0xE0000001 ]
+    HashBuckets:     [ 0x1 ]
+    HashValues:      [ 0x2B61C, 0x2B61E, 0x2B61F ]
+  - Name:            .dynsym
+    Type:            SHT_DYNSYM
+    Link:            .dynstr
+  - Name:            .dynstr
+    Type:            SHT_STRTAB
+DynamicSymbols:
+  - Name:            x
+    Index:           SHN_ABS
+    Value:           0x0
+  - Name:            y
+    Index:           SHN_ABS
+    Value:           0x1
+  - Name:            z
+    Index:           SHN_ABS
+    Value:           0x3
+)");
+
+  ASSERT_THAT_EXPECTED(ElfOrErr, Succeeded());
+  const ELFFile<ELF64LE> &Elf = ElfOrErr->getELFFile();
+
+  auto HashOrErr = Elf.getSection(/*SHT_GNU_HASH=*/1);
+  ASSERT_THAT_EXPECTED(HashOrErr, Succeeded());
+
+  auto StrTabOrErr = Elf.getSection(/*SHT_STRTAB=*/3);
+  ASSERT_THAT_EXPECTED(StrTabOrErr, Succeeded());
+  auto ContentsOrErr = Elf.getSectionContentsAsArray<char>(**StrTabOrErr);
+  ASSERT_THAT_EXPECTED(ContentsOrErr, Succeeded());
+  StringRef StrTab(ContentsOrErr->begin(), ContentsOrErr->size());
+
+  for (StringRef SymbolName : {"x", "y", "z"}) {
+    auto SymOrErr = Elf.getSymbolFromHashTable(**HashOrErr, SymbolName);
+    ASSERT_THAT_EXPECTED(SymOrErr, Succeeded());
+    ASSERT_TRUE(*SymOrErr);
+    auto FoundSymNameOrErr = (*SymOrErr)->getName(StrTab);
+    ASSERT_THAT_EXPECTED(FoundSymNameOrErr, Succeeded());
+    ASSERT_TRUE(*FoundSymNameOrErr == SymbolName);
+  }
+
+  for (StringRef SymbolName : {"a", "b", "c", "d", "e", "f", "g", "h", "i"}) {
+    auto MissingOrErr = Elf.getSymbolFromHashTable(**HashOrErr, SymbolName);
+    ASSERT_THAT_EXPECTED(MissingOrErr, Succeeded());
+    ASSERT_TRUE(!*MissingOrErr);
+  }
+
+  const_cast<typename ELF64LE::Shdr *>(*HashOrErr)->sh_size = 17;
+  auto SymOrErr = Elf.getSymbolFromHashTable(**HashOrErr, "x");
+  EXPECT_THAT_EXPECTED(
+      SymOrErr, FailedWithMessage("section [index 1] has invalid sh_size: 17"));
+}
+
+// Test for getSymbolFromHashTable: check that it returns the expected symbol
+// using its associated name using the GNU_HASH table with a 32-bit bloom
+// filter.
+TEST(ELFObjectFileTest, SymbolFromGnuHashTableTest32) {
+  SmallString<0> Storage;
+  Expected<ELFObjectFile<ELF32LE>> ElfOrErr = toBinary<ELF32LE>(Storage, R"(
+--- !ELF
+FileHeader:
+  Class:           ELFCLASS32
+  Data:            ELFDATA2LSB
+  Type:            ET_DYN
+Sections:
+  - Name:            .gnu.hash
+    Type:            SHT_GNU_HASH
+    Link:            .dynsym
+    Header:
+      SymNdx:          0x1
+      Shift2:          0x1A
+    BloomFilter:     [ 0xE0000001 ]
+    HashBuckets:     [ 0x1 ]
+    HashValues:      [ 0x2B61C, 0x2B61E, 0x2B61F ]
+  - Name:            .dynsym
+    Type:            SHT_DYNSYM
+    Link:            .dynstr
+  - Name:            .dynstr
+    Type:            SHT_STRTAB
+DynamicSymbols:
+  - Name:            x
+    Index:           SHN_ABS
+    Value:           0x0
+  - Name:            y
+    Index:           SHN_ABS
+    Value:           0x1
+  - Name:            z
+    Index:           SHN_ABS
+    Value:           0x3
+)");
+
+  ASSERT_THAT_EXPECTED(ElfOrErr, Succeeded());
+  const ELFFile<ELF32LE> &Elf = ElfOrErr->getELFFile();
+
+  auto HashOrErr = Elf.getSection(/*SHT_GNU_HASH=*/1);
+  ASSERT_THAT_EXPECTED(HashOrErr, Succeeded());
+
+  auto StrTabOrErr = Elf.getSection(/*SHT_STRTAB=*/3);
+  ASSERT_THAT_EXPECTED(StrTabOrErr, Succeeded());
+  auto ContentsOrErr = Elf.getSectionContentsAsArray<char>(**StrTabOrErr);
+  ASSERT_THAT_EXPECTED(ContentsOrErr, Succeeded());
+  StringRef StrTab(ContentsOrErr->begin(), ContentsOrErr->size());
+
+  for (StringRef SymbolName : {"a", "b", "c", "d", "e", "f", "g", "h", "i"}) {
+    auto MissingOrErr = Elf.getSymbolFromHashTable(**HashOrErr, SymbolName);
+    ASSERT_THAT_EXPECTED(MissingOrErr, Succeeded());
+    ASSERT_TRUE(!*MissingOrErr);
+  }
+}