backtrace-arm.c revision f0c5872637a63e28e3cd314cfc915c07f76df9c6
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(const memory_t* memory, 124 const map_info_t* map_info_list, uintptr_t pc) { 125 if (!pc) { 126 ALOGV("get_exception_handler: pc is zero, no handler"); 127 return 0; 128 } 129 130 uintptr_t exidx_start; 131 size_t exidx_size; 132 const map_info_t* mi; 133 if (memory->tid < 0) { 134 mi = NULL; 135 exidx_start = find_exidx(pc, &exidx_size); 136 } else { 137 mi = find_map_info(map_info_list, pc); 138 if (mi && mi->data) { 139 const map_info_data_t* data = (const map_info_data_t*)mi->data; 140 exidx_start = data->exidx_start; 141 exidx_size = data->exidx_size; 142 } else { 143 exidx_start = 0; 144 exidx_size = 0; 145 } 146 } 147 148 uintptr_t handler = 0; 149 if (exidx_start) { 150 uint32_t low = 0; 151 uint32_t high = exidx_size; 152 while (low < high) { 153 uint32_t index = (low + high) / 2; 154 uintptr_t entry = exidx_start + index * 8; 155 uint32_t entry_prel_pc; 156 if (!try_get_word(memory, entry, &entry_prel_pc)) { 157 break; 158 } 159 uintptr_t entry_pc = prel_to_absolute(entry, entry_prel_pc); 160 if (pc < entry_pc) { 161 high = index; 162 continue; 163 } 164 if (index + 1 < exidx_size) { 165 uintptr_t next_entry = entry + 8; 166 uint32_t next_entry_prel_pc; 167 if (!try_get_word(memory, next_entry, &next_entry_prel_pc)) { 168 break; 169 } 170 uintptr_t next_entry_pc = prel_to_absolute(next_entry, next_entry_prel_pc); 171 if (pc >= next_entry_pc) { 172 low = index + 1; 173 continue; 174 } 175 } 176 177 uintptr_t entry_handler_ptr = entry + 4; 178 uint32_t entry_handler; 179 if (!try_get_word(memory, entry_handler_ptr, &entry_handler)) { 180 break; 181 } 182 if (entry_handler & (1L << 31)) { 183 handler = entry_handler_ptr; // in-place handler data 184 } else if (entry_handler != EXIDX_CANTUNWIND) { 185 handler = prel_to_absolute(entry_handler_ptr, entry_handler); 186 } 187 break; 188 } 189 } 190 if (mi) { 191 ALOGV("get_exception_handler: pc=0x%08x, module='%s', module_start=0x%08x, " 192 "exidx_start=0x%08x, exidx_size=%d, handler=0x%08x", 193 pc, mi->name, mi->start, exidx_start, exidx_size, handler); 194 } else { 195 ALOGV("get_exception_handler: pc=0x%08x, " 196 "exidx_start=0x%08x, exidx_size=%d, handler=0x%08x", 197 pc, exidx_start, exidx_size, handler); 198 } 199 return handler; 200} 201 202typedef struct { 203 uintptr_t ptr; 204 uint32_t word; 205} byte_stream_t; 206 207static bool try_next_byte(const memory_t* memory, byte_stream_t* stream, uint8_t* out_value) { 208 uint8_t result; 209 switch (stream->ptr & 3) { 210 case 0: 211 if (!try_get_word(memory, stream->ptr, &stream->word)) { 212 *out_value = 0; 213 return false; 214 } 215 *out_value = stream->word >> 24; 216 break; 217 218 case 1: 219 *out_value = stream->word >> 16; 220 break; 221 222 case 2: 223 *out_value = stream->word >> 8; 224 break; 225 226 default: 227 *out_value = stream->word; 228 break; 229 } 230 231 ALOGV("next_byte: ptr=0x%08x, value=0x%02x", stream->ptr, *out_value); 232 stream->ptr += 1; 233 return true; 234} 235 236static void set_reg(unwind_state_t* state, uint32_t reg, uint32_t value) { 237 ALOGV("set_reg: reg=%d, value=0x%08x", reg, value); 238 state->gregs[reg] = value; 239} 240 241static bool try_pop_registers(const memory_t* memory, unwind_state_t* state, uint32_t mask) { 242 uint32_t sp = state->gregs[R_SP]; 243 bool sp_updated = false; 244 for (int i = 0; i < 16; i++) { 245 if (mask & (1 << i)) { 246 uint32_t value; 247 if (!try_get_word(memory, sp, &value)) { 248 return false; 249 } 250 if (i == R_SP) { 251 sp_updated = true; 252 } 253 set_reg(state, i, value); 254 sp += 4; 255 } 256 } 257 if (!sp_updated) { 258 set_reg(state, R_SP, sp); 259 } 260 return true; 261} 262 263/* Executes a built-in personality routine as defined in the EHABI. 264 * Returns true if unwinding should continue. 265 * 266 * The data for the built-in personality routines consists of a sequence 267 * of unwinding instructions, followed by a sequence of scope descriptors, 268 * each of which has a length and offset encoded using 16-bit or 32-bit 269 * values. 270 * 271 * We only care about the unwinding instructions. They specify the 272 * operations of an abstract machine whose purpose is to transform the 273 * virtual register state (including the stack pointer) such that 274 * the call frame is unwound and the PC register points to the call site. 275 */ 276static bool execute_personality_routine(const memory_t* memory, 277 unwind_state_t* state, byte_stream_t* stream, int pr_index) { 278 size_t size; 279 switch (pr_index) { 280 case 0: // Personality routine #0, short frame, descriptors have 16-bit scope. 281 size = 3; 282 break; 283 case 1: // Personality routine #1, long frame, descriptors have 16-bit scope. 284 case 2: { // Personality routine #2, long frame, descriptors have 32-bit scope. 285 uint8_t size_byte; 286 if (!try_next_byte(memory, stream, &size_byte)) { 287 return false; 288 } 289 size = (uint32_t)size_byte * sizeof(uint32_t) + 2; 290 break; 291 } 292 default: // Unknown personality routine. Stop here. 293 return false; 294 } 295 296 bool pc_was_set = false; 297 while (size--) { 298 uint8_t op; 299 if (!try_next_byte(memory, stream, &op)) { 300 return false; 301 } 302 if ((op & 0xc0) == 0x00) { 303 // "vsp = vsp + (xxxxxx << 2) + 4" 304 set_reg(state, R_SP, state->gregs[R_SP] + ((op & 0x3f) << 2) + 4); 305 } else if ((op & 0xc0) == 0x40) { 306 // "vsp = vsp - (xxxxxx << 2) - 4" 307 set_reg(state, R_SP, state->gregs[R_SP] - ((op & 0x3f) << 2) - 4); 308 } else if ((op & 0xf0) == 0x80) { 309 uint8_t op2; 310 if (!(size--) || !try_next_byte(memory, stream, &op2)) { 311 return false; 312 } 313 uint32_t mask = (((uint32_t)op & 0x0f) << 12) | ((uint32_t)op2 << 4); 314 if (mask) { 315 // "Pop up to 12 integer registers under masks {r15-r12}, {r11-r4}" 316 if (!try_pop_registers(memory, state, mask)) { 317 return false; 318 } 319 if (mask & (1 << R_PC)) { 320 pc_was_set = true; 321 } 322 } else { 323 // "Refuse to unwind" 324 return false; 325 } 326 } else if ((op & 0xf0) == 0x90) { 327 if (op != 0x9d && op != 0x9f) { 328 // "Set vsp = r[nnnn]" 329 set_reg(state, R_SP, state->gregs[op & 0x0f]); 330 } else { 331 // "Reserved as prefix for ARM register to register moves" 332 // "Reserved as prefix for Intel Wireless MMX register to register moves" 333 return false; 334 } 335 } else if ((op & 0xf8) == 0xa0) { 336 // "Pop r4-r[4+nnn]" 337 uint32_t mask = (0x0ff0 >> (7 - (op & 0x07))) & 0x0ff0; 338 if (!try_pop_registers(memory, state, mask)) { 339 return false; 340 } 341 } else if ((op & 0xf8) == 0xa8) { 342 // "Pop r4-r[4+nnn], r14" 343 uint32_t mask = ((0x0ff0 >> (7 - (op & 0x07))) & 0x0ff0) | 0x4000; 344 if (!try_pop_registers(memory, state, mask)) { 345 return false; 346 } 347 } else if (op == 0xb0) { 348 // "Finish" 349 break; 350 } else if (op == 0xb1) { 351 uint8_t op2; 352 if (!(size--) || !try_next_byte(memory, stream, &op2)) { 353 return false; 354 } 355 if (op2 != 0x00 && (op2 & 0xf0) == 0x00) { 356 // "Pop integer registers under mask {r3, r2, r1, r0}" 357 if (!try_pop_registers(memory, state, op2)) { 358 return false; 359 } 360 } else { 361 // "Spare" 362 return false; 363 } 364 } else if (op == 0xb2) { 365 // "vsp = vsp + 0x204 + (uleb128 << 2)" 366 uint32_t value = 0; 367 uint32_t shift = 0; 368 uint8_t op2; 369 do { 370 if (!(size--) || !try_next_byte(memory, stream, &op2)) { 371 return false; 372 } 373 value |= (op2 & 0x7f) << shift; 374 shift += 7; 375 } while (op2 & 0x80); 376 set_reg(state, R_SP, state->gregs[R_SP] + (value << 2) + 0x204); 377 } else if (op == 0xb3) { 378 // "Pop VFP double-precision registers D[ssss]-D[ssss+cccc] saved (as if) by FSTMFDX" 379 uint8_t op2; 380 if (!(size--) || !try_next_byte(memory, stream, &op2)) { 381 return false; 382 } 383 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 12); 384 } else if ((op & 0xf8) == 0xb8) { 385 // "Pop VFP double-precision registers D[8]-D[8+nnn] saved (as if) by FSTMFDX" 386 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op & 0x07) * 8 + 12); 387 } else if ((op & 0xf8) == 0xc0) { 388 // "Intel Wireless MMX pop wR[10]-wR[10+nnn]" 389 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op & 0x07) * 8 + 8); 390 } else if (op == 0xc6) { 391 // "Intel Wireless MMX pop wR[ssss]-wR[ssss+cccc]" 392 uint8_t op2; 393 if (!(size--) || !try_next_byte(memory, stream, &op2)) { 394 return false; 395 } 396 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 8); 397 } else if (op == 0xc7) { 398 uint8_t op2; 399 if (!(size--) || !try_next_byte(memory, stream, &op2)) { 400 return false; 401 } 402 if (op2 != 0x00 && (op2 & 0xf0) == 0x00) { 403 // "Intel Wireless MMX pop wCGR registers under mask {wCGR3,2,1,0}" 404 set_reg(state, R_SP, state->gregs[R_SP] + __builtin_popcount(op2) * 4); 405 } else { 406 // "Spare" 407 return false; 408 } 409 } else if (op == 0xc8) { 410 // "Pop VFP double precision registers D[16+ssss]-D[16+ssss+cccc] 411 // saved (as if) by FSTMFD" 412 uint8_t op2; 413 if (!(size--) || !try_next_byte(memory, stream, &op2)) { 414 return false; 415 } 416 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 8); 417 } else if (op == 0xc9) { 418 // "Pop VFP double precision registers D[ssss]-D[ssss+cccc] saved (as if) by FSTMFDD" 419 uint8_t op2; 420 if (!(size--) || !try_next_byte(memory, stream, &op2)) { 421 return false; 422 } 423 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 8); 424 } else if ((op == 0xf8) == 0xd0) { 425 // "Pop VFP double-precision registers D[8]-D[8+nnn] saved (as if) by FSTMFDD" 426 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op & 0x07) * 8 + 8); 427 } else { 428 // "Spare" 429 return false; 430 } 431 } 432 if (!pc_was_set) { 433 set_reg(state, R_PC, state->gregs[R_LR]); 434 } 435 return true; 436} 437 438static bool try_get_half_word(const memory_t* memory, uint32_t pc, uint16_t* out_value) { 439 uint32_t word; 440 if (try_get_word(memory, pc & ~2, &word)) { 441 *out_value = pc & 2 ? word >> 16 : word & 0xffff; 442 return true; 443 } 444 return false; 445} 446 447uintptr_t rewind_pc_arch(const memory_t* memory, uintptr_t pc) { 448 if (pc & 1) { 449 /* Thumb mode - need to check whether the bl(x) has long offset or not. 450 * Examples: 451 * 452 * arm blx in the middle of thumb: 453 * 187ae: 2300 movs r3, #0 454 * 187b0: f7fe ee1c blx 173ec 455 * 187b4: 2c00 cmp r4, #0 456 * 457 * arm bl in the middle of thumb: 458 * 187d8: 1c20 adds r0, r4, #0 459 * 187da: f136 fd15 bl 14f208 460 * 187de: 2800 cmp r0, #0 461 * 462 * pure thumb: 463 * 18894: 189b adds r3, r3, r2 464 * 18896: 4798 blx r3 465 * 18898: b001 add sp, #4 466 */ 467 pc &= ~1; 468 uint16_t prev1, prev2; 469 if (try_get_half_word(memory, pc - 4, &prev1) 470 && ((prev1 & 0xf000) == 0xf000) 471 && try_get_half_word(memory, pc - 2, &prev2) 472 && ((prev2 & 0xe000) == 0xe000)) { 473 pc -= 4; // long offset 474 } else { 475 pc -= 2; 476 } 477 } else { 478 /* ARM mode, all instructions are 32bit. Yay! */ 479 pc -= 4; 480 } 481 return pc; 482} 483 484static ssize_t unwind_backtrace_common(const memory_t* memory, 485 const map_info_t* map_info_list, 486 unwind_state_t* state, backtrace_frame_t* backtrace, 487 size_t ignore_depth, size_t max_depth) { 488 size_t ignored_frames = 0; 489 size_t returned_frames = 0; 490 491 for (size_t index = 0; returned_frames < max_depth; index++) { 492 uintptr_t pc = index ? rewind_pc_arch(memory, state->gregs[R_PC]) 493 : state->gregs[R_PC]; 494 backtrace_frame_t* frame = add_backtrace_entry(pc, 495 backtrace, ignore_depth, max_depth, &ignored_frames, &returned_frames); 496 if (frame) { 497 frame->stack_top = state->gregs[R_SP]; 498 } 499 500 uintptr_t handler = get_exception_handler(memory, map_info_list, pc); 501 if (!handler) { 502 // If there is no handler for the PC and this is the first frame, 503 // then the program may have branched to an invalid address. 504 // Try starting from the LR instead, otherwise stop unwinding. 505 if (index == 0 && state->gregs[R_LR] 506 && state->gregs[R_LR] != state->gregs[R_PC]) { 507 set_reg(state, R_PC, state->gregs[R_LR]); 508 continue; 509 } else { 510 break; 511 } 512 } 513 514 byte_stream_t stream; 515 stream.ptr = handler; 516 uint8_t pr; 517 if (!try_next_byte(memory, &stream, &pr)) { 518 break; 519 } 520 if ((pr & 0xf0) != 0x80) { 521 // The first word is a place-relative pointer to a generic personality 522 // routine function. We don't support invoking such functions, so stop here. 523 break; 524 } 525 526 // The first byte indicates the personality routine to execute. 527 // Following bytes provide instructions to the personality routine. 528 if (!execute_personality_routine(memory, state, &stream, pr & 0x0f)) { 529 break; 530 } 531 if (frame && state->gregs[R_SP] > frame->stack_top) { 532 frame->stack_size = state->gregs[R_SP] - frame->stack_top; 533 } 534 if (!state->gregs[R_PC]) { 535 break; 536 } 537 } 538 539 // Ran out of frames that we could unwind using handlers. 540 // Add a final entry for the LR if it looks sane and call it good. 541 if (returned_frames < max_depth 542 && state->gregs[R_LR] 543 && state->gregs[R_LR] != state->gregs[R_PC] 544 && is_executable_map(map_info_list, state->gregs[R_LR])) { 545 // We don't know where the stack for this extra frame starts so we 546 // don't return any stack information for it. 547 add_backtrace_entry(rewind_pc_arch(memory, state->gregs[R_LR]), 548 backtrace, ignore_depth, max_depth, &ignored_frames, &returned_frames); 549 } 550 return returned_frames; 551} 552 553ssize_t unwind_backtrace_signal_arch(siginfo_t* siginfo, void* sigcontext, 554 const map_info_t* map_info_list, 555 backtrace_frame_t* backtrace, size_t ignore_depth, size_t max_depth) { 556 const ucontext_t* uc = (const ucontext_t*)sigcontext; 557 558 unwind_state_t state; 559 for (int i = 0; i < 16; i++) { 560 state.gregs[i] = uc->uc_mcontext.gregs[i]; 561 } 562 563 memory_t memory; 564 init_memory(&memory, map_info_list); 565 return unwind_backtrace_common(&memory, map_info_list, &state, 566 backtrace, ignore_depth, max_depth); 567} 568 569ssize_t unwind_backtrace_ptrace_arch(pid_t tid, const ptrace_context_t* context, 570 backtrace_frame_t* backtrace, size_t ignore_depth, size_t max_depth) { 571 struct pt_regs regs; 572 if (ptrace(PTRACE_GETREGS, tid, 0, ®s)) { 573 return -1; 574 } 575 576 unwind_state_t state; 577 for (int i = 0; i < 16; i++) { 578 state.gregs[i] = regs.uregs[i]; 579 } 580 581 memory_t memory; 582 init_memory_ptrace(&memory, tid); 583 return unwind_backtrace_common(&memory, context->map_info_list, &state, 584 backtrace, ignore_depth, max_depth); 585} 586