[PATCH] Bug with powerof2 macro in sys/param.h

[Garrett Cooper]

On Thu, Oct 14, 2010 at 6:37 AM, John Baldwin <jhb at freebsd.org> wrote:
> On Thursday, October 14, 2010 7:58:32 am Andriy Gapon wrote:
>> on 14/10/2010 00:30 Garrett Cooper said the following:
>> >     I was talking to someone today about this macro, and he noted that
>> > the algorithm is incorrect -- it fails the base case with ((x) == 0 --
>> > which makes sense because 2^(x) cannot equal 0 (mathematically
>> > impossible, unless you consider the limit as x goes to negative
>> > infinity as log (0) / log(2) is undefined). I tested out his claim and
>> > he was right:
>>
>> That's kind of obvious given the code.
>> I think that this might be an intentional optimization.
>> I guess that it doesn't really make sense to apply powerof2 to zero and the users
>> of the macro should do the check on their own if they expect zero as input (many
>> places in the do not allow that).

But the point is that this could be micro-optimizing things
incorrectly. I'm running simple iteration tests to see what the
performance is like, but the runtime is going to take a while to
produce stable results.

Mathematically there is a conflict with the definition of the macro,
so it might confuse folks who pay attention to the math as opposed to
the details (if you want I'll gladly add a comment around the macro in
a patch to note the caveats of using powerof2).

> I agree, the current macro is this way on purpose (and straight out of
> "Hacker's Delight").
>
> Of the existing calls you weren't sure of:
>
> sys/dev/cxgb/cxgb_sge.c:       while (!powerof2(fl_q_size))
> sys/dev/cxgb/cxgb_sge.c:       while (!powerof2(jumbo_q_size))
>
> These are fine, will not be zero.

Good to know.

> sys/x86/x86/local_apic.c:      KASSERT(powerof2(count), ("bad count"));
> sys/x86/x86/local_apic.c:      KASSERT(powerof2(align), ("bad align"));
>
> These are fine.  No code allocates zero IDT vectors.  We never allocate IDT
> vectors for unallocated MSI or MSI-X IRQs.

Excellent.

> sys/net/flowtable.c:           ft->ft_lock_count =
> 2*(powerof2(mp_maxid + 1) ? (mp_maxid + 1):
>
> Clearly, 'mp_maxid + 1' will not be zero (barring a bizarre overflow case
> which will not happen until we support 2^32 CPUs), so this is fine.

But that should be caught by the mp_machdep code, correct?

> sys/i386/pci/pci_pir.c:                if (error &&
> !powerof2(pci_link->pl_irqmask)) {
>
> This fine.  Earlier in the function if pl_irqmask is zero, then all of the
> pci_pir_choose_irq() calls will fail, so this is only invoked if pl_irqmask
> is non-zero.  In practice pl_irqmask is never zero anyway.

Ok.

> I suspect the GEOM ones are also generally safe.

Well, that is the overall feeling I was getting, but I'm not sure that
they're ok 100% of the time.

What about the other patches? The mfiutil and mptutil ones at least
get the two beforementioned tools in sync with sys/param.h at least,
so I see some degree of value in the patches (even if they're just
cleanup).

Thanks,
-Garrett