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>
18 #include <asm/backtrace.h>
20 #include <arch/chip.h>
22 #include <asm/opcode-tile.h>
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
44 typedef long long bt_int_reg_t
;
46 #define OPCODE_STORE TILE_OPC_SW
47 typedef int bt_int_reg_t
;
50 /** A decoded bundle used for backtracer analysis. */
51 struct BacktraceBundle
{
52 tile_bundle_bits bits
;
54 struct tile_decoded_instruction
55 insns
[TILE_MAX_INSTRUCTIONS_PER_BUNDLE
];
59 /* This implementation only makes sense for native tools. */
60 /** Default function to read memory. */
61 static bool bt_read_memory(void *result
, VirtualAddress addr
,
62 unsigned int size
, void *extra
)
65 memcpy(result
, (const void *)addr
, size
);
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'.
74 static 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
)
83 for (i
= 0; i
< bundle
->num_insns
; i
++) {
84 const struct tile_decoded_instruction
*insn
=
87 if (insn
->opcode
->mnemonic
!= mnemonic
)
91 for (j
= 0; j
< num_operands_to_match
; j
++) {
92 if (operand_values
[j
] != insn
->operand_values
[j
]) {
105 /** Does this bundle contain an 'iret' instruction? */
106 static inline bool bt_has_iret(const struct BacktraceBundle
*bundle
)
108 return find_matching_insn(bundle
, TILE_OPC_IRET
, NULL
, 0) != NULL
;
111 /** Does this bundle contain an 'addi sp, sp, OFFSET' or
112 * 'addli sp, sp, OFFSET' instruction, and if so, what is OFFSET?
114 static bool bt_has_addi_sp(const struct BacktraceBundle
*bundle
, int *adjust
)
116 static const int vals
[2] = { TREG_SP
, TREG_SP
};
118 const struct tile_decoded_instruction
*insn
=
119 find_matching_insn(bundle
, TILE_OPC_ADDI
, vals
, 2);
121 insn
= find_matching_insn(bundle
, TILE_OPC_ADDLI
, vals
, 2);
124 insn
= find_matching_insn(bundle
, TILEGX_OPC_ADDXLI
, vals
, 2);
126 insn
= find_matching_insn(bundle
, TILEGX_OPC_ADDXI
, vals
, 2);
131 *adjust
= insn
->operand_values
[2];
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.
140 static int bt_get_info_ops(const struct BacktraceBundle
*bundle
,
141 int operands
[MAX_INFO_OPS_PER_BUNDLE
])
146 for (i
= 0; i
< bundle
->num_insns
; i
++) {
147 const struct tile_decoded_instruction
*insn
=
150 if (insn
->opcode
->mnemonic
== TILE_OPC_INFO
||
151 insn
->opcode
->mnemonic
== TILE_OPC_INFOL
) {
152 operands
[num_ops
++] = insn
->operand_values
[0];
159 /** Does this bundle contain a jrp instruction, and if so, to which
160 * register is it jumping?
162 static bool bt_has_jrp(const struct BacktraceBundle
*bundle
, int *target_reg
)
164 const struct tile_decoded_instruction
*insn
=
165 find_matching_insn(bundle
, TILE_OPC_JRP
, NULL
, 0);
169 *target_reg
= insn
->operand_values
[0];
173 /** Does this bundle modify the specified register in any way? */
174 static bool bt_modifies_reg(const struct BacktraceBundle
*bundle
, int reg
)
177 for (i
= 0; i
< bundle
->num_insns
; i
++) {
178 const struct tile_decoded_instruction
*insn
=
181 if (insn
->opcode
->implicitly_written_register
== reg
)
184 for (j
= 0; j
< insn
->opcode
->num_operands
; j
++)
185 if (insn
->operands
[j
]->is_dest_reg
&&
186 insn
->operand_values
[j
] == reg
)
193 /** Does this bundle modify sp? */
194 static inline bool bt_modifies_sp(const struct BacktraceBundle
*bundle
)
196 return bt_modifies_reg(bundle
, TREG_SP
);
199 /** Does this bundle modify lr? */
200 static inline bool bt_modifies_lr(const struct BacktraceBundle
*bundle
)
202 return bt_modifies_reg(bundle
, TREG_LR
);
205 /** Does this bundle contain the instruction 'move fp, sp'? */
206 static inline bool bt_has_move_r52_sp(const struct BacktraceBundle
*bundle
)
208 static const int vals
[2] = { 52, TREG_SP
};
209 return find_matching_insn(bundle
, TILE_OPC_MOVE
, vals
, 2) != NULL
;
212 /** Does this bundle contain a store of lr to sp? */
213 static inline bool bt_has_sw_sp_lr(const struct BacktraceBundle
*bundle
)
215 static const int vals
[2] = { TREG_SP
, TREG_LR
};
216 return find_matching_insn(bundle
, OPCODE_STORE
, vals
, 2) != NULL
;
220 /** Track moveli values placed into registers. */
221 static inline void bt_update_moveli(const struct BacktraceBundle
*bundle
,
225 for (i
= 0; i
< bundle
->num_insns
; i
++) {
226 const struct tile_decoded_instruction
*insn
=
229 if (insn
->opcode
->mnemonic
== TILEGX_OPC_MOVELI
) {
230 int reg
= insn
->operand_values
[0];
231 moveli_args
[reg
] = insn
->operand_values
[1];
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?
240 static bool bt_has_add_sp(const struct BacktraceBundle
*bundle
, int *adjust
,
243 static const int vals
[2] = { TREG_SP
, TREG_SP
};
245 const struct tile_decoded_instruction
*insn
=
246 find_matching_insn(bundle
, TILEGX_OPC_ADDX
, vals
, 2);
248 int reg
= insn
->operand_values
[2];
249 if (moveli_args
[reg
]) {
250 *adjust
= moveli_args
[reg
];
258 /** Locates the caller's PC and SP for a program starting at the
261 static 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
)
266 /* Have we explicitly decided what the sp is,
267 * rather than just the default?
269 bool sp_determined
= false;
271 /* Has any bundle seen so far modified lr? */
272 bool lr_modified
= false;
274 /* Have we seen a move from sp to fp? */
275 bool sp_moved_to_r52
= false;
277 /* Have we seen a terminating bundle? */
278 bool seen_terminating_bundle
= false;
280 /* Cut down on round-trip reading overhead by reading several
283 tile_bundle_bits prefetched_bundles
[32];
284 int num_bundles_prefetched
= 0;
289 /* Naively try to track moveli values to support addx for -m32. */
290 int moveli_args
[TILEGX_NUM_REGISTERS
] = { 0 };
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.
297 location
->sp_location
= SP_LOC_OFFSET
;
298 location
->sp_offset
= 0;
300 /* Default to having no idea where the caller PC is. */
301 location
->pc_location
= PC_LOC_UNKNOWN
;
303 /* Don't even try if the PC is not aligned. */
304 if (start_pc
% TILE_BUNDLE_ALIGNMENT_IN_BYTES
!= 0)
307 for (pc
= start_pc
;; pc
+= sizeof(tile_bundle_bits
)) {
309 struct BacktraceBundle bundle
;
310 int num_info_ops
, info_operands
[MAX_INFO_OPS_PER_BUNDLE
];
311 int one_ago
, jrp_reg
;
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.
322 unsigned int bytes_to_prefetch
= 4096 - (pc
& 4095);
323 if (bytes_to_prefetch
> sizeof prefetched_bundles
)
324 bytes_to_prefetch
= sizeof prefetched_bundles
;
326 if (!read_memory_func(prefetched_bundles
, pc
,
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.
336 location
->pc_location
= PC_LOC_IN_LR
;
340 /* Unreadable address. Give up. */
345 num_bundles_prefetched
=
346 bytes_to_prefetch
/ sizeof(tile_bundle_bits
);
349 /* Decode the next bundle. */
350 bundle
.bits
= prefetched_bundles
[next_bundle
++];
352 parse_insn_tile(bundle
.bits
, pc
, bundle
.insns
);
353 num_info_ops
= bt_get_info_ops(&bundle
, info_operands
);
355 /* First look at any one_ago info ops if they are interesting,
356 * since they should shadow any non-one-ago info ops.
358 for (one_ago
= (pc
!= start_pc
) ? 1 : 0;
359 one_ago
>= 0; one_ago
--) {
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. */
368 /* Skip info ops which are not in the
369 * "one_ago" mode we want right now.
371 if (((info_operand
& ONE_BUNDLE_AGO_FLAG
) != 0)
375 /* Clear the flag to make later checking
377 info_operand
&= ~ONE_BUNDLE_AGO_FLAG
;
379 /* Default to looking at PC_IN_LR_FLAG. */
380 if (info_operand
& PC_IN_LR_FLAG
)
381 location
->pc_location
=
384 location
->pc_location
=
387 switch (info_operand
) {
388 case CALLER_UNKNOWN_BASE
:
389 location
->pc_location
= PC_LOC_UNKNOWN
;
390 location
->sp_location
= SP_LOC_UNKNOWN
;
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
;
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
407 location
->sp_location
=
409 location
->sp_offset
=
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.
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.
433 if (bundle
.bits
== 0) {
434 /* Wacky terminating bundle. Stop looping, and hope
435 * we've already seen enough to find the caller.
441 * Try to determine caller's SP.
444 if (!sp_determined
) {
446 if (bt_has_addi_sp(&bundle
, &adjust
)
448 || bt_has_add_sp(&bundle
, &adjust
, moveli_args
)
451 location
->sp_location
= SP_LOC_OFFSET
;
454 /* We are in prolog about to adjust
456 location
->sp_offset
= 0;
458 /* We are in epilog restoring SP. */
459 location
->sp_offset
= adjust
;
462 sp_determined
= true;
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.
470 sp_moved_to_r52
= true;
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
482 location
->sp_location
=
484 location
->sp_offset
= 0;
486 /* Someone must have saved
487 * aside the caller's SP value
488 * into r52, so r52 holds the
491 location
->sp_location
=
494 sp_determined
= true;
499 /* Track moveli arguments for -m32 mode. */
500 bt_update_moveli(&bundle
, moveli_args
);
504 if (bt_has_iret(&bundle
)) {
505 /* This is a terminating bundle. */
506 seen_terminating_bundle
= true;
511 * Try to determine caller's PC.
515 has_jrp
= bt_has_jrp(&bundle
, &jrp_reg
);
517 seen_terminating_bundle
= true;
519 if (location
->pc_location
== PC_LOC_UNKNOWN
) {
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
=
527 location
->pc_location
=
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
)) {
540 void 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
)
546 CallerLocation location
;
547 VirtualAddress fp
, initial_frame_caller_pc
;
549 if (read_memory_func
== NULL
) {
550 read_memory_func
= bt_read_memory
;
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
);
557 switch (location
.sp_location
) {
568 fp
= sp
+ location
.sp_offset
;
577 /* If the frame pointer is not aligned to the basic word size
578 * something terrible happened and we should mark it as invalid.
580 if (fp
% sizeof(bt_int_reg_t
) != 0)
583 /* -1 means "don't know initial_frame_caller_pc". */
584 initial_frame_caller_pc
= -1;
586 switch (location
.pc_location
) {
593 if (lr
== 0 || lr
% TILE_BUNDLE_ALIGNMENT_IN_BYTES
!= 0) {
597 initial_frame_caller_pc
= lr
;
601 case PC_LOC_ON_STACK
:
602 /* Leave initial_frame_caller_pc as -1,
603 * meaning check the stack.
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
;
621 /* Handle the case where the register holds more bits than the VA. */
622 static bool valid_addr_reg(bt_int_reg_t reg
)
624 return ((VirtualAddress
)reg
== reg
);
627 bool backtrace_next(BacktraceIterator
*state
)
629 VirtualAddress next_fp
, next_pc
;
630 bt_int_reg_t next_frame
[2];
632 if (state
->fp
== -1) {
633 /* No parent frame. */
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
)) {
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. */
650 if (state
->initial_frame_caller_pc
!= -1) {
651 /* We must be in the initial stack frame and already know the
654 next_pc
= state
->initial_frame_caller_pc
;
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.
660 state
->initial_frame_caller_pc
= -1;
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. */
671 /* Update state to become the caller's stack frame. */
673 state
->sp
= state
->fp
;