Implementing reverse execution

Robert O'Callahan robert at ocallahan.org
Sun Feb 1 21:38:12 PST 2015


Now that I've unraveled the multiple-signal mess, I plan to start working
on reverse execution soon. Here are my thoughts on this:

I want to make reverse-exec an abstraction separate from the gdb code,
since it should be reusable for other needs. But I don't want to add it to
ReplaySession since a ReplaySession currently corresponds to a single set
of Tasks at a single point in time and that isn't sufficient for
reverse-exec, and I don't want to complicate ReplaySession. So, I propose
adding a new abstraction, a Timeline:

* A Timeline represents the entire history of an execution.
* You initialize a Timeline with a ReplaySession representing the start of
the execution.
* A Timeline has a "current state", a ReplaySession representing "the state
at the current point in time". Timeline API calls may change the current
state to a different ReplaySession object.
* To support navigation through time, a Timeline exposes a set of Marks
each representing a point in time.
* Marks have a total order (i.e. a less-than operator with the obvious
meaning)
* You can get "the current Mark" for the current state.
* You can seek the Timeline's current state to a given Mark.
* Checkpoint management: you can explicitly request that the Timeline
maintain a checkpoint for the current Mark, or release a checkpoint for any
Mark, or get the ReplaySession for the checkpoint at a given Mark. This
will avoid Timeline users maintaining their own checkpoints for execution
states that the Timeline is maintaining its own checkpoints for.
* You add/remove code/data breakpoints through an API on the Timeline.
* You can continue or singlestep the current state forwards or backwards
until a breakpoint, or a Mark, or the end of the timeline is reached.

Timeline would be built on ReplaySession. GdbServer would be modified to
use Timeline instead of a single ReplaySession.

Implementation:
* A Mark identifies a point in the execution in our usual way: tick-count +
general-purpose registers.
* Establishing the total order on Marks is a bit tricky since two different
Marks may have the same tick-count. We can do it though, if necessary by
cloning ReplaySession state at mark M1 and running forwards to see if we
hit mark M2 before the tick-count increments. In practice I think we can
avoid that most of the time. We'll share Mark objects and keep them in an
ordered list in the Timeline.
* The rest is reasonably straightforward. Forward execution is trivial
based on what ReplaySession already provides. Reverse execution backs up to
the previous checkpoint, runs forward counting how many breakpoints are
hit, and then backs up and runs forward again, stopping at breakpoint N-1.
* The Timeline can maintain an internal database of which breakpoints get
hit (or not) over various time intervals. This would speed up the above
process a lot. This data could even be persisted alongside the trace data.
* Managing the checkpoint budget is interesting. It would be nice to
encapsulate that in the Timeline, but clients could provide very helpful
heuristics (e.g. checkpoint on new page load, or start of new mochitest).

Rob
-- 
oIo otoeololo oyooouo otohoaoto oaonoyooonoeo owohooo oioso oaonogoroyo
owoiotoho oao oboroootohoeoro oooro osoiosotoeoro owoiololo oboeo
osouobojoeocoto otooo ojouodogomoeonoto.o oAogoaoiono,o oaonoyooonoeo
owohooo
osoaoyoso otooo oao oboroootohoeoro oooro osoiosotoeoro,o o‘oRoaocoao,o’o
oioso
oaonosowoeoroaoboloeo otooo otohoeo ocooouoroto.o oAonodo oaonoyooonoeo
owohooo
osoaoyoso,o o‘oYooouo ofooooolo!o’o owoiololo oboeo oiono odoaonogoeoro
ooofo
otohoeo ofoioroeo ooofo ohoeololo.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rr-dev/attachments/20150202/695fcee3/attachment.html>


More information about the rr-dev mailing list