Article

Samsara: efficient deterministic replay in multiprocessor environments with hardware virtualization extensions

Authors:

Weijia SongAuthors Info & Claims

USENIX ATC '16: Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference

Pages 551 - 564

Published: 22 June 2016 Publication History

Abstract

Deterministic replay, which provides the ability to travel backward in time and reconstruct the past execution flow of a multiprocessor system, has many prominent applications. Prior research in this area can be classified into two categories: hardware-only schemes and software-only schemes. While hardware-only schemes deliver high performance, they require significant modifications to the existing hardware which makes them difficult to deploy in real systems. In contrast, software-only schemes work on commodity hardware, but suffer from excessive performance overhead and huge logs caused by tracing every single memory access in the software layer.

In this paper, we present the design and implementation of a novel system, Samsara, which uses the hardware-assisted virtualization (HAV) extensions to achieve efficient and practical deterministic replay without requiring any hardware modification. Unlike prior software schemes which trace every single memory access to record interleaving, Samsara leverages the HAV extensions on commodity processors to track the read-set and write-set for implementing a chunk-based recording scheme in software. By doing so, we avoid all memory access detections, which is a major source of overhead in prior works. We implement and evaluate our system in KVM on commodity Intel Haswell processor. Evaluation results show that compared with prior software-only schemes, Samsara significantly reduces the log file size to 1/70th on average, and further reduces the recording overhead from about 10×, reported by state-of-the-art works, to 2.3× on average.

References

[1]

AGRAWAL, H., DE MILLO, R., AND SPAFFORD, E. An execution-backtracking approach to debugging. Software, IEEE 8, 3 (1991), 21-26.

[2]

ALTEKAR, G., AND STOICA, I. Odr: Output-deterministic replay for multicore debugging. In Proceedings of the ACM SIGOPS 22Nd Symposium on Operating Systems Principles (2009), pp. 193-206.

[3]

BASU, A., BOBBA, J., AND HILL, M. D. Karma: Scalable deterministic record-replay. In Proceedings of the International Conference on Supercomputing (2011), ICS '11, pp. 359-368.

[4]

BHANSALI, S., CHEN, W.-K., DE JONG, S., EDWARDS, A., MURRAY, R., DRINIC, M., MIHOČKA, D., AND CHAU, J. Framework for instruction-level tracing and analysis of program executions. In Proceedings of the 2Nd International Conference on Virtual Execution Environments (2006), VEE '06, pp. 154-163.

[5]

BIENIA, C. Benchmarking Modern Multiprocessors. PhD thesis, Princeton University, January 2011.

[6]

BRESSOUD, T. C., AND SCHNEIDER, F. B. Hypervisor-based fault tolerance. In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (1995), SOSP '95, pp. 1-11.

[7]

CHEN, A., MOORE, W. B., XIAO, H., HAEBERLEN, A., PHAN, L. T. X., SHERR, M., AND ZHOU, W. Detecting covert timing channels with time-deterministic replay. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14) (Broomfield, CO, Oct. 2014), pp. 541-554.

[8]

CHEN, Y., AND CHEN, H. Scalable deterministic replay in a parallel full-system emulator. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (2013), pp. 207-218.

[9]

CHEN, Y., HU, W., CHEN, T., AND WU, R. Lreplay: A pending period based deterministic replay scheme. In Proceedings of the 37th Annual International Symposium on Computer Architecture (2010), ISCA '10, pp. 187-197.

[10]

DAH-MING, C., AND RAJ, J. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks. Computer Networks and ISDN systems 17, 1 (1989), 1-14.

[11]

DEVECSERY, D., CHOW, M., DOU, X., FLINN, J., AND CHEN, P. M. Eidetic systems. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14) (Broomfield, CO, Oct. 2014), pp. 525-540.

[12]

DUNLAP, G. W., KING, S. T., CINAR, S., BASRAI, M. A., AND CHEN, P. M. Revirt: Enabling intrusion analysis through virtual-machine logging and replay. In Proceedings of the 2002 Symposium on Operating Systems Design and Implementation (2002), pp. 211-224.

[13]

DUNLAP, G. W., LUCCHETTI, D. G., FETTERMAN, M. A., AND CHEN, P. M. Execution replay of multiprocessor virtual machines. In Proceedings of the Fourth ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (2008), pp. 121-130.

[14]

HONARMAND, N., DAUTENHAHN, N., TORRELLAS, J., KING, S. T., POKAM, G., AND PEREIRA, C. Cyrus: Unintrusive application-level record-replay for replay parallelism. In Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems (2013), ASPLOS '13, pp. 193-206.

[15]

HONARMAND, N., AND TORRELLAS, J. Relaxreplay: Record and replay for relaxed-consistency multiprocessors. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems (2014), pp. 223-238.

[16]

HOWER, D. R., AND HILL, M. D. Rerun: Exploiting episodes for lightweight memory race recording. In Proceedings of the 35th Annual International Symposium on Computer Architecture (2008), ISCA '08, pp. 265-276.

[17]

JOSHI, A., KING, S. T., DUNLAP, G. W., AND CHEN, P. M. Detecting past and present intrusions through vulnerability-specific predicates. In Proceedings of the Twentieth ACM Symposium on Operating Systems Principles (2005), SOSP '05, pp. 91-104.

[18]

KING, S. T., AND CHEN, P. M. Backtracking intrusions. In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (2003), SOSP '03, pp. 223-236.

[19]

LEBLANC, T., AND MELLOR-CRUMMEY, J. Debugging parallel programs with instant replay. Computers, IEEE Transactions on C-36, 4 (April 1987), 471-482.

[20]

LEE, D., WESTER, B., VEERARAGHAVAN, K., NARAYANASAMY, S., CHEN, P. M., AND FLINN, J. Respec: Efficient online multiprocessor replayvia speculation and external determinism. In Proceedings of the Fifteenth Edition of ASPLOS on Architectural Support for Programming Languages and Operating Systems (2010), pp. 77-90.

[21]

MONTESINOS, P., CEZE, L., AND TORRELLAS, J. Delorean: Recording and deterministically replaying shared-memory multiprocessor execution efficiently. In Proceedings of the International Symposium on Computer Architecture (2008), pp. 289-300.

[22]

NARAYANASAMY, S., PEREIRA, C., AND CALDER, B. Recording shared memory dependencies using strata. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (2006), pp. 229-240.

[23]

NARAYANASAMY, S., POKAM, G., AND CALDER, B. Bugnet: Continuously recording program execution for deterministic replay debugging. In Proceedings of the 32Nd Annual International Symposium on Computer Architecture (2005), ISCA '05, pp. 284-295.

[24]

NETZER, R. H., AND XU, J. Adaptive message logging for incremental program replay. IEEE Concurrency 1, 4 (1993), 32-39.

[25]

OLSZEWSKI, M., ANSEL, J., AND AMARASINGHE, S. Kendo: Efficient deterministic multithreading in software. In Proceedings of the 14th International Conference on Architectural Support for Programming Languages and Operating Systems (2009), pp. 97-108.

[26]

PARK, S., ZHOU, Y., XIONG, W., YIN, Z., KAUSHIK, R., LEE, K. H., AND LU, S. Pres: Probabilistic replay with execution sketching on multiprocessors. In Proceedings of the ACM SIGOPS 22Nd Symposium on Operating Systems Principles (2009), pp. 177-192.

[27]

PATIL, H., PEREIRA, C., STALLCUP, M., LUECK, G., AND COWNIE, J. Pinplay: A framework for deterministic replay and reproducible analysis of parallel programs. In Proceedings of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization (2010), pp. 2-11.

[28]

POKAM, G., PEREIRA, C., DANNE, K., KASSA, R., AND ADL-TABATABAI, A.-R. Architecting a chunk-based memory race recorder in modern cmps. In Proceedings of the 42Nd Annual IEEE/ACM International Symposium on Microarchitecture (2009), MICRO 42, pp. 576-585.

[29]

QIAN, X., HUANG, H., SAHELICES, B., AND QIAN, D. Rainbow: Efficient memory dependence recording with high replay parallelism for relaxed memory model. In High Performance Computer Architecture (HPCA2013), 2013 IEEE 19th International Symposium on (Feb 2013), pp. 554-565.

[30]

QIAN, X., SAHELICES, B., AND QIAN, D. Pacifier: Record and replay for relaxed-consistency multiprocessors with distributed directory protocol. In Proceeding of the 41st Annual International Symposium on Computer Architecuture (2014), ISCA '14, pp. 433-444.

[31]

REN, S., LI, C., TAN, L., AND XIAO, Z. Samsara: Efficient deterministic replay with hardware virtualization extensions. In Proceedings of the 6th Asia-Pacific Workshop on Systems (2015), APSys '15, pp. 9:1-9:7.

[32]

SCALES, D. J., NELSON, M., AND VENKITACHALAM, G. The design of a practical system for fault-tolerant virtual machines. SIGOPS Oper. Syst. Rev. 44, 4 (Dec. 2010), 30-39.

[33]

SRINIVASAN, S. M., KANDULA, S., ANDREWS, C. R., AND ZHOU, Y. Flashback: A lightweight extension for rollback and deterministic replay for software debugging. In USENIX Annual Technical Conference, General Track (2004), pp. 29-44.

[34]

VEERARAGHAVAN, K., LEE, D., WESTER, B., OUYANG, J., CHEN, P. M., FLINN, J., AND NARAYANASAMY, S. Doubleplay: Parallelizing sequential logging and replay. ACM Trans. Comput. Syst. 30, 1 (Feb. 2012), 3:1-3:24.

[35]

VOSKUILEN, G., AHMAD, F., AND VIJAYKUMAR, T. N. Timetraveler: Exploiting acyclic races for optimizing memory race recording. In Proceedings of the 37th Annual International Symposium on Computer Architecture (2010), ISCA '10, pp. 198-209.

[36]

WOO, S. C., OHARA, M., TORRIE, E., SINGH, J. P., AND GUPTA, A. The splash-2 programs: Characterization and methodological considerations. In Proceedings of the 22Nd Annual International Symposium on Computer Architecture (1995), ISCA '95, pp. 24-36.

[37]

WU, X., AND MUELLER, F. Elastic and scalable tracing and accurate replay of non-deterministic events. In Proceedings of the 27th International ACM Conference on International Conference on Supercomputing (2013), ICS '13, pp. 59-68.

[38]

XU, M., BODIK, R., AND HILL, M. A "flight data recorder" for enabling full-system multiprocessor deterministic replay. In Proceedings of the International Symposium on Computer Architecture (2003), pp. 122-133.

[39]

XU, M., HILL, M. D., AND BODIK, R. A regulated transitive reduction (rtr) for longer memory race recording. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (2006), ASPLOS XII, pp. 49-60.

[40]

XU, M., MALYUGIN, V., SHELDON, J., VENKITACHALAM, G., AND WEISSMAN, B. Retrace: Collecting execution trace with virtual machine deterministic replay. In Proceedings of the Third Annual Workshop on Modeling, Benchmarking and Simulation (2007).

[41]

YANG, Z., YANG, M., XU, L., CHEN, H., AND ZANG, B. Order: Object centric deterministic replay for java. In USENIX Annual Technical Conference (2011).

[42]

ZHU, J., JIANG, Z., AND XIAO, Z. Twinkle: A fast resource provisioning mechanism for internet services. In Proceedings of the IEEE INFOCOM (2011), pp. 802-810.

[43]

ZHU, J., JIANG, Z., XIAO, Z., AND LI, X. Optimizing the performance of virtual machine synchronization for fault tolerance. IEEE Transactions on Computers 60, 12 (Dec 2011), 1718-1729.

Cited By

Ren SZhang YPan LXiao Z(2019)PhantasyIEEE Transactions on Computers10.1109/TC.2018.286594368:2(225-238)Online publication date: 17-Jul-2019
https://dl.acm.org/doi/10.1109/TC.2018.2865943
Stamatogiannakis MAthanasopoulos EBos HGroth P(2017)PROV2RACM Transactions on Internet Technology10.1145/306217617:4(1-24)Online publication date: 18-Aug-2017
https://dl.acm.org/doi/10.1145/3062176

Samsara: efficient deterministic replay in multiprocessor environments with hardware virtualization extensions
1. General and reference
  1. Cross-computing tools and techniques

Recommendations

Samsara: Efficient Deterministic Replay with Hardware Virtualization Extensions
APSys '15: Proceedings of the 6th Asia-Pacific Workshop on Systems

Deterministic replay, which provides the ability to travel backward in time and reconstructs the past execution flow of a multi-processor system, has many prominent applications including cyclic debugging, intrusion detection, malware analysis, and ...
SRVM: Hypervisor Support for Live Migration with Passthrough SR-IOV Network Devices
VEE '16

Single-Root I/O Virtualization (SR-IOV) is a specification that allows a single PCI Express (PCIe) device (ysical function or PF) to be used as multiple PCIe devices (virtual functions or VF). In a virtualization system, each VF can be directly assigned ...
SRVM: Hypervisor Support for Live Migration with Passthrough SR-IOV Network Devices
VEE '16: Proceedings of the12th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments

Single-Root I/O Virtualization (SR-IOV) is a specification that allows a single PCI Express (PCIe) device (ysical function or PF) to be used as multiple PCIe devices (virtual functions or VF). In a virtualization system, each VF can be directly assigned ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

USENIX ATC '16: Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference

June 2016

662 pages

ISBN:9781931971300

Program Chairs:
Ajay Gulati
Zerostack, Inc.
,
Hakim Weatherspoon
Cornell University

Sponsors

VMware
NetApp
Google Inc.
NSF
Facebook: Facebook

Publisher

USENIX Association

United States

Publication History

Published: 22 June 2016

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ren SZhang YPan LXiao Z(2019)PhantasyIEEE Transactions on Computers10.1109/TC.2018.286594368:2(225-238)Online publication date: 17-Jul-2019
https://dl.acm.org/doi/10.1109/TC.2018.2865943
Stamatogiannakis MAthanasopoulos EBos HGroth P(2017)PROV2RACM Transactions on Internet Technology10.1145/306217617:4(1-24)Online publication date: 18-Aug-2017
https://dl.acm.org/doi/10.1145/3062176

View Options

View options

Media

Figures

Other

Tables

View Table of Contents