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