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	#include "SyntheticSections.h"
10	#include "ConcatOutputSection.h"
11	#include "Config.h"
12	#include "ExportTrie.h"
13	#include "InputFiles.h"
14	#include "MachOStructs.h"
15	#include "ObjC.h"
16	#include "OutputSegment.h"
17	#include "SymbolTable.h"
18	#include "Symbols.h"
19
20	#include "lld/Common/CommonLinkerContext.h"
21	#include "llvm/ADT/STLExtras.h"
22	#include "llvm/Config/llvm-config.h"
23	#include "llvm/Support/EndianStream.h"
24	#include "llvm/Support/FileSystem.h"
25	#include "llvm/Support/LEB128.h"
26	#include "llvm/Support/Parallel.h"
27	#include "llvm/Support/Path.h"
28	#include "llvm/Support/xxhash.h"
29
30	#if defined(__APPLE__)
31	#include <sys/mman.h>
32
33	#define COMMON_DIGEST_FOR_OPENSSL
34	#include <CommonCrypto/CommonDigest.h>
35	#else
36	#include "llvm/Support/SHA256.h"
37	#endif
38
39	using namespace llvm;
40	using namespace llvm::MachO;
41	using namespace llvm::support;
42	using namespace llvm::support::endian;
43	using namespace lld;
44	using namespace lld::macho;
45
46	// Reads `len` bytes at data and writes the 32-byte SHA256 checksum to `output`.
47	static void sha256(const uint8_t *data, size_t len, uint8_t *output) {
48	#if defined(__APPLE__)
49	// FIXME: Make LLVM's SHA256 faster and use it unconditionally. See PR56121
50	// for some notes on this.
51	CC_SHA256(data, len, output);
52	#else
53	ArrayRef<uint8_t> block(data, len);
54	std::array<uint8_t, 32> hash = SHA256::hash(Data: block);
55	static_assert(hash.size() == CodeSignatureSection::hashSize);
56	memcpy(dest: output, src: hash.data(), n: hash.size());
57	#endif
58	}
59
60	InStruct macho::in;
61	std::vector<SyntheticSection *> macho::syntheticSections;
62
63	SyntheticSection::SyntheticSection(const char *segname, const char *name)
64	: OutputSection(SyntheticKind, name) {
65	std::tie(args&: this->segname, args&: this->name) = maybeRenameSection(key: {segname, name});
66	isec = makeSyntheticInputSection(segName: segname, sectName: name);
67	isec->parent = this;
68	syntheticSections.push_back(x: this);
69	}
70
71	// dyld3's MachOLoaded::getSlide() assumes that the __TEXT segment starts
72	// from the beginning of the file (i.e. the header).
73	MachHeaderSection::MachHeaderSection()
74	: SyntheticSection(segment_names::text, section_names::header) {
75	// XXX: This is a hack. (See D97007)
76	// Setting the index to 1 to pretend that this section is the text
77	// section.
78	index = 1;
79	isec->isFinal = true;
80	}
81
82	void MachHeaderSection::addLoadCommand(LoadCommand *lc) {
83	loadCommands.push_back(x: lc);
84	sizeOfCmds += lc->getSize();
85	}
86
87	uint64_t MachHeaderSection::getSize() const {
88	uint64_t size = target->headerSize + sizeOfCmds + config->headerPad;
89	// If we are emitting an encryptable binary, our load commands must have a
90	// separate (non-encrypted) page to themselves.
91	if (config->emitEncryptionInfo)
92	size = alignToPowerOf2(Value: size, Align: target->getPageSize());
93	return size;
94	}
95
96	static uint32_t cpuSubtype() {
97	uint32_t subtype = target->cpuSubtype;
98
99	if (config->outputType == MH_EXECUTE && !config->staticLink &&
100	target->cpuSubtype == CPU_SUBTYPE_X86_64_ALL &&
101	config->platform() == PLATFORM_MACOS &&
102	config->platformInfo.target.MinDeployment >= VersionTuple(10, 5))
103	subtype |= CPU_SUBTYPE_LIB64;
104
105	return subtype;
106	}
107
108	static bool hasWeakBinding() {
109	return config->emitChainedFixups ? in.chainedFixups->hasWeakBinding()
110	: in.weakBinding->hasEntry();
111	}
112
113	static bool hasNonWeakDefinition() {
114	return config->emitChainedFixups ? in.chainedFixups->hasNonWeakDefinition()
115	: in.weakBinding->hasNonWeakDefinition();
116	}
117
118	void MachHeaderSection::writeTo(uint8_t *buf) const {
119	auto *hdr = reinterpret_cast<mach_header *>(buf);
120	hdr->magic = target->magic;
121	hdr->cputype = target->cpuType;
122	hdr->cpusubtype = cpuSubtype();
123	hdr->filetype = config->outputType;
124	hdr->ncmds = loadCommands.size();
125	hdr->sizeofcmds = sizeOfCmds;
126	hdr->flags = MH_DYLDLINK;
127
128	if (config->namespaceKind == NamespaceKind::twolevel)
129	hdr->flags |= MH_NOUNDEFS | MH_TWOLEVEL;
130
131	if (config->outputType == MH_DYLIB && !config->hasReexports)
132	hdr->flags |= MH_NO_REEXPORTED_DYLIBS;
133
134	if (config->markDeadStrippableDylib)
135	hdr->flags |= MH_DEAD_STRIPPABLE_DYLIB;
136
137	if (config->outputType == MH_EXECUTE && config->isPic)
138	hdr->flags |= MH_PIE;
139
140	if (config->outputType == MH_DYLIB && config->applicationExtension)
141	hdr->flags |= MH_APP_EXTENSION_SAFE;
142
143	if (in.exports->hasWeakSymbol || hasNonWeakDefinition())
144	hdr->flags |= MH_WEAK_DEFINES;
145
146	if (in.exports->hasWeakSymbol || hasWeakBinding())
147	hdr->flags |= MH_BINDS_TO_WEAK;
148
149	for (const OutputSegment *seg : outputSegments) {
150	for (const OutputSection *osec : seg->getSections()) {
151	if (isThreadLocalVariables(flags: osec->flags)) {
152	hdr->flags |= MH_HAS_TLV_DESCRIPTORS;
153	break;
154	}
155	}
156	}
157
158	uint8_t *p = reinterpret_cast<uint8_t *>(hdr) + target->headerSize;
159	for (const LoadCommand *lc : loadCommands) {
160	lc->writeTo(buf: p);
161	p += lc->getSize();
162	}
163	}
164
165	PageZeroSection::PageZeroSection()
166	: SyntheticSection(segment_names::pageZero, section_names::pageZero) {}
167
168	RebaseSection::RebaseSection()
169	: LinkEditSection(segment_names::linkEdit, section_names::rebase) {}
170
171	namespace {
172	struct RebaseState {
173	uint64_t sequenceLength;
174	uint64_t skipLength;
175	};
176	} // namespace
177
178	static void emitIncrement(uint64_t incr, raw_svector_ostream &os) {
179	assert(incr != 0);
180
181	if ((incr >> target->p2WordSize) <= REBASE_IMMEDIATE_MASK &&
182	(incr % target->wordSize) == 0) {
183	os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_IMM_SCALED |
184	(incr >> target->p2WordSize));
185	} else {
186	os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_ULEB);
187	encodeULEB128(Value: incr, OS&: os);
188	}
189	}
190
191	static void flushRebase(const RebaseState &state, raw_svector_ostream &os) {
192	assert(state.sequenceLength > 0);
193
194	if (state.skipLength == target->wordSize) {
195	if (state.sequenceLength <= REBASE_IMMEDIATE_MASK) {
196	os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_IMM_TIMES |
197	state.sequenceLength);
198	} else {
199	os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_ULEB_TIMES);
200	encodeULEB128(Value: state.sequenceLength, OS&: os);
201	}
202	} else if (state.sequenceLength == 1) {
203	os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB);
204	encodeULEB128(Value: state.skipLength - target->wordSize, OS&: os);
205	} else {
206	os << static_cast<uint8_t>(
207	REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB);
208	encodeULEB128(Value: state.sequenceLength, OS&: os);
209	encodeULEB128(Value: state.skipLength - target->wordSize, OS&: os);
210	}
211	}
212
213	// Rebases are communicated to dyld using a bytecode, whose opcodes cause the
214	// memory location at a specific address to be rebased and/or the address to be
215	// incremented.
216	//
217	// Opcode REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB is the most generic
218	// one, encoding a series of evenly spaced addresses. This algorithm works by
219	// splitting up the sorted list of addresses into such chunks. If the locations
220	// are consecutive or the sequence consists of a single location, flushRebase
221	// will use a smaller, more specialized encoding.
222	static void encodeRebases(const OutputSegment *seg,
223	MutableArrayRef<Location> locations,
224	raw_svector_ostream &os) {
225	// dyld operates on segments. Translate section offsets into segment offsets.
226	for (Location &loc : locations)
227	loc.offset =
228	loc.isec->parent->getSegmentOffset() + loc.isec->getOffset(off: loc.offset);
229	// The algorithm assumes that locations are unique.
230	Location *end =
231	llvm::unique(R&: locations, P: [](const Location &a, const Location &b) {
232	return a.offset == b.offset;
233	});
234	size_t count = end - locations.begin();
235
236	os << static_cast<uint8_t>(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
237	seg->index);
238	assert(!locations.empty());
239	uint64_t offset = locations[0].offset;
240	encodeULEB128(Value: offset, OS&: os);
241
242	RebaseState state{.sequenceLength: 1, .skipLength: target->wordSize};
243
244	for (size_t i = 1; i < count; ++i) {
245	offset = locations[i].offset;
246
247	uint64_t skip = offset - locations[i - 1].offset;
248	assert(skip != 0 && "duplicate locations should have been weeded out");
249
250	if (skip == state.skipLength) {
251	++state.sequenceLength;
252	} else if (state.sequenceLength == 1) {
253	++state.sequenceLength;
254	state.skipLength = skip;
255	} else if (skip < state.skipLength) {
256	// The address is lower than what the rebase pointer would be if the last
257	// location would be part of a sequence. We start a new sequence from the
258	// previous location.
259	--state.sequenceLength;
260	flushRebase(state, os);
261
262	state.sequenceLength = 2;
263	state.skipLength = skip;
264	} else {
265	// The address is at some positive offset from the rebase pointer. We
266	// start a new sequence which begins with the current location.
267	flushRebase(state, os);
268	emitIncrement(incr: skip - state.skipLength, os);
269	state.sequenceLength = 1;
270	state.skipLength = target->wordSize;
271	}
272	}
273	flushRebase(state, os);
274	}
275
276	void RebaseSection::finalizeContents() {
277	if (locations.empty())
278	return;
279
280	raw_svector_ostream os{contents};
281	os << static_cast<uint8_t>(REBASE_OPCODE_SET_TYPE_IMM | REBASE_TYPE_POINTER);
282
283	llvm::sort(C&: locations, Comp: [](const Location &a, const Location &b) {
284	return a.isec->getVA(off: a.offset) < b.isec->getVA(off: b.offset);
285	});
286
287	for (size_t i = 0, count = locations.size(); i < count;) {
288	const OutputSegment *seg = locations[i].isec->parent->parent;
289	size_t j = i + 1;
290	while (j < count && locations[j].isec->parent->parent == seg)
291	++j;
292	encodeRebases(seg, locations: {locations.data() + i, locations.data() + j}, os);
293	i = j;
294	}
295	os << static_cast<uint8_t>(REBASE_OPCODE_DONE);
296	}
297
298	void RebaseSection::writeTo(uint8_t *buf) const {
299	memcpy(dest: buf, src: contents.data(), n: contents.size());
300	}
301
302	NonLazyPointerSectionBase::NonLazyPointerSectionBase(const char *segname,
303	const char *name)
304	: SyntheticSection(segname, name) {
305	align = target->wordSize;
306	}
307
308	void macho::addNonLazyBindingEntries(const Symbol *sym,
309	const InputSection *isec, uint64_t offset,
310	int64_t addend) {
311	if (config->emitChainedFixups) {
312	if (needsBinding(sym))
313	in.chainedFixups->addBinding(dysym: sym, isec, offset, addend);
314	else if (isa<Defined>(Val: sym))
315	in.chainedFixups->addRebase(isec, offset);
316	else
317	llvm_unreachable("cannot bind to an undefined symbol");
318	return;
319	}
320
321	if (const auto *dysym = dyn_cast<DylibSymbol>(Val: sym)) {
322	in.binding->addEntry(dysym, isec, offset, addend);
323	if (dysym->isWeakDef())
324	in.weakBinding->addEntry(symbol: sym, isec, offset, addend);
325	} else if (const auto *defined = dyn_cast<Defined>(Val: sym)) {
326	in.rebase->addEntry(isec, offset);
327	if (defined->isExternalWeakDef())
328	in.weakBinding->addEntry(symbol: sym, isec, offset, addend);
329	else if (defined->interposable)
330	in.binding->addEntry(dysym: sym, isec, offset, addend);
331	} else {
332	// Undefined symbols are filtered out in scanRelocations(); we should never
333	// get here
334	llvm_unreachable("cannot bind to an undefined symbol");
335	}
336	}
337
338	void NonLazyPointerSectionBase::addEntry(Symbol *sym) {
339	if (entries.insert(X: sym)) {
340	assert(!sym->isInGot());
341	sym->gotIndex = entries.size() - 1;
342
343	addNonLazyBindingEntries(sym, isec, offset: sym->gotIndex * target->wordSize);
344	}
345	}
346
347	void macho::writeChainedRebase(uint8_t *buf, uint64_t targetVA) {
348	assert(config->emitChainedFixups);
349	assert(target->wordSize == 8 && "Only 64-bit platforms are supported");
350	auto *rebase = reinterpret_cast<dyld_chained_ptr_64_rebase *>(buf);
351	rebase->target = targetVA & 0xf'ffff'ffff;
352	rebase->high8 = (targetVA >> 56);
353	rebase->reserved = 0;
354	rebase->next = 0;
355	rebase->bind = 0;
356
357	// The fixup format places a 64 GiB limit on the output's size.
358	// Should we handle this gracefully?
359	uint64_t encodedVA = rebase->target | ((uint64_t)rebase->high8 << 56);
360	if (encodedVA != targetVA)
361	error(msg: "rebase target address 0x" + Twine::utohexstr(Val: targetVA) +
362	" does not fit into chained fixup. Re-link with -no_fixup_chains");
363	}
364
365	static void writeChainedBind(uint8_t *buf, const Symbol *sym, int64_t addend) {
366	assert(config->emitChainedFixups);
367	assert(target->wordSize == 8 && "Only 64-bit platforms are supported");
368	auto *bind = reinterpret_cast<dyld_chained_ptr_64_bind *>(buf);
369	auto [ordinal, inlineAddend] = in.chainedFixups->getBinding(sym, addend);
370	bind->ordinal = ordinal;
371	bind->addend = inlineAddend;
372	bind->reserved = 0;
373	bind->next = 0;
374	bind->bind = 1;
375	}
376
377	void macho::writeChainedFixup(uint8_t *buf, const Symbol *sym, int64_t addend) {
378	if (needsBinding(sym))
379	writeChainedBind(buf, sym, addend);
380	else
381	writeChainedRebase(buf, targetVA: sym->getVA() + addend);
382	}
383
384	void NonLazyPointerSectionBase::writeTo(uint8_t *buf) const {
385	if (config->emitChainedFixups) {
386	for (const auto &[i, entry] : llvm::enumerate(First: entries))
387	writeChainedFixup(buf: &buf[i * target->wordSize], sym: entry, addend: 0);
388	} else {
389	for (const auto &[i, entry] : llvm::enumerate(First: entries))
390	if (auto *defined = dyn_cast<Defined>(Val: entry))
391	write64le(P: &buf[i * target->wordSize], V: defined->getVA());
392	}
393	}
394
395	GotSection::GotSection()
396	: NonLazyPointerSectionBase(segment_names::data, section_names::got) {
397	flags = S_NON_LAZY_SYMBOL_POINTERS;
398	}
399
400	TlvPointerSection::TlvPointerSection()
401	: NonLazyPointerSectionBase(segment_names::data,
402	section_names::threadPtrs) {
403	flags = S_THREAD_LOCAL_VARIABLE_POINTERS;
404	}
405
406	BindingSection::BindingSection()
407	: LinkEditSection(segment_names::linkEdit, section_names::binding) {}
408
409	namespace {
410	struct Binding {
411	OutputSegment *segment = nullptr;
412	uint64_t offset = 0;
413	int64_t addend = 0;
414	};
415	struct BindIR {
416	// Default value of 0xF0 is not valid opcode and should make the program
417	// scream instead of accidentally writing "valid" values.
418	uint8_t opcode = 0xF0;
419	uint64_t data = 0;
420	uint64_t consecutiveCount = 0;
421	};
422	} // namespace
423
424	// Encode a sequence of opcodes that tell dyld to write the address of symbol +
425	// addend at osec->addr + outSecOff.
426	//
427	// The bind opcode "interpreter" remembers the values of each binding field, so
428	// we only need to encode the differences between bindings. Hence the use of
429	// lastBinding.
430	static void encodeBinding(const OutputSection *osec, uint64_t outSecOff,
431	int64_t addend, Binding &lastBinding,
432	std::vector<BindIR> &opcodes) {
433	OutputSegment *seg = osec->parent;
434	uint64_t offset = osec->getSegmentOffset() + outSecOff;
435	if (lastBinding.segment != seg) {
436	opcodes.push_back(
437	x: {.opcode: static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
438	seg->index),
439	.data: offset});
440	lastBinding.segment = seg;
441	lastBinding.offset = offset;
442	} else if (lastBinding.offset != offset) {
443	opcodes.push_back(x: {.opcode: BIND_OPCODE_ADD_ADDR_ULEB, .data: offset - lastBinding.offset});
444	lastBinding.offset = offset;
445	}
446
447	if (lastBinding.addend != addend) {
448	opcodes.push_back(
449	x: {.opcode: BIND_OPCODE_SET_ADDEND_SLEB, .data: static_cast<uint64_t>(addend)});
450	lastBinding.addend = addend;
451	}
452
453	opcodes.push_back(x: {.opcode: BIND_OPCODE_DO_BIND, .data: 0});
454	// DO_BIND causes dyld to both perform the binding and increment the offset
455	lastBinding.offset += target->wordSize;
456	}
457
458	static void optimizeOpcodes(std::vector<BindIR> &opcodes) {
459	// Pass 1: Combine bind/add pairs
460	size_t i;
461	int pWrite = 0;
462	for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
463	if ((opcodes[i].opcode == BIND_OPCODE_ADD_ADDR_ULEB) &&
464	(opcodes[i - 1].opcode == BIND_OPCODE_DO_BIND)) {
465	opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB;
466	opcodes[pWrite].data = opcodes[i].data;
467	++i;
468	} else {
469	opcodes[pWrite] = opcodes[i - 1];
470	}
471	}
472	if (i == opcodes.size())
473	opcodes[pWrite] = opcodes[i - 1];
474	opcodes.resize(new_size: pWrite + 1);
475
476	// Pass 2: Compress two or more bind_add opcodes
477	pWrite = 0;
478	for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
479	if ((opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
480	(opcodes[i - 1].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
481	(opcodes[i].data == opcodes[i - 1].data)) {
482	opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
483	opcodes[pWrite].consecutiveCount = 2;
484	opcodes[pWrite].data = opcodes[i].data;
485	++i;
486	while (i < opcodes.size() &&
487	(opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
488	(opcodes[i].data == opcodes[i - 1].data)) {
489	opcodes[pWrite].consecutiveCount++;
490	++i;
491	}
492	} else {
493	opcodes[pWrite] = opcodes[i - 1];
494	}
495	}
496	if (i == opcodes.size())
497	opcodes[pWrite] = opcodes[i - 1];
498	opcodes.resize(new_size: pWrite + 1);
499
500	// Pass 3: Use immediate encodings
501	// Every binding is the size of one pointer. If the next binding is a
502	// multiple of wordSize away that is within BIND_IMMEDIATE_MASK, the
503	// opcode can be scaled by wordSize into a single byte and dyld will
504	// expand it to the correct address.
505	for (auto &p : opcodes) {
506	// It's unclear why the check needs to be less than BIND_IMMEDIATE_MASK,
507	// but ld64 currently does this. This could be a potential bug, but
508	// for now, perform the same behavior to prevent mysterious bugs.
509	if ((p.opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
510	((p.data / target->wordSize) < BIND_IMMEDIATE_MASK) &&
511	((p.data % target->wordSize) == 0)) {
512	p.opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED;
513	p.data /= target->wordSize;
514	}
515	}
516	}
517
518	static void flushOpcodes(const BindIR &op, raw_svector_ostream &os) {
519	uint8_t opcode = op.opcode & BIND_OPCODE_MASK;
520	switch (opcode) {
521	case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
522	case BIND_OPCODE_ADD_ADDR_ULEB:
523	case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
524	os << op.opcode;
525	encodeULEB128(Value: op.data, OS&: os);
526	break;
527	case BIND_OPCODE_SET_ADDEND_SLEB:
528	os << op.opcode;
529	encodeSLEB128(Value: static_cast<int64_t>(op.data), OS&: os);
530	break;
531	case BIND_OPCODE_DO_BIND:
532	os << op.opcode;
533	break;
534	case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
535	os << op.opcode;
536	encodeULEB128(Value: op.consecutiveCount, OS&: os);
537	encodeULEB128(Value: op.data, OS&: os);
538	break;
539	case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
540	os << static_cast<uint8_t>(op.opcode | op.data);
541	break;
542	default:
543	llvm_unreachable("cannot bind to an unrecognized symbol");
544	}
545	}
546
547	// Non-weak bindings need to have their dylib ordinal encoded as well.
548	static int16_t ordinalForDylibSymbol(const DylibSymbol &dysym) {
549	if (config->namespaceKind == NamespaceKind::flat || dysym.isDynamicLookup())
550	return static_cast<int16_t>(BIND_SPECIAL_DYLIB_FLAT_LOOKUP);
551	assert(dysym.getFile()->isReferenced());
552	return dysym.getFile()->ordinal;
553	}
554
555	static int16_t ordinalForSymbol(const Symbol &sym) {
556	if (const auto *dysym = dyn_cast<DylibSymbol>(Val: &sym))
557	return ordinalForDylibSymbol(dysym: *dysym);
558	assert(cast<Defined>(&sym)->interposable);
559	return BIND_SPECIAL_DYLIB_FLAT_LOOKUP;
560	}
561
562	static void encodeDylibOrdinal(int16_t ordinal, raw_svector_ostream &os) {
563	if (ordinal <= 0) {
564	os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM |
565	(ordinal & BIND_IMMEDIATE_MASK));
566	} else if (ordinal <= BIND_IMMEDIATE_MASK) {
567	os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | ordinal);
568	} else {
569	os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
570	encodeULEB128(Value: ordinal, OS&: os);
571	}
572	}
573
574	static void encodeWeakOverride(const Defined *defined,
575	raw_svector_ostream &os) {
576	os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM |
577	BIND_SYMBOL_FLAGS_NON_WEAK_DEFINITION)
578	<< defined->getName() << '\0';
579	}
580
581	// Organize the bindings so we can encoded them with fewer opcodes.
582	//
583	// First, all bindings for a given symbol should be grouped together.
584	// BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM is the largest opcode (since it
585	// has an associated symbol string), so we only want to emit it once per symbol.
586	//
587	// Within each group, we sort the bindings by address. Since bindings are
588	// delta-encoded, sorting them allows for a more compact result. Note that
589	// sorting by address alone ensures that bindings for the same segment / section
590	// are located together, minimizing the number of times we have to emit
591	// BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB.
592	//
593	// Finally, we sort the symbols by the address of their first binding, again
594	// to facilitate the delta-encoding process.
595	template <class Sym>
596	std::vector<std::pair<const Sym *, std::vector<BindingEntry>>>
597	sortBindings(const BindingsMap<const Sym *> &bindingsMap) {
598	std::vector<std::pair<const Sym *, std::vector<BindingEntry>>> bindingsVec(
599	bindingsMap.begin(), bindingsMap.end());
600	for (auto &p : bindingsVec) {
601	std::vector<BindingEntry> &bindings = p.second;
602	llvm::sort(bindings, [](const BindingEntry &a, const BindingEntry &b) {
603	return a.target.getVA() < b.target.getVA();
604	});
605	}
606	llvm::sort(bindingsVec, [](const auto &a, const auto &b) {
607	return a.second[0].target.getVA() < b.second[0].target.getVA();
608	});
609	return bindingsVec;
610	}
611
612	// Emit bind opcodes, which are a stream of byte-sized opcodes that dyld
613	// interprets to update a record with the following fields:
614	// * segment index (of the segment to write the symbol addresses to, typically
615	// the __DATA_CONST segment which contains the GOT)
616	// * offset within the segment, indicating the next location to write a binding
617	// * symbol type
618	// * symbol library ordinal (the index of its library's LC_LOAD_DYLIB command)
619	// * symbol name
620	// * addend
621	// When dyld sees BIND_OPCODE_DO_BIND, it uses the current record state to bind
622	// a symbol in the GOT, and increments the segment offset to point to the next
623	// entry. It does *not* clear the record state after doing the bind, so
624	// subsequent opcodes only need to encode the differences between bindings.
625	void BindingSection::finalizeContents() {
626	raw_svector_ostream os{contents};
627	Binding lastBinding;
628	int16_t lastOrdinal = 0;
629
630	for (auto &p : sortBindings(bindingsMap)) {
631	const Symbol *sym = p.first;
632	std::vector<BindingEntry> &bindings = p.second;
633	uint8_t flags = BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
634	if (sym->isWeakRef())
635	flags |= BIND_SYMBOL_FLAGS_WEAK_IMPORT;
636	os << flags << sym->getName() << '\0'
637	<< static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
638	int16_t ordinal = ordinalForSymbol(sym: *sym);
639	if (ordinal != lastOrdinal) {
640	encodeDylibOrdinal(ordinal, os);
641	lastOrdinal = ordinal;
642	}
643	std::vector<BindIR> opcodes;
644	for (const BindingEntry &b : bindings)
645	encodeBinding(osec: b.target.isec->parent,
646	outSecOff: b.target.isec->getOffset(off: b.target.offset), addend: b.addend,
647	lastBinding, opcodes);
648	if (config->optimize > 1)
649	optimizeOpcodes(opcodes);
650	for (const auto &op : opcodes)
651	flushOpcodes(op, os);
652	}
653	if (!bindingsMap.empty())
654	os << static_cast<uint8_t>(BIND_OPCODE_DONE);
655	}
656
657	void BindingSection::writeTo(uint8_t *buf) const {
658	memcpy(dest: buf, src: contents.data(), n: contents.size());
659	}
660
661	WeakBindingSection::WeakBindingSection()
662	: LinkEditSection(segment_names::linkEdit, section_names::weakBinding) {}
663
664	void WeakBindingSection::finalizeContents() {
665	raw_svector_ostream os{contents};
666	Binding lastBinding;
667
668	for (const Defined *defined : definitions)
669	encodeWeakOverride(defined, os);
670
671	for (auto &p : sortBindings(bindingsMap)) {
672	const Symbol *sym = p.first;
673	std::vector<BindingEntry> &bindings = p.second;
674	os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
675	<< sym->getName() << '\0'
676	<< static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
677	std::vector<BindIR> opcodes;
678	for (const BindingEntry &b : bindings)
679	encodeBinding(osec: b.target.isec->parent,
680	outSecOff: b.target.isec->getOffset(off: b.target.offset), addend: b.addend,
681	lastBinding, opcodes);
682	if (config->optimize > 1)
683	optimizeOpcodes(opcodes);
684	for (const auto &op : opcodes)
685	flushOpcodes(op, os);
686	}
687	if (!bindingsMap.empty() || !definitions.empty())
688	os << static_cast<uint8_t>(BIND_OPCODE_DONE);
689	}
690
691	void WeakBindingSection::writeTo(uint8_t *buf) const {
692	memcpy(dest: buf, src: contents.data(), n: contents.size());
693	}
694
695	StubsSection::StubsSection()
696	: SyntheticSection(segment_names::text, section_names::stubs) {
697	flags = S_SYMBOL_STUBS | S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
698	// The stubs section comprises machine instructions, which are aligned to
699	// 4 bytes on the archs we care about.
700	align = 4;
701	reserved2 = target->stubSize;
702	}
703
704	uint64_t StubsSection::getSize() const {
705	return entries.size() * target->stubSize;
706	}
707
708	void StubsSection::writeTo(uint8_t *buf) const {
709	size_t off = 0;
710	for (const Symbol *sym : entries) {
711	uint64_t pointerVA =
712	config->emitChainedFixups ? sym->getGotVA() : sym->getLazyPtrVA();
713	target->writeStub(buf: buf + off, *sym, pointerVA);
714	off += target->stubSize;
715	}
716	}
717
718	void StubsSection::finalize() { isFinal = true; }
719
720	static void addBindingsForStub(Symbol *sym) {
721	assert(!config->emitChainedFixups);
722	if (auto *dysym = dyn_cast<DylibSymbol>(Val: sym)) {
723	if (sym->isWeakDef()) {
724	in.binding->addEntry(dysym, isec: in.lazyPointers->isec,
725	offset: sym->stubsIndex * target->wordSize);
726	in.weakBinding->addEntry(symbol: sym, isec: in.lazyPointers->isec,
727	offset: sym->stubsIndex * target->wordSize);
728	} else {
729	in.lazyBinding->addEntry(dysym);
730	}
731	} else if (auto *defined = dyn_cast<Defined>(Val: sym)) {
732	if (defined->isExternalWeakDef()) {
733	in.rebase->addEntry(isec: in.lazyPointers->isec,
734	offset: sym->stubsIndex * target->wordSize);
735	in.weakBinding->addEntry(symbol: sym, isec: in.lazyPointers->isec,
736	offset: sym->stubsIndex * target->wordSize);
737	} else if (defined->interposable) {
738	in.lazyBinding->addEntry(dysym: sym);
739	} else {
740	llvm_unreachable("invalid stub target");
741	}
742	} else {
743	llvm_unreachable("invalid stub target symbol type");
744	}
745	}
746
747	void StubsSection::addEntry(Symbol *sym) {
748	bool inserted = entries.insert(X: sym);
749	if (inserted) {
750	sym->stubsIndex = entries.size() - 1;
751
752	if (config->emitChainedFixups)
753	in.got->addEntry(sym);
754	else
755	addBindingsForStub(sym);
756	}
757	}
758
759	StubHelperSection::StubHelperSection()
760	: SyntheticSection(segment_names::text, section_names::stubHelper) {
761	flags = S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
762	align = 4; // This section comprises machine instructions
763	}
764
765	uint64_t StubHelperSection::getSize() const {
766	return target->stubHelperHeaderSize +
767	in.lazyBinding->getEntries().size() * target->stubHelperEntrySize;
768	}
769
770	bool StubHelperSection::isNeeded() const { return in.lazyBinding->isNeeded(); }
771
772	void StubHelperSection::writeTo(uint8_t *buf) const {
773	target->writeStubHelperHeader(buf);
774	size_t off = target->stubHelperHeaderSize;
775	for (const Symbol *sym : in.lazyBinding->getEntries()) {
776	target->writeStubHelperEntry(buf: buf + off, *sym, entryAddr: addr + off);
777	off += target->stubHelperEntrySize;
778	}
779	}
780
781	void StubHelperSection::setUp() {
782	Symbol *binder = symtab->addUndefined(name: "dyld_stub_binder", /*file=*/nullptr,
783	/*isWeakRef=*/false);
784	if (auto *undefined = dyn_cast<Undefined>(Val: binder))
785	treatUndefinedSymbol(*undefined,
786	source: "lazy binding (normally in libSystem.dylib)");
787
788	// treatUndefinedSymbol() can replace binder with a DylibSymbol; re-check.
789	stubBinder = dyn_cast_or_null<DylibSymbol>(Val: binder);
790	if (stubBinder == nullptr)
791	return;
792
793	in.got->addEntry(sym: stubBinder);
794
795	in.imageLoaderCache->parent =
796	ConcatOutputSection::getOrCreateForInput(in.imageLoaderCache);
797	addInputSection(inputSection: in.imageLoaderCache);
798	// Since this isn't in the symbol table or in any input file, the noDeadStrip
799	// argument doesn't matter.
800	dyldPrivate =
801	make<Defined>(args: "__dyld_private", args: nullptr, args&: in.imageLoaderCache, args: 0, args: 0,
802	/*isWeakDef=*/args: false,
803	/*isExternal=*/args: false, /*isPrivateExtern=*/args: false,
804	/*includeInSymtab=*/args: true,
805	/*isReferencedDynamically=*/args: false,
806	/*noDeadStrip=*/args: false);
807	dyldPrivate->used = true;
808	}
809
810	llvm::DenseMap<llvm::CachedHashStringRef, ConcatInputSection *>
811	ObjCSelRefsHelper::methnameToSelref;
812	void ObjCSelRefsHelper::initialize() {
813	// Do not fold selrefs without ICF.
814	if (config->icfLevel == ICFLevel::none)
815	return;
816
817	// Search methnames already referenced in __objc_selrefs
818	// Map the name to the corresponding selref entry
819	// which we will reuse when creating objc stubs.
820	for (ConcatInputSection *isec : inputSections) {
821	if (isec->shouldOmitFromOutput())
822	continue;
823	if (isec->getName() != section_names::objcSelrefs)
824	continue;
825	// We expect a single relocation per selref entry to __objc_methname that
826	// might be aggregated.
827	assert(isec->relocs.size() == 1);
828	auto Reloc = isec->relocs[0];
829	if (const auto *sym = Reloc.referent.dyn_cast<Symbol *>()) {
830	if (const auto *d = dyn_cast<Defined>(Val: sym)) {
831	auto *cisec = cast<CStringInputSection>(Val: d->isec());
832	auto methname = cisec->getStringRefAtOffset(off: d->value);
833	methnameToSelref[CachedHashStringRef(methname)] = isec;
834	}
835	}
836	}
837	}
838
839	void ObjCSelRefsHelper::cleanup() { methnameToSelref.clear(); }
840
841	ConcatInputSection *ObjCSelRefsHelper::makeSelRef(StringRef methname) {
842	auto methnameOffset =
843	in.objcMethnameSection->getStringOffset(str: methname).outSecOff;
844
845	size_t wordSize = target->wordSize;
846	uint8_t *selrefData = bAlloc().Allocate<uint8_t>(Num: wordSize);
847	write64le(P: selrefData, V: methnameOffset);
848	ConcatInputSection *objcSelref =
849	makeSyntheticInputSection(segName: segment_names::data, sectName: section_names::objcSelrefs,
850	flags: S_LITERAL_POINTERS | S_ATTR_NO_DEAD_STRIP,
851	data: ArrayRef<uint8_t>{selrefData, wordSize},
852	/*align=*/wordSize);
853	assert(objcSelref->live);
854	objcSelref->relocs.push_back(x: {/*type=*/target->unsignedRelocType,
855	/*pcrel=*/false, /*length=*/3,
856	/*offset=*/0,
857	/*addend=*/static_cast<int64_t>(methnameOffset),
858	/*referent=*/in.objcMethnameSection->isec});
859	objcSelref->parent = ConcatOutputSection::getOrCreateForInput(objcSelref);
860	addInputSection(inputSection: objcSelref);
861	objcSelref->isFinal = true;
862	methnameToSelref[CachedHashStringRef(methname)] = objcSelref;
863	return objcSelref;
864	}
865
866	ConcatInputSection *ObjCSelRefsHelper::getSelRef(StringRef methname) {
867	auto it = methnameToSelref.find(Val: CachedHashStringRef(methname));
868	if (it == methnameToSelref.end())
869	return nullptr;
870	return it->second;
871	}
872
873	ObjCStubsSection::ObjCStubsSection()
874	: SyntheticSection(segment_names::text, section_names::objcStubs) {
875	flags = S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
876	align = config->objcStubsMode == ObjCStubsMode::fast
877	? target->objcStubsFastAlignment
878	: target->objcStubsSmallAlignment;
879	}
880
881	bool ObjCStubsSection::isObjCStubSymbol(Symbol *sym) {
882	return sym->getName().starts_with(Prefix: symbolPrefix);
883	}
884
885	StringRef ObjCStubsSection::getMethname(Symbol *sym) {
886	assert(isObjCStubSymbol(sym) && "not an objc stub");
887	auto name = sym->getName();
888	StringRef methname = name.drop_front(N: symbolPrefix.size());
889	return methname;
890	}
891
892	void ObjCStubsSection::addEntry(Symbol *sym) {
893	StringRef methname = getMethname(sym);
894	// We create a selref entry for each unique methname.
895	if (!ObjCSelRefsHelper::getSelRef(methname))
896	ObjCSelRefsHelper::makeSelRef(methname);
897
898	auto stubSize = config->objcStubsMode == ObjCStubsMode::fast
899	? target->objcStubsFastSize
900	: target->objcStubsSmallSize;
901	Defined *newSym = replaceSymbol<Defined>(
902	s: sym, arg: sym->getName(), arg: nullptr, arg&: isec,
903	/*value=*/arg: symbols.size() * stubSize,
904	/*size=*/arg&: stubSize,
905	/*isWeakDef=*/arg: false, /*isExternal=*/arg: true, /*isPrivateExtern=*/arg: true,
906	/*includeInSymtab=*/arg: true, /*isReferencedDynamically=*/arg: false,
907	/*noDeadStrip=*/arg: false);
908	symbols.push_back(x: newSym);
909	}
910
911	void ObjCStubsSection::setUp() {
912	objcMsgSend = symtab->addUndefined(name: "_objc_msgSend", /*file=*/nullptr,
913	/*isWeakRef=*/false);
914	if (auto *undefined = dyn_cast<Undefined>(Val: objcMsgSend))
915	treatUndefinedSymbol(*undefined,
916	source: "lazy binding (normally in libobjc.dylib)");
917	objcMsgSend->used = true;
918	if (config->objcStubsMode == ObjCStubsMode::fast) {
919	in.got->addEntry(sym: objcMsgSend);
920	assert(objcMsgSend->isInGot());
921	} else {
922	assert(config->objcStubsMode == ObjCStubsMode::small);
923	// In line with ld64's behavior, when objc_msgSend is a direct symbol,
924	// we directly reference it.
925	// In other cases, typically when binding in libobjc.dylib,
926	// we generate a stub to invoke objc_msgSend.
927	if (!isa<Defined>(Val: objcMsgSend))
928	in.stubs->addEntry(sym: objcMsgSend);
929	}
930	}
931
932	uint64_t ObjCStubsSection::getSize() const {
933	auto stubSize = config->objcStubsMode == ObjCStubsMode::fast
934	? target->objcStubsFastSize
935	: target->objcStubsSmallSize;
936	return stubSize * symbols.size();
937	}
938
939	void ObjCStubsSection::writeTo(uint8_t *buf) const {
940	uint64_t stubOffset = 0;
941	for (size_t i = 0, n = symbols.size(); i < n; ++i) {
942	Defined *sym = symbols[i];
943
944	auto methname = getMethname(sym);
945	InputSection *selRef = ObjCSelRefsHelper::getSelRef(methname);
946	assert(selRef != nullptr && "no selref for methname");
947	auto selrefAddr = selRef->getVA(off: 0);
948	target->writeObjCMsgSendStub(buf: buf + stubOffset, sym, stubsAddr: in.objcStubs->addr,
949	stubOffset, selrefVA: selrefAddr, objcMsgSend);
950	}
951	}
952
953	LazyPointerSection::LazyPointerSection()
954	: SyntheticSection(segment_names::data, section_names::lazySymbolPtr) {
955	align = target->wordSize;
956	flags = S_LAZY_SYMBOL_POINTERS;
957	}
958
959	uint64_t LazyPointerSection::getSize() const {
960	return in.stubs->getEntries().size() * target->wordSize;
961	}
962
963	bool LazyPointerSection::isNeeded() const {
964	return !in.stubs->getEntries().empty();
965	}
966
967	void LazyPointerSection::writeTo(uint8_t *buf) const {
968	size_t off = 0;
969	for (const Symbol *sym : in.stubs->getEntries()) {
970	if (const auto *dysym = dyn_cast<DylibSymbol>(Val: sym)) {
971	if (dysym->hasStubsHelper()) {
972	uint64_t stubHelperOffset =
973	target->stubHelperHeaderSize +
974	dysym->stubsHelperIndex * target->stubHelperEntrySize;
975	write64le(P: buf + off, V: in.stubHelper->addr + stubHelperOffset);
976	}
977	} else {
978	write64le(P: buf + off, V: sym->getVA());
979	}
980	off += target->wordSize;
981	}
982	}
983
984	LazyBindingSection::LazyBindingSection()
985	: LinkEditSection(segment_names::linkEdit, section_names::lazyBinding) {}
986
987	void LazyBindingSection::finalizeContents() {
988	// TODO: Just precompute output size here instead of writing to a temporary
989	// buffer
990	for (Symbol *sym : entries)
991	sym->lazyBindOffset = encode(*sym);
992	}
993
994	void LazyBindingSection::writeTo(uint8_t *buf) const {
995	memcpy(dest: buf, src: contents.data(), n: contents.size());
996	}
997
998	void LazyBindingSection::addEntry(Symbol *sym) {
999	assert(!config->emitChainedFixups && "Chained fixups always bind eagerly");
1000	if (entries.insert(X: sym)) {
1001	sym->stubsHelperIndex = entries.size() - 1;
1002	in.rebase->addEntry(isec: in.lazyPointers->isec,
1003	offset: sym->stubsIndex * target->wordSize);
1004	}
1005	}
1006
1007	// Unlike the non-lazy binding section, the bind opcodes in this section aren't
1008	// interpreted all at once. Rather, dyld will start interpreting opcodes at a
1009	// given offset, typically only binding a single symbol before it finds a
1010	// BIND_OPCODE_DONE terminator. As such, unlike in the non-lazy-binding case,
1011	// we cannot encode just the differences between symbols; we have to emit the
1012	// complete bind information for each symbol.
1013	uint32_t LazyBindingSection::encode(const Symbol &sym) {
1014	uint32_t opstreamOffset = contents.size();
1015	OutputSegment *dataSeg = in.lazyPointers->parent;
1016	os << static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
1017	dataSeg->index);
1018	uint64_t offset =
1019	in.lazyPointers->addr - dataSeg->addr + sym.stubsIndex * target->wordSize;
1020	encodeULEB128(Value: offset, OS&: os);
1021	encodeDylibOrdinal(ordinal: ordinalForSymbol(sym), os);
1022
1023	uint8_t flags = BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
1024	if (sym.isWeakRef())
1025	flags |= BIND_SYMBOL_FLAGS_WEAK_IMPORT;
1026
1027	os << flags << sym.getName() << '\0'
1028	<< static_cast<uint8_t>(BIND_OPCODE_DO_BIND)
1029	<< static_cast<uint8_t>(BIND_OPCODE_DONE);
1030	return opstreamOffset;
1031	}
1032
1033	ExportSection::ExportSection()
1034	: LinkEditSection(segment_names::linkEdit, section_names::export_) {}
1035
1036	void ExportSection::finalizeContents() {
1037	trieBuilder.setImageBase(in.header->addr);
1038	for (const Symbol *sym : symtab->getSymbols()) {
1039	if (const auto *defined = dyn_cast<Defined>(Val: sym)) {
1040	if (defined->privateExtern || !defined->isLive())
1041	continue;
1042	trieBuilder.addSymbol(sym: *defined);
1043	hasWeakSymbol = hasWeakSymbol || sym->isWeakDef();
1044	} else if (auto *dysym = dyn_cast<DylibSymbol>(Val: sym)) {
1045	if (dysym->shouldReexport)
1046	trieBuilder.addSymbol(sym: *dysym);
1047	}
1048	}
1049	size = trieBuilder.build();
1050	}
1051
1052	void ExportSection::writeTo(uint8_t *buf) const { trieBuilder.writeTo(buf); }
1053
1054	DataInCodeSection::DataInCodeSection()
1055	: LinkEditSection(segment_names::linkEdit, section_names::dataInCode) {}
1056
1057	template <class LP>
1058	static std::vector<MachO::data_in_code_entry> collectDataInCodeEntries() {
1059	std::vector<MachO::data_in_code_entry> dataInCodeEntries;
1060	for (const InputFile *inputFile : inputFiles) {
1061	if (!isa<ObjFile>(Val: inputFile))
1062	continue;
1063	const ObjFile *objFile = cast<ObjFile>(Val: inputFile);
1064	ArrayRef<MachO::data_in_code_entry> entries = objFile->getDataInCode();
1065	if (entries.empty())
1066	continue;
1067
1068	std::vector<MachO::data_in_code_entry> sortedEntries;
1069	sortedEntries.assign(first: entries.begin(), last: entries.end());
1070	llvm::sort(sortedEntries, [](const data_in_code_entry &lhs,
1071	const data_in_code_entry &rhs) {
1072	return lhs.offset < rhs.offset;
1073	});
1074
1075	// For each code subsection find 'data in code' entries residing in it.
1076	// Compute the new offset values as
1077	// <offset within subsection> + <subsection address> - <__TEXT address>.
1078	for (const Section *section : objFile->sections) {
1079	for (const Subsection &subsec : section->subsections) {
1080	const InputSection *isec = subsec.isec;
1081	if (!isCodeSection(isec))
1082	continue;
1083	if (cast<ConcatInputSection>(Val: isec)->shouldOmitFromOutput())
1084	continue;
1085	const uint64_t beginAddr = section->addr + subsec.offset;
1086	auto it = llvm::lower_bound(
1087	sortedEntries, beginAddr,
1088	[](const MachO::data_in_code_entry &entry, uint64_t addr) {
1089	return entry.offset < addr;
1090	});
1091	const uint64_t endAddr = beginAddr + isec->getSize();
1092	for (const auto end = sortedEntries.end();
1093	it != end && it->offset + it->length <= endAddr; ++it)
1094	dataInCodeEntries.push_back(
1095	{static_cast<uint32_t>(isec->getVA(off: it->offset - beginAddr) -
1096	in.header->addr),
1097	it->length, it->kind});
1098	}
1099	}
1100	}
1101
1102	// ld64 emits the table in sorted order too.
1103	llvm::sort(dataInCodeEntries,
1104	[](const data_in_code_entry &lhs, const data_in_code_entry &rhs) {
1105	return lhs.offset < rhs.offset;
1106	});
1107	return dataInCodeEntries;
1108	}
1109
1110	void DataInCodeSection::finalizeContents() {
1111	entries = target->wordSize == 8 ? collectDataInCodeEntries<LP64>()
1112	: collectDataInCodeEntries<ILP32>();
1113	}
1114
1115	void DataInCodeSection::writeTo(uint8_t *buf) const {
1116	if (!entries.empty())
1117	memcpy(dest: buf, src: entries.data(), n: getRawSize());
1118	}
1119
1120	FunctionStartsSection::FunctionStartsSection()
1121	: LinkEditSection(segment_names::linkEdit, section_names::functionStarts) {}
1122
1123	void FunctionStartsSection::finalizeContents() {
1124	raw_svector_ostream os{contents};
1125	std::vector<uint64_t> addrs;
1126	for (const InputFile *file : inputFiles) {
1127	if (auto *objFile = dyn_cast<ObjFile>(Val: file)) {
1128	for (const Symbol *sym : objFile->symbols) {
1129	if (const auto *defined = dyn_cast_or_null<Defined>(Val: sym)) {
1130	if (!defined->isec() || !isCodeSection(defined->isec()) ||
1131	!defined->isLive())
1132	continue;
1133	addrs.push_back(x: defined->getVA());
1134	}
1135	}
1136	}
1137	}
1138	llvm::sort(C&: addrs);
1139	uint64_t addr = in.header->addr;
1140	for (uint64_t nextAddr : addrs) {
1141	uint64_t delta = nextAddr - addr;
1142	if (delta == 0)
1143	continue;
1144	encodeULEB128(Value: delta, OS&: os);
1145	addr = nextAddr;
1146	}
1147	os << '\0';
1148	}
1149
1150	void FunctionStartsSection::writeTo(uint8_t *buf) const {
1151	memcpy(dest: buf, src: contents.data(), n: contents.size());
1152	}
1153
1154	SymtabSection::SymtabSection(StringTableSection &stringTableSection)
1155	: LinkEditSection(segment_names::linkEdit, section_names::symbolTable),
1156	stringTableSection(stringTableSection) {}
1157
1158	void SymtabSection::emitBeginSourceStab(StringRef sourceFile) {
1159	StabsEntry stab(N_SO);
1160	stab.strx = stringTableSection.addString(saver().save(S: sourceFile));
1161	stabs.emplace_back(args: std::move(stab));
1162	}
1163
1164	void SymtabSection::emitEndSourceStab() {
1165	StabsEntry stab(N_SO);
1166	stab.sect = 1;
1167	stabs.emplace_back(args: std::move(stab));
1168	}
1169
1170	void SymtabSection::emitObjectFileStab(ObjFile *file) {
1171	StabsEntry stab(N_OSO);
1172	stab.sect = target->cpuSubtype;
1173	SmallString<261> path(!file->archiveName.empty() ? file->archiveName
1174	: file->getName());
1175	std::error_code ec = sys::fs::make_absolute(path);
1176	if (ec)
1177	fatal(msg: "failed to get absolute path for " + path);
1178
1179	if (!file->archiveName.empty())
1180	path.append(Refs: {"(", file->getName(), ")"});
1181
1182	StringRef adjustedPath = saver().save(S: path.str());
1183	adjustedPath.consume_front(Prefix: config->osoPrefix);
1184
1185	stab.strx = stringTableSection.addString(adjustedPath);
1186	stab.desc = 1;
1187	stab.value = file->modTime;
1188	stabs.emplace_back(args: std::move(stab));
1189	}
1190
1191	void SymtabSection::emitEndFunStab(Defined *defined) {
1192	StabsEntry stab(N_FUN);
1193	stab.value = defined->size;
1194	stabs.emplace_back(args: std::move(stab));
1195	}
1196
1197	void SymtabSection::emitStabs() {
1198	if (config->omitDebugInfo)
1199	return;
1200
1201	for (const std::string &s : config->astPaths) {
1202	StabsEntry astStab(N_AST);
1203	astStab.strx = stringTableSection.addString(s);
1204	stabs.emplace_back(args: std::move(astStab));
1205	}
1206
1207	// Cache the file ID for each symbol in an std::pair for faster sorting.
1208	using SortingPair = std::pair<Defined *, int>;
1209	std::vector<SortingPair> symbolsNeedingStabs;
1210	for (const SymtabEntry &entry :
1211	concat<SymtabEntry>(Ranges&: localSymbols, Ranges&: externalSymbols)) {
1212	Symbol *sym = entry.sym;
1213	assert(sym->isLive() &&
1214	"dead symbols should not be in localSymbols, externalSymbols");
1215	if (auto *defined = dyn_cast<Defined>(Val: sym)) {
1216	// Excluded symbols should have been filtered out in finalizeContents().
1217	assert(defined->includeInSymtab);
1218
1219	if (defined->isAbsolute())
1220	continue;
1221
1222	// Constant-folded symbols go in the executable's symbol table, but don't
1223	// get a stabs entry.
1224	if (defined->wasIdenticalCodeFolded)
1225	continue;
1226
1227	ObjFile *file = defined->getObjectFile();
1228	if (!file || !file->compileUnit)
1229	continue;
1230
1231	symbolsNeedingStabs.emplace_back(args&: defined, args: defined->isec()->getFile()->id);
1232	}
1233	}
1234
1235	llvm::stable_sort(Range&: symbolsNeedingStabs,
1236	C: [&](const SortingPair &a, const SortingPair &b) {
1237	return a.second < b.second;
1238	});
1239
1240	// Emit STABS symbols so that dsymutil and/or the debugger can map address
1241	// regions in the final binary to the source and object files from which they
1242	// originated.
1243	InputFile *lastFile = nullptr;
1244	for (SortingPair &pair : symbolsNeedingStabs) {
1245	Defined *defined = pair.first;
1246	InputSection *isec = defined->isec();
1247	ObjFile *file = cast<ObjFile>(Val: isec->getFile());
1248
1249	if (lastFile == nullptr || lastFile != file) {
1250	if (lastFile != nullptr)
1251	emitEndSourceStab();
1252	lastFile = file;
1253
1254	emitBeginSourceStab(sourceFile: file->sourceFile());
1255	emitObjectFileStab(file);
1256	}
1257
1258	StabsEntry symStab;
1259	symStab.sect = defined->isec()->parent->index;
1260	symStab.strx = stringTableSection.addString(defined->getName());
1261	symStab.value = defined->getVA();
1262
1263	if (isCodeSection(isec)) {
1264	symStab.type = N_FUN;
1265	stabs.emplace_back(args: std::move(symStab));
1266	emitEndFunStab(defined);
1267	} else {
1268	symStab.type = defined->isExternal() ? N_GSYM : N_STSYM;
1269	stabs.emplace_back(args: std::move(symStab));
1270	}
1271	}
1272
1273	if (!stabs.empty())
1274	emitEndSourceStab();
1275	}
1276
1277	void SymtabSection::finalizeContents() {
1278	auto addSymbol = [&](std::vector<SymtabEntry> &symbols, Symbol *sym) {
1279	uint32_t strx = stringTableSection.addString(sym->getName());
1280	symbols.push_back(x: {.sym: sym, .strx: strx});
1281	};
1282
1283	std::function<void(Symbol *)> localSymbolsHandler;
1284	switch (config->localSymbolsPresence) {
1285	case SymtabPresence::All:
1286	localSymbolsHandler = [&](Symbol *sym) { addSymbol(localSymbols, sym); };
1287	break;
1288	case SymtabPresence::None:
1289	localSymbolsHandler = [&](Symbol *) { /* Do nothing*/ };
1290	break;
1291	case SymtabPresence::SelectivelyIncluded:
1292	localSymbolsHandler = [&](Symbol *sym) {
1293	if (config->localSymbolPatterns.match(symbolName: sym->getName()))
1294	addSymbol(localSymbols, sym);
1295	};
1296	break;
1297	case SymtabPresence::SelectivelyExcluded:
1298	localSymbolsHandler = [&](Symbol *sym) {
1299	if (!config->localSymbolPatterns.match(symbolName: sym->getName()))
1300	addSymbol(localSymbols, sym);
1301	};
1302	break;
1303	}
1304
1305	// Local symbols aren't in the SymbolTable, so we walk the list of object
1306	// files to gather them.
1307	// But if `-x` is set, then we don't need to. localSymbolsHandler() will do
1308	// the right thing regardless, but this check is a perf optimization because
1309	// iterating through all the input files and their symbols is expensive.
1310	if (config->localSymbolsPresence != SymtabPresence::None) {
1311	for (const InputFile *file : inputFiles) {
1312	if (auto *objFile = dyn_cast<ObjFile>(Val: file)) {
1313	for (Symbol *sym : objFile->symbols) {
1314	if (auto *defined = dyn_cast_or_null<Defined>(Val: sym)) {
1315	if (defined->isExternal() || !defined->isLive() ||
1316	!defined->includeInSymtab)
1317	continue;
1318	localSymbolsHandler(sym);
1319	}
1320	}
1321	}
1322	}
1323	}
1324
1325	// __dyld_private is a local symbol too. It's linker-created and doesn't
1326	// exist in any object file.
1327	if (in.stubHelper && in.stubHelper->dyldPrivate)
1328	localSymbolsHandler(in.stubHelper->dyldPrivate);
1329
1330	for (Symbol *sym : symtab->getSymbols()) {
1331	if (!sym->isLive())
1332	continue;
1333	if (auto *defined = dyn_cast<Defined>(Val: sym)) {
1334	if (!defined->includeInSymtab)
1335	continue;
1336	assert(defined->isExternal());
1337	if (defined->privateExtern)
1338	localSymbolsHandler(defined);
1339	else
1340	addSymbol(externalSymbols, defined);
1341	} else if (auto *dysym = dyn_cast<DylibSymbol>(Val: sym)) {
1342	if (dysym->isReferenced())
1343	addSymbol(undefinedSymbols, sym);
1344	}
1345	}
1346
1347	emitStabs();
1348	uint32_t symtabIndex = stabs.size();
1349	for (const SymtabEntry &entry :
1350	concat<SymtabEntry>(Ranges&: localSymbols, Ranges&: externalSymbols, Ranges&: undefinedSymbols)) {
1351	entry.sym->symtabIndex = symtabIndex++;
1352	}
1353	}
1354
1355	uint32_t SymtabSection::getNumSymbols() const {
1356	return stabs.size() + localSymbols.size() + externalSymbols.size() +
1357	undefinedSymbols.size();
1358	}
1359
1360	// This serves to hide (type-erase) the template parameter from SymtabSection.
1361	template <class LP> class SymtabSectionImpl final : public SymtabSection {
1362	public:
1363	SymtabSectionImpl(StringTableSection &stringTableSection)
1364	: SymtabSection(stringTableSection) {}
1365	uint64_t getRawSize() const override;
1366	void writeTo(uint8_t *buf) const override;
1367	};
1368
1369	template <class LP> uint64_t SymtabSectionImpl<LP>::getRawSize() const {
1370	return getNumSymbols() * sizeof(typename LP::nlist);
1371	}
1372
1373	template <class LP> void SymtabSectionImpl<LP>::writeTo(uint8_t *buf) const {
1374	auto *nList = reinterpret_cast<typename LP::nlist *>(buf);
1375	// Emit the stabs entries before the "real" symbols. We cannot emit them
1376	// after as that would render Symbol::symtabIndex inaccurate.
1377	for (const StabsEntry &entry : stabs) {
1378	nList->n_strx = entry.strx;
1379	nList->n_type = entry.type;
1380	nList->n_sect = entry.sect;
1381	nList->n_desc = entry.desc;
1382	nList->n_value = entry.value;
1383	++nList;
1384	}
1385
1386	for (const SymtabEntry &entry : concat<const SymtabEntry>(
1387	localSymbols, externalSymbols, undefinedSymbols)) {
1388	nList->n_strx = entry.strx;
1389	// TODO populate n_desc with more flags
1390	if (auto *defined = dyn_cast<Defined>(Val: entry.sym)) {
1391	uint8_t scope = 0;
1392	if (defined->privateExtern) {
1393	// Private external -- dylib scoped symbol.
1394	// Promote to non-external at link time.
1395	scope = N_PEXT;
1396	} else if (defined->isExternal()) {
1397	// Normal global symbol.
1398	scope = N_EXT;
1399	} else {
1400	// TU-local symbol from localSymbols.
1401	scope = 0;
1402	}
1403
1404	if (defined->isAbsolute()) {
1405	nList->n_type = scope | N_ABS;
1406	nList->n_sect = NO_SECT;
1407	nList->n_value = defined->value;
1408	} else {
1409	nList->n_type = scope | N_SECT;
1410	nList->n_sect = defined->isec()->parent->index;
1411	// For the N_SECT symbol type, n_value is the address of the symbol
1412	nList->n_value = defined->getVA();
1413	}
1414	nList->n_desc |= defined->isExternalWeakDef() ? N_WEAK_DEF : 0;
1415	nList->n_desc |=
1416	defined->referencedDynamically ? REFERENCED_DYNAMICALLY : 0;
1417	} else if (auto *dysym = dyn_cast<DylibSymbol>(Val: entry.sym)) {
1418	uint16_t n_desc = nList->n_desc;
1419	int16_t ordinal = ordinalForDylibSymbol(dysym: *dysym);
1420	if (ordinal == BIND_SPECIAL_DYLIB_FLAT_LOOKUP)
1421	SET_LIBRARY_ORDINAL(n_desc, ordinal: DYNAMIC_LOOKUP_ORDINAL);
1422	else if (ordinal == BIND_SPECIAL_DYLIB_MAIN_EXECUTABLE)
1423	SET_LIBRARY_ORDINAL(n_desc, ordinal: EXECUTABLE_ORDINAL);
1424	else {
1425	assert(ordinal > 0);
1426	SET_LIBRARY_ORDINAL(n_desc, ordinal: static_cast<uint8_t>(ordinal));
1427	}
1428
1429	nList->n_type = N_EXT;
1430	n_desc |= dysym->isWeakDef() ? N_WEAK_DEF : 0;
1431	n_desc |= dysym->isWeakRef() ? N_WEAK_REF : 0;
1432	nList->n_desc = n_desc;
1433	}
1434	++nList;
1435	}
1436	}
1437
1438	template <class LP>
1439	SymtabSection *
1440	macho::makeSymtabSection(StringTableSection &stringTableSection) {
1441	return make<SymtabSectionImpl<LP>>(stringTableSection);
1442	}
1443
1444	IndirectSymtabSection::IndirectSymtabSection()
1445	: LinkEditSection(segment_names::linkEdit,
1446	section_names::indirectSymbolTable) {}
1447
1448	uint32_t IndirectSymtabSection::getNumSymbols() const {
1449	uint32_t size = in.got->getEntries().size() +
1450	in.tlvPointers->getEntries().size() +
1451	in.stubs->getEntries().size();
1452	if (!config->emitChainedFixups)
1453	size += in.stubs->getEntries().size();
1454	return size;
1455	}
1456
1457	bool IndirectSymtabSection::isNeeded() const {
1458	return in.got->isNeeded() || in.tlvPointers->isNeeded() ||
1459	in.stubs->isNeeded();
1460	}
1461
1462	void IndirectSymtabSection::finalizeContents() {
1463	uint32_t off = 0;
1464	in.got->reserved1 = off;
1465	off += in.got->getEntries().size();
1466	in.tlvPointers->reserved1 = off;
1467	off += in.tlvPointers->getEntries().size();
1468	in.stubs->reserved1 = off;
1469	if (in.lazyPointers) {
1470	off += in.stubs->getEntries().size();
1471	in.lazyPointers->reserved1 = off;
1472	}
1473	}
1474
1475	static uint32_t indirectValue(const Symbol *sym) {
1476	if (sym->symtabIndex == UINT32_MAX)
1477	return INDIRECT_SYMBOL_LOCAL;
1478	if (auto *defined = dyn_cast<Defined>(Val: sym))
1479	if (defined->privateExtern)
1480	return INDIRECT_SYMBOL_LOCAL;
1481	return sym->symtabIndex;
1482	}
1483
1484	void IndirectSymtabSection::writeTo(uint8_t *buf) const {
1485	uint32_t off = 0;
1486	for (const Symbol *sym : in.got->getEntries()) {
1487	write32le(P: buf + off * sizeof(uint32_t), V: indirectValue(sym));
1488	++off;
1489	}
1490	for (const Symbol *sym : in.tlvPointers->getEntries()) {
1491	write32le(P: buf + off * sizeof(uint32_t), V: indirectValue(sym));
1492	++off;
1493	}
1494	for (const Symbol *sym : in.stubs->getEntries()) {
1495	write32le(P: buf + off * sizeof(uint32_t), V: indirectValue(sym));
1496	++off;
1497	}
1498
1499	if (in.lazyPointers) {
1500	// There is a 1:1 correspondence between stubs and LazyPointerSection
1501	// entries. But giving __stubs and __la_symbol_ptr the same reserved1
1502	// (the offset into the indirect symbol table) so that they both refer
1503	// to the same range of offsets confuses `strip`, so write the stubs
1504	// symbol table offsets a second time.
1505	for (const Symbol *sym : in.stubs->getEntries()) {
1506	write32le(P: buf + off * sizeof(uint32_t), V: indirectValue(sym));
1507	++off;
1508	}
1509	}
1510	}
1511
1512	StringTableSection::StringTableSection()
1513	: LinkEditSection(segment_names::linkEdit, section_names::stringTable) {}
1514
1515	uint32_t StringTableSection::addString(StringRef str) {
1516	uint32_t strx = size;
1517	strings.push_back(x: str); // TODO: consider deduplicating strings
1518	size += str.size() + 1; // account for null terminator
1519	return strx;
1520	}
1521
1522	void StringTableSection::writeTo(uint8_t *buf) const {
1523	uint32_t off = 0;
1524	for (StringRef str : strings) {
1525	memcpy(dest: buf + off, src: str.data(), n: str.size());
1526	off += str.size() + 1; // account for null terminator
1527	}
1528	}
1529
1530	static_assert((CodeSignatureSection::blobHeadersSize % 8) == 0);
1531	static_assert((CodeSignatureSection::fixedHeadersSize % 8) == 0);
1532
1533	CodeSignatureSection::CodeSignatureSection()
1534	: LinkEditSection(segment_names::linkEdit, section_names::codeSignature) {
1535	align = 16; // required by libstuff
1536
1537	// XXX: This mimics LD64, where it uses the install-name as codesign
1538	// identifier, if available.
1539	if (!config->installName.empty())
1540	fileName = config->installName;
1541	else
1542	// FIXME: Consider using finalOutput instead of outputFile.
1543	fileName = config->outputFile;
1544
1545	size_t slashIndex = fileName.rfind(Str: "/");
1546	if (slashIndex != std::string::npos)
1547	fileName = fileName.drop_front(N: slashIndex + 1);
1548
1549	// NOTE: Any changes to these calculations should be repeated
1550	// in llvm-objcopy's MachOLayoutBuilder::layoutTail.
1551	allHeadersSize = alignTo<16>(Value: fixedHeadersSize + fileName.size() + 1);
1552	fileNamePad = allHeadersSize - fixedHeadersSize - fileName.size();
1553	}
1554
1555	uint32_t CodeSignatureSection::getBlockCount() const {
1556	return (fileOff + blockSize - 1) / blockSize;
1557	}
1558
1559	uint64_t CodeSignatureSection::getRawSize() const {
1560	return allHeadersSize + getBlockCount() * hashSize;
1561	}
1562
1563	void CodeSignatureSection::writeHashes(uint8_t *buf) const {
1564	// NOTE: Changes to this functionality should be repeated in llvm-objcopy's
1565	// MachOWriter::writeSignatureData.
1566	uint8_t *hashes = buf + fileOff + allHeadersSize;
1567	parallelFor(Begin: 0, End: getBlockCount(), Fn: [&](size_t i) {
1568	sha256(data: buf + i * blockSize,
1569	len: std::min(a: static_cast<size_t>(fileOff - i * blockSize), b: blockSize),
1570	output: hashes + i * hashSize);
1571	});
1572	#if defined(__APPLE__)
1573	// This is macOS-specific work-around and makes no sense for any
1574	// other host OS. See https://openradar.appspot.com/FB8914231
1575	//
1576	// The macOS kernel maintains a signature-verification cache to
1577	// quickly validate applications at time of execve(2). The trouble
1578	// is that for the kernel creates the cache entry at the time of the
1579	// mmap(2) call, before we have a chance to write either the code to
1580	// sign or the signature header+hashes. The fix is to invalidate
1581	// all cached data associated with the output file, thus discarding
1582	// the bogus prematurely-cached signature.
1583	msync(buf, fileOff + getSize(), MS_INVALIDATE);
1584	#endif
1585	}
1586
1587	void CodeSignatureSection::writeTo(uint8_t *buf) const {
1588	// NOTE: Changes to this functionality should be repeated in llvm-objcopy's
1589	// MachOWriter::writeSignatureData.
1590	uint32_t signatureSize = static_cast<uint32_t>(getSize());
1591	auto *superBlob = reinterpret_cast<CS_SuperBlob *>(buf);
1592	write32be(P: &superBlob->magic, V: CSMAGIC_EMBEDDED_SIGNATURE);
1593	write32be(P: &superBlob->length, V: signatureSize);
1594	write32be(P: &superBlob->count, V: 1);
1595	auto *blobIndex = reinterpret_cast<CS_BlobIndex *>(&superBlob[1]);
1596	write32be(P: &blobIndex->type, V: CSSLOT_CODEDIRECTORY);
1597	write32be(P: &blobIndex->offset, V: blobHeadersSize);
1598	auto *codeDirectory =
1599	reinterpret_cast<CS_CodeDirectory *>(buf + blobHeadersSize);
1600	write32be(P: &codeDirectory->magic, V: CSMAGIC_CODEDIRECTORY);
1601	write32be(P: &codeDirectory->length, V: signatureSize - blobHeadersSize);
1602	write32be(P: &codeDirectory->version, V: CS_SUPPORTSEXECSEG);
1603	write32be(P: &codeDirectory->flags, V: CS_ADHOC | CS_LINKER_SIGNED);
1604	write32be(P: &codeDirectory->hashOffset,
1605	V: sizeof(CS_CodeDirectory) + fileName.size() + fileNamePad);
1606	write32be(P: &codeDirectory->identOffset, V: sizeof(CS_CodeDirectory));
1607	codeDirectory->nSpecialSlots = 0;
1608	write32be(P: &codeDirectory->nCodeSlots, V: getBlockCount());
1609	write32be(P: &codeDirectory->codeLimit, V: fileOff);
1610	codeDirectory->hashSize = static_cast<uint8_t>(hashSize);
1611	codeDirectory->hashType = kSecCodeSignatureHashSHA256;
1612	codeDirectory->platform = 0;
1613	codeDirectory->pageSize = blockSizeShift;
1614	codeDirectory->spare2 = 0;
1615	codeDirectory->scatterOffset = 0;
1616	codeDirectory->teamOffset = 0;
1617	codeDirectory->spare3 = 0;
1618	codeDirectory->codeLimit64 = 0;
1619	OutputSegment *textSeg = getOrCreateOutputSegment(name: segment_names::text);
1620	write64be(P: &codeDirectory->execSegBase, V: textSeg->fileOff);
1621	write64be(P: &codeDirectory->execSegLimit, V: textSeg->fileSize);
1622	write64be(P: &codeDirectory->execSegFlags,
1623	V: config->outputType == MH_EXECUTE ? CS_EXECSEG_MAIN_BINARY : 0);
1624	auto *id = reinterpret_cast<char *>(&codeDirectory[1]);
1625	memcpy(dest: id, src: fileName.begin(), n: fileName.size());
1626	memset(s: id + fileName.size(), c: 0, n: fileNamePad);
1627	}
1628
1629	CStringSection::CStringSection(const char *name)
1630	: SyntheticSection(segment_names::text, name) {
1631	flags = S_CSTRING_LITERALS;
1632	}
1633
1634	void CStringSection::addInput(CStringInputSection *isec) {
1635	isec->parent = this;
1636	inputs.push_back(x: isec);
1637	if (isec->align > align)
1638	align = isec->align;
1639	}
1640
1641	void CStringSection::writeTo(uint8_t *buf) const {
1642	for (const CStringInputSection *isec : inputs) {
1643	for (const auto &[i, piece] : llvm::enumerate(First: isec->pieces)) {
1644	if (!piece.live)
1645	continue;
1646	StringRef string = isec->getStringRef(i);
1647	memcpy(dest: buf + piece.outSecOff, src: string.data(), n: string.size());
1648	}
1649	}
1650	}
1651
1652	void CStringSection::finalizeContents() {
1653	uint64_t offset = 0;
1654	for (CStringInputSection *isec : inputs) {
1655	for (const auto &[i, piece] : llvm::enumerate(First&: isec->pieces)) {
1656	if (!piece.live)
1657	continue;
1658	// See comment above DeduplicatedCStringSection for how alignment is
1659	// handled.
1660	uint32_t pieceAlign = 1
1661	<< llvm::countr_zero(Val: isec->align | piece.inSecOff);
1662	offset = alignToPowerOf2(Value: offset, Align: pieceAlign);
1663	piece.outSecOff = offset;
1664	isec->isFinal = true;
1665	StringRef string = isec->getStringRef(i);
1666	offset += string.size() + 1; // account for null terminator
1667	}
1668	}
1669	size = offset;
1670	}
1671
1672	// Mergeable cstring literals are found under the __TEXT,__cstring section. In
1673	// contrast to ELF, which puts strings that need different alignments into
1674	// different sections, clang's Mach-O backend puts them all in one section.
1675	// Strings that need to be aligned have the .p2align directive emitted before
1676	// them, which simply translates into zero padding in the object file. In other
1677	// words, we have to infer the desired alignment of these cstrings from their
1678	// addresses.
1679	//
1680	// We differ slightly from ld64 in how we've chosen to align these cstrings.
1681	// Both LLD and ld64 preserve the number of trailing zeros in each cstring's
1682	// address in the input object files. When deduplicating identical cstrings,
1683	// both linkers pick the cstring whose address has more trailing zeros, and
1684	// preserve the alignment of that address in the final binary. However, ld64
1685	// goes a step further and also preserves the offset of the cstring from the
1686	// last section-aligned address. I.e. if a cstring is at offset 18 in the
1687	// input, with a section alignment of 16, then both LLD and ld64 will ensure the
1688	// final address is 2-byte aligned (since 18 == 16 + 2). But ld64 will also
1689	// ensure that the final address is of the form 16 * k + 2 for some k.
1690	//
1691	// Note that ld64's heuristic means that a dedup'ed cstring's final address is
1692	// dependent on the order of the input object files. E.g. if in addition to the
1693	// cstring at offset 18 above, we have a duplicate one in another file with a
1694	// `.cstring` section alignment of 2 and an offset of zero, then ld64 will pick
1695	// the cstring from the object file earlier on the command line (since both have
1696	// the same number of trailing zeros in their address). So the final cstring may
1697	// either be at some address `16 * k + 2` or at some address `2 * k`.
1698	//
1699	// I've opted not to follow this behavior primarily for implementation
1700	// simplicity, and secondarily to save a few more bytes. It's not clear to me
1701	// that preserving the section alignment + offset is ever necessary, and there
1702	// are many cases that are clearly redundant. In particular, if an x86_64 object
1703	// file contains some strings that are accessed via SIMD instructions, then the
1704	// .cstring section in the object file will be 16-byte-aligned (since SIMD
1705	// requires its operand addresses to be 16-byte aligned). However, there will
1706	// typically also be other cstrings in the same file that aren't used via SIMD
1707	// and don't need this alignment. They will be emitted at some arbitrary address
1708	// `A`, but ld64 will treat them as being 16-byte aligned with an offset of `16
1709	// % A`.
1710	void DeduplicatedCStringSection::finalizeContents() {
1711	// Find the largest alignment required for each string.
1712	for (const CStringInputSection *isec : inputs) {
1713	for (const auto &[i, piece] : llvm::enumerate(First: isec->pieces)) {
1714	if (!piece.live)
1715	continue;
1716	auto s = isec->getCachedHashStringRef(i);
1717	assert(isec->align != 0);
1718	uint8_t trailingZeros = llvm::countr_zero(Val: isec->align | piece.inSecOff);
1719	auto it = stringOffsetMap.insert(
1720	KV: std::make_pair(x&: s, y: StringOffset(trailingZeros)));
1721	if (!it.second && it.first->second.trailingZeros < trailingZeros)
1722	it.first->second.trailingZeros = trailingZeros;
1723	}
1724	}
1725
1726	// Assign an offset for each string and save it to the corresponding
1727	// StringPieces for easy access.
1728	for (CStringInputSection *isec : inputs) {
1729	for (const auto &[i, piece] : llvm::enumerate(First&: isec->pieces)) {
1730	if (!piece.live)
1731	continue;
1732	auto s = isec->getCachedHashStringRef(i);
1733	auto it = stringOffsetMap.find(Val: s);
1734	assert(it != stringOffsetMap.end());
1735	StringOffset &offsetInfo = it->second;
1736	if (offsetInfo.outSecOff == UINT64_MAX) {
1737	offsetInfo.outSecOff =
1738	alignToPowerOf2(Value: size, Align: 1ULL << offsetInfo.trailingZeros);
1739	size =
1740	offsetInfo.outSecOff + s.size() + 1; // account for null terminator
1741	}
1742	piece.outSecOff = offsetInfo.outSecOff;
1743	}
1744	isec->isFinal = true;
1745	}
1746	}
1747
1748	void DeduplicatedCStringSection::writeTo(uint8_t *buf) const {
1749	for (const auto &p : stringOffsetMap) {
1750	StringRef data = p.first.val();
1751	uint64_t off = p.second.outSecOff;
1752	if (!data.empty())
1753	memcpy(dest: buf + off, src: data.data(), n: data.size());
1754	}
1755	}
1756
1757	DeduplicatedCStringSection::StringOffset
1758	DeduplicatedCStringSection::getStringOffset(StringRef str) const {
1759	// StringPiece uses 31 bits to store the hashes, so we replicate that
1760	uint32_t hash = xxh3_64bits(data: str) & 0x7fffffff;
1761	auto offset = stringOffsetMap.find(Val: CachedHashStringRef(str, hash));
1762	assert(offset != stringOffsetMap.end() &&
1763	"Looked-up strings should always exist in section");
1764	return offset->second;
1765	}
1766
1767	// This section is actually emitted as __TEXT,__const by ld64, but clang may
1768	// emit input sections of that name, and LLD doesn't currently support mixing
1769	// synthetic and concat-type OutputSections. To work around this, I've given
1770	// our merged-literals section a different name.
1771	WordLiteralSection::WordLiteralSection()
1772	: SyntheticSection(segment_names::text, section_names::literals) {
1773	align = 16;
1774	}
1775
1776	void WordLiteralSection::addInput(WordLiteralInputSection *isec) {
1777	isec->parent = this;
1778	inputs.push_back(x: isec);
1779	}
1780
1781	void WordLiteralSection::finalizeContents() {
1782	for (WordLiteralInputSection *isec : inputs) {
1783	// We do all processing of the InputSection here, so it will be effectively
1784	// finalized.
1785	isec->isFinal = true;
1786	const uint8_t *buf = isec->data.data();
1787	switch (sectionType(flags: isec->getFlags())) {
1788	case S_4BYTE_LITERALS: {
1789	for (size_t off = 0, e = isec->data.size(); off < e; off += 4) {
1790	if (!isec->isLive(off))
1791	continue;
1792	uint32_t value = *reinterpret_cast<const uint32_t *>(buf + off);
1793	literal4Map.emplace(args&: value, args: literal4Map.size());
1794	}
1795	break;
1796	}
1797	case S_8BYTE_LITERALS: {
1798	for (size_t off = 0, e = isec->data.size(); off < e; off += 8) {
1799	if (!isec->isLive(off))
1800	continue;
1801	uint64_t value = *reinterpret_cast<const uint64_t *>(buf + off);
1802	literal8Map.emplace(args&: value, args: literal8Map.size());
1803	}
1804	break;
1805	}
1806	case S_16BYTE_LITERALS: {
1807	for (size_t off = 0, e = isec->data.size(); off < e; off += 16) {
1808	if (!isec->isLive(off))
1809	continue;
1810	UInt128 value = *reinterpret_cast<const UInt128 *>(buf + off);
1811	literal16Map.emplace(args&: value, args: literal16Map.size());
1812	}
1813	break;
1814	}
1815	default:
1816	llvm_unreachable("invalid literal section type");
1817	}
1818	}
1819	}
1820
1821	void WordLiteralSection::writeTo(uint8_t *buf) const {
1822	// Note that we don't attempt to do any endianness conversion in addInput(),
1823	// so we don't do it here either -- just write out the original value,
1824	// byte-for-byte.
1825	for (const auto &p : literal16Map)
1826	memcpy(dest: buf + p.second * 16, src: &p.first, n: 16);
1827	buf += literal16Map.size() * 16;
1828
1829	for (const auto &p : literal8Map)
1830	memcpy(dest: buf + p.second * 8, src: &p.first, n: 8);
1831	buf += literal8Map.size() * 8;
1832
1833	for (const auto &p : literal4Map)
1834	memcpy(dest: buf + p.second * 4, src: &p.first, n: 4);
1835	}
1836
1837	ObjCImageInfoSection::ObjCImageInfoSection()
1838	: SyntheticSection(segment_names::data, section_names::objCImageInfo) {}
1839
1840	ObjCImageInfoSection::ImageInfo
1841	ObjCImageInfoSection::parseImageInfo(const InputFile *file) {
1842	ImageInfo info;
1843	ArrayRef<uint8_t> data = file->objCImageInfo;
1844	// The image info struct has the following layout:
1845	// struct {
1846	// uint32_t version;
1847	// uint32_t flags;
1848	// };
1849	if (data.size() < 8) {
1850	warn(msg: toString(file) + ": invalid __objc_imageinfo size");
1851	return info;
1852	}
1853
1854	auto *buf = reinterpret_cast<const uint32_t *>(data.data());
1855	if (read32le(P: buf) != 0) {
1856	warn(msg: toString(file) + ": invalid __objc_imageinfo version");
1857	return info;
1858	}
1859
1860	uint32_t flags = read32le(P: buf + 1);
1861	info.swiftVersion = (flags >> 8) & 0xff;
1862	info.hasCategoryClassProperties = flags & 0x40;
1863	return info;
1864	}
1865
1866	static std::string swiftVersionString(uint8_t version) {
1867	switch (version) {
1868	case 1:
1869	return "1.0";
1870	case 2:
1871	return "1.1";
1872	case 3:
1873	return "2.0";
1874	case 4:
1875	return "3.0";
1876	case 5:
1877	return "4.0";
1878	default:
1879	return ("0x" + Twine::utohexstr(Val: version)).str();
1880	}
1881	}
1882
1883	// Validate each object file's __objc_imageinfo and use them to generate the
1884	// image info for the output binary. Only two pieces of info are relevant:
1885	// 1. The Swift version (should be identical across inputs)
1886	// 2. `bool hasCategoryClassProperties` (true only if true for all inputs)
1887	void ObjCImageInfoSection::finalizeContents() {
1888	assert(files.size() != 0); // should have already been checked via isNeeded()
1889
1890	info.hasCategoryClassProperties = true;
1891	const InputFile *firstFile;
1892	for (const InputFile *file : files) {
1893	ImageInfo inputInfo = parseImageInfo(file);
1894	info.hasCategoryClassProperties &= inputInfo.hasCategoryClassProperties;
1895
1896	// swiftVersion 0 means no Swift is present, so no version checking required
1897	if (inputInfo.swiftVersion == 0)
1898	continue;
1899
1900	if (info.swiftVersion != 0 && info.swiftVersion != inputInfo.swiftVersion) {
1901	error(msg: "Swift version mismatch: " + toString(file: firstFile) + " has version " +
1902	swiftVersionString(version: info.swiftVersion) + " but " + toString(file) +
1903	" has version " + swiftVersionString(version: inputInfo.swiftVersion));
1904	} else {
1905	info.swiftVersion = inputInfo.swiftVersion;
1906	firstFile = file;
1907	}
1908	}
1909	}
1910
1911	void ObjCImageInfoSection::writeTo(uint8_t *buf) const {
1912	uint32_t flags = info.hasCategoryClassProperties ? 0x40 : 0x0;
1913	flags |= info.swiftVersion << 8;
1914	write32le(P: buf + 4, V: flags);
1915	}
1916
1917	InitOffsetsSection::InitOffsetsSection()
1918	: SyntheticSection(segment_names::text, section_names::initOffsets) {
1919	flags = S_INIT_FUNC_OFFSETS;
1920	align = 4; // This section contains 32-bit integers.
1921	}
1922
1923	uint64_t InitOffsetsSection::getSize() const {
1924	size_t count = 0;
1925	for (const ConcatInputSection *isec : sections)
1926	count += isec->relocs.size();
1927	return count * sizeof(uint32_t);
1928	}
1929
1930	void InitOffsetsSection::writeTo(uint8_t *buf) const {
1931	// FIXME: Add function specified by -init when that argument is implemented.
1932	for (ConcatInputSection *isec : sections) {
1933	for (const Reloc &rel : isec->relocs) {
1934	const Symbol *referent = rel.referent.dyn_cast<Symbol *>();
1935	assert(referent && "section relocation should have been rejected");
1936	uint64_t offset = referent->getVA() - in.header->addr;
1937	// FIXME: Can we handle this gracefully?
1938	if (offset > UINT32_MAX)
1939	fatal(msg: isec->getLocation(off: rel.offset) + ": offset to initializer " +
1940	referent->getName() + " (" + utohexstr(X: offset) +
1941	") does not fit in 32 bits");
1942
1943	// Entries need to be added in the order they appear in the section, but
1944	// relocations aren't guaranteed to be sorted.
1945	size_t index = rel.offset >> target->p2WordSize;
1946	write32le(P: &buf[index * sizeof(uint32_t)], V: offset);
1947	}
1948	buf += isec->relocs.size() * sizeof(uint32_t);
1949	}
1950	}
1951
1952	// The inputs are __mod_init_func sections, which contain pointers to
1953	// initializer functions, therefore all relocations should be of the UNSIGNED
1954	// type. InitOffsetsSection stores offsets, so if the initializer's address is
1955	// not known at link time, stub-indirection has to be used.
1956	void InitOffsetsSection::setUp() {
1957	for (const ConcatInputSection *isec : sections) {
1958	for (const Reloc &rel : isec->relocs) {
1959	RelocAttrs attrs = target->getRelocAttrs(type: rel.type);
1960	if (!attrs.hasAttr(b: RelocAttrBits::UNSIGNED))
1961	error(msg: isec->getLocation(off: rel.offset) +
1962	": unsupported relocation type: " + attrs.name);
1963	if (rel.addend != 0)
1964	error(msg: isec->getLocation(off: rel.offset) +
1965	": relocation addend is not representable in __init_offsets");
1966	if (rel.referent.is<InputSection *>())
1967	error(msg: isec->getLocation(off: rel.offset) +
1968	": unexpected section relocation");
1969
1970	Symbol *sym = rel.referent.dyn_cast<Symbol *>();
1971	if (auto *undefined = dyn_cast<Undefined>(Val: sym))
1972	treatUndefinedSymbol(*undefined, isec, offset: rel.offset);
1973	if (needsBinding(sym))
1974	in.stubs->addEntry(sym);
1975	}
1976	}
1977	}
1978
1979	ObjCMethListSection::ObjCMethListSection()
1980	: SyntheticSection(segment_names::text, section_names::objcMethList) {
1981	flags = S_ATTR_NO_DEAD_STRIP;
1982	align = relativeOffsetSize;
1983	}
1984
1985	// Go through all input method lists and ensure that we have selrefs for all
1986	// their method names. The selrefs will be needed later by ::writeTo. We need to
1987	// create them early on here to ensure they are processed correctly by the lld
1988	// pipeline.
1989	void ObjCMethListSection::setUp() {
1990	for (const ConcatInputSection *isec : inputs) {
1991	uint32_t structSizeAndFlags = 0, structCount = 0;
1992	readMethodListHeader(buf: isec->data.data(), structSizeAndFlags, structCount);
1993	uint32_t originalStructSize = structSizeAndFlags & structSizeMask;
1994	// Method name is immediately after header
1995	uint32_t methodNameOff = methodListHeaderSize;
1996
1997	// Loop through all methods, and ensure a selref for each of them exists.
1998	while (methodNameOff < isec->data.size()) {
1999	const Reloc *reloc = isec->getRelocAt(off: methodNameOff);
2000	assert(reloc && "Relocation expected at method list name slot");
2001	auto *def = dyn_cast_or_null<Defined>(Val: reloc->referent.get<Symbol *>());
2002	assert(def && "Expected valid Defined at method list name slot");
2003	auto *cisec = cast<CStringInputSection>(Val: def->isec());
2004	assert(cisec && "Expected method name to be in a CStringInputSection");
2005	auto methname = cisec->getStringRefAtOffset(off: def->value);
2006	if (!ObjCSelRefsHelper::getSelRef(methname))
2007	ObjCSelRefsHelper::makeSelRef(methname);
2008
2009	// Jump to method name offset in next struct
2010	methodNameOff += originalStructSize;
2011	}
2012	}
2013	}
2014
2015	// Calculate section size and final offsets for where InputSection's need to be
2016	// written.
2017	void ObjCMethListSection::finalize() {
2018	// sectionSize will be the total size of the __objc_methlist section
2019	sectionSize = 0;
2020	for (ConcatInputSection *isec : inputs) {
2021	// We can also use sectionSize as write offset for isec
2022	assert(sectionSize == alignToPowerOf2(sectionSize, relativeOffsetSize) &&
2023	"expected __objc_methlist to be aligned by default with the "
2024	"required section alignment");
2025	isec->outSecOff = sectionSize;
2026
2027	isec->isFinal = true;
2028	uint32_t relativeListSize =
2029	computeRelativeMethodListSize(absoluteMethodListSize: isec->data.size());
2030	sectionSize += relativeListSize;
2031
2032	// If encoding the method list in relative offset format shrinks the size,
2033	// then we also need to adjust symbol sizes to match the new size. Note that
2034	// on 32bit platforms the size of the method list will remain the same when
2035	// encoded in relative offset format.
2036	if (relativeListSize != isec->data.size()) {
2037	for (Symbol *sym : isec->symbols) {
2038	assert(isa<Defined>(sym) &&
2039	"Unexpected undefined symbol in ObjC method list");
2040	auto *def = cast<Defined>(Val: sym);
2041	// There can be 0-size symbols, check if this is the case and ignore
2042	// them.
2043	if (def->size) {
2044	assert(
2045	def->size == isec->data.size() &&
2046	"Invalid ObjC method list symbol size: expected symbol size to "
2047	"match isec size");
2048	def->size = relativeListSize;
2049	}
2050	}
2051	}
2052	}
2053	}
2054
2055	void ObjCMethListSection::writeTo(uint8_t *bufStart) const {
2056	uint8_t *buf = bufStart;
2057	for (const ConcatInputSection *isec : inputs) {
2058	assert(buf - bufStart == long(isec->outSecOff) &&
2059	"Writing at unexpected offset");
2060	uint32_t writtenSize = writeRelativeMethodList(isec, buf);
2061	buf += writtenSize;
2062	}
2063	assert(buf - bufStart == sectionSize &&
2064	"Written size does not match expected section size");
2065	}
2066
2067	// Check if an InputSection is a method list. To do this we scan the
2068	// InputSection for any symbols who's names match the patterns we expect clang
2069	// to generate for method lists.
2070	bool ObjCMethListSection::isMethodList(const ConcatInputSection *isec) {
2071	const char *symPrefixes[] = {objc::symbol_names::classMethods,
2072	objc::symbol_names::instanceMethods,
2073	objc::symbol_names::categoryInstanceMethods,
2074	objc::symbol_names::categoryClassMethods};
2075	if (!isec)
2076	return false;
2077	for (const Symbol *sym : isec->symbols) {
2078	auto *def = dyn_cast_or_null<Defined>(Val: sym);
2079	if (!def)
2080	continue;
2081	for (const char *prefix : symPrefixes) {
2082	if (def->getName().starts_with(Prefix: prefix)) {
2083	assert(def->size == isec->data.size() &&
2084	"Invalid ObjC method list symbol size: expected symbol size to "
2085	"match isec size");
2086	assert(def->value == 0 &&
2087	"Offset of ObjC method list symbol must be 0");
2088	return true;
2089	}
2090	}
2091	}
2092
2093	return false;
2094	}
2095
2096	// Encode a single relative offset value. The input is the data/symbol at
2097	// (&isec->data[inSecOff]). The output is written to (&buf[outSecOff]).
2098	// 'createSelRef' indicates that we should not directly use the specified
2099	// symbol, but instead get the selRef for the symbol and use that instead.
2100	void ObjCMethListSection::writeRelativeOffsetForIsec(
2101	const ConcatInputSection *isec, uint8_t *buf, uint32_t &inSecOff,
2102	uint32_t &outSecOff, bool useSelRef) const {
2103	const Reloc *reloc = isec->getRelocAt(off: inSecOff);
2104	assert(reloc && "Relocation expected at __objc_methlist Offset");
2105	auto *def = dyn_cast_or_null<Defined>(Val: reloc->referent.get<Symbol *>());
2106	assert(def && "Expected all syms in __objc_methlist to be defined");
2107	uint32_t symVA = def->getVA();
2108
2109	if (useSelRef) {
2110	auto *cisec = cast<CStringInputSection>(Val: def->isec());
2111	auto methname = cisec->getStringRefAtOffset(off: def->value);
2112	ConcatInputSection *selRef = ObjCSelRefsHelper::getSelRef(methname);
2113	assert(selRef && "Expected all selector names to already be already be "
2114	"present in __objc_selrefs");
2115	symVA = selRef->getVA();
2116	assert(selRef->data.size() == sizeof(target->wordSize) &&
2117	"Expected one selref per ConcatInputSection");
2118	}
2119
2120	uint32_t currentVA = isec->getVA() + outSecOff;
2121	uint32_t delta = symVA - currentVA;
2122	write32le(P: buf + outSecOff, V: delta);
2123
2124	// Move one pointer forward in the absolute method list
2125	inSecOff += target->wordSize;
2126	// Move one relative offset forward in the relative method list (32 bits)
2127	outSecOff += relativeOffsetSize;
2128	}
2129
2130	// Write a relative method list to buf, return the size of the written
2131	// information
2132	uint32_t
2133	ObjCMethListSection::writeRelativeMethodList(const ConcatInputSection *isec,
2134	uint8_t *buf) const {
2135	// Copy over the header, and add the "this is a relative method list" magic
2136	// value flag
2137	uint32_t structSizeAndFlags = 0, structCount = 0;
2138	readMethodListHeader(buf: isec->data.data(), structSizeAndFlags, structCount);
2139	// Set the struct size for the relative method list
2140	uint32_t relativeStructSizeAndFlags =
2141	(relativeOffsetSize * pointersPerStruct) & structSizeMask;
2142	// Carry over the old flags from the input struct
2143	relativeStructSizeAndFlags |= structSizeAndFlags & structFlagsMask;
2144	// Set the relative method list flag
2145	relativeStructSizeAndFlags |= relMethodHeaderFlag;
2146
2147	writeMethodListHeader(buf, structSizeAndFlags: relativeStructSizeAndFlags, structCount);
2148
2149	assert(methodListHeaderSize +
2150	(structCount * pointersPerStruct * target->wordSize) ==
2151	isec->data.size() &&
2152	"Invalid computed ObjC method list size");
2153
2154	uint32_t inSecOff = methodListHeaderSize;
2155	uint32_t outSecOff = methodListHeaderSize;
2156
2157	// Go through the method list and encode input absolute pointers as relative
2158	// offsets. writeRelativeOffsetForIsec will be incrementing inSecOff and
2159	// outSecOff
2160	for (uint32_t i = 0; i < structCount; i++) {
2161	// Write the name of the method
2162	writeRelativeOffsetForIsec(isec, buf, inSecOff, outSecOff, useSelRef: true);
2163	// Write the type of the method
2164	writeRelativeOffsetForIsec(isec, buf, inSecOff, outSecOff, useSelRef: false);
2165	// Write reference to the selector of the method
2166	writeRelativeOffsetForIsec(isec, buf, inSecOff, outSecOff, useSelRef: false);
2167	}
2168
2169	// Expecting to have read all the data in the isec
2170	assert(inSecOff == isec->data.size() &&
2171	"Invalid actual ObjC method list size");
2172	assert(
2173	outSecOff == computeRelativeMethodListSize(inSecOff) &&
2174	"Mismatch between input & output size when writing relative method list");
2175	return outSecOff;
2176	}
2177
2178	// Given the size of an ObjC method list InputSection, return the size of the
2179	// method list when encoded in relative offsets format. We can do this without
2180	// decoding the actual data, as it can be directly inferred from the size of the
2181	// isec.
2182	uint32_t ObjCMethListSection::computeRelativeMethodListSize(
2183	uint32_t absoluteMethodListSize) const {
2184	uint32_t oldPointersSize = absoluteMethodListSize - methodListHeaderSize;
2185	uint32_t pointerCount = oldPointersSize / target->wordSize;
2186	assert(((pointerCount % pointersPerStruct) == 0) &&
2187	"__objc_methlist expects method lists to have multiple-of-3 pointers");
2188
2189	uint32_t newPointersSize = pointerCount * relativeOffsetSize;
2190	uint32_t newTotalSize = methodListHeaderSize + newPointersSize;
2191
2192	assert((newTotalSize <= absoluteMethodListSize) &&
2193	"Expected relative method list size to be smaller or equal than "
2194	"original size");
2195	return newTotalSize;
2196	}
2197
2198	// Read a method list header from buf
2199	void ObjCMethListSection::readMethodListHeader(const uint8_t *buf,
2200	uint32_t &structSizeAndFlags,
2201	uint32_t &structCount) const {
2202	structSizeAndFlags = read32le(P: buf);
2203	structCount = read32le(P: buf + sizeof(uint32_t));
2204	}
2205
2206	// Write a method list header to buf
2207	void ObjCMethListSection::writeMethodListHeader(uint8_t *buf,
2208	uint32_t structSizeAndFlags,
2209	uint32_t structCount) const {
2210	write32le(P: buf, V: structSizeAndFlags);
2211	write32le(P: buf + sizeof(structSizeAndFlags), V: structCount);
2212	}
2213
2214	void macho::createSyntheticSymbols() {
2215	auto addHeaderSymbol = [](const char *name) {
2216	symtab->addSynthetic(name, in.header->isec, /*value=*/0,
2217	/*isPrivateExtern=*/true, /*includeInSymtab=*/false,
2218	/*referencedDynamically=*/false);
2219	};
2220
2221	switch (config->outputType) {
2222	// FIXME: Assign the right address value for these symbols
2223	// (rather than 0). But we need to do that after assignAddresses().
2224	case MH_EXECUTE:
2225	// If linking PIE, __mh_execute_header is a defined symbol in
2226	// __TEXT, __text)
2227	// Otherwise, it's an absolute symbol.
2228	if (config->isPic)
2229	symtab->addSynthetic(name: "__mh_execute_header", in.header->isec, /*value=*/0,
2230	/*isPrivateExtern=*/false, /*includeInSymtab=*/true,
2231	/*referencedDynamically=*/true);
2232	else
2233	symtab->addSynthetic(name: "__mh_execute_header", /*isec=*/nullptr, /*value=*/0,
2234	/*isPrivateExtern=*/false, /*includeInSymtab=*/true,
2235	/*referencedDynamically=*/true);
2236	break;
2237
2238	// The following symbols are N_SECT symbols, even though the header is not
2239	// part of any section and that they are private to the bundle/dylib/object
2240	// they are part of.
2241	case MH_BUNDLE:
2242	addHeaderSymbol("__mh_bundle_header");
2243	break;
2244	case MH_DYLIB:
2245	addHeaderSymbol("__mh_dylib_header");
2246	break;
2247	case MH_DYLINKER:
2248	addHeaderSymbol("__mh_dylinker_header");
2249	break;
2250	case MH_OBJECT:
2251	addHeaderSymbol("__mh_object_header");
2252	break;
2253	default:
2254	llvm_unreachable("unexpected outputType");
2255	break;
2256	}
2257
2258	// The Itanium C++ ABI requires dylibs to pass a pointer to __cxa_atexit
2259	// which does e.g. cleanup of static global variables. The ABI document
2260	// says that the pointer can point to any address in one of the dylib's
2261	// segments, but in practice ld64 seems to set it to point to the header,
2262	// so that's what's implemented here.
2263	addHeaderSymbol("___dso_handle");
2264	}
2265
2266	ChainedFixupsSection::ChainedFixupsSection()
2267	: LinkEditSection(segment_names::linkEdit, section_names::chainFixups) {}
2268
2269	bool ChainedFixupsSection::isNeeded() const {
2270	assert(config->emitChainedFixups);
2271	// dyld always expects LC_DYLD_CHAINED_FIXUPS to point to a valid
2272	// dyld_chained_fixups_header, so we create this section even if there aren't
2273	// any fixups.
2274	return true;
2275	}
2276
2277	static bool needsWeakBind(const Symbol &sym) {
2278	if (auto *dysym = dyn_cast<DylibSymbol>(Val: &sym))
2279	return dysym->isWeakDef();
2280	if (auto *defined = dyn_cast<Defined>(Val: &sym))
2281	return defined->isExternalWeakDef();
2282	return false;
2283	}
2284
2285	void ChainedFixupsSection::addBinding(const Symbol *sym,
2286	const InputSection *isec, uint64_t offset,
2287	int64_t addend) {
2288	locations.emplace_back(args&: isec, args&: offset);
2289	int64_t outlineAddend = (addend < 0 || addend > 0xFF) ? addend : 0;
2290	auto [it, inserted] = bindings.insert(
2291	KV: {{sym, outlineAddend}, static_cast<uint32_t>(bindings.size())});
2292
2293	if (inserted) {
2294	symtabSize += sym->getName().size() + 1;
2295	hasWeakBind = hasWeakBind || needsWeakBind(sym: *sym);
2296	if (!isInt<23>(x: outlineAddend))
2297	needsLargeAddend = true;
2298	else if (outlineAddend != 0)
2299	needsAddend = true;
2300	}
2301	}
2302
2303	std::pair<uint32_t, uint8_t>
2304	ChainedFixupsSection::getBinding(const Symbol *sym, int64_t addend) const {
2305	int64_t outlineAddend = (addend < 0 || addend > 0xFF) ? addend : 0;
2306	auto it = bindings.find(Key: {sym, outlineAddend});
2307	assert(it != bindings.end() && "binding not found in the imports table");
2308	if (outlineAddend == 0)
2309	return {it->second, addend};
2310	return {it->second, 0};
2311	}
2312
2313	static size_t writeImport(uint8_t *buf, int format, uint32_t libOrdinal,
2314	bool weakRef, uint32_t nameOffset, int64_t addend) {
2315	switch (format) {
2316	case DYLD_CHAINED_IMPORT: {
2317	auto *import = reinterpret_cast<dyld_chained_import *>(buf);
2318	import->lib_ordinal = libOrdinal;
2319	import->weak_import = weakRef;
2320	import->name_offset = nameOffset;
2321	return sizeof(dyld_chained_import);
2322	}
2323	case DYLD_CHAINED_IMPORT_ADDEND: {
2324	auto *import = reinterpret_cast<dyld_chained_import_addend *>(buf);
2325	import->lib_ordinal = libOrdinal;
2326	import->weak_import = weakRef;
2327	import->name_offset = nameOffset;
2328	import->addend = addend;
2329	return sizeof(dyld_chained_import_addend);
2330	}
2331	case DYLD_CHAINED_IMPORT_ADDEND64: {
2332	auto *import = reinterpret_cast<dyld_chained_import_addend64 *>(buf);
2333	import->lib_ordinal = libOrdinal;
2334	import->weak_import = weakRef;
2335	import->name_offset = nameOffset;
2336	import->addend = addend;
2337	return sizeof(dyld_chained_import_addend64);
2338	}
2339	default:
2340	llvm_unreachable("Unknown import format");
2341	}
2342	}
2343
2344	size_t ChainedFixupsSection::SegmentInfo::getSize() const {
2345	assert(pageStarts.size() > 0 && "SegmentInfo for segment with no fixups?");
2346	return alignTo<8>(Value: sizeof(dyld_chained_starts_in_segment) +
2347	pageStarts.back().first * sizeof(uint16_t));
2348	}
2349
2350	size_t ChainedFixupsSection::SegmentInfo::writeTo(uint8_t *buf) const {
2351	auto *segInfo = reinterpret_cast<dyld_chained_starts_in_segment *>(buf);
2352	segInfo->size = getSize();
2353	segInfo->page_size = target->getPageSize();
2354	// FIXME: Use DYLD_CHAINED_PTR_64_OFFSET on newer OS versions.
2355	segInfo->pointer_format = DYLD_CHAINED_PTR_64;
2356	segInfo->segment_offset = oseg->addr - in.header->addr;
2357	segInfo->max_valid_pointer = 0; // not used on 64-bit
2358	segInfo->page_count = pageStarts.back().first + 1;
2359
2360	uint16_t *starts = segInfo->page_start;
2361	for (size_t i = 0; i < segInfo->page_count; ++i)
2362	starts[i] = DYLD_CHAINED_PTR_START_NONE;
2363
2364	for (auto [pageIdx, startAddr] : pageStarts)
2365	starts[pageIdx] = startAddr;
2366	return segInfo->size;
2367	}
2368
2369	static size_t importEntrySize(int format) {
2370	switch (format) {
2371	case DYLD_CHAINED_IMPORT:
2372	return sizeof(dyld_chained_import);
2373	case DYLD_CHAINED_IMPORT_ADDEND:
2374	return sizeof(dyld_chained_import_addend);
2375	case DYLD_CHAINED_IMPORT_ADDEND64:
2376	return sizeof(dyld_chained_import_addend64);
2377	default:
2378	llvm_unreachable("Unknown import format");
2379	}
2380	}
2381
2382	// This is step 3 of the algorithm described in the class comment of
2383	// ChainedFixupsSection.
2384	//
2385	// LC_DYLD_CHAINED_FIXUPS data consists of (in this order):
2386	// * A dyld_chained_fixups_header
2387	// * A dyld_chained_starts_in_image
2388	// * One dyld_chained_starts_in_segment per segment
2389	// * List of all imports (dyld_chained_import, dyld_chained_import_addend, or
2390	// dyld_chained_import_addend64)
2391	// * Names of imported symbols
2392	void ChainedFixupsSection::writeTo(uint8_t *buf) const {
2393	auto *header = reinterpret_cast<dyld_chained_fixups_header *>(buf);
2394	header->fixups_version = 0;
2395	header->imports_count = bindings.size();
2396	header->imports_format = importFormat;
2397	header->symbols_format = 0;
2398
2399	buf += alignTo<8>(Value: sizeof(*header));
2400
2401	auto curOffset = [&buf, &header]() -> uint32_t {
2402	return buf - reinterpret_cast<uint8_t *>(header);
2403	};
2404
2405	header->starts_offset = curOffset();
2406
2407	auto *imageInfo = reinterpret_cast<dyld_chained_starts_in_image *>(buf);
2408	imageInfo->seg_count = outputSegments.size();
2409	uint32_t *segStarts = imageInfo->seg_info_offset;
2410
2411	// dyld_chained_starts_in_image ends in a flexible array member containing an
2412	// uint32_t for each segment. Leave room for it, and fill it via segStarts.
2413	buf += alignTo<8>(offsetof(dyld_chained_starts_in_image, seg_info_offset) +
2414	outputSegments.size() * sizeof(uint32_t));
2415
2416	// Initialize all offsets to 0, which indicates that the segment does not have
2417	// fixups. Those that do have them will be filled in below.
2418	for (size_t i = 0; i < outputSegments.size(); ++i)
2419	segStarts[i] = 0;
2420
2421	for (const SegmentInfo &seg : fixupSegments) {
2422	segStarts[seg.oseg->index] = curOffset() - header->starts_offset;
2423	buf += seg.writeTo(buf);
2424	}
2425
2426	// Write imports table.
2427	header->imports_offset = curOffset();
2428	uint64_t nameOffset = 0;
2429	for (auto [import, idx] : bindings) {
2430	const Symbol &sym = *import.first;
2431	int16_t libOrdinal = needsWeakBind(sym)
2432	? (int64_t)BIND_SPECIAL_DYLIB_WEAK_LOOKUP
2433	: ordinalForSymbol(sym);
2434	buf += writeImport(buf, format: importFormat, libOrdinal, weakRef: sym.isWeakRef(),
2435	nameOffset, addend: import.second);
2436	nameOffset += sym.getName().size() + 1;
2437	}
2438
2439	// Write imported symbol names.
2440	header->symbols_offset = curOffset();
2441	for (auto [import, idx] : bindings) {
2442	StringRef name = import.first->getName();
2443	memcpy(dest: buf, src: name.data(), n: name.size());
2444	buf += name.size() + 1; // account for null terminator
2445	}
2446
2447	assert(curOffset() == getRawSize());
2448	}
2449
2450	// This is step 2 of the algorithm described in the class comment of
2451	// ChainedFixupsSection.
2452	void ChainedFixupsSection::finalizeContents() {
2453	assert(target->wordSize == 8 && "Only 64-bit platforms are supported");
2454	assert(config->emitChainedFixups);
2455
2456	if (!isUInt<32>(x: symtabSize))
2457	error(msg: "cannot encode chained fixups: imported symbols table size " +
2458	Twine(symtabSize) + " exceeds 4 GiB");
2459
2460	if (needsLargeAddend || !isUInt<23>(x: symtabSize))
2461	importFormat = DYLD_CHAINED_IMPORT_ADDEND64;
2462	else if (needsAddend)
2463	importFormat = DYLD_CHAINED_IMPORT_ADDEND;
2464	else
2465	importFormat = DYLD_CHAINED_IMPORT;
2466
2467	for (Location &loc : locations)
2468	loc.offset =
2469	loc.isec->parent->getSegmentOffset() + loc.isec->getOffset(off: loc.offset);
2470
2471	llvm::sort(C&: locations, Comp: [](const Location &a, const Location &b) {
2472	const OutputSegment *segA = a.isec->parent->parent;
2473	const OutputSegment *segB = b.isec->parent->parent;
2474	if (segA == segB)
2475	return a.offset < b.offset;
2476	return segA->addr < segB->addr;
2477	});
2478
2479	auto sameSegment = [](const Location &a, const Location &b) {
2480	return a.isec->parent->parent == b.isec->parent->parent;
2481	};
2482
2483	const uint64_t pageSize = target->getPageSize();
2484	for (size_t i = 0, count = locations.size(); i < count;) {
2485	const Location &firstLoc = locations[i];
2486	fixupSegments.emplace_back(Args&: firstLoc.isec->parent->parent);
2487	while (i < count && sameSegment(locations[i], firstLoc)) {
2488	uint32_t pageIdx = locations[i].offset / pageSize;
2489	fixupSegments.back().pageStarts.emplace_back(
2490	Args&: pageIdx, Args: locations[i].offset % pageSize);
2491	++i;
2492	while (i < count && sameSegment(locations[i], firstLoc) &&
2493	locations[i].offset / pageSize == pageIdx)
2494	++i;
2495	}
2496	}
2497
2498	// Compute expected encoded size.
2499	size = alignTo<8>(Value: sizeof(dyld_chained_fixups_header));
2500	size += alignTo<8>(offsetof(dyld_chained_starts_in_image, seg_info_offset) +
2501	outputSegments.size() * sizeof(uint32_t));
2502	for (const SegmentInfo &seg : fixupSegments)
2503	size += seg.getSize();
2504	size += importEntrySize(format: importFormat) * bindings.size();
2505	size += symtabSize;
2506	}
2507
2508	template SymtabSection *macho::makeSymtabSection<LP64>(StringTableSection &);
2509	template SymtabSection *macho::makeSymtabSection<ILP32>(StringTableSection &);
2510