linux-kernel - Re: [PATCH 02/17] bitops: Add generic parity calculation for u64

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] [day] [month] [year] [list]
Message-ID: <EF874FA4-2719-44EA-B0DB-93A0980142BE@zytor.com>
Date: Thu, 27 Feb 2025 17:50:55 -0800
From: "H. Peter Anvin" <hpa@...or.com>
To: David Laight <david.laight.linux@...il.com>,
        Yury Norov <yury.norov@...il.com>
CC: Kuan-Wei Chiu <visitorckw@...il.com>, tglx@...utronix.de, mingo@...hat.com,
        bp@...en8.de, dave.hansen@...ux.intel.com, x86@...nel.org,
        jk@...abs.org, joel@....id.au, eajames@...ux.ibm.com,
        andrzej.hajda@...el.com, neil.armstrong@...aro.org, rfoss@...nel.org,
        maarten.lankhorst@...ux.intel.com, mripard@...nel.org,
        tzimmermann@...e.de, airlied@...il.com, simona@...ll.ch,
        dmitry.torokhov@...il.com, mchehab@...nel.org, awalls@...metrocast.net,
        hverkuil@...all.nl, miquel.raynal@...tlin.com, richard@....at,
        vigneshr@...com, louis.peens@...igine.com, andrew+netdev@...n.ch,
        davem@...emloft.net, edumazet@...gle.com, pabeni@...hat.com,
        parthiban.veerasooran@...rochip.com, arend.vanspriel@...adcom.com,
        johannes@...solutions.net, gregkh@...uxfoundation.org,
        jirislaby@...nel.org, akpm@...ux-foundation.org, alistair@...ple.id.au,
        linux@...musvillemoes.dk, Laurent.pinchart@...asonboard.com,
        jonas@...boo.se, jernej.skrabec@...il.com, kuba@...nel.org,
        linux-kernel@...r.kernel.org, linux-fsi@...ts.ozlabs.org,
        dri-devel@...ts.freedesktop.org, linux-input@...r.kernel.org,
        linux-media@...r.kernel.org, linux-mtd@...ts.infradead.org,
        oss-drivers@...igine.com, netdev@...r.kernel.org,
        linux-wireless@...r.kernel.org, brcm80211@...ts.linux.dev,
        brcm80211-dev-list.pdl@...adcom.com, linux-serial@...r.kernel.org,
        bpf@...r.kernel.org, jserv@...s.ncku.edu.tw,
        Yu-Chun Lin <eleanor15x@...il.com>
Subject: Re: [PATCH 02/17] bitops: Add generic parity calculation for u64

On February 27, 2025 1:57:41 PM PST, David Laight <david.laight.linux@...il.com> wrote:
>On Thu, 27 Feb 2025 13:05:29 -0500
>Yury Norov <yury.norov@...il.com> wrote:
>
>> On Wed, Feb 26, 2025 at 10:29:11PM +0000, David Laight wrote:
>> > On Mon, 24 Feb 2025 14:27:03 -0500
>> > Yury Norov <yury.norov@...il.com> wrote:
>> > ....  
>> > > +#define parity(val)					\
>> > > +({							\
>> > > +	u64 __v = (val);				\
>> > > +	int __ret;					\
>> > > +	switch (BITS_PER_TYPE(val)) {			\
>> > > +	case 64:					\
>> > > +		__v ^= __v >> 32;			\
>> > > +		fallthrough;				\
>> > > +	case 32:					\
>> > > +		__v ^= __v >> 16;			\
>> > > +		fallthrough;				\
>> > > +	case 16:					\
>> > > +		__v ^= __v >> 8;			\
>> > > +		fallthrough;				\
>> > > +	case 8:						\
>> > > +		__v ^= __v >> 4;			\
>> > > +		__ret =  (0x6996 >> (__v & 0xf)) & 1;	\
>> > > +		break;					\
>> > > +	default:					\
>> > > +		BUILD_BUG();				\
>> > > +	}						\
>> > > +	__ret;						\
>> > > +})
>> > > +  
>> > 
>> > You really don't want to do that!
>> > gcc makes a right hash of it for x86 (32bit).
>> > See https://www.godbolt.org/z/jG8dv3cvs  
>> 
>> GCC fails to even understand this. Of course, the __v should be an
>> __auto_type. But that way GCC fails to understand that case 64 is
>> a dead code for all smaller type and throws a false-positive 
>> Wshift-count-overflow. This is a known issue, unfixed for 25 years!
>
>Just do __v ^= __v >> 16 >> 16
>
>> 
>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=4210
>>  
>> > You do better using a __v32 after the 64bit xor.  
>> 
>> It should be an __auto_type. I already mentioned. So because of that,
>> we can either do something like this:
>> 
>>   #define parity(val)					\
>>   ({							\
>>   #ifdef CLANG                                          \
>>   	__auto_type __v = (val);			\
>>   #else /* GCC; because of this and that */             \
>>   	u64 __v = (val);			        \
>>   #endif                                                \
>>   	int __ret;					\
>> 
>> Or simply disable Wshift-count-overflow for GCC.
>
>For 64bit values on 32bit it is probably better to do:
>int p32(unsigned long long x)
>{
>    unsigned int lo = x;
>    lo ^= x >> 32;
>    lo ^= lo >> 16;
>    lo ^= lo >> 8;
>    lo ^= lo >> 4;
>    return (0x6996 >> (lo & 0xf)) & 1;
>}
>That stops the compiler doing 64bit shifts (ok on x86, but probably not elsewhere).
>It is likely to be reasonably optimal for most 64bit cpu as well.
>(For x86-64 it probably removes a load of REX prefix.)
>(It adds an extra instruction to arm because if its barrel shifter.)
>
>
>> 
>> > Even the 64bit version is probably sub-optimal (both gcc and clang).
>> > The whole lot ends up being a bit single register dependency chain.
>> > You want to do:  
>> 
>> No, I don't. I want to have a sane compiler that does it for me.
>> 
>> > 	mov %eax, %edx
>> > 	shrl $n, %eax
>> > 	xor %edx, %eax
>> > so that the 'mov' and 'shrl' can happen in the same clock
>> > (without relying on the register-register move being optimised out).
>> > 
>> > I dropped in the arm64 for an example of where the magic shift of 6996
>> > just adds an extra instruction.  
>> 
>> It's still unclear to me that this parity thing is used in hot paths.
>> If that holds, it's unclear that your hand-made version is better than
>> what's generated by GCC.
>
>I wasn't seriously considering doing that optimisation.
>Perhaps just hoping is might make a compiler person think :-)
>
>	David
>
>> 
>> Do you have any perf test?
>> 
>> Thanks,
>> Yury
>

What the compiler people need to do is to not make __builtin_parity*() generate crap.