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 implements the core relocation processing logic. It analyzes
10// relocations and determines what auxiliary data structures (GOT, PLT, copy
11// relocations) need to be created during linking.
12//
13// The main entry point is scanRelocations(), which calls scanSection() to
14// process all relocations within an input section. For each relocation,
15// scanSection() analyzes the type and target, and determines whether a
16// synthetic section entry or dynamic relocation is needed.
17//
18// Note: This file analyzes what needs to be done but doesn't apply the
19// actual relocations - that happens later in InputSection::writeTo().
20// Instead, it populates Relocation objects in InputSectionBase::relocations
21// and creates necessary synthetic sections (GOT, PLT, etc.).
22//
23// In addition, this file implements the core Thunk creation logic, called
24// during finalizeAddressDependentContent().
25//
26//===----------------------------------------------------------------------===//
27
28#include "Relocations.h"
29#include "Config.h"
30#include "InputFiles.h"
31#include "LinkerScript.h"
32#include "OutputSections.h"
33#include "RelocScan.h"
34#include "SymbolTable.h"
35#include "Symbols.h"
36#include "SyntheticSections.h"
37#include "Target.h"
38#include "Thunks.h"
39#include "lld/Common/ErrorHandler.h"
40#include "lld/Common/Memory.h"
41#include "lld/Common/Parallel.h"
42#include "llvm/ADT/SmallSet.h"
43#include "llvm/BinaryFormat/ELF.h"
44#include "llvm/Demangle/Demangle.h"
45#include "llvm/Support/Parallel.h"
46#include <algorithm>
47
48using namespace llvm;
49using namespace llvm::ELF;
50using namespace llvm::object;
51using namespace llvm::support::endian;
52using namespace lld;
53using namespace lld::elf;
54
55static void printDefinedLocation(ELFSyncStream &s, const Symbol &sym) {
56 s << "\n>>> defined in " << sym.file;
57}
58
59// Construct a message in the following format.
60//
61// >>> defined in /home/alice/src/foo.o
62// >>> referenced by bar.c:12 (/home/alice/src/bar.c:12)
63// >>> /home/alice/src/bar.o:(.text+0x1)
64void elf::printLocation(ELFSyncStream &s, InputSectionBase &sec,
65 const Symbol &sym, uint64_t off) {
66 printDefinedLocation(s, sym);
67 s << "\n>>> referenced by ";
68 auto tell = s.tell();
69 s << sec.getSrcMsg(sym, offset: off);
70 if (tell != s.tell())
71 s << "\n>>> ";
72 s << sec.getObjMsg(offset: off);
73}
74
75void elf::reportRangeError(Ctx &ctx, uint8_t *loc, const Relocation &rel,
76 const Twine &v, int64_t min, uint64_t max) {
77 ErrorPlace errPlace = getErrorPlace(ctx, loc);
78 auto diag = Err(ctx);
79 diag << errPlace.loc << "relocation " << rel.type
80 << " out of range: " << v.str() << " is not in [" << min << ", " << max
81 << ']';
82
83 if (rel.sym) {
84 if (!rel.sym->isSection())
85 diag << "; references '" << rel.sym << '\'';
86 else if (auto *d = dyn_cast<Defined>(Val: rel.sym))
87 diag << "; references section '" << d->section->name << "'";
88
89 if (ctx.arg.emachine == EM_X86_64 && rel.type == R_X86_64_PC32 &&
90 rel.sym->getOutputSection() &&
91 (rel.sym->getOutputSection()->flags & SHF_X86_64_LARGE)) {
92 diag << "; R_X86_64_PC32 should not reference a section marked "
93 "SHF_X86_64_LARGE";
94 }
95 }
96 if (!errPlace.srcLoc.empty())
97 diag << "\n>>> referenced by " << errPlace.srcLoc;
98 if (rel.sym && !rel.sym->isSection())
99 printDefinedLocation(s&: diag, sym: *rel.sym);
100
101 if (errPlace.isec && errPlace.isec->name.starts_with(Prefix: ".debug"))
102 diag << "; consider recompiling with -fdebug-types-section to reduce size "
103 "of debug sections";
104}
105
106void elf::reportRangeError(Ctx &ctx, uint8_t *loc, int64_t v, int n,
107 const Symbol &sym, const Twine &msg) {
108 auto diag = Err(ctx);
109 diag << getErrorPlace(ctx, loc).loc << msg << " is out of range: " << v
110 << " is not in [" << llvm::minIntN(N: n) << ", " << llvm::maxIntN(N: n) << "]";
111 if (!sym.getName().empty()) {
112 diag << "; references '" << &sym << '\'';
113 printDefinedLocation(s&: diag, sym);
114 }
115}
116
117// True if non-preemptable symbol always has the same value regardless of where
118// the DSO is loaded.
119bool elf::isAbsolute(const Symbol &sym) {
120 if (sym.isUndefined())
121 return true;
122 if (const auto *dr = dyn_cast<Defined>(Val: &sym))
123 return dr->section == nullptr; // Absolute symbol.
124 return false;
125}
126
127static bool isAbsoluteOrTls(const Symbol &sym) {
128 return isAbsolute(sym) || sym.isTls();
129}
130
131// Returns true if Expr refers a PLT entry.
132static bool needsPlt(RelExpr expr) {
133 return oneof<R_PLT, R_PLT_PC, R_PLT_GOTREL, R_PLT_GOTPLT, R_GOTPLT_GOTREL,
134 R_GOTPLT_PC, RE_LOONGARCH_PLT_PAGE_PC, RE_PPC32_PLTREL,
135 RE_PPC64_CALL_PLT>(expr);
136}
137
138bool lld::elf::needsGot(RelExpr expr) {
139 return oneof<R_GOT, R_GOT_OFF, RE_MIPS_GOT_LOCAL_PAGE, RE_MIPS_GOT_OFF,
140 RE_MIPS_GOT_OFF32, RE_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTPLT,
141 RE_AARCH64_GOT_PAGE, RE_LOONGARCH_GOT, RE_LOONGARCH_GOT_PAGE_PC>(
142 expr);
143}
144
145// True if this expression is of the form Sym - X, where X is a position in the
146// file (PC, or GOT for example).
147static bool isRelExpr(RelExpr expr) {
148 return oneof<R_PC, R_GOTREL, R_GOTPLTREL, RE_ARM_PCA, RE_MIPS_GOTREL,
149 RE_PPC64_CALL, RE_AARCH64_PAGE_PC, R_RELAX_GOT_PC,
150 RE_RISCV_PC_INDIRECT, RE_LOONGARCH_PAGE_PC,
151 RE_LOONGARCH_PC_INDIRECT>(expr);
152}
153
154// True if a reference to a non-absolute symbol is independent of the load base
155// of the ELF file.
156static bool isLoadBaseIndependent(Ctx &ctx, RelExpr expr, RelType type) {
157 return oneof<R_SIZE, RE_RISCV_LEB128>(expr) || isRelExpr(expr) ||
158 ctx.target->usesOnlyLowPageBits(type);
159}
160
161static RelExpr toPlt(RelExpr expr) {
162 switch (expr) {
163 case RE_LOONGARCH_PAGE_PC:
164 return RE_LOONGARCH_PLT_PAGE_PC;
165 case RE_PPC64_CALL:
166 return RE_PPC64_CALL_PLT;
167 case R_PC:
168 return R_PLT_PC;
169 case R_ABS:
170 return R_PLT;
171 case R_GOTREL:
172 return R_PLT_GOTREL;
173 default:
174 return expr;
175 }
176}
177
178static RelExpr fromPlt(RelExpr expr) {
179 // We decided not to use a plt. Optimize a reference to the plt to a
180 // reference to the symbol itself.
181 switch (expr) {
182 case R_PLT_PC:
183 case RE_PPC32_PLTREL:
184 return R_PC;
185 case RE_LOONGARCH_PLT_PAGE_PC:
186 return RE_LOONGARCH_PAGE_PC;
187 case RE_PPC64_CALL_PLT:
188 return RE_PPC64_CALL;
189 case R_PLT:
190 return R_ABS;
191 case R_PLT_GOTPLT:
192 return R_GOTPLTREL;
193 case R_PLT_GOTREL:
194 return R_GOTREL;
195 default:
196 return expr;
197 }
198}
199
200// Returns true if a given shared symbol is in a read-only segment in a DSO.
201template <class ELFT> static bool isReadOnly(SharedSymbol &ss) {
202 using Elf_Phdr = typename ELFT::Phdr;
203
204 // Determine if the symbol is read-only by scanning the DSO's program headers.
205 const auto &file = cast<SharedFile>(Val&: *ss.file);
206 for (const Elf_Phdr &phdr :
207 check(file.template getObj<ELFT>().program_headers()))
208 if ((phdr.p_type == ELF::PT_LOAD || phdr.p_type == ELF::PT_GNU_RELRO) &&
209 !(phdr.p_flags & ELF::PF_W) && ss.value >= phdr.p_vaddr &&
210 ss.value < phdr.p_vaddr + phdr.p_memsz)
211 return true;
212 return false;
213}
214
215// Returns symbols at the same offset as a given symbol, including SS itself.
216//
217// If two or more symbols are at the same offset, and at least one of
218// them are copied by a copy relocation, all of them need to be copied.
219// Otherwise, they would refer to different places at runtime.
220template <class ELFT>
221static SmallPtrSet<SharedSymbol *, 4> getSymbolsAt(Ctx &ctx, SharedSymbol &ss) {
222 using Elf_Sym = typename ELFT::Sym;
223
224 const auto &file = cast<SharedFile>(Val&: *ss.file);
225
226 SmallPtrSet<SharedSymbol *, 4> ret;
227 for (const Elf_Sym &s : file.template getGlobalELFSyms<ELFT>()) {
228 if (s.st_shndx == SHN_UNDEF || s.st_shndx == SHN_ABS ||
229 s.getType() == STT_TLS || s.st_value != ss.value)
230 continue;
231 StringRef name = check(s.getName(file.getStringTable()));
232 Symbol *sym = ctx.symtab->find(name);
233 if (auto *alias = dyn_cast_or_null<SharedSymbol>(Val: sym))
234 ret.insert(Ptr: alias);
235 }
236
237 // The loop does not check SHT_GNU_verneed, so ret does not contain
238 // non-default version symbols. If ss has a non-default version, ret won't
239 // contain ss. Just add ss unconditionally. If a non-default version alias is
240 // separately copy relocated, it and ss will have different addresses.
241 // Fortunately this case is impractical and fails with GNU ld as well.
242 ret.insert(Ptr: &ss);
243 return ret;
244}
245
246// When a symbol is copy relocated or we create a canonical plt entry, it is
247// effectively a defined symbol. In the case of copy relocation the symbol is
248// in .bss and in the case of a canonical plt entry it is in .plt. This function
249// replaces the existing symbol with a Defined pointing to the appropriate
250// location.
251static void replaceWithDefined(Ctx &ctx, Symbol &sym, SectionBase &sec,
252 uint64_t value, uint64_t size) {
253 uint16_t versionId = sym.versionId;
254 Defined(sym.file, StringRef(), sym.binding, sym.stOther, sym.type, value,
255 size, &sec)
256 .overwrite(sym);
257
258 sym.versionId = versionId;
259 sym.isUsedInRegularObj = true;
260 // A copy relocated alias may need a GOT entry.
261 sym.flags.fetch_and(i: NEEDS_GOT | NEEDS_GOT_AUTH, m: std::memory_order_relaxed);
262}
263
264// Reserve space in .bss or .bss.rel.ro for copy relocation.
265//
266// The copy relocation is pretty much a hack. If you use a copy relocation
267// in your program, not only the symbol name but the symbol's size, RW/RO
268// bit and alignment become part of the ABI. In addition to that, if the
269// symbol has aliases, the aliases become part of the ABI. That's subtle,
270// but if you violate that implicit ABI, that can cause very counter-
271// intuitive consequences.
272//
273// So, what is the copy relocation? It's for linking non-position
274// independent code to DSOs. In an ideal world, all references to data
275// exported by DSOs should go indirectly through GOT. But if object files
276// are compiled as non-PIC, all data references are direct. There is no
277// way for the linker to transform the code to use GOT, as machine
278// instructions are already set in stone in object files. This is where
279// the copy relocation takes a role.
280//
281// A copy relocation instructs the dynamic linker to copy data from a DSO
282// to a specified address (which is usually in .bss) at load-time. If the
283// static linker (that's us) finds a direct data reference to a DSO
284// symbol, it creates a copy relocation, so that the symbol can be
285// resolved as if it were in .bss rather than in a DSO.
286//
287// As you can see in this function, we create a copy relocation for the
288// dynamic linker, and the relocation contains not only symbol name but
289// various other information about the symbol. So, such attributes become a
290// part of the ABI.
291//
292// Note for application developers: I can give you a piece of advice if
293// you are writing a shared library. You probably should export only
294// functions from your library. You shouldn't export variables.
295//
296// As an example what can happen when you export variables without knowing
297// the semantics of copy relocations, assume that you have an exported
298// variable of type T. It is an ABI-breaking change to add new members at
299// end of T even though doing that doesn't change the layout of the
300// existing members. That's because the space for the new members are not
301// reserved in .bss unless you recompile the main program. That means they
302// are likely to overlap with other data that happens to be laid out next
303// to the variable in .bss. This kind of issue is sometimes very hard to
304// debug. What's a solution? Instead of exporting a variable V from a DSO,
305// define an accessor getV().
306template <class ELFT> static void addCopyRelSymbol(Ctx &ctx, SharedSymbol &ss) {
307 // Copy relocation against zero-sized symbol doesn't make sense.
308 uint64_t symSize = ss.getSize();
309 if (symSize == 0 || ss.alignment == 0)
310 Err(ctx) << "cannot create a copy relocation for symbol " << &ss;
311
312 // See if this symbol is in a read-only segment. If so, preserve the symbol's
313 // memory protection by reserving space in the .bss.rel.ro section.
314 bool isRO = isReadOnly<ELFT>(ss);
315 BssSection *sec = make<BssSection>(args&: ctx, args: isRO ? ".bss.rel.ro" : ".bss",
316 args&: symSize, args&: ss.alignment);
317 OutputSection *osec = (isRO ? ctx.in.bssRelRo : ctx.in.bss)->getParent();
318
319 // At this point, sectionBases has been migrated to sections. Append sec to
320 // sections.
321 if (osec->commands.empty() ||
322 !isa<InputSectionDescription>(Val: osec->commands.back()))
323 osec->commands.push_back(Elt: make<InputSectionDescription>(args: ""));
324 auto *isd = cast<InputSectionDescription>(Val: osec->commands.back());
325 isd->sections.push_back(Elt: sec);
326 osec->commitSection(isec: sec);
327
328 // Look through the DSO's dynamic symbol table for aliases and create a
329 // dynamic symbol for each one. This causes the copy relocation to correctly
330 // interpose any aliases.
331 for (SharedSymbol *sym : getSymbolsAt<ELFT>(ctx, ss))
332 replaceWithDefined(ctx, sym&: *sym, sec&: *sec, value: 0, size: sym->size);
333
334 ctx.in.relaDyn->addSymbolReloc(dynType: ctx.target->copyRel, isec&: *sec, offsetInSec: 0, sym&: ss);
335}
336
337// .eh_frame sections are mergeable input sections, so their input
338// offsets are not linearly mapped to output section. For each input
339// offset, we need to find a section piece containing the offset and
340// add the piece's base address to the input offset to compute the
341// output offset. That isn't cheap.
342//
343// This class is to speed up the offset computation. When we process
344// relocations, we access offsets in the monotonically increasing
345// order. So we can optimize for that access pattern.
346//
347// For sections other than .eh_frame, this class doesn't do anything.
348namespace {
349class OffsetGetter {
350public:
351 OffsetGetter() = default;
352 explicit OffsetGetter(EhInputSection &sec) {
353 cies = sec.cies;
354 fdes = sec.fdes;
355 i = cies.begin();
356 j = fdes.begin();
357 }
358
359 // Translates offsets in input sections to offsets in output sections.
360 // Given offset must increase monotonically. We assume that Piece is
361 // sorted by inputOff.
362 uint64_t get(Ctx &ctx, uint64_t off) {
363 while (j != fdes.end() && j->inputOff <= off)
364 ++j;
365 auto it = j;
366 if (j == fdes.begin() || j[-1].inputOff + j[-1].size <= off) {
367 while (i != cies.end() && i->inputOff <= off)
368 ++i;
369 if (i == cies.begin() || i[-1].inputOff + i[-1].size <= off) {
370 Err(ctx) << ".eh_frame: relocation is not in any piece";
371 return -1;
372 }
373 it = i;
374 }
375
376 // Offset -1 means that the piece is dead (i.e. garbage collected).
377 if (it[-1].outputOff == -1)
378 return -1;
379 return it[-1].outputOff + (off - it[-1].inputOff);
380 }
381
382private:
383 ArrayRef<EhSectionPiece> cies, fdes;
384 ArrayRef<EhSectionPiece>::iterator i, j;
385};
386} // namespace
387
388// Custom error message if Sym is defined in a discarded section.
389template <class ELFT>
390static void maybeReportDiscarded(Ctx &ctx, ELFSyncStream &msg, Undefined &sym) {
391 auto *file = dyn_cast<ObjFile<ELFT>>(sym.file);
392 if (!file || !sym.discardedSecIdx)
393 return;
394 ArrayRef<typename ELFT::Shdr> objSections =
395 file->template getELFShdrs<ELFT>();
396
397 if (sym.type == ELF::STT_SECTION) {
398 msg << "relocation refers to a discarded section: ";
399 msg << CHECK2(
400 file->getObj().getSectionName(objSections[sym.discardedSecIdx]), file);
401 } else {
402 msg << "relocation refers to a symbol in a discarded section: " << &sym;
403 }
404 msg << "\n>>> defined in " << file;
405
406 Elf_Shdr_Impl<ELFT> elfSec = objSections[sym.discardedSecIdx - 1];
407 if (elfSec.sh_type != SHT_GROUP)
408 return;
409
410 // If the discarded section is a COMDAT.
411 StringRef signature = file->getShtGroupSignature(objSections, elfSec);
412 if (const InputFile *prevailing =
413 ctx.symtab->comdatGroups.lookup(Val: CachedHashStringRef(signature))) {
414 msg << "\n>>> section group signature: " << signature
415 << "\n>>> prevailing definition is in " << prevailing;
416 if (sym.nonPrevailing) {
417 msg << "\n>>> or the symbol in the prevailing group had STB_WEAK "
418 "binding and the symbol in a non-prevailing group had STB_GLOBAL "
419 "binding. Mixing groups with STB_WEAK and STB_GLOBAL binding "
420 "signature is not supported";
421 }
422 }
423}
424
425// Check whether the definition name def is a mangled function name that matches
426// the reference name ref.
427static bool canSuggestExternCForCXX(StringRef ref, StringRef def) {
428 llvm::ItaniumPartialDemangler d;
429 std::string name = def.str();
430 if (d.partialDemangle(MangledName: name.c_str()))
431 return false;
432 char *buf = d.getFunctionName(Buf: nullptr, N: nullptr);
433 if (!buf)
434 return false;
435 bool ret = ref == buf;
436 free(ptr: buf);
437 return ret;
438}
439
440// Suggest an alternative spelling of an "undefined symbol" diagnostic. Returns
441// the suggested symbol, which is either in the symbol table, or in the same
442// file of sym.
443static const Symbol *getAlternativeSpelling(Ctx &ctx, const Undefined &sym,
444 std::string &pre_hint,
445 std::string &post_hint) {
446 DenseMap<StringRef, const Symbol *> map;
447 if (sym.file->kind() == InputFile::ObjKind) {
448 auto *file = cast<ELFFileBase>(Val: sym.file);
449 // If sym is a symbol defined in a discarded section, maybeReportDiscarded()
450 // will give an error. Don't suggest an alternative spelling.
451 if (sym.discardedSecIdx != 0 &&
452 file->getSections()[sym.discardedSecIdx] == &InputSection::discarded)
453 return nullptr;
454
455 // Build a map of local defined symbols.
456 for (const Symbol *s : sym.file->getSymbols())
457 if (s->isLocal() && s->isDefined() && !s->getName().empty())
458 map.try_emplace(Key: s->getName(), Args&: s);
459 }
460
461 auto suggest = [&](StringRef newName) -> const Symbol * {
462 // If defined locally.
463 if (const Symbol *s = map.lookup(Val: newName))
464 return s;
465
466 // If in the symbol table and not undefined.
467 if (const Symbol *s = ctx.symtab->find(name: newName))
468 if (!s->isUndefined())
469 return s;
470
471 return nullptr;
472 };
473
474 // This loop enumerates all strings of Levenshtein distance 1 as typo
475 // correction candidates and suggests the one that exists as a non-undefined
476 // symbol.
477 StringRef name = sym.getName();
478 for (size_t i = 0, e = name.size(); i != e + 1; ++i) {
479 // Insert a character before name[i].
480 std::string newName = (name.substr(Start: 0, N: i) + "0" + name.substr(Start: i)).str();
481 for (char c = '0'; c <= 'z'; ++c) {
482 newName[i] = c;
483 if (const Symbol *s = suggest(newName))
484 return s;
485 }
486 if (i == e)
487 break;
488
489 // Substitute name[i].
490 newName = std::string(name);
491 for (char c = '0'; c <= 'z'; ++c) {
492 newName[i] = c;
493 if (const Symbol *s = suggest(newName))
494 return s;
495 }
496
497 // Transpose name[i] and name[i+1]. This is of edit distance 2 but it is
498 // common.
499 if (i + 1 < e) {
500 newName[i] = name[i + 1];
501 newName[i + 1] = name[i];
502 if (const Symbol *s = suggest(newName))
503 return s;
504 }
505
506 // Delete name[i].
507 newName = (name.substr(Start: 0, N: i) + name.substr(Start: i + 1)).str();
508 if (const Symbol *s = suggest(newName))
509 return s;
510 }
511
512 // Case mismatch, e.g. Foo vs FOO.
513 for (auto &it : map)
514 if (name.equals_insensitive(RHS: it.first))
515 return it.second;
516 for (Symbol *sym : ctx.symtab->getSymbols())
517 if (!sym->isUndefined() && name.equals_insensitive(RHS: sym->getName()))
518 return sym;
519
520 // The reference may be a mangled name while the definition is not. Suggest a
521 // missing extern "C".
522 if (name.starts_with(Prefix: "_Z")) {
523 std::string buf = name.str();
524 llvm::ItaniumPartialDemangler d;
525 if (!d.partialDemangle(MangledName: buf.c_str()))
526 if (char *buf = d.getFunctionName(Buf: nullptr, N: nullptr)) {
527 const Symbol *s = suggest(buf);
528 free(ptr: buf);
529 if (s) {
530 pre_hint = ": extern \"C\" ";
531 return s;
532 }
533 }
534 } else {
535 const Symbol *s = nullptr;
536 for (auto &it : map)
537 if (canSuggestExternCForCXX(ref: name, def: it.first)) {
538 s = it.second;
539 break;
540 }
541 if (!s)
542 for (Symbol *sym : ctx.symtab->getSymbols())
543 if (canSuggestExternCForCXX(ref: name, def: sym->getName())) {
544 s = sym;
545 break;
546 }
547 if (s) {
548 pre_hint = " to declare ";
549 post_hint = " as extern \"C\"?";
550 return s;
551 }
552 }
553
554 return nullptr;
555}
556
557static void reportUndefinedSymbol(Ctx &ctx, const UndefinedDiag &undef,
558 bool correctSpelling) {
559 Undefined &sym = *undef.sym;
560 ELFSyncStream msg(ctx, DiagLevel::None);
561
562 auto visibility = [&]() {
563 switch (sym.visibility()) {
564 case STV_INTERNAL:
565 return "internal ";
566 case STV_HIDDEN:
567 return "hidden ";
568 case STV_PROTECTED:
569 return "protected ";
570 default:
571 return "";
572 }
573 };
574
575 switch (ctx.arg.ekind) {
576 case ELF32LEKind:
577 maybeReportDiscarded<ELF32LE>(ctx, msg, sym);
578 break;
579 case ELF32BEKind:
580 maybeReportDiscarded<ELF32BE>(ctx, msg, sym);
581 break;
582 case ELF64LEKind:
583 maybeReportDiscarded<ELF64LE>(ctx, msg, sym);
584 break;
585 case ELF64BEKind:
586 maybeReportDiscarded<ELF64BE>(ctx, msg, sym);
587 break;
588 default:
589 llvm_unreachable("");
590 }
591 if (msg.str().empty())
592 msg << "undefined " << visibility() << "symbol: " << &sym;
593
594 const size_t maxUndefReferences = 3;
595 for (UndefinedDiag::Loc l :
596 ArrayRef(undef.locs).take_front(N: maxUndefReferences)) {
597 InputSectionBase &sec = *l.sec;
598 uint64_t offset = l.offset;
599
600 msg << "\n>>> referenced by ";
601 // In the absence of line number information, utilize DW_TAG_variable (if
602 // present) for the enclosing symbol (e.g. var in `int *a[] = {&undef};`).
603 Symbol *enclosing = sec.getEnclosingSymbol(offset);
604
605 ELFSyncStream msg1(ctx, DiagLevel::None);
606 auto tell = msg.tell();
607 msg << sec.getSrcMsg(sym: enclosing ? *enclosing : sym, offset);
608 if (tell != msg.tell())
609 msg << "\n>>> ";
610 msg << sec.getObjMsg(offset);
611 }
612
613 if (maxUndefReferences < undef.locs.size())
614 msg << "\n>>> referenced " << (undef.locs.size() - maxUndefReferences)
615 << " more times";
616
617 if (correctSpelling) {
618 std::string pre_hint = ": ", post_hint;
619 if (const Symbol *corrected =
620 getAlternativeSpelling(ctx, sym, pre_hint, post_hint)) {
621 msg << "\n>>> did you mean" << pre_hint << corrected << post_hint
622 << "\n>>> defined in: " << corrected->file;
623 }
624 }
625
626 if (sym.getName().starts_with(Prefix: "_ZTV"))
627 msg << "\n>>> the vtable symbol may be undefined because the class is "
628 "missing its key function "
629 "(see https://lld.llvm.org/missingkeyfunction)";
630 if (ctx.arg.gcSections && ctx.arg.zStartStopGC &&
631 sym.getName().starts_with(Prefix: "__start_")) {
632 msg << "\n>>> the encapsulation symbol needs to be retained under "
633 "--gc-sections properly; consider -z nostart-stop-gc "
634 "(see https://lld.llvm.org/ELF/start-stop-gc)";
635 }
636
637 if (undef.isWarning)
638 Warn(ctx) << msg.str();
639 else
640 ctx.e.error(msg: msg.str(), tag: ErrorTag::SymbolNotFound, args: {sym.getName()});
641}
642
643void elf::reportUndefinedSymbols(Ctx &ctx) {
644 // Find the first "undefined symbol" diagnostic for each diagnostic, and
645 // collect all "referenced from" lines at the first diagnostic.
646 DenseMap<Symbol *, UndefinedDiag *> firstRef;
647 for (UndefinedDiag &undef : ctx.undefErrs) {
648 assert(undef.locs.size() == 1);
649 if (UndefinedDiag *canon = firstRef.lookup(Val: undef.sym)) {
650 canon->locs.push_back(Elt: undef.locs[0]);
651 undef.locs.clear();
652 } else
653 firstRef[undef.sym] = &undef;
654 }
655
656 // Enable spell corrector for the first 2 diagnostics.
657 for (auto [i, undef] : llvm::enumerate(First&: ctx.undefErrs))
658 if (!undef.locs.empty())
659 reportUndefinedSymbol(ctx, undef, correctSpelling: i < 2);
660}
661
662// Report an undefined symbol if necessary.
663// Returns true if the undefined symbol will produce an error message.
664bool elf::maybeReportUndefined(Ctx &ctx, Undefined &sym, InputSectionBase &sec,
665 uint64_t offset) {
666 // If versioned, issue an error (even if the symbol is weak) because we don't
667 // know the defining filename which is required to construct a Verneed entry.
668 if (sym.hasVersionSuffix) {
669 ctx.undefErrs.push_back(Elt: {.sym: &sym, .locs: {{.sec: &sec, .offset: offset}}, .isWarning: false});
670 return true;
671 }
672 if (sym.isWeak())
673 return false;
674
675 bool canBeExternal = !sym.isLocal() && sym.visibility() == STV_DEFAULT;
676 if (ctx.arg.unresolvedSymbols == UnresolvedPolicy::Ignore && canBeExternal)
677 return false;
678
679 // clang (as of 2019-06-12) / gcc (as of 8.2.1) PPC64 may emit a .rela.toc
680 // which references a switch table in a discarded .rodata/.text section. The
681 // .toc and the .rela.toc are incorrectly not placed in the comdat. The ELF
682 // spec says references from outside the group to a STB_LOCAL symbol are not
683 // allowed. Work around the bug.
684 //
685 // PPC32 .got2 is similar but cannot be fixed. Multiple .got2 is infeasible
686 // because .LC0-.LTOC is not representable if the two labels are in different
687 // .got2
688 if (sym.discardedSecIdx != 0 && (sec.name == ".got2" || sec.name == ".toc"))
689 return false;
690
691 bool isWarning =
692 (ctx.arg.unresolvedSymbols == UnresolvedPolicy::Warn && canBeExternal) ||
693 ctx.arg.noinhibitExec;
694 ctx.undefErrs.push_back(Elt: {.sym: &sym, .locs: {{.sec: &sec, .offset: offset}}, .isWarning: isWarning});
695 return !isWarning;
696}
697
698bool RelocScan::maybeReportUndefined(Undefined &sym, uint64_t offset) {
699 std::lock_guard<std::mutex> lock(ctx.relocMutex);
700 return elf::maybeReportUndefined(ctx, sym, sec&: *sec, offset);
701}
702
703bool RelocScan::checkTlsLe(uint64_t offset, Symbol &sym, RelType type) {
704 if (!ctx.arg.shared)
705 return false;
706 auto diag = Err(ctx);
707 diag << "relocation " << type << " against " << &sym
708 << " cannot be used with -shared";
709 printLocation(s&: diag, sec&: *sec, sym, off: offset);
710 return true;
711}
712
713template <bool concurrent = false>
714static void addRelativeReloc(Ctx &ctx, InputSectionBase &isec,
715 uint64_t offsetInSec, Symbol &sym, int64_t addend,
716 RelExpr expr, RelType type, unsigned shard = 0) {
717 bool isAArch64Auth =
718 ctx.arg.emachine == EM_AARCH64 && type == R_AARCH64_AUTH_ABS64;
719
720 // Add a relative relocation. If relrDyn section is enabled, and the
721 // relocation offset is guaranteed to be even, add the relocation to
722 // the relrDyn section, otherwise add it to the relaDyn section.
723 // relrDyn sections don't support odd offsets. Also, relrDyn sections
724 // don't store the addend values, so we must write it to the relocated
725 // address.
726 //
727 // When symbol values are determined in finalizeAddressDependentContent,
728 // some .relr.auth.dyn relocations may be moved to .rela.dyn.
729 //
730 // MTE globals may need to store the original addend as well so cannot use
731 // relrDyn. TODO: It should be unambiguous when not using R_ADDEND_NEG below?
732 RelrBaseSection *relrDyn = ctx.in.relrDyn.get();
733 if (isAArch64Auth)
734 relrDyn = ctx.in.relrAuthDyn.get();
735 if (sym.isTagged())
736 relrDyn = nullptr;
737 if (relrDyn && isec.addralign >= 2 && offsetInSec % 2 == 0) {
738 relrDyn->addRelativeReloc<concurrent>(isec, offsetInSec, sym, addend, type,
739 expr, shard);
740 return;
741 }
742 RelType relativeType = ctx.target->relativeRel;
743 if (isAArch64Auth)
744 relativeType = R_AARCH64_AUTH_RELATIVE;
745 ctx.in.relaDyn->addRelativeReloc<concurrent>(relativeType, isec, offsetInSec,
746 sym, addend, type, expr, shard);
747 // With MTE globals, we always want to derive the address tag by `ldg`-ing
748 // the symbol. When we have a RELATIVE relocation though, we no longer have
749 // a reference to the symbol. Because of this, when we have an addend that
750 // puts the result of the RELATIVE relocation out-of-bounds of the symbol
751 // (e.g. the addend is outside of [0, sym.getSize()]), the AArch64 MemtagABI
752 // says we should store the offset to the start of the symbol in the target
753 // field. This is described in further detail in:
754 // https://github.com/ARM-software/abi-aa/blob/main/memtagabielf64/memtagabielf64.rst#841extended-semantics-of-r_aarch64_relative
755 if (sym.isTagged() &&
756 (addend < 0 || static_cast<uint64_t>(addend) >= sym.getSize()))
757 isec.addReloc(r: {.expr: R_ADDEND_NEG, .type: type, .offset: offsetInSec, .addend: addend, .sym: &sym});
758}
759
760template <class PltSection, class GotPltSection>
761static void addPltEntry(Ctx &ctx, PltSection &plt, GotPltSection &gotPlt,
762 RelocationBaseSection &rel, RelType type, Symbol &sym) {
763 plt.addEntry(sym);
764 bool isPreemptible = sym.isPreemptible;
765 RelExpr expr = isPreemptible ? R_ADDEND : R_ABS;
766 if (!ctx.target->usesGotPlt) {
767 rel.addReloc(
768 {type, &plt, sym.getPltOffset(ctx), isPreemptible, sym, 0, expr});
769 return;
770 }
771 gotPlt.addEntry(sym);
772 if (sym.isPreemptible && ctx.arg.zMarkPlt && type == ctx.target->pltRel)
773 expr = R_PLT;
774 rel.addReloc(
775 {type, &gotPlt, sym.getGotPltOffset(ctx), isPreemptible, sym, 0, expr});
776}
777
778void elf::addGotEntry(Ctx &ctx, Symbol &sym) {
779 ctx.in.got->addEntry(sym);
780 uint64_t off = sym.getGotOffset(ctx);
781
782 // If preemptible, emit a GLOB_DAT relocation.
783 if (sym.isPreemptible) {
784 ctx.in.relaDyn->addReloc(
785 reloc: {ctx.target->gotRel, ctx.in.got.get(), off, true, sym, 0, R_ADDEND});
786 return;
787 }
788
789 // Otherwise, the value is either a link-time constant or the load base
790 // plus a constant.
791 if (!ctx.arg.isPic || isAbsolute(sym))
792 ctx.in.got->addConstant(r: {.expr: R_ABS, .type: ctx.target->symbolicRel, .offset: off, .addend: 0, .sym: &sym});
793 else
794 addRelativeReloc(ctx, isec&: *ctx.in.got, offsetInSec: off, sym, addend: 0, expr: R_ABS,
795 type: ctx.target->symbolicRel);
796}
797
798static void addGotAuthEntry(Ctx &ctx, Symbol &sym) {
799 ctx.in.got->addEntry(sym);
800 ctx.in.got->addAuthEntry(sym);
801 uint64_t off = sym.getGotOffset(ctx);
802
803 // If preemptible, emit a GLOB_DAT relocation.
804 if (sym.isPreemptible) {
805 ctx.in.relaDyn->addReloc(reloc: {R_AARCH64_AUTH_GLOB_DAT, ctx.in.got.get(), off,
806 true, sym, 0, R_ADDEND});
807 return;
808 }
809
810 // Signed GOT requires dynamic relocation unless the symbol is
811 // non-preemptible and undefined.
812 if (!sym.isUndefined())
813 ctx.in.relaDyn->addReloc(
814 reloc: {R_AARCH64_AUTH_RELATIVE, ctx.in.got.get(), off, false, sym, 0, R_ABS});
815}
816
817static void addTpOffsetGotEntry(Ctx &ctx, Symbol &sym) {
818 ctx.in.got->addEntry(sym);
819 uint64_t off = sym.getGotOffset(ctx);
820 if (!sym.isPreemptible && !ctx.arg.shared) {
821 ctx.in.got->addConstant(r: {.expr: R_TPREL, .type: ctx.target->symbolicRel, .offset: off, .addend: 0, .sym: &sym});
822 return;
823 }
824 ctx.in.relaDyn->addAddendOnlyRelocIfNonPreemptible(
825 dynType: ctx.target->tlsGotRel, isec&: *ctx.in.got, offsetInSec: off, sym, addendRelType: ctx.target->symbolicRel);
826}
827
828// Return true if we can define a symbol in the executable that
829// contains the value/function of a symbol defined in a shared
830// library.
831static bool canDefineSymbolInExecutable(Ctx &ctx, Symbol &sym) {
832 // If the symbol has default visibility the symbol defined in the
833 // executable will preempt it.
834 // Note that we want the visibility of the shared symbol itself, not
835 // the visibility of the symbol in the output file we are producing.
836 if (!sym.dsoProtected)
837 return true;
838
839 // If we are allowed to break address equality of functions, defining
840 // a plt entry will allow the program to call the function in the
841 // .so, but the .so and the executable will no agree on the address
842 // of the function. Similar logic for objects.
843 return ((sym.isFunc() && ctx.arg.ignoreFunctionAddressEquality) ||
844 (sym.isObject() && ctx.arg.ignoreDataAddressEquality));
845}
846
847// Returns true if a given relocation can be computed at link-time.
848// This only handles relocation types expected in process().
849//
850// For instance, we know the offset from a relocation to its target at
851// link-time if the relocation is PC-relative and refers a
852// non-interposable function in the same executable. This function
853// will return true for such relocation.
854//
855// If this function returns false, that means we need to emit a
856// dynamic relocation so that the relocation will be fixed at load-time.
857bool RelocScan::isStaticLinkTimeConstant(RelExpr e, RelType type,
858 const Symbol &sym,
859 uint64_t relOff) const {
860 // These expressions always compute a constant
861 if (oneof<R_GOTPLT, R_GOT_OFF, R_RELAX_HINT, RE_MIPS_GOT_LOCAL_PAGE,
862 RE_MIPS_GOTREL, RE_MIPS_GOT_OFF, RE_MIPS_GOT_OFF32,
863 RE_MIPS_GOT_GP_PC, RE_AARCH64_GOT_PAGE_PC, R_GOT_PC, R_GOTONLY_PC,
864 R_GOTPLTONLY_PC, R_PLT_PC, R_PLT_GOTREL, R_PLT_GOTPLT,
865 R_GOTPLT_GOTREL, R_GOTPLT_PC, RE_PPC32_PLTREL, RE_PPC64_CALL_PLT,
866 RE_RISCV_ADD, RE_AARCH64_GOT_PAGE, RE_LOONGARCH_PLT_PAGE_PC,
867 RE_LOONGARCH_GOT, RE_LOONGARCH_GOT_PAGE_PC>(expr: e))
868 return true;
869
870 // These never do, except if the entire file is position dependent or if
871 // only the low bits are used.
872 if (e == R_GOT || e == R_PLT)
873 return ctx.target->usesOnlyLowPageBits(type) || !ctx.arg.isPic;
874 // R_AARCH64_AUTH_ABS64 requires a dynamic relocation unless the symbol is
875 // non-preemptible and undefined.
876 if (e == RE_AARCH64_AUTH && (!sym.isUndefined() || sym.isPreemptible))
877 return false;
878 // iRelSymbolicRel requires a dynamic relocation.
879 if (type == ctx.target->iRelSymbolicRel)
880 return false;
881
882 // The behavior of an undefined weak reference is implementation defined.
883 // (We treat undefined non-weak the same as undefined weak.) For static
884 // -no-pie linking, dynamic relocations are generally avoided (except
885 // IRELATIVE). Emitting dynamic relocations for -shared aligns with its -z
886 // undefs default. Dynamic -no-pie linking and -pie allow flexibility.
887 if (sym.isPreemptible)
888 return sym.isUndefined() && !ctx.arg.isPic;
889 if (!ctx.arg.isPic)
890 return true;
891
892 bool absVal = isAbsoluteOrTls(sym) && e != RE_PPC64_TOCBASE;
893 if (!absVal)
894 return isLoadBaseIndependent(ctx, expr: e, type);
895 if (oneof<R_SIZE, RE_RISCV_LEB128>(expr: e) || !isRelExpr(expr: e))
896 return true;
897
898 // Allow R_PLT_PC (optimized to R_PC here) to a hidden undefined weak symbol
899 // in PIC mode. This is a little strange, but it allows us to link function
900 // calls to such symbols (e.g. glibc/stdlib/exit.c:__run_exit_handlers).
901 // Normally such a call will be guarded with a comparison, which will load a
902 // zero from the GOT.
903 if (sym.isUndefined())
904 return true;
905
906 // We set the final symbols values for linker script defined symbols later.
907 // They always can be computed as a link time constant.
908 if (sym.scriptDefined)
909 return true;
910
911 auto diag = Err(ctx);
912 diag << "relocation " << type << " cannot refer to absolute symbol: " << &sym;
913 printLocation(s&: diag, sec&: *sec, sym, off: relOff);
914 return true;
915}
916
917// The reason we have to do this early scan is as follows
918// * To mmap the output file, we need to know the size
919// * For that, we need to know how many dynamic relocs we will have.
920// It might be possible to avoid this by outputting the file with write:
921// * Write the allocated output sections, computing addresses.
922// * Apply relocations, recording which ones require a dynamic reloc.
923// * Write the dynamic relocations.
924// * Write the rest of the file.
925// This would have some drawbacks. For example, we would only know if .rela.dyn
926// is needed after applying relocations. If it is, it will go after rw and rx
927// sections. Given that it is ro, we will need an extra PT_LOAD. This
928// complicates things for the dynamic linker and means we would have to reserve
929// space for the extra PT_LOAD even if we end up not using it.
930void RelocScan::process(RelExpr expr, RelType type, uint64_t offset,
931 Symbol &sym, int64_t addend) const {
932 // If non-ifunc non-preemptible, change PLT to direct call and optimize GOT
933 // indirection.
934 const bool isIfunc = sym.isGnuIFunc();
935 if (!sym.isPreemptible && !isIfunc) {
936 if (expr != R_GOT_PC) {
937 expr = fromPlt(expr);
938 } else if (!isAbsoluteOrTls(sym)) {
939 expr = ctx.target->adjustGotPcExpr(type, addend,
940 loc: sec->content().data() + offset);
941 // If the target adjusted the expression to an optimizable form, we may
942 // end up needing the GOT if we can't optimize everything.
943 if (expr == R_RELAX_GOT_PC || expr == R_RELAX_GOT_PC_NOPIC)
944 ctx.in.got->hasDeferredEntries.store(i: true, m: std::memory_order_relaxed);
945 }
946 }
947
948 // We were asked not to generate PLT entries for ifuncs. Instead, pass the
949 // direct relocation on through.
950 if (LLVM_UNLIKELY(isIfunc) && ctx.arg.zIfuncNoplt) {
951 std::lock_guard<std::mutex> lock(ctx.relocMutex);
952 sym.isExported = true;
953 ctx.in.relaDyn->addSymbolReloc(dynType: type, isec&: *sec, offsetInSec: offset, sym, addend, addendRelType: type);
954 return;
955 }
956
957 if (needsGot(expr)) {
958 if (ctx.arg.emachine == EM_MIPS) {
959 // MIPS ABI has special rules to process GOT entries and doesn't
960 // require relocation entries for them. A special case is TLS
961 // relocations. In that case dynamic loader applies dynamic
962 // relocations to initialize TLS GOT entries.
963 // See "Global Offset Table" in Chapter 5 in the following document
964 // for detailed description:
965 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
966 ctx.in.mipsGot->addEntry(file&: *sec->file, sym, addend, expr);
967 } else if (!sym.isTls() || ctx.arg.emachine != EM_LOONGARCH) {
968 // Many LoongArch TLS relocs reuse the RE_LOONGARCH_GOT type, in which
969 // case the NEEDS_GOT flag shouldn't get set.
970 sym.setFlags(NEEDS_GOT);
971 }
972 } else if (needsPlt(expr)) {
973 sym.setFlags(NEEDS_PLT);
974 } else if (LLVM_UNLIKELY(isIfunc)) {
975 sym.setFlags(HAS_DIRECT_RELOC);
976 }
977
978 processAux(expr, type, offset, sym, addend);
979}
980
981// Process relocation after needsGot/needsPlt flags are already handled.
982// This is the bottom half of process(), handling isStaticLinkTimeConstant
983// check, dynamic relocations, copy relocations, and error reporting.
984void RelocScan::processAux(RelExpr expr, RelType type, uint64_t offset,
985 Symbol &sym, int64_t addend) const {
986 const bool isIfunc = sym.isGnuIFunc();
987
988 // If the relocation is known to be a link-time constant, we know no dynamic
989 // relocation will be created, pass the control to relocateAlloc() or
990 // relocateNonAlloc() to resolve it.
991 if (isStaticLinkTimeConstant(e: expr, type, sym, relOff: offset)) {
992 sec->addReloc(r: {.expr: expr, .type: type, .offset: offset, .addend: addend, .sym: &sym});
993 return;
994 }
995
996 // Use a simple -z notext rule that treats all sections except .eh_frame as
997 // writable. GNU ld does not produce dynamic relocations in .eh_frame.
998 //
999 // For MIPS, we don't implement GNU ld's DW_EH_PE_absptr to DW_EH_PE_pcrel
1000 // conversion. We still emit a dynamic relocation.
1001 bool canWrite = (sec->flags & SHF_WRITE) ||
1002 !(ctx.arg.zText ||
1003 (isa<EhInputSection>(Val: sec) && ctx.arg.emachine != EM_MIPS));
1004 if (canWrite) {
1005 RelType rel = ctx.target->getDynRel(type);
1006 if (oneof<R_GOT, RE_LOONGARCH_GOT>(expr) ||
1007 ((rel == ctx.target->symbolicRel ||
1008 (ctx.arg.emachine == EM_AARCH64 && type == R_AARCH64_AUTH_ABS64)) &&
1009 !sym.isPreemptible)) {
1010 addRelativeReloc<true>(ctx, isec&: *sec, offsetInSec: offset, sym, addend, expr, type, shard);
1011 return;
1012 }
1013 if (rel != 0) {
1014 if (ctx.arg.emachine == EM_MIPS && rel == ctx.target->symbolicRel)
1015 rel = ctx.target->relativeRel;
1016 std::lock_guard<std::mutex> lock(ctx.relocMutex);
1017 if (LLVM_UNLIKELY(type == ctx.target->iRelSymbolicRel)) {
1018 if (sym.isPreemptible) {
1019 auto diag = Err(ctx);
1020 diag << "relocation " << type
1021 << " cannot be used against preemptible symbol '" << &sym << "'";
1022 printLocation(s&: diag, sec&: *sec, sym, off: offset);
1023 } else if (isIfunc) {
1024 auto diag = Err(ctx);
1025 diag << "relocation " << type
1026 << " cannot be used against ifunc symbol '" << &sym << "'";
1027 printLocation(s&: diag, sec&: *sec, sym, off: offset);
1028 } else {
1029 ctx.in.relaDyn->addReloc(reloc: {ctx.target->iRelativeRel, sec, offset,
1030 false, sym, addend, R_ABS});
1031 return;
1032 }
1033 }
1034 ctx.in.relaDyn->addSymbolReloc(dynType: rel, isec&: *sec, offsetInSec: offset, sym, addend, addendRelType: type);
1035
1036 // MIPS ABI turns using of GOT and dynamic relocations inside out.
1037 // While regular ABI uses dynamic relocations to fill up GOT entries
1038 // MIPS ABI requires dynamic linker to fills up GOT entries using
1039 // specially sorted dynamic symbol table. This affects even dynamic
1040 // relocations against symbols which do not require GOT entries
1041 // creation explicitly, i.e. do not have any GOT-relocations. So if
1042 // a preemptible symbol has a dynamic relocation we anyway have
1043 // to create a GOT entry for it.
1044 // If a non-preemptible symbol has a dynamic relocation against it,
1045 // dynamic linker takes it st_value, adds offset and writes down
1046 // result of the dynamic relocation. In case of preemptible symbol
1047 // dynamic linker performs symbol resolution, writes the symbol value
1048 // to the GOT entry and reads the GOT entry when it needs to perform
1049 // a dynamic relocation.
1050 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf p.4-19
1051 if (ctx.arg.emachine == EM_MIPS)
1052 ctx.in.mipsGot->addEntry(file&: *sec->file, sym, addend, expr);
1053 return;
1054 }
1055 }
1056
1057 // When producing an executable, we can perform copy relocations (for
1058 // STT_OBJECT) and canonical PLT (for STT_FUNC) if sym is defined by a DSO.
1059 // In a PIE, the reference must be independent of the load base.
1060 // Copy relocations/canonical PLT entries are unsupported for
1061 // R_AARCH64_AUTH_ABS64.
1062 if (!ctx.arg.shared && sym.isShared() &&
1063 (!ctx.arg.pie || isLoadBaseIndependent(ctx, expr, type)) &&
1064 !(ctx.arg.emachine == EM_AARCH64 && type == R_AARCH64_AUTH_ABS64)) {
1065 if (!canDefineSymbolInExecutable(ctx, sym)) {
1066 auto diag = Err(ctx);
1067 diag << "cannot preempt symbol: " << &sym;
1068 printLocation(s&: diag, sec&: *sec, sym, off: offset);
1069 return;
1070 }
1071
1072 if (sym.isObject()) {
1073 // Produce a copy relocation.
1074 if (auto *ss = dyn_cast<SharedSymbol>(Val: &sym)) {
1075 if (!ctx.arg.zCopyreloc) {
1076 auto diag = Err(ctx);
1077 diag << "unresolvable relocation " << type << " against symbol '"
1078 << ss << "'; recompile with -fPIC or remove '-z nocopyreloc'";
1079 printLocation(s&: diag, sec&: *sec, sym, off: offset);
1080 }
1081 sym.setFlags(NEEDS_COPY);
1082 }
1083 sec->addReloc(r: {.expr: expr, .type: type, .offset: offset, .addend: addend, .sym: &sym});
1084 return;
1085 }
1086
1087 // This handles a non PIC program call to function in a shared library. In
1088 // an ideal world, we could just report an error saying the relocation can
1089 // overflow at runtime. In the real world with glibc, crt1.o has a
1090 // R_X86_64_PC32 pointing to libc.so.
1091 //
1092 // The general idea on how to handle such cases is to create a PLT entry and
1093 // use that as the function value.
1094 //
1095 // For the static linking part, we just return a plt expr and everything
1096 // else will use the PLT entry as the address.
1097 //
1098 // The remaining problem is making sure pointer equality still works. We
1099 // need the help of the dynamic linker for that. We let it know that we have
1100 // a direct reference to a so symbol by creating an undefined symbol with a
1101 // non zero st_value. Seeing that, the dynamic linker resolves the symbol to
1102 // the value of the symbol we created. This is true even for got entries, so
1103 // pointer equality is maintained. To avoid an infinite loop, the only entry
1104 // that points to the real function is a dedicated got entry used by the
1105 // plt. That is identified by special relocation types (R_X86_64_JUMP_SLOT,
1106 // R_386_JMP_SLOT, etc).
1107
1108 // For position independent executable on i386, the plt entry requires ebx
1109 // to be set. This causes two problems:
1110 // * If some code has a direct reference to a function, it was probably
1111 // compiled without -fPIE/-fPIC and doesn't maintain ebx.
1112 // * If a library definition gets preempted to the executable, it will have
1113 // the wrong ebx value.
1114 if (sym.isFunc()) {
1115 if (ctx.arg.pie && ctx.arg.emachine == EM_386) {
1116 auto diag = Err(ctx);
1117 diag << "symbol '" << &sym
1118 << "' cannot be preempted; recompile with -fPIE";
1119 printLocation(s&: diag, sec&: *sec, sym, off: offset);
1120 }
1121 sym.setFlags(NEEDS_COPY | NEEDS_PLT);
1122 sec->addReloc(r: {.expr: expr, .type: type, .offset: offset, .addend: addend, .sym: &sym});
1123 return;
1124 }
1125 }
1126
1127 auto diag = Err(ctx);
1128 diag << "relocation " << type << " cannot be used against ";
1129 if (sym.getName().empty())
1130 diag << "local symbol";
1131 else
1132 diag << "symbol '" << &sym << "'";
1133 diag << "; recompile with -fPIC";
1134 printLocation(s&: diag, sec&: *sec, sym, off: offset);
1135}
1136
1137template <class RelTy>
1138void TargetInfo::scanSectionImpl(InputSectionBase &sec, Relocs<RelTy> rels,
1139 unsigned shard) {
1140 RelocScan rs(ctx, &sec, shard);
1141 // Many relocations end up in sec.relocations.
1142 sec.relocations.reserve(N: rels.size());
1143
1144 for (const RelTy &rel : rels) {
1145 RelType type = rel.getType(false);
1146 uint32_t symIdx = rel.getSymbol(false);
1147 Symbol &sym = sec.file->getSymbol(symbolIndex: symIdx);
1148 uint64_t offset = rel.r_offset;
1149 RelExpr expr = getRelExpr(type, s: sym, loc: sec.content().data() + offset);
1150
1151 // Error if the target symbol is undefined. Symbol index 0 may be used by
1152 // marker relocations, e.g. R_*_NONE and R_ARM_V4BX. Don't error on them.
1153 if (sym.isUndefined() && symIdx != 0 &&
1154 rs.maybeReportUndefined(sym&: cast<Undefined>(Val&: sym), offset))
1155 continue;
1156 rs.process(expr, type, offset, sym, addend: rs.getAddend(rel, type));
1157 }
1158}
1159
1160void TargetInfo::scanSection(InputSectionBase &sec, unsigned shard) {
1161 invokeELFT(elf::scanSection1, *this, sec, shard);
1162}
1163
1164void RelocScan::scanEhSection(EhInputSection &s) {
1165 sec = &s;
1166 OffsetGetter getter(s);
1167 s.relocations.reserve(N: s.rels.size());
1168 for (const Relocation &r : s.rels) {
1169 // Ignore R_*_NONE and other marker relocations.
1170 if (r.expr == R_NONE)
1171 continue;
1172 uint64_t offset = getter.get(ctx, off: r.offset);
1173 // Skip if the relocation offset is within a dead piece.
1174 if (offset == uint64_t(-1))
1175 continue;
1176 Symbol *sym = r.sym;
1177 if (sym->isUndefined() &&
1178 maybeReportUndefined(sym&: cast<Undefined>(Val&: *sym), offset))
1179 continue;
1180 process(expr: r.expr, type: r.type, offset, sym&: *sym, addend: r.addend);
1181 }
1182}
1183
1184void elf::scanRelocations(Ctx &ctx) {
1185 // Scan all relocations. Each relocation goes through a series of tests to
1186 // determine if it needs special treatment, such as creating GOT, PLT,
1187 // copy relocations, etc. Note that relocations for non-alloc sections are
1188 // directly processed by InputSection::relocateNonAlloc.
1189
1190 // MIPS modifies MipsGotSection during relocation scanning, which is not
1191 // suitable for parallelism.
1192 size_t numWorkers = ctx.arg.emachine == EM_MIPS ? 1 : ctx.arg.threadCount;
1193 // Item 0 scans special sections (claimed first since .eh_frame is large)
1194 // while item i scans ctx.objectFiles[i - 1].
1195 parallelForSharded(
1196 numShards: numWorkers, end: ctx.objectFiles.size() + 1, fn: [&](size_t shard, size_t i) {
1197 if (i != 0) {
1198 for (InputSectionBase *s : ctx.objectFiles[i - 1]->getSections())
1199 if (s && s->kind() == SectionBase::Regular && s->isLive() &&
1200 (s->flags & SHF_ALLOC) &&
1201 !(s->type == SHT_ARM_EXIDX && ctx.arg.emachine == EM_ARM))
1202 ctx.target->scanSection(sec&: *s, shard);
1203 return;
1204 }
1205 RelocScan scanner(ctx, nullptr, shard);
1206 for (EhInputSection *sec : ctx.in.ehFrame->sections)
1207 scanner.scanEhSection(s&: *sec);
1208 ARMExidxSyntheticSection *armExidx = ctx.in.armExidx.get();
1209 if (armExidx && armExidx->isLive())
1210 for (InputSection *sec : armExidx->exidxSections)
1211 if (sec->isLive())
1212 ctx.target->scanSection(sec&: *sec, shard);
1213 });
1214}
1215
1216RelocationBaseSection &elf::getIRelativeSection(Ctx &ctx) {
1217 // Prior to Android V, there was a bug that caused RELR relocations to be
1218 // applied after packed relocations. This meant that resolvers referenced by
1219 // IRELATIVE relocations in the packed relocation section would read
1220 // unrelocated globals with RELR relocations when
1221 // --pack-relative-relocs=android+relr is enabled. Work around this by placing
1222 // IRELATIVE in .rela.plt.
1223 return ctx.arg.androidPackDynRelocs ? *ctx.in.relaPlt : *ctx.in.relaDyn;
1224}
1225
1226static bool handleNonPreemptibleIfunc(Ctx &ctx, Symbol &sym, uint16_t flags) {
1227 // Non-preemptible ifuncs are called via a PLT entry that resolves the actual
1228 // address at runtime. We create an IPLT entry and an IGOTPLT slot. The
1229 // IGOTPLT slot is relocated by an IRELATIVE relocation, whose addend encodes
1230 // the resolver address. At startup, the runtime calls the resolver and
1231 // fills the IGOTPLT slot.
1232 //
1233 // For direct (non-GOT/PLT) relocations, the symbol must have a constant
1234 // address. We achieve this by redirecting the symbol to its IPLT entry
1235 // ("canonicalizing" it), so all references see the same address, and the
1236 // resolver is called exactly once. This may result in two GOT entries: one
1237 // in .got.plt for the IRELATIVE, and one in .got pointing to the canonical
1238 // IPLT entry (for GOT-generating relocations). We clone the symbol to
1239 // preserve the original resolver address for the IRELATIVE addend. The clone
1240 // is tracked in ctx.irelativeSyms so that linker relaxation can adjust its
1241 // value when the resolver address changes.
1242 //
1243 // Note: IRELATIVE relocations are needed even in static executables; see
1244 // `addRelIpltSymbols`.
1245 if (!sym.isGnuIFunc() || sym.isPreemptible || ctx.arg.zIfuncNoplt)
1246 return false;
1247 // Skip unreferenced non-preemptible ifunc.
1248 if (!(flags & (NEEDS_GOT | NEEDS_GOT_AUTH | NEEDS_PLT | HAS_DIRECT_RELOC)))
1249 return true;
1250 // We only support one kind of GOT entry, and IPLT entries currently always
1251 // use non-AUTH GOT entries.
1252 if (flags & NEEDS_GOT_AUTH) {
1253 auto diag = Err(ctx);
1254 diag << "AUTH GOT entry for non-preemptible ifunc '" << sym.getName()
1255 << "' requested, but R_AARCH64_AUTH_IRELATIVE is not supported yet";
1256 return true;
1257 }
1258
1259 auto addIpltEntry = [&](Symbol &irelativeSym) {
1260 irelativeSym.isInIplt = true;
1261 irelativeSym.allocateAux(ctx);
1262 auto &dyn = getIRelativeSection(ctx);
1263 addPltEntry(ctx, plt&: *ctx.in.iplt, gotPlt&: *ctx.in.igotPlt, rel&: dyn,
1264 type: ctx.target->iRelativeRel, sym&: irelativeSym);
1265 };
1266
1267 if (flags & HAS_DIRECT_RELOC) {
1268 // Change the value to the IPLT and redirect all references to it.
1269 auto &d = cast<Defined>(Val&: sym);
1270 auto *irelativeSym = addSyntheticLocal(ctx, name: d.getName(), type: d.type, value: d.value,
1271 size: d.size, section&: *d.section);
1272 addIpltEntry(*irelativeSym);
1273 ctx.irelativeSyms.push_back(Elt: irelativeSym);
1274 sym.isInIplt = true;
1275 sym.allocateAux(ctx);
1276 ctx.symAux.back().pltIdx = ctx.symAux[irelativeSym->auxIdx].pltIdx;
1277 d.section = ctx.in.iplt.get();
1278 d.value = d.getPltIdx(ctx) * ctx.target->ipltEntrySize;
1279 d.size = 0;
1280 // It's important to set the symbol type here so that dynamic loaders
1281 // don't try to call the PLT as if it were an ifunc resolver.
1282 d.type = STT_FUNC;
1283
1284 if (flags & NEEDS_GOT)
1285 addGotEntry(ctx, sym);
1286 } else {
1287 addIpltEntry(sym);
1288 if (flags & NEEDS_GOT) {
1289 // Redirect GOT accesses to point to the Igot.
1290 sym.gotInIgot = true;
1291 }
1292 }
1293 return true;
1294}
1295
1296void elf::postScanRelocations(Ctx &ctx) {
1297 bool needsTlsIe = false;
1298 auto fn = [&](Symbol &sym) {
1299 auto flags = sym.flags.load(m: std::memory_order_relaxed);
1300 if (handleNonPreemptibleIfunc(ctx, sym, flags))
1301 return;
1302
1303 if (sym.isTagged() && sym.isDefined())
1304 ctx.in.memtagGlobalDescriptors->addSymbol(sym);
1305
1306 if (!sym.needsDynReloc())
1307 return;
1308 sym.allocateAux(ctx);
1309
1310 if (flags & (NEEDS_GOT | NEEDS_GOT_AUTH)) {
1311 if ((flags & NEEDS_GOT) && (flags & NEEDS_GOT_AUTH)) {
1312 auto diag = Err(ctx);
1313 diag << "both AUTH and non-AUTH GOT entries for '" << sym.getName()
1314 << "' requested, but only one type of GOT entry per symbol is "
1315 "supported";
1316 return;
1317 }
1318 if (flags & NEEDS_GOT_AUTH)
1319 addGotAuthEntry(ctx, sym);
1320 else
1321 addGotEntry(ctx, sym);
1322 }
1323 if (flags & NEEDS_PLT)
1324 addPltEntry(ctx, plt&: *ctx.in.plt, gotPlt&: *ctx.in.gotPlt, rel&: *ctx.in.relaPlt,
1325 type: ctx.target->pltRel, sym);
1326 if (flags & NEEDS_COPY) {
1327 if (sym.isObject()) {
1328 invokeELFT(addCopyRelSymbol, ctx, cast<SharedSymbol>(sym));
1329 // NEEDS_COPY is cleared for sym and its aliases so that in
1330 // later iterations aliases won't cause redundant copies.
1331 assert(!sym.hasFlag(NEEDS_COPY));
1332 } else {
1333 assert(sym.isFunc() && sym.hasFlag(NEEDS_PLT));
1334 if (!sym.isDefined()) {
1335 replaceWithDefined(ctx, sym, sec&: *ctx.in.plt,
1336 value: ctx.target->pltHeaderSize +
1337 ctx.target->pltEntrySize * sym.getPltIdx(ctx),
1338 size: 0);
1339 sym.setFlags(NEEDS_COPY);
1340 if (ctx.arg.emachine == EM_PPC) {
1341 // PPC32 canonical PLT entries are at the beginning of .glink
1342 cast<Defined>(Val&: sym).value = ctx.in.plt->headerSize;
1343 ctx.in.plt->headerSize += 16;
1344 cast<PPC32GlinkSection>(Val&: *ctx.in.plt).canonical_plts.push_back(Elt: &sym);
1345 }
1346 }
1347 }
1348 }
1349
1350 if (!sym.isTls())
1351 return;
1352 GotSection *got = ctx.in.got.get();
1353
1354 if (flags & (NEEDS_TLSDESC | NEEDS_TLSDESC_AUTH)) {
1355 if ((flags & NEEDS_TLSDESC) && (flags & NEEDS_TLSDESC_AUTH)) {
1356 Err(ctx)
1357 << "both AUTH and non-AUTH TLSDESC entries for '" << sym.getName()
1358 << "' requested, but only one type of TLSDESC entry per symbol is "
1359 "supported";
1360 return;
1361 }
1362 got->addTlsDescEntry(sym);
1363 RelType tlsDescRel = ctx.target->tlsDescRel;
1364 if (flags & NEEDS_TLSDESC_AUTH) {
1365 got->addTlsDescAuthEntry(sym);
1366 tlsDescRel = ELF::R_AARCH64_AUTH_TLSDESC;
1367 }
1368 ctx.in.relaDyn->addAddendOnlyRelocIfNonPreemptible(
1369 dynType: tlsDescRel, isec&: *got, offsetInSec: got->getTlsDescOffset(sym), sym, addendRelType: tlsDescRel);
1370 }
1371 if (flags & NEEDS_TLSGD) {
1372 got->addDynTlsEntry(sym);
1373 uint64_t off = got->getGlobalDynOffset(b: sym);
1374 uint64_t offsetOff = off + ctx.arg.wordsize;
1375 if (sym.isPreemptible) {
1376 ctx.in.relaDyn->addSymbolReloc(dynType: ctx.target->tlsModuleIndexRel, isec&: *got, offsetInSec: off,
1377 sym);
1378 // If the symbol is preemptible we need the dynamic linker to write
1379 // the offset too.
1380 ctx.in.relaDyn->addSymbolReloc(dynType: ctx.target->tlsOffsetRel, isec&: *got,
1381 offsetInSec: offsetOff, sym);
1382 } else {
1383 if (ctx.arg.shared)
1384 ctx.in.relaDyn->addReloc(reloc: {ctx.target->tlsModuleIndexRel, got, off});
1385 else
1386 // Write one to the GOT slot.
1387 got->addConstant(r: {.expr: R_ADDEND, .type: ctx.target->symbolicRel, .offset: off, .addend: 1, .sym: &sym});
1388 got->addConstant(r: {.expr: R_ABS, .type: ctx.target->tlsOffsetRel, .offset: offsetOff, .addend: 0, .sym: &sym});
1389 }
1390 }
1391 if (flags & NEEDS_GOT_DTPREL) {
1392 got->addEntry(sym);
1393 got->addConstant(
1394 r: {.expr: R_ABS, .type: ctx.target->tlsOffsetRel, .offset: sym.getGotOffset(ctx), .addend: 0, .sym: &sym});
1395 }
1396
1397 if (flags & NEEDS_TLSIE) {
1398 needsTlsIe = true;
1399 addTpOffsetGotEntry(ctx, sym);
1400 }
1401 };
1402
1403 ctx.target->finalizeRelocScan();
1404
1405 GotSection *got = ctx.in.got.get();
1406 if (ctx.needsTlsLd.load(m: std::memory_order_relaxed) && got->addTlsIndex()) {
1407 if (ctx.arg.shared)
1408 ctx.in.relaDyn->addReloc(
1409 reloc: {ctx.target->tlsModuleIndexRel, got, got->getTlsIndexOff()});
1410 else
1411 got->addConstant(r: {.expr: R_ADDEND, .type: ctx.target->symbolicRel,
1412 .offset: got->getTlsIndexOff(), .addend: 1, .sym: ctx.dummySym});
1413 }
1414
1415 assert(ctx.symAux.size() == 1);
1416 for (Symbol *sym : ctx.symtab->getSymbols())
1417 fn(*sym);
1418
1419 // Local symbols may need the aforementioned non-preemptible ifunc and GOT
1420 // handling. They don't need regular PLT.
1421 for (ELFFileBase *file : ctx.objectFiles)
1422 for (Symbol *sym : file->getLocalSymbols())
1423 fn(*sym);
1424
1425 if (needsTlsIe)
1426 ctx.hasTlsIe.store(i: true, m: std::memory_order_relaxed);
1427
1428 if (ctx.arg.branchToBranch)
1429 ctx.target->applyBranchToBranchOpt();
1430}
1431
1432static bool mergeCmp(const InputSection *a, const InputSection *b) {
1433 // std::merge requires a strict weak ordering.
1434 if (a->outSecOff < b->outSecOff)
1435 return true;
1436
1437 // FIXME dyn_cast<ThunkSection> is non-null for any SyntheticSection.
1438 if (a->outSecOff == b->outSecOff && a != b) {
1439 auto *ta = dyn_cast<ThunkSection>(Val: a);
1440 auto *tb = dyn_cast<ThunkSection>(Val: b);
1441
1442 // Check if Thunk is immediately before any specific Target
1443 // InputSection for example Mips LA25 Thunks.
1444 if (ta && ta->getTargetInputSection() == b)
1445 return true;
1446
1447 // Place Thunk Sections without specific targets before
1448 // non-Thunk Sections.
1449 if (ta && !tb && !ta->getTargetInputSection())
1450 return true;
1451 }
1452
1453 return false;
1454}
1455
1456// Call Fn on every executable InputSection accessed via the linker script
1457// InputSectionDescription::Sections.
1458static void forEachInputSectionDescription(
1459 ArrayRef<OutputSection *> outputSections,
1460 llvm::function_ref<void(OutputSection *, InputSectionDescription *)> fn) {
1461 for (OutputSection *os : outputSections) {
1462 if (!(os->flags & SHF_ALLOC) || !(os->flags & SHF_EXECINSTR))
1463 continue;
1464 for (SectionCommand *bc : os->commands)
1465 if (auto *isd = dyn_cast<InputSectionDescription>(Val: bc))
1466 fn(os, isd);
1467 }
1468}
1469
1470ThunkCreator::ThunkCreator(Ctx &ctx) : ctx(ctx) {}
1471
1472ThunkCreator::~ThunkCreator() {}
1473
1474// Thunk Implementation
1475//
1476// Thunks (sometimes called stubs, veneers or branch islands) are small pieces
1477// of code that the linker inserts inbetween a caller and a callee. The thunks
1478// are added at link time rather than compile time as the decision on whether
1479// a thunk is needed, such as the caller and callee being out of range, can only
1480// be made at link time.
1481//
1482// It is straightforward to tell given the current state of the program when a
1483// thunk is needed for a particular call. The more difficult part is that
1484// the thunk needs to be placed in the program such that the caller can reach
1485// the thunk and the thunk can reach the callee; furthermore, adding thunks to
1486// the program alters addresses, which can mean more thunks etc.
1487//
1488// In lld we have a synthetic ThunkSection that can hold many Thunks.
1489// The decision to have a ThunkSection act as a container means that we can
1490// more easily handle the most common case of a single block of contiguous
1491// Thunks by inserting just a single ThunkSection.
1492//
1493// The implementation of Thunks in lld is split across these areas
1494// Relocations.cpp : Framework for creating and placing thunks
1495// Thunks.cpp : The code generated for each supported thunk
1496// Target.cpp : Target specific hooks that the framework uses to decide when
1497// a thunk is used
1498// Synthetic.cpp : Implementation of ThunkSection
1499// Writer.cpp : Iteratively call framework until no more Thunks added
1500//
1501// Thunk placement requirements:
1502// Mips LA25 thunks. These must be placed immediately before the callee section
1503// We can assume that the caller is in range of the Thunk. These are modelled
1504// by Thunks that return the section they must precede with
1505// getTargetInputSection().
1506//
1507// ARM interworking and range extension thunks. These thunks must be placed
1508// within range of the caller. All implemented ARM thunks can always reach the
1509// callee as they use an indirect jump via a register that has no range
1510// restrictions.
1511//
1512// Thunk placement algorithm:
1513// For Mips LA25 ThunkSections; the placement is explicit, it has to be before
1514// getTargetInputSection().
1515//
1516// For thunks that must be placed within range of the caller there are many
1517// possible choices given that the maximum range from the caller is usually
1518// much larger than the average InputSection size. Desirable properties include:
1519// - Maximize reuse of thunks by multiple callers
1520// - Minimize number of ThunkSections to simplify insertion
1521// - Handle impact of already added Thunks on addresses
1522// - Simple to understand and implement
1523//
1524// In lld for the first pass, we pre-create one or more ThunkSections per
1525// InputSectionDescription at Target specific intervals. A ThunkSection is
1526// placed so that the estimated end of the ThunkSection is within range of the
1527// start of the InputSectionDescription or the previous ThunkSection. For
1528// example:
1529// InputSectionDescription
1530// Section 0
1531// ...
1532// Section N
1533// ThunkSection 0
1534// Section N + 1
1535// ...
1536// Section N + K
1537// Thunk Section 1
1538//
1539// The intention is that we can add a Thunk to a ThunkSection that is well
1540// spaced enough to service a number of callers without having to do a lot
1541// of work. An important principle is that it is not an error if a Thunk cannot
1542// be placed in a pre-created ThunkSection; when this happens we create a new
1543// ThunkSection placed next to the caller. This allows us to handle the vast
1544// majority of thunks simply, but also handle rare cases where the branch range
1545// is smaller than the target specific spacing.
1546//
1547// The algorithm is expected to create all the thunks that are needed in a
1548// single pass, with a small number of programs needing a second pass due to
1549// the insertion of thunks in the first pass increasing the offset between
1550// callers and callees that were only just in range.
1551//
1552// A consequence of allowing new ThunkSections to be created outside of the
1553// pre-created ThunkSections is that in rare cases calls to Thunks that were in
1554// range in pass K, are out of range in some pass > K due to the insertion of
1555// more Thunks in between the caller and callee. When this happens we retarget
1556// the relocation back to the original target and create another Thunk.
1557
1558// Remove ThunkSections that are empty, this should only be the initial set
1559// precreated on pass 0.
1560
1561// Insert the Thunks for OutputSection OS into their designated place
1562// in the Sections vector, and recalculate the InputSection output section
1563// offsets.
1564// This may invalidate any output section offsets stored outside of InputSection
1565void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> outputSections) {
1566 forEachInputSectionDescription(
1567 outputSections, fn: [&](OutputSection *os, InputSectionDescription *isd) {
1568 if (isd->thunkSections.empty())
1569 return;
1570
1571 // Remove any zero sized precreated Thunks.
1572 llvm::erase_if(C&: isd->thunkSections,
1573 P: [](const std::pair<ThunkSection *, uint32_t> &ts) {
1574 return ts.first->getSize() == 0;
1575 });
1576
1577 // ISD->ThunkSections contains all created ThunkSections, including
1578 // those inserted in previous passes. Extract the Thunks created this
1579 // pass and order them in ascending outSecOff.
1580 std::vector<ThunkSection *> newThunks;
1581 for (std::pair<ThunkSection *, uint32_t> ts : isd->thunkSections)
1582 if (ts.second == pass)
1583 newThunks.push_back(x: ts.first);
1584 llvm::stable_sort(Range&: newThunks,
1585 C: [](const ThunkSection *a, const ThunkSection *b) {
1586 return a->outSecOff < b->outSecOff;
1587 });
1588
1589 // Merge sorted vectors of Thunks and InputSections by outSecOff
1590 SmallVector<InputSection *, 0> tmp;
1591 tmp.reserve(N: isd->sections.size() + newThunks.size());
1592
1593 std::merge(first1: isd->sections.begin(), last1: isd->sections.end(),
1594 first2: newThunks.begin(), last2: newThunks.end(), result: std::back_inserter(x&: tmp),
1595 comp: mergeCmp);
1596
1597 isd->sections = std::move(tmp);
1598 });
1599}
1600
1601constexpr uint32_t HEXAGON_MASK_END_PACKET = 3 << 14;
1602constexpr uint32_t HEXAGON_END_OF_PACKET = 3 << 14;
1603constexpr uint32_t HEXAGON_END_OF_DUPLEX = 0 << 14;
1604
1605// Return the distance between the packet start and the instruction in the
1606// relocation.
1607static int getHexagonPacketOffset(const InputSection &isec,
1608 const Relocation &rel) {
1609 const ArrayRef<uint8_t> data = isec.content();
1610
1611 // Search back as many as 3 instructions.
1612 for (unsigned i = 0;; i++) {
1613 if (i == 3 || rel.offset < (i + 1) * 4)
1614 return i * 4;
1615 uint32_t instWord =
1616 read32(ctx&: isec.getCtx(), p: data.data() + (rel.offset - (i + 1) * 4));
1617 if (((instWord & HEXAGON_MASK_END_PACKET) == HEXAGON_END_OF_PACKET) ||
1618 ((instWord & HEXAGON_MASK_END_PACKET) == HEXAGON_END_OF_DUPLEX))
1619 return i * 4;
1620 }
1621}
1622
1623static int64_t getPCBias(Ctx &ctx, const InputSection &isec,
1624 const Relocation &rel) {
1625 if (ctx.arg.emachine == EM_ARM) {
1626 switch (rel.type) {
1627 case R_ARM_THM_JUMP19:
1628 case R_ARM_THM_JUMP24:
1629 case R_ARM_THM_CALL:
1630 return 4;
1631 default:
1632 return 8;
1633 }
1634 }
1635 if (ctx.arg.emachine == EM_HEXAGON)
1636 return -getHexagonPacketOffset(isec, rel);
1637 return 0;
1638}
1639
1640// Find or create a ThunkSection within the InputSectionDescription (ISD) that
1641// is in range of Src. An ISD maps to a range of InputSections described by a
1642// linker script section pattern such as { .text .text.* }.
1643ThunkSection *ThunkCreator::getISDThunkSec(OutputSection *os,
1644 InputSection *isec,
1645 InputSectionDescription *isd,
1646 const Relocation &rel,
1647 uint64_t src) {
1648 // See the comment in getThunk for -pcBias below.
1649 const int64_t pcBias = getPCBias(ctx, isec: *isec, rel);
1650 for (std::pair<ThunkSection *, uint32_t> tp : isd->thunkSections) {
1651 ThunkSection *ts = tp.first;
1652 uint64_t tsBase = os->addr + ts->outSecOff - pcBias;
1653 uint64_t tsLimit = tsBase + ts->getSize();
1654 if (ctx.target->inBranchRange(type: rel.type, src,
1655 dst: (src > tsLimit) ? tsBase : tsLimit))
1656 return ts;
1657 }
1658
1659 // No suitable ThunkSection exists. This can happen when there is a branch
1660 // with lower range than the ThunkSection spacing or when there are too
1661 // many Thunks. Create a new ThunkSection as close to the InputSection as
1662 // possible. Error if InputSection is so large we cannot place ThunkSection
1663 // anywhere in Range.
1664 uint64_t thunkSecOff = isec->outSecOff;
1665 if (!ctx.target->inBranchRange(type: rel.type, src,
1666 dst: os->addr + thunkSecOff + rel.addend)) {
1667 thunkSecOff = isec->outSecOff + isec->getSize();
1668 if (!ctx.target->inBranchRange(type: rel.type, src,
1669 dst: os->addr + thunkSecOff + rel.addend))
1670 Fatal(ctx) << "InputSection too large for range extension thunk "
1671 << isec->getObjMsg(offset: src - (os->addr << isec->outSecOff));
1672 }
1673 return addThunkSection(os, isd, off: thunkSecOff);
1674}
1675
1676// Add a Thunk that needs to be placed in a ThunkSection that immediately
1677// precedes its Target.
1678ThunkSection *ThunkCreator::getISThunkSec(InputSection *isec) {
1679 ThunkSection *ts = thunkedSections.lookup(Val: isec);
1680 if (ts)
1681 return ts;
1682
1683 // Find InputSectionRange within Target Output Section (TOS) that the
1684 // InputSection (IS) that we need to precede is in.
1685 OutputSection *tos = isec->getParent();
1686 for (SectionCommand *bc : tos->commands) {
1687 auto *isd = dyn_cast<InputSectionDescription>(Val: bc);
1688 if (!isd || isd->sections.empty())
1689 continue;
1690
1691 InputSection *first = isd->sections.front();
1692 InputSection *last = isd->sections.back();
1693
1694 if (isec->outSecOff < first->outSecOff || last->outSecOff < isec->outSecOff)
1695 continue;
1696
1697 ts = addThunkSection(os: tos, isd, off: isec->outSecOff, /*isPrefix=*/true);
1698 thunkedSections[isec] = ts;
1699 return ts;
1700 }
1701
1702 return nullptr;
1703}
1704
1705// Create one or more ThunkSections per OS that can be used to place Thunks.
1706// We attempt to place the ThunkSections using the following desirable
1707// properties:
1708// - Within range of the maximum number of callers
1709// - Minimise the number of ThunkSections
1710//
1711// We follow a simple but conservative heuristic to place ThunkSections at
1712// offsets that are multiples of a Target specific branch range.
1713// For an InputSectionDescription that is smaller than the range, a single
1714// ThunkSection at the end of the range will do.
1715//
1716// For an InputSectionDescription that is more than twice the size of the range,
1717// we place the last ThunkSection at range bytes from the end of the
1718// InputSectionDescription in order to increase the likelihood that the
1719// distance from a thunk to its target will be sufficiently small to
1720// allow for the creation of a short thunk.
1721void ThunkCreator::createInitialThunkSections(
1722 ArrayRef<OutputSection *> outputSections) {
1723 uint32_t thunkSectionSpacing = ctx.target->getThunkSectionSpacing();
1724 forEachInputSectionDescription(
1725 outputSections, fn: [&](OutputSection *os, InputSectionDescription *isd) {
1726 if (isd->sections.empty())
1727 return;
1728
1729 uint32_t isdBegin = isd->sections.front()->outSecOff;
1730 uint32_t isdEnd =
1731 isd->sections.back()->outSecOff + isd->sections.back()->getSize();
1732 uint32_t lastThunkLowerBound = -1;
1733 if (isdEnd - isdBegin > thunkSectionSpacing * 2)
1734 lastThunkLowerBound = isdEnd - thunkSectionSpacing;
1735
1736 uint32_t isecLimit;
1737 uint32_t prevIsecLimit = isdBegin;
1738 uint32_t thunkUpperBound = isdBegin + thunkSectionSpacing;
1739
1740 for (const InputSection *isec : isd->sections) {
1741 isecLimit = isec->outSecOff + isec->getSize();
1742 if (isecLimit > thunkUpperBound) {
1743 addThunkSection(os, isd, off: prevIsecLimit);
1744 thunkUpperBound = prevIsecLimit + thunkSectionSpacing;
1745 }
1746 if (isecLimit > lastThunkLowerBound)
1747 break;
1748 prevIsecLimit = isecLimit;
1749 }
1750 addThunkSection(os, isd, off: isecLimit);
1751 });
1752}
1753
1754ThunkSection *ThunkCreator::addThunkSection(OutputSection *os,
1755 InputSectionDescription *isd,
1756 uint64_t off, bool isPrefix) {
1757 auto *ts = make<ThunkSection>(args&: ctx, args&: os, args&: off);
1758 ts->partition = os->partition;
1759 if ((ctx.arg.fixCortexA53Errata843419 || ctx.arg.fixCortexA8) &&
1760 !isd->sections.empty() && !isPrefix) {
1761 // The errata fixes are sensitive to addresses modulo 4 KiB. When we add
1762 // thunks we disturb the base addresses of sections placed after the thunks
1763 // this makes patches we have generated redundant, and may cause us to
1764 // generate more patches as different instructions are now in sensitive
1765 // locations. When we generate more patches we may force more branches to
1766 // go out of range, causing more thunks to be generated. In pathological
1767 // cases this can cause the address dependent content pass not to converge.
1768 // We fix this by rounding up the size of the ThunkSection to 4KiB, this
1769 // limits the insertion of a ThunkSection on the addresses modulo 4 KiB,
1770 // which means that adding Thunks to the section does not invalidate
1771 // errata patches for following code.
1772 // Rounding up the size to 4KiB has consequences for code-size and can
1773 // trip up linker script defined assertions. For example the linux kernel
1774 // has an assertion that what LLD represents as an InputSectionDescription
1775 // does not exceed 4 KiB even if the overall OutputSection is > 128 Mib.
1776 // We use the heuristic of rounding up the size when both of the following
1777 // conditions are true:
1778 // 1.) The OutputSection is larger than the ThunkSectionSpacing. This
1779 // accounts for the case where no single InputSectionDescription is
1780 // larger than the OutputSection size. This is conservative but simple.
1781 // 2.) The InputSectionDescription is larger than 4 KiB. This will prevent
1782 // any assertion failures that an InputSectionDescription is < 4 KiB
1783 // in size.
1784 //
1785 // isPrefix is a ThunkSection explicitly inserted before its target
1786 // section. We suppress the rounding up of the size of these ThunkSections
1787 // as unlike normal ThunkSections, they are small in size, but when BTI is
1788 // enabled very frequent. This can bloat code-size and push the errata
1789 // patches out of branch range.
1790 uint64_t isdSize = isd->sections.back()->outSecOff +
1791 isd->sections.back()->getSize() -
1792 isd->sections.front()->outSecOff;
1793 if (os->size > ctx.target->getThunkSectionSpacing() && isdSize > 4096)
1794 ts->roundUpSizeForErrata = true;
1795 }
1796 isd->thunkSections.push_back(Elt: {ts, pass});
1797 return ts;
1798}
1799
1800static bool isThunkSectionCompatible(InputSection *source, Thunk &thunk) {
1801 // Thunks that precede their target section are logically an alternative entry
1802 // point and can always compatible.
1803 if (thunk.getTargetInputSection())
1804 return true;
1805
1806 SectionBase *target = thunk.getThunkTargetSym()->section;
1807 OutputSection *sourceOS = source->getOutputSection();
1808 OutputSection *targetOS = target->getOutputSection();
1809 assert(sourceOS && targetOS);
1810
1811 // Thunks in a different Overlay Output Section can't be reused
1812 // as we can't guarantee that the Overlay will be in memory.
1813 return (sourceOS == targetOS || !targetOS->inOverlay);
1814}
1815
1816std::pair<Thunk *, bool> ThunkCreator::getThunk(InputSection *isec,
1817 Relocation &rel, uint64_t src) {
1818 SmallVector<std::unique_ptr<Thunk>, 0> *thunkVec = nullptr;
1819 // Arm and Thumb have a PC Bias of 8 and 4 respectively, this is cancelled
1820 // out in the relocation addend. We compensate for the PC bias so that
1821 // an Arm and Thumb relocation to the same destination get the same keyAddend,
1822 // which is usually 0.
1823 const int64_t pcBias = getPCBias(ctx, isec: *isec, rel);
1824 const int64_t keyAddend = rel.addend + pcBias;
1825
1826 // We use a ((section, offset), addend) pair to find the thunk position if
1827 // possible so that we create only one thunk for aliased symbols or ICFed
1828 // sections. There may be multiple relocations sharing the same (section,
1829 // offset + addend) pair. We may revert the relocation back to its original
1830 // non-Thunk target, so we cannot fold offset + addend.
1831 if (auto *d = dyn_cast<Defined>(Val: rel.sym))
1832 if (!d->isInPlt(ctx) && d->section)
1833 thunkVec = &thunkedSymbolsBySectionAndAddend[{{d->section, d->value},
1834 keyAddend}];
1835 if (!thunkVec)
1836 thunkVec = &thunkedSymbols[{rel.sym, keyAddend}];
1837
1838 // Check existing Thunks for Sym to see if they can be reused
1839 for (auto &t : *thunkVec)
1840 if (isThunkSectionCompatible(source: isec, thunk&: *t) && t->isCompatibleWith(*isec, rel) &&
1841 ctx.target->inBranchRange(type: rel.type, src,
1842 dst: t->getThunkTargetSym()->getVA(ctx, addend: -pcBias)))
1843 return std::make_pair(x: t.get(), y: false);
1844
1845 // No existing compatible Thunk in range, create a new one
1846 thunkVec->push_back(Elt: addThunk(ctx, isec: *isec, rel));
1847 return std::make_pair(x: thunkVec->back().get(), y: true);
1848}
1849
1850std::pair<Thunk *, bool> ThunkCreator::getSyntheticLandingPad(Defined &d,
1851 int64_t a) {
1852 auto [it, isNew] = landingPadsBySectionAndAddend.try_emplace(
1853 Key: {{d.section, d.value}, a}, Args: nullptr);
1854 if (isNew)
1855 it->second = addLandingPadThunk(ctx, s&: d, a);
1856 return {it->second.get(), isNew};
1857}
1858
1859// Return true if the relocation target is an in range Thunk.
1860// Return false if the relocation is not to a Thunk. If the relocation target
1861// was originally to a Thunk, but is no longer in range we revert the
1862// relocation back to its original non-Thunk target.
1863bool ThunkCreator::normalizeExistingThunk(Relocation &rel, uint64_t src) {
1864 if (Thunk *t = thunks.lookup(Val: rel.sym)) {
1865 if (ctx.target->inBranchRange(type: rel.type, src,
1866 dst: rel.sym->getVA(ctx, addend: rel.addend)))
1867 return true;
1868 rel.sym = &t->destination;
1869 rel.addend = t->addend;
1870 if (rel.sym->isInPlt(ctx))
1871 rel.expr = toPlt(expr: rel.expr);
1872 }
1873 return false;
1874}
1875
1876// When indirect branches are restricted, such as AArch64 BTI Thunks may need
1877// to target a linker generated landing pad instead of the target. This needs
1878// to be done once per pass as the need for a BTI thunk is dependent whether
1879// a thunk is short or long. We iterate over all the thunks to make sure we
1880// catch thunks that have been created but are no longer live. Non-live thunks
1881// are not reachable via normalizeExistingThunk() but are still written.
1882bool ThunkCreator::addSyntheticLandingPads() {
1883 bool addressesChanged = false;
1884 for (Thunk *t : allThunks) {
1885 if (!t->needsSyntheticLandingPad())
1886 continue;
1887 Thunk *lpt;
1888 bool isNew;
1889 auto &dr = cast<Defined>(Val&: t->destination);
1890 std::tie(args&: lpt, args&: isNew) = getSyntheticLandingPad(d&: dr, a: t->addend);
1891 if (isNew) {
1892 addressesChanged = true;
1893 getISThunkSec(isec: cast<InputSection>(Val: dr.section))->addThunk(t: lpt);
1894 }
1895 t->landingPad = lpt->getThunkTargetSym();
1896 }
1897 return addressesChanged;
1898}
1899
1900// Process all relocations from the InputSections that have been assigned
1901// to InputSectionDescriptions and redirect through Thunks if needed. The
1902// function should be called iteratively until it returns false.
1903//
1904// PreConditions:
1905// All InputSections that may need a Thunk are reachable from
1906// OutputSectionCommands.
1907//
1908// All OutputSections have an address and all InputSections have an offset
1909// within the OutputSection.
1910//
1911// The offsets between caller (relocation place) and callee
1912// (relocation target) will not be modified outside of createThunks().
1913//
1914// PostConditions:
1915// If return value is true then ThunkSections have been inserted into
1916// OutputSections. All relocations that needed a Thunk based on the information
1917// available to createThunks() on entry have been redirected to a Thunk. Note
1918// that adding Thunks changes offsets between caller and callee so more Thunks
1919// may be required.
1920//
1921// If return value is false then no more Thunks are needed, and createThunks has
1922// made no changes. If the target requires range extension thunks, currently
1923// ARM, then any future change in offset between caller and callee risks a
1924// relocation out of range error.
1925bool ThunkCreator::createThunks(uint32_t pass,
1926 ArrayRef<OutputSection *> outputSections) {
1927 this->pass = pass;
1928 bool addressesChanged = false;
1929
1930 if (pass == 0 && ctx.target->getThunkSectionSpacing())
1931 createInitialThunkSections(outputSections);
1932
1933 if (ctx.arg.emachine == EM_AARCH64)
1934 addressesChanged = addSyntheticLandingPads();
1935
1936 // Create all the Thunks and insert them into synthetic ThunkSections. The
1937 // ThunkSections are later inserted back into InputSectionDescriptions.
1938 // We separate the creation of ThunkSections from the insertion of the
1939 // ThunkSections as ThunkSections are not always inserted into the same
1940 // InputSectionDescription as the caller.
1941 forEachInputSectionDescription(
1942 outputSections, fn: [&](OutputSection *os, InputSectionDescription *isd) {
1943 for (InputSection *isec : isd->sections)
1944 for (Relocation &rel : isec->relocs()) {
1945 uint64_t src = isec->getVA(offset: rel.offset);
1946
1947 // If we are a relocation to an existing Thunk, check if it is
1948 // still in range. If not then Rel will be altered to point to its
1949 // original target so another Thunk can be generated.
1950 if (pass > 0 && normalizeExistingThunk(rel, src))
1951 continue;
1952
1953 if (!ctx.target->needsThunk(expr: rel.expr, relocType: rel.type, file: isec->file, branchAddr: src,
1954 s: *rel.sym, a: rel.addend))
1955 continue;
1956
1957 Thunk *t;
1958 bool isNew;
1959 std::tie(args&: t, args&: isNew) = getThunk(isec, rel, src);
1960
1961 if (isNew) {
1962 // Find or create a ThunkSection for the new Thunk
1963 ThunkSection *ts;
1964 if (auto *tis = t->getTargetInputSection())
1965 ts = getISThunkSec(isec: tis);
1966 else
1967 ts = getISDThunkSec(os, isec, isd, rel, src);
1968 ts->addThunk(t);
1969 thunks[t->getThunkTargetSym()] = t;
1970 allThunks.push_back(x: t);
1971 }
1972
1973 // Redirect relocation to Thunk, we never go via the PLT to a Thunk
1974 rel.sym = t->getThunkTargetSym();
1975 rel.expr = fromPlt(expr: rel.expr);
1976
1977 // On AArch64 and PPC, a jump/call relocation may be encoded as
1978 // STT_SECTION + non-zero addend, clear the addend after
1979 // redirection.
1980 if (ctx.arg.emachine != EM_MIPS)
1981 rel.addend = -getPCBias(ctx, isec: *isec, rel);
1982 }
1983
1984 for (auto &p : isd->thunkSections) {
1985 // Sort in pass 0, which creates most thunks.
1986 if (pass == 0)
1987 p.first->sortByDestination();
1988 addressesChanged |= p.first->assignOffsets();
1989 }
1990 });
1991
1992 for (auto &p : thunkedSections)
1993 addressesChanged |= p.second->assignOffsets();
1994
1995 // Merge all created synthetic ThunkSections back into OutputSection
1996 mergeThunks(outputSections);
1997 return addressesChanged;
1998}
1999
2000static bool matchesRefTo(const NoCrossRefCommand &cmd, StringRef osec) {
2001 if (cmd.toFirst)
2002 return cmd.outputSections[0] == osec;
2003 return llvm::is_contained(Range: cmd.outputSections, Element: osec);
2004}
2005
2006template <class ELFT, class Rels>
2007static void scanCrossRefs(Ctx &ctx, const NoCrossRefCommand &cmd,
2008 OutputSection *osec, InputSection *sec, Rels rels) {
2009 for (const auto &r : rels) {
2010 Symbol &sym = sec->file->getSymbol(symbolIndex: r.getSymbol(ctx.arg.isMips64EL));
2011 // A legal cross-reference is when the destination output section is
2012 // nullptr, osec for a self-reference, or a section that is described by the
2013 // NOCROSSREFS/NOCROSSREFS_TO command.
2014 auto *dstOsec = sym.getOutputSection();
2015 if (!dstOsec || dstOsec == osec || !matchesRefTo(cmd, osec: dstOsec->name))
2016 continue;
2017
2018 std::string toSymName;
2019 if (!sym.isSection())
2020 toSymName = toStr(ctx, sym);
2021 else if (auto *d = dyn_cast<Defined>(Val: &sym))
2022 toSymName = d->section->name;
2023 Err(ctx) << sec->getLocation(offset: r.r_offset)
2024 << ": prohibited cross reference from '" << osec->name << "' to '"
2025 << toSymName << "' in '" << dstOsec->name << "'";
2026 }
2027}
2028
2029// For each output section described by at least one NOCROSSREFS(_TO) command,
2030// scan relocations from its input sections for prohibited cross references.
2031template <class ELFT> void elf::checkNoCrossRefs(Ctx &ctx) {
2032 for (OutputSection *osec : ctx.outputSections) {
2033 for (const NoCrossRefCommand &noxref : ctx.script->noCrossRefs) {
2034 if (!llvm::is_contained(Range: noxref.outputSections, Element: osec->name) ||
2035 (noxref.toFirst && noxref.outputSections[0] == osec->name))
2036 continue;
2037 for (SectionCommand *cmd : osec->commands) {
2038 auto *isd = dyn_cast<InputSectionDescription>(Val: cmd);
2039 if (!isd)
2040 continue;
2041 parallelForEach(isd->sections, [&](InputSection *sec) {
2042 invokeOnRelocs(*sec, scanCrossRefs<ELFT>, ctx, noxref, osec, sec);
2043 });
2044 }
2045 }
2046 }
2047}
2048
2049template void elf::checkNoCrossRefs<ELF32LE>(Ctx &);
2050template void elf::checkNoCrossRefs<ELF32BE>(Ctx &);
2051template void elf::checkNoCrossRefs<ELF64LE>(Ctx &);
2052template void elf::checkNoCrossRefs<ELF64BE>(Ctx &);
2053