公開ハック/200610/レポート


Top / 公開ハック / 200610 / レポート

このページは何か? (by Tino)

2006年10月15日の公開ハックの作業レポートです。

作業に使用したソースコードは次の通りです。

1. 自動変数

自動変数の有無で出力されるアセンブリの変化を観察します。

やたらに複雑なアセンブリが出力されます。

2. main()は特殊

main()には起動関係のコードが自動追加されることを確認します。

1〜3.cppをそれぞれg++ -Sとしてアセンブリを出力させます。
差分を取ると、2と3はシンボル名だけの差ですが、1はそれ以外に色々な処理が入ることが分かります。

アセンブリの観察は簡単な方が良いため、main()に処理を書かずに、別の関数を呼び出すスタイルで進めます。

3. マングリング

4.cppから出力したtest()の該当アセンブリです。

__Z4testv:
	pushl	%ebp
	movl	%esp, %ebp
	popl	%ebp
	ret

test()という名前が__Z4testvという複雑なシンボル名になっています。
このマングリングの背景をオーバーロードに絡めて説明しました。
extern "C"でシンボル名が変化することと、オーバーロードできなくなることを確認しました。

シンボルをデマングラで確認しました。

$ c++filt __Z4testv
test()

4. 話を1に戻す

もともと自動変数がどのようにアセンブリに反映されるか確認するだけなのに、main()が冗長なのと、マングリングの説明とで脱線しました。そのため話を戻します。

5. Intel形式

gas(AT&T)形式のアセンブリに慣れないため、意味がすんなり読み取れませんでした。
アセンブリに深入りするのが目的ではないので、Intel形式で確認して済ませます。

$ g++ -c 5.cpp
$ ndisasm -u 5.o

【追記】こんなことをしなくても、g++ -masm=intel -S 5.cppとすればIntel形式で5.sが出力されます。

ここでndisasmに-uを付けていますが、これは32bitで解釈するという意味です。リアルモードとプロテクトモードでは同じバイナリでも違う意味(AX⇔EAX等)になるという背景を確認しました。

話を戻して、ndisasmの結果から該当部分だけを抜き出して確認します。

push ebp
mov ebp,esp
sub esp,byte +0x4
mov dword [ebp-0x4],0x1
leave
ret

やはりIntel形式の方がすんなり読めます。

6. leave

疑問点として、push ebpに対するpopがないというものが挙がりました。
念のためIntelのマニュアルで、leaveが以下と等価であることを確認しました。

mov esp,ebp
pop ebp

これに絡めてCISCとRISCの話をちょっとしたりと脱線しました。

7. 再度話を1に戻す

また脱線しました。今度こそ確認します。
簡単のため注目部分だけ以下に引用します。

  1. スタックに自動変数が格納されているということの意味を、具体的に確認しました。
  2. ebpとespの役割分担や、espをずらす理由としてpush(call等でも発生)で破壊されないようにすることなどを確認しました。
  3. ebpの存在理由が、自動変数のスタックであることと、そのABIを念頭に設計されたものであることを確認しました。

8. debug

espではなくebp経由でアドレス演算している背景として、アセンブリに許可される組み合わせが限定的であることを確認しました。

手軽に済ませるため、16bitであることを割り切った上で、debugコマンドを使用しました。

>debug
-a
2CE1:0100 mov [sp+4],ax
               ^ エラー
2CE1:0100 mov [bp+4],ax
2CE1:0103
-q

9. ポインタ

自動変数とスタックの概念を確認したので、次はポインタにメスを入れます。

  1. callのアドレスはPEリンカが解決するため不定であることを確認しました。
  2. x86のABIでは、引数をスタックに積んで渡すことと、関数の戻り値がEAXで渡されることを確認しました。
    • これに絡めて、x86-64のABIでは増えたレジスタに役割が割り振られる等、少しだけ脱線しました。

10. ポインタは整数値

上の例ではいきなりcall等が絡んでいたため、ポインタが自動変数として扱われている部分の具体的イメージが把握しきれませんでした。
そのため意味のないコードで確認を試みました。

これは余計に混乱を招きました。しかし理解しなくては先に進めません。
あーでもない、こーでもない、と1時間くらいすったもんだの挙げ句、32bitではポインタはintと等価であって、アセンブリに型の概念がないということで割り切りました。

Tinoやひげぽんさんは「自分では理解できるけど、どうやって説明して良いのか分からない」と、説明することの難しさを痛感しました。

こんな説明をネット上でやったら確実に発散したでしょう。。。
ここが今回の最大の山場でした。

以上でスタックと自動変数の関係をアセンブリで確認するのは終了です。

11. ポインタのポインタ

ここからはアセンブリではなくprintf()でアドレスを確認しながら進めます。

void* aに対する&aという意味を、int aに対する&aと比較しています。
また、前者がvoid**であるということなども取り上げました。

これは直感的に理解しにくいため、またまた引っ掛かりました。
「10. ポインタは整数値」と絡めて、ポインタは単なる整数値として見るということで、どうにか収まりました。

12. GCのイメージ

こんなコードでGCが働くのかなというイメージです。

new int;が無駄なので、GCで消されるべきという意味です。
一般見学者の方から、3番目のnew int;などと代入せずに単発で書くのは初めて見たという感想がありました。
こんな無意味なコードを書くことは普通ないので、当然ですが。。。

13. newの上書き

newの挙動を変えてGC対応にするため、独自定義しました。

もちろんこれだけでは何の意味もありません。
ここを出発点に意味を持たせていきます。

14. スタック領域の取得

散々見てきたアセンブリのコードから、ESP〜EBP間に自動変数が格納されていると考えられます。EBPは起動直後のものを採取すると正確です。それを実際に確認してみます。

自動変数がESP〜EBP間のスタックに収まっていることが確認できました。

15. スタックの内容を見る

スタック(ESP〜EBP間)の内容をダンプして確認しようとしました。
試行錯誤の過程が14.cppですが、(int)esp[-1]などと逆を向いているなど、本当に試行錯誤です。

結局、Cygwinのgdbに付属するinsightでメモリやレジスタの内容を確認しました。ひげぽんさんから生のgdbを使うように忠告されましたが、今回のケースで便利だと思えなかったので見送りました。というか生のgdbはコアダンプしたときのbtくらいしか使い方を知りません。。。

注意点として、デバッガを使うときは-gを付けてコンパイルすることを確認しました。

16. マーク&スイープ

以下のアルゴリズムで検出を試みます。

  1. newで確保した領域をリスト(1)で保持する。
  2. GCを呼ぶと、スタックを走査して、リスト(1)と合致するポインタをリスト(2)に列挙する。
  3. リスト(2)に列挙されなかった領域を削除対象と見なす。
  1. このようなアルゴリズムをマーク&スイープと呼ぶということを確認しました。
  2. たまたまポインタと同じ値が検出される可能性は排除できません。
    • 少し余分に残っても実害はメモリが少し余分に使われるくらいです。逆に余計に消して落ちてしまうのは大問題なので、どちらがましかとなると前者です。このような方針を「保守的なGC」と呼ぶことを確認しました。
    • 実際にはたまたま一致する可能性は極めて少ないので、無視してもほとんど問題ないと言われています。
  3. リストにstd::vectorを使ったところ、newを上書きしているのと干渉して無限ループに陥ってしまいました。
    • 結局BayOS独自のリストクラス(List.h)を持って来て、その中のnew/deleteをmalloc/freeに置き換えることで対処しました。

17. リファクタリング

リストを2つ持って判定していますが、より「マーク」するという感覚に近付けるため、確保領域の先頭に独自ヘッダを挟んでマーク領域としました。

実行結果は15.cppと同じです。

以上でGCの基本となる実装は出来たので、お開きとしました。

18. 今後の展望

  1. リファクタリングを進めて構造を綺麗にする。
    • ポインタの検出がリストのリニアサーチなので、それをハッシュ化する等。
    • アドレスを8bitごとに区切って、使用している所だけをリストとして保持するのが良いのではないかという話をしました。
  2. フィールドとして保持しているポインタをマークするため、検出されたポインタの領域を再帰的に走査する。←極めて重要
    • スタックの自動変数はルートで、そこからフィールドが枝分かれしているイメージ。
    • 実はこの話をするのを忘れていました!本当にごめんなさい!
  3. マルチスレッドに対応する。(後述)

19. マルチスレッド

もともとGCのマルチスレッド対応が課題としてありました。
そのためにGCを自分で実装して理解する目的での公開ハックです。
無事にアルゴリズム理解の目的は達成されました。

今後の課題として、マルチスレッド対応の問題点を挙げました。

  1. スレッドごとにスタックが別々の領域にある。
  2. GC中にスレッドを一時停止しないと結果の正確さが保証できない。
    • 任意に一時停止できない場合の簡単な回避策として、自分のスレッドでnewしたものしかGCの対象にしないという方針を確認しました。
    • 上の方針では、他のスレッドと共有するインスタンスは、利用するすべてのスレッドが継続している間はGCされてしまわないように、コードを書く側で注意する必要があります。
    • 簡単な回避策の1つとして、必要なインスタンスは即座にコピーするというものがあります。この手のテクニックはパターンがあるのでそれほど難しいものではないはずだということを確認しました。

20. スレッドとスタック

話がちょっと横路にそれて、スレッドごとのスタック領域は、同じアドレスをページングで切り替える実装があるらしい(未確認)という話になりました。

ためしにWindowsでどうなっているかを調査してみました。

$ g++ -mno-cygwin threadstack.cpp && ./a
[main] esp = 22fed0, ebp = 22ff78
[sub] esp = 6aff68, ebp = 6aff80
[sub] esp = 8aff68, ebp = 8aff80
[sub] esp = aaff68, ebp = aaff80
[sub] esp = caff68, ebp = caff80
[sub] esp = eaff68, ebp = eaff80
[sub] esp = 10aff68, ebp = 10aff80
[sub] esp = 12aff68, ebp = 12aff80
[sub] esp = 14aff68, ebp = 14aff80
[sub] esp = 16aff68, ebp = 16aff80
[sub] esp = 18aff68, ebp = 18aff80
[sub] esp = 1aaff68, ebp = 1aaff80
[sub] esp = 1caff68, ebp = 1caff80
[sub] esp = 6aff68, ebp = 6aff80
[sub] esp = 8aff68, ebp = 8aff80
[sub] esp = aaff68, ebp = aaff80
[sub] esp = caff68, ebp = caff80

この結果から推測します。

  1. スレッドごとのスタックはアドレス自体が違って、ページングされてはいない。
  2. 終了したスレッドのスタック領域は、新しいスレッドで再利用される。

Linuxでどうなっているかはひげぽんさんが調査中です。
移植の参考としてWin32スレッドとpthreadを#ifdefで並べたクラスを提供しました。

Gakuさんとひげぽんさんが、ページングの影響を議論していました。

21. スタイル

現地で見ていた人には一目瞭然なのですが、エディタで書きながら、コマンドプロンプトでビルド&ランという原始的なスタイルでやりました。Makefileも書いていません。簡単なテストはこれくらいで充分ではないかという割り切りです。シンプルなスタイルだったため、特に敷居もなくTinoとbaysideさんの間で合意が得られました。

他人がどんなスタイルでやっているのかというのは、オンラインでは絶対に見ることができないので、これだけでも公開ハックの意義はあったと思いました。

22. その他

ひげぽんさんと話し合うと、ネットでは見過ごしていた行き違いがボロボロと出て来ました。これじゃ話が噛み合わないわけだ。。。

Tinoの話術を向上させることが今後の課題として残りました。。。

あと素朴な感想として、皆さんの実際の口調がネット上の発言と同じだということが、ちょっと意外でした。ネット人格とか変な先入観を持ちすぎですね。。。

以上でTinoによるレポートを終わります。

コメント

最新の1000件を表示しています。 コメントページを参照

お名前:
  • 16.cppのdelete [] temp_list;が落ちていた問題ですが、operator delete()の実装でfree(p)としていたのに問題がありました。pはヘッダとして挟んだboolの分だけずらす必要があります。operator new[]()やoperator delete[]()も実装する必要があります。また、List.hでdelete []の置き換え漏れがありました。これらを修正したものを置いておきます。file16.cppfileList.h>baysideさん -- Tino 2006-10-16 (月) 14:56:51
  • 「フィールドとして保持しているポインタをマークするため、検出されたポインタの領域を再帰的に走査する。」というのは sms_gc でやっていますか?もしやっているならどの辺りのソースを参考にしたらよいか教えてください。 -- bayside 2006-10-16 (月) 13:43:29
    • やっています。sms_gc_collect_internal()です。 -- Tino 2006-10-16 (月) 14:50:47
    • 簡単に説明します。class Foo { Bar* a; };のようなクラスでFoo* f = new Foo();とした場合に、f(スタック)だけでなく、f->a(ヒープ)の値も調べないといけないということです。そうしないとf->aがマークされずにスイープされてしまいます。 -- Tino 2006-10-16 (月) 14:53:35
    • というわけで次はnew int;だけでなく、上で書いたFoo* f = new Foo;f->a = new Bar;のようなものを処理できるようにする必要があるでしょう。 -- Tino 2006-10-16 (月) 15:04:06

MENU

now: 1

リンク


最新の20件
2018-05-03 2017-09-29 2017-04-25 2017-01-10 2016-12-11 2016-10-04 2016-08-14 2016-06-05 2016-05-29 2016-04-15 2015-12-28 2013-02-25 2013-02-21 2013-02-20 2013-02-12 2013-02-11 2013-02-10
最新の20件
2010-02-01 2010-01-31 2010-01-30 2010-01-29 2010-01-16

Counter: 2978, today: 1, yesterday: 0

添付ファイル: fileList.h 647件 [詳細] file16.cpp 603件 [詳細]

リロード   新規 編集 凍結 差分 添付 複製 改名   トップ 一覧 検索 最終更新 バックアップ   ヘルプ   最終更新のRSS

Last-modified: 2008-03-28 (金) 15:48:03 (3709d);  Modified by mona
PukiWiki 1.4.6 Copyright © 2001-2005 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji
Powered by PHP 5.2.17
HTML convert time to 0.126 sec.