From: Ondrej Mosnacek <omosnace@redhat.com>
To: selinux@vger.kernel.org
Subject: [PATCH userspace v2] libsepol: cache ebitmap cardinality value
Date: Thu, 13 Feb 2020 14:39:59 +0100 [thread overview]
Message-ID: <20200213133959.14217-1-omosnace@redhat.com> (raw)
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
next reply other threads:[~2020-02-13 13:40 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-02-13 13:39 Ondrej Mosnacek [this message]
2020-02-14 17:38 ` [PATCH userspace v2] libsepol: cache ebitmap cardinality value 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
2020-02-25 21:24 ` Nicolas Iooss
2020-02-25 21:56 ` William Roberts
2020-02-26 13:23 ` Ondrej Mosnacek
2020-02-26 15:39 ` William Roberts
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20200213133959.14217-1-omosnace@redhat.com \
--to=omosnace@redhat.com \
--cc=selinux@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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 NNTP newsgroup(s).