Messages in this thread | | | Date | Thu, 01 Aug 2013 16:58:39 -0700 | From | Casey Schaufler <> | Subject | Re: [RFCv2] security: smack: add a hash table to quicken smk_find_entry() |
| |
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 >
| |