selinux: optimize MLS context to string conversion
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
@@ -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
Paul Moore
maintainerQuoted 14 lines · Ondrej Mosnacek
When
mls_compute_context_len()ormls_sid_to_context()encounters a context with large category ranges, it behaves suboptimally - it traverses each positive bit of the category bitmap, each time callingfind_next_bit()again.This has a large performance impact on UNIX datagram sockets with
SO_PASSSECset, 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
Reported-by Michal Sekletar <[email protected]>Signed-off-by Ondrej Mosnacek <[email protected]>
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
Quoted 15 lines · Paul Moore
Quoted 14 lines · Ondrej Mosnacek
When
mls_compute_context_len()ormls_sid_to_context()encounters a context with large category ranges, it behaves suboptimally - it traverses each positive bit of the category bitmap, each time callingfind_next_bit()again.This has a large performance impact on UNIX datagram sockets with
SO_PASSSECset, 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
Reported-by Michal Sekletar <[email protected]>Signed-off-by Ondrej Mosnacek <[email protected]>My current opinion is that this isn't the right way to solve the problem, a SELinux
sid->secctxcache 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).
Quoted 50 lines · Ondrej Mosnacek
When
mls_compute_context_len()ormls_sid_to_context()encounters a context with large category ranges, it behaves suboptimally - it traverses each positive bit of the category bitmap, each time callingfind_next_bit()again.This has a large performance impact on UNIX datagram sockets with
SO_PASSSECset, 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 <[email protected]>Signed-off-by Ondrej Mosnacek <[email protected]>--- 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@@ -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@@ -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 ]))
Quoted 53 lines · Stephen Smalley
Quoted 52 lines · Ondrej Mosnacek
When
mls_compute_context_len()ormls_sid_to_context()encounters a context with large category ranges, it behaves suboptimally - it traverses each positive bit of the category bitmap, each time callingfind_next_bit()again.This has a large performance impact on UNIX datagram sockets with
SO_PASSSECset, 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 <[email protected]>Signed-off-by Ondrej Mosnacek <[email protected]>---
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@@ -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(structebitmap_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@@ -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]))
Quoted 68 lines · Stephen Smalley
Quoted 58 lines · Stephen Smalley
Quoted 57 lines · Ondrej Mosnacek
When
mls_compute_context_len()ormls_sid_to_context()encounters a context with large category ranges, it behaves suboptimally - it traverses each positive bit of the category bitmap, each time callingfind_next_bit()again.This has a large performance impact on UNIX datagram sockets with
SO_PASSSECset, 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 <[email protected]>Signed-off-by Ondrej Mosnacek <[email protected]>--- 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@@ -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 -ZThe 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@@ -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.