| Message ID | 20200212115140.107017-1-omosnace@redhat.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | [userspace] libsepol: cache ebitmap cardinality value | expand |
On Wed, Feb 12, 2020 at 12:51 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 ~21.4s to ~18.6s (2.8s saved). Please don't ack/merge this yet, I need to re-evaluate these numbers... > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> > --- > 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 >
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; }
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 ~21.4s to ~18.6s (2.8s saved). Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com> --- libsepol/include/sepol/policydb/ebitmap.h | 1 + libsepol/src/ebitmap.c | 10 ++++++++++ 2 files changed, 11 insertions(+)