On Thu, Apr 1, 2021 at 1:20 AM Paul Moore <paul@xxxxxxxxxxxxxx> wrote:
> On Wed, Mar 31, 2021 at 5:12 AM Ondrej Mosnacek <omosnace@xxxxxxxxxx> wrote:
> > On Wed, Mar 31, 2021 at 4:04 AM Paul Moore <paul@xxxxxxxxxxxxxx> wrote:
> > > On Tue, Mar 30, 2021 at 9:16 AM Ondrej Mosnacek <omosnace@xxxxxxxxxx> wrote:
>
> ...
>
> > > > -int avtab_duplicate(struct avtab *new, struct avtab *orig)
> > > > +int avtab_alloc(struct avtab *h, u32 nrules)
> > > > {
> > > > - int i;
> > > > - struct avtab_node *node, *tmp, *tail;
> > > > -
> > > > - memset(new, 0, sizeof(*new));
> > > > + int rc;
> > > > + u32 shift = 0;
> > > > + u32 work = nrules;
> > > > + u32 nslot = 0;
> > > >
> > > > - new->htable = kvcalloc(orig->nslot, sizeof(void *), GFP_KERNEL);
> > > > - if (!new->htable)
> > > > - return -ENOMEM;
> > > > - new->nslot = orig->nslot;
> > > > - new->mask = orig->mask;
> > > > -
> > > > - for (i = 0; i < orig->nslot; i++) {
> > > > - tail = NULL;
> > > > - for (node = orig->htable[i]; node; node = node->next) {
> > > > - tmp = kmem_cache_zalloc(avtab_node_cachep, GFP_KERNEL);
> > > > - if (!tmp)
> > > > - goto error;
> > > > - tmp->key = node->key;
> > > > - if (tmp->key.specified & AVTAB_XPERMS) {
> > > > - tmp->datum.u.xperms =
> > > > - kmem_cache_zalloc(avtab_xperms_cachep,
> > > > - GFP_KERNEL);
> > > > - if (!tmp->datum.u.xperms) {
> > > > - kmem_cache_free(avtab_node_cachep, tmp);
> > > > - goto error;
> > > > - }
> > > > - tmp->datum.u.xperms = node->datum.u.xperms;
> > > > - } else
> > > > - tmp->datum.u.data = node->datum.u.data;
> > > > -
> > > > - if (tail)
> > > > - tail->next = tmp;
> > > > - else
> > > > - new->htable[i] = tmp;
> > > > -
> > > > - tail = tmp;
> > > > - new->nel++;
> > > > + if (nrules != 0) {
> > > > + while (work) {
> > > > + work = work >> 1;
> > >
> > > Extra horizontal spaces are awkward and bad.
> > >
> > > > + shift++;
> > > > }
> > > > + if (shift > 2)
> > > > + shift = shift - 2;
> > >
> > > Since we are getting nit-picky with this code, why not make the
> > > loop/if a bit more elegant? How about something like below?
> > >
> > > u32 shift = 2;
> > > u32 work = nrules >> 4;
> > > while (work) {
> > > work >>= 1;
> > > shift++;
> > > }
> >
> > I think you meant:
> > u32 shift = 0;
> > u32 work = nrules >> 2;
> > while (work) {
> > work >>= 1;
> > shift++;
> > }
> >
> > ...which is equivalent to the current code and yes, I'll use that :)
>
> Well, no, not really, but that's okay as looking at it now we both got
> it wrong :)
>
> Basically I wanted to avoid the odd problem where the current code has
> a dip in the number of slots/buckets when nrules is equal to 4, 5, 6,
> or 7. While the code I proposed yesterday did that, it inflated the
> number of buckets beyond the current code; your suggestion had
> problems with low numbers resulting in zero buckets.
Aah, I wrongly parsed the "if (shift > 2) shift -= 2;" statement...
Yeah, I guess even the original intent was different than what the
code does.
Anyway, my code doesn't result in zero buckets, at worst in 1 bucket
(nslot = 1 << shift), which I think is reasonable given that the
intent of the code seems to be to simply squeeze the number of slots
down to approx. 1/4 the number of rules.
To make it a bit more concrete: your code allocates 4 buckets for
nrules 1..15; my code allocates 1 bucket for nrules 1..3, 2 buckets
for nrules 4..7, and 4 buckets for 8..15. Both our solutions are
equivalent to the old code at nrules >= 8.
So I'll argue that my proposed solution is actually slightly better
(and avoids adding a new magic number).
>
> I think what we really want is this:
>
> shift = 2;
> work = nrules >> 4;
> while (work) {
> work >>= 1;
> shift++;
> }
>
> ... it avoids any dips in the bucket count and it results in similar
> bucket counts as the existing code for larger numbers of rules.
But that's exactly the same as your original suggestion :D
--
Ondrej Mosnacek
Software Engineer, Linux Security - SELinux kernel
Red Hat, Inc.
