[reverse] A "toy" implementation of reverse execution

[reverse] A "toy" implementation of reverse execution

[Michael Snyder]

Hey folks,

Here's a "toy" implementation of a target that can,
to a very limited extent, act as if it's offering
reverse execution to gdb.  I hope it will be useful
for trying out ideas.  It should be useful for both
the "bookmark" approach and the "reverse-stepi" method.

What I've done is, starting from the "sample" program in RDA,
I added the ability to understand "tfind" requests, and then
added on a module that could read simplified tracepoint frames
from a file, and then serve them back to gdb.

Then I generated a trace frame file from the testsuite program
"break.c", starting at main and saving a tracepoint for every
instruction.  It only took about 157 frames.   ;-)

Now, if I feed that file to my rda-derived trace frame server,
"tfind next" becomes equivalent to "stepi", and "tfind prev"
becomes equivalent to "reverse-stepi".

With those as primatives, reverse-step turns out to be,
to first approximation at least, fairly easy:

	define reverse-si
	  tfind -
	end

	define si
	  tfind
	end

	define unstep
	  reverse-si
	  set $foo=$trace_line
	  while $foo==$trace_line
	    reverse-si
	  end
	  si
	end

As several of us speculated, the algorhythm for stepping backward
involves first taking a backstep, then establishing the line range
and stepping out of it, and finally taking one forward step.

I've created a branch and checked in my modified rda, along with
a hacked-up gdb that I'm using to help create trace frame files.
The branch is "msnyder-tracepoint-checkpoint-branch", and y'all
are welcome to play with it.  There's a README-CHECKPOINTS file.

Re: [reverse] A "toy" implementation of reverse execution

[Michael Snyder]

[-- Attachment #1: Type: text/plain, Size: 2012 bytes --]

And I forgot to attach my example.  This contains a trace-frame
file for the testsuite/gdb.base/break.c program, with one frame
per instruction.  Using the rda server and any x86 gdb you can
debug this forward and backward, by instruction or by source line.


Michael Snyder wrote:
> Hey folks,
> 
> Here's a "toy" implementation of a target that can,
> to a very limited extent, act as if it's offering
> reverse execution to gdb.  I hope it will be useful
> for trying out ideas.  It should be useful for both
> the "bookmark" approach and the "reverse-stepi" method.
> 
> What I've done is, starting from the "sample" program in RDA,
> I added the ability to understand "tfind" requests, and then
> added on a module that could read simplified tracepoint frames
> from a file, and then serve them back to gdb.
> 
> Then I generated a trace frame file from the testsuite program
> "break.c", starting at main and saving a tracepoint for every
> instruction.  It only took about 157 frames.   ;-)
> 
> Now, if I feed that file to my rda-derived trace frame server,
> "tfind next" becomes equivalent to "stepi", and "tfind prev"
> becomes equivalent to "reverse-stepi".
> 
> With those as primatives, reverse-step turns out to be,
> to first approximation at least, fairly easy:
> 
>     define reverse-si
>       tfind -
>     end
> 
>     define si
>       tfind
>     end
> 
>     define unstep
>       reverse-si
>       set $foo=$trace_line
>       while $foo==$trace_line
>         reverse-si
>       end
>       si
>     end
> 
> As several of us speculated, the algorhythm for stepping backward
> involves first taking a backstep, then establishing the line range
> and stepping out of it, and finally taking one forward step.
> 
> I've created a branch and checked in my modified rda, along with
> a hacked-up gdb that I'm using to help create trace frame files.
> The branch is "msnyder-tracepoint-checkpoint-branch", and y'all
> are welcome to play with it.  There's a README-CHECKPOINTS file.
> 
> 


[-- Attachment #2: example.tar.gz --]
[-- Type: application/x-tar, Size: 12005 bytes --]

Re: [reverse] A "toy" implementation of reverse execution

[Soam Vasani]

Hi,

We've implemented some reverse debugging functionality using
checkpoints, but without stopping at every instruction.
Currently it only works on native i386.

Please see http://lizard.sourceforge.net/explain.html for
more information.

regards,
soam

Re: [reverse] A "toy" implementation of reverse execution

[Michael Snyder]

Soam Vasani wrote:
> Hi,
> 
> We've implemented some reverse debugging functionality using
> checkpoints, but without stopping at every instruction.
> Currently it only works on native i386.
> 
> Please see http://lizard.sourceforge.net/explain.html for
> more information.
> 
> regards,
> soam

Wow -- I read your description -- pretty interesting!

What do you think would be the chances of combining the
non-interactive trace process and the interactive replay
process into one -- eg. under the control of gdb -- so that
you could back up and then go forward along a different path?

Re: [reverse] A "toy" implementation of reverse execution

[Soam Vasani]

Michael Snyder wrote:
 > What do you think would be the chances of combining the
 > non-interactive trace process and the interactive replay
 > process into one -- eg. under the control of gdb -- so that
 > you could back up and then go forward along a different path?

Yeah, it should be quite doable.  (And it's been on our todo list for
some time.)

regards,
soam

Reversible GDB resources

[Dan Shearer]

I think we need more sample working code to develop a convincingly good
design for reversible GDB more code (thanks to Johan Rydberg and Michael
Snyder for what we have so far.)

It turns out there are several projects completed over the last two
years that have done a reversible GDB. I asked two of them if they could
make their code available for review, and another two if they'd mind
publishing their reversible targets.

So I hope that this group will soon have available much better resources
for testing reversibility approaches:

* a total of four different sets of reversible GDB patches known to
  work when pointed at exactly the right kind of target (I'm including
  Soam Vasani's Lizard link here, nice research project)

* a total of at least 4 reversible targets publicly available to help in
  development and testing of a reversible GDB (I'm including Michael's
  toy tracepoint target here, hopefully it can evolve into a standard
  testbed catering for other technologies too. But it demonstrates a
  point already.) Some people will have access to closed-source Simics
  too.

-- 
Dan Shearer
dan@shearer.org

Re: Reversible GDB resources

[Dan Shearer]

On Sun, Jun 05, 2005 at 08:41:49AM +0930, Dan Shearer wrote:
> I think we need more sample working code to develop a convincingly good
> design for reversible GDB more code (thanks to Johan Rydberg and Michael
> Snyder for what we have so far.)
> 
> It turns out there are several projects completed over the last two
> years that have done a reversible GDB. I asked two of them if they could
> make their code available for review, and another two if they'd mind
> publishing their reversible targets.

Here's the first one. ReVirt (part of the CoVirt project as mentioned before,
see http://www.eecs.umich.edu/CoVirt/ ) published their GDB at
http://www.eecs.umich.edu/~kingst/uml-kd.tgz . This is the entire project,
a 60Mb download.

The CoVirt project (see email address on their web page) told me:

> We did not modify gdb directly, instead we have a small wrapper
> program that intercepts each of our reverse commands and sends
> specific hypercalls to our vmm.  That program is called mygdb and can
> be found in the  uml-kd/uml-2.4.20 directory.  I uses gdb
> functionality through the gdb user interface (via pipes) and the
> algorithms used to implement each of our new commands can be found in
> that application.

-- 
Dan Shearer
dan@shearer.org