[llvm-objcopy] New layout algorithm that lays out segments first

[jakehehrlich]

Summary

The current file layout algorithm in llvm-objcopy is simple but difficult to reason about. It also makes it very complicated to support nested segments and to support segments that have offsets that come before a point after the program headers. To support these cases and simplify one of the most critical parts llvm-objcopy I rewrote the layout algorithm. Laying out segments first solves most of the issues encountered by the previous algorithm.

[phosek]

Just a few small nits but otherwise looks good to me.

tools/llvm-objcopy/Object.cpp

263

nit: Space between if and paren.

278

nit: s/segmnet/segment

[jhenderson]

I like this approach. Just a slight comment rephrasing needed from my point of view, apart from the nits.

tools/llvm-objcopy/Object.cpp

258–284

Nit: capital letter

279–281

Nit: full stop at end.

It's not clear to me whose original offset is being talked about in each of the two mentions here, please could you rephrase somehow.

[jakehehrlich]

Fixed comments by Petr and James

[jhenderson]

LGTM.

tools/llvm-objcopy/Object.h

public:
   uint32_t Flags;
   uint32_t Index;
   uint64_t MemSize;
   uint64_t Offset;
   uint64_t PAddr;
   uint64_t Type;
   uint64_t VAddr;
 
+  uint64_t OriginalOffset;
+
   Segment(llvm::ArrayRef<uint8_t> Data) : Contents(Data) {}
   void finalize();
   const SectionBase *firstSection() const {
     if (!Sections.empty())
       return *Sections.begin();
     return nullptr;
   }
   void addSection(const SectionBase *sec) { Sections.insert(sec); }

tools/llvm-objcopy/Object.cpp

void Object<ELFT>::readProgramHeaders(const ELFFile<ELFT> &ElfFile) {
   uint32_t Index = 0;
   for (const auto &Phdr : unwrapOrError(ElfFile.program_headers())) {
     ArrayRef<uint8_t> Data{ElfFile.base() + Phdr.p_offset,
                            (size_t)Phdr.p_filesz};
     Segments.emplace_back(llvm::make_unique<Segment>(Data));
     Segment &Seg = *Segments.back();
     Seg.Type = Phdr.p_type;
     Seg.Flags = Phdr.p_flags;
+    Seg.OriginalOffset = Phdr.p_offset;
     Seg.Offset = Phdr.p_offset;
     Seg.VAddr = Phdr.p_vaddr;
     Seg.PAddr = Phdr.p_paddr;
     Seg.FileSize = Phdr.p_filesz;
     Seg.MemSize = Phdr.p_memsz;
     Seg.Align = Phdr.p_align;
     Seg.Index = Index++;
     for (auto &Section : Sections) {
template <class ELFT> void ELFObject<ELFT>::sortSections() {
   auto CompareSections = [](const SecPtr &A, const SecPtr &B) {
     return A->OriginalOffset < B->OriginalOffset;
   };
   std::stable_sort(std::begin(this->Sections), std::end(this->Sections),
                    CompareSections);
 }
 
 template <class ELFT> void ELFObject<ELFT>::assignOffsets() {
-  // Decide file offsets and indexes.
-  size_t PhdrSize = this->Segments.size() * sizeof(Elf_Phdr);
-  // We can put section data after the ELF header and the program headers.
-  uint64_t Offset = sizeof(Elf_Ehdr) + PhdrSize;
-  uint64_t Index = 1;
+  // The size of ELF + program headers will not change so it is ok to assume
+  // that the first offset of the first segment is a good place to start
+  // outputting sections. This covers both the standard case and the PT_PHDR
+  // case.
+  uint64_t Offset;
+  if (!this->Segments.empty()) {
+    Offset = this->Segments[0]->Offset;
+  } else {
+    Offset = sizeof(Elf_Ehdr);
+  }
+  // The only way a segment should move is if a section was between two
+  // segments and that section was removed. If that section isn't in a segment
+  // then it's acceptable, but not ideal, to simply move it to after the
+  // segments. So we can simply layout segments one after the other accounting
+  // for alignment.
+  for (auto &Segment : this->Segments) {
+    Offset = alignTo(Offset, Segment->Align);
+    Segment->Offset = Offset;
+    Offset += Segment->FileSize;
+  }
+  // Now the offset of every segment has been set we can assign the offsets
+  // of each section. For sections that are covered by a segment we should use
+  // the segment's original offset and the section's original offset to compute
+  // the offset from the start of the segment. Using the offset from the start
+  // of the segment we can assign a new offset to the section. For sections not
+  // covered by segments we can just bump Offset to the next valid location.
+  uint32_t Index = 1;
   for (auto &Section : this->Sections) {
-    // The segment can have a different alignment than the section. In the case
-    // that there is a parent segment then as long as we satisfy the alignment
-    // of the segment it should follow that that the section is aligned.
-    if (Section->ParentSegment) {
-      auto FirstInSeg = Section->ParentSegment->firstSection();
-      if (FirstInSeg == Section.get()) {
-        Offset = alignTo(Offset, Section->ParentSegment->Align);
-        // There can be gaps at the start of a segment before the first section.
-        // So first we assign the alignment of the segment and then assign the
-        // location of the section from there
-        Section->Offset =
-            Offset + Section->OriginalOffset - Section->ParentSegment->Offset;
-      }
-      // We should respect interstitial gaps of allocated sections. We *must*
-      // maintain the memory image so that addresses are preserved. As, with the
-      // exception of SHT_NOBITS sections at the end of segments, the memory
-      // image is a copy of the file image, we preserve the file image as well.
-      // There's a strange case where a thread local SHT_NOBITS can cause the
-      // memory image and file image to not be the same. This occurs, on some
-      // systems, when a thread local SHT_NOBITS is between two SHT_PROGBITS
-      // and the thread local SHT_NOBITS section is at the end of a TLS segment.
-      // In this case to faithfully copy the segment file image we must use
-      // relative offsets. In any other case this would be the same as using the
-      // relative addresses so this should maintian the memory image as desired.
-      Offset = FirstInSeg->Offset + Section->OriginalOffset -
-               FirstInSeg->OriginalOffset;
-    }
-    // Alignment should have already been handled by the above if statement if
-    // this if this section is in a segment. Technically this shouldn't do
-    // anything bad if the alignments of the sections are all correct and the
-    // file image isn't corrupted. Still in sticking with the motto "maintain
-    // the file image" we should avoid messing up the file image if the
-    // alignment disagrees with the file image.
-    if (!Section->ParentSegment && Section->Align)
-      Offset = alignTo(Offset, Section->Align);
+    Section->Index = Index++;
+    if (Section->ParentSegment != nullptr) {
+      auto Segment = Section->ParentSegment;
+          Segment->Offset + (Section->OriginalOffset - Segment->OriginalOffset);
+    } else {
+      Offset = alignTo(Offset, Section->Offset);
       Section->Offset = Offset;
-    Section->Index = Index++;
       if (Section->Type != SHT_NOBITS)
         Offset += Section->Size;
     }
-  // '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 properly however so we should align it as needed. For 32-bit ELF
-  // this needs to be 4-byte aligned and on 64-bit it needs to be 8-byte aligned
-  // so the size of ELFT::Addr is used to ensure this.
+  }
+
   Offset = alignTo(Offset, sizeof(typename ELFT::Addr));
   this->SHOffset = Offset;
 }
 
 template <class ELFT> size_t ELFObject<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 this->SHOffset + this->Sections.size() * sizeof(Elf_Shdr) +