* [PATCH] selinux: optimize MLS context to string conversion
@ 2019-07-30 12:48 Ondrej Mosnacek
2019-07-30 14:46 ` Paul Moore
2019-09-16 14:43 ` Stephen Smalley
0 siblings, 2 replies; 6+ messages in thread
From: Ondrej Mosnacek @ 2019-07-30 12:48 UTC (permalink / raw)
To: selinux, Paul Moore; +Cc: Stephen Smalley, Michal Sekletar
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@redhat.com>
Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
---
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]))
--
2.21.0
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH] selinux: optimize MLS context to string conversion
2019-07-30 12:48 [PATCH] selinux: optimize MLS context to string conversion Ondrej Mosnacek
@ 2019-07-30 14:46 ` Paul Moore
2019-07-30 16:35 ` Casey Schaufler
2019-09-16 14:43 ` Stephen Smalley
1 sibling, 1 reply; 6+ messages in thread
From: Paul Moore @ 2019-07-30 14:46 UTC (permalink / raw)
To: Ondrej Mosnacek; +Cc: selinux, Stephen Smalley, Michal Sekletar
On Tue, Jul 30, 2019 at 8:48 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> 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@redhat.com>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
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).
--
paul moore
www.paul-moore.com
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] selinux: optimize MLS context to string conversion
2019-07-30 14:46 ` Paul Moore
@ 2019-07-30 16:35 ` Casey Schaufler
0 siblings, 0 replies; 6+ messages in thread
From: Casey Schaufler @ 2019-07-30 16:35 UTC (permalink / raw)
To: Paul Moore, Ondrej Mosnacek
Cc: selinux, Stephen Smalley, Michal Sekletar, casey
On 7/30/2019 7:46 AM, Paul Moore wrote:
> On Tue, Jul 30, 2019 at 8:48 AM Ondrej Mosnacek <omosnace@redhat.com> wrote:
>> 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@redhat.com>
>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> 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.
> 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).
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] selinux: optimize MLS context to string conversion
2019-07-30 12:48 [PATCH] selinux: optimize MLS context to string conversion Ondrej Mosnacek
2019-07-30 14:46 ` Paul Moore
@ 2019-09-16 14:43 ` Stephen Smalley
2019-09-16 17:30 ` Stephen Smalley
1 sibling, 1 reply; 6+ messages in thread
From: Stephen Smalley @ 2019-09-16 14:43 UTC (permalink / raw)
To: Ondrej Mosnacek, selinux, Paul Moore; +Cc: Michal Sekletar
On 7/30/19 8:48 AM, Ondrej Mosnacek wrote:
> 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@redhat.com>
> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> ---
> 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);
> +}
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.
> +
> +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]))
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] selinux: optimize MLS context to string conversion
2019-09-16 14:43 ` Stephen Smalley
@ 2019-09-16 17:30 ` Stephen Smalley
2019-09-17 10:23 ` Ondrej Mosnacek
0 siblings, 1 reply; 6+ messages in thread
From: Stephen Smalley @ 2019-09-16 17:30 UTC (permalink / raw)
To: Ondrej Mosnacek, selinux, Paul Moore; +Cc: Michal Sekletar
On 9/16/19 10:43 AM, Stephen Smalley wrote:
> On 7/30/19 8:48 AM, Ondrej Mosnacek wrote:
>> 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@redhat.com>
>> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
>> ---
>> 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);
>> +}
>
> 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.
>
>> +
>> +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]))
>>
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] selinux: optimize MLS context to string conversion
2019-09-16 17:30 ` Stephen Smalley
@ 2019-09-17 10:23 ` Ondrej Mosnacek
0 siblings, 0 replies; 6+ messages in thread
From: Ondrej Mosnacek @ 2019-09-17 10:23 UTC (permalink / raw)
To: Stephen Smalley; +Cc: SElinux list, Paul Moore, Michal Sekletar
On Mon, Sep 16, 2019 at 7:30 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> On 9/16/19 10:43 AM, Stephen Smalley wrote:
> > On 7/30/19 8:48 AM, Ondrej Mosnacek wrote:
> >> 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@redhat.com>
> >> Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> >> ---
> >> 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);
> >> +}
> >
> > 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.
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...
>
> >
> >> +
> >> +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]))
> >>
> >
>
--
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2019-09-17 10:23 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-07-30 12:48 [PATCH] selinux: optimize MLS context to string conversion Ondrej Mosnacek
2019-07-30 14:46 ` Paul Moore
2019-07-30 16:35 ` Casey Schaufler
2019-09-16 14:43 ` Stephen Smalley
2019-09-16 17:30 ` Stephen Smalley
2019-09-17 10:23 ` Ondrej Mosnacek
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).