[llvm] Add symbol table support to llvm-objcopy

[jakehehrlich]

Summary

This change depends on D36196

This change adds support for SHT_SYMTAB sections

[jakehehrlich]

Forgot one thing

[jakehehrlich]

I updated this to match the latest code in D33964

[jakehehrlich]

I swapped the order of these diffs around so that binary output comes first now.

[jakehehrlich]

Updated this yet again to match revisions made to other diffs. This change only depends on a diff that already has an LGTM so it should be ready for review.

[jhenderson]

Nit: full stops at the end of all comments, please.

In addition to the inline comments, I'm concerned about the behaviour for section symbols, which do not have a name directly associated with them (they could be considered to have the section name, but this is not usually recorded in the string table). As things stand, it looks to me like only one section symbol will be added, because the others will all have the same (empty) Name, and so will clash in the StringMap.

I'm also not a fan of the use of Symbols and FinalSymbols as it means that there are two copies of the symbol table, which could become quite a large additional memory overhead (also such similar names don't sit well with me). Not thought about this too much, but I could think of a couple of other options: 1) Turn the FinalSymbols vector into a vector of pointers into the Symbols map, ordered in the output order; 2) Perhaps combined with my suggested alternative algorithm for finalizing the symbol table order above, simply record the new index in the symbols in the map, and then iterate over the map when writing, jumping to the appropriate location as needed.

test/tools/llvm-objcopy/symbol-copy.test

92

For completeness, please check that there are no more symbols by checking the end of the symbol table has been reached.

tools/llvm-objcopy/Object.cpp

124

I don't think weak and global symbols have to be ordered in any specific order with respect to each other, but this will sort all STB_WEAK symbols to be after the STB_GLOBAL symbols.

137

Could you comment why you do the double sorting, please?

I assume the aim is to maintain the symbol order as much as possible, but moving symbols that are now local/global to the correct place in the symbol table, but it would be good to explicitly say something like that.

Alternatively, isn't it possible to combine the two comparators and then run a single sort?

Perhaps an even better alternative is to use a different algorithm entirely, namely to insert the symbols in the vector in the correct order already - simply record where the last STB_LOCAL was and insert it there if local, or at the end if not. This recorded location can then also be use to set the Info field appropriately, without needing to do a search.

146

Could this become addSymbolNames, please, as that's more descriptive.

208

This could cause a crash if the the sh_link field is corrupt and is higher than the number of sections, or is unset.

211

Could this error message be improved to include the symbol and supposed string table index, please?

219

What is Sym.st_shndx is not a valid section?

406–407

You appear to have lost a comment here.

tools/llvm-objcopy/Object.h

120

Is this comment correct? The problem isn't that we're changing from ELFT to ELFT, it's because we are changing from ELFT to some internal representation and then back again.

134

Do we need this function for now?

[jakehehrlich]

1. I fixed a lot of little things that James mentioned
2. I removed a the "removeSymbol" method because, as James noted, it isn't needed right now. It will be needed for strip. Consequently we don't have to reassign indexes to symbols which addresses a whole slew of problems that were raised. This combined with James' idea on how to write the symbol table simplified the code and removed many of the concerns around FinalSymbols (like sorting, extra memory usage, what to name that thing, etc...). This however side-steps what we will need to do in the future so I'd like to recommend two possible plans for adding symbols at a later date in place of adding code to handle reassigning indexes.

Plan 1) Keep the same writeSection algorithm in this latest diff (the algorithm proposed by James) and then locally create an std::vector<Symbol*> in finalize that can be sorted and then iterated though to assign new indexes. The sorting algorithm would use a comparision that would make any STB_LOCAL symbol come before but would ignore STB_WEAK vs STB_GLOBAL in order to better maintain the original order (addressing a particular concern raised by James). The comparison would compare by original index when binding was not an issue.

Pros) Only adds 8-bytes to memory usage for each symbol and that memory is only allocated for the duration that symbols are being finalized.
Cons) Writes happen out of order and there will cause some less than ideal behavior write caching behavior. Sorting increases finalization time for symbol tables also.

Plan 2) Make Symbol an intrusive list node type. When adding a symbol it must then be added to the Symbols map but also to the intrusively constructed list. A pointer to the head of this list would be maintained. When adding and removing symbols the last local symbol is kept track of. This lets us quickly add local symbols to the right place so that we never have to worry about sorting them in any way. As local symbols are removed we can update the pointer to the last local symbol.

Pros) The symbol table is written in order, no sorting is needed so finalization becomes linear. This also means we only need to do 2 passes over the symbols for the whole thing. The last local symbol is kept track of by the SymbolTableSection so finalizing the Info field is easy (It's the index of the local symbol whose's next symbol is not local).
Cons) It's a bit more complicated. It uses like 16-bytes (or more?) of space per symbol and that space is is used for the whole duration of llvm-objcopy's life. Each constant time operation will likely be more expensive.

My proposal is that some veriation of one of these 2 methods be used to add removeSymbol to SymbolTableSection just before symbol stripping is needed.

[jakehehrlich]

In addition to the inline comments, I'm concerned about the behaviour for section symbols, which do not have a name directly associated with them (they could be considered to have the section name, but this is not usually recorded in the string table). As things stand, it looks to me like only one section symbol will be added, because the others will all have the same (empty) Name, and so will clash in the StringMap.

What are section symbols? It doesn't sound like I have supported them and I am not aware of what they are. I wasn't able to find them online. These are some kind of symbol for which distinct symbols can have the same name? That seems to spell problems for my overall design here.

[jhenderson]

In D34167#849321, @jakehehrlich wrote:

Plan 1) Keep the same writeSection algorithm in this latest diff (the algorithm proposed by James) and then locally create an std::vector<Symbol*> in finalize that can be sorted and then iterated though to assign new indexes. The sorting algorithm would use a comparision that would make any STB_LOCAL symbol come before but would ignore STB_WEAK vs STB_GLOBAL in order to better maintain the original order (addressing a particular concern raised by James). The comparison would compare by original index when binding was not an issue.

Pros) Only adds 8-bytes to memory usage for each symbol and that memory is only allocated for the duration that symbols are being finalized.
Cons) Writes happen out of order and there will cause some less than ideal behavior write caching behavior. Sorting increases finalization time for symbol tables also.

Which writes are we talking about here? If we've sorted things, then we'll be writing contiguously into the buffer.

Plan 2) Make Symbol an intrusive list node type. When adding a symbol it must then be added to the Symbols map but also to the intrusively constructed list. A pointer to the head of this list would be maintained. When adding and removing symbols the last local symbol is kept track of. This lets us quickly add local symbols to the right place so that we never have to worry about sorting them in any way. As local symbols are removed we can update the pointer to the last local symbol.

Pros) The symbol table is written in order, no sorting is needed so finalization becomes linear. This also means we only need to do 2 passes over the symbols for the whole thing. The last local symbol is kept track of by the SymbolTableSection so finalizing the Info field is easy (It's the index of the local symbol whose's next symbol is not local).
Cons) It's a bit more complicated. It uses like 16-bytes (or more?) of space per symbol and that space is is used for the whole duration of llvm-objcopy's life. Each constant time operation will likely be more expensive.

My biggest concern with this is that we have to be careful not to change the symbol binding of a symbol in place, or if we did, we would need to move it within the list. If that gets forgotten, then the order will be wrong.

My proposal is that some veriation of one of these 2 methods be used to add removeSymbol to SymbolTableSection just before symbol stripping is needed.

My initial instinct is that we should take the simpler approach (option 1), as it is less likely to go wrong as more functionality is added to llvm-objcopy. That being said, I suspect that in the general case, people aren't going to make many changes to symbol bindings, so I'd say that the order of existing symbols is unlikely to change much, making a general sort probably rather inefficient. This then suggests option 2 to be better!

Do we need a map at all? Is removing individual symbols by name something that needs to be supported, and is it up to objcopy to ensure that there are no two symbols with the same name? Could we actually maintain a single vector, where the index in the vector is the symbol's index (with something recording the last local). Then, when adding symbols, insert in the corresponding place. Changing a symbol's binding from weak/global to local or vice versa becomes a move within the vector. I think this means that there would only be a memory overhead of a std::vector, plus one size_t value.

One thing that occurred to me with regards to modifying the symbol table ordering that might be somewhat related to this - we have to be wary that there might be relocations (and possibly other section contents), that refer to symbol indexes, so we need to track those if we anticipate the symbol table contents changing.

In D34167#849325, @jakehehrlich wrote:

What are section symbols? It doesn't sound like I have supported them and I am not aware of what they are. I wasn't able to find them online. These are some kind of symbol for which distinct symbols can have the same name? That seems to spell problems for my overall design here.

Section symbols are local symbols with type STT_SECTION. They do not have a name as such (their st_name field is 0, so points to the empty string), but most tools that I've encountered use the name of their corresponding section (identified by st_shndx) when displaying them. They are used by relocations primarily, to allow section relative relocations, i.e. references to some offset into a section that doesn't necessarily have its own symbol. The only thing that you have to be aware of for them in this area is that they don't have unique names. This suggests to me that we shouldn't be using the StringMap (see my above comment).

tools/llvm-objcopy/Object.cpp

226

invalid section index of -> invalid section with index

I think that reads better.

tools/llvm-objcopy/Object.h

120

The first line now doesn't read well at all - I'm not sure what you're trying to say any more with it.

[jakehehrlich]

Which writes are we talking about here? If we've sorted things, then we'll be writing contiguously into the buffer.

I was considering having "FinalSymbols" be a local variable. If it isn't local then we can write contiguously. If it is local then all it helps us do is assign the indexes and we would have to do things noncontiguously. But I think removing the StringMap all together as you recommended is likely a better solution.

My biggest concern with this is that we have to be careful not to change the symbol binding of a symbol in place, or if we did, we would need to move it within the list. If that gets forgotten, then the order will be wrong.

Eh, yeah. That is a fair concern. I'd rather allow for as many modifications to occur as possible. I think I prefer sorting now, especially since this latest diff doesn't have a StringMap

My initial instinct is that we should take the simpler approach (option 1), as it is less likely to go wrong as more functionality is added to llvm-objcopy. That being said, I suspect that in the general case, people aren't going to make many changes to symbol bindings, so I'd say that the order of existing symbols is unlikely to change much, making a general sort probably rather inefficient. This then suggests option 2 to be better!

I think we can get the best of both worlds actually. You pointed that people won't make changes to symbol bindings or symbol order. When these things do change they likely won't change very much. Well lots of sorting algorithms are linear under these conditions. So we just need to use a sorting algorithm that takes advantage of this. Unfortunately there don't seem to be any ready implementations of such algorithms in the standard library or in llvm.

This diff:

1. Should have fixed a couple nits by James
2. I reworked the algorithm taking the "do we need the StringMap" idea seriously. All operations should happen in ideal running time, the implementation is simple, and caching behavior should be better than previous considered options. The only real downside is that now symbols have to be allocated individually.

The primary reason for the StringMap before was so that when handling relocations we could look up symbol indexes (see here: https://reviews.llvm.org/D36554). Strings seemed like a better option because I thought symbol names were unique. Symbol names, unlike symbol indexes, will not change on strip operations so strings seemed like better identifiers than indexes. James pointed out however that symbol names are not necessarily unique so we can't do that. So we need another way to look up indexes of the finalized symbols. If we agree that before modification of the symbol table that symbol indexes agree with original symbol indexes then we can look up pointers to symbols very quickly. For relocation sections rather than storing a symbol name we can store a pointer to the symbol.

When removing symbols we will not remove symbols one by one but instead remove a whole bunch of symbols all at once. When we do this we can reassign new Index values to each symbol so that the internal symbol index (not the original index) stays consistent with the vector the symbols are being stored in. This means that if Sym is returned by the getSymbolByIndex method that Sym->Index will agree with the index passed to getSymbolByIndex. This reassignment of indexes won't affect relocations since relocations will grab pointers to the symbols during construction before any modification has occured.

[jhenderson]

To clarify, because I may have missed it, but are we deferring sorting for now, to a later change when it becomes important? I don't see where it's happening currently!

tools/llvm-objcopy/Object.cpp

108

Do we need an explicit this here now that this class isn't templated?

[jakehehrlich]

In D34167#851158, @jhenderson wrote:

To clarify, because I may have missed it, but are we deferring sorting for now, to a later change when it becomes important? I don't see where it's happening currently!

It's not currently happening. I figured once it's clear how symbols are being altered we can add the sorting algorithm. I'll add it now if you'd like, it just seemed like it's unnecessary right now. Your call.

[jakehehrlich]

tools/llvm-objcopy/Object.cpp

108

Nope! I thought it was odd that I needed this-> in other places. I didn't realize what the rule was for when you need this-> and when you don't. Thanks!

[jhenderson]

In D34167#851894, @jakehehrlich wrote:

In D34167#851158, @jhenderson wrote:

To clarify, because I may have missed it, but are we deferring sorting for now, to a later change when it becomes important? I don't see where it's happening currently!

It's not currently happening. I figured once it's clear how symbols are being altered we can add the sorting algorithm. I'll add it now if you'd like, it just seemed like it's unnecessary right now. Your call.

Nope, I'm happy with it being added later. No point in adding unnecessary code at this point for the sake of it.

I realised that there's another case that you need to add support for either now or later, namely symbols with section indexes of SHN_COMMON or SHN_ABS, as these don't refer to actual sections. I'm happy for this to be a later change though. Assuming you do this in a subsequent change, this gets a LGTM from me.

tools/llvm-objcopy/Object.cpp

108

This Stack Overflow post is a good summary of the issue: https://stackoverflow.com/questions/993352/when-should-i-make-explicit-use-of-the-this-pointer

[jakehehrlich]

Added explicit move when returning SymTab for gnu builds

test/tools/llvm-objcopy/basic-copy.test

Sections:
   - Name:            .text
     Type:            SHT_PROGBITS
     Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
     AddressAlign:    0x0000000000000010
     Content:         "00000000"
 
 # CHECK: Type: SHT_NULL
 
-# CHECK:      Name: .shstrtab
-# CHECK-NEXT: Type: SHT_STRTAB
-# CHECK-NEXT: Flags [
-# CHECK-NEXT: ]
-
 # CHECK:      Name: .text
 # CHECK-NEXT: Type: SHT_PROGBITS
 # CHECK-NEXT: Flags [
 # CHECK-NEXT:   SHF_ALLOC
 # CHECK-NEXT:   SHF_EXECINSTR
 # CHECK-NEXT: ]
 # CHECK-NEXT: Address:
 # CHECK-NEXT: Offset:
 # CHECK-NEXT: Size: 4
+
+# CHECK:      Name: .symtab
+# CHECK-NEXT: Type: SHT_SYMTAB
+# CHECK-NEXT: Flags [
+# CHECK-NEXT: ]
+
+# CHECK:      Name: .strtab
+# CHECK-NEXT: Type: SHT_STRTAB
+# CHECK-NEXT: Flags [
+# CHECK-NEXT: ]
+
+# CHECK:      Name: .shstrtab
+# CHECK-NEXT: Type: SHT_STRTAB
+# CHECK-NEXT: Flags [
+# CHECK-NEXT: ]

test/tools/llvm-objcopy/symbol-copy.test

+# RUN: yaml2obj %s > %t
+# RUN: llvm-objcopy %t %t2
+# RUN: llvm-readobj -symbols %t2 | FileCheck %s
+
+!ELF
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_EXEC
+  Machine:         EM_X86_64
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x1000
+    AddressAlign:    0x0000000000000010
+    Content:         "0000000000000000"
+  - Name:            .data
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC ]
+    Address:         0x2000
+    AddressAlign:    0x0000000000000010
+    Content:         "0000000000000000"
+Symbols:
+  Global:
+    - Name:     _start
+      Type:     STT_FUNC
+      Section:  .text
+      Value:    0x1000
+      Size:     4
+    - Name:     foo
+      Type:     STT_FUNC
+      Section:  .text
+      Section:  .text
+      Value:    0x1004
+    - Name:     bar
+      Type:     STT_OBJECT
+      Section:  .data
+      Value:    0x2000
+      Size:     4
+    - Name:     baz
+      Type:     STT_OBJECT
+      Section:  .data
+      Value:    0x2004
+      Size:     4
+
+#CHECK: Symbols [
+#CHECK-NEXT:  Symbol {
+#CHECK-NEXT:    Name:  (0)
+#CHECK-NEXT:    Value: 0x0
+#CHECK-NEXT:    Size: 0
+#CHECK-NEXT:    Binding: Local
+#CHECK-NEXT:    Type: None
+#CHECK-NEXT:    Other: 0
+#CHECK-NEXT:    Section: Undefined
+#CHECK-NEXT:  }
+#CHECK-NEXT:  Symbol {
+#CHECK-NEXT:    Name: _start
+#CHECK-NEXT:    Value: 0x1000
+#CHECK-NEXT:    Size: 4
+#CHECK-NEXT:    Binding: Global
+#CHECK-NEXT:    Type: Function
+#CHECK-NEXT:    Other: 0
+#CHECK-NEXT:    Section: .text
+#CHECK-NEXT:  }
+#CHECK-NEXT:  Symbol {
+#CHECK-NEXT:    Name: foo
+#CHECK-NEXT:    Value: 0x1004
+#CHECK-NEXT:    Size: 0
+#CHECK-NEXT:    Binding: Global
+#CHECK-NEXT:    Type: Function
+#CHECK-NEXT:    Other: 0
+#CHECK-NEXT:    Section: .text
+#CHECK-NEXT:  }
+#CHECK-NEXT:  Symbol {
+#CHECK-NEXT:    Name: bar
+#CHECK-NEXT:    Value: 0x2000
+#CHECK-NEXT:    Size: 4
+#CHECK-NEXT:    Binding: Global
+#CHECK-NEXT:    Type: Object
+#CHECK-NEXT:    Other: 0
+#CHECK-NEXT:    Section: .data
+#CHECK-NEXT:  }
+#CHECK-NEXT:  Symbol {
+#CHECK-NEXT:    Name: baz
+#CHECK-NEXT:    Value: 0x2004
+#CHECK-NEXT:    Size: 4
+#CHECK-NEXT:    Binding: Global
+#CHECK-NEXT:    Type: Object
+#CHECK-NEXT:    Other: 0
+#CHECK-NEXT:    Section: .data

tools/llvm-objcopy/Object.h

public:
   uint32_t findIndex(llvm::StringRef Name) const;
   void finalize() override;
   void writeSection(llvm::FileOutputBuffer &Out) const override;
   static bool classof(const SectionBase *S) {
     return S->Type == llvm::ELF::SHT_STRTAB;
   }
 };
 
+struct Symbol {
+  uint8_t Binding;
+  SectionBase *DefinedIn;
+  uint32_t Index;
+  llvm::StringRef Name;
+  uint32_t NameIndex;
+  uint64_t Size;
+  uint8_t Type;
+  uint64_t Value;
+};
+
+// The symbol data changes from ELFT to ELFT so we need to template it. This
+// lets us implement writeSection
+template <class ELFT> class SymbolTableSection : public SectionBase {
+private:
+  std::vector<Symbol> FinalSymbols;
+  llvm::StringMap<Symbol> Symbols;
+  StringTableSection &SymbolNames;
+
+public:
+  SymbolTableSection(StringTableSection &SymNames) : SymbolNames(SymNames) {
+    Type = llvm::ELF::SHT_SYMTAB;
+    Align = sizeof(typename ELFT::Word);
+    EntrySize = sizeof(typename ELFT::Sym);
+  }
+
+  void addSymbol(llvm::StringRef Name, uint8_t Bind, uint8_t Type,
+                 SectionBase *DefinedIn, uint64_t Value, uint64_t Sz);
+  void removeSymbol(llvm::StringRef);
+  void finalize() override;
+  void writeSection(llvm::FileOutputBuffer &) const override;
+  static bool classof(const SectionBase *S) {
+    return S->Type == llvm::ELF::SHT_SYMTAB;
+  }
+};
+
 template<class ELFT>
 class Object {
 private:
   typedef std::unique_ptr<SectionBase> SecPtr;
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Ehdr Elf_Ehdr;
   typedef typename ELFT::Phdr Elf_Phdr;
 
+  SymbolTableSection<ELFT> *SymbolTable;
   StringTableSection *SectionNames;
   std::vector<SecPtr> Sections;
   std::vector<Segment> Segments;
 
   void sortSections();
   void assignOffsets();
   void readProgramHeaders(const llvm::object::ELFFile<ELFT> &ElfFile);
   void readSectionHeaders(const llvm::object::ELFFile<ELFT> &ElfFile);
+  void readSymbolTable(const llvm::object::ELFFile<ELFT> &ElfFile,
+                       const Elf_Shdr &SymTabShdr);
   void writeHeader(llvm::FileOutputBuffer &Out) const;
   void writeProgramHeaders(llvm::FileOutputBuffer &Out) const;
   void writeSectionData(llvm::FileOutputBuffer &Out) const;
   void writeSectionHeaders(llvm::FileOutputBuffer &Out) const;
 
 public:
   uint8_t Ident[16];
   uint64_t Entry;

tools/llvm-objcopy/Object.cpp

for (const auto &Name : Strings) {
     Buf = std::copy(std::begin(Name.getKey()), std::end(Name.getKey()), Buf);
     // We need to set the null character and then increment the buffer past it
     *Buf = 0;
     Buf++;
   }
 }
 
 template <class ELFT>
+void SymbolTableSection<ELFT>::addSymbol(StringRef Name, uint8_t Bind,
+                                         uint8_t Type, SectionBase *DefinedIn,
+                                         uint64_t Value, uint64_t Sz) {
+  Symbol Sym;
+  Sym.Name = Name;
+  Sym.Binding = Bind;
+  Sym.Type = Type;
+  Sym.DefinedIn = DefinedIn;
+  Sym.Value = Value;
+  Sym.Size = Sz;
+  Sym.Index = Symbols.size();
+  auto Res = Symbols.insert(std::make_pair(Name, Sym));
+  if (Res.second)
+    Size += sizeof(typename ELFT::Sym);
+  SymbolNames.addString(Name);
+}
+
+template <class ELFT>
+void SymbolTableSection<ELFT>::removeSymbol(StringRef Name) {
+  auto Iter = Symbols.find(Name);
+  if (Iter != std::end(Symbols)) {
+    Symbols.erase(Iter);
+    Size += sizeof(ELFT::Sym);
+  }
+  SymbolNames.removeString(Name);
+}
+
+template <class ELFT> void SymbolTableSection<ELFT>::finalize() {
+  auto CompareBinding = [](const Symbol &a, const Symbol &b) {
+    return a.Binding < b.Binding;
+  };
+  auto CompareIndex = [](const Symbol &a, const Symbol &b) {
+    return a.Index < b.Index;
+  };
+  // Make sure that SymbolNames is finalized first
+  SymbolNames.finalize();
+  for (auto &Entry : Symbols) {
+    Entry.second.NameIndex = SymbolNames.findIndex(Entry.second.Name);
+    FinalSymbols.push_back(Entry.second);
+  }
+  Symbol DummyLocal;
+  DummyLocal.Binding = STB_LOCAL;
+  std::sort(std::begin(FinalSymbols), std::end(FinalSymbols), CompareIndex);
+  std::stable_sort(std::begin(FinalSymbols), std::end(FinalSymbols),
+                   CompareBinding);
+  auto Iter = std::upper_bound(std::begin(FinalSymbols), std::end(FinalSymbols),
+                               DummyLocal, CompareBinding);
+  Info = std::end(FinalSymbols) - Iter;
+  Link = SymbolNames.Index;
+}
+
+template <class ELFT>
+void SymbolTableSection<ELFT>::writeSection(llvm::FileOutputBuffer &Out) const {
+  uint8_t *Buf = Out.getBufferStart();
+  Buf += Offset;
+  typename ELFT::Sym *Sym = reinterpret_cast<typename ELFT::Sym *>(Buf);
+
+  for(auto &Symbol : FinalSymbols) {
+    Sym->st_name = Symbol.NameIndex;
+    Sym->st_value = Symbol.Value;
+    Sym->st_size = Symbol.Size;
+    Sym->setBinding(Symbol.Binding);
+    Sym->setType(Symbol.Type);
+    if(Symbol.DefinedIn)
+      Sym->st_shndx = Symbol.DefinedIn->Index;
+    else
+      Sym->st_shndx = SHN_UNDEF;
+    ++Sym;
+  }
+}
+
+template <class ELFT>
 void Object<ELFT>::readProgramHeaders(const ELFFile<ELFT> &ElfFile) {
   uint32_t Index = 0;
   for (const auto &Phdr : unwrapOrError(ElfFile.program_headers())) {
     Segments.emplace_back();
     Segment &Seg = Segments.back();
     Seg.Type = Phdr.p_type;
     Seg.Flags = Phdr.p_flags;
     Seg.Offset = Phdr.p_offset;
     Seg.VAddr = Phdr.p_vaddr;
     Seg.FileSize = Phdr.p_filesz;
     Seg.MemSize = Phdr.p_memsz;
     Seg.Align = Phdr.p_align;
     Seg.Index = Index++;
     for (auto &Section : Sections) {
       if (Seg.Offset <= Section->Offset &&
           Seg.Offset + Seg.FileSize >= Section->Offset + Section->Size) {
         Seg.addSection(&*Section);
         Section->ParrentSegment = &Seg;
       }
     }
   }
 }
 
 template <class ELFT>
+void Object<ELFT>::readSymbolTable(const ELFFile<ELFT> &ElfFile,
+                                   const Elf_Shdr &SymTabShdr) {
+
+  StringTableSection *StrTab =
+      dyn_cast<StringTableSection>(Sections[SymTabShdr.sh_link].get());
+
+  uint32_t SymTabIndex =
+      &SymTabShdr - unwrapOrError(ElfFile.sections()).begin();
+
+  SymbolTable = new SymbolTableSection<ELFT>(*StrTab);
+  SymbolTable->Name = unwrapOrError(ElfFile.getSectionName(&SymTabShdr));
+  SymbolTable->Index = SymTabIndex;
+  SectionNames->addString(SymbolTable->Name);
+
+  StringRef StrTabData =
+      unwrapOrError(ElfFile.getStringTableForSymtab(SymTabShdr));
+
+  for (const auto &Sym : unwrapOrError(ElfFile.symbols(&SymTabShdr))) {
+    SectionBase *DefSection = nullptr;
+    if (Sym.st_shndx != SHN_UNDEF)
+      DefSection = Sections[Sym.st_shndx].get();
+    StringRef Name = unwrapOrError(Sym.getName(StrTabData));
+    SymbolTable->addSymbol(Name, Sym.getBinding(), Sym.getType(), DefSection,
+                           Sym.getValue(), Sym.st_size);
+  }
+  // Calculate where the SymbolTable belongs
+  Sections[SymTabIndex].reset(SymbolTable);
+}
+
+template <class ELFT>
+static std::unique_ptr<SectionBase> makeSection(ArrayRef<uint8_t> Data,
+                                                uint64_t Type) {
+  if (Type == SHT_STRTAB)
+    return make_unique<StringTableSection>();
+  return make_unique<Section>(Data);
+}
+
+template <class ELFT>
 void Object<ELFT>::readSectionHeaders(const ELFFile<ELFT> &ElfFile) {
   uint32_t Index = 0;
+  const Elf_Shdr *SymTabShdr = nullptr;
   for (const auto &Shdr : unwrapOrError(ElfFile.sections())) {
-    if (Shdr.sh_type == SHT_STRTAB)
+    if (Index == SectionNames->Index) {
+      Sections.emplace_back(SectionNames);
+      Index++;
       continue;
+    }
+    if (Shdr.sh_type == SHT_SYMTAB) {
+      // Put a placeholder in Sections so that Index corrasponds to the
+      // location in the array the symbol table should go
+      Sections.emplace_back(nullptr);
+      SymTabShdr = &Shdr;
+      Index++;
+      continue;
+    }
     ArrayRef<uint8_t> Data = unwrapOrError(ElfFile.getSectionContents(&Shdr));
-    SecPtr Sec = make_unique<Section>(Data);
+    SecPtr Sec = makeSection<ELFT>(Data, Shdr.sh_type);
     Sec->Name = unwrapOrError(ElfFile.getSectionName(&Shdr));
     Sec->Type = Shdr.sh_type;
     Sec->Flags = Shdr.sh_flags;
     Sec->Addr = Shdr.sh_addr;
     Sec->Offset = Shdr.sh_offset;
     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;
-    Index++;
+    Sec->Index = Index++;
     SectionNames->addString(Sec->Name);
     Sections.push_back(std::move(Sec));
   }
+  // If we encountered a symbol table construct it now that we should have
+  // every section
+  if (SymTabShdr)
+    readSymbolTable(ElfFile, *SymTabShdr);
 }
 
 template <class ELFT> size_t Object<ELFT>::totalSize() const {
   // We already have the section header offset so we can calculate the total
   // size by just adding up the size of each section header;
   return SHOffset + Sections.size() * sizeof(Elf_Shdr);
 }
 
 template <class ELFT> Object<ELFT>::Object(const ELFObjectFile<ELFT> &Obj) {
   const auto &ElfFile = *Obj.getELFFile();
   const auto &Ehdr = *ElfFile.getHeader();
 
   std::copy(Ehdr.e_ident, Ehdr.e_ident + 16, Ident);
   Type = Ehdr.e_type;
   Machine = Ehdr.e_machine;
   Version = Ehdr.e_version;
   Entry = Ehdr.e_entry;
   Flags = Ehdr.e_flags;
+
   SectionNames = new StringTableSection();
-  SectionNames->Name = ".shstrtab";
+  auto Shdr = unwrapOrError(ElfFile.getSection(Ehdr.e_shstrndx));
+  SectionNames->Name = unwrapOrError(ElfFile.getSectionName(Shdr));
+  SectionNames->Index = Ehdr.e_shstrndx;
   SectionNames->addString(SectionNames->Name);
-  Sections.emplace_back(SectionNames);
 
   readSectionHeaders(ElfFile);
   readProgramHeaders(ElfFile);
 }
 
 template <class ELFT> void Object<ELFT>::sortSections() {
-  // Put allocated sections in address order. Maintain ordering as closely as
-  // possible while meeting that demand however.
-  auto CompareSections = [](const SecPtr &A, const SecPtr &B) {
-    if (A->Type == SHT_NULL)
-      return true;
-    if (A->Flags & SHF_ALLOC && B->Flags & SHF_ALLOC)
-      return A->Addr < B->Addr;
-    return A->Index < B->Index;
-  };
-  std::sort(std::begin(Sections), std::end(Sections), CompareSections);
+  std::sort(
+      std::begin(Sections), std::end(Sections),
+      [](const SecPtr &A, const SecPtr &B) { return A->Index < B->Index; });
 }
 
 uint64_t align(uint64_t Value, uint64_t Multiple) {
   if (!Multiple || Value % Multiple == 0)
     return Value;
   return Value + Multiple - Value % Multiple;
 }
 
for (auto &Section : Sections) {
     if (Section->Type != SHT_NOBITS)
       Offset += Section->Size;
     Index++;
   }
   // 'offset' should now be just after all the section data so we should set the
   // section header table offset to be exactly here. This spot might not be
   // aligned properlly however so we should align it as needed. This only takes
   // a little bit of tweaking to ensure that the sh_name is 4 byte aligned
-  Offset += 4 - Offset % 4;
+  Offset = align(Offset, 4);
   SHOffset = Offset;
 }
 
 template <class ELFT> void Object<ELFT>::finalize() {
   sortSections();
   assignOffsets();
 
   // finalize SectionNames first so that we can assign name indexes.
   SectionNames->finalize();
+
   // Finally now that all offsets and indexes have been set we can finalize any
   // reamining issues.
   uint64_t Offset = SHOffset;
   for (auto &Section : Sections) {
     Section->HeaderOffset = Offset;
     Offset += sizeof(Elf_Shdr);
     Section->NameIndex = SectionNames->findIndex(Section->Name);
     Section->finalize();
for (auto &Section : Sections)
     Section->template writeHeader<ELFT>(Out);
 }
 
 template <class ELFT>
 void Object<ELFT>::writeSectionData(FileOutputBuffer &Out) const {
   for (auto &Section : Sections)
     Section->writeSection(Out);
 }
 
 template <class ELFT> void Object<ELFT>::write(FileOutputBuffer &Out) {
   writeHeader(Out);
   writeProgramHeaders(Out);
   writeSectionData(Out);
   writeSectionHeaders(Out);
 }
 
 template class Object<ELF64LE>;
 template class Object<ELF64BE>;
 template class Object<ELF32LE>;
 template class Object<ELF32BE>;