Re: MmioTrace: Using the Instruction Decoder, etc.

Re: MmioTrace: Using the Instruction Decoder, etc.

[Pekka Paalanen]

On Mon, 14 Oct 2013 22:45:09 +0400
Eugene Shatokhin <euspectre@gmail.com> wrote:

> Hi,
> 
> There is an interesting TODO item on MmioTraceDeveloper page:
> "kprobes has a generic instruction decoding facility, use that instead of
> homebrewn (or KVM), and use emulation instead of page faulting"
> 
> Actually, I have done something similar in one of my systems, KernelStrider
> (http://code.google.com/p/kernel-strider/). The system instruments a kernel
> module when that module is being loaded. The instrumented code executes
> instead of the original one and provides information about the memory
> accesses it makes and the functions it calls. These data are sent to user
> space for further analysis.
> 
> Currently, I use this system to detect data races in the Linux kernel (and
> have found some). I suppose, it could probably be useful to MmioTrace as
> well.
> 
> KernelStrider uses an enhanced version of the x86 instruction decoder that
> Kprobes use and relies on binary instrumentation rather than on page
> faults. So, it can track:
> - memory accesses (address and size of the accessed memory as well as the
> access type are recorded)
> - function calls (exported functions and callbacks, one can setup pre- and
> post- handlers for these)
> 
> Is there any interest in trying this approach to the task of MmioTrace?
> 
> If so, we can discuss it. When I have time, I could try to create a
> prototype based on KernelStrider's core that tracks the memory accesses
> Mmiotrace needs.
> What do you think?

Hi Eugene,

that is very interesting! I assume emulating the instructions is
not only cleaner, but also faster than page-faulting, right? Maybe
even more reliable, perhaps up to the point where we would not need
to disable all but one CPU.

Unfortunately, my job exhausts my coding energy, and I haven't even
touched mmiotrace in years.

However, let's see if there are interested people on the mailing
lists. I'm CC'ing nouveau, since that is where mmiotrace started,
and dri-devel in the hopes to catch other drivers' reverse
engineers.


Thanks,
pq

Re: MmioTrace: Using the Instruction Decoder, etc.

[Eugene Shatokhin]

[-- Attachment #1.1: Type: text/plain, Size: 4145 bytes --]

Hi,

Good to know that!

Yes, it should be faster than page faulting, although I haven't done the
benchmarking yet. And yes, it is not needed to disable all but one CPU. In
my current implementation, I use an ordered workqueue to send the data to
the mmapped output buffer (where they will be read from from the user
space) and that ensures the order of events is kept. May be less than ideal
but it currently works quite well with network drivers, the performance
overhead is acceptable there.

A subtle drawback may be that the system sees the memory reads and writes
made by the code of the driver directly but if the driver uses some other
kernel functions, it needs to intercept these calls and determine how they
access the memory of interest. Theoretically, it could be less accurate
than page fault handling. A page fault happens no matter if the driver
accesses the memory directly or via strcpy(), for example. I doubt this
would be a big problem for tracking the accesses to ioremapped memory
though.

Nevertheless, it is manageable, the system already handles string
functions, for example, and reports appropriate events. The handlers for
other functions could be added as well. So this just requires a bit more
maintenance work.

> Unfortunately, my job exhausts my coding energy, and I haven't even
touched mmiotrace in years.

I understand. I have many other responsibilities too. Code to write, bugs
to fix, etc. ;-)

Well, then, when time permits, I'll try to prepare a prototype so that its
performance and reliability could be evaluated. Hard to tell what the
numbers will be before that.

Suggestions, comments and other feedback are welcome of course.

And, by the way, video drivers do not use SSE and similar instructions when
accessing ioremapped memory, do they?
Such things are rare in the kernel and usually frowned upon so I opted not
to handle them so far in KernelStrider.

Regards,
Eugene




2013/10/17 Pekka Paalanen <pq@iki.fi>

> On Mon, 14 Oct 2013 22:45:09 +0400
> Eugene Shatokhin <euspectre@gmail.com> wrote:
>
> > Hi,
> >
> > There is an interesting TODO item on MmioTraceDeveloper page:
> > "kprobes has a generic instruction decoding facility, use that instead of
> > homebrewn (or KVM), and use emulation instead of page faulting"
> >
> > Actually, I have done something similar in one of my systems,
> KernelStrider
> > (http://code.google.com/p/kernel-strider/). The system instruments a
> kernel
> > module when that module is being loaded. The instrumented code executes
> > instead of the original one and provides information about the memory
> > accesses it makes and the functions it calls. These data are sent to user
> > space for further analysis.
> >
> > Currently, I use this system to detect data races in the Linux kernel
> (and
> > have found some). I suppose, it could probably be useful to MmioTrace as
> > well.
> >
> > KernelStrider uses an enhanced version of the x86 instruction decoder
> that
> > Kprobes use and relies on binary instrumentation rather than on page
> > faults. So, it can track:
> > - memory accesses (address and size of the accessed memory as well as the
> > access type are recorded)
> > - function calls (exported functions and callbacks, one can setup pre-
> and
> > post- handlers for these)
> >
> > Is there any interest in trying this approach to the task of MmioTrace?
> >
> > If so, we can discuss it. When I have time, I could try to create a
> > prototype based on KernelStrider's core that tracks the memory accesses
> > Mmiotrace needs.
> > What do you think?
>
> Hi Eugene,
>
> that is very interesting! I assume emulating the instructions is
> not only cleaner, but also faster than page-faulting, right? Maybe
> even more reliable, perhaps up to the point where we would not need
> to disable all but one CPU.
>
> Unfortunately, my job exhausts my coding energy, and I haven't even
> touched mmiotrace in years.
>
> However, let's see if there are interested people on the mailing
> lists. I'm CC'ing nouveau, since that is where mmiotrace started,
> and dri-devel in the hopes to catch other drivers' reverse
> engineers.
>
>
> Thanks,
> pq
>

[-- Attachment #1.2: Type: text/html, Size: 5213 bytes --]

[-- Attachment #2: Type: text/plain, Size: 159 bytes --]

_______________________________________________
dri-devel mailing list
dri-devel@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/dri-devel

Re: MmioTrace: Using the Instruction Decoder, etc.

[Pekka Paalanen]

On Fri, 18 Oct 2013 00:11:15 +0400
Eugene Shatokhin <euspectre@gmail.com> wrote:

> Hi,
> 
> Good to know that!
> 
> Yes, it should be faster than page faulting, although I haven't done the
> benchmarking yet. And yes, it is not needed to disable all but one CPU. In
> my current implementation, I use an ordered workqueue to send the data to
> the mmapped output buffer (where they will be read from from the user
> space) and that ensures the order of events is kept. May be less than ideal
> but it currently works quite well with network drivers, the performance
> overhead is acceptable there.

Ah, you are not using the ftrace framework nor relayfs? Mmiotrace
used to be relayfs at one point and then converted to ftrace.

> A subtle drawback may be that the system sees the memory reads and writes
> made by the code of the driver directly but if the driver uses some other
> kernel functions, it needs to intercept these calls and determine how they
> access the memory of interest. Theoretically, it could be less accurate
> than page fault handling. A page fault happens no matter if the driver
> accesses the memory directly or via strcpy(), for example. I doubt this
> would be a big problem for tracking the accesses to ioremapped memory
> though.
> 
> Nevertheless, it is manageable, the system already handles string
> functions, for example, and reports appropriate events. The handlers for
> other functions could be added as well. So this just requires a bit more
> maintenance work.

Are you saying that you intercept function calls, and *never* rely
on page faulting?

Does that mean that if a driver does the ugly thing and
dereferences an iomem pointer directly, you won't catch that?
Unfortunately, I think proprietary drivers do such uglies, since
they are x86 and x86_64 only where it works. Or they might have the
iomem accessor functions inlined.

What I had in mind was to still use page faulting to catch the
memory accessing machine instructions, but then use emulation to
execute that instruction with the memory address diverted to the
real ioremapped region instead of the dummy region given to the driver.
Currently for each access, on the page fault, mmiotrace uses single
stepping and page table manipulation to let the instruction run for
real, and immediately afterwards set things back to page faulting.

Sorry, I see my terminology was wrong. I don't think we can avoid
the page faulting, but I'd like to avoid the single-stepping and
page table mangling on the fly. Heh, things are slowly coming back
to me.

What do you thing, would it still be interesting?

> > Unfortunately, my job exhausts my coding energy, and I haven't even
> touched mmiotrace in years.
> 
> I understand. I have many other responsibilities too. Code to write, bugs
> to fix, etc. ;-)
> 
> Well, then, when time permits, I'll try to prepare a prototype so that its
> performance and reliability could be evaluated. Hard to tell what the
> numbers will be before that.
> 
> Suggestions, comments and other feedback are welcome of course.
> 
> And, by the way, video drivers do not use SSE and similar instructions when
> accessing ioremapped memory, do they?
> Such things are rare in the kernel and usually frowned upon so I opted not
> to handle them so far in KernelStrider.

I don't really know. I guess everything could be possible in
proprietary drivers, but you can look at the instruction decoding
code in mmiotrace, which digs up the type and size of access and
the value. That has been enough so far.


Thanks,
pq

> 2013/10/17 Pekka Paalanen <pq@iki.fi>
> 
> > On Mon, 14 Oct 2013 22:45:09 +0400
> > Eugene Shatokhin <euspectre@gmail.com> wrote:
> >
> > > Hi,
> > >
> > > There is an interesting TODO item on MmioTraceDeveloper page:
> > > "kprobes has a generic instruction decoding facility, use that instead of
> > > homebrewn (or KVM), and use emulation instead of page faulting"
> > >
> > > Actually, I have done something similar in one of my systems,
> > KernelStrider
> > > (http://code.google.com/p/kernel-strider/). The system instruments a
> > kernel
> > > module when that module is being loaded. The instrumented code executes
> > > instead of the original one and provides information about the memory
> > > accesses it makes and the functions it calls. These data are sent to user
> > > space for further analysis.
> > >
> > > Currently, I use this system to detect data races in the Linux kernel
> > (and
> > > have found some). I suppose, it could probably be useful to MmioTrace as
> > > well.
> > >
> > > KernelStrider uses an enhanced version of the x86 instruction decoder
> > that
> > > Kprobes use and relies on binary instrumentation rather than on page
> > > faults. So, it can track:
> > > - memory accesses (address and size of the accessed memory as well as the
> > > access type are recorded)
> > > - function calls (exported functions and callbacks, one can setup pre-
> > and
> > > post- handlers for these)
> > >
> > > Is there any interest in trying this approach to the task of MmioTrace?
> > >
> > > If so, we can discuss it. When I have time, I could try to create a
> > > prototype based on KernelStrider's core that tracks the memory accesses
> > > Mmiotrace needs.
> > > What do you think?
> >
> > Hi Eugene,
> >
> > that is very interesting! I assume emulating the instructions is
> > not only cleaner, but also faster than page-faulting, right? Maybe
> > even more reliable, perhaps up to the point where we would not need
> > to disable all but one CPU.
> >
> > Unfortunately, my job exhausts my coding energy, and I haven't even
> > touched mmiotrace in years.
> >
> > However, let's see if there are interested people on the mailing
> > lists. I'm CC'ing nouveau, since that is where mmiotrace started,
> > and dri-devel in the hopes to catch other drivers' reverse
> > engineers.
> >

Re: MmioTrace: Using the Instruction Decoder, etc.

[Eugene Shatokhin]

[-- Attachment #1.1: Type: text/plain, Size: 3381 bytes --]

Hi,

>  Ah, you are not using the ftrace framework nor relayfs? Mmiotrace
 used to be relayfs at one point and then converted to ftrace.

Yes, I considered these when I started working on KernelStrider but finally
borrowed ideas from Perf and implemented them. A mmapped ring buffer does
its job well and has a higher throughput than Ftrace in my case.

> Are you saying that you intercept function calls, and *never* rely
> on page faulting?

The system intercepts both function calls *and* memory operations made by
the driver itself. Yes, it never relies on page faulting.

 > Does that mean that if a driver does the ugly thing and
 > dereferences an iomem pointer directly, you won't catch that?

It will be caught.

What my system actually does is as follows.

When the target kernel module has been loaded into memory but before it has
begun its initialization, KernelStrider processes it, function after
function. It creates an instrumented variant of each function in the module
mapping space and places a jump at the beginning of the original function
to point to the instrumented one. After instrumentation is done, the target
driver may start executing.

If some original function of the driver contained, say,

  mov 0xabcd (%rax), %rsi
  mov %rbx, 0xbeeffeed (%rsi)

that will be transformed to something like

  lea  0xabcd (%rax), %rbx
  mov %rbx, <local_storage1>
  mov 0xabcd (%rax), %rsi
  lea  0xbeeffeed (%rsi), %rbx
  mov %rbx, <local_storage2>
  mov %rbx, 0xbeeffeed (%rsi)
  ...
  <send the local_storage to the output system>

That is, the address which is about to be accessed is determined and stored
in 'local_storage', a special memory structure. At the end of the block of
instructions, the information from the local storage is sent to the output
system. So the addresses and sizes of the accessed memory areas as well as
the types of the accesses (read/write/update) will be available for reading
from the user space.

It is actually more complex than that (KernelStrider has to deal with
register allocation, relocations and other things) but the principle is as
I described.

The function calls are processed too so that we can set our own handlers to
execute at the beginning of a function and right before its exit.

Yes, the functions like read[bwql]() and write[bwlq]() are usually inline
but they pose no problem: on x86 they compile to ordinary MOV instructions
and the like which are handled as I described above.

The instrumented code will access the ioremapped area the same way as the
original code would, no need for single-stepping or emulation in this case.

What I wrote in my previous letter is that there is a special case when the
target driver uses some non-inline function provided by the kernel proper
or by another driver and that function accesses the ioremapped memory area
of interest.

KernelStrider needs to track all such functions in order not to miss some
memory accesses to that ioremapped area. Perhaps, that's manageable. There
are not too many such functions, aren't they?

> I don't really know. I guess everything could be possible in
> proprietary drivers, but you can look at the instruction decoding
> code in mmiotrace, which digs up the type and size of access and
> the value. That has been enough so far.

Yes, I will take a closer look on that part of MmioTrace, thanks for the
point.

Regards,

Eugene

[-- Attachment #1.2: Type: text/html, Size: 5160 bytes --]

[-- Attachment #2: Type: text/plain, Size: 181 bytes --]

_______________________________________________
Nouveau mailing list
Nouveau-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
http://lists.freedesktop.org/mailman/listinfo/nouveau

Re: MmioTrace: Using the Instruction Decoder, etc.

[Eugene Shatokhin]

[-- Attachment #1.1: Type: text/plain, Size: 445 bytes --]

Oh, messed up the registers in the example. Should be like this:

If some original function of the driver contained, say,

mov 0xabcd (%rax), %rsi
mov %rdx, 0xbeeffeed (%rsi)

that will be transformed to something like

lea 0xabcd (%rax), %rbx
mov %rbx, <local_storage1>
mov 0xabcd (%rax), %rsi
lea 0xbeeffeed (%rsi), %rbx
mov %rbx, <local_storage2>
mov %rdx, 0xbeeffeed (%rsi)
...
<send the local_storage to the output system>

Regards,
Eugene

[-- Attachment #1.2: Type: text/html, Size: 626 bytes --]

[-- Attachment #2: Type: text/plain, Size: 181 bytes --]

_______________________________________________
Nouveau mailing list
Nouveau-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
http://lists.freedesktop.org/mailman/listinfo/nouveau

Re: MmioTrace: Using the Instruction Decoder, etc.

[Pekka Paalanen]

On Sat, 19 Oct 2013 17:12:20 +0400
Eugene Shatokhin <euspectre@gmail.com> wrote:

> Hi,
> 
> >  Ah, you are not using the ftrace framework nor relayfs? Mmiotrace
>  used to be relayfs at one point and then converted to ftrace.
> 
> Yes, I considered these when I started working on KernelStrider but finally
> borrowed ideas from Perf and implemented them. A mmapped ring buffer does
> its job well and has a higher throughput than Ftrace in my case.
> 
> > Are you saying that you intercept function calls, and *never* rely
> > on page faulting?
> 
> The system intercepts both function calls *and* memory operations made by
> the driver itself. Yes, it never relies on page faulting.
> 
>  > Does that mean that if a driver does the ugly thing and
>  > dereferences an iomem pointer directly, you won't catch that?
> 
> It will be caught.
> 
> What my system actually does is as follows.
> 
> When the target kernel module has been loaded into memory but before it has
> begun its initialization, KernelStrider processes it, function after
> function. It creates an instrumented variant of each function in the module
> mapping space and places a jump at the beginning of the original function
> to point to the instrumented one. After instrumentation is done, the target
> driver may start executing.

Oh, that works on a completely different way than I even imagined,
a whole another level of complexity.


<...snip code you corrected in another email>

> That is, the address which is about to be accessed is determined and stored
> in 'local_storage', a special memory structure. At the end of the block of
> instructions, the information from the local storage is sent to the output
> system. So the addresses and sizes of the accessed memory areas as well as
> the types of the accesses (read/write/update) will be available for reading
> from the user space.

Just curious, how do you detect interesting instructions to
instrument from uninteresting instructions that do not access mmio
areas?

Does it rely on post-processing, in that you instrument practically
everything, and then in post-processing you check if the accessed
memory address actually was interesting before sending the data to user
space?

> It is actually more complex than that (KernelStrider has to deal with
> register allocation, relocations and other things) but the principle is as
> I described.
> 
> The function calls are processed too so that we can set our own handlers to
> execute at the beginning of a function and right before its exit.
> 
> Yes, the functions like read[bwql]() and write[bwlq]() are usually inline
> but they pose no problem: on x86 they compile to ordinary MOV instructions
> and the like which are handled as I described above.
> 
> The instrumented code will access the ioremapped area the same way as the
> original code would, no need for single-stepping or emulation in this case.

That is very cool, the possibility never even occurred to me.

> What I wrote in my previous letter is that there is a special case when the
> target driver uses some non-inline function provided by the kernel proper
> or by another driver and that function accesses the ioremapped memory area
> of interest.
> 
> KernelStrider needs to track all such functions in order not to miss some
> memory accesses to that ioremapped area. Perhaps, that's manageable. There
> are not too many such functions, aren't they?

I don't really know, and personally I was never even interested,
since the page faulting approach was a catch-all method. We
could even detect when we hit some access we couldn't handle right
due to lacking instruction decoding.

I guess to be sure your approach does not miss anything, we'd still
need the page faulting setup as a safety net to know when or if
something is missed, right? And somehow have the instrumented code
circumvent it.

We could use some comments from the real reverse-engineers. I used
to be mostly a tool writer.


Thanks,
pq

Re: MmioTrace: Using the Instruction Decoder, etc.

[Eugene Shatokhin]

[-- Attachment #1.1: Type: text/plain, Size: 2568 bytes --]

Hi,

2013/10/25 Pekka Paalanen <pq-X3B1VOXEql0@public.gmane.org>

>
> Just curious, how do you detect interesting instructions to
> instrument from uninteresting instructions that do not access mmio
> areas?
>
>
As I currently use this for data race detection in general, there is no
need to separate accesses to mmio areas from the accesses to other memory.
The tool just tracks all except the accesses to the data on the stack (if
it can know for sure the data are on the stack from the address of the
memory area). These are usually not interested for data race detection in
the kernel anyway.

So, yes, almost all the instructions that may access memory (except some
special instructions as well as MMX, SSE, AVX, ...) are instrumented. For
some instructions, it is easy to determine in advance if they access
memory, so I enhanced the decoder from Kprobes to provide that info. For
other instructions (e.g. CMPXCHG, conditional MOVs), it is determined in
runtime whether they access memory and whether this event should be
reported.

So, currently, it does not handle mmio areas in any special way. I am just
evaluating, if it could be useful to create a tool based on the same
technique for these purposes.

mmio areas can be obtained by a driver through a few kernel functions. A
set of currently obtained such areas could be used to filter the accesses
and decide whether to report them or not. So, yes, basically, it is
"instrument everything, filter before reporting to user space".

I guess to be sure your approach does not miss anything, we'd still
> need the page faulting setup as a safety net to know when or if
> something is missed, right? And somehow have the instrumented code
> circumvent it.
>

Page faulting as a safety net... I haven't thought that through yet.

I suppose, I'll look at the code first when I have time and try to
understand at least the common ways for a driver to access mmio areas. It
will be clearer then how to make sure we do not lose anything. And - if it
is possible with the techniques KernelStrider uses.



>
> We could use some comments from the real reverse-engineers. I used
> to be mostly a tool writer.
>

Yes, if some experts could share their knowledge of this matter, this would
be most welcome!

Regards,

Eugene

P.S. If you are interested, more info concerning KernelStrider can be found
in my recent talk at LinuxCon Europe. The slides and notes for them are
available in "Talks and slides" section on the project page (
https://code.google.com/p/kernel-strider/). This is mostly about data races
though.

[-- Attachment #1.2: Type: text/html, Size: 3760 bytes --]

[-- Attachment #2: Type: text/plain, Size: 181 bytes --]

_______________________________________________
Nouveau mailing list
Nouveau-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
http://lists.freedesktop.org/mailman/listinfo/nouveau

Re: MmioTrace: Using the Instruction Decoder, etc.

[Pekka Paalanen]

On Fri, 25 Oct 2013 17:19:56 +0400
Eugene Shatokhin <euspectre@gmail.com> wrote:

> Hi,
> 
> 2013/10/25 Pekka Paalanen <pq@iki.fi>
> 
...
> > We could use some comments from the real reverse-engineers. I used
> > to be mostly a tool writer.
> >
> 
> Yes, if some experts could share their knowledge of this matter, this would
> be most welcome!

Hi,

I got one comment in IRC, saying that a faster mmiotrace would be
nice, but probably not something he would invest time in.

Looking at it from that point of view, I guess mmiotrace works well enough,
and is "only" a reverse-engineering tool, not something used daily.
That, and the lack of replies here indicate that rewriting mmiotrace
with your approach might not be worth it. I don't think anyone
opposes to the idea, they just have better things to do.

It's all up to you, I believe.


Thanks,
pq

Re: MmioTrace: Using the Instruction Decoder, etc.

[Eugene Shatokhin]

[-- Attachment #1.1: Type: text/plain, Size: 1230 bytes --]

Hi,

That's OK.

The first rule of a good software developer is, they say, 'if that works -
don't touch it'. :-)

There are definitely many other things to do.

Thanks for your feedback!

Regards,
Eugene



2013/10/28 Pekka Paalanen <pq-X3B1VOXEql0@public.gmane.org>

> On Fri, 25 Oct 2013 17:19:56 +0400
> Eugene Shatokhin <euspectre-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:
>
> > Hi,
> >
> > 2013/10/25 Pekka Paalanen <pq-X3B1VOXEql0@public.gmane.org>
> >
> ...
> > > We could use some comments from the real reverse-engineers. I used
> > > to be mostly a tool writer.
> > >
> >
> > Yes, if some experts could share their knowledge of this matter, this
> would
> > be most welcome!
>
> Hi,
>
> I got one comment in IRC, saying that a faster mmiotrace would be
> nice, but probably not something he would invest time in.
>
> Looking at it from that point of view, I guess mmiotrace works well enough,
> and is "only" a reverse-engineering tool, not something used daily.
> That, and the lack of replies here indicate that rewriting mmiotrace
> with your approach might not be worth it. I don't think anyone
> opposes to the idea, they just have better things to do.
>
> It's all up to you, I believe.
>
>
> Thanks,
> pq
>

[-- Attachment #1.2: Type: text/html, Size: 2019 bytes --]

[-- Attachment #2: Type: text/plain, Size: 181 bytes --]

_______________________________________________
Nouveau mailing list
Nouveau-PD4FTy7X32lNgt0PjOBp9y5qC8QIuHrW@public.gmane.org
http://lists.freedesktop.org/mailman/listinfo/nouveau