xref: /freebsd/contrib/llvm-project/lld/ELF/SymbolTable.cpp (revision b4e38a41f584ad4391c04b8cfec81f46176b18b0)
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 "LinkerScript.h"
19 #include "Symbols.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"
25 
26 using namespace llvm;
27 using namespace llvm::object;
28 using namespace llvm::ELF;
29 
30 namespace lld {
31 namespace elf {
32 SymbolTable *symtab;
33 
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())];
39 
40   idx2 = idx1;
41   idx1 = idx3;
42 
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));
48   real->setName(s);
49 }
50 
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>.
55   //
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);
62 
63   auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
64   int &symIndex = p.first->second;
65   bool isNew = p.second;
66 
67   if (!isNew)
68     return symVector[symIndex];
69 
70   Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
71   symVector.push_back(sym);
72 
73   // *sym was not initialized by a constructor. Fields that may get referenced
74   // when it is a placeholder must be initialized here.
75   sym->setName(name);
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;
84   sym->traced = false;
85   sym->scriptDefined = false;
86   sym->partition = 1;
87   return sym;
88 }
89 
90 Symbol *SymbolTable::addSymbol(const Symbol &newSym) {
91   Symbol *sym = symtab->insert(newSym.getName());
92   sym->resolve(newSym);
93   return sym;
94 }
95 
96 Symbol *SymbolTable::find(StringRef name) {
97   auto it = symMap.find(CachedHashStringRef(name));
98   if (it == symMap.end())
99     return nullptr;
100   Symbol *sym = symVector[it->second];
101   if (sym->isPlaceholder())
102     return nullptr;
103   return sym;
104 }
105 
106 // Initialize demangledSyms with a map from demangled symbols to symbol
107 // objects. Used to handle "extern C++" directive in version scripts.
108 //
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.
112 //
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
118 // symbols.
119 StringMap<std::vector<Symbol *>> &SymbolTable::getDemangledSyms() {
120   if (!demangledSyms) {
121     demangledSyms.emplace();
122     for (Symbol *sym : symVector) {
123       if (!sym->isDefined() && !sym->isCommon())
124         continue;
125       (*demangledSyms)[demangleItanium(sym->getName())].push_back(sym);
126     }
127   }
128   return *demangledSyms;
129 }
130 
131 std::vector<Symbol *> SymbolTable::findByVersion(SymbolVersion ver) {
132   if (ver.isExternCpp)
133     return getDemangledSyms().lookup(ver.name);
134   if (Symbol *b = find(ver.name))
135     if (b->isDefined() || b->isCommon())
136       return {b};
137   return {};
138 }
139 
140 std::vector<Symbol *> SymbolTable::findAllByVersion(SymbolVersion ver) {
141   std::vector<Symbol *> res;
142   StringMatcher m(ver.name);
143 
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());
148     return res;
149   }
150 
151   for (Symbol *sym : symVector)
152     if ((sym->isDefined() || sym->isCommon()) && m.match(sym->getName()))
153       res.push_back(sym);
154   return res;
155 }
156 
157 // Handles -dynamic-list.
158 void SymbolTable::handleDynamicList() {
159   for (SymbolVersion &ver : config->dynamicList) {
160     std::vector<Symbol *> syms;
161     if (ver.hasWildcard)
162       syms = findAllByVersion(ver);
163     else
164       syms = findByVersion(ver);
165 
166     for (Symbol *sym : syms)
167       sym->inDynamicList = true;
168   }
169 }
170 
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) {
175   if (ver.hasWildcard)
176     return;
177 
178   // Get a list of symbols which we need to assign the version to.
179   std::vector<Symbol *> syms = findByVersion(ver);
180   if (syms.empty()) {
181     if (!config->undefinedVersion)
182       error("version script assignment of '" + versionName + "' to symbol '" +
183             ver.name + "' failed: symbol not defined");
184     return;
185   }
186 
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();
193   };
194 
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('@'))
201       continue;
202 
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;
208     }
209     if (sym->versionId == versionId)
210       continue;
211 
212     warn("attempt to reassign symbol '" + ver.name + "' of " +
213          getName(sym->versionId) + " to " + getName(versionId));
214   }
215 }
216 
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;
225     }
226 }
227 
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);
239 
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);
247 
248   // Then, assign versions to "*". In GNU linkers they have lower priority than
249   // other wildcards.
250   for (VersionDefinition &v : config->versionDefinitions)
251     for (SymbolVersion &pat : v.patterns)
252       if (pat.hasWildcard && pat.name == "*")
253         assignWildcardVersion(pat, v.id);
254 
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();
260 
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
264   // --dynamic-list.
265   handleDynamicList();
266 }
267 
268 } // namespace elf
269 } // namespace lld
270