lib: resync lib/div64.c and <linux/math64.h> with Linux v7.1
cover lib: resync lib/div64.c and <linux/math64.h> with Linux v7.1
U-Boot's <linux/math64.h> was last really synced with Linux in 2017 by commit 0342e335ba88 ("lib: div64: sync with Linux"). Since then it has only been patched locally twice, and both times in ways that increased the divergence rather than tracking upstream.
The one that prompted this series is DIV64_U64_ROUND_UP(). Commit 3adc17f60bf8 ("lib: div64: Add support for round up of div64_u64") added it inside the #if BITS_PER_LONG == 64 branch, whereas upstream defines it unconditionally after that block, so any 32-bit user fails to build.
While auditing the header, two bugs turned up in lib/div64.c, so this series starts with those. Both are 32-bit only:
- div64_u64() and div64_u64_rem() shifted by 1 + fls(high) instead of fls(high), losing a bit of the divisor. Linux fixed this in 2019, while U-Boot never picked it up.
- div64_s64() used abs() on s64 operands. U-Boot's abs() is not 64-bit
safe: its own comment says to use abs64() instead. Both operands were silently truncated to 32 bits.
Transitive headers that affect what <linux/math64.h> offers were checked too. <linux/math.h> and <vdso/math64.h> have no U-Boot equivalent and are not needed; do_div() comes from U-Boot's <div64.h> in place of <asm/div64.h>.
Deliberately left out of this resync:
- CONFIG_ARCH_SUPPORTS_INT128 is tested by <linux/math64.h> but isn't defined anywhere in U-Boot, so the __int128 fast paths for mul_u64_u32_shr() and mul_u64_u64_shr() are dead code on arm64, riscv64 and x86_64 where they could have been useful. Wiring it up in the arch Kconfigs looks like an easy win (but could result in subtle behavior changes or code size drift, so needs to be approached separately).
- abs() in <linux/kernel.h> diverges from Linux and is not 64-bit safe. Patch 2 and patch 5 work around it with abs64() at the two call sites that need it. Replacing it with Linux's __abs_choose_expr() version would be the root fix, but changes abs()'s return type from long to typeof(x) for every caller in the tree.
- abs_diff() lives in <linux/math64.h> here rather than upstream's <linux/math.h>; it could move to <linux/kernel.h> alongside abs().
- mul_u64_add_u64_div_u64() and the mul_u64_u64_div_u64() macros are not ported, as they need a u128 type and ~110 lines of lib/math/div64.c that nothing in U-Boot calls yet.
Build tested with both gcc and clang for evb-rk3288-rk808 (32-bit LE), generic-rk3576 (64-bit LE), malta (32-bit big-endian, which is what actually compiles the __BIG_ENDIAN union paths), plus sandbox and tools-only. No size change on any phase.
---
Alexey Charkov (5):
lib: div64: fix off-by-one shift in div64_u64() and div64_u64_rem()
lib: div64: use abs64() for the 64-bit operands of div64_s64()
lib: div64: inline __iter_div_u64_rem() into its only user
lib: div64: sync with Linux v7.1
lib: math64: sync <linux/math64.h> with Linux v7.1include/linux/math64.h | 201 +++++++++++++++++++++++++++++++++++++++++-------- lib/div64.c | 46 +++++++---- 2 files changed, 203 insertions(+), 44 deletions(-)
---
base-commit: 44f0dcf476140c1077ee3dbe16a80fdb6f8265c4
change-id: 20260730-math64-resync-3e50332c1683
Best regards,
Signature · 1 line
Alexey Charkov <[email protected]>
PATCH 1/5 lib: div64: fix off-by-one shift in div64_u64() and div64_u64_rem()
fls() counts bits starting from 1, so shifting the operands right by 1 + fls(high) discards one more bit of the divisor than intended. Both functions estimate the quotient from the shifted operands and then fix it up with a single decrement/increment, so an estimate that is off by more than one cannot be repaired and the result comes out wrong.
This only affects BITS_PER_LONG == 32, where these are the out-of-line implementations; on 64-bit the header provides plain C division.
The error is only reachable when the quotient is large, which needs a divisor just above 2^32. For example:
dividend = 15559272575191414037
divisor = 4333540799
expected = 3590429465
actual = 3590429468 (off by 3)
A sweep over 6.4M random operand pairs, stratified by the width of the divisor's high word, mismatches a __int128 reference 8260 times before this change and never after it. All failures have a divisor with one or two significant bits above bit 32; uniformly random 64-bit divisors are closer to 2^63 and yield quotients of ~1, which hides the problem.
Port of Linux commit cdc94a374931 ("lib/div64.c: off by one in shift"), which fixed the same code and cites [1].
In-tree users of div64_u64() that are built for 32-bit targets include the Aspeed, Meson and Cadence TTC PWM drivers, the Versaclock and wrpll-cln28hpc clock drivers, and the DWC3 USB core.
--- lib/div64.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
lib/div64.c +2 -2
@@ -109,7 +109,7 @@ u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder) quot =div_u64_rem (dividend, divisor, &rem32); *remainder = rem32; }else { -int n =1 +fls (high); +int n =fls (high); quot =div_u64 (dividend >> n, divisor >> n);if (quot !=0 )
@@ -147,7 +147,7 @@ u64 div64_u64(u64 dividend, u64 divisor)if (high ==0 ) { quot =div_u64 (dividend, divisor); }else { -int n =1 +fls (high); +int n =fls (high); quot =div_u64 (dividend >> n, divisor >> n);if (quot !=0 )
Signature · 1 line
2.54.0
Re: [PATCH 1/5] lib: div64: fix off-by-one shift in div64_u64() and div64_u64_rem()
Quoted 32 lines · Alexey Charkov
lib: div64: fix off-by-one shift in
div64_u64()anddiv64_u64_rem()
fls()counts bits starting from 1, so shifting the operands right by 1 + fls(high) discards one more bit of the divisor than intended. Both functions estimate the quotient from the shifted operands and then fix it up with a single decrement/increment, so an estimate that is off by more than one cannot be repaired and the result comes out wrong.This only affects
BITS_PER_LONG== 32, where these are the out-of-line implementations; on 64-bit the header provides plain C division.The error is only reachable when the quotient is large, which needs a divisor just above 2^32. For example:
dividend = 15559272575191414037
divisor = 4333540799
expected = 3590429465
actual = 3590429468 (off by 3)A sweep over 6.4M random operand pairs, stratified by the width of the divisor's high word, mismatches a
__int128reference 8260 times before this change and never after it. All failures have a divisor with one or two significant bits above bit 32; uniformly random 64-bit divisors are closer to 2^63 and yield quotients of ~1, which hides the problem.Port of Linux commit
cdc94a374931("lib/div64.c: off by one in shift"), which fixed the same code and cites [1].In-tree users of
div64_u64()that are built for 32-bit targets include the Aspeed, Meson and Cadence TTC PWM drivers, the Versaclock and wrpll-cln28hpc clock drivers, and the DWC3 USB core.
Quoted 6 lines
Fixes 0342e335ba88 ("lib: div64: sync with Linux")Signed-off-by Alexey Charkov <[email protected]>
lib/div64.c| 4 ++--1 file changed, 2 insertions(+), 2 deletions(-)
PATCH 2/5 lib: div64: use abs64() for the 64-bit operands of div64_s64()
In reply to Alexey CharkovBoth operands of div64_s64() are s64, but U-Boot's abs() is not 64-bit safe. Unlike its Linux counterpart, which dispatches on the argument type down to long long, U-Boot's abs() evaluates its argument as int whenever sizeof(x) != sizeof(long) and yields a long.
The header even says so: "abs() should not be used for 64-bit types (s64, u64, long long) - use abs64() for those."
So on BITS_PER_LONG == 32 both operands are silently truncated to 32 bits before the division. Simulating the macro with long narrowed to 32 bits shows what reaches div64_u64():
x= -4294967296 abs()= 0 abs64()= 4294967296 x= -5000000000 abs()= 705032704 abs64()= 5000000000 x=-9223372036854775807 abs()= 1 abs64()= 9223372036854775807
A zero from the first case makes the subsequent division a divide by zero rather than merely imprecise.
div64_s64() has no in-tree callers today, so this is a latent bug and not a regression. Note that the abs() in div_s64_rem() is correct as-is and deliberately left alone.
--- lib/div64.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)
lib/div64.c +6 -1
@@ -171,7 +171,12 @@ s64 div64_s64(s64 dividend, s64 divisor) {s64 quot, t; - quot =div64_u64 (abs (dividend),abs (divisor)); +/* +* Unlike Linux, U-Boot's abs() is not 64-bit safe: it evaluates its +* argument as int when sizeof(x) != sizeof(long), so both operands +* need abs64() here. +*/ + quot =div64_u64 (abs64 (dividend),abs64 (divisor)); t = (dividend ^ divisor) >>63 ;return (quot ^ t) - t;
Signature · 1 line
2.54.0
Re: [PATCH 2/5] lib: div64: use abs64() for the 64-bit operands of div64_s64()
Quoted 25 lines · Alexey Charkov
lib: div64: use
abs64()for the 64-bit operands ofdiv64_s64()Both operands of
div64_s64()are s64, but U-Boot'sabs()is not 64-bit safe. Unlike its Linux counterpart, which dispatches on the argument type down to long long, U-Boot'sabs()evaluates its argument as int whenever sizeof(x) != sizeof(long) and yields a long.The header even says so: "
abs()should not be used for 64-bit types (s64, u64, long long) - useabs64()for those."So on
BITS_PER_LONG== 32 both operands are silently truncated to 32 bits before the division. Simulating the macro with long narrowed to 32 bits shows what reachesdiv64_u64():x= -4294967296 abs()= 0 abs64()= 4294967296 x= -5000000000 abs()= 705032704 abs64()= 5000000000 x=-9223372036854775807 abs()= 1 abs64()= 9223372036854775807A zero from the first case makes the subsequent division a divide by zero rather than merely imprecise.
div64_s64()has no in-tree callers today, so this is a latent bug and not a regression. Note that theabs()indiv_s64_rem()is correct as-is and deliberately left alone.
Quoted 5 lines
Fixes 0342e335ba88 ("lib: div64: sync with Linux")Signed-off-by Alexey Charkov <[email protected]>
lib/div64.c| 7 ++++++-1 file changed, 6 insertions(+), 1 deletion(-)
PATCH 3/5 lib: div64: inline __iter_div_u64_rem() into its only user
In reply to Alexey Charkov__iter_div_u64_rem() is only split out in Linux for its vDSO header, which has no use in U-Boot. Inline the body of the helper directly into its only user, which is the iter_div_u64_rem() wrapper in this same file, and drop the static inline, so that a subsequent resync of include/linux/math64.h against Linux does not have to carry an exception for it.
include/vdso/math64.h is deliberately not created: its only other resident, mul_u64_u32_add_u64_shr(), has no U-Boot user.
No functional change: the generated code is identical, verified by comparing objdump -d of lib/div64.o before and after for evb-rk3288-rk808_defconfig. The compiler was already inlining the sole call.
iter_div_u64_rem() itself has no in-tree callers either, but it is upstream API and is left in place.
--- include/linux/math64.h | 19 ------------------- lib/div64.c | 17 ++++++++++++++++- 2 files changed, 16 insertions(+), 20 deletions(-)
include/linux/math64.h +0 -19
@@ -118,25 +118,6 @@ static inline s64 div_s64(s64 dividend, s32 divisor)u32 iter_div_u64_rem (u64 dividend,u32 divisor,u64 *remainder); -static __always_inline u32 -__iter_div_u64_rem (u64 dividend,u32 divisor,u64 *remainder) -{ -u32 ret =0 ; - -while (dividend >= divisor) { -/* The following asm() prevents the compiler from -optimising this loop into a modulo operation. */ - asm("" :"+rm" (dividend)); - - dividend -= divisor; - ret++; - } - - *remainder = dividend; - -return ret; -} -#ifndef mul_u32_u32/* * Many a GCC version messes this up and generates a 64x64 mult :-(
lib/div64.c +16 -1
@@ -192,6 +192,21 @@ EXPORT_SYMBOL(div64_s64);*/ u32 iter_div_u64_rem (u64 dividend,u32 divisor,u64 *remainder) { -return __iter_div_u64_rem (dividend, divisor, remainder); +u32 ret =0 ; + +while (dividend >= divisor) { +/* +* The following asm() prevents the compiler from +* optimising this loop into a modulo operation. +*/ + asm("" :"+rm" (dividend)); + + dividend -= divisor; + ret++; + } + + *remainder = dividend; + +return ret; }EXPORT_SYMBOL (iter_div_u64_rem);
Signature · 1 line
2.54.0
Re: [PATCH 3/5] lib: div64: inline __iter_div_u64_rem() into its only user
Quoted 16 lines · Alexey Charkov
lib: div64: inline
__iter_div_u64_rem()into its only user
__iter_div_u64_rem()is only split out in Linux for its vDSO header, which has no use in U-Boot. Inline the body of the helper directly into its only user, which is theiter_div_u64_rem()wrapper in this same file, and drop the static inline, so that a subsequent resync ofinclude/linux/math64.hagainst Linux does not have to carry an exception for it.
include/vdso/math64.his deliberately not created: its only other resident,mul_u64_u32_add_u64_shr(), has no U-Boot user.No functional change: the generated code is identical, verified by comparing objdump -d of
lib/div64.obefore and after for evb-rk3288-rk808_defconfig. The compiler was already inlining the sole call.
Quoted 8 lines
iter_div_u64_rem()itself has no in-tree callers either, but it is upstream API and is left in place.Signed-off-by Alexey Charkov <[email protected]>
include/linux/math64.h| 19 -------------------lib/div64.c | 17 ++++++++++++++++- 2 files changed, 16 insertions(+), 20 deletions(-)
PATCH 4/5 lib: div64: sync with Linux v7.1
In reply to Alexey CharkovBring the structure of this file in line with Linux v7.1 lib/math/div64.c, so that future resyncs are a near-verbatim diff. No functional change: the compiled lib/div64.o is byte-identical before and after, verified by comparing objdump -d output for both evb-rk3288-rk808_defconfig (32-bit, where these out-of-line helpers are actually built) and generic-rk3576_defconfig (64-bit).
- Add the SPDX license identifier, as upstream did in commit b24413180f56 ("License cleanup: add SPDX GPL-2.0 license identifier to files with no license").
- Demote the kernel-doc blocks on div64_u64_rem() and div64_u64() to plain comments and drop the one on div64_s64() entirely, following upstream commit d28a1de5d112 ("math64: favor kernel-doc from header files"). The kernel-doc for these lands in <linux/math64.h> in a later patch of this series; keeping it in both places would only let the two copies drift apart.
- Guard iter_div_u64_rem() with #ifndef iter_div_u64_rem, matching upstream, so an arch can override it the same way it can override the other helpers here.
Two U-Boot-local deviations are kept deliberately and are now marked as such so that the next resync does not silently drop them:
- __div64_32() carries a no_instrument_function attribute, needed because CONFIG_TRACE builds with -finstrument-functions and this function is reachable from tracing code via do_div().
- The includes stay as they are. <linux/compat.h> provides U-Boot's no-op EXPORT_SYMBOL() in place of upstream's <linux/export.h>, and <linux/kernel.h> provides abs()/abs64() in place of upstream's <linux/math.h>, which U-Boot does not have.
The u32/u64 spelling is also left alone rather than converted to Linux's uint32_t/uint64_t: U-Boot's <div64.h> already made the opposite choice, and matching Linux here would make the two files inconsistent for no benefit.
--- lib/div64.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-)
lib/div64.c +8 -10
@@ -1,3 +1,4 @@ +// SPDX-License-Identifier: GPL-2.0 /* * Copyright (C) 2003 Bernardo Innocenti <[email protected]> *
@@ -27,9 +28,9 @@#ifndef __div64_32/* -* Don't instrument this function as it may be called from tracing code, since -* it needs to read the timer and this often requires calling do_div(), which -* calls this function. +* U-Boot addition, not present upstream: don't instrument this function as it +* may be called from tracing code, since it needs to read the timer and this +* often requires calling do_div(), which calls this function. */ uint32_t __attribute__((weak, no_instrument_function))__div64_32 (u64 *n,u32 base)
@@ -87,7 +88,7 @@ s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)EXPORT_SYMBOL (div_s64_rem);#endif -/** +/* * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder * @dividend: 64bit dividend * @divisor: 64bit divisor
@@ -127,7 +128,7 @@ u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)EXPORT_SYMBOL (div64_u64_rem);#endif -/** +/* * div64_u64 - unsigned 64bit divide with 64bit divisor * @dividend: 64bit dividend * @divisor: 64bit divisor
@@ -161,11 +162,6 @@ u64 div64_u64(u64 dividend, u64 divisor)EXPORT_SYMBOL (div64_u64);#endif -/** -* div64_s64 - signed 64bit divide with 64bit divisor -* @dividend: 64bit dividend -* @divisor: 64bit divisor -*/ #ifndef div64_s64s64 div64_s64 (s64 dividend,s64 divisor) {
@@ -190,6 +186,7 @@ EXPORT_SYMBOL(div64_s64);* Iterative div/mod for use when dividend is not expected to be much * bigger than divisor. */ +#ifndef iter_div_u64_remu32 iter_div_u64_rem (u64 dividend,u32 divisor,u64 *remainder) {u32 ret =0 ;
@@ -210,3 +207,4 @@ u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder) return ret; }EXPORT_SYMBOL (iter_div_u64_rem); +#endif
Signature · 1 line
2.54.0
Re: [PATCH 4/5] lib: div64: sync with Linux v7.1
Quoted 41 lines · Alexey Charkov
lib: div64: sync with Linux v7.1
Bring the structure of this file in line with Linux v7.1
lib/math/div64.c, so that future resyncs are a near-verbatim diff. No functional change: the compiledlib/div64.ois byte-identical before and after, verified by comparing objdump -d output for both evb-rk3288-rk808_defconfig (32-bit, where these out-of-line helpers are actually built) and generic-rk3576_defconfig (64-bit).- Add the SPDX license identifier, as upstream did in commit
b24413180f56("License cleanup: add SPDX GPL-2.0 license identifier to files with no license").- Demote the kernel-doc blocks on
div64_u64_rem()anddiv64_u64()to plain comments and drop the one ondiv64_s64()entirely, following upstream commitd28a1de5d112("math64: favor kernel-doc from header files"). The kernel-doc for these lands in <linux/math64.h> in a later patch of this series; keeping it in both places would only let the two copies drift apart.- Guard
iter_div_u64_rem()with #ifndefiter_div_u64_rem, matching upstream, so an arch can override it the same way it can override the other helpers here.Two U-Boot-local deviations are kept deliberately and are now marked as such so that the next resync does not silently drop them:
-
__div64_32()carries ano_instrument_functionattribute, needed becauseCONFIG_TRACEbuilds with -finstrument-functions and this function is reachable from tracing code viado_div().- The includes stay as they are. <
linux/compat.h> provides U-Boot's no-opEXPORT_SYMBOL()in place of upstream's <linux/export.h>, and <linux/kernel.h> provides abs()/abs64() in place of upstream's <linux/math.h>, which U-Boot does not have.The u32/u64 spelling is also left alone rather than converted to Linux's uint32_t/uint64_t: U-Boot's <
div64.h> already made the opposite choice, and matching Linux here would make the two files inconsistent for no benefit.
Quoted 4 lines
Signed-off-by Alexey Charkov <[email protected]>
lib/div64.c| 18 ++++++++----------1 file changed, 8 insertions(+), 10 deletions(-)
PATCH 5/5 lib: math64: sync <linux/math64.h> with Linux v7.1
In reply to Alexey CharkovU-Boot's copy was last synced with Linux in 2017 by commit 0342e335ba88 ("lib: div64: sync with Linux"). Since then it has only been touched twice locally, and both times in ways that increased the divergence rather than tracking upstream. Take the file from the v7.1 tag.
The immediate motivation is DIV64_U64_ROUND_UP(). Commit 3adc17f60bf8 ("lib: div64: Add support for round up of div64_u64") added it inside the #if BITS_PER_LONG == 64 branch, whereas Linux defines it unconditionally after that block. Any 32-bit user therefore fails to compile:
error: implicit declaration of function 'DIV64_U64_ROUND_UP'; did you mean 'DIV_ROUND_UP'?
This has been surfaced while reworking fractional PLL logic for Rockchip RK3588/RK3576, which unexpectedly failed to compile on 32-bit variants [1].
Newly available as a result: DIV64_U64_ROUND_UP() on 32-bit, DIV_U64_ROUND_UP(), DIV64_U64_ROUND_CLOSEST(), DIV_U64_ROUND_CLOSEST(), DIV_S64_ROUND_CLOSEST(), roundup_u64(), add_u64_u32() and mul_s64_u64_shr(), plus upstream's kernel-doc for everything that was already here and __always_inline on mul_u64_u32_shr()/mul_u64_u64_shr().
The file is otherwise a verbatim copy of v7.1. Four deviations:
- The includes. U-Boot has no <linux/math.h>, no <asm/div64.h> and no <vdso/math64.h>. do_div() comes from U-Boot's <div64.h>, BITS_PER_LONG from <linux/bitops.h>, and abs64() from <linux/kernel.h>, which is where U-Boot keeps the rest of what upstream puts in <linux/math.h>.
- mul_s64_u64_shr() uses abs64() rather than abs(), because U-Boot's abs() evaluates its argument as int for anything that is not a long.
- mul_u64_add_u64_div_u64() and the mul_u64_u64_div_u64() and mul_u64_u64_div_u64_roundup() macros built on it are not ported. They would need ~110 lines of lib/math/div64.c brought along, plus a u128 type and OPTIMIZER_HIDE_VAR(), and U-Boot has no users for them yet.
- abs_diff(), added locally by commit f1f4a1d1d835 ("compat: math64:
add abs_diff()"), is kept. Upstream has it in <linux/math.h>.
Build tested for evb-rk3288-rk808 (32-bit LE), generic-rk3576 (64-bit LE), malta (32-bit BE, which is what compiles the __BIG_ENDIAN union paths in mul_u64_u64_shr() and mul_u64_u32_div()), sandbox and tools-only, with both gcc and clang. All six DIV*_ROUND_* macros plus roundup_u64(), mul_s64_u64_shr(), add_u64_u32() and abs_diff() were additionally instantiated on 32-bit ARM to confirm they now resolve.
--- include/linux/math64.h | 182 ++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 171 insertions(+), 11 deletions(-)
include/linux/math64.h +171 -11
@@ -1,8 +1,10 @@ +/* SPDX-License-Identifier: GPL-2.0 */ #ifndef _LINUX_MATH64_H#define _LINUX_MATH64_H#include <div64.h> #include <linux/bitops.h> +#include <linux/kernel.h> #include <linux/types.h> #if BITS_PER_LONG ==64
@@ -12,6 +14,11 @@/** * div_u64_rem - unsigned 64bit divide with 32bit divisor with remainder +* @dividend: unsigned 64bit dividend +* @divisor: unsigned 32bit divisor +* @remainder: pointer to unsigned 32bit remainder +* +* Return: sets ``*remainder``, then returns dividend / divisor * * This is commonly provided by 32bit archs to provide an optimized 64bit * divide.
@@ -24,6 +31,11 @@ static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)/** * div_s64_rem - signed 64bit divide with 32bit divisor with remainder +* @dividend: signed 64bit dividend +* @divisor: signed 32bit divisor +* @remainder: pointer to signed 32bit remainder +* +* Return: sets ``*remainder``, then returns dividend / divisor */ static inline s64 div_s64_rem (s64 dividend,s32 divisor,s32 *remainder) {
@@ -33,6 +45,11 @@ static inline s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)/** * div64_u64_rem - unsigned 64bit divide with 64bit divisor and remainder +* @dividend: unsigned 64bit dividend +* @divisor: unsigned 64bit divisor +* @remainder: pointer to unsigned 64bit remainder +* +* Return: sets ``*remainder``, then returns dividend / divisor */ static inline u64 div64_u64_rem (u64 dividend,u64 divisor,u64 *remainder) {
@@ -42,17 +59,22 @@ static inline u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder)/** * div64_u64 - unsigned 64bit divide with 64bit divisor +* @dividend: unsigned 64bit dividend +* @divisor: unsigned 64bit divisor +* +* Return: dividend / divisor */ static inline u64 div64_u64 (u64 dividend,u64 divisor) {return dividend / divisor; } -#define DIV64_U64_ROUND_UP (ll, d) \ - ({ u64 _tmp = (d); div64_u64((ll) + _tmp - 1, _tmp); }) -/** * div64_s64 - signed 64bit divide with 64bit divisor +* @dividend: signed 64bit dividend +* @divisor: signed 64bit divisor +* +* Return: dividend / divisor */ static inline s64 div64_s64 (s64 dividend,s64 divisor) {
@@ -92,10 +114,14 @@ extern s64 div64_s64(s64 dividend, s64 divisor);/** * div_u64 - unsigned 64bit divide with 32bit divisor +* @dividend: unsigned 64bit dividend +* @divisor: unsigned 32bit divisor * * This is the most common 64bit divide and should be used if possible, * as many 32bit archs can optimize this variant better than a full 64bit * divide. +* +* Return: dividend / divisor */ #ifndef div_u64static inline u64 div_u64 (u64 dividend,u32 divisor)
@@ -107,6 +133,10 @@ static inline u64 div_u64(u64 dividend, u32 divisor)/** * div_s64 - signed 64bit divide with 32bit divisor +* @dividend: signed 64bit dividend +* @divisor: signed 32bit divisor +* +* Return: dividend / divisor */ #ifndef div_s64static inline s64 div_s64 (s64 dividend,s32 divisor)
@@ -128,17 +158,28 @@ static inline u64 mul_u32_u32(u32 a, u32 b) }#endif +#ifndef add_u64_u32 +/* +* Many a GCC version also messes this up. +* Zero extending b and then spilling everything to stack. +*/ +static inline u64 add_u64_u32 (u64 a,u32 b) +{ +return a + b; +} +#endif +#if defined(CONFIG_ARCH_SUPPORTS_INT128 ) && defined(__SIZEOF_INT128__)#ifndef mul_u64_u32_shr -static inline u64 mul_u64_u32_shr (u64 a,u32 mul,unsigned int shift) +static __always_inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift) {return (u64)(((unsigned __int128 )a * mul) >> shift); }#endif /* mul_u64_u32_shr */ #ifndef mul_u64_u64_shr -static inline u64 mul_u64_u64_shr (u64 a,u64 mul,unsigned int shift) +static __always_inline u64 mul_u64_u64_shr(u64 a, u64 mul, unsigned int shift) {return (u64)(((unsigned __int128 )a * mul) >> shift); }
@@ -147,18 +188,14 @@ static inline u64 mul_u64_u64_shr(u64 a, u64 mul, unsigned int shift)#else #ifndef mul_u64_u32_shr -static inline u64 mul_u64_u32_shr (u64 a,u32 mul,unsigned int shift) +static __always_inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift) { -u32 ah, al; +u32 ah = a >>32 , al = a;u64 ret; - al = a; - ah = a >>32 ; - ret =mul_u32_u32 (al, mul) >> shift;if (ah) ret +=mul_u32_u32 (ah, mul) << (32 - shift); -return ret; }#endif /* mul_u64_u32_shr */
@@ -209,6 +246,27 @@ static inline u64 mul_u64_u64_shr(u64 a, u64 b, unsigned int shift)#endif +#ifndef mul_s64_u64_shr +static inline u64 mul_s64_u64_shr (s64 a,u64 b,unsigned int shift) +{ +u64 ret; + +/* +* Extract the sign before the multiplication and put it back +* afterwards if needed. +* +* Note: Linux uses abs() here, which U-Boot's abs() cannot do: +* it evaluates its argument as int for anything that is not a long. +*/ + ret =mul_u64_u64_shr (abs64 (a), b, shift); + +if (a <0 ) + ret = -((s64 ) ret); + +return ret; +} +#endif /* mul_s64_u64_shr */ +#ifndef mul_u64_u32_divstatic inline u64 mul_u64_u32_div (u64 a,u32 mul,u32 divisor) {
@@ -238,6 +296,108 @@ static inline u64 mul_u64_u32_div(u64 a, u32 mul, u32 divisor) }#endif /* mul_u64_u32_div */ +/* +* Not ported from Linux: mul_u64_add_u64_div_u64() and the +* mul_u64_u64_div_u64() / mul_u64_u64_div_u64_roundup() macros built on it. +* They need ~110 lines of lib/math/div64.c brought along, plus a u128 type +* and OPTIMIZER_HIDE_VAR(), and U-Boot has no users for them yet. Port the +* lot when the first one turns up. +*/ + +/** +* DIV64_U64_ROUND_UP - unsigned 64bit divide with 64bit divisor rounded up +* @ll: unsigned 64bit dividend +* @d: unsigned 64bit divisor +* +* Divide unsigned 64bit dividend by unsigned 64bit divisor +* and round up. +* +* Return: dividend / divisor rounded up +*/ +#define DIV64_U64_ROUND_UP (ll, d) \ + ({ u64 _tmp = (d); div64_u64((ll) + _tmp - 1, _tmp); }) + +/** +* DIV_U64_ROUND_UP - unsigned 64bit divide with 32bit divisor rounded up +* @ll: unsigned 64bit dividend +* @d: unsigned 32bit divisor +* +* Divide unsigned 64bit dividend by unsigned 32bit divisor +* and round up. +* +* Return: dividend / divisor rounded up +*/ +#define DIV_U64_ROUND_UP (ll, d) \ + ({ u32 _tmp = (d); div_u64((ll) + _tmp - 1, _tmp); }) + +/** +* DIV64_U64_ROUND_CLOSEST - unsigned 64bit divide with 64bit divisor rounded to nearest integer +* @dividend: unsigned 64bit dividend +* @divisor: unsigned 64bit divisor +* +* Divide unsigned 64bit dividend by unsigned 64bit divisor +* and round to closest integer. +* +* Return: dividend / divisor rounded to nearest integer +*/ +#define DIV64_U64_ROUND_CLOSEST (dividend, divisor) \ + ({ u64 _tmp = (divisor); div64_u64((dividend) + _tmp / 2, _tmp); }) + +/** +* DIV_U64_ROUND_CLOSEST - unsigned 64bit divide with 32bit divisor rounded to nearest integer +* @dividend: unsigned 64bit dividend +* @divisor: unsigned 32bit divisor +* +* Divide unsigned 64bit dividend by unsigned 32bit divisor +* and round to closest integer. +* +* Return: dividend / divisor rounded to nearest integer +*/ +#define DIV_U64_ROUND_CLOSEST (dividend, divisor) \ + ({ u32 _tmp = (divisor); div_u64((u64)(dividend) + _tmp / 2, _tmp); }) + +/** +* DIV_S64_ROUND_CLOSEST - signed 64bit divide with 32bit divisor rounded to nearest integer +* @dividend: signed 64bit dividend +* @divisor: signed 32bit divisor +* +* Divide signed 64bit dividend by signed 32bit divisor +* and round to closest integer. +* +* Return: dividend / divisor rounded to nearest integer +*/ +#define DIV_S64_ROUND_CLOSEST (dividend, divisor)( \ +{ \ + s64 __x = (dividend); \ + s32 __d = (divisor); \ + ((__x > 0) == (__d > 0)) ? \ + div_s64((__x + (__d / 2)), __d) : \ + div_s64((__x - (__d / 2)), __d); \ +} \ +) + +/** +* roundup_u64 - Round up a 64bit value to the next specified 32bit multiple +* @x: the value to up +* @y: 32bit multiple to round up to +* +* Rounds @x to the next multiple of @y. For 32bit @x values, see roundup and +* the faster round_up() for powers of 2. +* +* Return: rounded up value. +*/ +static inline u64 roundup_u64 (u64 x,u32 y) +{ +return DIV_U64_ROUND_UP (x, y) * y; +} + +/* +* U-Boot addition, not present in Linux's <linux/math64.h>: Linux keeps +* abs_diff() in <linux/math.h>, which U-Boot does not have. Its other +* contents live in <linux/kernel.h> here, but abs_diff() was added to this +* header instead, so leave it be rather than move it around. +*/ +/** * abs_diff - return absolute value of the difference between the arguments * @a: the first argument
Signature · 1 line
2.54.0
Re: [PATCH 5/5] lib: math64: sync <linux/math64.h> with Linux v7.1
Quoted 52 lines · Alexey Charkov
lib: math64: sync <
linux/math64.h> with Linux v7.1U-Boot's copy was last synced with Linux in 2017 by commit
0342e335ba88("lib: div64: sync with Linux"). Since then it has only been touched twice locally, and both times in ways that increased the divergence rather than tracking upstream. Take the file from the v7.1 tag.The immediate motivation is
DIV64_U64_ROUND_UP(). Commit3adc17f60bf8("lib: div64: Add support for round up ofdiv64_u64") added it inside the #ifBITS_PER_LONG== 64 branch, whereas Linux defines it unconditionally after that block. Any 32-bit user therefore fails to compile:error: implicit declaration of function '
DIV64_U64_ROUND_UP'; did you mean 'DIV_ROUND_UP'?This has been surfaced while reworking fractional PLL logic for Rockchip RK3588/RK3576, which unexpectedly failed to compile on 32-bit variants [1].
Newly available as a result:
DIV64_U64_ROUND_UP()on 32-bit,DIV_U64_ROUND_UP(),DIV64_U64_ROUND_CLOSEST(),DIV_U64_ROUND_CLOSEST(),DIV_S64_ROUND_CLOSEST(),roundup_u64(),add_u64_u32()andmul_s64_u64_shr(), plus upstream's kernel-doc for everything that was already here and__always_inlineon mul_u64_u32_shr()/mul_u64_u64_shr().The file is otherwise a verbatim copy of v7.1. Four deviations:
- The includes. U-Boot has no <
linux/math.h>, no <asm/div64.h> and no <vdso/math64.h>.do_div()comes from U-Boot's <div64.h>,BITS_PER_LONGfrom <linux/bitops.h>, andabs64()from <linux/kernel.h>, which is where U-Boot keeps the rest of what upstream puts in <linux/math.h>.-
mul_s64_u64_shr()usesabs64()rather thanabs(), because U-Boot'sabs()evaluates its argument as int for anything that is not a long.-
mul_u64_add_u64_div_u64()and themul_u64_u64_div_u64()andmul_u64_u64_div_u64_roundup()macros built on it are not ported. They would need ~110 lines oflib/math/div64.cbrought along, plus a u128 type andOPTIMIZER_HIDE_VAR(), and U-Boot has no users for them yet.-
abs_diff(), added locally by commitf1f4a1d1d835("compat: math64:
addabs_diff()"), is kept. Upstream has it in <linux/math.h>.Build tested for evb-rk3288-rk808 (32-bit LE), generic-rk3576 (64-bit LE), malta (32-bit BE, which is what compiles the
__BIG_ENDIANunion paths inmul_u64_u64_shr()andmul_u64_u32_div()), sandbox and tools-only, with both gcc and clang. All six DIV*_ROUND_* macros plusroundup_u64(),mul_s64_u64_shr(),add_u64_u32()andabs_diff()were additionally instantiated on 32-bit ARM to confirm they now resolve.
Quoted 5 lines
Signed-off-by Alexey Charkov <[email protected]>
include/linux/math64.h| 182 ++++++++++++++++++++++++++++++++++++++++++++++---1 file changed, 171 insertions(+), 11 deletions(-)
Quoted 64 lines · Alexey Charkov
U-Boot's <
linux/math64.h> was last really synced with Linux in 2017 by commit0342e335ba88("lib: div64: sync with Linux"). Since then it has only been patched locally twice, and both times in ways that increased the divergence rather than tracking upstream.The one that prompted this series is
DIV64_U64_ROUND_UP(). Commit3adc17f60bf8("lib: div64: Add support for round up ofdiv64_u64") added it inside the #ifBITS_PER_LONG== 64 branch, whereas upstream defines it unconditionally after that block, so any 32-bit user fails to build.While auditing the header, two bugs turned up in
lib/div64.c, so this series starts with those. Both are 32-bit only:-
div64_u64()anddiv64_u64_rem()shifted by 1 + fls(high) instead of fls(high), losing a bit of the divisor. Linux fixed this in 2019, while U-Boot never picked it up.-
div64_s64()usedabs()on s64 operands. U-Boot'sabs()is not 64-bit
safe: its own comment says to useabs64()instead. Both operands were silently truncated to 32 bits.Transitive headers that affect what <
linux/math64.h> offers were checked too. <linux/math.h> and <vdso/math64.h> have no U-Boot equivalent and are not needed;do_div()comes from U-Boot's <div64.h> in place of <asm/div64.h>.Deliberately left out of this resync:
-
CONFIG_ARCH_SUPPORTS_INT128is tested by <linux/math64.h> but isn't defined anywhere in U-Boot, so the__int128fast paths formul_u64_u32_shr()andmul_u64_u64_shr()are dead code on arm64, riscv64 andx86_64where they could have been useful. Wiring it up in the arch Kconfigs looks like an easy win (but could result in subtle behavior changes or code size drift, so needs to be approached separately).-
abs()in <linux/kernel.h> diverges from Linux and is not 64-bit safe. Patch 2 and patch 5 work around it withabs64()at the two call sites that need it. Replacing it with Linux's__abs_choose_expr()version would be the root fix, but changes abs()'s return type from long to typeof(x) for every caller in the tree.-
abs_diff()lives in <linux/math64.h> here rather than upstream's <linux/math.h>; it could move to <linux/kernel.h> alongsideabs().-
mul_u64_add_u64_div_u64()and themul_u64_u64_div_u64()macros are not ported, as they need a u128 type and ~110 lines oflib/math/div64.cthat nothing in U-Boot calls yet.Build tested with both gcc and clang for evb-rk3288-rk808 (32-bit LE), generic-rk3576 (64-bit LE), malta (32-bit big-endian, which is what actually compiles the
__BIG_ENDIANunion paths), plus sandbox and tools-only. No size change on any phase.Signed-off-by Alexey Charkov <[email protected]>---
Alexey Charkov (5):lib: div64: fix off-by-one shift in div64_u64() and div64_u64_rem() lib: div64: use abs64() for the 64-bit operands of div64_s64() lib: div64: inline __iter_div_u64_rem() into its only user lib: div64: sync with Linux v7.1 lib: math64: sync <linux/math64.h> with Linux v7.1
Quoted 3 lines
include/linux/math64.h | 201 +++++++++++++++++++++++++++++++++++++++++-------- lib/div64.c | 46 +++++++---- 2 files changed, 203 insertions(+), 44 deletions(-)
NB: CI passes all green:
https://git.u-boot-project.org/u-boot/contributors/alchark/u-boot/-/pipelines/812
Best regards,
Alexey
Hi Alexey,
Quoted 2 lines · Alexey Charkov
While auditing the header, two bugs turned up in
lib/div64.c, so this series starts with those. Both are 32-bit only:
Thanks for looking at this!
Quoted 3 lines
-
div64_u64()anddiv64_u64_rem()shifted by 1 + fls(high) instead of fls(high), losing a bit of the divisor. Linux fixed this in 2019, while U-Boot never picked it up.
Since patch 1 has such a nice reproducer, how about adding a small self-test under test/lib/ for div64_u64() and div64_s64() as part of this series? It would guard against future regressions on 32-bit and give the sync patches some cover. A handful of the divisor-just-above-2^32 cases plus the div64_s64() truncation case would be plenty.
Regards,
Simon
Quoted 11 lines · Alexey Charkov
U-Boot's <
linux/math64.h> was last really synced with Linux in 2017 by commit0342e335ba88("lib: div64: sync with Linux"). Since then it has only been patched locally twice, and both times in ways that increased the divergence rather than tracking upstream.The one that prompted this series is
DIV64_U64_ROUND_UP(). Commit3adc17f60bf8("lib: div64: Add support for round up ofdiv64_u64") added it inside the #ifBITS_PER_LONG== 64 branch, whereas upstream defines it unconditionally after that block, so any 32-bit user fails to build.[...]
Applied to u-boot/next, thanks!
[1/5] lib: div64: fix off-by-one shift in div64_u64() and div64_u64_rem()
commit: 8e82c0a75f5df98df1b23d0898c4d7008ab64621
[2/5] lib: div64: use abs64() for the 64-bit operands of div64_s64()
commit: c81dbcc9cef01c31f7d6f3da07130cdf4f3ec63a
[3/5] lib: div64: inline __iter_div_u64_rem() into its only user
commit: 6228dd6d791c0f9eab56060a1eb404d4d174b525
[4/5] lib: div64: sync with Linux v7.1
commit: 378c10eab1a7224f00ee7d9b29748bb08c14d396
[5/5] lib: math64: sync <linux/math64.h> with Linux v7.1
commit: b7fd64c36d4c98e5259a9970d3382cad2a715f74Signature · 1 line
Tom