[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1519065.1519095acmconferencesArticle/Chapter ViewAbstractPublication PageseurosysConference Proceedingsconference-collections
research-article

Dingo: taming device drivers

Published: 01 April 2009 Publication History

Abstract

Device drivers are notorious for being a major source of failure in operating systems. In analysing a sample of real defects in Linux drivers, we found that a large proportion (39%) of bugs are due to two key shortcomings in the device-driver architecture enforced by current operating systems: poorly-defined communication protocols between drivers and the OS, which confuse developers and lead to protocol violations, and a multithreaded model of computation that leads to numerous race conditions and deadlocks.
We claim that a better device driver architecture can help reduce the occurrence of these faults, and present our Dingo framework as constructive proof. Dingo provides a formal, state-machine based, language for describing driver protocols, which avoids confusion and ambiguity, and helps driver writers implement correct behaviour. It also enforces an event-driven model of computation, which eliminates most concurrency-related faults. Our implementation of the Dingo architecture in Linux offers these improvements, while introducing negligible performance overhead. It allows Dingo and native Linux drivers to coexist, providing a gradual migration path to more reliable device drivers.

References

[1]
A. Adya, J. Howell, M. Theimer, W. Bolosky, and J. Douceur. Cooperative task management without manual stack management. In 2002 USENIX, pages 289--302, Monterey, CA, USA, Jun 2002.
[2]
Apple Inc. Apple Inc. Introduction to I/O Kit fundamentals, Nov 2006.
[3]
Thomas Ball, Ella Bounimova, Byron Cook, Vladimir Levin, Jakob Lichtenberg, Con McGarvey, Bohus Ondrusek, Sriram K. Rajamani, and Abdullah Ustuner. Thorough static analysis of device drivers. In 1st EuroSys Conf., pages 73--85, Leuven, Belgium, Apr 2006.
[4]
Andy Chou, Bryan Fulton, and Seth Hallem. Linux kernel security report, 2005.
[5]
Andy Chou, Jun-Feng Yang, Benjamin Chelf, Seth Hallem, and Dawson Engler. An empirical study of operating systems errors. In 18th SOSP, pages 73--88, Lake Louise, Alta, Canada, Oct 2001.
[6]
Christopher L. Conway and Stephen A. Edwards. NDL: a domain-specific language for device drivers. In LCTES'04, pages 30--36, Washington, DC, USA, Jun 2004.
[7]
Dawson R. Engler, Benjamin Chelf, Andy Chou, and Seth Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In 4th OSDI, pages 1--16, San Diego, CA, Oct 2000.
[8]
Ulfar Erlingsson, Martin Abadi, Michael Vrable, Mihai Budiu, and George C. Necula. XFI: software guards for system address spaces. In 7th OSDI, pages 75--88, Seattle, Washington, Nov 2006.
[9]
Manuel Fahndrich, Mark Aiken, Chris Hawblitzel, Orion Hodson, Galen C. Hunt, James R. Larus, and Steven Levi. Language support for fast and reliable message-based communication in Singularity OS. In 1st EuroSys Conf., pages 177--190, Leuven, Belgium, Apr 2006.
[10]
Alessandro Forin, David Golub, and Brian Bershad. An I/O system for Mach 3.0. In USENIX Mach Symp., pages 163--176, Monterey, CA, USA, Nov 1991.
[11]
Archana Ganapathi, Viji Ganapathi, and David Patterson. Windows XP kernel crash analysis. In 20th LISA, pages 101--111, Washington, DC, USA, 2006.
[12]
David Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8(3) 231--274, Jun 1987.
[13]
Jorrit N. Herder, Herbert Bos, Ben Gras, Philip Homburg, and Andrew S. Tanenbaum. MINIX 3: A highly reliable, self-repairing operating system. Operat. Syst. Rev., 40(3) 80--89, Jul 2006.
[14]
Maxwell Krohn, Eddie Kohler, and M. Frans Kaashoek. Events can make sense. In 2007 USENIX, pages 1--14, Santa Clara, CA, USA, Jun 2007.
[15]
H. C. Lauer and R. M. Needham. On the duality of operating system structures. In 2nd Int. Symp. Operat. Syst., pages 3--19, Rocquerncourt, France, Oct 1978.
[16]
Ben Leslie, Peter Chubb, Nicholas Fitzroy-Dale, Stefan Gotz, Charles Gray, Luke Macpherson, Daniel Potts, Yueting (Rita) Shen, Kevin Elphinstone, and Gernot Heiser. User-level device drivers: Achieved performance. Journal of Computer Science and Technology, 20(5) 654--664, Sep 2005.
[17]
Jochen Liedtke, Ulrich Bartling, Uwe Beyer, Dietmar Heinrichs, Rudolf Ruland, and Gyula Szalay. Two years of experience with a u-kernel based OS. Operat. Syst. Rev., 25(2) 51--62, Apr 1991.
[18]
Fabrice Merillon, Laurent Reveillere, Charles Consel, Renaud Marlet, and Gilles Muller. Devil: An IDL for hardware programming. In 4th OSDI, pages 17--30, San Diego, CA, USA, Oct 2000.
[19]
Microsoft. Architecture of the user-mode driver framework, 2007.
[20]
Brendan Murphy. Automating software failure reporting. ACM Queue, 2(8) 42--48, Nov 2004.
[21]
Bryce Nakatani. User mode drivers, 2002.
[22]
OMG. UML 2.0 specification, 2005.
[23]
Leonid Ryzhyk, Ihor Kuz, and Gernot Heiser. Formalising device driver interfaces. In 4th PLOS, Stevenson, Washington, USA, Oct 2007.
[24]
Mark Sullivan and Ram Chillarege. Software defects and their impact on system availability -- a study of field failures in operating systems. In 21st IEEE Int. Symp. Fault-Tolerant Comput., pages 2--9, Montreal, Canada, Jun 1991.
[25]
Jun Sun, Wanghong Yuan, Mahesh Kallahalla, and Nayeem Islam. HAIL: a language for easy and correct device access. In 5th EMSOFT, pages 1--9, Jersey City, NJ, USA, Sep 2005.
[26]
Michael M. Swift, Steven Marting, Henry M. Levy, and Susan G. Eggers. Nooks: An architecture for reliable device drivers. In 10th SIGOPS Eur. WS, pages 101--107, St Emilion, France, Sep 2002.
[27]
Rob von Behren, Jeremy Condit, and Eric Brewer. Why events are a bad idea (for high-concurrency servers). In 9th HotOS, pages 19--24, Lihue, Hawaii, USA, May 2003.
[28]
Feng Zhou, Jeremy Condit, Zachary Anderson, Ilya Bagrak, Rob Ennals, Matthew Harren, George Necula, and Eric Brewer. SafeDrive: Safe and recoverable extensions using language-based techniques. In 7th OSDI, pages 45--60, Seattle, WA, USA, Nov 2006.

Cited By

View all
  • (2023)Why write address translation OS code yourself when you can synthesize it?Proceedings of the 19th Workshop on Hot Topics in Operating Systems10.1145/3593856.3595895(174-180)Online publication date: 22-Jun-2023
  • (2023)Sfitag: Efficient Software Fault Isolation with Memory Tagging for ARM Kernel ExtensionsProceedings of the 2023 ACM Asia Conference on Computer and Communications Security10.1145/3579856.3590341(469-480)Online publication date: 10-Jul-2023
  • (2023)Comparative Study on Fuchsia and Linux Device Driver ArchitectureProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577828(1305-1308)Online publication date: 27-Mar-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
EuroSys '09: Proceedings of the 4th ACM European conference on Computer systems
April 2009
342 pages
ISBN:9781605584829
DOI:10.1145/1519065
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: 01 April 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. concurrent programming
  2. device drivers
  3. domain-specific languages
  4. fault avoidance
  5. reliability

Qualifiers

  • Research-article

Conference

EuroSys '09
Sponsor:
EuroSys '09: Fourth EuroSys Conference 2009
April 1 - 3, 2009
Nuremberg, Germany

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25
Twentieth European Conference on Computer Systems
March 30 - April 3, 2025
Rotterdam , Netherlands

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)28
  • Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2023)Why write address translation OS code yourself when you can synthesize it?Proceedings of the 19th Workshop on Hot Topics in Operating Systems10.1145/3593856.3595895(174-180)Online publication date: 22-Jun-2023
  • (2023)Sfitag: Efficient Software Fault Isolation with Memory Tagging for ARM Kernel ExtensionsProceedings of the 2023 ACM Asia Conference on Computer and Communications Security10.1145/3579856.3590341(469-480)Online publication date: 10-Jul-2023
  • (2023)Comparative Study on Fuchsia and Linux Device Driver ArchitectureProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577828(1305-1308)Online publication date: 27-Mar-2023
  • (2022)Hybrid Static-Dynamic Analysis of Data Races Caused by Inconsistent Locking Discipline in Device DriversIEEE Transactions on Software Engineering10.1109/TSE.2021.3138735(1-1)Online publication date: 2022
  • (2022)As Code Testing: Characterizing Test Quality in Open Source Ansible Development2022 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST53961.2022.00031(208-219)Online publication date: Apr-2022
  • (2021)Declarative Power SequencingACM Transactions on Embedded Computing Systems10.1145/347703920:5s(1-21)Online publication date: 22-Sep-2021
  • (2021)Research on reliability and real-time of on-board computer based on RT-Linux2021 IEEE 5th Information Technology,Networking,Electronic and Automation Control Conference (ITNEC)10.1109/ITNEC52019.2021.9587066(499-503)Online publication date: 15-Oct-2021
  • (2020)NetTLPProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388253(141-156)Online publication date: 25-Feb-2020
  • (2019)An Empirical Study of Fault Triggers in the Linux Operating System: An Evolutionary PerspectiveIEEE Transactions on Reliability10.1109/TR.2019.291620468:4(1356-1383)Online publication date: Dec-2019
  • (2019)Sytare: a Lightweight Kernel for NVRAM-Based Transiently-Powered SystemsIEEE Transactions on Computers10.1109/TC.2018.2889080(1-1)Online publication date: 2019
  • Show More Cited By

View Options

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