ODR

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

ODR: output-deterministic replay for multicore debugging

Full text

Pdf (658 KB)

Source

ACM Symposium on Operating Systems Principles archive
Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles table of contents

Big Sky, Montana, USA

SESSION: Parallel debugging table of contents

Pages 193-206

Year of Publication: 2009

ISBN:978-1-60558-752-3

Authors

Gautam Altekar	UC Berkeley, Berkeley, USA
Ion Stoica	UC Berkeley, Berkeley, USA

Sponsors

ACM: Association for Computing Machinery
SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 61, Downloads (12 Months): 61, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629575.1629594 What is a DOI?

ABSTRACT

Reproducing bugs is hard. Deterministic replay systems address this problem by providing a high-fidelity replica of an original program run that can be repeatedly executed to zero-in on bugs. Unfortunately, existing replay systems for multiprocessor programs fall short. These systems either incur high overheads, rely on non-standard multiprocessor hardware, or fail to reliably reproduce executions. Their primary stumbling block is data races -- a source of nondeterminism that must be captured if executions are to be faithfully reproduced.

In this paper, we present ODR--a software-only replay system that reproduces bugs and provides low-overhead multiprocessor recording. The key observation behind ODR is that, for debugging purposes, a replay system does not need to generate a high-fidelity replica of the original execution. Instead, it suffices to produce any execution that exhibits the same outputs as the original. Guided by this observation, ODR relaxes its fidelity guarantees to avoid the problem of reproducing data-races altogether. The result is a system that replays real multiprocessor applications, such as Apache, MySQL, and the Java Virtual Machine, and provides low record-mode overhead.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	G. Altekar and I. Stoica. Output--deterministic replay for multicore debugging. Technical Report UCB/EECS-2009-108, EECS Department, University of California, Berkeley, Aug 2009.
	2	A. Ayers, R. Schooler, C. Metcalf, A. Agarwal, J. Rhee, and E. Witchel. Traceback: first fault diagnosis by reconstruction of distributed control flow. In V. Sarkar and M.W. Hall, editors, PLDI, pages 201--212. ACM, 2005.
	3	S. Bhansali, W.-K. Chen, S. de Jong, A. Edwards, R. Murray, M. Drinić, D. MihoÇcka, and J. Chau. Framework for instruction-level tracing and analysis of program executions. In VEE '06, pages 154--163, New York, NY, USA, 2006. ACM.
	4	C. Cadar, V. Ganesh, P.M. Pawlowski, D.L. Dill, and D.R. Engler. Exe: automatically generating inputs of death. In CCS '06: Proceedings of the 13th ACM conference on Computer and communications security, pages 322--335, New York, NY, USA, 2006. ACM Press.
	5	G.W. Dunlap, D.G. Lucchetti, M.A. Fetterman, and P.M. Chen. Execution replay of multiprocessor virtual machines. In VEE '08, pages 121--130, New York, NY, USA, 2008. ACM.
	6	V. Ganesh and D.L. Dill. A decision procedure for bit-vectors and arrays. In W. Damm and H. Hermanns, editors, CAV, volume 4590 of Lecture Notes in Computer Science, pages 519--531. Springer, 2007.
	7	D. Geels, G. Altekar, S. Shenker, and I. Stoica. Replay debugging for distributed applications. In USENIX Annual Technical Conference, General Track, pages 289--300. USENIX, 2006.
	8	Z. Guo, X. Wang, J. Tang, X. Liu, Z. Xu, M. Wu, M.F. Kaashoek, and Z. Zhang. R2: An application-level kernel for record and replay. In R. Draves and R. van Renesse, editors, OSDI, pages 193--208. USENIX Association, 2008.
	9	J.L. Hennessy and D.A. Patterson. Computer Architecture, Fourth Edition: A Quantitative Approach. Morgan Kaufmann, September 2006.
	10	D.R. Hower and M.D. Hill. Rerun: Exploiting episodes for lightweight memory race recording. In ISCA '08: Proceedings of the 35th International Symposium on Computer Architecture, pages 265--276, Washington, DC, USA, 2008. IEEE Computer Society.
	11	Intel. Intel 64 and IA-32 Architectures Reference Manual, November 2008.
	12	J.C. King. Symbolic execution and program testing. Commun. ACM, 19(7):385--394, 1976.
	13	S.T. King, G.W. Dunlap, and P.M. Chen. Debugging operating systems with time-traveling virtual machines. In USENIX Annual Technical Conference, General Track, pages 1--15. USENIX, 2005.
	14	L. Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558--565, 1978.
	15	C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V.J. Reddi, and K. Hazelwood. Pin: building customized program analysis tools with dynamic instrumentation. In PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, volume 40, pages 190--200, New York, NY, USA, June 2005. ACM Press.
	16	D.A. Molnar and D. Wagner. Catchconv: Symbolic execution and run-time type inference for integer conversion errors. Technical Report UCB/EECS-2007-23, EECS Department, University of California, Berkeley, 2007.
	17	P. Montesinos, L. Ceze, and J. Torrellas. Delorean: Recording and deterministically replaying shared=memory multiprocessor execution efficiently. In ISCA '08: Proceedings of the 35th International Symposium on Computer Architecture, pages 289--300, Washington, DC, USA, 2008. IEEE Computer Society.
	18	P. Montesinos, M. Hicks, S.T. King, and J. Torrellas. Capo: a software-hardware interface for practical deterministic multiprocessor replay. In M.L. Soffa and M.J. Irwin, editors, ASPLOS, pages 73--84. ACM, 2009.
	19	N. Nethercote and J. Seward. Valgrind: a framework for heavyweight dynamic binary instrumentation. SIGPLAN Not., 42(6):89--100, June 2007.
	20	J. Pool, I.S.K. Wong, and D. Lie. Relaxed determinism: making redundant execution on multiprocessors practical. In HOTOS'07: Proceedings of the 11th USENIX workshop on Hot topics in operating systems, pages 1--6, Berkeley, CA, USA, 2007. USENIX Association.
	21	M. Ronsse and K. De Bosschere. Recplay: a fully integrated practical record/replay system. ACM Trans. Comput. Syst., 17(2):133--152, 1999.
	22	Y. Saito. Jockey: A user-space library for record-replay debugging. In In AADEBUG'05: Proceedings of the sixth international symposium on Automated analysis-driven debugging, pages 69--76. ACM Press, 2005.
	23	S.C. Woo, M. Ohara, E. Torrie, J.P. Singh, and A. Gupta. The SPLASH-2 programs: Characterization and methodological considerations. In Proceedings of the 22nd Annual International Symposium on Computer Architecture, pages 24--37, New York, February 1995. ACM Press.