xref: /freebsd/contrib/llvm-project/lld/ELF/SymbolTable.cpp (revision 370e009188ba90c3290b1479aa06ec98b66e140a)
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/ErrorHandler.h"
21 #include "lld/Common/Memory.h"
22 #include "lld/Common/Strings.h"
23 #include "llvm/ADT/STLExtras.h"
24 
25 using namespace llvm;
26 using namespace llvm::object;
27 using namespace llvm::ELF;
28 using namespace lld;
29 using namespace lld::elf;
30 
31 std::unique_ptr<SymbolTable> elf::symtab;
32 
33 void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
34   // Redirect __real_foo to the original foo and foo to the original __wrap_foo.
35   int &idx1 = symMap[CachedHashStringRef(sym->getName())];
36   int &idx2 = symMap[CachedHashStringRef(real->getName())];
37   int &idx3 = symMap[CachedHashStringRef(wrap->getName())];
38 
39   idx2 = idx1;
40   idx1 = idx3;
41 
42   // Propagate symbol usage information to the redirected symbols.
43   if (sym->isUsedInRegularObj)
44     wrap->isUsedInRegularObj = true;
45   if (real->isUsedInRegularObj)
46     sym->isUsedInRegularObj = true;
47   else if (!sym->isDefined())
48     // Now that all references to sym have been redirected to wrap, if there are
49     // no references to real (which has been redirected to sym), we only need to
50     // keep sym if it was defined, otherwise it's unused and can be dropped.
51     sym->isUsedInRegularObj = false;
52 
53   // Now renaming is complete, and no one refers to real. We drop real from
54   // .symtab and .dynsym. If real is undefined, it is important that we don't
55   // leave it in .dynsym, because otherwise it might lead to an undefined symbol
56   // error in a subsequent link. If real is defined, we could emit real as an
57   // alias for sym, but that could degrade the user experience of some tools
58   // that can print out only one symbol for each location: sym is a preferred
59   // name than real, but they might print out real instead.
60   memcpy(real, sym, sizeof(SymbolUnion));
61   real->isUsedInRegularObj = false;
62 }
63 
64 // Find an existing symbol or create a new one.
65 Symbol *SymbolTable::insert(StringRef name) {
66   // <name>@@<version> means the symbol is the default version. In that
67   // case <name>@@<version> will be used to resolve references to <name>.
68   //
69   // Since this is a hot path, the following string search code is
70   // optimized for speed. StringRef::find(char) is much faster than
71   // StringRef::find(StringRef).
72   StringRef stem = name;
73   size_t pos = name.find('@');
74   if (pos != StringRef::npos && pos + 1 < name.size() && name[pos + 1] == '@')
75     stem = name.take_front(pos);
76 
77   auto p = symMap.insert({CachedHashStringRef(stem), (int)symVector.size()});
78   if (!p.second) {
79     Symbol *sym = symVector[p.first->second];
80     if (stem.size() != name.size()) {
81       sym->setName(name);
82       sym->hasVersionSuffix = true;
83     }
84     return sym;
85   }
86 
87   Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
88   symVector.push_back(sym);
89 
90   // *sym was not initialized by a constructor. Fields that may get referenced
91   // when it is a placeholder must be initialized here.
92   sym->setName(name);
93   sym->symbolKind = Symbol::PlaceholderKind;
94   sym->partition = 1;
95   sym->visibility = STV_DEFAULT;
96   sym->isUsedInRegularObj = false;
97   sym->exportDynamic = false;
98   sym->inDynamicList = false;
99   sym->referenced = false;
100   sym->traced = false;
101   sym->scriptDefined = false;
102   sym->versionId = VER_NDX_GLOBAL;
103   if (pos != StringRef::npos)
104     sym->hasVersionSuffix = true;
105   return sym;
106 }
107 
108 Symbol *SymbolTable::addSymbol(const Symbol &newSym) {
109   Symbol *sym = insert(newSym.getName());
110   sym->resolve(newSym);
111   return sym;
112 }
113 
114 // This variant of addSymbol is used by BinaryFile::parse to check duplicate
115 // symbol errors.
116 Symbol *SymbolTable::addAndCheckDuplicate(const Defined &newSym) {
117   Symbol *sym = insert(newSym.getName());
118   if (sym->isDefined())
119     sym->checkDuplicate(newSym);
120   sym->resolve(newSym);
121   sym->isUsedInRegularObj = true;
122   return sym;
123 }
124 
125 Symbol *SymbolTable::find(StringRef name) {
126   auto it = symMap.find(CachedHashStringRef(name));
127   if (it == symMap.end())
128     return nullptr;
129   return symVector[it->second];
130 }
131 
132 // A version script/dynamic list is only meaningful for a Defined symbol.
133 // A CommonSymbol will be converted to a Defined in replaceCommonSymbols().
134 // A lazy symbol may be made Defined if an LTO libcall extracts it.
135 static bool canBeVersioned(const Symbol &sym) {
136   return sym.isDefined() || sym.isCommon() || sym.isLazy();
137 }
138 
139 // Initialize demangledSyms with a map from demangled symbols to symbol
140 // objects. Used to handle "extern C++" directive in version scripts.
141 //
142 // The map will contain all demangled symbols. That can be very large,
143 // and in LLD we generally want to avoid do anything for each symbol.
144 // Then, why are we doing this? Here's why.
145 //
146 // Users can use "extern C++ {}" directive to match against demangled
147 // C++ symbols. For example, you can write a pattern such as
148 // "llvm::*::foo(int, ?)". Obviously, there's no way to handle this
149 // other than trying to match a pattern against all demangled symbols.
150 // So, if "extern C++" feature is used, we need to demangle all known
151 // symbols.
152 StringMap<SmallVector<Symbol *, 0>> &SymbolTable::getDemangledSyms() {
153   if (!demangledSyms) {
154     demangledSyms.emplace();
155     std::string demangled;
156     for (Symbol *sym : symVector)
157       if (canBeVersioned(*sym)) {
158         StringRef name = sym->getName();
159         size_t pos = name.find('@');
160         if (pos == std::string::npos)
161           demangled = demangle(name, config->demangle);
162         else if (pos + 1 == name.size() || name[pos + 1] == '@')
163           demangled = demangle(name.substr(0, pos), config->demangle);
164         else
165           demangled = (demangle(name.substr(0, pos), config->demangle) +
166                        name.substr(pos))
167                           .str();
168         (*demangledSyms)[demangled].push_back(sym);
169       }
170   }
171   return *demangledSyms;
172 }
173 
174 SmallVector<Symbol *, 0> SymbolTable::findByVersion(SymbolVersion ver) {
175   if (ver.isExternCpp)
176     return getDemangledSyms().lookup(ver.name);
177   if (Symbol *sym = find(ver.name))
178     if (canBeVersioned(*sym))
179       return {sym};
180   return {};
181 }
182 
183 SmallVector<Symbol *, 0> SymbolTable::findAllByVersion(SymbolVersion ver,
184                                                        bool includeNonDefault) {
185   SmallVector<Symbol *, 0> res;
186   SingleStringMatcher m(ver.name);
187   auto check = [&](StringRef name) {
188     size_t pos = name.find('@');
189     if (!includeNonDefault)
190       return pos == StringRef::npos;
191     return !(pos + 1 < name.size() && name[pos + 1] == '@');
192   };
193 
194   if (ver.isExternCpp) {
195     for (auto &p : getDemangledSyms())
196       if (m.match(p.first()))
197         for (Symbol *sym : p.second)
198           if (check(sym->getName()))
199             res.push_back(sym);
200     return res;
201   }
202 
203   for (Symbol *sym : symVector)
204     if (canBeVersioned(*sym) && check(sym->getName()) &&
205         m.match(sym->getName()))
206       res.push_back(sym);
207   return res;
208 }
209 
210 void SymbolTable::handleDynamicList() {
211   SmallVector<Symbol *, 0> syms;
212   for (SymbolVersion &ver : config->dynamicList) {
213     if (ver.hasWildcard)
214       syms = findAllByVersion(ver, /*includeNonDefault=*/true);
215     else
216       syms = findByVersion(ver);
217 
218     for (Symbol *sym : syms)
219       sym->inDynamicList = true;
220   }
221 }
222 
223 // Set symbol versions to symbols. This function handles patterns containing no
224 // wildcard characters. Return false if no symbol definition matches ver.
225 bool SymbolTable::assignExactVersion(SymbolVersion ver, uint16_t versionId,
226                                      StringRef versionName,
227                                      bool includeNonDefault) {
228   // Get a list of symbols which we need to assign the version to.
229   SmallVector<Symbol *, 0> syms = findByVersion(ver);
230 
231   auto getName = [](uint16_t ver) -> std::string {
232     if (ver == VER_NDX_LOCAL)
233       return "VER_NDX_LOCAL";
234     if (ver == VER_NDX_GLOBAL)
235       return "VER_NDX_GLOBAL";
236     return ("version '" + config->versionDefinitions[ver].name + "'").str();
237   };
238 
239   // Assign the version.
240   for (Symbol *sym : syms) {
241     // For a non-local versionId, skip symbols containing version info because
242     // symbol versions specified by symbol names take precedence over version
243     // scripts. See parseSymbolVersion().
244     if (!includeNonDefault && versionId != VER_NDX_LOCAL &&
245         sym->getName().contains('@'))
246       continue;
247 
248     // If the version has not been assigned, verdefIndex is -1. Use an arbitrary
249     // number (0) to indicate the version has been assigned.
250     if (sym->verdefIndex == uint16_t(-1)) {
251       sym->verdefIndex = 0;
252       sym->versionId = versionId;
253     }
254     if (sym->versionId == versionId)
255       continue;
256 
257     warn("attempt to reassign symbol '" + ver.name + "' of " +
258          getName(sym->versionId) + " to " + getName(versionId));
259   }
260   return !syms.empty();
261 }
262 
263 void SymbolTable::assignWildcardVersion(SymbolVersion ver, uint16_t versionId,
264                                         bool includeNonDefault) {
265   // Exact matching takes precedence over fuzzy matching,
266   // so we set a version to a symbol only if no version has been assigned
267   // to the symbol. This behavior is compatible with GNU.
268   for (Symbol *sym : findAllByVersion(ver, includeNonDefault))
269     if (sym->verdefIndex == uint16_t(-1)) {
270       sym->verdefIndex = 0;
271       sym->versionId = versionId;
272     }
273 }
274 
275 // This function processes version scripts by updating the versionId
276 // member of symbols.
277 // If there's only one anonymous version definition in a version
278 // script file, the script does not actually define any symbol version,
279 // but just specifies symbols visibilities.
280 void SymbolTable::scanVersionScript() {
281   SmallString<128> buf;
282   // First, we assign versions to exact matching symbols,
283   // i.e. version definitions not containing any glob meta-characters.
284   for (VersionDefinition &v : config->versionDefinitions) {
285     auto assignExact = [&](SymbolVersion pat, uint16_t id, StringRef ver) {
286       bool found =
287           assignExactVersion(pat, id, ver, /*includeNonDefault=*/false);
288       buf.clear();
289       found |= assignExactVersion({(pat.name + "@" + v.name).toStringRef(buf),
290                                    pat.isExternCpp, /*hasWildCard=*/false},
291                                   id, ver, /*includeNonDefault=*/true);
292       if (!found && !config->undefinedVersion)
293         errorOrWarn("version script assignment of '" + ver + "' to symbol '" +
294                     pat.name + "' failed: symbol not defined");
295     };
296     for (SymbolVersion &pat : v.nonLocalPatterns)
297       if (!pat.hasWildcard)
298         assignExact(pat, v.id, v.name);
299     for (SymbolVersion pat : v.localPatterns)
300       if (!pat.hasWildcard)
301         assignExact(pat, VER_NDX_LOCAL, "local");
302   }
303 
304   // Next, assign versions to wildcards that are not "*". Note that because the
305   // last match takes precedence over previous matches, we iterate over the
306   // definitions in the reverse order.
307   auto assignWildcard = [&](SymbolVersion pat, uint16_t id, StringRef ver) {
308     assignWildcardVersion(pat, id, /*includeNonDefault=*/false);
309     buf.clear();
310     assignWildcardVersion({(pat.name + "@" + ver).toStringRef(buf),
311                            pat.isExternCpp, /*hasWildCard=*/true},
312                           id,
313                           /*includeNonDefault=*/true);
314   };
315   for (VersionDefinition &v : llvm::reverse(config->versionDefinitions)) {
316     for (SymbolVersion &pat : v.nonLocalPatterns)
317       if (pat.hasWildcard && pat.name != "*")
318         assignWildcard(pat, v.id, v.name);
319     for (SymbolVersion &pat : v.localPatterns)
320       if (pat.hasWildcard && pat.name != "*")
321         assignWildcard(pat, VER_NDX_LOCAL, v.name);
322   }
323 
324   // Then, assign versions to "*". In GNU linkers they have lower priority than
325   // other wildcards.
326   for (VersionDefinition &v : config->versionDefinitions) {
327     for (SymbolVersion &pat : v.nonLocalPatterns)
328       if (pat.hasWildcard && pat.name == "*")
329         assignWildcard(pat, v.id, v.name);
330     for (SymbolVersion &pat : v.localPatterns)
331       if (pat.hasWildcard && pat.name == "*")
332         assignWildcard(pat, VER_NDX_LOCAL, v.name);
333   }
334 
335   // Symbol themselves might know their versions because symbols
336   // can contain versions in the form of <name>@<version>.
337   // Let them parse and update their names to exclude version suffix.
338   for (Symbol *sym : symVector)
339     if (sym->hasVersionSuffix)
340       sym->parseSymbolVersion();
341 
342   // isPreemptible is false at this point. To correctly compute the binding of a
343   // Defined (which is used by includeInDynsym()), we need to know if it is
344   // VER_NDX_LOCAL or not. Compute symbol versions before handling
345   // --dynamic-list.
346   handleDynamicList();
347 }
348