プロフィール

kosaki

Author:kosaki
連絡先はコチラ

ブログ検索
最近の記事
最近のコメント
最近のトラックバック
リンク
カテゴリー
月別アーカイブ
RSSフィード
FC2ブログランキング

スポンサーサイト このエントリーをはてなブックマークに追加

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。


スポンサー広告 | 【--------(--) --:--:--】 | Trackback(-) | Comments(-)

alternative マクロと自己修正コード このエントリーをはてなブックマークに追加

alternativeマクロについて

シーケンスロック その3 において

> alternativeマクロは興味深い動作をするので、回を改めて詳しく説明しますが、

などと書いておいて すっかり忘れていた alternativeマクロですがいい機会なので解説しましょう。
いつものように lxr.linux.no あたりからソースを引っ張ってきている。

linux/include/asm-i386/system.h より
288 /* 
289 * Alternative instructions for different CPU types or capabilities.
290 *
291 * This allows to use optimized instructions even on generic binary
292 * kernels.
293 *
294 * length of oldinstr must be longer or equal the length of newinstr
295 * It can be padded with nops as needed.
296 *
297 * For non barrier like inlines please define new variants
298 * without volatile and memory clobber.
299 */
300 #define alternative(oldinstr, newinstr, feature) \
301 asm volatile ("661:\n\t" oldinstr "\n662:\n" \
302 ".section .altinstructions,\"a\"\n" \
303 " .align 4\n" \
304 " .long 661b\n" /* label */ \
305 " .long 663f\n" /* new instruction */ \
306 " .byte %c0\n" /* feature bit */ \
307 " .byte 662b-661b\n" /* sourcelen */ \
308 " .byte 664f-663f\n" /* replacementlen */ \
309 ".previous\n" \
310 ".section .altinstr_replacement,\"ax\"\n" \
311 "663:\n\t" newinstr "\n664:\n" /* replacement */ \
312 ".previous" :: "i" (feature) : "memory")


これがalternativeマクロの定義ね。
はっはっは、これを見せると確実に引かれるので省いたのだよ。

見やすくするために、このマクロを展開してみる。

まず、こんなファイルをカット&ペーストを駆使して作る

main.c
#define alternative(oldinstr, newinstr, feature) 	\
asm volatile ("661:\n\t" oldinstr "\n662:\n" \
".section .altinstructions,\"a\"\n" \
" .align 4\n" \
" .long 661b\n" /* label */ \
" .long 663f\n" /* new instruction */ \
" .byte %c0\n" /* feature bit */ \
" .byte 662b-661b\n" /* sourcelen */ \
" .byte 664f-663f\n" /* replacementlen */ \
".previous\n" \
".section .altinstr_replacement,\"ax\"\n" \
"663:\n\t" newinstr "\n664:\n" /* replacement */ \
".previous" :: "i" (feature) : "memory")

#define X86_FEATURE_XMM2 57 /* dummy */
#define mb() alternative("lock; addl $0,0(%%esp)", "mfence", X86_FEATURE_XMM2)


main(){
mb();
mb();
}


X86_FEATURE_XMM2 の定義は適当にでっちあげたが、何、かまやしない。

これを -S 付きでコンパイル

 $ gcc -S main.c -o main.s 


出来上がったファイルがこちら

main.s
	.file	"main.c"
.text
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
andl $-16, %esp
movl $0, %eax
addl $15, %eax
addl $15, %eax
shrl $4, %eax
sall $4, %eax
subl %eax, %esp
#APP
661:
lock; addl $0,0(%esp)
662:
.section .altinstructions,"a"
.align 4
.long 661b
.long 663f
.byte 57
.byte 662b-661b
.byte 664f-663f
.previous
.section .altinstr_replacement,"ax"
663:
mfence
664:
.previous
661:
lock; addl $0,0(%esp)
662:
.section .altinstructions,"a"
.align 4
.long 661b
.long 663f
.byte 57
.byte 662b-661b
.byte 664f-663f
.previous
.section .altinstr_replacement,"ax"
663:
mfence
664:
.previous
#NO_APP
leave
ret
.size main, .-main
.section .note.GNU-stack,"",@progbits
.ident "GCC: (GNU) 3.4.4 20050721 (Red Hat 3.4.4-2)"


gccは親切なことに、asm文の範囲を#APPと#NO_APPで教えてくれています。
あとasm文が volatile修飾されているので素直にマクロが2つとも展開されています。

まず文法的な説明から
詳しくは

 $info gas 


で調べて欲しいが簡単に。

セクション切り替え
.section [section_name], "[FLAGS]"

FLAGS:
'a' allocatable, 実行時にメモリにロードされる。これがOFFなセクションってほとんど見ない
'x' executable, 実行可能

セクション名は任意のASCII名がつけれるが、"."(ドット) で初めておくのが
スカートのプリーツを乱さないと同じくらい、ここでのたしなみ。

.previous 1つ前の.section命令をキャンセルする。
つまり
.section .foo
.previous

.scction .foo
.text
と同じなのだけれど、最初が.text じゃなかったときもうまく動くのが利点。


ローカルなラベル
[positive_number]:

普通のラベルと違い、複数あられてもOKなラベル。
このラベルを参照するときは末尾に"f"か"b"をつける。
"f"は参照より後ろ(forward)で一番近いラベル、"b"は参照より前(backword)で一番近いラベルをあらわす。

.byte
.long
即値埋め込み命令。
.byte 57
とやればそのまんまバイナリに57という数字が埋め込まれる。
普通はC言語的な意味での「定数」をバイナリに埋め込むために使うが
たまに変態的な使い方として
x86プロテクトモードアセンブラの一部に16bitモードのアセンブラを埋め込みたいとか
ARMのアセンブラの一部にTHUMBコードを埋め込みたいとかいうバカ(褒め言葉)が
.byteを駆使して、実行コードを記述する例も見られる。

あ、話がそれた。

.align [argument]
後続のデータをargument byteにアライメントさせる。

また、この引数ではラベルへの参照と簡単な四則演算が使える。つまり

.long 661b
と書けばラベル661を前方参照してそのアドレスを埋め込む

.byte 662b-661b
と書けばラベル662のアドレス引く661のアドレス、つまりその範囲のコードの長さが埋め込まれる。
ここで、661bとかってのはローカルラベルだから、最初のmbと2番目のmbで661bの展開先が異なることには
注意していただきたい。
ここを理解しないと、何を埋め込んでいるのかサッパリ分からなくなってしまう。

つまり661bは引数oldinstrのアドレスになっていて、663fは引数newinstrのアドレスになる。


これを確かめるために、先ほどのmain.c をコンパイルして出来た実行ファイルをobjdumpしてみる

セクション:
索引名 サイズ VMA LMA File off Algn
(中略)
12 .altinstr_replacement 00000006 0804841c 0804841c 0000041c 2**0
CONTENTS, ALLOC, LOAD, READONLY, CODE
13 .fini 0000001a 08048424 08048424 00000424 2**2
CONTENTS, ALLOC, LOAD, READONLY, CODE
14 .rodata 00000008 08048440 08048440 00000440 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA
15 .altinstructions 00000017 08048448 08048448 00000448 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA


よしよし、.altinstr_replacement と .altinstructions がちゃんとあるな。

あっと、寄り道になるけど補足しておこう。
なぜか .altinstr_replacement と .altinstructions の順番が逆になっているけど
これはセクションフラグに"x"を入れたかどうかの違いが現れている。
gccは特に指定しないと"x"がONになっているコード部分を実行ファイルの前のほうに
寄せるんです。


次に .altinstructions セクションをダンプしてみる。
ファイル位置は0x448でサイズが0x17とobjdump君はいっているので

[mkosaki@centos alternative_macro]$ od -A x -t x1  -j 0x448 -N 0x17 a.out
000448 50 83 04 08 1c 84 04 08 39 06 03 00 56 83 04 08
000458 1f 84 04 08 39 06 03


ほれ、でてきた。これを「じーーー」っと見ると

50 83 04 08 1c 84 04 08 39 06 03 00 
56 83 04 08 1f 84 04 08 39 06 03
----------- ----------- - - - -
oldinstr newinstr | | | |
| | | +-- pad (4byte alignにするため)
| | |
| | +------ mfence命令のopcodeは 0F AE /6 の3バイト
| |
| +--------- add mem imm8で5バイトlock prefixで+1
|
+ ----------- feature(0x39=57ダミーで入れたよね)


と、なんとなくソレらしい値になっていることが分かる。
特に661bとかのラベル参照がちゃんと、違うアドレスになっていることを確認していただきたい。


つまり、これは

linux/include/asm-i386/system.h の
278 struct alt_instr { 
279 __u8 *instr; /* original instruction */
280 __u8 *replacement;
281 __u8 cpuid; /* cpuid bit set for replacement */
282 __u8 instrlen; /* length of original instruction */
283 __u8 replacementlen; /* length of new instruction, <= instrlen */
284 __u8 pad;
285 };


というデータ構造をメンドクサイ方法で作っているだけだという事。
なんでわざわざ面倒な方法を採用するかというと、C言語で普通に書くと変数には
名前をつけなくてはいけない。
でも、そこらじゅうで使われるマクロだと名前のバッティングを避けるのがえらい面倒なので
アセンブラで無理やり無名データを作っているわけ。


さて、ここらで今までに分かったことを一端まとめると

alternativeマクロは、oldinstr引数だけを実行コードとして生成して、
newinstr引数、feature引数をつかって、.altinstr_replacement と .altinstructions
というなんだかよく分からないデータ構造を作る。

という事が分かった。


エェェ(´д`)ェェエ
newinstr が実行コードに入らないんじゃ意味ないじゃーーん。

と思うかもしれないが、信じて欲しい、最終的にはnewinstrが実行されるように
別の場所で細工しているのだ。

それをこれから解説していく。


まず、 .sectionがマクロ内で使っていた時点で「きっとリンカスクリプト」で何か
細工をしているに違いない。
と、ピンとこなければならない。

だって、他にセクションなんか使う場所ないんだもの。

で、リンカスクリプトを見てみると・・・

linux/arch/i386/kernel/vmlinux.lds.S
86   . = ALIGN(4);
87 __alt_instructions = .;
88 .altinstructions : { *(.altinstructions) }
89 __alt_instructions_end = .;
90 .altinstr_replacement : { *(.altinstr_replacement) }


ありました。
複数のファイルの、色々な場所に散らばっている.altinstructions と.altinstr_replacementを一箇所に集めています。
見方は
出力先のセクション名: { 入力ファイル名(入力ファイル内のセクション)}
で入力ファイルが*(ワイルドカード)だから全てのファイルのセクションを集めるって意味。

そして、.altinstructions セクションの直前と直後に__alt_instructions, __alt_instructions_endという
シンボル(C言語で言うところの変数)をつくり、カレントマーカを代入しています。

これも定石処理(どこの世界の常識だよ!)で、無名のデータを作ったまま何もしないと、
本当に使いようがなくなってしまうので、
リンク時に先頭にシンボルを作って、C言語の別の場所から extern __alt_instructions とかやって
参照できるようにするんですな。

あとは、__alt_instructions を作った以上はどこかでつかっているに違いないと、grepすると

linux/arch/i386/kernel/setup.c
1285 /* Replace instructions with better alternatives for this CPU type.
1286
1287 This runs before SMP is initialized to avoid SMP problems with
1288 self modifying code. This implies that assymetric systems where
1289 APs have less capabilities than the boot processor are not handled.
1290 In this case boot with "noreplacement". */
1291 void apply_alternatives(void *start, void *end)
1292 {
1293 struct alt_instr *a;
1294 int diff, i, k;
1295 unsigned char **noptable = intel_nops;
1296 for (i = 0; noptypes[i].cpuid >= 0; i++) {
1297 if (boot_cpu_has(noptypes[i].cpuid)) {
1298 noptable = noptypes[i].noptable;
1299 break;
1300 }
1301 }
1302 for (a = start; (void *)a < end; a++) {
1303 if (!boot_cpu_has(a->cpuid))
1304 continue;
1305 BUG_ON(a->replacementlen > a->instrlen);
1306 memcpy(a->instr, a->replacement, a->replacementlen);
1307 diff = a->instrlen - a->replacementlen;
1308 /* Pad the rest with nops */
1309 for (i = a->replacementlen; diff > 0; diff -= k, i += k) {
1310 k = diff;
1311 if (k > ASM_NOP_MAX)
1312 k = ASM_NOP_MAX;
1313 memcpy(a->instr + i, noptable[k], k);
1314 }
1315 }
1316 }
1317
1318 static int no_replacement __initdata = 0;
1319
1320 void __init alternative_instructions(void)
1321 {
1322 extern struct alt_instr __alt_instructions[], __alt_instructions_end[];
1323 if (no_replacement)
1324 return;
1325 apply_alternatives(__alt_instructions, __alt_instructions_end);
1326 }
1327
1328 static int __init noreplacement_setup(char *s)
1329 {
1330 no_replacement = 1;
1331 return 0;
1332 }
1333
1334 __setup("noreplacement", noreplacement_setup);


という処理をしているのがわかります。

__initはLinuxカーネル内における __attribute__((constructor)) 指定であり、
カーネル起動時に自動的に呼ばれます。
なんでgcc標準の__attribute__((constructor)) を使わないのかってはなしは面白いので別の機会にでも。

__setup()ってのはカーネル起動時のコマンドライン引数(lilo.confとかgrub.confとかに書くヤツ)
で第一引数の文字列が指定されたら第二引数の関数を呼べというある種のコールバック登録。

話がそれた。


で、見てみると
__alt_instructions をそのまま alt_instr構造体の配列とみなして
(そうできるように、.longやら.byteを駆使してデータ構造を作ったんだよね)

cpuid命令の結果からfeature bitがONになっていれば boot_cpu_has(a->cpuid)
newinstr をoldinstrの位置にmemcpy()して実行コードを直接書き換えてしまう(!)
という荒業を行っています。

これで実行時にif文を使わずにCPUにあわせた最適な処理が実行できるわけ。
alternativeマクロのコメントに記述してあるnewinstr引数はoldinstr引数よりも
生成コードが短くないといけないって制限もこれで納得していただけると思う。

1クロックでも無駄にしないカーネル魂。感じていただけただろうか。

あっと、書き忘れ
memcpy(a->instr + i, noptable[k], k); ってのは残りのバイトをNOPで埋めるんだけども
x86はNOPがいくつか種類があって、たとえば4バイトあまったときに
1バイトのNOP x4 よりも4バイトNOP x1 のほうがCPU にやさしい
(バファリンとカーネルハッカーの半分はやさしさで出来ています)
ので、こういうメンドクさいループを実行している。


どうだろう?
思ったよりも、ややこしかったのではないだろうか?
元を正せばマルチプロセッサ同期命令などという基本的な命令を
P6, Pentium4などという超最近に追加するIntelが悪いのだが、
素直にコンパイルオプションなぞにしてしまったら、ディストリビュータはきっと
Pentium4をOFFにしたGenericカーネルを配布しだして遅くなるし
条件分岐命令なんぞいれた日にゃあ、目も当てられない速度になるのは請け合い。
ってことで、かなり強引な手法がとられている。

普通のLinuxでは実行コードは書き換え不可なので、自己修正コードをつくるのはかなり難儀なのだが、そこはカーネル、なにものにも邪魔されずにハックされてる様は逆にすがすがしくもある
(なにが?)

当然、というか、x86以外ではここまでエエカげんな命令セット拡張はしてないので、
alternativeマクロ自体が存在しない。

どうだまいったか!(だからなにが?)



P.S.
ところで、これを書いている中で些細なバグをまた見つけてしまった。
Intelが発行している
「IA-32 インテル アーキテクチャ・ソフトウェア・デベロッパーズ・マニュアル 下巻: システムプログラミングガイド」の10.6節 自己修正コード の項にはコードを書き換えたらcpuid命令(など)を発行してシリアルか操作を実行してね。
と書いてあるけど、してないよね。
まあ、書き換え直後に実行しない限りprefechは考えなくて良いし、起動時に書き換えてるのでキャッシュにすでに
乗っている可能性は0なので、実害はないんだろうけど、うがが・・


P.S.2
今回は余興もかねて、よく分からないときの調べ方も含めて書こうとしたのだが、幾分中途半端だったかも。
次からは普通に、結論だけ書く記事に戻るかもしれん。
そのほうがこっちもラクだし。


P.S.3
早く発売してくれ



修正してやる
修正してやる! ランキング!
(そして返り討ち)

関連記事


linux | 【2006-04-18(Tue) 20:16:47】 | Trackback:(1) | Comments:(11)
コメント

>元を正せばマルチプロセッサ同期命令などという基本的な命令をを
>P6, Pentium4などという超最近に追加するIntelが悪いのだが、

P5の時代ってあんまり憶えてないんだけど、

・MPカーネルの主流はジャイアントロッキング
・プロセス=1スレッド
・x86命令をデコードせずにそのまま実行
・パイプラインが短い
・FSBとCPUのクロック差が小さい

と思うんだけど、そう考えるとMP間で同期する頻度って低いし、同期のコストも低いのであえて専用の命令を用意する必要はない!という判断もわかる気がするなぁ。
2006-04-18 火 10:11:47 | URL | ひら #G3vcSUbA [ 編集]

それはおっしゃるとおり。P5まではx86って本当におもちゃでIAサーバーなんてバカにされてましたものね。
んでもんでも、今は必要なくても将来必要になりそうなものはあらかじめ入れとくのが命令セット考える人のお仕事だと思うのですよ。
まわりのRISCみたら参考事例はいろいろとあったわけだし・・・

とかとか
2006-04-18 火 10:21:41 | URL | 管理者 #- [ 編集]

http://www.netfort.gr.jp/~dancer/diary/daily/2006-Apr-25.html.ja

によると、powerpc版も似たような事をしているらしいです。
こちらこそppc kernelは全然エンがないので勉強になります m(_ _)m
2006-04-25 火 21:46:24 | URL | 革命の日々 #- [ 編集]

このエントリ、めちゃくちゃ参考になりました。ありがとうございます
2007-08-09 木 04:39:26 | URL | bigt #- [ 編集]

bigtさんお役に立てて何よりです(^^)
でも、こんなマイナーなネタが参考になるって、どんなん調べてはったんですか??
2007-08-09 木 06:52:20 | URL | kosaki #- [ 編集]

kosakiさん

えーと、schedule()中のprefetch()を追っかけてたんですよね。alternative_input()を
理解したかったのですが、アセンブラは結構さっぱりなもので・・・(^^;)

>調べ方も含めて
自分のような新参には調べ方もあると大助かりです。おんぶにだっこですね(すんません)
2007-08-10 金 03:14:17 | URL | bigt #- [ 編集]

おおお、スケジューラ屋さんか。すばらしい。
最近は、CFSとかも出てきて、スケジューラ熱いっすね。
2007-08-11 土 01:08:20 | URL | kosaki #- [ 編集]
このコメントは管理人のみ閲覧できます
2007-10-07 日 14:31:08 | | # [ 編集]
このコメントは管理人のみ閲覧できます
2007-11-21 水 17:33:43 | | # [ 編集]
このコメントは管理人のみ閲覧できます
2007-11-27 火 23:46:52 | | # [ 編集]
このコメントは管理人のみ閲覧できます
2007-12-20 木 16:45:01 | | # [ 編集]
カーネル読書会デビューすることにしました。6/9 あたりにaltanativeマクロの話をする予定#うちのIMEは毎回、「カー寝る」と変換する。なぜ??
【2006-06-10 Sat 01:30:44】 | 革命の日々!
  1. 無料アクセス解析
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。