1//===- UnwindInfoSection.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 "UnwindInfoSection.h"
10#include "InputSection.h"
11#include "Layout.h"
12#include "OutputSection.h"
13#include "OutputSegment.h"
14#include "SymbolTable.h"
15#include "Symbols.h"
16#include "SyntheticSections.h"
17#include "Target.h"
18
19#include "lld/Common/ErrorHandler.h"
20#include "lld/Common/Memory.h"
21#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/BinaryFormat/MachO.h"
24#include "llvm/Support/Parallel.h"
25
26#include "mach-o/compact_unwind_encoding.h"
27
28#include <numeric>
29
30using namespace llvm;
31using namespace llvm::MachO;
32using namespace llvm::support::endian;
33using namespace lld;
34using namespace lld::macho;
35
36#define COMMON_ENCODINGS_MAX 127
37#define COMPACT_ENCODINGS_MAX 256
38
39#define SECOND_LEVEL_PAGE_BYTES 4096
40#define SECOND_LEVEL_PAGE_WORDS (SECOND_LEVEL_PAGE_BYTES / sizeof(uint32_t))
41#define REGULAR_SECOND_LEVEL_ENTRIES_MAX \
42 ((SECOND_LEVEL_PAGE_BYTES - \
43 sizeof(unwind_info_regular_second_level_page_header)) / \
44 sizeof(unwind_info_regular_second_level_entry))
45#define COMPRESSED_SECOND_LEVEL_ENTRIES_MAX \
46 ((SECOND_LEVEL_PAGE_BYTES - \
47 sizeof(unwind_info_compressed_second_level_page_header)) / \
48 sizeof(uint32_t))
49
50#define COMPRESSED_ENTRY_FUNC_OFFSET_BITS 24
51#define COMPRESSED_ENTRY_FUNC_OFFSET_MASK \
52 UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(~0)
53
54static_assert(static_cast<uint32_t>(UNWIND_X86_64_DWARF_SECTION_OFFSET) ==
55 static_cast<uint32_t>(UNWIND_ARM64_DWARF_SECTION_OFFSET) &&
56 static_cast<uint32_t>(UNWIND_X86_64_DWARF_SECTION_OFFSET) ==
57 static_cast<uint32_t>(UNWIND_X86_DWARF_SECTION_OFFSET));
58
59constexpr uint64_t DWARF_SECTION_OFFSET = UNWIND_X86_64_DWARF_SECTION_OFFSET;
60
61// Compact Unwind format is a Mach-O evolution of DWARF Unwind that
62// optimizes space and exception-time lookup. Most DWARF unwind
63// entries can be replaced with Compact Unwind entries, but the ones
64// that cannot are retained in DWARF form.
65//
66// This comment will address macro-level organization of the pre-link
67// and post-link compact unwind tables. For micro-level organization
68// pertaining to the bitfield layout of the 32-bit compact unwind
69// entries, see libunwind/include/mach-o/compact_unwind_encoding.h
70//
71// Important clarifying factoids:
72//
73// * __LD,__compact_unwind is the compact unwind format for compiler
74// output and linker input. It is never a final output. It could be
75// an intermediate output with the `-r` option which retains relocs.
76//
77// * __TEXT,__unwind_info is the compact unwind format for final
78// linker output. It is never an input.
79//
80// * __TEXT,__eh_frame is the DWARF format for both linker input and output.
81//
82// * __TEXT,__unwind_info entries are divided into 4 KiB pages (2nd
83// level) by ascending address, and the pages are referenced by an
84// index (1st level) in the section header.
85//
86// * Following the headers in __TEXT,__unwind_info, the bulk of the
87// section contains a vector of compact unwind entries
88// `{functionOffset, encoding}` sorted by ascending `functionOffset`.
89// Adjacent entries with the same encoding can be folded to great
90// advantage, achieving a 3-order-of-magnitude reduction in the
91// number of entries.
92//
93// Refer to the definition of unwind_info_section_header in
94// compact_unwind_encoding.h for an overview of the format we are encoding
95// here.
96
97// TODO(gkm): how do we align the 2nd-level pages?
98
99// The various fields in the on-disk representation of each compact unwind
100// entry.
101#define FOR_EACH_CU_FIELD(DO) \
102 DO(Ptr, functionAddress) \
103 DO(uint32_t, functionLength) \
104 DO(compact_unwind_encoding_t, encoding) \
105 DO(Ptr, personality) \
106 DO(Ptr, lsda)
107
108CREATE_LAYOUT_CLASS(CompactUnwind, FOR_EACH_CU_FIELD);
109
110#undef FOR_EACH_CU_FIELD
111
112// LLD's internal representation of a compact unwind entry.
113struct CompactUnwindEntry {
114 uint64_t functionAddress;
115 uint32_t functionLength;
116 compact_unwind_encoding_t encoding;
117 Symbol *personality;
118 InputSection *lsda;
119};
120
121using EncodingMap = DenseMap<compact_unwind_encoding_t, size_t>;
122
123struct SecondLevelPage {
124 uint32_t kind;
125 size_t entryIndex;
126 size_t entryCount;
127 size_t byteCount;
128 std::vector<compact_unwind_encoding_t> localEncodings;
129 EncodingMap localEncodingIndexes;
130};
131
132// UnwindInfoSectionImpl allows us to avoid cluttering our header file with a
133// lengthy definition of UnwindInfoSection.
134class UnwindInfoSectionImpl final : public UnwindInfoSection {
135public:
136 UnwindInfoSectionImpl() : cuLayout(target->wordSize) {}
137 uint64_t getSize() const override { return unwindInfoSize; }
138 void prepare() override;
139 void finalize() override;
140 void writeTo(uint8_t *buf) const override;
141
142private:
143 void prepareRelocations(ConcatInputSection *);
144 void relocateCompactUnwind(std::vector<CompactUnwindEntry> &);
145 void encodePersonalities();
146 Symbol *canonicalizePersonality(Symbol *);
147
148 uint64_t unwindInfoSize = 0;
149 SmallVector<decltype(symbols)::value_type, 0> symbolsVec;
150 CompactUnwindLayout cuLayout;
151 std::vector<std::pair<compact_unwind_encoding_t, size_t>> commonEncodings;
152 EncodingMap commonEncodingIndexes;
153 // The entries here will be in the same order as their originating symbols
154 // in symbolsVec.
155 std::vector<CompactUnwindEntry> cuEntries;
156 std::vector<Symbol *> personalities;
157 SmallDenseMap<std::pair<InputSection *, uint64_t /* addend */>, Symbol *>
158 personalityTable;
159 // Indices into cuEntries for CUEs with a non-null LSDA.
160 std::vector<size_t> entriesWithLsda;
161 // Map of cuEntries index to an index within the LSDA array.
162 DenseMap<size_t, uint32_t> lsdaIndex;
163 std::vector<SecondLevelPage> secondLevelPages;
164 uint64_t level2PagesOffset = 0;
165 // The highest-address function plus its size. The unwinder needs this to
166 // determine the address range that is covered by unwind info.
167 uint64_t cueEndBoundary = 0;
168};
169
170UnwindInfoSection::UnwindInfoSection()
171 : SyntheticSection(segment_names::text, section_names::unwindInfo) {
172 align = 4;
173}
174
175// Record function symbols that may need entries emitted in __unwind_info, which
176// stores unwind data for address ranges.
177//
178// Note that if several adjacent functions have the same unwind encoding and
179// personality function and no LSDA, they share one unwind entry. For this to
180// work, functions without unwind info need explicit "no unwind info" unwind
181// entries -- else the unwinder would think they have the unwind info of the
182// closest function with unwind info right before in the image. Thus, we add
183// function symbols for each unique address regardless of whether they have
184// associated unwind info.
185void UnwindInfoSection::addSymbol(const Defined *d) {
186 if (d->unwindEntry())
187 allEntriesAreOmitted = false;
188 // We don't yet know the final output address of this symbol, but we know that
189 // they are uniquely determined by a combination of the isec and value, so
190 // we use that as the key here.
191 auto p = symbols.insert(KV: {{d->isec(), d->value}, d});
192 // If we have multiple symbols at the same address, only one of them can have
193 // an associated unwind entry.
194 if (!p.second && d->unwindEntry()) {
195 assert(p.first->second == d || !p.first->second->unwindEntry());
196 p.first->second = d;
197 }
198}
199
200void UnwindInfoSectionImpl::prepare() {
201 // This iteration needs to be deterministic, since prepareRelocations may add
202 // entries to the GOT. Hence the use of a MapVector for
203 // UnwindInfoSection::symbols.
204 for (const Defined *d : make_second_range(c&: symbols))
205 if (d->unwindEntry()) {
206 if (d->unwindEntry()->getName() == section_names::compactUnwind) {
207 prepareRelocations(d->unwindEntry());
208 } else {
209 // We don't have to add entries to the GOT here because FDEs have
210 // explicit GOT relocations, so Writer::scanRelocations() will add those
211 // GOT entries. However, we still need to canonicalize the personality
212 // pointers (like prepareRelocations() does for CU entries) in order
213 // to avoid overflowing the 3-personality limit.
214 FDE &fde = cast<ObjFile>(Val: d->getFile())->fdes[d->unwindEntry()];
215 fde.personality = canonicalizePersonality(fde.personality);
216 // If ICF folded the LSDA, point at the surviving copy.
217 if (fde.lsda)
218 fde.lsda = fde.lsda->canonical();
219 }
220 }
221}
222
223// arm64e's unwinder expects signed personality pointers.
224static void addPersonalityGotEntry(Symbol *s) {
225 if (config->arch() == AK_arm64e)
226 in.authGot->addEntry(sym: s);
227 else
228 in.got->addEntry(sym: s);
229}
230
231static bool hasPersonalityGotEntry(const Symbol *s) {
232 return config->arch() == AK_arm64e ? in.authGot->contains(sym: s) : s->isInGot();
233}
234
235static uint64_t getPersonalityGotVA(const Symbol *s) {
236 return config->arch() == AK_arm64e ? in.authGot->getVA(sym: s) : s->getGotVA();
237}
238
239// Compact unwind relocations have different semantics, so we handle them in a
240// separate code path from regular relocations. First, we do not wish to add
241// rebase opcodes for __LD,__compact_unwind, because that section doesn't
242// actually end up in the final binary. Second, personality pointers always
243// reside in the GOT and must be treated specially.
244void UnwindInfoSectionImpl::prepareRelocations(ConcatInputSection *isec) {
245 assert(!isec->shouldOmitFromOutput() &&
246 "__compact_unwind section should not be omitted");
247
248 // FIXME: Make this skip relocations for CompactUnwindEntries that
249 // point to dead-stripped functions. That might save some amount of
250 // work. But since there are usually just few personality functions
251 // that are referenced from many places, at least some of them likely
252 // live, it wouldn't reduce number of got entries.
253 for (size_t i = 0; i < isec->relocs.size(); ++i) {
254 Relocation &r = isec->relocs[i];
255 assert(target->hasAttr(r.type, RelocAttrBits::UNSIGNED));
256 // Since compact unwind sections aren't part of the inputSections vector,
257 // they don't get canonicalized by scanRelocations(), so we have to do the
258 // canonicalization here.
259 if (auto *referentIsec = dyn_cast_if_present<InputSection *>(Val&: r.referent))
260 r.referent = referentIsec->canonical();
261
262 // Functions and LSDA entries always reside in the same object file as the
263 // compact unwind entries that references them, and thus appear as section
264 // relocs. There is no need to prepare them. We only prepare relocs for
265 // personality functions.
266 if (r.offset != cuLayout.personalityOffset)
267 continue;
268
269 if (auto *s = dyn_cast_if_present<Symbol *>(Val&: r.referent)) {
270 // Personality functions are nearly always system-defined (e.g.,
271 // ___gxx_personality_v0 for C++) and relocated as dylib symbols. When an
272 // application provides its own personality function, it might be
273 // referenced by an extern Defined symbol reloc, or a local section reloc.
274 if (auto *defined = dyn_cast<Defined>(Val: s)) {
275 // XXX(vyng) This is a special case for handling duplicate personality
276 // symbols. Note that LD64's behavior is a bit different and it is
277 // inconsistent with how symbol resolution usually work
278 //
279 // So we've decided not to follow it. Instead, simply pick the symbol
280 // with the same name from the symbol table to replace the local one.
281 //
282 // (See discussions/alternatives already considered on D107533)
283 if (!defined->isExternal())
284 if (Symbol *sym = symtab->find(name: defined->getName()))
285 if (!sym->isLazy())
286 r.referent = s = sym;
287 }
288 if (auto *undefined = dyn_cast<Undefined>(Val: s)) {
289 treatUndefinedSymbol(*undefined, isec, offset: r.offset);
290 // treatUndefinedSymbol() can replace s with a DylibSymbol; re-check.
291 if (isa<Undefined>(Val: s))
292 continue;
293 }
294
295 // Similar to canonicalizePersonality(), but we also register a GOT entry.
296 if (auto *defined = dyn_cast<Defined>(Val: s)) {
297 // Check if we have created a synthetic symbol at the same address.
298 Symbol *&personality =
299 personalityTable[{defined->isec(), defined->value}];
300 if (personality == nullptr) {
301 personality = defined;
302 addPersonalityGotEntry(s: defined);
303 } else if (personality != defined) {
304 r.referent = personality;
305 }
306 continue;
307 }
308
309 assert(isa<DylibSymbol>(s));
310 addPersonalityGotEntry(s);
311 continue;
312 }
313
314 if (auto *referentIsec = dyn_cast_if_present<InputSection *>(Val&: r.referent)) {
315 assert(!isCoalescedWeak(referentIsec));
316 // Personality functions can be referenced via section relocations
317 // if they live in the same object file. Create placeholder synthetic
318 // symbols for them in the GOT. If the corresponding symbol is already
319 // in the GOT, use that to avoid creating a duplicate entry. All GOT
320 // entries needed by non-unwind sections will have already been added
321 // by this point.
322 Symbol *&s = personalityTable[{referentIsec, r.getAddend()}];
323 if (s == nullptr) {
324 Defined *const *gotEntry =
325 llvm::find_if(Range&: referentIsec->symbols, P: [&](Defined const *d) {
326 return d->value == static_cast<uint64_t>(r.getAddend()) &&
327 hasPersonalityGotEntry(s: d);
328 });
329 if (gotEntry != referentIsec->symbols.end()) {
330 s = *gotEntry;
331 } else {
332 // This runs after dead stripping, so the noDeadStrip argument does
333 // not matter.
334 s = make<Defined>(args: "<internal>", /*file=*/args: nullptr, args&: referentIsec,
335 args: r.getAddend(), /*size=*/args: 0, /*isWeakDef=*/args: false,
336 /*isExternal=*/args: false, /*isPrivateExtern=*/args: false,
337 /*includeInSymtab=*/args: true,
338 /*isReferencedDynamically=*/args: false,
339 /*noDeadStrip=*/args: false);
340 s->used = true;
341 addPersonalityGotEntry(s);
342 }
343 }
344 r.referent = s;
345 r.setAddend(0);
346 }
347 }
348}
349
350Symbol *UnwindInfoSectionImpl::canonicalizePersonality(Symbol *personality) {
351 if (auto *defined = dyn_cast_or_null<Defined>(Val: personality)) {
352 // Check if we have created a synthetic symbol at the same address.
353 Symbol *&synth = personalityTable[{defined->isec(), defined->value}];
354 if (synth == nullptr)
355 synth = defined;
356 else if (synth != defined)
357 return synth;
358 }
359 return personality;
360}
361
362// We need to apply the relocations to the pre-link compact unwind section
363// before converting it to post-link form. There should only be absolute
364// relocations here: since we are not emitting the pre-link CU section, there
365// is no source address to make a relative location meaningful.
366void UnwindInfoSectionImpl::relocateCompactUnwind(
367 std::vector<CompactUnwindEntry> &cuEntries) {
368 parallelFor(Begin: 0, End: symbolsVec.size(), Fn: [&](size_t i) {
369 CompactUnwindEntry &cu = cuEntries[i];
370 const Defined *d = symbolsVec[i].second;
371 cu.functionAddress = d->getVA();
372 if (!d->unwindEntry())
373 return;
374
375 // If we have DWARF unwind info, create a slimmed-down CU entry that points
376 // to it.
377 if (d->unwindEntry()->getName() == section_names::ehFrame) {
378 // The unwinder will look for the DWARF entry starting at the hint,
379 // assuming the hint points to a valid CFI record start. If it
380 // fails to find the record, it proceeds in a linear search through the
381 // contiguous CFI records from the hint until the end of the section.
382 // Ideally, in the case where the offset is too large to be encoded, we
383 // would instead encode the largest possible offset to a valid CFI record,
384 // but since we don't keep track of that, just encode zero -- the start of
385 // the section is always the start of a CFI record.
386 uint64_t dwarfOffsetHint =
387 d->unwindEntry()->outSecOff <= DWARF_SECTION_OFFSET
388 ? d->unwindEntry()->outSecOff
389 : 0;
390 cu.encoding = target->modeDwarfEncoding | dwarfOffsetHint;
391 const FDE &fde = cast<ObjFile>(Val: d->getFile())->fdes[d->unwindEntry()];
392 cu.functionLength = fde.funcLength;
393 // Omit the DWARF personality from compact-unwind entry so that we
394 // don't need to encode it.
395 cu.personality = nullptr;
396 cu.lsda = fde.lsda;
397 return;
398 }
399
400 assert(d->unwindEntry()->getName() == section_names::compactUnwind);
401
402 auto buf =
403 reinterpret_cast<const uint8_t *>(d->unwindEntry()->data.data()) -
404 target->wordSize;
405 cu.functionLength =
406 support::endian::read32le(P: buf + cuLayout.functionLengthOffset);
407 cu.encoding = support::endian::read32le(P: buf + cuLayout.encodingOffset);
408 for (const Relocation &r : d->unwindEntry()->relocs) {
409 if (r.offset == cuLayout.personalityOffset)
410 cu.personality = cast<Symbol *>(Val: r.referent);
411 else if (r.offset == cuLayout.lsdaOffset)
412 cu.lsda = r.getReferentInputSection();
413 }
414 });
415}
416
417// There should only be a handful of unique personality pointers, so we can
418// encode them as 2-bit indices into a small array.
419void UnwindInfoSectionImpl::encodePersonalities() {
420 for (CompactUnwindEntry &cu : cuEntries) {
421 if (cu.personality == nullptr)
422 continue;
423 // Linear search is fast enough for a small array.
424 auto it = find(Range&: personalities, Val: cu.personality);
425 uint32_t personalityIndex; // 1-based index
426 if (it != personalities.end()) {
427 personalityIndex = std::distance(first: personalities.begin(), last: it) + 1;
428 } else {
429 personalities.push_back(x: cu.personality);
430 personalityIndex = personalities.size();
431 }
432 cu.encoding |=
433 personalityIndex << llvm::countr_zero(
434 Val: static_cast<compact_unwind_encoding_t>(UNWIND_PERSONALITY_MASK));
435 }
436 if (personalities.size() > 3)
437 error(msg: "too many personalities (" + Twine(personalities.size()) +
438 ") for compact unwind to encode");
439}
440
441static bool canFoldEncoding(compact_unwind_encoding_t encoding) {
442 // From compact_unwind_encoding.h:
443 // UNWIND_X86_64_MODE_STACK_IND:
444 // A "frameless" (RBP not used as frame pointer) function large constant
445 // stack size. This case is like the previous, except the stack size is too
446 // large to encode in the compact unwind encoding. Instead it requires that
447 // the function contains "subq $nnnnnnnn,RSP" in its prolog. The compact
448 // encoding contains the offset to the nnnnnnnn value in the function in
449 // UNWIND_X86_64_FRAMELESS_STACK_SIZE.
450 // Since this means the unwinder has to look at the `subq` in the function
451 // of the unwind info's unwind address, two functions that have identical
452 // unwind info can't be folded if it's using this encoding since both
453 // entries need unique addresses.
454 static_assert(static_cast<uint32_t>(UNWIND_X86_64_MODE_STACK_IND) ==
455 static_cast<uint32_t>(UNWIND_X86_MODE_STACK_IND));
456 if ((target->cpuType == CPU_TYPE_X86_64 || target->cpuType == CPU_TYPE_X86) &&
457 (encoding & UNWIND_MODE_MASK) == UNWIND_X86_64_MODE_STACK_IND) {
458 // FIXME: Consider passing in the two function addresses and getting
459 // their two stack sizes off the `subq` and only returning false if they're
460 // actually different.
461 return false;
462 }
463 return true;
464}
465
466// Scan the __LD,__compact_unwind entries and compute the space needs of
467// __TEXT,__unwind_info and __TEXT,__eh_frame.
468void UnwindInfoSectionImpl::finalize() {
469 if (symbols.empty())
470 return;
471
472 // At this point, the address space for __TEXT,__text has been
473 // assigned, so we can relocate the __LD,__compact_unwind entries
474 // into a temporary buffer. Relocation is necessary in order to sort
475 // the CU entries by function address. Sorting is necessary so that
476 // we can fold adjacent CU entries with identical encoding+personality
477 // and without any LSDA. Folding is necessary because it reduces the
478 // number of CU entries by as much as 3 orders of magnitude!
479 cuEntries.resize(new_size: symbols.size());
480 // The "map" part of the symbols MapVector was only needed for deduplication
481 // in addSymbol(). Now that we are done adding, move the contents to a plain
482 // std::vector for indexed access.
483 symbolsVec = symbols.takeVector();
484 relocateCompactUnwind(cuEntries);
485
486 // Sort the entries by address.
487 llvm::sort(C&: cuEntries, Comp: [&](auto &a, auto &b) {
488 return a.functionAddress < b.functionAddress;
489 });
490
491 // Record the ending boundary before we fold the entries.
492 cueEndBoundary =
493 cuEntries.back().functionAddress + cuEntries.back().functionLength;
494
495 // Fold adjacent entries with matching encoding+personality and without LSDA
496 // We use three iterators to fold in-situ:
497 // (1) `foldBegin` is the first of a potential sequence of matching entries
498 // (2) `foldEnd` is the first non-matching entry after `foldBegin`.
499 // The semi-open interval [ foldBegin .. foldEnd ) contains a range
500 // entries that can be folded into a single entry and written to ...
501 // (3) `foldWrite`
502 auto foldWrite = cuEntries.begin();
503 for (auto foldBegin = cuEntries.begin(); foldBegin != cuEntries.end();) {
504 auto foldEnd = foldBegin;
505 // Common LSDA encodings (e.g. for C++ and Objective-C) contain offsets from
506 // a base address. The base address is normally not contained directly in
507 // the LSDA, and in that case, the personality function treats the starting
508 // address of the function (which is computed by the unwinder) as the base
509 // address and interprets the LSDA accordingly. The unwinder computes the
510 // starting address of a function as the address associated with its CU
511 // entry. For this reason, we cannot fold adjacent entries if they have an
512 // LSDA, because folding would make the unwinder compute the wrong starting
513 // address for the functions with the folded entries, which in turn would
514 // cause the personality function to misinterpret the LSDA for those
515 // functions. In the very rare case where the base address is encoded
516 // directly in the LSDA, two functions at different addresses would
517 // necessarily have different LSDAs, so their CU entries would not have been
518 // folded anyway.
519 while (++foldEnd != cuEntries.end() &&
520 foldBegin->encoding == foldEnd->encoding && !foldBegin->lsda &&
521 !foldEnd->lsda &&
522 // If we've gotten to this point, we don't have an LSDA, which should
523 // also imply that we don't have a personality function, since in all
524 // likelihood a personality function needs the LSDA to do anything
525 // useful. It can be technically valid to have a personality function
526 // and no LSDA though (e.g. the C++ personality __gxx_personality_v0
527 // is just a no-op without LSDA), so we still check for personality
528 // function equivalence to handle that case.
529 foldBegin->personality == foldEnd->personality &&
530 canFoldEncoding(encoding: foldEnd->encoding))
531 ;
532 *foldWrite++ = *foldBegin;
533 foldBegin = foldEnd;
534 }
535 cuEntries.erase(first: foldWrite, last: cuEntries.end());
536
537 encodePersonalities();
538
539 // Count frequencies of the folded encodings
540 EncodingMap encodingFrequencies;
541 for (const CompactUnwindEntry &cu : cuEntries)
542 encodingFrequencies[cu.encoding]++;
543
544 // Make a vector of encodings, sorted by descending frequency
545 for (const auto &frequency : encodingFrequencies)
546 commonEncodings.emplace_back(args: frequency);
547 llvm::sort(C&: commonEncodings,
548 Comp: [](const std::pair<compact_unwind_encoding_t, size_t> &a,
549 const std::pair<compact_unwind_encoding_t, size_t> &b) {
550 // When frequencies match, secondarily sort on encoding
551 // to maintain parity with validate-unwind-info.py
552 return std::tie(args: a.second, args: a.first) > std::tie(args: b.second, args: b.first);
553 });
554
555 // Truncate the vector to 127 elements.
556 // Common encoding indexes are limited to 0..126, while encoding
557 // indexes 127..255 are local to each second-level page
558 if (commonEncodings.size() > COMMON_ENCODINGS_MAX)
559 commonEncodings.resize(COMMON_ENCODINGS_MAX);
560
561 // Create a map from encoding to common-encoding-table index
562 for (size_t i = 0; i < commonEncodings.size(); i++)
563 commonEncodingIndexes[commonEncodings[i].first] = i;
564
565 // Split folded encodings into pages, where each page is limited by ...
566 // (a) 4 KiB capacity
567 // (b) 24-bit difference between first & final function address
568 // (c) 8-bit compact-encoding-table index,
569 // for which 0..126 references the global common-encodings table,
570 // and 127..255 references a local per-second-level-page table.
571 // First we try the compact format and determine how many entries fit.
572 // If more entries fit in the regular format, we use that.
573 for (size_t i = 0; i < cuEntries.size();) {
574 secondLevelPages.emplace_back();
575 SecondLevelPage &page = secondLevelPages.back();
576 page.entryIndex = i;
577 uint64_t functionAddressMax =
578 cuEntries[i].functionAddress + COMPRESSED_ENTRY_FUNC_OFFSET_MASK;
579 size_t n = commonEncodings.size();
580 size_t wordsRemaining =
581 SECOND_LEVEL_PAGE_WORDS -
582 sizeof(unwind_info_compressed_second_level_page_header) /
583 sizeof(uint32_t);
584 while (wordsRemaining >= 1 && i < cuEntries.size()) {
585 const CompactUnwindEntry *cuPtr = &cuEntries[i];
586 if (cuPtr->functionAddress >= functionAddressMax)
587 break;
588 if (commonEncodingIndexes.count(Val: cuPtr->encoding) ||
589 page.localEncodingIndexes.count(Val: cuPtr->encoding)) {
590 i++;
591 wordsRemaining--;
592 } else if (wordsRemaining >= 2 && n < COMPACT_ENCODINGS_MAX) {
593 page.localEncodings.emplace_back(args: cuPtr->encoding);
594 page.localEncodingIndexes[cuPtr->encoding] = n++;
595 i++;
596 wordsRemaining -= 2;
597 } else {
598 break;
599 }
600 }
601 page.entryCount = i - page.entryIndex;
602
603 // If this is not the final page, see if it's possible to fit more entries
604 // by using the regular format. This can happen when there are many unique
605 // encodings, and we saturated the local encoding table early.
606 if (i < cuEntries.size() &&
607 page.entryCount < REGULAR_SECOND_LEVEL_ENTRIES_MAX) {
608 page.kind = UNWIND_SECOND_LEVEL_REGULAR;
609 page.entryCount = std::min(REGULAR_SECOND_LEVEL_ENTRIES_MAX,
610 b: cuEntries.size() - page.entryIndex);
611 i = page.entryIndex + page.entryCount;
612 } else {
613 page.kind = UNWIND_SECOND_LEVEL_COMPRESSED;
614 }
615 }
616
617 for (size_t i = 0; i < cuEntries.size(); ++i) {
618 lsdaIndex[i] = entriesWithLsda.size();
619 if (cuEntries[i].lsda)
620 entriesWithLsda.push_back(x: i);
621 }
622
623 // compute size of __TEXT,__unwind_info section
624 level2PagesOffset = sizeof(unwind_info_section_header) +
625 commonEncodings.size() * sizeof(uint32_t) +
626 personalities.size() * sizeof(uint32_t) +
627 // The extra second-level-page entry is for the sentinel
628 (secondLevelPages.size() + 1) *
629 sizeof(unwind_info_section_header_index_entry) +
630 entriesWithLsda.size() *
631 sizeof(unwind_info_section_header_lsda_index_entry);
632 unwindInfoSize =
633 level2PagesOffset + secondLevelPages.size() * SECOND_LEVEL_PAGE_BYTES;
634}
635
636// All inputs are relocated and output addresses are known, so write!
637
638void UnwindInfoSectionImpl::writeTo(uint8_t *buf) const {
639 assert(!cuEntries.empty() && "call only if there is unwind info");
640
641 // section header
642 auto *uip = reinterpret_cast<unwind_info_section_header *>(buf);
643 uip->version = 1;
644 uip->commonEncodingsArraySectionOffset = sizeof(unwind_info_section_header);
645 uip->commonEncodingsArrayCount = commonEncodings.size();
646 uip->personalityArraySectionOffset =
647 uip->commonEncodingsArraySectionOffset +
648 (uip->commonEncodingsArrayCount * sizeof(uint32_t));
649 uip->personalityArrayCount = personalities.size();
650 uip->indexSectionOffset = uip->personalityArraySectionOffset +
651 (uip->personalityArrayCount * sizeof(uint32_t));
652 uip->indexCount = secondLevelPages.size() + 1;
653
654 // Common encodings
655 auto *i32p = reinterpret_cast<uint32_t *>(&uip[1]);
656 for (const auto &encoding : commonEncodings)
657 *i32p++ = encoding.first;
658
659 // Personalities
660 for (const Symbol *personality : personalities)
661 *i32p++ = getPersonalityGotVA(s: personality) - in.header->addr;
662
663 // FIXME: LD64 checks and warns aboutgaps or overlapse in cuEntries address
664 // ranges. We should do the same too
665
666 // Level-1 index
667 uint32_t lsdaOffset =
668 uip->indexSectionOffset +
669 uip->indexCount * sizeof(unwind_info_section_header_index_entry);
670 uint64_t l2PagesOffset = level2PagesOffset;
671 auto *iep = reinterpret_cast<unwind_info_section_header_index_entry *>(i32p);
672 for (const SecondLevelPage &page : secondLevelPages) {
673 size_t idx = page.entryIndex;
674 iep->functionOffset = cuEntries[idx].functionAddress - in.header->addr;
675 iep->secondLevelPagesSectionOffset = l2PagesOffset;
676 iep->lsdaIndexArraySectionOffset =
677 lsdaOffset + lsdaIndex.lookup(Val: idx) *
678 sizeof(unwind_info_section_header_lsda_index_entry);
679 iep++;
680 l2PagesOffset += SECOND_LEVEL_PAGE_BYTES;
681 }
682 // Level-1 sentinel
683 // XXX(vyng): Note that LD64 adds +1 here.
684 // Unsure whether it's a bug or it's their workaround for something else.
685 // See comments from https://reviews.llvm.org/D138320.
686 iep->functionOffset = cueEndBoundary - in.header->addr;
687 iep->secondLevelPagesSectionOffset = 0;
688 iep->lsdaIndexArraySectionOffset =
689 lsdaOffset + entriesWithLsda.size() *
690 sizeof(unwind_info_section_header_lsda_index_entry);
691 iep++;
692
693 // LSDAs
694 auto *lep =
695 reinterpret_cast<unwind_info_section_header_lsda_index_entry *>(iep);
696 for (size_t idx : entriesWithLsda) {
697 const CompactUnwindEntry &cu = cuEntries[idx];
698 lep->lsdaOffset = cu.lsda->getVA(/*off=*/0) - in.header->addr;
699 lep->functionOffset = cu.functionAddress - in.header->addr;
700 lep++;
701 }
702
703 // Level-2 pages
704 auto *pp = reinterpret_cast<uint32_t *>(lep);
705 for (const SecondLevelPage &page : secondLevelPages) {
706 if (page.kind == UNWIND_SECOND_LEVEL_COMPRESSED) {
707 uintptr_t functionAddressBase =
708 cuEntries[page.entryIndex].functionAddress;
709 auto *p2p =
710 reinterpret_cast<unwind_info_compressed_second_level_page_header *>(
711 pp);
712 p2p->kind = page.kind;
713 p2p->entryPageOffset =
714 sizeof(unwind_info_compressed_second_level_page_header);
715 p2p->entryCount = page.entryCount;
716 p2p->encodingsPageOffset =
717 p2p->entryPageOffset + p2p->entryCount * sizeof(uint32_t);
718 p2p->encodingsCount = page.localEncodings.size();
719 auto *ep = reinterpret_cast<uint32_t *>(&p2p[1]);
720 for (size_t i = 0; i < page.entryCount; i++) {
721 const CompactUnwindEntry &cue = cuEntries[page.entryIndex + i];
722 auto it = commonEncodingIndexes.find(Val: cue.encoding);
723 if (it == commonEncodingIndexes.end())
724 it = page.localEncodingIndexes.find(Val: cue.encoding);
725 *ep++ = (it->second << COMPRESSED_ENTRY_FUNC_OFFSET_BITS) |
726 (cue.functionAddress - functionAddressBase);
727 }
728 if (!page.localEncodings.empty())
729 memcpy(dest: ep, src: page.localEncodings.data(),
730 n: page.localEncodings.size() * sizeof(uint32_t));
731 } else {
732 auto *p2p =
733 reinterpret_cast<unwind_info_regular_second_level_page_header *>(pp);
734 p2p->kind = page.kind;
735 p2p->entryPageOffset =
736 sizeof(unwind_info_regular_second_level_page_header);
737 p2p->entryCount = page.entryCount;
738 auto *ep = reinterpret_cast<uint32_t *>(&p2p[1]);
739 for (size_t i = 0; i < page.entryCount; i++) {
740 const CompactUnwindEntry &cue = cuEntries[page.entryIndex + i];
741 *ep++ = cue.functionAddress;
742 *ep++ = cue.encoding;
743 }
744 }
745 pp += SECOND_LEVEL_PAGE_WORDS;
746 }
747}
748
749UnwindInfoSection *macho::makeUnwindInfoSection() {
750 return make<UnwindInfoSectionImpl>();
751}
752