[llvm-objcopy] Add support for large indexes

[jakehehrlich]

Summary

This patch is an update of an older patch that never landed (see here: https://reviews.llvm.org/D42516)

Recently various users have run into this issue and it just 100% has to be solved at this point. The main difference in this patch is that I use gunzip instead of unzip which should hopefully allow tests to pass. Please review this as if it is a new patch however. I found some issues along the way and made some minor modifications.

The binary used in this patch for testing (a zip file to make it small) can be found here: https://drive.google.com/file/d/1UjsnTO9edLttZibbr-2T1bJl92KEQFAO/view?usp=sharing

[alexander-shaposhnikov]

llvm/test/tools/llvm-objcopy/auto-remove-shndx.test

2

just in case - I don't see any other tests using gunzip - not sure if it's available by default (in particular, on the machines where build bots are running)

[jakehehrlich]

llvm/test/tools/llvm-objcopy/auto-remove-shndx.test

2

There is no published list. I'll just have to try it and revert it if it doesn't work. This is the easy case that *might* just work. If this dosn't work then I'll add some python to each of these tests to unzip the file instead.

[alexander-shaposhnikov]

llvm/tools/llvm-objcopy/Object.h

404

similarly to how it's done in the other similar cases I'd initialize Symbols with nullptr

[jhenderson]

I might be going overboard with the comments around "auto", and I didn't highlight all of the ones I spotted. But here's the link to the corresponding style point: https://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable. Feel free to ignore what I said if you think they're valid uses.

llvm/test/tools/llvm-objcopy/auto-remove-shndx.test

2

I just tested, and my Windows machine doesn't have it, so it's not part of the GnuWin32 tools, which are the requirement.

llvm/test/tools/llvm-objcopy/remove-shndx.test

3

Would you mind first putting in a separate patch to LLVM to rename .symtab_shndxr to .symtab_shndx, which is the standard name? I'd rather not propagate the incorrect name further.

llvm/test/tools/llvm-objcopy/strict-no-add.test

2–3

Just musing about this a bit. I wonder if this is the behaviour we should follow. It's certainly correct to do so, but it's unclear from the gABI whether it's okay to generate it under other circumstances. If we think it's okay to, maybe it would be simpler to just always generate the table if there are >= SHN_LORESERVE number of sections?

llvm/tools/llvm-objcopy/Object.cpp

164

I'd rename this to something like "IndexesBuffer" or similar, just because I got confused between Indexes and Sec.Indexes on the line below.

203

I'm not sure "proper value of st_shndx" is quite clear enough. Maybe "the value that will appear in st_shndx" might be better?

705–706

What is the type of Symbols here? I think the LLVM coding style is not to use auto in these situations.

706

Ditto.

723

Ditto.

726

Hmm... not sure about this error message, since the section isn't invalid, rather the section index is. So, maybe something like "Symbol 'bar' has an invalid section index 12345".

I assume that testing this would be unrealistic due to the size of the required test input?

857

initilize -> initialize (x 2)

859

refernece -> reference

1021

See comments about auto above.

1233–1238

Could you use std::any_of here?
Also, I might have missed something, but why the update to Sec.Index for large-index sections only here? You assign the indexes further down anyway.

1245

but if -> but if we

1264

I wouldn't use the function name in the comment here. I'd just say "prepare for layout"

1270

"For instance" -> "For instance,"

llvm/tools/llvm-objcopy/Object.h

419

I wonder if this should be the default for all SectionBase classes (i.e. initialise the field in the header)?

[jakehehrlich]

Now uses python to uncompress.
Responded to comments.

[jakehehrlich]

llvm/test/tools/llvm-objcopy/auto-remove-shndx.test

2

siiiiigh. I'll rewrite the test to work using python then.

llvm/test/tools/llvm-objcopy/strict-no-add.test

2–3

I think the cases where anyone would care about it too much are few and far between which is why I'm not breaking my back to solve the case where it overly eagerly emits a shndx table by 1 index. I started to write the code for doing this but it just winds up being that we delete some code that I already wrote so why not keep it I guess. If you think the system as a whole is strictly improved by removing that code I'll remove it.

llvm/tools/llvm-objcopy/Object.cpp

705–706

Our options here are

ElfFile<ELFT>::Elf_Sym_Range
typename ELFT::SymRange
ArrayRef<typename ELFT::Sym>

I've presented these in order of unfolding. They're all shorter than I expected. The last is the most clear but also it means that if ElfFile or ELFT changes their SymRange type an issue could arise. I find most of these either verbose or opaque however.

706

I'm going to push back here because a typename and collon is needed. e.g. there is extra difficulty.

726

This is actually testable quite easily by uploading a specially constructed binary (which I'm getting pretty good at these days). Basically construct a binary that uses SHN_XINDEX and then puts an overly large index in the shndx table despite there being only 1 symbol. This would require just a bit of yaml2obj and some hex editing. The problem is that constructing such a binary is liable to take me 2-3 hours and I don't want to spend that time just to test one error message.

llvm/tools/llvm-objcopy/Object.h

419

Sure, I'll go ahead and set it that way, why not.

[jakehehrlich]

Forgot to update error message for one of James' comments

[jakehehrlich]

Updated shndx name for this test.

[alexander-shaposhnikov]

to me looks good, though I'd wait for James.

[jhenderson]

LGTM, with the nits, assuming the tests aren't realistic without spending hours at it.

llvm/test/tools/llvm-objcopy/remove-shndx.test

2

Probably worth putting a comment at the start of this test, to say what it is doing, because at the moment the test name is "remove-shndx", but the test doesn't actually do so!

llvm/tools/llvm-objcopy/Object.cpp

203

Nit: will appear st_shndx -> will appear in st_shndx

712–713

Do we have a sensible way to test this, without binary editing something?

720–721

Ditto. Is a test here feasible?

726

Okay, fair enough. I won't force it. I wonder if maybe this is an indication we need a "relaxed" mode for yaml2obj that allows us to write arbitrary values to the file? Anyway, not really part of this, more just idle musing again.

I think my ideal scenario would be able to write a symbol with a custom section index to the symbol table, even if that doesn't refer to a real section index.

[alexander-shaposhnikov]

@jakehehrlich - is there anything blocking this ?

[jakehehrlich]

Nope, I was just about to land it. I wasn't in office Friday and I was conducting an interview this morning. It will be in shortly.

[alexander-shaposhnikov]

thanks!

llvm/test/tools/llvm-objcopy/Inputs/ungzip.py

+import gzip
+import sys
+
+with gzip.open(sys.argv[1], 'rb') as f:
+  sys.stdout.write(f.read())

llvm/test/tools/llvm-objcopy/auto-remove-shndx.test

+# RUN: python %p/Inputs/ungzip.py %p/Inputs/many-sections.o.gz > %t
+# RUN: llvm-objcopy -R .text -R s0 -R s1 -R s2 -R s3 -R s4 -R s5 -R s6 %t %t2
+# RUN: llvm-readobj -sections %t2 | FileCheck --check-prefix=SECS %s
+
+# SECS-NOT: Name: .symtab_shndx

llvm/test/tools/llvm-objcopy/many-sections.test

+RUN: python %p/Inputs/ungzip.py %p/Inputs/many-sections.o.gz > %t
+RUN: llvm-objcopy %t %t2
+RUN: llvm-readobj -file-headers %t2 | FileCheck --check-prefix=EHDR %s
+RUN: llvm-readobj -sections %t2 | FileCheck --check-prefix=SECS %s
+RUN: llvm-readobj -symbols %t2 | grep "Symbol {" | wc -l | FileCheck --check-prefix=SYMS %s
+
+EHDR:      Format: ELF64-x86-64
+EHDR-NEXT: Arch: x86_64
+EHDR-NEXT: AddressSize: 64bit
+EHDR-NEXT: LoadName:
+EHDR-NEXT: ElfHeader {
+EHDR-NEXT:   Ident {
+EHDR-NEXT:     Magic: (7F 45 4C 46)
+EHDR-NEXT:     Class: 64-bit (0x2)
+EHDR-NEXT:     DataEncoding: LittleEndian (0x1)
+EHDR-NEXT:     FileVersion: 1
+EHDR-NEXT:     OS/ABI: SystemV (0x0)
+EHDR-NEXT:     ABIVersion: 0
+EHDR-NEXT:     Unused: (00 00 00 00 00 00 00)
+EHDR-NEXT:   }
+EHDR-NEXT:   Type: Relocatable (0x1)
+EHDR-NEXT:   Machine: EM_X86_64 (0x3E)
+EHDR-NEXT:   Version: 1
+EHDR-NEXT:   Entry: 0x0
+EHDR-NEXT:   ProgramHeaderOffset: 0x40
+EHDR-NEXT:   SectionHeaderOffset:
+EHDR-NEXT:   Flags [ (0x0)
+EHDR-NEXT:   ]
+EHDR-NEXT:   HeaderSize: 64
+EHDR-NEXT:   ProgramHeaderEntrySize: 56
+EHDR-NEXT:   ProgramHeaderCount: 0
+EHDR-NEXT:   SectionHeaderEntrySize: 64
+EHDR-NEXT:   SectionHeaderCount: 0
+EHDR-NEXT:   StringTableSectionIndex: 65535
+EHDR-NEXT: }
+
+SECS: Index: 65285
+SECS-NEXT: Name: .symtab
+SECS-NEXT: Type: SHT_SYMTAB
+SECS: Name: .symtab_shndx
+SECS-NEXT: Type: SHT_SYMTAB_SHNDX
+SECS-NEXT: Flags [ (0x0)
+SECS-NEXT: ]
+SECS-NEXT: Address: 0x0
+SECS-NEXT: Offset:
+# There should be #syms * EntrySize bytes.
+SECS-NEXT: Size: 261136
+SECS-NEXT: Link: 65285
+SECS-NEXT: Info:
+SECS-NEXT: AddressAlignment: 4
+SECS-NEXT: EntrySize: 4
+SECS: Index: 65287
+SYMS: 65284

llvm/test/tools/llvm-objcopy/remove-shndx.test

+RUN: python %p/Inputs/ungzip.py %p/Inputs/many-sections.o.gz > %t
+RUN: llvm-objcopy -R .symtab_shndxr %t %t2
+RUN: llvm-readobj -sections %t2 | FileCheck %s
+
+CHECK: Name: .symtab_shndx (

llvm/test/tools/llvm-objcopy/strict-no-add.test

+# This test makes sure that sections added at the end that don't have symbols
+# defined in them don't trigger the creation of a large index table.
+
+RUN: python %p/Inputs/ungzip.py %p/Inputs/many-sections.o.gz > %t.0
+RUN: cat %p/Inputs/alloc-symtab.o > %t
+RUN: llvm-objcopy -R .text -R s0 -R s1 -R s2 -R s3 -R s4 -R s5 -R s6 %t.0 %t2
+RUN: llvm-objcopy -add-section=.s0=%t -add-section=.s1=%t -add-section=.s2=%t %t2 %t2
+RUN: llvm-readobj -sections %t2 | FileCheck --check-prefix=SECS %s
+
+SECS-NOT: Name: .symtab_shndx

llvm/tools/llvm-objcopy/Object.h

 class Section;
 class OwnedDataSection;
 class StringTableSection;
 class SymbolTableSection;
 class RelocationSection;
 class DynamicRelocationSection;
 class GnuDebugLinkSection;
 class GroupSection;
+class SectionIndexSection;
 class Segment;
 class Object;
 struct Symbol;
 
 class SectionTableRef {
   MutableArrayRef<std::unique_ptr<SectionBase>> Sections;
 
 public:
   using iterator = pointee_iterator<std::unique_ptr<SectionBase> *>;
 
   explicit SectionTableRef(MutableArrayRef<std::unique_ptr<SectionBase>> Secs)
       : Sections(Secs) {}
   SectionTableRef(const SectionTableRef &) = default;
 
   iterator begin() { return iterator(Sections.data()); }
   iterator end() { return iterator(Sections.data() + Sections.size()); }
 
-  SectionBase *getSection(uint16_t Index, Twine ErrMsg);
+  SectionBase *getSection(uint32_t Index, Twine ErrMsg);
 
   template <class T>
-  T *getSectionOfType(uint16_t Index, Twine IndexErrMsg, Twine TypeErrMsg);
+  T *getSectionOfType(uint32_t Index, Twine IndexErrMsg, Twine TypeErrMsg);
 };
 
 enum ElfType { ELFT_ELF32LE, ELFT_ELF64LE, ELFT_ELF32BE, ELFT_ELF64BE };
 
 class SectionVisitor {
 public:
   virtual ~SectionVisitor();
 
   virtual void visit(const Section &Sec) = 0;
   virtual void visit(const OwnedDataSection &Sec) = 0;
   virtual void visit(const StringTableSection &Sec) = 0;
   virtual void visit(const SymbolTableSection &Sec) = 0;
   virtual void visit(const RelocationSection &Sec) = 0;
   virtual void visit(const DynamicRelocationSection &Sec) = 0;
   virtual void visit(const GnuDebugLinkSection &Sec) = 0;
   virtual void visit(const GroupSection &Sec) = 0;
+  virtual void visit(const SectionIndexSection &Sec) = 0;
 };
 
 class SectionWriter : public SectionVisitor {
 protected:
   Buffer &Out;
 
 public:
   virtual ~SectionWriter(){};
 
   void visit(const Section &Sec) override;
   void visit(const OwnedDataSection &Sec) override;
   void visit(const StringTableSection &Sec) override;
   void visit(const DynamicRelocationSection &Sec) override;
   virtual void visit(const SymbolTableSection &Sec) override = 0;
   virtual void visit(const RelocationSection &Sec) override = 0;
   virtual void visit(const GnuDebugLinkSection &Sec) override = 0;
   virtual void visit(const GroupSection &Sec) override = 0;
+  virtual void visit(const SectionIndexSection &Sec) override = 0;
 
   explicit SectionWriter(Buffer &Buf) : Out(Buf) {}
 };
 
 template <class ELFT> class ELFSectionWriter : public SectionWriter {
 private:
   using Elf_Word = typename ELFT::Word;
   using Elf_Rel = typename ELFT::Rel;
   using Elf_Rela = typename ELFT::Rela;
 
 public:
   virtual ~ELFSectionWriter() {}
   void visit(const SymbolTableSection &Sec) override;
   void visit(const RelocationSection &Sec) override;
   void visit(const GnuDebugLinkSection &Sec) override;
   void visit(const GroupSection &Sec) override;
+  void visit(const SectionIndexSection &Sec) override;
 
   explicit ELFSectionWriter(Buffer &Buf) : SectionWriter(Buf) {}
 };
 
 #define MAKE_SEC_WRITER_FRIEND                                                 \
   friend class SectionWriter;                                                  \
   template <class ELFT> friend class ELFSectionWriter;
 
 class BinarySectionWriter : public SectionWriter {
 public:
   virtual ~BinarySectionWriter() {}
 
   void visit(const SymbolTableSection &Sec) override;
   void visit(const RelocationSection &Sec) override;
   void visit(const GnuDebugLinkSection &Sec) override;
   void visit(const GroupSection &Sec) override;
+  void visit(const SectionIndexSection &Sec) override;
 
   explicit BinarySectionWriter(Buffer &Buf) : SectionWriter(Buf) {}
 };
 
 // The class Buffer abstracts out the common interface of FileOutputBuffer and
 // WritableMemoryBuffer so that the hierarchy of Writers depends on this
 // abstract interface and doesn't depend on a particular implementation.
 // TODO: refactor the buffer classes in LLVM to enable us to use them here
public:
   BinaryWriter(Object &Obj, Buffer &Buf) : Writer(Obj, Buf) {}
 };
 
 class SectionBase {
 public:
   StringRef Name;
   Segment *ParentSegment = nullptr;
   uint64_t HeaderOffset;
-  uint64_t OriginalOffset;
+  uint64_t OriginalOffset = std::numeric_limits<uint64_t>::max();
   uint32_t Index;
+  bool HasSymbol = false;
 
   uint64_t Addr = 0;
   uint64_t Align = 1;
   uint32_t EntrySize = 0;
   uint64_t Flags = 0;
   uint64_t Info = 0;
   uint64_t Link = ELF::SHN_UNDEF;
   uint64_t NameIndex = 0;

 enum SymbolShndxType {
   SYMBOL_SIMPLE_INDEX = 0,
   SYMBOL_ABS = ELF::SHN_ABS,
   SYMBOL_COMMON = ELF::SHN_COMMON,
   SYMBOL_HEXAGON_SCOMMON = ELF::SHN_HEXAGON_SCOMMON,
   SYMBOL_HEXAGON_SCOMMON_2 = ELF::SHN_HEXAGON_SCOMMON_2,
   SYMBOL_HEXAGON_SCOMMON_4 = ELF::SHN_HEXAGON_SCOMMON_4,
   SYMBOL_HEXAGON_SCOMMON_8 = ELF::SHN_HEXAGON_SCOMMON_8,
+  SYMBOL_XINDEX = ELF::SHN_XINDEX,
 };
 
 struct Symbol {
   uint8_t Binding;
   SectionBase *DefinedIn = nullptr;
   SymbolShndxType ShndxType;
   uint32_t Index;
   StringRef Name;
   uint32_t NameIndex;
   uint64_t Size;
   uint8_t Type;
   uint64_t Value;
   uint8_t Visibility;
   bool Referenced = false;
 
   uint16_t getShndx() const;
 };
 
+class SectionIndexSection : public SectionBase {
+  MAKE_SEC_WRITER_FRIEND
+
+private:
+  std::vector<uint32_t> Indexes;
+  SymbolTableSection *Symbols = nullptr;
+
+public:
+  virtual ~SectionIndexSection() {}
+  void addIndex(uint32_t Index) {
+    Indexes.push_back(Index);
+    Size += 4;
+  }
+  void setSymTab(SymbolTableSection *SymTab) { Symbols = SymTab; }
+  void initialize(SectionTableRef SecTable) override;
+  void finalize() override;
+  void accept(SectionVisitor &Visitor) const override;
+
+  SectionIndexSection() {
+    Name = ".symtab_shndx";
+    Align = 4;
+    EntrySize = 4;
+    Type = ELF::SHT_SYMTAB_SHNDX;
+  }
+};
+
 class SymbolTableSection : public SectionBase {
   MAKE_SEC_WRITER_FRIEND
 
   void setStrTab(StringTableSection *StrTab) { SymbolNames = StrTab; }
   void assignIndices();
 
 protected:
   std::vector<std::unique_ptr<Symbol>> Symbols;
   StringTableSection *SymbolNames = nullptr;
+  SectionIndexSection *SectionIndexTable = nullptr;
 
   using SymPtr = std::unique_ptr<Symbol>;
 
 public:
   void addSymbol(StringRef Name, uint8_t Bind, uint8_t Type,
                  SectionBase *DefinedIn, uint64_t Value, uint8_t Visibility,
                  uint16_t Shndx, uint64_t Sz);
-  void addSymbolNames();
+  void prepareForLayout();
   // An 'empty' symbol table still contains a null symbol.
   bool empty() const { return Symbols.size() == 1; }
+  void setShndxTable(SectionIndexSection *ShndxTable) {
+    SectionIndexTable = ShndxTable;
+  }
+  const SectionIndexSection *getShndxTable() const { return SectionIndexTable; }
   const SectionBase *getStrTab() const { return SymbolNames; }
   const Symbol *getSymbolByIndex(uint32_t Index) const;
   Symbol *getSymbolByIndex(uint32_t Index);
   void updateSymbols(function_ref<void(Symbol &)> Callable);
 
   void removeSectionReferences(const SectionBase *Sec) override;
   void initialize(SectionTableRef SecTable) override;
   void finalize() override;

 using object::ELFObjectFile;
 using object::OwningBinary;
 
 template <class ELFT> class ELFBuilder {
 private:
   using Elf_Addr = typename ELFT::Addr;
   using Elf_Shdr = typename ELFT::Shdr;
   using Elf_Ehdr = typename ELFT::Ehdr;
+  using Elf_Word = typename ELFT::Word;
 
   const ELFFile<ELFT> &ElfFile;
   Object &Obj;
 
   void setParentSegment(Segment &Child);
   void readProgramHeaders();
   void initGroupSection(GroupSection *GroupSec);
   void initSymbolTable(SymbolTableSection *SymTab);
public:
   uint64_t SHOffset;
   uint32_t Type;
   uint32_t Machine;
   uint32_t Version;
   uint32_t Flags;
 
   StringTableSection *SectionNames = nullptr;
   SymbolTableSection *SymbolTable = nullptr;
+  SectionIndexSection *SectionIndexTable = nullptr;
 
   void sortSections();
   SectionTableRef sections() { return SectionTableRef(Sections); }
   ConstRange<SectionBase> sections() const {
     return make_pointee_range(Sections);
   }
   Range<Segment> segments() { return make_pointee_range(Segments); }
   ConstRange<Segment> segments() const { return make_pointee_range(Segments); }

llvm/tools/llvm-objcopy/Object.cpp

template <class ELFT> void ELFWriter<ELFT>::writeShdr(const SectionBase &Sec) {
   Shdr.sh_link = Sec.Link;
   Shdr.sh_info = Sec.Info;
   Shdr.sh_addralign = Sec.Align;
   Shdr.sh_entsize = Sec.EntrySize;
 }
 
 SectionVisitor::~SectionVisitor() {}
 
+void BinarySectionWriter::visit(const SectionIndexSection &Sec) {
+  error("Cannot write symbol section index table '" + Sec.Name + "' ");
+}
+
 void BinarySectionWriter::visit(const SymbolTableSection &Sec) {
   error("Cannot write symbol table '" + Sec.Name + "' out to binary");
 }
 
 void BinarySectionWriter::visit(const RelocationSection &Sec) {
   error("Cannot write relocation section '" + Sec.Name + "' out to binary");
 }
 

 void SectionWriter::visit(const StringTableSection &Sec) {
   Sec.StrTabBuilder.write(Out.getBufferStart() + Sec.Offset);
 }
 
 void StringTableSection::accept(SectionVisitor &Visitor) const {
   Visitor.visit(*this);
 }
 
+template <class ELFT>
+void ELFSectionWriter<ELFT>::visit(const SectionIndexSection &Sec) {
+  uint8_t *Buf = Out.getBufferStart() + Sec.Offset;
+  auto *IndexesBuffer = reinterpret_cast<typename ELFT::Word *>(Buf);
+  std::copy(std::begin(Sec.Indexes), std::end(Sec.Indexes), IndexesBuffer);
+}
+
+void SectionIndexSection::initialize(SectionTableRef SecTable) {
+  Size = 0;
+  setSymTab(SecTable.getSectionOfType<SymbolTableSection>(
+      Link,
+      "Link field value " + Twine(Link) + " in section " + Name + " is invalid",
+      "Link field value " + Twine(Link) + " in section " + Name +
+          " is not a symbol table"));
+  Symbols->setShndxTable(this);
+}
+
+void SectionIndexSection::finalize() { Link = Symbols->Index; }
+
+void SectionIndexSection::accept(SectionVisitor &Visitor) const {
+  Visitor.visit(*this);
+}
+
 static bool isValidReservedSectionIndex(uint16_t Index, uint16_t Machine) {
   switch (Index) {
   case SHN_ABS:
   case SHN_COMMON:
     return true;
   }
   if (Machine == EM_HEXAGON) {
     switch (Index) {
     case SHN_HEXAGON_SCOMMON:
     case SHN_HEXAGON_SCOMMON_2:
     case SHN_HEXAGON_SCOMMON_4:
     case SHN_HEXAGON_SCOMMON_8:
       return true;
     }
   }
   return false;
 }
 
+// Large indexes force us to clarify exactly what this function should do. This
+// function should return the value that will appear st_shndx when written out.
 uint16_t Symbol::getShndx() const {
   if (DefinedIn != nullptr) {
+    if (DefinedIn->Index >= SHN_LORESERVE)
+      return SHN_XINDEX;
     return DefinedIn->Index;
   }
   switch (ShndxType) {
   // This means that we don't have a defined section but we do need to
   // output a legitimate section index.
   case SYMBOL_SIMPLE_INDEX:
     return SHN_UNDEF;
   case SYMBOL_ABS:
   case SYMBOL_COMMON:
   case SYMBOL_HEXAGON_SCOMMON:
   case SYMBOL_HEXAGON_SCOMMON_2:
   case SYMBOL_HEXAGON_SCOMMON_4:
   case SYMBOL_HEXAGON_SCOMMON_8:
+  case SYMBOL_XINDEX:
     return static_cast<uint16_t>(ShndxType);
   }
   llvm_unreachable("Symbol with invalid ShndxType encountered");
 }
 
 void SymbolTableSection::assignIndices() {
   uint32_t Index = 0;
   for (auto &Sym : Symbols)
     Sym->Index = Index++;
 }
 
 void SymbolTableSection::addSymbol(StringRef Name, uint8_t Bind, uint8_t Type,
                                    SectionBase *DefinedIn, uint64_t Value,
                                    uint8_t Visibility, uint16_t Shndx,
                                    uint64_t Sz) {
   Symbol Sym;
   Sym.Name = Name;
   Sym.Binding = Bind;
   Sym.Type = Type;
   Sym.DefinedIn = DefinedIn;
+  if (DefinedIn != nullptr)
+    DefinedIn->HasSymbol = true;
   if (DefinedIn == nullptr) {
     if (Shndx >= SHN_LORESERVE)
       Sym.ShndxType = static_cast<SymbolShndxType>(Shndx);
     else
       Sym.ShndxType = SYMBOL_SIMPLE_INDEX;
   }
   Sym.Value = Value;
   Sym.Visibility = Visibility;
   Sym.Size = Sz;
   Sym.Index = Symbols.size();
   Symbols.emplace_back(llvm::make_unique<Symbol>(Sym));
   Size += this->EntrySize;
 }
 
 void SymbolTableSection::removeSectionReferences(const SectionBase *Sec) {
+  if (SectionIndexTable == Sec)
+    SectionIndexTable = nullptr;
   if (SymbolNames == Sec) {
     error("String table " + SymbolNames->Name +
           " cannot be removed because it is referenced by the symbol table " +
           this->Name);
   }
   removeSymbols([Sec](const Symbol &Sym) { return Sym.DefinedIn == Sec; });
 }
 
for (auto &Sym : Symbols) {
     if (Sym->Binding == STB_LOCAL)
       MaxLocalIndex = std::max(MaxLocalIndex, Sym->Index);
   }
   // Now we need to set the Link and Info fields.
   Link = SymbolNames->Index;
   Info = MaxLocalIndex + 1;
 }
 
-void SymbolTableSection::addSymbolNames() {
+void SymbolTableSection::prepareForLayout() {
+  // Add all potential section indexes before file layout so that the section
+  // index section has the approprite size.
+  if (SectionIndexTable != nullptr) {
+    for (const auto &Sym : Symbols) {
+      if (Sym->DefinedIn != nullptr && Sym->DefinedIn->Index >= SHN_LORESERVE)
+        SectionIndexTable->addIndex(Sym->DefinedIn->Index);
+      else
+        SectionIndexTable->addIndex(SHN_UNDEF);
+    }
+  }
   // Add all of our strings to SymbolNames so that SymbolNames has the right
   // size before layout is decided.
   for (auto &Sym : Symbols)
     SymbolNames->addString(Sym->Name);
 }
 
 const Symbol *SymbolTableSection::getSymbolByIndex(uint32_t Index) const {
   if (Symbols.size() <= Index)
GroupSec->addMember(SecTable.getSection(
                    GroupSec->Name + " is invalid"));
   }
 }
 
 template <class ELFT>
 void ELFBuilder<ELFT>::initSymbolTable(SymbolTableSection *SymTab) {
   const Elf_Shdr &Shdr = *unwrapOrError(ElfFile.getSection(SymTab->Index));
   StringRef StrTabData = unwrapOrError(ElfFile.getStringTableForSymtab(Shdr));
+  ArrayRef<Elf_Word> ShndxData;
 
-  for (const auto &Sym : unwrapOrError(ElfFile.symbols(&Shdr))) {
+  auto Symbols = unwrapOrError(ElfFile.symbols(&Shdr));
+  for (const auto &Sym : Symbols) {
     SectionBase *DefSection = nullptr;
     StringRef Name = unwrapOrError(Sym.getName(StrTabData));
 
-    if (Sym.st_shndx >= SHN_LORESERVE) {
+    if (Sym.st_shndx == SHN_XINDEX) {
+      if (SymTab->getShndxTable() == nullptr)
+        error("Symbol '" + Name +
+              "' has index SHN_XINDEX but no SHT_SYMTAB_SHNDX section exists.");
+      if (ShndxData.data() == nullptr) {
+        const Elf_Shdr &ShndxSec =
+            *unwrapOrError(ElfFile.getSection(SymTab->getShndxTable()->Index));
+        ShndxData = unwrapOrError(
+            ElfFile.template getSectionContentsAsArray<Elf_Word>(&ShndxSec));
+        if (ShndxData.size() != Symbols.size())
+          error("Symbol section index table does not have the same number of "
+                "entries as the symbol table.");
+      }
+      Elf_Word Index = ShndxData[&Sym - Symbols.begin()];
+      DefSection = Obj.sections().getSection(
+          Index,
+          "Symbol '" + Name + "' has invalid section index " +
+              Twine(Index));
+    } else if (Sym.st_shndx >= SHN_LORESERVE) {
       if (!isValidReservedSectionIndex(Sym.st_shndx, Obj.Machine)) {
         error(
             "Symbol '" + Name +
             "' has unsupported value greater than or equal to SHN_LORESERVE: " +
             Twine(Sym.st_shndx));
       }
     } else if (Sym.st_shndx != SHN_UNDEF) {
       DefSection = Obj.sections().getSection(
           Sym.st_shndx, "Symbol '" + Name +
-                            "' is defined in invalid section with index " +
+                            "' is defined has invalid section index " +
                             Twine(Sym.st_shndx));
     }
 
     SymTab->addSymbol(Name, Sym.getBinding(), Sym.getType(), DefSection,
                       Sym.getValue(), Sym.st_other, Sym.st_shndx, Sym.st_size);
   }
 }
 
for (const auto &Rel : RelRange) {
     ToAdd.Offset = Rel.r_offset;
     getAddend(ToAdd.Addend, Rel);
     ToAdd.Type = Rel.getType(false);
     ToAdd.RelocSymbol = SymbolTable->getSymbolByIndex(Rel.getSymbol(false));
     Relocs->addRelocation(ToAdd);
   }
 }
 
-SectionBase *SectionTableRef::getSection(uint16_t Index, Twine ErrMsg) {
+SectionBase *SectionTableRef::getSection(uint32_t Index, Twine ErrMsg) {
   if (Index == SHN_UNDEF || Index > Sections.size())
     error(ErrMsg);
   return Sections[Index - 1].get();
 }
 
 template <class T>
-T *SectionTableRef::getSectionOfType(uint16_t Index, Twine IndexErrMsg,
+T *SectionTableRef::getSectionOfType(uint32_t Index, Twine IndexErrMsg,
                                      Twine TypeErrMsg) {
   if (T *Sec = dyn_cast<T>(getSection(Index, IndexErrMsg)))
     return Sec;
   error(TypeErrMsg);
 }
 
 template <class ELFT>
 SectionBase &ELFBuilder<ELFT>::makeSection(const Elf_Shdr &Shdr) {
SectionBase &ELFBuilder<ELFT>::makeSection(const Elf_Shdr &Shdr) {
   case SHT_DYNAMIC:
     Data = unwrapOrError(ElfFile.getSectionContents(&Shdr));
     return Obj.addSection<DynamicSection>(Data);
   case SHT_SYMTAB: {
     auto &SymTab = Obj.addSection<SymbolTableSection>();
     Obj.SymbolTable = &SymTab;
     return SymTab;
   }
+  case SHT_SYMTAB_SHNDX: {
+    auto &ShndxSection = Obj.addSection<SectionIndexSection>();
+    Obj.SectionIndexTable = &ShndxSection;
+    return ShndxSection;
+  }
   case SHT_NOBITS:
     return Obj.addSection<Section>(Data);
   default:
     Data = unwrapOrError(ElfFile.getSectionContents(&Shdr));
     return Obj.addSection<Section>(Data);
   }
 }
 
for (const auto &Shdr : unwrapOrError(ElfFile.sections())) {
     Sec.Size = Shdr.sh_size;
     Sec.Link = Shdr.sh_link;
     Sec.Info = Shdr.sh_info;
     Sec.Align = Shdr.sh_addralign;
     Sec.EntrySize = Shdr.sh_entsize;
     Sec.Index = Index++;
   }
 
+  // If a section index table exists we'll need to initialize it before we
+  // initialize the symbol table because the symbol table might need to
+  // reference it.
+  if (Obj.SectionIndexTable)
+    Obj.SectionIndexTable->initialize(Obj.sections());
+
   // Now that all of the sections have been added we can fill out some extra
   // details about symbol tables. We need the symbol table filled out before
   // any relocations.
   if (Obj.SymbolTable) {
     Obj.SymbolTable->initialize(Obj.sections());
     initSymbolTable(Obj.SymbolTable);
   }
 
template <class ELFT> void ELFBuilder<ELFT>::build() {
   Obj.Machine = Ehdr.e_machine;
   Obj.Version = Ehdr.e_version;
   Obj.Entry = Ehdr.e_entry;
   Obj.Flags = Ehdr.e_flags;
 
   readSectionHeaders();
   readProgramHeaders();
 
+  uint32_t ShstrIndex = Ehdr.e_shstrndx;
+  if (ShstrIndex == SHN_XINDEX)
+    ShstrIndex = unwrapOrError(ElfFile.getSection(0))->sh_link;
+
   Obj.SectionNames =
       Obj.sections().template getSectionOfType<StringTableSection>(
-          Ehdr.e_shstrndx,
+          ShstrIndex,
           "e_shstrndx field value " + Twine(Ehdr.e_shstrndx) +
               " in elf header " + " is invalid",
           "e_shstrndx field value " + Twine(Ehdr.e_shstrndx) +
               " in elf header " + " is not a string table");
 }
 
 // A generic size function which computes sizes of any random access range.
 template <class R> size_t size(R &&Range) {
template <class ELFT> void ELFWriter<ELFT>::writeEhdr() {
   Ehdr.e_phoff = Obj.ProgramHdrSegment.Offset;
   Ehdr.e_flags = Obj.Flags;
   Ehdr.e_ehsize = sizeof(Elf_Ehdr);
   Ehdr.e_phentsize = sizeof(Elf_Phdr);
   Ehdr.e_phnum = size(Obj.segments());
   Ehdr.e_shentsize = sizeof(Elf_Shdr);
   if (WriteSectionHeaders) {
     Ehdr.e_shoff = Obj.SHOffset;
-    Ehdr.e_shnum = size(Obj.sections()) + 1;
+    // """
+    // If the number of sections is greater than or equal to
+    // SHN_LORESERVE (0xff00), this member has the value zero and the actual
+    // number of section header table entries is contained in the sh_size field
+    // of the section header at index 0.
+    // """
+    auto Shnum = size(Obj.sections()) + 1;
+    if (Shnum >= SHN_LORESERVE)
+      Ehdr.e_shnum = 0;
+    else
+      Ehdr.e_shnum = Shnum;
+    // """
+    // If the section name string table section index is greater than or equal
+    // to SHN_LORESERVE (0xff00), this member has the value SHN_XINDEX (0xffff)
+    // and the actual index of the section name string table section is
+    // contained in the sh_link field of the section header at index 0.
+    // """
+    if (Obj.SectionNames->Index >= SHN_LORESERVE)
+      Ehdr.e_shstrndx = SHN_XINDEX;
+    else
       Ehdr.e_shstrndx = Obj.SectionNames->Index;
   } else {
     Ehdr.e_shoff = 0;
     Ehdr.e_shnum = 0;
     Ehdr.e_shstrndx = 0;
   }
 }
 
 template <class ELFT> void ELFWriter<ELFT>::writePhdrs() {
   for (auto &Seg : Obj.segments())
     writePhdr(Seg);
 }
 
 template <class ELFT> void ELFWriter<ELFT>::writeShdrs() {
   uint8_t *B = Buf.getBufferStart() + Obj.SHOffset;
   // This reference serves to write the dummy section header at the begining
   // of the file. It is not used for anything else
   Elf_Shdr &Shdr = *reinterpret_cast<Elf_Shdr *>(B);
   Shdr.sh_name = 0;
   Shdr.sh_type = SHT_NULL;
   Shdr.sh_flags = 0;
   Shdr.sh_addr = 0;
   Shdr.sh_offset = 0;
+  // See writeEhdr for why we do this.
+  uint64_t Shnum = size(Obj.sections()) + 1;
+  if (Shnum >= SHN_LORESERVE)
+    Shdr.sh_size = Shnum;
+  else
     Shdr.sh_size = 0;
+  // See writeEhdr for why we do this.
+  if (Obj.SectionNames != nullptr && Obj.SectionNames->Index >= SHN_LORESERVE)
+    Shdr.sh_link = Obj.SectionNames->Index;
+  else
     Shdr.sh_link = 0;
   Shdr.sh_info = 0;
   Shdr.sh_addralign = 0;
   Shdr.sh_entsize = 0;
 
   for (auto &Sec : Obj.sections())
     writeShdr(Sec);
 }
 
auto Iter = std::stable_partition(
         if (auto RelSec = dyn_cast<RelocationSectionBase>(Sec.get())) {
           if (auto ToRelSec = RelSec->getSection())
             return !ToRemove(*ToRelSec);
         }
         return true;
       });
   if (SymbolTable != nullptr && ToRemove(*SymbolTable))
     SymbolTable = nullptr;
-  if (SectionNames != nullptr && ToRemove(*SectionNames)) {
+  if (SectionNames != nullptr && ToRemove(*SectionNames))
     SectionNames = nullptr;
-  }
+  if (SectionIndexTable != nullptr && ToRemove(*SectionIndexTable))
+    SectionIndexTable = nullptr;
   // Now make sure there are no remaining references to the sections that will
   // be removed. Sometimes it is impossible to remove a reference so we emit
   // an error here instead.
   for (auto &RemoveSec : make_range(Iter, std::end(Sections))) {
     for (auto &Segment : Segments)
       Segment->removeSection(RemoveSec.get());
     for (auto &KeepSec : make_range(std::begin(Sections), Iter))
       KeepSec->removeSectionReferences(RemoveSec.get());

 template <class ELFT> void ELFWriter<ELFT>::finalize() {
   // It could happen that SectionNames has been removed and yet the user wants
   // a section header table output. We need to throw an error if a user tries
   // to do that.
   if (Obj.SectionNames == nullptr && WriteSectionHeaders)
     error("Cannot write section header table because section header string "
           "table was removed.");
 
-  // Make sure we add the names of all the sections.
+  Obj.sortSections();
+
+  // We need to assign indexes before we perform layout because we need to know
+  // if we need large indexes or not. We can assign indexes first and check as
+  // we go to see if we will actully need large indexes.
+  bool NeedsLargeIndexes = false;
+  if (size(Obj.sections()) >= SHN_LORESERVE) {
+    auto Sections = Obj.sections();
+    NeedsLargeIndexes =
+        std::any_of(Sections.begin() + SHN_LORESERVE, Sections.end(),
+                    [](const SectionBase &Sec) { return Sec.HasSymbol; });
+    // TODO: handle case where only one section needs the large index table but
+    // only needs it because the large index table hasn't been removed yet.
+  }
+
+  if (NeedsLargeIndexes) {
+    // This means we definitely need to have a section index table but if we
+    // already have one then we should use it instead of making a new one.
+    if (Obj.SymbolTable != nullptr && Obj.SectionIndexTable == nullptr) {
+      // Addition of a section to the end does not invalidate the indexes of
+      // other sections and assigns the correct index to the new section.
+      auto &Shndx = Obj.addSection<SectionIndexSection>();
+      Obj.SymbolTable->setShndxTable(&Shndx);
+      Shndx.setSymTab(Obj.SymbolTable);
+    }
+  } else {
+    // Since we don't need SectionIndexTable we should remove it and all
+    // references to it.
+    if (Obj.SectionIndexTable != nullptr) {
+      Obj.removeSections([this](const SectionBase &Sec) {
+        return &Sec == Obj.SectionIndexTable;
+      });
+    }
+  }
+
+  // Make sure we add the names of all the sections. Importantly this must be
+  // done after we decide to add or remove SectionIndexes.
   if (Obj.SectionNames != nullptr)
     for (const auto &Section : Obj.sections()) {
       Obj.SectionNames->addString(Section.Name);
     }
-  // Make sure we add the names of all the symbols.
+
+  // Before we can prepare for layout the indexes need to be finalized.
+  uint64_t Index = 0;
+  for (auto &Sec : Obj.sections())
+    Sec.Index = Index++;
+
+  // The symbol table does not update all other sections on update. For
+  // instance, symbol names are not added as new symbols are added. This means
+  // that some sections, like .strtab, don't yet have their final size.
   if (Obj.SymbolTable != nullptr)
-    Obj.SymbolTable->addSymbolNames();
+    Obj.SymbolTable->prepareForLayout();
 
-  Obj.sortSections();
   assignOffsets();
 
   // Finalize SectionNames first so that we can assign name indexes.
   if (Obj.SectionNames != nullptr)
     Obj.SectionNames->finalize();
   // Finally now that all offsets and indexes have been set we can finalize any
   // remaining issues.
   uint64_t Offset = Obj.SHOffset + sizeof(Elf_Shdr);