[PATCH] Bug with powerof2 macro in sys/param.h
John Baldwin
jhb at freebsd.org
Fri Oct 15 13:08:41 UTC 2010
On Thursday, October 14, 2010 11:49:23 pm Garrett Cooper wrote:
> 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).
We aren't dealing with mathematicians, but programmers.
> > I agree, the current macro is this way on purpose (and straight out of
> > "Hacker's Delight").
And this book trumps you on that case. Using the powerof2() macro as it
currently stands is a widely-used practice among folks who write
systems-level code. If you were writing a powerof2() function for a higher
level language where performance doesn't matter and bit twiddling isn't
common, then a super-safe variant of powerof2() might be appropriate.
However, this is C, and C programmers are expected to know how this stuff
works.
> > 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?
Yes, hence "bizarre". It is also way unrealistic and not worth excessive
pessimizations scattered throughout the tree.
> 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).
No, powerof2() should not change. It would most likely be a POLA violation
to change how it works given 1) it's historical behavior, and 2) it's
underlying idiom's common (and well-understood) use among the software
world.
--
John Baldwin
More information about the freebsd-hackers
mailing list