[llvm-objcopy] Make removeSectionReferences batched

[rupprecht]

Summary

Removing a large number of sections from a file with a lot of symbols can have abysmal (i.e. O(n^2)) performance, e.g. when running --only-section to extract one section out of a large file.

This comes from iterating over all symbols in the symbol table each time we remove a section, to remove references to the section we just removed.
Instead, do just one pass of symbol removal by passing a hash set of all the sections we'd like to remove references to.

This fixes a regression when running llvm-objcopy -j <one section> on an object file with many sections and symbols -- on my machine, running objcopy -j .keep_me huge-input.o /tmp/foo.o takes .3s with GNU objcopy, 1.3s with an updated llvm-objcopy, and 7+ minutes with llvm-objcopy prior to this patch.

[MaskRay]

The approach looks good to me, but is anyone concerned about the 3MB compressed file?

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

340 ↗

(On Diff #187053)

Do you consider a plural form?

[jhenderson]

Don't know if you're planning on using the description as your commit message (I usually do), but there's a typo in it: abyssmal -> abysmal.

llvm/test/tools/llvm-objcopy/ELF/only-section-huge.test

1 ↗

(On Diff #187053)

How does this test show reasonable performance in a CI run? I don't see anything that checks that the runtime is sane.

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

278 ↗

(On Diff #187053)

ArrayRef?

Also Sec -> Sections.

[rupprecht]

• vector->ArrayRef
• Pluralize Sections arg

[rupprecht]

In D58296#1400258, @MaskRay wrote:

The approach looks good to me, but is anyone concerned about the 3MB compressed file?

FWIW, this would be the 11th largest file:

$ find . -size +1M -print0 | xargs -0 du -sk | grep -v .git | sort -nr
15752   ./compiler-rt/test/builtins/Unit/udivmodti4_test.c
8124    ./lldb/unittests/Process/minidump/Inputs/fizzbuzz_wow64.dmp
8124    ./lldb/packages/Python/lldbsuite/test/functionalities/postmortem/wow64_minidump/fizzbuzz_wow64.dmp
7416    ./lldb/www/python_reference/lldb-pysrc.html
5404    ./llvm/test/MC/Disassembler/AMDGPU/gfx9_dasm_all.txt
5244    ./libcxxabi/test/test_demangle.pass.cpp
5108    ./llvm/test/MC/Disassembler/AMDGPU/gfx8_dasm_all.txt
3712    ./llvm/test/tools/sancov/Inputs/test-linux_android_aarch64
3688    ./llvm/test/MC/AMDGPU/gfx9_asm_all.s
3508    ./llvm/test/MC/AMDGPU/gfx8_asm_all.s
3352    ./llvm/test/tools/llvm-objcopy/ELF/Inputs/huge-input.o.gz

As mentioned in a comment though, I plan to pull it from the review.

llvm/test/tools/llvm-objcopy/ELF/only-section-huge.test

1 ↗

(On Diff #187053)

It doesn't -- it will just take a very long time, and hopefully buildbots would be configured to run with a timeout and kill the test if it takes too long.

I think I should actually revert the test portion of this change, but I can leave it up in phab until I commit it. Testing timeouts like this doesn't seem very common or well supported with lit. Also, someone on IRC (sorry, I forget who) suggested not writing a test with a timeout, because it could fail if it just happens to run on really slow hardware. Maybe I'll save it and commit it later if there's a better regression testing framework -- there is LNT, but I'm not sure if it's suited to this task.

[jhenderson]

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

1358 ↗

(On Diff #187452)

I'm staring at this and thinking that an unordered Set may be a better container for performance here, especially given our use of pointers, making the comparison and hashing operations cheap. It would remove the need for sort and binary_search in favour of a set lookup, which is (usually) constant time.

Have I missed something?

[jakehehrlich]

If we're just giving a set we might as well give the user a function instead right? That's a bit more general of an interface and easier to use. many-sections.o.gz is smaller than 3.3 MB right? I went to a lot of pains to make sure that I was uploading as small a file as was possible. Do we have large file support

cc @echristo who might have a better idea of what our limits are there.

[rupprecht]

In D58296#1404774, @jakehehrlich wrote:

If we're just giving a set we might as well give the user a function instead right? That's a bit more general of an interface and easier to use.

That's a good idea, and makes with experimenting with the lookup algorithm (switching out a vector for an unordered_set) trivial. Done,

many-sections.o.gz is smaller than 3.3 MB right? I went to a lot of pains to make sure that I was uploading as small a file as was possible. Do we have large file support

cc @echristo who might have a better idea of what our limits are there.

I'll update the patch description -- given concerns about the file size, I'll drop it when committing, but it's here for review if anyone wants to see it.
I could check in a tiny script instead and just generate it on the fly, but that ends up being very slow, so I'd rather check in a pre-built object if anything at all.

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

1358 ↗

(On Diff #187452)

Switched, although it is only a minor improvement:

python -m timeit -n 3 -r 10 -v -s 'import os' 'os.system("llvm-objcopy -j .keep_me /tmp/huge-input.o /tmp/foo.o")'

w/ sorted vector:
raw times: 4.23 4.14 4.16 4.17 4.27 4.22 4.13 4.14 4.14 4.2
3 loops, best of 10: 1.38 sec per loop

w/ unordered_set:
raw times: 3.83 3.75 3.85 3.77 3.76 3.87 3.81 3.82 3.84 3.83
3 loops, best of 10: 1.25 sec per loop

[rupprecht]

• Use function_ref to isolate the lookup logic to one place
• Use unordered_set

[echristo]

Awesome patch.

As far as the testcase:

Right now we don't really have anything in the testsuite that tackles "How long does something take?" and I'm not sure I want to add it here yet. One thing we could do is add it to projects/test-suite where there is some tracking of how long things take via lnt. I'm not quite sure how to do that here, but it could work.

[echristo]

One more comment:

I also have no objections to adding a test of this size if we need to for correctness concerns.

[MaskRay]

FWIW, this would be the 11th largest file:

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

1358 ↗

(On Diff #187452)

No preference here.. Is SmallPtrSet<const SectionBase *, ?> faster?

[rupprecht]

Looking at projects/test-suite; it doesn't seem to have much support for running other llvm tools, but I can add llvm-objcopy. Still planning to do that separately from this patch though.

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

1358 ↗

(On Diff #187452)

No, but it's not slower -- it produces numbers within noise.

[jhenderson]

LGTM.

I'm surprised at just how much slower we are than GNU objcopy still, but this is definitely a big win.

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

1358 ↗

(On Diff #187452)

Switched, although it is only a minor improvement:

I'll take a 10% performance improvement, thanks!

llvm/trunk/tools/llvm-objcopy/ELF/Object.h

public:
 
   SectionBase() = default;
   SectionBase(const SectionBase &) = default;
 
   virtual ~SectionBase() = default;
 
   virtual void initialize(SectionTableRef SecTable);
   virtual void finalize();
-  virtual Error removeSectionReferences(const SectionBase *Sec);
+  // Remove references to these sections. The list of sections must be sorted.
+  virtual Error
+  removeSectionReferences(function_ref<bool(const SectionBase *)> ToRemove);
   virtual Error removeSymbols(function_ref<bool(const Symbol &)> ToRemove);
   virtual void accept(SectionVisitor &Visitor) const = 0;
   virtual void accept(MutableSectionVisitor &Visitor) = 0;
   virtual void markSymbols();
 };
 
 class Segment {
 private:
class Section : public SectionBase {
   ArrayRef<uint8_t> Contents;
   SectionBase *LinkSection = nullptr;
 
 public:
   explicit Section(ArrayRef<uint8_t> Data) : Contents(Data) {}
 
   void accept(SectionVisitor &Visitor) const override;
   void accept(MutableSectionVisitor &Visitor) override;
-  Error removeSectionReferences(const SectionBase *Sec) override;
+  Error removeSectionReferences(
+      function_ref<bool(const SectionBase *)> ToRemove) override;
   void initialize(SectionTableRef SecTable) override;
   void finalize() override;
 };
 
 class OwnedDataSection : public SectionBase {
   MAKE_SEC_WRITER_FRIEND
 
   std::vector<uint8_t> Data;
void setShndxTable(SectionIndexSection *ShndxTable) {
     SectionIndexTable = ShndxTable;
   }
   const SectionIndexSection *getShndxTable() const { return SectionIndexTable; }
   const SectionBase *getStrTab() const { return SymbolNames; }
   const Symbol *getSymbolByIndex(uint32_t Index) const;
   Symbol *getSymbolByIndex(uint32_t Index);
   void updateSymbols(function_ref<void(Symbol &)> Callable);
 
-  Error removeSectionReferences(const SectionBase *Sec) override;
+  Error removeSectionReferences(
+      function_ref<bool(const SectionBase *)> ToRemove) override;
   void initialize(SectionTableRef SecTable) override;
   void finalize() override;
   void accept(SectionVisitor &Visitor) const override;
   void accept(MutableSectionVisitor &Visitor) override;
   Error removeSymbols(function_ref<bool(const Symbol &)> ToRemove) override;
 
   static bool classof(const SectionBase *S) {
     return S->Type == ELF::SHT_SYMTAB;

 class RelocSectionWithSymtabBase : public RelocationSectionBase {
   SymTabType *Symbols = nullptr;
   void setSymTab(SymTabType *SymTab) { Symbols = SymTab; }
 
 protected:
   RelocSectionWithSymtabBase() = default;
 
 public:
-  Error removeSectionReferences(const SectionBase *Sec) override;
+  Error removeSectionReferences(
+      function_ref<bool(const SectionBase *)> ToRemove) override;
   void initialize(SectionTableRef SecTable) override;
   void finalize() override;
 };
 
 class RelocationSection
     : public RelocSectionWithSymtabBase<SymbolTableSection> {
   MAKE_SEC_WRITER_FRIEND
 

llvm/trunk/tools/llvm-objcopy/ELF/Object.cpp

 #include "llvm/Support/Errc.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FileOutputBuffer.h"
 #include "llvm/Support/Path.h"
 #include <algorithm>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
+#include <unordered_set>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 namespace objcopy {
 namespace elf {
 
 using namespace object;
 using namespace ELF;
 
 template <class ELFT> void ELFWriter<ELFT>::writePhdr(const Segment &Seg) {
   uint8_t *B = Buf.getBufferStart();
   B += Obj.ProgramHdrSegment.Offset + Seg.Index * sizeof(Elf_Phdr);
   Elf_Phdr &Phdr = *reinterpret_cast<Elf_Phdr *>(B);
   Phdr.p_type = Seg.Type;
   Phdr.p_flags = Seg.Flags;
   Phdr.p_offset = Seg.Offset;
   Phdr.p_vaddr = Seg.VAddr;
   Phdr.p_paddr = Seg.PAddr;
   Phdr.p_filesz = Seg.FileSize;
   Phdr.p_memsz = Seg.MemSize;
   Phdr.p_align = Seg.Align;
 }
 
-Error SectionBase::removeSectionReferences(const SectionBase *Sec) {
+Error SectionBase::removeSectionReferences(
+    function_ref<bool(const SectionBase *)> ToRemove) {
   return Error::success();
 }
 
 Error SectionBase::removeSymbols(function_ref<bool(const Symbol &)> ToRemove) {
   return Error::success();
 }
 
 void SectionBase::initialize(SectionTableRef SecTable) {}
void SymbolTableSection::addSymbol(Twine Name, uint8_t Bind, uint8_t Type,
   Sym.Value = Value;
   Sym.Visibility = Visibility;
   Sym.Size = Size;
   Sym.Index = Symbols.size();
   Symbols.emplace_back(llvm::make_unique<Symbol>(Sym));
   Size += this->EntrySize;
 }
 
-Error SymbolTableSection::removeSectionReferences(const SectionBase *Sec) {
-  if (SectionIndexTable == Sec)
+Error SymbolTableSection::removeSectionReferences(
+    function_ref<bool(const SectionBase *)> ToRemove) {
+  if (ToRemove(SectionIndexTable))
     SectionIndexTable = nullptr;
-  if (SymbolNames == Sec) {
+  if (ToRemove(SymbolNames))
     return createStringError(llvm::errc::invalid_argument,
                              "String table %s cannot be removed because it is "
                              "referenced by the symbol table %s",
                              SymbolNames->Name.data(), this->Name.data());
-  }
   return removeSymbols(
-      [Sec](const Symbol &Sym) { return Sym.DefinedIn == Sec; });
+      [ToRemove](const Symbol &Sym) { return ToRemove(Sym.DefinedIn); });
 }
 
 void SymbolTableSection::updateSymbols(function_ref<void(Symbol &)> Callable) {
   std::for_each(std::begin(Symbols) + 1, std::end(Symbols),
                 [Callable](SymPtr &Sym) { Callable(*Sym); });
   std::stable_partition(
       std::begin(Symbols), std::end(Symbols),
       [](const SymPtr &Sym) { return Sym->Binding == STB_LOCAL; });

 }
 
 void SymbolTableSection::accept(MutableSectionVisitor &Visitor) {
   Visitor.visit(*this);
 }
 
 template <class SymTabType>
 Error RelocSectionWithSymtabBase<SymTabType>::removeSectionReferences(
-    const SectionBase *Sec) {
-  if (Symbols == Sec)
+    function_ref<bool(const SectionBase *)> ToRemove) {
+  if (ToRemove(Symbols))
     return createStringError(llvm::errc::invalid_argument,
                              "Symbol table %s cannot be removed because it is "
                              "referenced by the relocation section %s.",
                              Symbols->Name.data(), this->Name.data());
   return Error::success();
 }
 
 template <class SymTabType>

 void DynamicRelocationSection::accept(SectionVisitor &Visitor) const {
   Visitor.visit(*this);
 }
 
 void DynamicRelocationSection::accept(MutableSectionVisitor &Visitor) {
   Visitor.visit(*this);
 }
 
-Error Section::removeSectionReferences(const SectionBase *Sec) {
-  if (LinkSection == Sec)
+Error Section::removeSectionReferences(
+    function_ref<bool(const SectionBase *)> ToRemove) {
+  if (ToRemove(LinkSection))
     return createStringError(llvm::errc::invalid_argument,
                              "Section %s cannot be removed because it is "
                              "referenced by the section %s",
                              LinkSection->Name.data(), this->Name.data());
   return Error::success();
 }
 
 void GroupSection::finalize() {
if (SymbolTable != nullptr && ToRemove(*SymbolTable))
     SymbolTable = nullptr;
   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.
+  std::unordered_set<const SectionBase *> RemoveSections;
+  RemoveSections.reserve(std::distance(Iter, std::end(Sections)));
   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))
-      if (Error E = KeepSec->removeSectionReferences(RemoveSec.get()))
-        return E;
-  }
+    RemoveSections.insert(RemoveSec.get());
+  }
+    if (Error E = KeepSec->removeSectionReferences(
+            [&RemoveSections](const SectionBase *Sec) {
+              return RemoveSections.find(Sec) != RemoveSections.end();
+            }))
   // Now finally get rid of them all togethor.
   Sections.erase(Iter, std::end(Sections));
   return Error::success();
 }
 
 Error Object::removeSymbols(function_ref<bool(const Symbol &)> ToRemove) {
   if (SymbolTable)
     for (const SecPtr &Sec : Sections)