1// Copyright 2017 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14//
15// Produce stack trace
16
17#ifndef ABSL_DEBUGGING_INTERNAL_STACKTRACE_X86_INL_INC_
18#define ABSL_DEBUGGING_INTERNAL_STACKTRACE_X86_INL_INC_
19
20#if defined(__linux__) && (defined(__i386__) || defined(__x86_64__))
21#include <ucontext.h>  // for ucontext_t
22#endif
23
24#if !defined(_WIN32)
25#include <unistd.h>
26#endif
27
28#include <cassert>
29#include <cstdint>
30
31#include "absl/base/macros.h"
32#include "absl/base/port.h"
33#include "absl/debugging/internal/address_is_readable.h"
34#include "absl/debugging/internal/vdso_support.h"  // a no-op on non-elf or non-glibc systems
35#include "absl/debugging/stacktrace.h"
36
37#include "absl/base/internal/raw_logging.h"
38
39using absl::debugging_internal::AddressIsReadable;
40
41#if defined(__linux__) && defined(__i386__)
42// Count "push %reg" instructions in VDSO __kernel_vsyscall(),
43// preceeding "syscall" or "sysenter".
44// If __kernel_vsyscall uses frame pointer, answer 0.
45//
46// kMaxBytes tells how many instruction bytes of __kernel_vsyscall
47// to analyze before giving up. Up to kMaxBytes+1 bytes of
48// instructions could be accessed.
49//
50// Here are known __kernel_vsyscall instruction sequences:
51//
52// SYSENTER (linux-2.6.26/arch/x86/vdso/vdso32/sysenter.S).
53// Used on Intel.
54//  0xffffe400 <__kernel_vsyscall+0>:       push   %ecx
55//  0xffffe401 <__kernel_vsyscall+1>:       push   %edx
56//  0xffffe402 <__kernel_vsyscall+2>:       push   %ebp
57//  0xffffe403 <__kernel_vsyscall+3>:       mov    %esp,%ebp
58//  0xffffe405 <__kernel_vsyscall+5>:       sysenter
59//
60// SYSCALL (see linux-2.6.26/arch/x86/vdso/vdso32/syscall.S).
61// Used on AMD.
62//  0xffffe400 <__kernel_vsyscall+0>:       push   %ebp
63//  0xffffe401 <__kernel_vsyscall+1>:       mov    %ecx,%ebp
64//  0xffffe403 <__kernel_vsyscall+3>:       syscall
65//
66
67// The sequence below isn't actually expected in Google fleet,
68// here only for completeness. Remove this comment from OSS release.
69
70// i386 (see linux-2.6.26/arch/x86/vdso/vdso32/int80.S)
71//  0xffffe400 <__kernel_vsyscall+0>:       int $0x80
72//  0xffffe401 <__kernel_vsyscall+1>:       ret
73//
74static const int kMaxBytes = 10;
75
76// We use assert()s instead of DCHECK()s -- this is too low level
77// for DCHECK().
78
79static int CountPushInstructions(const unsigned char *const addr) {
80  int result = 0;
81  for (int i = 0; i < kMaxBytes; ++i) {
82    if (addr[i] == 0x89) {
83      // "mov reg,reg"
84      if (addr[i + 1] == 0xE5) {
85        // Found "mov %esp,%ebp".
86        return 0;
87      }
88      ++i;  // Skip register encoding byte.
89    } else if (addr[i] == 0x0F &&
90               (addr[i + 1] == 0x34 || addr[i + 1] == 0x05)) {
91      // Found "sysenter" or "syscall".
92      return result;
93    } else if ((addr[i] & 0xF0) == 0x50) {
94      // Found "push %reg".
95      ++result;
96    } else if (addr[i] == 0xCD && addr[i + 1] == 0x80) {
97      // Found "int $0x80"
98      assert(result == 0);
99      return 0;
100    } else {
101      // Unexpected instruction.
102      assert(false && "unexpected instruction in __kernel_vsyscall");
103      return 0;
104    }
105  }
106  // Unexpected: didn't find SYSENTER or SYSCALL in
107  // [__kernel_vsyscall, __kernel_vsyscall + kMaxBytes) interval.
108  assert(false && "did not find SYSENTER or SYSCALL in __kernel_vsyscall");
109  return 0;
110}
111#endif
112
113// Assume stack frames larger than 100,000 bytes are bogus.
114static const int kMaxFrameBytes = 100000;
115
116// Returns the stack frame pointer from signal context, 0 if unknown.
117// vuc is a ucontext_t *.  We use void* to avoid the use
118// of ucontext_t on non-POSIX systems.
119static uintptr_t GetFP(const void *vuc) {
120#if !defined(__linux__)
121  static_cast<void>(vuc);  // Avoid an unused argument compiler warning.
122#else
123  if (vuc != nullptr) {
124    auto *uc = reinterpret_cast<const ucontext_t *>(vuc);
125#if defined(__i386__)
126    const auto bp = uc->uc_mcontext.gregs[REG_EBP];
127    const auto sp = uc->uc_mcontext.gregs[REG_ESP];
128#elif defined(__x86_64__)
129    const auto bp = uc->uc_mcontext.gregs[REG_RBP];
130    const auto sp = uc->uc_mcontext.gregs[REG_RSP];
131#else
132    const uintptr_t bp = 0;
133    const uintptr_t sp = 0;
134#endif
135    // Sanity-check that the base pointer is valid.  It should be as long as
136    // SHRINK_WRAP_FRAME_POINTER is not set, but it's possible that some code in
137    // the process is compiled with --copt=-fomit-frame-pointer or
138    // --copt=-momit-leaf-frame-pointer.
139    //
140    // TODO(bcmills): -momit-leaf-frame-pointer is currently the default
141    // behavior when building with clang.  Talk to the C++ toolchain team about
142    // fixing that.
143    if (bp >= sp && bp - sp <= kMaxFrameBytes) return bp;
144
145    // If bp isn't a plausible frame pointer, return the stack pointer instead.
146    // If we're lucky, it points to the start of a stack frame; otherwise, we'll
147    // get one frame of garbage in the stack trace and fail the sanity check on
148    // the next iteration.
149    return sp;
150  }
151#endif
152  return 0;
153}
154
155// Given a pointer to a stack frame, locate and return the calling
156// stackframe, or return null if no stackframe can be found. Perform sanity
157// checks (the strictness of which is controlled by the boolean parameter
158// "STRICT_UNWINDING") to reduce the chance that a bad pointer is returned.
159template <bool STRICT_UNWINDING, bool WITH_CONTEXT>
160ABSL_ATTRIBUTE_NO_SANITIZE_ADDRESS  // May read random elements from stack.
161ABSL_ATTRIBUTE_NO_SANITIZE_MEMORY   // May read random elements from stack.
162static void **NextStackFrame(void **old_fp, const void *uc) {
163  void **new_fp = (void **)*old_fp;
164
165#if defined(__linux__) && defined(__i386__)
166  if (WITH_CONTEXT && uc != nullptr) {
167    // How many "push %reg" instructions are there at __kernel_vsyscall?
168    // This is constant for a given kernel and processor, so compute
169    // it only once.
170    static int num_push_instructions = -1;  // Sentinel: not computed yet.
171    // Initialize with sentinel value: __kernel_rt_sigreturn can not possibly
172    // be there.
173    static const unsigned char *kernel_rt_sigreturn_address = nullptr;
174    static const unsigned char *kernel_vsyscall_address = nullptr;
175    if (num_push_instructions == -1) {
176#ifdef ABSL_HAVE_VDSO_SUPPORT
177      absl::debugging_internal::VDSOSupport vdso;
178      if (vdso.IsPresent()) {
179        absl::debugging_internal::VDSOSupport::SymbolInfo
180            rt_sigreturn_symbol_info;
181        absl::debugging_internal::VDSOSupport::SymbolInfo vsyscall_symbol_info;
182        if (!vdso.LookupSymbol("__kernel_rt_sigreturn", "LINUX_2.5", STT_FUNC,
183                               &rt_sigreturn_symbol_info) ||
184            !vdso.LookupSymbol("__kernel_vsyscall", "LINUX_2.5", STT_FUNC,
185                               &vsyscall_symbol_info) ||
186            rt_sigreturn_symbol_info.address == nullptr ||
187            vsyscall_symbol_info.address == nullptr) {
188          // Unexpected: 32-bit VDSO is present, yet one of the expected
189          // symbols is missing or null.
190          assert(false && "VDSO is present, but doesn't have expected symbols");
191          num_push_instructions = 0;
192        } else {
193          kernel_rt_sigreturn_address =
194              reinterpret_cast<const unsigned char *>(
195                  rt_sigreturn_symbol_info.address);
196          kernel_vsyscall_address =
197              reinterpret_cast<const unsigned char *>(
198                  vsyscall_symbol_info.address);
199          num_push_instructions =
200              CountPushInstructions(kernel_vsyscall_address);
201        }
202      } else {
203        num_push_instructions = 0;
204      }
205#else  // ABSL_HAVE_VDSO_SUPPORT
206      num_push_instructions = 0;
207#endif  // ABSL_HAVE_VDSO_SUPPORT
208    }
209    if (num_push_instructions != 0 && kernel_rt_sigreturn_address != nullptr &&
210        old_fp[1] == kernel_rt_sigreturn_address) {
211      const ucontext_t *ucv = static_cast<const ucontext_t *>(uc);
212      // This kernel does not use frame pointer in its VDSO code,
213      // and so %ebp is not suitable for unwinding.
214      void **const reg_ebp =
215          reinterpret_cast<void **>(ucv->uc_mcontext.gregs[REG_EBP]);
216      const unsigned char *const reg_eip =
217          reinterpret_cast<unsigned char *>(ucv->uc_mcontext.gregs[REG_EIP]);
218      if (new_fp == reg_ebp && kernel_vsyscall_address <= reg_eip &&
219          reg_eip - kernel_vsyscall_address < kMaxBytes) {
220        // We "stepped up" to __kernel_vsyscall, but %ebp is not usable.
221        // Restore from 'ucv' instead.
222        void **const reg_esp =
223            reinterpret_cast<void **>(ucv->uc_mcontext.gregs[REG_ESP]);
224        // Check that alleged %esp is not null and is reasonably aligned.
225        if (reg_esp &&
226            ((uintptr_t)reg_esp & (sizeof(reg_esp) - 1)) == 0) {
227          // Check that alleged %esp is actually readable. This is to prevent
228          // "double fault" in case we hit the first fault due to e.g. stack
229          // corruption.
230          void *const reg_esp2 = reg_esp[num_push_instructions - 1];
231          if (AddressIsReadable(reg_esp2)) {
232            // Alleged %esp is readable, use it for further unwinding.
233            new_fp = reinterpret_cast<void **>(reg_esp2);
234          }
235        }
236      }
237    }
238  }
239#endif
240
241  const uintptr_t old_fp_u = reinterpret_cast<uintptr_t>(old_fp);
242  const uintptr_t new_fp_u = reinterpret_cast<uintptr_t>(new_fp);
243
244  // Check that the transition from frame pointer old_fp to frame
245  // pointer new_fp isn't clearly bogus.  Skip the checks if new_fp
246  // matches the signal context, so that we don't skip out early when
247  // using an alternate signal stack.
248  //
249  // TODO(bcmills): The GetFP call should be completely unnecessary when
250  // SHRINK_WRAP_FRAME_POINTER is set (because we should be back in the thread's
251  // stack by this point), but it is empirically still needed (e.g. when the
252  // stack includes a call to abort).  unw_get_reg returns UNW_EBADREG for some
253  // frames.  Figure out why GetValidFrameAddr and/or libunwind isn't doing what
254  // it's supposed to.
255  if (STRICT_UNWINDING &&
256      (!WITH_CONTEXT || uc == nullptr || new_fp_u != GetFP(uc))) {
257    // With the stack growing downwards, older stack frame must be
258    // at a greater address that the current one.
259    if (new_fp_u <= old_fp_u) return nullptr;
260    if (new_fp_u - old_fp_u > kMaxFrameBytes) return nullptr;
261  } else {
262    if (new_fp == nullptr) return nullptr;  // skip AddressIsReadable() below
263    // In the non-strict mode, allow discontiguous stack frames.
264    // (alternate-signal-stacks for example).
265    if (new_fp == old_fp) return nullptr;
266  }
267
268  if (new_fp_u & (sizeof(void *) - 1)) return nullptr;
269#ifdef __i386__
270  // On 32-bit machines, the stack pointer can be very close to
271  // 0xffffffff, so we explicitly check for a pointer into the
272  // last two pages in the address space
273  if (new_fp_u >= 0xffffe000) return nullptr;
274#endif
275#if !defined(_WIN32)
276  if (!STRICT_UNWINDING) {
277    // Lax sanity checks cause a crash in 32-bit tcmalloc/crash_reason_test
278    // on AMD-based machines with VDSO-enabled kernels.
279    // Make an extra sanity check to insure new_fp is readable.
280    // Note: NextStackFrame<false>() is only called while the program
281    //       is already on its last leg, so it's ok to be slow here.
282
283    if (!AddressIsReadable(new_fp)) {
284      return nullptr;
285    }
286  }
287#endif
288  return new_fp;
289}
290
291template <bool IS_STACK_FRAMES, bool IS_WITH_CONTEXT>
292ABSL_ATTRIBUTE_NO_SANITIZE_ADDRESS  // May read random elements from stack.
293ABSL_ATTRIBUTE_NO_SANITIZE_MEMORY   // May read random elements from stack.
294ABSL_ATTRIBUTE_NOINLINE
295static int UnwindImpl(void **result, int *sizes, int max_depth, int skip_count,
296                      const void *ucp, int *min_dropped_frames) {
297  int n = 0;
298  void **fp = reinterpret_cast<void **>(__builtin_frame_address(0));
299
300  while (fp && n < max_depth) {
301    if (*(fp + 1) == reinterpret_cast<void *>(0)) {
302      // In 64-bit code, we often see a frame that
303      // points to itself and has a return address of 0.
304      break;
305    }
306    void **next_fp = NextStackFrame<!IS_STACK_FRAMES, IS_WITH_CONTEXT>(fp, ucp);
307    if (skip_count > 0) {
308      skip_count--;
309    } else {
310      result[n] = *(fp + 1);
311      if (IS_STACK_FRAMES) {
312        if (next_fp > fp) {
313          sizes[n] = (uintptr_t)next_fp - (uintptr_t)fp;
314        } else {
315          // A frame-size of 0 is used to indicate unknown frame size.
316          sizes[n] = 0;
317        }
318      }
319      n++;
320    }
321    fp = next_fp;
322  }
323  if (min_dropped_frames != nullptr) {
324    // Implementation detail: we clamp the max of frames we are willing to
325    // count, so as not to spend too much time in the loop below.
326    const int kMaxUnwind = 1000;
327    int j = 0;
328    for (; fp != nullptr && j < kMaxUnwind; j++) {
329      fp = NextStackFrame<!IS_STACK_FRAMES, IS_WITH_CONTEXT>(fp, ucp);
330    }
331    *min_dropped_frames = j;
332  }
333  return n;
334}
335
336namespace absl {
337ABSL_NAMESPACE_BEGIN
338namespace debugging_internal {
339bool StackTraceWorksForTest() {
340  return true;
341}
342}  // namespace debugging_internal
343ABSL_NAMESPACE_END
344}  // namespace absl
345
346#endif  // ABSL_DEBUGGING_INTERNAL_STACKTRACE_X86_INL_INC_
347