reverse debugging implementation

reverse debugging implementation

[David McQuillan]

Hi,

I see gdb now supports reverse debugging. This is something I 
implemented for myself a number of years ago with my own simulators when 
I was working on testing some compilers and other stuff. That all died a 
long time ago but some of the ideas from it might be useful if you 
haven't done them already.

Firstly as far as I can see gdb saves all the state change for every 
instruction. This is unnecessary, all you have to do is save the state 
of the cpu every few thousand instructions and for each instruction only 
save the state of memory locations before they are changed. Going back 
one instruction then involves rolling back the memory changes, the 
registers are set up then go forward n-1 instruction to go back one.

I also had debug instructions to mark the current spot, then one could 
go between a few different different states easily to check on the 
difference.

I think practically everything else I had about what to do about library 
calls is there - I intercepted system calls so they weren't redone just 
the old results returned so I had to save both before and after looks. 
Special work had to be done about allocating and freeing space and I 
only had serial files and no special device access so you can see I had 
a fairly straightforward environment.

If you used virtual memory tricks it might be possible to save the state 
of the memory that way instead of even taking before looks. It would 
slow going backwards a bit but I never noticed any particular delay 
going back an instruction and machines have sped up and there's lots 
more memory nowadays.

Cheers,
David McQuillan

Re: reverse debugging implementation

[paawan oza]

Hi,

please find my inline.

Regards,
Oza.



----- Original Message ----
From: David McQuillan <dmcq@fano.co.uk>
To: gdb@sourceware.org
Sent: Sun, August 22, 2010 7:09:14 PM
Subject: reverse debugging implementation

Hi,

I see gdb now supports reverse debugging. This is something I implemented for 
myself a number of years ago with my own simulators when I was working on 
testing some compilers and other stuff. That all died a long time ago but some 
of the ideas from it might be useful if you haven't done them already.

Firstly as far as I can see gdb saves all the state change for every 
instruction. This is unnecessary, all you have to do is save the state of the 
cpu every few thousand instructions and for each instruction only save the state 
of memory locations before they are changed. Going back one instruction then 
involves rolling back the memory changes, the registers are set up then go 
forward n-1 instruction to go back one.

oza : so does it mean that instructions which changes memory you can take one 
step backward, but instructions which have changed registers you can not step 
back by one instruction but n-1. so we lost the ability to track back by 
instruction, yes of course it is performance gain by the factor of n.

I also had debug instructions to mark the current spot, then one could go 
between a few different different states easily to check on the difference.

I think practically everything else I had about what to do about library calls 
is there - I intercepted system calls so they weren't redone just the old 
results returned so I had to save both before and after looks. Special work had 
to be done about allocating and freeing space and I only had serial files and no 
special device access so you can see I had a fairly straightforward environment.

Oza: -> Is it possible to revoke all system calls, such as revoking sent signal 
etc, doesnt it ned kernel change in all cases and probably making ptrace more 
powerful. ?

If you used virtual memory tricks it might be possible to save the state of the 
memory that way instead of even taking before looks. It would slow going 
backwards a bit but I never noticed any particular delay going back an 
instruction and machines have sped up and there's lots more memory nowadays.

Oza -> does it involve saving whole virtuall address space on disk or something 
?

Cheers,
David McQuillan


      

Re: reverse debugging implementation

[David McQuillan]

Hi paawan, my replies about what I did..

David

On 25/08/2010 07:30, paawan oza wrote:
 >...
> Firstly as far as I can see gdb saves all the state change for every
> instruction. This is unnecessary, all you have to do is save the state of the
> cpu every few thousand instructions and for each instruction only save the state
> of memory locations before they are changed. Going back one instruction then
> involves rolling back the memory changes, the registers are set up then go
> forward n-1 instruction to go back one.
>
> oza : so does it mean that instructions which changes memory you can take one
> step backward, but instructions which have changed registers you can not step
> back by one instruction but n-1. so we lost the ability to track back by
> instruction, yes of course it is performance gain by the factor of n.

No, every single step backwards involved going back to the last time the 
registers were saved unrolling the memory changes on the way. The 
simulators kept the instruction count so I simply set them to stop when 
they executed the current instruction count - count when registers were 
saved - 1 instructions. The only special code in the simulators was to 
do the before looks of memory writes so it was quite a minimal change 
for existing simulators.

 >...
> I think practically everything else I had about what to do about library calls
> is there - I intercepted system calls so they weren't redone just the old
> results returned so I had to save both before and after looks. Special work had
> to be done about allocating and freeing space and I only had serial files and no
> special device access so you can see I had a fairly straightforward environment.
>
> Oza: ->  Is it possible to revoke all system calls, such as revoking sent signal
> etc, doesnt it ned kernel change in all cases and probably making ptrace more
> powerful. ?

No, I simply saved any the memory the system calls would change plus the 
registers after the call. Actually I didn't save the state afterwards, I 
used the same space for the before look and it swapped between being the 
before look and the after look depending on whether I had rolled to 
before the call. The system calls were not redone when going forward 
after having looked at a previous point. Thus  for example if you rolled 
back over typewriter input on going forward it would return what was 
typed the last time.

I didn't actually free memory at the time a free was done. That was 
delayed until I'd used up too much space on saving memory before looks 
and was then freed at the same time as that.

The serial files bit was a special to allow changes to be made to the 
state after rewinding to a previous point and also one might want a 
monitor file to be written to again rather than just setting the memory 
when redoing instructions going forwards. If one only has serial files 
and a simple environment one can change the previous state, then before 
going forward one has to reset the file pointers and free any memory 
that was allocated at a future point. It could be done with something 
more complicated but that was my only need and I actually didn't need to 
do it much - being able to view what went wrong in detail going 
backwards and forwards is quite enough facility for most purposes when 
debugging without trying to roll back the system in general.

> If you used virtual memory tricks it might be possible to save the state of the
> memory that way instead of even taking before looks. It would slow going
> backwards a bit but I never noticed any particular delay going back an
> instruction and machines have sped up and there's lots more memory nowadays.
>
> Oza ->  does it involve saving whole virtuall address space on disk or something
> ?

No I was just pointing out that one could set the writeable pages read 
only after saving the registers then just copy whole pages and set them 
writeable as required going forwards. It's not something I did but it 
would mean the simulators needn't even do memory before looks and if the 
time between register saves was made something like a few million 
instructions rather than the few thousand I did it would be quite 
economic on memory. It might help with dealing with memory frees 
properly as well rather than leaving the space visible like I did. Going 
back a few million instructions and forward again would be practically 
instantaneous as far as a user is concerned with modern processors.

On performance with the way I did it I always ran with it so a backtrack 
could be done and had it set so it could go back a few million 
instructions before the earlier bits were thrown away. The saving of the 
memory was only a small overall overhead on speed.

David

Re: reverse debugging implementation + commands

[David McQuillan]

Just a bit on testing for conditions when going backwards.

Just had a look at reverse.c and it is very different from anything I 
ever did. To find the last time a location was changed for instance it 
looks like it would go back one instruction at a time until the 
condition is satisfied. I can see a middle way that encompasses both 
approaches in that if the registers are saved on every single 
instruction my approach ends up being the same as what reverse.c does so 
I've written it up here that way:

set found counter to unset
set check counter to here
while found counter is null and we can go backwards
   roll back from check counter to previous save point
   go forward till check counter reached
    if condition set then
      set found counter to instruction counter
   endif
   if found counter not set
     roll back to last save point
     set check counter to this point
   endif
endwhile

At the end of this found counter if set gives the instruction counter 
when the condition was last satisfied.

With this there is no special work needed to check conditions when going 
backwards compared to going forwards.

David

RE: reverse debugging implementation

[Engblom, Jakob]

> > of memory locations before they are changed. Going back one
> instruction then
> > involves rolling back the memory changes, the registers are set up
> then go
> > forward n-1 instruction to go back one.

If you go back in the gdb mailinglist, you will see that this is exactly
how Wind River Simics does its reverse execution.  Back up to a recent
checkpoint, and then reexecute forward to some point in time.  Silently
record any breakpoints, and if you are running breakpoints backwards, go
back to the checkpoint again and reexecute forward to the point in time
where the breakpoint hits.  

Works very well for a full-system simulator where the entire target
state is encapsulated and controlled.

I believe similar things have been done in the RTL simulation field in
the 1990s, but I have only anecdotal evidence.  If you have
checkpoints/snapshots and a deterministic simulator it is an "obvious"
thing to do.

/jakob


Jakob Engblom | Wind River | Technical Marketing Manager - Simics
Stockholm, Sweden
mobile +46 734 368 958 | email jakob.engblom@windriver.com

Re: reverse debugging implementation

[paawan oza]

Hi,

I am not sure whether that implementation will improve performance drastically 
compare to existing gdb reversible debuggin implementation.
as
does it involve 

-> stopping at every insn and find out whether insn is changing register or 
memory, and if register then record it (probably not every insn but depends on 
interval and no of memory changing insns)

-> when you want to go back, you go back n-1 and forward execution till 
current-1, that probably involves single steeping which has performance impact.

of course the record for memory is saved as we do not need to save architectural 
state at every insn, but performance !!

Regards,
Oza.




----- Original Message ----
From: "Engblom, Jakob" <Jakob.Engblom@windriver.com>
To: gdb@sourceware.org
Sent: Thu, September 2, 2010 12:18:02 PM
Subject: RE: reverse debugging implementation

> > of memory locations before they are changed. Going back one
> instruction then
> > involves rolling back the memory changes, the registers are set up
> then go
> > forward n-1 instruction to go back one.

If you go back in the gdb mailinglist, you will see that this is exactly
how Wind River Simics does its reverse execution.  Back up to a recent
checkpoint, and then reexecute forward to some point in time.  Silently
record any breakpoints, and if you are running breakpoints backwards, go
back to the checkpoint again and reexecute forward to the point in time
where the breakpoint hits.  

Works very well for a full-system simulator where the entire target
state is encapsulated and controlled.

I believe similar things have been done in the RTL simulation field in
the 1990s, but I have only anecdotal evidence.  If you have
checkpoints/snapshots and a deterministic simulator it is an "obvious"
thing to do.

/jakob


Jakob Engblom | Wind River | Technical Marketing Manager - Simics
Stockholm, Sweden
mobile +46 734 368 958 | email jakob.engblom@windriver.com


      

RE: reverse debugging implementation

[Engblom, Jakob]

> I am not sure whether that implementation will improve performance
> drastically
> compare to existing gdb reversible debuggin implementation.
> as
> does it involve
> 
> -> stopping at every insn and find out whether insn is changing
> register or
> memory, and if register then record it (probably not every insn but
> depends on
> interval and no of memory changing insns)

Neither. We only reexecute all the instructions, period.  No saving of
state other than at the regular checkpoints (snapshots).

> -> when you want to go back, you go back n-1 and forward execution
till
> current-1, that probably involves single steeping which has
performance
> impact.

Not really, we run the target system in JIT mode typically, only
stepping the last few instructions if that is in the middle of a
translation unit.  Note that his is using a complete target system
simulator, not at all relying on the host.  Simics can stop at a precise
point in virtual time, that is key to this exercise.

> of course the record for memory is saved as we do not need to save
> architectural
> state at every insn, but performance !!

Note that we also include networks, disks, and the rest of the virtual
world in this approach.  

VMWare is doing something similar with their record/replay, but in a
different way with different performance/portability/generality
tradeoffs.

In any case, comparing performance with the gdb record-replay system is
not very useful as we atually do something different. First of all, this
is system-level, so you can work with boot loaders, operating systems,
and multithreaded and multicore target.  See
http://blogs.windriver.com/engblom/2010/04/what_is_simics_really.html
for more on Simics if you are interested.

But I am not here to sonud like an advertisement, I just wanted to point
out that checkpoint/snapshot + deterministic reexecution is a viable way
to do reverse execution. 

/jakob