linux-kernel - Re: [PATCH v3 next 09/10] 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: <008r6n2s-0985-2507-5o66-67qs6nn199r6@syhkavp.arg>
Date: Wed, 18 Jun 2025 22:43:47 -0400 (EDT)
From: Nicolas Pitre <nico@...xnic.net>
To: David Laight <david.laight.linux@...il.com>
cc: Andrew Morton <akpm@...ux-foundation.org>, linux-kernel@...r.kernel.org, 
    u.kleine-koenig@...libre.com, Oleg Nesterov <oleg@...hat.com>, 
    Peter Zijlstra <peterz@...radead.org>, 
    Biju Das <biju.das.jz@...renesas.com>
Subject: Re: [PATCH v3 next 09/10] lib: mul_u64_u64_div_u64() Optimise the
 divide code

On Wed, 18 Jun 2025, David Laight wrote:

> On Wed, 18 Jun 2025 16:12:49 -0400 (EDT)
> Nicolas Pitre <nico@...xnic.net> wrote:
> 
> > On Wed, 18 Jun 2025, David Laight wrote:
> > 
> > > On Wed, 18 Jun 2025 11:39:20 -0400 (EDT)
> > > Nicolas Pitre <nico@...xnic.net> wrote:
> > >   
> > > > > > +		q_digit = n_long / d_msig;    
> > > > > 
> > > > > I think you want to do the divide right at the top - maybe even if the
> > > > > result isn't used!
> > > > > All the shifts then happen while the divide instruction is in progress
> > > > > (even without out-of-order execution).    
> > 
> > Well.... testing on my old Intel Core i7-4770R doesn't show a gain.
> > 
> > With your proposed patch as is: ~34ns per call
> > 
> > With my proposed changes: ~31ns per call
> > 
> > With my changes but leaving the divide at the top of the loop: ~32ns per call
> 
> Wonders what makes the difference...
> Is that random 64bit values (where you don't expect zero digits)
> or values where there are likely to be small divisors and/or zero digits?

Those are values from the test module. I just copied it into a user 
space program.

> On x86 you can use the PERF_COUNT_HW_CPU_CYCLES counter to get pretty accurate
> counts for a single call.
> The 'trick' is to use syscall(___NR_perf_event_open,...) and pc = mmap() to get
> the register number pc->index - 1.

I'm not acquainted enough with x86 to fully make sense of the above.
This is more your territory than mine.  ;-)

> > > Can you do accurate timings for arm64 or arm32?  
> > 
> > On a Broadcom BCM2712 (ARM Cortex-A76):
> > 
> > With your proposed patch as is: ~20 ns per call
> > 
> > With my proposed changes: ~19 ns per call
> > 
> > With my changes but leaving the divide at the top of the loop: ~19 ns per call
> 
> Pretty much no difference.
> Is that 64bit or 32bit (or the 16 bits per iteration on 64bit) ?

64bit executable with 32 bits per iteration.

> Have you timed the original code?

The "your proposed patch as is" is the original code per the first email 
in this thread.

> > Both CPUs have the same max CPU clock rate (2.4 GHz). These are obtained 
> > with clock_gettime(CLOCK_MONOTONIC) over 56000 calls. There is some 
> > noise in the results over multiple runs though but still.
> 
> That many loops definitely trains the branch predictor and ignores
> any effects of loading the I-cache.
> As Linus keeps saying, the kernel tends to be 'cold cache', code size
> matters.

My proposed changes shrink the code especially on 32-bit systems due to 
the pre-loop special cases removal.

> That also means that branches are 50% likely to be mis-predicted.

We can tag it as unlikely. In practice this isn't taken very often.

> (Although working out what cpu actually do is hard.)
> 
> > 
> > I could get cycle measurements on the RPi5 but that requires a kernel 
> > recompile.
> 
> Or a loadable module - shame there isn't a sysctl.

Not sure. I've not investigated how the RPi kernel is configured yet.
I suspect this is about granting user space direct access to PMU regs.


Nicolas