Breakpad: Generate unwind plans from STACK CFI records

Summary:
This patch implements the GetUnwindPlan interface (added in the previous
patch) for SymbolFileBreakpad, and uses it to generate unwind plans from
STACK CFI records in breakpad files.

We first perform a light-weight parse of the breakpad in order to build
up a map of regions covered by the unwind info so that we can later jump
to the right record when we need to unwind a specific function.

The actual parsing is relatively straight-forward, as the STACK CFI records
are just another (text) form of the eh_frame unwind instructions, and
the same goes for lldb's UnwindPlans. The newly-introduced
PostfixExpression API is used to convert the breakpad postfix
expressions into DWARF. The generated dwarf expressions are stored in a
BumpPtrAllocator, as the UnwindPlan does not take ownership of the
expression data it references (usually this is static data in an object
file, so special ownership is needed).

At this moment the generated unwind plans aren't used in the actual
unwind machinery (only in the image show-unwind command), but that is
coming in a separate patch.

Reviewers: amccarth, clayborg, markmentovai

Subscribers: aprantl, jasonmolenda, lldb-commits

Differential Revision: https://reviews.llvm.org/D61733

llvm-svn: 360574

5 files changed, 298 insertions, 2 deletions

diff --git a/lldb/lit/SymbolFile/Breakpad/Inputs/stack-cfi-parsing.syms b/lldb/lit/SymbolFile/Breakpad/Inputs/stack-cfi-parsing.syms
new file mode 100644
index 00000000000..1ebecb48022
--- /dev/null
+++ b/lldb/lit/SymbolFile/Breakpad/Inputs/stack-cfi-parsing.syms
@@ -0,0 +1,20 @@
+MODULE Linux x86_64 E5894855C35DCCCCCCCCCCCCCCCCCCCC0 linux.out
+INFO CODE_ID E35C283BC327C28762DB788BF5A4078BE2351448
+FUNC 0 2 0 func0
+FUNC 2 1 0 func2
+FUNC 3 1 0 func3
+FUNC 4 1 0 func4
+FUNC 5 1 0 func5
+FUNC 6 1 0 func6
+FUNC 7 2 0 func7
+FUNC 9 1 0 func9
+STACK CFI INIT 0 2 .cfa: $rsp .ra: .cfa $rbp: $rsp
+STACK CFI 1 $rbp: $rax $rbx: $rcx
+STACK CFI INIT 2 1 $r47: $r42
+STACK CFI INIT 3 1 $rbp:
+STACK CFI INIT 4 1 $rbp
+STACK CFI INIT 5 1 $rbp: $rbx $rsp:
+STACK CFI INIT 6 1 $rbp: $rsp:
+STACK CFI INIT 7 1 .cfa: $rsp
+STACK CFI bogus
+STACK CFI INIT 9 1 .cfa: $rbp .ra: $rax
diff --git a/lldb/lit/SymbolFile/Breakpad/Inputs/stack-cfi-parsing.yaml b/lldb/lit/SymbolFile/Breakpad/Inputs/stack-cfi-parsing.yaml
new file mode 100644
index 00000000000..9f3a6316986
--- /dev/null
+++ b/lldb/lit/SymbolFile/Breakpad/Inputs/stack-cfi-parsing.yaml
@@ -0,0 +1,36 @@
+--- !minidump
+Streams:         
+  - Type:            ThreadList
+    Threads:         
+      - Thread Id:       0x00003E81
+        Context:         DEAD
+        Stack:           
+          Start of Memory Range: 0x00007FFCEB34A000
+          Content:         DEAD
+  - Type:            ModuleList
+    Modules:         
+      - Base of Image:   0x0000000000400000
+        Size of Image:   0x00001000
+        Module Name:     '/tmp/stack-cfi-parsing.out'
+        CodeView Record: 4C457042E35C283BC327C28762DB788BF5A4078BE2351448
+  - Type:            SystemInfo
+    Processor Arch:  AMD64
+    Processor Level: 6
+    Processor Revision: 15876
+    Number of Processors: 40
+    Platform ID:     Linux
+    CSD Version:     'Linux 3.13.0-91-generic'
+    CPU:             
+      Vendor ID:       GenuineIntel
+      Version Info:    0x00000000
+      Feature Info:    0x00000000
+  - Type:            LinuxProcStatus
+    Text:             |
+      Name:	linux-x86_64
+      State:	t (tracing stop)
+      Tgid:	29917
+      Ngid:	0
+      Pid:	29917
+      PPid:	29370
+
+...
diff --git a/lldb/lit/SymbolFile/Breakpad/stack-cfi-parsing.test b/lldb/lit/SymbolFile/Breakpad/stack-cfi-parsing.test
new file mode 100644
index 00000000000..c8d9694172c
--- /dev/null
+++ b/lldb/lit/SymbolFile/Breakpad/stack-cfi-parsing.test
@@ -0,0 +1,48 @@
+# RUN: yaml2obj %S/Inputs/stack-cfi-parsing.yaml > %t
+# RUN: %lldb -c %t -o "target symbols add %S/Inputs/stack-cfi-parsing.syms" \
+# RUN:   -s %s -b | FileCheck %s
+
+image show-unwind -n func0
+# CHECK-LABEL: image show-unwind -n func0
+# CHECK:      Symbol file UnwindPlan:
+# CHECK-NEXT: This UnwindPlan originally sourced from breakpad STACK CFI
+# CHECK-NEXT: This UnwindPlan is sourced from the compiler: yes.
+# CHECK-NEXT: This UnwindPlan is valid at all instruction locations: no.
+# CHECK-NEXT: Address range of this UnwindPlan: [stack-cfi-parsing.out..module_image + 0-0x0000000000000002)
+# CHECK-NEXT: row[0]:    0: CFA=DW_OP_breg7 +0 => rbp=DW_OP_breg7 +0 rip=DW_OP_pick 0x00 
+# CHECK-NEXT: row[1]:    1: CFA=DW_OP_breg7 +0 => rbx=DW_OP_breg2 +0 rbp=DW_OP_breg0 +0 rip=DW_OP_pick 0x00 
+
+# The following plans are all (syntactically) invalid for various reasons.
+# Processing those should not cause a crash.
+
+image show-unwind -n func2
+# CHECK-LABEL: image show-unwind -n func2
+# CHECK-NOT: Symbol file
+
+image show-unwind -n func3
+# CHECK-LABEL: image show-unwind -n func3
+# CHECK-NOT: Symbol file
+
+image show-unwind -n func4
+# CHECK-LABEL: image show-unwind -n func4
+# CHECK-NOT: Symbol file
+
+image show-unwind -n func5
+# CHECK-LABEL: image show-unwind -n func5
+# CHECK-NOT: Symbol file
+
+image show-unwind -n func6
+# CHECK-LABEL: image show-unwind -n func6
+# CHECK-NOT: Symbol file
+
+image show-unwind -n func7
+# CHECK-LABEL: image show-unwind -n func7
+# CHECK-NOT: Symbol file
+
+# Finally, try an unwind plan with just a single row
+image show-unwind -n func9
+# CHECK-LABEL: image show-unwind -n func9
+# CHECK: Symbol file UnwindPlan:
+# CHECK: Address range of this UnwindPlan: [stack-cfi-parsing.out..module_image + 9-0x000000000000000a)
+# CHECK: row[0]:    0: CFA=DW_OP_breg6 +0 => rip=DW_OP_breg0 +0
+
diff --git a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp
index 9057c2a8d3c..d4258274a38 100644
--- a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp
+++ b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp
@@ -15,9 +15,11 @@
 #include "lldb/Host/FileSystem.h"
 #include "lldb/Symbol/CompileUnit.h"
 #include "lldb/Symbol/ObjectFile.h"
+#include "lldb/Symbol/PostfixExpression.h"
 #include "lldb/Symbol/SymbolVendor.h"
 #include "lldb/Symbol/TypeMap.h"
 #include "lldb/Utility/Log.h"
+#include "lldb/Utility/StreamString.h"
 #include "llvm/ADT/StringExtras.h"
 
 using namespace lldb;
@@ -370,6 +372,155 @@ void SymbolFileBreakpad::AddSymbols(Symtab &symtab) {
   symtab.CalculateSymbolSizes();
 }
 
+static llvm::Optional<std::pair<llvm::StringRef, llvm::StringRef>>
+GetRule(llvm::StringRef &unwind_rules) {
+  // Unwind rules are of the form
+  //   register1: expression1 register2: expression2 ...
+  // We assume none of the tokens in expression<n> end with a colon.
+
+  llvm::StringRef lhs, rest;
+  std::tie(lhs, rest) = getToken(unwind_rules);
+  if (!lhs.consume_back(":"))
+    return llvm::None;
+
+  // Seek forward to the next register: expression pair
+  llvm::StringRef::size_type pos = rest.find(": ");
+  if (pos == llvm::StringRef::npos) {
+    // No pair found, this means the rest of the string is a single expression.
+    unwind_rules = llvm::StringRef();
+    return std::make_pair(lhs, rest);
+  }
+
+  // Go back one token to find the end of the current rule.
+  pos = rest.rfind(' ', pos);
+  if (pos == llvm::StringRef::npos)
+    return llvm::None;
+
+  llvm::StringRef rhs = rest.take_front(pos);
+  unwind_rules = rest.drop_front(pos);
+  return std::make_pair(lhs, rhs);
+}
+
+static const RegisterInfo *
+ResolveRegister(const SymbolFile::RegisterInfoResolver &resolver,
+                llvm::StringRef name) {
+  if (name.consume_front("$"))
+    return resolver.ResolveName(name);
+
+  return nullptr;
+}
+
+static const RegisterInfo *
+ResolveRegisterOrRA(const SymbolFile::RegisterInfoResolver &resolver,
+                    llvm::StringRef name) {
+  if (name == ".ra")
+    return resolver.ResolveNumber(eRegisterKindGeneric, LLDB_REGNUM_GENERIC_PC);
+  return ResolveRegister(resolver, name);
+}
+
+bool SymbolFileBreakpad::ParseUnwindRow(llvm::StringRef unwind_rules,
+                                        const RegisterInfoResolver &resolver,
+                                        UnwindPlan::Row &row) {
+  Log *log = GetLogIfAllCategoriesSet(LIBLLDB_LOG_SYMBOLS);
+
+  llvm::BumpPtrAllocator node_alloc;
+  while (auto rule = GetRule(unwind_rules)) {
+    node_alloc.Reset();
+    llvm::StringRef lhs = rule->first;
+    postfix::Node *rhs = postfix::Parse(rule->second, node_alloc);
+    if (!rhs) {
+      LLDB_LOG(log, "Could not parse `{0}` as unwind rhs.", rule->second);
+      return false;
+    }
+
+    bool success = postfix::ResolveSymbols(
+        rhs, [&](postfix::SymbolNode &symbol) -> postfix::Node * {
+          llvm::StringRef name = symbol.GetName();
+          if (name == ".cfa" && lhs != ".cfa")
+            return postfix::MakeNode<postfix::InitialValueNode>(node_alloc);
+
+          if (const RegisterInfo *info = ResolveRegister(resolver, name)) {
+            return postfix::MakeNode<postfix::RegisterNode>(
+                node_alloc, info->kinds[eRegisterKindLLDB]);
+          }
+          return nullptr;
+        });
+
+    if (!success) {
+      LLDB_LOG(log, "Resolving symbols in `{0}` failed.", rule->second);
+      return false;
+    }
+
+    ArchSpec arch = m_obj_file->GetArchitecture();
+    StreamString dwarf(Stream::eBinary, arch.GetAddressByteSize(),
+                       arch.GetByteOrder());
+    ToDWARF(*rhs, dwarf);
+    uint8_t *saved = m_allocator.Allocate<uint8_t>(dwarf.GetSize());
+    std::memcpy(saved, dwarf.GetData(), dwarf.GetSize());
+
+    if (lhs == ".cfa") {
+      row.GetCFAValue().SetIsDWARFExpression(saved, dwarf.GetSize());
+    } else if (const RegisterInfo *info = ResolveRegisterOrRA(resolver, lhs)) {
+      UnwindPlan::Row::RegisterLocation loc;
+      loc.SetIsDWARFExpression(saved, dwarf.GetSize());
+      row.SetRegisterInfo(info->kinds[eRegisterKindLLDB], loc);
+    } else
+      LLDB_LOG(log, "Invalid register `{0}` in unwind rule.", lhs);
+  }
+  if (unwind_rules.empty())
+    return true;
+
+  LLDB_LOG(log, "Could not parse `{0}` as an unwind rule.", unwind_rules);
+  return false;
+}
+
+UnwindPlanSP
+SymbolFileBreakpad::GetUnwindPlan(const Address &address,
+                                  const RegisterInfoResolver &resolver) {
+  ParseUnwindData();
+  const UnwindMap::Entry *entry =
+      m_unwind_data->FindEntryThatContains(address.GetFileAddress());
+  if (!entry)
+    return nullptr;
+
+  addr_t base = GetBaseFileAddress();
+  if (base == LLDB_INVALID_ADDRESS)
+    return nullptr;
+
+  LineIterator It(*m_obj_file, Record::StackCFI, entry->data), End(*m_obj_file);
+  llvm::Optional<StackCFIRecord> init_record = StackCFIRecord::parse(*It);
+  assert(init_record.hasValue());
+  assert(init_record->Size.hasValue());
+
+  auto plan_sp = std::make_shared<UnwindPlan>(lldb::eRegisterKindLLDB);
+  plan_sp->SetSourceName("breakpad STACK CFI");
+  plan_sp->SetUnwindPlanValidAtAllInstructions(eLazyBoolNo);
+  plan_sp->SetSourcedFromCompiler(eLazyBoolYes);
+  plan_sp->SetPlanValidAddressRange(
+      AddressRange(base + init_record->Address, *init_record->Size,
+                   m_obj_file->GetModule()->GetSectionList()));
+
+  auto row_sp = std::make_shared<UnwindPlan::Row>();
+  row_sp->SetOffset(0);
+  if (!ParseUnwindRow(init_record->UnwindRules, resolver, *row_sp))
+    return nullptr;
+  plan_sp->AppendRow(row_sp);
+  for (++It; It != End; ++It) {
+    llvm::Optional<StackCFIRecord> record = StackCFIRecord::parse(*It);
+    if (!record.hasValue())
+      return nullptr;
+    if (record->Size.hasValue())
+      break;
+
+    row_sp = std::make_shared<UnwindPlan::Row>(*row_sp);
+    row_sp->SetOffset(record->Address - init_record->Address);
+    if (!ParseUnwindRow(record->UnwindRules, resolver, *row_sp))
+      return nullptr;
+    plan_sp->AppendRow(row_sp);
+  }
+  return plan_sp;
+}
+
 SymbolVendor &SymbolFileBreakpad::GetSymbolVendor() {
   return *m_obj_file->GetModule()->GetSymbolVendor();
 }
@@ -476,3 +627,27 @@ void SymbolFileBreakpad::ParseLineTableAndSupportFiles(CompileUnit &cu,
     finish_sequence();
   data.support_files = map.translate(cu, *m_files);
 }
+
+void SymbolFileBreakpad::ParseUnwindData() {
+  if (m_unwind_data)
+    return;
+
+  m_unwind_data.emplace();
+  Log *log = GetLogIfAllCategoriesSet(LIBLLDB_LOG_SYMBOLS);
+  addr_t base = GetBaseFileAddress();
+  if (base == LLDB_INVALID_ADDRESS) {
+    LLDB_LOG(log, "SymbolFile parsing failed: Unable to fetch the base address "
+                  "of object file.");
+  }
+
+  for (LineIterator It(*m_obj_file, Record::StackCFI), End(*m_obj_file);
+       It != End; ++It) {
+    if (auto record = StackCFIRecord::parse(*It)) {
+      if (record->Size)
+        m_unwind_data->Append(UnwindMap::Entry(
+            base + record->Address, *record->Size, It.GetBookmark()));
+    } else
+      LLDB_LOG(log, "Failed to parse: {0}. Skipping record.", *It);
+  }
+  m_unwind_data->Sort();
+}
diff --git a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h
index 2760a5a573e..8a0b7645fd0 100644
--- a/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h
+++ b/lldb/source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h
@@ -13,6 +13,7 @@
 #include "lldb/Core/FileSpecList.h"
 #include "lldb/Symbol/LineTable.h"
 #include "lldb/Symbol/SymbolFile.h"
+#include "lldb/Symbol/UnwindPlan.h"
 
 namespace lldb_private {
 
@@ -133,6 +134,10 @@ public:
 
   void AddSymbols(Symtab &symtab) override;
 
+  lldb::UnwindPlanSP
+  GetUnwindPlan(const Address &address,
+                const RegisterInfoResolver &resolver) override;
+
   ConstString GetPluginName() override { return GetPluginNameStatic(); }
   uint32_t GetPluginVersion() override { return 1; }
 
@@ -144,6 +149,11 @@ private:
   struct Bookmark {
     uint32_t section;
     size_t offset;
+
+    friend bool operator<(const Bookmark &lhs, const Bookmark &rhs) {
+      return std::tie(lhs.section, lhs.offset) <
+             std::tie(rhs.section, rhs.offset);
+    }
   };
 
   // At iterator class for simplifying algorithms reading data from the breakpad
@@ -177,8 +187,7 @@ private:
       return *this;
     }
     friend bool operator<(const CompUnitData &lhs, const CompUnitData &rhs) {
-      return std::tie(lhs.bookmark.section, lhs.bookmark.offset) <
-             std::tie(rhs.bookmark.section, rhs.bookmark.offset);
+      return lhs.bookmark < rhs.bookmark;
     }
 
     Bookmark bookmark;
@@ -192,11 +201,19 @@ private:
   void ParseFileRecords();
   void ParseCUData();
   void ParseLineTableAndSupportFiles(CompileUnit &cu, CompUnitData &data);
+  void ParseUnwindData();
+  bool ParseUnwindRow(llvm::StringRef unwind_rules,
+                      const RegisterInfoResolver &resolver,
+                      UnwindPlan::Row &row);
 
   using CompUnitMap = RangeDataVector<lldb::addr_t, lldb::addr_t, CompUnitData>;
 
   llvm::Optional<std::vector<FileSpec>> m_files;
   llvm::Optional<CompUnitMap> m_cu_data;
+
+  using UnwindMap = RangeDataVector<lldb::addr_t, lldb::addr_t, Bookmark>;
+  llvm::Optional<UnwindMap> m_unwind_data;
+  llvm::BumpPtrAllocator m_allocator;
 };
 
 } // namespace breakpad