From: Stephen Smalley <sds@tycho.nsa.gov>
To: Ondrej Mosnacek <omosnace@redhat.com>,
selinux@vger.kernel.org, Paul Moore <paul@paul-moore.com>
Cc: Michal Sekletar <msekleta@redhat.com>
Subject: Re: [PATCH] selinux: optimize MLS context to string conversion
Date: Mon, 16 Sep 2019 13:30:26 -0400 [thread overview]
Message-ID: <e4390a08-4043-49bc-e792-c600d3183d5b@tycho.nsa.gov> (raw)
In-Reply-To: <2412f6e1-8f70-1ede-2776-79470083b912@tycho.nsa.gov>
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]))
>>
>
next prev parent reply other threads:[~2019-09-16 17:31 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
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 [this message]
2019-09-17 10:23 ` Ondrej Mosnacek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=e4390a08-4043-49bc-e792-c600d3183d5b@tycho.nsa.gov \
--to=sds@tycho.nsa.gov \
--cc=msekleta@redhat.com \
--cc=omosnace@redhat.com \
--cc=paul@paul-moore.com \
--cc=selinux@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).