arch/tile/kernel/backtrace.c

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