Path: blob/main/contrib/llvm-project/lld/MachO/SymbolTable.cpp
34878 views
//===- SymbolTable.cpp ----------------------------------------------------===//1//2// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.3// See https://llvm.org/LICENSE.txt for license information.4// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception5//6//===----------------------------------------------------------------------===//78#include "SymbolTable.h"9#include "ConcatOutputSection.h"10#include "Config.h"11#include "InputFiles.h"12#include "InputSection.h"13#include "Symbols.h"14#include "SyntheticSections.h"15#include "lld/Common/ErrorHandler.h"16#include "lld/Common/Memory.h"17#include "llvm/Demangle/Demangle.h"1819using namespace llvm;20using namespace lld;21using namespace lld::macho;2223Symbol *SymbolTable::find(CachedHashStringRef cachedName) {24auto it = symMap.find(cachedName);25if (it == symMap.end())26return nullptr;27return symVector[it->second];28}2930std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,31const InputFile *file) {32auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});3334Symbol *sym;35if (!p.second) {36// Name already present in the symbol table.37sym = symVector[p.first->second];38} else {39// Name is a new symbol.40sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());41symVector.push_back(sym);42}4344sym->isUsedInRegularObj |= !file || isa<ObjFile>(file);45return {sym, p.second};46}4748namespace {49struct DuplicateSymbolDiag {50// Pair containing source location and source file51const std::pair<std::string, std::string> src1;52const std::pair<std::string, std::string> src2;53const Symbol *sym;5455DuplicateSymbolDiag(const std::pair<std::string, std::string> src1,56const std::pair<std::string, std::string> src2,57const Symbol *sym)58: src1(src1), src2(src2), sym(sym) {}59};60SmallVector<DuplicateSymbolDiag> dupSymDiags;61} // namespace6263// Move symbols at \p fromOff in \p fromIsec into \p toIsec, unless that symbol64// is \p skip.65static void transplantSymbolsAtOffset(InputSection *fromIsec,66InputSection *toIsec, Defined *skip,67uint64_t fromOff, uint64_t toOff) {68// Ensure the symbols will still be in address order after our insertions.69auto insertIt = llvm::upper_bound(toIsec->symbols, toOff,70[](uint64_t off, const Symbol *s) {71return cast<Defined>(s)->value < off;72});73llvm::erase_if(fromIsec->symbols, [&](Symbol *s) {74auto *d = cast<Defined>(s);75if (d->value != fromOff)76return false;77if (d != skip) {78// This repeated insertion will be quadratic unless insertIt is the end79// iterator. However, that is typically the case for files that have80// .subsections_via_symbols set.81insertIt = toIsec->symbols.insert(insertIt, d);82d->originalIsec = toIsec;83d->value = toOff;84// We don't want to have more than one unwindEntry at a given address, so85// drop the redundant ones. We We can safely drop the unwindEntries of86// the symbols in fromIsec since we will be adding another unwindEntry as87// we finish parsing toIsec's file. (We can assume that toIsec has its88// own unwindEntry because of the ODR.)89d->originalUnwindEntry = nullptr;90}91return true;92});93}9495Defined *SymbolTable::addDefined(StringRef name, InputFile *file,96InputSection *isec, uint64_t value,97uint64_t size, bool isWeakDef,98bool isPrivateExtern,99bool isReferencedDynamically, bool noDeadStrip,100bool isWeakDefCanBeHidden) {101bool overridesWeakDef = false;102auto [s, wasInserted] = insert(name, file);103104assert(!file || !isa<BitcodeFile>(file) || !isec);105106if (!wasInserted) {107if (auto *defined = dyn_cast<Defined>(s)) {108if (isWeakDef) {109// See further comment in createDefined() in InputFiles.cpp110if (defined->isWeakDef()) {111defined->privateExtern &= isPrivateExtern;112defined->weakDefCanBeHidden &= isWeakDefCanBeHidden;113defined->referencedDynamically |= isReferencedDynamically;114defined->noDeadStrip |= noDeadStrip;115}116if (auto concatIsec = dyn_cast_or_null<ConcatInputSection>(isec)) {117concatIsec->wasCoalesced = true;118// Any local symbols that alias the coalesced symbol should be moved119// into the prevailing section. Note that we have sorted the symbols120// in ObjFile::parseSymbols() such that extern weak symbols appear121// last, so we don't need to worry about subsequent symbols being122// added to an already-coalesced section.123if (defined->isec())124transplantSymbolsAtOffset(concatIsec, defined->isec(),125/*skip=*/nullptr, value, defined->value);126}127return defined;128}129130if (defined->isWeakDef()) {131if (auto concatIsec =132dyn_cast_or_null<ConcatInputSection>(defined->isec())) {133concatIsec->wasCoalesced = true;134if (isec)135transplantSymbolsAtOffset(concatIsec, isec, defined, defined->value,136value);137}138} else {139std::string srcLoc1 = defined->getSourceLocation();140std::string srcLoc2 = isec ? isec->getSourceLocation(value) : "";141std::string srcFile1 = toString(defined->getFile());142std::string srcFile2 = toString(file);143144dupSymDiags.push_back({make_pair(srcLoc1, srcFile1),145make_pair(srcLoc2, srcFile2), defined});146}147148} else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {149overridesWeakDef = !isWeakDef && dysym->isWeakDef();150dysym->unreference();151} else if (auto *undef = dyn_cast<Undefined>(s)) {152if (undef->wasBitcodeSymbol) {153auto objFile = dyn_cast<ObjFile>(file);154if (!objFile) {155// The file must be a native object file, as opposed to potentially156// being another bitcode file. A situation arises when some symbols157// are defined thru `module asm` and thus they are not present in the158// bitcode's symbol table. Consider bitcode modules `A`, `B`, and `C`.159// LTO compiles only `A` and `C`, since there's no explicit symbol160// reference to `B` other than a symbol from `A` via `module asm`.161// After LTO is finished, the missing symbol now appears in the162// resulting object file for `A`, which prematurely resolves another163// prevailing symbol with `B` that hasn't been compiled, instead of164// the resulting object for `C`. Consequently, an incorrect165// relocation is generated for the prevailing symbol.166assert(isa<BitcodeFile>(file) && "Bitcode file is expected.");167std::string message =168"The pending prevailing symbol(" + name.str() +169") in the bitcode file(" + toString(undef->getFile()) +170") is overridden by a non-native object (from bitcode): " +171toString(file);172error(message);173} else if (!objFile->builtFromBitcode) {174// Ideally, this should be an object file compiled from a bitcode175// file. However, this might not hold true if a LC linker option is176// used. In case LTO internalizes a prevailing hidden weak symbol,177// there's a situation where an unresolved prevailing symbol might be178// linked with the corresponding one from a native library, which is179// loaded later after LTO. Although this could potentially result in180// an ODR violation, we choose to permit this scenario as a warning.181std::string message = "The pending prevailing symbol(" + name.str() +182") in the bitcode file(" +183toString(undef->getFile()) +184") is overridden by a post-processed native "185"object (from native archive): " +186toString(file);187warn(message);188} else {189// Preserve the original bitcode file name (instead of using the190// object file name).191file = undef->getFile();192}193}194}195// Defined symbols take priority over other types of symbols, so in case196// of a name conflict, we fall through to the replaceSymbol() call below.197}198199// With -flat_namespace, all extern symbols in dylibs are interposable.200// FIXME: Add support for `-interposable` (PR53680).201bool interposable = config->namespaceKind == NamespaceKind::flat &&202config->outputType != MachO::MH_EXECUTE &&203!isPrivateExtern;204Defined *defined = replaceSymbol<Defined>(205s, name, file, isec, value, size, isWeakDef, /*isExternal=*/true,206isPrivateExtern, /*includeInSymtab=*/true, isReferencedDynamically,207noDeadStrip, overridesWeakDef, isWeakDefCanBeHidden, interposable);208return defined;209}210211Defined *SymbolTable::aliasDefined(Defined *src, StringRef target,212InputFile *newFile, bool makePrivateExtern) {213bool isPrivateExtern = makePrivateExtern || src->privateExtern;214return addDefined(target, newFile, src->isec(), src->value, src->size,215src->isWeakDef(), isPrivateExtern,216src->referencedDynamically, src->noDeadStrip,217src->weakDefCanBeHidden);218}219220Symbol *SymbolTable::addUndefined(StringRef name, InputFile *file,221bool isWeakRef) {222auto [s, wasInserted] = insert(name, file);223224RefState refState = isWeakRef ? RefState::Weak : RefState::Strong;225226if (wasInserted)227replaceSymbol<Undefined>(s, name, file, refState,228/*wasBitcodeSymbol=*/false);229else if (auto *lazy = dyn_cast<LazyArchive>(s))230lazy->fetchArchiveMember();231else if (isa<LazyObject>(s))232extract(*s->getFile(), s->getName());233else if (auto *dynsym = dyn_cast<DylibSymbol>(s))234dynsym->reference(refState);235else if (auto *undefined = dyn_cast<Undefined>(s))236undefined->refState = std::max(undefined->refState, refState);237return s;238}239240Symbol *SymbolTable::addCommon(StringRef name, InputFile *file, uint64_t size,241uint32_t align, bool isPrivateExtern) {242auto [s, wasInserted] = insert(name, file);243244if (!wasInserted) {245if (auto *common = dyn_cast<CommonSymbol>(s)) {246if (size < common->size)247return s;248} else if (isa<Defined>(s)) {249return s;250}251// Common symbols take priority over all non-Defined symbols, so in case of252// a name conflict, we fall through to the replaceSymbol() call below.253}254255replaceSymbol<CommonSymbol>(s, name, file, size, align, isPrivateExtern);256return s;257}258259Symbol *SymbolTable::addDylib(StringRef name, DylibFile *file, bool isWeakDef,260bool isTlv) {261auto [s, wasInserted] = insert(name, file);262263RefState refState = RefState::Unreferenced;264if (!wasInserted) {265if (auto *defined = dyn_cast<Defined>(s)) {266if (isWeakDef && !defined->isWeakDef())267defined->overridesWeakDef = true;268} else if (auto *undefined = dyn_cast<Undefined>(s)) {269refState = undefined->refState;270} else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {271refState = dysym->getRefState();272}273}274275bool isDynamicLookup = file == nullptr;276if (wasInserted || isa<Undefined>(s) ||277(isa<DylibSymbol>(s) &&278((!isWeakDef && s->isWeakDef()) ||279(!isDynamicLookup && cast<DylibSymbol>(s)->isDynamicLookup())))) {280if (auto *dynsym = dyn_cast<DylibSymbol>(s))281dynsym->unreference();282replaceSymbol<DylibSymbol>(s, file, name, isWeakDef, refState, isTlv);283}284285return s;286}287288Symbol *SymbolTable::addDynamicLookup(StringRef name) {289return addDylib(name, /*file=*/nullptr, /*isWeakDef=*/false, /*isTlv=*/false);290}291292Symbol *SymbolTable::addLazyArchive(StringRef name, ArchiveFile *file,293const object::Archive::Symbol &sym) {294auto [s, wasInserted] = insert(name, file);295296if (wasInserted) {297replaceSymbol<LazyArchive>(s, file, sym);298} else if (isa<Undefined>(s)) {299file->fetch(sym);300} else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {301if (dysym->isWeakDef()) {302if (dysym->getRefState() != RefState::Unreferenced)303file->fetch(sym);304else305replaceSymbol<LazyArchive>(s, file, sym);306}307}308return s;309}310311Symbol *SymbolTable::addLazyObject(StringRef name, InputFile &file) {312auto [s, wasInserted] = insert(name, &file);313314if (wasInserted) {315replaceSymbol<LazyObject>(s, file, name);316} else if (isa<Undefined>(s)) {317extract(file, name);318} else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {319if (dysym->isWeakDef()) {320if (dysym->getRefState() != RefState::Unreferenced)321extract(file, name);322else323replaceSymbol<LazyObject>(s, file, name);324}325}326return s;327}328329Defined *SymbolTable::addSynthetic(StringRef name, InputSection *isec,330uint64_t value, bool isPrivateExtern,331bool includeInSymtab,332bool referencedDynamically) {333assert(!isec || !isec->getFile()); // See makeSyntheticInputSection().334Defined *s = addDefined(name, /*file=*/nullptr, isec, value, /*size=*/0,335/*isWeakDef=*/false, isPrivateExtern,336referencedDynamically, /*noDeadStrip=*/false,337/*isWeakDefCanBeHidden=*/false);338s->includeInSymtab = includeInSymtab;339return s;340}341342enum class Boundary {343Start,344End,345};346347static Defined *createBoundarySymbol(const Undefined &sym) {348return symtab->addSynthetic(349sym.getName(), /*isec=*/nullptr, /*value=*/-1, /*isPrivateExtern=*/true,350/*includeInSymtab=*/false, /*referencedDynamically=*/false);351}352353static void handleSectionBoundarySymbol(const Undefined &sym, StringRef segSect,354Boundary which) {355auto [segName, sectName] = segSect.split('$');356357// Attach the symbol to any InputSection that will end up in the right358// OutputSection -- it doesn't matter which one we pick.359// Don't bother looking through inputSections for a matching360// ConcatInputSection -- we need to create ConcatInputSection for361// non-existing sections anyways, and that codepath works even if we should362// already have a ConcatInputSection with the right name.363364OutputSection *osec = nullptr;365// This looks for __TEXT,__cstring etc.366for (SyntheticSection *ssec : syntheticSections)367if (ssec->segname == segName && ssec->name == sectName) {368osec = ssec->isec->parent;369break;370}371372if (!osec) {373ConcatInputSection *isec = makeSyntheticInputSection(segName, sectName);374375// This runs after markLive() and is only called for Undefineds that are376// live. Marking the isec live ensures an OutputSection is created that the377// start/end symbol can refer to.378assert(sym.isLive());379assert(isec->live);380381// This runs after gatherInputSections(), so need to explicitly set parent382// and add to inputSections.383osec = isec->parent = ConcatOutputSection::getOrCreateForInput(isec);384inputSections.push_back(isec);385}386387if (which == Boundary::Start)388osec->sectionStartSymbols.push_back(createBoundarySymbol(sym));389else390osec->sectionEndSymbols.push_back(createBoundarySymbol(sym));391}392393static void handleSegmentBoundarySymbol(const Undefined &sym, StringRef segName,394Boundary which) {395OutputSegment *seg = getOrCreateOutputSegment(segName);396if (which == Boundary::Start)397seg->segmentStartSymbols.push_back(createBoundarySymbol(sym));398else399seg->segmentEndSymbols.push_back(createBoundarySymbol(sym));400}401402// Try to find a definition for an undefined symbol.403// Returns true if a definition was found and no diagnostics are needed.404static bool recoverFromUndefinedSymbol(const Undefined &sym) {405// Handle start/end symbols.406StringRef name = sym.getName();407if (name.consume_front("section$start$")) {408handleSectionBoundarySymbol(sym, name, Boundary::Start);409return true;410}411if (name.consume_front("section$end$")) {412handleSectionBoundarySymbol(sym, name, Boundary::End);413return true;414}415if (name.consume_front("segment$start$")) {416handleSegmentBoundarySymbol(sym, name, Boundary::Start);417return true;418}419if (name.consume_front("segment$end$")) {420handleSegmentBoundarySymbol(sym, name, Boundary::End);421return true;422}423424// Leave dtrace symbols, since we will handle them when we do the relocation425if (name.starts_with("___dtrace_"))426return true;427428// Handle -U.429if (config->explicitDynamicLookups.count(sym.getName())) {430symtab->addDynamicLookup(sym.getName());431return true;432}433434// Handle -undefined.435if (config->undefinedSymbolTreatment ==436UndefinedSymbolTreatment::dynamic_lookup ||437config->undefinedSymbolTreatment == UndefinedSymbolTreatment::suppress) {438symtab->addDynamicLookup(sym.getName());439return true;440}441442// We do not return true here, as we still need to print diagnostics.443if (config->undefinedSymbolTreatment == UndefinedSymbolTreatment::warning)444symtab->addDynamicLookup(sym.getName());445446return false;447}448449namespace {450struct UndefinedDiag {451struct SectionAndOffset {452const InputSection *isec;453uint64_t offset;454};455456std::vector<SectionAndOffset> codeReferences;457std::vector<std::string> otherReferences;458};459460MapVector<const Undefined *, UndefinedDiag> undefs;461} // namespace462463void macho::reportPendingDuplicateSymbols() {464for (const auto &duplicate : dupSymDiags) {465if (!config->deadStripDuplicates || duplicate.sym->isLive()) {466std::string message =467"duplicate symbol: " + toString(*duplicate.sym) + "\n>>> defined in ";468if (!duplicate.src1.first.empty())469message += duplicate.src1.first + "\n>>> ";470message += duplicate.src1.second + "\n>>> defined in ";471if (!duplicate.src2.first.empty())472message += duplicate.src2.first + "\n>>> ";473error(message + duplicate.src2.second);474}475}476}477478// Check whether the definition name def is a mangled function name that matches479// the reference name ref.480static bool canSuggestExternCForCXX(StringRef ref, StringRef def) {481llvm::ItaniumPartialDemangler d;482std::string name = def.str();483if (d.partialDemangle(name.c_str()))484return false;485char *buf = d.getFunctionName(nullptr, nullptr);486if (!buf)487return false;488bool ret = ref == buf;489free(buf);490return ret;491}492493// Suggest an alternative spelling of an "undefined symbol" diagnostic. Returns494// the suggested symbol, which is either in the symbol table, or in the same495// file of sym.496static const Symbol *getAlternativeSpelling(const Undefined &sym,497std::string &preHint,498std::string &postHint) {499DenseMap<StringRef, const Symbol *> map;500if (sym.getFile() && sym.getFile()->kind() == InputFile::ObjKind) {501// Build a map of local defined symbols.502for (const Symbol *s : sym.getFile()->symbols)503if (auto *defined = dyn_cast_or_null<Defined>(s))504if (!defined->isExternal())505map.try_emplace(s->getName(), s);506}507508auto suggest = [&](StringRef newName) -> const Symbol * {509// If defined locally.510if (const Symbol *s = map.lookup(newName))511return s;512513// If in the symbol table and not undefined.514if (const Symbol *s = symtab->find(newName))515if (dyn_cast<Undefined>(s) == nullptr)516return s;517518return nullptr;519};520521// This loop enumerates all strings of Levenshtein distance 1 as typo522// correction candidates and suggests the one that exists as a non-undefined523// symbol.524StringRef name = sym.getName();525for (size_t i = 0, e = name.size(); i != e + 1; ++i) {526// Insert a character before name[i].527std::string newName = (name.substr(0, i) + "0" + name.substr(i)).str();528for (char c = '0'; c <= 'z'; ++c) {529newName[i] = c;530if (const Symbol *s = suggest(newName))531return s;532}533if (i == e)534break;535536// Substitute name[i].537newName = std::string(name);538for (char c = '0'; c <= 'z'; ++c) {539newName[i] = c;540if (const Symbol *s = suggest(newName))541return s;542}543544// Transpose name[i] and name[i+1]. This is of edit distance 2 but it is545// common.546if (i + 1 < e) {547newName[i] = name[i + 1];548newName[i + 1] = name[i];549if (const Symbol *s = suggest(newName))550return s;551}552553// Delete name[i].554newName = (name.substr(0, i) + name.substr(i + 1)).str();555if (const Symbol *s = suggest(newName))556return s;557}558559// Case mismatch, e.g. Foo vs FOO.560for (auto &it : map)561if (name.equals_insensitive(it.first))562return it.second;563for (Symbol *sym : symtab->getSymbols())564if (dyn_cast<Undefined>(sym) == nullptr &&565name.equals_insensitive(sym->getName()))566return sym;567568// The reference may be a mangled name while the definition is not. Suggest a569// missing extern "C".570if (name.starts_with("__Z")) {571std::string buf = name.str();572llvm::ItaniumPartialDemangler d;573if (!d.partialDemangle(buf.c_str()))574if (char *buf = d.getFunctionName(nullptr, nullptr)) {575const Symbol *s = suggest((Twine("_") + buf).str());576free(buf);577if (s) {578preHint = ": extern \"C\" ";579return s;580}581}582} else {583StringRef nameWithoutUnderscore = name;584nameWithoutUnderscore.consume_front("_");585const Symbol *s = nullptr;586for (auto &it : map)587if (canSuggestExternCForCXX(nameWithoutUnderscore, it.first)) {588s = it.second;589break;590}591if (!s)592for (Symbol *sym : symtab->getSymbols())593if (canSuggestExternCForCXX(nameWithoutUnderscore, sym->getName())) {594s = sym;595break;596}597if (s) {598preHint = " to declare ";599postHint = " as extern \"C\"?";600return s;601}602}603604return nullptr;605}606607static void reportUndefinedSymbol(const Undefined &sym,608const UndefinedDiag &locations,609bool correctSpelling) {610std::string message = "undefined symbol";611if (config->archMultiple)612message += (" for arch " + getArchitectureName(config->arch())).str();613message += ": " + toString(sym);614615const size_t maxUndefinedReferences = 3;616size_t i = 0;617for (const std::string &loc : locations.otherReferences) {618if (i >= maxUndefinedReferences)619break;620message += "\n>>> referenced by " + loc;621++i;622}623624for (const UndefinedDiag::SectionAndOffset &loc : locations.codeReferences) {625if (i >= maxUndefinedReferences)626break;627message += "\n>>> referenced by ";628std::string src = loc.isec->getSourceLocation(loc.offset);629if (!src.empty())630message += src + "\n>>> ";631message += loc.isec->getLocation(loc.offset);632++i;633}634635size_t totalReferences =636locations.otherReferences.size() + locations.codeReferences.size();637if (totalReferences > i)638message +=639("\n>>> referenced " + Twine(totalReferences - i) + " more times")640.str();641642if (correctSpelling) {643std::string preHint = ": ", postHint;644if (const Symbol *corrected =645getAlternativeSpelling(sym, preHint, postHint)) {646message +=647"\n>>> did you mean" + preHint + toString(*corrected) + postHint;648if (corrected->getFile())649message += "\n>>> defined in: " + toString(corrected->getFile());650}651}652653if (config->undefinedSymbolTreatment == UndefinedSymbolTreatment::error)654error(message);655else if (config->undefinedSymbolTreatment ==656UndefinedSymbolTreatment::warning)657warn(message);658else659assert(false && "diagnostics make sense for -undefined error|warning only");660}661662void macho::reportPendingUndefinedSymbols() {663// Enable spell corrector for the first 2 diagnostics.664for (const auto &[i, undef] : llvm::enumerate(undefs))665reportUndefinedSymbol(*undef.first, undef.second, i < 2);666667// This function is called multiple times during execution. Clear the printed668// diagnostics to avoid printing the same things again the next time.669undefs.clear();670}671672void macho::treatUndefinedSymbol(const Undefined &sym, StringRef source) {673if (recoverFromUndefinedSymbol(sym))674return;675676undefs[&sym].otherReferences.push_back(source.str());677}678679void macho::treatUndefinedSymbol(const Undefined &sym, const InputSection *isec,680uint64_t offset) {681if (recoverFromUndefinedSymbol(sym))682return;683684undefs[&sym].codeReferences.push_back({isec, offset});685}686687std::unique_ptr<SymbolTable> macho::symtab;688689690