[patch] customizable AVTAB_HASH_BITS for embedded devices

[patch] customizable AVTAB_HASH_BITS for embedded devices

[Yuichi Nakamura]

Hi.

I am working to reduce memory usage of SELinux for embedded devices.
I would like to propose very small patch at first.
Thanks for advice > KaiGai-san .

1. Background 
* In avtab_init:
 h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
Number of hash table size is AVTAB_SIZE.

* In avtab.h
#define AVTAB_HASH_BITS 15
#define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
#define AVTAB_SIZE AVTAB_HASH_BUCKETS

AVTAB_SIZE is 2^15 = 32768

So 32768 entries are allocated for avtab, 
and 2 avtabs are used in policydb:
struct avtab te_avtab;
struct avtab te_cond_avtab;

If te rules are fewer than 32768,
unused entries are using memory.

In embedded devices, the rules tend to be fewer.
In my test system(SH architecture board), it is less than 10000 rules.

2. Patch
I made AVTAB_HASH_BITS customizable by Kconfig.
Allocated hash slots for avtab can be reduced by reducing AVTAB_HASH_BITS.

Attached  patch is for 2.6.22.
Then, I measured memory usage by /proc/memstat before/after tuning

* Memory usage: SELinux before loading policy.
2720k is used.

* Memory usage: SELinux after loading policy(about 8000 rules) before patch
+1068k increase

* Memory usage: SELinux after loading poilcy(about 8000 rules) after patch.
  configured AVTAB_HASH_BITS as "13" 
+876k increase
-> improved 192k

* Theoretical value:
- Before tuning: 
  Number of hashslot 2^15 * 2 
  Size of hash slot: 4 (sizeof(*(h->htable)))
  Memory usage = 2^15*2*4 = 262k

- After tuning: 
  Number of hash slot is 2^13 * 2, 
  and size of hash slot is 4 (sizeof(*(h->htable)))
  Memory usage = 2^13*2*4 = 65k 
  -> 197k should improve, this value is almost the same as measured value.

Following is a patch:

diff -ur security/selinux.orig/Kconfig security/selinux/Kconfig
--- security/selinux.orig/Kconfig	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/Kconfig	2007-07-20 17:45:40.000000000 +0900
@@ -11,6 +11,17 @@
 	  from <http://www.nsa.gov/selinux/>.
 	  If you are unsure how to answer this question, answer N.
 
+config SECURITY_SELINUX_AVTAB_HASH_BITS
+	int "NSA SELinux default AVTAB_HASH_BITS value"
+	depends on SECURITY_SELINUX && EMBEDDED
+	range 1 15
+	default 15
+	help
+	  This configures AVTAB_HASH_BITS in avtab.h. The size of avtab hashtable 
+	  is 2^AVTAB_HASH_BITS. You can improve memory footprint of SELinux by 
+	  configuring this value appropriately.
+	  If you are unsure how to answer this question, answer 15.
+
 config SECURITY_SELINUX_BOOTPARAM
 	bool "NSA SELinux boot parameter"
 	depends on SECURITY_SELINUX
diff -ur security/selinux.orig/ss/avtab.h security/selinux/ss/avtab.h
--- security/selinux.orig/ss/avtab.h	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/ss/avtab.h	2007-07-20 18:18:56.000000000 +0900
@@ -74,7 +74,7 @@
 void avtab_cache_init(void);
 void avtab_cache_destroy(void);
 
-#define AVTAB_HASH_BITS 15
+#define AVTAB_HASH_BITS CONFIG_SECURITY_SELINUX_AVTAB_HASH_BITS
 #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
 #define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
 

Regards,
-- 
Yuichi Nakamura
Hitachi Software Engineering Co., Ltd.
Japan SELinux Users Group(JSELUG): http://www.selinux.gr.jp/
SELinux Policy Editor: http://seedit.sourceforge.net/


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Stephen Smalley]

On Mon, 2007-07-23 at 16:03 +0900, Yuichi Nakamura wrote:
> Hi.
> 
> I am working to reduce memory usage of SELinux for embedded devices.
> I would like to propose very small patch at first.
> Thanks for advice > KaiGai-san .
> 
> 1. Background 
> * In avtab_init:
>  h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
> Number of hash table size is AVTAB_SIZE.
> 
> * In avtab.h
> #define AVTAB_HASH_BITS 15
> #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
> #define AVTAB_SIZE AVTAB_HASH_BUCKETS
> 
> AVTAB_SIZE is 2^15 = 32768
> 
> So 32768 entries are allocated for avtab, 
> and 2 avtabs are used in policydb:
> struct avtab te_avtab;
> struct avtab te_cond_avtab;
> 
> If te rules are fewer than 32768,
> unused entries are using memory.
> 
> In embedded devices, the rules tend to be fewer.
> In my test system(SH architecture board), it is less than 10000 rules.
> 
> 2. Patch
> I made AVTAB_HASH_BITS customizable by Kconfig.
> Allocated hash slots for avtab can be reduced by reducing AVTAB_HASH_BITS.
> 
> Attached  patch is for 2.6.22.
> Then, I measured memory usage by /proc/memstat before/after tuning
> 
> * Memory usage: SELinux before loading policy.
> 2720k is used.
> 
> * Memory usage: SELinux after loading policy(about 8000 rules) before patch
> +1068k increase
> 
> * Memory usage: SELinux after loading poilcy(about 8000 rules) after patch.
>   configured AVTAB_HASH_BITS as "13" 
> +876k increase
> -> improved 192k
> 
> * Theoretical value:
> - Before tuning: 
>   Number of hashslot 2^15 * 2 
>   Size of hash slot: 4 (sizeof(*(h->htable)))
>   Memory usage = 2^15*2*4 = 262k
> 
> - After tuning: 
>   Number of hash slot is 2^13 * 2, 
>   and size of hash slot is 4 (sizeof(*(h->htable)))
>   Memory usage = 2^13*2*4 = 65k 
>   -> 197k should improve, this value is almost the same as measured value.
> 
> Following is a patch:
> 
> diff -ur security/selinux.orig/Kconfig security/selinux/Kconfig
> --- security/selinux.orig/Kconfig	2007-07-20 17:29:30.000000000 +0900
> +++ security/selinux/Kconfig	2007-07-20 17:45:40.000000000 +0900
> @@ -11,6 +11,17 @@
>  	  from <http://www.nsa.gov/selinux/>.
>  	  If you are unsure how to answer this question, answer N.
>  
> +config SECURITY_SELINUX_AVTAB_HASH_BITS
> +	int "NSA SELinux default AVTAB_HASH_BITS value"
> +	depends on SECURITY_SELINUX && EMBEDDED
> +	range 1 15
> +	default 15
> +	help
> +	  This configures AVTAB_HASH_BITS in avtab.h. The size of avtab hashtable 
> +	  is 2^AVTAB_HASH_BITS. You can improve memory footprint of SELinux by 
> +	  configuring this value appropriately.
> +	  If you are unsure how to answer this question, answer 15.
> +
>  config SECURITY_SELINUX_BOOTPARAM
>  	bool "NSA SELinux boot parameter"
>  	depends on SECURITY_SELINUX
> diff -ur security/selinux.orig/ss/avtab.h security/selinux/ss/avtab.h
> --- security/selinux.orig/ss/avtab.h	2007-07-20 17:29:30.000000000 +0900
> +++ security/selinux/ss/avtab.h	2007-07-20 18:18:56.000000000 +0900
> @@ -74,7 +74,7 @@
>  void avtab_cache_init(void);
>  void avtab_cache_destroy(void);
>  
> -#define AVTAB_HASH_BITS 15
> +#define AVTAB_HASH_BITS CONFIG_SECURITY_SELINUX_AVTAB_HASH_BITS
>  #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
>  #define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)

I'm open to making this configurable, although I'm not sure whether it
should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
of course, it would be runtime computed based on the actual policy size.
Rewriting the avtab and other security server data structures to more
kernel native would be fine with me too - they don't need to match the
userland ones.

(please cc James, Eric, and me on selinux kernel patches)

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Stephen Smalley]

On Mon, 2007-07-23 at 15:58 -0400, Stephen Smalley wrote:
> On Mon, 2007-07-23 at 16:03 +0900, Yuichi Nakamura wrote:
> > Hi.
> > 
> > I am working to reduce memory usage of SELinux for embedded devices.
> > I would like to propose very small patch at first.
> > Thanks for advice > KaiGai-san .
> > 
> > 1. Background 
> > * In avtab_init:
> >  h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
> > Number of hash table size is AVTAB_SIZE.
> > 
> > * In avtab.h
> > #define AVTAB_HASH_BITS 15
> > #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
> > #define AVTAB_SIZE AVTAB_HASH_BUCKETS
> > 
> > AVTAB_SIZE is 2^15 = 32768
> > 
> > So 32768 entries are allocated for avtab, 
> > and 2 avtabs are used in policydb:
> > struct avtab te_avtab;
> > struct avtab te_cond_avtab;
> > 
> > If te rules are fewer than 32768,
> > unused entries are using memory.
> > 
> > In embedded devices, the rules tend to be fewer.
> > In my test system(SH architecture board), it is less than 10000 rules.
> > 
> > 2. Patch
> > I made AVTAB_HASH_BITS customizable by Kconfig.
> > Allocated hash slots for avtab can be reduced by reducing AVTAB_HASH_BITS.
> > 
> > Attached  patch is for 2.6.22.
> > Then, I measured memory usage by /proc/memstat before/after tuning
> > 
> > * Memory usage: SELinux before loading policy.
> > 2720k is used.
> > 
> > * Memory usage: SELinux after loading policy(about 8000 rules) before patch
> > +1068k increase
> > 
> > * Memory usage: SELinux after loading poilcy(about 8000 rules) after patch.
> >   configured AVTAB_HASH_BITS as "13" 
> > +876k increase
> > -> improved 192k
> > 
> > * Theoretical value:
> > - Before tuning: 
> >   Number of hashslot 2^15 * 2 
> >   Size of hash slot: 4 (sizeof(*(h->htable)))
> >   Memory usage = 2^15*2*4 = 262k
> > 
> > - After tuning: 
> >   Number of hash slot is 2^13 * 2, 
> >   and size of hash slot is 4 (sizeof(*(h->htable)))
> >   Memory usage = 2^13*2*4 = 65k 
> >   -> 197k should improve, this value is almost the same as measured value.
> > 
> > Following is a patch:
> > 
> > diff -ur security/selinux.orig/Kconfig security/selinux/Kconfig
> > --- security/selinux.orig/Kconfig	2007-07-20 17:29:30.000000000 +0900
> > +++ security/selinux/Kconfig	2007-07-20 17:45:40.000000000 +0900
> > @@ -11,6 +11,17 @@
> >  	  from <http://www.nsa.gov/selinux/>.
> >  	  If you are unsure how to answer this question, answer N.
> >  
> > +config SECURITY_SELINUX_AVTAB_HASH_BITS
> > +	int "NSA SELinux default AVTAB_HASH_BITS value"
> > +	depends on SECURITY_SELINUX && EMBEDDED
> > +	range 1 15
> > +	default 15
> > +	help
> > +	  This configures AVTAB_HASH_BITS in avtab.h. The size of avtab hashtable 
> > +	  is 2^AVTAB_HASH_BITS. You can improve memory footprint of SELinux by 
> > +	  configuring this value appropriately.
> > +	  If you are unsure how to answer this question, answer 15.
> > +
> >  config SECURITY_SELINUX_BOOTPARAM
> >  	bool "NSA SELinux boot parameter"
> >  	depends on SECURITY_SELINUX
> > diff -ur security/selinux.orig/ss/avtab.h security/selinux/ss/avtab.h
> > --- security/selinux.orig/ss/avtab.h	2007-07-20 17:29:30.000000000 +0900
> > +++ security/selinux/ss/avtab.h	2007-07-20 18:18:56.000000000 +0900
> > @@ -74,7 +74,7 @@
> >  void avtab_cache_init(void);
> >  void avtab_cache_destroy(void);
> >  
> > -#define AVTAB_HASH_BITS 15
> > +#define AVTAB_HASH_BITS CONFIG_SECURITY_SELINUX_AVTAB_HASH_BITS
> >  #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
> >  #define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
> 
> I'm open to making this configurable, although I'm not sure whether it
> should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
> of course, it would be runtime computed based on the actual policy size.
> Rewriting the avtab and other security server data structures to more
> kernel native would be fine with me too - they don't need to match the
> userland ones.

Another thing to consider here as well is that if the size is smaller,
one could use kmalloc rather than vmalloc for the avtab, which would
also be of benefit.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[KaiGai Kohei]

Stephen Smalley wrote:
> On Mon, 2007-07-23 at 16:03 +0900, Yuichi Nakamura wrote:
>> Hi.
>>
>> I am working to reduce memory usage of SELinux for embedded devices.
>> I would like to propose very small patch at first.
>> Thanks for advice > KaiGai-san .
>>
>> 1. Background 
>> * In avtab_init:
>>  h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
>> Number of hash table size is AVTAB_SIZE.
>>
>> * In avtab.h
>> #define AVTAB_HASH_BITS 15
>> #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
>> #define AVTAB_SIZE AVTAB_HASH_BUCKETS
>>
>> AVTAB_SIZE is 2^15 = 32768
>>
>> So 32768 entries are allocated for avtab, 
>> and 2 avtabs are used in policydb:
>> struct avtab te_avtab;
>> struct avtab te_cond_avtab;
>>
>> If te rules are fewer than 32768,
>> unused entries are using memory.
>>
>> In embedded devices, the rules tend to be fewer.
>> In my test system(SH architecture board), it is less than 10000 rules.
>>
>> 2. Patch
>> I made AVTAB_HASH_BITS customizable by Kconfig.
>> Allocated hash slots for avtab can be reduced by reducing AVTAB_HASH_BITS.
>>
>> Attached  patch is for 2.6.22.
>> Then, I measured memory usage by /proc/memstat before/after tuning
>>
>> * Memory usage: SELinux before loading policy.
>> 2720k is used.
>>
>> * Memory usage: SELinux after loading policy(about 8000 rules) before patch
>> +1068k increase
>>
>> * Memory usage: SELinux after loading poilcy(about 8000 rules) after patch.
>>   configured AVTAB_HASH_BITS as "13" 
>> +876k increase
>> -> improved 192k
>>
>> * Theoretical value:
>> - Before tuning: 
>>   Number of hashslot 2^15 * 2 
>>   Size of hash slot: 4 (sizeof(*(h->htable)))
>>   Memory usage = 2^15*2*4 = 262k
>>
>> - After tuning: 
>>   Number of hash slot is 2^13 * 2, 
>>   and size of hash slot is 4 (sizeof(*(h->htable)))
>>   Memory usage = 2^13*2*4 = 65k 
>>   -> 197k should improve, this value is almost the same as measured value.
>>
>> Following is a patch:
>>
>> diff -ur security/selinux.orig/Kconfig security/selinux/Kconfig
>> --- security/selinux.orig/Kconfig	2007-07-20 17:29:30.000000000 +0900
>> +++ security/selinux/Kconfig	2007-07-20 17:45:40.000000000 +0900
>> @@ -11,6 +11,17 @@
>>  	  from <http://www.nsa.gov/selinux/>.
>>  	  If you are unsure how to answer this question, answer N.
>>  
>> +config SECURITY_SELINUX_AVTAB_HASH_BITS
>> +	int "NSA SELinux default AVTAB_HASH_BITS value"
>> +	depends on SECURITY_SELINUX && EMBEDDED
>> +	range 1 15
>> +	default 15
>> +	help
>> +	  This configures AVTAB_HASH_BITS in avtab.h. The size of avtab hashtable 
>> +	  is 2^AVTAB_HASH_BITS. You can improve memory footprint of SELinux by 
>> +	  configuring this value appropriately.
>> +	  If you are unsure how to answer this question, answer 15.
>> +
>>  config SECURITY_SELINUX_BOOTPARAM
>>  	bool "NSA SELinux boot parameter"
>>  	depends on SECURITY_SELINUX
>> diff -ur security/selinux.orig/ss/avtab.h security/selinux/ss/avtab.h
>> --- security/selinux.orig/ss/avtab.h	2007-07-20 17:29:30.000000000 +0900
>> +++ security/selinux/ss/avtab.h	2007-07-20 18:18:56.000000000 +0900
>> @@ -74,7 +74,7 @@
>>  void avtab_cache_init(void);
>>  void avtab_cache_destroy(void);
>>  
>> -#define AVTAB_HASH_BITS 15
>> +#define AVTAB_HASH_BITS CONFIG_SECURITY_SELINUX_AVTAB_HASH_BITS
>>  #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
>>  #define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
> 
> I'm open to making this configurable, although I'm not sure whether it
> should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
> of course, it would be runtime computed based on the actual policy size.
> Rewriting the avtab and other security server data structures to more
> kernel native would be fine with me too - they don't need to match the
> userland ones.
> 
> (please cc James, Eric, and me on selinux kernel patches)

How do you think an idea that the values of AVTAB_HASH_BITS depends
on CONFIG_EMBEDDED, more than adding a new Kconfig entry?
I think SECURITY_SELINUX_AVTAB_HASH_BITS in Kconfig is too detailed.

For example,

#ifdef CONFIG_EMBEDDED
/* to reduce memory footpoint in embedded devices */
#define AVTAB_HASH_BITS (PAGE_SHIFT - 2)
#else
#define AVTAB_HASH_BITS 15
#endif

PAGE_SIZE is the minimum unit for vmalloc(), so it is nonsense
to require a region less than 2^(PAGE_SHIFT - 2).
In addition, CONFIG_EMBEDDED is already set 'y' in defconfig of
some of SH, MIPS, ARM and so on. It will fit to your target.

There is another background, although Nakamura-san didn't mentioned.
The AVC hit rate is extremely high, so getting longer the chain of
avtab hash list does not have maeningful difference in performance.

Thanks,
-- 
Open Source Software Promotion Center, NEC
KaiGai Kohei <kaigai@ak.jp.nec.com>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Joshua Brindle]

KaiGai Kohei wrote:
> Stephen Smalley wrote:
>   
>> On Mon, 2007-07-23 at 16:03 +0900, Yuichi Nakamura wrote:
>>     
>>> Hi.
>>>
>>> I am working to reduce memory usage of SELinux for embedded devices.
>>> I would like to propose very small patch at first.
>>> Thanks for advice > KaiGai-san .
>>>
>>> 1. Background 
>>> * In avtab_init:
>>>  h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
>>> Number of hash table size is AVTAB_SIZE.
>>>
>>> * In avtab.h
>>> #define AVTAB_HASH_BITS 15
>>> #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
>>> #define AVTAB_SIZE AVTAB_HASH_BUCKETS
>>>
>>> AVTAB_SIZE is 2^15 = 32768
>>>
>>> So 32768 entries are allocated for avtab, 
>>> and 2 avtabs are used in policydb:
>>> struct avtab te_avtab;
>>> struct avtab te_cond_avtab;
>>>
>>> If te rules are fewer than 32768,
>>> unused entries are using memory.
>>>
>>> In embedded devices, the rules tend to be fewer.
>>> In my test system(SH architecture board), it is less than 10000 rules.
>>>
>>> 2. Patch
>>> I made AVTAB_HASH_BITS customizable by Kconfig.
>>> Allocated hash slots for avtab can be reduced by reducing AVTAB_HASH_BITS.
>>>
>>> Attached  patch is for 2.6.22.
>>> Then, I measured memory usage by /proc/memstat before/after tuning
>>>
>>> * Memory usage: SELinux before loading policy.
>>> 2720k is used.
>>>
>>> * Memory usage: SELinux after loading policy(about 8000 rules) before patch
>>> +1068k increase
>>>
>>> * Memory usage: SELinux after loading poilcy(about 8000 rules) after patch.
>>>   configured AVTAB_HASH_BITS as "13" 
>>> +876k increase
>>> -> improved 192k
>>>
>>> * Theoretical value:
>>> - Before tuning: 
>>>   Number of hashslot 2^15 * 2 
>>>   Size of hash slot: 4 (sizeof(*(h->htable)))
>>>   Memory usage = 2^15*2*4 = 262k
>>>
>>> - After tuning: 
>>>   Number of hash slot is 2^13 * 2, 
>>>   and size of hash slot is 4 (sizeof(*(h->htable)))
>>>   Memory usage = 2^13*2*4 = 65k 
>>>   -> 197k should improve, this value is almost the same as measured value.
>>>
>>> Following is a patch:
>>>
>>> diff -ur security/selinux.orig/Kconfig security/selinux/Kconfig
>>> --- security/selinux.orig/Kconfig	2007-07-20 17:29:30.000000000 +0900
>>> +++ security/selinux/Kconfig	2007-07-20 17:45:40.000000000 +0900
>>> @@ -11,6 +11,17 @@
>>>  	  from <http://www.nsa.gov/selinux/>.
>>>  	  If you are unsure how to answer this question, answer N.
>>>  
>>> +config SECURITY_SELINUX_AVTAB_HASH_BITS
>>> +	int "NSA SELinux default AVTAB_HASH_BITS value"
>>> +	depends on SECURITY_SELINUX && EMBEDDED
>>> +	range 1 15
>>> +	default 15
>>> +	help
>>> +	  This configures AVTAB_HASH_BITS in avtab.h. The size of avtab hashtable 
>>> +	  is 2^AVTAB_HASH_BITS. You can improve memory footprint of SELinux by 
>>> +	  configuring this value appropriately.
>>> +	  If you are unsure how to answer this question, answer 15.
>>> +
>>>  config SECURITY_SELINUX_BOOTPARAM
>>>  	bool "NSA SELinux boot parameter"
>>>  	depends on SECURITY_SELINUX
>>> diff -ur security/selinux.orig/ss/avtab.h security/selinux/ss/avtab.h
>>> --- security/selinux.orig/ss/avtab.h	2007-07-20 17:29:30.000000000 +0900
>>> +++ security/selinux/ss/avtab.h	2007-07-20 18:18:56.000000000 +0900
>>> @@ -74,7 +74,7 @@
>>>  void avtab_cache_init(void);
>>>  void avtab_cache_destroy(void);
>>>  
>>> -#define AVTAB_HASH_BITS 15
>>> +#define AVTAB_HASH_BITS CONFIG_SECURITY_SELINUX_AVTAB_HASH_BITS
>>>  #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
>>>  #define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
>>>       
>> I'm open to making this configurable, although I'm not sure whether it
>> should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
>> of course, it would be runtime computed based on the actual policy size.
>> Rewriting the avtab and other security server data structures to more
>> kernel native would be fine with me too - they don't need to match the
>> userland ones.
>>
>> (please cc James, Eric, and me on selinux kernel patches)
>>     
>
> How do you think an idea that the values of AVTAB_HASH_BITS depends
> on CONFIG_EMBEDDED, more than adding a new Kconfig entry?
> I think SECURITY_SELINUX_AVTAB_HASH_BITS in Kconfig is too detailed.
>
> For example,
>
> #ifdef CONFIG_EMBEDDED
> /* to reduce memory footpoint in embedded devices */
> #define AVTAB_HASH_BITS (PAGE_SHIFT - 2)
> #else
> #define AVTAB_HASH_BITS 15
> #endif
>
> PAGE_SIZE is the minimum unit for vmalloc(), so it is nonsense
> to require a region less than 2^(PAGE_SHIFT - 2).
> In addition, CONFIG_EMBEDDED is already set 'y' in defconfig of
> some of SH, MIPS, ARM and so on. It will fit to your target.
>
>   
I think he was suggesting making it runtime configurable (or even
automatic based on the size of the loaded policy)

One should be able to dynamically choose the number of hash buckets
based off of how many rules are in the policy being loaded, keeping the
buckets balanced though could be a harder problem to solve.

> There is another background, although Nakamura-san didn't mentioned.
> The AVC hit rate is extremely high, so getting longer the chain of
> avtab hash list does not have maeningful difference in performance.
>   
We've had some issues lately with the speed of the avtab, specifically
around finding reachable user domains. They've been addressed for now
(my offloading some work to userspace) but there may be others lurking,
people are finally starting to profile some of this code though.


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Yuichi Nakamura]

Hi.

Stephen, KaiGai, Josua, Thanks for comments.

On Mon, 23 Jul 2007 23:31:14 -0400
Joshua Brindle  wrote:
> KaiGai Kohei wrote:
> > Stephen Smalley wrote:
<snip>
> I think he was suggesting making it runtime configurable (or even
> automatic based on the size of the loaded policy)
> 
> One should be able to dynamically choose the number of hash buckets
> based off of how many rules are in the policy being loaded, keeping the
> buckets balanced though could be a harder problem to solve.
OK, I am testing to dynamically configuring number of hash slots based on number of rules.
I will send RFC later.
 
> > There is another background, although Nakamura-san didn't mentioned.
> > The AVC hit rate is extremely high, so getting longer the chain of
> > avtab hash list does not have maeningful difference in performance.
> >   
> We've had some issues lately with the speed of the avtab, specifically
> around finding reachable user domains. They've been addressed for now
> (my offloading some work to userspace) but there may be others lurking,
> people are finally starting to profile some of this code though.
> 
> 
> --
> This message was distributed to subscribers of the selinux mailing list.
> If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
> the words "unsubscribe selinux" without quotes as the message.


Regards,
-- 
Yuichi Nakamura
Hitachi Software Engineering Co., Ltd.
Japan SELinux Users Group(JSELUG): http://www.selinux.gr.jp/
SELinux Policy Editor: http://seedit.sourceforge.net/


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

[RFC] Dynamically deciding number of hash slots for avtab (Was:Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Yuichi Nakamura]

On Mon, 23 Jul 2007 15:58:31 -0400
Stephen Smalley  wrote:
> I'm open to making this configurable, although I'm not sure whether it
> should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
> of course, it would be runtime computed based on the actual policy size.
> Rewriting the avtab and other security server data structures to more
> kernel native would be fine with me too - they don't need to match the
> userland ones.
> 
> (please cc James, Eric, and me on selinux kernel patches)
OK, I made patch about that. 
Please look at patch at the end of this e-mail.

It decides number of hash slots based on number of unconditional TE rules.
I looked at avtab_read, and found number of unconditional TE rules are 
described in binary policy, 
so it can be used.
Number of hash slot is 2^n. n is decided based on number of unconditional TE rules.
If number of unconditional TE rules is 4000, n is 12, so 2^12 = 4096 slots 
are allocated for te_avtab and te_cond_avtab.

I tested the patch against my test policy.
It contains 8486 unconditional TE rules, 3464 conditional TE rules.
So number of hash slots for te_avtab is 16384.
te_cond_avtab is also 16384.
Before tuning, it was 32768 for both, 
so saved 32768 hash slots(about 32768*4 = 131k byte).

I could not find the way to obtain number of "conditinal" TE rules 
before avtab_init(in cond_read_list).
If I could obtain number of conditional TE rules before avtab_init,
number of allocated hash slots for te_cond_avtab would be 4096, can save memory more...
Does anyone know how to obtain number of conditional TE rules?
Should policy format be changed for that?

And I had to change AVTAB_HASH.
Is it OK?

Below is patch.

diff -r -pu security/selinux.orig/ss/avtab.c security/selinux/ss/avtab.c
--- security/selinux.orig/ss/avtab.c	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/ss/avtab.c	2007-07-24 15:11:43.000000000 +0900
@@ -22,11 +22,11 @@
 #include "avtab.h"
 #include "policydb.h"
 
-#define AVTAB_HASH(keyp) \
+#define AVTAB_HASH(keyp,mask)			\
 ((keyp->target_class + \
  (keyp->target_type << 2) + \
  (keyp->source_type << 9)) & \
- AVTAB_HASH_MASK)
+ mask)
 
 static struct kmem_cache *avtab_node_cachep;
 
@@ -62,7 +62,7 @@ static int avtab_insert(struct avtab *h,
 	if (!h)
 		return -EINVAL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key,h->mask);
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {
@@ -102,7 +102,7 @@ avtab_insert_nonunique(struct avtab * h,
 
 	if (!h)
 		return NULL;
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {
@@ -135,7 +135,7 @@ struct avtab_datum *avtab_search(struct 
 	if (!h)
 		return NULL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 		if (key->source_type == cur->key.source_type &&
 		    key->target_type == cur->key.target_type &&
@@ -170,7 +170,7 @@ avtab_search_node(struct avtab *h, struc
 	if (!h)
 		return NULL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 		if (key->source_type == cur->key.source_type &&
 		    key->target_type == cur->key.target_type &&
@@ -228,7 +228,7 @@ void avtab_destroy(struct avtab *h)
 	if (!h || !h->htable)
 		return;
 
-	for (i = 0; i < AVTAB_SIZE; i++) {
+	for (i = 0; i < h->nslot; i++) {
 		cur = h->htable[i];
 		while (cur != NULL) {
 			temp = cur;
@@ -239,19 +239,38 @@ void avtab_destroy(struct avtab *h)
 	}
 	vfree(h->htable);
 	h->htable = NULL;
+	h->nslot = 0;
+	h->mask = 0;
 }
 
-
-int avtab_init(struct avtab *h)
-{
+int avtab_init(struct avtab *h, int nrules) {
 	int i;
+	u16 mask;
+	int shift = 0;
+	int work = nrules;
+	int nslot;
+	
+	if (nrules > MAX_AVTAB_SIZE) {
+		nslot = MAX_AVTAB_SIZE;
+		mask =  MAX_AVTAB_HASH_MASK ;
+	} else {
+		while(work) {
+			work  = work>>1;
+			shift++;
+		}
+		mask =(1 << shift) - 1;	
+		nslot = 1 << shift;
+	}
 
-	h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
+	h->htable = vmalloc(sizeof(*(h->htable)) * nslot);
 	if (!h->htable)
 		return -ENOMEM;
-	for (i = 0; i < AVTAB_SIZE; i++)
+	for (i = 0; i < nslot; i++)
 		h->htable[i] = NULL;
 	h->nel = 0;
+	h->nslot = nslot;
+	h->mask = mask;	
+	printk(KERN_DEBUG "SELinux:%d avtab hash slots allocated. Num of rules:%d\n", h->nslot, nrules);
 	return 0;
 }
 
@@ -262,7 +281,7 @@ void avtab_hash_eval(struct avtab *h, ch
 
 	slots_used = 0;
 	max_chain_len = 0;
-	for (i = 0; i < AVTAB_SIZE; i++) {
+	for (i = 0; i < h->nslot; i++) {
 		cur = h->htable[i];
 		if (cur) {
 			slots_used++;
@@ -278,7 +297,7 @@ void avtab_hash_eval(struct avtab *h, ch
 	}
 
 	printk(KERN_DEBUG "%s:  %d entries and %d/%d buckets used, longest "
-	       "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
+	       "chain length %d\n", tag, h->nel, slots_used, h->nslot,
 	       max_chain_len);
 }
 
@@ -419,6 +438,13 @@ int avtab_read(struct avtab *a, void *fp
 		rc = -EINVAL;
 		goto bad;
 	}
+
+	rc = avtab_init(a, nel);
+	if (rc) {
+		rc = -ENOMEM;
+		goto bad;
+	}
+
 	for (i = 0; i < nel; i++) {
 		rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL);
 		if (rc) {

diff -r -pu security/selinux.orig/ss/avtab.h security/selinux/ss/avtab.h
--- security/selinux.orig/ss/avtab.h	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/ss/avtab.h	2007-07-24 14:31:28.000000000 +0900
@@ -50,9 +50,12 @@ struct avtab_node {
 struct avtab {
 	struct avtab_node **htable;
 	u32 nel;	/* number of elements */
+	u32 nslot;      /* number of hash slots */
+	u16 mask;       /* mask to compute hash func */
+
 };
 
-int avtab_init(struct avtab *);
+int avtab_init(struct avtab *, int);
 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *k);
 void avtab_destroy(struct avtab *h);
 void avtab_hash_eval(struct avtab *h, char *tag);
@@ -74,11 +77,10 @@ struct avtab_node *avtab_search_node_nex
 void avtab_cache_init(void);
 void avtab_cache_destroy(void);
 
-#define AVTAB_HASH_BITS 15
-#define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
-#define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
-
-#define AVTAB_SIZE AVTAB_HASH_BUCKETS
+#define MAX_AVTAB_HASH_BITS 15
+#define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
+#define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
+#define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
 
 #endif	/* _SS_AVTAB_H_ */
 

diff -r -pu security/selinux.orig/ss/conditional.c security/selinux/ss/conditional.c
--- security/selinux.orig/ss/conditional.c	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/ss/conditional.c	2007-07-24 18:15:50.000000000 +0900
@@ -122,8 +122,8 @@ int cond_policydb_init(struct policydb *
 {
 	p->bool_val_to_struct = NULL;
 	p->cond_list = NULL;
-	if (avtab_init(&p->te_cond_avtab))
-		return -1;
+	p->te_cond_avtab.htable = NULL;
+	p->te_cond_avtab.nel = 0;
 
 	return 0;
 }
@@ -455,6 +455,16 @@ int cond_read_list(struct policydb *p, v
 		return -1;
 
 	len = le32_to_cpu(buf[0]);
+	
+	rc = avtab_init(&(p->te_cond_avtab), p->te_avtab.nel);
+	/* FIXME
+	  Number of hash slots is the same as te_avtab for now..
+	  Could be smaller.. Ideas?
+	 */
+	if (rc) {
+		rc = -ENOMEM;
+		goto err;
+	}
 
 	for (i = 0; i < len; i++) {
 		node = kzalloc(sizeof(struct cond_node), GFP_KERNEL);


diff -r -pu security/selinux.orig/ss/policydb.c security/selinux/ss/policydb.c
--- security/selinux.orig/ss/policydb.c	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/ss/policydb.c	2007-07-24 17:09:24.000000000 +0900
@@ -169,25 +169,21 @@ static int policydb_init(struct policydb
 		if (rc)
 			goto out_free_symtab;
 	}
-
-	rc = avtab_init(&p->te_avtab);
-	if (rc)
-		goto out_free_symtab;
-
+	
+	p->te_avtab.htable = NULL;
+	p->te_avtab.nel = 0;
+	
 	rc = roles_init(p);
 	if (rc)
-		goto out_free_avtab;
+		goto out_free_symtab;
 
 	rc = cond_policydb_init(p);
 	if (rc)
-		goto out_free_avtab;
+	  goto out_free_symtab;
 
 out:
 	return rc;
 
-out_free_avtab:
-	avtab_destroy(&p->te_avtab);
-
 out_free_symtab:
 	for (i = 0; i < SYM_NUM; i++)
 		hashtab_destroy(p->symtab[i].table);

Regards,
-- 
Yuichi Nakamura
Hitachi Software Engineering Co., Ltd.
Japan SELinux Users Group(JSELUG): http://www.selinux.gr.jp/
SELinux Policy Editor: http://seedit.sourceforge.net/

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Stephen Smalley]

On Tue, 2007-07-24 at 12:06 +0900, KaiGai Kohei wrote:
> Stephen Smalley wrote:
> > On Mon, 2007-07-23 at 16:03 +0900, Yuichi Nakamura wrote:
> >> Hi.
> >>
> >> I am working to reduce memory usage of SELinux for embedded devices.
> >> I would like to propose very small patch at first.
> >> Thanks for advice > KaiGai-san .
> >>
> >> 1. Background 
> >> * In avtab_init:
> >>  h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
> >> Number of hash table size is AVTAB_SIZE.
> >>
> >> * In avtab.h
> >> #define AVTAB_HASH_BITS 15
> >> #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
> >> #define AVTAB_SIZE AVTAB_HASH_BUCKETS
> >>
> >> AVTAB_SIZE is 2^15 = 32768
> >>
> >> So 32768 entries are allocated for avtab, 
> >> and 2 avtabs are used in policydb:
> >> struct avtab te_avtab;
> >> struct avtab te_cond_avtab;
> >>
> >> If te rules are fewer than 32768,
> >> unused entries are using memory.
> >>
> >> In embedded devices, the rules tend to be fewer.
> >> In my test system(SH architecture board), it is less than 10000 rules.
> >>
> >> 2. Patch
> >> I made AVTAB_HASH_BITS customizable by Kconfig.
> >> Allocated hash slots for avtab can be reduced by reducing AVTAB_HASH_BITS.
> >>
> >> Attached  patch is for 2.6.22.
> >> Then, I measured memory usage by /proc/memstat before/after tuning
> >>
> >> * Memory usage: SELinux before loading policy.
> >> 2720k is used.
> >>
> >> * Memory usage: SELinux after loading policy(about 8000 rules) before patch
> >> +1068k increase
> >>
> >> * Memory usage: SELinux after loading poilcy(about 8000 rules) after patch.
> >>   configured AVTAB_HASH_BITS as "13" 
> >> +876k increase
> >> -> improved 192k
> >>
> >> * Theoretical value:
> >> - Before tuning: 
> >>   Number of hashslot 2^15 * 2 
> >>   Size of hash slot: 4 (sizeof(*(h->htable)))
> >>   Memory usage = 2^15*2*4 = 262k
> >>
> >> - After tuning: 
> >>   Number of hash slot is 2^13 * 2, 
> >>   and size of hash slot is 4 (sizeof(*(h->htable)))
> >>   Memory usage = 2^13*2*4 = 65k 
> >>   -> 197k should improve, this value is almost the same as measured value.
> >>
> >> Following is a patch:
> >>
> >> diff -ur security/selinux.orig/Kconfig security/selinux/Kconfig
> >> --- security/selinux.orig/Kconfig	2007-07-20 17:29:30.000000000 +0900
> >> +++ security/selinux/Kconfig	2007-07-20 17:45:40.000000000 +0900
> >> @@ -11,6 +11,17 @@
> >>  	  from <http://www.nsa.gov/selinux/>.
> >>  	  If you are unsure how to answer this question, answer N.
> >>  
> >> +config SECURITY_SELINUX_AVTAB_HASH_BITS
> >> +	int "NSA SELinux default AVTAB_HASH_BITS value"
> >> +	depends on SECURITY_SELINUX && EMBEDDED
> >> +	range 1 15
> >> +	default 15
> >> +	help
> >> +	  This configures AVTAB_HASH_BITS in avtab.h. The size of avtab hashtable 
> >> +	  is 2^AVTAB_HASH_BITS. You can improve memory footprint of SELinux by 
> >> +	  configuring this value appropriately.
> >> +	  If you are unsure how to answer this question, answer 15.
> >> +
> >>  config SECURITY_SELINUX_BOOTPARAM
> >>  	bool "NSA SELinux boot parameter"
> >>  	depends on SECURITY_SELINUX
> >> diff -ur security/selinux.orig/ss/avtab.h security/selinux/ss/avtab.h
> >> --- security/selinux.orig/ss/avtab.h	2007-07-20 17:29:30.000000000 +0900
> >> +++ security/selinux/ss/avtab.h	2007-07-20 18:18:56.000000000 +0900
> >> @@ -74,7 +74,7 @@
> >>  void avtab_cache_init(void);
> >>  void avtab_cache_destroy(void);
> >>  
> >> -#define AVTAB_HASH_BITS 15
> >> +#define AVTAB_HASH_BITS CONFIG_SECURITY_SELINUX_AVTAB_HASH_BITS
> >>  #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
> >>  #define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
> > 
> > I'm open to making this configurable, although I'm not sure whether it
> > should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
> > of course, it would be runtime computed based on the actual policy size.
> > Rewriting the avtab and other security server data structures to more
> > kernel native would be fine with me too - they don't need to match the
> > userland ones.
> > 
> > (please cc James, Eric, and me on selinux kernel patches)
> 
> How do you think an idea that the values of AVTAB_HASH_BITS depends
> on CONFIG_EMBEDDED, more than adding a new Kconfig entry?
> I think SECURITY_SELINUX_AVTAB_HASH_BITS in Kconfig is too detailed.
> 
> For example,
> 
> #ifdef CONFIG_EMBEDDED
> /* to reduce memory footpoint in embedded devices */
> #define AVTAB_HASH_BITS (PAGE_SHIFT - 2)
> #else
> #define AVTAB_HASH_BITS 15
> #endif
> 
> PAGE_SIZE is the minimum unit for vmalloc(), so it is nonsense
> to require a region less than 2^(PAGE_SHIFT - 2).
> In addition, CONFIG_EMBEDDED is already set 'y' in defconfig of
> some of SH, MIPS, ARM and so on. It will fit to your target.
> 
> There is another background, although Nakamura-san didn't mentioned.
> The AVC hit rate is extremely high, so getting longer the chain of
> avtab hash list does not have maeningful difference in performance.

I have to wonder then whether we should just unconditionally shrink the
avtab, regardless of embedded or not.  And revert from vmalloc to
kmalloc for it.


-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Stephen Smalley]

On Mon, 2007-07-23 at 23:31 -0400, Joshua Brindle wrote:
> KaiGai Kohei wrote:
> > Stephen Smalley wrote:
> >   
> >> On Mon, 2007-07-23 at 16:03 +0900, Yuichi Nakamura wrote:
> >>     
> >>> Hi.
> >>>
> >>> I am working to reduce memory usage of SELinux for embedded devices.
> >>> I would like to propose very small patch at first.
> >>> Thanks for advice > KaiGai-san .
> >>>
> >>> 1. Background 
> >>> * In avtab_init:
> >>>  h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
> >>> Number of hash table size is AVTAB_SIZE.
> >>>
> >>> * In avtab.h
> >>> #define AVTAB_HASH_BITS 15
> >>> #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
> >>> #define AVTAB_SIZE AVTAB_HASH_BUCKETS
> >>>
> >>> AVTAB_SIZE is 2^15 = 32768
> >>>
> >>> So 32768 entries are allocated for avtab, 
> >>> and 2 avtabs are used in policydb:
> >>> struct avtab te_avtab;
> >>> struct avtab te_cond_avtab;
> >>>
> >>> If te rules are fewer than 32768,
> >>> unused entries are using memory.
> >>>
> >>> In embedded devices, the rules tend to be fewer.
> >>> In my test system(SH architecture board), it is less than 10000 rules.
> >>>
> >>> 2. Patch
> >>> I made AVTAB_HASH_BITS customizable by Kconfig.
> >>> Allocated hash slots for avtab can be reduced by reducing AVTAB_HASH_BITS.
> >>>
> >>> Attached  patch is for 2.6.22.
> >>> Then, I measured memory usage by /proc/memstat before/after tuning
> >>>
> >>> * Memory usage: SELinux before loading policy.
> >>> 2720k is used.
> >>>
> >>> * Memory usage: SELinux after loading policy(about 8000 rules) before patch
> >>> +1068k increase
> >>>
> >>> * Memory usage: SELinux after loading poilcy(about 8000 rules) after patch.
> >>>   configured AVTAB_HASH_BITS as "13" 
> >>> +876k increase
> >>> -> improved 192k
> >>>
> >>> * Theoretical value:
> >>> - Before tuning: 
> >>>   Number of hashslot 2^15 * 2 
> >>>   Size of hash slot: 4 (sizeof(*(h->htable)))
> >>>   Memory usage = 2^15*2*4 = 262k
> >>>
> >>> - After tuning: 
> >>>   Number of hash slot is 2^13 * 2, 
> >>>   and size of hash slot is 4 (sizeof(*(h->htable)))
> >>>   Memory usage = 2^13*2*4 = 65k 
> >>>   -> 197k should improve, this value is almost the same as measured value.
> >>>
> >>> Following is a patch:
> >>>
> >>> diff -ur security/selinux.orig/Kconfig security/selinux/Kconfig
> >>> --- security/selinux.orig/Kconfig	2007-07-20 17:29:30.000000000 +0900
> >>> +++ security/selinux/Kconfig	2007-07-20 17:45:40.000000000 +0900
> >>> @@ -11,6 +11,17 @@
> >>>  	  from <http://www.nsa.gov/selinux/>.
> >>>  	  If you are unsure how to answer this question, answer N.
> >>>  
> >>> +config SECURITY_SELINUX_AVTAB_HASH_BITS
> >>> +	int "NSA SELinux default AVTAB_HASH_BITS value"
> >>> +	depends on SECURITY_SELINUX && EMBEDDED
> >>> +	range 1 15
> >>> +	default 15
> >>> +	help
> >>> +	  This configures AVTAB_HASH_BITS in avtab.h. The size of avtab hashtable 
> >>> +	  is 2^AVTAB_HASH_BITS. You can improve memory footprint of SELinux by 
> >>> +	  configuring this value appropriately.
> >>> +	  If you are unsure how to answer this question, answer 15.
> >>> +
> >>>  config SECURITY_SELINUX_BOOTPARAM
> >>>  	bool "NSA SELinux boot parameter"
> >>>  	depends on SECURITY_SELINUX
> >>> diff -ur security/selinux.orig/ss/avtab.h security/selinux/ss/avtab.h
> >>> --- security/selinux.orig/ss/avtab.h	2007-07-20 17:29:30.000000000 +0900
> >>> +++ security/selinux/ss/avtab.h	2007-07-20 18:18:56.000000000 +0900
> >>> @@ -74,7 +74,7 @@
> >>>  void avtab_cache_init(void);
> >>>  void avtab_cache_destroy(void);
> >>>  
> >>> -#define AVTAB_HASH_BITS 15
> >>> +#define AVTAB_HASH_BITS CONFIG_SECURITY_SELINUX_AVTAB_HASH_BITS
> >>>  #define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
> >>>  #define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
> >>>       
> >> I'm open to making this configurable, although I'm not sure whether it
> >> should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
> >> of course, it would be runtime computed based on the actual policy size.
> >> Rewriting the avtab and other security server data structures to more
> >> kernel native would be fine with me too - they don't need to match the
> >> userland ones.
> >>
> >> (please cc James, Eric, and me on selinux kernel patches)
> >>     
> >
> > How do you think an idea that the values of AVTAB_HASH_BITS depends
> > on CONFIG_EMBEDDED, more than adding a new Kconfig entry?
> > I think SECURITY_SELINUX_AVTAB_HASH_BITS in Kconfig is too detailed.
> >
> > For example,
> >
> > #ifdef CONFIG_EMBEDDED
> > /* to reduce memory footpoint in embedded devices */
> > #define AVTAB_HASH_BITS (PAGE_SHIFT - 2)
> > #else
> > #define AVTAB_HASH_BITS 15
> > #endif
> >
> > PAGE_SIZE is the minimum unit for vmalloc(), so it is nonsense
> > to require a region less than 2^(PAGE_SHIFT - 2).
> > In addition, CONFIG_EMBEDDED is already set 'y' in defconfig of
> > some of SH, MIPS, ARM and so on. It will fit to your target.
> >
> >   
> I think he was suggesting making it runtime configurable (or even
> automatic based on the size of the loaded policy)
> 
> One should be able to dynamically choose the number of hash buckets
> based off of how many rules are in the policy being loaded, keeping the
> buckets balanced though could be a harder problem to solve.
> 
> > There is another background, although Nakamura-san didn't mentioned.
> > The AVC hit rate is extremely high, so getting longer the chain of
> > avtab hash list does not have maeningful difference in performance.
> >   
> We've had some issues lately with the speed of the avtab, specifically
> around finding reachable user domains. They've been addressed for now
> (my offloading some work to userspace)

Actually, that offloading hasn't been done yet.  All we've done so far
is make the security_get_user_sids() code preemptible.  Providing the
right set of interfaces via selinuxfs so that libselinux can completely
compute reachable user contexts in userspace remains to be done.

>  but there may be others lurking,
> people are finally starting to profile some of this code though.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC] Dynamically deciding number of hash slots for avtab (Was:Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Stephen Smalley]

On Tue, 2007-07-24 at 18:32 +0900, Yuichi Nakamura wrote:
> On Mon, 23 Jul 2007 15:58:31 -0400
> Stephen Smalley  wrote:
> > I'm open to making this configurable, although I'm not sure whether it
> > should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
> > of course, it would be runtime computed based on the actual policy size.
> > Rewriting the avtab and other security server data structures to more
> > kernel native would be fine with me too - they don't need to match the
> > userland ones.
> > 
> > (please cc James, Eric, and me on selinux kernel patches)
> OK, I made patch about that. 
> Please look at patch at the end of this e-mail.
> 
> It decides number of hash slots based on number of unconditional TE rules.
> I looked at avtab_read, and found number of unconditional TE rules are 
> described in binary policy, 
> so it can be used.
> Number of hash slot is 2^n. n is decided based on number of unconditional TE rules.
> If number of unconditional TE rules is 4000, n is 12, so 2^12 = 4096 slots 
> are allocated for te_avtab and te_cond_avtab.

That seems too high; we don't need one slot per rule, especially given
the AVC, as noted by KaiGai.  I'd tune it down further.  And make the
max lower, such that we can always use kmalloc instead of vmalloc.

> I tested the patch against my test policy.
> It contains 8486 unconditional TE rules, 3464 conditional TE rules.
> So number of hash slots for te_avtab is 16384.
> te_cond_avtab is also 16384.
> Before tuning, it was 32768 for both, 
> so saved 32768 hash slots(about 32768*4 = 131k byte).
> 
> I could not find the way to obtain number of "conditinal" TE rules 
> before avtab_init(in cond_read_list).
> If I could obtain number of conditional TE rules before avtab_init,
> number of allocated hash slots for te_cond_avtab would be 4096, can save memory more...
> Does anyone know how to obtain number of conditional TE rules?
> Should policy format be changed for that?

There doesn't appear to be a good way to determine that number presently
(you'd have to make two passes over the conditional lists).  So until we
make another format change (which should bundle up more than just this
one change), I'd say just reuse the number of slots of the unconditional
avtab for the conditional one.

> diff -r -pu security/selinux.orig/ss/avtab.c security/selinux/ss/avtab.c
> --- security/selinux.orig/ss/avtab.c	2007-07-20 17:29:30.000000000 +0900
> +++ security/selinux/ss/avtab.c	2007-07-24 15:11:43.000000000 +0900
> @@ -22,11 +22,11 @@
>  #include "avtab.h"
>  #include "policydb.h"
>  
> -#define AVTAB_HASH(keyp) \
> +#define AVTAB_HASH(keyp,mask)			\
>  ((keyp->target_class + \
>   (keyp->target_type << 2) + \
>   (keyp->source_type << 9)) & \
> - AVTAB_HASH_MASK)
> + mask)

The hash function likely needs to be completely replaced to work well
with smaller number of slots.  Maybe we can leverage
include/linux/hash.h or include/linux/jhash.h?

> @@ -239,19 +239,38 @@ void avtab_destroy(struct avtab *h)
>  	}
>  	vfree(h->htable);
>  	h->htable = NULL;
> +	h->nslot = 0;
> +	h->mask = 0;
>  }
>  
> -
> -int avtab_init(struct avtab *h)
> -{
> +int avtab_init(struct avtab *h, int nrules) {
>  	int i;
> +	u16 mask;
> +	int shift = 0;
> +	int work = nrules;
> +	int nslot;

int?  Or u32?

> +	
> +	if (nrules > MAX_AVTAB_SIZE) {
> +		nslot = MAX_AVTAB_SIZE;
> +		mask =  MAX_AVTAB_HASH_MASK ;
> +	} else {
> +		while(work) {
> +			work  = work>>1;
> +			shift++;
> +		}
> +		mask =(1 << shift) - 1;	
> +		nslot = 1 << shift;

I'd tune this down.  And you only need to compute 1 << shift once.

Not sure if this should still be called avtab_init() as it no longer
happens at policydb_init().  Versus keeping a simple avtab_init() that
just clears the avtab fields and introducing a new avtab_alloc()
function or similar.

> @@ -262,7 +281,7 @@ void avtab_hash_eval(struct avtab *h, ch
>  
>  	slots_used = 0;
>  	max_chain_len = 0;
> -	for (i = 0; i < AVTAB_SIZE; i++) {
> +	for (i = 0; i < h->nslot; i++) {
>  		cur = h->htable[i];
>  		if (cur) {
>  			slots_used++;
> @@ -278,7 +297,7 @@ void avtab_hash_eval(struct avtab *h, ch
>  	}
>  
>  	printk(KERN_DEBUG "%s:  %d entries and %d/%d buckets used, longest "
> -	       "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
> +	       "chain length %d\n", tag, h->nel, slots_used, h->nslot,
>  	       max_chain_len);
>  }

Enable the call to this function by #define'ing DEBUG_HASHES in
policydb.c, and then look at the output not only for your policy but for
a full one.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[James Morris]

On Tue, 24 Jul 2007, Stephen Smalley wrote:

> > There is another background, although Nakamura-san didn't mentioned.
> > The AVC hit rate is extremely high, so getting longer the chain of
> > avtab hash list does not have maeningful difference in performance.
> 
> I have to wonder then whether we should just unconditionally shrink the
> avtab, regardless of embedded or not.  And revert from vmalloc to
> kmalloc for it.

Yes, I think we should aim at having a single value which works for the 
general case, and only make it configurable if the need for 
configurability can be demonstrated.

We'd need to see some performance figures before making the change.


-- 
James Morris
<jmorris@namei.org>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC] Dynamically deciding number of hash slots for avtab (Was:Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Yuichi Nakamura]

Hi.

Thanks for reply.

On Tue, 24 Jul 2007 08:52:03 -0400
Stephen Smalley  wrote:
> On Tue, 2007-07-24 at 18:32 +0900, Yuichi Nakamura wrote:
> > On Mon, 23 Jul 2007 15:58:31 -0400
> > Stephen Smalley  wrote:
> > > I'm open to making this configurable, although I'm not sure whether it
> > > should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
> > > of course, it would be runtime computed based on the actual policy size.
> > > Rewriting the avtab and other security server data structures to more
> > > kernel native would be fine with me too - they don't need to match the
> > > userland ones.
> > > 
> > > (please cc James, Eric, and me on selinux kernel patches)
> > OK, I made patch about that. 
> > Please look at patch at the end of this e-mail.
> > 
> > It decides number of hash slots based on number of unconditional TE rules.
> > I looked at avtab_read, and found number of unconditional TE rules are 
> > described in binary policy, 
> > so it can be used.
> > Number of hash slot is 2^n. n is decided based on number of unconditional TE rules.
> > If number of unconditional TE rules is 4000, n is 12, so 2^12 = 4096 slots 
> > are allocated for te_avtab and te_cond_avtab.
> 
> That seems too high; we don't need one slot per rule, especially given
> the AVC, as noted by KaiGai.  I'd tune it down further.  And make the
> max lower, such that we can always use kmalloc instead of vmalloc.
I see. Please do that.

Are you going to always use kmalloc?
Using kmalloc only when size of hash slots is small does not sound good for you?

> > I tested the patch against my test policy.
> > It contains 8486 unconditional TE rules, 3464 conditional TE rules.
> > So number of hash slots for te_avtab is 16384.
> > te_cond_avtab is also 16384.
> > Before tuning, it was 32768 for both, 
> > so saved 32768 hash slots(about 32768*4 = 131k byte).
> > 
> > I could not find the way to obtain number of "conditinal" TE rules 
> > before avtab_init(in cond_read_list).
> > If I could obtain number of conditional TE rules before avtab_init,
> > number of allocated hash slots for te_cond_avtab would be 4096, can save memory more...
> > Does anyone know how to obtain number of conditional TE rules?
> > Should policy format be changed for that?
> 
> There doesn't appear to be a good way to determine that number presently
> (you'd have to make two passes over the conditional lists).  So until we
> make another format change (which should bundle up more than just this
> one change), I'd say just reuse the number of slots of the unconditional
> avtab for the conditional one.
> 
> > diff -r -pu security/selinux.orig/ss/avtab.c security/selinux/ss/avtab.c
> > --- security/selinux.orig/ss/avtab.c	2007-07-20 17:29:30.000000000 +0900
> > +++ security/selinux/ss/avtab.c	2007-07-24 15:11:43.000000000 +0900
> > @@ -22,11 +22,11 @@
> >  #include "avtab.h"
> >  #include "policydb.h"
> >  
> > -#define AVTAB_HASH(keyp) \
> > +#define AVTAB_HASH(keyp,mask)			\
> >  ((keyp->target_class + \
> >   (keyp->target_type << 2) + \
> >   (keyp->source_type << 9)) & \
> > - AVTAB_HASH_MASK)
> > + mask)
> 
> The hash function likely needs to be completely replaced to work well
> with smaller number of slots.  Maybe we can leverage
> include/linux/hash.h or include/linux/jhash.h?
I will look at them later.

> > @@ -239,19 +239,38 @@ void avtab_destroy(struct avtab *h)
> >  	}
> >  	vfree(h->htable);
> >  	h->htable = NULL;
> > +	h->nslot = 0;
> > +	h->mask = 0;
> >  }
> >  
> > -
> > -int avtab_init(struct avtab *h)
> > -{
> > +int avtab_init(struct avtab *h, int nrules) {
> >  	int i;
> > +	u16 mask;
> > +	int shift = 0;
> > +	int work = nrules;
> > +	int nslot;
> 
> int?  Or u32?
It is mistake, u32.
Fixed.

> > +	
> > +	if (nrules > MAX_AVTAB_SIZE) {
> > +		nslot = MAX_AVTAB_SIZE;
> > +		mask =  MAX_AVTAB_HASH_MASK ;
> > +	} else {
> > +		while(work) {
> > +			work  = work>>1;
> > +			shift++;
> > +		}
> > +		mask =(1 << shift) - 1;	
> > +		nslot = 1 << shift;
> 
> I'd tune this down.  And you only need to compute 1 << shift once.
Fixed about 1<<shift.

> Not sure if this should still be called avtab_init() as it no longer
> happens at policydb_init().  Versus keeping a simple avtab_init() that
> just clears the avtab fields and introducing a new avtab_alloc()
> function or similar.
I prepared avtab_alloc, because it looks cleaner.


> > @@ -262,7 +281,7 @@ void avtab_hash_eval(struct avtab *h, ch
> >  
> >  	slots_used = 0;
> >  	max_chain_len = 0;
> > -	for (i = 0; i < AVTAB_SIZE; i++) {
> > +	for (i = 0; i < h->nslot; i++) {
> >  		cur = h->htable[i];
> >  		if (cur) {
> >  			slots_used++;
> > @@ -278,7 +297,7 @@ void avtab_hash_eval(struct avtab *h, ch
> >  	}
> >  
> >  	printk(KERN_DEBUG "%s:  %d entries and %d/%d buckets used, longest "
> > -	       "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
> > +	       "chain length %d\n", tag, h->nel, slots_used, h->nslot,
> >  	       max_chain_len);
> >  }
> 
> Enable the call to this function by #define'ing DEBUG_HASHES in
> policydb.c, and then look at the output not only for your policy but for
> a full one.
I see.

> -- 
> Stephen Smalley
> National Security Agency

Following is updated patch with trivial fixes.
Using kmalloc, using another hash func are pending

diff -urp security/selinux.orig/ss/avtab.c security/selinux/ss/avtab.c
--- security/selinux.orig/ss/avtab.c	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/ss/avtab.c	2007-07-25 11:26:31.000000000 +0900
@@ -22,11 +22,11 @@
 #include "avtab.h"
 #include "policydb.h"
 
-#define AVTAB_HASH(keyp) \
+#define AVTAB_HASH(keyp,mask)			\
 ((keyp->target_class + \
  (keyp->target_type << 2) + \
  (keyp->source_type << 9)) & \
- AVTAB_HASH_MASK)
+ mask)
 
 static struct kmem_cache *avtab_node_cachep;
 
@@ -62,7 +62,7 @@ static int avtab_insert(struct avtab *h,
 	if (!h)
 		return -EINVAL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key,h->mask);
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {
@@ -102,7 +102,7 @@ avtab_insert_nonunique(struct avtab * h,
 
 	if (!h)
 		return NULL;
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (prev = NULL, cur = h->htable[hvalue];
 	     cur;
 	     prev = cur, cur = cur->next) {
@@ -135,7 +135,7 @@ struct avtab_datum *avtab_search(struct 
 	if (!h)
 		return NULL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 		if (key->source_type == cur->key.source_type &&
 		    key->target_type == cur->key.target_type &&
@@ -170,7 +170,7 @@ avtab_search_node(struct avtab *h, struc
 	if (!h)
 		return NULL;
 
-	hvalue = AVTAB_HASH(key);
+	hvalue = AVTAB_HASH(key, h->mask);
 	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
 		if (key->source_type == cur->key.source_type &&
 		    key->target_type == cur->key.target_type &&
@@ -228,7 +228,7 @@ void avtab_destroy(struct avtab *h)
 	if (!h || !h->htable)
 		return;
 
-	for (i = 0; i < AVTAB_SIZE; i++) {
+	for (i = 0; i < h->nslot; i++) {
 		cur = h->htable[i];
 		while (cur != NULL) {
 			temp = cur;
@@ -239,19 +239,45 @@ void avtab_destroy(struct avtab *h)
 	}
 	vfree(h->htable);
 	h->htable = NULL;
+	h->nslot = 0;
+	h->mask = 0;
 }
 
-
 int avtab_init(struct avtab *h)
 {
+	h->htable = NULL;
+	h->nel = 0;
+	return 0;
+}
+
+int avtab_alloc(struct avtab *h, int nrules) {
 	int i;
+	u16 mask;
+	u32 shift = 0;
+	u32 work = nrules;
+	u32 nslot;
+	
+	if (nrules > MAX_AVTAB_SIZE) {
+		nslot = MAX_AVTAB_SIZE;
+		mask =  MAX_AVTAB_HASH_MASK ;
+	} else {
+		while(work) {
+			work  = work>>1;
+			shift++;
+		}
+		nslot = 1 << shift;
+		mask = nslot - 1;
+	}
 
-	h->htable = vmalloc(sizeof(*(h->htable)) * AVTAB_SIZE);
+	h->htable = vmalloc(sizeof(*(h->htable)) * nslot);
 	if (!h->htable)
 		return -ENOMEM;
-	for (i = 0; i < AVTAB_SIZE; i++)
+	for (i = 0; i < nslot; i++)
 		h->htable[i] = NULL;
 	h->nel = 0;
+	h->nslot = nslot;
+	h->mask = mask;	
+	printk(KERN_DEBUG "SELinux:%d avtab hash slots allocated. Num of rules:%d\n", h->nslot, nrules);
 	return 0;
 }
 
@@ -262,7 +288,7 @@ void avtab_hash_eval(struct avtab *h, ch
 
 	slots_used = 0;
 	max_chain_len = 0;
-	for (i = 0; i < AVTAB_SIZE; i++) {
+	for (i = 0; i < h->nslot; i++) {
 		cur = h->htable[i];
 		if (cur) {
 			slots_used++;
@@ -278,7 +304,7 @@ void avtab_hash_eval(struct avtab *h, ch
 	}
 
 	printk(KERN_DEBUG "%s:  %d entries and %d/%d buckets used, longest "
-	       "chain length %d\n", tag, h->nel, slots_used, AVTAB_SIZE,
+	       "chain length %d\n", tag, h->nel, slots_used, h->nslot,
 	       max_chain_len);
 }
 
@@ -419,6 +445,13 @@ int avtab_read(struct avtab *a, void *fp
 		rc = -EINVAL;
 		goto bad;
 	}
+
+	rc = avtab_alloc(a, nel);
+	if (rc) {
+		rc = -ENOMEM;
+		goto bad;
+	}
+
 	for (i = 0; i < nel; i++) {
 		rc = avtab_read_item(fp,vers, a, avtab_insertf, NULL);
 		if (rc) {
diff -urp security/selinux.orig/ss/avtab.h security/selinux/ss/avtab.h
--- security/selinux.orig/ss/avtab.h	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/ss/avtab.h	2007-07-25 11:14:05.000000000 +0900
@@ -50,9 +50,13 @@ struct avtab_node {
 struct avtab {
 	struct avtab_node **htable;
 	u32 nel;	/* number of elements */
+	u32 nslot;      /* number of hash slots */
+	u16 mask;       /* mask to compute hash func */
+
 };
 
 int avtab_init(struct avtab *);
+int avtab_alloc(struct avtab *, int);
 struct avtab_datum *avtab_search(struct avtab *h, struct avtab_key *k);
 void avtab_destroy(struct avtab *h);
 void avtab_hash_eval(struct avtab *h, char *tag);
@@ -74,11 +78,10 @@ struct avtab_node *avtab_search_node_nex
 void avtab_cache_init(void);
 void avtab_cache_destroy(void);
 
-#define AVTAB_HASH_BITS 15
-#define AVTAB_HASH_BUCKETS (1 << AVTAB_HASH_BITS)
-#define AVTAB_HASH_MASK (AVTAB_HASH_BUCKETS-1)
-
-#define AVTAB_SIZE AVTAB_HASH_BUCKETS
+#define MAX_AVTAB_HASH_BITS 15
+#define MAX_AVTAB_HASH_BUCKETS (1 << MAX_AVTAB_HASH_BITS)
+#define MAX_AVTAB_HASH_MASK (MAX_AVTAB_HASH_BUCKETS-1)
+#define MAX_AVTAB_SIZE MAX_AVTAB_HASH_BUCKETS
 
 #endif	/* _SS_AVTAB_H_ */
 
diff -urp security/selinux.orig/ss/conditional.c security/selinux/ss/conditional.c
--- security/selinux.orig/ss/conditional.c	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/ss/conditional.c	2007-07-25 11:25:32.000000000 +0900
@@ -455,6 +455,12 @@ int cond_read_list(struct policydb *p, v
 		return -1;
 
 	len = le32_to_cpu(buf[0]);
+	
+	rc = avtab_alloc(&(p->te_cond_avtab), p->te_avtab.nel);
+	if (rc) {
+		rc = -ENOMEM;
+		goto err;
+	}
 
 	for (i = 0; i < len; i++) {
 		node = kzalloc(sizeof(struct cond_node), GFP_KERNEL);
diff -urp security/selinux.orig/ss/policydb.c security/selinux/ss/policydb.c
--- security/selinux.orig/ss/policydb.c	2007-07-20 17:29:30.000000000 +0900
+++ security/selinux/ss/policydb.c	2007-07-25 11:13:45.000000000 +0900
@@ -172,22 +172,19 @@ static int policydb_init(struct policydb
 
 	rc = avtab_init(&p->te_avtab);
 	if (rc)
-		goto out_free_symtab;
+		goto out_free_symtab;	
 
 	rc = roles_init(p);
 	if (rc)
-		goto out_free_avtab;
+		goto out_free_symtab;
 
 	rc = cond_policydb_init(p);
 	if (rc)
-		goto out_free_avtab;
+		goto out_free_symtab;
 
 out:
 	return rc;
 
-out_free_avtab:
-	avtab_destroy(&p->te_avtab);
-
 out_free_symtab:
 	for (i = 0; i < SYM_NUM; i++)
 		hashtab_destroy(p->symtab[i].table);


Regards,
-- 
Yuichi Nakamura
Hitachi Software Engineering Co., Ltd.
Japan SELinux Users Group(JSELUG): http://www.selinux.gr.jp/
SELinux Policy Editor: http://seedit.sourceforge.net/


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC] Dynamically deciding number of hash slots for avtab (Was:Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Stephen Smalley]

On Wed, 2007-07-25 at 12:01 +0900, Yuichi Nakamura wrote:
> Hi.
> 
> Thanks for reply.
> 
> On Tue, 24 Jul 2007 08:52:03 -0400
> Stephen Smalley  wrote:
> > On Tue, 2007-07-24 at 18:32 +0900, Yuichi Nakamura wrote:
> > > On Mon, 23 Jul 2007 15:58:31 -0400
> > > Stephen Smalley  wrote:
> > > > I'm open to making this configurable, although I'm not sure whether it
> > > > should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
> > > > of course, it would be runtime computed based on the actual policy size.
> > > > Rewriting the avtab and other security server data structures to more
> > > > kernel native would be fine with me too - they don't need to match the
> > > > userland ones.
> > > > 
> > > > (please cc James, Eric, and me on selinux kernel patches)
> > > OK, I made patch about that. 
> > > Please look at patch at the end of this e-mail.
> > > 
> > > It decides number of hash slots based on number of unconditional TE rules.
> > > I looked at avtab_read, and found number of unconditional TE rules are 
> > > described in binary policy, 
> > > so it can be used.
> > > Number of hash slot is 2^n. n is decided based on number of unconditional TE rules.
> > > If number of unconditional TE rules is 4000, n is 12, so 2^12 = 4096 slots 
> > > are allocated for te_avtab and te_cond_avtab.
> > 
> > That seems too high; we don't need one slot per rule, especially given
> > the AVC, as noted by KaiGai.  I'd tune it down further.  And make the
> > max lower, such that we can always use kmalloc instead of vmalloc.
> I see. Please do that.

What?  Your patch would make this change.

> Are you going to always use kmalloc?
> Using kmalloc only when size of hash slots is small does not sound good for you?

No, we don't want the code conditionally using kmalloc or vmalloc.  Just
pick one and use throughout, setting the max accordingly.

> > > +	
> > > +	if (nrules > MAX_AVTAB_SIZE) {
> > > +		nslot = MAX_AVTAB_SIZE;
> > > +		mask =  MAX_AVTAB_HASH_MASK ;
> > > +	} else {
> > > +		while(work) {
> > > +			work  = work>>1;
> > > +			shift++;
> > > +		}
> > > +		mask =(1 << shift) - 1;	
> > > +		nslot = 1 << shift;
> > 
> > I'd tune this down.  And you only need to compute 1 << shift once.
> Fixed about 1<<shift.

But you still don't need this many slots, I think, as it is ok for the
hash chains to be longer in the avtab.

> > Not sure if this should still be called avtab_init() as it no longer
> > happens at policydb_init().  Versus keeping a simple avtab_init() that
> > just clears the avtab fields and introducing a new avtab_alloc()
> > function or similar.
> I prepared avtab_alloc, because it looks cleaner.

Good.

> Following is updated patch with trivial fixes.
> Using kmalloc, using another hash func are pending

And the hash stats for using it with reference policy?

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: [RFC] Dynamically deciding number of hash slots for avtab (Was:Re: [patch] customizable AVTAB_HASH_BITS for embedded devices

[Yuichi Nakamura]

On Wed, 25 Jul 2007 08:59:40 -0400
Stephen Smalley  wrote:
> On Wed, 2007-07-25 at 12:01 +0900, Yuichi Nakamura wrote:
> > Hi.
> > 
> > Thanks for reply.
> > 
> > On Tue, 24 Jul 2007 08:52:03 -0400
> > Stephen Smalley  wrote:
> > > On Tue, 2007-07-24 at 18:32 +0900, Yuichi Nakamura wrote:
> > > > On Mon, 23 Jul 2007 15:58:31 -0400
> > > > Stephen Smalley  wrote:
> > > > > I'm open to making this configurable, although I'm not sure whether it
> > > > > should be a Kconfig setting or selinuxfs (or sysctl) setting.  Ideally,
> > > > > of course, it would be runtime computed based on the actual policy size.
> > > > > Rewriting the avtab and other security server data structures to more
> > > > > kernel native would be fine with me too - they don't need to match the
> > > > > userland ones.
> > > > > 
> > > > > (please cc James, Eric, and me on selinux kernel patches)
> > > > OK, I made patch about that. 
> > > > Please look at patch at the end of this e-mail.
> > > > 
> > > > It decides number of hash slots based on number of unconditional TE rules.
> > > > I looked at avtab_read, and found number of unconditional TE rules are 
> > > > described in binary policy, 
> > > > so it can be used.
> > > > Number of hash slot is 2^n. n is decided based on number of unconditional TE rules.
> > > > If number of unconditional TE rules is 4000, n is 12, so 2^12 = 4096 slots 
> > > > are allocated for te_avtab and te_cond_avtab.
> > > 
> > > That seems too high; we don't need one slot per rule, especially given
> > > the AVC, as noted by KaiGai.  I'd tune it down further.  And make the
> > > max lower, such that we can always use kmalloc instead of vmalloc.
> > I see. Please do that.
> 
> What?  Your patch would make this change.
OOps, I was misunderstaning.

> > Are you going to always use kmalloc?
> > Using kmalloc only when size of hash slots is small does not sound good for you?
> 
> No, we don't want the code conditionally using kmalloc or vmalloc.  Just
> pick one and use throughout, setting the max accordingly.
I see.


> > > > +	
> > > > +	if (nrules > MAX_AVTAB_SIZE) {
> > > > +		nslot = MAX_AVTAB_SIZE;
> > > > +		mask =  MAX_AVTAB_HASH_MASK ;
> > > > +	} else {
> > > > +		while(work) {
> > > > +			work  = work>>1;
> > > > +			shift++;
> > > > +		}
> > > > +		mask =(1 << shift) - 1;	
> > > > +		nslot = 1 << shift;
> > > 
> > > I'd tune this down.  And you only need to compute 1 << shift once.
> > Fixed about 1<<shift.
> 
> But you still don't need this many slots, I think, as it is ok for the
> hash chains to be longer in the avtab.
I think so, number of slots may be 1/2 or smaller.

> > > Not sure if this should still be called avtab_init() as it no longer
> > > happens at policydb_init().  Versus keeping a simple avtab_init() that
> > > just clears the avtab fields and introducing a new avtab_alloc()
> > > function or similar.
> > I prepared avtab_alloc, because it looks cleaner.
> 
> Good.
> 
> > Following is updated patch with trivial fixes.
> > Using kmalloc, using another hash func are pending
> 
> And the hash stats for using it with reference policy?
Yes, current test policy that I used was refpolicy with small number of modules.

I am now in place where no development environment, within this week...
I will start to measure hash stats in some situations next week.
I also am going to send update for libselinux in another thread, next week.

Regards,
---
Yuichi Nakamura

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[Yuichi Nakamura]

Hi.

In previous discussion,
I posted patch to reduce memory usage of te_avtab, 
and it could save up to 300k memory.

I had to determin two things about te_avtab hash table.
1)  Determin appropriate max number of hash slots.
  It is 32768(MAX_AVTAB_HASH_SIZE) in previous patch.
  If it can be smaller, kmalloc can be used instead of zmalloc.

2) Determin number of hash slots from number of rules.
 In previous patch, number of allocated hash slots is the same as number of rules.

To determin 1), 
We have to see hash stats when big policy is loaded.
I loaded full-size refpolicy(It is strict policy), and looked at hash stats.
# I defined  DEBUG_HASHES to see hash stats.
And varied max number of hash slots.
* Version of refpolicy: selinux-policy-strict-2.4.6-80.fc6
* Num of uncond rules: 166741.

To determin 2), 
We have to see hash stats when small policy is loaded.
I loaded small size refpolicy, and looked at hash stats.
Varied number of hash slots.
* Version of refpoilcy: serefpolicy-2.4.6
* Num of uncond rules: 8188
 # Removed unneeded sources, and made it smaller.

Below is a result of measurement of hash stats.
Please give me advice about appropriate number of hash slots. 

1. Result for 1)
* max table size = 32768
SELinux:32768 avtab hash slots allocated. Num of rules:166741
rules:  166741 entries and 30128/32768 buckets used, longest chain length 34   
-> chain length = 34

* 16384
SELinux:16384 avtab hash slots allocated. Num of rules:166741   
rules:  166741 entries and 16221/16384 buckets used, longest chain length 59   

* 8192
SELinux:8192 avtab hash slots allocated. Num of rules:166741
rules:  166741 entries and 8190/8192 buckets used, longest chain length 97   

*  4096
SELinux:4096 avtab hash slots allocated. Num of rules:166741enfs_contexts
rules:  166741 entries and 4096/4096 buckets used, longest chain length 182

It seems that 4096, 8192 is small, because chain length is 182, 97.
It might be better not to alter max table size, but I am not sure..

2. Result for 2)
* Number of slot = num of rules
SELinux:8192 avtab hash slots allocated. Num of rules:8188
rules:  8188 entries and 3925/8192 buckets used, longest chain length 13     
-> chain length = 13

* Number of slot = num of rules/2
SELinux:4096 avtab hash slots allocated. Num of rules:8188
rules:  8188 entries and 2809/4096 buckets used, longest chain length 21

* Number of slot = num of rules/4
SELinux:2048 avtab hash slots allocated. Num of rules:8188
rules:  8188 entries and 1742/2048 buckets used, longest chain length 35

*  Number of slot = num of rules/8
SELinux:1024 avtab hash slots allocated. Num of rules:8188
rules:  8188 entries and 978/1024 buckets used, longest chain length 64

"Number of slot = num of rules/8" may be too small.
/4 or /2 is good?



Regards,
-- 
Yuichi Nakamura
Hitachi Software Engineering Co., Ltd.
Japan SELinux Users Group(JSELUG): http://www.selinux.gr.jp/
SELinux Policy Editor: http://seedit.sourceforge.net/


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[Stephen Smalley]

On Tue, 2007-08-07 at 18:05 +0900, Yuichi Nakamura wrote:
> Hi.
> 
> In previous discussion,
> I posted patch to reduce memory usage of te_avtab, 
> and it could save up to 300k memory.
> 
> I had to determin two things about te_avtab hash table.
> 1)  Determin appropriate max number of hash slots.
>   It is 32768(MAX_AVTAB_HASH_SIZE) in previous patch.
>   If it can be smaller, kmalloc can be used instead of zmalloc.
> 
> 2) Determin number of hash slots from number of rules.
>  In previous patch, number of allocated hash slots is the same as number of rules.
> 
> To determin 1), 
> We have to see hash stats when big policy is loaded.
> I loaded full-size refpolicy(It is strict policy), and looked at hash stats.
> # I defined  DEBUG_HASHES to see hash stats.
> And varied max number of hash slots.
> * Version of refpolicy: selinux-policy-strict-2.4.6-80.fc6
> * Num of uncond rules: 166741.
> 
> To determin 2), 
> We have to see hash stats when small policy is loaded.
> I loaded small size refpolicy, and looked at hash stats.
> Varied number of hash slots.
> * Version of refpoilcy: serefpolicy-2.4.6
> * Num of uncond rules: 8188
>  # Removed unneeded sources, and made it smaller.
> 
> Below is a result of measurement of hash stats.
> Please give me advice about appropriate number of hash slots. 
> 
> 1. Result for 1)
> * max table size = 32768
> SELinux:32768 avtab hash slots allocated. Num of rules:166741
> rules:  166741 entries and 30128/32768 buckets used, longest chain length 34   
> -> chain length = 34

Doesn't sound like the hash function is doing so well anymore.

> * 16384
> SELinux:16384 avtab hash slots allocated. Num of rules:166741   
> rules:  166741 entries and 16221/16384 buckets used, longest chain length 59   
> 
> * 8192
> SELinux:8192 avtab hash slots allocated. Num of rules:166741
> rules:  166741 entries and 8190/8192 buckets used, longest chain length 97   
> 
> *  4096
> SELinux:4096 avtab hash slots allocated. Num of rules:166741enfs_contexts
> rules:  166741 entries and 4096/4096 buckets used, longest chain length 182
>
> 
> It seems that 4096, 8192 is small, because chain length is 182, 97.
> It might be better not to alter max table size, but I am not sure..

If you had adjusted the hash function too, you could have gotten better
results.

> 2. Result for 2)
> * Number of slot = num of rules
> SELinux:8192 avtab hash slots allocated. Num of rules:8188
> rules:  8188 entries and 3925/8192 buckets used, longest chain length 13     
> -> chain length = 13
> 
> * Number of slot = num of rules/2
> SELinux:4096 avtab hash slots allocated. Num of rules:8188
> rules:  8188 entries and 2809/4096 buckets used, longest chain length 21
> 
> * Number of slot = num of rules/4
> SELinux:2048 avtab hash slots allocated. Num of rules:8188
> rules:  8188 entries and 1742/2048 buckets used, longest chain length 35
> 
> *  Number of slot = num of rules/8
> SELinux:1024 avtab hash slots allocated. Num of rules:8188
> rules:  8188 entries and 978/1024 buckets used, longest chain length 64
> 
> "Number of slot = num of rules/8" may be too small.
> /4 or /2 is good?

Try tuning the hash function.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[Yuichi Nakamura]

On Tue, 07 Aug 2007 08:33:29 -0400
Stephen Smalley  wrote:
>If you had adjusted the hash function too, you could have gotten better
results.
<snip>
> Try tuning the hash function.

Thanks for advice.
So, I tried another hash function.
I found jhash_3words in linux/jhash.h,
it calculates hash value based on 3 args. 

I replaced AVTAB_HASH using jhash like below, 
and measured hash stats again.

#define AVTAB_HASH(keyp,mask)	\
(jhash_3words((u32)(keyp->target_class), \
 (u32)(keyp->target_type), \
 (u32)(keyp->source_type), 0) & \
 mask)

Following is result.

1. Result for 1) (Full strict refpolicy)

* max table size = 32768
SELinux:32768 avtab hash slots allocated. Num of rules:166741
- default hash
rules:  166741 entries and 30128/32768 buckets used, longest chain length 34   
- jhash
rules:  166741 entries and 32391/32768 buckets used, longest chain length 21  

* 16384
SELinux:16384 avtab hash slots allocated. Num of rules:166741   
- default
rules:  166741 entries and 16221/16384 buckets used, longest chain length 59   
- jhash
rules:  166741 entries and 16382/16384 buckets used, longest chain length 27

* 8192
SELinux:8192 avtab hash slots allocated. Num of rules:166741
- default
rules:  166741 entries and 8190/8192 buckets used, longest chain length 97   
- jhash
rules:  166741 entries and 8192/8192 buckets used, longest chain length 41 

*  4096
SELinux:4096 avtab hash slots allocated. Num of rules:166741enfs_contexts
- default
rules:  166741 entries and 4096/4096 buckets used, longest chain length 182
- jhash
rules:  166741 entries and 4096/4096 buckets used, longest chain length 67 

jhash is better.
If we use jhash, max table size could be 16384 or 8192..

2. Result for 2) (smaller refpolicy)

* Number of slot = num of rules
SELinux:8192 avtab hash slots allocated. Num of rules:8188
- default
rules:  8188 entries and 3925/8192 buckets used, longest chain length 13
- jhash
rules:  8188 entries and 5053/8192 buckets used, longest chain length 7 

* Number of slot = num of rules/2
SELinux:4096 avtab hash slots allocated. Num of rules:8188
- default
rules:  8188 entries and 2809/4096 buckets used, longest chain length 21
- jhash
rules:  8188 entries and 3466/4096 buckets used, longest chain length 9 

* Number of slot = num of rules/4
SELinux:2048 avtab hash slots allocated. Num of rules:8188
- default
rules:  8188 entries and 1742/2048 buckets used, longest chain length 35
- jhash
rules:  8188 entries and 1991/2048 buckets used, longest chain length 12 

*  Number of slot = num of rules/8
SELinux:1024 avtab hash slots allocated. Num of rules:8188
- default
rules:  8188 entries and 978/1024 buckets used, longest chain length 64
- jhash
rules:  8188 entries and 1024/1024 buckets used, longest chain length 22

jhash is also better.

Can We use jhash ?

Regards,
-- 
Yuichi Nakamura
Hitachi Software Engineering Co., Ltd.
Japan SELinux Users Group(JSELUG): http://www.selinux.gr.jp/
SELinux Policy Editor: http://seedit.sourceforge.net/


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[James Morris]

On Wed, 8 Aug 2007, Yuichi Nakamura wrote:

> * Number of slot = num of rules/2
> SELinux:4096 avtab hash slots allocated. Num of rules:8188
> - default
> rules:  8188 entries and 2809/4096 buckets used, longest chain length 21
> - jhash
> rules:  8188 entries and 3466/4096 buckets used, longest chain length 9 

This looks pretty good.

What is the performance overhead of jhash vs. the existing hash?

(You could probably make a kernel module which calls the avc in a loop 
with some repeatable sequence of paramters).


-- 
James Morris
<jmorris@namei.org>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[Stephen Smalley]

On Wed, 2007-08-08 at 15:00 +0900, Yuichi Nakamura wrote:
> On Tue, 07 Aug 2007 08:33:29 -0400
> Stephen Smalley  wrote:
> >If you had adjusted the hash function too, you could have gotten better
> results.
> <snip>
> > Try tuning the hash function.
> 
> Thanks for advice.
> So, I tried another hash function.
> I found jhash_3words in linux/jhash.h,
> it calculates hash value based on 3 args. 
> 
> I replaced AVTAB_HASH using jhash like below, 
> and measured hash stats again.
> 
> #define AVTAB_HASH(keyp,mask)	\
> (jhash_3words((u32)(keyp->target_class), \
>  (u32)(keyp->target_type), \
>  (u32)(keyp->source_type), 0) & \
>  mask)
> 
> Following is result.
> 
> 1. Result for 1) (Full strict refpolicy)
> 
> * max table size = 32768
> SELinux:32768 avtab hash slots allocated. Num of rules:166741
> - default hash
> rules:  166741 entries and 30128/32768 buckets used, longest chain length 34   
> - jhash
> rules:  166741 entries and 32391/32768 buckets used, longest chain length 21  
> 
> * 16384
> SELinux:16384 avtab hash slots allocated. Num of rules:166741   
> - default
> rules:  166741 entries and 16221/16384 buckets used, longest chain length 59   
> - jhash
> rules:  166741 entries and 16382/16384 buckets used, longest chain length 27
> 
> * 8192
> SELinux:8192 avtab hash slots allocated. Num of rules:166741
> - default
> rules:  166741 entries and 8190/8192 buckets used, longest chain length 97   
> - jhash
> rules:  166741 entries and 8192/8192 buckets used, longest chain length 41 
> 
> *  4096
> SELinux:4096 avtab hash slots allocated. Num of rules:166741enfs_contexts
> - default
> rules:  166741 entries and 4096/4096 buckets used, longest chain length 182
> - jhash
> rules:  166741 entries and 4096/4096 buckets used, longest chain length 67 
> 
> jhash is better.
> If we use jhash, max table size could be 16384 or 8192..
> 
> 2. Result for 2) (smaller refpolicy)
> 
> * Number of slot = num of rules
> SELinux:8192 avtab hash slots allocated. Num of rules:8188
> - default
> rules:  8188 entries and 3925/8192 buckets used, longest chain length 13
> - jhash
> rules:  8188 entries and 5053/8192 buckets used, longest chain length 7 
> 
> * Number of slot = num of rules/2
> SELinux:4096 avtab hash slots allocated. Num of rules:8188
> - default
> rules:  8188 entries and 2809/4096 buckets used, longest chain length 21
> - jhash
> rules:  8188 entries and 3466/4096 buckets used, longest chain length 9 
> 
> * Number of slot = num of rules/4
> SELinux:2048 avtab hash slots allocated. Num of rules:8188
> - default
> rules:  8188 entries and 1742/2048 buckets used, longest chain length 35
> - jhash
> rules:  8188 entries and 1991/2048 buckets used, longest chain length 12 
> 
> *  Number of slot = num of rules/8
> SELinux:1024 avtab hash slots allocated. Num of rules:8188
> - default
> rules:  8188 entries and 978/1024 buckets used, longest chain length 64
> - jhash
> rules:  8188 entries and 1024/1024 buckets used, longest chain length 22
> 
> jhash is also better.
> 
> Can We use jhash ?

I think so, as long as it doesn't impose a significant overhead.
Running some benchmarks would be useful, although the AVC will hide much
of it.  Might want to set /selinux/avc/cache_threshold to a low value
for measurement so that you see the actual cost of the avtab lookups.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[Yuichi Nakamura]

On Wed, 8 Aug 2007 07:43:00 -0700 (PDT)
James Morris  wrote:

> On Wed, 8 Aug 2007, Yuichi Nakamura wrote:
> 
> > * Number of slot = num of rules/2
> > SELinux:4096 avtab hash slots allocated. Num of rules:8188
> > - default
> > rules:  8188 entries and 2809/4096 buckets used, longest chain length 21
> > - jhash
> > rules:  8188 entries and 3466/4096 buckets used, longest chain length 9 
> 
> This looks pretty good.
> 
> What is the performance overhead of jhash vs. the existing hash?
I am not sure now.

> 
> (You could probably make a kernel module which calls the avc in a loop 
> with some repeatable sequence of paramters).
OK, I will try it next.

> 
> 
> -- 
> James Morris
> <jmorris@namei.org>
> 
> --
> This message was distributed to subscribers of the selinux mailing list.
> If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
> the words "unsubscribe selinux" without quotes as the message.

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[Stephen Smalley]

On Wed, 2007-08-08 at 23:58 +0900, Yuichi Nakamura wrote:
> On Wed, 8 Aug 2007 07:43:00 -0700 (PDT)
> James Morris  wrote:
> 
> > On Wed, 8 Aug 2007, Yuichi Nakamura wrote:
> > 
> > > * Number of slot = num of rules/2
> > > SELinux:4096 avtab hash slots allocated. Num of rules:8188
> > > - default
> > > rules:  8188 entries and 2809/4096 buckets used, longest chain length 21
> > > - jhash
> > > rules:  8188 entries and 3466/4096 buckets used, longest chain length 9 
> > 
> > This looks pretty good.
> > 
> > What is the performance overhead of jhash vs. the existing hash?
> I am not sure now.
> 
> > 
> > (You could probably make a kernel module which calls the avc in a loop 
> > with some repeatable sequence of paramters).
> OK, I will try it next.

If so, don't bother calling the avc - call avtab_search directly.

-- 
Stephen Smalley
National Security Agency


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[Yuichi Nakamura]

On Wed, 08 Aug 2007 10:45:12 -0400
Stephen Smalley  wrote:
<snip>
> > jhash is also better.
> > 
> > Can We use jhash ?
> 
> I think so, as long as it doesn't impose a significant overhead.
> Running some benchmarks would be useful, although the AVC will hide much
> of it.  Might want to set /selinux/avc/cache_threshold to a low value
> for measurement so that you see the actual cost of the avtab lookups.
I will try  it. 
Please wait for next result.

> 
> -- 
> Stephen Smalley
> National Security Agency
> 
> 
> --
> This message was distributed to subscribers of the selinux mailing list.
> If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
> the words "unsubscribe selinux" without quotes as the message.

Regards,
Yuichi Nakamura

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[James Morris]

On Wed, 8 Aug 2007, Stephen Smalley wrote:

> > Can We use jhash ?
> 
> I think so, as long as it doesn't impose a significant overhead.

It's now used extensively in the networking code, so I suspect it will be 
ok (and unlikely to be a bottleneck for SELinux), but yep, we do need to 
measure it.

-- 
James Morris
<jmorris@namei.org>

--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.

Re: Appropriate number of hash slots for te_avtab(Was:Re: [RFC] Dynamically deciding number of hash slots for avtab

[Yuichi Nakamura]

On Wed, 8 Aug 2007 08:35:09 -0700 (PDT)
James Morris wrote:
> On Wed, 8 Aug 2007, Stephen Smalley wrote:
> 
> > > Can We use jhash ?
> > 
> > I think so, as long as it doesn't impose a significant overhead.
> 
> It's now used extensively in the networking code, so I suspect it will be 
> ok (and unlikely to be a bottleneck for SELinux), but yep, we do need to 
> measure it.

I've measured performance of hash functions in avtab.c.
I compared default hash and jhash.

To measure performance, I measured time to call security_compute_av.
I measured time 10000 security_compute_av call from system boot, 
like below code.

int avc_has_perm_noaudit(u32 ssid, u32 tsid,
                         u16 tclass, u32 requested,
                         struct av_decision *avd)
{
	struct avc_node *node;
	struct avc_entry entry, *p_ae;
	int rc = 0;
	u32 denied;
+	unsigned long long t0,t1;
+	unsigned long long t2=0;
+	static unsigned long long t3=0;
+	static int count = 0;
+	static int flag = 1;
+	static int max = 10000;
+	int i = 0;


	rcu_read_lock();
+	if (flag && ss_initialized) {
+		t0 = sched_clock();
+		security_compute_av(ssid,tsid,tclass, requested, &entry.avd);
+		t1 = sched_clock();
+		t2 = t1 - t0;
+		t3 += t2;
+		count ++;
+	} 
+	if (flag && (count == max)) {
+		flag = 0;
+		printk("SELinux:security_compute_av execution time:%Lu\n", t3);
+
+	}

security_compute_av is located at the entry of avc_has_perm_no_audit.
And nano second to call 10000 security_compute_av function is printed out.

I did this benchmark varying hash table size, policy and hash functions.
I summarized result with hash table chain length(those I measured in previous message).
Below is a result.

1. Result for 1) (Full strict refpolicy)
* max table size = 32768
        usage of slot  chain-length  time to call 10000 security_compute_av(sec)
default: 30128/32768   34            6.95
jhash  : 32391/32768   21            7.28

* 16384
default:  16221/16384 59  6.91
jhash:    16382/16384 27  7.28

* 8192
default: 8190/8192 97 7.15
jhash:   8192/8192 41 7.78

*  4096
default: 4096/4096  182 7.73
jhash:   4096/4096  67  8.87

2. Result for 2) (smaller refpolicy)
* Number of slot = num of rules
        usage of slot  chain-length time(sec)
default : 3925/8192      13           9.65
jhash   : 5053/8192      7           10.1

* Number of slot = num of rules/2
default : 2809/4096  21   9.63
jhash   : 3466/4096   9   10.35

* Number of slot = num of rules/4
default: 1742/2048  35    9.69
jhash:   1991/2048  12   10.35

*  Number of slot = num of rules/8
default: 978/1024    64  10.02
jhash  : 1024/1024   22  11.23

* Number of slot = default(32768)
default: 5993/32768 7   9.99
jhash:  6975/32768  4  10.50

In both case,
about chain length, jhash is better,
however, performance is worse !
so is it better not to use jhash??

About max number of hash slots, 
we can use 16384 or 8192, because performance is almost the same.
About number of dynamically allocated hash slots, 
we can use slot = num of rules /4?

And there is one strange thing.
Performance is worse in smaller policy.
For 32768 hash slots, default hash function, 
6.95(s) for strict policy, 9.99(s) for smaller refpolicy.

Any comments, please.

Regards,
-- 
Yuichi Nakamura
Hitachi Software Engineering Co., Ltd.
Japan SELinux Users Group(JSELUG): http://www.selinux.gr.jp/
SELinux Policy Editor: http://seedit.sourceforge.net/


--
This message was distributed to subscribers of the selinux mailing list.
If you no longer wish to subscribe, send mail to majordomo@tycho.nsa.gov with
the words "unsubscribe selinux" without quotes as the message.