Re: [PATCH 1/1] libsepol: make ebitmap_cardinality() of linear complexity

[Ondrej Mosnacek <omosnace@redhat.com>]

On Tue, Feb 25, 2020 at 11:49 PM Nicolas Iooss <nicolas.iooss@m4x.org> wrote:
> As ebitmap_get_bit() complexity is linear in the size of the bitmap, the
> complexity of ebitmap_cardinality() is quadratic. This can be optimized
> by browsing the nodes of the bitmap directly in ebitmap_cardinality().
>
> While at it, use built-in function __builtin_popcountll() to count the
> ones in the 64-bit value n->map for each bitmap node. This seems better
> suited than "count++". This seems to work on gcc and clang on x86,
> x86_64, ARM and ARM64 but if it causes compatibility issues with some
> compilers or architectures (or with older versions of gcc or clang),
> the use of __builtin_popcountll() can be replaced by a C implementation
> of a popcount algorithm.
>
> Signed-off-by: Nicolas Iooss <nicolas.iooss@m4x.org>
> ---
>  libsepol/src/ebitmap.c | 9 +++++----
>  1 file changed, 5 insertions(+), 4 deletions(-)
>
> diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
> index d23444ce5064..a5108b7184c5 100644
> --- a/libsepol/src/ebitmap.c
> +++ b/libsepol/src/ebitmap.c
> @@ -128,14 +128,15 @@ int ebitmap_andnot(ebitmap_t *dst, ebitmap_t *e1, ebitmap_t *e2, unsigned int ma
>
>  unsigned int ebitmap_cardinality(ebitmap_t *e1)
>  {
> -       unsigned int i, count = 0;
> +       unsigned int count = 0;
> +       ebitmap_node_t *n;
>
>         if (e1->cardinality || e1->highbit == 0)
>                 return e1->cardinality;
>
> -       for (i=ebitmap_startbit(e1); i < ebitmap_length(e1); i++)
> -               if (ebitmap_get_bit(e1, i))
> -                       count++;
> +       for (n = e1->node; n; n = n->next) {
> +               count += __builtin_popcountll(n->map);
> +       }
>         e1->cardinality = count;
>         return count;
>  }
> --
> 2.25.0
>

Acked-by: Ondrej Mosnacek <omosnace@redhat.com>

I'll check if the cardinality caching still makes any measurable
difference and if not, I'll post a revert patch.

-- 
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.