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 ↗

(On Diff #193717)

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

123 ↗

(On Diff #193717)

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?

132 ↗

(On Diff #193717)

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 ↗

(On Diff #193717)

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

123 ↗

(On Diff #193717)

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.

132 ↗

(On Diff #193717)

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 ↗

(On Diff #193849)

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 ↗

(On Diff #193849)

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

[clayborg]

source/Plugins/ObjectFile/Breakpad/BreakpadRecords.cpp

393 ↗

(On Diff #193849)

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 ↗

(On Diff #193849)

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 ↗

(On Diff #193849)

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.

lldb/trunk/lit/Modules/Breakpad/sections.test

 CHECK-NEXT:   VM size: 0
 CHECK-NEXT:   File size: 21
 CHECK-NEXT:   Data:  (
 CHECK-NEXT:       0000: 5055424C 49432031 30313020 30205F73 74617274 0A                          |PUBLIC 1010 0 _start.|
 CHECK-NEXT:   )
 
 CHECK:        Index: 5
 CHECK-NEXT:   ID: 0x6
-CHECK-NEXT:   Name: STACK CFI INIT
+CHECK-NEXT:   Name: STACK CFI
 CHECK-NEXT:   Type: regular
 CHECK-NEXT:   Permissions: ---
 CHECK-NEXT:   Thread specific: no
 CHECK-NEXT:   VM address: 0
 CHECK-NEXT:   VM size: 0
 CHECK-NEXT:   File size: 136
 CHECK-NEXT:   Data:  (
 CHECK-NEXT:       0000: 53544143 4B204346 4920494E 49542031 30313020 3130202E 6366613A 20247273  |STACK CFI INIT 1010 10 .cfa: $rs|
 CHECK-NEXT:       0020: 70203820 2B202E72 613A202E 63666120 2D38202B 205E0A53 5441434B 20434649  |p 8 + .ra: .cfa -8 + ^.STACK CFI|
 CHECK-NEXT:       0040: 20313031 31202472 62703A20 2E636661 202D3136 202B205E 202E6366 613A2024  | 1011 $rbp: .cfa -16 + ^ .cfa: $|
 CHECK-NEXT:       0060: 72737020 3136202B 0A535441 434B2043 46492031 30313420 2E636661 3A202472  |rsp 16 +.STACK CFI 1014 .cfa: $r|
 CHECK-NEXT:       0080: 62702031 36202B0A                                                        |bp 16 +.|
 CHECK-NEXT:   )

lldb/trunk/source/Plugins/ObjectFile/Breakpad/BreakpadRecords.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::StringRef UnwindRules)
+      : Record(StackCFI), Address(Address), Size(Size),
+        UnwindRules(UnwindRules) {}
+
+  lldb::addr_t Address;
+  llvm::Optional<lldb::addr_t> Size;
+  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

lldb/trunk/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;
+  }
+
+  return StackCFIRecord(Address, Size, Line.trim());
+}
+
+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);
+  return OS << " " << R.UnwindRules;
+}
+
 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!");
 }

lldb/trunk/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());
 }

lldb/trunk/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 +"),
+            StackCFIRecord::parse("STACK CFI 47 .cfa: $esp 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(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"));
+}