Unwind stack past system libraries on Linux.

base/debug/stack_trace.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/debug/stack_trace.h"
 
 #include <string.h>
 
 #include <algorithm>
-#include <limits>
 #include <sstream>
 
 #include "base/macros.h"
 
 #if HAVE_TRACE_STACK_FRAME_POINTERS
 
 #if defined(OS_LINUX) || defined(OS_ANDROID)
 #include <pthread.h>
 #include "base/process/process_handle.h"
 #include "base/threading/platform_thread.h"
 #endif
 
 #if defined(OS_LINUX) && defined(__GLIBC__)
 extern "C" void* __libc_stack_end;
 #endif
 
 #endif  // HAVE_TRACE_STACK_FRAME_POINTERS
 
 namespace base {
 namespace debug {
 
-StackTrace::StackTrace(const void* const* trace, size_t count) {
-  count = std::min(count, arraysize(trace_));
-  if (count)
-    memcpy(trace_, trace, count * sizeof(trace_[0]));
-  count_ = count;
-}
-
-StackTrace::~StackTrace() {
-}
-
-const void *const *StackTrace::Addresses(size_t* count) const {
-  *count = count_;
-  if (count_)
-    return trace_;
-  return NULL;
-}
-
-std::string StackTrace::ToString() const {
-  std::stringstream stream;
-#if !defined(__UCLIBC__)
-  OutputToStream(&stream);
-#endif
-  return stream.str();
-}
+namespace {
 
 #if HAVE_TRACE_STACK_FRAME_POINTERS
 
-static uintptr_t GetStackEnd() {
+#if defined(OS_LINUX)
+#define SCAN_STACK_FOR_FRAMES
+// TraceStackFramePointers() will try to scan stack for frame pointers to
+// continue unwinding past system libraries. Only supported on Linux where
+// system libraries are usually in the middle of the trace, for example:
+//
+//   TraceStackFramePointers
+//   <more frames from Chrome>
+//   g_main_context_dispatch    <--- unwinding stops here
+//   g_main_context_iteration
+//   base::MessagePumpGlib::Run
+//   base::RunLoop::Run         <--- resumes from here
+//   <more frames from Chrome>
+//   __libc_start_main
+//
+// Note that base::MessagePumpGlib::Run() is lost, because its frame was
+// not saved by g_main_context_iteration().
+//
+// For stack scanning to be efficient it's very important for the thread to
+// be started by Chrome. In that case we naturally terminate unwinding once
+// we reach the origin of the stack (i.e. GetStackEnd()). If the thread was
+// not started by Chrome (e.g. Android's main thread), then we end up always
+// scanning area at the origin of the stack, wasting time and not finding any
+// frames (since e.g. Android libraries don't have frame pointers).
+
+// Allows to resume ~95% of all prematurely terminated traces on Linux.
+constexpr size_t kMaxStackScanArea = 512;
+#endif
+
+// Returns end of the stack, or 0 if it's unknown.
+uintptr_t GetStackEnd() {
 #if defined(OS_ANDROID)
   // Bionic reads proc/maps on every call to pthread_getattr_np() when called
   // from the main thread. So we need to cache end of stack in that case to get
   // acceptable performance.
   // For all other threads pthread_getattr_np() is fast enough as it just reads
   // values from its pthread_t argument.
   static uintptr_t main_stack_end = 0;
 
   bool is_main_thread = GetCurrentProcId() == PlatformThread::CurrentId();
   if (is_main_thread && main_stack_end) {
@@ skipping 20 matching lines @@
   return stack_end;
 
 #elif defined(OS_LINUX) && defined(__GLIBC__)
 
   if (GetCurrentProcId() == PlatformThread::CurrentId()) {
     // For the main thread we have a shortcut.
     return reinterpret_cast<uintptr_t>(__libc_stack_end);
   } else {
     // No easy way to get stack end for non-main threads,
     // see crbug.com/617730.
-    return std::numeric_limits<uintptr_t>::max();
+    return 0;
   }
 
 #else
 
   // TODO(dskiba): support Windows, macOS
-  return std::numeric_limits<uintptr_t>::max();
+  return 0;
 
 #endif
 }
 
+#if defined(__arm__) && defined(__GNUC__) && !defined(__clang__)
+// GCC and LLVM generate slightly different frames on ARM, see
+// https://llvm.org/bugs/show_bug.cgi?id=18505 - LLVM generates
+// x86-compatible frame, while GCC needs adjustment.
+constexpr size_t kStackFrameAdjustment = sizeof(uintptr_t);
+#else
+constexpr size_t kStackFrameAdjustment = 0;
+#endif
+
+uintptr_t GetNextStackFrame(uintptr_t fp) {
+  return reinterpret_cast<const uintptr_t*>(fp)[0] - kStackFrameAdjustment;
+}
+
+uintptr_t GetStackFramePC(uintptr_t fp) {
+  return reinterpret_cast<const uintptr_t*>(fp)[1];
+}
+
+bool IsStackFrameValid(uintptr_t fp, uintptr_t prev_fp, uintptr_t stack_end) {
+  // With the stack growing downwards, older stack frame must be
+  // at a greater address that the current one.
+  if (fp <= prev_fp) return false;
+
+  // Assume huge stack frames are bogus.
+  if (fp - prev_fp > 100000) return false;
+
+  // Check alignment.
+  if (fp & (sizeof(uintptr_t) - 1)) return false;
+
+  if (stack_end) {
+    // Both fp[0] and fp[1] must be within the stack.
+    if (fp > stack_end - 2 * sizeof(uintptr_t)) return false;
+
+#if defined(SCAN_STACK_FOR_FRAMES)
+    // Additional check to filter out false positives.
+    if (GetStackFramePC(fp) < 32768) return false;
+#endif
+  }
+
+  return true;
+};
+
+#endif  // HAVE_TRACE_STACK_FRAME_POINTERS
+
+}  // namespace
+
+StackTrace::StackTrace(const void* const* trace, size_t count) {
+  count = std::min(count, arraysize(trace_));
+  if (count)
+    memcpy(trace_, trace, count * sizeof(trace_[0]));
+  count_ = count;
+}
+
+StackTrace::~StackTrace() {
+}
+
+const void *const *StackTrace::Addresses(size_t* count) const {
+  *count = count_;
+  if (count_)
+    return trace_;
+  return NULL;
+}
+
+std::string StackTrace::ToString() const {
+  std::stringstream stream;
+#if !defined(__UCLIBC__)
+  OutputToStream(&stream);
+#endif
+  return stream.str();
+}
+
+#if HAVE_TRACE_STACK_FRAME_POINTERS
+
 size_t TraceStackFramePointers(const void** out_trace,
                                size_t max_depth,
                                size_t skip_initial) {
   // Usage of __builtin_frame_address() enables frame pointers in this
-  // function even if they are not enabled globally. So 'sp' will always
+  // function even if they are not enabled globally. So 'fp' will always
   // be valid.
-  uintptr_t sp = reinterpret_cast<uintptr_t>(__builtin_frame_address(0));
+  uintptr_t fp = reinterpret_cast<uintptr_t>(__builtin_frame_address(0)) -
+                    kStackFrameAdjustment;
 
   uintptr_t stack_end = GetStackEnd();
 
   size_t depth = 0;
   while (depth < max_depth) {
-#if defined(__arm__) && defined(__GNUC__) && !defined(__clang__)
-    // GCC and LLVM generate slightly different frames on ARM, see
-    // https://llvm.org/bugs/show_bug.cgi?id=18505 - LLVM generates
-    // x86-compatible frame, while GCC needs adjustment.
-    sp -= sizeof(uintptr_t);
-#endif
-
-    // Both sp[0] and s[1] must be valid.
-    if (sp + 2 * sizeof(uintptr_t) > stack_end) {
-      break;
-    }
-
     if (skip_initial != 0) {
       skip_initial--;
     } else {
-      out_trace[depth++] = reinterpret_cast<const void**>(sp)[1];
+      out_trace[depth++] = reinterpret_cast<const void*>(GetStackFramePC(fp));
     }
 
-    // Find out next frame pointer
-    // (heuristics are from TCMalloc's stacktrace functions)
-    {
-      uintptr_t next_sp = reinterpret_cast<const uintptr_t*>(sp)[0];
-
-      // With the stack growing downwards, older stack frame must be
-      // at a greater address that the current one.
-      if (next_sp <= sp) break;
-
-      // Assume stack frames larger than 100,000 bytes are bogus.
-      if (next_sp - sp > 100000) break;
-
-      // Check alignment.
-      if (sp & (sizeof(void*) - 1)) break;
-
-      sp = next_sp;
+    uintptr_t next_fp = GetNextStackFrame(fp);
+    if (!IsStackFrameValid(next_fp, fp, stack_end)) {

[Primiano Tucci (use gerrit), 2016/08/25 11:42:53]

I'd reverse the if condition and reduce one leven of indentation here, I think
makes the overall code more readable if you do:

if (!IsStackFrameValid(next_fp, fp, stack_end)) 
  continue;

// Could not reconstruct a frame using frame pointer. Resorting on 
// stack scanning.
...

[Dmitry Skiba, 2016/08/30 18:04:21]

Done.

+#if defined(SCAN_STACK_FOR_FRAMES)

[Primiano Tucci (use gerrit), 2016/08/25 11:42:53]

Since you introduced all these beautiful helper functions here (nice), maybe you
can also have another helper for the stack scan.
The would remove the need of this SCAN_STACK_FOR_FRAME macro as you can:
1. here just do:
next_fp = ScanStackForNextFrame(...)
if (!next_fp) break;

2. above you can:
uintptr_t ScanStackForNextFrame(...) {
#if OS_LINUX...
...
# else
return 0;
#
}

Which IMHO reduces the need of jumping up and down with the eyes to follow the
macros.

[Dmitry Skiba, 2016/08/30 18:04:21]

Done.

[Primiano Tucci (use gerrit), 2016/08/31 13:48:49]

Doesn't seem so :)
WHat I mean is for ScanStackForNextFrame to be always defined. SO you don't need
the SCAN_STACK_FOR_FRAME define and just make the entire implementation a noop
if ! OS_LINUX.

[Dmitry Skiba, 2016/09/07 22:33:24]

Ah, I see. Done now :)

+      if (!stack_end) {
+        break;
+      }
+      fp += sizeof(uintptr_t);
+      uintptr_t last_scan_fp = std::min(fp + kMaxStackScanArea, stack_end) -

[Primiano Tucci (use gerrit), 2016/08/25 11:42:53]

Just a minor naming thing: when I saw "last_scan_fp" for a while I thought this
was "the resulting fp of the last stack scan".
Took me a while to realize that this is "the end boundary where to stop the
current stack scanning".
Maybe call it stack_scan_boundary ? or stack_scan_end? or stack_scan_limit? I'd
avoid "last", as IMHO can mistakenly get confused with "previous iteration"

[Dmitry Skiba, 2016/08/30 18:04:21]

Done.

+                                  sizeof(uintptr_t);
+      for (;fp <= last_scan_fp; fp += sizeof(uintptr_t)) {
+        next_fp = GetNextStackFrame(fp);
+        if (IsStackFrameValid(next_fp, fp, stack_end)) {
+          // Check two frames deep. Since stack frame is just a pointer to
+          // a higher address on the stack, it's relatively easy to find
+          // something that looks like one. However two linked frames are
+          // far less likely to be bogus.
+          uintptr_t next2_fp = GetNextStackFrame(next_fp);

[Primiano Tucci (use gerrit), 2016/08/25 11:42:53]

Hmm I'm missing something here, does this mean that you stack scan works only if
you have exactly one frame missing a FP?
If I read the code correctly this is:
- looking for something that looks like a pointer and checking if it's withing
the stack.
- If so, you find a very likely candidate. So far so good.
But now in the second nested if() you expect that the frame you found has a
valid FP. This might not be the case if you have two or more functions that
don't have a valid FP.

Or am I misreading completely this?

[Dmitry Skiba, 2016/08/30 18:04:21]

This tries to get rid of false positives - it's fairly easy to find something on
the stack that points further to the stack, and mistake that for a frame
pointer. Nested if() requires found frame pointer to be linked to the next valid
frame, reducing chances of finding garbage.

+          if (IsStackFrameValid(next2_fp, next_fp, stack_end)) {
+            break;
+          }
+        }
+      }
+      if (fp > last_scan_fp) {
+        break;
+      }
     }
+    fp = next_fp;
+#else
+    // Stack scanning is not enabled, stop unwinding.
+    break;
+#endif  // defined(SCAN_STACK_FOR_FRAMES)
   }
 
   return depth;
 }
 
 #endif  // HAVE_TRACE_STACK_FRAME_POINTERS
 
 }  // namespace debug
 }  // namespace base