From: Ondrej Mosnacek <omosnace@redhat.com>
To: Stephen Smalley <sds@tycho.nsa.gov>
Cc: SElinux list <selinux@vger.kernel.org>,
Paul Moore <paul@paul-moore.com>,
Michal Sekletar <msekleta@redhat.com>
Subject: Re: [PATCH] selinux: optimize MLS context to string conversion
Date: Tue, 17 Sep 2019 12:23:44 +0200 [thread overview]
Message-ID: <CAFqZXNuEF9u7+HbeougzHjt294oMNF3YCbD+NqdXbf=x3g+hpQ@mail.gmail.com> (raw)
In-Reply-To: <e4390a08-4043-49bc-e792-c600d3183d5b@tycho.nsa.gov>
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.
prev parent reply other threads:[~2019-09-17 10:23 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
2019-09-17 10:23 ` Ondrej Mosnacek [this message]
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='CAFqZXNuEF9u7+HbeougzHjt294oMNF3YCbD+NqdXbf=x3g+hpQ@mail.gmail.com' \
--to=omosnace@redhat.com \
--cc=msekleta@redhat.com \
--cc=paul@paul-moore.com \
--cc=sds@tycho.nsa.gov \
--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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.