[RFC] kprobe'ing conditionally executed instructions

[RFC] kprobe'ing conditionally executed instructions

[David Long]

There is a moderate amount of code already in kprobes on ARM and the 
current ARMv8 patch to deal with conditional execution of instructions. 
One aspect of how this is handled is that instructions that fail their 
predicate and are not (technically) executed are also not treated as a 
hit kprobe. Steve Capper has suggested that the probe handling should 
still take place because we stepped through the instruction even if it 
was effectively a nop.  This would be a significant change in how it 
currently works on 32-bit ARM, and a change in the patch for ARMv8 
(although it's not likely to be much of a change in the kernel code).

I need input on this.  Do people have opinions?

-dl

[RFC] kprobe'ing conditionally executed instructions

[David Long]

There is a moderate amount of code already in kprobes on ARM and the 
current ARMv8 patch to deal with conditional execution of instructions. 
One aspect of how this is handled is that instructions that fail their 
predicate and are not (technically) executed are also not treated as a 
hit kprobe. Steve Capper has suggested that the probe handling should 
still take place because we stepped through the instruction even if it 
was effectively a nop.  This would be a significant change in how it 
currently works on 32-bit ARM, and a change in the patch for ARMv8 
(although it's not likely to be much of a change in the kernel code).

I need input on this.  Do people have opinions?

-dl

[RFC] kprobe'ing conditionally executed instructions

[Steve Capper]

On 11 December 2015 at 13:05, David Long <dave.long@linaro.org> wrote:
> There is a moderate amount of code already in kprobes on ARM and the current
> ARMv8 patch to deal with conditional execution of instructions. One aspect
> of how this is handled is that instructions that fail their predicate and
> are not (technically) executed are also not treated as a hit kprobe. Steve
> Capper has suggested that the probe handling should still take place because
> we stepped through the instruction even if it was effectively a nop.  This
> would be a significant change in how it currently works on 32-bit ARM, and a
> change in the patch for ARMv8 (although it's not likely to be much of a
> change in the kernel code).
>
> I need input on this.  Do people have opinions?

Hi David,
Thanks for posting this.

Just to clarify the reasoning behind my suggestion for kprobes always
being hit was to achieve parity with x86.

I highlighted an example of discrepancy in behaviour between arm64 and
x86 in the following email:
http://lists.infradead.org/pipermail/linux-arm-kernel/2015-August/364201.html

Cheers,
--
Steve

Re: [RFC] kprobe'ing conditionally executed instructions

[Steve Capper]

On 11 December 2015 at 13:05, David Long <dave.long@linaro.org> wrote:
> There is a moderate amount of code already in kprobes on ARM and the current
> ARMv8 patch to deal with conditional execution of instructions. One aspect
> of how this is handled is that instructions that fail their predicate and
> are not (technically) executed are also not treated as a hit kprobe. Steve
> Capper has suggested that the probe handling should still take place because
> we stepped through the instruction even if it was effectively a nop.  This
> would be a significant change in how it currently works on 32-bit ARM, and a
> change in the patch for ARMv8 (although it's not likely to be much of a
> change in the kernel code).
>
> I need input on this.  Do people have opinions?

Hi David,
Thanks for posting this.

Just to clarify the reasoning behind my suggestion for kprobes always
being hit was to achieve parity with x86.

I highlighted an example of discrepancy in behaviour between arm64 and
x86 in the following email:
http://lists.infradead.org/pipermail/linux-arm-kernel/2015-August/364201.html

Cheers,
--
Steve

[RFC] kprobe'ing conditionally executed instructions

[Jon Medhurst (Tixy)]

On Fri, 2015-12-11 at 00:05 -0500, David Long wrote:
> There is a moderate amount of code already in kprobes on ARM and the 
> current ARMv8 patch to deal with conditional execution of instructions. 
> One aspect of how this is handled is that instructions that fail their 
> predicate and are not (technically) executed are also not treated as a 
> hit kprobe. Steve Capper has suggested that the probe handling should 
> still take place because we stepped through the instruction even if it 
> was effectively a nop.  This would be a significant change in how it 
> currently works on 32-bit ARM

32-bit ARM uses undefined instructions for kprobe 'breakpoints' and the
ARM ARM says it's implementation defined behaviour whether these
generate exceptions or not, i.e. whether the kprobe handler will be
called. You could say that we could always use unconditional
breakpoints, but this doesn't work with thumb where the instruction
could be in an IT block. So, the only way to have consistent behaviour
on all platforms is to not call kprobe handlers if condition check
fails. Which is the reason for the current implementation's design.

Also, if we change the current implementation as suggested, then looking
at things from a source code point of view...

if (test)
	foo()
else
	bar();

If you put a probe on the call to foo() and the compiler uses a branch
instruction for the test you're never going to hit the probe
fortest==false. But if it decides to use conditional instructions it
will (on some CPU implementations). And the choice between
branch/conditional instructions probably varies between GCC version and
kernel configs.

So again, IMO, the current kprobes implementation leads to consistency.

-- 
Tixy 

Re: [RFC] kprobe'ing conditionally executed instructions

[Jon Medhurst (Tixy)]

On Fri, 2015-12-11 at 00:05 -0500, David Long wrote:
> There is a moderate amount of code already in kprobes on ARM and the 
> current ARMv8 patch to deal with conditional execution of instructions. 
> One aspect of how this is handled is that instructions that fail their 
> predicate and are not (technically) executed are also not treated as a 
> hit kprobe. Steve Capper has suggested that the probe handling should 
> still take place because we stepped through the instruction even if it 
> was effectively a nop.  This would be a significant change in how it 
> currently works on 32-bit ARM

32-bit ARM uses undefined instructions for kprobe 'breakpoints' and the
ARM ARM says it's implementation defined behaviour whether these
generate exceptions or not, i.e. whether the kprobe handler will be
called. You could say that we could always use unconditional
breakpoints, but this doesn't work with thumb where the instruction
could be in an IT block. So, the only way to have consistent behaviour
on all platforms is to not call kprobe handlers if condition check
fails. Which is the reason for the current implementation's design.

Also, if we change the current implementation as suggested, then looking
at things from a source code point of view...

if (test)
	foo()
else
	bar();

If you put a probe on the call to foo() and the compiler uses a branch
instruction for the test you're never going to hit the probe
fortest==false. But if it decides to use conditional instructions it
will (on some CPU implementations). And the choice between
branch/conditional instructions probably varies between GCC version and
kernel configs.

So again, IMO, the current kprobes implementation leads to consistency.

-- 
Tixy 

[RFC] kprobe'ing conditionally executed instructions

[Russell King - ARM Linux]

On Fri, Dec 11, 2015 at 10:27:13AM +0000, Jon Medhurst (Tixy) wrote:
> On Fri, 2015-12-11 at 00:05 -0500, David Long wrote:
> > There is a moderate amount of code already in kprobes on ARM and the 
> > current ARMv8 patch to deal with conditional execution of instructions. 
> > One aspect of how this is handled is that instructions that fail their 
> > predicate and are not (technically) executed are also not treated as a 
> > hit kprobe. Steve Capper has suggested that the probe handling should 
> > still take place because we stepped through the instruction even if it 
> > was effectively a nop.  This would be a significant change in how it 
> > currently works on 32-bit ARM
> 
> 32-bit ARM uses undefined instructions for kprobe 'breakpoints' and the
> ARM ARM says it's implementation defined behaviour whether these
> generate exceptions or not, i.e. whether the kprobe handler will be
> called.

There are two classes of undefined instructions.  There are those which
fall into the above category, and there are those which are guaranteed
to raise an exception.  We should always be using the guaranteed ones,
not the other set.

-- 
RMK's Patch system: http://www.arm.linux.org.uk/developer/patches/
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

Re: [RFC] kprobe'ing conditionally executed instructions

[Russell King - ARM Linux]

On Fri, Dec 11, 2015 at 10:27:13AM +0000, Jon Medhurst (Tixy) wrote:
> On Fri, 2015-12-11 at 00:05 -0500, David Long wrote:
> > There is a moderate amount of code already in kprobes on ARM and the 
> > current ARMv8 patch to deal with conditional execution of instructions. 
> > One aspect of how this is handled is that instructions that fail their 
> > predicate and are not (technically) executed are also not treated as a 
> > hit kprobe. Steve Capper has suggested that the probe handling should 
> > still take place because we stepped through the instruction even if it 
> > was effectively a nop.  This would be a significant change in how it 
> > currently works on 32-bit ARM
> 
> 32-bit ARM uses undefined instructions for kprobe 'breakpoints' and the
> ARM ARM says it's implementation defined behaviour whether these
> generate exceptions or not, i.e. whether the kprobe handler will be
> called.

There are two classes of undefined instructions.  There are those which
fall into the above category, and there are those which are guaranteed
to raise an exception.  We should always be using the guaranteed ones,
not the other set.

-- 
RMK's Patch system: http://www.arm.linux.org.uk/developer/patches/
FTTC broadband for 0.8mile line: currently at 9.6Mbps down 400kbps up
according to speedtest.net.

[RFC] kprobe'ing conditionally executed instructions

[Jon Medhurst (Tixy)]

On Fri, 2015-12-11 at 10:34 +0000, Russell King - ARM Linux wrote:
> On Fri, Dec 11, 2015 at 10:27:13AM +0000, Jon Medhurst (Tixy) wrote:
> > On Fri, 2015-12-11 at 00:05 -0500, David Long wrote:
> > > There is a moderate amount of code already in kprobes on ARM and the 
> > > current ARMv8 patch to deal with conditional execution of instructions. 
> > > One aspect of how this is handled is that instructions that fail their 
> > > predicate and are not (technically) executed are also not treated as a 
> > > hit kprobe. Steve Capper has suggested that the probe handling should 
> > > still take place because we stepped through the instruction even if it 
> > > was effectively a nop.  This would be a significant change in how it 
> > > currently works on 32-bit ARM
> > 
> > 32-bit ARM uses undefined instructions for kprobe 'breakpoints' and the
> > ARM ARM says it's implementation defined behaviour whether these
> > generate exceptions or not, i.e. whether the kprobe handler will be
> > called.
> 
> There are two classes of undefined instructions.  There are those which
> fall into the above category, and there are those which are guaranteed
> to raise an exception.  We should always be using the guaranteed ones,
> not the other set.

I wonder if I'm going senile or have been subject to having the ARM ARM
evolve under me. I could swear we used instructions that were defined as
undefined (so to speak) and that conditional versions of undefined
instructions were UNPREDICTABLE. However, checking the ARM ARM again I
see those instruction encodings are for the BKPT instruction which says:

  Breakpoint causes a software breakpoint to occur.
  Breakpoint is always unconditional, even when inside an IT block.

So, my previous statements about not being able to implement the
proposed kprobe changes consistently aren't true.

-- 
Tixy

Re: [RFC] kprobe'ing conditionally executed instructions

[Jon Medhurst (Tixy)]

On Fri, 2015-12-11 at 10:34 +0000, Russell King - ARM Linux wrote:
> On Fri, Dec 11, 2015 at 10:27:13AM +0000, Jon Medhurst (Tixy) wrote:
> > On Fri, 2015-12-11 at 00:05 -0500, David Long wrote:
> > > There is a moderate amount of code already in kprobes on ARM and the 
> > > current ARMv8 patch to deal with conditional execution of instructions. 
> > > One aspect of how this is handled is that instructions that fail their 
> > > predicate and are not (technically) executed are also not treated as a 
> > > hit kprobe. Steve Capper has suggested that the probe handling should 
> > > still take place because we stepped through the instruction even if it 
> > > was effectively a nop.  This would be a significant change in how it 
> > > currently works on 32-bit ARM
> > 
> > 32-bit ARM uses undefined instructions for kprobe 'breakpoints' and the
> > ARM ARM says it's implementation defined behaviour whether these
> > generate exceptions or not, i.e. whether the kprobe handler will be
> > called.
> 
> There are two classes of undefined instructions.  There are those which
> fall into the above category, and there are those which are guaranteed
> to raise an exception.  We should always be using the guaranteed ones,
> not the other set.

I wonder if I'm going senile or have been subject to having the ARM ARM
evolve under me. I could swear we used instructions that were defined as
undefined (so to speak) and that conditional versions of undefined
instructions were UNPREDICTABLE. However, checking the ARM ARM again I
see those instruction encodings are for the BKPT instruction which says:

  Breakpoint causes a software breakpoint to occur.
  Breakpoint is always unconditional, even when inside an IT block.

So, my previous statements about not being able to implement the
proposed kprobe changes consistently aren't true.

-- 
Tixy

[RFC] kprobe'ing conditionally executed instructions

[William Cohen]

On 12/11/2015 12:05 AM, David Long wrote:
> There is a moderate amount of code already in kprobes on ARM and the current ARMv8 patch to deal with conditional execution of instructions. One aspect of how this is handled is that instructions that fail their predicate and are not (technically) executed are also not treated as a hit kprobe. Steve Capper has suggested that the probe handling should still take place because we stepped through the instruction even if it was effectively a nop.  This would be a significant change in how it currently works on 32-bit ARM, and a change in the patch for ARMv8 (although it's not likely to be much of a change in the kernel code).
> 
> I need input on this.  Do people have opinions?
> 
> -dl
> 

Hi Dave,

Conditionally executing the kprobes would violate the assumptions made for perf and systemtap collecting data. Even if the instruction is predicated and treated as a NOP it should still reliably trigger the kprobe.  However, for efficiency the simulation/emulation/single-step of the instruction could be skipped if the instruction is known to have no change on the machine state other than changing the program counter.

-Will Cohen

Re: [RFC] kprobe'ing conditionally executed instructions

[William Cohen]

On 12/11/2015 12:05 AM, David Long wrote:
> There is a moderate amount of code already in kprobes on ARM and the current ARMv8 patch to deal with conditional execution of instructions. One aspect of how this is handled is that instructions that fail their predicate and are not (technically) executed are also not treated as a hit kprobe. Steve Capper has suggested that the probe handling should still take place because we stepped through the instruction even if it was effectively a nop.  This would be a significant change in how it currently works on 32-bit ARM, and a change in the patch for ARMv8 (although it's not likely to be much of a change in the kernel code).
> 
> I need input on this.  Do people have opinions?
> 
> -dl
> 

Hi Dave,

Conditionally executing the kprobes would violate the assumptions made for perf and systemtap collecting data. Even if the instruction is predicated and treated as a NOP it should still reliably trigger the kprobe.  However, for efficiency the simulation/emulation/single-step of the instruction could be skipped if the instruction is known to have no change on the machine state other than changing the program counter.

-Will Cohen

[RFC] kprobe'ing conditionally executed instructions

[David Long]

On 12/11/2015 11:09 AM, William Cohen wrote:
> On 12/11/2015 12:05 AM, David Long wrote:
>> There is a moderate amount of code already in kprobes on ARM and the current ARMv8 patch to deal with conditional execution of instructions. One aspect of how this is handled is that instructions that fail their predicate and are not (technically) executed are also not treated as a hit kprobe. Steve Capper has suggested that the probe handling should still take place because we stepped through the instruction even if it was effectively a nop.  This would be a significant change in how it currently works on 32-bit ARM, and a change in the patch for ARMv8 (although it's not likely to be much of a change in the kernel code).
>>
>> I need input on this.  Do people have opinions?
>>
>> -dl
>>
>
> Hi Dave,
>
> Conditionally executing the kprobes would violate the assumptions made for perf and systemtap collecting data. Even if the instruction is predicated and treated as a NOP it should still reliably trigger the kprobe.  However, for efficiency the simulation/emulation/single-step of the instruction could be skipped if the instruction is known to have no change on the machine state other than changing the program counter.
>
> -Will Cohen
>

I wonder if this might explain some systemtap failures.

-dl

Re: [RFC] kprobe'ing conditionally executed instructions

[David Long]

On 12/11/2015 11:09 AM, William Cohen wrote:
> On 12/11/2015 12:05 AM, David Long wrote:
>> There is a moderate amount of code already in kprobes on ARM and the current ARMv8 patch to deal with conditional execution of instructions. One aspect of how this is handled is that instructions that fail their predicate and are not (technically) executed are also not treated as a hit kprobe. Steve Capper has suggested that the probe handling should still take place because we stepped through the instruction even if it was effectively a nop.  This would be a significant change in how it currently works on 32-bit ARM, and a change in the patch for ARMv8 (although it's not likely to be much of a change in the kernel code).
>>
>> I need input on this.  Do people have opinions?
>>
>> -dl
>>
>
> Hi Dave,
>
> Conditionally executing the kprobes would violate the assumptions made for perf and systemtap collecting data. Even if the instruction is predicated and treated as a NOP it should still reliably trigger the kprobe.  However, for efficiency the simulation/emulation/single-step of the instruction could be skipped if the instruction is known to have no change on the machine state other than changing the program counter.
>
> -Will Cohen
>

I wonder if this might explain some systemtap failures.

-dl

[RFC] kprobe'ing conditionally executed instructions

[William Cohen]

On 12/12/2015 12:56 AM, David Long wrote:
> On 12/11/2015 11:09 AM, William Cohen wrote:
>> On 12/11/2015 12:05 AM, David Long wrote:
>>> There is a moderate amount of code already in kprobes on ARM and the current ARMv8 patch to deal with conditional execution of instructions. One aspect of how this is handled is that instructions that fail their predicate and are not (technically) executed are also not treated as a hit kprobe. Steve Capper has suggested that the probe handling should still take place because we stepped through the instruction even if it was effectively a nop.  This would be a significant change in how it currently works on 32-bit ARM, and a change in the patch for ARMv8 (although it's not likely to be much of a change in the kernel code).
>>>
>>> I need input on this.  Do people have opinions?
>>>
>>> -dl
>>>
>>
>> Hi Dave,
>>
>> Conditionally executing the kprobes would violate the assumptions made for perf and systemtap collecting data. Even if the instruction is predicated and treated as a NOP it should still reliably trigger the kprobe.  However, for efficiency the simulation/emulation/single-step of the instruction could be skipped if the instruction is known to have no change on the machine state other than changing the program counter.
>>
>> -Will Cohen
>>
> 
> I wonder if this might explain some systemtap failures.
> 
> -dl
> 

Hi Dave,

It is possible that some of the kprobes not triggering would cause testsuite failures, but I don't have a specific test to point to this is happening.

How much of change would it be to fix the kprobes to get the correct behavior.  It might be easiest to fix it and compare the test results to find possible candidates where this problem occurs.

-Will

Re: [RFC] kprobe'ing conditionally executed instructions

[William Cohen]

On 12/12/2015 12:56 AM, David Long wrote:
> On 12/11/2015 11:09 AM, William Cohen wrote:
>> On 12/11/2015 12:05 AM, David Long wrote:
>>> There is a moderate amount of code already in kprobes on ARM and the current ARMv8 patch to deal with conditional execution of instructions. One aspect of how this is handled is that instructions that fail their predicate and are not (technically) executed are also not treated as a hit kprobe. Steve Capper has suggested that the probe handling should still take place because we stepped through the instruction even if it was effectively a nop.  This would be a significant change in how it currently works on 32-bit ARM, and a change in the patch for ARMv8 (although it's not likely to be much of a change in the kernel code).
>>>
>>> I need input on this.  Do people have opinions?
>>>
>>> -dl
>>>
>>
>> Hi Dave,
>>
>> Conditionally executing the kprobes would violate the assumptions made for perf and systemtap collecting data. Even if the instruction is predicated and treated as a NOP it should still reliably trigger the kprobe.  However, for efficiency the simulation/emulation/single-step of the instruction could be skipped if the instruction is known to have no change on the machine state other than changing the program counter.
>>
>> -Will Cohen
>>
> 
> I wonder if this might explain some systemtap failures.
> 
> -dl
> 

Hi Dave,

It is possible that some of the kprobes not triggering would cause testsuite failures, but I don't have a specific test to point to this is happening.

How much of change would it be to fix the kprobes to get the correct behavior.  It might be easiest to fix it and compare the test results to find possible candidates where this problem occurs.

-Will

[RFC] kprobe'ing conditionally executed instructions

[David Long]

On 12/12/2015 01:48 PM, William Cohen wrote:
> On 12/12/2015 12:56 AM, David Long wrote:
>> On 12/11/2015 11:09 AM, William Cohen wrote:
>>> On 12/11/2015 12:05 AM, David Long wrote:
>>>> There is a moderate amount of code already in kprobes on ARM and the current ARMv8 patch to deal with conditional execution of instructions. One aspect of how this is handled is that instructions that fail their predicate and are not (technically) executed are also not treated as a hit kprobe. Steve Capper has suggested that the probe handling should still take place because we stepped through the instruction even if it was effectively a nop.  This would be a significant change in how it currently works on 32-bit ARM, and a change in the patch for ARMv8 (although it's not likely to be much of a change in the kernel code).
>>>>
>>>> I need input on this.  Do people have opinions?
>>>>
>>>> -dl
>>>>
>>>
>>> Hi Dave,
>>>
>>> Conditionally executing the kprobes would violate the assumptions made for perf and systemtap collecting data. Even if the instruction is predicated and treated as a NOP it should still reliably trigger the kprobe.  However, for efficiency the simulation/emulation/single-step of the instruction could be skipped if the instruction is known to have no change on the machine state other than changing the program counter.
>>>
>>> -Will Cohen
>>>
>>
>> I wonder if this might explain some systemtap failures.
>>
>> -dl
>>
>
> Hi Dave,
>
> It is possible that some of the kprobes not triggering would cause testsuite failures, but I don't have a specific test to point to this is happening.
>
> How much of change would it be to fix the kprobes to get the correct behavior.  It might be easiest to fix it and compare the test results to find possible candidates where this problem occurs.
>
> -Will
>

I think it's a very simple change.  I will come up with something for 
you to test shortly. It sounds like we may need the change permanently 
anyway, although clearly there is not a solid consensus yet.

I would think this would impact 32-bit behavior much more than 64-bit. 
I can see about producing something for testing that too.

-dl

Re: [RFC] kprobe'ing conditionally executed instructions

[David Long]

On 12/12/2015 01:48 PM, William Cohen wrote:
> On 12/12/2015 12:56 AM, David Long wrote:
>> On 12/11/2015 11:09 AM, William Cohen wrote:
>>> On 12/11/2015 12:05 AM, David Long wrote:
>>>> There is a moderate amount of code already in kprobes on ARM and the current ARMv8 patch to deal with conditional execution of instructions. One aspect of how this is handled is that instructions that fail their predicate and are not (technically) executed are also not treated as a hit kprobe. Steve Capper has suggested that the probe handling should still take place because we stepped through the instruction even if it was effectively a nop.  This would be a significant change in how it currently works on 32-bit ARM, and a change in the patch for ARMv8 (although it's not likely to be much of a change in the kernel code).
>>>>
>>>> I need input on this.  Do people have opinions?
>>>>
>>>> -dl
>>>>
>>>
>>> Hi Dave,
>>>
>>> Conditionally executing the kprobes would violate the assumptions made for perf and systemtap collecting data. Even if the instruction is predicated and treated as a NOP it should still reliably trigger the kprobe.  However, for efficiency the simulation/emulation/single-step of the instruction could be skipped if the instruction is known to have no change on the machine state other than changing the program counter.
>>>
>>> -Will Cohen
>>>
>>
>> I wonder if this might explain some systemtap failures.
>>
>> -dl
>>
>
> Hi Dave,
>
> It is possible that some of the kprobes not triggering would cause testsuite failures, but I don't have a specific test to point to this is happening.
>
> How much of change would it be to fix the kprobes to get the correct behavior.  It might be easiest to fix it and compare the test results to find possible candidates where this problem occurs.
>
> -Will
>

I think it's a very simple change.  I will come up with something for 
you to test shortly. It sounds like we may need the change permanently 
anyway, although clearly there is not a solid consensus yet.

I would think this would impact 32-bit behavior much more than 64-bit. 
I can see about producing something for testing that too.

-dl