Re: [Qemu-devel] Reverse execution and deterministic replay

Re: [Qemu-devel] Reverse execution and deterministic replay

[Peter Crosthwaite]

Hi Pavel,

On Fri, Jun 27, 2014 at 3:18 PM, Pavel Dovgaluk
<Pavel.Dovgaluk@ispras.ru> wrote:
> Hello!
>
> We want to publish set of patches related to the reverse execution and deterministic replay of qemu.
> Our implementation of deterministic replay can be used for deterministic and reverse debugging of
> guest code through gdb remote interface.
>
> Execution recording writes non-deterministic events log, which can be later used for replaying the
> execution anywhere and for unlimited number of times. It also supports checkpointing for faster
> rewinding during reverse debugging. Execution replaying reads the log and replays all
> non-deterministic events including external input, hardware clocks, and interrupts.
>
> Reverse execution has the following features:
>  * Deterministically replays whole system execution and all contents of the memory,
>    state of the hadrware devices, clocks, and screen of the VM.
>  * Writes execution log into the file for latter replaying for multiple times
>    on different machines.
>  * Supports i386, x86_64, and ARM hardware platforms.
>  * Performs deterministic replay of all operations with keyboard, mouse, network adapters,
>    audio devices, serial interfaces, and physical USB devices connected to the emulator.
>  * Provides support for gdb reverse debugging commands like reverse-step and reverse-continue.
>  * Supports auto-checkpointing for convenient reverse debugging.
>  * Allows "going to the live execution" from the replay mode.
>
> Our implementation is completely tested for qemu 1.5 and is in beta state for 2.0.50.
>
> Some details about our implementation of reverse execution can be found in paper:
> http://www.computer.org/csdl/proceedings/csmr/2012/4666/00/4666a553-abs.html
>

Add relevant implementation details to the git commit messages.

> Can anyone review our patches?
>

Fred Konrad is doing a series on reverse exe at the moment. CC. Is the
an independent implementation of the same thing or are you building on
it?

I suggest posting a full RFC, this looks to me just like a cover
letter but without a series.

Note that we are going into hard freeze imminently so there will be
some delay for merge.

Regards,
Peter

> Pavel Dovgaluk
>
>
>

Re: [Qemu-devel] Reverse execution and deterministic replay

[Pavel Dovgaluk]

> -----Original Message-----
> From: peter.crosthwaite@petalogix.com [mailto:peter.crosthwaite@petalogix.com] On Behalf Of
> Peter Crosthwaite
> Sent: Friday, June 27, 2014 10:11 AM
> To: Pavel Dovgaluk; Fréderic Konrad
> Cc: qemu-devel@nongnu.org Developers; Paolo Bonzini
> Subject: Re: [Qemu-devel] Reverse execution and deterministic replay
> 
> Hi Pavel,
> 
> On Fri, Jun 27, 2014 at 3:18 PM, Pavel Dovgaluk
> <Pavel.Dovgaluk@ispras.ru> wrote:
> > Hello!
> >
> > We want to publish set of patches related to the reverse execution and deterministic replay
> of qemu.
> > Our implementation of deterministic replay can be used for deterministic and reverse
> debugging of
> > guest code through gdb remote interface.
> >
> > Execution recording writes non-deterministic events log, which can be later used for
> replaying the
> > execution anywhere and for unlimited number of times. It also supports checkpointing for
> faster
> > rewinding during reverse debugging. Execution replaying reads the log and replays all
> > non-deterministic events including external input, hardware clocks, and interrupts.
> >
> > Reverse execution has the following features:
> >  * Deterministically replays whole system execution and all contents of the memory,
> >    state of the hadrware devices, clocks, and screen of the VM.
> >  * Writes execution log into the file for latter replaying for multiple times
> >    on different machines.
> >  * Supports i386, x86_64, and ARM hardware platforms.
> >  * Performs deterministic replay of all operations with keyboard, mouse, network adapters,
> >    audio devices, serial interfaces, and physical USB devices connected to the emulator.
> >  * Provides support for gdb reverse debugging commands like reverse-step and reverse-
> continue.
> >  * Supports auto-checkpointing for convenient reverse debugging.
> >  * Allows "going to the live execution" from the replay mode.
> >
> > Our implementation is completely tested for qemu 1.5 and is in beta state for 2.0.50.
> >
> > Some details about our implementation of reverse execution can be found in paper:
> > http://www.computer.org/csdl/proceedings/csmr/2012/4666/00/4666a553-abs.html
> >
> 
> Add relevant implementation details to the git commit messages.

Do you mean describing the details in patches that I should submit?

> > Can anyone review our patches?
> >
> 
> Fred Konrad is doing a series on reverse exe at the moment. CC. Is the
> an independent implementation of the same thing or are you building on
> it?

Our implementation is not related to Fred Konrad.

> I suggest posting a full RFC, this looks to me just like a cover
> letter but without a series.

Of course I will post a full RFC with details of implementation.

> 
> Note that we are going into hard freeze imminently so there will be
> some delay for merge.

Pavel Dovgaluk

Re: [Qemu-devel] Reverse execution and deterministic replay

[Frederic Konrad]

On 27/06/2014 08:11, Peter Crosthwaite wrote:
> Hi Pavel,
>
> On Fri, Jun 27, 2014 at 3:18 PM, Pavel Dovgaluk
> <Pavel.Dovgaluk@ispras.ru> wrote:
>> Hello!
>>
>> We want to publish set of patches related to the reverse execution and deterministic replay of qemu.
>> Our implementation of deterministic replay can be used for deterministic and reverse debugging of
>> guest code through gdb remote interface.
>>
>> Execution recording writes non-deterministic events log, which can be later used for replaying the
>> execution anywhere and for unlimited number of times. It also supports checkpointing for faster
>> rewinding during reverse debugging. Execution replaying reads the log and replays all
>> non-deterministic events including external input, hardware clocks, and interrupts.
>>
>> Reverse execution has the following features:
>>   * Deterministically replays whole system execution and all contents of the memory,
>>     state of the hadrware devices, clocks, and screen of the VM.
>>   * Writes execution log into the file for latter replaying for multiple times
>>     on different machines.
>>   * Supports i386, x86_64, and ARM hardware platforms.
>>   * Performs deterministic replay of all operations with keyboard, mouse, network adapters,
>>     audio devices, serial interfaces, and physical USB devices connected to the emulator.
>>   * Provides support for gdb reverse debugging commands like reverse-step and reverse-continue.
>>   * Supports auto-checkpointing for convenient reverse debugging.
>>   * Allows "going to the live execution" from the replay mode.
>>
>> Our implementation is completely tested for qemu 1.5 and is in beta state for 2.0.50.
>>
>> Some details about our implementation of reverse execution can be found in paper:
>> http://www.computer.org/csdl/proceedings/csmr/2012/4666/00/4666a553-abs.html
>>
> Add relevant implementation details to the git commit messages.
>
>> Can anyone review our patches?
>>
> Fred Konrad is doing a series on reverse exe at the moment. CC. Is the
> an independent implementation of the same thing or are you building on
> it?

Hi,

Yes seems we are doing the same thing only we use icount as an instruction
counter and you created a new instruction counter?

This has advantage of having it working everywhere icount works but the
disavantages of having to use icount for reverse execution.

I think we can use both way so the reverse execution will works on other
architecture the time an instruction counter is added to them.

I'm sure your patches will add to our solution and I can review your patches
when you'll send them.

It would help if you rebase them on the patch set that is currently on 
the list:
"[RFC PATCH v5 00/13] Reverse execution." I sent two days ago.

Thanks,
Fred
>
> I suggest posting a full RFC, this looks to me just like a cover
> letter but without a series.
>
> Note that we are going into hard freeze imminently so there will be
> some delay for merge.
>
> Regards,
> Peter
>
>> Pavel Dovgaluk
>>
>>
>>

Re: [Qemu-devel] Reverse execution and deterministic replay

[Pavel Dovgaluk]

> -----Original Message-----
> From: Frederic Konrad [mailto:fred.konrad@greensocs.com]
> Sent: Friday, June 27, 2014 11:48 AM
> To: Pavel Dovgaluk
> Cc: Peter Crosthwaite; Paolo Bonzini; qemu-devel@nongnu.org Developers; Mark Burton
> Subject: Re: [Qemu-devel] Reverse execution and deterministic replay
> 
> On 27/06/2014 08:11, Peter Crosthwaite wrote:
> > Hi Pavel,
> >
> > On Fri, Jun 27, 2014 at 3:18 PM, Pavel Dovgaluk
> > <Pavel.Dovgaluk@ispras.ru> wrote:
> >> Hello!
> >>
> >> We want to publish set of patches related to the reverse execution and deterministic replay
> of qemu.
> >> Our implementation of deterministic replay can be used for deterministic and reverse
> debugging of
> >> guest code through gdb remote interface.
> >>
> >> Execution recording writes non-deterministic events log, which can be later used for
> replaying the
> >> execution anywhere and for unlimited number of times. It also supports checkpointing for
> faster
> >> rewinding during reverse debugging. Execution replaying reads the log and replays all
> >> non-deterministic events including external input, hardware clocks, and interrupts.
> >>
> >> Reverse execution has the following features:
> >>   * Deterministically replays whole system execution and all contents of the memory,
> >>     state of the hadrware devices, clocks, and screen of the VM.
> >>   * Writes execution log into the file for latter replaying for multiple times
> >>     on different machines.
> >>   * Supports i386, x86_64, and ARM hardware platforms.
> >>   * Performs deterministic replay of all operations with keyboard, mouse, network adapters,
> >>     audio devices, serial interfaces, and physical USB devices connected to the emulator.
> >>   * Provides support for gdb reverse debugging commands like reverse-step and reverse-
> continue.
> >>   * Supports auto-checkpointing for convenient reverse debugging.
> >>   * Allows "going to the live execution" from the replay mode.
> >>
> >> Our implementation is completely tested for qemu 1.5 and is in beta state for 2.0.50.
> >>
> >> Some details about our implementation of reverse execution can be found in paper:
> >> http://www.computer.org/csdl/proceedings/csmr/2012/4666/00/4666a553-abs.html
> >>
> > Add relevant implementation details to the git commit messages.
> >
> >> Can anyone review our patches?
> >>
> > Fred Konrad is doing a series on reverse exe at the moment. CC. Is the
> > an independent implementation of the same thing or are you building on
> > it?
> 
> Hi,
> 
> Yes seems we are doing the same thing only we use icount as an instruction
> counter and you created a new instruction counter?

Yes, we created new instruction-accurate counter.

> This has advantage of having it working everywhere icount works but the
> disavantages of having to use icount for reverse execution.

The major disadvantage of icount is that it's updated only on TB boundaries.
When one instruction in the middle of the block uses virtual clock, it could
have different values for different divisions of the code to TB. E.g. you can
stop the execution using the debugger in the middle of the block. 
It will lead to creation of the new block starting from the next instruction
(which previously was in the middle of the TB). Reading virtual clock by this
instruction can give you different values.

> I think we can use both way so the reverse execution will works on other
> architecture the time an instruction counter is added to them.
> 
> I'm sure your patches will add to our solution and I can review your patches
> when you'll send them.
> 
> It would help if you rebase them on the patch set that is currently on
> the list:
> "[RFC PATCH v5 00/13] Reverse execution." I sent two days ago.

We do not use icount at all. We record virtual time into the replay log instead.
But we implemented an icount-like feature, which computes the values of virtual
clock and TSC using our internal instruction counter.

> 
> Thanks,
> Fred
> >
> > I suggest posting a full RFC, this looks to me just like a cover
> > letter but without a series.
> >
> > Note that we are going into hard freeze imminently so there will be
> > some delay for merge.
> >
> > Regards,
> > Peter
> >
> >> Pavel Dovgaluk
> >>
> >>
> >>


Pavel Dovgaluk

Re: [Qemu-devel] Reverse execution and deterministic replay

[Peter Maydell]

On 27 June 2014 11:35, Pavel Dovgaluk <Pavel.Dovgaluk@ispras.ru> wrote:
> The major disadvantage of icount is that it's updated only on TB boundaries.
> When one instruction in the middle of the block uses virtual clock, it could
> have different values for different divisions of the code to TB.

This is only true if the instruction is incorrectly not
marked as being "I/O". The idea behind icount is that in
general we update it on TB boundaries (it's much faster
than doing it once per insn) but for those places which
do turn out to need an exact icount we then retranslate
the block to get the instruction-to-icount-adjustment
mapping.

It wouldn't surprise me if this turned out to have some
bugs in corner cases, but fixing these issues seems to
me like a much better design than ignoring icount completely
and reimplementing a second instruction counter.

thanks
-- PMM

Re: [Qemu-devel] Reverse execution and deterministic replay

[Pavel Dovgaluk]

> On 27 June 2014 11:35, Pavel Dovgaluk <Pavel.Dovgaluk@ispras.ru> wrote:
> > The major disadvantage of icount is that it's updated only on TB boundaries.
> > When one instruction in the middle of the block uses virtual clock, it could
> > have different values for different divisions of the code to TB.
> 
> This is only true if the instruction is incorrectly not
> marked as being "I/O". The idea behind icount is that in
> general we update it on TB boundaries (it's much faster
> than doing it once per insn) but for those places which
> do turn out to need an exact icount we then retranslate
> the block to get the instruction-to-icount-adjustment
> mapping.

I see. But if we want virtual clock in "real" mode then we still
should create new timer (based on icount code).

> It wouldn't surprise me if this turned out to have some
> bugs in corner cases, but fixing these issues seems to
> me like a much better design than ignoring icount completely
> and reimplementing a second instruction counter.

When we started an implementation, we didn't have enough resources
to fix all such bugs. That is why we selected such conservative
approach. But I believe that in future we will adopt the icount
for replay purposes.

Pavel Dovgaluk

Re: [Qemu-devel] Reverse execution and deterministic replay

[Pavel Dovgaluk]

> On 27 June 2014 11:35, Pavel Dovgaluk <Pavel.Dovgaluk@ispras.ru> wrote:
> > The major disadvantage of icount is that it's updated only on TB boundaries.
> > When one instruction in the middle of the block uses virtual clock, it could
> > have different values for different divisions of the code to TB.
> 
> This is only true if the instruction is incorrectly not
> marked as being "I/O". The idea behind icount is that in
> general we update it on TB boundaries (it's much faster
> than doing it once per insn) but for those places which
> do turn out to need an exact icount we then retranslate
> the block to get the instruction-to-icount-adjustment
> mapping.

I forgot about one more issue.
When qemu stops execution on the breakpoint, the icount
is decreased to the number of instructions in the block.
But in this case the last instruction is not executed and
should not affect the counter.

Pavel Dovgaluk

Re: [Qemu-devel] Reverse execution and deterministic replay

[Peter Maydell]

On 27 June 2014 12:31, Pavel Dovgaluk <Pavel.Dovgaluk@ispras.ru> wrote:
> I forgot about one more issue.
> When qemu stops execution on the breakpoint, the icount
> is decreased to the number of instructions in the block.
> But in this case the last instruction is not executed and
> should not affect the counter.

Yes, indeed, that's the sort of edge case bug we should fix.

-- PMM

Re: [Qemu-devel] Reverse execution and deterministic replay

[Frederic Konrad]

We also started with a separate counter, but using icount, which is 
intended to
provide just this functionality, is much more logical.

On 27/06/2014 13:17, Pavel Dovgaluk wrote:
>> On 27 June 2014 11:35, Pavel Dovgaluk <Pavel.Dovgaluk@ispras.ru> wrote:
>>> The major disadvantage of icount is that it's updated only on TB boundaries.
>>> When one instruction in the middle of the block uses virtual clock, it could
>>> have different values for different divisions of the code to TB.
>> This is only true if the instruction is incorrectly not
>> marked as being "I/O". The idea behind icount is that in
>> general we update it on TB boundaries (it's much faster
>> than doing it once per insn) but for those places which
>> do turn out to need an exact icount we then retranslate
>> the block to get the instruction-to-icount-adjustment
>> mapping.
> I see. But if we want virtual clock in "real" mode then we still
> should create new timer (based on icount code).

That's exactly what QEMU_ICOUNT_CLOCK does in our series:
It depends only on the instruction counter and we use it to exit at the 
right
moment (by computing icount extra from this new clock as well). We don't 
have
this with QEMU_VIRTUAL_CLOCK as some host time is added to it.

"Real" mode support is somewhat a strange notion when we talk about 
reversing,
we believe that insisting on using icount for reverse execution is perfectly
acceptable, as introducing any sort of non-determinism based on the host 
clock
will not be helpful.

>> It wouldn't surprise me if this turned out to have some
>> bugs in corner cases, but fixing these issues seems to
>> me like a much better design than ignoring icount completely
>> and reimplementing a second instruction counter.
> When we started an implementation, we didn't have enough resources
> to fix all such bugs. That is why we selected such conservative
> approach. But I believe that in future we will adopt the icount
> for replay purposes.
>
> Pavel Dovgaluk
>
As you say, there are some little bugs with icount which must be fixed 
anyway.

I'm sure you did other advances that we have not managed, and as I say, 
I would
be happy to review your patches as I am sure they will imporve reverse 
execution
support.

Fred

Re: [Qemu-devel] Reverse execution and deterministic replay

[Peter Maydell]

On 27 June 2014 06:18, Pavel Dovgaluk <Pavel.Dovgaluk@ispras.ru> wrote:
> Our implementation is completely tested for qemu 1.5 and is in beta state for 2.0.50.

Note that you should post patches against current QEMU master;
patches against old releases like 1.5 are not something we could
use.

thanks
-- PMM

[Qemu-devel] Reverse execution and deterministic replay

[Pavel Dovgaluk]

Hello!

We want to publish set of patches related to the reverse execution and deterministic replay of qemu.
Our implementation of deterministic replay can be used for deterministic and reverse debugging of
guest code through gdb remote interface.

Execution recording writes non-deterministic events log, which can be later used for replaying the
execution anywhere and for unlimited number of times. It also supports checkpointing for faster
rewinding during reverse debugging. Execution replaying reads the log and replays all 
non-deterministic events including external input, hardware clocks, and interrupts.

Reverse execution has the following features:
 * Deterministically replays whole system execution and all contents of the memory,
   state of the hadrware devices, clocks, and screen of the VM.
 * Writes execution log into the file for latter replaying for multiple times 
   on different machines.
 * Supports i386, x86_64, and ARM hardware platforms.
 * Performs deterministic replay of all operations with keyboard, mouse, network adapters,
   audio devices, serial interfaces, and physical USB devices connected to the emulator.
 * Provides support for gdb reverse debugging commands like reverse-step and reverse-continue.
 * Supports auto-checkpointing for convenient reverse debugging.
 * Allows "going to the live execution" from the replay mode.

Our implementation is completely tested for qemu 1.5 and is in beta state for 2.0.50.

Some details about our implementation of reverse execution can be found in paper:
http://www.computer.org/csdl/proceedings/csmr/2012/4666/00/4666a553-abs.html

Can anyone review our patches?

Pavel Dovgaluk