コールグラフ - Mae向きなブログ

以前からコールグラフを書いてみたいと思っていたのですが，どうやって書けばいいのか，全く検討もつきませんでした。ところが，最近になって，小さな点となって散らばっていた知識が線となってつながり始めたような感じで，こうやればコールグラフが書けるのではと思いました。Ubuntu上でやってみたので以下にまとめてみます。

目的

以下のような簡単な再帰プログラム(fact.c)からコールグラフを作成したい。最終的にはもっと複雑なものを扱いたい。

#include <stdio.h>

int fact(int n);

int fact(int n)
{
  if (n == 0)
    return 1;
  else
    return n * fact(n - 1);
}

int main(void)
{
  printf("5! = %d\n", fact(5));
  return 0;
}

関数へのenter/exitをフックする

GCCの-finstrument-functionsというオプションを利用すると，C/C++の関数が呼び出された直後と，その関数からreturnする直前に，自作の関数を呼び出してもらうことができます。
今回は，fact.cを使って関数が呼ばれる様子を観察したいので，-finstrument-functionsオプションを使って，fact.cをコンパイルします。

$ gcc -finstrument-functions fact.c

次に，以下のようなフック関数を含んだ，func_trace.cを作成します。

#define _GNU_SOURCE
#include <stdio.h>

__attribute__((no_instrument_function))
void __cyg_profile_func_enter(void *func_address, void *call_site)
{
  void *frame = __builtin_frame_address(1) + 8;
  printf("enter: %p, %d\n", func_address, *(int*)frame);
}

__attribute__((no_instrument_function))
void __cyg_profile_func_exit(void *func_address, void *call_site)
{
  printf("exit: %p\n", func_address);
}

__cyg_profile_func_enterに関数へのenter時に行う処理，__cyg_profile_func_exitに関数からのexit時に行う処理を記述します。今回は，__cyg_profile_func_enterの中で，

呼ばれた関数のアドレス
そのときの引数

を出力という処理をしています。以下のように，func_trace.cを共有ライブラリ化します。

$ gcc -fPIC -shared -o func_trace.so func_trace.c

func_trace.soをプリロードして，階乗プログラムを実行してみます。

$ LD_PRELOAD=./func_trace.so ./a.out
enter: 0x80484bb, 134513968
enter: 0x8048464, 5
enter: 0x8048464, 4
enter: 0x8048464, 3
enter: 0x8048464, 2
enter: 0x8048464, 1
enter: 0x8048464, 0
exit: 0x8048464
exit: 0x8048464
exit: 0x8048464
exit: 0x8048464
exit: 0x8048464
exit: 0x8048464
5! = 120
exit: 0x80484bb

ちょっと分かりにくいですが，0x80484bb,0x8048464が呼ばれた関数のアドレスとなります。ちなみに，0x80484bbがmain関数，0x8048464がfact関数のアドレスです。

addr2line

上記の実行結果だと，分かりにくいので，addr2lineを使って関数名を得ることを考えます。と同時に，RubyとGraphvizを使って一気にpngファイルを作成します。

generate_png.rb

#!/usr/bin/env ruby
require 'rubygems'
gem 'ruby-graphviz'
require 'graphviz'

func_trace = []
while line = gets
  next if line =~ /\Aexit/
  if line =~ /\Aenter:\s+(0x\d+),\s+(\d+)/
    (addr, arg) = $1, $2
    func_trace << [`addr2line -f -e a.out #{addr}`.split[0], arg]
  end
end

g = GraphViz::new("G")
before = g.add_node("main")
func_trace.each do |func, arg|
  node = g.add_node(func + arg)
  g.add_edge(before, node)
  before = node
end

g.output(:output => "png")