SyntheticSections.cpp

//===- SyntheticSections.cpp ---------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include"SyntheticSections.h"
#include"ConcatOutputSection.h"
#include"Config.h"
#include"ExportTrie.h"
#include"ICF.h"
#include"InputFiles.h"
#include"MachOStructs.h"
#include"ObjC.h"
#include"OutputSegment.h"
#include"SymbolTable.h"
#include"Symbols.h"

#include"lld/Common/CommonLinkerContext.h"
#include"llvm/ADT/STLExtras.h"
#include"llvm/Config/llvm-config.h"
#include"llvm/Support/EndianStream.h"
#include"llvm/Support/FileSystem.h"
#include"llvm/Support/LEB128.h"
#include"llvm/Support/Parallel.h"
#include"llvm/Support/Path.h"
#include"llvm/Support/xxhash.h"

#if defined(__APPLE__)
#include<sys/mman.h>

#defineCOMMON_DIGEST_FOR_OPENSSL
#include<CommonCrypto/CommonDigest.h>
#else
#include"llvm/Support/SHA256.h"
#endif

usingnamespacellvm;
usingnamespacellvm::MachO;
usingnamespacellvm::support;
usingnamespacellvm::support::endian;
usingnamespacelld;
usingnamespacelld::macho;

// Reads `len` bytes at data and writes the 32-byte SHA256 checksum to `output`.
staticvoidsha256(constuint8_t *data, size_t len, uint8_t *output) {
#if defined(__APPLE__)
// FIXME: Make LLVM's SHA256 faster and use it unconditionally. See PR56121
// for some notes on this.
CC_SHA256(data, len, output);
#else
 ArrayRef<uint8_t> block(data, len);
 std::array<uint8_t, 32> hash = SHA256::hash(block);
static_assert(hash.size() == CodeSignatureSection::hashSize);
memcpy(output, hash.data(), hash.size());
#endif
}

InStruct macho::in;
std::vector<SyntheticSection *> macho::syntheticSections;

SyntheticSection::SyntheticSection(constchar *segname, constchar *name)
 : OutputSection(SyntheticKind, name) {
std::tie(this->segname, this->name) = maybeRenameSection({segname, name});
 isec = makeSyntheticInputSection(segname, name);
 isec->parent = this;
 syntheticSections.push_back(this);
}

// dyld3's MachOLoaded::getSlide() assumes that the __TEXT segment starts
// from the beginning of the file (i.e. the header).
MachHeaderSection::MachHeaderSection()
 : SyntheticSection(segment_names::text, section_names::header) {
// XXX: This is a hack. (See D97007)
// Setting the index to 1 to pretend that this section is the text
// section.
index = 1;
 isec->isFinal = true;
}

voidMachHeaderSection::addLoadCommand(LoadCommand *lc) {
 loadCommands.push_back(lc);
 sizeOfCmds += lc->getSize();
}

uint64_tMachHeaderSection::getSize() const {
uint64_t size = target->headerSize + sizeOfCmds + config->headerPad;
// If we are emitting an encryptable binary, our load commands must have a
// separate (non-encrypted) page to themselves.
if (config->emitEncryptionInfo)
 size = alignToPowerOf2(size, target->getPageSize());
return size;
}

staticuint32_tcpuSubtype() {
uint32_t subtype = target->cpuSubtype;

if (config->outputType == MH_EXECUTE && !config->staticLink &&
 target->cpuSubtype == CPU_SUBTYPE_X86_64_ALL &&
 config->platform() == PLATFORM_MACOS &&
 config->platformInfo.target.MinDeployment >= VersionTuple(10, 5))
 subtype |= CPU_SUBTYPE_LIB64;

return subtype;
}

staticboolhasWeakBinding() {
return config->emitChainedFixups ? in.chainedFixups->hasWeakBinding()
 : in.weakBinding->hasEntry();
}

staticboolhasNonWeakDefinition() {
return config->emitChainedFixups ? in.chainedFixups->hasNonWeakDefinition()
 : in.weakBinding->hasNonWeakDefinition();
}

voidMachHeaderSection::writeTo(uint8_t *buf) const {
auto *hdr = reinterpret_cast<mach_header *>(buf);
 hdr->magic = target->magic;
 hdr->cputype = target->cpuType;
 hdr->cpusubtype = cpuSubtype();
 hdr->filetype = config->outputType;
 hdr->ncmds = loadCommands.size();
 hdr->sizeofcmds = sizeOfCmds;
 hdr->flags = MH_DYLDLINK;

if (config->namespaceKind == NamespaceKind::twolevel)
 hdr->flags |= MH_NOUNDEFS | MH_TWOLEVEL;

if (config->outputType == MH_DYLIB && !config->hasReexports)
 hdr->flags |= MH_NO_REEXPORTED_DYLIBS;

if (config->markDeadStrippableDylib)
 hdr->flags |= MH_DEAD_STRIPPABLE_DYLIB;

if (config->outputType == MH_EXECUTE && config->isPic)
 hdr->flags |= MH_PIE;

if (config->outputType == MH_DYLIB && config->applicationExtension)
 hdr->flags |= MH_APP_EXTENSION_SAFE;

if (in.exports->hasWeakSymbol || hasNonWeakDefinition())
 hdr->flags |= MH_WEAK_DEFINES;

if (in.exports->hasWeakSymbol || hasWeakBinding())
 hdr->flags |= MH_BINDS_TO_WEAK;

for (const OutputSegment *seg : outputSegments) {
for (const OutputSection *osec : seg->getSections()) {
if (isThreadLocalVariables(osec->flags)) {
 hdr->flags |= MH_HAS_TLV_DESCRIPTORS;
break;
 }
 }
 }

uint8_t *p = reinterpret_cast<uint8_t *>(hdr) + target->headerSize;
for (const LoadCommand *lc : loadCommands) {
 lc->writeTo(p);
 p += lc->getSize();
 }
}

PageZeroSection::PageZeroSection()
 : SyntheticSection(segment_names::pageZero, section_names::pageZero) {}

RebaseSection::RebaseSection()
 : LinkEditSection(segment_names::linkEdit, section_names::rebase) {}

namespace {
structRebaseState {
uint64_t sequenceLength;
uint64_t skipLength;
};
} // namespace

staticvoidemitIncrement(uint64_t incr, raw_svector_ostream &os) {
assert(incr != 0);

if ((incr >> target->p2WordSize) <= REBASE_IMMEDIATE_MASK &&
 (incr % target->wordSize) == 0) {
 os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_IMM_SCALED |
 (incr >> target->p2WordSize));
 } else {
 os << static_cast<uint8_t>(REBASE_OPCODE_ADD_ADDR_ULEB);
encodeULEB128(incr, os);
 }
}

staticvoidflushRebase(const RebaseState &state, raw_svector_ostream &os) {
assert(state.sequenceLength > 0);

if (state.skipLength == target->wordSize) {
if (state.sequenceLength <= REBASE_IMMEDIATE_MASK) {
 os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_IMM_TIMES |
 state.sequenceLength);
 } else {
 os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_ULEB_TIMES);
encodeULEB128(state.sequenceLength, os);
 }
 } elseif (state.sequenceLength == 1) {
 os << static_cast<uint8_t>(REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB);
encodeULEB128(state.skipLength - target->wordSize, os);
 } else {
 os << static_cast<uint8_t>(
 REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB);
encodeULEB128(state.sequenceLength, os);
encodeULEB128(state.skipLength - target->wordSize, os);
 }
}

// Rebases are communicated to dyld using a bytecode, whose opcodes cause the
// memory location at a specific address to be rebased and/or the address to be
// incremented.
//
// Opcode REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB is the most generic
// one, encoding a series of evenly spaced addresses. This algorithm works by
// splitting up the sorted list of addresses into such chunks. If the locations
// are consecutive or the sequence consists of a single location, flushRebase
// will use a smaller, more specialized encoding.
staticvoidencodeRebases(const OutputSegment *seg,
 MutableArrayRef<Location> locations,
 raw_svector_ostream &os) {
// dyld operates on segments. Translate section offsets into segment offsets.
for (Location &loc : locations)
 loc.offset =
 loc.isec->parent->getSegmentOffset() + loc.isec->getOffset(loc.offset);
// The algorithm assumes that locations are unique.
 Location *end =
llvm::unique(locations, [](const Location &a, const Location &b) {
return a.offset == b.offset;
 });
size_t count = end - locations.begin();

 os << static_cast<uint8_t>(REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
 seg->index);
assert(!locations.empty());
uint64_t offset = locations[0].offset;
encodeULEB128(offset, os);

 RebaseState state{1, target->wordSize};

for (size_t i = 1; i < count; ++i) {
 offset = locations[i].offset;

uint64_t skip = offset - locations[i - 1].offset;
assert(skip != 0 && "duplicate locations should have been weeded out");

if (skip == state.skipLength) {
 ++state.sequenceLength;
 } elseif (state.sequenceLength == 1) {
 ++state.sequenceLength;
 state.skipLength = skip;
 } elseif (skip < state.skipLength) {
// The address is lower than what the rebase pointer would be if the last
// location would be part of a sequence. We start a new sequence from the
// previous location.
 --state.sequenceLength;
flushRebase(state, os);

 state.sequenceLength = 2;
 state.skipLength = skip;
 } else {
// The address is at some positive offset from the rebase pointer. We
// start a new sequence which begins with the current location.
flushRebase(state, os);
emitIncrement(skip - state.skipLength, os);
 state.sequenceLength = 1;
 state.skipLength = target->wordSize;
 }
 }
flushRebase(state, os);
}

voidRebaseSection::finalizeContents() {
if (locations.empty())
return;

 raw_svector_ostream os{contents};
 os << static_cast<uint8_t>(REBASE_OPCODE_SET_TYPE_IMM | REBASE_TYPE_POINTER);

llvm::sort(locations, [](const Location &a, const Location &b) {
return a.isec->getVA(a.offset) < b.isec->getVA(b.offset);
 });

for (size_t i = 0, count = locations.size(); i < count;) {
const OutputSegment *seg = locations[i].isec->parent->parent;
size_t j = i + 1;
while (j < count && locations[j].isec->parent->parent == seg)
 ++j;
encodeRebases(seg, {locations.data() + i, locations.data() + j}, os);
 i = j;
 }
 os << static_cast<uint8_t>(REBASE_OPCODE_DONE);
}

voidRebaseSection::writeTo(uint8_t *buf) const {
memcpy(buf, contents.data(), contents.size());
}

NonLazyPointerSectionBase::NonLazyPointerSectionBase(constchar *segname,
constchar *name)
 : SyntheticSection(segname, name) {
 align = target->wordSize;
}

voidmacho::addNonLazyBindingEntries(const Symbol *sym,
const InputSection *isec, uint64_t offset,
int64_t addend) {
if (config->emitChainedFixups) {
if (needsBinding(sym))
 in.chainedFixups->addBinding(sym, isec, offset, addend);
elseif (isa<Defined>(sym))
 in.chainedFixups->addRebase(isec, offset);
else
llvm_unreachable("cannot bind to an undefined symbol");
return;
 }

if (constauto *dysym = dyn_cast<DylibSymbol>(sym)) {
 in.binding->addEntry(dysym, isec, offset, addend);
if (dysym->isWeakDef())
 in.weakBinding->addEntry(sym, isec, offset, addend);
 } elseif (constauto *defined = dyn_cast<Defined>(sym)) {
 in.rebase->addEntry(isec, offset);
if (defined->isExternalWeakDef())
 in.weakBinding->addEntry(sym, isec, offset, addend);
elseif (defined->interposable)
 in.binding->addEntry(sym, isec, offset, addend);
 } else {
// Undefined symbols are filtered out in scanRelocations(); we should never
// get here
llvm_unreachable("cannot bind to an undefined symbol");
 }
}

voidNonLazyPointerSectionBase::addEntry(Symbol *sym) {
if (entries.insert(sym)) {
assert(!sym->isInGot());
 sym->gotIndex = entries.size() - 1;

addNonLazyBindingEntries(sym, isec, sym->gotIndex * target->wordSize);
 }
}

voidmacho::writeChainedRebase(uint8_t *buf, uint64_t targetVA) {
assert(config->emitChainedFixups);
assert(target->wordSize == 8 && "Only 64-bit platforms are supported");
auto *rebase = reinterpret_cast<dyld_chained_ptr_64_rebase *>(buf);
 rebase->target = targetVA & 0xf'ffff'ffff;
 rebase->high8 = (targetVA >> 56);
 rebase->reserved = 0;
 rebase->next = 0;
 rebase->bind = 0;

// The fixup format places a 64 GiB limit on the output's size.
// Should we handle this gracefully?
uint64_t encodedVA = rebase->target | ((uint64_t)rebase->high8 << 56);
if (encodedVA != targetVA)
error("rebase target address 0x" + Twine::utohexstr(targetVA) +
" does not fit into chained fixup. Re-link with -no_fixup_chains");
}

staticvoidwriteChainedBind(uint8_t *buf, const Symbol *sym, int64_t addend) {
assert(config->emitChainedFixups);
assert(target->wordSize == 8 && "Only 64-bit platforms are supported");
auto *bind = reinterpret_cast<dyld_chained_ptr_64_bind *>(buf);
auto [ordinal, inlineAddend] = in.chainedFixups->getBinding(sym, addend);
 bind->ordinal = ordinal;
 bind->addend = inlineAddend;
 bind->reserved = 0;
 bind->next = 0;
 bind->bind = 1;
}

voidmacho::writeChainedFixup(uint8_t *buf, const Symbol *sym, int64_t addend) {
if (needsBinding(sym))
writeChainedBind(buf, sym, addend);
else
writeChainedRebase(buf, sym->getVA() + addend);
}

voidNonLazyPointerSectionBase::writeTo(uint8_t *buf) const {
if (config->emitChainedFixups) {
for (constauto &[i, entry] : llvm::enumerate(entries))
writeChainedFixup(&buf[i * target->wordSize], entry, 0);
 } else {
for (constauto &[i, entry] : llvm::enumerate(entries))
if (auto *defined = dyn_cast<Defined>(entry))
write64le(&buf[i * target->wordSize], defined->getVA());
 }
}

GotSection::GotSection()
 : NonLazyPointerSectionBase(segment_names::data, section_names::got) {
 flags = S_NON_LAZY_SYMBOL_POINTERS;
}

TlvPointerSection::TlvPointerSection()
 : NonLazyPointerSectionBase(segment_names::data,
 section_names::threadPtrs) {
 flags = S_THREAD_LOCAL_VARIABLE_POINTERS;
}

BindingSection::BindingSection()
 : LinkEditSection(segment_names::linkEdit, section_names::binding) {}

namespace {
structBinding {
 OutputSegment *segment = nullptr;
uint64_t offset = 0;
int64_t addend = 0;
};
structBindIR {
// Default value of 0xF0 is not valid opcode and should make the program
// scream instead of accidentally writing "valid" values.
uint8_t opcode = 0xF0;
uint64_t data = 0;
uint64_t consecutiveCount = 0;
};
} // namespace

// Encode a sequence of opcodes that tell dyld to write the address of symbol +
// addend at osec->addr + outSecOff.
//
// The bind opcode "interpreter" remembers the values of each binding field, so
// we only need to encode the differences between bindings. Hence the use of
// lastBinding.
staticvoidencodeBinding(const OutputSection *osec, uint64_t outSecOff,
int64_t addend, Binding &lastBinding,
 std::vector<BindIR> &opcodes) {
 OutputSegment *seg = osec->parent;
uint64_t offset = osec->getSegmentOffset() + outSecOff;
if (lastBinding.segment != seg) {
 opcodes.push_back(
 {static_cast<uint8_t>(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
 seg->index),
 offset});
 lastBinding.segment = seg;
 lastBinding.offset = offset;
 } elseif (lastBinding.offset != offset) {
 opcodes.push_back({BIND_OPCODE_ADD_ADDR_ULEB, offset - lastBinding.offset});
 lastBinding.offset = offset;
 }

if (lastBinding.addend != addend) {
 opcodes.push_back(
 {BIND_OPCODE_SET_ADDEND_SLEB, static_cast<uint64_t>(addend)});
 lastBinding.addend = addend;
 }

 opcodes.push_back({BIND_OPCODE_DO_BIND, 0});
// DO_BIND causes dyld to both perform the binding and increment the offset
 lastBinding.offset += target->wordSize;
}

staticvoidoptimizeOpcodes(std::vector<BindIR> &opcodes) {
// Pass 1: Combine bind/add pairs
size_t i;
int pWrite = 0;
for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
if ((opcodes[i].opcode == BIND_OPCODE_ADD_ADDR_ULEB) &&
 (opcodes[i - 1].opcode == BIND_OPCODE_DO_BIND)) {
 opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB;
 opcodes[pWrite].data = opcodes[i].data;
 ++i;
 } else {
 opcodes[pWrite] = opcodes[i - 1];
 }
 }
if (i == opcodes.size())
 opcodes[pWrite] = opcodes[i - 1];
 opcodes.resize(pWrite + 1);

// Pass 2: Compress two or more bind_add opcodes
 pWrite = 0;
for (i = 1; i < opcodes.size(); ++i, ++pWrite) {
if ((opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
 (opcodes[i - 1].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
 (opcodes[i].data == opcodes[i - 1].data)) {
 opcodes[pWrite].opcode = BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB;
 opcodes[pWrite].consecutiveCount = 2;
 opcodes[pWrite].data = opcodes[i].data;
 ++i;
while (i < opcodes.size() &&
 (opcodes[i].opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
 (opcodes[i].data == opcodes[i - 1].data)) {
 opcodes[pWrite].consecutiveCount++;
 ++i;
 }
 } else {
 opcodes[pWrite] = opcodes[i - 1];
 }
 }
if (i == opcodes.size())
 opcodes[pWrite] = opcodes[i - 1];
 opcodes.resize(pWrite + 1);

// Pass 3: Use immediate encodings
// Every binding is the size of one pointer. If the next binding is a
// multiple of wordSize away that is within BIND_IMMEDIATE_MASK, the
// opcode can be scaled by wordSize into a single byte and dyld will
// expand it to the correct address.
for (auto &p : opcodes) {
// It's unclear why the check needs to be less than BIND_IMMEDIATE_MASK,
// but ld64 currently does this. This could be a potential bug, but
// for now, perform the same behavior to prevent mysterious bugs.
if ((p.opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB) &&
 ((p.data / target->wordSize) < BIND_IMMEDIATE_MASK) &&
 ((p.data % target->wordSize) == 0)) {
 p.opcode = BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED;
 p.data /= target->wordSize;
 }
 }
}

staticvoidflushOpcodes(const BindIR &op, raw_svector_ostream &os) {
uint8_t opcode = op.opcode & BIND_OPCODE_MASK;
switch (opcode) {
case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
case BIND_OPCODE_ADD_ADDR_ULEB:
case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
 os << op.opcode;
encodeULEB128(op.data, os);
break;
case BIND_OPCODE_SET_ADDEND_SLEB:
 os << op.opcode;
encodeSLEB128(static_cast<int64_t>(op.data), os);
break;
case BIND_OPCODE_DO_BIND:
 os << op.opcode;
break;
case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
 os << op.opcode;
encodeULEB128(op.consecutiveCount, os);
encodeULEB128(op.data, os);
break;
case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
 os << static_cast<uint8_t>(op.opcode | op.data);
break;
default:
llvm_unreachable("cannot bind to an unrecognized symbol");
 }
}

staticboolneedsWeakBind(const Symbol &sym) {
if (auto *dysym = dyn_cast<DylibSymbol>(&sym))
return dysym->isWeakDef();
if (auto *defined = dyn_cast<Defined>(&sym))
return defined->isExternalWeakDef();
returnfalse;
}

// Non-weak bindings need to have their dylib ordinal encoded as well.
staticint16_tordinalForDylibSymbol(const DylibSymbol &dysym) {
if (config->namespaceKind == NamespaceKind::flat || dysym.isDynamicLookup())
returnstatic_cast<int16_t>(BIND_SPECIAL_DYLIB_FLAT_LOOKUP);
assert(dysym.getFile()->isReferenced());
return dysym.getFile()->ordinal;
}

staticint16_tordinalForSymbol(const Symbol &sym) {
if (config->emitChainedFixups && needsWeakBind(sym))
return BIND_SPECIAL_DYLIB_WEAK_LOOKUP;
if (constauto *dysym = dyn_cast<DylibSymbol>(&sym))
returnordinalForDylibSymbol(*dysym);
assert(cast<Defined>(&sym)->interposable);
return BIND_SPECIAL_DYLIB_FLAT_LOOKUP;
}

staticvoidencodeDylibOrdinal(int16_t ordinal, raw_svector_ostream &os) {
if (ordinal <= 0) {
 os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_SPECIAL_IMM |
 (ordinal & BIND_IMMEDIATE_MASK));
 } elseif (ordinal <= BIND_IMMEDIATE_MASK) {
 os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | ordinal);
 } else {
 os << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB);
encodeULEB128(ordinal, os);
 }
}

staticvoidencodeWeakOverride(const Defined *defined,
 raw_svector_ostream &os) {
 os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM |
 BIND_SYMBOL_FLAGS_NON_WEAK_DEFINITION)
 << defined->getName() << '\0';
}

// Organize the bindings so we can encoded them with fewer opcodes.
//
// First, all bindings for a given symbol should be grouped together.
// BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM is the largest opcode (since it
// has an associated symbol string), so we only want to emit it once per symbol.
//
// Within each group, we sort the bindings by address. Since bindings are
// delta-encoded, sorting them allows for a more compact result. Note that
// sorting by address alone ensures that bindings for the same segment / section
// are located together, minimizing the number of times we have to emit
// BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB.
//
// Finally, we sort the symbols by the address of their first binding, again
// to facilitate the delta-encoding process.
template <classSym>
std::vector<std::pair<const Sym *, std::vector<BindingEntry>>>
sortBindings(const BindingsMap<const Sym *> &bindingsMap) {
 std::vector<std::pair<const Sym *, std::vector<BindingEntry>>> bindingsVec(
 bindingsMap.begin(), bindingsMap.end());
for (auto &p : bindingsVec) {
 std::vector<BindingEntry> &bindings = p.second;
llvm::sort(bindings, [](const BindingEntry &a, const BindingEntry &b) {
return a.target.getVA() < b.target.getVA();
 });
 }
llvm::sort(bindingsVec, [](constauto &a, constauto &b) {
return a.second[0].target.getVA() < b.second[0].target.getVA();
 });
return bindingsVec;
}

// Emit bind opcodes, which are a stream of byte-sized opcodes that dyld
// interprets to update a record with the following fields:
// * segment index (of the segment to write the symbol addresses to, typically
// the __DATA_CONST segment which contains the GOT)
// * offset within the segment, indicating the next location to write a binding
// * symbol type
// * symbol library ordinal (the index of its library's LC_LOAD_DYLIB command)
// * symbol name
// * addend
// When dyld sees BIND_OPCODE_DO_BIND, it uses the current record state to bind
// a symbol in the GOT, and increments the segment offset to point to the next
// entry. It does *not* clear the record state after doing the bind, so
// subsequent opcodes only need to encode the differences between bindings.
voidBindingSection::finalizeContents() {
 raw_svector_ostream os{contents};
 Binding lastBinding;
int16_t lastOrdinal = 0;

for (auto &p : sortBindings(bindingsMap)) {
const Symbol *sym = p.first;
 std::vector<BindingEntry> &bindings = p.second;
uint8_t flags = BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
if (sym->isWeakRef())
 flags |= BIND_SYMBOL_FLAGS_WEAK_IMPORT;
 os << flags << sym->getName() << '\0'
 << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
int16_t ordinal = ordinalForSymbol(*sym);
if (ordinal != lastOrdinal) {
encodeDylibOrdinal(ordinal, os);
 lastOrdinal = ordinal;
 }
 std::vector<BindIR> opcodes;
for (const BindingEntry &b : bindings)
encodeBinding(b.target.isec->parent,
 b.target.isec->getOffset(b.target.offset), b.addend,
 lastBinding, opcodes);
if (config->optimize > 1)
optimizeOpcodes(opcodes);
for (constauto &op : opcodes)
flushOpcodes(op, os);
 }
if (!bindingsMap.empty())
 os << static_cast<uint8_t>(BIND_OPCODE_DONE);
}

voidBindingSection::writeTo(uint8_t *buf) const {
memcpy(buf, contents.data(), contents.size());
}

WeakBindingSection::WeakBindingSection()
 : LinkEditSection(segment_names::linkEdit, section_names::weakBinding) {}

voidWeakBindingSection::finalizeContents() {
 raw_svector_ostream os{contents};
 Binding lastBinding;

for (const Defined *defined : definitions)
encodeWeakOverride(defined, os);

for (auto &p : sortBindings(bindingsMap)) {
const Symbol *sym = p.first;
 std::vector<BindingEntry> &bindings = p.second;
 os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
 << sym->getName() << '\0'
 << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
 std::vector<BindIR> opcodes;
for (const BindingEntry &b : bindings)
encodeBinding(b.target.isec->parent,
 b.target.isec->getOffset(b.target.offset), b.addend,
 lastBinding, opcodes);
if (config->optimize > 1)
optimizeOpcodes(opcodes);
for (constauto &op : opcodes)
flushOpcodes(op, os);
 }
if (!bindingsMap.empty() || !definitions.empty())
 os << static_cast<uint8_t>(BIND_OPCODE_DONE);
}

voidWeakBindingSection::writeTo(uint8_t *buf) const {
memcpy(buf, contents.data(), contents.size());
}

StubsSection::StubsSection()
 : SyntheticSection(segment_names::text, section_names::stubs) {
 flags = S_SYMBOL_STUBS | S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
// The stubs section comprises machine instructions, which are aligned to
// 4 bytes on the archs we care about.
 align = 4;
 reserved2 = target->stubSize;
}

uint64_tStubsSection::getSize() const {
return entries.size() * target->stubSize;
}

voidStubsSection::writeTo(uint8_t *buf) const {
size_t off = 0;
for (const Symbol *sym : entries) {
uint64_t pointerVA =
 config->emitChainedFixups ? sym->getGotVA() : sym->getLazyPtrVA();
 target->writeStub(buf + off, *sym, pointerVA);
 off += target->stubSize;
 }
}

voidStubsSection::finalize() { isFinal = true; }

staticvoidaddBindingsForStub(Symbol *sym) {
assert(!config->emitChainedFixups);
if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
if (sym->isWeakDef()) {
 in.binding->addEntry(dysym, in.lazyPointers->isec,
 sym->stubsIndex * target->wordSize);
 in.weakBinding->addEntry(sym, in.lazyPointers->isec,
 sym->stubsIndex * target->wordSize);
 } else {
 in.lazyBinding->addEntry(dysym);
 }
 } elseif (auto *defined = dyn_cast<Defined>(sym)) {
if (defined->isExternalWeakDef()) {
 in.rebase->addEntry(in.lazyPointers->isec,
 sym->stubsIndex * target->wordSize);
 in.weakBinding->addEntry(sym, in.lazyPointers->isec,
 sym->stubsIndex * target->wordSize);
 } elseif (defined->interposable) {
 in.lazyBinding->addEntry(sym);
 } else {
llvm_unreachable("invalid stub target");
 }
 } else {
llvm_unreachable("invalid stub target symbol type");
 }
}

voidStubsSection::addEntry(Symbol *sym) {
bool inserted = entries.insert(sym);
if (inserted) {
 sym->stubsIndex = entries.size() - 1;

if (config->emitChainedFixups)
 in.got->addEntry(sym);
else
addBindingsForStub(sym);
 }
}

StubHelperSection::StubHelperSection()
 : SyntheticSection(segment_names::text, section_names::stubHelper) {
 flags = S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
 align = 4; // This section comprises machine instructions
}

uint64_tStubHelperSection::getSize() const {
return target->stubHelperHeaderSize +
 in.lazyBinding->getEntries().size() * target->stubHelperEntrySize;
}

boolStubHelperSection::isNeeded() const { return in.lazyBinding->isNeeded(); }

voidStubHelperSection::writeTo(uint8_t *buf) const {
 target->writeStubHelperHeader(buf);
size_t off = target->stubHelperHeaderSize;
for (const Symbol *sym : in.lazyBinding->getEntries()) {
 target->writeStubHelperEntry(buf + off, *sym, addr + off);
 off += target->stubHelperEntrySize;
 }
}

voidStubHelperSection::setUp() {
 Symbol *binder = symtab->addUndefined("dyld_stub_binder", /*file=*/nullptr,
/*isWeakRef=*/false);
if (auto *undefined = dyn_cast<Undefined>(binder))
treatUndefinedSymbol(*undefined,
"lazy binding (normally in libSystem.dylib)");

// treatUndefinedSymbol() can replace binder with a DylibSymbol; re-check.
 stubBinder = dyn_cast_or_null<DylibSymbol>(binder);
if (stubBinder == nullptr)
return;

 in.got->addEntry(stubBinder);

 in.imageLoaderCache->parent =
ConcatOutputSection::getOrCreateForInput(in.imageLoaderCache);
addInputSection(in.imageLoaderCache);
// Since this isn't in the symbol table or in any input file, the noDeadStrip
// argument doesn't matter.
 dyldPrivate =
 make<Defined>("__dyld_private", nullptr, in.imageLoaderCache, 0, 0,
/*isWeakDef=*/false,
/*isExternal=*/false, /*isPrivateExtern=*/false,
/*includeInSymtab=*/true,
/*isReferencedDynamically=*/false,
/*noDeadStrip=*/false);
 dyldPrivate->used = true;
}

llvm::DenseMap<llvm::CachedHashStringRef, ConcatInputSection *>
 ObjCSelRefsHelper::methnameToSelref;
voidObjCSelRefsHelper::initialize() {
// Do not fold selrefs without ICF.
if (config->icfLevel == ICFLevel::none)
return;

// Search methnames already referenced in __objc_selrefs
// Map the name to the corresponding selref entry
// which we will reuse when creating objc stubs.
for (ConcatInputSection *isec : inputSections) {
if (isec->shouldOmitFromOutput())
continue;
if (isec->getName() != section_names::objcSelrefs)
continue;
// We expect a single relocation per selref entry to __objc_methname that
// might be aggregated.
assert(isec->relocs.size() == 1);
auto Reloc = isec->relocs[0];
if (constauto *sym = Reloc.referent.dyn_cast<Symbol *>()) {
if (constauto *d = dyn_cast<Defined>(sym)) {
auto *cisec = cast<CStringInputSection>(d->isec());
auto methname = cisec->getStringRefAtOffset(d->value);
 methnameToSelref[CachedHashStringRef(methname)] = isec;
 }
 }
 }
}

voidObjCSelRefsHelper::cleanup() { methnameToSelref.clear(); }

ConcatInputSection *ObjCSelRefsHelper::makeSelRef(StringRef methname) {
auto methnameOffset =
 in.objcMethnameSection->getStringOffset(methname).outSecOff;

size_t wordSize = target->wordSize;
uint8_t *selrefData = bAlloc().Allocate<uint8_t>(wordSize);
write64le(selrefData, methnameOffset);
 ConcatInputSection *objcSelref =
makeSyntheticInputSection(segment_names::data, section_names::objcSelrefs,
 S_LITERAL_POINTERS | S_ATTR_NO_DEAD_STRIP,
 ArrayRef<uint8_t>{selrefData, wordSize},
/*align=*/wordSize);
assert(objcSelref->live);
 objcSelref->relocs.push_back({/*type=*/target->unsignedRelocType,
/*pcrel=*/false, /*length=*/3,
/*offset=*/0,
/*addend=*/static_cast<int64_t>(methnameOffset),
/*referent=*/in.objcMethnameSection->isec});
 objcSelref->parent = ConcatOutputSection::getOrCreateForInput(objcSelref);
addInputSection(objcSelref);
 objcSelref->isFinal = true;
 methnameToSelref[CachedHashStringRef(methname)] = objcSelref;
return objcSelref;
}

ConcatInputSection *ObjCSelRefsHelper::getSelRef(StringRef methname) {
auto it = methnameToSelref.find(CachedHashStringRef(methname));
if (it == methnameToSelref.end())
returnnullptr;
return it->second;
}

ObjCStubsSection::ObjCStubsSection()
 : SyntheticSection(segment_names::text, section_names::objcStubs) {
 flags = S_ATTR_SOME_INSTRUCTIONS | S_ATTR_PURE_INSTRUCTIONS;
 align = config->objcStubsMode == ObjCStubsMode::fast
 ? target->objcStubsFastAlignment
 : target->objcStubsSmallAlignment;
}

boolObjCStubsSection::isObjCStubSymbol(Symbol *sym) {
return sym->getName().starts_with(symbolPrefix);
}

StringRef ObjCStubsSection::getMethname(Symbol *sym) {
assert(isObjCStubSymbol(sym) && "not an objc stub");
auto name = sym->getName();
 StringRef methname = name.drop_front(symbolPrefix.size());
return methname;
}

voidObjCStubsSection::addEntry(Symbol *sym) {
 StringRef methname = getMethname(sym);
// We create a selref entry for each unique methname.
if (!ObjCSelRefsHelper::getSelRef(methname))
ObjCSelRefsHelper::makeSelRef(methname);

auto stubSize = config->objcStubsMode == ObjCStubsMode::fast
 ? target->objcStubsFastSize
 : target->objcStubsSmallSize;
 Defined *newSym = replaceSymbol<Defined>(
 sym, sym->getName(), nullptr, isec,
/*value=*/symbols.size() * stubSize,
/*size=*/stubSize,
/*isWeakDef=*/false, /*isExternal=*/true, /*isPrivateExtern=*/true,
/*includeInSymtab=*/true, /*isReferencedDynamically=*/false,
/*noDeadStrip=*/false);
 symbols.push_back(newSym);
}

voidObjCStubsSection::setUp() {
 objcMsgSend = symtab->addUndefined("_objc_msgSend", /*file=*/nullptr,
/*isWeakRef=*/false);
if (auto *undefined = dyn_cast<Undefined>(objcMsgSend))
treatUndefinedSymbol(*undefined,
"lazy binding (normally in libobjc.dylib)");
 objcMsgSend->used = true;
if (config->objcStubsMode == ObjCStubsMode::fast) {
 in.got->addEntry(objcMsgSend);
assert(objcMsgSend->isInGot());
 } else {
assert(config->objcStubsMode == ObjCStubsMode::small);
// In line with ld64's behavior, when objc_msgSend is a direct symbol,
// we directly reference it.
// In other cases, typically when binding in libobjc.dylib,
// we generate a stub to invoke objc_msgSend.
if (!isa<Defined>(objcMsgSend))
 in.stubs->addEntry(objcMsgSend);
 }
}

uint64_tObjCStubsSection::getSize() const {
auto stubSize = config->objcStubsMode == ObjCStubsMode::fast
 ? target->objcStubsFastSize
 : target->objcStubsSmallSize;
return stubSize * symbols.size();
}

voidObjCStubsSection::writeTo(uint8_t *buf) const {
uint64_t stubOffset = 0;
for (size_t i = 0, n = symbols.size(); i < n; ++i) {
 Defined *sym = symbols[i];

auto methname = getMethname(sym);
 InputSection *selRef = ObjCSelRefsHelper::getSelRef(methname);
assert(selRef != nullptr && "no selref for methname");
auto selrefAddr = selRef->getVA(0);
 target->writeObjCMsgSendStub(buf + stubOffset, sym, in.objcStubs->addr,
 stubOffset, selrefAddr, objcMsgSend);
 }
}

LazyPointerSection::LazyPointerSection()
 : SyntheticSection(segment_names::data, section_names::lazySymbolPtr) {
 align = target->wordSize;
 flags = S_LAZY_SYMBOL_POINTERS;
}

uint64_tLazyPointerSection::getSize() const {
return in.stubs->getEntries().size() * target->wordSize;
}

boolLazyPointerSection::isNeeded() const {
return !in.stubs->getEntries().empty();
}

voidLazyPointerSection::writeTo(uint8_t *buf) const {
size_t off = 0;
for (const Symbol *sym : in.stubs->getEntries()) {
if (constauto *dysym = dyn_cast<DylibSymbol>(sym)) {
if (dysym->hasStubsHelper()) {
uint64_t stubHelperOffset =
 target->stubHelperHeaderSize +
 dysym->stubsHelperIndex * target->stubHelperEntrySize;
write64le(buf + off, in.stubHelper->addr + stubHelperOffset);
 }
 } else {
write64le(buf + off, sym->getVA());
 }
 off += target->wordSize;
 }
}

LazyBindingSection::LazyBindingSection()
 : LinkEditSection(segment_names::linkEdit, section_names::lazyBinding) {}

voidLazyBindingSection::finalizeContents() {
// TODO: Just precompute output size here instead of writing to a temporary
// buffer