[lld-macho] Handle overflow beyond the 127 common encodings limit

[gkm]

Summary

The common encodings table holds only 127 entries. The encodings index for compact entries is 8 bits wide, and indexes 127..255 are stored locally to each second-level page. Prior to this diff, lld would fatal() if encodings overflowed the 127 limit.

This diff populates a per-second-level-page encodings table as needed. When the per-page encodings table hits its limit, we must terminate the page. If such early termination would consume fewer entries than a regular (non-compact) encoding page, then we prefer the regular format.

Caveat: one reason the common-encoding table might overflow is because of DWARF debug-info references, which are not yet implemented and will come with a later diff.

[int3]

lld/MachO/UnwindInfoSection.cpp

160–164

I know this is existing code, but isn't this the default behavior of std::pair::operator>()?

167–227

depending on how large the vector is, might be a useful perf optimization to use quickselect to find the 127th largest element and just sort over those smaller than it... but we can consider that later

205

2 * sizeof(uint32_t) is due to the size of unwind_info_regular_second_level_entry, right? how about using sizeof(unwind_info_regular_second_level_entry) instead?

211–212

let's use braces here too since the other if-else clauses have them

215

why does it matter if i < cuPtrVector.size()?

235–237

why the + 1?

274–275

avoid auto for types with simple names

298

avoid auto

322–323

could use memcpy

337

so I don't know if this is spec-guaranteed behavior, but there are already several places in LLD where we assume that an unwritten section of an mmap'ed buffer will be zero. I.e. we don't zero things out explicitly, and it seems to work in practice. I think doing that would allow us to eliminate padByteCount?

338–339

rm / uncomment?

lld/MachO/UnwindInfoSection.h

17

doesn't seem like unordered_map is actually used

41–46

why not use find() instead of lookup()?

75–76

general aesthetic suggestion: if we moved this into the .cpp file, we could do away with all the UNWIND_INFO_ prefixes and reduce some of the (extensive) line wrapping. Probably better in a separate diff though

[gkm]

lld/MachO/UnwindInfoSection.cpp

160–164

No. std::pair::operator>() collates primarily on .first and falls back on .second. Here, we need .second as the primary and .first as the fallback.

167–227

This is good thinkin'! The Chrome bug that motivated this diff has inputs with approx 380 common encodings. IMO, filtering with quickselect (1) offers an insignificant micro-efficiency, and (2) is possibly more expensive than sort alone.

205

This is a valid comment for handling the regular encoding format a bit further down in the function. Here, we are still handling compact encoding, and specifically the case where we need to extend the local encoding table by 1 word, and the compact entry list by 1 word.

215

When i == cuPtrVector.size(), the final page was filled using the compact format, so it is irrelevant to check if we might fit more entries using the regular format.

222–223

s/2 * 2 * sizeof(uint32_t)/sizeof(unwind_info_regular_second_level_entry)/ is appropriate here.

235–237

The first level index contains a sentinel.

lld/MachO/UnwindInfoSection.h

41–46

find() returns an iterator at key.
lookup() returns the value at key, and is simpler for my purposes.

75–76

I did this here. Vertical space is reduced by an underwhelming 2 lines, but horizontal line density is also lower, so on balance it seems an improvement.

[gkm]

• revise according to review feedback

[int3]

lld/MachO/UnwindInfoSection.cpp

215

ah, and if the final page can be filled with the compact format, it will always end up using fewer bytes than if it had used the regular format, right?

235–237

would be nice to have a conment

lld/MachO/UnwindInfoSection.h

41–46

I don't understand how it is simpler, since it looks like you always have to check if the returned value is a sentinel value -- just as you'd have to check if find() had returned a valid iterator. But it seems that using find() would remove the need for size_tx.

52

valid lint

[gkm]

lld/MachO/UnwindInfoSection.cpp

215

Yes, equal or fewer.

lld/MachO/UnwindInfoSection.h

41–46

Aside from the crufty helper class size_tx, I thought ...

• The current approach has a simpler access procedure:
  1. call .lookup() to receive the desired .second of the DenseMap's pair
  2. which we can compare with the default constructor size_tx() to detect "not found"
• With the iterator there are more steps:
  1. call .find() on to return an iterator
  2. compare iterator to .end() for "not found"
  3. if found, dereference the iterator to return a pair
  4. access .second to get the encoding-table index

I rewrote using .find() and it came-out nicer than anticipated, so I dropped size_tx and .lookup().

[gkm]

• rewrite encoding-index maps to use .find() rather than .lookup() so we can remove the crufty size_tx

[int3]

lgtm

lld/MachO/UnwindInfoSection.cpp

197

wouldn't hurt to address this lint

200–203

could use count() instead of find() here

318–319

[gkm]

I fixed the clang-tidy failures before landing. Unfortunately, I neglected to update the diff with the final version, which is why you see the notice that I landed with ongoing build failures. Oops. :(

lld/MachO/UnwindInfoSection.h

 //===- UnwindInfoSection.h ------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_UNWIND_INFO_H
 #define LLD_MACHO_UNWIND_INFO_H
 
 #include "MergedOutputSection.h"
 #include "SyntheticSections.h"
 
 #include "mach-o/compact_unwind_encoding.h"
 #include "llvm/ADT/DenseMap.h"
 
 #include <vector>
 
 // In 2020, we mostly care about 64-bit targets: x86_64 and arm64
 struct CompactUnwindEntry64 {
   uint64_t functionAddress;
   uint32_t functionLength;
   compact_unwind_encoding_t encoding;
   uint64_t personality;
   uint64_t lsda;
 };
 
 // FIXME(gkm): someday we might care about 32-bit targets: x86 & arm
 struct CompactUnwindEntry32 {
   uint32_t functionAddress;
   uint32_t functionLength;
   compact_unwind_encoding_t encoding;
   uint32_t personality;
   uint32_t lsda;
 };
 
 namespace lld {
 namespace macho {
 
 class UnwindInfoSection : public SyntheticSection {
 public:
   UnwindInfoSection();
   uint64_t getSize() const override { return unwindInfoSize; }
   bool isNeeded() const override;
   void finalize() override;
   void writeTo(uint8_t *buf) const override;
   void setCompactUnwindSection(MergedOutputSection *cuSection) {
     compactUnwindSection = cuSection;
   }
 
+  using EncodingMap = llvm::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;
+  };
+
 private:
   std::vector<std::pair<compact_unwind_encoding_t, size_t>> commonEncodings;
+  EncodingMap commonEncodingIndexes;
   std::vector<uint32_t> personalities;
   std::vector<unwind_info_section_header_lsda_index_entry> lsdaEntries;
   std::vector<CompactUnwindEntry64> cuVector;
   std::vector<const CompactUnwindEntry64 *> cuPtrVector;
-  std::vector<std::vector<const CompactUnwindEntry64 *>::const_iterator>
-      pageBounds;
+  std::vector<SecondLevelPage> secondLevelPages;
   MergedOutputSection *compactUnwindSection = nullptr;
   uint64_t level2PagesOffset = 0;
   uint64_t unwindInfoSize = 0;
 };
 
-#define UNWIND_INFO_COMMON_ENCODINGS_MAX 127
-
-#define UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE 4096
-#define UNWIND_INFO_REGULAR_SECOND_LEVEL_ENTRIES_MAX                           \
-  ((UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE -                                       \
-    sizeof(unwind_info_regular_second_level_page_header)) /                    \
-   sizeof(unwind_info_regular_second_level_entry))
-#define UNWIND_INFO_COMPRESSED_SECOND_LEVEL_ENTRIES_MAX                        \
-  ((UNWIND_INFO_SECOND_LEVEL_PAGE_SIZE -                                       \
-    sizeof(unwind_info_compressed_second_level_page_header)) /                 \
-   sizeof(uint32_t))
-
-#define UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_BITS 24
-#define UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET_MASK                          \
-  UNWIND_INFO_COMPRESSED_ENTRY_FUNC_OFFSET(~0)
-
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/UnwindInfoSection.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/BinaryFormat/MachO.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 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)
+
 // 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
size_t cuCount =
       compactUnwindSection->getSize() / sizeof(CompactUnwindEntry64);
   cuVector.resize(cuCount);
   // Relocate all __LD,__compact_unwind entries
   compactUnwindSection->writeTo(reinterpret_cast<uint8_t *>(cuVector.data()));
 
   // Rather than sort & fold the 32-byte entries directly, we create a
   // vector of pointers to entries and sort & fold that instead.
   cuPtrVector.reserve(cuCount);
-  for (const auto &cuEntry : cuVector)
+  for (const CompactUnwindEntry64 &cuEntry : cuVector)
     cuPtrVector.emplace_back(&cuEntry);
   std::sort(cuPtrVector.begin(), cuPtrVector.end(),
             [](const CompactUnwindEntry64 *a, const CompactUnwindEntry64 *b) {
               return a->functionAddress < b->functionAddress;
             });
 
   // Fold adjacent entries with matching encoding+personality+lsda
   // We use three iterators on the same cuPtrVector to fold in-situ:
while (++foldEnd < cuPtrVector.end() &&
            (*foldBegin)->lsda == (*foldEnd)->lsda)
       ;
     *foldWrite++ = *foldBegin;
     foldBegin = foldEnd;
   }
   cuPtrVector.erase(foldWrite, cuPtrVector.end());
 
   // Count frequencies of the folded encodings
-  llvm::DenseMap<compact_unwind_encoding_t, size_t> encodingFrequencies;
+  EncodingMap 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<compact_unwind_encoding_t, size_t> &a,
                const std::pair<compact_unwind_encoding_t, size_t> &b) {
               if (a.second == b.second)
                 // When frequencies match, secondarily sort on encoding
                 // to maintain parity with validate-unwind-info.py
                 return a.first > b.first;
               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())
+  // 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() > 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 < cuPtrVector.size();) {
+    secondLevelPages.emplace_back();
+    auto &page = secondLevelPages.back();
+    page.entryIndex = i;
+    uintptr_t functionAddressMax =
+        cuPtrVector[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 < cuPtrVector.size()) {
+      const auto *cuPtr = cuPtrVector[i];
+      if (cuPtr->functionAddress >= functionAddressMax) {
+        break;
+      } else 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;
-    i = pageBreak - cuPtrVector.cbegin();
+      }
+    }
+    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 we saturated the local
+    // encoding table early.
+    if (i < cuPtrVector.size() &&
+        page.entryCount < REGULAR_SECOND_LEVEL_ENTRIES_MAX) {
+      page.kind = UNWIND_SECOND_LEVEL_REGULAR;
+      page.entryCount = std::min(REGULAR_SECOND_LEVEL_ENTRIES_MAX,
+                                 cuPtrVector.size() - page.entryIndex);
+      i = page.entryIndex + page.entryCount;
+    } else {
+      page.kind = UNWIND_SECOND_LEVEL_COMPRESSED;
+    }
   }
 
   // compute size of __TEXT,__unwind_info section
   level2PagesOffset =
       sizeof(unwind_info_section_header) +
       commonEncodings.size() * sizeof(uint32_t) +
       personalities.size() * sizeof(uint32_t) +
-      pageBounds.size() * sizeof(unwind_info_section_header_index_entry) +
+      // The extra second-level-page entry is for the sentinel
+      (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);
+  unwindInfoSize =
+      level2PagesOffset + secondLevelPages.size() * SECOND_LEVEL_PAGE_BYTES;
 }
 
 // All inputs are relocated and output addresses are known, so write!
 
 void UnwindInfoSection::writeTo(uint8_t *buf) const {
   // 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 = pageBounds.size();
+  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 auto &personality : personalities)
+  for (const uint32_t &personality : personalities)
     *i32p++ = personality;
 
   // 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 (size_t i = 0; i < pageBounds.size() - 1; i++) {
-    iep->functionOffset = (*pageBounds[i])->functionAddress;
+  for (const SecondLevelPage &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 += SECOND_LEVEL_PAGE_BYTES;
   }
   // Level-1 sentinel
   const CompactUnwindEntry64 &cuEnd = cuVector.back();
   iep->functionOffset = cuEnd.functionAddress + cuEnd.functionLength;
   iep->secondLevelPagesSectionOffset = 0;
   iep->lsdaIndexArraySectionOffset = lsdaOffset;
   iep++;
 
   // LSDAs
   auto *lep =
       reinterpret_cast<unwind_info_section_header_lsda_index_entry *>(iep);
-  for (const auto &lsda : lsdaEntries) {
+  for (const unwind_info_section_header_lsda_index_entry &lsda : lsdaEntries) {
     lep->functionOffset = lsda.functionOffset;
     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<compact_unwind_encoding_t, size_t> commonEncodingIndexes;
-  for (const auto &encoding : commonEncodings)
-    commonEncodingIndexes[encoding.first] = i++;
-
   // 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 =
+          cuPtrVector[page.entryIndex]->functionAddress;
       auto *p2p =
-      reinterpret_cast<unwind_info_compressed_second_level_page_header *>(lep);
-  for (size_t i = 0; i < pageBounds.size() - 1; i++) {
-    p2p->kind = UNWIND_SECOND_LEVEL_COMPRESSED;
+          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 = pageBounds[i + 1] - pageBounds[i];
+      p2p->entryCount = page.entryCount;
       p2p->encodingsPageOffset =
           p2p->entryPageOffset + p2p->entryCount * sizeof(uint32_t);
-    p2p->encodingsCount = 0;
+      p2p->encodingsCount = page.localEncodings.size();
       auto *ep = reinterpret_cast<uint32_t *>(&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));
+      for (size_t i = 0; i < page.entryCount; i++) {
+        const CompactUnwindEntry64 *cuep = cuPtrVector[page.entryIndex + i];
+        auto it = commonEncodingIndexes.find(cuep->encoding);
+        if (it == commonEncodingIndexes.end())
+          it = page.localEncodingIndexes.find(cuep->encoding);
+        *ep++ = (it->second << COMPRESSED_ENTRY_FUNC_OFFSET_BITS) |
+                (cuep->functionAddress - functionAddressBase);
+      }
+      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 CompactUnwindEntry64 *cuep = cuPtrVector[page.entryIndex + i];
+        *ep++ = cuep->functionAddress;
+        *ep++ = cuep->encoding;
+      }
     }
-    p2p =
-        reinterpret_cast<unwind_info_compressed_second_level_page_header *>(ep);
+    pp += SECOND_LEVEL_PAGE_WORDS;
   }
-  assert(getSize() ==
-         static_cast<size_t>((reinterpret_cast<uint8_t *>(p2p) - buf)));
 }

lld/test/MachO/tools/generate-cfi-funcs.py

 saved_regs_combined = list(list(permutations(saved_regs, i))
                            for i in range(0,6))
 
 def print_function(name):
   global lsda_odds
   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
   func_size = random.randint(func_size_low, func_size_high) * 0x10
   func_size_high += 1
   if func_size_high % 0x10 == 0:
     func_size_low += 1
 

lld/test/MachO/tools/validate-unwind-info.py

def main():
   program_symbols_map = {address:symbol
     for address, symbol in
     re.findall(r"^%s(%s) g\s+F __TEXT,__text (x\1)$" % (hex8, hex8),
                objdump_string, re.MULTILINE)}
   if not program_symbols_map:
     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")
 
   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")
 
   # Fold adjacent entries from the object file that have matching encodings
   # TODO(gkm) add check for personality+lsda
   encoding0 = 0
   for symbol in sorted(object_encodings_map):
     encoding = object_encodings_map[symbol]
     fold = (encoding == encoding0)
     if fold:
       del object_encodings_map[symbol]
     if args.debug:
       print("%s %s with %s" % (
               'delete' if fold else 'retain', symbol, encoding))
     encoding0 = encoding
 
   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
   # and compare with the program-file common encodings table
   encoding_frequency_map = {}
   for _, encoding in object_encodings_map.items():
     encoding_frequency_map[encoding] = 1 + encoding_frequency_map.get(encoding, 0)
   encoding_frequencies = [x for x in
                           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")
 
 
 if __name__ == '__main__':
   main()