security: smack: add a hash table to quicken smk_find_entry()
Subsystems (2)
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(-)
Signature · 1 line
1.7.9.5
RFC v2 1/1 security: smack: add a hash table to quicken smk_find_entry()
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.
--- security/smack/smack.h | 5 +++++ security/smack/smack_access.c | 30 +++++++++++++++++++++++++++--- security/smack/smack_lsm.c | 12 ++++++------ 3 files changed, 38 insertions(+), 9 deletions(-)
security/smack/smack.h +5 -0
@@ -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? */
security/smack/smack_access.c +27 -3
@@ -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; }/*
security/smack/smack_lsm.c +6 -6
@@ -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); }/**
Signature · 1 line
1.7.9.5
Casey Schaufler
maintainerQuoted 5 lines · 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 insmk_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?
Quoted 19 lines
The current implementation of the function iterates over a global list of
smack_knownresulting in O(N) complexity forsmk_find_entry(). The total complexity of SMACK initialization becomesO(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 updateSMACK_HASH_SLOTSconstant defined insecurity/smack/smack.h. Introducing the configuration of this constant withKconfigor 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.
Quoted 6 lines
| 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.
Quoted 34 lines
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 <[email protected]>--- security/smack/smack.h | 5 +++++ security/smack/smack_access.c | 30 +++++++++++++++++++++++++++--- security/smack/smack_lsm.c | 12 ++++++------ 3 files changed, 38 insertions(+), 9 deletions(-)security/smack/smack.h +2
-0@@ -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 *);
security/smack/smack.h extern struct list_head smk_netlbladdr_list; · line 252
Quoted 4 lines
security/smack/smack.h +1
-0@@ -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.
Quoted 87 lines
security/smack/smack.h +2
-0+extern struct hlist_head smack_known_hash[SMACK_HASH_SLOTS ]; +/* * Is the directory transmuting? */ security/smack/smack_access.c +27
-3@@ -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; }/* security/smack/smack_lsm.c +6
-6@@ -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); }/**
Hi Casey,
Thank you for your review.
Please refer to comments below.
Quoted 12 lines · Casey Schaufler
Quoted 5 lines · 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 insmk_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.
Quoted 26 lines
Quoted 19 lines
The current implementation of the function iterates over a global list of
smack_knownresulting in O(N) complexity forsmk_find_entry(). The total complexity of SMACK initialization becomesO(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 updateSMACK_HASH_SLOTSconstant defined insecurity/smack/smack.h. Introducing the configuration of this constant withKconfigor 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.Quoted 6 lines
| 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
Quoted 9 lines
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
Quoted 13 lines
Quoted 13 lines
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 <[email protected]>--- security/smack/smack.h | 5 +++++ security/smack/smack_access.c | 30 +++++++++++++++++++++++++++--- security/smack/smack_lsm.c | 12 ++++++------ 3 files changed, 38 insertions(+), 9 deletions(-)
Casey Schaufler
maintainerQuoted 16 lines · Tomasz Stanislawski
Hi Casey,
Thank you for your review.
Please refer to comments below.Quoted 11 lines · Casey Schaufler
Quoted 5 lines · 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 insmk_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?
Quoted 8 lines
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.
Quoted 2 lines
I expect that there was a reason not to use
smk_find_entry()insmack_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.
Quoted 3 lines
Do you want me to introduce a new hash table for searching
skp->smk_netlabel.attr.mls.catusing up toSMK_CIPSOLENcharacter 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.
Quoted 2 lines
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.
Quoted 1 line
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.
Quoted 36 lines
Quoted 25 lines
Quoted 19 lines
The current implementation of the function iterates over a global list of
smack_knownresulting in O(N) complexity forsmk_find_entry(). The total complexity of SMACK initialization becomesO(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 updateSMACK_HASH_SLOTSconstant defined insecurity/smack/smack.h. Introducing the configuration of this constant withKconfigor 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.Quoted 6 lines
| 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.627Quoted 9 lines
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'.
Quoted 8 lines
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 toinclude/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.
Quoted 3 lines
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_knownand other objects) is:
196 / (17k rules * 32 bytes/rule) * 100% = 0.03%
But that memory is in use forever.
Quoted 3 lines
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.
Quoted 3 lines
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.
Quoted 2 lines
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.
Quoted 22 lines
Regards,
Tomasz StanislawskiQuoted 5 lines
Quoted 5 lines
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.Quoted 7 lines
Quoted 7 lines
Signed-off-by Tomasz Stanislawski <[email protected]>--- 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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 31 lines · 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 insmk_find_entry().The current implementation of the function iterates over a global list of
smack_knownresulting in O(N) complexity forsmk_find_entry(). The total complexity of SMACK initialization becomesO(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 updateSMACK_HASH_SLOTSconstant defined insecurity/smack/smack.h. Introducing the configuration of this constant withKconfigor 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
Quoted 6 lines
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 <[email protected]>
I will take this into my tree after changing SMACK_HASH_SLOTS to 16.
Quoted 118 lines
--- security/smack/smack.h | 5 +++++ security/smack/smack_access.c | 30 +++++++++++++++++++++++++++--- security/smack/smack_lsm.c | 12 ++++++------ 3 files changed, 38 insertions(+), 9 deletions(-)security/smack/smack.h +5
-0@@ -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? */ security/smack/smack_access.c +27
-3@@ -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; }/* security/smack/smack_lsm.c +6
-6@@ -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); }/**
Quoted 37 lines · Casey Schaufler
Quoted 36 lines · 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 insmk_find_entry().The current implementation of the function iterates over a global list of
smack_knownresulting in O(N) complexity forsmk_find_entry(). The total complexity of SMACK initialization becomesO(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 updateSMACK_HASH_SLOTSconstant defined insecurity/smack/smack.h. Introducing the configuration of this constant withKconfigor 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.627Surprisingly, 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.
Quoted 4 lines
Quoted 1 line
Signed-off-by Tomasz Stanislawski <[email protected]>I will take this into my tree after changing
SMACK_HASH_SLOTSto 16.Acked-by Casey Schaufler <[email protected]>
Applied to git://git.gitorious.org/smack-next/kernel.git#smack-for-3.12
Rebasing was required. The change has been tested.
Quoted 124 lines
Quoted 109 lines
--- security/smack/smack.h | 5 +++++ security/smack/smack_access.c | 30 +++++++++++++++++++++++++++--- security/smack/smack_lsm.c | 12 ++++++------ 3 files changed, 38 insertions(+), 9 deletions(-)security/smack/smack.h +5
-0@@ -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? */ security/smack/smack_access.c +27
-3@@ -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; }/* security/smack/smack_lsm.c +0
-5@@ -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);security/smack/smack_lsm.c static __init void init_smack_known_list(void) · line 3879
Quoted 10 lines
security/smack/smack_lsm.c +6
-1-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 [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 7 lines · Casey Schaufler
Quoted 6 lines · Casey Schaufler
Quoted 5 lines · 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 insmk_find_entry().
[snip]
Quoted 9 lines
Quoted 3 lines
I will take this into my tree after changing
SMACK_HASH_SLOTSto 16.Acked-by Casey Schaufler <[email protected]>Applied to
git://git.gitorious.org/smack-next/kernel.git#smack-for-3.12Rebasing 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