自作OS開発におけるTips集 〜liumOSの場合〜

これは、自作OS Advent Calendar 2019 の7番目の素数日の記事です。(遅れてごめんなさい!)

はじめに

github.com

liumOSは、2018年の中頃から私が一人で開発している自作OSです。これまでにいくつかの自作OSを作っては壊し続けてきましたが、今回が3作目になります。(蛇足ですが、前作はchnosという名前で、2010-2012年に主に開発していたようです。)

今回は、このliumOS自体の紹介ではなく、開発をしてゆく中で色々と工夫したポイントを紹介したいと思います。

ビルドの依存関係を自動生成する

プロジェクトの規模が大きくなってくると、全ファイルを毎回ビルドしていては時間がかかるようになってきます。 liumOSプロジェクトでは、C++のソース(.cc)とヘッダ(.h)ファイルが合計80個程度あり、これらを毎回ビルドするのはCPU時間の無駄です。 そこで、分割コンパイルにより、変更のないファイルを再度ビルドしないようにする方法がよくとられますが、ソースファイルには変更がなくても、それがincludeしているヘッダファイルに変更があった場合は、やはり再度ビルドする必要があります。そのため、各ソースファイルがどのヘッダをincludeしているのかをMakefileに記述する必要があるのですが、これは人間のやるべきことではありません!ファイル一つ一つの依存関係を列挙するのは面倒ですし、依存関係が変わった際に整合性をとれる保証もありません。

ということで、面倒なことはコンパイラにやらせましょう。

詳細はclangのドキュメントなどをみてもらうことにして、以下ではliumOSの場合を説明します。(ソースはこちら。)

まずは、Makefileにこのようなルールを書いておきます。

%.o.d : %.c Makefile
    @$(LLVM_CC) $(CXXFLAGS_LOADER) -MD -MF $@ -c -o $*.o $*.c >/dev/null 2>&1
    @echo 'DEP $@'

%.o.d : %.cc Makefile
    @$(LLVM_CXX) $(CXXFLAGS_LOADER) -MD -MF $@ -c -o $*.o $*.cc >/dev/null 2>&1
    @echo 'DEP $@'

%.o.d : %.S Makefile
    @touch $@ # generate dummy
    @echo 'DEP $@'

...

ここで、LLVM_CC/CXXはCコンパイラへのパス、CXX_FLAGS_LOADRERは、ローダ用のCFLAGSが入っています。オブジェクトファイルを生成する各ルールのパラメータを少し変えてオブジェクトファイルの名前.dというファイルを生成するルールを書いています。アセンブリソース.Sなど、依存するヘッダがないものはダミーを生成しておきます。

そして、さらに以下のような記述をMakefile最後に書いておきます。

-include $(LOADER_DEPS)
-include $(KERNEL_DEPS)

このLOADER_DEPSには、上で説明した生成規則で生成される*.dのファイルが列挙されています。(acpi.o.d apic.o.d asm.o.d inthandler.o.d ... のような感じです。)

実際には、このような感じでソースコードのリストから生成しています。

COMMON_SRCS= \
             acpi.cc apic.cc asm.S inthandler.S \
             ...

LOADER_SRCS= $(COMMON_SRCS) \
             efimain.cc \
             ...

KERNEL_SRCS= $(COMMON_SRCS) \
             command.cc \
             ...

LOADER_OBJS= $(addsuffix .o, $(basename $(LOADER_SRCS)))
LOADER_DEPS= $(addsuffix .o.d, $(basename $(LOADER_SRCS)))
KERNEL_OBJS= $(addsuffix .elf.o, $(basename $(KERNEL_SRCS)))
KERNEL_DEPS= $(addsuffix .elf.d, $(basename $(KERNEL_SRCS)))

Makeは、このincludeディレクティブをみつけると、C言語のincludeと同じようにそのファイルの内容を書かれた場所に展開しようとするのですが、もしそのファイルが存在しなかった場合、これまで読み込んだ生成規則を適用して、読み込むべきファイルを生成しようとしてくれます。これにより、対象のソースファイルが更新された場合や、依存関係を記したファイルが存在しない場合は、自動的それをmakeしてくれるわけです。

生成される.dファイルの中身は、このような感じになっています。

$ cat acpi.o.d
acpi.o: acpi.cc liumos.h acpi.h apic.h generic.h \
  /usr/local/Cellar/llvm/9.0.0_1/lib/clang/9.0.0/include/stddef.h \
  /usr/local/Cellar/llvm/9.0.0_1/lib/clang/9.0.0/include/__stddef_max_align_t.h \
  third_party_root/include/stdint.h \
  third_party_root/include/machine/_default_types.h \
  third_party_root/include/sys/features.h \
  third_party_root/include/_newlib_version.h \
  third_party_root/include/limits.h third_party_root/include/newlib.h \
  third_party_root/include/sys/cdefs.h \
  third_party_root/include/sys/syslimits.h \
  third_party_root/include/sys/config.h \
  third_party_root/include/machine/ieeefp.h \
  third_party_root/include/sys/_intsup.h \
  third_party_root/include/sys/_stdint.h immintrin.h loader_support.h \
  guid.h asm.h console.h efi.h efi_file.h elf.h \
  third_party_root/include/elf.h gdt.h githash.h hpet.h interrupt.h \
  ring_buffer.h scheduler.h process.h execution_context.h \
  kernel_virtual_heap_allocator.h paging.h stl.h phys_page_allocator.h \
  sys_constant.h pmem.h keyboard.h keyid.h serial.h sheet.h \
  sheet_painter.h text_box.h

ここに書かれた生成規則の依存関係をみて、Makeは実際にacpi.oを生成するかどうか決定してくれます。わーい、これでCPU時間を節約できましたね!

macOSLinuxのどちらでもビルドしたい!

liumOSは、macOSLinuxのどちらでもビルドできるようになっています。これは主に、LLVMツールチェーンが異なるプラットフォーム向けのクロスビルドにデフォルトで対応してくれているおかげなのですが、ツールチェーン自体は対応していても、周辺のライブラリとの兼ね合いで困難な点がいくつかあったので、少し説明したいと思います。

まず、macOS標準のclangは、Appleが少し手を加えているようで、なんとx86_64-pc-win32-coffx86_64-unknown-none-elfなどのターゲット指定に対応していないという悲しい事実があります。また、liumOSではEDK2やgnu-efiなどのUEFI開発環境を用いずに、clang+lldのみでOSのローダを生成しているのですが、macOSにはなんとlldが入っていません!(その代わり、ld64というリンカが入っているようです。)ですから、Homebrew経由でふつうのLLVMツールチェーンを入れる必要があります。

これでツールチェーン自体は揃ったのですが、環境ごとにコンパイラを切り替えなければなりません。そこで、liumOSでは以下のMakefileで、該当するアーキテクチャ向けのツールチェーン情報を取得しています。

$ cat common.mk 
THIS_DIR:=$(dir $(abspath $(lastword $(MAKEFILE_LIST))))

OSNAME=${shell uname -s}

ifeq ($(OSNAME),Darwin)
$(THIS_DIR)cc_cache.gen.mk : $(THIS_DIR)scripts/gen_tool_defs_linux.sh
    @ $(THIS_DIR)scripts/gen_tool_defs_macos.sh > $@
else
$(THIS_DIR)cc_cache.gen.mk : $(THIS_DIR)scripts/gen_tool_defs_linux.sh
    @ $(THIS_DIR)scripts/gen_tool_defs_linux.sh > $@
endif

include $(THIS_DIR)cc_cache.gen.mk
CLANG_SYSTEM_INC_PATH=$(shell $(THIS_DIR)./scripts/get_clang_builtin_include_dir.sh $(LLVM_CXX))

ここで、なぜ直接シェルを叩いてツールチェーンの情報を変数に入れずに、cc_cache.gen.mkなるファイルを生成して読み込んでいるかというと、

$ cat scripts/gen_tool_defs_macos.sh 
LLVM_PREFIX=`brew --prefix llvm`
echo "LLVM_CC:=${LLVM_PREFIX}/bin/clang"
echo "LLVM_CXX:=${LLVM_PREFIX}/bin/clang++"
echo "LLVM_LLD_LINK:=${LLVM_PREFIX}/bin/lld-link"
echo "LLVM_LD_LLD:=${LLVM_PREFIX}/bin/ld.lld"
echo "LLVM_AR:=${LLVM_PREFIX}/bin/llvm-ar"
echo "LLVM_RANLIB:=${LLVM_PREFIX}/bin/llvm-ranlib"

このスクリプト中のbrew --prefix llvmがちょっと重くて、

$ time brew --prefix llvm
/usr/local/opt/llvm

real    0m0.723s
user    0m0.406s
sys 0m0.303s

毎回実行するコストが大きいためです。ビルドするたびに待たされるのは困りますよね?

というわけで、無事各ツールのパスは手に入ったわけですが、もう一つ引っ掛かりどころがあります。それは、stdint.hなどの、コンパイラが提供するヘッダファイルのパスについてです。

C標準ライブラリのうち、stdint.hなどの一部のヘッダは、コンパイラの実装に依存するため、標準ライブラリではなくコンパイラによって提供されます。このヘッダは通常であれば、デフォルトのインクルードパスに含まれているため、気にする必要はないのですが、私たちはOSを書きたいので、-nostdlibinc -nostdlibを設定してしまっています。そうすると、コンパイラが提供するヘッダファイル、つまりはコンパイラさえあれば使えるはずのヘッダファイルが見えなくなってしまい、困ってしまいます。(newlibなども、コンパイラが提供するstdint.hに依存しているため、なんとかしないといけません。)

では、この「コンパイラが提供するヘッダファイル」はどこにあるのかというと…

the default location to look for builtin headers is in a path $(dirname /path/to/tool)/../lib/clang/3.3/include relative to the tool binary. https://clang.llvm.org/docs/LibTooling.html#libtooling-builtin-includes

ということで、わかりづらいのですが、ツールチェインのバイナリが置かれているパスから相対パス../lib/clang/<clangのバージョン>/include にあるようです。

…clangのバージョンがいるの、つらい…。

ということで、シェルスクリプトでよしなにやります。

$ cat scripts/get_clang_builtin_include_dir.sh
#!/bin/bash
if [ "$(uname)" == 'Darwin' ] || [ "$(expr substr $(uname -s) 1 5)" == 'Linux' ]; then
    # macOS, Linux
    version=`$1 --version | head -1 | sed 's/^.*[^0-9] \([0-9]*\.[0-9]*\.[0-9]*\).*$/\1/'`
    basepath="$(dirname $(dirname $(which $1)))"
    echo ${basepath}/lib/clang/${version}/include
else
    echo "Your platform ($(uname -a)) is not supported."
    exit 1
fi

ここで、第一引数にはclangへのパスが入ってきていることを想定しています(上記のcommon.mkを参照)。このようなスクリプトを、以下のように実行すれば、めでたく組み込みヘッダファイルのインクルードパスを得ることができます。

$ ./scripts/get_clang_builtin_include_dir.sh /usr/local/opt/llvm/bin/clang
/usr/local/opt/llvm/lib/clang/9.0.0/include

これを適宜コンパイラに指定してあげれば、無事にstdint.hなどが使えるようになるはずです!

というわけで、「ツールチェーンのパス」と「組み込みヘッダファイルのパス」に気をつければ、macOSLinuxでクロスビルドをすることはそんなに難しくありません。皆さんもぜひお試しください!

まとめ

自作OSは、一人もしくは少人数で作っている場合がほとんどだとは思いますが、その割にソースコードの規模が大きくなりがちです。そのような状況下で、効率よく、ストレスをためずに開発をするためには、今回紹介したような開発環境としての工夫も大事になってきます。 この記事をきっかけに、みなさんの自作OS開発が少しでも効率化・汎用化されれば幸いです。 年末、そして来年も、自作OSを楽しんでいきましょう!

SECCON 2019 Online CTF Writeup

f:id:hikalium:20191020154255p:plain
follow-me

Harekazeの一員として参加しました。4724点を得て14位だったようです。

私は2問に取り組み、うち1問を解けたのでメモ。

follow-me (reversing)

ちょっとした計算機アプリのバイナリが渡される。そのプログラムをIntel Pin を利用したトレーサでトレースした結果と、そのトレーサのソースが与えられる。このトレース結果が同一になるような、アプリケーションへの入力を求めてねという問題。

与えられているトレース結果はこんな感じ。

{"event": "image_load", "image_name": "/home/tomori/follow-me/build/sample/calc", "image_id": 1, "base_addr": "0x55f6b4d44000", "image_size": "0x1377"},
{"event": "image_load", "image_name": "/lib64/ld-linux-x86-64.so.2", "image_id": 2, "base_addr": "0x7f13ae220000", "image_size": "0x26c23"},
{"event": "image_load", "image_name": "[vdso]", "image_id": 3, "base_addr": "0x7ffc2b775000", "image_size": "0x100a"},
{"event": "image_load", "image_name": "/lib/x86_64-linux-gnu/libc.so.6", "image_id": 4, "base_addr": "0x7f1399a39000", "image_size": "0x3f0adf"},
{"event": "branch", "inst_addr": "0x55f6b4d445de", "next_inst_addr": "0", "branch_taken": true},
{"event": "branch", "inst_addr": "0x55f6b4d44f44", "next_inst_addr": "0", "branch_taken": false},
{"event": "branch", "inst_addr": "0x55f6b4d44765", "next_inst_addr": "0", "branch_taken": true},

最初の行のbase_addrと、各分岐結果のinst_addrを差し引きすることで、実行バイナリ内のオフセットがわかる。

h_noson師匠が数秒で入力の文法と分岐の解析結果を与えてくれたので、あとは入力結果を推測するだけという簡単なお仕事。

0-9 (c): val = c - 0x30 + val * 10
,: push val to stack
+: pop twice and push(x + y)
-: pop twice and push(x - y)
*: pop twice and push(x * y)
m: pop twice and push(min(x, y))
M: pop twice and push(max(x, y))
C: pop twice and push(x C y)

たとえば./calc '5,3,+'の結果は8になる。そんなかんじ。 数値は複数桁になることもできて、先頭が0埋めでも問題ないことを確認した。

0xc1c (false): 0-9
0xbe9 (false): ,
0xc58 (false): +
0xcaf (false): -
0xd06 (false): *
0xd5d (false): m
0xdb4 (false): M
0xe08 (false): C

また、演算子による分岐だけでなく、計算時の値によっても分岐結果が変わることがわかった。

乗算は、左辺の値-1回、0xa1fを通る。

r '13,3,*' -> 0xa1fは12回呼ばれる

加算は、(右辺の値%10) + 1回、0xa1fを通る。

r '13,18,+' -> 0xa1fは9回

そして、0xe87の分岐がtrueのときに項を読み続けるので、これを境界としてトレース結果を分割し、上記の結果を総合して推測すればよい。

たとえば、以下のようなトレース列は

e87", "next_inst_addr": "0", "branch_taken": true},
be9", "next_inst_addr": "0", "branch_taken": true},
c1c", "next_inst_addr": "0", "branch_taken": true},
c58", "next_inst_addr": "0", "branch_taken": true},
caf", "next_inst_addr": "0", "branch_taken": true},
d06", "next_inst_addr": "0", "branch_taken": false},
8dc", "next_inst_addr": "0", "branch_taken": true},
8dc", "next_inst_addr": "0", "branch_taken": true},
a5b", "next_inst_addr": "0", "branch_taken": true},
a81", "next_inst_addr": "0", "branch_taken": true},
a0b", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": true},
a1f", "next_inst_addr": "0", "branch_taken": false},
a81", "next_inst_addr": "0", "branch_taken": false},
93e", "next_inst_addr": "0", "branch_taken": true},
d54", "next_inst_addr": "0", "branch_taken": true},
  • 0xd06の分岐がfalseなので乗算
  • 0xa1fの分岐を7回通っているので、この演算が実行される際の左辺の値は8

ということがわかる。

トレース結果より、入力列は

ccc,ccc,ccc,ccc,ccc,cccc,ccc,mm-mM-ccc,ccc,ccc,mm-ccc,ccc,ccc,ccc,ccc,-+-M+ccc,ccc,ccc,mm*

と予想できる(cは数字が入る)。これは実際に値が1つに収束するのでよさそうである。

加算と乗算に気をつけつつ、後ろ側からいい感じに値を割り当てていく。たとえばこんなかんじに。

001,002,003,004,005,0006,007,mm-mM-001,002,003,mm-008,005,001,004,001,-+-M+001,002,003,mm*

あとは問題の指示通りにサーバーに答えを投げてあげれば、フラグを得ることができた。

{"error":false,"flag":"SECCON{Is it easy for you to recovery input from execution trace? Keep hacking:)}","message":"Thanks! I'll give you a flag as a thank you."}

repair (forensics)

解けなかった…。

問題としては、壊れたAVIファイルが与えられ、その先頭1セクタ(512Bytes)が欠損しているので、なんとかしてその部分(つまりはヘッダ)を復元してねーという話だった。

解析プログラムをささっと書いて、だいたいどんなデータ構造か、フレーム数はいくつかなどを調べて、それっぽいパラメータでffmpegで動画を生成し、先頭512Bytesをつぎはぎするなどしたが、codecが特定できず断念した。

AVI file reader for SECCON 2019 Online CTF

moviリスト内の00dcというチャンクがフレームのデータで、こんな感じで並んでいる。

@+0x00146E: LIST                                                                                     
  size = 2789052                                                                                  
  movi                                                                                               
  @+0x00147A: 00dc                                                                                
    size = 32440                                                                                     
   00 00 7E B8 03 C0 02 1C                                                                        
   00 01 10 00 7E AE 00 00 00 00 02 1C 03 C0 20 00 00 04 22 00 00 0A 00 00 00 00 00 00 32 00 7E 94...
  @+0x00933A: 00dc                                                                                
    size = 4086                                                                                      
   01 00 0F F6 03 C0 02 1C                                                                        
   00 01 11 00 0F EC 00 00 00 00 02 1C 03 C0 20 00 00 04 22 00 00 04 31 00 0F D8 00 00 00 00 00 00...
  @+0x00A338: 00dc                                                                                
    size = 4086                                                                                      
   01 00 0F F6 03 C0 02 1C                                                                        
   00 01 11 00 0F EC 00 00 00 00 02 1C 03 C0 20 00 00 04 22 00 00 04 31 00 0F D8 00 00 00 00 00 00...

各フレームデータの先頭8bytesは以下のようなフォーマットになっているっぽい

     00 00 7E B8 03 C0 02 1C 
     ^^ 0ならキーフレーム, 1なら中間フレーム
           ^^ ^^ ビッグエンディアンでこのフレーム全体のサイズ(00dcのサイズと一緒)
                 ^^ ^^ 960(Width)
                       ^^ ^^ 540(Height)

ということがわかったので、ビッグエンディアンでこういうフォーマットになっているcodecないかなと探したり、ffmpegのcodecを片端から試してこのような出力が得られないか試したが間に合わなかった。かなしい。

参考文献: OpenDML AVI File Format Extensions

まとめ

CTFは生活リズムを破壊する(たのしいので)

あとAVIファイルのフレームデータの区切りがHex上で見えるようになったのでよかった。

技術書典6に初出展したところ300部の新刊が完売した話

2019-04-14, 技術書典6が池袋で開催されました。私は、前回の技術書典5の際に、買いに行く側としての初参加を果たしたのですが、その際「来年は書く側で出しなよ〜」と多数の皆様に煽られ応援されたのでした。

その流れを踏まえ、今回は絶対に書いてやるぞ!という強い意志で、アンケートをとった結果

OS Girlsというタイトルが人々にもっとも望まれているということでしたので、ひとまずサークル参加の応募をしたところ、高倍率の中ではありましたが、運良く参加できることが決まったのでした。

もうこうなったら、何か出さないわけにはいかない(出せなかった場合、もう一生技術書典からbanされてもおかしくない)ので、とにかくやっていくぞという気持ちになれました。

結果、初めての執筆・入稿・販売ということで、ヒヤヒヤしながらではありましたが、なんとなんと用意していた印刷部数のすべて、300部を頒布し尽くすことができました!

というわけで、ここまでの大雑把な流れと、ついさっきまでの当日の様子、反省点などをまとめておきたいと思います。

前日まで

正直言って、進捗は芳しくありませんでした。以下の画像は、執筆リポジトリのCode frequencyのグラフです。

f:id:hikalium:20190414210526p:plain
Code frequency of os-girls

どう見ても、締め切り直前にどかっと書いている様子がわかりますね。

ちなみに、入稿は4/9に行いました。(印刷は日光企画さんにお願いしました。)

元々は、日光企画の技術書典のしめきり表にある「40%OFF」つまり3/27に入稿できたらいいな、とか考えていたのですが、無理でした。ええ、無理は禁物です。

結局、自分はもう真のしめきりがいつだか知っているのだから、それを騙すことはできないのです。ロジックは正直です。

というわけで、滑り込みで入稿して、しかもその日の締め切り時間の数時間前に確認の電話があり

「原稿の本文の一部が完全に崩れていて読めない」

という衝撃的な事実がわかり、SATySFiで出力したものを入稿するなどという冒険をした自分を呪うなどしました。(日光企画さんにはお手数をおかけしました…丁寧な対応でほんと助かりました…)。

とりあえず、Macで「印刷」からpdfをエクスポートし直したものと、最悪のケースに備えて全ページを600dpiのjpgで出力したものを同封して再入稿するなど、バタバタとしたのち、連絡がなくて心配になりついに電話して確認したところ

「いただいたデータで大丈夫でしたので当日お届けいたします!」

と言っていただけて、やっと人心地ついたのでした。

前日準備

さて、これであとは人事を尽くして天命を、というところでしたが、ブースの設営もなにせ初めてでしたので、先人の知恵をインターネットで検索して、必要そうなものをリストアップして急遽買うなどしました。

急遽買ったものとしては、ブックスタンド、おかねを入れる袋、コインケース、透明ブックカバーなどがありました。

あと、現地には電源がないということだったので、大容量のモバイルバッテリーを買うなどしました。(元々欲しかったのでちょうどよかった。)

さらには、前日になってはじめて「500円で頒布するならおつりの500円玉がたくさん必要では?」ということに気づき、焦って1000円を握りしめ、コンビニに走ってアイスを買うなどしました。

ブース環境ともちもの

ブースの環境としては、運営からの注意事項にもあった通り

  • 机半卓(横90センチ×奥行45センチ)椅子2脚
  • Wi-Fiはなし
  • 電源もない
  • 飲食は可能、ごみすて場なし

という状況でした。

持っていったものとしては、

  • hikaliumステッカー全部(400より少し少ないくらいか?)
  • 目玉・ダブルクリップ(テーブルクロス固定等に使う)
  • モバイルバッテリー(スマホ充電用)
  • スケッチブック的ななにか(おしながきや完売表示に)
  • ふせん(価格表示やとりおき表示に)
  • テーブルクロス(みんなやってる)
  • マスキングテープ(テーブルクロスとかブックスタンドを固定できる)
  • 油性マーカ(おしながき書いたり)
  • ノート(おかねの管理等)
  • ブックスタンド(サンプル展示用)
  • ブックカバー(サンプル用)
  • 名刺(あるといいかも)
  • のみもの(水がないと死ぬ)
  • おかね・コインケース・お金を入れる袋(お金はだいじ)

という感じでした。

あと、本体としてのPCとか、通常の装備を持って行きました。

当日

なんとか起床に成功し現着。

本も無事に机の下に配送されていて、ほんと印刷所の方と運営スタッフありがとうという気持ちになった。

ほぼ初めての印刷入稿だったが、想像以上に「数学ガール」感を出せていたのでとてもよかった。マットPP貼り大好き!

そして、ブース設営完了。

(このあと、windholeの風穴さんから、吊るタイプのpopハンガーをお借りして、ブースがさらにパワーアップしました!)

ちなみに、売り子はセキュキャン同期で、かつCERNLLVMを書いていたことで知られているYuka Takahashi氏にお願いしました。ほんとに優秀で超助かりました。ありがとう。popなどはyuka氏が書いてくれました。

技術書典の会場はラッシュ時の中央線並みに混雑し、かつとても広く、出口は1箇所しかないため、会場外に昼食やトイレに行く場合はものすごく時間がかかります。それを考えると、売り子なしの1人でブースを切り盛りするのは不可能です。かならず売り子はだれかにお願いしましょう。

そして、あとは売るだけ。とにかく売る。お金を受け取って商品を渡す。簡単後払いのバーコードを読んでもらって確認画面を見て商品をわたす。それの繰り返しです。

弊ブースでは、現金・かんたん後払い・Pixiv Payの3種の支払い方法に対応していました。

内訳としては、簡単後払いが予想以上に多く、ざっと確認した限りで100名以上の方が利用してくださっていました。

Pixiv payは2名ほどでしたが利用者がおり、それ以外はすべて現金だったようです。

(かんたん後払いアプリ、販売数や金額の統計が見られないのでつらいです。とても便利なアプリなので、その部分を改善していただけるとより使いやすくなると思います!)

現金の支払いについては、Pixiv payのレジ機能で一応カウントしていたのですが、応対が忙しくなるにつれ、入力漏れが増えてきてしまいつらかったです。

当日ネタと終焉

あとは、ステッカーを50枚強奪していく悪いオタクが出現したり(きちんと対価はいただいているのでよいのです)

差し入れをさまざまな方からいただいたり(差し入れてくださった皆さま、ありがとうございました!!)

そうしていたらいつのまにか机の上の在庫だけになり、

そして完売。(ちなみに最後の一冊は、BitNOSのuchanさんが買おうとしていたら、隣のブースの暗黒通信団の方が颯爽とお買い上げしていきました。)

私もまさか完売するとは思っておらず、完全にBOOTH倉庫に直接発送できるサービスを使おうと思っていたのですが、使わずに済んでしまいました。びっくり。

とはいえ、早く売り切れになりすぎることもなく、大幅に売れ残ることもなく、ちょうどよいか少し少ない、といった程度の冊数だったのではないかな、と思います。

ちなみに、この記事を書いている、技術書典終了後の夜のチェック数はこんな感じでした。

f:id:hikalium:20190414215653p:plain

まとめ・反省点

結論としては、本当に最高の1日でした。まさか、こんなにも自分の書いた文章を買ってくださる方がたくさん、しかもリアルワールドに存在するなんて、すごくすごくありがたいことです。

正直、もっと本のクオリティをあげたかったな、というところが最大の反省点に今はなっています。

OSGirlsを読んでくださったみなさまはお気づきかと思いますが、実は結構内容が不足していたり、唐突な終わり方になってしまったりしています。特に、途中で唐突に出てくる elf.hbuild.sh なんて、本のどこを読んでも書いてありません。ええ、これは私の能力不足です。

サポートページへのリンクもつくったのですが、内容がゼロです。本当にすみません。一週間中に充実させます。(少なくとも、本の中でアキとミカが体験したことをできるだけの情報は提示します。)

…とまあ、たいへん穴だらけの作品だったわけですが、それでもみなさんが私に期待して、購入してくださったということがとても嬉しいですし、原動力にもなりました。

秋の技術書典では、もちろん続きを出したいと思います。今度は、さらに盛りだくさんで、充実した内容になるようがんばります。

というわけで、今後も OSGirls は続けて行きたいと思いますので、みなさまどうかよろしくお願いいたします。

デジタルデータ販売

BOOTHにてPDFデータの販売を開始しました。

booth.pm

こちらのデータは、現在は技術書典6で頒布した冊子と完全に同一の内容ですが、今後内容を更新した際には最新の版に更新してゆく予定です。

次の技術書典に向けて応援してくださるみなさまや、物理本を買うことができなかったので内容が気になる方はぜひ購入していただけるとありがたいです。

謝辞

OSGirlsの表紙絵は、私の古くからの友人である @From_boku_To_ 氏に描いていただきました。忙しい中、無理を言って描いてくださってありがとうございました。今後ともよろしくお願いします(笑)。

技術書典6の販売ブースでは, Yuka Takahashi氏にお手伝いいただきました。完璧なオペレーションで私が離席中も一切心配する必要がありませんでした。本当に感謝です。

また、何度か執筆の場を設けてくださったサイボウズの風穴さん( @windhole )にも大いに感謝しています。また執筆会を設けていただけると助かります!

そして、今回の作品の形態のベースとなった「数学ガール」作者の結城浩氏と、私をOSの世界に引き込んでくれた「30日でできる!OS自作入門」作者の川合秀実氏にも深くお礼を申し上げます。ありがとうございました。

次回に向けて

技術書典7でもOSGirlsを出すぞー!!!

f:id:hikalium:20190414223445j:plain

compilium v2 におけるdeclarationの実装

この記事は、C言語 Advent Calendar 2018のうち、3連続素数和が素数になる最小の数番目の記事です。

…といったものの、かなり公開が遅れてしまいました。ごめんなさい…(SECCON国内決勝とかぶったりした&計画性がないのが原因です。)

また、言語実装アドベントカレンダーのほうでもcompiliumに関連する内容の記事を書きましたので興味があればご参照ください。

hikalium.hatenablog.jp

はじめに

Cコンパイラを実装したことのあるみなさんも、変数の宣言や型の宣言を行うdeclarationの実装で詰まってしまった方は多いのではないでしょうか。 この記事では、Cのdeclarationをインクリメンタルにうまく実装する方法について検討した記録と、その実装を一部途中まで進めた話を紹介します。

仕様についてはもう知ってるので説明不要だよ!というプロの皆様は、下の方にある「インクリメンタルに実装しよう!」を読んでいただくと時間の節約になります。

まずはdeclarationについて知る

何はともあれまずは仕様書を読んで、おおまかに仕様を理解します。いくらインクリメンタルに開発するとはいえ、最終的な到達目標をきちんと理解していないことには、途中で立ち行かなくなってしまいますからね。 というわけで、declarationとは一体どのようなものか、仕様書に沿って見ていくことにしましょう。

そもそもdeclarationってなんだ?

仕様書によれば、declarationとは、いくつかのidentifierについてその解釈や属性を与えるもので、具体的には

  • ローカル変数やグローバル変数などの記憶領域を持つオブジェクト
  • 関数
  • 列挙定数
  • typedef名

となるような識別子を宣言するものであると書かれています。というわけで、declarationには必ず名前となる識別子が一つ以上、それに対応する属性もいっしょに書かれていることになります。 (ちなみに、_Static_assertも構文上はdeclarationに入っていてこれは識別子を持たないのですが、実質的にはdeclarationではないのでここでは説明しません。)

declarationの最もトップレベルな構文としては、以下のようになっています。(末尾のoptは省略可能という意味です。)

declaration:
       declaration-specifiers init-declarator-listopt ;
       static_assert-declaration
declaration-specifiers:
       storage-class-specifier declaration-specifiersopt
       type-specifier declaration-specifiersopt
       type-qualifier declaration-specifiersopt
       function-specifier declaration-specifiersopt
       alignment-specifier declaration-specifiersopt
init-declarator-list:
       init-declarator
       init-declarator-list , init-declarator
init-declarator:
       declarator
       declarator = initializer

…といって理解できればみんな困らないので、上の構文をint a = 3, *b;について図示してみたものが以下です。

f:id:hikalium:20181224205850p:plain
declaration int a = 3, *b;

みなさんご存知の通り、int a = 3, *b;を解釈すると、初期値3をもつint型の変数aと、int型へのポインタ変数b、が宣言されますね。

構文的な重要ポイントとしては、

  • declarationdeclaration-specifiersがひとつと、init-declaratorが複数合わさったものであり
  • init-declaratordeclaratorと、任意でinitializerをつけることができる

ということです。とりあえず、最初はinitializerのことは無視することにして、いまここで最も重要なことは

  • declaration-specifiers + declarator でひとつの宣言が出来上がる

ということです。ではdeclaration-specifiersdeclaratorについて見ていくことにしましょう。

declaration-specifiersってなんだ?

上の構文

declaration-specifiers:
       storage-class-specifier declaration-specifiersopt
       type-specifier declaration-specifiersopt
       type-qualifier declaration-specifiersopt
       function-specifier declaration-specifiersopt
       alignment-specifier declaration-specifiersopt

からわかることとしては、なんとかspecifierとか、なんとかqualifierというのが1つ以上並んだものがdeclaration-specifiersです。

type-specifier

たとえば、type-specifierは、よくみるintcharとかunsignedとかのことです。

type-specifier:
        void        
        char        
        short       
        int
        long        
        float       
        double      
        signed      
        unsigned    
        _Bool       
        _Complex    
        atomic-type-specifier
        struct-or-union-specifier
        enum-specifier
        typedef-name

また、これにはstructやunion, enumの型情報も含まれます。つまり、struct KV{const char *key; void *v;}とかはtype-specifier, 中でもstruct-or-union-specifierに含まれるわけです。

さらに、typedefによってつけられた型の別名もここに入ります(typedef-name)。typedefのせいで、C言語のパーサはパースしながらdeclarationを解釈しなくてはいけないのです。まあ、最初は実装しなくてもいいのですが。

enum-specifier

enum E{kKey1 = 3, kKey2} とかのことです。

type-qualifier

constとかvolatileとかです。

function-specifier

inline_Noreturnのことです。

storage-class-specifier

typedefとかexternとかstaticとかのことです。

declaration-specifiersの衝撃の事実

もっと詳しく知りたい方は、仕様書を適当に読んでほしいのですが、面白いネタとしてはこんな話があります。

なんと、上記のspecifierたちは、一部の例外を除いて順序を自由に入れ替えてよいことになっています。したがって、 unsigned long const int long externとか書いても全く問題ないわけです。(人間には厳しいですが。)

declaratorってなんだ?

正直、declaration-specifiersはやるだけです。簡単です。でもこっちのdeclaratorは、少し冷静になってしっかり理解をする必要があります。

まずdeclaratorそのものは単純明快です。

declarator:
      pointeropt direct-declarator

pointer:
      * type-qualifier-listopt
      * type-qualifier-listopt pointer

これは要するに、ポインタの*(とその修飾子列の組)が0個以上並んだあとに、direct-declaratorが続くよ、という意味です。たとえば、int *b;とかなら

f:id:hikalium:20181224215246p:plain
int *b;

という感じになります。この例は、direct-declaratorには識別子が一つだけくるケースになっています。

ところが、direct-declaratorはそう単純ではありません。

declarator:
    pointeropt direct-declarator

direct-declarator:
    identifier
    ( declarator )
    direct-declarator [ type-qualifier-listopt assignment-expressionopt ]
    direct-declarator [ static type-qualifier-listopt assignment-expression ]
    direct-declarator [ type-qualifier-list static assignment-expression ]
    direct-declarator [ type-qualifier-listopt * ]
    direct-declarator ( parameter-type-list )
    direct-declarator ( identifier-listopt )

なんとdirect-declaratorは自身とdeclarator再帰的に含むことができます。 (これはつまり、declaratordeclarator再帰的に含むことができるということです。) したがって、単にdeclaratorと呼んでしまっては、declaratorの全体をさすのか、部分を指すのか分かりづらくなってしまいます。

というわけで、あるdeclarationにおいて、他のどのdeclaratorにも含まれないようなdeclaratorのことを、仕様書の言葉を借りてfull-declaratorと呼ぶことにしましょう。

例としては、

  • int *f(int a, int b);*f(int a, int b)
  • char m[3][4];m[3][4]
  • void (*fp)(int a);(*fp)(int a);

がfull-declaratorにあたります。

declaratorの構文をじっくり見ていただくとわかるのですが、いくらdeclarator入れ子になっても、ひとつのfull-declaratorについて、identifierが現れるのはちょうどひとつになることが分かります。

つまり、declaratorは、宣言の情報のうち

  • ポインタ
  • 配列
  • 関数
  • そしてひとつの識別子(declaratonが定義しようとしている名前)

を表現することがわかります。

declarationの構文を書き下してみる

さて、ここまでの情報をもとに、declarationをもう少しわかりやすい形で書き直してみることにしましょう。

結局のところ、declarationは、なんらかの識別子と、その型や属性をペアにしたものを複数同時に表現する構文なわけです。 なぜ複数になるのかというと、init-declarator-listによって、ひとつのdeclarationの中に複数のfull-declarationが入ることがあるためなのですが、とりあえずひとつの識別子について型や属性を知りたいので、ここでは単純にdeclaration = declaration-specifiers + full-declaratorで構成されると考えて説明します。

まず、declarationの各部分を、以下のような文字でおくことにします。

T: declaration-specifier
D: declarator
P: pointer
E: direct-declaratorの各断片
I: Identifier 

そしてこれらを用いて、各構文を正規表現風に記述するとこんな感じになります。

declaration = TD
D = P*[I|(D)]E*

最もシンプルなケース

たとえば、int a;というdeclarationは、書き下すとTIになります。 int a;を回りくどく書けば、a is_a(int)ですからI(t): Iが識別子Xだとして、X is_a(t) を返すと考えればよさそうです。

ポインタの適用順

次のケースは、ポインタの場合です。たとえば、int * const * p;などを考えてみましょう。 ちなみに、これも回りくどく書けばp is_a(pointer_of(const_pointer_of(int)))となるのはすぐわかるでしょう。 念の為言っておきますと、ポインタ変数そのものは書き換えられますが、1回デリファレンスしたものはconstなポインタ変数になるので書き換えできず、2回デリファレンスしたものはただのint型なので書き換えられます。

さて、説明を容易にするため、PやEについて、左から右に番号を振ることにします。つまり、

declaration = T P_1 P_2 ... [I | (D)] E_1 E_2 ...

という感じです。

このノリでいくと、

int * const * p;
= T P_1 P_2 I

T: int
P_1: * const
P_2: *
I: p

ということになります。

さて、Pは入れ子にできますから、

P(t): pointer_of(t)を返す。(constがついているならconst_pointer_of(t)を返す)

とおくと都合がよさそうです。

この型がp is_a(pointer_of(const_pointer_of(int)))であることを考えると、連続したPは

I(P_2(P_1(T)))
= I(P_2(P_1(int)))
= I(P_2(const_pointer_of(int)))
= I(pointer_of(const_pointer_of(int)))
= p is_a(pointer_of(const_pointer_of(int)))

というように、P_1 P_2 P_3 => ...P_3(P_2(P_1(t)))と評価すればうまくいきそうです。

配列の適用順

じゃあ次は配列いってみましょうか。

たとえば、よくあるint arr[3][5];は、arr is_a(Array(size: 3, type: Array(size: 5, type: int)))という意味です。

ということでE(t): Eがarray declarator [n] ならば、Array(size: n, type: t)を返す。と考えればよさそうです。

適用順としては、 E_1 E_2 E_3 => E_1(E_2(E_3(t)))とすれば、

I(E_1(E_2(T)))
= I(E_1(E_2(int)))
= I(E_1(Array(size: 5, type: int)))
= I(Array(size: 3, type: Array(size: 5, type: int)))
= arr is_a(Array(size: 3, type: Array(size: 5, type: int)))

となってうまくいきそうです。

関数の場合

関数も配列と同じdirect-declaratorに含まれるので、配列の適用順を参考にすれば E(t): Eがfunction declarator (arg1, arg2, ...) ならば、Func(returns: t, args: (arg1, arg2, ...)) を返す。 とすれば、たとえばvoid f(int a);などは

I(E_1(T))
= I(E_1(void))
= I(Func(returns: void, args: (int a))
= f is_a(Func(returns: void, args: (int a))

となってうまくいきそうです。(引数に関しては、declarationを再帰的に適用すれば目的の結果が得られるので今回はそのままにしています。)

ところで、関数を要素とするような配列や、配列・関数を戻り値とするような関数をつくることはできてはならないと仕様書に明記されています。

したがって、Eが関数の場合にE同士がネストするケースをここで紹介することは不可能です。

E, P, (D)|Iの適用順

たとえば、みんな大好き

void (*signal(int sig, void (*func)(int)))(int);

は、書き下すと

T1(P2_1 I2 E2_1)E1_1

となります。そして、ここから導ける型としては

signal is_a(
  Func(
    returns: pointer_of(Func(returns: void, args: (int))),
    args: (int sig, void (*func)(int))
  )
)

となることから、逆に辿って考えてみると、

signal is_a(
  Func(
    returns: pointer_of(Func(returns: void, args: (int))),
    args: (int sig, void (*func)(int))
  )
)
= I2(
  Func(
    returns: pointer_of(Func(returns: void, args: (int))),
    args: (int sig, void (*func)(int))
  )
)
= I2(E2_1(
    pointer_of(Func(returns: void, args: (int)))
))
= I2(E2_1(P2_1(
    Func(returns: void, args: (int))
)))
= I2(E2_1(P2_1(E1_1(
  void
))))
= I2(E2_1(P2_1(E1_1(T))))

となります。つまり、適用順は

T
-> Pの小さい方から大きい方
-> Eの大きい方から小さい方
-> DがあればD
-> I

という順番になるんですね。

インクリメンタルに実装しよう!

お疲れ様でした。長い説明に付き合ってくださりありがとうございました。(理解しづらいところがあればぜひコメントをください。)

では、簡単なケースからインクリメンタルに実装してみましょう!

int a;char c;のようなTI型を処理できるようにする

Tにあたるものとして、BaseTypeという構造体をつくります。 とりあえず、type_specifierひとつだけがBaseTypeだと考えましょう。(int, char, voidとかが表現できるね!)

struct BaseType {
  struct Token *type_specifier;
};

次に、D: declaratorにあたるものとして、Declarator構造体をつくりましょう。 最初は簡単な例としてint a;が表現できればよいので、identifierだけ入れることにしましょう。

struct Declarator {
  struct Token *identifier;
};

これらの組をDeclarationPairとしましょう。

struct DeclarationPair {
  struct BaseType *base_type;
  struct Declarator *decltor;
};

これで、BaseTypeとDeclaratorの組TIの形式で表現できる宣言をDeclarationPairで表現できるようになりました。 パーサは再帰下降法で書くだけなので省略します。

DeclarationPairから作成される、型情報の構造体について考えます。

型情報は統一的にTypeという構造体で表すことにして、

struct Type {
  enum {
      kBaseType,
      kIdentifierAttr,
  } subtype;
  struct BaseType *base_type;
  struct Token *identifier;
  struct Type *next;
}

というふうにしておきます。nextは、pointer_of(t)ident is_a(t)のtにあたるものです。

そしてDeclarationPairからTypeを作るような関数をつくります。

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
  return type;
}

これだけで、ひとまずint a;とかchar c;とかはいけるようになります。やったね!

int **pp;のようなTP*I型を処理できるようにする

つぎは、ポインタに対応しましょう。最初は*constなどのポインタ属性に対応しないと割り切ってしまえば*の個数を数えればいいので、Declaratorに*の個数を格納するメンバを追加します。

struct Declarator {
  int pointer_count;    // new!
  struct Token *identifier;
};

そして、Typeにも型だけ追加しておきます。

struct Type {
  enum {
      kBaseType,
      kIdentifierAttr,
      kPointerType,    // new!
  } subtype;
  struct BaseType *base_type;
  struct Token *identifier;
  struct Type *next;
}

そして、CreateTypeFromDeclarationPair()にコードを追加します。

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  for(int i = 0; i < decl_pair->decltor->pointer_count){  // this loop
    type = AllocAndInitPointerType(type);
  }
  type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
  return type;
}

これで、int **pp;とかが処理できますね!

int *arr[2][3];のようなTP*IE*(Eは配列)を処理できるようにする

ポインタができたら、次は配列ですね。配列は、要素数に整数のみをとると仮定しましょう。

とりあえず、direct-declaratorに対応する構造体をつくります。

struct DirectDeclarator {
  enum {
    kArrayDeclarator,
  } type;
  int size;
}

そして、DirectDeclaratorの列E*を格納するメンバをDeclaratorに追加します。

struct Declarator {
  int pointer_count;
  struct Token *identifier;
  struct List *direct_declarators;  // List of DirectDeclarator
};

ここでは、Listの実装の詳細については述べません。

そして、CreateTypeFromDeclarationPair()にコードを追加します。

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  for(int i = 0; i < decl_pair->decltor->pointer_count){
    type = AllocAndInitPointerType(type);
  }
  for(int i = GetSizeOfList(decl_pair->decltor->direct_declarators); i >= 0; i--) {  // this loop
    struct DirectDeclarator **dd = 
      GetNodeAt(decl_pair->decltor->direct_declarators, i);
    if(dd->type == kArrayDeclarator)
      type = AllocAndInitArrayType(dd->size, type);
  }
  type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
  return type;
}

これで、int *arr[2][3];とかが処理できますね!

int f(int c);のようなTP*IE*(Eは関数)を処理できるようにする

同様にして、関数も処理できるようにしましょう。 とりあえず、direct-declaratorにメンバを追加します。

struct DirectDeclarator {
  enum {
    kArrayDeclarator,
    kFuncDeclarator,  // new!
  } type;
  int size;
  struct List *args;  // new!
}

一応argsもつけましたが、最初はargsは真面目にチェックしなくてよいと思います。また、argsのパースや型情報への変換もここでは扱いません。そんなに難しくないのですぐにできると思います。

そして、CreateTypeFromDeclarationPair()にコードを追加します。かんたんですね!

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  for(int i = 0; i < decl_pair->decltor->pointer_count){
    type = AllocAndInitPointerType(type);
  }
  for(int i = GetSizeOfList(decl_pair->decltor->direct_declarators); i >= 0; i--) {  // this loop
    struct DirectDeclarator **dd = 
      GetNodeAt(decl_pair->decltor->direct_declarators, i);
    if(dd->type == kArrayDeclarator)
      type = AllocAndInitArrayType(dd->size, type);
    if(dd->type == kFuncDeclarator)
      type = AllocAndInitFuncType(type, dd->args);  // here!
  }
  type = AllocAndInitIdentifierAttr(decl_pair->decltor->identifier, type);
  return type;
}

これでint f(int c);int **f();とかも処理できるんですよ。すごくないですか!

ちなみに、この変換コードでは、先ほど説明したような、関数の戻り値に関数/配列を指定できない、配列の要素型に関数を指定できないというチェックを行なっていません。 チェックを追加するのはとてもかんたんなので、読者への課題とします。(最初はやらなくていいと思いますよ!)

ネストしたdeclaratorに対応する

さて、みんな大好きsignalの定義をパースできるまであともう少しです!ネストしたdeclaratorに対応できれば、表現力はぐっと向上します。

まず、ネストしたdeclaratorを表現できるようにdeclaratorを修正します。

struct Declarator {
  int pointer_count;
  struct Token *identifier;
  struct Declarator *next;  // here!
  struct List *direct_declarators;
};

例によりパーサは書けると思うので省略します。

そして、CreateTypeFromDeclarationPair()から関数を切り出して、ネストにうまく対応できるように準備します。(以下のコードは、一つ前のコードと等価な動作をします)

struct Type *CreateTypeFromDeclarator(struct Declarator *decltor, struct Type *type) {
  for(int i = 0; i < decltor->pointer_count){
    type = AllocAndInitPointerType(type);
  }
  for(int i = GetSizeOfList(decltor->direct_declarators); i >= 0; i--) {
    struct DirectDeclarator **dd = 
      GetNodeAt(decltor->direct_declarators, i);
    if(dd->type == kArrayDeclarator)
      type = AllocAndInitArrayType(dd->size, type);
    if(dd->type == kFuncDeclarator)
      type = AllocAndInitFuncType(type, dd->args);
  }
  return AllocAndInitIdentifierAttr(decltor->identifier, type);
}

struct Type *CreateTypeFromDeclarationPair(struct DeclarationPair *decl_pair) {
  struct Type *type = AllocAndInitBaseType(decl_pair->base_type);
  return CreateTypeFromDeclarator(decl_pair->decltor, type);
}

そして、もしもネストしていたら、再帰的にCreateTypeFromDeclarator()を呼び出すようにします。

struct Type *CreateTypeFromDeclarator(struct Declarator *decltor, struct Type *type) {
  for(int i = 0; i < decltor->pointer_count){
    type = AllocAndInitPointerType(type);
  }
  for(int i = GetSizeOfList(decltor->direct_declarators); i >= 0; i--) {
    struct DirectDeclarator **dd = 
      GetNodeAt(decltor->direct_declarators, i);
    if(dd->type == kArrayDeclarator)
      type = AllocAndInitArrayType(dd->size, type);
    if(dd->type == kFuncDeclarator)
      type = AllocAndInitFuncType(type, dd->args);
  }
  if(decltor->next)
    return CreateTypeFromDeclarator(decltor->next, type);  // here!
  return AllocAndInitIdentifierAttr(decltor->identifier, type);
}

なんとこれだけです!これだけで、あの奇怪なvoid (*signal(int sig, void (*func)(int)))(int);があなたのコンパイラでも綺麗に解釈できるようになったのです!

まとめ

本当はここでcompiliumの実際のコードを貼ることになるはずだったのですが、そちらのほうはちょっと間に合いませんでした。申し訳ないです。(27日までには出したいですね。)

実を言うと、上記のコードはブログの編集画面に直接打ち込んだため、バグやtypo、ロジックのミスなどがあるかもしれません。発見しましたら、どうかそっと教えていただけると助かります。(報告、意見等は大歓迎です!@hikaliumまでお寄せください。)

駆け足になりましたが、これでC言語のdeclarationの半分以上を理解していただけたならば私としても嬉しいですし、コンパイラを書いていてdeclarationの処理で詰まっていた皆様の一助になればいいなと思っております。

ということで、大変遅く&長くなりましたが、これにてひとまずおしまいです。

上の続きとしては、

  • const pointer
  • struct/union
  • enum
  • typedef

などが待ち受けていますが、ここまでできれば比較的簡単にできると思います。(もちろん、落とし穴はたくさんありますが…。)

長々と読んでいただき、ありがとうございました。

来年もよいCコンパイラ自作ライフを楽しみましょう!

参考文献

SECCON CTF 2018 ( DOMESTIC )にチームBluemermaidで出て2位だった話

2018-12-23に開催されたSECCON CTF 2018の国内決勝に、チームBluemermaidとして h_nosonうさぎsrupとともに出場して、準優勝したようです。

ということで、一応Write-up的なものを書いておこうと思います。

概況

問題としては大きく三つ: 松島・天橋立・宮島に分かれており、最初は天橋立と宮島だけが開放されていて、松島は試合の途中で開放されました。 私は毎年のように、謎アーキテクチャバイナリ担当として雇われていた(予選ではそれだけしか解けなかった)のですが、残念ながらそういった問題は出なかったので、アセンブリコードゴルフができそうな3つ目の宮島を主にやっていました。

松島

松島は、ビデオポーカーの乱数に脆弱性があるので、それをついてうまくいい手を出すとフラグがもらえたりディフェンスキーワードをサブミットできるよ(プログラムのバイナリは与えるよ)というものでした。

これはうさぎさんとsrupさんがさくっと解いてくれたので詳細は各人に任せますが、どうも乱数に脆弱性がありすぎ?だったようで、バイナリを解析せずとも4カードやフルハウスを出せてしまったらしく、しかもディフェンスキーワードのサブミットフォームの送信先URLが常に同一だったため、一回解いてしまえばポーカーには一切触れず自動化できてしまうという代物だったようです。

天橋立

天橋立は、ディフェンスポイントのみがある問題でした。 XSS HELLというサイト名で、XSS脆弱性があるような任意のhtmlをアップロードできる仕組みになっていました。 そのhtmlはだれでもダウンロードでき、それに存在するXSSを他のチームは解くことができて、解かれてしまうとディフェンスポイントは入らないよーというルールでした。 具体的には、アップロード時の名前をディフェンスキーワードの文字列にすることで、その問題が解かれずに残っていると、ディフェンスポイントが入るという仕組みでした。

というわけで、人々は最初、そこそこ難しいペイロードを突っ込んだ時だけXSSが発動するようなhtmlをあげておいて、ディフェンスキーワードが変わったら自分たちで解いて新しくアップロードしなおせばいいのだと考えていました。 ところがなんと、あるチームがアップロードしたhtmlは、そのチームが自ら解くことはできず、一方でタイトルはアップロード履歴画面から任意に変更できるという仕組みになっていたのです。 …そうすると、何が起こったか。

どのチームも、そのチームだけが知っている特定のキーワードのハッシュ値をhtmlに書いておき、それが一致した時のみXSSを突かれたような挙動をする、ただのパスワード認証のようなhtmlを上げ始めたのです。 結局、「他のチームの問題を解く」という行為はほぼ不可能になり(SHA-256をじっと睨めば解ける方ならちがうかもしれませんが)、もはやディフェンスキーワードの更新を自動化するだけの作業だけが残ったのでした。

このゲーム性のなさは、作問者のYu Yagihashi氏も認識しており、コンセプトが崩壊したと悲しみの声を表明しておられました。

同時に、どのようにすればXSS HELLがコンセプト崩壊しなかったのか、意見を募集しておられるようですので、なにか思いついた方はつぶやいてみるのもよいのではないでしょうか。

宮島

というわけで、松島も天橋立も終わってしまった今となっては、もう宮島しか我々には残されていないわけです。

宮島はどのような問題だったかというと

  • ある与えられた要件を満たすような動作をするx86アセンブリのバイナリを作成して投げる
  • テストに合格すれば、フラグがもらえるので、アタックポイントがもらえる
  • バイナリと同時にディフェンスキーワードも送信する
    • 最も短いバイナリを最速でsubmitすることでディフェンスキーワードを書き込むことができる
    • 同じ長さのバイナリで2番目以降にsubmitした人はディフェンスキーワードを書き込めない
    • より短いバイナリを他のチームに投げられない限り、書き込まれたディフェンスキーワードのチームにディフェンスポイントが一定時間ごとに入る

というものでした。

画面としては以下のような感じ。

f:id:hikalium:20181224000347p:plain

これは最終問題なので、まあまあな感じですが、最初は

int型の引数a, bが渡されるので、その和を返す関数を実装してください

という感じのかんたんさで、かんたんであるが故にバイナリの短さの限界が見えてしまい、もはや問題予測&早解き大会となっていました。

ちなみに、上記のXorはおそらく下記のものが最短かと思われます(他のチームに先を越されてしまいましたが。)

0000000000000000 <func>:
   0:   87 ce                   xchg   %ecx,%esi

0000000000000002 <Lcmp>:
   2:   30 54 0f ff             xor    %dl,-0x1(%rdi,%rcx,1)
   6:   e2 fa                   loop   2 <Lcmp>
   8:   c3                      retq   

LOOP命令を使うのがミソです。SDMを読んでた甲斐がありましたね!

バイナリ早書き支援Makefile

最初からバイナリを書いてもいいんですが、間違えやすいので、こんなかんじで最初はcで書き、あとでasmで書いてみて、test.cとリンクしてテストするという感じで作業しました。

c:
    gcc -Os -c -o c.o c.c
    cp c.o func.o
    objdump -d c.o
    objdump -d c.o | cut -f 3
    objcopy -O binary -j .text c.o co
    od -An -t x1 co

asm:
    as -o asm.o asm.S
    cp asm.o func.o
    objdump -d asm.o
    objdump -d asm.o | cut -f 3
    objcopy -O binary -j .text asm.o co
    od -An -t x1 co

test:
    gcc -o test.bin func.o test.c
    ./test.bin

まあ、私より周りのプロのほうが早くてあまり役に立てませんでしたが…。

CLIからバイナリ送信

バイナリ送信がwebフォーム経由だったのですが、ディフェンスキーワードをいれたり、コードをコピペしてEnterを押すのは面倒だったので、CLIでできるように準備だけはしました。暇だったので。(だって最速AC取られたら30分後まで勝ち目はないんだもの…)。

const puppeteer = require('puppeteer');

(async () => {
  var key = process.argv[2];
  var code = process.argv[3];
  const browser = await puppeteer.launch();
  const page = await browser.newPage();
  page.on('dialog', async dialog => {
    console.log(dialog.message());
    await dialog.dismiss();
  });
  await page.goto('http://miyajima.pwn.ja.seccon/');
  await page.type('input', key);
  await page.type('textarea', code);
  const elementHandle = await page.$('button');
  await elementHandle.press('Enter');
  const element = await page.$(".form__attacking-flag");
  if(element){
    const flag = await page.evaluate(element => element.value, element);
    console.log("FLAG: " + flag);
  }
  await page.screenshot({path: 'example.png'});
  await browser.close();
})();

ぐーぐるくろーむのpuppeteerっていうのを使うと、けっこうお気軽にWebブラウザ操作の自動化ができておいしいです。べんり。

github.com

最初はLighthouseを使おうとしたのですが、どうもうまくいかなかったのでこちらを使いました。 ただ、結構インターネットの海にある使ってみたよ記事は古いAPIを使っていたりしてうまくいかないことが多かったです。 困った時はちゃんとAPIドキュメントを見ると楽かもしれません。

感想

少し問題数が少なかったような気がする。特に、アタックポイントにほとんど差がついていなかったと思うので、もう少し問題数を増やすとか、解ききれない難しいものを出してもらえるとよかったかもしれない。 また、問題に穴が多かったというか、ゲーム性が少なく、早押しクイズのような感じになってしまっていた部分が例年より多かったように感じた。

とはいえ、解くこと自体は面白かったし、SECCONはSECCONなのでよかったと思います。 来年ももっと進化したSECCONを楽しみにしています!(精進します…。)

共に戦った参加者のみなさん、運営のみなさま、関係者の皆様、ありがとうございましたー!

自作OSでできる!NVDIMMのつかいかた

これは、自作OS Advent Calendar 2018 の7番目の素数日の記事です。

はじめに

みなさん、NVDIMMって知っていますか?知っている人はぜひ仲良くなりましょうー。

NVDIMMとは、Non-Volatile DIMMの略で、要するにDIMMスロットに刺さる不揮発性の記憶モジュールのことです。 通常のDRAM DIMMは、電源を切るとデータが消えてしまう揮発性の記憶素子なのですが、なんとNVDIMMは電源を切ってもデータが消えません。すごいね!

(NVDIMMの実現方法にはいくつか種類があって…という、NVDIMM自体の細かい話はここではしません。)

さて、自作OSを書いている皆様はよくわかると思うのですが、自作OSで何らかのデータを保存するのはとても大変です。メモリにあるデータは電源を切ると消えてしまいますから、HDDやSSDやSDカードに書き出さないといけません。そうすると、まずはそれらのデバイスのドライバを書かなくてはいけませんし、しかもこれらのデバイスはブロック単位でしか書き込みができませんから、何らかのファイルシステムのような仕組みも用意しなくてはいけません。…大変ですね。

そういうわけで、多くのみなさんはデータを保存する機構を実装せず、電源を切ったらデータは全部消えてしまってもいいという割り切りをすることになります。これはかなしい。

ところが!NVDIMMはCPUからみたとき、メモリとして認識されるので、ドライバなしにCPUから直接読み書きすることができます。つまり、DIMMにマッピングされたアドレスに書いたデータは、起動後もそのまま読み出せるのです!

ということで、この記事では、自作OSでNVDIMMを使うにはどうすればいいかを解説していきます。

検証環境

残念ながら、NVDIMMの実機を個人で買うのはすこしたいへんです。なので、代わりにQEMUのNVDIMMエミュレーションを利用することにします。

利用したバージョンはコミット7c69b7c849をソースビルドしたものです。

QEMU emulator version 3.0.50 (v3.0.0-1143-g7c69b7c849)

コマンドラインオプション

公式ドキュメントは以下にあります。

qemu/docs/nvdimm.txt

これを参考に、QEMUの起動コマンドラインオプションは以下のようにしました。

-bios $(OVMF) \
-machine q35,nvdimm -cpu qemu64 -smp 4 \
-monitor stdio \
-m 8G,slots=2,maxmem=10G \
-drive format=raw,file=fat:rw:mnt -net none \
-object memory-backend-file,id=mem1,share=on,mem-path=pmem.img,size=2G \
-device nvdimm,id=nvdimm1,memdev=mem1

これらのオプションのうち、NVDIMMをエミュレーションする上で重要なポイントは以下の通りです。

  • -machinenvdimm を追加する。
  • -m のサイズはDRAMのサイズを設定する。
    • slots は、(メインのDRAMスロット数+NVDIMMスロット数)に設定する。
      • (今回の場合 1 + 1 = 2)
    • maxmem は、(メインのDRAM容量 + NVDIMMの容量)に設定する。
      • (今回の場合 8G + 2G = 10G)
  • -object-device の組で、ひとつのファイルバックエンドNVDIMMデバイスを作成できる。
    • -objectid と、-devicememdevの値を一致させる。
    • -mem-path にはqemu-imgで作成したデータイメージのパスを指定する。
      • ここでは、qemu-img create pmem.img 2G と実行して作成されたイメージを利用した。
    • -sizeには、上記データイメージ作成時に渡したパラメータと同じサイズを指定する。

また、今回はUEFIを利用するため、-biosにはOVMFのコミットb9cee524e6からビルドしたbiosイメージを指定しています。

Linux以外でのエミュレーションができなかった問題

ちなみに、Linux以外でNVDIMMエミュレーション(正確にはhostmem-file)が正しく動作しない問題があったので、私がパッチを送っておきました。すでにmasterにはマージされているので、最新のQEMUコンパイルしてご利用ください。

https://github.com/qemu/qemu/commit/d5dbde4645fe56a1bcd678f85fa26c5548bcf552

実装の指針

さて、これでエミュレーションの準備は整いました。つぎは実装の計画を立てましょう。

いかにしてNVDIMMのマップされている物理アドレスを取得するか

NVDIMMはメモリバスの配下に接続されているので、物理アドレス空間のどこかにNon-volatileなメモリ空間が生い茂っているはずです。 しかし、私たちはそれがどこにあるのかまだ知りません。知るためにはどうすればよいか…ACPIのNFITを読みます。

ACPI NFIT

ACPI Revision 6.0 より、NFITというPlatform Capabilities Structureが追加されました。 NFITとは、NVDIMM Firmware Interface Table の略です。このテーブルを参照することで、実行中のプラットフォーム上にあるNVDIMMの情報を取得できます。

packed_struct ACPI_NFIT {
  char signature[4];
  uint32_t length;
  uint8_t revision;
  uint8_t checksum;
  uint8_t oem_id[6];
  uint64_t oem_table_id;
  uint32_t oem_revision;
  uint32_t creator_id;
  uint32_t creator_revision;
  uint32_t reserved;
  uint16_t entry[1];
};

今回はそのNFITに含まれる情報の中でも、SPA(System Physical Address) Range Structures に知りたい情報があります。

packed_struct ACPI_NFIT_SYSTEM_PHYSICAL_ADDRESS_RANGE_STRUCTURE {
  uint16_t type;
  uint16_t length;
  uint16_t spa_range_structure_index;
  uint16_t flags;
  uint32_t reserved;
  uint32_t proximity_domain;
  uint64_t address_range_type_guid[2];
  uint64_t system_physical_address_range_base;
  uint64_t system_physical_address_range_length;
  uint64_t address_range_memory_mapping_attribute;
};

話はわかった。ところで、そのNFITっていうのはどうやったら読めるの?

NFITへのポインタは、ACPIのXSDT(eXtended System Descriptor Table)に格納されています。

packed_struct ACPI_XSDT {
  char signature[4];
  uint32_t length;
  uint8_t revision;
  uint8_t checksum;
  uint8_t oem_id[6];
  uint64_t oem_table_id;
  uint32_t oem_revision;
  uint32_t creator_id;
  uint32_t creator_revision;
  void* entry[1];
};

XSDTへのポインタはRSDT(Root System Description Table)に格納されています。

packed_struct ACPI_RSDT {
  char signature[8];
  uint8_t checksum;
  uint8_t oem_id[6];
  uint8_t revision;
  uint32_t rsdt_address;
  uint32_t length;
  ACPI_XSDT* xsdt;           // <<< HERE!
  uint8_t extended_checksum;
  uint8_t reserved;
};

で、このRSDTへのポインタは…EFI Configuration Table にあります。(EFI_ACPI_TABLE_GUIDから引ける。)

というわけで、実際の順番としては

EFIConfigurationTable 
-> ACPI_RSDT 
-> ACPI_XSDT 
-> ACPI_NFIT 
-> SPARangeStructure

と辿っていけば、NVDIMMのマップされているアドレス system_physical_address_range_base がわかるわけです。

実装

さあ、これでもうあとは実装するだけですね!

ということで、実装してみた例がこちらです。

github.com

軽く実装について説明します。

src/liumos.cc のMainForBootProcessor()が、起動後に最初に実行される関数です。

この関数内の、

  ACPI_RSDT* rsdt = static_cast<ACPI_RSDT*>(
      EFIGetConfigurationTableByUUID(&EFI_ACPITableGUID));
  ACPI_XSDT* xsdt = rsdt->xsdt;

という部分で、EFIConfigurationTableからRSDTを取得し、そこからXSDTを取得しています。

そして、以下のようにしてXSDTからNFITを見つけ出し、

  ACPI_NFIT* nfit = nullptr;
  ...
  for (int i = 0; i < num_of_xsdt_entries; i++) {
    const char* signature = static_cast<const char*>(xsdt->entry[i]);
    if (IsEqualStringWithSize(signature, "NFIT", 4))
      nfit = static_cast<ACPI_NFIT*>(xsdt->entry[i]);
   ...
  }

NFITが存在していれば、適当にSPARange structureを見つけ出して、適宜書き込んだり読み込んだりしてみてその結果を表示しています。

 if (nfit) {
    PutString("NFIT found\n");
    PutStringAndHex("NFIT Size", nfit->length);
    PutStringAndHex("First NFIT Structure Type", nfit->entry[0]);
    PutStringAndHex("First NFIT Structure Size", nfit->entry[1]);
    if (static_cast<ACPI_NFITStructureType>(nfit->entry[0]) ==
        ACPI_NFITStructureType::kSystemPhysicalAddressRangeStructure) {
      ACPI_NFIT_SPARange* spa_range = (ACPI_NFIT_SPARange*)&nfit->entry[0];
      PutStringAndHex("SPARange Base",
                      spa_range->system_physical_address_range_base);
      PutStringAndHex("SPARange Length",
                      spa_range->system_physical_address_range_length);
      PutStringAndHex("SPARange Attribute",
                      spa_range->address_range_memory_mapping_attribute);
      PutStringAndHex("SPARange TypeGUID[0]",
                      spa_range->address_range_type_guid[0]);
      PutStringAndHex("SPARange TypeGUID[1]",
                      spa_range->address_range_type_guid[1]);

      uint64_t* p = (uint64_t*)spa_range->system_physical_address_range_base;
      PutStringAndHex("\nPointer in PMEM Region: ", p);
      PutStringAndHex("PMEM Previous value: ", *p);
      (*p)++;
      PutStringAndHex("PMEM value after write: ", *p);

      uint64_t* q = reinterpret_cast<uint64_t*>(page_allocator.AllocPages(1));
      PutStringAndHex("\nPointer in DRAM Region: ", q);
      PutStringAndHex("DRAM Previous value: ", *q);
      (*q)++;
      PutStringAndHex("DRAM value after write: ", *q);
    }
  }

(本当はきちんと見つけ出さなければいけないのですが、QEMUの場合NFIT中の0番目のエントリに運良くSPARangeStructureがあったので手抜きしています。ごめんなさい!)

ね!テーブルをたどるだけの簡単なお仕事でしょ!

実行結果

リポジトリのこのハッシュをクローンしてきてmake runすると、最初にpmem.imgが作成されてからQEMUが起動します。

$ make run
make -C src
make[1]: Nothing to be done for `default'.
qemu-img create pmem.img 2G
Formatting 'pmem.img', fmt=raw size=2147483648
mkdir -p mnt/EFI/BOOT
cp src/BOOTX64.EFI mnt/EFI/BOOT/
qemu-system-x86_64 -bios ovmf/bios64.bin -machine q35,nvdimm -cpu qemu64 -smp 4 -monitor stdio -m 8G,slots=2,maxmem=10G -drive format=raw,file=fat:rw:mnt -net none -object memory-backend-file,id=mem1,share=on,mem-path=pmem.img,size=2G -device nvdimm,id=nvdimm1,memdev=mem1
QEMU 3.0.50 monitor - type 'help' for more information
(qemu)

画面としてはこのような感じになります。

f:id:hikalium:20181217181025p:plain
最初の起動

今回は比較のため、PMEM領域に含まれるアドレスと、DRAM領域に含まれるアドレスにある8バイト整数を起動毎にそれぞれインクリメントしていくように実装しました。

ひとまず最初は、どちらも運良く0で初期化されていたので、それぞれインクリメントしたら1になっていますね。

では、qemuのコンソールにqと打ち込んで終了させ、もう一度make runしてみましょう。

すると…!

f:id:hikalium:20181217231241p:plain
2回目の起動

DRAMとPMEM、どちらも最初の起動時と同じポインタを読み書きしているのですが、DRAMでは最初の起動時にインクリメントした1は忘れ去られてまた0からやりなおしになっている一方、PMEMでは前回のインクリメント結果である1が再起動後も残っていて、今度は2が書き込まれました!

念の為もう一回再起動してみると…

f:id:hikalium:20181217231640p:plain
3回目の起動

やっぱりDRAMはデータが消えてしまっていますが、PMEMは残っていますね!すごい!

まとめ

というわけで、NVDIMMを使えば、自作OSでも簡単にデータを保存して再起動後にも残しておけるということがわかりました! とはいえ今回は簡単な説明しかしておらず、実装は手抜きですし、キャッシュをフラッシュしなければデータが消える可能性があるなど、細かい点で注意しなければならないことが山積みです。

これらを考慮しつつ、liumOSはNVDIMMを有効活用した新しいOSを目指して開発をしてゆきますので、今後にご期待ください!

では皆様、よいOS自作ライフを!

参考文献

編集履歴

  • ACPI SpecおよびUEFI Specについて、最新バージョンを参照するよう参考文献を変更しました。
  • ACPI SpecにNFITが追加されたのは6.2Aではなく6.0からとの指摘を受けましたので、該当箇所を修正しました。

compilium v2 (in progress)の工夫点

この記事は、言語実装アドベントカレンダーの7日目にあたります。

ちなみに、これを書いている現在は2018年12月7日の12:00です。果たして今日中に記事を公開することはできるのでしょうか…。

compilium v2とは

github.com

compiliumは、hikaliumが開発しているC11準拠(予定)のCコンパイラです。C言語で書かれています。

compilium v2では、v1での反省点およびセキュリティ・キャンプ全国大会2018のCコンパイラ自作ゼミでの知見をもとに、よりわかりやすく単純でインクリメンタルに開発できることを目標に開発しています。

この記事では、これらの得られた知見とともに、それらが実際にどのようにcompilium v2に活かされているかを紹介します。

最初からレジスタマシンとしてアセンブリを出力する

当初、Cコンパイラゼミでは、スタックマシンとしてアセンブリを出力するよう受講者のみなさんにお願いしていました。

これは、レジスタ割り当てを最初から考慮するのは大変であり、スタックマシンならばシンプルに実装できるという予想に基づいたものでした。

実際、スタックマシンを採用したことで、式のコード生成については、かなりスムーズに習得してもらうことができました。

一方で、スタックマシンの弱点としては、アセンブリレベルでのデバッグが非常に困難になることが挙げられます。 これは、出力の多くが本質的な計算ではなくpush/popに占められることと、各計算の間で値がどのように伝播するかわかりづらいことが原因でした。

そこで、レジスタマシンの可能性を再考してみたところ、式に閉じたレジスタマシンであれば、複雑な式を与えない限り、単純なコードでもうまく生成でき、出力も自然に近いアセンブリになることがわかりました。

簡単なレジスタマシンの実装

式(Expression)に閉じたレジスタマシン、つまり、異なる式の間で値を引き継いだりしないようなものは容易に実装することができます。 具体的には、値であれば新しくレジスタを確保し、演算子であればその各オペランドに対してレジスタ割り当てを実行したのち、戻り値を戻すためのレジスタ一つをのぞいてすべて解放する、という手順を行えばよいです。

戻り値を戻すためのレジスタとして、演算子の左側のオペランドレジスタを利用することにした場合、2 + 3 * 5は、下の図のように割り当てることができます(R, G, Bはそれぞれレジスタ名です)。

f:id:hikalium:20181207192720g:plain
レジスタ割り当てのようす

実際には、この式は2つのレジスタで計算可能な式(3*5を先に計算すればよい)なのですが、そんなことは気にしたら負けです。 とにかく単純に実装することがcompiliumの目的ですからね!

利用可能なレジスタ

SystemV ABI において、保存せずに破壊しても問題ない汎用レジスタは、以下のものになります。

rax, rcx, rdx, rsi, rdi, r8, r9, r10, r11

このうち、

  • raxは戻り値の格納に使われる
  • rdxはmul, div系で変更される可能性がある(MUL r/m64: RDX:RAX ← RAX ∗ r/m64))
  • rcxはシフト系演算でオペランドとして利用される(シフト系演算のシフト量は、レジスタで指定する場合CLしか使えない)

ことから、単純のため利用しないことにすると、気軽に自由に使えるレジスタ

rsi, rdi, r8, r9, r10, r11

の6つになります。

なぜこれで大体うまくいくのか

f:id:hikalium:20181207200845p:plain
レジスタ割り当ての例

上の図を参照してもらえればわかるように、ASTが右に伸びるほど、必要なレジスタの個数が増えていることがわかります。

ASTが右に伸びるということは、右側のほうを先に計算する必要がある、つまり、右側の演算子の優先順位が高いか、同じ優先順位でも右結合の場合か、もしくはかっこで包まれている場合に限られます。

C言語二項演算子で右結合性のものはassignment-operatorのみであり、これを連続して使うような場合はあまり多くありません。

したがって、優先順位の異なる演算子や括弧をひとつの式の中で多用しないかぎり、このアルゴリズムでも大体うまくいくわけです。

うまくいかなかったらどうするかって?ソースを書き換えちゃいましょう!変数を使えばどんな式もコンパイルできる形に確実に書き直せますよ!

エラーメッセージの改善

compilium v1では、エラー時にその行番号を報告することしかできませんでした。 しかし、式のテストは1行にソースが押し込められてしまうことから、行番号は大して役にたちませんでした。 そこで、compilium v2では、エラー発生時に該当トークンの前後を表示できるように実装されました。

{int *a; return sizeof(a);}
                ^^^^^^
Error: Generate: Not implemented unary prefix op

assignment-expression のパーストリック

assignment-expression:
    conditional-expression
    unary-expression assignment-operator assignment-expression

assignment-expressionが右再帰であることは先ほど触れましたが、右再帰とはいっても単純な右再帰ではありません。 再帰の終端点では conditional-expression が許されるのに対し、再帰途中の左辺には unary-expressionしか許されません。 パーサを書いていて、ここをどう処理するか悩んでいるみなさんも多いのではないでしょうか。(もしかしてみんな悩まない!?)

compilium v2の実装にあたり、この問題の解決策をいくつか考えてみました。

方法1: unary-expressionを先読みする

conditional-expressionは、cast-expressionの場合を除いて、先頭にunary-expressionがくる。

そして、cast-expressionの場合に左側に来る要素はunary-expressionとして認識される可能性がない( type-name ) ので、unary-expressionを先読みして直後にassignment-operatorがくるか調べ、来なければそのunary-expressionを渡しつつconditional-expressionをパースすれば良い。

  • 利点:
    • 文法に沿ったパース結果を得られる
  • 欠点:
    • パーサの一部のみ引数が増える

方法2: 試してみてだめだったら巻き戻す

compilium v1で採用していた方法

  • 利点
    • 文法に沿ったパース結果を得られる
  • 欠点
    • 巻き戻すのはださい(このためだけにTokenStreamの位置を保存しなければいけない)
    • 効率が悪い(2回同じことをすることになる可能性がある)

方法3: conditional-expressionとして読んでから、読んだトークンのクラスを判定する

  • 利点:
    • 文法に沿ったパース結果を得られる
    • パーサの引数の数を統一できる
  • 欠点:
    • ASTのタイプを注意深く設計しなければならない
    • unary-expression以下のASTタイプを新たに実装した際に判定条件に追加しなければならない
      • unary-expression, postfix-expression, primary-expression がunary-expressionに含まれる。

方法4: 単純な右再起になるよう構文を変更してしまう

assignment-expression:
    conditional-expression
    conditional-expression assignment-operator assignment-expression
    ^^^^^^^^^^^^^^^^^^^^^^

9ccで採用されている方法 compilium v2でもこれを採用することにした。

  • 利点:
    • パーサの記述が楽
  • 欠点:
    • 構文にあてはまらない入力をパースできてしまう
      • a+1 = 2 のような構文は本来パースできない
    • ただし意味解析で除去できる(左辺がlvalueかどうかチェックすればよい)
    • 副作用として、条件演算子を左辺値として用いることができるようになる。
      • これはgcc拡張である
      • しかもこの構文はC++ではvalid(つまりこっちのほうが自然)

というわけで、皆さんも方法4を採用するといいと思います!(楽なので)

主要な構造体をTokenとASTNodeのみに集約

compilium v1 では、型がついていないと不安だし、メモリを効率よく使いたいという思いから、ASTの各タイプごとに構造体を用意していました。

しかし、これは機能追加ごとのコード量が増大する要因となり、またほぼ同一内容のコードがソース中に増える原因となりました。

compilium v2 では、思い切ってASTおよび型情報を単一の構造体ASTNodeに押し込めることにしました。

これは、メモリ効率の低下を招きますが、まあ昨今みんなRAMは32GB以上積んでいると思われますので問題ないでしょう…。

(やっぱり無理して書くよりも気楽に書いた方がいいですよ。)

おわりに

本来はもっと真面目にもっと詳細に語りたかったのですが、ちょっと疲れてしまってゆるふわになってしまいました。ごめんなさい…。

特に型の話についてはもう少し語りたいので、12/23のC言語アドベントカレンダーでまた書きたいと思います。

私もコンパイラ初心者なので、何か指摘や質問等あればぜひTwitterのほうまでお願いします!

年内にはv2がセルフホストできるようにがんばりますので、どうか生暖かい目で見守っていてください…。

今年度セキュリティキャンプ2018のCコンパイラゼミに参加してくださったみなさん、そして一緒に講師を担当していただいたRuiさんには、実装方法など様々な面でよい刺激をいただきました。ありがとうございます。

ということで、

みなさんもCコンパイラ書きましょうね?

楽しいぞ!

参考文献