[elfabi] Add support for reading dynamic symbols from binaries

[amontanez]

Summary

This patch adds initial support for reading dynamic symbols from ELF binaries. Currently, STT_NOTYPE, STT_OBJECT, STT_FUNC, and STT_TLS are explicitly supported. Other symbol types are mapped to ELFSymbolType::Unknown to improve signal/noise ratio.

Symbols must meet two criteria to be read into in an ELFStub:

• The symbol's binding must be STB_GLOBAL or STB_WEAK.
• The symbol's visibility must be STV_DEFAULT or STV_PROTECTED.

This filters out symbols that aren't of interest during compile-time linking against a shared object.

This change uses DT_HASH and DT_GNU_HASH to determine the size of .dynsym. Using hash tables to determine the number of symbols in .dynsym allows llvm-elfabi to work on binaries without relying on section headers.

[amontanez]

Now uses DT_HASH and DT_GNU_HASH to determine the size of .dynsym. A number of tests still need to be updated as this change requires that a DT_SYMTAB entry exists in the .dynamic section (which many tests are missing).

[jakehehrlich]

llvm/tools/llvm-elfabi/ELFObjHandler.cpp

166

Isn't this what values() is for?

195

ELFT should be inferred here.

195

i think rather than trying to be pedantic and get the largest index from both, you can just return right here.

198

I think you might consider adding ElfHash in a second patch instead.

243

Technically this gets a lot more complicated. You have a lot of special section indexes and there are there is this somewhat complicated thing for large symbol indexes that you don't need to implement now. You should check that the symbol index is below SHN_LORESERVE first. In final library form there is potential for this input from the disk to be wrong so you'll need to return an error anyhow.

Add a todo for the other things like common, abs, large indexes, etc...

269

This should just be a range based for loop.

271

There are macros to do this for I believe. Same with visibility.

[amontanez]

Addressed most of your comments, but I've left the ELF/SYSV hash table in since it amounts to 12 additional lines for now. I can pull it out later if that's really needed. I feel it's relevant and small enough to leave in.

[amontanez]

llvm/tools/llvm-elfabi/ELFObjHandler.cpp

195

I'm not fully certain why, but ELFT can't be inferred in this situation.

243

As per offline discussion, there's not really a case where any value of st_shndx other than SHN_UNDEF would make a symbol undefined.

[amontanez]

Rebase on license changes, fix behavior for edge case when a .gnu.hash section has no buckets.

[jakehehrlich]

Pending 1 nit, LGTM.

llvm/tools/llvm-elfabi/ELFObjHandler.cpp

195

I see why now, it is the "ELFT::..." You can think "::GnuHash" as acting like a function and the compiler would have to reverse that function. In fact there might not actually be a unique inverse.

There's an alternative, which is to use the underlying type that is paramterized by ELFT but this is *not* the intended surface of the ELFType library so you shouldn't do that. So this was correct as is I suppose.

275–277

This would all be nicer if populateSymbol was part of a constructor for ELFSymbol and then you could used TargetStub.Symbols.emplace(*SymName, RawSym) instead of these 3 lines.

[amontanez]

Changed populateSymbol() to createELFSymbol().

[amontanez]

llvm/tools/llvm-elfabi/ELFObjHandler.cpp

275–277

Since we can't have TextAPI rely on libObject, we can't add a constructor for ELFSymbol that uses ELFT. I've changed populateSymbol() to createELFSymbol() so this portion looks slightly better.

[amontanez]

Added dummy DT_SYMTAB entries to tests so all tests pass again.

[amontanez]

Fixed a comment that passed 80 character width limit.

llvm/test/tools/llvm-elfabi/binary-read-syms-gnu-hash.test

+# RUN: llvm-elfabi --elf %p/Inputs/gnu_hash.so --emit-tbe=- | FileCheck %s
+
+# CHECK:      --- !tapi-tbe
+# CHECK-NEXT: TbeVersion:      1.0
+# CHECK-NEXT: SoName:          libsomething.so
+# CHECK-NEXT: Arch:            x86_64
+# CHECK-NEXT: NeededLibs:
+# CHECK-NEXT:   - libm.so.6
+# CHECK-NEXT:   - libc.so.6
+# CHECK-NEXT:   - ld-linux-x86-64.so.2
+# CHECK-NEXT: Symbols:
+# CHECK-NEXT:   AGlobalInteger:  { Type: Object, Size: 4 }
+# CHECK-NEXT:   AThreadLocalLongInteger: { Type: TLS, Size: 8 }
+# CHECK-NEXT:   _ITM_deregisterTMCloneTable: { Type: NoType, Undefined: true, Weak: true }
+# CHECK-NEXT:   _ITM_registerTMCloneTable: { Type: NoType, Undefined: true, Weak: true }
+# CHECK-NEXT:   _Z11rotateArrayPii: { Type: Func }
+# CHECK-NEXT:   __cxa_finalize:  { Type: Func, Undefined: true, Weak: true }
+# CHECK-NEXT:   __gmon_start__:  { Type: NoType, Undefined: true, Weak: true }
+# CHECK-NEXT:   __tls_get_addr:  { Type: Func, Undefined: true }
+# CHECK-NEXT:   _fini:           { Type: Func }
+# CHECK-NEXT:   _init:           { Type: Func }
+# CHECK-NEXT: ...

llvm/test/tools/llvm-elfabi/binary-read-syms-sysv-hash.test

+# RUN: llvm-elfabi --elf %p/Inputs/sysv_hash.so --emit-tbe=- | FileCheck %s
+
+# CHECK:      --- !tapi-tbe
+# CHECK-NEXT: TbeVersion:      1.0
+# CHECK-NEXT: SoName:          libsomething.so
+# CHECK-NEXT: Arch:            x86_64
+# CHECK-NEXT: NeededLibs:
+# CHECK-NEXT:   - libm.so.6
+# CHECK-NEXT:   - libc.so.6
+# CHECK-NEXT:   - ld-linux-x86-64.so.2
+# CHECK-NEXT: Symbols:
+# CHECK-NEXT:   AGlobalInteger:  { Type: Object, Size: 4 }
+# CHECK-NEXT:   AThreadLocalLongInteger: { Type: TLS, Size: 8 }
+# CHECK-NEXT:   _ITM_deregisterTMCloneTable: { Type: NoType, Undefined: true, Weak: true }
+# CHECK-NEXT:   _ITM_registerTMCloneTable: { Type: NoType, Undefined: true, Weak: true }
+# CHECK-NEXT:   _Z11rotateArrayPii: { Type: Func }
+# CHECK-NEXT:   __cxa_finalize:  { Type: Func, Undefined: true, Weak: true }
+# CHECK-NEXT:   __gmon_start__:  { Type: NoType, Undefined: true, Weak: true }
+# CHECK-NEXT:   __tls_get_addr:  { Type: Func, Undefined: true }
+# CHECK-NEXT:   _fini:           { Type: Func }
+# CHECK-NEXT:   _init:           { Type: Func }
+# CHECK-NEXT: ...

llvm/tools/llvm-elfabi/ELFObjHandler.cpp

 #include "ELFObjHandler.h"
 #include "llvm/Object/Binary.h"
 #include "llvm/Object/ELFObjectFile.h"
 #include "llvm/Object/ELFTypes.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/TextAPI/ELF/ELFStub.h"
+#include <algorithm>
 
 using llvm::MemoryBufferRef;
 using llvm::object::ELFObjectFile;
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::ELF;
 
 namespace llvm {
 namespace elfabi {
 
 // Simple struct to hold relevant .dynamic entries.
 struct DynamicEntries {
   uint64_t StrTabAddr = 0;
   uint64_t StrSize = 0;
   Optional<uint64_t> SONameOffset;
   std::vector<uint64_t> NeededLibNames;
+  // Symbol table:
+  uint64_t DynSymAddr = 0;
+  // Hash tables:
+  Optional<uint64_t> ElfHash;
+  Optional<uint64_t> GnuHash;
 };
 
 /// This function behaves similarly to StringRef::substr(), but attempts to
 /// terminate the returned StringRef at the first null terminator. If no null
 /// terminator is found, an error is returned.
 ///
 /// @param Str Source string to create a substring from.
 /// @param Offset The start index of the desired substring.

 static Error populateDynamic(DynamicEntries &Dyn,
                              typename ELFT::DynRange DynTable) {
   if (DynTable.empty())
     return createError("No .dynamic section found");
 
   // Search .dynamic for relevant entries.
   bool FoundDynStr = false;
   bool FoundDynStrSz = false;
+  bool FoundDynSym = false;
   for (auto &Entry : DynTable) {
     switch (Entry.d_tag) {
     case DT_SONAME:
       Dyn.SONameOffset = Entry.d_un.d_val;
       break;
     case DT_STRTAB:
       Dyn.StrTabAddr = Entry.d_un.d_ptr;
       FoundDynStr = true;
       break;
     case DT_STRSZ:
       Dyn.StrSize = Entry.d_un.d_val;
       FoundDynStrSz = true;
       break;
     case DT_NEEDED:
       Dyn.NeededLibNames.push_back(Entry.d_un.d_val);
       break;
+    case DT_SYMTAB:
+      Dyn.DynSymAddr = Entry.d_un.d_ptr;
+      FoundDynSym = true;
+      break;
+    case DT_HASH:
+      Dyn.ElfHash = Entry.d_un.d_ptr;
+      break;
+    case DT_GNU_HASH:
+      Dyn.GnuHash = Entry.d_un.d_ptr;
     }
   }
 
   if (!FoundDynStr) {
     return createError(
         "Couldn't locate dynamic string table (no DT_STRTAB entry)");
   }
   if (!FoundDynStrSz) {
     return createError(
         "Couldn't determine dynamic string table size (no DT_STRSZ entry)");
   }
+  if (!FoundDynSym) {
+    return createError(
+        "Couldn't locate dynamic symbol table (no DT_SYMTAB entry)");
+  }
   if (Dyn.SONameOffset.hasValue() && *Dyn.SONameOffset >= Dyn.StrSize) {
     return createStringError(
         object_error::parse_failed,
         "DT_SONAME string offset (0x%016x) outside of dynamic string table",
         *Dyn.SONameOffset);
   }
   for (uint64_t Offset : Dyn.NeededLibNames) {
     if (Offset >= Dyn.StrSize) {
       return createStringError(
           object_error::parse_failed,
           "DT_NEEDED string offset (0x%016x) outside of dynamic string table",
           Offset);
     }
   }
 
   return Error::success();
 }
 
+/// This function finds the number of dynamic symbols using a GNU hash table.
+///
+/// @param Table The GNU hash table for .dynsym.
+template <class ELFT>
+static uint64_t getDynSymtabSize(const typename ELFT::GnuHash &Table) {
+  using Elf_Word = typename ELFT::Word;
+  if (Table.nbuckets == 0)
+    return 0;
+  uint64_t LastSymIdx = 0;
+  uint64_t BucketVal = 0;
+  // Find the index of the first symbol in the last chain.
+  for (Elf_Word Val : Table.buckets()) {
+    BucketVal = std::max(BucketVal, (uint64_t)Val);
+  }
+  LastSymIdx += BucketVal;
+  const Elf_Word *It =
+      reinterpret_cast<const Elf_Word *>(Table.buckets().end());
+  It += (BucketVal - Table.symndx);
+  // Locate the end of the chain to find the last symbol index.
+  while ((*It & 1) == 0) {
+    LastSymIdx++;
+    It++;
+  }
+  return LastSymIdx + 1;
+}
+
+/// This function determines the number of dynamic symbols.
+/// Without access to section headers, the number of symbols must be determined
+/// by parsing dynamic hash tables.
+///
+/// @param Dyn Entries with the locations of hash tables.
+/// @param ElfFile The ElfFile that the section contents reside in.
+template <class ELFT>
+static Expected<uint64_t> getNumSyms(DynamicEntries &Dyn,
+                                     const ELFFile<ELFT> &ElfFile) {
+  using Elf_Hash = typename ELFT::Hash;
+  using Elf_GnuHash = typename ELFT::GnuHash;
+  uint64_t Count = 0;
+  // Search GNU hash table to try to find the upper bound of dynsym.
+  if (Dyn.GnuHash.hasValue()) {
+    Expected<const uint8_t *> TablePtr = ElfFile.toMappedAddr(*Dyn.GnuHash);
+    if (!TablePtr)
+      return TablePtr.takeError();
+    const Elf_GnuHash *Table =
+        reinterpret_cast<const Elf_GnuHash *>(TablePtr.get());
+    Count = std::max(Count, getDynSymtabSize<ELFT>(*Table));
+  }
+  // Search SYSV hash table to try to find the upper bound of dynsym.
+  if (Dyn.ElfHash.hasValue()) {
+    Expected<const uint8_t *> TablePtr = ElfFile.toMappedAddr(*Dyn.ElfHash);
+    if (!TablePtr)
+      return TablePtr.takeError();
+    const Elf_Hash *Table = reinterpret_cast<const Elf_Hash *>(TablePtr.get());
+    Count = std::max(Count, (uint64_t)Table->nchain);
+  }
+  return Count;
+}
+
+/// This function extracts symbol type from a symbol's st_info member and
+/// maps it to an ELFSymbolType enum.
+/// Currently, STT_NOTYPE, STT_OBJECT, STT_FUNC, and STT_TLS are supported.
+/// Other symbol types are mapped to ELFSymbolType::Unknown.
+///
+/// @param Info Binary symbol st_info to extract symbol type from.
+static ELFSymbolType convertInfoToType(uint8_t Info) {
+  Info = Info & 0xf;
+  switch (Info) {
+    case ELF::STT_NOTYPE:
+      return ELFSymbolType::NoType;
+    case ELF::STT_OBJECT:
+      return ELFSymbolType::Object;
+    case ELF::STT_FUNC:
+      return ELFSymbolType::Func;
+    case ELF::STT_TLS:
+      return ELFSymbolType::TLS;
+    default:
+      return ELFSymbolType::Unknown;
+  }
+}
+
+/// This function populates all members of an ELFSymbol from a binary ELFT::Sym.
+///
+/// @param TargetSym ELFSymbol to populate.
+/// @param RawSym ELFT::Sym to extract symbol information from.
+template <class ELFT>
+static void populateSymbol(ELFSymbol &TargetSym,
+                           const typename ELFT::Sym &RawSym) {
+  uint8_t Binding = RawSym.st_info >> 4;
+  if (Binding == STB_WEAK)
+    TargetSym.Weak = true;
+  else
+    TargetSym.Weak = false;
+
+  if (RawSym.st_shndx == 0)
+    TargetSym.Undefined = true;
+  else
+    TargetSym.Undefined = false;
+
+  TargetSym.Type = convertInfoToType(RawSym.st_info);
+
+  if (TargetSym.Type == ELFSymbolType::Func) {
+    TargetSym.Size = 0;
+  } else {
+    TargetSym.Size = RawSym.st_size;
+  }
+}
+
+/// This function populates an ELFStub with symbols using information read
+/// from an ELF binary.
+///
+/// @param TargetStub ELFStub to add symbols to.
+/// @param DynSym Range of dynamic symbols to add to TargetStub.
+/// @param DynStr StringRef to the dynamic string table.
+template <class ELFT>
+static Error populateSymbols(ELFStub &TargetStub,
+                            const typename ELFT::SymRange DynSym,
+                            StringRef DynStr) {
+  // This loop deliberately skips the first symbol since it's the NULL symbol.
+  auto RawSym = DynSym.begin();
+  while (++RawSym < DynSym.end()) {
+    // If a symbol does not have global or weak binding, ignore it.
+    uint8_t Binding = RawSym->st_info >> 4;
+    if (!(Binding == STB_GLOBAL || Binding == STB_WEAK))
+      continue;
+    // If a symbol doesn't have default or protected visibility, ignore it.
+    uint8_t Visibility = RawSym->st_other & 0x3;
+    if (!(Visibility == STV_DEFAULT || Visibility == STV_PROTECTED))
+      continue;
+    // Create an ELFSymbol and populate it with information from the symbol table entry.
+    Expected<StringRef> SymName = terminatedSubstr(DynStr, RawSym->st_name);
+    if (!SymName)
+      return SymName.takeError();
+    ELFSymbol Sym(*SymName);
+    populateSymbol<ELFT>(Sym, *RawSym);
+    TargetStub.Symbols.insert(std::move(Sym));
+    // TODO: Populate symbol warning.
+  }
+  return Error::success();
+}
+
 /// Returns a new ELFStub with all members populated from an ELFObjectFile.
 /// @param ElfObj Source ELFObjectFile.
 template <class ELFT>
 static Expected<std::unique_ptr<ELFStub>>
 buildStub(const ELFObjectFile<ELFT> &ElfObj) {
   using Elf_Dyn_Range = typename ELFT::DynRange;
   using Elf_Phdr_Range = typename ELFT::PhdrRange;
+  using Elf_Sym_Range = typename ELFT::SymRange;
+  using Elf_Sym = typename ELFT::Sym;
   std::unique_ptr<ELFStub> DestStub = make_unique<ELFStub>();
   const ELFFile<ELFT> *ElfFile = ElfObj.getELFFile();
   // Fetch .dynamic table.
   Expected<Elf_Dyn_Range> DynTable = ElfFile->dynamicEntries();
   if (!DynTable) {
     return DynTable.takeError();
   }
 
   // Fetch program headers.
   Expected<Elf_Phdr_Range> PHdrs = ElfFile->program_headers();
   if (!PHdrs) {
     return PHdrs.takeError();
   }
 
   // Collect relevant .dynamic entries.
   DynamicEntries DynEnt;
   if (Error Err = populateDynamic<ELFT>(DynEnt, *DynTable))
     return std::move(Err);
 
-  // Convert .dynstr address to an offset.
+    // Get pointer to in-memory location of .dynstr section.
   Expected<const uint8_t *> DynStrPtr =
       ElfFile->toMappedAddr(DynEnt.StrTabAddr);
   if (!DynStrPtr)
     return appendToError(DynStrPtr.takeError(),
                          "when locating .dynstr section contents");
 
   StringRef DynStr(reinterpret_cast<const char *>(DynStrPtr.get()),
                    DynEnt.StrSize);
for (uint64_t NeededStrOffset : DynEnt.NeededLibNames) {
     Expected<StringRef> LibNameOrErr =
         terminatedSubstr(DynStr, NeededStrOffset);
     if (!LibNameOrErr) {
       return appendToError(LibNameOrErr.takeError(), "when reading DT_NEEDED");
     }
     DestStub->NeededLibs.push_back(*LibNameOrErr);
   }
 
-  // TODO: Populate Symbols from .dynsym table and linked string table.
+  // Populate Symbols from .dynsym table and dynamic string table.
+  Expected<uint64_t> SymCount = getNumSyms(DynEnt, *ElfFile);
+  if (!SymCount)
+    return SymCount.takeError();
+  if (*SymCount > 0) {
+    // Get pointer to in-memory location of .dynsym section.
+    Expected<const uint8_t *> DynSymPtr =
+        ElfFile->toMappedAddr(DynEnt.DynSymAddr);
+    if (!DynSymPtr)
+      return appendToError(DynSymPtr.takeError(),
+                           "when locating .dynsym section contents");
+    Elf_Sym_Range DynSyms =
+        ArrayRef<Elf_Sym>(reinterpret_cast<const Elf_Sym *>(*DynSymPtr),
+                          *SymCount);
+    Error SymReadError = populateSymbols<ELFT>(*DestStub, DynSyms, DynStr);
+    if (SymReadError)
+      return appendToError(std::move(SymReadError),
+                           "when reading dynamic symbols");
+  }
 
   return std::move(DestStub);
 }
 
 Expected<std::unique_ptr<ELFStub>> readELFFile(MemoryBufferRef Buf) {
   Expected<std::unique_ptr<Binary>> BinOrErr = createBinary(Buf);
   if (!BinOrErr) {
     return BinOrErr.takeError();