Garbage collect dllimported symbols.

[ruiu]

Summary

Previously, the garbage collector (enabled by default or by explicitly
passing /opt:ref) did not kill dllimported symbols. As a result,
dllimported symbols could be added to resulting executables' dllimport
list even if no one was actually using them.

This patch implements dllexported symbol garbage collection. Just like
COMDAT sections, dllimported symbols now have Live bits to manage their
liveness, and MarkLive marks reachable dllimported symbols.

Fixes https://bugs.llvm.org/show_bug.cgi?id=32950

[pcc]

A high level question: we are already using chunks to represent "GOTs" and "PLTs" for imported symbols. Would it not work to move the live bit to Chunk and track liveness of these special chunks in the same way as with regular chunks?

[ruiu]

That should theoretically work, but I can imagine that that will be more complicated than this. Chunks for dllimported symbols are created not when they are read from file but when writer needs them, so at the time when MarkLive runs, chunks for dllimported symbols don't exist.

[pcc]

In D33264#756872, @ruiu wrote:

That should theoretically work, but I can imagine that that will be more complicated than this. Chunks for dllimported symbols are created not when they are read from file but when writer needs them, so at the time when MarkLive runs, chunks for dllimported symbols don't exist.

I see. We could always try and create the import chunks earlier though. But that seems like a separate potential refactoring.

lld/COFF/MarkLive.cpp

41

This could just use auto.

lld/COFF/Symbols.h

310

nit: "to the other symbol."

[ruiu]

lld/COFF/MarkLive.cpp

41

It doesn't compile, as this is a recursive function.

[ruiu]

I've submitted this change by mistake, but I got OK from Peter verbally.

lld/COFF/InputFiles.cpp

case IMPORT_NAME_UNDECORATE:
     ExtName = ltrim1(Name, "?@_");
     ExtName = ExtName.substr(0, ExtName.find('@'));
     break;
   }
 
   this->Hdr = Hdr;
   ExternalName = ExtName;
 
+  // Instantiate symbol objects.
   ImpSym = cast<DefinedImportData>(
       Symtab->addImportData(ImpName, this)->body());
-  if (Hdr->getType() == llvm::COFF::IMPORT_CONST)
+
+  if (Hdr->getType() == llvm::COFF::IMPORT_CONST) {
     ConstSym =
         cast<DefinedImportData>(Symtab->addImportData(Name, this)->body());
 
+    // A __imp_ and non-__imp_ symbols for the same dllimport'ed symbol
+    // should be gc'ed as a group. Add a bidirectional edge.
+    // Used by MarkLive.cpp.
+    ImpSym->Sibling = ConstSym;
+    ConstSym->Sibling = ImpSym;
+  }
+
   // If type is function, we need to create a thunk which jump to an
   // address pointed by the __imp_ symbol. (This allows you to call
   // DLL functions just like regular non-DLL functions.)
   if (Hdr->getType() != llvm::COFF::IMPORT_CODE)
     return;
   ThunkSym = cast<DefinedImportThunk>(
       Symtab->addImportThunk(Name, ImpSym, Hdr->Machine)->body());
 }

lld/COFF/MarkLive.cpp

 #include "Chunks.h"
 #include "Symbols.h"
 #include "llvm/ADT/STLExtras.h"
 #include <vector>
 
 namespace lld {
 namespace coff {
 
-// Set live bit on for each reachable chunk. Unmarked (unreachable)
-// COMDAT chunks will be ignored by Writer, so they will be excluded
-// from the final output.
+// Set live bit for each reachable COMDAT chunk and dllimported symbol.
+// Unmarked (or unreachable) chunks or symbols are ignored by Writer,
+// so they are not included in the final output.
 void markLive(const std::vector<Chunk *> &Chunks) {
   // We build up a worklist of sections which have been marked as live. We only
   // push into the worklist when we discover an unmarked section, and we mark
   // as we push, so sections never appear twice in the list.
   SmallVector<SectionChunk *, 256> Worklist;
 
-  // COMDAT section chunks are dead by default. Add non-COMDAT chunks.
+  // Non-COMDAT chunks are never be gc'ed, so they are gc-root.
   for (Chunk *C : Chunks)
     if (auto *SC = dyn_cast<SectionChunk>(C))
       if (SC->isLive())
         Worklist.push_back(SC);
 
   auto Enqueue = [&](SectionChunk *C) {
     if (C->isLive())
       return;
     C->markLive();
     Worklist.push_back(C);
   };
 
-  // Add GC root chunks.
+  // Mark a given symbol as reachable.
+  std::function<void(SymbolBody * B)> AddSym = [&](SymbolBody *B) {
+    if (auto *Sym = dyn_cast<DefinedRegular>(B)) {
+      Enqueue(Sym->getChunk());
+    } else if (auto *Sym = dyn_cast<DefinedImportData>(B)) {
+      if (Sym->Live)
+        return;
+      Sym->Live = true;
+      if (Sym->Sibling)
+        Sym->Sibling->Live = true;
+    } else if (auto *Sym = dyn_cast<DefinedImportThunk>(B)) {
+      if (Sym->Live)
+        return;
+      Sym->Live = true;
+      AddSym(Sym->WrappedSym);
+    } else if (auto *Sym = dyn_cast<DefinedLocalImport>(B)) {
+      AddSym(Sym->WrappedSym);
+    }
+  };
+
+  // Add gc-root symbols.
   for (SymbolBody *B : Config->GCRoot)
-    if (auto *D = dyn_cast<DefinedRegular>(B))
-      Enqueue(D->getChunk());
+    AddSym(B);
 
   while (!Worklist.empty()) {
     SectionChunk *SC = Worklist.pop_back_val();
     assert(SC->isLive() && "We mark as live when pushing onto the worklist!");
 
     // Mark all symbols listed in the relocation table for this section.
-    for (SymbolBody *S : SC->symbols())
-      if (auto *D = dyn_cast<DefinedRegular>(S))
-        Enqueue(D->getChunk());
+    for (SymbolBody *B : SC->symbols())
+      AddSym(B);
 
     // Mark associative sections if any.
     for (SectionChunk *C : SC->children())
       Enqueue(C);
   }
 }
 
 }
 }

lld/COFF/Symbols.h

 
 // This class represents a symbol imported from a DLL. This has two
 // names for internal use and external use. The former is used for
 // name resolution, and the latter is used for the import descriptor
 // table in an output. The former has "__imp_" prefix.
 class DefinedImportData : public Defined {
 public:
   DefinedImportData(StringRef N, ImportFile *F)
-      : Defined(DefinedImportDataKind, N), File(F) {
-  }
+      : Defined(DefinedImportDataKind, N), Live(!Config->DoGC), File(F) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedImportDataKind;
   }
 
   uint64_t getRVA() { return File->Location->getRVA(); }
+
   StringRef getDLLName() { return File->DLLName; }
   StringRef getExternalName() { return File->ExternalName; }
   void setLocation(Chunk *AddressTable) { File->Location = AddressTable; }
   uint16_t getOrdinal() { return File->Hdr->OrdinalHint; }
 
+  // If all sections referring a dllimported symbol become dead by gc,
+  // we want to kill the symbol as well, so that a resulting binary has
+  // fewer number of dependencies to DLLs. "Live" bit manages reachability.
+  bool Live;
+
+  // For a dllimported data symbol, we create two symbols.
+  // They should be considered as a unit by gc. This pointer points
+  // to each other
+  DefinedImportData *Sibling = nullptr;
+
 private:
   ImportFile *File;
 };
 
 // This class represents a symbol for a jump table entry which jumps
 // to a function in a DLL. Linker are supposed to create such symbols
 // without "__imp_" prefix for all function symbols exported from
 // DLLs, so that you can call DLL functions as regular functions with
 // a regular name. A function pointer is given as a DefinedImportData.
 class DefinedImportThunk : public Defined {
 public:
   DefinedImportThunk(StringRef Name, DefinedImportData *S, uint16_t Machine);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedImportThunkKind;
   }
 
   uint64_t getRVA() { return Data->getRVA(); }
   Chunk *getChunk() { return Data; }
 
+  // For GC.
+  bool Live;
+  DefinedImportData *WrappedSym;
+
 private:
   Chunk *Data;
 };
 
 // If you have a symbol "__imp_foo" in your object file, a symbol name
 // "foo" becomes automatically available as a pointer to "__imp_foo".
 // This class is for such automatically-created symbols.
 // Yes, this is an odd feature. We didn't intend to implement that.
 // This is here just for compatibility with MSVC.
 class DefinedLocalImport : public Defined {
 public:
   DefinedLocalImport(StringRef N, Defined *S)
-      : Defined(DefinedLocalImportKind, N), Data(make<LocalImportChunk>(S)) {}
+      : Defined(DefinedLocalImportKind, N), WrappedSym(S),
+        Data(make<LocalImportChunk>(S)) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedLocalImportKind;
   }
 
   uint64_t getRVA() { return Data->getRVA(); }
   Chunk *getChunk() { return Data; }
 
+  // For GC.
+  Defined *WrappedSym;
+
 private:
   LocalImportChunk *Data;
 };
 
 inline uint64_t Defined::getRVA() {
   switch (kind()) {
   case DefinedAbsoluteKind:
     return cast<DefinedAbsolute>(this)->getRVA();

lld/COFF/Symbols.cpp

COFFSymbolRef DefinedCOFF::getCOFFSymbol() {
   if (SymSize == sizeof(coff_symbol16))
     return COFFSymbolRef(reinterpret_cast<const coff_symbol16 *>(Sym));
   assert(SymSize == sizeof(coff_symbol32));
   return COFFSymbolRef(reinterpret_cast<const coff_symbol32 *>(Sym));
 }
 
 DefinedImportThunk::DefinedImportThunk(StringRef Name, DefinedImportData *S,
                                        uint16_t Machine)
-    : Defined(DefinedImportThunkKind, Name) {
+    : Defined(DefinedImportThunkKind, Name), Live(!Config->DoGC),
+      WrappedSym(S) {
   switch (Machine) {
   case AMD64: Data = make<ImportThunkChunkX64>(S); return;
   case I386:  Data = make<ImportThunkChunkX86>(S); return;
   case ARMNT: Data = make<ImportThunkChunkARM>(S); return;
   default:    llvm_unreachable("unknown machine type");
   }
 }
 

lld/COFF/Writer.cpp

for (ImportFile *File : Symtab->ImportFiles) {
     std::string DLL = StringRef(File->DLLName).lower();
     if (Config->DLLOrder.count(DLL) == 0)
       Config->DLLOrder[DLL] = Config->DLLOrder.size();
   }
 
   OutputSection *Text = createSection(".text");
   for (ImportFile *File : Symtab->ImportFiles) {
     if (DefinedImportThunk *Thunk = File->ThunkSym)
+      if (Thunk->Live)
         Text->addChunk(Thunk->getChunk());
+
     if (Config->DelayLoads.count(StringRef(File->DLLName).lower())) {
+      if (File->ImpSym->Live)
         DelayIdata.add(File->ImpSym);
     } else {
+      if (File->ImpSym->Live)
         Idata.add(File->ImpSym);
     }
   }
+
   if (!Idata.empty()) {
     OutputSection *Sec = createSection(".idata");
     for (Chunk *C : Idata.getChunks())
       Sec->addChunk(C);
   }
+
   if (!DelayIdata.empty()) {
     Defined *Helper = cast<Defined>(Config->DelayLoadHelper);
     DelayIdata.create(Helper);
     OutputSection *Sec = createSection(".didat");
     for (Chunk *C : DelayIdata.getChunks())
       Sec->addChunk(C);
     Sec = createSection(".data");
     for (Chunk *C : DelayIdata.getDataChunks())

lld/test/COFF/Inputs/import.yaml

 --- !COFF
 header:
   Machine:         IMAGE_FILE_MACHINE_AMD64
   Characteristics: []
 sections:
   - Name:            .text
     Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
     Alignment:       4
     SectionData:     0000000000000000
+    Relocations:
+  - VirtualAddress:  0
+        SymbolName:      exportfn1
+        Type:            IMAGE_REL_AMD64_ADDR32NB
+  - VirtualAddress:  4
+        SymbolName:      exportfn2
+        Type:            IMAGE_REL_AMD64_ADDR32NB
 symbols:
   - Name:            .text
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_NULL
     StorageClass:    IMAGE_SYM_CLASS_STATIC
     SectionDefinition:
       Length:          8
-      NumberOfRelocations: 0
+      NumberOfRelocations: 2
       NumberOfLinenumbers: 0
       CheckSum:        0
       Number:          0
   - Name:            main
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_FUNCTION

lld/test/COFF/dllimport-gc.test

+# REQUIRES: winres
+
+# RUN: yaml2obj < %p/Inputs/export.yaml > %t-lib.obj
+# RUN: lld-link /out:%t.dll /dll %t-lib.obj /implib:%t.lib /export:exportfn1
+
+# RUN: yaml2obj < %s > %t.obj
+
+# RUN: lld-link /out:%t1.exe /entry:main %t.obj %t.lib
+# RUN: llvm-readobj -coff-imports %t1.exe | FileCheck -check-prefix=REF %s
+# REF-NOT: Symbol: exportfn1
+
+# RUN: lld-link /out:%t2.exe /entry:main %t.obj %t.lib /opt:noref
+# RUN: llvm-readobj -coff-imports %t2.exe | FileCheck -check-prefix=NOREF %s
+# NOREF: Symbol: exportfn1
+
 --- !COFF
 header:
   Machine:         IMAGE_FILE_MACHINE_AMD64
   Characteristics: []
 sections:
   - Name:            .text
     Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
     Alignment:       4
     SectionData:     0000000000000000
+    Relocations:
 symbols:
   - Name:            .text
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_NULL
     StorageClass:    IMAGE_SYM_CLASS_STATIC
     SectionDefinition:
       Length:          8
-      NumberOfRelocations: 0
+      NumberOfRelocations: 2
       NumberOfLinenumbers: 0
       CheckSum:        0
       Number:          0
   - Name:            main
     Value:           0
     SectionNumber:   1
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
     StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
   - Name:            exportfn1
     Value:           0
     SectionNumber:   0
     SimpleType:      IMAGE_SYM_TYPE_NULL
     ComplexType:     IMAGE_SYM_DTYPE_NULL
     StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
-  - Name:            exportfn2
-    Value:           0
-    SectionNumber:   0
-    SimpleType:      IMAGE_SYM_TYPE_NULL
-    ComplexType:     IMAGE_SYM_DTYPE_NULL
-    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
 ...