DWARF情報とpyelftoolsを使ってバックトレースする

# TL;DR

[gdbのpython拡張](https://sourceware.org/gdb/current/onlinedocs/gdb/Python.html#Python)と[`pyelftools`モジュール](https://github.com/eliben/pyelftools)を使って、バックトレースを[実装してみた](https://gist.github.com/sumomoneko/d8415b14f8eddf74a3eb9bd6d521fab3)。
gdbの`backtrace`コマンドがそのままでは動かない環境などで便利に使えるかもしれない。

# 動機

くみこみちほーで開発をしていると、

- ICEについてきたgdbserverがなんだかバグっていて、`backtrace`でgdbが落ちる。
- gdbが知らないスレッド実装を使っているので、スレッドごとのバックトレースが出来ない。
- バイナリしかないgdbserverがスレッド構造知っているけども、スレッド周りのコード変更したら構造体が段ずれしてgdbごと落ちる。
- rawなメモリダンプが手元に来たが、そもそもこのプラットフォーム向けgdbではダンプファイルを読む機能がない。

という状況がまれによくあるのではないでしょうか。そんなシリアルとLEDだけでサバンナに放り投げられ困っていたとき、[デバッグ情報の歩き方](https://qiita.com/mhiramat/items/8df17f5113434e93ff0c)のおかげで でばっぐじょーほーがよめるフレンズ になれたので、バックトレースしてみようかな、というのが本稿になります。

# 準備

## 確認環境

追試の簡単のため、組み込み環境ではなくx64 ubuntu 16.04 gcc5.4/python3.5の環境で確認しています[^1]。

[^1]: 組み込みとしては、RXで実戦投入しています。

## 説明にあたって

DWARFの基本については[デバッグ情報の歩き方](https://qiita.com/mhiramat/items/8df17f5113434e93ff0c)にとても詳しく説明されていますので、そちらを参照ください。あと、[こちら](https://ja.osdn.net/projects/drdeamon64/wiki/DWARF%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E3%83%95%E3%82%A9%E3%83%BC%E3%83%9E%E3%83%83%E3%83%88)の記事もとても参考になりました。

また、[gdb Python-API](https://sourceware.org/gdb/onlinedocs/gdb/Python-API.html#Python-API)についてもあまり細かくは触れません。`python gdb`モジュールを使って複雑なことをやっているわけではありませんので、サンプルを見ればなんとなく伝わるかなと思います。


## `pyelftools`のインストール

素手でDWARFをデコードしていくのは辛いので、かなりの部分をデコードしてくれるpythonモジュール[pyelftools](https://github.com/eliben/pyelftools)をインストールします。
virtualenvなどで環境を隔離したいところですが、gdb経由でpythonを呼んだ場合にvirtualenvでのモジュールパスを見てくれなかったので、システムに直に入れてしまいます。

```shell
$ sudo pip3 install pyelftools
```

あるいは、どこか適当なところにモジュールを展開して、pythonスクリプトの先頭に

```python
import sys
sys.path.append("/home/oreore/virtualenv/python/site-packages")
```

のようにパスを入れてしまってもよいかもしれません[^2]。

[^2]: このあたり、gdbを説得できる華麗な解法がありましたら指摘おねがいします。

## 確認用コードをclone&make

動作の確認用に手頃な規模のコードを利用します。ここではマッハな圧縮伸長ライブラリ[lz4](https://github.com/lz4/lz4)とそのテストアプリ`simpleBuffer`を利用します。`lz4`とはなにかについては、たとえば[こちら](https://qiita.com/nishemon/items/818cc64dc2f8577edd87)でわかりやすく解説されていますので、そちらを参照ください。

それでは以下のようにcloneとビルドを行います。

```sh
$ git clone https://github.com/lz4/lz4.git
$ cd lz4
$ CFLAGS="-g3 -fno-dwarf2-cfi-asm" make all
```
ビルドフラグについて若干の補足になりますが、こちらで試したgcc (Ubuntu 5.4.1-2ubuntu1~16.04) 5.4.1 20160904 では、[gasのCFI ディレクティブ](https://sourceware.org/binutils/docs/as/CFI-directives.html)によってスタックフレーム情報が格納されるセクション`.debug_frame`が省略されるようで、その簡略版(?)`.eh_frame`しかでてきませんでした。
`pyelftools`では`.eh_frame`のデコードにも対応しているのですが、使うには若干手間がかかります。そこで今回は、コンパイラに対して`.debug_frame`を出力してもらうよう、[`-fno-dwarf2-cfi-asm`オプション](https://gcc.gnu.org/onlinedocs/gcc/Debugging-Options.html)で依頼しました。このあたり、最近のubuntu/gccで変わっているのかもしれません。


## gdbで backterace実行、答えをみておく

まずはgdbで実行、適当な部分でブレークして、バックトレースしてみましょう。

```
$ cd examples
$ gdb simpleBuffer
 :
 :
(gdb) b lz4.c:578
Breakpoint 1 at 0x4010a4: lz4.c:578. (11 locations)

(gdb) r
Starting program: /home/oreore/lz4/examples/simpleBuffer 

Breakpoint 1, LZ4_compress_generic (acceleration=1, dictIssue=<optimized out>, dict=<optimized out>, tableType=<optimized out>, 
    outputLimited=<optimized out>, maxOutputSize=<optimized out>, inputSize=57, dest=0x61e010 "", 
    source=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", cctx=0x7fffffff9810) at lz4.c:578
578	    LZ4_putPosition(ip, cctx->hashTable, tableType, base);

(gdb) bt
#0  LZ4_compress_generic (acceleration=1, dictIssue=<optimized out>, dict=<optimized out>, 
    tableType=<optimized out>, outputLimited=<optimized out>, maxOutputSize=<optimized out>, 
    inputSize=57, dest=0x61e010 "", 
    source=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", cctx=0x7fffffff9570)
    at lz4.c:578
#1  LZ4_compress_fast_extState (state=0x7fffffff9570, 
    sourpppce=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", dest=0x61e010 "", 
    inputSize=57, maxOutputSize=73, acceleration=1) at lz4.c:739
#2  0x0000000000404722 in LZ4_compress_fast (
    source=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", dest=0x61e010 "", 
    inputSize=57, maxOutputSize=73, acceleration=1) at lz4.c:760
#3  0x0000000000404776 in LZ4_compress_default (
    source=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", dest=0x61e010 "", 
    inputSize=57, maxOutputSize=73) at lz4.c:771
#4  0x0000000000400957 in main () at simple_buffer.c:54
```

それではこれを再現していきましょう。


# 実装

完成したものを[gist](https://gist.github.com/sumomoneko/d8415b14f8eddf74a3eb9bd6d521fab3)に用意しましたので、それに沿って説明したいと思います。

## プラットフォーム固有の部分を分離しておく

さっそくDWARFの解析に入りたいところですがそのまえに、実行環境の整理をしておきます。

今回、x64のgdb上で動くpythonスクリプトを作っていくわけですが、別にgdb上で動かすことが必須というわけではありません。またDWARFの性質上、x64じゃないとダメ、というわけでもありません。
以下の機能が用意できれば、単体のpythonスクリプトとして、gdbからもアーキテクチャからも独立して実行することが出来ます。

- DWARFが含まれるファイルパスを得る
- 指定されたアドレスからメモリを読む
- バックトレース起点(プログラム停止場所)のプログラムカウンタを取得する
- 停止時のレジスタ値を取得する
- スタックポインタに値を設定する

まずはこれらの機能を関数として分離し、あとあとターゲット変更が容易になるようにしておきましょう。
以下、それぞれの機能実装について説明します。

### DWARFが含まれるファイルパスを得る

stripしていない実行ファイルのパスを得ます。gdb配下で実行しているオブジェクト(gdbでは"inferior"と呼んでいます)の名前を取ってきています。組み込みだと、ROMに焼く前にとっておいたstrip前のバイナリファイルになりますね。

```python
def get_elf_file_name() -> str:
    """
    デバッグ情報が含まれているファイル名を得る。
    gdb環境下の場合、gdb.objfiles()[0].filenameで見つかる
    :return: デバッグ情報をもつファイルパス
    """
    import gdb
    return gdb.objfiles()[0].filename
```

### 指定されたアドレスからメモリを読む


```cpp
uintptr_t ret = *reinterpret_cast<uintptr_t*>(addr);
```
これをgdb-pythonで行うイメージです。レジスタが指すメモリを取ってくるときに使います。メモリ領域として必要となるのはスタック領域なので、独自ダンプを作る場合は少なくともスタック領域をダンプ対象としておくとよいですね。

```python
def read_uintptr_t(addr: int) -> int:
    """
    uintptr_t サイズのデータをメモリから読む
    uintptr_t ret = *reinterpret_cast<uintptr_t*>(addr);
    :param addr: アドレス
    :return: データ
    """
    import gdb
    uintptr_t = gdb.lookup_type('uintptr_t')
    return int(gdb.Value(addr).reinterpret_cast(uintptr_t.pointer()).dereference())
```

### バックトレース起点(プログラム停止場所)のプログラムカウンタを取得する

`(gdb) p $pc`をpython-gdbで書いただけです。
独自ダンプを作るなら、例外処理に飛んできた飛び元アドレスをとっておく感じでしょうか。

```python
def get_pc() -> int:
    """
    プログラムカウンタを取得する
    :return: PC値
    """
    import gdb
    return int(gdb.parse_and_eval("$pc"))
```

### 停止時のレジスタ値を取得する

DWARFはいろんなアーキテクチャに対応するよう設計されています。なので、レジスタをアーキテクチャ固有の名前では扱わず、番号をつけて管理しています。ではどのレジスタが何番なのか、なのですが、さくっと[gdbのソースコード](https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;a=blob;f=gdb/amd64-tdep.c;h=b589d93940f1f498177ba91273190dc9b0714370;hb=HEAD#l156)をみてしまいましょう。

ということで出来上がったのがこちらです。`stN`とか`mmN`レジスタをコメントアウトしていますが、これは幅が広いレジスタはなにかと面倒だったための手抜きです[^3]。
別アーキテクチャのレジスタ番号を探す場合は、gdbソースツリーのの似たようなところにCPU名付きの似たようなファイルがあるはずなので、そこら辺をみると良いでしょう。

[^3]: もともと組み込みCPUのデバッグ用に書いていたので、そんなレジスタしりません。

```python
def get_registers() -> List[int]:
    """
    DWARFのレジスタ番号に沿って、gdbからレジスタ値を集める
    https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;a=blob;f=gdb/amd64-tdep.c;h=b589d93940f1f498177ba91273190dc9b0714370;hb=HEAD#l156
    :return: DWARFレジスタ番号順のレジスタ値リスト
    """
    import gdb
    reg_names = ["rax", "rdx", "rcx", "rbx", "rsi", "rdi", "rbp", "rsp",
                 "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15",
                 "rip",
                 # "xmm0", "xmm1", "xmm2", "xmm3", "xmm4", "xmm5", "xmm6", "xmm7",
                 # "xmm8", "xmm9", "xmm10", "xmm11", "xmm12", "xmm13", "xmm14", "xmm15",
                 None, None, None, None, None, None, None, None,
                 None, None, None, None, None, None, None, None,
                 # "st0", "st1", "st3", "st4", "st5", "st6", "st7",
                 None, None, None, None, None, None, None, None,
                 # "mm0", "mm1", "mm2", "mm3", "mm4", "mm5", "mm6", "mm7",
                 None, None, None, None, None, None, None, None,
                 "eflags",
                 "es", "cs", "ss", "ds", "fs", "gs", None, None,

                 None, None, None, None,
                 None, None,
                 "mxcsr", "fctrl", "fstat"]

    ret = []
    for name in reg_names:
        if name is not None:
            val = int(gdb.parse_and_eval("${}".format(name)))
            ret.append(val)
        else:
            ret.append(-1)
    return ret
```

### スタックポインタに値を設定する

コールツリーを遡る際、スタックを巻き戻す必要があります。スタックを保持するレジスタはアーキテクチャ依存なので、巻き戻し処理として関数に切り分けておきます。

```python
def unwind_stack(regs: List[int], cfa: int) -> None:
    """
    レジスタのうちスタックポインタを保持するレジスタにアドレスを設定する。
    x64の場合は$rspが対象。DWARFレジスタ番号は7番なので、そこにアドレス設定する。
    :param regs: レジスタの配列(DWARFレジスタ番号順)
    :param cfa: スタックポインタとして設定するアドレス
    :return: None
    """
    regs[7] = cfa
```

以上で、gdbとアーキテクチャに依存するところは終わりです。


## 全体の流れ

バックトレース処理の全体の流れとしては以下のようになります。

1. 停止アドレス, レジスタ(含スタックポインタ)を得る
1. アドレスから関数情報を得る
1. スタックフレーム情報から、呼び出し元アドレスと、呼び出し直前のレジスタ状況を得る
1. 2に戻って繰り返し

これを`main()`でベタに書いています。

```python
def main() -> None:
    """
    バックトレースを表示する
    """
    with open(get_elf_file_name(), 'rb') as f:
        elf_file = ELFFile(f)
        if not elf_file.has_dwarf_info():
            print('file has no DWARF info')
            return

        dwarf_info = elf_file.get_dwarf_info()

        # 現在の停止位置情報から初めて、
        pc = get_pc()
        regs = get_registers()
        i = 0
        while True:
            # 停止位置の関数情報を取得
            fi = get_func_info(dwarf_info, pc)
            if fi is None:
                break

            print("#{:<3}0x{:016x} in {}() at {}:{}".format(i,
                                                            fi["addr"],
                                                            fi["func_name"],
                                                            fi["path"],
                                                            fi["line"]))
            i += 1

            # スタックフレームを見て、呼び出し元をたどる
            pc, regs = get_prev_frame(fi["cu"], pc, regs, read_uintptr_t)
            if pc is None:
                break
```

「停止アドレス, レジスタ(&スタックポインタ)を得る」は、前節で説明した関数を呼んでいるだけなので、その次、「アドレスが含まれる関数情報を得る」から順に見ていきます。

## アドレスが含まれる関数情報を得る

とあるアドレスから、そこが含まれる関数を得るためのDWARF攻略ルートとしては、

- 全CU/DIEを舐めてまわり、ヒットするアドレス範囲を見つける
- アドレスからDIEを引く

の２通りがあります。後者はまさに今回の目的のための方法で、[DWARFv4 6.1.2 Lookup by Address](http://www.dwarfstd.org/doc/DWARF4.pdf#%5B%7B%22num%22%3A347%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C0%2C792%2Cnull%5D)にて説明されているように、`.debug_aranges`セクションに対応テーブルが書かれています。
ただ残念なことに`pyelftools`では`.debug_aranges`に[対応していません](https://github.com/eliben/pyelftools/wiki/User's-guide#dwarf)。ということで、愚直にCU/DIEを探して回ることにします。

```python
def get_func_info(dwarf_info: DWARFInfo, addr: int) -> Optional[Dict]:
    """
    addr で示されたアドレスが含まれる関数情報を取得する
    :param dwarf_info: DWARF情報
    :param addr: プログラムカウンタ
    :return: 関数名・アドレスなどの関数情報
    """

    # それぞれのコンパイルユニットから
    for cu in dwarf_info.iter_CUs():
        # DIEをイテレートしながら、
        for die in cu.iter_DIEs():
            try:
                # 関数のDIEを探して、
                if die.tag == 'DW_TAG_subprogram':
                    # 関数が占めるアドレス範囲を探す
                    low_pc = die.attributes['DW_AT_low_pc'].value
                    high_pc_attr = die.attributes['DW_AT_high_pc']
                    high_pc_attr_class = describe_form_class(high_pc_attr.form)
                    if high_pc_attr_class == 'address':
                        high_pc = high_pc_attr.value
                    elif high_pc_attr_class == 'constant':
                        high_pc = low_pc + high_pc_attr.value
                    else:
                        print('Error: invalid DW_AT_high_pc class:{}\n'.format(high_pc_attr_class))
                        continue

                    # 指定されたアドレスがこの関数範囲にマッチしていればビンゴ
                    if low_pc <= addr < high_pc:
                        ret = dict()
                        ret["addr"] = addr
                        ret["cu"] = cu
                        ret["func_name"] = die.attributes['DW_AT_name'].value.decode("utf-8")
                        ret["func_addr"] = low_pc
                        ret["offset_from_func"] = addr - low_pc
                        ret.update(get_file_line_from_address(cu, addr))
                        return ret
            except KeyError:
                continue
    return None
```

全CompileUnitから、DIEを検索して関数を表すDIE `DW_TAG_subprogram` をイテレートしていきます。関数が占めているアドレス範囲は、[2.17 Code Addresses and Ranges](http://dwarfstd.org/doc/DWARF4.pdf#%5B%7B%22num%22%3A137%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C0%2C792%2Cnull%5D)にその仕様が書かれています。
区間を示す属性[`DW_AT_low_pc`, `DW_AT_high_pc`)で単一のアドレス範囲として示されるか、最適化などで不連続な複数の範囲になっていた場合、`DW_AT_ranges`で範囲が指定されるとあります。
ここはひとまず単一のアドレス範囲だけに対応しておきます。`DW_AT_ranges`が出てきた場合はその時実装しましょう。

ここから属性だとかクラスだとか、ドメイン固有の言葉が乱立してきますので、一旦整理しておきます。

<dl>
    <dt>CompileUnit(CU)
        <dd>コンパイルする単位。Cならソースファイル単位。
    <dt>DIE
        <dd>デバッグ情報の構造体で、親子関係のツリーになっている。CUごとに１つのDIEツリーがある。
        いろいろ種類があるが、大まかに<code>DW_AT_TAG_*</code>で区別される。
    <dt>属性(<code>DW_AT_*</code>)
        <dd>DIEに含まれる情報要素。名前とかアドレス範囲とか。
    <dt>クラス(class)
        <dd>属性が表現する意味。<code>address</code>とか<code>constant</code>とか<code>string</code>とか。
    <dt>形式(<code>DW_FORM_*</code>)
        <dd>実体としてどのような形で保持されているのかを示す。<code>DW_FORM_data2</code>なら2バイトの値、<code>DW_FORM_data4</code>なら4バイトの値。
</dl>

これらの用語を使って関数の先頭アドレスの探し方を表現するならば、

>main.cのCUについて、てっぺんのDIEから辿って行くと、main関数のDIEにたどり着く。このDIEのタグは`DW_TAG_subprogram`、`DW_AT_name`属性は"main"。`DW_AT_low_pc`属性としては`DW_FORM_addr`という形の`address`クラスの値を持っている。それはすなわちmain関数の先頭アドレス。

となります。

先頭アドレスはわかりましたので、次に末尾側、`DW_AT_high_pc`属性を見ていきます。
[2.17.2 Contiguous Address Range](http://dwarfstd.org/doc/DWARF4.pdf#%5B%7B%22num%22%3A137%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C0%2C792%2Cnull%5D)によれば、`DW_AT_high_pc`属性は、クラスが`address`の場合と、`constant`の場合があります。
クラス`address`であれば、それは*the relocated address*ということで、ロードされたメモリ上のアドレスと考えてよいかと思います[^4]。クラス`constant`であれば、`DW_AT_low_pc`からのオフセットアドレスを示していることになります。

[^4]: gdbが動く際はASLRは無効になっていると思いますので、リンク時の言い値そのままになっているはずです(共有ライブラリとかちゃんと考えてないので若干ゃ自信なし)

以上でこの関数の先頭・末尾アドレスがわかったので、探している関数がこれなのかどうか判断できます。

### アドレスからソースファイル名・行番号を探す

関数名とアドレスは分かったのですが、ソースファイルとの対応はどうすれば良いのでしょうか。

[6.2 Line Number Information](http://www.dwarfstd.org/doc/DWARF4.pdf#%5B%7B%22num%22%3A350%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C0%2C792%2Cnull%5D)によると、`.debug_line`セクションにアドレス→ソースコードへの変換表が有ることがわかります。
基本的なアイディアとしては、オブジェクトのアドレスからソースコードファイル名・行・桁番号への参照テーブルを用意すればよいでしょう。がしかし、単純にそのようなテーブルを作ると、下のようにオブジェクトの数倍以上の巨大なテーブルになってしまいます。

| アドレス | ソースファイル名 | 行数 | 桁数 |
|----|---------------|----|----|
|0x00abcd|main.c|10|8|
|0x00abce|main.c|11|10|
|0x00abcf|main.c|11|10|
|0x00abcg|main.c|12|8|
|0x00abch|main.c|12|8|
|0x00abci|main.c|13|8|


そこでDWARFでは、以下の2つの方法で格納サイズの削減を行っています。

* 単純に、重複行は省略する

| アドレス | ソースファイル名 | 行数 | 桁数 |
|:----|:---------------|:----|:----|
|0x00abcd|main.c|10|8|
|0x00abce|main.c|11|10|
|0x00abcg|main.c|12|8|
|0x00abci|main.c|13|8|

マシン命令が複数バイトであった場合に重複行を削ることで、サイズを節約します。

* スタックマシンを設計

テーブルを記録せずに独自のスタックマシンを設計し、それを用いて記録サイズを節約します。

```
＿人人人人人人人人人人人人＿
＞　スタックマシンを設計　＜
￣Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y￣
```

いきなりの超展開になりましたが、幸い`pyelftools`ではスタックマシンを動かしてアドレス・行数テーブルに展開してくれるので、それを有りがたく使わせていただきます。実際には[class LineProgram](https://github.com/eliben/pyelftools/blob/master/elftools/dwarf/lineprogram.py#L71)このあたりで、スタックマシンを動作させています。

ということで、アドレスからソースファイル名・行数を得る関数が以下になります。

```python
def get_file_line_from_address(cu: CompileUnit, addr: int) -> Dict:
    """
    compile unit から、ソースコードのファイル名・行数情報を探す
    :param cu: compile unit 情報
    :param addr: オブジェクト中のアドレス
    :return: ソースコードのファイル名・行数
    """

    top_die = cu.get_top_DIE()  # type: DIE

    # コンパイル時のディレクトリ。
    # ソースパスはこのディレクトリを基準に相対表記されている
    if "DW_AT_comp_dir" in top_die.attributes.keys():
        comp_dir = top_die.attributes["DW_AT_comp_dir"].value.decode('utf-8')
    else:
        comp_dir = ""

    line_program = cu.dwarfinfo.line_program_for_CU(cu)  # type: LineProgram

    for entry in reversed(line_program.get_entries()):  # type: LineProgramEntry
        if entry.state is not None and not entry.state.end_sequence:
            if entry.state.address < addr:
                # entryのアドレス範囲に、探しているアドレスが含まれていた

                # ファイルのフルパスを求める
                fe = line_program["file_entry"][entry.state.file - 1]
                name = fe.name.decode('utf-8')
                if fe.dir_index != 0:
                    # コンパイル時ディレクトリでなく、違うディレクトリ(相対パスで表記)にソースが有る場合
                    d = line_program["include_directory"][fe.dir_index - 1].decode('utf-8')
                else:
                    d = ""

                path = posixpath.normpath(posixpath.join(comp_dir, d, name))

                ret = dict()
                ret["path"] = path
                ret["line"] = entry.state.line
                return ret

    return dict()
```

## スタックフレーム情報から、呼び出し元アドレスと、呼び出し直前のレジスタ状況を得る

さてここからが本番です。呼び出しを遡るためには、

* 呼び出し元のアドレス
* 呼び出し元のスタックポインタ
* 呼び出し規約により、復帰時に戻す約束になっているレジスタの保存場所

これらの情報が必要です。

基本的なアイディアとしては、例によって巨大なテーブルを持っておけば解決です。例えば

|アドレス| 呼び元のスタックポインタ | 復帰すべきレジスタr0 | 復帰すべきレジスタr1 | 呼び元アドレス|
|:--|:--|:--|:--|:--|
|0x100|..|..|..|..|
|0x101|..|..|..|..|
|0x102|..|..|..|..|
|0x103|..|..|..|..|

この様な巨大テーブルを作っておくと、関数を進むにつれ刻一刻とレジスタ・スタックの消費状況が変わる中、任意の番地において呼び元に戻るための情報が復元できることになります。

ここでちょっと用語の定義になりますが、関数呼び元に戻った時のスタックポインタのてっぺんをCFAと呼ぶ、とざっくりと定義します。正確には:
[6.4 Call Frame Information](http://dwarfstd.org/doc/DWARF4.pdf#%5B%7B%22num%22%3A398%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C0%2C792%2Cnull%5D)
>An area of memory that is allocated on a stack called a “call frame.” The call frame is identified by an address on the stack. We refer to this address as the Canonical Frame Address or CFA. Typically, the CFA is defined to be the value of the stack pointer at the call site in the previous frame (which may be different from its value on entry to the current frame).

>スタック上に確保されたメモリ領域を"call frame"と呼びます。call frameはスタック上のアドレスとして識別されます。この識別のためのアドレスをCFA(基準のフレームアドレス)と呼びます。典型には、CFAは関数呼び出し直前のスタックポインタの値になります。

ということで、*典型的には*という点が引っかかりますが、ざっくり理解ですすめてしまいます。

さて、例によってDWARFではこのテーブルをスタックマシンを用いて圧縮していますが、実際の作業は`pyelftools`がやってくれます。展開方法について詳細を書き出すと終わりが見えないので、ざらっと展開したテーブルを追っかける雰囲気だけを説明していきます。

まず`.debug_frame`セクションに記録されている`LZ4_compress_fast()`関数の情報を`eu-readelf -w`で表示してみました。`Program`ってある部分がスタックマシンのコードです。

```
[    70] CIE length=20
   CIE_id:                   0
   version:                  3
   augmentation:             "zR"
   code_alignment_factor:    1
   data_alignment_factor:    -8
   return_address_register:  16
   Augmentation data:        0x3 (FDE アドレスエンコード udata4)

   Program:
     def_cfa r7 (rsp) at offset 8
     offset r16 (rip) at cfa-8
     nop
     nop
 :
 :
[   470] FDE length=44 cie=[    70]
   CIE_pointer:              1028
   initial_location:         0x00000000004046a3 <LZ4_compress_fast>
   address_range:            0xa1

   Program:
     advance_loc4 1 to 0x1
     def_cfa_offset 16
     offset r6 (rbp) at cfa-16
     advance_loc4 3 to 0x4
     def_cfa_register r6 (rbp)
     advance_loc4 156 to 0xa0
     def_cfa r7 (rsp) at offset 8
     nop
     nop
     nop
     nop
     nop
     nop
     nop
```

ここからアドレス・レジスタ対応表を復元することになりますが、pyrlftoolsでデコードすると以下の形にまで展開してくれます。

```python
# entries = cu.dwarfinfo.CFI_entries()
# entry.cie.header
Container({'version': 3,
           'code_alignment_factor': 1,
           'augmentation': b'',
           'length': 20,
           'data_alignment_factor': -8,
           'CIE_id': 4294967295,
           'return_address_register': 16})
# entry.decoded()
DecodedCallFrameTable(table=[{'pc':  0x4046A3,
                              'cfa': CFARule(reg=7, offset=8, expr=None)},
                              16:    RegisterRule(OFFSET, -8),
                             {'pc':  0x4046A4,
                              'cfa': CFARule(reg=7, offset=16, expr=None),
                              6:     RegisterRule(OFFSET, -16),
                              16:    RegisterRule(OFFSET, -8)},
                             {'pc':  0x4046A7,
                              'cfa': CFARule(reg=6, offset=16, expr=None),
                              6:     RegisterRule(OFFSET, -16)
                              16:    RegisterRule(OFFSET, -8),},
                             {'pc':  0x404743,
                              'cfa': CFARule(reg=7, offset=8, expr=None),
                              6:     RegisterRule(OFFSET, -16),
                              16:    RegisterRule(OFFSET, -8)}],
                      reg_order=[16, 6])
```

これをさらに表の形式にまとめたのが下表です。

ちなみに、ここでは戻り先を格納するレジスタreturn_address_registerとして16番、$ripに割り振られていますが、アーキテクチャによっては実体レジスタに割り当てられていない場合もあります。

|アドレス|CFA|r6 ($rbp)|r16 ($rip, return_address_register)|
|:----|:--|:--|:--|
|0x4046A3|r7+8|-|\*(CFA-8)|
|0x4046A4|r7+16|\*(CFA-16)|\*(CFA-8)|
|0x4046A7|r6+16|\*(CFA-16)|\*(CFA-8)|
|0x404743|r7+8|\*(CFA-16)|\*(CFA-8)|

実際にこの表を使って、`LZ4_compress_fast()`を呼んだ呼び元のアドレスを復元してみます。

```
(gdb) bt
#0  LZ4_compress_generic (acceleration=1, dictIssue=<optimized out>, dict=<optimized out>, tableType=<optimized out>, 
    outputLimited=<optimized out>, maxOutputSize=<optimized out>, inputSize=57, dest=0x61e010 "", 
    source=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", cctx=0x7fffffff9530) at lz4.c:578
#1  LZ4_compress_fast_extState (state=0x7fffffff9530, source=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", dest=0x61e010 "", 
    inputSize=57, maxOutputSize=73, acceleration=1) at lz4.c:739
#2  0x0000000000404722 in LZ4_compress_fast (source=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", dest=0x61e010 "", 
    inputSize=57, maxOutputSize=73, acceleration=1) at lz4.c:760
#3  0x0000000000404776 in LZ4_compress_default (source=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", dest=0x61e010 "", 
    inputSize=57, maxOutputSize=73) at lz4.c:771
#4  0x0000000000400957 in main () at simple_buffer.c:54
```

まずは`LZ4_compress_fast()`関数実行中のスタックフレームに移動します。

```
(gdb) frame 2
#2  0x0000000000404722 in LZ4_compress_fast (source=0x41b4b8 "Lorem ipsum dolor sit amet, consectetur adipiscing elit.", dest=0x61e010 "", 
    inputSize=57, maxOutputSize=73, acceleration=1) at lz4.c:760
760	    int const result = LZ4_compress_fast_extState(ctxPtr, source, dest, inputSize, maxOutputSize, acceleration);
```

この時の実行アドレスは0x404722なので、上の表をアドレスで検索すると

|アドレス|CFA|r6 ($rbp)|r16 ($rip, return_address)|
|:----|:--|:--|:--|
|0x4046A7|r6+16|\*(CFA-16)|\*(CFA-8)|

この行がマッチします。`r6 == $rbp`なので、 CFAの場所は `$rbp+16`です。で、`r16`は`CFA-8`なので、結局**return_address**は:

```
(gdb) x $rbp+16-8
0x7fffffffd568:	0x00404776
```

となるはずです。このアドレスは確かにフレーム#3の実行アドレスに一致していますので、呼び元アドレスを復元出来たことになります。

ここで若干の注意点があります。CFAの場所としてr6を参照していますが、これは呼び出し復用に復元したr6ではなく、今現在、0x404722実行時点でのr6になります。もしそうじゃなければr6を復元するためにCFAを基準にしているので、循環してしまいますし。

つまりは:

1. 今現在のレジスタの値を使ってCFAの場所を求める。
1. 現在の関数から復帰時に戻すべきレジスタの値を、上で求めたCFAの場所を使って求める。

という順で計算する必要があります。


以上ふまえ、処理を行っているのが以下の関数です。なお、ここではreturn_addressの復元・レジスタの復元に加え、スタックの巻き戻しも行っています。

```python
def get_prev_frame(cu: CompileUnit,
                   addr: int,
                   regs: List[int],
                   read_mem: Callable[[int], int]) -> Tuple[Optional[int], Optional[List[int]]]:
    """
    実行アドレス・レジスタおよびメモリ(主にスタック)から、スタックフレームを特定し、
    呼び出し元のアドレス、その時のレジスタを復元する
    :param cu: CU情報
    :param addr: 実行アドレス
    :param regs: DWARF Register Number でインデックスされたレジスタ一覧
    :param read_mem: メモリを読む関数。読み出しはポインタ(レジスタ)サイズ
    :return: 呼び出し元アドレスとレジスタ
    """

    if cu.dwarfinfo.has_CFI():
        entries = cu.dwarfinfo.CFI_entries()
    else:
        # .debug_frame が無い
        entries = []

    for entry in entries:
        if "initial_location" not in entry.header.keys():
            continue
        start = entry.header.initial_location
        end = start + entry.header.address_range
        if not (start <= addr < end):
            continue
        dec = entry.get_decoded()
        for row in reversed(dec.table):
            if row["pc"] <= addr:
                # 戻り先アドレスと、そのレジスタを復元する
                cfa_rule = row["cfa"]  # type: CFARule
                assert cfa_rule.expr is None, "DWARF表現未対応"
                cfa = regs[cfa_rule.reg] + cfa_rule.offset

                return_address_rule = row[entry.cie.header.return_address_register]  # type: RegisterRule
                assert return_address_rule.type == RegisterRule.OFFSET, "OFFSET以外未対応"
                return_address = cfa + return_address_rule.arg

                prev_regs = regs[:]
                for key, reg in row.items():
                    if isinstance(reg, RegisterRule):
                        assert reg.type == RegisterRule.OFFSET, "OFFSET以外未対応"
                        prev_regs[key] = read_mem(cfa + reg.arg)

                # スタック巻き戻し
                unwind_stack(prev_regs, cfa)
                return read_mem(return_address), prev_regs
    return None, None
```

# 動作確認

一通り完成しましたので、実行してみましょう。カレントディレクトリに`bt.py`を配置して、gdbからpythonモジュールを呼び出してみます。frameをずらしたままだとレジスタの値が変わっていますので、先頭フレームに戻しておくのを忘れずに!

```
(gdb) frame 0
(gdb) source bt.py 
#0  0x00000000004010a4 in LZ4_compress_fast_extState() at /home/oreore/lz4/lib/lz4.c:575
#1  0x0000000000404722 in LZ4_compress_fast() at /home/oreore/lz4/lib/lz4.c:760
#2  0x0000000000404776 in LZ4_compress_default() at /home/oreore/lz4/lib/lz4.c:771
#3  0x0000000000400957 in main() at /home/oreore/lz4/examples/simple_buffer.c:54
```

結構いい感じになってはいますが、よく見るとフレームが1こ足りないことに気づきます。
これはインライン展開をちゃんと解析していないためです。`LZ4_compress_fast_extState()`関数のなかに`LZ4_compress_generic()`関数がインライン展開されているのですが、それに気づかないまま`LZ4_compress_fast_extState()`関数としてデコードしているのです。

インラインを解釈するには`DW_TAG_inlined_subroutine`を真面目に見ていかなくてはならないのですが、それを書くには余白が足りないので一旦ここまでとします。

またパラメータも表示していません。こちらもこれはこれで`.debug_loc`セクションをみたりと結構やるべきことが多く、それを書くには(ry

# おわりに

けものフレンズ、続きが見たかったですね。。。