On Tue, Oct 3, 2023 at 5:07 PM Paul Moore <paul@xxxxxxxxxxxxxx> wrote:
>
> On Sep 29, 2023 Jacob Satterfield <jsatterfield.linux@xxxxxxxxx> wrote:
> >
> > In four separate functions within avtab, the same comparison logic is
> > used. The only difference is how the result is handled or whether there
> > is a unique specifier value to be checked for or used.
> >
> > Extracting this functionality into the avtab_node_cmp() function unifies
> > the comparison logic between searching and insertion and gets rid of
> > duplicative code so that the implementation is easier to maintain.
> >
> > Signed-off-by: Jacob Satterfield <jsatterfield.linux@xxxxxxxxx>
> > Reviewed-by: Stephen Smalley <stephen.smalley.work@xxxxxxxxx>
> > ---
> > security/selinux/ss/avtab.c | 101 +++++++++++++++---------------------
> > 1 file changed, 41 insertions(+), 60 deletions(-)
>
> Thanks for doing this. I've got a few small nits (below), but overall
> I think this is a nice improvement.
>
> > diff --git a/security/selinux/ss/avtab.c b/security/selinux/ss/avtab.c
> > index 8751a602ead2..1cd4fed30bf7 100644
> > --- a/security/selinux/ss/avtab.c
> > +++ b/security/selinux/ss/avtab.c
> > @@ -96,12 +96,34 @@ avtab_insert_node(struct avtab *h, struct avtab_node **dst,
> > return newnode;
> > }
> >
> > +static int avtab_node_cmp(const struct avtab_key *key1,
> > + const struct avtab_key *key2)
> > +{
> > + u16 specified = key1->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > +
> > + if (key1->source_type == key2->source_type &&
> > + key1->target_type == key2->target_type &&
> > + key1->target_class == key2->target_class &&
> > + (specified & key2->specified))
> > + return 0;
>
> Normally I'd be a nice guy and fix this up during the merge, but
> since I'd like a respin for other reasons I'm going to mention
> this so you can fix it yourself, and learn a bit for next time ;)
>
> Please don't needlessly indent multi-line if-conditionals. As an
> example, here is what I would have preferred to see for the above
> if-statement:
>
> if (key1->source_type == key2->source_type &&
> key1->target_type == key2->target_type &&
> key1->target_class == key2->target_class &&
> (specified & key2->specified))
> return 0;
>
> At some point in the future (hopefully soon, but my review backlog
> is daunting at the moment) we'll have some automated tools to help
> identify problems like this, but we're not there quite yet.
>
Fixed, my editor must have inserted them when I moved the code up.
I'll be more mindful in the future.
> > + if (key1->source_type < key2->source_type)
> > + return -1;
> > + if (key1->source_type == key2->source_type &&
> > + key1->target_type < key2->target_type)
> > + return -1;
> > + if (key1->source_type == key2->source_type &&
> > + key1->target_type == key2->target_type &&
> > + key1->target_class < key2->target_class)
> > + return -1;
> > + return 1;
> > +}
> > +
> > static int avtab_insert(struct avtab *h, const struct avtab_key *key,
> > const struct avtab_datum *datum)
> > {
> > u32 hvalue;
> > struct avtab_node *prev, *cur, *newnode;
> > - u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > + int cmp;
> >
> > if (!h || !h->nslot || h->nel == U32_MAX)
> > return -EINVAL;
> > @@ -110,23 +132,11 @@ static int avtab_insert(struct avtab *h, const struct avtab_key *key,
> > for (prev = NULL, cur = h->htable[hvalue];
> > cur;
> > prev = cur, cur = cur->next) {
> > - if (key->source_type == cur->key.source_type &&
> > - key->target_type == cur->key.target_type &&
> > - key->target_class == cur->key.target_class &&
> > - (specified & cur->key.specified)) {
> > - /* extended perms may not be unique */
> > - if (specified & AVTAB_XPERMS)
> > - break;
> > + cmp = avtab_node_cmp(key, &cur->key);
> > + /* extended perms may not be unique */
> > + if (unlikely(cmp == 0 && !(key->specified & AVTAB_XPERMS)))
> > return -EEXIST;
> > - }
>
> I'm generally not a big fan of the unlikely()/likely() macros unless
> it is a rather extreme case, please don't add one here.
>
Understood. I will not add them unless perf profiling shows a
significant branch-predictor improvement; and I'll tag it accordingly
in the commit message.
> > - if (key->source_type < cur->key.source_type)
> > - break;
> > - if (key->source_type == cur->key.source_type &&
> > - key->target_type < cur->key.target_type)
> > - break;
> > - if (key->source_type == cur->key.source_type &&
> > - key->target_type == cur->key.target_type &&
> > - key->target_class < cur->key.target_class)
> > + if (cmp <= 0)
> > break;
>
> I wonder if we should put the `cmp <= 0` (no match) check first since
> that will probably the more common case, right? Or am I thinking of
> this backwards?
>
In this function, we can't do the `<=` first because the `==` branch
is an invalid policy check. Only duplicate XPERMs are allowed, but if
the `<=` is moved first it would allow all duplicates.
> > }
> >
> > @@ -148,7 +158,7 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
> > {
> > u32 hvalue;
> > struct avtab_node *prev, *cur;
> > - u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > + int cmp;
> >
> > if (!h || !h->nslot || h->nel == U32_MAX)
> > return NULL;
> > @@ -156,19 +166,8 @@ struct avtab_node *avtab_insert_nonunique(struct avtab *h,
> > for (prev = NULL, cur = h->htable[hvalue];
> > cur;
> > prev = cur, cur = cur->next) {
> > - if (key->source_type == cur->key.source_type &&
> > - key->target_type == cur->key.target_type &&
> > - key->target_class == cur->key.target_class &&
> > - (specified & cur->key.specified))
> > - break;
> > - if (key->source_type < cur->key.source_type)
> > - break;
> > - if (key->source_type == cur->key.source_type &&
> > - key->target_type < cur->key.target_type)
> > - break;
> > - if (key->source_type == cur->key.source_type &&
> > - key->target_type == cur->key.target_type &&
> > - key->target_class < cur->key.target_class)
> > + cmp = avtab_node_cmp(key, &cur->key);
> > + if (cmp <= 0)
> > break;
> > }
> > return avtab_insert_node(h, prev ? &prev->next : &h->htable[hvalue],
> > @@ -183,7 +182,7 @@ struct avtab_node *avtab_search_node(struct avtab *h,
> > {
> > u32 hvalue;
> > struct avtab_node *cur;
> > - u16 specified = key->specified & ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > + int cmp;
> >
> > if (!h || !h->nslot)
> > return NULL;
> > @@ -191,20 +190,10 @@ struct avtab_node *avtab_search_node(struct avtab *h,
> > hvalue = avtab_hash(key, h->mask);
> > for (cur = h->htable[hvalue]; cur;
> > cur = cur->next) {
> > - if (key->source_type == cur->key.source_type &&
> > - key->target_type == cur->key.target_type &&
> > - key->target_class == cur->key.target_class &&
> > - (specified & cur->key.specified))
> > + cmp = avtab_node_cmp(key, &cur->key);
> > + if (cmp == 0)
> > return cur;
> > -
> > - if (key->source_type < cur->key.source_type)
> > - break;
> > - if (key->source_type == cur->key.source_type &&
> > - key->target_type < cur->key.target_type)
> > - break;
> > - if (key->source_type == cur->key.source_type &&
> > - key->target_type == cur->key.target_type &&
> > - key->target_class < cur->key.target_class)
> > + if (cmp < 0)
> > break;
>
> See the ordering comment/question above in avtab_insert(). I'm
> reasonably confident in the search case there will be more misses
> than hits.
>
I'll admit that I'm not well versed in all of the ways that SELinux is
exercised, but my intuition of the call patterns of this particular
function leads me to believe that the performance trade-off depends on
which mode will be used.
Under permissive mode, a long-running process (like a database or
webserver) could cause an indeterminate number of searches which don't
have entries in the avtab causing misses to be more prevalent. Under
enforcing mode, the same process would only search up to the first
missing entry before being denied, making hits the default case.
I did not consider a change to the original ordering since I had
assumed this trade-off had already been considered. The current
ordering suggests that enforcing would be preferred. However, given
that this portion of code has not been touched since it was mainlined,
do we see one mode preferred over the other and should that preference
be catered to? Should it be a compile time option? And how substantial
is the performance difference under the policies of different
distributions?
> > }
> > return NULL;
> > @@ -213,27 +202,19 @@ struct avtab_node *avtab_search_node(struct avtab *h,
> > struct avtab_node*
> > avtab_search_node_next(struct avtab_node *node, u16 specified)
> > {
> > + struct avtab_key tmp_key;
> > struct avtab_node *cur;
> > + int cmp;
> >
> > if (!node)
> > return NULL;
> > -
> > - specified &= ~(AVTAB_ENABLED|AVTAB_ENABLED_OLD);
> > + tmp_key = node->key;
> > + tmp_key.specified = specified;
> > for (cur = node->next; cur; cur = cur->next) {
> > - if (node->key.source_type == cur->key.source_type &&
> > - node->key.target_type == cur->key.target_type &&
> > - node->key.target_class == cur->key.target_class &&
> > - (specified & cur->key.specified))
> > + cmp = avtab_node_cmp(&tmp_key, &cur->key);
> > + if (cmp == 0)
> > return cur;
> > -
> > - if (node->key.source_type < cur->key.source_type)
> > - break;
> > - if (node->key.source_type == cur->key.source_type &&
> > - node->key.target_type < cur->key.target_type)
> > - break;
> > - if (node->key.source_type == cur->key.source_type &&
> > - node->key.target_type == cur->key.target_type &&
> > - node->key.target_class < cur->key.target_class)
> > + if (cmp < 0)
> > break;
>
> Another ordering spot.
>
My comments above apply to here as well.
> > }
> > return NULL;
> > --
> > 2.41.0
>
> --
> paul-moore.com
Thanks for the review!
-Jacob
