Commit | Line | Data |
---|---|---|
867e359b CM |
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 */ |