backtrace-arm.c revision 9524e4158fbb988b6a5e4f5be68ee10b7e4dd6d8
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 if (tid < 0) { 128 exidx_start = find_exidx(pc, &exidx_size); 129 } else { 130 const map_info_t* mi = find_map_info(context->map_info_list, pc); 131 if (mi && mi->data) { 132 const map_info_data_t* data = (const map_info_data_t*)mi->data; 133 exidx_start = data->exidx_start; 134 exidx_size = data->exidx_size; 135 } else { 136 exidx_start = 0; 137 exidx_size = 0; 138 } 139 } 140 141 // The PC points to the instruction following the branch. 142 // We want to find the exception handler entry that corresponds to the branch itself, 143 // so we offset the PC backwards into the previous instruction. 144 // ARM instructions are 4 bytes, Thumb are 2, so we just subtract two so we either 145 // end up in the middle (ARM) or at the beginning of the instruction (Thumb). 146 if (pc >= 2) { 147 pc -= 2; 148 } 149 150 uint32_t handler = 0; 151 if (exidx_start) { 152 uint32_t low = 0; 153 uint32_t high = exidx_size; 154 while (low < high) { 155 uint32_t index = (low + high) / 2; 156 uintptr_t entry = exidx_start + index * 8; 157 uint32_t entry_prel_pc; 158 if (!try_get_word(tid, entry, &entry_prel_pc)) { 159 break; 160 } 161 uintptr_t entry_pc = prel_to_absolute(entry, entry_prel_pc); 162 if (pc < entry_pc) { 163 high = index; 164 continue; 165 } 166 if (index + 1 < exidx_size) { 167 uintptr_t next_entry = entry + 8; 168 uint32_t next_entry_prel_pc; 169 if (!try_get_word(tid, next_entry, &next_entry_prel_pc)) { 170 break; 171 } 172 uintptr_t next_entry_pc = prel_to_absolute(next_entry, next_entry_prel_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(tid, 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 break; 190 } 191 } 192 LOGV("get handler: pc=0x%08x, exidx_start=0x%08x, exidx_size=%d, handler=0x%08x", 193 pc, exidx_start, exidx_size, handler); 194 return handler; 195} 196 197typedef struct { 198 uintptr_t ptr; 199 uint32_t word; 200} byte_stream_t; 201 202static bool try_next_byte(pid_t tid, byte_stream_t* stream, uint8_t* out_value) { 203 uint8_t result; 204 switch (stream->ptr & 3) { 205 case 0: 206 if (!try_get_word(tid, stream->ptr, &stream->word)) { 207 *out_value = 0; 208 return false; 209 } 210 *out_value = stream->word >> 24; 211 break; 212 213 case 1: 214 *out_value = stream->word >> 16; 215 break; 216 217 case 2: 218 *out_value = stream->word >> 8; 219 break; 220 221 default: 222 *out_value = stream->word; 223 break; 224 } 225 226 LOGV("next_byte: ptr=0x%08x, value=0x%02x", stream->ptr, *out_value); 227 stream->ptr += 1; 228 return true; 229} 230 231static void set_reg(unwind_state_t* state, uint32_t reg, uint32_t value) { 232 LOGV("set_reg: reg=%d, value=0x%08x", reg, value); 233 state->gregs[reg] = value; 234} 235 236static bool try_pop_registers(pid_t tid, unwind_state_t* state, uint32_t mask) { 237 uint32_t sp = state->gregs[R_SP]; 238 bool sp_updated = false; 239 for (int i = 0; i < 16; i++) { 240 if (mask & (1 << i)) { 241 uint32_t value; 242 if (!try_get_word(tid, sp, &value)) { 243 return false; 244 } 245 if (i == R_SP) { 246 sp_updated = true; 247 } 248 set_reg(state, i, value); 249 sp += 4; 250 } 251 } 252 if (!sp_updated) { 253 set_reg(state, R_SP, sp); 254 } 255 return true; 256} 257 258/* Executes a built-in personality routine as defined in the EHABI. 259 * Returns true if unwinding should continue. 260 * 261 * The data for the built-in personality routines consists of a sequence 262 * of unwinding instructions, followed by a sequence of scope descriptors, 263 * each of which has a length and offset encoded using 16-bit or 32-bit 264 * values. 265 * 266 * We only care about the unwinding instructions. They specify the 267 * operations of an abstract machine whose purpose is to transform the 268 * virtual register state (including the stack pointer) such that 269 * the call frame is unwound and the PC register points to the call site. 270 */ 271static bool execute_personality_routine(pid_t tid, unwind_state_t* state, 272 byte_stream_t* stream, int pr_index) { 273 size_t size; 274 switch (pr_index) { 275 case 0: // Personality routine #0, short frame, descriptors have 16-bit scope. 276 size = 3; 277 break; 278 case 1: // Personality routine #1, long frame, descriptors have 16-bit scope. 279 case 2: { // Personality routine #2, long frame, descriptors have 32-bit scope. 280 uint8_t size_byte; 281 if (!try_next_byte(tid, stream, &size_byte)) { 282 return false; 283 } 284 size = (uint32_t)size_byte * sizeof(uint32_t) + 2; 285 break; 286 } 287 default: // Unknown personality routine. Stop here. 288 return false; 289 } 290 291 bool pc_was_set = false; 292 while (size--) { 293 uint8_t op; 294 if (!try_next_byte(tid, stream, &op)) { 295 return false; 296 } 297 if ((op & 0xc0) == 0x00) { 298 // "vsp = vsp + (xxxxxx << 2) + 4" 299 set_reg(state, R_SP, state->gregs[R_SP] + ((op & 0x3f) << 2) + 4); 300 } else if ((op & 0xc0) == 0x40) { 301 // "vsp = vsp - (xxxxxx << 2) - 4" 302 set_reg(state, R_SP, state->gregs[R_SP] - ((op & 0x3f) << 2) - 4); 303 } else if ((op & 0xf0) == 0x80) { 304 uint8_t op2; 305 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 306 return false; 307 } 308 uint32_t mask = (((uint32_t)op & 0x0f) << 12) | ((uint32_t)op2 << 4); 309 if (mask) { 310 // "Pop up to 12 integer registers under masks {r15-r12}, {r11-r4}" 311 if (!try_pop_registers(tid, state, mask)) { 312 return false; 313 } 314 if (mask & (1 << R_PC)) { 315 pc_was_set = true; 316 } 317 } else { 318 // "Refuse to unwind" 319 return false; 320 } 321 } else if ((op & 0xf0) == 0x90) { 322 if (op != 0x9d && op != 0x9f) { 323 // "Set vsp = r[nnnn]" 324 set_reg(state, R_SP, state->gregs[op & 0x0f]); 325 } else { 326 // "Reserved as prefix for ARM register to register moves" 327 // "Reserved as prefix for Intel Wireless MMX register to register moves" 328 return false; 329 } 330 } else if ((op & 0xf8) == 0xa0) { 331 // "Pop r4-r[4+nnn]" 332 uint32_t mask = (0x0ff0 >> (7 - (op & 0x07))) & 0x0ff0; 333 if (!try_pop_registers(tid, state, mask)) { 334 return false; 335 } 336 } else if ((op & 0xf8) == 0xa8) { 337 // "Pop r4-r[4+nnn], r14" 338 uint32_t mask = ((0x0ff0 >> (7 - (op & 0x07))) & 0x0ff0) | 0x4000; 339 if (!try_pop_registers(tid, state, mask)) { 340 return false; 341 } 342 } else if (op == 0xb0) { 343 // "Finish" 344 break; 345 } else if (op == 0xb1) { 346 uint8_t op2; 347 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 348 return false; 349 } 350 if (op2 != 0x00 && (op2 & 0xf0) == 0x00) { 351 // "Pop integer registers under mask {r3, r2, r1, r0}" 352 if (!try_pop_registers(tid, state, op2)) { 353 return false; 354 } 355 } else { 356 // "Spare" 357 return false; 358 } 359 } else if (op == 0xb2) { 360 // "vsp = vsp + 0x204 + (uleb128 << 2)" 361 uint32_t value = 0; 362 uint32_t shift = 0; 363 uint8_t op2; 364 do { 365 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 366 return false; 367 } 368 value |= (op2 & 0x7f) << shift; 369 shift += 7; 370 } while (op2 & 0x80); 371 set_reg(state, R_SP, state->gregs[R_SP] + (value << 2) + 0x204); 372 } else if (op == 0xb3) { 373 // "Pop VFP double-precision registers D[ssss]-D[ssss+cccc] saved (as if) by FSTMFDX" 374 uint8_t op2; 375 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 376 return false; 377 } 378 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 12); 379 } else if ((op & 0xf8) == 0xb8) { 380 // "Pop VFP double-precision registers D[8]-D[8+nnn] saved (as if) by FSTMFDX" 381 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op & 0x07) * 8 + 12); 382 } else if ((op & 0xf8) == 0xc0) { 383 // "Intel Wireless MMX pop wR[10]-wR[10+nnn]" 384 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op & 0x07) * 8 + 8); 385 } else if (op == 0xc6) { 386 // "Intel Wireless MMX pop wR[ssss]-wR[ssss+cccc]" 387 uint8_t op2; 388 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 389 return false; 390 } 391 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 8); 392 } else if (op == 0xc7) { 393 uint8_t op2; 394 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 395 return false; 396 } 397 if (op2 != 0x00 && (op2 & 0xf0) == 0x00) { 398 // "Intel Wireless MMX pop wCGR registers under mask {wCGR3,2,1,0}" 399 set_reg(state, R_SP, state->gregs[R_SP] + __builtin_popcount(op2) * 4); 400 } else { 401 // "Spare" 402 return false; 403 } 404 } else if (op == 0xc8) { 405 // "Pop VFP double precision registers D[16+ssss]-D[16+ssss+cccc] 406 // saved (as if) by FSTMFD" 407 uint8_t op2; 408 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 409 return false; 410 } 411 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 8); 412 } else if (op == 0xc9) { 413 // "Pop VFP double precision registers D[ssss]-D[ssss+cccc] saved (as if) by FSTMFDD" 414 uint8_t op2; 415 if (!(size--) || !try_next_byte(tid, stream, &op2)) { 416 return false; 417 } 418 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op2 & 0x0f) * 8 + 8); 419 } else if ((op == 0xf8) == 0xd0) { 420 // "Pop VFP double-precision registers D[8]-D[8+nnn] saved (as if) by FSTMFDD" 421 set_reg(state, R_SP, state->gregs[R_SP] + (uint32_t)(op & 0x07) * 8 + 8); 422 } else { 423 // "Spare" 424 return false; 425 } 426 } 427 if (!pc_was_set) { 428 set_reg(state, R_PC, state->gregs[R_LR]); 429 } 430 return true; 431} 432 433static ssize_t unwind_backtrace_common(pid_t tid, const ptrace_context_t* context, 434 unwind_state_t* state, backtrace_frame_t* backtrace, 435 size_t ignore_depth, size_t max_depth) { 436 size_t ignored_frames = 0; 437 size_t returned_frames = 0; 438 439 uintptr_t handler = get_exception_handler(context, tid, state->gregs[R_PC]); 440 if (!handler) { 441 // If there is no handler for the PC, the program may have branched to 442 // an invalid address. Check whether we have a handler for the LR 443 // where we came from and use that instead. 444 backtrace_frame_t* frame = add_backtrace_entry(state->gregs[R_PC], backtrace, 445 ignore_depth, max_depth, &ignored_frames, &returned_frames); 446 if (frame) { 447 frame->stack_top = state->gregs[R_SP]; 448 } 449 450 handler = get_exception_handler(context, tid, state->gregs[R_LR]); 451 if (!handler) { 452 // We don't have a handler here either. Unwinding will not be possible. 453 // Return the PC and LR (if it looks sane) and call it good. 454 if (state->gregs[R_LR] && state->gregs[R_LR] != state->gregs[R_PC]) { 455 // Don't return the SP for this second frame because we don't 456 // know how big the first one is so we don't know where this 457 // one starts. 458 frame = add_backtrace_entry(state->gregs[R_LR], backtrace, 459 ignore_depth, max_depth, &ignored_frames, &returned_frames); 460 } 461 return returned_frames; 462 } 463 464 // Ok, continue from the LR. 465 set_reg(state, R_PC, state->gregs[R_LR]); 466 } 467 468 while (handler && returned_frames < max_depth) { 469 backtrace_frame_t* frame = add_backtrace_entry(state->gregs[R_PC], backtrace, 470 ignore_depth, max_depth, &ignored_frames, &returned_frames); 471 if (frame) { 472 frame->stack_top = state->gregs[R_SP]; 473 } 474 475 byte_stream_t stream; 476 stream.ptr = handler; 477 uint8_t pr; 478 if (!try_next_byte(tid, &stream, &pr)) { 479 break; 480 } 481 if ((pr & 0xf0) != 0x80) { 482 // The first word is a place-relative pointer to a generic personality 483 // routine function. We don't support invoking such functions, so stop here. 484 break; 485 } 486 487 // The first byte indicates the personality routine to execute. 488 // Following bytes provide instructions to the personality routine. 489 if (!execute_personality_routine(tid, state, &stream, pr & 0x0f)) { 490 break; 491 } 492 if (frame && state->gregs[R_SP] > frame->stack_top) { 493 frame->stack_size = state->gregs[R_SP] - frame->stack_top; 494 } 495 496 handler = get_exception_handler(context, tid, state->gregs[R_PC]); 497 } 498 return returned_frames; 499} 500 501ssize_t unwind_backtrace_signal_arch(siginfo_t* siginfo, void* sigcontext, 502 backtrace_frame_t* backtrace, size_t ignore_depth, size_t max_depth) { 503 const ucontext_t* uc = (const ucontext_t*)sigcontext; 504 505 unwind_state_t state; 506 for (int i = 0; i < 16; i++) { 507 state.gregs[i] = uc->uc_mcontext.gregs[i]; 508 } 509 510 return unwind_backtrace_common(-1, NULL, &state, backtrace, ignore_depth, max_depth); 511} 512 513ssize_t unwind_backtrace_ptrace_arch(pid_t tid, const ptrace_context_t* context, 514 backtrace_frame_t* backtrace, size_t ignore_depth, size_t max_depth) { 515 struct pt_regs regs; 516 if (ptrace(PTRACE_GETREGS, tid, 0, ®s)) { 517 return -1; 518 } 519 520 unwind_state_t state; 521 for (int i = 0; i < 16; i++) { 522 state.gregs[i] = regs.uregs[i]; 523 } 524 525 return unwind_backtrace_common(tid, context, &state, backtrace, ignore_depth, max_depth); 526} 527