Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3445814.3446744acmconferencesArticle/Chapter ViewAbstractPublication PagesasplosConference Proceedingsconference-collections
research-article

Fast, flexible, and comprehensive bug detection for persistent memory programs

Published: 17 April 2021 Publication History

Abstract

Debugging persistent memory (PM) programs faces a fundamental tradeoff between performance overhead and bug coverage (comprehensiveness). Large performance overhead or limited bug coverage makes debugging infeasible or ineffective for PM programs. We present PMDebugger, a debugger that detects crash consistency bugs in PM programs. Unlike prior work, PMDebugger is fast, flexible and comprehensive. The design of PMDebugger is driven by a characterization that shows how three fundamental operations in PM programs (store, cache writeback and fence) typically occur in PM programs. PMDebugger uses a hierarchical design composed of PM debugging-specific data structures, operations and bug-detection algorithms (rules). We generalize nine rules to detect crash-consistency bugs for various PM persistency models. Compared with a state-of-the-art detector (XFDetector) and an industry-quality detector (Pmemcheck), PMDebugger leads to 49.3x and 3.4x speedup on average. Compared with another state-of-the-art detector (PMTest) optimized for high performance, PMDebugger achieves comparable performance (within a factor of 2), without heavily relying on programmer annotations, and detects 38 more bugs on ten applications. PMDebugger also identifies more bugs than XFDetector and Pmemcheck. PMDebugger detects 19 new bugs in a real application (memcached) and two new bugs from Intel PMDK.

References

[1]
Joy Arulraj, Andrew Pavlo, and Subramanya R. Dulloor. 2015. Let's Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD).
[2]
Dhruva R. Chakrabarti, Hans-J. Boehm, and Kumud Bhandari. 2014. Atlas: Leveraging Locks for Non-Volatile Memory Consistency. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA).
[3]
Youmin Chen, Youyou Lu, Fan Yang, Qing Wang, Yang Wang, and Jiwu Shu. 2020. FlatStore: An Eficient Log-Structured Key-Value Storage Engine for Persistent Memory. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[4]
Joel Coburn, Adrian M. Caulfield, Ameen Akel, Laura M. Grupp, Rajesh K. Gupta, Ranjit Jhala, and Steven Swanson. 2011. NV-Heaps: making persistent objects fast and safe with next-generation, non-volatile memories. In Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[5]
Jeremy Condit, Edmund B. Nightingale, Christopher Frost, Engin Ipek, Benjamin Lee, Doug Burger, and Derrick Coetzee. 2009. Better I/O through ByteAddressable, Persistent Memory. In Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles (SOSP).
[6]
Jeremy Condit, Edmund B. Nightingale, Christopher Frost, Engin Ipek, Benjamin C. Lee, Doug Burger, and Derrick Coetzee. 2009. Better I/O through byte-addressable, persistent memory. In Proceedings of the 22nd ACM Symposium on Operating Systems Principles (SOSP).
[7]
Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing.
[8]
Intel Corporation. 2015. An introduction to pmemcheck. https://pmem.io/ 2015 / 07/17/pmemcheck-basic. html.
[9]
Intel Corporation. 2018. Intel architecture instruction set extensions programming reference. https://software.intel.com/sites/default/files/managed/c5/15/ architecture-instruction-set-extensions-programming-reference.pdf.
[10]
Intel Corporation. 2018. Redis. https://github.com/pmem/redis/tree/3.2-nvml.
[11]
Intel Corporation. 2020. Detect Persistent Memory Programming Errors Using Persistence Inspector. https://software.intel.com/content/www/us/en/develop/ articles/detect-persistent-memory-programming-errors-with-intel-inspectorpersistence-inspector.html.
[12]
Intel Corporation. 2020. Inconsistency bugs in array example for libpmemobj. https://github.com/pmem/pmdk/issues/4927.
[13]
Intel Corporation. 2020. Intel Optane DC persistent memory. https: //www.intel.com/content/www/us/en/architecture-and-technology/optanedc-persistent-memory.html.
[14]
Intel Corporation. 2020. Obj: fix data_store example transaction logic to remove redudant fences. https://github.com/pmem/pmdk/pull/4939/commits/ e394307ef2baea1de31fa054a1e2c3df3581a59.
[15]
Intel Corporation. 2020. Persistent memory programming. https://pmem.io/.
[16]
Joel E. Denny, Seyong Lee, and Jefrey S. Vetter. 2016. NVL-C: Static Analysis Techniques for Eficient, Correct Programming of Non-Volatile Main Memory Systems. In Proceedings of the 25th ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC).
[17]
Mingkai Dong, Heng Bu, Jifei Yi, Benchao Dong, and Haibo Chen. 2019. Performance and Protection in the ZoFS User-Space NVM File System. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP).
[18]
Vaibhav Gogte, William Wang, Stephan Diestelhorst, Peter M. Chen, Satish Narayanasamy, and Thomas F. Wenisch. 2020. Relaxed Persist Ordering Using Strand Persistency. In ACM/IEEE 47st International Symposium on Computer Architecture (ISCA).
[19]
Jinyu Gu, Qianqian Yu, Xiayang Wang, Zhaoguo Wang, Binyu Zang, Haibing Guan, and Haibo Chen. 2019. Pisces: A Scalable and Eficient Persistent Transactional Memory. In Proceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC).
[20]
Swapnil Haria, Mark D. Hill, and Michael M. Swift. 2020. MOD: Minimally Ordered Durable Datastructures for Persistent Memory. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[21]
Terry Ching-Hsiang Hsu, Helge Brügner, Indrajit Roy, Kimberly Keeton, and Patrick Eugster. 2017. NVthreads: Practical Persistence for Multi-Threaded Applications. In Proceedings of the Twelfth European Conference on Computer Systems (EuroSys).
[22]
Jian Huang, Karsten Schwan, and Moinuddin K. Qureshi. 2014. NVRAM-Aware Logging in Transaction Systems. Proceedings of the VLDB Endowment ( 2014 ).
[23]
Joseph Izraelevitz, Terence Kelly, and Aasheesh Kolli. 2016. Failure-Atomic Persistent Memory Updates via JUSTDO Logging. In Proceedings of the TwentyFirst International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[24]
Jungi Jeong and Changhee Jung. 2021. PMEM-Spec: Persistent Memory Speculation (Strict Persistency Can Trump Relaxed Persistency). In Proceedings of the Twenty-Sixth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[25]
A. Joshi, V. Nagarajan, S. Viglas, and M. Cintra. 2017. ATOM: Atomic Durability in Non-volatile Memory through Hardware Logging. In 2017 IEEE International Symposium on High Performance Computer Architecture (HPCA).
[26]
Rohan Kadekodi, Se Kwon Lee, Sanidhya Kashyap, Taesoo Kim, Aasheesh Kolli, and Vijay Chidambaram. 2019. SplitFS: Reducing Software Overhead in File Systems for Persistent Memory. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP).
[27]
Olzhas Kaiyrakhmet, Songyi Lee, Beomseok Nam, Sam H. Noh, and Young-Ri Choi. 2019. SLM-DB: Single-Level Key-Value Store with Persistent Memory. In Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST).
[28]
Aasheesh Kolli, Jef Rosen, Stephan Diestelhorst, Ali Saidi, Steven Pelley, Sihang Liu, Peter M. Chen, and Thomas F. Wenisch. 2016. Delegated Persist Ordering. In The 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO).
[29]
Aasheesh Kolli, Jef Rosen, Stephan Diestelhorst, Ali G. Saidi, Steven Pelley, Sihang Liu, Peter M. Chen, and Thomas F. Wenisch. 2016. Delegated persist ordering. In 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO).
[30]
Harendra Kumar, Yuvraj Patel, Ram Kesavan, and Sumith Makam. 2017. High Performance Metadata Integrity Protection in the WAFL Copy-on-Write File System. In 15th USENIX Conference on File and Storage Technologies, (FAST).
[31]
Youngjin Kwon, Henrique Fingler, Tyler Hunt, Simon Peter, Emmett Witchel, and Thomas Anderson. 2017. Strata: A Cross Media File System. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP).
[32]
Youngjin Kwon, Henrique Fingler, Tyler Hunt, Simon Peter, Emmett Witchel, and Thomas E. Anderson. 2017. Strata: A Cross Media File System. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP).
[33]
Philip Lantz, Dulloor Subramanya Rao, Sanjay Kumar, Rajesh Sankaran, and Jef Jackson. 2014. Yat: A Validation Framework for Persistent Memory Software. In Proceedings of the 2014 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC).
[34]
Se Kwon Lee, Jayashree Mohan, Sanidhya Kashyap, Taesoo Kim, and Vijay Chidambaram. 2019. Recipe: Converting Concurrent DRAM Indexes to PersistentMemory Indexes. In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP).
[35]
Lenovo. 2018. Memcached-pmem. https://github.com/lenovo/memcachedpmem.
[36]
Mengxing Liu, Mingxing Zhang, Kang Chen, Xuehai Qian, Yongwei Wu, Weimin Zheng, and Jinglei Ren. 2017. DudeTM: Building Durable Transactions with Decoupling for Persistent Memory. In Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[37]
Qingrui Liu, Joseph Izraelevitz, Se Kwon Lee, Michael L. Scott, Sam H. Noh, and Changhee Jung. 2018. iDO: Compiler-Directed Failure Atomicity for Nonvolatile Memory. In 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO).
[38]
Sihang Liu, Korakit Seemakhupt, Yizhou Wei, Thomas F. Wenisch, Aasheesh Kolli, and Samira Khan. 2020. Cross-Failure Bug Detection in Persistent Memory Programs. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[39]
Sihang Liu, Yizhou Wei, Jishen Zhao, Aasheesh Kolli, and Samira Manabi Khan. 2019. PMTest: A Fast and Flexible Testing Framework for Persistent Memory Programs. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[40]
Baotong Lu, Xiangpeng Hao, Tianzheng Wang, and Eric Lo. 2020. Dash: Scalable Hashing on Persistent Memory. Proceedings of the VLDB Endowment ( 2020 ).
[41]
Sanketh Nalli, Swapnil Haria, Mark D. Hill, Michael M. Swift, Haris Volos, and Kimberly Keeton. 2017. An Analysis of Persistent Memory Use with WHISPER. In Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[42]
Moohyeon Nam, Hokeun Cha, Young ri Choi, Sam H. Noh, and Beomseok Nam. 2019. Write-Optimized Dynamic Hashing for Persistent Memory. In 17th USENIX Conference on File and Storage Technologies (FAST).
[43]
Ian Neal, Ben Reeves, Ben Stoler, Andrew Quinn, Youngjin Kwon, Simon Peter, and Baris Kasikci. 2020. AGAMOTTO: How Persistent is your Persistent Memory Application?. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI).
[44]
Matheus Almeida Ogleari, Ethan L. Miller, and Jishen Zhao. 2018. Steal but No Force: Eficient Hardware Undo+Redo Logging for Persistent Memory Systems. In 2018 IEEE International Symposium on High Performance Computer Architecture (HPCA).
[45]
Steven Pelley, Peter M. Chen, and Thomas F. Wenisch. 2014. Memory persistency. In ACM/IEEE 41st International Symposium on Computer Architecture (ISCA).
[46]
PMDebugger. 2020. https://github.com/PASAUCMerced/PMDebugger.
[47]
Dulloor Subramanya Rao, Sanjay Kumar, Anil S. Keshavamurthy, Philip Lantz, Dheeraj Reddy, Rajesh Sankaran, and Jef Jackson. 2014. System software for persistent memory. In Proceedings of the Ninth European Conference on Computer Systems (EuroSys).
[48]
Jinglei Ren, Jishen Zhao, Samira Khan, Jongmoo Choi, Yongwei Wu, and Onur Mutlu. 2015. ThyNVM: Enabling Software-Transparent Crash Consistency in Persistent Memory Systems. In Proceedings of the International Symposium on Microarchitecture (MICRO).
[49]
Valgrind. 2020. An instrumentation framework for building dynamic analysis tools. https://valgrind.org.
[50]
Alexander van Renen, Viktor Leis, Alfons Kemper, Thomas Neumann, Takushi Hashida, Kazuichi Oe, Yoshiyasu Doi, Lilian Harada, and Mitsuru Sato. 2018. Managing Non-Volatile Memory in Database Systems. In Proceedings of the 2018 ACM SIGMOD International Conference on Management of Data (SIGMOD).
[51]
Haris Volos, Andres Jaan Tack, and Michael M. Swift. 2011. Mnemosyne: lightweight persistent memory. In Proceedings of the 16th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[52]
Xingbo Wu, Fan Ni, Li Zhang, Yandong Wang, Yufei Ren, Michel Hack, Zili Shao, and Song Jiang. 2016. NVMcached: An NVM-based Key-Value Cache. In Proceedings of the 7th ACM SIGOPS Asia-Pacific Workshop on Systems.
[53]
Zhenwei Wu, Kai Lu, Andrew Nisbet, Wenzhe Zhang, and Mikel Luján. 2020. PMThreads: Persistent Memory Threads Harnessing Versioned Shadow Copies. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI).
[54]
Fei Xia, Dejun Jiang, Jin Xiong, and Ninghui Sun. 2017. HiKV: A Hybrid Index Key-Value Store for DRAM-NVM Memory Systems. In Proceedings of the 2017 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC).
[55]
Jian Xu and Steven Swanson. 2016. NOVA: A Log-structured File System for Hybrid Volatile/Non-volatile Main Memories. In 14th USENIX Conference on File and Storage Technologies (FAST).
[56]
Jian Xu, Lu Zhang, Amirsaman Memaripour, Akshatha Gangadharaiah, Amit Borase, Tamires Brito Da Silva, Steven Swanson, and Andy Rudof. 2017. NOVAFortis: A Fault-Tolerant Non-Volatile Main Memory File System. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP).
[57]
Yiying Zhang, Jian Yang, Amirsaman Memaripour, and Steven Swanson. 2015. Mojim: A Reliable and Highly-Available Non-Volatile Memory System. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS).
[58]
Pengfei Zuo, Yu Hua, and Jie Wu. 2018. Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory. In Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation (OSDI).
[59]
Yoav Zuriel, Michal Friedman, Gali Shefi, Nachshon Cohen, and Erez Petrank. 2019. Eficient Lock-Free Durable Sets. ( 2019 ).

Cited By

View all
  • (2024)Constraint Based Program Repair for Persistent Memory BugsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639204(1-12)Online publication date: 20-May-2024
  • (2024)SPP: Safe Persistent Pointers for Memory Safety2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58291.2024.00019(37-52)Online publication date: 24-Jun-2024
  • (2024) Reviving Storage Systems Education in the 21 st Century — An experience report 2024 IEEE 24th International Symposium on Cluster, Cloud and Internet Computing (CCGrid)10.1109/CCGrid59990.2024.00074(616-625)Online publication date: 6-May-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ASPLOS '21: Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems
April 2021
1090 pages
ISBN:9781450383172
DOI:10.1145/3445814
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 April 2021

Permissions

Request permissions for this article.

Check for updates

Badges

Author Tags

  1. Crash Consistency
  2. Debugging
  3. Persistent Memory
  4. Testing

Qualifiers

  • Research-article

Conference

ASPLOS '21
Sponsor:

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)74
  • Downloads (Last 6 weeks)3
Reflects downloads up to 14 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Constraint Based Program Repair for Persistent Memory BugsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639204(1-12)Online publication date: 20-May-2024
  • (2024)SPP: Safe Persistent Pointers for Memory Safety2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58291.2024.00019(37-52)Online publication date: 24-Jun-2024
  • (2024) Reviving Storage Systems Education in the 21 st Century — An experience report 2024 IEEE 24th International Symposium on Cluster, Cloud and Internet Computing (CCGrid)10.1109/CCGrid59990.2024.00074(616-625)Online publication date: 6-May-2024
  • (2023)Breathing New Life into an Old Tree: Resolving Logging Dilemma of B+-tree on Modern Computational Storage DrivesProceedings of the VLDB Endowment10.14778/3626292.362629717:2(134-147)Online publication date: 1-Oct-2023
  • (2023)Mumak: Efficient and Black-Box Bug Detection for Persistent MemoryProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3587447(734-750)Online publication date: 8-May-2023
  • (2023)On the Performance Intricacies of Persistent Memory Aware Storage EnginesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.324864335:10(10365-10382)Online publication date: 1-Oct-2023
  • (2023)A quantitative evaluation of persistent memory hash indexesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00812-133:2(375-397)Online publication date: 9-Sep-2023
  • (2022)Halo: A Hybrid PMem-DRAM Persistent Hash Index with Fast RecoveryProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517884(1049-1063)Online publication date: 10-Jun-2022
  • (2022)Unified Holistic Memory Management Supporting Multiple Big Data Processing Frameworks over Hybrid MemoriesACM Transactions on Computer Systems10.1145/351121139:1-4(1-38)Online publication date: 5-Jul-2022
  • (2022)Yashme: detecting persistency racesProceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3503222.3507766(830-845)Online publication date: 28-Feb-2022
  • Show More Cited By

View Options

Get Access

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media