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.

Tuesday, 23 June 2015

Whistler Hike

I'm at the Mozilla all-hands week in Whistler. Today (Monday) was a travel day, but many of us arrived yesterday, so today I had most of the day free and chose to go on a long time organized by Sebastian --- because I like hiking, but also lots of exercise outside should help me adjust to the time zone. We took a fairly new trail, the Skywalk South trail: starting in the Alpine Meadows settlement at the Rick's Roost trailhead at the end of Alpine Way, walking up to connect with the Flank trail, turning up 19 Mile Creek to wind up through forest to Iceberg lake above the treeline, then south up and over a ridge on the Skywalk South route, connecting with the Rainbow Ridge Loop route, then down through Switchback 27 to finally reach Alta Lake Rd. This took us a bit over 8 hours including stops. We generally hiked quite fast, but some of the terrain was tough, especially the climb up to and over the ridge heading south from Iceberg Lake, which was more of a rock-climb than a hike in places! We had to get through snow in several places. We had a group of eight, four of us who did the long version and four who did a slightly shorter version by returning from Iceberg Lake the way we came. Though I'm tired, I'm really glad we did this hike the way we did it; the weather was perfect, the scenery was stunning, and we had a good workout. I even went for a dip in Iceberg Lake, which was a little bit crazy and well worth it!

Saturday, 20 June 2015

Bug In Newer Linux Kernels Affecting rr

As of kernel 4.0.4 (and probably earlier), writing to /proc/.../mem at a page which is mapped PROT_NONE causes a kernel BUG at mm/memory.c, which kills the writing process. This breaks rr, although I have a workaround which I'm about to land; the workaround temporarily makes the PROT_NONE regions we're writing to PROT_WRITE.

Trevor reported this in the kernel bugzilla already, though I was able to come up with a nice small test program.

Wednesday, 17 June 2015

Israel, Part 3

Friday June 5 was a relatively quiet day for me in Jerusalem. I slept in, then went for a walk to the nearby shops of Nachlaot to get some food and a replacement mini-suitcase --- my old little suitcase had fallen apart. It was fun to sit and eat pastries and watch the passers-by and wonder what their stories were. I made it back to my hotel before noon to drop off my gear and headed to the Israel Museum to check out their archaeological area for a couple of hours. It was as fascinating as I'd hoped. An unexpected bonus was the huge scale model of pre-Great-Revolt Jerusalem, giving me a really good feel for the scale and magnificence of the place in those times. I spent the rest of the day relaxing in the hotel lobby and later at Nimrod's friend's apartment, working on my laptop and generally taking it easy until we had another excellent dinner out. This was in preparation for a short sleep and a very early start --- 2:30am --- for our trip to climb the ancient mountain-fortress of Masada before dawn.

We left Jerusalem at 3am and reached the park entrance around 4:30am while it was still almost completely dark. Masada is a steep-sided flat-topped mountain about 350m high with our "Snake Path" winding up the eastern side. It was thrilling to climb that rocky path in that utterly barren landscape, in the dim half-light before dawn, following in the footsteps of countless ancients. We got to the top well before dawn and got some great photos of the sunrise over the Jordanian mountains, across the Dead Sea. Over the next four hours we thoroughly explored the extensive palaces, storehouses, cisterns and other ruins, most of which date back 2000 years to Herod the Great. Over those few hours the cool grey shadows gave way to blazing light and heat, and the Judean mountains emerged in their desolate glory. Masada is a breathtaking place, a perfect combination for my interests in hiking and history. The landscape and the ruins are compelling enough, but its greatest feature is the story of the Sicarii, the band of Jewish rebels who held Masada in 73 AD against the Romans, until the fortress finally fell and (as Josephus tells it) the defenders committed communal suicide just before the Romans entered. The remains of the besieging Roman camps are still clearly visible from above.

My last adventure in Israel was a stop at Kalia Beach on the Dead Sea on the way back to Jerusalem. It was a hot day --- 36C --- and a swim was most welcome, though bathing in the Dead Sea can hardly be called "swimming"! You're encouraged to avoid even the slightest amount of water getting on your face, which makes sense, because it's so saturated with salt it feels oily and you can pick up precipitated salt crystals from the bottom. But it's a lot of fun to lie on.

On the way back to Jerusalem I saw camels. Awesome!

The rest of Saturday was a late lunch in Jerusalem (excellent, again), and Nimrod driving me back to the airport for an uneventful flight home. After the sunny deserts of Israel it was a bit of a relief to return to the cool, wet greenery of Auckland!

The trip was even more memorable than I'd expected. Nothing disappointed, everything was fascinating, and the food was unexpectedly sublime. My hosts Eran, Ruth, Nimrod and Nimrod's friends were simply wonderful. Now when I read in the Bible mentions of Jerusalem and other places I have a much better idea what they are --- and were --- really like, and for that and everything else I'm extremely grateful.

Thursday, 11 June 2015

Israel, Part 2

My Technion hosts Eran and Ruth were very eager to ensure I had a good time in Israel, and I'm immensely grateful to them for that. Ruth organised a day trip from Haifa to Nazareth for me (and another conference-related person) on Wednesday, with a Christian Arab guide called Nuha ("mind" in Arabic) who's based in Nazareth. We started at the International Mary of Nazareth Center, which has a beautiful chapel and a good view over Nazareth, and is built over a display of the ruins of a house from around the time of Jesus. The Center has a theme of Christian unity and combines elements of many Christian traditions --- I felt it very uplifting. Almost next door is the Basilica of the Annunciation, a Catholic cathedral celebrating the site where the angel announced to Mary her pregnancy. Parts of the cathedral are decorated with Madonna-and-child images donated by Catholics from many different cultures, and it's heartwarming to see how they've interpreted the scene according to their own cultures! The Basilica is a great example of how history piles up in layers in Israel; there was originally a Byzantine church on the site, Crusaders built on top of the ruins of that, and very recently Catholics built over those ruins. At each stage, some of the older buildings were preserved, so inside the modern cathedral you see parts of the walls of the Crusader church, which enclose even more ancient Byzantine ruins. We also visited the church at the traditional site of Joseph's home, a hundred-year-old cafe, a slightly older house with ceilings painted in the style of Orthodox iconography, the "White Mosque", and a spice shop built in an old milling factory --- all very interesting.

On Thursday I took the train to Tel Aviv to meet Martin Odersky and a guide to take us on a tour of Jerusalem --- again arranged by Ruth. Our guide first took us to look out over the area from a church tower at the Mount of Olives, which still has many olive trees. We parked near the city hall, and walked around the city walls past the Jaffa Gate and the Tower of David to enter the old city at the Zion Gate. The city walls of Jersualem are another place where every era has visibly built on the ruins of what came before. Inside the old city, there's so much history all piled together I can't even remember everything we saw. Buildings are piled atop and against each other in time and space, connected by a maze of roads, alleys, stairs, and tunnels ... and less visibly by the lives of countless generations of pilgrims, families, rulers and servants who frequented them. A few scenes particularly struck me: Jewish men studying Torah at the Tomb of David; the partially excavated "Broad Wall" of Hezekiah, 2,600 years old; joyous bar mitzvahs at the the Western Wall; the Via Dolorosa; the Church of the Holy Sepulchre with its polyglot patchwork of Christian communities worshiping --- and fighting --- together. Along the way we squeezed in a very nice meal at the "Abu-Taher" restaurant in the Muslim Quarter. It may be trite to say so, but the Old City of Jerusalem was the highlight of my whole trip. The place is steeped in history, politics, culture and religion like no other.

When you consider the past and present state of Jerusalem, it's easy to see tragedy, but to me it's also awe-inspiring to think about the generations of pilgrims, worshipers and warriors who have lived, prayed and died there through the millennia. Sin and redemption, destruction and creation are all part of the story of Jerusalem, as in all stories of God's dealings with us. I look forward to a time when God will make all things well, but I think we'll be treasuring those stories into eternity.

After checking into my hotel on Thursday evening, I had some time on my hands so I walked to the World Zionist Organization's gardens on Mount Herzl and then to the Yad Vashem Holocaust memorial. There's a path that physically and thematically connects the two, with commentary drawing the connection between the aftermath of the Holocaust and the establishment of the Israeli state. Even though I was familiar with much of the content, Yad Vashem was a powerful and humbling experience. There's no escaping the fact that --- with some notable exceptions --- Christians generally abetted or inadequately resisted the Holocaust. The question one has to ask oneself is: would I have done better? If another such test comes, will I do better? I hope reminders like Yad Vashem sharpen our resolve.