SELinux Archive on lore.kernel.org
 help / color / Atom feed
* [PATCH userspace v2] libsepol: cache ebitmap cardinality value
@ 2020-02-13 13:39 Ondrej Mosnacek
  2020-02-14 17:38 ` Stephen Smalley
  2020-02-18 15:22 ` Ondrej Mosnacek
  0 siblings, 2 replies; 9+ messages in thread
From: Ondrej Mosnacek @ 2020-02-13 13:39 UTC (permalink / raw)
  To: selinux

According to profiling of semodule -BN, ebitmap_cardinality() is called
quite often and contributes a lot to the total runtime. Cache its result
in the ebitmap struct to reduce this overhead. The cached value is
invalidated on most modifying operations, but ebitmap_cardinality() is
usually called once the ebitmap doesn't change any more.

After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
decreased from ~14.6s to ~12.4s (2.2s saved).

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

v2: corrected time values in commit message

 libsepol/include/sepol/policydb/ebitmap.h |  1 +
 libsepol/src/ebitmap.c                    | 10 ++++++++++
 2 files changed, 11 insertions(+)

diff --git a/libsepol/include/sepol/policydb/ebitmap.h b/libsepol/include/sepol/policydb/ebitmap.h
index e62df01c..53fafdaa 100644
--- a/libsepol/include/sepol/policydb/ebitmap.h
+++ b/libsepol/include/sepol/policydb/ebitmap.h
@@ -37,6 +37,7 @@ typedef struct ebitmap_node {
 typedef struct ebitmap {
 	ebitmap_node_t *node;	/* first node in the bitmap */
 	uint32_t highbit;	/* highest position in the total bitmap */
+	unsigned int cardinality;	/* cached value of cardinality */
 } ebitmap_t;
 
 #define ebitmap_length(e) ((e)->highbit)
diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
index 6c9951b7..d23444ce 100644
--- a/libsepol/src/ebitmap.c
+++ b/libsepol/src/ebitmap.c
@@ -67,6 +67,7 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
 	ebitmap_destroy(dst);
 	dst->node = tmp.node;
 	dst->highbit = tmp.highbit;
+	dst->cardinality = 0;
 
 	return 0;
 }
@@ -128,9 +129,14 @@ 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;
+
+	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++;
+	e1->cardinality = count;
 	return count;
 }
 
@@ -194,6 +200,7 @@ int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
 	}
 
 	dst->highbit = src->highbit;
+	dst->cardinality = src->cardinality;
 	return 0;
 }
 
@@ -309,6 +316,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
 					free(n);
 				}
 			}
+			e->cardinality = 0; /* invalidate cached cardinality */
 			return 0;
 		}
 		prev = n;
@@ -339,6 +347,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
 		e->node = new;
 	}
 
+	e->cardinality = 0; /* invalidate cached cardinality */
 	return 0;
 }
 
@@ -358,6 +367,7 @@ void ebitmap_destroy(ebitmap_t * e)
 
 	e->highbit = 0;
 	e->node = 0;
+	e->cardinality = 0;
 	return;
 }
 
-- 
2.24.1


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value
  2020-02-13 13:39 [PATCH userspace v2] libsepol: cache ebitmap cardinality value Ondrej Mosnacek
@ 2020-02-14 17:38 ` Stephen Smalley
  2020-02-14 18:20   ` Stephen Smalley
  2020-02-14 19:51   ` Ondrej Mosnacek
  2020-02-18 15:22 ` Ondrej Mosnacek
  1 sibling, 2 replies; 9+ messages in thread
From: Stephen Smalley @ 2020-02-14 17:38 UTC (permalink / raw)
  To: Ondrej Mosnacek, selinux, James Carter

On 2/13/20 8:39 AM, Ondrej Mosnacek wrote:
> According to profiling of semodule -BN, ebitmap_cardinality() is called
> quite often and contributes a lot to the total runtime. Cache its result
> in the ebitmap struct to reduce this overhead. The cached value is
> invalidated on most modifying operations, but ebitmap_cardinality() is
> usually called once the ebitmap doesn't change any more.
> 
> After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
> decreased from ~14.6s to ~12.4s (2.2s saved).
> 
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>

This seems fine but I was wondering how many of the callers of 
ebitmap_cardinality() actually need anything more than ebitmap_length()?

> ---
> 
> v2: corrected time values in commit message
> 
>   libsepol/include/sepol/policydb/ebitmap.h |  1 +
>   libsepol/src/ebitmap.c                    | 10 ++++++++++
>   2 files changed, 11 insertions(+)
> 
> diff --git a/libsepol/include/sepol/policydb/ebitmap.h b/libsepol/include/sepol/policydb/ebitmap.h
> index e62df01c..53fafdaa 100644
> --- a/libsepol/include/sepol/policydb/ebitmap.h
> +++ b/libsepol/include/sepol/policydb/ebitmap.h
> @@ -37,6 +37,7 @@ typedef struct ebitmap_node {
>   typedef struct ebitmap {
>   	ebitmap_node_t *node;	/* first node in the bitmap */
>   	uint32_t highbit;	/* highest position in the total bitmap */
> +	unsigned int cardinality;	/* cached value of cardinality */
>   } ebitmap_t;
>   
>   #define ebitmap_length(e) ((e)->highbit)
> diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
> index 6c9951b7..d23444ce 100644
> --- a/libsepol/src/ebitmap.c
> +++ b/libsepol/src/ebitmap.c
> @@ -67,6 +67,7 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
>   	ebitmap_destroy(dst);
>   	dst->node = tmp.node;
>   	dst->highbit = tmp.highbit;
> +	dst->cardinality = 0;
>   
>   	return 0;
>   }
> @@ -128,9 +129,14 @@ 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;
> +
> +	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++;
> +	e1->cardinality = count;
>   	return count;
>   }
>   
> @@ -194,6 +200,7 @@ int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
>   	}
>   
>   	dst->highbit = src->highbit;
> +	dst->cardinality = src->cardinality;
>   	return 0;
>   }
>   
> @@ -309,6 +316,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
>   					free(n);
>   				}
>   			}
> +			e->cardinality = 0; /* invalidate cached cardinality */
>   			return 0;
>   		}
>   		prev = n;
> @@ -339,6 +347,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
>   		e->node = new;
>   	}
>   
> +	e->cardinality = 0; /* invalidate cached cardinality */
>   	return 0;
>   }
>   
> @@ -358,6 +367,7 @@ void ebitmap_destroy(ebitmap_t * e)
>   
>   	e->highbit = 0;
>   	e->node = 0;
> +	e->cardinality = 0;
>   	return;
>   }
>   
> 


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value
  2020-02-14 17:38 ` Stephen Smalley
@ 2020-02-14 18:20   ` Stephen Smalley
  2020-02-14 19:51   ` Ondrej Mosnacek
  1 sibling, 0 replies; 9+ messages in thread
From: Stephen Smalley @ 2020-02-14 18:20 UTC (permalink / raw)
  To: Ondrej Mosnacek, selinux, James Carter

On 2/14/20 12:38 PM, Stephen Smalley wrote:
> On 2/13/20 8:39 AM, Ondrej Mosnacek wrote:
>> According to profiling of semodule -BN, ebitmap_cardinality() is called
>> quite often and contributes a lot to the total runtime. Cache its result
>> in the ebitmap struct to reduce this overhead. The cached value is
>> invalidated on most modifying operations, but ebitmap_cardinality() is
>> usually called once the ebitmap doesn't change any more.
>>
>> After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
>> decreased from ~14.6s to ~12.4s (2.2s saved).
>>
>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> 
> This seems fine but I was wondering how many of the callers of 
> ebitmap_cardinality() actually need anything more than ebitmap_length()?

Regardless,

Acked-by: Stephen Smalley <sds@tycho.nsa.gov>

> 
>> ---
>>
>> v2: corrected time values in commit message
>>
>>   libsepol/include/sepol/policydb/ebitmap.h |  1 +
>>   libsepol/src/ebitmap.c                    | 10 ++++++++++
>>   2 files changed, 11 insertions(+)
>>
>> diff --git a/libsepol/include/sepol/policydb/ebitmap.h 
>> b/libsepol/include/sepol/policydb/ebitmap.h
>> index e62df01c..53fafdaa 100644
>> --- a/libsepol/include/sepol/policydb/ebitmap.h
>> +++ b/libsepol/include/sepol/policydb/ebitmap.h
>> @@ -37,6 +37,7 @@ typedef struct ebitmap_node {
>>   typedef struct ebitmap {
>>       ebitmap_node_t *node;    /* first node in the bitmap */
>>       uint32_t highbit;    /* highest position in the total bitmap */
>> +    unsigned int cardinality;    /* cached value of cardinality */
>>   } ebitmap_t;
>>   #define ebitmap_length(e) ((e)->highbit)
>> diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
>> index 6c9951b7..d23444ce 100644
>> --- a/libsepol/src/ebitmap.c
>> +++ b/libsepol/src/ebitmap.c
>> @@ -67,6 +67,7 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * 
>> e1)
>>       ebitmap_destroy(dst);
>>       dst->node = tmp.node;
>>       dst->highbit = tmp.highbit;
>> +    dst->cardinality = 0;
>>       return 0;
>>   }
>> @@ -128,9 +129,14 @@ 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;
>> +
>> +    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++;
>> +    e1->cardinality = count;
>>       return count;
>>   }
>> @@ -194,6 +200,7 @@ int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * 
>> src)
>>       }
>>       dst->highbit = src->highbit;
>> +    dst->cardinality = src->cardinality;
>>       return 0;
>>   }
>> @@ -309,6 +316,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int 
>> bit, int value)
>>                       free(n);
>>                   }
>>               }
>> +            e->cardinality = 0; /* invalidate cached cardinality */
>>               return 0;
>>           }
>>           prev = n;
>> @@ -339,6 +347,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int 
>> bit, int value)
>>           e->node = new;
>>       }
>> +    e->cardinality = 0; /* invalidate cached cardinality */
>>       return 0;
>>   }
>> @@ -358,6 +367,7 @@ void ebitmap_destroy(ebitmap_t * e)
>>       e->highbit = 0;
>>       e->node = 0;
>> +    e->cardinality = 0;
>>       return;
>>   }
>>
> 


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value
  2020-02-14 17:38 ` Stephen Smalley
  2020-02-14 18:20   ` Stephen Smalley
@ 2020-02-14 19:51   ` Ondrej Mosnacek
  2020-02-14 19:57     ` Stephen Smalley
  2020-02-14 20:19     ` Ondrej Mosnacek
  1 sibling, 2 replies; 9+ messages in thread
From: Ondrej Mosnacek @ 2020-02-14 19:51 UTC (permalink / raw)
  To: Stephen Smalley; +Cc: SElinux list, James Carter

On Fri, Feb 14, 2020 at 6:37 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> On 2/13/20 8:39 AM, Ondrej Mosnacek wrote:
> > According to profiling of semodule -BN, ebitmap_cardinality() is called
> > quite often and contributes a lot to the total runtime. Cache its result
> > in the ebitmap struct to reduce this overhead. The cached value is
> > invalidated on most modifying operations, but ebitmap_cardinality() is
> > usually called once the ebitmap doesn't change any more.
> >
> > After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
> > decreased from ~14.6s to ~12.4s (2.2s saved).
> >
> > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>
> This seems fine but I was wondering how many of the callers of
> ebitmap_cardinality() actually need anything more than ebitmap_length()?

The caller that calls it the most (>99%) during a 'semodule -B' is
__cil_should_expand_attribute(), which logically needs the actual
cardinality. It might be possible to cache the decision directly in
'struct cil_typeattribute', but I don't know the CIL code well enough
to attempt that...

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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value
  2020-02-14 19:51   ` Ondrej Mosnacek
@ 2020-02-14 19:57     ` Stephen Smalley
  2020-02-14 20:19     ` Ondrej Mosnacek
  1 sibling, 0 replies; 9+ messages in thread
From: Stephen Smalley @ 2020-02-14 19:57 UTC (permalink / raw)
  To: Ondrej Mosnacek; +Cc: SElinux list, James Carter

On 2/14/20 2:51 PM, Ondrej Mosnacek wrote:
> On Fri, Feb 14, 2020 at 6:37 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
>> On 2/13/20 8:39 AM, Ondrej Mosnacek wrote:
>>> According to profiling of semodule -BN, ebitmap_cardinality() is called
>>> quite often and contributes a lot to the total runtime. Cache its result
>>> in the ebitmap struct to reduce this overhead. The cached value is
>>> invalidated on most modifying operations, but ebitmap_cardinality() is
>>> usually called once the ebitmap doesn't change any more.
>>>
>>> After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
>>> decreased from ~14.6s to ~12.4s (2.2s saved).
>>>
>>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>>
>> This seems fine but I was wondering how many of the callers of
>> ebitmap_cardinality() actually need anything more than ebitmap_length()?
> 
> The caller that calls it the most (>99%) during a 'semodule -B' is
> __cil_should_expand_attribute(), which logically needs the actual
> cardinality. It might be possible to cache the decision directly in
> 'struct cil_typeattribute', but I don't know the CIL code well enough
> to attempt that...

That's fine - I'm ok with the patch itself.  I just happened to notice 
that there appear to be quite a few callers elsewhere in libsepol that 
only seem to care whether the result is zero or non-zero, which 
seemingly would be just as happy using ebitmap_length().



^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value
  2020-02-14 19:51   ` Ondrej Mosnacek
  2020-02-14 19:57     ` Stephen Smalley
@ 2020-02-14 20:19     ` Ondrej Mosnacek
  1 sibling, 0 replies; 9+ messages in thread
From: Ondrej Mosnacek @ 2020-02-14 20:19 UTC (permalink / raw)
  To: Stephen Smalley; +Cc: SElinux list, James Carter

On Fri, Feb 14, 2020 at 8:51 PM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> On Fri, Feb 14, 2020 at 6:37 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> > On 2/13/20 8:39 AM, Ondrej Mosnacek wrote:
> > > According to profiling of semodule -BN, ebitmap_cardinality() is called
> > > quite often and contributes a lot to the total runtime. Cache its result
> > > in the ebitmap struct to reduce this overhead. The cached value is
> > > invalidated on most modifying operations, but ebitmap_cardinality() is
> > > usually called once the ebitmap doesn't change any more.
> > >
> > > After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
> > > decreased from ~14.6s to ~12.4s (2.2s saved).
> > >
> > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> >
> > This seems fine but I was wondering how many of the callers of
> > ebitmap_cardinality() actually need anything more than ebitmap_length()?
>
> The caller that calls it the most (>99%) during a 'semodule -B' is
> __cil_should_expand_attribute(), which logically needs the actual
> cardinality. It might be possible to cache the decision directly in
> 'struct cil_typeattribute', but I don't know the CIL code well enough
> to attempt that...

BTW, in case anyone is wondering how I'm getting these numbers/facts -
I use Callgrind [1] to profile a program's run and then analyze it
with KCachegrind [2]. It is a surprisingly nice and easy to use GUI
for analyzing where the program spends most of its time.

Collecting the profile data is as simple as:

LD_BIND_NOW=1 valgrind --tool=callgrind <your_command> <args>...

(The LD_BIND_NOW=1 is to prevent the dynamic linker's lazy binding
from messing with the results.)

Then you can just open the generated "callgrind.out.<pid>" file with
KCachegrind and click around... Note that to see the function names,
you need to compile the program with -g (but you should keep -O2 et
al. to get the same optimized code as an actual build). Alternatively,
Callgrind will also auto-detect and use debug symbols provided by
distributions in their -debug/-debuginfo packages.

Maybe this is common knowledge for most, but perhaps someone here will
be one of today's lucky 10000 :) [3]

[1] https://valgrind.org/docs/manual/cl-manual.html
[2] https://kcachegrind.github.io/html/Home.html
[3] https://xkcd.com/1053/

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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value
  2020-02-13 13:39 [PATCH userspace v2] libsepol: cache ebitmap cardinality value Ondrej Mosnacek
  2020-02-14 17:38 ` Stephen Smalley
@ 2020-02-18 15:22 ` Ondrej Mosnacek
  2020-02-18 15:41   ` Stephen Smalley
  1 sibling, 1 reply; 9+ messages in thread
From: Ondrej Mosnacek @ 2020-02-18 15:22 UTC (permalink / raw)
  To: SElinux list; +Cc: Stephen Smalley

On Thu, Feb 13, 2020 at 2:40 PM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> According to profiling of semodule -BN, ebitmap_cardinality() is called
> quite often and contributes a lot to the total runtime. Cache its result
> in the ebitmap struct to reduce this overhead. The cached value is
> invalidated on most modifying operations, but ebitmap_cardinality() is
> usually called once the ebitmap doesn't change any more.
>
> After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
> decreased from ~14.6s to ~12.4s (2.2s saved).

I have no idea why, but I'm now getting completely different times
(10.9s vs. 8.9s) with the same builds on the same setup... I can no
longer reproduce the slower times anywhere (F31/locally/...) so I have
to assume it was some kind of glitch. Since the numbers show a similar
magnitude of speed-up (and they depend on a bunch of HW/SW factors
anyway), I'm not going to do another respin. The applying person (most
likely Stephen) is free to fix the numbers when applying if they wish
to do so.

>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
>
> v2: corrected time values in commit message
>
>  libsepol/include/sepol/policydb/ebitmap.h |  1 +
>  libsepol/src/ebitmap.c                    | 10 ++++++++++
>  2 files changed, 11 insertions(+)
>
> diff --git a/libsepol/include/sepol/policydb/ebitmap.h b/libsepol/include/sepol/policydb/ebitmap.h
> index e62df01c..53fafdaa 100644
> --- a/libsepol/include/sepol/policydb/ebitmap.h
> +++ b/libsepol/include/sepol/policydb/ebitmap.h
> @@ -37,6 +37,7 @@ typedef struct ebitmap_node {
>  typedef struct ebitmap {
>         ebitmap_node_t *node;   /* first node in the bitmap */
>         uint32_t highbit;       /* highest position in the total bitmap */
> +       unsigned int cardinality;       /* cached value of cardinality */
>  } ebitmap_t;
>
>  #define ebitmap_length(e) ((e)->highbit)
> diff --git a/libsepol/src/ebitmap.c b/libsepol/src/ebitmap.c
> index 6c9951b7..d23444ce 100644
> --- a/libsepol/src/ebitmap.c
> +++ b/libsepol/src/ebitmap.c
> @@ -67,6 +67,7 @@ int ebitmap_union(ebitmap_t * dst, const ebitmap_t * e1)
>         ebitmap_destroy(dst);
>         dst->node = tmp.node;
>         dst->highbit = tmp.highbit;
> +       dst->cardinality = 0;
>
>         return 0;
>  }
> @@ -128,9 +129,14 @@ 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;
> +
> +       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++;
> +       e1->cardinality = count;
>         return count;
>  }
>
> @@ -194,6 +200,7 @@ int ebitmap_cpy(ebitmap_t * dst, const ebitmap_t * src)
>         }
>
>         dst->highbit = src->highbit;
> +       dst->cardinality = src->cardinality;
>         return 0;
>  }
>
> @@ -309,6 +316,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
>                                         free(n);
>                                 }
>                         }
> +                       e->cardinality = 0; /* invalidate cached cardinality */
>                         return 0;
>                 }
>                 prev = n;
> @@ -339,6 +347,7 @@ int ebitmap_set_bit(ebitmap_t * e, unsigned int bit, int value)
>                 e->node = new;
>         }
>
> +       e->cardinality = 0; /* invalidate cached cardinality */
>         return 0;
>  }
>
> @@ -358,6 +367,7 @@ void ebitmap_destroy(ebitmap_t * e)
>
>         e->highbit = 0;
>         e->node = 0;
> +       e->cardinality = 0;
>         return;
>  }
>
> --
> 2.24.1
>


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


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value
  2020-02-18 15:22 ` Ondrej Mosnacek
@ 2020-02-18 15:41   ` Stephen Smalley
  2020-02-18 16:01     ` Ondrej Mosnacek
  0 siblings, 1 reply; 9+ messages in thread
From: Stephen Smalley @ 2020-02-18 15:41 UTC (permalink / raw)
  To: Ondrej Mosnacek, SElinux list

On 2/18/20 10:22 AM, Ondrej Mosnacek wrote:
> On Thu, Feb 13, 2020 at 2:40 PM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>> According to profiling of semodule -BN, ebitmap_cardinality() is called
>> quite often and contributes a lot to the total runtime. Cache its result
>> in the ebitmap struct to reduce this overhead. The cached value is
>> invalidated on most modifying operations, but ebitmap_cardinality() is
>> usually called once the ebitmap doesn't change any more.
>>
>> After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
>> decreased from ~14.6s to ~12.4s (2.2s saved).
> 
> I have no idea why, but I'm now getting completely different times
> (10.9s vs. 8.9s) with the same builds on the same setup... I can no
> longer reproduce the slower times anywhere (F31/locally/...) so I have
> to assume it was some kind of glitch. Since the numbers show a similar
> magnitude of speed-up (and they depend on a bunch of HW/SW factors
> anyway), I'm not going to do another respin. The applying person (most
> likely Stephen) is free to fix the numbers when applying if they wish
> to do so.

Thanks, applied with fixed times (although I don't really think it 
matters very much).  Maybe you're also picking up the difference from 
the "libsepol/cil: remove unnecessary hash tables" change.


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value
  2020-02-18 15:41   ` Stephen Smalley
@ 2020-02-18 16:01     ` Ondrej Mosnacek
  0 siblings, 0 replies; 9+ messages in thread
From: Ondrej Mosnacek @ 2020-02-18 16:01 UTC (permalink / raw)
  To: Stephen Smalley; +Cc: SElinux list

On Tue, Feb 18, 2020 at 4:40 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> On 2/18/20 10:22 AM, Ondrej Mosnacek wrote:
> > On Thu, Feb 13, 2020 at 2:40 PM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> >> According to profiling of semodule -BN, ebitmap_cardinality() is called
> >> quite often and contributes a lot to the total runtime. Cache its result
> >> in the ebitmap struct to reduce this overhead. The cached value is
> >> invalidated on most modifying operations, but ebitmap_cardinality() is
> >> usually called once the ebitmap doesn't change any more.
> >>
> >> After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
> >> decreased from ~14.6s to ~12.4s (2.2s saved).
> >
> > I have no idea why, but I'm now getting completely different times
> > (10.9s vs. 8.9s) with the same builds on the same setup... I can no
> > longer reproduce the slower times anywhere (F31/locally/...) so I have
> > to assume it was some kind of glitch. Since the numbers show a similar
> > magnitude of speed-up (and they depend on a bunch of HW/SW factors
> > anyway), I'm not going to do another respin. The applying person (most
> > likely Stephen) is free to fix the numbers when applying if they wish
> > to do so.
>
> Thanks, applied with fixed times (although I don't really think it
> matters very much).  Maybe you're also picking up the difference from
> the "libsepol/cil: remove unnecessary hash tables" change.

No, that was actually the reason for the first correction.

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


^ permalink raw reply	[flat|nested] 9+ messages in thread

end of thread, back to index

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-02-13 13:39 [PATCH userspace v2] libsepol: cache ebitmap cardinality value Ondrej Mosnacek
2020-02-14 17:38 ` Stephen Smalley
2020-02-14 18:20   ` Stephen Smalley
2020-02-14 19:51   ` Ondrej Mosnacek
2020-02-14 19:57     ` Stephen Smalley
2020-02-14 20:19     ` Ondrej Mosnacek
2020-02-18 15:22 ` Ondrej Mosnacek
2020-02-18 15:41   ` Stephen Smalley
2020-02-18 16:01     ` Ondrej Mosnacek

SELinux Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/selinux/0 selinux/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 selinux selinux/ https://lore.kernel.org/selinux \
		selinux@vger.kernel.org
	public-inbox-index selinux

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.selinux


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git