| //===- UnwindInfoSection.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 "UnwindInfoSection.h" | |
| #include "InputSection.h" | |
| #include "Layout.h" | |
| #include "OutputSection.h" | |
| #include "OutputSegment.h" | |
| #include "SymbolTable.h" | |
| #include "Symbols.h" | |
| #include "SyntheticSections.h" | |
| #include "Target.h" | |
| #include "lld/Common/ErrorHandler.h" | |
| #include "lld/Common/Memory.h" | |
| #include "llvm/ADT/DenseMap.h" | |
| #include "llvm/ADT/STLExtras.h" | |
| #include "llvm/BinaryFormat/MachO.h" | |
| #include "llvm/Support/Parallel.h" | |
| #include "mach-o/compact_unwind_encoding.h" | |
| #include <numeric> | |
| using namespace llvm; | |
| using namespace llvm::MachO; | |
| using namespace llvm::support::endian; | |
| using namespace lld; | |
| using namespace lld::macho; | |
| #define COMMON_ENCODINGS_MAX 127 | |
| #define COMPACT_ENCODINGS_MAX 256 | |
| #define SECOND_LEVEL_PAGE_BYTES 4096 | |
| #define SECOND_LEVEL_PAGE_WORDS (SECOND_LEVEL_PAGE_BYTES / sizeof(uint32_t)) | |
| #define REGULAR_SECOND_LEVEL_ENTRIES_MAX \ | |
| ((SECOND_LEVEL_PAGE_BYTES - \ | |
| sizeof(unwind_info_regular_second_level_page_header)) / \ | |
| sizeof(unwind_info_regular_second_level_entry)) | |
| #define COMPRESSED_SECOND_LEVEL_ENTRIES_MAX \ | |
| ((SECOND_LEVEL_PAGE_BYTES - \ | |
| sizeof(unwind_info_compressed_second_level_page_header)) / \ | |
| sizeof(uint32_t)) | |
| #define COMPRESSED_ENTRY_FUNC_OFFSET_BITS 24 | |
| #define COMPRESSED_ENTRY_FUNC_OFFSET_MASK \ | |
| UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(~0) | |
| static_assert(static_cast<uint32_t>(UNWIND_X86_64_DWARF_SECTION_OFFSET) == | |
| static_cast<uint32_t>(UNWIND_ARM64_DWARF_SECTION_OFFSET) && | |
| static_cast<uint32_t>(UNWIND_X86_64_DWARF_SECTION_OFFSET) == | |
| static_cast<uint32_t>(UNWIND_X86_DWARF_SECTION_OFFSET)); | |
| constexpr uint64_t DWARF_SECTION_OFFSET = UNWIND_X86_64_DWARF_SECTION_OFFSET; | |
| // Compact Unwind format is a Mach-O evolution of DWARF Unwind that | |
| // optimizes space and exception-time lookup. Most DWARF unwind | |
| // entries can be replaced with Compact Unwind entries, but the ones | |
| // that cannot are retained in DWARF form. | |
| // | |
| // This comment will address macro-level organization of the pre-link | |
| // and post-link compact unwind tables. For micro-level organization | |
| // pertaining to the bitfield layout of the 32-bit compact unwind | |
| // entries, see libunwind/include/mach-o/compact_unwind_encoding.h | |
| // | |
| // Important clarifying factoids: | |
| // | |
| // * __LD,__compact_unwind is the compact unwind format for compiler | |
| // output and linker input. It is never a final output. It could be | |
| // an intermediate output with the `-r` option which retains relocs. | |
| // | |
| // * __TEXT,__unwind_info is the compact unwind format for final | |
| // linker output. It is never an input. | |
| // | |
| // * __TEXT,__eh_frame is the DWARF format for both linker input and output. | |
| // | |
| // * __TEXT,__unwind_info entries are divided into 4 KiB pages (2nd | |
| // level) by ascending address, and the pages are referenced by an | |
| // index (1st level) in the section header. | |
| // | |
| // * Following the headers in __TEXT,__unwind_info, the bulk of the | |
| // section contains a vector of compact unwind entries | |
| // `{functionOffset, encoding}` sorted by ascending `functionOffset`. | |
| // Adjacent entries with the same encoding can be folded to great | |
| // advantage, achieving a 3-order-of-magnitude reduction in the | |
| // number of entries. | |
| // | |
| // Refer to the definition of unwind_info_section_header in | |
| // compact_unwind_encoding.h for an overview of the format we are encoding | |
| // here. | |
| // TODO(gkm): how do we align the 2nd-level pages? | |
| // The various fields in the on-disk representation of each compact unwind | |
| // entry. | |
| #define FOR_EACH_CU_FIELD(DO) \ | |
| DO(Ptr, functionAddress) \ | |
| DO(uint32_t, functionLength) \ | |
| DO(compact_unwind_encoding_t, encoding) \ | |
| DO(Ptr, personality) \ | |
| DO(Ptr, lsda) | |
| CREATE_LAYOUT_CLASS(CompactUnwind, FOR_EACH_CU_FIELD); | |
| #undef FOR_EACH_CU_FIELD | |
| // LLD's internal representation of a compact unwind entry. | |
| struct CompactUnwindEntry { | |
| uint64_t functionAddress; | |
| uint32_t functionLength; | |
| compact_unwind_encoding_t encoding; | |
| Symbol *personality; | |
| InputSection *lsda; | |
| }; | |
| using EncodingMap = DenseMap<compact_unwind_encoding_t, size_t>; | |
| struct SecondLevelPage { | |
| uint32_t kind; | |
| size_t entryIndex; | |
| size_t entryCount; | |
| size_t byteCount; | |
| std::vector<compact_unwind_encoding_t> localEncodings; | |
| EncodingMap localEncodingIndexes; | |
| }; | |
| // UnwindInfoSectionImpl allows us to avoid cluttering our header file with a | |
| // lengthy definition of UnwindInfoSection. | |
| class UnwindInfoSectionImpl final : public UnwindInfoSection { | |
| public: | |
| UnwindInfoSectionImpl() : cuLayout(target->wordSize) {} | |
| uint64_t getSize() const override { return unwindInfoSize; } | |
| void prepare() override; | |
| void finalize() override; | |
| void writeTo(uint8_t *buf) const override; | |
| private: | |
| void prepareRelocations(ConcatInputSection *); | |
| void relocateCompactUnwind(std::vector<CompactUnwindEntry> &); | |
| void encodePersonalities(); | |
| Symbol *canonicalizePersonality(Symbol *); | |
| uint64_t unwindInfoSize = 0; | |
| SmallVector<decltype(symbols)::value_type, 0> symbolsVec; | |
| CompactUnwindLayout cuLayout; | |
| std::vector<std::pair<compact_unwind_encoding_t, size_t>> commonEncodings; | |
| EncodingMap commonEncodingIndexes; | |
| // The entries here will be in the same order as their originating symbols | |
| // in symbolsVec. | |
| std::vector<CompactUnwindEntry> cuEntries; | |
| std::vector<Symbol *> personalities; | |
| SmallDenseMap<std::pair<InputSection *, uint64_t /* addend */>, Symbol *> | |
| personalityTable; | |
| // Indices into cuEntries for CUEs with a non-null LSDA. | |
| std::vector<size_t> entriesWithLsda; | |
| // Map of cuEntries index to an index within the LSDA array. | |
| DenseMap<size_t, uint32_t> lsdaIndex; | |
| std::vector<SecondLevelPage> secondLevelPages; | |
| uint64_t level2PagesOffset = 0; | |
| // The highest-address function plus its size. The unwinder needs this to | |
| // determine the address range that is covered by unwind info. | |
| uint64_t cueEndBoundary = 0; | |
| }; | |
| UnwindInfoSection::UnwindInfoSection() | |
| : SyntheticSection(segment_names::text, section_names::unwindInfo) { | |
| align = 4; | |
| } | |
| // Record function symbols that may need entries emitted in __unwind_info, which | |
| // stores unwind data for address ranges. | |
| // | |
| // Note that if several adjacent functions have the same unwind encoding and | |
| // personality function and no LSDA, they share one unwind entry. For this to | |
| // work, functions without unwind info need explicit "no unwind info" unwind | |
| // entries -- else the unwinder would think they have the unwind info of the | |
| // closest function with unwind info right before in the image. Thus, we add | |
| // function symbols for each unique address regardless of whether they have | |
| // associated unwind info. | |
| void UnwindInfoSection::addSymbol(const Defined *d) { | |
| if (d->unwindEntry()) | |
| allEntriesAreOmitted = false; | |
| // We don't yet know the final output address of this symbol, but we know that | |
| // they are uniquely determined by a combination of the isec and value, so | |
| // we use that as the key here. | |
| auto p = symbols.insert({{d->isec(), d->value}, d}); | |
| // If we have multiple symbols at the same address, only one of them can have | |
| // an associated unwind entry. | |
| if (!p.second && d->unwindEntry()) { | |
| assert(p.first->second == d || !p.first->second->unwindEntry()); | |
| p.first->second = d; | |
| } | |
| } | |
| void UnwindInfoSectionImpl::prepare() { | |
| // This iteration needs to be deterministic, since prepareRelocations may add | |
| // entries to the GOT. Hence the use of a MapVector for | |
| // UnwindInfoSection::symbols. | |
| for (const Defined *d : make_second_range(symbols)) | |
| if (d->unwindEntry()) { | |
| if (d->unwindEntry()->getName() == section_names::compactUnwind) { | |
| prepareRelocations(d->unwindEntry()); | |
| } else { | |
| // We don't have to add entries to the GOT here because FDEs have | |
| // explicit GOT relocations, so Writer::scanRelocations() will add those | |
| // GOT entries. However, we still need to canonicalize the personality | |
| // pointers (like prepareRelocations() does for CU entries) in order | |
| // to avoid overflowing the 3-personality limit. | |
| FDE &fde = cast<ObjFile>(d->getFile())->fdes[d->unwindEntry()]; | |
| fde.personality = canonicalizePersonality(fde.personality); | |
| // If ICF folded the LSDA, point at the surviving copy. | |
| if (fde.lsda) | |
| fde.lsda = fde.lsda->canonical(); | |
| } | |
| } | |
| } | |
| // arm64e's unwinder expects signed personality pointers. | |
| static void addPersonalityGotEntry(Symbol *s) { | |
| if (config->arch() == AK_arm64e) | |
| in.authGot->addEntry(s); | |
| else | |
| in.got->addEntry(s); | |
| } | |
| static bool hasPersonalityGotEntry(const Symbol *s) { | |
| return config->arch() == AK_arm64e ? in.authGot->contains(s) : s->isInGot(); | |
| } | |
| static uint64_t getPersonalityGotVA(const Symbol *s) { | |
| return config->arch() == AK_arm64e ? in.authGot->getVA(s) : s->getGotVA(); | |
| } | |
| // Compact unwind relocations have different semantics, so we handle them in a | |
| // separate code path from regular relocations. First, we do not wish to add | |
| // rebase opcodes for __LD,__compact_unwind, because that section doesn't | |
| // actually end up in the final binary. Second, personality pointers always | |
| // reside in the GOT and must be treated specially. | |
| void UnwindInfoSectionImpl::prepareRelocations(ConcatInputSection *isec) { | |
| assert(!isec->shouldOmitFromOutput() && | |
| "__compact_unwind section should not be omitted"); | |
| // FIXME: Make this skip relocations for CompactUnwindEntries that | |
| // point to dead-stripped functions. That might save some amount of | |
| // work. But since there are usually just few personality functions | |
| // that are referenced from many places, at least some of them likely | |
| // live, it wouldn't reduce number of got entries. | |
| for (size_t i = 0; i < isec->relocs.size(); ++i) { | |
| Relocation &r = isec->relocs[i]; | |
| assert(target->hasAttr(r.type, RelocAttrBits::UNSIGNED)); | |
| // Since compact unwind sections aren't part of the inputSections vector, | |
| // they don't get canonicalized by scanRelocations(), so we have to do the | |
| // canonicalization here. | |
| if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) | |
| r.referent = referentIsec->canonical(); | |
| // Functions and LSDA entries always reside in the same object file as the | |
| // compact unwind entries that references them, and thus appear as section | |
| // relocs. There is no need to prepare them. We only prepare relocs for | |
| // personality functions. | |
| if (r.offset != cuLayout.personalityOffset) | |
| continue; | |
| if (auto *s = r.referent.dyn_cast<Symbol *>()) { | |
| // Personality functions are nearly always system-defined (e.g., | |
| // ___gxx_personality_v0 for C++) and relocated as dylib symbols. When an | |
| // application provides its own personality function, it might be | |
| // referenced by an extern Defined symbol reloc, or a local section reloc. | |
| if (auto *defined = dyn_cast<Defined>(s)) { | |
| // XXX(vyng) This is a special case for handling duplicate personality | |
| // symbols. Note that LD64's behavior is a bit different and it is | |
| // inconsistent with how symbol resolution usually work | |
| // | |
| // So we've decided not to follow it. Instead, simply pick the symbol | |
| // with the same name from the symbol table to replace the local one. | |
| // | |
| // (See discussions/alternatives already considered on D107533) | |
| if (!defined->isExternal()) | |
| if (Symbol *sym = symtab->find(defined->getName())) | |
| if (!sym->isLazy()) | |
| r.referent = s = sym; | |
| } | |
| if (auto *undefined = dyn_cast<Undefined>(s)) { | |
| treatUndefinedSymbol(*undefined, isec, r.offset); | |
| // treatUndefinedSymbol() can replace s with a DylibSymbol; re-check. | |
| if (isa<Undefined>(s)) | |
| continue; | |
| } | |
| // Similar to canonicalizePersonality(), but we also register a GOT entry. | |
| if (auto *defined = dyn_cast<Defined>(s)) { | |
| // Check if we have created a synthetic symbol at the same address. | |
| Symbol *&personality = | |
| personalityTable[{defined->isec(), defined->value}]; | |
| if (personality == nullptr) { | |
| personality = defined; | |
| addPersonalityGotEntry(defined); | |
| } else if (personality != defined) { | |
| r.referent = personality; | |
| } | |
| continue; | |
| } | |
| assert(isa<DylibSymbol>(s)); | |
| addPersonalityGotEntry(s); | |
| continue; | |
| } | |
| if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) { | |
| assert(!isCoalescedWeak(referentIsec)); | |
| // Personality functions can be referenced via section relocations | |
| // if they live in the same object file. Create placeholder synthetic | |
| // symbols for them in the GOT. If the corresponding symbol is already | |
| // in the GOT, use that to avoid creating a duplicate entry. All GOT | |
| // entries needed by non-unwind sections will have already been added | |
| // by this point. | |
| Symbol *&s = personalityTable[{referentIsec, r.getAddend()}]; | |
| if (s == nullptr) { | |
| Defined *const *gotEntry = | |
| llvm::find_if(referentIsec->symbols, [&](Defined const *d) { | |
| return d->value == static_cast<uint64_t>(r.getAddend()) && | |
| hasPersonalityGotEntry(d); | |
| }); | |
| if (gotEntry != referentIsec->symbols.end()) { | |
| s = *gotEntry; | |
| } else { | |
| // This runs after dead stripping, so the noDeadStrip argument does | |
| // not matter. | |
| s = make<Defined>("<internal>", /*file=*/nullptr, referentIsec, | |
| r.getAddend(), /*size=*/0, /*isWeakDef=*/false, | |
| /*isExternal=*/false, /*isPrivateExtern=*/false, | |
| /*includeInSymtab=*/true, | |
| /*isReferencedDynamically=*/false, | |
| /*noDeadStrip=*/false); | |
| s->used = true; | |
| addPersonalityGotEntry(s); | |
| } | |
| } | |
| r.referent = s; | |
| r.setAddend(0); | |
| } | |
| } | |
| } | |
| Symbol *UnwindInfoSectionImpl::canonicalizePersonality(Symbol *personality) { | |
| if (auto *defined = dyn_cast_or_null<Defined>(personality)) { | |
| // Check if we have created a synthetic symbol at the same address. | |
| Symbol *&synth = personalityTable[{defined->isec(), defined->value}]; | |
| if (synth == nullptr) | |
| synth = defined; | |
| else if (synth != defined) | |
| return synth; | |
| } | |
| return personality; | |
| } | |
| // We need to apply the relocations to the pre-link compact unwind section | |
| // before converting it to post-link form. There should only be absolute | |
| // relocations here: since we are not emitting the pre-link CU section, there | |
| // is no source address to make a relative location meaningful. | |
| void UnwindInfoSectionImpl::relocateCompactUnwind( | |
| std::vector<CompactUnwindEntry> &cuEntries) { | |
| parallelFor(0, symbolsVec.size(), [&](size_t i) { | |
| CompactUnwindEntry &cu = cuEntries[i]; | |
| const Defined *d = symbolsVec[i].second; | |
| cu.functionAddress = d->getVA(); | |
| if (!d->unwindEntry()) | |
| return; | |
| // If we have DWARF unwind info, create a slimmed-down CU entry that points | |
| // to it. | |
| if (d->unwindEntry()->getName() == section_names::ehFrame) { | |
| // The unwinder will look for the DWARF entry starting at the hint, | |
| // assuming the hint points to a valid CFI record start. If it | |
| // fails to find the record, it proceeds in a linear search through the | |
| // contiguous CFI records from the hint until the end of the section. | |
| // Ideally, in the case where the offset is too large to be encoded, we | |
| // would instead encode the largest possible offset to a valid CFI record, | |
| // but since we don't keep track of that, just encode zero -- the start of | |
| // the section is always the start of a CFI record. | |
| uint64_t dwarfOffsetHint = | |
| d->unwindEntry()->outSecOff <= DWARF_SECTION_OFFSET | |
| ? d->unwindEntry()->outSecOff | |
| : 0; | |
| cu.encoding = target->modeDwarfEncoding | dwarfOffsetHint; | |
| const FDE &fde = cast<ObjFile>(d->getFile())->fdes[d->unwindEntry()]; | |
| cu.functionLength = fde.funcLength; | |
| // Omit the DWARF personality from compact-unwind entry so that we | |
| // don't need to encode it. | |
| cu.personality = nullptr; | |
| cu.lsda = fde.lsda; | |
| return; | |
| } | |
| assert(d->unwindEntry()->getName() == section_names::compactUnwind); | |
| auto buf = | |
| reinterpret_cast<const uint8_t *>(d->unwindEntry()->data.data()) - | |
| target->wordSize; | |
| cu.functionLength = | |
| support::endian::read32le(buf + cuLayout.functionLengthOffset); | |
| cu.encoding = support::endian::read32le(buf + cuLayout.encodingOffset); | |
| for (const Relocation &r : d->unwindEntry()->relocs) { | |
| if (r.offset == cuLayout.personalityOffset) | |
| cu.personality = cast<Symbol *>(r.referent); | |
| else if (r.offset == cuLayout.lsdaOffset) | |
| cu.lsda = r.getReferentInputSection(); | |
| } | |
| }); | |
| } | |
| // There should only be a handful of unique personality pointers, so we can | |
| // encode them as 2-bit indices into a small array. | |
| void UnwindInfoSectionImpl::encodePersonalities() { | |
| for (CompactUnwindEntry &cu : cuEntries) { | |
| if (cu.personality == nullptr) | |
| continue; | |
| // Linear search is fast enough for a small array. | |
| auto it = find(personalities, cu.personality); | |
| uint32_t personalityIndex; // 1-based index | |
| if (it != personalities.end()) { | |
| personalityIndex = std::distance(personalities.begin(), it) + 1; | |
| } else { | |
| personalities.push_back(cu.personality); | |
| personalityIndex = personalities.size(); | |
| } | |
| cu.encoding |= | |
| personalityIndex << llvm::countr_zero( | |
| static_cast<compact_unwind_encoding_t>(UNWIND_PERSONALITY_MASK)); | |
| } | |
| if (personalities.size() > 3) | |
| error("too many personalities (" + Twine(personalities.size()) + | |
| ") for compact unwind to encode"); | |
| } | |
| static bool canFoldEncoding(compact_unwind_encoding_t encoding) { | |
| // From compact_unwind_encoding.h: | |
| // UNWIND_X86_64_MODE_STACK_IND: | |
| // A "frameless" (RBP not used as frame pointer) function large constant | |
| // stack size. This case is like the previous, except the stack size is too | |
| // large to encode in the compact unwind encoding. Instead it requires that | |
| // the function contains "subq $nnnnnnnn,RSP" in its prolog. The compact | |
| // encoding contains the offset to the nnnnnnnn value in the function in | |
| // UNWIND_X86_64_FRAMELESS_STACK_SIZE. | |
| // Since this means the unwinder has to look at the `subq` in the function | |
| // of the unwind info's unwind address, two functions that have identical | |
| // unwind info can't be folded if it's using this encoding since both | |
| // entries need unique addresses. | |
| static_assert(static_cast<uint32_t>(UNWIND_X86_64_MODE_STACK_IND) == | |
| static_cast<uint32_t>(UNWIND_X86_MODE_STACK_IND)); | |
| if ((target->cpuType == CPU_TYPE_X86_64 || target->cpuType == CPU_TYPE_X86) && | |
| (encoding & UNWIND_MODE_MASK) == UNWIND_X86_64_MODE_STACK_IND) { | |
| // FIXME: Consider passing in the two function addresses and getting | |
| // their two stack sizes off the `subq` and only returning false if they're | |
| // actually different. | |
| return false; | |
| } | |
| return true; | |
| } | |
| // Scan the __LD,__compact_unwind entries and compute the space needs of | |
| // __TEXT,__unwind_info and __TEXT,__eh_frame. | |
| void UnwindInfoSectionImpl::finalize() { | |
| if (symbols.empty()) | |
| return; | |
| // At this point, the address space for __TEXT,__text has been | |
| // assigned, so we can relocate the __LD,__compact_unwind entries | |
| // into a temporary buffer. Relocation is necessary in order to sort | |
| // the CU entries by function address. Sorting is necessary so that | |
| // we can fold adjacent CU entries with identical encoding+personality | |
| // and without any LSDA. Folding is necessary because it reduces the | |
| // number of CU entries by as much as 3 orders of magnitude! | |
| cuEntries.resize(symbols.size()); | |
| // The "map" part of the symbols MapVector was only needed for deduplication | |
| // in addSymbol(). Now that we are done adding, move the contents to a plain | |
| // std::vector for indexed access. | |
| symbolsVec = symbols.takeVector(); | |
| relocateCompactUnwind(cuEntries); | |
| // Sort the entries by address. | |
| llvm::sort(cuEntries, [&](auto &a, auto &b) { | |
| return a.functionAddress < b.functionAddress; | |
| }); | |
| // Record the ending boundary before we fold the entries. | |
| cueEndBoundary = | |
| cuEntries.back().functionAddress + cuEntries.back().functionLength; | |
| // Fold adjacent entries with matching encoding+personality and without LSDA | |
| // We use three iterators to fold in-situ: | |
| // (1) `foldBegin` is the first of a potential sequence of matching entries | |
| // (2) `foldEnd` is the first non-matching entry after `foldBegin`. | |
| // The semi-open interval [ foldBegin .. foldEnd ) contains a range | |
| // entries that can be folded into a single entry and written to ... | |
| // (3) `foldWrite` | |
| auto foldWrite = cuEntries.begin(); | |
| for (auto foldBegin = cuEntries.begin(); foldBegin != cuEntries.end();) { | |
| auto foldEnd = foldBegin; | |
| // Common LSDA encodings (e.g. for C++ and Objective-C) contain offsets from | |
| // a base address. The base address is normally not contained directly in | |
| // the LSDA, and in that case, the personality function treats the starting | |
| // address of the function (which is computed by the unwinder) as the base | |
| // address and interprets the LSDA accordingly. The unwinder computes the | |
| // starting address of a function as the address associated with its CU | |
| // entry. For this reason, we cannot fold adjacent entries if they have an | |
| // LSDA, because folding would make the unwinder compute the wrong starting | |
| // address for the functions with the folded entries, which in turn would | |
| // cause the personality function to misinterpret the LSDA for those | |
| // functions. In the very rare case where the base address is encoded | |
| // directly in the LSDA, two functions at different addresses would | |
| // necessarily have different LSDAs, so their CU entries would not have been | |
| // folded anyway. | |
| while (++foldEnd != cuEntries.end() && | |
| foldBegin->encoding == foldEnd->encoding && !foldBegin->lsda && | |
| !foldEnd->lsda && | |
| // If we've gotten to this point, we don't have an LSDA, which should | |
| // also imply that we don't have a personality function, since in all | |
| // likelihood a personality function needs the LSDA to do anything | |
| // useful. It can be technically valid to have a personality function | |
| // and no LSDA though (e.g. the C++ personality __gxx_personality_v0 | |
| // is just a no-op without LSDA), so we still check for personality | |
| // function equivalence to handle that case. | |
| foldBegin->personality == foldEnd->personality && | |
| canFoldEncoding(foldEnd->encoding)) | |
| ; | |
| *foldWrite++ = *foldBegin; | |
| foldBegin = foldEnd; | |
| } | |
| cuEntries.erase(foldWrite, cuEntries.end()); | |
| encodePersonalities(); | |
| // Count frequencies of the folded encodings | |
| EncodingMap encodingFrequencies; | |
| for (const CompactUnwindEntry &cu : cuEntries) | |
| encodingFrequencies[cu.encoding]++; | |
| // Make a vector of encodings, sorted by descending frequency | |
| for (const auto &frequency : encodingFrequencies) | |
| commonEncodings.emplace_back(frequency); | |
| llvm::sort(commonEncodings, | |
| [](const std::pair<compact_unwind_encoding_t, size_t> &a, | |
| const std::pair<compact_unwind_encoding_t, size_t> &b) { | |
| // When frequencies match, secondarily sort on encoding | |
| // to maintain parity with validate-unwind-info.py | |
| return std::tie(a.second, a.first) > std::tie(b.second, b.first); | |
| }); | |
| // Truncate the vector to 127 elements. | |
| // Common encoding indexes are limited to 0..126, while encoding | |
| // indexes 127..255 are local to each second-level page | |
| if (commonEncodings.size() > COMMON_ENCODINGS_MAX) | |
| commonEncodings.resize(COMMON_ENCODINGS_MAX); | |
| // Create a map from encoding to common-encoding-table index | |
| for (size_t i = 0; i < commonEncodings.size(); i++) | |
| commonEncodingIndexes[commonEncodings[i].first] = i; | |
| // Split folded encodings into pages, where each page is limited by ... | |
| // (a) 4 KiB capacity | |
| // (b) 24-bit difference between first & final function address | |
| // (c) 8-bit compact-encoding-table index, | |
| // for which 0..126 references the global common-encodings table, | |
| // and 127..255 references a local per-second-level-page table. | |
| // First we try the compact format and determine how many entries fit. | |
| // If more entries fit in the regular format, we use that. | |
| for (size_t i = 0; i < cuEntries.size();) { | |
| secondLevelPages.emplace_back(); | |
| SecondLevelPage &page = secondLevelPages.back(); | |
| page.entryIndex = i; | |
| uint64_t functionAddressMax = | |
| cuEntries[i].functionAddress + COMPRESSED_ENTRY_FUNC_OFFSET_MASK; | |
| size_t n = commonEncodings.size(); | |
| size_t wordsRemaining = | |
| SECOND_LEVEL_PAGE_WORDS - | |
| sizeof(unwind_info_compressed_second_level_page_header) / | |
| sizeof(uint32_t); | |
| while (wordsRemaining >= 1 && i < cuEntries.size()) { | |
| const CompactUnwindEntry *cuPtr = &cuEntries[i]; | |
| if (cuPtr->functionAddress >= functionAddressMax) | |
| break; | |
| if (commonEncodingIndexes.count(cuPtr->encoding) || | |
| page.localEncodingIndexes.count(cuPtr->encoding)) { | |
| i++; | |
| wordsRemaining--; | |
| } else if (wordsRemaining >= 2 && n < COMPACT_ENCODINGS_MAX) { | |
| page.localEncodings.emplace_back(cuPtr->encoding); | |
| page.localEncodingIndexes[cuPtr->encoding] = n++; | |
| i++; | |
| wordsRemaining -= 2; | |
| } else { | |
| break; | |
| } | |
| } | |
| page.entryCount = i - page.entryIndex; | |
| // If this is not the final page, see if it's possible to fit more entries | |
| // by using the regular format. This can happen when there are many unique | |
| // encodings, and we saturated the local encoding table early. | |
| if (i < cuEntries.size() && | |
| page.entryCount < REGULAR_SECOND_LEVEL_ENTRIES_MAX) { | |
| page.kind = UNWIND_SECOND_LEVEL_REGULAR; | |
| page.entryCount = std::min(REGULAR_SECOND_LEVEL_ENTRIES_MAX, | |
| cuEntries.size() - page.entryIndex); | |
| i = page.entryIndex + page.entryCount; | |
| } else { | |
| page.kind = UNWIND_SECOND_LEVEL_COMPRESSED; | |
| } | |
| } | |
| for (size_t i = 0; i < cuEntries.size(); ++i) { | |
| lsdaIndex[i] = entriesWithLsda.size(); | |
| if (cuEntries[i].lsda) | |
| entriesWithLsda.push_back(i); | |
| } | |
| // compute size of __TEXT,__unwind_info section | |
| level2PagesOffset = sizeof(unwind_info_section_header) + | |
| commonEncodings.size() * sizeof(uint32_t) + | |
| personalities.size() * sizeof(uint32_t) + | |
| // The extra second-level-page entry is for the sentinel | |
| (secondLevelPages.size() + 1) * | |
| sizeof(unwind_info_section_header_index_entry) + | |
| entriesWithLsda.size() * | |
| sizeof(unwind_info_section_header_lsda_index_entry); | |
| unwindInfoSize = | |
| level2PagesOffset + secondLevelPages.size() * SECOND_LEVEL_PAGE_BYTES; | |
| } | |
| // All inputs are relocated and output addresses are known, so write! | |
| void UnwindInfoSectionImpl::writeTo(uint8_t *buf) const { | |
| assert(!cuEntries.empty() && "call only if there is unwind info"); | |
| // section header | |
| auto *uip = reinterpret_cast<unwind_info_section_header *>(buf); | |
| uip->version = 1; | |
| uip->commonEncodingsArraySectionOffset = sizeof(unwind_info_section_header); | |
| uip->commonEncodingsArrayCount = commonEncodings.size(); | |
| uip->personalityArraySectionOffset = | |
| uip->commonEncodingsArraySectionOffset + | |
| (uip->commonEncodingsArrayCount * sizeof(uint32_t)); | |
| uip->personalityArrayCount = personalities.size(); | |
| uip->indexSectionOffset = uip->personalityArraySectionOffset + | |
| (uip->personalityArrayCount * sizeof(uint32_t)); | |
| uip->indexCount = secondLevelPages.size() + 1; | |
| // Common encodings | |
| auto *i32p = reinterpret_cast<uint32_t *>(&uip[1]); | |
| for (const auto &encoding : commonEncodings) | |
| *i32p++ = encoding.first; | |
| // Personalities | |
| for (const Symbol *personality : personalities) | |
| *i32p++ = getPersonalityGotVA(personality) - in.header->addr; | |
| // FIXME: LD64 checks and warns aboutgaps or overlapse in cuEntries address | |
| // ranges. We should do the same too | |
| // Level-1 index | |
| uint32_t lsdaOffset = | |
| uip->indexSectionOffset + | |
| uip->indexCount * sizeof(unwind_info_section_header_index_entry); | |
| uint64_t l2PagesOffset = level2PagesOffset; | |
| auto *iep = reinterpret_cast<unwind_info_section_header_index_entry *>(i32p); | |
| for (const SecondLevelPage &page : secondLevelPages) { | |
| size_t idx = page.entryIndex; | |
| iep->functionOffset = cuEntries[idx].functionAddress - in.header->addr; | |
| iep->secondLevelPagesSectionOffset = l2PagesOffset; | |
| iep->lsdaIndexArraySectionOffset = | |
| lsdaOffset + lsdaIndex.lookup(idx) * | |
| sizeof(unwind_info_section_header_lsda_index_entry); | |
| iep++; | |
| l2PagesOffset += SECOND_LEVEL_PAGE_BYTES; | |
| } | |
| // Level-1 sentinel | |
| // XXX(vyng): Note that LD64 adds +1 here. | |
| // Unsure whether it's a bug or it's their workaround for something else. | |
| // See comments from https://reviews.llvm.org/D138320. | |
| iep->functionOffset = cueEndBoundary - in.header->addr; | |
| iep->secondLevelPagesSectionOffset = 0; | |
| iep->lsdaIndexArraySectionOffset = | |
| lsdaOffset + entriesWithLsda.size() * | |
| sizeof(unwind_info_section_header_lsda_index_entry); | |
| iep++; | |
| // LSDAs | |
| auto *lep = | |
| reinterpret_cast<unwind_info_section_header_lsda_index_entry *>(iep); | |
| for (size_t idx : entriesWithLsda) { | |
| const CompactUnwindEntry &cu = cuEntries[idx]; | |
| lep->lsdaOffset = cu.lsda->getVA(/*off=*/0) - in.header->addr; | |
| lep->functionOffset = cu.functionAddress - in.header->addr; | |
| lep++; | |
| } | |
| // Level-2 pages | |
| auto *pp = reinterpret_cast<uint32_t *>(lep); | |
| for (const SecondLevelPage &page : secondLevelPages) { | |
| if (page.kind == UNWIND_SECOND_LEVEL_COMPRESSED) { | |
| uintptr_t functionAddressBase = | |
| cuEntries[page.entryIndex].functionAddress; | |
| auto *p2p = | |
| reinterpret_cast<unwind_info_compressed_second_level_page_header *>( | |
| pp); | |
| p2p->kind = page.kind; | |
| p2p->entryPageOffset = | |
| sizeof(unwind_info_compressed_second_level_page_header); | |
| p2p->entryCount = page.entryCount; | |
| p2p->encodingsPageOffset = | |
| p2p->entryPageOffset + p2p->entryCount * sizeof(uint32_t); | |
| p2p->encodingsCount = page.localEncodings.size(); | |
| auto *ep = reinterpret_cast<uint32_t *>(&p2p[1]); | |
| for (size_t i = 0; i < page.entryCount; i++) { | |
| const CompactUnwindEntry &cue = cuEntries[page.entryIndex + i]; | |
| auto it = commonEncodingIndexes.find(cue.encoding); | |
| if (it == commonEncodingIndexes.end()) | |
| it = page.localEncodingIndexes.find(cue.encoding); | |
| *ep++ = (it->second << COMPRESSED_ENTRY_FUNC_OFFSET_BITS) | | |
| (cue.functionAddress - functionAddressBase); | |
| } | |
| if (!page.localEncodings.empty()) | |
| memcpy(ep, page.localEncodings.data(), | |
| page.localEncodings.size() * sizeof(uint32_t)); | |
| } else { | |
| auto *p2p = | |
| reinterpret_cast<unwind_info_regular_second_level_page_header *>(pp); | |
| p2p->kind = page.kind; | |
| p2p->entryPageOffset = | |
| sizeof(unwind_info_regular_second_level_page_header); | |
| p2p->entryCount = page.entryCount; | |
| auto *ep = reinterpret_cast<uint32_t *>(&p2p[1]); | |
| for (size_t i = 0; i < page.entryCount; i++) { | |
| const CompactUnwindEntry &cue = cuEntries[page.entryIndex + i]; | |
| *ep++ = cue.functionAddress; | |
| *ep++ = cue.encoding; | |
| } | |
| } | |
| pp += SECOND_LEVEL_PAGE_WORDS; | |
| } | |
| } | |
| UnwindInfoSection *macho::makeUnwindInfoSection() { | |
| return make<UnwindInfoSectionImpl>(); | |
| } |