謎のコンテナランタイムlinuxd

はじめに

本記事はLinux Advent Calenda 2018の最終日、25日目の記事です。

ここ数年、一つないし複数のプロセスから成るアプリをコンテナと呼ばれるサンドボックス上で動かすのが流行っています。このときアプリを動かす実行環境のことをコンテナランタイムと呼びます。このコンテナランタイムには例えば次のようなものがあります。

  • runC: アプリをそれぞれ別々のnamespace上で実行。カーネルは全アプリで共有。世間的に「コンテナ」というと今はだいたいこれを指す
  • Kata Containers: アプリを個々のアプリ専用VM上で実行
  • gVisor: アプリをユーザ空間で独自実装されたLinuxカーネルのサブセット上で実行

f:id:satoru_takeuchi:20200329054809j:plain

本記事は最近筆者が気になっているlinuxdというコンテナランタイムについて簡単に紹介したいと思います。

何がどう"謎"なのか

タイトルに「謎の」と書いているのは、後述の通り世の中に情報がほとんど出回っていないからです。私の知る限り、linuxdが初めて表に出たのは2018年のLinuxCon Chinaであり、そのあとOpen Source Summit 2018 North Americaでも発表があったようです。スライドはこちら。で、いまのところ世に出ている情報は悲しいことにこれだけです。

スライドにも細かい実装の話は載っていないので、本記事は「たぶんこうではなかろうか」という推測をもとに書いていることをあらかじめお断りしておきます。「いやその解釈はおかしいだろう」「たぶんほんとはこうなっているはず」などの突っ込みお待ちしています。

概要

linuxdとはユーザ空間で動作するlinuxカーネル上でアプリを動かすコンテナランタイムです。将来的にはOCIやCRIに準拠したランタイムになる予定だそうです。

f:id:satoru_takeuchi:20200329054825j:plain

上記のさまざまなコンテナランタイムのうち、ユーザ空間で動作するカーネル上で実行するという意味で、linuxdはgVisorに似ています。これ以降は主にgVisorとの比較という形でlinuxdがどのようなものなのかについて述べます。

linuxdはgViorとは異なりカーネルは独自実装のものではなく、linuxそのものに少し手を加えたものです。どのような手を加えているかについては次節で述べます。

linuxdの作者はユーザ空間カーネルを独自実装ではなくlinuxベースにする利点として、次のようなものを挙げています。

  • 成熟したlinuxのコードベースを利用できる
  • 現在はupstreamのlinuxに独自パッチを当てているが、将来的にupstreamに取り込まれれば以後のカーネルアップデートに自動的に追従できる
  • アプリを一切改変せずに動作させられる。gVisorはlinuxの全機能をサポートしているわけではないのでアプリを動作させるためには改変が必要なことがある

linuxカーネルの変更点

linuxdにおいて動かすユーザ空間カーネルはupstreamのlinuxカーネルそのものではなく、それに3つの変更を加えたものです。以下それぞれについて説明します。

アドレス空間操作処理

ユーザ空間カーネル上でアプリを動かすためには、ユーザ空間カーネルがアプリ内の個々のプロセスのためにアドレス空間を作る必要があります。かつ、その後アドレス空間に変更があったときにもユーザ空間カーネルが処理してやる必要があります。詳細は省略しますが、gVisorのようにupstreamカーネルの機能を使ってこれを実現しようとすると、これらの処理のためにユーザ空間カーネルからカーネルに対して大量のシステムコールを発行する必要があります。

これに対してlinuxdにおいては、上記のようなアドレス空間の操作専用システムコールをupstreamカーネルに追加しました。これによってアドレス空間の操作にかかるコストを削減しました

システムコールや例外の横取り処理

ユーザ空間カーネル上でプロセスを動かすためには、アプリ内の各プロセスの動作中にシステムコールの発行や例外が発生したことをユーザ空間カーネルが認識し、処理してやる必要があります。gVisorではこれをptraceシステムコールを使ったカーネル処理の横取りによって実現しています1。ところがこれには複雑な処理が必要なため、非常に低速です。

注意: 本節のここからの部分は冒頭にリンクを張った"Containerize Linux Kernel"というスライドの中の以下の部分から推測しました。

update code on the path for syscalls and exceptions for the new ASes

これに対してlinuxdにおいては、ホストカーネルのシステムコールの入り口部分に変更を加えていると考えられます。ホストカーネル上で直接動作しているプロセスがシステムコールを発行したときは従来通りの動作をします。その一方でlinuxdから立ち上げられたプロセスの場合は、linuxdのユーザ空間カーネルにシステムコールの処理を委託します。linuxdは委託されたシステムコールを実行した上でプロセスに制御を戻します。

この一連の処理はptraceを使う場合に比べて少ない手番で済むので高速、ということでしょう。

ユーザ空間カーネルとホストカーネル間のインターフェース

ユーザ空間カーネルはシステムコールを処理する必要ができたときに、処理が自分自身の中で完結できればそうするのですが、そうではないとき、たとえば物理ハードウェアにアクセスしなければいけないときなどにはホストカーネルに処理を委託します。

本節のここからの部分は元スライドの以下の部分を元に推測しました。

Reduced Attack Surface to Host Kernel - No Hardware ABIs - Limited linux ABI with host kernel, less than 30 sysalls or even less - Limited usage of host kernel functionalities

linuxdにおいてはホストカーネルのうち、ハードウェアを操作する部分はホストカーネルに処理を委託するシステムコール発行に置き換えていると考えられます。このとき使用するシステムコールは必要最小限にしておき、かつ、使っていないシステムコールはseccompによって実行不能にしておくことによって堅牢性を高めているはずです。

おわりに

ユーザ空間でlinuxカーネルを動かすというlinuxdのアプローチはなかなかアツいアイデアに見えます。ただし、Linuxには遥か昔からこれとかなり似たUser Mode Linux(UML)という機能がありました。UMLについてはスライドの中でも次のように言及がありました。

Its experimental stage has started for about 1 year, spawning PoC product based on UML showed the approach workable.

個人的にはUMLの性能向上および拡張ではなくlinuxdという新規のプロジェクトにしている理由がよくわかりませんでしたが、これまでに述べた通り謎が多いので実際のところはよくわかりません。近いうちに上記のような私の理解を発表者にして確認してみようと思っています。回答をもらえて、かつ、公開可能であれば本記事を更新する予定です。

  1. 正確にはptraceシステムコールではなく仮想化技術を使って同等のことをする方法もgVisorは提供していますが、ここでは割愛します↩

OSSの継続性を推測する基準の例

はじめに

みなさんは自分が欲しい機能を持ったOSSを見つけたものの「使っているうちに開発が止まったりしないだろうか」と思ったことはないでしょうか。あるいは似たような複数のOSSのうちのどれを採用するかという選択を迫られて悩んだ経験はないでしょうか。筆者はどちらもよくあります。本記事はこのようなときOSSの継続性が高いかどうか(言い方を変えると今後も開発が続きそうかどうか)を推測するための筆者の基準についていくつか紹介します。題材とするのはgolangのデバッガとして知られる二つのソフトウェア、delveとgodebugです。

delveとgodebugはそれぞれ2014年5月と2015年という比較的近い時期に誕生した(initial commitされた)、golangで作られたプログラムのデバッガです。ソースコードの規模も数千行と、それほど違いはありません。現在前者は勢いよく開発中、後者はREADMEに「非推奨。今後開発は続かないからかわりにdelveを使ってね(意訳)」と書いてあるという違いがあります。これから両者のgitリポジトリから得られる情報をもとに、それぞれが誕生してから現在までにどのように変化してきたのかを紹介しつつ、上記の基準を紹介いたします。

コミット数の推移

OSSの勢いを測る指標のひとつにコミット数の推移があります。単に絶対数というわけではなく推移というのがポイントです。

delveがinitial commitされた2014年5月から2018年8月までの2つのプロジェクトのコミット数の推移を次に示します。

f:id:satoru_takeuchi:20200329054632p:plain

delveは誕生時から現在にかけて開発が絶え間なく続いていることがわかります。このようなOSSは継続性が高いと期待できるため、採用しやすいと筆者は考えています。

godebugについては誕生から数か月間は一時的にdelveよりもコミット数が多いことがありましたが、すぐ順番が入れ替わってからその後は勢いを取り戻すことはなく2015年の後半以降はほぼ開店休業状態になってしまいました。このようなOSSを選ぶのは今後の機能追加もバグ修正も期待できないため、採用するリスクが高いです。実際に、久しぶりにコミットした2017年には上記のREADMEの「delveを使ってね」という文言を追加しています。

なおコミット数はあくまで目安なので、複数のOSSから1つを選択する場合にコミット数の多少の違いを気にして「このOSSが一番コミット数多いので採用！」とするのは早急です。とくに2つのソフトウェアのソース規模が違う場合はコミット数を単純比較しても意味がないです。

コミッタ数の推移

コミット数だけではなくOSSの開発にかかわっているコミッタ数の推移も重要な指標です。以下にコミット数の推移と同期間におけるそれぞれのOSSについてのコミッタ数を示します。

f:id:satoru_takeuchi:20200329054642p:plain

delveは定期的に複数人がコミットしているのに対してgodebugはオリジナル作者がほとんど一人で頑張っているということがわかります。一人での開発はどうしても多人数開発の場合に比べて人的資源の問題で開発速度が遅くなりがちです。さらに作者が飽きたり、あるいは他のことで忙しくなるなどの理由によって開発を継続できなくなると、そのOSSの開発そのものが止まる可能性もあります。仮にコミット数が多くてもコミッタ数が少ないOSSは相対的に将来開発を継続できなくなるリスクが高いと筆者は考えます。

その他の観点

delveやgodebugは該当しませんが、大手の会社が資本を投入しているか、開発に参加しているか(コミッタのメールアドレスを見ればわかる)」というのも継続性を推測するのに重要な要素です。他にもいろいろあるのですが、全部書いていたらきりがないのでこのあたりでやめておきます。

おわりに

本記事を通じて「OSSの継続性を推測するにはこういう観点があるのか」ということがなんとなくわかっていただければ幸いです。

なお、ここまで主にユーザからの視点で記載してきましたが、自分が使いたいOSSの開発を継続するためにはみなさん自身ができる範囲でいいのでそのOSSのコミュニティになんらかの貢献(issueの発行、コードやドキュメントの提供)をするのがとても重要です。実際に、重要かつユーザが多いものの資金難や開発者が少ないことによって継続の危機にあるOSSはいくつもあります。

Linuxカーネルに関する独自コードをメンテナンスするコスト

はじめに

Linuxカーネル(以下カーネル)に機能を追加する、あるいはバグを修正する自作コードには次の2つの種類があります。

これらの変更を長期間メンテナンスするには次の方法があります。

  • Linux開発コミュニティに働きかけて独自コードを公式のmainlineと呼ばれるツリーにコードをマージする
  • 独自コードを自分自身で管理して、mainlineカーネルの新バージョンが出るたびに追従する(後述)

本記事は前者の方法に比べて後者の方法をとった場合に必要なメンテナンスコストについて述べます。本記事の表題にはlinuxと書いていますが、linuxと似たようなドラスティックな変更(後述)を是とするソフトウェアすべてに当てはまる話なのでlinuxの開発には関係ないかたにも役立つ話かと思います。

独自カーネルモジュールを作る場合の追従コスト

昨日書いたエントリで述べたように、カーネルは外部インターフェース(ユーザ空間とのインターフェース)は基本的には変えませんが、内部インターフェースは変わることがままあります。インターフェースを変更するときはmainlineにマージされれているコードについては、インターフェースを変更した人やサブシステムメンテナなど1が責任を持って新しいインターフェースに置き換えます。

このときmainlineにマージされていないコードに対する配慮はありません。したがって、ある時点のカーネルバージョンに対応する独自カーネルモジュールを作っており、それが問題なくビルドできていたとしても、そのモジュールが使っているインターフェースがその後に変更された場合、それはビルドできなくなります。このため独自カーネルモジュールを新しいバージョンに追従するためのコストがかかります。さらに独自モジュールのコード量は時を経るほど増えていくので、一回の追従に必要なコストは増える一方です。

f:id:satoru_takeuchi:20200329054309j:plain

複数バージョンに対してモジュールをメンテナンスしなければいけない場合は、古いバージョンのモジュールに対して新しいバージョンの変更をバックポートしないといけないので、どんどん追従が困難になっていきます。

f:id:satoru_takeuchi:20200329054319j:plain

これを続けると、自作コードの量(ここではパッチの数)が増えるにつれて、および、追従すべきカーネルの数が増えるごとに追従コストが爆発的に増えていくことがわかっていただけると思います。

カーネル本体を変更する場合の追従コスト

カーネル本体を変更する場合は前節において説明した独自カーネルモジュールのメンテナンスにかかるコストに加えて、別のコストもかかります。カーネル内インターフェースが変わらなくても、関数内の処理論理が書き換えられることがあります。このときは既存カーネルに対する変更を新しい処理論理に合わせて変更する必要があります*1。

f:id:satoru_takeuchi:20200329054331j:plain

複数のmainlineカーネルバージョンに対して変更部分を管理しなくていけない場合、上記のコストに加えて、古いバージョンに対して新しいカーネルに入っている重大バグの修正パッチもバックポートし続ける必要があります。これらの修正はパッチ数でいうと1バージョンごとに数百、数千個にも及びますので、大量の人的資源が無いと現実的ではありません。

f:id:satoru_takeuchi:20200329054413j:plain

バックポートのコストはstableカーネルというものを使えば減らせます。linuxには各バージョンのmainlineカーネルに対して、より新しいカーネルからの重大なバグ修正パッチをバックポートしたstableカーネルがしばらくの間提供されます。これを利用すれば、古いカーネルについては新しいstableカーネルが出るたびに、その上に独自コードのパッチを(必要であれば変更した上で)当てたものを使えば、相当バックポートコストが減らせます((stableカーネルに似たような長期間サポートされるカーネルは他にも色々ありますが、それらについての説明は省略します)。ただしそれもstableカーネルが出る期間が終わるまでです。それ以降は自分でなんとかする必要があります。

f:id:satoru_takeuchi:20200329054503j:plain

上記の図の中では、見やすさのために新しいカーネルからのバックポートのためのコード量を少な目に表現していますが、実際には独自コードよりもはるかに大きいことにご注意ください。

バックポートコストを減らすためには、stableカーネル以外にも、ある時点でのstableカーネルをもとにディストリビューション独自の変更をしたディストリビューションカーネルをベースにするという方法もあります。ただしここで一点注意があります。ディストリビューションが提供するカーネルは独自パッチを当てるとサポート対象にならなくなります。商用ディストリビューションのサポートを受けているかたは、独自コードを使いたければmainlineに取り込んだ上でディストリビュータに取り込み依頼をしなければなりません。

mainlineにマージすべきか否か

これまでの記述によって「では必ずmainlineにマージすべきなの？」と思うかもしれませんが、必ずしもそうとも限りません。前述の追従コストに比べてmainline化のコストが高くなるような場合は、あえて独自管理をすることもありえます。その他にも、コードを一般公開したくないなどの理由によってmainline化をしない選択をする場合もあります。

おわりに

本記事で書いたことは一度体験してみないとなかなかわからないため、これまでに様々な組織が独自管理を選択した後に収集がつかない状態になった結果、独自コードのmainline化を基本方針にするようになりました。本記事を読むことによって、みなさまが先人達の轍を踏むことなく独自コードの将来的な管理コストについて学んでいただければ幸いです。

  1. サブシステムメンテナがみなさん自身なら自分で書き換えなければいけないこともありますが…↩

*1:場合によっては当該パッチが不要になることもあります

Linuxのプロセススケジューラから見たSocionext SC2A11

はじめに

本記事はSocionext SC2A11のキャッシュメモリ構成の続きです。今回はLinuxのプロセススケジューラにはこのCPUがどのように見えているかについて調べました。

まずは前提知識としてLinuxカーネルのプロセススケジューラに存在するロードバランサという機能について説明します。その後に、ロードバランサからSC2A11がどのように見えているのかについて記載します。

ロードバランサ

システムに複数の論理CPU(1つのコア、あるいはSMT(1)が有効なら1つのスレッド)が存在する場合、Linuxのプロセススケジューラの中のロードバランサという機能がそれぞれの論理CPU上のプロセス数を平均化しようとします2。

たとえば1ソケット4コア、つまり4論理CPUのシステムにおいて実行可能プロセスが4つ存在する場合、1つの論理CPUに4つのプロセスが偏るようなことはなく、それぞれの論理CPUにプロセスが1つづつ割り振られます。一時的にそのようなことになる可能性はありますが、すぐに解消されます。

f:id:satoru_takeuchi:20200329053857p:plain

ロードバランサが単純に全論理CPUを平等に扱って負荷分散すると問題が発生します。たとえば2コア2プロセスの4論理CPUシステムについて考えてみましょう。論理CPU0,1と2と3がそれぞれ同じコア内の2スレッドとします。このとき実行可能プロセスが2つあるとすると、論理CPU0と1にプロセスが割り振られて、2と3がアイドルという状況が考えられます。

ペアになっているスレッドはほとんどのハードウェア資源を共有するため、現実的なワークロードの場合、2つのスレッド上に両方プロセスが動作している場合の性能は片方のスレッドにだけプロセスが存在する場合の高々1.5倍程度です。したがって、この場合は論理CPU0と1のいずれかに1つのプロセスを、論理CPU1と2のいずれかに1つのプロセスを割り振るほうがCPU資源を有効に使えます。

f:id:satoru_takeuchi:20200329053908p:plain

ロードバランサはCPU資源を有効に使うためにハードウェアから与えられた情報をもとにして論理CPUの階層構造を作り出し、上の階層から下の階層に順番に負荷分散します。それぞれの階層のことをスケジューラドメインと呼びます。たとえば前述の2コア2スレッドのシステムの場合は

  1. まずは上層のスケジューラドメインにおいて2コア間のプロセス数を平均化する
  2. 続いて下層のスケジューラドメインにおいて1コア内の2スレッド間でプロセス数を平均化する

という処理論理になっています。スケジューラドメインの階層構造は/proc/schedstatを見ればわかります。詳細については次節において述べます。

SC2A11の場合

SC2A11の/proc/schedstatの中身は次のようになっていました。

$ cat /proc/schedstat
cpu0 0 0 0 0 0 0 40778266780070 212490834550 257123
domain0 000003 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
cpu1 0 0 0 0 0 0 6518877752440 6168684830 155606
domain0 000003 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
cpu2 0 0 0 0 0 0 2042515035170 7070977990 189374
domain0 00000c 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
...
domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
cpu22 0 0 0 0 0 0 777618304410 8670056290 155964
domain0 c00000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
cpu23 0 0 0 0 0 0 803551513420 8844408870 165495
domain0 c00000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
domain1 ffffff 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
$

ここでは論理CPUごとに自身が属するスケジューラドメインについての情報が出力されます。各ドメインはdomain<階層番号>で表現されます。階層番号が大きいほど上の階層であることを示します。domainの右にある数値が、当該スケジューラドメインに属する論理CPUの一覧を示すビットマスクです。

上記の出力によって次のことがわかります。

  • スケジューラドメインは2階層ある
  • 階層0のスケジューラドメインは2つの論理CPU間で負荷分散する
  • 階層1のスケジューラドメインは12個ある階層0のスケジューラドメイン間で負荷分散する

続いてこの階層はどこから得られたものなのかを調査しました。arm64アーキテクチャにおけるスケジューラドメインの階層構造は最大3階層です。

  • CPUコアを複数まとめたクラスタ間で負荷分散
  • クラスタ内のコア(最大4個)間で負荷分散
  • コア内のスレッド間で負荷分散

この階層構造を作っているのがarch/arm64/kernel/topology.c内のコードです。ここで作成した情報は/sys/firmware/devicetree/base/cpus/cpu-map以下を見ればわかります。SC2A11の場合はcpu-mapディレクトリの下に12個のcluster<クラスタ番号>ファイル、そのまた下にcore<クラスタ内のコア番号>というディレクトリが存在します。つまりSC2A11は24個のコアが2個づつのコアから成る12個のクラスタによって構成されていることがわかりました。ちなみに1つのクラスタを構成する2つのコアは前回の記事においてL2キャッシュを共有していることがわかっています。

なお、このマシンは該当しませんが、SMT機能があるCPUの場合はcoreディレクトリの下に、さらにthread<コア内のスレッド番号>というディレクトリができるようです。

おわりに

次の記事はSocionext SC0FQAA-BはNUMAか否かです。

  1. Intelの場合はハイパースレッドという機能名です↩

  2. nice値やスケジューリングクラス、CPU affinityが絡んでくると話はこの限りではありませんが、ここではそれらについれは割愛↩

Socionext SC2A11のキャッシュメモリ構成の推測

はじめに

本記事はARM v8 アーキテクチャのネイティブな開発環境を提供するSC0FQAA-Bに搭載されているSocionext SC2A11 (24コア)のキャッシュメモリがそれぞれどのコア間で共有されているかを調べた結果をまとめた記事です。

なぜそんなことをしたかというと、SC2A11のカタログにはL1dが32KB, L2が256KB, L3が4MBということは書いてあったのですが、それぞれの共有関係については記載がなかったからです。公式サイトからたどれるその他ドキュメントにも同様に記載がありませんでした。

資料請求のフォームがあったのでそこから仕様書をもらって確認するという方法がありましたが

  • 個人ユーザが「キャッシュメモリの情報を知りたかったから」という理由で資料をもらえる気がしない
  • できたとしても面倒そうだし、時間もかかりそう

という理由により、実験によって情報を得ることにしました。

ちなみに実験に使ったマシンは自分で買ったわけではなく、東大PFLabが買ったもの同研究室のご厚意によって借りたものです。某SNSでこのキャッシュの疑問についてブツブツつぶやいていたら、PFLabでこのマシンをセットアップしたlivaさんがよきに計らってくれました。livaさんとPFLabには厚く御礼申し上げます。

調査結果

キャッシュメモリは恐らく次のような構成になっていることがわかりました。

名前 合計サイズ[KB] 共有関係 サイズ/コア[KB]
L1d 32 全コア独立 32
L2 256 2コアごとに共有 128
l3 4096 全コアで共有 約170

(2018/3/16追記) 数日前、このマシン用のDevice Treeにキャッシュメモリ構成に関する情報を追加するパッチが投稿されていることをMasami Hiramatsuさんに教えていただきました。パッチの内容によると筆者の推測は正しかったようです。なお、このパッチはすでにマージされたので、いずれファームウェアのバージョンアップによってキャッシュメモリの情報が正しくlinuxから取得できるようになりそうです。

sysfsからの情報採取

カーネルが初期化時にハードウェアからキャッシュメモリの構成を得ている場合は/sys/devices/system/cpu/cpu/cache以下からその情報を得られます1。このマシンにおいて同じファイルを探そうとしましたが、見つかりませんでした。

dmesgを見たところ、起動中に次のようなメッセージが出力されていました。

# dmesg
...
[    2.582856] cacheinfo: Unable to detect cache hierarchy for CPU 0
...

これはlinuxカーネルのソースコードでいうと以下の部分に該当します。

...
static int detect_cache_attributes(unsigned int cpu)
{
        int ret;

        if (init_cache_level(cpu) || !cache_leaves(cpu))
                return -ENOENT;

        per_cpu_cacheinfo(cpu) = kcalloc(cache_leaves(cpu),
                                         sizeof(struct cacheinfo), GFP_KERNEL);
        if (per_cpu_cacheinfo(cpu) == NULL)
                return -ENOMEM;

        ret = populate_cache_leaves(cpu);
        if (ret)
                goto free_ci;
        /*                                                                                                                                                                                            * For systems using DT for cache hierarchy, of_node and shared_cpu_map                                                                                                                       * will be set up here only if they are not populated already                                                                                                                                 */
        ret = cache_shared_cpu_map_setup(cpu);
        if (ret) {
                pr_warn("Unable to detect cache hierarchy for CPU %d\n", cpu); ... ★
                goto free_ci;
        }

        cache_override_properties(cpu);
        return 0;

free_ci:
        free_cache_attributes(cpu);
        return ret;
}
...

どうやらcache_shared_cpu_map_setup()が失敗したようです。この原因が次のうちどれなのかはわかっていません。

  • 全アーキテクチャ共有コード(drivers/base/cacheinfo.cあたり)
  • arm64のコード(arch/arm64/kernel/cacheinfo.cあたり)
  • このマシン用のDevice Tree(/sys/firmware/devicetree以下にマップされている)
  • その他

ここでこれ以上深堀りはしたくなかったので、次に示す実験によるアプローチによってキャッシュメモリ構成を推測することにしました。

実験

実験のコンセプトは次の通りです。

  • コア0上で所定サイズのバッファにアクセスし続けるプログラム(memory_loadプログラム)を動かす
  • コア0~23のいずれかの上で、所定サイズのバッファ(memory_loadプログラムのものとは別)に所定の回数アクセスすることによってアクセス速度を計測するプログラム(cacheプログラム)を動かす
  • memory_loadプログラムのバッファサイズを(a) L1よりやや小さな値(30[KB])、(b) L2よりやや小さな値(500[KB])、(c) L3 よりやや小さな値(4000[KB])にする。これによって次のことが言える
  • a) cacheプログラムのバッファサイズL1以下における性能が劣化した場合、2つのプログラムが動作しているコア間ではL1キャッシュを共有している
  • b) 同バッファサイズがL2以下における性能が劣化した場合、2つのプログラムが動作しているコア間ではL2キャッシュを共有している
  • c) 同バッファサイズがL3以下における性能が劣化した場合、2つのプログラムが動作しているコア間ではL3キャッシュを共有している

2つのプログラムのソースを示します。

#include <unistd.h>
#include <sys/mman.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <err.h>

#define CACHE_LINE_SIZE 64

int main(int argc, char *argv[])
{
    char *progname;
    progname = argv[0];

    if (argc != 2) {
        fprintf(stderr, "usage: %s <size[KB]>\n", progname);
        exit(EXIT_FAILURE);
    }

    register int size;
    size = atoi(argv[1]) * 1024;
    if (!size) {
        fprintf(stderr, "size should be >= 1: %d\n", size);
        exit(EXIT_FAILURE);
    }

    char *buffer;
    buffer = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (buffer == (void *) -1)
        err(EXIT_FAILURE, "mmap() failed");

        struct timespec before, after;

    clock_gettime(CLOCK_MONOTONIC, &before);

    int i;
    for (;;) {
        long j;
        for (j = 0; j < size; j += CACHE_LINE_SIZE)
            buffer[j] = 0;
    }

    if (munmap(buffer, size) == -1)
        err(EXIT_FAILURE, "munmap() failed");
    exit(EXIT_SUCCESS);
}
#include <unistd.h>
#include <sys/mman.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <err.h>

#define CACHE_LINE_SIZE 64
#define NLOOP       (64*1024*1024)

#define NSECS_PER_SEC   1000000000UL

static inline long diff_nsec(struct timespec before, struct timespec after)
{
        return ((after.tv_sec * NSECS_PER_SEC + after.tv_nsec)
                - (before.tv_sec * NSECS_PER_SEC + before.tv_nsec));
}

int main(int argc, char *argv[])
{
    char *progname;
    progname = argv[0];

    if (argc != 2) {
        fprintf(stderr, "usage: %s <size[KB]>\n", progname);
        exit(EXIT_FAILURE);
    }

    register int size;
    size = atoi(argv[1]) * 1024;
    if (!size) {
        fprintf(stderr, "size should be >= 1: %d\n", size);
        exit(EXIT_FAILURE);
    }

    char *buffer;
    buffer = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (buffer == (void *) -1)
        err(EXIT_FAILURE, "mmap() failed");

        struct timespec before, after;

    clock_gettime(CLOCK_MONOTONIC, &before);

    int i;
    for (i = 0; i < NLOOP / (size / CACHE_LINE_SIZE); i++) {
        long j;
        for (j = 0; j < size; j += CACHE_LINE_SIZE)
            buffer[j] = 0;
    }

        clock_gettime(CLOCK_MONOTONIC, &after);

    printf("%f\n", (double)diff_nsec(before, after) / NLOOP);
    
    if (munmap(buffer, size) == -1)
        err(EXIT_FAILURE, "munmap() failed");
    exit(EXIT_SUCCESS);
}

それぞれ次のようにビルドします。

$ cc -O3 -o memory_load memory_load.c
$ cc -O3 -o cache cache.c

memory_loadプログラムを所定のCPU上で動かすときは次のようにします。

$ taskset -c <CPU番号> ./memory_load <バッファサイズ [KB]>

cacheプログラムを所定のCPU上で動かすときは次のようにします。

$ taskset -c <CPU番号> ./cache <バッファサイズ [KB]>

リファレンスとなるデータの採取

まずはすべてのデータの比較対象となる、負荷をまったくかけない状態の性能を計りました。その結果を以下に示します。

$ for i in 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 ; do taskset -c 0 ./cache $i ; done
0.494395338
0.4878244995
0.7931622984
0.849168839
0.8938277609
0.9555984775
1.041136652
1.064321914
1.069313969
1.158684927
1.505872599
1.577874511
$

コマンド実行結果の数値の単位はナノ秒です。これをグラフにすると次のようになります。x軸もy軸も対数なので見かたに注意してください。

f:id:satoru_takeuchi:20200329053503p:plain

おおよそL1(25 [KB]), L2(28 [KB]), L3(212 [KB])を境界として性能が悪くなってゆくことがわかります。

実験結果

L1の共有範囲

memory_loadのバッファサイズがL1よりやや小さな値(30KB)場合のデータをもとにしたグラフを以下に示します。

f:id:satoru_takeuchi:20200329053515p:plain

memory_loadプログラムとcacheプログラムを同じコア(コア0)上で動かした場合のみ性能が悪く、その他は同程度の性能となりました。ごちゃごちゃしていて見づらいので、

  • memory_loadプログラムを動かさない場合(リファレンス性能)
  • cacheプログラムをコア0上で動かした場合,
  • 同、コア1上で動かした場合

というデータのみを抽出したグラフを以下に示します。

f:id:satoru_takeuchi:20200329053526p:plain

コア0上でmemory_loadプログラムによってL1キャッシュをほとんど使っても他のコアにおける性能がほぼ変わらないことから、コア0とコア1~23はキャッシュを共有していないことがわかりました。

なお、cacheプログラムをコア0上で動かした場合の性能が悪いのは、2つのプログラムがCPU時間を分け合っているせいでしょう。

L2の共有範囲

memory_loadのバッファサイズがL2よりやや小さな値(500KB)にした場合のデータをもとにしたグラフを以下に示します。ここでcacheプログラムをコア2~23で動かした場合のデータはほぼ同じだったので、

  • memory_loadプログラムを動かさない場合(リファレンス性能)
  • cacheプログラムをコア0上で動かした場合,
  • 同、コア1上で動かした場合
  • 同、コア2上で動かした場合

というデータのみを抽出しています。

f:id:satoru_takeuchi:20200329053540p:plain

cacheプログラムをコア1上で動かした場合にバッファサイズがL1のサイズ~L2のサイズあたりで性能劣化していることから、コア0とコア1はL2キャッシュを共有していると考えられます。

L3の共有範囲

memory_loadのバッファサイズがL3よりやや小さな値(4000 KB)にした場合のデータをもとにしたグラフを以下に示します。ここでcacheプログラムをコア2~23で動かした場合のデータはほぼ同じだったので、

  • memory_loadプログラムを動かさない場合(リファレンス性能)
  • cacheプログラムをコア0上で動かした場合,
  • 同、コア1上で動かした場合
  • 同、コア2上で動かした場合

というデータのみを抽出しています。

f:id:satoru_takeuchi:20200329053549p:plain

cacheプログラムをコア2上で動かした場合にバッファサイズがL2のサイズ~L3のサイズあたりで性能劣化していることから、コア0とコア2(および3~23)はL3キャッシュを共有していると考えられます。

おわりに

今後も本マシンの色々なデータをとっていきたいと思います。バッファサイズをL3のサイズを超える16MBにしてmemory_loadプログラムを動かしたところ、コア0とL2を共有するコア1上でcacheプログラムを動かした場合の性能が上がったという謎現象(L2を共有していないかのような振舞いをする)が発生しました。

f:id:satoru_takeuchi:20200329053603p:plain

これが気になっているので最初に調査するかもしれませんし、気が変わってI/O性能測定などの全然違うことをするかもしれません。

(2018/3/13追記) 結局はさらに気が変わってSC2A11がプロセススケジューラからどう見えるかという観点で調査しました。

  1. lstopoコマンドやlscpuコマンドによって出力されるキャッシュメモリに関する情報もこれが情報源です↩

ソートの計算量と現実のプログラム

ソートアルゴリズムについての小ネタ。「ソートは迷わずクイックソート」と言われることがよくありますが1、場合によってはそれが最適ではないこともあるという話。ここではクイックソートと挿入ソートを比較します。

O-記法で書くとクイックソートの平均計算量はO(n*log(n))で、単純な挿入ソートのそれはO(n^2)なので、見かけ上は前者のほうが速そうなのです。ただし、あくまでこの記法はnが無限に近づいたときの振舞いについて述べているだけなので、現実的なプログラムでは必ずしもクイックソートのほうが速いというわけではないです。

次のような仕様のプログラムで実際に両者の速度を比較してみましょう。

  • 所定の下の整数要素を持つ配列をソートして、その所要時間出力する
  • 第一引数(len): 要素数
  • 第二引数(type): アルゴリズムの種類。'i'が挿入ソート。'q'がクイックソート。

この仕様を実装したのが以下のsortプログラムです。

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

#define NSECS_PER_MSEC 1000000UL
#define NSECS_PER_SEC 1000000000UL

static void insertion_sort(int *a, int len)
{
        int i, tmp;
        for (i = 1; i < len; i++) {
                tmp = a[i];
                if (a[i - 1] > tmp) {
                        int j;
                        j = i;
                        do {
                                a[j] = a[j - 1];
                                j--;
                        } while (j > 0 && a[j - 1] > tmp);
                        a[j] = tmp;
                }
        }
}

static inline long diff_nsec(struct timespec before, struct timespec after)
{
        return ((after.tv_sec * NSECS_PER_SEC + after.tv_nsec)
                - (before.tv_sec * NSECS_PER_SEC + before.tv_nsec));

}

static void prepare_data(int *a, int len)
{
        int i;
        for (i = 0; i < len; i++)
                a[i] = rand();
}

static int comp(const void *a, const void *b)
{
        return *((int *)a) - *((int *)b);
}

static char *progname;

int main(int argc, char *argv[])
{
        progname = argv[0];

        if (argc < 3) {
                fprintf(stderr, "usage: %s <len> <i|q>\n", progname);
                exit(EXIT_FAILURE);
        }

        int len = atoi(argv[1]);

        char type = argv[2][0];

        if (!((type == 'i') || (type == 'q'))) {
                fprintf(stderr, "%s: type should be 'i or q'\n", progname);
                exit(EXIT_FAILURE);
        }

        int *a;
        a = malloc(len * sizeof(int));
        prepare_data(a, len);

        struct timespec before, after;
        if (type == 'i') {
                clock_gettime(CLOCK_MONOTONIC, &before);
                insertion_sort(a, len);
                clock_gettime(CLOCK_MONOTONIC, &after);
        } else {
                clock_gettime(CLOCK_MONOTONIC, &before);
                qsort(a, len, sizeof(int), comp);
                clock_gettime(CLOCK_MONOTONIC, &after);
        }

        printf("%lu\n", diff_nsec(before, after));

        exit(EXIT_SUCCESS);
}

ビルド方法は次の通り。

$ CFLAGS=-O3 make sort
$

このプログラムを次のようなパラメタを使って実行しました。

パラメタ 値
第一引数(len) 20, 1, 2, ..., 15
第二引数(type) i, q

結果を以下のグラフにプロットしました。x軸は2len、y軸はlog(所要時間)なのに注意してください。

f:id:satoru_takeuchi:20200329053129p:plain

lenが大きくなっていくと確かにクイックソートのほうが速くなってゆき、その差は大きくなるばかりです。しかしlenが小さいとき、ここでは2^8(=128)あたりまでは挿入ソートのほうが速いことがわかります。これはクイックソートのほうが挿入ソートに比べて複雑な処理をしているためです。したがって、通常はクイックソートを使っていれば悪いようにはなりませんが、プログラムをカリカリにチューニングしたいとき、かつ、lenがそれほど大きくならないとわかっているときは挿入ソートを使って高速化に挑戦してみるのも一つの手です。ただし、「早すぎる最適化」という言葉にもある通り、最初からこの手の細かいチューニングをする必要はないでしょう。

最後に一点。上記のような理由もあって、本記事で作成したプログラムでも使っているglibcのqsort()関数は、ある程度小さなlen(<=MAX_THRESH)に対しては内部的に挿入ソートを使っています。他にもこのような実装になっている実装は山ほどあります。興味のあるかたは色々なクイックソートの実装を見てみるとよいでしょう。

  1. とくにスクリプト言語の場合はソートアルゴリズムを自分で選択することも少ないかもしれません↩

カーネルモジュール作成によるlinuxカーネル開発入門 - 第五回 排他制御

前回作成したスタックは、手元の端末でみなさんが対話的に操作しているうちは何も問題が起きません。しかし、このスタックを複数の処理が同時に操作した場合は問題が発生します。今回は、前回作成したスタックにどのような問題が存在しているのか、および、それを排他制御という仕組みによって解決する方法について述べます。

まずは今回用いるスタック作成モジュール用のソースを次に示します。前回作成したlist2.cのものに加えて、スタックのサイズを最大10に制限しています。

#include <linux/module.h>
#include <linux/slab.h>
#include <linux/debugfs.h>

MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("Satoru Takeuchi");
MODULE_DESCRIPTION("a example of mutual exclusion by using mutex");

struct mystack_entry {
    struct list_head list;
    int n;
};

#define MYSTACK_MAX_LEN 10

static LIST_HEAD(mystack);
static int mystack_len;

static void mystack_push(int n) {
    struct mystack_entry *e;

    if (mystack_len >= MYSTACK_MAX_LEN) {
        return;
    }
    e = kmalloc(sizeof(*e), GFP_KERNEL);
    INIT_LIST_HEAD(&e->list);
    e->n = n;
    list_add(&e->list, &mystack);
    ++mystack_len;
}

static int mystack_pop(int *np) {
    struct mystack_entry *e;

    if (list_empty(&mystack)) {
        return -1;
    }

    e = list_first_entry(&mystack, struct mystack_entry, list);
    if (np != NULL)
        *np = e->n;
    list_del(&e->list);
    --mystack_len;
    kfree(e);

    return 0;
}

static void mystack_clean_out(void) {
    while (!list_empty(&mystack)) {
        mystack_pop(NULL);
        --mystack_len;
    }
}

static struct dentry *mylist_dir;

static struct dentry *showfile;
static struct dentry *pushfile;
static struct dentry *popfile;

static char testbuf[1024];

static ssize_t show_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
    char *bufp = testbuf;
    size_t remain = sizeof(testbuf);
    struct mystack_entry *e;
    size_t l;
    ssize_t ret;

    if (list_empty(&mystack)) {
        ret = simple_read_from_buffer(buf, len, ppos, "\n", 1);
        return ret;
    }

    list_for_each_entry(e, &mystack, list) {
        int n;

        n = snprintf(bufp, remain, "%d ", e->n);
        if (n == 0)
            break;
        bufp += n;
        remain -= n;
    }
    l = strlen(testbuf);
    testbuf[l - 1] = '\n';
    ret =  simple_read_from_buffer(buf, len, ppos, testbuf, l);

    return ret;
}

static ssize_t push_write(struct file *f, const char __user *buf, size_t len, loff_t *ppos)
{
    ssize_t ret;
    int n;

    ret = simple_write_to_buffer(testbuf, sizeof(testbuf), ppos, buf, len);
    if (ret < 0)
        return ret;
    sscanf(testbuf, "%20d", &n);
    mystack_push(n);

    return ret;
}

static ssize_t pop_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
    int n;
    ssize_t ret;
    
    if (*ppos || mystack_pop(&n) == -1) {
        return 0;
    }
    snprintf(testbuf, sizeof(testbuf), "%d\n", n);
    ret = simple_read_from_buffer(buf, len, ppos, testbuf, strlen(testbuf));
    return ret;
}

static struct file_operations show_fops = {
    .owner = THIS_MODULE,
    .read = show_read,
};

static struct file_operations push_fops = {
    .owner = THIS_MODULE,
    .write = push_write,
};

static struct file_operations pop_fops = {
    .owner = THIS_MODULE,
    .read = pop_read,
};

static int mymodule_init(void)
{
    mylist_dir = debugfs_create_dir("mystack", NULL);
    if (!mylist_dir)
        return -ENOMEM;
    showfile = debugfs_create_file("show", 0400, mylist_dir, NULL, &show_fops);
    if (!showfile)
        goto fail;
    pushfile = debugfs_create_file("push", 0200, mylist_dir, NULL, &push_fops);
    if (!pushfile)
        goto fail;
    popfile = debugfs_create_file("pop", 0400, mylist_dir, NULL, &pop_fops);
    if (!popfile)
        goto fail;

    return 0;

fail:
    debugfs_remove_recursive(mylist_dir);
    return -ENOMEM;
}

static void mymodule_exit(void)
{
    debugfs_remove_recursive(mylist_dir);
    mystack_clean_out();
}

module_init(mymodule_init);
module_exit(mymodule_exit);

次に示すのは、大量のプロセスが同時に、かつ適当にスタックを操作するという拷問プログラムです。

#!/bin/bash

TOPDIR=/sys/kernel/debug/mystack

for ((i=0;j<10000;j++)) ; do
    echo 0 >${TOPDIR}/push &
    cat ${TOPDIR}/show >/dev/null &
    cat ${TOPDIR}/pop >/dev/null &
done

別の端末上でVMのシリアルコンソールに接続します。

shell-session:
$ virsh console elkdat_ktest
Connected to domain elkdat_ktest
Escape character is ^]


Ubuntu 16.04.1 LTS packer-qemu ttyS0

packer-qemu login:

lock1.koをロードした状態で、拷問プログラムを動作させます。

...
root@packer-qemu:/home/vagrant# insmod /vagrant/list2.ko
root@packer-qemu:/home/vagrant# /vagrant/lock-torture
root@packer-qemu:/home/vagrant#
...

このとき次のようなメッセージがシリアルコンソール上に大量に表示されます。

...
[ 2186.660837] BUG: unable to handle kernel NULL pointer dereference at 0000000000000010
[ 2186.661890] IP: [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1]
[ 2186.662618] PGD 1cce9067 [ 2186.662958] PUD 1cce8067 
PMD 0 [ 2186.663438] 
[ 2186.663643] Oops: 0000 [#1] SMP
[ 2186.664082] Modules linked in: lock1(O) crct10dif_pclmul crc32_pclmul ppdev aesni_intel aes_x86_64 glue_helper lrw gf128mul ablk_helper cryptd input_leds joydev serio_raw parport_pc parport mac_hid i2c_piix4 sunrpc autofs4 cirrus drm_kms_helper syscopyarea sysfillrect sysimgblt fb_sys_fops psmouse floppy ttm drm pata_acpi [last unloaded: lock1]
[ 2186.668308] CPU: 1 PID: 7243 Comm: cat Tainted: G           O    4.9.0-ktest #1
[ 2186.669215] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS Ubuntu-1.8.2-1ubuntu1 04/01/2014
[ 2186.670379] task: ffff8d3dd7c563c0 task.stack: ffffa0f3c1534000
[ 2186.671118] RIP: 0010:[<ffffffffc02910d5>]  [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1]
[ 2186.672246] RSP: 0018:ffffa0f3c1537dd0  EFLAGS: 00010203
[ 2186.672981] RAX: 0000000000000002 RBX: 00000000000003fe RCX: 0000000000000000
[ 2186.673801] RDX: 0000000000000001 RSI: ffffffffc0292029 RDI: 0000000000000000
[ 2186.674598] RBP: ffffa0f3c1537e00 R08: 0000000000000000 R09: 0000000000000000
[ 2186.675396] R10: 000000000000037b R11: ffffffffc0293681 R12: 0000000000020000
[ 2186.676193] R13: ffffa0f3c1537f18 R14: 0000000000000000 R15: ffffffffc0293682
[ 2186.677004] FS:  00007f94815eb700(0000) GS:ffff8d3ddfd00000(0000) knlGS:0000000000000000
[ 2186.677910] CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 2186.678566] CR2: 0000000000000010 CR3: 000000001ba56000 CR4: 00000000000406e0
[ 2186.679360] Stack:
[ 2186.679640]  00007f94815c9000 ffff8d3ddd2e7d80 0000000000000001 ffffffffc0293200
[ 2186.680561]  ffff8d3dde0add00 0000000000020000 ffffa0f3c1537e48 ffffffff893deeb4
[ 2186.681554]  00007f94815c9000 ffffa0f3c1537f18 ffff8d3dde0add00 ffffa0f3c1537f18
[ 2186.682540] Call Trace:
[ 2186.682930]  [<ffffffff893deeb4>] full_proxy_read+0x54/0x90
[ 2186.683636]  [<ffffffff8922bd27>] __vfs_read+0x37/0x150
[ 2186.684292]  [<ffffffff894bea7b>] ? security_file_permission+0x9b/0xc0
[ 2186.685037]  [<ffffffff8922cf03>] vfs_read+0x93/0x130
[ 2186.685659]  [<ffffffff8922e405>] SyS_read+0x55/0xc0
[ 2186.686239]  [<ffffffff8906c807>] ? trace_do_page_fault+0x37/0xe0
[ 2186.686933]  [<ffffffff899a24bb>] entry_SYSCALL_64_fastpath+0x1e/0xad
[ 2186.687658] Code: bb 00 04 00 00 49 c7 c7 80 36 29 c0 49 81 fe f0 32 29 c0 75 16 eb 2e 4d 8b 36 48 98 49 01 c7 48 29 c3 49 81 fe f0 32 29 c0 74 1a <41> 8b 4e 10 48 c7 c2 26 20 29 c0 48 89 de 4c 89 ff e8 15 1e 2d 
[ 2186.690753] RIP  [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1]
[ 2186.691475]  RSP <ffffa0f3c1537dd0>
[ 2186.691913] CR2: 0000000000000010
[ 2186.695397] ---[ end trace 83771c8afec0d8dc ]---
....

上記ログの中でとくに注目すべきは次の部分です。

...
[ 2186.660837] BUG: unable to handle kernel NULL pointer dereference at 0000000000000010    # ... (1)
[ 2186.661890] IP: [<ffffffffc02910d5>] show_read+0x65/0x110 [lock1]              # ... (2)
...
[ 2186.682540] Call Trace:
[ 2186.682930]  [<ffffffff893deeb4>] full_proxy_read+0x54/0x90
[ 2186.683636]  [<ffffffff8922bd27>] __vfs_read+0x37/0x150
[ 2186.684292]  [<ffffffff894bea7b>] ? security_file_permission+0x9b/0xc0
[ 2186.685037]  [<ffffffff8922cf03>] vfs_read+0x93/0x130
[ 2186.685659]  [<ffffffff8922e405>] SyS_read+0x55/0xc0                       # ... (3)
[ 2186.686239]  [<ffffffff8906c807>] ? trace_do_page_fault+0x37/0xe0
[ 2186.686933]  [<ffffffff899a24bb>] entry_SYSCALL_64_fastpath+0x1e/0xad
...

ここから次のことがわかります。

  • read()システムコールを発行した延長で(ログ内の(2)の部分)、show_read()関数の実行中に問題が発生した(ログ内の(2)の部分)
  • カーネルがNULLポインタにアクセスした(ログ内の(1)の部分)にアクセスした

このようなことが起きた理由は、lock1.koが提供しているスタックの実装に使っているmystackに複数の処理が同時にアクセスしたものの、mystackは同時アクセスに耐えない作りになっていることです。これが具体的にどういうことなのかを、これから明らかにしています。

空のmystackにa, bという2つの要素をpushする場合を考えます。このとき、カーネルの中では次に示すlist_add()が二回呼ばれます1。

...
static inline void list_add(struct list_head *new, struct list_head *head)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next, new;
}
...
static list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
...

まずは正しく動作する、2つのpush処理A, Bが順番に動くケースについて記載します。コードで表現すると、次のようになります。

処理A         処理B
==================================================
mystack->prev = a;
a->next = mystack;
a->prev = mystack;
mystack->next, a;
            a->prev = b;
            b->next = a;
            b->prev = mystack;
            mystack->next, b;

図で書くと次のようになります。

f:id:satoru_takeuchi:20200329052929p:plain

ややわかりにくいですが、こちらは正しく動作しています。mystackからnextをたどっていくとmystack->b->a->mystackと循環しており、かつ、prevをたどっていくと、mystack->a->b->mystackと循環していることがわかります。

続いて2つのpushが同時に動くケースについて記載します。コードで表現すると、次のようになります。

処理A         処理B
=================================================
mystack->prev = a;
            mystack->prev = b;
a->next = mystack;
            b->next = mystack;
a->prev = mystack;
            b->prev = mystack;
mystack->next, a;
            mystack->next, b;

図で書くと次のようになります。

f:id:satoru_takeuchi:20200329052943p:plain

これはmystack内のリンク関係が無茶苦茶になっています。mystackにはbしか繋がっていない状態です。mystackからnextをたどっていくと、mystack->b->mystackと循環しており、かつ、prevをたどっていくと、mystack->b->mystackと循環しています。その一方でaはprevもnextもmystackを指しており、自分ではmystackに繋がっているつもりになっています。この後何が起きても不思議では無い状態です。拷問プログラムの動作時において、この問題はNULLポインタへのアクセスという障害として顕在化しました。

「同時に複数の処理が動く」と一口に言っても、その組み合わせは様々です。その上、list2.koではlist_add()とlist_del()以外にもlist_empty()などの他の処理も同時多発的に動きますので、拷問プログラムにおいて実際にどのように問題が顕在化するのかは毎回異なります。したがって、みなさんの環境では、冒頭で示したものとは異なるスタックトレースが見えるかもしれません。

ここでの問題の本質は、mystackに同時にアクセスしてしまったことです。これを避けるために、クリティカルセクションと呼ばれる特定のコード領域には、ただ1つの処理しか同時に侵入できないようにします。これを排他制御と呼びます(ようやく今回のタイトルの文言が出てきました)。

排他制御をする方法にはいろいろありますが、ここではmutextという方法を使います。mutexを使うには、次のような手順を踏みます。

  1. クリティカルセクションを定義する。ここではmystackを操作する箇所全てが該当する。それに加えて、testbufを操作する箇所も含める。これまで述べなかったが、testbufも複数処理から同時に更新されるとユーザからの入出力値が不正なものになる可能性がある。
  2. クリティカルセクションを保護するためのmutex(struct mutex型の変数)を定義する。ここではmystack_mutexとする。
  3. クリティカルセクションの前後に必ずmutexを獲得/開放する。

1は済んでいますから、2以降をコードに落としましょう。まずは2のmutexの定義から。

static DEFINE_MUTEX(mystack_mutex);

続いて3のmutexを使用するコードを書きます。例としてmystackに新要素をpushするpush_write()関数内を、mutexを用いて排他制御するように変更します。

...
static ssize_t push_write(struct file *f, const char __user *buf, size_t len, loff_t *ppos)
{
    ssize_t ret;
    int n;

    mutex_lock(&mystack_mutex);
    ret = simple_write_to_buffer(testbuf, sizeof(testbuf), ppos, buf, len);
    if (ret < 0) {
        mutex_unlock(&mystack_mutex);
        return ret;
    }
    sscanf(testbuf, "%20d", &n);
    mystack_push(n);
    mutex_unlock(&mystack_mutex);

    return ret;
}
...

クリティカルセクションに入る前にmutex_lock()によってmutextを獲得し、そこを抜けたらmutex_unlock()によってmutexを開放しています。mutex_lock()の中では

  1. mutexが未獲得なら、獲得して先に進む
  2. mutexが獲得済みならmutexが開放されるまで待つ

という処理をします。これによって、複数の処理が同時にクリティカルセクションに入れなくなります。例えばリストへの同時アクセスだけに注目してみると、処理の流れが次のようになるためにmystackの破壊は防げます。

処理A             処理B
==========================================================================
mutex_lock(&mystack_mutex); #   mutex獲得
mystack->prev = a;
                mutex_lock(mystack_mutex);
a->next = mystack;       ... # ここからmutex獲得待ち
a->prev = mystack;       ...
mystack->next, a;        ...
mutex_unlock(&mystack_mutex);   ... # ここでmutex獲得
                mystack->prev = b;
                b->next = mystack;
                b->prev = mystack;
                mystack->next, b;
                mutex_unlock(&mystack_mutex);

mutexを用いてlock1.cを書き直したものが次のリストです。

#include <linux/module.h>
#include <linux/slab.h>
#include <linux/debugfs.h>

MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("Satoru Takeuchi");
MODULE_DESCRIPTION("a example of mutual exclusion by using mutex");

struct mystack_entry {
    struct list_head list;
    int n;
};

#define MYSTACK_MAX_LEN 10

static LIST_HEAD(mystack);
static int mystack_len;
static DEFINE_MUTEX(mystack_mutex);

static void mystack_push(int n) {
    struct mystack_entry *e;

    if (mystack_len >= MYSTACK_MAX_LEN) {
        return;
    }
    e = kmalloc(sizeof(*e), GFP_KERNEL);
    INIT_LIST_HEAD(&e->list);
    e->n = n;
    list_add(&e->list, &mystack);
    ++mystack_len;
}

static int mystack_pop(int *np) {
    struct mystack_entry *e;

    if (list_empty(&mystack)) {
        return -1;
    }

    e = list_first_entry(&mystack, struct mystack_entry, list);
    if (np != NULL)
        *np = e->n;
    list_del(&e->list);
    --mystack_len;
    kfree(e);

    return 0;
}

static void mystack_clean_out(void) {
    mutex_lock(&mystack_mutex);
    while (!list_empty(&mystack)) {
        mystack_pop(NULL);
        --mystack_len;
    }
    mutex_unlock(&mystack_mutex);
}

static struct dentry *mylist_dir;

static struct dentry *showfile;
static struct dentry *pushfile;
static struct dentry *popfile;

static char testbuf[1024];

static ssize_t show_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
    char *bufp = testbuf;
    size_t remain = sizeof(testbuf);
    struct mystack_entry *e;
    size_t l;
    ssize_t ret;

    mutex_lock(&mystack_mutex);
    if (list_empty(&mystack)) {
        ret = simple_read_from_buffer(buf, len, ppos, "\n", 1);
        mutex_unlock(&mystack_mutex);
        return ret;
    }

    list_for_each_entry(e, &mystack, list) {
        int n;

        n = snprintf(bufp, remain, "%d ", e->n);
        if (n == 0)
            break;
        bufp += n;
        remain -= n;
    }
    l = strlen(testbuf);
    testbuf[l - 1] = '\n';
    ret =  simple_read_from_buffer(buf, len, ppos, testbuf, l);
    mutex_unlock(&mystack_mutex);

    return ret;
}

static ssize_t push_write(struct file *f, const char __user *buf, size_t len, loff_t *ppos)
{
    ssize_t ret;
    int n;

    mutex_lock(&mystack_mutex);
    ret = simple_write_to_buffer(testbuf, sizeof(testbuf), ppos, buf, len);
    if (ret < 0) {
        mutex_unlock(&mystack_mutex);
        return ret;
    }
    sscanf(testbuf, "%20d", &n);
    mystack_push(n);
    mutex_unlock(&mystack_mutex);

    return ret;
}

static ssize_t pop_read(struct file *f, char __user *buf, size_t len, loff_t *ppos)
{
    int n;
    ssize_t ret;
    
    mutex_lock(&mystack_mutex);
    if (*ppos || mystack_pop(&n) == -1) {
        mutex_unlock(&mystack_mutex);
        return 0;
    }
    snprintf(testbuf, sizeof(testbuf), "%d\n", n);
    ret = simple_read_from_buffer(buf, len, ppos, testbuf, strlen(testbuf));
    mutex_unlock(&mystack_mutex);
    return ret;
}

static struct file_operations show_fops = {
    .owner = THIS_MODULE,
    .read = show_read,
};

static struct file_operations push_fops = {
    .owner = THIS_MODULE,
    .write = push_write,
};

static struct file_operations pop_fops = {
    .owner = THIS_MODULE,
    .read = pop_read,
};

static int mymodule_init(void)
{
    mylist_dir = debugfs_create_dir("mystack", NULL);
    if (!mylist_dir)
        return -ENOMEM;
    showfile = debugfs_create_file("show", 0400, mylist_dir, NULL, &show_fops);
    if (!showfile)
        goto fail;
    pushfile = debugfs_create_file("push", 0200, mylist_dir, NULL, &push_fops);
    if (!pushfile)
        goto fail;
    popfile = debugfs_create_file("pop", 0400, mylist_dir, NULL, &pop_fops);
    if (!popfile)
        goto fail;

    return 0;

fail:
    debugfs_remove_recursive(mylist_dir);
    return -ENOMEM;
}

static void mymodule_exit(void)
{
    debugfs_remove_recursive(mylist_dir);
    mystack_clean_out();
}

module_init(mymodule_init);
module_exit(mymodule_exit);

これをロードした後にlock-tortureを実行しても問題は発生しません。試してみてください。

演習問題

  • 第三回の debugfs3.c にも排他制御にまつわる問題があります。これについて、何が問題なのかを明らかにして、mutexを用いて問題が発生しないようにする。

おわりに

排他制御にはmutex以外にも様々な種類がありますが、すべてを紹介するにはまだ早いので、まずはここまで。ここでは、mutexの概念と、それを使用するために必要な手順だけを覚えていただければよいです。次回は多分デバイスドライバもどきを作成する予定です。

本章で作成したソースと同じものをexample/module/lock以下に配置しています。

  1. 実際のものはデバッグ用のコードが入っていたりしてもう少し複雑ですが、ここでは簡略化しています。↩