[ELF] Make foo@@v1 resolve undefined foo@v1

[MaskRay]

Summary

The symbol resolution rules for versioned symbols are:

• foo@@v1 (default version) resolves both undefined foo and foo@v1
• foo@v1 (non-default version) resolves undefined foo@v1

Note, foo@@v1 must be defined (the assembler errors if attempting to
create an undefined foo@@v1).

For defined foo@@v1 in a shared object, we call SymbolTable::addSymbol twice,
one for foo and the other for foo@v1. We don't do the same for object files, so
foo@@v1 defined in one object file incorrectly does not resolve a foo@v1
reference in another object file.

This patch fixes the issue by reusing the --wrap code to redirect symbols in
object files. This has to be done after processing input files because
foo and foo@v1 are two separate symbols if we haven't seen foo@@v1.

Add a helper Symbol::getVersionSuffix to retrieve the optional trailing
@... or @@... from the possibly truncated symbol name.

Depends on D92258

[MaskRay]

(FWIW I have made some notes about symbol versioning at https://translate.google.com/translate?sl=zh-CN&tl=en&u=https%3A%2F%2Fmaskray.me%2Fblog%2F2020-11-26-all-about-symbol-versioning)
(Apparently people are annoyed by lack of symbol versioning documentation https://invisible-island.net/ncurses/ncurses-mapsyms.html :) )
(We may need one document under docs/ELF/ describing the LLD behavior)

[MaskRay]

Report duplicate symbol error even if foo@@v1 is weak

[MaskRay]

Test visibility

[grimar]

lld/ELF/Driver.cpp

1937

Should we add something like Symbol::getFullName or Symbol::getVersionedName?
The code like const char *end1 = name.data() + name.size() looks hacky. I'd isolate it.

1939

I'd suggest this change here and below for conisistency.

[jhenderson]

I'm not much of a symbol versioning expert (see my inline comment), but this approach seems reasonable to me at least.

In D92259#2421021, @MaskRay wrote:

(FWIW I have made some notes about symbol versioning at https://translate.google.com/translate?sl=zh-CN&tl=en&u=https%3A%2F%2Fmaskray.me%2Fblog%2F2020-11-26-all-about-symbol-versioning)
(Apparently people are annoyed by lack of symbol versioning documentation https://invisible-island.net/ncurses/ncurses-mapsyms.html :) )
(We may need one document under docs/ELF/ describing the LLD behavior)

In my opinion, you can never have too much documentation.

lld/ELF/Driver.cpp

1927–1928

Given the possibility for a significant link time cost to this section of code where there are lots of (versioned) symbols, perhaps it is worth adding a time scope to this function with this change?

1934

Seems to me like iterating through all symbols could be quite expensive, based on an assumption that most symbols aren't versioned. At least for our platform, we don't even support symbol versioning, so there shouldn't be ANY versioned symbols, meaning an unnecessary trawl through the symbols. Would we be better off recording earlier and then using here a list of versioned symbols?

1935–1936

There's a slight inconsistency in your grammar here - the first sentence refers to multiple symbols, but "Its name" implies a singular symbol. Probably best to rewrite as suggested.

1942

1952

lld/test/ELF/symver.s

18–20

43–44

Optional improvement to this check, as it will a) still pass if there are more than 10 section headers, and b) is shorter. (It will start matching against 0 too, but that should be printed as UND so there is no issue here).

You can use the same technique for the protected case too, if you want.

[MaskRay]

Comments

[MaskRay]

lld/ELF/Driver.cpp

1934

Added a TimeScope.

In my testing,
for a 4.9GiB output, redirectSymbols takes 49ms in a 31s link, so the cost seems acceptable.
For a 161MiB clang, redirectSymbols takes 14ms in the 923ms link, so the cost (1.5%) is a bit significant.

I added an early return below, then it just takes 2ms for clang. I think the cost is acceptable.

(On an unrelated thing, 048b16f7fbb745635b48d31ee957bb8865597606 reclaimed a 1%~1.7% performance loss.)

1937

Added Symbol::getVersionSuffix

[MaskRay]

Fix comments

[MaskRay]

Rebase

[grimar]

Minor nit. The rest looks probably good to me.

lld/ELF/Symbols.h

181

NUl->NUL

[jhenderson]

LGTM, once the nit is fixed.

[MaskRay]

NUl -> NUL

lld/ELF/Driver.cpp

for (auto *arg : args.filtered(OPT_wrap)) {
     // Tell LTO not to eliminate these symbols.
     sym->isUsedInRegularObj = true;
     if (!wrap->isUndefined())
       wrap->isUsedInRegularObj = true;
   }
   return v;
 }
 
-// Do renaming for -wrap by updating pointers to symbols.
+// Do renaming for -wrap and foo@v1 by updating pointers to symbols.
 //
 // When this function is executed, only InputFiles and symbol table
 // contain pointers to symbol objects. We visit them to replace pointers,
 // so that wrapped symbols are swapped as instructed by the command line.
-static void wrapSymbols(ArrayRef<WrappedSymbol> wrapped) {
+static void redirectSymbols(ArrayRef<WrappedSymbol> wrapped) {
+  llvm::TimeTraceScope timeScope("Redirect symbols");
   DenseMap<Symbol *, Symbol *> map;
   for (const WrappedSymbol &w : wrapped) {
     map[w.sym] = w.wrap;
     map[w.real] = w.sym;
   }
+  for (Symbol *sym : symtab->symbols()) {
+    // Enumerate symbols with a non-default version (foo@v1).
+    StringRef name = sym->getName();
+    const char *suffix1 = sym->getVersionSuffix();
+    if (suffix1[0] != '@' || suffix1[1] == '@')
+      continue;
+
+    // Check whether the default version foo@@v1 exists. If it exists, the
+    // symbol can be found by the name "foo" in the symbol table.
+    Symbol *maybeDefault = symtab->find(name);
+    if (!maybeDefault)
+      continue;
+    const char *suffix2 = maybeDefault->getVersionSuffix();
+    if (suffix2[0] != '@' || suffix2[1] != '@' ||
+        strcmp(suffix1 + 1, suffix2 + 2) != 0)
+      continue;
+
+    // foo@v1 and foo@@v1 should be merged, so redirect foo@v1 to foo@@v1.
+    map.try_emplace(sym, maybeDefault);
+    // If both foo@v1 and foo@@v1 are defined and non-weak, report a duplicate
+    // definition error.
+    maybeDefault->resolve(*sym);
+    // Eliminate foo@v1 from the symbol table.
+    sym->symbolKind = Symbol::PlaceholderKind;
+  }
+
+  if (map.empty())
+    return;
 
   // Update pointers in input files.
   parallelForEach(objectFiles, [&](InputFile *file) {
     MutableArrayRef<Symbol *> syms = file->getMutableSymbols();
     for (size_t i = 0, e = syms.size(); i != e; ++i)
       if (Symbol *s = map.lookup(syms[i]))
         syms[i] = s;
   });
template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
   // options to create output files in bitcode or assembly code
   // repsectively. No object files are generated.
   // Also bail out here when only certain thinLTO modules are specified for
   // compilation. The intermediate object file are the expected output.
   if (config->thinLTOIndexOnly || config->emitLLVM || config->ltoEmitAsm ||
       !config->thinLTOModulesToCompile.empty())
     return;
 
-  // Apply symbol renames for -wrap.
-  if (!wrapped.empty())
-    wrapSymbols(wrapped);
+  // Apply symbol renames for -wrap and combine foo@v1 and foo@@v1.
+  redirectSymbols(wrapped);
 
   {
     llvm::TimeTraceScope timeScope("Aggregate sections");
     // Now that we have a complete list of input files.
     // Beyond this point, no new files are added.
     // Aggregate all input sections into one place.
     for (InputFile *f : objectFiles)
       for (InputSectionBase *s : f->getSections())

lld/ELF/Symbols.h

public:
 
   void setName(StringRef s) {
     nameData = s.data();
     nameSize = s.size();
   }
 
   void parseSymbolVersion();
 
+  // Get the NUL-terminated version suffix ("", "@...", or "@@...").
+  //
+  // For @@, the name has been truncated by insert(). For @, the name has been
+  // truncated by Symbol::parseSymbolVersion().
+  const char *getVersionSuffix() const {
+    assert(nameSize != (uint32_t)-1);
+    return nameData + nameSize;
+  }
+
   bool isInGot() const { return gotIndex != -1U; }
   bool isInPlt() const { return pltIndex != -1U; }
 
   uint64_t getVA(int64_t addend = 0) const;
 
   uint64_t getGotOffset() const;
   uint64_t getGotVA() const;
   uint64_t getGotPltOffset() const;

lld/ELF/Symbols.cpp

if (elf::config->demangle)
     return demangleItanium(symName);
   return std::string(symName);
 }
 
 std::string lld::toString(const elf::Symbol &sym) {
   StringRef name = sym.getName();
   std::string ret = demangle(name);
 
-  // If sym has a non-default version, its name may have been truncated at '@'
-  // by Symbol::parseSymbolVersion(). Add the trailing part. This check is safe
-  // because every symbol name ends with '\0'.
-  if (name.data()[name.size()] == '@')
-    ret += name.data() + name.size();
+  const char *suffix = sym.getVersionSuffix();
+  if (*suffix == '@')
+    ret += suffix;
   return ret;
 }
 
 std::string lld::toELFString(const Archive::Symbol &b) {
   return demangle(b.getName());
 }
 
 Defined *ElfSym::bss;

lld/test/ELF/symver.s

 # RUN: llvm-mc -filetype=obj -triple=x86_64 %t/hid1.s -o %t/hid1.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %t/hid1w.s -o %t/hid1w.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %t/def2.s -o %t/def2.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %t/wrap.s -o %t/wrap.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %t/wrap1.s -o %t/wrap1.o
 # RUN: ld.lld -shared --soname=def1.so --version-script=%t/ver %t/def1.o -o %t/def1.so
 # RUN: ld.lld -shared --soname=hid1.so --version-script=%t/ver %t/hid1.o -o %t/hid1.so
 
-## TODO Report a duplicate definition error for foo@v1 and foo@@v1.
-# RUN: ld.lld -shared --version-script=%t/ver %t/def1.o %t/hid1.o -o /dev/null
-
+## Report a duplicate definition error for foo@v1 and foo@@v1.
+# RUN: not ld.lld -shared --version-script=%t/ver %t/def1.o %t/hid1.o -o /dev/null 2>&1 | \
+# RUN:   FileCheck %s --check-prefix=DUP
 # RUN: ld.lld -shared --version-script=%t/ver %t/def1w.o %t/hid1.o -o /dev/null
 # RUN: ld.lld -shared --version-script=%t/ver %t/def1.o %t/hid1w.o -o /dev/null
 # RUN: ld.lld -shared --version-script=%t/ver %t/def1w.o %t/hid1w.o -o /dev/null
 
-## TODO foo@@v1 should resolve undefined foo@v1.
-# RUN: not ld.lld -shared --version-script=%t/ver %t/ref1p.o %t/def1.o -o /dev/null
+# DUP:      error: duplicate symbol: foo@@v1
+# DUP-NEXT: >>> defined at {{.*}}/def1{{w?}}.o:(.text+0x0)
+# DUP-NEXT: >>> defined at {{.*}}/hid1.o:(.text+0x0)
+
+## Protected undefined foo@v1 makes the output symbol protected.
+# RUN: ld.lld -shared --version-script=%t/ver %t/ref1p.o %t/def1.o -o %t.protected
+# RUN: llvm-readelf --dyn-syms %t.protected | FileCheck %s --check-prefix=PROTECTED
+
+# PROTECTED:  NOTYPE GLOBAL PROTECTED [[#]] foo@@v1
 
-## TODO
 ## foo@@v1 resolves both undefined foo and foo@v1. There is one single definition.
 ## Note: set soname so that the name string referenced by .gnu.version_d is fixed.
 # RUN: ld.lld -shared --soname=t --version-script=%t/ver %t/ref.o %t/ref1.o %t/def1.o -o %t1
 # RUN: llvm-readelf -r --dyn-syms %t1 | FileCheck %s
 
-# CHECK:       Relocation section '.rela.plt' at offset {{.*}} contains 2 entries:
+# CHECK:       Relocation section '.rela.plt' at offset {{.*}} contains 1 entries:
 # CHECK-NEXT:  {{.*}} Type               {{.*}}
 # CHECK-NEXT:  {{.*}} R_X86_64_JUMP_SLOT {{.*}} foo@@v1 + 0
-# CHECK-NEXT:  {{.*}} R_X86_64_JUMP_SLOT {{.*}} foo + 0
 
-# CHECK:       1: {{.*}} NOTYPE GLOBAL DEFAULT UND   foo{{$}}
-# CHECK-NEXT:  2: {{.*}} NOTYPE GLOBAL DEFAULT [[#]] foo@@v1
+# CHECK:       1: {{.*}} NOTYPE GLOBAL DEFAULT [[#]] foo@@v1
 # CHECK-EMPTY:
 
 ## foo@@v2 does not resolve undefined foo@v1.
 ## TODO Undefined 'foo@v1' should be errored.
 # RUN: ld.lld -shared --soname=t --version-script=%t/ver %t/ref.o %t/ref1.o %t/def2.o -o %t2
 # RUN: llvm-readelf --dyn-syms %t2 | FileCheck %s --check-prefix=CHECK2
 
 # CHECK2:       1: {{.*}} NOTYPE GLOBAL DEFAULT UND   foo{{$}}

 
 ## Test the interaction with --wrap.
 
 ## The reference from ref.o is redirected. The reference from ref1.o is not.
 # RUN: ld.lld -shared --soname=t --version-script=%t/ver --wrap=foo %t/ref.o %t/ref1.o %t/def1.o %t/wrap.o -o %t.w1
 # RUN: llvm-readobj -r %t.w1 | FileCheck %s --check-prefix=W1REL
 # RUN: llvm-objdump -d --no-show-raw-insn %t.w1 | FileCheck %s --check-prefix=W1DIS
 
-## TODO foo should be foo@@v1.
 # W1REL:      .rela.plt {
 # W1REL-NEXT:   R_X86_64_JUMP_SLOT __wrap_foo 0x0
-# W1REL-NEXT:   R_X86_64_JUMP_SLOT foo 0x0
+# W1REL-NEXT:   R_X86_64_JUMP_SLOT foo@@v1 0x0
 # W1REL-NEXT: }
 
 # W1DIS-LABEL: <.text>:
 # W1DIS-NEXT:    callq {{.*}} <__wrap_foo@plt>
 # W1DIS-COUNT-3: int3
 # W1DIS-NEXT:    callq {{.*}} <foo@plt>
 
 ## The reference from ref.o is redirected. The reference from ref1.o is not.

 # W4REL-NEXT:   R_X86_64_JUMP_SLOT __wrap_foo@v1 0x0
 # W4REL-NEXT: }
 
 # W4DIS-LABEL: <.text>:
 # W4DIS-NEXT:    callq {{.*}} <foo@plt>
 # W4DIS-COUNT-3: int3
 # W4DIS-NEXT:    callq {{.*}} <__wrap_foo@plt>
 
-## TODO The two callq should jump to the same address.
 ## Note: GNU ld errors "no symbol version section for versioned symbol `__wrap_foo@@v1'".
 # RUN: ld.lld -shared --soname=t --version-script=%t/ver --wrap=foo@@v1 %t/ref.o %t/ref1.o %t/def1.o %t/wrap.o -o %t.w5
 # RUN: llvm-readobj -r %t.w5 | FileCheck %s --check-prefix=W5REL
 # RUN: llvm-objdump -d --no-show-raw-insn %t.w5 | FileCheck %s --check-prefix=W5DIS
 
 # W5REL:      .rela.plt {
 # W5REL-NEXT:   R_X86_64_JUMP_SLOT foo@@v1 0x0
-# W5REL-NEXT:   R_X86_64_JUMP_SLOT foo 0x0
 # W5REL-NEXT: }
 
 # W5DIS-LABEL: <.text>:
-# W5DIS-NEXT:    callq 0x1380 <foo@plt>
+# W5DIS-NEXT:    callq 0x1350 <foo@plt>
 # W5DIS-COUNT-3: int3
-# W5DIS-NEXT:    callq 0x1390 <foo@plt>
+# W5DIS-NEXT:    callq 0x1350 <foo@plt>
 
 #--- ver
 v1 {};
 v2 {};
 
 #--- ref.s
 call foo