読者です 読者をやめる 読者になる 読者になる

【お知らせ】プログラミング記事の投稿はQiitaに移行しました。

Brainf*ckトランスレータ (5) 位置独立コード

前回に引き続きBrainf*ckのトランスレータを見ていきます。

Mac OS Xではデフォルトで位置独立コード(PIC)が要求されます。プログラムがどのアドレスにロードされるか決められないため、グローバル変数のアドレスを即値ではなく、プログラムカウンタからの相対で得たテーブルからポインタを取り出す必要があります。

非PICとPICを比較するため、まずはELFを見てみます。

i386(ELF) 非PIC

PICではないコードでは、オブジェクトコードの段階ではゼロが埋め込まれて、リンク時にアドレスが埋め込まれます。

例としてC言語コードのコンパイルとリンクを追ってみます。テスト環境はNetBSD/amd64で、gcc -m32を指定して32bitのコードを生成しています。

test.c
int mem[1];

int main(void) {
    mem[0] = 1;
    return 0;
}

C言語と対比するため-gオプションでデバッグ情報を埋め込みます。オブジェクトコードを生成して逆アセンブルします。

$ gcc -m32 -g -c test.c
$ objdump -S test.o

main()でグローバル変数が関係するのは以下の部分です。memのアドレスが0になっているのが分かります。

        mem[0] = 1;
   e:   c7 05 00 00 00 00 01    movl   $0x1,0x0
  15:   00 00 00 

リンクして逆アセンブルします。

$ gcc -m32 -o test test.o
$ objdump -S test

先ほどの部分にmemのアドレスが埋め込まれているのが分かります。

        mem[0] = 1;
 80486ea:       c7 05 d0 98 04 08 01    movl   $0x1,0x80498d0
 80486f1:       00 00 00 

オブジェクトファイルにはリンク時にアドレスを埋め込む場所が記録されています。リンカがこれを見てアドレスを埋め込みます。

$ objdump -x test.o
(中略)
RELOCATION RECORDS FOR [.text]:
OFFSET   TYPE              VALUE 
00000010 R_386_32          mem
(後略)

i386(ELF) PIC

PICではコードがどのように変化するか見てみます。リンカによって埋め込まれる値があまりにも多いため、逆アセンブルではなくコンパイラのアセンブリ出力を見ます。

$ gcc -m32 -fPIC -S test.c

memにアクセスしている部分と、関係する部分を抜粋します。

        call    __i686.get_pc_thunk.cx
        addl    $_GLOBAL_OFFSET_TABLE_, %ecx
        movl    mem@GOT(%ecx), %eax
        movl    $1, (%eax)
__i686.get_pc_thunk.cx:
        movl    (%esp), %ecx
        ret

i386ではプログラムカウンタ(eip)を直接取得することができないため、__i686.get_pc_thunk.cxでcall命令によってスタックに積まれた戻り先アドレスをecxに入れることで、間接的にeipを取得しています。具体的には次のようなことがやりたかったのだと思われます。

        movl    %eip, %ecx
        addl    $_GLOBAL_OFFSET_TABLE_, %ecx
        movl    mem@GOT(%ecx), %eax
        movl    $1, (%eax)
GOT

ecxに足されている$_GLOBAL_OFFSET_TABLE_は定数ではなく、リンカがプログラムカウンタを考慮して値を埋め込みます。次の例を見ると理解しやすいかもしれません。

got.s
addl $_GLOBAL_OFFSET_TABLE_, %ecx
addl $_GLOBAL_OFFSET_TABLE_, %ecx
$ gcc -m32 -nostdlib got.s
$ objdump -d a.out
(中略)
 8048074:       81 c1 0c 10 00 00       add    $0x100c,%ecx
 804807a:       81 c1 06 10 00 00       add    $0x1006,%ecx

ecxに命令のアドレスが入っていれば、計算結果は常に同じアドレスになります。

  • 0x8048074 + 0x100c = 0x8049080
  • 0x8049080 + 0x1006 = 0x8049080

Global Offset Table(GOT)とは、簡単に言えばグローバル変数や即値のポインタが入っているテーブルです。値そのものではなく、ポインタが入っています。更に間接参照してようやく値に到達できます。

  • eip → GOT → ポインタ → 目的の値

GOTに値を入れれば間接参照が1段階減りますが、巨大な配列を定義すればすぐにGOTが埋まってしまうため、それを避けるためにこのような仕様になっていると思われます。プログラムカウンタに$_GLOBAL_OFFSET_TABLE_を足して得られるアドレスは、GOTの先頭ではなく中央です。相対アドレッシングは符号付きで表現されるため、負の値も活用するための仕様です。

ちなみにMIPSやAlphaでは、GOTの中央を指す専用のレジスタ(GP)が存在します。それらのCPUではレジスタが32個と多いため、1つくらいレジスタを割り当ててもほとんど問題にはなりません。

まとめ

まとめると、プログラムカウンタ相対でGOT(ポインタが集まっているテーブル)のアドレスを求めて、そこからポインタを取り出して目的のアドレスにアクセスするわけです。

x86_64(ELF) 非PIC

64bitではプログラムカウンタ(rip)が直接取得できるようになったため、即値は埋め込まずにプログラムカウンタ相対でアドレスを取得します。

$ gcc -S test.c

該当部分を抜粋します。

        movl    $1, mem(%rip)

逆アセンブルすると以下の通りです。

$ gcc -g test.c
$ objdump -S a.out
(中略)
      mem[0] = 1;
400894: c7 05 5a 04 10 00 01  movl $0x1,1049690(%rip) # 500cf8<mem>
40089b: 00 00 00 
(後略)

プログラムカウンタは次の命令を指しているため、相対アドレスを計算すると以下の通りとなります。これがコメントの意味です。

  • 0x40089e + 1049690 = 0x500cf8

x86_64(ELF) PIC

PICでは32bitと同じようにGOT経由でアクセスします。

$ gcc -fPIC -S test.c

該当部分を抜粋します。

        movq    mem@GOTPCREL(%rip), %rax
        movl    $1, (%rax)

たった1命令でGOTからポインタを取得しています。GOTの中心から相対計算せずにいきなり算出しています。32bitと比べて非常に単純になっています。

i386(Mac)

さて、いよいよMac OS Xです。デフォルトでPICとなります。

$ gcc -m32 -S test.c

該当部分を抜粋します。

        .comm   _mem,4
(中略)
        call    ___i686.get_pc_thunk.cx
L00000000001$pb:
        leal    L_mem$non_lazy_ptr-L00000000001$pb(%ecx), %eax
        movl    (%eax), %eax
        movl    $1, (%eax)
(中略)
        .section __TEXT,__textcoal_nt,coalesced,pure_instructions
        .weak_definition        ___i686.get_pc_thunk.cx
        .private_extern ___i686.get_pc_thunk.cx
___i686.get_pc_thunk.cx:
        movl    (%esp), %ecx
        ret
        .section __IMPORT,__pointers,non_lazy_symbol_pointers
L_mem$non_lazy_ptr:
        .indirect_symbol _mem
        .long   0
        .subsections_via_symbols

ELFでの$_GLOBAL_OFFSET_TABLE_に相当する部分が自動ではなく泥臭い表現になっていますが、やっていることはほぼ同じです。

x86_64(Mac)

シンボルにプレフィックスが付いている以外はELFのPICと同じです。

$ gcc -S test.c

該当部分を抜粋します。

        movq    _mem@GOTPCREL(%rip), %rax
        movl    $1, (%rax)

おわりに

以上でMac/Win/ELFでBrainf*ckのアセンブリ言語トランスレータの実装に必要な知識の説明は終了です。複数のアーキテクチャを比較したため複雑になりました。しかし自分の使っているアーキテクチャで実装したいというのが人情ですから、ある程度は網羅的な説明になるのは避けられません。

※こうなると収集が付かなくなる恐れがあるので、入り口としてi386-peに的を絞ったのがPE勉強会だったというわけです。