Stories
Slash Boxes
Comments
Search

News for nerds, stuff that matters

Slashdot Log In

Log In

Create Account  |  Retrieve Password

Hindsight: Reversible Computing

Posted by Hemos on Fri Mar 11, 2005 08:35 AM
from the step-back-into-the-past dept.
Programming Technology IT
One of the more interesting tech pieces that came out this week has been Hindsight [PDF]. Hindsight is made by Virtutech and is billed as the "the first complete, general-purpose tool for reverse execution and debugging of arbitrary electronic systems." The demos were received extremely well and it just looks cool.
+ -
story
This discussion has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Hindsight: Reversible Computing 50 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.

  • Sounds good - but expensive. (Score:5, Informative)

    by bigtallmofo (695287) on Friday March 11 2005, @08:39AM (#11909317)
    From reading about this earlier [eetimes.com], it is a very exciting technology for embedded systems. It does seem a bit expensive though:

    Hindsight will go into beta sites in May, with production slated for July. Incremental cost over Simics is around $5,000 per seat, but Hindsight won't target single seats. A typical engagement, including Simics, Hindsight and some initial model development, is estimated at $200,000 to $300,000 for a software development group with 10 to 20 seats.

  • That's just nutty... (Score:4, Informative)

    by The Desert Palooka (311888) on Friday March 11 2005, @08:39AM (#11909318)
    With Simics Hindsight it is now possible to step back just before the error and then run forward again, providing another opportunity to reproduce the error and look more closely at what occurs in detail, without having to re-launch the program. Simics Hindsight can even unboot an operating system, running the code backwards until it reaches the initial hardware launch instruction after a hardware reset.

    That would be quite nice... It almost seems like a shuttle head or what not for programmers... Rewind, play, slow motion and so on... I know they said it's the first complete one, but is there anything else out there like this?
    • Take a look at
      http://www.lambdacs.com/debugger/debugger.html [lambdacs.com] I'm sure a Hindsight sales person would (correctly) say this isn't a complete solution, but its the closest thing I've seen before this article.
    • The only way to "back up" execution is to save your state as you go. In Computational Theory, this amounts to the fact that, given a particular UTM in a particular state (state, position on the tape, values on the tape) an infinite number of UTMs exist which, at some point in their execution, arrive at a state equal to that particular state. (we leave the proof to the reader)

      Thus the only way to "back up" computation is to know the past of that machine, i.e. a state log of the execution of the program.

      B

      • Re:That's just nutty... (Score:4, Interesting)

        by VAXman (96870) on Friday March 11 2005, @10:31AM (#11910366)
        The only way to "back up" execution is to save your state as you go.

        At first I wasn't sure that your statement was true, but after thinking about it for 30 seconds or so, I realized it definitely was. Every instruction produces a deterministic calculation and can be reversed, right? If we have "ADD EAX, EBX", and know the current values of EAX and EBX, going backwards is easy, right?

        Well, one really difficult case is jumps. How do you know what the previous instruction executed was? On X86 this would be pretty difficult since the encodings are non-regular, but even on an ISA with regular encodings it would be non-trivial because it would be difficult to figure whether you got to the instruction via a jump (which could be anywhere in memory), or from the previous instruction.

        Add things such as Self-Modifying Code, and you have a real headache. Yes, you definitely need to track state as you go, though I'm not sure you'd need to save anything more than just the Instruction Pointer (which X86 does have a mechanism for). If you know what instructions were executed, it should be pretty easy to backtrack in time. I think.
        • Not only that, just try to undo a "i += rand()" type of statement... or user input... or a network call. Most network protocols do not support "forget the last three statements and roll back in state". :)

        • The only way to "back up" execution is to save your state as you go.

          At first I wasn't sure that your statement was true, but after thinking about it for 30 seconds or so, I realized it definitely was. Every instruction produces a deterministic calculation and can be reversed, right? If we have "ADD EAX, EBX", and know the current values of EAX and EBX, going backwards is easy, right?

          Try this UTM program:

          Set A and B to the values 1 and 2
          Add values of A and B and put them in C
          Put value x1 and y1 int

        • Every instruction produces a deterministic calculation and can be reversed, right?

          Wrong.

          mov eax, 0
          mov eax, [eax]
          xor eax, eax
          jmp eax
          imul eax , 0
          ...
          Basically any code that moves any data is crunching some other data. Given that RISC and CISC processors are Load/Store based architectures, that makes for pretty much a majority of cases.
    • There's an academically interesting (I'm assured :)) Java system similar to this called Bdbj [ed.ac.uk]. I'm not sure if it's useful in a real context, but I assume it is to some degree.
    • but is there anything else out there like this?

      Yes, in the museum.

      The debugger that came with BS3 on the TR440 [vaxman.de] had an option that enabled you to step back a defined (small due to lack of space for saving) number of steps if you set the appropriate switch when compiling. Very cool feature - 30 years ago !

      CC.

  • UI (Score:5, Interesting)

    by GigsVT (208848) on Friday March 11 2005, @08:43AM (#11909347) Journal
    They say the way they accomplish this is running the program in some sort of sandbox and taking checkpoints every so often and then when you step back, it actually runs forward from the closest checkpoint and stops one instruction short.

    My question is how UI interactions are handled. If the execution between the checkpoint and current-1 instruction includes a UI interaction, it might be very confusing to the programmer to know what or how many UI interactions need to be carried out to accomplish the backstep.
    • A big honking emulator with state saving in a memory buffer. I'm sure they've already accounted for recursive loops and interactions, just they've improved the ability to load / save states.

      Don't the video game emulators already do this?
      • Don't the video game emulators already do this?

        Yeah. To create a movie they save the state and log the following input, so the game can be replayed exactly. ZSNES also has a rewind key, but I haven't messed with it.

    • Re:UI (Score:3, Interesting)

      by TuringTest (533084)
      Furthermore, this won't work for finding bugs on concurrent programs due to race conditions or parallel threads corrupting a shared resource.

      Those bugs might be catched if the environment would record instructions one-by-one, but as is you may find a bug in your execution, roll back to the checkpoint and find that the bug is gone in the replay. Hey, that would be funny if it happened on a TV football game...

  • Mirror (Score:5, Informative)

    by tabkey12 (851759) on Friday March 11 2005, @08:45AM (#11909353) Homepage
    Mirror of the PDF [mirrordot.org]

    Never underestimate the Slashdot Effect!

  • Virtualization layer for checkpointing and steppin (Score:5, Informative)

    by jaxdahl (227487) on Friday March 11 2005, @08:45AM (#11909356)
    This seems to create a virtualization layer where checkpoints are saved periodically, then instructions are single stepped through. So to step back, it goes to the first checkpoint before the instruction you want to step back to, then it single steps up to that point. This would aid in kernel-level debugging where data structures might be overwritten from almost anywhere in the computer that can access the kernel space -- no need to set a watchpoint then reboot and wait for the next error to occur.

    • checkpoint the hard disk too? (Score:4, Insightful)

      by goombah99 (560566) on Friday March 11 2005, @10:15AM (#11910154)
      the state of a computer is not the state of the memory. it includes the hard disk as well. to give one tiny example: the vvirtual memory. to give a better example, if a program overwrites a file you have to check point back over that too. to give an even better example, if you were debuggin a disk defragmenting program every bit on the disk could move.
  • Yeah, I can see some technical hurdles here ... like storing all old variable/register contents, jump addresses, etc.

    How in the world did they pull this off?
    • If you read the article carefully, it does actually say. Basically they've optimised the printf() and scanf() functions, from the standard C libraries, to a very high degree. Using these optimised functions allows them to literally run the processor backwards, with a little help from Euler Integration to approximate the execution path. Its very clever indeed.
    • It's in the article, the section labelled "how it works".

      Assuming most slashdotters are lazy f*cks, a condensed explanation: it takes a snapshot every couple of seconds, then when you want to go backwards it moves all the way to the previous snapshot, then runs forwards ignoring sleep() to appear instant.

  • But what about external events (Score:5, Interesting)

    by bangzilla (534214) on Friday March 11 2005, @08:47AM (#11909368) Journal
    It's all very well to be able to run code backwards/forwards/slo-mo/etc, but how to handle non deterministic external events coming in from the network? Does this tool presume that all applications to which it will be applied live in isolation?
  • I can see how this software can come in real handy, but it won't work in every situation. It states in TFA that Hindsight doesn't do the naive approach of recording every instrction, but rather takes snapshots and tries to fill in the gaps. There are many types of calculations out there (think The Game of Life or other CAs) that by their nature cannot be reversed, so all of those states would have to be stored or it would be mathematically impossible to calculate the reverse steps.

    Therefore, I can't see their approach being foolproof, and the over-obvious advertisement (this is what normal debugging toolbars look like, but they don't have a nifty step-one-back feature) seems too bright to be withot caveat. At $5,000 a seat I'd say buyer beware.

    • Re:Too good to be true... (Score:4, Informative)

      by CausticPuppy (82139) on Friday March 11 2005, @09:33AM (#11909747) Homepage
      There are many types of calculations out there (think The Game of Life or other CAs) that by their nature cannot be reversed, so all of those states would have to be stored or it would be mathematically impossible to calculate the reverse steps.

      It also says in TFA that it doesn't actually calculate the reverse steps, so it doesn't matter if it's mathematically impossible.

      What it does do is take complete snapshots every (for example) 100 steps. In order to move "backwards" a step, it returns to the previous breakpoint (a known state) and goes forward 99 steps.
      Then it returns to the same breakpoint and goes forward 98 steps. And so on. So from your perspective, you see the 99th step, 98th, 97th, and on down. It only LOOKS like it's running backwards.

      This would even work for the game of life.

      So the performance tradeoff would be this:
      More frequent breakpoints causes forward execution to be slower because it's spending more time saving data at regular intervals for breakpoints, but "reverse" execution would be faster because it has to iterate fewer steps from the previous breakpoint.
  • Now when I'm playing online, when I die I can rewind.

    I can hear it now, "Godlike!"

  • The Omniscient Debugger? (Score:3, Informative)

    by Anonymous Coward on Friday March 11 2005, @08:51AM (#11909402)

    http://www.lambdacs.com/debugger/debugger.html/ [lambdacs.com]

    Seems like this has been done before, at least for java apps...

  • BSOL? (Score:3, Funny)

    by bunyip (17018) on Friday March 11 2005, @08:53AM (#11909417)
    So, would reversible computing let me have a Blue Screen Of Life?

    That would be so cool...

    Alan.

  • Problems with platform emulalators (Score:3, Insightful)

    by selectspec (74651) on Friday March 11 2005, @08:53AM (#11909422)
    Hindsight is a service within their platform emulator. While it sounds nifty, and I'm all for it... emulators never behaive the same as the real platform... especially in embedded environments. The timing of peripherals is never the same on the emulator as the platform. The result is that lots of time is spent debugging the emulator environment that bares little fruit for the platform environment.

    What would be far more useful, would be to write tools that took advantage of many of the onboard hardware debugging capabilities of some of the common embedded chip architectures.

  • Thats simple... (Score:3, Funny)

    by Anonymous Coward on Friday March 11 2005, @08:54AM (#11909432)
    just invert the micro clock signal so everything runs backwards :)

  • Not by a decade. (Score:5, Interesting)

    by Murmer (96505) on Friday March 11 2005, @08:56AM (#11909449) Homepage
    This technology has existed, in GPL form [shout.net], for ten years. It's just had exactly zero uptake.

    I read this usenet post [google.ca] every now and then when I'm trying to fix something, and it makes me want to cry every time I do.

    • Mod parent up (Score:4, Informative)

      by Animats (122034) on Friday March 11 2005, @11:32AM (#11911034) Homepage
      That's impressive technology. And it needs to be better known. Reverse-stepping has been available for gdb under Linux since at least 1999, and nobody knows it. So please, mod the parent up.

      This has real potential. Beta versions of programs should run with this installed, so the core dump can be stepped backwards to the trouble spot. This could make Linux software significantly more reliable.

    • Wow, what to say?!

      First, it was kind of silly to name the program the same as my user name, but I never found a better name for it than "my trace-and-replay debugger".

      My original plan was to write this for Solaris and sell it, hence the insistence on tracing and replaying without modifying the target program or the operating system, and that's why the replay controller messes with gdb's mind, so that it can work with a stock gdb rather than needing gdb extensions.

      I developed a Linux version first because
  • We've seen a few april fools claiming to be able to run code backwards. This is impossible, at the lowest level. For example, take the logical OR: C = A + B (excuse the layout, the top line is the value of B, the first column the value of A)

    A\B | 0 | 1 |
    0 | 0 | 1 |
    1 | 1 | 1 |

    We know the result, C. How do we know if A, B, or both was 1? We lost information (2 bits of info became 1), and cannot get it back. So at first I dismissed any ridiculous claims of reverse execution. But we aren't the 1st of April...

  • Reversible Computing != Reversible Execution (Score:5, Informative)

    by Anonymous Coward on Friday March 11 2005, @09:01AM (#11909494)
    Reversible computing is a way of computing without (permenantly) consuming energy. Look it up if you're not familiar, because it's pretty interesting.

    Anyway, the headline is misleading.

  • OCaml anyone? (Score:4, Interesting)

    by fab13n (680873) on Friday March 11 2005, @09:02AM (#11909498)
    OCaml [inria.fr] as been offering timestamps and backward debugging for years, in addition of a great programming language (backward debugger's implementation is based on Unix's forking and copy-on-write, so running it on windows requires cygwin). Simply compile your stuff to byte-code rather than with the native optimizing compiler, run the debugger and use backstep/backward just as you used to do with step/forward. Breakpoints block execution in both directions.

    And what about GUI and other side effects? Debugging a program in which such side-effects are deeply interleaved with algorithmics can be tricky indeed, although smart timestamping from the debugger will reduce glitches. But if you don't know better than randomly mixing algo and front-end in the first place, then you'd better fix the programmer than the program...

  • Any relation to ReVirt? (Score:5, Interesting)

    by eddy (18759) on Friday March 11 2005, @09:07AM (#11909532) Homepage Journal

    ReVirt [umich.edu]:

    The ability to replay the execution of a virtual machine is useful in many ways besides intrusion analysis. For example, it enables one to replay and debug any portion of a prior execution. We have built an extension to gdb that uses virtual-machine replay to provide the illusion of time travel. In particular, we provide the ability to do reverse debugging, though commands such as reverse watchpoint and reverse breakpoint. graph. See our paper in USENIX 2005 for details.

  • Elephants never forget (Score:5, Interesting)

    by same_old_story (833424) on Friday March 11 2005, @09:09AM (#11909550)
    John McCarthy has been talking about giving programming langues the notion of time for quite some time (no pun intended).

    In this paper, he proposes the Elephant language [stanford.edu] that can refer to the past in computer programs.

    Pretty cool stuff!

  • I can back up easily enough with a call stack. I can see some situations where this approach might be better than a simple stack, but those instances would seem to be few and far between.

  • Is This Really New? (Score:3, Interesting)

    by Ginnungagap42 (817075) on Friday March 11 2005, @09:14AM (#11909586)
    I remember that several of the older compilers like Borland's Turbo Pascal, Turbo C and Microsoft C and MASM could run reverse execution through the debugger. They also had the "animate" feature that let you step through the code automatically, but slowly so you could watch each line of code as it was executed. I remember setting my PC up with two video cards: a monochrome Hercules card and an EGA card. A lot of the compilers from those days supported mutiple graphics card output - the code would appear on the monochrome monitor and the running executable would appear on the color monitor.

    Being able to trace backwards ware extraordinarily useful, and it's one thing I miss in modern compilers. I always assumed that this capability was taken out with the advent of event-driven (GUI) programming. That's when a lot of this kind of functionality seemed to disappear.
  • Interesting, but will it work on a dead badger [strangehorizons.com] running GNU/Linux? Cause thats where do all my development work.

  • Come from? (Score:4, Funny)

    by AJWM (19027) on Friday March 11 2005, @10:59AM (#11910663) Homepage
    Reverse execution? Are we finally going to see an implementation of the COME FROM [fortran.com] statement?

    (See also the entry in the jargon file [catb.org].)
    • If computing is reversable then the system is not losing information. All that entropy has to go somewhere. while built up heat can radiate away on the fan, the entropy must keep building up. At some point its going to explode!

      more seriously, that would mean that there is no crypto on these machines since all encoding would be reversible.

    • The term "reversible computing" has also been used for a type of circuit that does not consume energy, other than entropy, for computation.

      I think you got it just the wrong way.

      Traditional computers generate entropy because of the information destroyed. Entropy created is necessarily associated with heat. With reversible computing there is no entropy increase, which in theory means less heat produced and less energy consumption.

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.