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