SECON 2017 Online CTF writeup (Remote debugging of a micro computer)

概要

SECCON 2017 Online CTF にチーム Bluemermaid (a.k.a. Harekaze)として参加し、Remote debugging of a micro computer (300) を解きました。 この問題を解いたチームは13チームと結構少なめだったようです。 また、チーム全体では5800ポイントで第3位でした。最終的に出題されていたほとんどの問題が解かれていてびっくりしました。チームのプロの皆様に感謝 :pray: 。

ちなみにこれに時間を費やした結果、TOEICに行き損ねました。

バイナリの方が話者多いし問題ないでしょ!

解くまでの過程

問題

Remote debugging of a micro computer

Connect to the server and read "word.txt" on current directory.

$ echo '$g#67+' | nc micro.pwn.seccon.jp 10000

The server is running on GDB simulator with special patches.

Long time connection will be disconnected automatically. (in several minutes)

Short interval requests will be also ignored. (in several seconds)

URLとポートが与えられ、そこにncで接続すると、GDBのリモートデバッグプロトコルで問題サーバーとお話しできます。 そして、word.txtというファイルがカレントディレクトリにあるので、それを読んでね!という内容でした。

与えられている情報は:

  • デバッグポートのURLと番号
  • 去年も同じような問題を出したよ
  • SOP(Step-Oriented Programming)というのがあるよ(スライドへのリンク)
  • 去年の問題サーバのソースとか、マルチアーキテクチャ対応のgccはここにあるよ(リンク)

という感じでした。つまりですね、この問題は

「対象アーキテクチャが一切不明な状態」 で始まるのです。

SOP(Step-Oriented Programming)ってなんだ

これはたしか坂井さん(KOZOSやバイナリかるたとか熱血アセンブラ入門で有名なあの方です。セキュリティキャンプなどで大変お世話になっております)の造語で、「デバッガでステップ実行することで任意コード実行できるよね?じゃあやってみようか」というものです。 今年のCODEBLUEでも坂井さんがこの話で登壇されていらっしゃいました。というか、問題で提示されていたスライドはどう見てもCODEBLUEのときのものです。

www.slideshare.net

ただし、フル機能のデバッガが使える状態であれば、あまりにも簡単過ぎてお話しになりません。 というわけで、問題文をよく読んでみるとThe server is running on GDB simulator with special patches. と書いてあります。つまり、このリモートデバッガはなんでもできる訳ではなく、機能が非常に制限されているのです。

どの程度制限されているかということはスライドに記載があります。

簡単に説明すると、デバッガは通常、レジスタへの読み書きと、メモリへの読み書きができるのですが、今回は「メモリへの書き込みができない」ような状態になっています。

いやー、それはそうですよ。だって、メモリに書き込めちゃったら、(アーキテクチャさえわかれば)簡単に任意コード実行できますからね。

という訳で、この問題で重要なパートは以下の2つに大別されます。

  • 対象バイナリのアーキテクチャを特定する
  • 任意コード実行をできるようにしてフラグファイルを読む

ではまず、アーキテクチャの特定からとりかかりましょう。

アーキテクチャの特定

さて、アーキテクチャを特定したかったのですが、まずこの問題はバイナリが配布されていません。バイナリがないことには(一般人は)アーキテクチャを特定しようがないので、どうにかバイナリを手に入れることを考えます。

バイナリをもらってくる

GDBデバッグプロトコルには、メモリを読み込む命令があります。形式は以下の通りです。

$m<addr>,<count>#<checksum>+

addrとcountは16進数です。桁数は適当で大丈夫でした。 checksumは、コマンド部分に相当するバイトの総和をhexで記述します。 といっても、いちいち手動で計算するのはつらいので、問題文に書いてあった昨年の解答例に含まれているperlスクリプトを利用するとよいでしょう。スクリプトを利用する際は、先頭の$と末尾の#<checksum>+はつけなくて大丈夫です(自動で付加されます)。

echo "m0000,100" | ./sendgdbproto.pl | nc micro.pwn.seccon.jp 10000

すると、こんな感じの応答が得られます。

+$00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#00

うん。たしかに100バイトですね。でも全部0...。

いつかバイナリに当たることを祈って、順次アドレスを変化させてゆきます。 ちなみに、一度に取得するサイズを大きくしすぎると

+$E03#a8

のように、Eが先頭につく返答が帰ってきます。かなしいです。 だいたい300くらいまでは大丈夫そうでした。

で、やがて見つける訳です。バイナリを。

echo "m2000,200" | ./sendgdbproto.pl | nc micro.pwn.seccon.jp 10000
+$11400e08b0137620b01381011001b01384011001b01385011001b01382011001b01383011001b0130820b1000200c14d0100cd01ad0001001e43b0131420a100020010010a140a4db0132a200c4a0a1610012a14094cca0d6d4d0d930924880044200c494813aa0001006d4a0d93f9230c43281610011c438d006821b01352200c43b01326205a143a401f00064305461e430b46084e085e094b096b074807fc0f490ffd0fd70f93022406de05db3a530e480b490a93ee230c460d45551610010a1408142a428800862048133a530a93fc2308160a1610016a14b1001400814c00000c4d0d4e0a4fc14313000e4c0edd0e9303200f9301201a43ce01ae0012000e1440183841401839418700762180003621044c34f00f000e43054e051204120e16ee07e64e0000b013c0200a9501243a53385339630912081206160e4c0edd0e93e7230a930524f64030000000800030212c41cd06ad000100b01352200c43a10014006416100148656c6c6f20576f726c64210a00303132333435363738396162636465660000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#2a

おおー!待望のバイナリですね。これでもう勝てた...と思ったら大間違いです。ここからがつらかった...。

じっとながめる

上記の出力から無駄な部分をのぞいて、純粋なバイト列にしたものが以下です。

00000000  11 40 0e 08 b0 13 76 20  b0 13 81 01 10 01 b0 13  |.@....v ........|
00000010  84 01 10 01 b0 13 85 01  10 01 b0 13 82 01 10 01  |................|
00000020  b0 13 83 01 10 01 b0 13  08 20 b1 00 02 00 c1 4d  |......... .....M|
00000030  01 00 cd 01 ad 00 01 00  1e 43 b0 13 14 20 a1 00  |.........C... ..|
00000040  02 00 10 01 0a 14 0a 4d  b0 13 2a 20 0c 4a 0a 16  |.......M..* .J..|
00000050  10 01 2a 14 09 4c ca 0d  6d 4d 0d 93 09 24 88 00  |..*..L..mM...$..|
00000060  44 20 0c 49 48 13 aa 00  01 00 6d 4a 0d 93 f9 23  |D .IH.....mJ...#|
00000070  0c 43 28 16 10 01 1c 43  8d 00 68 21 b0 13 52 20  |.C(....C..h!..R |
00000080  0c 43 b0 13 26 20 5a 14  3a 40 1f 00 06 43 05 46  |.C..& Z.:@...C.F|
00000090  1e 43 0b 46 08 4e 08 5e  09 4b 09 6b 07 48 07 fc  |.C.F.N.^.K.k.H..|
000000a0  0f 49 0f fd 0f d7 0f 93  02 24 06 de 05 db 3a 53  |.I.......$....:S|
000000b0  0e 48 0b 49 0a 93 ee 23  0c 46 0d 45 55 16 10 01  |.H.I...#.F.EU...|
000000c0  0a 14 08 14 2a 42 88 00  86 20 48 13 3a 53 0a 93  |....*B... H.:S..|
000000d0  fc 23 08 16 0a 16 10 01  6a 14 b1 00 14 00 81 4c  |.#......j......L|
000000e0  00 00 0c 4d 0d 4e 0a 4f  c1 43 13 00 0e 4c 0e dd  |...M.N.O.C...L..|
000000f0  0e 93 03 20 0f 93 01 20  1a 43 ce 01 ae 00 12 00  |... ... .C......|
00000100  0e 14 40 18 38 41 40 18  39 41 87 00 76 21 80 00  |..@.8A@.9A..v!..|
00000110  36 21 04 4c 34 f0 0f 00  0e 43 05 4e 05 12 04 12  |6!.L4....C.N....|
00000120  0e 16 ee 07 e6 4e 00 00  b0 13 c0 20 0a 95 01 24  |.....N..... ...$|
00000130  3a 53 38 53 39 63 09 12  08 12 06 16 0e 4c 0e dd  |:S8S9c.......L..|
00000140  0e 93 e7 23 0a 93 05 24  f6 40 30 00 00 00 80 00  |...#...$.@0.....|
00000150  30 21 2c 41 cd 06 ad 00  01 00 b0 13 52 20 0c 43  |0!,A........R .C|
00000160  a1 00 14 00 64 16 10 01  48 65 6c 6c 6f 20 57 6f  |....d...Hello Wo|
00000170  72 6c 64 21 0a 00 30 31  32 33 34 35 36 37 38 39  |rld!..0123456789|
00000180  61 62 63 64 65 66 00 00  00 00 00 00 00 00 00 00  |abcdef..........|
00000190  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

みなさんはこれを見て、何を思いますか? ごく少数のプロを除けば、「は?」という感じだと思います。

これ以降は、私が適当に時間をかけて無理やりアーキテクチャを特定した話なので、参考になるかはご自身で判断してください。 もし、もっといい方法があったなら(きっとある)ぜひ教えてください...。

まず、気づくこととしては

  • eが多い訳でもない -> ARMっぽくない
  • b0 13が頻出する(なんかありそう)
  • 10 01もたまに出てくる (なんかありそう)
  • 最後の部分はASCIIコードでHello World!のあとに'0-9a-z'って書いてある

があげられると思います。 というわけで、バイナリ部分をとりあえず予想にしたがって切ってみましょう。

11400e08
b0137620
b01381011001
b01384011001
b01385011001
b01382011001
b01383011001
b0130820b1000200c14d0100cd01ad0001001e43
b0131420a100020010010a140a4d
b0132a200c4a0a1610012a14094cca0d6d4d0d930924880044200c494813aa0001006d4a0d93f9230c43281610011c438d006821
b01352200c43
b01326205a143a401f00064305461e430b46084e085e094b096b074807fc0f490ffd0fd70f93022406de05db3a530e480b490a93ee230c460d45551610010a1408142a428800862048133a530a93fc2308160a1610016a14b1001400814c00000c4d0d4e0a4fc14313000e4c0edd0e9303200f9301201a43ce01ae0012000e1440183841401839418700762180003621044c34f00f000e43054e051204120e16ee07e64e0000
b013c0200a9501243a53385339630912081206160e4c0edd0e93e7230a930524f64030000000800030212c41cd06ad000100
b01352200c43a1001400641610014
8656c6c6f20576f726c64210a0030313233343536373839616263646566

おー、たしかにb0 13がたくさんありますね。しかも先頭の方、末尾が全部01 10 01 になっていて、怪しいです。 でも、01 10 01で1命令だとすると、先頭部分と合いませんね。そもそも3バイト固定ってアーキテクチャってのも変だし...。

というわけで、これ以上予想を重ねるのはやめて、きちんと動作を確認して予想を立てることにします。

ステップ実行してレジスタの様子をみる

こういう時はステップ実行すれば、命令境界がわかって嬉しいですね。 というわけで、レジスタをトレースしつつ、ステップ実行してみましょう。 現在のレジスタ状態を取得するコマンドはg, ステップ実行はsです。

g
s
g
s
g

これを適当にcmd.txtとでも保存して、cat cmd.txt | ./sendgdbproto.pl | nc micro.pwn.seccon.jp 10000とすれば、順次実行時のレジスタ状態が降ってきます。かんたんですね。

+$00200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#02+$T05#b9+$04200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#06+$T05#b9+$76200000fcff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000#1a+$T05#b9+$78200000fcff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000#1d+$T05#b9+$7c200000fcff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000682100000000000000000000#59+$T05#b9+$52200000f8ff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000682100000000000000000000#fb+$T05#b9+$54200000ecff0f000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000682100000000000000000000#27+$T05#b9+$56200000ecff0f000000000000000000000000000000000000000000000000000000000001000000000000000000000001000000682100000000000000000000#2a+$T05#b9+$58200000ecff0f000000000000000000000000000000000000000000000000000000000001000000682100000000000001000000682100000000000000000000#3d+$T05#b9

これを見ていると、いくつかわかることがあります。まず、最初の少なくとも2バイトがプログラムカウンタだということ、そして途中で突然4バイトめが負の数っぽくなっていることから、そのあたりがスタックポインタっぽい、しかもその幅をみるに、16bitに収まらないから32bitだろう...などです。

でも、出力を読むのがつらいです。どこでレジスタが切れているのかわからない...。 というわけで、これを自動でフォーマットしてくれる&前状態との差分をとってくれるプログラムを書きました。

seccon 2017 online CTF writeup (Remote debugging o ...

このプログラムでは、レジスタ幅を32bitとしていますが、当初私は16bitと仮定していて、上に書いた通りスタックポインタの動きを見て、32bitだと考えて修正しました。

で、もうちょっとステップ実行の回数を増やして、出力をこのプログラムに食べさせると、こんな感じになります。

PC: 0x2000
----
PC: 0x2004
----
PC: 0x2076
        SP: 0x0 -> 0xffffc
----
PC: 0x2078
        R12: 0x0 -> 0x1
----
PC: 0x207c
        R13: 0x0 -> 0x2168
----
PC: 0x2052
        SP: 0xffffc -> 0xffff8
----
PC: 0x2054
        SP: 0xffff8 -> 0xfffec
----
PC: 0x2056
        R9: 0x0 -> 0x1
----
PC: 0x2058
        R10: 0x0 -> 0x2168
----
PC: 0x205a
        R13: 0x2168 -> 0x48
----
PC: 0x205c
        R2: 0x0 -> 0x1
----
PC: 0x205e
----
PC: 0x2062
        R8: 0x0 -> 0x2044
----
PC: 0x2064
----
PC: 0x2044
        SP: 0xfffec -> 0xfffe8
----
PC: 0x2046
        SP: 0xfffe8 -> 0xfffe4
----
PC: 0x2048
        R10: 0x2168 -> 0x48
----
PC: 0x202a
        SP: 0xfffe4 -> 0xfffe0
----
...

この出力をどんどん見てゆくと、

  • 命令サイズは2 or 4バイト
  • レジスタ数は16本(PC, SP含む)
  • b0 13 aa bb = call 0xbbaa っぽい
  • 8r aa bb cc = Rr = 0xccbbaa っぽい

ということがわかります。分岐命令や代入命令はそこそこ登場頻度が多いので、それがわかればアーキテクチャを見分けられる可能性が高まります。

では、これらのヒントをもとに、アーキテクチャを絞り込んでゆきます。

絞り込む(目grep

最初はgrepb0 13とか調べればいいかなと思ったのですが、どうもぱっとしませんでした。というわけで、ありそうなアーキテクチャアセンブリコードを総当りすることにしました。

ヒントとなるのは、問題に書かれていたクロスコンパイラの中にあるサンプルです。 cross-gcc494/sample/*.dには、各アーキテクチャ向けのバイナリ&アセンブリ例が載っています。

ここを読んで、形式が似ているかどうか、そして、同じ命令がないかをじっくり探しました。

- このCPU -> 2, 4バイト混在, 16個のレジスタ(4byte), アドレス幅は16bit?
- aarch64 -> 4バイト固定
- alpha -> 4バイト固定
- arm -> 4バイト固定
- arm16 -> 2, 4バイト混在
- mn10030 -> 可変長命令、ちょっとちがう
- avr -> 2バイト固定
- avr8 -> 2バイト固定
- bfin -> 2, 4混在
- cr16 -> 2, 4混在
- cris -> 2, 4, 8バイト, ちょっとちがう
- epiphany -> 2, 4混在
- frv -> 4バイト固定
- fr30 -> 2, 4混在
- h8300 -> 2, 4バイト混在,
- h8300h -> 2, 4バイト混在,
- hppa -> 4固定
- i386 -> 可変長
- lm32 -> 4バイト固定
- m32r -> 4バイト固定
- m32c -> 1-4可変
- m6811 -> 1-4バイト可変
- m68k -> 2, 4, 6可変
- mcore -> 2バイト固定
- microblaze -> 4固定
- mips -> 4バイト固定
- mips16 -> 2, 4バイト混在。
- mips64 -> 4固定
- mn10300 -> 1-3バイト混在
- moxie -> 2, 4混在
- msp430 -> 2, 4混在
- powerpci -> 4バイト固定
- sh -> 2バイト固定
- sh64 -> 4バイト固定
- sparc -> 4バイト固定
- v850 -> 2, 4バイト混在

そして、やっとmsp430にたどり着いた訳です。

ちなみに、決め手はこのサイトでした。

16進数を流し込んだら、「読める、読めるぞ!!!」という感じで最高に嬉しかったです。

あとはシステムコールを叩くだけ...どうやって?

さて、これでアーキテクチャは完全にわかったので、どのコード片がどういう動作をするのかだいたい把握できた訳です。 あとは、システムコールを叩いてword.txtを読むだけなのですが、しかし、どうやらこのアーキテクチャでは、システムコールは「syscall命令」や「割り込み」ではなく、関数呼び出しとして実装されているようです。syscallみたいな文字が見えないですし。

(2017-12-11追記:作問者の坂井さんより、このアーキテクチャではシステムコール呼び出しに使えるCPUの機構がおそらくなく、そのためシミュレータは「モニタ」とよばれる、各マイコンメーカから提供されるデバッガのようなハードウエアの動作を模倣しているのではないか、もしくはこの「システムコール」はGDBの独自拡張ではないか、という話でした。ちなみに、こういった「特定番地を呼び出すとシステムコール的な動作をする」仕組みのことを、H8マイコンでは magic trap というらしいですが、一般的な用語ではないそうなので、「システムコールっぽいサービスを関数呼び出しでエミュレーションしているよくあるやりかた」と言うと通じるらしいです。)

ここは少し悩んだ結果、disasmした結果から、"Hello World!"している場所を探して、どうやって処理しているか確認しました(私もこれを書きながら一瞬どうやったのか忘れてしまいました)。

まず、"Hello World"という文字列が格納されているアドレスですが、それは物理メモリ上の0x216eでした。 で、disasmした結果からこの番地を使っている場所を探すと、

2076: 1c 43                            mov   #1, r12 ;r3 As==01
2078: 8d 00 68 21                      mova #8552,  r13 ;0x02168
207c: b0 13 52 20                      calla    #8274       ;0x02052
2080: 0c 43                            clr  r12     ;
2082: b0 13 26 20                      calla    #8230       ;0x02026

という場所が見つかり、ここが文字列を出力している部分と思われます。ここでは2回callaがありますが、ひとつめはstrlenした結果をr14に格納するようなコードに飛ぶもので、問題は2つめのほうです。この飛び先は...。というあたりで、どうやって解いたのか忘れてしまいました。 ここは思い出したら追記します。ごめんなさい。メモリがそろそろ耐用年数を過ぎていて...。

ひとまず、特定のアドレスに飛ぶことが、syscallを呼び出すことになると理解してください。

結果、以下のことがわかりました。

  • open(path, flags, mode)は以下の命令を以下のレジスタ状態で呼べば良い。

    • 201a: b0 13 82 01 calla #386 ;0x00182
    • R12 = path
    • R13 = flags
    • R14 = mode
  • read(fd, buf, size) は以下の命令を以下のレジスタ状態で呼べば良い。

    • 200e: b0 13 84 01 calla #388 ;0x00184
    • R12 = fd
    • R13 = size
    • R14 = buf

任意メモリ書き換えの手段

これも、アセンブリの中から使えそうな命令を拾ってきます。私が選んだのはこの子です。

20de: 81 4c 00 00         mov    r12,    0(r1)    ;

この命令を実行すれば、r12のデータがr1番地に書き込まれます。試したところ、16bit分でした。わーい。

道具は揃った

さて、これで道具は揃いました。すべきことは3段階です。

  • "word.txt"をメモリ上のどこかにつくる
  • openする
  • readする

これらは、

Gコマンドでレジスタを特定の状態に設定し、 sコマンドで動かす

ということを繰り返せば実現できます。

最初の目標は、言い換えれば77 6f 72 64 2e 74 78 74 00をメモリに書き込むことでした。 ちょうど、"Hello World!"の後半は"World"だったので、この辺りに書き込むことにします。(効率化は面倒なのでしなかった。あとでやってみたい。) アドレス0x216eからの場所に書き込むとすれば、

Gde2000006e2100000*l776f00000*4
s
Gde200000702100000*l726400000*4
s
Gde200000722100000*l2e7400000*4
s
Gde200000742100000*l787400000*4
s
Gde200000762100000*l000000000*4
s

こうすれば書き込めます!あ、ちなみに0*lとかは省略表記で、*の前の文字を、(後ろの文字のASCIIコード-28)回書くことと同義です。(2017-12-11 回数が間違っていたので修正しました。)

スライドには「さらに(後ろの文字のASCIIコード-29)回書いたのと同じ」と書いてあって私は誤解した(全体でこうだと思っていた)ので、気をつけるといいと思います。

つまり、0*40が32個と等価になるわけです。

そして、最後のsyscallですが、openは

G1a20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006e210000000000000000000000000000
s

readは

G0e2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000006e2100002000000000000000
s

とすればよいです。もちろん、読み出した結果を知る必要もありますから、末尾にメモリ呼び出し命令をつければ、全体では

m0216e,10
g
Gde2000006e2100000*l776f00000*4
s
Gde200000702100000*l726400000*4
s
Gde200000722100000*l2e7400000*4
s
Gde200000742100000*l787400000*4
s
Gde200000762100000*l000000000*4
s
G1a20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006e210000000000000000000000000000
g
s
g
G0e2000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000006e2100002000000000000000
s
g
s
g
m0216e,20

という感じになります(実際にこれで通しました)。最後に出力されたメモリ内容が、フラグの文字列データになっていました。

あ、実はopenしたファイルディスクリプタが2になると信じ込んでいて、(stdin: 0, stdout: 1, stderr: 2 だから3になるのはあたりまえ)、それで10分くらい無駄にしたのは秘密です。

本当は省略表記を活用すればもっと綺麗になったかと思いますが、それはまたの機会に。

おわりに

TOEICをさようならしたおかげで、なんとか問題を解くことができて非常に嬉しかったです。

競技時間内は、なんのアーキテクチャかわからず6時間くらい苦しい時間を過ごしていたので、もっと色々なアーキテクチャのことを知らなければ、と思いました。

久々にバイナリをたくさん食べてお腹がいっぱいになったので、また明日からも頑張れそうです。

ではみなさまも、存分にバイナリをお楽しみください。

NVMeドライバをLinux上でuioを用いて開発してみたが間に合わなかった

はじめに

いいですか。「開発してみました」というのは、「完成しました」ではないのです…。

「黙って現在の進捗を差し出せ!」という方はこちらをご参照ください。

github.com

この記事はなに

自作OSアドベントカレンダーの7日目として書かれた記事です。

17日を書こうと思ったら、すでに登録されている方がいらっしゃいましたので、2番目に好きな素数を選びました。

話は6か月前にさかのぼる…

6ヶ月ほど前でしたでしょうか。Liva師からこんな話が降って来たのは。

Liva師「hikaliumさん、うちの自作OS(Raphine)向けにNVMeのドライバとか書いてみたくない?」

hikalium「いいですね〜」

いいですねーと言ってしまったものの、私は実は本当のドライバというものを書いたことがありませんでした。

これでは、自作OS開発者失格ですね。

というわけで、とりあえずnvmeの仕様をざっと読んでみることにしました。

NVMeってなに?

Non-Volatile Memory Expressの略で、不揮発性メモリ(SSDとか)を高速に読み書きできるインターフェイスを提供するよ!というものです。やっぱり速いのは正義ですね。 最近はこの、NVMeのインターフェイスで通信するSSDもだいぶ増えてきていて、ノートPCにも内蔵されていたりします。 これは自作OSとしてはサポートするしかありませんね!

どれくらいすごいインターフェイスなのかは、検索するなりWikipediaでも眺めておいてください。 私たちが知りたいのはそれよりも下の、どうやって制御すればいいのか、というところですので。

というわけで、まずは仕様を読んでみました。

仕様はどんな感じ?

NVMeの仕組み自体は、そこまで難しいものではありません。

まずは、データ構造の話から。仕様書の4章をみてください。

Submission Queue / Completion Queue

NVMeのコントローラとコマンドやデータをやり取りするためには、Submission Queue / Completion Queueという、リングバッファのような構造を用います。この解説が、4.1に書いてあります。

Submission Queue(略してSQ)は、コントローラに対してコマンドを送るために使用します。たとえば、読み書きを行ったり、設定情報を読み書きしたりするときには、このSQに私たちがコマンドを書き込んであげるわけです。

Completion Queue(略してCQ)は、逆に、コントローラから「コマンドが完了したよー」もしくは「エラーがおきた!」ということを私たちに通知するために使用されます。

NVMeのすごいところは、これらのQueueのセットを、複数作成することができる、という点です。 これにより、複数のCPUコアに、Queueのセットを1つずつ持たせることなども可能になり、コア間でQueueのロックを取り合って性能が低下することを避けることができます。

さて、これらのQueueは、あくまでもコントローラーに対する「命令」と、その「結果」をやり取りするためのものです。 そのため、これらのQueueのエントリの大きさは、固定されています。では、例えばSSDに対して読み書きなどを行いたい場合、どのようにコントローラとの間でデータをやり取りするのでしょうか?

Physical Region Page Entry / List

ということで、コントローラーとの間で大きなデータをやり取りする際に用いられるのが、Physical Region Page(PRP)エントリおよびリストです。詳細は、仕様書の4.3を確認してください。

PRPエントリは、物理メモリの場所を指し示すポインタです。そのため、64bitの幅を持っています。 これが指すメモリ領域の大きさはコントローラのレジスタCC.MPSで定義します。つまり、PRPエントリひとつあたりが指すメモリ領域は固定です。最低でも、4KBの大きさがあります。(ページングみたいですね。)

コントローラに対して送るコマンドの構造体には、このPRPエントリを書ける場所が2箇所ありますが、4*2=8KBしか一度に転送できない、とかいうわけではありません。もっと大きなメモリ空間を指定したい場合に用いられる構造が、PRP Listです。

PRP List は、PRPエントリが指し示すメモリ領域に、PRPエントリを敷き詰めることで構成されます。 コマンドのPRPフィールドに、PRPエントリを指定するのか、PRPリストを指定するのかは、コマンドによって異なるようです。

ちなみに、PRP List / Entry以外にも、Scatter Gather Listとかいうかっこいい構造を使うこともできるのですが、今回の実装では使用していないので省略します。(知りたい人は4.4を読んでください。)

Namespace

NVMeは、他のストレージインターフェイスと異なり、ストレージ空間をNamespaceというパーティションのようなものに分割することができます。仕様書の1.4 Theory of Operationには、図解入りでその説明が書いてありますが、パーティションのようなものだと思っておいていただければOKです。 この、Namespaceを区別するIDを、Namespace ID (NSID)と呼びます。16bit幅の値をもち、0は常にInvalidで、0xffffffffはBroadcast Valueといい、全Namespaceを表すIDとして使われます。

話はいいからさっさとドライバを書け

こんな感じで、いろいろと情報をまとめたのはよかったのですが、セキュリティキャンプでCPUの作り方を教えたり、大学の学園祭の準備をしていたり、CODEBLUEでNOCをしたりしていたら、いつのまにか冬になってしまいました。

私は、Liva師が非常に進捗を重視する方であると知っていたので、きっと進捗を出していない私はもう見向きもされないのだろうと思い、ひっそりと生きていこうと思っていたのですが、そんなときにLiva師から神の手が差し伸べられたのです。

Liva師「NVMeのドライバ、まだやる気があるなら、ちょっとおもしろいことをしてみようと思うので、いかがでしょうか。」

Liva師「uioというものがあってね…。それを使うと、Linuxでドライバが簡単に書けちゃうんだ。」

なんですって!これは書くしかありませんね。

uioはすごいぞ

uioというのは、Userspace IOの略で、なんとユーザー空間からIOを制御できるというスグレモノのカーネルモジュールです。

ドライバを書いたことがある人ならわかると思いますが、ユーザーランドでドライバを書けるということは本当にすごいことです(技術的にではなく心理的に)。 だって、

  • バグってもカーネルパニックになりにくい(たいていSEGVで済む)
  • いろいろ面倒をみてくれる
  • printfができる!!!
  • gdbがつかえる!!!

こんなことがドライバの開発でできるんですよ!! 画面の色やキーボードのLEDを変化させたり、がんばってシリアルポートを制御したりして苦労してデバッグをする時代は終わったんです! これからは、いくらでもprintfしていいんです!gdbであの変数の値を見ちゃってもいいんです。最高でしょ?

というわけで、まずはuioの使い方を知るところから実装は始まりました。

uioの使用例 〜Liva師のXHCIドライバ〜

心優しき、かのLiva師は、uioを用いてXHCIを実装してくださいました。

github.com

これと、上のドキュメントを読むのがもっとも正確ですが、要点をかいつまんで説明しましょう。

まずは、コマンドでPCIバイスの制御をuioに移します。

  • sudo modprobe uio_pci_genericを実行して、uio_pci_genericカーネルモジュールをロードする。
  • 制御したいデバイスのベンダIDとデバイスIDをスペース区切りで/sys/bus/pci/drivers/uio_pci_generic/new_idに書き込む。
  • 制御したいデバイスを、デフォルトのドライバからunbindする(/sys/bus/pci/drivers/$(TARGET_KERNEL_DRIVER)/unbindにバス番号を書き込む)
  • 制御したいデバイスを、uio_pci_genericドライバにbindする(/sys/bus/pci/drivers/uio_pci_generic/bindにバス番号を書き込む)

これが終わると、なんとプログラムからPCIレジスタ空間がファイル(/sys/class/uio/uio0など。最後の数字は複数attachしている場合は違う。)として見えるようになります。

使い方の簡単な例がドキュメントにありますが、簡単にいうと

  • /dev/uio0をreadすると、デバイスからの割り込みがかかるまでブロックされる。
  • /sys/class/uio/uio0/device/configmmapすれば、PCIレジスタ空間がメモリにマップされて触れるようになる
  • /sys/class/uio/uio0/device/resource0mmapすれば、BAR0のレジスタ空間を触れる(resource1にすればBAR1も読める)

これだけです。ここまで触れれば、PCIバイスのドライバは簡単に書けるはずです。 どうですかuio! みなさんも使ってみたくなりましたか?快適なドライバ開発ライフを私たちと一緒に送りませんか?

で、進捗どうですか

さて、ただいま12/7の23:40です。

私がドライバを本格的に書き始めたのは、12/6の朝なのですが...。 さすがに、NVMeのSSDに対する読み書きを実行するまでは間に合いませんでした。ごめんなさい。 年内には完成させますので、お楽しみに!

f:id:hikalium:20171207234823p:plain

ちなみに現在は、Identifyというコマンドをコントローラに送信して、その返答の割り込みを処理するところまで書きました。しかも実機で動きます。というか逆にVirtualboxで動きません。原因究明中です…。

途中でuio_pci_genericがうまく動作しなくなったり、Virtualboxでは割り込みが再現しない(多分私のコードのミスだけど)といった問題に悩まされましたが、約1日でNVMeさんとお話をできるレベルにはなったわけです。実機だけorカーネルランドで開発していたら、1日ではここまで来れなかったでしょう。やはりuioはすごいですね!

ちなみに、uioで書かれたドライバを、Raphineという自作OSに容易に移植できるよう、クラスなどを整備する予定ですので、今みなさんがuioでドライバを書けば、Raphineに取り込まれるかもしれませんよ!ぜひやってみてください!

まとめ

  • NVMeのドライバは未完成
  • uioは便利だからみんな使おう!!!というかドライバ書こう!
  • やっぱり低レイヤは最高だね!

VirtualBox上のCentOS7でQuartus Primeを動かすためのVagrant Boxの使い方

タイトルが長すぎますね。反省。

作ったもの

概要

Quartus PrimeはMac向けのバイナリはない。そのため、Macで無理やり開発をするためには、VM上のWindowsLinuxにインストールする必要がある。

VM上のCentOS7にQuartus Primeを入れるためには、いろいろなパッケージやVirtualBox Guest Add-on を入れたりする必要がある。 これが面倒なので、それらの事前準備をすべて終えた状態のBoxを作成した。

Quartus Primeはインストールされていないので、以下の手順でインストールする必要がある。(容量とライセンスの関係から入れなかった。)

検証環境

手順

準備

事前に Oracle VM VirtualBoxVagrant by HashiCorp をインストールしておいてください。

また、事前にQuartus Prime Lite のLinux版を http://dl.altera.com/?edition=lite からダウンロードしておいてください。

さらに、以下のコマンドを実行して、Vagrantにscpのpluginをインストールしてください。

vagrant plugin install vagrant-scp

VMを作成・起動

適当なディレクトリで以下を実行(初回は仮想マシンイメージをダウンロードするので、ネットワーク接続のよいところで実行してください!)

git clone https://github.com/hikalium/centos-quartus.git
cd centos-quartus
vagrant up

QuartusのパッケージをVM内に転送する

vagrant scp <Quartus-lite-xxx.tarのパス> /home/vagrant/

ちょっと時間がかかります。

Quartusを展開してインストー

vagrant ssh
  • 以下はsshで接続したVM内での作業
tar -xvf <Quartus-lite-xxx.tar のファイル名>
./setup.sh
  • とりあえずEnterを連打して、ライセンスの条文を読む。
  • Do you accept ~?と出てきたら、yと入力してEnter
  • そのあとはすべてEnterでOK
  • インストールが開始する(少し時間がかかる)
  • インストールが終了したら、 「Launch Quartus ~ ?」だけはnと入力し、それ以外はyもしくは単にEnterでOK
  • VMGUI画面のデスクトップに、Quartusが追加されていたら成功です!

Verilog-HDLで算術右シフトを書く方法

結論

以下のように書けばよい。

重要な点は、signed>>>である。

何をどう勘違いしていたのか

算術右シフトをVerilog-HDLで書けるのか調べていたところ、以下の記事にぶつかった。

d.hatena.ne.jp

この記事では、>>>を使用すれば、算術シフト、>>を使用すれば論理シフトになるかのように読み取れる。

しかし、>>>を使用しても、私の手元では算術シフトにならず、論理シフトとして扱われていた。

当初、私はこれをエミュレータのバグではないかと疑っていた(icarus-verilogを使っていたため)。

しかし、Quartus付属のModelSimでも同様の動作であったため、これは根本的にコードが間違っているということに気づいた。

そして、以下のような記事を発見した。

FPGAの部屋 Verilog HDL で unsigned, signed の演算をする1

やはりいつも最後にはmarseeさんの情報にたどり着く。この記事には、算術右シフトのことについては触れられていなかったが、もしかしてと思ってsignedとつけたら、うまく動作した。

結論

  • Verilog-HDLでは標準で符号なしなので、符号ありとして扱いたい場合はsignedをつける
    • 符号なしの値に対して>>>を使ったら警告くらい出してくれてもいいのに…(気づかなかっただけか?)
  • 私は無知すぎる
  • エミュレーターを疑う前に自分の頭を疑うべき
  • やはり http://marsee101.blog19.fc2.com/ の情報は有用なのでもっと読むべき

CentOS7でModelSimが起動しない問題の解決策

結論

以下のライブラリが不足しているので入れればよい。

sudo yum install libX11-devel.i686 libXext-devel.i686 libXft-devel.i686 ncurses-libs.i686

現象

Tools -> Run Simulation Tool -> RTL Simulationを選択すると、以下のエラーメッセージが出て起動しない。

ライセンス関係やパス、環境変数の問題に見えるが、実際はそうではなかった。

原因追求

エラーメッセージに記載のログファイルを開いたところ、modelsim_ase/bin/vsimを実行しようとして落ちていることまでわかった。そこで直接これを実行したところ、ライブラリが見つからない旨表示された。

指定されたライブラリを以下のコマンドで探索した。

yum whatprovides */libname

見つかったパッケージを.i686をつけてinstallし、再度vsimを起動させることを数回繰り返した結果、起動するようになった。

結論

  • yum whatprovides */libnameはめっちゃ便利
  • レポートは早めにやろう

QuartusのプロジェクトをGitで管理する

意外にも日本語の情報が少なかったので書いた。

QuartusのようなIDEが作ってくれるプロジェクトをGitで管理する場合、問題になるのは、どこまでが自動生成のファイルで、どこからが自動生成ではないファイルなのか、というところである。

端的に言うと、.gitignoreをどう書けばいいのか、という情報を知りたいわけだ。

quartus project gitで検索をかけたところ、Alteraのフォーラムなどで同じことを考えている人がたくさんいることは発見した。

また、altera wiki に以下のようなページがあった。

Version Control - Altera Wiki

さらに、GitHubで良さげな.gitignoreを書いている人も見つけた。

github.com

というわけで、上の二つの資料を参考に.gitignoreを書けば幸せになれそうだ。

CentOS7でXのキーマップが日本語にならなくてつらいとき

  • Xのキーマップは独立してるということを忘れてはいけない(2行目)
localectl set-keymap jp106
setxkbmap jp -model jp106