implement generic frame pointer backtracer

This supports frame pointer backtracing on x86-64, aarch64 and
riscv-s (should work for both 32 and 64 bits).

Also added is detection of borked libunwind on aarch64-s. In this case
frame pointer unwinder is preferred.

4 files changed, 394 insertions, 14 deletions

diff --git a/Makefile.am b/Makefile.am
index 730582e..d93300d 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -331,6 +331,7 @@ if WITH_STACK_TRACE
 ### The header files we use.  We divide into categories based on directory
 S_STACKTRACE_INCLUDES = src/stacktrace_impl_setup-inl.h \
                         src/stacktrace_generic-inl.h \
+                        src/stacktrace_generic_fp-inl.h \
                         src/stacktrace_libgcc-inl.h \
 			src/stacktrace_libunwind-inl.h \
 			src/stacktrace_arm-inl.h \
diff --git a/src/stacktrace.cc b/src/stacktrace.cc
index 7e853d8..ab1c381 100644
--- a/src/stacktrace.cc
+++ b/src/stacktrace.cc
@@ -120,6 +120,27 @@ struct GetStackImplementation {
 #define HAVE_GST_x86
 #endif // i386 || x86_64
 
+// Sadly, different OSes have very different mcontexts even for
+// identical hardware arch. So keep it linux-only for now.
+#if defined(__GNUC__) && __linux__ && (defined(__x86_64__) || defined(__aarch64__) || defined(__riscv))
+#define STACKTRACE_INL_HEADER "stacktrace_generic_fp-inl.h"
+#define GST_SUFFIX generic_fp
+#include "stacktrace_impl_setup-inl.h"
+#undef GST_SUFFIX
+#undef STACKTRACE_INL_HEADER
+#define HAVE_GST_generic_fp
+
+#undef TCMALLOC_UNSAFE_GENERIC_FP_STACKTRACE
+#define TCMALLOC_UNSAFE_GENERIC_FP_STACKTRACE 1
+
+#define STACKTRACE_INL_HEADER "stacktrace_generic_fp-inl.h"
+#define GST_SUFFIX generic_fp_unsafe
+#include "stacktrace_impl_setup-inl.h"
+#undef GST_SUFFIX
+#undef STACKTRACE_INL_HEADER
+#define HAVE_GST_generic_fp_unsafe
+#endif
+
 #if defined(__ppc__) || defined(__PPC__)
 #if defined(__linux__)
 #define STACKTRACE_INL_HEADER "stacktrace_powerpc-linux-inl.h"
@@ -169,6 +190,12 @@ static GetStackImplementation *all_impls[] = {
 #ifdef HAVE_GST_generic
   &impl__generic,
 #endif
+#ifdef HAVE_GST_generic_fp
+  &impl__generic_fp,
+#endif
+#ifdef HAVE_GST_generic_fp
+  &impl__generic_fp_unsafe,
+#endif
 #ifdef HAVE_GST_libunwind
   &impl__libunwind,
 #endif
@@ -204,6 +231,8 @@ static bool get_stack_impl_inited;
 static GetStackImplementation *get_stack_impl = &impl__instrument;
 #elif defined(HAVE_GST_win32)
 static GetStackImplementation *get_stack_impl = &impl__win32;
+#elif defined(HAVE_GST_generic_fp) && (!defined(HAVE_GST_libunwind) || defined(TCMALLOC_DONT_PREFER_LIBUNWIND))
+static GetStackImplementation *get_stack_impl = &impl__generic_fp;
 #elif defined(HAVE_GST_x86) && defined(TCMALLOC_DONT_PREFER_LIBUNWIND)
 static GetStackImplementation *get_stack_impl = &impl__x86;
 #elif defined(HAVE_GST_ppc) && defined(TCMALLOC_DONT_PREFER_LIBUNWIND)
@@ -306,6 +335,29 @@ PERFTOOLS_DLL_DECL int GetStackTraceWithContext(void** result, int max_depth,
                         result, max_depth, skip_count, uc));
 }
 
+// As of this writing, aarch64 has completely borked libunwind, so
+// lets test this case and fall back to frame pointers (which is
+// nearly but not quite perfect).
+ATTRIBUTE_NOINLINE
+static void maybe_convert_libunwind_to_generic_fp() {
+#if defined(HAVE_GST_libunwind) && defined(HAVE_GST_generic_fp)
+  if (get_stack_impl != &impl__libunwind) {
+    return;
+  }
+
+  // Okay we're on libunwind and we have generic_fp, check if
+  // libunwind returns bogus results.
+  void* stack[4];
+  int rv = get_stack_impl->GetStackTracePtr(stack, 4, 0);
+  if (rv > 2) {
+    // Seems fine
+    return;
+  }
+  // bogus. So replacing with generic_fp
+  get_stack_impl = &impl__generic_fp;
+#endif
+}
+
 static void init_default_stack_impl_inner(void) {
   if (get_stack_impl_inited) {
     return;
@@ -313,6 +365,7 @@ static void init_default_stack_impl_inner(void) {
   get_stack_impl_inited = true;
   const char *val = TCMallocGetenvSafe("TCMALLOC_STACKTRACE_METHOD");
   if (!val || !*val) {
+    maybe_convert_libunwind_to_generic_fp();
     return;
   }
   for (GetStackImplementation **p = all_impls; *p; p++) {
@@ -325,6 +378,7 @@ static void init_default_stack_impl_inner(void) {
   fprintf(stderr, "Unknown or unsupported stacktrace method requested: %s. Ignoring it\n", val);
 }
 
+ATTRIBUTE_NOINLINE
 static void init_default_stack_impl(void) {
   init_default_stack_impl_inner();
   if (EnvToBool("TCMALLOC_STACKTRACE_METHOD_VERBOSE", false)) {
diff --git a/src/stacktrace_generic_fp-inl.h b/src/stacktrace_generic_fp-inl.h
new file mode 100644
index 0000000..d458109
--- /dev/null
+++ b/src/stacktrace_generic_fp-inl.h
@@ -0,0 +1,222 @@
+// -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*-
+// Copyright (c) 2021, gperftools Contributors
+// 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.
+
+// This file contains "generic" stack frame pointer backtracing
+// code. Attempt is made to minimize amount of arch- or os-specific
+// code and keep everything as generic as possible. Currently
+// supported are x86-64, aarch64 and riscv.
+#ifndef BASE_STACKTRACE_GENERIC_FP_INL_H_
+#define BASE_STACKTRACE_GENERIC_FP_INL_H_
+
+#if defined(HAVE_SYS_UCONTEXT_H)
+#include <sys/ucontext.h>
+#elif defined(HAVE_UCONTEXT_H)
+#include <ucontext.h>
+#endif
+
+// This is only used on OS-es with mmap support.
+#include <sys/mman.h>
+
+// Set this to true to disable "probing" of addresses that are read to
+// make backtracing less-safe, but faster.
+#ifndef TCMALLOC_UNSAFE_GENERIC_FP_STACKTRACE
+#define TCMALLOC_UNSAFE_GENERIC_FP_STACKTRACE 0
+#endif
+
+namespace {
+namespace stacktrace_generic_fp {
+
+struct frame {
+  uintptr_t parent;
+  void* pc;
+};
+
+frame* adjust_fp(frame* f) {
+#ifdef __riscv
+  return f - 1;
+#else
+  return f;
+#endif
+}
+
+static bool CheckPageIsReadable(void* ptr, void* checked_ptr) {
+  static uintptr_t pagesize;
+  if (pagesize == 0) {
+    pagesize = getpagesize();
+  }
+
+  uintptr_t addr = reinterpret_cast<uintptr_t>(ptr);
+  uintptr_t parent_frame = reinterpret_cast<uintptr_t>(checked_ptr);
+
+  parent_frame &= ~(pagesize - 1);
+  addr &= ~(pagesize - 1);
+
+  if (parent_frame != 0 && addr == parent_frame) {
+    return true;
+  }
+
+  return (msync(reinterpret_cast<void*>(addr), pagesize, MS_ASYNC) == 0);
+}
+
+ATTRIBUTE_NOINLINE // forces architectures with link register to save it
+int capture(void **result, int max_depth, int skip_count,
+            void* initial_frame, void* const * initial_pc) {
+  int i = 0;
+
+  if (initial_pc != nullptr) {
+    // This is 'with ucontext' case. We take first pc from ucontext
+    // and then skip_count is ignored as we assume that caller only
+    // needed stack trace up to signal handler frame.
+    skip_count = 0;
+    if (max_depth == 0) {
+      return 0;
+    }
+    result[0] = *initial_pc;
+    i++;
+  }
+
+  constexpr uintptr_t kTooSmallAddr = 16 << 10;
+  constexpr uintptr_t kFrameSizeThreshold = 128 << 10;
+
+  // This is simplistic yet. Here we're targeting x86-64, aarch64 and
+  // riscv. All have 16 bytes stack alignment (even 32 bit
+  // riscv). This can be made more elaborate as we consider more
+  // architectures. Note, it allows us to only readability of check
+  // f->parent address.
+  constexpr uintptr_t kAlignment = 16;
+
+  uintptr_t initial_frame_addr = reinterpret_cast<uintptr_t>(initial_frame);
+  if ((initial_frame_addr & (kAlignment - 1)) != 0) {
+    return i;
+  }
+  if (initial_frame_addr < kTooSmallAddr) {
+    return i;
+  }
+
+  frame* prev_f = nullptr;
+  frame *f = adjust_fp(reinterpret_cast<frame*>(initial_frame));
+
+  while (i < max_depth) {
+    if (!TCMALLOC_UNSAFE_GENERIC_FP_STACKTRACE
+        && !CheckPageIsReadable(&f->parent, prev_f)) {
+      break;
+    }
+
+    void* pc = f->pc;
+    if (pc == nullptr) {
+      break;
+    }
+
+    if (i >= skip_count) {
+      result[i - skip_count] = pc;
+    }
+
+    i++;
+
+    uintptr_t parent_frame_addr = f->parent;
+    uintptr_t child_frame_addr = reinterpret_cast<uintptr_t>(f);
+
+    if (parent_frame_addr < kTooSmallAddr) {
+      break;
+    }
+    // stack grows towards smaller addresses, so if we didn't see
+    // frame address increased (going from child to parent), it is bad
+    // frame. We also test if frame is too big since that is another
+    // sign of bad stack frame.
+    if (parent_frame_addr - child_frame_addr > kFrameSizeThreshold) {
+      break;
+    }
+
+    if ((parent_frame_addr & (kAlignment - 1)) != 0) {
+      // not aligned, so we keep it safe and assume frame is bogus
+      break;
+    }
+
+    prev_f = f;
+
+    f = adjust_fp(reinterpret_cast<frame*>(parent_frame_addr));
+  }
+  return i;
+}
+
+}  // namespace stacktrace_generic_fp
+}  // namespace
+
+#endif  // BASE_STACKTRACE_GENERIC_FP_INL_H_
+
+// Note: this part of the file is included several times.
+// Do not put globals below.
+
+// The following 4 functions are generated from the code below:
+//   GetStack{Trace,Frames}()
+//   GetStack{Trace,Frames}WithContext()
+//
+// These functions take the following args:
+//   void** result: the stack-trace, as an array
+//   int* sizes: the size of each stack frame, as an array
+//               (GetStackFrames* only)
+//   int max_depth: the size of the result (and sizes) array(s)
+//   int skip_count: how many stack pointers to skip before storing in result
+//   void* ucp: a ucontext_t* (GetStack{Trace,Frames}WithContext only)
+
+static int GET_STACK_TRACE_OR_FRAMES {
+#if IS_STACK_FRAMES
+  memset(sizes, 0, sizeof(*sizes) * max_depth);
+#endif
+
+  // one for this function
+  skip_count += 1;
+
+  void* const * initial_pc = nullptr;
+  void* initial_frame = __builtin_frame_address(0);
+
+#if IS_WITH_CONTEXT
+  if (ucp) {
+    auto uc = static_cast<const ucontext_t*>(ucp);
+#ifdef __riscv
+    initial_pc = reinterpret_cast<void* const *>(&uc->uc_mcontext.__gregs[REG_PC]);
+    initial_frame = reinterpret_cast<void*>(uc->uc_mcontext.__gregs[REG_S0]);
+#elif __aarch64__
+    initial_pc = reinterpret_cast<void* const *>(&uc->uc_mcontext.pc);
+    initial_frame = reinterpret_cast<void*>(uc->uc_mcontext.regs[29]);
+#else
+    initial_pc = reinterpret_cast<void* const *>(&uc->uc_mcontext.gregs[REG_RIP]);
+    initial_frame = reinterpret_cast<void*>(uc->uc_mcontext.gregs[REG_RBP]);
+#endif
+  }
+#endif  // IS_WITH_CONTEXT
+
+  int n = stacktrace_generic_fp::capture(result, max_depth, skip_count,
+                                         initial_frame, initial_pc);
+
+  // make sure we don't tail-call capture
+  (void)*(const_cast<void * volatile *>(result));
+  return n;
+}
diff --git a/src/tests/stacktrace_unittest.cc b/src/tests/stacktrace_unittest.cc
index 6c764d0..e55a632 100644
--- a/src/tests/stacktrace_unittest.cc
+++ b/src/tests/stacktrace_unittest.cc
@@ -34,9 +34,18 @@
 #endif
 #include <stdio.h>
 #include <stdlib.h>
+
+// On those architectures we can and should test if backtracing with
+// ucontext and from signal handler works
+#if __GNUC__ && __linux__ && (__x86_64__ || __aarch64__ || __riscv)
+#include <signal.h>
+#define TEST_UCONTEXT_BITS 1
+#endif
+
 #include "base/commandlineflags.h"
 #include "base/logging.h"
 #include <gperftools/stacktrace.h>
+#include "tests/testutil.h"
 
 namespace {
 
@@ -97,6 +106,7 @@ AddressRange expected_range[BACKTRACE_STEPS];
 #define ADJUST_ADDRESS_RANGE_FROM_RA(prange) do { } while (0)
 #endif  // __GNUC__
 
+
 //-----------------------------------------------------------------------//
 
 void CheckRetAddrIsInFunction(void *ret_addr, const AddressRange &range)
@@ -107,24 +117,105 @@ void CheckRetAddrIsInFunction(void *ret_addr, const AddressRange &range)
 
 //-----------------------------------------------------------------------//
 
-void ATTRIBUTE_NOINLINE CheckStackTrace(int);
-void ATTRIBUTE_NOINLINE CheckStackTraceLeaf(void) {
-  const int STACK_LEN = 10;
-  void *stack[STACK_LEN];
+#if TEST_UCONTEXT_BITS
+
+struct get_stack_trace_args {
+	int *size_ptr;
+	void **result;
+	int max_depth;
+	uintptr_t where;
+} gst_args;
+
+static
+void SignalHandler(int dummy, siginfo_t *si, void* ucv) {
+	auto uc = static_cast<ucontext_t*>(ucv);
+
+#ifdef __riscv
+	uc->uc_mcontext.__gregs[REG_PC] = gst_args.where;
+#elif __aarch64__
+	uc->uc_mcontext.pc = gst_args.where;
+#else
+	uc->uc_mcontext.gregs[REG_RIP] = gst_args.where;
+#endif
+
+	*gst_args.size_ptr = GetStackTraceWithContext(
+		gst_args.result,
+		gst_args.max_depth,
+		2,
+		uc);
+}
+
+int ATTRIBUTE_NOINLINE CaptureLeafUContext(void **stack, int stack_len) {
+  INIT_ADDRESS_RANGE(CheckStackTraceLeaf, start, end, &expected_range[0]);
+  DECLARE_ADDRESS_LABEL(start);
+
   int size;
 
-  ADJUST_ADDRESS_RANGE_FROM_RA(&expected_range[1]);
+  printf("Capturing stack trace from signal's ucontext\n");
+  struct sigaction sa;
+  memset(&sa, 0, sizeof(sa));
+  sa.sa_sigaction = SignalHandler;
+  sa.sa_flags = SA_SIGINFO | SA_RESETHAND;
+  int rv = sigaction(SIGSEGV, &sa, nullptr);
+  CHECK(rv == 0);
+
+  gst_args.size_ptr = &size;
+  gst_args.result = stack;
+  gst_args.max_depth = stack_len;
+  gst_args.where = reinterpret_cast<uintptr_t>(noopt(&&after));
+
+  // now, "write" to null pointer and trigger sigsegv to run signal
+  // handler. It'll then change PC to after, as if we jumped one line
+  // below.
+  *noopt(reinterpret_cast<void**>(0)) = 0;
+  // this is not reached, but gcc gets really odd if we don't actually
+  // use computed goto.
+  static void* jump_target = &&after;
+  goto *noopt(&jump_target);
+
+after:
+  printf("Obtained %d stack frames.\n", size);
+  CHECK_GE(size, 1);
+  CHECK_LE(size, stack_len);
+
+  DECLARE_ADDRESS_LABEL(end);
+
+  return size;
+}
+
+#endif  // TEST_UCONTEXT_BITS
+
+int ATTRIBUTE_NOINLINE CaptureLeafPlain(void **stack, int stack_len) {
   INIT_ADDRESS_RANGE(CheckStackTraceLeaf, start, end, &expected_range[0]);
   DECLARE_ADDRESS_LABEL(start);
-  size = GetStackTrace(stack, STACK_LEN, 0);
+
+  int size = GetStackTrace(stack, stack_len, 0);
+
   printf("Obtained %d stack frames.\n", size);
   CHECK_GE(size, 1);
-  CHECK_LE(size, STACK_LEN);
+  CHECK_LE(size, stack_len);
+
+  DECLARE_ADDRESS_LABEL(end);
+
+  return size;
+}
+
+void ATTRIBUTE_NOINLINE CheckStackTrace(int);
+
+int (*leaf_capture_fn)(void**, int) = CaptureLeafPlain;
+
+void ATTRIBUTE_NOINLINE CheckStackTraceLeaf(int i) {
+  const int STACK_LEN = 20;
+  void *stack[STACK_LEN];
+  int size;
+
+  ADJUST_ADDRESS_RANGE_FROM_RA(&expected_range[1]);
+
+  size = leaf_capture_fn(stack, STACK_LEN);
 
 #ifdef HAVE_EXECINFO_H
   {
     char **strings = backtrace_symbols(stack, size);
-    printf("Obtained %d stack frames.\n", size);
     for (int i = 0; i < size; i++)
       printf("%s %p\n", strings[i], stack[i]);
     printf("CheckStackTrace() addr: %p\n", &CheckStackTrace);
@@ -132,14 +223,18 @@ void ATTRIBUTE_NOINLINE CheckStackTraceLeaf(void) {
   }
 #endif
 
-  for (int i = 0; i < BACKTRACE_STEPS; i++) {
+  for (int i = 0, j = 0; i < BACKTRACE_STEPS; i++, j++) {
+    if (i == 1 && j == 1) {
+      // this is expected to be our function for which we don't
+      // establish bounds. So skip.
+      j++;
+    }
     printf("Backtrace %d: expected: %p..%p  actual: %p ... ",
-           i, expected_range[i].start, expected_range[i].end, stack[i]);
+           i, expected_range[i].start, expected_range[i].end, stack[j]);
     fflush(stdout);
-    CheckRetAddrIsInFunction(stack[i], expected_range[i]);
+    CheckRetAddrIsInFunction(stack[j], expected_range[i]);
     printf("OK\n");
   }
-  DECLARE_ADDRESS_LABEL(end);
 }
 
 //-----------------------------------------------------------------------//
@@ -150,7 +245,7 @@ void ATTRIBUTE_NOINLINE CheckStackTrace4(int i) {
   INIT_ADDRESS_RANGE(CheckStackTrace4, start, end, &expected_range[1]);
   DECLARE_ADDRESS_LABEL(start);
   for (int j = i; j >= 0; j--)
-    CheckStackTraceLeaf();
+    CheckStackTraceLeaf(j);
   DECLARE_ADDRESS_LABEL(end);
 }
 void ATTRIBUTE_NOINLINE CheckStackTrace3(int i) {
@@ -180,8 +275,9 @@ void ATTRIBUTE_NOINLINE CheckStackTrace1(int i) {
 void ATTRIBUTE_NOINLINE CheckStackTrace(int i) {
   INIT_ADDRESS_RANGE(CheckStackTrace, start, end, &expected_range[5]);
   DECLARE_ADDRESS_LABEL(start);
-  for (int j = i; j >= 0; j--)
+  for (int j = i; j >= 0; j--) {
     CheckStackTrace1(j);
+  }
   DECLARE_ADDRESS_LABEL(end);
 }
 
@@ -191,5 +287,12 @@ void ATTRIBUTE_NOINLINE CheckStackTrace(int i) {
 int main(int argc, char ** argv) {
   CheckStackTrace(0);
   printf("PASS\n");
+
+#if TEST_UCONTEXT_BITS
+  leaf_capture_fn = CaptureLeafUContext;
+  CheckStackTrace(0);
+  printf("PASS\n");
+#endif  // TEST_UCONTEXT_BITS
+
   return 0;
 }