diff options
Diffstat (limited to 'arch/tile/kernel/backtrace.c')
| -rw-r--r-- | arch/tile/kernel/backtrace.c | 682 |
1 files changed, 682 insertions, 0 deletions
diff --git a/arch/tile/kernel/backtrace.c b/arch/tile/kernel/backtrace.c new file mode 100644 index 00000000000..d3c41c1ff6b --- /dev/null +++ b/arch/tile/kernel/backtrace.c @@ -0,0 +1,682 @@ +/* + * Copyright 2010 Tilera Corporation. All Rights Reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation, version 2. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, GOOD TITLE or + * NON INFRINGEMENT. See the GNU General Public License for + * more details. + */ + +#include <linux/kernel.h> +#include <linux/string.h> + +#include <asm/backtrace.h> + +#include <arch/chip.h> + +#include <asm/opcode-tile.h> + + +#define TREG_SP 54 +#define TREG_LR 55 + + +#if TILE_CHIP >= 10 +#define tile_bundle_bits tilegx_bundle_bits +#define TILE_MAX_INSTRUCTIONS_PER_BUNDLE TILEGX_MAX_INSTRUCTIONS_PER_BUNDLE +#define TILE_BUNDLE_ALIGNMENT_IN_BYTES TILEGX_BUNDLE_ALIGNMENT_IN_BYTES +#define tile_decoded_instruction tilegx_decoded_instruction +#define tile_mnemonic tilegx_mnemonic +#define parse_insn_tile parse_insn_tilegx +#define TILE_OPC_IRET TILEGX_OPC_IRET +#define TILE_OPC_ADDI TILEGX_OPC_ADDI +#define TILE_OPC_ADDLI TILEGX_OPC_ADDLI +#define TILE_OPC_INFO TILEGX_OPC_INFO +#define TILE_OPC_INFOL TILEGX_OPC_INFOL +#define TILE_OPC_JRP TILEGX_OPC_JRP +#define TILE_OPC_MOVE TILEGX_OPC_MOVE +#define OPCODE_STORE TILEGX_OPC_ST +typedef long long bt_int_reg_t; +#else +#define OPCODE_STORE TILE_OPC_SW +typedef int bt_int_reg_t; +#endif + +/** A decoded bundle used for backtracer analysis. */ +struct BacktraceBundle { + tile_bundle_bits bits; + int num_insns; + struct tile_decoded_instruction + insns[TILE_MAX_INSTRUCTIONS_PER_BUNDLE]; +}; + + +/* This implementation only makes sense for native tools. */ +/** Default function to read memory. */ +static bool bt_read_memory(void *result, VirtualAddress addr, + unsigned int size, void *extra) +{ + /* FIXME: this should do some horrible signal stuff to catch + * SEGV cleanly and fail. + * + * Or else the caller should do the setjmp for efficiency. + */ + + memcpy(result, (const void *)addr, size); + return true; +} + + +/** Locates an instruction inside the given bundle that + * has the specified mnemonic, and whose first 'num_operands_to_match' + * operands exactly match those in 'operand_values'. + */ +static const struct tile_decoded_instruction *find_matching_insn( + const struct BacktraceBundle *bundle, + tile_mnemonic mnemonic, + const int *operand_values, + int num_operands_to_match) +{ + int i, j; + bool match; + + for (i = 0; i < bundle->num_insns; i++) { + const struct tile_decoded_instruction *insn = + &bundle->insns[i]; + + if (insn->opcode->mnemonic != mnemonic) + continue; + + match = true; + for (j = 0; j < num_operands_to_match; j++) { + if (operand_values[j] != insn->operand_values[j]) { + match = false; + break; + } + } + + if (match) + return insn; + } + + return NULL; +} + +/** Does this bundle contain an 'iret' instruction? */ +static inline bool bt_has_iret(const struct BacktraceBundle *bundle) +{ + return find_matching_insn(bundle, TILE_OPC_IRET, NULL, 0) != NULL; +} + +/** Does this bundle contain an 'addi sp, sp, OFFSET' or + * 'addli sp, sp, OFFSET' instruction, and if so, what is OFFSET? + */ +static bool bt_has_addi_sp(const struct BacktraceBundle *bundle, int *adjust) +{ + static const int vals[2] = { TREG_SP, TREG_SP }; + + const struct tile_decoded_instruction *insn = + find_matching_insn(bundle, TILE_OPC_ADDI, vals, 2); + if (insn == NULL) + insn = find_matching_insn(bundle, TILE_OPC_ADDLI, vals, 2); +#if TILE_CHIP >= 10 + if (insn == NULL) + insn = find_matching_insn(bundle, TILEGX_OPC_ADDXLI, vals, 2); + if (insn == NULL) + insn = find_matching_insn(bundle, TILEGX_OPC_ADDXI, vals, 2); +#endif + if (insn == NULL) + return false; + + *adjust = insn->operand_values[2]; + return true; +} + +/** Does this bundle contain any 'info OP' or 'infol OP' + * instruction, and if so, what are their OP? Note that OP is interpreted + * as an unsigned value by this code since that's what the caller wants. + * Returns the number of info ops found. + */ +static int bt_get_info_ops(const struct BacktraceBundle *bundle, + int operands[MAX_INFO_OPS_PER_BUNDLE]) +{ + int num_ops = 0; + int i; + + for (i = 0; i < bundle->num_insns; i++) { + const struct tile_decoded_instruction *insn = + &bundle->insns[i]; + + if (insn->opcode->mnemonic == TILE_OPC_INFO || + insn->opcode->mnemonic == TILE_OPC_INFOL) { + operands[num_ops++] = insn->operand_values[0]; + } + } + + return num_ops; +} + +/** Does this bundle contain a jrp instruction, and if so, to which + * register is it jumping? + */ +static bool bt_has_jrp(const struct BacktraceBundle *bundle, int *target_reg) +{ + const struct tile_decoded_instruction *insn = + find_matching_insn(bundle, TILE_OPC_JRP, NULL, 0); + if (insn == NULL) + return false; + + *target_reg = insn->operand_values[0]; + return true; +} + +/** Does this bundle modify the specified register in any way? */ +static bool bt_modifies_reg(const struct BacktraceBundle *bundle, int reg) +{ + int i, j; + for (i = 0; i < bundle->num_insns; i++) { + const struct tile_decoded_instruction *insn = + &bundle->insns[i]; + + if (insn->opcode->implicitly_written_register == reg) + return true; + + for (j = 0; j < insn->opcode->num_operands; j++) + if (insn->operands[j]->is_dest_reg && + insn->operand_values[j] == reg) + return true; + } + + return false; +} + +/** Does this bundle modify sp? */ +static inline bool bt_modifies_sp(const struct BacktraceBundle *bundle) +{ + return bt_modifies_reg(bundle, TREG_SP); +} + +/** Does this bundle modify lr? */ +static inline bool bt_modifies_lr(const struct BacktraceBundle *bundle) +{ + return bt_modifies_reg(bundle, TREG_LR); +} + +/** Does this bundle contain the instruction 'move fp, sp'? */ +static inline bool bt_has_move_r52_sp(const struct BacktraceBundle *bundle) +{ + static const int vals[2] = { 52, TREG_SP }; + return find_matching_insn(bundle, TILE_OPC_MOVE, vals, 2) != NULL; +} + +/** Does this bundle contain a store of lr to sp? */ +static inline bool bt_has_sw_sp_lr(const struct BacktraceBundle *bundle) +{ + static const int vals[2] = { TREG_SP, TREG_LR }; + return find_matching_insn(bundle, OPCODE_STORE, vals, 2) != NULL; +} + +#if TILE_CHIP >= 10 +/** Track moveli values placed into registers. */ +static inline void bt_update_moveli(const struct BacktraceBundle *bundle, + int moveli_args[]) +{ + int i; + for (i = 0; i < bundle->num_insns; i++) { + const struct tile_decoded_instruction *insn = + &bundle->insns[i]; + + if (insn->opcode->mnemonic == TILEGX_OPC_MOVELI) { + int reg = insn->operand_values[0]; + moveli_args[reg] = insn->operand_values[1]; + } + } +} + +/** Does this bundle contain an 'add sp, sp, reg' instruction + * from a register that we saw a moveli into, and if so, what + * is the value in the register? + */ +static bool bt_has_add_sp(const struct BacktraceBundle *bundle, int *adjust, + int moveli_args[]) +{ + static const int vals[2] = { TREG_SP, TREG_SP }; + + const struct tile_decoded_instruction *insn = + find_matching_insn(bundle, TILEGX_OPC_ADDX, vals, 2); + if (insn) { + int reg = insn->operand_values[2]; + if (moveli_args[reg]) { + *adjust = moveli_args[reg]; + return true; + } + } + return false; +} +#endif + +/** Locates the caller's PC and SP for a program starting at the + * given address. + */ +static void find_caller_pc_and_caller_sp(CallerLocation *location, + const VirtualAddress start_pc, + BacktraceMemoryReader read_memory_func, + void *read_memory_func_extra) +{ + /* Have we explicitly decided what the sp is, + * rather than just the default? + */ + bool sp_determined = false; + + /* Has any bundle seen so far modified lr? */ + bool lr_modified = false; + + /* Have we seen a move from sp to fp? */ + bool sp_moved_to_r52 = false; + + /* Have we seen a terminating bundle? */ + bool seen_terminating_bundle = false; + + /* Cut down on round-trip reading overhead by reading several + * bundles at a time. + */ + tile_bundle_bits prefetched_bundles[32]; + int num_bundles_prefetched = 0; + int next_bundle = 0; + VirtualAddress pc; + +#if TILE_CHIP >= 10 + /* Naively try to track moveli values to support addx for -m32. */ + int moveli_args[TILEGX_NUM_REGISTERS] = { 0 }; +#endif + + /* Default to assuming that the caller's sp is the current sp. + * This is necessary to handle the case where we start backtracing + * right at the end of the epilog. + */ + location->sp_location = SP_LOC_OFFSET; + location->sp_offset = 0; + + /* Default to having no idea where the caller PC is. */ + location->pc_location = PC_LOC_UNKNOWN; + + /* Don't even try if the PC is not aligned. */ + if (start_pc % TILE_BUNDLE_ALIGNMENT_IN_BYTES != 0) + return; + + for (pc = start_pc;; pc += sizeof(tile_bundle_bits)) { + + struct BacktraceBundle bundle; + int num_info_ops, info_operands[MAX_INFO_OPS_PER_BUNDLE]; + int one_ago, jrp_reg; + bool has_jrp; + + if (next_bundle >= num_bundles_prefetched) { + /* Prefetch some bytes, but don't cross a page + * boundary since that might cause a read failure we + * don't care about if we only need the first few + * bytes. Note: we don't care what the actual page + * size is; using the minimum possible page size will + * prevent any problems. + */ + unsigned int bytes_to_prefetch = 4096 - (pc & 4095); + if (bytes_to_prefetch > sizeof prefetched_bundles) + bytes_to_prefetch = sizeof prefetched_bundles; + + if (!read_memory_func(prefetched_bundles, pc, + bytes_to_prefetch, + read_memory_func_extra)) { + if (pc == start_pc) { + /* The program probably called a bad + * address, such as a NULL pointer. + * So treat this as if we are at the + * start of the function prolog so the + * backtrace will show how we got here. + */ + location->pc_location = PC_LOC_IN_LR; + return; + } + + /* Unreadable address. Give up. */ + break; + } + + next_bundle = 0; + num_bundles_prefetched = + bytes_to_prefetch / sizeof(tile_bundle_bits); + } + + /* Decode the next bundle. */ + bundle.bits = prefetched_bundles[next_bundle++]; + bundle.num_insns = + parse_insn_tile(bundle.bits, pc, bundle.insns); + num_info_ops = bt_get_info_ops(&bundle, info_operands); + + /* First look at any one_ago info ops if they are interesting, + * since they should shadow any non-one-ago info ops. + */ + for (one_ago = (pc != start_pc) ? 1 : 0; + one_ago >= 0; one_ago--) { + int i; + for (i = 0; i < num_info_ops; i++) { + int info_operand = info_operands[i]; + if (info_operand < CALLER_UNKNOWN_BASE) { + /* Weird; reserved value, ignore it. */ + continue; + } + + /* Skip info ops which are not in the + * "one_ago" mode we want right now. + */ + if (((info_operand & ONE_BUNDLE_AGO_FLAG) != 0) + != (one_ago != 0)) + continue; + + /* Clear the flag to make later checking + * easier. */ + info_operand &= ~ONE_BUNDLE_AGO_FLAG; + + /* Default to looking at PC_IN_LR_FLAG. */ + if (info_operand & PC_IN_LR_FLAG) + location->pc_location = + PC_LOC_IN_LR; + else + location->pc_location = + PC_LOC_ON_STACK; + + switch (info_operand) { + case CALLER_UNKNOWN_BASE: + location->pc_location = PC_LOC_UNKNOWN; + location->sp_location = SP_LOC_UNKNOWN; + return; + + case CALLER_SP_IN_R52_BASE: + case CALLER_SP_IN_R52_BASE | PC_IN_LR_FLAG: + location->sp_location = SP_LOC_IN_R52; + return; + + default: + { + const unsigned int val = info_operand + - CALLER_SP_OFFSET_BASE; + const unsigned int sp_offset = + (val >> NUM_INFO_OP_FLAGS) * 8; + if (sp_offset < 32768) { + /* This is a properly encoded + * SP offset. */ + location->sp_location = + SP_LOC_OFFSET; + location->sp_offset = + sp_offset; + return; + } else { + /* This looked like an SP + * offset, but it's outside + * the legal range, so this + * must be an unrecognized + * info operand. Ignore it. + */ + } + } + break; + } + } + } + + if (seen_terminating_bundle) { + /* We saw a terminating bundle during the previous + * iteration, so we were only looking for an info op. + */ + break; + } + + if (bundle.bits == 0) { + /* Wacky terminating bundle. Stop looping, and hope + * we've already seen enough to find the caller. + */ + break; + } + + /* + * Try to determine caller's SP. + */ + + if (!sp_determined) { + int adjust; + if (bt_has_addi_sp(&bundle, &adjust) +#if TILE_CHIP >= 10 + || bt_has_add_sp(&bundle, &adjust, moveli_args) +#endif + ) { + location->sp_location = SP_LOC_OFFSET; + + if (adjust <= 0) { + /* We are in prolog about to adjust + * SP. */ + location->sp_offset = 0; + } else { + /* We are in epilog restoring SP. */ + location->sp_offset = adjust; + } + + sp_determined = true; + } else { + if (bt_has_move_r52_sp(&bundle)) { + /* Maybe in prolog, creating an + * alloca-style frame. But maybe in + * the middle of a fixed-size frame + * clobbering r52 with SP. + */ + sp_moved_to_r52 = true; + } + + if (bt_modifies_sp(&bundle)) { + if (sp_moved_to_r52) { + /* We saw SP get saved into + * r52 earlier (or now), which + * must have been in the + * prolog, so we now know that + * SP is still holding the + * caller's sp value. + */ + location->sp_location = + SP_LOC_OFFSET; + location->sp_offset = 0; + } else { + /* Someone must have saved + * aside the caller's SP value + * into r52, so r52 holds the + * current value. + */ + location->sp_location = + SP_LOC_IN_R52; + } + sp_determined = true; + } + } + +#if TILE_CHIP >= 10 + /* Track moveli arguments for -m32 mode. */ + bt_update_moveli(&bundle, moveli_args); +#endif + } + + if (bt_has_iret(&bundle)) { + /* This is a terminating bundle. */ + seen_terminating_bundle = true; + continue; + } + + /* + * Try to determine caller's PC. + */ + + jrp_reg = -1; + has_jrp = bt_has_jrp(&bundle, &jrp_reg); + if (has_jrp) + seen_terminating_bundle = true; + + if (location->pc_location == PC_LOC_UNKNOWN) { + if (has_jrp) { + if (jrp_reg == TREG_LR && !lr_modified) { + /* Looks like a leaf function, or else + * lr is already restored. */ + location->pc_location = + PC_LOC_IN_LR; + } else { + location->pc_location = + PC_LOC_ON_STACK; + } + } else if (bt_has_sw_sp_lr(&bundle)) { + /* In prolog, spilling initial lr to stack. */ + location->pc_location = PC_LOC_IN_LR; + } else if (bt_modifies_lr(&bundle)) { + lr_modified = true; + } + } + } +} + +void backtrace_init(BacktraceIterator *state, + BacktraceMemoryReader read_memory_func, + void *read_memory_func_extra, + VirtualAddress pc, VirtualAddress lr, + VirtualAddress sp, VirtualAddress r52) +{ + CallerLocation location; + VirtualAddress fp, initial_frame_caller_pc; + + if (read_memory_func == NULL) { + read_memory_func = bt_read_memory; + } + + /* Find out where we are in the initial frame. */ + find_caller_pc_and_caller_sp(&location, pc, + read_memory_func, read_memory_func_extra); + + switch (location.sp_location) { + case SP_LOC_UNKNOWN: + /* Give up. */ + fp = -1; + break; + + case SP_LOC_IN_R52: + fp = r52; + break; + + case SP_LOC_OFFSET: + fp = sp + location.sp_offset; + break; + + default: + /* Give up. */ + fp = -1; + break; + } + + /* If the frame pointer is not aligned to the basic word size + * something terrible happened and we should mark it as invalid. + */ + if (fp % sizeof(bt_int_reg_t) != 0) + fp = -1; + + /* -1 means "don't know initial_frame_caller_pc". */ + initial_frame_caller_pc = -1; + + switch (location.pc_location) { + case PC_LOC_UNKNOWN: + /* Give up. */ + fp = -1; + break; + + case PC_LOC_IN_LR: + if (lr == 0 || lr % TILE_BUNDLE_ALIGNMENT_IN_BYTES != 0) { + /* Give up. */ + fp = -1; + } else { + initial_frame_caller_pc = lr; + } + break; + + case PC_LOC_ON_STACK: + /* Leave initial_frame_caller_pc as -1, + * meaning check the stack. + */ + break; + + default: + /* Give up. */ + fp = -1; + break; + } + + state->pc = pc; + state->sp = sp; + state->fp = fp; + state->initial_frame_caller_pc = initial_frame_caller_pc; + state->read_memory_func = read_memory_func; + state->read_memory_func_extra = read_memory_func_extra; +} + +/* Handle the case where the register holds more bits than the VA. */ +static bool valid_addr_reg(bt_int_reg_t reg) +{ + return ((VirtualAddress)reg == reg); +} + +bool backtrace_next(BacktraceIterator *state) +{ + VirtualAddress next_fp, next_pc; + bt_int_reg_t next_frame[2]; + + if (state->fp == -1) { + /* No parent frame. */ + return false; + } + + /* Try to read the frame linkage data chaining to the next function. */ + if (!state->read_memory_func(&next_frame, state->fp, sizeof next_frame, + state->read_memory_func_extra)) { + return false; + } + + next_fp = next_frame[1]; + if (!valid_addr_reg(next_frame[1]) || + next_fp % sizeof(bt_int_reg_t) != 0) { + /* Caller's frame pointer is suspect, so give up. */ + return false; + } + + if (state->initial_frame_caller_pc != -1) { + /* We must be in the initial stack frame and already know the + * caller PC. + */ + next_pc = state->initial_frame_caller_pc; + + /* Force reading stack next time, in case we were in the + * initial frame. We don't do this above just to paranoidly + * avoid changing the struct at all when we return false. + */ + state->initial_frame_caller_pc = -1; + } else { + /* Get the caller PC from the frame linkage area. */ + next_pc = next_frame[0]; + if (!valid_addr_reg(next_frame[0]) || next_pc == 0 || + next_pc % TILE_BUNDLE_ALIGNMENT_IN_BYTES != 0) { + /* The PC is suspect, so give up. */ + return false; + } + } + + /* Update state to become the caller's stack frame. */ + state->pc = next_pc; + state->sp = state->fp; + state->fp = next_fp; + + return true; +} |