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/ErrorHandler.h"
17 #include "lld/Common/Memory.h"
18 #include "llvm/BinaryFormat/MachO.h"
19 #include "llvm/Support/ScopedPrinter.h"
20 #include "llvm/Support/TimeProfiler.h"
21
22 using namespace llvm;
23 using namespace llvm::MachO;
24 using namespace lld;
25 using namespace lld::macho;
26
27 MapVector<NamePair, ConcatOutputSection *> macho::concatOutputSections;
28
addInput(ConcatInputSection * input)29 void ConcatOutputSection::addInput(ConcatInputSection *input) {
30 assert(input->parent == this);
31 if (inputs.empty()) {
32 align = input->align;
33 flags = input->getFlags();
34 } else {
35 align = std::max(align, input->align);
36 finalizeFlags(input);
37 }
38 inputs.push_back(input);
39 }
40
41 // Branch-range extension can be implemented in two ways, either through ...
42 //
43 // (1) Branch islands: Single branch instructions (also of limited range),
44 // that might be chained in multiple hops to reach the desired
45 // destination. On ARM64, as 16 branch islands are needed to hop between
46 // opposite ends of a 2 GiB program. LD64 uses branch islands exclusively,
47 // even when it needs excessive hops.
48 //
49 // (2) Thunks: Instruction(s) to load the destination address into a scratch
50 // register, followed by a register-indirect branch. Thunks are
51 // constructed to reach any arbitrary address, so need not be
52 // chained. Although thunks need not be chained, a program might need
53 // multiple thunks to the same destination distributed throughout a large
54 // program so that all call sites can have one within range.
55 //
56 // The optimal approach is to mix islands for distinations within two hops,
57 // and use thunks for destinations at greater distance. For now, we only
58 // implement thunks. TODO: Adding support for branch islands!
59 //
60 // Internally -- as expressed in LLD's data structures -- a
61 // branch-range-extension thunk comprises ...
62 //
63 // (1) new Defined privateExtern symbol for the thunk named
64 // <FUNCTION>.thunk.<SEQUENCE>, which references ...
65 // (2) new InputSection, which contains ...
66 // (3.1) new data for the instructions to load & branch to the far address +
67 // (3.2) new Relocs on instructions to load the far address, which reference ...
68 // (4.1) existing Defined extern symbol for the real function in __text, or
69 // (4.2) existing DylibSymbol for the real function in a dylib
70 //
71 // Nearly-optimal thunk-placement algorithm features:
72 //
73 // * Single pass: O(n) on the number of call sites.
74 //
75 // * Accounts for the exact space overhead of thunks - no heuristics
76 //
77 // * Exploits the full range of call instructions - forward & backward
78 //
79 // Data:
80 //
81 // * DenseMap<Symbol *, ThunkInfo> thunkMap: Maps the function symbol
82 // to its thunk bookkeeper.
83 //
84 // * struct ThunkInfo (bookkeeper): Call instructions have limited range, and
85 // distant call sites might be unable to reach the same thunk, so multiple
86 // thunks are necessary to serve all call sites in a very large program. A
87 // thunkInfo stores state for all thunks associated with a particular
88 // function: (a) thunk symbol, (b) input section containing stub code, and
89 // (c) sequence number for the active thunk incarnation. When an old thunk
90 // goes out of range, we increment the sequence number and create a new
91 // thunk named <FUNCTION>.thunk.<SEQUENCE>.
92 //
93 // * A thunk incarnation comprises (a) private-extern Defined symbol pointing
94 // to (b) an InputSection holding machine instructions (similar to a MachO
95 // stub), and (c) Reloc(s) that reference the real function for fixing-up
96 // the stub code.
97 //
98 // * std::vector<InputSection *> MergedInputSection::thunks: A vector parallel
99 // to the inputs vector. We store new thunks via cheap vector append, rather
100 // than costly insertion into the inputs vector.
101 //
102 // Control Flow:
103 //
104 // * During address assignment, MergedInputSection::finalize() examines call
105 // sites by ascending address and creates thunks. When a function is beyond
106 // the range of a call site, we need a thunk. Place it at the largest
107 // available forward address from the call site. Call sites increase
108 // monotonically and thunks are always placed as far forward as possible;
109 // thus, we place thunks at monotonically increasing addresses. Once a thunk
110 // is placed, it and all previous input-section addresses are final.
111 //
112 // * MergedInputSection::finalize() and MergedInputSection::writeTo() merge
113 // the inputs and thunks vectors (both ordered by ascending address), which
114 // is simple and cheap.
115
116 DenseMap<Symbol *, ThunkInfo> lld::macho::thunkMap;
117
118 // Determine whether we need thunks, which depends on the target arch -- RISC
119 // (i.e., ARM) generally does because it has limited-range branch/call
120 // instructions, whereas CISC (i.e., x86) generally doesn't. RISC only needs
121 // thunks for programs so large that branch source & destination addresses
122 // might differ more than the range of branch instruction(s).
needsThunks() const123 bool ConcatOutputSection::needsThunks() const {
124 if (!target->usesThunks())
125 return false;
126 uint64_t isecAddr = addr;
127 for (InputSection *isec : inputs)
128 isecAddr = alignTo(isecAddr, isec->align) + isec->getSize();
129 if (isecAddr - addr + in.stubs->getSize() <= target->branchRange)
130 return false;
131 // Yes, this program is large enough to need thunks.
132 for (InputSection *isec : inputs) {
133 for (Reloc &r : isec->relocs) {
134 if (!target->hasAttr(r.type, RelocAttrBits::BRANCH))
135 continue;
136 auto *sym = r.referent.get<Symbol *>();
137 // Pre-populate the thunkMap and memoize call site counts for every
138 // InputSection and ThunkInfo. We do this for the benefit of
139 // ConcatOutputSection::estimateStubsInRangeVA()
140 ThunkInfo &thunkInfo = thunkMap[sym];
141 // Knowing ThunkInfo call site count will help us know whether or not we
142 // might need to create more for this referent at the time we are
143 // estimating distance to __stubs in .
144 ++thunkInfo.callSiteCount;
145 // Knowing InputSection call site count will help us avoid work on those
146 // that have no BRANCH relocs.
147 ++isec->callSiteCount;
148 }
149 }
150 return true;
151 }
152
153 // Since __stubs is placed after __text, we must estimate the address
154 // beyond which stubs are within range of a simple forward branch.
estimateStubsInRangeVA(size_t callIdx) const155 uint64_t ConcatOutputSection::estimateStubsInRangeVA(size_t callIdx) const {
156 uint64_t branchRange = target->branchRange;
157 size_t endIdx = inputs.size();
158 ConcatInputSection *isec = inputs[callIdx];
159 uint64_t isecVA = isec->getVA();
160 // Tally the non-stub functions which still have call sites
161 // remaining to process, which yields the maximum number
162 // of thunks we might yet place.
163 size_t maxPotentialThunks = 0;
164 for (auto &tp : thunkMap) {
165 ThunkInfo &ti = tp.second;
166 maxPotentialThunks +=
167 !tp.first->isInStubs() && ti.callSitesUsed < ti.callSiteCount;
168 }
169 // Tally the total size of input sections remaining to process.
170 uint64_t isecEnd = isec->getVA();
171 for (size_t i = callIdx; i < endIdx; i++) {
172 InputSection *isec = inputs[i];
173 isecEnd = alignTo(isecEnd, isec->align) + isec->getSize();
174 }
175 // Estimate the address after which call sites can safely call stubs
176 // directly rather than through intermediary thunks.
177 uint64_t stubsInRangeVA = isecEnd + maxPotentialThunks * target->thunkSize +
178 in.stubs->getSize() - branchRange;
179 log("thunks = " + std::to_string(thunkMap.size()) +
180 ", potential = " + std::to_string(maxPotentialThunks) +
181 ", stubs = " + std::to_string(in.stubs->getSize()) + ", isecVA = " +
182 to_hexString(isecVA) + ", threshold = " + to_hexString(stubsInRangeVA) +
183 ", isecEnd = " + to_hexString(isecEnd) +
184 ", tail = " + to_hexString(isecEnd - isecVA) +
185 ", slop = " + to_hexString(branchRange - (isecEnd - isecVA)));
186 return stubsInRangeVA;
187 }
188
finalize()189 void ConcatOutputSection::finalize() {
190 uint64_t isecAddr = addr;
191 uint64_t isecFileOff = fileOff;
192 auto finalizeOne = [&](ConcatInputSection *isec) {
193 isecAddr = alignTo(isecAddr, isec->align);
194 isecFileOff = alignTo(isecFileOff, isec->align);
195 isec->outSecOff = isecAddr - addr;
196 isec->isFinal = true;
197 isecAddr += isec->getSize();
198 isecFileOff += isec->getFileSize();
199 };
200
201 if (!needsThunks()) {
202 for (ConcatInputSection *isec : inputs)
203 finalizeOne(isec);
204 size = isecAddr - addr;
205 fileSize = isecFileOff - fileOff;
206 return;
207 }
208
209 uint64_t branchRange = target->branchRange;
210 uint64_t stubsInRangeVA = TargetInfo::outOfRangeVA;
211 size_t thunkSize = target->thunkSize;
212 size_t relocCount = 0;
213 size_t callSiteCount = 0;
214 size_t thunkCallCount = 0;
215 size_t thunkCount = 0;
216
217 // inputs[finalIdx] is for finalization (address-assignment)
218 size_t finalIdx = 0;
219 // Kick-off by ensuring that the first input section has an address
220 for (size_t callIdx = 0, endIdx = inputs.size(); callIdx < endIdx;
221 ++callIdx) {
222 if (finalIdx == callIdx)
223 finalizeOne(inputs[finalIdx++]);
224 ConcatInputSection *isec = inputs[callIdx];
225 assert(isec->isFinal);
226 uint64_t isecVA = isec->getVA();
227 // Assign addresses up-to the forward branch-range limit
228 while (finalIdx < endIdx &&
229 isecAddr + inputs[finalIdx]->getSize() < isecVA + branchRange)
230 finalizeOne(inputs[finalIdx++]);
231 if (isec->callSiteCount == 0)
232 continue;
233 if (finalIdx == endIdx && stubsInRangeVA == TargetInfo::outOfRangeVA) {
234 // When we have finalized all input sections, __stubs (destined
235 // to follow __text) comes within range of forward branches and
236 // we can estimate the threshold address after which we can
237 // reach any stub with a forward branch. Note that although it
238 // sits in the middle of a loop, this code executes only once.
239 // It is in the loop because we need to call it at the proper
240 // time: the earliest call site from which the end of __text
241 // (and start of __stubs) comes within range of a forward branch.
242 stubsInRangeVA = estimateStubsInRangeVA(callIdx);
243 }
244 // Process relocs by ascending address, i.e., ascending offset within isec
245 std::vector<Reloc> &relocs = isec->relocs;
246 // FIXME: This property does not hold for object files produced by ld64's
247 // `-r` mode.
248 assert(is_sorted(relocs,
249 [](Reloc &a, Reloc &b) { return a.offset > b.offset; }));
250 for (Reloc &r : reverse(relocs)) {
251 ++relocCount;
252 if (!target->hasAttr(r.type, RelocAttrBits::BRANCH))
253 continue;
254 ++callSiteCount;
255 // Calculate branch reachability boundaries
256 uint64_t callVA = isecVA + r.offset;
257 uint64_t lowVA = branchRange < callVA ? callVA - branchRange : 0;
258 uint64_t highVA = callVA + branchRange;
259 // Calculate our call referent address
260 auto *funcSym = r.referent.get<Symbol *>();
261 ThunkInfo &thunkInfo = thunkMap[funcSym];
262 // The referent is not reachable, so we need to use a thunk ...
263 if (funcSym->isInStubs() && callVA >= stubsInRangeVA) {
264 // ... Oh, wait! We are close enough to the end that __stubs
265 // are now within range of a simple forward branch.
266 continue;
267 }
268 uint64_t funcVA = funcSym->resolveBranchVA();
269 ++thunkInfo.callSitesUsed;
270 if (lowVA < funcVA && funcVA < highVA) {
271 // The referent is reachable with a simple call instruction.
272 continue;
273 }
274 ++thunkInfo.thunkCallCount;
275 ++thunkCallCount;
276 // If an existing thunk is reachable, use it ...
277 if (thunkInfo.sym) {
278 uint64_t thunkVA = thunkInfo.isec->getVA();
279 if (lowVA < thunkVA && thunkVA < highVA) {
280 r.referent = thunkInfo.sym;
281 continue;
282 }
283 }
284 // ... otherwise, create a new thunk
285 if (isecAddr > highVA) {
286 // When there is small-to-no margin between highVA and
287 // isecAddr and the distance between subsequent call sites is
288 // smaller than thunkSize, then a new thunk can go out of
289 // range. Fix by unfinalizing inputs[finalIdx] to reduce the
290 // distance between callVA and highVA, then shift some thunks
291 // to occupy address-space formerly occupied by the
292 // unfinalized inputs[finalIdx].
293 fatal(Twine(__FUNCTION__) + ": FIXME: thunk range overrun");
294 }
295 thunkInfo.isec =
296 make<ConcatInputSection>(isec->getSegName(), isec->getName());
297 thunkInfo.isec->parent = this;
298 StringRef thunkName = saver.save(funcSym->getName() + ".thunk." +
299 std::to_string(thunkInfo.sequence++));
300 r.referent = thunkInfo.sym = symtab->addDefined(
301 thunkName, /*file=*/nullptr, thunkInfo.isec, /*value=*/0,
302 /*size=*/thunkSize, /*isWeakDef=*/false, /*isPrivateExtern=*/true,
303 /*isThumb=*/false, /*isReferencedDynamically=*/false,
304 /*noDeadStrip=*/false);
305 target->populateThunk(thunkInfo.isec, funcSym);
306 finalizeOne(thunkInfo.isec);
307 thunks.push_back(thunkInfo.isec);
308 ++thunkCount;
309 }
310 }
311 size = isecAddr - addr;
312 fileSize = isecFileOff - fileOff;
313
314 log("thunks for " + parent->name + "," + name +
315 ": funcs = " + std::to_string(thunkMap.size()) +
316 ", relocs = " + std::to_string(relocCount) +
317 ", all calls = " + std::to_string(callSiteCount) +
318 ", thunk calls = " + std::to_string(thunkCallCount) +
319 ", thunks = " + std::to_string(thunkCount));
320 }
321
writeTo(uint8_t * buf) const322 void ConcatOutputSection::writeTo(uint8_t *buf) const {
323 // Merge input sections from thunk & ordinary vectors
324 size_t i = 0, ie = inputs.size();
325 size_t t = 0, te = thunks.size();
326 while (i < ie || t < te) {
327 while (i < ie && (t == te || inputs[i]->getSize() == 0 ||
328 inputs[i]->outSecOff < thunks[t]->outSecOff)) {
329 inputs[i]->writeTo(buf + inputs[i]->outSecOff);
330 ++i;
331 }
332 while (t < te && (i == ie || thunks[t]->outSecOff < inputs[i]->outSecOff)) {
333 thunks[t]->writeTo(buf + thunks[t]->outSecOff);
334 ++t;
335 }
336 }
337 }
338
finalizeFlags(InputSection * input)339 void ConcatOutputSection::finalizeFlags(InputSection *input) {
340 switch (sectionType(input->getFlags())) {
341 default /*type-unspec'ed*/:
342 // FIXME: Add additional logic here when supporting emitting obj files.
343 break;
344 case S_4BYTE_LITERALS:
345 case S_8BYTE_LITERALS:
346 case S_16BYTE_LITERALS:
347 case S_CSTRING_LITERALS:
348 case S_ZEROFILL:
349 case S_LAZY_SYMBOL_POINTERS:
350 case S_MOD_TERM_FUNC_POINTERS:
351 case S_THREAD_LOCAL_REGULAR:
352 case S_THREAD_LOCAL_ZEROFILL:
353 case S_THREAD_LOCAL_VARIABLES:
354 case S_THREAD_LOCAL_INIT_FUNCTION_POINTERS:
355 case S_THREAD_LOCAL_VARIABLE_POINTERS:
356 case S_NON_LAZY_SYMBOL_POINTERS:
357 case S_SYMBOL_STUBS:
358 flags |= input->getFlags();
359 break;
360 }
361 }
362
363 ConcatOutputSection *
getOrCreateForInput(const InputSection * isec)364 ConcatOutputSection::getOrCreateForInput(const InputSection *isec) {
365 NamePair names = maybeRenameSection({isec->getSegName(), isec->getName()});
366 ConcatOutputSection *&osec = concatOutputSections[names];
367 if (!osec)
368 osec = make<ConcatOutputSection>(names.second);
369 return osec;
370 }
371
maybeRenameSection(NamePair key)372 NamePair macho::maybeRenameSection(NamePair key) {
373 auto newNames = config->sectionRenameMap.find(key);
374 if (newNames != config->sectionRenameMap.end())
375 return newNames->second;
376 return key;
377 }
378