[lld-macho] Fix bug in CUE folding that resulted in wrong unwind table.

[oontvoo]

Summary

PR/59070

[jyknight]

Code change looks good to me!

[int3]

Thanks for tracking this down!!

lld/MachO/UnwindInfoSection.cpp

182

nit: rm blank line

183

nit 1: I think "largest" is more descriptive than "final" (plus "final" often has temporal-ordering connotations, e.g. InputSection::isFinal). Also maybe unwindAddressBoundary or cuAddressBoundary might be a better name for the variable, for similar reasons?

nit 2: I don't think "this should covered folded entries as well" is a super clear explanation; I thought about how to elaborate on it, but then I think maybe it's better to let the reader figure that out by reading the comments in the implementation. I guess it's okay if you want to keep that line though.

464

"remember" usually means "recall", rather than record/save.

660–661

this is now unused

661–664

I'm not entirely sure why, but this is what ld64 does

lld/test/MachO/compact-unwind-folding-bug.s

2 ↗

(On Diff #476565)

just to be clear, 'remove boilerplate' will include removing all the LSDA stuff, yes? we don't need to have a file that repros the actual no-catch bug, just something that checks that the last address of a bunch of folded CUEs is correct

[jyknight]

lld/MachO/UnwindInfoSection.cpp

661–664

Adding 1 does make sense. This value is the start of the "next function", so it's an exclusive bound, and you want the final byte of the function to actually be included in the range.

[int3]

lld/MachO/UnwindInfoSection.cpp

661–664

That was my initial thought too, but shouldn't adding the length already make it an exclusive bound?

[oontvoo]

lld/MachO/UnwindInfoSection.cpp

661–664

hmm yeah, looks like LD64 does add 1. (here and a couple of lines up in the secondLevelPages loop too).

[oontvoo]

addressed review comments + simplified test.

Thanks!

[oontvoo]

fixed test + off-by-one error

[jyknight]

lld/MachO/UnwindInfoSection.cpp

661–664

@int3: oh, good point! ld64's code is actually making it too large by one byte. I suspect that's by accident, and a mistake which we should not replicate.

[int3]

Thanks!

lld/MachO/UnwindInfoSection.cpp

183

thanks for changing the comments!

thoughts on the variable rename?

641

661–664

or possibly to work around a mistake in the runtime unwinder... hard to say without carefully reading its implementation.

@oontvoo I'll leave it up to you whether you want to leave the +1 in. We could certainly omit it and see if it causes any problems in practice.

lld/test/MachO/compact-unwind-folding-bug.s

2 ↗

(On Diff #476878)

How about

This is a regression test. for verifying that the level-1 index sentinel entry has the correct address value. In particular, we used to emit the wrong value when the last N compact unwind entries were folded together.

I'm also wondering if the test file name can have something more specific than "folding bug"... maybe compact-unwind-tail-folding.s? Because it's not a bug in folding in general, only when the fold happens at the tail entries of the CUE array.

19 ↗

(On Diff #476878)

(alternatively you could omit it entirely, MC emits stuff into .text by default)

24–27 ↗

(On Diff #476657)

can we remove more boilerplate? (likewise for the other functions)

56–59 ↗

(On Diff #476657)

why do we need this?

[oontvoo]

lld/MachO/UnwindInfoSection.cpp

183

changed to cueEndBoundary ?

661–664

I'll remove the +1 since it seems wrong (ie., if there happens to be stuff after the last entry taht *shouldn't* be in it, then the table would still include it.)

Also speaking of "strange", there seems to be another edge case here. I've added the test case below.

Should we replicate this or not? (my guess is no, but /shrug)

lld/test/MachO/compact-unwind-folding-bug.s

2 ↗

(On Diff #476878)

How about just compact-unwind-folding.s?
(added two additional test cases, where we behave slightly differently from LD64 ... LMK what you think)

24–27 ↗

(On Diff #476657)

We probably could - but slightly prefer that these symbols refer to each other (so that they don't look like they're all unused)
(I did remove the push/pop pairs to make the test smaller)

[oontvoo]

updated tests and remove the off-by-one "bug"

[int3]

lld/MachO/UnwindInfoSection.cpp

183

sounds good!

lld/test/MachO/compact-unwind-folding-bug.s

2 ↗

(On Diff #476878)

sgtm!

lld/test/MachO/compact-unwind-foldings.s

8

60–61

this makes sense to me, and I think we can keep our deviation from ld64's behavior here

62

is this directive necessary?

86–87

both ld64 and LLD do include an entry (with encoding 0x0) for this, right?

I'm not sure there's a way to *not* include _d here, since if there isn't an entry with 0x0 encoding, then the unwinder just uses the CUE at the most recent preceding address. So I think ld64 is working correctly here

89

ditto

[oontvoo]

lld/test/MachO/compact-unwind-foldings.s

86–87

right - when _d is in the middle of the range, we can't exclude it.

[oontvoo]

address review comments + rebase

[oontvoo]

thanks!

lld/MachO/UnwindInfoSection.cpp

private:
   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
void UnwindInfoSectionImpl::finalize() {
   // Rather than sort & fold the 32-byte entries directly, we create a
   // vector of indices to entries and sort & fold that instead.
   cuIndices.resize(cuEntries.size());
   std::iota(cuIndices.begin(), cuIndices.end(), 0);
   llvm::sort(cuIndices, [&](size_t a, size_t b) {
     return cuEntries[a].functionAddress < cuEntries[b].functionAddress;
   });
 
+  // Record the ending boundary before we fold the entries.
+  cueEndBoundary = cuEntries[cuIndices.back()].functionAddress +
+                   cuEntries[cuIndices.back()].functionLength;
+
   // Fold adjacent entries with matching encoding+personality and without LSDA
   // We use three iterators on the same cuIndices 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 = cuIndices.begin();
void UnwindInfoSectionImpl::writeTo(uint8_t *buf) const {
   auto *i32p = reinterpret_cast<uint32_t *>(&uip[1]);
   for (const auto &encoding : commonEncodings)
     *i32p++ = encoding.first;
 
   // Personalities
   for (const Symbol *personality : personalities)
     *i32p++ = personality->getGotVA() - 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 = cuIndices[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
-  const CompactUnwindEntry &cuEnd = cuEntries[cuIndices.back()];
-  iep->functionOffset =
-      cuEnd.functionAddress - in.header->addr + cuEnd.functionLength;
+  // 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 =

lld/test/MachO/compact-unwind-foldings.s

+# REQUIRES: x86
+# Tests to verify that
+#    - the folded CUEs covered up to the last entries, even if they were removed/folded.
+#    - only entries that *should* be in eh_frame are actually included. (**)
+# (**) This is where LD64 does differently.
+
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/fold-tail.s -o %t/fold-tail.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/cues-range-gap.s -o %t/cues-range-gap.o
+
+# RUN: %lld -o %t/fold-tail.out %t/fold-tail.o
+# RUN: llvm-objdump --macho --syms --unwind-info %t/fold-tail.out | FileCheck %s 
+
+# RUN: %lld -o %t/cues-range-gap.out %t/cues-range-gap.o
+
+# CHECK-LABEL: SYMBOL TABLE:
+# CHECK:       [[#%x,A_ADDR:]]  l     F __TEXT,__text _a
+# CHECK:       [[#%x,B_ADDR:]]  l     F __TEXT,__text _b
+# CHECK:       [[#%x,C_ADDR:]]  l     F __TEXT,__text _c
+# CHECK:       [[#%x,D_ADDR:]]  l     F __TEXT,__text _d
+# CHECK:       [[#%x,MAIN_ADDR:]]  g     F __TEXT,__text _main
+
+## Check that [1] offset starts at c's address + 3 (its length).
+# CHECK-LABEL: Contents of __unwind_info section:
+# CHECK:  Top level indices: (count = 2)
+# CHECK-NEXT : [0]: function offset=[[#%#.7x,MAIN_ADDR]]
+# CHECK-NEXT : [1]: function offset=[[#%#.7x,C_ADDR + 3]]
+
+#--- fold-tail.s
+        .text
+        .globl  _main
+        .p2align        4, 0x90
+_main:
+        .cfi_startproc
+        callq   _a
+        retq
+        .cfi_endproc
+
+        .p2align        4, 0x90
+_a:
+        .cfi_startproc
+        callq   _b
+        retq
+        .cfi_endproc
+
+        .p2align        4, 0x90
+_b:
+        .cfi_startproc
+        callq   _c
+        retq
+        .cfi_endproc
+
+        .p2align        4, 0x90
+_c:
+        .cfi_startproc
+        retq
+        .cfi_endproc
+
+// _d should NOT have an entry in .eh_frame
+// So it shouldn't be covered by the unwind table.
+_d:
+        xorl %eax, %eax
+        ret
+
+.subsections_via_symbols
+
+#--- cues-range-gap.s
+        .text
+        .globl  _main
+        .p2align        4, 0x90
+_main:
+        .cfi_startproc
+        callq   _a
+        retq
+        .cfi_endproc
+
+        .p2align        4, 0x90
+_a:
+        .cfi_startproc
+        callq   _b
+        retq
+        .cfi_endproc
+
+// _d is intentionally placed in between the symbols with eh_frame entries.
+// but _d should NOT have an entry in .eh_frame
+// So it shouldn't be covered by the unwind table.
+_d:
+        xorl %eax, %eax
+        ret
+
+        .p2align        4, 0x90
+_b:
+        .cfi_startproc
+        callq   _c
+        retq
+        .cfi_endproc
+
+        .p2align        4, 0x90
+_c:
+        .cfi_startproc
+        retq
+        .cfi_endproc
+
+.subsections_via_symbols