Add .eh_frame_hdr search to Linux unwinder.

[danalbert]

Summary

This improves the performance of unwinding on DWARF based targets. The
32-bit x86 support for scanning the full eh_frame
(CFI_Parser::findFDE) apparently does not work (at least not on
Linux). Since the eh_frame_hdr code delegates to that, this still
doesn't work for x86 Linux, but it has been tested on x86_64 Linux and
aarch64 Android.

[danalbert]

This is passing all of the tests for x86_64, but I'm still having some (seemingly unrelated trouble) with x86. On x86, I'm seeing a bogus return address coming from the CFI here: https://github.com/llvm-mirror/libcxxabi/blob/master/src/Unwind/DwarfInstructions.hpp#L187 So far I haven't had any luck in figuring out why.

In theory this should work for aarch64 too, but I haven't had a chance to test that.

The commit message is actually not correct. This should work for the BSDs as well.

[jroelofs]

src/Unwind/AddressSpace.hpp

375

Do byval captures not work here?

383

As an optimization, I think you can bail early here if the targetAddr cannot possibly be in the particular *.so:

if (cbdata->targetAddr < pinfo->dlpi_addr)
  return false;

409

src/Unwind/EHHeaderParser.hpp

112

The EHABI unwinder uses some library function for doing its binary search for the EHT entry. Maybe that can be re-used here too.

src/Unwind/UnwindCursor.hpp

839

It's interesting that the cache lookup isn't first. I wonder why (not really important for this review).

src/Unwind/config.h

86–88

I think one of @joerg's platforms uses dwarf unwind on arm. I don't remember the name of the guard he created to detect that though.

[dschuff]

src/Unwind/config.h

86–88

elsewhere in libcxxabi there are ifdefs for ARM_DWARF_EH

[danalbert]

src/Unwind/AddressSpace.hpp

375

No captures whatsoever. Those only work where the function actually takes a std::function, whereas this is a plain old function pointer.

409

src/Unwind/EHHeaderParser.hpp

112

I'll look in to that.

[joerg]

src/Unwind/EHHeaderParser.hpp

120

Isn't this wrong if you hit a case exactly?

[danalbert]

Address review comments.

[danalbert]

src/Unwind/EHHeaderParser.hpp

112

The case you were thinking of is https://github.com/llvm-mirror/libcxxabi/blob/master/src/Unwind/UnwindCursor.hpp#L676

That's a dependency on libc++, and you've been trying to fix the layering issues here. I don't think I'll add to them :)

[jroelofs]

src/Unwind/EHHeaderParser.hpp

112

yeah, that's it. I forgot it was using something from std::. Agreed, no need to add one more layering problem.

[danalbert]

Follow same header search pattern as netbsd at nbjoerg's suggestion.

[jroelofs]

@danalbert: reminder so you don't forget about this before @compnerd moves the unwdiner.

[ed]

Just stumbled upon this patch and thought I'd chime in briefly.

I am currently working on a POSIX-like environment that is completely built around the concept of capability-based security which I am planning on releasing under a BSD license 1-2 months from now. I'm leaning on LLVM components quite heavily (LLVM, Clang, libcxx, libcxxabi, compiler-rt).

To get exceptions working in my environment I previously used a small patch to ld's linker script to add symbols where .eh_frame begins/ends and a change for libcxxabi to use those. After discovering this patch I decided to add dl_iterate_phdr() as well and revert my local changes. So far things work great. All libcxx exception related tests pass properly. At least on x86-64.

That said, keep in mind that ElfW() does not exist on FreeBSD. Adding some code like this makes the code build properly.

#ifndef ElfW                                                                     
#define ElfW(type) ElfW2(__INTPTR_WIDTH__, type)
#define ElfW2(width, type) ElfW3(width, type)
#define ElfW3(width, type) Elf##width##_##type
#endif

Thanks!

[danalbert]

Fix the base address for the unwind table.

Apparently this hadn't actually been working before. The header search was
failing, and then the seach was falling back to scanning the whole table.
Thanks to Saleem for noticing my mistake.

Unfortunately this means that we can't actually test this code directly. If it
fails to find the entry in the search table, it will still find it by scanning
the whole section. We should probably add some real unit tests to this project
at some point to deal with this.

[compnerd]

Looks like it should be okay beyond the inline comments.

src/Unwind/EHHeaderParser.hpp

34

Can you change these to the specification specified names? It makes it easier to cross-reference.

src/Unwind/config.h

86

Does clang-format format this statement this way?

[danalbert]

Make the header info names match the names in the spec.

[danalbert]

src/Unwind/config.h

86

clang-format hates everything about this project. The other defines in the file match this.

[danalbert]

Closed as http://reviews.llvm.org/rL230802

src/Unwind/AddressSpace.hpp

 struct EHTEntry {
   uint32_t functionOffset;
   uint32_t unwindOpcodes;
 };
 extern EHTEntry __exidx_start;
 extern EHTEntry __exidx_end;
 #endif // !defined(_LIBUNWIND_IS_BAREMETAL)
 
+#elif _LIBUNWIND_SUPPORT_DWARF_UNWIND
+#include <link.h>
+#include "EHHeaderParser.hpp"
 #endif  // LIBCXXABI_ARM_EHABI
 
 namespace libunwind {
 
 /// Used by findUnwindSections() to return info about needed sections.
 struct UnwindInfoSections {
 #if _LIBUNWIND_SUPPORT_DWARF_UNWIND || _LIBUNWIND_SUPPORT_DWARF_INDEX ||       \
     _LIBUNWIND_SUPPORT_COMPACT_UNWIND
v128             getVector(pint_t addr) {
     v128 val;
     memcpy(&val, (void *)addr, sizeof(val));
     return val;
   }
   uintptr_t       getP(pint_t addr);
   static uint64_t getULEB128(pint_t &addr, pint_t end);
   static int64_t  getSLEB128(pint_t &addr, pint_t end);
 
-  pint_t getEncodedP(pint_t &addr, pint_t end, uint8_t encoding);
+  pint_t getEncodedP(pint_t &addr, pint_t end, uint8_t encoding,
+                     pint_t datarelBase = 0);
   bool findFunctionName(pint_t addr, char *buf, size_t bufLen,
                         unw_word_t *offset);
   bool findUnwindSections(pint_t targetAddr, UnwindInfoSections &info);
   bool findOtherFDE(pint_t targetAddr, pint_t &fde);
 
   static LocalAddressSpace sThisAddressSpace;
 };
 
inline int64_t LocalAddressSpace::getSLEB128(pint_t &addr, pint_t end) {
   } while (byte & 0x80);
   // sign extend negative numbers
   if ((byte & 0x40) != 0)
     result |= (-1LL) << bit;
   addr = (pint_t) p;
   return result;
 }
 
-inline LocalAddressSpace::pint_t LocalAddressSpace::getEncodedP(pint_t &addr,
-                                                         pint_t end,
-                                                         uint8_t encoding) {
+inline LocalAddressSpace::pint_t
+LocalAddressSpace::getEncodedP(pint_t &addr, pint_t end, uint8_t encoding,
+                               pint_t datarelBase) {
   pint_t startAddr = addr;
   const uint8_t *p = (uint8_t *)addr;
   pint_t result;
 
   // first get value
   switch (encoding & 0x0F) {
   case DW_EH_PE_ptr:
     result = getP(addr);
case DW_EH_PE_absptr:
     break;
   case DW_EH_PE_pcrel:
     result += startAddr;
     break;
   case DW_EH_PE_textrel:
     _LIBUNWIND_ABORT("DW_EH_PE_textrel pointer encoding not supported");
     break;
   case DW_EH_PE_datarel:
-    _LIBUNWIND_ABORT("DW_EH_PE_datarel pointer encoding not supported");
+    // DW_EH_PE_datarel is only valid in a few places, so the parameter has a
+    // default value of 0, and we abort in the event that someone calls this
+    // function with a datarelBase of 0 and DW_EH_PE_datarel encoding.
+    if (datarelBase == 0)
+      _LIBUNWIND_ABORT("DW_EH_PE_datarel is invalid with a datarelBase of 0");
+    result += datarelBase;
     break;
   case DW_EH_PE_funcrel:
     _LIBUNWIND_ABORT("DW_EH_PE_funcrel pointer encoding not supported");
     break;
   case DW_EH_PE_aligned:
     _LIBUNWIND_ABORT("DW_EH_PE_aligned pointer encoding not supported");
     break;
   default:
#else
   info.arm_section = (uintptr_t) dl_unwind_find_exidx(
       (_Unwind_Ptr) targetAddr, &length);
   info.arm_section_length = (uintptr_t)length;
  #endif
   _LIBUNWIND_TRACE_UNWINDING("findUnwindSections: section %X length %x\n",
                              info.arm_section, info.arm_section_length);
   if (info.arm_section && info.arm_section_length)
     return true;
+#elif _LIBUNWIND_SUPPORT_DWARF_UNWIND
+#if _LIBUNWIND_SUPPORT_DWARF_INDEX
+  struct dl_iterate_cb_data {
+    LocalAddressSpace *addressSpace;
+    UnwindInfoSections *sects;
+    uintptr_t targetAddr;
+  };
+
+  dl_iterate_cb_data cb_data = {this, &info, targetAddr};
+  int found = dl_iterate_phdr(
+      [](struct dl_phdr_info *pinfo, size_t, void *data) -> int {
+        auto cbdata = static_cast<dl_iterate_cb_data *>(data);
+        size_t object_length;
+        bool found_obj = false;
+        bool found_hdr = false;
+
+        assert(cbdata);
+        assert(cbdata->sects);
+
+        if (cbdata->targetAddr < pinfo->dlpi_addr) {
+          return false;
+        }
+
+        for (ElfW(Half) i = 0; i < pinfo->dlpi_phnum; i++) {
+          const ElfW(Phdr) *phdr = &pinfo->dlpi_phdr[i];
+          if (phdr->p_type == PT_LOAD) {
+            uintptr_t begin = pinfo->dlpi_addr + phdr->p_vaddr;
+            uintptr_t end = begin + phdr->p_memsz;
+            if (cbdata->targetAddr >= begin && cbdata->targetAddr < end) {
+              cbdata->sects->dso_base = begin;
+              object_length = phdr->p_memsz;
+              found_obj = true;
+            }
+          } else if (phdr->p_type == PT_GNU_EH_FRAME) {
+            EHHeaderParser<LocalAddressSpace>::EHHeaderInfo hdrInfo;
+            uintptr_t eh_frame_hdr_start = pinfo->dlpi_addr + phdr->p_vaddr;
+            cbdata->sects->dwarf_index_section = eh_frame_hdr_start;
+            cbdata->sects->dwarf_index_section_length = phdr->p_memsz;
+            EHHeaderParser<LocalAddressSpace>::decodeEHHdr(
+                *cbdata->addressSpace, eh_frame_hdr_start, phdr->p_memsz,
+                hdrInfo);
+            cbdata->sects->dwarf_section = hdrInfo.ehFramePtr;
+            found_hdr = true;
+          }
+        }
+
+        if (found_obj && found_hdr) {
+          cbdata->sects->dwarf_section_length = object_length;
+          return true;
+        } else {
+          return false;
+        }
+      },
+      &cb_data);
+  return static_cast<bool>(found);
+#else
+#error "_LIBUNWIND_SUPPORT_DWARF_UNWIND requires _LIBUNWIND_SUPPORT_DWARF_INDEX on this platform."
+#endif
 #endif
 
   return false;
 }
 
 
 inline bool LocalAddressSpace::findOtherFDE(pint_t targetAddr, pint_t &fde) {
 #ifdef __APPLE__
public:
 
   uint8_t   get8(pint_t addr);
   uint16_t  get16(pint_t addr);
   uint32_t  get32(pint_t addr);
   uint64_t  get64(pint_t addr);
   pint_t    getP(pint_t addr);
   uint64_t  getULEB128(pint_t &addr, pint_t end);
   int64_t   getSLEB128(pint_t &addr, pint_t end);
-  pint_t    getEncodedP(pint_t &addr, pint_t end, uint8_t encoding);
+  pint_t    getEncodedP(pint_t &addr, pint_t end, uint8_t encoding,
+                        pint_t datarelBase = 0);
   bool      findFunctionName(pint_t addr, char *buf, size_t bufLen,
                         unw_word_t *offset);
   bool      findUnwindSections(pint_t targetAddr, UnwindInfoSections &info);
   bool      findOtherFDE(pint_t targetAddr, pint_t &fde);
 private:
   void *localCopy(pint_t addr);
 
   task_t fTask;

src/Unwind/EHHeaderParser.hpp

+//===------------------------- EHHeaderParser.hpp -------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//
+//  Parses ELF .eh_frame_hdr sections.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef __EHHEADERPARSER_HPP__
+#define __EHHEADERPARSER_HPP__
+
+#include "libunwind.h"
+
+#include "AddressSpace.hpp"
+#include "DwarfParser.hpp"
+
+namespace libunwind {
+
+/// \brief EHHeaderParser does basic parsing of an ELF .eh_frame_hdr section.
+///
+/// See DWARF spec for details:
+///    http://refspecs.linuxbase.org/LSB_3.1.0/LSB-Core-generic/LSB-Core-generic/ehframechpt.html
+///
+template <typename A> class EHHeaderParser {
+public:
+  typedef typename A::pint_t pint_t;
+
+  /// Information encoded in the EH frame header.
+  struct EHHeaderInfo {
+    pint_t ehFramePtr;
+    size_t fdeCount;
+    pint_t searchTable;
+    uint8_t searchTableEnc;
+  };
+
+  static void decodeEHHdr(A &addressSpace, pint_t ehHdrStart, pint_t ehHdrEnd,
+                          EHHeaderInfo &ehHdrInfo);
+  static bool findFDE(A &addressSpace, pint_t pc, pint_t ehHdrStart,
+                      uint32_t sectionLength,
+                      typename CFI_Parser<A>::FDE_Info *fdeInfo,
+                      typename CFI_Parser<A>::CIE_Info *cieInfo);
+
+private:
+  static bool decodeTableEntry(A &addressSpace, pint_t &tableEntry,
+                               pint_t ehHdrStart, pint_t ehHdrEnd,
+                               uint8_t tableEnc,
+                               typename CFI_Parser<A>::FDE_Info *fdeInfo,
+                               typename CFI_Parser<A>::CIE_Info *cieInfo);
+  static size_t getTableEntrySize(uint8_t tableEnc);
+};
+
+template <typename A>
+void EHHeaderParser<A>::decodeEHHdr(A &addressSpace, pint_t ehHdrStart,
+                                    pint_t ehHdrEnd, EHHeaderInfo &ehHdrInfo) {
+  pint_t p = ehHdrStart;
+  uint8_t version = addressSpace.get8(p++);
+  if (version != 1)
+    _LIBUNWIND_ABORT("Unsupported .eh_frame_hdr version");
+
+  uint8_t ehFramePtrEnc = addressSpace.get8(p++);
+  uint8_t fdeCountEnc = addressSpace.get8(p++);
+  ehHdrInfo.searchTableEnc = addressSpace.get8(p++);
+
+  ehHdrInfo.ehFramePtr =
+      addressSpace.getEncodedP(p, ehHdrEnd, ehFramePtrEnc, ehHdrStart);
+  ehHdrInfo.fdeCount =
+      addressSpace.getEncodedP(p, ehHdrEnd, fdeCountEnc, ehHdrStart);
+  ehHdrInfo.searchTable = p;
+}
+
+template <typename A>
+bool EHHeaderParser<A>::decodeTableEntry(
+    A &addressSpace, pint_t &tableEntry, pint_t ehHdrStart, pint_t ehHdrEnd,
+    uint8_t tableEnc, typename CFI_Parser<A>::FDE_Info *fdeInfo,
+    typename CFI_Parser<A>::CIE_Info *cieInfo) {
+  // Have to decode the whole FDE for the PC range anyway, so just throw away
+  // the PC start.
+  addressSpace.getEncodedP(tableEntry, ehHdrEnd, tableEnc, ehHdrStart);
+  pint_t fde =
+      addressSpace.getEncodedP(tableEntry, ehHdrEnd, tableEnc, ehHdrStart);
+  const char *message =
+      CFI_Parser<A>::decodeFDE(addressSpace, fde, fdeInfo, cieInfo);
+  if (message != NULL) {
+    _LIBUNWIND_DEBUG_LOG("EHHeaderParser::decodeTableEntry: bad fde: %s\n",
+                         message);
+    return false;
+  }
+
+  return true;
+}
+
+template <typename A>
+bool EHHeaderParser<A>::findFDE(A &addressSpace, pint_t pc, pint_t ehHdrStart,
+                                uint32_t sectionLength,
+                                typename CFI_Parser<A>::FDE_Info *fdeInfo,
+                                typename CFI_Parser<A>::CIE_Info *cieInfo) {
+  pint_t ehHdrEnd = ehHdrStart + sectionLength;
+
+  EHHeaderParser<A>::EHHeaderInfo hdrInfo;
+  EHHeaderParser<A>::decodeEHHdr(addressSpace, ehHdrStart, ehHdrEnd, hdrInfo);
+
+  size_t tableEntrySize = getTableEntrySize(hdrInfo.searchTableEnc);
+  pint_t tableEntry;
+
+  size_t low = 0;
+  for (size_t len = hdrInfo.fdeCount; len > 1;) {
+    size_t mid = low + (len / 2);
+    tableEntry = hdrInfo.searchTable + mid * tableEntrySize;
+    pint_t start = addressSpace.getEncodedP(tableEntry, ehHdrEnd,
+                                            hdrInfo.searchTableEnc, ehHdrStart);
+
+    if (start == pc) {
+      low = mid;
+      break;
+    } else if (start < pc) {
+      low = mid;
+      len -= (len / 2);
+    } else {
+      len /= 2;
+    }
+  }
+
+  tableEntry = hdrInfo.searchTable + low * tableEntrySize;
+  if (decodeTableEntry(addressSpace, tableEntry, ehHdrStart, ehHdrEnd,
+                       hdrInfo.searchTableEnc, fdeInfo, cieInfo)) {
+    if (pc >= fdeInfo->pcStart && pc < fdeInfo->pcEnd)
+      return true;
+  }
+
+  return false;
+}
+
+template <typename A>
+size_t EHHeaderParser<A>::getTableEntrySize(uint8_t tableEnc) {
+  switch (tableEnc & 0x0f) {
+  case DW_EH_PE_sdata2:
+  case DW_EH_PE_udata2:
+    return 4;
+  case DW_EH_PE_sdata4:
+  case DW_EH_PE_udata4:
+    return 8;
+  case DW_EH_PE_sdata8:
+  case DW_EH_PE_udata8:
+    return 16;
+  case DW_EH_PE_sleb128:
+  case DW_EH_PE_uleb128:
+    _LIBUNWIND_ABORT("Can't binary search on variable length encoded data.");
+  case DW_EH_PE_omit:
+    return 0;
+  default:
+    _LIBUNWIND_ABORT("Unknown DWARF encoding for search table.");
+  }
+}
+
+}
+
+#endif

src/Unwind/UnwindCursor.hpp

 #endif
 
 #include "config.h"
 
 #include "AddressSpace.hpp"
 #include "CompactUnwinder.hpp"
 #include "config.h"
 #include "DwarfInstructions.hpp"
+#include "EHHeaderParser.hpp"
 #include "libunwind.h"
 #include "Registers.hpp"
 #include "Unwind-EHABI.h"
 
 namespace libunwind {
 
 #if _LIBUNWIND_SUPPORT_DWARF_UNWIND
 /// Cache of recently found FDEs.
bool UnwindCursor<A, R>::getInfoFromDwarfSection(pint_t pc,
   if (fdeSectionOffsetHint != 0) {
     foundFDE = CFI_Parser<A>::findFDE(_addressSpace, pc, sects.dwarf_section,
                                     (uint32_t)sects.dwarf_section_length,
                                     sects.dwarf_section + fdeSectionOffsetHint,
                                     &fdeInfo, &cieInfo);
   }
 #if _LIBUNWIND_SUPPORT_DWARF_INDEX
   if (!foundFDE && (sects.dwarf_index_section != 0)) {
-    // Have eh_frame_hdr section which is index into dwarf section.
-    // TO DO: implement index search
+    foundFDE = EHHeaderParser<A>::findFDE(
+        _addressSpace, pc, sects.dwarf_index_section,
+        (uint32_t)sects.dwarf_index_section_length, &fdeInfo, &cieInfo);
   }
 #endif
   if (!foundFDE) {
     // otherwise, search cache of previously found FDEs.
     pint_t cachedFDE = DwarfFDECache<A>::findFDE(sects.dso_base, pc);
     if (cachedFDE != 0) {
       foundFDE =
           CFI_Parser<A>::findFDE(_addressSpace, pc, sects.dwarf_section,
                                  (uint32_t)sects.dwarf_section_length,
                                  cachedFDE, &fdeInfo, &cieInfo);
       foundInCache = foundFDE;
     }

src/Unwind/config.h

#else
   #define _LIBUNWIND_SUPPORT_FRAME_APIS   (defined(__i386__) || \
                                            defined(__x86_64__))
   #define _LIBUNWIND_EXPORT               __attribute__((visibility("default")))
   #define _LIBUNWIND_HIDDEN               __attribute__((visibility("hidden")))
   #define _LIBUNWIND_LOG(msg, ...) fprintf(stderr, "libuwind: " msg, __VA_ARGS__)
   #define _LIBUNWIND_ABORT(msg) assert_rtn(__func__, __FILE__, __LINE__, msg)
 
   #define _LIBUNWIND_SUPPORT_COMPACT_UNWIND 0
-  #define _LIBUNWIND_SUPPORT_DWARF_UNWIND   0
-  #define _LIBUNWIND_SUPPORT_DWARF_INDEX    0
+  #define _LIBUNWIND_SUPPORT_DWARF_UNWIND !defined(__arm__) || \
+                                          defined(__ARM_DWARF_EH__)
+  #define _LIBUNWIND_SUPPORT_DWARF_INDEX _LIBUNWIND_SUPPORT_DWARF_UNWIND
 #endif
 
 
 // Macros that define away in non-Debug builds
 #ifdef NDEBUG
   #define _LIBUNWIND_DEBUG_LOG(msg, ...)
   #define _LIBUNWIND_TRACE_API(msg, ...)
   #define _LIBUNWIND_TRACING_UNWINDING 0