1	//===- SyntheticSections.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 linker-synthesized sections. Currently,
10	// synthetic sections are created either output sections or input sections,
11	// but we are rewriting code so that all synthetic sections are created as
12	// input sections.
13	//
14	//===----------------------------------------------------------------------===//
15
16	#include "SyntheticSections.h"
17	#include "Config.h"
18	#include "DWARF.h"
19	#include "EhFrame.h"
20	#include "InputFiles.h"
21	#include "LinkerScript.h"
22	#include "OutputSections.h"
23	#include "SymbolTable.h"
24	#include "Symbols.h"
25	#include "Target.h"
26	#include "Thunks.h"
27	#include "Writer.h"
28	#include "lld/Common/CommonLinkerContext.h"
29	#include "lld/Common/DWARF.h"
30	#include "lld/Common/Strings.h"
31	#include "lld/Common/Version.h"
32	#include "llvm/ADT/STLExtras.h"
33	#include "llvm/ADT/Sequence.h"
34	#include "llvm/ADT/SetOperations.h"
35	#include "llvm/ADT/StringExtras.h"
36	#include "llvm/BinaryFormat/Dwarf.h"
37	#include "llvm/BinaryFormat/ELF.h"
38	#include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
39	#include "llvm/DebugInfo/DWARF/DWARFDebugPubTable.h"
40	#include "llvm/Support/DJB.h"
41	#include "llvm/Support/Endian.h"
42	#include "llvm/Support/LEB128.h"
43	#include "llvm/Support/Parallel.h"
44	#include "llvm/Support/TimeProfiler.h"
45	#include <cinttypes>
46	#include <cstdlib>
47
48	using namespace llvm;
49	using namespace llvm::dwarf;
50	using namespace llvm::ELF;
51	using namespace llvm::object;
52	using namespace llvm::support;
53	using namespace lld;
54	using namespace lld::elf;
55
56	using llvm::support::endian::read32le;
57	using llvm::support::endian::write32le;
58	using llvm::support::endian::write64le;
59
60	constexpr size_t MergeNoTailSection::numShards;
61
62	static uint64_t readUint(uint8_t *buf) {
63	return config->is64 ? read64(p: buf) : read32(p: buf);
64	}
65
66	static void writeUint(uint8_t *buf, uint64_t val) {
67	if (config->is64)
68	write64(p: buf, v: val);
69	else
70	write32(p: buf, v: val);
71	}
72
73	// Returns an LLD version string.
74	static ArrayRef<uint8_t> getVersion() {
75	// Check LLD_VERSION first for ease of testing.
76	// You can get consistent output by using the environment variable.
77	// This is only for testing.
78	StringRef s = getenv(name: "LLD_VERSION");
79	if (s.empty())
80	s = saver().save(S: Twine("Linker: ") + getLLDVersion());
81
82	// +1 to include the terminating '\0'.
83	return {(const uint8_t *)s.data(), s.size() + 1};
84	}
85
86	// Creates a .comment section containing LLD version info.
87	// With this feature, you can identify LLD-generated binaries easily
88	// by "readelf --string-dump .comment <file>".
89	// The returned object is a mergeable string section.
90	MergeInputSection *elf::createCommentSection() {
91	auto *sec = make<MergeInputSection>(args: SHF_MERGE | SHF_STRINGS, args: SHT_PROGBITS, args: 1,
92	args: getVersion(), args: ".comment");
93	sec->splitIntoPieces();
94	return sec;
95	}
96
97	// .MIPS.abiflags section.
98	template <class ELFT>
99	MipsAbiFlagsSection<ELFT>::MipsAbiFlagsSection(Elf_Mips_ABIFlags flags)
100	: SyntheticSection(SHF_ALLOC, SHT_MIPS_ABIFLAGS, 8, ".MIPS.abiflags"),
101	flags(flags) {
102	this->entsize = sizeof(Elf_Mips_ABIFlags);
103	}
104
105	template <class ELFT> void MipsAbiFlagsSection<ELFT>::writeTo(uint8_t *buf) {
106	memcpy(buf, &flags, sizeof(flags));
107	}
108
109	template <class ELFT>
110	std::unique_ptr<MipsAbiFlagsSection<ELFT>> MipsAbiFlagsSection<ELFT>::create() {
111	Elf_Mips_ABIFlags flags = {};
112	bool create = false;
113
114	for (InputSectionBase *sec : ctx.inputSections) {
115	if (sec->type != SHT_MIPS_ABIFLAGS)
116	continue;
117	sec->markDead();
118	create = true;
119
120	std::string filename = toString(f: sec->file);
121	const size_t size = sec->content().size();
122	// Older version of BFD (such as the default FreeBSD linker) concatenate
123	// .MIPS.abiflags instead of merging. To allow for this case (or potential
124	// zero padding) we ignore everything after the first Elf_Mips_ABIFlags
125	if (size < sizeof(Elf_Mips_ABIFlags)) {
126	error(msg: filename + ": invalid size of .MIPS.abiflags section: got " +
127	Twine(size) + " instead of " + Twine(sizeof(Elf_Mips_ABIFlags)));
128	return nullptr;
129	}
130	auto *s =
131	reinterpret_cast<const Elf_Mips_ABIFlags *>(sec->content().data());
132	if (s->version != 0) {
133	error(msg: filename + ": unexpected .MIPS.abiflags version " +
134	Twine(s->version));
135	return nullptr;
136	}
137
138	// LLD checks ISA compatibility in calcMipsEFlags(). Here we just
139	// select the highest number of ISA/Rev/Ext.
140	flags.isa_level = std::max(flags.isa_level, s->isa_level);
141	flags.isa_rev = std::max(flags.isa_rev, s->isa_rev);
142	flags.isa_ext = std::max(flags.isa_ext, s->isa_ext);
143	flags.gpr_size = std::max(flags.gpr_size, s->gpr_size);
144	flags.cpr1_size = std::max(flags.cpr1_size, s->cpr1_size);
145	flags.cpr2_size = std::max(flags.cpr2_size, s->cpr2_size);
146	flags.ases |= s->ases;
147	flags.flags1 |= s->flags1;
148	flags.flags2 |= s->flags2;
149	flags.fp_abi = elf::getMipsFpAbiFlag(oldFlag: flags.fp_abi, newFlag: s->fp_abi, fileName: filename);
150	};
151
152	if (create)
153	return std::make_unique<MipsAbiFlagsSection<ELFT>>(flags);
154	return nullptr;
155	}
156
157	// .MIPS.options section.
158	template <class ELFT>
159	MipsOptionsSection<ELFT>::MipsOptionsSection(Elf_Mips_RegInfo reginfo)
160	: SyntheticSection(SHF_ALLOC, SHT_MIPS_OPTIONS, 8, ".MIPS.options"),
161	reginfo(reginfo) {
162	this->entsize = sizeof(Elf_Mips_Options) + sizeof(Elf_Mips_RegInfo);
163	}
164
165	template <class ELFT> void MipsOptionsSection<ELFT>::writeTo(uint8_t *buf) {
166	auto *options = reinterpret_cast<Elf_Mips_Options *>(buf);
167	options->kind = ODK_REGINFO;
168	options->size = getSize();
169
170	if (!config->relocatable)
171	reginfo.ri_gp_value = in.mipsGot->getGp();
172	memcpy(buf + sizeof(Elf_Mips_Options), &reginfo, sizeof(reginfo));
173	}
174
175	template <class ELFT>
176	std::unique_ptr<MipsOptionsSection<ELFT>> MipsOptionsSection<ELFT>::create() {
177	// N64 ABI only.
178	if (!ELFT::Is64Bits)
179	return nullptr;
180
181	SmallVector<InputSectionBase *, 0> sections;
182	for (InputSectionBase *sec : ctx.inputSections)
183	if (sec->type == SHT_MIPS_OPTIONS)
184	sections.push_back(Elt: sec);
185
186	if (sections.empty())
187	return nullptr;
188
189	Elf_Mips_RegInfo reginfo = {};
190	for (InputSectionBase *sec : sections) {
191	sec->markDead();
192
193	std::string filename = toString(f: sec->file);
194	ArrayRef<uint8_t> d = sec->content();
195
196	while (!d.empty()) {
197	if (d.size() < sizeof(Elf_Mips_Options)) {
198	error(msg: filename + ": invalid size of .MIPS.options section");
199	break;
200	}
201
202	auto *opt = reinterpret_cast<const Elf_Mips_Options *>(d.data());
203	if (opt->kind == ODK_REGINFO) {
204	reginfo.ri_gprmask |= opt->getRegInfo().ri_gprmask;
205	sec->getFile<ELFT>()->mipsGp0 = opt->getRegInfo().ri_gp_value;
206	break;
207	}
208
209	if (!opt->size)
210	fatal(msg: filename + ": zero option descriptor size");
211	d = d.slice(opt->size);
212	}
213	};
214
215	return std::make_unique<MipsOptionsSection<ELFT>>(reginfo);
216	}
217
218	// MIPS .reginfo section.
219	template <class ELFT>
220	MipsReginfoSection<ELFT>::MipsReginfoSection(Elf_Mips_RegInfo reginfo)
221	: SyntheticSection(SHF_ALLOC, SHT_MIPS_REGINFO, 4, ".reginfo"),
222	reginfo(reginfo) {
223	this->entsize = sizeof(Elf_Mips_RegInfo);
224	}
225
226	template <class ELFT> void MipsReginfoSection<ELFT>::writeTo(uint8_t *buf) {
227	if (!config->relocatable)
228	reginfo.ri_gp_value = in.mipsGot->getGp();
229	memcpy(buf, &reginfo, sizeof(reginfo));
230	}
231
232	template <class ELFT>
233	std::unique_ptr<MipsReginfoSection<ELFT>> MipsReginfoSection<ELFT>::create() {
234	// Section should be alive for O32 and N32 ABIs only.
235	if (ELFT::Is64Bits)
236	return nullptr;
237
238	SmallVector<InputSectionBase *, 0> sections;
239	for (InputSectionBase *sec : ctx.inputSections)
240	if (sec->type == SHT_MIPS_REGINFO)
241	sections.push_back(Elt: sec);
242
243	if (sections.empty())
244	return nullptr;
245
246	Elf_Mips_RegInfo reginfo = {};
247	for (InputSectionBase *sec : sections) {
248	sec->markDead();
249
250	if (sec->content().size() != sizeof(Elf_Mips_RegInfo)) {
251	error(msg: toString(f: sec->file) + ": invalid size of .reginfo section");
252	return nullptr;
253	}
254
255	auto *r = reinterpret_cast<const Elf_Mips_RegInfo *>(sec->content().data());
256	reginfo.ri_gprmask |= r->ri_gprmask;
257	sec->getFile<ELFT>()->mipsGp0 = r->ri_gp_value;
258	};
259
260	return std::make_unique<MipsReginfoSection<ELFT>>(reginfo);
261	}
262
263	InputSection *elf::createInterpSection() {
264	// StringSaver guarantees that the returned string ends with '\0'.
265	StringRef s = saver().save(S: config->dynamicLinker);
266	ArrayRef<uint8_t> contents = {(const uint8_t *)s.data(), s.size() + 1};
267
268	return make<InputSection>(args&: ctx.internalFile, args: SHF_ALLOC, args: SHT_PROGBITS, args: 1,
269	args&: contents, args: ".interp");
270	}
271
272	Defined *elf::addSyntheticLocal(StringRef name, uint8_t type, uint64_t value,
273	uint64_t size, InputSectionBase &section) {
274	Defined *s = makeDefined(args&: section.file, args&: name, args: STB_LOCAL, args: STV_DEFAULT, args&: type,
275	args&: value, args&: size, args: &section);
276	if (in.symTab)
277	in.symTab->addSymbol(sym: s);
278
279	if (config->emachine == EM_ARM && !config->isLE && config->armBe8 &&
280	(section.flags & SHF_EXECINSTR))
281	// Adding Linker generated mapping symbols to the arm specific mapping
282	// symbols list.
283	addArmSyntheticSectionMappingSymbol(s);
284
285	return s;
286	}
287
288	static size_t getHashSize() {
289	switch (config->buildId) {
290	case BuildIdKind::Fast:
291	return 8;
292	case BuildIdKind::Md5:
293	case BuildIdKind::Uuid:
294	return 16;
295	case BuildIdKind::Sha1:
296	return 20;
297	case BuildIdKind::Hexstring:
298	return config->buildIdVector.size();
299	default:
300	llvm_unreachable("unknown BuildIdKind");
301	}
302	}
303
304	// This class represents a linker-synthesized .note.gnu.property section.
305	//
306	// In x86 and AArch64, object files may contain feature flags indicating the
307	// features that they have used. The flags are stored in a .note.gnu.property
308	// section.
309	//
310	// lld reads the sections from input files and merges them by computing AND of
311	// the flags. The result is written as a new .note.gnu.property section.
312	//
313	// If the flag is zero (which indicates that the intersection of the feature
314	// sets is empty, or some input files didn't have .note.gnu.property sections),
315	// we don't create this section.
316	GnuPropertySection::GnuPropertySection()
317	: SyntheticSection(llvm::ELF::SHF_ALLOC, llvm::ELF::SHT_NOTE,
318	config->wordsize, ".note.gnu.property") {}
319
320	void GnuPropertySection::writeTo(uint8_t *buf) {
321	write32(p: buf, v: 4); // Name size
322	write32(p: buf + 4, v: getSize() - 16); // Content size
323	write32(p: buf + 8, v: NT_GNU_PROPERTY_TYPE_0); // Type
324	memcpy(dest: buf + 12, src: "GNU", n: 4); // Name string
325
326	uint32_t featureAndType = config->emachine == EM_AARCH64
327	? GNU_PROPERTY_AARCH64_FEATURE_1_AND
328	: GNU_PROPERTY_X86_FEATURE_1_AND;
329
330	unsigned offset = 16;
331	if (config->andFeatures != 0) {
332	write32(p: buf + offset + 0, v: featureAndType); // Feature type
333	write32(p: buf + offset + 4, v: 4); // Feature size
334	write32(p: buf + offset + 8, v: config->andFeatures); // Feature flags
335	if (config->is64)
336	write32(p: buf + offset + 12, v: 0); // Padding
337	offset += 16;
338	}
339
340	if (!ctx.aarch64PauthAbiCoreInfo.empty()) {
341	write32(p: buf + offset + 0, v: GNU_PROPERTY_AARCH64_FEATURE_PAUTH);
342	write32(p: buf + offset + 4, v: ctx.aarch64PauthAbiCoreInfo.size());
343	memcpy(dest: buf + offset + 8, src: ctx.aarch64PauthAbiCoreInfo.data(),
344	n: ctx.aarch64PauthAbiCoreInfo.size());
345	}
346	}
347
348	size_t GnuPropertySection::getSize() const {
349	uint32_t contentSize = 0;
350	if (config->andFeatures != 0)
351	contentSize += config->is64 ? 16 : 12;
352	if (!ctx.aarch64PauthAbiCoreInfo.empty())
353	contentSize += 4 + 4 + ctx.aarch64PauthAbiCoreInfo.size();
354	assert(contentSize != 0);
355	return contentSize + 16;
356	}
357
358	BuildIdSection::BuildIdSection()
359	: SyntheticSection(SHF_ALLOC, SHT_NOTE, 4, ".note.gnu.build-id"),
360	hashSize(getHashSize()) {}
361
362	void BuildIdSection::writeTo(uint8_t *buf) {
363	write32(p: buf, v: 4); // Name size
364	write32(p: buf + 4, v: hashSize); // Content size
365	write32(p: buf + 8, v: NT_GNU_BUILD_ID); // Type
366	memcpy(dest: buf + 12, src: "GNU", n: 4); // Name string
367	hashBuf = buf + 16;
368	}
369
370	void BuildIdSection::writeBuildId(ArrayRef<uint8_t> buf) {
371	assert(buf.size() == hashSize);
372	memcpy(dest: hashBuf, src: buf.data(), n: hashSize);
373	}
374
375	BssSection::BssSection(StringRef name, uint64_t size, uint32_t alignment)
376	: SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_NOBITS, alignment, name) {
377	this->bss = true;
378	this->size = size;
379	}
380
381	EhFrameSection::EhFrameSection()
382	: SyntheticSection(SHF_ALLOC, SHT_PROGBITS, 1, ".eh_frame") {}
383
384	// Search for an existing CIE record or create a new one.
385	// CIE records from input object files are uniquified by their contents
386	// and where their relocations point to.
387	template <class ELFT, class RelTy>
388	CieRecord *EhFrameSection::addCie(EhSectionPiece &cie, ArrayRef<RelTy> rels) {
389	Symbol *personality = nullptr;
390	unsigned firstRelI = cie.firstRelocation;
391	if (firstRelI != (unsigned)-1)
392	personality = &cie.sec->file->getRelocTargetSym(rels[firstRelI]);
393
394	// Search for an existing CIE by CIE contents/relocation target pair.
395	CieRecord *&rec = cieMap[{cie.data(), personality}];
396
397	// If not found, create a new one.
398	if (!rec) {
399	rec = make<CieRecord>();
400	rec->cie = &cie;
401	cieRecords.push_back(Elt: rec);
402	}
403	return rec;
404	}
405
406	// There is one FDE per function. Returns a non-null pointer to the function
407	// symbol if the given FDE points to a live function.
408	template <class ELFT, class RelTy>
409	Defined *EhFrameSection::isFdeLive(EhSectionPiece &fde, ArrayRef<RelTy> rels) {
410	auto *sec = cast<EhInputSection>(Val: fde.sec);
411	unsigned firstRelI = fde.firstRelocation;
412
413	// An FDE should point to some function because FDEs are to describe
414	// functions. That's however not always the case due to an issue of
415	// ld.gold with -r. ld.gold may discard only functions and leave their
416	// corresponding FDEs, which results in creating bad .eh_frame sections.
417	// To deal with that, we ignore such FDEs.
418	if (firstRelI == (unsigned)-1)
419	return nullptr;
420
421	const RelTy &rel = rels[firstRelI];
422	Symbol &b = sec->file->getRelocTargetSym(rel);
423
424	// FDEs for garbage-collected or merged-by-ICF sections, or sections in
425	// another partition, are dead.
426	if (auto *d = dyn_cast<Defined>(Val: &b))
427	if (!d->folded && d->section && d->section->partition == partition)
428	return d;
429	return nullptr;
430	}
431
432	// .eh_frame is a sequence of CIE or FDE records. In general, there
433	// is one CIE record per input object file which is followed by
434	// a list of FDEs. This function searches an existing CIE or create a new
435	// one and associates FDEs to the CIE.
436	template <class ELFT, class RelTy>
437	void EhFrameSection::addRecords(EhInputSection *sec, ArrayRef<RelTy> rels) {
438	offsetToCie.clear();
439	for (EhSectionPiece &cie : sec->cies)
440	offsetToCie[cie.inputOff] = addCie<ELFT>(cie, rels);
441	for (EhSectionPiece &fde : sec->fdes) {
442	uint32_t id = endian::read32<ELFT::Endianness>(fde.data().data() + 4);
443	CieRecord *rec = offsetToCie[fde.inputOff + 4 - id];
444	if (!rec)
445	fatal(msg: toString(sec) + ": invalid CIE reference");
446
447	if (!isFdeLive<ELFT>(fde, rels))
448	continue;
449	rec->fdes.push_back(Elt: &fde);
450	numFdes++;
451	}
452	}
453
454	template <class ELFT>
455	void EhFrameSection::addSectionAux(EhInputSection *sec) {
456	if (!sec->isLive())
457	return;
458	const RelsOrRelas<ELFT> rels = sec->template relsOrRelas<ELFT>();
459	if (rels.areRelocsRel())
460	addRecords<ELFT>(sec, rels.rels);
461	else
462	addRecords<ELFT>(sec, rels.relas);
463	}
464
465	// Used by ICF<ELFT>::handleLSDA(). This function is very similar to
466	// EhFrameSection::addRecords().
467	template <class ELFT, class RelTy>
468	void EhFrameSection::iterateFDEWithLSDAAux(
469	EhInputSection &sec, ArrayRef<RelTy> rels, DenseSet<size_t> &ciesWithLSDA,
470	llvm::function_ref<void(InputSection &)> fn) {
471	for (EhSectionPiece &cie : sec.cies)
472	if (hasLSDA(p: cie))
473	ciesWithLSDA.insert(V: cie.inputOff);
474	for (EhSectionPiece &fde : sec.fdes) {
475	uint32_t id = endian::read32<ELFT::Endianness>(fde.data().data() + 4);
476	if (!ciesWithLSDA.contains(V: fde.inputOff + 4 - id))
477	continue;
478
479	// The CIE has a LSDA argument. Call fn with d's section.
480	if (Defined *d = isFdeLive<ELFT>(fde, rels))
481	if (auto *s = dyn_cast_or_null<InputSection>(Val: d->section))
482	fn(*s);
483	}
484	}
485
486	template <class ELFT>
487	void EhFrameSection::iterateFDEWithLSDA(
488	llvm::function_ref<void(InputSection &)> fn) {
489	DenseSet<size_t> ciesWithLSDA;
490	for (EhInputSection *sec : sections) {
491	ciesWithLSDA.clear();
492	const RelsOrRelas<ELFT> rels = sec->template relsOrRelas<ELFT>();
493	if (rels.areRelocsRel())
494	iterateFDEWithLSDAAux<ELFT>(*sec, rels.rels, ciesWithLSDA, fn);
495	else
496	iterateFDEWithLSDAAux<ELFT>(*sec, rels.relas, ciesWithLSDA, fn);
497	}
498	}
499
500	static void writeCieFde(uint8_t *buf, ArrayRef<uint8_t> d) {
501	memcpy(dest: buf, src: d.data(), n: d.size());
502	// Fix the size field. -4 since size does not include the size field itself.
503	write32(p: buf, v: d.size() - 4);
504	}
505
506	void EhFrameSection::finalizeContents() {
507	assert(!this->size); // Not finalized.
508
509	switch (config->ekind) {
510	case ELFNoneKind:
511	llvm_unreachable("invalid ekind");
512	case ELF32LEKind:
513	for (EhInputSection *sec : sections)
514	addSectionAux<ELF32LE>(sec);
515	break;
516	case ELF32BEKind:
517	for (EhInputSection *sec : sections)
518	addSectionAux<ELF32BE>(sec);
519	break;
520	case ELF64LEKind:
521	for (EhInputSection *sec : sections)
522	addSectionAux<ELF64LE>(sec);
523	break;
524	case ELF64BEKind:
525	for (EhInputSection *sec : sections)
526	addSectionAux<ELF64BE>(sec);
527	break;
528	}
529
530	size_t off = 0;
531	for (CieRecord *rec : cieRecords) {
532	rec->cie->outputOff = off;
533	off += rec->cie->size;
534
535	for (EhSectionPiece *fde : rec->fdes) {
536	fde->outputOff = off;
537	off += fde->size;
538	}
539	}
540
541	// The LSB standard does not allow a .eh_frame section with zero
542	// Call Frame Information records. glibc unwind-dw2-fde.c
543	// classify_object_over_fdes expects there is a CIE record length 0 as a
544	// terminator. Thus we add one unconditionally.
545	off += 4;
546
547	this->size = off;
548	}
549
550	// Returns data for .eh_frame_hdr. .eh_frame_hdr is a binary search table
551	// to get an FDE from an address to which FDE is applied. This function
552	// returns a list of such pairs.
553	SmallVector<EhFrameSection::FdeData, 0> EhFrameSection::getFdeData() const {
554	uint8_t *buf = Out::bufferStart + getParent()->offset + outSecOff;
555	SmallVector<FdeData, 0> ret;
556
557	uint64_t va = getPartition().ehFrameHdr->getVA();
558	for (CieRecord *rec : cieRecords) {
559	uint8_t enc = getFdeEncoding(p: rec->cie);
560	for (EhSectionPiece *fde : rec->fdes) {
561	uint64_t pc = getFdePc(buf, off: fde->outputOff, enc);
562	uint64_t fdeVA = getParent()->addr + fde->outputOff;
563	if (!isInt<32>(x: pc - va)) {
564	errorOrWarn(msg: toString(fde->sec) + ": PC offset is too large: 0x" +
565	Twine::utohexstr(Val: pc - va));
566	continue;
567	}
568	ret.push_back(Elt: {.pcRel: uint32_t(pc - va), .fdeVARel: uint32_t(fdeVA - va)});
569	}
570	}
571
572	// Sort the FDE list by their PC and uniqueify. Usually there is only
573	// one FDE for a PC (i.e. function), but if ICF merges two functions
574	// into one, there can be more than one FDEs pointing to the address.
575	auto less = [](const FdeData &a, const FdeData &b) {
576	return a.pcRel < b.pcRel;
577	};
578	llvm::stable_sort(Range&: ret, C: less);
579	auto eq = [](const FdeData &a, const FdeData &b) {
580	return a.pcRel == b.pcRel;
581	};
582	ret.erase(CS: std::unique(first: ret.begin(), last: ret.end(), binary_pred: eq), CE: ret.end());
583
584	return ret;
585	}
586
587	static uint64_t readFdeAddr(uint8_t *buf, int size) {
588	switch (size) {
589	case DW_EH_PE_udata2:
590	return read16(p: buf);
591	case DW_EH_PE_sdata2:
592	return (int16_t)read16(p: buf);
593	case DW_EH_PE_udata4:
594	return read32(p: buf);
595	case DW_EH_PE_sdata4:
596	return (int32_t)read32(p: buf);
597	case DW_EH_PE_udata8:
598	case DW_EH_PE_sdata8:
599	return read64(p: buf);
600	case DW_EH_PE_absptr:
601	return readUint(buf);
602	}
603	fatal(msg: "unknown FDE size encoding");
604	}
605
606	// Returns the VA to which a given FDE (on a mmap'ed buffer) is applied to.
607	// We need it to create .eh_frame_hdr section.
608	uint64_t EhFrameSection::getFdePc(uint8_t *buf, size_t fdeOff,
609	uint8_t enc) const {
610	// The starting address to which this FDE applies is
611	// stored at FDE + 8 byte. And this offset is within
612	// the .eh_frame section.
613	size_t off = fdeOff + 8;
614	uint64_t addr = readFdeAddr(buf: buf + off, size: enc & 0xf);
615	if ((enc & 0x70) == DW_EH_PE_absptr)
616	return addr;
617	if ((enc & 0x70) == DW_EH_PE_pcrel)
618	return addr + getParent()->addr + off + outSecOff;
619	fatal(msg: "unknown FDE size relative encoding");
620	}
621
622	void EhFrameSection::writeTo(uint8_t *buf) {
623	// Write CIE and FDE records.
624	for (CieRecord *rec : cieRecords) {
625	size_t cieOffset = rec->cie->outputOff;
626	writeCieFde(buf: buf + cieOffset, d: rec->cie->data());
627
628	for (EhSectionPiece *fde : rec->fdes) {
629	size_t off = fde->outputOff;
630	writeCieFde(buf: buf + off, d: fde->data());
631
632	// FDE's second word should have the offset to an associated CIE.
633	// Write it.
634	write32(p: buf + off + 4, v: off + 4 - cieOffset);
635	}
636	}
637
638	// Apply relocations. .eh_frame section contents are not contiguous
639	// in the output buffer, but relocateAlloc() still works because
640	// getOffset() takes care of discontiguous section pieces.
641	for (EhInputSection *s : sections)
642	target->relocateAlloc(sec&: *s, buf);
643
644	if (getPartition().ehFrameHdr && getPartition().ehFrameHdr->getParent())
645	getPartition().ehFrameHdr->write();
646	}
647
648	GotSection::GotSection()
649	: SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS,
650	target->gotEntrySize, ".got") {
651	numEntries = target->gotHeaderEntriesNum;
652	}
653
654	void GotSection::addConstant(const Relocation &r) { relocations.push_back(Elt: r); }
655	void GotSection::addEntry(const Symbol &sym) {
656	assert(sym.auxIdx == symAux.size() - 1);
657	symAux.back().gotIdx = numEntries++;
658	}
659
660	bool GotSection::addTlsDescEntry(const Symbol &sym) {
661	assert(sym.auxIdx == symAux.size() - 1);
662	symAux.back().tlsDescIdx = numEntries;
663	numEntries += 2;
664	return true;
665	}
666
667	bool GotSection::addDynTlsEntry(const Symbol &sym) {
668	assert(sym.auxIdx == symAux.size() - 1);
669	symAux.back().tlsGdIdx = numEntries;
670	// Global Dynamic TLS entries take two GOT slots.
671	numEntries += 2;
672	return true;
673	}
674
675	// Reserves TLS entries for a TLS module ID and a TLS block offset.
676	// In total it takes two GOT slots.
677	bool GotSection::addTlsIndex() {
678	if (tlsIndexOff != uint32_t(-1))
679	return false;
680	tlsIndexOff = numEntries * config->wordsize;
681	numEntries += 2;
682	return true;
683	}
684
685	uint32_t GotSection::getTlsDescOffset(const Symbol &sym) const {
686	return sym.getTlsDescIdx() * config->wordsize;
687	}
688
689	uint64_t GotSection::getTlsDescAddr(const Symbol &sym) const {
690	return getVA() + getTlsDescOffset(sym);
691	}
692
693	uint64_t GotSection::getGlobalDynAddr(const Symbol &b) const {
694	return this->getVA() + b.getTlsGdIdx() * config->wordsize;
695	}
696
697	uint64_t GotSection::getGlobalDynOffset(const Symbol &b) const {
698	return b.getTlsGdIdx() * config->wordsize;
699	}
700
701	void GotSection::finalizeContents() {
702	if (config->emachine == EM_PPC64 &&
703	numEntries <= target->gotHeaderEntriesNum && !ElfSym::globalOffsetTable)
704	size = 0;
705	else
706	size = numEntries * config->wordsize;
707	}
708
709	bool GotSection::isNeeded() const {
710	// Needed if the GOT symbol is used or the number of entries is more than just
711	// the header. A GOT with just the header may not be needed.
712	return hasGotOffRel || numEntries > target->gotHeaderEntriesNum;
713	}
714
715	void GotSection::writeTo(uint8_t *buf) {
716	// On PPC64 .got may be needed but empty. Skip the write.
717	if (size == 0)
718	return;
719	target->writeGotHeader(buf);
720	target->relocateAlloc(sec&: *this, buf);
721	}
722
723	static uint64_t getMipsPageAddr(uint64_t addr) {
724	return (addr + 0x8000) & ~0xffff;
725	}
726
727	static uint64_t getMipsPageCount(uint64_t size) {
728	return (size + 0xfffe) / 0xffff + 1;
729	}
730
731	MipsGotSection::MipsGotSection()
732	: SyntheticSection(SHF_ALLOC | SHF_WRITE | SHF_MIPS_GPREL, SHT_PROGBITS, 16,
733	".got") {}
734
735	void MipsGotSection::addEntry(InputFile &file, Symbol &sym, int64_t addend,
736	RelExpr expr) {
737	FileGot &g = getGot(f&: file);
738	if (expr == R_MIPS_GOT_LOCAL_PAGE) {
739	if (const OutputSection *os = sym.getOutputSection())
740	g.pagesMap.insert(KV: {os, {}});
741	else
742	g.local16.insert(KV: {{nullptr, getMipsPageAddr(addr: sym.getVA(addend))}, 0});
743	} else if (sym.isTls())
744	g.tls.insert(KV: {&sym, 0});
745	else if (sym.isPreemptible && expr == R_ABS)
746	g.relocs.insert(KV: {&sym, 0});
747	else if (sym.isPreemptible)
748	g.global.insert(KV: {&sym, 0});
749	else if (expr == R_MIPS_GOT_OFF32)
750	g.local32.insert(KV: {{&sym, addend}, 0});
751	else
752	g.local16.insert(KV: {{&sym, addend}, 0});
753	}
754
755	void MipsGotSection::addDynTlsEntry(InputFile &file, Symbol &sym) {
756	getGot(f&: file).dynTlsSymbols.insert(KV: {&sym, 0});
757	}
758
759	void MipsGotSection::addTlsIndex(InputFile &file) {
760	getGot(f&: file).dynTlsSymbols.insert(KV: {nullptr, 0});
761	}
762
763	size_t MipsGotSection::FileGot::getEntriesNum() const {
764	return getPageEntriesNum() + local16.size() + global.size() + relocs.size() +
765	tls.size() + dynTlsSymbols.size() * 2;
766	}
767
768	size_t MipsGotSection::FileGot::getPageEntriesNum() const {
769	size_t num = 0;
770	for (const std::pair<const OutputSection *, FileGot::PageBlock> &p : pagesMap)
771	num += p.second.count;
772	return num;
773	}
774
775	size_t MipsGotSection::FileGot::getIndexedEntriesNum() const {
776	size_t count = getPageEntriesNum() + local16.size() + global.size();
777	// If there are relocation-only entries in the GOT, TLS entries
778	// are allocated after them. TLS entries should be addressable
779	// by 16-bit index so count both reloc-only and TLS entries.
780	if (!tls.empty() || !dynTlsSymbols.empty())
781	count += relocs.size() + tls.size() + dynTlsSymbols.size() * 2;
782	return count;
783	}
784
785	MipsGotSection::FileGot &MipsGotSection::getGot(InputFile &f) {
786	if (f.mipsGotIndex == uint32_t(-1)) {
787	gots.emplace_back();
788	gots.back().file = &f;
789	f.mipsGotIndex = gots.size() - 1;
790	}
791	return gots[f.mipsGotIndex];
792	}
793
794	uint64_t MipsGotSection::getPageEntryOffset(const InputFile *f,
795	const Symbol &sym,
796	int64_t addend) const {
797	const FileGot &g = gots[f->mipsGotIndex];
798	uint64_t index = 0;
799	if (const OutputSection *outSec = sym.getOutputSection()) {
800	uint64_t secAddr = getMipsPageAddr(addr: outSec->addr);
801	uint64_t symAddr = getMipsPageAddr(addr: sym.getVA(addend));
802	index = g.pagesMap.lookup(Key: outSec).firstIndex + (symAddr - secAddr) / 0xffff;
803	} else {
804	index = g.local16.lookup(Key: {nullptr, getMipsPageAddr(addr: sym.getVA(addend))});
805	}
806	return index * config->wordsize;
807	}
808
809	uint64_t MipsGotSection::getSymEntryOffset(const InputFile *f, const Symbol &s,
810	int64_t addend) const {
811	const FileGot &g = gots[f->mipsGotIndex];
812	Symbol *sym = const_cast<Symbol *>(&s);
813	if (sym->isTls())
814	return g.tls.lookup(Key: sym) * config->wordsize;
815	if (sym->isPreemptible)
816	return g.global.lookup(Key: sym) * config->wordsize;
817	return g.local16.lookup(Key: {sym, addend}) * config->wordsize;
818	}
819
820	uint64_t MipsGotSection::getTlsIndexOffset(const InputFile *f) const {
821	const FileGot &g = gots[f->mipsGotIndex];
822	return g.dynTlsSymbols.lookup(Key: nullptr) * config->wordsize;
823	}
824
825	uint64_t MipsGotSection::getGlobalDynOffset(const InputFile *f,
826	const Symbol &s) const {
827	const FileGot &g = gots[f->mipsGotIndex];
828	Symbol *sym = const_cast<Symbol *>(&s);
829	return g.dynTlsSymbols.lookup(Key: sym) * config->wordsize;
830	}
831
832	const Symbol *MipsGotSection::getFirstGlobalEntry() const {
833	if (gots.empty())
834	return nullptr;
835	const FileGot &primGot = gots.front();
836	if (!primGot.global.empty())
837	return primGot.global.front().first;
838	if (!primGot.relocs.empty())
839	return primGot.relocs.front().first;
840	return nullptr;
841	}
842
843	unsigned MipsGotSection::getLocalEntriesNum() const {
844	if (gots.empty())
845	return headerEntriesNum;
846	return headerEntriesNum + gots.front().getPageEntriesNum() +
847	gots.front().local16.size();
848	}
849
850	bool MipsGotSection::tryMergeGots(FileGot &dst, FileGot &src, bool isPrimary) {
851	FileGot tmp = dst;
852	set_union(S1&: tmp.pagesMap, S2: src.pagesMap);
853	set_union(S1&: tmp.local16, S2: src.local16);
854	set_union(S1&: tmp.global, S2: src.global);
855	set_union(S1&: tmp.relocs, S2: src.relocs);
856	set_union(S1&: tmp.tls, S2: src.tls);
857	set_union(S1&: tmp.dynTlsSymbols, S2: src.dynTlsSymbols);
858
859	size_t count = isPrimary ? headerEntriesNum : 0;
860	count += tmp.getIndexedEntriesNum();
861
862	if (count * config->wordsize > config->mipsGotSize)
863	return false;
864
865	std::swap(a&: tmp, b&: dst);
866	return true;
867	}
868
869	void MipsGotSection::finalizeContents() { updateAllocSize(); }
870
871	bool MipsGotSection::updateAllocSize() {
872	size = headerEntriesNum * config->wordsize;
873	for (const FileGot &g : gots)
874	size += g.getEntriesNum() * config->wordsize;
875	return false;
876	}
877
878	void MipsGotSection::build() {
879	if (gots.empty())
880	return;
881
882	std::vector<FileGot> mergedGots(1);
883
884	// For each GOT move non-preemptible symbols from the `Global`
885	// to `Local16` list. Preemptible symbol might become non-preemptible
886	// one if, for example, it gets a related copy relocation.
887	for (FileGot &got : gots) {
888	for (auto &p: got.global)
889	if (!p.first->isPreemptible)
890	got.local16.insert(KV: {{p.first, 0}, 0});
891	got.global.remove_if(Pred: [&](const std::pair<Symbol *, size_t> &p) {
892	return !p.first->isPreemptible;
893	});
894	}
895
896	// For each GOT remove "reloc-only" entry if there is "global"
897	// entry for the same symbol. And add local entries which indexed
898	// using 32-bit value at the end of 16-bit entries.
899	for (FileGot &got : gots) {
900	got.relocs.remove_if(Pred: [&](const std::pair<Symbol *, size_t> &p) {
901	return got.global.count(Key: p.first);
902	});
903	set_union(S1&: got.local16, S2: got.local32);
904	got.local32.clear();
905	}
906
907	// Evaluate number of "reloc-only" entries in the resulting GOT.
908	// To do that put all unique "reloc-only" and "global" entries
909	// from all GOTs to the future primary GOT.
910	FileGot *primGot = &mergedGots.front();
911	for (FileGot &got : gots) {
912	set_union(S1&: primGot->relocs, S2: got.global);
913	set_union(S1&: primGot->relocs, S2: got.relocs);
914	got.relocs.clear();
915	}
916
917	// Evaluate number of "page" entries in each GOT.
918	for (FileGot &got : gots) {
919	for (std::pair<const OutputSection *, FileGot::PageBlock> &p :
920	got.pagesMap) {
921	const OutputSection *os = p.first;
922	uint64_t secSize = 0;
923	for (SectionCommand *cmd : os->commands) {
924	if (auto *isd = dyn_cast<InputSectionDescription>(Val: cmd))
925	for (InputSection *isec : isd->sections) {
926	uint64_t off = alignToPowerOf2(Value: secSize, Align: isec->addralign);
927	secSize = off + isec->getSize();
928	}
929	}
930	p.second.count = getMipsPageCount(size: secSize);
931	}
932	}
933
934	// Merge GOTs. Try to join as much as possible GOTs but do not exceed
935	// maximum GOT size. At first, try to fill the primary GOT because
936	// the primary GOT can be accessed in the most effective way. If it
937	// is not possible, try to fill the last GOT in the list, and finally
938	// create a new GOT if both attempts failed.
939	for (FileGot &srcGot : gots) {
940	InputFile *file = srcGot.file;
941	if (tryMergeGots(dst&: mergedGots.front(), src&: srcGot, isPrimary: true)) {
942	file->mipsGotIndex = 0;
943	} else {
944	// If this is the first time we failed to merge with the primary GOT,
945	// MergedGots.back() will also be the primary GOT. We must make sure not
946	// to try to merge again with isPrimary=false, as otherwise, if the
947	// inputs are just right, we could allow the primary GOT to become 1 or 2
948	// words bigger due to ignoring the header size.
949	if (mergedGots.size() == 1 ||
950	!tryMergeGots(dst&: mergedGots.back(), src&: srcGot, isPrimary: false)) {
951	mergedGots.emplace_back();
952	std::swap(a&: mergedGots.back(), b&: srcGot);
953	}
954	file->mipsGotIndex = mergedGots.size() - 1;
955	}
956	}
957	std::swap(x&: gots, y&: mergedGots);
958
959	// Reduce number of "reloc-only" entries in the primary GOT
960	// by subtracting "global" entries in the primary GOT.
961	primGot = &gots.front();
962	primGot->relocs.remove_if(Pred: [&](const std::pair<Symbol *, size_t> &p) {
963	return primGot->global.count(Key: p.first);
964	});
965
966	// Calculate indexes for each GOT entry.
967	size_t index = headerEntriesNum;
968	for (FileGot &got : gots) {
969	got.startIndex = &got == primGot ? 0 : index;
970	for (std::pair<const OutputSection *, FileGot::PageBlock> &p :
971	got.pagesMap) {
972	// For each output section referenced by GOT page relocations calculate
973	// and save into pagesMap an upper bound of MIPS GOT entries required
974	// to store page addresses of local symbols. We assume the worst case -
975	// each 64kb page of the output section has at least one GOT relocation
976	// against it. And take in account the case when the section intersects
977	// page boundaries.
978	p.second.firstIndex = index;
979	index += p.second.count;
980	}
981	for (auto &p: got.local16)
982	p.second = index++;
983	for (auto &p: got.global)
984	p.second = index++;
985	for (auto &p: got.relocs)
986	p.second = index++;
987	for (auto &p: got.tls)
988	p.second = index++;
989	for (auto &p: got.dynTlsSymbols) {
990	p.second = index;
991	index += 2;
992	}
993	}
994
995	// Update SymbolAux::gotIdx field to use this
996	// value later in the `sortMipsSymbols` function.
997	for (auto &p : primGot->global) {
998	if (p.first->auxIdx == 0)
999	p.first->allocateAux();
1000	symAux.back().gotIdx = p.second;
1001	}
1002	for (auto &p : primGot->relocs) {
1003	if (p.first->auxIdx == 0)
1004	p.first->allocateAux();
1005	symAux.back().gotIdx = p.second;
1006	}
1007
1008	// Create dynamic relocations.
1009	for (FileGot &got : gots) {
1010	// Create dynamic relocations for TLS entries.
1011	for (std::pair<Symbol *, size_t> &p : got.tls) {
1012	Symbol *s = p.first;
1013	uint64_t offset = p.second * config->wordsize;
1014	// When building a shared library we still need a dynamic relocation
1015	// for the TP-relative offset as we don't know how much other data will
1016	// be allocated before us in the static TLS block.
1017	if (s->isPreemptible || config->shared)
1018	mainPart->relaDyn->addReloc(reloc: {target->tlsGotRel, this, offset,
1019	DynamicReloc::AgainstSymbolWithTargetVA,
1020	*s, 0, R_ABS});
1021	}
1022	for (std::pair<Symbol *, size_t> &p : got.dynTlsSymbols) {
1023	Symbol *s = p.first;
1024	uint64_t offset = p.second * config->wordsize;
1025	if (s == nullptr) {
1026	if (!config->shared)
1027	continue;
1028	mainPart->relaDyn->addReloc(reloc: {target->tlsModuleIndexRel, this, offset});
1029	} else {
1030	// When building a shared library we still need a dynamic relocation
1031	// for the module index. Therefore only checking for
1032	// S->isPreemptible is not sufficient (this happens e.g. for
1033	// thread-locals that have been marked as local through a linker script)
1034	if (!s->isPreemptible && !config->shared)
1035	continue;
1036	mainPart->relaDyn->addSymbolReloc(dynType: target->tlsModuleIndexRel, isec&: *this,
1037	offsetInSec: offset, sym&: *s);
1038	// However, we can skip writing the TLS offset reloc for non-preemptible
1039	// symbols since it is known even in shared libraries
1040	if (!s->isPreemptible)
1041	continue;
1042	offset += config->wordsize;
1043	mainPart->relaDyn->addSymbolReloc(dynType: target->tlsOffsetRel, isec&: *this, offsetInSec: offset,
1044	sym&: *s);
1045	}
1046	}
1047
1048	// Do not create dynamic relocations for non-TLS
1049	// entries in the primary GOT.
1050	if (&got == primGot)
1051	continue;
1052
1053	// Dynamic relocations for "global" entries.
1054	for (const std::pair<Symbol *, size_t> &p : got.global) {
1055	uint64_t offset = p.second * config->wordsize;
1056	mainPart->relaDyn->addSymbolReloc(dynType: target->relativeRel, isec&: *this, offsetInSec: offset,
1057	sym&: *p.first);
1058	}
1059	if (!config->isPic)
1060	continue;
1061	// Dynamic relocations for "local" entries in case of PIC.
1062	for (const std::pair<const OutputSection *, FileGot::PageBlock> &l :
1063	got.pagesMap) {
1064	size_t pageCount = l.second.count;
1065	for (size_t pi = 0; pi < pageCount; ++pi) {
1066	uint64_t offset = (l.second.firstIndex + pi) * config->wordsize;
1067	mainPart->relaDyn->addReloc(reloc: {target->relativeRel, this, offset, l.first,
1068	int64_t(pi * 0x10000)});
1069	}
1070	}
1071	for (const std::pair<GotEntry, size_t> &p : got.local16) {
1072	uint64_t offset = p.second * config->wordsize;
1073	mainPart->relaDyn->addReloc(reloc: {target->relativeRel, this, offset,
1074	DynamicReloc::AddendOnlyWithTargetVA,
1075	*p.first.first, p.first.second, R_ABS});
1076	}
1077	}
1078	}
1079
1080	bool MipsGotSection::isNeeded() const {
1081	// We add the .got section to the result for dynamic MIPS target because
1082	// its address and properties are mentioned in the .dynamic section.
1083	return !config->relocatable;
1084	}
1085
1086	uint64_t MipsGotSection::getGp(const InputFile *f) const {
1087	// For files without related GOT or files refer a primary GOT
1088	// returns "common" _gp value. For secondary GOTs calculate
1089	// individual _gp values.
1090	if (!f || f->mipsGotIndex == uint32_t(-1) || f->mipsGotIndex == 0)
1091	return ElfSym::mipsGp->getVA(addend: 0);
1092	return getVA() + gots[f->mipsGotIndex].startIndex * config->wordsize + 0x7ff0;
1093	}
1094
1095	void MipsGotSection::writeTo(uint8_t *buf) {
1096	// Set the MSB of the second GOT slot. This is not required by any
1097	// MIPS ABI documentation, though.
1098	//
1099	// There is a comment in glibc saying that "The MSB of got[1] of a
1100	// gnu object is set to identify gnu objects," and in GNU gold it
1101	// says "the second entry will be used by some runtime loaders".
1102	// But how this field is being used is unclear.
1103	//
1104	// We are not really willing to mimic other linkers behaviors
1105	// without understanding why they do that, but because all files
1106	// generated by GNU tools have this special GOT value, and because
1107	// we've been doing this for years, it is probably a safe bet to
1108	// keep doing this for now. We really need to revisit this to see
1109	// if we had to do this.
1110	writeUint(buf: buf + config->wordsize, val: (uint64_t)1 << (config->wordsize * 8 - 1));
1111	for (const FileGot &g : gots) {
1112	auto write = [&](size_t i, const Symbol *s, int64_t a) {
1113	uint64_t va = a;
1114	if (s)
1115	va = s->getVA(addend: a);
1116	writeUint(buf: buf + i * config->wordsize, val: va);
1117	};
1118	// Write 'page address' entries to the local part of the GOT.
1119	for (const std::pair<const OutputSection *, FileGot::PageBlock> &l :
1120	g.pagesMap) {
1121	size_t pageCount = l.second.count;
1122	uint64_t firstPageAddr = getMipsPageAddr(addr: l.first->addr);
1123	for (size_t pi = 0; pi < pageCount; ++pi)
1124	write(l.second.firstIndex + pi, nullptr, firstPageAddr + pi * 0x10000);
1125	}
1126	// Local, global, TLS, reloc-only entries.
1127	// If TLS entry has a corresponding dynamic relocations, leave it
1128	// initialized by zero. Write down adjusted TLS symbol's values otherwise.
1129	// To calculate the adjustments use offsets for thread-local storage.
1130	// http://web.archive.org/web/20190324223224/https://www.linux-mips.org/wiki/NPTL
1131	for (const std::pair<GotEntry, size_t> &p : g.local16)
1132	write(p.second, p.first.first, p.first.second);
1133	// Write VA to the primary GOT only. For secondary GOTs that
1134	// will be done by REL32 dynamic relocations.
1135	if (&g == &gots.front())
1136	for (const std::pair<Symbol *, size_t> &p : g.global)
1137	write(p.second, p.first, 0);
1138	for (const std::pair<Symbol *, size_t> &p : g.relocs)
1139	write(p.second, p.first, 0);
1140	for (const std::pair<Symbol *, size_t> &p : g.tls)
1141	write(p.second, p.first,
1142	p.first->isPreemptible || config->shared ? 0 : -0x7000);
1143	for (const std::pair<Symbol *, size_t> &p : g.dynTlsSymbols) {
1144	if (p.first == nullptr && !config->shared)
1145	write(p.second, nullptr, 1);
1146	else if (p.first && !p.first->isPreemptible) {
1147	// If we are emitting a shared library with relocations we mustn't write
1148	// anything to the GOT here. When using Elf_Rel relocations the value
1149	// one will be treated as an addend and will cause crashes at runtime
1150	if (!config->shared)
1151	write(p.second, nullptr, 1);
1152	write(p.second + 1, p.first, -0x8000);
1153	}
1154	}
1155	}
1156	}
1157
1158	// On PowerPC the .plt section is used to hold the table of function addresses
1159	// instead of the .got.plt, and the type is SHT_NOBITS similar to a .bss
1160	// section. I don't know why we have a BSS style type for the section but it is
1161	// consistent across both 64-bit PowerPC ABIs as well as the 32-bit PowerPC ABI.
1162	GotPltSection::GotPltSection()
1163	: SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, config->wordsize,
1164	".got.plt") {
1165	if (config->emachine == EM_PPC) {
1166	name = ".plt";
1167	} else if (config->emachine == EM_PPC64) {
1168	type = SHT_NOBITS;
1169	name = ".plt";
1170	}
1171	}
1172
1173	void GotPltSection::addEntry(Symbol &sym) {
1174	assert(sym.auxIdx == symAux.size() - 1 &&
1175	symAux.back().pltIdx == entries.size());
1176	entries.push_back(Elt: &sym);
1177	}
1178
1179	size_t GotPltSection::getSize() const {
1180	return (target->gotPltHeaderEntriesNum + entries.size()) *
1181	target->gotEntrySize;
1182	}
1183
1184	void GotPltSection::writeTo(uint8_t *buf) {
1185	target->writeGotPltHeader(buf);
1186	buf += target->gotPltHeaderEntriesNum * target->gotEntrySize;
1187	for (const Symbol *b : entries) {
1188	target->writeGotPlt(buf, s: *b);
1189	buf += target->gotEntrySize;
1190	}
1191	}
1192
1193	bool GotPltSection::isNeeded() const {
1194	// We need to emit GOTPLT even if it's empty if there's a relocation relative
1195	// to it.
1196	return !entries.empty() || hasGotPltOffRel;
1197	}
1198
1199	static StringRef getIgotPltName() {
1200	// On ARM the IgotPltSection is part of the GotSection.
1201	if (config->emachine == EM_ARM)
1202	return ".got";
1203
1204	// On PowerPC64 the GotPltSection is renamed to '.plt' so the IgotPltSection
1205	// needs to be named the same.
1206	if (config->emachine == EM_PPC64)
1207	return ".plt";
1208
1209	return ".got.plt";
1210	}
1211
1212	// On PowerPC64 the GotPltSection type is SHT_NOBITS so we have to follow suit
1213	// with the IgotPltSection.
1214	IgotPltSection::IgotPltSection()
1215	: SyntheticSection(SHF_ALLOC | SHF_WRITE,
1216	config->emachine == EM_PPC64 ? SHT_NOBITS : SHT_PROGBITS,
1217	target->gotEntrySize, getIgotPltName()) {}
1218
1219	void IgotPltSection::addEntry(Symbol &sym) {
1220	assert(symAux.back().pltIdx == entries.size());
1221	entries.push_back(Elt: &sym);
1222	}
1223
1224	size_t IgotPltSection::getSize() const {
1225	return entries.size() * target->gotEntrySize;
1226	}
1227
1228	void IgotPltSection::writeTo(uint8_t *buf) {
1229	for (const Symbol *b : entries) {
1230	target->writeIgotPlt(buf, s: *b);
1231	buf += target->gotEntrySize;
1232	}
1233	}
1234
1235	StringTableSection::StringTableSection(StringRef name, bool dynamic)
1236	: SyntheticSection(dynamic ? (uint64_t)SHF_ALLOC : 0, SHT_STRTAB, 1, name),
1237	dynamic(dynamic) {
1238	// ELF string tables start with a NUL byte.
1239	strings.push_back(Elt: "");
1240	stringMap.try_emplace(Key: CachedHashStringRef(""), Args: 0);
1241	size = 1;
1242	}
1243
1244	// Adds a string to the string table. If `hashIt` is true we hash and check for
1245	// duplicates. It is optional because the name of global symbols are already
1246	// uniqued and hashing them again has a big cost for a small value: uniquing
1247	// them with some other string that happens to be the same.
1248	unsigned StringTableSection::addString(StringRef s, bool hashIt) {
1249	if (hashIt) {
1250	auto r = stringMap.try_emplace(Key: CachedHashStringRef(s), Args&: size);
1251	if (!r.second)
1252	return r.first->second;
1253	}
1254	if (s.empty())
1255	return 0;
1256	unsigned ret = this->size;
1257	this->size = this->size + s.size() + 1;
1258	strings.push_back(Elt: s);
1259	return ret;
1260	}
1261
1262	void StringTableSection::writeTo(uint8_t *buf) {
1263	for (StringRef s : strings) {
1264	memcpy(dest: buf, src: s.data(), n: s.size());
1265	buf[s.size()] = '\0';
1266	buf += s.size() + 1;
1267	}
1268	}
1269
1270	// Returns the number of entries in .gnu.version_d: the number of
1271	// non-VER_NDX_LOCAL-non-VER_NDX_GLOBAL definitions, plus 1.
1272	// Note that we don't support vd_cnt > 1 yet.
1273	static unsigned getVerDefNum() {
1274	return namedVersionDefs().size() + 1;
1275	}
1276
1277	template <class ELFT>
1278	DynamicSection<ELFT>::DynamicSection()
1279	: SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_DYNAMIC, config->wordsize,
1280	".dynamic") {
1281	this->entsize = ELFT::Is64Bits ? 16 : 8;
1282
1283	// .dynamic section is not writable on MIPS and on Fuchsia OS
1284	// which passes -z rodynamic.
1285	// See "Special Section" in Chapter 4 in the following document:
1286	// ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
1287	if (config->emachine == EM_MIPS || config->zRodynamic)
1288	this->flags = SHF_ALLOC;
1289	}
1290
1291	// The output section .rela.dyn may include these synthetic sections:
1292	//
1293	// - part.relaDyn
1294	// - in.relaPlt: this is included if a linker script places .rela.plt inside
1295	// .rela.dyn
1296	//
1297	// DT_RELASZ is the total size of the included sections.
1298	static uint64_t addRelaSz(const RelocationBaseSection &relaDyn) {
1299	size_t size = relaDyn.getSize();
1300	if (in.relaPlt->getParent() == relaDyn.getParent())
1301	size += in.relaPlt->getSize();
1302	return size;
1303	}
1304
1305	// A Linker script may assign the RELA relocation sections to the same
1306	// output section. When this occurs we cannot just use the OutputSection
1307	// Size. Moreover the [DT_JMPREL, DT_JMPREL + DT_PLTRELSZ) is permitted to
1308	// overlap with the [DT_RELA, DT_RELA + DT_RELASZ).
1309	static uint64_t addPltRelSz() { return in.relaPlt->getSize(); }
1310
1311	// Add remaining entries to complete .dynamic contents.
1312	template <class ELFT>
1313	std::vector<std::pair<int32_t, uint64_t>>
1314	DynamicSection<ELFT>::computeContents() {
1315	elf::Partition &part = getPartition();
1316	bool isMain = part.name.empty();
1317	std::vector<std::pair<int32_t, uint64_t>> entries;
1318
1319	auto addInt = [&](int32_t tag, uint64_t val) {
1320	entries.emplace_back(args&: tag, args&: val);
1321	};
1322	auto addInSec = [&](int32_t tag, const InputSection &sec) {
1323	entries.emplace_back(args&: tag, args: sec.getVA());
1324	};
1325
1326	for (StringRef s : config->filterList)
1327	addInt(DT_FILTER, part.dynStrTab->addString(s));
1328	for (StringRef s : config->auxiliaryList)
1329	addInt(DT_AUXILIARY, part.dynStrTab->addString(s));
1330
1331	if (!config->rpath.empty())
1332	addInt(config->enableNewDtags ? DT_RUNPATH : DT_RPATH,
1333	part.dynStrTab->addString(s: config->rpath));
1334
1335	for (SharedFile *file : ctx.sharedFiles)
1336	if (file->isNeeded)
1337	addInt(DT_NEEDED, part.dynStrTab->addString(s: file->soName));
1338
1339	if (isMain) {
1340	if (!config->soName.empty())
1341	addInt(DT_SONAME, part.dynStrTab->addString(s: config->soName));
1342	} else {
1343	if (!config->soName.empty())
1344	addInt(DT_NEEDED, part.dynStrTab->addString(s: config->soName));
1345	addInt(DT_SONAME, part.dynStrTab->addString(s: part.name));
1346	}
1347
1348	// Set DT_FLAGS and DT_FLAGS_1.
1349	uint32_t dtFlags = 0;
1350	uint32_t dtFlags1 = 0;
1351	if (config->bsymbolic == BsymbolicKind::All)
1352	dtFlags |= DF_SYMBOLIC;
1353	if (config->zGlobal)
1354	dtFlags1 |= DF_1_GLOBAL;
1355	if (config->zInitfirst)
1356	dtFlags1 |= DF_1_INITFIRST;
1357	if (config->zInterpose)
1358	dtFlags1 |= DF_1_INTERPOSE;
1359	if (config->zNodefaultlib)
1360	dtFlags1 |= DF_1_NODEFLIB;
1361	if (config->zNodelete)
1362	dtFlags1 |= DF_1_NODELETE;
1363	if (config->zNodlopen)
1364	dtFlags1 |= DF_1_NOOPEN;
1365	if (config->pie)
1366	dtFlags1 |= DF_1_PIE;
1367	if (config->zNow) {
1368	dtFlags |= DF_BIND_NOW;
1369	dtFlags1 |= DF_1_NOW;
1370	}
1371	if (config->zOrigin) {
1372	dtFlags |= DF_ORIGIN;
1373	dtFlags1 |= DF_1_ORIGIN;
1374	}
1375	if (!config->zText)
1376	dtFlags |= DF_TEXTREL;
1377	if (ctx.hasTlsIe && config->shared)
1378	dtFlags |= DF_STATIC_TLS;
1379
1380	if (dtFlags)
1381	addInt(DT_FLAGS, dtFlags);
1382	if (dtFlags1)
1383	addInt(DT_FLAGS_1, dtFlags1);
1384
1385	// DT_DEBUG is a pointer to debug information used by debuggers at runtime. We
1386	// need it for each process, so we don't write it for DSOs. The loader writes
1387	// the pointer into this entry.
1388	//
1389	// DT_DEBUG is the only .dynamic entry that needs to be written to. Some
1390	// systems (currently only Fuchsia OS) provide other means to give the
1391	// debugger this information. Such systems may choose make .dynamic read-only.
1392	// If the target is such a system (used -z rodynamic) don't write DT_DEBUG.
1393	if (!config->shared && !config->relocatable && !config->zRodynamic)
1394	addInt(DT_DEBUG, 0);
1395
1396	if (part.relaDyn->isNeeded()) {
1397	addInSec(part.relaDyn->dynamicTag, *part.relaDyn);
1398	entries.emplace_back(args&: part.relaDyn->sizeDynamicTag,
1399	args: addRelaSz(relaDyn: *part.relaDyn));
1400
1401	bool isRela = config->isRela;
1402	addInt(isRela ? DT_RELAENT : DT_RELENT,
1403	isRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel));
1404
1405	// MIPS dynamic loader does not support RELCOUNT tag.
1406	// The problem is in the tight relation between dynamic
1407	// relocations and GOT. So do not emit this tag on MIPS.
1408	if (config->emachine != EM_MIPS) {
1409	size_t numRelativeRels = part.relaDyn->getRelativeRelocCount();
1410	if (config->zCombreloc && numRelativeRels)
1411	addInt(isRela ? DT_RELACOUNT : DT_RELCOUNT, numRelativeRels);
1412	}
1413	}
1414	if (part.relrDyn && part.relrDyn->getParent() &&
1415	!part.relrDyn->relocs.empty()) {
1416	addInSec(config->useAndroidRelrTags ? DT_ANDROID_RELR : DT_RELR,
1417	*part.relrDyn);
1418	addInt(config->useAndroidRelrTags ? DT_ANDROID_RELRSZ : DT_RELRSZ,
1419	part.relrDyn->getParent()->size);
1420	addInt(config->useAndroidRelrTags ? DT_ANDROID_RELRENT : DT_RELRENT,
1421	sizeof(Elf_Relr));
1422	}
1423	if (isMain && in.relaPlt->isNeeded()) {
1424	addInSec(DT_JMPREL, *in.relaPlt);
1425	entries.emplace_back(args: DT_PLTRELSZ, args: addPltRelSz());
1426	switch (config->emachine) {
1427	case EM_MIPS:
1428	addInSec(DT_MIPS_PLTGOT, *in.gotPlt);
1429	break;
1430	case EM_S390:
1431	addInSec(DT_PLTGOT, *in.got);
1432	break;
1433	case EM_SPARCV9:
1434	addInSec(DT_PLTGOT, *in.plt);
1435	break;
1436	case EM_AARCH64:
1437	if (llvm::find_if(in.relaPlt->relocs, [](const DynamicReloc &r) {
1438	return r.type == target->pltRel &&
1439	r.sym->stOther & STO_AARCH64_VARIANT_PCS;
1440	}) != in.relaPlt->relocs.end())
1441	addInt(DT_AARCH64_VARIANT_PCS, 0);
1442	addInSec(DT_PLTGOT, *in.gotPlt);
1443	break;
1444	case EM_RISCV:
1445	if (llvm::any_of(in.relaPlt->relocs, [](const DynamicReloc &r) {
1446	return r.type == target->pltRel &&
1447	(r.sym->stOther & STO_RISCV_VARIANT_CC);
1448	}))
1449	addInt(DT_RISCV_VARIANT_CC, 0);
1450	[[fallthrough]];
1451	default:
1452	addInSec(DT_PLTGOT, *in.gotPlt);
1453	break;
1454	}
1455	addInt(DT_PLTREL, config->isRela ? DT_RELA : DT_REL);
1456	}
1457
1458	if (config->emachine == EM_AARCH64) {
1459	if (config->andFeatures & GNU_PROPERTY_AARCH64_FEATURE_1_BTI)
1460	addInt(DT_AARCH64_BTI_PLT, 0);
1461	if (config->zPacPlt)
1462	addInt(DT_AARCH64_PAC_PLT, 0);
1463
1464	if (hasMemtag()) {
1465	addInt(DT_AARCH64_MEMTAG_MODE, config->androidMemtagMode == NT_MEMTAG_LEVEL_ASYNC);
1466	addInt(DT_AARCH64_MEMTAG_HEAP, config->androidMemtagHeap);
1467	addInt(DT_AARCH64_MEMTAG_STACK, config->androidMemtagStack);
1468	if (mainPart->memtagGlobalDescriptors->isNeeded()) {
1469	addInSec(DT_AARCH64_MEMTAG_GLOBALS, *mainPart->memtagGlobalDescriptors);
1470	addInt(DT_AARCH64_MEMTAG_GLOBALSSZ,
1471	mainPart->memtagGlobalDescriptors->getSize());
1472	}
1473	}
1474	}
1475
1476	addInSec(DT_SYMTAB, *part.dynSymTab);
1477	addInt(DT_SYMENT, sizeof(Elf_Sym));
1478	addInSec(DT_STRTAB, *part.dynStrTab);
1479	addInt(DT_STRSZ, part.dynStrTab->getSize());
1480	if (!config->zText)
1481	addInt(DT_TEXTREL, 0);
1482	if (part.gnuHashTab && part.gnuHashTab->getParent())
1483	addInSec(DT_GNU_HASH, *part.gnuHashTab);
1484	if (part.hashTab && part.hashTab->getParent())
1485	addInSec(DT_HASH, *part.hashTab);
1486
1487	if (isMain) {
1488	if (Out::preinitArray) {
1489	addInt(DT_PREINIT_ARRAY, Out::preinitArray->addr);
1490	addInt(DT_PREINIT_ARRAYSZ, Out::preinitArray->size);
1491	}
1492	if (Out::initArray) {
1493	addInt(DT_INIT_ARRAY, Out::initArray->addr);
1494	addInt(DT_INIT_ARRAYSZ, Out::initArray->size);
1495	}
1496	if (Out::finiArray) {
1497	addInt(DT_FINI_ARRAY, Out::finiArray->addr);
1498	addInt(DT_FINI_ARRAYSZ, Out::finiArray->size);
1499	}
1500
1501	if (Symbol *b = symtab.find(name: config->init))
1502	if (b->isDefined())
1503	addInt(DT_INIT, b->getVA());
1504	if (Symbol *b = symtab.find(name: config->fini))
1505	if (b->isDefined())
1506	addInt(DT_FINI, b->getVA());
1507	}
1508
1509	if (part.verSym && part.verSym->isNeeded())
1510	addInSec(DT_VERSYM, *part.verSym);
1511	if (part.verDef && part.verDef->isLive()) {
1512	addInSec(DT_VERDEF, *part.verDef);
1513	addInt(DT_VERDEFNUM, getVerDefNum());
1514	}
1515	if (part.verNeed && part.verNeed->isNeeded()) {
1516	addInSec(DT_VERNEED, *part.verNeed);
1517	unsigned needNum = 0;
1518	for (SharedFile *f : ctx.sharedFiles)
1519	if (!f->vernauxs.empty())
1520	++needNum;
1521	addInt(DT_VERNEEDNUM, needNum);
1522	}
1523
1524	if (config->emachine == EM_MIPS) {
1525	addInt(DT_MIPS_RLD_VERSION, 1);
1526	addInt(DT_MIPS_FLAGS, RHF_NOTPOT);
1527	addInt(DT_MIPS_BASE_ADDRESS, target->getImageBase());
1528	addInt(DT_MIPS_SYMTABNO, part.dynSymTab->getNumSymbols());
1529	addInt(DT_MIPS_LOCAL_GOTNO, in.mipsGot->getLocalEntriesNum());
1530
1531	if (const Symbol *b = in.mipsGot->getFirstGlobalEntry())
1532	addInt(DT_MIPS_GOTSYM, b->dynsymIndex);
1533	else
1534	addInt(DT_MIPS_GOTSYM, part.dynSymTab->getNumSymbols());
1535	addInSec(DT_PLTGOT, *in.mipsGot);
1536	if (in.mipsRldMap) {
1537	if (!config->pie)
1538	addInSec(DT_MIPS_RLD_MAP, *in.mipsRldMap);
1539	// Store the offset to the .rld_map section
1540	// relative to the address of the tag.
1541	addInt(DT_MIPS_RLD_MAP_REL,
1542	in.mipsRldMap->getVA() - (getVA() + entries.size() * entsize));
1543	}
1544	}
1545
1546	// DT_PPC_GOT indicates to glibc Secure PLT is used. If DT_PPC_GOT is absent,
1547	// glibc assumes the old-style BSS PLT layout which we don't support.
1548	if (config->emachine == EM_PPC)
1549	addInSec(DT_PPC_GOT, *in.got);
1550
1551	// Glink dynamic tag is required by the V2 abi if the plt section isn't empty.
1552	if (config->emachine == EM_PPC64 && in.plt->isNeeded()) {
1553	// The Glink tag points to 32 bytes before the first lazy symbol resolution
1554	// stub, which starts directly after the header.
1555	addInt(DT_PPC64_GLINK, in.plt->getVA() + target->pltHeaderSize - 32);
1556	}
1557
1558	if (config->emachine == EM_PPC64)
1559	addInt(DT_PPC64_OPT, getPPC64TargetInfo()->ppc64DynamicSectionOpt);
1560
1561	addInt(DT_NULL, 0);
1562	return entries;
1563	}
1564
1565	template <class ELFT> void DynamicSection<ELFT>::finalizeContents() {
1566	if (OutputSection *sec = getPartition().dynStrTab->getParent())
1567	getParent()->link = sec->sectionIndex;
1568	this->size = computeContents().size() * this->entsize;
1569	}
1570
1571	template <class ELFT> void DynamicSection<ELFT>::writeTo(uint8_t *buf) {
1572	auto *p = reinterpret_cast<Elf_Dyn *>(buf);
1573
1574	for (std::pair<int32_t, uint64_t> kv : computeContents()) {
1575	p->d_tag = kv.first;
1576	p->d_un.d_val = kv.second;
1577	++p;
1578	}
1579	}
1580
1581	uint64_t DynamicReloc::getOffset() const {
1582	return inputSec->getVA(offset: offsetInSec);
1583	}
1584
1585	int64_t DynamicReloc::computeAddend() const {
1586	switch (kind) {
1587	case AddendOnly:
1588	assert(sym == nullptr);
1589	return addend;
1590	case AgainstSymbol:
1591	assert(sym != nullptr);
1592	return addend;
1593	case AddendOnlyWithTargetVA:
1594	case AgainstSymbolWithTargetVA: {
1595	uint64_t ca = InputSection::getRelocTargetVA(File: inputSec->file, Type: type, A: addend,
1596	P: getOffset(), Sym: *sym, Expr: expr);
1597	return config->is64 ? ca : SignExtend64<32>(x: ca);
1598	}
1599	case MipsMultiGotPage:
1600	assert(sym == nullptr);
1601	return getMipsPageAddr(addr: outputSec->addr) + addend;
1602	}
1603	llvm_unreachable("Unknown DynamicReloc::Kind enum");
1604	}
1605
1606	uint32_t DynamicReloc::getSymIndex(SymbolTableBaseSection *symTab) const {
1607	if (!needsDynSymIndex())
1608	return 0;
1609
1610	size_t index = symTab->getSymbolIndex(sym: *sym);
1611	assert((index != 0 || (type != target->gotRel && type != target->pltRel) ||
1612	!mainPart->dynSymTab->getParent()) &&
1613	"GOT or PLT relocation must refer to symbol in dynamic symbol table");
1614	return index;
1615	}
1616
1617	RelocationBaseSection::RelocationBaseSection(StringRef name, uint32_t type,
1618	int32_t dynamicTag,
1619	int32_t sizeDynamicTag,
1620	bool combreloc,
1621	unsigned concurrency)
1622	: SyntheticSection(SHF_ALLOC, type, config->wordsize, name),
1623	dynamicTag(dynamicTag), sizeDynamicTag(sizeDynamicTag),
1624	relocsVec(concurrency), combreloc(combreloc) {}
1625
1626	void RelocationBaseSection::addSymbolReloc(
1627	RelType dynType, InputSectionBase &isec, uint64_t offsetInSec, Symbol &sym,
1628	int64_t addend, std::optional<RelType> addendRelType) {
1629	addReloc(kind: DynamicReloc::AgainstSymbol, dynType, sec&: isec, offsetInSec, sym, addend,
1630	expr: R_ADDEND, addendRelType: addendRelType ? *addendRelType : target->noneRel);
1631	}
1632
1633	void RelocationBaseSection::addAddendOnlyRelocIfNonPreemptible(
1634	RelType dynType, GotSection &sec, uint64_t offsetInSec, Symbol &sym,
1635	RelType addendRelType) {
1636	// No need to write an addend to the section for preemptible symbols.
1637	if (sym.isPreemptible)
1638	addReloc(reloc: {dynType, &sec, offsetInSec, DynamicReloc::AgainstSymbol, sym, 0,
1639	R_ABS});
1640	else
1641	addReloc(kind: DynamicReloc::AddendOnlyWithTargetVA, dynType, sec, offsetInSec,
1642	sym, addend: 0, expr: R_ABS, addendRelType);
1643	}
1644
1645	void RelocationBaseSection::mergeRels() {
1646	size_t newSize = relocs.size();
1647	for (const auto &v : relocsVec)
1648	newSize += v.size();
1649	relocs.reserve(N: newSize);
1650	for (const auto &v : relocsVec)
1651	llvm::append_range(C&: relocs, R: v);
1652	relocsVec.clear();
1653	}
1654
1655	void RelocationBaseSection::partitionRels() {
1656	if (!combreloc)
1657	return;
1658	const RelType relativeRel = target->relativeRel;
1659	numRelativeRelocs =
1660	std::stable_partition(first: relocs.begin(), last: relocs.end(),
1661	pred: [=](auto &r) { return r.type == relativeRel; }) -
1662	relocs.begin();
1663	}
1664
1665	void RelocationBaseSection::finalizeContents() {
1666	SymbolTableBaseSection *symTab = getPartition().dynSymTab.get();
1667
1668	// When linking glibc statically, .rel{,a}.plt contains R_*_IRELATIVE
1669	// relocations due to IFUNC (e.g. strcpy). sh_link will be set to 0 in that
1670	// case.
1671	if (symTab && symTab->getParent())
1672	getParent()->link = symTab->getParent()->sectionIndex;
1673	else
1674	getParent()->link = 0;
1675
1676	if (in.relaPlt.get() == this && in.gotPlt->getParent()) {
1677	getParent()->flags |= ELF::SHF_INFO_LINK;
1678	getParent()->info = in.gotPlt->getParent()->sectionIndex;
1679	}
1680	}
1681
1682	void DynamicReloc::computeRaw(SymbolTableBaseSection *symtab) {
1683	r_offset = getOffset();
1684	r_sym = getSymIndex(symTab: symtab);
1685	addend = computeAddend();
1686	kind = AddendOnly; // Catch errors
1687	}
1688
1689	void RelocationBaseSection::computeRels() {
1690	SymbolTableBaseSection *symTab = getPartition().dynSymTab.get();
1691	parallelForEach(R&: relocs,
1692	Fn: [symTab](DynamicReloc &rel) { rel.computeRaw(symtab: symTab); });
1693
1694	auto irelative = std::stable_partition(
1695	first: relocs.begin() + numRelativeRelocs, last: relocs.end(),
1696	pred: [t = target->iRelativeRel](auto &r) { return r.type != t; });
1697
1698	// Sort by (!IsRelative,SymIndex,r_offset). DT_REL[A]COUNT requires us to
1699	// place R_*_RELATIVE first. SymIndex is to improve locality, while r_offset
1700	// is to make results easier to read.
1701	if (combreloc) {
1702	auto nonRelative = relocs.begin() + numRelativeRelocs;
1703	parallelSort(Start: relocs.begin(), End: nonRelative,
1704	Comp: [&](auto &a, auto &b) { return a.r_offset < b.r_offset; });
1705	// Non-relative relocations are few, so don't bother with parallelSort.
1706	llvm::sort(Start: nonRelative, End: irelative, Comp: [&](auto &a, auto &b) {
1707	return std::tie(a.r_sym, a.r_offset) < std::tie(b.r_sym, b.r_offset);
1708	});
1709	}
1710	}
1711
1712	template <class ELFT>
1713	RelocationSection<ELFT>::RelocationSection(StringRef name, bool combreloc,
1714	unsigned concurrency)
1715	: RelocationBaseSection(name, config->isRela ? SHT_RELA : SHT_REL,
1716	config->isRela ? DT_RELA : DT_REL,
1717	config->isRela ? DT_RELASZ : DT_RELSZ, combreloc,
1718	concurrency) {
1719	this->entsize = config->isRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
1720	}
1721
1722	template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *buf) {
1723	computeRels();
1724	for (const DynamicReloc &rel : relocs) {
1725	auto *p = reinterpret_cast<Elf_Rela *>(buf);
1726	p->r_offset = rel.r_offset;
1727	p->setSymbolAndType(rel.r_sym, rel.type, config->isMips64EL);
1728	if (config->isRela)
1729	p->r_addend = rel.addend;
1730	buf += config->isRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
1731	}
1732	}
1733
1734	RelrBaseSection::RelrBaseSection(unsigned concurrency)
1735	: SyntheticSection(SHF_ALLOC,
1736	config->useAndroidRelrTags ? SHT_ANDROID_RELR : SHT_RELR,
1737	config->wordsize, ".relr.dyn"),
1738	relocsVec(concurrency) {}
1739
1740	void RelrBaseSection::mergeRels() {
1741	size_t newSize = relocs.size();
1742	for (const auto &v : relocsVec)
1743	newSize += v.size();
1744	relocs.reserve(N: newSize);
1745	for (const auto &v : relocsVec)
1746	llvm::append_range(C&: relocs, R: v);
1747	relocsVec.clear();
1748	}
1749
1750	template <class ELFT>
1751	AndroidPackedRelocationSection<ELFT>::AndroidPackedRelocationSection(
1752	StringRef name, unsigned concurrency)
1753	: RelocationBaseSection(
1754	name, config->isRela ? SHT_ANDROID_RELA : SHT_ANDROID_REL,
1755	config->isRela ? DT_ANDROID_RELA : DT_ANDROID_REL,
1756	config->isRela ? DT_ANDROID_RELASZ : DT_ANDROID_RELSZ,
1757	/*combreloc=*/false, concurrency) {
1758	this->entsize = 1;
1759	}
1760
1761	template <class ELFT>
1762	bool AndroidPackedRelocationSection<ELFT>::updateAllocSize() {
1763	// This function computes the contents of an Android-format packed relocation
1764	// section.
1765	//
1766	// This format compresses relocations by using relocation groups to factor out
1767	// fields that are common between relocations and storing deltas from previous
1768	// relocations in SLEB128 format (which has a short representation for small
1769	// numbers). A good example of a relocation type with common fields is
1770	// R_*_RELATIVE, which is normally used to represent function pointers in
1771	// vtables. In the REL format, each relative relocation has the same r_info
1772	// field, and is only different from other relative relocations in terms of
1773	// the r_offset field. By sorting relocations by offset, grouping them by
1774	// r_info and representing each relocation with only the delta from the
1775	// previous offset, each 8-byte relocation can be compressed to as little as 1
1776	// byte (or less with run-length encoding). This relocation packer was able to
1777	// reduce the size of the relocation section in an Android Chromium DSO from
1778	// 2,911,184 bytes to 174,693 bytes, or 6% of the original size.
1779	//
1780	// A relocation section consists of a header containing the literal bytes
1781	// 'APS2' followed by a sequence of SLEB128-encoded integers. The first two
1782	// elements are the total number of relocations in the section and an initial
1783	// r_offset value. The remaining elements define a sequence of relocation
1784	// groups. Each relocation group starts with a header consisting of the
1785	// following elements:
1786	//
1787	// - the number of relocations in the relocation group
1788	// - flags for the relocation group
1789	// - (if RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG is set) the r_offset delta
1790	// for each relocation in the group.
1791	// - (if RELOCATION_GROUPED_BY_INFO_FLAG is set) the value of the r_info
1792	// field for each relocation in the group.
1793	// - (if RELOCATION_GROUP_HAS_ADDEND_FLAG and
1794	// RELOCATION_GROUPED_BY_ADDEND_FLAG are set) the r_addend delta for
1795	// each relocation in the group.
1796	//
1797	// Following the relocation group header are descriptions of each of the
1798	// relocations in the group. They consist of the following elements:
1799	//
1800	// - (if RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG is not set) the r_offset
1801	// delta for this relocation.
1802	// - (if RELOCATION_GROUPED_BY_INFO_FLAG is not set) the value of the r_info
1803	// field for this relocation.
1804	// - (if RELOCATION_GROUP_HAS_ADDEND_FLAG is set and
1805	// RELOCATION_GROUPED_BY_ADDEND_FLAG is not set) the r_addend delta for
1806	// this relocation.
1807
1808	size_t oldSize = relocData.size();
1809
1810	relocData = {'A', 'P', 'S', '2'};
1811	raw_svector_ostream os(relocData);
1812	auto add = [&](int64_t v) { encodeSLEB128(Value: v, OS&: os); };
1813
1814	// The format header includes the number of relocations and the initial
1815	// offset (we set this to zero because the first relocation group will
1816	// perform the initial adjustment).
1817	add(relocs.size());
1818	add(0);
1819
1820	std::vector<Elf_Rela> relatives, nonRelatives;
1821
1822	for (const DynamicReloc &rel : relocs) {
1823	Elf_Rela r;
1824	r.r_offset = rel.getOffset();
1825	r.setSymbolAndType(rel.getSymIndex(symTab: getPartition().dynSymTab.get()),
1826	rel.type, false);
1827	r.r_addend = config->isRela ? rel.computeAddend() : 0;
1828
1829	if (r.getType(config->isMips64EL) == target->relativeRel)
1830	relatives.push_back(r);
1831	else
1832	nonRelatives.push_back(r);
1833	}
1834
1835	llvm::sort(relatives, [](const Elf_Rel &a, const Elf_Rel &b) {
1836	return a.r_offset < b.r_offset;
1837	});
1838
1839	// Try to find groups of relative relocations which are spaced one word
1840	// apart from one another. These generally correspond to vtable entries. The
1841	// format allows these groups to be encoded using a sort of run-length
1842	// encoding, but each group will cost 7 bytes in addition to the offset from
1843	// the previous group, so it is only profitable to do this for groups of
1844	// size 8 or larger.
1845	std::vector<Elf_Rela> ungroupedRelatives;
1846	std::vector<std::vector<Elf_Rela>> relativeGroups;
1847	for (auto i = relatives.begin(), e = relatives.end(); i != e;) {
1848	std::vector<Elf_Rela> group;
1849	do {
1850	group.push_back(*i++);
1851	} while (i != e && (i - 1)->r_offset + config->wordsize == i->r_offset);
1852
1853	if (group.size() < 8)
1854	ungroupedRelatives.insert(ungroupedRelatives.end(), group.begin(),
1855	group.end());
1856	else
1857	relativeGroups.emplace_back(std::move(group));
1858	}
1859
1860	// For non-relative relocations, we would like to:
1861	// 1. Have relocations with the same symbol offset to be consecutive, so
1862	// that the runtime linker can speed-up symbol lookup by implementing an
1863	// 1-entry cache.
1864	// 2. Group relocations by r_info to reduce the size of the relocation
1865	// section.
1866	// Since the symbol offset is the high bits in r_info, sorting by r_info
1867	// allows us to do both.
1868	//
1869	// For Rela, we also want to sort by r_addend when r_info is the same. This
1870	// enables us to group by r_addend as well.
1871	llvm::sort(nonRelatives, [](const Elf_Rela &a, const Elf_Rela &b) {
1872	if (a.r_info != b.r_info)
1873	return a.r_info < b.r_info;
1874	if (a.r_addend != b.r_addend)
1875	return a.r_addend < b.r_addend;
1876	return a.r_offset < b.r_offset;
1877	});
1878
1879	// Group relocations with the same r_info. Note that each group emits a group
1880	// header and that may make the relocation section larger. It is hard to
1881	// estimate the size of a group header as the encoded size of that varies
1882	// based on r_info. However, we can approximate this trade-off by the number
1883	// of values encoded. Each group header contains 3 values, and each relocation
1884	// in a group encodes one less value, as compared to when it is not grouped.
1885	// Therefore, we only group relocations if there are 3 or more of them with
1886	// the same r_info.
1887	//
1888	// For Rela, the addend for most non-relative relocations is zero, and thus we
1889	// can usually get a smaller relocation section if we group relocations with 0
1890	// addend as well.
1891	std::vector<Elf_Rela> ungroupedNonRelatives;
1892	std::vector<std::vector<Elf_Rela>> nonRelativeGroups;
1893	for (auto i = nonRelatives.begin(), e = nonRelatives.end(); i != e;) {
1894	auto j = i + 1;
1895	while (j != e && i->r_info == j->r_info &&
1896	(!config->isRela || i->r_addend == j->r_addend))
1897	++j;
1898	if (j - i < 3 || (config->isRela && i->r_addend != 0))
1899	ungroupedNonRelatives.insert(ungroupedNonRelatives.end(), i, j);
1900	else
1901	nonRelativeGroups.emplace_back(i, j);
1902	i = j;
1903	}
1904
1905	// Sort ungrouped relocations by offset to minimize the encoded length.
1906	llvm::sort(ungroupedNonRelatives, [](const Elf_Rela &a, const Elf_Rela &b) {
1907	return a.r_offset < b.r_offset;
1908	});
1909
1910	unsigned hasAddendIfRela =
1911	config->isRela ? RELOCATION_GROUP_HAS_ADDEND_FLAG : 0;
1912
1913	uint64_t offset = 0;
1914	uint64_t addend = 0;
1915
1916	// Emit the run-length encoding for the groups of adjacent relative
1917	// relocations. Each group is represented using two groups in the packed
1918	// format. The first is used to set the current offset to the start of the
1919	// group (and also encodes the first relocation), and the second encodes the
1920	// remaining relocations.
1921	for (std::vector<Elf_Rela> &g : relativeGroups) {
1922	// The first relocation in the group.
1923	add(1);
1924	add(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG |
1925	RELOCATION_GROUPED_BY_INFO_FLAG | hasAddendIfRela);
1926	add(g[0].r_offset - offset);
1927	add(target->relativeRel);
1928	if (config->isRela) {
1929	add(g[0].r_addend - addend);
1930	addend = g[0].r_addend;
1931	}
1932
1933	// The remaining relocations.
1934	add(g.size() - 1);
1935	add(RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG |
1936	RELOCATION_GROUPED_BY_INFO_FLAG | hasAddendIfRela);
1937	add(config->wordsize);
1938	add(target->relativeRel);
1939	if (config->isRela) {
1940	for (const auto &i : llvm::drop_begin(g)) {
1941	add(i.r_addend - addend);
1942	addend = i.r_addend;
1943	}
1944	}
1945
1946	offset = g.back().r_offset;
1947	}
1948
1949	// Now the ungrouped relatives.
1950	if (!ungroupedRelatives.empty()) {
1951	add(ungroupedRelatives.size());
1952	add(RELOCATION_GROUPED_BY_INFO_FLAG | hasAddendIfRela);
1953	add(target->relativeRel);
1954	for (Elf_Rela &r : ungroupedRelatives) {
1955	add(r.r_offset - offset);
1956	offset = r.r_offset;
1957	if (config->isRela) {
1958	add(r.r_addend - addend);
1959	addend = r.r_addend;
1960	}
1961	}
1962	}
1963
1964	// Grouped non-relatives.
1965	for (ArrayRef<Elf_Rela> g : nonRelativeGroups) {
1966	add(g.size());
1967	add(RELOCATION_GROUPED_BY_INFO_FLAG);
1968	add(g[0].r_info);
1969	for (const Elf_Rela &r : g) {
1970	add(r.r_offset - offset);
1971	offset = r.r_offset;
1972	}
1973	addend = 0;
1974	}
1975
1976	// Finally the ungrouped non-relative relocations.
1977	if (!ungroupedNonRelatives.empty()) {
1978	add(ungroupedNonRelatives.size());
1979	add(hasAddendIfRela);
1980	for (Elf_Rela &r : ungroupedNonRelatives) {
1981	add(r.r_offset - offset);
1982	offset = r.r_offset;
1983	add(r.r_info);
1984	if (config->isRela) {
1985	add(r.r_addend - addend);
1986	addend = r.r_addend;
1987	}
1988	}
1989	}
1990
1991	// Don't allow the section to shrink; otherwise the size of the section can
1992	// oscillate infinitely.
1993	if (relocData.size() < oldSize)
1994	relocData.append(NumInputs: oldSize - relocData.size(), Elt: 0);
1995
1996	// Returns whether the section size changed. We need to keep recomputing both
1997	// section layout and the contents of this section until the size converges
1998	// because changing this section's size can affect section layout, which in
1999	// turn can affect the sizes of the LEB-encoded integers stored in this
2000	// section.
2001	return relocData.size() != oldSize;
2002	}
2003
2004	template <class ELFT>
2005	RelrSection<ELFT>::RelrSection(unsigned concurrency)
2006	: RelrBaseSection(concurrency) {
2007	this->entsize = config->wordsize;
2008	}
2009
2010	template <class ELFT> bool RelrSection<ELFT>::updateAllocSize() {
2011	// This function computes the contents of an SHT_RELR packed relocation
2012	// section.
2013	//
2014	// Proposal for adding SHT_RELR sections to generic-abi is here:
2015	// https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg
2016	//
2017	// The encoded sequence of Elf64_Relr entries in a SHT_RELR section looks
2018	// like [ AAAAAAAA BBBBBBB1 BBBBBBB1 ... AAAAAAAA BBBBBB1 ... ]
2019	//
2020	// i.e. start with an address, followed by any number of bitmaps. The address
2021	// entry encodes 1 relocation. The subsequent bitmap entries encode up to 63
2022	// relocations each, at subsequent offsets following the last address entry.
2023	//
2024	// The bitmap entries must have 1 in the least significant bit. The assumption
2025	// here is that an address cannot have 1 in lsb. Odd addresses are not
2026	// supported.
2027	//
2028	// Excluding the least significant bit in the bitmap, each non-zero bit in
2029	// the bitmap represents a relocation to be applied to a corresponding machine
2030	// word that follows the base address word. The second least significant bit
2031	// represents the machine word immediately following the initial address, and
2032	// each bit that follows represents the next word, in linear order. As such,
2033	// a single bitmap can encode up to 31 relocations in a 32-bit object, and
2034	// 63 relocations in a 64-bit object.
2035	//
2036	// This encoding has a couple of interesting properties:
2037	// 1. Looking at any entry, it is clear whether it's an address or a bitmap:
2038	// even means address, odd means bitmap.
2039	// 2. Just a simple list of addresses is a valid encoding.
2040
2041	size_t oldSize = relrRelocs.size();
2042	relrRelocs.clear();
2043
2044	// Same as Config->Wordsize but faster because this is a compile-time
2045	// constant.
2046	const size_t wordsize = sizeof(typename ELFT::uint);
2047
2048	// Number of bits to use for the relocation offsets bitmap.
2049	// Must be either 63 or 31.
2050	const size_t nBits = wordsize * 8 - 1;
2051
2052	// Get offsets for all relative relocations and sort them.
2053	std::unique_ptr<uint64_t[]> offsets(new uint64_t[relocs.size()]);
2054	for (auto [i, r] : llvm::enumerate(relocs))
2055	offsets[i] = r.getOffset();
2056	llvm::sort(offsets.get(), offsets.get() + relocs.size());
2057
2058	// For each leading relocation, find following ones that can be folded
2059	// as a bitmap and fold them.
2060	for (size_t i = 0, e = relocs.size(); i != e;) {
2061	// Add a leading relocation.
2062	relrRelocs.push_back(Elf_Relr(offsets[i]));
2063	uint64_t base = offsets[i] + wordsize;
2064	++i;
2065
2066	// Find foldable relocations to construct bitmaps.
2067	for (;;) {
2068	uint64_t bitmap = 0;
2069	for (; i != e; ++i) {
2070	uint64_t d = offsets[i] - base;
2071	if (d >= nBits * wordsize || d % wordsize)
2072	break;
2073	bitmap |= uint64_t(1) << (d / wordsize);
2074	}
2075	if (!bitmap)
2076	break;
2077	relrRelocs.push_back(Elf_Relr((bitmap << 1) | 1));
2078	base += nBits * wordsize;
2079	}
2080	}
2081
2082	// Don't allow the section to shrink; otherwise the size of the section can
2083	// oscillate infinitely. Trailing 1s do not decode to more relocations.
2084	if (relrRelocs.size() < oldSize) {
2085	log(msg: ".relr.dyn needs " + Twine(oldSize - relrRelocs.size()) +
2086	" padding word(s)");
2087	relrRelocs.resize(oldSize, Elf_Relr(1));
2088	}
2089
2090	return relrRelocs.size() != oldSize;
2091	}
2092
2093	SymbolTableBaseSection::SymbolTableBaseSection(StringTableSection &strTabSec)
2094	: SyntheticSection(strTabSec.isDynamic() ? (uint64_t)SHF_ALLOC : 0,
2095	strTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,
2096	config->wordsize,
2097	strTabSec.isDynamic() ? ".dynsym" : ".symtab"),
2098	strTabSec(strTabSec) {}
2099
2100	// Orders symbols according to their positions in the GOT,
2101	// in compliance with MIPS ABI rules.
2102	// See "Global Offset Table" in Chapter 5 in the following document
2103	// for detailed description:
2104	// ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
2105	static bool sortMipsSymbols(const SymbolTableEntry &l,
2106	const SymbolTableEntry &r) {
2107	// Sort entries related to non-local preemptible symbols by GOT indexes.
2108	// All other entries go to the beginning of a dynsym in arbitrary order.
2109	if (l.sym->isInGot() && r.sym->isInGot())
2110	return l.sym->getGotIdx() < r.sym->getGotIdx();
2111	if (!l.sym->isInGot() && !r.sym->isInGot())
2112	return false;
2113	return !l.sym->isInGot();
2114	}
2115
2116	void SymbolTableBaseSection::finalizeContents() {
2117	if (OutputSection *sec = strTabSec.getParent())
2118	getParent()->link = sec->sectionIndex;
2119
2120	if (this->type != SHT_DYNSYM) {
2121	sortSymTabSymbols();
2122	return;
2123	}
2124
2125	// If it is a .dynsym, there should be no local symbols, but we need
2126	// to do a few things for the dynamic linker.
2127
2128	// Section's Info field has the index of the first non-local symbol.
2129	// Because the first symbol entry is a null entry, 1 is the first.
2130	getParent()->info = 1;
2131
2132	if (getPartition().gnuHashTab) {
2133	// NB: It also sorts Symbols to meet the GNU hash table requirements.
2134	getPartition().gnuHashTab->addSymbols(symbols);
2135	} else if (config->emachine == EM_MIPS) {
2136	llvm::stable_sort(Range&: symbols, C: sortMipsSymbols);
2137	}
2138
2139	// Only the main partition's dynsym indexes are stored in the symbols
2140	// themselves. All other partitions use a lookup table.
2141	if (this == mainPart->dynSymTab.get()) {
2142	size_t i = 0;
2143	for (const SymbolTableEntry &s : symbols)
2144	s.sym->dynsymIndex = ++i;
2145	}
2146	}
2147
2148	// The ELF spec requires that all local symbols precede global symbols, so we
2149	// sort symbol entries in this function. (For .dynsym, we don't do that because
2150	// symbols for dynamic linking are inherently all globals.)
2151	//
2152	// Aside from above, we put local symbols in groups starting with the STT_FILE
2153	// symbol. That is convenient for purpose of identifying where are local symbols
2154	// coming from.
2155	void SymbolTableBaseSection::sortSymTabSymbols() {
2156	// Move all local symbols before global symbols.
2157	auto e = std::stable_partition(
2158	first: symbols.begin(), last: symbols.end(),
2159	pred: [](const SymbolTableEntry &s) { return s.sym->isLocal(); });
2160	size_t numLocals = e - symbols.begin();
2161	getParent()->info = numLocals + 1;
2162
2163	// We want to group the local symbols by file. For that we rebuild the local
2164	// part of the symbols vector. We do not need to care about the STT_FILE
2165	// symbols, they are already naturally placed first in each group. That
2166	// happens because STT_FILE is always the first symbol in the object and hence
2167	// precede all other local symbols we add for a file.
2168	MapVector<InputFile *, SmallVector<SymbolTableEntry, 0>> arr;
2169	for (const SymbolTableEntry &s : llvm::make_range(x: symbols.begin(), y: e))
2170	arr[s.sym->file].push_back(Elt: s);
2171
2172	auto i = symbols.begin();
2173	for (auto &p : arr)
2174	for (SymbolTableEntry &entry : p.second)
2175	*i++ = entry;
2176	}
2177
2178	void SymbolTableBaseSection::addSymbol(Symbol *b) {
2179	// Adding a local symbol to a .dynsym is a bug.
2180	assert(this->type != SHT_DYNSYM || !b->isLocal());
2181	symbols.push_back(Elt: {.sym: b, .strTabOffset: strTabSec.addString(s: b->getName(), hashIt: false)});
2182	}
2183
2184	size_t SymbolTableBaseSection::getSymbolIndex(const Symbol &sym) {
2185	if (this == mainPart->dynSymTab.get())
2186	return sym.dynsymIndex;
2187
2188	// Initializes symbol lookup tables lazily. This is used only for -r,
2189	// --emit-relocs and dynsyms in partitions other than the main one.
2190	llvm::call_once(flag&: onceFlag, F: [&] {
2191	symbolIndexMap.reserve(NumEntries: symbols.size());
2192	size_t i = 0;
2193	for (const SymbolTableEntry &e : symbols) {
2194	if (e.sym->type == STT_SECTION)
2195	sectionIndexMap[e.sym->getOutputSection()] = ++i;
2196	else
2197	symbolIndexMap[e.sym] = ++i;
2198	}
2199	});
2200
2201	// Section symbols are mapped based on their output sections
2202	// to maintain their semantics.
2203	if (sym.type == STT_SECTION)
2204	return sectionIndexMap.lookup(Val: sym.getOutputSection());
2205	return symbolIndexMap.lookup(Val: &sym);
2206	}
2207
2208	template <class ELFT>
2209	SymbolTableSection<ELFT>::SymbolTableSection(StringTableSection &strTabSec)
2210	: SymbolTableBaseSection(strTabSec) {
2211	this->entsize = sizeof(Elf_Sym);
2212	}
2213
2214	static BssSection *getCommonSec(Symbol *sym) {
2215	if (config->relocatable)
2216	if (auto *d = dyn_cast<Defined>(Val: sym))
2217	return dyn_cast_or_null<BssSection>(Val: d->section);
2218	return nullptr;
2219	}
2220
2221	static uint32_t getSymSectionIndex(Symbol *sym) {
2222	assert(!(sym->hasFlag(NEEDS_COPY) && sym->isObject()));
2223	if (!isa<Defined>(Val: sym) || sym->hasFlag(bit: NEEDS_COPY))
2224	return SHN_UNDEF;
2225	if (const OutputSection *os = sym->getOutputSection())
2226	return os->sectionIndex >= SHN_LORESERVE ? (uint32_t)SHN_XINDEX
2227	: os->sectionIndex;
2228	return SHN_ABS;
2229	}
2230
2231	// Write the internal symbol table contents to the output symbol table.
2232	template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *buf) {
2233	// The first entry is a null entry as per the ELF spec.
2234	buf += sizeof(Elf_Sym);
2235
2236	auto *eSym = reinterpret_cast<Elf_Sym *>(buf);
2237
2238	for (SymbolTableEntry &ent : symbols) {
2239	Symbol *sym = ent.sym;
2240	bool isDefinedHere = type == SHT_SYMTAB || sym->partition == partition;
2241
2242	// Set st_name, st_info and st_other.
2243	eSym->st_name = ent.strTabOffset;
2244	eSym->setBindingAndType(sym->binding, sym->type);
2245	eSym->st_other = sym->stOther;
2246
2247	if (BssSection *commonSec = getCommonSec(sym)) {
2248	// When -r is specified, a COMMON symbol is not allocated. Its st_shndx
2249	// holds SHN_COMMON and st_value holds the alignment.
2250	eSym->st_shndx = SHN_COMMON;
2251	eSym->st_value = commonSec->addralign;
2252	eSym->st_size = cast<Defined>(Val: sym)->size;
2253	} else {
2254	const uint32_t shndx = getSymSectionIndex(sym);
2255	if (isDefinedHere) {
2256	eSym->st_shndx = shndx;
2257	eSym->st_value = sym->getVA();
2258	// Copy symbol size if it is a defined symbol. st_size is not
2259	// significant for undefined symbols, so whether copying it or not is up
2260	// to us if that's the case. We'll leave it as zero because by not
2261	// setting a value, we can get the exact same outputs for two sets of
2262	// input files that differ only in undefined symbol size in DSOs.
2263	eSym->st_size = shndx != SHN_UNDEF ? cast<Defined>(Val: sym)->size : 0;
2264	} else {
2265	eSym->st_shndx = 0;
2266	eSym->st_value = 0;
2267	eSym->st_size = 0;
2268	}
2269	}
2270
2271	++eSym;
2272	}
2273
2274	// On MIPS we need to mark symbol which has a PLT entry and requires
2275	// pointer equality by STO_MIPS_PLT flag. That is necessary to help
2276	// dynamic linker distinguish such symbols and MIPS lazy-binding stubs.
2277	// https://sourceware.org/ml/binutils/2008-07/txt00000.txt
2278	if (config->emachine == EM_MIPS) {
2279	auto *eSym = reinterpret_cast<Elf_Sym *>(buf);
2280
2281	for (SymbolTableEntry &ent : symbols) {
2282	Symbol *sym = ent.sym;
2283	if (sym->isInPlt() && sym->hasFlag(bit: NEEDS_COPY))
2284	eSym->st_other |= STO_MIPS_PLT;
2285	if (isMicroMips()) {
2286	// We already set the less-significant bit for symbols
2287	// marked by the `STO_MIPS_MICROMIPS` flag and for microMIPS PLT
2288	// records. That allows us to distinguish such symbols in
2289	// the `MIPS<ELFT>::relocate()` routine. Now we should
2290	// clear that bit for non-dynamic symbol table, so tools
2291	// like `objdump` will be able to deal with a correct
2292	// symbol position.
2293	if (sym->isDefined() &&
2294	((sym->stOther & STO_MIPS_MICROMIPS) || sym->hasFlag(bit: NEEDS_COPY))) {
2295	if (!strTabSec.isDynamic())
2296	eSym->st_value &= ~1;
2297	eSym->st_other |= STO_MIPS_MICROMIPS;
2298	}
2299	}
2300	if (config->relocatable)
2301	if (auto *d = dyn_cast<Defined>(Val: sym))
2302	if (isMipsPIC<ELFT>(d))
2303	eSym->st_other |= STO_MIPS_PIC;
2304	++eSym;
2305	}
2306	}
2307	}
2308
2309	SymtabShndxSection::SymtabShndxSection()
2310	: SyntheticSection(0, SHT_SYMTAB_SHNDX, 4, ".symtab_shndx") {
2311	this->entsize = 4;
2312	}
2313
2314	void SymtabShndxSection::writeTo(uint8_t *buf) {
2315	// We write an array of 32 bit values, where each value has 1:1 association
2316	// with an entry in .symtab. If the corresponding entry contains SHN_XINDEX,
2317	// we need to write actual index, otherwise, we must write SHN_UNDEF(0).
2318	buf += 4; // Ignore .symtab[0] entry.
2319	for (const SymbolTableEntry &entry : in.symTab->getSymbols()) {
2320	if (!getCommonSec(sym: entry.sym) && getSymSectionIndex(sym: entry.sym) == SHN_XINDEX)
2321	write32(p: buf, v: entry.sym->getOutputSection()->sectionIndex);
2322	buf += 4;
2323	}
2324	}
2325
2326	bool SymtabShndxSection::isNeeded() const {
2327	// SHT_SYMTAB can hold symbols with section indices values up to
2328	// SHN_LORESERVE. If we need more, we want to use extension SHT_SYMTAB_SHNDX
2329	// section. Problem is that we reveal the final section indices a bit too
2330	// late, and we do not know them here. For simplicity, we just always create
2331	// a .symtab_shndx section when the amount of output sections is huge.
2332	size_t size = 0;
2333	for (SectionCommand *cmd : script->sectionCommands)
2334	if (isa<OutputDesc>(Val: cmd))
2335	++size;
2336	return size >= SHN_LORESERVE;
2337	}
2338
2339	void SymtabShndxSection::finalizeContents() {
2340	getParent()->link = in.symTab->getParent()->sectionIndex;
2341	}
2342
2343	size_t SymtabShndxSection::getSize() const {
2344	return in.symTab->getNumSymbols() * 4;
2345	}
2346
2347	// .hash and .gnu.hash sections contain on-disk hash tables that map
2348	// symbol names to their dynamic symbol table indices. Their purpose
2349	// is to help the dynamic linker resolve symbols quickly. If ELF files
2350	// don't have them, the dynamic linker has to do linear search on all
2351	// dynamic symbols, which makes programs slower. Therefore, a .hash
2352	// section is added to a DSO by default.
2353	//
2354	// The Unix semantics of resolving dynamic symbols is somewhat expensive.
2355	// Each ELF file has a list of DSOs that the ELF file depends on and a
2356	// list of dynamic symbols that need to be resolved from any of the
2357	// DSOs. That means resolving all dynamic symbols takes O(m)*O(n)
2358	// where m is the number of DSOs and n is the number of dynamic
2359	// symbols. For modern large programs, both m and n are large. So
2360	// making each step faster by using hash tables substantially
2361	// improves time to load programs.
2362	//
2363	// (Note that this is not the only way to design the shared library.
2364	// For instance, the Windows DLL takes a different approach. On
2365	// Windows, each dynamic symbol has a name of DLL from which the symbol
2366	// has to be resolved. That makes the cost of symbol resolution O(n).
2367	// This disables some hacky techniques you can use on Unix such as
2368	// LD_PRELOAD, but this is arguably better semantics than the Unix ones.)
2369	//
2370	// Due to historical reasons, we have two different hash tables, .hash
2371	// and .gnu.hash. They are for the same purpose, and .gnu.hash is a new
2372	// and better version of .hash. .hash is just an on-disk hash table, but
2373	// .gnu.hash has a bloom filter in addition to a hash table to skip
2374	// DSOs very quickly. If you are sure that your dynamic linker knows
2375	// about .gnu.hash, you want to specify --hash-style=gnu. Otherwise, a
2376	// safe bet is to specify --hash-style=both for backward compatibility.
2377	GnuHashTableSection::GnuHashTableSection()
2378	: SyntheticSection(SHF_ALLOC, SHT_GNU_HASH, config->wordsize, ".gnu.hash") {
2379	}
2380
2381	void GnuHashTableSection::finalizeContents() {
2382	if (OutputSection *sec = getPartition().dynSymTab->getParent())
2383	getParent()->link = sec->sectionIndex;
2384
2385	// Computes bloom filter size in word size. We want to allocate 12
2386	// bits for each symbol. It must be a power of two.
2387	if (symbols.empty()) {
2388	maskWords = 1;
2389	} else {
2390	uint64_t numBits = symbols.size() * 12;
2391	maskWords = NextPowerOf2(A: numBits / (config->wordsize * 8));
2392	}
2393
2394	size = 16; // Header
2395	size += config->wordsize * maskWords; // Bloom filter
2396	size += nBuckets * 4; // Hash buckets
2397	size += symbols.size() * 4; // Hash values
2398	}
2399
2400	void GnuHashTableSection::writeTo(uint8_t *buf) {
2401	// Write a header.
2402	write32(p: buf, v: nBuckets);
2403	write32(p: buf + 4, v: getPartition().dynSymTab->getNumSymbols() - symbols.size());
2404	write32(p: buf + 8, v: maskWords);
2405	write32(p: buf + 12, v: Shift2);
2406	buf += 16;
2407
2408	// Write the 2-bit bloom filter.
2409	const unsigned c = config->is64 ? 64 : 32;
2410	for (const Entry &sym : symbols) {
2411	// When C = 64, we choose a word with bits [6:...] and set 1 to two bits in
2412	// the word using bits [0:5] and [26:31].
2413	size_t i = (sym.hash / c) & (maskWords - 1);
2414	uint64_t val = readUint(buf: buf + i * config->wordsize);
2415	val |= uint64_t(1) << (sym.hash % c);
2416	val |= uint64_t(1) << ((sym.hash >> Shift2) % c);
2417	writeUint(buf: buf + i * config->wordsize, val);
2418	}
2419	buf += config->wordsize * maskWords;
2420
2421	// Write the hash table.
2422	uint32_t *buckets = reinterpret_cast<uint32_t *>(buf);
2423	uint32_t oldBucket = -1;
2424	uint32_t *values = buckets + nBuckets;
2425	for (auto i = symbols.begin(), e = symbols.end(); i != e; ++i) {
2426	// Write a hash value. It represents a sequence of chains that share the
2427	// same hash modulo value. The last element of each chain is terminated by
2428	// LSB 1.
2429	uint32_t hash = i->hash;
2430	bool isLastInChain = (i + 1) == e || i->bucketIdx != (i + 1)->bucketIdx;
2431	hash = isLastInChain ? hash | 1 : hash & ~1;
2432	write32(p: values++, v: hash);
2433
2434	if (i->bucketIdx == oldBucket)
2435	continue;
2436	// Write a hash bucket. Hash buckets contain indices in the following hash
2437	// value table.
2438	write32(p: buckets + i->bucketIdx,
2439	v: getPartition().dynSymTab->getSymbolIndex(sym: *i->sym));
2440	oldBucket = i->bucketIdx;
2441	}
2442	}
2443
2444	// Add symbols to this symbol hash table. Note that this function
2445	// destructively sort a given vector -- which is needed because
2446	// GNU-style hash table places some sorting requirements.
2447	void GnuHashTableSection::addSymbols(SmallVectorImpl<SymbolTableEntry> &v) {
2448	// We cannot use 'auto' for Mid because GCC 6.1 cannot deduce
2449	// its type correctly.
2450	auto mid =
2451	std::stable_partition(first: v.begin(), last: v.end(), pred: [&](const SymbolTableEntry &s) {
2452	return !s.sym->isDefined() || s.sym->partition != partition;
2453	});
2454
2455	// We chose load factor 4 for the on-disk hash table. For each hash
2456	// collision, the dynamic linker will compare a uint32_t hash value.
2457	// Since the integer comparison is quite fast, we believe we can
2458	// make the load factor even larger. 4 is just a conservative choice.
2459	//
2460	// Note that we don't want to create a zero-sized hash table because
2461	// Android loader as of 2018 doesn't like a .gnu.hash containing such
2462	// table. If that's the case, we create a hash table with one unused
2463	// dummy slot.
2464	nBuckets = std::max<size_t>(a: (v.end() - mid) / 4, b: 1);
2465
2466	if (mid == v.end())
2467	return;
2468
2469	for (SymbolTableEntry &ent : llvm::make_range(x: mid, y: v.end())) {
2470	Symbol *b = ent.sym;
2471	uint32_t hash = hashGnu(Name: b->getName());
2472	uint32_t bucketIdx = hash % nBuckets;
2473	symbols.push_back(Elt: {.sym: b, .strTabOffset: ent.strTabOffset, .hash: hash, .bucketIdx: bucketIdx});
2474	}
2475
2476	llvm::sort(C&: symbols, Comp: [](const Entry &l, const Entry &r) {
2477	return std::tie(args: l.bucketIdx, args: l.strTabOffset) <
2478	std::tie(args: r.bucketIdx, args: r.strTabOffset);
2479	});
2480
2481	v.erase(CS: mid, CE: v.end());
2482	for (const Entry &ent : symbols)
2483	v.push_back(Elt: {.sym: ent.sym, .strTabOffset: ent.strTabOffset});
2484	}
2485
2486	HashTableSection::HashTableSection()
2487	: SyntheticSection(SHF_ALLOC, SHT_HASH, 4, ".hash") {
2488	this->entsize = 4;
2489	}
2490
2491	void HashTableSection::finalizeContents() {
2492	SymbolTableBaseSection *symTab = getPartition().dynSymTab.get();
2493
2494	if (OutputSection *sec = symTab->getParent())
2495	getParent()->link = sec->sectionIndex;
2496
2497	unsigned numEntries = 2; // nbucket and nchain.
2498	numEntries += symTab->getNumSymbols(); // The chain entries.
2499
2500	// Create as many buckets as there are symbols.
2501	numEntries += symTab->getNumSymbols();
2502	this->size = numEntries * 4;
2503	}
2504
2505	void HashTableSection::writeTo(uint8_t *buf) {
2506	SymbolTableBaseSection *symTab = getPartition().dynSymTab.get();
2507	unsigned numSymbols = symTab->getNumSymbols();
2508
2509	uint32_t *p = reinterpret_cast<uint32_t *>(buf);
2510	write32(p: p++, v: numSymbols); // nbucket
2511	write32(p: p++, v: numSymbols); // nchain
2512
2513	uint32_t *buckets = p;
2514	uint32_t *chains = p + numSymbols;
2515
2516	for (const SymbolTableEntry &s : symTab->getSymbols()) {
2517	Symbol *sym = s.sym;
2518	StringRef name = sym->getName();
2519	unsigned i = sym->dynsymIndex;
2520	uint32_t hash = hashSysV(SymbolName: name) % numSymbols;
2521	chains[i] = buckets[hash];
2522	write32(p: buckets + hash, v: i);
2523	}
2524	}
2525
2526	PltSection::PltSection()
2527	: SyntheticSection(SHF_ALLOC | SHF_EXECINSTR, SHT_PROGBITS, 16, ".plt"),
2528	headerSize(target->pltHeaderSize) {
2529	// On PowerPC, this section contains lazy symbol resolvers.
2530	if (config->emachine == EM_PPC64) {
2531	name = ".glink";
2532	addralign = 4;
2533	}
2534
2535	// On x86 when IBT is enabled, this section contains the second PLT (lazy
2536	// symbol resolvers).
2537	if ((config->emachine == EM_386 || config->emachine == EM_X86_64) &&
2538	(config->andFeatures & GNU_PROPERTY_X86_FEATURE_1_IBT))
2539	name = ".plt.sec";
2540
2541	// The PLT needs to be writable on SPARC as the dynamic linker will
2542	// modify the instructions in the PLT entries.
2543	if (config->emachine == EM_SPARCV9)
2544	this->flags |= SHF_WRITE;
2545	}
2546
2547	void PltSection::writeTo(uint8_t *buf) {
2548	// At beginning of PLT, we have code to call the dynamic
2549	// linker to resolve dynsyms at runtime. Write such code.
2550	target->writePltHeader(buf);
2551	size_t off = headerSize;
2552
2553	for (const Symbol *sym : entries) {
2554	target->writePlt(buf: buf + off, sym: *sym, pltEntryAddr: getVA() + off);
2555	off += target->pltEntrySize;
2556	}
2557	}
2558
2559	void PltSection::addEntry(Symbol &sym) {
2560	assert(sym.auxIdx == symAux.size() - 1);
2561	symAux.back().pltIdx = entries.size();
2562	entries.push_back(Elt: &sym);
2563	}
2564
2565	size_t PltSection::getSize() const {
2566	return headerSize + entries.size() * target->pltEntrySize;
2567	}
2568
2569	bool PltSection::isNeeded() const {
2570	// For -z retpolineplt, .iplt needs the .plt header.
2571	return !entries.empty() || (config->zRetpolineplt && in.iplt->isNeeded());
2572	}
2573
2574	// Used by ARM to add mapping symbols in the PLT section, which aid
2575	// disassembly.
2576	void PltSection::addSymbols() {
2577	target->addPltHeaderSymbols(isec&: *this);
2578
2579	size_t off = headerSize;
2580	for (size_t i = 0; i < entries.size(); ++i) {
2581	target->addPltSymbols(isec&: *this, off);
2582	off += target->pltEntrySize;
2583	}
2584	}
2585
2586	IpltSection::IpltSection()
2587	: SyntheticSection(SHF_ALLOC | SHF_EXECINSTR, SHT_PROGBITS, 16, ".iplt") {
2588	if (config->emachine == EM_PPC || config->emachine == EM_PPC64) {
2589	name = ".glink";
2590	addralign = 4;
2591	}
2592	}
2593
2594	void IpltSection::writeTo(uint8_t *buf) {
2595	uint32_t off = 0;
2596	for (const Symbol *sym : entries) {
2597	target->writeIplt(buf: buf + off, sym: *sym, pltEntryAddr: getVA() + off);
2598	off += target->ipltEntrySize;
2599	}
2600	}
2601
2602	size_t IpltSection::getSize() const {
2603	return entries.size() * target->ipltEntrySize;
2604	}
2605
2606	void IpltSection::addEntry(Symbol &sym) {
2607	assert(sym.auxIdx == symAux.size() - 1);
2608	symAux.back().pltIdx = entries.size();
2609	entries.push_back(Elt: &sym);
2610	}
2611
2612	// ARM uses mapping symbols to aid disassembly.
2613	void IpltSection::addSymbols() {
2614	size_t off = 0;
2615	for (size_t i = 0, e = entries.size(); i != e; ++i) {
2616	target->addPltSymbols(isec&: *this, off);
2617	off += target->pltEntrySize;
2618	}
2619	}
2620
2621	PPC32GlinkSection::PPC32GlinkSection() {
2622	name = ".glink";
2623	addralign = 4;
2624	}
2625
2626	void PPC32GlinkSection::writeTo(uint8_t *buf) {
2627	writePPC32GlinkSection(buf, numEntries: entries.size());
2628	}
2629
2630	size_t PPC32GlinkSection::getSize() const {
2631	return headerSize + entries.size() * target->pltEntrySize + footerSize;
2632	}
2633
2634	// This is an x86-only extra PLT section and used only when a security
2635	// enhancement feature called CET is enabled. In this comment, I'll explain what
2636	// the feature is and why we have two PLT sections if CET is enabled.
2637	//
2638	// So, what does CET do? CET introduces a new restriction to indirect jump
2639	// instructions. CET works this way. Assume that CET is enabled. Then, if you
2640	// execute an indirect jump instruction, the processor verifies that a special
2641	// "landing pad" instruction (which is actually a repurposed NOP instruction and
2642	// now called "endbr32" or "endbr64") is at the jump target. If the jump target
2643	// does not start with that instruction, the processor raises an exception
2644	// instead of continuing executing code.
2645	//
2646	// If CET is enabled, the compiler emits endbr to all locations where indirect
2647	// jumps may jump to.
2648	//
2649	// This mechanism makes it extremely hard to transfer the control to a middle of
2650	// a function that is not supporsed to be a indirect jump target, preventing
2651	// certain types of attacks such as ROP or JOP.
2652	//
2653	// Note that the processors in the market as of 2019 don't actually support the
2654	// feature. Only the spec is available at the moment.
2655	//
2656	// Now, I'll explain why we have this extra PLT section for CET.
2657	//
2658	// Since you can indirectly jump to a PLT entry, we have to make PLT entries
2659	// start with endbr. The problem is there's no extra space for endbr (which is 4
2660	// bytes long), as the PLT entry is only 16 bytes long and all bytes are already
2661	// used.
2662	//
2663	// In order to deal with the issue, we split a PLT entry into two PLT entries.
2664	// Remember that each PLT entry contains code to jump to an address read from
2665	// .got.plt AND code to resolve a dynamic symbol lazily. With the 2-PLT scheme,
2666	// the former code is written to .plt.sec, and the latter code is written to
2667	// .plt.
2668	//
2669	// Lazy symbol resolution in the 2-PLT scheme works in the usual way, except
2670	// that the regular .plt is now called .plt.sec and .plt is repurposed to
2671	// contain only code for lazy symbol resolution.
2672	//
2673	// In other words, this is how the 2-PLT scheme works. Application code is
2674	// supposed to jump to .plt.sec to call an external function. Each .plt.sec
2675	// entry contains code to read an address from a corresponding .got.plt entry
2676	// and jump to that address. Addresses in .got.plt initially point to .plt, so
2677	// when an application calls an external function for the first time, the
2678	// control is transferred to a function that resolves a symbol name from
2679	// external shared object files. That function then rewrites a .got.plt entry
2680	// with a resolved address, so that the subsequent function calls directly jump
2681	// to a desired location from .plt.sec.
2682	//
2683	// There is an open question as to whether the 2-PLT scheme was desirable or
2684	// not. We could have simply extended the PLT entry size to 32-bytes to
2685	// accommodate endbr, and that scheme would have been much simpler than the
2686	// 2-PLT scheme. One reason to split PLT was, by doing that, we could keep hot
2687	// code (.plt.sec) from cold code (.plt). But as far as I know no one proved
2688	// that the optimization actually makes a difference.
2689	//
2690	// That said, the 2-PLT scheme is a part of the ABI, debuggers and other tools
2691	// depend on it, so we implement the ABI.
2692	IBTPltSection::IBTPltSection()
2693	: SyntheticSection(SHF_ALLOC | SHF_EXECINSTR, SHT_PROGBITS, 16, ".plt") {}
2694
2695	void IBTPltSection::writeTo(uint8_t *buf) {
2696	target->writeIBTPlt(buf, numEntries: in.plt->getNumEntries());
2697	}
2698
2699	size_t IBTPltSection::getSize() const {
2700	// 16 is the header size of .plt.
2701	return 16 + in.plt->getNumEntries() * target->pltEntrySize;
2702	}
2703
2704	bool IBTPltSection::isNeeded() const { return in.plt->getNumEntries() > 0; }
2705
2706	RelroPaddingSection::RelroPaddingSection()
2707	: SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_NOBITS, 1, ".relro_padding") {
2708	}
2709
2710	// The string hash function for .gdb_index.
2711	static uint32_t computeGdbHash(StringRef s) {
2712	uint32_t h = 0;
2713	for (uint8_t c : s)
2714	h = h * 67 + toLower(x: c) - 113;
2715	return h;
2716	}
2717
2718	// 4-byte alignment ensures that values in the hash lookup table and the name
2719	// table are aligned.
2720	DebugNamesBaseSection::DebugNamesBaseSection()
2721	: SyntheticSection(0, SHT_PROGBITS, 4, ".debug_names") {}
2722
2723	// Get the size of the .debug_names section header in bytes for DWARF32:
2724	static uint32_t getDebugNamesHeaderSize(uint32_t augmentationStringSize) {
2725	return /* unit length */ 4 +
2726	/* version */ 2 +
2727	/* padding */ 2 +
2728	/* CU count */ 4 +
2729	/* TU count */ 4 +
2730	/* Foreign TU count */ 4 +
2731	/* Bucket Count */ 4 +
2732	/* Name Count */ 4 +
2733	/* Abbrev table size */ 4 +
2734	/* Augmentation string size */ 4 +
2735	/* Augmentation string */ augmentationStringSize;
2736	}
2737
2738	static Expected<DebugNamesBaseSection::IndexEntry *>
2739	readEntry(uint64_t &offset, const DWARFDebugNames::NameIndex &ni,
2740	uint64_t entriesBase, DWARFDataExtractor &namesExtractor,
2741	const LLDDWARFSection &namesSec) {
2742	auto ie = makeThreadLocal<DebugNamesBaseSection::IndexEntry>();
2743	ie->poolOffset = offset;
2744	Error err = Error::success();
2745	uint64_t ulebVal = namesExtractor.getULEB128(offset_ptr: &offset, Err: &err);
2746	if (err)
2747	return createStringError(EC: inconvertibleErrorCode(),
2748	Fmt: "invalid abbrev code: %s",
2749	Vals: toString(E: std::move(err)).c_str());
2750	if (!isUInt<32>(x: ulebVal))
2751	return createStringError(EC: inconvertibleErrorCode(),
2752	Fmt: "abbrev code too large for DWARF32: %" PRIu64,
2753	Vals: ulebVal);
2754	ie->abbrevCode = static_cast<uint32_t>(ulebVal);
2755	auto it = ni.getAbbrevs().find_as(Val: ie->abbrevCode);
2756	if (it == ni.getAbbrevs().end())
2757	return createStringError(EC: inconvertibleErrorCode(),
2758	Fmt: "abbrev code not found in abbrev table: %" PRIu32,
2759	Vals: ie->abbrevCode);
2760
2761	DebugNamesBaseSection::AttrValue attr, cuAttr = {.attrValue: 0, .attrSize: 0};
2762	for (DWARFDebugNames::AttributeEncoding a : it->Attributes) {
2763	if (a.Index == dwarf::DW_IDX_parent) {
2764	if (a.Form == dwarf::DW_FORM_ref4) {
2765	attr.attrValue = namesExtractor.getU32(offset_ptr: &offset, Err: &err);
2766	attr.attrSize = 4;
2767	ie->parentOffset = entriesBase + attr.attrValue;
2768	} else if (a.Form != DW_FORM_flag_present)
2769	return createStringError(EC: inconvertibleErrorCode(),
2770	Msg: "invalid form for DW_IDX_parent");
2771	} else {
2772	switch (a.Form) {
2773	case DW_FORM_data1:
2774	case DW_FORM_ref1: {
2775	attr.attrValue = namesExtractor.getU8(offset_ptr: &offset, Err: &err);
2776	attr.attrSize = 1;
2777	break;
2778	}
2779	case DW_FORM_data2:
2780	case DW_FORM_ref2: {
2781	attr.attrValue = namesExtractor.getU16(offset_ptr: &offset, Err: &err);
2782	attr.attrSize = 2;
2783	break;
2784	}
2785	case DW_FORM_data4:
2786	case DW_FORM_ref4: {
2787	attr.attrValue = namesExtractor.getU32(offset_ptr: &offset, Err: &err);
2788	attr.attrSize = 4;
2789	break;
2790	}
2791	default:
2792	return createStringError(
2793	EC: inconvertibleErrorCode(),
2794	Fmt: "unrecognized form encoding %d in abbrev table", Vals: a.Form);
2795	}
2796	}
2797	if (err)
2798	return createStringError(EC: inconvertibleErrorCode(),
2799	Fmt: "error while reading attributes: %s",
2800	Vals: toString(E: std::move(err)).c_str());
2801	if (a.Index == DW_IDX_compile_unit)
2802	cuAttr = attr;
2803	else if (a.Form != DW_FORM_flag_present)
2804	ie->attrValues.push_back(Elt: attr);
2805	}
2806	// Canonicalize abbrev by placing the CU/TU index at the end.
2807	ie->attrValues.push_back(Elt: cuAttr);
2808	return ie;
2809	}
2810
2811	void DebugNamesBaseSection::parseDebugNames(
2812	InputChunk &inputChunk, OutputChunk &chunk,
2813	DWARFDataExtractor &namesExtractor, DataExtractor &strExtractor,
2814	function_ref<SmallVector<uint32_t, 0>(
2815	uint32_t numCus, const DWARFDebugNames::Header &,
2816	const DWARFDebugNames::DWARFDebugNamesOffsets &)>
2817	readOffsets) {
2818	const LLDDWARFSection &namesSec = inputChunk.section;
2819	DenseMap<uint32_t, IndexEntry *> offsetMap;
2820	// Number of CUs seen in previous NameIndex sections within current chunk.
2821	uint32_t numCus = 0;
2822	for (const DWARFDebugNames::NameIndex &ni : *inputChunk.llvmDebugNames) {
2823	NameData &nd = inputChunk.nameData.emplace_back();
2824	nd.hdr = ni.getHeader();
2825	if (nd.hdr.Format != DwarfFormat::DWARF32) {
2826	errorOrWarn(msg: toString(namesSec.sec) +
2827	Twine(": found DWARF64, which is currently unsupported"));
2828	return;
2829	}
2830	if (nd.hdr.Version != 5) {
2831	errorOrWarn(msg: toString(namesSec.sec) + Twine(": unsupported version: ") +
2832	Twine(nd.hdr.Version));
2833	return;
2834	}
2835	uint32_t dwarfSize = dwarf::getDwarfOffsetByteSize(Format: DwarfFormat::DWARF32);
2836	DWARFDebugNames::DWARFDebugNamesOffsets locs = ni.getOffsets();
2837	if (locs.EntriesBase > namesExtractor.getData().size()) {
2838	errorOrWarn(msg: toString(namesSec.sec) +
2839	Twine(": entry pool start is beyond end of section"));
2840	return;
2841	}
2842
2843	SmallVector<uint32_t, 0> entryOffsets = readOffsets(numCus, nd.hdr, locs);
2844
2845	// Read the entry pool.
2846	offsetMap.clear();
2847	nd.nameEntries.resize(N: nd.hdr.NameCount);
2848	for (auto i : seq(Size: nd.hdr.NameCount)) {
2849	NameEntry &ne = nd.nameEntries[i];
2850	uint64_t strOffset = locs.StringOffsetsBase + i * dwarfSize;
2851	ne.stringOffset = strOffset;
2852	uint64_t strp = namesExtractor.getRelocatedValue(Size: dwarfSize, Off: &strOffset);
2853	StringRef name = strExtractor.getCStrRef(OffsetPtr: &strp);
2854	ne.name = name.data();
2855	ne.hashValue = caseFoldingDjbHash(Buffer: name);
2856
2857	// Read a series of index entries that end with abbreviation code 0.
2858	uint64_t offset = locs.EntriesBase + entryOffsets[i];
2859	while (offset < namesSec.Data.size() && namesSec.Data[offset] != 0) {
2860	// Read & store all entries (for the same string).
2861	Expected<IndexEntry *> ieOrErr =
2862	readEntry(offset, ni, entriesBase: locs.EntriesBase, namesExtractor, namesSec);
2863	if (!ieOrErr) {
2864	errorOrWarn(msg: toString(namesSec.sec) + ": " +
2865	toString(E: ieOrErr.takeError()));
2866	return;
2867	}
2868	ne.indexEntries.push_back(Elt: std::move(*ieOrErr));
2869	}
2870	if (offset >= namesSec.Data.size())
2871	errorOrWarn(msg: toString(namesSec.sec) +
2872	Twine(": index entry is out of bounds"));
2873
2874	for (IndexEntry &ie : ne.entries())
2875	offsetMap[ie.poolOffset] = &ie;
2876	}
2877
2878	// Assign parent pointers, which will be used to update DW_IDX_parent index
2879	// attributes. Note: offsetMap[0] does not exist, so parentOffset == 0 will
2880	// get parentEntry == null as well.
2881	for (NameEntry &ne : nd.nameEntries)
2882	for (IndexEntry &ie : ne.entries())
2883	ie.parentEntry = offsetMap.lookup(Val: ie.parentOffset);
2884	numCus += nd.hdr.CompUnitCount;
2885	}
2886	}
2887
2888	// Compute the form for output DW_IDX_compile_unit attributes, similar to
2889	// DIEInteger::BestForm. The input form (often DW_FORM_data1) may not hold all
2890	// the merged CU indices.
2891	std::pair<uint8_t, dwarf::Form> static getMergedCuCountForm(
2892	uint32_t compUnitCount) {
2893	if (compUnitCount > UINT16_MAX)
2894	return {4, DW_FORM_data4};
2895	if (compUnitCount > UINT8_MAX)
2896	return {2, DW_FORM_data2};
2897	return {1, DW_FORM_data1};
2898	}
2899
2900	void DebugNamesBaseSection::computeHdrAndAbbrevTable(
2901	MutableArrayRef<InputChunk> inputChunks) {
2902	TimeTraceScope timeScope("Merge .debug_names", "hdr and abbrev table");
2903	size_t numCu = 0;
2904	hdr.Format = DwarfFormat::DWARF32;
2905	hdr.Version = 5;
2906	hdr.CompUnitCount = 0;
2907	hdr.LocalTypeUnitCount = 0;
2908	hdr.ForeignTypeUnitCount = 0;
2909	hdr.AugmentationStringSize = 0;
2910
2911	// Compute CU and TU counts.
2912	for (auto i : seq(Size: numChunks)) {
2913	InputChunk &inputChunk = inputChunks[i];
2914	inputChunk.baseCuIdx = numCu;
2915	numCu += chunks[i].compUnits.size();
2916	for (const NameData &nd : inputChunk.nameData) {
2917	hdr.CompUnitCount += nd.hdr.CompUnitCount;
2918	// TODO: We don't handle type units yet, so LocalTypeUnitCount &
2919	// ForeignTypeUnitCount are left as 0.
2920	if (nd.hdr.LocalTypeUnitCount || nd.hdr.ForeignTypeUnitCount)
2921	warn(msg: toString(inputChunk.section.sec) +
2922	Twine(": type units are not implemented"));
2923	// If augmentation strings are not identical, use an empty string.
2924	if (i == 0) {
2925	hdr.AugmentationStringSize = nd.hdr.AugmentationStringSize;
2926	hdr.AugmentationString = nd.hdr.AugmentationString;
2927	} else if (hdr.AugmentationString != nd.hdr.AugmentationString) {
2928	// There are conflicting augmentation strings, so it's best for the
2929	// merged index to not use an augmentation string.
2930	hdr.AugmentationStringSize = 0;
2931	hdr.AugmentationString.clear();
2932	}
2933	}
2934	}
2935
2936	// Create the merged abbrev table, uniquifyinng the input abbrev tables and
2937	// computing mapping from old (per-cu) abbrev codes to new (merged) abbrev
2938	// codes.
2939	FoldingSet<Abbrev> abbrevSet;
2940	// Determine the form for the DW_IDX_compile_unit attributes in the merged
2941	// index. The input form may not be big enough for all CU indices.
2942	dwarf::Form cuAttrForm = getMergedCuCountForm(compUnitCount: hdr.CompUnitCount).second;
2943	for (InputChunk &inputChunk : inputChunks) {
2944	for (auto [i, ni] : enumerate(First&: *inputChunk.llvmDebugNames)) {
2945	for (const DWARFDebugNames::Abbrev &oldAbbrev : ni.getAbbrevs()) {
2946	// Canonicalize abbrev by placing the CU/TU index at the end,
2947	// similar to 'parseDebugNames'.
2948	Abbrev abbrev;
2949	DWARFDebugNames::AttributeEncoding cuAttr(DW_IDX_compile_unit,
2950	cuAttrForm);
2951	abbrev.code = oldAbbrev.Code;
2952	abbrev.tag = oldAbbrev.Tag;
2953	for (DWARFDebugNames::AttributeEncoding a : oldAbbrev.Attributes) {
2954	if (a.Index == DW_IDX_compile_unit)
2955	cuAttr.Index = a.Index;
2956	else
2957	abbrev.attributes.push_back(Elt: {a.Index, a.Form});
2958	}
2959	// Put the CU/TU index at the end of the attributes list.
2960	abbrev.attributes.push_back(Elt: cuAttr);
2961
2962	// Profile the abbrev, get or assign a new code, then record the abbrev
2963	// code mapping.
2964	FoldingSetNodeID id;
2965	abbrev.Profile(id);
2966	uint32_t newCode;
2967	void *insertPos;
2968	if (Abbrev *existing = abbrevSet.FindNodeOrInsertPos(ID: id, InsertPos&: insertPos)) {
2969	// Found it; we've already seen an identical abbreviation.
2970	newCode = existing->code;
2971	} else {
2972	Abbrev *abbrev2 =
2973	new (abbrevAlloc.Allocate()) Abbrev(std::move(abbrev));
2974	abbrevSet.InsertNode(N: abbrev2, InsertPos: insertPos);
2975	abbrevTable.push_back(Elt: abbrev2);
2976	newCode = abbrevTable.size();
2977	abbrev2->code = newCode;
2978	}
2979	inputChunk.nameData[i].abbrevCodeMap[oldAbbrev.Code] = newCode;
2980	}
2981	}
2982	}
2983
2984	// Compute the merged abbrev table.
2985	raw_svector_ostream os(abbrevTableBuf);
2986	for (Abbrev *abbrev : abbrevTable) {
2987	encodeULEB128(Value: abbrev->code, OS&: os);
2988	encodeULEB128(Value: abbrev->tag, OS&: os);
2989	for (DWARFDebugNames::AttributeEncoding a : abbrev->attributes) {
2990	encodeULEB128(Value: a.Index, OS&: os);
2991	encodeULEB128(Value: a.Form, OS&: os);
2992	}
2993	os.write(Ptr: "\0", Size: 2); // attribute specification end
2994	}
2995	os.write(C: 0); // abbrev table end
2996	hdr.AbbrevTableSize = abbrevTableBuf.size();
2997	}
2998
2999	void DebugNamesBaseSection::Abbrev::Profile(FoldingSetNodeID &id) const {
3000	id.AddInteger(I: tag);
3001	for (const DWARFDebugNames::AttributeEncoding &attr : attributes) {
3002	id.AddInteger(I: attr.Index);
3003	id.AddInteger(I: attr.Form);
3004	}
3005	}
3006
3007	std::pair<uint32_t, uint32_t> DebugNamesBaseSection::computeEntryPool(
3008	MutableArrayRef<InputChunk> inputChunks) {
3009	TimeTraceScope timeScope("Merge .debug_names", "entry pool");
3010	// Collect and de-duplicate all the names (preserving all the entries).
3011	// Speed it up using multithreading, as the number of symbols can be in the
3012	// order of millions.
3013	const size_t concurrency =
3014	bit_floor(Value: std::min<size_t>(a: config->threadCount, b: numShards));
3015	const size_t shift = 32 - countr_zero(Val: numShards);
3016	const uint8_t cuAttrSize = getMergedCuCountForm(compUnitCount: hdr.CompUnitCount).first;
3017	DenseMap<CachedHashStringRef, size_t> maps[numShards];
3018
3019	parallelFor(Begin: 0, End: concurrency, Fn: [&](size_t threadId) {
3020	for (auto i : seq(Size: numChunks)) {
3021	InputChunk &inputChunk = inputChunks[i];
3022	for (auto j : seq(Size: inputChunk.nameData.size())) {
3023	NameData &nd = inputChunk.nameData[j];
3024	// Deduplicate the NameEntry records (based on the string/name),
3025	// appending all IndexEntries from duplicate NameEntry records to
3026	// the single preserved copy.
3027	for (NameEntry &ne : nd.nameEntries) {
3028	auto shardId = ne.hashValue >> shift;
3029	if ((shardId & (concurrency - 1)) != threadId)
3030	continue;
3031
3032	ne.chunkIdx = i;
3033	for (IndexEntry &ie : ne.entries()) {
3034	// Update the IndexEntry's abbrev code to match the merged
3035	// abbreviations.
3036	ie.abbrevCode = nd.abbrevCodeMap[ie.abbrevCode];
3037	// Update the DW_IDX_compile_unit attribute (the last one after
3038	// canonicalization) to have correct merged offset value and size.
3039	auto &back = ie.attrValues.back();
3040	back.attrValue += inputChunk.baseCuIdx + j;
3041	back.attrSize = cuAttrSize;
3042	}
3043
3044	auto &nameVec = nameVecs[shardId];
3045	auto [it, inserted] = maps[shardId].try_emplace(
3046	Key: CachedHashStringRef(ne.name, ne.hashValue), Args: nameVec.size());
3047	if (inserted)
3048	nameVec.push_back(Elt: std::move(ne));
3049	else
3050	nameVec[it->second].indexEntries.append(RHS: std::move(ne.indexEntries));
3051	}
3052	}
3053	}
3054	});
3055
3056	// Compute entry offsets in parallel. First, compute offsets relative to the
3057	// current shard.
3058	uint32_t offsets[numShards];
3059	parallelFor(Begin: 0, End: numShards, Fn: [&](size_t shard) {
3060	uint32_t offset = 0;
3061	for (NameEntry &ne : nameVecs[shard]) {
3062	ne.entryOffset = offset;
3063	for (IndexEntry &ie : ne.entries()) {
3064	ie.poolOffset = offset;
3065	offset += getULEB128Size(Value: ie.abbrevCode);
3066	for (AttrValue value : ie.attrValues)
3067	offset += value.attrSize;
3068	}
3069	++offset; // index entry sentinel
3070	}
3071	offsets[shard] = offset;
3072	});
3073	// Then add shard offsets.
3074	std::partial_sum(first: offsets, last: std::end(arr&: offsets), result: offsets);
3075	parallelFor(Begin: 1, End: numShards, Fn: [&](size_t shard) {
3076	uint32_t offset = offsets[shard - 1];
3077	for (NameEntry &ne : nameVecs[shard]) {
3078	ne.entryOffset += offset;
3079	for (IndexEntry &ie : ne.entries())
3080	ie.poolOffset += offset;
3081	}
3082	});
3083
3084	// Update the DW_IDX_parent entries that refer to real parents (have
3085	// DW_FORM_ref4).
3086	parallelFor(Begin: 0, End: numShards, Fn: [&](size_t shard) {
3087	for (NameEntry &ne : nameVecs[shard]) {
3088	for (IndexEntry &ie : ne.entries()) {
3089	if (!ie.parentEntry)
3090	continue;
3091	// Abbrevs are indexed starting at 1; vector starts at 0. (abbrevCode
3092	// corresponds to position in the merged table vector).
3093	const Abbrev *abbrev = abbrevTable[ie.abbrevCode - 1];
3094	for (const auto &[a, v] : zip_equal(t: abbrev->attributes, u&: ie.attrValues))
3095	if (a.Index == DW_IDX_parent && a.Form == DW_FORM_ref4)
3096	v.attrValue = ie.parentEntry->poolOffset;
3097	}
3098	}
3099	});
3100
3101	// Return (entry pool size, number of entries).
3102	uint32_t num = 0;
3103	for (auto &map : maps)
3104	num += map.size();
3105	return {offsets[numShards - 1], num};
3106	}
3107
3108	void DebugNamesBaseSection::init(
3109	function_ref<void(InputFile *, InputChunk &, OutputChunk &)> parseFile) {
3110	TimeTraceScope timeScope("Merge .debug_names");
3111	// Collect and remove input .debug_names sections. Save InputSection pointers
3112	// to relocate string offsets in `writeTo`.
3113	SetVector<InputFile *> files;
3114	for (InputSectionBase *s : ctx.inputSections) {
3115	InputSection *isec = dyn_cast<InputSection>(Val: s);
3116	if (!isec)
3117	continue;
3118	if (!(s->flags & SHF_ALLOC) && s->name == ".debug_names") {
3119	s->markDead();
3120	inputSections.push_back(Elt: isec);
3121	files.insert(X: isec->file);
3122	}
3123	}
3124
3125	// Parse input .debug_names sections and extract InputChunk and OutputChunk
3126	// data. OutputChunk contains CU information, which will be needed by
3127	// `writeTo`.
3128	auto inputChunksPtr = std::make_unique<InputChunk[]>(num: files.size());
3129	MutableArrayRef<InputChunk> inputChunks(inputChunksPtr.get(), files.size());
3130	numChunks = files.size();
3131	chunks = std::make_unique<OutputChunk[]>(num: files.size());
3132	{
3133	TimeTraceScope timeScope("Merge .debug_names", "parse");
3134	parallelFor(Begin: 0, End: files.size(), Fn: [&](size_t i) {
3135	parseFile(files[i], inputChunks[i], chunks[i]);
3136	});
3137	}
3138
3139	// Compute section header (except unit_length), abbrev table, and entry pool.
3140	computeHdrAndAbbrevTable(inputChunks);
3141	uint32_t entryPoolSize;
3142	std::tie(args&: entryPoolSize, args&: hdr.NameCount) = computeEntryPool(inputChunks);
3143	hdr.BucketCount = dwarf::getDebugNamesBucketCount(UniqueHashCount: hdr.NameCount);
3144
3145	// Compute the section size. Subtract 4 to get the unit_length for DWARF32.
3146	uint32_t hdrSize = getDebugNamesHeaderSize(augmentationStringSize: hdr.AugmentationStringSize);
3147	size = findDebugNamesOffsets(EndOfHeaderOffset: hdrSize, Hdr: hdr).EntriesBase + entryPoolSize;
3148	hdr.UnitLength = size - 4;
3149	}
3150
3151	template <class ELFT> DebugNamesSection<ELFT>::DebugNamesSection() {
3152	init(parseFile: [](InputFile *f, InputChunk &inputChunk, OutputChunk &chunk) {
3153	auto *file = cast<ObjFile<ELFT>>(f);
3154	DWARFContext dwarf(std::make_unique<LLDDwarfObj<ELFT>>(file));
3155	auto &dobj = static_cast<const LLDDwarfObj<ELFT> &>(dwarf.getDWARFObj());
3156	chunk.infoSec = dobj.getInfoSection();
3157	DWARFDataExtractor namesExtractor(dobj, dobj.getNamesSection(),
3158	ELFT::Endianness == endianness::little,
3159	ELFT::Is64Bits ? 8 : 4);
3160	// .debug_str is needed to get symbol names from string offsets.
3161	DataExtractor strExtractor(dobj.getStrSection(),
3162	ELFT::Endianness == endianness::little,
3163	ELFT::Is64Bits ? 8 : 4);
3164	inputChunk.section = dobj.getNamesSection();
3165
3166	inputChunk.llvmDebugNames.emplace(args&: namesExtractor, args&: strExtractor);
3167	if (Error e = inputChunk.llvmDebugNames->extract()) {
3168	errorOrWarn(toString(dobj.getNamesSection().sec) + Twine(": ") +
3169	toString(E: std::move(e)));
3170	}
3171	parseDebugNames(
3172	inputChunk, chunk, namesExtractor, strExtractor,
3173	readOffsets: [&chunk, namesData = dobj.getNamesSection().Data.data()](
3174	uint32_t numCus, const DWARFDebugNames::Header &hdr,
3175	const DWARFDebugNames::DWARFDebugNamesOffsets &locs) {
3176	// Read CU offsets, which are relocated by .debug_info + X
3177	// relocations. Record the section offset to be relocated by
3178	// `finalizeContents`.
3179	chunk.compUnits.resize_for_overwrite(N: numCus + hdr.CompUnitCount);
3180	for (auto i : seq(Size: hdr.CompUnitCount))
3181	chunk.compUnits[numCus + i] = locs.CUsBase + i * 4;
3182
3183	// Read entry offsets.
3184	const char *p = namesData + locs.EntryOffsetsBase;
3185	SmallVector<uint32_t, 0> entryOffsets;
3186	entryOffsets.resize_for_overwrite(N: hdr.NameCount);
3187	for (uint32_t &offset : entryOffsets)
3188	offset = endian::readNext<uint32_t, ELFT::Endianness, unaligned>(p);
3189	return entryOffsets;
3190	});
3191	});
3192	}
3193
3194	template <class ELFT>
3195	template <class RelTy>
3196	void DebugNamesSection<ELFT>::getNameRelocs(
3197	InputSection *sec, ArrayRef<RelTy> rels,
3198	DenseMap<uint32_t, uint32_t> &relocs) {
3199	for (const RelTy &rel : rels) {
3200	Symbol &sym = sec->file->getRelocTargetSym(rel);
3201	relocs[rel.r_offset] = sym.getVA(addend: getAddend<ELFT>(rel));
3202	}
3203	}
3204
3205	template <class ELFT> void DebugNamesSection<ELFT>::finalizeContents() {
3206	// Get relocations of .debug_names sections.
3207	auto relocs = std::make_unique<DenseMap<uint32_t, uint32_t>[]>(numChunks);
3208	parallelFor(0, numChunks, [&](size_t i) {
3209	InputSection *sec = inputSections[i];
3210	auto rels = sec->template relsOrRelas<ELFT>();
3211	if (rels.areRelocsRel())
3212	getNameRelocs(sec, rels.rels, relocs.get()[i]);
3213	else
3214	getNameRelocs(sec, rels.relas, relocs.get()[i]);
3215
3216	// Relocate CU offsets with .debug_info + X relocations.
3217	OutputChunk &chunk = chunks.get()[i];
3218	for (auto [j, cuOffset] : enumerate(First&: chunk.compUnits))
3219	cuOffset = relocs.get()[i].lookup(cuOffset);
3220	});
3221
3222	// Relocate string offsets in the name table with .debug_str + X relocations.
3223	parallelForEach(nameVecs, [&](auto &nameVec) {
3224	for (NameEntry &ne : nameVec)
3225	ne.stringOffset = relocs.get()[ne.chunkIdx].lookup(ne.stringOffset);
3226	});
3227	}
3228
3229	template <class ELFT> void DebugNamesSection<ELFT>::writeTo(uint8_t *buf) {
3230	[[maybe_unused]] const uint8_t *const beginBuf = buf;
3231	// Write the header.
3232	endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.UnitLength);
3233	endian::writeNext<uint16_t, ELFT::Endianness>(buf, hdr.Version);
3234	buf += 2; // padding
3235	endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.CompUnitCount);
3236	endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.LocalTypeUnitCount);
3237	endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.ForeignTypeUnitCount);
3238	endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.BucketCount);
3239	endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.NameCount);
3240	endian::writeNext<uint32_t, ELFT::Endianness>(buf, hdr.AbbrevTableSize);
3241	endian::writeNext<uint32_t, ELFT::Endianness>(buf,
3242	hdr.AugmentationStringSize);
3243	memcpy(buf, hdr.AugmentationString.c_str(), hdr.AugmentationString.size());
3244	buf += hdr.AugmentationStringSize;
3245
3246	// Write the CU list.
3247	for (auto &chunk : getChunks())
3248	for (uint32_t cuOffset : chunk.compUnits)
3249	endian::writeNext<uint32_t, ELFT::Endianness>(buf, cuOffset);
3250
3251	// TODO: Write the local TU list, then the foreign TU list..
3252
3253	// Write the hash lookup table.
3254	SmallVector<SmallVector<NameEntry *, 0>, 0> buckets(hdr.BucketCount);
3255	// Symbols enter into a bucket whose index is the hash modulo bucket_count.
3256	for (auto &nameVec : nameVecs)
3257	for (NameEntry &ne : nameVec)
3258	buckets[ne.hashValue % hdr.BucketCount].push_back(&ne);
3259
3260	// Write buckets (accumulated bucket counts).
3261	uint32_t bucketIdx = 1;
3262	for (const SmallVector<NameEntry *, 0> &bucket : buckets) {
3263	if (!bucket.empty())
3264	endian::write32<ELFT::Endianness>(buf, bucketIdx);
3265	buf += 4;
3266	bucketIdx += bucket.size();
3267	}
3268	// Write the hashes.
3269	for (const SmallVector<NameEntry *, 0> &bucket : buckets)
3270	for (const NameEntry *e : bucket)
3271	endian::writeNext<uint32_t, ELFT::Endianness>(buf, e->hashValue);
3272
3273	// Write the name table. The name entries are ordered by bucket_idx and
3274	// correspond one-to-one with the hash lookup table.
3275	//
3276	// First, write the relocated string offsets.
3277	for (const SmallVector<NameEntry *, 0> &bucket : buckets)
3278	for (const NameEntry *ne : bucket)
3279	endian::writeNext<uint32_t, ELFT::Endianness>(buf, ne->stringOffset);
3280
3281	// Then write the entry offsets.
3282	for (const SmallVector<NameEntry *, 0> &bucket : buckets)
3283	for (const NameEntry *ne : bucket)
3284	endian::writeNext<uint32_t, ELFT::Endianness>(buf, ne->entryOffset);
3285
3286	// Write the abbrev table.
3287	buf = llvm::copy(abbrevTableBuf, buf);
3288
3289	// Write the entry pool. Unlike the name table, the name entries follow the
3290	// nameVecs order computed by `computeEntryPool`.
3291	for (auto &nameVec : nameVecs) {
3292	for (NameEntry &ne : nameVec) {
3293	// Write all the entries for the string.
3294	for (const IndexEntry &ie : ne.entries()) {
3295	buf += encodeULEB128(Value: ie.abbrevCode, p: buf);
3296	for (AttrValue value : ie.attrValues) {
3297	switch (value.attrSize) {
3298	case 1:
3299	*buf++ = value.attrValue;
3300	break;
3301	case 2:
3302	endian::writeNext<uint16_t, ELFT::Endianness>(buf, value.attrValue);
3303	break;
3304	case 4:
3305	endian::writeNext<uint32_t, ELFT::Endianness>(buf, value.attrValue);
3306	break;
3307	default:
3308	llvm_unreachable("invalid attrSize");
3309	}
3310	}
3311	}
3312	++buf; // index entry sentinel
3313	}
3314	}
3315	assert(uint64_t(buf - beginBuf) == size);
3316	}
3317
3318	GdbIndexSection::GdbIndexSection()
3319	: SyntheticSection(0, SHT_PROGBITS, 1, ".gdb_index") {}
3320
3321	// Returns the desired size of an on-disk hash table for a .gdb_index section.
3322	// There's a tradeoff between size and collision rate. We aim 75% utilization.
3323	size_t GdbIndexSection::computeSymtabSize() const {
3324	return std::max<size_t>(a: NextPowerOf2(A: symbols.size() * 4 / 3), b: 1024);
3325	}
3326
3327	static SmallVector<GdbIndexSection::CuEntry, 0>
3328	readCuList(DWARFContext &dwarf) {
3329	SmallVector<GdbIndexSection::CuEntry, 0> ret;
3330	for (std::unique_ptr<DWARFUnit> &cu : dwarf.compile_units())
3331	ret.push_back(Elt: {.cuOffset: cu->getOffset(), .cuLength: cu->getLength() + 4});
3332	return ret;
3333	}
3334
3335	static SmallVector<GdbIndexSection::AddressEntry, 0>
3336	readAddressAreas(DWARFContext &dwarf, InputSection *sec) {
3337	SmallVector<GdbIndexSection::AddressEntry, 0> ret;
3338
3339	uint32_t cuIdx = 0;
3340	for (std::unique_ptr<DWARFUnit> &cu : dwarf.compile_units()) {
3341	if (Error e = cu->tryExtractDIEsIfNeeded(CUDieOnly: false)) {
3342	warn(msg: toString(sec) + ": " + toString(E: std::move(e)));
3343	return {};
3344	}
3345	Expected<DWARFAddressRangesVector> ranges = cu->collectAddressRanges();
3346	if (!ranges) {
3347	warn(msg: toString(sec) + ": " + toString(E: ranges.takeError()));
3348	return {};
3349	}
3350
3351	ArrayRef<InputSectionBase *> sections = sec->file->getSections();
3352	for (DWARFAddressRange &r : *ranges) {
3353	if (r.SectionIndex == -1ULL)
3354	continue;
3355	// Range list with zero size has no effect.
3356	InputSectionBase *s = sections[r.SectionIndex];
3357	if (s && s != &InputSection::discarded && s->isLive())
3358	if (r.LowPC != r.HighPC)
3359	ret.push_back(Elt: {.section: cast<InputSection>(Val: s), .lowAddress: r.LowPC, .highAddress: r.HighPC, .cuIndex: cuIdx});
3360	}
3361	++cuIdx;
3362	}
3363
3364	return ret;
3365	}
3366
3367	template <class ELFT>
3368	static SmallVector<GdbIndexSection::NameAttrEntry, 0>
3369	readPubNamesAndTypes(const LLDDwarfObj<ELFT> &obj,
3370	const SmallVectorImpl<GdbIndexSection::CuEntry> &cus) {
3371	const LLDDWARFSection &pubNames = obj.getGnuPubnamesSection();
3372	const LLDDWARFSection &pubTypes = obj.getGnuPubtypesSection();
3373
3374	SmallVector<GdbIndexSection::NameAttrEntry, 0> ret;
3375	for (const LLDDWARFSection *pub : {&pubNames, &pubTypes}) {
3376	DWARFDataExtractor data(obj, *pub, ELFT::Endianness == endianness::little,
3377	ELFT::Is64Bits ? 8 : 4);
3378	DWARFDebugPubTable table;
3379	table.extract(Data: data, /*GnuStyle=*/true, RecoverableErrorHandler: [&](Error e) {
3380	warn(msg: toString(pub->sec) + ": " + toString(E: std::move(e)));
3381	});
3382	for (const DWARFDebugPubTable::Set &set : table.getData()) {
3383	// The value written into the constant pool is kind << 24 | cuIndex. As we
3384	// don't know how many compilation units precede this object to compute
3385	// cuIndex, we compute (kind << 24 | cuIndexInThisObject) instead, and add
3386	// the number of preceding compilation units later.
3387	uint32_t i = llvm::partition_point(cus,
3388	[&](GdbIndexSection::CuEntry cu) {
3389	return cu.cuOffset < set.Offset;
3390	}) -
3391	cus.begin();
3392	for (const DWARFDebugPubTable::Entry &ent : set.Entries)
3393	ret.push_back(Elt: {.name: {ent.Name, computeGdbHash(s: ent.Name)},
3394	.cuIndexAndAttrs: (ent.Descriptor.toBits() << 24) | i});
3395	}
3396	}
3397	return ret;
3398	}
3399
3400	// Create a list of symbols from a given list of symbol names and types
3401	// by uniquifying them by name.
3402	static std::pair<SmallVector<GdbIndexSection::GdbSymbol, 0>, size_t>
3403	createSymbols(
3404	ArrayRef<SmallVector<GdbIndexSection::NameAttrEntry, 0>> nameAttrs,
3405	const SmallVector<GdbIndexSection::GdbChunk, 0> &chunks) {
3406	using GdbSymbol = GdbIndexSection::GdbSymbol;
3407	using NameAttrEntry = GdbIndexSection::NameAttrEntry;
3408
3409	// For each chunk, compute the number of compilation units preceding it.
3410	uint32_t cuIdx = 0;
3411	std::unique_ptr<uint32_t[]> cuIdxs(new uint32_t[chunks.size()]);
3412	for (uint32_t i = 0, e = chunks.size(); i != e; ++i) {
3413	cuIdxs[i] = cuIdx;
3414	cuIdx += chunks[i].compilationUnits.size();
3415	}
3416
3417	// Collect the compilation unitss for each unique name. Speed it up using
3418	// multi-threading as the number of symbols can be in the order of millions.
3419	// Shard GdbSymbols by hash's high bits.
3420	constexpr size_t numShards = 32;
3421	const size_t concurrency =
3422	llvm::bit_floor(Value: std::min<size_t>(a: config->threadCount, b: numShards));
3423	const size_t shift = 32 - llvm::countr_zero(Val: numShards);
3424	auto map =
3425	std::make_unique<DenseMap<CachedHashStringRef, size_t>[]>(num: numShards);
3426	auto symbols = std::make_unique<SmallVector<GdbSymbol, 0>[]>(num: numShards);
3427	parallelFor(Begin: 0, End: concurrency, Fn: [&](size_t threadId) {
3428	uint32_t i = 0;
3429	for (ArrayRef<NameAttrEntry> entries : nameAttrs) {
3430	for (const NameAttrEntry &ent : entries) {
3431	size_t shardId = ent.name.hash() >> shift;
3432	if ((shardId & (concurrency - 1)) != threadId)
3433	continue;
3434
3435	uint32_t v = ent.cuIndexAndAttrs + cuIdxs[i];
3436	auto [it, inserted] =
3437	map[shardId].try_emplace(Key: ent.name, Args: symbols[shardId].size());
3438	if (inserted)
3439	symbols[shardId].push_back(Elt: {.name: ent.name, .cuVector: {v}, .nameOff: 0, .cuVectorOff: 0});
3440	else
3441	symbols[shardId][it->second].cuVector.push_back(Elt: v);
3442	}
3443	++i;
3444	}
3445	});
3446
3447	size_t numSymbols = 0;
3448	for (ArrayRef<GdbSymbol> v : ArrayRef(symbols.get(), numShards))
3449	numSymbols += v.size();
3450
3451	// The return type is a flattened vector, so we'll copy each vector
3452	// contents to Ret.
3453	SmallVector<GdbSymbol, 0> ret;
3454	ret.reserve(N: numSymbols);
3455	for (SmallVector<GdbSymbol, 0> &vec :
3456	MutableArrayRef(symbols.get(), numShards))
3457	for (GdbSymbol &sym : vec)
3458	ret.push_back(Elt: std::move(sym));
3459
3460	// CU vectors and symbol names are adjacent in the output file.
3461	// We can compute their offsets in the output file now.
3462	size_t off = 0;
3463	for (GdbSymbol &sym : ret) {
3464	sym.cuVectorOff = off;
3465	off += (sym.cuVector.size() + 1) * 4;
3466	}
3467	for (GdbSymbol &sym : ret) {
3468	sym.nameOff = off;
3469	off += sym.name.size() + 1;
3470	}
3471	// If off overflows, the last symbol's nameOff likely overflows.
3472	if (!isUInt<32>(x: off))
3473	errorOrWarn(msg: "--gdb-index: constant pool size (" + Twine(off) +
3474	") exceeds UINT32_MAX");
3475
3476	return {ret, off};
3477	}
3478
3479	// Returns a newly-created .gdb_index section.
3480	template <class ELFT>
3481	std::unique_ptr<GdbIndexSection> GdbIndexSection::create() {
3482	llvm::TimeTraceScope timeScope("Create gdb index");
3483
3484	// Collect InputFiles with .debug_info. See the comment in
3485	// LLDDwarfObj<ELFT>::LLDDwarfObj. If we do lightweight parsing in the future,
3486	// note that isec->data() may uncompress the full content, which should be
3487	// parallelized.
3488	SetVector<InputFile *> files;
3489	for (InputSectionBase *s : ctx.inputSections) {
3490	InputSection *isec = dyn_cast<InputSection>(Val: s);
3491	if (!isec)
3492	continue;
3493	// .debug_gnu_pub{names,types} are useless in executables.
3494	// They are present in input object files solely for creating
3495	// a .gdb_index. So we can remove them from the output.
3496	if (s->name == ".debug_gnu_pubnames" || s->name == ".debug_gnu_pubtypes")
3497	s->markDead();
3498	else if (isec->name == ".debug_info")
3499	files.insert(X: isec->file);
3500	}
3501	// Drop .rel[a].debug_gnu_pub{names,types} for --emit-relocs.
3502	llvm::erase_if(ctx.inputSections, [](InputSectionBase *s) {
3503	if (auto *isec = dyn_cast<InputSection>(Val: s))
3504	if (InputSectionBase *rel = isec->getRelocatedSection())
3505	return !rel->isLive();
3506	return !s->isLive();
3507	});
3508
3509	SmallVector<GdbChunk, 0> chunks(files.size());
3510	SmallVector<SmallVector<NameAttrEntry, 0>, 0> nameAttrs(files.size());
3511
3512	parallelFor(0, files.size(), [&](size_t i) {
3513	// To keep memory usage low, we don't want to keep cached DWARFContext, so
3514	// avoid getDwarf() here.
3515	ObjFile<ELFT> *file = cast<ObjFile<ELFT>>(files[i]);
3516	DWARFContext dwarf(std::make_unique<LLDDwarfObj<ELFT>>(file));
3517	auto &dobj = static_cast<const LLDDwarfObj<ELFT> &>(dwarf.getDWARFObj());
3518
3519	// If the are multiple compile units .debug_info (very rare ld -r --unique),
3520	// this only picks the last one. Other address ranges are lost.
3521	chunks[i].sec = dobj.getInfoSection();
3522	chunks[i].compilationUnits = readCuList(dwarf);
3523	chunks[i].addressAreas = readAddressAreas(dwarf, sec: chunks[i].sec);
3524	nameAttrs[i] = readPubNamesAndTypes<ELFT>(dobj, chunks[i].compilationUnits);
3525	});
3526
3527	auto ret = std::make_unique<GdbIndexSection>();
3528	ret->chunks = std::move(chunks);
3529	std::tie(args&: ret->symbols, args&: ret->size) = createSymbols(nameAttrs, chunks: ret->chunks);
3530
3531	// Count the areas other than the constant pool.
3532	ret->size += sizeof(GdbIndexHeader) + ret->computeSymtabSize() * 8;
3533	for (GdbChunk &chunk : ret->chunks)
3534	ret->size +=
3535	chunk.compilationUnits.size() * 16 + chunk.addressAreas.size() * 20;
3536
3537	return ret;
3538	}
3539
3540	void GdbIndexSection::writeTo(uint8_t *buf) {
3541	// Write the header.
3542	auto *hdr = reinterpret_cast<GdbIndexHeader *>(buf);
3543	uint8_t *start = buf;
3544	hdr->version = 7;
3545	buf += sizeof(*hdr);
3546
3547	// Write the CU list.
3548	hdr->cuListOff = buf - start;
3549	for (GdbChunk &chunk : chunks) {
3550	for (CuEntry &cu : chunk.compilationUnits) {
3551	write64le(P: buf, V: chunk.sec->outSecOff + cu.cuOffset);
3552	write64le(P: buf + 8, V: cu.cuLength);
3553	buf += 16;
3554	}
3555	}
3556
3557	// Write the address area.
3558	hdr->cuTypesOff = buf - start;
3559	hdr->addressAreaOff = buf - start;
3560	uint32_t cuOff = 0;
3561	for (GdbChunk &chunk : chunks) {
3562	for (AddressEntry &e : chunk.addressAreas) {
3563	// In the case of ICF there may be duplicate address range entries.
3564	const uint64_t baseAddr = e.section->repl->getVA(offset: 0);
3565	write64le(P: buf, V: baseAddr + e.lowAddress);
3566	write64le(P: buf + 8, V: baseAddr + e.highAddress);
3567	write32le(P: buf + 16, V: e.cuIndex + cuOff);
3568	buf += 20;
3569	}
3570	cuOff += chunk.compilationUnits.size();
3571	}
3572
3573	// Write the on-disk open-addressing hash table containing symbols.
3574	hdr->symtabOff = buf - start;
3575	size_t symtabSize = computeSymtabSize();
3576	uint32_t mask = symtabSize - 1;
3577
3578	for (GdbSymbol &sym : symbols) {
3579	uint32_t h = sym.name.hash();
3580	uint32_t i = h & mask;
3581	uint32_t step = ((h * 17) & mask) | 1;
3582
3583	while (read32le(P: buf + i * 8))
3584	i = (i + step) & mask;
3585
3586	write32le(P: buf + i * 8, V: sym.nameOff);
3587	write32le(P: buf + i * 8 + 4, V: sym.cuVectorOff);
3588	}
3589
3590	buf += symtabSize * 8;
3591
3592	// Write the string pool.
3593	hdr->constantPoolOff = buf - start;
3594	parallelForEach(R&: symbols, Fn: [&](GdbSymbol &sym) {
3595	memcpy(dest: buf + sym.nameOff, src: sym.name.data(), n: sym.name.size());
3596	});
3597
3598	// Write the CU vectors.
3599	for (GdbSymbol &sym : symbols) {
3600	write32le(P: buf, V: sym.cuVector.size());
3601	buf += 4;
3602	for (uint32_t val : sym.cuVector) {
3603	write32le(P: buf, V: val);
3604	buf += 4;
3605	}
3606	}
3607	}
3608
3609	bool GdbIndexSection::isNeeded() const { return !chunks.empty(); }
3610
3611	EhFrameHeader::EhFrameHeader()
3612	: SyntheticSection(SHF_ALLOC, SHT_PROGBITS, 4, ".eh_frame_hdr") {}
3613
3614	void EhFrameHeader::writeTo(uint8_t *buf) {
3615	// Unlike most sections, the EhFrameHeader section is written while writing
3616	// another section, namely EhFrameSection, which calls the write() function
3617	// below from its writeTo() function. This is necessary because the contents
3618	// of EhFrameHeader depend on the relocated contents of EhFrameSection and we
3619	// don't know which order the sections will be written in.
3620	}
3621
3622	// .eh_frame_hdr contains a binary search table of pointers to FDEs.
3623	// Each entry of the search table consists of two values,
3624	// the starting PC from where FDEs covers, and the FDE's address.
3625	// It is sorted by PC.
3626	void EhFrameHeader::write() {
3627	uint8_t *buf = Out::bufferStart + getParent()->offset + outSecOff;
3628	using FdeData = EhFrameSection::FdeData;
3629	SmallVector<FdeData, 0> fdes = getPartition().ehFrame->getFdeData();
3630
3631	buf[0] = 1;
3632	buf[1] = DW_EH_PE_pcrel | DW_EH_PE_sdata4;
3633	buf[2] = DW_EH_PE_udata4;
3634	buf[3] = DW_EH_PE_datarel | DW_EH_PE_sdata4;
3635	write32(p: buf + 4,
3636	v: getPartition().ehFrame->getParent()->addr - this->getVA() - 4);
3637	write32(p: buf + 8, v: fdes.size());
3638	buf += 12;
3639
3640	for (FdeData &fde : fdes) {
3641	write32(p: buf, v: fde.pcRel);
3642	write32(p: buf + 4, v: fde.fdeVARel);
3643	buf += 8;
3644	}
3645	}
3646
3647	size_t EhFrameHeader::getSize() const {
3648	// .eh_frame_hdr has a 12 bytes header followed by an array of FDEs.
3649	return 12 + getPartition().ehFrame->numFdes * 8;
3650	}
3651
3652	bool EhFrameHeader::isNeeded() const {
3653	return isLive() && getPartition().ehFrame->isNeeded();
3654	}
3655
3656	VersionDefinitionSection::VersionDefinitionSection()
3657	: SyntheticSection(SHF_ALLOC, SHT_GNU_verdef, sizeof(uint32_t),
3658	".gnu.version_d") {}
3659
3660	StringRef VersionDefinitionSection::getFileDefName() {
3661	if (!getPartition().name.empty())
3662	return getPartition().name;
3663	if (!config->soName.empty())
3664	return config->soName;
3665	return config->outputFile;
3666	}
3667
3668	void VersionDefinitionSection::finalizeContents() {
3669	fileDefNameOff = getPartition().dynStrTab->addString(s: getFileDefName());
3670	for (const VersionDefinition &v : namedVersionDefs())
3671	verDefNameOffs.push_back(Elt: getPartition().dynStrTab->addString(s: v.name));
3672
3673	if (OutputSection *sec = getPartition().dynStrTab->getParent())
3674	getParent()->link = sec->sectionIndex;
3675
3676	// sh_info should be set to the number of definitions. This fact is missed in
3677	// documentation, but confirmed by binutils community:
3678	// https://sourceware.org/ml/binutils/2014-11/msg00355.html
3679	getParent()->info = getVerDefNum();
3680	}
3681
3682	void VersionDefinitionSection::writeOne(uint8_t *buf, uint32_t index,
3683	StringRef name, size_t nameOff) {
3684	uint16_t flags = index == 1 ? VER_FLG_BASE : 0;
3685
3686	// Write a verdef.
3687	write16(p: buf, v: 1); // vd_version
3688	write16(p: buf + 2, v: flags); // vd_flags
3689	write16(p: buf + 4, v: index); // vd_ndx
3690	write16(p: buf + 6, v: 1); // vd_cnt
3691	write32(p: buf + 8, v: hashSysV(SymbolName: name)); // vd_hash
3692	write32(p: buf + 12, v: 20); // vd_aux
3693	write32(p: buf + 16, v: 28); // vd_next
3694
3695	// Write a veraux.
3696	write32(p: buf + 20, v: nameOff); // vda_name
3697	write32(p: buf + 24, v: 0); // vda_next
3698	}
3699
3700	void VersionDefinitionSection::writeTo(uint8_t *buf) {
3701	writeOne(buf, index: 1, name: getFileDefName(), nameOff: fileDefNameOff);
3702
3703	auto nameOffIt = verDefNameOffs.begin();
3704	for (const VersionDefinition &v : namedVersionDefs()) {
3705	buf += EntrySize;
3706	writeOne(buf, index: v.id, name: v.name, nameOff: *nameOffIt++);
3707	}
3708
3709	// Need to terminate the last version definition.
3710	write32(p: buf + 16, v: 0); // vd_next
3711	}
3712
3713	size_t VersionDefinitionSection::getSize() const {
3714	return EntrySize * getVerDefNum();
3715	}
3716
3717	// .gnu.version is a table where each entry is 2 byte long.
3718	VersionTableSection::VersionTableSection()
3719	: SyntheticSection(SHF_ALLOC, SHT_GNU_versym, sizeof(uint16_t),
3720	".gnu.version") {
3721	this->entsize = 2;
3722	}
3723
3724	void VersionTableSection::finalizeContents() {
3725	// At the moment of june 2016 GNU docs does not mention that sh_link field
3726	// should be set, but Sun docs do. Also readelf relies on this field.
3727	getParent()->link = getPartition().dynSymTab->getParent()->sectionIndex;
3728	}
3729
3730	size_t VersionTableSection::getSize() const {
3731	return (getPartition().dynSymTab->getSymbols().size() + 1) * 2;
3732	}
3733
3734	void VersionTableSection::writeTo(uint8_t *buf) {
3735	buf += 2;
3736	for (const SymbolTableEntry &s : getPartition().dynSymTab->getSymbols()) {
3737	// For an unextracted lazy symbol (undefined weak), it must have been
3738	// converted to Undefined and have VER_NDX_GLOBAL version here.
3739	assert(!s.sym->isLazy());
3740	write16(p: buf, v: s.sym->versionId);
3741	buf += 2;
3742	}
3743	}
3744
3745	bool VersionTableSection::isNeeded() const {
3746	return isLive() &&
3747	(getPartition().verDef || getPartition().verNeed->isNeeded());
3748	}
3749
3750	void elf::addVerneed(Symbol *ss) {
3751	auto &file = cast<SharedFile>(Val&: *ss->file);
3752	if (ss->versionId == VER_NDX_GLOBAL)
3753	return;
3754
3755	if (file.vernauxs.empty())
3756	file.vernauxs.resize(N: file.verdefs.size());
3757
3758	// Select a version identifier for the vernaux data structure, if we haven't
3759	// already allocated one. The verdef identifiers cover the range
3760	// [1..getVerDefNum()]; this causes the vernaux identifiers to start from
3761	// getVerDefNum()+1.
3762	if (file.vernauxs[ss->versionId] == 0)
3763	file.vernauxs[ss->versionId] = ++SharedFile::vernauxNum + getVerDefNum();
3764
3765	ss->versionId = file.vernauxs[ss->versionId];
3766	}
3767
3768	template <class ELFT>
3769	VersionNeedSection<ELFT>::VersionNeedSection()
3770	: SyntheticSection(SHF_ALLOC, SHT_GNU_verneed, sizeof(uint32_t),
3771	".gnu.version_r") {}
3772
3773	template <class ELFT> void VersionNeedSection<ELFT>::finalizeContents() {
3774	for (SharedFile *f : ctx.sharedFiles) {
3775	if (f->vernauxs.empty())
3776	continue;
3777	verneeds.emplace_back();
3778	Verneed &vn = verneeds.back();
3779	vn.nameStrTab = getPartition().dynStrTab->addString(f->soName);
3780	bool isLibc = config->relrGlibc && f->soName.starts_with(Prefix: "libc.so.");
3781	bool isGlibc2 = false;
3782	for (unsigned i = 0; i != f->vernauxs.size(); ++i) {
3783	if (f->vernauxs[i] == 0)
3784	continue;
3785	auto *verdef =
3786	reinterpret_cast<const typename ELFT::Verdef *>(f->verdefs[i]);
3787	StringRef ver(f->getStringTable().data() + verdef->getAux()->vda_name);
3788	if (isLibc && ver.starts_with(Prefix: "GLIBC_2."))
3789	isGlibc2 = true;
3790	vn.vernauxs.push_back({verdef->vd_hash, f->vernauxs[i],
3791	getPartition().dynStrTab->addString(ver)});
3792	}
3793	if (isGlibc2) {
3794	const char *ver = "GLIBC_ABI_DT_RELR";
3795	vn.vernauxs.push_back({hashSysV(SymbolName: ver),
3796	++SharedFile::vernauxNum + getVerDefNum(),
3797	getPartition().dynStrTab->addString(ver)});
3798	}
3799	}
3800
3801	if (OutputSection *sec = getPartition().dynStrTab->getParent())
3802	getParent()->link = sec->sectionIndex;
3803	getParent()->info = verneeds.size();
3804	}
3805
3806	template <class ELFT> void VersionNeedSection<ELFT>::writeTo(uint8_t *buf) {
3807	// The Elf_Verneeds need to appear first, followed by the Elf_Vernauxs.
3808	auto *verneed = reinterpret_cast<Elf_Verneed *>(buf);
3809	auto *vernaux = reinterpret_cast<Elf_Vernaux *>(verneed + verneeds.size());
3810
3811	for (auto &vn : verneeds) {
3812	// Create an Elf_Verneed for this DSO.
3813	verneed->vn_version = 1;
3814	verneed->vn_cnt = vn.vernauxs.size();
3815	verneed->vn_file = vn.nameStrTab;
3816	verneed->vn_aux =
3817	reinterpret_cast<char *>(vernaux) - reinterpret_cast<char *>(verneed);
3818	verneed->vn_next = sizeof(Elf_Verneed);
3819	++verneed;
3820
3821	// Create the Elf_Vernauxs for this Elf_Verneed.
3822	for (auto &vna : vn.vernauxs) {
3823	vernaux->vna_hash = vna.hash;
3824	vernaux->vna_flags = 0;
3825	vernaux->vna_other = vna.verneedIndex;
3826	vernaux->vna_name = vna.nameStrTab;
3827	vernaux->vna_next = sizeof(Elf_Vernaux);
3828	++vernaux;
3829	}
3830
3831	vernaux[-1].vna_next = 0;
3832	}
3833	verneed[-1].vn_next = 0;
3834	}
3835
3836	template <class ELFT> size_t VersionNeedSection<ELFT>::getSize() const {
3837	return verneeds.size() * sizeof(Elf_Verneed) +
3838	SharedFile::vernauxNum * sizeof(Elf_Vernaux);
3839	}
3840
3841	template <class ELFT> bool VersionNeedSection<ELFT>::isNeeded() const {
3842	return isLive() && SharedFile::vernauxNum != 0;
3843	}
3844
3845	void MergeSyntheticSection::addSection(MergeInputSection *ms) {
3846	ms->parent = this;
3847	sections.push_back(Elt: ms);
3848	assert(addralign == ms->addralign || !(ms->flags & SHF_STRINGS));
3849	addralign = std::max(a: addralign, b: ms->addralign);
3850	}
3851
3852	MergeTailSection::MergeTailSection(StringRef name, uint32_t type,
3853	uint64_t flags, uint32_t alignment)
3854	: MergeSyntheticSection(name, type, flags, alignment),
3855	builder(StringTableBuilder::RAW, llvm::Align(alignment)) {}
3856
3857	size_t MergeTailSection::getSize() const { return builder.getSize(); }
3858
3859	void MergeTailSection::writeTo(uint8_t *buf) { builder.write(Buf: buf); }
3860
3861	void MergeTailSection::finalizeContents() {
3862	// Add all string pieces to the string table builder to create section
3863	// contents.
3864	for (MergeInputSection *sec : sections)
3865	for (size_t i = 0, e = sec->pieces.size(); i != e; ++i)
3866	if (sec->pieces[i].live)
3867	builder.add(S: sec->getData(i));
3868
3869	// Fix the string table content. After this, the contents will never change.
3870	builder.finalize();
3871
3872	// finalize() fixed tail-optimized strings, so we can now get
3873	// offsets of strings. Get an offset for each string and save it
3874	// to a corresponding SectionPiece for easy access.
3875	for (MergeInputSection *sec : sections)
3876	for (size_t i = 0, e = sec->pieces.size(); i != e; ++i)
3877	if (sec->pieces[i].live)
3878	sec->pieces[i].outputOff = builder.getOffset(S: sec->getData(i));
3879	}
3880
3881	void MergeNoTailSection::writeTo(uint8_t *buf) {
3882	parallelFor(Begin: 0, End: numShards,
3883	Fn: [&](size_t i) { shards[i].write(Buf: buf + shardOffsets[i]); });
3884	}
3885
3886	// This function is very hot (i.e. it can take several seconds to finish)
3887	// because sometimes the number of inputs is in an order of magnitude of
3888	// millions. So, we use multi-threading.
3889	//
3890	// For any strings S and T, we know S is not mergeable with T if S's hash
3891	// value is different from T's. If that's the case, we can safely put S and
3892	// T into different string builders without worrying about merge misses.
3893	// We do it in parallel.
3894	void MergeNoTailSection::finalizeContents() {
3895	// Initializes string table builders.
3896	for (size_t i = 0; i < numShards; ++i)
3897	shards.emplace_back(Args: StringTableBuilder::RAW, Args: llvm::Align(addralign));
3898
3899	// Concurrency level. Must be a power of 2 to avoid expensive modulo
3900	// operations in the following tight loop.
3901	const size_t concurrency =
3902	llvm::bit_floor(Value: std::min<size_t>(a: config->threadCount, b: numShards));
3903
3904	// Add section pieces to the builders.
3905	parallelFor(Begin: 0, End: concurrency, Fn: [&](size_t threadId) {
3906	for (MergeInputSection *sec : sections) {
3907	for (size_t i = 0, e = sec->pieces.size(); i != e; ++i) {
3908	if (!sec->pieces[i].live)
3909	continue;
3910	size_t shardId = getShardId(hash: sec->pieces[i].hash);
3911	if ((shardId & (concurrency - 1)) == threadId)
3912	sec->pieces[i].outputOff = shards[shardId].add(S: sec->getData(i));
3913	}
3914	}
3915	});
3916
3917	// Compute an in-section offset for each shard.
3918	size_t off = 0;
3919	for (size_t i = 0; i < numShards; ++i) {
3920	shards[i].finalizeInOrder();
3921	if (shards[i].getSize() > 0)
3922	off = alignToPowerOf2(Value: off, Align: addralign);
3923	shardOffsets[i] = off;
3924	off += shards[i].getSize();
3925	}
3926	size = off;
3927
3928	// So far, section pieces have offsets from beginning of shards, but
3929	// we want offsets from beginning of the whole section. Fix them.
3930	parallelForEach(R&: sections, Fn: [&](MergeInputSection *sec) {
3931	for (size_t i = 0, e = sec->pieces.size(); i != e; ++i)
3932	if (sec->pieces[i].live)
3933	sec->pieces[i].outputOff +=
3934	shardOffsets[getShardId(hash: sec->pieces[i].hash)];
3935	});
3936	}
3937
3938	template <class ELFT> void elf::splitSections() {
3939	llvm::TimeTraceScope timeScope("Split sections");
3940	// splitIntoPieces needs to be called on each MergeInputSection
3941	// before calling finalizeContents().
3942	parallelForEach(ctx.objectFiles, [](ELFFileBase *file) {
3943	for (InputSectionBase *sec : file->getSections()) {
3944	if (!sec)
3945	continue;
3946	if (auto *s = dyn_cast<MergeInputSection>(Val: sec))
3947	s->splitIntoPieces();
3948	else if (auto *eh = dyn_cast<EhInputSection>(Val: sec))
3949	eh->split<ELFT>();
3950	}
3951	});
3952	}
3953
3954	void elf::combineEhSections() {
3955	llvm::TimeTraceScope timeScope("Combine EH sections");
3956	for (EhInputSection *sec : ctx.ehInputSections) {
3957	EhFrameSection &eh = *sec->getPartition().ehFrame;
3958	sec->parent = &eh;
3959	eh.addralign = std::max(a: eh.addralign, b: sec->addralign);
3960	eh.sections.push_back(Elt: sec);
3961	llvm::append_range(C&: eh.dependentSections, R&: sec->dependentSections);
3962	}
3963
3964	if (!mainPart->armExidx)
3965	return;
3966	llvm::erase_if(C&: ctx.inputSections, P: [](InputSectionBase *s) {
3967	// Ignore dead sections and the partition end marker (.part.end),
3968	// whose partition number is out of bounds.
3969	if (!s->isLive() || s->partition == 255)
3970	return false;
3971	Partition &part = s->getPartition();
3972	return s->kind() == SectionBase::Regular && part.armExidx &&
3973	part.armExidx->addSection(isec: cast<InputSection>(Val: s));
3974	});
3975	}
3976
3977	MipsRldMapSection::MipsRldMapSection()
3978	: SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, config->wordsize,
3979	".rld_map") {}
3980
3981	ARMExidxSyntheticSection::ARMExidxSyntheticSection()
3982	: SyntheticSection(SHF_ALLOC | SHF_LINK_ORDER, SHT_ARM_EXIDX,
3983	config->wordsize, ".ARM.exidx") {}
3984
3985	static InputSection *findExidxSection(InputSection *isec) {
3986	for (InputSection *d : isec->dependentSections)
3987	if (d->type == SHT_ARM_EXIDX && d->isLive())
3988	return d;
3989	return nullptr;
3990	}
3991
3992	static bool isValidExidxSectionDep(InputSection *isec) {
3993	return (isec->flags & SHF_ALLOC) && (isec->flags & SHF_EXECINSTR) &&
3994	isec->getSize() > 0;
3995	}
3996
3997	bool ARMExidxSyntheticSection::addSection(InputSection *isec) {
3998	if (isec->type == SHT_ARM_EXIDX) {
3999	if (InputSection *dep = isec->getLinkOrderDep())
4000	if (isValidExidxSectionDep(isec: dep)) {
4001	exidxSections.push_back(Elt: isec);
4002	// Every exidxSection is 8 bytes, we need an estimate of
4003	// size before assignAddresses can be called. Final size
4004	// will only be known after finalize is called.
4005	size += 8;
4006	}
4007	return true;
4008	}
4009
4010	if (isValidExidxSectionDep(isec)) {
4011	executableSections.push_back(Elt: isec);
4012	return false;
4013	}
4014
4015	// FIXME: we do not output a relocation section when --emit-relocs is used
4016	// as we do not have relocation sections for linker generated table entries
4017	// and we would have to erase at a late stage relocations from merged entries.
4018	// Given that exception tables are already position independent and a binary
4019	// analyzer could derive the relocations we choose to erase the relocations.
4020	if (config->emitRelocs && isec->type == SHT_REL)
4021	if (InputSectionBase *ex = isec->getRelocatedSection())
4022	if (isa<InputSection>(Val: ex) && ex->type == SHT_ARM_EXIDX)
4023	return true;
4024
4025	return false;
4026	}
4027
4028	// References to .ARM.Extab Sections have bit 31 clear and are not the
4029	// special EXIDX_CANTUNWIND bit-pattern.
4030	static bool isExtabRef(uint32_t unwind) {
4031	return (unwind & 0x80000000) == 0 && unwind != 0x1;
4032	}
4033
4034	// Return true if the .ARM.exidx section Cur can be merged into the .ARM.exidx
4035	// section Prev, where Cur follows Prev in the table. This can be done if the
4036	// unwinding instructions in Cur are identical to Prev. Linker generated
4037	// EXIDX_CANTUNWIND entries are represented by nullptr as they do not have an
4038	// InputSection.
4039	static bool isDuplicateArmExidxSec(InputSection *prev, InputSection *cur) {
4040	// Get the last table Entry from the previous .ARM.exidx section. If Prev is
4041	// nullptr then it will be a synthesized EXIDX_CANTUNWIND entry.
4042	uint32_t prevUnwind = 1;
4043	if (prev)
4044	prevUnwind = read32(p: prev->content().data() + prev->content().size() - 4);
4045	if (isExtabRef(unwind: prevUnwind))
4046	return false;
4047
4048	// We consider the unwind instructions of an .ARM.exidx table entry
4049	// a duplicate if the previous unwind instructions if:
4050	// - Both are the special EXIDX_CANTUNWIND.
4051	// - Both are the same inline unwind instructions.
4052	// We do not attempt to follow and check links into .ARM.extab tables as
4053	// consecutive identical entries are rare and the effort to check that they
4054	// are identical is high.
4055
4056	// If Cur is nullptr then this is synthesized EXIDX_CANTUNWIND entry.
4057	if (cur == nullptr)
4058	return prevUnwind == 1;
4059
4060	for (uint32_t offset = 4; offset < (uint32_t)cur->content().size(); offset +=8) {
4061	uint32_t curUnwind = read32(p: cur->content().data() + offset);
4062	if (isExtabRef(unwind: curUnwind) || curUnwind != prevUnwind)
4063	return false;
4064	}
4065	// All table entries in this .ARM.exidx Section can be merged into the
4066	// previous Section.
4067	return true;
4068	}
4069
4070	// The .ARM.exidx table must be sorted in ascending order of the address of the
4071	// functions the table describes. std::optionally duplicate adjacent table
4072	// entries can be removed. At the end of the function the executableSections
4073	// must be sorted in ascending order of address, Sentinel is set to the
4074	// InputSection with the highest address and any InputSections that have
4075	// mergeable .ARM.exidx table entries are removed from it.
4076	void ARMExidxSyntheticSection::finalizeContents() {
4077	// The executableSections and exidxSections that we use to derive the final
4078	// contents of this SyntheticSection are populated before
4079	// processSectionCommands() and ICF. A /DISCARD/ entry in SECTIONS command or
4080	// ICF may remove executable InputSections and their dependent .ARM.exidx
4081	// section that we recorded earlier.
4082	auto isDiscarded = [](const InputSection *isec) { return !isec->isLive(); };
4083	llvm::erase_if(C&: exidxSections, P: isDiscarded);
4084	// We need to remove discarded InputSections and InputSections without
4085	// .ARM.exidx sections that if we generated the .ARM.exidx it would be out
4086	// of range.
4087	auto isDiscardedOrOutOfRange = [this](InputSection *isec) {
4088	if (!isec->isLive())
4089	return true;
4090	if (findExidxSection(isec))
4091	return false;
4092	int64_t off = static_cast<int64_t>(isec->getVA() - getVA());
4093	return off != llvm::SignExtend64(X: off, B: 31);
4094	};
4095	llvm::erase_if(C&: executableSections, P: isDiscardedOrOutOfRange);
4096
4097	// Sort the executable sections that may or may not have associated
4098	// .ARM.exidx sections by order of ascending address. This requires the
4099	// relative positions of InputSections and OutputSections to be known.
4100	auto compareByFilePosition = [](const InputSection *a,
4101	const InputSection *b) {
4102	OutputSection *aOut = a->getParent();
4103	OutputSection *bOut = b->getParent();
4104
4105	if (aOut != bOut)
4106	return aOut->addr < bOut->addr;
4107	return a->outSecOff < b->outSecOff;
4108	};
4109	llvm::stable_sort(Range&: executableSections, C: compareByFilePosition);
4110	sentinel = executableSections.back();
4111	// std::optionally merge adjacent duplicate entries.
4112	if (config->mergeArmExidx) {
4113	SmallVector<InputSection *, 0> selectedSections;
4114	selectedSections.reserve(N: executableSections.size());
4115	selectedSections.push_back(Elt: executableSections[0]);
4116	size_t prev = 0;
4117	for (size_t i = 1; i < executableSections.size(); ++i) {
4118	InputSection *ex1 = findExidxSection(isec: executableSections[prev]);
4119	InputSection *ex2 = findExidxSection(isec: executableSections[i]);
4120	if (!isDuplicateArmExidxSec(prev: ex1, cur: ex2)) {
4121	selectedSections.push_back(Elt: executableSections[i]);
4122	prev = i;
4123	}
4124	}
4125	executableSections = std::move(selectedSections);
4126	}
4127	// offset is within the SyntheticSection.
4128	size_t offset = 0;
4129	size = 0;
4130	for (InputSection *isec : executableSections) {
4131	if (InputSection *d = findExidxSection(isec)) {
4132	d->outSecOff = offset;
4133	d->parent = getParent();
4134	offset += d->getSize();
4135	} else {
4136	offset += 8;
4137	}
4138	}
4139	// Size includes Sentinel.
4140	size = offset + 8;
4141	}
4142
4143	InputSection *ARMExidxSyntheticSection::getLinkOrderDep() const {
4144	return executableSections.front();
4145	}
4146
4147	// To write the .ARM.exidx table from the ExecutableSections we have three cases
4148	// 1.) The InputSection has a .ARM.exidx InputSection in its dependent sections.
4149	// We write the .ARM.exidx section contents and apply its relocations.
4150	// 2.) The InputSection does not have a dependent .ARM.exidx InputSection. We
4151	// must write the contents of an EXIDX_CANTUNWIND directly. We use the
4152	// start of the InputSection as the purpose of the linker generated
4153	// section is to terminate the address range of the previous entry.
4154	// 3.) A trailing EXIDX_CANTUNWIND sentinel section is required at the end of
4155	// the table to terminate the address range of the final entry.
4156	void ARMExidxSyntheticSection::writeTo(uint8_t *buf) {
4157
4158	// A linker generated CANTUNWIND entry is made up of two words:
4159	// 0x0 with R_ARM_PREL31 relocation to target.
4160	// 0x1 with EXIDX_CANTUNWIND.
4161	uint64_t offset = 0;
4162	for (InputSection *isec : executableSections) {
4163	assert(isec->getParent() != nullptr);
4164	if (InputSection *d = findExidxSection(isec)) {
4165	for (int dataOffset = 0; dataOffset != (int)d->content().size();
4166	dataOffset += 4)
4167	write32(p: buf + offset + dataOffset,
4168	v: read32(p: d->content().data() + dataOffset));
4169	// Recalculate outSecOff as finalizeAddressDependentContent()
4170	// may have altered syntheticSection outSecOff.
4171	d->outSecOff = offset + outSecOff;
4172	target->relocateAlloc(sec&: *d, buf: buf + offset);
4173	offset += d->getSize();
4174	} else {
4175	// A Linker generated CANTUNWIND section.
4176	write32(p: buf + offset + 0, v: 0x0);
4177	write32(p: buf + offset + 4, v: 0x1);
4178	uint64_t s = isec->getVA();
4179	uint64_t p = getVA() + offset;
4180	target->relocateNoSym(loc: buf + offset, type: R_ARM_PREL31, val: s - p);
4181	offset += 8;
4182	}
4183	}
4184	// Write Sentinel CANTUNWIND entry.
4185	write32(p: buf + offset + 0, v: 0x0);
4186	write32(p: buf + offset + 4, v: 0x1);
4187	uint64_t s = sentinel->getVA(offset: sentinel->getSize());
4188	uint64_t p = getVA() + offset;
4189	target->relocateNoSym(loc: buf + offset, type: R_ARM_PREL31, val: s - p);
4190	assert(size == offset + 8);
4191	}
4192
4193	bool ARMExidxSyntheticSection::isNeeded() const {
4194	return llvm::any_of(Range: exidxSections,
4195	P: [](InputSection *isec) { return isec->isLive(); });
4196	}
4197
4198	ThunkSection::ThunkSection(OutputSection *os, uint64_t off)
4199	: SyntheticSection(SHF_ALLOC | SHF_EXECINSTR, SHT_PROGBITS,
4200	config->emachine == EM_PPC64 ? 16 : 4, ".text.thunk") {
4201	this->parent = os;
4202	this->outSecOff = off;
4203	}
4204
4205	size_t ThunkSection::getSize() const {
4206	if (roundUpSizeForErrata)
4207	return alignTo(Value: size, Align: 4096);
4208	return size;
4209	}
4210
4211	void ThunkSection::addThunk(Thunk *t) {
4212	thunks.push_back(Elt: t);
4213	t->addSymbols(isec&: *this);
4214	}
4215
4216	void ThunkSection::writeTo(uint8_t *buf) {
4217	for (Thunk *t : thunks)
4218	t->writeTo(buf: buf + t->offset);
4219	}
4220
4221	InputSection *ThunkSection::getTargetInputSection() const {
4222	if (thunks.empty())
4223	return nullptr;
4224	const Thunk *t = thunks.front();
4225	return t->getTargetInputSection();
4226	}
4227
4228	bool ThunkSection::assignOffsets() {
4229	uint64_t off = 0;
4230	for (Thunk *t : thunks) {
4231	off = alignToPowerOf2(Value: off, Align: t->alignment);
4232	t->setOffset(off);
4233	uint32_t size = t->size();
4234	t->getThunkTargetSym()->size = size;
4235	off += size;
4236	}
4237	bool changed = off != size;
4238	size = off;
4239	return changed;
4240	}
4241
4242	PPC32Got2Section::PPC32Got2Section()
4243	: SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, 4, ".got2") {}
4244
4245	bool PPC32Got2Section::isNeeded() const {
4246	// See the comment below. This is not needed if there is no other
4247	// InputSection.
4248	for (SectionCommand *cmd : getParent()->commands)
4249	if (auto *isd = dyn_cast<InputSectionDescription>(Val: cmd))
4250	for (InputSection *isec : isd->sections)
4251	if (isec != this)
4252	return true;
4253	return false;
4254	}
4255
4256	void PPC32Got2Section::finalizeContents() {
4257	// PPC32 may create multiple GOT sections for -fPIC/-fPIE, one per file in
4258	// .got2 . This function computes outSecOff of each .got2 to be used in
4259	// PPC32PltCallStub::writeTo(). The purpose of this empty synthetic section is
4260	// to collect input sections named ".got2".
4261	for (SectionCommand *cmd : getParent()->commands)
4262	if (auto *isd = dyn_cast<InputSectionDescription>(Val: cmd)) {
4263	for (InputSection *isec : isd->sections) {
4264	// isec->file may be nullptr for MergeSyntheticSection.
4265	if (isec != this && isec->file)
4266	isec->file->ppc32Got2 = isec;
4267	}
4268	}
4269	}
4270
4271	// If linking position-dependent code then the table will store the addresses
4272	// directly in the binary so the section has type SHT_PROGBITS. If linking
4273	// position-independent code the section has type SHT_NOBITS since it will be
4274	// allocated and filled in by the dynamic linker.
4275	PPC64LongBranchTargetSection::PPC64LongBranchTargetSection()
4276	: SyntheticSection(SHF_ALLOC | SHF_WRITE,
4277	config->isPic ? SHT_NOBITS : SHT_PROGBITS, 8,
4278	".branch_lt") {}
4279
4280	uint64_t PPC64LongBranchTargetSection::getEntryVA(const Symbol *sym,
4281	int64_t addend) {
4282	return getVA() + entry_index.find(Val: {sym, addend})->second * 8;
4283	}
4284
4285	std::optional<uint32_t>
4286	PPC64LongBranchTargetSection::addEntry(const Symbol *sym, int64_t addend) {
4287	auto res =
4288	entry_index.try_emplace(Key: std::make_pair(x&: sym, y&: addend), Args: entries.size());
4289	if (!res.second)
4290	return std::nullopt;
4291	entries.emplace_back(Args&: sym, Args&: addend);
4292	return res.first->second;
4293	}
4294
4295	size_t PPC64LongBranchTargetSection::getSize() const {
4296	return entries.size() * 8;
4297	}
4298
4299	void PPC64LongBranchTargetSection::writeTo(uint8_t *buf) {
4300	// If linking non-pic we have the final addresses of the targets and they get
4301	// written to the table directly. For pic the dynamic linker will allocate
4302	// the section and fill it.
4303	if (config->isPic)
4304	return;
4305
4306	for (auto entry : entries) {
4307	const Symbol *sym = entry.first;
4308	int64_t addend = entry.second;
4309	assert(sym->getVA());
4310	// Need calls to branch to the local entry-point since a long-branch
4311	// must be a local-call.
4312	write64(p: buf, v: sym->getVA(addend) +
4313	getPPC64GlobalEntryToLocalEntryOffset(stOther: sym->stOther));
4314	buf += 8;
4315	}
4316	}
4317
4318	bool PPC64LongBranchTargetSection::isNeeded() const {
4319	// `removeUnusedSyntheticSections()` is called before thunk allocation which
4320	// is too early to determine if this section will be empty or not. We need
4321	// Finalized to keep the section alive until after thunk creation. Finalized
4322	// only gets set to true once `finalizeSections()` is called after thunk
4323	// creation. Because of this, if we don't create any long-branch thunks we end
4324	// up with an empty .branch_lt section in the binary.
4325	return !finalized || !entries.empty();
4326	}
4327
4328	static uint8_t getAbiVersion() {
4329	// MIPS non-PIC executable gets ABI version 1.
4330	if (config->emachine == EM_MIPS) {
4331	if (!config->isPic && !config->relocatable &&
4332	(config->eflags & (EF_MIPS_PIC | EF_MIPS_CPIC)) == EF_MIPS_CPIC)
4333	return 1;
4334	return 0;
4335	}
4336
4337	if (config->emachine == EM_AMDGPU && !ctx.objectFiles.empty()) {
4338	uint8_t ver = ctx.objectFiles[0]->abiVersion;
4339	for (InputFile *file : ArrayRef(ctx.objectFiles).slice(N: 1))
4340	if (file->abiVersion != ver)
4341	error(msg: "incompatible ABI version: " + toString(f: file));
4342	return ver;
4343	}
4344
4345	return 0;
4346	}
4347
4348	template <typename ELFT> void elf::writeEhdr(uint8_t *buf, Partition &part) {
4349	memcpy(dest: buf, src: "\177ELF", n: 4);
4350
4351	auto *eHdr = reinterpret_cast<typename ELFT::Ehdr *>(buf);
4352	eHdr->e_ident[EI_CLASS] = ELFT::Is64Bits ? ELFCLASS64 : ELFCLASS32;
4353	eHdr->e_ident[EI_DATA] =
4354	ELFT::Endianness == endianness::little ? ELFDATA2LSB : ELFDATA2MSB;
4355	eHdr->e_ident[EI_VERSION] = EV_CURRENT;
4356	eHdr->e_ident[EI_OSABI] = config->osabi;
4357	eHdr->e_ident[EI_ABIVERSION] = getAbiVersion();
4358	eHdr->e_machine = config->emachine;
4359	eHdr->e_version = EV_CURRENT;
4360	eHdr->e_flags = config->eflags;
4361	eHdr->e_ehsize = sizeof(typename ELFT::Ehdr);
4362	eHdr->e_phnum = part.phdrs.size();
4363	eHdr->e_shentsize = sizeof(typename ELFT::Shdr);
4364
4365	if (!config->relocatable) {
4366	eHdr->e_phoff = sizeof(typename ELFT::Ehdr);
4367	eHdr->e_phentsize = sizeof(typename ELFT::Phdr);
4368	}
4369	}
4370
4371	template <typename ELFT> void elf::writePhdrs(uint8_t *buf, Partition &part) {
4372	// Write the program header table.
4373	auto *hBuf = reinterpret_cast<typename ELFT::Phdr *>(buf);
4374	for (PhdrEntry *p : part.phdrs) {
4375	hBuf->p_type = p->p_type;
4376	hBuf->p_flags = p->p_flags;
4377	hBuf->p_offset = p->p_offset;
4378	hBuf->p_vaddr = p->p_vaddr;
4379	hBuf->p_paddr = p->p_paddr;
4380	hBuf->p_filesz = p->p_filesz;
4381	hBuf->p_memsz = p->p_memsz;
4382	hBuf->p_align = p->p_align;
4383	++hBuf;
4384	}
4385	}
4386
4387	template <typename ELFT>
4388	PartitionElfHeaderSection<ELFT>::PartitionElfHeaderSection()
4389	: SyntheticSection(SHF_ALLOC, SHT_LLVM_PART_EHDR, 1, "") {}
4390
4391	template <typename ELFT>
4392	size_t PartitionElfHeaderSection<ELFT>::getSize() const {
4393	return sizeof(typename ELFT::Ehdr);
4394	}
4395
4396	template <typename ELFT>
4397	void PartitionElfHeaderSection<ELFT>::writeTo(uint8_t *buf) {
4398	writeEhdr<ELFT>(buf, getPartition());
4399
4400	// Loadable partitions are always ET_DYN.
4401	auto *eHdr = reinterpret_cast<typename ELFT::Ehdr *>(buf);
4402	eHdr->e_type = ET_DYN;
4403	}
4404
4405	template <typename ELFT>
4406	PartitionProgramHeadersSection<ELFT>::PartitionProgramHeadersSection()
4407	: SyntheticSection(SHF_ALLOC, SHT_LLVM_PART_PHDR, 1, ".phdrs") {}
4408
4409	template <typename ELFT>
4410	size_t PartitionProgramHeadersSection<ELFT>::getSize() const {
4411	return sizeof(typename ELFT::Phdr) * getPartition().phdrs.size();
4412	}
4413
4414	template <typename ELFT>
4415	void PartitionProgramHeadersSection<ELFT>::writeTo(uint8_t *buf) {
4416	writePhdrs<ELFT>(buf, getPartition());
4417	}
4418
4419	PartitionIndexSection::PartitionIndexSection()
4420	: SyntheticSection(SHF_ALLOC, SHT_PROGBITS, 4, ".rodata") {}
4421
4422	size_t PartitionIndexSection::getSize() const {
4423	return 12 * (partitions.size() - 1);
4424	}
4425
4426	void PartitionIndexSection::finalizeContents() {
4427	for (size_t i = 1; i != partitions.size(); ++i)
4428	partitions[i].nameStrTab = mainPart->dynStrTab->addString(s: partitions[i].name);
4429	}
4430
4431	void PartitionIndexSection::writeTo(uint8_t *buf) {
4432	uint64_t va = getVA();
4433	for (size_t i = 1; i != partitions.size(); ++i) {
4434	write32(p: buf, v: mainPart->dynStrTab->getVA() + partitions[i].nameStrTab - va);
4435	write32(p: buf + 4, v: partitions[i].elfHeader->getVA() - (va + 4));
4436
4437	SyntheticSection *next = i == partitions.size() - 1
4438	? in.partEnd.get()
4439	: partitions[i + 1].elfHeader.get();
4440	write32(p: buf + 8, v: next->getVA() - partitions[i].elfHeader->getVA());
4441
4442	va += 12;
4443	buf += 12;
4444	}
4445	}
4446
4447	void InStruct::reset() {
4448	attributes.reset();
4449	riscvAttributes.reset();
4450	bss.reset();
4451	bssRelRo.reset();
4452	got.reset();
4453	gotPlt.reset();
4454	igotPlt.reset();
4455	relroPadding.reset();
4456	armCmseSGSection.reset();
4457	ppc64LongBranchTarget.reset();
4458	mipsAbiFlags.reset();
4459	mipsGot.reset();
4460	mipsOptions.reset();
4461	mipsReginfo.reset();
4462	mipsRldMap.reset();
4463	partEnd.reset();
4464	partIndex.reset();
4465	plt.reset();
4466	iplt.reset();
4467	ppc32Got2.reset();
4468	ibtPlt.reset();
4469	relaPlt.reset();
4470	debugNames.reset();
4471	gdbIndex.reset();
4472	shStrTab.reset();
4473	strTab.reset();
4474	symTab.reset();
4475	symTabShndx.reset();
4476	}
4477
4478	static bool needsInterpSection() {
4479	return !config->relocatable && !config->shared &&
4480	!config->dynamicLinker.empty() && script->needsInterpSection();
4481	}
4482
4483	bool elf::hasMemtag() {
4484	return config->emachine == EM_AARCH64 &&
4485	config->androidMemtagMode != ELF::NT_MEMTAG_LEVEL_NONE;
4486	}
4487
4488	// Fully static executables don't support MTE globals at this point in time, as
4489	// we currently rely on:
4490	// - A dynamic loader to process relocations, and
4491	// - Dynamic entries.
4492	// This restriction could be removed in future by re-using some of the ideas
4493	// that ifuncs use in fully static executables.
4494	bool elf::canHaveMemtagGlobals() {
4495	return hasMemtag() &&
4496	(config->relocatable || config->shared || needsInterpSection());
4497	}
4498
4499	constexpr char kMemtagAndroidNoteName[] = "Android";
4500	void MemtagAndroidNote::writeTo(uint8_t *buf) {
4501	static_assert(
4502	sizeof(kMemtagAndroidNoteName) == 8,
4503	"Android 11 & 12 have an ABI that the note name is 8 bytes long. Keep it "
4504	"that way for backwards compatibility.");
4505
4506	write32(p: buf, v: sizeof(kMemtagAndroidNoteName));
4507	write32(p: buf + 4, v: sizeof(uint32_t));
4508	write32(p: buf + 8, v: ELF::NT_ANDROID_TYPE_MEMTAG);
4509	memcpy(dest: buf + 12, src: kMemtagAndroidNoteName, n: sizeof(kMemtagAndroidNoteName));
4510	buf += 12 + alignTo(Value: sizeof(kMemtagAndroidNoteName), Align: 4);
4511
4512	uint32_t value = 0;
4513	value |= config->androidMemtagMode;
4514	if (config->androidMemtagHeap)
4515	value |= ELF::NT_MEMTAG_HEAP;
4516	// Note, MTE stack is an ABI break. Attempting to run an MTE stack-enabled
4517	// binary on Android 11 or 12 will result in a checkfail in the loader.
4518	if (config->androidMemtagStack)
4519	value |= ELF::NT_MEMTAG_STACK;
4520	write32(p: buf, v: value); // note value
4521	}
4522
4523	size_t MemtagAndroidNote::getSize() const {
4524	return sizeof(llvm::ELF::Elf64_Nhdr) +
4525	/*namesz=*/alignTo(Value: sizeof(kMemtagAndroidNoteName), Align: 4) +
4526	/*descsz=*/sizeof(uint32_t);
4527	}
4528
4529	void PackageMetadataNote::writeTo(uint8_t *buf) {
4530	write32(p: buf, v: 4);
4531	write32(p: buf + 4, v: config->packageMetadata.size() + 1);
4532	write32(p: buf + 8, v: FDO_PACKAGING_METADATA);
4533	memcpy(dest: buf + 12, src: "FDO", n: 4);
4534	memcpy(dest: buf + 16, src: config->packageMetadata.data(),
4535	n: config->packageMetadata.size());
4536	}
4537
4538	size_t PackageMetadataNote::getSize() const {
4539	return sizeof(llvm::ELF::Elf64_Nhdr) + 4 +
4540	alignTo(Value: config->packageMetadata.size() + 1, Align: 4);
4541	}
4542
4543	// Helper function, return the size of the ULEB128 for 'v', optionally writing
4544	// it to `*(buf + offset)` if `buf` is non-null.
4545	static size_t computeOrWriteULEB128(uint64_t v, uint8_t *buf, size_t offset) {
4546	if (buf)
4547	return encodeULEB128(Value: v, p: buf + offset);
4548	return getULEB128Size(Value: v);
4549	}
4550
4551	// https://github.com/ARM-software/abi-aa/blob/main/memtagabielf64/memtagabielf64.rst#83encoding-of-sht_aarch64_memtag_globals_dynamic
4552	constexpr uint64_t kMemtagStepSizeBits = 3;
4553	constexpr uint64_t kMemtagGranuleSize = 16;
4554	static size_t
4555	createMemtagGlobalDescriptors(const SmallVector<const Symbol *, 0> &symbols,
4556	uint8_t *buf = nullptr) {
4557	size_t sectionSize = 0;
4558	uint64_t lastGlobalEnd = 0;
4559
4560	for (const Symbol *sym : symbols) {
4561	if (!includeInSymtab(b: *sym))
4562	continue;
4563	const uint64_t addr = sym->getVA();
4564	const uint64_t size = sym->getSize();
4565
4566	if (addr <= kMemtagGranuleSize && buf != nullptr)
4567	errorOrWarn(msg: "address of the tagged symbol \"" + sym->getName() +
4568	"\" falls in the ELF header. This is indicative of a "
4569	"compiler/linker bug");
4570	if (addr % kMemtagGranuleSize != 0)
4571	errorOrWarn(msg: "address of the tagged symbol \"" + sym->getName() +
4572	"\" at 0x" + Twine::utohexstr(Val: addr) +
4573	"\" is not granule (16-byte) aligned");
4574	if (size == 0)
4575	errorOrWarn(msg: "size of the tagged symbol \"" + sym->getName() +
4576	"\" is not allowed to be zero");
4577	if (size % kMemtagGranuleSize != 0)
4578	errorOrWarn(msg: "size of the tagged symbol \"" + sym->getName() +
4579	"\" (size 0x" + Twine::utohexstr(Val: size) +
4580	") is not granule (16-byte) aligned");
4581
4582	const uint64_t sizeToEncode = size / kMemtagGranuleSize;
4583	const uint64_t stepToEncode = ((addr - lastGlobalEnd) / kMemtagGranuleSize)
4584	<< kMemtagStepSizeBits;
4585	if (sizeToEncode < (1 << kMemtagStepSizeBits)) {
4586	sectionSize += computeOrWriteULEB128(v: stepToEncode | sizeToEncode, buf, offset: sectionSize);
4587	} else {
4588	sectionSize += computeOrWriteULEB128(v: stepToEncode, buf, offset: sectionSize);
4589	sectionSize += computeOrWriteULEB128(v: sizeToEncode - 1, buf, offset: sectionSize);
4590	}
4591	lastGlobalEnd = addr + size;
4592	}
4593
4594	return sectionSize;
4595	}
4596
4597	bool MemtagGlobalDescriptors::updateAllocSize() {
4598	size_t oldSize = getSize();
4599	std::stable_sort(first: symbols.begin(), last: symbols.end(),
4600	comp: [](const Symbol *s1, const Symbol *s2) {
4601	return s1->getVA() < s2->getVA();
4602	});
4603	return oldSize != getSize();
4604	}
4605
4606	void MemtagGlobalDescriptors::writeTo(uint8_t *buf) {
4607	createMemtagGlobalDescriptors(symbols, buf);
4608	}
4609
4610	size_t MemtagGlobalDescriptors::getSize() const {
4611	return createMemtagGlobalDescriptors(symbols);
4612	}
4613
4614	static OutputSection *findSection(StringRef name) {
4615	for (SectionCommand *cmd : script->sectionCommands)
4616	if (auto *osd = dyn_cast<OutputDesc>(Val: cmd))
4617	if (osd->osec.name == name)
4618	return &osd->osec;
4619	return nullptr;
4620	}
4621
4622	static Defined *addOptionalRegular(StringRef name, SectionBase *sec,
4623	uint64_t val, uint8_t stOther = STV_HIDDEN) {
4624	Symbol *s = symtab.find(name);
4625	if (!s || s->isDefined() || s->isCommon())
4626	return nullptr;
4627
4628	s->resolve(other: Defined{ctx.internalFile, StringRef(), STB_GLOBAL, stOther,
4629	STT_NOTYPE, val,
4630	/*size=*/0, sec});
4631	s->isUsedInRegularObj = true;
4632	return cast<Defined>(Val: s);
4633	}
4634
4635	template <class ELFT> void elf::createSyntheticSections() {
4636	// Initialize all pointers with NULL. This is needed because
4637	// you can call lld::elf::main more than once as a library.
4638	Out::tlsPhdr = nullptr;
4639	Out::preinitArray = nullptr;
4640	Out::initArray = nullptr;
4641	Out::finiArray = nullptr;
4642
4643	// Add the .interp section first because it is not a SyntheticSection.
4644	// The removeUnusedSyntheticSections() function relies on the
4645	// SyntheticSections coming last.
4646	if (needsInterpSection()) {
4647	for (size_t i = 1; i <= partitions.size(); ++i) {
4648	InputSection *sec = createInterpSection();
4649	sec->partition = i;
4650	ctx.inputSections.push_back(Elt: sec);
4651	}
4652	}
4653
4654	auto add = [](SyntheticSection &sec) { ctx.inputSections.push_back(Elt: &sec); };
4655
4656	in.shStrTab = std::make_unique<StringTableSection>(args: ".shstrtab", args: false);
4657
4658	Out::programHeaders = make<OutputSection>(args: "", args: 0, args: SHF_ALLOC);
4659	Out::programHeaders->addralign = config->wordsize;
4660
4661	if (config->strip != StripPolicy::All) {
4662	in.strTab = std::make_unique<StringTableSection>(args: ".strtab", args: false);
4663	in.symTab = std::make_unique<SymbolTableSection<ELFT>>(*in.strTab);
4664	in.symTabShndx = std::make_unique<SymtabShndxSection>();
4665	}
4666
4667	in.bss = std::make_unique<BssSection>(args: ".bss", args: 0, args: 1);
4668	add(*in.bss);
4669
4670	// If there is a SECTIONS command and a .data.rel.ro section name use name
4671	// .data.rel.ro.bss so that we match in the .data.rel.ro output section.
4672	// This makes sure our relro is contiguous.
4673	bool hasDataRelRo = script->hasSectionsCommand && findSection(name: ".data.rel.ro");
4674	in.bssRelRo = std::make_unique<BssSection>(
4675	args: hasDataRelRo ? ".data.rel.ro.bss" : ".bss.rel.ro", args: 0, args: 1);
4676	add(*in.bssRelRo);
4677
4678	// Add MIPS-specific sections.
4679	if (config->emachine == EM_MIPS) {
4680	if (!config->shared && config->hasDynSymTab) {
4681	in.mipsRldMap = std::make_unique<MipsRldMapSection>();
4682	add(*in.mipsRldMap);
4683	}
4684	if ((in.mipsAbiFlags = MipsAbiFlagsSection<ELFT>::create()))
4685	add(*in.mipsAbiFlags);
4686	if ((in.mipsOptions = MipsOptionsSection<ELFT>::create()))
4687	add(*in.mipsOptions);
4688	if ((in.mipsReginfo = MipsReginfoSection<ELFT>::create()))
4689	add(*in.mipsReginfo);
4690	}
4691
4692	StringRef relaDynName = config->isRela ? ".rela.dyn" : ".rel.dyn";
4693
4694	const unsigned threadCount = config->threadCount;
4695	for (Partition &part : partitions) {
4696	auto add = [&](SyntheticSection &sec) {
4697	sec.partition = part.getNumber();
4698	ctx.inputSections.push_back(Elt: &sec);
4699	};
4700
4701	if (!part.name.empty()) {
4702	part.elfHeader = std::make_unique<PartitionElfHeaderSection<ELFT>>();
4703	part.elfHeader->name = part.name;
4704	add(*part.elfHeader);
4705
4706	part.programHeaders =
4707	std::make_unique<PartitionProgramHeadersSection<ELFT>>();
4708	add(*part.programHeaders);
4709	}
4710
4711	if (config->buildId != BuildIdKind::None) {
4712	part.buildId = std::make_unique<BuildIdSection>();
4713	add(*part.buildId);
4714	}
4715
4716	part.dynStrTab = std::make_unique<StringTableSection>(args: ".dynstr", args: true);
4717	part.dynSymTab =
4718	std::make_unique<SymbolTableSection<ELFT>>(*part.dynStrTab);
4719	part.dynamic = std::make_unique<DynamicSection<ELFT>>();
4720
4721	if (hasMemtag()) {
4722	part.memtagAndroidNote = std::make_unique<MemtagAndroidNote>();
4723	add(*part.memtagAndroidNote);
4724	if (canHaveMemtagGlobals()) {
4725	part.memtagGlobalDescriptors =
4726	std::make_unique<MemtagGlobalDescriptors>();
4727	add(*part.memtagGlobalDescriptors);
4728	}
4729	}
4730
4731	if (config->androidPackDynRelocs)
4732	part.relaDyn = std::make_unique<AndroidPackedRelocationSection<ELFT>>(
4733	relaDynName, threadCount);
4734	else
4735	part.relaDyn = std::make_unique<RelocationSection<ELFT>>(
4736	relaDynName, config->zCombreloc, threadCount);
4737
4738	if (config->hasDynSymTab) {
4739	add(*part.dynSymTab);
4740
4741	part.verSym = std::make_unique<VersionTableSection>();
4742	add(*part.verSym);
4743
4744	if (!namedVersionDefs().empty()) {
4745	part.verDef = std::make_unique<VersionDefinitionSection>();
4746	add(*part.verDef);
4747	}
4748
4749	part.verNeed = std::make_unique<VersionNeedSection<ELFT>>();
4750	add(*part.verNeed);
4751
4752	if (config->gnuHash) {
4753	part.gnuHashTab = std::make_unique<GnuHashTableSection>();
4754	add(*part.gnuHashTab);
4755	}
4756
4757	if (config->sysvHash) {
4758	part.hashTab = std::make_unique<HashTableSection>();
4759	add(*part.hashTab);
4760	}
4761
4762	add(*part.dynamic);
4763	add(*part.dynStrTab);
4764	}
4765	add(*part.relaDyn);
4766
4767	if (config->relrPackDynRelocs) {
4768	part.relrDyn = std::make_unique<RelrSection<ELFT>>(threadCount);
4769	add(*part.relrDyn);
4770	}
4771
4772	if (!config->relocatable) {
4773	if (config->ehFrameHdr) {
4774	part.ehFrameHdr = std::make_unique<EhFrameHeader>();
4775	add(*part.ehFrameHdr);
4776	}
4777	part.ehFrame = std::make_unique<EhFrameSection>();
4778	add(*part.ehFrame);
4779
4780	if (config->emachine == EM_ARM) {
4781	// This section replaces all the individual .ARM.exidx InputSections.
4782	part.armExidx = std::make_unique<ARMExidxSyntheticSection>();
4783	add(*part.armExidx);
4784	}
4785	}
4786
4787	if (!config->packageMetadata.empty()) {
4788	part.packageMetadataNote = std::make_unique<PackageMetadataNote>();
4789	add(*part.packageMetadataNote);
4790	}
4791	}
4792
4793	if (partitions.size() != 1) {
4794	// Create the partition end marker. This needs to be in partition number 255
4795	// so that it is sorted after all other partitions. It also has other
4796	// special handling (see createPhdrs() and combineEhSections()).
4797	in.partEnd =
4798	std::make_unique<BssSection>(args: ".part.end", args&: config->maxPageSize, args: 1);
4799	in.partEnd->partition = 255;
4800	add(*in.partEnd);
4801
4802	in.partIndex = std::make_unique<PartitionIndexSection>();
4803	addOptionalRegular(name: "__part_index_begin", sec: in.partIndex.get(), val: 0);
4804	addOptionalRegular(name: "__part_index_end", sec: in.partIndex.get(),
4805	val: in.partIndex->getSize());
4806	add(*in.partIndex);
4807	}
4808
4809	// Add .got. MIPS' .got is so different from the other archs,
4810	// it has its own class.
4811	if (config->emachine == EM_MIPS) {
4812	in.mipsGot = std::make_unique<MipsGotSection>();
4813	add(*in.mipsGot);
4814	} else {
4815	in.got = std::make_unique<GotSection>();
4816	add(*in.got);
4817	}
4818
4819	if (config->emachine == EM_PPC) {
4820	in.ppc32Got2 = std::make_unique<PPC32Got2Section>();
4821	add(*in.ppc32Got2);
4822	}
4823
4824	if (config->emachine == EM_PPC64) {
4825	in.ppc64LongBranchTarget = std::make_unique<PPC64LongBranchTargetSection>();
4826	add(*in.ppc64LongBranchTarget);
4827	}
4828
4829	in.gotPlt = std::make_unique<GotPltSection>();
4830	add(*in.gotPlt);
4831	in.igotPlt = std::make_unique<IgotPltSection>();
4832	add(*in.igotPlt);
4833	// Add .relro_padding if DATA_SEGMENT_RELRO_END is used; otherwise, add the
4834	// section in the absence of PHDRS/SECTIONS commands.
4835	if (config->zRelro &&
4836	((script->phdrsCommands.empty() && !script->hasSectionsCommand) ||
4837	script->seenRelroEnd)) {
4838	in.relroPadding = std::make_unique<RelroPaddingSection>();
4839	add(*in.relroPadding);
4840	}
4841
4842	if (config->emachine == EM_ARM) {
4843	in.armCmseSGSection = std::make_unique<ArmCmseSGSection>();
4844	add(*in.armCmseSGSection);
4845	}
4846
4847	// _GLOBAL_OFFSET_TABLE_ is defined relative to either .got.plt or .got. Treat
4848	// it as a relocation and ensure the referenced section is created.
4849	if (ElfSym::globalOffsetTable && config->emachine != EM_MIPS) {
4850	if (target->gotBaseSymInGotPlt)
4851	in.gotPlt->hasGotPltOffRel = true;
4852	else
4853	in.got->hasGotOffRel = true;
4854	}
4855
4856	// We always need to add rel[a].plt to output if it has entries.
4857	// Even for static linking it can contain R_[*]_IRELATIVE relocations.
4858	in.relaPlt = std::make_unique<RelocationSection<ELFT>>(
4859	config->isRela ? ".rela.plt" : ".rel.plt", /*sort=*/false,
4860	/*threadCount=*/1);
4861	add(*in.relaPlt);
4862
4863	if ((config->emachine == EM_386 || config->emachine == EM_X86_64) &&
4864	(config->andFeatures & GNU_PROPERTY_X86_FEATURE_1_IBT)) {
4865	in.ibtPlt = std::make_unique<IBTPltSection>();
4866	add(*in.ibtPlt);
4867	}
4868
4869	if (config->emachine == EM_PPC)
4870	in.plt = std::make_unique<PPC32GlinkSection>();
4871	else
4872	in.plt = std::make_unique<PltSection>();
4873	add(*in.plt);
4874	in.iplt = std::make_unique<IpltSection>();
4875	add(*in.iplt);
4876
4877	if (config->andFeatures || !ctx.aarch64PauthAbiCoreInfo.empty())
4878	add(*make<GnuPropertySection>());
4879
4880	if (config->debugNames) {
4881	in.debugNames = std::make_unique<DebugNamesSection<ELFT>>();
4882	add(*in.debugNames);
4883	}
4884
4885	if (config->gdbIndex) {
4886	in.gdbIndex = GdbIndexSection::create<ELFT>();
4887	add(*in.gdbIndex);
4888	}
4889
4890	// .note.GNU-stack is always added when we are creating a re-linkable
4891	// object file. Other linkers are using the presence of this marker
4892	// section to control the executable-ness of the stack area, but that
4893	// is irrelevant these days. Stack area should always be non-executable
4894	// by default. So we emit this section unconditionally.
4895	if (config->relocatable)
4896	add(*make<GnuStackSection>());
4897
4898	if (in.symTab)
4899	add(*in.symTab);
4900	if (in.symTabShndx)
4901	add(*in.symTabShndx);
4902	add(*in.shStrTab);
4903	if (in.strTab)
4904	add(*in.strTab);
4905	}
4906
4907	InStruct elf::in;
4908
4909	std::vector<Partition> elf::partitions;
4910	Partition *elf::mainPart;
4911
4912	template void elf::splitSections<ELF32LE>();
4913	template void elf::splitSections<ELF32BE>();
4914	template void elf::splitSections<ELF64LE>();
4915	template void elf::splitSections<ELF64BE>();
4916
4917	template void EhFrameSection::iterateFDEWithLSDA<ELF32LE>(
4918	function_ref<void(InputSection &)>);
4919	template void EhFrameSection::iterateFDEWithLSDA<ELF32BE>(
4920	function_ref<void(InputSection &)>);
4921	template void EhFrameSection::iterateFDEWithLSDA<ELF64LE>(
4922	function_ref<void(InputSection &)>);
4923	template void EhFrameSection::iterateFDEWithLSDA<ELF64BE>(
4924	function_ref<void(InputSection &)>);
4925
4926	template class elf::SymbolTableSection<ELF32LE>;
4927	template class elf::SymbolTableSection<ELF32BE>;
4928	template class elf::SymbolTableSection<ELF64LE>;
4929	template class elf::SymbolTableSection<ELF64BE>;
4930
4931	template void elf::writeEhdr<ELF32LE>(uint8_t *Buf, Partition &Part);
4932	template void elf::writeEhdr<ELF32BE>(uint8_t *Buf, Partition &Part);
4933	template void elf::writeEhdr<ELF64LE>(uint8_t *Buf, Partition &Part);
4934	template void elf::writeEhdr<ELF64BE>(uint8_t *Buf, Partition &Part);
4935
4936	template void elf::writePhdrs<ELF32LE>(uint8_t *Buf, Partition &Part);
4937	template void elf::writePhdrs<ELF32BE>(uint8_t *Buf, Partition &Part);
4938	template void elf::writePhdrs<ELF64LE>(uint8_t *Buf, Partition &Part);
4939	template void elf::writePhdrs<ELF64BE>(uint8_t *Buf, Partition &Part);
4940
4941	template void elf::createSyntheticSections<ELF32LE>();
4942	template void elf::createSyntheticSections<ELF32BE>();
4943	template void elf::createSyntheticSections<ELF64LE>();
4944	template void elf::createSyntheticSections<ELF64BE>();
4945