/ «2007-04-02 (Mon) ^ 2007-05-01 (Tue)» ?
   西田 亙の本:GNU 開発ツール -- hello.c から a.out が誕生するまで --

Categories Books | Hard | Hardware | Linux | MCU | Misc | Publish | Radio | Repository | Thoughts | Time | UNIX | Writing | プロフィール


2007-04-11 (Wed)

[Linux][Writing] 世界一単純な実行ファイルフォーマット binfmt_flat

Computer Architecture Series 第二作のために、日々素材作りを進めているのですが、この作業の間に "binfmt_flat" というオタッキーなモジュールが誕生しました。今日は、このモジュールを使った "Hello golf" をご紹介しましょう(注: 昨年一世を風靡した ELF golf ではありませんので、あしからず)。

初学者の理解を阻む複雑な ELF

皆さんご存じの通り、PC-UNIX 上における標準のオブジェクトファイルフォーマットは ELF (Executable and Linking Format) ですが、このフォーマットは高機能を追求しているため、内部はかなり複雑な作りになっています。

実は、当初 Computer Architecture Series 第二作のテーマは、この ELF を予定していました。私にしては珍しく、前もって原稿も書き貯めていたのですが、考えた挙げ句に途中でお蔵入りとなってしまった次第、トホホ・・。

ELF の内部構造を理解するためには、アセンブリ言語はもとより、さらに深い機械語レベルの知識が必須となります。具体的には「オペコードマップを元に、アセンブラーとリンカーを自作できる位の腕力」が望ましいのですが、スクリプト言語全盛の時代に、このような時代錯誤の前提を置くわけにはいきません。

そこで、思い切って ELF のテーマは繰り越すこととし(Micro Controller Unit の解説以降を予定)、第二作では基本的な UNIX 環境に関する解説を行うこととしました。基本的かつ重要ではあるけれど、これまで語られることのなかったテーマの数々が登場します。

プログラムからプロセスへ

さて、ファイルイメージとして焼き付けられたプログラムファイルは、execve システムコールにより、メモリー上のプロセスへと生まれ変わります。

サナギから蝶への完全変体のように、プログラムファイルを鋳型にしたプロセスの生成は、大変興味深く、また好奇心を刺激される現象です。一体どのような仕組みでプロセスは誕生するのでしょうか?

binfmt モジュール

Linux カーネルにおいて、プログラムファイルからプロセスを起動する主要処理は、binfmt (BINary ForMaT) モジュールが担当しています。ELF フォーマットであれば binfmt_elf、旧来の a.out フォーマットであれば binfmt_aout がその処理を担当します。

しかしながら、binfmt モジュールに関する資料は、皆無に近い状況(Linux では毎度のことですが)。linux/Documentation ディレクトリ中に用意されている古い資料は binfmt_misc のみに関するものですし、ネット上の資料も Playing with binary formats のように、拡張子に基づいたファイルビューアーの自動起動方法を述べるだけで、肝心の binfmt コア部分に関するものはありません。

頼りの "Understanding the LINUX KERNEL 3rd Ed." も、binfmt については軽く言及しているだけで、重要なところがあちこち抜け落ちています。ウッキ〜〜!!

ということで、結局ソースにあたるしかないのですね。幸いなことに、プログラムファイルからプロセス生成に関わるコードは、多くはありません。fs/exec.c, fs/binfmt_*.c および関連するヘッダーファイル群を読み込んでいけば、意外なほど単純な仕組みが明らかになります。

世界最小の実行フォーマット binfmt_flat

で、この解析結果を元に、世界一シンプルな実行可能ファイルフォーマット binfmt_flat のモジュールを作ってみました。

フォーマットの仕様ですが、.rodata セクションは必要ないので削除。.bss セクション、そんな高級なもの必要ないので却下。ついでに .data セクションもありません。開始アドレスもゼロ番地固定。実は、.text セクションも・・ないんです。

「なんじゃそりゃ?!」と言われそうですが、昔はセクションなんて気の利いた代物はなかったのであります。CPU の前には、コードもデータも全て平等。だから、"flat"。

binfmt_flat フォーマットに要求される唯一の約束事は、先頭2バイトに "EB 00" が位置すること。これは、OMAGIC における "0407" をもじった、x86 版の "jmp short" 命令コードです。つまり、binfmt_flat フォーマットの「ヘッダーデータはわずか2バイト」ということになります。

さらば、ELF!

何もしないプログラム exit

手始めに、最も簡単なプログラムファイル exit.asm を用意します。crt ファイルとリンカースクリプトを用意すれば GNU C コンパイラも使えるのですが、今日は見通しの良い Netwide assembler でコンパクトに片付けてしまいましょう。なお、AT&T syntax の gas は、コードが美しくないので却下。

       bits 32                 ; operand/address size is 32 bits

       jmp     short _start    ; file signature (EB 00)
_start:
       mov     eax, 1          ; one means "_exit" system call
       mov     ebx, 123        ; exit status is 123
       int     0x80

先頭の "jmp short _start" 命令は、file signature (EB 00 に展開される) を兼ねています。残りは、教科書的な内容ですね。レジスタ指定を介して、Linux の _exit システムコールを直接呼び出しています。EBX レジスタに 123 を指定しているので、親プロセスであるシェルには終了ステータスコードとして 123 が返されます。

それでは、アセンブリソースファイルから binfmt_flat 実行可能ファイルを生成します。

$ nasm exit.asm 
$ ls -l exit
-rw-r--r--  1 wataru wataru 14 2007-04-12 01:51 exit
$ hexdump -C exit
00000000  eb 00 b8 01 00 00 00 bb  7b 00 00 00 cd 80        |?.?....?{...?.|
0000000e

実は、NASM には binfmt_flat フォーマットの出力オプションなどありません。NASM はデフォルトでバイナリーフォーマットで出力しますから、これでOKなのです。

ファイルサイズは驚きの14バイト。exit ファイルの内容を見ると、確かに先頭に EB 00 が位置しています。全体を逆アセンブルしてみましょう。

$ objdump -b binary -m i386 -D exit  

exit:     file format binary

Disassembly of section .data:

0000000000000000 <.data>:
  0:   eb 00                   jmp    0x2
  2:   b8 01 00 00 00          mov    $0x1,%eax
  7:   bb 7b 00 00 00          mov    $0x7b,%ebx
  c:   cd 80                   int    $0x80

このような時は、objdump の -D オプションを使います(-b, -m オプションも定石ですので、覚えておきましょう)。逆アセンブルリストが、みっともない AT&T syntax に置き換わっていますが、意図通りのコードが生成されています。高級言語やスクリプト言語にはない、この「一対一」の感覚は、アセンブリ言語ならではですね。

exit の実行前に、binfmt_falt モジュールをコンパイルし、カーネルにモジュールとして組み込みます。Linux カーネル 2.6 環境は複雑で初学者には向いていないため、書籍の作業環境には敢えて Debian sarge を採用しています。

$ gcc-2.95 -c -Wall -DMODULE -D__KERNEL__ -O binfmt_flat.c
$ sudo insmod binfmt_flat.o

最後に、exit ファイルに実行可能属性を付与して、シェルから呼び出します。

$ chmod +x exit
$ ./exit ; echo $?
123
$

わずか、14バイトのプログラムファイルがプロセスの命を与えられ、立派に動いています。これぞ、モジュールプログラミングの醍醐味と言えるでしょう。

Hello golf のはじまり、はじまり・・

それでは、お題目の Hello golf を始めましょう。NASM 版 Hello, world! プログラム hello.asm は次のようになります。

       bits 32                 ; operand/address size is 32 bits

       jmp     short _start    ; file signature (EB 00)
_start:
       mov     eax, 4          ; EAX = "write" system call
       mov     ebx, 1          ; EBX = STDOUT decsriptor
       mov     ecx, msg        ; ECX = message address
       mov     edx, mend - msg ; EDX = message length
       int     0x80

       mov     eax, 1          ; EAX = "_exit" system call
       mov     ebx, 123        ; EBX = exit status (123)
       int     0x80
msg:
       db      'Hello, world!'
       db      10
mend:

こちらも、教科書的な内容です。先ほどの exit.asm に、標準出力への write システムコールを付加しただけですね。アセンブルしてみましょう。

$ nasm hello.asm
$ chmod +x hello
$ wc -c hello
50 hello

来ました来ました、「ヘッダー2バイトの威力」により、最初から難なく50バイトを叩き出しています。ホンマに動くの?

$ ./hello ; echo $?
Hello, world!
123

ちゃんと動きましたが、まだまだ油断はできません。菊やんの雑記帳では、ELF でありながら58という恐るべきスコアを叩きだしています。

もう少し、刻んでみましょう。

レジスタ即値転送命令の無駄

hello の逆アセンブルリストを見直し、コードのどこに無駄が隠されているかチェックします。

 $ objdump -b binary -m i386 -D hello
 
 hello:     file format binary
 
 Disassembly of section .data:
 
 0000000000000000 <.data>:
    0:   eb 00                   jmp    0x2
    2:   b8 04 00 00 00          mov    $0x4,%eax
    7:   bb 01 00 00 00          mov    $0x1,%ebx
    c:   b9 24 00 00 00          mov    $0x24,%ecx
   11:   ba 0e 00 00 00          mov    $0xe,%edx
   16:   cd 80                   int    $0x80
   18:   b8 01 00 00 00          mov    $0x1,%eax
   1d:   bb 7b 00 00 00          mov    $0x7b,%ebx
   22:   cd 80                   int    $0x80
   24:   48                      dec    %eax
   25:   65                      gs
   26:   6c                      insb   (%dx),%es:(%edi)
   27:   6c                      insb   (%dx),%es:(%edi)
   28:   6f                      outsl  %ds:(%esi),(%dx)
   29:   2c 20                   sub    $0x20,%al
   2b:   77 6f                   ja     0x9c
   2d:   72 6c                   jb     0x9b
   2f:   64 21 0a                and    %ecx,%fs:(%edx)

このリスト中で目立つのは、1や4などの定数をレジスターに格納する際(レジスタへの即値転送命令)に、5バイトも消費している点です。ここを工夫してみましょう。

xor 命令とバイト転送命令の活用

       bits 32                 ; operand/address size is 32 bits
 
       global _start           ; intended for ELF version
         jmp     short _start    ; file signature (EB 00)
 _start:
       xor     eax, eax
       xor     ebx, ebx
       xor     ecx, ecx
       xor     edx, edx
 
       mov     al, 4           ; EAX = "write" system call
       mov     bl, 1           ; EBX = STDOUT decsriptor
       mov     cl, msg         ; ECX = message address
       mov     dl, mend - msg  ; EDX = message length
       int     0x80
 
       xor     eax, eax
       xor     ebx, ebx
 
       mov     al, 1           ; EAX = "_exit" system call
       mov     bl, 123         ; EBX = exit status (123)
       int     0x80
 msg:
       db      'Hello, world!'
       db      10
 mend:

hello2.asm では、アセンブリ野郎にはおなじみの xor 命令によるゼロクリアを使っています。続く、バイト転送命令も8086野郎には常識の手段。x86 は 64 ビットへ進化を遂げようとも、内部では未だに基本論理命令やバイト転送命令が最短コードなのです。

 $ nasm hello2.asm
 $ wc -c hello2   
 44 hello2
 $ objdump -b binary -m i386 -D hello2
 
 hello2:     file format binary
 
 Disassembly of section .data:
 
 0000000000000000 <.data>:
    0: eb 00                   jmp    0x2
    2: 31 c0                   xor    %eax,%eax
    4: 31 db                   xor    %ebx,%ebx
    6: 31 c9                   xor    %ecx,%ecx
    8: 31 d2                   xor    %edx,%edx
    a: b0 04                   mov    $0x4,%al
    c: b3 01                   mov    $0x1,%bl
    e: b1 1e                   mov    $0x1e,%cl
   10: b2 0e                   mov    $0xe,%dl
   12: cd 80                   int    $0x80
   14: 31 c0                   xor    %eax,%eax
   16: 31 db                   xor    %ebx,%ebx
   18: b0 01                   mov    $0x1,%al
   1a: b3 7b                   mov    $0x7b,%bl
   1c: cd 80                   int    $0x80
   1e: 48                      dec    %eax
   1f: 65                      gs
   20: 6c                      insb   (%dx),%es:(%edi)
   21: 6c                      insb   (%dx),%es:(%edi)
   22: 6f                      outsl  %ds:(%esi),(%dx)
   23: 2c 20                   sub    $0x20,%al
   25: 77 6f                   ja     0x96
   27: 72 6c                   jb     0x95
   29: 64 21 0a                and    %ecx,%fs:(%edx)

xor 命令とバイト転送命令はそれぞれ2バイトとなり、hello2 のサイズは44バイトとなりました。こうなったら、意地でも40バイトを切りたいところ。

hello3.asm

もしも、プロセス起動時に EAX, EBX, ECX, EDX がゼロクリアされていることが保証されていれば、xor 命令が不要になりますので、かなりコードを節約できます。少しズルイ気もしますが、binfmt_flat モジュールに手を加え、プロセス開始時 EAX = EBX = ECX = EDX = 0 となるようにしてみました。

"神様" には、こういう事も許されるのであります。

       bits 32                 ; operand/address size is 32 bits
 
 ; binfmt_flat guarantess that "EAX = EBX = ECX = EDX = 0"
 
       jmp     short _start    ; file signature (EB 00)
 _start:
       push    eax
       push    ebx
 
       mov     al, 4           ; EAX = "write" system call
       mov     bl, 1           ; EBX = STDOUT decsriptor
       mov     cl, msg         ; ECX = message address
       mov     dl, mend - msg  ; EDX = message length
       int     0x80
 
       pop     ebx
       pop     eax
 
       mov     al, 1           ; EAX = "_exit" system call
       mov     bl, 123         ; EBX = exit status (123)
       int     0x80
 msg:
       db      'Hello, world!'
       db      10
 mend:

xor 命令がなくなると、随分スッキリしましたね。write システムコール実行中に EAX, EBX レジスタの内容が変化すると困るので、コードサイズの小さい PUSH/POP 命令で保存/復活させています。

さて、そのサイズはいかに?

$ nasm hello3.asm
$ wc -c hello3
36 hello3
$ chmod +x hello3
$ ./hello3 ; echo $?
Hello, world!
123

遂に、スコア36の Hello, world! が誕生しました。

閑話休題

思わず脱線してしまいましたが、binfmt_flat モジュールは Golf をやるために作成したのではありません(意識はしましたが)。最も単純なフラットファイルフォーマットまで遡り、これを発展させていく過程を通じて、なぜセクション構造が必要になったのか、その意味を読者の方々に実体験して頂くことが目的です。

GNU 開発ツールは強力なセクションコントロール能力を持っていますが、その力を最大限に発揮させるためには、基本の理解が不可欠だと私は考えています。