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

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.

Differential revision: https://reviews.llvm.org/D49541

llvm-svn: 338247

5 files changed, 109 insertions, 35 deletions

diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index 38859e1650b..386f1e824bf 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -1935,6 +1935,23 @@ SymbolTableSection<ELFT>::SymbolTableSection(StringTableSection &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 (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.
@@ -1956,22 +1973,7 @@ template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
     }
 
     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
@@ -1986,7 +1988,7 @@ template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
     // 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();
@@ -2026,6 +2028,44 @@ template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
   }
 }
 
+SymtabShndxSection::SymtabShndxSection()
+    : SyntheticSection(0, SHT_SYMTAB_SHNDX, 4, ".symtab_shndxr") {
+  this->Entsize = 4;
+}
+
+void SymtabShndxSection::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 SymtabShndxSection::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 SymtabShndxSection::finalizeContents() {
+  getParent()->Link = InX::SymTab->getParent()->SectionIndex;
+}
+
+size_t SymtabShndxSection::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
@@ -3025,6 +3065,7 @@ RelocationBaseSection *InX::RelaIplt;
 StringTableSection *InX::ShStrTab;
 StringTableSection *InX::StrTab;
 SymbolTableBaseSection *InX::SymTab;
+SymtabShndxSection *InX::SymTabShndx;
 
 template GdbIndexSection *GdbIndexSection::create<ELF32LE>();
 template GdbIndexSection *GdbIndexSection::create<ELF32BE>();
diff --git a/lld/ELF/SyntheticSections.h b/lld/ELF/SyntheticSections.h
index 0366c6c3f8c..a780c663137 100644
--- a/lld/ELF/SyntheticSections.h
+++ b/lld/ELF/SyntheticSections.h
@@ -588,6 +588,16 @@ public:
   void writeTo(uint8_t *Buf) override;
 };
 
+class SymtabShndxSection final : public SyntheticSection {
+public:
+  SymtabShndxSection();
+
+  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 {
@@ -992,6 +1002,7 @@ struct InX {
   static StringTableSection *ShStrTab;
   static StringTableSection *StrTab;
   static SymbolTableBaseSection *SymTab;
+  static SymtabShndxSection* SymTabShndx;
 };
 
 template <class ELFT> struct In {
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index 533ac47f937..91741f6eaf5 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -287,6 +287,7 @@ template <class ELFT> static void createSyntheticSections() {
   if (Config->Strip != StripPolicy::All) {
     InX::StrTab = make<StringTableSection>(".strtab", false);
     InX::SymTab = make<SymbolTableSection<ELFT>>(*InX::StrTab);
+    InX::SymTabShndx = make<SymtabShndxSection>();
   }
 
   if (Config->BuildId != BuildIdKind::None) {
@@ -409,6 +410,8 @@ template <class ELFT> static void createSyntheticSections() {
 
   if (InX::SymTab)
     Add(InX::SymTab);
+  if (InX::SymTabShndx)
+    Add(InX::SymTabShndx);
   Add(InX::ShStrTab);
   if (InX::StrTab)
     Add(InX::StrTab);
@@ -1639,12 +1642,13 @@ template <class ELFT> void Writer<ELFT>::finalizeSections() {
   // 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)
diff --git a/lld/test/ELF/linkerscript/orphan-report.s b/lld/test/ELF/linkerscript/orphan-report.s
index 241857b239c..903ef799e7a 100644
--- a/lld/test/ELF/linkerscript/orphan-report.s
+++ b/lld/test/ELF/linkerscript/orphan-report.s
@@ -36,6 +36,7 @@
 # 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'
 
diff --git a/lld/test/ELF/relocatable-many-sections.s b/lld/test/ELF/relocatable-many-sections.s
index df22154d0c9..347f3f784f2 100644
--- a/lld/test/ELF/relocatable-many-sections.s
+++ b/lld/test/ELF/relocatable-many-sections.s
@@ -1,20 +1,32 @@
 # 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
-## sections amount is greater than SHN_LORESERVE.
-# CHECK:      ElfHeader {
-# CHECK:        SectionHeaderCount: 0 (65541)
-# CHECK-NEXT:   StringTableSectionIndex: 65535 (65539)
+## Check we are able to link against relocatable file produced.
+# RUN: ld.lld %t -o %t.out
 
-## 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
+## Check we emit a valid ELF header when
+## sections amount is greater than SHN_LORESERVE.
+# 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
@@ -88,5 +100,10 @@ gen_sections16384 b
 gen_sections16384 c
 gen_sections16384 d
 
+.section .bar
+.global foo
+foo:
+
+.section .text, "ax"
 .global _start
 _start: