Lockless Kretprobeに学ぶ失敗例

今日はちょっと、Satさんの失敗プログラマに触発され、最近やった開発について失敗の気づきをメモしておこうと思います。C言語とアセンブラの知識が少しあれば、何をしているかは理解できると思います。

#Kretprobeとはなにか

KretprobeはLinuxカーネル内の関数のリターンをフックして、任意のユーザハンドラを呼び出す仕組みです。仕組みは簡単、対象の関数の先頭アドレスにソフトウェアブレークポイント（あるいはジャンプ命令）を設定し、そこで実行をフックして関数呼び出しのリターンアドレスを保持しているスタックやレジスタを改変し、こちらで用意したトランポリンアドレスに戻るようにします。
トランポリンアドレスでは（アーキテクチャ毎に実装は少し違うんだけど）またKprobeでフックするか、あるいはアセンブラコードでレジスタを退避してkretprobeのユーザハンドラを呼び出します。その後は何事もなかったかのように本来のリターンアドレスに戻るという仕組みです。

#開発の経緯と発見した失敗

##問題の報告

事の発端は、Linux-5.8上である操作をするとkretprobeが全く動かないという[報告](https://lkml.kernel.org/r/8816bdbbc55c4d2397e0b02aad2825d3@trendmicro.com)でした。詳細な再現方法と共に、bisectした結果も付いてきていたので非常に助かりました。

bisectで特定されたコードは、x86で「int3例外（ソフトウェアブレークポイント命令）を割り込みではなくNMIとして扱う」という変更でした。これ自体は悪い話ではなく、まあ確かにソフトウェアブレークポイント命令なんて回避できないのだから、それこそ何処にでも入り得る、例えばクリティカルセクションの中に入れたり、それこそNMIハンドラ内部に入れることも出来てしまう、確かにNMIの一種であると言えます。
（*NMI*：Non-Maskable Interrupt、割り込み禁止できない特殊な割り込みのこと。Watchdogやハードウェア的なエラーの検出などで使われる）

この変更で何が起きたのかと言うと、ざっくり言うと「デッドロック回避のためにINT3を使ったkretprobeが動かなくなってしまった」のです。わざわざINT3と前置きしたのは、通常のkretprobeは動いてしまっていたからです。実はx86などの一部のアーキテクチャでは、デフォルトでは関数のフックをソフトウェアブレークポイントではなくFtrace (Function tracer)で代用していたことと、さらにデフォルトでjump optimization（ソフトウェアブレークポイントをジャンプ命令で代用する）が有効になっていたため、この2つの仕組みを強制的にOFFにしないと、この現象は発生しなかったのです。このため、リリース前のテストでは発見できていませんでした。（ftraceはKconfigでオフに出来るものの、jump optimizationの無効化は実行時にsysctlを実行する必要がある）
本当に発見して報告してくれたトレンドマイクロのEddy Wuさんには感謝しかありません。

##問題の原因
何故これが起きたのか。元々kretprobeでは、内部でロック(spinlock)を使う際の問題として「kretprobeのクリティカルセクションに本当のNMIが割り込み、そのNMIハンドラで同じ関数が呼び出されたら、自分でdeadlockを起こしてしまう」ということは認識しており、kretprobeのスピンロック処理をする前に、in_nmi()という関数を利用して「もしNMIのコンテキストでkretprobeが呼び出されたら実行をキャンセルする」という仕組みが入っていました。
ところが、ところがですよ、このin_nmi()、仕組みとして先程の「NMIとして扱う」場合は常に真になってしまうのです。つまり、ftraceやjump optimizationが実行されたときはkretprobeは実行されるが、INT3の延長でハンドラが呼び出されると常にスキップされてしまう状態になっていました。

##失敗#1
そこでいろいろ調べると、実はこのin_nmi()自体不要なのでは？と[気が付きました](https://lkml.kernel.org/r/20200826190041.2d0ff0fbe154ba62163b0c00@kernel.org)。そもそもkprobesの外部の仕組みであるin_nmi()に依存するところでなんか駄目っぽいのですが、実はこのアドホックなin_nmi()チェックを追加したしばらく後に、もう一つ別のロック競合を起こす可能性がある場所が見つかりました。それで最終的にダミーのkprobe構造体(kprobe_busy)を作り、関数の戻りアドレスをフックしたkretprobeが行う処理の前後で「このCPUは（ダミーの）kprobe_busyが使用中ですよ」という宣言をする（実際にはper-cpu変数のcurrent_kprobeにkprobe_busyを突っ込んだ）パッチが追加されていたのです。
つまり、元々問題としていた「kretprobeのクリティカルセクションに本当のNMIが割り込み、そのNMIハンドラで同じ関数が呼び出されたら、自分でdeadlockを起こしてしまう」という問題は、このパッチによって解決されていたのでした。良かったよかった。

##失敗#2
（承前）とはならなかったのが２つ目の失敗です。これは歴史的な失敗なのですが、kretprobeを最初に実装した時に、なぜかそれほどアーキテクチャ依存でもない処理が、アーキテクチャ依存のソースファイル内部で実装されていました。これは初期のkprobesの開発が、ほぼほぼx86だけで進められていた（開発ツリーも-tipと呼ばれるx86のツリーだった）ため、他のアーキテクチャのコードレビューなどをほとんどしていなかったことが一端です。
他のアーキテクチャにkprobesを移植した人が、その時のx86のコードをコピペして再実装した結果、各アーキテクチャで微妙に異なる実装が残っていました。そして例のダミーのkprobe_busyを設定するコードは、x86だけで実装されていたのです・・・。つまり問題はx86だけで起きるけど実は前のパッチで修正されていたけどx86だけでしかそのパッチは実装されていなかったぜ！　あれ？解決してるんじゃないの？
いえいえ、実はin_nmi()のチェックはアーキテクチャ非依存のコードで実装されていました。つまり纏めると以下のようになります。

- in_nmi()チェック：全アーキテクチャで有効
- kprobe_busyによる排他：x86だけ有効
- int3がNMI化：x86だけの処理

ここでin_nmi()チェックだけを外すと、x86は良いですが他のアーキテクチャは保護されなくなってしまいます。つまり、in_nmi()チェックを外す前にkprobe_busyによる排他処理を他のアーキテクチャに導入する必要が出てきました。しかし当然ながら各アーキテクチャで実装コードが異なるため、単純に適用して回るわけにはいきません。というか二度手間ですしね。
最終的に、最も進んでいたx86のコードを元にアーキテクチャ非依存の汎用コードを作り、一旦不完全にコピペされていたアーキテクチャ依存のコードを全部消して汎用コードを呼び出すようにしました。
過去の怠惰の「つけ」って、本当に返さないといけないんですねえ（苦笑）。

##失敗#3
しかしこれで良いのかと思っていたら、まだこれからが本題でした。つまりLockless Kretprobeです。（前置きが長い）
上記の話がきっかけで、IntelのPeter Zijilstraさんから、そもそもkretprobeがkprobesの中でロックを取るのはおかしい、という[話が出ます](https://lkml.kernel.org/r/20200825120911.GX1362448@hirez.programming.kicks-ass.net)。確かに出来ればlocklessにしたいのですが、これは歴史的に、kretprobeの仕組みがLinuxカーネルに対して非侵襲かつメモリ消費を押さえるためにロックを必要としていました。
kretprobeが戻りアドレスをフックした後、正しい戻りアドレスを探し出すには、現在のタスク（スレッド）に紐付いたリストから探し出す必要があります。素直に実装すればtask構造体にリストを追加すれば良かったのですが、最初にkretprobeを実装した当時は非侵襲を意図しすぎたのか、kretprobe専用のハッシュリストを作り、task構造体のアドレスからハッシュ値を計算して、そのリストに正しい戻りアドレスを記録したkretprobe_instanceというオブジェクトを追加しています。このハッシュリストへの追加・削除は当然ながらスレッド間で競合しますから、アクセスにはロックを掛ける必要がありました。
また、カーネル上の様々な箇所（コンテキスト）からkretprobeが呼び出される可能性を考慮すると、このkretprobe_instanceオブジェクトは、最初の関数入り口をフックした場所ではメモリ確保できないことは明白です。このため、kretprobe_instanceオブジェクトは予め決められた数を作成し、kretprobeオブジェクトのリストに繋いでおく形になっています。つまり、ここでもリストのロックが必要になっているのです。
纏めるとkretprobeの実行手順は以下のようになります。

1. 関数入り口でkretprobeが呼び出される
2. **kretprobeをロック**し、kretprobeのリストからkretprobe_instanceを一つ取り出す
3. 戻りアドレスを改変し、正しい戻りアドレスをkretprobe_instanceに入れる
4. task構造体からハッシュ値を計算、**対象のハッシュリストをロック**し、kretprobe_instanceをつなぐ
5. 関数出口（リターン）でトランポリンアドレスに飛ぶ
6. task構造体からハッシュ値を計算、**対象のハッシュリストをロック**し、kretprobe_instanceを探す
7. 正しい戻りアドレスを取得し、kretprobeがあれば、kretprobeのハンドラを呼び出す
8. **kretprobeをロック**し、kretprobe_instanceをkretprobeに戻す。もしkretprobeがなければkretprobe_instanceを解放する。
9. 正しい戻りアドレスに飛ぶ

本来task構造体にリストをつなぐという実装になっていれば、ハッシュリストのロックの方は不要なはずです。
Linuxカーネルにはllist（lock-less NULL terminated single linked list）という単方向リスト構造体とメソッドが定義されており、これを使うことでいろいろ解決するのでは、というのが最初の提言でした。しかしllistはリストからの削除が重なった場合にはロックが必要という記述(linux/llist.h)があり、kretprobeから抜き出す場合のロックは依然として必要になります。（そもそもtask構造体に追加・削除するだけなら前述の通りロックはほぼ不要）

そこでPeterさんが取り上げたのが、lockless freelistという新しいリストの仕組みでした。これはCameronという方が[ブログで紹介していた](https://moodycamel.com/blog/2014/solving-the-aba-problem-for-lock-free-free-lists)ものを、PeterさんがLinuxカーネルに移植したものです。詳細はllistと合わせて別途記事にしようと思いますが、取り敢えず道具は揃ったように思えました。

##失敗#4
実はこの前に、もう一つ問題が残っていたのです。先程のkretprobeの実行手順#8で、「kretprobeがなければkretporbe_instanceを解放する」となっていたのですが、実はこれはNMIのコンテキストで呼び出された場合は問題になるのでした。Linuxカーネルのメモリ解放ルーチンkfree()は、かなり色んなコンテキストで呼び出すことが出来ます。しかしNMIのコンテキストでは他のkfree()の処理と競合する可能性があるため呼び出すことが出来ません。失敗#2を修正する際にin_nmi()のチェックを削除したことで、これは本質的に危険な処理になっていました。そこでkfree()の代わりにkfree_rcu()を使うことで、メモリ解放処理を遅延実行することにしました。

#lockless kretprobeの実装
こうして色々な失敗を修正し、[実装されたlockless kretprobe](https://lkml.kernel.org/r/159870598914.1229682.15230803449082078353.stgit@devnote2)は次のような処理になりました。完全にlocklessになっていますね。

1. 関数入り口でkretprobeが呼び出される
2. kretprobeのfreelistからkretprobe_instanceを一つ取り出す
3. 戻りアドレスを改変し、正しい戻りアドレスをkretprobe_instanceに入れる
4. Currentのtask構造体のllistにkretprobe_instanceをつなぐ
5. 関数出口（リターン）でトランポリンアドレスに飛ぶ
6. Currentのtask構造体のllistから、kretprobe_instanceを探す（実際には関数の呼び出し順にpushされているのをpopしていく）
7. 正しい戻りアドレスを取得し、kretprobeがあれば、kretprobeのハンドラを呼び出す
8. kretprobe_instanceをkretprobeのfreelistに戻す。もしkretprobeがなければcall_rcu()でkretprobe_instanceを解放する。
9. 正しい戻りアドレスに飛ぶ

##もう一つの改善
あれ？kfree_rcu()ではなかったの？という方、良い質問です。実は専用の解放用関数を呼び出しています。この背景には、実はもう一つ解決するべき課題があったのです。
問題はユーザが使い終わったkretprobeを削除しようとした時に発生します。kretprobeを削除しても、現在使用中のkretprobe_instanceは各スレッドのスタックを改変してしまっています。無理やりこのスタックを元に戻そうとすると、動いているスレッドを止めることになってしまい、非効率的です。このため、元のkretprobeではハッシュリストをロックして全部のkretprobe_instanceをなめ、削除しようとしているkretprobeのkretprobe_instanceが無効になったというフラグを付ける（実際にはkretprobeを指すポインタをNULLにする）処理をしていました。これは舐めるサイズが限られているハッシュリストだから出来たことです（それでもあまり嬉しくはない）。
失敗#3の修正でハッシュリストの代わりに各スレッドのリストに振り分けましたが、これと同じことをしようとすると全てのtask構造体を調べて回る必要があります。これでは動いているスレッドのtask構造体を調べるのに、ロックが必要になってしまいます。

そこで新たに、kretprobe_holderオブジェクトという「kretprobeオブジェクトのポインタを保持するオブジェクト」を[導入](https://lkml.kernel.org/r/159861781740.992023.4956784710984854658.stgit@devnote2)しました。このオブジェクトには予め「参照するkretprobe_instanceの数」で初期化された参照カウンタがついています。lockless kretprobeの実行手順#7と#8では、kretprobeがあるかどうかを調べるため、kretprobe_instanceオブジェクトからkretprobe_holderオブジェクトを取り出し、その中のkretprobeポインタの値を調べます。
kretprobeを削除するときには、このkretprobe_holderのポインタの値をNULLにしておきます。そうするとその後はどのスレッドでもkretprobeを参照できなくなります。その後、kretprobeのfreelistに残ったkretprobe_instanceの数だけkretprobe_holderの参照カウンタを減算し、0になればkretprobe_holderオブジェクトを削除します。
同様に実行手順#8からcall_rcu()を使って呼び出した関数でも、kretprobe_instanceオブジェクトを削除する前にkretprobe_holderの参照カウンタを1減らし、0になればkretprobe_holderオブジェクトを削除します。

この仕組みにより、全てのスレッドのtask構造体を調べて回る必要もなくなり、本当にkretprobeをlocklessにすることが出来ました。


##現状と未解決の問題
lockless kretprobeは現在tipツリーに半分ほど取り込まれているのですが、実はまだちょっとした問題があります。

###Linux 5.8の修正
失敗#2を乗り越えるためにかなり大掛かりにアーキテクチャ跨りでコードを修正したので、そのまま5.8カーネルにバックポートするかどうかがまだ決まっていません。（このままだと5.9もあやしい）最初に報告された課題はこの辺りのカーネルでは残ったままになるかも知れません。発現条件が決まっていて、LTSでもないからいいか、みたいな雰囲気になっているのですが、どうしても欲しい人はバックポート出来るように議論するしかないかも・・・。

###Kprobesとlockdep
また、これとは別に、kprobesのユーザハンドラでロックを取得するとlockdepに叱られるというlockdep側の[問題](https://lkml.kernel.org/r/20200909000923.54cca4fb530904c57e8ff529@kernel.org)も未修正な状況です。lockdepはデッドロックやABAロック競合の可能性を調べるための機能ですが、そのうちの一つに、通常コンテキストとNMIコンテキストで同じロックを利用した場合にエラーを出すという仕様があります。スピンロックは通常、割り込み禁止とセットにして使い、割り込みによってクリティカルセクション内で同じロックが取られるのを防ぎます。しかしNMIは割り込み禁止できないため、NMIコンテキストで同じロックを使うと、デッドロックを起こす可能性があるわけです。
ただしこれは実はfalse positiveなエラーです。というのは、kprobesは失敗#1で述べたとおり、per-cpu変数のcurrent_kprobeにkprobeオブジェクトがセットされている限り、ユーザハンドラは呼び出されずにスキップされます。つまりユーザハンドラはネストできないため、仮にkprobeがNMIコンテキストで呼び出されても、デッドロックを起こす可能性はありません。しかしlockdepはそのことを知らないため、デッドロックが起きる可能性があると警告を出してしまいます。