1303239Sdim//===- Relocations.cpp ----------------------------------------------------===// 2303239Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6303239Sdim// 7303239Sdim//===----------------------------------------------------------------------===// 8303239Sdim// 9303239Sdim// This file contains platform-independent functions to process relocations. 10303239Sdim// I'll describe the overview of this file here. 11303239Sdim// 12303239Sdim// Simple relocations are easy to handle for the linker. For example, 13303239Sdim// for R_X86_64_PC64 relocs, the linker just has to fix up locations 14303239Sdim// with the relative offsets to the target symbols. It would just be 15303239Sdim// reading records from relocation sections and applying them to output. 16303239Sdim// 17303239Sdim// But not all relocations are that easy to handle. For example, for 18303239Sdim// R_386_GOTOFF relocs, the linker has to create new GOT entries for 19303239Sdim// symbols if they don't exist, and fix up locations with GOT entry 20303239Sdim// offsets from the beginning of GOT section. So there is more than 21303239Sdim// fixing addresses in relocation processing. 22303239Sdim// 23303239Sdim// ELF defines a large number of complex relocations. 24303239Sdim// 25303239Sdim// The functions in this file analyze relocations and do whatever needs 26303239Sdim// to be done. It includes, but not limited to, the following. 27303239Sdim// 28303239Sdim// - create GOT/PLT entries 29303239Sdim// - create new relocations in .dynsym to let the dynamic linker resolve 30303239Sdim// them at runtime (since ELF supports dynamic linking, not all 31303239Sdim// relocations can be resolved at link-time) 32303239Sdim// - create COPY relocs and reserve space in .bss 33303239Sdim// - replace expensive relocs (in terms of runtime cost) with cheap ones 34303239Sdim// - error out infeasible combinations such as PIC and non-relative relocs 35303239Sdim// 36303239Sdim// Note that the functions in this file don't actually apply relocations 37303239Sdim// because it doesn't know about the output file nor the output file buffer. 38303239Sdim// It instead stores Relocation objects to InputSection's Relocations 39303239Sdim// vector to let it apply later in InputSection::writeTo. 40303239Sdim// 41303239Sdim//===----------------------------------------------------------------------===// 42303239Sdim 43303239Sdim#include "Relocations.h" 44303239Sdim#include "Config.h" 45321369Sdim#include "LinkerScript.h" 46303239Sdim#include "OutputSections.h" 47303239Sdim#include "SymbolTable.h" 48327952Sdim#include "Symbols.h" 49314564Sdim#include "SyntheticSections.h" 50303239Sdim#include "Target.h" 51303239Sdim#include "Thunks.h" 52344779Sdim#include "lld/Common/ErrorHandler.h" 53327952Sdim#include "lld/Common/Memory.h" 54341825Sdim#include "lld/Common/Strings.h" 55341825Sdim#include "llvm/ADT/SmallSet.h" 56360784Sdim#include "llvm/Demangle/Demangle.h" 57303239Sdim#include "llvm/Support/Endian.h" 58303239Sdim#include "llvm/Support/raw_ostream.h" 59321369Sdim#include <algorithm> 60303239Sdim 61303239Sdimusing namespace llvm; 62303239Sdimusing namespace llvm::ELF; 63303239Sdimusing namespace llvm::object; 64303239Sdimusing namespace llvm::support::endian; 65303239Sdim 66360784Sdimnamespace lld { 67360784Sdimnamespace elf { 68353358Sdimstatic Optional<std::string> getLinkerScriptLocation(const Symbol &sym) { 69353358Sdim for (BaseCommand *base : script->sectionCommands) 70353358Sdim if (auto *cmd = dyn_cast<SymbolAssignment>(base)) 71353358Sdim if (cmd->sym == &sym) 72353358Sdim return cmd->location; 73344779Sdim return None; 74344779Sdim} 75344779Sdim 76321369Sdim// Construct a message in the following format. 77321369Sdim// 78321369Sdim// >>> defined in /home/alice/src/foo.o 79321369Sdim// >>> referenced by bar.c:12 (/home/alice/src/bar.c:12) 80321369Sdim// >>> /home/alice/src/bar.o:(.text+0x1) 81353358Sdimstatic std::string getLocation(InputSectionBase &s, const Symbol &sym, 82353358Sdim uint64_t off) { 83353358Sdim std::string msg = "\n>>> defined in "; 84353358Sdim if (sym.file) 85353358Sdim msg += toString(sym.file); 86353358Sdim else if (Optional<std::string> loc = getLinkerScriptLocation(sym)) 87353358Sdim msg += *loc; 88344779Sdim 89353358Sdim msg += "\n>>> referenced by "; 90353358Sdim std::string src = s.getSrcMsg(sym, off); 91353358Sdim if (!src.empty()) 92353358Sdim msg += src + "\n>>> "; 93353358Sdim return msg + s.getObjMsg(off); 94303239Sdim} 95303239Sdim 96353358Sdimnamespace { 97353358Sdim// Build a bitmask with one bit set for each RelExpr. 98353358Sdim// 99353358Sdim// Constexpr function arguments can't be used in static asserts, so we 100353358Sdim// use template arguments to build the mask. 101353358Sdim// But function template partial specializations don't exist (needed 102353358Sdim// for base case of the recursion), so we need a dummy struct. 103353358Sdimtemplate <RelExpr... Exprs> struct RelExprMaskBuilder { 104353358Sdim static inline uint64_t build() { return 0; } 105353358Sdim}; 106353358Sdim 107353358Sdim// Specialization for recursive case. 108353358Sdimtemplate <RelExpr Head, RelExpr... Tail> 109353358Sdimstruct RelExprMaskBuilder<Head, Tail...> { 110353358Sdim static inline uint64_t build() { 111353358Sdim static_assert(0 <= Head && Head < 64, 112353358Sdim "RelExpr is too large for 64-bit mask!"); 113353358Sdim return (uint64_t(1) << Head) | RelExprMaskBuilder<Tail...>::build(); 114353358Sdim } 115353358Sdim}; 116353358Sdim} // namespace 117353358Sdim 118353358Sdim// Return true if `Expr` is one of `Exprs`. 119353358Sdim// There are fewer than 64 RelExpr's, so we can represent any set of 120353358Sdim// RelExpr's as a constant bit mask and test for membership with a 121353358Sdim// couple cheap bitwise operations. 122353358Sdimtemplate <RelExpr... Exprs> bool oneof(RelExpr expr) { 123353358Sdim assert(0 <= expr && (int)expr < 64 && 124353358Sdim "RelExpr is too large for 64-bit mask!"); 125353358Sdim return (uint64_t(1) << expr) & RelExprMaskBuilder<Exprs...>::build(); 126353358Sdim} 127353358Sdim 128321369Sdim// This function is similar to the `handleTlsRelocation`. MIPS does not 129321369Sdim// support any relaxations for TLS relocations so by factoring out MIPS 130314564Sdim// handling in to the separate function we can simplify the code and do not 131321369Sdim// pollute other `handleTlsRelocation` by MIPS `ifs` statements. 132321369Sdim// Mips has a custom MipsGotSection that handles the writing of GOT entries 133321369Sdim// without dynamic relocations. 134353358Sdimstatic unsigned handleMipsTlsRelocation(RelType type, Symbol &sym, 135353358Sdim InputSectionBase &c, uint64_t offset, 136353358Sdim int64_t addend, RelExpr expr) { 137353358Sdim if (expr == R_MIPS_TLSLD) { 138353358Sdim in.mipsGot->addTlsIndex(*c.file); 139353358Sdim c.relocations.push_back({expr, type, offset, addend, &sym}); 140321369Sdim return 1; 141321369Sdim } 142353358Sdim if (expr == R_MIPS_TLSGD) { 143353358Sdim in.mipsGot->addDynTlsEntry(*c.file, sym); 144353358Sdim c.relocations.push_back({expr, type, offset, addend, &sym}); 145321369Sdim return 1; 146321369Sdim } 147321369Sdim return 0; 148321369Sdim} 149321369Sdim 150353358Sdim// Notes about General Dynamic and Local Dynamic TLS models below. They may 151353358Sdim// require the generation of a pair of GOT entries that have associated dynamic 152353358Sdim// relocations. The pair of GOT entries created are of the form GOT[e0] Module 153353358Sdim// Index (Used to find pointer to TLS block at run-time) GOT[e1] Offset of 154353358Sdim// symbol in TLS block. 155321369Sdim// 156303239Sdim// Returns the number of relocations processed. 157303239Sdimtemplate <class ELFT> 158321369Sdimstatic unsigned 159353358SdimhandleTlsRelocation(RelType type, Symbol &sym, InputSectionBase &c, 160353358Sdim typename ELFT::uint offset, int64_t addend, RelExpr expr) { 161353358Sdim if (!sym.isTls()) 162303239Sdim return 0; 163303239Sdim 164353358Sdim if (config->emachine == EM_MIPS) 165353358Sdim return handleMipsTlsRelocation(type, sym, c, offset, addend, expr); 166303239Sdim 167353358Sdim if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC>( 168353358Sdim expr) && 169353358Sdim config->shared) { 170353358Sdim if (in.got->addDynTlsEntry(sym)) { 171353358Sdim uint64_t off = in.got->getGlobalDynOffset(sym); 172353358Sdim mainPart->relaDyn->addReloc( 173353358Sdim {target->tlsDescRel, in.got, off, !sym.isPreemptible, &sym, 0}); 174303239Sdim } 175353358Sdim if (expr != R_TLSDESC_CALL) 176353358Sdim c.relocations.push_back({expr, type, offset, addend, &sym}); 177303239Sdim return 1; 178303239Sdim } 179303239Sdim 180360784Sdim bool canRelax = config->emachine != EM_ARM && 181360784Sdim config->emachine != EM_HEXAGON && 182360784Sdim config->emachine != EM_RISCV; 183353358Sdim 184353358Sdim // If we are producing an executable and the symbol is non-preemptable, it 185353358Sdim // must be defined and the code sequence can be relaxed to use Local-Exec. 186353358Sdim // 187353358Sdim // ARM and RISC-V do not support any relaxations for TLS relocations, however, 188353358Sdim // we can omit the DTPMOD dynamic relocations and resolve them at link time 189353358Sdim // because them are always 1. This may be necessary for static linking as 190353358Sdim // DTPMOD may not be expected at load time. 191353358Sdim bool isLocalInExecutable = !sym.isPreemptible && !config->shared; 192353358Sdim 193353358Sdim // Local Dynamic is for access to module local TLS variables, while still 194353358Sdim // being suitable for being dynamically loaded via dlopen. GOT[e0] is the 195353358Sdim // module index, with a special value of 0 for the current module. GOT[e1] is 196353358Sdim // unused. There only needs to be one module index entry. 197353358Sdim if (oneof<R_TLSLD_GOT, R_TLSLD_GOTPLT, R_TLSLD_PC, R_TLSLD_HINT>( 198353358Sdim expr)) { 199303239Sdim // Local-Dynamic relocs can be relaxed to Local-Exec. 200353358Sdim if (canRelax && !config->shared) { 201353358Sdim c.relocations.push_back( 202353358Sdim {target->adjustRelaxExpr(type, nullptr, R_RELAX_TLS_LD_TO_LE), type, 203353358Sdim offset, addend, &sym}); 204353358Sdim return target->getTlsGdRelaxSkip(type); 205303239Sdim } 206353358Sdim if (expr == R_TLSLD_HINT) 207341825Sdim return 1; 208353358Sdim if (in.got->addTlsIndex()) { 209353358Sdim if (isLocalInExecutable) 210353358Sdim in.got->relocations.push_back( 211353358Sdim {R_ADDEND, target->symbolicRel, in.got->getTlsIndexOff(), 1, &sym}); 212353358Sdim else 213353358Sdim mainPart->relaDyn->addReloc(target->tlsModuleIndexRel, in.got, 214353358Sdim in.got->getTlsIndexOff(), nullptr); 215353358Sdim } 216353358Sdim c.relocations.push_back({expr, type, offset, addend, &sym}); 217303239Sdim return 1; 218303239Sdim } 219303239Sdim 220303239Sdim // Local-Dynamic relocs can be relaxed to Local-Exec. 221353358Sdim if (expr == R_DTPREL && !config->shared) { 222353358Sdim c.relocations.push_back( 223353358Sdim {target->adjustRelaxExpr(type, nullptr, R_RELAX_TLS_LD_TO_LE), type, 224353358Sdim offset, addend, &sym}); 225303239Sdim return 1; 226303239Sdim } 227303239Sdim 228341825Sdim // Local-Dynamic sequence where offset of tls variable relative to dynamic 229353358Sdim // thread pointer is stored in the got. This cannot be relaxed to Local-Exec. 230353358Sdim if (expr == R_TLSLD_GOT_OFF) { 231353358Sdim if (!sym.isInGot()) { 232353358Sdim in.got->addEntry(sym); 233353358Sdim uint64_t off = sym.getGotOffset(); 234353358Sdim in.got->relocations.push_back( 235353358Sdim {R_ABS, target->tlsOffsetRel, off, 0, &sym}); 236341825Sdim } 237353358Sdim c.relocations.push_back({expr, type, offset, addend, &sym}); 238341825Sdim return 1; 239341825Sdim } 240341825Sdim 241353358Sdim if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC, 242353358Sdim R_TLSGD_GOT, R_TLSGD_GOTPLT, R_TLSGD_PC>(expr)) { 243353358Sdim if (!canRelax || config->shared) { 244353358Sdim if (in.got->addDynTlsEntry(sym)) { 245353358Sdim uint64_t off = in.got->getGlobalDynOffset(sym); 246303239Sdim 247353358Sdim if (isLocalInExecutable) 248353358Sdim // Write one to the GOT slot. 249353358Sdim in.got->relocations.push_back( 250353358Sdim {R_ADDEND, target->symbolicRel, off, 1, &sym}); 251353358Sdim else 252353358Sdim mainPart->relaDyn->addReloc(target->tlsModuleIndexRel, in.got, off, &sym); 253353358Sdim 254303239Sdim // If the symbol is preemptible we need the dynamic linker to write 255303239Sdim // the offset too. 256353358Sdim uint64_t offsetOff = off + config->wordsize; 257353358Sdim if (sym.isPreemptible) 258353358Sdim mainPart->relaDyn->addReloc(target->tlsOffsetRel, in.got, offsetOff, 259353358Sdim &sym); 260314564Sdim else 261353358Sdim in.got->relocations.push_back( 262353358Sdim {R_ABS, target->tlsOffsetRel, offsetOff, 0, &sym}); 263303239Sdim } 264353358Sdim c.relocations.push_back({expr, type, offset, addend, &sym}); 265303239Sdim return 1; 266303239Sdim } 267303239Sdim 268303239Sdim // Global-Dynamic relocs can be relaxed to Initial-Exec or Local-Exec 269303239Sdim // depending on the symbol being locally defined or not. 270353358Sdim if (sym.isPreemptible) { 271353358Sdim c.relocations.push_back( 272353358Sdim {target->adjustRelaxExpr(type, nullptr, R_RELAX_TLS_GD_TO_IE), type, 273353358Sdim offset, addend, &sym}); 274353358Sdim if (!sym.isInGot()) { 275353358Sdim in.got->addEntry(sym); 276353358Sdim mainPart->relaDyn->addReloc(target->tlsGotRel, in.got, sym.getGotOffset(), 277353358Sdim &sym); 278303239Sdim } 279321369Sdim } else { 280353358Sdim c.relocations.push_back( 281353358Sdim {target->adjustRelaxExpr(type, nullptr, R_RELAX_TLS_GD_TO_LE), type, 282353358Sdim offset, addend, &sym}); 283303239Sdim } 284353358Sdim return target->getTlsGdRelaxSkip(type); 285303239Sdim } 286303239Sdim 287303239Sdim // Initial-Exec relocs can be relaxed to Local-Exec if the symbol is locally 288303239Sdim // defined. 289353358Sdim if (oneof<R_GOT, R_GOTPLT, R_GOT_PC, R_AARCH64_GOT_PAGE_PC, R_GOT_OFF, 290353358Sdim R_TLSIE_HINT>(expr) && 291353358Sdim canRelax && isLocalInExecutable) { 292353358Sdim c.relocations.push_back({R_RELAX_TLS_IE_TO_LE, type, offset, addend, &sym}); 293303239Sdim return 1; 294303239Sdim } 295321369Sdim 296353358Sdim if (expr == R_TLSIE_HINT) 297321369Sdim return 1; 298303239Sdim return 0; 299303239Sdim} 300303239Sdim 301353358Sdimstatic RelType getMipsPairType(RelType type, bool isLocal) { 302353358Sdim switch (type) { 303303239Sdim case R_MIPS_HI16: 304303239Sdim return R_MIPS_LO16; 305303239Sdim case R_MIPS_GOT16: 306327952Sdim // In case of global symbol, the R_MIPS_GOT16 relocation does not 307327952Sdim // have a pair. Each global symbol has a unique entry in the GOT 308327952Sdim // and a corresponding instruction with help of the R_MIPS_GOT16 309327952Sdim // relocation loads an address of the symbol. In case of local 310327952Sdim // symbol, the R_MIPS_GOT16 relocation creates a GOT entry to hold 311327952Sdim // the high 16 bits of the symbol's value. A paired R_MIPS_LO16 312327952Sdim // relocations handle low 16 bits of the address. That allows 313327952Sdim // to allocate only one GOT entry for every 64 KBytes of local data. 314353358Sdim return isLocal ? R_MIPS_LO16 : R_MIPS_NONE; 315327952Sdim case R_MICROMIPS_GOT16: 316353358Sdim return isLocal ? R_MICROMIPS_LO16 : R_MIPS_NONE; 317303239Sdim case R_MIPS_PCHI16: 318303239Sdim return R_MIPS_PCLO16; 319303239Sdim case R_MICROMIPS_HI16: 320303239Sdim return R_MICROMIPS_LO16; 321303239Sdim default: 322303239Sdim return R_MIPS_NONE; 323303239Sdim } 324303239Sdim} 325303239Sdim 326303239Sdim// True if non-preemptable symbol always has the same value regardless of where 327303239Sdim// the DSO is loaded. 328353358Sdimstatic bool isAbsolute(const Symbol &sym) { 329353358Sdim if (sym.isUndefWeak()) 330327952Sdim return true; 331353358Sdim if (const auto *dr = dyn_cast<Defined>(&sym)) 332353358Sdim return dr->section == nullptr; // Absolute symbol. 333303239Sdim return false; 334303239Sdim} 335303239Sdim 336353358Sdimstatic bool isAbsoluteValue(const Symbol &sym) { 337353358Sdim return isAbsolute(sym) || sym.isTls(); 338314564Sdim} 339314564Sdim 340321369Sdim// Returns true if Expr refers a PLT entry. 341353358Sdimstatic bool needsPlt(RelExpr expr) { 342353358Sdim return oneof<R_PLT_PC, R_PPC32_PLTREL, R_PPC64_CALL_PLT, R_PLT>(expr); 343303239Sdim} 344303239Sdim 345321369Sdim// Returns true if Expr refers a GOT entry. Note that this function 346321369Sdim// returns false for TLS variables even though they need GOT, because 347321369Sdim// TLS variables uses GOT differently than the regular variables. 348353358Sdimstatic bool needsGot(RelExpr expr) { 349360784Sdim return oneof<R_GOT, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOT_OFF, 350360784Sdim R_MIPS_GOT_OFF32, R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTPLT>( 351360784Sdim expr); 352321369Sdim} 353321369Sdim 354303239Sdim// True if this expression is of the form Sym - X, where X is a position in the 355303239Sdim// file (PC, or GOT for example). 356353358Sdimstatic bool isRelExpr(RelExpr expr) { 357353358Sdim return oneof<R_PC, R_GOTREL, R_GOTPLTREL, R_MIPS_GOTREL, R_PPC64_CALL, 358353358Sdim R_PPC64_RELAX_TOC, R_AARCH64_PAGE_PC, R_RELAX_GOT_PC, 359353358Sdim R_RISCV_PC_INDIRECT>(expr); 360303239Sdim} 361303239Sdim 362321369Sdim// Returns true if a given relocation can be computed at link-time. 363321369Sdim// 364321369Sdim// For instance, we know the offset from a relocation to its target at 365321369Sdim// link-time if the relocation is PC-relative and refers a 366321369Sdim// non-interposable function in the same executable. This function 367321369Sdim// will return true for such relocation. 368321369Sdim// 369321369Sdim// If this function returns false, that means we need to emit a 370321369Sdim// dynamic relocation so that the relocation will be fixed at load-time. 371353358Sdimstatic bool isStaticLinkTimeConstant(RelExpr e, RelType type, const Symbol &sym, 372353358Sdim InputSectionBase &s, uint64_t relOff) { 373303239Sdim // These expressions always compute a constant 374360784Sdim if (oneof<R_DTPREL, R_GOTPLT, R_GOT_OFF, R_TLSLD_GOT_OFF, 375353358Sdim R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOTREL, R_MIPS_GOT_OFF, 376353358Sdim R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC, R_MIPS_TLSGD, 377353358Sdim R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC, R_GOTPLTONLY_PC, 378353358Sdim R_PLT_PC, R_TLSGD_GOT, R_TLSGD_GOTPLT, R_TLSGD_PC, R_PPC32_PLTREL, 379353358Sdim R_PPC64_CALL_PLT, R_PPC64_RELAX_TOC, R_RISCV_ADD, R_TLSDESC_CALL, 380360784Sdim R_TLSDESC_PC, R_AARCH64_TLSDESC_PAGE, R_TLSLD_HINT, R_TLSIE_HINT>( 381360784Sdim e)) 382303239Sdim return true; 383303239Sdim 384303239Sdim // These never do, except if the entire file is position dependent or if 385303239Sdim // only the low bits are used. 386353358Sdim if (e == R_GOT || e == R_PLT || e == R_TLSDESC) 387353358Sdim return target->usesOnlyLowPageBits(type) || !config->isPic; 388303239Sdim 389353358Sdim if (sym.isPreemptible) 390303239Sdim return false; 391353358Sdim if (!config->isPic) 392303239Sdim return true; 393303239Sdim 394327952Sdim // The size of a non preemptible symbol is a constant. 395353358Sdim if (e == R_SIZE) 396327952Sdim return true; 397327952Sdim 398321369Sdim // For the target and the relocation, we want to know if they are 399321369Sdim // absolute or relative. 400353358Sdim bool absVal = isAbsoluteValue(sym); 401353358Sdim bool relE = isRelExpr(e); 402353358Sdim if (absVal && !relE) 403303239Sdim return true; 404353358Sdim if (!absVal && relE) 405303239Sdim return true; 406353358Sdim if (!absVal && !relE) 407353358Sdim return target->usesOnlyLowPageBits(type); 408303239Sdim 409353358Sdim assert(absVal && relE); 410360784Sdim 411360784Sdim // Allow R_PLT_PC (optimized to R_PC here) to a hidden undefined weak symbol 412360784Sdim // in PIC mode. This is a little strange, but it allows us to link function 413360784Sdim // calls to such symbols (e.g. glibc/stdlib/exit.c:__run_exit_handlers). 414360784Sdim // Normally such a call will be guarded with a comparison, which will load a 415360784Sdim // zero from the GOT. 416353358Sdim if (sym.isUndefWeak()) 417303239Sdim return true; 418303239Sdim 419353358Sdim // We set the final symbols values for linker script defined symbols later. 420353358Sdim // They always can be computed as a link time constant. 421353358Sdim if (sym.scriptDefined) 422353358Sdim return true; 423353358Sdim 424353358Sdim error("relocation " + toString(type) + " cannot refer to absolute symbol: " + 425353358Sdim toString(sym) + getLocation(s, sym, relOff)); 426321369Sdim return true; 427303239Sdim} 428303239Sdim 429353358Sdimstatic RelExpr toPlt(RelExpr expr) { 430353358Sdim switch (expr) { 431353358Sdim case R_PPC64_CALL: 432353358Sdim return R_PPC64_CALL_PLT; 433341825Sdim case R_PC: 434303239Sdim return R_PLT_PC; 435341825Sdim case R_ABS: 436303239Sdim return R_PLT; 437341825Sdim default: 438353358Sdim return expr; 439341825Sdim } 440303239Sdim} 441303239Sdim 442353358Sdimstatic RelExpr fromPlt(RelExpr expr) { 443303239Sdim // We decided not to use a plt. Optimize a reference to the plt to a 444303239Sdim // reference to the symbol itself. 445353358Sdim switch (expr) { 446341825Sdim case R_PLT_PC: 447353358Sdim case R_PPC32_PLTREL: 448303239Sdim return R_PC; 449353358Sdim case R_PPC64_CALL_PLT: 450353358Sdim return R_PPC64_CALL; 451341825Sdim case R_PLT: 452303239Sdim return R_ABS; 453341825Sdim default: 454353358Sdim return expr; 455341825Sdim } 456303239Sdim} 457303239Sdim 458321369Sdim// Returns true if a given shared symbol is in a read-only segment in a DSO. 459353358Sdimtemplate <class ELFT> static bool isReadOnly(SharedSymbol &ss) { 460353358Sdim using Elf_Phdr = typename ELFT::Phdr; 461314564Sdim 462314564Sdim // Determine if the symbol is read-only by scanning the DSO's program headers. 463353358Sdim const SharedFile &file = ss.getFile(); 464353358Sdim for (const Elf_Phdr &phdr : 465353358Sdim check(file.template getObj<ELFT>().program_headers())) 466353358Sdim if ((phdr.p_type == ELF::PT_LOAD || phdr.p_type == ELF::PT_GNU_RELRO) && 467353358Sdim !(phdr.p_flags & ELF::PF_W) && ss.value >= phdr.p_vaddr && 468353358Sdim ss.value < phdr.p_vaddr + phdr.p_memsz) 469314564Sdim return true; 470314564Sdim return false; 471314564Sdim} 472314564Sdim 473321369Sdim// Returns symbols at the same offset as a given symbol, including SS itself. 474321369Sdim// 475321369Sdim// If two or more symbols are at the same offset, and at least one of 476321369Sdim// them are copied by a copy relocation, all of them need to be copied. 477341825Sdim// Otherwise, they would refer to different places at runtime. 478321369Sdimtemplate <class ELFT> 479353358Sdimstatic SmallSet<SharedSymbol *, 4> getSymbolsAt(SharedSymbol &ss) { 480353358Sdim using Elf_Sym = typename ELFT::Sym; 481303239Sdim 482353358Sdim SharedFile &file = ss.getFile(); 483321369Sdim 484353358Sdim SmallSet<SharedSymbol *, 4> ret; 485353358Sdim for (const Elf_Sym &s : file.template getGlobalELFSyms<ELFT>()) { 486353358Sdim if (s.st_shndx == SHN_UNDEF || s.st_shndx == SHN_ABS || 487353358Sdim s.getType() == STT_TLS || s.st_value != ss.value) 488321369Sdim continue; 489353358Sdim StringRef name = check(s.getName(file.getStringTable())); 490353358Sdim Symbol *sym = symtab->find(name); 491353358Sdim if (auto *alias = dyn_cast_or_null<SharedSymbol>(sym)) 492353358Sdim ret.insert(alias); 493321369Sdim } 494353358Sdim return ret; 495321369Sdim} 496321369Sdim 497341825Sdim// When a symbol is copy relocated or we create a canonical plt entry, it is 498341825Sdim// effectively a defined symbol. In the case of copy relocation the symbol is 499341825Sdim// in .bss and in the case of a canonical plt entry it is in .plt. This function 500341825Sdim// replaces the existing symbol with a Defined pointing to the appropriate 501341825Sdim// location. 502353358Sdimstatic void replaceWithDefined(Symbol &sym, SectionBase *sec, uint64_t value, 503353358Sdim uint64_t size) { 504353358Sdim Symbol old = sym; 505353358Sdim 506353358Sdim sym.replace(Defined{sym.file, sym.getName(), sym.binding, sym.stOther, 507353358Sdim sym.type, value, size, sec}); 508353358Sdim 509353358Sdim sym.pltIndex = old.pltIndex; 510353358Sdim sym.gotIndex = old.gotIndex; 511353358Sdim sym.verdefIndex = old.verdefIndex; 512353358Sdim sym.exportDynamic = true; 513353358Sdim sym.isUsedInRegularObj = true; 514341825Sdim} 515341825Sdim 516321369Sdim// Reserve space in .bss or .bss.rel.ro for copy relocation. 517321369Sdim// 518321369Sdim// The copy relocation is pretty much a hack. If you use a copy relocation 519321369Sdim// in your program, not only the symbol name but the symbol's size, RW/RO 520321369Sdim// bit and alignment become part of the ABI. In addition to that, if the 521321369Sdim// symbol has aliases, the aliases become part of the ABI. That's subtle, 522321369Sdim// but if you violate that implicit ABI, that can cause very counter- 523321369Sdim// intuitive consequences. 524321369Sdim// 525321369Sdim// So, what is the copy relocation? It's for linking non-position 526321369Sdim// independent code to DSOs. In an ideal world, all references to data 527321369Sdim// exported by DSOs should go indirectly through GOT. But if object files 528321369Sdim// are compiled as non-PIC, all data references are direct. There is no 529321369Sdim// way for the linker to transform the code to use GOT, as machine 530321369Sdim// instructions are already set in stone in object files. This is where 531321369Sdim// the copy relocation takes a role. 532321369Sdim// 533321369Sdim// A copy relocation instructs the dynamic linker to copy data from a DSO 534321369Sdim// to a specified address (which is usually in .bss) at load-time. If the 535321369Sdim// static linker (that's us) finds a direct data reference to a DSO 536321369Sdim// symbol, it creates a copy relocation, so that the symbol can be 537321369Sdim// resolved as if it were in .bss rather than in a DSO. 538321369Sdim// 539321369Sdim// As you can see in this function, we create a copy relocation for the 540321369Sdim// dynamic linker, and the relocation contains not only symbol name but 541360784Sdim// various other information about the symbol. So, such attributes become a 542321369Sdim// part of the ABI. 543321369Sdim// 544321369Sdim// Note for application developers: I can give you a piece of advice if 545321369Sdim// you are writing a shared library. You probably should export only 546321369Sdim// functions from your library. You shouldn't export variables. 547321369Sdim// 548321369Sdim// As an example what can happen when you export variables without knowing 549321369Sdim// the semantics of copy relocations, assume that you have an exported 550321369Sdim// variable of type T. It is an ABI-breaking change to add new members at 551321369Sdim// end of T even though doing that doesn't change the layout of the 552321369Sdim// existing members. That's because the space for the new members are not 553321369Sdim// reserved in .bss unless you recompile the main program. That means they 554321369Sdim// are likely to overlap with other data that happens to be laid out next 555321369Sdim// to the variable in .bss. This kind of issue is sometimes very hard to 556360784Sdim// debug. What's a solution? Instead of exporting a variable V from a DSO, 557321369Sdim// define an accessor getV(). 558353358Sdimtemplate <class ELFT> static void addCopyRelSymbol(SharedSymbol &ss) { 559303239Sdim // Copy relocation against zero-sized symbol doesn't make sense. 560353358Sdim uint64_t symSize = ss.getSize(); 561353358Sdim if (symSize == 0 || ss.alignment == 0) 562353358Sdim fatal("cannot create a copy relocation for symbol " + toString(ss)); 563303239Sdim 564314564Sdim // See if this symbol is in a read-only segment. If so, preserve the symbol's 565314564Sdim // memory protection by reserving space in the .bss.rel.ro section. 566353358Sdim bool isRO = isReadOnly<ELFT>(ss); 567353358Sdim BssSection *sec = 568353358Sdim make<BssSection>(isRO ? ".bss.rel.ro" : ".bss", symSize, ss.alignment); 569360784Sdim OutputSection *osec = (isRO ? in.bssRelRo : in.bss)->getParent(); 570314564Sdim 571360784Sdim // At this point, sectionBases has been migrated to sections. Append sec to 572360784Sdim // sections. 573360784Sdim if (osec->sectionCommands.empty() || 574360784Sdim !isa<InputSectionDescription>(osec->sectionCommands.back())) 575360784Sdim osec->sectionCommands.push_back(make<InputSectionDescription>("")); 576360784Sdim auto *isd = cast<InputSectionDescription>(osec->sectionCommands.back()); 577360784Sdim isd->sections.push_back(sec); 578360784Sdim osec->commitSection(sec); 579360784Sdim 580303239Sdim // Look through the DSO's dynamic symbol table for aliases and create a 581303239Sdim // dynamic symbol for each one. This causes the copy relocation to correctly 582303239Sdim // interpose any aliases. 583353358Sdim for (SharedSymbol *sym : getSymbolsAt<ELFT>(ss)) 584353358Sdim replaceWithDefined(*sym, sec, 0, sym->size); 585321369Sdim 586353358Sdim mainPart->relaDyn->addReloc(target->copyRel, sec, 0, &ss); 587303239Sdim} 588303239Sdim 589321369Sdim// MIPS has an odd notion of "paired" relocations to calculate addends. 590321369Sdim// For example, if a relocation is of R_MIPS_HI16, there must be a 591321369Sdim// R_MIPS_LO16 relocation after that, and an addend is calculated using 592321369Sdim// the two relocations. 593321369Sdimtemplate <class ELFT, class RelTy> 594353358Sdimstatic int64_t computeMipsAddend(const RelTy &rel, const RelTy *end, 595353358Sdim InputSectionBase &sec, RelExpr expr, 596353358Sdim bool isLocal) { 597353358Sdim if (expr == R_MIPS_GOTREL && isLocal) 598353358Sdim return sec.getFile<ELFT>()->mipsGp0; 599321369Sdim 600321369Sdim // The ABI says that the paired relocation is used only for REL. 601321369Sdim // See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf 602321369Sdim if (RelTy::IsRela) 603321369Sdim return 0; 604321369Sdim 605353358Sdim RelType type = rel.getType(config->isMips64EL); 606353358Sdim uint32_t pairTy = getMipsPairType(type, isLocal); 607353358Sdim if (pairTy == R_MIPS_NONE) 608321369Sdim return 0; 609321369Sdim 610353358Sdim const uint8_t *buf = sec.data().data(); 611353358Sdim uint32_t symIndex = rel.getSymbol(config->isMips64EL); 612321369Sdim 613321369Sdim // To make things worse, paired relocations might not be contiguous in 614321369Sdim // the relocation table, so we need to do linear search. *sigh* 615353358Sdim for (const RelTy *ri = &rel; ri != end; ++ri) 616353358Sdim if (ri->getType(config->isMips64EL) == pairTy && 617353358Sdim ri->getSymbol(config->isMips64EL) == symIndex) 618353358Sdim return target->getImplicitAddend(buf + ri->r_offset, pairTy); 619321369Sdim 620353358Sdim warn("can't find matching " + toString(pairTy) + " relocation for " + 621353358Sdim toString(type)); 622321369Sdim return 0; 623303239Sdim} 624303239Sdim 625327952Sdim// Returns an addend of a given relocation. If it is RELA, an addend 626327952Sdim// is in a relocation itself. If it is REL, we need to read it from an 627327952Sdim// input section. 628327952Sdimtemplate <class ELFT, class RelTy> 629353358Sdimstatic int64_t computeAddend(const RelTy &rel, const RelTy *end, 630353358Sdim InputSectionBase &sec, RelExpr expr, 631353358Sdim bool isLocal) { 632353358Sdim int64_t addend; 633353358Sdim RelType type = rel.getType(config->isMips64EL); 634327952Sdim 635327952Sdim if (RelTy::IsRela) { 636353358Sdim addend = getAddend<ELFT>(rel); 637327952Sdim } else { 638353358Sdim const uint8_t *buf = sec.data().data(); 639353358Sdim addend = target->getImplicitAddend(buf + rel.r_offset, type); 640327952Sdim } 641327952Sdim 642353358Sdim if (config->emachine == EM_PPC64 && config->isPic && type == R_PPC64_TOC) 643353358Sdim addend += getPPC64TocBase(); 644353358Sdim if (config->emachine == EM_MIPS) 645353358Sdim addend += computeMipsAddend<ELFT>(rel, end, sec, expr, isLocal); 646327952Sdim 647353358Sdim return addend; 648327952Sdim} 649327952Sdim 650353358Sdim// Custom error message if Sym is defined in a discarded section. 651353358Sdimtemplate <class ELFT> 652353358Sdimstatic std::string maybeReportDiscarded(Undefined &sym) { 653353358Sdim auto *file = dyn_cast_or_null<ObjFile<ELFT>>(sym.file); 654353358Sdim if (!file || !sym.discardedSecIdx || 655353358Sdim file->getSections()[sym.discardedSecIdx] != &InputSection::discarded) 656353358Sdim return ""; 657353358Sdim ArrayRef<Elf_Shdr_Impl<ELFT>> objSections = 658353358Sdim CHECK(file->getObj().sections(), file); 659327952Sdim 660353358Sdim std::string msg; 661353358Sdim if (sym.type == ELF::STT_SECTION) { 662353358Sdim msg = "relocation refers to a discarded section: "; 663353358Sdim msg += CHECK( 664353358Sdim file->getObj().getSectionName(&objSections[sym.discardedSecIdx]), file); 665353358Sdim } else { 666353358Sdim msg = "relocation refers to a symbol in a discarded section: " + 667353358Sdim toString(sym); 668353358Sdim } 669353358Sdim msg += "\n>>> defined in " + toString(file); 670314564Sdim 671353358Sdim Elf_Shdr_Impl<ELFT> elfSec = objSections[sym.discardedSecIdx - 1]; 672353358Sdim if (elfSec.sh_type != SHT_GROUP) 673353358Sdim return msg; 674314564Sdim 675353358Sdim // If the discarded section is a COMDAT. 676353358Sdim StringRef signature = file->getShtGroupSignature(objSections, elfSec); 677353358Sdim if (const InputFile *prevailing = 678353358Sdim symtab->comdatGroups.lookup(CachedHashStringRef(signature))) 679353358Sdim msg += "\n>>> section group signature: " + signature.str() + 680353358Sdim "\n>>> prevailing definition is in " + toString(prevailing); 681353358Sdim return msg; 682353358Sdim} 683321369Sdim 684353358Sdim// Undefined diagnostics are collected in a vector and emitted once all of 685353358Sdim// them are known, so that some postprocessing on the list of undefined symbols 686353358Sdim// can happen before lld emits diagnostics. 687353358Sdimstruct UndefinedDiag { 688353358Sdim Symbol *sym; 689353358Sdim struct Loc { 690353358Sdim InputSectionBase *sec; 691353358Sdim uint64_t offset; 692353358Sdim }; 693353358Sdim std::vector<Loc> locs; 694353358Sdim bool isWarning; 695353358Sdim}; 696353358Sdim 697353358Sdimstatic std::vector<UndefinedDiag> undefs; 698353358Sdim 699360784Sdim// Check whether the definition name def is a mangled function name that matches 700360784Sdim// the reference name ref. 701360784Sdimstatic bool canSuggestExternCForCXX(StringRef ref, StringRef def) { 702360784Sdim llvm::ItaniumPartialDemangler d; 703360784Sdim std::string name = def.str(); 704360784Sdim if (d.partialDemangle(name.c_str())) 705360784Sdim return false; 706360784Sdim char *buf = d.getFunctionName(nullptr, nullptr); 707360784Sdim if (!buf) 708360784Sdim return false; 709360784Sdim bool ret = ref == buf; 710360784Sdim free(buf); 711360784Sdim return ret; 712360784Sdim} 713360784Sdim 714360784Sdim// Suggest an alternative spelling of an "undefined symbol" diagnostic. Returns 715360784Sdim// the suggested symbol, which is either in the symbol table, or in the same 716360784Sdim// file of sym. 717353358Sdimtemplate <class ELFT> 718360784Sdimstatic const Symbol *getAlternativeSpelling(const Undefined &sym, 719360784Sdim std::string &pre_hint, 720360784Sdim std::string &post_hint) { 721360784Sdim DenseMap<StringRef, const Symbol *> map; 722360784Sdim if (auto *file = dyn_cast_or_null<ObjFile<ELFT>>(sym.file)) { 723360784Sdim // If sym is a symbol defined in a discarded section, maybeReportDiscarded() 724360784Sdim // will give an error. Don't suggest an alternative spelling. 725360784Sdim if (file && sym.discardedSecIdx != 0 && 726360784Sdim file->getSections()[sym.discardedSecIdx] == &InputSection::discarded) 727360784Sdim return nullptr; 728360784Sdim 729360784Sdim // Build a map of local defined symbols. 730360784Sdim for (const Symbol *s : sym.file->getSymbols()) 731360784Sdim if (s->isLocal() && s->isDefined()) 732360784Sdim map.try_emplace(s->getName(), s); 733360784Sdim } 734360784Sdim 735360784Sdim auto suggest = [&](StringRef newName) -> const Symbol * { 736360784Sdim // If defined locally. 737360784Sdim if (const Symbol *s = map.lookup(newName)) 738360784Sdim return s; 739360784Sdim 740360784Sdim // If in the symbol table and not undefined. 741360784Sdim if (const Symbol *s = symtab->find(newName)) 742360784Sdim if (!s->isUndefined()) 743360784Sdim return s; 744360784Sdim 745360784Sdim return nullptr; 746360784Sdim }; 747360784Sdim 748360784Sdim // This loop enumerates all strings of Levenshtein distance 1 as typo 749360784Sdim // correction candidates and suggests the one that exists as a non-undefined 750360784Sdim // symbol. 751360784Sdim StringRef name = sym.getName(); 752360784Sdim for (size_t i = 0, e = name.size(); i != e + 1; ++i) { 753360784Sdim // Insert a character before name[i]. 754360784Sdim std::string newName = (name.substr(0, i) + "0" + name.substr(i)).str(); 755360784Sdim for (char c = '0'; c <= 'z'; ++c) { 756360784Sdim newName[i] = c; 757360784Sdim if (const Symbol *s = suggest(newName)) 758360784Sdim return s; 759360784Sdim } 760360784Sdim if (i == e) 761360784Sdim break; 762360784Sdim 763360784Sdim // Substitute name[i]. 764360784Sdim newName = name; 765360784Sdim for (char c = '0'; c <= 'z'; ++c) { 766360784Sdim newName[i] = c; 767360784Sdim if (const Symbol *s = suggest(newName)) 768360784Sdim return s; 769360784Sdim } 770360784Sdim 771360784Sdim // Transpose name[i] and name[i+1]. This is of edit distance 2 but it is 772360784Sdim // common. 773360784Sdim if (i + 1 < e) { 774360784Sdim newName[i] = name[i + 1]; 775360784Sdim newName[i + 1] = name[i]; 776360784Sdim if (const Symbol *s = suggest(newName)) 777360784Sdim return s; 778360784Sdim } 779360784Sdim 780360784Sdim // Delete name[i]. 781360784Sdim newName = (name.substr(0, i) + name.substr(i + 1)).str(); 782360784Sdim if (const Symbol *s = suggest(newName)) 783360784Sdim return s; 784360784Sdim } 785360784Sdim 786360784Sdim // Case mismatch, e.g. Foo vs FOO. 787360784Sdim for (auto &it : map) 788360784Sdim if (name.equals_lower(it.first)) 789360784Sdim return it.second; 790360784Sdim for (Symbol *sym : symtab->symbols()) 791360784Sdim if (!sym->isUndefined() && name.equals_lower(sym->getName())) 792360784Sdim return sym; 793360784Sdim 794360784Sdim // The reference may be a mangled name while the definition is not. Suggest a 795360784Sdim // missing extern "C". 796360784Sdim if (name.startswith("_Z")) { 797360784Sdim std::string buf = name.str(); 798360784Sdim llvm::ItaniumPartialDemangler d; 799360784Sdim if (!d.partialDemangle(buf.c_str())) 800360784Sdim if (char *buf = d.getFunctionName(nullptr, nullptr)) { 801360784Sdim const Symbol *s = suggest(buf); 802360784Sdim free(buf); 803360784Sdim if (s) { 804360784Sdim pre_hint = ": extern \"C\" "; 805360784Sdim return s; 806360784Sdim } 807360784Sdim } 808360784Sdim } else { 809360784Sdim const Symbol *s = nullptr; 810360784Sdim for (auto &it : map) 811360784Sdim if (canSuggestExternCForCXX(name, it.first)) { 812360784Sdim s = it.second; 813360784Sdim break; 814360784Sdim } 815360784Sdim if (!s) 816360784Sdim for (Symbol *sym : symtab->symbols()) 817360784Sdim if (canSuggestExternCForCXX(name, sym->getName())) { 818360784Sdim s = sym; 819360784Sdim break; 820360784Sdim } 821360784Sdim if (s) { 822360784Sdim pre_hint = " to declare "; 823360784Sdim post_hint = " as extern \"C\"?"; 824360784Sdim return s; 825360784Sdim } 826360784Sdim } 827360784Sdim 828360784Sdim return nullptr; 829360784Sdim} 830360784Sdim 831360784Sdimtemplate <class ELFT> 832360784Sdimstatic void reportUndefinedSymbol(const UndefinedDiag &undef, 833360784Sdim bool correctSpelling) { 834353358Sdim Symbol &sym = *undef.sym; 835353358Sdim 836353358Sdim auto visibility = [&]() -> std::string { 837353358Sdim switch (sym.visibility) { 838353358Sdim case STV_INTERNAL: 839353358Sdim return "internal "; 840353358Sdim case STV_HIDDEN: 841353358Sdim return "hidden "; 842353358Sdim case STV_PROTECTED: 843353358Sdim return "protected "; 844353358Sdim default: 845353358Sdim return ""; 846353358Sdim } 847353358Sdim }; 848353358Sdim 849353358Sdim std::string msg = maybeReportDiscarded<ELFT>(cast<Undefined>(sym)); 850353358Sdim if (msg.empty()) 851353358Sdim msg = "undefined " + visibility() + "symbol: " + toString(sym); 852353358Sdim 853353358Sdim const size_t maxUndefReferences = 10; 854353358Sdim size_t i = 0; 855353358Sdim for (UndefinedDiag::Loc l : undef.locs) { 856353358Sdim if (i >= maxUndefReferences) 857353358Sdim break; 858353358Sdim InputSectionBase &sec = *l.sec; 859353358Sdim uint64_t offset = l.offset; 860353358Sdim 861353358Sdim msg += "\n>>> referenced by "; 862353358Sdim std::string src = sec.getSrcMsg(sym, offset); 863353358Sdim if (!src.empty()) 864353358Sdim msg += src + "\n>>> "; 865353358Sdim msg += sec.getObjMsg(offset); 866353358Sdim i++; 867353358Sdim } 868353358Sdim 869353358Sdim if (i < undef.locs.size()) 870353358Sdim msg += ("\n>>> referenced " + Twine(undef.locs.size() - i) + " more times") 871353358Sdim .str(); 872353358Sdim 873360784Sdim if (correctSpelling) { 874360784Sdim std::string pre_hint = ": ", post_hint; 875360784Sdim if (const Symbol *corrected = getAlternativeSpelling<ELFT>( 876360784Sdim cast<Undefined>(sym), pre_hint, post_hint)) { 877360784Sdim msg += "\n>>> did you mean" + pre_hint + toString(*corrected) + post_hint; 878360784Sdim if (corrected->file) 879360784Sdim msg += "\n>>> defined in: " + toString(corrected->file); 880360784Sdim } 881360784Sdim } 882360784Sdim 883353358Sdim if (sym.getName().startswith("_ZTV")) 884353358Sdim msg += "\nthe vtable symbol may be undefined because the class is missing " 885344779Sdim "its key function (see https://lld.llvm.org/missingkeyfunction)"; 886344779Sdim 887353358Sdim if (undef.isWarning) 888353358Sdim warn(msg); 889353358Sdim else 890353358Sdim error(msg); 891353358Sdim} 892353358Sdim 893360784Sdimtemplate <class ELFT> void reportUndefinedSymbols() { 894353358Sdim // Find the first "undefined symbol" diagnostic for each diagnostic, and 895353358Sdim // collect all "referenced from" lines at the first diagnostic. 896353358Sdim DenseMap<Symbol *, UndefinedDiag *> firstRef; 897353358Sdim for (UndefinedDiag &undef : undefs) { 898353358Sdim assert(undef.locs.size() == 1); 899353358Sdim if (UndefinedDiag *canon = firstRef.lookup(undef.sym)) { 900353358Sdim canon->locs.push_back(undef.locs[0]); 901353358Sdim undef.locs.clear(); 902353358Sdim } else 903353358Sdim firstRef[undef.sym] = &undef; 904321369Sdim } 905327952Sdim 906360784Sdim // Enable spell corrector for the first 2 diagnostics. 907360784Sdim for (auto it : enumerate(undefs)) 908360784Sdim if (!it.value().locs.empty()) 909360784Sdim reportUndefinedSymbol<ELFT>(it.value(), it.index() < 2); 910353358Sdim undefs.clear(); 911314564Sdim} 912314564Sdim 913353358Sdim// Report an undefined symbol if necessary. 914353358Sdim// Returns true if the undefined symbol will produce an error message. 915353358Sdimstatic bool maybeReportUndefined(Symbol &sym, InputSectionBase &sec, 916353358Sdim uint64_t offset) { 917353358Sdim if (!sym.isUndefined() || sym.isWeak()) 918353358Sdim return false; 919353358Sdim 920360784Sdim bool canBeExternal = !sym.isLocal() && sym.visibility == STV_DEFAULT; 921353358Sdim if (config->unresolvedSymbols == UnresolvedPolicy::Ignore && canBeExternal) 922353358Sdim return false; 923353358Sdim 924353358Sdim // clang (as of 2019-06-12) / gcc (as of 8.2.1) PPC64 may emit a .rela.toc 925353358Sdim // which references a switch table in a discarded .rodata/.text section. The 926353358Sdim // .toc and the .rela.toc are incorrectly not placed in the comdat. The ELF 927353358Sdim // spec says references from outside the group to a STB_LOCAL symbol are not 928353358Sdim // allowed. Work around the bug. 929360784Sdim // 930360784Sdim // PPC32 .got2 is similar but cannot be fixed. Multiple .got2 is infeasible 931360784Sdim // because .LC0-.LTOC is not representable if the two labels are in different 932360784Sdim // .got2 933360784Sdim if (cast<Undefined>(sym).discardedSecIdx != 0 && 934360784Sdim (sec.name == ".got2" || sec.name == ".toc")) 935353358Sdim return false; 936353358Sdim 937353358Sdim bool isWarning = 938353358Sdim (config->unresolvedSymbols == UnresolvedPolicy::Warn && canBeExternal) || 939353358Sdim config->noinhibitExec; 940353358Sdim undefs.push_back({&sym, {{&sec, offset}}, isWarning}); 941353358Sdim return !isWarning; 942353358Sdim} 943353358Sdim 944327952Sdim// MIPS N32 ABI treats series of successive relocations with the same offset 945327952Sdim// as a single relocation. The similar approach used by N64 ABI, but this ABI 946327952Sdim// packs all relocations into the single relocation record. Here we emulate 947327952Sdim// this for the N32 ABI. Iterate over relocation with the same offset and put 948327952Sdim// theirs types into the single bit-set. 949353358Sdimtemplate <class RelTy> static RelType getMipsN32RelType(RelTy *&rel, RelTy *end) { 950353358Sdim RelType type = 0; 951353358Sdim uint64_t offset = rel->r_offset; 952327952Sdim 953353358Sdim int n = 0; 954353358Sdim while (rel != end && rel->r_offset == offset) 955353358Sdim type |= (rel++)->getType(config->isMips64EL) << (8 * n++); 956353358Sdim return type; 957314564Sdim} 958314564Sdim 959321369Sdim// .eh_frame sections are mergeable input sections, so their input 960321369Sdim// offsets are not linearly mapped to output section. For each input 961321369Sdim// offset, we need to find a section piece containing the offset and 962321369Sdim// add the piece's base address to the input offset to compute the 963321369Sdim// output offset. That isn't cheap. 964321369Sdim// 965321369Sdim// This class is to speed up the offset computation. When we process 966321369Sdim// relocations, we access offsets in the monotonically increasing 967321369Sdim// order. So we can optimize for that access pattern. 968321369Sdim// 969321369Sdim// For sections other than .eh_frame, this class doesn't do anything. 970321369Sdimnamespace { 971321369Sdimclass OffsetGetter { 972321369Sdimpublic: 973353358Sdim explicit OffsetGetter(InputSectionBase &sec) { 974353358Sdim if (auto *eh = dyn_cast<EhInputSection>(&sec)) 975353358Sdim pieces = eh->pieces; 976321369Sdim } 977321369Sdim 978321369Sdim // Translates offsets in input sections to offsets in output sections. 979327952Sdim // Given offset must increase monotonically. We assume that Piece is 980353358Sdim // sorted by inputOff. 981353358Sdim uint64_t get(uint64_t off) { 982353358Sdim if (pieces.empty()) 983353358Sdim return off; 984321369Sdim 985353358Sdim while (i != pieces.size() && pieces[i].inputOff + pieces[i].size <= off) 986353358Sdim ++i; 987353358Sdim if (i == pieces.size()) 988344779Sdim fatal(".eh_frame: relocation is not in any piece"); 989321369Sdim 990327952Sdim // Pieces must be contiguous, so there must be no holes in between. 991353358Sdim assert(pieces[i].inputOff <= off && "Relocation not in any piece"); 992321369Sdim 993321369Sdim // Offset -1 means that the piece is dead (i.e. garbage collected). 994353358Sdim if (pieces[i].outputOff == -1) 995321369Sdim return -1; 996353358Sdim return pieces[i].outputOff + off - pieces[i].inputOff; 997321369Sdim } 998321369Sdim 999321369Sdimprivate: 1000353358Sdim ArrayRef<EhSectionPiece> pieces; 1001353358Sdim size_t i = 0; 1002321369Sdim}; 1003321369Sdim} // namespace 1004321369Sdim 1005353358Sdimstatic void addRelativeReloc(InputSectionBase *isec, uint64_t offsetInSec, 1006353358Sdim Symbol *sym, int64_t addend, RelExpr expr, 1007353358Sdim RelType type) { 1008353358Sdim Partition &part = isec->getPartition(); 1009353358Sdim 1010353358Sdim // Add a relative relocation. If relrDyn section is enabled, and the 1011341825Sdim // relocation offset is guaranteed to be even, add the relocation to 1012353358Sdim // the relrDyn section, otherwise add it to the relaDyn section. 1013353358Sdim // relrDyn sections don't support odd offsets. Also, relrDyn sections 1014341825Sdim // don't store the addend values, so we must write it to the relocated 1015341825Sdim // address. 1016353358Sdim if (part.relrDyn && isec->alignment >= 2 && offsetInSec % 2 == 0) { 1017353358Sdim isec->relocations.push_back({expr, type, offsetInSec, addend, sym}); 1018353358Sdim part.relrDyn->relocs.push_back({isec, offsetInSec}); 1019341825Sdim return; 1020341825Sdim } 1021353358Sdim part.relaDyn->addReloc(target->relativeRel, isec, offsetInSec, sym, addend, 1022353358Sdim expr, type); 1023341825Sdim} 1024341825Sdim 1025360784Sdimtemplate <class PltSection, class GotPltSection> 1026353358Sdimstatic void addPltEntry(PltSection *plt, GotPltSection *gotPlt, 1027353358Sdim RelocationBaseSection *rel, RelType type, Symbol &sym) { 1028360784Sdim plt->addEntry(sym); 1029353358Sdim gotPlt->addEntry(sym); 1030353358Sdim rel->addReloc( 1031353358Sdim {type, gotPlt, sym.getGotPltOffset(), !sym.isPreemptible, &sym, 0}); 1032321369Sdim} 1033321369Sdim 1034353358Sdimstatic void addGotEntry(Symbol &sym) { 1035353358Sdim in.got->addEntry(sym); 1036321369Sdim 1037353358Sdim RelExpr expr = sym.isTls() ? R_TLS : R_ABS; 1038353358Sdim uint64_t off = sym.getGotOffset(); 1039321369Sdim 1040326897Semaste // If a GOT slot value can be calculated at link-time, which is now, 1041326897Semaste // we can just fill that out. 1042326897Semaste // 1043326897Semaste // (We don't actually write a value to a GOT slot right now, but we 1044326897Semaste // add a static relocation to a Relocations vector so that 1045326897Semaste // InputSection::relocate will do the work for us. We may be able 1046326897Semaste // to just write a value now, but it is a TODO.) 1047353358Sdim bool isLinkTimeConstant = 1048353358Sdim !sym.isPreemptible && (!config->isPic || isAbsolute(sym)); 1049353358Sdim if (isLinkTimeConstant) { 1050353358Sdim in.got->relocations.push_back({expr, target->symbolicRel, off, 0, &sym}); 1051327952Sdim return; 1052327952Sdim } 1053321369Sdim 1054327952Sdim // Otherwise, we emit a dynamic relocation to .rel[a].dyn so that 1055327952Sdim // the GOT slot will be fixed at load-time. 1056353358Sdim if (!sym.isTls() && !sym.isPreemptible && config->isPic && !isAbsolute(sym)) { 1057353358Sdim addRelativeReloc(in.got, off, &sym, 0, R_ABS, target->symbolicRel); 1058341825Sdim return; 1059341825Sdim } 1060353358Sdim mainPart->relaDyn->addReloc( 1061353358Sdim sym.isTls() ? target->tlsGotRel : target->gotRel, in.got, off, &sym, 0, 1062353358Sdim sym.isPreemptible ? R_ADDEND : R_ABS, target->symbolicRel); 1063341825Sdim} 1064327952Sdim 1065341825Sdim// Return true if we can define a symbol in the executable that 1066341825Sdim// contains the value/function of a symbol defined in a shared 1067341825Sdim// library. 1068353358Sdimstatic bool canDefineSymbolInExecutable(Symbol &sym) { 1069341825Sdim // If the symbol has default visibility the symbol defined in the 1070341825Sdim // executable will preempt it. 1071341825Sdim // Note that we want the visibility of the shared symbol itself, not 1072341825Sdim // the visibility of the symbol in the output file we are producing. That is 1073353358Sdim // why we use Sym.stOther. 1074353358Sdim if ((sym.stOther & 0x3) == STV_DEFAULT) 1075341825Sdim return true; 1076341825Sdim 1077341825Sdim // If we are allowed to break address equality of functions, defining 1078341825Sdim // a plt entry will allow the program to call the function in the 1079341825Sdim // .so, but the .so and the executable will no agree on the address 1080341825Sdim // of the function. Similar logic for objects. 1081353358Sdim return ((sym.isFunc() && config->ignoreFunctionAddressEquality) || 1082353358Sdim (sym.isObject() && config->ignoreDataAddressEquality)); 1083321369Sdim} 1084321369Sdim 1085303239Sdim// The reason we have to do this early scan is as follows 1086303239Sdim// * To mmap the output file, we need to know the size 1087303239Sdim// * For that, we need to know how many dynamic relocs we will have. 1088303239Sdim// It might be possible to avoid this by outputting the file with write: 1089303239Sdim// * Write the allocated output sections, computing addresses. 1090303239Sdim// * Apply relocations, recording which ones require a dynamic reloc. 1091303239Sdim// * Write the dynamic relocations. 1092303239Sdim// * Write the rest of the file. 1093303239Sdim// This would have some drawbacks. For example, we would only know if .rela.dyn 1094303239Sdim// is needed after applying relocations. If it is, it will go after rw and rx 1095303239Sdim// sections. Given that it is ro, we will need an extra PT_LOAD. This 1096303239Sdim// complicates things for the dynamic linker and means we would have to reserve 1097303239Sdim// space for the extra PT_LOAD even if we end up not using it. 1098303239Sdimtemplate <class ELFT, class RelTy> 1099353358Sdimstatic void processRelocAux(InputSectionBase &sec, RelExpr expr, RelType type, 1100353358Sdim uint64_t offset, Symbol &sym, const RelTy &rel, 1101353358Sdim int64_t addend) { 1102353358Sdim // If the relocation is known to be a link-time constant, we know no dynamic 1103353358Sdim // relocation will be created, pass the control to relocateAlloc() or 1104353358Sdim // relocateNonAlloc() to resolve it. 1105353358Sdim // 1106353358Sdim // The behavior of an undefined weak reference is implementation defined. If 1107353358Sdim // the relocation is to a weak undef, and we are producing an executable, let 1108353358Sdim // relocate{,Non}Alloc() resolve it. 1109353358Sdim if (isStaticLinkTimeConstant(expr, type, sym, sec, offset) || 1110353358Sdim (!config->shared && sym.isUndefWeak())) { 1111353358Sdim sec.relocations.push_back({expr, type, offset, addend, &sym}); 1112341825Sdim return; 1113341825Sdim } 1114303239Sdim 1115353358Sdim bool canWrite = (sec.flags & SHF_WRITE) || !config->zText; 1116353358Sdim if (canWrite) { 1117353358Sdim RelType rel = target->getDynRel(type); 1118353358Sdim if (expr == R_GOT || (rel == target->symbolicRel && !sym.isPreemptible)) { 1119353358Sdim addRelativeReloc(&sec, offset, &sym, addend, expr, type); 1120341825Sdim return; 1121353358Sdim } else if (rel != 0) { 1122353358Sdim if (config->emachine == EM_MIPS && rel == target->symbolicRel) 1123353358Sdim rel = target->relativeRel; 1124353358Sdim sec.getPartition().relaDyn->addReloc(rel, &sec, offset, &sym, addend, 1125353358Sdim R_ADDEND, type); 1126327952Sdim 1127341825Sdim // MIPS ABI turns using of GOT and dynamic relocations inside out. 1128341825Sdim // While regular ABI uses dynamic relocations to fill up GOT entries 1129341825Sdim // MIPS ABI requires dynamic linker to fills up GOT entries using 1130341825Sdim // specially sorted dynamic symbol table. This affects even dynamic 1131341825Sdim // relocations against symbols which do not require GOT entries 1132341825Sdim // creation explicitly, i.e. do not have any GOT-relocations. So if 1133341825Sdim // a preemptible symbol has a dynamic relocation we anyway have 1134341825Sdim // to create a GOT entry for it. 1135341825Sdim // If a non-preemptible symbol has a dynamic relocation against it, 1136341825Sdim // dynamic linker takes it st_value, adds offset and writes down 1137341825Sdim // result of the dynamic relocation. In case of preemptible symbol 1138341825Sdim // dynamic linker performs symbol resolution, writes the symbol value 1139341825Sdim // to the GOT entry and reads the GOT entry when it needs to perform 1140341825Sdim // a dynamic relocation. 1141341825Sdim // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf p.4-19 1142353358Sdim if (config->emachine == EM_MIPS) 1143353358Sdim in.mipsGot->addEntry(*sec.file, sym, addend, expr); 1144341825Sdim return; 1145341825Sdim } 1146341825Sdim } 1147303239Sdim 1148360784Sdim // When producing an executable, we can perform copy relocations (for 1149360784Sdim // STT_OBJECT) and canonical PLT (for STT_FUNC). 1150360784Sdim if (!config->shared) { 1151360784Sdim if (!canDefineSymbolInExecutable(sym)) { 1152360784Sdim errorOrWarn("cannot preempt symbol: " + toString(sym) + 1153360784Sdim getLocation(sec, sym, offset)); 1154360784Sdim return; 1155360784Sdim } 1156321369Sdim 1157360784Sdim if (sym.isObject()) { 1158360784Sdim // Produce a copy relocation. 1159360784Sdim if (auto *ss = dyn_cast<SharedSymbol>(&sym)) { 1160360784Sdim if (!config->zCopyreloc) 1161360784Sdim error("unresolvable relocation " + toString(type) + 1162360784Sdim " against symbol '" + toString(*ss) + 1163360784Sdim "'; recompile with -fPIC or remove '-z nocopyreloc'" + 1164360784Sdim getLocation(sec, sym, offset)); 1165360784Sdim addCopyRelSymbol<ELFT>(*ss); 1166360784Sdim } 1167360784Sdim sec.relocations.push_back({expr, type, offset, addend, &sym}); 1168360784Sdim return; 1169327952Sdim } 1170303239Sdim 1171341825Sdim // This handles a non PIC program call to function in a shared library. In 1172341825Sdim // an ideal world, we could just report an error saying the relocation can 1173341825Sdim // overflow at runtime. In the real world with glibc, crt1.o has a 1174341825Sdim // R_X86_64_PC32 pointing to libc.so. 1175327952Sdim // 1176341825Sdim // The general idea on how to handle such cases is to create a PLT entry and 1177341825Sdim // use that as the function value. 1178327952Sdim // 1179341825Sdim // For the static linking part, we just return a plt expr and everything 1180341825Sdim // else will use the PLT entry as the address. 1181341825Sdim // 1182341825Sdim // The remaining problem is making sure pointer equality still works. We 1183341825Sdim // need the help of the dynamic linker for that. We let it know that we have 1184341825Sdim // a direct reference to a so symbol by creating an undefined symbol with a 1185341825Sdim // non zero st_value. Seeing that, the dynamic linker resolves the symbol to 1186341825Sdim // the value of the symbol we created. This is true even for got entries, so 1187341825Sdim // pointer equality is maintained. To avoid an infinite loop, the only entry 1188341825Sdim // that points to the real function is a dedicated got entry used by the 1189341825Sdim // plt. That is identified by special relocation types (R_X86_64_JUMP_SLOT, 1190341825Sdim // R_386_JMP_SLOT, etc). 1191327952Sdim 1192341825Sdim // For position independent executable on i386, the plt entry requires ebx 1193341825Sdim // to be set. This causes two problems: 1194341825Sdim // * If some code has a direct reference to a function, it was probably 1195341825Sdim // compiled without -fPIE/-fPIC and doesn't maintain ebx. 1196341825Sdim // * If a library definition gets preempted to the executable, it will have 1197341825Sdim // the wrong ebx value. 1198360784Sdim if (sym.isFunc()) { 1199360784Sdim if (config->pie && config->emachine == EM_386) 1200360784Sdim errorOrWarn("symbol '" + toString(sym) + 1201360784Sdim "' cannot be preempted; recompile with -fPIE" + 1202360784Sdim getLocation(sec, sym, offset)); 1203360784Sdim if (!sym.isInPlt()) 1204360784Sdim addPltEntry(in.plt, in.gotPlt, in.relaPlt, target->pltRel, sym); 1205360784Sdim if (!sym.isDefined()) { 1206360784Sdim replaceWithDefined( 1207360784Sdim sym, in.plt, 1208360784Sdim target->pltHeaderSize + target->pltEntrySize * sym.pltIndex, 0); 1209360784Sdim if (config->emachine == EM_PPC) { 1210360784Sdim // PPC32 canonical PLT entries are at the beginning of .glink 1211360784Sdim cast<Defined>(sym).value = in.plt->headerSize; 1212360784Sdim in.plt->headerSize += 16; 1213360784Sdim cast<PPC32GlinkSection>(in.plt)->canonical_plts.push_back(&sym); 1214360784Sdim } 1215360784Sdim } 1216360784Sdim sym.needsPltAddr = true; 1217360784Sdim sec.relocations.push_back({expr, type, offset, addend, &sym}); 1218360784Sdim return; 1219360784Sdim } 1220360784Sdim } 1221360784Sdim 1222360784Sdim if (config->isPic) { 1223360784Sdim if (!canWrite && !isRelExpr(expr)) 1224360784Sdim errorOrWarn( 1225360784Sdim "can't create dynamic relocation " + toString(type) + " against " + 1226360784Sdim (sym.getName().empty() ? "local symbol" 1227360784Sdim : "symbol: " + toString(sym)) + 1228360784Sdim " in readonly segment; recompile object files with -fPIC " 1229360784Sdim "or pass '-Wl,-z,notext' to allow text relocations in the output" + 1230360784Sdim getLocation(sec, sym, offset)); 1231360784Sdim else 1232360784Sdim errorOrWarn( 1233360784Sdim "relocation " + toString(type) + " cannot be used against " + 1234360784Sdim (sym.getName().empty() ? "local symbol" : "symbol " + toString(sym)) + 1235360784Sdim "; recompile with -fPIC" + getLocation(sec, sym, offset)); 1236341825Sdim return; 1237341825Sdim } 1238327952Sdim 1239353358Sdim errorOrWarn("symbol '" + toString(sym) + "' has no type" + 1240353358Sdim getLocation(sec, sym, offset)); 1241341825Sdim} 1242327952Sdim 1243341825Sdimtemplate <class ELFT, class RelTy> 1244353358Sdimstatic void scanReloc(InputSectionBase &sec, OffsetGetter &getOffset, RelTy *&i, 1245353358Sdim RelTy *end) { 1246353358Sdim const RelTy &rel = *i; 1247353358Sdim uint32_t symIndex = rel.getSymbol(config->isMips64EL); 1248353358Sdim Symbol &sym = sec.getFile<ELFT>()->getSymbol(symIndex); 1249353358Sdim RelType type; 1250303239Sdim 1251341825Sdim // Deal with MIPS oddity. 1252353358Sdim if (config->mipsN32Abi) { 1253353358Sdim type = getMipsN32RelType(i, end); 1254341825Sdim } else { 1255353358Sdim type = rel.getType(config->isMips64EL); 1256353358Sdim ++i; 1257341825Sdim } 1258303239Sdim 1259341825Sdim // Get an offset in an output section this relocation is applied to. 1260353358Sdim uint64_t offset = getOffset.get(rel.r_offset); 1261353358Sdim if (offset == uint64_t(-1)) 1262341825Sdim return; 1263303239Sdim 1264353358Sdim // Error if the target symbol is undefined. Symbol index 0 may be used by 1265353358Sdim // marker relocations, e.g. R_*_NONE and R_ARM_V4BX. Don't error on them. 1266360784Sdim if (symIndex != 0 && maybeReportUndefined(sym, sec, rel.r_offset)) 1267341825Sdim return; 1268303239Sdim 1269353358Sdim const uint8_t *relocatedAddr = sec.data().begin() + rel.r_offset; 1270353358Sdim RelExpr expr = target->getRelExpr(type, sym, relocatedAddr); 1271303239Sdim 1272360784Sdim // Ignore R_*_NONE and other marker relocations. 1273360784Sdim if (expr == R_NONE) 1274341825Sdim return; 1275314564Sdim 1276353358Sdim // We can separate the small code model relocations into 2 categories: 1277353358Sdim // 1) Those that access the compiler generated .toc sections. 1278353358Sdim // 2) Those that access the linker allocated got entries. 1279353358Sdim // lld allocates got entries to symbols on demand. Since we don't try to sort 1280353358Sdim // the got entries in any way, we don't have to track which objects have 1281353358Sdim // got-based small code model relocs. The .toc sections get placed after the 1282353358Sdim // end of the linker allocated .got section and we do sort those so sections 1283353358Sdim // addressed with small code model relocations come first. 1284353358Sdim if (config->emachine == EM_PPC64 && isPPC64SmallCodeModelTocReloc(type)) 1285353358Sdim sec.file->ppc64SmallCodeModelTocRelocs = true; 1286353358Sdim 1287353358Sdim if (sym.isGnuIFunc() && !config->zText && config->warnIfuncTextrel) { 1288350467Sluporl warn("using ifunc symbols when text relocations are allowed may produce " 1289350467Sluporl "a binary that will segfault, if the object file is linked with " 1290350467Sluporl "old version of glibc (glibc 2.28 and earlier). If this applies to " 1291350467Sluporl "you, consider recompiling the object files without -fPIC and " 1292350467Sluporl "without -Wl,-z,notext option. Use -no-warn-ifunc-textrel to " 1293350467Sluporl "turn off this warning." + 1294353358Sdim getLocation(sec, sym, offset)); 1295350467Sluporl } 1296350467Sluporl 1297353358Sdim // Read an addend. 1298353358Sdim int64_t addend = computeAddend<ELFT>(rel, end, sec, expr, sym.isLocal()); 1299353358Sdim 1300350467Sluporl // Relax relocations. 1301341825Sdim // 1302350467Sluporl // If we know that a PLT entry will be resolved within the same ELF module, we 1303350467Sluporl // can skip PLT access and directly jump to the destination function. For 1304360784Sdim // example, if we are linking a main executable, all dynamic symbols that can 1305350467Sluporl // be resolved within the executable will actually be resolved that way at 1306360784Sdim // runtime, because the main executable is always at the beginning of a search 1307350467Sluporl // list. We can leverage that fact. 1308353358Sdim if (!sym.isPreemptible && (!sym.isGnuIFunc() || config->zIfuncNoplt)) { 1309353358Sdim if (expr == R_GOT_PC && !isAbsoluteValue(sym)) { 1310353358Sdim expr = target->adjustRelaxExpr(type, relocatedAddr, expr); 1311353358Sdim } else { 1312360784Sdim // The 0x8000 bit of r_addend of R_PPC_PLTREL24 is used to choose call 1313360784Sdim // stub type. It should be ignored if optimized to R_PC. 1314353358Sdim if (config->emachine == EM_PPC && expr == R_PPC32_PLTREL) 1315360784Sdim addend &= ~0x8000; 1316353358Sdim expr = fromPlt(expr); 1317353358Sdim } 1318344779Sdim } 1319321369Sdim 1320353358Sdim // If the relocation does not emit a GOT or GOTPLT entry but its computation 1321353358Sdim // uses their addresses, we need GOT or GOTPLT to be created. 1322353358Sdim // 1323353358Sdim // The 4 types that relative GOTPLT are all x86 and x86-64 specific. 1324353358Sdim if (oneof<R_GOTPLTONLY_PC, R_GOTPLTREL, R_GOTPLT, R_TLSGD_GOTPLT>(expr)) { 1325353358Sdim in.gotPlt->hasGotPltOffRel = true; 1326353358Sdim } else if (oneof<R_GOTONLY_PC, R_GOTREL, R_PPC64_TOCBASE, R_PPC64_RELAX_TOC>( 1327353358Sdim expr)) { 1328353358Sdim in.got->hasGotOffRel = true; 1329353358Sdim } 1330303239Sdim 1331341825Sdim // Process some TLS relocations, including relaxing TLS relocations. 1332341825Sdim // Note that this function does not handle all TLS relocations. 1333353358Sdim if (unsigned processed = 1334353358Sdim handleTlsRelocation<ELFT>(type, sym, sec, offset, addend, expr)) { 1335353358Sdim i += (processed - 1); 1336341825Sdim return; 1337341825Sdim } 1338327952Sdim 1339350467Sluporl // We were asked not to generate PLT entries for ifuncs. Instead, pass the 1340350467Sluporl // direct relocation on through. 1341353358Sdim if (sym.isGnuIFunc() && config->zIfuncNoplt) { 1342353358Sdim sym.exportDynamic = true; 1343353358Sdim mainPart->relaDyn->addReloc(type, &sec, offset, &sym, addend, R_ADDEND, type); 1344350467Sluporl return; 1345341825Sdim } 1346338251Smarkj 1347350467Sluporl // Non-preemptible ifuncs require special handling. First, handle the usual 1348350467Sluporl // case where the symbol isn't one of these. 1349353358Sdim if (!sym.isGnuIFunc() || sym.isPreemptible) { 1350350467Sluporl // If a relocation needs PLT, we create PLT and GOTPLT slots for the symbol. 1351353358Sdim if (needsPlt(expr) && !sym.isInPlt()) 1352360784Sdim addPltEntry(in.plt, in.gotPlt, in.relaPlt, target->pltRel, sym); 1353350467Sluporl 1354350467Sluporl // Create a GOT slot if a relocation needs GOT. 1355353358Sdim if (needsGot(expr)) { 1356353358Sdim if (config->emachine == EM_MIPS) { 1357350467Sluporl // MIPS ABI has special rules to process GOT entries and doesn't 1358350467Sluporl // require relocation entries for them. A special case is TLS 1359350467Sluporl // relocations. In that case dynamic loader applies dynamic 1360350467Sluporl // relocations to initialize TLS GOT entries. 1361350467Sluporl // See "Global Offset Table" in Chapter 5 in the following document 1362350467Sluporl // for detailed description: 1363350467Sluporl // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf 1364353358Sdim in.mipsGot->addEntry(*sec.file, sym, addend, expr); 1365353358Sdim } else if (!sym.isInGot()) { 1366353358Sdim addGotEntry(sym); 1367350467Sluporl } 1368327952Sdim } 1369350467Sluporl } else { 1370350467Sluporl // Handle a reference to a non-preemptible ifunc. These are special in a 1371350467Sluporl // few ways: 1372350467Sluporl // 1373350467Sluporl // - Unlike most non-preemptible symbols, non-preemptible ifuncs do not have 1374350467Sluporl // a fixed value. But assuming that all references to the ifunc are 1375350467Sluporl // GOT-generating or PLT-generating, the handling of an ifunc is 1376350467Sluporl // relatively straightforward. We create a PLT entry in Iplt, which is 1377350467Sluporl // usually at the end of .plt, which makes an indirect call using a 1378353358Sdim // matching GOT entry in igotPlt, which is usually at the end of .got.plt. 1379353358Sdim // The GOT entry is relocated using an IRELATIVE relocation in relaIplt, 1380350467Sluporl // which is usually at the end of .rela.plt. Unlike most relocations in 1381350467Sluporl // .rela.plt, which may be evaluated lazily without -z now, dynamic 1382350467Sluporl // loaders evaluate IRELATIVE relocs eagerly, which means that for 1383350467Sluporl // IRELATIVE relocs only, GOT-generating relocations can point directly to 1384350467Sluporl // .got.plt without requiring a separate GOT entry. 1385350467Sluporl // 1386350467Sluporl // - Despite the fact that an ifunc does not have a fixed value, compilers 1387350467Sluporl // that are not passed -fPIC will assume that they do, and will emit 1388350467Sluporl // direct (non-GOT-generating, non-PLT-generating) relocations to the 1389350467Sluporl // symbol. This means that if a direct relocation to the symbol is 1390350467Sluporl // seen, the linker must set a value for the symbol, and this value must 1391350467Sluporl // be consistent no matter what type of reference is made to the symbol. 1392350467Sluporl // This can be done by creating a PLT entry for the symbol in the way 1393350467Sluporl // described above and making it canonical, that is, making all references 1394350467Sluporl // point to the PLT entry instead of the resolver. In lld we also store 1395350467Sluporl // the address of the PLT entry in the dynamic symbol table, which means 1396350467Sluporl // that the symbol will also have the same value in other modules. 1397350467Sluporl // Because the value loaded from the GOT needs to be consistent with 1398350467Sluporl // the value computed using a direct relocation, a non-preemptible ifunc 1399350467Sluporl // may end up with two GOT entries, one in .got.plt that points to the 1400350467Sluporl // address returned by the resolver and is used only by the PLT entry, 1401350467Sluporl // and another in .got that points to the PLT entry and is used by 1402350467Sluporl // GOT-generating relocations. 1403350467Sluporl // 1404350467Sluporl // - The fact that these symbols do not have a fixed value makes them an 1405350467Sluporl // exception to the general rule that a statically linked executable does 1406350467Sluporl // not require any form of dynamic relocation. To handle these relocations 1407350467Sluporl // correctly, the IRELATIVE relocations are stored in an array which a 1408350467Sluporl // statically linked executable's startup code must enumerate using the 1409350467Sluporl // linker-defined symbols __rela?_iplt_{start,end}. 1410353358Sdim if (!sym.isInPlt()) { 1411350467Sluporl // Create PLT and GOTPLT slots for the symbol. 1412353358Sdim sym.isInIplt = true; 1413350467Sluporl 1414350467Sluporl // Create a copy of the symbol to use as the target of the IRELATIVE 1415353358Sdim // relocation in the igotPlt. This is in case we make the PLT canonical 1416350467Sluporl // later, which would overwrite the original symbol. 1417350467Sluporl // 1418350467Sluporl // FIXME: Creating a copy of the symbol here is a bit of a hack. All 1419350467Sluporl // that's really needed to create the IRELATIVE is the section and value, 1420350467Sluporl // so ideally we should just need to copy those. 1421353358Sdim auto *directSym = make<Defined>(cast<Defined>(sym)); 1422360784Sdim addPltEntry(in.iplt, in.igotPlt, in.relaIplt, target->iRelativeRel, 1423360784Sdim *directSym); 1424353358Sdim sym.pltIndex = directSym->pltIndex; 1425350467Sluporl } 1426353358Sdim if (needsGot(expr)) { 1427350467Sluporl // Redirect GOT accesses to point to the Igot. 1428350467Sluporl // 1429350467Sluporl // This field is also used to keep track of whether we ever needed a GOT 1430350467Sluporl // entry. If we did and we make the PLT canonical later, we'll need to 1431350467Sluporl // create a GOT entry pointing to the PLT entry for Sym. 1432353358Sdim sym.gotInIgot = true; 1433353358Sdim } else if (!needsPlt(expr)) { 1434350467Sluporl // Make the ifunc's PLT entry canonical by changing the value of its 1435350467Sluporl // symbol to redirect all references to point to it. 1436353358Sdim auto &d = cast<Defined>(sym); 1437353358Sdim d.section = in.iplt; 1438360784Sdim d.value = sym.pltIndex * target->ipltEntrySize; 1439353358Sdim d.size = 0; 1440350467Sluporl // It's important to set the symbol type here so that dynamic loaders 1441350467Sluporl // don't try to call the PLT as if it were an ifunc resolver. 1442353358Sdim d.type = STT_FUNC; 1443350467Sluporl 1444353358Sdim if (sym.gotInIgot) { 1445350467Sluporl // We previously encountered a GOT generating reference that we 1446350467Sluporl // redirected to the Igot. Now that the PLT entry is canonical we must 1447350467Sluporl // clear the redirection to the Igot and add a GOT entry. As we've 1448350467Sluporl // changed the symbol type to STT_FUNC future GOT generating references 1449350467Sluporl // will naturally use this GOT entry. 1450350467Sluporl // 1451350467Sluporl // We don't need to worry about creating a MIPS GOT here because ifuncs 1452350467Sluporl // aren't a thing on MIPS. 1453353358Sdim sym.gotInIgot = false; 1454353358Sdim addGotEntry(sym); 1455350467Sluporl } 1456350467Sluporl } 1457321369Sdim } 1458341825Sdim 1459353358Sdim processRelocAux<ELFT>(sec, expr, type, offset, sym, rel, addend); 1460321369Sdim} 1461303239Sdim 1462341825Sdimtemplate <class ELFT, class RelTy> 1463353358Sdimstatic void scanRelocs(InputSectionBase &sec, ArrayRef<RelTy> rels) { 1464353358Sdim OffsetGetter getOffset(sec); 1465341825Sdim 1466341825Sdim // Not all relocations end up in Sec.Relocations, but a lot do. 1467353358Sdim sec.relocations.reserve(rels.size()); 1468341825Sdim 1469353358Sdim for (auto i = rels.begin(), end = rels.end(); i != end;) 1470353358Sdim scanReloc<ELFT>(sec, getOffset, i, end); 1471344779Sdim 1472353358Sdim // Sort relocations by offset for more efficient searching for 1473353358Sdim // R_RISCV_PCREL_HI20 and R_PPC64_ADDR64. 1474353358Sdim if (config->emachine == EM_RISCV || 1475353358Sdim (config->emachine == EM_PPC64 && sec.name == ".toc")) 1476353358Sdim llvm::stable_sort(sec.relocations, 1477353358Sdim [](const Relocation &lhs, const Relocation &rhs) { 1478353358Sdim return lhs.offset < rhs.offset; 1479353358Sdim }); 1480341825Sdim} 1481341825Sdim 1482360784Sdimtemplate <class ELFT> void scanRelocations(InputSectionBase &s) { 1483353358Sdim if (s.areRelocsRela) 1484353358Sdim scanRelocs<ELFT>(s, s.relas<ELFT>()); 1485321369Sdim else 1486353358Sdim scanRelocs<ELFT>(s, s.rels<ELFT>()); 1487321369Sdim} 1488303239Sdim 1489353358Sdimstatic bool mergeCmp(const InputSection *a, const InputSection *b) { 1490344779Sdim // std::merge requires a strict weak ordering. 1491353358Sdim if (a->outSecOff < b->outSecOff) 1492344779Sdim return true; 1493344779Sdim 1494353358Sdim if (a->outSecOff == b->outSecOff) { 1495353358Sdim auto *ta = dyn_cast<ThunkSection>(a); 1496353358Sdim auto *tb = dyn_cast<ThunkSection>(b); 1497344779Sdim 1498344779Sdim // Check if Thunk is immediately before any specific Target 1499344779Sdim // InputSection for example Mips LA25 Thunks. 1500353358Sdim if (ta && ta->getTargetInputSection() == b) 1501344779Sdim return true; 1502344779Sdim 1503344779Sdim // Place Thunk Sections without specific targets before 1504344779Sdim // non-Thunk Sections. 1505353358Sdim if (ta && !tb && !ta->getTargetInputSection()) 1506344779Sdim return true; 1507344779Sdim } 1508344779Sdim 1509344779Sdim return false; 1510344779Sdim} 1511344779Sdim 1512344779Sdim// Call Fn on every executable InputSection accessed via the linker script 1513344779Sdim// InputSectionDescription::Sections. 1514344779Sdimstatic void forEachInputSectionDescription( 1515353358Sdim ArrayRef<OutputSection *> outputSections, 1516353358Sdim llvm::function_ref<void(OutputSection *, InputSectionDescription *)> fn) { 1517353358Sdim for (OutputSection *os : outputSections) { 1518353358Sdim if (!(os->flags & SHF_ALLOC) || !(os->flags & SHF_EXECINSTR)) 1519344779Sdim continue; 1520353358Sdim for (BaseCommand *bc : os->sectionCommands) 1521353358Sdim if (auto *isd = dyn_cast<InputSectionDescription>(bc)) 1522353358Sdim fn(os, isd); 1523344779Sdim } 1524344779Sdim} 1525344779Sdim 1526327952Sdim// Thunk Implementation 1527327952Sdim// 1528327952Sdim// Thunks (sometimes called stubs, veneers or branch islands) are small pieces 1529327952Sdim// of code that the linker inserts inbetween a caller and a callee. The thunks 1530327952Sdim// are added at link time rather than compile time as the decision on whether 1531327952Sdim// a thunk is needed, such as the caller and callee being out of range, can only 1532327952Sdim// be made at link time. 1533327952Sdim// 1534327952Sdim// It is straightforward to tell given the current state of the program when a 1535327952Sdim// thunk is needed for a particular call. The more difficult part is that 1536327952Sdim// the thunk needs to be placed in the program such that the caller can reach 1537327952Sdim// the thunk and the thunk can reach the callee; furthermore, adding thunks to 1538327952Sdim// the program alters addresses, which can mean more thunks etc. 1539327952Sdim// 1540327952Sdim// In lld we have a synthetic ThunkSection that can hold many Thunks. 1541327952Sdim// The decision to have a ThunkSection act as a container means that we can 1542327952Sdim// more easily handle the most common case of a single block of contiguous 1543327952Sdim// Thunks by inserting just a single ThunkSection. 1544327952Sdim// 1545327952Sdim// The implementation of Thunks in lld is split across these areas 1546327952Sdim// Relocations.cpp : Framework for creating and placing thunks 1547327952Sdim// Thunks.cpp : The code generated for each supported thunk 1548327952Sdim// Target.cpp : Target specific hooks that the framework uses to decide when 1549327952Sdim// a thunk is used 1550327952Sdim// Synthetic.cpp : Implementation of ThunkSection 1551327952Sdim// Writer.cpp : Iteratively call framework until no more Thunks added 1552327952Sdim// 1553327952Sdim// Thunk placement requirements: 1554327952Sdim// Mips LA25 thunks. These must be placed immediately before the callee section 1555327952Sdim// We can assume that the caller is in range of the Thunk. These are modelled 1556327952Sdim// by Thunks that return the section they must precede with 1557327952Sdim// getTargetInputSection(). 1558327952Sdim// 1559327952Sdim// ARM interworking and range extension thunks. These thunks must be placed 1560327952Sdim// within range of the caller. All implemented ARM thunks can always reach the 1561327952Sdim// callee as they use an indirect jump via a register that has no range 1562327952Sdim// restrictions. 1563327952Sdim// 1564327952Sdim// Thunk placement algorithm: 1565327952Sdim// For Mips LA25 ThunkSections; the placement is explicit, it has to be before 1566327952Sdim// getTargetInputSection(). 1567327952Sdim// 1568327952Sdim// For thunks that must be placed within range of the caller there are many 1569327952Sdim// possible choices given that the maximum range from the caller is usually 1570327952Sdim// much larger than the average InputSection size. Desirable properties include: 1571327952Sdim// - Maximize reuse of thunks by multiple callers 1572327952Sdim// - Minimize number of ThunkSections to simplify insertion 1573327952Sdim// - Handle impact of already added Thunks on addresses 1574327952Sdim// - Simple to understand and implement 1575327952Sdim// 1576327952Sdim// In lld for the first pass, we pre-create one or more ThunkSections per 1577327952Sdim// InputSectionDescription at Target specific intervals. A ThunkSection is 1578327952Sdim// placed so that the estimated end of the ThunkSection is within range of the 1579327952Sdim// start of the InputSectionDescription or the previous ThunkSection. For 1580327952Sdim// example: 1581327952Sdim// InputSectionDescription 1582327952Sdim// Section 0 1583327952Sdim// ... 1584327952Sdim// Section N 1585327952Sdim// ThunkSection 0 1586327952Sdim// Section N + 1 1587327952Sdim// ... 1588327952Sdim// Section N + K 1589327952Sdim// Thunk Section 1 1590327952Sdim// 1591327952Sdim// The intention is that we can add a Thunk to a ThunkSection that is well 1592327952Sdim// spaced enough to service a number of callers without having to do a lot 1593327952Sdim// of work. An important principle is that it is not an error if a Thunk cannot 1594327952Sdim// be placed in a pre-created ThunkSection; when this happens we create a new 1595327952Sdim// ThunkSection placed next to the caller. This allows us to handle the vast 1596327952Sdim// majority of thunks simply, but also handle rare cases where the branch range 1597327952Sdim// is smaller than the target specific spacing. 1598327952Sdim// 1599327952Sdim// The algorithm is expected to create all the thunks that are needed in a 1600327952Sdim// single pass, with a small number of programs needing a second pass due to 1601327952Sdim// the insertion of thunks in the first pass increasing the offset between 1602327952Sdim// callers and callees that were only just in range. 1603327952Sdim// 1604327952Sdim// A consequence of allowing new ThunkSections to be created outside of the 1605327952Sdim// pre-created ThunkSections is that in rare cases calls to Thunks that were in 1606327952Sdim// range in pass K, are out of range in some pass > K due to the insertion of 1607327952Sdim// more Thunks in between the caller and callee. When this happens we retarget 1608327952Sdim// the relocation back to the original target and create another Thunk. 1609327952Sdim 1610327952Sdim// Remove ThunkSections that are empty, this should only be the initial set 1611327952Sdim// precreated on pass 0. 1612327952Sdim 1613321369Sdim// Insert the Thunks for OutputSection OS into their designated place 1614321369Sdim// in the Sections vector, and recalculate the InputSection output section 1615321369Sdim// offsets. 1616321369Sdim// This may invalidate any output section offsets stored outside of InputSection 1617353358Sdimvoid ThunkCreator::mergeThunks(ArrayRef<OutputSection *> outputSections) { 1618327952Sdim forEachInputSectionDescription( 1619353358Sdim outputSections, [&](OutputSection *os, InputSectionDescription *isd) { 1620353358Sdim if (isd->thunkSections.empty()) 1621327952Sdim return; 1622314564Sdim 1623327952Sdim // Remove any zero sized precreated Thunks. 1624353358Sdim llvm::erase_if(isd->thunkSections, 1625353358Sdim [](const std::pair<ThunkSection *, uint32_t> &ts) { 1626353358Sdim return ts.first->getSize() == 0; 1627327952Sdim }); 1628344779Sdim 1629327952Sdim // ISD->ThunkSections contains all created ThunkSections, including 1630327952Sdim // those inserted in previous passes. Extract the Thunks created this 1631353358Sdim // pass and order them in ascending outSecOff. 1632353358Sdim std::vector<ThunkSection *> newThunks; 1633360784Sdim for (std::pair<ThunkSection *, uint32_t> ts : isd->thunkSections) 1634353358Sdim if (ts.second == pass) 1635353358Sdim newThunks.push_back(ts.first); 1636353358Sdim llvm::stable_sort(newThunks, 1637353358Sdim [](const ThunkSection *a, const ThunkSection *b) { 1638353358Sdim return a->outSecOff < b->outSecOff; 1639353358Sdim }); 1640321369Sdim 1641353358Sdim // Merge sorted vectors of Thunks and InputSections by outSecOff 1642353358Sdim std::vector<InputSection *> tmp; 1643353358Sdim tmp.reserve(isd->sections.size() + newThunks.size()); 1644344779Sdim 1645353358Sdim std::merge(isd->sections.begin(), isd->sections.end(), 1646353358Sdim newThunks.begin(), newThunks.end(), std::back_inserter(tmp), 1647344779Sdim mergeCmp); 1648344779Sdim 1649353358Sdim isd->sections = std::move(tmp); 1650327952Sdim }); 1651303239Sdim} 1652303239Sdim 1653327952Sdim// Find or create a ThunkSection within the InputSectionDescription (ISD) that 1654327952Sdim// is in range of Src. An ISD maps to a range of InputSections described by a 1655327952Sdim// linker script section pattern such as { .text .text.* }. 1656353358SdimThunkSection *ThunkCreator::getISDThunkSec(OutputSection *os, InputSection *isec, 1657353358Sdim InputSectionDescription *isd, 1658353358Sdim uint32_t type, uint64_t src) { 1659353358Sdim for (std::pair<ThunkSection *, uint32_t> tp : isd->thunkSections) { 1660353358Sdim ThunkSection *ts = tp.first; 1661353358Sdim uint64_t tsBase = os->addr + ts->outSecOff; 1662353358Sdim uint64_t tsLimit = tsBase + ts->getSize(); 1663353358Sdim if (target->inBranchRange(type, src, (src > tsLimit) ? tsBase : tsLimit)) 1664353358Sdim return ts; 1665327952Sdim } 1666303239Sdim 1667327952Sdim // No suitable ThunkSection exists. This can happen when there is a branch 1668327952Sdim // with lower range than the ThunkSection spacing or when there are too 1669327952Sdim // many Thunks. Create a new ThunkSection as close to the InputSection as 1670327952Sdim // possible. Error if InputSection is so large we cannot place ThunkSection 1671327952Sdim // anywhere in Range. 1672353358Sdim uint64_t thunkSecOff = isec->outSecOff; 1673353358Sdim if (!target->inBranchRange(type, src, os->addr + thunkSecOff)) { 1674353358Sdim thunkSecOff = isec->outSecOff + isec->getSize(); 1675353358Sdim if (!target->inBranchRange(type, src, os->addr + thunkSecOff)) 1676327952Sdim fatal("InputSection too large for range extension thunk " + 1677353358Sdim isec->getObjMsg(src - (os->addr + isec->outSecOff))); 1678321369Sdim } 1679353358Sdim return addThunkSection(os, isd, thunkSecOff); 1680321369Sdim} 1681321369Sdim 1682327952Sdim// Add a Thunk that needs to be placed in a ThunkSection that immediately 1683327952Sdim// precedes its Target. 1684353358SdimThunkSection *ThunkCreator::getISThunkSec(InputSection *isec) { 1685353358Sdim ThunkSection *ts = thunkedSections.lookup(isec); 1686353358Sdim if (ts) 1687353358Sdim return ts; 1688321369Sdim 1689327952Sdim // Find InputSectionRange within Target Output Section (TOS) that the 1690327952Sdim // InputSection (IS) that we need to precede is in. 1691353358Sdim OutputSection *tos = isec->getParent(); 1692353358Sdim for (BaseCommand *bc : tos->sectionCommands) { 1693353358Sdim auto *isd = dyn_cast<InputSectionDescription>(bc); 1694353358Sdim if (!isd || isd->sections.empty()) 1695344779Sdim continue; 1696344779Sdim 1697353358Sdim InputSection *first = isd->sections.front(); 1698353358Sdim InputSection *last = isd->sections.back(); 1699344779Sdim 1700353358Sdim if (isec->outSecOff < first->outSecOff || last->outSecOff < isec->outSecOff) 1701344779Sdim continue; 1702344779Sdim 1703353358Sdim ts = addThunkSection(tos, isd, isec->outSecOff); 1704353358Sdim thunkedSections[isec] = ts; 1705353358Sdim return ts; 1706344779Sdim } 1707344779Sdim 1708344779Sdim return nullptr; 1709321369Sdim} 1710321369Sdim 1711327952Sdim// Create one or more ThunkSections per OS that can be used to place Thunks. 1712327952Sdim// We attempt to place the ThunkSections using the following desirable 1713327952Sdim// properties: 1714327952Sdim// - Within range of the maximum number of callers 1715327952Sdim// - Minimise the number of ThunkSections 1716327952Sdim// 1717327952Sdim// We follow a simple but conservative heuristic to place ThunkSections at 1718327952Sdim// offsets that are multiples of a Target specific branch range. 1719341825Sdim// For an InputSectionDescription that is smaller than the range, a single 1720327952Sdim// ThunkSection at the end of the range will do. 1721341825Sdim// 1722341825Sdim// For an InputSectionDescription that is more than twice the size of the range, 1723341825Sdim// we place the last ThunkSection at range bytes from the end of the 1724341825Sdim// InputSectionDescription in order to increase the likelihood that the 1725341825Sdim// distance from a thunk to its target will be sufficiently small to 1726341825Sdim// allow for the creation of a short thunk. 1727327952Sdimvoid ThunkCreator::createInitialThunkSections( 1728353358Sdim ArrayRef<OutputSection *> outputSections) { 1729353358Sdim uint32_t thunkSectionSpacing = target->getThunkSectionSpacing(); 1730344779Sdim 1731327952Sdim forEachInputSectionDescription( 1732353358Sdim outputSections, [&](OutputSection *os, InputSectionDescription *isd) { 1733353358Sdim if (isd->sections.empty()) 1734327952Sdim return; 1735344779Sdim 1736353358Sdim uint32_t isdBegin = isd->sections.front()->outSecOff; 1737353358Sdim uint32_t isdEnd = 1738353358Sdim isd->sections.back()->outSecOff + isd->sections.back()->getSize(); 1739353358Sdim uint32_t lastThunkLowerBound = -1; 1740353358Sdim if (isdEnd - isdBegin > thunkSectionSpacing * 2) 1741353358Sdim lastThunkLowerBound = isdEnd - thunkSectionSpacing; 1742341825Sdim 1743353358Sdim uint32_t isecLimit; 1744353358Sdim uint32_t prevIsecLimit = isdBegin; 1745353358Sdim uint32_t thunkUpperBound = isdBegin + thunkSectionSpacing; 1746327952Sdim 1747353358Sdim for (const InputSection *isec : isd->sections) { 1748353358Sdim isecLimit = isec->outSecOff + isec->getSize(); 1749353358Sdim if (isecLimit > thunkUpperBound) { 1750353358Sdim addThunkSection(os, isd, prevIsecLimit); 1751353358Sdim thunkUpperBound = prevIsecLimit + thunkSectionSpacing; 1752327952Sdim } 1753353358Sdim if (isecLimit > lastThunkLowerBound) 1754341825Sdim break; 1755353358Sdim prevIsecLimit = isecLimit; 1756327952Sdim } 1757353358Sdim addThunkSection(os, isd, isecLimit); 1758327952Sdim }); 1759327952Sdim} 1760327952Sdim 1761353358SdimThunkSection *ThunkCreator::addThunkSection(OutputSection *os, 1762353358Sdim InputSectionDescription *isd, 1763353358Sdim uint64_t off) { 1764353358Sdim auto *ts = make<ThunkSection>(os, off); 1765353358Sdim ts->partition = os->partition; 1766360784Sdim if ((config->fixCortexA53Errata843419 || config->fixCortexA8) && 1767360784Sdim !isd->sections.empty()) { 1768360784Sdim // The errata fixes are sensitive to addresses modulo 4 KiB. When we add 1769360784Sdim // thunks we disturb the base addresses of sections placed after the thunks 1770360784Sdim // this makes patches we have generated redundant, and may cause us to 1771360784Sdim // generate more patches as different instructions are now in sensitive 1772360784Sdim // locations. When we generate more patches we may force more branches to 1773360784Sdim // go out of range, causing more thunks to be generated. In pathological 1774360784Sdim // cases this can cause the address dependent content pass not to converge. 1775360784Sdim // We fix this by rounding up the size of the ThunkSection to 4KiB, this 1776360784Sdim // limits the insertion of a ThunkSection on the addresses modulo 4 KiB, 1777360784Sdim // which means that adding Thunks to the section does not invalidate 1778360784Sdim // errata patches for following code. 1779360784Sdim // Rounding up the size to 4KiB has consequences for code-size and can 1780360784Sdim // trip up linker script defined assertions. For example the linux kernel 1781360784Sdim // has an assertion that what LLD represents as an InputSectionDescription 1782360784Sdim // does not exceed 4 KiB even if the overall OutputSection is > 128 Mib. 1783360784Sdim // We use the heuristic of rounding up the size when both of the following 1784360784Sdim // conditions are true: 1785360784Sdim // 1.) The OutputSection is larger than the ThunkSectionSpacing. This 1786360784Sdim // accounts for the case where no single InputSectionDescription is 1787360784Sdim // larger than the OutputSection size. This is conservative but simple. 1788360784Sdim // 2.) The InputSectionDescription is larger than 4 KiB. This will prevent 1789360784Sdim // any assertion failures that an InputSectionDescription is < 4 KiB 1790360784Sdim // in size. 1791360784Sdim uint64_t isdSize = isd->sections.back()->outSecOff + 1792360784Sdim isd->sections.back()->getSize() - 1793360784Sdim isd->sections.front()->outSecOff; 1794360784Sdim if (os->size > target->getThunkSectionSpacing() && isdSize > 4096) 1795360784Sdim ts->roundUpSizeForErrata = true; 1796360784Sdim } 1797353358Sdim isd->thunkSections.push_back({ts, pass}); 1798353358Sdim return ts; 1799321369Sdim} 1800321369Sdim 1801353358Sdimstatic bool isThunkSectionCompatible(InputSection *source, 1802353358Sdim SectionBase *target) { 1803353358Sdim // We can't reuse thunks in different loadable partitions because they might 1804353358Sdim // not be loaded. But partition 1 (the main partition) will always be loaded. 1805353358Sdim if (source->partition != target->partition) 1806353358Sdim return target->partition == 1; 1807353358Sdim return true; 1808353358Sdim} 1809344779Sdim 1810360784Sdimstatic int64_t getPCBias(RelType type) { 1811360784Sdim if (config->emachine != EM_ARM) 1812360784Sdim return 0; 1813360784Sdim switch (type) { 1814360784Sdim case R_ARM_THM_JUMP19: 1815360784Sdim case R_ARM_THM_JUMP24: 1816360784Sdim case R_ARM_THM_CALL: 1817360784Sdim return 4; 1818360784Sdim default: 1819360784Sdim return 8; 1820360784Sdim } 1821360784Sdim} 1822360784Sdim 1823353358Sdimstd::pair<Thunk *, bool> ThunkCreator::getThunk(InputSection *isec, 1824353358Sdim Relocation &rel, uint64_t src) { 1825353358Sdim std::vector<Thunk *> *thunkVec = nullptr; 1826360784Sdim int64_t addend = rel.addend + getPCBias(rel.type); 1827353358Sdim 1828360784Sdim // We use a ((section, offset), addend) pair to find the thunk position if 1829360784Sdim // possible so that we create only one thunk for aliased symbols or ICFed 1830360784Sdim // sections. There may be multiple relocations sharing the same (section, 1831360784Sdim // offset + addend) pair. We may revert the relocation back to its original 1832360784Sdim // non-Thunk target, so we cannot fold offset + addend. 1833353358Sdim if (auto *d = dyn_cast<Defined>(rel.sym)) 1834353358Sdim if (!d->isInPlt() && d->section) 1835360784Sdim thunkVec = &thunkedSymbolsBySectionAndAddend[{ 1836360784Sdim {d->section->repl, d->value}, addend}]; 1837353358Sdim if (!thunkVec) 1838360784Sdim thunkVec = &thunkedSymbols[{rel.sym, addend}]; 1839344779Sdim 1840341825Sdim // Check existing Thunks for Sym to see if they can be reused 1841353358Sdim for (Thunk *t : *thunkVec) 1842353358Sdim if (isThunkSectionCompatible(isec, t->getThunkTargetSym()->section) && 1843353358Sdim t->isCompatibleWith(*isec, rel) && 1844360784Sdim target->inBranchRange(rel.type, src, 1845360784Sdim t->getThunkTargetSym()->getVA(rel.addend) + 1846360784Sdim getPCBias(rel.type))) 1847353358Sdim return std::make_pair(t, false); 1848344779Sdim 1849321369Sdim // No existing compatible Thunk in range, create a new one 1850353358Sdim Thunk *t = addThunk(*isec, rel); 1851353358Sdim thunkVec->push_back(t); 1852353358Sdim return std::make_pair(t, true); 1853303239Sdim} 1854303239Sdim 1855327952Sdim// Return true if the relocation target is an in range Thunk. 1856327952Sdim// Return false if the relocation is not to a Thunk. If the relocation target 1857327952Sdim// was originally to a Thunk, but is no longer in range we revert the 1858327952Sdim// relocation back to its original non-Thunk target. 1859353358Sdimbool ThunkCreator::normalizeExistingThunk(Relocation &rel, uint64_t src) { 1860353358Sdim if (Thunk *t = thunks.lookup(rel.sym)) { 1861360784Sdim if (target->inBranchRange(rel.type, src, 1862360784Sdim rel.sym->getVA(rel.addend) + getPCBias(rel.type))) 1863327952Sdim return true; 1864353358Sdim rel.sym = &t->destination; 1865360784Sdim rel.addend = t->addend; 1866353358Sdim if (rel.sym->isInPlt()) 1867353358Sdim rel.expr = toPlt(rel.expr); 1868327952Sdim } 1869327952Sdim return false; 1870327952Sdim} 1871327952Sdim 1872321369Sdim// Process all relocations from the InputSections that have been assigned 1873327952Sdim// to InputSectionDescriptions and redirect through Thunks if needed. The 1874327952Sdim// function should be called iteratively until it returns false. 1875321369Sdim// 1876327952Sdim// PreConditions: 1877327952Sdim// All InputSections that may need a Thunk are reachable from 1878327952Sdim// OutputSectionCommands. 1879321369Sdim// 1880327952Sdim// All OutputSections have an address and all InputSections have an offset 1881327952Sdim// within the OutputSection. 1882327952Sdim// 1883327952Sdim// The offsets between caller (relocation place) and callee 1884327952Sdim// (relocation target) will not be modified outside of createThunks(). 1885327952Sdim// 1886327952Sdim// PostConditions: 1887327952Sdim// If return value is true then ThunkSections have been inserted into 1888327952Sdim// OutputSections. All relocations that needed a Thunk based on the information 1889327952Sdim// available to createThunks() on entry have been redirected to a Thunk. Note 1890327952Sdim// that adding Thunks changes offsets between caller and callee so more Thunks 1891327952Sdim// may be required. 1892327952Sdim// 1893327952Sdim// If return value is false then no more Thunks are needed, and createThunks has 1894327952Sdim// made no changes. If the target requires range extension thunks, currently 1895327952Sdim// ARM, then any future change in offset between caller and callee risks a 1896327952Sdim// relocation out of range error. 1897353358Sdimbool ThunkCreator::createThunks(ArrayRef<OutputSection *> outputSections) { 1898353358Sdim bool addressesChanged = false; 1899344779Sdim 1900353358Sdim if (pass == 0 && target->getThunkSectionSpacing()) 1901353358Sdim createInitialThunkSections(outputSections); 1902344779Sdim 1903321369Sdim // Create all the Thunks and insert them into synthetic ThunkSections. The 1904327952Sdim // ThunkSections are later inserted back into InputSectionDescriptions. 1905327952Sdim // We separate the creation of ThunkSections from the insertion of the 1906327952Sdim // ThunkSections as ThunkSections are not always inserted into the same 1907327952Sdim // InputSectionDescription as the caller. 1908327952Sdim forEachInputSectionDescription( 1909353358Sdim outputSections, [&](OutputSection *os, InputSectionDescription *isd) { 1910353358Sdim for (InputSection *isec : isd->sections) 1911353358Sdim for (Relocation &rel : isec->relocations) { 1912353358Sdim uint64_t src = isec->getVA(rel.offset); 1913321369Sdim 1914327952Sdim // If we are a relocation to an existing Thunk, check if it is 1915327952Sdim // still in range. If not then Rel will be altered to point to its 1916327952Sdim // original target so another Thunk can be generated. 1917353358Sdim if (pass > 0 && normalizeExistingThunk(rel, src)) 1918327952Sdim continue; 1919327952Sdim 1920353358Sdim if (!target->needsThunk(rel.expr, rel.type, isec->file, src, 1921360784Sdim *rel.sym, rel.addend)) 1922327952Sdim continue; 1923344779Sdim 1924353358Sdim Thunk *t; 1925353358Sdim bool isNew; 1926353358Sdim std::tie(t, isNew) = getThunk(isec, rel, src); 1927344779Sdim 1928353358Sdim if (isNew) { 1929327952Sdim // Find or create a ThunkSection for the new Thunk 1930353358Sdim ThunkSection *ts; 1931353358Sdim if (auto *tis = t->getTargetInputSection()) 1932353358Sdim ts = getISThunkSec(tis); 1933327952Sdim else 1934353358Sdim ts = getISDThunkSec(os, isec, isd, rel.type, src); 1935353358Sdim ts->addThunk(t); 1936353358Sdim thunks[t->getThunkTargetSym()] = t; 1937327952Sdim } 1938344779Sdim 1939327952Sdim // Redirect relocation to Thunk, we never go via the PLT to a Thunk 1940353358Sdim rel.sym = t->getThunkTargetSym(); 1941353358Sdim rel.expr = fromPlt(rel.expr); 1942353358Sdim 1943360784Sdim // On AArch64 and PPC, a jump/call relocation may be encoded as 1944360784Sdim // STT_SECTION + non-zero addend, clear the addend after 1945360784Sdim // redirection. 1946360784Sdim if (config->emachine != EM_MIPS) 1947360784Sdim rel.addend = -getPCBias(rel.type); 1948327952Sdim } 1949344779Sdim 1950353358Sdim for (auto &p : isd->thunkSections) 1951353358Sdim addressesChanged |= p.first->assignOffsets(); 1952327952Sdim }); 1953344779Sdim 1954353358Sdim for (auto &p : thunkedSections) 1955353358Sdim addressesChanged |= p.second->assignOffsets(); 1956341825Sdim 1957321369Sdim // Merge all created synthetic ThunkSections back into OutputSection 1958353358Sdim mergeThunks(outputSections); 1959353358Sdim ++pass; 1960353358Sdim return addressesChanged; 1961303239Sdim} 1962321369Sdim 1963360784Sdimtemplate void scanRelocations<ELF32LE>(InputSectionBase &); 1964360784Sdimtemplate void scanRelocations<ELF32BE>(InputSectionBase &); 1965360784Sdimtemplate void scanRelocations<ELF64LE>(InputSectionBase &); 1966360784Sdimtemplate void scanRelocations<ELF64BE>(InputSectionBase &); 1967360784Sdimtemplate void reportUndefinedSymbols<ELF32LE>(); 1968360784Sdimtemplate void reportUndefinedSymbols<ELF32BE>(); 1969360784Sdimtemplate void reportUndefinedSymbols<ELF64LE>(); 1970360784Sdimtemplate void reportUndefinedSymbols<ELF64BE>(); 1971360784Sdim 1972360784Sdim} // namespace elf 1973360784Sdim} // namespace lld 1974