diff --git a/lld/MachO/UnwindInfoSection.h b/lld/MachO/UnwindInfoSection.h --- a/lld/MachO/UnwindInfoSection.h +++ b/lld/MachO/UnwindInfoSection.h @@ -14,6 +14,7 @@ #include "mach-o/compact_unwind_encoding.h" #include "llvm/ADT/DenseMap.h" +#include #include @@ -38,6 +39,27 @@ namespace lld { namespace macho { +// This is a wrapper class that is otherwise like size_t, but has a +// default constructor that yields ~0 rather than 0. I need it so that +// lookup() of absent keys from DenseMap<..., size_tx> return ~0, +// since 0 is a valid value. +// TODO: If someone knows nicer way to accomplish this, please advise. +// A simpler alternative: bias all values by 1. + +struct size_tx { + size_tx() : x(~0L) {} + size_tx(size_t s) { x = s; } + size_tx(int i) { x = i; } + operator size_t() { return x; } + size_tx operator++(int) { return static_cast(x++); } + size_t x; +}; +inline bool operator==(const size_tx a, const size_tx b) { return a.x == b.x; } +inline bool operator!=(const size_tx a, const size_tx b) { return a.x != b.x; } +inline bool operator<(const size_tx a, const size_t b) { return a.x < b; } +inline bool operator<(const size_tx a, const size_tx b) { return a.x < b.x; } +inline bool operator>(const size_tx a, const size_tx b) { return a.x > b.x; } + class UnwindInfoSection : public SyntheticSection { public: UnwindInfoSection(); @@ -49,20 +71,31 @@ compactUnwindSection = cuSection; } + struct secondLevelPage { + uint32_t kind; + size_t entryIndex; + size_t entryCount; + size_t byteCount; + size_t padByteCount; + std::vector localEncodings; + llvm::DenseMap localEncodingIndexes; + }; + private: - std::vector> commonEncodings; + std::vector> commonEncodings; + llvm::DenseMap commonEncodingIndexes; std::vector personalities; std::vector lsdaEntries; std::vector cuVector; std::vector cuPtrVector; - std::vector::const_iterator> - pageBounds; + std::vector secondLevelPages; MergedOutputSection *compactUnwindSection = nullptr; uint64_t level2PagesOffset = 0; uint64_t unwindInfoSize = 0; }; #define UNWIND_INFO_COMMON_ENCODINGS_MAX 127 +#define UNWIND_INFO_COMPACT_ENCODINGS_MAX 256 #define UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE 4096 #define UNWIND_INFO_REGULAR_SECOND_LEVEL_ENTRIES_MAX \ diff --git a/lld/MachO/UnwindInfoSection.cpp b/lld/MachO/UnwindInfoSection.cpp --- a/lld/MachO/UnwindInfoSection.cpp +++ b/lld/MachO/UnwindInfoSection.cpp @@ -129,18 +129,16 @@ cuPtrVector.erase(foldWrite, cuPtrVector.end()); // Count frequencies of the folded encodings - llvm::DenseMap encodingFrequencies; + llvm::DenseMap encodingFrequencies; for (auto cuPtrEntry : cuPtrVector) encodingFrequencies[cuPtrEntry->encoding]++; - if (encodingFrequencies.size() > UNWIND_INFO_COMMON_ENCODINGS_MAX) - error("TODO(gkm): handle common encodings table overflow"); - // Make a table of encodings, sorted by descending frequency + // Make a vector of encodings, sorted by descending frequency for (const auto &frequency : encodingFrequencies) commonEncodings.emplace_back(frequency); std::sort(commonEncodings.begin(), commonEncodings.end(), - [](const std::pair &a, - const std::pair &b) { + [](const std::pair &a, + const std::pair &b) { if (a.second == b.second) // When frequencies match, secondarily sort on encoding // to maintain parity with validate-unwind-info.py @@ -148,37 +146,67 @@ return a.second > b.second; }); - // Split folded encodings into pages, limited by capacity of a page - // and the 24-bit range of function offset - // - // Record the page splits as a vector of iterators on cuPtrVector - // such that successive elements form a semi-open interval. E.g., - // page X's bounds are thus: [ pageBounds[X] .. pageBounds[X+1] ) - // - // Note that pageBounds.size() is one greater than the number of - // pages, and pageBounds.back() holds the sentinel cuPtrVector.cend() - pageBounds.push_back(cuPtrVector.cbegin()); - // TODO(gkm): cut 1st page entries short to accommodate section headers ??? - CompactUnwindEntry64 cuEntryKey; - for (size_t i = 0;;) { - // Limit the search to entries that can fit within a 4 KiB page. - const auto pageBegin = pageBounds[0] + i; - const auto pageMax = - pageBounds[0] + - std::min(i + UNWIND_INFO_COMPRESSED_SECOND_LEVEL_ENTRIES_MAX, - cuPtrVector.size()); - // Exclude entries with functionOffset that would overflow 24 bits - cuEntryKey.functionAddress = (*pageBegin)->functionAddress + - UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_MASK; - const auto pageBreak = std::lower_bound( - pageBegin, pageMax, &cuEntryKey, - [](const CompactUnwindEntry64 *a, const CompactUnwindEntry64 *b) { - return a->functionAddress < b->functionAddress; - }); - pageBounds.push_back(pageBreak); - if (pageBreak == cuPtrVector.cend()) - break; - i = pageBreak - cuPtrVector.cbegin(); + // Truncate the vector to 127 elements. + // Common encoding indexes are limited to 0..126, while enconding + // indexes 127..255 are local to each second-level page + if (commonEncodings.size() > UNWIND_INFO_COMMON_ENCODINGS_MAX) + commonEncodings.resize(UNWIND_INFO_COMMON_ENCODINGS_MAX); + + // Create a map from encoding to common-encoding-table index + for (size_tx 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 < cuPtrVector.size();) { + secondLevelPages.emplace_back(); + auto &page = secondLevelPages.back(); + page.entryIndex = i; + uintptr_t functionAddressMax = + cuPtrVector[i]->functionAddress + + UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_MASK; + size_t n = commonEncodings.size(); + size_t bytesRemaining = + UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE - + sizeof(unwind_info_compressed_second_level_page_header); + while (bytesRemaining >= sizeof(uint32_t) && i < cuPtrVector.size()) { + auto *cuPtr = cuPtrVector[i]; + if (cuPtr->functionAddress >= functionAddressMax) { + break; + } else if (commonEncodingIndexes.lookup(cuPtr->encoding) != size_tx() || + page.localEncodingIndexes.lookup(cuPtr->encoding) != + size_tx()) { + i++; + bytesRemaining -= sizeof(uint32_t); + } else if (bytesRemaining >= 2 * sizeof(uint32_t) && + n < UNWIND_INFO_COMPACT_ENCODINGS_MAX) { + page.localEncodings.emplace_back(cuPtr->encoding); + page.localEncodingIndexes[cuPtr->encoding] = n++; + i++; + bytesRemaining -= 2 * sizeof(uint32_t); + } else + break; + } + page.entryCount = i - page.entryIndex; + if (i < cuPtrVector.size() && + page.entryCount < UNWIND_INFO_REGULAR_SECOND_LEVEL_ENTRIES_MAX) { + page.kind = UNWIND_SECOND_LEVEL_REGULAR; + page.entryCount = std::min(UNWIND_INFO_REGULAR_SECOND_LEVEL_ENTRIES_MAX, + cuPtrVector.size() - page.entryIndex); + i = page.entryIndex + page.entryCount; + page.padByteCount = + (UNWIND_INFO_REGULAR_SECOND_LEVEL_ENTRIES_MAX - page.entryCount) * 2 * + sizeof(uint32_t); + } else { + page.kind = UNWIND_SECOND_LEVEL_COMPRESSED; + page.padByteCount = bytesRemaining; + } } // compute size of __TEXT,__unwind_info section @@ -186,12 +214,11 @@ sizeof(unwind_info_section_header) + commonEncodings.size() * sizeof(uint32_t) + personalities.size() * sizeof(uint32_t) + - pageBounds.size() * sizeof(unwind_info_section_header_index_entry) + + (secondLevelPages.size() + 1) * + sizeof(unwind_info_section_header_index_entry) + lsdaEntries.size() * sizeof(unwind_info_section_header_lsda_index_entry); unwindInfoSize = level2PagesOffset + - (pageBounds.size() - 1) * - sizeof(unwind_info_compressed_second_level_page_header) + - cuPtrVector.size() * sizeof(uint32_t); + secondLevelPages.size() * UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE; } // All inputs are relocated and output addresses are known, so write! @@ -208,7 +235,7 @@ uip->personalityArrayCount = personalities.size(); uip->indexSectionOffset = uip->personalityArraySectionOffset + (uip->personalityArrayCount * sizeof(uint32_t)); - uip->indexCount = pageBounds.size(); + uip->indexCount = secondLevelPages.size() + 1; // Common encodings auto *i32p = reinterpret_cast(&uip[1]); @@ -225,16 +252,12 @@ uip->indexCount * sizeof(unwind_info_section_header_index_entry); uint64_t l2PagesOffset = level2PagesOffset; auto *iep = reinterpret_cast(i32p); - for (size_t i = 0; i < pageBounds.size() - 1; i++) { - iep->functionOffset = (*pageBounds[i])->functionAddress; + for (const auto &page : secondLevelPages) { + iep->functionOffset = cuPtrVector[page.entryIndex]->functionAddress; iep->secondLevelPagesSectionOffset = l2PagesOffset; iep->lsdaIndexArraySectionOffset = lsdaOffset; iep++; - // TODO(gkm): pad to 4 KiB page boundary ??? - size_t entryCount = pageBounds[i + 1] - pageBounds[i]; - uint64_t pageSize = sizeof(unwind_info_section_header_index_entry) + - entryCount * sizeof(uint32_t); - l2PagesOffset += pageSize; + l2PagesOffset += UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE; } // Level-1 sentinel const CompactUnwindEntry64 &cuEnd = cuVector.back(); @@ -251,36 +274,51 @@ lep->lsdaOffset = lsda.lsdaOffset; } - // create map from encoding to common-encoding-table index compact - // encoding entries use 7 bits to index the common-encoding table - size_t i = 0; - llvm::DenseMap commonEncodingIndexes; - for (const auto &encoding : commonEncodings) - commonEncodingIndexes[encoding.first] = i++; - // Level-2 pages - auto *p2p = - reinterpret_cast(lep); - for (size_t i = 0; i < pageBounds.size() - 1; i++) { - p2p->kind = UNWIND_SECOND_LEVEL_COMPRESSED; - p2p->entryPageOffset = - sizeof(unwind_info_compressed_second_level_page_header); - p2p->entryCount = pageBounds[i + 1] - pageBounds[i]; - p2p->encodingsPageOffset = - p2p->entryPageOffset + p2p->entryCount * sizeof(uint32_t); - p2p->encodingsCount = 0; - auto *ep = reinterpret_cast(&p2p[1]); - auto cuPtrVectorIt = pageBounds[i]; - uintptr_t functionAddressBase = (*cuPtrVectorIt)->functionAddress; - while (cuPtrVectorIt < pageBounds[i + 1]) { - const CompactUnwindEntry64 *cuep = *cuPtrVectorIt++; - size_t cueIndex = commonEncodingIndexes.lookup(cuep->encoding); - *ep++ = ((cueIndex << UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_BITS) | - (cuep->functionAddress - functionAddressBase)); + auto *ep = reinterpret_cast(lep); + for (const auto &page : secondLevelPages) { + if (page.kind == UNWIND_SECOND_LEVEL_COMPRESSED) { + uintptr_t functionAddressBase = + cuPtrVector[page.entryIndex]->functionAddress; + auto *p2p = + reinterpret_cast( + ep); + 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(); + ep = reinterpret_cast(&p2p[1]); + for (size_t i = 0; i < page.entryCount; i++) { + const CompactUnwindEntry64 *cuep = cuPtrVector[page.entryIndex + i]; + size_tx cueIndex = commonEncodingIndexes.lookup(cuep->encoding); + if (cueIndex == size_tx()) + cueIndex = page.localEncodingIndexes.lookup(cuep->encoding); + assert(cueIndex != size_tx()); + *ep++ = ((cueIndex << UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_BITS) | + (cuep->functionAddress - functionAddressBase)); + } + for (auto &encoding : page.localEncodings) + *ep++ = encoding; + } else { + auto *p2p = + reinterpret_cast(ep); + p2p->kind = page.kind; + p2p->entryPageOffset = + sizeof(unwind_info_regular_second_level_page_header); + p2p->entryCount = page.entryCount; + ep = reinterpret_cast(&p2p[1]); + for (size_t i = 0; i < page.entryCount; i++) { + const CompactUnwindEntry64 *cuep = cuPtrVector[page.entryIndex + i]; + *ep++ = cuep->functionAddress; + *ep++ = cuep->encoding; + } } - p2p = - reinterpret_cast(ep); + memset(ep, 0, page.padByteCount); + ep += (page.padByteCount / sizeof(uint32_t)); } - assert(getSize() == - static_cast((reinterpret_cast(p2p) - buf))); + // assert(getSize() == + // static_cast((reinterpret_cast(p2p) - buf))); } diff --git a/lld/test/MachO/tools/generate-cfi-funcs.py b/lld/test/MachO/tools/generate-cfi-funcs.py --- a/lld/test/MachO/tools/generate-cfi-funcs.py +++ b/lld/test/MachO/tools/generate-cfi-funcs.py @@ -24,7 +24,7 @@ have_lsda = (random.random() < lsda_odds) frame_size = random.randint(4, 64) * 16 frame_offset = -random.randint(0, (frame_size/16 - 4)) * 16 - reg_count = random.randint(0, 4) + reg_count = random.randint(0, 5) reg_combo = random.randint(0, factorial(reg_count) - 1) regs_saved = saved_regs_combined[reg_count][reg_combo] global func_size_low, func_size_high diff --git a/lld/test/MachO/tools/validate-unwind-info.py b/lld/test/MachO/tools/validate-unwind-info.py --- a/lld/test/MachO/tools/validate-unwind-info.py +++ b/lld/test/MachO/tools/validate-unwind-info.py @@ -45,7 +45,7 @@ sys.exit("no program symbols found in input") program_common_encodings = ( - re.findall(r"^\s+encoding\[\d+\]: 0x(%s+)$" % hex, + re.findall(r"^\s+encoding\[(?:\d|\d\d|1[01]\d|12[0-6])\]: 0x(%s+)$" % hex, objdump_string, re.MULTILINE)) if not program_common_encodings: sys.exit("no common encodings found in input") @@ -53,7 +53,7 @@ program_encodings_map = {program_symbols_map[address]:encoding for address, encoding in re.findall(r"^\s+\[\d+\]: function offset=0x(%s+), " % hex + - r"encoding\[\d+\]=0x(%s+)$" % hex, + r"encoding(?:\[\d+\])?=0x(%s+)$" % hex, objdump_string, re.MULTILINE)} if not object_encodings_map: sys.exit("no program encodings found in input") @@ -73,8 +73,8 @@ if program_encodings_map != object_encodings_map: if args.debug: - pprint("program encodings map:\n" + program_encodings_map) - pprint("object encodings map:\n" + object_encodings_map) + pprint("program encodings map:\n" + str(program_encodings_map)) + pprint("object encodings map:\n" + str(object_encodings_map)) sys.exit("encoding maps differ") # Count frequency of object-file folded encodings @@ -86,11 +86,12 @@ sorted(encoding_frequency_map, key=lambda x: (encoding_frequency_map.get(x), x), reverse=True)] + del encoding_frequencies[127:] if program_common_encodings != encoding_frequencies: if args.debug: - pprint("program common encodings:\n" + program_common_encodings) - pprint("object encoding frequencies:\n" + encoding_frequencies) + pprint("program common encodings:\n" + str(program_common_encodings)) + pprint("object encoding frequencies:\n" + str(encoding_frequencies)) sys.exit("encoding frequencies differ")