linux.git/lib/math, branch v6.6.132 Clone of https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git bitmap: introduce generic optimized bitmap_size() 2024-08-29T15:33:14+00:00 Alexander Lobakin aleksander.lobakin@intel.com 2024-03-27T15:23:49+00:00 97a532c3ac4f5219d2fffc7cf1bebbe31a9b0929 commit a37fbe666c016fd89e4460d0ebfcea05baba46dc upstream. The number of times yet another open coded `BITS_TO_LONGS(nbits) * sizeof(long)` can be spotted is huge. Some generic helper is long overdue. Add one, bitmap_size(), but with one detail. BITS_TO_LONGS() uses DIV_ROUND_UP(). The latter works well when both divident and divisor are compile-time constants or when the divisor is not a pow-of-2. When it is however, the compilers sometimes tend to generate suboptimal code (GCC 13): 48 83 c0 3f add $0x3f,%rax 48 c1 e8 06 shr $0x6,%rax 48 8d 14 c5 00 00 00 00 lea 0x0(,%rax,8),%rdx %BITS_PER_LONG is always a pow-2 (either 32 or 64), but GCC still does full division of `nbits + 63` by it and then multiplication by 8. Instead of BITS_TO_LONGS(), use ALIGN() and then divide by 8. GCC: 8d 50 3f lea 0x3f(%rax),%edx c1 ea 03 shr $0x3,%edx 81 e2 f8 ff ff 1f and $0x1ffffff8,%edx Now it shifts `nbits + 63` by 3 positions (IOW performs fast division by 8) and then masks bits[2:0]. bloat-o-meter: add/remove: 0/0 grow/shrink: 20/133 up/down: 156/-773 (-617) Clang does it better and generates the same code before/after starting from -O1, except that with the ALIGN() approach it uses %edx and thus still saves some bytes: add/remove: 0/0 grow/shrink: 9/133 up/down: 18/-538 (-520) Note that we can't expand DIV_ROUND_UP() by adding a check and using this approach there, as it's used in array declarations where expressions are not allowed. Add this helper to tools/ as well. Reviewed-by: Przemek Kitszel <przemyslaw.kitszel@intel.com> Acked-by: Yury Norov <yury.norov@gmail.com> Signed-off-by: Alexander Lobakin <aleksander.lobakin@intel.com> Signed-off-by: David S. Miller <davem@davemloft.net> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org> 
commit a37fbe666c016fd89e4460d0ebfcea05baba46dc upstream.

The number of times yet another open coded
`BITS_TO_LONGS(nbits) * sizeof(long)` can be spotted is huge.
Some generic helper is long overdue.

Add one, bitmap_size(), but with one detail.
BITS_TO_LONGS() uses DIV_ROUND_UP(). The latter works well when both
divident and divisor are compile-time constants or when the divisor
is not a pow-of-2. When it is however, the compilers sometimes tend
to generate suboptimal code (GCC 13):

48 83 c0 3f          	add    $0x3f,%rax
48 c1 e8 06          	shr    $0x6,%rax
48 8d 14 c5 00 00 00 00	lea    0x0(,%rax,8),%rdx

%BITS_PER_LONG is always a pow-2 (either 32 or 64), but GCC still does
full division of `nbits + 63` by it and then multiplication by 8.
Instead of BITS_TO_LONGS(), use ALIGN() and then divide by 8. GCC:

8d 50 3f             	lea    0x3f(%rax),%edx
c1 ea 03             	shr    $0x3,%edx
81 e2 f8 ff ff 1f    	and    $0x1ffffff8,%edx

Now it shifts `nbits + 63` by 3 positions (IOW performs fast division
by 8) and then masks bits[2:0]. bloat-o-meter:

add/remove: 0/0 grow/shrink: 20/133 up/down: 156/-773 (-617)

Clang does it better and generates the same code before/after starting
from -O1, except that with the ALIGN() approach it uses %edx and thus
still saves some bytes:

add/remove: 0/0 grow/shrink: 9/133 up/down: 18/-538 (-520)

Note that we can't expand DIV_ROUND_UP() by adding a check and using
this approach there, as it's used in array declarations where
expressions are not allowed.
Add this helper to tools/ as well.

Reviewed-by: Przemek Kitszel <przemyslaw.kitszel@intel.com>
Acked-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Alexander Lobakin <aleksander.lobakin@intel.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
lib/math/int_log: Replace LGPL-2.1-or-later boilerplate with SPDX identifier 2023-07-09T21:47:50+00:00 Andy Shevchenko andriy.shevchenko@linux.intel.com 2023-07-03T13:52:10+00:00 9ab04d7ed8bdd395b0617a1647dd475681f99151 Replace license boilerplate in udftime.c with SPDX identifier for LGPL-2.1-or-later. Acked-by: Mauro Carvalho Chehab <mchehab@kernel.org> Link: https://lore.kernel.org/r/20230619172019.21457-4-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Link: https://lore.kernel.org/r/20230703135211.87416-4-andriy.shevchenko@linux.intel.com Signed-off-by: Mark Brown <broonie@kernel.org> 
Replace license boilerplate in udftime.c with SPDX identifier for
LGPL-2.1-or-later.

Acked-by: Mauro Carvalho Chehab <mchehab@kernel.org>
Link: https://lore.kernel.org/r/20230619172019.21457-4-andriy.shevchenko@linux.intel.com
Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Link: https://lore.kernel.org/r/20230703135211.87416-4-andriy.shevchenko@linux.intel.com
Signed-off-by: Mark Brown <broonie@kernel.org>
lib/math/int_log: Use ARRAY_SIZE(logtable) where makes sense 2023-07-09T21:47:49+00:00 Andy Shevchenko andriy.shevchenko@linux.intel.com 2023-07-03T13:52:09+00:00 08f6a14b2d376e96cb7166694193ec3c3a496d25 Use ARRAY_SIZE(logtable) where makes sense. Reviewed-by: Mauro Carvalho Chehab <mchehab@kernel.org> Acked-by: Mauro Carvalho Chehab <mchehab@kernel.org> Link: https://lore.kernel.org/r/20230619172019.21457-3-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Link: https://lore.kernel.org/r/20230703135211.87416-3-andriy.shevchenko@linux.intel.com Signed-off-by: Mark Brown <broonie@kernel.org> 
Use ARRAY_SIZE(logtable) where makes sense.

Reviewed-by: Mauro Carvalho Chehab <mchehab@kernel.org>
Acked-by: Mauro Carvalho Chehab <mchehab@kernel.org>
Link: https://lore.kernel.org/r/20230619172019.21457-3-andriy.shevchenko@linux.intel.com
Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Link: https://lore.kernel.org/r/20230703135211.87416-3-andriy.shevchenko@linux.intel.com
Signed-off-by: Mark Brown <broonie@kernel.org>
lib/math: Move dvb_math.c into lib/math/int_log.c 2023-07-09T21:47:48+00:00 Andy Shevchenko andriy.shevchenko@linux.intel.com 2023-07-03T13:52:08+00:00 f97fa3dcb2db02013e6904c032a1d2d45707ee40 Some existing and new users may benefit from the intlog2() and intlog10() APIs, make them wide available. Reviewed-by: Mauro Carvalho Chehab <mchehab@kernel.org> Acked-by: Mauro Carvalho Chehab <mchehab@kernel.org> Link: https://lore.kernel.org/r/20230619172019.21457-2-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Reviewed-by: Randy Dunlap <rdunlap@infradead.org> Link: https://lore.kernel.org/r/20230703135211.87416-2-andriy.shevchenko@linux.intel.com Signed-off-by: Mark Brown <broonie@kernel.org> 
Some existing and new users may benefit from the intlog2() and
intlog10() APIs, make them wide available.

Reviewed-by: Mauro Carvalho Chehab <mchehab@kernel.org>
Acked-by: Mauro Carvalho Chehab <mchehab@kernel.org>
Link: https://lore.kernel.org/r/20230619172019.21457-2-andriy.shevchenko@linux.intel.com
Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Reviewed-by: Randy Dunlap <rdunlap@infradead.org>
Link: https://lore.kernel.org/r/20230703135211.87416-2-andriy.shevchenko@linux.intel.com
Signed-off-by: Mark Brown <broonie@kernel.org>
math64: favor kernel-doc from header files 2022-11-21T21:30:53+00:00 Liam Beguin liambeguin@gmail.com 2022-11-18T18:23:07+00:00 d28a1de5d1128d6caef15fdc04d3f6484dc7264b Fix the kernel-doc markings for div64 functions to point to the header file instead of the lib/ directory. This avoids having implementation specific comments in generic documentation. Furthermore, given that some kernel-doc comments are identical, drop them from lib/math64 and only keep there comments that add implementation details. Signed-off-by: Liam Beguin <liambeguin@gmail.com> Acked-by: Randy Dunlap <rdunlap@infradead.org> Tested-by: Randy Dunlap <rdunlap@infradead.org> Link: https://lore.kernel.org/r/20221118182309.3824530-1-liambeguin@gmail.com Signed-off-by: Jonathan Corbet <corbet@lwn.net> 
Fix the kernel-doc markings for div64 functions to point to the header
file instead of the lib/ directory.  This avoids having implementation
specific comments in generic documentation.  Furthermore, given that
some kernel-doc comments are identical, drop them from lib/math64 and
only keep there comments that add implementation details.

Signed-off-by: Liam Beguin <liambeguin@gmail.com>
Acked-by: Randy Dunlap <rdunlap@infradead.org>
Tested-by: Randy Dunlap <rdunlap@infradead.org>
Link: https://lore.kernel.org/r/20221118182309.3824530-1-liambeguin@gmail.com
Signed-off-by: Jonathan Corbet <corbet@lwn.net>
math: make RATIONAL tristate 2021-09-08T18:50:26+00:00 Geert Uytterhoeven geert@linux-m68k.org 2021-09-08T02:58:33+00:00 bcda5fd34417c89f653cc0912cc0608b36ea032c Patch series "math: RATIONAL and RATIONAL_KUNIT_TEST improvements". This series makes the RATIONAL symbol tristate, so it is not forced builtin if all users are modular, and makes the RATIONAL_KUNIT_TEST depend on RATIONAL, to avoid enabling RATIONAL if there are no real users. This patch (of 2): All but one symbols that select RATIONAL are tristate, but RATIONAL itself is bool. Change it to tristate, so the rational fractions support code can be modular if no builtin code relies on it. Link: https://lkml.kernel.org/r/20210706100945.3803694-1-geert@linux-m68k.org Link: https://lkml.kernel.org/r/20210706100945.3803694-2-geert@linux-m68k.org Signed-off-by: Geert Uytterhoeven <geert@linux-m68k.org> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Trent Piepho <tpiepho@gmail.com> Cc: Colin Ian King <colin.king@canonical.com> Cc: Brendan Higgins <brendanhiggins@google.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> 
Patch series "math: RATIONAL and RATIONAL_KUNIT_TEST improvements".

This series makes the RATIONAL symbol tristate, so it is not forced
builtin if all users are modular, and makes the RATIONAL_KUNIT_TEST depend
on RATIONAL, to avoid enabling RATIONAL if there are no real users.

This patch (of 2):

All but one symbols that select RATIONAL are tristate, but RATIONAL itself
is bool.  Change it to tristate, so the rational fractions support code
can be modular if no builtin code relies on it.

Link: https://lkml.kernel.org/r/20210706100945.3803694-1-geert@linux-m68k.org
Link: https://lkml.kernel.org/r/20210706100945.3803694-2-geert@linux-m68k.org
Signed-off-by: Geert Uytterhoeven <geert@linux-m68k.org>
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Cc: Trent Piepho <tpiepho@gmail.com>
Cc: Colin Ian King <colin.king@canonical.com>
Cc: Brendan Higgins <brendanhiggins@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
lib/math/rational: add Kunit test cases 2021-07-01T18:06:05+00:00 Trent Piepho tpiepho@gmail.com 2021-07-01T01:55:52+00:00 b6c75c4afceb8bc065a4ebb5c6c381452bf96f53 Adds a number of test cases that cover a range of possible code paths. [akpm@linux-foundation.org: remove non-ascii characters, fix whitespace] [colin.king@canonical.com: fix spelling mistake "demominator" -> "denominator"] Link: https://lkml.kernel.org/r/20210526085049.6393-1-colin.king@canonical.com Link: https://lkml.kernel.org/r/20210525144250.214670-2-tpiepho@gmail.com Signed-off-by: Trent Piepho <tpiepho@gmail.com> Signed-off-by: Colin Ian King <colin.king@canonical.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Daniel Latypov <dlatypov@google.com> Cc: Oskar Schirmer <oskar@scara.com> Cc: Yiyuan Guo <yguoaz@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> 
Adds a number of test cases that cover a range of possible code paths.

[akpm@linux-foundation.org: remove non-ascii characters, fix whitespace]
[colin.king@canonical.com: fix spelling mistake "demominator" -> "denominator"]
  Link: https://lkml.kernel.org/r/20210526085049.6393-1-colin.king@canonical.com

Link: https://lkml.kernel.org/r/20210525144250.214670-2-tpiepho@gmail.com
Signed-off-by: Trent Piepho <tpiepho@gmail.com>
Signed-off-by: Colin Ian King <colin.king@canonical.com>
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Cc: Daniel Latypov <dlatypov@google.com>
Cc: Oskar Schirmer <oskar@scara.com>
Cc: Yiyuan Guo <yguoaz@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
lib/math/rational.c: fix divide by zero 2021-07-01T18:06:05+00:00 Trent Piepho tpiepho@gmail.com 2021-07-01T01:55:49+00:00 65a0d3c14685663ba111038a35db70f559e39336 If the input is out of the range of the allowed values, either larger than the largest value or closer to zero than the smallest non-zero allowed value, then a division by zero would occur. In the case of input too large, the division by zero will occur on the first iteration. The best result (largest allowed value) will be found by always choosing the semi-convergent and excluding the denominator based limit when finding it. In the case of the input too small, the division by zero will occur on the second iteration. The numerator based semi-convergent should not be calculated to avoid the division by zero. But the semi-convergent vs previous convergent test is still needed, which effectively chooses between 0 (the previous convergent) vs the smallest allowed fraction (best semi-convergent) as the result. Link: https://lkml.kernel.org/r/20210525144250.214670-1-tpiepho@gmail.com Fixes: 323dd2c3ed0 ("lib/math/rational.c: fix possible incorrect result from rational fractions helper") Signed-off-by: Trent Piepho <tpiepho@gmail.com> Reported-by: Yiyuan Guo <yguoaz@gmail.com> Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Oskar Schirmer <oskar@scara.com> Cc: Daniel Latypov <dlatypov@google.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org> 
If the input is out of the range of the allowed values, either larger than
the largest value or closer to zero than the smallest non-zero allowed
value, then a division by zero would occur.

In the case of input too large, the division by zero will occur on the
first iteration.  The best result (largest allowed value) will be found by
always choosing the semi-convergent and excluding the denominator based
limit when finding it.

In the case of the input too small, the division by zero will occur on the
second iteration.  The numerator based semi-convergent should not be
calculated to avoid the division by zero.  But the semi-convergent vs
previous convergent test is still needed, which effectively chooses
between 0 (the previous convergent) vs the smallest allowed fraction (best
semi-convergent) as the result.

Link: https://lkml.kernel.org/r/20210525144250.214670-1-tpiepho@gmail.com
Fixes: 323dd2c3ed0 ("lib/math/rational.c: fix possible incorrect result from rational fractions helper")
Signed-off-by: Trent Piepho <tpiepho@gmail.com>
Reported-by: Yiyuan Guo <yguoaz@gmail.com>
Reviewed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Cc: Oskar Schirmer <oskar@scara.com>
Cc: Daniel Latypov <dlatypov@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Merge tag 'mips_5.13' of git://git.kernel.org/pub/scm/linux/kernel/git/mips/linux 2021-04-29T18:28:08+00:00 Linus Torvalds torvalds@linux-foundation.org 2021-04-29T18:28:08+00:00 77d51337d650086643e1e96b8a7e1e6cbf0b09ff Pull MIPS updates from Thomas Bogendoerfer: - removed get_fs/set_fs - removed broken/unmaintained MIPS KVM trap and emulate support - added support for Loongson-2K1000 - fixes and cleanups * tag 'mips_5.13' of git://git.kernel.org/pub/scm/linux/kernel/git/mips/linux: (107 commits) MIPS: BCM63XX: Use BUG_ON instead of condition followed by BUG. MIPS: select ARCH_KEEP_MEMBLOCK unconditionally mips: Do not include hi and lo in clobber list for R6 MIPS:DTS:Correct the license for Loongson-2K MIPS:DTS:Fix label name and interrupt number of ohci for Loongson-2K MIPS: Avoid handcoded DIVU in `__div64_32' altogether lib/math/test_div64: Correct the spelling of "dividend" lib/math/test_div64: Fix error message formatting mips/bootinfo:correct some comments of fw_arg MIPS: Avoid DIVU in `__div64_32' is result would be zero MIPS: Reinstate platform `__div64_32' handler div64: Correct inline documentation for `do_div' lib/math: Add a `do_div' test module MIPS: Makefile: Replace -pg with CC_FLAGS_FTRACE MIPS: pci-legacy: revert "use generic pci_enable_resources" MIPS: Loongson64: Add kexec/kdump support MIPS: pci-legacy: use generic pci_enable_resources MIPS: pci-legacy: remove busn_resource field MIPS: pci-legacy: remove redundant info messages MIPS: pci-legacy: stop using of_pci_range_to_resource ... 
Pull MIPS updates from Thomas Bogendoerfer:

 - removed get_fs/set_fs

 - removed broken/unmaintained MIPS KVM trap and emulate support

 - added support for Loongson-2K1000

 - fixes and cleanups

* tag 'mips_5.13' of git://git.kernel.org/pub/scm/linux/kernel/git/mips/linux: (107 commits)
  MIPS: BCM63XX: Use BUG_ON instead of condition followed by BUG.
  MIPS: select ARCH_KEEP_MEMBLOCK unconditionally
  mips: Do not include hi and lo in clobber list for R6
  MIPS:DTS:Correct the license for Loongson-2K
  MIPS:DTS:Fix label name and interrupt number of ohci for Loongson-2K
  MIPS: Avoid handcoded DIVU in `__div64_32' altogether
  lib/math/test_div64: Correct the spelling of "dividend"
  lib/math/test_div64: Fix error message formatting
  mips/bootinfo:correct some comments of fw_arg
  MIPS: Avoid DIVU in `__div64_32' is result would be zero
  MIPS: Reinstate platform `__div64_32' handler
  div64: Correct inline documentation for `do_div'
  lib/math: Add a `do_div' test module
  MIPS: Makefile: Replace -pg with CC_FLAGS_FTRACE
  MIPS: pci-legacy: revert "use generic pci_enable_resources"
  MIPS: Loongson64: Add kexec/kdump support
  MIPS: pci-legacy: use generic pci_enable_resources
  MIPS: pci-legacy: remove busn_resource field
  MIPS: pci-legacy: remove redundant info messages
  MIPS: pci-legacy: stop using of_pci_range_to_resource
  ...
lib/math/test_div64: Correct the spelling of "dividend" 2021-04-23T11:40:05+00:00 Maciej W. Rozycki macro@orcam.me.uk 2021-04-22T20:36:08+00:00 517b322c07e17787fc8a22ca9cede709b6ae9ec0 The word is spelt with a final "d" of course. What a massive messup! Signed-off-by: Maciej W. Rozycki <macro@orcam.me.uk> Signed-off-by: Thomas Bogendoerfer <tsbogend@alpha.franken.de> 
The word is spelt with a final "d" of course.  What a massive messup!

Signed-off-by: Maciej W. Rozycki <macro@orcam.me.uk>
Signed-off-by: Thomas Bogendoerfer <tsbogend@alpha.franken.de>