The impact of generic data structures: decoding the role of lists in the linux kernel
Abstract
The increasing adoption of the Linux kernel has been sustained by a large and constant maintenance effort, performed by a wide and heterogeneous base of contributors. One important problem that maintainers face in any code base is the rapid understanding of complex data structures. The Linux kernel is written in the C language, which enables the definition of arbitrarily uninformative datatypes, via the use of casts and pointer arithmetic, of which doubly linked lists are a prominent example. In this paper, we explore the advantages and disadvantages of such lists, for expressivity, for code understanding, and for code reliability. Based on our observations, we have developed a toolset that includes inference of descriptive list types and a tool for list visualization. Our tools identify more than 10,000 list fields and variables in recent Linux kernel releases and succeeds in typing 90%. We show how these tools could have been used to detect previously fixed bugs and identify 6 new ones.
References
[1]
Robert Dyer, Hridesh Rajan, Hoan Anh Nguyen, and Tien N. Nguyen. 2014. Mining billions of AST nodes to study actual and potential usage of Java language features. In ICSE. 779--790.
[2]
Dawson R. Engler, David Yu Chen, and Andy Chou. 2001. Bugs as deviant behavior: A general approach to inferring errors in systems code. In SOSP. 57--72.
[3]
Jeffrey S Foster, Manuel Fähndrich, and Alexander Aiken. 1999. A theory of type qualifiers. In ACM SIGPLAN Conference on Programming Language Design and Implementation. 192--203.
[4]
M. Fowler. 1999. Refactoring-Improving the Design of Existing Code. Addison-Wesley.
[5]
Robert M. Fuhrer, Frank Tip, Adam Kiezun, Julian Dolby, and Markus Keller. 2005. Efficiently refactoring Java applications to use generic libraries. In ECOOP. 71--96.
[6]
Wei Huang, Werner Dietl, Ana Milanova, and Michael D Ernst. 2012. Inference and checking of object ownership. In European Conference on Object-Oriented Programming. Springer, 181--206.
[7]
Ted Kremenek, Paul Twohey, Godmar Back, Andrew Y. Ng, and Dawson R. Engler. 2006. From uncertainty to belief: Inferring the specification within. In OSDI. 161--176.
[8]
Julia Lawall and Gilles Muller. 2018. Coccinelle: 10 years of automated evolution in the Linux kernel. In USENIX ATC. 601--614.
[9]
Julia Lawall, Derek Palinski, Lukas Gnirke, and Gilles Muller. 2017. Fast and precise retrieval of forward and back porting information for Linux device drivers. In USENIX ATC. 15--26.
[10]
Julia L. Lawall and David Lo. 2010. An automated approach for finding variable-constant pairing bugs. In ASE. 103--112.
[11]
Zhenmin Li and Yuanyuan Zhou. 2013. PR-Miner: automatically extracting implicit programming rules and detecting violations in large software code. In ESEC/FSE. 306--315.
[12]
Shan Lu, Soyeon Park, Chongfeng Hu, Xiao Ma, Weihang Jiang, Zhenmin Li, Raluca A. Popa, and Yuanyuan Zhou. 2007. MUVI: Automatically inferring multi-variable access correlations and detecting related semantic and concurrency bugs. In SOSP. 103--116.
[13]
Robert O'Callahan and Daniel Jackson. 1997. Lackwit: A program understanding tool based on type inference. In Proceedings of the (19th) International Conference on Software Engineering. IEEE Computer Society, 338--348.
[14]
Yoann Padioleau, Julia L. Lawall, René Rydhof Hansen, and Gilles Muller. 2008. Documenting and automating collateral evolutions in Linux device drivers. In EuroSys. 247--260.
[15]
Matthew M Papi, Mahmood Ali, Telmo Luis Correa Jr, Jeff H Perkins, and Michael D Ernst. 2008. Practical pluggable types for Java. In Proceedings of the 2008 international symposium on Software testing and analysis. 201--212.
[16]
Chris Parnin, Christian Bird, and Emerson R. Murphy-Hill. 2011. Java generics adoption: how new features are introduced, championed, or ignored. In MSR. 3--12.
[17]
Suman Saha, Jean-Pierre Lozi, Gaël Thomas, Julia L. Lawall, and Gilles Muller. 2013. Hector: Detecting resource-release omission faults in error-handling code for systems software. In DSN. 1--12.
[18]
Umesh Shankar, Kunal Talwar, Jeffrey S Foster, and David A Wagner. 2001. Detecting format string vulnerabilities with type qualifiers. In USENIX Security Symposium. 201--220.
[19]
Bjarne Stroustrup. 1989. Parameterized Types for C++. J. Object Oriented Program. 1, 5 (Jan. 1989), 5--16.
[20]
Mohsen Vakilian, Amarin Phaosawasdi, Michael D Ernst, and Ralph E Johnson. 2015. Cascade: A universal programmer-assisted type qualifier inference tool. In 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, Vol. 1. IEEE, 234--245.
[21]
Nic Volanschi and Julia Lawall. 2020. Supplementary material as Git repository. https://gitlab.inria.fr/lawall/liliput/. [Online; accessed 28-August-2020].
[22]
Nic Volanschi and Julia Lawall. 2020. Supplementary material as Software Heritage permalink (specific version for reproducibility purposes). https://archive.softwareheritage.org/swh:1:rev:a303a19397a995a2bc4d8a2a2156f7409c39afef;origin=https://gitlab.inria.fr/lawall/liliput.git. [Online; accessed 28-August-2020].
[23]
Alexander von Rhein, Jörg Liebig, Andreas Janker, Christian Kästner, and Sven Apel. 2018. Variability-Aware Static Analysis at Scale: An Empirical Study. ACM Transactions on Software Engineering and Methodology 27, 4 (2018), Article No. 18.
[24]
Konstantin Weitz, Gene Kim, Siwakorn Srisakaokul, and Michael D Ernst. 2014. A type system for format strings. In Proceedings of the 2014 International Symposium on Software Testing and Analysis. 127--137.
Index Terms
- The impact of generic data structures: decoding the role of lists in the linux kernel
Recommendations
ECMO: Peripheral Transplantation to Rehost Embedded Linux Kernels
CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications SecurityDynamic analysis based on the full-system emulator QEMU is widely used for various purposes.However, it is challenging to run firmware images of embedded devices in QEMU, especially the process to boot the Linux kernel (we call this process rehosting ...
Adding wildcards to the Java programming language
SAC '04: Proceedings of the 2004 ACM symposium on Applied computingThis paper describes wildcards, a new language construct designed to increase the flexibility of object-oriented type systems with parameterized classes. Based on the notion of use-site variance, wildcards provide a type safe abstraction over different ...
On the Semantics of “Data Type”
This paper considers the general problem of specifying the meaning of programming languages that include “data type definition facilities.” The fundamental question posed in attempting to define such languages is: “what meaning should be given to a data ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2020
1449 pages
ISBN:9781450367684
DOI:10.1145/3324884
- General Chair:
- John Grundy,
- Program Chairs:
- Claire Le Goues,
- David Lo
Copyright © 2020 ACM.
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
In-Cooperation
- IEEE CS
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 January 2021
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
ASE '20: 35th IEEE/ACM International Conference on Automated Software Engineering
December 21 - 25, 2020
Virtual Event, Australia
Acceptance Rates
Overall Acceptance Rate 82 of 337 submissions, 24%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 108Total Downloads
- Downloads (Last 12 months)11
- Downloads (Last 6 weeks)2
Reflects downloads up to 13 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in