跳到主要內容

誰在呼叫我?不同的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 ("sp");
356 
357         pr_debug("%s(regs = %p tsk = %p)\n", __func__, regs, tsk);
358 
359         if (!tsk)
360                 tsk = current;
361 
362         if (regs) {
363                 frame.fp = regs->ARM_fp;
364                 frame.sp = regs->ARM_sp;
365                 frame.lr = regs->ARM_lr;
366                 /* PC might be corrupted, use LR in that case. */
367                 frame.pc = kernel_text_address(regs->ARM_pc)
368                          ? regs->ARM_pc : regs->ARM_lr;
369         } else if (tsk == current) {
370                 frame.fp = (unsigned long)__builtin_frame_address(0);
371                 frame.sp = current_sp;
372                 frame.lr = (unsigned long)__builtin_return_address(0);
373                 frame.pc = (unsigned long)unwind_backtrace;
374         } else {
375                 /* task blocked in __switch_to */
376                 frame.fp = thread_saved_fp(tsk);
377                 frame.sp = thread_saved_sp(tsk);
378                 /*
379                  * The function calling __switch_to cannot be a leaf function
380                  * so LR is recovered from the stack.
381                  */
382                 frame.lr = 0;
383                 frame.pc = thread_saved_pc(tsk);
384         }
385 
386         while (1) {
387                 int urc;
388                 unsigned long where = frame.pc;
389 
390                 urc = unwind_frame(&frame);
391                 if (urc < 0)
392                         break;
393                 dump_backtrace_entry(where, frame.pc, frame.sp - 4);
394         }
395 }
了解原理與不同的可能作法後,對於kernel所採取的的作法就可以更容易體會嘍~ Really fun~

留言

  1. 小鄭學長你好:

    請問一下程式runtime的時候我可以以printf()印出return address (by __builtin_return_address(0)),但是我應該無法直接使用得到的return address直接用printf()印出caller function名稱吧?可以嗎?!

    如果可以,我要怎麼做呢?!

    回覆刪除
  2. 哈,你沒有仔細看我推薦的文章喔,當然可以。前面Jserv那篇文章就有用libbfd去實作,懶得用libbfd的話,可以直接用addr2line搭配一點點script來完成(第二篇文章)。基本想法就是,由於你printf出來的address是執行期的絕對位址,而addr2line去找libxxx.so中的function名稱是要靠相對位移,所以要從/proc/process_id/maps去找libxxx.so的載入起始位址,然後用印出的絕對位址去減掉載入的起始位址,然後才能使用addr2line。第二篇文章是這篇:
    http://www.limodev.cn/2009/05/21/%E7%B3%BB%E7%BB%9F%E7%A8%8B%E5%BA%8F%E5%91%98%E6%88%90%E9%95%BF%E8%AE%A1%E5%88%92%EF%BC%8D%E5%83%8F%E6%9C%BA%E5%99%A8%E4%B8%80%E6%A0%B7%E6%80%9D%E8%80%83%E4%BA%8C/

    回覆刪除
  3. 嘿!被抓包~~ (^^|||)
    我會再去研究一下,感謝你喔。

    回覆刪除
  4. 不用那麼客氣啦~有什麼就直接討論,大家都在學習啊~Keep walking!! :)

    回覆刪除
  5. 學長抱歉請容許我再釐清一個觀念先。

    首先我認為"addr2line"是一個外部工具,因為compiler是架於工作站,我無法確定管理員是否有安裝或是要如何下command,這部分我會再去研究看看。(我果然對linux不是很在行 XD)

    我看過這篇文章後發現他都是對於一個編譯後的執行檔配合addr2line來取出caller。但是因為我想用於我的工作上,我們的code build完都是一大包,說實在我無法用這個方法。

    我想要做的是說我可以直接在機器運行的時候,利用console線直接印出caller function而不靠助外面的compiler機制。舉例來說:

    function A(){
    uint32 returnAdd = __builtin_return_address(0);
    (char*)callerName = get_by_address(returnAdd);
    }

    其實我想找的是這種不靠助外力(不要使用compiler)就直接可以打印的程式,就像我舉例的寫出這個get_by_address()。這樣真的可以嗎?!因為我看見範例都要用到外部compiler的幫忙,其實我比較不想這樣使用。我認為無論如何都要借助外面的symbol file來查詢caller的名稱,所以我一開始說我認為無法不利用讀外部檔案就可以印出caller的名稱。

    請問我這樣的觀念是對的嗎?!

    回覆刪除
  6. 當然可以。在前面推薦的文章中有喔~我再貼一次,並附上我的測試:
    http://www.acsu.buffalo.edu/~charngda/backtrace.html
    [mars@dream tmp]$ cat bt.c
    /* gcc -o bt -rdynamic bt.c
    * ./bt
    */
    #include
    #include
    #include

    /* Obtain a backtrace and print it to stdout. */
    void print_trace(void)
    {
    void *array[10];
    size_t size;
    char **strings;
    size_t i;

    size = backtrace (array, 10);
    strings = backtrace_symbols (array, size);

    printf ("Obtained %zd stack frames.\n", size);

    for (i = 0; i < size; i++)
    printf ("%s\n", strings[i]);

    free (strings);
    }

    /* A dummy function to make the backtrace more interesting. */
    void dummy_function (void)
    {
    print_trace ();
    }

    int main (void)
    {
    dummy_function ();
    return 0;
    }
    [mars@dream tmp]$./bt
    Obtained 5 stack frames.
    ./bt(print_trace+0x19) [0x804873d]
    ./bt(dummy_function+0xb) [0x80487a9]
    ./bt(main+0xb) [0x80487b6]
    /lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe6) [0x18fb56]
    ./bt [0x8048691]
    這個方式是用glibc提供的backtrace_symbols()。如果想要完全的控制,則須像jserv那篇,用libbfd去執行檔格式中找要的資訊,甚至是像linux kernel那樣自己寫parser去找執行檔中的資訊。
    簡單來說,依不同情況,backtrace的實作有幾種:
    step 1: 取出return address:
    0. 自己觀察stack的變化,取出適當的return address
    or
    1 用GCC的__builtin_return_address()
    or
    2 用glibc的backtrace()

    step 2: 根據return address找出對應的function name
    0. 用addr2line
    or
    1. 用glibc的backtrace_symbol()
    or
    2. 用libbfd
    or
    3. 用libunwind
    or
    4. 像Linux kernel一樣,自定執行檔部份section,自行parse執行檔,取出要的資訊

    所有的資訊都在執行檔與作業系統中,只是看我們如何去取得而已。:)

    回覆刪除
  7. Hi~小鄭學長問個問題,

    請問在你所介紹的blog中(http://www.limodev.cn/2009/05/21/%E7%B3%BB%E7%BB%9F%E7%A8%8B%E5%BA%8F%E5%91%98%E6%88%90%E9%95%BF%E8%AE%A1%E5%88%92%EF%BC%8D%E5%83%8F%E6%9C%BA%E5%99%A8%E4%B8%80%E6%A0%B7%E6%80%9D%E8%80%83%E4%BA%8C/),他再寫"int backtrace(void** buffer, int size)"這個function的時候,為什麼都把 int n = 0xfefefefe;

    其中這個0xfefefefe有甚麼意義?!我怎麼認為應該不是這樣?是我疏漏了甚麼嗎?!

    他的全部程式碼是:
    int backtrace(void** buffer, int size)
    {
    int n = 0xfefefefe; /*奇怪點?!*/
    int* p = &n;
    int i = 0;

    int ebp = p[1 + OFFSET];
    int eip = p[2 + OFFSET];

    for(i = 0; i < size; i++)
    {
    buffer[i] = (void*)eip;
    p = (int*)ebp;
    ebp = p[0];
    eip = p[1];
    }

    return size;
    }

    回覆刪除
  8. 那只是為了下面這個觀察,所以給一個變數,然後透過這個變數的位址去找到上一個ebp的值而已:

    "调用时,先把被调函数的参数压入栈中,C语言的压栈方式是:先压入最后一个参数,再压入倒数第二参数,按此顺序入栈,最后才压入第一个参数。

    然后压入EIP和EBP,此时EIP指向完成本次调用后下一条指令的地址 ,这个地址可以近似的认为是函数调用者的地址。EBP是调用者和被调函数之间的分界线,分界线之上是调用者的临时变量、被调函数的参数、函数返回地址(EIP),和上一层函数的EBP,分界线之下是被调函数的临时变量。

    最后进入被调函数,并为它分配临时变量的空间。gcc不同版本的处理是不一样的,对于老版本的gcc(如gcc3.4),第一个临时变量放在最高的地址,第二个其次,依次顺序分布。而对于新版本的gcc(如gcc4.3),临时变量的位置是反的,即最后一个临时变量在最高的地址,倒数第二个其次,依次顺序分布。"

    在我的電腦上,不用定義NEW_GCC(我的gcc是4.4.1),直接gcc -g -o bt bt.c,就可以正常輸出,所以看來不同版本的stack變數擺放的先後順序有可能會不一樣。用objdump -d bt就可以很清楚的看到stack的實際變化嘍~

    回覆刪除
  9. 同樣的,前面提到的文章之一:
    http://eli.thegreenplace.net/2011/02/04/where-the-top-of-the-stack-is-on-x86/
    解釋的圖畫的比我漂亮多了~ :)

    回覆刪除
  10. 你將n的值設為多少都是OK的,重要的是它的位址,在backtrace()中,stack的長像類似是這樣:

    |
    |
    |____*p_____| <- 0xbf100008
    |____n______| <- 0xbf100004 <- &n
    |_prev ebp__| <- 0xbf100000 <- current ebp
    |___________

    所以將p的初始值設為&n,表示指向目前的ebp的下一個位址,因為linux上,stack的生長方向是往位址低的方向,所以p + 1就是"上一個"ebp的"值"所在的位址,所以p[1+0]就是該位址的值,也就是prev ebp,所以接著將這個"值"當作位址來用:
    p = (int*)ebp;
    然後再把更上一層的ebp的"值"找出來:
    ebp = p[0];
    希望這樣有比較清楚。 :)

    回覆刪除
  11. HI~小鄭學長,我想我大致上了解也實作了一下。

    抱歉您的圖是不是有點不太對,但是我想沒有關係,我已經知道意思了!!

    根據eli的想法:int backtrace(void** buffer, int size)

    H |__size______|
    |__**buffer__|
    ↑ |__EIP_______|
    ↓ |__EBP_______|
    |__n_________|<---
    |__*p________|----(存n位址)
    L |__i_________|

    是長這樣是吧?!

    我發現打印的EIP實際上是"下一個指令"的位址,所以說這個叫做who call me是不是有點奇怪,是不是應該改名叫"who is my next"比較貼切?還是我又遺漏了甚麼導致我觀念錯誤。

    感謝你耐心指導,讓我實作也學會不少東西。
    Happy new year to you!!!

    回覆刪除
  12. 哈,我位址應該往上遞減,打錯了~
    EIP就是一般所謂的program counter,指向下一個要執行的指令,whocallme指的是從哪個function呼叫過來的,透過"上一層"的EIP(這個位址會落在上一個function的區間),我們就可以知道是從哪個function來呼叫目前function。所以這個名稱沒有問題。

    回覆刪除

張貼留言

這個網誌中的熱門文章

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_write+0xb8/0x130
 [<c0150682>] sy…

Linux User Space記憶體管理行為

整理了一下Linux/glibc在user space的一些記憶體管理行為後,發現幾個有趣的現象,感覺值得紀錄一下:

1. glibc會依據malloc的block大小決定使用brk()/sbrk()或mmap()。 malloc呼叫後,glibc會根據block的大小決定是透過brk()/sbrk()或mmap()去跟kernel要記憶體,這個值可以透過mallopt(MMAP_THRESHOLD, size)去變更。我猜想這應該是為了效率問題。因為在heap中要找尋一塊足夠大的block,必須有某種查詢的方式去看目前free block是否足夠大塊,而一般程式的行為應該是以小塊block居多,所以往往會造成需要再呼叫brk()/sbrk()去要記憶體,而釋放大塊的block時,又需要再次呼叫brk()/sbrk()(小塊block一般不需要,看2.的說明),這樣會造成很多不必要的system call呼叫。

2. glibc透過brk()/sbrk()去擴展/縮減heap的策略類似Schmitt trigger 因為brk()/sbrk()是system call,所以一般這個開銷會比library call大一些,為了減少小尺寸的block頻繁地觸發system call,brk()/sbrk()的呼叫時機會類似Schmitt trigger的特性,也就是說,當第一次要求小block時,就會透過brk()去擴展一個較大的尺寸,以減少後續呼叫次數,然後釋放block後,會等到heap的頂端退到了一個門檻值後才再呼叫sbrk去縮減。觀察方式很容易,如下: [mars@dream tmp]$ ./a.out & [2] 2447 [mars@dream tmp]$ 0x8b8f008 

[mars@dream tmp]$ cat /proc/2447/maps 
08048000-08049000 r-xp 00000000 08:03 2891777    /home/mars/hobbies/tmp/a.out
08049000-0804a000 r--p 00000000 08:03 2891777    /home/mars/hobbies/tmp/a.out
0804a000-0804b000 rw-p 00001000 08:03 2891777    /home/…