[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

461

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

464–466

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

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

I think you can remove lld::.

ELF/LinkerScript.h

99

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

ELF/SymbolTable.cpp

462

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/LinkerScript.h

private:
   uintX_t Dot;
 };
 
 // Variable template is a C++14 feature, so we can't template
 // a global variable. Use a struct to workaround.
 template <class ELFT> struct Script { static LinkerScript<ELFT> *X; };
 template <class ELFT> LinkerScript<ELFT> *Script<ELFT>::X;
 
+bool matchStr(StringRef S, StringRef T);
+
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/LinkerScript.cpp

 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace lld;
 using namespace lld::elf;
 
 ScriptConfiguration *elf::ScriptConfig;
 
-static bool matchStr(StringRef S, StringRef T);
-
 // This is an operator-precedence parser to parse and evaluate
 // a linker script expression. For each linker script arithmetic
 // expression (e.g. ". = . + 0x1000"), a new instance of ExprParser
 // is created and ran.
 namespace {
 class ExprParser : public ScriptParserBase {
 public:
   ExprParser(std::vector<StringRef> &Tokens, uint64_t Dot)
int LinkerScript<ELFT>::compareSections(StringRef A, StringRef B) {
   if (I == INT_MAX && J == INT_MAX)
     return 0;
   return I < J ? -1 : 1;
 }
 
 // Returns true if S matches T. S can contain glob meta-characters.
 // The asterisk ('*') matches zero or more characters, and the question
 // mark ('?') matches one character.
-static bool matchStr(StringRef S, StringRef T) {
+bool lld::elf::matchStr(StringRef S, StringRef T) {
   for (;;) {
     if (S.empty())
       return T.empty();
     if (S[0] == '*') {
       S = S.substr(1);
       if (S.empty())
         // Fast path. If a pattern is '*', it matches anything.
         return true;

ELF/SymbolTable.h

public:
 
   void scanUndefinedFlags();
   void scanShlibUndefined();
   void scanDynamicList();
   void scanVersionScript();
   void traceDefined();
 
   SymbolBody *find(StringRef Name);
+  std::vector<SymbolBody *> findAll(StringRef Pattern);
   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

 // a hash table with the logic to resolve symbol name conflicts using
 // the symbol types.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolTable.h"
 #include "Config.h"
 #include "Error.h"
+#include "LinkerScript.h"
 #include "Symbols.h"
 #include "llvm/Bitcode/ReaderWriter.h"
 #include "llvm/Support/StringSaver.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::ELF;
 

 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 Pattern) {
+  std::vector<SymbolBody *> Result;
+
+  // Fast-path. Fallback to find() if Pattern doesn't contain any wildcard
+  // characters.
+  bool HasWildcards = (Pattern.find_first_of("?*") != StringRef::npos);
+  if (!HasWildcards)
+    return {find(Pattern)};
+
+  for (auto &It : Symtab)
+    if (matchStr(Pattern, It.first.Val))
+      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 (!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) {
-      SymbolBody *B = find(Name);
+      for (SymbolBody *B : findAll(Name)) {
         if (!B || B->isUndefined()) {
           if (Config->NoUndefinedVersion)
             error("version script assignment of " + V.Name + " to symbol " +
                   Name + " failed: symbol not defined");
           continue;
         }
 
         if (B->symbol()->VersionId != VER_NDX_GLOBAL &&
             B->symbol()->VersionId != VER_NDX_LOCAL)
           warning("duplicate symbol " + Name + " in version script");
         B->symbol()->VersionId = I;
       }
+    }
     ++I;
   }
 }
 
 // Print the module names which define the notified
 // symbols provided through -y or --trace-symbol option.
 template <class ELFT> void SymbolTable<ELFT>::traceDefined() {
   for (const auto &Symbol : Config->TraceSymbol)

test/ELF/version-wildcard.test

+# 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