[RFC] kprobes with thumb2 conditional code

[RFC] kprobes with thumb2 conditional code

[Tixy]

Hello All

I'm about to start work on getting kprobes working with thumb2.

One of the issues I have is that when probes are placed onto
conditionally executed instructions in a IT block, they may not fire if
the condition is not met. This is because on ARM we use invalid
instructions for breakpoints, and the ARM ARM says:

  "it is IMPLEMENTATION DEFINED whether the instruction executes as a
   NOP or causes an Undefined Instruction exception"

This is a similar issue to that already encountered by GDB [1][2]

If we take this code as an example...

probe1:
if(condition) {
probe2:
    some_code;
}

It seams reasonable at first sight that probe2 would only fire if the
condition is true. This will always be the case if the compiler
generates test-and-branch code, but if it generates conditionally
executed instructions for 'some_code' then it gets complicated...

The current arm kprobes implementation will always fire probe2 because
it uses unconditional instructions for its breakpoints. With thumb
instructions we can't force unconditional execution, so we would have an
'implementation defined' situation whether it would fire or not when the
condition is false. (Thought you would hope it would be consistent on a
particular device.)

Some options for dealing with this, in increasing order of
complexity... 

1. Accept the situation as described.

2. Change arm probes to use conditional instructions so we would
(hopefully) have consistent undefined behaviour in both arm and thumb
code. (If that isn't an oxymoron :-)

3. Do 2, and modify kprobe_handler to test for false firings (breakpoint
when condition false) and not execute the probe's callback functions in
these cases. E.g. consistently make probe2 appear to not fire when
condition is false.

4. Make thumb probes fire unconditionally like current arm
implementation...

4a. Use breakpoint instructions rather than undefined instructions for
kprobes. Apparently this doesn't play nicely with hardware debuggers [2]
though I don't have enough experience in this area to otherwise comment.

4b. Rewrite IT blocks when probes are inserted into them to make the
breakpoint unconditional. This would require parsing backwards through
the instruction stream to find the IT instruction, which I don't believe
is possible with variable length thumb instructions. Or, another
possibility which was suggested to me, use the unwind table to find the
start of the containing function and parse forwards to find the IT
instruction. Though the kernel doesn't currently have enough information
to skip things like inline data that may be the function.

The effort, complexity and bloat involved in 4b seems to be rather
excessive to me, even before getting into the book-keeping required to
handle multiple probes in the same IT block. So 4b is a bit of a straw
man.

BTW, does anyone know of any test code for kprobes, particularly with
regard to checking emulation/single-stepping of the different CPU
instructions?

Thanks for any feedback

-- 
Tixy


[1] http://permalink.gmane.org/gmane.comp.gdb.patches/54862  
[2]
http://thread.gmane.org/gmane.linux.ports.arm.kernel/72199/focus=73489

[RFC] kprobes with thumb2 conditional code

[Dave Martin]

On Fri, Mar 11, 2011 at 5:01 PM, Tixy <tixy@yxit.co.uk> wrote:
> Hello All
>
> I'm about to start work on getting kprobes working with thumb2.
>
> One of the issues I have is that when probes are placed onto
> conditionally executed instructions in a IT block, they may not fire if
> the condition is not met. This is because on ARM we use invalid
> instructions for breakpoints, and the ARM ARM says:
>
> ?"it is IMPLEMENTATION DEFINED whether the instruction executes as a
> ? NOP or causes an Undefined Instruction exception"
>
> This is a similar issue to that already encountered by GDB [1][2]
>
> If we take this code as an example...
>
> probe1:
> if(condition) {
> probe2:
> ? ?some_code;
> }
>
> It seams reasonable at first sight that probe2 would only fire if the
> condition is true. This will always be the case if the compiler
> generates test-and-branch code, but if it generates conditionally
> executed instructions for 'some_code' then it gets complicated...
>
> The current arm kprobes implementation will always fire probe2 because

Well, actually it's somewhat unpredictable whether/when a probe on
probe2 will fire, because it depends on the code generated by the
compiler.  The compiler could choose to use a conditional instruction
at probe2, or it could conditionally branch round it, even in ARM.
Or, the whole conditional might disappear to be replaced with an
unconditional instruction sequence that has the same overall effect.

> it uses unconditional instructions for its breakpoints. With thumb
> instructions we can't force unconditional execution, so we would have an
> 'implementation defined' situation whether it would fire or not when the
> condition is false. (Thought you would hope it would be consistent on a
> particular device.)
>
> Some options for dealing with this, in increasing order of
> complexity...
>
> 1. Accept the situation as described.
>
> 2. Change arm probes to use conditional instructions so we would
> (hopefully) have consistent undefined behaviour in both arm and thumb
> code. (If that isn't an oxymoron :-)
>
> 3. Do 2, and modify kprobe_handler to test for false firings (breakpoint
> when condition false) and not execute the probe's callback functions in
> these cases. E.g. consistently make probe2 appear to not fire when
> condition is false.

My preference would be for option (1) or (3).  For (3), we could
choose to extend this behaviour to cover the existing ARM
implementation as well as Thumb, which could be a tidier and more
consistent approach.  This seems to be the "right" thing, since it
means kprobes never fire for real on instructions which are logically
not executed, no matter how the compiler (or human) implemented the
conditionality.  Currently, ARM kprobes can fire on instructions which
would fail their condition check, which might be considered wrong.

Alternatively, we could avoid fixing what isn't broken and leave the
ARM implementation unchanged.  Since the compiler will implement some
different instruction-level optimisations in Thumb compared with ARM,
it may not make sense to try to make the kprobe firing behaviour
behave exactly the same around conditional code in both instruction
sets -- because the code generation differences may always cause the
observed behaviour to be different anyway, just as might happen if you
switch to a newer compiler or use a different -march/-mtune
combination.

For the same reasons described above, I'd advise against the more
complex routes in (4).  The extra complexity probably doesn't bring
any useful consistency.


Has anyone made use of kprobes in a way where the precise firing
behaviour for conditional code would be important?

Cheers
---Dave

>
> 4. Make thumb probes fire unconditionally like current arm
> implementation...
>
> 4a. Use breakpoint instructions rather than undefined instructions for
> kprobes. Apparently this doesn't play nicely with hardware debuggers [2]
> though I don't have enough experience in this area to otherwise comment.
>
> 4b. Rewrite IT blocks when probes are inserted into them to make the
> breakpoint unconditional. This would require parsing backwards through
> the instruction stream to find the IT instruction, which I don't believe
> is possible with variable length thumb instructions. Or, another
> possibility which was suggested to me, use the unwind table to find the
> start of the containing function and parse forwards to find the IT
> instruction. Though the kernel doesn't currently have enough information
> to skip things like inline data that may be the function.
>
> The effort, complexity and bloat involved in 4b seems to be rather
> excessive to me, even before getting into the book-keeping required to
> handle multiple probes in the same IT block. So 4b is a bit of a straw
> man.
>
> BTW, does anyone know of any test code for kprobes, particularly with
> regard to checking emulation/single-stepping of the different CPU
> instructions?
>
> Thanks for any feedback
>
> --
> Tixy
>
>
> [1] http://permalink.gmane.org/gmane.comp.gdb.patches/54862
> [2]
> http://thread.gmane.org/gmane.linux.ports.arm.kernel/72199/focus=73489
>
>
>
> _______________________________________________
> linaro-dev mailing list
> linaro-dev at lists.linaro.org
> http://lists.linaro.org/mailman/listinfo/linaro-dev
>

[RFC] kprobes with thumb2 conditional code

[Nicolas Pitre]

On Thu, 17 Mar 2011, Dave Martin wrote:

> On Fri, Mar 11, 2011 at 5:01 PM, Tixy <tixy@yxit.co.uk> wrote:
> > Hello All
> >
> > I'm about to start work on getting kprobes working with thumb2.
> >
> > One of the issues I have is that when probes are placed onto
> > conditionally executed instructions in a IT block, they may not fire if
> > the condition is not met. This is because on ARM we use invalid
> > instructions for breakpoints, and the ARM ARM says:
> >
> > ?"it is IMPLEMENTATION DEFINED whether the instruction executes as a
> > ? NOP or causes an Undefined Instruction exception"
> >
> > This is a similar issue to that already encountered by GDB [1][2]
> >
> > If we take this code as an example...
> >
> > probe1:
> > if(condition) {
> > probe2:
> > ? ?some_code;
> > }
> >
> > It seams reasonable at first sight that probe2 would only fire if the
> > condition is true. This will always be the case if the compiler
> > generates test-and-branch code, but if it generates conditionally
> > executed instructions for 'some_code' then it gets complicated...
> >
> > The current arm kprobes implementation will always fire probe2 because
> 
> Well, actually it's somewhat unpredictable whether/when a probe on
> probe2 will fire, because it depends on the code generated by the
> compiler.  The compiler could choose to use a conditional instruction
> at probe2, or it could conditionally branch round it, even in ARM.

And we definitely don't want that.

> Or, the whole conditional might disappear to be replaced with an
> unconditional instruction sequence that has the same overall effect.

Sure, but this is an extreme case which is not specific to ARM or 
Thumb2.  Such a situation could happen on x86 as well.  Let's not worry 
about that and keep ourselves to those cases we have control over.

> > it uses unconditional instructions for its breakpoints. With thumb
> > instructions we can't force unconditional execution, so we would have an
> > 'implementation defined' situation whether it would fire or not when the
> > condition is false. (Thought you would hope it would be consistent on a
> > particular device.)
> >
> > Some options for dealing with this, in increasing order of
> > complexity...
> >
> > 1. Accept the situation as described.
> >
> > 2. Change arm probes to use conditional instructions so we would
> > (hopefully) have consistent undefined behaviour in both arm and thumb
> > code. (If that isn't an oxymoron :-)
> >
> > 3. Do 2, and modify kprobe_handler to test for false firings (breakpoint
> > when condition false) and not execute the probe's callback functions in
> > these cases. E.g. consistently make probe2 appear to not fire when
> > condition is false.
> 
> My preference would be for option (1) or (3).  For (3), we could
> choose to extend this behaviour to cover the existing ARM
> implementation as well as Thumb, which could be a tidier and more
> consistent approach.  This seems to be the "right" thing, since it
> means kprobes never fire for real on instructions which are logically
> not executed, no matter how the compiler (or human) implemented the
> conditionality.  Currently, ARM kprobes can fire on instructions which
> would fail their condition check, which might be considered wrong.

Definitely #3.

In the ARM case, this can be achieved by saving the condition code 
of the replaced instruction when installing a probe, and test it 
against the CPSR value from the interrupted state.  If the condition is 
false then just skip the native emulation of the resulting NOP and 
ignore the probe callback.  In the Thumb2 case the IT state in the CPSR 
would indicate right away if the probe should be ignored.

> Alternatively, we could avoid fixing what isn't broken and leave the
> ARM implementation unchanged.

I wouldn't call the ARM implementation not broken.  It just happens that 
probes are typically installed at the beginning of functions and no 
conditional instructions are normally placed there.  This would explain 
why no one reported this issue so far.

> Since the compiler will implement some
> different instruction-level optimisations in Thumb compared with ARM,
> it may not make sense to try to make the kprobe firing behaviour
> behave exactly the same around conditional code in both instruction
> sets -- because the code generation differences may always cause the
> observed behaviour to be different anyway, just as might happen if you
> switch to a newer compiler or use a different -march/-mtune
> combination.

That doesn't matter.  We should respect the expected execution flow at 
the probe location irrespective of any compiler optimization.  It is 
true that code generation might be different between different compilers 
and options, but that's not our problem as long as we don't introduce 
more randomness.  And it happens that making this work properly is 
trivial with Thumb2.  And in ARM mode, the most complex task is to 
determine if a given instruction is conditionally executable or not.


Nicolas

[RFC] kprobes with thumb2 conditional code

[Dave Martin]

On Thu, Mar 17, 2011 at 10:46 PM, Nicolas Pitre
<nicolas.pitre@linaro.org> wrote:
> On Thu, 17 Mar 2011, Dave Martin wrote:
>
>> On Fri, Mar 11, 2011 at 5:01 PM, Tixy <tixy@yxit.co.uk> wrote:
>> > Hello All
>> >
>> > I'm about to start work on getting kprobes working with thumb2.
>> >
>> > One of the issues I have is that when probes are placed onto
>> > conditionally executed instructions in a IT block, they may not fire if
>> > the condition is not met. This is because on ARM we use invalid
>> > instructions for breakpoints, and the ARM ARM says:
>> >
>> > ?"it is IMPLEMENTATION DEFINED whether the instruction executes as a
>> > ? NOP or causes an Undefined Instruction exception"
>> >
>> > This is a similar issue to that already encountered by GDB [1][2]
>> >
>> > If we take this code as an example...
>> >
>> > probe1:
>> > if(condition) {
>> > probe2:
>> > ? ?some_code;
>> > }
>> >
>> > It seams reasonable at first sight that probe2 would only fire if the
>> > condition is true. This will always be the case if the compiler
>> > generates test-and-branch code, but if it generates conditionally
>> > executed instructions for 'some_code' then it gets complicated...
>> >
>> > The current arm kprobes implementation will always fire probe2 because
>>
>> Well, actually it's somewhat unpredictable whether/when a probe on
>> probe2 will fire, because it depends on the code generated by the
>> compiler. ?The compiler could choose to use a conditional instruction
>> at probe2, or it could conditionally branch round it, even in ARM.
>
> And we definitely don't want that.
>
>> Or, the whole conditional might disappear to be replaced with an
>> unconditional instruction sequence that has the same overall effect.
>
> Sure, but this is an extreme case which is not specific to ARM or
> Thumb2. ?Such a situation could happen on x86 as well. ?Let's not worry
> about that and keep ourselves to those cases we have control over.
>
>> > it uses unconditional instructions for its breakpoints. With thumb
>> > instructions we can't force unconditional execution, so we would have an
>> > 'implementation defined' situation whether it would fire or not when the
>> > condition is false. (Thought you would hope it would be consistent on a
>> > particular device.)
>> >
>> > Some options for dealing with this, in increasing order of
>> > complexity...
>> >
>> > 1. Accept the situation as described.
>> >
>> > 2. Change arm probes to use conditional instructions so we would
>> > (hopefully) have consistent undefined behaviour in both arm and thumb
>> > code. (If that isn't an oxymoron :-)
>> >
>> > 3. Do 2, and modify kprobe_handler to test for false firings (breakpoint
>> > when condition false) and not execute the probe's callback functions in
>> > these cases. E.g. consistently make probe2 appear to not fire when
>> > condition is false.
>>
>> My preference would be for option (1) or (3). ?For (3), we could
>> choose to extend this behaviour to cover the existing ARM
>> implementation as well as Thumb, which could be a tidier and more
>> consistent approach. ?This seems to be the "right" thing, since it
>> means kprobes never fire for real on instructions which are logically
>> not executed, no matter how the compiler (or human) implemented the
>> conditionality. ?Currently, ARM kprobes can fire on instructions which
>> would fail their condition check, which might be considered wrong.
>
> Definitely #3.
>
> In the ARM case, this can be achieved by saving the condition code
> of the replaced instruction when installing a probe, and test it
> against the CPSR value from the interrupted state. ?If the condition is
> false then just skip the native emulation of the resulting NOP and
> ignore the probe callback. ?In the Thumb2 case the IT state in the CPSR
> would indicate right away if the probe should be ignored.

We could also insert a conditional undefined instruction for the probe
-- this may reduce the number of false positives, but it depends on
the hardware implementation.
Since kprobes needs to do explicit condition code checks anyway, use
of conditional undefs doesn't add any functionality, however.

>
>> Alternatively, we could avoid fixing what isn't broken and leave the
>> ARM implementation unchanged.
>
> I wouldn't call the ARM implementation not broken. ?It just happens that
> probes are typically installed at the beginning of functions and no
> conditional instructions are normally placed there. ?This would explain
> why no one reported this issue so far.

Well, fair enough -- if there's appetite for tidying this up, and we
don't think it will break anything anyone else is doing, then I'd say
fixing it is a good idea.

>
>> Since the compiler will implement some
>> different instruction-level optimisations in Thumb compared with ARM,
>> it may not make sense to try to make the kprobe firing behaviour
>> behave exactly the same around conditional code in both instruction
>> sets -- because the code generation differences may always cause the
>> observed behaviour to be different anyway, just as might happen if you
>> switch to a newer compiler or use a different -march/-mtune
>> combination.
>
> That doesn't matter. ?We should respect the expected execution flow at
> the probe location irrespective of any compiler optimization. ?It is
> true that code generation might be different between different compilers
> and options, but that's not our problem as long as we don't introduce
> more randomness. ?And it happens that making this work properly is
> trivial with Thumb2. ?And in ARM mode, the most complex task is to
> determine if a given instruction is conditionally executable or not.

Note that in Thumb, not everything that's conditional is inside an IT
block: there are a couple of conditional branch encodings which have
an explicit condition code.

It's still a pretty simple decoding task, but not quite as simple as
the ARM case.

Cheers
---Dave

[RFC] kprobes with thumb2 conditional code

[Tixy]

I would like to revisit the discussion about how to handle kprobes
placed on conditionally executed instructions...

On Thu, 2011-03-17 at 18:46 -0400, Nicolas Pitre wrote: 
> On Thu, 17 Mar 2011, Dave Martin wrote:
> > On Fri, Mar 11, 2011 at 5:01 PM, Tixy <tixy@yxit.co.uk> wrote:
> > > it uses unconditional instructions for its breakpoints. With thumb
> > > instructions we can't force unconditional execution, so we would have an
> > > 'implementation defined' situation whether it would fire or not when the
> > > condition is false. (Thought you would hope it would be consistent on a
> > > particular device.)
> > >
> > > Some options for dealing with this, in increasing order of
> > > complexity...
> > >
> > > 1. Accept the situation as described.
> > >
> > > 2. Change arm probes to use conditional instructions so we would
> > > (hopefully) have consistent undefined behaviour in both arm and thumb
> > > code. (If that isn't an oxymoron :-)
> > >
> > > 3. Do 2, and modify kprobe_handler to test for false firings (breakpoint
> > > when condition false) and not execute the probe's callback functions in
> > > these cases. E.g. consistently make probe2 appear to not fire when
> > > condition is false.
> > 
> > My preference would be for option (1) or (3).  For (3), we could
> > choose to extend this behaviour to cover the existing ARM
> > implementation as well as Thumb, which could be a tidier and more
> > consistent approach.  This seems to be the "right" thing, since it
> > means kprobes never fire for real on instructions which are logically
> > not executed, no matter how the compiler (or human) implemented the
> > conditionality.  Currently, ARM kprobes can fire on instructions which
> > would fail their condition check, which might be considered wrong.
> 
> Definitely #3.
> 
> In the ARM case, this can be achieved by saving the condition code 
> of the replaced instruction when installing a probe, and test it 
> against the CPSR value from the interrupted state.  If the condition is 
> false then just skip the native emulation of the resulting NOP and 
> ignore the probe callback.  In the Thumb2 case the IT state in the CPSR 
> would indicate right away if the probe should be ignored.

If we don't fire a probe because a conditional instruction wouldn't be
executed then for branch instructions we only fire when branches are
taken. So, with things like loops...

1:  movs r0, r0, asl #1
    bpl 1b

the probe would fire on every iteration of the loop except the last.
This inconsistency seems bad to me.

We could make exceptions for branches, and every other instruction which
can changes PC, but we would still have the issue that we can't force
unconditional firing of Thumb branches in an IT block.

There doesn't appear to be a single satisfactory solution. 

Perhaps we should do option #1, i.e. don't change anything and have
probes always firing except when breakpoints are missed in IT blocks due
to the condition being false.

Or looking at it another way, leave things as the are until someone
comes up with a real-life use-case which indicates that a change is
needed.

-- 
Tixy 

[RFC] kprobes with thumb2 conditional code

[Dave Martin]

On Wed, Jun 15, 2011 at 10:45:38AM +0100, Tixy wrote:
> I would like to revisit the discussion about how to handle kprobes
> placed on conditionally executed instructions...
> 
> On Thu, 2011-03-17 at 18:46 -0400, Nicolas Pitre wrote: 
> > On Thu, 17 Mar 2011, Dave Martin wrote:
> > > On Fri, Mar 11, 2011 at 5:01 PM, Tixy <tixy@yxit.co.uk> wrote:
> > > > it uses unconditional instructions for its breakpoints. With thumb
> > > > instructions we can't force unconditional execution, so we would have an
> > > > 'implementation defined' situation whether it would fire or not when the
> > > > condition is false. (Thought you would hope it would be consistent on a
> > > > particular device.)
> > > >
> > > > Some options for dealing with this, in increasing order of
> > > > complexity...
> > > >
> > > > 1. Accept the situation as described.
> > > >
> > > > 2. Change arm probes to use conditional instructions so we would
> > > > (hopefully) have consistent undefined behaviour in both arm and thumb
> > > > code. (If that isn't an oxymoron :-)
> > > >
> > > > 3. Do 2, and modify kprobe_handler to test for false firings (breakpoint
> > > > when condition false) and not execute the probe's callback functions in
> > > > these cases. E.g. consistently make probe2 appear to not fire when
> > > > condition is false.
> > > 
> > > My preference would be for option (1) or (3).  For (3), we could
> > > choose to extend this behaviour to cover the existing ARM
> > > implementation as well as Thumb, which could be a tidier and more
> > > consistent approach.  This seems to be the "right" thing, since it
> > > means kprobes never fire for real on instructions which are logically
> > > not executed, no matter how the compiler (or human) implemented the
> > > conditionality.  Currently, ARM kprobes can fire on instructions which
> > > would fail their condition check, which might be considered wrong.
> > 
> > Definitely #3.
> > 
> > In the ARM case, this can be achieved by saving the condition code 
> > of the replaced instruction when installing a probe, and test it 
> > against the CPSR value from the interrupted state.  If the condition is 
> > false then just skip the native emulation of the resulting NOP and 
> > ignore the probe callback.  In the Thumb2 case the IT state in the CPSR 
> > would indicate right away if the probe should be ignored.
> 
> If we don't fire a probe because a conditional instruction wouldn't be
> executed then for branch instructions we only fire when branches are
> taken. So, with things like loops...
> 
> 1:  movs r0, r0, asl #1
>     bpl 1b
> 
> the probe would fire on every iteration of the loop except the last.
> This inconsistency seems bad to me.
> 
> We could make exceptions for branches, and every other instruction which
> can changes PC, but we would still have the issue that we can't force
> unconditional firing of Thumb branches in an IT block.

I suspect that it's more common to see conditional branches outside IT
blocks than inside, due to the different encodings available and the
fact that it's most common for a conditional branch to follow some
unconditional instruction to set up the condition.

According to my hacky measurements, only about 2% of the conditional
branches in a typical vmlinux image are inside IT blocks.  So if we
don't solve this case it may not be catastrophic.

> There doesn't appear to be a single satisfactory solution. 

Since the instruction stream can be reliably decoded _forwards_, we
could trap on the branch-not-taken case by setting an additional probe
after the affected branch.

Where branches appear in IT blocks, they're not allowed to be anywhere
except at the end of the block, so the next instruction is either outside
the block, or is an IT instruction itself (in which case we can still
set a probe on it).  In valid code there will always be a next instruction,
since the CPU will fall through the branch if the condition is false.

That would deal with almost all cases, but it adds a bit of complexity
so I'm not convinced it's worth it.

> 
> Perhaps we should do option #1, i.e. don't change anything and have
> probes always firing except when breakpoints are missed in IT blocks due
> to the condition being false.
> 
> Or looking at it another way, leave things as the are until someone
> comes up with a real-life use-case which indicates that a change is
> needed.

We could ask the question of what a developer is trying to detect when
a kprobe is set.

It would either be:

	a) does the PC logically reach this address?
	b) is this instruction logically executed?

Currently, the proposed implementation (#3) follows interpretation (b).

We cannot reliably implement (a) because the CPU may effectively skip
over IT blocks rather than considering each instruction in turn for
potential faulting; i.e., the CPU does not reliably answer question (a)
for us.  Notions like where the PC is at a particular time and the 
exact locations it visits usually can have pretty fuzzy meaning once
you get into actual CPU implementation; so the ARM architecture doesn't
commit CPU implementors to meaningfully answering question (a) in all
situations -- which is the fundamental difficulty here, since this is
the question people usually expect to be answered when they set a
breakpoint.

So, we have a choice between a consistent but sometimes counterintuitive
approach (b), or an inconsistent (and hence sometimes counterintuitive)
approach approximating (a).  The latter case will be more complex to
implement, and I'm not sure of the benefits.

We could make a special exception to the false-firing rule for branches,
but that raises the question of which other instructions should be
excepted.  Efectively, this means that we "guess" based on the actual
instruction whether the developer meant (a) or (b) when setting their
kprobe.  Unfortunately I don't think there's a correct answer to
that question magically, unless the API has a way for the developer
to actually state this.  It doesn't, AFAICT.

Apart from simple things like breaking on entry to a function,
I think we can (and should) expect developers using kprobes in an arch-
specific manner to understand what they're doing.  For example,
set your probe on the start of a loop, and the first unconditional
instruction following the looping branch, not on the looping branch
itself.

Either way, we should of course document clearly the implemented
kprobe firing behaviour so that people understand how to work with it.

Those are just my thoughts ... I don't think there's any single
correct answer to how to implement this.  Going for the simplest
reasonable-looking approach and changing it later if and only if
this causes problems for people seems the best approach in such cases.

If you think that that #3 is not the simplest reasonable-looking
approach after all, then I guess we can think about alternatives.

---Cheers

[RFC] kprobes with thumb2 conditional code

[Tixy]

On Wed, 2011-06-15 at 12:16 +0100, Dave Martin wrote:
> On Wed, Jun 15, 2011 at 10:45:38AM +0100, Tixy wrote:
> > I would like to revisit the discussion about how to handle kprobes
> > placed on conditionally executed instructions...
> > 
> > On Thu, 2011-03-17 at 18:46 -0400, Nicolas Pitre wrote: 
> > > On Thu, 17 Mar 2011, Dave Martin wrote:
> > > > On Fri, Mar 11, 2011 at 5:01 PM, Tixy <tixy@yxit.co.uk> wrote:
> > > > > it uses unconditional instructions for its breakpoints. With thumb
> > > > > instructions we can't force unconditional execution, so we would have an
> > > > > 'implementation defined' situation whether it would fire or not when the
> > > > > condition is false. (Thought you would hope it would be consistent on a
> > > > > particular device.)
> > > > >
> > > > > Some options for dealing with this, in increasing order of
> > > > > complexity...
> > > > >
> > > > > 1. Accept the situation as described.
> > > > >
> > > > > 2. Change arm probes to use conditional instructions so we would
> > > > > (hopefully) have consistent undefined behaviour in both arm and thumb
> > > > > code. (If that isn't an oxymoron :-)
> > > > >
> > > > > 3. Do 2, and modify kprobe_handler to test for false firings (breakpoint
> > > > > when condition false) and not execute the probe's callback functions in
> > > > > these cases. E.g. consistently make probe2 appear to not fire when
> > > > > condition is false.
> > > > 
> > > > My preference would be for option (1) or (3).  For (3), we could
> > > > choose to extend this behaviour to cover the existing ARM
> > > > implementation as well as Thumb, which could be a tidier and more
> > > > consistent approach.  This seems to be the "right" thing, since it
> > > > means kprobes never fire for real on instructions which are logically
> > > > not executed, no matter how the compiler (or human) implemented the
> > > > conditionality.  Currently, ARM kprobes can fire on instructions which
> > > > would fail their condition check, which might be considered wrong.
> > > 
> > > Definitely #3.
> > > 
> > > In the ARM case, this can be achieved by saving the condition code 
> > > of the replaced instruction when installing a probe, and test it 
> > > against the CPSR value from the interrupted state.  If the condition is 
> > > false then just skip the native emulation of the resulting NOP and 
> > > ignore the probe callback.  In the Thumb2 case the IT state in the CPSR 
> > > would indicate right away if the probe should be ignored.
> > 
> > If we don't fire a probe because a conditional instruction wouldn't be
> > executed then for branch instructions we only fire when branches are
> > taken. So, with things like loops...
> > 
> > 1:  movs r0, r0, asl #1
> >     bpl 1b
> > 
> > the probe would fire on every iteration of the loop except the last.
> > This inconsistency seems bad to me.
> > 
> > We could make exceptions for branches, and every other instruction which
> > can changes PC, but we would still have the issue that we can't force
> > unconditional firing of Thumb branches in an IT block.
> 
> I suspect that it's more common to see conditional branches outside IT
> blocks than inside, due to the different encodings available and the
> fact that it's most common for a conditional branch to follow some
> unconditional instruction to set up the condition.
> 
> According to my hacky measurements, only about 2% of the conditional
> branches in a typical vmlinux image are inside IT blocks.  So if we
> don't solve this case it may not be catastrophic.
> 
> > There doesn't appear to be a single satisfactory solution. 
> 
> Since the instruction stream can be reliably decoded _forwards_, we
> could trap on the branch-not-taken case by setting an additional probe
> after the affected branch.
> 
> Where branches appear in IT blocks, they're not allowed to be anywhere
> except at the end of the block, so the next instruction is either outside
> the block, or is an IT instruction itself (in which case we can still
> set a probe on it).  In valid code there will always be a next instruction,
> since the CPU will fall through the branch if the condition is false.

But, if we are asked to probe a normal unconditional branch, we don't
know if its in an IT block or not. E.g. the branch instruction in this:

	cmp	r1, #0
	itt	eq
	moveq	r0, #1
	beq	somewhere
	ldr	r0, [r1]

and in this:

	mov	r0, #1
	b	somewhere
	.word	some_literal_pool_value

are the same instruction, the 'beq' syntax is just for readability.

The real Thumb conditional branch instructions aren't allowed in IT
blocks. It was when I implemented emulation of these that I began to
have second thoughts about the approach to conditional instructions.

> That would deal with almost all cases, but it adds a bit of complexity
> so I'm not convinced it's worth it.

Too complex to go there ;-)

<big snip>
> Either way, we should of course document clearly the implemented
> kprobe firing behaviour so that people understand how to work with it.
> 
> Those are just my thoughts ... I don't think there's any single
> correct answer to how to implement this.  Going for the simplest
> reasonable-looking approach and changing it later if and only if
> this causes problems for people seems the best approach in such cases.
> 
> If you think that that #3 is not the simplest reasonable-looking
> approach after all, then I guess we can think about alternatives.

I'm now convinced that #3 is best after all. It is the only thing we can
get simple, consistent rules for. I.e.

        "Kprobes on conditional instructions don't trigger when the
        condition is false. For conditional branches, this means that
        they don't trigger in the branch not taken case."

-- 
Tixy

[RFC] kprobes with thumb2 conditional code

[Dave Martin]

On Wed, Jun 15, 2011 at 01:24:35PM +0100, Tixy wrote:
> On Wed, 2011-06-15 at 12:16 +0100, Dave Martin wrote:

[...]

> > Where branches appear in IT blocks, they're not allowed to be anywhere
> > except at the end of the block, so the next instruction is either outside
> > the block, or is an IT instruction itself (in which case we can still
> > set a probe on it).  In valid code there will always be a next instruction,
> > since the CPU will fall through the branch if the condition is false.
> 
> But, if we are asked to probe a normal unconditional branch, we don't
> know if its in an IT block or not. E.g. the branch instruction in this:
> 
> 	cmp	r1, #0
> 	itt	eq
> 	moveq	r0, #1
> 	beq	somewhere
> 	ldr	r0, [r1]
> 
> and in this:
> 
> 	mov	r0, #1
> 	b	somewhere
> 	.word	some_literal_pool_value
> 
> are the same instruction, the 'beq' syntax is just for readability.

Good point, I understand that those instructions are encoded the same, but
I hadn't considered the possibility that the following bytes will contain data
instead of instructions... though actually that will be common-ish after
unconditional branches.

Attempting to set a probe in data will of course be bad, since it may
lead to undetectable corruption.  Ugh.

(Hard to work around, unless you really want to implement full
instruction tracing or watchpoints.  OK, let's not do that! ;) 

> The real Thumb conditional branch instructions aren't allowed in IT
> blocks. It was when I implemented emulation of these that I began to
> have second thoughts about the approach to conditional instructions.
> 
> > That would deal with almost all cases, but it adds a bit of complexity
> > so I'm not convinced it's worth it.
> 
> Too complex to go there ;-)

Yup, I agree.

[...]

> > If you think that that #3 is not the simplest reasonable-looking
> > approach after all, then I guess we can think about alternatives.
> 
> I'm now convinced that #3 is best after all. It is the only thing we can
> get simple, consistent rules for. I.e.
> 
>         "Kprobes on conditional instructions don't trigger when the
>         condition is false. For conditional branches, this means that
>         they don't trigger in the branch not taken case."

Plus it's fairly striaghtforward to implement, so shouldn't waste effort.

As long as people don't get unpleasant surprises from setting a probe
on a function entry point, I think that's OK as an approach.

I think a real function generated by the compiler will never have a
conditional instruction at its entry point, since the ABI permits the
condition flags to be clobbered across procedure calls and returns
anyway... so the result of such an instruction would be indeterminate.
So a probe set on an external function label should always fire even
with the proposed implementation.

So #3 sounds good for me.

Cheers
---Dave