[RFCv2] security: smack: add a hash table to quicken smk_find_entry()

[RFCv2] security: smack: add a hash table to quicken smk_find_entry()

[Tomasz Stanislawski]

Hi everyone,
I have updated the patch after Casey's review.
The fixes from the recent version are:
- update naming according to Casey's guidelines
- fix coding style issues
- use hlist interface instead of double-linked list to reduce memory
  usage and to speed-up initialization
- drop Dan Bernstein hash function in favor of more standard full_name_hash
- adjust the number of hash slots basing on measurements

Regards,
Tomasz Stanislawski

Tomasz Stanislawski (1):
  security: smack: add a hash table to quicken smk_find_entry()

 security/smack/smack.h        |    5 +++++
 security/smack/smack_access.c |   30 +++++++++++++++++++++++++++---
 security/smack/smack_lsm.c    |   12 ++++++------
 3 files changed, 38 insertions(+), 9 deletions(-)

-- 
1.7.9.5

[RFCv2] security: smack: add a hash table to quicken smk_find_entry()

[Tomasz Stanislawski]

This patch adds a hash table to quicken searching of a smack label by its name.

Basically, the patch improves performance of SMACK initialization.  Parsing of
rules involves translation from a string to a smack_known (aka label) entity
which is done in smk_find_entry().

The current implementation of the function iterates over a global list of
smack_known resulting in O(N) complexity for smk_find_entry().  The total
complexity of SMACK initialization becomes O(rules * labels).  Therefore it
scales quadratically with a complexity of a system.

Applying the patch reduced the complexity of smk_find_entry() to O(1) as long
as number of label is in hundreds. If the number of labels is increased please
update SMACK_HASH_SLOTS constant defined in security/smack/smack.h. Introducing
the configuration of this constant with Kconfig or cmdline might be a good
idea.

The size of the hash table was adjusted experimentally.  The rule set used by
TIZEN contains circa 17K rules for 500 labels.  The table above contains
results of SMACK initialization using 'time smackctl apply' bash command.
The 'Ref' is a kernel without this patch applied. The consecutive values
refers to value of SMACK_HASH_SLOTS.  Every measurement was repeated three
times to reduce noise.

     |  Ref  |   1   |   2   |   4   |   8   |   16  |   32  |   64  |  128  |  256  |  512
--------------------------------------------------------------------------------------------
Run1 | 1.156 | 1.096 | 0.883 | 0.764 | 0.692 | 0.667 | 0.649 | 0.633 | 0.634 | 0.629 | 0.620
Run2 | 1.156 | 1.111 | 0.885 | 0.764 | 0.694 | 0.661 | 0.649 | 0.651 | 0.634 | 0.638 | 0.623
Run3 | 1.160 | 1.107 | 0.886 | 0.764 | 0.694 | 0.671 | 0.661 | 0.638 | 0.631 | 0.624 | 0.638
AVG  | 1.157 | 1.105 | 0.885 | 0.764 | 0.693 | 0.666 | 0.653 | 0.641 | 0.633 | 0.630 | 0.627

Surprisingly, a single hlist is slightly faster than a double-linked list.
The speed-up saturates near 64 slots.  Therefore I chose value 128 to provide
some margin if more labels were used.
It looks that IO becomes a new bottleneck.

Signed-off-by: Tomasz Stanislawski <t.stanislaws@samsung.com>
---
 security/smack/smack.h        |    5 +++++
 security/smack/smack_access.c |   30 +++++++++++++++++++++++++++---
 security/smack/smack_lsm.c    |   12 ++++++------
 3 files changed, 38 insertions(+), 9 deletions(-)

diff --git a/security/smack/smack.h b/security/smack/smack.h
index 339614c..b1d9441 100644
--- a/security/smack/smack.h
+++ b/security/smack/smack.h
@@ -53,6 +53,7 @@
  */
 struct smack_known {
 	struct list_head		list;
+	struct hlist_node		smk_hashed;
 	char				*smk_known;
 	u32				smk_secid;
 	struct netlbl_lsm_secattr	smk_netlabel;	/* on wire labels */
@@ -222,6 +223,7 @@ char *smk_parse_smack(const char *string, int len);
 int smk_netlbl_mls(int, char *, struct netlbl_lsm_secattr *, int);
 char *smk_import(const char *, int);
 struct smack_known *smk_import_entry(const char *, int);
+void smk_insert_entry(struct smack_known *skp);
 struct smack_known *smk_find_entry(const char *);
 u32 smack_to_secid(const char *);
 
@@ -247,6 +249,9 @@ extern struct list_head smk_netlbladdr_list;
 
 extern struct security_operations smack_ops;
 
+#define SMACK_HASH_SLOTS 128
+extern struct hlist_head smack_known_hash[SMACK_HASH_SLOTS];
+
 /*
  * Is the directory transmuting?
  */
diff --git a/security/smack/smack_access.c b/security/smack/smack_access.c
index 6a0377f..b598c32 100644
--- a/security/smack/smack_access.c
+++ b/security/smack/smack_access.c
@@ -325,6 +325,25 @@ void smack_log(char *subject_label, char *object_label, int request,
 
 DEFINE_MUTEX(smack_known_lock);
 
+struct hlist_head smack_known_hash[SMACK_HASH_SLOTS];
+
+/**
+ * smk_insert_entry - insert a smack label into a hash map,
+ *
+ * this function must be called under smack_known_lock
+ */
+void smk_insert_entry(struct smack_known *skp)
+{
+	unsigned int hash;
+	struct hlist_head *head;
+
+	hash = full_name_hash(skp->smk_known, strlen(skp->smk_known));
+	head = &smack_known_hash[hash & (SMACK_HASH_SLOTS - 1)];
+
+	hlist_add_head_rcu(&skp->smk_hashed, head);
+	list_add_rcu(&skp->list, &smack_known_list);
+}
+
 /**
  * smk_find_entry - find a label on the list, return the list entry
  * @string: a text string that might be a Smack label
@@ -334,12 +353,17 @@ DEFINE_MUTEX(smack_known_lock);
  */
 struct smack_known *smk_find_entry(const char *string)
 {
+	unsigned int hash;
+	struct hlist_head *head;
+	struct hlist_node *cursor;
 	struct smack_known *skp;
 
-	list_for_each_entry_rcu(skp, &smack_known_list, list) {
+	hash = full_name_hash(string, strlen(string));
+	head = &smack_known_hash[hash & (SMACK_HASH_SLOTS - 1)];
+
+	hlist_for_each_entry_rcu(skp, cursor, head, smk_hashed)
 		if (strcmp(skp->smk_known, string) == 0)
 			return skp;
-	}
 
 	return NULL;
 }
@@ -475,7 +499,7 @@ struct smack_known *smk_import_entry(const char *string, int len)
 		 * Make sure that the entry is actually
 		 * filled before putting it on the list.
 		 */
-		list_add_rcu(&skp->list, &smack_known_list);
+		smk_insert_entry(skp);
 		goto unlockout;
 	}
 	/*
diff --git a/security/smack/smack_lsm.c b/security/smack/smack_lsm.c
index 6a08330..6cabca6 100644
--- a/security/smack/smack_lsm.c
+++ b/security/smack/smack_lsm.c
@@ -3868,12 +3868,12 @@ static __init void init_smack_known_list(void)
 	/*
 	 * Create the known labels list
 	 */
-	list_add(&smack_known_huh.list, &smack_known_list);
-	list_add(&smack_known_hat.list, &smack_known_list);
-	list_add(&smack_known_star.list, &smack_known_list);
-	list_add(&smack_known_floor.list, &smack_known_list);
-	list_add(&smack_known_invalid.list, &smack_known_list);
-	list_add(&smack_known_web.list, &smack_known_list);
+	smk_insert_entry(&smack_known_huh);
+	smk_insert_entry(&smack_known_hat);
+	smk_insert_entry(&smack_known_star);
+	smk_insert_entry(&smack_known_floor);
+	smk_insert_entry(&smack_known_invalid);
+	smk_insert_entry(&smack_known_web);
 }
 
 /**
-- 
1.7.9.5

Re: [RFCv2] security: smack: add a hash table to quicken smk_find_entry()

[Casey Schaufler]

On 6/11/2013 5:55 AM, Tomasz Stanislawski wrote:
> This patch adds a hash table to quicken searching of a smack label by its name.
>
> Basically, the patch improves performance of SMACK initialization.  Parsing of
> rules involves translation from a string to a smack_known (aka label) entity
> which is done in smk_find_entry().

There is one place where this is done, and that is in smk_import_entry().

There is another place where labels are looked up, and that is in
smack_from_secattr(). Can you apply this enhancement there, too?

>
> The current implementation of the function iterates over a global list of
> smack_known resulting in O(N) complexity for smk_find_entry().  The total
> complexity of SMACK initialization becomes O(rules * labels).  Therefore it
> scales quadratically with a complexity of a system.
>
> Applying the patch reduced the complexity of smk_find_entry() to O(1) as long
> as number of label is in hundreds. If the number of labels is increased please
> update SMACK_HASH_SLOTS constant defined in security/smack/smack.h. Introducing
> the configuration of this constant with Kconfig or cmdline might be a good
> idea.
>
> The size of the hash table was adjusted experimentally.  The rule set used by
> TIZEN contains circa 17K rules for 500 labels.  The table above contains
> results of SMACK initialization using 'time smackctl apply' bash command.
> The 'Ref' is a kernel without this patch applied. The consecutive values
> refers to value of SMACK_HASH_SLOTS.  Every measurement was repeated three
> times to reduce noise.
>
>      |  Ref  |   1   |   2   |   4   |   8   |   16  |   32  |   64  |  128  |  256  |  512
> --------------------------------------------------------------------------------------------
> Run1 | 1.156 | 1.096 | 0.883 | 0.764 | 0.692 | 0.667 | 0.649 | 0.633 | 0.634 | 0.629 | 0.620
> Run2 | 1.156 | 1.111 | 0.885 | 0.764 | 0.694 | 0.661 | 0.649 | 0.651 | 0.634 | 0.638 | 0.623
> Run3 | 1.160 | 1.107 | 0.886 | 0.764 | 0.694 | 0.671 | 0.661 | 0.638 | 0.631 | 0.624 | 0.638
> AVG  | 1.157 | 1.105 | 0.885 | 0.764 | 0.693 | 0.666 | 0.653 | 0.641 | 0.633 | 0.630 | 0.627

                 4%      20%     14%     9%      4%      2%      2%      1%      <1%


You get 4% by going to the hlist. The improvement is trivial after 16 slots.
If you have 500 labels and 128 slots that's an average of 4 labels per slot.
That's an awfully big hash table for so few labels and so little performance
gain over what you get with 16 slots. Plus, 500 labels is a huge number of
labels. Most Smack systems should be using far fewer than that. 

>
> Surprisingly, a single hlist is slightly faster than a double-linked list.
> The speed-up saturates near 64 slots.  Therefore I chose value 128 to provide
> some margin if more labels were used.
> It looks that IO becomes a new bottleneck.
>
> Signed-off-by: Tomasz Stanislawski <t.stanislaws@samsung.com>
> ---
>  security/smack/smack.h        |    5 +++++
>  security/smack/smack_access.c |   30 +++++++++++++++++++++++++++---
>  security/smack/smack_lsm.c    |   12 ++++++------
>  3 files changed, 38 insertions(+), 9 deletions(-)
>
> diff --git a/security/smack/smack.h b/security/smack/smack.h
> index 339614c..b1d9441 100644
> --- a/security/smack/smack.h
> +++ b/security/smack/smack.h
> @@ -53,6 +53,7 @@
>   */
>  struct smack_known {
>  	struct list_head		list;
> +	struct hlist_node		smk_hashed;
>  	char				*smk_known;
>  	u32				smk_secid;
>  	struct netlbl_lsm_secattr	smk_netlabel;	/* on wire labels */
> @@ -222,6 +223,7 @@ char *smk_parse_smack(const char *string, int len);
>  int smk_netlbl_mls(int, char *, struct netlbl_lsm_secattr *, int);
>  char *smk_import(const char *, int);
>  struct smack_known *smk_import_entry(const char *, int);
> +void smk_insert_entry(struct smack_known *skp);
>  struct smack_known *smk_find_entry(const char *);
>  u32 smack_to_secid(const char *);
>  
> @@ -247,6 +249,9 @@ extern struct list_head smk_netlbladdr_list;
>  
>  extern struct security_operations smack_ops;
>  
> +#define SMACK_HASH_SLOTS 128

As outlined above, make this 16.

> +extern struct hlist_head smack_known_hash[SMACK_HASH_SLOTS];
> +
>  /*
>   * Is the directory transmuting?
>   */
> diff --git a/security/smack/smack_access.c b/security/smack/smack_access.c
> index 6a0377f..b598c32 100644
> --- a/security/smack/smack_access.c
> +++ b/security/smack/smack_access.c
> @@ -325,6 +325,25 @@ void smack_log(char *subject_label, char *object_label, int request,
>  
>  DEFINE_MUTEX(smack_known_lock);
>  
> +struct hlist_head smack_known_hash[SMACK_HASH_SLOTS];
> +
> +/**
> + * smk_insert_entry - insert a smack label into a hash map,
> + *
> + * this function must be called under smack_known_lock
> + */
> +void smk_insert_entry(struct smack_known *skp)
> +{
> +	unsigned int hash;
> +	struct hlist_head *head;
> +
> +	hash = full_name_hash(skp->smk_known, strlen(skp->smk_known));
> +	head = &smack_known_hash[hash & (SMACK_HASH_SLOTS - 1)];
> +
> +	hlist_add_head_rcu(&skp->smk_hashed, head);
> +	list_add_rcu(&skp->list, &smack_known_list);
> +}
> +
>  /**
>   * smk_find_entry - find a label on the list, return the list entry
>   * @string: a text string that might be a Smack label
> @@ -334,12 +353,17 @@ DEFINE_MUTEX(smack_known_lock);
>   */
>  struct smack_known *smk_find_entry(const char *string)
>  {
> +	unsigned int hash;
> +	struct hlist_head *head;
> +	struct hlist_node *cursor;
>  	struct smack_known *skp;
>  
> -	list_for_each_entry_rcu(skp, &smack_known_list, list) {
> +	hash = full_name_hash(string, strlen(string));
> +	head = &smack_known_hash[hash & (SMACK_HASH_SLOTS - 1)];
> +
> +	hlist_for_each_entry_rcu(skp, cursor, head, smk_hashed)
>  		if (strcmp(skp->smk_known, string) == 0)
>  			return skp;
> -	}
>  
>  	return NULL;
>  }
> @@ -475,7 +499,7 @@ struct smack_known *smk_import_entry(const char *string, int len)
>  		 * Make sure that the entry is actually
>  		 * filled before putting it on the list.
>  		 */
> -		list_add_rcu(&skp->list, &smack_known_list);
> +		smk_insert_entry(skp);
>  		goto unlockout;
>  	}
>  	/*
> diff --git a/security/smack/smack_lsm.c b/security/smack/smack_lsm.c
> index 6a08330..6cabca6 100644
> --- a/security/smack/smack_lsm.c
> +++ b/security/smack/smack_lsm.c
> @@ -3868,12 +3868,12 @@ static __init void init_smack_known_list(void)
>  	/*
>  	 * Create the known labels list
>  	 */
> -	list_add(&smack_known_huh.list, &smack_known_list);
> -	list_add(&smack_known_hat.list, &smack_known_list);
> -	list_add(&smack_known_star.list, &smack_known_list);
> -	list_add(&smack_known_floor.list, &smack_known_list);
> -	list_add(&smack_known_invalid.list, &smack_known_list);
> -	list_add(&smack_known_web.list, &smack_known_list);
> +	smk_insert_entry(&smack_known_huh);
> +	smk_insert_entry(&smack_known_hat);
> +	smk_insert_entry(&smack_known_star);
> +	smk_insert_entry(&smack_known_floor);
> +	smk_insert_entry(&smack_known_invalid);
> +	smk_insert_entry(&smack_known_web);
>  }
>  
>  /**

Re: [RFCv2] security: smack: add a hash table to quicken smk_find_entry()

[Tomasz Stanislawski]

Hi Casey,
Thank you for your review.
Please refer to comments below.

On 06/12/2013 07:11 AM, Casey Schaufler wrote:
> On 6/11/2013 5:55 AM, Tomasz Stanislawski wrote:
>> This patch adds a hash table to quicken searching of a smack label by its name.
>>
>> Basically, the patch improves performance of SMACK initialization.  Parsing of
>> rules involves translation from a string to a smack_known (aka label) entity
>> which is done in smk_find_entry().
> 
> There is one place where this is done, and that is in smk_import_entry().
> 
> There is another place where labels are looked up, and that is in
> smack_from_secattr(). Can you apply this enhancement there, too?
> 

The overmentioned function contains following check:

                        if (memcmp(sap->attr.mls.cat,
                                 skp->smk_netlabel.attr.mls.cat,
                                 SMK_CIPSOLEN) != 0)
                                 continue;

What does it mean?
I expect that there was a reason not to use smk_find_entry()
in smack_from_secattr().

Do you want me to introduce a new hash table for searching
skp->smk_netlabel.attr.mls.cat using up to SMK_CIPSOLEN character
to produce a hash?

If it is true then this change is rather orthogonal to the current patch
and it can go to a separate patch.

Moreover, smack_from_secid() may need some hashing improvement.

>>
>> The current implementation of the function iterates over a global list of
>> smack_known resulting in O(N) complexity for smk_find_entry().  The total
>> complexity of SMACK initialization becomes O(rules * labels).  Therefore it
>> scales quadratically with a complexity of a system.
>>
>> Applying the patch reduced the complexity of smk_find_entry() to O(1) as long
>> as number of label is in hundreds. If the number of labels is increased please
>> update SMACK_HASH_SLOTS constant defined in security/smack/smack.h. Introducing
>> the configuration of this constant with Kconfig or cmdline might be a good
>> idea.
>>
>> The size of the hash table was adjusted experimentally.  The rule set used by
>> TIZEN contains circa 17K rules for 500 labels.  The table above contains
>> results of SMACK initialization using 'time smackctl apply' bash command.
>> The 'Ref' is a kernel without this patch applied. The consecutive values
>> refers to value of SMACK_HASH_SLOTS.  Every measurement was repeated three
>> times to reduce noise.
>>
>>      |  Ref  |   1   |   2   |   4   |   8   |   16  |   32  |   64  |  128  |  256  |  512
>> --------------------------------------------------------------------------------------------
>> Run1 | 1.156 | 1.096 | 0.883 | 0.764 | 0.692 | 0.667 | 0.649 | 0.633 | 0.634 | 0.629 | 0.620
>> Run2 | 1.156 | 1.111 | 0.885 | 0.764 | 0.694 | 0.661 | 0.649 | 0.651 | 0.634 | 0.638 | 0.623
>> Run3 | 1.160 | 1.107 | 0.886 | 0.764 | 0.694 | 0.671 | 0.661 | 0.638 | 0.631 | 0.624 | 0.638
>> AVG  | 1.157 | 1.105 | 0.885 | 0.764 | 0.693 | 0.666 | 0.653 | 0.641 | 0.633 | 0.630 | 0.627
> 
>                  4%      20%     14%     9%      4%      2%      2%      1%      <1%
> 
> 
> You get 4% by going to the hlist. The improvement is trivial after 16 slots.
> If you have 500 labels and 128 slots that's an average of 4 labels per slot.
> That's an awfully big hash table for so few labels and so little performance
> gain over what you get with 16 slots. Plus, 500 labels is a huge number of
> labels. Most Smack systems should be using far fewer than that. 
> 

Ok. 16 slots might be considered as 'good-enough'.

However, the cost of a single slot is a hash table is only 4 bytes (on ARM).
For example, using 64 slots instead of 16 costs only 4 * (64 - 16) = 196 bytes.
It is a very small value in comparison to other structures used in SMACK.
For example, sizeof(struct smack_rule) == 20. Notice that 32 bytes are consumed
due to kmalloc alignment policy (refer to include/linux/kmalloc_sizes.h).
So the cost is equal to the cost of 6 additional rules.

The performance gain is 4% (for 64 slots compared to 16 slots).
The gain (expressed in percents) will be larger if IO issues in smackctl get resolved.
The additional memory cost for TIZEN case (not including smack_known and other objects) is:
196 / (17k rules * 32 bytes/rule) * 100% = 0.03%

I think that 4% speed for 0.03% memory is a very good trade-off.
Especially as it makes system more resistant if a number of labels somehow
get increased.

Anyway, if you consider 16 to be the best value then 16 is the best value.

Are there any other issues to be fixed in the patch?
Do you think that commit log is a good place for measurement results.
Maybe cover-letter would be a better place?

Regards,
Tomasz Stanislawski

>>
>> Surprisingly, a single hlist is slightly faster than a double-linked list.
>> The speed-up saturates near 64 slots.  Therefore I chose value 128 to provide
>> some margin if more labels were used.
>> It looks that IO becomes a new bottleneck.
>>
>> Signed-off-by: Tomasz Stanislawski <t.stanislaws@samsung.com>
>> ---
>>  security/smack/smack.h        |    5 +++++
>>  security/smack/smack_access.c |   30 +++++++++++++++++++++++++++---
>>  security/smack/smack_lsm.c    |   12 ++++++------
>>  3 files changed, 38 insertions(+), 9 deletions(-)
>>

Re: [RFCv2] security: smack: add a hash table to quicken smk_find_entry()

[Casey Schaufler]

On 6/12/2013 6:40 AM, Tomasz Stanislawski wrote:
> Hi Casey,
> Thank you for your review.
> Please refer to comments below.
>
> On 06/12/2013 07:11 AM, Casey Schaufler wrote:
>> On 6/11/2013 5:55 AM, Tomasz Stanislawski wrote:
>>> This patch adds a hash table to quicken searching of a smack label by its name.
>>>
>>> Basically, the patch improves performance of SMACK initialization.  Parsing of
>>> rules involves translation from a string to a smack_known (aka label) entity
>>> which is done in smk_find_entry().
>> There is one place where this is done, and that is in smk_import_entry().
>>
>> There is another place where labels are looked up, and that is in
>> smack_from_secattr(). Can you apply this enhancement there, too?
>>
> The overmentioned function contains following check:
>
>                         if (memcmp(sap->attr.mls.cat,
>                                  skp->smk_netlabel.attr.mls.cat,
>                                  SMK_CIPSOLEN) != 0)
>                                  continue;
>
> What does it mean?

The Smack label is encoded in the CIPSO categories in one
of two ways. When the label is imported (smk_import_entry())
the CIPSO encoding is generated and saved in the smack_known
entry for that label. When a packet is received the CIPSO
categories are not interpreted, instead it's a simple matter
of matching the saved category set in the label list.

> I expect that there was a reason not to use smk_find_entry()
> in smack_from_secattr().

Yes. While the dirty little secret is that for short labels
the CIPSO encoding is the Smack label, you can't count on the
bitwise representation matching because, well, networking code
is just like that.


> Do you want me to introduce a new hash table for searching
> skp->smk_netlabel.attr.mls.cat using up to SMK_CIPSOLEN character
> to produce a hash?

If we're going down the hashing path this would be an obvious
step to take. And we're always looking for ways to improve
network performance.

> If it is true then this change is rather orthogonal to the current patch
> and it can go to a separate patch.

I can go either way.

> Moreover, smack_from_secid() may need some hashing improvement.

Yes. The hash function is going to be pretty trivial. smack_from_secid
is a fortunately rare call.

>
>>> The current implementation of the function iterates over a global list of
>>> smack_known resulting in O(N) complexity for smk_find_entry().  The total
>>> complexity of SMACK initialization becomes O(rules * labels).  Therefore it
>>> scales quadratically with a complexity of a system.
>>>
>>> Applying the patch reduced the complexity of smk_find_entry() to O(1) as long
>>> as number of label is in hundreds. If the number of labels is increased please
>>> update SMACK_HASH_SLOTS constant defined in security/smack/smack.h. Introducing
>>> the configuration of this constant with Kconfig or cmdline might be a good
>>> idea.
>>>
>>> The size of the hash table was adjusted experimentally.  The rule set used by
>>> TIZEN contains circa 17K rules for 500 labels.  The table above contains
>>> results of SMACK initialization using 'time smackctl apply' bash command.
>>> The 'Ref' is a kernel without this patch applied. The consecutive values
>>> refers to value of SMACK_HASH_SLOTS.  Every measurement was repeated three
>>> times to reduce noise.
>>>
>>>      |  Ref  |   1   |   2   |   4   |   8   |   16  |   32  |   64  |  128  |  256  |  512
>>> --------------------------------------------------------------------------------------------
>>> Run1 | 1.156 | 1.096 | 0.883 | 0.764 | 0.692 | 0.667 | 0.649 | 0.633 | 0.634 | 0.629 | 0.620
>>> Run2 | 1.156 | 1.111 | 0.885 | 0.764 | 0.694 | 0.661 | 0.649 | 0.651 | 0.634 | 0.638 | 0.623
>>> Run3 | 1.160 | 1.107 | 0.886 | 0.764 | 0.694 | 0.671 | 0.661 | 0.638 | 0.631 | 0.624 | 0.638
>>> AVG  | 1.157 | 1.105 | 0.885 | 0.764 | 0.693 | 0.666 | 0.653 | 0.641 | 0.633 | 0.630 | 0.627
>>                  4%      20%     14%     9%      4%      2%      2%      1%      <1%
>>
>>
>> You get 4% by going to the hlist. The improvement is trivial after 16 slots.
>> If you have 500 labels and 128 slots that's an average of 4 labels per slot.
>> That's an awfully big hash table for so few labels and so little performance
>> gain over what you get with 16 slots. Plus, 500 labels is a huge number of
>> labels. Most Smack systems should be using far fewer than that. 
>>
> Ok. 16 slots might be considered as 'good-enough'.
>
> However, the cost of a single slot is a hash table is only 4 bytes (on ARM).
> For example, using 64 slots instead of 16 costs only 4 * (64 - 16) = 196 bytes.
> It is a very small value in comparison to other structures used in SMACK.
> For example, sizeof(struct smack_rule) == 20. Notice that 32 bytes are consumed
> due to kmalloc alignment policy (refer to include/linux/kmalloc_sizes.h).
> So the cost is equal to the cost of 6 additional rules.
>
> The performance gain is 4% (for 64 slots compared to 16 slots).

Which is still only 20 milliseconds, once, at boot time.

> The gain (expressed in percents) will be larger if IO issues in smackctl get resolved.
> The additional memory cost for TIZEN case (not including smack_known and other objects) is:
> 196 / (17k rules * 32 bytes/rule) * 100% = 0.03%

But that memory is in use forever. 

> I think that 4% speed for 0.03% memory is a very good trade-off.
> Especially as it makes system more resistant if a number of labels somehow
> get increased.

The number of labels is already larger than it ought to be. We have
work to do on that.

> Anyway, if you consider 16 to be the best value then 16 is the best value.
>
> Are there any other issues to be fixed in the patch?

I don't see any right now, but of course something could come up
during my testing.

> Do you think that commit log is a good place for measurement results.
> Maybe cover-letter would be a better place?

Commit log is fine. It never hurts to record why something
seems like a good idea.

>
> Regards,
> Tomasz Stanislawski
>
>>> Surprisingly, a single hlist is slightly faster than a double-linked list.
>>> The speed-up saturates near 64 slots.  Therefore I chose value 128 to provide
>>> some margin if more labels were used.
>>> It looks that IO becomes a new bottleneck.
>>>
>>> Signed-off-by: Tomasz Stanislawski <t.stanislaws@samsung.com>
>>> ---
>>>  security/smack/smack.h        |    5 +++++
>>>  security/smack/smack_access.c |   30 +++++++++++++++++++++++++++---
>>>  security/smack/smack_lsm.c    |   12 ++++++------
>>>  3 files changed, 38 insertions(+), 9 deletions(-)
>>>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: [RFCv2] security: smack: add a hash table to quicken smk_find_entry()

[Casey Schaufler]

On 6/11/2013 5:55 AM, Tomasz Stanislawski wrote:
> This patch adds a hash table to quicken searching of a smack label by its name.
>
> Basically, the patch improves performance of SMACK initialization.  Parsing of
> rules involves translation from a string to a smack_known (aka label) entity
> which is done in smk_find_entry().
>
> The current implementation of the function iterates over a global list of
> smack_known resulting in O(N) complexity for smk_find_entry().  The total
> complexity of SMACK initialization becomes O(rules * labels).  Therefore it
> scales quadratically with a complexity of a system.
>
> Applying the patch reduced the complexity of smk_find_entry() to O(1) as long
> as number of label is in hundreds. If the number of labels is increased please
> update SMACK_HASH_SLOTS constant defined in security/smack/smack.h. Introducing
> the configuration of this constant with Kconfig or cmdline might be a good
> idea.
>
> The size of the hash table was adjusted experimentally.  The rule set used by
> TIZEN contains circa 17K rules for 500 labels.  The table above contains
> results of SMACK initialization using 'time smackctl apply' bash command.
> The 'Ref' is a kernel without this patch applied. The consecutive values
> refers to value of SMACK_HASH_SLOTS.  Every measurement was repeated three
> times to reduce noise.
>
>      |  Ref  |   1   |   2   |   4   |   8   |   16  |   32  |   64  |  128  |  256  |  512
> --------------------------------------------------------------------------------------------
> Run1 | 1.156 | 1.096 | 0.883 | 0.764 | 0.692 | 0.667 | 0.649 | 0.633 | 0.634 | 0.629 | 0.620
> Run2 | 1.156 | 1.111 | 0.885 | 0.764 | 0.694 | 0.661 | 0.649 | 0.651 | 0.634 | 0.638 | 0.623
> Run3 | 1.160 | 1.107 | 0.886 | 0.764 | 0.694 | 0.671 | 0.661 | 0.638 | 0.631 | 0.624 | 0.638
> AVG  | 1.157 | 1.105 | 0.885 | 0.764 | 0.693 | 0.666 | 0.653 | 0.641 | 0.633 | 0.630 | 0.627
>
> Surprisingly, a single hlist is slightly faster than a double-linked list.
> The speed-up saturates near 64 slots.  Therefore I chose value 128 to provide
> some margin if more labels were used.
> It looks that IO becomes a new bottleneck.
>
> Signed-off-by: Tomasz Stanislawski <t.stanislaws@samsung.com>

I will take this into my tree after changing SMACK_HASH_SLOTS to 16.

Acked-by: Casey Schaufler <casey@schaufler-ca.com>

> ---
>  security/smack/smack.h        |    5 +++++
>  security/smack/smack_access.c |   30 +++++++++++++++++++++++++++---
>  security/smack/smack_lsm.c    |   12 ++++++------
>  3 files changed, 38 insertions(+), 9 deletions(-)
>
> diff --git a/security/smack/smack.h b/security/smack/smack.h
> index 339614c..b1d9441 100644
> --- a/security/smack/smack.h
> +++ b/security/smack/smack.h
> @@ -53,6 +53,7 @@
>   */
>  struct smack_known {
>  	struct list_head		list;
> +	struct hlist_node		smk_hashed;
>  	char				*smk_known;
>  	u32				smk_secid;
>  	struct netlbl_lsm_secattr	smk_netlabel;	/* on wire labels */
> @@ -222,6 +223,7 @@ char *smk_parse_smack(const char *string, int len);
>  int smk_netlbl_mls(int, char *, struct netlbl_lsm_secattr *, int);
>  char *smk_import(const char *, int);
>  struct smack_known *smk_import_entry(const char *, int);
> +void smk_insert_entry(struct smack_known *skp);
>  struct smack_known *smk_find_entry(const char *);
>  u32 smack_to_secid(const char *);
>  
> @@ -247,6 +249,9 @@ extern struct list_head smk_netlbladdr_list;
>  
>  extern struct security_operations smack_ops;
>  
> +#define SMACK_HASH_SLOTS 128
> +extern struct hlist_head smack_known_hash[SMACK_HASH_SLOTS];
> +
>  /*
>   * Is the directory transmuting?
>   */
> diff --git a/security/smack/smack_access.c b/security/smack/smack_access.c
> index 6a0377f..b598c32 100644
> --- a/security/smack/smack_access.c
> +++ b/security/smack/smack_access.c
> @@ -325,6 +325,25 @@ void smack_log(char *subject_label, char *object_label, int request,
>  
>  DEFINE_MUTEX(smack_known_lock);
>  
> +struct hlist_head smack_known_hash[SMACK_HASH_SLOTS];
> +
> +/**
> + * smk_insert_entry - insert a smack label into a hash map,
> + *
> + * this function must be called under smack_known_lock
> + */
> +void smk_insert_entry(struct smack_known *skp)
> +{
> +	unsigned int hash;
> +	struct hlist_head *head;
> +
> +	hash = full_name_hash(skp->smk_known, strlen(skp->smk_known));
> +	head = &smack_known_hash[hash & (SMACK_HASH_SLOTS - 1)];
> +
> +	hlist_add_head_rcu(&skp->smk_hashed, head);
> +	list_add_rcu(&skp->list, &smack_known_list);
> +}
> +
>  /**
>   * smk_find_entry - find a label on the list, return the list entry
>   * @string: a text string that might be a Smack label
> @@ -334,12 +353,17 @@ DEFINE_MUTEX(smack_known_lock);
>   */
>  struct smack_known *smk_find_entry(const char *string)
>  {
> +	unsigned int hash;
> +	struct hlist_head *head;
> +	struct hlist_node *cursor;
>  	struct smack_known *skp;
>  
> -	list_for_each_entry_rcu(skp, &smack_known_list, list) {
> +	hash = full_name_hash(string, strlen(string));
> +	head = &smack_known_hash[hash & (SMACK_HASH_SLOTS - 1)];
> +
> +	hlist_for_each_entry_rcu(skp, cursor, head, smk_hashed)
>  		if (strcmp(skp->smk_known, string) == 0)
>  			return skp;
> -	}
>  
>  	return NULL;
>  }
> @@ -475,7 +499,7 @@ struct smack_known *smk_import_entry(const char *string, int len)
>  		 * Make sure that the entry is actually
>  		 * filled before putting it on the list.
>  		 */
> -		list_add_rcu(&skp->list, &smack_known_list);
> +		smk_insert_entry(skp);
>  		goto unlockout;
>  	}
>  	/*
> diff --git a/security/smack/smack_lsm.c b/security/smack/smack_lsm.c
> index 6a08330..6cabca6 100644
> --- a/security/smack/smack_lsm.c
> +++ b/security/smack/smack_lsm.c
> @@ -3868,12 +3868,12 @@ static __init void init_smack_known_list(void)
>  	/*
>  	 * Create the known labels list
>  	 */
> -	list_add(&smack_known_huh.list, &smack_known_list);
> -	list_add(&smack_known_hat.list, &smack_known_list);
> -	list_add(&smack_known_star.list, &smack_known_list);
> -	list_add(&smack_known_floor.list, &smack_known_list);
> -	list_add(&smack_known_invalid.list, &smack_known_list);
> -	list_add(&smack_known_web.list, &smack_known_list);
> +	smk_insert_entry(&smack_known_huh);
> +	smk_insert_entry(&smack_known_hat);
> +	smk_insert_entry(&smack_known_star);
> +	smk_insert_entry(&smack_known_floor);
> +	smk_insert_entry(&smack_known_invalid);
> +	smk_insert_entry(&smack_known_web);
>  }
>  
>  /**

Re: [RFCv2] security: smack: add a hash table to quicken smk_find_entry()

[Casey Schaufler]

On 6/27/2013 2:11 PM, Casey Schaufler wrote:
> On 6/11/2013 5:55 AM, Tomasz Stanislawski wrote:
>> This patch adds a hash table to quicken searching of a smack label by its name.
>>
>> Basically, the patch improves performance of SMACK initialization.  Parsing of
>> rules involves translation from a string to a smack_known (aka label) entity
>> which is done in smk_find_entry().
>>
>> The current implementation of the function iterates over a global list of
>> smack_known resulting in O(N) complexity for smk_find_entry().  The total
>> complexity of SMACK initialization becomes O(rules * labels).  Therefore it
>> scales quadratically with a complexity of a system.
>>
>> Applying the patch reduced the complexity of smk_find_entry() to O(1) as long
>> as number of label is in hundreds. If the number of labels is increased please
>> update SMACK_HASH_SLOTS constant defined in security/smack/smack.h. Introducing
>> the configuration of this constant with Kconfig or cmdline might be a good
>> idea.
>>
>> The size of the hash table was adjusted experimentally.  The rule set used by
>> TIZEN contains circa 17K rules for 500 labels.  The table above contains
>> results of SMACK initialization using 'time smackctl apply' bash command.
>> The 'Ref' is a kernel without this patch applied. The consecutive values
>> refers to value of SMACK_HASH_SLOTS.  Every measurement was repeated three
>> times to reduce noise.
>>
>>      |  Ref  |   1   |   2   |   4   |   8   |   16  |   32  |   64  |  128  |  256  |  512
>> --------------------------------------------------------------------------------------------
>> Run1 | 1.156 | 1.096 | 0.883 | 0.764 | 0.692 | 0.667 | 0.649 | 0.633 | 0.634 | 0.629 | 0.620
>> Run2 | 1.156 | 1.111 | 0.885 | 0.764 | 0.694 | 0.661 | 0.649 | 0.651 | 0.634 | 0.638 | 0.623
>> Run3 | 1.160 | 1.107 | 0.886 | 0.764 | 0.694 | 0.671 | 0.661 | 0.638 | 0.631 | 0.624 | 0.638
>> AVG  | 1.157 | 1.105 | 0.885 | 0.764 | 0.693 | 0.666 | 0.653 | 0.641 | 0.633 | 0.630 | 0.627
>>
>> Surprisingly, a single hlist is slightly faster than a double-linked list.
>> The speed-up saturates near 64 slots.  Therefore I chose value 128 to provide
>> some margin if more labels were used.
>> It looks that IO becomes a new bottleneck.
>>
>> Signed-off-by: Tomasz Stanislawski <t.stanislaws@samsung.com>
> I will take this into my tree after changing SMACK_HASH_SLOTS to 16.
>
> Acked-by: Casey Schaufler <casey@schaufler-ca.com>

Applied to git://git.gitorious.org/smack-next/kernel.git#smack-for-3.12

Rebasing was required. The change has been tested.


>
>> ---
>>  security/smack/smack.h        |    5 +++++
>>  security/smack/smack_access.c |   30 +++++++++++++++++++++++++++---
>>  security/smack/smack_lsm.c    |   12 ++++++------
>>  3 files changed, 38 insertions(+), 9 deletions(-)
>>
>> diff --git a/security/smack/smack.h b/security/smack/smack.h
>> index 339614c..b1d9441 100644
>> --- a/security/smack/smack.h
>> +++ b/security/smack/smack.h
>> @@ -53,6 +53,7 @@
>>   */
>>  struct smack_known {
>>  	struct list_head		list;
>> +	struct hlist_node		smk_hashed;
>>  	char				*smk_known;
>>  	u32				smk_secid;
>>  	struct netlbl_lsm_secattr	smk_netlabel;	/* on wire labels */
>> @@ -222,6 +223,7 @@ char *smk_parse_smack(const char *string, int len);
>>  int smk_netlbl_mls(int, char *, struct netlbl_lsm_secattr *, int);
>>  char *smk_import(const char *, int);
>>  struct smack_known *smk_import_entry(const char *, int);
>> +void smk_insert_entry(struct smack_known *skp);
>>  struct smack_known *smk_find_entry(const char *);
>>  u32 smack_to_secid(const char *);
>>  
>> @@ -247,6 +249,9 @@ extern struct list_head smk_netlbladdr_list;
>>  
>>  extern struct security_operations smack_ops;
>>  
>> +#define SMACK_HASH_SLOTS 128
>> +extern struct hlist_head smack_known_hash[SMACK_HASH_SLOTS];
>> +
>>  /*
>>   * Is the directory transmuting?
>>   */
>> diff --git a/security/smack/smack_access.c b/security/smack/smack_access.c
>> index 6a0377f..b598c32 100644
>> --- a/security/smack/smack_access.c
>> +++ b/security/smack/smack_access.c
>> @@ -325,6 +325,25 @@ void smack_log(char *subject_label, char *object_label, int request,
>>  
>>  DEFINE_MUTEX(smack_known_lock);
>>  
>> +struct hlist_head smack_known_hash[SMACK_HASH_SLOTS];
>> +
>> +/**
>> + * smk_insert_entry - insert a smack label into a hash map,
>> + *
>> + * this function must be called under smack_known_lock
>> + */
>> +void smk_insert_entry(struct smack_known *skp)
>> +{
>> +	unsigned int hash;
>> +	struct hlist_head *head;
>> +
>> +	hash = full_name_hash(skp->smk_known, strlen(skp->smk_known));
>> +	head = &smack_known_hash[hash & (SMACK_HASH_SLOTS - 1)];
>> +
>> +	hlist_add_head_rcu(&skp->smk_hashed, head);
>> +	list_add_rcu(&skp->list, &smack_known_list);
>> +}
>> +
>>  /**
>>   * smk_find_entry - find a label on the list, return the list entry
>>   * @string: a text string that might be a Smack label
>> @@ -334,12 +353,17 @@ DEFINE_MUTEX(smack_known_lock);
>>   */
>>  struct smack_known *smk_find_entry(const char *string)
>>  {
>> +	unsigned int hash;
>> +	struct hlist_head *head;
>> +	struct hlist_node *cursor;
>>  	struct smack_known *skp;
>>  
>> -	list_for_each_entry_rcu(skp, &smack_known_list, list) {
>> +	hash = full_name_hash(string, strlen(string));
>> +	head = &smack_known_hash[hash & (SMACK_HASH_SLOTS - 1)];
>> +
>> +	hlist_for_each_entry_rcu(skp, cursor, head, smk_hashed)
>>  		if (strcmp(skp->smk_known, string) == 0)
>>  			return skp;
>> -	}
>>  
>>  	return NULL;
>>  }
>> @@ -475,7 +499,7 @@ struct smack_known *smk_import_entry(const char *string, int len)
>>  		 * Make sure that the entry is actually
>>  		 * filled before putting it on the list.
>>  		 */
>> -		list_add_rcu(&skp->list, &smack_known_list);
>> +		smk_insert_entry(skp);
>>  		goto unlockout;
>>  	}
>>  	/*
>> diff --git a/security/smack/smack_lsm.c b/security/smack/smack_lsm.c
>> index 6a08330..6cabca6 100644
>> --- a/security/smack/smack_lsm.c
>> +++ b/security/smack/smack_lsm.c
>> @@ -3868,12 +3868,12 @@ static __init void init_smack_known_list(void)
>>  	/*
>>  	 * Create the known labels list
>>  	 */
>> -	list_add(&smack_known_huh.list, &smack_known_list);
>> -	list_add(&smack_known_hat.list, &smack_known_list);
>> -	list_add(&smack_known_star.list, &smack_known_list);
>> -	list_add(&smack_known_floor.list, &smack_known_list);
>> -	list_add(&smack_known_invalid.list, &smack_known_list);
>> -	list_add(&smack_known_web.list, &smack_known_list);
>> +	smk_insert_entry(&smack_known_huh);
>> +	smk_insert_entry(&smack_known_hat);
>> +	smk_insert_entry(&smack_known_star);
>> +	smk_insert_entry(&smack_known_floor);
>> +	smk_insert_entry(&smack_known_invalid);
>> +	smk_insert_entry(&smack_known_web);
>>  }
>>  
>>  /**
> --
> To unsubscribe from this list: send the line "unsubscribe linux-security-module" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: [RFCv2] security: smack: add a hash table to quicken smk_find_entry()

[Tomasz Stanislawski]

On 08/02/2013 01:58 AM, Casey Schaufler wrote:
> On 6/27/2013 2:11 PM, Casey Schaufler wrote:
>> On 6/11/2013 5:55 AM, Tomasz Stanislawski wrote:
>>> This patch adds a hash table to quicken searching of a smack label by its name.
>>>
>>> Basically, the patch improves performance of SMACK initialization.  Parsing of
>>> rules involves translation from a string to a smack_known (aka label) entity
>>> which is done in smk_find_entry().

[snip]

>> I will take this into my tree after changing SMACK_HASH_SLOTS to 16.
>>
>> Acked-by: Casey Schaufler <casey@schaufler-ca.com>
> 
> Applied to git://git.gitorious.org/smack-next/kernel.git#smack-for-3.12
> 
> Rebasing was required. The change has been tested.
> 
> 

Hi,
Thanks for merging the patch.
BTW. Do you have comments about:

http://thread.gmane.org/gmane.linux.kernel.lsm/19650

Here I posted all of the acceptable patches rebased on smack-next.
Moreover, I added measurements of impact of patches on both time and
memory consumption.
There were no comments about this patchset. Maybe something was lost?

Regards,
Tomasz Stanislawski