From patchwork Thu Jul 31 03:26:44 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Damian Hobson-Garcia X-Patchwork-Id: 4653011 Return-Path: X-Original-To: patchwork-ltsi-dev@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.19.201]) by patchwork1.web.kernel.org (Postfix) with ESMTP id D88389F36A for ; Thu, 31 Jul 2014 03:27:55 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id D4F6E201B4 for ; Thu, 31 Jul 2014 03:27:54 +0000 (UTC) Received: from mail.linuxfoundation.org (mail.linuxfoundation.org [140.211.169.12]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id D2E152015E for ; Thu, 31 Jul 2014 03:27:53 +0000 (UTC) Received: from mail.linux-foundation.org (localhost [IPv6:::1]) by mail.linuxfoundation.org (Postfix) with ESMTP id 8072C9F6; Thu, 31 Jul 2014 03:27:12 +0000 (UTC) X-Original-To: ltsi-dev@lists.linuxfoundation.org Delivered-To: ltsi-dev@mail.linuxfoundation.org Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 729D3A8A for ; Thu, 31 Jul 2014 03:27:11 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-pd0-f172.google.com (mail-pd0-f172.google.com [209.85.192.172]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D68E31FB59 for ; Thu, 31 Jul 2014 03:27:10 +0000 (UTC) Received: by mail-pd0-f172.google.com with SMTP id ft15so2636658pdb.3 for ; Wed, 30 Jul 2014 20:27:10 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=NtNjzGai7KZ86hh6ClRrFg5vQ0b6jkKZfjvSfgKC5Io=; b=aNojchlMwtP4Q6l6MhxwIhAm9kZJM/D6YUjUs1bkOxdLjVMq9NELLieRz2xi7XN5uR 6fKrNTM9cUmLbBY5CBHx31ZbHOrZhLBpldFaNgxv0KvUvVbbfZxCRFPkF+kLRWxXR7+0 VWnskdPxvz78rWgwVPrNBLx0BFqlmjUEGAgZRovFaoHLqTqc0YIWCgyRWKmf54uyorGV ZXLLBs/E15ZYQhtfDh76oBYRZ9+a1MMU/0iWCDjxZBl8QM1Lek42bDaYJsOdqDmSxRFf 6cyGUN60wTkqbQDH28h8uFwofMHmbtMPgrB058FpivY6QhMOk6c2ank00+6LpwL3z4ZO hlNg== X-Gm-Message-State: ALoCoQnWOR6PEmVQeONmZlhJe4ABNDJnvIHaSJKRdBlFAEaid+gPjkcfJcxTBNVVDYYoJrrU1D+1 X-Received: by 10.68.102.34 with SMTP id fl2mr1237018pbb.2.1406777230664; Wed, 30 Jul 2014 20:27:10 -0700 (PDT) Received: from v400.hq.igel.co.jp (napt.igel.co.jp. [219.106.231.132]) by mx.google.com with ESMTPSA id d13sm3843861pbu.72.2014.07.30.20.27.09 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 30 Jul 2014 20:27:09 -0700 (PDT) From: Damian Hobson-Garcia To: ltsi-dev@lists.linuxfoundation.org Date: Thu, 31 Jul 2014 12:26:44 +0900 Message-Id: <1406777210-28425-11-git-send-email-dhobsong@igel.co.jp> X-Mailer: git-send-email 1.7.9.5 In-Reply-To: <1406777210-28425-1-git-send-email-dhobsong@igel.co.jp> References: <1406777210-28425-1-git-send-email-dhobsong@igel.co.jp> X-Spam-Status: No, score=-4.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_MED, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org Subject: [LTSI-dev] [PATCH 10/16] security: smack: add a hash table to quicken smk_find_entry() X-BeenThere: ltsi-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: "A list to discuss patches, development, and other things related to the LTSI project" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: ltsi-dev-bounces@lists.linuxfoundation.org Errors-To: ltsi-dev-bounces@lists.linuxfoundation.org X-Virus-Scanned: ClamAV using ClamSMTP From: Tomasz Stanislawski Accepted for the smack-next tree after changing the number of slots from 128 to 16. 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 (cherry picked from commit 4d7cf4a1f49f76f4069114ee08be75cd68c37c5a) Signed-off-by: Damian Hobson-Garcia Signed-off-by: Tomohito Esaki --- security/smack/smack.h | 5 +++++ security/smack/smack_access.c | 29 ++++++++++++++++++++++++++--- security/smack/smack_lsm.c | 12 ++++++------ 3 files changed, 37 insertions(+), 9 deletions(-) diff --git a/security/smack/smack.h b/security/smack/smack.h index 339614c..e80597a 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 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..b3b59b1 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,16 @@ DEFINE_MUTEX(smack_known_lock); */ struct smack_known *smk_find_entry(const char *string) { + unsigned int hash; + struct hlist_head *head; 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, head, smk_hashed) if (strcmp(skp->smk_known, string) == 0) return skp; - } return NULL; } @@ -475,7 +498,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 a113a77..f70a0fa 100644 --- a/security/smack/smack_lsm.c +++ b/security/smack/smack_lsm.c @@ -3876,12 +3876,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); } /**