research-article

Efficient extraction and analysis of preprocessor-based variability

Authors:

Reinhard Tartler,

Daniel Lohmann,

Wolfgang Schröder-PreikschatAuthors Info & Claims

ACM SIGPLAN Notices, Volume 46, Issue 2

Pages 33 - 42

https://doi.org/10.1145/1942788.1868300

Published: 10 October 2010 Publication History

Abstract

The C Preprocessor (CPP) is the tool of choice for the implementation of variability in many large-scale configurable software projects. Linux, probably the most-configurable piece of software ever, employs more than 10,000 preprocessor variables for this purpose. However, this de-facto variability tends to be "hidden in the code"; which on the long term leads to variability defects, such as dead code or inconsistencies with respect to the intended (modeled) variability of the software. This calls for tool support for the efficient extraction of (and reasoning over) CPP-based variability.

We suggest a novel approach to extract CPP-based variability. Our tool transforms CPP-based variability in O(n) complexity into a propositional formula that "mimics" all valid effects of conditional compilation and can be analyzed with standard SAT or BDD packages.

Our evaluation results demonstrate the scalability and practicability of the approach. A dead-block-analysis on the complete Linux source tree takes less than 30 minutes; we thereby have revealed 60 dead blocks, 2 of which meanwhile have been confirmed as new (and long-lasting) bugs; the rest is still under investigation.

References

[1]

}}Greg J Badros and David Notkin. A framework for preprocessor-aware c source code analyses. Software: Practice and Experience, 30(8):907--924, 2000.

Digital Library

[2]

}}Ira D. Baxter. DMS: program transformations for practical scalable software evolution. In 5th Int. W'shop on Principles of Software Evolution (IWPSE’02), pages 48--51, New York, NY, USA, 2002. ACM.

Digital Library

[3]

}}Ira D. Baxter and Michael Mehlich. Preprocessor conditional removal by simple partial evaluation. In 8th Conf. on Reverse Engineering (WCRE ’01), pages 281--, Washington, DC, USA, 2001. IEEE.

Digital Library

[4]

}}D. Benavides, A. Ruiz-Cortés, and P. Trinidad. Automated reasoning on feature models. In 17th Int. Conf. on Advanced Information Systems Engineering (CAISE '05), volume 3520, pages 491--503, Heidelberg, Germany, 2005. Springer.

Digital Library

[5]

}}BuDDy project. http://sourceforge.net/projects/buddy, 2009.

[6]

}}Andreas Classen, Arnaud Hubaux, and Patrick Heymans. A formal semantics for multi-level staged configuration. In 3th Int. W'shop on Variability Modelling of Software-intensive Systems (VAMOS '09), pages 51--60, 2009.

[7]

}}Krzysztof Czarnecki and Krzysztof Pietroszek. Verifying feature-based model templates against well-formedness OCL constraints. In 6th Int. Conf. on Generative Programming and Component Engineering (GPCE '06), pages 211--220, New York, NY, USA, 2006. ACM.

Digital Library

[8]

}}Krzysztof Czarnecki and Andrzej Wasowski. Feature diagrams and logics: There and back again. In 11th Software Product Line Conf. (SPLC '07), pages 23--34. IEEE, Sept. 2007.

Digital Library

[9]

}}Alejandra Garrido. Program refactoring in the presence of preprocessor directives. PhD thesis, University of Illinois at Urbana-Champaign, Champaign, IL, USA, 2005. Adviser-Johnson, Ralph.

Digital Library

[10]

}}Ying Hu, Ettore Merlo, Michel Dagenais, and Bruno Lagüe. C/C++ conditional compilation analysis using symbolic execution. In 16th IEEE Int. Conf. on Software Maintainance (ICSM’00), page 196, Washington, DC, USA, 2000. IEEE.

Digital Library

[11]

}}International Organization for Standardization. ISO/IEC 9899:TC2: Programming languages -- C. International Organization for Standardization, Geneva, Switzerland, 2005.

[12]

}}Neil D. Jones, Carsten K. Gomard, and Peter Sestoft. Partial evaluation and automatic program generation. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.

Digital Library

[13]

}}Christian Kastner, Sven Apel, and Martin Kuhlemann. Granularity in software product lines. In 30th Int. Conf. on Software Engineering (ICSE '08), pages 311--320, New York, NY, USA, 2008. ACM.

Digital Library

[14]

}}Christian Kastner, Sven Apel, Salvador Trujillo, Martin Kuhlemann, and Don Batory. Guaranteeing syntactic correctness for all product line variants: A language-independent approach. In Proceedings of the 47th International Conference Objects, Models, Components, Patterns (TOOLS EUROPE), volume 33 of Lecture Notes in Business Information Processing, pages 175--194. Springer Berlin Heidelberg, June 2009.

[15]

}}Mario Latendresse. Rewrite systems for symbolic evaluation of c-like preprocessing. In CSMR '04: Proceedings of the Eighth Euromicro Working Conference on Software Maintenance and Reengineering (CSMR'04), page 165, Washington, DC, USA, 2004. IEEE Computer Society.

Digital Library

[16]

}}Jörg Liebig, Sven Apel, Christian Lengauer, Christian Kastner, and Michael Schulze. An analysis of the variability in forty preprocessor-based software product lines. In 32nd Int. Conf. on Software Engineering (ICSE '10), New York, NY, USA, 2010. ACM.

Digital Library

[17]

}}The Limmat SAT solver. http://fmv.jku.at/limmat/, 2002.

[18]

}}Linus Torvalds. Sparse - a semantic parser for C. http://www.kernel.org/pub/software/devel/sparse/, 2003.

[19]

}}Roberto E. Lopez-Herrejon and Don Batory. A standard problem for evaluating product-line methodologies. In 3rd Int. Conf. on Generative and Component-Based Software Engineering (GCSE '01), volume 2186, pages 10--24, Heidelberg, Germany, 2001. Springer.

Digital Library

[20]

}}Marc'ılio Mendonça, Andrzej Wasowski, Krzysztof Czarnecki, and Donald D. Cowan. Efficient compilation techniques for large scale feature models. In 5th Int. Conf. on Generative Programming and Component Engineering (GPCE '08), pages 13--22, New York, NY, USA, 2008. ACM.

Digital Library

[21]

}}Andreas Metzger, Patrick Heymans, Klaus Pohl, Pierre-Yves Schobbens, and Germain Saval. Disambiguating the documentation of variability in software product lines. In 15th IEEE Int. Conf. on Requirements Engineering (RE'07), pages 243--253, Washington, DC, USA, 2007. IEEE Computer Society.

[22]

}}Steven She, Rafael Lotufo, Thorsten Berger, Andrzej Wasowski, and Krzysztof Czarnecki. The variability model of the linux kernel. In 4th Int. W'shop on Variability Modelling of Software-intensive Systems (VAMOS '10), Linz, Austria, January 2010.

[23]

}}Julio Sincero, Horst Schirmeier, Wolfgang Schröder-Preikschat, and Olaf Spinczyk. Is the linux kernel a software product line? In Frank van der Linden and Björn Lundell, editors, International Workshop on Open Source Software and Product Lines (SPLC-OSSPL 2007), Kyoto, Japan, 2007.

[24]

}}Julio Sincero and Wolfgang Schröder-Preikschat. The linux kernel configurator as a feature modeling tool. In Steffen Thiel and Klaus Pohl, editors, 12th Software Product Line Conf. (SPLC '08), Second Volume, pages 257--260. Lero Int. Science Centre, University of Limerick, Ireland, 2008.

[25]

}}Julio Sincero, Reinhard Tartler, and Daniel Lohmann. An algorithm for quantifying the program variability induced by conditional compilation. Technical Report CS-2010-02, University of Erlangen, Dept. of Computer Science, January 2010.

[26]

}}Henry Spencer and Gehoff Collyer. #ifdef considered harmful, or portability experience with C News. In 1992 USENIX ATC, Berkeley, CA, USA, June 1992. USENIX.

[27]

}}Reinhard Tartler, Julio Sincero, Wolfgang Schröder-Preikschat, and Daniel Lohmann. Dead or alive: Finding zombie features in the Linux kernel. In 1st W'shop on Feature-Oriented Software Development (FOSD '09), pages 81--86. ACM, 2009.

Digital Library

[28]

}}Sahil Thaker, Don Batory, David Kitchin, and William Cook. Safe composition of product lines. In 7th Int. Conf. on Generative Programming and Component Engineering (GPCE '07), pages 95--104, New York, NY, USA, 2007. ACM.

Digital Library

[29]

}}Thomas Thum, Don Batory, and Christian Kastner. Reasoning about edits to feature models. In 31st Int. Conf. on Software Engineering (ICSE '09), pages 254--264, Washington, DC, USA, 2009. IEEE.

Digital Library

Cited By

Mortara JCollet PMousavi MSchobbens P(2021)Capturing the diversity of analyses on the Linux kernel variabilityProceedings of the 25th ACM International Systems and Software Product Line Conference - Volume A10.1145/3461001.3471151(160-171)Online publication date: 6-Sep-2021
https://dl.acm.org/doi/10.1145/3461001.3471151
Kuo HWilliams DKoller RMohan SBilas AMagoutis KMarkatos EKostic DSeltzer M(2020)A Linux in unikernel clothingProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387526(1-15)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3342195.3387526
Krieter SKrüger JLeich T(2018)Don't Worry About itProceedings of the 12th International Workshop on Variability Modelling of Software-Intensive Systems10.1145/3168365.3170426(19-26)Online publication date: 7-Feb-2018
https://dl.acm.org/doi/10.1145/3168365.3170426
Show More Cited By

Index Terms

Efficient extraction and analysis of preprocessor-based variability
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Preprocessors

Recommendations

Efficient extraction and analysis of preprocessor-based variability
GPCE '10: Proceedings of the ninth international conference on Generative programming and component engineering

The C Preprocessor (CPP) is the tool of choice for the implementation of variability in many large-scale configurable software projects. Linux, probably the most-configurable piece of software ever, employs more than 10,000 preprocessor variables for ...
Variability-aware parsing in the presence of lexical macros and conditional compilation
OOPSLA '11

In many projects, lexical preprocessors are used to manage different variants of the project (using conditional compilation) and to define compile-time code transformations (using macros). Unfortunately, while being a simple way to implement variability,...
Variability-aware parsing in the presence of lexical macros and conditional compilation
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications

In many projects, lexical preprocessors are used to manage different variants of the project (using conditional compilation) and to define compile-time code transformations (using macros). Unfortunately, while being a simple way to implement variability,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 46, Issue 2

GPCE '10

Febuary 2011

185 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1942788

Issue’s Table of Contents

GPCE '10: Proceedings of the ninth international conference on Generative programming and component engineering
October 2010
198 pages
ISBN:9781450301541
DOI:10.1145/1868294
General Chair:
Eelco Visser
Delft University of Technology, The Netherlands
,
Program Chair:
Jaakko Järvi
Texas A&M University, USA

Copyright © 2010 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 October 2010

Published in SIGPLAN Volume 46, Issue 2

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
343
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mortara JCollet PMousavi MSchobbens P(2021)Capturing the diversity of analyses on the Linux kernel variabilityProceedings of the 25th ACM International Systems and Software Product Line Conference - Volume A10.1145/3461001.3471151(160-171)Online publication date: 6-Sep-2021
https://dl.acm.org/doi/10.1145/3461001.3471151
Kuo HWilliams DKoller RMohan SBilas AMagoutis KMarkatos EKostic DSeltzer M(2020)A Linux in unikernel clothingProceedings of the Fifteenth European Conference on Computer Systems10.1145/3342195.3387526(1-15)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1145/3342195.3387526
Krieter SKrüger JLeich T(2018)Don't Worry About itProceedings of the 12th International Workshop on Variability Modelling of Software-Intensive Systems10.1145/3168365.3170426(19-26)Online publication date: 7-Feb-2018
https://dl.acm.org/doi/10.1145/3168365.3170426
Dintzner NDeursen APinzger M(2017)Analysing the Linux kernel feature model changes using FMDiffSoftware and Systems Modeling (SoSyM)10.1007/s10270-015-0472-216:1(55-76)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10270-015-0472-2
Zhang BDuszynski SBecker M(2016)Variability mechanisms and lessons learned in practiceProceedings of the 1st International Workshop on Variability and Complexity in Software Design10.1145/2897045.2897048(14-20)Online publication date: 14-May-2016
https://dl.acm.org/doi/10.1145/2897045.2897048
Dintzner NVan Deursen APinzger MCollet PWąsowski AWeyer T(2014)Extracting feature model changes from the Linux kernel using FMDiffProceedings of the 8th International Workshop on Variability Modelling of Software-Intensive Systems10.1145/2556624.2556631(1-8)Online publication date: 22-Jan-2014
https://dl.acm.org/doi/10.1145/2556624.2556631
Zhang BBecker MPatzke TSierszecki KSavolainen JKishi TJarzabek SGnesi S(2013)Variability evolution and erosion in industrial product linesProceedings of the 17th International Software Product Line Conference10.1145/2491627.2491645(168-177)Online publication date: 26-Aug-2013
https://dl.acm.org/doi/10.1145/2491627.2491645
Zhang BBecker M(2012)Code-based variability model extraction for software product line improvementProceedings of the 16th International Software Product Line Conference - Volume 210.1145/2364412.2364428(91-98)Online publication date: 2-Sep-2012
https://dl.acm.org/doi/10.1145/2364412.2364428
Fernandez-Amoros DHeradio RHorcas Aguilera JGalindo JBenavides DFuentes L(2024)Pragmatic Random Sampling of the Linux Kernel: Enhancing the Randomness and Correctness of the conf ToolProceedings of the 28th ACM International Systems and Software Product Line Conference10.1145/3646548.3672586(24-35)Online publication date: 2-Sep-2024
https://dl.acm.org/doi/10.1145/3646548.3672586
Yıldıran NOh JLawall JGazzillo P(2024)Maximizing Patch Coverage for Testing of Highly-Configurable Software without Exploding Build TimesProceedings of the ACM on Software Engineering10.1145/36437461:FSE(427-449)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3643746
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 Issue’s Table of Contents