Add stack-scanning fallback to Stackwalker{AMD64,ARM}.

R=jimb at http://breakpad.appspot.com/206001/show

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

7 files changed, 361 insertions, 20 deletions

diff --git a/src/processor/stackwalker_amd64.cc b/src/processor/stackwalker_amd64.cc
index ce31243f..c142e2a3 100644
--- a/src/processor/stackwalker_amd64.cc
+++ b/src/processor/stackwalker_amd64.cc
@@ -142,6 +142,36 @@ StackFrameAMD64 *StackwalkerAMD64::GetCallerByCFIFrameInfo(
   return frame.release();
 }
 
+StackFrameAMD64 *StackwalkerAMD64::GetCallerByStackScan(
+    const vector<StackFrame *> &frames) {
+  StackFrameAMD64 *last_frame = static_cast<StackFrameAMD64 *>(frames.back());
+  u_int64_t last_rsp = last_frame->context.rsp;
+  u_int64_t caller_rsp, caller_rip;
+  
+  if (!ScanForReturnAddress(last_rsp, &caller_rsp, &caller_rip)) {
+    // No plausible return address was found.
+    return NULL;
+  }
+
+  // ScanForReturnAddress found a reasonable return address. Advance
+  // %rsp to the location above the one where the return address was
+  // found.
+  caller_rsp += 8;
+
+  // Create a new stack frame (ownership will be transferred to the caller)
+  // and fill it in.
+  StackFrameAMD64 *frame = new StackFrameAMD64();
+
+  frame->trust = StackFrame::FRAME_TRUST_SCAN;
+  frame->context = last_frame->context;
+  frame->context.rip = caller_rip;
+  frame->context.rsp = caller_rsp;
+  frame->context_validity = StackFrameAMD64::CONTEXT_VALID_RIP |
+                            StackFrameAMD64::CONTEXT_VALID_RSP;
+
+  return frame;
+}
+
 StackFrame* StackwalkerAMD64::GetCallerFrame(const CallStack *stack) {
   if (!memory_ || !stack) {
     BPLOG(ERROR) << "Can't get caller frame without memory or stack";
@@ -158,6 +188,12 @@ StackFrame* StackwalkerAMD64::GetCallerFrame(const CallStack *stack) {
   if (cfi_frame_info.get())
     new_frame.reset(GetCallerByCFIFrameInfo(frames, cfi_frame_info.get()));
 
+  // If CFI failed, or there wasn't CFI available, fall back
+  // to stack scanning.
+  if (!new_frame.get()) {
+    new_frame.reset(GetCallerByStackScan(frames));
+  }
+
   // If nothing worked, tell the caller.
   if (!new_frame.get())
     return NULL;
@@ -185,5 +221,4 @@ StackFrame* StackwalkerAMD64::GetCallerFrame(const CallStack *stack) {
   return new_frame.release();
 }
 
-
 }  // namespace google_breakpad
diff --git a/src/processor/stackwalker_amd64.h b/src/processor/stackwalker_amd64.h
index 9e61fcf5..cde95208 100644
--- a/src/processor/stackwalker_amd64.h
+++ b/src/processor/stackwalker_amd64.h
@@ -77,6 +77,10 @@ class StackwalkerAMD64 : public Stackwalker {
   StackFrameAMD64 *GetCallerByCFIFrameInfo(const vector<StackFrame *> &frames,
                                            CFIFrameInfo *cfi_frame_info);
 
+  // Scan the stack for plausible return addresses. The caller takes ownership
+  // of the returned frame. Return NULL on failure. 
+  StackFrameAMD64 *GetCallerByStackScan(const vector<StackFrame *> &frames);
+
   // Stores the CPU context corresponding to the innermost stack frame to
   // be returned by GetContextFrame.
   const MDRawContextAMD64 *context_;
diff --git a/src/processor/stackwalker_amd64_unittest.cc b/src/processor/stackwalker_amd64_unittest.cc
index 9438ea0d..6fd3bea4 100644
--- a/src/processor/stackwalker_amd64_unittest.cc
+++ b/src/processor/stackwalker_amd64_unittest.cc
@@ -146,6 +146,129 @@ TEST_F(GetContextFrame, Simple) {
   EXPECT_TRUE(memcmp(&raw_context, &frame->context, sizeof(raw_context)) == 0);
 }
 
+class GetCallerFrame: public StackwalkerAMD64Fixture, public Test { };
+
+TEST_F(GetCallerFrame, ScanWithoutSymbols) {
+  // When the stack walker resorts to scanning the stack,
+  // only addresses located within loaded modules are
+  // considered valid return addresses.
+  // Force scanning through three frames to ensure that the
+  // stack pointer is set properly in scan-recovered frames.
+  stack_section.start() = 0x8000000080000000ULL;
+  u_int64_t return_address1 = 0x50000000b0000100ULL;
+  u_int64_t return_address2 = 0x50000000b0000900ULL;
+  Label frame1_sp, frame2_sp;
+  stack_section
+    // frame 0
+    .Append(16, 0)                      // space
+
+    .D64(0x40000000b0000000ULL)         // junk that's not
+    .D64(0x50000000d0000000ULL)         // a return address
+
+    .D64(return_address1)               // actual return address
+    // frame 1
+    .Mark(&frame1_sp)
+    .Append(16, 0)                      // space
+
+    .D64(0x40000000b0000000ULL)         // more junk
+    .D64(0x50000000d0000000ULL)
+
+    .D64(return_address2)               // actual return address
+    // frame 2
+    .Mark(&frame2_sp)
+    .Append(32, 0);                     // end of stack
+
+  RegionFromSection();
+    
+  raw_context.rip = 0x40000000c0000200ULL;
+  raw_context.rsp = stack_section.start().Value();
+
+  StackwalkerAMD64 walker(&system_info, &raw_context, &stack_region, &modules,
+                          &supplier, &resolver);
+  ASSERT_TRUE(walker.Walk(&call_stack));
+  frames = call_stack.frames();
+  ASSERT_EQ(3U, frames->size());
+
+  StackFrameAMD64 *frame0 = static_cast<StackFrameAMD64 *>(frames->at(0));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_CONTEXT, frame0->trust);
+  ASSERT_EQ(StackFrameAMD64::CONTEXT_VALID_ALL, frame0->context_validity);
+  EXPECT_TRUE(memcmp(&raw_context, &frame0->context, sizeof(raw_context)) == 0);
+
+  StackFrameAMD64 *frame1 = static_cast<StackFrameAMD64 *>(frames->at(1));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_SCAN, frame1->trust);
+  ASSERT_EQ((StackFrameAMD64::CONTEXT_VALID_RIP |
+             StackFrameAMD64::CONTEXT_VALID_RSP),
+            frame1->context_validity);
+  EXPECT_EQ(return_address1, frame1->context.rip);
+  EXPECT_EQ(frame1_sp.Value(), frame1->context.rsp);
+
+  StackFrameAMD64 *frame2 = static_cast<StackFrameAMD64 *>(frames->at(2));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_SCAN, frame2->trust);
+  ASSERT_EQ((StackFrameAMD64::CONTEXT_VALID_RIP |
+             StackFrameAMD64::CONTEXT_VALID_RSP),
+            frame2->context_validity);
+  EXPECT_EQ(return_address2, frame2->context.rip);
+  EXPECT_EQ(frame2_sp.Value(), frame2->context.rsp);
+}
+
+TEST_F(GetCallerFrame, ScanWithFunctionSymbols) {
+  // During stack scanning, if a potential return address
+  // is located within a loaded module that has symbols,
+  // it is only considered a valid return address if it
+  // lies within a function's bounds.
+  stack_section.start() = 0x8000000080000000ULL;
+  u_int64_t return_address = 0x50000000b0000110ULL;
+  Label frame1_sp;
+
+  stack_section
+    // frame 0
+    .Append(16, 0)                      // space
+
+    .D64(0x40000000b0000000ULL)         // junk that's not
+    .D64(0x50000000b0000000ULL)         // a return address
+
+    .D64(0x40000000c0001000ULL)         // a couple of plausible addresses
+    .D64(0x50000000b000aaaaULL)         // that are not within functions
+
+    .D64(return_address)                // actual return address
+    // frame 1
+    .Mark(&frame1_sp)
+    .Append(32, 0);                     // end of stack
+  RegionFromSection();
+    
+  raw_context.rip = 0x40000000c0000200ULL;
+  raw_context.rsp = stack_section.start().Value();
+
+  SetModuleSymbols(&module1,
+                   // The youngest frame's function.
+                   "FUNC 100 400 10 platypus\n");
+  SetModuleSymbols(&module2,
+                   // The calling frame's function.
+                   "FUNC 100 400 10 echidna\n");
+
+  StackwalkerAMD64 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());
+
+  StackFrameAMD64 *frame0 = static_cast<StackFrameAMD64 *>(frames->at(0));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_CONTEXT, frame0->trust);
+  ASSERT_EQ(StackFrameAMD64::CONTEXT_VALID_ALL, frame0->context_validity);
+  EXPECT_EQ("platypus", frame0->function_name);
+  EXPECT_EQ(0x40000000c0000100ULL, frame0->function_base);
+
+  StackFrameAMD64 *frame1 = static_cast<StackFrameAMD64 *>(frames->at(1));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_SCAN, frame1->trust);
+  ASSERT_EQ((StackFrameAMD64::CONTEXT_VALID_RIP |
+             StackFrameAMD64::CONTEXT_VALID_RSP),
+            frame1->context_validity);
+  EXPECT_EQ(return_address, frame1->context.rip);
+  EXPECT_EQ(frame1_sp.Value(), frame1->context.rsp);
+  EXPECT_EQ("echidna", frame1->function_name);
+  EXPECT_EQ(0x50000000b0000100ULL, frame1->function_base);
+}
+
 struct CFIFixture: public StackwalkerAMD64Fixture {
   CFIFixture() {
     // Provide a bunch of STACK CFI records; we'll walk to the caller
diff --git a/src/processor/stackwalker_arm.cc b/src/processor/stackwalker_arm.cc
index 03f92824..239f89d0 100644
--- a/src/processor/stackwalker_arm.cc
+++ b/src/processor/stackwalker_arm.cc
@@ -75,24 +75,11 @@ StackFrame* StackwalkerARM::GetContextFrame() {
   return frame;
 }
 
-
-StackFrame* StackwalkerARM::GetCallerFrame(const CallStack *stack) {
-  if (!memory_ || !stack) {
-    BPLOG(ERROR) << "Can't get caller frame without memory or stack";
-    return NULL;
-  }
-
-  const vector<StackFrame *> &frames = *stack->frames();
+StackFrameARM *StackwalkerARM::GetCallerByCFIFrameInfo(
+    const vector<StackFrame *> &frames,
+    CFIFrameInfo *cfi_frame_info) {
   StackFrameARM *last_frame = static_cast<StackFrameARM *>(frames.back());
 
-  // See if we have DWARF call frame information covering this address.
-  scoped_ptr<CFIFrameInfo> cfi_frame_info(resolver_
-                                          ->FindCFIFrameInfo(last_frame));
-  if (cfi_frame_info == NULL)
-    // Unfortunately, CFI is our only option on the ARM for now. If we
-    // add a second strategy, we should put each one in its own function.
-    return NULL;
-
   static const char *register_names[] = {
     "r0",  "r1",  "r2",  "r3",  "r4",  "r5",  "r6",  "r7",
     "r8",  "r9",  "r10", "r11", "r12", "sp",  "lr",  "pc",
@@ -158,6 +145,67 @@ StackFrame* StackwalkerARM::GetCallerFrame(const CallStack *stack) {
   if ((frame->context_validity & essentials) != essentials)
     return NULL;
 
+  frame->trust = StackFrame::FRAME_TRUST_CFI;
+  return frame.release();
+}
+
+StackFrameARM *StackwalkerARM::GetCallerByStackScan(
+    const vector<StackFrame *> &frames) {
+  StackFrameARM *last_frame = static_cast<StackFrameARM *>(frames.back());
+  u_int32_t last_sp = last_frame->context.iregs[MD_CONTEXT_ARM_REG_SP];
+  u_int32_t caller_sp, caller_pc;
+  
+  if (!ScanForReturnAddress(last_sp, &caller_sp, &caller_pc)) {
+    // No plausible return address was found.
+    return NULL;
+  }
+
+  // ScanForReturnAddress found a reasonable return address. Advance
+  // %sp to the location above the one where the return address was
+  // found.
+  caller_sp += 4;
+
+  // Create a new stack frame (ownership will be transferred to the caller)
+  // and fill it in.
+  StackFrameARM *frame = new StackFrameARM();
+
+  frame->trust = StackFrame::FRAME_TRUST_SCAN;
+  frame->context = last_frame->context;
+  frame->context.iregs[MD_CONTEXT_ARM_REG_PC] = caller_pc;
+  frame->context.iregs[MD_CONTEXT_ARM_REG_SP] = caller_sp;
+  frame->context_validity = StackFrameARM::CONTEXT_VALID_PC |
+                            StackFrameARM::CONTEXT_VALID_SP;
+
+  return frame;
+}
+
+StackFrame* StackwalkerARM::GetCallerFrame(const CallStack *stack) {
+  if (!memory_ || !stack) {
+    BPLOG(ERROR) << "Can't get caller frame without memory or stack";
+    return NULL;
+  }
+
+  const vector<StackFrame *> &frames = *stack->frames();
+  StackFrameARM *last_frame = static_cast<StackFrameARM *>(frames.back());
+  scoped_ptr<StackFrameARM> frame;
+
+  // See if there is DWARF call frame information covering this address.
+  scoped_ptr<CFIFrameInfo> cfi_frame_info(resolver_
+                                          ->FindCFIFrameInfo(last_frame));
+  if (cfi_frame_info.get())
+    frame.reset(GetCallerByCFIFrameInfo(frames, cfi_frame_info.get()));
+
+  // If CFI failed, or there wasn't CFI available, fall back
+  // to stack scanning.
+  if (!frame.get()) {
+    frame.reset(GetCallerByStackScan(frames));
+  }
+
+  // If nothing worked, tell the caller.
+  if (!frame.get())
+    return NULL;
+
+
   // An instruction address of zero marks the end of the stack.
   if (frame->context.iregs[MD_CONTEXT_ARM_REG_PC] == 0)
     return NULL;
@@ -179,7 +227,6 @@ StackFrame* StackwalkerARM::GetCallerFrame(const CallStack *stack) {
   // frame->context.iregs[MD_CONTEXT_ARM_REG_PC].
   frame->instruction = frame->context.iregs[MD_CONTEXT_ARM_REG_PC] - 1;
 
-  frame->trust = StackFrame::FRAME_TRUST_CFI;
   return frame.release();
 }
 
diff --git a/src/processor/stackwalker_arm.h b/src/processor/stackwalker_arm.h
index 3768cc2c..830579b2 100644
--- a/src/processor/stackwalker_arm.h
+++ b/src/processor/stackwalker_arm.h
@@ -69,10 +69,19 @@ class StackwalkerARM : public Stackwalker {
 
  private:
   // Implementation of Stackwalker, using arm context and stack conventions.
-  // TODO: currently stubbed out, needs CFI symbol dumper support
   virtual StackFrame* GetContextFrame();
   virtual StackFrame* GetCallerFrame(const CallStack *stack);
 
+  // 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.
+  StackFrameARM *GetCallerByCFIFrameInfo(const vector<StackFrame *> &frames,
+                                         CFIFrameInfo *cfi_frame_info);
+
+  // Scan the stack for plausible return addresses. The caller takes ownership
+  // of the returned frame. Return NULL on failure. 
+  StackFrameARM *GetCallerByStackScan(const vector<StackFrame *> &frames);
+
   // Stores the CPU context corresponding to the youngest stack frame, to
   // be returned by GetContextFrame.
   const MDRawContextARM *context_;
diff --git a/src/processor/stackwalker_arm_unittest.cc b/src/processor/stackwalker_arm_unittest.cc
index 22d17d46..ad7aeb31 100644
--- a/src/processor/stackwalker_arm_unittest.cc
+++ b/src/processor/stackwalker_arm_unittest.cc
@@ -144,6 +144,129 @@ TEST_F(GetContextFrame, Simple) {
   EXPECT_TRUE(memcmp(&raw_context, &frame->context, sizeof(raw_context)) == 0);
 }
 
+class GetCallerFrame: public StackwalkerARMFixture, public Test { };
+
+TEST_F(GetCallerFrame, ScanWithoutSymbols) {
+  // When the stack walker resorts to scanning the stack,
+  // only addresses located within loaded modules are
+  // considered valid return addresses.
+  // Force scanning through three frames to ensure that the
+  // stack pointer is set properly in scan-recovered frames.
+  stack_section.start() = 0x80000000;
+  u_int32_t return_address1 = 0x50000100;
+  u_int32_t return_address2 = 0x50000900;
+  Label frame1_sp, frame2_sp;
+  stack_section
+    // frame 0
+    .Append(16, 0)                      // space
+
+    .D32(0x40090000)                    // junk that's not
+    .D32(0x60000000)                    // a return address
+
+    .D32(return_address1)               // actual return address
+    // frame 1
+    .Mark(&frame1_sp)
+    .Append(16, 0)                      // space
+
+    .D32(0xF0000000)                    // more junk
+    .D32(0x0000000D)
+
+    .D32(return_address2)               // actual return address
+    // frame 2
+    .Mark(&frame2_sp)
+    .Append(32, 0);                     // end of stack
+  RegionFromSection();
+
+  raw_context.iregs[MD_CONTEXT_ARM_REG_PC] = 0x40005510;
+  raw_context.iregs[MD_CONTEXT_ARM_REG_SP] = stack_section.start().Value();
+
+  StackwalkerARM walker(&system_info, &raw_context, &stack_region, &modules,
+                        &supplier, &resolver);
+  ASSERT_TRUE(walker.Walk(&call_stack));
+  frames = call_stack.frames();
+  ASSERT_EQ(3U, frames->size());
+
+  StackFrameARM *frame0 = static_cast<StackFrameARM *>(frames->at(0));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_CONTEXT, frame0->trust);
+  ASSERT_EQ(StackFrameARM::CONTEXT_VALID_ALL, frame0->context_validity);
+  EXPECT_TRUE(memcmp(&raw_context, &frame0->context, sizeof(raw_context)) == 0);
+
+  StackFrameARM *frame1 = static_cast<StackFrameARM *>(frames->at(1));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_SCAN, frame1->trust);
+  ASSERT_EQ((StackFrameARM::CONTEXT_VALID_PC |
+             StackFrameARM::CONTEXT_VALID_SP),
+            frame1->context_validity);
+  EXPECT_EQ(return_address1, frame1->context.iregs[MD_CONTEXT_ARM_REG_PC]);
+  EXPECT_EQ(frame1_sp.Value(), frame1->context.iregs[MD_CONTEXT_ARM_REG_SP]);
+
+  StackFrameARM *frame2 = static_cast<StackFrameARM *>(frames->at(2));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_SCAN, frame2->trust);
+  ASSERT_EQ((StackFrameARM::CONTEXT_VALID_PC |
+             StackFrameARM::CONTEXT_VALID_SP),
+            frame2->context_validity);
+  EXPECT_EQ(return_address2, frame2->context.iregs[MD_CONTEXT_ARM_REG_PC]);
+  EXPECT_EQ(frame2_sp.Value(), frame2->context.iregs[MD_CONTEXT_ARM_REG_SP]);
+}
+
+TEST_F(GetCallerFrame, ScanWithFunctionSymbols) {
+  // During stack scanning, if a potential return address
+  // is located within a loaded module that has symbols,
+  // it is only considered a valid return address if it
+  // lies within a function's bounds.
+  stack_section.start() = 0x80000000;
+  u_int32_t return_address = 0x50000200;
+  Label frame1_sp;
+
+  stack_section
+    // frame 0
+    .Append(16, 0)                      // space
+
+    .D32(0x40090000)                    // junk that's not
+    .D32(0x60000000)                    // a return address
+
+    .D32(0x40001000)                    // a couple of plausible addresses
+    .D32(0x5000F000)                    // that are not within functions
+
+    .D32(return_address)                // actual return address
+    // frame 1
+    .Mark(&frame1_sp)
+    .Append(32, 0);                     // end of stack
+  RegionFromSection();
+
+  raw_context.iregs[MD_CONTEXT_ARM_REG_PC] = 0x40000200;
+  raw_context.iregs[MD_CONTEXT_ARM_REG_SP] = stack_section.start().Value();
+
+  SetModuleSymbols(&module1,
+                   // The youngest frame's function.
+                   "FUNC 100 400 10 monotreme\n");
+  SetModuleSymbols(&module2,
+                   // The calling frame's function.
+                   "FUNC 100 400 10 marsupial\n");
+
+  StackwalkerARM 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());
+
+  StackFrameARM *frame0 = static_cast<StackFrameARM *>(frames->at(0));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_CONTEXT, frame0->trust);
+  ASSERT_EQ(StackFrameARM::CONTEXT_VALID_ALL, frame0->context_validity);
+  EXPECT_TRUE(memcmp(&raw_context, &frame0->context, sizeof(raw_context)) == 0);
+  EXPECT_EQ("monotreme", frame0->function_name);
+  EXPECT_EQ(0x40000100, frame0->function_base);
+
+  StackFrameARM *frame1 = static_cast<StackFrameARM *>(frames->at(1));
+  EXPECT_EQ(StackFrame::FRAME_TRUST_SCAN, frame1->trust);
+  ASSERT_EQ((StackFrameARM::CONTEXT_VALID_PC |
+             StackFrameARM::CONTEXT_VALID_SP),
+            frame1->context_validity);
+  EXPECT_EQ(return_address, frame1->context.iregs[MD_CONTEXT_ARM_REG_PC]);
+  EXPECT_EQ(frame1_sp.Value(), frame1->context.iregs[MD_CONTEXT_ARM_REG_SP]);
+  EXPECT_EQ("marsupial", frame1->function_name);
+  EXPECT_EQ(0x50000100, frame1->function_base);
+}
+
 struct CFIFixture: public StackwalkerARMFixture {
   CFIFixture() {
     // Provide a bunch of STACK CFI records; we'll walk to the caller
diff --git a/src/processor/stackwalker_x86.cc b/src/processor/stackwalker_x86.cc
index bab484d9..9440f1d5 100644
--- a/src/processor/stackwalker_x86.cc
+++ b/src/processor/stackwalker_x86.cc
@@ -491,7 +491,7 @@ StackFrameX86 *StackwalkerX86::GetCallerByEBPAtBase(
     if (!ScanForReturnAddress(last_esp, &caller_esp, &caller_eip)) {
       // if we can't find an instruction pointer even with stack scanning,
       // give up.
-      return false;
+      return NULL;
     }
 
     // ScanForReturnAddress found a reasonable return address. Advance