技術書典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ハンガーをお借りして、ブースがさらにパワーアップしました！）

ちなみに、売り子はセキュキャン同期で、かつCERNでLLVMを書いていたことで知られている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.h や build.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、が宣言されますね。

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

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

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

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

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

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は、よくみるintやcharとか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を再帰的に含むことができます。 （これはつまり、declaratorはdeclaratorを再帰的に含むことができるということです。） したがって、単に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をエミュレーションする上で重要なポイントは以下の通りです。

  • -machine に nvdimm を追加する。
  • -m のサイズはDRAMのサイズを設定する。
    • slots は、(メインのDRAMスロット数+NVDIMMスロット数)に設定する。
      • （今回の場合 1 + 1 = 2）
    • maxmem は、（メインのDRAM容量 + NVDIMMの容量）に設定する。
      • （今回の場合 8G + 2G = 10G）
  • -object と -device の組で、ひとつのファイルバックエンドNVDIMMデバイスを作成できる。
    • -object のid と、-deviceのmemdevの値を一致させる。
    • -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コンパイラ書きましょうね？

楽しいぞ！

参考文献

SECCON 2018 Online CTF Writeup

https://score-quals.seccon.jp/team/115

チーム Bluemermaid として参加しました。総合17位、国内6位だったようです。 私がsubmitしたフラグは1つでした。（2つ解けたのだけど、1つは少し前に他の方が解いていた…。はやい。）

解けた問題

Special Device File

毎度おなじみ謎アーキでした。

$ file runme_8a10b7425cea81a043db0fd352c82a370a2d3373 
runme_8a10b7425cea81a043db0fd352c82a370a2d3373: ELF 64-bit LSB executable, ARM aarch64, version 1 (SYSV), statically linked, not stripped

と言ってもaarch64ですが。

まずは毎度おなじみ環境構築をします。私はUbuntu 18.04でやりました。（事前にやっておけ。） 全部のアーキをビルドしていると試合が終わってしまうので、必要なアーキだけtargets.shに書いておくとよいでしょう。

そんなわけで、とりあえずシミュレータで実行してみると

/usr/local/cross2-gcc494/bin/aarch64-elf-run runme_8a10b7425cea81a043db0fd352c82a370a2d3373

トラップで落ちます。まあきっと未実装なのでしょう。

みんな大好きobjdumpをみてみると、

000000000000140c <__exit>:                           
    140c:       d4200000        .word   0xd4200000   
    1410:       d65f03c0        ret               
                                                      
0000000000001414 <__read>:                           
    1414:       d28000c8        mov     x8, #0x6                        // #6
    1418:       d45e0000        .word   0xd45e0000             
    141c:       d65f03c0        ret                            
                                                    
0000000000001420 <__write>:                           
    1420:       d28000a8        mov     x8, #0x5                        // #5
    1424:       d45e0000        .word   0xd45e0000         
    1428:       d65f03c0        ret                   
                                                     
000000000000142c <__open>:                           
    142c:       d2800028        mov     x8, #0x1                        // #1
    1430:       d45e0000        .word   0xd45e0000    
    1434:       d65f03c0        ret                  
                                                      
0000000000001438 <__close>:                                                  
    1438:       d2800048        mov     x8, #0x2                        // #2    
    143c:       d45e0000        .word   0xd45e0000          
    1440:       d65f03c0        ret                         
    1444:       d503201f        nop                        
    1448:       d503201f        nop

こんな感じでたいへん怪しいです。きっと0xd45e0000という命令を実装しないといけないのでしょう。

ここで、シミュレータをトレース付きで実行してみると、

/usr/local/cross-gcc494/aarch64-elf/bin/run --trace-syscall=on  runme_8a10b7425cea81a043db0fd352c82a370a2d3373

どこでこけているのかわかるようになります。

具体的には、cross-gcc494/toolchain/gdb-7.12.1/sim/aarch64/simulator.cの中のhandle_halt関数内です。（このソースは1万5000行くらいあって、ファイル分けてほしかったなあという気持ちになった。）

static void
handle_halt (sim_cpu *cpu, uint32_t val)
{
  ....
  switch (aarch64_get_reg_u32 (cpu, 0, NO_SP))
    {
    case AngelSVC_Reason_HeapInfo:
    ...
    case AngelSVC_Reason_Rename:
    case AngelSVC_Reason_Elapsed:
    default:
      TRACE_SYSCALL (cpu, " HLT [Unknown angel %x]",
         aarch64_get_reg_u32 (cpu, 0, NO_SP));
      sim_engine_halt (CPU_STATE (cpu), cpu, NULL, aarch64_get_PC (cpu),
           sim_stopped, SIM_SIGTRAP);
    }
  aarch64_set_reg_u64 (cpu, 0, NO_SP, result);
}

この関数の下方、AngelSVC_XXXでswitch-caseのdefaultで落ちていました。ということで、適当にここにハンドラを作ってあげればよさそうです。

syscall番号は、先のobjdump disasより、x8レジスタに代入されていることがわかっているので、引数はレジスタ0から入ると仮定していろいろみてみたところ、なんと/dev/xorshift64といういかにもなデバイスをopenしていることがわかりました。 最初のwriteはシードを設定するのでしょう。そして、後続のreadで乱数を取得すると予想できます。 というわけで、こんな感じで書いてみるとよさそうです。

    default:
      {     
        static uint64_t seed = 0;
        uint64_t syscall_id = aarch64_get_reg_u64 (cpu, 8, SP_OK);
        if(syscall_id == 1) {
          uint64_t pathname = aarch64_get_reg_u64 (cpu, 0, SP_OK);
          uint64_t flags = aarch64_get_reg_u64 (cpu, 1, SP_OK);
          uint64_t mode = aarch64_get_reg_u64 (cpu, 1, SP_OK);
          printf("open \n");
          printf("pathname:%s \n", aarch64_get_mem_ptr (cpu, pathname));
          break;
        } else if(syscall_id == 2) {
          printf("close\n");
          break;
        } else if(syscall_id == 5) {
          printf("write\n");
          uint64_t buf = aarch64_get_reg_u64 (cpu, 1, SP_OK);
          uint64_t size = aarch64_get_reg_u64 (cpu, 2, SP_OK);
          printf("buf:%lX \n", buf); 
          printf("size:%lX \n", size);
          seed = aarch64_get_mem_u64 (cpu, buf); 
          printf("seed:%lX \n", seed);
          break;
        } else if(syscall_id == 6) {
          uint64_t buf = aarch64_get_reg_u64 (cpu, 1, SP_OK);
          uint64_t size = aarch64_get_reg_u64 (cpu, 2, SP_OK);
          printf("read\n");
          printf("seed:%lX \n", seed);
          printf("buf:%lX \n", buf); 
          printf("size:%lX \n", size);
          aarch64_set_mem_u64(cpu, buf, xorshift64_2(&seed));
          printf("seed:%lX \n", seed);
          break;
        }     
        printf("not implemented syscall %lX\n", syscall_id);
      }     
      

      TRACE_SYSCALL (cpu, " HLT [Unknown angel %x]",
         aarch64_get_reg_u32 (cpu, 0, NO_SP));
      sim_engine_halt (CPU_STATE (cpu), cpu, NULL, aarch64_get_PC (cpu),
           sim_stopped, SIM_SIGTRAP);

注意しておきたいのは、readは戻り値ではなく、メモリに読み込んだ値を書き込んで返すということです。当たり前なのですが、私はうっかり戻り値に収まる大きさだったので戻り値として乱数を返してしまっており、時間を少し無駄にしました。（そのぶんaarch64のアセンブリを読めるようになったのでよしとしよう）。

ちなみにxorshift64_2は、試行錯誤の結果以下のコードでうまくいきました。（試行錯誤の過程が関数名に現れている。）

uint64_t xorshift64_2(uint64_t *state) {
  uint64_t x = *state;
      x = x ^ (x << 13);
      x = x ^ (x >> 7);
      x = x ^ (x << 17);
      *state = x; 
      return x;
}

xorshiftは、よい周期性をもつシフトパラメータがいくつも存在するので、どれが選ばれるかは実装依存なのですが、このパラメータはxorshiftの論文内で例として用いられていたものでした。

Xorshift RNGs George Marsaglia ∗The Florida State University

余談ですが、論文内のxorshift32の実装例のところに

It uses one of my favorite choices, [a, b, c] = [13, 17, 5]

と書いてあって、めっちゃわかるー、ってなっていました。64bit版もきれいでよい。

まあ、こんな感じでデバイスの実装自体は終わりですが、文字出力のほうも既存のsyscallの実装にかぶっていたのでよしなにしてあげます。（同関数の上方です。）

    case AngelSVC_Reason_Open:
      {
        /* Get the pointer  */
        /* uint64_t ptr = aarch64_get_reg_u64 (cpu, 1, SP_OK);.  */
        /* FIXME: For now we just assume that we will only be asked
           to open the standard file descriptors.  */
        static int fd = 0;
        result = fd ++;

        //TRACE_SYSCALL (cpu, " AngelSVC: Open file %d", fd - 1);
        uint64_t p0 = aarch64_get_reg_u64 (cpu, 0, SP_OK);
        uint64_t p1 = aarch64_get_reg_u64 (cpu, 1, SP_OK);
        uint64_t p2 = aarch64_get_reg_u64 (cpu, 2, SP_OK);
        uint64_t p19 = aarch64_get_reg_u64 (cpu, 19, SP_OK);
        //printf("p0:%lx p1:%lx p2:%lx sp:%lx p19:%lx\n", p0, p1, p2, aarch64_get_reg_u64 (cpu, 31, SP_OK), p19);
        printf ("%c", aarch64_get_mem_u8(cpu, p1));
      }
      break;

（いろいろdeadcodeがありますが気にしないでください。）

これでシミュレータをコンパイルして再度実行してあげるとフラグを得られました。

SECCON{UseTheSpecialDeviceFile}

Special Instructions

これも謎アーキです。cross-gccのサンプルをfileしたときの出力と、与えられたファイルのfileを比較した結果、アーキはmoxieとわかりました。

$ file runme_f3abe874e1d795ffb6a3eed7898ddcbcd929b7be 
runme_f3abe874e1d795ffb6a3eed7898ddcbcd929b7be: ELF 32-bit MSB executable, *unknown arch 0xdf* version 1 (SYSV), statically linked, not stripped

*unknown arch 0xdf* いい響きだ。

さて、というわけで適当に実行してみると、

This program uses special instructions.
SETRSEED: (Opcode:0x16)
RegA -> SEED
GETRAND: (Opcode:0x17)
xorshift32(SEED) -> SEED
SEED -> RegA

と出てから、SIGILLで落ちてしまいます。

cross-gcc494/toolchain/gdb-7.12.1/sim/moxie/interp.c にソースがあるので適当に読むと、該当する命令番号にご丁寧にも/*bad*/と書かれているのがわかりました。というわけで、適当に実装しちゃいましょう。

      case 0x16: /* bad */
        {    
          int a = (inst >> 4) & 0xf; 
          xorstate = cpu.asregs.regs[a];
          //printf("SETRSEED(%X)\n", xorstate);
        }    
        break;
      case 0x17: /* bad */
        {    
          int a = (inst >> 4) & 0xf; 
          //printf("GETRAND SEED=%X\n", xorstate);
          cpu.asregs.regs[a] = XorShift(&xorstate);
        }    
        break;

変数 xorstate は適当に関数sim_engine_runの先頭でstatic宣言しておきます。

void
sim_engine_run (SIM_DESC sd,
    int next_cpu_nr, /* ignore  */
    int nr_cpus, /* ignore  */
    int siggnal) /* ignore  */
{
  word pc, opc;
  unsigned short inst;
  sim_cpu *scpu = STATE_CPU (sd, 0); /* FIXME */
  address_word cia = CPU_PC_GET (scpu);
  static int xorstate = 0;

で、問題はxorshiftです。論文で示されているパラメータは64セットあるのですが、十数個試しても引っかかりません。こまった。

というわけで、適当にパラメタ化してソルバを書いてやりました。

int shift_table[9 * 9 * 3] = {
 1, 3,10, 1, 5,16, 1, 5,19, 1, 9,29, 1,11, 6, 1,11,16, 1,19, 3, 1,21,20, 1,27,27,
 2, 5,15, 2, 5,21, 2, 7, 7, 2, 7, 9, 2, 7,25, 2, 9,15, 2,15,17, 2,15,25, 2,21, 9,
 3, 1,14, 3, 3,26, 3, 3,28, 3, 3,29, 3, 5,20, 3, 5,22, 3, 5,25, 3, 7,29, 3,13, 7,
 3,23,25, 3,25,24, 3,27,11, 4, 3,17, 4, 3,27, 4, 5,15, 5, 3,21, 5, 7,22, 5, 9,7 ,
 5, 9,28, 5, 9,31, 5,13, 6, 5,15,17, 5,17,13, 5,21,12, 5,27, 8, 5,27,21, 5,27,25,
 5,27,28, 6, 1,11, 6, 3,17, 6,17, 9, 6,21, 7, 6,21,13, 7, 1, 9, 7, 1,18, 7, 1,25,
 7,13,25, 7,17,21, 7,25,12, 7,25,20, 8, 7,23, 8,9,23 , 9, 5,1 , 9, 5,25, 9,11,19,
 9,21,16,10, 9,21,10, 9,25,11, 7,12,11, 7,16,11,17,13,11,21,13,12, 9,23,13, 3,17,
13, 3,27,13, 5,19,13,17,15,14, 1,15,14,13,15,15, 1,29,17,15,20,17,15,23,17,15,26,
};

uint32_t XorShift(uint32_t *state)
{
  *state ^= *state << shift_table[SHIFT_INDEX * 3 + 0];
  *state ^= *state >> shift_table[SHIFT_INDEX * 3 + 1];
  *state ^= *state << shift_table[SHIFT_INDEX * 3 + 2];
  return *state;
}

SHIFT_INDEXを定義してビルド&実行をぶん回すスクリプトを用意して

for i in {0..80}
do
echo index=$i
touch ~/repo/cross-gcc494/toolchain/gdb-7.12.1/sim/moxie/interp.c && \
        make -s -C ~/repo/cross-gcc494/build/gdb/moxie-elf/sim CFLAGS+="-DSHIFT_INDEX=$i " &> /dev/null && \
        cp ~/repo/cross-gcc494/build/gdb/moxie-elf/sim/moxie/run /usr/local/cross-gcc494/moxie-elf/bin/ && \
        /usr/local/cross-gcc494/moxie-elf/bin/run runme_f3abe874e1d795ffb6a3eed7898ddcbcd929b7be | grep SECCON && exit
done

実行すると

$ ./solve.sh 
index=0
...
index=74
SECCON{MakeSpecialInstructions}

74番目は...13,17,15でしたね。うつくしい…。

ということで、フラグを得ました。（ところが十数分前にsrupさんがsubmitしていたのでした。きっとソルバを書き始めようとしていた頃でしょう。ちょっとくやしい。）

解けなかった問題

q-escape

megumishさんから教えていただいた

あたりを参考にしつつ、情報収拾をしている段階で時間切れでした。

$ ./qemu-system-x86_64 -device help 2>&1 | grep cydf
name "cydf-vga", bus PCI, desc "Cydf CLGD 54xx VGA"
name "isa-cydf-vga", bus ISA
$ nm qemu-system-x86_64 | grep cydf | grep ' d '
0000000000f5a580 d isa_cydf_vga_properties
0000000000f5a460 d pci_vga_cydf_properties
$ nm qemu-system-x86_64 | grep mmio | grep cydf
000000000068da40 t cydf_mmio_blt_read
000000000068ec70 t cydf_mmio_blt_write
0000000000a99bc0 r cydf_mmio_io_ops
000000000068dd90 t cydf_mmio_read
000000000068f9f0 t cydf_mmio_write
00:02.0 Class 0300: 1234:1111
/ # cat /proc/iomem | grep 00:02.0
  fc000000-fcffffff : 0000:00:02.0
  febc0000-febc0fff : 0000:00:02.0

これはがんばれば解けそうな気がするのでぜひやりたい。

Needle in a haystack

場所の特定はした。大阪の梅田ですね。（「新梅田研修センター」という看板が目立っていた。） 画面中央のビルは実在しなさそうなので怪しかったのですが、動画処理は得意ではないので撤退しました。

まとめ

今回は謎アーキ問題がそんなに多くなかったし、そこまで頭をひねるというわけでもなかったのは少し残念かもしれない。 とはいえ、単純なところで引っかかって時間を無駄にしてしまったり、そもそも準備不足で環境構築に時間を浪費する場面が多かったので、本戦に行く際には改善してゆきたい。 あと風邪を引いてしまったようなので、きちんと休んで回復したい。

運営の皆さん、面白い問題をありがとうございました！

ISUCON8 本戦に出てまあまあだった話

（この記事は本戦後の眠い頭を無理に回して書いています。どうか温かい目で読んであげてください…。）

これまでのあらすじ

前回は、ISUCON8予選に出てガチャを引いたら運良く本戦に行けることになった！という話を書きました。

hikalium.hatenablog.jp

というわけで今回は、本戦でどのようなことをしたのか、そしてその結果などをまとめてゆきたいと思います。

試合開始前

椅子CONではなく机CONだった

開場より少し早く会場に着いてしまったので、エレベーターホールで受付開始まで待っていたのですが、すでにかなりの人数が集まっていたのでびっくり。

入場開始するも、チームメイトのうさぎさん・megumishさんがまだ着いていなかったので、長蛇の列を横目に傍観していた。

列も捌けてきたし、まだ二人が来ないので入場して会場のあるフロアへ。

「机は各チームひとつくらいで」とのことだったので周囲を見回して見たところ、すでにけっこう埋まっていた。

埋まっていないもっとも多くある机は、3人だとちょうどよいか少し肩身がせまいかも、という感じだった。

広めの机はすでに確保されていたし、空いている広い机は椅子に座って作業するには適していない低い机だったので、まあしょうがない。

（もちろんたくさんのチームを招くために場所を確保するのはたいへんだったと思うのでありがたい限りだが、もう少し各チームの机が広かったらうれしいなあと思った。）

ストーリー説明

仮想椅子取引所ISUCOINというこれまた面白そうなテーマの背景ストーリーが説明された。あの人気SNS、ISUBATAと連携！とか、過去問をやっていてわかるネタがあって、良く練られていると感じた。

試合の中身

私はインフラ要員として雇われた感じなので、アプリのアルゴリズムそのものではなく、環境やDB, Webサーバの設定最適化を主に担当した。

環境としては、2cpu, 1G mem のサーバーが4台与えられて、初期状態では各サーバでDB, Webサービス共に動作していた。

目新しかった点は、サービスがDocker内で動いていたということである。Dockerよくわからん！となったので、とりあえず当初は、Dockerからアプリを引き剥がす作業に取り組むことになった。

megumish氏はアプリ本体、私はDBとWebサーバをひっぺがす作業をした。

今回はアプリがHTTPSで動作していたため、当初何も考えずにcertbotで新しくグローバルのドメイン用にLetsEncryptで証明書を取ってきたりしたのだが、なんとベンチマーカはグローバルIPではなくベンチマーカIPを対象にアクセスしており、そのIPにはグローバルのドメインとは別のドメインが割り当てられていたため、証明書エラーでベンチマークが落ちてしまった。これは、よくよくアプリのディレクトリを確認すると、Docker内のnginxが参照していた証明書が置いてあったため、それを証明書として指定してやればうまくいった。（ちょっと時間を無駄にしてしまった。）

同時に、アプリの実装を、デフォルトのgolangからPythonに変更する作業もした。ここまでの作業をしてdstatをつかってなんとなく状況を測定してみたところ、やはりCPUを食いつぶしていたので、次はDBを別サーバに分離することにした。

このあたりだったか、うさぎさんがさくっとLIMIT 1の修正などを追加してくれて、これにより得点が700前後->2000超になった。

https://github.com/kmyk/isucon8-final/pull/6

アプリサーバとDBサーバを分けてからベンチマークを再度かけてみたところ、DBサーバのCPU使用率が高く、律速しているような雰囲気だった。

ここでうさぎさんが、ローソク足の計算を毎回履歴を走査して計算することなく、アプリ起動時にキャッシュするようにすればよいのではないかと気づき実装してくれた。

https://github.com/kmyk/isucon8-final/pull/9

この修正により、ベンチマーク中のDBサーバのCPU利用率は、ベンチ開始時にどかんと上がり、すぐに低くなって低いまま走る、という感じになった。

この、ベンチ開始時に急にCPU利用率が上がるという現象は、今後ロードバランシングする上で問題になりそうだったので、そもそも初期データに対するローソク足の計算は事前にやっておいてテーブルの初期データに挿入しておけばいいという話になり、その変更が入った。

https://github.com/kmyk/isucon8-final/pull/12

これにより、DBの利用率はかなり落ちて、またシェアボタンも確率的に出すようにしたところ( https://github.com/kmyk/isucon8-final/pull/10 )、アプリが律速してきたような印象だったため、ロードバランシングをするようにしてみた。

https://github.com/kmyk/isucon8-final/pull/13

当初は2台でロードバランシングしていたが、それでも1台のサーバに対してベンチマークをかけて2台のサーバのCPU利用率が上がるのは、見ていて非常に楽しかった。

と、ここに来て、連続でベンチを2回走らせると必ず事前チェックでfailするという問題が明らかになり、どうも初期に投入した、settingsのシングルトン化がバグっていたということがわかり、revertするなどした。

megumish氏はこの裏で、ログ送信を即時ではなくキューイングして非同期に行う方法を模索していたのだが、それがなかなかうまくいかずこの辺りでチームの人々に疲れが相当見え始めた。

結局最後は、全4台でアプリサーバをロードバランスしつつ、DBサーバはひとつという構成に落とし込んで、ガチャを回しつつ再起動テストに備える（ただし実際に再起動はしないで最後は祈る）ということをした。

結果

f:id:hikalium:20181020235815p:plain

f:id:hikalium:20181020235848p:plain

明らかに得点が伸び悩んだので、これはかなり厳しい結果だったのではないかと誰もが覚悟していたが、予想に反して全30チーム中12位の最終7475点（途中最高は7752点）、学生チームだけで見れば第4位と、そこまでひどくない成績を残せたようで、チームメンバー一同少し心がやわらぎました。

そして、なんと優勝は学生チームの「最大の敵は時差」で、35312点でした。すごい！おめでとうございます。

社会人チームの「takedashi」は、最大で5万点超えを出していたようですが、再起動後に動作が不調で減点の結果、2位となったようです。残念（でもすごい）。

講評や反省

試合結果発表後、問題作成者による講評があったのですが、DBのパーティションを解除しましたか？したほうが高速だったよ、という話を聞いて、それは気づかなかったなあ、まだまだ勉強が足りないな、と思いました。

また、私がPythonにそんなに慣れていないこともあって直接ロジックの改良に加われなかったこと、非同期処理や排他制御に関する知識の不足、そもそも練習不足なども多くあったなあと、反省する点が多く見つかりました。

もちろん、これまで何度か練習をしたことで得た知見を活かせていた部分もあったので、もっとこれからもいろいろ知識を身につけてゆけばよいのですが。がんばってゆきたい！

感想

  • 高レイヤ、まだまだ知らないことが多すぎる
  • 非同期・マルチスレッドの知識が薄かったので深めたい
  • ISUCON楽しい！

学生生活延長することになったし、来年も本戦に出られるよう精進します。次こそは優勝するぞ！

f:id:hikalium:20181020231226j:plain