1/* 2 * Copyright 2010 Tilera Corporation. All Rights Reserved. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License 6 * as published by the Free Software Foundation, version 2. 7 * 8 * This program is distributed in the hope that it will be useful, but 9 * WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, GOOD TITLE or 11 * NON INFRINGEMENT. See the GNU General Public License for 12 * more details. 13 */ 14 15#include <linux/kernel.h> 16#include <linux/string.h> 17 18#include <asm/backtrace.h> 19 20#include <arch/chip.h> 21 22#include <asm/opcode-tile.h> 23 24 25#define TREG_SP 54 26#define TREG_LR 55 27 28 29#if TILE_CHIP >= 10 30#define tile_bundle_bits tilegx_bundle_bits 31#define TILE_MAX_INSTRUCTIONS_PER_BUNDLE TILEGX_MAX_INSTRUCTIONS_PER_BUNDLE 32#define TILE_BUNDLE_ALIGNMENT_IN_BYTES TILEGX_BUNDLE_ALIGNMENT_IN_BYTES 33#define tile_decoded_instruction tilegx_decoded_instruction 34#define tile_mnemonic tilegx_mnemonic 35#define parse_insn_tile parse_insn_tilegx 36#define TILE_OPC_IRET TILEGX_OPC_IRET 37#define TILE_OPC_ADDI TILEGX_OPC_ADDI 38#define TILE_OPC_ADDLI TILEGX_OPC_ADDLI 39#define TILE_OPC_INFO TILEGX_OPC_INFO 40#define TILE_OPC_INFOL TILEGX_OPC_INFOL 41#define TILE_OPC_JRP TILEGX_OPC_JRP 42#define TILE_OPC_MOVE TILEGX_OPC_MOVE 43#define OPCODE_STORE TILEGX_OPC_ST 44typedef long long bt_int_reg_t; 45#else 46#define OPCODE_STORE TILE_OPC_SW 47typedef int bt_int_reg_t; 48#endif 49 50/** A decoded bundle used for backtracer analysis. */ 51struct BacktraceBundle { 52 tile_bundle_bits bits; 53 int num_insns; 54 struct tile_decoded_instruction 55 insns[TILE_MAX_INSTRUCTIONS_PER_BUNDLE]; 56}; 57 58 59/* This implementation only makes sense for native tools. */ 60/** Default function to read memory. */ 61static bool bt_read_memory(void *result, VirtualAddress addr, 62 unsigned int size, void *extra) 63{ 64 65 memcpy(result, (const void *)addr, size); 66 return true; 67} 68 69 70/** Locates an instruction inside the given bundle that 71 * has the specified mnemonic, and whose first 'num_operands_to_match' 72 * operands exactly match those in 'operand_values'. 73 */ 74static const struct tile_decoded_instruction *find_matching_insn( 75 const struct BacktraceBundle *bundle, 76 tile_mnemonic mnemonic, 77 const int *operand_values, 78 int num_operands_to_match) 79{ 80 int i, j; 81 bool match; 82 83 for (i = 0; i < bundle->num_insns; i++) { 84 const struct tile_decoded_instruction *insn = 85 &bundle->insns[i]; 86 87 if (insn->opcode->mnemonic != mnemonic) 88 continue; 89 90 match = true; 91 for (j = 0; j < num_operands_to_match; j++) { 92 if (operand_values[j] != insn->operand_values[j]) { 93 match = false; 94 break; 95 } 96 } 97 98 if (match) 99 return insn; 100 } 101 102 return NULL; 103} 104 105/** Does this bundle contain an 'iret' instruction? */ 106static inline bool bt_has_iret(const struct BacktraceBundle *bundle) 107{ 108 return find_matching_insn(bundle, TILE_OPC_IRET, NULL, 0) != NULL; 109} 110 111/** Does this bundle contain an 'addi sp, sp, OFFSET' or 112 * 'addli sp, sp, OFFSET' instruction, and if so, what is OFFSET? 113 */ 114static bool bt_has_addi_sp(const struct BacktraceBundle *bundle, int *adjust) 115{ 116 static const int vals[2] = { TREG_SP, TREG_SP }; 117 118 const struct tile_decoded_instruction *insn = 119 find_matching_insn(bundle, TILE_OPC_ADDI, vals, 2); 120 if (insn == NULL) 121 insn = find_matching_insn(bundle, TILE_OPC_ADDLI, vals, 2); 122#if TILE_CHIP >= 10 123 if (insn == NULL) 124 insn = find_matching_insn(bundle, TILEGX_OPC_ADDXLI, vals, 2); 125 if (insn == NULL) 126 insn = find_matching_insn(bundle, TILEGX_OPC_ADDXI, vals, 2); 127#endif 128 if (insn == NULL) 129 return false; 130 131 *adjust = insn->operand_values[2]; 132 return true; 133} 134 135/** Does this bundle contain any 'info OP' or 'infol OP' 136 * instruction, and if so, what are their OP? Note that OP is interpreted 137 * as an unsigned value by this code since that's what the caller wants. 138 * Returns the number of info ops found. 139 */ 140static int bt_get_info_ops(const struct BacktraceBundle *bundle, 141 int operands[MAX_INFO_OPS_PER_BUNDLE]) 142{ 143 int num_ops = 0; 144 int i; 145 146 for (i = 0; i < bundle->num_insns; i++) { 147 const struct tile_decoded_instruction *insn = 148 &bundle->insns[i]; 149 150 if (insn->opcode->mnemonic == TILE_OPC_INFO || 151 insn->opcode->mnemonic == TILE_OPC_INFOL) { 152 operands[num_ops++] = insn->operand_values[0]; 153 } 154 } 155 156 return num_ops; 157} 158 159/** Does this bundle contain a jrp instruction, and if so, to which 160 * register is it jumping? 161 */ 162static bool bt_has_jrp(const struct BacktraceBundle *bundle, int *target_reg) 163{ 164 const struct tile_decoded_instruction *insn = 165 find_matching_insn(bundle, TILE_OPC_JRP, NULL, 0); 166 if (insn == NULL) 167 return false; 168 169 *target_reg = insn->operand_values[0]; 170 return true; 171} 172 173/** Does this bundle modify the specified register in any way? */ 174static bool bt_modifies_reg(const struct BacktraceBundle *bundle, int reg) 175{ 176 int i, j; 177 for (i = 0; i < bundle->num_insns; i++) { 178 const struct tile_decoded_instruction *insn = 179 &bundle->insns[i]; 180 181 if (insn->opcode->implicitly_written_register == reg) 182 return true; 183 184 for (j = 0; j < insn->opcode->num_operands; j++) 185 if (insn->operands[j]->is_dest_reg && 186 insn->operand_values[j] == reg) 187 return true; 188 } 189 190 return false; 191} 192 193/** Does this bundle modify sp? */ 194static inline bool bt_modifies_sp(const struct BacktraceBundle *bundle) 195{ 196 return bt_modifies_reg(bundle, TREG_SP); 197} 198 199/** Does this bundle modify lr? */ 200static inline bool bt_modifies_lr(const struct BacktraceBundle *bundle) 201{ 202 return bt_modifies_reg(bundle, TREG_LR); 203} 204 205/** Does this bundle contain the instruction 'move fp, sp'? */ 206static inline bool bt_has_move_r52_sp(const struct BacktraceBundle *bundle) 207{ 208 static const int vals[2] = { 52, TREG_SP }; 209 return find_matching_insn(bundle, TILE_OPC_MOVE, vals, 2) != NULL; 210} 211 212/** Does this bundle contain a store of lr to sp? */ 213static inline bool bt_has_sw_sp_lr(const struct BacktraceBundle *bundle) 214{ 215 static const int vals[2] = { TREG_SP, TREG_LR }; 216 return find_matching_insn(bundle, OPCODE_STORE, vals, 2) != NULL; 217} 218 219#if TILE_CHIP >= 10 220/** Track moveli values placed into registers. */ 221static inline void bt_update_moveli(const struct BacktraceBundle *bundle, 222 int moveli_args[]) 223{ 224 int i; 225 for (i = 0; i < bundle->num_insns; i++) { 226 const struct tile_decoded_instruction *insn = 227 &bundle->insns[i]; 228 229 if (insn->opcode->mnemonic == TILEGX_OPC_MOVELI) { 230 int reg = insn->operand_values[0]; 231 moveli_args[reg] = insn->operand_values[1]; 232 } 233 } 234} 235 236/** Does this bundle contain an 'add sp, sp, reg' instruction 237 * from a register that we saw a moveli into, and if so, what 238 * is the value in the register? 239 */ 240static bool bt_has_add_sp(const struct BacktraceBundle *bundle, int *adjust, 241 int moveli_args[]) 242{ 243 static const int vals[2] = { TREG_SP, TREG_SP }; 244 245 const struct tile_decoded_instruction *insn = 246 find_matching_insn(bundle, TILEGX_OPC_ADDX, vals, 2); 247 if (insn) { 248 int reg = insn->operand_values[2]; 249 if (moveli_args[reg]) { 250 *adjust = moveli_args[reg]; 251 return true; 252 } 253 } 254 return false; 255} 256#endif 257 258/** Locates the caller's PC and SP for a program starting at the 259 * given address. 260 */ 261static void find_caller_pc_and_caller_sp(CallerLocation *location, 262 const VirtualAddress start_pc, 263 BacktraceMemoryReader read_memory_func, 264 void *read_memory_func_extra) 265{ 266 /* Have we explicitly decided what the sp is, 267 * rather than just the default? 268 */ 269 bool sp_determined = false; 270 271 /* Has any bundle seen so far modified lr? */ 272 bool lr_modified = false; 273 274 /* Have we seen a move from sp to fp? */ 275 bool sp_moved_to_r52 = false; 276 277 /* Have we seen a terminating bundle? */ 278 bool seen_terminating_bundle = false; 279 280 /* Cut down on round-trip reading overhead by reading several 281 * bundles at a time. 282 */ 283 tile_bundle_bits prefetched_bundles[32]; 284 int num_bundles_prefetched = 0; 285 int next_bundle = 0; 286 VirtualAddress pc; 287 288#if TILE_CHIP >= 10 289 /* Naively try to track moveli values to support addx for -m32. */ 290 int moveli_args[TILEGX_NUM_REGISTERS] = { 0 }; 291#endif 292 293 /* Default to assuming that the caller's sp is the current sp. 294 * This is necessary to handle the case where we start backtracing 295 * right at the end of the epilog. 296 */ 297 location->sp_location = SP_LOC_OFFSET; 298 location->sp_offset = 0; 299 300 /* Default to having no idea where the caller PC is. */ 301 location->pc_location = PC_LOC_UNKNOWN; 302 303 /* Don't even try if the PC is not aligned. */ 304 if (start_pc % TILE_BUNDLE_ALIGNMENT_IN_BYTES != 0) 305 return; 306 307 for (pc = start_pc;; pc += sizeof(tile_bundle_bits)) { 308 309 struct BacktraceBundle bundle; 310 int num_info_ops, info_operands[MAX_INFO_OPS_PER_BUNDLE]; 311 int one_ago, jrp_reg; 312 bool has_jrp; 313 314 if (next_bundle >= num_bundles_prefetched) { 315 /* Prefetch some bytes, but don't cross a page 316 * boundary since that might cause a read failure we 317 * don't care about if we only need the first few 318 * bytes. Note: we don't care what the actual page 319 * size is; using the minimum possible page size will 320 * prevent any problems. 321 */ 322 unsigned int bytes_to_prefetch = 4096 - (pc & 4095); 323 if (bytes_to_prefetch > sizeof prefetched_bundles) 324 bytes_to_prefetch = sizeof prefetched_bundles; 325 326 if (!read_memory_func(prefetched_bundles, pc, 327 bytes_to_prefetch, 328 read_memory_func_extra)) { 329 if (pc == start_pc) { 330 /* The program probably called a bad 331 * address, such as a NULL pointer. 332 * So treat this as if we are at the 333 * start of the function prolog so the 334 * backtrace will show how we got here. 335 */ 336 location->pc_location = PC_LOC_IN_LR; 337 return; 338 } 339 340 /* Unreadable address. Give up. */ 341 break; 342 } 343 344 next_bundle = 0; 345 num_bundles_prefetched = 346 bytes_to_prefetch / sizeof(tile_bundle_bits); 347 } 348 349 /* Decode the next bundle. */ 350 bundle.bits = prefetched_bundles[next_bundle++]; 351 bundle.num_insns = 352 parse_insn_tile(bundle.bits, pc, bundle.insns); 353 num_info_ops = bt_get_info_ops(&bundle, info_operands); 354 355 /* First look at any one_ago info ops if they are interesting, 356 * since they should shadow any non-one-ago info ops. 357 */ 358 for (one_ago = (pc != start_pc) ? 1 : 0; 359 one_ago >= 0; one_ago--) { 360 int i; 361 for (i = 0; i < num_info_ops; i++) { 362 int info_operand = info_operands[i]; 363 if (info_operand < CALLER_UNKNOWN_BASE) { 364 /* Weird; reserved value, ignore it. */ 365 continue; 366 } 367 368 /* Skip info ops which are not in the 369 * "one_ago" mode we want right now. 370 */ 371 if (((info_operand & ONE_BUNDLE_AGO_FLAG) != 0) 372 != (one_ago != 0)) 373 continue; 374 375 /* Clear the flag to make later checking 376 * easier. */ 377 info_operand &= ~ONE_BUNDLE_AGO_FLAG; 378 379 /* Default to looking at PC_IN_LR_FLAG. */ 380 if (info_operand & PC_IN_LR_FLAG) 381 location->pc_location = 382 PC_LOC_IN_LR; 383 else 384 location->pc_location = 385 PC_LOC_ON_STACK; 386 387 switch (info_operand) { 388 case CALLER_UNKNOWN_BASE: 389 location->pc_location = PC_LOC_UNKNOWN; 390 location->sp_location = SP_LOC_UNKNOWN; 391 return; 392 393 case CALLER_SP_IN_R52_BASE: 394 case CALLER_SP_IN_R52_BASE | PC_IN_LR_FLAG: 395 location->sp_location = SP_LOC_IN_R52; 396 return; 397 398 default: 399 { 400 const unsigned int val = info_operand 401 - CALLER_SP_OFFSET_BASE; 402 const unsigned int sp_offset = 403 (val >> NUM_INFO_OP_FLAGS) * 8; 404 if (sp_offset < 32768) { 405 /* This is a properly encoded 406 * SP offset. */ 407 location->sp_location = 408 SP_LOC_OFFSET; 409 location->sp_offset = 410 sp_offset; 411 return; 412 } else { 413 /* This looked like an SP 414 * offset, but it's outside 415 * the legal range, so this 416 * must be an unrecognized 417 * info operand. Ignore it. 418 */ 419 } 420 } 421 break; 422 } 423 } 424 } 425 426 if (seen_terminating_bundle) { 427 /* We saw a terminating bundle during the previous 428 * iteration, so we were only looking for an info op. 429 */ 430 break; 431 } 432 433 if (bundle.bits == 0) { 434 /* Wacky terminating bundle. Stop looping, and hope 435 * we've already seen enough to find the caller. 436 */ 437 break; 438 } 439 440 /* 441 * Try to determine caller's SP. 442 */ 443 444 if (!sp_determined) { 445 int adjust; 446 if (bt_has_addi_sp(&bundle, &adjust) 447#if TILE_CHIP >= 10 448 || bt_has_add_sp(&bundle, &adjust, moveli_args) 449#endif 450 ) { 451 location->sp_location = SP_LOC_OFFSET; 452 453 if (adjust <= 0) { 454 /* We are in prolog about to adjust 455 * SP. */ 456 location->sp_offset = 0; 457 } else { 458 /* We are in epilog restoring SP. */ 459 location->sp_offset = adjust; 460 } 461 462 sp_determined = true; 463 } else { 464 if (bt_has_move_r52_sp(&bundle)) { 465 /* Maybe in prolog, creating an 466 * alloca-style frame. But maybe in 467 * the middle of a fixed-size frame 468 * clobbering r52 with SP. 469 */ 470 sp_moved_to_r52 = true; 471 } 472 473 if (bt_modifies_sp(&bundle)) { 474 if (sp_moved_to_r52) { 475 /* We saw SP get saved into 476 * r52 earlier (or now), which 477 * must have been in the 478 * prolog, so we now know that 479 * SP is still holding the 480 * caller's sp value. 481 */ 482 location->sp_location = 483 SP_LOC_OFFSET; 484 location->sp_offset = 0; 485 } else { 486 /* Someone must have saved 487 * aside the caller's SP value 488 * into r52, so r52 holds the 489 * current value. 490 */ 491 location->sp_location = 492 SP_LOC_IN_R52; 493 } 494 sp_determined = true; 495 } 496 } 497 498#if TILE_CHIP >= 10 499 /* Track moveli arguments for -m32 mode. */ 500 bt_update_moveli(&bundle, moveli_args); 501#endif 502 } 503 504 if (bt_has_iret(&bundle)) { 505 /* This is a terminating bundle. */ 506 seen_terminating_bundle = true; 507 continue; 508 } 509 510 /* 511 * Try to determine caller's PC. 512 */ 513 514 jrp_reg = -1; 515 has_jrp = bt_has_jrp(&bundle, &jrp_reg); 516 if (has_jrp) 517 seen_terminating_bundle = true; 518 519 if (location->pc_location == PC_LOC_UNKNOWN) { 520 if (has_jrp) { 521 if (jrp_reg == TREG_LR && !lr_modified) { 522 /* Looks like a leaf function, or else 523 * lr is already restored. */ 524 location->pc_location = 525 PC_LOC_IN_LR; 526 } else { 527 location->pc_location = 528 PC_LOC_ON_STACK; 529 } 530 } else if (bt_has_sw_sp_lr(&bundle)) { 531 /* In prolog, spilling initial lr to stack. */ 532 location->pc_location = PC_LOC_IN_LR; 533 } else if (bt_modifies_lr(&bundle)) { 534 lr_modified = true; 535 } 536 } 537 } 538} 539 540void backtrace_init(BacktraceIterator *state, 541 BacktraceMemoryReader read_memory_func, 542 void *read_memory_func_extra, 543 VirtualAddress pc, VirtualAddress lr, 544 VirtualAddress sp, VirtualAddress r52) 545{ 546 CallerLocation location; 547 VirtualAddress fp, initial_frame_caller_pc; 548 549 if (read_memory_func == NULL) { 550 read_memory_func = bt_read_memory; 551 } 552 553 /* Find out where we are in the initial frame. */ 554 find_caller_pc_and_caller_sp(&location, pc, 555 read_memory_func, read_memory_func_extra); 556 557 switch (location.sp_location) { 558 case SP_LOC_UNKNOWN: 559 /* Give up. */ 560 fp = -1; 561 break; 562 563 case SP_LOC_IN_R52: 564 fp = r52; 565 break; 566 567 case SP_LOC_OFFSET: 568 fp = sp + location.sp_offset; 569 break; 570 571 default: 572 /* Give up. */ 573 fp = -1; 574 break; 575 } 576 577 /* If the frame pointer is not aligned to the basic word size 578 * something terrible happened and we should mark it as invalid. 579 */ 580 if (fp % sizeof(bt_int_reg_t) != 0) 581 fp = -1; 582 583 /* -1 means "don't know initial_frame_caller_pc". */ 584 initial_frame_caller_pc = -1; 585 586 switch (location.pc_location) { 587 case PC_LOC_UNKNOWN: 588 /* Give up. */ 589 fp = -1; 590 break; 591 592 case PC_LOC_IN_LR: 593 if (lr == 0 || lr % TILE_BUNDLE_ALIGNMENT_IN_BYTES != 0) { 594 /* Give up. */ 595 fp = -1; 596 } else { 597 initial_frame_caller_pc = lr; 598 } 599 break; 600 601 case PC_LOC_ON_STACK: 602 /* Leave initial_frame_caller_pc as -1, 603 * meaning check the stack. 604 */ 605 break; 606 607 default: 608 /* Give up. */ 609 fp = -1; 610 break; 611 } 612 613 state->pc = pc; 614 state->sp = sp; 615 state->fp = fp; 616 state->initial_frame_caller_pc = initial_frame_caller_pc; 617 state->read_memory_func = read_memory_func; 618 state->read_memory_func_extra = read_memory_func_extra; 619} 620 621/* Handle the case where the register holds more bits than the VA. */ 622static bool valid_addr_reg(bt_int_reg_t reg) 623{ 624 return ((VirtualAddress)reg == reg); 625} 626 627bool backtrace_next(BacktraceIterator *state) 628{ 629 VirtualAddress next_fp, next_pc; 630 bt_int_reg_t next_frame[2]; 631 632 if (state->fp == -1) { 633 /* No parent frame. */ 634 return false; 635 } 636 637 /* Try to read the frame linkage data chaining to the next function. */ 638 if (!state->read_memory_func(&next_frame, state->fp, sizeof next_frame, 639 state->read_memory_func_extra)) { 640 return false; 641 } 642 643 next_fp = next_frame[1]; 644 if (!valid_addr_reg(next_frame[1]) || 645 next_fp % sizeof(bt_int_reg_t) != 0) { 646 /* Caller's frame pointer is suspect, so give up. */ 647 return false; 648 } 649 650 if (state->initial_frame_caller_pc != -1) { 651 /* We must be in the initial stack frame and already know the 652 * caller PC. 653 */ 654 next_pc = state->initial_frame_caller_pc; 655 656 /* Force reading stack next time, in case we were in the 657 * initial frame. We don't do this above just to paranoidly 658 * avoid changing the struct at all when we return false. 659 */ 660 state->initial_frame_caller_pc = -1; 661 } else { 662 /* Get the caller PC from the frame linkage area. */ 663 next_pc = next_frame[0]; 664 if (!valid_addr_reg(next_frame[0]) || next_pc == 0 || 665 next_pc % TILE_BUNDLE_ALIGNMENT_IN_BYTES != 0) { 666 /* The PC is suspect, so give up. */ 667 return false; 668 } 669 } 670 671 /* Update state to become the caller's stack frame. */ 672 state->pc = next_pc; 673 state->sp = state->fp; 674 state->fp = next_fp; 675 676 return true; 677} 678