Received-SPF: pass (google.com: domain of linux-kernel+bounces-122080-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) client-ip=147.75.48.161;
Date: Wed, 27 Mar 2024 18:07:44 -0400
Message-ID: <66718f36ae0e8dbad8bbf74038e9e0d6@paul-moore.com>
Precedence: bulk
MIME-Version: 1.0 
Content-Type: text/plain; charset=utf-8 
Content-Disposition: inline 
Content-Transfer-Encoding: 8bit
From: Paul Moore <paul@paul-moore.com>
To: =?UTF-8?q?Christian=20G=C3=B6ttsche?= <cgzones@googlemail.com>, selinux@vger.kernel.org
Cc: Stephen Smalley <stephen.smalley.work@gmail.com>, Ondrej Mosnacek <omosnace@redhat.com>, linux-kernel@vger.kernel.org
Subject: Re: [PATCH v3] selinux: optimize ebitmap_and()
References: <20240315181204.647182-1-cgzones@googlemail.com>
In-Reply-To: <20240315181204.647182-1-cgzones@googlemail.com>

On Mar 15, 2024 =?UTF-8?q?Christian=20G=C3=B6ttsche?= <cgzones@googlemail.com> wrote:
> 
> Iterate on nodes instead of single bits to save node resolution for each
> single bit.
> 
> Similar to userspace patch efcd00814879 ("libsepol: optimize
> ebitmap_and").
> 
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
> ---
> v3:
>   apply format style
> v2:
>   fix array size computation
> ---
>  security/selinux/ss/ebitmap.c | 50 +++++++++++++++++++++++++++++------
>  1 file changed, 42 insertions(+), 8 deletions(-)

Some minor comments below, but do you have any performance measurements
for this change?  I realize that ebitmap_and() isn't widely used, but
it would be nice to understand the performance difference, and if there
isn't much/any difference we might want to stick with the original code
as it is much simpler.

> diff --git a/security/selinux/ss/ebitmap.c b/security/selinux/ss/ebitmap.c
> index 67c1a73cd5ee..47cb90106118 100644
> --- a/security/selinux/ss/ebitmap.c
> +++ b/security/selinux/ss/ebitmap.c
> @@ -78,19 +78,53 @@ int ebitmap_cpy(struct ebitmap *dst, const struct ebitmap *src)
>  int ebitmap_and(struct ebitmap *dst, const struct ebitmap *e1,
>  		const struct ebitmap *e2)
>  {
> -	struct ebitmap_node *n;
> -	int bit, rc;
> +	const struct ebitmap_node *n1, *n2;
> +	struct ebitmap_node *new = NULL, **prev;
>  
>  	ebitmap_init(dst);
>  
> -	ebitmap_for_each_positive_bit(e1, n, bit)
> -	{
> -		if (ebitmap_get_bit(e2, bit)) {
> -			rc = ebitmap_set_bit(dst, bit, 1);
> -			if (rc < 0)
> -				return rc;
> +	prev = &dst->node;

Later in this function you include parenthesis, that might be nice
here too:

  prev = &(dst->node);

> +	n1 = e1->node;
> +	n2 = e2->node;
> +	while (n1 && n2) {
> +		if (n1->startbit == n2->startbit) {
> +			unsigned long testmap[EBITMAP_UNIT_NUMS];

This is very bikeshed-y, but I much prefer "dstmaps" over "testmap".

> +			unsigned int i;
> +			bool match = false;
> +
> +			for (i = 0; i < ARRAY_SIZE(testmap); i++) {
> +				testmap[i] = n1->maps[i] & n2->maps[i];
> +				if (testmap[i] != 0)

If I'm going to be nitpicky, I'd probably prefer 'if (!dstmaps[i])'.

> +					match = true;
> +			}
> +
> +			if (match) {
> +				new = kmem_cache_zalloc(ebitmap_node_cachep,
> +							GFP_ATOMIC);
> +				if (!new) {
> +					ebitmap_destroy(dst);
> +					return -ENOMEM;
> +				}
> +				new->startbit = n1->startbit;
> +				memcpy(new->maps, testmap, EBITMAP_SIZE / 8);

Why not just use 'sizeof(dstmaps)'?

  memcpy(new->maps, dstmaps, sizeof(dstmaps));

> +				new->next = NULL;

You shouldn't need the line above since you're doing a _zalloc().

> +				*prev = new;
> +				prev = &(new->next);
> +			}
> +
> +			n1 = n1->next;
> +			n2 = n2->next;
> +		} else if (n1->startbit > n2->startbit) {
> +			n2 = n2->next;
> +		} else {
> +			n1 = n1->next;
>  		}
>  	}
> +
> +	if (new)
> +		dst->highbit = new->startbit + EBITMAP_SIZE;
> +
>  	return 0;
>  }
>  
> -- 
> 2.43.0

--
paul-moore.com