Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755662Ab3FEOx2 (ORCPT ); Wed, 5 Jun 2013 10:53:28 -0400 Received: from g6t0186.atlanta.hp.com ([15.193.32.63]:20767 "EHLO g6t0186.atlanta.hp.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755487Ab3FEOxZ (ORCPT ); Wed, 5 Jun 2013 10:53:25 -0400 Message-ID: <51AF50D9.5060006@hp.com> Date: Wed, 05 Jun 2013 10:53:13 -0400 From: Waiman Long User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:10.0.12) Gecko/20130109 Thunderbird/10.0.12 MIME-Version: 1.0 To: Stephen Smalley , James Morris , Eric Paris CC: linux-security-module@vger.kernel.org, linux-kernel@vger.kernel.org, "Chandramouleeswaran, Aswin" , "Norton, Scott J" Subject: Re: [PATCH RFC 1/2] SELinux: reduce overhead of mls_level_isvalid() function call References: <1365618383-29340-1-git-send-email-Waiman.Long@hp.com> <5183C4BE.5030504@hp.com> In-Reply-To: <5183C4BE.5030504@hp.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 5518 Lines: 134 On 05/03/2013 10:07 AM, Waiman Long wrote: > On 04/10/2013 02:26 PM, Waiman Long wrote: >> While running the high_systime workload of the AIM7 benchmark on >> a 2-socket 12-core Westmere x86-64 machine running 3.8.2 kernel, >> it was found that a pretty sizable amount of time was spent in the >> SELinux code. Below was the perf trace of the "perf record -a -s" >> of a test run at 1500 users: >> >> 3.96% ls [kernel.kallsyms] [k] ebitmap_get_bit >> 1.44% ls [kernel.kallsyms] [k] mls_level_isvalid >> 1.33% ls [kernel.kallsyms] [k] find_next_bit >> >> The ebitmap_get_bit() was the hottest function in the perf-report >> output. Both the ebitmap_get_bit() and find_next_bit() functions >> were, in fact, called by mls_level_isvalid(). As a result, the >> mls_level_isvalid() call consumed 6.73% of the total CPU time of all >> the 24 virtual CPUs which is quite a lot. >> >> Looking at the mls_level_isvalid() function, it is checking to see >> if all the bits set in one of the ebitmap structure are also set in >> another one as well as the highest set bit is no bigger than the one >> specified by the given policydb data structure. It is doing it in >> a bit-by-bit manner. So if the ebitmap structure has many bits set, >> the iteration loop will be done many times. >> >> The current code can be rewritten to use a similar algorithm as the >> ebitmap_contains() function with an additional check for the highest >> set bit. With that change, the perf trace showed that the used CPU >> time drop down to just 0.09% of the total which is about 100X less >> than before. >> >> 0.04% ls [kernel.kallsyms] [k] ebitmap_get_bit >> 0.04% ls [kernel.kallsyms] [k] mls_level_isvalid >> 0.01% ls [kernel.kallsyms] [k] find_next_bit >> >> Actually, the remaining ebitmap_get_bit() and find_next_bit() function >> calls are made by other kernel routines as the new mls_level_isvalid() >> function will not call them anymore. >> >> This patch also improves the high_systime AIM7 benchmark result, >> though the improvement is not as impressive as is suggested by the >> reduction in CPU time. The table below shows the performance change >> on the 2-socket x86-64 system mentioned above. >> >> +--------------+---------------+----------------+-----------------+ >> | Workload | mean % change | mean % change | mean % change | >> | | 10-100 users | 200-1000 users | 1100-2000 users | >> +--------------+---------------+----------------+-----------------+ >> | high_systime | +0.2% | +1.1% | +2.4% | >> +--------------+---------------+----------------+-----------------+ >> >> Signed-off-by: Waiman Long >> --- >> security/selinux/ss/mls.c | 38 >> +++++++++++++++++++++++++++----------- >> 1 files changed, 27 insertions(+), 11 deletions(-) >> >> diff --git a/security/selinux/ss/mls.c b/security/selinux/ss/mls.c >> index 40de8d3..ce02803 100644 >> --- a/security/selinux/ss/mls.c >> +++ b/security/selinux/ss/mls.c >> @@ -160,8 +160,7 @@ void mls_sid_to_context(struct context *context, >> int mls_level_isvalid(struct policydb *p, struct mls_level *l) >> { >> struct level_datum *levdatum; >> - struct ebitmap_node *node; >> - int i; >> + struct ebitmap_node *nodel, *noded; >> >> if (!l->sens || l->sens> p->p_levels.nprim) >> return 0; >> @@ -170,16 +169,33 @@ int mls_level_isvalid(struct policydb *p, >> struct mls_level *l) >> if (!levdatum) >> return 0; >> >> - ebitmap_for_each_positive_bit(&l->cat, node, i) { >> - if (i> p->p_cats.nprim) >> - return 0; >> - if (!ebitmap_get_bit(&levdatum->level->cat, i)) { >> - /* >> - * Category may not be associated with >> - * sensitivity. >> - */ >> - return 0; >> + /* >> + * Return 1 iff >> + * 1. l->cat.node is NULL, or >> + * 2. all the bits set in l->cat are also set in >> levdatum->level->cat, >> + * and >> + * 3. the last bit set in l->cat should not be larger than >> + * p->p_cats.nprim. >> + */ >> + noded = levdatum->level->cat.node; >> + for (nodel = l->cat.node ; nodel ; nodel = nodel->next) { >> + int i, lastsetbit = -1; >> + >> + for (i = EBITMAP_UNIT_NUMS - 1 ; i>= 0 ; i--) { >> + if (!nodel->maps[i]) >> + continue; >> + if (!noded || >> + ((nodel->maps[i]&noded->maps[i]) != nodel->maps[i])) >> + return 0; >> + if (lastsetbit< 0) >> + lastsetbit = nodel->startbit + >> + i * EBITMAP_UNIT_SIZE + >> + __fls(nodel->maps[i]); >> } >> + if ((lastsetbit>= 0)&& (lastsetbit> p->p_cats.nprim)) >> + return 0; >> + if (noded) >> + noded = noded->next; >> } >> >> return 1; > > Would you mind giving me some feedback on what you think about this > patch? > > Thank a lot! > Regards, > Longman I am sorry for the annoyance, but I really want to have some feedback on whether this patch is viable or not. Thanks, Longman -- 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/