Date: Fri, 15 Oct 2010 12:34:50 -0700 From: Garrett Cooper <gcooper@FreeBSD.org> To: John Baldwin <jhb@freebsd.org> Cc: freebsd-hackers@freebsd.org, Andriy Gapon <avg@icyb.net.ua> Subject: Re: [PATCH] Bug with powerof2 macro in sys/param.h Message-ID: <AANLkTimniuCPb%2BWcAiqxCO65NLGuTgxcOSwmeWi=Voyv@mail.gmail.com> In-Reply-To: <201010150851.14749.jhb@freebsd.org> References: <AANLkTi=0PSp2KpFTAHTAoosRYdcewiVAxweH4=ivYTLt@mail.gmail.com> <201010140937.51953.jhb@freebsd.org> <AANLkTineQfE12Q4sh6QgKapJGJ-S7UHDfiwRasw5nQVG@mail.gmail.com> <201010150851.14749.jhb@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Fri, Oct 15, 2010 at 5:51 AM, John Baldwin <jhb@freebsd.org> wrote:
> On Thursday, October 14, 2010 11:49:23 pm Garrett Cooper wrote:
>> On Thu, Oct 14, 2010 at 6:37 AM, John Baldwin <jhb@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:
>> >> > =A0 =A0 I was talking to someone today about this macro, and he not=
ed that
>> >> > the algorithm is incorrect -- it fails the base case with ((x) =3D=
=3D 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 a=
nd 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. =A0Using the powerof2() macro as i=
t
> currently stands is a widely-used practice among folks who write
> systems-level code. =A0If you were writing a powerof2() function for a hi=
gher
> level language where performance doesn't matter and bit twiddling isn't
> common, then a super-safe variant of powerof2() might be appropriate.
Ok, excellent point.
> However, this is C, and C programmers are expected to know how this stuff
> works.
Yes, but compilers (when setup to optimize) should pick up on the
fact that this clause in the conditional [(x) !=3D 0] is in fact covered
by a number of these statements when bounding the input set of (x) to
values greater than 0 (all of the areas I identified that I understood
the context were bounded to at least positive integer value range), so
it would be optimized way as an effective unreachable case.
>> > sys/net/flowtable.c: =A0 =A0 =A0 =A0 =A0 ft->ft_lock_count =3D
>> > 2*(powerof2(mp_maxid + 1) ? (mp_maxid + 1):
>> >
>> > Clearly, 'mp_maxid + 1' will not be zero (barring a bizarre overflow c=
ase
>> > 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". =A0 It is also way unrealistic and not worth excess=
ive
> pessimizations scattered throughout the tree.
Agreed :).
>> 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. =A0It would most likely be a POLA viola=
tion
> 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.
Ok. Given that similar logic is also employed in some of the other
macros in sys/params.h, like roundup2, etc, and that logic is used
more pervasively than powerof2, I agree that it's best to leave things
be... otherwise the code would turn into a dyslexic mess `fixing' most
of these relatively benign issues.
Thanks Andriy, Colin, and John for the lookover and explanation :).
Cheers,
-Garrett
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?AANLkTimniuCPb%2BWcAiqxCO65NLGuTgxcOSwmeWi=Voyv>