[llvm-objcopy] Add support for large indexes

[jakehehrlich]

Summary

Because of -ffunction-sections (and maybe other use cases I'm not aware of?) it can occur that we need more than 0xfeff sections but ELF dosn't support that many sections. To solve this problem SHN_XINDEX exists and with it come a whole host of changes for section indexes everywhere. This change adds support for those cases which should allow llvm-objcopy to copy binaries that have an arbitrary number of sections.

[jakehehrlich]

forgot context

[jakehehrlich]

As is there are a few problems but I didn't want to miss another day of review just because I didn't finish this today

1. There are no tests. This needs several tests. Recommendations on how to test this would be appreciated. I've been locally testing using an ELF I created that has 64k symbols and 128k sections but llvm-objcopy takes 5 seconds on that. I can work on optimizing that binary (smaller file, just the right amount of sections, etc...) but that still seems extreme. Additionally I think testing some combination of removal and such would be nice.
2. What if an --add-section pushes the section count over to SHN_LORESERVE? should we synthesize a SectionIndexSection?
3. What if stripping sections pushes the section counter below SHN_LORESERVE? Should we remove the SectionIndexSection because it isn't needed?
4. I wasn't sure if section indexes of symbols below SHN_LORESERVE should have SHN_XINDEX as their index despite it being possible to directly encode them. Should every symbol have SHN_XINDEX for st_shndx?

[jhenderson]

Ah, the joys of Prop74/Large ELFs.

In D42516#987361, @jakehehrlich wrote:

As is there are a few problems but I didn't want to miss another day of review just because I didn't finish this today

1. There are no tests. This needs several tests. Recommendations on how to test this would be appreciated. I've been locally testing using an ELF I created that has 64k symbols and 128k sections but llvm-objcopy takes 5 seconds on that. I can work on optimizing that binary (smaller file, just the right amount of sections, etc...) but that still seems extreme. Additionally I think testing some combination of removal and such would be nice.

I don't think 5 seconds is all that unreasonable, due to the size of the ELF, but it may be worth optimizing anyway. Maybe you could have a little python script that generates a YAML file for yaml2obj (assuming yaml2obj can handle very large ELFs).

2. What if an --add-section pushes the section count over to SHN_LORESERVE? should we synthesize a SectionIndexSection?
3. What if stripping sections pushes the section counter below SHN_LORESERVE? Should we remove the SectionIndexSection because it isn't needed?

I think we might want to rebuild this section every time, prior to finalizing the ELF. Effectively, the read-in version uses this section only to interpret section indexes, and then a new one is created from scratch, if needed, afterwards. We could refuse to create it, but I wouldn't recommend that, personally. The gABI definitely suggests that this process should only be followed for larger ELFs, and not for those that don't need it.

4. I wasn't sure if section indexes of symbols below SHN_LORESERVE should have SHN_XINDEX as their index despite it being possible to directly encode them. Should every symbol have SHN_XINDEX for st_shndx?

I think SHN_XINDEX should only be used where the value can't be represented (i.e. >= SHN_LORESERVE). The ELF gABI says:

"If this member contains SHN_XINDEX, then the actual section header index is too large to fit in this field."

Just to check, which document are you using for the quotes? It would be good to include the URLs to the parts of the documents.

One general point: theoretically, each symbol table could have its own SYMTAB_SHNDX section. The obvious case for this would be the static symbol table and the dynamic symbol table. The corresponding section is indicated by the sh_link field of the SYMTAB_SHNDX section, so we should be using that to establish a link. I think that implies that the SYMTAB_SHNDX section pointer should be a member of the symbol table class, not of the Object.

tools/llvm-objcopy/Object.cpp

73 ↗

(On Diff #131383)

I'd call this the "symbol section index table" for a bit more clarity.

159 ↗

(On Diff #131383)

Full stop.

267–269 ↗

(On Diff #131383)

I think this should have a value SHN_UNDEF unless the index is >= SHN_LORESERVE.

546–553 ↗

(On Diff #131383)

It seems to me like this block should only happen the first time we encounter a SHN_XINDEX symbol. After that, we should already have the data, and should be able to load from it directly.

554 ↗

(On Diff #131383)

Somewhere, we should check that the symtab shndx section has the same number of entries as the corresponding symbol table.

656 ↗

(On Diff #131383)

I'd avoid calling references to the symtab shndx section "Shndx" as that's a common abbreviation for section header index, which could lead to confusion or ambiguity in places. I'd recommend calling it ShndxSection or similar.

811 ↗

(On Diff #131383)

Comment looks like it's wrapped early?

823 ↗

(On Diff #131383)

Fix comment wrapping here too.

854–859 ↗

(On Diff #131383)

I feel like having these quotes duplicated is not great. I wonder whether it's a sign that the null shdr should be constructed in the writeEhdr function, so that the decisions only need making the once? Thoughts?

tools/llvm-objcopy/Object.h

373 ↗

(On Diff #131383)

I'd rename this member to SectionIndexTable (or ShndxTable)

378 ↗

(On Diff #131383)

I'd rename this function "setShndxTable" since setShndx implies you're setting the section header index of the section.

[jakehehrlich]

1. Still no tests
2. changed error message for clarity
3. fixed typos
4. populated the section index table with SHN_UNDEF for values < SHN_LORESERVE
5. computed address of section index table data just once in initSymbolTable
6. avoided Shndx use for section index table name
7. I haven't updated "SectionIdexes" to "SectionIndexTable" because I ran out of time. I'll get back to that tomorrow.

tools/llvm-objcopy/Object.cpp

811 ↗

(On Diff #131383)

I want "SHN_LORESERVE (0xff00)" to stay together which means I have to wrap early. It looksreally odd if you wrap the parenthsies to the next line. Since this is a direct quote I don't want to take the "(0xff00)" out to better resolve that issue.

854–859 ↗

(On Diff #131383)

I'm a bit conflicted on this one. I like having the logic for writing the whole section header table in one place because it makes the logic of "do we write the section header table out or not" more succinct. I also however agree with your claim that quoting this twice is annoying.

I can think of two options here:

1. remove the comments in the second case and just leave a URL
2. move this to writeEhdr just like you said

[jakehehrlich]

Changed SectionIndexes to SectionIndexTable everywhere

[jhenderson]

tools/llvm-objcopy/Object.cpp

705 ↗

(On Diff #131918)

properlly -> properly

1085 ↗

(On Diff #131918)

This line doesn't read right, and I think you should avoid using "S/shndx" here. Refer to it as the symbol section index table or similar. It also looks like the last sentence is incomplete.

1090 ↗

(On Diff #131918)

">=" here?

1112 ↗

(On Diff #131918)

Typo in "SectionIndxes" and missing full-stop.

1118–1119 ↗

(On Diff #131918)

It's not clear to me what this comment is saying. Why would symbols keep sections updated or not as the case may be?

854–859 ↗

(On Diff #131383)

I think I'd prefer a third option actually: remove these comments, and replace with a reference to the standard quote in writeEhdr(), i.e. "// See writeEhdr for why we do this" or similar.

[jakehehrlich]

Hey I'm back!

This change fixes previous comments by James and adds a test. Other tests that are needed yet still

1. Make sure section index table is removed when not needed
2. Make sure section index table is added when it is needed
3. Check error for binary output
4. Check initialization errors for section index table
5. To the existing test add checks for the appropriate fields for section index table
6. Check error for case when symbol has SHN_XINDEX index but not

If you can think of more tests please inform.

[jhenderson]

In D42516#1014046, @jakehehrlich wrote:

3. Check error for binary output

What error would you expect in this case? Why wouldn't it just work?

6. Check error for case when symbol has SHN_XINDEX index but not

I think you messed up the end of this sentence :)

How about tests for attempting to strip the SYMTAB_SHNDX table? I.e. We should refuse to do so, if there are too many sections. An interesting edge case is adding sections such that we now require the table, but also explicitly stripping the symtab_shndx table if it exists. I'm not clear on the behaviour here, but I guess we should throw away the old one and build one from scratch in this case.

Can't think of any other cases off the top of my head.

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

1 ↗

(On Diff #135194)

Lower-case .s is more common for test files.

47 ↗

(On Diff #135194)

Could this be SECS: Index: 65542?

Similar for symbols.

tools/llvm-objcopy/Object.cpp

661 ↗

(On Diff #135194)

Unnecessary braces.

896–901 ↗

(On Diff #135194)

Unfortunately, I think you've gone the wrong way round here! The quote refers to "this member" which only makes sense if it's talking about the Elf Header, so this and the other quote belong in writeEhdr.

1115 ↗

(On Diff #135194)

Could this loop be improved to not loop over every section? You only need to loop over sections from Index >= SHN_LORESERVE upwards, don't you? Or is this vector not ordered by section index?

1118 ↗

(On Diff #135194)

break here after this is set.

1124 ↗

(On Diff #135194)

definitly -> definitely

tools/llvm-objcopy/Object.h

369 ↗

(On Diff #135194)

The ELF gABI suggests that the name ".symtab_shndx" is used for the SHT_SYMTAB_SHNDX section.

An old commit from 2014 seems to have changed the name emitted by MC from this to ".symtab_shndxr". I'm not sure why the name changed there. Searching for that string online only yields that commit and references to the LLVM code-base, so it doesn't look like there's prior art for that name. Independently of this change, I think finding out why the name was changed (and change it back if appropriate) would be a sensible exercise.

394 ↗

(On Diff #135194)

getShndx() -> getShndxTable(), since getShndx() implies getting the section index for this section, which it doesn't (see also setShndx).

378 ↗

(On Diff #131383)

Ping on this comment?

[jhenderson]

One other point - it would be good to compare the performance of llvm-objcopy to GNU objcopy in this case, and if we're a lot worse, run a profiler at some point to identify what we're doing that makes things worse.

[jakehehrlich]

In D42516#1014317, @jhenderson wrote:

One other point - it would be good to compare the performance of llvm-objcopy to GNU objcopy in this case, and if we're a lot worse, run a profiler at some point to identify what we're doing that makes things worse.

I don't know which cases this happens in but the reason this feature was requested is because under some cases objcopy has O(n^2) behavior for sections. I have one preliminary data point that makes me hopeful which is that the unoptimized debug llvm-objcopy is only about twice as slow as the optimized GNU objcopy is right now. e.g. I think just doing a release build would bump us to comparable performance and then we'd still have room to profile and optimize after that.

[emaste]

In D42516#1014317, @jhenderson wrote:

One other point - it would be good to compare the performance of llvm-objcopy to GNU objcopy in this case, and if we're a lot worse, run a profiler at some point to identify what we're doing that makes things worse.

If someone's running performance comparisons it would be good to also include ELF Tool Chain's version.
https://sourceforge.net/p/elftoolchain/wiki/Home/

(We replaced (most of) binutils with ELF Tool Chain in FreeBSD.)

[jakehehrlich]

What error would you expect in this case? Why wouldn't it just work?

It depends on the endianness of the system we're writing to so it the BinaryWriter should throw an error if you try to write an allocated one. Later (in a seperate patch) we'll need to support large indexes for dynamic symbols which I plan on handling the general way we've handled dynamic stuff (by just copying). At that point the error will become impossible until we have section editing.

Check error for case when symbol has SHN_XINDEX index but not...

That was meant to be "Check error for case when symbol has SHN_XINDEX index but no symbol index table". There's an error in the code but it isn't checked that its actually thrown in that case at the moment.

How about tests for attempting to strip the SYMTAB_SHNDX table? I.e. We should refuse to do so, if there are too many sections. An interesting edge case is adding sections such that we now require the table, but also explicitly stripping the symtab_shndx table if it exists. I'm not clear on the behaviour here, but I guess we should throw away the old one and build one from scratch in this case.

I think they should be allowed to strip it but if it winds up being needed we should add it in (which is what we do now). So there shouldn't be an error, it should just wind up having a SYMTAB_SHNDX table despite the fact that they stripped it. We should have a test for this case to make sure it's acceptable. We should also have a case for the edge case you mention.

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

47 ↗

(On Diff #135194)

For sections I can do this but for symbols I can't. Also I'm glad you had me do this test. Somewhere in the output of llvm-readobj there is an extra occurence of "Name" than there should be. The largest section index is 65540 which means that there should be 65541 occurrences of "Name:" which means this test had an issue with it. It turns out that at the start of every llvm-readobj output there is a field "LoadName:" which triggers the count on this. So instead I'll use the Index number for sections and "Symbol {" count for symbols.

tools/llvm-objcopy/Object.cpp

1115 ↗

(On Diff #135194)

You have this right. It can also exit early if it finds one because we'll have to reassign indexes later anyway. Good catch.

[jakehehrlich]

I spent some time today figuring out how to a) improve the time it takes the test to run and b) make the uploaded binary as small as possible. I'm uploading a binary so that not every test has to regenerate the same file (which dominates the running time of generating this file). I tried to make this binary as small and as compressible as possible. I got the compressed archive down to 147 kb which I think is acceptable. On my machine the total running time of decompressing, running llvm-objcopy, and then checking the data, is about 1.6 seconds which is acceptably fast in my opinion. This problem was much more solvable than when I implemented 64-bit symbol offsets for archives.

For some details on the file:

1. it has 65541 sections, 65537 symbols
2. every symbol is named "x" but is technically a unique section. Each symbol is defined in a different section
3. every symbol is named "x" but is technically a unique section.

The uncompressed binary is about 6 MB which is about a 98% compression ratio. I can make the whole thing a bit smaller if I only use a small number of symbols though.

[jakehehrlich]

You can download the zip file that I'm using here: https://drive.google.com/file/d/1u6W1mUHkFBPsLzEV4u50M_BeiPKMyipM/view?usp=sharing

I'll follow up later with the other mentioned tests. The plan is to have them each uncompress the binary.

[emaste]

In D42516#1015414, @jakehehrlich wrote:

You can download the zip file that I'm using here: https://drive.google.com/file/d/1u6W1mUHkFBPsLzEV4u50M_BeiPKMyipM/view?usp=sharing

Thanks for this. It demonstrates some particularly poor behaviour in ELF Tool Chain's elfcopy (so, if anyone's comparing objcopy versions, there's not much value in including ELF Tool Chain right now).

[jhenderson]

Code looks okay to me, aside from a couple of comment nits. I'll hold off approving though, since I'd like to see the other tests.

tools/llvm-objcopy/Object.cpp

875 ↗

(On Diff #135351)

Weird wrapping again?

1131 ↗

(On Diff #135351)

Have you wrapped slightly early here? I think we can get this comment down to 2 lines.

[jakehehrlich]

In D42516#1015427, @emaste wrote:

In D42516#1015414, @jakehehrlich wrote:

You can download the zip file that I'm using here: https://drive.google.com/file/d/1u6W1mUHkFBPsLzEV4u50M_BeiPKMyipM/view?usp=sharing

Thanks for this. It demonstrates some particularly poor behaviour in ELF Tool Chain's elfcopy (so, if anyone's comparing objcopy versions, there's not much value in including ELF Tool Chain right now).

I had to commit many atrocities to make that file. I actually have a desire for a yaml2obj like tool that would let me construct ELFs more succinctly. That binary was produced by getting as close as I could with a generated .s and then using many different tools to tweak the results. It wasn't pretty.

[jakehehrlich]

1. Make sure section index table is removed when not needed
2. Make sure section index table is added when it is needed
3. Check error for binary output
4. Check initialization errors for section index table
5. To the existing test add checks for the appropriate fields for section index table
6. Check error for case when symbol has SHN_XINDEX index but no section index table exists

So these tests are hard to fulfill. 1. is done. 2. isn't possible because there is no way to a) add a symbol to a section or b) add a section before another section. As soon as symbols can be added or section position can be edited this will need to be tested. 3. isn't possible because there isn't really a way (short of using dd to make a binary modification) to make the section header table allocated. Also eventually dynamic section header tables will need to be supported and such a test will become impossible until section editing becomes a thing because allocated section header tables will be treated the way dynamic sections will be. Checking the initialization error also requires binary editing the link of the section index table (Again once we can edit sections, that will be a proper test). I added the extra checks for the section header index fields. It's not an ideal test but to test that

So unless you have other test ideas I think these tests are the best I can do. They're better than a basic smoke test but they're not 100% complete.

[jakehehrlich]

Added tests. I think this is about as good as it's going to get without adding other features to llvm-objcopy.

[jhenderson]

Two comment wrapping issues are still outstanding (I've pinged them).

In D42516#1021711, @jakehehrlich wrote:

It's not an ideal test but to test that

I think you forgot to end a sentence :) Also I don't see any comment about number 6?

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

41 ↗

(On Diff #136227)

SHT_SYMTAB_SHNDX?

46 ↗

(On Diff #136227)

I think checking the size here would be wise. It should be easy to do, since you know how many symbols there are. A comment describing the calculation would be helpful too, i.e. something like "# Size == 4 * symbol count".

tools/llvm-objcopy/Object.cpp

875 ↗

(On Diff #135351)

Ping

1131 ↗

(On Diff #135351)

Ping

[jakehehrlich]

1. Fixed wrapping
2. Added size of .symtab_shndx to test
3. Fixed section type so it has the full type name

[jakehehrlich]

In D42516#1021711, @jakehehrlich wrote:

It's not an ideal test but to test that

I think you forgot to end a sentence :)

I don't remember exactly what I wanted to say but basically I'm not sure adding more tests is worth it because there are many challenges in adding this sort test.

Also I don't see any comment about number 6?

It requires uploading another binary which isn't ideal. It's also hard to produce.

[jhenderson]

LGTM.

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

+RUN: unzip -p %p/Inputs/many-sections.o.zip > %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/trunk/test/tools/llvm-objcopy/many-sections.test

+RUN: unzip -p %p/Inputs/many-sections.o.zip > %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/trunk/test/tools/llvm-objcopy/remove-shndx.test

+RUN: unzip -p %p/Inputs/many-sections.o.zip > %t
+RUN: llvm-objcopy -R=.symtab_shndxr %t %t2
+RUN: llvm-readobj -sections %t2 | FileCheck %s
+
+CHECK: Name: .symtab_shndx (
+

llvm/trunk/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: unzip -p %p/Inputs/many-sections.o.zip > %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/trunk/tools/llvm-objcopy/Object.h

 class SectionBase;
 class Section;
 class OwnedDataSection;
 class StringTableSection;
 class SymbolTableSection;
 class RelocationSection;
 class DynamicRelocationSection;
 class GnuDebugLinkSection;
+class SectionIndexSection;
 class Segment;
 class Object;
 
 class SectionTableRef {
 private:
   MutableArrayRef<std::unique_ptr<SectionBase>> Sections;
 
 public:
   using iterator = pointee_iterator<std::unique_ptr<SectionBase> *>;
 
   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 SectionIndexSection &Sec) = 0;
 };
 
 class SectionWriter : public SectionVisitor {
 protected:
   FileOutputBuffer &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 SectionIndexSection &Sec) override = 0;
 
   SectionWriter(FileOutputBuffer &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 SectionIndexSection &Sec) override;
 
   ELFSectionWriter(FileOutputBuffer &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 SectionIndexSection &Sec) override;
   BinarySectionWriter(FileOutputBuffer &Buf) : SectionWriter(Buf) {}
 };
 
 class Writer {
 protected:
   StringRef File;
   Object &Obj;
   std::unique_ptr<FileOutputBuffer> BufPtr;

 
 class SectionBase {
 public:
   StringRef Name;
   Segment *ParentSegment = nullptr;
   uint64_t HeaderOffset;
   uint64_t OriginalOffset;
   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;
 
   uint16_t getShndx() const;
 };
 
+class SectionIndexSection : public SectionBase {
+  MAKE_SEC_WRITER_FRIEND
+
+private:
+  std::vector<uint32_t> Indexes;
+  SymbolTableSection *Symbols;
+
+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";
+    OriginalOffset = std::numeric_limits<uint64_t>::max();
+    Align = 4;
+    EntrySize = 4;
+    Type = ELF::SHT_SYMTAB_SHNDX;
+  }
+};
+
 class SymbolTableSection : public SectionBase {
   MAKE_SEC_WRITER_FRIEND
 
   void setStrTab(StringTableSection *StrTab) { SymbolNames = StrTab; }
 
 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();
+  void setShndxTable(SectionIndexSection *ShndxTable) { SectionIndexTable = ShndxTable; }
+  const SectionBase *getShndxTable() const { return SectionIndexTable; }
   const SectionBase *getStrTab() const { return SymbolNames; }
   const Symbol *getSymbolByIndex(uint32_t Index) const;
   void removeSectionReferences(const SectionBase *Sec) override;
   void localize(std::function<bool(const Symbol &)> ToLocalize);
   void initialize(SectionTableRef SecTable) override;
   void finalize() override;
   void accept(SectionVisitor &Visitor) const override;
 

 using object::ELFFile;
 using object::ELFObjectFile;
 
 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 initSymbolTable(SymbolTableSection *SymTab);
   void readSectionHeaders();
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;
 
   Object(std::shared_ptr<MemoryBuffer> Data) : OwnedData(Data) {}
   virtual ~Object() = default;
 
   void sortSections();
   SectionTableRef sections() { return SectionTableRef(Sections); }
   ConstRange<SectionBase> sections() const {
     return make_pointee_range(Sections);

llvm/trunk/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 *Indexes = reinterpret_cast<typename ELFT::Word *>(Buf);
+  std::copy(std::begin(Sec.Indexes), std::end(Sec.Indexes), Indexes);
+}
+
+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 proper value of st_shndx.
 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::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) {
-    if (Shndx >= SHN_LORESERVE)
-      Sym.ShndxType = static_cast<SymbolShndxType>(Shndx);
-    else
-      Sym.ShndxType = SYMBOL_SIMPLE_INDEX;
-  }
+  if (DefinedIn != nullptr)
+    DefinedIn->HasSymbol = true;
   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);
   }
   auto Iter =
       std::remove_if(std::begin(Symbols), std::end(Symbols),
                      [=](const SymPtr &Sym) { return Sym->DefinedIn == Sec; });
void SymbolTableSection::localize(
   // Lastly we fix the symbol indexes.
   uint32_t Index = 0;
   for (auto &Sym : Symbols)
     Sym->Index = Index++;
 }
 
 void SymbolTableSection::initialize(SectionTableRef SecTable) {
   Size = 0;
+
   setStrTab(SecTable.getSectionOfType<StringTableSection>(
       Link,
       "Symbol table has link index of " + Twine(Link) +
           " which is not a valid index",
       "Symbol table has link index of " + Twine(Link) +
           " which is not a string table"));
 }
 
 void SymbolTableSection::finalize() {
   // Make sure SymbolNames is finalized before getting name indexes.
   SymbolNames->finalize();
 
   uint32_t MaxLocalIndex = 0;
   for (auto &Sym : Symbols) {
     Sym->NameIndex = SymbolNames->findIndex(Sym->Name);
     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)
template <class ELFT> void ELFBuilder<ELFT>::readProgramHeaders() {
   setParentSegment(ElfHdr);
   setParentSegment(PrHdr);
 }
 
 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.");
+      }
+      auto Index = ShndxData[&Sym - Symbols.begin()];
+      DefSection = Obj.sections().getSection(
+          Index,
+          "Symbol '" + Name + "' is defined in invalid section with 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(
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 we have a SectionIndexTable we need to initialize it before the symbol
+  // table because the symbol table will need it to properly read in symbols.
+  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,
-          "e_shstrndx field value " + Twine(Ehdr.e_shstrndx) +
+          ShstrIndex,
+          "e_shstrndx field value " + Twine(ShstrIndex) +
               " in elf header " + " is invalid",
-          "e_shstrndx field value " + Twine(Ehdr.e_shstrndx) +
+          "e_shstrndx field value " + Twine(ShstrIndex) +
               " 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) {
   return static_cast<size_t>(std::end(Range) - std::begin(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 *Buf = BufPtr->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 *>(Buf);
   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.
+  auto 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) {
+    uint64_t Index = SHN_LORESERVE;
+    auto Sections = Obj.sections();
+    auto LargeIndexSections =
+        make_range(Sections.begin() + SHN_LORESERVE, Sections.end());
+    for (auto &Sec : LargeIndexSections) {
+      Sec.Index = Index++;
+      if (Sec.HasSymbol) {
+        NeedsLargeIndexes = true;
+        break;
+      }
+    }
+    // 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
+    // already have one then we should use it instead of making a new one.
+    if (Obj.SymbolTable != nullptr && Obj.SectionIndexTable == nullptr) {
+      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(
+          [](const SectionBase &Sec) { return Sec.Type == SHT_SYMTAB_SHNDX; });
+    }
+  }
+
+  // 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.
+
+  // 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);