[v5,3/3] 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.

v4 -> v5:

 - Don't optimize stack store operations.

 - Introduce prepared field to arch_optimized_insn to indicate whether
   it is prepared. Similar to size field with x86. See v1 -> v2.

Signed-off-by: Wang Nan <wangnan0@huawei.com>
Acked-by: Masami Hiramatsu <masami.hiramatsu.pt@hitachi.com>
Cc: Russell King <linux@arm.linux.org.uk>
Cc: "David A. Long" <dave.long@linaro.org> 
Cc: Jon Medhurst <tixy@linaro.org>
Cc: Taras Kondratiuk <taras.kondratiuk@linaro.org>
Cc: Ben Dooks <ben.dooks@codethink.co.uk>
Cc: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
Cc: Anil S Keshavamurthy <anil.s.keshavamurthy@intel.com>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Will Deacon <will.deacon@arm.com>

---
 arch/arm/Kconfig               |   1 +
 arch/arm/include/asm/kprobes.h |  28 +++++
 arch/arm/kernel/Makefile       |   3 +-
 arch/arm/kernel/kprobes-opt.c  | 259 +++++++++++++++++++++++++++++++++++++++++
 4 files changed, 290 insertions(+), 1 deletion(-)
 create mode 100644 arch/arm/kernel/kprobes-opt.c

(2014/08/27 22:02), Wang Nan wrote:
> +/*
> + * ARM can always optimize an instruction when using ARM ISA.
> + */

Hmm, this comment looks not correct anymore :)

> +int arch_prepared_optinsn(struct arch_optimized_insn *optinsn)
> +{
> +	return optinsn->prepared;
> +}

BTW, why don't you check optinsn->insn != NULL ?
If it is not prepared for optimizing,  optinsn->insn always be NULL.

[...]
> +int arch_prepare_optimized_kprobe(struct optimized_kprobe *op)
> +{
> +	u8 *buf;
> +	unsigned long rel_chk;
> +	unsigned long val;
> +
> +	if (!can_optimize(op))
> +		return -EILSEQ;
> +
> +	op->optinsn.insn = get_optinsn_slot();
> +	if (!op->optinsn.insn)
> +		return -ENOMEM;
> +
> +	/*
> +	 * Verify if the address gap is in 32MiB range, because this uses
> +	 * a relative jump.
> +	 *
> +	 * kprobe opt use a 'b' instruction to branch to optinsn.insn.
> +	 * According to ARM manual, branch instruction is:
> +	 *
> +	 *   31  28 27           24 23             0
> +	 *  +------+---+---+---+---+----------------+
> +	 *  | cond | 1 | 0 | 1 | 0 |      imm24     |
> +	 *  +------+---+---+---+---+----------------+
> +	 *
> +	 * imm24 is a signed 24 bits integer. The real branch offset is computed
> +	 * by: imm32 = SignExtend(imm24:'00', 32);
> +	 *
> +	 * So the maximum forward branch should be:
> +	 *   (0x007fffff << 2) = 0x01fffffc =  0x1fffffc
> +	 * The maximum backword branch should be:
> +	 *   (0xff800000 << 2) = 0xfe000000 = -0x2000000
> +	 *
> +	 * We can simply check (rel & 0xfe000003):
> +	 *  if rel is positive, (rel & 0xfe000000) shoule be 0
> +	 *  if rel is negitive, (rel & 0xfe000000) should be 0xfe000000
> +	 *  the last '3' is used for alignment checking.
> +	 */
> +	rel_chk = (unsigned long)((long)op->optinsn.insn -
> +			(long)op->kp.addr + 8) & 0xfe000003;
> +
> +	if ((rel_chk != 0) && (rel_chk != 0xfe000000)) {
> +		__arch_remove_optimized_kprobe(op, 0);
> +		return -ERANGE;
> +	}
> +
> +	buf = (u8 *)op->optinsn.insn;
> +
> +	/* Copy arch-dep-instance from template */
> +	memcpy(buf, &optprobe_template_entry, TMPL_END_IDX);
> +
> +	/* Set probe information */
> +	val = (unsigned long)op;
> +	memcpy(buf + TMPL_VAL_IDX, &val, sizeof(val));
> +
> +	/* Set probe function call */
> +	val = (unsigned long)optimized_callback;
> +	memcpy(buf + TMPL_CALL_IDX, &val, sizeof(val));
> +
> +	flush_icache_range((unsigned long)buf,
> +			   (unsigned long)buf + TMPL_END_IDX);
> +
> +	op->optinsn.prepared = true;
> +	return 0;
> +}
> +

Thank you,

I gave the patches a quick test and in doing so found a bug which stops
any probes actually being optimised, and the same bug should affect X86,
see comment below...

On Wed, 2014-08-27 at 21:02 +0800, Wang Nan wrote:
[...]
> +int arch_prepare_optimized_kprobe(struct optimized_kprobe *op)
> +{
> +	u8 *buf;
> +	unsigned long rel_chk;
> +	unsigned long val;
> +
> +	if (!can_optimize(op))
> +		return -EILSEQ;
> +
> +	op->optinsn.insn = get_optinsn_slot();
> +	if (!op->optinsn.insn)
> +		return -ENOMEM;
> +
> +	/*
> +	 * Verify if the address gap is in 32MiB range, because this uses
> +	 * a relative jump.
> +	 *
> +	 * kprobe opt use a 'b' instruction to branch to optinsn.insn.
> +	 * According to ARM manual, branch instruction is:
> +	 *
> +	 *   31  28 27           24 23             0
> +	 *  +------+---+---+---+---+----------------+
> +	 *  | cond | 1 | 0 | 1 | 0 |      imm24     |
> +	 *  +------+---+---+---+---+----------------+
> +	 *
> +	 * imm24 is a signed 24 bits integer. The real branch offset is computed
> +	 * by: imm32 = SignExtend(imm24:'00', 32);
> +	 *
> +	 * So the maximum forward branch should be:
> +	 *   (0x007fffff << 2) = 0x01fffffc =  0x1fffffc
> +	 * The maximum backword branch should be:
> +	 *   (0xff800000 << 2) = 0xfe000000 = -0x2000000
> +	 *
> +	 * We can simply check (rel & 0xfe000003):
> +	 *  if rel is positive, (rel & 0xfe000000) shoule be 0
> +	 *  if rel is negitive, (rel & 0xfe000000) should be 0xfe000000
> +	 *  the last '3' is used for alignment checking.
> +	 */
> +	rel_chk = (unsigned long)((long)op->optinsn.insn -
> +			(long)op->kp.addr + 8) & 0xfe000003;

This check always fails because op->kp.addr is zero. Debugging this I
found that this function is called from alloc_aggr_kprobe() and that
copies the real kprobe into op->kp using copy_kprobe(), which doesn't
actually copy the 'addr' value...

        static inline void copy_kprobe(struct kprobe *ap, struct kprobe *p)
        {
        	memcpy(&p->opcode, &ap->opcode, sizeof(kprobe_opcode_t));
        	memcpy(&p->ainsn, &ap->ainsn, sizeof(struct arch_specific_insn));
        }

Thing is, the new ARM code is a close copy of the existing X86 version
so that would also suffer the same problem of kp.addr always being zero.
So either I've miss understood something or this is fundamental bug no
one has noticed before.

Throwing in 'p->addr = ap->addr' into the copy_kprobe function fixed the
behaviour arch_prepare_optimized_kprobe.

I was testing this by running the kprobes tests
(CONFIG_ARM_KPROBES_TEST=y) and putting a few printk's in strategic
places in kprobes-opt.c to check to see what code paths got executed,
which is how I discovered the problem.

Two things to note when running kprobes tests...

1. On SMP systems it's very slow because of kprobe's use of stop_machine
for applying and removing probes, this forces the system to idle and
wait for the next scheduler tick for each probe change.

2. It's a good idea to enable VERBOSE in kprobes-test.h to get output
for each test case instruction, this reassures you things are
progressing and if things explode lets you know what instruction type
triggered it.

On Wed, Sep 03, 2014 at 11:18:04AM +0100, Masami Hiramatsu wrote:
> (2014/09/02 22:49), Jon Medhurst (Tixy) wrote:
> > 1. On SMP systems it's very slow because of kprobe's use of stop_machine
> > for applying and removing probes, this forces the system to idle and
> > wait for the next scheduler tick for each probe change.
> 
> Hmm, agreed. It seems that arm32 limitation of self-modifying code on SMP.
> I'm not sure how we can handle it, but I guess;
>  - for some processors which have better coherent cache for SMP, we can
>    atomically replace the breakpoint code with original code.

Except that it's not an architected breakpoint instruction, as I mentioned
before. It's also not really a property of the cache.

>  - Even if we get an "undefined instruction" exception, its handler can
>    ask kprobes if the address is under modifying or not. And if it is,
>    we can just return from the exception to retry the execution.

It's not as simple as that -- you could potentially see an interleaving of
the two instructions. The architecture is even broader than that:

 Concurrent modification and execution of instructions can lead to the
 resulting instruction performing any behavior that can be achieved by
 executing any sequence of instructions that can be executed from the
 same Exception level,

There are additional guarantees for some instructions (like the architected
BKPT instruction).

Will
--
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/

On Wed, 2014-09-03 at 11:30 +0100, Will Deacon wrote:
> On Wed, Sep 03, 2014 at 11:18:04AM +0100, Masami Hiramatsu wrote:
> > (2014/09/02 22:49), Jon Medhurst (Tixy) wrote:
> > > 1. On SMP systems it's very slow because of kprobe's use of stop_machine
> > > for applying and removing probes, this forces the system to idle and
> > > wait for the next scheduler tick for each probe change.
> > 
> > Hmm, agreed. It seems that arm32 limitation of self-modifying code on SMP.
> > I'm not sure how we can handle it, but I guess;
> >  - for some processors which have better coherent cache for SMP, we can
> >    atomically replace the breakpoint code with original code.
> 
> Except that it's not an architected breakpoint instruction, as I mentioned
> before. It's also not really a property of the cache.
> 
> >  - Even if we get an "undefined instruction" exception, its handler can
> >    ask kprobes if the address is under modifying or not. And if it is,
> >    we can just return from the exception to retry the execution.
> 
> It's not as simple as that -- you could potentially see an interleaving of
> the two instructions. The architecture is even broader than that:
> 
>  Concurrent modification and execution of instructions can lead to the
>  resulting instruction performing any behavior that can be achieved by
>  executing any sequence of instructions that can be executed from the
>  same Exception level,
> 
> There are additional guarantees for some instructions (like the architected
> BKPT instruction).

I should point out that the current implementation of kprobes doesn't
use stop_machine because it's trying to meet the above architecture
restrictions, and that arming kprobes (changing probed instruction to an
undefined instruction) isn't usually done under stop_machine, so other
CPUs could be executing the original instruction as it's being modified.

So, should we be making patch_text unconditionally use stop machine and
remove all direct use of __patch_text? (E.g. by jump labels.)

On Thu, Sep 04, 2014 at 11:40:35AM +0100, Jon Medhurst (Tixy) wrote:
> On Wed, 2014-09-03 at 11:30 +0100, Will Deacon wrote:
> > On Wed, Sep 03, 2014 at 11:18:04AM +0100, Masami Hiramatsu wrote:
> > > (2014/09/02 22:49), Jon Medhurst (Tixy) wrote:
> > > > 1. On SMP systems it's very slow because of kprobe's use of stop_machine
> > > > for applying and removing probes, this forces the system to idle and
> > > > wait for the next scheduler tick for each probe change.
> > > 
> > > Hmm, agreed. It seems that arm32 limitation of self-modifying code on SMP.
> > > I'm not sure how we can handle it, but I guess;
> > >  - for some processors which have better coherent cache for SMP, we can
> > >    atomically replace the breakpoint code with original code.
> > 
> > Except that it's not an architected breakpoint instruction, as I mentioned
> > before. It's also not really a property of the cache.
> > 
> > >  - Even if we get an "undefined instruction" exception, its handler can
> > >    ask kprobes if the address is under modifying or not. And if it is,
> > >    we can just return from the exception to retry the execution.
> > 
> > It's not as simple as that -- you could potentially see an interleaving of
> > the two instructions. The architecture is even broader than that:
> > 
> >  Concurrent modification and execution of instructions can lead to the
> >  resulting instruction performing any behavior that can be achieved by
> >  executing any sequence of instructions that can be executed from the
> >  same Exception level,
> > 
> > There are additional guarantees for some instructions (like the architected
> > BKPT instruction).
> 
> I should point out that the current implementation of kprobes doesn't
> use stop_machine because it's trying to meet the above architecture
> restrictions, and that arming kprobes (changing probed instruction to an
> undefined instruction) isn't usually done under stop_machine, so other
> CPUs could be executing the original instruction as it's being modified.
> 
> So, should we be making patch_text unconditionally use stop machine and
> remove all direct use of __patch_text? (E.g. by jump labels.)

You could take a look at what we do for arm64 (see aarch64_insn_hotpatch_safe)
for inspiration.

Will
--
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/