"I saw demos some years ago and assumed one used it similarly to gdb but with rewind."
You can do reverse debugging in gdb.
Here's how:
Run: gdb --args /usr/bin/foo --bar baz
Type "start", then "record", then "continue"
Now can try a number of reverse-debugging commands, for example:
* reverse-stepi
* reverse-next
* etc
gdb's built-in recording doesn't scale. You can't record across system calls, thread context switches, etc, and it's about a 1000x slowdown during record and replay. (rr is more like 2x.) It is, unfortunately, an attractive nuisance, because a lot of people have tried it out and concluded that record-and-replay debugging is useless.
You can do reverse debugging in gdb.
Here's how: