[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

1924

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.

1926

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

1915

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?

1921

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?

1922–1923

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.

1929

1939

lld/test/ELF/symver.s

19

29

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

1921

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.)

1924

Added Symbol::getVersionSuffix

[MaskRay]

Fix comments

[MaskRay]

Rebase

[grimar]

Minor nit. The rest looks probably good to me.

lld/ELF/Symbols.h

181 ↗

(On Diff #308430)

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) {
   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). Its name was
+    // truncated at '@' by Symbol::parseSymbolVersion().
+    StringRef name = sym->getName();
+    const char *end1 = name.data() + name.size();
+    if (*end1 != '@' || end1[1] == '@')
+      continue;
+
+    // Check whether the default version foo@@v1 exists. If exists, the symbol
+    // can be found by the name "foo" in the symbol table.
+    Symbol *maybeDefault = symtab->find(name);
+    if (!maybeDefault)
+      continue;
+    const char *end2 =
+        maybeDefault->getName().data() + maybeDefault->getName().size();
+    if (*end2 != '@' || end2[1] != '@' || strcmp(end1 + 1, end2 + 2) != 0)
+      continue;
+
+    // foo@v1 and foo@@v1 should be considered as one symbol. So we redirect
+    // foo@v1 references to foo@@v1.
+    map.try_emplace(sym, maybeDefault);
+    // If foo@v1 is also definied, report a duplicate definition error.
+    sym->resolve(*maybeDefault);
+    // Eliminate foo@v1 from the symbol table.
+    sym->symbolKind = Symbol::PlaceholderKind;
+  }
 
   // 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/test/ELF/symver.s

 # REQUIRES: x86
 # RUN: split-file %s %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %t/ref.s -o %t/ref.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %t/ref1.s -o %t/ref1.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %t/def1.s -o %t/def1.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64 %t/hid1.s -o %t/hid1.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: 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 an 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 an 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
+
+# DUP:      error: duplicate symbol: foo@v1
+# DUP-NEXT: >>> defined at {{.*}}/hid1.o:(.text+0x0)
+# DUP-NEXT: >>> defined at {{.*}}/def1.o:(.text+0x0)
 
-## 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=t1 --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 {{[1-9]}} foo@@v1
+# CHECK:       1: {{.*}} NOTYPE GLOBAL DEFAULT {{[1-9]}} foo@@v1
 # CHECK-EMPTY:
 
 ## foo@@v2 does not resolve undefined foo@v1.
 ## TODO Undefined 'foo@v1' should be errored.
 # RUN: ld.lld -shared --soname=t2 --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{{$}}