[lld-macho] __eh_frame: relocate & prune redundant entries

[gkm]

Summary

Work in progress ...
See the large block comment above ObjFile::registerUnwindEntries() in lld/MachO/InputFiles.cpp.

[gkm]

• major update

[gkm]

Add address member to ParsedSection. Many other updates.

[gkm]

• factor-out NFC changes into D114017
• many updates

lld/MachO/Driver.cpp

static void gatherInputSections() {
   int inputOrder = 0;
   for (const InputFile *file : inputFiles) {
     for (const SubsectionMap &map : file->subsections) {
       ConcatOutputSection *osec = nullptr;
       for (const SubsectionEntry &entry : map) {
         if (auto *isec = dyn_cast<ConcatInputSection>(entry.isec)) {
           if (isec->isCoalescedWeak())
             continue;
-          if (isec->getSegName() == segment_names::ld) {
-            assert(isec->getName() == section_names::compactUnwind);
+          if (isec->getName() == section_names::compactUnwind) {
             in.unwindInfo->addInput(isec);
             continue;
           }
           isec->outSecOff = inputOrder++;
           if (!osec)
             osec = ConcatOutputSection::getOrCreateForInput(isec);
           isec->parent = osec;
           inputSections.push_back(isec);
+        } else if (auto *isec = dyn_cast<EhFrameInputSection>(entry.isec)) {
+          in.ehFrameSection->addInput(isec);
+          continue;
         } else if (auto *isec = dyn_cast<CStringInputSection>(entry.isec)) {
           if (in.cStringSection->inputOrder == UnspecifiedInputOrder)
             in.cStringSection->inputOrder = inputOrder++;
           in.cStringSection->addInput(isec);
         } else if (auto *isec = dyn_cast<WordLiteralInputSection>(entry.isec)) {
           if (in.wordLiteralSection->inputOrder == UnspecifiedInputOrder)
             in.wordLiteralSection->inputOrder = inputOrder++;
           in.wordLiteralSection->addInput(isec);

lld/MachO/InputFiles.cpp

if (sectionType(sec.flags) == S_CSTRING_LITERALS ||
             make<CStringInputSection>(segname, name, this, data, align, flags);
         // FIXME: parallelize this?
         cast<CStringInputSection>(isec)->splitIntoPieces();
       } else {
         isec = make<WordLiteralInputSection>(segname, name, this, data, align,
                                              flags);
       }
       subsections.push_back({{0, isec}});
-    } else if (config->icfLevel != ICFLevel::none &&
-               (name == section_names::cfString &&
-                segname == segment_names::data)) {
+      continue;
+    }
+    if (config->icfLevel != ICFLevel::none &&
+        (name == section_names::cfString && segname == segment_names::data)) {
       uint64_t literalSize = target->wordSize == 8 ? 32 : 16;
       subsections.push_back({});
       SubsectionMap &subsecMap = subsections.back();
       for (uint64_t off = 0; off < data.size(); off += literalSize)
         subsecMap.push_back(
             {off, make<ConcatInputSection>(segname, name, this,
                                            data.slice(off, literalSize), align,
                                            flags)});
-    } else {
+      continue;
+    }
+    if (name == section_names::ehFrame) {
       auto *isec =
-          make<ConcatInputSection>(segname, name, this, data, align, flags);
-      if (!(isDebugSection(isec->getFlags()) &&
-            isec->getSegName() == segment_names::dwarf)) {
-        subsections.push_back({{0, isec}});
-      } else {
-        // Instead of emitting DWARF sections, we emit STABS symbols to the
-        // object files that contain them. We filter them out early to avoid
-        // parsing their relocations unnecessarily. But we must still push an
-        // empty map to ensure the indices line up for the remaining sections.
-        subsections.push_back({});
-        debugSections.push_back(isec);
-      }
-    }
+          make<EhFrameInputSection>(segname, name, this, data, align, flags);
+      continue;
+    }
+    auto *isec =
+        make<ConcatInputSection>(segname, name, this, data, align, flags);
+    if (isDebugSection(isec->getFlags()) &&
+        isec->getSegName() == segment_names::dwarf) {
+      continue;
+    subsections.push_back({{0, isec}});
   }
 }
 
 // Find the subsection corresponding to the greatest section offset that is <=
 // that of the given offset.
 //
 // offset: an offset relative to the start of the original InputSection (before
 // any subsection splitting has occurred). It will be updated to represent the
ObjFile::ObjFile(MemoryBufferRef mb, uint32_t modTime, StringRef archiveName)
     : InputFile(ObjKind, mb), modTime(modTime) {
   this->archiveName = std::string(archiveName);
   if (target->wordSize == 8)
     parse<LP64>();
   else
     parse<ILP32>();
 }
 
+// (See https://www.airs.com/blog/archives/460 for an overview of DWARF
+// __eh_frame format)
+//
+// * Processing unwind info involves a complex mesh of four input sections:
+//   (1) __LD,__compact_unwind: vector of CUE (Compact Unwind Entry)
+//   (2) __TEXT,__eh_frame: sequence of DWARF records (see below)
+//   (3) __TEXT,__gcc_except_tab: LSDA (Language Specific Data Area)
+//   (4) __TEXT,__text: Functions associated with unwind info
+//
+// * The __eh_frame section contains two types of record: CIE (Common
+//   Information Entry) and FDE (Frame Description Entry). CIEs are simple
+//   to deduplicate, but since an FDE's content is logically tied to its
+//   associated function body, we must deduplicate function+FDE during ICF.
+//
+// * CUE contains relocation_info for the __text entrypoint of its associated
+//   function. It can also contain relocation_info for the optional personality
+//   function and LSDA
+//
+// * CIE can contain relocation_info to an optional personality function
+//
+// * FDE references the __text entrypoint of its associated function, but the
+//   compiler generates no relocation_info
+//
+// * FDE can reference __gcc_except_tab for LSDA, but again, there is
+//   no compiler-generated relocation_info
+//
+// * The compiler will produce one of four configurations for each function:
+//   (1) no unwind info: we must create a degenerate CUE
+//   (2) CUE only: no action necessary
+//   (3) CUE and FDE: discard the FDE
+//   (4) FDE only: create a special CUE that references the FDE
+
+using EhFrameFdeMap = DenseMap<EhFrameRecord *, uint64_t>;
+using ExceptTabMap = DenseMap<ConcatInputSection *, uint64_t>;
+using CompactUnwindMap = DenseMap<CompactUnwindEntry *, uint64_t>;
+
+static void populateEhFrameFDEs(EhFrameFdeMap &ehFrameFDEs,
+                                SubsectionMap &subsecMap) {
+  InputSection *isec = get<EhFrameInputSection>(subsecMap.back().isec);
+  isec->splitIntoRecords();
+  for (EhFrameRecord &record : isec->records) {
+    if (record.id == UINT32_MAX)
+      continue;
+    // FIXME: relocate record.functionAddress
+    ehFrameFDEs[*record.functionAddress] = &record;
+  }
+}
+
+static void populateExceptTabs(ExceptTabMap &exceptTabs,
+                               SubsectionMap &subsecMap) {
+  uint64_t off = 0;
+  for (const SubsectionEntry &entry : subsecMap) {
+    ConcatInputSection *isec = get<ConcatInputSection>(entry.isec);
+    exceptTabs[off] = isec;
+    off += isec->getSize();
+  }
+}
+
+static void populateCompactUnwinds(CompactUnwindMap &compactUnwinds,
+                                   SubsectionMap &subsecMap) {
+  ConcatInputSection *isec = get<ConcatInputSection>(subsecMap.back().isec);
+  CompactUnwindEntry<> isec->data.data() for () {}
+}
+
+ObjFile::parseUnwindInfo() {
+  EhFrameFdeMap ehFrameFDEs;
+  ExceptTabMap exceptTabs;
+  CompactUnwindMap compactUnwinds;
+  for (const SubsectionMap &map : subsections)
+    if (InputSection *isec = map.back().isec) {
+      if (isec->name == section_names::gccExceptTab)
+        populateExceptTabs(exceptTabs, map);
+      else if (isec->name == section_names::compactUnwind)
+        populateCompactUnwinds(compactUnwinds, map);
+      else if (isec->name == section_names::ehFrame)
+        populateEhFrameFDEs(ehFrameFDEs, map);
+    }
+
+  for (const SubsectionMap &map : subsections) {
+    if (!isCodeSection(isec))
+      continue;
+    for (const SubsectionEntry &entry : map) {
+      ConcatInputSection *isec = get<ConcatInputSection>(entry.isec);
+    }
+  }
+
+  // iterate over CUE, make map for function addresses
+  // parse DWARF into a vector of CIEs & FDEs, make map for function addresses
+  // make map for __gcc_except_tab subsection offsets
+  // for __text subsections:
+  //   if (CUE[s])
+  //     keep the CUE
+  //   else if (FDE[s])
+  //     mark FDE as live, create CUE to reference FDE
+  //   else
+  //     create degenerate CUE
+}
+
 template <class LP> void ObjFile::parse() {
   using Header = typename LP::mach_header;
   using SegmentCommand = typename LP::segment_command;
   using Section = typename LP::section;
   using NList = typename LP::nlist;
 
   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   auto *hdr = reinterpret_cast<const Header *>(mb.getBufferStart());
if (const load_command *cmd = findCommand(hdr, LC_SYMTAB)) {
     auto *c = reinterpret_cast<const symtab_command *>(cmd);
     ArrayRef<NList> nList(reinterpret_cast<const NList *>(buf + c->symoff),
                           c->nsyms);
     const char *strtab = reinterpret_cast<const char *>(buf) + c->stroff;
     bool subsectionsViaSymbols = hdr->flags & MH_SUBSECTIONS_VIA_SYMBOLS;
     parseSymbols<LP>(sectionHeaders, nList, strtab, subsectionsViaSymbols);
   }
 
+  parseUnwindInfo();
+
   // The relocations may refer to the symbols, so we parse them after we have
   // parsed all the symbols.
   for (size_t i = 0, n = subsections.size(); i < n; ++i)
     if (!subsections[i].empty())
       parseRelocations(sectionHeaders, sectionHeaders[i], subsections[i]);
 
   parseDebugInfo();
   if (config->emitDataInCodeInfo)

lld/MachO/InputSection.h

 class Defined;
 
 class InputSection {
 public:
   enum Kind {
     ConcatKind,
     CStringLiteralKind,
     WordLiteralKind,
+    EhFrameKind,
   };
 
   Kind kind() const { return shared->sectionKind; }
   virtual ~InputSection() = default;
   virtual uint64_t getSize() const { return data.size(); }
   InputFile *getFile() const { return shared->file; }
   StringRef getName() const { return shared->name; }
   StringRef getSegName() const { return shared->segname; }
return sectionType(flags) == llvm::MachO::S_4BYTE_LITERALS ||
          sectionType(flags) == llvm::MachO::S_8BYTE_LITERALS ||
          sectionType(flags) == llvm::MachO::S_16BYTE_LITERALS;
 }
 
 bool isCodeSection(const InputSection *);
 
 bool isCfStringSection(const InputSection *);
 
+template <class Ptr> struct EhFrameRecord {
+  EhFrameRecord(ArrayRef<uint8_t> data) : data(data) {}
+
+  void parse();
+
+  ArrayRef<uint8_t> data;
+
+  // In the object file, according to DWARF ...
+  // CIE: id == 0
+  // FDE: id is the backward offset to its CIE
+  // While parsing records, id holds the value read from the record.
+  //
+  // After parsing ...
+  // CIE: id == ~0
+  // FDE: id is the index for its CIE within EhFrameInputSection::records[]
+  uint32_t id;
+  uint8_t personalityEncoding;
+  uint8_t lsdaEncoding;
+  uint8_t fdeEncocding;
+
+  // The CIE optionally contains a pointer to the personality function, and
+  // MachO has a relocation_info for it.
+  //
+  // The FDE contains the function address, and optionally the LSDA address, but
+  // MachO does not have relocation_info for either, so we need to write code to
+  // handle relocation fixups. The values for the fixups are the addresses
+  // assigned to the ConcatInputSection for the function and LSDA respectively.
+  //
+  // These two offsets within the FDE identify the location(s) to fixup within
+  // the FDE data.
+  uint8_t personalityOffset;
+  uint8_t funcAddrOffset;
+  uint8_t lsdaOffset;
+};
+
+// This corresponds to a __eh_frame section of an input file.
+template <class Ptr> class EhFrameInputSection : public InputSection {
+public:
+  EhFrameInputSection(StringRef segname, StringRef name)
+      : InputSection(EhFrameKind, segname, name) {}
+
+  EhFrameInputSection(StringRef segname, StringRef name, InputFile *file,
+                      ArrayRef<uint8_t> data, uint32_t align = 1,
+                      uint32_t flags = 0)
+      : InputSection(EhFrameKind, segname, name, file, data, align, flags) {}
+
+  // FIXME: stubbed for now
+  uint64_t getOffset(uint64_t off) const override { return off; }
+  bool isLive(uint64_t off) const override { return true; }
+  void markLive(uint64_t off) override {}
+
+  ArrayRef<uint8_t> getEhRecordData(uint64_t off);
+  void splitIntoRecords();
+
+  static bool classof(const InputSection *isec) {
+    return isec->kind() == EhFrameKind;
+  }
+
+  std::vector<EhFrameRecord<Ptr>> records;
+};
+
 extern std::vector<ConcatInputSection *> inputSections;
 
 namespace section_names {
 
 constexpr const char authGot[] = "__auth_got";
 constexpr const char authPtr[] = "__auth_ptr";
 constexpr const char binding[] = "__binding";
 constexpr const char bitcodeBundle[] = "__bundle";
 constexpr const char cString[] = "__cstring";
 constexpr const char cfString[] = "__cfstring";
 constexpr const char codeSignature[] = "__code_signature";
 constexpr const char common[] = "__common";
 constexpr const char compactUnwind[] = "__compact_unwind";
 constexpr const char data[] = "__data";
 constexpr const char debugAbbrev[] = "__debug_abbrev";
 constexpr const char debugInfo[] = "__debug_info";
 constexpr const char debugStr[] = "__debug_str";
 constexpr const char ehFrame[] = "__eh_frame";
+constexpr const char gccExceptTab[] = "__gcc_except_tab";
 constexpr const char export_[] = "__export";
 constexpr const char dataInCode[] = "__data_in_code";
 constexpr const char functionStarts[] = "__func_starts";
 constexpr const char got[] = "__got";
 constexpr const char header[] = "__mach_header";
 constexpr const char indirectSymbolTable[] = "__ind_sym_tab";
 constexpr const char const_[] = "__const";
 constexpr const char lazySymbolPtr[] = "__la_symbol_ptr";

lld/MachO/InputSection.cpp

 #include "InputFiles.h"
 #include "OutputSegment.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "UnwindInfoSection.h"
 #include "Writer.h"
 #include "lld/Common/Memory.h"
+#include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/xxhash.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::support;
+using namespace llvm::support::endian;
 using namespace lld;
 using namespace lld::macho;
 
 std::vector<ConcatInputSection *> macho::inputSections;
 
 uint64_t InputSection::getFileSize() const {
   return isZeroFill(getFlags()) ? 0 : getSize();
 }
case S_8BYTE_LITERALS:
     return osec->getLiteral8Offset(buf + off);
   case S_16BYTE_LITERALS:
     return osec->getLiteral16Offset(buf + off);
   default:
     llvm_unreachable("invalid literal section type");
   }
 }
 
+static void fatalAt(const InputSection *isec, const ArrayRef<uint8_t> &data,
+                    const Twine &msg) {
+  uint64_t offset = data.data() - isec->data.data();
+  fatal("corrupted __eh_frame at offset=" + utohexstr(offset) + ": " + msg +
+        "\n>>> defined in " + toString(isec->getFile()));
+}
+
+uint32_t EhFrameRecord::parse(EhFrameInputSection *isec,
+                              ArrayRef<uint8_t> front) {
+  data = front;
+  if (data.size() < 4)
+    fatalAt(isec, data, "CIE/FDE too small");
+  uint8_t *buf = data.data();
+  uint64_t length = read32le(buf);
+  buf += 4;
+  if (length == UINT32_MAX)
+    fatalAt(isec, data, "CIE/FDE too large");
+  length += 4;
+  if (length > data.size())
+    fatalAt(isec, data, "CIE/FDE ends past the end of the section");
+  data = data.take_front(length);
+
+  id = read32le(buf);
+  buf += 4;
+  if (id == 0) {
+    // CIE
+    uint8_t version = *buf++;
+    assert(version == 1);
+    auto *augmentation = reinterpret_cast<const char *>(buf);
+    buf += strlen(augmentation) + 1;
+    ++buf; // skip code alignment factor
+    ++buf; // skip data alignment factor
+    ++buf; // skip return address register
+    while (*augmentation++)
+      switch (*augmentation) {
+      case 'z':
+        ++buf; // skip augmentation length
+        break;
+      case 'P':
+        personalityEncoding = *buf++;
+        assert(personalityEncoding ==
+               (DW_EH_PE_sdata4 | DW_EH_PE_pcrel | DW_EH_PE_indirect));
+        personalityOffset = buf - data.data();
+        buf += 4;
+        break;
+      case 'L':
+        lsdaEncoding = *buf++;
+        assert(lsdaEncoding == DW_EH_PE_pcrel);
+        break;
+      case 'R':
+        fdeEncocding = *buf++;
+        assert(fdeEncocding == DW_EH_PE_pcrel);
+        break;
+      case 'S':
+      case 'B':
+        break;
+      default:
+        llvm_unreachable("unknown DWARF EH augmentation char");
+      }
+  } else {
+    // FDE
+    funcAddrOffset = buf - data.data();
+    buf += target->wordSize; // skip function address
+    buf += target->wordSize; // skip function length
+    ++buf;                   // skip augmentation length
+    lsdaOffset = buf - data.data();
+    buf += target->wordSize; // skip LSDA address
+  }
+}
+
+void EhFrameInputSection::splitIntoRecords() {
+  size_t off = 0;
+  size_t idx = 0;
+  DenseMap<uint32_t, size_t> recordIndex;
+  while (off < data.size()) {
+    records.emplace_back();
+    EhFrameRecord &record = records.back();
+    record.parse(this, data.drop_front(off));
+    record.id = record.id ? recordIndex[off - record.id] : UINT32_MAX;
+    if (record.id > idx)
+      fatalAt(this, data, "malformed ID in EhFrame record");
+    off += record.data.size();
+    ++idx;
+  }
+}
+
 bool macho::isCodeSection(const InputSection *isec) {
   uint32_t type = sectionType(isec->getFlags());
   if (type != S_REGULAR && type != S_COALESCED)
     return false;
 
   uint32_t attr = isec->getFlags() & SECTION_ATTRIBUTES_USR;
   if (attr == S_ATTR_PURE_INSTRUCTIONS)
     return true;

lld/MachO/SyntheticSections.h

 namespace lld {
 namespace macho {
 
 class Defined;
 class DylibSymbol;
 class LoadCommand;
 class ObjFile;
 class UnwindInfoSection;
+class EhFrameSection;
 
 class SyntheticSection : public OutputSection {
 public:
   SyntheticSection(const char *segname, const char *name);
   virtual ~SyntheticSection() = default;
 
   static bool classof(const OutputSection *sec) {
     return sec->kind() == SyntheticKind;
struct InStruct {
   LazyBindingSection *lazyBinding = nullptr;
   ExportSection *exports = nullptr;
   GotSection *got = nullptr;
   TlvPointerSection *tlvPointers = nullptr;
   LazyPointerSection *lazyPointers = nullptr;
   StubsSection *stubs = nullptr;
   StubHelperSection *stubHelper = nullptr;
   UnwindInfoSection *unwindInfo = nullptr;
+  EhFrameSection *ehFrame = nullptr;
   ConcatInputSection *imageLoaderCache = nullptr;
 };
 
 extern InStruct in;
 extern std::vector<SyntheticSection *> syntheticSections;
 
 void createSyntheticSymbols();
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/UnwindInfoSection.h

protected:
 
   ConcatOutputSection *compactUnwindSection;
   uint64_t unwindInfoSize = 0;
   bool allEntriesAreOmitted = true;
 };
 
 UnwindInfoSection *makeUnwindInfoSection();
 
+class EhFrameSection : public SyntheticSection {
+public:
+  bool isNeeded() const override {
+    return !ehFrameInputSection->records.empty() && !allEntriesAreOmitted;
+  }
+  uint64_t getSize() const override { return ehFrameSize; }
+  virtual void addInput(EhFrameInputSection *) = 0;
+  std::vector<EhFrameRecord> getPieces() {
+    return ehFrameInputSection->records;
+  }
+  void prepareRelocations();
+
+protected:
+  EhFrameSection();
+  virtual void prepareRelocations(EhFrameInputSection *) = 0;
+
+  EhFrameInputSection *ehFrameInputSection;
+  uint64_t ehFrameSize = 0;
+  bool allEntriesAreOmitted = true;
+};
+
+EhFrameSection *makeEhFrameSection();
+
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/UnwindInfoSection.cpp

private:
   // Indices of personality functions within the GOT.
   std::vector<Ptr> personalities;
   SmallDenseMap<std::pair<InputSection *, uint64_t /* addend */>, Symbol *>
       personalityTable;
   std::vector<unwind_info_section_header_lsda_index_entry> lsdaEntries;
   // Map of function offset (from the image base) to an index within the LSDA
   // array.
   DenseMap<uint32_t, uint32_t> functionToLsdaIndex;
+  // std::vector<EhFrameEntry<Ptr>> ehVector;
   std::vector<CompactUnwindEntry<Ptr>> cuVector;
   std::vector<CompactUnwindEntry<Ptr> *> cuPtrVector;
   std::vector<SecondLevelPage> secondLevelPages;
   uint64_t level2PagesOffset = 0;
 };
 
 UnwindInfoSection::UnwindInfoSection()
     : SyntheticSection(segment_names::text, section_names::unwindInfo) {
template <class Ptr> void UnwindInfoSectionImpl<Ptr>::finalize() {
   // the number of CU entries by as much as 3 orders of magnitude!
   compactUnwindSection->finalize();
   assert(compactUnwindSection->getSize() % sizeof(CompactUnwindEntry<Ptr>) ==
          0);
   size_t cuCount =
       compactUnwindSection->getSize() / sizeof(CompactUnwindEntry<Ptr>);
   cuVector.resize(cuCount);
   relocateCompactUnwind(compactUnwindSection, cuVector);
-
+  // removeRedundantEhFrameEntries(ehVector, cuVector);
   addEntriesForFunctionsWithoutUnwindInfo(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(cuVector.size());
   for (CompactUnwindEntry<Ptr> &cuEntry : cuVector)
     cuPtrVector.emplace_back(&cuEntry);
   llvm::sort(cuPtrVector, [](const CompactUnwindEntry<Ptr> *a,

 }
 
 UnwindInfoSection *macho::makeUnwindInfoSection() {
   if (target->wordSize == 8)
     return make<UnwindInfoSectionImpl<uint64_t>>();
   else
     return make<UnwindInfoSectionImpl<uint32_t>>();
 }
+
+EhFrameSection::EhFrameSection()
+    : SyntheticSection(segment_names::text, section_names::ehFrame) {
+  align = 4;
+  ehFrameSection = make<EhFrameSection>(section_names::ehFrameSection);
+}
+
+template <class Ptr>
+void UnwindInfoSectionImpl<Ptr>::addInput(EhFrameInputSection *isec) {
+  assert(isec->getName() == section_names::ehFrame);
+  ehFrameSection->addInput(isec);
+}
+
+EhFrameSection *macho::makeEhFrameSection() {
+  if (target->wordSize == 8)
+    return make<EhFrameSectionImpl<uint64_t>>();
+  else
+    return make<EhFrameSectionImpl<uint32_t>>();
+}