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