[ELF] Do not keep symbols if they referenced only from discarded sections.

[ikudrin]

Summary

Such symbols introduce unwanted dependencies.
In some cases, keeping them may even result in failing linking an executable.

[ikudrin]

Ping.

• Rebased on the tip.
• Slightly improved tests.

[ruiu]

I wonder if you really had to add a new flag to the symbol. includeInDynsym can return false if a symbol is in a dead section, no?

[ikudrin]

The symbol is not in a dead section but referenced from it. Right now I don't know any existing way to say if a symbol is referenced only from dead sections or not.

[ruiu]

ELF/Writer.cpp

1289–1299

I don't think this is logically correct. If includeInDynsym returns true, the symbol should be included in a .dynsym regardless of other conditions. You should modify other place so that includeInDynsym works correctly.

[ikudrin]

ELF/Writer.cpp

1289–1299

includeInDynsym is used when computing IsPreemptible. This flag is calculated before calling scanRelocations because it is used there. And with my approach, we can say that a symbol is useless only after scanRelocations is finished and the symbol has not been used anywhere.

includeInDynsym is also called in SymbolTable::handleDynamicList, even before GC. At that point, we can't say if a symbol is going to become unreferenced after GC or not.

What if we just rename includeInDynsym to something like maybeIncludeInDynsym?

[ruiu]

ELF/Writer.cpp

1289–1299

Still it doesn't feel right. It feels like is a violation of constraints each step in lld should maintain. This complex and subtle decision shouldn't be made at this late stage.

You are fixing an issue when -gc-section is given. In the garbage collector, you visit all relocations to see whether something is alive or not. So, can't you do everything in that phase?

[ikudrin]

• Rebase on the top.
• Add flag 'Live' to Symbol.
• Determine most of the alive symbols during GC phase.

[ruiu]

ELF/MarkLive.cpp

65 ↗

(On Diff #122219)

Why do you have to exclude weak symbols? Please expand (or replace) the comment to explain why this code should be like this.

281 ↗

(On Diff #122219)

Can't you just use getSymbols instead of getLocalSymbols?

310–312 ↗

(On Diff #122219)

Why do you need to keep such symbols? It seems like practically you can just ignore such symbols.

[ikudrin]

ELF/MarkLive.cpp

65 ↗

(On Diff #122219)

What about this?

// Weak symbols should not cause adding DT_NEEDED.

Anyway, it's mostly a replacement for the code removed from SymbolTable::addShared().

281 ↗

(On Diff #122219)

Not all symbols come from the object files. For example, in test/ELF/wrap.s, symbol __real_foo would disappear if we didn't process Symtab->getSymbols(). So, we have to process symbols from Symtab. Additionally, local symbols from object files should also be processed, but we don't need to scan global symbols again because they are already processed at the first step.

310–312 ↗

(On Diff #122219)

It's a replacement for the removed logic from includeInSymtab(). Now we have Live flag set for all existing symbols after GC phase.

There might be several cases when a symbol references an alive section, but we haven't seen it in relocations. For example:

$ cat a.s
.global _start, foo, bar
.text
_start:
	bl foo
	bl baz
.section .text.foo,"ax"
foo:
	nop
bar:
	nop
baz:
	nop
$ as a.s -o a.o
$ readelf -r a.o
Relocation section '.rela.text' at offset 0x178 contains 2 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000000  00090000011b R_AARCH64_CALL26  0000000000000000 foo + 0
000000000004  00060000011b R_AARCH64_CALL26  0000000000000000 .text.foo + 8
$ ld.lld --gc-sections a.o -o a.out

The question is, should symbols bar and baz be kept or not? As you can see, bar points to some location inside the section, but is not involved in any relocation. For baz, things are a bit different; it is used in the code but in the corresponding relocation a section symbol is used instead.

The current behavior of lld and other linkers (ld and gold) is consistent, as they all keep such symbols. I believe that, in any case, this patch should not change that because it is intended to solve another issue.

[ruiu]

I feel like this patch is a bit too complicated, but I can't really point out why I felt like that. This patch actually does two different things, no? Do you mind if I ask you to split it? I think one patch can be something like this https://reviews.llvm.org/D40240, and you can create another patch not to add dead symbols to the symbol table later.

[ikudrin]

• Extract corrections in the existing tests into D40253.
• Use handling of DT_NEEDED from D40240.
• Don't try to maintain actual Live flag for all symbols. Just mark symbols used in relocations in live sections and make the final decision later in includeInSymtab.

[ikudrin]

In D38790#930021, @ruiu wrote:

I feel like this patch is a bit too complicated, but I can't really point out why I felt like that. This patch actually does two different things, no? Do you mind if I ask you to split it? I think one patch can be something like this https://reviews.llvm.org/D40240, and you can create another patch not to add dead symbols to the symbol table later.

The main reason I did it that way is that ELF/gc-sections-shared.s test stated that an external symbol bar2 and DT_NEEDED entry for the corresponding library should be both eighter preserved or dropped. Thus, if dealing with DT_NEEDED is extracted into a separate patch, the test has to be adjusted to that intermediate state accordingly.

[ruiu]

Can you upload a patch again? It seems like this patch is not against master but against my patch.

[ikudrin]

• Do not depend on D40240.
• Mark test/ELF/gc-sections-shared.s to be in an intermediate state.

[ikudrin]

• Rebased on the tip.
• This is mostly Rafael's version of the patch.
• Added a check for a weak symbol when setting IsNeeded.
• Added the test to check that a weak symbol doesn't cause adding DT_NEEDED; this test might be extracted to a separate patch.

[ruiu]

LGTM

ELF/Relocations.cpp

 static void scanRelocs(InputSectionBase &Sec, ArrayRef<RelTy> Rels) {
   OffsetGetter GetOffset(Sec);
 
   for (auto I = Rels.begin(), End = Rels.end(); I != End; ++I) {
     const RelTy &Rel = *I;
     SymbolBody &Body = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
     uint32_t Type = Rel.getType(Config->IsMips64EL);
 
+    Body.IsUsedInReloc = true;
+
     if (Config->MipsN32Abi) {
       uint32_t Processed;
       std::tie(Type, Processed) =
           mergeMipsN32RelTypes(Type, Rel.r_offset, I + 1, End);
       I += Processed;
     }
 
     // Compute the offset of this section in the output section.

ELF/Symbols.h

public:
   // True if this symbol is in the Iplt sub-section of the Plt.
   unsigned IsInIplt : 1;
 
   // True if this symbol is in the Igot sub-section of the .got.plt or .got.
   unsigned IsInIgot : 1;
 
   unsigned IsPreemptible : 1;
 
+  // True if this symbol is referenced by some relocation.
+  unsigned IsUsedInReloc : 1;
+
   // The following fields have the same meaning as the ELF symbol attributes.
   uint8_t Type;    // symbol type
   uint8_t StOther; // st_other field value
 
   // The Type field may also have this value. It means that we have not yet seen
   // a non-Lazy symbol with this name, so we don't know what its type is. The
   // Type field is normally set to this value for Lazy symbols unless we saw a
   // weak undefined symbol first, in which case we need to remember the original

ELF/Symbols.cpp

static uint64_t getSymVA(const SymbolBody &Body, int64_t &Addend) {
   }
   llvm_unreachable("invalid symbol kind");
 }
 
 SymbolBody::SymbolBody(Kind K, StringRefZ Name, bool IsLocal, uint8_t StOther,
                        uint8_t Type)
     : SymbolKind(K), NeedsPltAddr(false), IsLocal(IsLocal),
       IsInGlobalMipsGot(false), Is32BitMipsGot(false), IsInIplt(false),
-      IsInIgot(false), IsPreemptible(false), Type(Type), StOther(StOther),
-      Name(Name) {}
+      IsInIgot(false), IsPreemptible(false), IsUsedInReloc(false), Type(Type),
+      StOther(StOther), Name(Name) {}
 
 bool SymbolBody::isUndefWeak() const {
   if (isLocal())
     return false;
   return symbol()->isWeak() && (isUndefined() || isLazy());
 }
 
 InputFile *SymbolBody::getFile() const {

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::finalizeSections() {
   for (Symbol *S : Symtab->getSymbols()) {
     SymbolBody *Body = S->body();
 
     if (!includeInSymtab(*Body))
       continue;
     if (InX::SymTab)
       InX::SymTab->addSymbol(Body);
 
     if (InX::DynSymTab && S->includeInDynsym()) {
+      if (Body->isUndefined() && !Body->IsUsedInReloc)
+        // This symbol was most probably used in a section, which was collected
+        // in the GC phase. We don't need such symbols in the dynamic symbols
+        // table because they solely introduce useless dependencies.
+        continue;
       InX::DynSymTab->addSymbol(Body);
       if (auto *SS = dyn_cast<SharedSymbol>(Body))
         if (cast<SharedFile<ELFT>>(S->File)->isNeeded())
           In<ELFT>::VerNeed->addSymbol(SS);
     }
   }
 
   // Do not proceed if there was an undefined symbol.
   if (ErrorCount)
     return;
 
   addPredefinedSections();
   removeUnusedSyntheticSections();

test/ELF/Inputs/gnu-hash-table.s

+.globl foo
+.data
+  .dc.a foo

test/ELF/Inputs/progname.s

+.global __progname
+.data
+  .dc.a __progname

test/ELF/gc-collect-undefined.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+# RUN: ld.lld %t -o %tout --gc-sections -shared
+# RUN: llvm-nm -D %tout | FileCheck %s
+
+# CHECK: bar
+# CHECK-NOT: qux
+
+  .global foo,bar,qux
+  .local baz
+
+  .section .data.foo,"aw",%progbits
+foo:
+  .dc.a bar
+
+  .section .bata.baz,"aw",%progbits
+baz:
+  .dc.a qux

test/ELF/gnu-hash-table.s

 # REQUIRES: x86,ppc
 
-# RUN: echo ".globl foo" > %te.s
-# RUN: llvm-mc -filetype=obj -triple=i386-pc-linux      %te.s -o %te-i386.o
+# RUN: llvm-mc -filetype=obj -triple=i386-pc-linux %S/Inputs/gnu-hash-table.s -o %te-i386.o
 # RUN: llvm-mc -filetype=obj -triple=i386-pc-linux      %s    -o %t-i386.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux    %s    -o %t-x86_64.o
 # RUN: llvm-mc -filetype=obj -triple=powerpc64-pc-linux %s    -o %t-ppc64.o
 
 # RUN: ld.lld -shared --hash-style=gnu  -o %te-i386.so  %te-i386.o
 # RUN: ld.lld -shared  -hash-style=gnu  -o %t-i386.so   %t-i386.o
 # RUN: ld.lld -shared  -hash-style=gnu  -o %t-x86_64.so %t-x86_64.o
 # RUN: ld.lld -shared --hash-style both -o %t-ppc64.so  %t-ppc64.o

 # PPC64-NEXT:   Bloom Filter: [0x400000000004204]
 # PPC64-NEXT:   Buckets: [2]
 # PPC64-NEXT:   Values: [0xB8860BA, 0xB887389]
 # PPC64-NEXT: }
 
 .globl foo,bar,baz
 foo:
 bar:
+.data
+  .dc.a baz

test/ELF/lto/Inputs/shlib-undefined.s

+.global __progname
+.data
+  .dc.a __progname

test/ELF/lto/shlib-undefined.ll

 ; REQUIRES: x86
 ; RUN: llvm-as %s -o %t.o
-; RUN: echo .global __progname > %t2.s
-; RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %t2.s -o %t2.o
+; RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %S/Inputs/shlib-undefined.s -o %t2.o
 ; RUN: ld.lld -shared %t2.o -o %t2.so
 ; RUN: ld.lld -o %t %t.o %t2.so
 ; RUN: llvm-readobj -dyn-symbols %t | FileCheck %s
 
 ; CHECK:      Name:     __progname@
 ; CHECK-NEXT: Value:    0x201010
 ; CHECK-NEXT: Size:     1
 ; CHECK-NEXT: Binding:  Global (0x1)

test/ELF/progname.s

 // REQUIRES: x86
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t.o
-// RUN: echo .global __progname > %t2.s
-// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %t2.s -o %t2.o
+// RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %S/Inputs/progname.s -o %t2.o
 // RUN: ld.lld -shared %t2.o -o %t2.so
 // RUN: ld.lld -o %t %t.o %t2.so
 // RUN: llvm-readobj -dyn-symbols %t | FileCheck %s
 
 // RUN: echo "VER_1 { global: bar; };" > %t.script
 // RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux \
 // RUN:   %p/Inputs/progname-ver.s -o %t-ver.o
 // RUN: ld.lld -shared -o %t.so -version-script %t.script %t-ver.o

test/ELF/undef-version-script.s

 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
 # RUN: echo "{ local: *; };" > %t.script
 # RUN: ld.lld --version-script %t.script -shared %t.o -o %t.so
 # RUN: llvm-readobj -dyn-symbols %t.so | FileCheck %s
 
-# This does not match gold's behavior because gold does not create undefined
-# symbols in dynsym without an appropriate (e.g. PLT) relocation in the input.
-
 # CHECK:      DynamicSymbols [
 # CHECK-NEXT:   Symbol {
 # CHECK-NEXT:     Name: @
 # CHECK-NEXT:     Value: 0x0
 # CHECK-NEXT:     Size: 0
 # CHECK-NEXT:     Binding: Local (0x0)
 # CHECK-NEXT:     Type: None (0x0)
 # CHECK-NEXT:     Other: 0

 # CHECK-NEXT:     Type: None (0x0)
 # CHECK-NEXT:     Other: 0
 # CHECK-NEXT:     Section: Undefined (0x0)
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
 .global foo
 .weak bar
+.data
+  .dc.a foo
+  .dc.a bar

test/ELF/weak-undef.s

 # CHECK-NEXT:     Section: Undefined
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
 .weak foo
 
 .globl _start
 _start:
+
+.data
+  .dc.a foo