1 //===- SymbolTable.cpp ----------------------------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // Symbol table is a bag of all known symbols. We put all symbols of
10 // all input files to the symbol table. The symbol table is basically
11 // a hash table with the logic to resolve symbol name conflicts using
14 //===----------------------------------------------------------------------===//
16 #include "SymbolTable.h"
18 #include "LinkerScript.h"
20 #include "SyntheticSections.h"
21 #include "lld/Common/ErrorHandler.h"
22 #include "lld/Common/Memory.h"
23 #include "lld/Common/Strings.h"
24 #include "llvm/ADT/STLExtras.h"
27 using namespace llvm::object;
28 using namespace llvm::ELF;
34 void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
35 // Swap symbols as instructed by -wrap.
36 int &idx1 = symMap[CachedHashStringRef(sym->getName())];
37 int &idx2 = symMap[CachedHashStringRef(real->getName())];
38 int &idx3 = symMap[CachedHashStringRef(wrap->getName())];
43 // Now renaming is complete. No one refers Real symbol. We could leave
44 // Real as-is, but if Real is written to the symbol table, that may
45 // contain irrelevant values. So, we copy all values from Sym to Real.
46 StringRef s = real->getName();
47 memcpy(real, sym, sizeof(SymbolUnion));
51 // Find an existing symbol or create a new one.
52 Symbol *SymbolTable::insert(StringRef name) {
53 // <name>@@<version> means the symbol is the default version. In that
54 // case <name>@@<version> will be used to resolve references to <name>.
56 // Since this is a hot path, the following string search code is
57 // optimized for speed. StringRef::find(char) is much faster than
58 // StringRef::find(StringRef).
59 size_t pos = name.find('@');
60 if (pos != StringRef::npos && pos + 1 < name.size() && name[pos + 1] == '@')
61 name = name.take_front(pos);
63 auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
64 int &symIndex = p.first->second;
65 bool isNew = p.second;
68 return symVector[symIndex];
70 Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
71 symVector.push_back(sym);
73 // *sym was not initialized by a constructor. Fields that may get referenced
74 // when it is a placeholder must be initialized here.
76 sym->symbolKind = Symbol::PlaceholderKind;
77 sym->versionId = VER_NDX_GLOBAL;
78 sym->visibility = STV_DEFAULT;
79 sym->isUsedInRegularObj = false;
80 sym->exportDynamic = false;
81 sym->inDynamicList = false;
82 sym->canInline = true;
83 sym->referenced = false;
85 sym->scriptDefined = false;
90 Symbol *SymbolTable::addSymbol(const Symbol &newSym) {
91 Symbol *sym = symtab->insert(newSym.getName());
96 Symbol *SymbolTable::find(StringRef name) {
97 auto it = symMap.find(CachedHashStringRef(name));
98 if (it == symMap.end())
100 Symbol *sym = symVector[it->second];
101 if (sym->isPlaceholder())
106 // Initialize demangledSyms with a map from demangled symbols to symbol
107 // objects. Used to handle "extern C++" directive in version scripts.
109 // The map will contain all demangled symbols. That can be very large,
110 // and in LLD we generally want to avoid do anything for each symbol.
111 // Then, why are we doing this? Here's why.
113 // Users can use "extern C++ {}" directive to match against demangled
114 // C++ symbols. For example, you can write a pattern such as
115 // "llvm::*::foo(int, ?)". Obviously, there's no way to handle this
116 // other than trying to match a pattern against all demangled symbols.
117 // So, if "extern C++" feature is used, we need to demangle all known
119 StringMap<std::vector<Symbol *>> &SymbolTable::getDemangledSyms() {
120 if (!demangledSyms) {
121 demangledSyms.emplace();
122 for (Symbol *sym : symVector) {
123 if (!sym->isDefined() && !sym->isCommon())
125 (*demangledSyms)[demangleItanium(sym->getName())].push_back(sym);
128 return *demangledSyms;
131 std::vector<Symbol *> SymbolTable::findByVersion(SymbolVersion ver) {
133 return getDemangledSyms().lookup(ver.name);
134 if (Symbol *b = find(ver.name))
135 if (b->isDefined() || b->isCommon())
140 std::vector<Symbol *> SymbolTable::findAllByVersion(SymbolVersion ver) {
141 std::vector<Symbol *> res;
142 StringMatcher m(ver.name);
144 if (ver.isExternCpp) {
145 for (auto &p : getDemangledSyms())
146 if (m.match(p.first()))
147 res.insert(res.end(), p.second.begin(), p.second.end());
151 for (Symbol *sym : symVector)
152 if ((sym->isDefined() || sym->isCommon()) && m.match(sym->getName()))
157 // Handles -dynamic-list.
158 void SymbolTable::handleDynamicList() {
159 for (SymbolVersion &ver : config->dynamicList) {
160 std::vector<Symbol *> syms;
162 syms = findAllByVersion(ver);
164 syms = findByVersion(ver);
166 for (Symbol *sym : syms)
167 sym->inDynamicList = true;
171 // Set symbol versions to symbols. This function handles patterns
172 // containing no wildcard characters.
173 void SymbolTable::assignExactVersion(SymbolVersion ver, uint16_t versionId,
174 StringRef versionName) {
178 // Get a list of symbols which we need to assign the version to.
179 std::vector<Symbol *> syms = findByVersion(ver);
181 if (!config->undefinedVersion)
182 error("version script assignment of '" + versionName + "' to symbol '" +
183 ver.name + "' failed: symbol not defined");
187 auto getName = [](uint16_t ver) -> std::string {
188 if (ver == VER_NDX_LOCAL)
189 return "VER_NDX_LOCAL";
190 if (ver == VER_NDX_GLOBAL)
191 return "VER_NDX_GLOBAL";
192 return ("version '" + config->versionDefinitions[ver].name + "'").str();
195 // Assign the version.
196 for (Symbol *sym : syms) {
197 // Skip symbols containing version info because symbol versions
198 // specified by symbol names take precedence over version scripts.
199 // See parseSymbolVersion().
200 if (sym->getName().contains('@'))
203 // If the version has not been assigned, verdefIndex is -1. Use an arbitrary
204 // number (0) to indicate the version has been assigned.
205 if (sym->verdefIndex == UINT32_C(-1)) {
206 sym->verdefIndex = 0;
207 sym->versionId = versionId;
209 if (sym->versionId == versionId)
212 warn("attempt to reassign symbol '" + ver.name + "' of " +
213 getName(sym->versionId) + " to " + getName(versionId));
217 void SymbolTable::assignWildcardVersion(SymbolVersion ver, uint16_t versionId) {
218 // Exact matching takes precedence over fuzzy matching,
219 // so we set a version to a symbol only if no version has been assigned
220 // to the symbol. This behavior is compatible with GNU.
221 for (Symbol *sym : findAllByVersion(ver))
222 if (sym->verdefIndex == UINT32_C(-1)) {
223 sym->verdefIndex = 0;
224 sym->versionId = versionId;
228 // This function processes version scripts by updating the versionId
229 // member of symbols.
230 // If there's only one anonymous version definition in a version
231 // script file, the script does not actually define any symbol version,
232 // but just specifies symbols visibilities.
233 void SymbolTable::scanVersionScript() {
234 // First, we assign versions to exact matching symbols,
235 // i.e. version definitions not containing any glob meta-characters.
236 for (VersionDefinition &v : config->versionDefinitions)
237 for (SymbolVersion &pat : v.patterns)
238 assignExactVersion(pat, v.id, v.name);
240 // Next, assign versions to wildcards that are not "*". Note that because the
241 // last match takes precedence over previous matches, we iterate over the
242 // definitions in the reverse order.
243 for (VersionDefinition &v : llvm::reverse(config->versionDefinitions))
244 for (SymbolVersion &pat : v.patterns)
245 if (pat.hasWildcard && pat.name != "*")
246 assignWildcardVersion(pat, v.id);
248 // Then, assign versions to "*". In GNU linkers they have lower priority than
250 for (VersionDefinition &v : config->versionDefinitions)
251 for (SymbolVersion &pat : v.patterns)
252 if (pat.hasWildcard && pat.name == "*")
253 assignWildcardVersion(pat, v.id);
255 // Symbol themselves might know their versions because symbols
256 // can contain versions in the form of <name>@<version>.
257 // Let them parse and update their names to exclude version suffix.
258 for (Symbol *sym : symVector)
259 sym->parseSymbolVersion();
261 // isPreemptible is false at this point. To correctly compute the binding of a
262 // Defined (which is used by includeInDynsym()), we need to know if it is
263 // VER_NDX_LOCAL or not. Compute symbol versions before handling