[discuss] going back: reverse-execution vs. checkpoint/restart

[discuss] going back: reverse-execution vs. checkpoint/restart

[Michael Snyder]

Last week I was beginning to lean in the direction of
Paul's and Frank's viewpoint.  On reflection, I think
I can argue that the two are not mutually exclusive.

As Frank points out, the "rs/bs" and "rc/bc" primatives
are useful only for a really clever target -- one that
not only has a means of backing up to a previous state,
but can do it at single-instruction granularity, fast
and efficiently, and has worked out a lot of the 'kinks'
that a lot of us haven't even thought about yet.  And
as Paul points out, there is currently only one such
target that we know of.

The bookmark (or checkpoint/restart) model is a considerably
smaller and less daunting "chunk" for the target-side
implementer to take on at one go -- and is not necessarily
limited to simulators.  If gdb implemented an interface for
checkpoint/restart, there's a good chance that a number of
targets would soon take advantage of it.

And it's quite reasonable to suppose that there is an
evolutionary path from checkpoint/restart to reverse
execution.  We've already discussed some of the ways
in which it could go, so I think it's virtually a given
that it is possible to get from A to B.  For that matter,
it should be also possible to get from B to A: a target
that only supports the rs/bs primatives should be able
to implement checkpoint/restart in terms of them.

How much of that evolution needs to take place on the
gdb side, and how much on the target side, is a great
field for discussion -- I would only note that we do
not have to answer that question now.  If we convince
ourselves that both sets of primatives are useful for
some targets, and that one may evolve into the other,
then there is no reason not to implement them both.
Being able to do either one but not the other would
be better than not being able to do either.

Certainly users have been asking for checkpoint/restart
for years, if not decades.  It would be very cool if
we could give it to them, with an interface that lends
itself to porting to various target environments.

And certainly the idea of reverse execution has been
around for years too, and it would be cool to be able
to support that.

So why settle for one or the other?  The beauty of
gdb is that it doesn't need to know HOW the target
accomplishes a thing.  Details such as whether the
cached states are kept in a circular buffer are
for the target implementers to worry about.  We just
define our interface specification to be as general
as possible.  The less we assume about the target-side
implementation, the better.

That said -- it's still useful and fun to discuss how
these things may be accomplished, and should help us
to design a generally useful interface.

Re: [discuss] going back: reverse-execution vs. checkpoint/restart

[Daniel Jacobowitz]

On Mon, May 23, 2005 at 11:51:03AM -0700, Michael Snyder wrote:
> And it's quite reasonable to suppose that there is an
> evolutionary path from checkpoint/restart to reverse
> execution.  We've already discussed some of the ways
> in which it could go, so I think it's virtually a given
> that it is possible to get from A to B.  For that matter,
> it should be also possible to get from B to A: a target
> that only supports the rs/bs primatives should be able
> to implement checkpoint/restart in terms of them.

Not necessarily.  Once you back up and manually make a state change it
may not be possible to get back to some other state previously reached.

> How much of that evolution needs to take place on the
> gdb side, and how much on the target side, is a great
> field for discussion -- I would only note that we do
> not have to answer that question now.  If we convince
> ourselves that both sets of primatives are useful for
> some targets, and that one may evolve into the other,
> then there is no reason not to implement them both.
> Being able to do either one but not the other would
> be better than not being able to do either.

Thank you, Michael - that's what I was trying to suggest, but not very
well.

-- 
Daniel Jacobowitz
CodeSourcery, LLC

Re: [discuss] going back: reverse-execution vs. checkpoint/restart

[Michael Snyder]

Daniel Jacobowitz wrote:
> On Mon, May 23, 2005 at 11:51:03AM -0700, Michael Snyder wrote:
> 
>>And it's quite reasonable to suppose that there is an
>>evolutionary path from checkpoint/restart to reverse
>>execution.  We've already discussed some of the ways
>>in which it could go, so I think it's virtually a given
>>that it is possible to get from A to B.  For that matter,
>>it should be also possible to get from B to A: a target
>>that only supports the rs/bs primatives should be able
>>to implement checkpoint/restart in terms of them.
> 
> 
> Not necessarily.  Once you back up and manually make a state change it
> may not be possible to get back to some other state previously reached.

OK -- but that just means that for any of these requests,
we must take into account the possibility that the request
may fail.  EG. a target may support checkpoints, but a
request for a specific checkpoint may fail for reasons
that only the target may know (eg. you went back in time
and "killed your grandfather", so the future you remember
doesn't exist any more).

So, we export the simplest, most general and least
restrictive interface we can think of, make no assumptions
about the implementation details, and always check for
failure messages.

Re: [discuss] going back: reverse-execution vs. checkpoint/restart

[Dan Shearer]

On Mon, May 23, 2005 at 11:51:03AM -0700, Michael Snyder wrote:

> As Frank points out, the "rs/bs" and "rc/bc" primatives
> are useful only for a really clever target -- one that
> not only has a means of backing up to a previous state,
> but can do it at single-instruction granularity, fast
> and efficiently, and has worked out a lot of the 'kinks'
> that a lot of us haven't even thought about yet.  And
> as Paul points out, there is currently only one such
> target that we know of.

True. One of the interesting things here is that while the limiting case
above is just the same as checkpointing before in terms of the technical
concept, the end result is quite different. I charaterise the above as
reversible hardware and the below as timeshifting.

> The bookmark (or checkpoint/restart) model is a considerably
> smaller and less daunting "chunk" for the target-side
> implementer to take on at one go -- and is not necessarily
> limited to simulators.  If gdb implemented an interface for
> checkpoint/restart, there's a good chance that a number of
> targets would soon take advantage of it.

I agree.

http://sbuml.sourceforge.net/ (32-bit intel User Mode Linux instances)
probably could use it straight away.

Xen (which runs Linux, BSD and other targets on x86 only for now)
currently can save and restore memory state but doesn't do disk state.
But presumably if the developers decided it was interesting they could
quickly do it. See http://www.cl.cam.ac.uk/Research/SRG/netos/xen/

QEMU (which runs numerous OSs on PPC, x86, Sparc and others to varying
degrees of completeness) already implements savevm and loadvm commands
for memory and a snapshot command for disk images. QEMU would not be far
from being able to incorporate a stub supporting this level of
functionality. See http://fabrice.bellard.free.fr/qemu/

DragonflyBSD and a number of other OSs offer checkpointing at the
process level and are working to expand the scope.

In commercial space, Solaris for example has had full-system
checkpointing for nearly ten years done by Aurema, who also did
implementations for other companies.

-- 
Dan Shearer
dan@shearer.org

Re: [discuss] going back: reverse-execution vs. checkpoint/restart

[Dan Shearer]

On Tue, May 24, 2005 at 05:01:55AM +0930, Dan Shearer wrote:

> True. One of the interesting things here is that while the limiting case
> above is just the same as checkpointing before in terms of the technical

s/before/below/

-- 
Dan Shearer
dan@shearer.org

Re: [discuss] going back: reverse-execution vs. checkpoint/restart

[Paul Schlie]

In hopes it may be helpful, upon reviewing some of the earlier posts:

- checkpoints/undo-reverse can never "fail" even if the current
  program state is manually modifed, as by definition a check-pointed
  state represents the "state" of the program at some previous point in
  time, therefore insensitive to it's current state (altered or not,
  with a caveat noted below).

- it's likely a good idea to differentiate check-pointing a process
  or even a thread running on an OS, from check-pointing the entire
  machine inclusive of the OS and all of it's processes. (as where the
  later may be infeasible in the general case except for very small
  embedded systems, the former may be typically reasonable with the
  understanding that the state of the world around it on the other
  side of the system interfaces represented in other process states
  would not have been check-pointed, therefore are in what ever state
  they were last in; which is likely of little consequence if one is
  attempting to debug an algorithm which doesn't make sensitive system
  calls, however if a socket was opened in a network protocol loop but
  not closed prior to reverting to a previous program state which may
  have been prior to the socket being originally opened, things could
  get weird, so there's no magic, powerful features may require
  delicate piloting.)

- in all reasonably useful cases, GDB has direct access to all the
  information required without necessity of explicit target support,
  who's implementation my be partitioned in such a way that targets
  may then improve the efficiency of the solution in an incremental
  manor depending on the sophistication of the target, without
  requiring that any target support any particular feature to enable
  basic check-point/restart, and undo-reverse execution; although
  it will be true that in order to achieve a level of efficiency
  likely required to interactively do so for large complex processes,
  some amount of target assist may be practically necessary (however
  there's no magic, check-pointing an entire multi-process platform
  may never be practical under any circumstance, regardless of target
  support or not).