linux.git/lib/math, branch v6.18.21

lib/math/gcd: use static key to select implementation at runtime

2025-07-20T02:08:28+00:00

Patch series "Optimize GCD performance on RISC-V by selecting
implementation at runtime", v3.

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.


This patch (of 3):

On platforms like RISC-V, the compiler may generate hardware FFS
instructions even if the underlying CPU does not actually support them. 
Currently, the GCD implementation is chosen at compile time based on
CONFIG_CPU_NO_EFFICIENT_FFS, which can result in suboptimal behavior on
such systems.

Introduce a static key, efficient_ffs_key, to enable runtime selection
between the binary GCD (using ffs) and the odd-even GCD implementation. 
This allows the kernel to default to the faster binary GCD when FFS is
efficient, while retaining the ability to fall back when needed.

Link: https://lkml.kernel.org/r/20250606134758.1308400-1-visitorckw@gmail.com
Link: https://lkml.kernel.org/r/20250606134758.1308400-2-visitorckw@gmail.com
Co-developed-by: Yu-Chun Lin 
Signed-off-by: Yu-Chun Lin 
Signed-off-by: Kuan-Wei Chiu 
Cc: Albert Ou 
Cc: Ching-Chun (Jim) Huang 
Cc: Palmer Dabbelt 
Cc: Paul Walmsley 
Cc: Alexandre Ghiti 
Signed-off-by: Andrew Morton

mul_u64_u64_div_u64: fix the division-by-zero behavior

2025-07-10T05:57:53+00:00

The current implementation forces a compile-time 1/0 division, which
generates an undefined instruction (ud2 on x86) rather than a proper
runtime division-by-zero exception.

Change to trigger an actual div-by-0 exception at runtime, consistent with
other division operations.  Use a non-1 dividend to prevent the compiler
from optimizing the division into a comparison.

Link: https://lkml.kernel.org/r/q246p466-1453-qon9-29so-37105116009q@onlyvoer.pbz
Signed-off-by: Nicolas Pitre 
Cc: Biju Das 
Cc: Oleg Nesterov 
Cc: Peter Zijlstra 
Cc: Thomas Weißschuh 
Cc: Uwe Kleine-König 
Cc: David Laight 
Signed-off-by: Andrew Morton

lib/prime_numbers: convert self-test to KUnit

2025-02-12T22:00:11+00:00

Extract a private header and convert the prime_numbers self-test to a
KUnit test. I considered parameterizing the test using
`KUNIT_CASE_PARAM` but didn't see how it was possible since the test
logic is entangled with the test parameter generation logic.

Signed-off-by: Tamir Duberstein 
Link: https://lore.kernel.org/r/20250208-prime_numbers-kunit-convert-v5-2-b0cb82ae7c7d@gmail.com
Signed-off-by: Kees Cook

lib/math: Add Kunit test suite for gcd()

2025-02-12T22:00:11+00:00

Add a KUnit test suite for the gcd() function.
This test suite verifies the correctness of gcd() across various
scenarios, including edge cases.

Signed-off-by: Yu-Chun Lin 
Reviewed-by: Kuan-Wei Chiu 
Link: https://lore.kernel.org/r/20250203075400.3431330-1-eleanor15x@gmail.com
Signed-off-by: Kees Cook

lib/math: Add int_log test suite

2025-02-11T02:25:37+00:00

This commit introduces KUnit tests for the intlog2 and intlog10
functions, which compute logarithms in base 2 and base 10, respectively.
The tests cover a range of inputs to ensure the correctness of these
functions across common and edge cases.

Signed-off-by: Bruno Sobreira França 
Reviewed-by: David Gow 
Reviewed-by: Rae Moar 
Link: https://lore.kernel.org/r/20241202075545.3648096-3-davidgow@google.com
Signed-off-by: Kees Cook

lib: math: Move KUnit tests into tests/ subdir

2025-02-11T02:24:57+00:00

This patch is a follow-up task from a discussion stemming from point 3
in a recent patch introducing the int_pow kunit test [1] and
documentation regarding kunit test style and nomenclature [2].

Colocate all kunit test suites in lib/math/tests/ and
follow recommended naming convention for files _kunit.c
and kconfig entries CONFIG__KUNIT_TEST.

Link: https://lore.kernel.org/all/CABVgOS=-vh5TqHFCq_jo=ffq8v_nGgr6JsPnOZag3e6+19ysxQ@mail.gmail.com/ [1]
Link: https://docs.kernel.org/dev-tools/kunit/style.html [2]

Signed-off-by: Luis Felipe Hernandez 
Acked-by: Nicolas Pitre 
Reviewed-by: David Gow 
Reviewed-by: Rae Moar 
Link: https://lore.kernel.org/r/20241202075545.3648096-2-davidgow@google.com
Signed-off-by: Kees Cook

lib/math: add int_sqrt test suite

2025-01-13T04:21:08+00:00

Adds test suite for integer based square root function.

The test suite is designed to verify the correctness of the int_sqrt()
math library function.

Link: https://lkml.kernel.org/r/20241213042701.1037467-1-luis.hernandez093@gmail.com
Signed-off-by: Luis Felipe Hernandez 
Reviewed-by: Kuan-Wei Chiu 
Cc: David Gow 
Cc: Ricardo B. Marliere 
Cc: Shuah Khan 
Signed-off-by: Andrew Morton

lib/math/test_div64: add some edge cases relevant to __div64_const32()

2024-10-28T21:44:28+00:00

Be sure to test the extreme cases with and without bias.

Signed-off-by: Nicolas Pitre 
Signed-off-by: Arnd Bergmann

Merge tag 'mm-nonmm-stable-2024-09-21-07-52' of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

2024-09-21T15:20:50+00:00

Pull non-MM updates from Andrew Morton:
"Many singleton patches - please see the various changelogs for
details.

Quite a lot of nilfs2 work this time around.

Notable patch series in this pull request are:

- "mul_u64_u64_div_u64: new implementation" by Nicolas Pitre, with
assistance from Uwe Kleine-König. Reimplement mul_u64_u64_div_u64()
to provide (much) more accurate results. The current implementation
was causing Uwe some issues in the PWM drivers.

- "xz: Updates to license, filters, and compression options" from
Lasse Collin. Miscellaneous maintenance and kinor feature work to
the xz decompressor.

- "Fix some GDB command error and add some GDB commands" from
Kuan-Ying Lee. Fixes and enhancements to the gdb scripts.

- "treewide: add missing MODULE_DESCRIPTION() macros" from Jeff
Johnson. Adds lots of MODULE_DESCRIPTIONs, thus fixing lots of
warnings about this.

- "nilfs2: add support for some common ioctls" from Ryusuke Konishi.
Adds various commonly-available ioctls to nilfs2.

- "This series fixes a number of formatting issues in kernel doc
comments" from Ryusuke Konishi does that.

- "nilfs2: prevent unexpected ENOENT propagation" from Ryusuke
Konishi. Fix issues where -ENOENT was being unintentionally and
inappropriately returned to userspace.

- "nilfs2: assorted cleanups" from Huang Xiaojia.

- "nilfs2: fix potential issues with empty b-tree nodes" from Ryusuke
Konishi fixes some issues which can occur on corrupted nilfs2
filesystems.

- "scripts/decode_stacktrace.sh: improve error reporting and
usability" from Luca Ceresoli does those things"

* tag 'mm-nonmm-stable-2024-09-21-07-52' of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm: (103 commits)
list: test: increase coverage of list_test_list_replace*()
list: test: fix tests for list_cut_position()
proc: use __auto_type more
treewide: correct the typo 'retun'
ocfs2: cleanup return value and mlog in ocfs2_global_read_info()
nilfs2: remove duplicate 'unlikely()' usage
nilfs2: fix potential oob read in nilfs_btree_check_delete()
nilfs2: determine empty node blocks as corrupted
nilfs2: fix potential null-ptr-deref in nilfs_btree_insert()
user_namespace: use kmemdup_array() instead of kmemdup() for multiple allocation
tools/mm: rm thp_swap_allocator_test when make clean
squashfs: fix percpu address space issues in decompressor_multi_percpu.c
lib: glob.c: added null check for character class
nilfs2: refactor nilfs_segctor_thread()
nilfs2: use kthread_create and kthread_stop for the log writer thread
nilfs2: remove sc_timer_task
nilfs2: do not repair reserved inode bitmap in nilfs_new_inode()
nilfs2: eliminate the shared counter and spinlock for i_generation
nilfs2: separate inode type information from i_state field
nilfs2: use the BITS_PER_LONG macro
...

lib/math: Add int_pow test suite

2024-09-12T16:03:00+00:00

Adds test suite for integer based power function which performs integer
exponentiation.

The test suite is designed to verify that the implementation of int_pow
correctly computes the power of a given base raised to a given exponent.

The tests check various scenarios and edge cases to ensure the accuracy
and reliability of the exponentiation function.

Updated commit with test information at commit time: Shuah Khan

Signed-off-by: Luis Felipe Hernandez 
Reviewed-by: David Gow 
Signed-off-by: Shuah Khan