[llvm-objcopy][ELF] Preserve sh_link to .symtab when applicable

[andrewng]

Summary

This change to llvm-objcopy preserves the ELF section sh_link to .symtab
so long as none of the symbol table indices have been changed.
Previously, any invocation of llvm-objcopy including a "no-op" would
clear any section sh_link to .symtab.

[andrewng]

Ping.

[MaskRay]

Sorry for the delay. This looks good me. Is the intention to make ld.lld --icf=safe work after certain llvm-objcopy operations? If so, it'd be good to state the motivation in the summary.
I think the change is good for other sh_link->SHT_SYMTAB sections.

I have a comment whether we should make new symbols (while existing symbol indices are unchanged) reset sh_link to zero.

I wonder whether we still consider changing the design of ELF SHT_LLVM_ADDRSIG (. Mach-O uses relocation-based __addrsig (https://discourse.llvm.org/t/problems-with-mach-o-address-significance-table-generation/63392 https://maskray.me/blog/2020-11-15-explain-gnu-linker-options#:~:text=icf).

llvm/lib/ObjCopy/ELF/ELFObject.cpp

693–694

Add {} for if and else. See https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

If the manual loop unswitching necessary? Can we just keep the else part?

2533

llvm/test/tools/llvm-objcopy/ELF/symtab-link.test

21

[MaskRay]

llvm/test/tools/llvm-objcopy/ELF/symtab-link.test

9

Perhaps add a comment to cover all the symbol index affecting operations, something like:

A section with sh_link referencing SHT_SYMTAB indicates that its content may use the old symbol indices.
If symbol indices changed, reset sh_link to 0 to inform tools like linkers that the link is invalidated.

[andrewng]

Sorry for the delay. This looks good me. Is the intention to make ld.lld --icf=safe work after certain llvm-objcopy operations? If so, it'd be good to state the motivation in the summary.
I think the change is good for other sh_link->SHT_SYMTAB sections.

No, this was not specifically done for SHT_LLVM_ADDRSIG but for some downstream sections.

I have a comment whether we should make new symbols (while existing symbol indices are unchanged) reset sh_link to zero.

I did consider this but decided not to reset sh_link to 0. Do you have a reason for why resetting sh_link to 0 in this scenario would be better/preferable?

llvm/lib/ObjCopy/ELF/ELFObject.cpp

693–694

If the manual loop unswitching necessary? Can we just keep the else part?

It's not needed but felt like a reasonable optimisation. Would you rather drop the optimisation?

[MaskRay]

In D150859#4373263, @andrewng wrote:

Sorry for the delay. This looks good me. Is the intention to make ld.lld --icf=safe work after certain llvm-objcopy operations? If so, it'd be good to state the motivation in the summary.
I think the change is good for other sh_link->SHT_SYMTAB sections.

No, this was not specifically done for SHT_LLVM_ADDRSIG but for some downstream sections.

I have a comment whether we should make new symbols (while existing symbol indices are unchanged) reset sh_link to zero.

I did consider this but decided not to reset sh_link to 0. Do you have a reason for why resetting sh_link to 0 in this scenario would be better/preferable?

The section content may be a digest of existing symbols. Adding a symbol nullifies its assumption that its content is comprehensive.
However, I don't have an example that this breaks.

llvm/lib/ObjCopy/ELF/ELFObject.cpp

693–694

I'd drop this optimization. It likely doesn't affect performance. There are complex symbol table operations elsewhere..

[andrewng]

I have a comment whether we should make new symbols (while existing symbol indices are unchanged) reset sh_link to zero.

I did consider this but decided not to reset sh_link to 0. Do you have a reason for why resetting sh_link to 0 in this scenario would be better/preferable?

The section content may be a digest of existing symbols. Adding a symbol nullifies its assumption that its content is comprehensive.
However, I don't have an example that this breaks.

Yes, the number of symbols could differ. I guess resetting sh_link to 0 would be the safer option but on the other hand if the user is making such modifications then it could be considered at their own risk.

[MaskRay]

In D150859#4376058, @andrewng wrote:

I have a comment whether we should make new symbols (while existing symbol indices are unchanged) reset sh_link to zero.

I did consider this but decided not to reset sh_link to 0. Do you have a reason for why resetting sh_link to 0 in this scenario would be better/preferable?

The section content may be a digest of existing symbols. Adding a symbol nullifies its assumption that its content is comprehensive.
However, I don't have an example that this breaks.

Yes, the number of symbols could differ. I guess resetting sh_link to 0 would be the safer option but on the other hand if the user is making such modifications then it could be considered at their own risk.

Thanks. The argument for not resetting sh_link to 0 for --add-symbol looks good to me.

[andrewng]

Updated for review comments and suggestions.

[MaskRay]

llvm/lib/ObjCopy/ELF/ELFObject.cpp

432

* -> & for a non-nullable pointer.

[jhenderson]

One question; otherwise looks good.

llvm/test/tools/llvm-objcopy/ELF/symtab-link.test

22

I'm probably missing something, but why does stripping the last symbol result in an index change (and therefore sh_link 0)?

[andrewng]

llvm/test/tools/llvm-objcopy/ELF/symtab-link.test

22

It's treated as a change to the indices because there's now less than there were before, i.e. the last symbol could have been referenced by the linked section. It is a bit conservative because you could add and then remove those symbols and still have all the "original" symbols but that would complicate the patch and seems an unusual use (less) case in reality.

lld/test/ELF/icf-safe.s

 # REQUIRES: x86
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
 # RUN: llvm-objcopy %t1.o %t1copy.o
+# RUN: llvm-objcopy --localize-symbol=h1 %t1.o %t1changed.o
+# RUN: ld.lld -r %t1.o -o %t1reloc.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/icf-safe.s -o %t2.o
 # RUN: ld.lld %t1.o %t2.o -o %t2 --icf=safe --print-icf-sections | FileCheck %s
+# RUN: ld.lld %t1copy.o %t2.o -o %t2 --icf=safe --print-icf-sections | FileCheck %s
 # RUN: ld.lld %t1.o %t2.o -o %t3 --icf=safe --print-icf-sections -shared | FileCheck --check-prefix=EXPORT %s
 # RUN: ld.lld %t1.o %t2.o -o %t3 --icf=safe --print-icf-sections --export-dynamic | FileCheck --check-prefix=EXPORT %s
 # RUN: ld.lld %t1.o %t2.o -o %t2 --icf=all --print-icf-sections | FileCheck --check-prefix=ALL %s
 # RUN: ld.lld %t1.o %t2.o -o %t2 --icf=all --print-icf-sections --export-dynamic | FileCheck --check-prefix=ALL-EXPORT %s
-# RUN: ld.lld %t1copy.o -o %t4 --icf=safe 2>&1 | FileCheck --check-prefix=OBJCOPY %s
+# RUN: ld.lld %t1changed.o -o %t4 --icf=safe 2>&1 | FileCheck --check-prefix=SH_LINK_0 %s
+# RUN: ld.lld %t1reloc.o -o %t4 --icf=safe 2>&1 | FileCheck --check-prefix=SH_LINK_0 %s
 
 # CHECK-NOT: selected section {{.*}}:(.text.f1)
 # CHECK: selected section {{.*}}:(.text.f3)
 # CHECK:   removing identical section {{.*}}:(.text.f4)
 
 # CHECK-NOT: selected section {{.*}}:(.rodata.h1)
 # CHECK: selected section {{.*}}:(.rodata.h3)
 # CHECK:   removing identical section {{.*}}:(.rodata.h4)

 # ALL-EXPORT:   removing identical section {{.*}}:(.rodata.l4)
 # ALL-EXPORT-NOT: selected section
 # ALL-EXPORT: selected section {{.*}}:(.text.f1)
 # ALL-EXPORT:   removing identical section {{.*}}:(.text.f2)
 # ALL-EXPORT:   removing identical section {{.*}}:(.text.non_addrsig1)
 # ALL-EXPORT:   removing identical section {{.*}}:(.text.non_addrsig2)
 # ALL-EXPORT-NOT: selected section
 
-# OBJCOPY: --icf=safe conservatively ignores SHT_LLVM_ADDRSIG [index [[#]]] with sh_link=0 (likely created using objcopy or ld -r)
+# SH_LINK_0: --icf=safe conservatively ignores SHT_LLVM_ADDRSIG [index [[#]]] with sh_link=0 (likely created using objcopy or ld -r)
 
 .section .text.f1,"ax",@progbits
 .globl f1
 f1:
 ret
 
 .section .text.f2,"ax",@progbits
 .globl f2

llvm/lib/ObjCopy/ELF/ELFObject.h

public:
   virtual Error accept(SectionVisitor &Visitor) const = 0;
   virtual Error accept(MutableSectionVisitor &Visitor) = 0;
   virtual void markSymbols();
   virtual void
   replaceSectionReferences(const DenseMap<SectionBase *, SectionBase *> &);
   virtual bool hasContents() const { return false; }
   // Notify the section that it is subject to removal.
   virtual void onRemove();
+
+  virtual void restoreSymTabLink(SymbolTableSection &) {}
 };
 
 class Segment {
 private:
   struct SectionCompare {
     bool operator()(const SectionBase *Lhs, const SectionBase *Rhs) const {
       // Some sections might have the same address if one of them is empty. To
       // fix this we can use the lexicographic ordering on ->Addr and the
public:
   ArrayRef<uint8_t> getContents() const { return Contents; }
 };
 
 class Section : public SectionBase {
   MAKE_SEC_WRITER_FRIEND
 
   ArrayRef<uint8_t> Contents;
   SectionBase *LinkSection = nullptr;
+  bool HasSymTabLink = false;
 
 public:
   explicit Section(ArrayRef<uint8_t> Data) : Contents(Data) {}
 
   Error accept(SectionVisitor &Visitor) const override;
   Error accept(MutableSectionVisitor &Visitor) override;
   Error removeSectionReferences(
       bool AllowBrokenLinks,
       function_ref<bool(const SectionBase *)> ToRemove) override;
   Error initialize(SectionTableRef SecTable) override;
   void finalize() override;
   bool hasContents() const override {
     return Type != ELF::SHT_NOBITS && Type != ELF::SHT_NULL;
   }
+  void restoreSymTabLink(SymbolTableSection &SymTab) override;
 };
 
 class OwnedDataSection : public SectionBase {
   MAKE_SEC_WRITER_FRIEND
 
   std::vector<uint8_t> Data;
 
 public:
class SymbolTableSection : public SectionBase {
 
   void setStrTab(StringTableSection *StrTab) { SymbolNames = StrTab; }
   void assignIndices();
 
 protected:
   std::vector<std::unique_ptr<Symbol>> Symbols;
   StringTableSection *SymbolNames = nullptr;
   SectionIndexSection *SectionIndexTable = nullptr;
+  bool IndicesChanged = false;
 
   using SymPtr = std::unique_ptr<Symbol>;
 
 public:
   SymbolTableSection() { Type = OriginalType = ELF::SHT_SYMTAB; }
 
   void addSymbol(Twine Name, uint8_t Bind, uint8_t Type, SectionBase *DefinedIn,
                  uint64_t Value, uint8_t Visibility, uint16_t Shndx,
                  uint64_t SymbolSize);
   void prepareForLayout();
   // An 'empty' symbol table still contains a null symbol.
   bool empty() const { return Symbols.size() == 1; }
+  bool indicesChanged() const { return IndicesChanged; }
   void setShndxTable(SectionIndexSection *ShndxTable) {
     SectionIndexTable = ShndxTable;
   }
   const SectionIndexSection *getShndxTable() const { return SectionIndexTable; }
   void fillShndxTable();
   const SectionBase *getStrTab() const { return SymbolNames; }
   Expected<const Symbol *> getSymbolByIndex(uint32_t Index) const;
   Expected<Symbol *> getSymbolByIndex(uint32_t Index);

llvm/lib/ObjCopy/ELF/ELFObject.cpp

 Error Section::accept(SectionVisitor &Visitor) const {
   return Visitor.visit(*this);
 }
 
 Error Section::accept(MutableSectionVisitor &Visitor) {
   return Visitor.visit(*this);
 }
 
+void Section::restoreSymTabLink(SymbolTableSection &SymTab) {
+  if (HasSymTabLink) {
+    assert(LinkSection == nullptr);
+    LinkSection = &SymTab;
+  }
+}
+
 Error SectionWriter::visit(const OwnedDataSection &Sec) {
   llvm::copy(Sec.Data, Out.getBufferStart() + Sec.Offset);
   return Error::success();
 }
 
 template <class ELFT>
 Error ELFSectionWriter<ELFT>::visit(const DecompressedSection &Sec) {
   ArrayRef<uint8_t> Compressed =
assert(ShndxType == SYMBOL_ABS || ShndxType == SYMBOL_COMMON ||
          (ShndxType >= SYMBOL_LOOS && ShndxType <= SYMBOL_HIOS));
   return static_cast<uint16_t>(ShndxType);
 }
 
 bool Symbol::isCommon() const { return getShndx() == SHN_COMMON; }
 
 void SymbolTableSection::assignIndices() {
   uint32_t Index = 0;
-  for (auto &Sym : Symbols)
+  for (auto &Sym : Symbols) {
+    if (Sym->Index != Index)
+      IndicesChanged = true;
     Sym->Index = Index++;
   }
+}
 
 void SymbolTableSection::addSymbol(Twine Name, uint8_t Bind, uint8_t Type,
                                    SectionBase *DefinedIn, uint64_t Value,
                                    uint8_t Visibility, uint16_t Shndx,
                                    uint64_t SymbolSize) {
   Symbol Sym;
   Sym.Name = Name.str();
   Sym.Binding = Bind;

 }
 
 Error SymbolTableSection::removeSymbols(
     function_ref<bool(const Symbol &)> ToRemove) {
   Symbols.erase(
       std::remove_if(std::begin(Symbols) + 1, std::end(Symbols),
                      [ToRemove](const SymPtr &Sym) { return ToRemove(*Sym); }),
       std::end(Symbols));
+  auto PrevSize = Size;
   Size = Symbols.size() * EntrySize;
+  if (Size < PrevSize)
+    IndicesChanged = true;
   assignIndices();
   return Error::success();
 }
 
 void SymbolTableSection::replaceSectionReferences(
     const DenseMap<SectionBase *, SectionBase *> &FromTo) {
   for (std::unique_ptr<Symbol> &Sym : Symbols)
     if (SectionBase *To = FromTo.lookup(Sym->DefinedIn))
Error Section::initialize(SectionTableRef SecTable) {
   Expected<SectionBase *> Sec =
       SecTable.getSection(Link, "Link field value " + Twine(Link) +
                                     " in section " + Name + " is invalid");
   if (!Sec)
     return Sec.takeError();
 
   LinkSection = *Sec;
 
-  if (LinkSection->Type == ELF::SHT_SYMTAB)
+  if (LinkSection->Type == ELF::SHT_SYMTAB) {
+    HasSymTabLink = true;
     LinkSection = nullptr;
+  }
 
   return Error::success();
 }
 
 void Section::finalize() { this->Link = LinkSection ? LinkSection->Index : 0; }
 
 void GnuDebugLinkSection::init(StringRef File) {
   FileName = sys::path::filename(File);
template <class ELFT> Error ELFWriter<ELFT>::finalize() {
   if (Obj.SectionNames == nullptr && WriteSectionHeaders)
     return createStringError(llvm::errc::invalid_argument,
                              "cannot write section header table because "
                              "section header string table was removed");
 
   if (Error E = removeUnneededSections(Obj))
     return E;
 
+  // If the .symtab indices have not been changed, restore the sh_link to
+  // .symtab for sections that were linked to .symtab.
+  if (Obj.SymbolTable && !Obj.SymbolTable->indicesChanged())
+    for (SectionBase &Sec : Obj.sections())
+      Sec.restoreSymTabLink(*Obj.SymbolTable);
+
   // We need to assign indexes before we perform layout because we need to know
   // if we need large indexes or not. We can assign indexes first and check as
   // we go to see if we will actully need large indexes.
   bool NeedsLargeIndexes = false;
   if (Obj.sections().size() >= SHN_LORESERVE) {
     SectionTableRef Sections = Obj.sections();
     // Sections doesn't include the null section header, so account for this
     // when skipping the first N sections.

llvm/test/tools/llvm-objcopy/ELF/symtab-link.test

 # RUN: yaml2obj %s -o %t
+## No-op copy.
 # RUN: llvm-objcopy %t %t2
 # RUN: llvm-readobj --sections %t2 | FileCheck %s
+## No-op strip.
 # RUN: cp %t %t3
 # RUN: llvm-strip --no-strip-all %t3
 # RUN: llvm-readobj --sections %t3 | FileCheck %s
+## Add symbol.
+# RUN: llvm-objcopy --add-symbol=another=.text:0,function %t %t4
+# RUN: llvm-readobj --sections %t4 | FileCheck %s
+
+## A section with sh_link referencing SHT_SYMTAB indicates that its content may
+## use the old symbol indices. If the symbol indices change, reset sh_link to 0
+## to inform tools like linkers that the sh_link has been invalidated.
+
+## Strip first symbol.
+# RUN: llvm-objcopy --strip-symbol bar %t %t5
+# RUN: llvm-readobj --sections %t5 | FileCheck %s --check-prefix=LINK-0
+## Strip last symbol.
+# RUN: llvm-objcopy --strip-symbol baz %t %t6
+# RUN: llvm-readobj --sections %t6 | FileCheck %s --check-prefix=LINK-0
+## Re-order symbols.
+# RUN: llvm-objcopy --localize-symbol baz %t %t7
+# RUN: llvm-readobj --sections %t7 | FileCheck %s --check-prefix=LINK-0
+## Remove .text section.
+# RUN: llvm-objcopy --remove-section=.text %t %t8
+# RUN: llvm-readobj --sections %t8 | FileCheck %s --check-prefix=LINK-0
 
 !ELF
 FileHeader:
   Class:           ELFCLASS64
   Data:            ELFDATA2LSB
   Type:            ET_REL
   Machine:         EM_X86_64
 Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x1000
+    AddressAlign:    0x0000000000000010
+    Size:            32
   - Name:            .foo
     Link:            .symtab
     Type:            SHT_PROGBITS
     Flags:           [ ]
-Symbols: []
+Symbols:
+  - Name:     bar
+    Type:     STT_FUNC
+    Size:     8
+    Section:  .text
+    Value:    0x1000
+    Binding:  STB_GLOBAL
+  - Name:     baz
+    Type:     STT_FUNC
+    Size:     8
+    Section:  .text
+    Value:    0x1010
+    Binding:  STB_GLOBAL
 
 # CHECK:      Name: .foo
 # CHECK-NEXT: Type:
 # CHECK-NEXT: Flags [ (0x0)
 # CHECK-NEXT: ]
 # CHECK-NEXT: Address:
 # CHECK-NEXT: Offset:
 # CHECK-NEXT: Size:
-# CHECK-NEXT: Link: 0
+# CHECK-NEXT: Link: [[#SYMTABIDX:]]
+
+# CHECK:      Index: [[#SYMTABIDX]]
+# CHECK-NEXT: Name: .symtab
+# CHECK-NEXT: Type: SHT_SYMTAB
+
+# LINK-0:      Name: .foo
+# LINK-0-NEXT: Type:
+# LINK-0-NEXT: Flags [ (0x0)
+# LINK-0-NEXT: ]
+# LINK-0-NEXT: Address:
+# LINK-0-NEXT: Offset:
+# LINK-0-NEXT: Size:
+# LINK-0-NEXT: Link: 0