Skip to contentSkip to conversation

lib: resync lib/div64.c and <linux/math64.h> with Linux v7.1

PATCH In review Alexey Charkov 3 participants 14 messages Jul 30 – Aug 11 Library code

lore
Share & tools
lore
#0 lore raw

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.1
 include/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]>
#1 lore raw

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.

Fixes 0342e335ba88 ("lib: div64: sync with Linux")
---
 lib/div64.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
lib/div64.c +2 -2
index 779d7521f69f..14d402ce4c7e 100644
@@ -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
Reviewed-by on v1 1/5
#2 lore raw

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() 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.

Quoted 6 lines
Fixes 0342e335ba88 ("lib: div64: sync with Linux")

lib/div64.c | 4 ++--

 1 file changed, 2 insertions(+), 2 deletions(-)
#3 lore raw

PATCH 2/5 lib: div64: use abs64() for the 64-bit operands of div64_s64()

In reply to Alexey Charkov

Both 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.

Fixes 0342e335ba88 ("lib: div64: sync with Linux")
---
 lib/div64.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
lib/div64.c +6 -1
index 14d402ce4c7e..f5624279086a 100644
@@ -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
Reviewed-by on v1 2/5
#4 lore raw

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 of div64_s64()

Both 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.

Quoted 5 lines
Fixes 0342e335ba88 ("lib: div64: sync with Linux")

lib/div64.c | 7 ++++++-

 1 file changed, 6 insertions(+), 1 deletion(-)
#5 lore raw

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
index 70a7ee3ff1d3..eb560e3183a9 100644
@@ -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
index f5624279086a..9db7499fcd34 100644
@@ -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
Reviewed-by on v1 3/5
#6 lore raw

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 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.

Quoted 8 lines

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(-)
#7 lore raw

PATCH 4/5 lib: div64: sync with Linux v7.1

In reply to Alexey Charkov

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 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
index 9db7499fcd34..e3553c3956ed 100644
@@ -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_s64
 s64 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_rem
 u32 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
Reviewed-by on v1 4/5
#8 lore raw

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 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.

Quoted 4 lines

lib/div64.c | 18 ++++++++----------

 1 file changed, 8 insertions(+), 10 deletions(-)
#9 lore raw

PATCH 5/5 lib: math64: sync <linux/math64.h> with Linux v7.1

In reply to Alexey Charkov

U-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
index eb560e3183a9..78c184eb85be 100644
@@ -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_u64
 static 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_s64
 static 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_div
 static 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
Reviewed-by on v1 5/5
#10 lore raw

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.1

U-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.

Quoted 5 lines

include/linux/math64.h | 182 ++++++++++++++++++++++++++++++++++++++++++++++---

 1 file changed, 171 insertions(+), 11 deletions(-)
#11 lore raw
In reply to Alexey Charkov
Quoted 64 lines · Alexey Charkov

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.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

#12 lore raw
In reply to Alexey Charkov

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() 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.

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

#13 lore raw
In reply to Alexey Charkov
Quoted 11 lines · Alexey Charkov

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.

[...]

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: b7fd64c36d4c98e5259a9970d3382cad2a715f74
Signature · 1 line
Tom