From 2947a4567f3a79127d2d540384e7f042106c1a24 Mon Sep 17 00:00:00 2001 From: Nathan Chancellor Date: Tue, 9 Jan 2024 15:16:31 -0700 Subject: treewide: update LLVM Bugzilla links LLVM moved their issue tracker from their own Bugzilla instance to GitHub issues. While all of the links are still valid, they may not necessarily show the most up to date information around the issues, as all updates will occur on GitHub, not Bugzilla. Another complication is that the Bugzilla issue number is not always the same as the GitHub issue number. Thankfully, LLVM maintains this mapping through two shortlinks: https://llvm.org/bz -> https://bugs.llvm.org/show_bug.cgi?id= https://llvm.org/pr -> https://github.com/llvm/llvm-project/issues/ Switch all "https://bugs.llvm.org/show_bug.cgi?id=" links to the "https://llvm.org/pr" shortlink so that the links show the most up to date information. Each migrated issue links back to the Bugzilla entry, so there should be no loss of fidelity of information here. Link: https://lkml.kernel.org/r/20240109-update-llvm-links-v1-3-eb09b59db071@kernel.org Signed-off-by: Nathan Chancellor Reviewed-by: Kees Cook Acked-by: Fangrui Song Cc: Alexei Starovoitov Cc: Andrii Nakryiko Cc: Daniel Borkmann Cc: Mykola Lysenko Signed-off-by: Andrew Morton --- lib/Kconfig.kasan | 2 +- lib/raid6/Makefile | 2 +- lib/stackinit_kunit.c | 2 +- 3 files changed, 3 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/Kconfig.kasan b/lib/Kconfig.kasan index e6eda054ab27..98016e137b7f 100644 --- a/lib/Kconfig.kasan +++ b/lib/Kconfig.kasan @@ -158,7 +158,7 @@ config KASAN_STACK out-of-bounds bugs in stack variables. With Clang, stack instrumentation has a problem that causes excessive - stack usage, see https://bugs.llvm.org/show_bug.cgi?id=38809. Thus, + stack usage, see https://llvm.org/pr38809. Thus, with Clang, this option is deemed unsafe. This option is always disabled when compile-testing with Clang to diff --git a/lib/raid6/Makefile b/lib/raid6/Makefile index 1c5420ff254e..385a94aa0b99 100644 --- a/lib/raid6/Makefile +++ b/lib/raid6/Makefile @@ -21,7 +21,7 @@ altivec_flags += -isystem $(shell $(CC) -print-file-name=include) ifdef CONFIG_CC_IS_CLANG # clang ppc port does not yet support -maltivec when -msoft-float is # enabled. A future release of clang will resolve this -# https://bugs.llvm.org/show_bug.cgi?id=31177 +# https://llvm.org/pr31177 CFLAGS_REMOVE_altivec1.o += -msoft-float CFLAGS_REMOVE_altivec2.o += -msoft-float CFLAGS_REMOVE_altivec4.o += -msoft-float diff --git a/lib/stackinit_kunit.c b/lib/stackinit_kunit.c index 05947a2feb93..7a10e1d17258 100644 --- a/lib/stackinit_kunit.c +++ b/lib/stackinit_kunit.c @@ -404,7 +404,7 @@ static noinline int leaf_switch_2_none(unsigned long sp, bool fill, * These are expected to fail for most configurations because neither * GCC nor Clang have a way to perform initialization of variables in * non-code areas (i.e. in a switch statement before the first "case"). - * https://bugs.llvm.org/show_bug.cgi?id=44916 + * https://llvm.org/pr44916 */ DEFINE_TEST_DRIVER(switch_1_none, uint64_t, SCALAR, ALWAYS_FAIL); DEFINE_TEST_DRIVER(switch_2_none, uint64_t, SCALAR, ALWAYS_FAIL); -- cgit v1.2.3 From db946a42226052a13fbce8757ff77b3107dd2030 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Sat, 13 Jan 2024 11:13:51 +0800 Subject: lib/sort: optimize heapsort for equal elements in sift-down path Patch series "lib/sort: Optimize the number of swaps and comparisons". This patch series aims to optimize the heapsort algorithm, specifically targeting a reduction in the number of swaps and comparisons required. This patch (of 2): Currently, when searching for the sift-down path and encountering equal elements, the algorithm chooses the left child. However, considering that the height of the right subtree may be one less than that of the left subtree, selecting the right child in such cases can potentially reduce the number of comparisons and swaps. For instance, when sorting an array of 10,000 identical elements, the current implementation requires 247,209 comparisons. With this patch, the number of comparisons can be reduced to 227,241. Link: https://lkml.kernel.org/r/20240113031352.2395118-1-visitorckw@gmail.com Link: https://lkml.kernel.org/r/20240113031352.2395118-2-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Signed-off-by: Andrew Morton --- lib/sort.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/sort.c b/lib/sort.c index b399bf10d675..fe4efd4a1410 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -262,7 +262,7 @@ void sort_r(void *base, size_t num, size_t size, * average, 3/4 worst-case.) */ for (b = a; c = 2*b + size, (d = c + size) < n;) - b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d; + b = do_cmp(base + c, base + d, cmp_func, priv) > 0 ? c : d; if (d == n) /* Special case last leaf with no sibling */ b = c; -- cgit v1.2.3 From 0e02ca29a5634dfb90fe1bad9467ee0965a1e170 Mon Sep 17 00:00:00 2001 From: Kuan-Wei Chiu Date: Sat, 13 Jan 2024 11:13:52 +0800 Subject: lib/sort: optimize heapsort with double-pop variation Instead of popping only the maximum element from the heap during each iteration, we now pop the two largest elements at once. Although this introduces an additional comparison to determine the second largest element, it enables a reduction in the height of the tree by one during the heapify operations starting from root's left/right child. This reduction in tree height by one leads to a decrease of one comparison and one swap. This optimization results in saving approximately 0.5 * n swaps without increasing the number of comparisons. Additionally, the heap size during heapify is now one less than the original size, offering a chance for further reduction in comparisons and swaps. The following experimental data is based on the array generated using get_random_u32(). | N | swaps (old) | swaps (new) | comparisons (old) | comparisons (new) | |-------|-------------|-------------|-------------------|-------------------| | 1000 | 9054 | 8569 | 10328 | 10320 | | 2000 | 20137 | 19182 | 22634 | 22587 | | 3000 | 32062 | 30623 | 35833 | 35752 | | 4000 | 44274 | 42282 | 49332 | 49306 | | 5000 | 57195 | 54676 | 63300 | 63294 | | 6000 | 70205 | 67202 | 77599 | 77557 | | 7000 | 83276 | 79831 | 92113 | 92032 | | 8000 | 96630 | 92678 | 106635 | 106617 | | 9000 | 110349 | 105883 | 121505 | 121404 | | 10000 | 124165 | 119202 | 136628 | 136617 | Link: https://lkml.kernel.org/r/20240113031352.2395118-3-visitorckw@gmail.com Signed-off-by: Kuan-Wei Chiu Cc: Ching-Chun (Jim) Huang Cc: George Spelvin Signed-off-by: Andrew Morton --- lib/sort.c | 18 ++++++++++++++---- 1 file changed, 14 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/sort.c b/lib/sort.c index fe4efd4a1410..a0509088f82a 100644 --- a/lib/sort.c +++ b/lib/sort.c @@ -215,6 +215,7 @@ void sort_r(void *base, size_t num, size_t size, /* pre-scale counters for performance */ size_t n = num * size, a = (num/2) * size; const unsigned int lsbit = size & -size; /* Used to find parent */ + size_t shift = 0; if (!a) /* num < 2 || size == 0 */ return; @@ -242,12 +243,21 @@ void sort_r(void *base, size_t num, size_t size, for (;;) { size_t b, c, d; - if (a) /* Building heap: sift down --a */ - a -= size; - else if (n -= size) /* Sorting: Extract root to --n */ + if (a) /* Building heap: sift down a */ + a -= size << shift; + else if (n > 3 * size) { /* Sorting: Extract two largest elements */ + n -= size; do_swap(base, base + n, size, swap_func, priv); - else /* Sort complete */ + shift = do_cmp(base + size, base + 2 * size, cmp_func, priv) <= 0; + a = size << shift; + n -= size; + do_swap(base + a, base + n, size, swap_func, priv); + } else if (n > size) { /* Sorting: Extract root */ + n -= size; + do_swap(base, base + n, size, swap_func, priv); + } else { /* Sort complete */ break; + } /* * Sift element at "a" down into heap. This is the -- cgit v1.2.3 From d6bbab8f352efb0533d3fa4af09bb60da770ecc5 Mon Sep 17 00:00:00 2001 From: Kemeng Shi Date: Fri, 19 Jan 2024 04:13:21 +0800 Subject: flex_proportions: remove unused fprop_local_single The single variant of flex_proportions is not used. Simply remove it. Link: https://lkml.kernel.org/r/20240118201321.759174-1-shikemeng@huaweicloud.com Signed-off-by: Kemeng Shi Reviewed-by: Jan Kara Signed-off-by: Andrew Morton --- lib/flex_proportions.c | 77 -------------------------------------------------- 1 file changed, 77 deletions(-) (limited to 'lib') diff --git a/lib/flex_proportions.c b/lib/flex_proportions.c index 83332fefa6f4..84ecccddc771 100644 --- a/lib/flex_proportions.c +++ b/lib/flex_proportions.c @@ -83,83 +83,6 @@ bool fprop_new_period(struct fprop_global *p, int periods) return true; } -/* - * ---- SINGLE ---- - */ - -int fprop_local_init_single(struct fprop_local_single *pl) -{ - pl->events = 0; - pl->period = 0; - raw_spin_lock_init(&pl->lock); - return 0; -} - -void fprop_local_destroy_single(struct fprop_local_single *pl) -{ -} - -static void fprop_reflect_period_single(struct fprop_global *p, - struct fprop_local_single *pl) -{ - unsigned int period = p->period; - unsigned long flags; - - /* Fast path - period didn't change */ - if (pl->period == period) - return; - raw_spin_lock_irqsave(&pl->lock, flags); - /* Someone updated pl->period while we were spinning? */ - if (pl->period >= period) { - raw_spin_unlock_irqrestore(&pl->lock, flags); - return; - } - /* Aging zeroed our fraction? */ - if (period - pl->period < BITS_PER_LONG) - pl->events >>= period - pl->period; - else - pl->events = 0; - pl->period = period; - raw_spin_unlock_irqrestore(&pl->lock, flags); -} - -/* Event of type pl happened */ -void __fprop_inc_single(struct fprop_global *p, struct fprop_local_single *pl) -{ - fprop_reflect_period_single(p, pl); - pl->events++; - percpu_counter_add(&p->events, 1); -} - -/* Return fraction of events of type pl */ -void fprop_fraction_single(struct fprop_global *p, - struct fprop_local_single *pl, - unsigned long *numerator, unsigned long *denominator) -{ - unsigned int seq; - s64 num, den; - - do { - seq = read_seqcount_begin(&p->sequence); - fprop_reflect_period_single(p, pl); - num = pl->events; - den = percpu_counter_read_positive(&p->events); - } while (read_seqcount_retry(&p->sequence, seq)); - - /* - * Make fraction <= 1 and denominator > 0 even in presence of percpu - * counter errors - */ - if (den <= num) { - if (num) - den = num; - else - den = 1; - } - *denominator = den; - *numerator = num; -} - /* * ---- PERCPU ---- */ -- cgit v1.2.3 From c3c6c204823859037c24507420ed83947fe506f1 Mon Sep 17 00:00:00 2001 From: Geert Uytterhoeven Date: Mon, 22 Jan 2024 15:50:43 +0100 Subject: lib: dhry: remove unneeded Patch series "lib: dhry: miscellaneous cleanups". This patch series contains a few miscellaneous cleanups for the Dhrystone benchmark test. This patch (of 3): The Dhrystone benchmark test does not use mutexes. Link: https://lkml.kernel.org/r/cover.1705934853.git.geert+renesas@glider.be Link: https://lkml.kernel.org/r/cf8fafaedccf96143f1513745c43a457480bfc24.1705934853.git.geert+renesas@glider.be Signed-off-by: Geert Uytterhoeven Signed-off-by: Andrew Morton --- lib/dhry_run.c | 1 - 1 file changed, 1 deletion(-) (limited to 'lib') diff --git a/lib/dhry_run.c b/lib/dhry_run.c index f15ac666e9d3..e6a279dabf84 100644 --- a/lib/dhry_run.c +++ b/lib/dhry_run.c @@ -10,7 +10,6 @@ #include #include #include -#include #include #define DHRY_VAX 1757 -- cgit v1.2.3 From b8d1b82837f342969b96c6ee6c4fde5e9ea02974 Mon Sep 17 00:00:00 2001 From: Geert Uytterhoeven Date: Mon, 22 Jan 2024 15:50:44 +0100 Subject: lib: dhry: use ktime_ms_delta() helper Use the existing ktime_ms_delta() helper instead of open-coding the same operation. Link: https://lkml.kernel.org/r/bb43c67a7580de6152f5e6eb225071166d33b6e4.1705934853.git.geert+renesas@glider.be Signed-off-by: Geert Uytterhoeven Signed-off-by: Andrew Morton --- lib/dhry_1.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/dhry_1.c b/lib/dhry_1.c index 08edbbb19f57..ca6c87232c58 100644 --- a/lib/dhry_1.c +++ b/lib/dhry_1.c @@ -277,7 +277,7 @@ int dhry(int n) dhry_assert_string_eq(Str_1_Loc, "DHRYSTONE PROGRAM, 1'ST STRING"); dhry_assert_string_eq(Str_2_Loc, "DHRYSTONE PROGRAM, 2'ND STRING"); - User_Time = ktime_to_ms(ktime_sub(End_Time, Begin_Time)); + User_Time = ktime_ms_delta(End_Time, Begin_Time); kfree(Ptr_Glob); kfree(Next_Ptr_Glob); -- cgit v1.2.3 From f785785c0a545d2cb254a619a47bcbffa0ee07d3 Mon Sep 17 00:00:00 2001 From: Geert Uytterhoeven Date: Mon, 22 Jan 2024 15:50:45 +0100 Subject: lib: dhry: add missing closing parenthesis The help text for the Dhrystone benchmark test lacks a matching closing parenthesis. Link: https://lkml.kernel.org/r/772b43271bcb3dd17a6aae671b2084f08c05b079.1705934853.git.geert+renesas@glider.be Signed-off-by: Geert Uytterhoeven Signed-off-by: Andrew Morton --- lib/Kconfig.debug | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 975a07f9f1cc..8f502f15dc7f 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2142,7 +2142,7 @@ config TEST_DHRY To run the benchmark, it needs to be enabled explicitly, either from the kernel command line (when built-in), or from userspace (when - built-in or modular. + built-in or modular). Run once during kernel boot: -- cgit v1.2.3 From 9feceff1d2d6075b9556b84b81a14c584ef78aa5 Mon Sep 17 00:00:00 2001 From: Nathan Chancellor Date: Thu, 25 Jan 2024 15:55:16 -0700 Subject: lib/Kconfig.debug: update Clang version check in CONFIG_KCOV Now that the minimum supported version of LLVM for building the kernel has been bumped to 13.0.1, this condition can be changed to just CONFIG_CC_IS_CLANG, as the build will fail during the configuration stage for older LLVM versions. Link: https://lkml.kernel.org/r/20240125-bump-min-llvm-ver-to-13-0-1-v1-10-f5ff9bda41c5@kernel.org Signed-off-by: Nathan Chancellor Reviewed-by: Kees Cook Cc: Albert Ou Cc: "Aneesh Kumar K.V (IBM)" Cc: Ard Biesheuvel Cc: Borislav Petkov (AMD) Cc: Catalin Marinas Cc: Conor Dooley Cc: Dave Hansen Cc: Ingo Molnar Cc: Mark Rutland Cc: Masahiro Yamada Cc: Michael Ellerman Cc: "Naveen N. Rao" Cc: Nicholas Piggin Cc: Nicolas Schier Cc: Palmer Dabbelt Cc: Paul Walmsley Cc: Russell King Cc: Thomas Gleixner Cc: Will Deacon Signed-off-by: Andrew Morton --- lib/Kconfig.debug | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 8f502f15dc7f..1339fb893d71 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2085,7 +2085,7 @@ config KCOV depends on ARCH_HAS_KCOV depends on CC_HAS_SANCOV_TRACE_PC || GCC_PLUGINS depends on !ARCH_WANTS_NO_INSTR || HAVE_NOINSTR_HACK || \ - GCC_VERSION >= 120000 || CLANG_VERSION >= 130000 + GCC_VERSION >= 120000 || CC_IS_CLANG select DEBUG_FS select GCC_PLUGIN_SANCOV if !CC_HAS_SANCOV_TRACE_PC select OBJTOOL if HAVE_NOINSTR_HACK -- cgit v1.2.3 From 9bea6216f94bb711267e01f6ff8b07e3ff1e22d6 Mon Sep 17 00:00:00 2001 From: Andy Shevchenko Date: Tue, 13 Feb 2024 18:27:41 +0200 Subject: dyndbg: replace kstrdup() + strchr() with kstrdup_and_replace() Replace open coded functionalify of kstrdup_and_replace() with a call. Link: https://lkml.kernel.org/r/20240213162741.3102810-1-andriy.shevchenko@linux.intel.com Signed-off-by: Andy Shevchenko Reviewed-by: Luis Chamberlain Cc: Jason Baron Cc: Jim Cromie Signed-off-by: Andrew Morton --- lib/dynamic_debug.c | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/dynamic_debug.c b/lib/dynamic_debug.c index 6fba6423cc10..c78f335fa981 100644 --- a/lib/dynamic_debug.c +++ b/lib/dynamic_debug.c @@ -640,10 +640,9 @@ static int param_set_dyndbg_classnames(const char *instr, const struct kernel_pa int cls_id, totct = 0; bool wanted; - cl_str = tmp = kstrdup(instr, GFP_KERNEL); - p = strchr(cl_str, '\n'); - if (p) - *p = '\0'; + cl_str = tmp = kstrdup_and_replace(instr, '\n', '\0', GFP_KERNEL); + if (!tmp) + return -ENOMEM; /* start with previously set state-bits, then modify */ curr_bits = old_bits = *dcp->bits; -- cgit v1.2.3 From 8c86fb68ffcb0d8a5418e171c8d359d712912e9b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Uwe=20Kleine-K=C3=B6nig?= Date: Sun, 3 Mar 2024 10:24:09 +0100 Subject: mul_u64_u64_div_u64: increase precision by conditionally swapping a and b MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit As indicated in the added comment, the algorithm works better if b is big. As multiplication is commutative, a and b can be swapped. Do this if a is bigger than b. Link: https://lkml.kernel.org/r/20240303092408.662449-2-u.kleine-koenig@pengutronix.de Signed-off-by: Uwe Kleine-König Tested-by: Biju Das Signed-off-by: Andrew Morton --- lib/math/div64.c | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'lib') diff --git a/lib/math/div64.c b/lib/math/div64.c index 55a81782e271..191761b1b623 100644 --- a/lib/math/div64.c +++ b/lib/math/div64.c @@ -22,6 +22,7 @@ #include #include #include +#include #include /* Not needed on 64bit architectures */ @@ -190,6 +191,20 @@ u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 c) /* can a * b overflow ? */ if (ilog2(a) + ilog2(b) > 62) { + /* + * Note that the algorithm after the if block below might lose + * some precision and the result is more exact for b > a. So + * exchange a and b if a is bigger than b. + * + * For example with a = 43980465100800, b = 100000000, c = 1000000000 + * the below calculation doesn't modify b at all because div == 0 + * and then shift becomes 45 + 26 - 62 = 9 and so the result + * becomes 4398035251080. However with a and b swapped the exact + * result is calculated (i.e. 4398046510080). + */ + if (a > b) + swap(a, b); + /* * (b * a) / c is equal to * -- cgit v1.2.3 From c44f063e740ed580574b9012751e641e749bbe0e Mon Sep 17 00:00:00 2001 From: Peng Hao Date: Wed, 6 Mar 2024 11:48:04 +0800 Subject: buildid: use kmap_local_page() Use kmap_local_page() instead of kmap_atomic() which has been deprecated. Link: https://lkml.kernel.org/r/20240306034804.62087-1-flyingpeng@tencent.com Signed-off-by: Peng Hao Signed-off-by: Andrew Morton --- lib/buildid.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/buildid.c b/lib/buildid.c index e3a7acdeef0e..29fdfb4cccf0 100644 --- a/lib/buildid.c +++ b/lib/buildid.c @@ -140,7 +140,7 @@ int build_id_parse(struct vm_area_struct *vma, unsigned char *build_id, return -EFAULT; /* page not mapped */ ret = -EINVAL; - page_addr = kmap_atomic(page); + page_addr = kmap_local_page(page); ehdr = (Elf32_Ehdr *)page_addr; /* compare magic x7f "ELF" */ @@ -156,7 +156,7 @@ int build_id_parse(struct vm_area_struct *vma, unsigned char *build_id, else if (ehdr->e_ident[EI_CLASS] == ELFCLASS64) ret = get_build_id_64(page_addr, build_id, size); out: - kunmap_atomic(page_addr); + kunmap_local(page_addr); put_page(page); return ret; } -- cgit v1.2.3 From bea0a58695870295a315cec15a9fea6f40fe5ff3 Mon Sep 17 00:00:00 2001 From: Roman Smirnov Date: Thu, 7 Mar 2024 10:17:17 +0300 Subject: assoc_array: fix the return value in assoc_array_insert_mid_shortcut() Returning the edit variable is redundant because it is dereferenced right before it is returned. It would be better to return true. Found by Linux Verification Center (linuxtesting.org) with Svace. Link: https://lkml.kernel.org/r/20240307071717.5318-1-r.smirnov@omp.ru Signed-off-by: Roman Smirnov Reviewed-by: Sergey Shtylyov Signed-off-by: Andrew Morton --- lib/assoc_array.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/assoc_array.c b/lib/assoc_array.c index ca0b4f360c1a..388e656ac974 100644 --- a/lib/assoc_array.c +++ b/lib/assoc_array.c @@ -938,7 +938,7 @@ static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit, edit->leaf_p = &new_n0->slots[0]; pr_devel("<--%s() = ok [split shortcut]\n", __func__); - return edit; + return true; } /** -- cgit v1.2.3