[discuss] semantics, "replay debugging" vs. "reverse debugging"

[discuss] semantics, "replay debugging" vs. "reverse debugging"

[Michael Snyder]

Just to make sure we're all on the same page,
I'm gonna state what I believe is true, and invite
discussion or contradiction.

Replay debugging --> ability to record an execution
sequence and "play it back" (repeat it) with some
degree of determinism.

Reverse debugging --> ability to make the inferior
process "back up" to a previous state, eg. reverse
step and reverse continue-to-breakpoint.

They're related but not identical.  One could theoretically
have one without the other, although in practice all
presently existing reverse-debug targets (that I know of)
are implemented by using record and replay.

One could have reverse without record/replay if,
for instance, one had a machine architecture where
all instructions were reversable, ie. the machine
itself could reverse-execute an instruction.

And an example of a record/replay implementation
without reverse debugging capability would be
Michael Chastain's (circa 1999) implementation
of Linux system-call based record and replay, which
could deterministically replay a recorded program
execution, but did not have reverse-step or
reverse-continue-to-breakpoint.

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[Frederic Riss]

Hello,

2008/10/20 Michael Snyder <msnyder@vmware.com>:
> Just to make sure we're all on the same page,
> I'm gonna state what I believe is true, and invite
> discussion or contradiction.
>
> Replay debugging --> ability to record an execution
> sequence and "play it back" (repeat it) with some
> degree of determinism.
>
> Reverse debugging --> ability to make the inferior
> process "back up" to a previous state, eg. reverse
> step and reverse continue-to-breakpoint.
>
> They're related but not identical.  One could theoretically
> have one without the other, although in practice all
> presently existing reverse-debug targets (that I know of)
> are implemented by using record and replay.

For what it's worth, I spent some evenings a few weeks ago starting a
remote reversible gdbserver implementation as a valgrind skin. I've
the 'record' part nearly done, but I've stopped working on it due to
personal priorities inversion. My idea was that I'd use the recorded
history to reverse the execution, but that I'd let the virtual
processor do the replay itself (ie. simply let the target run form the
state I would have restored).

Of course, I was aware that some syscalls aren't 'reversible' and I
was wondering how to report that to the user. My first idea was to
just say: "You're using reverse debugging, watch your steps!". I see
that 'replaying' the history can be useful in such cases, and I could
certainly implement that on top of my history record.

However, now I'm wondering: can't the current implementations 'rewrite
the past'? My scheme of record->reverse->rerun was expected to allow
the user to modify thing in the past execution and then watch the
consequences. If it's possible for them, where is the decision made
when to switch between replay and rerun?

Take the above with a grain of salt, as I haven't worked on that
project for quite some time, and I haven't yet implemented the
reverse/rerun part.

Fred.

> One could have reverse without record/replay if,
> for instance, one had a machine architecture where
> all instructions were reversable, ie. the machine
> itself could reverse-execute an instruction.
>
> And an example of a record/replay implementation
> without reverse debugging capability would be
> Michael Chastain's (circa 1999) implementation
> of Linux system-call based record and replay, which
> could deterministically replay a recorded program
> execution, but did not have reverse-step or
> reverse-continue-to-breakpoint.
>

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[teawater]

On Mon, Oct 20, 2008 at 09:09, Michael Snyder <msnyder@vmware.com> wrote:
> Just to make sure we're all on the same page,
> I'm gonna state what I believe is true, and invite
> discussion or contradiction.
>
> Replay debugging --> ability to record an execution
> sequence and "play it back" (repeat it) with some
> degree of determinism.
>
> Reverse debugging --> ability to make the inferior
> process "back up" to a previous state, eg. reverse
> step and reverse continue-to-breakpoint.
>
> They're related but not identical.  One could theoretically
> have one without the other, although in practice all
> presently existing reverse-debug targets (that I know of)
> are implemented by using record and replay.
>
> One could have reverse without record/replay if,
> for instance, one had a machine architecture where
> all instructions were reversable, ie. the machine
> itself could reverse-execute an instruction.

I think maybe some instruction can do it.
Such as add instruction. When it forward execute, it add some number
to a value of register. When it reverse, it can sub this number from
the value of register. It can reverse without record.

In P record, I make a interface to use it in record_t need_dasm. But I
still not use it. Maybe I can use it in the future.


>
> And an example of a record/replay implementation
> without reverse debugging capability would be
> Michael Chastain's (circa 1999) implementation
> of Linux system-call based record and replay, which
> could deterministically replay a recorded program
> execution, but did not have reverse-step or
> reverse-continue-to-breakpoint.
>

RE: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[Jakob Engblom]

> > One could have reverse without record/replay if,
> > for instance, one had a machine architecture where
> > all instructions were reversable, ie. the machine
> > itself could reverse-execute an instruction.
> 
> I think maybe some instruction can do it.
> Such as add instruction. When it forward execute, it add some number
> to a value of register. When it reverse, it can sub this number from
> the value of register. It can reverse without record.
> 
> In P record, I make a interface to use it in record_t need_dasm. But I
> still not use it. Maybe I can use it in the future.

When thinking about overflow semantics, etc., it is clear that this can never
work in general.  

The easiest way to create a reversible system is to 

1. Impose determinisim

2. Make sure you can get back to a previous state

And then you simply jump back and reexecute until some chosen point in time.
Works like a charm, and is very general.

/jakob

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[teawater]

I think your not clear my idea.

> I think maybe some instruction can do it.
> Such as add instruction. When it forward execute, it add some number
> to a value of register. When it reverse, it can sub this number from
> the value of register. It can reverse without record.

Maybe you can read this part again.

And what is the status of program? Most of time, it's just the values
of registers and memory. Do not think anything that complex.

On Tue, Oct 21, 2008 at 15:28, Jakob Engblom <jakob@virtutech.com> wrote:
>
>> > One could have reverse without record/replay if,
>> > for instance, one had a machine architecture where
>> > all instructions were reversable, ie. the machine
>> > itself could reverse-execute an instruction.
>>
>> I think maybe some instruction can do it.
>> Such as add instruction. When it forward execute, it add some number
>> to a value of register. When it reverse, it can sub this number from
>> the value of register. It can reverse without record.
>>
>> In P record, I make a interface to use it in record_t need_dasm. But I
>> still not use it. Maybe I can use it in the future.
>
> When thinking about overflow semantics, etc., it is clear that this can never
> work in general.
>
> The easiest way to create a reversible system is to
>
> 1. Impose determinisim
>
> 2. Make sure you can get back to a previous state
>
> And then you simply jump back and reexecute until some chosen point in time.
> Works like a charm, and is very general.
>
> /jakob
>
>

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[Daniel Jacobowitz]

On Wed, Oct 22, 2008 at 11:25:17AM +0800, teawater wrote:
> I think your not clear my idea.
> 
> > I think maybe some instruction can do it.
> > Such as add instruction. When it forward execute, it add some number
> > to a value of register. When it reverse, it can sub this number from
> > the value of register. It can reverse without record.
> 
> Maybe you can read this part again.
> 
> And what is the status of program? Most of time, it's just the values
> of registers and memory. Do not think anything that complex.

Jakob is right.  For instance, if the add instruction sets an overflow
flag in the status register, you can not figure out what the previous
version of the overflow flag was after the instruction.

-- 
Daniel Jacobowitz
CodeSourcery

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[teawater]

I think your mean that add is a X86 instruction or ARM insn. But some
arch's add not set flag such as MIPS.

addiu $1, $1, 10

It not set anything except $1.

And I said add insn just a example, I am not say for each arch and
each insn? just some of them.



On Wed, Oct 22, 2008 at 21:37, Daniel Jacobowitz <drow@false.org> wrote:
>
> On Wed, Oct 22, 2008 at 11:25:17AM +0800, teawater wrote:
> > I think your not clear my idea.
> >
> > > I think maybe some instruction can do it.
> > > Such as add instruction. When it forward execute, it add some number
> > > to a value of register. When it reverse, it can sub this number from
> > > the value of register. It can reverse without record.
> >
> > Maybe you can read this part again.
> >
> > And what is the status of program? Most of time, it's just the values
> > of registers and memory. Do not think anything that complex.
>
> Jakob is right.  For instance, if the add instruction sets an overflow
> flag in the status register, you can not figure out what the previous
> version of the overflow flag was after the instruction.
>
> --
> Daniel Jacobowitz
> CodeSourcery

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[teawater]

Sorry I am wrong.
In ARM, Just adds set cpsr reg. So:
add r0,r0,#10
Can reverse without record too.


On Thu, Oct 23, 2008 at 00:18, teawater <teawater@gmail.com> wrote:
> I think your mean that add is a X86 instruction or ARM insn. But some
> arch's add not set flag such as MIPS.
>
> addiu $1, $1, 10
>
> It not set anything except $1.
>
> And I said add insn just a example, I am not say for each arch and
> each insn? just some of them.
>
>
>
> On Wed, Oct 22, 2008 at 21:37, Daniel Jacobowitz <drow@false.org> wrote:
>>
>> On Wed, Oct 22, 2008 at 11:25:17AM +0800, teawater wrote:
>> > I think your not clear my idea.
>> >
>> > > I think maybe some instruction can do it.
>> > > Such as add instruction. When it forward execute, it add some number
>> > > to a value of register. When it reverse, it can sub this number from
>> > > the value of register. It can reverse without record.
>> >
>> > Maybe you can read this part again.
>> >
>> > And what is the status of program? Most of time, it's just the values
>> > of registers and memory. Do not think anything that complex.
>>
>> Jakob is right.  For instance, if the add instruction sets an overflow
>> flag in the status register, you can not figure out what the previous
>> version of the overflow flag was after the instruction.
>>
>> --
>> Daniel Jacobowitz
>> CodeSourcery
>

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[teawater]

And I think reverse without record in X86 is impossible beause the
size of its insn is not same.

On Thu, Oct 23, 2008 at 00:42, teawater <teawater@gmail.com> wrote:
> Sorry I am wrong.
> In ARM, Just adds set cpsr reg. So:
> add r0,r0,#10
> Can reverse without record too.
>
>
> On Thu, Oct 23, 2008 at 00:18, teawater <teawater@gmail.com> wrote:
>> I think your mean that add is a X86 instruction or ARM insn. But some
>> arch's add not set flag such as MIPS.
>>
>> addiu $1, $1, 10
>>
>> It not set anything except $1.
>>
>> And I said add insn just a example, I am not say for each arch and
>> each insn? just some of them.
>>
>>
>>
>> On Wed, Oct 22, 2008 at 21:37, Daniel Jacobowitz <drow@false.org> wrote:
>>>
>>> On Wed, Oct 22, 2008 at 11:25:17AM +0800, teawater wrote:
>>> > I think your not clear my idea.
>>> >
>>> > > I think maybe some instruction can do it.
>>> > > Such as add instruction. When it forward execute, it add some number
>>> > > to a value of register. When it reverse, it can sub this number from
>>> > > the value of register. It can reverse without record.
>>> >
>>> > Maybe you can read this part again.
>>> >
>>> > And what is the status of program? Most of time, it's just the values
>>> > of registers and memory. Do not think anything that complex.
>>>
>>> Jakob is right.  For instance, if the add instruction sets an overflow
>>> flag in the status register, you can not figure out what the previous
>>> version of the overflow flag was after the instruction.
>>>
>>> --
>>> Daniel Jacobowitz
>>> CodeSourcery
>>
>

RE: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[Dave Korn]

teawater wrote on 22 October 2008 17:43:

> Sorry I am wrong.
> In ARM, Just adds set cpsr reg. So:
> add r0,r0,#10
> Can reverse without record too.

  Your examples are too limited to be of practical use; almost every
instruction executed destroys information.

  It's easy to reverse "add r0,r0,#10" by subtracting 10 from r0.  But how do
you reverse "add r0,r1,#10", or anything else where the source and dest
register are different?  The original value of r0 is gone without trace, and
r1 was not changed by the instruction!


    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[teawater]

So I just say "some insn". Not all.

On Thu, Oct 23, 2008 at 01:09, Dave Korn <dave.korn@artimi.com> wrote:
> teawater wrote on 22 October 2008 17:43:
>
>> Sorry I am wrong.
>> In ARM, Just adds set cpsr reg. So:
>> add r0,r0,#10
>> Can reverse without record too.
>
>  Your examples are too limited to be of practical use; almost every
> instruction executed destroys information.
>
>  It's easy to reverse "add r0,r0,#10" by subtracting 10 from r0.  But how do
> you reverse "add r0,r1,#10", or anything else where the source and dest
> register are different?  The original value of r0 is gone without trace, and
> r1 was not changed by the instruction!
>
>
>    cheers,
>      DaveK
> --
> Can't think of a witty .sigline today....
>
>

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[Michael Snyder]

teawater wrote:
> Sorry I am wrong.
> In ARM, Just adds set cpsr reg. So:
> add r0,r0,#10
> Can reverse without record too.

OK, well, I was really speaking in the abstract.
I only meant "it's possible to imagine a target or
architecture in which reverse execution can be done
by some means other than record/replay".

Didn't necessarily mean that it could be done on any
real, existing architecture.

RE: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[Jakob Engblom]

> > Sorry I am wrong.
> > In ARM, Just adds set cpsr reg. So:
> > add r0,r0,#10
> > Can reverse without record too.
> 
> OK, well, I was really speaking in the abstract.
> I only meant "it's possible to imagine a target or
> architecture in which reverse execution can be done
> by some means other than record/replay".
> 
> Didn't necessarily mean that it could be done on any
> real, existing architecture.

Just to add some more to this:

1. Simics is such a target, as is really any deterministic simulator that is
running without any asynchronous (from the perspective of the simulator program)
inputs.  Typical cases involve booting a machine, which tends to be
non-interactive. Or running  a program that has all its input data compiled into
it or read from some place that is already on the target.   And you could say
that this is a degenerate form of record, since you DO have to "record" the
initial state in some way, even if the initial state is something that you write
yourself as a simulator configuration. It is recorded in a form that can be
brought back identically.

2. There are some odd-ball ideas in computer architecture close to the thinking
behing transactional memory where you do checkpoint and restore and reexecute
inside an actual physical CPU core.  These might also for limited scopes support
reversing without replay. 

But in general, the only way to get back to an earlier state is to record how to
get there, usually from some even earlier point.  Alternatively, use a
tape-recorder analogy and just have a limited buffer with interesting data. 


Best regards,

/jakob

_______________________________________________________

Jakob Engblom, PhD, Technical Marketing Manager

Virtutech                   Direct: +46 8 690 07 47    
Drottningholmsvägen 14      Mobile: +46 709 242 646   
11243 Stockholm             Web:    www.virtutech.com  
Sweden
________________________________________________________
 

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[teawater]

I heard some non-opensource implement of reverse. Do you have some
message about them?

On Thu, Oct 23, 2008 at 03:37, Jakob Engblom <jakob@virtutech.com> wrote:
>> > Sorry I am wrong.
>> > In ARM, Just adds set cpsr reg. So:
>> > add r0,r0,#10
>> > Can reverse without record too.
>>
>> OK, well, I was really speaking in the abstract.
>> I only meant "it's possible to imagine a target or
>> architecture in which reverse execution can be done
>> by some means other than record/replay".
>>
>> Didn't necessarily mean that it could be done on any
>> real, existing architecture.
>
> Just to add some more to this:
>
> 1. Simics is such a target, as is really any deterministic simulator that is
> running without any asynchronous (from the perspective of the simulator program)
> inputs.  Typical cases involve booting a machine, which tends to be
> non-interactive. Or running  a program that has all its input data compiled into
> it or read from some place that is already on the target.   And you could say
> that this is a degenerate form of record, since you DO have to "record" the
> initial state in some way, even if the initial state is something that you write
> yourself as a simulator configuration. It is recorded in a form that can be
> brought back identically.
>
> 2. There are some odd-ball ideas in computer architecture close to the thinking
> behing transactional memory where you do checkpoint and restore and reexecute
> inside an actual physical CPU core.  These might also for limited scopes support
> reversing without replay.
>
> But in general, the only way to get back to an earlier state is to record how to
> get there, usually from some even earlier point.  Alternatively, use a
> tape-recorder analogy and just have a limited buffer with interesting data.
>
>
> Best regards,
>
> /jakob
>
> _______________________________________________________
>
> Jakob Engblom, PhD, Technical Marketing Manager
>
> Virtutech                   Direct: +46 8 690 07 47
> Drottningholmsvägen 14      Mobile: +46 709 242 646
> 11243 Stockholm             Web:    www.virtutech.com
> Sweden
> ________________________________________________________
>
>
>
>
>

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[Jeremy Bennett]

On Thu, 2008-10-23 at 11:45 +0800, teawater wrote:
> I heard some non-opensource implement of reverse. Do you have some
> message about them?

I've heard of UndoDB:

        http://undo-software.com/

HTH,


Jeremy

-- 
Tel:      +44 (1202) 416955
Cell:     +44 (7970) 676050
SkypeID: jeremybennett
Email:   jeremy.bennett@embecosm.com
Web:     www.embecosm.com

RE: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[Jakob Engblom]

> I heard some non-opensource implement of reverse. Do you have some
> message about them?

And Simics and VmWare I guess count to that, even if they talk to gdb.

And Lauterbach and GreenHills hardware-based solutions. I would not be surprised
if ARM also sneaks one out the door, they have the trace facilities in their
cores to do it.

/jakob

Re: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[teawater]

Sorry buddies. Maybe I spend too much time to think about the implement. :)

And even if in same size insn set arch and insn is like "add
r0,r0,#10". It can't reverse without record yet. Cause when you want
reverse execute, you need load insn. But you don't know where are you
form. From prev insn or a long address that have a jump insn.
Of course, you can just record the PC, not record other thing. :)

On Thu, Oct 23, 2008 at 02:09, Michael Snyder <msnyder@vmware.com> wrote:
> teawater wrote:
>>
>> Sorry I am wrong.
>> In ARM, Just adds set cpsr reg. So:
>> add r0,r0,#10
>> Can reverse without record too.
>
> OK, well, I was really speaking in the abstract.
> I only meant "it's possible to imagine a target or
> architecture in which reverse execution can be done
> by some means other than record/replay".
>
> Didn't necessarily mean that it could be done on any
> real, existing architecture.
>
>

RE: [discuss] semantics, "replay debugging" vs. "reverse debugging"

[Jakob Engblom]

> Just to make sure we're all on the same page,
> I'm gonna state what I believe is true, and invite
> discussion or contradiction.
> 
> Replay debugging --> ability to record an execution
> sequence and "play it back" (repeat it) with some
> degree of determinism.

I think there are two very important different types of recording in existence:

* Complete CPU state tracing, like you get with the trace boxes from GreenHills
and Lauterbach, for example.  They have a limited reach as they as basically
reusing a circular buffer, but the CPU execution can be replicated 100%.
However, you can only work within the length of the recording.

* Recording system execution at a higher level and then force the execution path
at important points, such as the Zealcore/Enea solutions.  Here, you force task
switches and asynch IO to occur at certain points, and hope that the system
underneath is deterministic enough that you see the same code execution. 

I am not familiar with gdb process recording, I would assume it goes into the
first category, but running on  ahost rather than using JTAG/etc.

> Reverse debugging --> ability to make the inferior
> process "back up" to a previous state, eg. reverse
> step and reverse continue-to-breakpoint.

Sounds good. 

> They're related but not identical.  One could theoretically
> have one without the other, although in practice all
> presently existing reverse-debug targets (that I know of)
> are implemented by using record and replay.

Well, depends on how you do the recording... what you need is some way to
reconstruct thee previous state in a consistent manner. This can be done in a
few ways:

* Complete recording, as above

* Completely deterministic target, where you can reset to start, and then just
reexecute until the point of interest.  Requires a controlled world that has no
asynch inputs.  For example, booting a machien inside a full-system simulator
works like this most of the time (if you script all serial inputs needed, and
provide simulation models for network services).  Simics does this with ease,
for example. It does require that the simulation system complete imposes
semantics on all timed events, which is the case in most cases. 

* Deterministic target with recording of asynch IO.  This is what Simics does
when a simulated set of machines is connected to a physical network connection
or subject to unscripted user input.  

> One could have reverse without record/replay if,
> for instance, one had a machine architecture where
> all instructions were reversable, ie. the machine
> itself could reverse-execute an instruction.

Not particularly likely, though? Most machine instructions destroy information,
like XOR R0,R0...

> And an example of a record/replay implementation
> without reverse debugging capability would be
> Michael Chastain's (circa 1999) implementation
> of Linux system-call based record and replay, which
> could deterministically replay a recorded program
> execution, but did not have reverse-step or
> reverse-continue-to-breakpoint.

Sounds like my recording type 2 above, actually. 


Best regards,

/jakob

_______________________________________________________

Jakob Engblom, PhD, Technical Marketing Manager

Virtutech                   Direct: +46 8 690 07 47    
Drottningholmsvägen 14      Mobile: +46 709 242 646   
11243 Stockholm             Web:    www.virtutech.com  
Sweden
________________________________________________________