Jun 18

一つ前のエントリの続き。gccの_Unwind_Backtrace()には、フレームポインタなしでコンパイルされたコードに対しても動くという特長がある。はじめは、最初のフレームのときだけbuiltin関数に頼った後はレジスタの値を復元しながら巻き戻していくのでそういうこともできて当然、くらいに思っていたのだが、調べてみたらかなりtrickyだということが判明した: (少なくともFreeBSD/i386の場合)フレームポインタなしでコンパイルすると、gccは各フレームにおけるスタックの伸縮状況を細かく記録するFDEを作る。_Unwind_Backtrace()で巻き戻すときは、レジスタの状況にはほとんど頼らず、一つ前のフレームにおけるスタックの開始位置から、FDEに記録されている現在のフレームのスタックのサイズ分を差し引いて、直接現在フレームのスタックの位置を計算している。
単に_Unwind_Backtrace()を使うだけなら、こんなことまで知ってる必要はまったくないのだが、せっかく時間をかけて調べたのでこれもメモとして残しておくことにする。

フレームポインタの有無とbacktrace

i386やx86_64などでフレームポインタが使える場合には、お手軽かつより効率よくbacktrace情報を入手することができる。ebpやrbpレジスタがフレームポインタを指すようにバイナリが生成されていれば、まずなんらかの方法(インラインアセンブリなど)でこれらのレジスタの値を入手し、あとは以下のようにして順番にフレームをたどっていけばよい。

/* 最初にebpにレジスタの値をコピー */
while (ebp != NULL) {
	retaddr[i++] = ((void **)ebp)[1];
	ebp = *ebp;
}

しかし、この方法には、実行コードがフレームポインタを使わないような最適化を用いて生成されている場合には使えないという欠点がある。gccだと-fomit-frame-pointerオプションを付けてコンパイルしたバイナリではこの最適化が有効になる。

たとえば以下のような(何もしない)プログラムをi386で何も指定せずにコンパイルすると

void
foo() {
	return;
}

生成されるコードは以下のようになる

foo:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$8, %esp
	leave
	ret

すなわち、まずebpレジスタをスタックに積み(この時点ではebpには一つ上のスタックフレームのアドレスが入っている)、次いで積んだ場所(スタックポインタの値)をebpにコピーする。これにより*(void **)$ebpが一つ上のフレームのアドレスを指すことになる。また、スタック内の直前(一つ奥)の位置には関数からの戻りアドレスが入っているので、((void **)$ebp)[1]でこのアドレスが得られる。

一方、-fomit-frame-pointer付きでコンパイルすると以下のようになる:

foo:
	ret

(つまり、本当に「何もしない」関数になる)。当然、ebpレジスタにはでたらめな値が入っているのでこれは使えないし、仮にスタックの始点がわかったとしても、その場所に一つ上のフレームへのポインタが入っているわけではないので、backtraceの処理を再帰的に継続するための役には立たない。

i386の場合、関数へのすべての引数がスタックに積まれていて、フレームポインタなしだとかえって効率の悪いコードになることもあるせいか、この最適化が使用される例は稀なようだが、x86_64では引数が少ない場合はレジスタ渡しになるためにより積極的に用いられる傾向があるらしい。実際、x86_64のDebianでgccに-O2を付けてコンパイルすると自動的に-fomit-frame-pointer相当の最適化が用いられるようだ。

_Unwind_Backtrace()は、こういう場合でも利用できる。たとえば、一つ前のエントリで示した検証用のプログラムは-fomit-frame-pointer付きでコンパイルしても動作する:

% cc -fomit-frame-pointer -g -o unwindtest unwindtest.c

% ./unwindtest -e
frame[0] 0x8048eda: entrance pt=0x8048eac, diff=46
frame[1] 0x8048fa0: entrance pt=0x8048f98, diff=8
frame[2] 0x8048fd6: entrance pt=0x8048fa4, diff=50

以下はその仕組みの詳細について調べた結果の詳細。

gcc builtin関数とフレームポインタ

まず、_Unwind_Backtrace()が依存しているgccのbuiltin関数がフレームポインタなしでも動くことを確認する必要がある。

__builtin_return_address(0)は、(実装は見てないけど)コンパイル時の文脈によって動作を変えるようになっているらしく、たとえばフレームポインタが利用できるかどうかによって生成するコードを変えている。

たとえば、以下のようなプログラムをi386で何も指定せずにコンパイルすると

void *foo() {
	void *p = __builtin_return_address(0);
	return (p);
}

生成されるコードは次のようになる。

foo:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$4, %esp
	movl	4(%ebp), %eax
	movl	%eax, -4(%ebp)
	movl	-4(%ebp), %eax
	leave
	ret

ここではebpレジスタをフレームポインタとして使えるので、__builtin_return_address(0)4(%ebp) (= ((void **)$ebp)[1])に展開されていることがわかる。

一方、同じプログラムを-fomit-frame-pointer付きでコンパイルして生成されるコードは以下のようになる。

foo:
	subl	$4, %esp
	movl	4(%esp), %eax
	movl	%eax, (%esp)
	movl	(%esp), %eax
	addl	$4, %esp
	ret

この場合はebpポインタをあてにできないので、スタックポインタをスタックのサイズ分だけ巻き戻した位置に格納されている値4(%esp) (= ((void **)$esp)[1])__builtin_return_address(0)の値になっている。フレームポインタを使っていないので、この位置には戻りアドレスが格納されているはずで、これは正しい値である。

以上のように、__builtin_return_address(0)はフレームポインタの有無に関わらず正しい戻りアドレスを返すことがわかる。詳細は省略するが、__builtin_dwarf_cfa()も文脈によって挙動が変わるようになっていて、フレームポインタが利用できなくても正しく動作する。

フレームポインタに頼らないDWARF2処理(予備知識)

gccのbuiltin関数を使って最初(最下層)のフレームの情報を得た後は、DWARF2(もどき)のフレーム情報をもとにフレームを遡ることになる。

この動作を、前回示した検証用プログラムにおいてshow_backtrace()からbar()に遡る部分について具体的に確認してみる。これを理解するためには、DWARF2の仕様とgccのunwindにおけるその実装に関する知識が多少必要になる。

  • CFA: Canonical Frame Address. 各フレームで利用するスタック領域の始点(=底)を指すアドレス。ただし、gcc unwindにおけるCFAの定義は一般的なイメージでのスタックの始点とは違っているようで、i386の場合でいえば「戻りアドレスが入っている場所 + 4バイト」の位置が使われている。フレームポインタのある場合なら$ebp + 8になる。
  • レジスタ: DWARF2では、対象とするマシンの状態を模倣するために使う仮想的なレジスタを管理している。i386の場合、r0からr17までの18個のレジスタが使われている。これらのうち、ここでの議論で必要になる特別なレジスタは以下の2つ:
    • return address register: 一つ上のフレームへの戻りアドレスを格納するレジスタ
    • CFAのオフセット計算に用いるレジスタ。DWARF2の処理の途中でCFAが必要になったら、このレジスタの値に与えられたオフセットを加えて求める。

gccの実装の中では、DWARF2の内部状態をcontextというstruct _Unwind_Context *型の変数で参照していることが多い。context->cfaがCFAであり、レジスタ群はcontext->reg[]という配列になっている。

また、CIEとFDEで決まる各フレームごとの状態は_Unwind_FrameStateという構造体に格納されている。これはしばしばfsというポインタを通じて参照される。fs->cfa_regがCFAのオフセット計算で使うレジスタの番号(context->regの配列インデックス)、fs->retaddr_columnがreturn address registerの番号になる。また、CFAを求める際に使うオフセット値としてはfs->cfa_offsetが使われる。

フレームポインタに頼らないDWARF2処理(本編)

_Unwind_Backtrace()がフレームを遡っていく際には、起点となるフレーム内のアドレス(これは_Unwind_Backtrace()自身)をもとに、対応するFDE(とそれに付随するCIE)を求め、CIEのinstruction、FDEのinstructionの順にDWARF2上のレジスタを操作する。その結果としてreturn address registerには一つ上のフレーム内の戻りアドレスが格納され、CFAを求めるためのレジスタも一つ上のフレームにおけるCFAを計算するための値に更新される(フレームポインタがある場合なら、フレームポインタのレジスタをpopする操作に相当する)。

いま考えている例、つまりshow_backtrace()からbar()に遡る場合にどういう操作が起きているかを調べるために、まずshow_backtrace()のCIEとFDEの内容を見てみる。

% readelf --debug-dump=frames unwindtest(実行ファイル名)

などとすると、.eh_frameと.debug_frame sectionの内容が人間が読める形式(といってもDWARF2の仕様を知らなければほとんど暗号だが)でダンプされるので、それを参照するとこんな感じになる:

CIE
  Return address column: 8
  DW_CFA_def_cfa: r4 ofs 4
  DW_CFA_offset: r8 at cfa-4

FDE cie=00000000 pc=08048e6c..08048eab
  DW_CFA_advance_loc: 3 to 08048e6f
  DW_CFA_def_cfa_offset: 32
  DW_CFA_advance_loc: 34 to 08048e91
  DW_CFA_def_cfa_offset: 40
  DW_CFA_advance_loc: 5 to 08048e96
  DW_CFA_def_cfa_offset: 44
  DW_CFA_advance_loc: 5 to 08048e9b
  DW_CFA_def_cfa_offset: 48
  DW_CFA_advance_loc: 8 to 08048ea3
  DW_CFA_def_cfa_offset: 32

(なお、ここでの話に関係ない出力を削るなどして一部簡略化している)

まず、CIEのinstructionによれば、

  • CFAはレジスタr4の値+4(gccの内部的には*((void **)context->reg[4]))
  • 一つ上のフレームへの戻りアドレスはr8に格納される
  • r8の値はCFA – 4番地に格納されている

ことがわかる。つまり、戻りアドレスがCFA – 4の位置に格納されているということで、これは前項で書いたi386におけるCFAの一般的な用法と合致する。

問題はFDEの部分で、これは結局コード内の5つの個所におけるスタックの伸縮の様子を記録しているだけのものになっていて、どのレジスタも更新されていない。したがって、CIEとFDEのinstructionを通じて更新されるレジスタはr8だけだということになる。

一方、一つ上のフレームに相当するbar()のFDEは以下のようになっている(なお、CIEは上と共通):

FDE cie=00000000 pc=08048eac..08048f95
  DW_CFA_advance_loc: 3 to 08048eaf
  DW_CFA_def_cfa_offset: 48
  DW_CFA_advance_loc: 11 to 08048eba
  DW_CFA_def_cfa_offset: 52
[...以下基本的にこのパターンの繰り返し]

すなわち、show_backtrace()と同様、スタックの伸縮が記録されているだけである。したがって、DWARF2の規則によれば、bar()のCFAはレジスタr4を用いて計算されるはずだが、r4はshow_backtrace()のフレームでの操作を通じて変更されていないので、当然正しい値ではあり得ない。

実は、gccの_Unwind_Backtrace()は、フレームポインタがない場合にはちょっと特別な処理をして独自にCFAを計算している。

その仕掛けはunwind-dw2.cuw_update_context_1()という関数の中にある以下の部分:

  /* Special handling here: Many machines do not use a frame pointer,
     [...]
     the value over from one frame to another doesn't make sense.  */

  _Unwind_SpTmp tmp_sp;

  if (!_Unwind_GetGRPtr (&orig_context, __builtin_dwarf_sp_column ()))
    _Unwind_SetSpColumn (&orig_context, context->cfa, &tmp_sp);
  _Unwind_SetGRPtr (context, __builtin_dwarf_sp_column (), NULL);

ここで、orig_contextuw_update_context_1()内での作業用に作られたcontextのコピー。__builtin_dwarf_sp_column ()はこの環境では4、つまりレジスタr4のインデックスを返す。_Unwind_SetSpColumn()は、この環境では、与えられたcontext(第一引数)のr4に指定された値(第二引数)を格納する。つまり、この特別扱い部分のコードは、レジスタr4が未定義であれば、orig_context内におけるr4には一時的に一つ前のCFAの値を保持するように設定している。また、次のフレーム以降r4の値が(CIEまたはFDEで設定されない限り)未定義になるように修正している。

この特別コードはshow_backtrace()の処理の部分でも走っている。show_backtrace()のCIE・FDE処理ではr4は更新されていないので、bar()の処理の段階ではifの中も実施されて、r4には一時的にshow_backtrace()のCFAが格納されている。この仕掛けを用いると、bar()のためのCFAは以下のようになる:

  show_backtrace()のCFA + bar()のFDEで指定されたオフセット

これで整合性が取れているかどうかを調べるために、bar()のアセンブリコードを見て実際のスタックの様子と付き合わせてみる。アセンブリコードは以下の通り(show_backtrace()を呼ぶ部分まで):

08048eac <bar>:
 8048eac: sub    $0x2c,%esp
 8048eaf: movl   $0x0,0x14(%esp)
 8048eb6:				
 8048eb7: sub    $0x4,%esp
 8048eba: push   $0xc
 8048ebc: push   $0x0
 8048ebe: lea    0xc(%esp),%eax
 8048ec2: push   %eax
 8048ec3: call   8048694 <_init+0xc4>
 8048ec8: add    $0x10,%esp
 8048ecb: sub    $0x8,%esp
 8048ece: push   $0x3
 8048ed0: lea    0xc(%esp),%eax
 8048ed4: push   %eax			
 8048ed5: call   8048e6c <show_backtrace>

したがって、show_backtrace()が呼ばれた時点でのスタックの様子は以下のようになっているはず:

sp0+4  <should be cfa for bar()>
sp0->  [retaddr in foo()]
...
sp0-44 (sub $0x2cの結果)
sp0-52 (sub $0x8の結果)
sp0-56 [0x3]
sp0-60 [%eax]  <cfa for show_backtrace()>
sp0-64 [retaddr in bar()]

ここで、bar()の開始時点でのスタックポインタの値をsp0としている。sp0には一つ上のフレームであるfoo()内への戻りアドレスの値が入っていて、sp0 + 4がbar()のCFAとなるはず。また、アセンブリコードの内容から、show_backtrace()が呼ばれた時点ではスタックはsp0から64バイトまで伸びていて、その位置にbar()に戻ってくるときのアドレスが格納されているはず。したがってsp0-60がshow_backtrace()におけるCFAの値となっているはずである。

この図によれば、修正すべきオフセットはsp0+4とsp0-60の差分である64となるはず。一方、実際のFDEの内容を見ると、

FDE cie=00000000 pc=08048eac..08048f95
  DW_CFA_advance_loc: 3 to 08048eaf
  DW_CFA_def_cfa_offset: 48
[...]
  DW_CFA_advance_loc: 5 to 08048ed5
  DW_CFA_def_cfa_offset: 64
  DW_CFA_advance_loc: 8 to 08048edd
  DW_CFA_def_cfa_offset: 48
[...]

というわけで、確かに64になっている(もっとも、ここまで愚直に確かめずとも、FDEがスタックの伸縮をコードに忠実に記録していて、CFAの位置が規則通りであれば、更新後のCFAの値も正しいことは明らかではある)。なお、FDEのinstructionは、実際にこのフレーム内で処理が進んでいる位置、すなわちshow_backtrace()のcallから戻る直前(8048ed5番地の直後)までのみ実施される。したがってオフセットが64になった状態でinstruction処理は止まっている。

しかし、これは結構際どい技だ…FDEのルールがスタックの様子を細かく記録していることを前提としてはじめて成立する方法なので。_Unwind_SetSpColumn()の場合、FDEを作るのも追いかけるのも実質gccだから問題ないけど、gccで吐いたコードを毛並の違うデバッガで追いかけたりするとはまることもありそうだ。

コメントを投稿 / Submit Comments



(あれば / Optional):