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}
125
126Defined *TextOutputSection::getThunkInRange(const ConcatInputSection &isec,
127 const Relocation &r,
128 const ThunkInfo &thunkInfo) const {
129 assert(!isTargetKnownInRange(isec, r));
130 if (!thunkInfo.sym)
131 return nullptr;
132 uint64_t callVA = isec.getVA() + r.offset;
133 uint64_t lowVA = target->backwardBranchRange < callVA
134 ? callVA - target->backwardBranchRange
135 : 0;
136 uint64_t highVA = callVA + target->forwardBranchRange;
137 uint64_t thunkVA = thunkInfo.isec->getVA();
138 if (lowVA <= thunkVA && thunkVA <= highVA)
139 return thunkInfo.sym;
140 return nullptr;
141}
142
143void TextOutputSection::updateBranchTargetToThunk(Relocation &r,
144 Defined *thunk) {
145 r.referent = thunk;
146 // The thunk itself bakes in the addend, so the call-site reloc must
147 // branch to the thunk start with no extra offset.
148 r.addend = 0;
149 ++thunkCallCount;
150}
151
152void TextOutputSection::createThunk(const ConcatInputSection &isec,
153 Relocation &r, ThunkInfo &thunkInfo) {
154 assert(getThunkInRange(isec, r, thunkInfo) == nullptr);
155 assert(isec.isFinal);
156 uint64_t highVA = isec.getVA() + r.offset + target->forwardBranchRange;
157 if (addr + size > highVA) {
158 // There were too many consecutive branch instructions for `slop`
159 // below. If you hit this: For the current algorithm, just bumping up
160 // slop below and trying again is probably simplest. (See also PR51578
161 // comment 5).
162 fatal(msg: Twine(__FUNCTION__) +
163 ": FIXME: thunk range overrun. Consider increasing the "
164 "slop-scale with `--slop-scale=<unsigned_int>`.");
165 }
166 thunkInfo.isec = makeSyntheticInputSection(segName: isec.getSegName(), sectName: isec.getName());
167 thunkInfo.isec->parent = this;
168 assert(thunkInfo.isec->live);
169
170 std::string addendSuffix;
171 if (r.addend != 0)
172 addendSuffix = "+" + std::to_string(val: r.addend);
173 size_t thunkSize = target->thunkSize;
174 auto *funcSym = cast<Symbol *>(Val&: r.referent);
175 StringRef thunkName =
176 saver().save(S: funcSym->getName() + addendSuffix + ".thunk." +
177 std::to_string(val: thunkInfo.sequence++));
178 if (!isa<Defined>(Val: funcSym) || cast<Defined>(Val: funcSym)->isExternal()) {
179 thunkInfo.sym = symtab->addDefined(
180 name: thunkName, /*file=*/nullptr, thunkInfo.isec, /*value=*/0, size: thunkSize,
181 /*isWeakDef=*/false, /*isPrivateExtern=*/true,
182 /*isReferencedDynamically=*/false, /*noDeadStrip=*/false,
183 /*isWeakDefCanBeHidden=*/false);
184 } else {
185 thunkInfo.sym = make<Defined>(
186 args&: thunkName, /*file=*/args: nullptr, args&: thunkInfo.isec, /*value=*/args: 0, args&: thunkSize,
187 /*isWeakDef=*/args: false, /*isExternal=*/args: false, /*isPrivateExtern=*/args: true,
188 /*includeInSymtab=*/args: true, /*isReferencedDynamically=*/args: false,
189 /*noDeadStrip=*/args: false, /*isWeakDefCanBeHidden=*/args: false);
190 }
191 thunkInfo.sym->used = true;
192 thunkInfo.sym->branchExtensionThunk = true;
193 target->populateThunk(thunk: thunkInfo.isec, funcSym, addend: r.addend);
194 updateBranchTargetToThunk(r, thunk: thunkInfo.sym);
195 finalizeOne(isec: thunkInfo.isec);
196 thunks.push_back(x: thunkInfo.isec);
197}
198
199std::optional<uint64_t>
200TextOutputSection::estimateStubsEndVA(unsigned numPotentialThunks) const {
201 if (!parent)
202 return std::nullopt;
203
204 auto sections =
205 ArrayRef(parent->getSections())
206 .drop_until(Pred: [&](const OutputSection *osec) { return osec == this; });
207
208 // Walk backwards to find the last stubs section
209 while (!sections.empty()) {
210 auto *osec = sections.back();
211 if (osec->isNeeded() && (osec == in.stubs || osec == in.objcStubs))
212 break;
213 sections.consume_back();
214 }
215 if (sections.empty())
216 return std::nullopt;
217
218 assert(inputs.empty() || inputs.back()->isFinal);
219 uint64_t estimatedStubsEnd =
220 addr + size + numPotentialThunks * target->thunkSize;
221 for (auto *osec : sections) {
222 if (osec == this)
223 continue;
224 if (!osec->isNeeded())
225 continue;
226 // Check if we will emit any more sections before the last stubs section
227 if (osec != in.stubs && osec != in.stubHelper && osec != in.objcStubs)
228 return std::nullopt;
229 estimatedStubsEnd =
230 alignToPowerOf2(Value: estimatedStubsEnd, Align: osec->align) + osec->getSize();
231 }
232 return estimatedStubsEnd;
233}
234
235bool TextOutputSection::isTargetStubsAndInRange(
236 const ConcatInputSection &isec, const Relocation &r,
237 std::optional<uint64_t> estimatedStubsEnd) const {
238 if (!estimatedStubsEnd.has_value())
239 return false;
240 auto *funcSym = cast<Symbol *>(Val: r.referent);
241 if (!funcSym->isInStubs() && !(in.objcStubs && in.objcStubs->isNeeded() &&
242 ObjCStubsSection::isObjCStubSymbol(sym: funcSym)))
243 return false;
244 if (r.addend)
245 return false;
246 uint64_t highVA = isec.getVA() + r.offset + target->forwardBranchRange;
247 return *estimatedStubsEnd <= highVA;
248}
249
250void TextOutputSection::finalize() {
251 if (!needsThunks()) {
252 for (ConcatInputSection *isec : inputs)
253 finalizeOne(isec);
254 return;
255 }
256
257 // Branches whose target sections are out of range or have not yet been
258 // finalized. We may need to emit thunks for them.
259 std::deque<std::pair<ConcatInputSection *, Relocation *>> branchesToProcess;
260 // Branches whose targets have not yet be finalized, but a thunk for that
261 // target exists. We defer processing these branches because it's possible we
262 // can still direct call to their targets after they have all been finalized.
263 SmallVector<std::tuple<ConcatInputSection *, Relocation *, Defined *>>
264 deferredBranchRedirects;
265
266 const uint64_t slop = config->slopScale * target->thunkSize;
267 for (auto *isec : inputs) {
268 while (!branchesToProcess.empty()) {
269 auto [callerIsec, r] = branchesToProcess.front();
270 assert(callerIsec->isFinal);
271 auto &thunkInfo = thunkMap[*r];
272 if (isTargetKnownInRange(isec: *callerIsec, r: *r)) {
273 branchesToProcess.pop_front();
274 continue;
275 }
276 if (auto *thunk = getThunkInRange(isec: *callerIsec, r: *r, thunkInfo)) {
277 deferredBranchRedirects.emplace_back(Args&: callerIsec, Args&: r, Args&: thunk);
278 branchesToProcess.pop_front();
279 continue;
280 }
281 uint64_t highVA =
282 callerIsec->getVA() + r->offset + target->forwardBranchRange;
283 uint64_t nextEnd =
284 alignToPowerOf2(Value: addr + size, Align: isec->align) + isec->getSize();
285 // If we were to emit this section, would we have enough space for more
286 // thunks? If we do, then we can delay processing this thunk so we may
287 // finalize more potencial target sections. Otherwise we must emit thunks
288 // until we have enough space.
289 if (nextEnd + slop <= highVA)
290 break;
291
292 createThunk(isec: *callerIsec, r&: *r, thunkInfo);
293 branchesToProcess.pop_front();
294 }
295 finalizeOne(isec);
296
297 // TODO: Remove this check and the assert below. In fact, I don't believe
298 // the relocation iteration order matters for correctness.
299 bool hasCallsite = llvm::any_of(Range&: isec->relocs, P: [](Relocation &r) {
300 return target->hasAttr(type: r.type, bit: RelocAttrBits::BRANCH);
301 });
302 if (!hasCallsite)
303 continue;
304
305 // Process relocs by ascending address, i.e., ascending offset within isec
306 // FIXME: This property does not hold for object files produced by ld64's
307 // `-r` mode.
308 assert(is_sorted(isec->relocs, [](Relocation &a, Relocation &b) {
309 return a.offset > b.offset;
310 }));
311 for (Relocation &r : reverse(C&: isec->relocs)) {
312 if (!target->hasAttr(type: r.type, bit: RelocAttrBits::BRANCH))
313 continue;
314 if (isTargetKnownInRange(isec: *isec, r))
315 continue;
316 auto &thunkInfo = thunkMap[r];
317 if (auto *thunk = getThunkInRange(isec: *isec, r, thunkInfo)) {
318 deferredBranchRedirects.emplace_back(Args&: isec, Args: &r, Args&: thunk);
319 continue;
320 }
321 branchesToProcess.emplace_back(args&: isec, args: &r);
322 }
323 }
324
325 llvm::erase_if(C&: branchesToProcess, P: [&](auto &pair) {
326 auto [callerIsec, r] = pair;
327 return isTargetKnownInRange(isec: *callerIsec, r: *r);
328 });
329 // Count distinct unresolved branch targets that still lack an in-range thunk.
330 // We use this as an upper bound on the number of thunks we may still create
331 // when estimating where __stubs / __objc_stubs could end up.
332 DenseSet<ThunkKey, ThunkMapKeyInfo> branchTargets;
333 for (auto [callerIsec, r] : branchesToProcess) {
334 ThunkKey thunkKey(*r);
335 auto &thunkInfo = thunkMap[thunkKey];
336 if (!getThunkInRange(isec: *callerIsec, r: *r, thunkInfo))
337 branchTargets.insert(V: thunkKey);
338 }
339
340 auto estimatedStubsEnd = estimateStubsEndVA(numPotentialThunks: branchTargets.size());
341 for (auto [isec, r, thunk] : deferredBranchRedirects) {
342 if (isTargetKnownInRange(isec: *isec, r: *r))
343 continue;
344 if (isTargetStubsAndInRange(isec: *isec, r: *r, estimatedStubsEnd))
345 continue;
346 updateBranchTargetToThunk(r&: *r, thunk);
347 }
348
349 for (auto [isec, r] : branchesToProcess) {
350 if (isTargetStubsAndInRange(isec: *isec, r: *r, estimatedStubsEnd))
351 continue;
352 auto &thunkInfo = thunkMap[*r];
353 if (auto *thunk = getThunkInRange(isec: *isec, r: *r, thunkInfo)) {
354 updateBranchTargetToThunk(r&: *r, thunk);
355 continue;
356 }
357 createThunk(isec: *isec, r&: *r, thunkInfo);
358 }
359
360 if (!thunks.empty())
361 log(msg: name + ": Created " + Twine(thunks.size()) + " (" +
362 Twine(thunks.size() * target->thunkSize / 1024) +
363 " KB) thunks and updated " + Twine(thunkCallCount) + " branch targets");
364}
365
366void ConcatOutputSection::writeTo(uint8_t *buf) const {
367 parallelForEach(R: inputs, Fn: [buf](ConcatInputSection *isec) {
368 isec->writeTo(buf: buf + isec->outSecOff);
369 });
370}
371
372void TextOutputSection::writeTo(uint8_t *buf) const {
373 // Inputs and thunks all write to their own range of the output buffer, so
374 // there is no need to interleave the two sorted vectors here.
375 parallelForEach(R: inputs, Fn: [buf](ConcatInputSection *isec) {
376 isec->writeTo(buf: buf + isec->outSecOff);
377 });
378 parallelForEach(R: thunks, Fn: [buf](ConcatInputSection *thunk) {
379 thunk->writeTo(buf: buf + thunk->outSecOff);
380 });
381}
382
383void ConcatOutputSection::finalizeFlags(InputSection *input) {
384 switch (sectionType(flags: input->getFlags())) {
385 default /*type-unspec'ed*/:
386 // FIXME: Add additional logic here when supporting emitting obj files.
387 break;
388 case S_4BYTE_LITERALS:
389 case S_8BYTE_LITERALS:
390 case S_16BYTE_LITERALS:
391 case S_CSTRING_LITERALS:
392 case S_ZEROFILL:
393 case S_LAZY_SYMBOL_POINTERS:
394 case S_MOD_TERM_FUNC_POINTERS:
395 case S_THREAD_LOCAL_REGULAR:
396 case S_THREAD_LOCAL_ZEROFILL:
397 case S_THREAD_LOCAL_VARIABLES:
398 case S_THREAD_LOCAL_INIT_FUNCTION_POINTERS:
399 case S_THREAD_LOCAL_VARIABLE_POINTERS:
400 case S_NON_LAZY_SYMBOL_POINTERS:
401 case S_SYMBOL_STUBS:
402 flags |= input->getFlags();
403 break;
404 }
405}
406
407ConcatOutputSection *
408ConcatOutputSection::getOrCreateForInput(const InputSection *isec) {
409 NamePair names = maybeRenameSection(key: {isec->getSegName(), isec->getName()});
410 ConcatOutputSection *&osec = concatOutputSections[names];
411 if (!osec) {
412 if (isec->getSegName() == segment_names::text &&
413 isec->getName() != section_names::gccExceptTab &&
414 isec->getName() != section_names::ehFrame)
415 osec = make<TextOutputSection>(args&: names.second);
416 else
417 osec = make<ConcatOutputSection>(args&: names.second);
418 }
419 return osec;
420}
421
422NamePair macho::maybeRenameSection(NamePair key) {
423 auto newNames = config->sectionRenameMap.find(Val: key);
424 if (newNames != config->sectionRenameMap.end())
425 return newNames->second;
426 return key;
427}
428