英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
内核图:从图中理解内核
Jianjun Shi, Weixing Ji, Jingjing Zhang, Zhiwei Gao, Yizhuo Wang and Feng Shi
摘要
通过近14000名程序员的贡献，Linux内核已经增长到了200万行代码。Linux内核的复杂性给内核的维护带来了挑战，并使得学习Linux得开发者更加难以去理解。自动化工具的支持对于理解如此大规模且涉及大量代码的程序来说是至关重要的。在这篇文章中，我们提出了内核图，它可以通过提供一个对内核结构的可视化的表示，来提高对于Linux内核的理解。内核图看起来像在线地图系统，通过一种直观和交互式的方式促进内核代码的导航。我们可以说被用在内核图去处理内核代码库大量信息十分快速。我们同样在内核图的基础上实现了两个应用去提高对内核的理解。内核图被呈现给30个参与者，再对照研究中他们被问了许多关于内核理解的问题。我们的实验结果表明，与其它的源代码理解工具相比，内核图通过使得内核可视化以及提供一个有效的浏览内核结构的方式提升了对内核的理解。在高层次的视图和源代码之间无缝转换的能力显著减少了源代码和高层次心理表达之间的差距。内核图很容易扩展去支持其它大规模代码库的可视化。
关键词
Linux内核，代码可视化，程序理解
介绍
包含数十万行代码的大规模软件项目通常十分难以理解和维护。一些传统一同已经发展了几十年，变得极为复杂和庞大。这些系统已经被来自世界各地的数千名开发人员维护了数十年，而他们又具有不同的编程风格。移植和调试这些系统非常耗时。Linux内核是个复杂并久远的软件项目，包含大约2000万行代码。由于Linux内核的复杂性提高，理解和修改这么一个大规模的代码库变得昂贵且乏味。开发人员可能难以解决这样的项目，拥有了对整个代码库的全局视角，他们就可以理解和帮助维护项目。
Linux不断增长的规模和复杂性已经在理解整体代码结构，构件，以及构件之间的关系等方面提出了新的挑战。开发人员花费了非常多的时间阅读内核代码去获得对整个代码库的全局视角。与其直接阅读以文本为基础的源代码，代码可视化技术使得开发人员通过系统的方法理解成千上万行的代码容易得多。使用代码视觉表达，开发人员能够清楚地协调地检查成千上万行代码。尽管已经存在像CodeSurveyor，Treemap和kernelmap这样的可视化工具，提供了直观的视图帮助理解内核，但是他们很少被工业开发商管广泛使用：
- 像CodeSurveyor，Treemap和kernel map这样的工具，提供了目录和文件层次的代码展示，但并没有显示函数之间的关系
- 他们失去了“大图”，因为他们吧程序分解成许多片段，一个窗口展示一个片段
- 他们需要复杂的设置和预处理程序，这对于许多开发者来说是很痛苦的
- 他们缺乏互动和清晰的观点去表达当前研究的子系统与程序的整体结构有何关系
在这篇文章里，我们设计了一个内核可视化工具去解决大量代码空间的导航并提供对复杂内核结构的视觉展示，名字叫KernelGraph。KernelGraph利用发展良好的Web和可视化技术，加上强大的表格和可视化库区显示内核源代码。它提供了一个简单直观且可迭代的方法去理解和Linux内核并且从代码可视化获得深入见解。
下面的这些特点使KernelGraph现代化、独一无二且有效：
- KernelGraph看起来像一个在线地图服务，提供了对复杂Linux内核内部的视觉显示。它提供了一个对有2000万行代码的整个系统的全景视角，提供了直观的可迭代的方式去导航和理解代码，并且作为传统基于文本源代码阅读工具的替代品。
- KernelGraph展现了内核函数的更深的可视化，还有目录和文件的表示。在高级视角和源代码之间无缝切换的能力显著地减少了源代码和构建一个抽象高等心理表达之间的距离。
- KernelGraph能够作为云服务被部署，仅需要一个浏览器，用户不需要去安装任何其他软件。
- KernelGraph很容易扩展区支持其他大型工程的可视化，比如MySQL，Apache和其他大规模开源工程。
- KernelGraph能被用来开发与Linux内核相关的附加应用，这篇文章的“应用”章描述两个这样的KernelGraph应用。
这篇文章剩下的部分的组织如下。“内核代码可视化”这一章描述了我们关于代码可视化的想法，并提出了促进内核代码戴航的技术和算法。“实现和评估”这一章描述了KernelGraph的实现细节和评估它的性能和可用性的结果。“应用”这一章展示了两个KernelGraph应用来提高内核代码理解。“相关工作”这一章讨论工作。最后，我们在“总结”这一章进行了总结。
内核代码可视化
在过去的几十年，许多研究者提出了各种各样的理论和方法来开发高效的工具来帮助复杂程序的理解。程序理解关心一个开发者对于程序做了什么以及为了不出错地做一些功能性的修改和扩展时该如何做。在理解程序的过程中，开发者将对程序在大脑中建立心理的描述。开发者认知的过程和他们用来构建心理模型的暂时信息结构已经被人机交互广泛地学习。基于他们的发现，心理模型能够被认知模型来藐视，它被分为从上至下、从下至上或者两者的结合。两种不同的理解策略被开发者用来理解一个给定的程序：系统性的和按需的。理解策略关注的是理解的范围，而不是抽象层次(自顶向下、自底向上和组合)。系统策略涉及在进行修改之前获取知识和理解程序的尝试，而按需策略则由只关注与当前任务相关的代码的程序员使用。尽管按需策略最小化了修改程序之前必须理解的代码量，但是它可能会忽略重要的交互并导致更多的错误。相比之下，系统化的策略更可靠，但对于大型项目来说却不太可行;例如，Linux内核包含成千上万的功能。
认知理论领域的研究人员提出了一些重要的发现，可用于改善大型软件项目的理解过程：
- 使用能生成概念结构，在真实世界理解概念结构的方法
- 使用能让观看高层摘要的可视化工具
- 提供一个简单的导航和一个清晰的上下文环境，在其中当前的计划部分调查涉及到计划的整体结构
- 生成结构化的信息来识别程序的组成部分，然后在需要时使这些组成部分可访问
在我们的日常生活中，我们可能会浏览在线地图来定位一个不熟悉的位置。因此，在线地图服务的主要功能是生成精确表示特定区域的地图，突出显示对象和区域元素之间的关系，详细描述主要道路、主干和其他兴趣点。这些服务还提供诸如旅行路线规划、从一个地方到另一个地方的距离计算、实时交通状况和导航帮助等功能。与在线地图类似，KernelGraph提供了各种交互式视图，让开发人员可以像浏览地图一样探索内核代码空间。尽管地图系统和软件系统属于完全不同的领域，但它们在系统检查方面有许多相似之处。例如，内核开发人员通常更关注内核中的一个子系统;从那里，他们可以向上和向下跟踪调用链，以确定两个函数之间是否存在调用路径。
基于人类的认知模型(自底向上和自顶向下模型的组合)，我们设计了kernelgraph来帮助浏览内核代码。KernelGraph提供的主要服务如下：
- 符号查询——为所有函数、变量和数据类型提供了一个符号查询入口。大多数相关的查询结果以及它们之间的关系都显示在一个力指向的图中。符号查询涉及一个广泛的主题，可能有成千上万的相关结果。
- 引用查询——这涉及到从一个符号导航并逐步展开其上游或下游符号。
- 源代码查询——这涉及到检索与文件或符号相关的源代码文本。KernelGraph提供了整个代码库的鸟瞰图，但有时用户可能希望对某个特定功能进行深入分析。KernelGraph在图形中选择符号时，在单独的窗口中显示相应的源代码。
- 连接性查询——这涉及到在两个任意符号(可能是函数、变量和数据类型)之间查找所有可能的引用路径。
- 结构查询——它提供了一个结构视图，显示代码库的原始组织。用户可以按任意顺序遍历组织树，查询子树中的所有符号及其交叉引用。当一个子树包含太多的符号时，符号在层中被取消。
为了给用户提供一个轻量级的前端，我们使用主流的web技术实现了KernelGraph。力向图是一种显示图中所有节点、边及其相对位置的有效的可视化方法。在KernelGraph中，我们使用不同的颜色来突出显示图形中的不同符号。不同颜色的符号显示在不同的层中，用户可以通过在网页中随时禁用颜色来隐藏任何层。图1显示了在3.1内核中竞争条件的可视化表示(提交id: 91b57191cfd152c02ded0745250167d0263084f8)。可以从不同的路径同时调用vmpressure_work_fn方法。当开发人员被要求跟踪图1中类似的bug时，KernelGraph帮助快速定位有bug的函数及其调用路径，而不是要求开发人员阅读基于文本的源代码并在头脑中构建一个完整的图。
图2给出了内核函数vmpressure_work_fn的源代码。一般来说，图1和图2中使用的“符号查询”、“参考查询”、“源代码查询”是KernelGraph的基本特征，是从自下而上的认知模型中衍生出来的。
连接性查询是KernelGraph特定的接口。它为开发人员提供了一种快速确定两个函数之间是否存在调用路径的方法。连通性查询类似于在线地图中的路径搜索;它可以直接找到有效的调用路径，而不是逐个地搜索调用关系。图3描述了acpibattery_notify到get_freepointer的调用路径。开发人员输入一个源函数和一个目标函数后，如果它们是连接的，KernelGraph将返回调用路径。
最新的内核包含近50万个函数和大约100万个调用链接。因此，为自顶向下的理解模型构建所有内核函数的全局视图是具有挑战性的;一次只能在窗口中显示部分图形。现有的可视化工具，比如Source Insight和Understand把图分割成许多块，并在不同窗口分散展示每一块。通常，可视化方法提供了一个概览，用较少的详细信息显示整个图的全局视图。然而，正如Storey等人所说，多视图方法并不令人满意，因为用户必须概念化和整合不同窗口内容之间的隐含关系。为了显示详细的结构信息并保持上下文关系，KernelGraph使用和弦图来表示Linux内核的结构。弦图用于表示一个圆图中连接节点之间的相互关系。在我们的内核图中，我们使用层次和弦图给出了Linux内核代码的全局视图。开发人员可以通过缩放(放大)或缩小(缩小)一个位置节点的视图来在不同层次的细节上探索图形。通过多次放大或缩小不同的节点，KernelGraph将在单一的统一的视图中显示具有不同详细级别的不同节点。
图4显示了Linux内核“驱动程序”子系统中不同层次的视图序列。首先，显示所有的内核模块，每个模块代表一个子系统。从第一层开始，选择节点 “scripts”，将显示放大到显示较低层的子图。结果如图4(b)所示。第二层不仅保留父节点，而且还将被选择的节点扩展到它的所有子节点。类似地，节点“mod”可以被放大到一个中间层，如图4(c)所示。中间层名为“mod_0”，它使用“图划分”小节中描述的图划分算法将整个图解析为较小的组件。图4(d)中显示的最后一层是由目录“mod”生成的组件之一。使用图4的图表，对于开发者来说，理解一个项目的整个架构是非常直观的。项目的不同部分之间的关系也被清晰地呈现出来。
图1 内核中竞争条件的核图表示。从不同的路径并发调用。
图2 KernelGraph中的内核源代码表示。vmpressure_work_fn函数的源代码。
图3 从acpibattery_notify到get_freepointer路径搜索结果及其可视化表示
分析
代码解析。为了能够快速响应visualnavigation，我们首先从ker-nel源代码中提取结构数据(函数、变量和用户定义类型)，并将它们存储在数据库中。尽管许多工具(如GCC、GNU cflow和clang)可以分析一组源文件和编程语言，并输出各种函数之间的依赖关系图，但这些工具并不提取变量之间的引用。还应该考虑用户定义类型和全局变量之间的依赖关系。
在我们的调查中，我们发现doxygen是一个收集与函数和变量相关的所有信息的有效工具。它实际上是一个标准工具，用于从带注释的c源代码生成文档。它很容易配置，经常用于大规模代码解析。Doxygen还支持其他流行的编程语言，如C、Object-C、C#和Java. Doxygen从无文档的源文件解析代码结构，输出一个交叉引用输入文件中遇到的所有符号清单，包括函数、变量和用户定义类型。然而，Linux内核源代码是一个如此庞大的项目，用Doxygen一次解析所有结构信息是不可能的。因此，根据源代码文件的总数，将整个文件集分为四个部分。
图划分。在我们的统计数据中，Linux内核3.19源代码包含40多万个函数，全局变量的数量达到15万个。在kernelgraph中显示所有功能节点似乎既不可能也没有必要;因此，我们使用图形划分算法在图形中显示函数的部分集合。
通常，图划分是一个非常困难的问题，现有的解决方案都是由启发式和近似算法得到的。Buluc等人研究了图划分的最新进展。
在KernelGraph中，我们使用了一个名为metis的开源软件包来将大的图形划分成更小的组件。METIS是基于多级图划分算法
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[235328]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
