[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

1275–1281

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

1275–1281

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

1275–1281

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

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

276

Can't you just use getSymbols instead of getLocalSymbols?

300–302

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

[ikudrin]

ELF/MarkLive.cpp

65

What about this?

// Weak symbols should not cause adding DT_NEEDED.

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

276

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.

300–302

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/MarkLive.cpp

 
 // There are normally few input sections whose names are valid C
 // identifiers, so we just store a std::vector instead of a multimap.
 static DenseMap<StringRef, std::vector<InputSectionBase *>> CNamedSections;
 
 template <class ELFT, class RelT>
 static void resolveReloc(InputSectionBase &Sec, RelT &Rel,
                          std::function<void(InputSectionBase *, uint64_t)> Fn) {
   Symbol &B = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
 
+  // If a symbol is referenced in a live section, it is alive.
+  B.ForceLive = true;
+
   if (auto *Sym = dyn_cast<SharedSymbol>(&B))
     if (!Sym->isWeak())
       cast<SharedFile<ELFT>>(Sym->File)->IsNeeded = true;
 
   if (auto *D = dyn_cast<Defined>(&B)) {
     if (!D->Section)
       return;
     uint64_t Offset = D->Value;
auto Enqueue = [&](InputSectionBase *Sec, uint64_t Offset) {
     Sec->Live = true;
 
     // Add input section to the queue.
     if (InputSection *S = dyn_cast<InputSection>(Sec))
       Q.push_back(S);
   };
 
   auto MarkSymbol = [&](Symbol *Sym) {
-    if (auto *S = dyn_cast_or_null<SharedSymbol>(Sym))
-      if (!S->isWeak())
-        cast<SharedFile<ELFT>>(S->File)->IsNeeded = true;
-
     if (auto *D = dyn_cast_or_null<Defined>(Sym))
       if (auto *IS = cast_or_null<InputSectionBase>(D->Section))
         Enqueue(IS, D->Value);
   };
 
   // Add GC root symbols.
   MarkSymbol(Symtab->find(Config->Entry));
   MarkSymbol(Symtab->find(Config->Init));

 template <class ELFT> void elf::markLive() {
   // If -gc-sections is missing, no sections are removed.
   if (!Config->GcSections) {
     for (InputSectionBase *Sec : InputSections)
       Sec->Live = true;
     return;
   }
 
   // The -gc-sections option works only for SHF_ALLOC sections
   // (sections that are memory-mapped at runtime). So we can
   // unconditionally make non-SHF_ALLOC sections alive.
   //
   // Non SHF_ALLOC sections are not removed even if they are
   // unreachable through relocations because reachability is not
   // a good signal whether they are garbage or not (e.g. there is
   // usually no section referring to a .comment section, but we
   // want to keep it.)
   //
   // Note on SHF_REL{,A}: Such sections reach here only when -r
   // or -emit-reloc were given. And they are subject of garbage
   // collection because, if we remove a text section, we also
   // remove its relocation section.
   for (InputSectionBase *Sec : InputSections) {
     bool IsAlloc = (Sec->Flags & SHF_ALLOC);
     bool IsRel = (Sec->Type == SHT_REL || Sec->Type == SHT_RELA);
     if (!IsAlloc && !IsRel)
       Sec->Live = true;
   }
 
   // Follow the graph to mark all live sections.
   doGcSections<ELFT>();
 
   // Report garbage-collected sections.
   if (Config->PrintGcSections)
     for (InputSectionBase *Sec : InputSections)
       if (!Sec->Live)
         message("removing unused section from '" + Sec->Name + "' in file '" +
                 Sec->File->getName() + "'");
 }
 
 template void elf::markLive<ELF32LE>();
 template void elf::markLive<ELF32BE>();
 template void elf::markLive<ELF64LE>();
 template void elf::markLive<ELF64BE>();

ELF/Symbols.h

public:
   uint32_t PltIndex = -1;
   uint32_t GlobalDynIndex = -1;
 
 protected:
   Symbol(Kind K, StringRefZ Name, uint8_t Binding, uint8_t StOther,
          uint8_t Type)
       : Binding(Binding), SymbolKind(K), NeedsPltAddr(false),
         IsInGlobalMipsGot(false), Is32BitMipsGot(false), IsInIplt(false),
-        IsInIgot(false), IsPreemptible(false), Type(Type), StOther(StOther),
-        Name(Name) {}
+        IsInIgot(false), IsPreemptible(false), ForceLive(false), Type(Type),
+        StOther(StOther), Name(Name) {}
 
   const unsigned SymbolKind : 8;
 
 public:
   // True the symbol should point to its PLT entry.
   // For SharedSymbol only.
   unsigned NeedsPltAddr : 1;
   // True if this symbol has an entry in the global part of MIPS GOT.
   unsigned IsInGlobalMipsGot : 1;
 
   // True if this symbol is referenced by 32-bit GOT relocations.
   unsigned Is32BitMipsGot : 1;
 
   // 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 GC marked this symbol alive because it is used in a live section.
+  unsigned ForceLive : 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
void replaceSymbol(Symbol *S, InputFile *File, ArgT &&... Arg) {
 
   S->VersionId = Sym.VersionId;
   S->Visibility = Sym.Visibility;
   S->IsUsedInRegularObj = Sym.IsUsedInRegularObj;
   S->ExportDynamic = Sym.ExportDynamic;
   S->CanInline = Sym.CanInline;
   S->Traced = Sym.Traced;
   S->InVersionScript = Sym.InVersionScript;
+  S->ForceLive = Sym.ForceLive;
 
   // Print out a log message if --trace-symbol was specified.
   // This is for debugging.
   if (S->Traced)
     printTraceSymbol(S);
 }
 } // namespace elf
 
 std::string toString(const elf::Symbol &B);
 } // namespace lld
 
 #endif

ELF/Writer.cpp

if (auto *IS = dyn_cast<InputSectionBase>(Sec)) {
       IS = cast<InputSectionBase>(Sec);
       // Exclude symbols pointing to garbage-collected sections.
       if (!IS->Live)
         return false;
     }
     if (auto *S = dyn_cast<MergeInputSection>(Sec))
       if (!S->getSectionPiece(D->Value)->Live)
         return false;
-  }
     return true;
   }
+  return B.ForceLive || !Config->GcSections;
+}
 
 // Local symbols are not in the linker's symbol table. This function scans
 // each object file's symbol table to copy local symbols to the output.
 template <class ELFT> void Writer<ELFT>::copyLocalSymbols() {
   if (!InX::SymTab)
     return;
   for (InputFile *File : ObjectFiles) {
     ObjFile<ELFT> *F = cast<ObjFile<ELFT>>(File);
template <class ELFT> void Writer<ELFT>::finalizeSections() {
 
   // Now that we have defined all possible global symbols including linker-
   // synthesized ones. Visit all symbols to give the finishing touches.
   for (Symbol *Sym : Symtab->getSymbols()) {
     if (!includeInSymtab(*Sym))
       continue;
     if (InX::SymTab)
       InX::SymTab->addSymbol(Sym);
 
     if (InX::DynSymTab && Sym->includeInDynsym()) {
       InX::DynSymTab->addSymbol(Sym);
       if (auto *SS = dyn_cast<SharedSymbol>(Sym))
         if (cast<SharedFile<ELFT>>(Sym->File)->IsNeeded)
           In<ELFT>::VerNeed->addSymbol(SS);
     }
   }
 
   // Do not proceed if there was an undefined symbol.
   if (errorCount())
     return;
 
   addPredefinedSections();
   removeUnusedSyntheticSections();

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/gc-sections-shared.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/shared.s -o %t2.o
 # RUN: ld.lld -shared %t2.o -o %t2.so
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/shared3.s -o %t3.o
+# RUN: ld.lld -shared %t3.o -o %t3.so
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
-# RUN: ld.lld --gc-sections --export-dynamic-symbol foo -o %t %t.o --as-needed %t2.so
+# RUN: ld.lld --gc-sections --export-dynamic-symbol foo -o %t %t.o --as-needed %t2.so %t3.so
 # RUN: llvm-readobj --dynamic-table --dyn-symbols %t | FileCheck %s
 
 # This test the property that we have a needed line for every undefined.
-# It would also be OK to drop bar2 and the need for the .so
+# '%t2.so' is dropped because 'bar2' is eliminated, whereas
+# '%t3.so' is preserved because 'baz' is used.
 
 # CHECK:      DynamicSymbols [
 # CHECK-NEXT:   Symbol {
 # CHECK-NEXT:     Name:
 # CHECK-NEXT:     Value:
 # CHECK-NEXT:     Size:
 # CHECK-NEXT:     Binding: Local
 # CHECK-NEXT:     Type:
 # CHECK-NEXT:     Other:
 # CHECK-NEXT:     Section: Undefined (0x0)
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: bar2
+# CHECK-NEXT:     Name: bar
 # CHECK-NEXT:     Value:
 # CHECK-NEXT:     Size:
 # CHECK-NEXT:     Binding: Global
 # CHECK-NEXT:     Type:
 # CHECK-NEXT:     Other:
-# CHECK-NEXT:     Section: Undefined
+# CHECK-NEXT:     Section: .text
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: bar
+# CHECK-NEXT:     Name: foo
 # CHECK-NEXT:     Value:
 # CHECK-NEXT:     Size:
 # CHECK-NEXT:     Binding: Global
 # CHECK-NEXT:     Type:
 # CHECK-NEXT:     Other:
 # CHECK-NEXT:     Section: .text
 # CHECK-NEXT:   }
 # CHECK-NEXT:   Symbol {
-# CHECK-NEXT:     Name: foo
+# CHECK-NEXT:     Name: baz
 # CHECK-NEXT:     Value:
 # CHECK-NEXT:     Size:
 # CHECK-NEXT:     Binding: Global
 # CHECK-NEXT:     Type:
 # CHECK-NEXT:     Other:
-# CHECK-NEXT:     Section: .text
+# CHECK-NEXT:     Section: Undefined
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
-# CHECK: NEEDED Shared library: [{{.*}}.so]
+# CHECK-NOT: NEEDED Shared library: [{{.*}}2.so]
+# CHECK:     NEEDED Shared library: [{{.*}}3.so]
 
 .section .text.foo, "ax"
 .globl foo
 foo:
 call bar
+call baz
 
 .section .text.bar, "ax"
 .globl bar
 bar:
 ret
 
 .section .text._start, "ax"
 .globl _start
 _start:
 ret
 
 .section .text.unused, "ax"
 call bar2