[ELF] - Fixed incorrect logic of version assignments when mixing wildcards with values matching.

[grimar]

Summary

Previously we had incorrect logic here. Imagine we would have the next script:

LIBSAMPLE_1.0
{
  global:
   a_2;
 local:
  *;
};

LIBSAMPLE_2.0
{
  global:
   a*;
};

According to previous logic it would assign version 1 to a_2 and then
would try to reassign it to version 2 because of applying wildcard a*.
And show a warning about that.

Generally Ian Lance Tailor wrote about next rules that should be applied:
(http://www.airs.com/blog/archives/300)

Here are the current rules for gold:

• If there is an exact match for the mangled name, we use it.

If there is more than one exact match, we give a warning, and we use the first tag in the script which matches.
If a symbol has an exact match as both global and local for the same version tag, we give an error.

• Otherwise, we look for an extern C++ or an extern Java exact match. If we find an exact match, we use it.

If there is more than one exact match, we give a warning, and we use the first tag in the script which matches.
If a symbol has an exact match as both global and local for the same version tag, we give an error.

• Otherwise, we look through the wildcard patterns, ignoring “*” patterns. We look through the version tags in reverse order. For each version tag, we look through the global patterns and then the local patterns. We use the first match we find (i.e., the last matching version tag in the file).

• Otherwise, we use the “*” pattern if there is one. We give a warning if there are multiple “*” patterns.

Patch makes wildcard matching to be in revered order and to follow after the regular naming matching.

[grimar]

That probably looks a bit better. May be a wrong place for Reverser,
or may be we have something like that in LLVM already ? I did not find.

[ruiu]

ELF/Config.h

40

I think it's not worth to store this property as a member of this variable. You can always compute it from Name when needed.

ELF/SymbolTable.cpp

565–566

This function should probably be inlined to the place where you call it because non-wildcard patterns and wildcard patterns shares less code. For example, you don't need to call findAll for non-wildcards (but instead you want to call find). You don't want to issue a warning if non-wildcards. So this function is not actually common code for both cases.

617

Reverse is overkill. You can just iterate in the reverse order by this.

for (size_t I = Config->SymbolVersions.size() - 1; I != 0; --I) {
  VersionSymbol &Sym = Config->SymbolVersions[I];
  ...
}

[grimar]

ELF/Config.h

40

Idea here was to avoid several searches of "*?". Since I do 2 iterations now,
one for wildcarded names and one for not.

Also I planned to use this struct to add the flag
IsExternCpp or something for externs handling patch.

[ruiu]

ELF/Config.h

40

Yes, I understand that, but finding "*?" is pretty cheap, and number of symbols in version scripts is not that large.

[grimar]

ELF/Config.h

40

Ok.
So relative to possible patch for externs:
What about possible list of extern c++ symbols ? Do you suggest to make a separate array for them ?

[ruiu]

ELF/Config.h

40

I didn't suggest that -- IsExternCpp may make sense.

[grimar]

ELF/Config.h

40

Ok. So I am removing HasWildcard and VersionSymbol from this patch, and will probably add VersionSymbol back with IsExternCpp field for externs patch then.

ELF/SymbolTable.cpp

617

Sure I can :) That just looks a bit different from loop above making me think it do something special, when it is not.
Will fix.

[ruiu]

ELF/SymbolTable.cpp

617

I'd rewrite the above for-loop with an explicit index as well because &V - Config->SymbolVersions.data() is not intuitive.

[grimar]

ELF/SymbolTable.cpp

617

ok

[grimar]

• Addressed review comments.

ELF/SymbolTable.cpp

565–566

Done.

[grimar]

• minor changes.

[grimar]

• Restored testcase removed by mistake previously.

[ruiu]

ELF/SymbolTable.cpp

32

Early continue.

33

Define hasWildcard(StringRef S) and use early continue.

if (hasWildcard(Name))
  continue;

33–34

for (SymbolBody *B : findAll(Name))

[grimar]

• Addressed review comments.

ELF/SymbolTable.cpp

32

Done.

33

Done.

33–34

Done.

[ruiu]

LGTM with a few nits.

ELF/SymbolTable.cpp

609

You don't have to do this in this patch, but + 2 seems too magical and needs to be handled in a better way. I think it is better to add VersionId member to Version struct and store the version id to that member.

613

I >= 0

[grimar]

ELF/SymbolTable.cpp

613

This will not work. If for Config->SymbolVersions.size() == 1, for example,
first iteration will pass, but then since "I" is unsigned it will be equal 0xffffffff and loop will continue,
when it should terminate.
Changing to "I > 0" will not work as expected either.

[grimar]

ELF/SymbolTable.cpp

609

I`ll prepare a patch.

ELF/Config.h

enum ELFKind {
   ELF64LEKind,
   ELF64BEKind
 };
 
 enum class BuildIdKind { None, Fnv1, Md5, Sha1, Hexstring };
 
 enum class UnresolvedPolicy { NoUndef, Error, Warn, Ignore };
 
+struct VersionSymbol {
+  llvm::StringRef Name;
+  bool HasWildcard;
+};
+
 // This struct contains symbols version definition that
 // can be found in version script if it is used for link.
 struct Version {
   Version(llvm::StringRef Name) : Name(Name) {}
   llvm::StringRef Name;
   llvm::StringRef Parent;
-  std::vector<llvm::StringRef> Globals;
+  std::vector<VersionSymbol> Globals;
   size_t NameOff; // Offset in string table.
 };
 
 // This struct contains the global configuration for the linker.
 // Most fields are direct mapping from the command line options
 // and such fields have the same name as the corresponding options.
 // Most fields are initialized by the driver.
 struct Configuration {
struct Configuration {
   llvm::StringRef SoName;
   llvm::StringRef Sysroot;
   llvm::StringSet<> TraceSymbol;
   std::string RPath;
   std::vector<Version> SymbolVersions;
   std::vector<llvm::StringRef> DynamicList;
   std::vector<llvm::StringRef> SearchPaths;
   std::vector<llvm::StringRef> Undefined;
-  std::vector<llvm::StringRef> VersionScriptGlobals;
+  std::vector<VersionSymbol> VersionScriptGlobals;
   std::vector<uint8_t> BuildIdVector;
   bool AllowMultipleDefinition;
   bool AsNeeded = false;
   bool Bsymbolic;
   bool BsymbolicFunctions;
   bool Demangle = true;
   bool DisableVerify;
   bool DiscardAll;

ELF/SymbolListFile.cpp

 void VersionScriptParser::parseLocal() {
   expect("local:");
   expect("*");
   expect(";");
   Config->VersionScriptGlobalByDefault = false;
 }
 
 void VersionScriptParser::parseVersionSymbols(StringRef Version) {
-  std::vector<StringRef> *Globals;
+  std::vector<VersionSymbol> *Globals;
   if (Version.empty())
     Globals = &Config->VersionScriptGlobals;
   else
     Globals = &Config->SymbolVersions.back().Globals;
 
   for (;;) {
     StringRef Cur = peek();
     if (Cur == "extern")
       setError("extern keyword is not supported");
     if (Cur == "}" || Cur == "local:" || Error)
       return;
     next();
-    Globals->push_back(Cur);
+    Globals->push_back({Cur, Cur.find_first_of("?*") != StringRef::npos});
     expect(";");
   }
 }
 
 void VersionScriptParser::run() {
   StringRef Msg = "anonymous version definition is used in "
                   "combination with other version definitions";
   if (peek() == "{") {

ELF/SymbolTable.h

public:
   void scanDynamicList();
   void scanVersionScript();
   void traceDefined();
 
   SymbolBody *find(StringRef Name);
   void wrap(StringRef Name);
 
 private:
-  std::vector<SymbolBody *> findAll(StringRef Pattern);
+  std::vector<SymbolBody *> findAll(StringRef Pattern, bool NoWildcard);
   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);
 
   std::string conflictMsg(SymbolBody *Existing, InputFile *NewFile);
   void reportDuplicate(SymbolBody *Existing, InputFile *NewFile);
 
+  void applySymbolVersion(VersionSymbol &Sym, size_t Version);
+
   // The order the global symbols are in is not defined. We can use an arbitrary
   // order, but it has to be reproducible. That is true even when cross linking.
   // The default hashing of StringRef produces different results on 32 and 64
   // bit systems so we use a map to a vector. That is arbitrary, deterministic
   // but a bit inefficient.
   // FIXME: Experiment with passing in a custom hashing or sorting the symbols
   // once symbol resolution is finished.
   llvm::DenseMap<SymName, unsigned> Symtab;

ELF/SymbolTable.cpp

 #include "llvm/Support/StringSaver.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::ELF;
 
 using namespace lld;
 using namespace lld::elf;
 
 // All input object files must be for the same architecture
 // (e.g. it does not make sense to link x86 object files with
 // MIPS object files.) This function checks for that error.
 template <class ELFT> static bool isCompatible(InputFile *F) {
   if (!isa<ELFFileBase<ELFT>>(F) && !isa<BitcodeFile>(F))
     return true;
   if (F->EKind == Config->EKind && F->EMachine == Config->EMachine)
     return true;
   StringRef A = F->getName();
   StringRef B = Config->Emulation;
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();
 }
 
 // Returns a list of defined symbols that match with a given glob pattern.
 template <class ELFT>
-std::vector<SymbolBody *> SymbolTable<ELFT>::findAll(StringRef Pattern) {
+std::vector<SymbolBody *> SymbolTable<ELFT>::findAll(StringRef Pattern,
+                                                     bool NoWildcard) {
   // Fast-path. Fallback to find() if Pattern doesn't contain any wildcard
   // characters.
-  if (Pattern.find_first_of("?*") == StringRef::npos) {
+  if (NoWildcard) {
     if (SymbolBody *B = find(Pattern))
       if (!B->isUndefined())
         return {B};
     return {};
   }
 
   std::vector<SymbolBody *> Res;
   for (auto &It : Symtab) {

 // This function process the dynamic list option by marking all the symbols
 // to be exported in the dynamic table.
 template <class ELFT> void SymbolTable<ELFT>::scanDynamicList() {
   for (StringRef S : Config->DynamicList)
     if (SymbolBody *B = find(S))
       B->symbol()->ExportDynamic = true;
 }
 
+template <class ELFT>
+void SymbolTable<ELFT>::applySymbolVersion(VersionSymbol &Sym, size_t Version) {
+  std::vector<SymbolBody *> Syms = findAll(Sym.Name, !Sym.HasWildcard);
+  if (Syms.empty()) {
+    if (Config->NoUndefinedVersion)
+      error("version script assignment of " +
+            Config->SymbolVersions[Version].Name + " to symbol " + Sym.Name +
+            " failed: symbol not defined");
+    return;
+  }
+
+  for (SymbolBody *B : Syms) {
+    if (B->symbol()->VersionId == VER_NDX_GLOBAL ||
+        B->symbol()->VersionId == VER_NDX_LOCAL) {
+      B->symbol()->VersionId = Version + 2;
+      continue;
+    }
+
+    // It is ok that wildcard matches the symbol that already was assigned
+    // some version. Just skip it.
+    if (Sym.HasWildcard)
+      continue;
+
+    warning("duplicate symbol " + Sym.Name + " in version script");
+  }
+}
+
 // This function processes the --version-script option by marking all global
 // symbols with the VersionScriptGlobal flag, which acts as a filter on the
 // dynamic symbol table.
 template <class ELFT> void SymbolTable<ELFT>::scanVersionScript() {
   // If version script does not contain versions declarations,
   // we just should mark global symbols.
   if (!Config->VersionScriptGlobals.empty()) {
-    for (StringRef S : Config->VersionScriptGlobals)
-      if (SymbolBody *B = find(S))
+    for (VersionSymbol &S : Config->VersionScriptGlobals)
+      if (SymbolBody *B = find(S.Name))
         B->symbol()->VersionId = VER_NDX_GLOBAL;
     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) {
-      std::vector<SymbolBody *> Syms = findAll(Name);
-      if (Syms.empty()) {
-        if (Config->NoUndefinedVersion)
-          error("version script assignment of " + V.Name + " to symbol " +
-                Name + " failed: symbol not defined");
-        continue;
-      }
-
-      for (SymbolBody *B : Syms) {
-        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;
-  }
+  // Current rules are:
+  // * If there is an exact match for the mangled name, we use it.
+  // * Otherwise, we look through the wildcard patterns. We look through the
+  //   version tags in reverse order. We use the first match we find (the last
+  //   matching version tag in the file).
+  for (Version &V : Config->SymbolVersions)
+    for (VersionSymbol &Sym : V.Globals)
+      if (!Sym.HasWildcard)
+        applySymbolVersion(Sym, &V - Config->SymbolVersions.data());
+
+  std::for_each(Config->SymbolVersions.rbegin(), Config->SymbolVersions.rend(),
+                [this](Version &V) {
+                  for (VersionSymbol &Sym : V.Globals)
+                    if (Sym.HasWildcard)
+                      applySymbolVersion(Sym,
+                                         &V - Config->SymbolVersions.data());
+                });
 }
 
 // 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)
     if (SymbolBody *B = find(Symbol.getKey()))
       if (B->isDefined() || B->isCommon())

test/ELF/version-wildcard.test

 # CHECK-NEXT:     Size: 0
 # CHECK-NEXT:     Binding: Global
 # CHECK-NEXT:     Type: None
 # CHECK-NEXT:     Other: 0
 # CHECK-NEXT:     Section: .text
 # CHECK-NEXT:   }
 # CHECK-NEXT: ]
 
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.o
+# RUN: echo "VERSION_1.0{      \
+# RUN:          global: foo2;  \
+# RUN:          local: *; };   \
+# RUN:       VERSION_2.0{      \
+# RUN:          global: foo*;  \
+# RUN:       }; " > %t2.script
+# RUN: ld.lld --version-script %t2.script -shared %t.o -o %t2.so
+# RUN: llvm-readobj -dyn-symbols %t2.so | FileCheck --check-prefix=MIX %s
+
+# MIX:      DynamicSymbols [
+# MIX-NEXT:   Symbol {
+# MIX-NEXT:     Name: @
+# MIX-NEXT:     Value: 0x0
+# MIX-NEXT:     Size: 0
+# MIX-NEXT:     Binding: Local
+# MIX-NEXT:     Type: None
+# MIX-NEXT:     Other: 0
+# MIX-NEXT:     Section: Undefined
+# MIX-NEXT:   }
+# MIX-NEXT:   Symbol {
+# MIX-NEXT:     Name: foo1@@VERSION_2.0
+# MIX-NEXT:     Value: 0x1000
+# MIX-NEXT:     Size: 0
+# MIX-NEXT:     Binding: Global
+# MIX-NEXT:     Type: None
+# MIX-NEXT:     Other: 0
+# MIX-NEXT:     Section: .text
+# MIX-NEXT:   }
+# MIX-NEXT:   Symbol {
+# MIX-NEXT:     Name: foo2@@VERSION_1.0
+# MIX-NEXT:     Value: 0x1001
+# MIX-NEXT:     Size: 0
+# MIX-NEXT:     Binding: Global
+# MIX-NEXT:     Type: None
+# MIX-NEXT:     Other: 0
+# MIX-NEXT:     Section: .text
+# MIX-NEXT:   }
+# MIX-NEXT:   Symbol {
+# MIX-NEXT:     Name: foo3@@VERSION_2.0
+# MIX-NEXT:     Value: 0x1007
+# MIX-NEXT:     Size: 0
+# MIX-NEXT:     Binding: Global
+# MIX-NEXT:     Type: None
+# MIX-NEXT:     Other: 0
+# MIX-NEXT:     Section: .text
+# MIX-NEXT:   }
+# MIX-NEXT: ]
+
 .globl foo1
 foo1:
   ret
 
 .globl foo2
 foo2:
   call foo1@PLT
   ret