Re: [PATCH RFC 1/2] SELinux: reduce overhead of mls_level_isvalid()function call

[Stephen Smalley]

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@xxxxxx>
> > ---
> >   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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/