有许多优秀的源代码分析工具，如cscope, ctags和SI等，利用这些工具可以在源码中穿梭，可以查找符号，搜索函数定义，搜索被哪些函数调用，查找字符串等等，但是如果你知道两个函数，怎么找到它们之间的调用路径，CodeViz可以生成函数调用图，但是CodeViz安装复杂，而且需要用修改过的gcc编译源码，虽然能输出可视化的图片，但是调用分枝太庞大，包含很多无用信息。

下面从分析cscope.out文件格式，构造函数调用关系图，DFS搜索两个函数之间的调用路径，针对Linux这样的大型项目，首先找出调用频率TOP 1000的函数，不作考虑，以提升搜索速度。

cscope 的四个参数

  -b       Build the database only.
  -c       Use  only  ASCII characters in the database file, that is, do not compress the data.
  -k       Kernel  Mode  turns  off  the  use of the default include dir (usually /usr/include) when  building the database, since kernel source trees generally do not use it.
  -R      Recurse subdirectories during search  for  source files.

cscope.out fromat

    A mark is a tab followed by one of these characters:

    Char   Meaning

    @      file
    $      function definition
    `      function call

reference http://goo.gl/R2ErDs

运行gengraph.sh生成 graph.out文件

#!/bin/bash
rm cscope.out
cscope -b -c -k -R
grep -e "[\$\`]" cscope.out > graph.out
sed -i 's/^[[:space:]]*//' graph.out

graph.out 文件的格式

$函数名（定义，不是声明，不是被调用）
`函数名（被调用）

例如Linux内核生成的graph.out

    $vfs_read
    `rw_verify_area
    `do_sync_read
    `fsnotify_access
    `add_rchar
    `inc_syscr
    $do_sync_write
    `init_sync_kiocb
    `aio_write
    `wait_on_sync_kiocb

在图中，$后的函数是图的顶点，"`" 是前一个顶点的邻接顶点。

写完第一个版本，搜索小项目毫无压力，即使用递归的DFS也不会导致函数栈崩溃。但是像Linux这样的工程，由于没有压缩，cscope.out 有347M（linux3.12），graph.out也有36M，分析下发现代码中有很多printk,memcpy等函数调用，可认为树的叶节点，有什么方法找出所有的叶节点？ 统计！找出调用频率top 100（最后还是低估Linux了，top 5000中每个函数调用次数都在50以上）。 排除top 100后，图依然很大，先工作起来吧。

xroute.py

    #!/usr/bin/python
    '''
    find one path between two functions.
    cannot process function pointer.
    '''

    import sys
    import os
    import operator

    graph = "graph.out"
    graph_lite = "graph-lite.out"
    data = []
    route = []
    visited = []

    def reverse_output_route(call):
        if call[1] >=0 :
            reverse_output_route(route[call[1]])
        print "\t->", call[0]

    def non_recursive_dfs(f1, f2):
        global route 
        global visited 
        route = []
        visited = []
        stack = [(f1, -1)]
        while len(stack) > 0:
            call = stack.pop()
            if call[0] == f2:
                reverse_output_route(call)
                return True
            parent = len(route) 
            route.append(call)
            visited.append(call[0])
            try:
                no = data.index("$" + call[0]) + 1
                dedup = set()
                for i in range(no, len(data)):
                    v = data[i]
                    if v[0]!='`':
                        break
                    v = v[1:]
                    if v not in visited and v not in dedup:
                        dedup.add(v)
                        stack.append((v, parent))
            except ValueError:
                pass

    def top(n):
        f = open(graph, "r")
        data = f.read().splitlines()
        f.close()

        stat = dict()

        for name in data:
            k = name[1:]
            if k in stat:
                stat[k] += 1
            else:
                stat[k] = 1

        sorted_stat = sorted(stat.items(), key=operator.itemgetter(1), reverse=True)

        topdata = []
        i = 1 
        for k in sorted_stat:
            topdata.append(k[0])
            i+=1
            if i > n:
                break
        return topdata

    def readdata():
        global data
        if os.path.isfile(graph_lite):
            fd = open(graph_lite, "r")
            data = fd.read().splitlines()
            fd.close()
            return

        fd = open(graph, "r")
        temp = fd.read().splitlines()
        fd.close()

        topdata = top(5000)
        i=1
        sz = len(temp)
        while i < sz:
            if temp[i][1:] not in topdata:
                data.append(temp[i])
                i += 1
                continue
            if temp[i][0] == '`':
                i += 1
            else:
                i += 1
                while i < sz:
                    if temp[i][0] == '$':
                        break;
                    i += 1
        fd = open(graph_lite, "w")
        fd.write("\n".join(data))
        fd.close()

    def main(f1, f2):
        readdata()
        #if not non_recursive_dfs(f1, f2) and not non_recursive_dfs(f2, f1):
        if not non_recursive_dfs(f1, f2):
            print "\nthere is no path between %s and %s\n" %(f1, f2)

    def usage(pname):
        print "\n", pname, ": output the path between two functions\n"
        print "usage: ./%s [function a] [function b]\n" %(pname)
        sys.exit(-1)

    if __name__ == '__main__':
        if len(sys.argv) < 3:
            usage(sys.argv[0])
        main(sys.argv[1], sys.argv[2])

示例

    root@ubuntu:~/linux-3.12# time ./xroute.py do_sys_open security_file_alloc
        -> do_sys_open
        -> do_filp_open
        -> path_openat
        -> get_empty_filp
        -> security_file_alloc

    real    0m25.051s
    user    0m24.799s
    sys 0m0.260s

缺点是比较明显，速度慢，不能处理函数指针。

顺便列出Linux3.12 中top 10的函数

root@ubuntu:~# ./stats.py stats.out 10
rank    function                        frequency
1   printk                          44492
2   kfree                           24554
3   dev_err                         20570
4   memcpy                          18013
5   spin_unlock_irqrestore          16125
6   mutex_unlock                    15917
7   spin_lock_irqsave               13696
8   memset                          13518
9   dev_dbg                         12451
10  BIT                             12117