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

[Waiman Long <Waiman.Long@hp.com>]

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