Linux内核的静态调用图生成 [英] Static call graph generation for the Linux kernel

问题描述

我正在寻找一种工具来静态生成Linux内核的调用图(对于给定的内核配置).在包括所有调用在内的意义上，生成的调用图应该是完整的"，在Linux内核的情况下，包括潜在的间接调用(我们可以假设这些调用只能通过使用函数指针来完成).

I'm looking for a tool to statically generate a call graph of the Linux kernel (for a given kernel configuration). The generated call graph should be "complete", in the sense that all calls are included, including potential indirect ones which we can assume are only done through the use of function pointers in the case of the Linux kernel.

例如，这可以通过分析函数指针类型来完成:这种方法将导致图形中多余的边缘，但这对我来说是可以的.

For instance, this could be done by analyzing the function pointer types: this approach would lead to superfluous edges in the graph, but that's ok for me.

ncc 似乎实现了这个想法，但是我没有成功地使它在3.0内核.还有其他建议吗?

ncc seems to implement this idea, however I didn't succeed in making it work on the 3.0 kernel. Any other suggestions?

我猜想这种方法在使用函数指针强制转换的情况下也可能导致边缘缺失，因此我也想知道在Linux内核中是否有这种可能.

I'm guessing this approach could also lead to missing edges in cases where function pointer casts are used, so I'd also be interested in knowing whether this is likely in the Linux kernel.

作为一个旁注，似乎还有其他工具能够对源进行语义分析以推断潜在的指针值，但是AFAICT却没有一个设计用于诸如Linux内核之类的项目中.

As a side note, there seems to be other tools that are able to do semantic analysis of the source to infer potential pointer values, but AFAICT, none of them are design to be used in a project such as the Linux kernel.

任何帮助将不胜感激.

推荐答案

我们已经完成了2600万行(18,000个编译单元)的整体C系统的全局指向分析(使用间接函数指针)和完整调用图构造

We've done global points-to analysis (with indirect function pointers) and full call graph construction of monolithic C systems of 26 million lines (18,000 compilation units).

我们使用 DMS软件再造工具包(它的 C前端及其

We did it using our DMS Software Reengineering Toolkit, its C Front End and its associated flow analysis machinery. The points-to analysis machinery (and the other analyses) are conservative; yes, you get some bogus points-to and therefore call edges as a consequence. These are pretty hard to avoid. You can help such analyzers by providing certain crucial facts about key functions, and by harnessing knowledge such as "embedded systems [and OSes] tend not to have cycles in the call graph", which means you can eliminate some of these. Of course, you have to allow for exceptions; my moral: "in big systems, everything happens."

特定的问题包括使用特定于此特定软件的特殊加载方案动态加载(！)C模块，但这只是增加了问题.

The particular problem included dynamically loaded(!) C modules using a special loading scheme specific to this particular software, but that just added to the problem.

在函数指针上的广播不应丢失边缘；保守的分析应该简单地假设强制转换指针与签名中对应于强制转换结果的系统中的任何函数匹配.更麻烦的是产生兼容兼容签名的强制类型转换.如果在调用的实际函数接受一个int值时将函数指针转换为void * foo(uint)，则分析点必然会保守地选择错误的函数.您不能为此责怪分析仪；演员就在这种情况下.是的，我们在2600万生产线系统中看到了这种垃圾.

Casts on function pointers shouldn't lose edges; a conservative analysis should simply assume that the cast pointer matches any function in the system with signature corresponding to the casted result. More problematic are casts which produce sort-of-compatible signatures; if you cast a function pointer to void* foo(uint) when the actual function being called accepts an int, the points to analysis will necessarily conservatively choose the wrong functions. You can't blame the analyzer for that; the cast lies in that case. Yes, we saw this kind of trash in the 26 million line system.

这无疑是分析Linux的正确尺度(我认为这仅仅是800万行左右:-).但是我们还没有在Linux上专门尝试过.

This is certainly the right scale for analyzing Linux (which I think is a mere 8 million lines or so :-). But we haven't tried it specifically on Linux.

设置此工具非常复杂，因为您必须捕获有关编译本身的所有详细信息，尤其是要生成的Linux内核的配置.因此，您几乎必须拦截编译器调用才能获取命令行开关等.

Setting up this tool is complicated because you have to capture all the details about the compilations themselves, and in particular the configuration of the Linux kernal you want to generate. So you pretty much have to intercept the compiler calls to get the command line switches, etc.

这篇关于Linux内核的静态调用图生成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！