1 //===- Relocations.cpp ----------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains platform-independent functions to process relocations. 10 // I'll describe the overview of this file here. 11 // 12 // Simple relocations are easy to handle for the linker. For example, 13 // for R_X86_64_PC64 relocs, the linker just has to fix up locations 14 // with the relative offsets to the target symbols. It would just be 15 // reading records from relocation sections and applying them to output. 16 // 17 // But not all relocations are that easy to handle. For example, for 18 // R_386_GOTOFF relocs, the linker has to create new GOT entries for 19 // symbols if they don't exist, and fix up locations with GOT entry 20 // offsets from the beginning of GOT section. So there is more than 21 // fixing addresses in relocation processing. 22 // 23 // ELF defines a large number of complex relocations. 24 // 25 // The functions in this file analyze relocations and do whatever needs 26 // to be done. It includes, but not limited to, the following. 27 // 28 // - create GOT/PLT entries 29 // - create new relocations in .dynsym to let the dynamic linker resolve 30 // them at runtime (since ELF supports dynamic linking, not all 31 // relocations can be resolved at link-time) 32 // - create COPY relocs and reserve space in .bss 33 // - replace expensive relocs (in terms of runtime cost) with cheap ones 34 // - error out infeasible combinations such as PIC and non-relative relocs 35 // 36 // Note that the functions in this file don't actually apply relocations 37 // because it doesn't know about the output file nor the output file buffer. 38 // It instead stores Relocation objects to InputSection's Relocations 39 // vector to let it apply later in InputSection::writeTo. 40 // 41 //===----------------------------------------------------------------------===// 42 43 #include "Relocations.h" 44 #include "Config.h" 45 #include "LinkerScript.h" 46 #include "OutputSections.h" 47 #include "SymbolTable.h" 48 #include "Symbols.h" 49 #include "SyntheticSections.h" 50 #include "Target.h" 51 #include "Thunks.h" 52 #include "lld/Common/ErrorHandler.h" 53 #include "lld/Common/Memory.h" 54 #include "lld/Common/Strings.h" 55 #include "llvm/ADT/SmallSet.h" 56 #include "llvm/Demangle/Demangle.h" 57 #include "llvm/Support/Endian.h" 58 #include "llvm/Support/raw_ostream.h" 59 #include <algorithm> 60 61 using namespace llvm; 62 using namespace llvm::ELF; 63 using namespace llvm::object; 64 using namespace llvm::support::endian; 65 using namespace lld; 66 using namespace lld::elf; 67 68 static Optional<std::string> getLinkerScriptLocation(const Symbol &sym) { 69 for (BaseCommand *base : script->sectionCommands) 70 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) 71 if (cmd->sym == &sym) 72 return cmd->location; 73 return None; 74 } 75 76 static std::string getDefinedLocation(const Symbol &sym) { 77 const char msg[] = "\n>>> defined in "; 78 if (sym.file) 79 return msg + toString(sym.file); 80 if (Optional<std::string> loc = getLinkerScriptLocation(sym)) 81 return msg + *loc; 82 return ""; 83 } 84 85 // Construct a message in the following format. 86 // 87 // >>> defined in /home/alice/src/foo.o 88 // >>> referenced by bar.c:12 (/home/alice/src/bar.c:12) 89 // >>> /home/alice/src/bar.o:(.text+0x1) 90 static std::string getLocation(InputSectionBase &s, const Symbol &sym, 91 uint64_t off) { 92 std::string msg = getDefinedLocation(sym) + "\n>>> referenced by "; 93 std::string src = s.getSrcMsg(sym, off); 94 if (!src.empty()) 95 msg += src + "\n>>> "; 96 return msg + s.getObjMsg(off); 97 } 98 99 void elf::reportRangeError(uint8_t *loc, const Relocation &rel, const Twine &v, 100 int64_t min, uint64_t max) { 101 ErrorPlace errPlace = getErrorPlace(loc); 102 std::string hint; 103 if (rel.sym && !rel.sym->isLocal()) 104 hint = "; references " + lld::toString(*rel.sym) + 105 getDefinedLocation(*rel.sym); 106 107 if (errPlace.isec && errPlace.isec->name.startswith(".debug")) 108 hint += "; consider recompiling with -fdebug-types-section to reduce size " 109 "of debug sections"; 110 111 errorOrWarn(errPlace.loc + "relocation " + lld::toString(rel.type) + 112 " out of range: " + v.str() + " is not in [" + Twine(min).str() + 113 ", " + Twine(max).str() + "]" + hint); 114 } 115 116 void elf::reportRangeError(uint8_t *loc, int64_t v, int n, const Symbol &sym, 117 const Twine &msg) { 118 ErrorPlace errPlace = getErrorPlace(loc); 119 std::string hint; 120 if (!sym.getName().empty()) 121 hint = "; references " + lld::toString(sym) + getDefinedLocation(sym); 122 errorOrWarn(errPlace.loc + msg + " is out of range: " + Twine(v) + 123 " is not in [" + Twine(llvm::minIntN(n)) + ", " + 124 Twine(llvm::maxIntN(n)) + "]" + hint); 125 } 126 127 namespace { 128 // Build a bitmask with one bit set for each RelExpr. 129 // 130 // Constexpr function arguments can't be used in static asserts, so we 131 // use template arguments to build the mask. 132 // But function template partial specializations don't exist (needed 133 // for base case of the recursion), so we need a dummy struct. 134 template <RelExpr... Exprs> struct RelExprMaskBuilder { 135 static inline uint64_t build() { return 0; } 136 }; 137 138 // Specialization for recursive case. 139 template <RelExpr Head, RelExpr... Tail> 140 struct RelExprMaskBuilder<Head, Tail...> { 141 static inline uint64_t build() { 142 static_assert(0 <= Head && Head < 64, 143 "RelExpr is too large for 64-bit mask!"); 144 return (uint64_t(1) << Head) | RelExprMaskBuilder<Tail...>::build(); 145 } 146 }; 147 } // namespace 148 149 // Return true if `Expr` is one of `Exprs`. 150 // There are fewer than 64 RelExpr's, so we can represent any set of 151 // RelExpr's as a constant bit mask and test for membership with a 152 // couple cheap bitwise operations. 153 template <RelExpr... Exprs> bool oneof(RelExpr expr) { 154 assert(0 <= expr && (int)expr < 64 && 155 "RelExpr is too large for 64-bit mask!"); 156 return (uint64_t(1) << expr) & RelExprMaskBuilder<Exprs...>::build(); 157 } 158 159 // This function is similar to the `handleTlsRelocation`. MIPS does not 160 // support any relaxations for TLS relocations so by factoring out MIPS 161 // handling in to the separate function we can simplify the code and do not 162 // pollute other `handleTlsRelocation` by MIPS `ifs` statements. 163 // Mips has a custom MipsGotSection that handles the writing of GOT entries 164 // without dynamic relocations. 165 static unsigned handleMipsTlsRelocation(RelType type, Symbol &sym, 166 InputSectionBase &c, uint64_t offset, 167 int64_t addend, RelExpr expr) { 168 if (expr == R_MIPS_TLSLD) { 169 in.mipsGot->addTlsIndex(*c.file); 170 c.relocations.push_back({expr, type, offset, addend, &sym}); 171 return 1; 172 } 173 if (expr == R_MIPS_TLSGD) { 174 in.mipsGot->addDynTlsEntry(*c.file, sym); 175 c.relocations.push_back({expr, type, offset, addend, &sym}); 176 return 1; 177 } 178 return 0; 179 } 180 181 // Notes about General Dynamic and Local Dynamic TLS models below. They may 182 // require the generation of a pair of GOT entries that have associated dynamic 183 // relocations. The pair of GOT entries created are of the form GOT[e0] Module 184 // Index (Used to find pointer to TLS block at run-time) GOT[e1] Offset of 185 // symbol in TLS block. 186 // 187 // Returns the number of relocations processed. 188 template <class ELFT> 189 static unsigned 190 handleTlsRelocation(RelType type, Symbol &sym, InputSectionBase &c, 191 typename ELFT::uint offset, int64_t addend, RelExpr expr) { 192 if (!sym.isTls()) 193 return 0; 194 195 if (config->emachine == EM_MIPS) 196 return handleMipsTlsRelocation(type, sym, c, offset, addend, expr); 197 198 if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC>( 199 expr) && 200 config->shared) { 201 if (in.got->addDynTlsEntry(sym)) { 202 uint64_t off = in.got->getGlobalDynOffset(sym); 203 mainPart->relaDyn->addAddendOnlyRelocIfNonPreemptible( 204 target->tlsDescRel, in.got, off, sym, target->tlsDescRel); 205 } 206 if (expr != R_TLSDESC_CALL) 207 c.relocations.push_back({expr, type, offset, addend, &sym}); 208 return 1; 209 } 210 211 // ARM, Hexagon and RISC-V do not support GD/LD to IE/LE relaxation. For 212 // PPC64, if the file has missing R_PPC64_TLSGD/R_PPC64_TLSLD, disable 213 // relaxation as well. 214 bool toExecRelax = !config->shared && config->emachine != EM_ARM && 215 config->emachine != EM_HEXAGON && 216 config->emachine != EM_RISCV && 217 !c.file->ppc64DisableTLSRelax; 218 219 // If we are producing an executable and the symbol is non-preemptable, it 220 // must be defined and the code sequence can be relaxed to use Local-Exec. 221 // 222 // ARM and RISC-V do not support any relaxations for TLS relocations, however, 223 // we can omit the DTPMOD dynamic relocations and resolve them at link time 224 // because them are always 1. This may be necessary for static linking as 225 // DTPMOD may not be expected at load time. 226 bool isLocalInExecutable = !sym.isPreemptible && !config->shared; 227 228 // Local Dynamic is for access to module local TLS variables, while still 229 // being suitable for being dynamically loaded via dlopen. GOT[e0] is the 230 // module index, with a special value of 0 for the current module. GOT[e1] is 231 // unused. There only needs to be one module index entry. 232 if (oneof<R_TLSLD_GOT, R_TLSLD_GOTPLT, R_TLSLD_PC, R_TLSLD_HINT>( 233 expr)) { 234 // Local-Dynamic relocs can be relaxed to Local-Exec. 235 if (toExecRelax) { 236 c.relocations.push_back( 237 {target->adjustTlsExpr(type, R_RELAX_TLS_LD_TO_LE), type, offset, 238 addend, &sym}); 239 return target->getTlsGdRelaxSkip(type); 240 } 241 if (expr == R_TLSLD_HINT) 242 return 1; 243 if (in.got->addTlsIndex()) { 244 if (isLocalInExecutable) 245 in.got->relocations.push_back( 246 {R_ADDEND, target->symbolicRel, in.got->getTlsIndexOff(), 1, &sym}); 247 else 248 mainPart->relaDyn->addReloc( 249 {target->tlsModuleIndexRel, in.got, in.got->getTlsIndexOff()}); 250 } 251 c.relocations.push_back({expr, type, offset, addend, &sym}); 252 return 1; 253 } 254 255 // Local-Dynamic relocs can be relaxed to Local-Exec. 256 if (expr == R_DTPREL && toExecRelax) { 257 c.relocations.push_back({target->adjustTlsExpr(type, R_RELAX_TLS_LD_TO_LE), 258 type, offset, addend, &sym}); 259 return 1; 260 } 261 262 // Local-Dynamic sequence where offset of tls variable relative to dynamic 263 // thread pointer is stored in the got. This cannot be relaxed to Local-Exec. 264 if (expr == R_TLSLD_GOT_OFF) { 265 if (!sym.isInGot()) { 266 in.got->addEntry(sym); 267 uint64_t off = sym.getGotOffset(); 268 in.got->relocations.push_back( 269 {R_ABS, target->tlsOffsetRel, off, 0, &sym}); 270 } 271 c.relocations.push_back({expr, type, offset, addend, &sym}); 272 return 1; 273 } 274 275 if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC, 276 R_TLSGD_GOT, R_TLSGD_GOTPLT, R_TLSGD_PC>(expr)) { 277 if (!toExecRelax) { 278 if (in.got->addDynTlsEntry(sym)) { 279 uint64_t off = in.got->getGlobalDynOffset(sym); 280 281 if (isLocalInExecutable) 282 // Write one to the GOT slot. 283 in.got->relocations.push_back( 284 {R_ADDEND, target->symbolicRel, off, 1, &sym}); 285 else 286 mainPart->relaDyn->addSymbolReloc(target->tlsModuleIndexRel, in.got, 287 off, sym); 288 289 // If the symbol is preemptible we need the dynamic linker to write 290 // the offset too. 291 uint64_t offsetOff = off + config->wordsize; 292 if (sym.isPreemptible) 293 mainPart->relaDyn->addSymbolReloc(target->tlsOffsetRel, in.got, 294 offsetOff, sym); 295 else 296 in.got->relocations.push_back( 297 {R_ABS, target->tlsOffsetRel, offsetOff, 0, &sym}); 298 } 299 c.relocations.push_back({expr, type, offset, addend, &sym}); 300 return 1; 301 } 302 303 // Global-Dynamic relocs can be relaxed to Initial-Exec or Local-Exec 304 // depending on the symbol being locally defined or not. 305 if (sym.isPreemptible) { 306 c.relocations.push_back( 307 {target->adjustTlsExpr(type, R_RELAX_TLS_GD_TO_IE), type, offset, 308 addend, &sym}); 309 if (!sym.isInGot()) { 310 in.got->addEntry(sym); 311 mainPart->relaDyn->addSymbolReloc(target->tlsGotRel, in.got, 312 sym.getGotOffset(), sym); 313 } 314 } else { 315 c.relocations.push_back( 316 {target->adjustTlsExpr(type, R_RELAX_TLS_GD_TO_LE), type, offset, 317 addend, &sym}); 318 } 319 return target->getTlsGdRelaxSkip(type); 320 } 321 322 // Initial-Exec relocs can be relaxed to Local-Exec if the symbol is locally 323 // defined. 324 if (oneof<R_GOT, R_GOTPLT, R_GOT_PC, R_AARCH64_GOT_PAGE_PC, R_GOT_OFF, 325 R_TLSIE_HINT>(expr) && 326 toExecRelax && isLocalInExecutable) { 327 c.relocations.push_back({R_RELAX_TLS_IE_TO_LE, type, offset, addend, &sym}); 328 return 1; 329 } 330 331 if (expr == R_TLSIE_HINT) 332 return 1; 333 return 0; 334 } 335 336 static RelType getMipsPairType(RelType type, bool isLocal) { 337 switch (type) { 338 case R_MIPS_HI16: 339 return R_MIPS_LO16; 340 case R_MIPS_GOT16: 341 // In case of global symbol, the R_MIPS_GOT16 relocation does not 342 // have a pair. Each global symbol has a unique entry in the GOT 343 // and a corresponding instruction with help of the R_MIPS_GOT16 344 // relocation loads an address of the symbol. In case of local 345 // symbol, the R_MIPS_GOT16 relocation creates a GOT entry to hold 346 // the high 16 bits of the symbol's value. A paired R_MIPS_LO16 347 // relocations handle low 16 bits of the address. That allows 348 // to allocate only one GOT entry for every 64 KBytes of local data. 349 return isLocal ? R_MIPS_LO16 : R_MIPS_NONE; 350 case R_MICROMIPS_GOT16: 351 return isLocal ? R_MICROMIPS_LO16 : R_MIPS_NONE; 352 case R_MIPS_PCHI16: 353 return R_MIPS_PCLO16; 354 case R_MICROMIPS_HI16: 355 return R_MICROMIPS_LO16; 356 default: 357 return R_MIPS_NONE; 358 } 359 } 360 361 // True if non-preemptable symbol always has the same value regardless of where 362 // the DSO is loaded. 363 static bool isAbsolute(const Symbol &sym) { 364 if (sym.isUndefWeak()) 365 return true; 366 if (const auto *dr = dyn_cast<Defined>(&sym)) 367 return dr->section == nullptr; // Absolute symbol. 368 return false; 369 } 370 371 static bool isAbsoluteValue(const Symbol &sym) { 372 return isAbsolute(sym) || sym.isTls(); 373 } 374 375 // Returns true if Expr refers a PLT entry. 376 static bool needsPlt(RelExpr expr) { 377 return oneof<R_PLT_PC, R_PPC32_PLTREL, R_PPC64_CALL_PLT, R_PLT>(expr); 378 } 379 380 // Returns true if Expr refers a GOT entry. Note that this function 381 // returns false for TLS variables even though they need GOT, because 382 // TLS variables uses GOT differently than the regular variables. 383 static bool needsGot(RelExpr expr) { 384 return oneof<R_GOT, R_GOT_OFF, R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOT_OFF, 385 R_MIPS_GOT_OFF32, R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTPLT, 386 R_AARCH64_GOT_PAGE>(expr); 387 } 388 389 // True if this expression is of the form Sym - X, where X is a position in the 390 // file (PC, or GOT for example). 391 static bool isRelExpr(RelExpr expr) { 392 return oneof<R_PC, R_GOTREL, R_GOTPLTREL, R_MIPS_GOTREL, R_PPC64_CALL, 393 R_PPC64_RELAX_TOC, R_AARCH64_PAGE_PC, R_RELAX_GOT_PC, 394 R_RISCV_PC_INDIRECT, R_PPC64_RELAX_GOT_PC>(expr); 395 } 396 397 // Returns true if a given relocation can be computed at link-time. 398 // 399 // For instance, we know the offset from a relocation to its target at 400 // link-time if the relocation is PC-relative and refers a 401 // non-interposable function in the same executable. This function 402 // will return true for such relocation. 403 // 404 // If this function returns false, that means we need to emit a 405 // dynamic relocation so that the relocation will be fixed at load-time. 406 static bool isStaticLinkTimeConstant(RelExpr e, RelType type, const Symbol &sym, 407 InputSectionBase &s, uint64_t relOff) { 408 // These expressions always compute a constant 409 if (oneof<R_DTPREL, R_GOTPLT, R_GOT_OFF, R_TLSLD_GOT_OFF, 410 R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOTREL, R_MIPS_GOT_OFF, 411 R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC, R_MIPS_TLSGD, 412 R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC, R_GOTPLTONLY_PC, 413 R_PLT_PC, R_TLSGD_GOT, R_TLSGD_GOTPLT, R_TLSGD_PC, R_PPC32_PLTREL, 414 R_PPC64_CALL_PLT, R_PPC64_RELAX_TOC, R_RISCV_ADD, R_TLSDESC_CALL, 415 R_TLSDESC_PC, R_AARCH64_TLSDESC_PAGE, R_TLSLD_HINT, R_TLSIE_HINT, 416 R_AARCH64_GOT_PAGE>( 417 e)) 418 return true; 419 420 // These never do, except if the entire file is position dependent or if 421 // only the low bits are used. 422 if (e == R_GOT || e == R_PLT || e == R_TLSDESC) 423 return target->usesOnlyLowPageBits(type) || !config->isPic; 424 425 if (sym.isPreemptible) 426 return false; 427 if (!config->isPic) 428 return true; 429 430 // The size of a non preemptible symbol is a constant. 431 if (e == R_SIZE) 432 return true; 433 434 // For the target and the relocation, we want to know if they are 435 // absolute or relative. 436 bool absVal = isAbsoluteValue(sym); 437 bool relE = isRelExpr(e); 438 if (absVal && !relE) 439 return true; 440 if (!absVal && relE) 441 return true; 442 if (!absVal && !relE) 443 return target->usesOnlyLowPageBits(type); 444 445 assert(absVal && relE); 446 447 // Allow R_PLT_PC (optimized to R_PC here) to a hidden undefined weak symbol 448 // in PIC mode. This is a little strange, but it allows us to link function 449 // calls to such symbols (e.g. glibc/stdlib/exit.c:__run_exit_handlers). 450 // Normally such a call will be guarded with a comparison, which will load a 451 // zero from the GOT. 452 if (sym.isUndefWeak()) 453 return true; 454 455 // We set the final symbols values for linker script defined symbols later. 456 // They always can be computed as a link time constant. 457 if (sym.scriptDefined) 458 return true; 459 460 error("relocation " + toString(type) + " cannot refer to absolute symbol: " + 461 toString(sym) + getLocation(s, sym, relOff)); 462 return true; 463 } 464 465 static RelExpr toPlt(RelExpr expr) { 466 switch (expr) { 467 case R_PPC64_CALL: 468 return R_PPC64_CALL_PLT; 469 case R_PC: 470 return R_PLT_PC; 471 case R_ABS: 472 return R_PLT; 473 default: 474 return expr; 475 } 476 } 477 478 static RelExpr fromPlt(RelExpr expr) { 479 // We decided not to use a plt. Optimize a reference to the plt to a 480 // reference to the symbol itself. 481 switch (expr) { 482 case R_PLT_PC: 483 case R_PPC32_PLTREL: 484 return R_PC; 485 case R_PPC64_CALL_PLT: 486 return R_PPC64_CALL; 487 case R_PLT: 488 return R_ABS; 489 default: 490 return expr; 491 } 492 } 493 494 // Returns true if a given shared symbol is in a read-only segment in a DSO. 495 template <class ELFT> static bool isReadOnly(SharedSymbol &ss) { 496 using Elf_Phdr = typename ELFT::Phdr; 497 498 // Determine if the symbol is read-only by scanning the DSO's program headers. 499 const SharedFile &file = ss.getFile(); 500 for (const Elf_Phdr &phdr : 501 check(file.template getObj<ELFT>().program_headers())) 502 if ((phdr.p_type == ELF::PT_LOAD || phdr.p_type == ELF::PT_GNU_RELRO) && 503 !(phdr.p_flags & ELF::PF_W) && ss.value >= phdr.p_vaddr && 504 ss.value < phdr.p_vaddr + phdr.p_memsz) 505 return true; 506 return false; 507 } 508 509 // Returns symbols at the same offset as a given symbol, including SS itself. 510 // 511 // If two or more symbols are at the same offset, and at least one of 512 // them are copied by a copy relocation, all of them need to be copied. 513 // Otherwise, they would refer to different places at runtime. 514 template <class ELFT> 515 static SmallSet<SharedSymbol *, 4> getSymbolsAt(SharedSymbol &ss) { 516 using Elf_Sym = typename ELFT::Sym; 517 518 SharedFile &file = ss.getFile(); 519 520 SmallSet<SharedSymbol *, 4> ret; 521 for (const Elf_Sym &s : file.template getGlobalELFSyms<ELFT>()) { 522 if (s.st_shndx == SHN_UNDEF || s.st_shndx == SHN_ABS || 523 s.getType() == STT_TLS || s.st_value != ss.value) 524 continue; 525 StringRef name = check(s.getName(file.getStringTable())); 526 Symbol *sym = symtab->find(name); 527 if (auto *alias = dyn_cast_or_null<SharedSymbol>(sym)) 528 ret.insert(alias); 529 } 530 531 // The loop does not check SHT_GNU_verneed, so ret does not contain 532 // non-default version symbols. If ss has a non-default version, ret won't 533 // contain ss. Just add ss unconditionally. If a non-default version alias is 534 // separately copy relocated, it and ss will have different addresses. 535 // Fortunately this case is impractical and fails with GNU ld as well. 536 ret.insert(&ss); 537 return ret; 538 } 539 540 // When a symbol is copy relocated or we create a canonical plt entry, it is 541 // effectively a defined symbol. In the case of copy relocation the symbol is 542 // in .bss and in the case of a canonical plt entry it is in .plt. This function 543 // replaces the existing symbol with a Defined pointing to the appropriate 544 // location. 545 static void replaceWithDefined(Symbol &sym, SectionBase *sec, uint64_t value, 546 uint64_t size) { 547 Symbol old = sym; 548 549 sym.replace(Defined{sym.file, sym.getName(), sym.binding, sym.stOther, 550 sym.type, value, size, sec}); 551 552 sym.pltIndex = old.pltIndex; 553 sym.gotIndex = old.gotIndex; 554 sym.verdefIndex = old.verdefIndex; 555 sym.exportDynamic = true; 556 sym.isUsedInRegularObj = true; 557 } 558 559 // Reserve space in .bss or .bss.rel.ro for copy relocation. 560 // 561 // The copy relocation is pretty much a hack. If you use a copy relocation 562 // in your program, not only the symbol name but the symbol's size, RW/RO 563 // bit and alignment become part of the ABI. In addition to that, if the 564 // symbol has aliases, the aliases become part of the ABI. That's subtle, 565 // but if you violate that implicit ABI, that can cause very counter- 566 // intuitive consequences. 567 // 568 // So, what is the copy relocation? It's for linking non-position 569 // independent code to DSOs. In an ideal world, all references to data 570 // exported by DSOs should go indirectly through GOT. But if object files 571 // are compiled as non-PIC, all data references are direct. There is no 572 // way for the linker to transform the code to use GOT, as machine 573 // instructions are already set in stone in object files. This is where 574 // the copy relocation takes a role. 575 // 576 // A copy relocation instructs the dynamic linker to copy data from a DSO 577 // to a specified address (which is usually in .bss) at load-time. If the 578 // static linker (that's us) finds a direct data reference to a DSO 579 // symbol, it creates a copy relocation, so that the symbol can be 580 // resolved as if it were in .bss rather than in a DSO. 581 // 582 // As you can see in this function, we create a copy relocation for the 583 // dynamic linker, and the relocation contains not only symbol name but 584 // various other information about the symbol. So, such attributes become a 585 // part of the ABI. 586 // 587 // Note for application developers: I can give you a piece of advice if 588 // you are writing a shared library. You probably should export only 589 // functions from your library. You shouldn't export variables. 590 // 591 // As an example what can happen when you export variables without knowing 592 // the semantics of copy relocations, assume that you have an exported 593 // variable of type T. It is an ABI-breaking change to add new members at 594 // end of T even though doing that doesn't change the layout of the 595 // existing members. That's because the space for the new members are not 596 // reserved in .bss unless you recompile the main program. That means they 597 // are likely to overlap with other data that happens to be laid out next 598 // to the variable in .bss. This kind of issue is sometimes very hard to 599 // debug. What's a solution? Instead of exporting a variable V from a DSO, 600 // define an accessor getV(). 601 template <class ELFT> static void addCopyRelSymbol(SharedSymbol &ss) { 602 // Copy relocation against zero-sized symbol doesn't make sense. 603 uint64_t symSize = ss.getSize(); 604 if (symSize == 0 || ss.alignment == 0) 605 fatal("cannot create a copy relocation for symbol " + toString(ss)); 606 607 // See if this symbol is in a read-only segment. If so, preserve the symbol's 608 // memory protection by reserving space in the .bss.rel.ro section. 609 bool isRO = isReadOnly<ELFT>(ss); 610 BssSection *sec = 611 make<BssSection>(isRO ? ".bss.rel.ro" : ".bss", symSize, ss.alignment); 612 OutputSection *osec = (isRO ? in.bssRelRo : in.bss)->getParent(); 613 614 // At this point, sectionBases has been migrated to sections. Append sec to 615 // sections. 616 if (osec->sectionCommands.empty() || 617 !isa<InputSectionDescription>(osec->sectionCommands.back())) 618 osec->sectionCommands.push_back(make<InputSectionDescription>("")); 619 auto *isd = cast<InputSectionDescription>(osec->sectionCommands.back()); 620 isd->sections.push_back(sec); 621 osec->commitSection(sec); 622 623 // Look through the DSO's dynamic symbol table for aliases and create a 624 // dynamic symbol for each one. This causes the copy relocation to correctly 625 // interpose any aliases. 626 for (SharedSymbol *sym : getSymbolsAt<ELFT>(ss)) 627 replaceWithDefined(*sym, sec, 0, sym->size); 628 629 mainPart->relaDyn->addSymbolReloc(target->copyRel, sec, 0, ss); 630 } 631 632 // MIPS has an odd notion of "paired" relocations to calculate addends. 633 // For example, if a relocation is of R_MIPS_HI16, there must be a 634 // R_MIPS_LO16 relocation after that, and an addend is calculated using 635 // the two relocations. 636 template <class ELFT, class RelTy> 637 static int64_t computeMipsAddend(const RelTy &rel, const RelTy *end, 638 InputSectionBase &sec, RelExpr expr, 639 bool isLocal) { 640 if (expr == R_MIPS_GOTREL && isLocal) 641 return sec.getFile<ELFT>()->mipsGp0; 642 643 // The ABI says that the paired relocation is used only for REL. 644 // See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf 645 if (RelTy::IsRela) 646 return 0; 647 648 RelType type = rel.getType(config->isMips64EL); 649 uint32_t pairTy = getMipsPairType(type, isLocal); 650 if (pairTy == R_MIPS_NONE) 651 return 0; 652 653 const uint8_t *buf = sec.data().data(); 654 uint32_t symIndex = rel.getSymbol(config->isMips64EL); 655 656 // To make things worse, paired relocations might not be contiguous in 657 // the relocation table, so we need to do linear search. *sigh* 658 for (const RelTy *ri = &rel; ri != end; ++ri) 659 if (ri->getType(config->isMips64EL) == pairTy && 660 ri->getSymbol(config->isMips64EL) == symIndex) 661 return target->getImplicitAddend(buf + ri->r_offset, pairTy); 662 663 warn("can't find matching " + toString(pairTy) + " relocation for " + 664 toString(type)); 665 return 0; 666 } 667 668 // Returns an addend of a given relocation. If it is RELA, an addend 669 // is in a relocation itself. If it is REL, we need to read it from an 670 // input section. 671 template <class ELFT, class RelTy> 672 static int64_t computeAddend(const RelTy &rel, const RelTy *end, 673 InputSectionBase &sec, RelExpr expr, 674 bool isLocal) { 675 int64_t addend; 676 RelType type = rel.getType(config->isMips64EL); 677 678 if (RelTy::IsRela) { 679 addend = getAddend<ELFT>(rel); 680 } else { 681 const uint8_t *buf = sec.data().data(); 682 addend = target->getImplicitAddend(buf + rel.r_offset, type); 683 } 684 685 if (config->emachine == EM_PPC64 && config->isPic && type == R_PPC64_TOC) 686 addend += getPPC64TocBase(); 687 if (config->emachine == EM_MIPS) 688 addend += computeMipsAddend<ELFT>(rel, end, sec, expr, isLocal); 689 690 return addend; 691 } 692 693 // Custom error message if Sym is defined in a discarded section. 694 template <class ELFT> 695 static std::string maybeReportDiscarded(Undefined &sym) { 696 auto *file = dyn_cast_or_null<ObjFile<ELFT>>(sym.file); 697 if (!file || !sym.discardedSecIdx || 698 file->getSections()[sym.discardedSecIdx] != &InputSection::discarded) 699 return ""; 700 ArrayRef<Elf_Shdr_Impl<ELFT>> objSections = 701 CHECK(file->getObj().sections(), file); 702 703 std::string msg; 704 if (sym.type == ELF::STT_SECTION) { 705 msg = "relocation refers to a discarded section: "; 706 msg += CHECK( 707 file->getObj().getSectionName(objSections[sym.discardedSecIdx]), file); 708 } else { 709 msg = "relocation refers to a symbol in a discarded section: " + 710 toString(sym); 711 } 712 msg += "\n>>> defined in " + toString(file); 713 714 Elf_Shdr_Impl<ELFT> elfSec = objSections[sym.discardedSecIdx - 1]; 715 if (elfSec.sh_type != SHT_GROUP) 716 return msg; 717 718 // If the discarded section is a COMDAT. 719 StringRef signature = file->getShtGroupSignature(objSections, elfSec); 720 if (const InputFile *prevailing = 721 symtab->comdatGroups.lookup(CachedHashStringRef(signature))) 722 msg += "\n>>> section group signature: " + signature.str() + 723 "\n>>> prevailing definition is in " + toString(prevailing); 724 return msg; 725 } 726 727 // Undefined diagnostics are collected in a vector and emitted once all of 728 // them are known, so that some postprocessing on the list of undefined symbols 729 // can happen before lld emits diagnostics. 730 struct UndefinedDiag { 731 Symbol *sym; 732 struct Loc { 733 InputSectionBase *sec; 734 uint64_t offset; 735 }; 736 std::vector<Loc> locs; 737 bool isWarning; 738 }; 739 740 static std::vector<UndefinedDiag> undefs; 741 742 // Check whether the definition name def is a mangled function name that matches 743 // the reference name ref. 744 static bool canSuggestExternCForCXX(StringRef ref, StringRef def) { 745 llvm::ItaniumPartialDemangler d; 746 std::string name = def.str(); 747 if (d.partialDemangle(name.c_str())) 748 return false; 749 char *buf = d.getFunctionName(nullptr, nullptr); 750 if (!buf) 751 return false; 752 bool ret = ref == buf; 753 free(buf); 754 return ret; 755 } 756 757 // Suggest an alternative spelling of an "undefined symbol" diagnostic. Returns 758 // the suggested symbol, which is either in the symbol table, or in the same 759 // file of sym. 760 template <class ELFT> 761 static const Symbol *getAlternativeSpelling(const Undefined &sym, 762 std::string &pre_hint, 763 std::string &post_hint) { 764 DenseMap<StringRef, const Symbol *> map; 765 if (auto *file = dyn_cast_or_null<ObjFile<ELFT>>(sym.file)) { 766 // If sym is a symbol defined in a discarded section, maybeReportDiscarded() 767 // will give an error. Don't suggest an alternative spelling. 768 if (file && sym.discardedSecIdx != 0 && 769 file->getSections()[sym.discardedSecIdx] == &InputSection::discarded) 770 return nullptr; 771 772 // Build a map of local defined symbols. 773 for (const Symbol *s : sym.file->getSymbols()) 774 if (s->isLocal() && s->isDefined() && !s->getName().empty()) 775 map.try_emplace(s->getName(), s); 776 } 777 778 auto suggest = [&](StringRef newName) -> const Symbol * { 779 // If defined locally. 780 if (const Symbol *s = map.lookup(newName)) 781 return s; 782 783 // If in the symbol table and not undefined. 784 if (const Symbol *s = symtab->find(newName)) 785 if (!s->isUndefined()) 786 return s; 787 788 return nullptr; 789 }; 790 791 // This loop enumerates all strings of Levenshtein distance 1 as typo 792 // correction candidates and suggests the one that exists as a non-undefined 793 // symbol. 794 StringRef name = sym.getName(); 795 for (size_t i = 0, e = name.size(); i != e + 1; ++i) { 796 // Insert a character before name[i]. 797 std::string newName = (name.substr(0, i) + "0" + name.substr(i)).str(); 798 for (char c = '0'; c <= 'z'; ++c) { 799 newName[i] = c; 800 if (const Symbol *s = suggest(newName)) 801 return s; 802 } 803 if (i == e) 804 break; 805 806 // Substitute name[i]. 807 newName = std::string(name); 808 for (char c = '0'; c <= 'z'; ++c) { 809 newName[i] = c; 810 if (const Symbol *s = suggest(newName)) 811 return s; 812 } 813 814 // Transpose name[i] and name[i+1]. This is of edit distance 2 but it is 815 // common. 816 if (i + 1 < e) { 817 newName[i] = name[i + 1]; 818 newName[i + 1] = name[i]; 819 if (const Symbol *s = suggest(newName)) 820 return s; 821 } 822 823 // Delete name[i]. 824 newName = (name.substr(0, i) + name.substr(i + 1)).str(); 825 if (const Symbol *s = suggest(newName)) 826 return s; 827 } 828 829 // Case mismatch, e.g. Foo vs FOO. 830 for (auto &it : map) 831 if (name.equals_insensitive(it.first)) 832 return it.second; 833 for (Symbol *sym : symtab->symbols()) 834 if (!sym->isUndefined() && name.equals_insensitive(sym->getName())) 835 return sym; 836 837 // The reference may be a mangled name while the definition is not. Suggest a 838 // missing extern "C". 839 if (name.startswith("_Z")) { 840 std::string buf = name.str(); 841 llvm::ItaniumPartialDemangler d; 842 if (!d.partialDemangle(buf.c_str())) 843 if (char *buf = d.getFunctionName(nullptr, nullptr)) { 844 const Symbol *s = suggest(buf); 845 free(buf); 846 if (s) { 847 pre_hint = ": extern \"C\" "; 848 return s; 849 } 850 } 851 } else { 852 const Symbol *s = nullptr; 853 for (auto &it : map) 854 if (canSuggestExternCForCXX(name, it.first)) { 855 s = it.second; 856 break; 857 } 858 if (!s) 859 for (Symbol *sym : symtab->symbols()) 860 if (canSuggestExternCForCXX(name, sym->getName())) { 861 s = sym; 862 break; 863 } 864 if (s) { 865 pre_hint = " to declare "; 866 post_hint = " as extern \"C\"?"; 867 return s; 868 } 869 } 870 871 return nullptr; 872 } 873 874 template <class ELFT> 875 static void reportUndefinedSymbol(const UndefinedDiag &undef, 876 bool correctSpelling) { 877 Symbol &sym = *undef.sym; 878 879 auto visibility = [&]() -> std::string { 880 switch (sym.visibility) { 881 case STV_INTERNAL: 882 return "internal "; 883 case STV_HIDDEN: 884 return "hidden "; 885 case STV_PROTECTED: 886 return "protected "; 887 default: 888 return ""; 889 } 890 }; 891 892 std::string msg = maybeReportDiscarded<ELFT>(cast<Undefined>(sym)); 893 if (msg.empty()) 894 msg = "undefined " + visibility() + "symbol: " + toString(sym); 895 896 const size_t maxUndefReferences = 3; 897 size_t i = 0; 898 for (UndefinedDiag::Loc l : undef.locs) { 899 if (i >= maxUndefReferences) 900 break; 901 InputSectionBase &sec = *l.sec; 902 uint64_t offset = l.offset; 903 904 msg += "\n>>> referenced by "; 905 std::string src = sec.getSrcMsg(sym, offset); 906 if (!src.empty()) 907 msg += src + "\n>>> "; 908 msg += sec.getObjMsg(offset); 909 i++; 910 } 911 912 if (i < undef.locs.size()) 913 msg += ("\n>>> referenced " + Twine(undef.locs.size() - i) + " more times") 914 .str(); 915 916 if (correctSpelling) { 917 std::string pre_hint = ": ", post_hint; 918 if (const Symbol *corrected = getAlternativeSpelling<ELFT>( 919 cast<Undefined>(sym), pre_hint, post_hint)) { 920 msg += "\n>>> did you mean" + pre_hint + toString(*corrected) + post_hint; 921 if (corrected->file) 922 msg += "\n>>> defined in: " + toString(corrected->file); 923 } 924 } 925 926 if (sym.getName().startswith("_ZTV")) 927 msg += 928 "\n>>> the vtable symbol may be undefined because the class is missing " 929 "its key function (see https://lld.llvm.org/missingkeyfunction)"; 930 931 if (undef.isWarning) 932 warn(msg); 933 else 934 error(msg, ErrorTag::SymbolNotFound, {sym.getName()}); 935 } 936 937 template <class ELFT> void elf::reportUndefinedSymbols() { 938 // Find the first "undefined symbol" diagnostic for each diagnostic, and 939 // collect all "referenced from" lines at the first diagnostic. 940 DenseMap<Symbol *, UndefinedDiag *> firstRef; 941 for (UndefinedDiag &undef : undefs) { 942 assert(undef.locs.size() == 1); 943 if (UndefinedDiag *canon = firstRef.lookup(undef.sym)) { 944 canon->locs.push_back(undef.locs[0]); 945 undef.locs.clear(); 946 } else 947 firstRef[undef.sym] = &undef; 948 } 949 950 // Enable spell corrector for the first 2 diagnostics. 951 for (auto it : enumerate(undefs)) 952 if (!it.value().locs.empty()) 953 reportUndefinedSymbol<ELFT>(it.value(), it.index() < 2); 954 undefs.clear(); 955 } 956 957 // Report an undefined symbol if necessary. 958 // Returns true if the undefined symbol will produce an error message. 959 static bool maybeReportUndefined(Symbol &sym, InputSectionBase &sec, 960 uint64_t offset) { 961 if (!sym.isUndefined()) 962 return false; 963 // If versioned, issue an error (even if the symbol is weak) because we don't 964 // know the defining filename which is required to construct a Verneed entry. 965 if (*sym.getVersionSuffix() == '@') { 966 undefs.push_back({&sym, {{&sec, offset}}, false}); 967 return true; 968 } 969 if (sym.isWeak()) 970 return false; 971 972 bool canBeExternal = !sym.isLocal() && sym.visibility == STV_DEFAULT; 973 if (config->unresolvedSymbols == UnresolvedPolicy::Ignore && canBeExternal) 974 return false; 975 976 // clang (as of 2019-06-12) / gcc (as of 8.2.1) PPC64 may emit a .rela.toc 977 // which references a switch table in a discarded .rodata/.text section. The 978 // .toc and the .rela.toc are incorrectly not placed in the comdat. The ELF 979 // spec says references from outside the group to a STB_LOCAL symbol are not 980 // allowed. Work around the bug. 981 // 982 // PPC32 .got2 is similar but cannot be fixed. Multiple .got2 is infeasible 983 // because .LC0-.LTOC is not representable if the two labels are in different 984 // .got2 985 if (cast<Undefined>(sym).discardedSecIdx != 0 && 986 (sec.name == ".got2" || sec.name == ".toc")) 987 return false; 988 989 bool isWarning = 990 (config->unresolvedSymbols == UnresolvedPolicy::Warn && canBeExternal) || 991 config->noinhibitExec; 992 undefs.push_back({&sym, {{&sec, offset}}, isWarning}); 993 return !isWarning; 994 } 995 996 // MIPS N32 ABI treats series of successive relocations with the same offset 997 // as a single relocation. The similar approach used by N64 ABI, but this ABI 998 // packs all relocations into the single relocation record. Here we emulate 999 // this for the N32 ABI. Iterate over relocation with the same offset and put 1000 // theirs types into the single bit-set. 1001 template <class RelTy> static RelType getMipsN32RelType(RelTy *&rel, RelTy *end) { 1002 RelType type = 0; 1003 uint64_t offset = rel->r_offset; 1004 1005 int n = 0; 1006 while (rel != end && rel->r_offset == offset) 1007 type |= (rel++)->getType(config->isMips64EL) << (8 * n++); 1008 return type; 1009 } 1010 1011 // .eh_frame sections are mergeable input sections, so their input 1012 // offsets are not linearly mapped to output section. For each input 1013 // offset, we need to find a section piece containing the offset and 1014 // add the piece's base address to the input offset to compute the 1015 // output offset. That isn't cheap. 1016 // 1017 // This class is to speed up the offset computation. When we process 1018 // relocations, we access offsets in the monotonically increasing 1019 // order. So we can optimize for that access pattern. 1020 // 1021 // For sections other than .eh_frame, this class doesn't do anything. 1022 namespace { 1023 class OffsetGetter { 1024 public: 1025 explicit OffsetGetter(InputSectionBase &sec) { 1026 if (auto *eh = dyn_cast<EhInputSection>(&sec)) 1027 pieces = eh->pieces; 1028 } 1029 1030 // Translates offsets in input sections to offsets in output sections. 1031 // Given offset must increase monotonically. We assume that Piece is 1032 // sorted by inputOff. 1033 uint64_t get(uint64_t off) { 1034 if (pieces.empty()) 1035 return off; 1036 1037 while (i != pieces.size() && pieces[i].inputOff + pieces[i].size <= off) 1038 ++i; 1039 if (i == pieces.size()) 1040 fatal(".eh_frame: relocation is not in any piece"); 1041 1042 // Pieces must be contiguous, so there must be no holes in between. 1043 assert(pieces[i].inputOff <= off && "Relocation not in any piece"); 1044 1045 // Offset -1 means that the piece is dead (i.e. garbage collected). 1046 if (pieces[i].outputOff == -1) 1047 return -1; 1048 return pieces[i].outputOff + off - pieces[i].inputOff; 1049 } 1050 1051 private: 1052 ArrayRef<EhSectionPiece> pieces; 1053 size_t i = 0; 1054 }; 1055 } // namespace 1056 1057 static void addRelativeReloc(InputSectionBase *isec, uint64_t offsetInSec, 1058 Symbol &sym, int64_t addend, RelExpr expr, 1059 RelType type) { 1060 Partition &part = isec->getPartition(); 1061 1062 // Add a relative relocation. If relrDyn section is enabled, and the 1063 // relocation offset is guaranteed to be even, add the relocation to 1064 // the relrDyn section, otherwise add it to the relaDyn section. 1065 // relrDyn sections don't support odd offsets. Also, relrDyn sections 1066 // don't store the addend values, so we must write it to the relocated 1067 // address. 1068 if (part.relrDyn && isec->alignment >= 2 && offsetInSec % 2 == 0) { 1069 isec->relocations.push_back({expr, type, offsetInSec, addend, &sym}); 1070 part.relrDyn->relocs.push_back({isec, offsetInSec}); 1071 return; 1072 } 1073 part.relaDyn->addRelativeReloc(target->relativeRel, isec, offsetInSec, sym, 1074 addend, type, expr); 1075 } 1076 1077 template <class PltSection, class GotPltSection> 1078 static void addPltEntry(PltSection *plt, GotPltSection *gotPlt, 1079 RelocationBaseSection *rel, RelType type, Symbol &sym) { 1080 plt->addEntry(sym); 1081 gotPlt->addEntry(sym); 1082 rel->addReloc({type, gotPlt, sym.getGotPltOffset(), 1083 sym.isPreemptible ? DynamicReloc::AgainstSymbol 1084 : DynamicReloc::AddendOnlyWithTargetVA, 1085 sym, 0, R_ABS}); 1086 } 1087 1088 static void addGotEntry(Symbol &sym) { 1089 in.got->addEntry(sym); 1090 1091 RelExpr expr = sym.isTls() ? R_TPREL : R_ABS; 1092 uint64_t off = sym.getGotOffset(); 1093 1094 // If a GOT slot value can be calculated at link-time, which is now, 1095 // we can just fill that out. 1096 // 1097 // (We don't actually write a value to a GOT slot right now, but we 1098 // add a static relocation to a Relocations vector so that 1099 // InputSection::relocate will do the work for us. We may be able 1100 // to just write a value now, but it is a TODO.) 1101 bool isLinkTimeConstant = 1102 !sym.isPreemptible && (!config->isPic || isAbsolute(sym)); 1103 if (isLinkTimeConstant) { 1104 in.got->relocations.push_back({expr, target->symbolicRel, off, 0, &sym}); 1105 return; 1106 } 1107 1108 // Otherwise, we emit a dynamic relocation to .rel[a].dyn so that 1109 // the GOT slot will be fixed at load-time. 1110 if (!sym.isTls() && !sym.isPreemptible && config->isPic) { 1111 addRelativeReloc(in.got, off, sym, 0, R_ABS, target->symbolicRel); 1112 return; 1113 } 1114 mainPart->relaDyn->addAddendOnlyRelocIfNonPreemptible( 1115 sym.isTls() ? target->tlsGotRel : target->gotRel, in.got, off, sym, 1116 target->symbolicRel); 1117 } 1118 1119 // Return true if we can define a symbol in the executable that 1120 // contains the value/function of a symbol defined in a shared 1121 // library. 1122 static bool canDefineSymbolInExecutable(Symbol &sym) { 1123 // If the symbol has default visibility the symbol defined in the 1124 // executable will preempt it. 1125 // Note that we want the visibility of the shared symbol itself, not 1126 // the visibility of the symbol in the output file we are producing. That is 1127 // why we use Sym.stOther. 1128 if ((sym.stOther & 0x3) == STV_DEFAULT) 1129 return true; 1130 1131 // If we are allowed to break address equality of functions, defining 1132 // a plt entry will allow the program to call the function in the 1133 // .so, but the .so and the executable will no agree on the address 1134 // of the function. Similar logic for objects. 1135 return ((sym.isFunc() && config->ignoreFunctionAddressEquality) || 1136 (sym.isObject() && config->ignoreDataAddressEquality)); 1137 } 1138 1139 // The reason we have to do this early scan is as follows 1140 // * To mmap the output file, we need to know the size 1141 // * For that, we need to know how many dynamic relocs we will have. 1142 // It might be possible to avoid this by outputting the file with write: 1143 // * Write the allocated output sections, computing addresses. 1144 // * Apply relocations, recording which ones require a dynamic reloc. 1145 // * Write the dynamic relocations. 1146 // * Write the rest of the file. 1147 // This would have some drawbacks. For example, we would only know if .rela.dyn 1148 // is needed after applying relocations. If it is, it will go after rw and rx 1149 // sections. Given that it is ro, we will need an extra PT_LOAD. This 1150 // complicates things for the dynamic linker and means we would have to reserve 1151 // space for the extra PT_LOAD even if we end up not using it. 1152 template <class ELFT, class RelTy> 1153 static void processRelocAux(InputSectionBase &sec, RelExpr expr, RelType type, 1154 uint64_t offset, Symbol &sym, const RelTy &rel, 1155 int64_t addend) { 1156 // If the relocation is known to be a link-time constant, we know no dynamic 1157 // relocation will be created, pass the control to relocateAlloc() or 1158 // relocateNonAlloc() to resolve it. 1159 // 1160 // The behavior of an undefined weak reference is implementation defined. For 1161 // non-link-time constants, we resolve relocations statically (let 1162 // relocate{,Non}Alloc() resolve them) for -no-pie and try producing dynamic 1163 // relocations for -pie and -shared. 1164 // 1165 // The general expectation of -no-pie static linking is that there is no 1166 // dynamic relocation (except IRELATIVE). Emitting dynamic relocations for 1167 // -shared matches the spirit of its -z undefs default. -pie has freedom on 1168 // choices, and we choose dynamic relocations to be consistent with the 1169 // handling of GOT-generating relocations. 1170 if (isStaticLinkTimeConstant(expr, type, sym, sec, offset) || 1171 (!config->isPic && sym.isUndefWeak())) { 1172 sec.relocations.push_back({expr, type, offset, addend, &sym}); 1173 return; 1174 } 1175 1176 bool canWrite = (sec.flags & SHF_WRITE) || !config->zText; 1177 if (canWrite) { 1178 RelType rel = target->getDynRel(type); 1179 if (expr == R_GOT || (rel == target->symbolicRel && !sym.isPreemptible)) { 1180 addRelativeReloc(&sec, offset, sym, addend, expr, type); 1181 return; 1182 } else if (rel != 0) { 1183 if (config->emachine == EM_MIPS && rel == target->symbolicRel) 1184 rel = target->relativeRel; 1185 sec.getPartition().relaDyn->addSymbolReloc(rel, &sec, offset, sym, addend, 1186 type); 1187 1188 // MIPS ABI turns using of GOT and dynamic relocations inside out. 1189 // While regular ABI uses dynamic relocations to fill up GOT entries 1190 // MIPS ABI requires dynamic linker to fills up GOT entries using 1191 // specially sorted dynamic symbol table. This affects even dynamic 1192 // relocations against symbols which do not require GOT entries 1193 // creation explicitly, i.e. do not have any GOT-relocations. So if 1194 // a preemptible symbol has a dynamic relocation we anyway have 1195 // to create a GOT entry for it. 1196 // If a non-preemptible symbol has a dynamic relocation against it, 1197 // dynamic linker takes it st_value, adds offset and writes down 1198 // result of the dynamic relocation. In case of preemptible symbol 1199 // dynamic linker performs symbol resolution, writes the symbol value 1200 // to the GOT entry and reads the GOT entry when it needs to perform 1201 // a dynamic relocation. 1202 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf p.4-19 1203 if (config->emachine == EM_MIPS) 1204 in.mipsGot->addEntry(*sec.file, sym, addend, expr); 1205 return; 1206 } 1207 } 1208 1209 // When producing an executable, we can perform copy relocations (for 1210 // STT_OBJECT) and canonical PLT (for STT_FUNC). 1211 if (!config->shared) { 1212 if (!canDefineSymbolInExecutable(sym)) { 1213 errorOrWarn("cannot preempt symbol: " + toString(sym) + 1214 getLocation(sec, sym, offset)); 1215 return; 1216 } 1217 1218 if (sym.isObject()) { 1219 // Produce a copy relocation. 1220 if (auto *ss = dyn_cast<SharedSymbol>(&sym)) { 1221 if (!config->zCopyreloc) 1222 error("unresolvable relocation " + toString(type) + 1223 " against symbol '" + toString(*ss) + 1224 "'; recompile with -fPIC or remove '-z nocopyreloc'" + 1225 getLocation(sec, sym, offset)); 1226 addCopyRelSymbol<ELFT>(*ss); 1227 } 1228 sec.relocations.push_back({expr, type, offset, addend, &sym}); 1229 return; 1230 } 1231 1232 // This handles a non PIC program call to function in a shared library. In 1233 // an ideal world, we could just report an error saying the relocation can 1234 // overflow at runtime. In the real world with glibc, crt1.o has a 1235 // R_X86_64_PC32 pointing to libc.so. 1236 // 1237 // The general idea on how to handle such cases is to create a PLT entry and 1238 // use that as the function value. 1239 // 1240 // For the static linking part, we just return a plt expr and everything 1241 // else will use the PLT entry as the address. 1242 // 1243 // The remaining problem is making sure pointer equality still works. We 1244 // need the help of the dynamic linker for that. We let it know that we have 1245 // a direct reference to a so symbol by creating an undefined symbol with a 1246 // non zero st_value. Seeing that, the dynamic linker resolves the symbol to 1247 // the value of the symbol we created. This is true even for got entries, so 1248 // pointer equality is maintained. To avoid an infinite loop, the only entry 1249 // that points to the real function is a dedicated got entry used by the 1250 // plt. That is identified by special relocation types (R_X86_64_JUMP_SLOT, 1251 // R_386_JMP_SLOT, etc). 1252 1253 // For position independent executable on i386, the plt entry requires ebx 1254 // to be set. This causes two problems: 1255 // * If some code has a direct reference to a function, it was probably 1256 // compiled without -fPIE/-fPIC and doesn't maintain ebx. 1257 // * If a library definition gets preempted to the executable, it will have 1258 // the wrong ebx value. 1259 if (sym.isFunc()) { 1260 if (config->pie && config->emachine == EM_386) 1261 errorOrWarn("symbol '" + toString(sym) + 1262 "' cannot be preempted; recompile with -fPIE" + 1263 getLocation(sec, sym, offset)); 1264 if (!sym.isInPlt()) 1265 addPltEntry(in.plt, in.gotPlt, in.relaPlt, target->pltRel, sym); 1266 if (!sym.isDefined()) { 1267 replaceWithDefined( 1268 sym, in.plt, 1269 target->pltHeaderSize + target->pltEntrySize * sym.pltIndex, 0); 1270 if (config->emachine == EM_PPC) { 1271 // PPC32 canonical PLT entries are at the beginning of .glink 1272 cast<Defined>(sym).value = in.plt->headerSize; 1273 in.plt->headerSize += 16; 1274 cast<PPC32GlinkSection>(in.plt)->canonical_plts.push_back(&sym); 1275 } 1276 } 1277 sym.needsPltAddr = true; 1278 sec.relocations.push_back({expr, type, offset, addend, &sym}); 1279 return; 1280 } 1281 } 1282 1283 if (config->isPic) { 1284 if (!canWrite && !isRelExpr(expr)) 1285 errorOrWarn( 1286 "can't create dynamic relocation " + toString(type) + " against " + 1287 (sym.getName().empty() ? "local symbol" 1288 : "symbol: " + toString(sym)) + 1289 " in readonly segment; recompile object files with -fPIC " 1290 "or pass '-Wl,-z,notext' to allow text relocations in the output" + 1291 getLocation(sec, sym, offset)); 1292 else 1293 errorOrWarn( 1294 "relocation " + toString(type) + " cannot be used against " + 1295 (sym.getName().empty() ? "local symbol" : "symbol " + toString(sym)) + 1296 "; recompile with -fPIC" + getLocation(sec, sym, offset)); 1297 return; 1298 } 1299 1300 errorOrWarn("symbol '" + toString(sym) + "' has no type" + 1301 getLocation(sec, sym, offset)); 1302 } 1303 1304 template <class ELFT, class RelTy> 1305 static void scanReloc(InputSectionBase &sec, OffsetGetter &getOffset, RelTy *&i, 1306 RelTy *start, RelTy *end) { 1307 const RelTy &rel = *i; 1308 uint32_t symIndex = rel.getSymbol(config->isMips64EL); 1309 Symbol &sym = sec.getFile<ELFT>()->getSymbol(symIndex); 1310 RelType type; 1311 1312 // Deal with MIPS oddity. 1313 if (config->mipsN32Abi) { 1314 type = getMipsN32RelType(i, end); 1315 } else { 1316 type = rel.getType(config->isMips64EL); 1317 ++i; 1318 } 1319 1320 // Get an offset in an output section this relocation is applied to. 1321 uint64_t offset = getOffset.get(rel.r_offset); 1322 if (offset == uint64_t(-1)) 1323 return; 1324 1325 // Error if the target symbol is undefined. Symbol index 0 may be used by 1326 // marker relocations, e.g. R_*_NONE and R_ARM_V4BX. Don't error on them. 1327 if (symIndex != 0 && maybeReportUndefined(sym, sec, rel.r_offset)) 1328 return; 1329 1330 const uint8_t *relocatedAddr = sec.data().begin() + rel.r_offset; 1331 RelExpr expr = target->getRelExpr(type, sym, relocatedAddr); 1332 1333 // Ignore R_*_NONE and other marker relocations. 1334 if (expr == R_NONE) 1335 return; 1336 1337 // Read an addend. 1338 int64_t addend = computeAddend<ELFT>(rel, end, sec, expr, sym.isLocal()); 1339 1340 if (config->emachine == EM_PPC64) { 1341 // We can separate the small code model relocations into 2 categories: 1342 // 1) Those that access the compiler generated .toc sections. 1343 // 2) Those that access the linker allocated got entries. 1344 // lld allocates got entries to symbols on demand. Since we don't try to 1345 // sort the got entries in any way, we don't have to track which objects 1346 // have got-based small code model relocs. The .toc sections get placed 1347 // after the end of the linker allocated .got section and we do sort those 1348 // so sections addressed with small code model relocations come first. 1349 if (isPPC64SmallCodeModelTocReloc(type)) 1350 sec.file->ppc64SmallCodeModelTocRelocs = true; 1351 1352 // Record the TOC entry (.toc + addend) as not relaxable. See the comment in 1353 // InputSectionBase::relocateAlloc(). 1354 if (type == R_PPC64_TOC16_LO && sym.isSection() && isa<Defined>(sym) && 1355 cast<Defined>(sym).section->name == ".toc") 1356 ppc64noTocRelax.insert({&sym, addend}); 1357 1358 if ((type == R_PPC64_TLSGD && expr == R_TLSDESC_CALL) || 1359 (type == R_PPC64_TLSLD && expr == R_TLSLD_HINT)) { 1360 if (i == end) { 1361 errorOrWarn("R_PPC64_TLSGD/R_PPC64_TLSLD may not be the last " 1362 "relocation" + 1363 getLocation(sec, sym, offset)); 1364 return; 1365 } 1366 1367 // Offset the 4-byte aligned R_PPC64_TLSGD by one byte in the NOTOC case, 1368 // so we can discern it later from the toc-case. 1369 if (i->getType(/*isMips64EL=*/false) == R_PPC64_REL24_NOTOC) 1370 ++offset; 1371 } 1372 } 1373 1374 // Relax relocations. 1375 // 1376 // If we know that a PLT entry will be resolved within the same ELF module, we 1377 // can skip PLT access and directly jump to the destination function. For 1378 // example, if we are linking a main executable, all dynamic symbols that can 1379 // be resolved within the executable will actually be resolved that way at 1380 // runtime, because the main executable is always at the beginning of a search 1381 // list. We can leverage that fact. 1382 if (!sym.isPreemptible && (!sym.isGnuIFunc() || config->zIfuncNoplt)) { 1383 if (expr != R_GOT_PC) { 1384 // The 0x8000 bit of r_addend of R_PPC_PLTREL24 is used to choose call 1385 // stub type. It should be ignored if optimized to R_PC. 1386 if (config->emachine == EM_PPC && expr == R_PPC32_PLTREL) 1387 addend &= ~0x8000; 1388 // R_HEX_GD_PLT_B22_PCREL (call a@GDPLT) is transformed into 1389 // call __tls_get_addr even if the symbol is non-preemptible. 1390 if (!(config->emachine == EM_HEXAGON && 1391 (type == R_HEX_GD_PLT_B22_PCREL || 1392 type == R_HEX_GD_PLT_B22_PCREL_X || 1393 type == R_HEX_GD_PLT_B32_PCREL_X))) 1394 expr = fromPlt(expr); 1395 } else if (!isAbsoluteValue(sym)) { 1396 expr = target->adjustGotPcExpr(type, addend, relocatedAddr); 1397 } 1398 } 1399 1400 // If the relocation does not emit a GOT or GOTPLT entry but its computation 1401 // uses their addresses, we need GOT or GOTPLT to be created. 1402 // 1403 // The 4 types that relative GOTPLT are all x86 and x86-64 specific. 1404 if (oneof<R_GOTPLTONLY_PC, R_GOTPLTREL, R_GOTPLT, R_TLSGD_GOTPLT>(expr)) { 1405 in.gotPlt->hasGotPltOffRel = true; 1406 } else if (oneof<R_GOTONLY_PC, R_GOTREL, R_PPC64_TOCBASE, R_PPC64_RELAX_TOC>( 1407 expr)) { 1408 in.got->hasGotOffRel = true; 1409 } 1410 1411 // Process TLS relocations, including relaxing TLS relocations. Note that 1412 // R_TPREL and R_TPREL_NEG relocations are resolved in processRelocAux. 1413 if (expr == R_TPREL || expr == R_TPREL_NEG) { 1414 if (config->shared) { 1415 errorOrWarn("relocation " + toString(type) + " against " + toString(sym) + 1416 " cannot be used with -shared" + 1417 getLocation(sec, sym, offset)); 1418 return; 1419 } 1420 } else if (unsigned processed = handleTlsRelocation<ELFT>( 1421 type, sym, sec, offset, addend, expr)) { 1422 i += (processed - 1); 1423 return; 1424 } 1425 1426 // We were asked not to generate PLT entries for ifuncs. Instead, pass the 1427 // direct relocation on through. 1428 if (sym.isGnuIFunc() && config->zIfuncNoplt) { 1429 sym.exportDynamic = true; 1430 mainPart->relaDyn->addSymbolReloc(type, &sec, offset, sym, addend, type); 1431 return; 1432 } 1433 1434 // Non-preemptible ifuncs require special handling. First, handle the usual 1435 // case where the symbol isn't one of these. 1436 if (!sym.isGnuIFunc() || sym.isPreemptible) { 1437 // If a relocation needs PLT, we create PLT and GOTPLT slots for the symbol. 1438 if (needsPlt(expr) && !sym.isInPlt()) 1439 addPltEntry(in.plt, in.gotPlt, in.relaPlt, target->pltRel, sym); 1440 1441 // Create a GOT slot if a relocation needs GOT. 1442 if (needsGot(expr)) { 1443 if (config->emachine == EM_MIPS) { 1444 // MIPS ABI has special rules to process GOT entries and doesn't 1445 // require relocation entries for them. A special case is TLS 1446 // relocations. In that case dynamic loader applies dynamic 1447 // relocations to initialize TLS GOT entries. 1448 // See "Global Offset Table" in Chapter 5 in the following document 1449 // for detailed description: 1450 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf 1451 in.mipsGot->addEntry(*sec.file, sym, addend, expr); 1452 } else if (!sym.isInGot()) { 1453 addGotEntry(sym); 1454 } 1455 } 1456 } else { 1457 // Handle a reference to a non-preemptible ifunc. These are special in a 1458 // few ways: 1459 // 1460 // - Unlike most non-preemptible symbols, non-preemptible ifuncs do not have 1461 // a fixed value. But assuming that all references to the ifunc are 1462 // GOT-generating or PLT-generating, the handling of an ifunc is 1463 // relatively straightforward. We create a PLT entry in Iplt, which is 1464 // usually at the end of .plt, which makes an indirect call using a 1465 // matching GOT entry in igotPlt, which is usually at the end of .got.plt. 1466 // The GOT entry is relocated using an IRELATIVE relocation in relaIplt, 1467 // which is usually at the end of .rela.plt. Unlike most relocations in 1468 // .rela.plt, which may be evaluated lazily without -z now, dynamic 1469 // loaders evaluate IRELATIVE relocs eagerly, which means that for 1470 // IRELATIVE relocs only, GOT-generating relocations can point directly to 1471 // .got.plt without requiring a separate GOT entry. 1472 // 1473 // - Despite the fact that an ifunc does not have a fixed value, compilers 1474 // that are not passed -fPIC will assume that they do, and will emit 1475 // direct (non-GOT-generating, non-PLT-generating) relocations to the 1476 // symbol. This means that if a direct relocation to the symbol is 1477 // seen, the linker must set a value for the symbol, and this value must 1478 // be consistent no matter what type of reference is made to the symbol. 1479 // This can be done by creating a PLT entry for the symbol in the way 1480 // described above and making it canonical, that is, making all references 1481 // point to the PLT entry instead of the resolver. In lld we also store 1482 // the address of the PLT entry in the dynamic symbol table, which means 1483 // that the symbol will also have the same value in other modules. 1484 // Because the value loaded from the GOT needs to be consistent with 1485 // the value computed using a direct relocation, a non-preemptible ifunc 1486 // may end up with two GOT entries, one in .got.plt that points to the 1487 // address returned by the resolver and is used only by the PLT entry, 1488 // and another in .got that points to the PLT entry and is used by 1489 // GOT-generating relocations. 1490 // 1491 // - The fact that these symbols do not have a fixed value makes them an 1492 // exception to the general rule that a statically linked executable does 1493 // not require any form of dynamic relocation. To handle these relocations 1494 // correctly, the IRELATIVE relocations are stored in an array which a 1495 // statically linked executable's startup code must enumerate using the 1496 // linker-defined symbols __rela?_iplt_{start,end}. 1497 if (!sym.isInPlt()) { 1498 // Create PLT and GOTPLT slots for the symbol. 1499 sym.isInIplt = true; 1500 1501 // Create a copy of the symbol to use as the target of the IRELATIVE 1502 // relocation in the igotPlt. This is in case we make the PLT canonical 1503 // later, which would overwrite the original symbol. 1504 // 1505 // FIXME: Creating a copy of the symbol here is a bit of a hack. All 1506 // that's really needed to create the IRELATIVE is the section and value, 1507 // so ideally we should just need to copy those. 1508 auto *directSym = make<Defined>(cast<Defined>(sym)); 1509 addPltEntry(in.iplt, in.igotPlt, in.relaIplt, target->iRelativeRel, 1510 *directSym); 1511 sym.pltIndex = directSym->pltIndex; 1512 } 1513 if (needsGot(expr)) { 1514 // Redirect GOT accesses to point to the Igot. 1515 // 1516 // This field is also used to keep track of whether we ever needed a GOT 1517 // entry. If we did and we make the PLT canonical later, we'll need to 1518 // create a GOT entry pointing to the PLT entry for Sym. 1519 sym.gotInIgot = true; 1520 } else if (!needsPlt(expr)) { 1521 // Make the ifunc's PLT entry canonical by changing the value of its 1522 // symbol to redirect all references to point to it. 1523 auto &d = cast<Defined>(sym); 1524 d.section = in.iplt; 1525 d.value = sym.pltIndex * target->ipltEntrySize; 1526 d.size = 0; 1527 // It's important to set the symbol type here so that dynamic loaders 1528 // don't try to call the PLT as if it were an ifunc resolver. 1529 d.type = STT_FUNC; 1530 1531 if (sym.gotInIgot) { 1532 // We previously encountered a GOT generating reference that we 1533 // redirected to the Igot. Now that the PLT entry is canonical we must 1534 // clear the redirection to the Igot and add a GOT entry. As we've 1535 // changed the symbol type to STT_FUNC future GOT generating references 1536 // will naturally use this GOT entry. 1537 // 1538 // We don't need to worry about creating a MIPS GOT here because ifuncs 1539 // aren't a thing on MIPS. 1540 sym.gotInIgot = false; 1541 addGotEntry(sym); 1542 } 1543 } 1544 } 1545 1546 processRelocAux<ELFT>(sec, expr, type, offset, sym, rel, addend); 1547 } 1548 1549 // R_PPC64_TLSGD/R_PPC64_TLSLD is required to mark `bl __tls_get_addr` for 1550 // General Dynamic/Local Dynamic code sequences. If a GD/LD GOT relocation is 1551 // found but no R_PPC64_TLSGD/R_PPC64_TLSLD is seen, we assume that the 1552 // instructions are generated by very old IBM XL compilers. Work around the 1553 // issue by disabling GD/LD to IE/LE relaxation. 1554 template <class RelTy> 1555 static void checkPPC64TLSRelax(InputSectionBase &sec, ArrayRef<RelTy> rels) { 1556 // Skip if sec is synthetic (sec.file is null) or if sec has been marked. 1557 if (!sec.file || sec.file->ppc64DisableTLSRelax) 1558 return; 1559 bool hasGDLD = false; 1560 for (const RelTy &rel : rels) { 1561 RelType type = rel.getType(false); 1562 switch (type) { 1563 case R_PPC64_TLSGD: 1564 case R_PPC64_TLSLD: 1565 return; // Found a marker 1566 case R_PPC64_GOT_TLSGD16: 1567 case R_PPC64_GOT_TLSGD16_HA: 1568 case R_PPC64_GOT_TLSGD16_HI: 1569 case R_PPC64_GOT_TLSGD16_LO: 1570 case R_PPC64_GOT_TLSLD16: 1571 case R_PPC64_GOT_TLSLD16_HA: 1572 case R_PPC64_GOT_TLSLD16_HI: 1573 case R_PPC64_GOT_TLSLD16_LO: 1574 hasGDLD = true; 1575 break; 1576 } 1577 } 1578 if (hasGDLD) { 1579 sec.file->ppc64DisableTLSRelax = true; 1580 warn(toString(sec.file) + 1581 ": disable TLS relaxation due to R_PPC64_GOT_TLS* relocations without " 1582 "R_PPC64_TLSGD/R_PPC64_TLSLD relocations"); 1583 } 1584 } 1585 1586 template <class ELFT, class RelTy> 1587 static void scanRelocs(InputSectionBase &sec, ArrayRef<RelTy> rels) { 1588 OffsetGetter getOffset(sec); 1589 1590 // Not all relocations end up in Sec.Relocations, but a lot do. 1591 sec.relocations.reserve(rels.size()); 1592 1593 if (config->emachine == EM_PPC64) 1594 checkPPC64TLSRelax<RelTy>(sec, rels); 1595 1596 // For EhInputSection, OffsetGetter expects the relocations to be sorted by 1597 // r_offset. In rare cases (.eh_frame pieces are reordered by a linker 1598 // script), the relocations may be unordered. 1599 SmallVector<RelTy, 0> storage; 1600 if (isa<EhInputSection>(sec)) 1601 rels = sortRels(rels, storage); 1602 1603 for (auto i = rels.begin(), end = rels.end(); i != end;) 1604 scanReloc<ELFT>(sec, getOffset, i, rels.begin(), end); 1605 1606 // Sort relocations by offset for more efficient searching for 1607 // R_RISCV_PCREL_HI20 and R_PPC64_ADDR64. 1608 if (config->emachine == EM_RISCV || 1609 (config->emachine == EM_PPC64 && sec.name == ".toc")) 1610 llvm::stable_sort(sec.relocations, 1611 [](const Relocation &lhs, const Relocation &rhs) { 1612 return lhs.offset < rhs.offset; 1613 }); 1614 } 1615 1616 template <class ELFT> void elf::scanRelocations(InputSectionBase &s) { 1617 if (s.areRelocsRela) 1618 scanRelocs<ELFT>(s, s.relas<ELFT>()); 1619 else 1620 scanRelocs<ELFT>(s, s.rels<ELFT>()); 1621 } 1622 1623 static bool mergeCmp(const InputSection *a, const InputSection *b) { 1624 // std::merge requires a strict weak ordering. 1625 if (a->outSecOff < b->outSecOff) 1626 return true; 1627 1628 if (a->outSecOff == b->outSecOff) { 1629 auto *ta = dyn_cast<ThunkSection>(a); 1630 auto *tb = dyn_cast<ThunkSection>(b); 1631 1632 // Check if Thunk is immediately before any specific Target 1633 // InputSection for example Mips LA25 Thunks. 1634 if (ta && ta->getTargetInputSection() == b) 1635 return true; 1636 1637 // Place Thunk Sections without specific targets before 1638 // non-Thunk Sections. 1639 if (ta && !tb && !ta->getTargetInputSection()) 1640 return true; 1641 } 1642 1643 return false; 1644 } 1645 1646 // Call Fn on every executable InputSection accessed via the linker script 1647 // InputSectionDescription::Sections. 1648 static void forEachInputSectionDescription( 1649 ArrayRef<OutputSection *> outputSections, 1650 llvm::function_ref<void(OutputSection *, InputSectionDescription *)> fn) { 1651 for (OutputSection *os : outputSections) { 1652 if (!(os->flags & SHF_ALLOC) || !(os->flags & SHF_EXECINSTR)) 1653 continue; 1654 for (BaseCommand *bc : os->sectionCommands) 1655 if (auto *isd = dyn_cast<InputSectionDescription>(bc)) 1656 fn(os, isd); 1657 } 1658 } 1659 1660 // Thunk Implementation 1661 // 1662 // Thunks (sometimes called stubs, veneers or branch islands) are small pieces 1663 // of code that the linker inserts inbetween a caller and a callee. The thunks 1664 // are added at link time rather than compile time as the decision on whether 1665 // a thunk is needed, such as the caller and callee being out of range, can only 1666 // be made at link time. 1667 // 1668 // It is straightforward to tell given the current state of the program when a 1669 // thunk is needed for a particular call. The more difficult part is that 1670 // the thunk needs to be placed in the program such that the caller can reach 1671 // the thunk and the thunk can reach the callee; furthermore, adding thunks to 1672 // the program alters addresses, which can mean more thunks etc. 1673 // 1674 // In lld we have a synthetic ThunkSection that can hold many Thunks. 1675 // The decision to have a ThunkSection act as a container means that we can 1676 // more easily handle the most common case of a single block of contiguous 1677 // Thunks by inserting just a single ThunkSection. 1678 // 1679 // The implementation of Thunks in lld is split across these areas 1680 // Relocations.cpp : Framework for creating and placing thunks 1681 // Thunks.cpp : The code generated for each supported thunk 1682 // Target.cpp : Target specific hooks that the framework uses to decide when 1683 // a thunk is used 1684 // Synthetic.cpp : Implementation of ThunkSection 1685 // Writer.cpp : Iteratively call framework until no more Thunks added 1686 // 1687 // Thunk placement requirements: 1688 // Mips LA25 thunks. These must be placed immediately before the callee section 1689 // We can assume that the caller is in range of the Thunk. These are modelled 1690 // by Thunks that return the section they must precede with 1691 // getTargetInputSection(). 1692 // 1693 // ARM interworking and range extension thunks. These thunks must be placed 1694 // within range of the caller. All implemented ARM thunks can always reach the 1695 // callee as they use an indirect jump via a register that has no range 1696 // restrictions. 1697 // 1698 // Thunk placement algorithm: 1699 // For Mips LA25 ThunkSections; the placement is explicit, it has to be before 1700 // getTargetInputSection(). 1701 // 1702 // For thunks that must be placed within range of the caller there are many 1703 // possible choices given that the maximum range from the caller is usually 1704 // much larger than the average InputSection size. Desirable properties include: 1705 // - Maximize reuse of thunks by multiple callers 1706 // - Minimize number of ThunkSections to simplify insertion 1707 // - Handle impact of already added Thunks on addresses 1708 // - Simple to understand and implement 1709 // 1710 // In lld for the first pass, we pre-create one or more ThunkSections per 1711 // InputSectionDescription at Target specific intervals. A ThunkSection is 1712 // placed so that the estimated end of the ThunkSection is within range of the 1713 // start of the InputSectionDescription or the previous ThunkSection. For 1714 // example: 1715 // InputSectionDescription 1716 // Section 0 1717 // ... 1718 // Section N 1719 // ThunkSection 0 1720 // Section N + 1 1721 // ... 1722 // Section N + K 1723 // Thunk Section 1 1724 // 1725 // The intention is that we can add a Thunk to a ThunkSection that is well 1726 // spaced enough to service a number of callers without having to do a lot 1727 // of work. An important principle is that it is not an error if a Thunk cannot 1728 // be placed in a pre-created ThunkSection; when this happens we create a new 1729 // ThunkSection placed next to the caller. This allows us to handle the vast 1730 // majority of thunks simply, but also handle rare cases where the branch range 1731 // is smaller than the target specific spacing. 1732 // 1733 // The algorithm is expected to create all the thunks that are needed in a 1734 // single pass, with a small number of programs needing a second pass due to 1735 // the insertion of thunks in the first pass increasing the offset between 1736 // callers and callees that were only just in range. 1737 // 1738 // A consequence of allowing new ThunkSections to be created outside of the 1739 // pre-created ThunkSections is that in rare cases calls to Thunks that were in 1740 // range in pass K, are out of range in some pass > K due to the insertion of 1741 // more Thunks in between the caller and callee. When this happens we retarget 1742 // the relocation back to the original target and create another Thunk. 1743 1744 // Remove ThunkSections that are empty, this should only be the initial set 1745 // precreated on pass 0. 1746 1747 // Insert the Thunks for OutputSection OS into their designated place 1748 // in the Sections vector, and recalculate the InputSection output section 1749 // offsets. 1750 // This may invalidate any output section offsets stored outside of InputSection 1751 void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> outputSections) { 1752 forEachInputSectionDescription( 1753 outputSections, [&](OutputSection *os, InputSectionDescription *isd) { 1754 if (isd->thunkSections.empty()) 1755 return; 1756 1757 // Remove any zero sized precreated Thunks. 1758 llvm::erase_if(isd->thunkSections, 1759 [](const std::pair<ThunkSection *, uint32_t> &ts) { 1760 return ts.first->getSize() == 0; 1761 }); 1762 1763 // ISD->ThunkSections contains all created ThunkSections, including 1764 // those inserted in previous passes. Extract the Thunks created this 1765 // pass and order them in ascending outSecOff. 1766 std::vector<ThunkSection *> newThunks; 1767 for (std::pair<ThunkSection *, uint32_t> ts : isd->thunkSections) 1768 if (ts.second == pass) 1769 newThunks.push_back(ts.first); 1770 llvm::stable_sort(newThunks, 1771 [](const ThunkSection *a, const ThunkSection *b) { 1772 return a->outSecOff < b->outSecOff; 1773 }); 1774 1775 // Merge sorted vectors of Thunks and InputSections by outSecOff 1776 std::vector<InputSection *> tmp; 1777 tmp.reserve(isd->sections.size() + newThunks.size()); 1778 1779 std::merge(isd->sections.begin(), isd->sections.end(), 1780 newThunks.begin(), newThunks.end(), std::back_inserter(tmp), 1781 mergeCmp); 1782 1783 isd->sections = std::move(tmp); 1784 }); 1785 } 1786 1787 // Find or create a ThunkSection within the InputSectionDescription (ISD) that 1788 // is in range of Src. An ISD maps to a range of InputSections described by a 1789 // linker script section pattern such as { .text .text.* }. 1790 ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *os, 1791 InputSection *isec, 1792 InputSectionDescription *isd, 1793 const Relocation &rel, 1794 uint64_t src) { 1795 for (std::pair<ThunkSection *, uint32_t> tp : isd->thunkSections) { 1796 ThunkSection *ts = tp.first; 1797 uint64_t tsBase = os->addr + ts->outSecOff + rel.addend; 1798 uint64_t tsLimit = tsBase + ts->getSize() + rel.addend; 1799 if (target->inBranchRange(rel.type, src, 1800 (src > tsLimit) ? tsBase : tsLimit)) 1801 return ts; 1802 } 1803 1804 // No suitable ThunkSection exists. This can happen when there is a branch 1805 // with lower range than the ThunkSection spacing or when there are too 1806 // many Thunks. Create a new ThunkSection as close to the InputSection as 1807 // possible. Error if InputSection is so large we cannot place ThunkSection 1808 // anywhere in Range. 1809 uint64_t thunkSecOff = isec->outSecOff; 1810 if (!target->inBranchRange(rel.type, src, 1811 os->addr + thunkSecOff + rel.addend)) { 1812 thunkSecOff = isec->outSecOff + isec->getSize(); 1813 if (!target->inBranchRange(rel.type, src, 1814 os->addr + thunkSecOff + rel.addend)) 1815 fatal("InputSection too large for range extension thunk " + 1816 isec->getObjMsg(src - (os->addr + isec->outSecOff))); 1817 } 1818 return addThunkSection(os, isd, thunkSecOff); 1819 } 1820 1821 // Add a Thunk that needs to be placed in a ThunkSection that immediately 1822 // precedes its Target. 1823 ThunkSection *ThunkCreator::getISThunkSec(InputSection *isec) { 1824 ThunkSection *ts = thunkedSections.lookup(isec); 1825 if (ts) 1826 return ts; 1827 1828 // Find InputSectionRange within Target Output Section (TOS) that the 1829 // InputSection (IS) that we need to precede is in. 1830 OutputSection *tos = isec->getParent(); 1831 for (BaseCommand *bc : tos->sectionCommands) { 1832 auto *isd = dyn_cast<InputSectionDescription>(bc); 1833 if (!isd || isd->sections.empty()) 1834 continue; 1835 1836 InputSection *first = isd->sections.front(); 1837 InputSection *last = isd->sections.back(); 1838 1839 if (isec->outSecOff < first->outSecOff || last->outSecOff < isec->outSecOff) 1840 continue; 1841 1842 ts = addThunkSection(tos, isd, isec->outSecOff); 1843 thunkedSections[isec] = ts; 1844 return ts; 1845 } 1846 1847 return nullptr; 1848 } 1849 1850 // Create one or more ThunkSections per OS that can be used to place Thunks. 1851 // We attempt to place the ThunkSections using the following desirable 1852 // properties: 1853 // - Within range of the maximum number of callers 1854 // - Minimise the number of ThunkSections 1855 // 1856 // We follow a simple but conservative heuristic to place ThunkSections at 1857 // offsets that are multiples of a Target specific branch range. 1858 // For an InputSectionDescription that is smaller than the range, a single 1859 // ThunkSection at the end of the range will do. 1860 // 1861 // For an InputSectionDescription that is more than twice the size of the range, 1862 // we place the last ThunkSection at range bytes from the end of the 1863 // InputSectionDescription in order to increase the likelihood that the 1864 // distance from a thunk to its target will be sufficiently small to 1865 // allow for the creation of a short thunk. 1866 void ThunkCreator::createInitialThunkSections( 1867 ArrayRef<OutputSection *> outputSections) { 1868 uint32_t thunkSectionSpacing = target->getThunkSectionSpacing(); 1869 1870 forEachInputSectionDescription( 1871 outputSections, [&](OutputSection *os, InputSectionDescription *isd) { 1872 if (isd->sections.empty()) 1873 return; 1874 1875 uint32_t isdBegin = isd->sections.front()->outSecOff; 1876 uint32_t isdEnd = 1877 isd->sections.back()->outSecOff + isd->sections.back()->getSize(); 1878 uint32_t lastThunkLowerBound = -1; 1879 if (isdEnd - isdBegin > thunkSectionSpacing * 2) 1880 lastThunkLowerBound = isdEnd - thunkSectionSpacing; 1881 1882 uint32_t isecLimit; 1883 uint32_t prevIsecLimit = isdBegin; 1884 uint32_t thunkUpperBound = isdBegin + thunkSectionSpacing; 1885 1886 for (const InputSection *isec : isd->sections) { 1887 isecLimit = isec->outSecOff + isec->getSize(); 1888 if (isecLimit > thunkUpperBound) { 1889 addThunkSection(os, isd, prevIsecLimit); 1890 thunkUpperBound = prevIsecLimit + thunkSectionSpacing; 1891 } 1892 if (isecLimit > lastThunkLowerBound) 1893 break; 1894 prevIsecLimit = isecLimit; 1895 } 1896 addThunkSection(os, isd, isecLimit); 1897 }); 1898 } 1899 1900 ThunkSection *ThunkCreator::addThunkSection(OutputSection *os, 1901 InputSectionDescription *isd, 1902 uint64_t off) { 1903 auto *ts = make<ThunkSection>(os, off); 1904 ts->partition = os->partition; 1905 if ((config->fixCortexA53Errata843419 || config->fixCortexA8) && 1906 !isd->sections.empty()) { 1907 // The errata fixes are sensitive to addresses modulo 4 KiB. When we add 1908 // thunks we disturb the base addresses of sections placed after the thunks 1909 // this makes patches we have generated redundant, and may cause us to 1910 // generate more patches as different instructions are now in sensitive 1911 // locations. When we generate more patches we may force more branches to 1912 // go out of range, causing more thunks to be generated. In pathological 1913 // cases this can cause the address dependent content pass not to converge. 1914 // We fix this by rounding up the size of the ThunkSection to 4KiB, this 1915 // limits the insertion of a ThunkSection on the addresses modulo 4 KiB, 1916 // which means that adding Thunks to the section does not invalidate 1917 // errata patches for following code. 1918 // Rounding up the size to 4KiB has consequences for code-size and can 1919 // trip up linker script defined assertions. For example the linux kernel 1920 // has an assertion that what LLD represents as an InputSectionDescription 1921 // does not exceed 4 KiB even if the overall OutputSection is > 128 Mib. 1922 // We use the heuristic of rounding up the size when both of the following 1923 // conditions are true: 1924 // 1.) The OutputSection is larger than the ThunkSectionSpacing. This 1925 // accounts for the case where no single InputSectionDescription is 1926 // larger than the OutputSection size. This is conservative but simple. 1927 // 2.) The InputSectionDescription is larger than 4 KiB. This will prevent 1928 // any assertion failures that an InputSectionDescription is < 4 KiB 1929 // in size. 1930 uint64_t isdSize = isd->sections.back()->outSecOff + 1931 isd->sections.back()->getSize() - 1932 isd->sections.front()->outSecOff; 1933 if (os->size > target->getThunkSectionSpacing() && isdSize > 4096) 1934 ts->roundUpSizeForErrata = true; 1935 } 1936 isd->thunkSections.push_back({ts, pass}); 1937 return ts; 1938 } 1939 1940 static bool isThunkSectionCompatible(InputSection *source, 1941 SectionBase *target) { 1942 // We can't reuse thunks in different loadable partitions because they might 1943 // not be loaded. But partition 1 (the main partition) will always be loaded. 1944 if (source->partition != target->partition) 1945 return target->partition == 1; 1946 return true; 1947 } 1948 1949 static int64_t getPCBias(RelType type) { 1950 if (config->emachine != EM_ARM) 1951 return 0; 1952 switch (type) { 1953 case R_ARM_THM_JUMP19: 1954 case R_ARM_THM_JUMP24: 1955 case R_ARM_THM_CALL: 1956 return 4; 1957 default: 1958 return 8; 1959 } 1960 } 1961 1962 std::pair<Thunk *, bool> ThunkCreator::getThunk(InputSection *isec, 1963 Relocation &rel, uint64_t src) { 1964 std::vector<Thunk *> *thunkVec = nullptr; 1965 // Arm and Thumb have a PC Bias of 8 and 4 respectively, this is cancelled 1966 // out in the relocation addend. We compensate for the PC bias so that 1967 // an Arm and Thumb relocation to the same destination get the same keyAddend, 1968 // which is usually 0. 1969 int64_t keyAddend = rel.addend + getPCBias(rel.type); 1970 1971 // We use a ((section, offset), addend) pair to find the thunk position if 1972 // possible so that we create only one thunk for aliased symbols or ICFed 1973 // sections. There may be multiple relocations sharing the same (section, 1974 // offset + addend) pair. We may revert the relocation back to its original 1975 // non-Thunk target, so we cannot fold offset + addend. 1976 if (auto *d = dyn_cast<Defined>(rel.sym)) 1977 if (!d->isInPlt() && d->section) 1978 thunkVec = &thunkedSymbolsBySectionAndAddend[{ 1979 {d->section->repl, d->value}, keyAddend}]; 1980 if (!thunkVec) 1981 thunkVec = &thunkedSymbols[{rel.sym, keyAddend}]; 1982 1983 // Check existing Thunks for Sym to see if they can be reused 1984 for (Thunk *t : *thunkVec) 1985 if (isThunkSectionCompatible(isec, t->getThunkTargetSym()->section) && 1986 t->isCompatibleWith(*isec, rel) && 1987 target->inBranchRange(rel.type, src, 1988 t->getThunkTargetSym()->getVA(rel.addend))) 1989 return std::make_pair(t, false); 1990 1991 // No existing compatible Thunk in range, create a new one 1992 Thunk *t = addThunk(*isec, rel); 1993 thunkVec->push_back(t); 1994 return std::make_pair(t, true); 1995 } 1996 1997 // Return true if the relocation target is an in range Thunk. 1998 // Return false if the relocation is not to a Thunk. If the relocation target 1999 // was originally to a Thunk, but is no longer in range we revert the 2000 // relocation back to its original non-Thunk target. 2001 bool ThunkCreator::normalizeExistingThunk(Relocation &rel, uint64_t src) { 2002 if (Thunk *t = thunks.lookup(rel.sym)) { 2003 if (target->inBranchRange(rel.type, src, rel.sym->getVA(rel.addend))) 2004 return true; 2005 rel.sym = &t->destination; 2006 rel.addend = t->addend; 2007 if (rel.sym->isInPlt()) 2008 rel.expr = toPlt(rel.expr); 2009 } 2010 return false; 2011 } 2012 2013 // Process all relocations from the InputSections that have been assigned 2014 // to InputSectionDescriptions and redirect through Thunks if needed. The 2015 // function should be called iteratively until it returns false. 2016 // 2017 // PreConditions: 2018 // All InputSections that may need a Thunk are reachable from 2019 // OutputSectionCommands. 2020 // 2021 // All OutputSections have an address and all InputSections have an offset 2022 // within the OutputSection. 2023 // 2024 // The offsets between caller (relocation place) and callee 2025 // (relocation target) will not be modified outside of createThunks(). 2026 // 2027 // PostConditions: 2028 // If return value is true then ThunkSections have been inserted into 2029 // OutputSections. All relocations that needed a Thunk based on the information 2030 // available to createThunks() on entry have been redirected to a Thunk. Note 2031 // that adding Thunks changes offsets between caller and callee so more Thunks 2032 // may be required. 2033 // 2034 // If return value is false then no more Thunks are needed, and createThunks has 2035 // made no changes. If the target requires range extension thunks, currently 2036 // ARM, then any future change in offset between caller and callee risks a 2037 // relocation out of range error. 2038 bool ThunkCreator::createThunks(ArrayRef<OutputSection *> outputSections) { 2039 bool addressesChanged = false; 2040 2041 if (pass == 0 && target->getThunkSectionSpacing()) 2042 createInitialThunkSections(outputSections); 2043 2044 // Create all the Thunks and insert them into synthetic ThunkSections. The 2045 // ThunkSections are later inserted back into InputSectionDescriptions. 2046 // We separate the creation of ThunkSections from the insertion of the 2047 // ThunkSections as ThunkSections are not always inserted into the same 2048 // InputSectionDescription as the caller. 2049 forEachInputSectionDescription( 2050 outputSections, [&](OutputSection *os, InputSectionDescription *isd) { 2051 for (InputSection *isec : isd->sections) 2052 for (Relocation &rel : isec->relocations) { 2053 uint64_t src = isec->getVA(rel.offset); 2054 2055 // If we are a relocation to an existing Thunk, check if it is 2056 // still in range. If not then Rel will be altered to point to its 2057 // original target so another Thunk can be generated. 2058 if (pass > 0 && normalizeExistingThunk(rel, src)) 2059 continue; 2060 2061 if (!target->needsThunk(rel.expr, rel.type, isec->file, src, 2062 *rel.sym, rel.addend)) 2063 continue; 2064 2065 Thunk *t; 2066 bool isNew; 2067 std::tie(t, isNew) = getThunk(isec, rel, src); 2068 2069 if (isNew) { 2070 // Find or create a ThunkSection for the new Thunk 2071 ThunkSection *ts; 2072 if (auto *tis = t->getTargetInputSection()) 2073 ts = getISThunkSec(tis); 2074 else 2075 ts = getISDThunkSec(os, isec, isd, rel, src); 2076 ts->addThunk(t); 2077 thunks[t->getThunkTargetSym()] = t; 2078 } 2079 2080 // Redirect relocation to Thunk, we never go via the PLT to a Thunk 2081 rel.sym = t->getThunkTargetSym(); 2082 rel.expr = fromPlt(rel.expr); 2083 2084 // On AArch64 and PPC, a jump/call relocation may be encoded as 2085 // STT_SECTION + non-zero addend, clear the addend after 2086 // redirection. 2087 if (config->emachine != EM_MIPS) 2088 rel.addend = -getPCBias(rel.type); 2089 } 2090 2091 for (auto &p : isd->thunkSections) 2092 addressesChanged |= p.first->assignOffsets(); 2093 }); 2094 2095 for (auto &p : thunkedSections) 2096 addressesChanged |= p.second->assignOffsets(); 2097 2098 // Merge all created synthetic ThunkSections back into OutputSection 2099 mergeThunks(outputSections); 2100 ++pass; 2101 return addressesChanged; 2102 } 2103 2104 // The following aid in the conversion of call x@GDPLT to call __tls_get_addr 2105 // hexagonNeedsTLSSymbol scans for relocations would require a call to 2106 // __tls_get_addr. 2107 // hexagonTLSSymbolUpdate rebinds the relocation to __tls_get_addr. 2108 bool elf::hexagonNeedsTLSSymbol(ArrayRef<OutputSection *> outputSections) { 2109 bool needTlsSymbol = false; 2110 forEachInputSectionDescription( 2111 outputSections, [&](OutputSection *os, InputSectionDescription *isd) { 2112 for (InputSection *isec : isd->sections) 2113 for (Relocation &rel : isec->relocations) 2114 if (rel.sym->type == llvm::ELF::STT_TLS && rel.expr == R_PLT_PC) { 2115 needTlsSymbol = true; 2116 return; 2117 } 2118 }); 2119 return needTlsSymbol; 2120 } 2121 2122 void elf::hexagonTLSSymbolUpdate(ArrayRef<OutputSection *> outputSections) { 2123 Symbol *sym = symtab->find("__tls_get_addr"); 2124 if (!sym) 2125 return; 2126 bool needEntry = true; 2127 forEachInputSectionDescription( 2128 outputSections, [&](OutputSection *os, InputSectionDescription *isd) { 2129 for (InputSection *isec : isd->sections) 2130 for (Relocation &rel : isec->relocations) 2131 if (rel.sym->type == llvm::ELF::STT_TLS && rel.expr == R_PLT_PC) { 2132 if (needEntry) { 2133 addPltEntry(in.plt, in.gotPlt, in.relaPlt, target->pltRel, 2134 *sym); 2135 needEntry = false; 2136 } 2137 rel.sym = sym; 2138 } 2139 }); 2140 } 2141 2142 template void elf::scanRelocations<ELF32LE>(InputSectionBase &); 2143 template void elf::scanRelocations<ELF32BE>(InputSectionBase &); 2144 template void elf::scanRelocations<ELF64LE>(InputSectionBase &); 2145 template void elf::scanRelocations<ELF64BE>(InputSectionBase &); 2146 template void elf::reportUndefinedSymbols<ELF32LE>(); 2147 template void elf::reportUndefinedSymbols<ELF32BE>(); 2148 template void elf::reportUndefinedSymbols<ELF64LE>(); 2149 template void elf::reportUndefinedSymbols<ELF64BE>(); 2150