メモリ削減パッチ再提出

SELinux

また提出しなおし。
ひたすらベンチマークとった。
http://marc.info/?l=selinux&m=118767082011094&w=2
さらにハッシュスロットへらして、300ｋ超のメモリを節約した。

ハッシュ関数変えたけど、ハッシュテーブルの利用状況は良くとも、
ハッシュ関数が遅くなるほうが上回り、
全体として遅くなるので、変えないほうがいいという結論。

ちなみに、測定の中で、
ポリシーのサイズが小さくなると、
security_compute_avが遅くなっているように見える現象を発見した。
KaiGaiさんに聞いたら、アトリビュートが怪しいのではとのこと。
security_compute_avから呼ばれる関数に以下のような処理がある。

331         sattr = &policydb.type_attr_map[scontext->type - 1];
332         tattr = &policydb.type_attr_map[tcontext->type - 1];
333         ebitmap_for_each_bit(sattr, snode, i) {
334                 if (!ebitmap_node_get_bit(snode, i))
335                         continue;
336                 ebitmap_for_each_bit(tattr, tnode, j) {
337                         if (!ebitmap_node_get_bit(tnode, j))
338                                 continue;
339                         avkey.source_type = i + 1;
340                         avkey.target_type = j + 1;
341                         for (node = avtab_search_node(&policydb.te_avtab, &avkey);
　　　＜略＞
350                         }

つまり、ドメイン側とタイプ側に付与されたアトリビュート全ての組合せに対して、
avtab_search_nodeを呼んでいる。
調べてみると、
strictポリシでは、例えばkernel_tには8個アトリビュートが付与されているのに対し、
targetedでは、kernel_tに24個も。
遅くなるわけだ。

お、早速返事が返ってきた。
概ねよさそうだ。あとはコーディングスタイルの問題っぽい。
そういえば、カーネルコーディングのお作法はよく知らないなぁ。勉強しなきゃ（汗

SELinuxは重いのか？

SELinux

avtab関連のベンチマークを取るついでに、
AVCのベンチマークも取っている。

AVCの効果

その中で分かったのは、AVC(Access Vector Cache)の効果。
SELinuxで、アクセス制御のチェックをするときは、
1) AVCを見に行く
2) AVCにないときは、security_compute_avで、ポリシーファイルを探索
となっている。

測ってみた感じでは、
2)のポリシ探索処理にかかる時間が100だとすると、
1)にかかる時間はわずか1/100!
AVCのヒット率だが、
手元のF7マシンだと、
# cat /selinux/avc/cache_stats
lookups hits misses allocations reclaims frees
905705 901458 4247 4247 3728 3747
なので、
ヒット率：99.53%
ミス率：0.47%
ぐらい。
てことは、
平均時間は、AVCにヒットした場合を１として、
1*0.9953 + 100 * 0.47/100 = 1.465
か。
ミス率をもっと減らせれば、早くできるなぁ。

AVCをチェックする処理

SELinuxのパーミッションチェックは、以下の関数。

905 int avc_has_perm(u32 ssid, u32 tsid, u16 tclass,
906                  u32 requested, struct avc_audit_data *auditdata)
907 {
908         struct av_decision avd;
909         int rc;
910 
911         rc = avc_has_perm_noaudit(ssid, tsid, tclass, requested, &avd);
912         avc_audit(ssid, tsid, tclass, requested, &avd, rc, auditdata);
913         return rc;
914 }
915

avc_has_perm_noauditが、アクセスチェック関数。
avc_auditはログを取る関数

847 int avc_has_perm_noaudit(u32 ssid, u32 tsid,
848                          u16 tclass, u32 requested,
849                          struct av_decision *avd)
850 {
851         struct avc_node *node;
852         struct avc_entry entry, *p_ae;
853         int rc = 0;
854         u32 denied;
855 
856         rcu_read_lock();
857 
858         node = avc_lookup(ssid, tsid, tclass, requested);
            ★↑ここで、AVCを見に行っている★
859         if (!node) {
860                 rcu_read_unlock();
861                 rc = security_compute_av(ssid,tsid,tclass,requested,&entry.avd);
　　　　　　★AVCをミスした場合は、↑でポリシファイルを見に行っている★
862                 if (rc)
863                         goto out;
864                 rcu_read_lock();
865                 node = avc_insert(ssid,tsid,tclass,&entry);
866         }


avc_lookup関数だが、以下。

401 static struct avc_node *avc_lookup(u32 ssid, u32 tsid, u16 tclass, u32 requested)
402 {
403         struct avc_node *node;
404 
405         avc_cache_stats_incr(lookups);
406         node = avc_search_node(ssid, tsid, tclass);
407 
408         if (node && ((node->ae.avd.decided & requested) == requested)) {
409                 avc_cache_stats_incr(hits);
410                 goto out;
411         }
412 
413         node = NULL;
414         avc_cache_stats_incr(misses);
415 out:
416         return node;
417 }

360 static inline struct avc_node *avc_search_node(u32 ssid, u32 tsid, u16 tclass)
361 {
362         struct avc_node *node, *ret = NULL;
363         int hvalue;
364 
365         hvalue = avc_hash(ssid, tsid, tclass);
366         list_for_each_entry_rcu(node, &avc_cache.slots[hvalue], list) {
367                 if (ssid == node->ae.ssid &&
368                     tclass == node->ae.tclass &&
369                     tsid == node->ae.tsid) {
370                         ret = node;
371                         break;
372                 }
373         }
374 
375         if (ret == NULL) {
376                 /* cache miss */
377                 goto out;
378         }
379 
380         /* cache hit */
381         if (atomic_read(&ret->ae.used) != 1)
382                 atomic_set(&ret->ae.used, 1);
383 out:
384         return ret;
385 }

処理の内容だが、
hvalue = avc_hash(ssid, tsid, tclass);
のハッシュ関数の計算と、
ハッシュチェーンを探索、単純な比較演算ぐらい。
avc_hashは、
return (ssid ^ (tsid<<2) ^ (tclass<<4)) & (AVC_CACHE_SLOTS - 1);
という単純なビット演算。

やってることは軽そう。SELinuxのコア部分は、簡単な処理しかしてませんので、
たぶん、重くないです。

さらに軽くするためのポイントを考えてみると。。。
avc_auditの呼び出しは、全部の場合呼ぶ必要ないだろうというのと、
avc_cache_stats_incr(lookups);
が普通はいらないのでselinuxfsで切れるようにすることか。