| Message ID | 20230929195617.65120-3-jsatterfield.linux@gmail.com (mailing list archive) |
|---|---|
| State | Changes Requested |
| Delegated to: | Paul Moore |
| Headers | show |
| Series | selinux: avtab arrays and refactors | expand |
On Fri, Sep 29, 2023 at 3:56 PM Jacob Satterfield <jsatterfield.linux@gmail.com> 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@gmail.com> Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com>
On Sep 29, 2023 Jacob Satterfield <jsatterfield.linux@gmail.com> 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@gmail.com> > Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com> > --- > 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. > + 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. > - 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? > } > > @@ -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. > } > 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. > } > return NULL; > -- > 2.41.0 -- paul-moore.com
On Tue, Oct 3, 2023 at 5:07 PM Paul Moore <paul@paul-moore.com> wrote: > > On Sep 29, 2023 Jacob Satterfield <jsatterfield.linux@gmail.com> 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@gmail.com> > > Reviewed-by: Stephen Smalley <stephen.smalley.work@gmail.com> > > --- > > 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
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; + 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; - } - 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; } @@ -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; } 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; } return NULL;
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@gmail.com> --- security/selinux/ss/avtab.c | 101 +++++++++++++++--------------------- 1 file changed, 41 insertions(+), 60 deletions(-)