[v4] kprobes: arm: enable OPTPROBES for ARM 32

This patch introduce kprobeopt for ARM 32.

Limitations:
 - Currently only kernel compiled with ARM ISA is supported.

 - Offset between probe point and optinsn slot must not larger than
   32MiB. Masami Hiramatsu suggests replacing 2 words, it will make
   things complex. Futher patch can make such optimization.

Kprobe opt on ARM is relatively simpler than kprobe opt on x86 because
ARM instruction is always 4 bytes aligned and 4 bytes long. This patch
replace probed instruction by a 'b', branch to trampoline code and then
calls optimized_callback(). optimized_callback() calls opt_pre_handler()
to execute kprobe handler. It also emulate/simulate replaced instruction.

When unregistering kprobe, the deferred manner of unoptimizer may leave
branch instruction before optimizer is called. Different from x86_64,
which only copy the probed insn after optprobe_template_end and
reexecute them, this patch call singlestep to emulate/simulate the insn
directly. Futher patch can optimize this behavior.

v1 -> v2:

 - Improvement: if replaced instruction is conditional, generate a
   conditional branch instruction for it;

 - Introduces RELATIVEJUMP_OPCODES due to ARM kprobe_opcode_t is 4
   bytes;

 - Removes size field in struct arch_optimized_insn;

 - Use arm_gen_branch() to generate branch instruction;

 - Remove all recover logic: ARM doesn't use tail buffer, no need
   recover replaced instructions like x86;

 - Remove incorrect CONFIG_THUMB checking;

 - can_optimize() always returns true if address is well aligned;

 - Improve optimized_callback: using opt_pre_handler();

 - Bugfix: correct range checking code and improve comments;

 - Fix commit message.

v2 -> v3:

 - Rename RELATIVEJUMP_OPCODES to MAX_COPIED_INSNS;

 - Remove unneeded checking:
      arch_check_optimized_kprobe(), can_optimize();

 - Add missing flush_icache_range() in arch_prepare_optimized_kprobe();

 - Remove unneeded 'return;'.

v3 -> v4:

 - Use __mem_to_opcode_arm() to translate copied_insn to ensure it
   works in big endian kernel;

 - Replace 'nop' placeholder in trampoline code template with
   '.long 0' to avoid confusion: reader may regard 'nop' as an
   instruction, but it is value in fact.

Signed-off-by: Wang Nan <wangnan0@huawei.com>
Cc: Masami Hiramatsu <masami.hiramatsu.pt@hitachi.com>
Cc: Jon Medhurst (Tixy) <tixy@linaro.org>
Cc: Russell King - ARM Linux <linux@arm.linux.org.uk>
Cc: Will Deacon <will.deacon@arm.com>
---
 arch/arm/Kconfig               |   1 +
 arch/arm/include/asm/kprobes.h |  26 +++++
 arch/arm/kernel/Makefile       |   3 +-
 arch/arm/kernel/kprobes-opt.c  | 255 +++++++++++++++++++++++++++++++++++++++++
 4 files changed, 284 insertions(+), 1 deletion(-)
 create mode 100644 arch/arm/kernel/kprobes-opt.c

Hi Masami and everyone,

When checking my code I found a problem: if we replace a stack operatinon instruction,
it is possible that the emulate execution of such instruction destroy the stack used
by kprobeopt:

> +
> +asm (
> +			".global optprobe_template_entry\n"
> +			"optprobe_template_entry:\n"
> +			"	sub	sp, sp, #80\n"
> +			"	stmia	sp, {r0 - r14} \n"

Here, trampoline code sub sp with 80 (0x50, I choose this number without much thinking), and then
use stmia to push r0 - r14 (registers except pc) onto the stack. Assume the original sp is
0xd0000050, the stack becomes:

0xd0000000: r0
0xd0000004: r1
0xd0000008: r2
...
0xd0000038: r14
0xd000003c: r15 (place holder)
0xd0000040: cpsr (place holder)
0xd0000044: ?
0xd0000048: ?
0xd000004c: ?
0xd0000050: original stack

If the replaced code operates stack, for example, push {r0 - r10}, it will overwrite our register.
For that reason, sub sp, #80 is not enough, we need at least 64 bytes stack space, so the first instruction
here should be sub sp, #128.

However, it increase stack requirement. Moreover, although rare, there may be sp relative addressing,
such as: str r1, [sp, #-132].

To make every situations safe, do you think we need to alloc a pre-cpu optprobe private stack?

For example:

str sp, [pc, #??]     (store original sp first)
ldr sp, [pc, #??]     (load pre-cpu stack)
sub sp, #68
stmia	sp, {r0 - r12}
...                   (fix sp and pc in stack)
ldmia   sp, {r0 - r15}
optprobe_template_sp:
1: .long 0          (placeholder for saved sp)
optprobe_template_private_stack:
2: .long 0          (placeholder for per-cpu private stack)
optprobe_template_pc:
3: .long 0          (placeholder for pc)

> +			"	add	r3, sp, #80\n"
> +			"	str	r3, [sp, #52]\n"
> +			"	mrs	r4, cpsr\n"
> +			"	str	r4, [sp, #64]\n"
> +			"	mov	r1, sp\n"
> +			"	ldr	r0, 1f\n"
> +			"	ldr	r2, 2f\n"
> +			"	blx	r2\n"
> +			"	ldr	r1, [sp, #64]\n"
> +			"	msr	cpsr_fs, r1\n"
> +			"	ldmia	sp, {r0 - r15}\n"
> +			".global optprobe_template_val\n"
> +			"optprobe_template_val:\n"
> +			"1:	.long 0\n"
> +			".global optprobe_template_call\n"
> +			"optprobe_template_call:\n"
> +			"2:	.long 0\n"
> +			".global optprobe_template_end\n"
> +			"optprobe_template_end:\n");
> +


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

(2014/08/12 22:03), Wang Nan wrote:
> Hi Masami and everyone,
> 
> When checking my code I found a problem: if we replace a stack operatinon instruction,
> it is possible that the emulate execution of such instruction destroy the stack used
> by kprobeopt:
> 
>> +
>> +asm (
>> +			".global optprobe_template_entry\n"
>> +			"optprobe_template_entry:\n"
>> +			"	sub	sp, sp, #80\n"
>> +			"	stmia	sp, {r0 - r14} \n"
> 
> Here, trampoline code sub sp with 80 (0x50, I choose this number without much thinking), and then
> use stmia to push r0 - r14 (registers except pc) onto the stack. Assume the original sp is
> 0xd0000050, the stack becomes:
> 
> 0xd0000000: r0
> 0xd0000004: r1
> 0xd0000008: r2
> ...
> 0xd0000038: r14
> 0xd000003c: r15 (place holder)
> 0xd0000040: cpsr (place holder)
> 0xd0000044: ?
> 0xd0000048: ?
> 0xd000004c: ?
> 0xd0000050: original stack
> 
> If the replaced code operates stack, for example, push {r0 - r10}, it will overwrite our register.
> For that reason, sub sp, #80 is not enough, we need at least 64 bytes stack space, so the first instruction
> here should be sub sp, #128.
> 
> However, it increase stack requirement. Moreover, although rare, there may be sp relative addressing,
> such as: str r1, [sp, #-132].

Hmm, I see the increasing stack is clearly hard to emulate, but
why is it hard to emulate sp relative instruction? It should
access the memory under the stack pointer.

> To make every situations safe, do you think we need to alloc a pre-cpu optprobe private stack?

Of course, that is one possible idea, but the simplest way is just not
optimizing such instructions. Why not can_optimize() check that? ;)

Thank you,

(2014/08/12 13:56), Wang Nan wrote:
> +/* Caller must ensure addr & 3 == 0 */
> +static int can_optimize(unsigned long paddr)
> +{
> +	return 1;
> +}

As we have talked on another thread, we'd better filter-out all stack-pushing
instructions here, since (as you said) that will corrupt pt_regs on the stack.

Thank you,

On 2014/8/15 23:23, Masami Hiramatsu wrote:
> (2014/08/12 13:56), Wang Nan wrote:
>> +/* Caller must ensure addr & 3 == 0 */
>> +static int can_optimize(unsigned long paddr)
>> +{
>> +	return 1;
>> +}
> 
> As we have talked on another thread, we'd better filter-out all stack-pushing
> instructions here, since (as you said) that will corrupt pt_regs on the stack.
> 
> Thank you,
> 

So we need to identify the replaced instruction. I think some improvement on
arm instruction decoder is required, else we have to implement another (although simpler)
decoder for memory accessing instructions.

In this situation we are talking about, we need the decoder identify the addressing
information for str/stm instroction. However, decoder can bring up more information such as
instruction type, source/destnation registers, memory access pattern ...
With such information, we can further optimize our trampoline code.
For example: doesn't protect destnation registers, and for some (most of, I think) instruction,
we can direct execute them like x86_64.

What do you think?


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

(2014/08/16 10:38), Wang Nan wrote:
> On 2014/8/15 23:23, Masami Hiramatsu wrote:
>> (2014/08/12 13:56), Wang Nan wrote:
>>> +/* Caller must ensure addr & 3 == 0 */
>>> +static int can_optimize(unsigned long paddr)
>>> +{
>>> +	return 1;
>>> +}
>>
>> As we have talked on another thread, we'd better filter-out all stack-pushing
>> instructions here, since (as you said) that will corrupt pt_regs on the stack.
>>
>> Thank you,
>>
> 
> So we need to identify the replaced instruction. I think some improvement on
> arm instruction decoder is required, else we have to implement another (although simpler)
> decoder for memory accessing instructions.

Since arm32 already have instruction emulator, I guess it's not so hard, we can
start with using emulator code to find which one will change sp.

> In this situation we are talking about, we need the decoder identify the addressing
> information for str/stm instroction.

No, sp register must be always the top of stack, or the code is just broken (breaks
stack frame). So we need to identify the stm/str instructions which destination is
sp register.

> However, decoder can bring up more information such as
> instruction type, source/destnation registers, memory access pattern ...
> With such information, we can further optimize our trampoline code.
> For example: doesn't protect destnation registers, and for some (most of, I think) instruction,
> we can direct execute them like x86_64.

Yeah, direct execution may reduce the overhead much :). But anyway, since we need pt_regs,
we have to store all registers same as pt_regs.

Thank you,