Breakpad: Generate unwind plans from STACK CFI records

[labath]

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.

[clayborg]

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

378

This format seems a bit challenging to parse

418

LLDB_REGNUM_GENERIC_RA? Do we want the PC here or do we want the link register?

491–492

will this code be ok if the assertions are compiled out?

[labath]

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

418

It looks a bit weird, but I believe it should be the PC (and I have checked that things unwind correctly this way), because we are specifying value for the PC in the parent frame (which is the same as the return address of the current frame). Or, to put it another way, breakpad uses ".ra" even on platforms which do not have a LLDB_REGNUM_GENERIC_RA register (like x86).

491–492

Yes, because we make sure that we only store the address of a syntactically correct STACK CFI INIT record in the m_unwind_data map (down on line 645)

[clayborg]

Thanks for the clarification! LGTM

[amccarth]

LGTM once you double-check the return value in the error case at the end of SymbolFileBreakpad::ParseUnwindRow.

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

472

Should the function return false when there are leftover unparsable rules? The other error cases seem to do that.

[jasonmolenda]

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

418

This is fine, fwiw RegisterContextLLDB won't try to use LLDB_REGNUM_GENERIC_RA on architectures that don't use a return address register (e.g. lr on arm), so using LLDB_REGNUM_GENERIC_PC is correct if we ever need to do this unwind on an x86 breakpad file.

[labath]

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

472

Good point. In fact this should have been caught by the test, if it was written properly, but I forgot the colon after the CHECK-NOT directive, which meant it was ignored by FileCheck. :/
Fixing that found another case where I was mistakenly returning a "valid" unwind plan for invalid input, which I have fixed too.

[labath]

• use a yaml form of the minidump file (as it is possible to do that as of today)
• fix the CHECK-NOT directives in the test and the two issues they caught
• found a way to trigger one of the asserts with an invalid input, so I demote it into a "return nullptr"

lit/SymbolFile/Breakpad/Inputs/stack-cfi-parsing.syms

+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

lit/SymbolFile/Breakpad/Inputs/stack-cfi-parsing.yaml

+--- !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
+
+...

lit/SymbolFile/Breakpad/stack-cfi-parsing.test

+# 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
+

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.h

 //===-- SymbolFileBreakpad.h ------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLDB_PLUGINS_SYMBOLFILE_BREAKPAD_SYMBOLFILEBREAKPAD_H
 #define LLDB_PLUGINS_SYMBOLFILE_BREAKPAD_SYMBOLFILEBREAKPAD_H
 
 #include "Plugins/ObjectFile/Breakpad/BreakpadRecords.h"
 #include "lldb/Core/FileSpecList.h"
 #include "lldb/Symbol/LineTable.h"
 #include "lldb/Symbol/SymbolFile.h"
+#include "lldb/Symbol/UnwindPlan.h"
 
 namespace lldb_private {
 
 namespace breakpad {
 
 class SymbolFileBreakpad : public SymbolFile {
 public:
   // Static Functions
public:
   CompilerDeclContext
   FindNamespace(ConstString name,
                 const CompilerDeclContext *parent_decl_ctx) override {
     return CompilerDeclContext();
   }
 
   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; }
 
 private:
   // A class representing a position in the breakpad file. Useful for
   // remembering the position so we can go back to it later and parse more data.
   // Can be converted to/from a LineIterator, but it has a much smaller memory
   // footprint.
   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
   // file. It iterates over all records (lines) in the sections of a given type.
   // It also supports saving a specific position (via the GetBookmark() method)
   // and then resuming from it afterwards.
   class LineIterator;
 
public:
     CompUnitData(const CompUnitData &rhs) : bookmark(rhs.bookmark) {}
     CompUnitData &operator=(const CompUnitData &rhs) {
       bookmark = rhs.bookmark;
       support_files.reset();
       line_table_up.reset();
       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;
     llvm::Optional<FileSpecList> support_files;
     std::unique_ptr<LineTable> line_table_up;
 
   };
 
   SymbolVendor &GetSymbolVendor();
   lldb::addr_t GetBaseFileAddress();
   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
 } // namespace lldb_private
 
 #endif

source/Plugins/SymbolFile/Breakpad/SymbolFileBreakpad.cpp

 #include "Plugins/ObjectFile/Breakpad/BreakpadRecords.h"
 #include "Plugins/ObjectFile/Breakpad/ObjectFileBreakpad.h"
 #include "lldb/Core/Module.h"
 #include "lldb/Core/PluginManager.h"
 #include "lldb/Core/Section.h"
 #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;
 using namespace lldb_private;
 using namespace lldb_private::breakpad;
 
 class SymbolFileBreakpad::LineIterator {
 public:
else
       LLDB_LOG(log, "Failed to parse: {0}. Skipping record.", line);
   }
 
   for (auto &KV : symbols)
     symtab.AddSymbol(std::move(KV.second));
   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();
 }
 
 addr_t SymbolFileBreakpad::GetBaseFileAddress() {
   return m_obj_file->GetModule()
       ->GetObjectFile()
       ->GetBaseAddress()
data.line_table_up->AppendLineEntryToSequence(
         /*is_start_of_basic_block*/ false, /*is_prologue_end*/ false,
         /*is_epilogue_begin*/ false, /*is_terminal_entry*/ false);
     next_addr = record->Address + record->Size;
   }
   if (next_addr)
     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();
+}