linux-kernel - Re: [PATCH v3 0/3] Optimize GCD performance on RISC-V by selecting implementation at runtime

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: <203fba2f-24c0-45bd-aeac-c907297f9a6e@ghiti.fr>
Date: Wed, 9 Jul 2025 17:08:31 +0200
From: Alexandre Ghiti <alex@...ti.fr>
To: Kuan-Wei Chiu <visitorckw@...il.com>, paul.walmsley@...ive.com,
 palmer@...belt.com, aou@...s.berkeley.edu, akpm@...ux-foundation.org
Cc: linux-riscv@...ts.infradead.org, linux-kernel@...r.kernel.org,
 jserv@...s.ncku.edu.tw, Yu-Chun Lin <eleanor15x@...il.com>
Subject: Re: [PATCH v3 0/3] Optimize GCD performance on RISC-V by selecting
 implementation at runtime

Hi Kuan-Wei, Andrew,

@Andrew: Will you merge this one? I can do it through the riscv tree if 
not, no problem at all.

Thanks,

Alex

On 6/6/25 15:47, Kuan-Wei Chiu wrote:
> The current implementation of gcd() selects between the binary GCD and
> the odd-even GCD algorithm at compile time, depending on whether
> CONFIG_CPU_NO_EFFICIENT_FFS is set. On platforms like RISC-V, however,
> this compile-time decision can be misleading: even when the compiler
> emits ctz instructions based on the assumption that they are efficient
> (as is the case when CONFIG_RISCV_ISA_ZBB is enabled), the actual
> hardware may lack support for the Zbb extension. In such cases, ffs()
> falls back to a software implementation at runtime, making the binary
> GCD algorithm significantly slower than the odd-even variant.
>
> To address this, we introduce a static key to allow runtime selection
> between the binary and odd-even GCD implementations. On RISC-V, the
> kernel now checks for Zbb support during boot. If Zbb is unavailable,
> the static key is disabled so that gcd() consistently uses the more
> efficient odd-even algorithm in that scenario. Additionally, to further
> reduce code size, we select CONFIG_CPU_NO_EFFICIENT_FFS automatically
> when CONFIG_RISCV_ISA_ZBB is not enabled, avoiding compilation of the
> unused binary GCD implementation entirely on systems where it would
> never be executed.
>
> This series ensures that the most efficient GCD algorithm is used in
> practice and avoids compiling unnecessary code based on hardware
> capabilities and kernel configuration.
>
> Co-developed-by: Yu-Chun Lin <eleanor15x@...il.com>
> Signed-off-by: Yu-Chun Lin <eleanor15x@...il.com>
> Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.com>
>
> ---
> This series has been tested on QEMU to verify that the correct GCD
> implementation is used both with and without Zbb support.
>
> v2 -> v3:
> - Drop if (!a || !b) check in binary_gcd()
> - Move DECLARE_STATIC_KEY_TRUE(efficient_ffs_key) to gcd.h
> v1 -> v2:
> - Use a static key to select the GCD implementation at runtime.
>
> v2: https://lore.kernel.org/lkml/20250524155519.1142570-1-visitorckw@gmail.com/
> v1: https://lore.kernel.org/lkml/20250217013708.1932496-1-visitorckw@gmail.com/
>
> Kuan-Wei Chiu (3):
>    lib/math/gcd: Use static key to select implementation at runtime
>    riscv: Optimize gcd() code size when CONFIG_RISCV_ISA_ZBB is disabled
>    riscv: Optimize gcd() performance on RISC-V without Zbb extension
>
>   arch/riscv/Kconfig        |  1 +
>   arch/riscv/kernel/setup.c |  5 +++++
>   include/linux/gcd.h       |  3 +++
>   lib/math/gcd.c            | 27 +++++++++++++++------------
>   4 files changed, 24 insertions(+), 12 deletions(-)
>