himainu氏のところで紹介されている私のパッチを説明する。
http://marc.info/?l=selinux&m=118956715414494&w=2
SELinuxのAVCミスヒット時のパフォーマンスを改善するものである。
AVCミスヒット時、SELinuxはセキュリティポリシーを探索してAVCエントリを作成する必要がある。この時、タイプに付与された属性(attribute)が持っているルールを計算する必要があった。
その実装は以下の通り
ebitmap_for_each_bit(..., i) {
if (!ebitmap_node_get_bit(..., i))
continue;
ebitmap_for_each_bit(..., j) {
if (!ebitmap_node_get_bit(..., j))
continue;
:
(AVCエントリの計算)
:
}
}ebitmap_for_each_bit()というのは、ebitmapに含まれるbitの最小〜最大までを繰り返すイテレータ。そしてebitmap_node_get_bit()は、引数で指定されたビットが立っているかどうかを調べる関数。
ebitmapの構造上、'&'演算一発ではこれを確認できないため、ebitmap_node_get_bit()は"やや重い処理"となる。
そして、イテレータを二重に重ねているということは、この関数の実行をポリシーに含まれる属性の数の二乗回だけ行わなければならないということになり、結果、AVCミスヒット時の処理はかなり重いものとなる。
私のパッチでは ebitmap_for_each_positive_bit() というイテレータを用意した。これは 1 のビットに対応する場合のみループを実施するというもので、内部的には find_next_bit() という最終的には専用の機械語命令に展開される関数を呼び出している。
このマクロの適用によって、ebitmap_node_get_bit()の呼び出し回数が減ることに加えて、ebitmapの探索自体も高速になる。(そもそも32bitのプロセッサだから、アルゴリズムを工夫すれば32bit同時に処理できるべき！)
その結果が以下の通り。
selinux-2.6 selinux-2.6-ebitmap AVG: 22.763 [s] 8.750 [s] STD: 0.265 0.019 ------------------------------------------ 1st: 22.558 [s] 8.786 [s] 2nd: 22.458 [s] 8.750 [s] 3rd: 22.478 [s] 8.754 [s] 4th: 22.724 [s] 8.745 [s] 5th: 22.918 [s] 8.748 [s] 6th: 22.905 [s] 8.764 [s] 7th: 23.238 [s] 8.726 [s] 8th: 22.822 [s] 8.729 [s]
わざと AVC ミスヒットを起こすような負荷パターンを与えてみたが、この結果は最悪時の応答性能の改善を示している。特に組込みLinuxの分野では、OSのリアルタイム性が要求されるため、カーネル内部での busy loop 状態は避けるべきで、これはかなり良好な結果なのではないかと思う。
パッチの行数がやや増えてしまったが、これは u64 ⇔ unsigned long に変換せねばならない部分が結構あったため。しかし、本質的なアイデアの部分はそう多くない。
