xref: /freebsd/contrib/llvm-project/lld/ELF/SymbolTable.cpp (revision 85868e8a1daeaae7a0e48effb2ea2310ae3b02c6)
10b57cec5SDimitry Andric //===- SymbolTable.cpp ----------------------------------------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // Symbol table is a bag of all known symbols. We put all symbols of
100b57cec5SDimitry Andric // all input files to the symbol table. The symbol table is basically
110b57cec5SDimitry Andric // a hash table with the logic to resolve symbol name conflicts using
120b57cec5SDimitry Andric // the symbol types.
130b57cec5SDimitry Andric //
140b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
150b57cec5SDimitry Andric 
160b57cec5SDimitry Andric #include "SymbolTable.h"
170b57cec5SDimitry Andric #include "Config.h"
180b57cec5SDimitry Andric #include "LinkerScript.h"
190b57cec5SDimitry Andric #include "Symbols.h"
200b57cec5SDimitry Andric #include "SyntheticSections.h"
210b57cec5SDimitry Andric #include "lld/Common/ErrorHandler.h"
220b57cec5SDimitry Andric #include "lld/Common/Memory.h"
230b57cec5SDimitry Andric #include "lld/Common/Strings.h"
240b57cec5SDimitry Andric #include "llvm/ADT/STLExtras.h"
250b57cec5SDimitry Andric 
260b57cec5SDimitry Andric using namespace llvm;
270b57cec5SDimitry Andric using namespace llvm::object;
280b57cec5SDimitry Andric using namespace llvm::ELF;
290b57cec5SDimitry Andric 
30*85868e8aSDimitry Andric namespace lld {
31*85868e8aSDimitry Andric namespace elf {
32*85868e8aSDimitry Andric SymbolTable *symtab;
330b57cec5SDimitry Andric 
340b57cec5SDimitry Andric void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
350b57cec5SDimitry Andric   // Swap symbols as instructed by -wrap.
360b57cec5SDimitry Andric   int &idx1 = symMap[CachedHashStringRef(sym->getName())];
370b57cec5SDimitry Andric   int &idx2 = symMap[CachedHashStringRef(real->getName())];
380b57cec5SDimitry Andric   int &idx3 = symMap[CachedHashStringRef(wrap->getName())];
390b57cec5SDimitry Andric 
400b57cec5SDimitry Andric   idx2 = idx1;
410b57cec5SDimitry Andric   idx1 = idx3;
420b57cec5SDimitry Andric 
430b57cec5SDimitry Andric   // Now renaming is complete. No one refers Real symbol. We could leave
440b57cec5SDimitry Andric   // Real as-is, but if Real is written to the symbol table, that may
450b57cec5SDimitry Andric   // contain irrelevant values. So, we copy all values from Sym to Real.
460b57cec5SDimitry Andric   StringRef s = real->getName();
470b57cec5SDimitry Andric   memcpy(real, sym, sizeof(SymbolUnion));
480b57cec5SDimitry Andric   real->setName(s);
490b57cec5SDimitry Andric }
500b57cec5SDimitry Andric 
510b57cec5SDimitry Andric // Find an existing symbol or create a new one.
520b57cec5SDimitry Andric Symbol *SymbolTable::insert(StringRef name) {
530b57cec5SDimitry Andric   // <name>@@<version> means the symbol is the default version. In that
540b57cec5SDimitry Andric   // case <name>@@<version> will be used to resolve references to <name>.
550b57cec5SDimitry Andric   //
560b57cec5SDimitry Andric   // Since this is a hot path, the following string search code is
570b57cec5SDimitry Andric   // optimized for speed. StringRef::find(char) is much faster than
580b57cec5SDimitry Andric   // StringRef::find(StringRef).
590b57cec5SDimitry Andric   size_t pos = name.find('@');
600b57cec5SDimitry Andric   if (pos != StringRef::npos && pos + 1 < name.size() && name[pos + 1] == '@')
610b57cec5SDimitry Andric     name = name.take_front(pos);
620b57cec5SDimitry Andric 
630b57cec5SDimitry Andric   auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
640b57cec5SDimitry Andric   int &symIndex = p.first->second;
650b57cec5SDimitry Andric   bool isNew = p.second;
660b57cec5SDimitry Andric 
670b57cec5SDimitry Andric   if (!isNew)
680b57cec5SDimitry Andric     return symVector[symIndex];
690b57cec5SDimitry Andric 
700b57cec5SDimitry Andric   Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
710b57cec5SDimitry Andric   symVector.push_back(sym);
720b57cec5SDimitry Andric 
73*85868e8aSDimitry Andric   // *sym was not initialized by a constructor. Fields that may get referenced
74*85868e8aSDimitry Andric   // when it is a placeholder must be initialized here.
750b57cec5SDimitry Andric   sym->setName(name);
760b57cec5SDimitry Andric   sym->symbolKind = Symbol::PlaceholderKind;
77*85868e8aSDimitry Andric   sym->versionId = VER_NDX_GLOBAL;
780b57cec5SDimitry Andric   sym->visibility = STV_DEFAULT;
790b57cec5SDimitry Andric   sym->isUsedInRegularObj = false;
800b57cec5SDimitry Andric   sym->exportDynamic = false;
81*85868e8aSDimitry Andric   sym->inDynamicList = false;
820b57cec5SDimitry Andric   sym->canInline = true;
83*85868e8aSDimitry Andric   sym->referenced = false;
84*85868e8aSDimitry Andric   sym->traced = false;
850b57cec5SDimitry Andric   sym->scriptDefined = false;
860b57cec5SDimitry Andric   sym->partition = 1;
870b57cec5SDimitry Andric   return sym;
880b57cec5SDimitry Andric }
890b57cec5SDimitry Andric 
90*85868e8aSDimitry Andric Symbol *SymbolTable::addSymbol(const Symbol &newSym) {
91*85868e8aSDimitry Andric   Symbol *sym = symtab->insert(newSym.getName());
92*85868e8aSDimitry Andric   sym->resolve(newSym);
930b57cec5SDimitry Andric   return sym;
940b57cec5SDimitry Andric }
950b57cec5SDimitry Andric 
960b57cec5SDimitry Andric Symbol *SymbolTable::find(StringRef name) {
970b57cec5SDimitry Andric   auto it = symMap.find(CachedHashStringRef(name));
980b57cec5SDimitry Andric   if (it == symMap.end())
990b57cec5SDimitry Andric     return nullptr;
1000b57cec5SDimitry Andric   Symbol *sym = symVector[it->second];
1010b57cec5SDimitry Andric   if (sym->isPlaceholder())
1020b57cec5SDimitry Andric     return nullptr;
1030b57cec5SDimitry Andric   return sym;
1040b57cec5SDimitry Andric }
1050b57cec5SDimitry Andric 
1060b57cec5SDimitry Andric // Initialize demangledSyms with a map from demangled symbols to symbol
1070b57cec5SDimitry Andric // objects. Used to handle "extern C++" directive in version scripts.
1080b57cec5SDimitry Andric //
1090b57cec5SDimitry Andric // The map will contain all demangled symbols. That can be very large,
1100b57cec5SDimitry Andric // and in LLD we generally want to avoid do anything for each symbol.
1110b57cec5SDimitry Andric // Then, why are we doing this? Here's why.
1120b57cec5SDimitry Andric //
1130b57cec5SDimitry Andric // Users can use "extern C++ {}" directive to match against demangled
1140b57cec5SDimitry Andric // C++ symbols. For example, you can write a pattern such as
1150b57cec5SDimitry Andric // "llvm::*::foo(int, ?)". Obviously, there's no way to handle this
1160b57cec5SDimitry Andric // other than trying to match a pattern against all demangled symbols.
1170b57cec5SDimitry Andric // So, if "extern C++" feature is used, we need to demangle all known
1180b57cec5SDimitry Andric // symbols.
1190b57cec5SDimitry Andric StringMap<std::vector<Symbol *>> &SymbolTable::getDemangledSyms() {
1200b57cec5SDimitry Andric   if (!demangledSyms) {
1210b57cec5SDimitry Andric     demangledSyms.emplace();
1220b57cec5SDimitry Andric     for (Symbol *sym : symVector) {
1230b57cec5SDimitry Andric       if (!sym->isDefined() && !sym->isCommon())
1240b57cec5SDimitry Andric         continue;
125*85868e8aSDimitry Andric       (*demangledSyms)[demangleItanium(sym->getName())].push_back(sym);
1260b57cec5SDimitry Andric     }
1270b57cec5SDimitry Andric   }
1280b57cec5SDimitry Andric   return *demangledSyms;
1290b57cec5SDimitry Andric }
1300b57cec5SDimitry Andric 
1310b57cec5SDimitry Andric std::vector<Symbol *> SymbolTable::findByVersion(SymbolVersion ver) {
1320b57cec5SDimitry Andric   if (ver.isExternCpp)
1330b57cec5SDimitry Andric     return getDemangledSyms().lookup(ver.name);
1340b57cec5SDimitry Andric   if (Symbol *b = find(ver.name))
1350b57cec5SDimitry Andric     if (b->isDefined() || b->isCommon())
1360b57cec5SDimitry Andric       return {b};
1370b57cec5SDimitry Andric   return {};
1380b57cec5SDimitry Andric }
1390b57cec5SDimitry Andric 
1400b57cec5SDimitry Andric std::vector<Symbol *> SymbolTable::findAllByVersion(SymbolVersion ver) {
1410b57cec5SDimitry Andric   std::vector<Symbol *> res;
1420b57cec5SDimitry Andric   StringMatcher m(ver.name);
1430b57cec5SDimitry Andric 
1440b57cec5SDimitry Andric   if (ver.isExternCpp) {
1450b57cec5SDimitry Andric     for (auto &p : getDemangledSyms())
1460b57cec5SDimitry Andric       if (m.match(p.first()))
1470b57cec5SDimitry Andric         res.insert(res.end(), p.second.begin(), p.second.end());
1480b57cec5SDimitry Andric     return res;
1490b57cec5SDimitry Andric   }
1500b57cec5SDimitry Andric 
1510b57cec5SDimitry Andric   for (Symbol *sym : symVector)
1520b57cec5SDimitry Andric     if ((sym->isDefined() || sym->isCommon()) && m.match(sym->getName()))
1530b57cec5SDimitry Andric       res.push_back(sym);
1540b57cec5SDimitry Andric   return res;
1550b57cec5SDimitry Andric }
1560b57cec5SDimitry Andric 
1570b57cec5SDimitry Andric // Handles -dynamic-list.
1580b57cec5SDimitry Andric void SymbolTable::handleDynamicList() {
1590b57cec5SDimitry Andric   for (SymbolVersion &ver : config->dynamicList) {
1600b57cec5SDimitry Andric     std::vector<Symbol *> syms;
1610b57cec5SDimitry Andric     if (ver.hasWildcard)
1620b57cec5SDimitry Andric       syms = findAllByVersion(ver);
1630b57cec5SDimitry Andric     else
1640b57cec5SDimitry Andric       syms = findByVersion(ver);
1650b57cec5SDimitry Andric 
166*85868e8aSDimitry Andric     for (Symbol *sym : syms)
167*85868e8aSDimitry Andric       sym->inDynamicList = true;
1680b57cec5SDimitry Andric   }
1690b57cec5SDimitry Andric }
1700b57cec5SDimitry Andric 
1710b57cec5SDimitry Andric // Set symbol versions to symbols. This function handles patterns
1720b57cec5SDimitry Andric // containing no wildcard characters.
1730b57cec5SDimitry Andric void SymbolTable::assignExactVersion(SymbolVersion ver, uint16_t versionId,
1740b57cec5SDimitry Andric                                      StringRef versionName) {
1750b57cec5SDimitry Andric   if (ver.hasWildcard)
1760b57cec5SDimitry Andric     return;
1770b57cec5SDimitry Andric 
1780b57cec5SDimitry Andric   // Get a list of symbols which we need to assign the version to.
1790b57cec5SDimitry Andric   std::vector<Symbol *> syms = findByVersion(ver);
1800b57cec5SDimitry Andric   if (syms.empty()) {
1810b57cec5SDimitry Andric     if (!config->undefinedVersion)
1820b57cec5SDimitry Andric       error("version script assignment of '" + versionName + "' to symbol '" +
1830b57cec5SDimitry Andric             ver.name + "' failed: symbol not defined");
1840b57cec5SDimitry Andric     return;
1850b57cec5SDimitry Andric   }
1860b57cec5SDimitry Andric 
1870b57cec5SDimitry Andric   auto getName = [](uint16_t ver) -> std::string {
1880b57cec5SDimitry Andric     if (ver == VER_NDX_LOCAL)
1890b57cec5SDimitry Andric       return "VER_NDX_LOCAL";
1900b57cec5SDimitry Andric     if (ver == VER_NDX_GLOBAL)
1910b57cec5SDimitry Andric       return "VER_NDX_GLOBAL";
192*85868e8aSDimitry Andric     return ("version '" + config->versionDefinitions[ver].name + "'").str();
1930b57cec5SDimitry Andric   };
1940b57cec5SDimitry Andric 
1950b57cec5SDimitry Andric   // Assign the version.
1960b57cec5SDimitry Andric   for (Symbol *sym : syms) {
1970b57cec5SDimitry Andric     // Skip symbols containing version info because symbol versions
1980b57cec5SDimitry Andric     // specified by symbol names take precedence over version scripts.
1990b57cec5SDimitry Andric     // See parseSymbolVersion().
2000b57cec5SDimitry Andric     if (sym->getName().contains('@'))
2010b57cec5SDimitry Andric       continue;
2020b57cec5SDimitry Andric 
203*85868e8aSDimitry Andric     // If the version has not been assigned, verdefIndex is -1. Use an arbitrary
204*85868e8aSDimitry Andric     // number (0) to indicate the version has been assigned.
205*85868e8aSDimitry Andric     if (sym->verdefIndex == UINT32_C(-1)) {
206*85868e8aSDimitry Andric       sym->verdefIndex = 0;
2070b57cec5SDimitry Andric       sym->versionId = versionId;
208*85868e8aSDimitry Andric     }
2090b57cec5SDimitry Andric     if (sym->versionId == versionId)
2100b57cec5SDimitry Andric       continue;
2110b57cec5SDimitry Andric 
2120b57cec5SDimitry Andric     warn("attempt to reassign symbol '" + ver.name + "' of " +
2130b57cec5SDimitry Andric          getName(sym->versionId) + " to " + getName(versionId));
2140b57cec5SDimitry Andric   }
2150b57cec5SDimitry Andric }
2160b57cec5SDimitry Andric 
2170b57cec5SDimitry Andric void SymbolTable::assignWildcardVersion(SymbolVersion ver, uint16_t versionId) {
2180b57cec5SDimitry Andric   // Exact matching takes precendence over fuzzy matching,
2190b57cec5SDimitry Andric   // so we set a version to a symbol only if no version has been assigned
2200b57cec5SDimitry Andric   // to the symbol. This behavior is compatible with GNU.
221*85868e8aSDimitry Andric   for (Symbol *sym : findAllByVersion(ver))
222*85868e8aSDimitry Andric     if (sym->verdefIndex == UINT32_C(-1)) {
223*85868e8aSDimitry Andric       sym->verdefIndex = 0;
224*85868e8aSDimitry Andric       sym->versionId = versionId;
225*85868e8aSDimitry Andric     }
2260b57cec5SDimitry Andric }
2270b57cec5SDimitry Andric 
2280b57cec5SDimitry Andric // This function processes version scripts by updating the versionId
2290b57cec5SDimitry Andric // member of symbols.
2300b57cec5SDimitry Andric // If there's only one anonymous version definition in a version
2310b57cec5SDimitry Andric // script file, the script does not actually define any symbol version,
2320b57cec5SDimitry Andric // but just specifies symbols visibilities.
2330b57cec5SDimitry Andric void SymbolTable::scanVersionScript() {
2340b57cec5SDimitry Andric   // First, we assign versions to exact matching symbols,
2350b57cec5SDimitry Andric   // i.e. version definitions not containing any glob meta-characters.
2360b57cec5SDimitry Andric   for (VersionDefinition &v : config->versionDefinitions)
237*85868e8aSDimitry Andric     for (SymbolVersion &pat : v.patterns)
238*85868e8aSDimitry Andric       assignExactVersion(pat, v.id, v.name);
2390b57cec5SDimitry Andric 
240*85868e8aSDimitry Andric   // Next, assign versions to wildcards that are not "*". Note that because the
241*85868e8aSDimitry Andric   // last match takes precedence over previous matches, we iterate over the
242*85868e8aSDimitry Andric   // definitions in the reverse order.
2430b57cec5SDimitry Andric   for (VersionDefinition &v : llvm::reverse(config->versionDefinitions))
244*85868e8aSDimitry Andric     for (SymbolVersion &pat : v.patterns)
245*85868e8aSDimitry Andric       if (pat.hasWildcard && pat.name != "*")
246*85868e8aSDimitry Andric         assignWildcardVersion(pat, v.id);
247*85868e8aSDimitry Andric 
248*85868e8aSDimitry Andric   // Then, assign versions to "*". In GNU linkers they have lower priority than
249*85868e8aSDimitry Andric   // other wildcards.
250*85868e8aSDimitry Andric   for (VersionDefinition &v : config->versionDefinitions)
251*85868e8aSDimitry Andric     for (SymbolVersion &pat : v.patterns)
252*85868e8aSDimitry Andric       if (pat.hasWildcard && pat.name == "*")
253*85868e8aSDimitry Andric         assignWildcardVersion(pat, v.id);
2540b57cec5SDimitry Andric 
2550b57cec5SDimitry Andric   // Symbol themselves might know their versions because symbols
2560b57cec5SDimitry Andric   // can contain versions in the form of <name>@<version>.
2570b57cec5SDimitry Andric   // Let them parse and update their names to exclude version suffix.
2580b57cec5SDimitry Andric   for (Symbol *sym : symVector)
2590b57cec5SDimitry Andric     sym->parseSymbolVersion();
2600b57cec5SDimitry Andric 
2610b57cec5SDimitry Andric   // isPreemptible is false at this point. To correctly compute the binding of a
2620b57cec5SDimitry Andric   // Defined (which is used by includeInDynsym()), we need to know if it is
263*85868e8aSDimitry Andric   // VER_NDX_LOCAL or not. Compute symbol versions before handling
264*85868e8aSDimitry Andric   // --dynamic-list.
2650b57cec5SDimitry Andric   handleDynamicList();
2660b57cec5SDimitry Andric }
267*85868e8aSDimitry Andric 
268*85868e8aSDimitry Andric } // namespace elf
269*85868e8aSDimitry Andric } // namespace lld
270