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