Efficient algorithms for bidirectional debugging
Efficient algorithms for bidirectional debugging
复制标题
用于双向调试的高效算法
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Bob Boothe
中科院分区：
文献类型：
--
作者：
Bob Boothe
本文讨论了我们的研究算法，以创建一个有效的双向调试器中，所有传统的向前移动命令可以在相反的方向上同样容易地执行。我们期望，将这些向后移动功能添加到调试器中将大大提高其作为编程工具的效率。
我们的方法的效率来自于我们使用的事件计数器，它嵌入到被调试的程序中。这些计数器被用来在目标程序执行的过程中精确地识别所需的目标事件。这与传统的调试器相反，传统的调试器可能会因为某些移动而多次返回调试器。对于反向运动，我们重新执行程序（可能使用两个通道）以识别并停止在所需的较早点。我们的基于计数器的技术对于这些反向运动是必不可少的，因为它们使我们能够有效地执行重新执行期间遇到的数百万个事件。
这个调试器的另外两个重要组件是它的I/O日志和检查点。我们记录系统调用的结果，并在以后重播，以确保确定性的重新执行，我们使用检查点来限制用于反向移动的重新执行量。短的移动通常是瞬时的，而长的移动的时间通常被限制在向后移动的时间距离的一个小的常数因子内。
This paper discusses our research into algorithms for creating anefficient bidirectional debugger in which all traditional forward movement commands can be performed with equal ease in the reverse direction. We expect that adding these backwards movement capabilities to a debugger will greatly increase its efficacy as a programming tool.
The efficiency of our methods arises from our use of event countersthat are embedded into the program being debugged. These counters areused to precisely identify the desired target event on the fly as thetarget program executes. This is in contrast to traditional debuggers that may trap back to the debugger many times for some movements. For reverse movements we re-execute the program (possibly using two passes) to identify and stop at the desired earlier point. Our counter based techniques are essential for these reverse movements because they allow us to efficiently execute through the millions of events encountered during re-execution.
Two other important components of this debugger are its I/O logging and checkpointing. We log and later replay the results of system callsto ensure deterministic re-execution, and we use checkpointing to bound theamount of re-execution used for reverse movements. Short movements generally appear instantaneous, and the time for longer movements is usually bounded within a small constant factor of the temporal distance moved back.