Monday, 13 July 2015

Two Reverse-Execution Optimizations

rr 4.0 will be the first rr release where reverse execution is reliable. I want to release it soon, but some users still find situations where reverse executions that seems to hang. I've implemented a mitigation by allowing ctrl-C to interrupt reverse execution (though I think there are still bugs where sometimes it fails to interrupt cleanly), but there are also underlying issues that can cause reverse execution to be very slow, and I want to fix as many of those as I can. I've recently fixed the two major fixable issues that I currently know of, and they're interesting.

For the following discussion, keep in mind that we implement reverse execution by restoring the program state to a previous checkpoint, then executing forwards and noting which breakpoints/watchpoints get hit. Once we reach our original starting point, we know which breakpoint/watchpoint firing is the "next" one in the reverse direction; we restore the program state to a previous checkpoint again, and execute forward again until we reach that target breakpoint/watchpoint.

The first issue involves reverse execution over conditional breakpoints/watchpoints that are hit frequently but whose condition almost always returns false. Following the above procedure, rr would reverse-continue to the most recent triggering of the breakpoint (or watchpoint), then stop and signal gdb; gdb would read program state via rr to evaluate the breakpoint, and then signal rr to continue with reverse execution. Thus, every time the breakpoint is hit, rr must perform at least two clonings of checkpoint state plus some amount of forward execution. That makes reverse execution unbearably slow if the breakpoint is hit hundreds of times.

Fortunately, gdb has an obscure feature that lets it offload evaluation of simple conditions to the remote target (in this case, rr) by expressing them as bytecode. So we add to rr a little interpreter for gdb's bytecode; then rr can implement reverse execution by executing forwards over some time interval, and every time a breakpoint is hit, evaluating its condition and ignoring the hit if the condition evaluates to false. If all goes well we only have to reconstruct program state for debugger stops where the user actually wanted to stop.

Unfortunately not all goes well. Some breakpoint expressions, e.g. those involving function calls, are too complex for gdb to express with its bytecode; in such cases, pathological slowdown of reverse execution is inevitable. So try to avoid using complex breakpoint conditions on breakpoints that are frequently hit during reverse execution. Moreover it turns out gdb has a bad bug in code generation, which requires an even worse workaround. I submitted a gdb fix which has landed upstream so hopefully one day we can get rid of the workaround.

Another case which is difficult to deal with is an unconditional breakpoint being hit very many times during the interval we're reverse-executing over. In this case just executing forward and stopping thousands times to find the last hit can be prohibitively expensive. Ideally we could turn off breakpoints, run forward until we're close to where reverse execution started, then enable breakpoints and continue forward again, hopefully only hitting a few occurrences of the breakpoint before we reach the last one. We can approximate this by detecting that we're hitting "too many" breakpoints while executing forward, and responding by cutting the remaining execution interval roughly in half, advancing to the start of the second half with breakpoints disabled, and resuming normal forward execution with breakpoints enabled --- possibly having to repeat the subdivision process if we're still in dense region of breakpoint hits.

I just landed these fixes on master. I'm very interested in hearing about any remaining cases where reverse execution takes a pathologically long time.

Sunday, 12 July 2015

Midwinter Road Trip

It being the school holidays, I took a few days off for a short road trip around the central North Island with my and my brother's family --- two nights in Waitomo and two nights in Taupo. It is the middle of winter and we had a bit of a cold snap --- frosts every night --- but the weather was clear, fine and sunny. It was a thoroughly excellent trip all around: caves, rivers, countryside, mountains, board games, geothermal areas, tasty food, love and laughter. The South Island is more spectacular, but the central North Island remains dearest to my heart as a God-given blessing to all who live in and around it.

One highlight for me was "black-water rafting" at Waitomo: wetsuit, inner tube, helmet and head-lamp in an underground river. It's thrilling and a little crazy but not as testing as I'd been led to believe; highly recommended. Beyond the thrills, I will long remember drifting along underground in darkness and silence under the glow-worm-studded roof.

Another highlight was a hastily-planned trip up Mt Pureora between Waitomo and Taupo on Friday. We drove up Link Rd from highway 32 on the east side of the mountain --- it's gravel, but in very good condition --- and reached the trailhead a bit late at 3pm, but had plenty of gear and moved fast. We reached the summit by 4pm (beating the signposted time of 1.5 hours) and after 15 minutes at the top returned to the car at 5pm. There had been snow the previous night (closing the roads around Ruapehu/Tongariro --- otherwise we'd probably have been doing a walk there) and the walk was delightful, starting as a regular North Island bush walk and ascending into a winter wonderland with a light covering of snow and ice, opening at the summit into magnificent views of the central North Island --- Taupo, the Waikato, and the snow-capped volcanic plateau. There are many other tracks in the area, and I'd love to visit again.

Tuesday, 7 July 2015

rr Talk Video From TCE 2015

The good people at the Technion have uploaded video of the TCE 2015 talks, in particular video of my rr talk. My slides are also available. This is a fairly high-level talk describing the motivation and design of rr, delving into a few interesting details and concluding with a discussion of some of the exciting possibilities that could be enabled by rr and similar technology.