[lld-macho] Emit personalities in compact unwind

[int3]

Summary

Note that there is a triple indirection involved with
personalities and compact unwind:

1. Two bits of each CU encoding are used as an offset into the personality array.
2. Each entry of the personality array is an offset from the image base. The resulting address (after adding the image base) should point within the GOT.
3. The corresponding GOT entry contains the actual pointer to the personality function.

To further complicate things, when the personality function is in the
object file (as opposed to a dylib), its references in
__compact_unwind may refer to it via a section + offset relocation
instead of a symbol relocation. Since our GOT implementation can only
create entries for symbols, we have to create a synthetic symbol at the
given section offset.

[clayborg]

lld/MachO/UnwindInfoSection.cpp

109

Is there an assert or check you can put into the code to verify this assumption?

234

We don't seem to modify the "cuEntry" in the loop below, can be put the "const" back and revert this change?

[int3]

lld/MachO/UnwindInfoSection.cpp

109

I suppose we could be conservative and assert that the relocations only point within the __TEXT segment...

Note that problem already exists in the current implementation (which @gkm wrote) -- it calls compactUnwindSection->writeTo() instead of relocateCompactUnwind(), but writeTo() makes the same assumptions. Not sure if @gkm has thoughts on this.

234

oops yeah leftover change

[int3]

lld/MachO/UnwindInfoSection.cpp

234

o wait, this is actually necessary. That's because I am now modifying the CU entries that I get from iterating over cuPtrVector, so they cannot be const, and since this loop populates the cuPtrVector, the cuEntrys cannot be const here.

[int3]

check that compact unwind entries only reference __TEXT

[int3]

• insert personality pointers into GOT earlier, since they determine whether a GOT is needed
• dedup personality pointers
• Add test for invalid compact unwind that references non-text segments

[int3]

try and fix tests

[int3]

rebase

lld/MachO/SyntheticSections.cpp

void IndirectSymtabSection::finalizeContents() {
   off += in.got->getEntries().size();
   in.tlvPointers->reserved1 = off;
   off += in.tlvPointers->getEntries().size();
   // There is a 1:1 correspondence between stubs and LazyPointerSection
   // entries, so they can share the same sub-array in the table.
   in.stubs->reserved1 = in.lazyPointers->reserved1 = off;
 }
 
+static uint32_t indirectValue(const Symbol *sym) {
+  return sym->symtabIndex != UINT32_MAX ? sym->symtabIndex
+                                        : MachO::INDIRECT_SYMBOL_LOCAL;
+}
+
 void IndirectSymtabSection::writeTo(uint8_t *buf) const {
   uint32_t off = 0;
   for (const Symbol *sym : in.got->getEntries()) {
-    write32le(buf + off * sizeof(uint32_t), sym->symtabIndex);
+    write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
     ++off;
   }
   for (const Symbol *sym : in.tlvPointers->getEntries()) {
-    write32le(buf + off * sizeof(uint32_t), sym->symtabIndex);
+    write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
     ++off;
   }
   for (const Symbol *sym : in.stubs->getEntries()) {
-    write32le(buf + off * sizeof(uint32_t), sym->symtabIndex);
+    write32le(buf + off * sizeof(uint32_t), indirectValue(sym));
     ++off;
   }
 }
 
 StringTableSection::StringTableSection()
     : LinkEditSection(segment_names::linkEdit, section_names::stringTable) {}
 
 uint32_t StringTableSection::addString(StringRef str) {

lld/MachO/UnwindInfoSection.h

struct SecondLevelPage {
     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;
+  // Indices of personality functions within the GOT.
   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<CompactUnwindEntry64 *> cuPtrVector;
   std::vector<SecondLevelPage> secondLevelPages;
   MergedOutputSection *compactUnwindSection = nullptr;
   uint64_t level2PagesOffset = 0;
   uint64_t unwindInfoSize = 0;
 };
 
+void prepareCompactUnwind(InputSection *isec);
+
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/UnwindInfoSection.cpp

 //===- 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 "Config.h"
 #include "InputSection.h"
 #include "MergedOutputSection.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/SmallVector.h"
 #include "llvm/BinaryFormat/MachO.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 

 // number of entries.
 //
 // * The __TEXT,__unwind_info format can accommodate up to 127 unique
 // encodings for the space-efficient compressed format. In practice,
 // fewer than a dozen unique encodings are used by C++ programs of
 // all sizes. Therefore, we don't even bother implementing the regular
 // non-compressed format. Time will tell if anyone in the field ever
 // overflows the 127-encodings limit.
+//
+// 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): prune __eh_frame entries superseded by __unwind_info
 // TODO(gkm): how do we align the 2nd-level pages?
 
 UnwindInfoSection::UnwindInfoSection()
     : SyntheticSection(segment_names::text, section_names::unwindInfo) {
   align = 4; // mimic ld64
 }
 
 bool UnwindInfoSection::isNeeded() const {
   return (compactUnwindSection != nullptr);
 }
 
+// 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 macho::prepareCompactUnwind(InputSection *isec) {
+  assert(isec->segname == segment_names::ld &&
+         isec->name == section_names::compactUnwind);
+
+  DenseMap<std::pair<InputSection *, uint64_t /* addend */>, macho::Symbol *>
+      anonPersonalitySymbols;
+  for (Reloc &r : isec->relocs) {
+    // TODO: generalize for other archs
+    assert(r.type == X86_64_RELOC_UNSIGNED);
+    if (r.offset % sizeof(CompactUnwindEntry64) !=
+        offsetof(struct CompactUnwindEntry64, personality))
+      continue;
+
+    if (auto *s = r.referent.dyn_cast<lld::macho::Symbol *>()) {
+      if (auto *undefined = dyn_cast<Undefined>(s))
+        treatUndefinedSymbol(*undefined);
+      else
+        in.got->addEntry(s);
+    } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
+      // Personality functions can be referenced via section relocations
+      // if they live in an object file (instead of a dylib). Create
+      // placeholder synthetic symbols for them in the GOT.
+      macho::Symbol *&s = anonPersonalitySymbols[{referentIsec, r.addend}];
+      if (s == nullptr) {
+        s = make<Defined>("<internal>", nullptr, referentIsec, r.addend, false,
+                          false, false);
+        in.got->addEntry(s);
+      }
+      r.referent = s;
+      r.addend = 0;
+    }
+  }
+}
+
+// Unwind info lives in __DATA, and finalization of __TEXT will occur before
+// finalization of __DATA. Moreover, the finalization of unwind info depends on
+// the exact addresses that it references. So it is safe for compact unwind to
+// reference addresses in __TEXT, but not addresses in any other segment.
+static void checkTextSegment(InputSection *isec) {
+  if (isec->segname != segment_names::text)
+    error("compact unwind references address in " + toString(isec) +
+          " which is not in segment __TEXT");
+}
+
+// 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.
+static void relocateCompactUnwind(MergedOutputSection *compactUnwindSection,
+                                  std::vector<CompactUnwindEntry64> &cuVector) {
+  for (InputSection *isec : compactUnwindSection->inputs) {
+    uint8_t *buf =
+        reinterpret_cast<uint8_t *>(cuVector.data()) + isec->outSecFileOff;
+    memcpy(buf, isec->data.data(), isec->data.size());
+
+    for (Reloc &r : isec->relocs) {
+      uint64_t referentVA = 0;
+      if (auto *referentSym = r.referent.dyn_cast<macho::Symbol *>()) {
+        if (!isa<Undefined>(referentSym)) {
+          assert(referentSym->isInGot());
+          if (auto *defined = dyn_cast<Defined>(referentSym))
+            checkTextSegment(defined->isec);
+          // At this point in the link, we may not yet know the final address of
+          // the GOT, so we just encode the index. We make it a 1-based index so
+          // that we can distinguish the null pointer case.
+          referentVA = referentSym->gotIndex + 1;
+        }
+      } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
+        checkTextSegment(referentIsec);
+        referentVA = referentIsec->getVA() + r.addend;
+      }
+      support::endian::write64le(buf + r.offset, referentVA);
+    }
+  }
+}
+
+// There should only be a handful of unique personality pointers, so we can
+// encode them as 2-bit indices into a small array.
+void encodePersonalities(const std::vector<CompactUnwindEntry64 *> &cuPtrVector,
+                         std::vector<uint32_t> &personalities) {
+  for (CompactUnwindEntry64 *cu : cuPtrVector) {
+    if (cu->personality == 0)
+      continue;
+    uint32_t personalityOffset = cu->personality - in.header->addr;
+    // Linear search is fast enough for a small array.
+    auto it = find(personalities, personalityOffset);
+    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 << countTrailingZeros(
+            static_cast<compact_unwind_encoding_t>(UNWIND_PERSONALITY_MASK));
+  }
+  if (personalities.size() > 3)
+    error("too many personalities (" + std::to_string(personalities.size()) +
+          ") for compact unwind to encode");
+}
+
 // Scan the __LD,__compact_unwind entries and compute the space needs of
 // __TEXT,__unwind_info and __TEXT,__eh_frame
-
 void UnwindInfoSection::finalize() {
   if (compactUnwindSection == nullptr)
     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+lsda. Folding is necessary because it reduces
   // the number of CU entries by as much as 3 orders of magnitude!
   compactUnwindSection->finalize();
   assert(compactUnwindSection->getSize() % sizeof(CompactUnwindEntry64) == 0);
   size_t cuCount =
       compactUnwindSection->getSize() / sizeof(CompactUnwindEntry64);
   cuVector.resize(cuCount);
   // Relocate all __LD,__compact_unwind entries
-  compactUnwindSection->writeTo(reinterpret_cast<uint8_t *>(cuVector.data()));
+  relocateCompactUnwind(compactUnwindSection, cuVector);
 
   // 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 CompactUnwindEntry64 &cuEntry : cuVector)
+  for (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)->personality == (*foldEnd)->personality &&
            (*foldBegin)->lsda == (*foldEnd)->lsda)
       ;
     *foldWrite++ = *foldBegin;
     foldBegin = foldEnd;
   }
   cuPtrVector.erase(foldWrite, cuPtrVector.end());
 
+  encodePersonalities(cuPtrVector, personalities);
+
   // Count frequencies of the folded encodings
   EncodingMap encodingFrequencies;
   for (auto cuPtrEntry : cuPtrVector)
     encodingFrequencies[cuPtrEntry->encoding]++;
 
   // Make a vector of encodings, sorted by descending frequency
   for (const auto &frequency : encodingFrequencies)
     commonEncodings.emplace_back(frequency);
void UnwindInfoSection::writeTo(uint8_t *buf) const {
 
   // Common encodings
   auto *i32p = reinterpret_cast<uint32_t *>(&uip[1]);
   for (const auto &encoding : commonEncodings)
     *i32p++ = encoding.first;
 
   // Personalities
   for (const uint32_t &personality : personalities)
-    *i32p++ = personality;
+    *i32p++ = in.got->addr + (personality - 1) * WordSize;
 
   // 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) {

lld/MachO/Writer.cpp

if (relocAttrs.hasAttr(RelocAttrBits::BRANCH)) {
     // need of rebase opcodes.
     if (!(isThreadLocalVariables(isec->flags) && isa<Defined>(sym)))
       addNonLazyBindingEntries(sym, isec, r.offset, r.addend);
   }
 }
 
 void Writer::scanRelocations() {
   for (InputSection *isec : inputSections) {
-    // We do not wish to add rebase opcodes for __LD,__compact_unwind, because
-    // it doesn't actually end up in the final binary. TODO: filtering it out
-    // before Writer runs might be cleaner...
-    if (isec->segname == segment_names::ld)
+    if (isec->segname == segment_names::ld) {
+      prepareCompactUnwind(isec);
       continue;
+    }
 
     for (Reloc &r : isec->relocs) {
       if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND))
         continue;
       if (auto *sym = r.referent.dyn_cast<lld::macho::Symbol *>()) {
         if (auto *undefined = dyn_cast<Undefined>(sym))
           treatUndefinedSymbol(*undefined);
         else if (target->validateSymbolRelocation(sym, isec, r))

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

-# REQUIRES: x86
-# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 %s -o %t.o
-# RUN: %lld -pie -lSystem %t.o -o %t
-# RUN: llvm-objdump --macho --unwind-info --rebase %t | FileCheck %s
-
-## Check that we do not add rebase opcodes to the compact unwind section.
-# CHECK:      Contents of __unwind_info section:
-# CHECK-NEXT:   Version:                                   0x1
-# CHECK-NEXT:   Common encodings array section offset:
-# CHECK-NEXT:   Number of common encodings in array:       0x1
-# CHECK:      Rebase table:
-# CHECK-NEXT: segment  section            address     type
-# CHECK-EMPTY:
-
-.globl _main
-.text
-_main:
-  .cfi_startproc
-  .cfi_def_cfa_offset 16
-  retq
-  .cfi_endproc

lld/test/MachO/compact-unwind.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 %s -o %t.o
+# RUN: %lld -pie -lSystem -lc++ %t.o -o %t
+# RUN: llvm-objdump --macho --unwind-info --indirect-symbols --rebase %t | FileCheck %s
+
+# CHECK:      Indirect symbols for (__DATA_CONST,__got)
+# CHECK-NEXT: address                    index name
+# CHECK-DAG:  0x[[#%x,GXX_PERSONALITY:]] [[#]] ___gxx_personality_v0
+# CHECK-DAG:  0x[[#%x,MY_PERSONALITY:]]  LOCAL
+
+# CHECK:      Contents of __unwind_info section:
+# CHECK:        Personality functions: (count = 2)
+# CHECK-NEXT:     personality[1]: 0x{{0*}}[[#MY_PERSONALITY-0x100000000]]
+# CHECK-NEXT:     personality[2]: 0x{{0*}}[[#GXX_PERSONALITY-0x100000000]]
+
+## Check that we do not add rebase opcodes to the compact unwind section.
+# CHECK:      Rebase table:
+# CHECK-NEXT: segment      section        address          type
+# CHECK-NEXT: __DATA_CONST __got          0x{{[0-9a-f]*}}  pointer
+# CHECK-NEXT: __DATA_CONST __got          0x{{[0-9a-f]*}}  pointer
+# CHECK-EMPTY:
+
+.globl _main, _foo, _my_personality, _bar
+
+.text
+_foo:
+  .cfi_startproc
+  .cfi_personality 155, _my_personality
+  .cfi_def_cfa_offset 16
+  retq
+  .cfi_endproc
+
+_bar:
+  .cfi_startproc
+## Check that we dedup references to the same statically-linked personality.
+  .cfi_personality 155, _my_personality
+  .cfi_def_cfa_offset 16
+  retq
+  .cfi_endproc
+
+_main:
+  .cfi_startproc
+  .cfi_personality 155, ___gxx_personality_v0
+  .cfi_def_cfa_offset 16
+  retq
+  .cfi_endproc
+
+_my_personality:
+  retq

lld/test/MachO/invalid/compact-unwind-bad-reloc.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 %s -o %t.o
+# RUN: not %lld -pie -lSystem -lc++ %t.o -o %t 2>&1 | FileCheck %s -DFILE=%t.o
+# CHECK: error: compact unwind references address in [[FILE]]:(__data) which is not in segment __TEXT
+
+.globl _main, _not_a_function
+.text
+_main:
+  retq
+
+.data
+_not_a_function:
+  .cfi_startproc
+  .cfi_personality 155, ___gxx_personality_v0
+  .cfi_def_cfa_offset 16
+  retq
+  .cfi_endproc

lld/test/MachO/invalid/compact-unwind-personalities.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 %s -o %t.o
+# RUN: not %lld -pie -lSystem -lc++ %t.o -o %t 2>&1 | FileCheck %s --check-prefix=TOO-MANY
+# RUN: not %lld -pie -lSystem %t.o -o %t 2>&1 | FileCheck %s --check-prefix=UNDEF
+# TOO-MANY: error: too many personalities (4) for compact unwind to encode
+# UNDEF: error: undefined symbol: ___gxx_personality_v0
+
+.globl _main, _personality_1, _personality_2, _personality_3
+
+.text
+
+_foo:
+  .cfi_startproc
+  .cfi_personality 155, _personality_1
+  .cfi_def_cfa_offset 16
+  retq
+  .cfi_endproc
+
+_bar:
+  .cfi_startproc
+  .cfi_personality 155, _personality_2
+  .cfi_def_cfa_offset 16
+  retq
+  .cfi_endproc
+
+_baz:
+  .cfi_startproc
+  .cfi_personality 155, _personality_3
+  .cfi_def_cfa_offset 16
+  retq
+  .cfi_endproc
+
+_main:
+  .cfi_startproc
+  .cfi_personality 155, ___gxx_personality_v0
+  .cfi_def_cfa_offset 16
+  retq
+  .cfi_endproc
+
+_personality_1:
+  retq
+_personality_2:
+  retq
+_personality_3:
+  retq

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

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" + str(program_encodings_map))
-      pprint("object encodings map:\n" + str(object_encodings_map))
+      print("program encodings map:")
+      pprint(program_encodings_map)
+      print("object encodings map:")
+      pprint(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