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"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"lld/Common/Strings.h"
#include"llvm/ADT/SmallSet.h"
#include"llvm/Support/Endian.h"
#include"llvm/Support/raw_ostream.h"
#include<algorithm>

usingnamespacellvm;
usingnamespacellvm::ELF;
usingnamespacellvm::object;
usingnamespacellvm::support::endian;

usingnamespacelld;
usingnamespacelld::elf;

static Optional<std::string> getLinkerScriptLocation(const Symbol &Sym) {
for (BaseCommand *Base : Script->SectionCommands)
if (auto *Cmd = dyn_cast<SymbolAssignment>(Base))
if (Cmd->Sym == &Sym)
return Cmd->Location;
return None;
}

// 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)
static std::string getLocation(InputSectionBase &S, const Symbol &Sym,
uint64_t Off) {
 std::string Msg = "\n>>> defined in ";
if (Sym.File)
 Msg += toString(Sym.File);
elseif (Optional<std::string> Loc = getLinkerScriptLocation(Sym))
 Msg += *Loc;

 Msg += "\n>>> referenced by ";
 std::string Src = S.getSrcMsg(Sym, Off);
if (!Src.empty())
 Msg += Src + "\n>>> ";
return Msg + S.getObjMsg(Off);
}

namespace {
// Build a bitmask with one bit set for each RelExpr.
//
// Constexpr function arguments can't be used in static asserts, so we
// use template arguments to build the mask.
// But function template partial specializations don't exist (needed
// for base case of the recursion), so we need a dummy struct.
template <RelExpr... Exprs> structRelExprMaskBuilder {
staticinlineuint64_tbuild() { return0; }
};

// Specialization for recursive case.
template <RelExpr Head, RelExpr... Tail>
structRelExprMaskBuilder<Head, Tail...> {
staticinlineuint64_tbuild() {
static_assert(0 <= Head && Head < 64,
"RelExpr is too large for 64-bit mask!");
return (uint64_t(1) << Head) | RelExprMaskBuilder<Tail...>::build();
 }
};
} // namespace

// Return true if `Expr` is one of `Exprs`.
// There are fewer than 64 RelExpr's, so we can represent any set of
// RelExpr's as a constant bit mask and test for membership with a
// couple cheap bitwise operations.
template <RelExpr... Exprs> booloneof(RelExpr Expr) {
assert(0 <= Expr && (int)Expr < 64 &&
"RelExpr is too large for 64-bit mask!");
return (uint64_t(1) << Expr) & RelExprMaskBuilder<Exprs...>::build();
}

// This function is similar to the `handleTlsRelocation`. MIPS does not
// support any relaxations for TLS relocations so by factoring out MIPS
// handling in to the separate function we can simplify the code and do not
// pollute other `handleTlsRelocation` by MIPS `ifs` statements.
// Mips has a custom MipsGotSection that handles the writing of GOT entries
// without dynamic relocations.
staticunsignedhandleMipsTlsRelocation(RelType Type, Symbol &Sym,
 InputSectionBase &C, uint64_t Offset,
int64_t Addend, RelExpr Expr) {
if (Expr == R_MIPS_TLSLD) {
 In.MipsGot->addTlsIndex(*C.File);
 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
return1;
 }
if (Expr == R_MIPS_TLSGD) {
 In.MipsGot->addDynTlsEntry(*C.File, Sym);
 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
return1;
 }
return0;
}

// Notes about General Dynamic and Local Dynamic TLS models below. They may
// require the generation of a pair of GOT entries that have associated dynamic
// relocations. The pair of GOT entries created are of the form GOT[e0] Module
// Index (Used to find pointer to TLS block at run-time) GOT[e1] Offset of
// symbol in TLS block.
//
// Returns the number of relocations processed.
template <classELFT>
staticunsigned
handleTlsRelocation(RelType Type, Symbol &Sym, InputSectionBase &C,
typename ELFT::uint Offset, int64_t Addend, RelExpr Expr) {
if (!Sym.isTls())
return0;

if (Config->EMachine == EM_MIPS)
returnhandleMipsTlsRelocation(Type, Sym, C, Offset, Addend, Expr);

if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC>(
 Expr) &&
 Config->Shared) {
if (In.Got->addDynTlsEntry(Sym)) {
uint64_t Off = In.Got->getGlobalDynOffset(Sym);
 Main->RelaDyn->addReloc(
 {Target->TlsDescRel, In.Got, Off, !Sym.IsPreemptible, &Sym, 0});
 }
if (Expr != R_TLSDESC_CALL)
 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
return1;
 }

bool CanRelax = Config->EMachine != EM_ARM;

// If we are producing an executable and the symbol is non-preemptable, it
// must be defined and the code sequence can be relaxed to use Local-Exec.
//
// ARM and RISC-V do not support any relaxations for TLS relocations, however,
// we can omit the DTPMOD dynamic relocations and resolve them at link time
// because them are always 1. This may be necessary for static linking as
// DTPMOD may not be expected at load time.
bool IsLocalInExecutable = !Sym.IsPreemptible && !Config->Shared;

// Local Dynamic is for access to module local TLS variables, while still
// being suitable for being dynamically loaded via dlopen. GOT[e0] is the
// module index, with a special value of 0 for the current module. GOT[e1] is
// unused. There only needs to be one module index entry.
if (oneof<R_TLSLD_GOT, R_TLSLD_GOTPLT, R_TLSLD_PC, R_TLSLD_HINT>(
 Expr)) {
// Local-Dynamic relocs can be relaxed to Local-Exec.
if (CanRelax && !Config->Shared) {
 C.Relocations.push_back(
 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_LD_TO_LE), Type,
 Offset, Addend, &Sym});
return Target->getTlsGdRelaxSkip(Type);
 }
if (Expr == R_TLSLD_HINT)
return1;
if (In.Got->addTlsIndex()) {
if (IsLocalInExecutable)
 In.Got->Relocations.push_back(
 {R_ADDEND, Target->SymbolicRel, In.Got->getTlsIndexOff(), 1, &Sym});
else
 Main->RelaDyn->addReloc(Target->TlsModuleIndexRel, In.Got,
 In.Got->getTlsIndexOff(), nullptr);
 }
 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
return1;
 }

// Local-Dynamic relocs can be relaxed to Local-Exec.
if (Expr == R_DTPREL && !Config->Shared) {
 C.Relocations.push_back(
 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_LD_TO_LE), Type,
 Offset, Addend, &Sym});
return1;
 }

// Local-Dynamic sequence where offset of tls variable relative to dynamic
// thread pointer is stored in the got. This cannot be relaxed to Local-Exec.
if (Expr == R_TLSLD_GOT_OFF) {
if (!Sym.isInGot()) {
 In.Got->addEntry(Sym);
uint64_t Off = Sym.getGotOffset();
 In.Got->Relocations.push_back(
 {R_ABS, Target->TlsOffsetRel, Off, 0, &Sym});
 }
 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
return1;
 }

if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC,
 R_TLSGD_GOT, R_TLSGD_GOTPLT, R_TLSGD_PC>(Expr)) {
if (!CanRelax || Config->Shared) {
if (In.Got->addDynTlsEntry(Sym)) {
uint64_t Off = In.Got->getGlobalDynOffset(Sym);

if (IsLocalInExecutable)
// Write one to the GOT slot.
 In.Got->Relocations.push_back(
 {R_ADDEND, Target->SymbolicRel, Off, 1, &Sym});
else
 Main->RelaDyn->addReloc(Target->TlsModuleIndexRel, In.Got, Off, &Sym);

// If the symbol is preemptible we need the dynamic linker to write
// the offset too.
uint64_t OffsetOff = Off + Config->Wordsize;
if (Sym.IsPreemptible)
 Main->RelaDyn->addReloc(Target->TlsOffsetRel, In.Got, OffsetOff,
 &Sym);
else
 In.Got->Relocations.push_back(
 {R_ABS, Target->TlsOffsetRel, OffsetOff, 0, &Sym});
 }
 C.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
return1;
 }

// Global-Dynamic relocs can be relaxed to Initial-Exec or Local-Exec
// depending on the symbol being locally defined or not.
if (Sym.IsPreemptible) {
 C.Relocations.push_back(
 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_GD_TO_IE), Type,
 Offset, Addend, &Sym});
if (!Sym.isInGot()) {
 In.Got->addEntry(Sym);
 Main->RelaDyn->addReloc(Target->TlsGotRel, In.Got, Sym.getGotOffset(),
 &Sym);
 }
 } else {
 C.Relocations.push_back(
 {Target->adjustRelaxExpr(Type, nullptr, R_RELAX_TLS_GD_TO_LE), Type,
 Offset, Addend, &Sym});
 }
return Target->getTlsGdRelaxSkip(Type);
 }

// Initial-Exec relocs can be relaxed to Local-Exec if the symbol is locally
// defined.
if (oneof<R_GOT, R_GOTPLT, R_GOT_PC, R_AARCH64_GOT_PAGE_PC, R_GOT_OFF,
 R_TLSIE_HINT>(Expr) &&
 CanRelax && IsLocalInExecutable) {
 C.Relocations.push_back({R_RELAX_TLS_IE_TO_LE, Type, Offset, Addend, &Sym});
return1;
 }

if (Expr == R_TLSIE_HINT)
return1;
return0;
}

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.isUndefWeak())
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_PC, R_PPC32_PLTREL, R_PPC64_CALL_PLT, R_PLT>(Expr);
}

// Returns true if Expr refers a GOT entry. Note that this function
// returns false for TLS variables even though they need GOT, because
// TLS variables uses GOT differently than the regular variables.
staticboolneedsGot(RelExpr Expr) {
return oneof<R_GOT, R_GOT_OFF, R_HEXAGON_GOT, R_MIPS_GOT_LOCAL_PAGE,
 R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_AARCH64_GOT_PAGE_PC,
 R_GOT_PC, R_GOTPLT>(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, R_MIPS_GOTREL, R_PPC64_CALL,
 R_PPC64_RELAX_TOC, R_AARCH64_PAGE_PC, R_RELAX_GOT_PC,
 R_RISCV_PC_INDIRECT>(Expr);
}

// Returns true if a given relocation can be computed at link-time.
//
// 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.
staticboolisStaticLinkTimeConstant(RelExpr E, RelType Type, const Symbol &Sym,
 InputSectionBase &S, uint64_t RelOff) {
// These expressions always compute a constant
if (oneof<R_DTPREL, R_GOTPLT, R_GOT_OFF, R_HEXAGON_GOT, R_TLSLD_GOT_OFF,
 R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOTREL, R_MIPS_GOT_OFF,
 R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC, R_MIPS_TLSGD,
 R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC, R_GOTPLTONLY_PC,
 R_PLT_PC, R_TLSGD_GOT, R_TLSGD_GOTPLT, R_TLSGD_PC, R_PPC32_PLTREL,
 R_PPC64_CALL_PLT, R_PPC64_RELAX_TOC, R_RISCV_ADD, R_TLSDESC_CALL,
 R_TLSDESC_PC, R_AARCH64_TLSDESC_PAGE, R_HINT, R_TLSLD_HINT,
 R_TLSIE_HINT>(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 || E == R_TLSDESC)
return Target->usesOnlyLowPageBits(Type) || !Config->Pic;

if (Sym.IsPreemptible)
returnfalse;
if (!Config->Pic)
returntrue;

// The size of a non preemptible symbol is a constant.
if (E == R_SIZE)
returntrue;

// For the target and the relocation, we want to know if they are
// absolute or relative.
bool AbsVal = isAbsoluteValue(Sym);
bool RelE = isRelExpr(E);
if (AbsVal && !RelE)
returntrue;
if (!AbsVal && RelE)
returntrue;
if (!AbsVal && !RelE)
return Target->usesOnlyLowPageBits(Type);

// Relative relocation to an absolute value. This is normally unrepresentable,
// but if the relocation refers to a weak undefined symbol, we allow it to
// resolve to the image base. This is a little strange, but it allows us to
// link function calls to such symbols. Normally such a call will be guarded
// with a comparison, which will load a zero from the GOT.
// Another special case is MIPS _gp_disp symbol which represents offset
// between start of a function and '_gp' value and defined as absolute just
// to simplify the code.
assert(AbsVal && RelE);
if (Sym.isUndefWeak())
returntrue;

// We set the final symbols values for linker script defined symbols later.
// They always can be computed as a link time constant.
if (Sym.ScriptDefined)
returntrue;

error("relocation " + toString(Type) + " cannot refer to absolute symbol: " +
toString(Sym) + getLocation(S, Sym, RelOff));
returntrue;
}

static RelExpr toPlt(RelExpr Expr) {
switch (Expr) {
case R_PPC64_CALL:
return R_PPC64_CALL_PLT;
case R_PC:
return R_PLT_PC;
case R_ABS:
return R_PLT;
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 R_PPC32_PLTREL:
return R_PC;
case R_PPC64_CALL_PLT:
return R_PPC64_CALL;
case R_PLT:
return R_ABS;
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.
const SharedFile &File = SS.getFile();
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(SharedSymbol &SS) {
using Elf_Sym = typename ELFT::Sym;

 SharedFile &File = SS.getFile();

 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 = Symtab->find(Name);
if (auto *Alias = dyn_cast_or_null<SharedSymbol>(Sym))
 Ret.insert(Alias);
 }
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(Symbol &Sym, SectionBase *Sec, uint64_t Value,
uint64_tSize) {
 Symbol Old = Sym;

 Sym.replace(Defined{Sym.File, Sym.getName(), Sym.Binding, Sym.StOther,
 Sym.Type, Value, Size, Sec});

 Sym.PltIndex = Old.PltIndex;
 Sym.GotIndex = Old.GotIndex;
 Sym.VerdefIndex = Old.VerdefIndex;
 Sym.PPC64BranchltIndex = Old.PPC64BranchltIndex;
 Sym.IsPreemptible = true;
 Sym.ExportDynamic = true;
 Sym.IsUsedInRegularObj = true;
 Sym.Used = true;
}

// 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 informtion 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 varaible V from a DSO,
// define an accessor getV().
template <classELFT> staticvoidaddCopyRelSymbol(SharedSymbol &SS) {
// Copy relocation against zero-sized symbol doesn't make sense.
uint64_t SymSize = SS.getSize();
if (SymSize == 0 || SS.Alignment == 0)
fatal("cannot create a copy relocation for symbol " + toString(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 IsReadOnly = isReadOnly<ELFT>(SS);
 BssSection *Sec = make<BssSection>(IsReadOnly ? ".bss.rel.ro" : ".bss",
 SymSize, SS.Alignment);
if (IsReadOnly)
 In.BssRelRo->getParent()->addSection(Sec);
else
 In.Bss->getParent()->addSection(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>(SS))
replaceWithDefined(*Sym, Sec, 0, Sym->Size);

 Main->RelaDyn->addReloc(Target->CopyRel, Sec, 0, &SS);
}

// 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>
staticint64_tcomputeMipsAddend(const RelTy &Rel, const RelTy *End,
 InputSectionBase &Sec, RelExpr Expr,
bool IsLocal) {
if (Expr == R_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
if (RelTy::IsRela)
return0;

 RelType Type = Rel.getType(Config->IsMips64EL);
uint32_t PairTy = getMipsPairType(Type, IsLocal);
if (PairTy == R_MIPS_NONE)
return0;

constuint8_t *Buf = Sec.data().data();
uint32_t SymIndex = Rel.getSymbol(Config->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 != End; ++RI)
if (RI->getType(Config->IsMips64EL) == PairTy &&
 RI->getSymbol(Config->IsMips64EL) == SymIndex)
return Target->getImplicitAddend(Buf + RI->r_offset, PairTy);

warn("can't find matching " + toString(PairTy) + " relocation for " +
toString(Type));
return0;
}

// Returns an addend of a given relocation. If it is RELA, an addend
// is in a relocation itself. If it is REL, we need to read it from an
// input section.
template <classELFT, classRelTy>
staticint64_tcomputeAddend(const RelTy &Rel, const RelTy *End,
 InputSectionBase &Sec, RelExpr Expr,
bool IsLocal) {
int64_t Addend;
 RelType Type = Rel.getType(Config->IsMips64EL);

if (RelTy::IsRela) {
 Addend = getAddend<ELFT>(Rel);
 } else {
constuint8_t *Buf = Sec.data().data();
 Addend = Target->getImplicitAddend(Buf + Rel.r_offset, Type);
 }

if (Config->EMachine == EM_PPC64 && Config->Pic && Type == R_PPC64_TOC)
 Addend += getPPC64TocBase();
if (Config->EMachine == EM_MIPS)
 Addend += computeMipsAddend<ELFT>(Rel, End, Sec, Expr, IsLocal);

return Addend;
}

// Custom error message if Sym is defined in a discarded section.
template <classELFT>
static std::string maybeReportDiscarded(Undefined &Sym) {
auto *File = dyn_cast_or_null<ObjFile<ELFT>>(Sym.File);
if (!File || !Sym.DiscardedSecIdx ||
 File->getSections()[Sym.DiscardedSecIdx] != &InputSection::Discarded)
return"";
 ArrayRef<Elf_Shdr_Impl<ELFT>> ObjSections =
CHECK(File->getObj().sections(), File);

 std::string Msg;
if (Sym.Type == ELF::STT_SECTION) {
 Msg = "relocation refers to a discarded section: ";
 Msg += CHECK(
 File->getObj().getSectionName(&ObjSections[Sym.DiscardedSecIdx]), File);
 } else {
 Msg = "relocation refers to a symbol in a discarded section: " +
toString(Sym);
 }
 Msg += "\n>>> defined in " + toString(File);

 Elf_Shdr_Impl<ELFT> ELFSec = ObjSections[Sym.DiscardedSecIdx - 1];
if (ELFSec.sh_type != SHT_GROUP)
return Msg;

// If the discarded section is a COMDAT.
 StringRef Signature = File->getShtGroupSignature(ObjSections, ELFSec);
if (const InputFile *Prevailing =
 Symtab->ComdatGroups.lookup(CachedHashStringRef(Signature)))
 Msg += "\n>>> section group signature: " + Signature.str() +
"\n>>> prevailing definition is in " + toString(Prevailing);
return Msg;
}

// Undefined diagnostics are collected in a vector and emitted once all of
// them are known, so that some postprocessing on the list of undefined symbols
// can happen before lld emits diagnostics.
structUndefinedDiag {
 Symbol *Sym;
structLoc {
 InputSectionBase *Sec;
uint64_t Offset;
 };
 std::vector<Loc> Locs;
bool IsWarning;
};

static std::vector<UndefinedDiag> Undefs;

template <classELFT>
staticvoidreportUndefinedSymbol(const UndefinedDiag &Undef) {
 Symbol &Sym = *Undef.Sym;

auto Visibility = [&]() -> std::string {
switch (Sym.Visibility) {
case STV_INTERNAL:
return"internal ";
case STV_HIDDEN:
return"hidden ";
case STV_PROTECTED:
return"protected ";
default:
return"";
 }
 };

 std::string Msg = maybeReportDiscarded<ELFT>(cast<Undefined>(Sym));
if (Msg.empty())
 Msg = "undefined " + Visibility() + "symbol: " + toString(Sym);

constsize_t MaxUndefReferences = 10;
size_t I = 0;
for (UndefinedDiag::Loc L : Undef.Locs) {
if (I >= MaxUndefReferences)
break;
 InputSectionBase &Sec = *L.Sec;
uint64_t Offset = L.Offset;

 Msg += "\n>>> referenced by ";
 std::string Src = Sec.getSrcMsg(Sym, Offset);
if (!Src.empty())
 Msg += Src + "\n>>> ";
 Msg += Sec.getObjMsg(Offset);
 I++;
 }

if (I < Undef.Locs.size())
 Msg += ("\n>>> referenced " + Twine(Undef.Locs.size() - I) + " more times")
 .str();

if (Sym.getName().startswith("_ZTV"))
 Msg += "\nthe vtable symbol may be undefined because the class is missing "
"its key function (see https://lld.llvm.org/missingkeyfunction)";

if (Undef.IsWarning)
warn(Msg);
else
error(Msg);
}

template <classELFT> voidelf::reportUndefinedSymbols() {
// 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 : Undefs) {
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;
 }

for (const UndefinedDiag &Undef : Undefs) {
if (!Undef.Locs.empty())
 reportUndefinedSymbol<ELFT>(Undef);
 }
 Undefs.clear();
}

// Report an undefined symbol if necessary.
// Returns true if the undefined symbol will produce an error message.
template <classELFT>
staticboolmaybeReportUndefined(Symbol &Sym, InputSectionBase &Sec,
uint64_t Offset) {
if (!Sym.isUndefined() || Sym.isWeak())
returnfalse;

bool CanBeExternal = !Sym.isLocal() && Sym.computeBinding() != STB_LOCAL &&
 Sym.Visibility == STV_DEFAULT;
if (Config->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.
if (Config->EMachine == EM_PPC64 &&
 cast<Undefined>(Sym).DiscardedSecIdx != 0 && Sec.Name == ".toc")
returnfalse;

bool IsWarning =
 (Config->UnresolvedSymbols == UnresolvedPolicy::Warn && CanBeExternal) ||
 Config->NoinhibitExec;
 Undefs.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> static RelType getMipsN32RelType(RelTy *&Rel, RelTy *End) {
 RelType Type = 0;
uint64_t Offset = Rel->r_offset;

int N = 0;
while (Rel != End && Rel->r_offset == Offset)
 Type |= (Rel++)->getType(Config->IsMips64EL) << (8 * N++);
return Type;
}

// .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:
explicitOffsetGetter(InputSectionBase &Sec) {
if (auto *Eh = dyn_cast<EhInputSection>(&Sec))
 Pieces = Eh->Pieces;
 }

// 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(uint64_t Off) {
if (Pieces.empty())
return Off;

while (I != Pieces.size() && Pieces[I].InputOff + Pieces[I].Size <= Off)
 ++I;
if (I == Pieces.size())
fatal(".eh_frame: relocation is not in any piece");

// Pieces must be contiguous, so there must be no holes in between.
assert(Pieces[I].InputOff <= Off && "Relocation not in any piece");

// Offset -1 means that the piece is dead (i.e. garbage collected).
if (Pieces[I].OutputOff == -1)
return -1;
return Pieces[I].OutputOff + Off - Pieces[I].InputOff;
 }

private:
 ArrayRef<EhSectionPiece> Pieces;
size_t I = 0;
};
} // namespace

staticvoidaddRelativeReloc(InputSectionBase *IS, uint64_t OffsetInSec,
 Symbol *Sym, int64_t Addend, RelExpr Expr,
 RelType Type) {
 Partition &Part = IS->getPartition();

// 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 && IS->Alignment >= 2 && OffsetInSec % 2 == 0) {
 IS->Relocations.push_back({Expr, Type, OffsetInSec, Addend, Sym});
 Part.RelrDyn->Relocs.push_back({IS, OffsetInSec});
return;
 }
 Part.RelaDyn->addReloc(Target->RelativeRel, IS, OffsetInSec, Sym, Addend,
 Expr, Type);
}

template <classELFT, classGotPltSection>
staticvoidaddPltEntry(PltSection *Plt, GotPltSection *GotPlt,
 RelocationBaseSection *Rel, RelType Type, Symbol &Sym) {
 Plt->addEntry<ELFT>(Sym);
 GotPlt->addEntry(Sym);
 Rel->addReloc(
 {Type, GotPlt, Sym.getGotPltOffset(), !Sym.IsPreemptible, &Sym, 0});
}

staticvoidaddGotEntry(Symbol &Sym) {
 In.Got->addEntry(Sym);

 RelExpr Expr = Sym.isTls() ? R_TLS : R_ABS;
uint64_t Off = Sym.getGotOffset();

// If a GOT slot value can be calculated at link-time, which is now,
// we can just fill that out.
//
// (We don't actually write a value to a GOT slot right now, but we
// add a static relocation to a Relocations vector so that
// InputSection::relocate will do the work for us. We may be able
// to just write a value now, but it is a TODO.)
bool IsLinkTimeConstant =
 !Sym.IsPreemptible && (!Config->Pic || isAbsolute(Sym));
if (IsLinkTimeConstant) {
 In.Got->Relocations.push_back({Expr, Target->SymbolicRel, Off, 0, &Sym});
return;
 }

// Otherwise, we emit a dynamic relocation to .rel[a].dyn so that
// the GOT slot will be fixed at load-time.
if (!Sym.isTls() && !Sym.IsPreemptible && Config->Pic && !isAbsolute(Sym)) {
addRelativeReloc(In.Got, Off, &Sym, 0, R_ABS, Target->SymbolicRel);
return;
 }
 Main->RelaDyn->addReloc(
 Sym.isTls() ? Target->TlsGotRel : Target->GotRel, In.Got, Off, &Sym, 0,
 Sym.IsPreemptible ? R_ADDEND : R_ABS, 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(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. That is
// why we use Sym.StOther.
if ((Sym.StOther & 0x3) == STV_DEFAULT)
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() && Config->IgnoreFunctionAddressEquality) ||
 (Sym.isObject() && Config->IgnoreDataAddressEquality));
}

// The reason we have to do this early scan is as follows
// * To mmap the output file, we need to know the size
// * For that, we need to know how many dynamic relocs we will have.
// It might be possible to avoid this by outputting the file with write:
// * Write the allocated output sections, computing addresses.
// * Apply relocations, recording which ones require a dynamic reloc.
// * Write the dynamic relocations.
// * Write the rest of the file.
// This would have some drawbacks. For example, we would only know if .rela.dyn
// is needed after applying relocations. If it is, it will go after rw and rx
// sections. Given that it is ro, we will need an extra PT_LOAD. This
// complicates things for the dynamic linker and means we would have to reserve
// space for the extra PT_LOAD even if we end up not using it.
template <classELFT, classRelTy>
staticvoidprocessRelocAux(InputSectionBase &Sec, RelExpr Expr, RelType Type,
uint64_t Offset, Symbol &Sym, const RelTy &Rel,
int64_t Addend) {
// If the relocation is known to be a link-time constant, we know no dynamic
// relocation will be created, pass the control to relocateAlloc() or
// relocateNonAlloc() to resolve it.
//
// The behavior of an undefined weak reference is implementation defined. If
// the relocation is to a weak undef, and we are producing an executable, let
// relocate{,Non}Alloc() resolve it.
if (isStaticLinkTimeConstant(Expr, Type, Sym, Sec, Offset) ||
 (!Config->Shared && Sym.isUndefWeak())) {
 Sec.Relocations.push_back({Expr, Type, Offset, Addend, &Sym});
return;
 }

bool CanWrite = (Sec.Flags & SHF_WRITE) || !Config->ZText;
if (CanWrite) {
 RelType Rel = Target->getDynRel(Type);
if (Expr == R_GOT || (Rel == Target->SymbolicRel && !Sym.IsPreemptible)) {
addRelativeReloc(&Sec, Offset, &Sym, Addend, Expr, Type);
return;
 } elseif (Rel != 0) {
if (Config->EMachine == EM_MIPS && Rel == Target->SymbolicRel)
 Rel = Target->RelativeRel;
 Sec.getPartition().RelaDyn->addReloc(Rel, &Sec, Offset, &Sym, Addend,
 R_ADDEND, Type);

// MIPS ABI turns using of GOT and dynamic relocations inside out.
// While regular ABI uses dynamic relocations to fill up GOT entries
// MIPS ABI requires dynamic linker to fills up GOT entries using
// specially sorted dynamic symbol table. This affects even dynamic
// relocations against symbols which do not require GOT entries
// creation explicitly, i.e. do not have any GOT-relocations. So if
// a preemptible symbol has a dynamic relocation we anyway have
// to create a GOT entry for it.
// If a non-preemptible symbol has a dynamic relocation against it,
// dynamic linker takes it st_value, adds offset and writes down
// result of the dynamic relocation. In case of preemptible symbol
// dynamic linker performs symbol resolution, writes the symbol value
// to the GOT entry and reads the GOT entry when it needs to perform
// a dynamic relocation.
// ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf p.4-19
if (Config->EMachine == EM_MIPS)
 In.MipsGot->addEntry(*Sec.File, Sym, Addend, Expr);
return;
 }
 }

if (!CanWrite && (Config->Pic && !isRelExpr(Expr))) {