[JITLink][ELF] Add support for reading extended table

[steven_wu]

Summary

Add support for reading extended table in ELF object file. This allows
JITLink to support ELF object files with many sections.

[lhames]

Nice! Thanks very much for implementing this.

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

protected:
   typename ELFFile::Elf_Shdr_Range Sections;
   const typename ELFFile::Elf_Shdr *SymTabSec = nullptr;
   StringRef SectionStringTab;
 
   // Maps ELF section indexes to LinkGraph Sections.
   // Only SHF_ALLOC sections will have graph sections.
   DenseMap<ELFSectionIndex, Section *> GraphSections;
   DenseMap<ELFSymbolIndex, Symbol *> GraphSymbols;
+  DenseMap<const typename ELFFile::Elf_Shdr *,
+           ArrayRef<typename ELFFile::Elf_Word>>
+      ShndxTables;
 };
 
 template <typename ELFT>
 ELFLinkGraphBuilder<ELFT>::ELFLinkGraphBuilder(
     const ELFFile &Obj, Triple TT, StringRef FileName,
     LinkGraph::GetEdgeKindNameFunction GetEdgeKindName)
     : ELFLinkGraphBuilderBase(std::make_unique<LinkGraph>(
           FileName.str(), Triple(std::move(TT)), ELFT::Is64Bits ? 8 : 4,
template <typename ELFT> Error ELFLinkGraphBuilder<ELFT>::prepare() {
 
   // Get the section string table.
   if (auto SectionStringTabOrErr = Obj.getSectionStringTable(Sections))
     SectionStringTab = *SectionStringTabOrErr;
   else
     return SectionStringTabOrErr.takeError();
 
   // Get the SHT_SYMTAB section.
-  for (auto &Sec : Sections)
+  for (auto &Sec : Sections) {
     if (Sec.sh_type == ELF::SHT_SYMTAB) {
       if (!SymTabSec)
         SymTabSec = &Sec;
       else
         return make_error<JITLinkError>("Multiple SHT_SYMTAB sections in " +
                                         G->getName());
     }
 
+    // Extended table.
+    if (Sec.sh_type == ELF::SHT_SYMTAB_SHNDX) {
+      uint32_t SymtabNdx = Sec.sh_link;
+      if (SymtabNdx >= Sections.size())
+        return make_error<JITLinkError>("sh_link is out of bound");
+
+      auto ShndxTable = Obj.getSHNDXTable(Sec);
+      if (!ShndxTable)
+        return ShndxTable.takeError();
+
+      ShndxTables.insert({&Sections[SymtabNdx], *ShndxTable});
+    }
+  }
+
   return Error::success();
 }
 
 template <typename ELFT> Error ELFLinkGraphBuilder<ELFT>::graphifySections() {
   LLVM_DEBUG(dbgs() << "  Creating graph sections...\n");
 
   // For each section...
   for (ELFSectionIndex SecIndex = 0; SecIndex != Sections.size(); ++SecIndex) {
if (auto LSOrErr = getSymbolLinkageAndScope(Sym, *Name))
       std::tie(L, S) = *LSOrErr;
     else
       return LSOrErr.takeError();
 
     if (Sym.isDefined() &&
         (Sym.getType() == ELF::STT_NOTYPE || Sym.getType() == ELF::STT_FUNC ||
          Sym.getType() == ELF::STT_OBJECT ||
          Sym.getType() == ELF::STT_SECTION || Sym.getType() == ELF::STT_TLS)) {
-
-      // FIXME: Handle extended tables.
-      if (auto *GraphSec = getGraphSection(Sym.st_shndx)) {
+      // Handle extended tables.
+      unsigned Shndx = Sym.st_shndx;
+      if (Shndx == ELF::SHN_XINDEX) {
+        auto ShndxTable = ShndxTables.find(SymTabSec);
+        if (ShndxTable == ShndxTables.end())
+          continue;
+        auto NdxOrErr = object::getExtendedSymbolTableIndex<ELFT>(
+            Sym, SymIndex, ShndxTable->second);
+        if (!NdxOrErr)
+          return NdxOrErr.takeError();
+        Shndx = *NdxOrErr;
+      }
+      if (auto *GraphSec = getGraphSection(Shndx)) {
         Block *B = nullptr;
         {
           auto Blocks = GraphSec->blocks();
           assert(Blocks.begin() != Blocks.end() && "No blocks for section");
           assert(std::next(Blocks.begin()) == Blocks.end() &&
                  "Multiple blocks for section");
           B = *Blocks.begin();
         }

llvm/test/ExecutionEngine/JITLink/X86/ELF_shndex.s

+// Test object file with extended symbol table can be linked.
+
+// RUN: llvm-mc -filetype=obj -triple x86_64-pc-linux-gnu %s -o %t
+// RUN: llvm-jitlink -noexec %t
+
+.macro gen_sections4 x
+        .section a\x
+        .section b\x
+        .section c\x
+        .section d\x
+.endm
+
+.macro gen_sections8 x
+        gen_sections4 a\x
+        gen_sections4 b\x
+.endm
+
+.macro gen_sections16 x
+        gen_sections8 a\x
+        gen_sections8 b\x
+.endm
+
+.macro gen_sections32 x
+        gen_sections16 a\x
+        gen_sections16 b\x
+.endm
+
+.macro gen_sections64 x
+        gen_sections32 a\x
+        gen_sections32 b\x
+.endm
+
+.macro gen_sections128 x
+        gen_sections64 a\x
+        gen_sections64 b\x
+.endm
+
+.macro gen_sections256 x
+        gen_sections128 a\x
+        gen_sections128 b\x
+.endm
+
+.macro gen_sections512 x
+        gen_sections256 a\x
+        gen_sections256 b\x
+.endm
+
+.macro gen_sections1024 x
+        gen_sections512 a\x
+        gen_sections512 b\x
+.endm
+
+.macro gen_sections2048 x
+        gen_sections1024 a\x
+        gen_sections1024 b\x
+.endm
+
+.macro gen_sections4096 x
+        gen_sections2048 a\x
+        gen_sections2048 b\x
+.endm
+
+.macro gen_sections8192 x
+        gen_sections4096 a\x
+        gen_sections4096 b\x
+.endm
+
+.macro gen_sections16384 x
+        gen_sections8192 a\x
+        gen_sections8192 b\x
+.endm
+
+.macro gen_sections32768 x
+        gen_sections16384 a\x
+        gen_sections16384 b\x
+.endm
+
+        .section foo
+        .section bar
+
+gen_sections32768 a
+gen_sections16384 b
+gen_sections8192 c
+gen_sections4096 d
+gen_sections2048 e
+gen_sections1024 f
+gen_sections512 g
+gen_sections128 h
+gen_sections64 i
+gen_sections32 j
+gen_sections16 k
+gen_sections8 l
+gen_sections4 m
+
+.section test,"ax"
+.global a
+a:
+nop
+.size   a, .-a
+
+.text
+.global main
+main:
+nop
+.size   main, .-main