Analysis of the Linux Kernel Evolution
Using Code Clone Coverage
Simone Livieri
Yoshiki Higo
Makoto Matsushita
Katsuro Inoue

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Code clone?

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Code Clone?
A code clone is a set of identical or similarfragments of code

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Code Clone Detection
Various detection methods
Token basedAbstract Syntax Tree basedProgram Dependence Graphbased...

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

CCFinderToken-based code-clone detection toolInsensitive to renamed variable and code layout

Multi language support (C, C++, COBOL, Java, ...)

Very good scalability and speed...

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

CCFinderToken-based code-clone detection toolInsensitive to renamed variable and code layout

Multi language support (C, C++, COBOL, Java, ...)

Very good scalability and speed...
...but scalability is limited by thehardware used
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

D-CCFinder

A system for distributed code cloneanalysis
Uses CCFinder as code clone detector

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

What?

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

What

Start a large scale study of asoftware system's evolution usingcode clone analysis

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Why?

Department of Computer Science, Graduate School of Information Science and Technology, Osaka UniversityWhyThe evolution of a software system can bereconstructed with code clone analysis
No large scale study have been performed yet
D-CCFinder permits large scale code cloneanalysis

Department of Computer Science, Graduate School of Information Science and Technology, Osaka UniversityWhy

The evolution of a software system can bereconstructed with code clone analysis
No large scale study have been performed yet
D-CCFinder permits large scale code clone
analysis
There were two weeks left before the deadline
and we had nothing to do
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

The guinea pig

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

The Linux Kernel

15 years long development effort involving hundredsof developers
Two development branches: stable and unstable(prior to version 2.6)
The source code size grew from 3.8Mbytes (version1.0) to 157Mbytes (2.6.18.3)

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

The Linux Kernel
Version1.0
1.2.0~
1.2.132.0.0~
2.0.402.2.0~
2.2.262.4.0~
2.4.33.4
2.6.0~
2.6.18.3

LOC Size (Kbytes) # of versions
141K
3,926
1
234K
6,534
14
238K
6,596
563K
16,07641
768K
21,952
1,310K
37,05627
1,970K58,812
2,366K
69,20034
3,865K112,148
4,120K
120,030
195,476K
157,290

Total number of versions
Number of .c files
Total lines of code
Total size

136
376,596
266,943,565
7.4 Gbytes



136 kernel versions
from the stablebranchesConsidered only .c files

Size measured with du

LOC counted with wc

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

How?

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

HowFor each pair (A, B) of kernel versions we computedand plotted the code clone coverage
Loc CC  A , B
Coverage A , B=Loc  ALoc B

CC(A,B)= code clone fragments between
A and B
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Results

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Results

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Results
Max coverage: 67%
Highest coverage onthe diagonal (asexpected)

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Results

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Results

2.0

Same pattern
Code “back-ported” fromthe development branches

2.2

2.4

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Results

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

ResultsDifferent patterns due todifferent development
processes
2.4

2.6

Department of Computer Science, Graduate School of Information Science and Technology, Osaka University

Conclusion & FutureConclusion

Presented a tentative study of the evolution of the Linuxkernel computing and visualizing the code-clone coverage
metricFuture
Elaborate and complete the analysis presented andproduce a more detailed report of the code changes

以上
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University