Relocations.cpp

//===- Relocations.cpp ----------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains platform-independent functions to process relocations.
// I'll describe the overview of this file here.
//
// Simple relocations are easy to handle for the linker. For example,
// for R_X86_64_PC64 relocs, the linker just has to fix up locations
// with the relative offsets to the target symbols. It would just be
// reading records from relocation sections and applying them to output.
//
// But not all relocations are that easy to handle. For example, for
// R_386_GOTOFF relocs, the linker has to create new GOT entries for
// symbols if they don't exist, and fix up locations with GOT entry
// offsets from the beginning of GOT section. So there is more than
// fixing addresses in relocation processing.
//
// ELF defines a large number of complex relocations.
//
// The functions in this file analyze relocations and do whatever needs
// to be done. It includes, but not limited to, the following.
//
// - create GOT/PLT entries
// - create new relocations in .dynsym to let the dynamic linker resolve
// them at runtime (since ELF supports dynamic linking, not all
// relocations can be resolved at link-time)
// - create COPY relocs and reserve space in .bss
// - replace expensive relocs (in terms of runtime cost) with cheap ones
// - error out infeasible combinations such as PIC and non-relative relocs
//
// Note that the functions in this file don't actually apply relocations
// because it doesn't know about the output file nor the output file buffer.
// It instead stores Relocation objects to InputSection's Relocations
// vector to let it apply later in InputSection::writeTo.
//
//===----------------------------------------------------------------------===//

#include"Relocations.h"
#include"Config.h"
#include"InputFiles.h"
#include"LinkerScript.h"
#include"OutputSections.h"
#include"SymbolTable.h"
#include"Symbols.h"
#include"SyntheticSections.h"
#include"Target.h"
#include"Thunks.h"
#include"lld/Common/ErrorHandler.h"
#include"lld/Common/Memory.h"
#include"llvm/ADT/SmallSet.h"
#include"llvm/BinaryFormat/ELF.h"
#include"llvm/Demangle/Demangle.h"
#include"llvm/Support/Endian.h"
#include<algorithm>

usingnamespacellvm;
usingnamespacellvm::ELF;
usingnamespacellvm::object;
usingnamespacellvm::support::endian;
usingnamespacelld;
usingnamespacelld::elf;

staticvoidprintDefinedLocation(ELFSyncStream &s, const Symbol &sym) {
 s << "\n>>> defined in " << sym.file;
}

// Construct a message in the following format.
//
// >>> defined in /home/alice/src/foo.o
// >>> referenced by bar.c:12 (/home/alice/src/bar.c:12)
// >>> /home/alice/src/bar.o:(.text+0x1)
staticvoidprintLocation(ELFSyncStream &s, InputSectionBase &sec,
const Symbol &sym, uint64_t off) {
printDefinedLocation(s, sym);
 s << "\n>>> referenced by ";
auto tell = s.tell();
 s << sec.getSrcMsg(sym, off);
if (tell != s.tell())
 s << "\n>>> ";
 s << sec.getObjMsg(off);
}

voidelf::reportRangeError(Ctx &ctx, uint8_t *loc, const Relocation &rel,
const Twine &v, int64_t min, uint64_t max) {
 ErrorPlace errPlace = getErrorPlace(ctx, loc);
auto diag = Err(ctx);
 diag << errPlace.loc << "relocation " << rel.type
 << " out of range: " << v.str() << " is not in [" << min << ", " << max
 << ']';

if (rel.sym) {
if (!rel.sym->isSection())
 diag << "; references '" << rel.sym << '\'';
elseif (auto *d = dyn_cast<Defined>(rel.sym))
 diag << "; references section '" << d->section->name << "'";

if (ctx.arg.emachine == EM_X86_64 && rel.type == R_X86_64_PC32 &&
 rel.sym->getOutputSection() &&
 (rel.sym->getOutputSection()->flags & SHF_X86_64_LARGE)) {
 diag << "; R_X86_64_PC32 should not reference a section marked "
"SHF_X86_64_LARGE";
 }
 }
if (!errPlace.srcLoc.empty())
 diag << "\n>>> referenced by " << errPlace.srcLoc;
if (rel.sym && !rel.sym->isSection())
printDefinedLocation(diag, *rel.sym);

if (errPlace.isec && errPlace.isec->name.starts_with(".debug"))
 diag << "; consider recompiling with -fdebug-types-section to reduce size "
"of debug sections";
}

voidelf::reportRangeError(Ctx &ctx, uint8_t *loc, int64_t v, int n,
const Symbol &sym, const Twine &msg) {
auto diag = Err(ctx);
 diag << getErrorPlace(ctx, loc).loc << msg << " is out of range: " << v
 << " is not in [" << llvm::minIntN(n) << ", " << llvm::maxIntN(n) << "]";
if (!sym.getName().empty()) {
 diag << "; references '" << &sym << '\'';
printDefinedLocation(diag, sym);
 }
}

// Build a bitmask with one bit set for each 64 subset of RelExpr.
staticconstexpruint64_tbuildMask() { return0; }

template <typename... Tails>
staticconstexpruint64_tbuildMask(int head, Tails... tails) {
return (0 <= head && head < 64 ? uint64_t(1) << head : 0) |
buildMask(tails...);
}

// Return true if `Expr` is one of `Exprs`.
// There are more than 64 but less than 128 RelExprs, so we divide the set of
// exprs into [0, 64) and [64, 128) and represent each range as a constant
// 64-bit mask. Then we decide which mask to test depending on the value of
// expr and use a simple shift and bitwise-and to test for membership.
template <RelExpr... Exprs> staticbooloneof(RelExpr expr) {
assert(0 <= expr && (int)expr < 128 &&
"RelExpr is too large for 128-bit mask!");

if (expr >= 64)
return (uint64_t(1) << (expr - 64)) & buildMask((Exprs - 64)...);
return (uint64_t(1) << expr) & buildMask(Exprs...);
}

static RelType getMipsPairType(RelType type, bool isLocal) {
switch (type) {
case R_MIPS_HI16:
return R_MIPS_LO16;
case R_MIPS_GOT16:
// In case of global symbol, the R_MIPS_GOT16 relocation does not
// have a pair. Each global symbol has a unique entry in the GOT
// and a corresponding instruction with help of the R_MIPS_GOT16
// relocation loads an address of the symbol. In case of local
// symbol, the R_MIPS_GOT16 relocation creates a GOT entry to hold
// the high 16 bits of the symbol's value. A paired R_MIPS_LO16
// relocations handle low 16 bits of the address. That allows
// to allocate only one GOT entry for every 64 KBytes of local data.
return isLocal ? R_MIPS_LO16 : R_MIPS_NONE;
case R_MICROMIPS_GOT16:
return isLocal ? R_MICROMIPS_LO16 : R_MIPS_NONE;
case R_MIPS_PCHI16:
return R_MIPS_PCLO16;
case R_MICROMIPS_HI16:
return R_MICROMIPS_LO16;
default:
return R_MIPS_NONE;
 }
}

// True if non-preemptable symbol always has the same value regardless of where
// the DSO is loaded.
staticboolisAbsolute(const Symbol &sym) {
if (sym.isUndefined())
returntrue;
if (constauto *dr = dyn_cast<Defined>(&sym))
return dr->section == nullptr; // Absolute symbol.
returnfalse;
}

staticboolisAbsoluteValue(const Symbol &sym) {
returnisAbsolute(sym) || sym.isTls();
}

// Returns true if Expr refers a PLT entry.
staticboolneedsPlt(RelExpr expr) {
return oneof<R_PLT, R_PLT_PC, R_PLT_GOTREL, R_PLT_GOTPLT, R_GOTPLT_GOTREL,
 R_GOTPLT_PC, RE_LOONGARCH_PLT_PAGE_PC, RE_PPC32_PLTREL,
 RE_PPC64_CALL_PLT>(expr);
}

boollld::elf::needsGot(RelExpr expr) {
return oneof<R_GOT, RE_AARCH64_AUTH_GOT, RE_AARCH64_AUTH_GOT_PC, R_GOT_OFF,
 RE_MIPS_GOT_LOCAL_PAGE, RE_MIPS_GOT_OFF, RE_MIPS_GOT_OFF32,
 RE_AARCH64_GOT_PAGE_PC, RE_AARCH64_AUTH_GOT_PAGE_PC,
 RE_AARCH64_AUTH_GOT_PAGE_PC, R_GOT_PC, R_GOTPLT,
 RE_AARCH64_GOT_PAGE, RE_LOONGARCH_GOT, RE_LOONGARCH_GOT_PAGE_PC>(
 expr);
}

// True if this expression is of the form Sym - X, where X is a position in the
// file (PC, or GOT for example).
staticboolisRelExpr(RelExpr expr) {
return oneof<R_PC, R_GOTREL, R_GOTPLTREL, RE_ARM_PCA, RE_MIPS_GOTREL,
 RE_PPC64_CALL, RE_PPC64_RELAX_TOC, RE_AARCH64_PAGE_PC,
 R_RELAX_GOT_PC, RE_RISCV_PC_INDIRECT, RE_PPC64_RELAX_GOT_PC,
 RE_LOONGARCH_PAGE_PC>(expr);
}

static RelExpr toPlt(RelExpr expr) {
switch (expr) {
case RE_LOONGARCH_PAGE_PC:
return RE_LOONGARCH_PLT_PAGE_PC;
case RE_PPC64_CALL:
return RE_PPC64_CALL_PLT;
case R_PC:
return R_PLT_PC;
case R_ABS:
return R_PLT;
case R_GOTREL:
return R_PLT_GOTREL;
default:
return expr;
 }
}

static RelExpr fromPlt(RelExpr expr) {
// We decided not to use a plt. Optimize a reference to the plt to a
// reference to the symbol itself.
switch (expr) {
case R_PLT_PC:
case RE_PPC32_PLTREL:
return R_PC;
case RE_LOONGARCH_PLT_PAGE_PC:
return RE_LOONGARCH_PAGE_PC;
case RE_PPC64_CALL_PLT:
return RE_PPC64_CALL;
case R_PLT:
return R_ABS;
case R_PLT_GOTPLT:
return R_GOTPLTREL;
case R_PLT_GOTREL:
return R_GOTREL;
default:
return expr;
 }
}

// Returns true if a given shared symbol is in a read-only segment in a DSO.
template <classELFT> staticboolisReadOnly(SharedSymbol &ss) {
using Elf_Phdr = typename ELFT::Phdr;

// Determine if the symbol is read-only by scanning the DSO's program headers.
constauto &file = cast<SharedFile>(*ss.file);
for (const Elf_Phdr &phdr :
check(file.templategetObj<ELFT>().program_headers()))
if ((phdr.p_type == ELF::PT_LOAD || phdr.p_type == ELF::PT_GNU_RELRO) &&
 !(phdr.p_flags & ELF::PF_W) && ss.value >= phdr.p_vaddr &&
 ss.value < phdr.p_vaddr + phdr.p_memsz)
returntrue;
returnfalse;
}

// Returns symbols at the same offset as a given symbol, including SS itself.
//
// If two or more symbols are at the same offset, and at least one of
// them are copied by a copy relocation, all of them need to be copied.
// Otherwise, they would refer to different places at runtime.
template <classELFT>
static SmallSet<SharedSymbol *, 4> getSymbolsAt(Ctx &ctx, SharedSymbol &ss) {
using Elf_Sym = typename ELFT::Sym;

constauto &file = cast<SharedFile>(*ss.file);

 SmallSet<SharedSymbol *, 4> ret;
for (const Elf_Sym &s : file.templategetGlobalELFSyms<ELFT>()) {
if (s.st_shndx == SHN_UNDEF || s.st_shndx == SHN_ABS ||
 s.getType() == STT_TLS || s.st_value != ss.value)
continue;
 StringRef name = check(s.getName(file.getStringTable()));
 Symbol *sym = ctx.symtab->find(name);
if (auto *alias = dyn_cast_or_null<SharedSymbol>(sym))
 ret.insert(alias);
 }

// The loop does not check SHT_GNU_verneed, so ret does not contain
// non-default version symbols. If ss has a non-default version, ret won't
// contain ss. Just add ss unconditionally. If a non-default version alias is
// separately copy relocated, it and ss will have different addresses.
// Fortunately this case is impractical and fails with GNU ld as well.
 ret.insert(&ss);
return ret;
}

// When a symbol is copy relocated or we create a canonical plt entry, it is
// effectively a defined symbol. In the case of copy relocation the symbol is
// in .bss and in the case of a canonical plt entry it is in .plt. This function
// replaces the existing symbol with a Defined pointing to the appropriate
// location.
staticvoidreplaceWithDefined(Ctx &ctx, Symbol &sym, SectionBase &sec,
uint64_t value, uint64_t size) {
 Symbol old = sym;
Defined(ctx, sym.file, StringRef(), sym.binding, sym.stOther, sym.type, value,
 size, &sec)
 .overwrite(sym);

 sym.versionId = old.versionId;
 sym.isUsedInRegularObj = true;
// A copy relocated alias may need a GOT entry.
 sym.flags.store(old.flags.load(std::memory_order_relaxed) & NEEDS_GOT,
 std::memory_order_relaxed);
}

// Reserve space in .bss or .bss.rel.ro for copy relocation.
//
// The copy relocation is pretty much a hack. If you use a copy relocation
// in your program, not only the symbol name but the symbol's size, RW/RO
// bit and alignment become part of the ABI. In addition to that, if the
// symbol has aliases, the aliases become part of the ABI. That's subtle,
// but if you violate that implicit ABI, that can cause very counter-
// intuitive consequences.
//
// So, what is the copy relocation? It's for linking non-position
// independent code to DSOs. In an ideal world, all references to data
// exported by DSOs should go indirectly through GOT. But if object files
// are compiled as non-PIC, all data references are direct. There is no
// way for the linker to transform the code to use GOT, as machine
// instructions are already set in stone in object files. This is where
// the copy relocation takes a role.
//
// A copy relocation instructs the dynamic linker to copy data from a DSO
// to a specified address (which is usually in .bss) at load-time. If the
// static linker (that's us) finds a direct data reference to a DSO
// symbol, it creates a copy relocation, so that the symbol can be
// resolved as if it were in .bss rather than in a DSO.
//
// As you can see in this function, we create a copy relocation for the
// dynamic linker, and the relocation contains not only symbol name but
// various other information about the symbol. So, such attributes become a
// part of the ABI.
//
// Note for application developers: I can give you a piece of advice if
// you are writing a shared library. You probably should export only
// functions from your library. You shouldn't export variables.
//
// As an example what can happen when you export variables without knowing
// the semantics of copy relocations, assume that you have an exported
// variable of type T. It is an ABI-breaking change to add new members at
// end of T even though doing that doesn't change the layout of the
// existing members. That's because the space for the new members are not
// reserved in .bss unless you recompile the main program. That means they
// are likely to overlap with other data that happens to be laid out next
// to the variable in .bss. This kind of issue is sometimes very hard to
// debug. What's a solution? Instead of exporting a variable V from a DSO,
// define an accessor getV().
template <classELFT> staticvoidaddCopyRelSymbol(Ctx &ctx, SharedSymbol &ss) {
// Copy relocation against zero-sized symbol doesn't make sense.
uint64_t symSize = ss.getSize();
if (symSize == 0 || ss.alignment == 0)
Err(ctx) << "cannot create a copy relocation for symbol " << &ss;

// See if this symbol is in a read-only segment. If so, preserve the symbol's
// memory protection by reserving space in the .bss.rel.ro section.
bool isRO = isReadOnly<ELFT>(ss);
 BssSection *sec = make<BssSection>(ctx, isRO ? ".bss.rel.ro" : ".bss",
 symSize, ss.alignment);
 OutputSection *osec = (isRO ? ctx.in.bssRelRo : ctx.in.bss)->getParent();

// At this point, sectionBases has been migrated to sections. Append sec to
// sections.
if (osec->commands.empty() ||
 !isa<InputSectionDescription>(osec->commands.back()))
 osec->commands.push_back(make<InputSectionDescription>(""));
auto *isd = cast<InputSectionDescription>(osec->commands.back());
 isd->sections.push_back(sec);
 osec->commitSection(sec);

// Look through the DSO's dynamic symbol table for aliases and create a
// dynamic symbol for each one. This causes the copy relocation to correctly
// interpose any aliases.
for (SharedSymbol *sym : getSymbolsAt<ELFT>(ctx, ss))
replaceWithDefined(ctx, *sym, *sec, 0, sym->size);

 ctx.mainPart->relaDyn->addSymbolReloc(ctx.target->copyRel, *sec, 0, ss);
}

// .eh_frame sections are mergeable input sections, so their input
// offsets are not linearly mapped to output section. For each input
// offset, we need to find a section piece containing the offset and
// add the piece's base address to the input offset to compute the
// output offset. That isn't cheap.
//
// This class is to speed up the offset computation. When we process
// relocations, we access offsets in the monotonically increasing
// order. So we can optimize for that access pattern.
//
// For sections other than .eh_frame, this class doesn't do anything.
namespace {
classOffsetGetter {
public:
OffsetGetter() = default;
explicitOffsetGetter(InputSectionBase &sec) {
if (auto *eh = dyn_cast<EhInputSection>(&sec)) {
 cies = eh->cies;
 fdes = eh->fdes;
 i = cies.begin();
 j = fdes.begin();
 }
 }

// Translates offsets in input sections to offsets in output sections.
// Given offset must increase monotonically. We assume that Piece is
// sorted by inputOff.
uint64_tget(Ctx &ctx, uint64_t off) {
if (cies.empty())
return off;

while (j != fdes.end() && j->inputOff <= off)
 ++j;
auto it = j;
if (j == fdes.begin() || j[-1].inputOff + j[-1].size <= off) {
while (i != cies.end() && i->inputOff <= off)
 ++i;
if (i == cies.begin() || i[-1].inputOff + i[-1].size <= off) {
Err(ctx) << ".eh_frame: relocation is not in any piece";
return0;
 }
 it = i;
 }

// Offset -1 means that the piece is dead (i.e. garbage collected).
if (it[-1].outputOff == -1)
return -1;
return it[-1].outputOff + (off - it[-1].inputOff);
 }

private:
 ArrayRef<EhSectionPiece> cies, fdes;
 ArrayRef<EhSectionPiece>::iterator i, j;
};

// This class encapsulates states needed to scan relocations for one
// InputSectionBase.
classRelocationScanner {
public:
RelocationScanner(Ctx &ctx) : ctx(ctx) {}
template <classELFT>
voidscanSection(InputSectionBase &s, bool isEH = false);

private:
 Ctx &ctx;
 InputSectionBase *sec;
 OffsetGetter getter;

// End of relocations, used by Mips/PPC64.
constvoid *end = nullptr;

template <classRelTy> RelType getMipsN32RelType(RelTy *&rel) const;
template <classELFT, classRelTy>
int64_tcomputeMipsAddend(const RelTy &rel, RelExpr expr, bool isLocal) const;
boolisStaticLinkTimeConstant(RelExpr e, RelType type, const Symbol &sym,
uint64_t relOff) const;
voidprocessAux(RelExpr expr, RelType type, uint64_t offset, Symbol &sym,
int64_t addend) const;
unsignedhandleTlsRelocation(RelExpr expr, RelType type, uint64_t offset,
 Symbol &sym, int64_t addend);

template <classELFT, classRelTy>
voidscanOne(typename Relocs<RelTy>::const_iterator &i);
template <classELFT, classRelTy> voidscan(Relocs<RelTy> rels);
};
} // namespace

// MIPS has an odd notion of "paired" relocations to calculate addends.
// For example, if a relocation is of R_MIPS_HI16, there must be a
// R_MIPS_LO16 relocation after that, and an addend is calculated using
// the two relocations.
template <classELFT, classRelTy>
int64_tRelocationScanner::computeMipsAddend(const RelTy &rel, RelExpr expr,
bool isLocal) const {
if (expr == RE_MIPS_GOTREL && isLocal)
return sec->getFile<ELFT>()->mipsGp0;

// The ABI says that the paired relocation is used only for REL.
// See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
// This generalises to relocation types with implicit addends.
if (RelTy::HasAddend)
return0;

 RelType type = rel.getType(ctx.arg.isMips64EL);
 RelType pairTy = getMipsPairType(type, isLocal);
if (pairTy == R_MIPS_NONE)
return0;

constuint8_t *buf = sec->content().data();
uint32_t symIndex = rel.getSymbol(ctx.arg.isMips64EL);

// To make things worse, paired relocations might not be contiguous in
// the relocation table, so we need to do linear search. *sigh*
for (const RelTy *ri = &rel; ri != static_cast<const RelTy *>(end); ++ri)
if (ri->getType(ctx.arg.isMips64EL) == pairTy &&
 ri->getSymbol(ctx.arg.isMips64EL) == symIndex)
return ctx.target->getImplicitAddend(buf + ri->r_offset, pairTy);

Warn(ctx) << "can't find matching " << pairTy << " relocation for " << type;
return0;
}

// Custom error message if Sym is defined in a discarded section.
template <classELFT>
staticvoidmaybeReportDiscarded(Ctx &ctx, ELFSyncStream &msg, Undefined &sym) {
auto *file = dyn_cast<ObjFile<ELFT>>(sym.file);
if (!file || !sym.discardedSecIdx)
return;
 ArrayRef<typename ELFT::Shdr> objSections =
 file->templategetELFShdrs<ELFT>();

if (sym.type == ELF::STT_SECTION) {
 msg << "relocation refers to a discarded section: ";
 msg << CHECK2(
 file->getObj().getSectionName(objSections[sym.discardedSecIdx]), file);
 } else {
 msg << "relocation refers to a symbol in a discarded section: " << &sym;
 }
 msg << "\n>>> defined in " << file;

 Elf_Shdr_Impl<ELFT> elfSec = objSections[sym.discardedSecIdx - 1];
if (elfSec.sh_type != SHT_GROUP)
return;

// If the discarded section is a COMDAT.
 StringRef signature = file->getShtGroupSignature(objSections, elfSec);
if (const InputFile *prevailing =
 ctx.symtab->comdatGroups.lookup(CachedHashStringRef(signature))) {
 msg << "\n>>> section group signature: " << signature
 << "\n>>> prevailing definition is in " << prevailing;
if (sym.nonPrevailing) {
 msg << "\n>>> or the symbol in the prevailing group had STB_WEAK "
"binding and the symbol in a non-prevailing group had STB_GLOBAL "
"binding. Mixing groups with STB_WEAK and STB_GLOBAL binding "
"signature is not supported";
 }
 }
}

// Check whether the definition name def is a mangled function name that matches
// the reference name ref.
staticboolcanSuggestExternCForCXX(StringRef ref, StringRef def) {
 llvm::ItaniumPartialDemangler d;
 std::string name = def.str();
if (d.partialDemangle(name.c_str()))
returnfalse;
char *buf = d.getFunctionName(nullptr, nullptr);
if (!buf)
returnfalse;
bool ret = ref == buf;
free(buf);
return ret;
}

// Suggest an alternative spelling of an "undefined symbol" diagnostic. Returns
// the suggested symbol, which is either in the symbol table, or in the same
// file of sym.
staticconst Symbol *getAlternativeSpelling(Ctx &ctx, const Undefined &sym,
 std::string &pre_hint,
 std::string &post_hint) {
 DenseMap<StringRef, const Symbol *> map;
if (sym.file->kind() == InputFile::ObjKind) {
auto *file = cast<ELFFileBase>(sym.file);
// If sym is a symbol defined in a discarded section, maybeReportDiscarded()
// will give an error. Don't suggest an alternative spelling.
if (sym.discardedSecIdx != 0 &&
 file->getSections()[sym.discardedSecIdx] == &InputSection::discarded)
returnnullptr;

// Build a map of local defined symbols.
for (const Symbol *s : sym.file->getSymbols())
if (s->isLocal() && s->isDefined() && !s->getName().empty())
 map.try_emplace(s->getName(), s);
 }

auto suggest = [&](StringRef newName) -> const Symbol * {
// If defined locally.
if (const Symbol *s = map.lookup(newName))
return s;

// If in the symbol table and not undefined.
if (const Symbol *s = ctx.symtab->find(newName))
if (!s->isUndefined())
return s;

returnnullptr;
 };

// This loop enumerates all strings of Levenshtein distance 1 as typo
// correction candidates and suggests the one that exists as a non-undefined
// symbol.
 StringRef name = sym.getName();
for (size_t i = 0, e = name.size(); i != e + 1; ++i) {
// Insert a character before name[i].
 std::string newName = (name.substr(0, i) + "0" + name.substr(i)).str();
for (char c = '0'; c <= 'z'; ++c) {
 newName[i] = c;
if (const Symbol *s = suggest(newName))
return s;
 }
if (i == e)
break;

// Substitute name[i].
 newName = std::string(name);
for (char c = '0'; c <= 'z'; ++c) {
 newName[i] = c;
if (const Symbol *s = suggest(newName))
return s;
 }

// Transpose name[i] and name[i+1]. This is of edit distance 2 but it is
// common.
if (i + 1 < e) {
 newName[i] = name[i + 1];
 newName[i + 1] = name[i];
if (const Symbol *s = suggest(newName))
return s;
 }

// Delete name[i].
 newName = (name.substr(0, i) + name.substr(i + 1)).str();
if (const Symbol *s = suggest(newName))
return s;
 }

// Case mismatch, e.g. Foo vs FOO.
for (auto &it : map)
if (name.equals_insensitive(it.first))
return it.second;
for (Symbol *sym : ctx.symtab->getSymbols())
if (!sym->isUndefined() && name.equals_insensitive(sym->getName()))
return sym;

// The reference may be a mangled name while the definition is not. Suggest a
// missing extern "C".
if (name.starts_with("_Z")) {
 std::string buf = name.str();
 llvm::ItaniumPartialDemangler d;
if (!d.partialDemangle(buf.c_str()))
if (char *buf = d.getFunctionName(nullptr, nullptr)) {
const Symbol *s = suggest(buf);
free(buf);
if (s) {
 pre_hint = ": extern \"C\"";
return s;
 }
 }
 } else {
const Symbol *s = nullptr;
for (auto &it : map)
if (canSuggestExternCForCXX(name, it.first)) {
 s = it.second;
break;
 }
if (!s)
for (Symbol *sym : ctx.symtab->getSymbols())
if (canSuggestExternCForCXX(name, sym->getName())) {
 s = sym;
break;
 }
if (s) {
 pre_hint = " to declare ";
 post_hint = " as extern \"C\"?";
return s;
 }
 }

returnnullptr;
}

staticvoidreportUndefinedSymbol(Ctx &ctx, const UndefinedDiag &undef,
bool correctSpelling) {
 Undefined &sym = *undef.sym;
 ELFSyncStream msg(ctx, DiagLevel::None);

auto visibility = [&]() {
switch (sym.visibility()) {
case STV_INTERNAL:
return"internal ";
case STV_HIDDEN:
return"hidden ";
case STV_PROTECTED:
return"protected ";
default:
return"";
 }
 };

switch (ctx.arg.ekind) {
case ELF32LEKind:
 maybeReportDiscarded<ELF32LE>(ctx, msg, sym);
break;
case ELF32BEKind:
 maybeReportDiscarded<ELF32BE>(ctx, msg, sym);
break;
case ELF64LEKind:
 maybeReportDiscarded<ELF64LE>(ctx, msg, sym);
break;
case ELF64BEKind:
 maybeReportDiscarded<ELF64BE>(ctx, msg, sym);
break;
default:
llvm_unreachable("");
 }
if (msg.str().empty())
 msg << "undefined " << visibility() << "symbol: " << &sym;

constsize_t maxUndefReferences = 3;
for (UndefinedDiag::Loc l :
ArrayRef(undef.locs).take_front(maxUndefReferences)) {
 InputSectionBase &sec = *l.sec;
uint64_t offset = l.offset;

 msg << "\n>>> referenced by ";
// In the absence of line number information, utilize DW_TAG_variable (if
// present) for the enclosing symbol (e.g. var in `int *a[] = {&undef};`).
 Symbol *enclosing = sec.getEnclosingSymbol(offset);

 ELFSyncStream msg1(ctx, DiagLevel::None);
auto tell = msg.tell();
 msg << sec.getSrcMsg(enclosing ? *enclosing : sym, offset);
if (tell != msg.tell())
 msg << "\n>>> ";
 msg << sec.getObjMsg(offset);
 }

if (maxUndefReferences < undef.locs.size())
 msg << "\n>>> referenced " << (undef.locs.size() - maxUndefReferences)
 << " more times";

if (correctSpelling) {
 std::string pre_hint = ": ", post_hint;
if (const Symbol *corrected =
getAlternativeSpelling(ctx, sym, pre_hint, post_hint)) {
 msg << "\n>>> did you mean" << pre_hint << corrected << post_hint
 << "\n>>> defined in: " << corrected->file;
 }
 }

if (sym.getName().starts_with("_ZTV"))
 msg << "\n>>> the vtable symbol may be undefined because the class is "
"missing its key function "
"(see https://lld.llvm.org/missingkeyfunction)";
if (ctx.arg.gcSections && ctx.arg.zStartStopGC &&
 sym.getName().starts_with("__start_")) {
 msg << "\n>>> the encapsulation symbol needs to be retained under "
"--gc-sections properly; consider -z nostart-stop-gc "
"(see https://lld.llvm.org/ELF/start-stop-gc)";
 }

if (undef.isWarning)
Warn(ctx) << msg.str();
else
 ctx.e.error(msg.str(), ErrorTag::SymbolNotFound, {sym.getName()});
}

voidelf::reportUndefinedSymbols(Ctx &ctx) {
// Find the first "undefined symbol" diagnostic for each diagnostic, and
// collect all "referenced from" lines at the first diagnostic.
 DenseMap<Symbol *, UndefinedDiag *> firstRef;
for (UndefinedDiag &undef : ctx.undefErrs) {
assert(undef.locs.size() == 1);
if (UndefinedDiag *canon = firstRef.lookup(undef.sym)) {
 canon->locs.push_back(undef.locs[0]);
 undef.locs.clear();
 } else
 firstRef[undef.sym] = &undef;
 }

// Enable spell corrector for the first 2 diagnostics.
for (auto [i, undef] : llvm::enumerate(ctx.undefErrs))
if (!undef.locs.empty())
reportUndefinedSymbol(ctx, undef, i < 2);
}

// Report an undefined symbol if necessary.
// Returns true if the undefined symbol will produce an error message.
staticboolmaybeReportUndefined(Ctx &ctx, Undefined &sym,
 InputSectionBase &sec, uint64_t offset) {
 std::lock_guard<std::mutex> lock(ctx.relocMutex);
// If versioned, issue an error (even if the symbol is weak) because we don't
// know the defining filename which is required to construct a Verneed entry.
if (sym.hasVersionSuffix) {
 ctx.undefErrs.push_back({&sym, {{&sec, offset}}, false});
returntrue;
 }
if (sym.isWeak())
returnfalse;

bool canBeExternal = !sym.isLocal() && sym.visibility() == STV_DEFAULT;
if (ctx.arg.unresolvedSymbols == UnresolvedPolicy::Ignore && canBeExternal)
returnfalse;

// clang (as of 2019-06-12) / gcc (as of 8.2.1) PPC64 may emit a .rela.toc
// which references a switch table in a discarded .rodata/.text section. The
// .toc and the .rela.toc are incorrectly not placed in the comdat. The ELF
// spec says references from outside the group to a STB_LOCAL symbol are not
// allowed. Work around the bug.
//
// PPC32 .got2 is similar but cannot be fixed. Multiple .got2 is infeasible
// because .LC0-.LTOC is not representable if the two labels are in different
// .got2
if (sym.discardedSecIdx != 0 && (sec.name == ".got2" || sec.name == ".toc"))
returnfalse;

bool isWarning =
 (ctx.arg.unresolvedSymbols == UnresolvedPolicy::Warn && canBeExternal) ||
 ctx.arg.noinhibitExec;
 ctx.undefErrs.push_back({&sym, {{&sec, offset}}, isWarning});
return !isWarning;
}

// MIPS N32 ABI treats series of successive relocations with the same offset
// as a single relocation. The similar approach used by N64 ABI, but this ABI
// packs all relocations into the single relocation record. Here we emulate
// this for the N32 ABI. Iterate over relocation with the same offset and put
// theirs types into the single bit-set.
template <classRelTy>
RelType RelocationScanner::getMipsN32RelType(RelTy *&rel) const {
uint32_t type = 0;
uint64_t offset = rel->r_offset;

int n = 0;
while (rel != static_cast<const RelTy *>(end) && rel->r_offset == offset)
 type |= (rel++)->getType(ctx.arg.isMips64EL) << (8 * n++);
return type;
}

template <bool shard = false>
staticvoidaddRelativeReloc(Ctx &ctx, InputSectionBase &isec,
uint64_t offsetInSec, Symbol &sym, int64_t addend,
 RelExpr expr, RelType type) {
 Partition &part = isec.getPartition(ctx);

if (sym.isTagged()) {
 part.relaDyn->addRelativeReloc<shard>(ctx.target->relativeRel, isec,
 offsetInSec, sym, addend, type, expr);
// With MTE globals, we always want to derive the address tag by `ldg`-ing
// the symbol. When we have a RELATIVE relocation though, we no longer have
// a reference to the symbol. Because of this, when we have an addend that
// puts the result of the RELATIVE relocation out-of-bounds of the symbol
// (e.g. the addend is outside of [0, sym.getSize()]), the AArch64 MemtagABI
// says we should store the offset to the start of the symbol in the target
// field. This is described in further detail in:
// https://github.com/ARM-software/abi-aa/blob/main/memtagabielf64/memtagabielf64.rst#841extended-semantics-of-r_aarch64_relative
if (addend < 0 || static_cast<uint64_t>(addend) >= sym.getSize())
 isec.relocations.push_back({expr, type, offsetInSec, addend, &sym});
return;
 }

// Add a relative relocation. If relrDyn section is enabled, and the
// relocation offset is guaranteed to be even, add the relocation to
// the relrDyn section, otherwise add it to the relaDyn section.
// relrDyn sections don't support odd offsets. Also, relrDyn sections
// don't store the addend values, so we must write it to the relocated
// address.
if (part.relrDyn && isec.addralign >= 2 && offsetInSec % 2 == 0) {
 isec.addReloc({expr, type, offsetInSec, addend, &sym});
if (shard)
 part.relrDyn->relocsVec[parallel::getThreadIndex()].push_back(
 {&isec, isec.relocs().size() - 1});
else
 part.relrDyn->relocs.push_back({&isec, isec.relocs().size() - 1});
return;
 }
 part.relaDyn->addRelativeReloc<shard>(ctx.target->relativeRel, isec,
 offsetInSec, sym, addend, type, expr);
}

template <classPltSection, classGotPltSection>
staticvoidaddPltEntry(Ctx &ctx, PltSection &plt, GotPltSection &gotPlt,
 RelocationBaseSection &rel, RelType type, Symbol &sym) {
 plt.addEntry(sym);
 gotPlt.addEntry(sym);
 rel.addReloc({type, &gotPlt, sym.getGotPltOffset(ctx),
 sym.isPreemptible ? DynamicReloc::AgainstSymbol
 : DynamicReloc::AddendOnlyWithTargetVA,
 sym, 0, R_ABS});
}

voidelf::addGotEntry(Ctx &ctx, Symbol &sym) {
 ctx.in.got->addEntry(sym);
uint64_t off = sym.getGotOffset(ctx);

// If preemptible, emit a GLOB_DAT relocation.
if (sym.isPreemptible) {
 ctx.mainPart->relaDyn->addReloc({ctx.target->gotRel, ctx.in.got.get(), off,
 DynamicReloc::AgainstSymbol, sym, 0,
 R_ABS});
return;
 }

// Otherwise, the value is either a link-time constant or the load base
// plus a constant.
if (!ctx.arg.isPic || isAbsolute(sym))
 ctx.in.got->addConstant({R_ABS, ctx.target->symbolicRel, off, 0, &sym});
else
addRelativeReloc(ctx, *ctx.in.got, off, sym, 0, R_ABS,
 ctx.target->symbolicRel);
}

staticvoidaddGotAuthEntry(Ctx &ctx, Symbol &sym) {
 ctx.in.got->addEntry(sym);
 ctx.in.got->addAuthEntry(sym);
uint64_t off = sym.getGotOffset(ctx);

// If preemptible, emit a GLOB_DAT relocation.
if (sym.isPreemptible) {
 ctx.mainPart->relaDyn->addReloc({R_AARCH64_AUTH_GLOB_DAT, ctx.in.got.get(),
 off, DynamicReloc::AgainstSymbol, sym, 0,
 R_ABS});
return;
 }

// Signed GOT requires dynamic relocation.
 ctx.in.got->getPartition(ctx).relaDyn->addReloc(
 {R_AARCH64_AUTH_RELATIVE, ctx.in.got.get(), off,
 DynamicReloc::AddendOnlyWithTargetVA, sym, 0, R_ABS});
}

staticvoidaddTpOffsetGotEntry(Ctx &ctx, Symbol &sym) {
 ctx.in.got->addEntry(sym);
uint64_t off = sym.getGotOffset(ctx);
if (!sym.isPreemptible && !ctx.arg.shared) {
 ctx.in.got->addConstant({R_TPREL, ctx.target->symbolicRel, off, 0, &sym});
return;
 }
 ctx.mainPart->relaDyn->addAddendOnlyRelocIfNonPreemptible(
 ctx.target->tlsGotRel, *ctx.in.got, off, sym, ctx.target->symbolicRel);
}

// Return true if we can define a symbol in the executable that
// contains the value/function of a symbol defined in a shared
// library.
staticboolcanDefineSymbolInExecutable(Ctx &ctx, Symbol &sym) {
// If the symbol has default visibility the symbol defined in the
// executable will preempt it.
// Note that we want the visibility of the shared symbol itself, not
// the visibility of the symbol in the output file we are producing.
if (!sym.dsoProtected)
returntrue;

// If we are allowed to break address equality of functions, defining
// a plt entry will allow the program to call the function in the
// .so, but the .so and the executable will no agree on the address
// of the function. Similar logic for objects.
return ((sym.isFunc() && ctx.arg.ignoreFunctionAddressEquality) ||
 (sym.isObject() && ctx.arg.ignoreDataAddressEquality));
}

// Returns true if a given relocation can be computed at link-time.
// This only handles relocation types expected in processAux.
//
// For instance, we know the offset from a relocation to its target at
// link-time if the relocation is PC-relative and refers a
// non-interposable function in the same executable. This function
// will return true for such relocation.
//
// If this function returns false, that means we need to emit a
// dynamic relocation so that the relocation will be fixed at load-time.
boolRelocationScanner::isStaticLinkTimeConstant(RelExpr e, RelType type,
const Symbol &sym,
uint64_t relOff) const {
// These expressions always compute a constant
if (oneof<
 R_GOTPLT, R_GOT_OFF, R_RELAX_HINT, RE_MIPS_GOT_LOCAL_PAGE,
 RE_MIPS_GOTREL, RE_MIPS_GOT_OFF, RE_MIPS_GOT_OFF32, RE_MIPS_GOT_GP_PC,
 RE_AARCH64_GOT_PAGE_PC, RE_AARCH64_AUTH_GOT_PAGE_PC, R_GOT_PC,
 R_GOTONLY_PC, R_GOTPLTONLY_PC, R_PLT_PC, R_PLT_GOTREL, R_PLT_GOTPLT,
 R_GOTPLT_GOTREL, R_GOTPLT_PC, RE_PPC32_PLTREL, RE_PPC64_CALL_PLT,
 RE_PPC64_RELAX_TOC, RE_RISCV_ADD, RE_AARCH64_GOT_PAGE,
 RE_AARCH64_AUTH_GOT, RE_AARCH64_AUTH_GOT_PC, RE_LOONGARCH_PLT_PAGE_PC,
 RE_LOONGARCH_GOT, RE_LOONGARCH_GOT_PAGE_PC>(e))
returntrue;

// These never do, except if the entire file is position dependent or if
// only the low bits are used.
if (e == R_GOT || e == R_PLT)
return ctx.target->usesOnlyLowPageBits(type) || !ctx.arg.isPic;

// R_AARCH64_AUTH_ABS64 requires a dynamic relocation.
if (sym.isPreemptible || e == RE_AARCH64_AUTH)
returnfalse;
if (!ctx.arg.isPic)
returntrue;