Skip to content

Implement mul_u64_u64_div_u64_roundup()

David Laight lkml 5 versions – Applied

Status from this message: [merged mm-nonmm-stable] lib-test_mul_u64_u64_div_u64-test-the-32bit-code-on-64bit.patch removed from -mm tree

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v5 Latest9 patches 5 repliesApplied 9/9
  2. v49 patches 20 repliesApplied
  3. v310 patches 35 repliesSuperseded
Earlier versions · 2
VersionPostedPatchesRepliesStatus
v24 patches15 repliesSuperseded
v13 patches10 repliesSuperseded

Changes in v5 from the cover letter

- Fix x86-64 asm code to correctly add non-constant 'add' values.
- Fix build on 32bit x86.
- Check for small dividends before divide overflow.

Patches in v5 All 9 applied

#Subject and filesSizeRepliesApplied
1/9lib: mul_u64_u64_div_u64() rename parameter 'c' to 'd'lib/math/div64.c+12 -120 repliesApplied
2/9lib: mul_u64_u64_div_u64() Combine overflow and divide by zero checkslib/math/div64.c+9 -100 repliesApplied
3/9lib: mul_u64_u64_div_u64() simplify check for a 64bit productlib/math/div64.c+3 -31 replyApplied
4/9lib: Add mul_u64_add_u64_div_u64() and mul_u64_u64_div_u64_roundup()arch/x86/include/asm/div64.h include/linux/math64.h lib/math/div64.c+67 -152 repliesApplied
5/9lib: Add tests for mul_u64_u64_div_u64_roundup()lib/math/test_mul_u64_u64_div_u64.c+73 -490 repliesApplied
6/9lib: test_mul_u64_u64_div_u64: Test both generic and arch versionslib/math/div64.c lib/math/test_mul_u64_u64_div_u64.c+51 -90 repliesApplied
7/9lib: mul_u64_u64_div_u64() optimise multiply on 32bit x86arch/x86/include/asm/div64.h include/linux/math64.h lib/math/div64.c+56 -142 repliesApplied
8/9lib: mul_u64_u64_div_u64() Optimise the divide codelib/math/div64.c+85 -390 repliesApplied
9/9lib: test_mul_u64_u64_div_u64: Test the 32bit code on 64bitlib/math/test_mul_u64_u64_div_u64.c+29 -00 repliesApplied

Reviews trailers per patch

All 9 patches have a Reviewed-by or Acked-by.

PatchNicolas Pitre
1/9R-b
2/9R-b
3/9R-b
4/9R-b
5/9R-b
6/9R-b
7/9R-b
8/9R-b
9/9R-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v5 thread

Cover letter [PATCH v5 next 0/9] Implement mul_u64_u64_div_u64_roundup()

The pwm-stm32.c code wants a 'rounding up' version of mul_u64_u64_div_u64(). This can be done simply by adding 'divisor - 1' to the 128bit product. Implement mul_u64_add_u64_div_u64(a, b, c, d) = (a * b + c)/d based on the existing code.
Define mul_u64_u64_div_u64(a, b, d) as mul_u64_add_u64_div_u64(a, b, 0, d) and mul_u64_u64_div_u64_roundup(a, b, d) as mul_u64_add_u64_div_u64(a, b, d-1, d).

Only x86-64 has an optimsed (asm) version of the function. That is optimised to avoid the 'add c' when c is known to be zero. In all other cases the extra code will be noise compared to the software divide code.

The test module has been updated to test mul_u64_u64_div_u64_roundup() and also enhanced it to verify the C division code on x86-64 and the 32bit division code on 64bit.

Changes for v2:
- Rename the 'divisor' parameter from 'c' to 'd'.
- Add an extra patch to use BUG_ON() to trap zero divisors.
- Remove the last patch that ran the C code on x86-64 (I've a plan to do that differently).

Changes for v3:
- Replace the BUG_ON() (or panic in the original version) for zero divisors with a WARN_ONCE() and return zero.
- Remove the 'pre-multiply' check for small products. Completely non-trivial on 32bit systems.
- Use mul_u32_u32() and the new add_u64_u32() to stop gcc generating pretty much pessimal code for x86 with lots of register spills.
- Replace the 'bit at a time' divide with one that generates 16 bits per iteration on 32bit systems and 32 bits per iteration on 64bit. Massively faster, the tests run in under 1/3 the time.

Changes for v4:
No significant code changes.
- Rebase on 6.18-rc2
- Don't change the behaviour for overflow (return ~0ull) or divide by zero (execute ~0ul/0).
- Merge patches 8 and 9 to avoid bisection issues.
- Fix build of 32bit test cases on non-x86.
- Fix shell script that verifies test cases.

Changes for v5:
- Fix x86-64 asm code to correctly add non-constant 'add' values.
- Fix build on 32bit x86.
- Check for small dividends before divide overflow.

I've left the x86-64 faulting on both overflow and divide by zero. The patch to add an execption table entry to return ~0 for both doesn't seem to have been merged.
If merged it would make sense for the C version to return ~0 for both. Callers can check for a result of ~0 and then check the divisor if they care about overflow (etc).
(A valid quotent of ~0 is pretty unlikely and marginal changes to the input values are likely to generate a real overflow.)
The code that faulted on overflow was about to get invalid results because one of the 64bit inputs would itself wrap very soon.

David Laight (9):
lib: mul_u64_u64_div_u64() rename parameter 'c' to 'd'
lib: mul_u64_u64_div_u64() Combine overflow and divide by zero checks
lib: mul_u64_u64_div_u64() simplify check for a 64bit product
lib: Add mul_u64_add_u64_div_u64() and mul_u64_u64_div_u64_roundup()
lib: Add tests for mul_u64_u64_div_u64_roundup()
lib: test_mul_u64_u64_div_u64: Test both generic and arch versions
lib: mul_u64_u64_div_u64() optimise multiply on 32bit x86
lib: mul_u64_u64_div_u64() Optimise the divide code
lib: test_mul_u64_u64_div_u64: Test the 32bit code on 64bit

 arch/x86/include/asm/div64.h        |  39 ++++--
 include/linux/math64.h              |  59 ++++++++-
 lib/math/div64.c                    | 185 ++++++++++++++++++---------
 lib/math/test_mul_u64_u64_div_u64.c | 191 ++++++++++++++++++++--------
 4 files changed, 354 insertions(+), 120 deletions(-)
Signature · 1 line
2.39.5