[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

11–12

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.

20

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

20

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

20

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

20

ok

[grimar]

• Addressed review comments.

ELF/SymbolTable.cpp

11–12

Done.

[grimar]

• minor changes.

[grimar]

• Restored testcase removed by mistake previously.

[ruiu]

ELF/SymbolTable.cpp

581

Define hasWildcard(StringRef S) and use early continue.

if (hasWildcard(Name))
  continue;

601

Early continue.

602–603

for (SymbolBody *B : findAll(Name))

[grimar]

• Addressed review comments.

ELF/SymbolTable.cpp

581

Done.

601

Done.

602–603

Done.

[ruiu]

LGTM with a few nits.

ELF/SymbolTable.cpp

13

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.

17

I >= 0

[grimar]

ELF/SymbolTable.cpp

17

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

13

I`ll prepare a patch.

ELF/SymbolTable.cpp

 //===- SymbolTable.cpp ----------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Symbol table is a bag of all known symbols. We put all symbols of
 // all input files to the symbol table. The symbol table is basically
 // 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 "Strings.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) {
   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;
template <class ELFT> void SymbolTable<ELFT>::scanVersionScript() {
   // 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) {
-    for (StringRef Name : V.Globals) {
-      std::vector<SymbolBody *> Syms = findAll(Name);
-      if (Syms.empty()) {
+  // 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)
+      if (Name.find_first_of("?*") == StringRef::npos) {
+        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;
+        B->symbol()->VersionId = I + 2;
       }
-    }
-    ++I;
+
+  for (size_t I = Config->SymbolVersions.size() - 1; I != (size_t)-1; --I) {
+    Version &V = Config->SymbolVersions[I];
+    for (StringRef Name : V.Globals)
+      if (Name.find_first_of("?*") != StringRef::npos) {
+        std::vector<SymbolBody *> Syms = findAll(Name);
+        for (SymbolBody *B : Syms)
+          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()))