はじめに
こんにちはNecoチームのsatです。本日はNecoチームの話ではなく、私が先週講師として参加した「セキュリティキャンプ全国大会 2018」というイベントの参加報告をいたします。このイベントの中でもとくに私が受け持った集中開発コース「Linux開発者を目指そう!」テーマについて述べます。
セキュリティキャンプ全国大会とは、お盆の時期に全国の学生が一か所に集まって、5日間その道のプロと一緒にセキュリティ技術について学ぶイベントです。イベントそのものについての詳細は以下リンク先をご覧ください。
「Linux開発者を目指そう!」コースの概要
「Linux開発者を目指そう!」コースは受講者が実際にLinuxカーネルの部品を開発、追加することによってLinuxカーネルの開発についての理解を深めてもらうためのものです*1。今回は2人の学生がこのテーマに取り組みました。
一人の方はLinuxのカーネルモジュール(後述)を独自開発しました。もう一人の方は独自のslabアロケータ(後述)を実装しました。では、お二方が具体的にどのようなことをしたかについて述べていきたいと思います。
独自カーネルモジュールの開発
カーネルモジュールとは
カーネルモジュールとはシステム起動時、およびその後の動作中にカーネルに機能を追加するための部品です。Webブラウザでいうプラグインを思い浮かべてもらえればいいかと思います。カーネルの機能のうちの多くの部分は最初からカーネルに組み込んでおくこともできますし、モジュールとして独立したファイルにしておいて必要になった時にカーネルに組み込むこともできます。
たとえばみなさんのPCに繋がっている各種デバイスを操作するデバイスドライバなどがそうです。モジュールはカーネル本体と同時にビルドできますし、後から別途個別にビルドもできます。本コースでは後者のアプローチをとりました。
開発の流れ
まずはカーネルモジュールのロード時にカーネルのログ*2に"hello world"と表示するだけの数行のプログラムを作るところから始めました。単純なプログラムなのですが、自分自身のコードがカーネルの一部として動くというのはなかなか体験できるものではありません。
続いてカーネルモジュールに問題があったらどうなるかというのを確認していただきました。具体的には通常のプロセス、およびカーネルモジュールの両方からNULLポインタにアクセスするプログラムを書きました。そうすると前者はNULLポインタにアクセスしたプログラムが異常終了するだけで終了しました。
これに対して後者はシステム全体が動作しなくなってしまいました。Windowsでいうブルースクリーンが出た状態に相当します。
実はこれ、実際のカーネルでこのような障害があれば立派な脆弱性になります*3。マルチユーザシステムで悪意のある一般ユーザのプログラムによってシステム全体がダウンしてしまうような場合を考えればわかっていただけるかと思います。こう書くだけでなんとなく理解はできるのですが、やはり聞くだけなのと実際にシステム全体を落としてみるのとでは理解の度合いが違います。
続いて彼は所定時間後に所定の処理を呼び出すカーネルタイマーというものについて学びました。最初はカーネルモジュールをロードしてから10秒後にメッセージを一回出力して終わり、というものから始まって、タイマーを二つ同時に起動するもの、二つのタイマーに別のメッセージを表示させるもの、などなど、多種多様なカーネルモジュールを作りました。
残念ながら本イベントの短い期間ではここで終わってしまいましたが、彼が具体的にどういうものを開発したのか、および、その先にどういうメニューが用意されていたのかについては下記の一連の中の文書とC言語ソースファイルをごらんください(独自開発ツールの使い方について述べている部分は読まなくていいです)。
講師の目から見て成長したところ
彼は低レイヤのプログラムに慣れていないことから最初はC言語の理解がおぼつかなかったのですが、最後には立派にカーネルモジュールが作れるまでに成長しました。初心者にとっての最難関であるポインタについてもプログラムのメモリマップを何度も図示しながら必死に学んだ結果、ある程度理解できるまでにこぎつけました。ポインタは本来一朝一夕で理解できるものではないので、これはすごいことです。
裏話: カーネル内インターフェースの変更
カーネルタイマーを使ったカーネルモジュールを作っていた時に思わぬ問題に遭遇しました。それは私が提供したサンプルソースが数年前に書いた古いものだったため、今回開発に使ったカーネルv4.18ではビルドできなかったことです。全然意図していなかったことながら、あるバージョンのカーネルに対して作ったカーネルモジュールが将来も修正なしに使える保証はLinuxカーネルにおいてはどこにもないことも学んでいただきました。この件についての詳細は下記の記事をごらんください。
独自slabアロケータの実装
slabアロケータとは
カーネルのメモリ管理サブシステムはハードウェアとの間でメモリをページという単位(通常4KB)でやりとりします。メモリ管理サブシステムはカーネルの他のコンポーネント、およびプロセスに対してはページを割り当てます。この割り当てプログラムのことをbuddyアロケータと呼びます。
しかし、バイト単位のメモリオブジェクトが欲しいカーネルサブシステムにとってこれは使いにくいです。たとえばメモリを8バイトだけほしいのにページ単位でしか要求できなければ、8バイトのために1ページを消費するという壮絶な無駄を発生させるか、あるいは自分自身でページを小分けして管理しなければなりません。
ここで「ページを小分けして管理」してくれるのがslabアロケータというしくみです。slabアロケータはbuddyアロケータからページを獲得した上で、ページをカーネル内サブシステムにバイト単位に小分けして渡します。図中にkmalloc()と書いてあるのは、ユーザ空間におけるmalloc()に相当するものであり、バイト単位のメモリ割り当てをする関数です。
linuxにはslabの実装が複数個存在します。具体的にはSLOB, SLAB, SLUBという3つです。似たような名前がたくさんあってややこしいですが、気にしないでください。
開発の流れ
彼は自分のslabアロケータにSLOBA(そば)というかっこいい名前を付けました。名前さえ付ければ終わったようなものです…というのは冗談として、最終日までの目的は「特定用途ではSLOB(最も単純な実装。メモリが少ないような環境で使われる)とSLAB(汎用。エンタープライズサーバ向けにも長きにわたって使われてきた)に勝つ」という明確なものでした*4。
フルスクラッチでslabアロケータを作るのはなかなか骨が折れるので、最初はSLOBをもとにして作り始めて、次第に独自のコードを増やしていくというアプローチをとりました。ベンチマークテストとして採用したのはkernelソースに対するdu -sコマンド発行の所要時間です。ディレクトリエントリごとにdentryと呼ばれるカーネル内のデータがslabアロケータから割り当てられるので、slabへの大量アクセスの所要時間が計測できるというわけです*5。
開発の初期段階で「SLOBのメモリ獲得処理はSLOBが持っているページの量に比例して多くなる」という事実に気づいた彼は、さっそくデータ構造を工夫して、定数時間でメモリ獲得できるように工夫しました。さらにその後には「SLOBは複数CPUから同時アクセスされるとスケールしない」などのSLOBの問題を次々に見つけ出し、改善していきました。スケーラビリティを上げる改善においては、spinlockの使い方に難儀したために無数のバグを仕込んでいましたが、最終日にはなんとか全て解決したようです。
最終的にはdu -sについてはシングルコア性能、マルチコア(4コア)性能共にSLOBには10倍以上の大差をつけて圧勝、SLABとはほぼ互角、という結果を叩き出しました。その上、SLOBAのコード量はSLABの約1/6に過ぎないというのですから驚きです。
筆者の見立てでは、SLOBにはほとんどのワークロードでも圧勝すると思いますが、SLABに対しては勝ったり負けたり、といったところでしょう。ぜひ色々なシステム構成、ワークロードでデータをとっていただきたいところです。
これ以上技術的な詳細には踏み込みませんが、参考までにSLOBとSLAB、SLOBAの構造を表す概要図を載せておきます。kmalloc()で取得するサイズごとにslabアロケータが存在するというイメージで見ていただければと思います*6。
- SLOB
- SLAB
- SLOBA
講師の目から見て成長したところ
彼は手を動かす速さについては最初から教えることは何もなかったです。今回はLinuxカーネル開発のお作法、効率的なソースコード解析およびトラブルシューティングの方法などを体験できたのがよかったのではないかと思います。今後はさらに高速に、かつ、高品質なコードを書けるエンジニアになってくれるのではないでしょうか。
裏話: 開発はインクリメンタルに
彼は二日目あたりで、とあるバグが取れない状態で悩んでいました。その際、「問題の無かったことがわかっているコミット」から「問題を検出したコミット」までの間のどのコミットが犯人かを二分探索によって見つけるbisectと呼ばれる方法*7を使おうとしましたが、それは不可能でした。なぜなら問題が起きなかった状態から起きるようになるまで一切コミットせずに数百行を変更してしまっていたからです。
彼の記憶にはバグに悩まされたことに加えて「次はインクリメンタルに開発しよう」という思いが刻まれたことでしょう。多分。
おわりに
本コースは「Linux開発者を目指そう!」と銘打っていますが、おふたりが今後Linux開発を続けるかどうかは彼ら次第です。本コースがLinuxという特定ソフトウェアの開発技術だけではなく、「トラブルに遭遇した時の対処方法」や「何かを変えるときは一回に一つだけという原則」、「ソースコードを読むコツ」など汎用的な知識を得るきっかけとなったのであれば幸いです。
*1:一見セキュリティには関係なさそうに見えますが、Linuxに限らずカーネルに関するセキュリティ知識を得るにはその基礎としてカーネルそのものの知識が必要なので、実は十分関係があるのです
*2:dmesgコマンドによって見られます
*3:たとえばCVE-2018-11232があります。興味のあるかたは読んでみてください。
*4:SLUBについては時間の都合上省略しました
*5:ファイルシステムをストレージデバイスではなくメモリ上に存在するtmpfs上に作ることによって、このコマンド発行に対するI/O処理の影響を無くしています
*6:slabアロケータを使うのはkmalloc()だけではないのですが、それについては割愛します
*7:たとえば前者から後者の間に16コミットあれば、最初は8個目のコミットで問題が起きるか確認して、問題が起きなければ次は12個目のコミットで確認…というように容疑者を一度に半分づつ減らしていく
