1//===- SymbolTable.cpp ----------------------------------------------------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
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
12// the symbol types.
13//
14//===----------------------------------------------------------------------===//
15
16#include "SymbolTable.h"
17#include "Config.h"
18#include "InputFiles.h"
19#include "Symbols.h"
20#include "lld/Common/Memory.h"
21#include "lld/Common/Strings.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/Demangle/Demangle.h"
24#include "llvm/Support/Parallel.h"
25
26using namespace llvm;
27using namespace llvm::object;
28using namespace llvm::ELF;
29using namespace lld;
30using namespace lld::elf;
31
32void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
33 // Redirect __real_foo to the original foo and foo to the original __wrap_foo.
34 auto lookup = [&](StringRef name) -> Symbol *& {
35 CachedHashStringRef key(name);
36 return getShard(key).map[key];
37 };
38 lookup(real->getName()) = sym;
39 lookup(sym->getName()) = wrap;
40
41 // Propagate symbol usage information to the redirected symbols.
42 if (sym->isUsedInRegularObj)
43 wrap->isUsedInRegularObj = true;
44 if (real->isUsedInRegularObj)
45 sym->isUsedInRegularObj = true;
46 else if (!sym->isDefined())
47 // Now that all references to sym have been redirected to wrap, if there are
48 // no references to real (which has been redirected to sym), we only need to
49 // keep sym if it was defined, otherwise it's unused and can be dropped.
50 sym->isUsedInRegularObj = false;
51
52 if (ctx.hasDynDbg) {
53 if (sym->isDynDbgRef)
54 wrap->isDynDbgRef = true;
55 if (real->isDynDbgRef)
56 sym->isDynDbgRef = true;
57 else if (!sym->isDefined())
58 sym->isDynDbgRef = false;
59 }
60
61 // Now renaming is complete, and no one refers to real. We drop real from
62 // .symtab and .dynsym. If real is undefined, it is important that we don't
63 // leave it in .dynsym, because otherwise it might lead to an undefined symbol
64 // error in a subsequent link. If real is defined, we could emit real as an
65 // alias for sym, but that could degrade the user experience of some tools
66 // that can print out only one symbol for each location: sym is a preferred
67 // name than real, but they might print out real instead.
68 memcpy(dest: static_cast<void *>(real), src: sym, n: sizeof(SymbolUnion));
69 real->isUsedInRegularObj = false;
70}
71
72// Find an existing symbol or create a new one.
73Symbol *SymbolTable::insert(StringRef name) {
74 // <name>@@<version> means the symbol is the default version. In that
75 // case <name>@@<version> will be used to resolve references to <name>.
76 //
77 // Since this is a hot path, the following string search code is
78 // optimized for speed. StringRef::find(char) is much faster than
79 // StringRef::find(StringRef).
80 StringRef stem = name;
81 size_t pos = name.find(C: '@');
82 if (pos != StringRef::npos && pos + 1 < name.size() && name[pos + 1] == '@')
83 stem = name.take_front(N: pos);
84
85 Symbol *sym = insert(sym: intern(name: CachedHashStringRef(stem)));
86 if (pos != StringRef::npos) {
87 if (stem.size() != name.size())
88 sym->setName(name);
89 sym->hasVersionSuffix = true;
90 }
91 return sym;
92}
93
94Symbol *SymbolTable::intern(CachedHashStringRef name) {
95 Shard &shard = getShard(key: name);
96 auto l = shard.getLock(concurrent);
97 Symbol *&sym = shard.map[name];
98 if (!sym) {
99 // The storage is value-initialized, so the Symbol fields are zero. Set the
100 // ones that need a non-zero value.
101 sym = reinterpret_cast<Symbol *>(makeThreadLocal<SymbolUnion>());
102 sym->setName(name.val());
103 sym->versionId = VER_NDX_GLOBAL;
104 }
105 return sym;
106}
107
108// This variant of addSymbol is used by BinaryFile::parse to check duplicate
109// symbol errors.
110Symbol *SymbolTable::addAndCheckDuplicate(const Defined &newSym) {
111 Symbol *sym = insert(name: newSym.getName());
112 if (sym->isDefined())
113 sym->checkDuplicate(ctx, other: newSym);
114 sym->resolve(ctx, other: newSym);
115 sym->isUsedInRegularObj = true;
116 return sym;
117}
118
119Symbol *SymbolTable::find(StringRef name) {
120 assert(!concurrent && "find() must not run while workers intern symbols");
121 CachedHashStringRef key(name);
122 Symbol *sym = getShard(key).map.lookup(Val: key);
123 return sym && sym->inserted ? sym : nullptr;
124}
125
126// A version script/dynamic list is only meaningful for a Defined symbol.
127// A CommonSymbol will be converted to a Defined in replaceCommonSymbols().
128// A lazy symbol may be made Defined if an LTO libcall extracts it.
129static bool canBeVersioned(const Symbol &sym) {
130 return sym.isDefined() || sym.isCommon() || sym.isLazy();
131}
132
133static std::string demangleForVersion(StringRef name) {
134 auto [base, ver] = name.split(Separator: '@');
135 std::string s = demangle(MangledName: base);
136 if (!ver.empty() && !ver.starts_with(Prefix: '@'))
137 s += ("@" + ver).str();
138 return s;
139}
140
141// Map from demangled name to symbols, for exact lookups in extern "C++" blocks.
142StringMap<SmallVector<Symbol *, 0>> &SymbolTable::getDemangledSyms() {
143 if (!demangledSyms) {
144 demangledSyms.emplace();
145 for (Symbol *sym : symVector)
146 if (canBeVersioned(sym: *sym))
147 (*demangledSyms)[demangleForVersion(name: sym->getName())].push_back(Elt: sym);
148 }
149 return *demangledSyms;
150}
151
152SmallVector<Symbol *, 0> SymbolTable::findByVersion(SymbolVersion ver) {
153 if (ver.isExternCpp)
154 return getDemangledSyms().lookup(Key: ver.name);
155 if (Symbol *sym = find(name: ver.name))
156 if (canBeVersioned(sym: *sym))
157 return {sym};
158 return {};
159}
160
161// Set symbol versions to symbols. This function handles patterns containing no
162// wildcard characters. Return false if no symbol definition matches ver.
163bool SymbolTable::assignExactVersion(SymbolVersion ver, uint16_t versionId) {
164 // Get a list of symbols which we need to assign the version to.
165 SmallVector<Symbol *, 0> syms = findByVersion(ver);
166
167 auto getName = [&ctx = ctx](uint16_t ver) -> std::string {
168 if (ver == VER_NDX_LOCAL)
169 return "VER_NDX_LOCAL";
170 if (ver == VER_NDX_GLOBAL)
171 return "VER_NDX_GLOBAL";
172 return ("version '" + ctx.arg.versionDefinitions[ver].name + "'").str();
173 };
174
175 // Assign the version.
176 for (Symbol *sym : syms) {
177 // Skip symbols containing version info because symbol versions specified
178 // by symbol names take precedence over version scripts. See
179 // parseSymbolVersion(ctx).
180 if (sym->hasVersionSuffix)
181 continue;
182
183 // If the version has not been assigned, assign versionId to the symbol.
184 if (!sym->versionScriptAssigned) {
185 sym->versionScriptAssigned = true;
186 sym->versionId = versionId;
187 }
188 if (sym->versionId == versionId)
189 continue;
190
191 Warn(ctx) << "attempt to reassign symbol '" << ver.name << "' of "
192 << getName(sym->versionId) << " to " << getName(versionId);
193 }
194 return !syms.empty();
195}
196
197namespace {
198struct WildcardPattern {
199 SingleStringMatcher matcher;
200 bool isExternCpp;
201 uint16_t versionId;
202 WildcardPattern(const SymbolVersion &ver, uint16_t versionId)
203 : matcher(ver.name), isExternCpp(ver.isExternCpp), versionId(versionId) {}
204};
205} // namespace
206
207// This function processes version scripts by updating the versionId
208// member of symbols.
209// If there's only one anonymous version definition in a version
210// script file, the script does not actually define any symbol version,
211// but just specifies symbols visibilities.
212void SymbolTable::scanVersionScript() {
213 SmallString<128> buf;
214 // First, we assign versions to exact matching symbols,
215 // i.e. version definitions not containing any glob meta-characters.
216 for (VersionDefinition &v : ctx.arg.versionDefinitions) {
217 auto assignExact = [&](SymbolVersion pat, uint16_t id, StringRef ver) {
218 bool found = assignExactVersion(ver: pat, versionId: id);
219 // A definition foo@v1 is keyed by "foo@v1"; look it up so that the
220 // pattern is not reported as undefined. Its version is governed by
221 // parseSymbolVersion instead.
222 buf.clear();
223 found |= !findByVersion(ver: {.name: (pat.name + "@" + v.name).toStringRef(Out&: buf),
224 .isExternCpp: pat.isExternCpp, /*hasWildCard=*/.hasWildcard: false})
225 .empty();
226 if (!found && !ctx.arg.undefinedVersion)
227 Err(ctx) << "version script assignment of '" << ver << "' to symbol '"
228 << pat.name << "' failed: symbol not defined";
229 };
230 for (SymbolVersion &pat : v.nonLocalPatterns)
231 if (!pat.hasWildcard)
232 assignExact(pat, v.id, v.name);
233 for (SymbolVersion pat : v.localPatterns)
234 if (!pat.hasWildcard)
235 assignExact(pat, VER_NDX_LOCAL, "local");
236 }
237
238 // Next, collect wildcards in precedence order, where "*" patterns have the
239 // lowest precedence in GNU ld. Because the last match takes precedence over
240 // previous matches, we iterate over the definitions in the reverse order.
241 SmallVector<WildcardPattern, 0> pats, asterisks;
242 bool globalAsteriskFound = false;
243 bool localAsteriskFound = false;
244 bool asteriskReported = false;
245 for (VersionDefinition &v : llvm::reverse(C&: ctx.arg.versionDefinitions)) {
246 for (bool isLocal : {false, true}) {
247 uint16_t id = isLocal ? VER_NDX_LOCAL : v.id;
248 for (SymbolVersion &pat :
249 isLocal ? v.localPatterns : v.nonLocalPatterns) {
250 if (!pat.hasWildcard)
251 continue;
252 if (pat.name != "*") {
253 pats.emplace_back(Args&: pat, Args&: id);
254 continue;
255 }
256 if (!asteriskReported) {
257 if ((isLocal && globalAsteriskFound) ||
258 (!isLocal && localAsteriskFound)) {
259 Warn(ctx)
260 << "wildcard pattern '*' is used for both 'local' and 'global' "
261 "scopes in version script";
262 asteriskReported = true;
263 } else if (!isLocal && globalAsteriskFound) {
264 Warn(ctx) << "wildcard pattern '*' is used for multiple version "
265 "definitions in version script";
266 asteriskReported = true;
267 } else {
268 localAsteriskFound = isLocal;
269 globalAsteriskFound = !isLocal;
270 }
271 }
272 asterisks.emplace_back(Args&: pat, Args&: id);
273 }
274 }
275 }
276 pats.append(RHS: asterisks);
277
278 auto findFirstMatch = [&](ArrayRef<WildcardPattern> pats,
279 StringRef name) -> const WildcardPattern * {
280 std::optional<std::string> demangled;
281 for (auto &pat : pats) {
282 if (pat.isExternCpp && !demangled)
283 demangled = demangleForVersion(name);
284 if (pat.matcher.match(s: pat.isExternCpp ? StringRef(*demangled) : name))
285 return &pat;
286 }
287 return nullptr;
288 };
289
290 // Exact matching takes precedence over wildcard matching, so a wildcard
291 // assigns a version only if none has been assigned.
292 if (!pats.empty()) {
293 parallelForEach(R&: symVector, Fn: [&](Symbol *sym) {
294 if (sym->versionScriptAssigned || sym->hasVersionSuffix ||
295 !canBeVersioned(sym: *sym))
296 return;
297 if (auto *pat = findFirstMatch(pats, sym->getName()))
298 sym->versionId = pat->versionId;
299 });
300 }
301
302 // Handle --dynamic-list. If a specified symbol is also matched by local: in a
303 // version script, the version script takes precedence.
304 SmallVector<Symbol *, 0> syms;
305 pats.clear();
306 for (SymbolVersion &ver : ctx.arg.dynamicList) {
307 if (ver.hasWildcard) {
308 pats.emplace_back(Args&: ver, Args: 0);
309 } else {
310 for (Symbol *sym : findByVersion(ver))
311 sym->isExported = sym->inDynamicList = true;
312 }
313 }
314 if (!pats.empty()) {
315 parallelForEach(R&: symVector, Fn: [&](Symbol *sym) {
316 if (!canBeVersioned(sym: *sym))
317 return;
318 StringRef name = sym->getName();
319 if (findFirstMatch(pats, name))
320 sym->isExported = sym->inDynamicList = true;
321 });
322 }
323}
324
325Symbol *SymbolTable::addUnusedUndefined(StringRef name, uint8_t binding) {
326 return addSymbol(newSym: Undefined{ctx.internalFile, name, binding, STV_DEFAULT, 0});
327}
328