Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 8

Proceedings of the 2016 Federated Conference on Computer Science and Information Systems

Managing Big Clones to Ease Evolution: Linux Kernel Example

, ,

DOI: http://dx.doi.org/10.15439/2016F173

Citation: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 8, pages 17271736 ()

Full text

Abstract. Successful software is often enhanced and adapted to the needs of new users. During evolution, a software system grows in size, becomes more complex, and costly to maintain. In this paper, we point to big clones---large granular duplicated program structures such as files or directories---as one of many reasons why this happens. Using the Linux kernel as an example, we show that big clones arise in the Linux kernel despite careful architecture design and a systematic approach for managing variability. We propose a solution to avoid these big clones by representing them as generalized templates in ART (Adaptive Reuse Technique). ART templates are constructed on top of the Linux code, without conflicts with the state-of-art techniques and tools used to manage the Linux kernel. Benefits include simplification of the Linux kernel due to non-redundancy, easier comprehension, and traceability of the change impact during evolution. The proposed technique is general and the Linux example discussed in this paper also illustrates general phenomena.


  1. P. Clements and D. Muthig, (Editors) Proceedings Workshop on Variability Management–Working with Variation mechanisms, in SPLC, 2006, IESE-Report No 152.06/E Version 1.0, Germany, October 15, 2006
  2. C. L. Goues, S. Forrest, and W. Weimer, "The case for software evolution," in FoSER, 2010, pp. 205–210, http://dx.doi.org/10.1145/1882362.1882406
  3. R. Koschke, "Identifying and removing software clones", in Software Evolution, Springer Berlin Heidelberg, 2008, pp. 15–36, http://dx.doi.org/10.1007/978-3-540-76440-3_2
  4. P. Clements and L. Northrop, Software product lines: practices and patterns. Addition-Wesley, 2002
  5. C. Kapser and M. W. Godfrey, ""Cloning considered harmful" considered harmful," in WCRE, 2006, pp. 19–28, http://dx.doi.org/10.1007/s10664-008-9076-6
  6. G. P. Krishnan and N. Tsantalis, "Unification and refactoring of clones," in CSMR-WCRE, 2014, pp. 104–113, http://dx.doi.org/10.1109/CSMR-WCRE.2014.6747160
  7. S. Jarzabek and L. Shubiao, "Eliminating redundancies with a "composition with adaptation" meta-programming technique," in ESEC/FSE, 2003, pp. 237–246, http://dx.doi.org/10.1145/949952.940104
  8. S. Schulze, S. Apel, and C. Kästner, "Code clones in feature-oriented software product lines," in GPCE, 2010, pp. 103–112, http://dx.doi.org/10.1145/1942788.1868310
  9. R. Koschke, "Frontiers of software clone management," in FoSM, 2008, pp. 119–128, http://dx.doi.org/10.1109/FOSM.2008.4659255
  10. Y. Dubinsky, J. Rubin, T. Berger, S. Duszynski, M. Becker, and K. Czarnecki, "An exploratory study of cloning in industrial software product lines," in CSMR, 2013, pp. 25–34, http://dx.doi.org/10.1109/CSMR.2013.13
  11. R. Lotufo, S. She, T. Berger, K. Czarnecki, and A. Wąsowski, "Evolution of the Linux kernel variability model," in SPLC, 2010, pp. 136–150, http://dx.doi.org/10.1007/978-3-642-15579-6_10
  12. R. Garcia, J. Jarvi, A. Lumsdaine, J. G. Siek, and J. Willcock, "A comparative study of language support for generic programming," in OOPSLA, 2003, pp. 115–134, http://dx.doi.org/10.1145/949305.949317
  13. S. Jarzabek, P. Bassett, H. Zhang, and W. Zhang, "XVCL: XML-based variant configuration language", in ICSE, 2003, pp. 810–811, http://dx.doi.org/10.1109/ICSE.2003.1201298
  14. P. Ye, X. Peng, Y. Xue, and S. Jarzabek, "A case study of variation mechanism in an industrial product line," in ICSR, 2009, pp. 126–136, http://dx.doi.org/10.1007/978-3-642-04211-9_13
  15. A. Kadav and M. M. Swift, “Understanding modern device drivers,” in ASPLOS, 2012, pp. 87–98, http://dx.doi.org/10.1145/2150976. 2150987
  16. C. Kapser and M. W. Godfrey, “Toward a taxonomy of clones in source code: A case study,” in ELISA, 2003, pp. 67–78
  17. G. Casazza, G. Antoniol, U. Villano, E. Merlo, and M. Di Penta, “Identifying clones in the Linux kernel,” in SCAM, 2001, pp. 90–97, http://dx.doi.org/10.1109/SCAM.2001.972670
  18. H. A. Basit and S. Jarzabek, "A data mining approach for detecting higher-level clones in software," IEEE Trans. Softw. Eng., vol. 35, no. 4, pp. 497–514, 2009, http://dx.doi.org/10.1109/TSE.2009.16
  19. U. Pettersson and S. Jarzabek, "Industrial experience with building a web portal product line using a lightweight, reactive approach," in ESEC/FSE, 2005, pp. 326–335, http://dx.doi.org/10.1145/1081706.1081758
  20. S. Jarzabek, U. Pettersson, and H. Zhang, "University-industry collaboration journey towards product lines," in ICSR, 2011, pp. 223–237, http://dx.doi.org/10.1007/978-3-642-21347-2_17
  21. S. Livieri, Y. Higo, M. Matsushita, K. Inoue, "Analysis of the Linux kernel evolution using code clone coverage," in MSR, 2007, pp. 22, http://dx.doi.org/10.1109/MSR.2007.1
  22. F. P. Brooks, Jr., "No silver bullet essence and accidents of software engineering," IEEE Computer, vol. 20, no. 4, pp. 10–19, 1987, http://dx.doi.org/10.1109/MC.1987.1663532
  23. M. Kim, V. Sazawal, D. Notkin, and G. Murphy, "An empirical study of code clone genealogies," in ESEC/FSE, 2005, pp. 187–196, http://dx.doi.org/10.1145/1081706.1081737
  24. W. Wei and M. W. Godfrey, "A study of cloning in the Linux SCSI drivers," in SCAM, 2011, pp. 95–104, http://dx.doi.org/10.1109/SCAM.2011.17
  25. J. A. Goguen, "Parameterized programming," IEEE Trans. Softw. Eng., vol. SE-10, no. 5, pp. 528–543, 1984, http://dx.doi.org/10.1109/TSE.1984.5010277
  26. D. R. Musser, G. J. Derge, and A. Saini, STL tutorial and reference guide: C++ programming with the standard template library. Addison-Wesley Professional, 2009
  27. T. Mende, R. Koschke, and F. Beckwermert, "An evaluation of code similarity identification for the grow-and-prune model,” J. of Soft. Maint. & Evol., vol. 21, no. 2, pp. 143–169, 2009, http://dx.doi.org/10.1002/smr.402
  28. P. Frenzel, R. Koschke, A. P. J. Breu, and K. Angstmann, "Extending the reflexion method for consolidating software variants into product lines,” in WCRE, 2007, pp. 160–169, http://dx.doi.org/10.1109/WCRE.2007.28
  29. E. W. Dijkstra, "On the role of scientific thought," in Selected Writings on Computing: A Personal Perspective, ed: Springer, 1982, pp. 60–66, http://dx.doi.org/10.1007/978-1-4612-5695-3_12
  30. G. Kiczales, J. Lamping, A. Mendhekar, C. Maeda, C. V. Lopes, J. M. Loingtier, and J. Irwin, "Aspect-oriented programming," in ECOOP, 1997, pp. 220–242, http://dx.doi.org/10.1007/BFb0053381
  31. P. Tarr, H. Ossher, W. Harrison, and S. Sutton, "N degrees of separation: multi-dimensional separation of concerns," in ICSE, 1999, pp. 107–119, http://dx.doi.org/10.1145/302405.302457
  32. D. Batory, J. N. Sarvela, and A. Rauschmayer, "Scaling step-wise refinement," IEEE Trans. Soft. Eng., vol.30, no. 6, pp. 355–371, 2004, http://dx.doi.org/10.1109/TSE.2004.23
  33. C. Kästner, S. Apel, and M. Kuhlemann, "Granularity in software product lines," in ICSE, 2008, pp. 311–320, http://dx.doi.org/10.1145/1368088.1368131
  34. C. Kästner, S. Apel, and D. Batory, “A case study implementing features using AspectJ,” in SPLC, 2007, pp. 223–232, http://dx.doi.org/10.1109/SPLC.2007.5
  35. E. Walkingshaw, C. Kästner, M. Erwig, S. Apel, and E. Bodden, “Variational data structures: exploring tradeoffs in computing with variability,” in ONWARD!, 2014, pp. 213–226, http://dx.doi.org/10.1145/2661136.2661143
  36. H. A. Basit, U. Ali, S. Haque, and S. Jarzabek, "Things structural clones tell that simple clones don't," in ICSM, 2012, pp. 275–284, http://dx.doi.org/10.1109/ICSM.2012.6405283