linux-kernel - Re: [PATCH v5 next 7/9] lib: mul_u64_u64_div

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: <20251106092633.6058001e@pumpkin>
Date: Thu, 6 Nov 2025 09:26:33 +0000
From: David Laight <david.laight.linux@...il.com>
To: "H. Peter Anvin" <hpa@...or.com>
Cc: Andrew Morton <akpm@...ux-foundation.org>, linux-kernel@...r.kernel.org,
 u.kleine-koenig@...libre.com, Nicolas Pitre <npitre@...libre.com>, Oleg
 Nesterov <oleg@...hat.com>, Peter Zijlstra <peterz@...radead.org>, Biju Das
 <biju.das.jz@...renesas.com>, Borislav Petkov <bp@...en8.de>, Dave Hansen
 <dave.hansen@...ux.intel.com>, Ingo Molnar <mingo@...hat.com>, Thomas
 Gleixner <tglx@...utronix.de>, Li RongQing <lirongqing@...du.com>,
 Khazhismel Kumykov <khazhy@...omium.org>, Jens Axboe <axboe@...nel.dk>,
 x86@...nel.org
Subject: Re: [PATCH v5 next 7/9] lib: mul_u64_u64_div_u64() optimise
 multiply on 32bit x86

On Wed, 05 Nov 2025 15:45:29 -0800
"H. Peter Anvin" <hpa@...or.com> wrote:

> On November 5, 2025 12:10:33 PM PST, David Laight <david.laight.linux@...il.com> wrote:
> >gcc generates horrid code for both ((u64)u32_a * u32_b) and (u64_a + u32_b).
> >As well as the extra instructions it can generate a lot of spills to stack
> >(including spills of constant zeros and even multiplies by constant zero).
> >
> >mul_u32_u32() already exists to optimise the multiply.
> >Add a similar add_u64_32() for the addition.
> >Disable both for clang - it generates better code without them.
> >
> >Move the 64x64 => 128 multiply into a static inline helper function
> >for code clarity.
> >No need for the a/b_hi/lo variables, the implicit casts on the function
> >calls do the work for us.
> >Should have minimal effect on the generated code.
> >
> >Use mul_u32_u32() and add_u64_u32() in the 64x64 => 128 multiply
> >in mul_u64_add_u64_div_u64().
> >
> >Signed-off-by: David Laight <david.laight.linux@...il.com>
> >Reviewed-by: Nicolas Pitre <npitre@...libre.com>
> >---
> >
> >Changes for v4:
> >- merge in patch 8.
> >- Add comments about gcc being 'broken' for mixed 32/64 bit maths.
> >  clang doesn't have the same issues.
> >- Use a #define for define mul_add() to avoid 'defined but not used'
> >  errors.
> >
> > arch/x86/include/asm/div64.h | 19 +++++++++++++++++
> > include/linux/math64.h       | 11 ++++++++++
> > lib/math/div64.c             | 40 +++++++++++++++++++++++-------------
> > 3 files changed, 56 insertions(+), 14 deletions(-)
> >
> >diff --git a/arch/x86/include/asm/div64.h b/arch/x86/include/asm/div64.h
> >index 6d8a3de3f43a..30fd06ede751 100644
> >--- a/arch/x86/include/asm/div64.h
> >+++ b/arch/x86/include/asm/div64.h
> >@@ -60,6 +60,12 @@ static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)
> > }
> > #define div_u64_rem	div_u64_rem
> > 
> >+/*
> >+ * gcc tends to zero extend 32bit values and do full 64bit maths.
> >+ * Define asm functions that avoid this.
> >+ * (clang generates better code for the C versions.)
> >+ */
> >+#ifndef __clang__
> > static inline u64 mul_u32_u32(u32 a, u32 b)
> > {
> > 	u32 high, low;
> >@@ -71,6 +77,19 @@ static inline u64 mul_u32_u32(u32 a, u32 b)
> > }
> > #define mul_u32_u32 mul_u32_u32
> > 
> >+static inline u64 add_u64_u32(u64 a, u32 b)
> >+{
> >+	u32 high = a >> 32, low = a;
> >+
> >+	asm ("addl %[b], %[low]; adcl $0, %[high]"
> >+		: [low] "+r" (low), [high] "+r" (high)
> >+		: [b] "rm" (b) );
> >+
> >+	return low | (u64)high << 32;
> >+}
> >+#define add_u64_u32 add_u64_u32
> >+#endif
...
> 
> By the way have you filed gcc bug reports for this?

As in the need for the asm() above?
No...
I doubt one was filed when the mul version was added either.
ISTR that some very recent gcc versions were a bit better, but it depends
on minor code changes and compiler options.

I suspect that internally gcc sometimes keeps a 64bit value as two 32bit
ones, but at other times it is assigned to a 64bit internal register.
If the latter happens it always promotes a 32bit value to 64 bits and
assigns to another 64bit register.
At that point it won't split the 64bit registers - so a lot of spills to
stack happen when it tries to assign real registers.
So breath on an 'A' (dx:ax) constraint and the generated code is horrid.

Even the lo | (u64)hi << 32 can generate 'or' instructions.

The same happens for int128 on 64bit.

	David