[ELF] Initial support for wildcard in symbol versions

[davide]

Summary

VERSION_1.0 {
  global: foo*; 
  local: *; }

currently doesn't add any symbol to the dynamic symbol table because the code has no logic for wildcard(s).
This patch is an attempt to fix, only for the "easy" case when the wildcard matching is at the end of the word.

The patch is motivated by an example I found in the wild. In fact, libreoffice has a version script which looks like this:

PRIVATE_textenc.1 { # LibreOffice 3.6
    global:
        _ZN3sal6detail7textenc20convertCharToUnicode*;
        _ZN3sal6detail7textenc20convertUnicodeToChar*;
        _ZN3sal6detail7textenc32handleUndefinedUnicodeToTextChar*;
        _ZN3sal6detail7textenc37handleBadInputTextToUnicodeConversion*;
        _ZN3sal6detail7textenc37handleBadInputUnicodeToTextConversion*;
};

This patch implements the matching in the most naive way possible, i.e. through a linear scan of the symbol table for each requested matching. It could be probably improved switching symtab to a data structure that preserves ordering of elements, but that will slow down the common case, so I'm not entirely sure it's worth it.

Comments welcome.

[davide]

FWIW, I think we should bit the bullet and implement also generalized wildcard matching.
When I was taking a shot at the libreoffice version scripts I found:

_ZThn*_N4cppu30WeakAggComponentImplHelperBase7acquireEv;
_ZThn*_N4cppu30WeakAggComponentImplHelperBase7disposeEv;
_ZThn*_N4cppu30WeakAggComponentImplHelperBase7releaseEv;
_ZThn*_N4cppu16OComponentHelper14queryInterfaceERKN3com3sun4star3uno4TypeE;
_ZThn*_N4cppu16OComponentHelper16addEventListenerERKN3com3sun4star3uno9ReferenceINS3_4lang14XEventListenerEEE;
_ZThn*_N4cppu16OComponentHelper19removeEventListenerERKN3com3sun4star3uno9ReferenceINS3_4lang14XEventListenerEEE;
_ZThn*_N4cppu16OComponentHelper7acquireEv;
_ZThn*_N4cppu16OComponentHelper7disposeEv;
_ZThn*_N4cppu16OComponentHelper7releaseEv;
_ZThn*_N4cppu18OPropertySetHelper14queryInterfaceERKN3com3sun4star3uno4TypeE;
_ZThn*_N4cppu18OPropertySetHelper20getFastPropertyValueE?;
_ZThn*_N4cppu18OPropertySetHelper20setFastPropertyValueE?RKN3com3sun4star3uno3AnyE;
_ZThn*_N4cppu18OPropertySetHelper16getPropertyValueERKN3rtl8OUStringE;

There are also some of them which use ? matching, e.g.:

# Introducing a question mark at the end because of
# marginal type discrepancy there is a difference in the
# mangled name between Linux and Mac OS X, see #i69351#
_ZN9salhelper21SimpleReferenceObjectnwE?; # salhelper::SimpleReferenceObject::operator new (std::size_t)

[ruiu]

So a natural question to ask is how slow it is if you have symbol patterns that contain "*"? I'd appreciate if you run a benchmark.

Also, how slow is it if you use matchStr function defined in LinkerScript.cpp?

ELF/SymbolTable.cpp

435

This parameter is not actually a prefix but a pattern that could end with "*". So I'd name this Pattern.

438–440

if (SymbolBody *B = find(Prefix))
  Result.push_back(B);

[grimar]

Not sure how much crazy that idea is, but I was thinking about splitting the list of globals somehow.
One list can contain symbols without wildcards and can be processed in a tight loop, and the second
list with wildcards that probably should be processed using matchStr to support more complex cases.

[davide]

Rebase

[ruiu]

ELF/LinkerScript.h

101 ↗

(On Diff #62146)

This should be defined in lld::elf namespace.

ELF/SymbolTable.cpp

468–469

I think you can do

if (!HasWildcards)
  return {find(Pattern)};

ELF/SymbolTable.h

88

s/Prefix/Pattern/

[davide]

Rui's comments.

[ruiu]

Stylistic comments.

ELF/LinkerScript.cpp

292 ↗

(On Diff #62166)

I think you can remove lld::.

ELF/LinkerScript.h

99 ↗

(On Diff #62166)

Please move this line at beginning of this elf {} namespace.

ELF/SymbolTable.cpp

436

Naturally you want to move this line after the if.

[davide]

Another round of comments.

[ruiu]

LGTM

[ruiu]

ELF/SymbolTable.h

88

One more thing: please make this a private function.

ELF/SymbolTable.h

public:
 
   void scanUndefinedFlags();
   void scanShlibUndefined();
   void scanDynamicList();
   void scanVersionScript();
   void traceDefined();
 
   SymbolBody *find(StringRef Name);
+  std::vector<SymbolBody *> findAll(StringRef Prefix);
   void wrap(StringRef Name);
 
 private:
   std::pair<Symbol *, bool> insert(StringRef Name);
   std::pair<Symbol *, bool> insert(StringRef Name, uint8_t Type,
                                    uint8_t Visibility, bool CanOmitFromDynSym,
                                    bool IsUsedInRegularObj, InputFile *File);
 

ELF/SymbolTable.cpp

 template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef Name) {
   auto It = Symtab.find(Name);
   if (It == Symtab.end())
     return nullptr;
   return SymVector[It->second]->body();
 }
 
 template <class ELFT>
+std::vector<SymbolBody *> SymbolTable<ELFT>::findAll(StringRef Prefix) {
+  std::vector<SymbolBody *> Result;
+  if (!Prefix.endswith("*")) {
+    SymbolBody *B = find(Prefix);
+    if (B != nullptr)
+      Result.push_back(B);
+    return Result;
+  }
+  for (auto &It : Symtab)
+    if (It.first.Val.startswith(Prefix.rtrim("*")))
+      Result.push_back(SymVector[It.second]->body());
+  return Result;
+}
+
+template <class ELFT>
 void SymbolTable<ELFT>::addLazyArchive(
     ArchiveFile *F, const llvm::object::Archive::Symbol Sym) {
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) = insert(Sym.getName());
   if (WasInserted) {
     replaceBody<LazyArchive>(S, *F, Sym, SymbolBody::UnknownType);
     return;
   }
   if (!S->body()->isUndefined())
     return;
 
   // Weak undefined symbols should not fetch members from archives. If we were
   // to keep old symbol we would not know that an archive member was available
   // if a strong undefined symbol shows up afterwards in the link. If a strong
   // undefined symbol never shows up, this lazy symbol will get to the end of
   // the link and must be treated as the weak undefined one. We already marked
   // this symbol as used when we added it to the symbol table, but we also need
   // to preserve its type. FIXME: Move the Type field to Symbol.
   if (S->isWeak()) {
     replaceBody<LazyArchive>(S, *F, Sym, S->body()->Type);
     return;
   }
   MemoryBufferRef MBRef = F->getMember(&Sym);
   if (!MBRef.getBuffer().empty())
     addFile(createObjectFile(MBRef, F->getName()));
 }
 
if (!Config->VersionScriptGlobals.empty()) {
     return;
   }
 
   // If we have symbols version declarations, we should
   // assign version references for each symbol.
   size_t I = 2;
   for (Version &V : Config->SymbolVersions) {
     for (StringRef Name : V.Globals)
-      if (SymbolBody *B = find(Name)) {
+      for (SymbolBody *B : findAll(Name)) {
         if (B->symbol()->VersionId != VER_NDX_GLOBAL &&
             B->symbol()->VersionId != VER_NDX_LOCAL)
           error("duplicate symbol " + Name + " in version script");
         B->symbol()->VersionId = I;
       }
     ++I;
   }
 }

test/ELF/partial-version.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: echo "VERSION_1.0{      \
+# RUN:          global: foo*;  \
+# RUN:          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
+
+# CHECK: DynamicSymbols [
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: @
+# CHECK-NEXT:     Value: 0x0
+# CHECK-NEXT:     Size: 0
+# CHECK-NEXT:     Binding: Local
+# CHECK-NEXT:     Type: None
+# CHECK-NEXT:     Other: 0
+# CHECK-NEXT:     Section: Undefined
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: foo1@@VERSION_1.0
+# CHECK-NEXT:     Value: 0x1000
+# CHECK-NEXT:     Size: 0
+# CHECK-NEXT:     Binding: Global
+# CHECK-NEXT:     Type: None
+# CHECK-NEXT:     Other: 0
+# CHECK-NEXT:     Section: .text
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: foo2@@VERSION_1.0
+# CHECK-NEXT:     Value: 0x1001
+# CHECK-NEXT:     Size: 0
+# CHECK-NEXT:     Binding: Global
+# CHECK-NEXT:     Type: None
+# CHECK-NEXT:     Other: 0
+# CHECK-NEXT:     Section: .text
+# CHECK-NEXT:   }
+# CHECK-NEXT:   Symbol {
+# CHECK-NEXT:     Name: foo3@@VERSION_1.0
+# CHECK-NEXT:     Value: 0x1007
+# CHECK-NEXT:     Size: 0
+# CHECK-NEXT:     Binding: Global
+# CHECK-NEXT:     Type: None
+# CHECK-NEXT:     Other: 0
+# CHECK-NEXT:     Section: .text
+# CHECK-NEXT:   }
+# CHECK-NEXT: ]
+
+.globl foo1
+foo1:
+  ret
+
+.globl foo2
+foo2:
+  call foo1@PLT
+  ret
+
+.globl foo3
+foo3:
+  call foo2@PLT
+  ret
+
+.globl _start
+_start:
+  ret