[llvm-objcopy] Improve section removal

[evgeny777]

Summary

This patch changes segment size, when last section in the segment is removed. Segment also can be removed completely when it doesn't contain section (such behavior differs from GNU objcopy which leaves empty segment with warning).

This patch changes way section and segment layout is calculated and is a base for --update-section, --pad-to and few other options.

[jakehehrlich]

Can we get an explicit real use case for this or a case where not removing these sections is detrimental? I believe this to be fundamentally wrong otherwise. Imagine what would happen if you first ran --strip-sections and then ran literally anything again. It's also a primary tenant so far that we not modify program headers. That's how we maintain that stripping not affect run time behavior so trivially. This diff changes that.

The one use case I'm aware of that would modify program headers is to add a program header so that a special chunk of data can be used at runtime that isn't available until after the binary is linked (because it is in part a way to verify that the correct binary is loaded or something like that; I'm not sure about the details)

[jakehehrlich]

cc @mcgrathr who can comment more in depth on how this works in GNU objcopy and how useful it is. He already noted that anything relaying on segment resizing behavior from GNU objcopy is already fragile.

[evgeny777]

Can we get an explicit real use case

Well, my understanding is that when someone removes section from final image he knows what he's doing. The patch allows reducing executable size when it is possible.
Also it now calculates segment file and memory sizes based on section offsets and sizes.

FYI GNU objcopy can not only shrink, but also expand segments, recalculating section and segment addresses. See --update-section.
My plans were implementing GNU objcopy options and (possibly) some that I personally find useful, i.e:

• Adding/modifying symbol in dynamic symbol table (.dynsym)
• Adding/modifying dynamic table entries

This requires segment modification as well. Is there any reasons why segments shouldn't be modified by llvm-objcopy, except that it might break something?

[jhenderson]

Some things that can go wrong if we allow segments to be modified such that their size or addresses change:

1. Dynamic relocations no longer patch the right area (potentially even patching memory outside the program's address space).
2. Dynamic tags could end up referencing incorrect addresses.
3. Code could end up referencing incorrect addresses.
4. The entry symbol may no longer point at a valid address.
5. Unlabelled space that has meaning (e.g. following section header stripping) may be discarded.

None of these are absolute reasons why we can't modify program headers, but I agree that we must have a concrete use case before we go ahead and implement manipulating phdrs in this way. I will say that it is probably safe to increase the size of a segment (both file and memory size), as long as the addresses of other segments are unaffected. This includes adding new segments entirely.

Using llvm-objcopy to reduce memory usage post-link seems like the wrong thing to do, because it can only safely remove sections that are known to be unused, and it's a bit of a sledge-hammer, because section concatenation has already been performed by the linker. A safer and much more appropriate place for this would be at link time, using switches such as --gc-sections. Using llvm-objcopy on the objects pre-link would also be possible here.

Removing empty segments is also sometimes not a no-op in terms of semantic behaviour (see e.g. the PT_GNU_STACK segment type). Even removing PT_LOAD segments may not be wise, since some loaders may explicitly expect a certain number of segments, although I agree that it is probably a feature that could be implemented, e.g. in via a switch.

test/tools/llvm-objcopy/ELF/fixup-segment.test

+# RUN: yaml2obj %s -o %t
+# Remove section from the middle of the segment. Segment table should not change
+# RUN: llvm-objcopy --remove-section=.data.2 %t %t2
+# RUN: llvm-readobj --sections --program-headers %t2 | FileCheck %s --check-prefix=REM-DATA2
+
+# Remove NOBITS section which is last in the segment. Second segment's file and memory size
+# should change after that.
+# RUN: llvm-objcopy --remove-section=.bss %t2 %t3
+# RUN: llvm-readobj --sections --program-headers %t3 | FileCheck %s --check-prefix=REM-BSS
+
+# Remove the last section from segment. Segment will be deleted after that.
+# RUN: llvm-objcopy --remove-section=.data.1 %t3 %t4
+# RUN: llvm-readobj --sections --program-headers %t4 | FileCheck %s --check-prefix=REM-DATA1
+
+!ELF
+FileHeader:
+  Class:           ELFCLASS32
+  Data:            ELFDATA2LSB
+  Type:            ET_EXEC
+  Machine:         EM_ARM
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x1000
+    AddressAlign:    0x8
+    Size:            64
+  - Name:            .data.1
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC ]
+    Address:         0x10000
+    AddressAlign:    0x8
+    Size:            0x1000
+  - Name:            .data.2
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC ]
+    Address:         0x11000
+    AddressAlign:    0x8
+    Size:            0x1000
+  - Name:            .bss
+    Type:            SHT_NOBITS
+    Flags:           [ SHF_ALLOC ]
+    Address:         0x12000
+    AddressAlign:    0x8
+    Size:            0x1000
+ProgramHeaders:
+  - Type: PT_LOAD
+    Flags: [ PF_X, PF_R ]
+    VAddr: 0x1000
+    PAddr: 0x1000
+    Align: 0x1000
+    Sections:
+      - Section: .text
+  - Type: PT_LOAD
+    Flags: [ PF_R, PF_W ]
+    VAddr: 0x10000
+    PAddr: 0x10000
+    Align: 0x1000
+    Sections:
+      - Section: .data.1
+      - Section: .data.2
+      - Section: .bss
+
+#REM-DATA2-NOT: .data.2
+#REM-DATA2:      ProgramHeaders [
+#REM-DATA2-NEXT:  ProgramHeader {
+#REM-DATA2-NEXT:    Type: PT_LOAD (0x1)
+#REM-DATA2-NEXT:    Offset: 0x1000
+#REM-DATA2-NEXT:    VirtualAddress: 0x1000
+#REM-DATA2-NEXT:    PhysicalAddress: 0x1000
+#REM-DATA2-NEXT:    FileSize: 64
+#REM-DATA2-NEXT:    MemSize: 64
+#REM-DATA2-NEXT:    Flags [ (0x5)
+#REM-DATA2-NEXT:      PF_R (0x4)
+#REM-DATA2-NEXT:      PF_X (0x1)
+#REM-DATA2-NEXT:    ]
+#REM-DATA2-NEXT:    Alignment: 4096
+#REM-DATA2-NEXT:  }
+#REM-DATA2-NEXT:  ProgramHeader {
+#REM-DATA2-NEXT:    Type: PT_LOAD (0x1)
+#REM-DATA2-NEXT:    Offset: 0x2000
+#REM-DATA2-NEXT:    VirtualAddress: 0x10000
+#REM-DATA2-NEXT:    PhysicalAddress: 0x10000
+#REM-DATA2-NEXT:    FileSize: 8192
+#REM-DATA2-NEXT:    MemSize: 12288
+#REM-DATA2-NEXT:    Flags [ (0x6)
+#REM-DATA2-NEXT:      PF_R (0x4)
+#REM-DATA2-NEXT:      PF_W (0x2)
+#REM-DATA2-NEXT:    ]
+#REM-DATA2-NEXT:    Alignment: 4096
+#REM-DATA2-NEXT:  }
+#REM-DATA2-NEXT: ]
+
+#REM-BSS-NOT: .bss
+#REM-BSS:     ProgramHeaders [
+#REM-BSS-NEXT:  ProgramHeader {
+#REM-BSS-NEXT:     Type: PT_LOAD (0x1)
+#REM-BSS-NEXT:     Offset: 0x1000
+#REM-BSS-NEXT:     VirtualAddress: 0x1000
+#REM-BSS-NEXT:     PhysicalAddress: 0x1000
+#REM-BSS-NEXT:     FileSize: 64
+#REM-BSS-NEXT:     MemSize: 64
+#REM-BSS-NEXT:     Flags [ (0x5)
+#REM-BSS-NEXT:       PF_R (0x4)
+#REM-BSS-NEXT:       PF_X (0x1)
+#REM-BSS-NEXT:     ]
+#REM-BSS-NEXT:     Alignment: 4096
+#REM-BSS-NEXT:   }
+#REM-BSS-NEXT:   ProgramHeader {
+#REM-BSS-NEXT:     Type: PT_LOAD (0x1)
+#REM-BSS-NEXT:     Offset: 0x2000
+#REM-BSS-NEXT:     VirtualAddress: 0x10000
+#REM-BSS-NEXT:     PhysicalAddress: 0x10000
+#REM-BSS-NEXT:     FileSize: 4096
+#REM-BSS-NEXT:     MemSize: 4096
+#REM-BSS-NEXT:     Flags [ (0x6)
+#REM-BSS-NEXT:       PF_R (0x4)
+#REM-BSS-NEXT:       PF_W (0x2)
+#REM-BSS-NEXT:     ]
+#REM-BSS-NEXT:     Alignment: 4096
+#REM-BSS-NEXT:   }
+#REM-BSS-NEXT: ]
+
+#REM-DATA1-NOT: .data
+#REM-DATA1:       ProgramHeaders [
+#REM-DATA1-NEXT:   ProgramHeader {
+#REM-DATA1-NEXT:     Type: PT_LOAD (0x1)
+#REM-DATA1-NEXT:     Offset: 0x1000
+#REM-DATA1-NEXT:     VirtualAddress: 0x1000
+#REM-DATA1-NEXT:     PhysicalAddress: 0x1000
+#REM-DATA1-NEXT:     FileSize: 64
+#REM-DATA1-NEXT:     MemSize: 64
+#REM-DATA1-NEXT:     Flags [ (0x5)
+#REM-DATA1-NEXT:       PF_R (0x4)
+#REM-DATA1-NEXT:       PF_X (0x1)
+#REM-DATA1-NEXT:     ]
+#REM-DATA1-NEXT:     Alignment: 4096
+#REM-DATA1-NEXT:   }
+#REM-DATA1-NEXT: ]
+

tools/llvm-objcopy/ELF/Object.h

private:
   void writeEhdr();
   void writePhdr(const Segment &Seg);
   void writeShdr(const SectionBase &Sec);
 
   void writePhdrs();
   void writeShdrs();
   void writeSectionData();
 
+  void setParentSegment(Segment &Child);
   void assignOffsets();
 
   std::unique_ptr<ELFSectionWriter<ELFT>> SecWriter;
 
   size_t totalSize() const;
 
 public:
   virtual ~ELFWriter() {}
public:
   uint64_t OriginalOffset;
   Segment *ParentSegment = nullptr;
   ArrayRef<uint8_t> Contents;
 
   explicit Segment(ArrayRef<uint8_t> Data) : Contents(Data) {}
   Segment() {}
 
   const SectionBase *firstSection() const {
-    if (!Sections.empty())
-      return *Sections.begin();
-    return nullptr;
+    return !Sections.empty() ? *Sections.begin() : nullptr;
+  }
+  const SectionBase *lastSection() const {
+    return !Sections.empty() ? *--Sections.end() : nullptr;
   }
 
   void removeSection(const SectionBase *Sec) { Sections.erase(Sec); }
   void addSection(const SectionBase *Sec) { Sections.insert(Sec); }
 };
 
 class Section : public SectionBase {
   MAKE_SEC_WRITER_FRIEND

 private:
   using Elf_Addr = typename ELFT::Addr;
   using Elf_Shdr = typename ELFT::Shdr;
   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);
   void readSectionHeaders();
   SectionBase &makeSection(const Elf_Shdr &Shdr);
 
 public:
   ELFBuilder(const ELFObjectFile<ELFT> &ElfObj, Object &Obj)
template <class T, class... Ts> T &addSection(Ts &&... Args) {
     Sections.emplace_back(std::move(Sec));
     Ptr->Index = Sections.size();
     return *Ptr;
   }
   Segment &addSegment(ArrayRef<uint8_t> Data) {
     Segments.emplace_back(llvm::make_unique<Segment>(Data));
     return *Segments.back();
   }
+  bool isParentForPhdrs(const Segment *Seg);
+  void fixupSegments();
 };
 
 } // end namespace elf
 } // end namespace objcopy
 } // end namespace llvm
 
 #endif // LLVM_TOOLS_OBJCOPY_OBJECT_H

tools/llvm-objcopy/ELF/Object.cpp

 // Returns true IFF a section is wholly inside the range of a segment
 static bool sectionWithinSegment(const SectionBase &Section,
                                  const Segment &Segment) {
   // If a section is empty it should be treated like it has a size of 1. This is
   // to clarify the case when an empty section lies on a boundary between two
   // segments and ensures that the section "belongs" to the second segment and
   // not the first.
   uint64_t SecSize = Section.Size ? Section.Size : 1;
-  return Segment.Offset <= Section.OriginalOffset &&
-         Segment.Offset + Segment.FileSize >= Section.OriginalOffset + SecSize;
+  return (Section.Flags & ELF::SHF_ALLOC) &&
+         Segment.Offset <= Section.OriginalOffset &&
+         Segment.Offset + Segment.MemSize >= Section.OriginalOffset + SecSize;
 }
 
 // Returns true IFF a segment's original offset is inside of another segment's
 // range.
 static bool segmentOverlapsSegment(const Segment &Child,
                                    const Segment &Parent) {
 
   return Parent.OriginalOffset <= Child.OriginalOffset &&
std::unique_ptr<Object> BinaryELFBuilder::build() {
   StringTableSection *StrTab = addStrTab();
   SymbolTableSection *SymTab = addSymTab(StrTab);
   initSections();
   addData(SymTab);
 
   return std::move(Obj);
 }
 
-template <class ELFT> void ELFBuilder<ELFT>::setParentSegment(Segment &Child) {
-  for (auto &Parent : Obj.segments()) {
-    // Every segment will overlap with itself but we don't want a segment to
-    // be it's own parent so we avoid that situation.
-    if (&Child != &Parent && segmentOverlapsSegment(Child, Parent)) {
-      // We want a canonical "most parental" segment but this requires
-      // inspecting the ParentSegment.
-      if (compareSegmentsByOffset(&Parent, &Child))
-        if (Child.ParentSegment == nullptr ||
-            compareSegmentsByOffset(&Parent, Child.ParentSegment)) {
-          Child.ParentSegment = &Parent;
-        }
-    }
-  }
-}
-
 template <class ELFT> void ELFBuilder<ELFT>::readProgramHeaders() {
   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};
     Segment &Seg = Obj.addSegment(Data);
     Seg.Type = Phdr.p_type;
     Seg.Flags = Phdr.p_flags;
template <class ELFT> void ELFBuilder<ELFT>::readProgramHeaders() {
   // always non-zero and to ensure the equation we assign the same value to
   // VAddr as well.
   PrHdr.OriginalOffset = PrHdr.Offset = PrHdr.VAddr = Ehdr.e_phoff;
   PrHdr.PAddr = 0;
   PrHdr.FileSize = PrHdr.MemSize = Ehdr.e_phentsize * Ehdr.e_phnum;
   // The spec requires us to naturally align all the fields.
   PrHdr.Align = sizeof(Elf_Addr);
   PrHdr.Index = Index++;
-
-  // Now we do an O(n^2) loop through the segments in order to match up
-  // segments.
-  for (auto &Child : Obj.segments())
-    setParentSegment(Child);
-  setParentSegment(ElfHdr);
-  setParentSegment(PrHdr);
 }
 
 template <class ELFT>
 void ELFBuilder<ELFT>::initGroupSection(GroupSection *GroupSec) {
   auto SecTable = Obj.sections();
   auto SymTab = SecTable.template getSectionOfType<SymbolTableSection>(
       GroupSec->Link,
       "Link field value " + Twine(GroupSec->Link) + " in section " +
void Object::sortSections() {
   // possible while meeting that demand however.
   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);
 }
 
+bool Object::isParentForPhdrs(const Segment *Seg) {
+  return ElfHdrSegment.ParentSegment == Seg ||
+         ProgramHdrSegment.ParentSegment == Seg;
+}
+
+void Object::fixupSegments() {
+  for (auto &Seg : Segments)
+    if (const SectionBase *LastSec = Seg->lastSection()) {
+      // We should be called before layouting.
+      assert(LastSec->Offset == LastSec->OriginalOffset);
+      Seg->MemSize = LastSec->Offset + LastSec->Size - Seg->Offset;
+      Seg->FileSize = LastSec->Type == SHT_NOBITS ? Seg->MemSize - LastSec->Size
+                                                  : Seg->MemSize;
+    }
+
+  // Remove every PT_LOAD segment which doesn't contain sections if
+  // it doesn't overlap with PT_PHDRS.
+  Segments.erase(std::remove_if(Segments.begin(), Segments.end(),
+                                [this](const SegPtr &Seg) {
+                                  return Seg->Type == PT_LOAD &&
+                                         Seg->firstSection() == nullptr &&
+                                         !isParentForPhdrs(Seg.get());
+                                }),
+                 Segments.end());
+}
+
 static uint64_t alignToAddr(uint64_t Offset, uint64_t Addr, uint64_t Align) {
   // Calculate Diff such that (Offset + Diff) & -Align == Addr & -Align.
   if (Align == 0)
     Align = 1;
   auto Diff =
       static_cast<int64_t>(Addr % Align) - static_cast<int64_t>(Offset % Align);
   // We only want to add to Offset, however, so if Diff < 0 we can add Align and
   // (Offset + Diff) & -Align == Addr & -Align will still hold.
template <class ELFT> void ELFWriter<ELFT>::initEhdrSegment() {
   ElfHdr.Flags = 0;
   ElfHdr.OriginalOffset = ElfHdr.Offset = 0;
   ElfHdr.VAddr = 0;
   ElfHdr.PAddr = 0;
   ElfHdr.FileSize = ElfHdr.MemSize = sizeof(Elf_Ehdr);
   ElfHdr.Align = 0;
 }
 
+template <class ELFT> void ELFWriter<ELFT>::setParentSegment(Segment &Child) {
+  for (auto &Parent : Obj.segments()) {
+    // Every segment will overlap with itself but we don't want a segment to
+    // be it's own parent so we avoid that situation.
+    if (&Child != &Parent && segmentOverlapsSegment(Child, Parent)) {
+      // We want a canonical "most parental" segment but this requires
+      // inspecting the ParentSegment.
+      if (compareSegmentsByOffset(&Parent, &Child))
+        if (Child.ParentSegment == nullptr ||
+            compareSegmentsByOffset(&Parent, Child.ParentSegment)) {
+          Child.ParentSegment = &Parent;
+        }
+    }
+  }
+}
+
 template <class ELFT> void ELFWriter<ELFT>::assignOffsets() {
+  // Set parent segment for ELF and program headers, so we don't
+  // occasionally remove load segment containing them in fixupSegments.
+  setParentSegment(Obj.ElfHdrSegment);
+  setParentSegment(Obj.ProgramHdrSegment);
+  // Fixup segments: set correct file and memory sizes and remove
+  // empty segments if any
+  Obj.fixupSegments();
+  // Now we do an O(n^2) loop through the segments in order to match up
+  // segments.
+  for (auto &Child : Obj.segments())
+    setParentSegment(Child);
   // We need a temporary list of segments that has a special order to it
   // so that we know that anytime ->ParentSegment is set that segment has
   // already had its offset properly set.
   std::vector<Segment *> OrderedSegments;
   for (auto &Segment : Obj.segments())
     OrderedSegments.push_back(&Segment);
   OrderedSegments.push_back(&Obj.ElfHdrSegment);
   OrderedSegments.push_back(&Obj.ProgramHdrSegment);