Breakpad: Parse Stack CFI records

[labath]

Summary

This patch adds support for parsing STACK CFI records from breakpad
files. For the expressions specifying the values of registers, only a
basic parse is performed -- the record is split into a bunch of key-value
pairs, where both keys and values are strings. The idea is that these
will be handed off to the postfix expression -> dwarf compiler, once
it is extracted from the internals of the NativePDB plugin

[amccarth]

This looks good. I have a few questions inline, but none of those are major concerns.

source/Plugins/ObjectFile/Breakpad/BreakpadRecords.h

173

I'm not a fan of deep class hierarchies, but given that StackCFIRecord is a subset of StackCFIInitRecord and given that the naming suggests StackCFIInitRecord is a concrete type of StackCFIRecord, should StackCFIInitRecord derive from StackCFIRecord? (Or perhaps contain one?)

If not, perhaps a comment to explain why not.

unittests/ObjectFile/Breakpad/BreakpadRecordsTest.cpp

122

All of the negative parsing tests seem to be incomplete (e.g., truncated or a missing INIT). Should there be others, like having the wrong token type? Or an invalid token? Or one that has extra tokens at the end of an otherwise valid record?

I see you're following the pattern for the other types here, but is that enough?

131

This test relies on the parsing test for the StackCFIInitRecord having covered most of the cases. That works because the parsing implementation is shared, so I'm OK with it. Will others be concerned that this test isn't as independent as it could be?

[labath]

source/Plugins/ObjectFile/Breakpad/BreakpadRecords.h

173

Good question. I was doing the same thing as I did with FUNC and PUBLIC records, which are also very similar, but I wouln't be comfortable saying one is a special case of the other. However, the case here is not as clear, as one could consider the "init" record to be a special kind of a "stack cfi" record. OTOH, I also don't like deep hierarchies and particularly having a concrete class (init record) inherit from another concrete class (stack cfi record).

Since this code is likely to have only a single consumer (the thing which converts these into UnwindPlans), adding an AbstractCFIRecord class would seem like an overkill. Instead, how about we just collapse things even more and use just a single class to represent both records (with an Optional<addr_t> for the size)?

I don't think this should make it the job of the consumer much harder, but it will allow us to:

• avoid needing special code to group these two records together
• give us an excuse to call this group (section) "STACK CFI". (I have previously called this group "STACK CFI INIT" for consistency with how the FUNC+LINE groups is handled, but that didn't feel quite right here).
• speed up parsing as we don't have to parse the "STACK CFI" part twice just to find out we're not parsing the correct record type.

unittests/ObjectFile/Breakpad/BreakpadRecordsTest.cpp

122

Following the pattern isn't much of an excuse for me, as I was the one who established that pattern. :)

The reason the pattern is like it is was that I was trying to cover all of the paths through the parsing code. I believe I have succeeded at that, but I haven't used a profiler or anything to verify that. Knowing the implementation, it's obvious that a test with an invalid record type is not going to be interesting, as we will bail out straight after the first token. However, I agree that from a black-box testing perspective, these are interesting cases to check, so I've added a couple more that I could think of.

This is going to be the most extensively tested piece of code in lldb :P.

131

Another advantage of merging the two record types is that it makes this comment void. :)

[labath]

merge StackCFI and StackCFIInit records
add some tests

[clayborg]

source/Plugins/ObjectFile/Breakpad/BreakpadRecords.cpp

393

Do we really need to pull the content apart into separate strings for each register? Seems like a lot of work and 99% of these we will never accessed. Maybe just store the entire string for all registers and be done?

394

Does the format specify no space between the register name and the colon?

[clayborg]

source/Plugins/ObjectFile/Breakpad/BreakpadRecords.cpp

393

You can add an iterator method to the StackCFIRecord record maybe for when you do want to parse each register?

[amccarth]

My concerns were address, so LGTM. I'll leave the rest to you and clayborg.

[labath]

source/Plugins/ObjectFile/Breakpad/BreakpadRecords.cpp

393

That's a good point. I'll remove the register parsing code from this patch and just store the entire expression as one string(ref). I'll see what's the best api for splitting these up when I get to connecting this with the postfix expression parser.

394

That is how I interpret the format "spec" https://chromium.googlesource.com/breakpad/breakpad/+/master/docs/symbol_files.md

Each registeri is the name of a register or pseudoregister. Each expression is a Breakpad postfix expression, which may contain spaces, but never ends with a colon.

That's not a very good definition because there are many ways one can split up these strings such they "don't end with a colon", but I chose this interpretation, as that's what made most sense to me (and it works for the example files I have lying around). We can always change that if we find a producer doing things slightly differently.

[labath]

Remove the fancy parsing of register expressions.

source/Plugins/ObjectFile/Breakpad/BreakpadRecords.h

 //===-- BreakpadRecords.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_OBJECTFILE_BREAKPAD_BREAKPADRECORDS_H
 #define LLDB_PLUGINS_OBJECTFILE_BREAKPAD_BREAKPADRECORDS_H
 
 #include "lldb/Utility/UUID.h"
 #include "lldb/lldb-types.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Support/FormatProviders.h"
 
 namespace lldb_private {
 namespace breakpad {
 
 class Record {
 public:
-  enum Kind { Module, Info, File, Func, Line, Public, StackCFIInit, StackCFI };
+  enum Kind { Module, Info, File, Func, Line, Public, StackCFI };
 
   /// Attempt to guess the kind of the record present in the argument without
   /// doing a full parse. The returned kind will always be correct for valid
   /// records, but the full parse can still fail in case of corrupted input.
   static llvm::Optional<Kind> classify(llvm::StringRef Line);
 
 protected:
   Record(Kind K) : TheKind(K) {}
public:
   lldb::addr_t Address;
   lldb::addr_t ParamSize;
   llvm::StringRef Name;
 };
 
 bool operator==(const PublicRecord &L, const PublicRecord &R);
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const PublicRecord &R);
 
+class StackCFIRecord : public Record {
+public:
+  static llvm::Optional<StackCFIRecord> parse(llvm::StringRef Line);
+  StackCFIRecord(lldb::addr_t Address, llvm::Optional<lldb::addr_t> Size,
+                 llvm::DenseMap<llvm::StringRef, llvm::StringRef> UnwindRules)
+      : Record(StackCFI), Address(Address), Size(Size),
+        UnwindRules(std::move(UnwindRules)) {}
+
+  lldb::addr_t Address;
+  llvm::Optional<lldb::addr_t> Size;
+  llvm::DenseMap<llvm::StringRef, llvm::StringRef> UnwindRules;
+};
+
+bool operator==(const StackCFIRecord &L, const StackCFIRecord &R);
+llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const StackCFIRecord &R);
+
 } // namespace breakpad
 } // namespace lldb_private
 
 #endif // LLDB_PLUGINS_OBJECTFILE_BREAKPAD_BREAKPADRECORDS_H

source/Plugins/ObjectFile/Breakpad/BreakpadRecords.cpp

llvm::Optional<Record::Kind> Record::classify(llvm::StringRef Line) {
   case Token::Func:
     return Record::Func;
   case Token::Public:
     return Record::Public;
   case Token::Stack:
     Tok = consume<Token>(Line);
     switch (Tok) {
     case Token::CFI:
-      Tok = consume<Token>(Line);
-      return Tok == Token::Init ? Record::StackCFIInit : Record::StackCFI;
+      return Record::StackCFI;
     default:
       return llvm::None;
     }
 
   case Token::Unknown:
     // Optimistically assume that any unrecognised token means this is a line
     // record, those don't have a special keyword and start directly with a
     // hex number. CODE_ID should never be at the start of a line, but if it

 }
 llvm::raw_ostream &breakpad::operator<<(llvm::raw_ostream &OS,
                                         const PublicRecord &R) {
   return OS << llvm::formatv("PUBLIC {0}{1:x-} {2:x-} {3}",
                              R.Multiple ? "m " : "", R.Address, R.ParamSize,
                              R.Name);
 }
 
+llvm::Optional<StackCFIRecord> StackCFIRecord::parse(llvm::StringRef Line) {
+  // STACK CFI INIT address size reg1: expr1 reg2: expr2 ...
+  // or
+  // STACK CFI address reg1: expr1 reg2: expr2 ...
+  // No token in exprN ends with a colon.
+
+  if (consume<Token>(Line) != Token::Stack)
+    return llvm::None;
+  if (consume<Token>(Line) != Token::CFI)
+    return llvm::None;
+
+  llvm::StringRef Str;
+  std::tie(Str, Line) = getToken(Line);
+
+  bool IsInitRecord = stringTo<Token>(Str) == Token::Init;
+  if (IsInitRecord)
+    std::tie(Str, Line) = getToken(Line);
+
+  lldb::addr_t Address;
+  if (!to_integer(Str, Address, 16))
+    return llvm::None;
+
+  llvm::Optional<lldb::addr_t> Size;
+  if (IsInitRecord) {
+    Size.emplace();
+    std::tie(Str, Line) = getToken(Line);
+    if (!to_integer(Str, *Size, 16))
+      return llvm::None;
+  }
+
+  llvm::DenseMap<llvm::StringRef, llvm::StringRef> UnwindRules;
+  llvm::StringRef LHS, RHS;
+  while (std::tie(Str, Line) = getToken(Line), !Str.empty()) {
+    if (Str.back() == ':') { // regN
+      // Flush the previous expression, if there is one.
+      if (!LHS.empty()) {
+        if (RHS.empty())
+          return llvm::None; // regN without an exprN
+        UnwindRules[LHS] = RHS;
+      }
+
+      LHS = Str.drop_back();
+      RHS = llvm::StringRef();
+      continue;
+    }
+
+    if (LHS.empty())
+      return llvm::None; // exprN without a preceding regN.
+
+    // Append token to RHS.
+    if (RHS.empty())
+      RHS = Str;
+    else
+      RHS = llvm::StringRef(RHS.begin(), Str.end() - RHS.begin());
+  }
+
+  // Append last rule, if it is valid.
+  if (RHS.empty())
+    return llvm::None;
+
+  UnwindRules[LHS] = RHS;
+  return StackCFIRecord(Address, Size, std::move(UnwindRules));
+}
+
+bool breakpad::operator==(const StackCFIRecord &L, const StackCFIRecord &R) {
+  return L.Address == R.Address && L.Size == R.Size &&
+         L.UnwindRules == R.UnwindRules;
+}
+
+llvm::raw_ostream &breakpad::operator<<(llvm::raw_ostream &OS,
+                                        const StackCFIRecord &R) {
+  OS << "STACK CFI ";
+  if (R.Size)
+    OS << "INIT ";
+  OS << llvm::formatv("{0:x-} ", R.Address);
+  if (R.Size)
+    OS << llvm::formatv("{0:x-} ", *R.Size);
+  llvm::StringRef Sep;
+  for (const auto &KV : R.UnwindRules) {
+    OS << Sep << KV.first << ": " << KV.second;
+    Sep = " ";
+  }
+  return OS;
+}
+
 llvm::StringRef breakpad::toString(Record::Kind K) {
   switch (K) {
   case Record::Module:
     return "MODULE";
   case Record::Info:
     return "INFO";
   case Record::File:
     return "FILE";
   case Record::Func:
     return "FUNC";
   case Record::Line:
     return "LINE";
   case Record::Public:
     return "PUBLIC";
-  case Record::StackCFIInit:
-    return "STACK CFI INIT";
   case Record::StackCFI:
     return "STACK CFI";
   }
   llvm_unreachable("Unknown record kind!");
 }

source/Plugins/ObjectFile/Breakpad/ObjectFileBreakpad.cpp

while (!text.empty()) {
     llvm::StringRef line;
     std::tie(line, text) = text.split('\n');
 
     llvm::Optional<Record::Kind> next_section = Record::classify(line);
     if (next_section == Record::Line) {
       // Line records logically belong to the preceding Func record, so we put
       // them in the same section.
       next_section = Record::Func;
-    } else if (next_section == Record::StackCFI) {
-      // Same goes for StackCFI and StackCFIInit
-      next_section = Record::StackCFIInit;
     }
     if (next_section == current_section)
       continue;
 
     // Changing sections, finish off the previous one, if there was any.
     maybe_add_section(line.bytes_begin());
     // And start a new one.
     current_section = next_section;
     section_start = line.bytes_begin() - m_data.GetDataStart();
   }
   // Finally, add the last section.
   maybe_add_section(m_data.GetDataEnd());
 }

unittests/ObjectFile/Breakpad/BreakpadRecordsTest.cpp

 using namespace lldb_private::breakpad;
 
 TEST(Record, classify) {
   EXPECT_EQ(Record::Module, Record::classify("MODULE"));
   EXPECT_EQ(Record::Info, Record::classify("INFO"));
   EXPECT_EQ(Record::File, Record::classify("FILE"));
   EXPECT_EQ(Record::Func, Record::classify("FUNC"));
   EXPECT_EQ(Record::Public, Record::classify("PUBLIC"));
-  EXPECT_EQ(Record::StackCFIInit, Record::classify("STACK CFI INIT"));
   EXPECT_EQ(Record::StackCFI, Record::classify("STACK CFI"));
 
   // Any obviously incorrect lines will be classified as such.
   EXPECT_EQ(llvm::None, Record::classify("STACK"));
   EXPECT_EQ(llvm::None, Record::classify("STACK CODE_ID"));
   EXPECT_EQ(llvm::None, Record::classify("CODE_ID"));
 
   // Any line which does not start with a known keyword will be classified as a
EXPECT_EQ(PublicRecord(false, 0x47, 0x8, "foo"),
             PublicRecord::parse("PUBLIC 47 8 foo"));
 
   EXPECT_EQ(llvm::None, PublicRecord::parse("FUNC 47 8 foo"));
   EXPECT_EQ(llvm::None, PublicRecord::parse("PUBLIC 47 8"));
   EXPECT_EQ(llvm::None, PublicRecord::parse("PUBLIC 47"));
   EXPECT_EQ(llvm::None, PublicRecord::parse("PUBLIC m"));
   EXPECT_EQ(llvm::None, PublicRecord::parse("PUBLIC"));
 }
+
+TEST(StackCFIRecord, parse) {
+  EXPECT_EQ(
+      StackCFIRecord(0x47, 0x8, {{".cfa", "$esp 4 +"}, {"$eip", ".cfa 4 - ^"}}),
+      StackCFIRecord::parse(
+          "STACK CFI INIT 47 8 .cfa: $esp 4 + $eip: .cfa 4 - ^"));
+  EXPECT_EQ(StackCFIRecord(0x47, 0x8, {{".cfa", "$esp 4 +"}}),
+            StackCFIRecord::parse("STACK CFI INIT 47 8 .cfa: $esp 4 +"));
+
+  EXPECT_EQ(
+      StackCFIRecord(0x47, llvm::None,
+                     {{".cfa", "$esp 4 +"}, {"$eip", ".cfa 4 - ^"}}),
+      StackCFIRecord::parse("STACK CFI 47 .cfa: $esp 4 + $eip: .cfa 4 - ^"));
+
+  // The validity of the register value expressions is not checked
+  EXPECT_EQ(StackCFIRecord(0x47, 0x8, {{".cfa", "^ ^ ^"}}),
+            StackCFIRecord::parse("STACK CFI INIT 47 8 .cfa: ^ ^ ^"));
+  EXPECT_EQ(StackCFIRecord(0x47, 0x8, {{".cfa", "STACK CFI"}}),
+            StackCFIRecord::parse("STACK CFI INIT 47 8 .cfa: STACK CFI"));
+
+  EXPECT_EQ(llvm::None,
+            StackCFIRecord::parse("STACK CFI INIT 47 .cfa: $esp 4 +"));
+  EXPECT_EQ(llvm::None, StackCFIRecord::parse("STACK CFI 47 8 .cfa: $esp 4 +"));
+  EXPECT_EQ(llvm::None,
+            StackCFIRecord::parse("STACK CFI INIT 47 8 .cfa: $esp 4 + $eip:"));
+  EXPECT_EQ(llvm::None,
+            StackCFIRecord::parse("STACK CFI INIT 47 8 .cfa: $eip: .cfa"));
+  EXPECT_EQ(llvm::None,
+            StackCFIRecord::parse("STACK CFI INIT 47 8 $esp .cfa: $esp"));
+  EXPECT_EQ(llvm::None, StackCFIRecord::parse("STACK CFI INIT 47 8 .cfa:"));
+  EXPECT_EQ(llvm::None, StackCFIRecord::parse("STACK CFI INIT 47 8"));
+  EXPECT_EQ(llvm::None, StackCFIRecord::parse("STACK CFI INIT 47"));
+  EXPECT_EQ(llvm::None, StackCFIRecord::parse("STACK CFI INIT"));
+  EXPECT_EQ(llvm::None, StackCFIRecord::parse("STACK CFI"));
+  EXPECT_EQ(llvm::None, StackCFIRecord::parse("STACK"));
+  EXPECT_EQ(llvm::None, StackCFIRecord::parse("FILE 47 foo"));
+  EXPECT_EQ(llvm::None, StackCFIRecord::parse("42 47"));
+}