跳到主要內容

中文試譯：Visualize function calls with Graphviz

作者：M. Tim Jones
原文連結：http://www.ibm.com/developerworks/linux/library/l-graphvis/


摘要：你可以花時間在大量的程式碼之間穿梭進而了解function的流程，但當function pointer牽涉其中，並且程式碼非常冗長與糾纏時，這個過程會變得相當困難。本篇文章使用開放原始碼軟體以及一點膠合用的代碼，為你展示如何建立一個動態的function call圖表產生器。

透過圖形化的方式去觀察一個應用程式的呼叫流程是非常具有教育性的經驗。這麼做可以幫助你了解應用程式的內部行為以及獲取對程式進行最佳化的資訊。舉例來說，透過最佳化那些被呼叫最多次的function，你就可以用最少的力氣去得到最大的改進。除此以外，呼叫流程可以識別出使用者的function中最深度的call depth，然後你就可以為stack記憶體作適當的安排使用(在嵌入式系統中，這是一個很重要的考量)。

要獲取並顯示一幅call graph，你需要4個元素：一個GNU toolchain、addr2line程式、一些自定義的膠合代碼、以及一個叫作Graphviz的工具程式。addr2line程式讓你能夠在知道一個執行檔的某個位址後，識別出function名稱以及在源代碼中的行號。自定義的膠合代碼則是一個簡單的工具，可以將位址的追蹤流程轉變成一個圖形的規格。Graphviz則是讓你能夠產生出那些圖形。整個流程如Figure 1所示：

Figure 1. 收集追蹤資訊、轉化、並產生圖形的流程
資料收集：追蹤function呼叫
要產生function呼叫的追蹤資訊，你必須知道在程式中的每個function何時被呼叫。在美好的舊時光中，你在每個function的進入點與離開點手動插入可產出獨一無二的符號。這個過程很冗長，令人生厭並且容易出錯，而且還會讓代碼變得混亂。

幸運的是，GNU toolchain(也就是gcc)提供一個為程式自動嵌入自訂function的方式。當被嵌入的程式執行時，profiling程式行為的資料就可以進行收集。你只需提供兩個特殊的此類functions。一個會在被嵌入的function被呼叫時執行；另一個則是當被嵌入的function離開時被呼叫(看Listing 1.)。這些functions有著特別的名稱，所以它們可以被編譯器所識別。

Listing 1. GNU對function進入與離開時的profiling functions

void __cyg_profile_func_enter( void *func_address, void *call_site )
                                __attribute__ ((no_instrument_function));

void __cyg_profile_func_exit ( void *func_address, void *call_site )
                                __attribute__ ((no_instrument_function));

避免特定的function被嵌入profiling functions


你或許會覺得奇怪，如果gcc會嵌入profiling functions，為何沒有將__cyg_* profiling functions也再度嵌入？gcc的開發者思考過這個問題，並且提供了一個function attribute，叫作no_instrument_function，這可以施於function的原型上，並讓嵌入的效果失效。如果不在profiling functions上給予這兩個attribute，就會造成無限遞迴並且產生一大堆沒用的資料。


當一個被嵌入的function被呼叫時，__cyg_profile_func_enter也會被呼叫，並將該function的位址透過func_address傳入，而呼叫此functions的發生點的位址也會透過call_site傳入。相反地，當一個function離開時，__cyg_profile_func_exit會被呼叫，透過func_address傳入該function的位址，而呼叫此functions的發生點的位址也會透過call_site傳入。

在這些profiling functions中，你可以紀錄這對位址並在稍候分析它們。要讓gcc對所有函式都有嵌入的profiling functions，每個檔案都必須以-finstrument-functions以及-g編譯選項進行編譯以獲得除錯資訊。

所以，現在你可以提供profiling functions給gcc，然後它就會無縫地為你在應用程式的每個function的進入點與離開點插入profiling functions了。但是當profiling functions被呼叫時，你要對獲得的位址做些什麼事呢？你有許多選擇，但為了簡單起見，把位址寫入到一個檔案就好。注意哪個位址是進入點以及離開點(看一下Listing 2.)

注意：callsite的資訊並沒有在Listing 2中使用，因為對此處的profiling並不需要。

(譯註：M. Tim Jones後續利用外部工具addr2line去處理位址，另一個作法是直接在程式碼中處理，可參考這篇文章)

Listing 2. profiling functions
void __cyg_profile_func_enter( void *this, void *callsite )
{
  /* Function Entry Address */
  fprintf(fp, "E%p\n", (int *)this);
}


void __cyg_profile_func_exit( void *this, void *callsite )
{
  /* Function Exit Address */
  fprintf(fp, "X%p\n", (int *)this);
}

現在你可以收集profiling data了，但你要在那邊開啟與關閉你的trace output檔案呢？到目前為止，沒有對原本應用程式作修改的需要。所以，如果沒有某種對profiling data輸出的初始化，你要如何嵌入你的應用程式，包括main function呢？gcc開發者也想過這點了，並且提供一個完美的方式來實現main function的constructor與destructor。constructor function會在main之前被呼叫；而destructor function會在應用程式離開時被呼叫。
要建立你自己的constructor與destructor，需宣告兩個functions，然後施以constructor與destuctor的function attribute。在constructor function中，一個trace file被打開，profiling data會在稍候被寫入；在desturctor中，該trace file會被關閉(Listing 3.)。
Listing 3. Profiling constructor以及destructor functions
/* Constructor and Destructor Prototypes */

void main_constructor( void )
 __attribute__ ((no_instrument_function, constructor));

void main_destructor( void )
 __attribute__ ((no_instrument_function, destructor));


/* Output trace file pointer */
static FILE *fp;

void main_constructor( void )
{
  fp = fopen( "trace.txt", "w" );
  if (fp == NULL) exit(-1);
}


void main_deconstructor( void )
{
  fclose( fp );
}

如果profiling functions(在instrument.c中)被編譯並連結進目標應用程式，結果就會是一個你的應用程式所產生的call trace，並存於trace.txt中。這個trace file會在應用程式被呼叫的同一個目錄下。你會獲得一個相當大的檔案，充斥著一堆位址。為了對這些資料有感覺，接著要使用一個較少人知道的GNU工具程式，叫作addr2line。


利用addr2line將function位址轉為function名稱
addr2line(GNU binutils的一部份)是一個將執行檔中的指令位址轉為檔案名稱、function名稱，以及在代碼中所屬行數的工具程式。這個功能對於將trace的位址轉換為某些有意義的東西相當完美。

要知道這件事情如何運作，就試驗一個簡單的例子吧。(我直接在shell中操作，因為這是證明這個過程最簡單的方式，看看Listing 4.吧。)範例程式(test.c)透過cat去建立(透過重導向標準輸入到檔案)。這個檔案接著以gcc編譯，並給予一些特殊編譯選項。首先，連結器被指示(透過-Wl)要產生map檔，然後編譯器被指示要產生除錯符號(-g)。結果會產出一個名為test的執行檔。你可以使用grep去尋找在map檔中的main的位址。將這個位址與可執行檔餵給addr2line，你就可以看到function名稱(main)、原始檔案(/home/mtj/test/test.c)、以及在代碼中的行數。

addr2line程式被喚起，透過-e選項識別出執行檔image為test。接著使用-f選項，要求它給出function名稱。

Listing 4. addr2line的使用例子
$ cat >> test.c
#include <stdio.h>

int main()
{
  printf("Hello World\n");
  return 0;
}
<ctld-d>
$ gcc -Wl,-Map=test.map -g -o test test.c
$ grep main test.map
 0x08048258  __libc_start_main@@GLIBC_2.0
 0x08048258  main
$ addr2line 0x08048258 -e test -f
main
/home/mtj/test/test.c:4
$

簡化function trace資料
你現在已經有收集function位址的trace資料，也有辦法透過addr2line將一個位址對應到function名稱。然而，當給你一大陀應用程式產出的trace位址時，你要如何簡化這些資料使得它們是有意義的？這就是自定義的膠合代碼需要填補開放原始碼工具的缺口。隨著此篇文章，我提供了一個對代碼有良好註解的工具程式(Pvtrace)，包括了如何建構與使用的說明(查看"資源"那一小節以獲取更多資訊)。
回想一下Figure 1，在被嵌入的應用程式執行後，一個名為trace.txt的檔案會被建立。這個可以讓我們閱讀的檔案包含了一大串的位址 -- 一行一個，每個都有一個prefix字元。如果prefix是E，該位址就是function的進入function(該function被呼叫)。如果prefix是X，該位址就是一個離開的位址(就是說，你將離開該function)。
所以啦，如果在該trace檔中，你有一個進入點的位址(A)，後面跟著另一個位址(B)，你就可以知道是(A)呼叫了(B)，如果(A)是跟著一個離開的位址(A)，那就是(A)被呼叫，然後返回了。當更長的呼叫發生時，這會變得不易知道誰呼叫了誰，所以一個簡單的解決方法就是維護一個進入點位址的stack。每一次當在trace檔中遇到一個進入點位址時，就將它放進stack中。在stack頂端的位址就表示最近被呼叫的那個function(也就是active function)。如果另一個進入點位址接著出現，就表示在stack中位址呼叫了這個剛從trace檔讀到的位址。當遇到一個離開點位址時，目前的active function就是要返回了，於是就可將在stack頂端的元素去掉一個。然後，此時就回到了前一個function的環境，這就是完成了正確的呼叫流程。
Figure 2將這個概念以資料的化簡法來示意。當呼叫流程從trace檔被解析時，一個connectivity matrix被建立，它會將哪個function呼叫哪個function的關係建立起來。matrix的列表示從哪個位址呼叫，而位於欄的位址表示被呼叫的位址。對每一次的呼叫組合來說，會有一個格子的數字增加1(呼叫次數)。當整個trace檔被讀取完畢並解析後，結果就會是這個精簡的表示法，表現出對整個應用程式呼叫經過，包括呼叫次數。
Figure 2. 解析並簡化trace資料為一個matrix的型式
Reduction process 
現在這個精簡的function connectivity matrix已建立起來了，接著就是要花張圖啦。讓我們深入Graphviz，了解一下要如何從一個connectivity matrix去弄出一張圖吧。
(譯註：此處的connectivity matrix應使用某種型式的sparse matrix來避免鉅量的記憶體使用量。)
使用Graphviz
Graphviz，或Graph Visiualization，是AT&T的一個開放原始碼圖形工具。他提供了數種圖形的選擇，不過我會聚焦在directed graph的能力，並使用Dot語言。我給你一個很快的概觀，讓你知道如何透過Dot去建立一張圖，並展示如何將profiling資料轉換為Graphviz所需的格式(請參考"資源"那一小節以下載這個工具)。
Dot的Graph格式
透過Dot語言，你可以定義三種物件：圖、節點、邊。為了了解這些物件的意思，讓我們建立一個例子來解釋吧。

Listing 5表示一個簡單的directed圖，它有3個節點，以Dot的表示法呈現。第1行宣告了你的圖，叫作G，以及它的類型(一個digraph)。接著的三行建立了圖的節點，叫作node1、node2、node3。當節點的名稱出現在圖的格式中時，它們就會被建立。邊則是透過->運算子將兩個節點合在一起時被建立，如6到8行所示。我也用了一個可選用的邊的屬性 -- label -- 也就是這個邊的名稱。最後，整張圖就在九行內完成了。
Listing 5. 用Dot表示式的範例 (test.dot)
1:  digraph G {
2:    node1;
3:    node2;
4:    node3;
5:
6:    node1 -> node2 [label="edge_1_2"];
7:    node1 -> node3 [label="edge_1_3"];
8:    node2 -> node3 [label="edge_2_3"];
9:  }


為了將這個.dot檔轉成圖檔，你要使用由Graphviz所提供的Dot工具程式，Listing 6展示了這個轉換：

Listing 6. 使用Dot以產生JPG圖檔
$ dot -Tjpg test.dot -o test.jpg
$


在這段代碼，我指示了Dot去利用我的test.dot然後產出一張JPG圖檔，test.jpg。這張圖在Figure 3.，我使用JPG格式，不過Dot支援其他圖檔格式，包括GIF、PNG、以及postscript。
Figure 3. Dot產生的範例圖檔
Sample graph created by Dot 
Dot語言還支援其他選項，包括形狀、顏色、以及一堆屬性。不過對我想要完成的東西來說，一點選項就很好用了。
將這些片斷串起來
現在你已經看到整個流程的每個片斷了，一個完整的例子來說明這個流程可以將它們全部串在一起。現在，你應該已經解開並安裝好Pvtrace工具程式了。你也應該有將instrument.c複製到你要觀察的原始碼目錄中。
在此例中，我有一個原始檔叫作test.c，我打算將它嵌入。Listing 7展示了整個過程。在第3行，我建立(編譯並連結)應用程式。我在第四行執行test，然後用 ls 確認trace.txt有產生出來。在第八行，我喚起pvtrace，然後餵給它一個image作為它的唯一參數。這個image名稱是要給add2line用的(在pvtrace中會使用addr2line)，所以addr2line就可以獲取image中的除錯資訊。在第九行，我使用了另一個 ls 去確認pvtrace有產出graph.dot。最後，在第12行，使用dot將圖形規格轉為JPG圖檔。

Listing 7. 產生呼叫流程圖檔的完整經過
 1:  $ ls
 2:  instrument.c    test.c
 3:  $ gcc -g -finstrument-functions test.c instrument.c -o test
 4:  $ ./test
 5:  $ ls
 6:  instrument.c     test.c
 7:  test             trace.txt
 8:  $ pvtrace test
 9:  $ ls
10:  graph.dot        test           trace.txt
11:  instrument.c     test.c
12:  $ dot -Tjpg graph.dot -o graph.jpg
13:  $ ls
14:  graph.dot        instrument.c   test.c
15:  graph.jpg        test           trace.txt
16:  $

這個流程的範例圖檔在Figure 4中呈現。這個範例圖檔是從一個簡單的、使用Q learning方式強化學習的應用程式擷取出來。
Figure 4. 範例程式的追蹤結果
Sample Program Trace Result
你也可以對更多程式使用這個方法。我給的最後一個例子是gzip工具程式。我很簡單的加進instrument.c到gzip的Makefile相依關係中，建置它，然後用gzip去產生出一個trace檔。這個圖檔太大了以至於無法呈現出太多細節，不過這張圖表現了gzip如何壓縮一個小檔的整個經過。
Figure 5. gzip的追蹤結果
Gzip trace result 
結論
利用開放原始碼軟體以及一點點的膠合代碼，你可以在很短的時間內開發出有趣並且有用的專案。透過一些GNU編譯器對應用程式進行profiling的extensions、addr2line解析位址的能力、以及Graphviz產生圖表的功能，你可以獲得一個可以對應用程式的呼叫流程的圖形。能夠以圖形方式觀看呼叫流程是很有用的，可以對內部行為更加理解。這種知識對於除錯與最佳化應用程式都有很大的幫助。
資源
標籤：

留言

張貼留言

這個網誌中的熱門文章

誰在呼叫我？不同的backtrace實作說明好文章

今天下班前一個同事問到：如何在Linux kernel的function中主動印出backtrace以方便除錯？ 寫過kernel module的人都知道，基本上就是用dump_stack()之類的function就可以作到了。但是dump_stack()的功能是如何作到的呢？概念上其實並不難，慣用手法就是先觀察stack在function call時的變化(一般OS或計組教科書都有很好的說明，如果不想翻書，可以參考 這篇 )，然後將對應的return address一層一層找出來後，再將對應的function名稱印出即可(透過執行檔中的section去讀取函式名稱即可，所以要將KALLSYM選項打開)。在userspace的實作可參考Jserv介紹過的 whocallme 或對岸好手實作過的 backtrace() ，都是針對x86架構的很好說明文章。 不過從前面兩篇文章可以知道，只要知道編譯器的calling convention，就可以實作出backtrace，所以是否GCC有提供現成的機制呢？Yes, that is what __builtin_return_address() for!! 可以參考這篇 文章 。該篇文章還提到了其他可以拿來實作功能更齊全的backtrace的 程式庫 ，在了解了運作原理後，用那些東西還蠻方便的。 OK，那Linux kernel是怎麼做的呢？就是用頭兩篇文章的方式啦~ 每個不同的CPU架構各自手工實作一份dump_stack()。 為啥不用GCC的機制？畢竟...嗯，我猜想，除了backtrace以外，開發者還會想看其他register的值，還有一些有的沒的，所以光是GCC提供的介面是很難印出全部所要的資訊，與其用半套GCC的機制，不如全都自己來~ arm的實作 大致上長這樣，可以看到基本上就只是透過迭代fp, lr, pc來完成： 352 void unwind_backtrace (struct pt_regs * regs , struct task_struct *tsk) 353 { 354 struct stackframe frame ; 355 register unsigned long current_sp asm ( "
13 則留言
閱讀完整內容

淺讀Linux root file system初始化流程

在Unix的世界中，file system佔據一個極重要的抽象化地位。其中，/ 所代表的rootfs更是所有後續新增file system所必須依賴前提條件。以Linux為例，黑客 Jserv 就曾經詳細說明過 initramfs的背後設計考量 。本篇文章不再重複背景知識，主要將追蹤rootfs初始化的流程作點整理，免得自己日後忘記。 :-) file system與特定CPU架構無關，所以我觀察的起點從init/main.c的start_kernel()開始，這是Linux作完基本CPU初始化後首先跳進的C function(我閱讀的版本為 3.12 )。跟root file system有關的流程羅列如下： start_kernel()         -> vfs_caches_init_early()         -> vfs_caches_init()                 -> mnt_init()                         -> init_rootfs()                         -> init_mount_tree()         -> rest_init()                 -> kernel_thread(kernel_init,...) 其中比較重要的是mnt_int()中的init_rootfs()與init_mout_tree()。init_rootfs()實作如下： int __init init_rootfs(void) {         int err = register_filesystem(&rootfs_fs_type);         if (err)                 return err;         if (IS_ENABLED(CONFIG_TMPFS) && !saved_root_name[0] &&                 (!root_fs_names || strstr(root_fs_names, "tmpfs"))) {          
張貼留言
閱讀完整內容

kernel panic之後怎麼辦？

今天同事在處理一個陌生的模組時遇到kernel panic，Linux印出了backtrace，同事大致上可以知道是在哪個function中，但該function的長度頗長，短時間無法定位在哪個位置，在這種情況下，要如何收斂除錯範圍呢？更糟的是，由於加入printk會改變模組行為，所以printk基本上無法拿來檢查參數的值是否正常。 一般這樣的問題會backtrace的資訊來著手。從這個資訊我們可以知道在function中的多少offset發生錯誤，以x86為例(從 LDD3 借來的例子)： Unable to handle kernel NULL pointer dereference at virtual address 00000000 printing eip: d083a064 Oops: 0002 [#1] SMP CPU:    0 EIP:    0060:[<d083a064>]    Not tainted EFLAGS: 00010246   (2.6.6) EIP is at faulty_write+0x4/0x10 [faulty] eax: 00000000   ebx: 00000000   ecx: 00000000   edx: 00000000 esi: cf8b2460   edi: cf8b2480   ebp: 00000005   esp: c31c5f74 ds: 007b   es: 007b   ss: 0068 Process bash (pid: 2086, threadinfo=c31c4000 task=cfa0a6c0) Stack: c0150558 cf8b2460 080e9408 00000005 cf8b2480 00000000 cf8b2460 cf8b2460        fffffff7 080e9408 c31c4000 c0150682 cf8b2460 080e9408 00000005 cf8b2480        00000000 00000001 00000005 c0103f8f 00000001 080e9408 00000005 00000005 Call Trace:  [<c0150558>] vfs
張貼留言
閱讀完整內容