1//===- ConcatOutputSection.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 "ConcatOutputSection.h"
10#include "Config.h"
11#include "OutputSegment.h"
12#include "SymbolTable.h"
13#include "Symbols.h"
14#include "SyntheticSections.h"
15#include "Target.h"
16#include "lld/Common/CommonLinkerContext.h"
17#include "llvm/BinaryFormat/MachO.h"
18#include "llvm/Support/Parallel.h"
19#include <deque>
20
21using namespace llvm;
22using namespace llvm::MachO;
23using namespace lld;
24using namespace lld::macho;
25
26MapVector<NamePair, ConcatOutputSection *> macho::concatOutputSections;
27
28void ConcatOutputSection::addInput(ConcatInputSection *input) {
29 assert(input->parent == this);
30 if (inputs.empty()) {
31 align = input->align;
32 flags = input->getFlags();
33 } else {
34 align = std::max(a: align, b: input->align);
35 finalizeFlags(input);
36 }
37 inputs.push_back(x: input);
38}
39
40// Branch-range extension can be implemented in two ways, either through ...
41//
42// (1) Branch islands: Single branch instructions (also of limited range),
43// that might be chained in multiple hops to reach the desired
44// destination. On ARM64, as 16 branch islands are needed to hop between
45// opposite ends of a 2 GiB program. LD64 uses branch islands exclusively,
46// even when it needs excessive hops.
47//
48// (2) Thunks: Instruction(s) to load the destination address into a scratch
49// register, followed by a register-indirect branch. Thunks are
50// constructed to reach any arbitrary address, so need not be
51// chained. Although thunks need not be chained, a program might need
52// multiple thunks to the same destination distributed throughout a large
53// program so that all call sites can have one within range.
54//
55// The optimal approach is to mix islands for destinations within two hops,
56// and use thunks for destinations at greater distance. For now, we only
57// implement thunks. TODO: Adding support for branch islands!
58
59DenseMap<ThunkKey, ThunkInfo, ThunkMapKeyInfo> lld::macho::thunkMap;
60
61// Determine whether we need thunks, which depends on the target arch -- RISC
62// (i.e., ARM) generally does because it has limited-range branch/call
63// instructions, whereas CISC (i.e., x86) generally doesn't. RISC only needs
64// thunks for programs so large that branch source & destination addresses
65// might differ more than the range of branch instruction(s).
66bool TextOutputSection::needsThunks() const {
67 if (!target->usesThunks())
68 return false;
69 // FIXME: It is not enough to just estimate the size of this section. We
70 // should compute parent->needsThunks by estimating the size of all __text
71 // sections. See https://github.com/llvm/llvm-project/issues/195387
72 uint64_t isecAddr = addr;
73 for (ConcatInputSection *isec : inputs)
74 isecAddr = alignToPowerOf2(Value: isecAddr, Align: isec->align) + isec->getSize();
75 // Other sections besides __text might be small enough to pass this
76 // test but nevertheless need thunks for calling into other sections.
77 // An imperfect heuristic to use in this case is that if a section
78 // we've already processed in this segment needs thunks, so do the
79 // rest.
80 bool needsThunks = parent && parent->needsThunks;
81
82 // Calculate the total size of all branch target sections
83 uint64_t branchTargetsSize = in.stubs->getSize();
84
85 // Add the size of __objc_stubs section if it exists
86 if (in.objcStubs && in.objcStubs->isNeeded())
87 branchTargetsSize += in.objcStubs->getSize();
88
89 if (!needsThunks &&
90 isecAddr - addr + branchTargetsSize <=
91 std::min(a: target->backwardBranchRange, b: target->forwardBranchRange))
92 return false;
93 // Yes, this program is large enough to need thunks.
94 if (parent)
95 parent->needsThunks = true;
96 return true;
97}
98
99void ConcatOutputSection::finalizeOne(ConcatInputSection *isec) {
100 size = alignToPowerOf2(Value: size, Align: isec->align);
101 fileSize = alignToPowerOf2(Value: fileSize, Align: isec->align);
102 isec->outSecOff = size;
103 isec->isFinal = true;
104 size += isec->getSize();
105 fileSize += isec->getFileSize();
106}
107
108void ConcatOutputSection::finalizeContents() {
109 for (ConcatInputSection *isec : inputs)
110 finalizeOne(isec);
111}
112
113bool TextOutputSection::isTargetKnownInRange(const ConcatInputSection &isec,
114 const Relocation &r) const {
115 uint64_t callVA = isec.getVA() + r.offset;
116 uint64_t lowVA = target->backwardBranchRange < callVA
117 ? callVA - target->backwardBranchRange
118 : 0;
119 uint64_t highVA = callVA + target->forwardBranchRange;
120 auto *funcSym = cast<Symbol *>(Val: r.referent);
121 uint64_t funcVA = resolveSymbolOffsetVA(sym: funcSym, type: r.type, offset: r.addend);
122 // Check if the referent is reachable with a simple call instruction.
123 return lowVA <= funcVA && funcVA <= highVA;
124}
125Defined *TextOutputSection::findThunkInRange(const ConcatInputSection &isec,
126 const Relocation &r) const {
127 auto it = thunkMap.find(Val: ThunkKey(r));
128 if (it == thunkMap.end())
129 return nullptr;
130 return getThunkInRange(isec, r, thunkInfo: it->second);
131}
132
133Defined *TextOutputSection::getThunkInRange(const ConcatInputSection &isec,
134 const Relocation &r,
135 const ThunkInfo &thunkInfo) const {
136 assert(!isTargetKnownInRange(isec, r));
137 if (!thunkInfo.sym)
138 return nullptr;
139 uint64_t callVA = isec.getVA() + r.offset;
140 uint64_t lowVA = target->backwardBranchRange < callVA
141 ? callVA - target->backwardBranchRange
142 : 0;
143 uint64_t highVA = callVA + target->forwardBranchRange;
144 uint64_t thunkVA = thunkInfo.isec->getVA();
145 if (lowVA <= thunkVA && thunkVA <= highVA)
146 return thunkInfo.sym;
147 return nullptr;
148}
149
150void TextOutputSection::updateBranchTargetToThunk(Relocation &r,
151 Defined *thunk) {
152 r.referent = thunk;
153 // The thunk itself bakes in the addend, so the call-site reloc must
154 // branch to the thunk start with no extra offset.
155 r.addend = 0;
156 ++thunkCallCount;
157}
158
159void TextOutputSection::createThunk(const ConcatInputSection &isec,
160 Relocation &r) {
161 auto &thunkInfo = thunkMap[r];
162 assert(getThunkInRange(isec, r, thunkInfo) == nullptr);
163 assert(isec.isFinal);
164 uint64_t highVA = isec.getVA() + r.offset + target->forwardBranchRange;
165 if (addr + size > highVA) {
166 // There were too many consecutive branch instructions for `slop`
167 // below. If you hit this: For the current algorithm, just bumping up
168 // slop below and trying again is probably simplest. (See also PR51578
169 // comment 5).
170 fatal(msg: Twine(__FUNCTION__) +
171 ": FIXME: thunk range overrun. Consider increasing the "
172 "slop-scale with `--slop-scale=<unsigned_int>`.");
173 }
174 thunkInfo.isec = makeSyntheticInputSection(segName: isec.getSegName(), sectName: isec.getName());
175 thunkInfo.isec->parent = this;
176 assert(thunkInfo.isec->live);
177
178 std::string addendSuffix;
179 if (r.addend != 0)
180 addendSuffix = "+" + std::to_string(val: r.addend);
181 size_t thunkSize = target->thunkSize;
182 auto *funcSym = cast<Symbol *>(Val&: r.referent);
183 StringRef thunkName =
184 saver().save(S: funcSym->getName() + addendSuffix + ".thunk." +
185 std::to_string(val: thunkInfo.sequence++));
186 if (!isa<Defined>(Val: funcSym) || cast<Defined>(Val: funcSym)->isExternal()) {
187 thunkInfo.sym = symtab->addDefined(
188 name: thunkName, /*file=*/nullptr, thunkInfo.isec, /*value=*/0, size: thunkSize,
189 /*isWeakDef=*/false, /*isPrivateExtern=*/true,
190 /*isReferencedDynamically=*/false, /*noDeadStrip=*/false,
191 /*isWeakDefCanBeHidden=*/false);
192 } else {
193 thunkInfo.sym = make<Defined>(
194 args&: thunkName, /*file=*/args: nullptr, args&: thunkInfo.isec, /*value=*/args: 0, args&: thunkSize,
195 /*isWeakDef=*/args: false, /*isExternal=*/args: false, /*isPrivateExtern=*/args: true,
196 /*includeInSymtab=*/args: true, /*isReferencedDynamically=*/args: false,
197 /*noDeadStrip=*/args: false, /*isWeakDefCanBeHidden=*/args: false);
198 }
199 thunkInfo.sym->used = true;
200 thunkInfo.sym->branchExtensionThunk = true;
201 target->populateThunk(thunk: thunkInfo.isec, funcSym, addend: r.addend);
202 updateBranchTargetToThunk(r, thunk: thunkInfo.sym);
203 finalizeOne(isec: thunkInfo.isec);
204 thunks.push_back(x: thunkInfo.isec);
205}
206
207std::optional<uint64_t>
208TextOutputSection::estimateStubsEndVA(unsigned numPotentialThunks) const {
209 if (!parent)
210 return std::nullopt;
211
212 auto sections =
213 ArrayRef(parent->getSections())
214 .drop_until(Pred: [&](const OutputSection *osec) { return osec == this; });
215
216 // Walk backwards to find the last stubs section
217 while (!sections.empty()) {
218 auto *osec = sections.back();
219 if (osec->isNeeded() && (osec == in.stubs || osec == in.objcStubs))
220 break;
221 sections.consume_back();
222 }
223 if (sections.empty())
224 return std::nullopt;
225
226 assert(inputs.empty() || inputs.back()->isFinal);
227 uint64_t estimatedStubsEnd =
228 addr + size + numPotentialThunks * target->thunkSize;
229 for (auto *osec : sections) {
230 if (osec == this)
231 continue;
232 if (!osec->isNeeded())
233 continue;
234 // Check if we will emit any more sections before the last stubs section
235 if (osec != in.stubs && osec != in.stubHelper && osec != in.objcStubs)
236 return std::nullopt;
237 estimatedStubsEnd =
238 alignToPowerOf2(Value: estimatedStubsEnd, Align: osec->align) + osec->getSize();
239 }
240 return estimatedStubsEnd;
241}
242
243bool TextOutputSection::isTargetStubsAndInRange(
244 const ConcatInputSection &isec, const Relocation &r,
245 std::optional<uint64_t> estimatedStubsEnd) const {
246 if (!estimatedStubsEnd.has_value())
247 return false;
248 auto *funcSym = cast<Symbol *>(Val: r.referent);
249 if (!funcSym->isInStubs() && !(in.objcStubs && in.objcStubs->isNeeded() &&
250 ObjCStubsSection::isObjCStubSymbol(sym: funcSym)))
251 return false;
252 if (r.addend)
253 return false;
254 uint64_t highVA = isec.getVA() + r.offset + target->forwardBranchRange;
255 return *estimatedStubsEnd <= highVA;
256}
257
258void TextOutputSection::finalize() {
259 if (!needsThunks()) {
260 for (ConcatInputSection *isec : inputs)
261 finalizeOne(isec);
262 return;
263 }
264
265 // Branches whose target sections are out of range or have not yet been
266 // finalized. We may need to emit thunks for them.
267 std::deque<std::pair<ConcatInputSection *, Relocation *>> branchesToProcess;
268 // Branches whose targets have not yet be finalized, but a thunk for that
269 // target exists. We defer processing these branches because it's possible we
270 // can still direct call to their targets after they have all been finalized.
271 SmallVector<std::tuple<ConcatInputSection *, Relocation *, Defined *>>
272 deferredBranchRedirects;
273
274 const uint64_t slop = config->slopScale * target->thunkSize;
275 for (auto *isec : inputs) {
276 while (!branchesToProcess.empty()) {
277 auto [callerIsec, r] = branchesToProcess.front();
278 assert(callerIsec->isFinal);
279 if (isTargetKnownInRange(isec: *callerIsec, r: *r)) {
280 branchesToProcess.pop_front();
281 continue;
282 }
283 if (auto *thunk = findThunkInRange(isec: *callerIsec, r: *r)) {
284 deferredBranchRedirects.emplace_back(Args&: callerIsec, Args&: r, Args&: thunk);
285 branchesToProcess.pop_front();
286 continue;
287 }
288 uint64_t highVA =
289 callerIsec->getVA() + r->offset + target->forwardBranchRange;
290 uint64_t nextEnd =
291 alignToPowerOf2(Value: addr + size, Align: isec->align) + isec->getSize();
292 // If we were to emit this section, would we have enough space for more
293 // thunks? If we do, then we can delay processing this thunk so we may
294 // finalize more potencial target sections. Otherwise we must emit thunks
295 // until we have enough space.
296 if (nextEnd + slop <= highVA)
297 break;
298
299 createThunk(isec: *callerIsec, r&: *r);
300 branchesToProcess.pop_front();
301 }
302 finalizeOne(isec);
303
304 // TODO: Remove this check and the assert below. In fact, I don't believe
305 // the relocation iteration order matters for correctness.
306 bool hasCallsite = llvm::any_of(Range&: isec->relocs, P: [](Relocation &r) {
307 return target->hasAttr(type: r.type, bit: RelocAttrBits::BRANCH);
308 });
309 if (!hasCallsite)
310 continue;
311
312 // Process relocs by ascending address, i.e., ascending offset within isec
313 // FIXME: This property does not hold for object files produced by ld64's
314 // `-r` mode.
315 assert(is_sorted(isec->relocs, [](Relocation &a, Relocation &b) {
316 return a.offset > b.offset;
317 }));
318 for (Relocation &r : reverse(C&: isec->relocs)) {
319 if (!target->hasAttr(type: r.type, bit: RelocAttrBits::BRANCH))
320 continue;
321 if (isTargetKnownInRange(isec: *isec, r))
322 continue;
323 if (auto *thunk = findThunkInRange(isec: *isec, r)) {
324 deferredBranchRedirects.emplace_back(Args&: isec, Args: &r, Args&: thunk);
325 continue;
326 }
327 branchesToProcess.emplace_back(args&: isec, args: &r);
328 }
329 }
330
331 llvm::erase_if(C&: branchesToProcess, P: [&](auto &pair) {
332 auto [callerIsec, r] = pair;
333 return isTargetKnownInRange(isec: *callerIsec, r: *r);
334 });
335 // Count distinct unresolved branch targets that still lack an in-range thunk.
336 // We use this as an upper bound on the number of thunks we may still create
337 // when estimating where __stubs / __objc_stubs could end up.
338 DenseSet<ThunkKey, ThunkMapKeyInfo> branchTargets;
339 for (auto [callerIsec, r] : branchesToProcess) {
340 if (!findThunkInRange(isec: *callerIsec, r: *r))
341 branchTargets.insert(V: ThunkKey(*r));
342 }
343
344 auto estimatedStubsEnd = estimateStubsEndVA(numPotentialThunks: branchTargets.size());
345 for (auto [isec, r, thunk] : deferredBranchRedirects) {
346 if (isTargetKnownInRange(isec: *isec, r: *r))
347 continue;
348 if (isTargetStubsAndInRange(isec: *isec, r: *r, estimatedStubsEnd))
349 continue;
350 updateBranchTargetToThunk(r&: *r, thunk);
351 }
352
353 for (auto [isec, r] : branchesToProcess) {
354 if (isTargetStubsAndInRange(isec: *isec, r: *r, estimatedStubsEnd))
355 continue;
356 if (auto *thunk = findThunkInRange(isec: *isec, r: *r)) {
357 updateBranchTargetToThunk(r&: *r, thunk);
358 continue;
359 }
360 createThunk(isec: *isec, r&: *r);
361 }
362
363 if (!thunks.empty())
364 log(msg: name + ": Created " + Twine(thunks.size()) + " (" +
365 Twine(thunks.size() * target->thunkSize / 1024) +
366 " KB) thunks and updated " + Twine(thunkCallCount) + " branch targets");
367}
368
369void ConcatOutputSection::writeTo(uint8_t *buf) const {
370 parallelForEach(R: inputs, Fn: [buf](ConcatInputSection *isec) {
371 isec->writeTo(buf: buf + isec->outSecOff);
372 });
373}
374
375void TextOutputSection::writeTo(uint8_t *buf) const {
376 // Inputs and thunks all write to their own range of the output buffer, so
377 // there is no need to interleave the two sorted vectors here.
378 parallelForEach(R: inputs, Fn: [buf](ConcatInputSection *isec) {
379 isec->writeTo(buf: buf + isec->outSecOff);
380 });
381 parallelForEach(R: thunks, Fn: [buf](ConcatInputSection *thunk) {
382 thunk->writeTo(buf: buf + thunk->outSecOff);
383 });
384}
385
386void ConcatOutputSection::finalizeFlags(InputSection *input) {
387 switch (sectionType(flags: input->getFlags())) {
388 default /*type-unspec'ed*/:
389 // FIXME: Add additional logic here when supporting emitting obj files.
390 break;
391 case S_4BYTE_LITERALS:
392 case S_8BYTE_LITERALS:
393 case S_16BYTE_LITERALS:
394 case S_CSTRING_LITERALS:
395 case S_ZEROFILL:
396 case S_LAZY_SYMBOL_POINTERS:
397 case S_MOD_TERM_FUNC_POINTERS:
398 case S_THREAD_LOCAL_REGULAR:
399 case S_THREAD_LOCAL_ZEROFILL:
400 case S_THREAD_LOCAL_VARIABLES:
401 case S_THREAD_LOCAL_INIT_FUNCTION_POINTERS:
402 case S_THREAD_LOCAL_VARIABLE_POINTERS:
403 case S_NON_LAZY_SYMBOL_POINTERS:
404 case S_SYMBOL_STUBS:
405 flags |= input->getFlags();
406 break;
407 }
408}
409
410ConcatOutputSection *
411ConcatOutputSection::getOrCreateForInput(const InputSection *isec) {
412 NamePair names = maybeRenameSection(key: {isec->getSegName(), isec->getName()});
413 ConcatOutputSection *&osec = concatOutputSections[names];
414 if (!osec) {
415 if (isec->getSegName() == segment_names::text &&
416 isec->getName() != section_names::gccExceptTab &&
417 isec->getName() != section_names::ehFrame)
418 osec = make<TextOutputSection>(args&: names.second);
419 else
420 osec = make<ConcatOutputSection>(args&: names.second);
421 }
422 return osec;
423}
424
425NamePair macho::maybeRenameSection(NamePair key) {
426 auto newNames = config->sectionRenameMap.find(Val: key);
427 if (newNames != config->sectionRenameMap.end())
428 return newNames->second;
429 return key;
430}
431