* [PATCH v3] selinux: optimize ebitmap_and()
@ 2024-03-15 18:11 Christian Göttsche
2024-03-27 22:07 ` Paul Moore
0 siblings, 1 reply; 2+ messages in thread
From: Christian Göttsche @ 2024-03-15 18:11 UTC (permalink / raw
To: selinux; +Cc: Paul Moore, Stephen Smalley, Ondrej Mosnacek, linux-kernel
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(-)
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;
+ n1 = e1->node;
+ n2 = e2->node;
+ while (n1 && n2) {
+ if (n1->startbit == n2->startbit) {
+ unsigned long testmap[EBITMAP_UNIT_NUMS];
+ 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)
+ 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);
+ new->next = NULL;
+
+ *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
^ permalink raw reply related [flat|nested] 2+ messages in thread
* Re: [PATCH v3] selinux: optimize ebitmap_and()
2024-03-15 18:11 [PATCH v3] selinux: optimize ebitmap_and() Christian Göttsche
@ 2024-03-27 22:07 ` Paul Moore
0 siblings, 0 replies; 2+ messages in thread
From: Paul Moore @ 2024-03-27 22:07 UTC (permalink / raw
To: Christian Göttsche, selinux
Cc: Stephen Smalley, Ondrej Mosnacek, linux-kernel
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
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2024-03-27 22:07 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-03-15 18:11 [PATCH v3] selinux: optimize ebitmap_and() Christian Göttsche
2024-03-27 22:07 ` Paul Moore
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).