From 663b8c2769c349094b2b083d10edc489671b8209 Mon Sep 17 00:00:00 2001 From: Rui Ueyama Date: Sun, 17 Jul 2016 17:23:17 +0000 Subject: [PATCH] Handle versioned symbols efficiently. Versions can be assigned to symbols in two different ways. One is the usual version scripts, and the other is special symbol suffix '@'. If a symbol contains '@', the string after that is considered to specify a version name. Previously, we look for '@' for all symbols. Anything that works on every symbol can be expensive because the linker has to handle a lot of symbols. The search for '@' was not an exception. In this patch, I made two optimizations. The first optimization is to handle '@' only when at least one version is defined. If no versions are defined, no versions can be assigned to any symbols, so it's waste of time to search for '@'. The second optimization is to scan only suffixes of symbol names instead of entire symbol names. Symbol names can be very long, but symbol versions are usually short, so scanning entire symbol names is waste of time, too. There are some error cases which we no longer be able to detect with this patch. I don't think it's a major drawback because they are minor errors. Speed is more important. This change improves LLD with debug info self-link time from 6.6993 seconds to 6.3426 seconds (or -5.3%). Differential Revision: https://reviews.llvm.org/D22433 llvm-svn: 275711 --- lld/ELF/Config.h | 1 - lld/ELF/Driver.cpp | 5 +- lld/ELF/SymbolTable.cpp | 115 +++++++++++------ lld/ELF/SymbolTable.h | 1 + lld/ELF/Symbols.cpp | 10 +- lld/ELF/Symbols.h | 8 +- lld/test/ELF/verdef-defaultver.s | 4 - lld/test/ELF/verdef-executable.s | 269 --------------------------------------- 8 files changed, 90 insertions(+), 323 deletions(-) delete mode 100644 lld/test/ELF/verdef-executable.s diff --git a/lld/ELF/Config.h b/lld/ELF/Config.h index a43ce33..32c51f2 100644 --- a/lld/ELF/Config.h +++ b/lld/ELF/Config.h @@ -90,7 +90,6 @@ struct Configuration { bool FatalWarnings; bool GcSections; bool GnuHash = false; - bool HasVersionScript = false; bool ICF; bool Mips64EL = false; bool NoGnuUnique; diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp index 630d8d7..fa3d628 100644 --- a/lld/ELF/Driver.cpp +++ b/lld/ELF/Driver.cpp @@ -443,11 +443,9 @@ void LinkerDriver::readConfigs(opt::InputArgList &Args) { for (auto *Arg : Args.filtered(OPT_export_dynamic_symbol)) Config->DynamicList.push_back(Arg->getValue()); - if (auto *Arg = Args.getLastArg(OPT_version_script)) { - Config->HasVersionScript = true; + if (auto *Arg = Args.getLastArg(OPT_version_script)) if (Optional Buffer = readFile(Arg->getValue())) parseVersionScript(*Buffer); - } for (auto *Arg : Args.filtered(OPT_trace_symbol)) Config->TraceSymbol.insert(Arg->getValue()); @@ -557,6 +555,7 @@ template void LinkerDriver::link(opt::InputArgList &Args) { Symtab.scanShlibUndefined(); Symtab.scanDynamicList(); Symtab.scanVersionScript(); + Symtab.scanSymbolVersions(); Symtab.traceDefined(); Symtab.addCombinedLtoObject(); diff --git a/lld/ELF/SymbolTable.cpp b/lld/ELF/SymbolTable.cpp index 4fb2b87..12e7d9a 100644 --- a/lld/ELF/SymbolTable.cpp +++ b/lld/ELF/SymbolTable.cpp @@ -165,39 +165,6 @@ static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) { return std::min(VA, VB); } -// A symbol version may be included in a symbol name as a suffix after '@'. -// This function parses that part and returns a version ID number. -static uint16_t getVersionId(Symbol *Sym, StringRef Name) { - size_t VersionBegin = Name.find('@'); - if (VersionBegin == StringRef::npos) - return Config->DefaultSymbolVersion; - - // If symbol name contains '@' or '@@' we can assign its version id right - // here. '@@' means the default version. It is usually the most recent one. - // VERSYM_HIDDEN flag should be set for all non-default versions. - StringRef Version = Name.drop_front(VersionBegin + 1); - bool Default = Version.startswith("@"); - if (Default) - Version = Version.drop_front(); - - for (VersionDefinition &V : Config->VersionDefinitions) - if (V.Name == Version) - return Default ? V.Id : (V.Id | VERSYM_HIDDEN); - - - // If we are not building shared and version script - // is not specified, then it is not a error, it is - // in common not to use script for linking executables. - // In this case we just create new version. - if (!Config->Shared && !Config->HasVersionScript) { - size_t Id = defineSymbolVersion(Version); - return Default ? Id : (Id | VERSYM_HIDDEN); - } - - error("symbol " + Name + " has undefined version " + Version); - return 0; -} - // Find an existing symbol or create and insert a new one. template std::pair SymbolTable::insert(StringRef Name) { @@ -210,9 +177,7 @@ std::pair SymbolTable::insert(StringRef Name) { Sym->Visibility = STV_DEFAULT; Sym->IsUsedInRegularObj = false; Sym->ExportDynamic = false; - Sym->VersionId = getVersionId(Sym, Name); - Sym->VersionedName = - Sym->VersionId != VER_NDX_LOCAL && Sym->VersionId != VER_NDX_GLOBAL; + Sym->VersionId = Config->DefaultSymbolVersion; SymVector.push_back(Sym); } else { Sym = SymVector[P.first->second]; @@ -646,6 +611,84 @@ template void SymbolTable::scanVersionScript() { } } +// Returns the size of the longest version name. +static int getMaxVersionLen() { + size_t Len = 0; + for (VersionDefinition &V : Config->VersionDefinitions) + Len = std::max(Len, V.Name.size()); + return Len; +} + +// Parses a symbol name in the form of @ or @@. +static std::pair +getSymbolVersion(SymbolBody *B, int MaxVersionLen) { + StringRef S = B->getName(); + + // MaxVersionLen was passed so that we don't need to scan + // all characters in a symbol name. It is effective because + // versions are usually short and symbol names can be very long. + size_t Pos = S.find('@', std::max(0, int(S.size()) - MaxVersionLen - 2)); + if (Pos == 0 || Pos == StringRef::npos) + return {"", 0}; + + StringRef Name = S.substr(0, Pos); + StringRef Verstr = S.substr(Pos + 1); + if (Verstr.empty()) + return {"", 0}; + + // '@@' in a symbol name means the default version. + // It is usually the most recent one. + bool IsDefault = (Verstr[0] == '@'); + if (IsDefault) + Verstr = Verstr.substr(1); + + for (VersionDefinition &V : Config->VersionDefinitions) { + if (V.Name == Verstr) + return {Name, IsDefault ? V.Id : (V.Id | VERSYM_HIDDEN)}; + } + + // It is an error if the specified version was not defined. + error("symbol " + S + " has undefined version " + Verstr); + return {"", 0}; +} + +// Versions are usually assigned to symbols using version scripts, +// but there's another way to assign versions to symbols. +// If a symbol name contains '@', the string after it is not +// actually a part of the symbol name but specifies a version. +// This function takes care of it. +template void SymbolTable::scanSymbolVersions() { + if (Config->VersionDefinitions.empty()) + return; + + int MaxVersionLen = getMaxVersionLen(); + + // Unfortunately there's no way other than iterating over all + // symbols to look for '@' characters in symbol names. + // So this is inherently slow. A good news is that we do this + // only when versions have been defined. + for (Symbol *Sym : SymVector) { + // Symbol versions for exported symbols are by nature + // only for defined global symbols. + SymbolBody *B = Sym->body(); + if (!B->isDefined()) + continue; + uint8_t Visibility = B->getVisibility(); + if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED) + continue; + + // Look for '@' in the symbol name. + StringRef Name; + uint16_t Version; + std::tie(Name, Version) = getSymbolVersion(B, MaxVersionLen); + if (Name.empty()) + continue; + + B->setName(Name); + Sym->VersionId = Version; + } +} + // Print the module names which define the notified // symbols provided through -y or --trace-symbol option. template void SymbolTable::traceDefined() { diff --git a/lld/ELF/SymbolTable.h b/lld/ELF/SymbolTable.h index 9e26ffe..61fd50f 100644 --- a/lld/ELF/SymbolTable.h +++ b/lld/ELF/SymbolTable.h @@ -82,6 +82,7 @@ public: void scanShlibUndefined(); void scanDynamicList(); void scanVersionScript(); + void scanSymbolVersions(); void traceDefined(); SymbolBody *find(StringRef Name); diff --git a/lld/ELF/Symbols.cpp b/lld/ELF/Symbols.cpp index 7c9c748..39942b5 100644 --- a/lld/ELF/Symbols.cpp +++ b/lld/ELF/Symbols.cpp @@ -98,10 +98,12 @@ SymbolBody::SymbolBody(Kind K, StringRef Name, uint8_t StOther, uint8_t Type) StringRef SymbolBody::getName() const { assert(!isLocal()); - StringRef S = StringRef(Name.S, Name.Len); - if (!symbol()->VersionedName) - return S; - return S.substr(0, S.find('@')); + return StringRef(Name.S, Name.Len); +} + +void SymbolBody::setName(StringRef S) { + Name.S = S.data(); + Name.Len = S.size(); } // Returns true if a symbol can be replaced at load-time by a symbol diff --git a/lld/ELF/Symbols.h b/lld/ELF/Symbols.h index f4b810d..b6d9e38 100644 --- a/lld/ELF/Symbols.h +++ b/lld/ELF/Symbols.h @@ -70,8 +70,9 @@ public: bool isLocal() const { return IsLocal; } bool isPreemptible() const; - // Returns the symbol name. StringRef getName() const; + void setName(StringRef S); + uint32_t getNameOffset() const { assert(isLocal()); return NameOffset; @@ -419,11 +420,6 @@ struct Symbol { // --export-dynamic, and by dynamic lists. unsigned ExportDynamic : 1; - // If this flag is true then symbol name also contains version name. Such - // name can have single or double symbol @. Double means that version is - // used as default. Single signals about depricated symbol version. - unsigned VersionedName : 1; - bool includeInDynsym() const; bool isWeak() const { return Binding == llvm::ELF::STB_WEAK; } diff --git a/lld/test/ELF/verdef-defaultver.s b/lld/test/ELF/verdef-defaultver.s index f9524d5..4d84734 100644 --- a/lld/test/ELF/verdef-defaultver.s +++ b/lld/test/ELF/verdef-defaultver.s @@ -198,10 +198,6 @@ # EXE-NEXT: } # EXE-NEXT: } -# RUN: not ld.lld -shared %t1 -o %terr.so 2>&1 | \ -# RUN: FileCheck -check-prefix=ERR1 %s -# ERR1: symbol b@@LIBSAMPLE_2.0 has undefined version LIBSAMPLE_2.0 - .globl _start _start: callq a diff --git a/lld/test/ELF/verdef-executable.s b/lld/test/ELF/verdef-executable.s deleted file mode 100644 index 9af98da..0000000 --- a/lld/test/ELF/verdef-executable.s +++ /dev/null @@ -1,269 +0,0 @@ -# REQUIRES: x86 - -# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1 -# RUN: ld.lld %t1 -o %t -# RUN: llvm-readobj -t -V -dyn-symbols %t | FileCheck --check-prefix=EXE %s - -# EXE: Symbols [ -# EXE-NEXT: Symbol { -# EXE-NEXT: Name: -# EXE-NEXT: Value: 0x0 -# EXE-NEXT: Size: 0 -# EXE-NEXT: Binding: Local -# EXE-NEXT: Type: None (0x0) -# EXE-NEXT: Other: 0 -# EXE-NEXT: Section: Undefined (0x0) -# EXE-NEXT: } -# EXE-NEXT: Symbol { -# EXE-NEXT: Name: _start -# EXE-NEXT: Value: 0x11004 -# EXE-NEXT: Size: 0 -# EXE-NEXT: Binding: Global -# EXE-NEXT: Type: None -# EXE-NEXT: Other: 0 -# EXE-NEXT: Section: .text -# EXE-NEXT: } -# EXE-NEXT: Symbol { -# EXE-NEXT: Name: a -# EXE-NEXT: Value: 0x11000 -# EXE-NEXT: Size: 0 -# EXE-NEXT: Binding: Global -# EXE-NEXT: Type: Function -# EXE-NEXT: Other: 0 -# EXE-NEXT: Section: .text -# EXE-NEXT: } -# EXE-NEXT: Symbol { -# EXE-NEXT: Name: b -# EXE-NEXT: Value: 0x11002 -# EXE-NEXT: Size: 0 -# EXE-NEXT: Binding: Global -# EXE-NEXT: Type: Function -# EXE-NEXT: Other: 0 -# EXE-NEXT: Section: .text -# EXE-NEXT: } -# EXE-NEXT: Symbol { -# EXE-NEXT: Name: b -# EXE-NEXT: Value: 0x11001 -# EXE-NEXT: Size: 0 -# EXE-NEXT: Binding: Global -# EXE-NEXT: Type: Function -# EXE-NEXT: Other: 0 -# EXE-NEXT: Section: .text -# EXE-NEXT: } -# EXE-NEXT: Symbol { -# EXE-NEXT: Name: b_1 -# EXE-NEXT: Value: 0x11001 -# EXE-NEXT: Size: 0 -# EXE-NEXT: Binding: Global -# EXE-NEXT: Type: Function -# EXE-NEXT: Other: 0 -# EXE-NEXT: Section: .text -# EXE-NEXT: } -# EXE-NEXT: Symbol { -# EXE-NEXT: Name: b_2 -# EXE-NEXT: Value: 0x11002 -# EXE-NEXT: Size: 0 -# EXE-NEXT: Binding: Global -# EXE-NEXT: Type: Function -# EXE-NEXT: Other: 0 -# EXE-NEXT: Section: .text -# EXE-NEXT: } -# EXE-NEXT: Symbol { -# EXE-NEXT: Name: c -# EXE-NEXT: Value: 0x11003 -# EXE-NEXT: Size: 0 -# EXE-NEXT: Binding: Global -# EXE-NEXT: Type: Function -# EXE-NEXT: Other: 0 -# EXE-NEXT: Section: .text -# EXE-NEXT: } -# EXE-NEXT: ] -# EXE-NEXT: DynamicSymbols [ -# EXE-NEXT: ] -# EXE-NEXT: Version symbols { -# EXE-NEXT: } -# EXE-NEXT: SHT_GNU_verdef { -# EXE-NEXT: } -# EXE-NEXT: SHT_GNU_verneed { -# EXE-NEXT: } - -# RUN: ld.lld -pie --export-dynamic %t1 -o %t2 -# RUN: llvm-readobj -t -V -dyn-symbols %t2 | \ -# RUN: FileCheck --check-prefix=EXEDYN %s - -# EXEDYN: DynamicSymbols [ -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Name: @ -# EXEDYN-NEXT: Value: 0x0 -# EXEDYN-NEXT: Size: 0 -# EXEDYN-NEXT: Binding: Local -# EXEDYN-NEXT: Type: None -# EXEDYN-NEXT: Other: 0 -# EXEDYN-NEXT: Section: Undefined -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Name: _start@ -# EXEDYN-NEXT: Value: 0x1004 -# EXEDYN-NEXT: Size: 0 -# EXEDYN-NEXT: Binding: Global -# EXEDYN-NEXT: Type: None -# EXEDYN-NEXT: Other: 0 -# EXEDYN-NEXT: Section: .text -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Name: a@ -# EXEDYN-NEXT: Value: 0x1000 -# EXEDYN-NEXT: Size: 0 -# EXEDYN-NEXT: Binding: Global -# EXEDYN-NEXT: Type: Function -# EXEDYN-NEXT: Other: 0 -# EXEDYN-NEXT: Section: .text -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Name: b@@LIBSAMPLE_2.0 -# EXEDYN-NEXT: Value: 0x1002 -# EXEDYN-NEXT: Size: 0 -# EXEDYN-NEXT: Binding: Global -# EXEDYN-NEXT: Type: Function -# EXEDYN-NEXT: Other: 0 -# EXEDYN-NEXT: Section: .text -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Name: b@LIBSAMPLE_1.0 -# EXEDYN-NEXT: Value: 0x1001 -# EXEDYN-NEXT: Size: 0 -# EXEDYN-NEXT: Binding: Global -# EXEDYN-NEXT: Type: Function -# EXEDYN-NEXT: Other: 0 -# EXEDYN-NEXT: Section: .text -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Name: b_1@ -# EXEDYN-NEXT: Value: 0x1001 -# EXEDYN-NEXT: Size: 0 -# EXEDYN-NEXT: Binding: Global -# EXEDYN-NEXT: Type: Function -# EXEDYN-NEXT: Other: 0 -# EXEDYN-NEXT: Section: .text -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Name: b_2@ -# EXEDYN-NEXT: Value: 0x1002 -# EXEDYN-NEXT: Size: 0 -# EXEDYN-NEXT: Binding: Global -# EXEDYN-NEXT: Type: Function -# EXEDYN-NEXT: Other: 0 -# EXEDYN-NEXT: Section: .text -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Name: c@ -# EXEDYN-NEXT: Value: 0x1003 -# EXEDYN-NEXT: Size: 0 -# EXEDYN-NEXT: Binding: Global -# EXEDYN-NEXT: Type: Function -# EXEDYN-NEXT: Other: 0 -# EXEDYN-NEXT: Section: .text -# EXEDYN-NEXT: } -# EXEDYN-NEXT: ] -# EXEDYN-NEXT: Version symbols { -# EXEDYN-NEXT: Section Name: .gnu.version -# EXEDYN-NEXT: Address: 0x288 -# EXEDYN-NEXT: Offset: 0x288 -# EXEDYN-NEXT: Link: 1 -# EXEDYN-NEXT: Symbols [ -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Version: 0 -# EXEDYN-NEXT: Name: @ -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Version: 1 -# EXEDYN-NEXT: Name: _start@ -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Version: 1 -# EXEDYN-NEXT: Name: a@ -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Version: 2 -# EXEDYN-NEXT: Name: b@@LIBSAMPLE_2.0 -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Version: 3 -# EXEDYN-NEXT: Name: b@LIBSAMPLE_1.0 -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Version: 1 -# EXEDYN-NEXT: Name: b_1@ -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Version: 1 -# EXEDYN-NEXT: Name: b_2@ -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Symbol { -# EXEDYN-NEXT: Version: 1 -# EXEDYN-NEXT: Name: c@ -# EXEDYN-NEXT: } -# EXEDYN-NEXT: ] -# EXEDYN-NEXT: } -# EXEDYN-NEXT: SHT_GNU_verdef { -# EXEDYN-NEXT: Definition { -# EXEDYN-NEXT: Version: 1 -# EXEDYN-NEXT: Flags: Base -# EXEDYN-NEXT: Index: 1 -# EXEDYN-NEXT: Hash: -# EXEDYN-NEXT: Name: -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Definition { -# EXEDYN-NEXT: Version: 1 -# EXEDYN-NEXT: Flags: 0x0 -# EXEDYN-NEXT: Index: 2 -# EXEDYN-NEXT: Hash: 98456416 -# EXEDYN-NEXT: Name: LIBSAMPLE_2.0 -# EXEDYN-NEXT: } -# EXEDYN-NEXT: Definition { -# EXEDYN-NEXT: Version: 1 -# EXEDYN-NEXT: Flags: 0x0 -# EXEDYN-NEXT: Index: 3 -# EXEDYN-NEXT: Hash: 98457184 -# EXEDYN-NEXT: Name: LIBSAMPLE_1.0 -# EXEDYN-NEXT: } -# EXEDYN-NEXT: } -# EXEDYN-NEXT: SHT_GNU_verneed { -# EXEDYN-NEXT: } - -## Check when linking executable that error produced if version script -## was specified and there are symbols with version in name that -## is absent in script. -# RUN: echo "VERSION { \ -# RUN: global: foo; \ -# RUN: local: *; }; " > %t.script -# RUN: not ld.lld --version-script %t.script %t1 -o %t3 2>&1 | \ -# RUN: FileCheck -check-prefix=ERR %s -# ERR: symbol b@LIBSAMPLE_1.0 has undefined version LIBSAMPLE_1.0 - -b@LIBSAMPLE_1.0 = b_1 -b@@LIBSAMPLE_2.0 = b_2 - -.globl a -.type a,@function -a: -retq - -.globl b_1 -.type b_1,@function -b_1: -retq - -.globl b_2 -.type b_2,@function -b_2: -retq - -.globl c -.type c,@function -c: -retq - -.globl _start -_start: - nop -- 2.7.4