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 int &idx1 = symMap[CachedHashStringRef(sym->getName())];
35 int &idx2 = symMap[CachedHashStringRef(real->getName())];
36 int &idx3 = symMap[CachedHashStringRef(wrap->getName())];
37
38 idx2 = idx1;
39 idx1 = idx3;
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 auto p = symMap.insert(KV: {CachedHashStringRef(stem), (int)symVector.size()});
86 if (!p.second) {
87 Symbol *sym = symVector[p.first->second];
88 if (stem.size() != name.size()) {
89 sym->setName(name);
90 sym->hasVersionSuffix = true;
91 }
92 return sym;
93 }
94
95 Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
96 symVector.push_back(Elt: sym);
97
98 // make<SymbolUnion>() value-initializes the storage, so the Symbol fields
99 // are zero. Set the ones that need a non-zero value.
100 sym->setName(name);
101 sym->versionId = VER_NDX_GLOBAL;
102 if (pos != StringRef::npos)
103 sym->hasVersionSuffix = true;
104 return sym;
105}
106
107// This variant of addSymbol is used by BinaryFile::parse to check duplicate
108// symbol errors.
109Symbol *SymbolTable::addAndCheckDuplicate(Ctx &ctx, const Defined &newSym) {
110 Symbol *sym = insert(name: newSym.getName());
111 if (sym->isDefined())
112 sym->checkDuplicate(ctx, other: newSym);
113 sym->resolve(ctx, other: newSym);
114 sym->isUsedInRegularObj = true;
115 return sym;
116}
117
118Symbol *SymbolTable::find(StringRef name) {
119 auto it = symMap.find(Val: CachedHashStringRef(name));
120 if (it == symMap.end())
121 return nullptr;
122 return symVector[it->second];
123}
124
125// A version script/dynamic list is only meaningful for a Defined symbol.
126// A CommonSymbol will be converted to a Defined in replaceCommonSymbols().
127// A lazy symbol may be made Defined if an LTO libcall extracts it.
128static bool canBeVersioned(const Symbol &sym) {
129 return sym.isDefined() || sym.isCommon() || sym.isLazy();
130}
131
132static std::string demangleForVersion(StringRef name) {
133 auto [base, ver] = name.split(Separator: '@');
134 std::string s = demangle(MangledName: base);
135 if (!ver.empty() && !ver.starts_with(Prefix: '@'))
136 s += ("@" + ver).str();
137 return s;
138}
139
140// Map from demangled name to symbols, for exact lookups in extern "C++" blocks.
141StringMap<SmallVector<Symbol *, 0>> &SymbolTable::getDemangledSyms() {
142 if (!demangledSyms) {
143 demangledSyms.emplace();
144 for (Symbol *sym : symVector)
145 if (canBeVersioned(sym: *sym))
146 (*demangledSyms)[demangleForVersion(name: sym->getName())].push_back(Elt: sym);
147 }
148 return *demangledSyms;
149}
150
151SmallVector<Symbol *, 0> SymbolTable::findByVersion(SymbolVersion ver) {
152 if (ver.isExternCpp)
153 return getDemangledSyms().lookup(Key: ver.name);
154 if (Symbol *sym = find(name: ver.name))
155 if (canBeVersioned(sym: *sym))
156 return {sym};
157 return {};
158}
159
160// Set symbol versions to symbols. This function handles patterns containing no
161// wildcard characters. Return false if no symbol definition matches ver.
162bool SymbolTable::assignExactVersion(SymbolVersion ver, uint16_t versionId) {
163 // Get a list of symbols which we need to assign the version to.
164 SmallVector<Symbol *, 0> syms = findByVersion(ver);
165
166 auto getName = [&ctx = ctx](uint16_t ver) -> std::string {
167 if (ver == VER_NDX_LOCAL)
168 return "VER_NDX_LOCAL";
169 if (ver == VER_NDX_GLOBAL)
170 return "VER_NDX_GLOBAL";
171 return ("version '" + ctx.arg.versionDefinitions[ver].name + "'").str();
172 };
173
174 // Assign the version.
175 for (Symbol *sym : syms) {
176 // Skip symbols containing version info because symbol versions specified
177 // by symbol names take precedence over version scripts. See
178 // parseSymbolVersion(ctx).
179 if (sym->hasVersionSuffix)
180 continue;
181
182 // If the version has not been assigned, assign versionId to the symbol.
183 if (!sym->versionScriptAssigned) {
184 sym->versionScriptAssigned = true;
185 sym->versionId = versionId;
186 }
187 if (sym->versionId == versionId)
188 continue;
189
190 Warn(ctx) << "attempt to reassign symbol '" << ver.name << "' of "
191 << getName(sym->versionId) << " to " << getName(versionId);
192 }
193 return !syms.empty();
194}
195
196namespace {
197struct WildcardPattern {
198 SingleStringMatcher matcher;
199 bool isExternCpp;
200 uint16_t versionId;
201 WildcardPattern(const SymbolVersion &ver, uint16_t versionId)
202 : matcher(ver.name), isExternCpp(ver.isExternCpp), versionId(versionId) {}
203};
204} // namespace
205
206// This function processes version scripts by updating the versionId
207// member of symbols.
208// If there's only one anonymous version definition in a version
209// script file, the script does not actually define any symbol version,
210// but just specifies symbols visibilities.
211void SymbolTable::scanVersionScript() {
212 SmallString<128> buf;
213 // First, we assign versions to exact matching symbols,
214 // i.e. version definitions not containing any glob meta-characters.
215 for (VersionDefinition &v : ctx.arg.versionDefinitions) {
216 auto assignExact = [&](SymbolVersion pat, uint16_t id, StringRef ver) {
217 bool found = assignExactVersion(ver: pat, versionId: id);
218 // A definition foo@v1 is keyed by "foo@v1"; look it up so that the
219 // pattern is not reported as undefined. Its version is governed by
220 // parseSymbolVersion instead.
221 buf.clear();
222 found |= !findByVersion(ver: {.name: (pat.name + "@" + v.name).toStringRef(Out&: buf),
223 .isExternCpp: pat.isExternCpp, /*hasWildCard=*/.hasWildcard: false})
224 .empty();
225 if (!found && !ctx.arg.undefinedVersion)
226 Err(ctx) << "version script assignment of '" << ver << "' to symbol '"
227 << pat.name << "' failed: symbol not defined";
228 };
229 for (SymbolVersion &pat : v.nonLocalPatterns)
230 if (!pat.hasWildcard)
231 assignExact(pat, v.id, v.name);
232 for (SymbolVersion pat : v.localPatterns)
233 if (!pat.hasWildcard)
234 assignExact(pat, VER_NDX_LOCAL, "local");
235 }
236
237 // Next, collect wildcards in precedence order, where "*" patterns have the
238 // lowest precedence in GNU ld. Because the last match takes precedence over
239 // previous matches, we iterate over the definitions in the reverse order.
240 SmallVector<WildcardPattern, 0> pats, asterisks;
241 bool globalAsteriskFound = false;
242 bool localAsteriskFound = false;
243 bool asteriskReported = false;
244 for (VersionDefinition &v : llvm::reverse(C&: ctx.arg.versionDefinitions)) {
245 for (bool isLocal : {false, true}) {
246 uint16_t id = isLocal ? VER_NDX_LOCAL : v.id;
247 for (SymbolVersion &pat :
248 isLocal ? v.localPatterns : v.nonLocalPatterns) {
249 if (!pat.hasWildcard)
250 continue;
251 if (pat.name != "*") {
252 pats.emplace_back(Args&: pat, Args&: id);
253 continue;
254 }
255 if (!asteriskReported) {
256 if ((isLocal && globalAsteriskFound) ||
257 (!isLocal && localAsteriskFound)) {
258 Warn(ctx)
259 << "wildcard pattern '*' is used for both 'local' and 'global' "
260 "scopes in version script";
261 asteriskReported = true;
262 } else if (!isLocal && globalAsteriskFound) {
263 Warn(ctx) << "wildcard pattern '*' is used for multiple version "
264 "definitions in version script";
265 asteriskReported = true;
266 } else {
267 localAsteriskFound = isLocal;
268 globalAsteriskFound = !isLocal;
269 }
270 }
271 asterisks.emplace_back(Args&: pat, Args&: id);
272 }
273 }
274 }
275 pats.append(RHS: asterisks);
276
277 auto findFirstMatch = [&](ArrayRef<WildcardPattern> pats,
278 StringRef name) -> const WildcardPattern * {
279 std::optional<std::string> demangled;
280 for (auto &pat : pats) {
281 if (pat.isExternCpp && !demangled)
282 demangled = demangleForVersion(name);
283 if (pat.matcher.match(s: pat.isExternCpp ? StringRef(*demangled) : name))
284 return &pat;
285 }
286 return nullptr;
287 };
288
289 // Exact matching takes precedence over wildcard matching, so a wildcard
290 // assigns a version only if none has been assigned.
291 if (!pats.empty()) {
292 parallelForEach(R&: symVector, Fn: [&](Symbol *sym) {
293 if (sym->versionScriptAssigned || sym->hasVersionSuffix ||
294 !canBeVersioned(sym: *sym))
295 return;
296 if (auto *pat = findFirstMatch(pats, sym->getName()))
297 sym->versionId = pat->versionId;
298 });
299 }
300
301 // Handle --dynamic-list. If a specified symbol is also matched by local: in a
302 // version script, the version script takes precedence.
303 SmallVector<Symbol *, 0> syms;
304 pats.clear();
305 for (SymbolVersion &ver : ctx.arg.dynamicList) {
306 if (ver.hasWildcard) {
307 pats.emplace_back(Args&: ver, Args: 0);
308 } else {
309 for (Symbol *sym : findByVersion(ver))
310 sym->isExported = sym->inDynamicList = true;
311 }
312 }
313 if (!pats.empty()) {
314 parallelForEach(R&: symVector, Fn: [&](Symbol *sym) {
315 if (!canBeVersioned(sym: *sym))
316 return;
317 StringRef name = sym->getName();
318 if (findFirstMatch(pats, name))
319 sym->isExported = sym->inDynamicList = true;
320 });
321 }
322}
323
324Symbol *SymbolTable::addUnusedUndefined(StringRef name, uint8_t binding) {
325 return addSymbol(newSym: Undefined{ctx.internalFile, name, binding, STV_DEFAULT, 0});
326}
327