KernelGraph: Understanding the kernel in a graph

Abstract

The Linux kernel has grown to 20 million lines of code, which have been contributed by almost 14,000 programmers. The complexity of the Linux kernel challenges the kernel maintenance and makes comprehending the kernel more difficult for developers learning the kernel. Automated tool support is crucial for comprehending such a large-scale program involving a high volume of code. In this article, we present KernelGraph, which enhances understanding of the Linux kernel by providing a visual representation of kernel internals. KernelGraph resembles online map systems and facilitates kernel code navigation in an intuitive and interactive way. We describe the key techniques used in KernelGraph to process the vast amount of information in the kernel codebase quickly. We also implemented two applications built atop KernelGraph to enhance kernel comprehension. KernelGraph was presented to 30 participants, who were asked several questions about their kernel comprehension in a controlled study. Our experimental results show that, compared with other source code comprehension tools, KernelGraph improves kernel comprehension by enabling people to visually browse the kernel code and by providing an effective means for exploring the kernel structure. The ability to switch seamlessly between high-level views and source code significantly reduces the gap between source code and high-level mental representation. KernelGraph can be easily extended to support visualizations of other large-scale codebases.

Keywords

Linux kernel code visualization program comprehension

Get full access to this article

View all access options for this article.

References

Storey

MAD

Wong

Muller

. How do program understanding tools affect how programmers understand programs? In: Proceedings of the fourth working conference on reverse engineering (WCRE ’97), Amsterdam, 6–8 October 1997, pp. 183–207. New York: IEEE.

Klemola

Rilling

. Modeling comprehension processes in software development. In: Proceedings of the first IEEE international conference on cognitive informatics, Calgary, AB, Canada, 19–20 August 2002, pp. 329–336.New York: IEEE.

Hawes

Marshall

Anslow

. Codesurveyor: mapping large-scale software to aid in code comprehension. In: Proceedings of the IEEE 3rd working conference on software visualization (VISSOFT), Bremen, 27–28 September 2015, pp. 96–105. New York: IEEE.

Shneiderman

. Tree visualization with tree-maps: 2-d space-filling approach. ACM T Graphic 1992; 11(1): 92–99.

Shulyupin

. The interactive map of Linux kernel, http://www.makelinux.net/kernel_map (2007, accessed 20 April 2017).

Ball

Eick

. Software visualization in the large. Computer 1996; 29(4): 33–43.

Karahasanović

Levine

Thomas

. Comprehension strategies and difficulties in maintaining object-oriented systems: an explorative study. J Syst Software 2007; 80(9): 1541–1559.

Storey

MAD

Wong

Fracchia

, et al. On integrating visualization techniques for effective software exploration. In: Proceedings of the IEEE symposium on information visualization (InfoVis ’97), Phoenix, AZ, 21 October 1997, pp. 38–45. New York: IEEE.

Source Dynamics, Inc. Source insight, http://www.sourceinsight.com (2017, accessed 11 March 2017).

10.

Scientific Toolworks, Inc. Understand, http://scitools.com (1996, accessed 11 March 2017).

11.

Project

. Gcc, the GNU compiler collection, http://gcc.gnu.org (1987, accessed 25 March 2017).

12.

Poznyakoff

. GNU cflow, http://www.gnu.org/software/cflow (2011, accessed 25 March 2017).

13.

Lattner

. clang: a C language family frontend for LLVM, http://clang.llvm.org (2007, accessed 25 March 2017).

14.

Van Heesch

. Doxygen, http://www.doxygen.org (1997, accessed 20 April 2017).

15.

Buluc

Meyerhenke

Safro

, et al. Recent advances in graph partitioning. Algorithm Eng 2013; 9220: 117–158.

16.

Karypis

. METIS—serial graph partitioning and fill-reducing matrix ordering, http://glaros.dtc.umn.edu/gkhome/views/metis (2013, accessed 12 April 2017).

17.

Kernighan

Lin

. An efficient heuristic procedure for partitioning graphs. Bell Syst Tech J 1970; 49(2): 291–307.

18.

Hershberger

Maxel

Suri

. Finding the k shortest simple paths: a new algorithm and its implementation. ACM Trans Algorithm 2007; 3(4): 45–46.

19.

Dijkstra

. A note on two problems in connexion with graphs. New York: Springer-Verlag, 1959.

20.

Baidu, Inc. ECharts, http://echarts.baidu.com.cn (2016, accessed 20 April 2017).

21.

Mohanta

Poddar

. Comprehensive study on computational methods for k-shortest paths problem. Int J Comput Appl T 2012; 40(14): 22–26.

22.

Opdenacker

Petazzoni

. Free electrons, http://elixir.free-electrons.com/linux/v3.19/ident (2004, accessed 20 May 2017).

23.

Yin

Yuan

Zhou

, et al. How do fixes become bugs? In: Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering (Sigsoft/fse’11), Szeged, 5–9 September 2011, pp. 26–36. New York: IEEE.

24.

Torvalds

. Linux kernel archives, http://www.kernel.org (1991, accessed 20 April 2017).

25.

Fekete

Plaisant

. Interactive information visualization of a million items. In: Proceedings of the IEEE symposium on information visualization (InfoVis’02), Boston, MA, 28–29 October 2002, pp. 117–124. New York: IEEE.

26.

Russell

. Free Code Graphing Project, http://fcgp.sourceforge.net (2004, accessed 20 April 2017).

27.

Ferreira

Kästner

Pfeffer

, et al. Characterizing complexity of highly-configurable systems with variational call graphs: analyzing configuration options interactions complexity in function calls. In: Proceedings of the 2015 symposium and bootcamp on the science of security (HotSoS ’15), Urbana, IL, 21–22 April 2015, pp. 1–2. New York: ACM.

28.

Malik

Pfeffer

Ferreira

, et al. Visualizing the variational callgraph of the linux kernel: an approach for reasoning about dependencies [poster]. In: Proceedings of the symposium and bootcamp on the science of security (HotSos ’16), Pittsburgh, PA, pp. 93–94. New York: ACM.