backtrace-arm.c revision 69f4cd7f5add7a7c7f5915e5292aab7eb2a42e9f
1/* 2 * Copyright (C) 2011 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17/* 18 * Backtracing functions for ARM. 19 * 20 * This implementation uses the exception unwinding tables provided by 21 * the compiler to unwind call frames. Refer to the ARM Exception Handling ABI 22 * documentation (EHABI) for more details about what's going on here. 23 * 24 * An ELF binary may contain an EXIDX section that provides an index to 25 * the exception handling table of each function, sorted by program 26 * counter address. 27 * 28 * This implementation also supports unwinding other processes via ptrace(). 29 * In that case, the EXIDX section is found by reading the ELF section table 30 * structures using ptrace(). 31 * 32 * Because the tables are used for exception handling, it can happen that 33 * a given function will not have an exception handling table. In particular, 34 * exceptions are assumed to only ever be thrown at call sites. Therefore, 35 * by definition leaf functions will not have exception handling tables. 36 * This may make unwinding impossible in some cases although we can still get 37 * some idea of the call stack by examining the PC and LR registers. 38 * 39 * As we are only interested in backtrace information, we do not need 40 * to perform all of the work of unwinding such as restoring register 41 * state and running cleanup functions. Unwinding is performed virtually on 42 * an abstract machine context consisting of just the ARM core registers. 43 * Furthermore, we do not run generic "personality functions" because 44 * we may not be in a position to execute arbitrary code, especially if 45 * we are running in a signal handler or using ptrace()! 46 */ 47 48#define LOG_TAG "Corkscrew" 49//#define LOG_NDEBUG 0 50 51#include "../backtrace-arch.h" 52#include "../backtrace-helper.h" 53#include "../ptrace-arch.h" 54#include <corkscrew/ptrace.h> 55 56#include <stdlib.h> 57#include <signal.h> 58#include <stdbool.h> 59#include <limits.h> 60#include <errno.h> 61#include <sys/ptrace.h> 62#include <sys/exec_elf.h> 63#include <cutils/log.h> 64 65/* Machine context at the time a signal was raised. */ 66typedef struct ucontext { 67 uint32_t uc_flags; 68 struct ucontext* uc_link; 69 stack_t uc_stack; 70 struct sigcontext { 71 uint32_t trap_no; 72 uint32_t error_code; 73 uint32_t oldmask; 74 uint32_t gregs[16]; 75 uint32_t arm_cpsr; 76 uint32_t fault_address; 77 } uc_mcontext; 78 uint32_t uc_sigmask; 79} ucontext_t; 80 81/* Unwind state. */ 82typedef struct { 83 uint32_t gregs[16]; 84} unwind_state_t; 85 86static const int R_SP = 13; 87static const int R_LR = 14; 88static const int R_PC = 15; 89 90/* Special EXIDX value that indicates that a frame cannot be unwound. */ 91static const uint32_t EXIDX_CANTUNWIND = 1; 92 93/* Get the EXIDX section start and size for the module that contains a 94 * given program counter address. 95 * 96 * When the executable is statically linked, the EXIDX section can be 97 * accessed by querying the values of the __exidx_start and __exidx_end 98 * symbols. 99 * 100 * When the executable is dynamically linked, the linker exports a function 101 * called dl_unwind_find_exidx that obtains the EXIDX section for a given 102 * absolute program counter address. 103 * 104 * Bionic exports a helpful function called __gnu_Unwind_Find_exidx that 105 * handles both cases, so we use that here. 106 */ 107typedef long unsigned int* _Unwind_Ptr; 108extern _Unwind_Ptr __gnu_Unwind_Find_exidx(_Unwind_Ptr pc, int *pcount); 109 110static uintptr_t find_exidx(uintptr_t pc, size_t* out_exidx_size) { 111 int count; 112 uintptr_t start = (uintptr_t)__gnu_Unwind_Find_exidx((_Unwind_Ptr)pc, &count); 113 *out_exidx_size = count; 114 return start; 115} 116 117/* Transforms a 31-bit place-relative offset to an absolute address. 118 * We assume the most significant bit is clear. */ 119static uintptr_t prel_to_absolute(uintptr_t place, uint32_t prel_offset) { 120 return place + (((int32_t)(prel_offset << 1)) >> 1); 121} 122 123static uintptr_t get_exception_handler( 124 const ptrace_context_t* context, pid_t tid, uintptr_t pc) { 125 uintptr_t exidx_start; 126 size_t exidx_size; 127 const map_info_t* mi; 128 if (tid < 0) { 129 mi = NULL; 130 exidx_start = find_exidx(pc, &exidx_size); 131 } else { 132 mi = find_map_info(context->map_info_list, pc); 133 if (mi && mi->data) { 134 const map_info_data_t* data = (const map_info_data_t*)mi->data; 135 exidx_start = data->exidx_start; 136 exidx_size = data->exidx_size / 8; 137 } else { 138 exidx_start = 0; 139 exidx_size = 0; 140 } 141 } 142 143 // The PC points to the instruction following the branch. 144 // We want to find the exception handler entry that corresponds to the branch itself, 145 // so we offset the PC backwards into the previous instruction. 146 // ARM instructions are 4 bytes, Thumb are 2, so we just subtract two so we either 147 // end up in the middle (ARM) or at the beginning of the instruction (Thumb). 148 if (pc >= 2) { 149 pc -= 2; 150 } 151 152 uintptr_t handler = 0; 153 if (exidx_start) { 154 uint32_t low = 0; 155 uint32_t high = exidx_size; 156 while (low < high) { 157 uint32_t index = (low + high) / 2; 158 uintptr_t entry = exidx_start + index * 8; 159 uint32_t entry_prel_pc; 160 if (!try_get_word(tid, entry, &entry_prel_pc)) { 161 break; 162 } 163 uintptr_t entry_pc = prel_to_absolute(entry, entry_prel_pc); 164 if (pc < entry_pc) { 165 high = index; 166 continue; 167 } 168 if (index + 1 < exidx_size) { 169 uintptr_t next_entry = entry + 8; 170 uint32_t next_entry_prel_pc; 171 if (!try_get_word(tid, next_entry, &next_entry_prel_pc)) { 172 break; 173 } 174 uintptr_t next_entry_pc = prel_to_absolute(next_entry, next_entry_prel_pc); 175 if (pc >= next_entry_pc) { 176 low = index + 1; 177 continue; 178 } 179 } 180 181 uintptr_t entry_handler_ptr = entry + 4; 182 uint32_t entry_handler; 183 if (!try_get_word(tid, entry_handler_ptr, &entry_handler)) { 184 break; 185 } 186 if (entry_handler & (1L << 31)) { 187 handler = entry_handler_ptr; // in-place handler data 188 } else if (entry_handler != EXIDX_CANTUNWIND) { 189 handler = prel_to_absolute(entry_handler_ptr, entry_handler); 190 } 191 break; 192 } 193 } 194 ALOGV("get_exception_handler: pc=0x%08x, module='%s', module_start=0x%08x, " 195 "exidx_start=0x%08x, exidx_size=%d, handler=0x%08x", 196 pc, mi ? mi->name : "<unknown>", mi ? mi->start : 0, 197 exidx_start, exidx_size, handler); 198 return handler; 199} 200 201typedef struct { 202 uintptr_t ptr; 203 uint32_t word; 204} byte_stream_t; 205 206static bool try_next_byte(pid_t tid, byte_stream_t* stream, uint8_t* out_value) { 207 uint8_t result; 208 switch (stream->ptr & 3) { 209 case 0: 210 if (!try_get_word(tid, stream->ptr, &stream->word)) { 211 *out_value = 0; 212 return false; 213 } 214 *out_value = stream->word >> 24; 215 break; 216 217 case 1: 218 *out_value = stream->word >> 16; 219 break; 220 221 case 2: 222 *out_value = stream->word >> 8; 223 break; 224 225 default: 226 *out_value = stream->word; 227 break; 228 } 229 230 ALOGV("next_byte: ptr=0x%08x, value=0x%02x", stream->ptr, *out_value); 231 stream->ptr += 1; 232 return true; 233} 234 235static void set_reg(unwind_state_t* state, uint32_t reg, uint32_t value) { 236 ALOGV("set_reg: reg=%d, value=0x%08x", reg, value); 237 state->gregs[reg] = value; 238} 239 240static bool try_pop_registers(pid_t tid, unwind_state_t* state, uint32_t mask) { 241 uint32_t sp = state->gregs[R_SP]; 242 bool sp_updated = false; 243 for (int i = 0; i < 16; i++) { 244 if (mask & (1 << i)) { 245 uint32_t value; 246 if (!try_get_word(tid, sp, &value)) { 247 return false; 248 } 249 if (i == R_SP) { 250 sp_updated = true; 251 } 252 set_reg(state, i, value); 253 sp += 4; 254 } 255 } 256 if (!sp_updated) { 257 set_reg(state, R_SP, sp); 258 } 259 return true; 260} 261 262/* Executes a built-in personality routine as defined in the EHABI. 263 * Returns true if unwinding should continue. 264 * 265 * The data for the built-in personality routines consists of a sequence 266 * of unwinding instructions, followed by a sequence of scope descriptors, 267 * each of which has a length and offset encoded using 16-bit or 32-bit 268 * values. 269 * 270 * We only care about the unwinding instructions. They specify the 271 * operations of an abstract machine whose purpose is to transform the 272 * virtual register state (including the stack pointer) such that 273 * the call frame is unwound and the PC register points to the call site. 274 */ 275static bool execute_personality_routine(pid_t tid, unwind_state_t* state, 276 byte_stream_t* stream, int pr_index) { 277 size_t size; 278 switch (pr_index) { 279 case 0: // Personality routine #0, short frame, descriptors have 16-bit scope. 280 size = 3; 281 break; 282 case 1: // Personality routine #1, long frame, descriptors have 16-bit scope. 283 case 2: { // Personality routine #2, long frame, descriptors have 32-bit scope. 284 uint8_t size_byte; 285 if (!try_next_byte(tid, stream, &size_byte)) { 286 return false; 287 } 288 size = (uint32_t)size_byte * sizeof(uint32_t) + 2; 289 break; 290 } 291 default: // Unknown personality routine. Stop here. 292 return false; 293 } 294 295 bool pc_was_set = false; 296 while (size--) { 297 uint8_t op; 298 if (!try_next_byte(tid, stream, &op)) { 299 return false; 300 } 301 if ((op & 0xc0) == 0x00) { 302 // "vsp = vsp + (xxxxxx << 2) + 4" 303 set_reg(state, R_SP, state->gregs[R_SP] + ((op & 0x3f) << 2) + 4); 304 } else if ((op & 0xc0) == 0x40) { 305 // "vsp = vsp - (xxxxxx << 2) - 4" 306 set_reg(state, R_SP, state->gregs[R_SP] - ((op & 0x3f) << 2) - 4); 307 } else if ((op & 0xf0) == 0x80) { 308 uint8_t op2; 309 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 310 return false; 311 } 312 uint32_t mask = (((uint32_t)op & 0x0f) << 12) | ((uint32_t)op2 << 4); 313 if (mask) { 314 // "Pop up to 12 integer registers under masks {r15-r12}, {r11-r4}" 315 if (!try_pop_registers(tid, state, mask)) { 316 return false; 317 } 318 if (mask & (1 << R_PC)) { 319 pc_was_set = true; 320 } 321 } else { 322 // "Refuse to unwind" 323 return false; 324 } 325 } else if ((op & 0xf0) == 0x90) { 326 if (op != 0x9d && op != 0x9f) { 327 // "Set vsp = r[nnnn]" 328 set_reg(state, R_SP, state->gregs[op & 0x0f]); 329 } else { 330 // "Reserved as prefix for ARM register to register moves" 331 // "Reserved as prefix for Intel Wireless MMX register to register moves" 332 return false; 333 } 334 } else if ((op & 0xf8) == 0xa0) { 335 // "Pop r4-r[4+nnn]" 336 uint32_t mask = (0x0ff0 >> (7 - (op & 0x07))) & 0x0ff0; 337 if (!try_pop_registers(tid, state, mask)) { 338 return false; 339 } 340 } else if ((op & 0xf8) == 0xa8) { 341 // "Pop r4-r[4+nnn], r14" 342 uint32_t mask = ((0x0ff0 >> (7 - (op & 0x07))) & 0x0ff0) | 0x4000; 343 if (!try_pop_registers(tid, state, mask)) { 344 return false; 345 } 346 } else if (op == 0xb0) { 347 // "Finish" 348 break; 349 } else if (op == 0xb1) { 350 uint8_t op2; 351 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 352 return false; 353 } 354 if (op2 != 0x00 && (op2 & 0xf0) == 0x00) { 355 // "Pop integer registers under mask {r3, r2, r1, r0}" 356 if (!try_pop_registers(tid, state, op2)) { 357 return false; 358 } 359 } else { 360 // "Spare" 361 return false; 362 } 363 } else if (op == 0xb2) { 364 // "vsp = vsp + 0x204 + (uleb128 << 2)" 365 uint32_t value = 0; 366 uint32_t shift = 0; 367 uint8_t op2; 368 do { 369 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 370 return false; 371 } 372 value |= (op2 & 0x7f) << shift; 373 shift += 7; 374 } while (op2 & 0x80); 375 set_reg(state, R_SP, state->gregs[R_SP] + (value << 2) + 0x204); 376 } else if (op == 0xb3) { 377 // "Pop VFP double-precision registers D[ssss]-D[ssss+cccc] saved (as if) by FSTMFDX" 378 uint8_t op2; 379 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 380 return false; 381 } 382 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 12); 383 } else if ((op & 0xf8) == 0xb8) { 384 // "Pop VFP double-precision registers D[8]-D[8+nnn] saved (as if) by FSTMFDX" 385 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op & 0x07) * 8 + 12); 386 } else if ((op & 0xf8) == 0xc0) { 387 // "Intel Wireless MMX pop wR[10]-wR[10+nnn]" 388 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op & 0x07) * 8 + 8); 389 } else if (op == 0xc6) { 390 // "Intel Wireless MMX pop wR[ssss]-wR[ssss+cccc]" 391 uint8_t op2; 392 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 393 return false; 394 } 395 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 8); 396 } else if (op == 0xc7) { 397 uint8_t op2; 398 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 399 return false; 400 } 401 if (op2 != 0x00 && (op2 & 0xf0) == 0x00) { 402 // "Intel Wireless MMX pop wCGR registers under mask {wCGR3,2,1,0}" 403 set_reg(state, R_SP, state->gregs[R_SP] + __builtin_popcount(op2) * 4); 404 } else { 405 // "Spare" 406 return false; 407 } 408 } else if (op == 0xc8) { 409 // "Pop VFP double precision registers D[16+ssss]-D[16+ssss+cccc] 410 // saved (as if) by FSTMFD" 411 uint8_t op2; 412 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 413 return false; 414 } 415 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 8); 416 } else if (op == 0xc9) { 417 // "Pop VFP double precision registers D[ssss]-D[ssss+cccc] saved (as if) by FSTMFDD" 418 uint8_t op2; 419 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 420 return false; 421 } 422 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 8); 423 } else if ((op == 0xf8) == 0xd0) { 424 // "Pop VFP double-precision registers D[8]-D[8+nnn] saved (as if) by FSTMFDD" 425 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op & 0x07) * 8 + 8); 426 } else { 427 // "Spare" 428 return false; 429 } 430 } 431 if (!pc_was_set) { 432 set_reg(state, R_PC, state->gregs[R_LR]); 433 } 434 return true; 435} 436 437static ssize_t unwind_backtrace_common(pid_t tid, const ptrace_context_t* context, 438 unwind_state_t* state, backtrace_frame_t* backtrace, 439 size_t ignore_depth, size_t max_depth) { 440 size_t ignored_frames = 0; 441 size_t returned_frames = 0; 442 443 uintptr_t handler = get_exception_handler(context, tid, state->gregs[R_PC]); 444 if (!handler) { 445 // If there is no handler for the PC, the program may have branched to 446 // an invalid address. Check whether we have a handler for the LR 447 // where we came from and use that instead. 448 backtrace_frame_t* frame = add_backtrace_entry(state->gregs[R_PC], backtrace, 449 ignore_depth, max_depth, &ignored_frames, &returned_frames); 450 if (frame) { 451 frame->stack_top = state->gregs[R_SP]; 452 } 453 454 handler = get_exception_handler(context, tid, state->gregs[R_LR]); 455 if (!handler) { 456 // We don't have a handler here either. Unwinding will not be possible. 457 // Return the PC and LR (if it looks sane) and call it good. 458 if (state->gregs[R_LR] && state->gregs[R_LR] != state->gregs[R_PC]) { 459 // Don't return the SP for this second frame because we don't 460 // know how big the first one is so we don't know where this 461 // one starts. 462 add_backtrace_entry(state->gregs[R_LR], backtrace, 463 ignore_depth, max_depth, &ignored_frames, &returned_frames); 464 } 465 return returned_frames; 466 } 467 468 // Ok, continue from the LR. 469 set_reg(state, R_PC, state->gregs[R_LR]); 470 } 471 472 while (handler && returned_frames < max_depth) { 473 backtrace_frame_t* frame = add_backtrace_entry(state->gregs[R_PC], backtrace, 474 ignore_depth, max_depth, &ignored_frames, &returned_frames); 475 if (frame) { 476 frame->stack_top = state->gregs[R_SP]; 477 } 478 479 byte_stream_t stream; 480 stream.ptr = handler; 481 uint8_t pr; 482 if (!try_next_byte(tid, &stream, &pr)) { 483 break; 484 } 485 if ((pr & 0xf0) != 0x80) { 486 // The first word is a place-relative pointer to a generic personality 487 // routine function. We don't support invoking such functions, so stop here. 488 break; 489 } 490 491 // The first byte indicates the personality routine to execute. 492 // Following bytes provide instructions to the personality routine. 493 if (!execute_personality_routine(tid, state, &stream, pr & 0x0f)) { 494 break; 495 } 496 if (frame && state->gregs[R_SP] > frame->stack_top) { 497 frame->stack_size = state->gregs[R_SP] - frame->stack_top; 498 } 499 500 handler = get_exception_handler(context, tid, state->gregs[R_PC]); 501 } 502 return returned_frames; 503} 504 505ssize_t unwind_backtrace_signal_arch(siginfo_t* siginfo, void* sigcontext, 506 backtrace_frame_t* backtrace, size_t ignore_depth, size_t max_depth) { 507 const ucontext_t* uc = (const ucontext_t*)sigcontext; 508 509 unwind_state_t state; 510 for (int i = 0; i < 16; i++) { 511 state.gregs[i] = uc->uc_mcontext.gregs[i]; 512 } 513 514 return unwind_backtrace_common(-1, NULL, &state, backtrace, ignore_depth, max_depth); 515} 516 517ssize_t unwind_backtrace_ptrace_arch(pid_t tid, const ptrace_context_t* context, 518 backtrace_frame_t* backtrace, size_t ignore_depth, size_t max_depth) { 519 struct pt_regs regs; 520 if (ptrace(PTRACE_GETREGS, tid, 0, ®s)) { 521 return -1; 522 } 523 524 unwind_state_t state; 525 for (int i = 0; i < 16; i++) { 526 state.gregs[i] = regs.uregs[i]; 527 } 528 529 return unwind_backtrace_common(tid, context, &state, backtrace, ignore_depth, max_depth); 530} 531