| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <51AF5251.5060104@tycho.nsa.gov>
Date: Wed, 05 Jun 2013 10:59:29 -0400
From: Stephen Smalley <sds@...ho.nsa.gov>
To: Waiman Long <Waiman.Long@...com>
CC: James Morris <james.l.morris@...cle.com>,
Eric Paris <eparis@...isplace.org>,
linux-security-module@...r.kernel.org,
linux-kernel@...r.kernel.org,
"Chandramouleeswaran, Aswin" <aswin@...com>,
"Norton, Scott J" <scott.norton@...com>
Subject: Re: [PATCH RFC 1/2] SELinux: reduce overhead of mls_level_isvalid()
function call
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<Waiman.Long@...com>
>> ---
>> 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?
Can you take the core logic into a helper function within ebitmap.c?
Otherwise you are directly exposing ebitmap internals to the mls code.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists