Messages in this thread | | | Date | Fri, 03 May 2013 10:07:58 -0400 | From | Waiman Long <> | Subject | Re: [PATCH RFC 1/2] SELinux: reduce overhead of mls_level_isvalid() function call |
| |
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@hp.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?
Thank a lot! Regards, Longman
| |