Use register %ebp (instead of %esp) when calculating the value of

.raSearchStart in the cases where there are alignment operators in
the program string.

If alignment operators are found in the program string, the current
value of %ebp must be valid and it is the only reliable data point
that can be used for getting to the previous frame.  Previously, the
.raSearchStart calculation was based on %esp and when %esp is aligned
in the current frame (which is a lossy operation) the resulting
.raSearchStart cannot was incorrect.  There is code that is trying to
work around this problem (scanning of up to 3 words for a return
address) which is unreliable and it doesn't work in many cases (e.g.
when the alignment is on a 64-byte boundary).

This fix is already deployed in Google and it was measured to reduce
the number of wrong stack traces (for Windows crashes) by 45%. No
regressions have been found so far.

Here is an example of an issue that was fixed by this change (where
register %esp is aligned on the 64-byte boundary and the workarounds
that we already had didn't work):

https://code.google.com/p/chromium/issues/detail?id=311359

0:013> uf chrome_59630000!base::MessagePumpForIO::DoRunLoop
  518 59685c39 55      push    ebp
  518 59685c3a 8bec    mov     ebp,esp
  518 59685c3c 83e4c0  and     esp,0FFFFFFC0h  <== 64-byte boundary
  518 59685c3f 83ec34  sub     esp,34h
  518 59685c42 53      push    ebx
  518 59685c43 56      push    esi

Program string contains 64-byte alignment:
$T1 .raSearch = $T0 $T1 4 - 64 @ = $ebp $T1 4 - ^ = $eip $T1 ^ = 
$esp $T1 4 + = $20 $T0 56 - ^ =  $23 $T0 60 - ^ =  $24 $T0 64 - ^ =
Review URL: https://breakpad.appspot.com/694002

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

2 files changed, 245 insertions, 13 deletions

diff --git a/src/processor/stackwalker_x86.cc b/src/processor/stackwalker_x86.cc
index 0d8b3edc..29d98e4b 100644
--- a/src/processor/stackwalker_x86.cc
+++ b/src/processor/stackwalker_x86.cc
@@ -217,14 +217,27 @@ StackFrameX86* StackwalkerX86::GetCallerByWindowsFrameInfo(
   dictionary[".cbLocals"] = last_frame_info->local_size;
 
   uint32_t raSearchStart = last_frame->context.esp +
-                            last_frame_callee_parameter_size +
-                            last_frame_info->local_size +
-                            last_frame_info->saved_register_size;
+                           last_frame_callee_parameter_size +
+                           last_frame_info->local_size +
+                           last_frame_info->saved_register_size;
 
   uint32_t raSearchStartOld = raSearchStart;
   uint32_t found = 0;  // dummy value
   // Scan up to three words above the calculated search value, in case
   // the stack was aligned to a quadword boundary.
+  //
+  // TODO(ivan.penkov): Consider cleaning up the scan for return address that
+  // follows.  The purpose of this scan is to adjust the .raSearchStart
+  // calculation (which is based on register %esp) in the cases where register
+  // %esp may have been aligned (up to a quadword).  There are two problems
+  // with this approach:
+  //  1) In practice, 64 byte boundary alignment is seen which clearly can not
+  //     be handled by a three word scan.
+  //  2) A search for a return address is "guesswork" by definition because
+  //     the results will be different depending on what is left on the stack
+  //     from previous executions.
+  // So, basically, the results from this scan should be ignored if other means
+  // for calculation of the value of .raSearchStart are available.
   if (ScanForReturnAddress(raSearchStart, &raSearchStart, &found, 3) &&
       last_frame->trust == StackFrame::FRAME_TRUST_CONTEXT &&
       last_frame->windows_frame_info != NULL &&
@@ -241,11 +254,6 @@ StackFrameX86* StackwalkerX86::GetCallerByWindowsFrameInfo(
     ScanForReturnAddress(raSearchStart, &raSearchStart, &found, 3);
   }
 
-  // The difference between raSearch and raSearchStart is unknown,
-  // but making them the same seems to work well in practice.
-  dictionary[".raSearchStart"] = raSearchStart;
-  dictionary[".raSearch"] = raSearchStart;
-
   dictionary[".cbParams"] = last_frame_info->parameter_size;
 
   // Decide what type of program string to use. The program string is in
@@ -330,6 +338,27 @@ StackFrameX86* StackwalkerX86::GetCallerByWindowsFrameInfo(
     recover_ebp = false;
   }
 
+  // Check for alignment operators in the program string.  If alignment
+  // operators are found, then current %ebp must be valid and it is the only
+  // reliable data point that can be used for getting to the previous frame.
+  // E.g. the .raSearchStart calculation (above) is based on %esp and since
+  // %esp was aligned in the current frame (which is a lossy operation) the
+  // calculated value of .raSearchStart cannot be correct and should not be
+  // used.  Instead .raSearchStart must be calculated based on %ebp.
+  // The code that follows assumes that .raSearchStart is supposed to point
+  // at the saved return address (ebp + 4).
+  // For some more details on this topic, take a look at the following thread:
+  // https://groups.google.com/forum/#!topic/google-breakpad-dev/ZP1FA9B1JjM
+  if ((StackFrameX86::CONTEXT_VALID_EBP & last_frame->context_validity) != 0 &&
+      program_string.find('@') != string::npos) {
+    raSearchStart = last_frame->context.ebp + 4;
+  }
+
+  // The difference between raSearch and raSearchStart is unknown,
+  // but making them the same seems to work well in practice.
+  dictionary[".raSearchStart"] = raSearchStart;
+  dictionary[".raSearch"] = raSearchStart;
+
   // Now crank it out, making sure that the program string set at least the
   // two required variables.
   PostfixEvaluator<uint32_t> evaluator =
diff --git a/src/processor/stackwalker_x86_unittest.cc b/src/processor/stackwalker_x86_unittest.cc
index 690f5f31..008b496b 100644
--- a/src/processor/stackwalker_x86_unittest.cc
+++ b/src/processor/stackwalker_x86_unittest.cc
@@ -565,15 +565,18 @@ TEST_F(GetCallerFrame, WindowsFrameDataAligned) {
                    " $ebp $T1 4 - ^ ="
                    " $eip $T1 ^ ="
                    " $esp $T1 4 + =");
+  Label frame0_esp, frame0_ebp;
   Label frame1_esp, frame1_ebp;
   stack_section.start() = 0x80000000;
   stack_section
     // frame 0
+    .Mark(&frame0_esp)
     .D32(0x0ffa0ffa)                    // unused saved register
     .D32(0xdeaddead)                    // locals
     .D32(0xbeefbeef)
     .D32(0)                             // 8-byte alignment
-    .D32(frame1_ebp)
+    .Mark(&frame0_ebp)
+    .D32(frame1_ebp)                    // saved %ebp
     .D32(0x5000129d)                    // return address
     // frame 1
     .Mark(&frame1_esp)
@@ -584,8 +587,8 @@ TEST_F(GetCallerFrame, WindowsFrameDataAligned) {
 
   RegionFromSection();
   raw_context.eip = 0x4000aa85;
-  raw_context.esp = stack_section.start().Value();
-  raw_context.ebp = 0xf052c1de;         // should not be needed to walk frame
+  raw_context.esp = frame0_esp.Value();
+  raw_context.ebp = frame0_ebp.Value();
 
   StackFrameSymbolizer frame_symbolizer(&supplier, &resolver);
   StackwalkerX86 walker(&system_info, &raw_context, &stack_region, &modules,
@@ -606,8 +609,8 @@ TEST_F(GetCallerFrame, WindowsFrameDataAligned) {
     ASSERT_EQ(StackFrameX86::CONTEXT_VALID_ALL, frame0->context_validity);
     EXPECT_EQ(0x4000aa85U, frame0->instruction);
     EXPECT_EQ(0x4000aa85U, frame0->context.eip);
-    EXPECT_EQ(stack_section.start().Value(), frame0->context.esp);
-    EXPECT_EQ(0xf052c1deU, frame0->context.ebp);
+    EXPECT_EQ(frame0_esp.Value(), frame0->context.esp);
+    EXPECT_EQ(frame0_ebp.Value(), frame0->context.ebp);
     EXPECT_TRUE(frame0->windows_frame_info != NULL);
   }
 
@@ -1462,6 +1465,206 @@ TEST_F(GetCallerFrame, ReturnAddressIsNotInKnownModule) {
   }
 }
 
+// Test the .raSearchStart/.raSearch calculation when alignment operators are
+// used in the program string.  The current %ebp must be valid and it is the
+// only reliable data point that can be used for that calculation.
+TEST_F(GetCallerFrame, HandleAlignmentInProgramString) {
+  MockCodeModule chrome_dll(0x59630000, 0x19e3000, "chrome.dll", "version1");
+  SetModuleSymbols(&chrome_dll,  // chrome.dll
+                   "FUNC 56422 50c 8 base::MessageLoop::RunTask"
+                   "(base::PendingTask const &)\n"
+                   "56422 e 458 4589\n"
+                   "STACK WIN 4 56422 50c 11 0 8 c ac 0 1 $T1 .raSearch = $T0 "
+                   "$T1 4 - 8 @ = $ebp $T1 4 - ^ = $eip $T1 ^ = $esp $T1 4 + = "
+                   "$20 $T0 176 - ^ =  $23 $T0 180 - ^ =  $24 $T0 184 - ^ =\n"
+                   "FUNC 55d34 34a 0 base::MessageLoop::DoWork()\n"
+                   "55d34 11 596 4589\n"
+                   "STACK WIN 4 55d34 34a 19 0 0 c 134 0 1 $T1 .raSearch = "
+                   "$T0  $T1 4 - 8 @ = $ebp $T1 4 - ^ = $eip $T1 ^ = $esp "
+                   "$T1 4 + = $20 $T0 312 - ^ =  $23 $T0 316 - ^ =  $24 $T0 "
+                   "320 - ^ =\n"
+                   "FUNC 55c39 fb 0 base::MessagePumpForIO::DoRunLoop()\n"
+                   "55c39 d 518 19962\n"
+                   "STACK WIN 4 55c39 fb d 0 0 c 34 0 1 $T1 .raSearch = $T0 "
+                   "$T1 4 - 64 @ = $ebp $T1 4 - ^ = $eip $T1 ^ = $esp $T1 4 + "
+                   "= $20 $T0 56 - ^ =  $23 $T0 60 - ^ =  $24 $T0 64 - ^ =\n"
+                   "FUNC 55bf0 49 4 base::MessagePumpWin::Run(base::"
+                   "MessagePump::Delegate *)\n"
+                   "55bf0 49 48 4724\n"
+                   "STACK WIN 4 55bf0 49 c 0 4 0 10 0 1 $T0 $ebp = $eip $T0 4 "
+                   "+ ^ = $ebp $T0 ^ = $esp $T0 8 + =\n"
+                   "FUNC 165d de 4 malloc\n"
+                   "165d 6 119 54\n"
+                   "STACK WIN 4 165d de d 0 4 8 0 0 1 $T1 .raSearch = $T0 "
+                   "$T1 4 - 8 @ = $ebp $T1 4 - ^ = $eip $T1 ^ = $esp $T1 4 "
+                   "+ = $23 $T0 4 - ^ =  $24 $T0 8 - ^ =\n"
+                   "FUNC 55ac9 79 0 base::MessageLoop::RunInternal()\n"
+                   "55ac9 d 427 4589\n"
+                   "STACK WIN 4 55ac9 79 d 0 0 8 10 0 1 $T1 .raSearch = $T0 "
+                   "$T1 4 - 8 @ = $ebp $T1 4 - ^ = $eip $T1 ^ = $esp $T1 4 + = "
+                   "$23 $T0 20 - ^ =  $24 $T0 24 - ^ =\n");
+
+  // Create some modules with some stock debugging information.
+  MockCodeModules local_modules;
+  local_modules.Add(&chrome_dll);
+
+  Label frame0_esp;
+  Label frame0_ebp;
+  Label frame1_esp;
+  Label frame1_ebp;
+  Label frame2_esp;
+  Label frame2_ebp;
+  Label frame3_esp;
+  Label frame3_ebp;
+
+  stack_section.start() = 0x046bfc80;
+  stack_section
+    .D32(0)
+    .Mark(&frame0_esp)
+    .D32(0x01e235a0)
+    .D32(0x00000000)
+    .D32(0x01e9f580)
+    .D32(0x01e9f580)
+    .D32(0x00000020)
+    .D32(0x00000000)
+    .D32(0x00463674)
+    .D32(0x00000020)
+    .D32(0x00000000)
+    .D32(0x046bfcd8)
+    .D32(0x046bfcd8)
+    .D32(0x0001204b)
+    .D32(0x00000000)
+    .D32(0xfdddb523)
+    .D32(0x00000000)
+    .D32(0x00000007)
+    .D32(0x00000040)
+    .D32(0x00000000)
+    .D32(0x59631693)  // chrome_59630000!malloc+0x36
+    .D32(0x01e9f580)
+    .D32(0x01e9f580)
+    .D32(0x046bfcf8)
+    .D32(0x77da6704)  // ntdll!NtSetIoCompletion+0xc
+    .D32(0x046bfd4c)
+    .D32(0x59685bec)  // chrome_59630000!base::MessageLoop::StartHistogrammer..
+    .D32(0x01e235a0)
+
+    .Mark(&frame0_ebp)
+    .D32(frame1_ebp)  // Child EBP    .D32(0x046bfd0c)
+    .D32(0x59685c2e)  // Return address in
+                      // chrome_59630000!base::MessagePumpWin::Run+0x3e
+    .Mark(&frame1_esp)
+    .D32(0x01e75a90)
+    .D32(0x046bfd4c)
+    .D32(0x01e75a90)
+    .D32(0x00000000)
+    .D32(0x00000300)
+    .D32(0x00000001)
+
+    .Mark(&frame1_ebp)
+    .D32(frame2_ebp)  // Child EBP    .D32(0x046bfd30)
+    .D32(0x59685b3c)  // Return address in
+                      // chrome_59630000!base::MessageLoop::RunInternal+0x73
+    .Mark(&frame2_esp)
+    .D32(0x01e75a90)
+    .D32(0x00000000)
+    .D32(0x046bfd4c)
+    .D32(0x59658123)  // chrome_59630000!std::deque..
+    .D32(0x046bfda0)
+    .D32(0x01e79d70)
+    .D32(0x046bfda0)
+
+    .Mark(&frame2_ebp)  // .D32(0x046bfd40)
+    .D32(0)             // saved %ebp (stack end)
+    .D32(0);            // saved %eip (stack end)
+
+  RegionFromSection();
+  raw_context.eip = 0x59685c46;  // Context frame in
+                                 // base::MessagePumpForIO::DoRunLoop
+  raw_context.esp = frame0_esp.Value();
+  raw_context.ebp = frame0_ebp.Value();
+
+  StackFrameSymbolizer frame_symbolizer(&supplier, &resolver);
+  StackwalkerX86 walker(&system_info, &raw_context, &stack_region,
+                        &local_modules, &frame_symbolizer);
+  vector<const CodeModule*> modules_without_symbols;
+  vector<const CodeModule*> modules_with_corrupt_symbols;
+  ASSERT_TRUE(walker.Walk(&call_stack, &modules_without_symbols,
+                          &modules_with_corrupt_symbols));
+  ASSERT_EQ(0U, modules_without_symbols.size());
+  ASSERT_EQ(0U, modules_with_corrupt_symbols.size());
+  frames = call_stack.frames();
+
+  ASSERT_EQ(3U, frames->size());
+
+  {  // To avoid reusing locals by mistake
+    StackFrameX86 *frame = static_cast<StackFrameX86 *>(frames->at(0));
+    EXPECT_EQ(StackFrame::FRAME_TRUST_CONTEXT, frame->trust);
+    ASSERT_EQ(StackFrameX86::CONTEXT_VALID_ALL, frame->context_validity);
+    EXPECT_EQ("base::MessagePumpForIO::DoRunLoop()", frame->function_name);
+    EXPECT_EQ(0x59685c46U, frame->instruction);
+    EXPECT_EQ(0x59685c46U, frame->context.eip);
+    EXPECT_EQ(frame0_esp.Value(), frame->context.esp);
+    EXPECT_EQ(frame0_ebp.Value(), frame->context.ebp);
+    EXPECT_EQ(&chrome_dll, frame->module);
+    ASSERT_TRUE(frame->windows_frame_info != NULL);
+    EXPECT_EQ(WindowsFrameInfo::VALID_ALL, frame->windows_frame_info->valid);
+    EXPECT_EQ(WindowsFrameInfo::STACK_INFO_FRAME_DATA,
+              frame->windows_frame_info->type_);
+    EXPECT_EQ("$T1 .raSearch = $T0 "
+              "$T1 4 - 64 @ = $ebp $T1 4 - ^ = $eip $T1 ^ = $esp $T1 4 + "
+              "= $20 $T0 56 - ^ =  $23 $T0 60 - ^ =  $24 $T0 64 - ^ =",
+              frame->windows_frame_info->program_string);
+    EXPECT_FALSE(frame->windows_frame_info->allocates_base_pointer);
+  }
+
+  {  // To avoid reusing locals by mistake
+    StackFrameX86 *frame = static_cast<StackFrameX86 *>(frames->at(1));
+    EXPECT_EQ(StackFrame::FRAME_TRUST_CFI, frame->trust);
+    ASSERT_EQ((StackFrameX86::CONTEXT_VALID_EIP |
+               StackFrameX86::CONTEXT_VALID_ESP |
+               StackFrameX86::CONTEXT_VALID_EBP),
+              frame->context_validity);
+    EXPECT_EQ("base::MessagePumpWin::Run(base::MessagePump::Delegate *)",
+              frame->function_name);
+    EXPECT_EQ(1500011566U, frame->instruction + 1);
+    EXPECT_EQ(1500011566U, frame->context.eip);
+    EXPECT_EQ(frame1_esp.Value(), frame->context.esp);
+    EXPECT_EQ(frame1_ebp.Value(), frame->context.ebp);
+    EXPECT_EQ(&chrome_dll, frame->module);
+    ASSERT_TRUE(frame->windows_frame_info != NULL);
+    EXPECT_EQ(WindowsFrameInfo::VALID_ALL, frame->windows_frame_info->valid);
+    EXPECT_EQ(WindowsFrameInfo::STACK_INFO_FRAME_DATA,
+              frame->windows_frame_info->type_);
+    EXPECT_EQ("$T0 $ebp = $eip $T0 4 + ^ = $ebp $T0 ^ = $esp $T0 8 + =",
+              frame->windows_frame_info->program_string);
+    EXPECT_FALSE(frame->windows_frame_info->allocates_base_pointer);
+  }
+
+  {  // To avoid reusing locals by mistake
+    StackFrameX86 *frame = static_cast<StackFrameX86 *>(frames->at(2));
+    EXPECT_EQ(StackFrame::FRAME_TRUST_CFI, frame->trust);
+    ASSERT_EQ((StackFrameX86::CONTEXT_VALID_EIP |
+               StackFrameX86::CONTEXT_VALID_ESP |
+               StackFrameX86::CONTEXT_VALID_EBP),
+              frame->context_validity);
+    EXPECT_EQ("base::MessageLoop::RunInternal()", frame->function_name);
+    EXPECT_EQ(1500011324U, frame->instruction + 1);
+    EXPECT_EQ(1500011324U, frame->context.eip);
+    EXPECT_EQ(frame2_esp.Value(), frame->context.esp);
+    EXPECT_EQ(frame2_ebp.Value(), frame->context.ebp);
+    EXPECT_EQ(&chrome_dll, frame->module);
+    ASSERT_TRUE(frame->windows_frame_info != NULL);
+    EXPECT_EQ(WindowsFrameInfo::VALID_ALL, frame->windows_frame_info->valid);
+    EXPECT_EQ(WindowsFrameInfo::STACK_INFO_FRAME_DATA,
+              frame->windows_frame_info->type_);
+    EXPECT_EQ("$T1 .raSearch = $T0 "
+              "$T1 4 - 8 @ = $ebp $T1 4 - ^ = $eip $T1 ^ = $esp $T1 4 + = "
+              "$23 $T0 20 - ^ =  $24 $T0 24 - ^ =",
+              frame->windows_frame_info->program_string);
+    EXPECT_FALSE(frame->windows_frame_info->allocates_base_pointer);
+  }
+}
+
 // Scan the stack for a return address and potentially skip frames when the
 // current IP address is not in a known module.  Note, that that the span of
 // this scan is limited to 120 search words for the context frame and 30