1 //===- Relocations.cpp ----------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file contains platform-independent functions to process relocations.
10 // I'll describe the overview of this file here.
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.
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.
23 // ELF defines a large number of complex relocations.
25 // The functions in this file analyze relocations and do whatever needs
26 // to be done. It includes, but not limited to, the following.
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
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.
41 //===----------------------------------------------------------------------===//
43 #include "Relocations.h"
45 #include "LinkerScript.h"
46 #include "OutputSections.h"
47 #include "SymbolTable.h"
49 #include "SyntheticSections.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/Support/Endian.h"
57 #include "llvm/Support/raw_ostream.h"
61 using namespace llvm::ELF;
62 using namespace llvm::object;
63 using namespace llvm::support::endian;
66 using namespace lld::elf;
68 static Optional<std::string> getLinkerScriptLocation(const Symbol &sym) {
69 for (BaseCommand *base : script->sectionCommands)
70 if (auto *cmd = dyn_cast<SymbolAssignment>(base))
76 // Construct a message in the following format.
78 // >>> defined in /home/alice/src/foo.o
79 // >>> referenced by bar.c:12 (/home/alice/src/bar.c:12)
80 // >>> /home/alice/src/bar.o:(.text+0x1)
81 static std::string getLocation(InputSectionBase &s, const Symbol &sym,
83 std::string msg = "\n>>> defined in ";
85 msg += toString(sym.file);
86 else if (Optional<std::string> loc = getLinkerScriptLocation(sym))
89 msg += "\n>>> referenced by ";
90 std::string src = s.getSrcMsg(sym, off);
92 msg += src + "\n>>> ";
93 return msg + s.getObjMsg(off);
97 // Build a bitmask with one bit set for each RelExpr.
99 // Constexpr function arguments can't be used in static asserts, so we
100 // use template arguments to build the mask.
101 // But function template partial specializations don't exist (needed
102 // for base case of the recursion), so we need a dummy struct.
103 template <RelExpr... Exprs> struct RelExprMaskBuilder {
104 static inline uint64_t build() { return 0; }
107 // Specialization for recursive case.
108 template <RelExpr Head, RelExpr... Tail>
109 struct RelExprMaskBuilder<Head, Tail...> {
110 static inline uint64_t build() {
111 static_assert(0 <= Head && Head < 64,
112 "RelExpr is too large for 64-bit mask!");
113 return (uint64_t(1) << Head) | RelExprMaskBuilder<Tail...>::build();
118 // Return true if `Expr` is one of `Exprs`.
119 // There are fewer than 64 RelExpr's, so we can represent any set of
120 // RelExpr's as a constant bit mask and test for membership with a
121 // couple cheap bitwise operations.
122 template <RelExpr... Exprs> bool oneof(RelExpr expr) {
123 assert(0 <= expr && (int)expr < 64 &&
124 "RelExpr is too large for 64-bit mask!");
125 return (uint64_t(1) << expr) & RelExprMaskBuilder<Exprs...>::build();
128 // This function is similar to the `handleTlsRelocation`. MIPS does not
129 // support any relaxations for TLS relocations so by factoring out MIPS
130 // handling in to the separate function we can simplify the code and do not
131 // pollute other `handleTlsRelocation` by MIPS `ifs` statements.
132 // Mips has a custom MipsGotSection that handles the writing of GOT entries
133 // without dynamic relocations.
134 static unsigned handleMipsTlsRelocation(RelType type, Symbol &sym,
135 InputSectionBase &c, uint64_t offset,
136 int64_t addend, RelExpr expr) {
137 if (expr == R_MIPS_TLSLD) {
138 in.mipsGot->addTlsIndex(*c.file);
139 c.relocations.push_back({expr, type, offset, addend, &sym});
142 if (expr == R_MIPS_TLSGD) {
143 in.mipsGot->addDynTlsEntry(*c.file, sym);
144 c.relocations.push_back({expr, type, offset, addend, &sym});
150 // Notes about General Dynamic and Local Dynamic TLS models below. They may
151 // require the generation of a pair of GOT entries that have associated dynamic
152 // relocations. The pair of GOT entries created are of the form GOT[e0] Module
153 // Index (Used to find pointer to TLS block at run-time) GOT[e1] Offset of
154 // symbol in TLS block.
156 // Returns the number of relocations processed.
157 template <class ELFT>
159 handleTlsRelocation(RelType type, Symbol &sym, InputSectionBase &c,
160 typename ELFT::uint offset, int64_t addend, RelExpr expr) {
164 if (config->emachine == EM_MIPS)
165 return handleMipsTlsRelocation(type, sym, c, offset, addend, expr);
167 if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC>(
170 if (in.got->addDynTlsEntry(sym)) {
171 uint64_t off = in.got->getGlobalDynOffset(sym);
172 mainPart->relaDyn->addReloc(
173 {target->tlsDescRel, in.got, off, !sym.isPreemptible, &sym, 0});
175 if (expr != R_TLSDESC_CALL)
176 c.relocations.push_back({expr, type, offset, addend, &sym});
180 bool canRelax = config->emachine != EM_ARM && config->emachine != EM_RISCV;
182 // If we are producing an executable and the symbol is non-preemptable, it
183 // must be defined and the code sequence can be relaxed to use Local-Exec.
185 // ARM and RISC-V do not support any relaxations for TLS relocations, however,
186 // we can omit the DTPMOD dynamic relocations and resolve them at link time
187 // because them are always 1. This may be necessary for static linking as
188 // DTPMOD may not be expected at load time.
189 bool isLocalInExecutable = !sym.isPreemptible && !config->shared;
191 // Local Dynamic is for access to module local TLS variables, while still
192 // being suitable for being dynamically loaded via dlopen. GOT[e0] is the
193 // module index, with a special value of 0 for the current module. GOT[e1] is
194 // unused. There only needs to be one module index entry.
195 if (oneof<R_TLSLD_GOT, R_TLSLD_GOTPLT, R_TLSLD_PC, R_TLSLD_HINT>(
197 // Local-Dynamic relocs can be relaxed to Local-Exec.
198 if (canRelax && !config->shared) {
199 c.relocations.push_back(
200 {target->adjustRelaxExpr(type, nullptr, R_RELAX_TLS_LD_TO_LE), type,
201 offset, addend, &sym});
202 return target->getTlsGdRelaxSkip(type);
204 if (expr == R_TLSLD_HINT)
206 if (in.got->addTlsIndex()) {
207 if (isLocalInExecutable)
208 in.got->relocations.push_back(
209 {R_ADDEND, target->symbolicRel, in.got->getTlsIndexOff(), 1, &sym});
211 mainPart->relaDyn->addReloc(target->tlsModuleIndexRel, in.got,
212 in.got->getTlsIndexOff(), nullptr);
214 c.relocations.push_back({expr, type, offset, addend, &sym});
218 // Local-Dynamic relocs can be relaxed to Local-Exec.
219 if (expr == R_DTPREL && !config->shared) {
220 c.relocations.push_back(
221 {target->adjustRelaxExpr(type, nullptr, R_RELAX_TLS_LD_TO_LE), type,
222 offset, addend, &sym});
226 // Local-Dynamic sequence where offset of tls variable relative to dynamic
227 // thread pointer is stored in the got. This cannot be relaxed to Local-Exec.
228 if (expr == R_TLSLD_GOT_OFF) {
229 if (!sym.isInGot()) {
230 in.got->addEntry(sym);
231 uint64_t off = sym.getGotOffset();
232 in.got->relocations.push_back(
233 {R_ABS, target->tlsOffsetRel, off, 0, &sym});
235 c.relocations.push_back({expr, type, offset, addend, &sym});
239 if (oneof<R_AARCH64_TLSDESC_PAGE, R_TLSDESC, R_TLSDESC_CALL, R_TLSDESC_PC,
240 R_TLSGD_GOT, R_TLSGD_GOTPLT, R_TLSGD_PC>(expr)) {
241 if (!canRelax || config->shared) {
242 if (in.got->addDynTlsEntry(sym)) {
243 uint64_t off = in.got->getGlobalDynOffset(sym);
245 if (isLocalInExecutable)
246 // Write one to the GOT slot.
247 in.got->relocations.push_back(
248 {R_ADDEND, target->symbolicRel, off, 1, &sym});
250 mainPart->relaDyn->addReloc(target->tlsModuleIndexRel, in.got, off, &sym);
252 // If the symbol is preemptible we need the dynamic linker to write
254 uint64_t offsetOff = off + config->wordsize;
255 if (sym.isPreemptible)
256 mainPart->relaDyn->addReloc(target->tlsOffsetRel, in.got, offsetOff,
259 in.got->relocations.push_back(
260 {R_ABS, target->tlsOffsetRel, offsetOff, 0, &sym});
262 c.relocations.push_back({expr, type, offset, addend, &sym});
266 // Global-Dynamic relocs can be relaxed to Initial-Exec or Local-Exec
267 // depending on the symbol being locally defined or not.
268 if (sym.isPreemptible) {
269 c.relocations.push_back(
270 {target->adjustRelaxExpr(type, nullptr, R_RELAX_TLS_GD_TO_IE), type,
271 offset, addend, &sym});
272 if (!sym.isInGot()) {
273 in.got->addEntry(sym);
274 mainPart->relaDyn->addReloc(target->tlsGotRel, in.got, sym.getGotOffset(),
278 c.relocations.push_back(
279 {target->adjustRelaxExpr(type, nullptr, R_RELAX_TLS_GD_TO_LE), type,
280 offset, addend, &sym});
282 return target->getTlsGdRelaxSkip(type);
285 // Initial-Exec relocs can be relaxed to Local-Exec if the symbol is locally
287 if (oneof<R_GOT, R_GOTPLT, R_GOT_PC, R_AARCH64_GOT_PAGE_PC, R_GOT_OFF,
288 R_TLSIE_HINT>(expr) &&
289 canRelax && isLocalInExecutable) {
290 c.relocations.push_back({R_RELAX_TLS_IE_TO_LE, type, offset, addend, &sym});
294 if (expr == R_TLSIE_HINT)
299 static RelType getMipsPairType(RelType type, bool isLocal) {
304 // In case of global symbol, the R_MIPS_GOT16 relocation does not
305 // have a pair. Each global symbol has a unique entry in the GOT
306 // and a corresponding instruction with help of the R_MIPS_GOT16
307 // relocation loads an address of the symbol. In case of local
308 // symbol, the R_MIPS_GOT16 relocation creates a GOT entry to hold
309 // the high 16 bits of the symbol's value. A paired R_MIPS_LO16
310 // relocations handle low 16 bits of the address. That allows
311 // to allocate only one GOT entry for every 64 KBytes of local data.
312 return isLocal ? R_MIPS_LO16 : R_MIPS_NONE;
313 case R_MICROMIPS_GOT16:
314 return isLocal ? R_MICROMIPS_LO16 : R_MIPS_NONE;
316 return R_MIPS_PCLO16;
317 case R_MICROMIPS_HI16:
318 return R_MICROMIPS_LO16;
324 // True if non-preemptable symbol always has the same value regardless of where
325 // the DSO is loaded.
326 static bool isAbsolute(const Symbol &sym) {
327 if (sym.isUndefWeak())
329 if (const auto *dr = dyn_cast<Defined>(&sym))
330 return dr->section == nullptr; // Absolute symbol.
334 static bool isAbsoluteValue(const Symbol &sym) {
335 return isAbsolute(sym) || sym.isTls();
338 // Returns true if Expr refers a PLT entry.
339 static bool needsPlt(RelExpr expr) {
340 return oneof<R_PLT_PC, R_PPC32_PLTREL, R_PPC64_CALL_PLT, R_PLT>(expr);
343 // Returns true if Expr refers a GOT entry. Note that this function
344 // returns false for TLS variables even though they need GOT, because
345 // TLS variables uses GOT differently than the regular variables.
346 static bool needsGot(RelExpr expr) {
347 return oneof<R_GOT, R_GOT_OFF, R_HEXAGON_GOT, R_MIPS_GOT_LOCAL_PAGE,
348 R_MIPS_GOT_OFF, R_MIPS_GOT_OFF32, R_AARCH64_GOT_PAGE_PC,
349 R_GOT_PC, R_GOTPLT>(expr);
352 // True if this expression is of the form Sym - X, where X is a position in the
353 // file (PC, or GOT for example).
354 static bool isRelExpr(RelExpr expr) {
355 return oneof<R_PC, R_GOTREL, R_GOTPLTREL, R_MIPS_GOTREL, R_PPC64_CALL,
356 R_PPC64_RELAX_TOC, R_AARCH64_PAGE_PC, R_RELAX_GOT_PC,
357 R_RISCV_PC_INDIRECT>(expr);
360 // Returns true if a given relocation can be computed at link-time.
362 // For instance, we know the offset from a relocation to its target at
363 // link-time if the relocation is PC-relative and refers a
364 // non-interposable function in the same executable. This function
365 // will return true for such relocation.
367 // If this function returns false, that means we need to emit a
368 // dynamic relocation so that the relocation will be fixed at load-time.
369 static bool isStaticLinkTimeConstant(RelExpr e, RelType type, const Symbol &sym,
370 InputSectionBase &s, uint64_t relOff) {
371 // These expressions always compute a constant
372 if (oneof<R_DTPREL, R_GOTPLT, R_GOT_OFF, R_HEXAGON_GOT, R_TLSLD_GOT_OFF,
373 R_MIPS_GOT_LOCAL_PAGE, R_MIPS_GOTREL, R_MIPS_GOT_OFF,
374 R_MIPS_GOT_OFF32, R_MIPS_GOT_GP_PC, R_MIPS_TLSGD,
375 R_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC, R_GOTPLTONLY_PC,
376 R_PLT_PC, R_TLSGD_GOT, R_TLSGD_GOTPLT, R_TLSGD_PC, R_PPC32_PLTREL,
377 R_PPC64_CALL_PLT, R_PPC64_RELAX_TOC, R_RISCV_ADD, R_TLSDESC_CALL,
378 R_TLSDESC_PC, R_AARCH64_TLSDESC_PAGE, R_HINT, R_TLSLD_HINT,
382 // These never do, except if the entire file is position dependent or if
383 // only the low bits are used.
384 if (e == R_GOT || e == R_PLT || e == R_TLSDESC)
385 return target->usesOnlyLowPageBits(type) || !config->isPic;
387 if (sym.isPreemptible)
392 // The size of a non preemptible symbol is a constant.
396 // For the target and the relocation, we want to know if they are
397 // absolute or relative.
398 bool absVal = isAbsoluteValue(sym);
399 bool relE = isRelExpr(e);
404 if (!absVal && !relE)
405 return target->usesOnlyLowPageBits(type);
407 // Relative relocation to an absolute value. This is normally unrepresentable,
408 // but if the relocation refers to a weak undefined symbol, we allow it to
409 // resolve to the image base. This is a little strange, but it allows us to
410 // link function calls to such symbols. Normally such a call will be guarded
411 // with a comparison, which will load a zero from the GOT.
412 // Another special case is MIPS _gp_disp symbol which represents offset
413 // between start of a function and '_gp' value and defined as absolute just
414 // to simplify the code.
415 assert(absVal && relE);
416 if (sym.isUndefWeak())
419 // We set the final symbols values for linker script defined symbols later.
420 // They always can be computed as a link time constant.
421 if (sym.scriptDefined)
424 error("relocation " + toString(type) + " cannot refer to absolute symbol: " +
425 toString(sym) + getLocation(s, sym, relOff));
429 static RelExpr toPlt(RelExpr expr) {
432 return R_PPC64_CALL_PLT;
442 static RelExpr fromPlt(RelExpr expr) {
443 // We decided not to use a plt. Optimize a reference to the plt to a
444 // reference to the symbol itself.
449 case R_PPC64_CALL_PLT:
458 // Returns true if a given shared symbol is in a read-only segment in a DSO.
459 template <class ELFT> static bool isReadOnly(SharedSymbol &ss) {
460 using Elf_Phdr = typename ELFT::Phdr;
462 // Determine if the symbol is read-only by scanning the DSO's program headers.
463 const SharedFile &file = ss.getFile();
464 for (const Elf_Phdr &phdr :
465 check(file.template getObj<ELFT>().program_headers()))
466 if ((phdr.p_type == ELF::PT_LOAD || phdr.p_type == ELF::PT_GNU_RELRO) &&
467 !(phdr.p_flags & ELF::PF_W) && ss.value >= phdr.p_vaddr &&
468 ss.value < phdr.p_vaddr + phdr.p_memsz)
473 // Returns symbols at the same offset as a given symbol, including SS itself.
475 // If two or more symbols are at the same offset, and at least one of
476 // them are copied by a copy relocation, all of them need to be copied.
477 // Otherwise, they would refer to different places at runtime.
478 template <class ELFT>
479 static SmallSet<SharedSymbol *, 4> getSymbolsAt(SharedSymbol &ss) {
480 using Elf_Sym = typename ELFT::Sym;
482 SharedFile &file = ss.getFile();
484 SmallSet<SharedSymbol *, 4> ret;
485 for (const Elf_Sym &s : file.template getGlobalELFSyms<ELFT>()) {
486 if (s.st_shndx == SHN_UNDEF || s.st_shndx == SHN_ABS ||
487 s.getType() == STT_TLS || s.st_value != ss.value)
489 StringRef name = check(s.getName(file.getStringTable()));
490 Symbol *sym = symtab->find(name);
491 if (auto *alias = dyn_cast_or_null<SharedSymbol>(sym))
497 // When a symbol is copy relocated or we create a canonical plt entry, it is
498 // effectively a defined symbol. In the case of copy relocation the symbol is
499 // in .bss and in the case of a canonical plt entry it is in .plt. This function
500 // replaces the existing symbol with a Defined pointing to the appropriate
502 static void replaceWithDefined(Symbol &sym, SectionBase *sec, uint64_t value,
506 sym.replace(Defined{sym.file, sym.getName(), sym.binding, sym.stOther,
507 sym.type, value, size, sec});
509 sym.pltIndex = old.pltIndex;
510 sym.gotIndex = old.gotIndex;
511 sym.verdefIndex = old.verdefIndex;
512 sym.ppc64BranchltIndex = old.ppc64BranchltIndex;
513 sym.isPreemptible = true;
514 sym.exportDynamic = true;
515 sym.isUsedInRegularObj = true;
519 // Reserve space in .bss or .bss.rel.ro for copy relocation.
521 // The copy relocation is pretty much a hack. If you use a copy relocation
522 // in your program, not only the symbol name but the symbol's size, RW/RO
523 // bit and alignment become part of the ABI. In addition to that, if the
524 // symbol has aliases, the aliases become part of the ABI. That's subtle,
525 // but if you violate that implicit ABI, that can cause very counter-
526 // intuitive consequences.
528 // So, what is the copy relocation? It's for linking non-position
529 // independent code to DSOs. In an ideal world, all references to data
530 // exported by DSOs should go indirectly through GOT. But if object files
531 // are compiled as non-PIC, all data references are direct. There is no
532 // way for the linker to transform the code to use GOT, as machine
533 // instructions are already set in stone in object files. This is where
534 // the copy relocation takes a role.
536 // A copy relocation instructs the dynamic linker to copy data from a DSO
537 // to a specified address (which is usually in .bss) at load-time. If the
538 // static linker (that's us) finds a direct data reference to a DSO
539 // symbol, it creates a copy relocation, so that the symbol can be
540 // resolved as if it were in .bss rather than in a DSO.
542 // As you can see in this function, we create a copy relocation for the
543 // dynamic linker, and the relocation contains not only symbol name but
544 // various other informtion about the symbol. So, such attributes become a
547 // Note for application developers: I can give you a piece of advice if
548 // you are writing a shared library. You probably should export only
549 // functions from your library. You shouldn't export variables.
551 // As an example what can happen when you export variables without knowing
552 // the semantics of copy relocations, assume that you have an exported
553 // variable of type T. It is an ABI-breaking change to add new members at
554 // end of T even though doing that doesn't change the layout of the
555 // existing members. That's because the space for the new members are not
556 // reserved in .bss unless you recompile the main program. That means they
557 // are likely to overlap with other data that happens to be laid out next
558 // to the variable in .bss. This kind of issue is sometimes very hard to
559 // debug. What's a solution? Instead of exporting a varaible V from a DSO,
560 // define an accessor getV().
561 template <class ELFT> static void addCopyRelSymbol(SharedSymbol &ss) {
562 // Copy relocation against zero-sized symbol doesn't make sense.
563 uint64_t symSize = ss.getSize();
564 if (symSize == 0 || ss.alignment == 0)
565 fatal("cannot create a copy relocation for symbol " + toString(ss));
567 // See if this symbol is in a read-only segment. If so, preserve the symbol's
568 // memory protection by reserving space in the .bss.rel.ro section.
569 bool isRO = isReadOnly<ELFT>(ss);
571 make<BssSection>(isRO ? ".bss.rel.ro" : ".bss", symSize, ss.alignment);
573 in.bssRelRo->getParent()->addSection(sec);
575 in.bss->getParent()->addSection(sec);
577 // Look through the DSO's dynamic symbol table for aliases and create a
578 // dynamic symbol for each one. This causes the copy relocation to correctly
579 // interpose any aliases.
580 for (SharedSymbol *sym : getSymbolsAt<ELFT>(ss))
581 replaceWithDefined(*sym, sec, 0, sym->size);
583 mainPart->relaDyn->addReloc(target->copyRel, sec, 0, &ss);
586 // MIPS has an odd notion of "paired" relocations to calculate addends.
587 // For example, if a relocation is of R_MIPS_HI16, there must be a
588 // R_MIPS_LO16 relocation after that, and an addend is calculated using
589 // the two relocations.
590 template <class ELFT, class RelTy>
591 static int64_t computeMipsAddend(const RelTy &rel, const RelTy *end,
592 InputSectionBase &sec, RelExpr expr,
594 if (expr == R_MIPS_GOTREL && isLocal)
595 return sec.getFile<ELFT>()->mipsGp0;
597 // The ABI says that the paired relocation is used only for REL.
598 // See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
602 RelType type = rel.getType(config->isMips64EL);
603 uint32_t pairTy = getMipsPairType(type, isLocal);
604 if (pairTy == R_MIPS_NONE)
607 const uint8_t *buf = sec.data().data();
608 uint32_t symIndex = rel.getSymbol(config->isMips64EL);
610 // To make things worse, paired relocations might not be contiguous in
611 // the relocation table, so we need to do linear search. *sigh*
612 for (const RelTy *ri = &rel; ri != end; ++ri)
613 if (ri->getType(config->isMips64EL) == pairTy &&
614 ri->getSymbol(config->isMips64EL) == symIndex)
615 return target->getImplicitAddend(buf + ri->r_offset, pairTy);
617 warn("can't find matching " + toString(pairTy) + " relocation for " +
622 // Returns an addend of a given relocation. If it is RELA, an addend
623 // is in a relocation itself. If it is REL, we need to read it from an
625 template <class ELFT, class RelTy>
626 static int64_t computeAddend(const RelTy &rel, const RelTy *end,
627 InputSectionBase &sec, RelExpr expr,
630 RelType type = rel.getType(config->isMips64EL);
633 addend = getAddend<ELFT>(rel);
635 const uint8_t *buf = sec.data().data();
636 addend = target->getImplicitAddend(buf + rel.r_offset, type);
639 if (config->emachine == EM_PPC64 && config->isPic && type == R_PPC64_TOC)
640 addend += getPPC64TocBase();
641 if (config->emachine == EM_MIPS)
642 addend += computeMipsAddend<ELFT>(rel, end, sec, expr, isLocal);
647 // Custom error message if Sym is defined in a discarded section.
648 template <class ELFT>
649 static std::string maybeReportDiscarded(Undefined &sym) {
650 auto *file = dyn_cast_or_null<ObjFile<ELFT>>(sym.file);
651 if (!file || !sym.discardedSecIdx ||
652 file->getSections()[sym.discardedSecIdx] != &InputSection::discarded)
654 ArrayRef<Elf_Shdr_Impl<ELFT>> objSections =
655 CHECK(file->getObj().sections(), file);
658 if (sym.type == ELF::STT_SECTION) {
659 msg = "relocation refers to a discarded section: ";
661 file->getObj().getSectionName(&objSections[sym.discardedSecIdx]), file);
663 msg = "relocation refers to a symbol in a discarded section: " +
666 msg += "\n>>> defined in " + toString(file);
668 Elf_Shdr_Impl<ELFT> elfSec = objSections[sym.discardedSecIdx - 1];
669 if (elfSec.sh_type != SHT_GROUP)
672 // If the discarded section is a COMDAT.
673 StringRef signature = file->getShtGroupSignature(objSections, elfSec);
674 if (const InputFile *prevailing =
675 symtab->comdatGroups.lookup(CachedHashStringRef(signature)))
676 msg += "\n>>> section group signature: " + signature.str() +
677 "\n>>> prevailing definition is in " + toString(prevailing);
681 // Undefined diagnostics are collected in a vector and emitted once all of
682 // them are known, so that some postprocessing on the list of undefined symbols
683 // can happen before lld emits diagnostics.
684 struct UndefinedDiag {
687 InputSectionBase *sec;
690 std::vector<Loc> locs;
694 static std::vector<UndefinedDiag> undefs;
696 template <class ELFT>
697 static void reportUndefinedSymbol(const UndefinedDiag &undef) {
698 Symbol &sym = *undef.sym;
700 auto visibility = [&]() -> std::string {
701 switch (sym.visibility) {
713 std::string msg = maybeReportDiscarded<ELFT>(cast<Undefined>(sym));
715 msg = "undefined " + visibility() + "symbol: " + toString(sym);
717 const size_t maxUndefReferences = 10;
719 for (UndefinedDiag::Loc l : undef.locs) {
720 if (i >= maxUndefReferences)
722 InputSectionBase &sec = *l.sec;
723 uint64_t offset = l.offset;
725 msg += "\n>>> referenced by ";
726 std::string src = sec.getSrcMsg(sym, offset);
728 msg += src + "\n>>> ";
729 msg += sec.getObjMsg(offset);
733 if (i < undef.locs.size())
734 msg += ("\n>>> referenced " + Twine(undef.locs.size() - i) + " more times")
737 if (sym.getName().startswith("_ZTV"))
738 msg += "\nthe vtable symbol may be undefined because the class is missing "
739 "its key function (see https://lld.llvm.org/missingkeyfunction)";
747 template <class ELFT> void elf::reportUndefinedSymbols() {
748 // Find the first "undefined symbol" diagnostic for each diagnostic, and
749 // collect all "referenced from" lines at the first diagnostic.
750 DenseMap<Symbol *, UndefinedDiag *> firstRef;
751 for (UndefinedDiag &undef : undefs) {
752 assert(undef.locs.size() == 1);
753 if (UndefinedDiag *canon = firstRef.lookup(undef.sym)) {
754 canon->locs.push_back(undef.locs[0]);
757 firstRef[undef.sym] = &undef;
760 for (const UndefinedDiag &undef : undefs) {
761 if (!undef.locs.empty())
762 reportUndefinedSymbol<ELFT>(undef);
767 // Report an undefined symbol if necessary.
768 // Returns true if the undefined symbol will produce an error message.
769 template <class ELFT>
770 static bool maybeReportUndefined(Symbol &sym, InputSectionBase &sec,
772 if (!sym.isUndefined() || sym.isWeak())
775 bool canBeExternal = !sym.isLocal() && sym.computeBinding() != STB_LOCAL &&
776 sym.visibility == STV_DEFAULT;
777 if (config->unresolvedSymbols == UnresolvedPolicy::Ignore && canBeExternal)
780 // clang (as of 2019-06-12) / gcc (as of 8.2.1) PPC64 may emit a .rela.toc
781 // which references a switch table in a discarded .rodata/.text section. The
782 // .toc and the .rela.toc are incorrectly not placed in the comdat. The ELF
783 // spec says references from outside the group to a STB_LOCAL symbol are not
784 // allowed. Work around the bug.
785 if (config->emachine == EM_PPC64 &&
786 cast<Undefined>(sym).discardedSecIdx != 0 && sec.name == ".toc")
790 (config->unresolvedSymbols == UnresolvedPolicy::Warn && canBeExternal) ||
791 config->noinhibitExec;
792 undefs.push_back({&sym, {{&sec, offset}}, isWarning});
796 // MIPS N32 ABI treats series of successive relocations with the same offset
797 // as a single relocation. The similar approach used by N64 ABI, but this ABI
798 // packs all relocations into the single relocation record. Here we emulate
799 // this for the N32 ABI. Iterate over relocation with the same offset and put
800 // theirs types into the single bit-set.
801 template <class RelTy> static RelType getMipsN32RelType(RelTy *&rel, RelTy *end) {
803 uint64_t offset = rel->r_offset;
806 while (rel != end && rel->r_offset == offset)
807 type |= (rel++)->getType(config->isMips64EL) << (8 * n++);
811 // .eh_frame sections are mergeable input sections, so their input
812 // offsets are not linearly mapped to output section. For each input
813 // offset, we need to find a section piece containing the offset and
814 // add the piece's base address to the input offset to compute the
815 // output offset. That isn't cheap.
817 // This class is to speed up the offset computation. When we process
818 // relocations, we access offsets in the monotonically increasing
819 // order. So we can optimize for that access pattern.
821 // For sections other than .eh_frame, this class doesn't do anything.
825 explicit OffsetGetter(InputSectionBase &sec) {
826 if (auto *eh = dyn_cast<EhInputSection>(&sec))
830 // Translates offsets in input sections to offsets in output sections.
831 // Given offset must increase monotonically. We assume that Piece is
832 // sorted by inputOff.
833 uint64_t get(uint64_t off) {
837 while (i != pieces.size() && pieces[i].inputOff + pieces[i].size <= off)
839 if (i == pieces.size())
840 fatal(".eh_frame: relocation is not in any piece");
842 // Pieces must be contiguous, so there must be no holes in between.
843 assert(pieces[i].inputOff <= off && "Relocation not in any piece");
845 // Offset -1 means that the piece is dead (i.e. garbage collected).
846 if (pieces[i].outputOff == -1)
848 return pieces[i].outputOff + off - pieces[i].inputOff;
852 ArrayRef<EhSectionPiece> pieces;
857 static void addRelativeReloc(InputSectionBase *isec, uint64_t offsetInSec,
858 Symbol *sym, int64_t addend, RelExpr expr,
860 Partition &part = isec->getPartition();
862 // Add a relative relocation. If relrDyn section is enabled, and the
863 // relocation offset is guaranteed to be even, add the relocation to
864 // the relrDyn section, otherwise add it to the relaDyn section.
865 // relrDyn sections don't support odd offsets. Also, relrDyn sections
866 // don't store the addend values, so we must write it to the relocated
868 if (part.relrDyn && isec->alignment >= 2 && offsetInSec % 2 == 0) {
869 isec->relocations.push_back({expr, type, offsetInSec, addend, sym});
870 part.relrDyn->relocs.push_back({isec, offsetInSec});
873 part.relaDyn->addReloc(target->relativeRel, isec, offsetInSec, sym, addend,
877 template <class ELFT, class GotPltSection>
878 static void addPltEntry(PltSection *plt, GotPltSection *gotPlt,
879 RelocationBaseSection *rel, RelType type, Symbol &sym) {
880 plt->addEntry<ELFT>(sym);
881 gotPlt->addEntry(sym);
883 {type, gotPlt, sym.getGotPltOffset(), !sym.isPreemptible, &sym, 0});
886 static void addGotEntry(Symbol &sym) {
887 in.got->addEntry(sym);
889 RelExpr expr = sym.isTls() ? R_TLS : R_ABS;
890 uint64_t off = sym.getGotOffset();
892 // If a GOT slot value can be calculated at link-time, which is now,
893 // we can just fill that out.
895 // (We don't actually write a value to a GOT slot right now, but we
896 // add a static relocation to a Relocations vector so that
897 // InputSection::relocate will do the work for us. We may be able
898 // to just write a value now, but it is a TODO.)
899 bool isLinkTimeConstant =
900 !sym.isPreemptible && (!config->isPic || isAbsolute(sym));
901 if (isLinkTimeConstant) {
902 in.got->relocations.push_back({expr, target->symbolicRel, off, 0, &sym});
906 // Otherwise, we emit a dynamic relocation to .rel[a].dyn so that
907 // the GOT slot will be fixed at load-time.
908 if (!sym.isTls() && !sym.isPreemptible && config->isPic && !isAbsolute(sym)) {
909 addRelativeReloc(in.got, off, &sym, 0, R_ABS, target->symbolicRel);
912 mainPart->relaDyn->addReloc(
913 sym.isTls() ? target->tlsGotRel : target->gotRel, in.got, off, &sym, 0,
914 sym.isPreemptible ? R_ADDEND : R_ABS, target->symbolicRel);
917 // Return true if we can define a symbol in the executable that
918 // contains the value/function of a symbol defined in a shared
920 static bool canDefineSymbolInExecutable(Symbol &sym) {
921 // If the symbol has default visibility the symbol defined in the
922 // executable will preempt it.
923 // Note that we want the visibility of the shared symbol itself, not
924 // the visibility of the symbol in the output file we are producing. That is
925 // why we use Sym.stOther.
926 if ((sym.stOther & 0x3) == STV_DEFAULT)
929 // If we are allowed to break address equality of functions, defining
930 // a plt entry will allow the program to call the function in the
931 // .so, but the .so and the executable will no agree on the address
932 // of the function. Similar logic for objects.
933 return ((sym.isFunc() && config->ignoreFunctionAddressEquality) ||
934 (sym.isObject() && config->ignoreDataAddressEquality));
937 // The reason we have to do this early scan is as follows
938 // * To mmap the output file, we need to know the size
939 // * For that, we need to know how many dynamic relocs we will have.
940 // It might be possible to avoid this by outputting the file with write:
941 // * Write the allocated output sections, computing addresses.
942 // * Apply relocations, recording which ones require a dynamic reloc.
943 // * Write the dynamic relocations.
944 // * Write the rest of the file.
945 // This would have some drawbacks. For example, we would only know if .rela.dyn
946 // is needed after applying relocations. If it is, it will go after rw and rx
947 // sections. Given that it is ro, we will need an extra PT_LOAD. This
948 // complicates things for the dynamic linker and means we would have to reserve
949 // space for the extra PT_LOAD even if we end up not using it.
950 template <class ELFT, class RelTy>
951 static void processRelocAux(InputSectionBase &sec, RelExpr expr, RelType type,
952 uint64_t offset, Symbol &sym, const RelTy &rel,
954 // If the relocation is known to be a link-time constant, we know no dynamic
955 // relocation will be created, pass the control to relocateAlloc() or
956 // relocateNonAlloc() to resolve it.
958 // The behavior of an undefined weak reference is implementation defined. If
959 // the relocation is to a weak undef, and we are producing an executable, let
960 // relocate{,Non}Alloc() resolve it.
961 if (isStaticLinkTimeConstant(expr, type, sym, sec, offset) ||
962 (!config->shared && sym.isUndefWeak())) {
963 sec.relocations.push_back({expr, type, offset, addend, &sym});
967 bool canWrite = (sec.flags & SHF_WRITE) || !config->zText;
969 RelType rel = target->getDynRel(type);
970 if (expr == R_GOT || (rel == target->symbolicRel && !sym.isPreemptible)) {
971 addRelativeReloc(&sec, offset, &sym, addend, expr, type);
973 } else if (rel != 0) {
974 if (config->emachine == EM_MIPS && rel == target->symbolicRel)
975 rel = target->relativeRel;
976 sec.getPartition().relaDyn->addReloc(rel, &sec, offset, &sym, addend,
979 // MIPS ABI turns using of GOT and dynamic relocations inside out.
980 // While regular ABI uses dynamic relocations to fill up GOT entries
981 // MIPS ABI requires dynamic linker to fills up GOT entries using
982 // specially sorted dynamic symbol table. This affects even dynamic
983 // relocations against symbols which do not require GOT entries
984 // creation explicitly, i.e. do not have any GOT-relocations. So if
985 // a preemptible symbol has a dynamic relocation we anyway have
986 // to create a GOT entry for it.
987 // If a non-preemptible symbol has a dynamic relocation against it,
988 // dynamic linker takes it st_value, adds offset and writes down
989 // result of the dynamic relocation. In case of preemptible symbol
990 // dynamic linker performs symbol resolution, writes the symbol value
991 // to the GOT entry and reads the GOT entry when it needs to perform
992 // a dynamic relocation.
993 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf p.4-19
994 if (config->emachine == EM_MIPS)
995 in.mipsGot->addEntry(*sec.file, sym, addend, expr);
1000 if (!canWrite && (config->isPic && !isRelExpr(expr))) {
1002 "can't create dynamic relocation " + toString(type) + " against " +
1003 (sym.getName().empty() ? "local symbol" : "symbol: " + toString(sym)) +
1004 " in readonly segment; recompile object files with -fPIC "
1005 "or pass '-Wl,-z,notext' to allow text relocations in the output" +
1006 getLocation(sec, sym, offset));
1010 // Copy relocations (for STT_OBJECT) and canonical PLT (for STT_FUNC) are only
1011 // possible in an executable.
1013 // Among R_ABS relocatoin types, symbolicRel has the same size as the word
1014 // size. Others have fewer bits and may cause runtime overflow in -pie/-shared
1015 // mode. Disallow them.
1016 if (config->shared ||
1017 (config->pie && expr == R_ABS && type != target->symbolicRel)) {
1019 "relocation " + toString(type) + " cannot be used against " +
1020 (sym.getName().empty() ? "local symbol" : "symbol " + toString(sym)) +
1021 "; recompile with -fPIC" + getLocation(sec, sym, offset));
1025 // If the symbol is undefined we already reported any relevant errors.
1026 if (sym.isUndefined())
1029 if (!canDefineSymbolInExecutable(sym)) {
1030 error("cannot preempt symbol: " + toString(sym) +
1031 getLocation(sec, sym, offset));
1035 if (sym.isObject()) {
1036 // Produce a copy relocation.
1037 if (auto *ss = dyn_cast<SharedSymbol>(&sym)) {
1038 if (!config->zCopyreloc)
1039 error("unresolvable relocation " + toString(type) +
1040 " against symbol '" + toString(*ss) +
1041 "'; recompile with -fPIC or remove '-z nocopyreloc'" +
1042 getLocation(sec, sym, offset));
1043 addCopyRelSymbol<ELFT>(*ss);
1045 sec.relocations.push_back({expr, type, offset, addend, &sym});
1050 // This handles a non PIC program call to function in a shared library. In
1051 // an ideal world, we could just report an error saying the relocation can
1052 // overflow at runtime. In the real world with glibc, crt1.o has a
1053 // R_X86_64_PC32 pointing to libc.so.
1055 // The general idea on how to handle such cases is to create a PLT entry and
1056 // use that as the function value.
1058 // For the static linking part, we just return a plt expr and everything
1059 // else will use the PLT entry as the address.
1061 // The remaining problem is making sure pointer equality still works. We
1062 // need the help of the dynamic linker for that. We let it know that we have
1063 // a direct reference to a so symbol by creating an undefined symbol with a
1064 // non zero st_value. Seeing that, the dynamic linker resolves the symbol to
1065 // the value of the symbol we created. This is true even for got entries, so
1066 // pointer equality is maintained. To avoid an infinite loop, the only entry
1067 // that points to the real function is a dedicated got entry used by the
1068 // plt. That is identified by special relocation types (R_X86_64_JUMP_SLOT,
1069 // R_386_JMP_SLOT, etc).
1071 // For position independent executable on i386, the plt entry requires ebx
1072 // to be set. This causes two problems:
1073 // * If some code has a direct reference to a function, it was probably
1074 // compiled without -fPIE/-fPIC and doesn't maintain ebx.
1075 // * If a library definition gets preempted to the executable, it will have
1076 // the wrong ebx value.
1077 if (config->pie && config->emachine == EM_386)
1078 errorOrWarn("symbol '" + toString(sym) +
1079 "' cannot be preempted; recompile with -fPIE" +
1080 getLocation(sec, sym, offset));
1082 addPltEntry<ELFT>(in.plt, in.gotPlt, in.relaPlt, target->pltRel, sym);
1083 if (!sym.isDefined())
1086 target->pltHeaderSize + target->pltEntrySize * sym.pltIndex, 0);
1087 sym.needsPltAddr = true;
1088 sec.relocations.push_back({expr, type, offset, addend, &sym});
1092 errorOrWarn("symbol '" + toString(sym) + "' has no type" +
1093 getLocation(sec, sym, offset));
1096 struct IRelativeReloc {
1098 InputSectionBase *sec;
1103 static std::vector<IRelativeReloc> iRelativeRelocs;
1105 template <class ELFT, class RelTy>
1106 static void scanReloc(InputSectionBase &sec, OffsetGetter &getOffset, RelTy *&i,
1108 const RelTy &rel = *i;
1109 uint32_t symIndex = rel.getSymbol(config->isMips64EL);
1110 Symbol &sym = sec.getFile<ELFT>()->getSymbol(symIndex);
1113 // Deal with MIPS oddity.
1114 if (config->mipsN32Abi) {
1115 type = getMipsN32RelType(i, end);
1117 type = rel.getType(config->isMips64EL);
1121 // Get an offset in an output section this relocation is applied to.
1122 uint64_t offset = getOffset.get(rel.r_offset);
1123 if (offset == uint64_t(-1))
1126 // Error if the target symbol is undefined. Symbol index 0 may be used by
1127 // marker relocations, e.g. R_*_NONE and R_ARM_V4BX. Don't error on them.
1128 if (symIndex != 0 && maybeReportUndefined<ELFT>(sym, sec, rel.r_offset))
1131 const uint8_t *relocatedAddr = sec.data().begin() + rel.r_offset;
1132 RelExpr expr = target->getRelExpr(type, sym, relocatedAddr);
1134 // Ignore "hint" relocations because they are only markers for relaxation.
1135 if (oneof<R_HINT, R_NONE>(expr))
1138 // We can separate the small code model relocations into 2 categories:
1139 // 1) Those that access the compiler generated .toc sections.
1140 // 2) Those that access the linker allocated got entries.
1141 // lld allocates got entries to symbols on demand. Since we don't try to sort
1142 // the got entries in any way, we don't have to track which objects have
1143 // got-based small code model relocs. The .toc sections get placed after the
1144 // end of the linker allocated .got section and we do sort those so sections
1145 // addressed with small code model relocations come first.
1146 if (config->emachine == EM_PPC64 && isPPC64SmallCodeModelTocReloc(type))
1147 sec.file->ppc64SmallCodeModelTocRelocs = true;
1149 if (sym.isGnuIFunc() && !config->zText && config->warnIfuncTextrel) {
1150 warn("using ifunc symbols when text relocations are allowed may produce "
1151 "a binary that will segfault, if the object file is linked with "
1152 "old version of glibc (glibc 2.28 and earlier). If this applies to "
1153 "you, consider recompiling the object files without -fPIC and "
1154 "without -Wl,-z,notext option. Use -no-warn-ifunc-textrel to "
1155 "turn off this warning." +
1156 getLocation(sec, sym, offset));
1160 int64_t addend = computeAddend<ELFT>(rel, end, sec, expr, sym.isLocal());
1162 // Relax relocations.
1164 // If we know that a PLT entry will be resolved within the same ELF module, we
1165 // can skip PLT access and directly jump to the destination function. For
1166 // example, if we are linking a main exectuable, all dynamic symbols that can
1167 // be resolved within the executable will actually be resolved that way at
1168 // runtime, because the main exectuable is always at the beginning of a search
1169 // list. We can leverage that fact.
1170 if (!sym.isPreemptible && (!sym.isGnuIFunc() || config->zIfuncNoplt)) {
1171 if (expr == R_GOT_PC && !isAbsoluteValue(sym)) {
1172 expr = target->adjustRelaxExpr(type, relocatedAddr, expr);
1174 // Addend of R_PPC_PLTREL24 is used to choose call stub type. It should be
1175 // ignored if optimized to R_PC.
1176 if (config->emachine == EM_PPC && expr == R_PPC32_PLTREL)
1178 expr = fromPlt(expr);
1182 // If the relocation does not emit a GOT or GOTPLT entry but its computation
1183 // uses their addresses, we need GOT or GOTPLT to be created.
1185 // The 4 types that relative GOTPLT are all x86 and x86-64 specific.
1186 if (oneof<R_GOTPLTONLY_PC, R_GOTPLTREL, R_GOTPLT, R_TLSGD_GOTPLT>(expr)) {
1187 in.gotPlt->hasGotPltOffRel = true;
1188 } else if (oneof<R_GOTONLY_PC, R_GOTREL, R_PPC64_TOCBASE, R_PPC64_RELAX_TOC>(
1190 in.got->hasGotOffRel = true;
1193 // Process some TLS relocations, including relaxing TLS relocations.
1194 // Note that this function does not handle all TLS relocations.
1195 if (unsigned processed =
1196 handleTlsRelocation<ELFT>(type, sym, sec, offset, addend, expr)) {
1197 i += (processed - 1);
1201 // We were asked not to generate PLT entries for ifuncs. Instead, pass the
1202 // direct relocation on through.
1203 if (sym.isGnuIFunc() && config->zIfuncNoplt) {
1204 sym.exportDynamic = true;
1205 mainPart->relaDyn->addReloc(type, &sec, offset, &sym, addend, R_ADDEND, type);
1209 // Non-preemptible ifuncs require special handling. First, handle the usual
1210 // case where the symbol isn't one of these.
1211 if (!sym.isGnuIFunc() || sym.isPreemptible) {
1212 // If a relocation needs PLT, we create PLT and GOTPLT slots for the symbol.
1213 if (needsPlt(expr) && !sym.isInPlt())
1214 addPltEntry<ELFT>(in.plt, in.gotPlt, in.relaPlt, target->pltRel, sym);
1216 // Create a GOT slot if a relocation needs GOT.
1217 if (needsGot(expr)) {
1218 if (config->emachine == EM_MIPS) {
1219 // MIPS ABI has special rules to process GOT entries and doesn't
1220 // require relocation entries for them. A special case is TLS
1221 // relocations. In that case dynamic loader applies dynamic
1222 // relocations to initialize TLS GOT entries.
1223 // See "Global Offset Table" in Chapter 5 in the following document
1224 // for detailed description:
1225 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
1226 in.mipsGot->addEntry(*sec.file, sym, addend, expr);
1227 } else if (!sym.isInGot()) {
1232 // Handle a reference to a non-preemptible ifunc. These are special in a
1235 // - Unlike most non-preemptible symbols, non-preemptible ifuncs do not have
1236 // a fixed value. But assuming that all references to the ifunc are
1237 // GOT-generating or PLT-generating, the handling of an ifunc is
1238 // relatively straightforward. We create a PLT entry in Iplt, which is
1239 // usually at the end of .plt, which makes an indirect call using a
1240 // matching GOT entry in igotPlt, which is usually at the end of .got.plt.
1241 // The GOT entry is relocated using an IRELATIVE relocation in relaIplt,
1242 // which is usually at the end of .rela.plt. Unlike most relocations in
1243 // .rela.plt, which may be evaluated lazily without -z now, dynamic
1244 // loaders evaluate IRELATIVE relocs eagerly, which means that for
1245 // IRELATIVE relocs only, GOT-generating relocations can point directly to
1246 // .got.plt without requiring a separate GOT entry.
1248 // - Despite the fact that an ifunc does not have a fixed value, compilers
1249 // that are not passed -fPIC will assume that they do, and will emit
1250 // direct (non-GOT-generating, non-PLT-generating) relocations to the
1251 // symbol. This means that if a direct relocation to the symbol is
1252 // seen, the linker must set a value for the symbol, and this value must
1253 // be consistent no matter what type of reference is made to the symbol.
1254 // This can be done by creating a PLT entry for the symbol in the way
1255 // described above and making it canonical, that is, making all references
1256 // point to the PLT entry instead of the resolver. In lld we also store
1257 // the address of the PLT entry in the dynamic symbol table, which means
1258 // that the symbol will also have the same value in other modules.
1259 // Because the value loaded from the GOT needs to be consistent with
1260 // the value computed using a direct relocation, a non-preemptible ifunc
1261 // may end up with two GOT entries, one in .got.plt that points to the
1262 // address returned by the resolver and is used only by the PLT entry,
1263 // and another in .got that points to the PLT entry and is used by
1264 // GOT-generating relocations.
1266 // - The fact that these symbols do not have a fixed value makes them an
1267 // exception to the general rule that a statically linked executable does
1268 // not require any form of dynamic relocation. To handle these relocations
1269 // correctly, the IRELATIVE relocations are stored in an array which a
1270 // statically linked executable's startup code must enumerate using the
1271 // linker-defined symbols __rela?_iplt_{start,end}.
1273 // - An absolute relocation to a non-preemptible ifunc (such as a global
1274 // variable containing a pointer to the ifunc) needs to be relocated in
1275 // the exact same way as a GOT entry, so we can avoid needing to make the
1276 // PLT entry canonical by translating such relocations into IRELATIVE
1277 // relocations in the relaIplt.
1278 if (!sym.isInPlt()) {
1279 // Create PLT and GOTPLT slots for the symbol.
1280 sym.isInIplt = true;
1282 // Create a copy of the symbol to use as the target of the IRELATIVE
1283 // relocation in the igotPlt. This is in case we make the PLT canonical
1284 // later, which would overwrite the original symbol.
1286 // FIXME: Creating a copy of the symbol here is a bit of a hack. All
1287 // that's really needed to create the IRELATIVE is the section and value,
1288 // so ideally we should just need to copy those.
1289 auto *directSym = make<Defined>(cast<Defined>(sym));
1290 addPltEntry<ELFT>(in.iplt, in.igotPlt, in.relaIplt, target->iRelativeRel,
1292 sym.pltIndex = directSym->pltIndex;
1294 if (expr == R_ABS && addend == 0 && (sec.flags & SHF_WRITE)) {
1295 // We might be able to represent this as an IRELATIVE. But we don't know
1296 // yet whether some later relocation will make the symbol point to a
1297 // canonical PLT, which would make this either a dynamic RELATIVE (PIC) or
1298 // static (non-PIC) relocation. So we keep a record of the information
1299 // required to process the relocation, and after scanRelocs() has been
1300 // called on all relocations, the relocation is resolved by
1301 // addIRelativeRelocs().
1302 iRelativeRelocs.push_back({type, &sec, offset, &sym});
1305 if (needsGot(expr)) {
1306 // Redirect GOT accesses to point to the Igot.
1308 // This field is also used to keep track of whether we ever needed a GOT
1309 // entry. If we did and we make the PLT canonical later, we'll need to
1310 // create a GOT entry pointing to the PLT entry for Sym.
1311 sym.gotInIgot = true;
1312 } else if (!needsPlt(expr)) {
1313 // Make the ifunc's PLT entry canonical by changing the value of its
1314 // symbol to redirect all references to point to it.
1315 unsigned entryOffset = sym.pltIndex * target->pltEntrySize;
1316 if (config->zRetpolineplt)
1317 entryOffset += target->pltHeaderSize;
1319 auto &d = cast<Defined>(sym);
1320 d.section = in.iplt;
1321 d.value = entryOffset;
1323 // It's important to set the symbol type here so that dynamic loaders
1324 // don't try to call the PLT as if it were an ifunc resolver.
1327 if (sym.gotInIgot) {
1328 // We previously encountered a GOT generating reference that we
1329 // redirected to the Igot. Now that the PLT entry is canonical we must
1330 // clear the redirection to the Igot and add a GOT entry. As we've
1331 // changed the symbol type to STT_FUNC future GOT generating references
1332 // will naturally use this GOT entry.
1334 // We don't need to worry about creating a MIPS GOT here because ifuncs
1335 // aren't a thing on MIPS.
1336 sym.gotInIgot = false;
1342 processRelocAux<ELFT>(sec, expr, type, offset, sym, rel, addend);
1345 template <class ELFT, class RelTy>
1346 static void scanRelocs(InputSectionBase &sec, ArrayRef<RelTy> rels) {
1347 OffsetGetter getOffset(sec);
1349 // Not all relocations end up in Sec.Relocations, but a lot do.
1350 sec.relocations.reserve(rels.size());
1352 for (auto i = rels.begin(), end = rels.end(); i != end;)
1353 scanReloc<ELFT>(sec, getOffset, i, end);
1355 // Sort relocations by offset for more efficient searching for
1356 // R_RISCV_PCREL_HI20 and R_PPC64_ADDR64.
1357 if (config->emachine == EM_RISCV ||
1358 (config->emachine == EM_PPC64 && sec.name == ".toc"))
1359 llvm::stable_sort(sec.relocations,
1360 [](const Relocation &lhs, const Relocation &rhs) {
1361 return lhs.offset < rhs.offset;
1365 template <class ELFT> void elf::scanRelocations(InputSectionBase &s) {
1366 if (s.areRelocsRela)
1367 scanRelocs<ELFT>(s, s.relas<ELFT>());
1369 scanRelocs<ELFT>(s, s.rels<ELFT>());
1372 // Figure out which representation to use for any absolute relocs to
1373 // non-preemptible ifuncs that we visited during scanRelocs().
1374 void elf::addIRelativeRelocs() {
1375 for (IRelativeReloc &r : iRelativeRelocs) {
1376 if (r.sym->type == STT_GNU_IFUNC)
1377 in.relaIplt->addReloc(
1378 {target->iRelativeRel, r.sec, r.offset, true, r.sym, 0});
1379 else if (config->isPic)
1380 addRelativeReloc(r.sec, r.offset, r.sym, 0, R_ABS, r.type);
1382 r.sec->relocations.push_back({R_ABS, r.type, r.offset, 0, r.sym});
1384 iRelativeRelocs.clear();
1387 static bool mergeCmp(const InputSection *a, const InputSection *b) {
1388 // std::merge requires a strict weak ordering.
1389 if (a->outSecOff < b->outSecOff)
1392 if (a->outSecOff == b->outSecOff) {
1393 auto *ta = dyn_cast<ThunkSection>(a);
1394 auto *tb = dyn_cast<ThunkSection>(b);
1396 // Check if Thunk is immediately before any specific Target
1397 // InputSection for example Mips LA25 Thunks.
1398 if (ta && ta->getTargetInputSection() == b)
1401 // Place Thunk Sections without specific targets before
1402 // non-Thunk Sections.
1403 if (ta && !tb && !ta->getTargetInputSection())
1410 // Call Fn on every executable InputSection accessed via the linker script
1411 // InputSectionDescription::Sections.
1412 static void forEachInputSectionDescription(
1413 ArrayRef<OutputSection *> outputSections,
1414 llvm::function_ref<void(OutputSection *, InputSectionDescription *)> fn) {
1415 for (OutputSection *os : outputSections) {
1416 if (!(os->flags & SHF_ALLOC) || !(os->flags & SHF_EXECINSTR))
1418 for (BaseCommand *bc : os->sectionCommands)
1419 if (auto *isd = dyn_cast<InputSectionDescription>(bc))
1424 // Thunk Implementation
1426 // Thunks (sometimes called stubs, veneers or branch islands) are small pieces
1427 // of code that the linker inserts inbetween a caller and a callee. The thunks
1428 // are added at link time rather than compile time as the decision on whether
1429 // a thunk is needed, such as the caller and callee being out of range, can only
1430 // be made at link time.
1432 // It is straightforward to tell given the current state of the program when a
1433 // thunk is needed for a particular call. The more difficult part is that
1434 // the thunk needs to be placed in the program such that the caller can reach
1435 // the thunk and the thunk can reach the callee; furthermore, adding thunks to
1436 // the program alters addresses, which can mean more thunks etc.
1438 // In lld we have a synthetic ThunkSection that can hold many Thunks.
1439 // The decision to have a ThunkSection act as a container means that we can
1440 // more easily handle the most common case of a single block of contiguous
1441 // Thunks by inserting just a single ThunkSection.
1443 // The implementation of Thunks in lld is split across these areas
1444 // Relocations.cpp : Framework for creating and placing thunks
1445 // Thunks.cpp : The code generated for each supported thunk
1446 // Target.cpp : Target specific hooks that the framework uses to decide when
1448 // Synthetic.cpp : Implementation of ThunkSection
1449 // Writer.cpp : Iteratively call framework until no more Thunks added
1451 // Thunk placement requirements:
1452 // Mips LA25 thunks. These must be placed immediately before the callee section
1453 // We can assume that the caller is in range of the Thunk. These are modelled
1454 // by Thunks that return the section they must precede with
1455 // getTargetInputSection().
1457 // ARM interworking and range extension thunks. These thunks must be placed
1458 // within range of the caller. All implemented ARM thunks can always reach the
1459 // callee as they use an indirect jump via a register that has no range
1462 // Thunk placement algorithm:
1463 // For Mips LA25 ThunkSections; the placement is explicit, it has to be before
1464 // getTargetInputSection().
1466 // For thunks that must be placed within range of the caller there are many
1467 // possible choices given that the maximum range from the caller is usually
1468 // much larger than the average InputSection size. Desirable properties include:
1469 // - Maximize reuse of thunks by multiple callers
1470 // - Minimize number of ThunkSections to simplify insertion
1471 // - Handle impact of already added Thunks on addresses
1472 // - Simple to understand and implement
1474 // In lld for the first pass, we pre-create one or more ThunkSections per
1475 // InputSectionDescription at Target specific intervals. A ThunkSection is
1476 // placed so that the estimated end of the ThunkSection is within range of the
1477 // start of the InputSectionDescription or the previous ThunkSection. For
1479 // InputSectionDescription
1489 // The intention is that we can add a Thunk to a ThunkSection that is well
1490 // spaced enough to service a number of callers without having to do a lot
1491 // of work. An important principle is that it is not an error if a Thunk cannot
1492 // be placed in a pre-created ThunkSection; when this happens we create a new
1493 // ThunkSection placed next to the caller. This allows us to handle the vast
1494 // majority of thunks simply, but also handle rare cases where the branch range
1495 // is smaller than the target specific spacing.
1497 // The algorithm is expected to create all the thunks that are needed in a
1498 // single pass, with a small number of programs needing a second pass due to
1499 // the insertion of thunks in the first pass increasing the offset between
1500 // callers and callees that were only just in range.
1502 // A consequence of allowing new ThunkSections to be created outside of the
1503 // pre-created ThunkSections is that in rare cases calls to Thunks that were in
1504 // range in pass K, are out of range in some pass > K due to the insertion of
1505 // more Thunks in between the caller and callee. When this happens we retarget
1506 // the relocation back to the original target and create another Thunk.
1508 // Remove ThunkSections that are empty, this should only be the initial set
1509 // precreated on pass 0.
1511 // Insert the Thunks for OutputSection OS into their designated place
1512 // in the Sections vector, and recalculate the InputSection output section
1514 // This may invalidate any output section offsets stored outside of InputSection
1515 void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> outputSections) {
1516 forEachInputSectionDescription(
1517 outputSections, [&](OutputSection *os, InputSectionDescription *isd) {
1518 if (isd->thunkSections.empty())
1521 // Remove any zero sized precreated Thunks.
1522 llvm::erase_if(isd->thunkSections,
1523 [](const std::pair<ThunkSection *, uint32_t> &ts) {
1524 return ts.first->getSize() == 0;
1527 // ISD->ThunkSections contains all created ThunkSections, including
1528 // those inserted in previous passes. Extract the Thunks created this
1529 // pass and order them in ascending outSecOff.
1530 std::vector<ThunkSection *> newThunks;
1531 for (const std::pair<ThunkSection *, uint32_t> ts : isd->thunkSections)
1532 if (ts.second == pass)
1533 newThunks.push_back(ts.first);
1534 llvm::stable_sort(newThunks,
1535 [](const ThunkSection *a, const ThunkSection *b) {
1536 return a->outSecOff < b->outSecOff;
1539 // Merge sorted vectors of Thunks and InputSections by outSecOff
1540 std::vector<InputSection *> tmp;
1541 tmp.reserve(isd->sections.size() + newThunks.size());
1543 std::merge(isd->sections.begin(), isd->sections.end(),
1544 newThunks.begin(), newThunks.end(), std::back_inserter(tmp),
1547 isd->sections = std::move(tmp);
1551 // Find or create a ThunkSection within the InputSectionDescription (ISD) that
1552 // is in range of Src. An ISD maps to a range of InputSections described by a
1553 // linker script section pattern such as { .text .text.* }.
1554 ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *os, InputSection *isec,
1555 InputSectionDescription *isd,
1556 uint32_t type, uint64_t src) {
1557 for (std::pair<ThunkSection *, uint32_t> tp : isd->thunkSections) {
1558 ThunkSection *ts = tp.first;
1559 uint64_t tsBase = os->addr + ts->outSecOff;
1560 uint64_t tsLimit = tsBase + ts->getSize();
1561 if (target->inBranchRange(type, src, (src > tsLimit) ? tsBase : tsLimit))
1565 // No suitable ThunkSection exists. This can happen when there is a branch
1566 // with lower range than the ThunkSection spacing or when there are too
1567 // many Thunks. Create a new ThunkSection as close to the InputSection as
1568 // possible. Error if InputSection is so large we cannot place ThunkSection
1569 // anywhere in Range.
1570 uint64_t thunkSecOff = isec->outSecOff;
1571 if (!target->inBranchRange(type, src, os->addr + thunkSecOff)) {
1572 thunkSecOff = isec->outSecOff + isec->getSize();
1573 if (!target->inBranchRange(type, src, os->addr + thunkSecOff))
1574 fatal("InputSection too large for range extension thunk " +
1575 isec->getObjMsg(src - (os->addr + isec->outSecOff)));
1577 return addThunkSection(os, isd, thunkSecOff);
1580 // Add a Thunk that needs to be placed in a ThunkSection that immediately
1581 // precedes its Target.
1582 ThunkSection *ThunkCreator::getISThunkSec(InputSection *isec) {
1583 ThunkSection *ts = thunkedSections.lookup(isec);
1587 // Find InputSectionRange within Target Output Section (TOS) that the
1588 // InputSection (IS) that we need to precede is in.
1589 OutputSection *tos = isec->getParent();
1590 for (BaseCommand *bc : tos->sectionCommands) {
1591 auto *isd = dyn_cast<InputSectionDescription>(bc);
1592 if (!isd || isd->sections.empty())
1595 InputSection *first = isd->sections.front();
1596 InputSection *last = isd->sections.back();
1598 if (isec->outSecOff < first->outSecOff || last->outSecOff < isec->outSecOff)
1601 ts = addThunkSection(tos, isd, isec->outSecOff);
1602 thunkedSections[isec] = ts;
1609 // Create one or more ThunkSections per OS that can be used to place Thunks.
1610 // We attempt to place the ThunkSections using the following desirable
1612 // - Within range of the maximum number of callers
1613 // - Minimise the number of ThunkSections
1615 // We follow a simple but conservative heuristic to place ThunkSections at
1616 // offsets that are multiples of a Target specific branch range.
1617 // For an InputSectionDescription that is smaller than the range, a single
1618 // ThunkSection at the end of the range will do.
1620 // For an InputSectionDescription that is more than twice the size of the range,
1621 // we place the last ThunkSection at range bytes from the end of the
1622 // InputSectionDescription in order to increase the likelihood that the
1623 // distance from a thunk to its target will be sufficiently small to
1624 // allow for the creation of a short thunk.
1625 void ThunkCreator::createInitialThunkSections(
1626 ArrayRef<OutputSection *> outputSections) {
1627 uint32_t thunkSectionSpacing = target->getThunkSectionSpacing();
1629 forEachInputSectionDescription(
1630 outputSections, [&](OutputSection *os, InputSectionDescription *isd) {
1631 if (isd->sections.empty())
1634 uint32_t isdBegin = isd->sections.front()->outSecOff;
1636 isd->sections.back()->outSecOff + isd->sections.back()->getSize();
1637 uint32_t lastThunkLowerBound = -1;
1638 if (isdEnd - isdBegin > thunkSectionSpacing * 2)
1639 lastThunkLowerBound = isdEnd - thunkSectionSpacing;
1642 uint32_t prevIsecLimit = isdBegin;
1643 uint32_t thunkUpperBound = isdBegin + thunkSectionSpacing;
1645 for (const InputSection *isec : isd->sections) {
1646 isecLimit = isec->outSecOff + isec->getSize();
1647 if (isecLimit > thunkUpperBound) {
1648 addThunkSection(os, isd, prevIsecLimit);
1649 thunkUpperBound = prevIsecLimit + thunkSectionSpacing;
1651 if (isecLimit > lastThunkLowerBound)
1653 prevIsecLimit = isecLimit;
1655 addThunkSection(os, isd, isecLimit);
1659 ThunkSection *ThunkCreator::addThunkSection(OutputSection *os,
1660 InputSectionDescription *isd,
1662 auto *ts = make<ThunkSection>(os, off);
1663 ts->partition = os->partition;
1664 isd->thunkSections.push_back({ts, pass});
1668 static bool isThunkSectionCompatible(InputSection *source,
1669 SectionBase *target) {
1670 // We can't reuse thunks in different loadable partitions because they might
1671 // not be loaded. But partition 1 (the main partition) will always be loaded.
1672 if (source->partition != target->partition)
1673 return target->partition == 1;
1677 std::pair<Thunk *, bool> ThunkCreator::getThunk(InputSection *isec,
1678 Relocation &rel, uint64_t src) {
1679 std::vector<Thunk *> *thunkVec = nullptr;
1681 // We use (section, offset) pair to find the thunk position if possible so
1682 // that we create only one thunk for aliased symbols or ICFed sections.
1683 if (auto *d = dyn_cast<Defined>(rel.sym))
1684 if (!d->isInPlt() && d->section)
1685 thunkVec = &thunkedSymbolsBySection[{d->section->repl, d->value}];
1687 thunkVec = &thunkedSymbols[rel.sym];
1689 // Check existing Thunks for Sym to see if they can be reused
1690 for (Thunk *t : *thunkVec)
1691 if (isThunkSectionCompatible(isec, t->getThunkTargetSym()->section) &&
1692 t->isCompatibleWith(*isec, rel) &&
1693 target->inBranchRange(rel.type, src, t->getThunkTargetSym()->getVA()))
1694 return std::make_pair(t, false);
1696 // No existing compatible Thunk in range, create a new one
1697 Thunk *t = addThunk(*isec, rel);
1698 thunkVec->push_back(t);
1699 return std::make_pair(t, true);
1702 // Return true if the relocation target is an in range Thunk.
1703 // Return false if the relocation is not to a Thunk. If the relocation target
1704 // was originally to a Thunk, but is no longer in range we revert the
1705 // relocation back to its original non-Thunk target.
1706 bool ThunkCreator::normalizeExistingThunk(Relocation &rel, uint64_t src) {
1707 if (Thunk *t = thunks.lookup(rel.sym)) {
1708 if (target->inBranchRange(rel.type, src, rel.sym->getVA()))
1710 rel.sym = &t->destination;
1711 if (rel.sym->isInPlt())
1712 rel.expr = toPlt(rel.expr);
1717 // Process all relocations from the InputSections that have been assigned
1718 // to InputSectionDescriptions and redirect through Thunks if needed. The
1719 // function should be called iteratively until it returns false.
1722 // All InputSections that may need a Thunk are reachable from
1723 // OutputSectionCommands.
1725 // All OutputSections have an address and all InputSections have an offset
1726 // within the OutputSection.
1728 // The offsets between caller (relocation place) and callee
1729 // (relocation target) will not be modified outside of createThunks().
1732 // If return value is true then ThunkSections have been inserted into
1733 // OutputSections. All relocations that needed a Thunk based on the information
1734 // available to createThunks() on entry have been redirected to a Thunk. Note
1735 // that adding Thunks changes offsets between caller and callee so more Thunks
1738 // If return value is false then no more Thunks are needed, and createThunks has
1739 // made no changes. If the target requires range extension thunks, currently
1740 // ARM, then any future change in offset between caller and callee risks a
1741 // relocation out of range error.
1742 bool ThunkCreator::createThunks(ArrayRef<OutputSection *> outputSections) {
1743 bool addressesChanged = false;
1745 if (pass == 0 && target->getThunkSectionSpacing())
1746 createInitialThunkSections(outputSections);
1748 // With Thunk Size much smaller than branch range we expect to
1749 // converge quickly; if we get to 10 something has gone wrong.
1751 fatal("thunk creation not converged");
1753 // Create all the Thunks and insert them into synthetic ThunkSections. The
1754 // ThunkSections are later inserted back into InputSectionDescriptions.
1755 // We separate the creation of ThunkSections from the insertion of the
1756 // ThunkSections as ThunkSections are not always inserted into the same
1757 // InputSectionDescription as the caller.
1758 forEachInputSectionDescription(
1759 outputSections, [&](OutputSection *os, InputSectionDescription *isd) {
1760 for (InputSection *isec : isd->sections)
1761 for (Relocation &rel : isec->relocations) {
1762 uint64_t src = isec->getVA(rel.offset);
1764 // If we are a relocation to an existing Thunk, check if it is
1765 // still in range. If not then Rel will be altered to point to its
1766 // original target so another Thunk can be generated.
1767 if (pass > 0 && normalizeExistingThunk(rel, src))
1770 if (!target->needsThunk(rel.expr, rel.type, isec->file, src,
1776 std::tie(t, isNew) = getThunk(isec, rel, src);
1779 // Find or create a ThunkSection for the new Thunk
1781 if (auto *tis = t->getTargetInputSection())
1782 ts = getISThunkSec(tis);
1784 ts = getISDThunkSec(os, isec, isd, rel.type, src);
1786 thunks[t->getThunkTargetSym()] = t;
1789 // Redirect relocation to Thunk, we never go via the PLT to a Thunk
1790 rel.sym = t->getThunkTargetSym();
1791 rel.expr = fromPlt(rel.expr);
1793 // The addend of R_PPC_PLTREL24 should be ignored after changing to
1795 if (config->emachine == EM_PPC && rel.type == R_PPC_PLTREL24)
1799 for (auto &p : isd->thunkSections)
1800 addressesChanged |= p.first->assignOffsets();
1803 for (auto &p : thunkedSections)
1804 addressesChanged |= p.second->assignOffsets();
1806 // Merge all created synthetic ThunkSections back into OutputSection
1807 mergeThunks(outputSections);
1809 return addressesChanged;
1812 template void elf::scanRelocations<ELF32LE>(InputSectionBase &);
1813 template void elf::scanRelocations<ELF32BE>(InputSectionBase &);
1814 template void elf::scanRelocations<ELF64LE>(InputSectionBase &);
1815 template void elf::scanRelocations<ELF64BE>(InputSectionBase &);
1816 template void elf::reportUndefinedSymbols<ELF32LE>();
1817 template void elf::reportUndefinedSymbols<ELF32BE>();
1818 template void elf::reportUndefinedSymbols<ELF64LE>();
1819 template void elf::reportUndefinedSymbols<ELF64BE>();