On Thu, Apr 1, 2021 at 5:36 PM Paul Moore <paul@xxxxxxxxxxxxxx> wrote:
> On Thu, Apr 1, 2021 at 3:59 AM Ondrej Mosnacek <omosnace@xxxxxxxxxx> wrote:
> > 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.
>
> I think we all mis-interpreted that bit of code at some point. I
> seriously doubt that dip was what the original author intended :)
>
> > Anyway, my code doesn't result in zero buckets, at worst in 1 bucket
> > (nslot = 1 << shift) ...
>
> Sorry, yes, I mis-spoke (mis-typed?); I was talking about the
> shift/exponent value.
>
> > So I'll argue that my proposed solution is actually slightly better
> > (and avoids adding a new magic number).
>
> The magic number argument isn't really valid as both approaches use
> them to some degree. Creating a #define constant is overkill here,
> but I guess a short comment wouldn't be a bad idea if you wanted to
> add one; I'm not going to require it in this case.
>
> Since we are at -rc5 I really want to wrap this up soon so I'm going
> to make one final suggestion:
>
> shift = 1;
> work = nrules >> 3;
> while (work) {
> work >>= 1;
> shift++;
> }
>
> ... this preserves the original nslot count, minus the bump/dip seen
> with low rule numbers. The shift value starts at 1, increases to 2
> when the rules reach 8, increases to 3 when the rules reach 16, and so
> on. Of the approaches we've discussed, I believe it is the most
> faithful to original intent.
Ok, I agree it's not something worth obsessing over, so I'll just use
this last suggestion :) (One day maybe I'll try to simplify/optimize
it a bit, but that is for another patch...)
--
Ondrej Mosnacek
Software Engineer, Linux Security - SELinux kernel
Red Hat, Inc.
