Support reverse-execution `b` commands

[daniel5151]

Support reverse-execution `b` commands

[DrChat]

Sure, I can probably target it against dev/0.5 :)

[DrChat]

@daniel5151 Can you give #48 a preliminary review, just to make sure I'm on the right path?

[daniel5151]

A brief skim through the GDB docs implies that this might be as simple as adding support for the bc and bs packets, and sending back the appropriate qSupported features. Unfortunately, while simple to implement at the protocol level, it might be surprisingly tricky to "nicely" implement this functionality in gdbstub:

1. How does bs know which thread to reverse step?
   • bc and bs seem to mirror the deprecated c and s packets, which do not package "execution context" (i.e: thread id) as part of the packets themselves. c and s relied on a separate H packet to communicate that execution context information.
   • From my cursory reading of the GDB docs, it doesn't seem to explicitly document how bc and bs know which thread to operate on (admittedly, I don't think it really matters for bc, since it'll just run the whole system in reverse). I'll have to see what the reference implementation is doing...
2. How to expose reverse execution functionality at the API level?
   • Note: This should actually be fairly straightforward in gdbstub 0.5 (assuming the current WIP resume API stays as-is), and would likely mirror how the optional range-steping API looks like. The difficulty would be in exposing this functionality in a non-breaking manner as part of 0.4.x.

Oh, in addition, it may be required to implement the replaylog Stop Reply Packet as well, though this shouldn't be too tricky.

In any case, this is certainly a feature worth supporting, and is something I'll keep an eye on when I find more time to hack away at gdbstub. In the meantime, feel free to dig a bit deeper into the question/challenges I outlined above, and if you'd like, consider whipping up a PR that implements the feature (preferably targeting the dev/0.5 branch).

[DrChat]

Perfect - thanks for the technical dive-in! I'll be spending some time looking at this as part of my current project, since reverse-execution support is desirable.

[DrChat]

One question is whether or not ResumeAction can be extended.
It looks like for your range-stepping implementation, you did not extend the enum, so multi-thread targets would have to handle it themselves.

It'd be more ideal to extend the enum instead, though I'm not familiar enough with the language to understand whether or not it's feasible or convenient to do so.

[daniel5151]

It'd be more ideal to extend the enum instead

The issue with extending the enum is that it forces targets that don't care about reverse-execution (or range-stepping for that matter) to handle that case, even though the GDB client will never send that variant their way. In the best case, this requires the user to extend their error handling code with a new Error::UnsupportedResumeAction variant (or similar), but in the worst case, will result in users inserting a wholly unnecessary panic! or unimplemented! call into their code.

Plus, having it as a separate, optional IDET is required to enabled effective dead-code-elimination, as we wouldn't want to unnecessarily bloat targets that don't support reverse-execution.

[DrChat]

Indeed - I'm wondering if there's a good way to extend it only as part of extensions... For example, I briefly considered doing:

pub enum ReverseResumeAction {
  Base(ResumeAction),
  ReverseStep,
  ReverseContinue,
}

This would get passed to the appropriate reverse-stepping IDET.
Problem is that this raises questions about what happens when you have multiple extensions to ResumeAction - you can't declare an enum that has multiple extensions.

[daniel5151]

Yeah... I find that the trickiest part of working on gdbstub is wrangling the absolutely insane (mostly optional!) surface area of the GDB Remote Serial Protocol into a single robust and ergonomic API. The fact that almost every feature can be mixed with almost any other feature makes things really complicated, and often times, hacking on gdbstub starts to feels more akin to assembling a jigsaw puzzle than it does to writing API bindings 😅

In any case, as you explore the design space further, please keep the following two principles in mind:

• The resulting API should be completely optional
  • If someone doesn't care about reverse-execution, they shouldn't be required to implement any boilerplate / stub code related to it.
• The resulting implementation should have zero* overhead when the feature isn't being used
  • i.e: leverage IDETs + dead code elimination as much as possible
  • Make liberal use of the ./example_no_std/check_size.sh script during development to make sure the base gdbstub configuration remains as small as possible.
  • *zero overhead may not be possible, so at the very least "negligible" overhead

Also, note that this extension is particularly tricky to implement, since it ties into the whole vCont / target resume machinery, which I'd wager is one of the most complicated and finicky bits of gdbstub's internal implementation.

[daniel5151]

As I suspected, bc and bs rely on the H packet...

https://github.com/bminor/binutils-gdb/blob/master/gdb/remote.c#L6295-L6308

[DrChat]

😛 Yeah I can see the jigsaw puzzle bits now, hah.
I was trying to add in reverse-stepping support similar to how you've done range-stepping - except that bs/bc are done in the same style as the deprecated continue commands instead of vCont.
Okay, so I look at how you did the deprecated commands - they're forward-compatible (to an extent) with the new vCont style and you simply forward it as a vCont. Unfortunately I can't do that because vCont does not support reverse-execution. Ahhh man, GDB...

Have you been monitoring their mailing list at all? Do they have plans to fix this injustice against the world? :V

[daniel5151]

Unfortunately I can't do that because vCont does not support reverse-execution.

I take it you're talking about the fact that VContKind doesn't include reverse stepping variants? Well... given that said enum is an internal construct anyways, it's probably fine to shoehorn reverse-execution variants in there (even through they don't actually correspond to any vCont packets). That's probably the most logical place for them anyways...

Have you been monitoring their mailing list at all? Do they have plans to fix this injustice against the world? :V

I can't say I do, but I'd be very surprised if it was on their roadmap 😅

The GDB RSP isn't a particularly popular protocol, and there really aren't may "fully featured" client / server implementations (i.e: implementations that do more than just implementing read/write registers/memory + basic breakpoints). I'd wager to bet that modernizing this obscure, rarely implemented bit of the RSP would take more effort than just biting the bullet, and dealing with the inconsistency.

Plus, implementations are required to support the H packet regardless, (it is used to specify execution context for the m and M packets for reading/writing memory), so what's the harm in using it to specify bs and bc's execution context as well 😝

[daniel5151]

sigh I grep'd through the old mailing list logs, and stumbled across the original conversation regarding adding reverse-execution to the RSP:

https://sourceware.org/pipermail/gdb/2005-May/022502.html

Assuming I've followed the thread correctly, it seems the authors wrote the entire patch-set without realizing that vCont was "a thing", and then instead of keeping it consistent, they just merged it in as-is. Nice.

[mchesser]

I implemented a very minimal version of this a while back for my emulator (i.e. here: 0.4.5...mchesser:master). Reverse stepping mostly worked (though I needed to include ReverseContinue, in qSupported, even if I never send a bc packet), I never bothered with reverse continue though.

As an aside backwards execution of multi-process/threaded programs is complex. rr emulates a single thread machine, and records the thread execution order. I'd expect that execution backwards may result in the active thread switching based on the recorded order.

[daniel5151]

Thanks for the input @mchesser!

As far as I can tell, the only thing your "very minimal" implementation is missing is a way to pass through execution context (i.e: which thread to "backwards step/continue") as specified by the most recently sent H packet. Aside from that, the code you've got there is pretty-much what I would have done myself (though I would have made reverse-execution as sub-IDET of {Single,Multi}ThreadedOps instead of a top-level IDET).

And you're absolutely right - implementing reverse execution for a target can be incredibly complex. Thankfully, it seems that at the GDB RSP level, none of that complexity is particularly important 😄. The GDB client simply asks the target to "go backwards", and then gladly present whatever system state the target returns.

[DrChat]

Really appreciate your work @mchesser!
Would you mind if I pulled that into a PR and made the touch-ups @daniel5151 suggested?

And yeah, I'm glad the complexity does not exist at a protocol level.
I'm actually not really sure how GDB targets implement reverse-continue - it's technically infeasible to actually run backwards.

[mchesser]

@DrChat Go for it, I don't have the time to do it myself so it'd be great if you can polish it up and I can stop using my fork.

My understanding is that almost all "reverse" execution engines are really just involve restoring a past snapshot, then replaying execution to a earlier point in time. For my emulator, when I have reverse execution enabled, I just create a snapshot of the emulator state every 10000 instructions or so, and when step back, I find the nearest snapshot and execute from there. This is plenty fast enough for my use cases, but I imagine there are some smarter techniques that could be implemented.

[daniel5151]

So, just to double check, are you going to be targeting the PR against master (for release as part of 0.4.x), or against dev/0.5?

While I don't think I can commit to a firm release date for 0.5 just yet, the branch has accumulated enough features, bugfixes, and genuine improvements such that I'm inclined to cut a release sometime relatively soon (i.e: within the next few weeks). As such, I'd prefer that you targeted dev/0.5 (thereby saving me the effort of porting it forwards), but if you're hoping to get this upstreamed ASAP, then I would accept a PR targeting master.

[daniel5151]

This feature is now implemented on the dev/0.5 branch.
This issue will be closed once 0.5 is published.