Hello World くらいしかできない言語のアセンブラをつくる

これは 言語実装Advent Calender 14日目 の記事です。

ざっくりと趣旨

アセンブラ（アセンブリ言語をオブジェクトファイルに変換するやつ）って具体的にどういうものなのか知りたいなと思ったので、むちゃくちゃ小さいアセンブラ作りに挑戦してみました。

※アセンブリ言語の書き方ではなく、アセンブラを自作することについての記事です

自己紹介

三土たつおといいます。プログラマーであり、ライターです。

プログラマーとしては、言語を自作するのが趣味です。Mud という、以下のような見た目の関数型言語を Haskell で作っています。

# 1 * 2 * .. * n を計算する関数
fun factorial : Int -> Int = {
    1 -> 1
    n -> n * factorial (n-1)
}
factorial 5   #=> 120

ライターとしては 「渋谷川が天井から飛び出す広場ができた：デイリーポータルZ」とか「街角図鑑」とかを書いています。

本題

高級言語で書かれたプログラムを実行ファイルに変換するには、およそ次のような道を通ると思います。

高級言語のプログラム
　　↓　コンパイラが変換
アセンブリ
　　↓　アセンブラが変換
オブジェクトファイル
　　↓　リンカが変換
実行ファイル

このうちコンパイラについては Qiita でも多くの記事がありますが、アセンブラ（アセンブリではなく）とリンカについては相対的に少ないように思います。また、自分としてもよく知りません。なので、具体的にごく小さいアセンブラを作ってみようと思いました。

方針としては、まず「Hello World」の出力くらいしかできないようなごく小さい言語を定義します。そしてそれをアセンブリにするごく小さいコンパイラを作り、最後にそれをオブジェクトファイルにするごく小さいアセンブラを作ろうと思います。

環境

対象のアーキテクチャは x86_64 で、作業環境は手元の mac の docker に用意した ubuntu:18.04 です。

言語を定義する

出発点となる言語はこんなものとします。

example.nano

puts "Hello World!"

puts 文は文字列を改行つきで出力するもので、この言語ではそれを1個だけ書けます。本当に Hello, World くらいしかできません。とはいえ名前をつけてあげるとモチベーションがあがるので、この言語を Nano とします。

これをオブジェクトファイルまで持っていくというのが今回のゴールです。

コンパイラをつくる

まずはコンパイラを作ります。コンパイラとは、ここでは高級言語（Nano）をアセンブリ言語に変換するプログラムのことです。

今回はコンパイラについては本題ではないので、さっくりと進めます。元となる Nano プログラム、

hello.nano

puts "hello, world"

に対応するアセンブリは結論から言うとこんなふうになります。

hello.s

	.intel_syntax noprefix
.LC0:
	.string	"hello, world"
	.globl	main
main:               
	push	rbp
	mov	rbp, rsp
	lea	rdi, .LC0[rip]
	call	puts@PLT
	mov	eax, 0
	pop	rbp
	ret

このアセンブリはどこから出てきたの？　という点については以下に畳んでおきます。

アセンブリの導き方 （クリックで開きます）

手でアセンブリを書くような能力などないので、gcc に聞きます。Nano の puts "hello, world" と等価なCのプログラムは例えばこんなふうになるはずです。

hello.c

#include <stdio.h>

int main() {
   puts("hello, world");
}

これを gccにアセンブリ言語に直してもらいます。gcc -S オプションを使います。

% gcc -S -masm=intel hello.c

hello.s

	.file	"hello.c"
	.intel_syntax noprefix
	.text
	.section	.rodata
.LC0:
	.string	"hello, world"
	.text
	.globl	main
	.type	main, @function
main:
.LFB0:
	.cfi_startproc
	push	rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	mov	rbp, rsp
	.cfi_def_cfa_register 6
	lea	rdi, .LC0[rip]
	call	puts@PLT
	mov	eax, 0
	pop	rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0"
	.section	.note.GNU-stack,"",@progbits

これの意味を調べて、不要な箇所を削るとさきほどのアセンブリになります（「アセンブリの導き方」ここまで）。

今回の言語(Nano)では、 上のアセンブリのうち "hello, world" の部分が変化するだけですから、Nanoプログラムを読み取ってそこだけを変えたアセンブリを出力できれば、それで Nano コンパイラのできあがりです。

で、そのようにしてコンパイラを作り、名前を nanoc（Nano Compiler）としました。

nanoc
https://github.com/mitsuchi/nano-lang/blob/master/nanoc.c

nanoc は、プログラムを標準入力から受け取り、アセンブリを標準出力に出力します。実際に使ってみましょう。プログラムは puts "hello, world" とします。

% echo 'puts "hello, world"' | ./nanoc > hello.s
% cat hello.s
    .intel_syntax noprefix
.LC0:
    .string "hello, world"
(以下略)

アセンブリ（hello.s）ができたので、 gcc の力を借りて実行ファイルにしてみます。

% gcc hello.s -o hello
% ./hello
hello, world

実行できました！　これでコンパイラはOKです。

アセンブラをつくる

つづいて本題のアセンブラを作ります。

アセンブラとは、ここではアセンブリ言語で書かれたプログラム（hello.s）を、機械語を含むオブジェクトファイル（hello.o）に変換するものです。でも、オブジェクトファイルとは具体的にどんな構造をしてるんでしょうか。

さきほどの節で gcc hello.s としたとき、gcc は実際には内部でアセンブラを呼び出していました。そこで gcc -v オプションを使い、gcc がどうやってアセンブラを呼び出しているかを調べます。

% gcc -v hello.s
(中略)
as -v --64 -o /tmp/ccrmtkwe.o hello.s

どうやら as というプログラムを呼び出しているようです。そこで as によるアセンブルの結果を hello.as.o として保存します。

% as --64 -o hello.as.o hello.s

中身をみてみます。

% cat hello.as.o
ELF>?@hello, worldUH??H?=??????]?
mainputs_GLOBAL_OFFSET_TABLE_????????.symtab.strtab.shstrtab.rela.text.data.bss @$&ddh? !P1

微妙に読める部分もありますが、バイナリなのでよく分かりません。

そこで xxd というツールを使い、バイナリの中身を16進数とASCIIで表示させてみます。

% xxd hello.as.o
00000000: 7f45 4c46 0201 0100 0000 0000 0000 0000  .ELF............
00000010: 0100 3e00 0100 0000 0000 0000 0000 0000  ..>.............
00000020: 0000 0000 0000 0000 8801 0000 0000 0000  ................
00000030: 0000 0000 4000 0000 0000 4000 0800 0700  ....@.....@.....
00000040: 6865 6c6c 6f2c 2077 6f72 6c64 0055 4889  hello, world.UH.
00000050: e548 8d3d e8ff ffff e800 0000 00b8 0000  .H.=............
00000060: 0000 5dc3 0000 0000 0000 0000 0000 0000  ..].............
00000070: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000080: 0000 0000 0300 0100 0000 0000 0000 0000  ................
00000090: 0000 0000 0000 0000 0000 0000 0300 0300  ................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000000b0: 0000 0000 0300 0400 0000 0000 0000 0000  ................
000000c0: 0000 0000 0000 0000 0100 0000 1000 0100  ................
000000d0: 0d00 0000 0000 0000 0000 0000 0000 0000  ................
000000e0: 0600 0000 1000 0000 0000 0000 0000 0000  ................
000000f0: 0000 0000 0000 0000 0b00 0000 1000 0000  ................
00000100: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000110: 006d 6169 6e00 7075 7473 005f 474c 4f42  .main.puts._GLOB
00000120: 414c 5f4f 4646 5345 545f 5441 424c 455f  AL_OFFSET_TABLE_
00000130: 0000 0000 0000 0000 1900 0000 0000 0000  ................
00000140: 0400 0000 0500 0000 fcff ffff ffff ffff  ................
00000150: 002e 7379 6d74 6162 002e 7374 7274 6162  ..symtab..strtab
00000160: 002e 7368 7374 7274 6162 002e 7265 6c61  ..shstrtab..rela
00000170: 2e74 6578 7400 2e64 6174 6100 2e62 7373  .text..data..bss
00000180: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000190: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000001a0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000001b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000001c0: 0000 0000 0000 0000 2000 0000 0100 0000  ........ .......
000001d0: 0600 0000 0000 0000 0000 0000 0000 0000  ................
000001e0: 4000 0000 0000 0000 2400 0000 0000 0000  @.......$.......
000001f0: 0000 0000 0000 0000 0100 0000 0000 0000  ................
00000200: 0000 0000 0000 0000 1b00 0000 0400 0000  ................
00000210: 4000 0000 0000 0000 0000 0000 0000 0000  @...............
00000220: 3801 0000 0000 0000 1800 0000 0000 0000  8...............
00000230: 0500 0000 0100 0000 0800 0000 0000 0000  ................
00000240: 1800 0000 0000 0000 2600 0000 0100 0000  ........&.......
00000250: 0300 0000 0000 0000 0000 0000 0000 0000  ................
00000260: 6400 0000 0000 0000 0000 0000 0000 0000  d...............
00000270: 0000 0000 0000 0000 0100 0000 0000 0000  ................
00000280: 0000 0000 0000 0000 2c00 0000 0800 0000  ........,.......
00000290: 0300 0000 0000 0000 0000 0000 0000 0000  ................
000002a0: 6400 0000 0000 0000 0000 0000 0000 0000  d...............
000002b0: 0000 0000 0000 0000 0100 0000 0000 0000  ................
000002c0: 0000 0000 0000 0000 0100 0000 0200 0000  ................
000002d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
000002e0: 6800 0000 0000 0000 a800 0000 0000 0000  h...............
000002f0: 0600 0000 0400 0000 0800 0000 0000 0000  ................
00000300: 1800 0000 0000 0000 0900 0000 0300 0000  ................
00000310: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000320: 1001 0000 0000 0000 2100 0000 0000 0000  ........!.......
00000330: 0000 0000 0000 0000 0100 0000 0000 0000  ................
00000340: 0000 0000 0000 0000 1100 0000 0300 0000  ................
00000350: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000360: 5001 0000 0000 0000 3100 0000 0000 0000  P.......1.......
00000370: 0000 0000 0000 0000 0100 0000 0000 0000  ................
00000380: 0000 0000 0000 0000                      ........

一番左側の列はアドレス、真ん中は16進数での中身、右はASCIIとして解釈した場合の中身です。

hello.s に比べてずいぶん長く、わけが分からなくなりました。しかしこの意味を1バイトずつ全部理解できれば、アセンブラが作れるはずです。というわけで、これらの意味を調べてみます。

（調べ中…。資料を探してきて読むなどの長い時間が流れています…。具体的には Executable and Linkable Format (ELF) と elf.h の2つが特に参考になりました。前者は概要をつかむために、後者は具体的な値の意味を参照するのに重宝しました。）

さて、なんとか調べました。その結果を先ほどのバイナリの図の上に載せてみます。

上の図で「s .text」とある部分は「.textという名前のセクション（後述）」を表します。「sh .data」であれば「.dataという名前のセクションヘッダ（後述）」です。

この中で hello, world という文字列を格納しているのは .text というセクションです。

右側のASCIIの欄を見ると hello, worldとなっているのが分かります。なので、バイナリのこの部分だけを任意の文字列に書き換えてやるプログラムをつくれば、とりあえずはアセンブラへの第一歩になりそうです。

とはいえもちろんそれだけでは足りません。他の部分も理解する必要があります。以下に整理してみます。

ELF

このオブジェクトファイル（hello.as.o）は ELF (Executable and Linkable Format) というフォーマットに従ったバイナリです。Linux x86_64 では、オブジェクトファイルや実行ファイルはこのフォーマットに従う約束になっています。

hello.as.o では、その中身は

• 1つのELFヘッダ
• 複数のセクションと、それに対応するヘッダ

からなっています。セクションとは、リンカにとって必要な情報を意味ごとにまとめたものです。セクションヘッダには、セクションの開始位置やサイズなどの情報が書かれます。

ELF ヘッダ

冒頭はELF自身のヘッダです。ヘッダの中には複数の異なる意味のデータがつまっています。それぞれを青い線で区切りました。データの意味は順に次のとおりです。

7f45 4c46
マジックナンバー（EI_MAG0-3）。後ろ3バイトはASCIIで "ELF" と読めるようになっています。

02
クラス（EI_CLASS）。"02"はアーキテクチャが 64bitであることを表します。

01
データの形式（EI_DATA）。2の補数かつリトルエンディアンであることを表します。

01
バージョン（EI_VERSION）。1で固定。

00
OSとABI（EI_OSABI）。UNIX - System V。

00
ABIのバージョン（EI_ABIVERSION）。0。

00 0000 0000 0000
パディング（EI_PAD）。0で埋めます。

0100
ファイルタイプ（e_type）。再配置可能ファイルを表します。EI_DATA にあるようにリトルエンディアンなので 0x0100 ではなく 0x0001 を意味します。以下同様です。

3e00
アーキテクチャー（e_machine）。x86-64 を表します。

0100 0000
バージョン（e_version）。1で固定。

0000 0000 0000 0000
プログラムの開始位置（e_entry）。0は特別な指定がないことを表します。

0000 0000 0000 0000
プログラムヘッダの開始位置（e_phoff）。プログラムヘッダはプログラムを実行するのに必要で、実行ファイルには必ず含まれますが、今回のオブジェクトファイルには含まれません。

8801 0000 0000 0000
セクションヘッダの開始位置（e_shoff）。0x0188番地です。確かに最初のセクションヘッダ（上の図の「sh 0」）があります。今回のアセンブラを作るにあたっては、 "hello, world" にあたる文字列の長さによって適切に変える必要があります。

0000 0000
プロセッサ固有の各種フラグ（e_flags）。いまのところ未定義です。

4000
このELFヘッダ自身のサイズ（e_ehsize）。たしかに 0x40 バイトです。

0000
プログラムヘッダの1つのサイズ（e_phentsize）。プログラムヘッダは含まれないので0です。

0000
プログラムヘッダの数（e_phnum）。同様に含まれないので0です。

4000
セクションヘッダの1つのサイズ（e_shentsize）。セクションヘッダは後半に8つありますが（上の図で sh 0 から sh .shstrtabまで）どれも確かに 0x40 バイトになっています。

0800
セクションヘッダの数（e_shnum）。8つです。

0700
セクション名の一覧が格納されたセクション（.shstrtab）に対応するヘッダの番号です（e_shstrndx）。上の図では sh .shstrtab にあたり、確かに（0から数えて）7番めです。

このように、ELFヘッダにはELFの中身を読み解くのにまず必要な情報が書かれています。
なお、今回はELFの何バイトめに何があるのかを具体的に知るために1バイトずつ読んでいますが、情報を得るだけならふつうは readelf を使うのがよいです。

% readelf -a hello.as.o
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Advanced Micro Devices X86-64
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          392 (bytes into file)
  Flags:                             0x0
  Size of this header:               64 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           64 (bytes)
  Number of section headers:         8
  Section header string table index: 7
(略)

上で読み解いた内容と一致するのが分かります。

.text セクション

ELFヘッダの次は .text という名前のセクションです。ここは元のアセンブリを機械語に翻訳した結果が素直に入っています。先頭のバイトからみてみます。

6865 6c6c 6f2c 2077 6f72 6c64 00
hello, world をASCIIコードで表した文字列です。最後の 00 は文字列の終端です。

55 4889 e548 8d3d e8ff ffff e800 0000 00b8 0000 0000 5dc3
アセンブリを機械語に翻訳した結果です。元のアセンブリとの対応を、逆アセンブルして確認してみましょう。

% objdump -M intel -d hello.as.o
(略)
   d:	55                   	push   rbp
   e:	48 89 e5             	mov    rbp,rsp
  11:	48 8d 3d e8 ff ff ff 	lea    rdi,[rip+0xffffffffffffffe8] # 0 <main-0xd>
  18:	e8 00 00 00 00       	call   1d <main+0x10>
  1d:	b8 00 00 00 00       	mov    eax,0x0
  22:	5d                   	pop    rbp
  23:	c3                   	ret   

機械語が、「コンパイラ」の節で示したアセンブリとちゃんと対応していることが分かります。

main-0xd と書かれた行にある "e8 ff ff ff" は、"hello, world" にあたる文字列の開始位置(0x0)の、lea命令の次の命令(0x18)からのオフセットを表しています（0x0 - 0x18）。アセンブラを作るにあたっては、文字列の長さに応じて適切に変える必要があります。

0000 0000
パディングです。直後のセクション（.symtab）の先頭番地が、ここでは8の倍数である必要があるため、足りない分を埋めています。

.text セクションヘッダ

.text セクションに対応するヘッダです。名前やサイズなどが書いてあります。

2000 0000
セクション名です。.shstrtab という別のセクションに詰め込まれた文字列たちのうち、何バイトめから始まるかによって文字列を表します。0x20 bytes から始まるのは ".text" です。

0100 0000
セクションタイプ。1は "PROGBITS"。.text セクションのバイト列の意味はプログラム自身によって定義される、ということを表します。

0600 0000 0000 0000
セクションフラグ。0x06 、つまり二進法で 0110 は、

• プログラムの実行中にこのセクションが実際にメモリに載る
• 実行可能である
  を意味します。ビットごとに意味があり、その他の意味は elf.h を参照。

0000 0000 0000 0000
セクションの仮想アドレス。ここでは0、つまり先頭です。

4000 0000 0000 0000
セクションのELF中の開始位置。0x40 bytes から始まるという意味です。上の .text セクションを確認すると、たしかにそうなっています。

2400 0000 0000 0000
セクションのサイズ。0x24 = 36 byte です。

0000 0000
他のセクションへのリンク。とくになし。

0000 0000
追加情報。とくになし。

0100 0000 0000 0000
アラインメント制限。01は特に制限がないことを表します。たとえば 0x08 なら、セクションの開始番地は8の倍数である必要があります。

0000 0000 0000 0000
表が付属してる場合の一個あたりのサイズ。とくになし。

あとはアセンブラを作ってみる

ずいぶん長くなったので、それぞれの詳細についてはこのへんにしておきます。あとは、アセンブリを読み取ったうえで上記で調べたとおりのバイナリを出力するようにすればいいはずです。

気をつけるべき点としては、

• "Hello, World"にあたる文字列が長くなる場合は、適切に .text セクションのサイズも長くする必要がある。
• それに伴って後ろのセクションも芋づる式に後ろにずらす。その際、アラインメント制限に気をつける。
• 各セクションヘッダ内の開始位置やサイズを適切にセットする。

といったあたりでしょうか。で、そのようにして実際にアセンブラを作ってみました。名前は nanoa（Nano Assembler）です。

nanoa
https://github.com/mitsuchi/nano-lang/blob/master/nanoa.c

nanoa は、アセンブリを標準入力から受け取り、バイナリであるオブジェクトファイルを標準出力に出力します。

では実際に使ってみましょう。

% echo 'puts "hello, my first assembler!"' | ./nanoc > hello.s
% cat hello.s
    .intel_syntax noprefix
.LC0:
    .string "hello, my first assembler!"
(以下略)
% cat hello.s | ./nanoa > hello.o

nanoa によってオブジェクトファイル（hello.o）ができました。これを実行ファイルにするにはリンカが必要ですが、ここでは gcc にお願いしてみます。

% gcc hello.o -o hello
% ./hello
hello, my first assembler!

実行できました！

はじめて作ったアセンブラが動いて嬉しいです。

まとめ

gcc による出力を真似することで、簡単なアセンブラを作りました。"Hello, World"くらいしかできない上にELF限定なのでアセンブラの本質はほとんど現れていないはずですが、第一歩にはなったと思います。

なお、このアドベントカレンダーのことは プログラミング言語処理系が好きな人の集まり というSlackのチャンネルで知りました（招待リンクはこちら）。見ているだけでとても楽しいので、みなさまもぜひ。