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