| Message ID | 20240315181204.647182-1-cgzones@googlemail.com (mailing list archive) |
|---|---|
| State | Changes Requested |
| Delegated to: | Paul Moore |
| Headers | show |
| Series | [v3] selinux: optimize ebitmap_and() | expand |
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
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; }
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(-)