From owner-freebsd-hackers@FreeBSD.ORG Fri Oct 15 19:42:35 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id D28201065672; Fri, 15 Oct 2010 19:42:35 +0000 (UTC) (envelope-from yanegomi@gmail.com) Received: from mail-iw0-f182.google.com (mail-iw0-f182.google.com [209.85.214.182]) by mx1.freebsd.org (Postfix) with ESMTP id 869FA8FC12; Fri, 15 Oct 2010 19:42:34 +0000 (UTC) Received: by iwn6 with SMTP id 6so789679iwn.13 for ; Fri, 15 Oct 2010 12:42:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:sender:received :in-reply-to:references:date:x-google-sender-auth:message-id:subject :from:to:cc:content-type:content-transfer-encoding; bh=vJjNBEKxn2t7GDFyWceXL5C3DBcobi7HobDBsKKTSfs=; b=IZlryoTyEpVlH6KtqPUdPpi9LbsO1gl3jOYYOGQznlr4pW5oO7SJl+DauZiFtkOyML XlNSGhczAGOqB2vKs/IJzRXLQ4G+lBF5eHqdkZtIJfYVIxGueI6AHXilf4AaHr1XU/z9 R5VeA5x4ZCENYMa85jjqUw+zHVvMmc0gBH8Qo= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; b=qgNEXhf5S4YvLOsnDL77LKnYyp3nMQg7LOgyjnG4YMUvJeJaj7g8YUB6M1mB12N94R Um9SsY1EVmheaDZuck5tAuCU9JDva4NBQj1kgEBi4RNpvCaUHtM3mrSl1Zg0oc9yGzlI Tk5i7mvWFbOwrJc9LJaHP3N/riZBkbKUBV9Bw= MIME-Version: 1.0 Received: by 10.231.150.7 with SMTP id w7mr1152949ibv.14.1287171290536; Fri, 15 Oct 2010 12:34:50 -0700 (PDT) Sender: yanegomi@gmail.com Received: by 10.231.184.3 with HTTP; Fri, 15 Oct 2010 12:34:50 -0700 (PDT) In-Reply-To: <201010150851.14749.jhb@freebsd.org> References: <201010140937.51953.jhb@freebsd.org> <201010150851.14749.jhb@freebsd.org> Date: Fri, 15 Oct 2010 12:34:50 -0700 X-Google-Sender-Auth: YhDmGc3De91h5NwW4zKTYO8JtLM Message-ID: From: Garrett Cooper To: John Baldwin Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Cc: freebsd-hackers@freebsd.org, Andriy Gapon Subject: Re: [PATCH] Bug with powerof2 macro in sys/param.h X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 15 Oct 2010 19:42:35 -0000 On Fri, Oct 15, 2010 at 5:51 AM, John Baldwin wrote: > On Thursday, October 14, 2010 11:49:23 pm Garrett Cooper wrote: >> On Thu, Oct 14, 2010 at 6:37 AM, John Baldwin 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