Stack sampling profiler: re-enable stack collection for stacks terminated by leaf functions

base/profiler/native_stack_sampler_win.cc

Index: base/profiler/native_stack_sampler_win.cc
diff --git a/base/profiler/native_stack_sampler_win.cc b/base/profiler/native_stack_sampler_win.cc
index 73b8e11ce41257cc2be911750d59506b03fc336b..b31fd1cf29d80618926884386547f5530c339d1d 100644
--- a/base/profiler/native_stack_sampler_win.cc
+++ b/base/profiler/native_stack_sampler_win.cc
@@ -8,8 +8,11 @@
 #include <map>
 #include <utility>
 
+#include "base/containers/hash_tables.h"
 #include "base/logging.h"
+#include "base/memory/singleton.h"
 #include "base/profiler/native_stack_sampler.h"
+#include "base/stl_util.h"
 #include "base/strings/string_util.h"
 #include "base/strings/stringprintf.h"
 #include "base/strings/utf_string_conversions.h"
@@ -19,16 +22,84 @@
 
 namespace base {
 
+// LeafUnwindBlacklist --------------------------------------------------------
+
 namespace {
 
+// Records modules that are known to have functions that violate the Microsoft
+// x64 calling convention and would be dangerous to manually unwind if
+// encountered as the last frame on the call stack.
+class LeafUnwindBlacklist {
+ public:
+  static LeafUnwindBlacklist* GetInstance();
+
+  // These functions do not allocate memory and are safe to call between
+  // SuspendThread and ResumeThread.
+  void RecordModuleForBlacklist(const void* module);
+  bool IsBlacklisted(const void* module) const;
+
+  // Allocates memory. Must be invoked only after ResumeThread, otherwise
+  // RecordStack will eventually deadlock on a heap lock.
+  void AddRecordedModuleToBlacklistIfPresent();
+
+ private:
+  friend struct DefaultSingletonTraits<LeafUnwindBlacklist>;
+
+  LeafUnwindBlacklist();
+  ~LeafUnwindBlacklist();
+
+  // Holding location for a possible pending blacklisted module. We can't add
+  // the module to |blacklisted_modules_| between SuspendThread and ResumeThread
+  // because it may allocate memory and deadlock, so we store it here
+  // temporarily then move it to |blacklisted_modules_| after ResumeThread.
+  const void* pending_blacklisted_module_;

[Nico, 2015/08/15 01:44:18]

I found it a bit confusing that this ephemeral value is a member on this class.

[Mike Wittman, 2015/08/16 00:54:12]

I suppose we could treat this as an out argument of RecordStack instead. Let me
see how things shake out with the changes to improve testability.

+
+  // The set of modules known to have functions that violate the Microsoft x64
+  // calling convention.
+  base::hash_set<const void*> blacklisted_modules_;
+
+  DISALLOW_COPY_AND_ASSIGN(LeafUnwindBlacklist);
+};
+
+// static
+LeafUnwindBlacklist* LeafUnwindBlacklist::GetInstance() {
+  // Leaky for shutdown performance.
+  return Singleton<LeafUnwindBlacklist,
+                   LeakySingletonTraits<LeafUnwindBlacklist>>::get();
+}
+
+void LeafUnwindBlacklist::RecordModuleForBlacklist(const void* module) {
+  CHECK(!pending_blacklisted_module_);
+  pending_blacklisted_module_ = module;
+}
+
+bool LeafUnwindBlacklist::IsBlacklisted(const void* module) const {
+  return ContainsKey(blacklisted_modules_, module);
+}
+
+void LeafUnwindBlacklist::AddRecordedModuleToBlacklistIfPresent() {
+  if (pending_blacklisted_module_)
+    blacklisted_modules_.insert(pending_blacklisted_module_);
+  pending_blacklisted_module_ = nullptr;
+}
+
+LeafUnwindBlacklist::LeafUnwindBlacklist()
+    : pending_blacklisted_module_(nullptr) {
+}
+
+LeafUnwindBlacklist::~LeafUnwindBlacklist() {
+}
+
+// Stack recording functions --------------------------------------------------
+
 // Walks the stack represented by |context| from the current frame downwards,
 // recording the instruction pointers for each frame in |instruction_pointers|.
 int RecordStack(CONTEXT* context,
                 int max_stack_size,
                 const void* instruction_pointers[],
-                bool* last_frame_is_unknown_function) {
+                LeafUnwindBlacklist* leaf_unwind_blacklist) {
 #ifdef _WIN64
-  *last_frame_is_unknown_function = false;
+  bool unwind_info_present_for_all_frames = true;
 
   int i = 0;
   for (; (i < max_stack_size) && context->Rip; ++i) {
@@ -46,20 +117,68 @@ int RecordStack(CONTEXT* context,
       RtlVirtualUnwind(0, image_base, context->Rip, runtime_function, context,
                        &handler_data, &establisher_frame, &nvcontext);
     } else {
-      // If we don't have a RUNTIME_FUNCTION, then in theory this should be a
-      // leaf function whose frame contains only a return address, at
-      // RSP. However, crash data also indicates that some third party libraries
-      // do not provide RUNTIME_FUNCTION information for non-leaf functions. We
-      // could manually unwind the stack in the former case, but attempting to
-      // do so in the latter case would produce wrong results and likely crash,
-      // so just bail out.
+      // RtlLookupFunctionEntry didn't find unwind information. This could mean
+      // the code at the instruction pointer is in:
       //
-      // Ad hoc runs with instrumentation show that ~5% of stack traces end with
-      // a valid leaf function. To avoid selectively omitting these traces it
-      // makes sense to ultimately try to distinguish these two cases and
-      // selectively unwind the stack for legitimate leaf functions. For the
-      // purposes of avoiding crashes though, just ignore them all for now.
-      return i;
+      // 1. a true leaf function (i.e. a function that neither calls a function,
+      //    nor allocates any stack space itself) in which case the return
+      //    address is at RSP, or
+      //
+      // 2. a function that doesn't adhere to the Microsoft x64 calling
+      //    convention, either by not providing the required unwind information,
+      //    or by not having the prologue or epilogue required for unwinding;
+      //    this case has been observed in crash data in injected third party
+      //    DLLs.
+      //
+      // In valid code, case 1 can only occur (by definition) as the last frame
+      // on the stack. This happens in about 5% of observed stacks and can

[Nico, 2015/08/15 01:44:18]

This seems surprisingly high to me.

[Mike Wittman, 2015/08/16 00:54:12]

That's the rough average I saw profiling startups on a local build. I didn't
look into what the leaf functions were.

+      // easily be unwound by popping RSP and using it as the next frame's
+      // instruction pointer.
+      //
+      // Case 2 can occur anywhere on the stack, and attempting to unwind the
+      // stack will result in treating whatever value happens to be on the stack
+      // at RSP as the next frame's instruction pointer. This is certainly wrong
+      // and very likely to lead to crashing by deferencing invalid pointers in
+      // the next RtlVirtualUnwind call.
+      //
+      // If we see case 2 at a location not the last frame, and all the previous
+      // frame had valid unwind information, then this is definitely bad code.
+      // We blacklist the module as untrustable for unwinding if we encounter a

[Nico, 2015/08/15 01:44:18]

Is this blacklisting useful? You're expecting some amount of crashes if case 2
happens at the top (right?), so this only helps for 3rd-party modules that have
invalid abi stuff but never have any leaf functions while sampling. That seems
not super useful to me – can you motivate why this blacklisting is useful a bit
more?

[Mike Wittman, 2015/08/16 00:54:11]

That's correct, but the blacklisting should substantially mitigate the frequency
of these crashes.
No, the blacklisting makes it OK to encounter case 2 functions in these modules
at the top of the stack while sampling, *if* our first encounter of a case 2
function in the module is in a frame below the top of the stack. When that
happens we know the function is bad and record the module in the blacklist.
If/when we later encounter any function in the module at the top of the stack,
we assume it might be case 2 and don't continue the stack unwinding.

Where the blacklist doesn't help is if our first encounter of a case 2 function
in a module is at the top frame in the stack. Then, we don't know any better, so
pop RSP to get the return address, and likely crash.
The last time we enabled this functionality we blindly popped RSP whenever we
didn't get unwind information, even if we weren't at the top of the stack. We
saw 184 crashes, all apparently due to either an injected third party module
that was hooking Win32 or that had set its own WndProc. The vast majority were
obviously due to case 2 in frames below the top of the stack. These crashes
would be fixed by this change. 

Of the other crashes, it's not clear how many were case 2 at the top of the
stack vs. just being difficult to tell what was going on.

Crash data from this change should make clear the frequency of encountering case
2 at the top of the stack as the first encounter of a case 2 function in a
module. This will inform a decision about how to deal with this scenario --
whether it happens infrequently enough not to worry about, whether it's worth
implementing more sophisticated heuristics for avoiding it, or whether we're
better off just ignoring all stack traces that end in a function without unwind
info.

[Nico, 2015/08/16 01:32:00]

Ok, fair enough.

+      // function in it that doesn't have unwind information.
+
+      if (i == 0) {
+        // We are at the end of the stack. It's very likely that we're in case 1
+        // since the vast majority of code adheres to the Microsoft x64 calling
+        // convention. But there's a small chance we might be unlucky and be in
+        // case 2. If this module is known to have bad code according to the
+        // leaf unwind blacklist, stop here, otherwise manually unwind.
+        if (leaf_unwind_blacklist->IsBlacklisted(
+                reinterpret_cast<const void*>(image_base))) {
+          return i + 1;
+        }
+
+        context->Rip = context->Rsp;
+        context->Rsp += 8;
+        unwind_info_present_for_all_frames = false;
+      } else {
+        // We're not at the end of the stack. This frame is untrustworthy and we
+        // can't safely unwind from here.
+        if (unwind_info_present_for_all_frames) {
+          // Unwind information was present for all previous frames, so we can
+          // be confident this is case 2. Record the module to be blacklisted.
+          leaf_unwind_blacklist->RecordModuleForBlacklist(
+              reinterpret_cast<const void*>(image_base));
+        } else {
+          // We started off on a function without unwind information. It's very
+          // likely that all frames up to this point have been good, and this
+          // frame is case 2. But it's possible that the initial frame was case
+          // 2 but hadn't been blacklisted yet, and we've started to go off into
+          // the weeds. Since we can't be sure, just bail out without
+          // blacklisting the module; chances are we'll later encounter the same
+          // function on a stack with full unwind information.
+        }
+        return i + 1;
+      }
     }
   }
   return i;
@@ -74,11 +193,8 @@ int RecordStack(CONTEXT* context,
 // SuspendThreadAndRecordStack for why |addresses| and |module_handles| are
 // arrays.
 void FindModuleHandlesForAddresses(const void* const addresses[],
-                             HMODULE module_handles[], int stack_depth,
-                             bool last_frame_is_unknown_function) {
-  const int module_frames =
-      last_frame_is_unknown_function ? stack_depth - 1 : stack_depth;
-  for (int i = 0; i < module_frames; ++i) {
+                                   HMODULE module_handles[], int stack_depth) {
+  for (int i = 0; i < stack_depth; ++i) {
     HMODULE module_handle = NULL;
     if (GetModuleHandleEx(GET_MODULE_HANDLE_EX_FLAG_FROM_ADDRESS,
                           reinterpret_cast<LPCTSTR>(addresses[i]),
@@ -128,6 +244,8 @@ std::string GetBuildIDForModule(HMODULE module_handle) {
   return WideToUTF8(build_id);
 }
 
+// ScopedDisablePriorityBoost -------------------------------------------------
+
 // Disables priority boost on a thread for the lifetime of the object.
 class ScopedDisablePriorityBoost {
  public:
@@ -169,8 +287,7 @@ ScopedDisablePriorityBoost::~ScopedDisablePriorityBoost() {
 // pointers and module handles as preallocated arrays rather than vectors, since
 // vectors make it too easy to subtly allocate memory.
 int SuspendThreadAndRecordStack(HANDLE thread_handle, int max_stack_size,
-                                const void* instruction_pointers[],
-                                bool* last_frame_is_unknown_function) {
+                                const void* instruction_pointers[]) {
   if (::SuspendThread(thread_handle) == -1)
     return 0;
 
@@ -180,7 +297,7 @@ int SuspendThreadAndRecordStack(HANDLE thread_handle, int max_stack_size,
   if (::GetThreadContext(thread_handle, &thread_context)) {
     stack_depth = RecordStack(&thread_context, max_stack_size,
                               instruction_pointers,
-                              last_frame_is_unknown_function);
+                              LeafUnwindBlacklist::GetInstance());
   }
 
   // Disable the priority boost that the thread would otherwise receive on
@@ -197,9 +314,13 @@ int SuspendThreadAndRecordStack(HANDLE thread_handle, int max_stack_size,
   bool resume_thread_succeeded = ::ResumeThread(thread_handle) != -1;
   CHECK(resume_thread_succeeded) << "ResumeThread failed: " << GetLastError();
 
+  LeafUnwindBlacklist::GetInstance()->AddRecordedModuleToBlacklistIfPresent();
+
   return stack_depth;
 }
 
+// NativeStackSamplerWin ------------------------------------------------------
+
 class NativeStackSamplerWin : public NativeStackSampler {
  public:
   explicit NativeStackSamplerWin(win::ScopedHandle thread_handle);
@@ -264,12 +385,11 @@ void NativeStackSamplerWin::RecordStackSample(
   const void* instruction_pointers[max_stack_size] = {0};
   HMODULE module_handles[max_stack_size] = {0};
 
-  bool last_frame_is_unknown_function = false;
-  int stack_depth = SuspendThreadAndRecordStack(
-      thread_handle_.Get(), max_stack_size, instruction_pointers,
-      &last_frame_is_unknown_function);
+  int stack_depth = SuspendThreadAndRecordStack(thread_handle_.Get(),
+                                                max_stack_size,
+                                                instruction_pointers);
   FindModuleHandlesForAddresses(instruction_pointers, module_handles,
-                                stack_depth, last_frame_is_unknown_function);
+                                stack_depth);
   CopyToSample(instruction_pointers, module_handles, stack_depth, sample,
                current_modules_);
   FreeModuleHandles(stack_depth, module_handles);