[PATCH]SELinux performance improvement by RCU (Re: RCU issue with SELinux)

[Kaigai Kohei]

Hi Stephen, thanks for your comments.

> > Please wait for a patch, thanks.
> 
> Thanks for working on this.  Could you also supply updated performance
> data when you have a newer patch?  Thanks.

I fixed the take-3 patch according to your and Paul's suggestions.

The attached take-4 patches replace the avc_lock in security/selinux/avc.c
by the lock-less read access with RCU.

The patches consist of three parts as follows:
[1] selinux.rcu-2.6.8.1-take4.patch
     removed the spinlock (avc_lock) from security/selinux/avc.c,
     and applied RCU-approach for the lock-less read access to the AVC.
[2] list_replace_rcu-2.6.8.1.patch
     added list_replace_rcu() to include/linux/list.h for the atomic updating
     operations according to RCU-model.
[3] atomic_inc_return-2.6.8.1.patch
     added atomic_inc_return() and atomic_dec_return() to i386, x86_64 and ARM
     architectures. It's necessary for the [1] patch.


[Changes by these patches from original implementation]
- Some of the data structures are re-defined.
  (struct avc_entry/struct avc_node/struct avc_cache)
- The direct references from security-private member in inode, task_struct and so on
  were removed, since these references prevent from applying RCU.
  Currently, avc_entry_ref is not used.
- The pre-allocation semantics of avc_node structure was replaced by kmalloc()
  on demand, since it's necessary for applying RCU.
  (The number of nodes is adjusted by AVC_CACHE_THRESHOLD, but it's not a hard limit.)
- avc_update_node() can return -ENOMEM when kmalloc() returns NULL.
  But this is not a significant problem, since the function is actually called
  by only avc_has_perm_noaudit() for the control of the flood of audit-logs.

Signed-off-by: KaiGai, Kohei <kaigai@xxxxxxxxxxxxx>
Signed-off-by: Takayoshi Kochi <t-kochi@xxxxxxxxxxxxx>

Thanks for all the comments and suggestions.


[Performance & Scalability results] --------------------------------------

2.6.8.1(disable/enable) : Original Stock Kernel
2.6.8.1.rwlock          : Improvement by rwlock(not disclosed)
2.6.8.1.rcu             : Improvement by RCU(attached take-4 patch)

o 500,000 times of write() syscall to the file on /dev/shm
 on Itanium2 x 1/2/4/8/16/32 + enough memory(needless to swap-out)
 *) The num of Processes equals the num of CPUs.
---------------- --1CPU--  --2CPU-- --4CPU-- -- 8CPU-- --16CPU-- --32CPU--
2.6.8.1(disable)   8.2959    8.0430   8.0158    8.0183    8.0146    8.0037
2.6.8.1(enable)   11.8427   14.0358  78.0957  319.0451 1322.0313  too long
2.6.8.1.rwlock    11.2485   13.8688  20.0100   49.0390   90.0200  177.0533
2.6.8.1.rcu       11.3754   11.2028  11.1743   11.1402   11.1216   11.2635
---------------- --------  -------- -------- --------- --------- ---------

o dbench (10 times mean results)
- Average[MB/s] -  -1proc- -2procs- -4procs-
2.6.8.1(disable)    247.43   473.11   891.51
2.6.8.1(enable)     218.99   434.97   761.06
2.6.8.1(+rwlock)    225.18   432.80   802.62
2.6.8.1(+RCU)       231.16   447.62   838.15
--------------------------------------------

o UNIX-bench

* INDEX value comparison ---------------------------------------------------
                                       2.6.8.1   2.6.8.1   2.6.8.1   2.6.8.1
                                     (Disable)  (Enable)  (rwlock)    (RCU) 
Dhrystone 2 using register variables    268.9     268.8     269.2     268.7 
Double-Precision Whetstone               94.2      94.2      94.2      94.2 
Execl Throughput                        388.3     379.0     377.8     377.0 
File Copy 1024 bufsize 2000 maxblocks   606.6     526.6     515.6     513.1 
File Copy 256 bufsize 500 maxblocks     508.9     417.0     410.4     402.9 
File Copy 4096 bufsize 8000 maxblocks   987.1     890.4     876.0     864.1 
Pipe Throughput                         525.1     406.4     404.5     356.2 
Process Creation                        321.2     317.8     315.9     316.5 
Shell Scripts (8 concurrent)           1312.8    1276.2    1278.8    1279.5 
System Call Overhead                    467.1     468.7     464.1     468.1 
                                    ========================================
     FINAL SCORE                        445.8     413.2     410.1     403.8 
----------------------------------------------------------------------------

--------
Kai Gai <kaigai@xxxxxxxxxxxxx>

Attachment: selinux.rcu-2.6.8.1-take4.patch
Description: Binary data

Attachment: atomic_inc_return-2.6.8.1.patch
Description: Binary data

Attachment: list_replace_rcu-2.6.8.1.patch
Description: Binary data