[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 ↗

(On Diff #62370)

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 ↗

(On Diff #62370)

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.

628 ↗

(On Diff #62370)

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 ↗

(On Diff #62370)

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 ↗

(On Diff #62370)

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 ↗

(On Diff #62370)

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 ↗

(On Diff #62370)

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

[grimar]

ELF/Config.h

40 ↗

(On Diff #62370)

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

628 ↗

(On Diff #62370)

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

628 ↗

(On Diff #62370)

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

628 ↗

(On Diff #62370)

ok

[grimar]

• Addressed review comments.

ELF/SymbolTable.cpp

565–566 ↗

(On Diff #62370)

Done.

[grimar]

• minor changes.

[grimar]

• Restored testcase removed by mistake previously.

[ruiu]

ELF/SymbolTable.cpp

581 ↗

(On Diff #62494)

Define hasWildcard(StringRef S) and use early continue.

if (hasWildcard(Name))
  continue;

601 ↗

(On Diff #62494)

Early continue.

602–603 ↗

(On Diff #62494)

for (SymbolBody *B : findAll(Name))

[grimar]

• Addressed review comments.

ELF/SymbolTable.cpp

581 ↗

(On Diff #62494)

Done.

601 ↗

(On Diff #62494)

Done.

602–603 ↗

(On Diff #62494)

Done.

[ruiu]

LGTM with a few nits.

ELF/SymbolTable.cpp

599 ↗

(On Diff #62663)

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.

603 ↗

(On Diff #62663)

I >= 0

[grimar]

ELF/SymbolTable.cpp

603 ↗

(On Diff #62663)

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

599 ↗

(On Diff #62663)

I`ll prepare a patch.

lld/trunk/ELF/SymbolTable.cpp

template <class ELFT> SymbolBody *SymbolTable<ELFT>::find(StringRef 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) {
-  // Fast-path. Fallback to find() if Pattern doesn't contain any wildcard
-  // characters.
-  if (Pattern.find_first_of("?*") == StringRef::npos) {
-    if (SymbolBody *B = find(Pattern))
-      if (!B->isUndefined())
-        return {B};
-    return {};
-  }
-
   std::vector<SymbolBody *> Res;
   for (auto &It : Symtab) {
     StringRef Name = It.first.Val;
     SymbolBody *B = SymVector[It.second]->body();
     if (!B->isUndefined() && globMatch(Pattern, Name))
       Res.push_back(B);
   }
   return Res;

 // 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;
 }
 
+static bool hasWildcard(StringRef S) {
+  return S.find_first_of("?*") != StringRef::npos;
+}
+
 // 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))
         B->symbol()->VersionId = VER_NDX_GLOBAL;
     return;
   }
 
+  if (Config->SymbolVersions.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) {
+  // 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 (size_t I = 0, E = Config->SymbolVersions.size(); I < E; ++I) {
+    Version &V = Config->SymbolVersions[I];
     for (StringRef Name : V.Globals) {
-      std::vector<SymbolBody *> Syms = findAll(Name);
-      if (Syms.empty()) {
+      if (hasWildcard(Name))
+        continue;
+
+      SymbolBody *B = find(Name);
+      if (!B || B->isUndefined()) {
         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;
+      B->symbol()->VersionId = I + 2;
+
+  for (size_t I = Config->SymbolVersions.size() - 1; I != (size_t)-1; --I) {
+    Version &V = Config->SymbolVersions[I];
+    for (StringRef Name : V.Globals) {
+      if (!hasWildcard(Name))
+        continue;
+
+      for (SymbolBody *B : findAll(Name))
+        if (B->symbol()->VersionId == VER_NDX_GLOBAL ||
+            B->symbol()->VersionId == VER_NDX_LOCAL)
+          B->symbol()->VersionId = I + 2;
+    }
   }
 }
 
 // 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()))

lld/trunk/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