DRDDR: a lightweight method to detect data races in Linux kernel

详细信息    查看全文

• 作者：Yunyun Jiang ; Yi Yang ; Tian Xiao ; Tianwei Sheng…
• 关键词：Data race detection ; Linux kernel ; Synchronization ; Debug register ; Sample
• 刊名：The Journal of Supercomputing
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：72
• 期：4
• 页码：1645-1659
• 全文大小：729 KB
• 参考文献：1.Leveson NG, Turner CS (1993) An investigation of the Therac-25 accidents. Computer 26(7):18–41CrossRef
  2.Poulsen K (2004) Software bug contributed to blackout. Security Focus. http://​www.​securityfocus.​com/​news/​8016
  3.Joab J (2012) Nasdaq’s Facebook glitch came from ‘race conditions’. http://​www.​computerworld.​com/​s/​article/​9227350
  4.Lamport L (1978) Time, clocks, and the ordering of events in a distributed system. Commun ACM 21(7):558–565CrossRef MATH
  5.Savage S, Burrows M, Nelson G, Sobalvarro P, Anderson T (1997) Eraser: a dynamic data race detector for multithreaded programs. ACM Trans Computer Syst 15(4):391–411CrossRef
  6.Choi JD, Lee K, Loginov A, O’Callahan R, Sarkar V, Sridharan M (2002) Efficient and precise datarace detection for multithreaded object-oriented programs. PLDI’02 37(5):258–269
  7.Yu Y, Rodeheffer T, Chen W (2005) Racetrack: efficient detection of data race conditions via adaptive tracking. SOSP’05 39(5):221–234
  8.Erickson J, Musuvathi M, Burckhardt S, Olynyk K (2010) Effective data-race detection for the kernel. OSDI’10 10:1–16
  9.Baris K, Zamfir C, Candea G (2012) Data races vs. data race bugs: telling the difference with portend. ACM SIGPLAN Notices 47(4):185–198CrossRef
  10.Debugfs-The Linux Kernel Archives. https://​www.​kernel.​org/​doc/​Documentation/​fil-esystems/​debugfs.​txt
  11.Open Source Processor Emulator QEMU. http://​wiki.​qemu.​org/​
  12.Kernel Based Virtual Machine KVM. http://​www.​linux-kvm.​org/​page/​
  13.IA-32 Architecture. https://​software.​intel.​com/​en-us/​articles/​ia-32-intelr-64-ia-64-architecture-mean/​
  14.AMD-64 Architecture. http://​support.​amd.​com/​TechDocs/​24592
  15.MIPS R4000 Microprocessor. http://​groups.​csail.​mit.​edu/​cag/​raw/​documents/​R4400_​Uman_​book_​Ed2
  16.SPARC Architecture. http://​searchservervirt​ualization.​techtarget.​com/​definition/​SP-ARC
  17.PowerPC Architecture. https://​www-01.​ibm.​com/​chips/​techlib/​techlib.​nsf/​products/​PowerPC
  18.Linux Kernel Bugzilla. https://​bugzilla.​kernel.​org
  19.Ecryptfs bug in Linux kernel. https://​bugzilla.​kernel.​org/​id=​29752
  20.Ext2 bug in Linux kernel. https://​bugzilla.​kernel.​org/​id=​36002
  21.Linux Test Project. http://​ltp.​sourceforge.​net/​
  22.DRDDR source code on GitHub. https://​github.​com/​ahyangyi/​DRDDR
  23.Bond MD, Coons KE, McKinley KS (2010) PACER: proportional detection of data races. PLDI’10 45(6):255–268
  24.Marino D, Musuvathi M, Narayanasamy S (2009) LiteRace: effective sampling for lightweight data-race detection. PLDI’09 44(6):134–143
  25.Flanagan C, Freund SN (2009) FastTrack: efficient and precise dynamic race detection. PLDI’09 44(6):121–133
  26.Kaushik V, Chen PM, Flinn J, Narayanasamy S (2011) Detecting and surviving data races using complementary schedules. In: Proceedings of the twenty-third ACM symposium on operating systems principles, pp 369–384
  27.Huang J, Meredith PON, Rosu G (2014) Maximal sound predictive race detection with control flow abstraction. ACM SIGPLAN Notices 49(6):337–348CrossRef
  28.Pedro F, Li C, Rodrigues R (2011) Finding complex concurrency bugs in large multi-threaded applications. In: Proceedings of the sixth conference on computer systems, pp 215–228
  29.Baris K, Zamfir C, Candea G (2013) RaceMob: crowdsourced data race detection. In: Proceedings of the twenty-fourth ACM symposium on operating systems principles, pp 406–422
  30.Sheng TW, Vachharajani N, Eranian S, Hundt R, Chen WG, Zheng WM (2011) RACEZ: a lightweight and non-invasive race detection tool for production applications. ICSE’11 401–410
  31.Zhou P, Teodorescu R, Zhou YY (2007) HARD: hardware-assisted lockset-based race detection. In: IEEE 13th international symposium on high performance computer architecture, HPCA 2007, pp 121–132
  32.Gupta S, Sultan F, Cadambi S, Ivancic F, Rotteler M (2009) Using hardware transactional memory for data race detection. In: IEEE international symposium on IPDPS 2009, pp 1–11
  33.Abdullah M, Qi S, Torrellas J (2012) Vulcan: hardware support for detecting sequential consistency violations dynamically. In: 45th annual IEEE/ACM international symposium on microarchitecture (MICRO), 2012, pp 363–375
  34.Jin G, Zhang W, Deng D, (2012) Automated concurrency-bug fixing. In: Presented as part of the 10th USENIX symposium on operating systems design and implementation (OSDI 12), 2012, pp 221–236
  35.Narayanasamy S, Wang Z, Tigani J, Edwards A, Calder B (2007) Automatically classifying benign and harmful data races using replay analysis. In: Programming language design and implementation (PLDI ’07), pp 22–31
  36.Sheng TW (2010) Researches on key technologies of data races detection in concurrent programs. Dissertation for the Doctoral Degree. Tsinghua University, Beijing
  
• 作者单位：Yunyun Jiang (1)
  Yi Yang (1)
  Tian Xiao (1)
  Tianwei Sheng (2)
  Wenguang Chen (1)
  
  1. Department of Computer Science and Technology, Tsinghua University, Beijing, China
  2. Department of Computer Science and Engineering, University of California, San Diego, USA
  
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers and Interpreters
  Processor Architectures
  Computer Science, general
  
• 出版者：Springer Netherlands
• ISSN：1573-0484

文摘

Data races in parallel programs are notoriously difficult to detect and resolve. Existing research has mostly focused on data race detection at the user level and significant progress has been made in this regard. However, a very few efforts have attempted to address OS kernel level races. In contrast to user-level applications, the code in kernels uses vastly more complicated synchronization mechanisms, including different kinds of locks, hardware and software interrupts, widely used signal/wait primitives, and various types of low-level shared resources. It is therefore difficult to apply detection methods designed for user-level applications to identify OS kernel level races. In this paper, we present a new detection tool that is able to effectively detect race conditions in the Linux kernel environment. We use a dynamic detection approach, employing hardware debug registers available on commodity processors, to catch races on the fly during runtime. Preliminary experimental results show that our tool can effectively identify real data race instances.