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: <3A122140-5646-46D7-91A0-0A3E5B21C951@zytor.com>
Date: Tue, 29 Apr 2025 07:32:10 -0700
From: "H. Peter Anvin" <hpa@...or.com>
To: Ingo Molnar <mingo@...nel.org>,
        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,
        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 April 29, 2025 3:08:03 AM PDT, Ingo Molnar <mingo@...nel.org> wrote:
>
>* 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

Well, they did build the roads... 🤣

Roman numerals obviously were not a positional system, but at least in accounting they used N for zero (nulla.)

ROMANI•ITE•DOMVM