Breakpad: Add minidump processor support for DWARF Call Frame Information.

Add a CFIFrameInfo class (named for symmetry with WindowsFrameInfo) to
represent the set of STACK CFI rules in effect at a given instruction,
and apply them to a set of register values. Provide a SimpleCFIWalker
class template, to allow the essential CFI code to be shared amongst
the different architectures.

Teach BasicSourceLineResolver to partially parse 'STACK CFI' records,
and produce the set of rules in effect at a given instruction on
demand, by combining the initial rule set and the appropriate rule
deltas in a CFIFrameInfo object.

Adapt StackwalkerX86 and StackFrameX86 to retrieve, store, and apply
CFI stack walking information.

Add validity flags for all the general-purpose registers to
StackFrameX86::ContextValidity.

a=jimblandy, r=mmentovai


git-svn-id: http://google-breakpad.googlecode.com/svn/trunk@549 4c0a9323-5329-0410-9bdc-e9ce6186880e

11 files changed, 1673 insertions, 27 deletions

diff --git a/src/processor/basic_source_line_resolver.cc b/src/processor/basic_source_line_resolver.cc
index a49868ab..0385f89f 100644
--- a/src/processor/basic_source_line_resolver.cc
+++ b/src/processor/basic_source_line_resolver.cc
@@ -47,6 +47,7 @@
 #include "processor/linked_ptr.h"
 #include "processor/scoped_ptr.h"
 #include "processor/windows_frame_info.h"
+#include "processor/cfi_frame_info.h"
 
 using std::map;
 using std::vector;
@@ -124,6 +125,12 @@ class BasicSourceLineResolver::Module {
   // object.
   WindowsFrameInfo *FindWindowsFrameInfo(const StackFrame *frame) const;
 
+  // If CFI stack walking information is available covering ADDRESS,
+  // return a CFIFrameInfo structure describing it. If the information
+  // is not available, return NULL. The caller takes ownership of any
+  // returned CFIFrameInfo object.
+  CFIFrameInfo *FindCFIFrameInfo(const StackFrame *frame) const;
+
  private:
   friend class BasicSourceLineResolver;
   typedef map<int, string> FileMap;
@@ -167,12 +174,20 @@ class BasicSourceLineResolver::Module {
   // Returns false if an error occurs.
   bool ParsePublicSymbol(char *public_line);
 
-  // Parses a stack frame info declaration, storing it in windows_frame_info_.
+  // Parses a STACK WIN or STACK CFI frame info declaration, storing
+  // it in the appropriate table.
   bool ParseStackInfo(char *stack_info_line);
 
   // Parses a STACK WIN record, storing it in windows_frame_info_.
   bool ParseWindowsFrameInfo(char *stack_info_line);
 
+  // Parses a STACK CFI record, storing it in cfi_frame_info_.
+  bool ParseCFIFrameInfo(char *stack_info_line);
+
+  // Parse RULE_SET, a series of rules of the sort appearing in STACK
+  // CFI records, and store the given rules in FRAME_INFO.
+  bool ParseCFIRuleSet(const string &rule_set, CFIFrameInfo *frame_info) const;
+
   string name_;
   FileMap files_;
   RangeMap< MemAddr, linked_ptr<Function> > functions_;
@@ -184,6 +199,24 @@ class BasicSourceLineResolver::Module {
   // information is only available as certain types.
   ContainedRangeMap< MemAddr, linked_ptr<WindowsFrameInfo> >
       windows_frame_info_[WINDOWS_FRAME_INFO_LAST];
+
+  // DWARF CFI stack walking data. The Module stores the initial rule sets
+  // and rule deltas as strings, just as they appear in the symbol file:
+  // although the file may contain hundreds of thousands of STACK CFI
+  // records, walking a stack will only ever use a few of them, so it's
+  // best to delay parsing a record until it's actually needed.
+
+  // STACK CFI INIT records: for each range, an initial set of register
+  // recovery rules. The RangeMap's itself gives the starting and ending
+  // addresses.
+  RangeMap<MemAddr, string> cfi_initial_rules_;
+
+  // STACK CFI records: at a given address, the changes to the register
+  // recovery rules that take effect at that address. The map key is the
+  // starting address; the ending address is the key of the next entry in
+  // this map, or the end of the range as given by the cfi_initial_rules_
+  // entry (which FindCFIFrameInfo looks up first).
+  map<MemAddr, string> cfi_delta_rules_;
 };
 
 BasicSourceLineResolver::BasicSourceLineResolver() : modules_(new ModuleMap) {
@@ -263,6 +296,17 @@ WindowsFrameInfo *BasicSourceLineResolver::FindWindowsFrameInfo(
   return NULL;
 }
 
+CFIFrameInfo *BasicSourceLineResolver::FindCFIFrameInfo(
+    const StackFrame *frame) const {
+  if (frame->module) {
+    ModuleMap::const_iterator it = modules_->find(frame->module->code_file());
+    if (it != modules_->end()) {
+      return it->second->FindCFIFrameInfo(frame);
+    }
+  }
+  return NULL;
+}
+
 class AutoFileCloser {
  public:
   AutoFileCloser(FILE *file) : file_(file) {}
@@ -515,6 +559,47 @@ WindowsFrameInfo *BasicSourceLineResolver::Module::FindWindowsFrameInfo(
   return NULL;
 }
 
+CFIFrameInfo *BasicSourceLineResolver::Module::FindCFIFrameInfo(
+    const StackFrame *frame) const {
+  MemAddr address = frame->instruction - frame->module->base_address();
+  MemAddr initial_base, initial_size;
+  string initial_rules;
+
+  // Find the initial rule whose range covers this address. That
+  // provides an initial set of register recovery rules. Then, walk
+  // forward from the initial rule's starting address to frame's
+  // instruction address, applying delta rules.
+  if (!cfi_initial_rules_.RetrieveRange(address, &initial_rules,
+                                        &initial_base, &initial_size)) {
+    return NULL;
+  }
+
+  // Create a frame info structure, and populate it with the rules from
+  // the STACK CFI INIT record.
+  scoped_ptr<CFIFrameInfo> rules(new CFIFrameInfo());
+  if (!ParseCFIRuleSet(initial_rules, rules.get()))
+    return NULL;
+
+  // Find the first delta rule that falls within the initial rule's range.
+  map<MemAddr, string>::const_iterator delta =
+    cfi_delta_rules_.lower_bound(initial_base);
+
+  // Apply delta rules up to and including the frame's address.
+  while (delta != cfi_delta_rules_.end() && delta->first <= address) {
+    ParseCFIRuleSet(delta->second, rules.get());
+    delta++;
+  }
+
+  return rules.release();
+}
+
+bool BasicSourceLineResolver::Module::ParseCFIRuleSet(
+    const string &rule_set, CFIFrameInfo *frame_info) const {
+  CFIFrameInfoParseHandler handler(frame_info);
+  CFIRuleParser parser(&handler);
+  return parser.Parse(rule_set);
+}
+
 // static
 bool BasicSourceLineResolver::Module::Tokenize(char *line, int max_tokens,
                                                vector<char*> *tokens) {
@@ -650,7 +735,11 @@ bool BasicSourceLineResolver::Module::ParseStackInfo(char *stack_info_line) {
   if (strcmp(platform, "WIN") == 0)
     return ParseWindowsFrameInfo(stack_info_line);
 
-  // Something we don't recognize.
+  // DWARF CFI stack frame info
+  else if (strcmp(platform, "CFI") == 0)
+    return ParseCFIFrameInfo(stack_info_line);
+
+  // Something unrecognized.
   else
     return false;
 }
@@ -721,6 +810,41 @@ bool BasicSourceLineResolver::Module::ParseWindowsFrameInfo(
   return true;
 }
 
+bool BasicSourceLineResolver::Module::ParseCFIFrameInfo(
+    char *stack_info_line) {
+  char *cursor;
+
+  // Is this an INIT record or a delta record?
+  char *init_or_address = strtok_r(stack_info_line, " \r\n", &cursor);
+  if (!init_or_address)
+    return false;
+
+  if (strcmp(init_or_address, "INIT") == 0) {
+    // This record has the form "STACK INIT <address> <size> <rules...>".
+    char *address_field = strtok_r(NULL, " \r\n", &cursor);
+    if (!address_field) return false;
+    
+    char *size_field = strtok_r(NULL, " \r\n", &cursor);
+    if (!size_field) return false;
+
+    char *initial_rules = strtok_r(NULL, "\r\n", &cursor);
+    if (!initial_rules) return false;
+
+    MemAddr address = strtoul(address_field, NULL, 16);
+    MemAddr size    = strtoul(size_field,    NULL, 16);
+    cfi_initial_rules_.StoreRange(address, size, initial_rules);
+    return true;
+  }
+
+  // This record has the form "STACK <address> <rules...>".
+  char *address_field = init_or_address;
+  char *delta_rules = strtok_r(NULL, "\r\n", &cursor);
+  if (!delta_rules) return false;
+  MemAddr address = strtoul(address_field, NULL, 16);
+  cfi_delta_rules_[address] = delta_rules;
+  return true;
+}
+
 bool BasicSourceLineResolver::CompareString::operator()(
     const string &s1, const string &s2) const {
   return strcmp(s1.c_str(), s2.c_str()) < 0;
diff --git a/src/processor/basic_source_line_resolver_unittest.cc b/src/processor/basic_source_line_resolver_unittest.cc
index c4cb6ea4..126ce6d6 100644
--- a/src/processor/basic_source_line_resolver_unittest.cc
+++ b/src/processor/basic_source_line_resolver_unittest.cc
@@ -32,10 +32,12 @@
 #include "google_breakpad/processor/basic_source_line_resolver.h"
 #include "google_breakpad/processor/code_module.h"
 #include "google_breakpad/processor/stack_frame.h"
+#include "google_breakpad/processor/memory_region.h"
 #include "processor/linked_ptr.h"
 #include "processor/logging.h"
 #include "processor/scoped_ptr.h"
 #include "processor/windows_frame_info.h"
+#include "processor/cfi_frame_info.h"
 
 #define ASSERT_TRUE(cond) \
   if (!(cond)) {                                                        \
@@ -51,11 +53,13 @@ namespace {
 
 using std::string;
 using google_breakpad::BasicSourceLineResolver;
+using google_breakpad::CFIFrameInfo;
 using google_breakpad::CodeModule;
-using google_breakpad::linked_ptr;
-using google_breakpad::scoped_ptr;
+using google_breakpad::MemoryRegion;
 using google_breakpad::StackFrame;
 using google_breakpad::WindowsFrameInfo;
+using google_breakpad::linked_ptr;
+using google_breakpad::scoped_ptr;
 
 class TestCodeModule : public CodeModule {
  public:
@@ -77,6 +81,70 @@ class TestCodeModule : public CodeModule {
   string code_file_;
 };
 
+// A mock memory region object, for use by the STACK CFI tests.
+class MockMemoryRegion: public MemoryRegion {
+  u_int64_t GetBase() const { return 0x10000; }
+  u_int32_t GetSize() const { return 0x01000; }
+  bool GetMemoryAtAddress(u_int64_t address, u_int8_t *value) const {
+    *value = address & 0xff;
+    return true;
+  }
+  bool GetMemoryAtAddress(u_int64_t address, u_int16_t *value) const {
+    *value = address & 0xffff;
+    return true;
+  }
+  bool GetMemoryAtAddress(u_int64_t address, u_int32_t *value) const {
+    switch (address) {
+      case 0x10008: *value = 0x98ecadc3; break; // saved %ebx
+      case 0x1000c: *value = 0x878f7524; break; // saved %esi
+      case 0x10010: *value = 0x6312f9a5; break; // saved %edi
+      case 0x10014: *value = 0x10038;    break; // caller's %ebp
+      case 0x10018: *value = 0xf6438648; break; // return address
+      default: *value = 0xdeadbeef;      break; // junk
+    }
+    return true;
+  }
+  bool GetMemoryAtAddress(u_int64_t address, u_int64_t *value) const {
+    *value = address;
+    return true;
+  }
+};
+
+// Verify that, for every association in ACTUAL, EXPECTED has the same
+// association. (That is, ACTUAL's associations should be a subset of
+// EXPECTED's.) Also verify that ACTUAL has associations for ".ra" and
+// ".cfa".
+static bool VerifyRegisters(
+    const char *file, int line,
+    const CFIFrameInfo::RegisterValueMap<u_int32_t> &expected,
+    const CFIFrameInfo::RegisterValueMap<u_int32_t> &actual) {
+  CFIFrameInfo::RegisterValueMap<u_int32_t>::const_iterator a;
+  a = actual.find(".cfa");
+  ASSERT_TRUE(a != actual.end());
+  a = actual.find(".ra");
+  ASSERT_TRUE(a != actual.end());
+  for (a = actual.begin(); a != actual.end(); a++) {
+    CFIFrameInfo::RegisterValueMap<u_int32_t>::const_iterator e =
+      expected.find(a->first);
+    if (e == expected.end()) {
+      fprintf(stderr, "%s:%d: unexpected register '%s' recovered, value 0x%x\n",
+              file, line, a->first.c_str(), a->second);
+      return false;
+    }
+    if (e->second != a->second) {
+      fprintf(stderr,
+              "%s:%d: register '%s' recovered value was 0x%x, expected 0x%x\n",
+              file, line, a->first.c_str(), a->second, e->second);
+      return false;
+    }
+    // Don't complain if this doesn't recover all registers. Although
+    // the DWARF spec says that unmentioned registers are undefined,
+    // GCC uses omission to mean that they are unchanged.
+  }
+  return true;
+}
+
+
 static bool VerifyEmpty(const StackFrame &frame) {
   ASSERT_TRUE(frame.function_name.empty());
   ASSERT_TRUE(frame.source_file_name.empty());
@@ -105,6 +173,7 @@ static bool RunTests() {
 
   StackFrame frame;
   scoped_ptr<WindowsFrameInfo> windows_frame_info;
+  scoped_ptr<CFIFrameInfo> cfi_frame_info;
   frame.instruction = 0x1000;
   frame.module = NULL;
   resolver.FillSourceLineInfo(&frame);
@@ -162,6 +231,99 @@ static bool RunTests() {
   windows_frame_info.reset(resolver.FindWindowsFrameInfo(&frame));
   ASSERT_FALSE(windows_frame_info.get());
 
+  // module1 has STACK CFI records covering 3d40..3def;
+  // module2 has STACK CFI records covering 3df0..3e9f;
+  // check that FindCFIFrameInfo doesn't claim to find any outside those ranges.
+  frame.instruction = 0x3d3f;
+  frame.module = &module1;
+  cfi_frame_info.reset(resolver.FindCFIFrameInfo(&frame));
+  ASSERT_FALSE(cfi_frame_info.get());
+
+  frame.instruction = 0x3e9f;
+  frame.module = &module1;
+  cfi_frame_info.reset(resolver.FindCFIFrameInfo(&frame));
+  ASSERT_FALSE(cfi_frame_info.get());
+
+  CFIFrameInfo::RegisterValueMap<u_int32_t> current_registers;
+  CFIFrameInfo::RegisterValueMap<u_int32_t> caller_registers;
+  CFIFrameInfo::RegisterValueMap<u_int32_t> expected_caller_registers;
+  MockMemoryRegion memory;
+
+  // Regardless of which instruction evaluation takes place at, it
+  // should produce the same values for the caller's registers.
+  expected_caller_registers[".cfa"] = 0x1001c;
+  expected_caller_registers[".ra"]  = 0xf6438648;
+  expected_caller_registers["$ebp"] = 0x10038;
+  expected_caller_registers["$ebx"] = 0x98ecadc3;
+  expected_caller_registers["$esi"] = 0x878f7524;
+  expected_caller_registers["$edi"] = 0x6312f9a5;
+
+  frame.instruction = 0x3d40;
+  frame.module = &module1;
+  current_registers.clear();
+  current_registers["$esp"] = 0x10018;
+  current_registers["$ebp"] = 0x10038;
+  current_registers["$ebx"] = 0x98ecadc3;
+  current_registers["$esi"] = 0x878f7524;
+  current_registers["$edi"] = 0x6312f9a5;
+  cfi_frame_info.reset(resolver.FindCFIFrameInfo(&frame));
+  ASSERT_TRUE(cfi_frame_info.get());
+  ASSERT_TRUE(cfi_frame_info.get()
+              ->FindCallerRegs<u_int32_t>(current_registers, memory,
+                                          &caller_registers));
+  VerifyRegisters(__FILE__, __LINE__,
+                  expected_caller_registers, caller_registers);
+
+  frame.instruction = 0x3d41;
+  current_registers["$esp"] = 0x10014;
+  cfi_frame_info.reset(resolver.FindCFIFrameInfo(&frame));
+  ASSERT_TRUE(cfi_frame_info.get());
+  ASSERT_TRUE(cfi_frame_info.get()
+              ->FindCallerRegs<u_int32_t>(current_registers, memory,
+                                          &caller_registers));
+  VerifyRegisters(__FILE__, __LINE__,
+                  expected_caller_registers, caller_registers);
+
+  frame.instruction = 0x3d43;
+  current_registers["$ebp"] = 0x10014;
+  cfi_frame_info.reset(resolver.FindCFIFrameInfo(&frame));
+  ASSERT_TRUE(cfi_frame_info.get());
+  ASSERT_TRUE(cfi_frame_info.get()
+              ->FindCallerRegs<u_int32_t>(current_registers, memory,
+                                          &caller_registers));
+  VerifyRegisters(__FILE__, __LINE__,
+                  expected_caller_registers, caller_registers);
+
+  frame.instruction = 0x3d54;
+  current_registers["$ebx"] = 0x6864f054U;
+  cfi_frame_info.reset(resolver.FindCFIFrameInfo(&frame));
+  ASSERT_TRUE(cfi_frame_info.get());
+  ASSERT_TRUE(cfi_frame_info.get()
+              ->FindCallerRegs<u_int32_t>(current_registers, memory,
+                                          &caller_registers));
+  VerifyRegisters(__FILE__, __LINE__,
+                  expected_caller_registers, caller_registers);
+
+  frame.instruction = 0x3d5a;
+  current_registers["$esi"] = 0x6285f79aU;
+  cfi_frame_info.reset(resolver.FindCFIFrameInfo(&frame));
+  ASSERT_TRUE(cfi_frame_info.get());
+  ASSERT_TRUE(cfi_frame_info.get()
+              ->FindCallerRegs<u_int32_t>(current_registers, memory,
+                                          &caller_registers));
+  VerifyRegisters(__FILE__, __LINE__,
+                  expected_caller_registers, caller_registers);
+
+  frame.instruction = 0x3d84;
+  current_registers["$edi"] = 0x64061449U;
+  cfi_frame_info.reset(resolver.FindCFIFrameInfo(&frame));
+  ASSERT_TRUE(cfi_frame_info.get());
+  ASSERT_TRUE(cfi_frame_info.get()
+              ->FindCallerRegs<u_int32_t>(current_registers, memory,
+                                          &caller_registers));
+  VerifyRegisters(__FILE__, __LINE__,
+                  expected_caller_registers, caller_registers);
+
   frame.instruction = 0x2900;
   frame.module = &module1;
   resolver.FillSourceLineInfo(&frame);
diff --git a/src/processor/cfi_frame_info-inl.h b/src/processor/cfi_frame_info-inl.h
new file mode 100644
index 00000000..e55e6ea2
--- /dev/null
+++ b/src/processor/cfi_frame_info-inl.h
@@ -0,0 +1,119 @@
+// -*- mode: C++ -*-
+
+// Copyright (c) 2010, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>
+
+// cfi_frame_info-inl.h: Definitions for cfi_frame_info.h inlined functions.
+
+#ifndef PROCESSOR_CFI_FRAME_INFO_INL_H_
+#define PROCESSOR_CFI_FRAME_INFO_INL_H_
+
+#include <string.h>
+
+namespace google_breakpad {
+
+template <typename RegisterType, class RawContextType>
+bool SimpleCFIWalker<RegisterType, RawContextType>::FindCallerRegisters(
+    const MemoryRegion &memory,
+    const CFIFrameInfo &cfi_frame_info,
+    const RawContextType &callee_context,
+    int callee_validity,
+    RawContextType *caller_context,
+    int *caller_validity) const {
+  typedef CFIFrameInfo::RegisterValueMap<RegisterType> ValueMap;
+  ValueMap callee_registers;
+  ValueMap caller_registers;
+  // Just for brevity.
+  typename ValueMap::const_iterator caller_none = caller_registers.end();
+
+  // Populate callee_registers with register values from callee_context.
+  for (size_t i = 0; i < map_size_; i++) {
+    const RegisterSet &r = register_map_[i];
+    if (callee_validity & r.validity_flag)
+      callee_registers[r.name] = callee_context.*r.context_member;
+  }
+
+  // Apply the rules, and see what register values they yield.
+  if (!cfi_frame_info.FindCallerRegs<RegisterType>(callee_registers, memory,
+                                                   &caller_registers))
+    return false;
+
+  // Populate *caller_context with the values the rules placed in
+  // caller_registers.
+  memset(caller_context, 0xda, sizeof(caller_context));
+  *caller_validity = 0;
+  for (size_t i = 0; i < map_size_; i++) {
+    const RegisterSet &r = register_map_[i];
+    typename ValueMap::const_iterator caller_entry;
+
+    // Did the rules provide a value for this register by its name?
+    caller_entry = caller_registers.find(r.name);
+    if (caller_entry != caller_none) {
+      caller_context->*r.context_member = caller_entry->second;
+      *caller_validity |= r.validity_flag;
+      continue;
+    }
+
+    // Did the rules provide a value for this register under its
+    // alternate name?
+    if (r.alternate_name) {
+      caller_entry = caller_registers.find(r.alternate_name);
+      if (caller_entry != caller_none) {
+        caller_context->*r.context_member = caller_entry->second;
+        *caller_validity |= r.validity_flag;
+        continue;
+      }
+    }
+
+    // Is this a callee-saves register? The walker assumes that these
+    // still hold the caller's value if the CFI doesn't mention them.
+    //
+    // Note that other frame walkers may fail to recover callee-saves
+    // registers; for example, the x86 "traditional" strategy only
+    // recovers %eip, %esp, and %ebp, even though %ebx, %esi, and %edi
+    // are callee-saves, too. It is not correct to blindly set the
+    // valid bit for all callee-saves registers, without first
+    // checking its validity bit in the callee.
+    if (r.callee_saves && (callee_validity & r.validity_flag) != 0) {
+      caller_context->*r.context_member = callee_context.*r.context_member;
+      *caller_validity |= r.validity_flag;
+      continue;
+    }
+
+    // Otherwise, the register's value is unknown.
+  }
+
+  return true;
+}
+
+} // namespace google_breakpad
+
+#endif // PROCESSOR_CFI_FRAME_INFO_INL_H_
diff --git a/src/processor/cfi_frame_info.cc b/src/processor/cfi_frame_info.cc
new file mode 100644
index 00000000..0cca6646
--- /dev/null
+++ b/src/processor/cfi_frame_info.cc
@@ -0,0 +1,157 @@
+// Copyright (c) 2010, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>
+
+// cfi_frame_info.cc: Implementation of CFIFrameInfo class.
+// See cfi_frame_info.h for details.
+
+#include <cstring>
+
+#include "processor/cfi_frame_info.h"
+#include "processor/postfix_evaluator-inl.h"
+#include "processor/scoped_ptr.h"
+
+namespace google_breakpad {
+
+template<typename V>
+bool CFIFrameInfo::FindCallerRegs(const RegisterValueMap<V> &registers,
+                                  const MemoryRegion &memory,
+                                  RegisterValueMap<V> *caller_registers) const {
+  // If there are not rules for both .ra and .cfa in effect at this address,
+  // don't use this CFI data for stack walking.
+  if (cfa_rule_.empty() || ra_rule_.empty())
+    return false;
+
+  RegisterValueMap<V> working;
+  PostfixEvaluator<V> evaluator(&working, &memory);
+
+  caller_registers->clear();
+
+  // First, compute the CFA.
+  V cfa;
+  working = registers;
+  if (!evaluator.EvaluateForValue(cfa_rule_, &cfa))
+    return false;
+
+  // Then, compute the return address.
+  V ra;
+  working = registers;
+  working[".cfa"] = cfa;
+  if (!evaluator.EvaluateForValue(ra_rule_, &ra))
+    return false;
+
+  // Now, compute values for all the registers register_rules_ mentions.
+  for (RuleMap::const_iterator it = register_rules_.begin();
+       it != register_rules_.end(); it++) {
+    V value;
+    working = registers;
+    working[".cfa"] = cfa;
+    if (!evaluator.EvaluateForValue(it->second, &value))
+      return false;
+    (*caller_registers)[it->first] = value;
+  }
+
+  (*caller_registers)[".ra"] = ra;
+  (*caller_registers)[".cfa"] = cfa;
+
+  return true;
+}
+
+// Explicit instantiations for 32-bit and 64-bit architectures.
+template bool CFIFrameInfo::FindCallerRegs<u_int32_t>(
+    const RegisterValueMap<u_int32_t> &registers,
+    const MemoryRegion &memory,
+    RegisterValueMap<u_int32_t> *caller_registers) const;
+template bool CFIFrameInfo::FindCallerRegs<u_int64_t>(
+    const RegisterValueMap<u_int64_t> &registers,
+    const MemoryRegion &memory,
+    RegisterValueMap<u_int64_t> *caller_registers) const;
+
+bool CFIRuleParser::Parse(const string &rule_set) {
+  size_t rule_set_len = rule_set.size();
+  scoped_array<char> working_copy(new char[rule_set_len + 1]);
+  memcpy(working_copy.get(), rule_set.data(), rule_set_len);
+  working_copy[rule_set_len] = '\0';
+
+  name_.clear();
+  expression_.clear();
+
+  char *cursor;
+  static const char token_breaks[] = " \t\r\n";
+  char *token = strtok_r(working_copy.get(), token_breaks, &cursor);
+
+  for (;;) {
+    // End of rule set?
+    if (!token) return Report();
+
+    // Register/pseudoregister name?
+    size_t token_len = strlen(token);
+    if (token_len >= 1 && token[token_len - 1] == ':') {
+      // Names can't be empty.
+      if (token_len < 2) return false;
+      // If there is any pending content, report it.
+      if (!name_.empty() || !expression_.empty()) {
+        if (!Report()) return false;
+      }
+      name_.assign(token, token_len - 1);
+      expression_.clear();
+    } else {
+      // Another expression component.
+      assert(token_len > 0); // strtok_r guarantees this, I think.
+      if (!expression_.empty())
+        expression_ += ' ';
+      expression_ += token;
+    }
+    token = strtok_r(NULL, token_breaks, &cursor);
+  }
+}
+
+bool CFIRuleParser::Report() {
+  if (name_.empty() || expression_.empty()) return false;
+  if (name_ == ".cfa") handler_->CFARule(expression_);
+  else if (name_ == ".ra") handler_->RARule(expression_);
+  else handler_->RegisterRule(name_, expression_);
+  return true;
+}
+
+void CFIFrameInfoParseHandler::CFARule(const string &expression) {
+  frame_info_->SetCFARule(expression);
+}
+
+void CFIFrameInfoParseHandler::RARule(const string &expression) {
+  frame_info_->SetRARule(expression);
+}
+
+void CFIFrameInfoParseHandler::RegisterRule(const string &name,
+                                            const string &expression) {
+  frame_info_->SetRegisterRule(name, expression);
+}
+
+} // namespace google_breakpad
diff --git a/src/processor/cfi_frame_info.h b/src/processor/cfi_frame_info.h
new file mode 100644
index 00000000..f537296a
--- /dev/null
+++ b/src/processor/cfi_frame_info.h
@@ -0,0 +1,271 @@
+// -*- mode: C++ -*-
+
+// Copyright (c) 2010, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>
+
+// cfi_frame_info.h: Define the CFIFrameInfo class, which holds the
+// set of 'STACK CFI'-derived register recovery rules that apply at a
+// given instruction.
+
+#ifndef PROCESSOR_CFI_FRAME_INFO_H_
+#define PROCESSOR_CFI_FRAME_INFO_H_
+
+#include <map>
+#include <string>
+
+#include "google_breakpad/common/breakpad_types.h"
+
+namespace google_breakpad {
+
+using std::map;
+using std::string;
+
+class MemoryRegion;
+
+// A set of rules for recovering the calling frame's registers'
+// values, when the PC is at a given address in the current frame's
+// function. See the description of 'STACK CFI' records at:
+//
+// http://code.google.com/p/google-breakpad/wiki/SymbolFiles
+//
+// To prepare an instance of CFIFrameInfo for use at a given
+// instruction, first populate it with the rules from the 'STACK CFI
+// INIT' record that covers that instruction, and then apply the
+// changes given by the 'STACK CFI' records up to our instruction's
+// address. Then, use the FindCallerRegs member function to apply the
+// rules to the callee frame's register values, yielding the caller
+// frame's register values.
+class CFIFrameInfo {
+ public:
+  // A map from register names onto values.
+  template<typename ValueType> class RegisterValueMap: 
+    public map<string, ValueType> { };
+
+  // Set the expression for computing a call frame address, return
+  // address, or register's value. At least the CFA rule and the RA
+  // rule must be set before calling FindCallerRegs.
+  void SetCFARule(const string &expression) { cfa_rule_ = expression; }
+  void SetRARule(const string &expression)  { ra_rule_ = expression; }
+  void SetRegisterRule(const string &register_name, const string &expression) {
+    register_rules_[register_name] = expression;
+  }
+
+  // Compute the values of the calling frame's registers, according to
+  // this rule set. Use ValueType in expression evaluation; this
+  // should be u_int32_t on machines with 32-bit addresses, or
+  // u_int64_t on machines with 64-bit addresses.
+  //
+  // Return true on success, false otherwise.
+  //
+  // MEMORY provides access to the contents of the stack. REGISTERS is
+  // a dictionary mapping the names of registers whose values are
+  // known in the current frame to their values. CALLER_REGISTERS is
+  // populated with the values of the recoverable registers in the
+  // frame that called the current frame.
+  //
+  // In addition, CALLER_REGISTERS[".ra"] will be the return address,
+  // and CALLER_REGISTERS[".cfa"] will be the call frame address.
+  // These may be helpful in computing the caller's PC and stack
+  // pointer, if their values are not explicitly specified.
+  template<typename ValueType>
+  bool FindCallerRegs(const RegisterValueMap<ValueType> &registers,
+                      const MemoryRegion &memory,
+                      RegisterValueMap<ValueType> *caller_registers) const;
+
+ private:
+
+  // A map from register names onto evaluation rules. 
+  typedef map<string, string> RuleMap;
+
+  // In this type, a "postfix expression" is an expression of the sort
+  // interpreted by google_breakpad::PostfixEvaluator.
+
+  // A postfix expression for computing the current frame's CFA (call
+  // frame address). The CFA is a reference address for the frame that
+  // remains unchanged throughout the frame's lifetime. You should
+  // evaluate this expression with a dictionary initially populated
+  // with the values of the current frame's known registers.
+  string cfa_rule_;
+
+  // The following expressions should be evaluated with a dictionary
+  // initially populated with the values of the current frame's known
+  // registers, and with ".cfa" set to the result of evaluating the
+  // cfa_rule expression, above.
+
+  // A postfix expression for computing the current frame's return
+  // address. 
+  string ra_rule_;
+
+  // For a register named REG, rules[REG] is a postfix expression
+  // which leaves the value of REG in the calling frame on the top of
+  // the stack. You should evaluate this expression
+  RuleMap register_rules_;
+};
+
+// A parser for STACK CFI-style rule sets.
+// This may seem bureaucratic: there's no legitimate run-time reason
+// to use a parser/handler pattern for this, as it's not a likely
+// reuse boundary. But doing so makes finer-grained unit testing
+// possible.
+class CFIRuleParser {
+ public:
+
+  class Handler {
+   public:
+    Handler() { }
+    virtual ~Handler() { }
+
+    // The input specifies EXPRESSION as the CFA/RA computation rule.
+    virtual void CFARule(const string &expression) = 0;
+    virtual void RARule(const string &expression) = 0;
+
+    // The input specifies EXPRESSION as the recovery rule for register NAME.
+    virtual void RegisterRule(const string &name, const string &expression) = 0;
+  };
+    
+  // Construct a parser which feeds its results to HANDLER.
+  CFIRuleParser(Handler *handler) : handler_(handler) { }
+
+  // Parse RULE_SET as a set of CFA computation and RA/register
+  // recovery rules, as appearing in STACK CFI records. Report the
+  // results of parsing by making the appropriate calls to handler_.
+  // Return true if parsing was successful, false otherwise.
+  bool Parse(const string &rule_set);
+
+ private:
+  // Report any accumulated rule to handler_
+  bool Report();
+
+  // The handler to which the parser reports its findings.
+  Handler *handler_;
+
+  // Working data.
+  string name_, expression_;
+};
+
+// A handler for rule set parsing that populates a CFIFrameInfo with
+// the results.
+class CFIFrameInfoParseHandler: public CFIRuleParser::Handler {
+ public:
+  // Populate FRAME_INFO with the results of parsing.
+  CFIFrameInfoParseHandler(CFIFrameInfo *frame_info)
+      : frame_info_(frame_info) { }
+
+  void CFARule(const string &expression);
+  void RARule(const string &expression);
+  void RegisterRule(const string &name, const string &expression);
+
+ private:
+  CFIFrameInfo *frame_info_;
+};
+
+// A utility class template for simple 'STACK CFI'-driven stack walkers.
+// Given a CFIFrameInfo instance, a table describing the architecture's
+// register set, and a context holding the last frame's registers, an
+// instance of this class can populate a new context with the caller's
+// registers.
+//
+// This class template doesn't use any internal knowledge of CFIFrameInfo
+// or the other stack walking structures; it just uses the public interface
+// of CFIFrameInfo to do the usual things. But the logic it handles should
+// be common to many different architectures' stack walkers, so wrapping it
+// up in a class should allow the walkers to share code.
+//
+// RegisterType should be the type of this architecture's registers, either
+// u_int32_t or u_int64_t. RawContextType should be the raw context
+// structure type for this architecture.
+template <typename RegisterType, class RawContextType>
+class SimpleCFIWalker {
+ public:
+  // A structure describing one architecture register.
+  struct RegisterSet {
+    // The register name, as it appears in STACK CFI rules.
+    const char *name;
+
+    // An alternate name that the register's value might be found
+    // under in a register value dictionary, or NULL. When generating
+    // names, prefer NAME to this value. It's common to list ".cfa" as
+    // an alternative name for the stack pointer, and ".ra" as an
+    // alternative name for the instruction pointer.
+    const char *alternate_name;
+
+    // True if the callee is expected to preserve the value of this
+    // register. If this flag is true for some register R, and the STACK
+    // CFI records provide no rule to recover R, then SimpleCFIWalker
+    // assumes that the callee has not changed R's value, and the caller's
+    // value for R is that currently in the callee's context.
+    bool callee_saves;
+
+    // The ContextValidity flag representing the register's presence.
+    int validity_flag;
+
+    // A pointer to the RawContextType member that holds the
+    // register's value.
+    RegisterType RawContextType::*context_member;
+  };
+
+  // Create a simple CFI-based frame walker, given a description of the
+  // architecture's register set. REGISTER_MAP is an array of
+  // RegisterSet structures; MAP_SIZE is the number of elements in the
+  // array.
+  SimpleCFIWalker(const RegisterSet *register_map, size_t map_size)
+      : register_map_(register_map), map_size_(map_size) { }
+
+  // Compute the calling frame's raw context given the callee's raw
+  // context.
+  //
+  // Given:
+  //
+  // - MEMORY, holding the stack's contents,
+  // - CFI_FRAME_INFO, describing the called function,
+  // - CALLEE_CONTEXT, holding the called frame's registers, and
+  // - CALLEE_VALIDITY, indicating which registers in CALLEE_CONTEXT are valid,
+  //
+  // fill in CALLER_CONTEXT with the caller's register values, and set
+  // CALLER_VALIDITY to indicate which registers are valid in
+  // CALLER_CONTEXT. Return true on success, or false on failure.
+  bool FindCallerRegisters(const MemoryRegion &memory,
+                           const CFIFrameInfo &cfi_frame_info,
+                           const RawContextType &callee_context,
+                           int callee_validity,
+                           RawContextType *caller_context,
+                           int *caller_validity) const;
+
+ private:
+  const RegisterSet *register_map_;
+  size_t map_size_;
+};
+
+}  // namespace google_breakpad
+
+#include "cfi_frame_info-inl.h"
+
+#endif  // PROCESSOR_CFI_FRAME_INFO_H_
diff --git a/src/processor/cfi_frame_info_unittest.cc b/src/processor/cfi_frame_info_unittest.cc
new file mode 100644
index 00000000..5f776fe8
--- /dev/null
+++ b/src/processor/cfi_frame_info_unittest.cc
@@ -0,0 +1,531 @@
+// Copyright (c) 2010, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// Original author: Jim Blandy <jimb@mozilla.com> <jimb@red-bean.com>
+
+// cfi_frame_info_unittest.cc: Unit tests for CFIFrameInfo,
+// CFIRuleParser, CFIFrameInfoParseHandler, and SimpleCFIWalker.
+
+#include <string.h>
+
+#include "breakpad_googletest_includes.h"
+#include "processor/cfi_frame_info.h"
+#include "google_breakpad/processor/memory_region.h"
+
+using google_breakpad::CFIFrameInfo;
+using google_breakpad::CFIFrameInfoParseHandler;
+using google_breakpad::CFIRuleParser;
+using google_breakpad::MemoryRegion;
+using google_breakpad::SimpleCFIWalker;
+using std::string;
+using testing::_;
+using testing::A;
+using testing::AtMost;
+using testing::DoAll;
+using testing::Return;
+using testing::SetArgumentPointee;
+using testing::Test;
+
+class MockMemoryRegion: public MemoryRegion {
+ public:
+  MOCK_CONST_METHOD0(GetBase, u_int64_t());
+  MOCK_CONST_METHOD0(GetSize, u_int32_t());
+  MOCK_CONST_METHOD2(GetMemoryAtAddress, bool(u_int64_t, u_int8_t *));
+  MOCK_CONST_METHOD2(GetMemoryAtAddress, bool(u_int64_t, u_int16_t *));
+  MOCK_CONST_METHOD2(GetMemoryAtAddress, bool(u_int64_t, u_int32_t *));
+  MOCK_CONST_METHOD2(GetMemoryAtAddress, bool(u_int64_t, u_int64_t *));
+};
+
+// Handy definitions for all tests.
+struct CFIFixture {
+
+  // Set up the mock memory object to expect no references.
+  void ExpectNoMemoryReferences() {
+    EXPECT_CALL(memory, GetBase()).Times(0);
+    EXPECT_CALL(memory, GetSize()).Times(0);
+    EXPECT_CALL(memory, GetMemoryAtAddress(_, A<u_int8_t *>())).Times(0);
+    EXPECT_CALL(memory, GetMemoryAtAddress(_, A<u_int16_t *>())).Times(0);
+    EXPECT_CALL(memory, GetMemoryAtAddress(_, A<u_int32_t *>())).Times(0);
+    EXPECT_CALL(memory, GetMemoryAtAddress(_, A<u_int64_t *>())).Times(0);
+  }
+
+  CFIFrameInfo cfi;
+  MockMemoryRegion memory;
+  CFIFrameInfo::RegisterValueMap<u_int64_t> registers, caller_registers;
+};
+
+class Simple: public CFIFixture, public Test { };
+
+// FindCallerRegs should fail if no .cfa rule is provided.
+TEST_F(Simple, NoCFA) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetRARule("0");
+  ASSERT_FALSE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                             &caller_registers));
+}
+
+// FindCallerRegs should fail if no .ra rule is provided.
+TEST_F(Simple, NoRA) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule("0");
+  ASSERT_FALSE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                             &caller_registers));
+}
+
+TEST_F(Simple, SetCFAAndRARule) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule("330903416631436410");
+  cfi.SetRARule("5870666104170902211");
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(2U, caller_registers.size());
+  ASSERT_EQ(330903416631436410ULL, caller_registers[".cfa"]);
+  ASSERT_EQ(5870666104170902211ULL, caller_registers[".ra"]);
+}
+
+TEST_F(Simple, SetManyRules) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule("$temp1 68737028 = $temp2 61072337 = $temp1 $temp2 -");
+  cfi.SetRARule(".cfa 99804755 +");
+  cfi.SetRegisterRule("register1", ".cfa 54370437 *");
+  cfi.SetRegisterRule("vodkathumbscrewingly", "24076308 .cfa +");
+  cfi.SetRegisterRule("pubvexingfjordschmaltzy", ".cfa 29801007 -");
+  cfi.SetRegisterRule("uncopyrightables", "92642917 .cfa /");
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(6U, caller_registers.size());
+  ASSERT_EQ(7664691U,           caller_registers[".cfa"]);
+  ASSERT_EQ(107469446U,         caller_registers[".ra"]);
+  ASSERT_EQ(416732599139967ULL, caller_registers["register1"]);
+  ASSERT_EQ(31740999U,          caller_registers["vodkathumbscrewingly"]);
+  ASSERT_EQ(-22136316ULL,       caller_registers["pubvexingfjordschmaltzy"]);
+  ASSERT_EQ(12U,                caller_registers["uncopyrightables"]);
+}
+
+TEST_F(Simple, RulesOverride) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule("330903416631436410");
+  cfi.SetRARule("5870666104170902211");
+  cfi.SetCFARule("2828089117179001");
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(2U, caller_registers.size());
+  ASSERT_EQ(2828089117179001ULL, caller_registers[".cfa"]);
+  ASSERT_EQ(5870666104170902211ULL, caller_registers[".ra"]);
+}
+
+class Scope: public CFIFixture, public Test { };
+
+// There should be no value for .cfa in scope when evaluating the CFA rule.
+TEST_F(Scope, CFALacksCFA) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule(".cfa");
+  cfi.SetRARule("0");
+  ASSERT_FALSE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                             &caller_registers));
+}
+
+// There should be no value for .ra in scope when evaluating the CFA rule.
+TEST_F(Scope, CFALacksRA) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule(".ra");
+  cfi.SetRARule("0");
+  ASSERT_FALSE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                             &caller_registers));
+}
+
+// The current frame's registers should be in scope when evaluating
+// the CFA rule.
+TEST_F(Scope, CFASeesCurrentRegs) {
+  ExpectNoMemoryReferences();
+
+  registers[".baraminology"] = 0x06a7bc63e4f13893ULL;
+  registers[".ornithorhynchus"] = 0x5e0bf850bafce9d2ULL;
+  cfi.SetCFARule(".baraminology .ornithorhynchus +");
+  cfi.SetRARule("0");
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(2U, caller_registers.size());
+  ASSERT_EQ(0x06a7bc63e4f13893ULL + 0x5e0bf850bafce9d2ULL,
+            caller_registers[".cfa"]);
+}
+
+// .cfa should be in scope in the return address expression.
+TEST_F(Scope, RASeesCFA) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule("48364076");
+  cfi.SetRARule(".cfa");
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(2U, caller_registers.size());
+  ASSERT_EQ(48364076U, caller_registers[".ra"]);
+}
+
+// There should be no value for .ra in scope when evaluating the CFA rule.
+TEST_F(Scope, RALacksRA) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule("0");
+  cfi.SetRARule(".ra");
+  ASSERT_FALSE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                             &caller_registers));
+}
+
+// The current frame's registers should be in scope in the return
+// address expression.
+TEST_F(Scope, RASeesCurrentRegs) {
+  ExpectNoMemoryReferences();
+
+  registers["noachian"] = 0x54dc4a5d8e5eb503ULL;
+  cfi.SetCFARule("10359370");
+  cfi.SetRARule("noachian");
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(2U, caller_registers.size());
+  ASSERT_EQ(0x54dc4a5d8e5eb503ULL, caller_registers[".ra"]);
+}
+
+// .cfa should be in scope for register rules.
+TEST_F(Scope, RegistersSeeCFA) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule("6515179");
+  cfi.SetRARule(".cfa");
+  cfi.SetRegisterRule("rogerian", ".cfa");
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(3U, caller_registers.size());
+  ASSERT_EQ(6515179U, caller_registers["rogerian"]);
+}
+
+// The return address should not be in scope for register rules.
+TEST_F(Scope, RegsLackRA) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule("42740329");
+  cfi.SetRARule("27045204");
+  cfi.SetRegisterRule("$r1", ".ra");
+  ASSERT_FALSE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                             &caller_registers));
+}
+
+// Register rules can see the current frame's register values.
+TEST_F(Scope, RegsSeeRegs) {
+  ExpectNoMemoryReferences();
+
+  registers["$r1"] = 0x6ed3582c4bedb9adULL;
+  registers["$r2"] = 0xd27d9e742b8df6d0ULL;
+  cfi.SetCFARule("88239303");
+  cfi.SetRARule("30503835");
+  cfi.SetRegisterRule("$r1", "$r1 42175211 = $r2");
+  cfi.SetRegisterRule("$r2", "$r2 21357221 = $r1");
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(4U, caller_registers.size());
+  ASSERT_EQ(0xd27d9e742b8df6d0ULL, caller_registers["$r1"]);
+  ASSERT_EQ(0x6ed3582c4bedb9adULL, caller_registers["$r2"]);
+}
+
+// Each rule's temporaries are separate.
+TEST_F(Scope, SeparateTempsRA) {
+  ExpectNoMemoryReferences();
+
+  cfi.SetCFARule("$temp1 76569129 = $temp1");
+  cfi.SetRARule("0");
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+
+  cfi.SetCFARule("$temp1 76569129 = $temp1");
+  cfi.SetRARule("$temp1");
+  ASSERT_FALSE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                             &caller_registers));
+}
+
+class MockCFIRuleParserHandler: public CFIRuleParser::Handler {
+ public:
+  MOCK_METHOD1(CFARule, void(const string &));
+  MOCK_METHOD1(RARule,  void(const string &));
+  MOCK_METHOD2(RegisterRule, void(const string &, const string &));
+};
+
+// A fixture class for testing CFIRuleParser.
+class CFIParserFixture {
+ public:
+  CFIParserFixture() : parser(&mock_handler) {
+    // Expect no parsing results to be reported to mock_handler. Individual
+    // tests can override this.
+    EXPECT_CALL(mock_handler, CFARule(_)).Times(0);
+    EXPECT_CALL(mock_handler, RARule(_)).Times(0);
+    EXPECT_CALL(mock_handler, RegisterRule(_, _)).Times(0);
+  }
+
+  MockCFIRuleParserHandler mock_handler;
+  CFIRuleParser parser;
+};
+
+class Parser: public CFIParserFixture, public Test { };
+
+TEST_F(Parser, Empty) {
+  EXPECT_FALSE(parser.Parse(""));
+}
+
+TEST_F(Parser, LoneColon) {
+  EXPECT_FALSE(parser.Parse(":"));
+}
+
+TEST_F(Parser, CFANoExpr) {
+  EXPECT_FALSE(parser.Parse(".cfa:"));
+}
+
+TEST_F(Parser, CFANoColonNoExpr) {
+  EXPECT_FALSE(parser.Parse(".cfa"));
+}
+
+TEST_F(Parser, RANoExpr) {
+  EXPECT_FALSE(parser.Parse(".ra:"));
+}
+
+TEST_F(Parser, RANoColonNoExpr) {
+  EXPECT_FALSE(parser.Parse(".ra"));
+}
+
+TEST_F(Parser, RegNoExpr) {
+  EXPECT_FALSE(parser.Parse("reg:"));
+}
+
+TEST_F(Parser, NoName) {
+  EXPECT_FALSE(parser.Parse("expr"));
+}
+
+TEST_F(Parser, NoNameTwo) {
+  EXPECT_FALSE(parser.Parse("expr1 expr2"));
+}
+
+TEST_F(Parser, StartsWithExpr) {
+  EXPECT_FALSE(parser.Parse("expr1 reg: expr2"));
+}
+
+TEST_F(Parser, CFA) {
+  EXPECT_CALL(mock_handler, CFARule("spleen")).WillOnce(Return());
+  EXPECT_TRUE(parser.Parse(".cfa: spleen"));
+}
+
+TEST_F(Parser, RA) {
+  EXPECT_CALL(mock_handler, RARule("notoriety")).WillOnce(Return());
+  EXPECT_TRUE(parser.Parse(".ra: notoriety"));
+}
+
+TEST_F(Parser, Reg) {
+  EXPECT_CALL(mock_handler, RegisterRule("nemo", "mellifluous"))
+      .WillOnce(Return());
+  EXPECT_TRUE(parser.Parse("nemo: mellifluous"));
+}
+
+TEST_F(Parser, CFARARegs) {
+  EXPECT_CALL(mock_handler, CFARule("cfa expression")).WillOnce(Return());
+  EXPECT_CALL(mock_handler, RARule("ra expression")).WillOnce(Return());
+  EXPECT_CALL(mock_handler, RegisterRule("galba", "praetorian"))
+      .WillOnce(Return());
+  EXPECT_CALL(mock_handler, RegisterRule("otho", "vitellius"))
+      .WillOnce(Return());
+  EXPECT_TRUE(parser.Parse(".cfa: cfa expression .ra: ra expression "
+                    "galba: praetorian otho: vitellius"));
+}
+
+TEST_F(Parser, Whitespace) {
+  EXPECT_CALL(mock_handler, RegisterRule("r1", "r1 expression"))
+      .WillOnce(Return());
+  EXPECT_CALL(mock_handler, RegisterRule("r2", "r2 expression"))
+      .WillOnce(Return());
+  EXPECT_TRUE(parser.Parse(" r1:\tr1\nexpression \tr2:\t\rr2\r\n "
+                           "expression  \n"));
+}
+
+TEST_F(Parser, WhitespaceLoneColon) {
+  EXPECT_FALSE(parser.Parse("  \n:\t  "));
+}
+
+TEST_F(Parser, EmptyName) {
+  EXPECT_CALL(mock_handler, RegisterRule("reg", _))
+      .Times(AtMost(1))
+      .WillRepeatedly(Return());
+  EXPECT_FALSE(parser.Parse("reg: expr1 : expr2"));
+}
+
+TEST_F(Parser, RuleLoneColon) {
+  EXPECT_CALL(mock_handler, RegisterRule("r1", "expr"))
+      .Times(AtMost(1))
+      .WillRepeatedly(Return());
+  EXPECT_FALSE(parser.Parse(" r1:   expr   :"));
+}
+
+TEST_F(Parser, RegNoExprRule) {
+  EXPECT_CALL(mock_handler, RegisterRule("r1", "expr"))
+      .Times(AtMost(1))
+      .WillRepeatedly(Return());
+  EXPECT_FALSE(parser.Parse("r0: r1:   expr"));
+}
+
+class ParseHandlerFixture: public CFIFixture {
+ public:
+  ParseHandlerFixture() : CFIFixture(), handler(&cfi) { }
+  CFIFrameInfoParseHandler handler;
+};
+
+class ParseHandler: public ParseHandlerFixture, public Test { };
+
+TEST_F(ParseHandler, CFARARule) {
+  handler.CFARule("reg-for-cfa");
+  handler.RARule("reg-for-ra");
+  registers["reg-for-cfa"] = 0x268a9a4a3821a797ULL;
+  registers["reg-for-ra"] = 0x6301b475b8b91c02ULL;
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(0x268a9a4a3821a797ULL, caller_registers[".cfa"]);
+  ASSERT_EQ(0x6301b475b8b91c02ULL, caller_registers[".ra"]);
+}
+
+TEST_F(ParseHandler, RegisterRules) {
+  handler.CFARule("reg-for-cfa");
+  handler.RARule("reg-for-ra");
+  handler.RegisterRule("reg1", "reg-for-reg1");
+  handler.RegisterRule("reg2", "reg-for-reg2");
+  registers["reg-for-cfa"] = 0x268a9a4a3821a797ULL;
+  registers["reg-for-ra"] = 0x6301b475b8b91c02ULL;
+  registers["reg-for-reg1"] = 0x06cde8e2ff062481ULL;
+  registers["reg-for-reg2"] = 0xff0c4f76403173e2ULL;
+  ASSERT_TRUE(cfi.FindCallerRegs<u_int64_t>(registers, memory,
+                                            &caller_registers));
+  ASSERT_EQ(0x268a9a4a3821a797ULL, caller_registers[".cfa"]);
+  ASSERT_EQ(0x6301b475b8b91c02ULL, caller_registers[".ra"]);
+  ASSERT_EQ(0x06cde8e2ff062481ULL, caller_registers["reg1"]);
+  ASSERT_EQ(0xff0c4f76403173e2ULL, caller_registers["reg2"]);
+}
+
+struct SimpleCFIWalkerFixture {
+  struct RawContext {
+    u_int64_t r0, r1, r2, r3, r4, sp, pc;
+  };
+  enum Validity {
+    R0_VALID = 0x01,
+    R1_VALID = 0x02,
+    R2_VALID = 0x04,
+    R3_VALID = 0x08,
+    R4_VALID = 0x10,
+    SP_VALID = 0x20,
+    PC_VALID = 0x40
+  };
+  typedef SimpleCFIWalker<u_int64_t, RawContext> CFIWalker;
+
+  SimpleCFIWalkerFixture()
+      : walker(register_map,
+               sizeof(register_map) / sizeof(register_map[0])) { }
+
+  static CFIWalker::RegisterSet register_map[7];
+  CFIFrameInfo call_frame_info;
+  CFIWalker walker;
+  MockMemoryRegion memory;
+  RawContext callee_context, caller_context;
+};
+
+SimpleCFIWalkerFixture::CFIWalker::RegisterSet
+SimpleCFIWalkerFixture::register_map[7] = {
+  { "r0", NULL,   true,  R0_VALID, &RawContext::r0 },
+  { "r1", NULL,   true,  R1_VALID, &RawContext::r1 },
+  { "r2", NULL,   false, R2_VALID, &RawContext::r2 },
+  { "r3", NULL,   false, R3_VALID, &RawContext::r3 },
+  { "r4", NULL,   true,  R4_VALID, &RawContext::r4 },
+  { "sp", ".cfa", true,  SP_VALID, &RawContext::sp },
+  { "pc", ".ra",  true,  PC_VALID, &RawContext::pc },
+};
+
+class SimpleWalker: public SimpleCFIWalkerFixture, public Test { };
+
+TEST_F(SimpleWalker, Walk) {
+  // Stack_top is the current stack pointer, pointing to the lowest
+  // address of a frame that looks like this (all 64-bit words):
+  //
+  // sp ->  saved r0
+  //        garbage
+  //        return address
+  // cfa -> 
+  //
+  // r0 has been saved on the stack.
+  // r1 has been saved in r2.
+  // r2 and r3 are not recoverable.
+  // r4 is not recoverable, even though it is a callee-saves register.
+  //    Some earlier frame's unwinder must have failed to recover it.
+
+  u_int64_t stack_top = 0x83254944b20d5512ULL;
+
+  // Saved r0.
+  EXPECT_CALL(memory,
+              GetMemoryAtAddress(stack_top, A<u_int64_t *>()))
+      .WillRepeatedly(DoAll(SetArgumentPointee<1>(0xdc1975eba8602302ULL),
+                            Return(true)));
+  // Saved return address.
+  EXPECT_CALL(memory,
+              GetMemoryAtAddress(stack_top + 16, A<u_int64_t *>()))
+      .WillRepeatedly(DoAll(SetArgumentPointee<1>(0xba5ad6d9acce28deULL),
+                            Return(true)));
+
+  call_frame_info.SetCFARule("sp 24 +");
+  call_frame_info.SetRARule(".cfa 8 - ^");
+  call_frame_info.SetRegisterRule("r0", ".cfa 24 - ^");
+  call_frame_info.SetRegisterRule("r1", "r2");
+
+  callee_context.r0 = 0x94e030ca79edd119ULL;
+  callee_context.r1 = 0x937b4d7e95ce52d9ULL;
+  callee_context.r2 = 0x5fe0027416b8b62aULL; // caller's r1
+  // callee_context.r3 is not valid in callee.
+  // callee_context.r4 is not valid in callee.
+  callee_context.sp = stack_top;
+  callee_context.pc = 0x25b21b224311d280ULL;
+  int callee_validity = R0_VALID | R1_VALID | R2_VALID | SP_VALID | PC_VALID;
+
+  memset(&caller_context, 0, sizeof(caller_context));
+
+  int caller_validity;
+  EXPECT_TRUE(walker.FindCallerRegisters(memory, call_frame_info,
+                                         callee_context, callee_validity,
+                                         &caller_context, &caller_validity));
+  EXPECT_EQ(R0_VALID | R1_VALID | SP_VALID | PC_VALID, caller_validity);
+  EXPECT_EQ(0xdc1975eba8602302ULL, caller_context.r0);
+  EXPECT_EQ(0x5fe0027416b8b62aULL, caller_context.r1);
+  EXPECT_EQ(stack_top + 24,        caller_context.sp);
+  EXPECT_EQ(0xba5ad6d9acce28deULL, caller_context.pc);
+}
diff --git a/src/processor/stackwalker_x86.cc b/src/processor/stackwalker_x86.cc
index 0f4b8463..81609033 100644
--- a/src/processor/stackwalker_x86.cc
+++ b/src/processor/stackwalker_x86.cc
@@ -45,10 +45,38 @@
 #include "processor/scoped_ptr.h"
 #include "processor/stackwalker_x86.h"
 #include "processor/windows_frame_info.h"
+#include "processor/cfi_frame_info.h"
 
 namespace google_breakpad {
 
 
+const StackwalkerX86::CFIWalker::RegisterSet
+StackwalkerX86::cfi_register_map_[] = {
+  // It may seem like $eip and $esp are callee-saves, because (with Unix or
+  // cdecl calling conventions) the callee is responsible for having them
+  // restored upon return. But the callee_saves flags here really means
+  // that the walker should assume they're unchanged if the CFI doesn't
+  // mention them, which is clearly wrong for $eip and $esp.
+  { "$eip", ".ra",  false,
+    StackFrameX86::CONTEXT_VALID_EIP, &MDRawContextX86::eip },
+  { "$esp", ".cfa", false,
+    StackFrameX86::CONTEXT_VALID_ESP, &MDRawContextX86::esp },
+  { "$ebp", NULL,   true,
+    StackFrameX86::CONTEXT_VALID_EBP, &MDRawContextX86::ebp },
+  { "$eax", NULL,   false,
+    StackFrameX86::CONTEXT_VALID_EAX, &MDRawContextX86::eax },
+  { "$ebx", NULL,   true,
+    StackFrameX86::CONTEXT_VALID_EBX, &MDRawContextX86::ebx },
+  { "$ecx", NULL,   false,
+    StackFrameX86::CONTEXT_VALID_ECX, &MDRawContextX86::ecx },
+  { "$edx", NULL,   false,
+    StackFrameX86::CONTEXT_VALID_EDX, &MDRawContextX86::edx },
+  { "$esi", NULL,   true,
+    StackFrameX86::CONTEXT_VALID_ESI, &MDRawContextX86::esi },
+  { "$edi", NULL,   true,
+    StackFrameX86::CONTEXT_VALID_EDI, &MDRawContextX86::edi },
+};
+
 StackwalkerX86::StackwalkerX86(const SystemInfo *system_info,
                                const MDRawContextX86 *context,
                                MemoryRegion *memory,
@@ -56,7 +84,9 @@ StackwalkerX86::StackwalkerX86(const SystemInfo *system_info,
                                SymbolSupplier *supplier,
                                SourceLineResolverInterface *resolver)
     : Stackwalker(system_info, memory, modules, supplier, resolver),
-      context_(context) {
+      context_(context),
+      cfi_walker_(cfi_register_map_,
+                  (sizeof(cfi_register_map_) / sizeof(cfi_register_map_[0]))) {
   if (memory_->GetBase() + memory_->GetSize() - 1 > 0xffffffff) {
     // The x86 is a 32-bit CPU, the limits of the supplied stack are invalid.
     // Mark memory_ = NULL, which will cause stackwalking to fail.
@@ -71,6 +101,9 @@ StackFrameX86::~StackFrameX86() {
   if (windows_frame_info)
     delete windows_frame_info;
   windows_frame_info = NULL;
+  if (cfi_frame_info)
+    delete cfi_frame_info;
+  cfi_frame_info = NULL;
 }
 
 StackFrame *StackwalkerX86::GetContextFrame() {
@@ -388,6 +421,31 @@ StackFrameX86 *StackwalkerX86::GetCallerByWindowsFrameInfo(
   return frame;
 }
 
+StackFrameX86 *StackwalkerX86::GetCallerByCFIFrameInfo(
+    const vector<StackFrame*> &frames,
+    CFIFrameInfo *cfi_frame_info) {
+  StackFrameX86 *last_frame = static_cast<StackFrameX86*>(frames.back());
+  last_frame->cfi_frame_info = cfi_frame_info;
+
+  scoped_ptr<StackFrameX86> frame(new StackFrameX86());
+  if (!cfi_walker_
+      .FindCallerRegisters(*memory_, *cfi_frame_info,
+                           last_frame->context, last_frame->context_validity,
+                           &frame->context, &frame->context_validity))
+    return NULL;
+  
+  // Make sure we recovered all the essentials.
+  static const int essentials = (StackFrameX86::CONTEXT_VALID_EIP
+                                 | StackFrameX86::CONTEXT_VALID_ESP
+                                 | StackFrameX86::CONTEXT_VALID_EBP);
+  if ((frame->context_validity & essentials) != essentials)
+    return NULL;
+
+  frame->trust = StackFrameX86::FRAME_TRUST_CFI;
+
+  return frame.release();
+}
+
 StackFrameX86 *StackwalkerX86::GetCallerByEBPAtBase(
     const vector<StackFrame *> &frames) {
   StackFrameX86::FrameTrust trust;
@@ -471,13 +529,20 @@ StackFrame *StackwalkerX86::GetCallerFrame(const CallStack *stack) {
   StackFrameX86 *last_frame = static_cast<StackFrameX86 *>(frames.back());
   scoped_ptr<StackFrameX86> new_frame;
 
-  // If we have Windows stack walking information, use that.
+  // If the resolver has Windows stack walking information, use that.
   WindowsFrameInfo *windows_frame_info
       = resolver_->FindWindowsFrameInfo(last_frame);
   if (windows_frame_info)
     new_frame.reset(GetCallerByWindowsFrameInfo(frames, windows_frame_info));
 
-  // Otherwise, hope that we're using a traditional frame structure.
+  // If the resolver has DWARF CFI information, use that.
+  if (!new_frame.get()) {
+    CFIFrameInfo *cfi_frame_info = resolver_->FindCFIFrameInfo(last_frame);
+    if (cfi_frame_info)
+      new_frame.reset(GetCallerByCFIFrameInfo(frames, cfi_frame_info));
+  }
+
+  // Otherwise, hope that the program was using a traditional frame structure.
   if (!new_frame.get())
     new_frame.reset(GetCallerByEBPAtBase(frames));
 
diff --git a/src/processor/stackwalker_x86.h b/src/processor/stackwalker_x86.h
index 02bda4c3..66b5839c 100644
--- a/src/processor/stackwalker_x86.h
+++ b/src/processor/stackwalker_x86.h
@@ -45,6 +45,7 @@
 #include "google_breakpad/common/minidump_format.h"
 #include "google_breakpad/processor/stackwalker.h"
 #include "google_breakpad/processor/stack_frame_cpu.h"
+#include "src/processor/cfi_frame_info.h"
 
 namespace google_breakpad {
 
@@ -65,6 +66,9 @@ class StackwalkerX86 : public Stackwalker {
                  SourceLineResolverInterface *resolver);
 
  private:
+  // A STACK CFI-driven frame walker for the X86.
+  typedef SimpleCFIWalker<u_int32_t, MDRawContextX86> CFIWalker;
+
   // Implementation of Stackwalker, using x86 context (%ebp, %esp, %eip) and
   // stack conventions (saved %ebp at [%ebp], saved %eip at 4[%ebp], or
   // alternate conventions as guided by any WindowsFrameInfo available for the
@@ -79,6 +83,12 @@ class StackwalkerX86 : public Stackwalker {
       const vector<StackFrame*> &frames,
       WindowsFrameInfo *windows_frame_info);
 
+  // Use cfi_frame_info (derived from STACK CFI records) to construct
+  // the frame that called frames.back(). The caller takes ownership
+  // of the returned frame. Return NULL on failure.
+  StackFrameX86 *GetCallerByCFIFrameInfo(const vector<StackFrame*> &frames,
+                                         CFIFrameInfo *cfi_frame_info);
+
   // Assuming a traditional frame layout --- where the caller's %ebp
   // has been pushed just after the return address and the callee's
   // %ebp points to the saved %ebp --- construct the frame that called
@@ -102,6 +112,12 @@ class StackwalkerX86 : public Stackwalker {
   // Stores the CPU context corresponding to the innermost stack frame to
   // be returned by GetContextFrame.
   const MDRawContextX86 *context_;
+
+  // Our register map, for cfi_walker_.
+  static const CFIWalker::RegisterSet cfi_register_map_[];
+
+  // Our CFI frame walker.
+  const CFIWalker cfi_walker_;
 };
 
 
diff --git a/src/processor/stackwalker_x86_unittest.cc b/src/processor/stackwalker_x86_unittest.cc
index 5381c482..464b94ed 100644
--- a/src/processor/stackwalker_x86_unittest.cc
+++ b/src/processor/stackwalker_x86_unittest.cc
@@ -237,7 +237,7 @@ TEST_F(GetCallerFrame, TraditionalScan) {
   EXPECT_EQ(StackFrameX86::FRAME_TRUST_SCAN, frame1->trust);
   // I'd argue that CONTEXT_VALID_EBP shouldn't be here, since the
   // walker does not actually fetch the EBP after a scan (forcing the
-  // next frame to be scanned as well). But we'll grandfather the existing
+  // next frame to be scanned as well). But let's grandfather the existing
   // behavior in for now.
   ASSERT_EQ((StackFrameX86::CONTEXT_VALID_EIP
              | StackFrameX86::CONTEXT_VALID_ESP
@@ -325,8 +325,8 @@ TEST_F(GetCallerFrame, WindowsFrameData) {
 TEST_F(GetCallerFrame, WindowsFrameDataParameterSize) {
   SetModuleSymbols(&module1, "FUNC 1000 100 c module1::wheedle\n");
   SetModuleSymbols(&module2,
-                   // Note bogus parameter size in FUNC record; we should
-                   // prefer the STACK WIN record, and see '4' below.
+                   // Note bogus parameter size in FUNC record; the stack walker
+                   // should prefer the STACK WIN record, and see '4' below.
                    "FUNC aa85 176 beef module2::whine\n"
                    "STACK WIN 4 aa85 176 0 0 4 10 4 0 1"
                    " $T2 $esp .cbLocals + .cbSavedRegs + ="
@@ -429,8 +429,8 @@ TEST_F(GetCallerFrame, WindowsFrameDataParameterSize) {
 
 // Use Windows frame data (a "STACK WIN 4" record, from a
 // FrameTypeFrameData DIA record) to walk a stack frame, where the
-// expression fails to yield both an $eip and an $ebp value, and we
-// must scan.
+// expression fails to yield both an $eip and an $ebp value, and the stack
+// walker must scan.
 TEST_F(GetCallerFrame, WindowsFrameDataScan) {
   SetModuleSymbols(&module1,
                    "STACK WIN 4 c8c 111 0 0 4 10 4 0 1 bad program string\n");
@@ -470,10 +470,10 @@ TEST_F(GetCallerFrame, WindowsFrameDataScan) {
 
   StackFrameX86 *frame1 = static_cast<StackFrameX86 *>(frames->at(1));
   EXPECT_EQ(StackFrameX86::FRAME_TRUST_SCAN, frame1->trust);
-  // I'd argue that CONTEXT_VALID_EBP shouldn't be here, since the
-  // walker does not actually fetch the EBP after a scan (forcing the
-  // next frame to be scanned as well). But we'll grandfather the existing
-  // behavior in for now.
+  // I'd argue that CONTEXT_VALID_EBP shouldn't be here, since the walker
+  // does not actually fetch the EBP after a scan (forcing the next frame
+  // to be scanned as well). But let's grandfather the existing behavior in
+  // for now.
   ASSERT_EQ((StackFrameX86::CONTEXT_VALID_EIP
              | StackFrameX86::CONTEXT_VALID_ESP
              | StackFrameX86::CONTEXT_VALID_EBP),
@@ -486,8 +486,8 @@ TEST_F(GetCallerFrame, WindowsFrameDataScan) {
 
 // Use Windows frame data (a "STACK WIN 4" record, from a
 // FrameTypeFrameData DIA record) to walk a stack frame, where the
-// expression yields an $eip that falls outside of any module, and we
-// must scan.
+// expression yields an $eip that falls outside of any module, and the
+// stack walker must scan.
 TEST_F(GetCallerFrame, WindowsFrameDataBadEIPScan) {
   SetModuleSymbols(&module1,
                    "STACK WIN 4 6e6 e7 0 0 0 8 4 0 1"
@@ -500,8 +500,8 @@ TEST_F(GetCallerFrame, WindowsFrameDataBadEIPScan) {
   stack_section.start() = 0x80000000;
 
   // In this stack, the context's %ebp is pointing at the wrong place, so
-  // we need to scan to find the return address, and then scan again to find
-  // the caller's saved %ebp.
+  // the stack walker needs to scan to find the return address, and then
+  // scan again to find the caller's saved %ebp.
   Label frame0_ebp, frame1_ebp, frame1_esp;
   stack_section
     // frame 0
@@ -510,7 +510,7 @@ TEST_F(GetCallerFrame, WindowsFrameDataBadEIPScan) {
                                 // at *** below
     // The STACK WIN record says that the following two values are
     // frame 1's saved %ebp and return address, but the %ebp is wrong;
-    // they're garbage. We will scan for the right values.
+    // they're garbage. The stack walker will scan for the right values.
     .D32(0x3d937b2b)            // alleged to be frame 1's saved %ebp
     .D32(0x17847f5b)            // alleged to be frame 1's return address
     .D32(frame1_ebp)            // frame 1's real saved %ebp; scan will find
@@ -520,7 +520,7 @@ TEST_F(GetCallerFrame, WindowsFrameDataBadEIPScan) {
     .D32(0x5000d000)            // frame 1's real saved %eip; scan will find
     // Frame 1, in module2::function. The STACK WIN record describes
     // this as the oldest frame, without referring to its contents, so
-    // we don't need to 
+    // we needn't to provide any actual data here.
     .Mark(&frame1_esp)
     .Mark(&frame1_ebp)          // frame 1 %ebp points here
     // A dummy value for frame 1's %ebp to point at. The scan recognizes the
@@ -551,7 +551,7 @@ TEST_F(GetCallerFrame, WindowsFrameDataBadEIPScan) {
   EXPECT_EQ(StackFrameX86::FRAME_TRUST_CFI_SCAN, frame1->trust);
   // I'd argue that CONTEXT_VALID_EBP shouldn't be here, since the
   // walker does not actually fetch the EBP after a scan (forcing the
-  // next frame to be scanned as well). But we'll grandfather the existing
+  // next frame to be scanned as well). But let's grandfather the existing
   // behavior in for now.
   ASSERT_EQ((StackFrameX86::CONTEXT_VALID_EIP
              | StackFrameX86::CONTEXT_VALID_ESP
@@ -568,8 +568,8 @@ TEST_F(GetCallerFrame, WindowsFrameDataBadEIPScan) {
 // does not modify %ebp from the value it had in the caller.
 TEST_F(GetCallerFrame, WindowsFPOUnchangedEBP) {
   SetModuleSymbols(&module1,
-                   // Note bogus parameter size in FUNC record; we should
-                   // prefer the STACK WIN record, and see '8' below.
+                   // Note bogus parameter size in FUNC record; the walker
+                   // should prefer the STACK WIN record, and see the '8' below.
                    "FUNC e8a8 100 feeb module1::discombobulated\n"
                    "STACK WIN 0 e8a8 100 0 0 8 4 10 0 0 0\n");
   Label frame0_esp;
@@ -637,8 +637,8 @@ TEST_F(GetCallerFrame, WindowsFPOUnchangedEBP) {
 // caller in the standard place in the saved register area.
 TEST_F(GetCallerFrame, WindowsFPOUsedEBP) {
   SetModuleSymbols(&module1,
-                   // Note bogus parameter size in FUNC record; we should
-                   // prefer the STACK WIN record, and see '8' below.
+                   // Note bogus parameter size in FUNC record; the walker
+                   // should prefer the STACK WIN record, and see the '8' below.
                    "FUNC 9aa8 e6 abbe module1::RaisedByTheAliens\n"
                    "STACK WIN 0 9aa8 e6 a 0 10 8 4 0 0 1\n");
   Label frame0_esp;
@@ -702,3 +702,192 @@ TEST_F(GetCallerFrame, WindowsFPOUsedEBP) {
   EXPECT_EQ("", frame1->function_name);
   EXPECT_EQ(NULL, frame1->windows_frame_info);
 }
+
+struct CFIFixture: public StackwalkerX86Fixture {
+  CFIFixture() {
+    // Provide a bunch of STACK CFI records; individual tests walk to the
+    // caller from every point in this series, expecting to find the same
+    // set of register values.
+    SetModuleSymbols(&module1,
+                     // The youngest frame's function.
+                     "FUNC 4000 1000 10 enchiridion\n"
+                     // Initially, just a return address.
+                     "STACK CFI INIT 4000 100 .cfa: $esp 4 + .ra: .cfa 4 - ^\n"
+                     // Push %ebx.
+                     "STACK CFI 4001 .cfa: $esp 8 + $ebx: .cfa 8 - ^\n"
+                     // Move %esi into %ebx.  Weird, but permitted.
+                     "STACK CFI 4002 $esi: $ebx\n"
+                     // Allocate frame space, and save %edi.
+                     "STACK CFI 4003 .cfa: $esp 20 + $edi: .cfa 16 - ^\n"
+                     // Put the return address in %edi.
+                     "STACK CFI 4005 .ra: $edi\n"
+                     // Save %ebp, and use it as a frame pointer.
+                     "STACK CFI 4006 .cfa: $ebp 8 + $ebp: .cfa 12 - ^\n"
+
+                     // The calling function.
+                     "FUNC 5000 1000 10 epictetus\n"
+                     // Mark it as end of stack.
+                     "STACK CFI INIT 5000 1000 .cfa: $esp .ra 0\n");
+
+    // Provide some distinctive values for the caller's registers.
+    expected.esp = 0x80000000;
+    expected.eip = 0x40005510;
+    expected.ebp = 0xc0d4aab9;
+    expected.ebx = 0x60f20ce6;
+    expected.esi = 0x53d1379d;
+    expected.edi = 0xafbae234;
+
+    // By default, registers are unchanged.
+    raw_context = expected;
+  }
+
+  // Walk the stack, using stack_section as the contents of the stack
+  // and raw_context as the current register values. (Set
+  // raw_context.esp to the stack's starting address.) Expect two
+  // stack frames; in the older frame, expect the callee-saves
+  // registers to have values matching those in 'expected'.
+  void CheckWalk() {
+    RegionFromSection();
+    raw_context.esp = stack_section.start().Value();
+
+    StackwalkerX86 walker(&system_info, &raw_context, &stack_region, &modules,
+                          &supplier, &resolver);
+    ASSERT_TRUE(walker.Walk(&call_stack));
+    frames = call_stack.frames();
+    ASSERT_EQ(2U, frames->size());
+
+    StackFrameX86 *frame0 = static_cast<StackFrameX86 *>(frames->at(0));
+    EXPECT_EQ(StackFrameX86::FRAME_TRUST_CONTEXT, frame0->trust);
+    ASSERT_EQ(StackFrameX86::CONTEXT_VALID_ALL, frame0->context_validity);
+    EXPECT_EQ("enchiridion", frame0->function_name);
+    EXPECT_EQ(0x40004000U, frame0->function_base);
+    ASSERT_TRUE(frame0->windows_frame_info != NULL);
+    ASSERT_EQ(WindowsFrameInfo::VALID_PARAMETER_SIZE,
+              frame0->windows_frame_info->valid);
+    ASSERT_TRUE(frame0->cfi_frame_info != NULL);
+
+    StackFrameX86 *frame1 = static_cast<StackFrameX86 *>(frames->at(1));
+    EXPECT_EQ(StackFrameX86::FRAME_TRUST_CFI, frame1->trust);
+    ASSERT_EQ((StackFrameX86::CONTEXT_VALID_EIP |
+               StackFrameX86::CONTEXT_VALID_ESP |
+               StackFrameX86::CONTEXT_VALID_EBP |
+               StackFrameX86::CONTEXT_VALID_EBX |
+               StackFrameX86::CONTEXT_VALID_ESI |
+               StackFrameX86::CONTEXT_VALID_EDI),
+              frame1->context_validity);
+    EXPECT_EQ(expected.eip, frame1->context.eip);
+    EXPECT_EQ(expected.esp, frame1->context.esp);
+    EXPECT_EQ(expected.ebp, frame1->context.ebp);
+    EXPECT_EQ(expected.ebx, frame1->context.ebx);
+    EXPECT_EQ(expected.esi, frame1->context.esi);
+    EXPECT_EQ(expected.edi, frame1->context.edi);
+    EXPECT_EQ("epictetus", frame1->function_name);
+  }
+
+  // The values the stack walker should find for the caller's registers.
+  MDRawContextX86 expected;
+};
+
+class CFI: public CFIFixture, public Test { };
+
+TEST_F(CFI, At4000) {
+  Label frame1_esp = expected.esp;
+  stack_section
+    .D32(0x40005510)            // return address
+    .Mark(&frame1_esp);         // This effectively sets stack_section.start().
+  raw_context.eip = 0x40004000;
+  CheckWalk();
+}
+
+TEST_F(CFI, At4001) {
+  Label frame1_esp = expected.esp;
+  stack_section
+    .D32(0x60f20ce6)            // saved %ebx
+    .D32(0x40005510)            // return address
+    .Mark(&frame1_esp);         // This effectively sets stack_section.start().
+  raw_context.eip = 0x40004001;
+  raw_context.ebx = 0x91aa9a8b; // callee's %ebx value
+  CheckWalk();
+}
+
+TEST_F(CFI, At4002) {
+  Label frame1_esp = expected.esp;
+  stack_section
+    .D32(0x60f20ce6)            // saved %ebx
+    .D32(0x40005510)            // return address
+    .Mark(&frame1_esp);         // This effectively sets stack_section.start().
+  raw_context.eip = 0x40004002;
+  raw_context.ebx = 0x53d1379d; // saved %esi
+  raw_context.esi = 0xa5c790ed; // callee's %esi value
+  CheckWalk();
+}
+
+TEST_F(CFI, At4003) {
+  Label frame1_esp = expected.esp;
+  stack_section
+    .D32(0x56ec3db7)            // garbage
+    .D32(0xafbae234)            // saved %edi
+    .D32(0x53d67131)            // garbage
+    .D32(0x60f20ce6)            // saved %ebx
+    .D32(0x40005510)            // return address
+    .Mark(&frame1_esp);         // This effectively sets stack_section.start().
+  raw_context.eip = 0x40004003;
+  raw_context.ebx = 0x53d1379d; // saved %esi
+  raw_context.esi = 0xa97f229d; // callee's %esi
+  raw_context.edi = 0xb05cc997; // callee's %edi
+  CheckWalk();
+}
+
+// The results here should be the same as those at module offset
+// 0x4003.
+TEST_F(CFI, At4004) {
+  Label frame1_esp = expected.esp;
+  stack_section
+    .D32(0xe29782c2)            // garbage
+    .D32(0xafbae234)            // saved %edi
+    .D32(0x5ba29ce9)            // garbage
+    .D32(0x60f20ce6)            // saved %ebx
+    .D32(0x40005510)            // return address
+    .Mark(&frame1_esp);         // This effectively sets stack_section.start().
+  raw_context.eip = 0x40004004;
+  raw_context.ebx = 0x53d1379d; // saved %esi
+  raw_context.esi = 0x0fb7dc4e; // callee's %esi
+  raw_context.edi = 0x993b4280; // callee's %edi
+  CheckWalk();
+}
+
+TEST_F(CFI, At4005) {
+  Label frame1_esp = expected.esp;
+  stack_section
+    .D32(0xe29782c2)            // garbage
+    .D32(0xafbae234)            // saved %edi
+    .D32(0x5ba29ce9)            // garbage
+    .D32(0x60f20ce6)            // saved %ebx
+    .D32(0x8036cc02)            // garbage
+    .Mark(&frame1_esp);         // This effectively sets stack_section.start().
+  raw_context.eip = 0x40004005;
+  raw_context.ebx = 0x53d1379d; // saved %esi
+  raw_context.esi = 0x0fb7dc4e; // callee's %esi
+  raw_context.edi = 0x40005510; // return address
+  CheckWalk();
+}
+
+TEST_F(CFI, At4006) {
+  Label frame0_ebp;
+  Label frame1_esp = expected.esp;
+  stack_section
+    .D32(0xdcdd25cd)            // garbage
+    .D32(0xafbae234)            // saved %edi
+    .D32(0xc0d4aab9)            // saved %ebp
+    .Mark(&frame0_ebp)          // frame pointer points here
+    .D32(0x60f20ce6)            // saved %ebx
+    .D32(0x8036cc02)            // garbage
+    .Mark(&frame1_esp);         // This effectively sets stack_section.start().
+  raw_context.eip = 0x40004006;
+  raw_context.ebp = frame0_ebp.Value();
+  raw_context.ebx = 0x53d1379d; // saved %esi
+  raw_context.esi = 0x743833c9; // callee's %esi
+  raw_context.edi = 0x40005510; // return address
+  CheckWalk();
+}
+
diff --git a/src/processor/testdata/module1.out b/src/processor/testdata/module1.out
index 3fb1f181..d4a8208a 100644
--- a/src/processor/testdata/module1.out
+++ b/src/processor/testdata/module1.out
@@ -20,3 +20,9 @@ STACK WIN 4 1000 c 1 0 0 0 0 0 1 $eip 4 + ^ = $esp $ebp 8 + = $ebp $ebp ^ =
 STACK WIN 4 1100 8 1 0 0 0 0 0 1 $eip 4 + ^ = $esp $ebp 8 + = $ebp $ebp ^ =
 STACK WIN 4 1100 100 1 0 0 0 0 0 1 $eip 4 + ^ = $esp $ebp 8 + = $ebp $ebp ^ =
 STACK WIN 4 1300 100 1 0 0 0 0 0 1 $eip 4 + ^ = $esp $ebp 8 + = $ebp $ebp ^ =
+STACK CFI INIT 3d40 af .cfa: $esp 4 + .ra: .cfa 4 - ^
+STACK CFI 3d41 .cfa: $esp 8 + 
+STACK CFI 3d43 .cfa: $ebp 8 + $ebp: .cfa 8 - ^
+STACK CFI 3d54 $ebx: .cfa 20 - ^
+STACK CFI 3d5a $esi: .cfa 16 - ^
+STACK CFI 3d84 $edi: .cfa 12 - ^
diff --git a/src/processor/testdata/module2.out b/src/processor/testdata/module2.out
index 265401c1..845212cc 100644
--- a/src/processor/testdata/module2.out
+++ b/src/processor/testdata/module2.out
@@ -15,3 +15,9 @@ FUNC 2170 14 4 Function2_2
 PUBLIC 21a0 0 Public2_2
 STACK WIN 4 2000 c 1 0 0 0 0 0 1 $eip 4 + ^ = $esp $ebp 8 + = $ebp $ebp ^ =
 STACK WIN 4 2170 14 1 0 0 0 0 0 1 $eip 4 + ^ = $esp $ebp 8 + = $ebp $ebp ^ =
+STACK CFI INIT 3df0 af .cfa: $esp 4 + .ra: .cfa 4 - ^
+STACK CFI 3df1 .cfa: $esp 8 +
+STACK CFI 3df3 .cfa: $ebp 8 + $ebp: .cfa 8 - ^
+STACK CFI 3e04 $ebx: .cfa 20 - ^
+STACK CFI 3e0a $esi: .cfa 16 - ^
+STACK CFI 3e34 $edi: .cfa 12 - ^