Article

Understanding collateral evolution in Linux device drivers

Authors:

Yoann Padioleau,

Julia L. Lawall,

Gilles MullerAuthors Info & Claims

EuroSys '06: Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006

Pages 59 - 71

https://doi.org/10.1145/1217935.1217942

Published: 18 April 2006 Publication History

Abstract

In a modern operating system (OS), device drivers can make up over 70% of the source code. Driver code is also heavily dependent on the rest of the OS, for functions and data structures defined in the kernel and driver support libraries. These properties pose a significant problem for OS evolution, as any changes in the interfaces exported by the kernel and driver support libraries can trigger a large number of adjustments in dependent drivers. These adjustments, which we refer to as collateral evolutions, may be complex, entailing substantial code reorganizations. As to our knowledge there exist no tools to help in this process, collateral evolution is thus time consuming and error prone.In this paper, we present a qualitative and quantitative assessment of collateral evolution in Linux device driver code. We provide a taxonomy of evolutions and collateral evolutions, and use an automated patch-analysis tool that we have developed to measure the number of evolutions and collateral evolutions that affect device drivers between Linux versions 2.2 and 2.6. In particular, we find that from one version of Linux to the next, collateral evolutions can account for up to 35% of the lines modified in such code.

References

[1]

J. Appavoo, M. Auslander, M. Burtico, D. D. Silva, O. Krieger, M. Mergen, M. Ostrowski, B. Rosenburg, R. W. Wisniewski, and J. Xenidis. K42: an open-source Linux-compatible scalable operating system kernel. IBM Systems Journal, 44(2):427--440, 2005.]]

Digital Library

[2]

T. Ball, E. Bounimova, B. Cook, V. Levin, J. Lichtenberg, C. McGarvey, B. Ondrusek, S. K. Rajamani, and A. Ustuner. Thorough static analysis of device drivers. In The first ACM SIGOPS EuroSys conference (EuroSys 2006), Leuven, Belgium, Apr. 2006. To appear.]]

Digital Library

[3]

A. Chou, J. Yang, B. Chelf, S. Hallem, and D. Engler. An empirical study of operating systems errors. In SOSP'01 {21}, pages 73--88.]]

Digital Library

[4]

A. C. de Melo, D. Jones, and J. Garzik, 2001. http://umeet.uninet.edu/umeet2001/talk/15--12--2001/arnaldo-talk.html.]]

[5]

D. R. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the Fourth USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 1--16, San Diego, CA, Oct. 2000.]]

Digital Library

[6]

D. R. Engler, D. Y. Chen, A. Chou, and B. Chelf. Bugs as deviant behavior: A general approach to inferring errors in systems code. In SOSP'01 {21}, pages 57--72.]]

Digital Library

[7]

J.-P. Fassino, J.-B. Stefani, J. Lawall, and G. Muller. THINK: A software framework for component-based operating system kernels. In 2000 USENIX Annual Technical Conference, pages 73--86, Monterey, CA, June 2002.]]

Digital Library

[8]

B. Ford, G. Back, G. Benson, J. Lepreau, A. Lin, and O. Shivers. The Flux OSKit: A substrate for kernel and language research. In Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP'97), pages 38--51, Saint-Malo, France, Oct. 1997.]]

Digital Library

[9]

J. S. Foster, T. Terauchi, and A. Aiken. Flow-sensitive type qualifiers. In Proceedings of the 2002 ACM SIGPLAN conference on Programming Language Design and Implementation, pages 38--51, Berlin, Germany, June 2002.]]

Digital Library

[10]

M. Fowler, K. Beck, J. Brant, W. Opdyke, and D. Roberts. Refactoring: Improving the Design of Existing Code. Addison-Wesley Professional, 1999.]]

Digital Library

[11]

M. W. Godfrey and Q. Tu. Evolution in open source software: A case study. In International Conference on Software Maintenance (ICSM'00), pages 131--142, San Jose, CA, 2000. IEEE.]]

Digital Library

[12]

A. E. Hassan. Mining Software Repositories to Assist Developers and Support Managers. PhD thesis, School of Computer Science, Faculty of Mathematics, University of Waterloo, Ontario, Canada, 2004.]]

Digital Library

[13]

C. Hellwig, 2003. http://www.cs.helsinki.fi/linux/linux- kernel/2003--20/1120.html.]]

[14]

P. Koellner, Feb. 2002. http://www.uwsg.iu.edu/hypermail/linux/kernel/0202.2/0106.html.]]

[15]

J. LeVasseur, V. Uhlig, J. Stoess, and S. Götz. Unmodified device driver reuse and improved system dependability via virtual machines. In OSDI'04 {19}, pages 17--30.]]

Digital Library

[16]

Z. Li, S. Lu, S. Myagmar, and Y. Zhou. CP-Miner: A tool for finding copy-paste and related bugs in operating system code. In OSDI'04 {19}, pages 289--302.]]

Digital Library

[17]

LWN. API changes in the 2.6 kernel series, Oct. 2005. http://lwn.net/Articles/2.6-kernel-api/.]]

[18]

D. S. Miller, Feb. 2002. http://www.ussg.iu.edu/hypermail/linux/kernel/0202.1/0855.html.]]

[19]

Proceedings of the Sixth USENIX Symposium on Operating Systems Design and Implementation (OSDI), San Fransisco, CA, Dec. 2004.]]

[20]

A. Rubini and J. Corbet. Linux Device Drivers, 2nd Edition. O'Reilly, June 2001.]]

Digital Library

[21]

Proceedings of the 18th ACM Symposium on Operating System Principles, Banff, Canada, Oct. 2001.]]

[22]

M. M. Swift, M. Annamalai, B. N. Bershad, and H. M. Levy. Recovering device drivers. In OSDI'04 {19}, pages 1--16.]]

Digital Library

[23]

M. M. Swift, B. N. Bershad, and H. M. Levy. Improving the reliability of commodity operating systems. ACM Transactions on Computer Systems, 23(1):77--110, Feb. 2005.]]

Digital Library

[24]

D. Wambolt, Dec. 2001. http://seclists.org/lists/linux-kernel/2001/Dec/2027.html.]]

[25]

J. Weber, Feb. 2002. http://www.ussg.iu.edu/hypermail/linux/kernel/0202.1/0697.html.]]

Cited By

Gopinath RNemati HZeller A(2021)Input Algebras2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)10.1109/ICSE43902.2021.00070(699-710)Online publication date: May-2021
https://doi.org/10.1109/ICSE43902.2021.00070
Serrano LNguyen VThung FJiang LLo DLawall JMuller GGavrilovska AZadok E(2020)SPINFERProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489162(235-248)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489162
Mooij AKetema JKlusener SSchuts M(2020)Reducing Code Complexity through Code Refactoring and Model-Based Rejuvenation2020 IEEE 27th International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER48275.2020.9054823(617-621)Online publication date: Feb-2020
https://doi.org/10.1109/SANER48275.2020.9054823
Show More Cited By

Index Terms

Understanding collateral evolution in Linux device drivers

Recommendations

Understanding collateral evolution in Linux device drivers
Proceedings of the 2006 EuroSys conference

In a modern operating system (OS), device drivers can make up over 70% of the source code. Driver code is also heavily dependent on the rest of the OS, for functions and data structures defined in the kernel and driver support libraries. These ...
Documenting and automating collateral evolutions in linux device drivers
EuroSys '08

The internal libraries of Linux are evolving rapidly, to address new requirements and improve performance. These evolutions, however, entail a massive problem of collateral evolution in Linux device drivers: for every change that affects an API, all ...
Semantic patches for documenting and automating collateral evolutions in Linux device drivers
PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems: linguistic support for modern operating systems

Developing and maintaining drivers is known to be one of the major challenges in creating a general-purpose, practically-useful operating system [1, 3]. In the case of Linux, device drivers make up, by far, the largest part of the kernel source code, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '06: Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006

April 2006

420 pages

ISBN:1595933220

DOI:10.1145/1217935

Conference Chair:
Yolande Berbers
K. U. Leuven, Belgium
,
Program Chair:
Willy Zwaenepoel
EPFL

ACM SIGOPS Operating Systems Review Volume 40, Issue 4
Proceedings of the 2006 EuroSys conference
October 2006
383 pages
ISSN:0163-5980
DOI:10.1145/1218063
Issue’s Table of Contents

Copyright © 2006 Authors.

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 April 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

EUROSYS06

Sponsor:

SIGOPS

EUROSYS06: Eurosys 2006 Conference

April 18 - 21, 2006

Leuven, Belgium

Acceptance Rates

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

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
1,021
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)2

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gopinath RNemati HZeller A(2021)Input Algebras2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE)10.1109/ICSE43902.2021.00070(699-710)Online publication date: May-2021
https://doi.org/10.1109/ICSE43902.2021.00070
Serrano LNguyen VThung FJiang LLo DLawall JMuller GGavrilovska AZadok E(2020)SPINFERProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489162(235-248)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489162
Mooij AKetema JKlusener SSchuts M(2020)Reducing Code Complexity through Code Refactoring and Model-Based Rejuvenation2020 IEEE 27th International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER48275.2020.9054823(617-621)Online publication date: Feb-2020
https://doi.org/10.1109/SANER48275.2020.9054823
Guo LZhai SQiao YLin FDan TDahlia M(2019)TranskernelProceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference10.5555/3358807.3358865(675-691)Online publication date: 10-Jul-2019
https://dl.acm.org/doi/10.5555/3358807.3358865
Xu SDong ZMeng NGuéhéneuc YKhomh FSarro F(2019)MeditorProceedings of the 27th International Conference on Program Comprehension10.1109/ICPC.2019.00052(335-346)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICPC.2019.00052
Kim MMeng NZhang T(2019)Software EvolutionHandbook of Software Engineering10.1007/978-3-030-00262-6_6(223-284)Online publication date: 12-Feb-2019
https://doi.org/10.1007/978-3-030-00262-6_6
Li DLi LKim DBissyandé TLo DLe Traon Y(2019)Watch out for this commit! A study of influential software changesJournal of Software: Evolution and Process10.1002/smr.218131:12Online publication date: 12-Dec-2019
https://dl.acm.org/doi/10.1002/smr.2181
Zhen YZhang WDai ZMao JChen Y(2018)Is It Possible to Automatically Port Kernel Modules?Proceedings of the 9th Asia-Pacific Workshop on Systems10.1145/3265723.3265732(1-8)Online publication date: 27-Aug-2018
https://dl.acm.org/doi/10.1145/3265723.3265732
Garcia JHammad MMalek S(2018)Lightweight, Obfuscation-Resilient Detection and Family Identification of Android MalwareACM Transactions on Software Engineering and Methodology10.1145/316262526:3(1-29)Online publication date: 12-Jan-2018
https://dl.acm.org/doi/10.1145/3162625
Abal IMelo JStănciulescu ŞBrabrand CRibeiro MWąsowski A(2018)Variability Bugs in Highly Configurable SystemsACM Transactions on Software Engineering and Methodology10.1145/314911926:3(1-34)Online publication date: 12-Jan-2018
https://dl.acm.org/doi/10.1145/3149119
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents