linux-kernel - Re: [PATCH] bitops/32: Convert variable_ffs() and fls() zero-case handling to C

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAHk-=wh5DUS+nhfTxPEEbaB9dsFib39gWatrX4NoFq_MpdOzGw@mail.gmail.com>
Date: Mon, 28 Apr 2025 09:23:44 -0700
From: Linus Torvalds <torvalds@...ux-foundation.org>
To: Ingo Molnar <mingo@...nel.org>
Cc: Andrew Cooper <andrew.cooper3@...rix.com>, Arnd Bergmann <arnd@...db.de>, 
	Arnd Bergmann <arnd@...nel.org>, Thomas Gleixner <tglx@...utronix.de>, Ingo Molnar <mingo@...hat.com>, 
	Borislav Petkov <bp@...en8.de>, Dave Hansen <dave.hansen@...ux.intel.com>, x86@...nel.org, 
	"H. Peter Anvin" <hpa@...or.com>, Juergen Gross <jgross@...e.com>, 
	Boris Ostrovsky <boris.ostrovsky@...cle.com>, 
	Alexander Usyskin <alexander.usyskin@...el.com>, 
	Greg Kroah-Hartman <gregkh@...uxfoundation.org>, Mateusz Jończyk <mat.jonczyk@...pl>, 
	Mike Rapoport <rppt@...nel.org>, Ard Biesheuvel <ardb@...nel.org>, Peter Zijlstra <peterz@...radead.org>, 
	linux-kernel@...r.kernel.org, xen-devel@...ts.xenproject.org
Subject: Re: [PATCH] bitops/32: Convert variable_ffs() and fls() zero-case
 handling to C

On Mon, 28 Apr 2025 at 00:14, Ingo Molnar <mingo@...nel.org> wrote:
>
> And, just out of intellectual curiosity, I also tried to measure the
> code generation price of the +1 standards-quirk in the fls()/ffs()
> interface as well:
>
> ... and unless I messed up the patch, it seems to have a surprisingly
> low impact - maybe because the compiler can amortize its cost by
> adjusting all dependent code mostly at build time, so the +1 doesn't
> end up being generated most of the time?

No, I think one issue is that most users actually end up subtracting
one from the return value of 'ffs()', because the "bit #0 returns 1"
semantics of the standard ffs() function really is insane.

It's not just that it doesn't match sane hardware, it's also that it
doesn't match sane *users*. If bit #0 is set, people want '0', so they
typically subtract 1.

So when you stop adding one, you aren't actually removing code -
you're often adding it.

Just see how many hits you get from

    git grep '\<ffs(.*).*-.*1'

which is obviously not a very precise pattern, but just look at the
output and see just *how* common that "subtract one" thing is.

I really don't understand how anybody *ever* thought that the whole
"return one bigger" was a good idea for ffs().

Sure, I understand that zero is special and needs a special return
value, but returning a negative value would have been pretty simple
(or just do what our bitops finding functions do, which is to return
past the end, which is often convenient but does tend to make the
error condition check a bit more complex).

Anyway, the fact that so many users subtract one means that your "look
at the size of the binary" model doesn't work. You're counting both
the wins (when that addition doesn't happen) and the losses (when the
"subtract one in the user" happens).

So the "+1" doesn't cause much code generation - as long as it's done
by the compiler that can also undo it - but it's just a horrid user
interface.

But maybe people really were poisoned by the Pascal mindset. Or maybe
it was invented by some ancient Roman who hadn't heard of the concept
of zero. Who knows?

               Linus