diff mbox series

[RFC,v2,11/20] objtool: arm64: Walk instructions and compute CFI for each instruction

Message ID 20220524001637.1707472-12-madvenka@linux.microsoft.com (mailing list archive)
State New, archived
Headers show
Series arm64: livepatch: Use ORC for dynamic frame pointer validation | expand

Commit Message

Madhavan T. Venkataraman May 24, 2022, 12:16 a.m. UTC 
From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>

Implement arch_initial_func_cfi_state() to initialize the CFI for a
function.

Add code to fpv_decode() to walk the instructions in every function and
compute the CFI information for each instruction.

Implement special handling for cases like jump tables.

Signed-off-by: Madhavan T. Venkataraman <madvenka@linux.microsoft.com>
---
 tools/objtool/arch/arm64/decode.c |  15 +++
 tools/objtool/fpv.c               | 204 ++++++++++++++++++++++++++++++
 2 files changed, 219 insertions(+)

Comments

Chen Zhongjin May 24, 2022, 1:45 p.m. UTC | #1 
Hi,

On 2022/5/24 8:16, madvenka@linux.microsoft.com wrote:
> From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>
> 
> Implement arch_initial_func_cfi_state() to initialize the CFI for a
> function.
> 
> Add code to fpv_decode() to walk the instructions in every function and
> compute the CFI information for each instruction.
> 
> Implement special handling for cases like jump tables.
> 
> Signed-off-by: Madhavan T. Venkataraman <madvenka@linux.microsoft.com>
> ---
>  tools/objtool/arch/arm64/decode.c |  15 +++
>  tools/objtool/fpv.c               | 204 ++++++++++++++++++++++++++++++
>  2 files changed, 219 insertions(+)
...
> +static void update_cfi_state(struct cfi_state *cfi, struct stack_op *op)
> +{
> +	struct cfi_reg *cfa = &cfi->cfa;
> +	struct cfi_reg *regs = cfi->regs;
> +
> +	if (op->src.reg == CFI_SP) {
> +		if (op->dest.reg == CFI_SP)
> +			cfa->offset -= op->src.offset;
> +		else
> +			regs[CFI_FP].offset = -cfa->offset + op->src.offset;
Seems wrong here, we don't have any op->src.offset for [mov x29, sp] so here we
get: fp->offset = -cfa->offset. The dumped info also proves this.

> +	case UNWIND_HINT_TYPE_CALL:
> +		/* Normal call */
> +		frame->cfa += orc->sp_offset;
> +		fp = frame->cfa + orc->fp_offset;
> +		break;
Obviously this is not conform to the reliability check because we get
frame->cfa == fp here.

IIUC your sp_offset equals to stack length, and fp_offset is offset from next
x29 to next CFA. So maybe here we should have
regs[CFI_FP].offset = regs[CFI_SP].offset for [mov x29, sp].

Anyway, in original objtool sp_offset and fp_offset both represents the offset
from CFA to REGs. I think it's better not spoiling their original meaning and
just extending.
Madhavan T. Venkataraman May 29, 2022, 3:18 p.m. UTC | #2 
On 5/24/22 08:45, Chen Zhongjin wrote:
> Hi,
> 
> On 2022/5/24 8:16, madvenka@linux.microsoft.com wrote:
>> From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>
>>
>> Implement arch_initial_func_cfi_state() to initialize the CFI for a
>> function.
>>
>> Add code to fpv_decode() to walk the instructions in every function and
>> compute the CFI information for each instruction.
>>
>> Implement special handling for cases like jump tables.
>>
>> Signed-off-by: Madhavan T. Venkataraman <madvenka@linux.microsoft.com>
>> ---
>>  tools/objtool/arch/arm64/decode.c |  15 +++
>>  tools/objtool/fpv.c               | 204 ++++++++++++++++++++++++++++++
>>  2 files changed, 219 insertions(+)
> ...
>> +static void update_cfi_state(struct cfi_state *cfi, struct stack_op *op)
>> +{
>> +	struct cfi_reg *cfa = &cfi->cfa;
>> +	struct cfi_reg *regs = cfi->regs;
>> +
>> +	if (op->src.reg == CFI_SP) {
>> +		if (op->dest.reg == CFI_SP)
>> +			cfa->offset -= op->src.offset;
>> +		else
>> +			regs[CFI_FP].offset = -cfa->offset + op->src.offset;
> Seems wrong here, we don't have any op->src.offset for [mov x29, sp] so here we
> get: fp->offset = -cfa->offset. The dumped info also proves this.


See the example below.

> 
>> +	case UNWIND_HINT_TYPE_CALL:
>> +		/* Normal call */
>> +		frame->cfa += orc->sp_offset;
>> +		fp = frame->cfa + orc->fp_offset;
>> +		break;
> Obviously this is not conform to the reliability check because we get
> frame->cfa == fp here.
> 

See the example below:

> IIUC your sp_offset equals to stack length, and fp_offset is offset from next
> x29 to next CFA. So maybe here we should have
> regs[CFI_FP].offset = regs[CFI_SP].offset for [mov x29, sp].
> 
> Anyway, in original objtool sp_offset and fp_offset both represents the offset
> from CFA to REGs. I think it's better not spoiling their original meaning and
> just extending.
> 
> 

I am not spoiling anything.


Let us take an example:

ffff800008010000 <bcm2835_handle_irq>:
ffff800008010000:       d503201f        nop
ffff800008010004:       d503201f        nop
ffff800008010008:       d503233f        paciasp
ffff80000801000c:       a9be7bfd        stp     x29, x30, [sp, #-32]!
ffff800008010010:       910003fd        mov     x29, sp
ffff800008010014:       f9000bf3        str     x19, [sp, #16]


The stack pointer is first moved by -32 and the FP and LR are stored there.
At this point, SP is pointing to the frame. The CFA is:

	CFA = SP + 32

The frame pointer has been stored at the location pointed to by the SP.
So, FP should be:

	FP = CFA - 32

Therefore, at instruction address ffff800008010014:

	frame->cfa = SP + 32;
	frame->fp = frame->cfa - 32 = SP;

So, if a call/interrupt happens after this instruction, the frame pointer computed
from the above data will match with the actual frame pointer.

I have verified this using the DWARF data generated by the compiler. It is correct.
I have also verified that the stack trace through such code passes the reliability
check. That is, it computes the frame pointer correctly which matches with the
actual frame pointer.

Madhavan
Chen Zhongjin May 30, 2022, 1:44 a.m. UTC | #3 
Hi,

On 2022/5/29 23:18, Madhavan T. Venkataraman wrote:
> 
> 
> On 5/24/22 08:45, Chen Zhongjin wrote:
>> Hi,
>>
>> On 2022/5/24 8:16, madvenka@linux.microsoft.com wrote:
>>> From: "Madhavan T. Venkataraman" <madvenka@linux.microsoft.com>
>>>
>>> Implement arch_initial_func_cfi_state() to initialize the CFI for a
>>> function.
>>>
>>> Add code to fpv_decode() to walk the instructions in every function and
>>> compute the CFI information for each instruction.
>>>
>>> Implement special handling for cases like jump tables.
>>>
>>> Signed-off-by: Madhavan T. Venkataraman <madvenka@linux.microsoft.com>
>>> ---
>>>  tools/objtool/arch/arm64/decode.c |  15 +++
>>>  tools/objtool/fpv.c               | 204 ++++++++++++++++++++++++++++++
>>>  2 files changed, 219 insertions(+)
>> ...
>>> +static void update_cfi_state(struct cfi_state *cfi, struct stack_op *op)
>>> +{
>>> +	struct cfi_reg *cfa = &cfi->cfa;
>>> +	struct cfi_reg *regs = cfi->regs;
>>> +
>>> +	if (op->src.reg == CFI_SP) {
>>> +		if (op->dest.reg == CFI_SP)
>>> +			cfa->offset -= op->src.offset;
>>> +		else
>>> +			regs[CFI_FP].offset = -cfa->offset + op->src.offset;
>> Seems wrong here, we don't have any op->src.offset for [mov x29, sp] so here we
>> get: fp->offset = -cfa->offset. The dumped info also proves this.
> 
> 
> See the example below.
> 
>>
>>> +	case UNWIND_HINT_TYPE_CALL:
>>> +		/* Normal call */
>>> +		frame->cfa += orc->sp_offset;
>>> +		fp = frame->cfa + orc->fp_offset;
>>> +		break;
>> Obviously this is not conform to the reliability check because we get
>> frame->cfa == fp here.
>>
> 
> See the example below:
> 
>> IIUC your sp_offset equals to stack length, and fp_offset is offset from next
>> x29 to next CFA. So maybe here we should have
>> regs[CFI_FP].offset = regs[CFI_SP].offset for [mov x29, sp].
>>
>> Anyway, in original objtool sp_offset and fp_offset both represents the offset
>> from CFA to REGs. I think it's better not spoiling their original meaning and
>> just extending.
>>
>>
> 
> I am not spoiling anything.
> 
> 
> Let us take an example:
> 
> ffff800008010000 <bcm2835_handle_irq>:
> ffff800008010000:       d503201f        nop
> ffff800008010004:       d503201f        nop
> ffff800008010008:       d503233f        paciasp
> ffff80000801000c:       a9be7bfd        stp     x29, x30, [sp, #-32]!
> ffff800008010010:       910003fd        mov     x29, sp
> ffff800008010014:       f9000bf3        str     x19, [sp, #16]
> 
> 
> The stack pointer is first moved by -32 and the FP and LR are stored there.
> At this point, SP is pointing to the frame. The CFA is:
> 
> 	CFA = SP + 32
> 
> The frame pointer has been stored at the location pointed to by the SP.
> So, FP should be:
> 
> 	FP = CFA - 32
> 
> Therefore, at instruction address ffff800008010014:
> 
> 	frame->cfa = SP + 32;
> 	frame->fp = frame->cfa - 32 = SP;
> 
> So, if a call/interrupt happens after this instruction, the frame pointer computed
> from the above data will match with the actual frame pointer.
> 
> I have verified this using the DWARF data generated by the compiler. It is correct.
> I have also verified that the stack trace through such code passes the reliability
> check. That is, it computes the frame pointer correctly which matches with the
> actual frame pointer
You are right, I think I mixed up frame of x86 and arm64.

Apologize for that and thanks for explaining!

Best,
Chen
diff mbox series

Patch

diff --git a/tools/objtool/arch/arm64/decode.c b/tools/objtool/arch/arm64/decode.c
index f9df8b321659..93ef7c0811f1 100644
--- a/tools/objtool/arch/arm64/decode.c
+++ b/tools/objtool/arch/arm64/decode.c
@@ -35,6 +35,21 @@  struct decode {
 
 /* --------------------- arch support functions ------------------------- */
 
+void arch_initial_func_cfi_state(struct cfi_init_state *state)
+{
+	int i;
+
+	for (i = 0; i < CFI_NUM_REGS; i++) {
+		state->regs[i].base = CFI_UNDEFINED;
+		state->regs[i].offset = 0;
+	}
+	state->regs[CFI_FP].base = CFI_CFA;
+
+	/* initial CFA (call frame address) */
+	state->cfa.base = CFI_SP;
+	state->cfa.offset = 0;
+}
+
 unsigned long arch_dest_reloc_offset(int addend)
 {
 	return addend;
diff --git a/tools/objtool/fpv.c b/tools/objtool/fpv.c
index 92ad0d0aac8e..52f613ae998f 100644
--- a/tools/objtool/fpv.c
+++ b/tools/objtool/fpv.c
@@ -13,6 +13,8 @@ 
 #include <objtool/insn.h>
 #include <objtool/warn.h>
 
+static bool	fill;
+
 /*
  * Find the destination instructions for all jumps.
  */
@@ -50,15 +52,217 @@  static void add_jump_destinations(struct objtool_file *file)
 	}
 }
 
+static void update_cfi_state(struct cfi_state *cfi, struct stack_op *op)
+{
+	struct cfi_reg *cfa = &cfi->cfa;
+	struct cfi_reg *regs = cfi->regs;
+
+	if (op->src.reg == CFI_SP) {
+		if (op->dest.reg == CFI_SP)
+			cfa->offset -= op->src.offset;
+		else
+			regs[CFI_FP].offset = -cfa->offset + op->src.offset;
+	} else {
+		if (op->dest.reg == CFI_SP)
+			cfa->offset = -(regs[CFI_FP].offset + op->src.offset);
+		else
+			regs[CFI_FP].offset += op->src.offset;
+	}
+
+	if (cfa->offset < -regs[CFI_FP].offset)
+		regs[CFI_FP].offset = 0;
+}
+
+static void do_stack_ops(struct instruction *insn, struct insn_state *state)
+{
+	struct stack_op *op;
+
+	list_for_each_entry(op, &insn->stack_ops, list) {
+		update_cfi_state(&state->cfi, op);
+	}
+}
+
+static void walk_code(struct objtool_file *file, struct section *sec,
+		      struct symbol *func,
+		      struct instruction *insn, struct insn_state *state)
+{
+	struct symbol *insn_func = insn->func;
+	struct instruction *dest;
+	struct cfi_state save_cfi;
+	unsigned long start, end;
+
+	for (; insn; insn = next_insn_same_sec(file, insn)) {
+
+		if (insn->func != insn_func)
+			return;
+
+		if (insn->cfi) {
+			if (fill) {
+				/* CFI is present. Nothing to fill. */
+				return;
+			}
+			if (insn->cfi->regs[CFI_FP].offset ||
+			    !state->cfi.regs[CFI_FP].offset) {
+				return;
+			}
+			/*
+			 * The new CFI contains a valid frame and the existing
+			 * CFI doesn't. Replace the existing CFI with the new
+			 * one.
+			 */
+		}
+		insn->cfi = cfi_hash_find_or_add(&state->cfi);
+		dest = insn->jump_dest;
+
+		do_stack_ops(insn, state);
+
+		switch (insn->type) {
+		case INSN_BUG:
+		case INSN_RETURN:
+		case INSN_UNRELIABLE:
+			return;
+
+		case INSN_CALL:
+		case INSN_CALL_DYNAMIC:
+			start = func->offset;
+			end = start + func->len;
+			/*
+			 * Treat intra-function calls as jumps and fall
+			 * through.
+			 */
+			if (!dest || dest->sec != sec ||
+			    dest->offset <= start || dest->offset >= end) {
+				break;
+			}
+			/* fallthrough */
+
+		case INSN_JUMP_UNCONDITIONAL:
+		case INSN_JUMP_CONDITIONAL:
+		case INSN_JUMP_DYNAMIC:
+			if (dest) {
+				save_cfi = state->cfi;
+				walk_code(file, sec, func, dest, state);
+				state->cfi = save_cfi;
+			}
+			if (insn->type == INSN_JUMP_UNCONDITIONAL ||
+			    insn->type == INSN_JUMP_DYNAMIC) {
+				return;
+			}
+			break;
+
+		default:
+			break;
+		}
+	}
+}
+
+static void walk_function(struct objtool_file *file, struct section *sec,
+			  struct symbol *func)
+{
+	struct instruction *insn = find_insn(file, sec, func->offset);
+	struct insn_state state;
+
+	init_insn_state(&state, sec);
+	set_func_state(&state.cfi);
+
+	walk_code(file, sec, func, insn, &state);
+}
+
+/*
+ * This function addresses cases like jump tables where there is an array
+ * of unconditional branches. The normal walk would not have visited these
+ * instructions and established CFIs for them. Find those instructions. For
+ * each such instruction, copy the CFI from the branch instruction and
+ * propagate it down.
+ */
+static void fill_function(struct objtool_file *file, struct section *sec,
+			  struct symbol *func)
+{
+	struct instruction *insn, *prev;
+	struct insn_state state;
+
+	func_for_each_insn(file, func, insn) {
+
+		if (insn->cfi) {
+			/* Instruction already has a CFI. */
+			continue;
+		}
+
+		prev = list_prev_entry(insn, list);
+		if (!prev || !prev->cfi) {
+			/*
+			 * Previous instruction does not have a CFI that can
+			 * be used for this instruction.
+			 */
+			continue;
+		}
+
+		if (prev->type != INSN_JUMP_UNCONDITIONAL &&
+		    prev->type != INSN_JUMP_DYNAMIC) {
+			/* Only copy CFI from unconditional branches. */
+			continue;
+		}
+
+		/*
+		 * Propagate the CFI to all the instructions that can be
+		 * visited from the current instruction that don't already
+		 * have a CFI.
+		 */
+		state.cfi = *prev->cfi;
+		walk_code(file, insn->sec, insn->func, insn, &state);
+	}
+}
+
+static void walk_section(struct objtool_file *file, struct section *sec)
+{
+	struct symbol *func;
+
+	list_for_each_entry(func, &sec->symbol_list, list) {
+
+		if (func->type != STT_FUNC || !func->len ||
+		    func->pfunc != func || func->alias != func) {
+			/* No CFI generated for this function. */
+			continue;
+		}
+
+		if (!fill)
+			walk_function(file, sec, func);
+		else
+			fill_function(file, sec, func);
+	}
+}
+
+static void walk_sections(struct objtool_file *file)
+{
+	struct section *sec;
+
+	for_each_sec(file, sec) {
+		if (sec->sh.sh_flags & SHF_EXECINSTR)
+			walk_section(file, sec);
+	}
+}
+
 int fpv_decode(struct objtool_file *file)
 {
 	int ret;
 
+	arch_initial_func_cfi_state(&initial_func_cfi);
+
+	if (!cfi_hash_alloc(1UL << (file->elf->symbol_bits - 3)))
+		return -1;
+
 	ret = decode_instructions(file);
 	if (ret)
 		return ret;
 
 	add_jump_destinations(file);
 
+	if (!list_empty(&file->insn_list)) {
+		fill = false;
+		walk_sections(file);
+		fill = true;
+		walk_sections(file);
+	}
+
 	return 0;
 }