When mls_compute_context_len() or mls_sid_to_context() encounters a
context with large category ranges, it behaves suboptimally - it
traverses each positive bit of the category bitmap, each time calling
find_next_bit() again.
This has a large performance impact on UNIX datagram sockets with
SO_PASSSEC set, since here the peer context needs to be converted to
string for each recieved datagram. See [1] for more information.
This patch introduces a new helper for ebitmap traversal, which allows
to efficiently iterate over positive ranges instead of bits -
ebitmap_for_each_positive_range() - and converts the two mls_*()
functions to leverage it.
[1] https://bugzilla.redhat.com/show_bug.cgi?id=1733259
Reported-by: Michal Sekletar <msekleta@xxxxxxxxxx>
Signed-off-by: Ondrej Mosnacek <omosnace@xxxxxxxxxx>
---
security/selinux/ss/ebitmap.h | 46 +++++++++++++++++++++
security/selinux/ss/mls.c | 76 +++++++++++++----------------------
2 files changed, 73 insertions(+), 49 deletions(-)
diff --git a/security/selinux/ss/ebitmap.h b/security/selinux/ss/ebitmap.h
index 6aa7cf6a2197..a415741cb206 100644
--- a/security/selinux/ss/ebitmap.h
+++ b/security/selinux/ss/ebitmap.h
@@ -42,6 +42,10 @@ struct ebitmap {
u32 highbit; /* highest position in the total bitmap */
};
+struct ebitmap_range {
+ unsigned int start, end;
+};
+
#define ebitmap_length(e) ((e)->highbit)
static inline unsigned int ebitmap_start_positive(struct ebitmap *e,
@@ -80,6 +84,43 @@ static inline unsigned int ebitmap_next_positive(struct ebitmap *e,
return ebitmap_length(e);
}
+static inline unsigned int ebitmap_next_negative(struct ebitmap *e,
+ struct ebitmap_node **n,
+ unsigned int bit)
+{
+ unsigned int ofs;
+
+ ofs = find_next_zero_bit((*n)->maps, EBITMAP_SIZE,
+ bit - (*n)->startbit + 1);
+ if (ofs < EBITMAP_SIZE)
+ return ofs + (*n)->startbit;
+
+ for (*n = (*n)->next; *n; *n = (*n)->next) {
+ ofs = find_first_zero_bit((*n)->maps, EBITMAP_SIZE);
+ if (ofs < EBITMAP_SIZE)
+ return ofs + (*n)->startbit;
+ }
+ return ebitmap_length(e);
+}
+
+static inline void ebitmap_start_positive_range(struct ebitmap *e,
+ struct ebitmap_node **n,
+ struct ebitmap_range *range)
+{
+ range->end = range->start = ebitmap_start_positive(e, n);
+ if (range->start < ebitmap_length(e))
+ range->end = ebitmap_next_negative(e, n, range->start);
+}
+
+static inline void ebitmap_next_positive_range(struct ebitmap *e,
+ struct ebitmap_node **n,
+ struct ebitmap_range *range)
+{
+ range->end = range->start = ebitmap_next_positive(e, n, range->end);
+ if (range->start < ebitmap_length(e))
+ range->end = ebitmap_next_negative(e, n, range->start);
+}
+
#define EBITMAP_NODE_INDEX(node, bit) \
(((bit) - (node)->startbit) / EBITMAP_UNIT_SIZE)
#define EBITMAP_NODE_OFFSET(node, bit) \
@@ -122,6 +163,11 @@ static inline void ebitmap_node_clr_bit(struct ebitmap_node *n,
bit < ebitmap_length(e); \
bit = ebitmap_next_positive(e, &n, bit)) \
+#define ebitmap_for_each_positive_range(e, n, range) \
+ for (ebitmap_start_positive_range(e, &n, &range); \
+ range.start < ebitmap_length(e); \
+ ebitmap_next_positive_range(e, &n, &range)) \
+
int ebitmap_cmp(struct ebitmap *e1, struct ebitmap *e2);
int ebitmap_cpy(struct ebitmap *dst, struct ebitmap *src);
int ebitmap_contains(struct ebitmap *e1, struct ebitmap *e2, u32 last_e2bit);
diff --git a/security/selinux/ss/mls.c b/security/selinux/ss/mls.c
index 5e05f5b902d7..3abd6b950c66 100644
--- a/security/selinux/ss/mls.c
+++ b/security/selinux/ss/mls.c
@@ -35,10 +35,12 @@
*/
int mls_compute_context_len(struct policydb *p, struct context *context)
{
- int i, l, len, head, prev;
+ int l, len;
char *nm;
struct ebitmap *e;
struct ebitmap_node *node;
+ struct ebitmap_range range;
+ unsigned int rlen;
if (!p->mls_enabled)
return 0;
@@ -49,24 +51,14 @@ int mls_compute_context_len(struct policydb *p, struct context *context)
len += strlen(sym_name(p, SYM_LEVELS, index_sens - 1));
/* categories */
- head = -2;
- prev = -2;
e = &context->range.level[l].cat;
- ebitmap_for_each_positive_bit(e, node, i) {
- if (i - prev > 1) {
- /* one or more negative bits are skipped */
- if (head != prev) {
- nm = sym_name(p, SYM_CATS, prev);
- len += strlen(nm) + 1;
- }
- nm = sym_name(p, SYM_CATS, i);
+ ebitmap_for_each_positive_range(e, node, range) {
+ rlen = range.end - range.start;
+ if (rlen > 1) {
+ nm = sym_name(p, SYM_CATS, range.start);
len += strlen(nm) + 1;
- head = i;
}
- prev = i;
- }
- if (prev != head) {
- nm = sym_name(p, SYM_CATS, prev);
+ nm = sym_name(p, SYM_CATS, range.end - 1);
len += strlen(nm) + 1;
}
if (l == 0) {
@@ -91,9 +83,11 @@ void mls_sid_to_context(struct policydb *p,
char **scontext)
{
char *scontextp, *nm;
- int i, l, head, prev;
+ int l, first;
struct ebitmap *e;
struct ebitmap_node *node;
+ struct ebitmap_range range;
+ unsigned int rlen;
if (!p->mls_enabled)
return;
@@ -109,43 +103,27 @@ void mls_sid_to_context(struct policydb *p,
scontextp += strlen(scontextp);
/* categories */
- head = -2;
- prev = -2;
+ first = 1;
e = &context->range.level[l].cat;
- ebitmap_for_each_positive_bit(e, node, i) {
- if (i - prev > 1) {
- /* one or more negative bits are skipped */
- if (prev != head) {
- if (prev - head > 1)
- *scontextp++ = '.';
- else
- *scontextp++ = ',';
- nm = sym_name(p, SYM_CATS, prev);
- strcpy(scontextp, nm);
- scontextp += strlen(nm);
- }
- if (prev < 0)
- *scontextp++ = ':';
- else
- *scontextp++ = ',';
- nm = sym_name(p, SYM_CATS, i);
- strcpy(scontextp, nm);
- scontextp += strlen(nm);
- head = i;
- }
- prev = i;
- }
-
- if (prev != head) {
- if (prev - head > 1)
- *scontextp++ = '.';
- else
+ ebitmap_for_each_positive_range(e, node, range) {
+ if (first) {
+ first = 0;
+ *scontextp++ = ':';
+ } else {
*scontextp++ = ',';
- nm = sym_name(p, SYM_CATS, prev);
+ }
+ nm = sym_name(p, SYM_CATS, range.start);
strcpy(scontextp, nm);
scontextp += strlen(nm);
- }
+ rlen = range.end - range.start;
+ if (rlen > 1) {
+ *scontextp++ = rlen > 2 ? '.' : ',';
+ nm = sym_name(p, SYM_CATS, range.end - 1);
+ strcpy(scontextp, nm);
+ scontextp += strlen(nm);
+ }
+ }
if (l == 0) {
if (mls_level_eq(&context->range.level[0],
&context->range.level[1]))
