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