2 * Copyright 2010 Tilera Corporation. All Rights Reserved.
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.
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
15 #include <linux/kernel.h>
16 #include <linux/string.h>
17 #include <asm/backtrace.h>
18 #include <asm/opcode-tile.h>
22 #define tile_bundle_bits tilegx_bundle_bits
23 #define TILE_MAX_INSTRUCTIONS_PER_BUNDLE TILEGX_MAX_INSTRUCTIONS_PER_BUNDLE
24 #define TILE_BUNDLE_ALIGNMENT_IN_BYTES TILEGX_BUNDLE_ALIGNMENT_IN_BYTES
25 #define tile_decoded_instruction tilegx_decoded_instruction
26 #define tile_mnemonic tilegx_mnemonic
27 #define parse_insn_tile parse_insn_tilegx
28 #define TILE_OPC_IRET TILEGX_OPC_IRET
29 #define TILE_OPC_ADDI TILEGX_OPC_ADDI
30 #define TILE_OPC_ADDLI TILEGX_OPC_ADDLI
31 #define TILE_OPC_INFO TILEGX_OPC_INFO
32 #define TILE_OPC_INFOL TILEGX_OPC_INFOL
33 #define TILE_OPC_JRP TILEGX_OPC_JRP
34 #define TILE_OPC_MOVE TILEGX_OPC_MOVE
35 #define OPCODE_STORE TILEGX_OPC_ST
36 typedef long long bt_int_reg_t;
38 #define OPCODE_STORE TILE_OPC_SW
39 typedef int bt_int_reg_t;
42 /* A decoded bundle used for backtracer analysis. */
43 struct BacktraceBundle {
44 tile_bundle_bits bits;
46 struct tile_decoded_instruction
47 insns[TILE_MAX_INSTRUCTIONS_PER_BUNDLE];
51 /* Locates an instruction inside the given bundle that
52 * has the specified mnemonic, and whose first 'num_operands_to_match'
53 * operands exactly match those in 'operand_values'.
55 static const struct tile_decoded_instruction *find_matching_insn(
56 const struct BacktraceBundle *bundle,
57 tile_mnemonic mnemonic,
58 const int *operand_values,
59 int num_operands_to_match)
64 for (i = 0; i < bundle->num_insns; i++) {
65 const struct tile_decoded_instruction *insn =
68 if (insn->opcode->mnemonic != mnemonic)
72 for (j = 0; j < num_operands_to_match; j++) {
73 if (operand_values[j] != insn->operand_values[j]) {
86 /* Does this bundle contain an 'iret' instruction? */
87 static inline bool bt_has_iret(const struct BacktraceBundle *bundle)
89 return find_matching_insn(bundle, TILE_OPC_IRET, NULL, 0) != NULL;
92 /* Does this bundle contain an 'addi sp, sp, OFFSET' or
93 * 'addli sp, sp, OFFSET' instruction, and if so, what is OFFSET?
95 static bool bt_has_addi_sp(const struct BacktraceBundle *bundle, int *adjust)
97 static const int vals[2] = { TREG_SP, TREG_SP };
99 const struct tile_decoded_instruction *insn =
100 find_matching_insn(bundle, TILE_OPC_ADDI, vals, 2);
102 insn = find_matching_insn(bundle, TILE_OPC_ADDLI, vals, 2);
105 insn = find_matching_insn(bundle, TILEGX_OPC_ADDXLI, vals, 2);
107 insn = find_matching_insn(bundle, TILEGX_OPC_ADDXI, vals, 2);
112 *adjust = insn->operand_values[2];
116 /* Does this bundle contain any 'info OP' or 'infol OP'
117 * instruction, and if so, what are their OP? Note that OP is interpreted
118 * as an unsigned value by this code since that's what the caller wants.
119 * Returns the number of info ops found.
121 static int bt_get_info_ops(const struct BacktraceBundle *bundle,
122 int operands[MAX_INFO_OPS_PER_BUNDLE])
127 for (i = 0; i < bundle->num_insns; i++) {
128 const struct tile_decoded_instruction *insn =
131 if (insn->opcode->mnemonic == TILE_OPC_INFO ||
132 insn->opcode->mnemonic == TILE_OPC_INFOL) {
133 operands[num_ops++] = insn->operand_values[0];
140 /* Does this bundle contain a jrp instruction, and if so, to which
141 * register is it jumping?
143 static bool bt_has_jrp(const struct BacktraceBundle *bundle, int *target_reg)
145 const struct tile_decoded_instruction *insn =
146 find_matching_insn(bundle, TILE_OPC_JRP, NULL, 0);
150 *target_reg = insn->operand_values[0];
154 /* Does this bundle modify the specified register in any way? */
155 static bool bt_modifies_reg(const struct BacktraceBundle *bundle, int reg)
158 for (i = 0; i < bundle->num_insns; i++) {
159 const struct tile_decoded_instruction *insn =
162 if (insn->opcode->implicitly_written_register == reg)
165 for (j = 0; j < insn->opcode->num_operands; j++)
166 if (insn->operands[j]->is_dest_reg &&
167 insn->operand_values[j] == reg)
174 /* Does this bundle modify sp? */
175 static inline bool bt_modifies_sp(const struct BacktraceBundle *bundle)
177 return bt_modifies_reg(bundle, TREG_SP);
180 /* Does this bundle modify lr? */
181 static inline bool bt_modifies_lr(const struct BacktraceBundle *bundle)
183 return bt_modifies_reg(bundle, TREG_LR);
186 /* Does this bundle contain the instruction 'move fp, sp'? */
187 static inline bool bt_has_move_r52_sp(const struct BacktraceBundle *bundle)
189 static const int vals[2] = { 52, TREG_SP };
190 return find_matching_insn(bundle, TILE_OPC_MOVE, vals, 2) != NULL;
193 /* Does this bundle contain a store of lr to sp? */
194 static inline bool bt_has_sw_sp_lr(const struct BacktraceBundle *bundle)
196 static const int vals[2] = { TREG_SP, TREG_LR };
197 return find_matching_insn(bundle, OPCODE_STORE, vals, 2) != NULL;
201 /* Track moveli values placed into registers. */
202 static inline void bt_update_moveli(const struct BacktraceBundle *bundle,
206 for (i = 0; i < bundle->num_insns; i++) {
207 const struct tile_decoded_instruction *insn =
210 if (insn->opcode->mnemonic == TILEGX_OPC_MOVELI) {
211 int reg = insn->operand_values[0];
212 moveli_args[reg] = insn->operand_values[1];
217 /* Does this bundle contain an 'add sp, sp, reg' instruction
218 * from a register that we saw a moveli into, and if so, what
219 * is the value in the register?
221 static bool bt_has_add_sp(const struct BacktraceBundle *bundle, int *adjust,
224 static const int vals[2] = { TREG_SP, TREG_SP };
226 const struct tile_decoded_instruction *insn =
227 find_matching_insn(bundle, TILEGX_OPC_ADDX, vals, 2);
229 int reg = insn->operand_values[2];
230 if (moveli_args[reg]) {
231 *adjust = moveli_args[reg];
239 /* Locates the caller's PC and SP for a program starting at the
242 static void find_caller_pc_and_caller_sp(CallerLocation *location,
243 const unsigned long start_pc,
244 BacktraceMemoryReader read_memory_func,
245 void *read_memory_func_extra)
247 /* Have we explicitly decided what the sp is,
248 * rather than just the default?
250 bool sp_determined = false;
252 /* Has any bundle seen so far modified lr? */
253 bool lr_modified = false;
255 /* Have we seen a move from sp to fp? */
256 bool sp_moved_to_r52 = false;
258 /* Have we seen a terminating bundle? */
259 bool seen_terminating_bundle = false;
261 /* Cut down on round-trip reading overhead by reading several
264 tile_bundle_bits prefetched_bundles[32];
265 int num_bundles_prefetched = 0;
270 /* Naively try to track moveli values to support addx for -m32. */
271 int moveli_args[TILEGX_NUM_REGISTERS] = { 0 };
274 /* Default to assuming that the caller's sp is the current sp.
275 * This is necessary to handle the case where we start backtracing
276 * right at the end of the epilog.
278 location->sp_location = SP_LOC_OFFSET;
279 location->sp_offset = 0;
281 /* Default to having no idea where the caller PC is. */
282 location->pc_location = PC_LOC_UNKNOWN;
284 /* Don't even try if the PC is not aligned. */
285 if (start_pc % TILE_BUNDLE_ALIGNMENT_IN_BYTES != 0)
288 for (pc = start_pc;; pc += sizeof(tile_bundle_bits)) {
290 struct BacktraceBundle bundle;
291 int num_info_ops, info_operands[MAX_INFO_OPS_PER_BUNDLE];
292 int one_ago, jrp_reg;
295 if (next_bundle >= num_bundles_prefetched) {
296 /* Prefetch some bytes, but don't cross a page
297 * boundary since that might cause a read failure we
298 * don't care about if we only need the first few
299 * bytes. Note: we don't care what the actual page
300 * size is; using the minimum possible page size will
301 * prevent any problems.
303 unsigned int bytes_to_prefetch = 4096 - (pc & 4095);
304 if (bytes_to_prefetch > sizeof prefetched_bundles)
305 bytes_to_prefetch = sizeof prefetched_bundles;
307 if (!read_memory_func(prefetched_bundles, pc,
309 read_memory_func_extra)) {
310 if (pc == start_pc) {
311 /* The program probably called a bad
312 * address, such as a NULL pointer.
313 * So treat this as if we are at the
314 * start of the function prolog so the
315 * backtrace will show how we got here.
317 location->pc_location = PC_LOC_IN_LR;
321 /* Unreadable address. Give up. */
326 num_bundles_prefetched =
327 bytes_to_prefetch / sizeof(tile_bundle_bits);
330 /* Decode the next bundle. */
331 bundle.bits = prefetched_bundles[next_bundle++];
333 parse_insn_tile(bundle.bits, pc, bundle.insns);
334 num_info_ops = bt_get_info_ops(&bundle, info_operands);
336 /* First look at any one_ago info ops if they are interesting,
337 * since they should shadow any non-one-ago info ops.
339 for (one_ago = (pc != start_pc) ? 1 : 0;
340 one_ago >= 0; one_ago--) {
342 for (i = 0; i < num_info_ops; i++) {
343 int info_operand = info_operands[i];
344 if (info_operand < CALLER_UNKNOWN_BASE) {
345 /* Weird; reserved value, ignore it. */
349 /* Skip info ops which are not in the
350 * "one_ago" mode we want right now.
352 if (((info_operand & ONE_BUNDLE_AGO_FLAG) != 0)
356 /* Clear the flag to make later checking
358 info_operand &= ~ONE_BUNDLE_AGO_FLAG;
360 /* Default to looking at PC_IN_LR_FLAG. */
361 if (info_operand & PC_IN_LR_FLAG)
362 location->pc_location =
365 location->pc_location =
368 switch (info_operand) {
369 case CALLER_UNKNOWN_BASE:
370 location->pc_location = PC_LOC_UNKNOWN;
371 location->sp_location = SP_LOC_UNKNOWN;
374 case CALLER_SP_IN_R52_BASE:
375 case CALLER_SP_IN_R52_BASE | PC_IN_LR_FLAG:
376 location->sp_location = SP_LOC_IN_R52;
381 const unsigned int val = info_operand
382 - CALLER_SP_OFFSET_BASE;
383 const unsigned int sp_offset =
384 (val >> NUM_INFO_OP_FLAGS) * 8;
385 if (sp_offset < 32768) {
386 /* This is a properly encoded
388 location->sp_location =
390 location->sp_offset =
394 /* This looked like an SP
395 * offset, but it's outside
396 * the legal range, so this
397 * must be an unrecognized
398 * info operand. Ignore it.
407 if (seen_terminating_bundle) {
408 /* We saw a terminating bundle during the previous
409 * iteration, so we were only looking for an info op.
414 if (bundle.bits == 0) {
415 /* Wacky terminating bundle. Stop looping, and hope
416 * we've already seen enough to find the caller.
422 * Try to determine caller's SP.
425 if (!sp_determined) {
427 if (bt_has_addi_sp(&bundle, &adjust)
429 || bt_has_add_sp(&bundle, &adjust, moveli_args)
432 location->sp_location = SP_LOC_OFFSET;
435 /* We are in prolog about to adjust
437 location->sp_offset = 0;
439 /* We are in epilog restoring SP. */
440 location->sp_offset = adjust;
443 sp_determined = true;
445 if (bt_has_move_r52_sp(&bundle)) {
446 /* Maybe in prolog, creating an
447 * alloca-style frame. But maybe in
448 * the middle of a fixed-size frame
449 * clobbering r52 with SP.
451 sp_moved_to_r52 = true;
454 if (bt_modifies_sp(&bundle)) {
455 if (sp_moved_to_r52) {
456 /* We saw SP get saved into
457 * r52 earlier (or now), which
458 * must have been in the
459 * prolog, so we now know that
460 * SP is still holding the
463 location->sp_location =
465 location->sp_offset = 0;
467 /* Someone must have saved
468 * aside the caller's SP value
469 * into r52, so r52 holds the
472 location->sp_location =
475 sp_determined = true;
480 /* Track moveli arguments for -m32 mode. */
481 bt_update_moveli(&bundle, moveli_args);
485 if (bt_has_iret(&bundle)) {
486 /* This is a terminating bundle. */
487 seen_terminating_bundle = true;
492 * Try to determine caller's PC.
496 has_jrp = bt_has_jrp(&bundle, &jrp_reg);
498 seen_terminating_bundle = true;
500 if (location->pc_location == PC_LOC_UNKNOWN) {
502 if (jrp_reg == TREG_LR && !lr_modified) {
503 /* Looks like a leaf function, or else
504 * lr is already restored. */
505 location->pc_location =
508 location->pc_location =
511 } else if (bt_has_sw_sp_lr(&bundle)) {
512 /* In prolog, spilling initial lr to stack. */
513 location->pc_location = PC_LOC_IN_LR;
514 } else if (bt_modifies_lr(&bundle)) {
521 /* Initializes a backtracer to start from the given location.
523 * If the frame pointer cannot be determined it is set to -1.
525 * state: The state to be filled in.
526 * read_memory_func: A callback that reads memory.
527 * read_memory_func_extra: An arbitrary argument to read_memory_func.
528 * pc: The current PC.
529 * lr: The current value of the 'lr' register.
530 * sp: The current value of the 'sp' register.
531 * r52: The current value of the 'r52' register.
533 void backtrace_init(BacktraceIterator *state,
534 BacktraceMemoryReader read_memory_func,
535 void *read_memory_func_extra,
536 unsigned long pc, unsigned long lr,
537 unsigned long sp, unsigned long r52)
539 CallerLocation location;
540 unsigned long fp, initial_frame_caller_pc;
542 /* Find out where we are in the initial frame. */
543 find_caller_pc_and_caller_sp(&location, pc,
544 read_memory_func, read_memory_func_extra);
546 switch (location.sp_location) {
557 fp = sp + location.sp_offset;
566 /* If the frame pointer is not aligned to the basic word size
567 * something terrible happened and we should mark it as invalid.
569 if (fp % sizeof(bt_int_reg_t) != 0)
572 /* -1 means "don't know initial_frame_caller_pc". */
573 initial_frame_caller_pc = -1;
575 switch (location.pc_location) {
582 if (lr == 0 || lr % TILE_BUNDLE_ALIGNMENT_IN_BYTES != 0) {
586 initial_frame_caller_pc = lr;
590 case PC_LOC_ON_STACK:
591 /* Leave initial_frame_caller_pc as -1,
592 * meaning check the stack.
605 state->initial_frame_caller_pc = initial_frame_caller_pc;
606 state->read_memory_func = read_memory_func;
607 state->read_memory_func_extra = read_memory_func_extra;
610 /* Handle the case where the register holds more bits than the VA. */
611 static bool valid_addr_reg(bt_int_reg_t reg)
613 return ((unsigned long)reg == reg);
616 /* Advances the backtracing state to the calling frame, returning
617 * true iff successful.
619 bool backtrace_next(BacktraceIterator *state)
621 unsigned long next_fp, next_pc;
622 bt_int_reg_t next_frame[2];
624 if (state->fp == -1) {
625 /* No parent frame. */
629 /* Try to read the frame linkage data chaining to the next function. */
630 if (!state->read_memory_func(&next_frame, state->fp, sizeof next_frame,
631 state->read_memory_func_extra)) {
635 next_fp = next_frame[1];
636 if (!valid_addr_reg(next_frame[1]) ||
637 next_fp % sizeof(bt_int_reg_t) != 0) {
638 /* Caller's frame pointer is suspect, so give up. */
642 if (state->initial_frame_caller_pc != -1) {
643 /* We must be in the initial stack frame and already know the
646 next_pc = state->initial_frame_caller_pc;
648 /* Force reading stack next time, in case we were in the
649 * initial frame. We don't do this above just to paranoidly
650 * avoid changing the struct at all when we return false.
652 state->initial_frame_caller_pc = -1;
654 /* Get the caller PC from the frame linkage area. */
655 next_pc = next_frame[0];
656 if (!valid_addr_reg(next_frame[0]) || next_pc == 0 ||
657 next_pc % TILE_BUNDLE_ALIGNMENT_IN_BYTES != 0) {
658 /* The PC is suspect, so give up. */
663 /* Update state to become the caller's stack frame. */
665 state->sp = state->fp;