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 for Android: free password hash cracker in your pocket

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

Message-ID: <aBClAy837xcLnVpp@gmail.com>
Date: Tue, 29 Apr 2025 12:08:03 +0200
From: Ingo Molnar <mingo@...nel.org>
To: Linus Torvalds <torvalds@...ux-foundation.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


* Linus Torvalds <torvalds@...ux-foundation.org> wrote:

> 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().

Yeah. No argument from me that it's a badly thought out interface - I 
was just surprised that it doesn't seem to impact performance as badly 
as I expected. I have to add that a lot of work went into absorbing the 
negative effects of the ffs()/fls() interfaces:

  starship:~/tip> git grep -Ee '__ffs\(|__fls\(' | wc -l
  1055

So it impacts code quality negatively, which is arguably the worse side 
effect.

> 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?

Hey, ancient Romans didn't even have the concept of *whitespaces* and 
punctuation to begin with:

    https://historyofinformation.com/images/Vergilius_Augusteus,_Georgica_121.jpg

Lazy stonemasons the lot of them.

Romans were the worst ever coders too I suspect. What have the Romans 
ever done for us??

	Ingo