src/third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h

   1 // Copyright (c) 2005, Google Inc.
   2 // All rights reserved.
   3 //
   4 // Redistribution and use in source and binary forms, with or without
   5 // modification, are permitted provided that the following conditions are
   6 // met:
   7 //
   8 //     * Redistributions of source code must retain the above copyright
   9 // notice, this list of conditions and the following disclaimer.
  10 //     * Redistributions in binary form must reproduce the above
  11 // copyright notice, this list of conditions and the following disclaimer
  12 // in the documentation and/or other materials provided with the
  13 // distribution.
  14 //     * Neither the name of Google Inc. nor the names of its
  15 // contributors may be used to endorse or promote products derived from
  16 // this software without specific prior written permission.
  17 //
  18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29
  30 // ---
  31 // Author: Sanjay Ghemawat
  32 //
  33 // Produce stack trace
  34
  35 #ifndef BASE_STACKTRACE_X86_INL_H_
  36 #define BASE_STACKTRACE_X86_INL_H_
  37 // Note: this file is included into stacktrace.cc more than once.
  38 // Anything that should only be defined once should be here:
  39
  40 #include "config.h"
  41 #include <stdlib.h>   // for NULL
  42 #include <assert.h>
  43 #if defined(HAVE_SYS_UCONTEXT_H)
  44 #include <sys/ucontext.h>
  45 #elif defined(HAVE_UCONTEXT_H)
  46 #include <ucontext.h>  // for ucontext_t
  47 #elif defined(HAVE_CYGWIN_SIGNAL_H)
  48 // cygwin/signal.h has a buglet where it uses pthread_attr_t without
  49 // #including <pthread.h> itself.  So we have to do it.
  50 # ifdef HAVE_PTHREAD
  51 # include <pthread.h>
  52 # endif
  53 #include <cygwin/signal.h>
  54 typedef ucontext ucontext_t;
  55 #endif
  56 #ifdef HAVE_STDINT_H
  57 #include <stdint.h>   // for uintptr_t
  58 #endif
  59 #ifdef HAVE_UNISTD_H
  60 #include <unistd.h>
  61 #endif
  62 #ifdef HAVE_MMAP
  63 #include <sys/mman.h> // for msync
  64 #include "base/vdso_support.h"
  65 #endif
  66
  67 #include "gperftools/stacktrace.h"
  68 #if defined(KEEP_SHADOW_STACKS)
  69 #include "linux_shadow_stacks.h"
  70 #endif  // KEEP_SHADOW_STACKS
  71
  72 #if defined(__linux__) && defined(__i386__) && defined(__ELF__) && defined(HAVE_MMAP)
  73 // Count "push %reg" instructions in VDSO __kernel_vsyscall(),
  74 // preceeding "syscall" or "sysenter".
  75 // If __kernel_vsyscall uses frame pointer, answer 0.
  76 //
  77 // kMaxBytes tells how many instruction bytes of __kernel_vsyscall
  78 // to analyze before giving up. Up to kMaxBytes+1 bytes of
  79 // instructions could be accessed.
  80 //
  81 // Here are known __kernel_vsyscall instruction sequences:
  82 //
  83 // SYSENTER (linux-2.6.26/arch/x86/vdso/vdso32/sysenter.S).
  84 // Used on Intel.
  85 //  0xffffe400 <__kernel_vsyscall+0>:       push   %ecx
  86 //  0xffffe401 <__kernel_vsyscall+1>:       push   %edx
  87 //  0xffffe402 <__kernel_vsyscall+2>:       push   %ebp
  88 //  0xffffe403 <__kernel_vsyscall+3>:       mov    %esp,%ebp
  89 //  0xffffe405 <__kernel_vsyscall+5>:       sysenter
  90 //
  91 // SYSCALL (see linux-2.6.26/arch/x86/vdso/vdso32/syscall.S).
  92 // Used on AMD.
  93 //  0xffffe400 <__kernel_vsyscall+0>:       push   %ebp
  94 //  0xffffe401 <__kernel_vsyscall+1>:       mov    %ecx,%ebp
  95 //  0xffffe403 <__kernel_vsyscall+3>:       syscall
  96 //
  97 // i386 (see linux-2.6.26/arch/x86/vdso/vdso32/int80.S)
  98 //  0xffffe400 <__kernel_vsyscall+0>:       int $0x80
  99 //  0xffffe401 <__kernel_vsyscall+1>:       ret
 100 //
 101 static const int kMaxBytes = 10;
 102
 103 // We use assert()s instead of DCHECK()s -- this is too low level
 104 // for DCHECK().
 105
 106 static int CountPushInstructions(const unsigned char *const addr) {
 107   int result = 0;
 108   for (int i = 0; i < kMaxBytes; ++i) {
 109     if (addr[i] == 0x89) {
 110       // "mov reg,reg"
 111       if (addr[i + 1] == 0xE5) {
 112         // Found "mov %esp,%ebp".
 113         return 0;
 114       }
 115       ++i;  // Skip register encoding byte.
 116     } else if (addr[i] == 0x0F &&
 117                (addr[i + 1] == 0x34 || addr[i + 1] == 0x05)) {
 118       // Found "sysenter" or "syscall".
 119       return result;
 120     } else if ((addr[i] & 0xF0) == 0x50) {
 121       // Found "push %reg".
 122       ++result;
 123     } else if (addr[i] == 0xCD && addr[i + 1] == 0x80) {
 124       // Found "int $0x80"
 125       assert(result == 0);
 126       return 0;
 127     } else {
 128       // Unexpected instruction.
 129       assert(0 == "unexpected instruction in __kernel_vsyscall");
 130       return 0;
 131     }
 132   }
 133   // Unexpected: didn't find SYSENTER or SYSCALL in
 134   // [__kernel_vsyscall, __kernel_vsyscall + kMaxBytes) interval.
 135   assert(0 == "did not find SYSENTER or SYSCALL in __kernel_vsyscall");
 136   return 0;
 137 }
 138 #endif
 139
 140 // Given a pointer to a stack frame, locate and return the calling
 141 // stackframe, or return NULL if no stackframe can be found. Perform sanity
 142 // checks (the strictness of which is controlled by the boolean parameter
 143 // "STRICT_UNWINDING") to reduce the chance that a bad pointer is returned.
 144 template<bool STRICT_UNWINDING, bool WITH_CONTEXT>
 145 static void **NextStackFrame(void **old_sp, const void *uc) {
 146   void **new_sp = (void **) *old_sp;
 147
 148 #if defined(__linux__) && defined(__i386__) && defined(HAVE_VDSO_SUPPORT)
 149   if (WITH_CONTEXT && uc != NULL) {
 150     // How many "push %reg" instructions are there at __kernel_vsyscall?
 151     // This is constant for a given kernel and processor, so compute
 152     // it only once.
 153     static int num_push_instructions = -1;  // Sentinel: not computed yet.
 154     // Initialize with sentinel value: __kernel_rt_sigreturn can not possibly
 155     // be there.
 156     static const unsigned char *kernel_rt_sigreturn_address = NULL;
 157     static const unsigned char *kernel_vsyscall_address = NULL;
 158     if (num_push_instructions == -1) {
 159       base::VDSOSupport vdso;
 160       if (vdso.IsPresent()) {
 161         base::VDSOSupport::SymbolInfo rt_sigreturn_symbol_info;
 162         base::VDSOSupport::SymbolInfo vsyscall_symbol_info;
 163         if (!vdso.LookupSymbol("__kernel_rt_sigreturn", "LINUX_2.5",
 164                                STT_FUNC, &rt_sigreturn_symbol_info) ||
 165             !vdso.LookupSymbol("__kernel_vsyscall", "LINUX_2.5",
 166                                STT_FUNC, &vsyscall_symbol_info) ||
 167             rt_sigreturn_symbol_info.address == NULL ||
 168             vsyscall_symbol_info.address == NULL) {
 169           // Unexpected: 32-bit VDSO is present, yet one of the expected
 170           // symbols is missing or NULL.
 171           assert(0 == "VDSO is present, but doesn't have expected symbols");
 172           num_push_instructions = 0;
 173         } else {
 174           kernel_rt_sigreturn_address =
 175               reinterpret_cast<const unsigned char *>(
 176                   rt_sigreturn_symbol_info.address);
 177           kernel_vsyscall_address =
 178               reinterpret_cast<const unsigned char *>(
 179                   vsyscall_symbol_info.address);
 180           num_push_instructions =
 181               CountPushInstructions(kernel_vsyscall_address);
 182         }
 183       } else {
 184         num_push_instructions = 0;
 185       }
 186     }
 187     if (num_push_instructions != 0 && kernel_rt_sigreturn_address != NULL &&
 188         old_sp[1] == kernel_rt_sigreturn_address) {
 189       const ucontext_t *ucv = static_cast<const ucontext_t *>(uc);
 190       // This kernel does not use frame pointer in its VDSO code,
 191       // and so %ebp is not suitable for unwinding.
 192       void **const reg_ebp =
 193           reinterpret_cast<void **>(ucv->uc_mcontext.gregs[REG_EBP]);
 194       const unsigned char *const reg_eip =
 195           reinterpret_cast<unsigned char *>(ucv->uc_mcontext.gregs[REG_EIP]);
 196       if (new_sp == reg_ebp &&
 197           kernel_vsyscall_address <= reg_eip &&
 198           reg_eip - kernel_vsyscall_address < kMaxBytes) {
 199         // We "stepped up" to __kernel_vsyscall, but %ebp is not usable.
 200         // Restore from 'ucv' instead.
 201         void **const reg_esp =
 202             reinterpret_cast<void **>(ucv->uc_mcontext.gregs[REG_ESP]);
 203         // Check that alleged %esp is not NULL and is reasonably aligned.
 204         if (reg_esp &&
 205             ((uintptr_t)reg_esp & (sizeof(reg_esp) - 1)) == 0) {
 206           // Check that alleged %esp is actually readable. This is to prevent
 207           // "double fault" in case we hit the first fault due to e.g. stack
 208           // corruption.
 209           //
 210           // page_size is linker-initalized to avoid async-unsafe locking
 211           // that GCC would otherwise insert (__cxa_guard_acquire etc).
 212           static int page_size;
 213           if (page_size == 0) {
 214             // First time through.
 215             page_size = getpagesize();
 216           }
 217           void *const reg_esp_aligned =
 218               reinterpret_cast<void *>(
 219                   (uintptr_t)(reg_esp + num_push_instructions - 1) &
 220                   ~(page_size - 1));
 221           if (msync(reg_esp_aligned, page_size, MS_ASYNC) == 0) {
 222             // Alleged %esp is readable, use it for further unwinding.
 223             new_sp = reinterpret_cast<void **>(
 224                 reg_esp[num_push_instructions - 1]);
 225           }
 226         }
 227       }
 228     }
 229   }
 230 #endif
 231
 232   // Check that the transition from frame pointer old_sp to frame
 233   // pointer new_sp isn't clearly bogus
 234   if (STRICT_UNWINDING) {
 235     // With the stack growing downwards, older stack frame must be
 236     // at a greater address that the current one.
 237     if (new_sp <= old_sp) return NULL;
 238     // Assume stack frames larger than 100,000 bytes are bogus.
 239     if ((uintptr_t)new_sp - (uintptr_t)old_sp > 100000) return NULL;
 240   } else {
 241     // In the non-strict mode, allow discontiguous stack frames.
 242     // (alternate-signal-stacks for example).
 243     if (new_sp == old_sp) return NULL;
 244     if (new_sp > old_sp) {
 245       // And allow frames upto about 1MB.
 246       const uintptr_t delta = (uintptr_t)new_sp - (uintptr_t)old_sp;
 247       const uintptr_t acceptable_delta = 1000000;
 248       if (delta > acceptable_delta) {
 249         return NULL;
 250       }
 251     }
 252   }
 253   if ((uintptr_t)new_sp & (sizeof(void *) - 1)) return NULL;
 254 #ifdef __i386__
 255   // On 64-bit machines, the stack pointer can be very close to
 256   // 0xffffffff, so we explicitly check for a pointer into the
 257   // last two pages in the address space
 258   if ((uintptr_t)new_sp >= 0xffffe000) return NULL;
 259 #endif
 260 #ifdef HAVE_MMAP
 261   if (!STRICT_UNWINDING) {
 262     // Lax sanity checks cause a crash on AMD-based machines with
 263     // VDSO-enabled kernels.
 264     // Make an extra sanity check to insure new_sp is readable.
 265     // Note: NextStackFrame<false>() is only called while the program
 266     //       is already on its last leg, so it's ok to be slow here.
 267     static int page_size = getpagesize();
 268     void *new_sp_aligned = (void *)((uintptr_t)new_sp & ~(page_size - 1));
 269     if (msync(new_sp_aligned, page_size, MS_ASYNC) == -1)
 270       return NULL;
 271   }
 272 #endif
 273   return new_sp;
 274 }
 275
 276 #endif  // BASE_STACKTRACE_X86_INL_H_
 277
 278 // Note: this part of the file is included several times.
 279 // Do not put globals below.
 280
 281 // The following 4 functions are generated from the code below:
 282 //   GetStack{Trace,Frames}()
 283 //   GetStack{Trace,Frames}WithContext()
 284 //
 285 // These functions take the following args:
 286 //   void** result: the stack-trace, as an array
 287 //   int* sizes: the size of each stack frame, as an array
 288 //               (GetStackFrames* only)
 289 //   int max_depth: the size of the result (and sizes) array(s)
 290 //   int skip_count: how many stack pointers to skip before storing in result
 291 //   void* ucp: a ucontext_t* (GetStack{Trace,Frames}WithContext only)
 292
 293 int GET_STACK_TRACE_OR_FRAMES {
 294   void **sp;
 295 #if (__GNUC__ > 4) || (__GNUC__ == 4 && __GNUC_MINOR__ >= 2) || __llvm__
 296   // __builtin_frame_address(0) can return the wrong address on gcc-4.1.0-k8.
 297   // It's always correct on llvm, and the techniques below aren't (in
 298   // particular, llvm-gcc will make a copy of pcs, so it's not in sp[2]),
 299   // so we also prefer __builtin_frame_address when running under llvm.
 300   sp = reinterpret_cast<void**>(__builtin_frame_address(0));
 301 #elif defined(__i386__)
 302   // Stack frame format:
 303   //    sp[0]   pointer to previous frame
 304   //    sp[1]   caller address
 305   //    sp[2]   first argument
 306   //    ...
 307   // NOTE: This will break under llvm, since result is a copy and not in sp[2]
 308   sp = (void **)&result - 2;
 309 #elif defined(__x86_64__)
 310   unsigned long rbp;
 311   // Move the value of the register %rbp into the local variable rbp.
 312   // We need 'volatile' to prevent this instruction from getting moved
 313   // around during optimization to before function prologue is done.
 314   // An alternative way to achieve this
 315   // would be (before this __asm__ instruction) to call Noop() defined as
 316   //   static void Noop() __attribute__ ((noinline));  // prevent inlining
 317   //   static void Noop() { asm(""); }  // prevent optimizing-away
 318   __asm__ volatile ("mov %%rbp, %0" : "=r" (rbp));
 319   // Arguments are passed in registers on x86-64, so we can't just
 320   // offset from &result
 321   sp = (void **) rbp;
 322 #else
 323 # error Using stacktrace_x86-inl.h on a non x86 architecture!
 324 #endif
 325
 326   int n = 0;
 327 #if defined(KEEP_SHADOW_STACKS)
 328   void **shadow_ip_stack;
 329   void **shadow_sp_stack;
 330   int stack_size;
 331   shadow_ip_stack = (void**) get_shadow_ip_stack(&stack_size);
 332   shadow_sp_stack = (void**) get_shadow_sp_stack(&stack_size);
 333   int shadow_index = stack_size - 1;
 334   for (int i = stack_size - 1; i >= 0; i--) {
 335     if (sp == shadow_sp_stack[i]) {
 336       shadow_index = i;
 337       break;
 338     }
 339   }
 340   void **prev_sp = NULL;
 341 #endif  // KEEP_SHADOW_STACKS
 342   while (sp && n < max_depth) {
 343     if (*(sp+1) == reinterpret_cast<void *>(0)) {
 344       // In 64-bit code, we often see a frame that
 345       // points to itself and has a return address of 0.
 346       break;
 347     }
 348 #if !IS_WITH_CONTEXT
 349     const void *const ucp = NULL;
 350 #endif
 351     void **next_sp = NextStackFrame<!IS_STACK_FRAMES, IS_WITH_CONTEXT>(sp, ucp);
 352     if (skip_count > 0) {
 353       skip_count--;
 354 #if defined(KEEP_SHADOW_STACKS)
 355       shadow_index--;
 356 #endif  // KEEP_SHADOW_STACKS
 357     } else {
 358       result[n] = *(sp+1);
 359 #if defined(KEEP_SHADOW_STACKS)
 360       if ((shadow_index > 0) && (sp == shadow_sp_stack[shadow_index])) {
 361         shadow_index--;
 362       }
 363 #endif  // KEEP_SHADOW_STACKS
 364
 365 #if IS_STACK_FRAMES
 366       if (next_sp > sp) {
 367         sizes[n] = (uintptr_t)next_sp - (uintptr_t)sp;
 368       } else {
 369         // A frame-size of 0 is used to indicate unknown frame size.
 370         sizes[n] = 0;
 371       }
 372 #endif
 373       n++;
 374     }
 375 #if defined(KEEP_SHADOW_STACKS)
 376     prev_sp = sp;
 377 #endif  // KEEP_SHADOW_STACKS
 378     sp = next_sp;
 379   }
 380
 381 #if defined(KEEP_SHADOW_STACKS)
 382   if (shadow_index >= 0) {
 383     for (int i = shadow_index; i >= 0; i--) {
 384       if (shadow_sp_stack[i] > prev_sp) {
 385         result[n] = shadow_ip_stack[i];
 386         if (n + 1 < max_depth) {
 387           n++;
 388           continue;
 389         }
 390       }
 391       break;
 392     }
 393   }
 394 #endif  // KEEP_SHADOW_STACKS
 395   return n;
 396 }