[ELF] - Implement SHT_SYMTAB_SHNDX (.symtab_shndxr) section.

[grimar]

Summary

This is relative to https://bugs.llvm.org//show_bug.cgi?id=38119.

SHT_SYMTAB section is able to keep symbols with output section indices up to 0xff00 (SHN_LORESERVE).
But if we have indices that are greater than that (PR shows that it might happen), we need to use
SHT_SYMTAB_SHNDX extended section. It was not supported by LLD.

Description of the SHT_SYMTAB_SHNDX section is here:
https://docs.oracle.com/cd/E19683-01/817-3677/chapter6-94076/index.html.

[ruiu]

LGTM

ELF/SyntheticSections.cpp

1921

You are not using CommonSec.

ELF/SyntheticSections.h

591

I'd name this SymtabShndxSection for consistency with the name of the section.

ELF/SyntheticSections.h

 class SymbolTableSection final : public SymbolTableBaseSection {
   typedef typename ELFT::Sym Elf_Sym;
 
 public:
   SymbolTableSection(StringTableSection &StrTabSec);
   void writeTo(uint8_t *Buf) override;
 };
 
+class SymbolTableShndxSection final : public SyntheticSection {
+public:
+  SymbolTableShndxSection();
+
+  void writeTo(uint8_t *Buf) override;
+  size_t getSize() const override;
+  bool empty() const override;
+  void finalizeContents() override;
+};
+
 // Outputs GNU Hash section. For detailed explanation see:
 // https://blogs.oracle.com/ali/entry/gnu_hash_elf_sections
 class GnuHashTableSection final : public SyntheticSection {
 public:
   GnuHashTableSection();
   void finalizeContents() override;
   void writeTo(uint8_t *Buf) override;
   size_t getSize() const override { return Size; }
struct InX {
   static PltSection *Iplt;
   static RelocationBaseSection *RelaDyn;
   static RelrBaseSection *RelrDyn;
   static RelocationBaseSection *RelaPlt;
   static RelocationBaseSection *RelaIplt;
   static StringTableSection *ShStrTab;
   static StringTableSection *StrTab;
   static SymbolTableBaseSection *SymTab;
+  static SymbolTableShndxSection* SymTabShndx;
 };
 
 template <class ELFT> struct In {
   static VersionDefinitionSection<ELFT> *VerDef;
   static VersionTableSection<ELFT> *VerSym;
   static VersionNeedSection<ELFT> *VerNeed;
 };
 
 template <class ELFT> VersionDefinitionSection<ELFT> *In<ELFT>::VerDef;
 template <class ELFT> VersionTableSection<ELFT> *In<ELFT>::VerSym;
 template <class ELFT> VersionNeedSection<ELFT> *In<ELFT>::VerNeed;
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/SyntheticSections.cpp

 }
 
 template <class ELFT>
 SymbolTableSection<ELFT>::SymbolTableSection(StringTableSection &StrTabSec)
     : SymbolTableBaseSection(StrTabSec) {
   this->Entsize = sizeof(Elf_Sym);
 }
 
+static BssSection *getCommonSec(Symbol *Sym) {
+  if (!Config->DefineCommon)
+    if (auto *D = dyn_cast<Defined>(Sym))
+      return dyn_cast_or_null<BssSection>(D->Section);
+  return nullptr;
+}
+
+static uint32_t getSymSectionIndex(Symbol *Sym) {
+  if (BssSection *CommonSec = getCommonSec(Sym))
+    return SHN_COMMON;
+  if (!isa<Defined>(Sym) || Sym->NeedsPltAddr)
+    return SHN_UNDEF;
+  if (const OutputSection *OS = Sym->getOutputSection())
+    return OS->SectionIndex >= SHN_LORESERVE ? SHN_XINDEX : OS->SectionIndex;
+  return SHN_ABS;
+}
+
 // Write the internal symbol table contents to the output symbol table.
 template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
   // The first entry is a null entry as per the ELF spec.
   memset(Buf, 0, sizeof(Elf_Sym));
   Buf += sizeof(Elf_Sym);
 
   auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
 
   for (SymbolTableEntry &Ent : Symbols) {
     Symbol *Sym = Ent.Sym;
 
     // Set st_info and st_other.
     ESym->st_other = 0;
     if (Sym->isLocal()) {
       ESym->setBindingAndType(STB_LOCAL, Sym->Type);
     } else {
       ESym->setBindingAndType(Sym->computeBinding(), Sym->Type);
       ESym->setVisibility(Sym->Visibility);
     }
 
     ESym->st_name = Ent.StrTabOffset;
-
-    // Set a section index.
-    BssSection *CommonSec = nullptr;
-    if (!Config->DefineCommon)
-      if (auto *D = dyn_cast<Defined>(Sym))
-        CommonSec = dyn_cast_or_null<BssSection>(D->Section);
-    if (CommonSec)
-      ESym->st_shndx = SHN_COMMON;
-    else if (Sym->NeedsPltAddr)
-      ESym->st_shndx = SHN_UNDEF;
-    else if (const OutputSection *OutSec = Sym->getOutputSection())
-      ESym->st_shndx = OutSec->SectionIndex;
-    else if (isa<Defined>(Sym))
-      ESym->st_shndx = SHN_ABS;
-    else
-      ESym->st_shndx = SHN_UNDEF;
+    ESym->st_shndx = getSymSectionIndex(Ent.Sym);
 
     // Copy symbol size if it is a defined symbol. st_size is not significant
     // for undefined symbols, so whether copying it or not is up to us if that's
     // the case. We'll leave it as zero because by not setting a value, we can
     // get the exact same outputs for two sets of input files that differ only
     // in undefined symbol size in DSOs.
     if (ESym->st_shndx == SHN_UNDEF)
       ESym->st_size = 0;
     else
       ESym->st_size = Sym->getSize();
 
     // st_value is usually an address of a symbol, but that has a
     // special meaining for uninstantiated common symbols (this can
     // occur if -r is given).
-    if (CommonSec)
+    if (BssSection *CommonSec = getCommonSec(Ent.Sym))
       ESym->st_value = CommonSec->Alignment;
     else
       ESym->st_value = Sym->getVA();
 
     ++ESym;
   }
 
   // On MIPS we need to mark symbol which has a PLT entry and requires
for (SymbolTableEntry &Ent : Symbols) {
         if (auto *D = dyn_cast<Defined>(Sym))
           if (isMipsPIC<ELFT>(D))
             ESym->st_other |= STO_MIPS_PIC;
       ++ESym;
     }
   }
 }
 
+SymbolTableShndxSection::SymbolTableShndxSection()
+    : SyntheticSection(0, SHT_SYMTAB_SHNDX, 4, ".symtab_shndxr") {
+  this->Entsize = 4;
+}
+
+void SymbolTableShndxSection::writeTo(uint8_t *Buf) {
+  // We write an array of 32 bit values, where each value has 1:1 association
+  // with an entry in .symtab. If the corresponding entry contains SHN_XINDEX,
+  // we need to write actual index, otherwise, we must write SHN_UNDEF(0).
+  Buf += 4; // Ignore .symtab[0] entry.
+  for (const SymbolTableEntry &Entry : InX::SymTab->getSymbols()) {
+    if (getSymSectionIndex(Entry.Sym) == SHN_XINDEX)
+      write32(Buf, Entry.Sym->getOutputSection()->SectionIndex);
+    Buf += 4;
+  }
+}
+
+bool SymbolTableShndxSection::empty() const {
+  // SHT_SYMTAB can hold symbols with section indices values up to
+  // SHN_LORESERVE. If we need more, we want to use extension SHT_SYMTAB_SHNDX
+  // section. Problem is that we reveal the final section indices a bit too
+  // late, and we do not know them here. For simplicity, we just always create
+  // a .symtab_shndxr section when the amount of output sections is huge.
+  size_t Size = 0;
+  for (BaseCommand *Base : Script->SectionCommands)
+    if (isa<OutputSection>(Base))
+      ++Size;
+  return Size < SHN_LORESERVE;
+}
+
+void SymbolTableShndxSection::finalizeContents() {
+  getParent()->Link = InX::SymTab->getParent()->SectionIndex;
+}
+
+size_t SymbolTableShndxSection::getSize() const {
+  return InX::SymTab->getNumSymbols() * 4;
+}
+
 // .hash and .gnu.hash sections contain on-disk hash tables that map
 // symbol names to their dynamic symbol table indices. Their purpose
 // is to help the dynamic linker resolve symbols quickly. If ELF files
 // don't have them, the dynamic linker has to do linear search on all
 // dynamic symbols, which makes programs slower. Therefore, a .hash
 // section is added to a DSO by default. A .gnu.hash is added if you
 // give the -hash-style=gnu or -hash-style=both option.
 //

 PltSection *InX::Iplt;
 RelocationBaseSection *InX::RelaDyn;
 RelrBaseSection *InX::RelrDyn;
 RelocationBaseSection *InX::RelaPlt;
 RelocationBaseSection *InX::RelaIplt;
 StringTableSection *InX::ShStrTab;
 StringTableSection *InX::StrTab;
 SymbolTableBaseSection *InX::SymTab;
+SymbolTableShndxSection *InX::SymTabShndx;
 
 template GdbIndexSection *GdbIndexSection::create<ELF32LE>();
 template GdbIndexSection *GdbIndexSection::create<ELF32BE>();
 template GdbIndexSection *GdbIndexSection::create<ELF64LE>();
 template GdbIndexSection *GdbIndexSection::create<ELF64BE>();
 
 template void elf::splitSections<ELF32LE>();
 template void elf::splitSections<ELF32BE>();

ELF/Writer.cpp

if (needsInterpSection()) {
     Add(InX::Interp);
   } else {
     InX::Interp = nullptr;
   }
 
   if (Config->Strip != StripPolicy::All) {
     InX::StrTab = make<StringTableSection>(".strtab", false);
     InX::SymTab = make<SymbolTableSection<ELFT>>(*InX::StrTab);
+    InX::SymTabShndx = make<SymbolTableShndxSection>();
   }
 
   if (Config->BuildId != BuildIdKind::None) {
     InX::BuildId = make<BuildIdSection>();
     Add(InX::BuildId);
   }
 
   InX::Bss = make<BssSection>(".bss", 0, 1);
if (Config->EhFrameHdr) {
       Add(InX::EhFrameHdr);
     }
     InX::EhFrame = make<EhFrameSection>();
     Add(InX::EhFrame);
   }
 
   if (InX::SymTab)
     Add(InX::SymTab);
+  if (InX::SymTabShndx)
+    Add(InX::SymTabShndx);
   Add(InX::ShStrTab);
   if (InX::StrTab)
     Add(InX::StrTab);
 
   if (Config->EMachine == EM_ARM && !Config->Relocatable)
     // Add a sentinel to terminate .ARM.exidx. It helps an unwinder
     // to find the exact address range of the last entry.
     Add(make<ARMExidxSentinelSection>());
template <class ELFT> void Writer<ELFT>::finalizeSections() {
 
   // Some symbols are defined in term of program headers. Now that we
   // have the headers, we can find out which sections they point to.
   setReservedSymbolSections();
 
   // Dynamic section must be the last one in this list and dynamic
   // symbol table section (DynSymTab) must be the first one.
   applySynthetic(
-      {InX::DynSymTab,   InX::Bss,         InX::BssRelRo,     InX::GnuHashTab,
-       InX::HashTab,     InX::SymTab,      InX::ShStrTab,     InX::StrTab,
-       In<ELFT>::VerDef, InX::DynStrTab,   InX::Got,          InX::MipsGot,
-       InX::IgotPlt,     InX::GotPlt,      InX::RelaDyn,      InX::RelrDyn,
-       InX::RelaIplt,    InX::RelaPlt,     InX::Plt,          InX::Iplt,
-       InX::EhFrameHdr,  In<ELFT>::VerSym, In<ELFT>::VerNeed, InX::Dynamic},
+      {InX::DynSymTab, InX::Bss,         InX::BssRelRo,    InX::GnuHashTab,
+       InX::HashTab,   InX::SymTab,      InX::SymTabShndx, InX::ShStrTab,
+       InX::StrTab,    In<ELFT>::VerDef, InX::DynStrTab,   InX::Got,
+       InX::MipsGot,   InX::IgotPlt,     InX::GotPlt,      InX::RelaDyn,
+       InX::RelrDyn,   InX::RelaIplt,    InX::RelaPlt,     InX::Plt,
+       InX::Iplt,      InX::EhFrameHdr,  In<ELFT>::VerSym, In<ELFT>::VerNeed,
+       InX::Dynamic},
       [](SyntheticSection *SS) { SS->finalizeContents(); });
 
   if (!Script->HasSectionsCommand && !Config->Relocatable)
     fixSectionAlignments();
 
   // After link order processing .ARM.exidx sections can be deduplicated, which
   // needs to be resolved before any other address dependent operation.
   resolveShfLinkOrder();

test/ELF/linkerscript/orphan-report.s

 # REPORT-NEXT: <internal>:(.got.plt) is being placed in '.got.plt'
 # REPORT-NEXT: <internal>:(.got.plt) is being placed in '.got.plt'
 # REPORT-NEXT: <internal>:(.rela.plt) is being placed in '.rela.plt'
 # REPORT-NEXT: <internal>:(.rela.plt) is being placed in '.rela.plt'
 # REPORT-NEXT: <internal>:(.plt) is being placed in '.plt'
 # REPORT-NEXT: <internal>:(.plt) is being placed in '.plt'
 # REPORT-NEXT: <internal>:(.eh_frame) is being placed in '.eh_frame'
 # REPORT-NEXT: <internal>:(.symtab) is being placed in '.symtab'
+# REPORT-NEXT: <internal>:(.symtab_shndxr) is being placed in '.symtab_shndxr'
 # REPORT-NEXT: <internal>:(.shstrtab) is being placed in '.shstrtab'
 # REPORT-NEXT: <internal>:(.strtab) is being placed in '.strtab'
 
 ## Check --orphan-handling=warn reports warnings about orphans.
 # RUN: ld.lld -shared --orphan-handling=warn -o %t.out --script %t.script \
 # RUN:   %t.o 2>&1 -verbose | FileCheck %s --check-prefix=REPORT
 
 # RUN: not ld.lld --orphan-handling=foo -o %t.out --script %t.script %t.o 2>&1 \
 # RUN:   | FileCheck %s --check-prefix=UNKNOWN
 # UNKNOWN: unknown --orphan-handling mode: foo
 
 .section .text.1,"a"
  nop
 
 .section .text.2,"a"
  nop

test/ELF/relocatable-many-sections.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple x86_64-pc-linux-gnu %s -o %t.o
 # RUN: ld.lld -r %t.o -o %t
-# RUN: llvm-readobj -file-headers %t | FileCheck %s
 
-## Check we are able to emit a valid ELF header when
+## Check we are able to link against relocatable file produced.
+# RUN: ld.lld %t -o %t.out
+
+## Check we emit a valid ELF header when
 ## sections amount is greater than SHN_LORESERVE.
-# CHECK:      ElfHeader {
-# CHECK:        SectionHeaderCount: 0 (65541)
-# CHECK-NEXT:   StringTableSectionIndex: 65535 (65539)
-
-## Check that 65539 is really the index of .shstrtab section.
-# RUN: llvm-objdump -section-headers -section=.shstrtab %t \
-# RUN:   | FileCheck %s --check-prefix=SHSTRTAB
-# SHSTRTAB:      Sections:
-# SHSTRTAB-NEXT:  Idx   Name
-# SHSTRTAB-NEXT:  65539 .shstrtab
+# RUN: llvm-readobj -file-headers %t | FileCheck %s --check-prefix=HDR
+# HDR:      ElfHeader {
+# HDR:        SectionHeaderCount: 0 (65543)
+# HDR-NEXT:   StringTableSectionIndex: 65535 (65541)
+
+## Check that:
+## 1) 65541 is the index of .shstrtab section.
+## 2) .symtab_shndxr is linked with .symtab.
+## 3) .symtab_shndxr entry size and alignment == 4.
+## 4) .symtab_shndxr has size equal to
+##    (sizeof(.symtab) / entsize(.symtab)) * entsize(.symtab_shndxr) = 0x4 * 0x180048 / 0x18 == 0x04000c
+# RUN: llvm-readelf -sections -symbols %t | FileCheck %s
+##              [Nr]    Name           Type                   Address          Off    Size   ES Flg  Lk    Inf    Al
+# CHECK:        [65538] .bar
+# CHECK-NEXT:   [65539] .symtab        SYMTAB                 0000000000000000 000040 180078 18      65542 65539  8
+# CHECK-NEXT:   [65540] .symtab_shndxr SYMTAB SECTION INDICES 0000000000000000 1800b8 040014 04      65539 0      4
+# CHECK-NEXT:   [65541] .shstrtab      STRTAB                 0000000000000000 1c00cc 0f0035 00      0     0      1
+# CHECK-NEXT:   [65542] .strtab        STRTAB                 0000000000000000 2b0101 00000c 00
+# 5) Check we are able to represent symbol foo with section (.bar) index  > 0xFF00 (SHN_LORESERVE).
+# CHECK: GLOBAL DEFAULT  65538 foo
 
 .macro gen_sections4 x
   .section a\x
   .section b\x
   .section c\x
   .section d\x
 .endm
 
.macro gen_sections16384 x
   gen_sections8192 b\x
 .endm
 
 gen_sections16384 a
 gen_sections16384 b
 gen_sections16384 c
 gen_sections16384 d
 
+.section .bar
+.global foo
+foo:
+
+.section .text, "ax"
 .global _start
 _start: