[llvm-objcopy][MachO] Make --remove-section clean up dead symbols

[alexander-shaposhnikov]

Summary

Make --remove-section clean up dead symbols, return an Error if it can't be safely done.

Test plan: make check-all

[alexander-shaposhnikov]

fix typo

[smeenai]

llvm/tools/llvm-objcopy/MachO/Object.cpp

31

This is gonna reorder the actual section load commands, right? Is that okay?

44

Would SmallPtrSet be better?

[jhenderson]

llvm/test/tools/llvm-objcopy/MachO/remove-section-dead-symbols.test

5

What's the reason for dumping the sections here?

llvm/test/tools/llvm-objcopy/MachO/remove-section-error.test

3

You can probably use /dev/null as the output file here.

99

I know that mach-o yaml2obj requires very noisy output, but I'm guessing you don't need eh_frame data at least? Similarly, is there anything else you can remove?

llvm/tools/llvm-objcopy/MachO/Object.cpp

1

Could you fix the missing licence header please? Can be a separate change, no review needed.

[alexander-shaposhnikov]

llvm/test/tools/llvm-objcopy/MachO/remove-section-dead-symbols.test

5

we have removed one section ("C") - thus we'd like to verify that the list of sections is correct
["text", "data"]

[alexander-shaposhnikov]

llvm/test/tools/llvm-objcopy/MachO/remove-section-error.test

99

it's kinda hard to remove things from here because it's tedious and error-prone to manually recalculate (e.g. harder than for ELF) the offsets specified in various places (e.g. in the load commands) and still get a valid binary (so that it can be parsed by llvm-readobj/llvm-objdump/otool).

this is particular test is based on a real world binary:

a.c: 
    __attribute__((section("__DATA,C"))) int a = 2;
    int f() { return a; }
clang -c a.c -o a.o

llvm/tools/llvm-objcopy/MachO/Object.cpp

1

sure, will do

[alexander-shaposhnikov]

llvm/test/tools/llvm-objcopy/MachO/remove-section-error.test

99

typo: this particular test is ...

[alexander-shaposhnikov]

llvm/test/tools/llvm-objcopy/MachO/remove-section-error.test

99

clang -fno-exceptions -fno-unwind-tables -c a.o seems to work (to get rid of eh_frame, __compact_unwind), I'll trim down the test tomorrow.

[jhenderson]

llvm/test/tools/llvm-objcopy/MachO/remove-section-dead-symbols.test

5

I guess my question is more along the lines of "we test the section is removed elsewhere, so do we need to test here?" Happy either way, if you think there's additional value.

llvm/test/tools/llvm-objcopy/MachO/remove-section-error.test

99

Okay, got it. It might be worth including the input and compilation command somewhere in a comment, so that the output can be recreated if needed.

[alexander-shaposhnikov]

llvm/tools/llvm-objcopy/MachO/Object.cpp

31

this could be "remove_if" if "remove_if" didn't modify the elements.
https://en.cppreference.com/w/cpp/algorithm/remove
https://en.cppreference.com/w/cpp/algorithm/stable_partition
https://iterator.wordpress.com/2016/01/31/algorithms_0/ .
Quite the opposite - with std::stable_partition we preserve the order of sections which have not been removed.

[smeenai]

The Mach-O bits look good to me.

llvm/tools/llvm-objcopy/MachO/Object.cpp

31

Right, makes sense.

[alexander-shaposhnikov]

Address comments

[jhenderson]

LGTM, with one outstanding comment/question.

llvm/test/tools/llvm-objcopy/MachO/remove-section-dead-symbols.test

5

I guess my question is more along the lines of "we test the section is removed elsewhere, so do we need to test here?" Happy either way, if you think there's additional value.

Just flagging this repsonse up in case you missed it. Do you think there's additional value in testing it here as well as in the regular --remove-section test?

[alexander-shaposhnikov]

Update test

[alexander-shaposhnikov]

llvm/test/tools/llvm-objcopy/MachO/remove-section-dead-symbols.test

5

I don't have any strong preferences regarding this, I've updated the test (removed those lines).

[seiya]

LGTM once clang-format warnings are addressed and build bots are happy.

[alexander-shaposhnikov]

Apply clang-format

[MaskRay]

llvm/test/tools/llvm-objcopy/MachO/remove-section-dead-symbols.test

5

Delete --sections since the section lines are dropped.

[MaskRay]

llvm/tools/llvm-objcopy/MachO/MachOReader.cpp

114

Why is the type change?

[alexander-shaposhnikov]

llvm/tools/llvm-objcopy/MachO/MachOReader.cpp

114

because in Section Index has this type.

[alexander-shaposhnikov]

(fix formatting)

llvm/test/tools/llvm-objcopy/MachO/remove-section-dead-symbols.test

+# RUN: yaml2obj %s -o %t
+# RUN: llvm-objcopy --remove-section __DATA,C %t %t.copy
+
+# RUN: llvm-readobj --sections --symbols %t.copy | FileCheck %s
+
+# CHECK: Symbols [
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: _A (1)
+# CHECK-NEXT:     Extern
+# CHECK-NEXT:     Type: Section (0xE)
+# CHECK-NEXT:     Section: __data (0x2)
+# CHECK-NEXT:     RefType: UndefinedNonLazy (0x0)
+# CHECK-NEXT:     Flags [ (0x0)
+# CHECK-NEXT:     ]
+# CHECK-NEXT:     Value: 0x0
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
+
+--- !mach-o
+FileHeader:
+  magic:           0xFEEDFACF
+  cputype:         0x01000007
+  cpusubtype:      0x00000003
+  filetype:        0x00000001
+  ncmds:           4
+  sizeofcmds:      432
+  flags:           0x00002000
+  reserved:        0x00000000
+LoadCommands:
+  - cmd:             LC_SEGMENT_64
+    cmdsize:         312
+    segname:         ''
+    vmaddr:          0
+    vmsize:          8
+    fileoff:         464
+    filesize:        8
+    maxprot:         7
+    initprot:        7
+    nsects:          3
+    flags:           0
+    Sections:
+      - sectname:        __text
+        segname:         __TEXT
+        addr:            0x0000000000000000
+        size:            0
+        offset:          0x000001D0
+        align:           0
+        reloff:          0x00000000
+        nreloc:          0
+        flags:           0x80000000
+        reserved1:       0x00000000
+        reserved2:       0x00000000
+        reserved3:       0x00000000
+        content:         ''
+      - sectname:        __data
+        segname:         __DATA
+        addr:            0x0000000000000000
+        size:            4
+        offset:          0x000001D0
+        align:           2
+        reloff:          0x00000000
+        nreloc:          0
+        flags:           0x00000000
+        reserved1:       0x00000000
+        reserved2:       0x00000000
+        reserved3:       0x00000000
+        content:         '01000000'
+      - sectname:        C
+        segname:         __DATA
+        addr:            0x0000000000000004
+        size:            4
+        offset:          0x000001D4
+        align:           2
+        reloff:          0x00000000
+        nreloc:          0
+        flags:           0x00000000
+        reserved1:       0x00000000
+        reserved2:       0x00000000
+        reserved3:       0x00000000
+        content:         '02000000'
+  - cmd:             LC_VERSION_MIN_MACOSX
+    cmdsize:         16
+    version:         658944
+    sdk:             0
+  - cmd:             LC_SYMTAB
+    cmdsize:         24
+    symoff:          472
+    nsyms:           2
+    stroff:          504
+    strsize:         8
+  - cmd:             LC_DYSYMTAB
+    cmdsize:         80
+    ilocalsym:       0
+    nlocalsym:       0
+    iextdefsym:      0
+    nextdefsym:      2
+    iundefsym:       2
+    nundefsym:       0
+    tocoff:          0
+    ntoc:            0
+    modtaboff:       0
+    nmodtab:         0
+    extrefsymoff:    0
+    nextrefsyms:     0
+    indirectsymoff:  0
+    nindirectsyms:   0
+    extreloff:       0
+    nextrel:         0
+    locreloff:       0
+    nlocrel:         0
+LinkEditData:
+  NameList:
+    - n_strx:          4
+      n_type:          0x0F
+      n_sect:          2
+      n_desc:          0
+      n_value:         0
+    - n_strx:          1
+      n_type:          0x0F
+      n_sect:          3
+      n_desc:          0
+      n_value:         4
+  StringTable:
+    - ''
+    - _B
+    - _A
+    - ''
+...

llvm/test/tools/llvm-objcopy/MachO/remove-section-error.test

+# RUN: yaml2obj %s -o %t
+# RUN: not llvm-objcopy --remove-section __DATA,C %t /dev/null 2>&1 | FileCheck %s
+
+# CHECK: symbol '_a' defined in section with index '2' cannot be removed because it is referenced by a relocation in section '__TEXT,__text'
+
+## The binary used in this test was built as follows: 
+## main.c: 
+##   __attribute__((section("__DATA,C"))) int a = 2;
+##   int f() { return a; }
+## build command:
+## clang -fno-exceptions -fno-unwind-tables -c main.c -o main.o
+
+--- !mach-o
+FileHeader:
+  magic:           0xFEEDFACF
+  cputype:         0x01000007
+  cpusubtype:      0x00000003
+  filetype:        0x00000001
+  ncmds:           4
+  sizeofcmds:      360
+  flags:           0x00002000
+  reserved:        0x00000000
+LoadCommands:
+  - cmd:             LC_SEGMENT_64
+    cmdsize:         232
+    segname:         ''
+    vmaddr:          0
+    vmsize:          16
+    fileoff:         392
+    filesize:        16
+    maxprot:         7
+    initprot:        7
+    nsects:          2
+    flags:           0
+    Sections:
+      - sectname:        __text
+        segname:         __TEXT
+        addr:            0x0000000000000000
+        size:            12
+        offset:          0x00000188
+        align:           4
+        reloff:          0x00000198
+        nreloc:          1
+        flags:           0x80000400
+        reserved1:       0x00000000
+        reserved2:       0x00000000
+        reserved3:       0x00000000
+        content:         554889E58B05000000005DC3
+        relocations:
+          - address:         0x00000006
+            symbolnum:       0
+            pcrel:           true
+            length:          2
+            extern:          true
+            type:            1
+            scattered:       false
+            value:           0
+      - sectname:        C
+        segname:         __DATA
+        addr:            0x000000000000000C
+        size:            4
+        offset:          0x00000194
+        align:           2
+        reloff:          0x00000000
+        nreloc:          0
+        flags:           0x00000000
+        reserved1:       0x00000000
+        reserved2:       0x00000000
+        reserved3:       0x00000000
+        content:         '02000000'
+  - cmd:             LC_BUILD_VERSION
+    cmdsize:         24
+    platform:        1
+    minos:           658944
+    sdk:             658944
+    ntools:          0
+  - cmd:             LC_SYMTAB
+    cmdsize:         24
+    symoff:          416
+    nsyms:           2
+    stroff:          448
+    strsize:         8
+  - cmd:             LC_DYSYMTAB
+    cmdsize:         80
+    ilocalsym:       0
+    nlocalsym:       0
+    iextdefsym:      0
+    nextdefsym:      2
+    iundefsym:       2
+    nundefsym:       0
+    tocoff:          0
+    ntoc:            0
+    modtaboff:       0
+    nmodtab:         0
+    extrefsymoff:    0
+    nextrefsyms:     0
+    indirectsymoff:  0
+    nindirectsyms:   0
+    extreloff:       0
+    nextrel:         0
+    locreloff:       0
+    nlocrel:         0
+LinkEditData:
+  NameList:
+    - n_strx:          4
+      n_type:          0x0F
+      n_sect:          2
+      n_desc:          0
+      n_value:         12
+    - n_strx:          1
+      n_type:          0x0F
+      n_sect:          1
+      n_desc:          0
+      n_value:         0
+  StringTable:
+    - ''
+    - _f
+    - _a
+    - ''
+...

llvm/tools/llvm-objcopy/MachO/MachOObjcopy.cpp

 
 namespace llvm {
 namespace objcopy {
 namespace macho {
 
 using namespace object;
 using SectionPred = std::function<bool(const std::unique_ptr<Section> &Sec)>;
 
-static void removeSections(const CopyConfig &Config, Object &Obj) {
+static Error removeSections(const CopyConfig &Config, Object &Obj) {
   SectionPred RemovePred = [](const std::unique_ptr<Section> &) { return false; };
 
   if (!Config.ToRemove.empty()) {
     RemovePred = [&Config, RemovePred](const std::unique_ptr<Section> &Sec) {
       return Config.ToRemove.matches(Sec->CanonicalName);
     };
   }
 
if (Config.AllowBrokenLinks || !Config.BuildIdLinkDir.empty() ||
       Config.StripNonAlloc || Config.StripSections || Config.Weaken ||
       Config.DecompressDebugSections || Config.StripNonAlloc ||
       Config.StripSections || Config.StripUnneeded ||
       Config.DiscardMode == DiscardType::Locals ||
       !Config.SymbolsToAdd.empty() || Config.EntryExpr) {
     return createStringError(llvm::errc::invalid_argument,
                              "option not supported by llvm-objcopy for MachO");
   }
-  removeSections(Config, Obj);
+
+  if (Error E = removeSections(Config, Obj))
+    return E;
 
   // Mark symbols to determine which symbols are still needed.
   if (Config.StripAll)
     markSymbols(Config, Obj);
 
   updateAndRemoveSymbols(Config, Obj);
 
   if (Config.StripAll)

llvm/tools/llvm-objcopy/MachO/MachOReader.cpp

void MachOReader::readHeader(Object &O) const {
   O.Header.CPUSubType = MachOObj.getHeader().cpusubtype;
   O.Header.FileType = MachOObj.getHeader().filetype;
   O.Header.NCmds = MachOObj.getHeader().ncmds;
   O.Header.SizeOfCmds = MachOObj.getHeader().sizeofcmds;
   O.Header.Flags = MachOObj.getHeader().flags;
 }
 
 template <typename SectionType>
-Section constructSectionCommon(SectionType Sec) {
+Section constructSectionCommon(SectionType Sec, uint32_t Index) {
   StringRef SegName(Sec.segname, strnlen(Sec.segname, sizeof(Sec.segname)));
   StringRef SectName(Sec.sectname, strnlen(Sec.sectname, sizeof(Sec.sectname)));
   Section S(SegName, SectName);
+  S.Index = Index;
   S.Addr = Sec.addr;
   S.Size = Sec.size;
   S.Offset = Sec.offset;
   S.Align = Sec.align;
   S.RelOff = Sec.reloff;
   S.NReloc = Sec.nreloc;
   S.Flags = Sec.flags;
   S.Reserved1 = Sec.reserved1;
   S.Reserved2 = Sec.reserved2;
   S.Reserved3 = 0;
   return S;
 }
 
-template <typename SectionType> Section constructSection(SectionType Sec);
+template <typename SectionType> Section constructSection(SectionType Sec, uint32_t Index);
 
-template <> Section constructSection(MachO::section Sec) {
-  return constructSectionCommon(Sec);
+template <> Section constructSection(MachO::section Sec, uint32_t Index) {
+  return constructSectionCommon(Sec, Index);
 }
 
-template <> Section constructSection(MachO::section_64 Sec) {
-  Section S = constructSectionCommon(Sec);
+template <> Section constructSection(MachO::section_64 Sec, uint32_t Index) {
+  Section S = constructSectionCommon(Sec, Index);
   S.Reserved3 = Sec.reserved3;
   return S;
 }
 
 // TODO: get rid of reportError and make MachOReader return Expected<> instead.
 template <typename SectionType, typename SegmentType>
 std::vector<std::unique_ptr<Section>>
 extractSections(const object::MachOObjectFile::LoadCommandInfo &LoadCmd,
                 const object::MachOObjectFile &MachOObj,
-                size_t &NextSectionIndex) {
+                uint32_t &NextSectionIndex) {
   auto End = LoadCmd.Ptr + LoadCmd.C.cmdsize;
   const SectionType *Curr =
       reinterpret_cast<const SectionType *>(LoadCmd.Ptr + sizeof(SegmentType));
   std::vector<std::unique_ptr<Section>> Sections;
   for (; reinterpret_cast<const void *>(Curr) < End; Curr++) {
     if (MachOObj.isLittleEndian() != sys::IsLittleEndianHost) {
       SectionType Sec;
       memcpy((void *)&Sec, Curr, sizeof(SectionType));
       MachO::swapStruct(Sec);
-      Sections.push_back(std::make_unique<Section>(constructSection(Sec)));
+      Sections.push_back(std::make_unique<Section>(constructSection(Sec, NextSectionIndex)));
     } else {
-      Sections.push_back(std::make_unique<Section>(constructSection(*Curr)));
+      Sections.push_back(std::make_unique<Section>(constructSection(*Curr, NextSectionIndex)));
     }
 
     Section &S = *Sections.back();
 
     Expected<object::SectionRef> SecRef =
         MachOObj.getSection(NextSectionIndex++);
     if (!SecRef)
       reportError(MachOObj.getFileName(), SecRef.takeError());
for (; reinterpret_cast<const void *>(Curr) < End; Curr++) {
     assert(S.NReloc == S.Relocations.size() &&
            "Incorrect number of relocations");
   }
   return Sections;
 }
 
 void MachOReader::readLoadCommands(Object &O) const {
   // For MachO sections indices start from 1.
-  size_t NextSectionIndex = 1;
+  uint32_t NextSectionIndex = 1;
   for (auto LoadCmd : MachOObj.load_commands()) {
     LoadCommand LC;
     switch (LoadCmd.C.cmd) {
     case MachO::LC_SEGMENT:
       LC.Sections = extractSections<MachO::section, MachO::segment_command>(
           LoadCmd, MachOObj, NextSectionIndex);
       break;
     case MachO::LC_SEGMENT_64:

llvm/tools/llvm-objcopy/MachO/Object.h

struct MachHeader {
   uint32_t NCmds;
   uint32_t SizeOfCmds;
   uint32_t Flags;
   uint32_t Reserved = 0;
 };
 
 struct RelocationInfo;
 struct Section {
+  uint32_t Index;
   std::string Segname;
   std::string Sectname;
   // CanonicalName is a string formatted as “<Segname>,<Sectname>".
   std::string CanonicalName;
   uint64_t Addr = 0;
   uint64_t Size = 0;
   uint32_t Offset = 0;
   uint32_t Align = 0;
bool isExternalSymbol() const {
     return n_type & ((MachO::N_EXT | MachO::N_PEXT));
   }
 
   bool isLocalSymbol() const { return !isExternalSymbol(); }
 
   bool isUndefinedSymbol() const {
     return (n_type & MachO::N_TYPE) == MachO::N_UNDF;
   }
+
+  Optional<uint32_t> section() const {
+    return n_sect == MachO::NO_SECT ? None : Optional<uint32_t>(n_sect);
+  }
 };
 
 /// The location of the symbol table inside the binary is described by LC_SYMTAB
 /// load command.
 struct SymbolTable {
   std::vector<std::unique_ptr<SymbolEntry>> Symbols;
 
   using iterator = pointee_iterator<
struct Object {
   /// The index LC_FUNCTION_STARTS load comamnd if present.
   Optional<size_t> FunctionStartsCommandIndex;
 
   BumpPtrAllocator Alloc;
   StringSaver NewSectionsContents;
 
   Object() : NewSectionsContents(Alloc) {}
 
-  void removeSections(function_ref<bool(const std::unique_ptr<Section> &)> ToRemove);
+  Error removeSections(function_ref<bool(const std::unique_ptr<Section> &)> ToRemove);
   void addLoadCommand(LoadCommand LC);
 
   /// Creates a new segment load command in the object and returns a reference
   /// to the newly created load command. The caller should verify that SegName
   /// is not too long (SegName.size() should be less than or equal to 16).
   LoadCommand &addSegment(StringRef SegName);
 
   bool is64Bit() const {
     return Header.Magic == MachO::MH_MAGIC_64 ||
            Header.Magic == MachO::MH_CIGAM_64;
   }
 };
 
 } // end namespace macho
 } // end namespace objcopy
 } // end namespace llvm
 
 #endif // LLVM_OBJCOPY_MACHO_OBJECT_H

llvm/tools/llvm-objcopy/MachO/Object.cpp

 #include "Object.h"
 #include "../llvm-objcopy.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include <unordered_set>
 
 namespace llvm {
 namespace objcopy {
 namespace macho {
 
 const SymbolEntry *SymbolTable::getSymbolByIndex(uint32_t Index) const {
   assert(Index < Symbols.size() && "invalid symbol index");
   return Symbols[Index].get();
 }
 
 SymbolEntry *SymbolTable::getSymbolByIndex(uint32_t Index) {
   return const_cast<SymbolEntry *>(
       static_cast<const SymbolTable *>(this)->getSymbolByIndex(Index));
 }
 
 void SymbolTable::removeSymbols(
     function_ref<bool(const std::unique_ptr<SymbolEntry> &)> ToRemove) {
   Symbols.erase(
       std::remove_if(std::begin(Symbols), std::end(Symbols), ToRemove),
       std::end(Symbols));
 }
 
-void Object::removeSections(function_ref<bool(const std::unique_ptr<Section> &)> ToRemove) {
-  for (LoadCommand &LC : LoadCommands)
-    LC.Sections.erase(std::remove_if(std::begin(LC.Sections),
-                                     std::end(LC.Sections), ToRemove),
-                      std::end(LC.Sections));
+Error Object::removeSections(
+    function_ref<bool(const std::unique_ptr<Section> &)> ToRemove) {
+  std::unordered_set<uint32_t> RemovedSectionsIndices;
+  for (LoadCommand &LC : LoadCommands) {
+    auto It = std::stable_partition(
+        std::begin(LC.Sections), std::end(LC.Sections),
+        [&](const std::unique_ptr<Section> &Sec) { return !ToRemove(Sec); });
+    for (auto I = It, End = LC.Sections.end(); I != End; ++I)
+      RemovedSectionsIndices.insert((*I)->Index);
+    LC.Sections.erase(It, LC.Sections.end());
+  }
+
+  auto IsDead = [&](const std::unique_ptr<SymbolEntry> &S) -> bool {
+    Optional<uint32_t> Section = S->section();
+    return (Section && RemovedSectionsIndices.count(*Section));
+  };
+
+  SmallPtrSet<const SymbolEntry *, 2> DeadSymbols;
+  for (const std::unique_ptr<SymbolEntry> &Sym : SymTable.Symbols)
+    if (IsDead(Sym))
+      DeadSymbols.insert(Sym.get());
+
+  for (const LoadCommand &LC : LoadCommands)
+    for (const std::unique_ptr<Section> &Sec : LC.Sections)
+      for (const RelocationInfo &R : Sec->Relocations)
+        if (R.Symbol && DeadSymbols.count(R.Symbol))
+          return createStringError(std::errc::invalid_argument,
+                                   "symbol '%s' defined in section with index "
+                                   "'%u' cannot be removed because it is "
+                                   "referenced by a relocation in section '%s'",
+                                   R.Symbol->Name.c_str(),
+                                   *(R.Symbol->section()),
+                                   Sec->CanonicalName.c_str());
+  SymTable.removeSymbols(IsDead);
+  return Error::success();
 }
 
 void Object::addLoadCommand(LoadCommand LC) {
   LoadCommands.push_back(std::move(LC));
 }
 
 template <typename SegmentType>
 static void constructSegment(SegmentType &Seg,