Skip to contentSkip to conversation

selinux: optimize MLS context to string conversion

PATCH In review Ondrej Mosnacek 4 participants 6 messages Jul 30, 2019 – Sep 17, 2019 SELinux security module

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 selinux: optimize MLS context to string conversion

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

---
 security/selinux/ss/ebitmap.h | 46 +++++++++++++++++++++
 security/selinux/ss/mls.c     | 76 +++++++++++++----------------------
 2 files changed, 73 insertions(+), 49 deletions(-)
security/selinux/ss/ebitmap.h +46 -0
index 6aa7cf6a2197..a415741cb206 100644
@@ -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);
security/selinux/ss/mls.c +27 -49

113 lines not on this page · raw message

Signature · 1 line
2.21.0
maintainer
#1 lore raw
Quoted 14 lines · Ondrej Mosnacek

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.

Quoted 4 lines

[1] https://bugzilla.redhat.com/show_bug.cgi?id=1733259

My current opinion is that this isn't the right way to solve the problem, a SELinux sid->secctx cache would be a better choice. With that in mind, and the understanding that this patch is an optimization and not a bug fix, I'm going to hold-off on doing anything with this patch until there is a cache option we can use for comparison.

As Stephen mentioned in the RH BZ (linked in the description), there are a couple of reasons why the code doesn't currently store the string translations. Ignoring the issue of aliasing for a moment, I do want to stress that I agree with Stephen on the issue of memory pressure and that to keep translated strings around indefinitely in the kernel is going to be a problem (there are other issues beyond just memory use). I imagine any cache implementation would need to be built to only store a subset of all the translations and there would need to be a way to age-out those translations (as well as purge them completely on events such as a policy load).

Signature · 2 lines
paul moore
www.paul-moore.com
#2 lore raw
Quoted 15 lines · Paul Moore
Quoted 14 lines · Ondrej Mosnacek

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.

Quoted 6 lines
Quoted 4 lines

[1] https://bugzilla.redhat.com/show_bug.cgi?id=1733259

My current opinion is that this isn't the right way to solve the problem, a SELinux sid->secctx cache would be a better choice.

I implemented secctx retention a while ago (can't locate the thread to determine exactly when) and the performance improvement was rather impressive. A cache with proper lifecycle management would be a tremendous win for audit by reducing not only the time required to generate a secctx, but the frequency at which they would need to be copied. The downside would be on small systems with sophisticated policies, where a small cache would be subject to thrashing. If the cached values aren't considered when doing secctx->sid conversions I would think aliasing issues wouldn't apply, although I have missed subtleties in the past.

I'm rooting for the cache solution.

Quoted 16 lines

With
that in mind, and the understanding that this patch is an optimization and not a bug fix, I'm going to hold-off on doing anything with this patch until there is a cache option we can use for comparison.

As Stephen mentioned in the RH BZ (linked in the description), there are a couple of reasons why the code doesn't currently store the string translations. Ignoring the issue of aliasing for a moment, I do want to stress that I agree with Stephen on the issue of memory pressure and that to keep translated strings around indefinitely in the kernel is going to be a problem (there are other issues beyond just memory use). I imagine any cache implementation would need to be built to only store a subset of all the translations and there would need to be a way to age-out those translations (as well as purge them completely on events such as a policy load).

#3 lore raw
In reply to Ondrej Mosnacek
Quoted 50 lines · Ondrej Mosnacek

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

---
  security/selinux/ss/ebitmap.h | 46 +++++++++++++++++++++
  security/selinux/ss/mls.c     | 76 +++++++++++++----------------------
  2 files changed, 73 insertions(+), 49 deletions(-)
security/selinux/ss/ebitmap.h +12 -0
index 6aa7cf6a2197..a415741cb206 100644
@@ -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);

security/selinux/ss/ebitmap.h static inline unsigned int ebitmap_next_positive(struct ebitmap *e, · line 104

Quoted 10 lines
security/selinux/ss/ebitmap.h +10 -0
+	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);
+}

This is likely moot given that the patch was deferred on exploring the cache option, but if/when this patch is revisited, you don't seem to account for the possibility that there could be a hole between the bitmaps represented by (*n) and (*n)->next, and that might be where the next negative/zero bit is.

Quoted 156 lines
security/selinux/ss/ebitmap.h +24 -0
+
+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);
security/selinux/ss/mls.c +27 -49
index 5e05f5b902d7..3abd6b950c66 100644
@@ -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]))
#4 lore raw
Quoted 53 lines · Stephen Smalley
Quoted 52 lines · Ondrej Mosnacek

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

---
  security/selinux/ss/ebitmap.h | 46 +++++++++++++++++++++ security/selinux/ss/mls.c     | 76 +++++++++++++----------------------

  2 files changed, 73 insertions(+), 49 deletions(-)
security/selinux/ss/ebitmap.h +0 -0
index 6aa7cf6a2197..a415741cb206 100644
@@ -42,6 +42,10 @@ struct ebitmap {

      u32 highbit;    /* highest position in the total bitmap */ };

security/selinux/ss/ebitmap.h +4 -0
+struct ebitmap_range {
+    unsigned int start, end;
+};
+

  #define ebitmap_length(e) ((e)->highbit)
  static inline unsigned int ebitmap_start_positive(struct ebitmap *e,

security/selinux/ss/ebitmap.h +12 -0
@@ -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) {
Quoted 8 lines

security/selinux/ss/ebitmap.h static inline unsigned int ebitmap_next_positive(struct ebitmap *e, · line 104

Quoted 6 lines
security/selinux/ss/ebitmap.h +6 -0
+        ofs = find_first_zero_bit((*n)->maps, EBITMAP_SIZE);
+        if (ofs < EBITMAP_SIZE)
+            return ofs + (*n)->startbit;
+    }
+    return ebitmap_length(e);
+}

This is likely moot given that the patch was deferred on exploring the cache option, but if/when this patch is revisited, you don't seem to account for the possibility that there could be a hole between the bitmaps represented by (*n) and (*n)->next, and that might be where the next negative/zero bit is.

You can see this bug manifest by doing the following:
runcon -l s0:c0.c383,c768 bash
id -Z

The correct output of course would be s0:c0.c383,c768, but your patched kernel will report s0:c0.c768.

Quoted 154 lines
Quoted 153 lines
security/selinux/ss/ebitmap.h +24 -0
+
+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);
security/selinux/ss/mls.c +27 -49
index 5e05f5b902d7..3abd6b950c66 100644
@@ -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]))
 
#5 lore raw
Quoted 68 lines · Stephen Smalley
Quoted 58 lines · Stephen Smalley
Quoted 57 lines · Ondrej Mosnacek

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

---
  security/selinux/ss/ebitmap.h | 46 +++++++++++++++++++++
  security/selinux/ss/mls.c     | 76 +++++++++++++----------------------
  2 files changed, 73 insertions(+), 49 deletions(-)
security/selinux/ss/ebitmap.h +20 -0
index 6aa7cf6a2197..a415741cb206 100644
@@ -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;
+    }
Quoted 8 lines

security/selinux/ss/ebitmap.h static inline unsigned int · line 104

Quoted 2 lines
security/selinux/ss/ebitmap.h +2 -0
+    return ebitmap_length(e);
+}

This is likely moot given that the patch was deferred on exploring the cache option, but if/when this patch is revisited, you don't seem to account for the possibility that there could be a hole between the bitmaps represented by (*n) and (*n)->next, and that might be where the next negative/zero bit is.

Quoted 6 lines

You can see this bug manifest by doing the following:
runcon -l s0:c0.c383,c768 bash
id -Z

The correct output of course would be s0:c0.c383,c768, but your patched kernel will report s0:c0.c768.

Yes, good catch! This patch would really need some focused testing (and fixing) before being committed... Some simple fuzz test over /sys/fs/selinux/context should be enough, but I didn't get as far as to write it. Probably should have initially sent the patch just as RFC, though...

Quoted 149 lines
Quoted 149 lines
Quoted 149 lines
security/selinux/ss/ebitmap.h +24 -0
+
+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);

security/selinux/ss/mls.c +24 -49
index 5e05f5b902d7..3abd6b950c66 100644
@@ -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);
Quoted 9 lines
Quoted 8 lines

security/selinux/ss/mls.c void mls_sid_to_context(struct policydb *p,

Quoted 7 lines
security/selinux/ss/mls.c +3 -0
+                scontextp += strlen(nm);
+            }
+        }
          if (l == 0) {
              if (mls_level_eq(&context->range.level[0],
                       &context->range.level[1]))
 

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