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