rr and Time-Traveling Debuggers

In this video I tell Huiqi about rr: a report/replay debugger for C and C++. We talk about how record/replay debuggers work using Redux as a starting point.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : uh okay so now i want to talk about the
00:02 : thing
00:03 : that i really want to talk about which
00:05 : is um
00:06 : so i so i've been doing this work kind
00:09 : of
00:10 : like this concept of the time traveling
00:13 : debugger
00:14 : uh for for more than a year now
00:18 : um okay and i i mostly i've just been
00:22 : freestyling i i would say it was
00:25 : inspired by a bunch of technologies
00:27 : like redux is a big one i think and but
00:30 : also python tutor
00:31 : right um and
00:36 : and other than those those inspirations
00:40 : that i had
00:41 : mostly going off on my own without
00:44 : reviewing any of the literature of
00:46 : what other people have done and only
00:48 : recently
00:49 : have i tried to find
00:54 : other people other prior art other
00:58 : people doing a similar thing
00:59 : and um and i i uh
01:03 : there's something i told you about this
01:05 : this uh
01:07 : this replay io which is a
01:11 : is a solution for uh javascript
01:15 : uh this is made by i had conversations
01:18 : with the ceo
01:20 : of this company uh he he's a previously
01:23 : a employee at mozilla
01:27 : and they actually they actually started
01:30 : building the technology for this at
01:32 : mozilla and then it got it got spun
01:35 : off into this company um
01:40 : and then there's other there's something
01:42 : called oz
01:43 : code as well which does a similar thing
01:47 : to what i'm doing
01:49 : for that net for like c-sharp um
01:54 : more recently i discovered something
01:56 : called uh
01:57 : rr rrproject.org
02:01 : so rr is a basically a
02:05 : time traveling debugger for c and c plus
02:08 : plus
02:09 : um it only works for linux currently
02:13 : um and and what's
02:17 : really interesting is the way that it
02:19 : works and
02:20 : let's also really impressive
02:24 : about it is so they developed this
02:26 : technology at
02:27 : mozilla research um
02:31 : and they specifically had the design
02:34 : goal of
02:35 : making it work for debugging the firefox
02:39 : browser
02:40 : um okay and the firefox browser
02:44 : is an extremely complex piece of
02:46 : software as you can imagine
02:49 : like any any any production level
02:53 : browser right is a really complex piece
02:55 : of software
02:57 : and and they wanted to build something
03:00 : that they
03:00 : could use to debug firefox
03:04 : um okay so that that's very difficult
03:06 : task
03:07 : i i imagine um so far the stuff i've
03:10 : been using to debug
03:11 : are very small programs relatively
03:14 : speaking
03:16 : um and
03:19 : and so in order to make that work they
03:23 : they actually had to do a lot of
03:25 : extremely
03:27 : ingenious ingenious solutions
03:30 : like uh they some of them are really
03:33 : crazy hacks
03:35 : um okay but the
03:38 : but i wanna explain the concept of how
03:41 : it works
03:43 : and there's also like a youtube video
03:46 : where one of the creators
03:50 : talks about it and there's also a paper
03:53 : that they
03:55 : released about this technology
03:58 : and i guess it's this is not
04:01 : the when i dug more into the literature
04:05 : on this
04:05 : i realized that this is what they did
04:09 : here
04:09 : was there's there's already a lot of
04:13 : prior work before this
04:17 : like they they they were using like
04:20 : there's a lot of work um
04:23 : in the research community uh
04:27 : on this and the term they use
04:30 : uh is a deterministic
04:33 : replay okay
04:37 : so if you if you search for
04:39 : deterministic
04:40 : replay you'll be able to find a lot of
04:42 : the research literature
04:44 : on this prior work and i want to talk
04:47 : about what that is
04:49 : we're gonna start with the redux
04:52 : first because it has a lot of
04:55 : similarities
04:56 : to redux actually so in in redux
05:00 : we have this situation where
05:02 : [Music]
05:03 : um well you have your program
05:11 : and the desire of redux is to sort of
05:16 : um encode your program
05:20 : as a reducer as much as possible right
05:25 : because a reducer is a pure function
05:29 : and pure functions are easier to deal
05:31 : with
05:33 : and the reducer
05:36 : i'm gonna try to
05:41 : there's two inputs and one output okay
05:44 : that's what the reducer does um
05:47 : the the the
05:50 : first input is the current state of the
05:52 : program and the second input
05:54 : is some sort of action or event
05:59 : i'll call it a for action and then the
06:02 : output is a new state i'll call it state
06:05 : prime right
06:08 : in sort of math mathematical
06:11 : notation so so this is more or less
06:15 : uh what the redux architecture is
06:18 : and what you end up having is a timeline
06:22 : i've drawn this many times where you
06:25 : have state 1
06:27 : state 1 state 2 state
06:32 : a1 goes in here
06:35 : and that spits out at s2 and then
06:39 : a2 goes in
06:42 : and then you go it goes to the reducer
06:46 : again
06:49 : and spits out the s3 and then you you
06:53 : have
06:53 : you build up the timeline this way and
06:57 : and in fact
06:58 : yeah it's a finite state machine
07:02 : is this a finite is this
07:06 : there only like definite amount of the
07:10 : space that you can generate
07:13 : and then which it depends on
07:16 : what is the what is the event and the
07:19 : current usually finite state machine
07:22 : you draw it like this
07:28 : um but each of these bubbles
07:31 : is one it's like an enum
07:34 : like like if you have states a b
07:37 : c then then the state is
07:41 : represented as a or b
07:44 : or c it's represented as an enum
07:48 : usually that's how usually that's how
07:50 : they do it in finite state machine
07:52 : maybe it doesn't have to be that way
07:55 : maybe you can have
07:56 : like state in terms of a variable value
07:59 : or stuff like that
08:00 : but i don't know if that still counts as
08:02 : a finite state machine
08:04 : in this case our state could be any
08:06 : amount of information
08:09 : okay so the difference is we don't know
08:12 : what the states
08:13 : are it's not it's not three sets of
08:16 : things
08:17 : yeah because the state could be any
08:20 : amount of
08:20 : information like any amount of there
08:23 : could be a
08:25 : like 10k of data right for example
08:28 : or the data structures that have it
08:31 : like very interesting linkage between
08:33 : each other
08:34 : okay um so anyway
08:38 : so so that's sort of the picture and if
08:40 : i were to draw it in a
08:41 : simpler manner it might look like this
08:50 : like so so so these are a's
08:58 : and these are the s's maybe i have start
09:01 : with a
09:02 : zero how about that
09:06 : um and so the observation
09:10 : so one of the sort of mind-blowing
09:13 : uh features of redux is that
09:17 : well you can travel back in time if if
09:20 : you follow this architecture
09:22 : because and there's two ways by which
09:25 : you can do that
09:26 : one way is uh you number one
09:29 : is you store the value of
09:33 : s0 and
09:36 : and all actions
09:40 : all a's and if if you store
09:44 : if you store s0 and all the a's
09:48 : then you can later on start with s0
09:52 : run through all the replay all the a's
09:55 : through the
09:56 : exact same reducer that you have and
09:58 : then you can generate
10:00 : uh all pass states
10:03 : that way you can regenerate s1 s2 and so
10:06 : forth
10:06 : the second way you can time travel is
10:09 : you just
10:10 : store all of the s's
10:13 : okay so is it like kind of like how git
10:17 : works like the first one a get get
10:20 : works in the second way actually
10:23 : yeah get get stores all of the states
10:27 : um and uh but but the predecessor of
10:32 : git um is svn
10:36 : and svn does it the first way
10:40 : okay okay
10:43 : um so
10:46 : so it is first of all it's interesting
10:48 : that there are
10:49 : two ways to implement time travel and
10:52 : and also interesting that
10:54 : you know uh it's not clear
10:57 : that one way it's clearly better than
10:59 : the other
11:01 : given that we have different tools that
11:03 : use a different strategy out of those
11:05 : two
11:07 : and in fact in fact i have implemented
11:11 : both of these
11:12 : so i i so first
11:16 : i implemented the play language
11:20 : the play language was based on number
11:23 : two
11:24 : i i i i had the end
11:28 : all of the state of the program
11:30 : including the stack frame
11:32 : and the heap objects all of that
11:35 : were sort of encoded
11:38 : inside of one gigantic
11:42 : data structure and and then whenever the
11:46 : program changed anything
11:49 : i muta i don't mutate that i
11:52 : create a new version of the entire
11:55 : program state
11:56 : uh so so i use git approach for the play
12:00 : language
12:01 : and then um but but
12:04 : for the python one for i i'm calling my
12:08 : python time debugger i call it pie
12:11 : rewind
12:14 : for pie rewind uh i i'm using
12:18 : approach number one and i'm every action
12:22 : that any action i i'm gonna define
12:26 : as you know any state mutation
12:30 : or or the fact that a particular line in
12:34 : the program
12:35 : has been visited has been reached
12:38 : those are actions um any of those
12:42 : i i save those into the log file
12:45 : and then the initial state well
12:48 : i don't explicitly store the initial
12:52 : state but the initial state is just like
12:54 : the beginning of the program
12:55 : right so then i just run back
12:59 : all of those events to regenerate
13:02 : all the intermediate states of the
13:04 : program and then now i can have a
13:06 : debugger that goes back in time
13:07 : right okay so i have tried
13:12 : both of these approaches myself um
13:15 : one of the biggest worries right i have
13:17 : right now is
13:18 : that uh the performance it
13:22 : can easily be a problem if the program
13:25 : is doing too much
13:26 : right so so that means i'm gonna have a
13:29 : very
13:30 : long list of actions and
13:34 : and you know and the time complexity of
13:37 : my
13:38 : my thing that recreates the past states
13:42 : is gonna you know be determined by how
13:44 : many actions there are
13:47 : um so how does rr
13:51 : do this rr takes this diagram
13:55 : it's the same diagram except that
13:58 : for rr
14:03 : uh this is the of the outer box
14:06 : oh one thing by the way one limit
14:10 : big limitation of redux is that even
14:12 : though they have this
14:13 : very nice vision i would say the the
14:17 : ideal has not totally been
14:19 : achieved because um
14:22 : the the time traveling capability
14:26 : when you're using it to debug stuff sort
14:29 : of it sort of only
14:31 : works for the thing that's
14:34 : enclosed inside of the reducer
14:38 : like but the problem is with redux
14:41 : applications there's actually a lot of
14:43 : code that's not in the reducer
14:45 : and if there's bugs in that code
14:48 : then the time traveling doesn't always
14:51 : help
14:51 : in debugging those problems right the
14:54 : the problem
14:55 : is you haven't housed all of your code
14:58 : inside this sort of sandbox
15:02 : that it's it's able to capture you're
15:05 : only capturing
15:06 : sort of this what the reducer is doing
15:10 : in other words write your code in a
15:13 : specific
15:13 : way to fitting them yeah the reason this
15:17 : came about is you know we really like
15:20 : functional programming right
15:22 : so because and we can write a reducer
15:26 : as a pure function the concept of reduce
15:30 : came out of functional programming so
15:33 : so um basically if functional
15:37 : like immutable functions or pure
15:40 : functions
15:41 : are easier to debug and that's why we
15:43 : would like to have this
15:45 : but the problem is that just you know
15:48 : you cannot write all of your code as
15:51 : immutable functions
15:53 : is it's still not possible so
15:56 : with rr we draw we draw the same diagram
16:01 : except where we have the outer box it
16:04 : was
16:05 : for redux it was the your program
16:08 : the outer box is the operating system
16:13 : and your your inner peace
16:17 : your inner peace is your program okay
16:20 : maybe i shouldn't draw it
16:21 : exactly the same way so uh i'm gonna say
16:25 : like this is your program
16:30 : and then and then we had the
16:33 : actions uh
16:36 : the actions are the system calls
16:44 : and and if
16:48 : if we're using a pure function in redux
16:51 : because a pure function is completely
16:53 : deterministic
16:54 : as in given the same inputs you will
16:56 : always have the same output
16:58 : and that's why we can do this whole
16:59 : thing
17:01 : um we're in rr
17:04 : is the same concept uh but we're saying
17:08 : the program is
17:11 : completely deterministic
17:14 : as the syst the system call is the way
17:18 : by which a program can communicate with
17:21 : the
17:22 : rest of the world it's this is a two-way
17:25 : arrow
17:27 : so the program makes system calls
17:30 : and then it get gets return value from
17:34 : system call a system call
17:35 : is like you know the api of the
17:38 : operating system right
17:41 : so in a sense is maybe a better way to
17:45 : draw this would be
17:46 : the the program interacts with the
17:48 : operating system
17:50 : through the system calls so if
17:54 : if the program code is deterministic
18:00 : then we can guarantee that
18:04 : if the same program ran and every time
18:07 : it made a system call
18:09 : it received the exact same result
18:12 : then it will do the exact same thing it
18:14 : did the first time
18:19 : and if you think about it this exact
18:21 : same picture that we have
18:23 : even though even though we have this
18:25 : state arrow
18:26 : in here and now we don't have the state
18:28 : arrow whenever
18:29 : state mutates state mutation
18:33 : happens inside here
18:39 : but if the if the way the program works
18:42 : is completely deterministic then given
18:45 : the same
18:46 : input the exact same state mutation
18:49 : should occur the second time
18:52 : so basically the system calls the
18:54 : actions
19:08 : yeah you you could still kind of think
19:11 : of it
19:12 : like this function here like you can
19:14 : still think of it like this reducer
19:16 : thing
19:17 : except that we we don't generate a new
19:19 : version of the state we just go ahead
19:21 : and mutate it
19:22 : right inside but but if we can
19:25 : if we can think about it as
19:29 : you know if we can model it as the
19:32 : reducer
19:36 : like
19:40 : whatever state it had you're just gonna
19:43 : write it right back into it
19:46 : uh plus whatever system call
19:49 : if you can model it like this whatever
19:51 : your current state is
19:53 : you run it through this function and
19:54 : then the output goes
19:56 : right back into the current state and
19:58 : then it's just same as
20:00 : mutating that state if we draw the
20:03 : picture this way
20:04 : and this piece is deterministic or a
20:08 : pure function
20:10 : this this is a pure function
20:16 : or or this is deterministic
20:20 : meaning if given the exact same
20:23 : input it will always give the exact same
20:25 : output
20:28 : then this scheme this scheme will work
20:32 : so so what rr does is it runs the
20:36 : program
20:37 : while recording all of the results
20:40 : of the system calls
20:43 : okay and then when it replace it it
20:48 : secretly it intercepts all the places
20:51 : where your program
20:52 : is making system calls and replaces
20:56 : the results with the previously recorded
20:58 : versions
20:59 : of the values
21:03 : uh okay question yes if
21:07 : the biggest difference that i saw
21:11 : between this schema and the one that's
21:13 : in the pi
21:15 : and that that's a long time and because
21:17 : you have that so that you can jump into
21:19 : the london line of the of the foot
21:24 : just remember that so how do you do it
21:27 : in the arm or how does this
21:28 : okay i want
21:34 : yeah yeah good great question yeah
21:36 : you're breaking up a little bit but i
21:38 : made out what you were saying basically
21:39 : you're saying like
21:41 : with my pi rewind implementation
21:44 : i have the full log and and i have read
21:47 : it all back to generate every
21:49 : intermediate state with with their thing
21:52 : they don't actually have all the
21:55 : intermediate states
21:57 : they the things they record
22:01 : are all the system calls right
22:04 : that's what they're recording they're
22:05 : recording all the system calls
22:08 : and they're not recording
22:11 : everything that happened inside your
22:14 : your program inside your building block
22:16 : here
22:17 : they're not re they're whereas my pi
22:19 : rewind
22:20 : i actually do record every single thing
22:23 : that happened like this
22:24 : list got updated i just added an item to
22:28 : this list
22:29 : i recorded i mutated this dictionary i
22:32 : recorded i
22:33 : i changed the value of this variable i
22:36 : record that in my pi rewind they don't
22:38 : do that but
22:39 : everything that happens inside this
22:41 : black box
22:42 : they don't touch they just touch things
22:45 : when the black box is communicating to
22:47 : the
22:47 : operating system that's what they log
22:51 : um so so the way they would
22:54 : have to implement traveling back in time
22:59 : did did rr choose scheme number one
23:02 : or scheme number two number one
23:06 : yeah right so rr chose scheme number one
23:08 : and the way scheme number one
23:10 : works is you start at state zero
23:14 : and then you have to replay all of the
23:17 : actions
23:18 : leading up to that point right so what
23:21 : that means
23:22 : if if you want to rewind back to state
23:25 : number two
23:26 : you're gonna have to start at state
23:28 : number zero
23:30 : replay replay the first two action in
23:33 : their case
23:34 : the actions are the system calls so
23:36 : they're gonna replay
23:37 : the first two system calls starting at
23:40 : uh
23:41 : starting at state number zero now they
23:43 : could potentially
23:45 : choose to optimize it by like if
23:49 : the user has to jump around a lot in
23:52 : time
23:53 : they could potentially choose to
23:55 : optimize it after
23:57 : re-running these to get state number two
24:00 : they could store state number two
24:02 : in the cache right okay
24:06 : watch it they could they could do
24:08 : something like that so they don't have
24:09 : to go back to the beginning all the time
24:14 : gotcha yeah that makes sense
24:18 : uh yeah so that this is
24:21 : this is really interesting to me uh i i
24:24 : and i
24:25 : i found that like the moment i searched
24:28 : for deterministic
24:29 : replay which which is the term for this
24:33 : kind of technology
24:34 : i found a lot of research articles
24:37 : research papers
24:38 : on this topic so i'm kind of wanting to
24:42 : do a deep dive on this there's even
24:45 : crazier
24:46 : stuff where um
24:49 : well i won't i won't keep you too long
24:51 : but i i just want to share
24:53 : that stuff with you oh talk to you later
24:56 : yeah thanks for sharing that's
24:57 : very interesting yeah you're welcome
24:59 : talk to you later bye-bye
25:01 : hey there this is toby coming to you
25:03 : from the future
25:04 : as they say i realized that in our
25:07 : conversation
25:08 : we missed one thing um
25:12 : when i was trying to answer huichi's
25:14 : question
25:15 : about um with
25:18 : rr how do you travel back in time
25:22 : uh i did not give the complete answer so
25:25 : i'll try to
25:26 : complete it now so we did mention that
25:30 : in order to jump back in time to some
25:33 : state uh in history you're gonna need to
25:37 : start at
25:38 : s0 and then replay the actions which
25:42 : in the case of are those are the system
25:44 : calls
25:46 : the question though is in a debugger
25:50 : application you actually need to be able
25:53 : to
25:55 : step to a particular line of code
25:58 : however that is not
26:02 : possible with simply representing a
26:05 : state because remember
26:07 : in rr these are system calls
26:11 : so if we replay the system calls
26:14 : we if we replay a1 and a2
26:18 : both of which are system goals and that
26:20 : gets as a
26:21 : new state s2 that only
26:24 : gives us the state of the program
26:28 : immediately after having
26:32 : completed a system goal what if what we
26:35 : want
26:36 : is to step into a point in time in the
26:39 : program's execution somewhere
26:43 : in between s1 and s2
26:46 : right like i want s 1.39
26:53 : how do you do that with rr and the
26:56 : answer to that question
26:58 : is we use the normal debugger
27:02 : that you would use and in their case
27:04 : they use
27:05 : gdb
27:08 : um okay so so if we
27:13 : let me clear the screen so
27:17 : so if we want to pause
27:22 : at a state that's between two states
27:25 : right what we'll need to do is use gdb
27:32 : to set a breakpoint
27:40 : at that uh at that line
27:43 : location in that code and
27:47 : and gdp has facilities of doing that
27:50 : kind of stuff
27:51 : i'm the actual way to do it
27:55 : i believe you can either use a hardware
27:59 : breakpoint if your
28:01 : cpu has support for that or
28:04 : gdb might actually modify your actual
28:07 : code in order to insert a breakpoint in
28:09 : any case
28:10 : we're going to ask gdb to basically
28:12 : insert a breakpoint
28:15 : into a line location somewhere in
28:18 : between
28:18 : state one and state two and then
28:22 : so then after that happens
28:26 : what we're gonna do is basically replay
28:29 : these
28:30 : system calls
28:35 : and after we replay system call 2
28:40 : uh it's going to cause this chain of
28:42 : executions we're going to hit
28:44 : this breakpoint and that's going to
28:45 : cause the program to pause
28:47 : and that's how we go back in time to
28:51 : any line that we choose
28:54 : so yeah
28:59 : you