diff options
Diffstat (limited to 'lib')
58 files changed, 3444 insertions, 813 deletions
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 881c3f84e88a..c8b379e2e9ad 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -389,6 +389,15 @@ config PAHOLE_HAS_BTF_TAG btf_decl_tag) or not. Currently only clang compiler implements these attributes, so make the config depend on CC_IS_CLANG. +config PAHOLE_HAS_LANG_EXCLUDE + def_bool PAHOLE_VERSION >= 124 + help + Support for the --lang_exclude flag which makes pahole exclude + compilation units from the supplied language. Used in Kbuild to + omit Rust CUs which are not supported in version 1.24 of pahole, + otherwise it would emit malformed kernel and module binaries when + using DEBUG_INFO_BTF_MODULES. + config DEBUG_INFO_BTF_MODULES def_bool y depends on DEBUG_INFO_BTF && MODULES && PAHOLE_HAS_SPLIT_BTF @@ -743,76 +752,6 @@ config SHRINKER_DEBUG visibility into the kernel memory shrinkers subsystem. Disable it to avoid an extra memory footprint. -config HAVE_DEBUG_KMEMLEAK - bool - -config DEBUG_KMEMLEAK - bool "Kernel memory leak detector" - depends on DEBUG_KERNEL && HAVE_DEBUG_KMEMLEAK - select DEBUG_FS - select STACKTRACE if STACKTRACE_SUPPORT - select KALLSYMS - select CRC32 - select STACKDEPOT - help - Say Y here if you want to enable the memory leak - detector. The memory allocation/freeing is traced in a way - similar to the Boehm's conservative garbage collector, the - difference being that the orphan objects are not freed but - only shown in /sys/kernel/debug/kmemleak. Enabling this - feature will introduce an overhead to memory - allocations. See Documentation/dev-tools/kmemleak.rst for more - details. - - Enabling DEBUG_SLAB or SLUB_DEBUG may increase the chances - of finding leaks due to the slab objects poisoning. - - In order to access the kmemleak file, debugfs needs to be - mounted (usually at /sys/kernel/debug). - -config DEBUG_KMEMLEAK_MEM_POOL_SIZE - int "Kmemleak memory pool size" - depends on DEBUG_KMEMLEAK - range 200 1000000 - default 16000 - help - Kmemleak must track all the memory allocations to avoid - reporting false positives. Since memory may be allocated or - freed before kmemleak is fully initialised, use a static pool - of metadata objects to track such callbacks. After kmemleak is - fully initialised, this memory pool acts as an emergency one - if slab allocations fail. - -config DEBUG_KMEMLEAK_TEST - tristate "Simple test for the kernel memory leak detector" - depends on DEBUG_KMEMLEAK && m - help - This option enables a module that explicitly leaks memory. - - If unsure, say N. - -config DEBUG_KMEMLEAK_DEFAULT_OFF - bool "Default kmemleak to off" - depends on DEBUG_KMEMLEAK - help - Say Y here to disable kmemleak by default. It can then be enabled - on the command line via kmemleak=on. - -config DEBUG_KMEMLEAK_AUTO_SCAN - bool "Enable kmemleak auto scan thread on boot up" - default y - depends on DEBUG_KMEMLEAK - help - Depending on the cpu, kmemleak scan may be cpu intensive and can - stall user tasks at times. This option enables/disables automatic - kmemleak scan at boot up. - - Say N here to disable kmemleak auto scan thread to stop automatic - scanning. Disabling this option disables automatic reporting of - memory leaks. - - If unsure, say Y. - config DEBUG_STACK_USAGE bool "Stack utilization instrumentation" depends on DEBUG_KERNEL && !IA64 @@ -1207,7 +1146,7 @@ config SCHED_DEBUG depends on DEBUG_KERNEL && PROC_FS default y help - If you say Y here, the /proc/sched_debug file will be provided + If you say Y here, the /sys/kernel/debug/sched file will be provided that can help debug the scheduler. The runtime overhead of this option is minimal. @@ -1246,13 +1185,16 @@ config DEBUG_TIMEKEEPING config DEBUG_PREEMPT bool "Debug preemptible kernel" depends on DEBUG_KERNEL && PREEMPTION && TRACE_IRQFLAGS_SUPPORT - default y help If you say Y here then the kernel will use a debug variant of the commonly used smp_processor_id() function and will print warnings if kernel code uses it in a preemption-unsafe way. Also, the kernel will detect preemption count underflows. + This option has potential to introduce high runtime overhead, + depending on workload as it triggers debugging routines for each + this_cpu operation. It should only be used for debugging purposes. + menu "Lock Debugging (spinlocks, mutexes, etc...)" config LOCK_DEBUGGING_SUPPORT @@ -1552,6 +1494,17 @@ config TRACE_IRQFLAGS_NMI depends on TRACE_IRQFLAGS depends on TRACE_IRQFLAGS_NMI_SUPPORT +config NMI_CHECK_CPU + bool "Debugging for CPUs failing to respond to backtrace requests" + depends on DEBUG_KERNEL + depends on X86 + default n + help + Enables debug prints when a CPU fails to respond to a given + backtrace NMI. These prints provide some reasons why a CPU + might legitimately be failing to respond, for example, if it + is offline of if ignore_nmis is set. + config DEBUG_IRQFLAGS bool "Debug IRQ flag manipulation" help @@ -1917,7 +1870,7 @@ config FUNCTION_ERROR_INJECTION help Add fault injections into various functions that are annotated with ALLOW_ERROR_INJECTION() in the kernel. BPF may also modify the return - value of theses functions. This is useful to test error paths of code. + value of these functions. This is useful to test error paths of code. If unsure, say N @@ -2079,6 +2032,41 @@ menuconfig RUNTIME_TESTING_MENU if RUNTIME_TESTING_MENU +config TEST_DHRY + tristate "Dhrystone benchmark test" + help + Enable this to include the Dhrystone 2.1 benchmark. This test + calculates the number of Dhrystones per second, and the number of + DMIPS (Dhrystone MIPS) obtained when the Dhrystone score is divided + by 1757 (the number of Dhrystones per second obtained on the VAX + 11/780, nominally a 1 MIPS machine). + + 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. + + Run once during kernel boot: + + test_dhry.run + + Set number of iterations from kernel command line: + + test_dhry.iterations=<n> + + Set number of iterations from userspace: + + echo <n> > /sys/module/test_dhry/parameters/iterations + + Trigger manual run from userspace: + + echo y > /sys/module/test_dhry/parameters/run + + If the number of iterations is <= 0, the test will devise a suitable + number of iterations (test runs for at least 2s) automatically. + This process takes ca. 4s. + + If unsure, say N. + config LKDTM tristate "Linux Kernel Dump Test Tool Module" depends on DEBUG_FS @@ -2496,6 +2484,19 @@ config LIST_KUNIT_TEST If unsure, say N. +config HASHTABLE_KUNIT_TEST + tristate "KUnit Test for Kernel Hashtable structures" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + This builds the hashtable KUnit test suite. + It tests the basic functionality of the API defined in + include/linux/hashtable.h. For more information on KUnit and + unit tests in general please refer to the KUnit documentation + in Documentation/dev-tools/kunit/. + + If unsure, say N. + config LINEAR_RANGES_TEST tristate "KUnit test for linear_ranges" depends on KUNIT @@ -2566,6 +2567,15 @@ config MEMCPY_KUNIT_TEST If unsure, say N. +config MEMCPY_SLOW_KUNIT_TEST + bool "Include exhaustive memcpy tests" + depends on MEMCPY_KUNIT_TEST + default y + help + Some memcpy tests are quite exhaustive in checking for overlaps + and bit ranges. These can be very slow, so they are split out + as a separate config, in case they need to be disabled. + config IS_SIGNED_TYPE_KUNIT_TEST tristate "Test is_signed_type() macro" if !KUNIT_ALL_TESTS depends on KUNIT @@ -2872,6 +2882,4 @@ config RUST_BUILD_ASSERT_ALLOW endmenu # "Rust" -source "Documentation/Kconfig" - endmenu # Kernel hacking diff --git a/lib/Kconfig.kcsan b/lib/Kconfig.kcsan index cb926b393556..609ddfc73de5 100644 --- a/lib/Kconfig.kcsan +++ b/lib/Kconfig.kcsan @@ -195,7 +195,7 @@ config KCSAN_WEAK_MEMORY Enable support for modeling a subset of weak memory, which allows detecting a subset of data races due to missing memory barriers. - Depends on KCSAN_STRICT, because the options strenghtening certain + Depends on KCSAN_STRICT, because the options strengthening certain plain accesses by default (depending on !KCSAN_STRICT) reduce the ability to detect any data races invoving reordered accesses, in particular reordered writes. diff --git a/lib/Makefile b/lib/Makefile index 4d9461bfea42..469be6240523 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -57,6 +57,8 @@ obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o obj-y += kstrtox.o obj-$(CONFIG_FIND_BIT_BENCHMARK) += find_bit_benchmark.o obj-$(CONFIG_TEST_BPF) += test_bpf.o +test_dhry-objs := dhry_1.o dhry_2.o dhry_run.o +obj-$(CONFIG_TEST_DHRY) += test_dhry.o obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o obj-$(CONFIG_TEST_BITOPS) += test_bitops.o CFLAGS_test_bitops.o += -Werror @@ -126,6 +128,14 @@ CFLAGS_test_fpu.o += $(FPU_CFLAGS) obj-$(CONFIG_TEST_LIVEPATCH) += livepatch/ obj-$(CONFIG_KUNIT) += kunit/ +# Include the KUnit hooks unconditionally. They'll compile to nothing if +# CONFIG_KUNIT=n, otherwise will be a small table of static data (static key, +# function pointers) which need to be built-in even when KUnit is a module. +ifeq ($(CONFIG_KUNIT), m) +obj-y += kunit/hooks.o +else +obj-$(CONFIG_KUNIT) += kunit/hooks.o +endif ifeq ($(CONFIG_DEBUG_KOBJECT),y) CFLAGS_kobject.o += -DDEBUG @@ -340,9 +350,7 @@ quiet_cmd_build_OID_registry = GEN $@ clean-files += oid_registry_data.c obj-$(CONFIG_UCS2_STRING) += ucs2_string.o -ifneq ($(CONFIG_UBSAN_TRAP),y) obj-$(CONFIG_UBSAN) += ubsan.o -endif UBSAN_SANITIZE_ubsan.o := n KASAN_SANITIZE_ubsan.o := n @@ -353,6 +361,8 @@ obj-$(CONFIG_SBITMAP) += sbitmap.o obj-$(CONFIG_PARMAN) += parman.o +obj-y += group_cpus.o + # GCC library routines obj-$(CONFIG_GENERIC_LIB_ASHLDI3) += ashldi3.o obj-$(CONFIG_GENERIC_LIB_ASHRDI3) += ashrdi3.o @@ -369,6 +379,7 @@ obj-$(CONFIG_PLDMFW) += pldmfw/ CFLAGS_bitfield_kunit.o := $(DISABLE_STRUCTLEAK_PLUGIN) obj-$(CONFIG_BITFIELD_KUNIT) += bitfield_kunit.o obj-$(CONFIG_LIST_KUNIT_TEST) += list-test.o +obj-$(CONFIG_HASHTABLE_KUNIT_TEST) += hashtable_test.o obj-$(CONFIG_LINEAR_RANGES_TEST) += test_linear_ranges.o obj-$(CONFIG_BITS_TEST) += test_bits.o obj-$(CONFIG_CMDLINE_KUNIT_TEST) += cmdline_kunit.o diff --git a/lib/bug.c b/lib/bug.c index c223a2575b72..e0ff21989990 100644 --- a/lib/bug.c +++ b/lib/bug.c @@ -47,6 +47,7 @@ #include <linux/sched.h> #include <linux/rculist.h> #include <linux/ftrace.h> +#include <linux/context_tracking.h> extern struct bug_entry __start___bug_table[], __stop___bug_table[]; @@ -153,7 +154,7 @@ struct bug_entry *find_bug(unsigned long bugaddr) return module_find_bug(bugaddr); } -enum bug_trap_type report_bug(unsigned long bugaddr, struct pt_regs *regs) +static enum bug_trap_type __report_bug(unsigned long bugaddr, struct pt_regs *regs) { struct bug_entry *bug; const char *file; @@ -209,6 +210,18 @@ enum bug_trap_type report_bug(unsigned long bugaddr, struct pt_regs *regs) return BUG_TRAP_TYPE_BUG; } +enum bug_trap_type report_bug(unsigned long bugaddr, struct pt_regs *regs) +{ + enum bug_trap_type ret; + bool rcu = false; + + rcu = warn_rcu_enter(); + ret = __report_bug(bugaddr, regs); + warn_rcu_exit(rcu); + + return ret; +} + static void clear_once_table(struct bug_entry *start, struct bug_entry *end) { struct bug_entry *bug; diff --git a/lib/cpumask.c b/lib/cpumask.c index c7c392514fd3..e7258836b60b 100644 --- a/lib/cpumask.c +++ b/lib/cpumask.c @@ -110,15 +110,33 @@ void __init free_bootmem_cpumask_var(cpumask_var_t mask) #endif /** - * cpumask_local_spread - select the i'th cpu with local numa cpu's first + * cpumask_local_spread - select the i'th cpu based on NUMA distances * @i: index number * @node: local numa_node * - * This function selects an online CPU according to a numa aware policy; - * local cpus are returned first, followed by non-local ones, then it - * wraps around. + * Returns online CPU according to a numa aware policy; local cpus are returned + * first, followed by non-local ones, then it wraps around. * - * It's not very efficient, but useful for setup. + * For those who wants to enumerate all CPUs based on their NUMA distances, + * i.e. call this function in a loop, like: + * + * for (i = 0; i < num_online_cpus(); i++) { + * cpu = cpumask_local_spread(i, node); + * do_something(cpu); + * } + * + * There's a better alternative based on for_each()-like iterators: + * + * for_each_numa_hop_mask(mask, node) { + * for_each_cpu_andnot(cpu, mask, prev) + * do_something(cpu); + * prev = mask; + * } + * + * It's simpler and more verbose than above. Complexity of iterator-based + * enumeration is O(sched_domains_numa_levels * nr_cpu_ids), while + * cpumask_local_spread() when called for each cpu is + * O(sched_domains_numa_levels * nr_cpu_ids * log(nr_cpu_ids)). */ unsigned int cpumask_local_spread(unsigned int i, int node) { @@ -127,24 +145,12 @@ unsigned int cpumask_local_spread(unsigned int i, int node) /* Wrap: we always want a cpu. */ i %= num_online_cpus(); - if (node == NUMA_NO_NODE) { - cpu = cpumask_nth(i, cpu_online_mask); - if (cpu < nr_cpu_ids) - return cpu; - } else { - /* NUMA first. */ - cpu = cpumask_nth_and(i, cpu_online_mask, cpumask_of_node(node)); - if (cpu < nr_cpu_ids) - return cpu; - - i -= cpumask_weight_and(cpu_online_mask, cpumask_of_node(node)); - - /* Skip NUMA nodes, done above. */ - cpu = cpumask_nth_andnot(i, cpu_online_mask, cpumask_of_node(node)); - if (cpu < nr_cpu_ids) - return cpu; - } - BUG(); + cpu = (node == NUMA_NO_NODE) ? + cpumask_nth(i, cpu_online_mask) : + sched_numa_find_nth_cpu(cpu_online_mask, i, node); + + WARN_ON(cpu >= nr_cpu_ids); + return cpu; } EXPORT_SYMBOL(cpumask_local_spread); diff --git a/lib/crypto/blake2s-selftest.c b/lib/crypto/blake2s-selftest.c index 7d77dea15587..d0634ed6a937 100644 --- a/lib/crypto/blake2s-selftest.c +++ b/lib/crypto/blake2s-selftest.c @@ -545,7 +545,7 @@ static const u8 blake2s_testvecs[][BLAKE2S_HASH_SIZE] __initconst = { 0xd6, 0x98, 0x6b, 0x07, 0x10, 0x65, 0x52, 0x65, }, }; -bool __init blake2s_selftest(void) +static bool __init noinline_for_stack blake2s_digest_test(void) { u8 key[BLAKE2S_KEY_SIZE]; u8 buf[ARRAY_SIZE(blake2s_testvecs)]; @@ -589,11 +589,20 @@ bool __init blake2s_selftest(void) } } + return success; +} + +static bool __init noinline_for_stack blake2s_random_test(void) +{ + struct blake2s_state state; + bool success = true; + int i, l; + for (i = 0; i < 32; ++i) { enum { TEST_ALIGNMENT = 16 }; - u8 unaligned_block[BLAKE2S_BLOCK_SIZE + TEST_ALIGNMENT - 1] + u8 blocks[BLAKE2S_BLOCK_SIZE * 2 + TEST_ALIGNMENT - 1] __aligned(TEST_ALIGNMENT); - u8 blocks[BLAKE2S_BLOCK_SIZE * 2]; + u8 *unaligned_block = blocks + BLAKE2S_BLOCK_SIZE; struct blake2s_state state1, state2; get_random_bytes(blocks, sizeof(blocks)); @@ -630,3 +639,13 @@ bool __init blake2s_selftest(void) return success; } + +bool __init blake2s_selftest(void) +{ + bool success; + + success = blake2s_digest_test(); + success &= blake2s_random_test(); + + return success; +} diff --git a/lib/dec_and_lock.c b/lib/dec_and_lock.c index 9555b68bb774..1dcca8f2e194 100644 --- a/lib/dec_and_lock.c +++ b/lib/dec_and_lock.c @@ -49,3 +49,34 @@ int _atomic_dec_and_lock_irqsave(atomic_t *atomic, spinlock_t *lock, return 0; } EXPORT_SYMBOL(_atomic_dec_and_lock_irqsave); + +int _atomic_dec_and_raw_lock(atomic_t *atomic, raw_spinlock_t *lock) +{ + /* Subtract 1 from counter unless that drops it to 0 (ie. it was 1) */ + if (atomic_add_unless(atomic, -1, 1)) + return 0; + + /* Otherwise do it the slow way */ + raw_spin_lock(lock); + if (atomic_dec_and_test(atomic)) + return 1; + raw_spin_unlock(lock); + return 0; +} +EXPORT_SYMBOL(_atomic_dec_and_raw_lock); + +int _atomic_dec_and_raw_lock_irqsave(atomic_t *atomic, raw_spinlock_t *lock, + unsigned long *flags) +{ + /* Subtract 1 from counter unless that drops it to 0 (ie. it was 1) */ + if (atomic_add_unless(atomic, -1, 1)) + return 0; + + /* Otherwise do it the slow way */ + raw_spin_lock_irqsave(lock, *flags); + if (atomic_dec_and_test(atomic)) + return 1; + raw_spin_unlock_irqrestore(lock, *flags); + return 0; +} +EXPORT_SYMBOL(_atomic_dec_and_raw_lock_irqsave); diff --git a/lib/dhry.h b/lib/dhry.h new file mode 100644 index 000000000000..e1a4db8e252c --- /dev/null +++ b/lib/dhry.h @@ -0,0 +1,358 @@ +/* SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause) */ +/* + **************************************************************************** + * + * "DHRYSTONE" Benchmark Program + * ----------------------------- + * + * Version: C, Version 2.1 + * + * File: dhry.h (part 1 of 3) + * + * Date: May 25, 1988 + * + * Author: Reinhold P. Weicker + * Siemens AG, AUT E 51 + * Postfach 3220 + * 8520 Erlangen + * Germany (West) + * Phone: [+49]-9131-7-20330 + * (8-17 Central European Time) + * Usenet: ..!mcsun!unido!estevax!weicker + * + * Original Version (in Ada) published in + * "Communications of the ACM" vol. 27., no. 10 (Oct. 1984), + * pp. 1013 - 1030, together with the statistics + * on which the distribution of statements etc. is based. + * + * In this C version, the following C library functions are used: + * - strcpy, strcmp (inside the measurement loop) + * - printf, scanf (outside the measurement loop) + * In addition, Berkeley UNIX system calls "times ()" or "time ()" + * are used for execution time measurement. For measurements + * on other systems, these calls have to be changed. + * + * Collection of Results: + * Reinhold Weicker (address see above) and + * + * Rick Richardson + * PC Research. Inc. + * 94 Apple Orchard Drive + * Tinton Falls, NJ 07724 + * Phone: (201) 389-8963 (9-17 EST) + * Usenet: ...!uunet!pcrat!rick + * + * Please send results to Rick Richardson and/or Reinhold Weicker. + * Complete information should be given on hardware and software used. + * Hardware information includes: Machine type, CPU, type and size + * of caches; for microprocessors: clock frequency, memory speed + * (number of wait states). + * Software information includes: Compiler (and runtime library) + * manufacturer and version, compilation switches, OS version. + * The Operating System version may give an indication about the + * compiler; Dhrystone itself performs no OS calls in the measurement loop. + * + * The complete output generated by the program should be mailed + * such that at least some checks for correctness can be made. + * + *************************************************************************** + * + * History: This version C/2.1 has been made for two reasons: + * + * 1) There is an obvious need for a common C version of + * Dhrystone, since C is at present the most popular system + * programming language for the class of processors + * (microcomputers, minicomputers) where Dhrystone is used most. + * There should be, as far as possible, only one C version of + * Dhrystone such that results can be compared without + * restrictions. In the past, the C versions distributed + * by Rick Richardson (Version 1.1) and by Reinhold Weicker + * had small (though not significant) differences. + * + * 2) As far as it is possible without changes to the Dhrystone + * statistics, optimizing compilers should be prevented from + * removing significant statements. + * + * This C version has been developed in cooperation with + * Rick Richardson (Tinton Falls, NJ), it incorporates many + * ideas from the "Version 1.1" distributed previously by + * him over the UNIX network Usenet. + * I also thank Chaim Benedelac (National Semiconductor), + * David Ditzel (SUN), Earl Killian and John Mashey (MIPS), + * Alan Smith and Rafael Saavedra-Barrera (UC at Berkeley) + * for their help with comments on earlier versions of the + * benchmark. + * + * Changes: In the initialization part, this version follows mostly + * Rick Richardson's version distributed via Usenet, not the + * version distributed earlier via floppy disk by Reinhold Weicker. + * As a concession to older compilers, names have been made + * unique within the first 8 characters. + * Inside the measurement loop, this version follows the + * version previously distributed by Reinhold Weicker. + * + * At several places in the benchmark, code has been added, + * but within the measurement loop only in branches that + * are not executed. The intention is that optimizing compilers + * should be prevented from moving code out of the measurement + * loop, or from removing code altogether. Since the statements + * that are executed within the measurement loop have NOT been + * changed, the numbers defining the "Dhrystone distribution" + * (distribution of statements, operand types and locality) + * still hold. Except for sophisticated optimizing compilers, + * execution times for this version should be the same as + * for previous versions. + * + * Since it has proven difficult to subtract the time for the + * measurement loop overhead in a correct way, the loop check + * has been made a part of the benchmark. This does have + * an impact - though a very minor one - on the distribution + * statistics which have been updated for this version. + * + * All changes within the measurement loop are described + * and discussed in the companion paper "Rationale for + * Dhrystone version 2". + * + * Because of the self-imposed limitation that the order and + * distribution of the executed statements should not be + * changed, there are still cases where optimizing compilers + * may not generate code for some statements. To a certain + * degree, this is unavoidable for small synthetic benchmarks. + * Users of the benchmark are advised to check code listings + * whether code is generated for all statements of Dhrystone. + * + * Version 2.1 is identical to version 2.0 distributed via + * the UNIX network Usenet in March 1988 except that it corrects + * some minor deficiencies that were found by users of version 2.0. + * The only change within the measurement loop is that a + * non-executed "else" part was added to the "if" statement in + * Func_3, and a non-executed "else" part removed from Proc_3. + * + *************************************************************************** + * + * Compilation model and measurement (IMPORTANT): + * + * This C version of Dhrystone consists of three files: + * - dhry.h (this file, containing global definitions and comments) + * - dhry_1.c (containing the code corresponding to Ada package Pack_1) + * - dhry_2.c (containing the code corresponding to Ada package Pack_2) + * + * The following "ground rules" apply for measurements: + * - Separate compilation + * - No procedure merging + * - Otherwise, compiler optimizations are allowed but should be indicated + * - Default results are those without register declarations + * See the companion paper "Rationale for Dhrystone Version 2" for a more + * detailed discussion of these ground rules. + * + * For 16-Bit processors (e.g. 80186, 80286), times for all compilation + * models ("small", "medium", "large" etc.) should be given if possible, + * together with a definition of these models for the compiler system used. + * + ************************************************************************** + * + * Dhrystone (C version) statistics: + * + * [Comment from the first distribution, updated for version 2. + * Note that because of language differences, the numbers are slightly + * different from the Ada version.] + * + * The following program contains statements of a high level programming + * language (here: C) in a distribution considered representative: + * + * assignments 52 (51.0 %) + * control statements 33 (32.4 %) + * procedure, function calls 17 (16.7 %) + * + * 103 statements are dynamically executed. The program is balanced with + * respect to the three aspects: + * + * - statement type + * - operand type + * - operand locality + * operand global, local, parameter, or constant. + * + * The combination of these three aspects is balanced only approximately. + * + * 1. Statement Type: + * ----------------- number + * + * V1 = V2 9 + * (incl. V1 = F(..) + * V = Constant 12 + * Assignment, 7 + * with array element + * Assignment, 6 + * with record component + * -- + * 34 34 + * + * X = Y +|-|"&&"|"|" Z 5 + * X = Y +|-|"==" Constant 6 + * X = X +|- 1 3 + * X = Y *|/ Z 2 + * X = Expression, 1 + * two operators + * X = Expression, 1 + * three operators + * -- + * 18 18 + * + * if .... 14 + * with "else" 7 + * without "else" 7 + * executed 3 + * not executed 4 + * for ... 7 | counted every time + * while ... 4 | the loop condition + * do ... while 1 | is evaluated + * switch ... 1 + * break 1 + * declaration with 1 + * initialization + * -- + * 34 34 + * + * P (...) procedure call 11 + * user procedure 10 + * library procedure 1 + * X = F (...) + * function call 6 + * user function 5 + * library function 1 + * -- + * 17 17 + * --- + * 103 + * + * The average number of parameters in procedure or function calls + * is 1.82 (not counting the function values as implicit parameters). + * + * + * 2. Operators + * ------------ + * number approximate + * percentage + * + * Arithmetic 32 50.8 + * + * + 21 33.3 + * - 7 11.1 + * * 3 4.8 + * / (int div) 1 1.6 + * + * Comparison 27 42.8 + * + * == 9 14.3 + * /= 4 6.3 + * > 1 1.6 + * < 3 4.8 + * >= 1 1.6 + * <= 9 14.3 + * + * Logic 4 6.3 + * + * && (AND-THEN) 1 1.6 + * | (OR) 1 1.6 + * ! (NOT) 2 3.2 + * + * -- ----- + * 63 100.1 + * + * + * 3. Operand Type (counted once per operand reference): + * --------------- + * number approximate + * percentage + * + * Integer 175 72.3 % + * Character 45 18.6 % + * Pointer 12 5.0 % + * String30 6 2.5 % + * Array 2 0.8 % + * Record 2 0.8 % + * --- ------- + * 242 100.0 % + * + * When there is an access path leading to the final operand (e.g. a record + * component), only the final data type on the access path is counted. + * + * + * 4. Operand Locality: + * ------------------- + * number approximate + * percentage + * + * local variable 114 47.1 % + * global variable 22 9.1 % + * parameter 45 18.6 % + * value 23 9.5 % + * reference 22 9.1 % + * function result 6 2.5 % + * constant 55 22.7 % + * --- ------- + * 242 100.0 % + * + * + * The program does not compute anything meaningful, but it is syntactically + * and semantically correct. All variables have a value assigned to them + * before they are used as a source operand. + * + * There has been no explicit effort to account for the effects of a + * cache, or to balance the use of long or short displacements for code or + * data. + * + *************************************************************************** + */ + +typedef enum { + Ident_1, + Ident_2, + Ident_3, + Ident_4, + Ident_5 +} Enumeration; /* for boolean and enumeration types in Ada, Pascal */ + +/* General definitions: */ + +typedef int One_Thirty; +typedef int One_Fifty; +typedef char Capital_Letter; +typedef int Boolean; +typedef char Str_30[31]; +typedef int Arr_1_Dim[50]; +typedef int Arr_2_Dim[50][50]; + +typedef struct record { + struct record *Ptr_Comp; + Enumeration Discr; + union { + struct { + Enumeration Enum_Comp; + int Int_Comp; + char Str_Comp[31]; + } var_1; + struct { + Enumeration E_Comp_2; + char Str_2_Comp[31]; + } var_2; + struct { + char Ch_1_Comp; + char Ch_2_Comp; + } var_3; + } variant; +} Rec_Type, *Rec_Pointer; + + +extern int Int_Glob; +extern char Ch_1_Glob; + +void Proc_6(Enumeration Enum_Val_Par, Enumeration *Enum_Ref_Par); +void Proc_7(One_Fifty Int_1_Par_Val, One_Fifty Int_2_Par_Val, + One_Fifty *Int_Par_Ref); +void Proc_8(Arr_1_Dim Arr_1_Par_Ref, Arr_2_Dim Arr_2_Par_Ref, + int Int_1_Par_Val, int Int_2_Par_Val); +Enumeration Func_1(Capital_Letter Ch_1_Par_Val, Capital_Letter Ch_2_Par_Val); +Boolean Func_2(Str_30 Str_1_Par_Ref, Str_30 Str_2_Par_Ref); + +int dhry(int n); diff --git a/lib/dhry_1.c b/lib/dhry_1.c new file mode 100644 index 000000000000..83247106824c --- /dev/null +++ b/lib/dhry_1.c @@ -0,0 +1,283 @@ +// SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause) +/* + **************************************************************************** + * + * "DHRYSTONE" Benchmark Program + * ----------------------------- + * + * Version: C, Version 2.1 + * + * File: dhry_1.c (part 2 of 3) + * + * Date: May 25, 1988 + * + * Author: Reinhold P. Weicker + * + **************************************************************************** + */ + +#include "dhry.h" + +#include <linux/ktime.h> +#include <linux/slab.h> +#include <linux/string.h> + +/* Global Variables: */ + +int Int_Glob; +char Ch_1_Glob; + +static Rec_Pointer Ptr_Glob, Next_Ptr_Glob; +static Boolean Bool_Glob; +static char Ch_2_Glob; +static int Arr_1_Glob[50]; +static int Arr_2_Glob[50][50]; + +static void Proc_3(Rec_Pointer *Ptr_Ref_Par) +/******************/ +/* executed once */ +/* Ptr_Ref_Par becomes Ptr_Glob */ +{ + if (Ptr_Glob) { + /* then, executed */ + *Ptr_Ref_Par = Ptr_Glob->Ptr_Comp; + } + Proc_7(10, Int_Glob, &Ptr_Glob->variant.var_1.Int_Comp); +} /* Proc_3 */ + + +static void Proc_1(Rec_Pointer Ptr_Val_Par) +/******************/ +/* executed once */ +{ + Rec_Pointer Next_Record = Ptr_Val_Par->Ptr_Comp; + /* == Ptr_Glob_Next */ + /* Local variable, initialized with Ptr_Val_Par->Ptr_Comp, */ + /* corresponds to "rename" in Ada, "with" in Pascal */ + + *Ptr_Val_Par->Ptr_Comp = *Ptr_Glob; + Ptr_Val_Par->variant.var_1.Int_Comp = 5; + Next_Record->variant.var_1.Int_Comp = + Ptr_Val_Par->variant.var_1.Int_Comp; + Next_Record->Ptr_Comp = Ptr_Val_Par->Ptr_Comp; + Proc_3(&Next_Record->Ptr_Comp); + /* Ptr_Val_Par->Ptr_Comp->Ptr_Comp == Ptr_Glob->Ptr_Comp */ + if (Next_Record->Discr == Ident_1) { + /* then, executed */ + Next_Record->variant.var_1.Int_Comp = 6; + Proc_6(Ptr_Val_Par->variant.var_1.Enum_Comp, + &Next_Record->variant.var_1.Enum_Comp); + Next_Record->Ptr_Comp = Ptr_Glob->Ptr_Comp; + Proc_7(Next_Record->variant.var_1.Int_Comp, 10, + &Next_Record->variant.var_1.Int_Comp); + } else { + /* not executed */ + *Ptr_Val_Par = *Ptr_Val_Par->Ptr_Comp; + } +} /* Proc_1 */ + + +static void Proc_2(One_Fifty *Int_Par_Ref) +/******************/ +/* executed once */ +/* *Int_Par_Ref == 1, becomes 4 */ +{ + One_Fifty Int_Loc; + Enumeration Enum_Loc; + + Int_Loc = *Int_Par_Ref + 10; + do { + /* executed once */ + if (Ch_1_Glob == 'A') { + /* then, executed */ + Int_Loc -= 1; + *Int_Par_Ref = Int_Loc - Int_Glob; + Enum_Loc = Ident_1; + } /* if */ + } while (Enum_Loc != Ident_1); /* true */ +} /* Proc_2 */ + + +static void Proc_4(void) +/*******/ +/* executed once */ +{ + Boolean Bool_Loc; + + Bool_Loc = Ch_1_Glob == 'A'; + Bool_Glob = Bool_Loc | Bool_Glob; + Ch_2_Glob = 'B'; +} /* Proc_4 */ + + +static void Proc_5(void) +/*******/ +/* executed once */ +{ + Ch_1_Glob = 'A'; + Bool_Glob = false; +} /* Proc_5 */ + + +int dhry(int n) +/*****/ + + /* main program, corresponds to procedures */ + /* Main and Proc_0 in the Ada version */ +{ + One_Fifty Int_1_Loc; + One_Fifty Int_2_Loc; + One_Fifty Int_3_Loc; + char Ch_Index; + Enumeration Enum_Loc; + Str_30 Str_1_Loc; + Str_30 Str_2_Loc; + int Run_Index; + int Number_Of_Runs; + ktime_t Begin_Time, End_Time; + u32 User_Time; + + /* Initializations */ + + Next_Ptr_Glob = (Rec_Pointer)kzalloc(sizeof(Rec_Type), GFP_KERNEL); + Ptr_Glob = (Rec_Pointer)kzalloc(sizeof(Rec_Type), GFP_KERNEL); + + Ptr_Glob->Ptr_Comp = Next_Ptr_Glob; + Ptr_Glob->Discr = Ident_1; + Ptr_Glob->variant.var_1.Enum_Comp = Ident_3; + Ptr_Glob->variant.var_1.Int_Comp = 40; + strcpy(Ptr_Glob->variant.var_1.Str_Comp, + "DHRYSTONE PROGRAM, SOME STRING"); + strcpy(Str_1_Loc, "DHRYSTONE PROGRAM, 1'ST STRING"); + + Arr_2_Glob[8][7] = 10; + /* Was missing in published program. Without this statement, */ + /* Arr_2_Glob[8][7] would have an undefined value. */ + /* Warning: With 16-Bit processors and Number_Of_Runs > 32000, */ + /* overflow may occur for this array element. */ + + pr_debug("Dhrystone Benchmark, Version 2.1 (Language: C)\n"); + + Number_Of_Runs = n; + + pr_debug("Execution starts, %d runs through Dhrystone\n", + Number_Of_Runs); + + /***************/ + /* Start timer */ + /***************/ + + Begin_Time = ktime_get(); + + for (Run_Index = 1; Run_Index <= Number_Of_Runs; ++Run_Index) { + Proc_5(); + Proc_4(); + /* Ch_1_Glob == 'A', Ch_2_Glob == 'B', Bool_Glob == true */ + Int_1_Loc = 2; + Int_2_Loc = 3; + strcpy(Str_2_Loc, "DHRYSTONE PROGRAM, 2'ND STRING"); + Enum_Loc = Ident_2; + Bool_Glob = !Func_2(Str_1_Loc, Str_2_Loc); + /* Bool_Glob == 1 */ + while (Int_1_Loc < Int_2_Loc) { + /* loop body executed once */ + Int_3_Loc = 5 * Int_1_Loc - Int_2_Loc; + /* Int_3_Loc == 7 */ + Proc_7(Int_1_Loc, Int_2_Loc, &Int_3_Loc); + /* Int_3_Loc == 7 */ + Int_1_Loc += 1; + } /* while */ + /* Int_1_Loc == 3, Int_2_Loc == 3, Int_3_Loc == 7 */ + Proc_8(Arr_1_Glob, Arr_2_Glob, Int_1_Loc, Int_3_Loc); + /* Int_Glob == 5 */ + Proc_1(Ptr_Glob); + for (Ch_Index = 'A'; Ch_Index <= Ch_2_Glob; ++Ch_Index) { + /* loop body executed twice */ + if (Enum_Loc == Func_1(Ch_Index, 'C')) { + /* then, not executed */ + Proc_6(Ident_1, &Enum_Loc); + strcpy(Str_2_Loc, "DHRYSTONE PROGRAM, 3'RD STRING"); + Int_2_Loc = Run_Index; + Int_Glob = Run_Index; + } + } + /* Int_1_Loc == 3, Int_2_Loc == 3, Int_3_Loc == 7 */ + Int_2_Loc = Int_2_Loc * Int_1_Loc; + Int_1_Loc = Int_2_Loc / Int_3_Loc; + Int_2_Loc = 7 * (Int_2_Loc - Int_3_Loc) - Int_1_Loc; + /* Int_1_Loc == 1, Int_2_Loc == 13, Int_3_Loc == 7 */ + Proc_2(&Int_1_Loc); + /* Int_1_Loc == 5 */ + + } /* loop "for Run_Index" */ + + /**************/ + /* Stop timer */ + /**************/ + + End_Time = ktime_get(); + +#define dhry_assert_int_eq(val, expected) \ + if (val != expected) \ + pr_err("%s: %d (FAIL, expected %d)\n", #val, val, \ + expected); \ + else \ + pr_debug("%s: %d (OK)\n", #val, val) + +#define dhry_assert_char_eq(val, expected) \ + if (val != expected) \ + pr_err("%s: %c (FAIL, expected %c)\n", #val, val, \ + expected); \ + else \ + pr_debug("%s: %c (OK)\n", #val, val) + +#define dhry_assert_string_eq(val, expected) \ + if (strcmp(val, expected)) \ + pr_err("%s: %s (FAIL, expected %s)\n", #val, val, \ + expected); \ + else \ + pr_debug("%s: %s (OK)\n", #val, val) + + pr_debug("Execution ends\n"); + pr_debug("Final values of the variables used in the benchmark:\n"); + dhry_assert_int_eq(Int_Glob, 5); + dhry_assert_int_eq(Bool_Glob, 1); + dhry_assert_char_eq(Ch_1_Glob, 'A'); + dhry_assert_char_eq(Ch_2_Glob, 'B'); + dhry_assert_int_eq(Arr_1_Glob[8], 7); + dhry_assert_int_eq(Arr_2_Glob[8][7], Number_Of_Runs + 10); + pr_debug("Ptr_Comp: %px\n", Ptr_Glob->Ptr_Comp); + dhry_assert_int_eq(Ptr_Glob->Discr, 0); + dhry_assert_int_eq(Ptr_Glob->variant.var_1.Enum_Comp, 2); + dhry_assert_int_eq(Ptr_Glob->variant.var_1.Int_Comp, 17); + dhry_assert_string_eq(Ptr_Glob->variant.var_1.Str_Comp, + "DHRYSTONE PROGRAM, SOME STRING"); + if (Next_Ptr_Glob->Ptr_Comp != Ptr_Glob->Ptr_Comp) + pr_err("Next_Ptr_Glob->Ptr_Comp: %px (expected %px)\n", + Next_Ptr_Glob->Ptr_Comp, Ptr_Glob->Ptr_Comp); + else + pr_debug("Next_Ptr_Glob->Ptr_Comp: %px\n", + Next_Ptr_Glob->Ptr_Comp); + dhry_assert_int_eq(Next_Ptr_Glob->Discr, 0); + dhry_assert_int_eq(Next_Ptr_Glob->variant.var_1.Enum_Comp, 1); + dhry_assert_int_eq(Next_Ptr_Glob->variant.var_1.Int_Comp, 18); + dhry_assert_string_eq(Next_Ptr_Glob->variant.var_1.Str_Comp, + "DHRYSTONE PROGRAM, SOME STRING"); + dhry_assert_int_eq(Int_1_Loc, 5); + dhry_assert_int_eq(Int_2_Loc, 13); + dhry_assert_int_eq(Int_3_Loc, 7); + dhry_assert_int_eq(Enum_Loc, 1); + 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)); + + kfree(Ptr_Glob); + kfree(Next_Ptr_Glob); + + /* Measurements should last at least 2 seconds */ + if (User_Time < 2 * MSEC_PER_SEC) + return -EAGAIN; + + return div_u64(mul_u32_u32(MSEC_PER_SEC, Number_Of_Runs), User_Time); +} diff --git a/lib/dhry_2.c b/lib/dhry_2.c new file mode 100644 index 000000000000..c19e661f37d3 --- /dev/null +++ b/lib/dhry_2.c @@ -0,0 +1,175 @@ +// SPDX-License-Identifier: (GPL-2.0-only OR BSD-2-Clause) +/* + **************************************************************************** + * + * "DHRYSTONE" Benchmark Program + * ----------------------------- + * + * Version: C, Version 2.1 + * + * File: dhry_2.c (part 3 of 3) + * + * Date: May 25, 1988 + * + * Author: Reinhold P. Weicker + * + **************************************************************************** + */ + +#include "dhry.h" + +#include <linux/string.h> + + +static Boolean Func_3(Enumeration Enum_Par_Val) +/***************************/ +/* executed once */ +/* Enum_Par_Val == Ident_3 */ +{ + Enumeration Enum_Loc; + + Enum_Loc = Enum_Par_Val; + if (Enum_Loc == Ident_3) { + /* then, executed */ + return true; + } else { + /* not executed */ + return false; + } +} /* Func_3 */ + + +void Proc_6(Enumeration Enum_Val_Par, Enumeration *Enum_Ref_Par) +/*********************************/ +/* executed once */ +/* Enum_Val_Par == Ident_3, Enum_Ref_Par becomes Ident_2 */ +{ + *Enum_Ref_Par = Enum_Val_Par; + if (!Func_3(Enum_Val_Par)) { + /* then, not executed */ + *Enum_Ref_Par = Ident_4; + } + switch (Enum_Val_Par) { + case Ident_1: + *Enum_Ref_Par = Ident_1; + break; + case Ident_2: + if (Int_Glob > 100) { + /* then */ + *Enum_Ref_Par = Ident_1; + } else { + *Enum_Ref_Par = Ident_4; + } + break; + case Ident_3: /* executed */ + *Enum_Ref_Par = Ident_2; + break; + case Ident_4: + break; + case Ident_5: + *Enum_Ref_Par = Ident_3; + break; + } /* switch */ +} /* Proc_6 */ + + +void Proc_7(One_Fifty Int_1_Par_Val, One_Fifty Int_2_Par_Val, One_Fifty *Int_Par_Ref) +/**********************************************/ +/* executed three times */ +/* first call: Int_1_Par_Val == 2, Int_2_Par_Val == 3, */ +/* Int_Par_Ref becomes 7 */ +/* second call: Int_1_Par_Val == 10, Int_2_Par_Val == 5, */ +/* Int_Par_Ref becomes 17 */ +/* third call: Int_1_Par_Val == 6, Int_2_Par_Val == 10, */ +/* Int_Par_Ref becomes 18 */ +{ + One_Fifty Int_Loc; + + Int_Loc = Int_1_Par_Val + 2; + *Int_Par_Ref = Int_2_Par_Val + Int_Loc; +} /* Proc_7 */ + + +void Proc_8(Arr_1_Dim Arr_1_Par_Ref, Arr_2_Dim Arr_2_Par_Ref, int Int_1_Par_Val, int Int_2_Par_Val) +/*********************************************************************/ +/* executed once */ +/* Int_Par_Val_1 == 3 */ +/* Int_Par_Val_2 == 7 */ +{ + One_Fifty Int_Index; + One_Fifty Int_Loc; + + Int_Loc = Int_1_Par_Val + 5; + Arr_1_Par_Ref[Int_Loc] = Int_2_Par_Val; + Arr_1_Par_Ref[Int_Loc+1] = Arr_1_Par_Ref[Int_Loc]; + Arr_1_Par_Ref[Int_Loc+30] = Int_Loc; + for (Int_Index = Int_Loc; Int_Index <= Int_Loc+1; ++Int_Index) + Arr_2_Par_Ref[Int_Loc][Int_Index] = Int_Loc; + Arr_2_Par_Ref[Int_Loc][Int_Loc-1] += 1; + Arr_2_Par_Ref[Int_Loc+20][Int_Loc] = Arr_1_Par_Ref[Int_Loc]; + Int_Glob = 5; +} /* Proc_8 */ + + +Enumeration Func_1(Capital_Letter Ch_1_Par_Val, Capital_Letter Ch_2_Par_Val) +/*************************************************/ +/* executed three times */ +/* first call: Ch_1_Par_Val == 'H', Ch_2_Par_Val == 'R' */ +/* second call: Ch_1_Par_Val == 'A', Ch_2_Par_Val == 'C' */ +/* third call: Ch_1_Par_Val == 'B', Ch_2_Par_Val == 'C' */ +{ + Capital_Letter Ch_1_Loc; + Capital_Letter Ch_2_Loc; + + Ch_1_Loc = Ch_1_Par_Val; + Ch_2_Loc = Ch_1_Loc; + if (Ch_2_Loc != Ch_2_Par_Val) { + /* then, executed */ + return Ident_1; + } else { + /* not executed */ + Ch_1_Glob = Ch_1_Loc; + return Ident_2; + } +} /* Func_1 */ + + +Boolean Func_2(Str_30 Str_1_Par_Ref, Str_30 Str_2_Par_Ref) +/*************************************************/ +/* executed once */ +/* Str_1_Par_Ref == "DHRYSTONE PROGRAM, 1'ST STRING" */ +/* Str_2_Par_Ref == "DHRYSTONE PROGRAM, 2'ND STRING" */ +{ + One_Thirty Int_Loc; + Capital_Letter Ch_Loc; + + Int_Loc = 2; + while (Int_Loc <= 2) { + /* loop body executed once */ + if (Func_1(Str_1_Par_Ref[Int_Loc], + Str_2_Par_Ref[Int_Loc+1]) == Ident_1) { + /* then, executed */ + Ch_Loc = 'A'; + Int_Loc += 1; + } + } /* if, while */ + if (Ch_Loc >= 'W' && Ch_Loc < 'Z') { + /* then, not executed */ + Int_Loc = 7; + } + if (Ch_Loc == 'R') { + /* then, not executed */ + return true; + } else { + /* executed */ + if (strcmp(Str_1_Par_Ref, Str_2_Par_Ref) > 0) { + /* then, not executed */ + Int_Loc += 7; + Int_Glob = Int_Loc; + return true; + } else { + /* executed */ + return false; + } + } /* if Ch_Loc */ +} /* Func_2 */ diff --git a/lib/dhry_run.c b/lib/dhry_run.c new file mode 100644 index 000000000000..f9d33efa6d09 --- /dev/null +++ b/lib/dhry_run.c @@ -0,0 +1,85 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * Dhrystone benchmark test module + * + * Copyright (C) 2022 Glider bv + */ + +#include "dhry.h" + +#include <linux/kernel.h> +#include <linux/module.h> +#include <linux/moduleparam.h> +#include <linux/mutex.h> +#include <linux/smp.h> + +#define DHRY_VAX 1757 + +static int dhry_run_set(const char *val, const struct kernel_param *kp); +static const struct kernel_param_ops run_ops = { + .flags = KERNEL_PARAM_OPS_FL_NOARG, + .set = dhry_run_set, +}; +static bool dhry_run; +module_param_cb(run, &run_ops, &dhry_run, 0200); +MODULE_PARM_DESC(run, "Run the test (default: false)"); + +static int iterations = -1; +module_param(iterations, int, 0644); +MODULE_PARM_DESC(iterations, + "Number of iterations through the benchmark (default: auto)"); + +static void dhry_benchmark(void) +{ + int i, n; + + if (iterations > 0) { + n = dhry(iterations); + goto report; + } + + for (i = DHRY_VAX; i > 0; i <<= 1) { + n = dhry(i); + if (n != -EAGAIN) + break; + } + +report: + if (n >= 0) + pr_info("CPU%u: Dhrystones per Second: %d (%d DMIPS)\n", + smp_processor_id(), n, n / DHRY_VAX); + else if (n == -EAGAIN) + pr_err("Please increase the number of iterations\n"); + else + pr_err("Dhrystone benchmark failed error %pe\n", ERR_PTR(n)); +} + +static int dhry_run_set(const char *val, const struct kernel_param *kp) +{ + int ret; + + if (val) { + ret = param_set_bool(val, kp); + if (ret) + return ret; + } else { + dhry_run = true; + } + + if (dhry_run && system_state == SYSTEM_RUNNING) + dhry_benchmark(); + + return 0; +} + +static int __init dhry_init(void) +{ + if (dhry_run) + dhry_benchmark(); + + return 0; +} +module_init(dhry_init); + +MODULE_AUTHOR("Geert Uytterhoeven <geert+renesas@glider.be>"); +MODULE_LICENSE("GPL"); diff --git a/lib/errname.c b/lib/errname.c index 05cbf731545f..67739b174a8c 100644 --- a/lib/errname.c +++ b/lib/errname.c @@ -21,6 +21,7 @@ static const char *names_0[] = { E(EADDRNOTAVAIL), E(EADV), E(EAFNOSUPPORT), + E(EAGAIN), /* EWOULDBLOCK */ E(EALREADY), E(EBADE), E(EBADF), @@ -31,15 +32,17 @@ static const char *names_0[] = { E(EBADSLT), E(EBFONT), E(EBUSY), -#ifdef ECANCELLED - E(ECANCELLED), -#endif + E(ECANCELED), /* ECANCELLED */ E(ECHILD), E(ECHRNG), E(ECOMM), E(ECONNABORTED), + E(ECONNREFUSED), /* EREFUSED */ E(ECONNRESET), + E(EDEADLK), /* EDEADLOCK */ +#if EDEADLK != EDEADLOCK /* mips, sparc, powerpc */ E(EDEADLOCK), +#endif E(EDESTADDRREQ), E(EDOM), E(EDOTDOT), @@ -166,14 +169,17 @@ static const char *names_0[] = { E(EUSERS), E(EXDEV), E(EXFULL), - - E(ECANCELED), /* ECANCELLED */ - E(EAGAIN), /* EWOULDBLOCK */ - E(ECONNREFUSED), /* EREFUSED */ - E(EDEADLK), /* EDEADLOCK */ }; #undef E +#ifdef EREFUSED /* parisc */ +static_assert(EREFUSED == ECONNREFUSED); +#endif +#ifdef ECANCELLED /* parisc */ +static_assert(ECANCELLED == ECANCELED); +#endif +static_assert(EAGAIN == EWOULDBLOCK); /* everywhere */ + #define E(err) [err - 512 + BUILD_BUG_ON_ZERO(err < 512 || err > 550)] = "-" #err static const char *names_512[] = { E(ERESTARTSYS), diff --git a/lib/error-inject.c b/lib/error-inject.c index 1afca1b1cdea..32c14770508e 100644 --- a/lib/error-inject.c +++ b/lib/error-inject.c @@ -40,7 +40,7 @@ bool within_error_injection_list(unsigned long addr) int get_injectable_error_type(unsigned long addr) { struct ei_entry *ent; - int ei_type = EI_ETYPE_NONE; + int ei_type = -EINVAL; mutex_lock(&ei_mutex); list_for_each_entry(ent, &error_injection_list, list) { diff --git a/lib/find_bit.c b/lib/find_bit.c index 18bc0a7ac8ee..c10920e66788 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -155,6 +155,15 @@ unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned l } EXPORT_SYMBOL(__find_nth_andnot_bit); +unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, + const unsigned long *addr2, + const unsigned long *addr3, + unsigned long size, unsigned long n) +{ + return FIND_NTH_BIT(addr1[idx] & addr2[idx] & ~addr3[idx], size, n); +} +EXPORT_SYMBOL(__find_nth_and_andnot_bit); + #ifndef find_next_and_bit unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long nbits, unsigned long start) diff --git a/lib/genalloc.c b/lib/genalloc.c index 00fc50d0a640..0c883d6fbd44 100644 --- a/lib/genalloc.c +++ b/lib/genalloc.c @@ -40,32 +40,30 @@ static inline size_t chunk_size(const struct gen_pool_chunk *chunk) return chunk->end_addr - chunk->start_addr + 1; } -static int set_bits_ll(unsigned long *addr, unsigned long mask_to_set) +static inline int +set_bits_ll(unsigned long *addr, unsigned long mask_to_set) { - unsigned long val, nval; + unsigned long val = READ_ONCE(*addr); - nval = *addr; do { - val = nval; if (val & mask_to_set) return -EBUSY; cpu_relax(); - } while ((nval = cmpxchg(addr, val, val | mask_to_set)) != val); + } while (!try_cmpxchg(addr, &val, val | mask_to_set)); return 0; } -static int clear_bits_ll(unsigned long *addr, unsigned long mask_to_clear) +static inline int +clear_bits_ll(unsigned long *addr, unsigned long mask_to_clear) { - unsigned long val, nval; + unsigned long val = READ_ONCE(*addr); - nval = *addr; do { - val = nval; if ((val & mask_to_clear) != mask_to_clear) return -EBUSY; cpu_relax(); - } while ((nval = cmpxchg(addr, val, val & ~mask_to_clear)) != val); + } while (!try_cmpxchg(addr, &val, val & ~mask_to_clear)); return 0; } diff --git a/lib/group_cpus.c b/lib/group_cpus.c new file mode 100644 index 000000000000..9c837a35fef7 --- /dev/null +++ b/lib/group_cpus.c @@ -0,0 +1,428 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2016 Thomas Gleixner. + * Copyright (C) 2016-2017 Christoph Hellwig. + */ +#include <linux/kernel.h> +#include <linux/slab.h> +#include <linux/cpu.h> +#include <linux/sort.h> +#include <linux/group_cpus.h> + +#ifdef CONFIG_SMP + +static void grp_spread_init_one(struct cpumask *irqmsk, struct cpumask *nmsk, + unsigned int cpus_per_grp) +{ + const struct cpumask *siblmsk; + int cpu, sibl; + + for ( ; cpus_per_grp > 0; ) { + cpu = cpumask_first(nmsk); + + /* Should not happen, but I'm too lazy to think about it */ + if (cpu >= nr_cpu_ids) + return; + + cpumask_clear_cpu(cpu, nmsk); + cpumask_set_cpu(cpu, irqmsk); + cpus_per_grp--; + + /* If the cpu has siblings, use them first */ + siblmsk = topology_sibling_cpumask(cpu); + for (sibl = -1; cpus_per_grp > 0; ) { + sibl = cpumask_next(sibl, siblmsk); + if (sibl >= nr_cpu_ids) + break; + if (!cpumask_test_and_clear_cpu(sibl, nmsk)) + continue; + cpumask_set_cpu(sibl, irqmsk); + cpus_per_grp--; + } + } +} + +static cpumask_var_t *alloc_node_to_cpumask(void) +{ + cpumask_var_t *masks; + int node; + + masks = kcalloc(nr_node_ids, sizeof(cpumask_var_t), GFP_KERNEL); + if (!masks) + return NULL; + + for (node = 0; node < nr_node_ids; node++) { + if (!zalloc_cpumask_var(&masks[node], GFP_KERNEL)) + goto out_unwind; + } + + return masks; + +out_unwind: + while (--node >= 0) + free_cpumask_var(masks[node]); + kfree(masks); + return NULL; +} + +static void free_node_to_cpumask(cpumask_var_t *masks) +{ + int node; + + for (node = 0; node < nr_node_ids; node++) + free_cpumask_var(masks[node]); + kfree(masks); +} + +static void build_node_to_cpumask(cpumask_var_t *masks) +{ + int cpu; + + for_each_possible_cpu(cpu) + cpumask_set_cpu(cpu, masks[cpu_to_node(cpu)]); +} + +static int get_nodes_in_cpumask(cpumask_var_t *node_to_cpumask, + const struct cpumask *mask, nodemask_t *nodemsk) +{ + int n, nodes = 0; + + /* Calculate the number of nodes in the supplied affinity mask */ + for_each_node(n) { + if (cpumask_intersects(mask, node_to_cpumask[n])) { + node_set(n, *nodemsk); + nodes++; + } + } + return nodes; +} + +struct node_groups { + unsigned id; + + union { + unsigned ngroups; + unsigned ncpus; + }; +}; + +static int ncpus_cmp_func(const void *l, const void *r) +{ + const struct node_groups *ln = l; + const struct node_groups *rn = r; + + return ln->ncpus - rn->ncpus; +} + +/* + * Allocate group number for each node, so that for each node: + * + * 1) the allocated number is >= 1 + * + * 2) the allocated number is <= active CPU number of this node + * + * The actual allocated total groups may be less than @numgrps when + * active total CPU number is less than @numgrps. + * + * Active CPUs means the CPUs in '@cpu_mask AND @node_to_cpumask[]' + * for each node. + */ +static void alloc_nodes_groups(unsigned int numgrps, + cpumask_var_t *node_to_cpumask, + const struct cpumask *cpu_mask, + const nodemask_t nodemsk, + struct cpumask *nmsk, + struct node_groups *node_groups) +{ + unsigned n, remaining_ncpus = 0; + + for (n = 0; n < nr_node_ids; n++) { + node_groups[n].id = n; + node_groups[n].ncpus = UINT_MAX; + } + + for_each_node_mask(n, nodemsk) { + unsigned ncpus; + + cpumask_and(nmsk, cpu_mask, node_to_cpumask[n]); + ncpus = cpumask_weight(nmsk); + + if (!ncpus) + continue; + remaining_ncpus += ncpus; + node_groups[n].ncpus = ncpus; + } + + numgrps = min_t(unsigned, remaining_ncpus, numgrps); + + sort(node_groups, nr_node_ids, sizeof(node_groups[0]), + ncpus_cmp_func, NULL); + + /* + * Allocate groups for each node according to the ratio of this + * node's nr_cpus to remaining un-assigned ncpus. 'numgrps' is + * bigger than number of active numa nodes. Always start the + * allocation from the node with minimized nr_cpus. + * + * This way guarantees that each active node gets allocated at + * least one group, and the theory is simple: over-allocation + * is only done when this node is assigned by one group, so + * other nodes will be allocated >= 1 groups, since 'numgrps' is + * bigger than number of numa nodes. + * + * One perfect invariant is that number of allocated groups for + * each node is <= CPU count of this node: + * + * 1) suppose there are two nodes: A and B + * ncpu(X) is CPU count of node X + * grps(X) is the group count allocated to node X via this + * algorithm + * + * ncpu(A) <= ncpu(B) + * ncpu(A) + ncpu(B) = N + * grps(A) + grps(B) = G + * + * grps(A) = max(1, round_down(G * ncpu(A) / N)) + * grps(B) = G - grps(A) + * + * both N and G are integer, and 2 <= G <= N, suppose + * G = N - delta, and 0 <= delta <= N - 2 + * + * 2) obviously grps(A) <= ncpu(A) because: + * + * if grps(A) is 1, then grps(A) <= ncpu(A) given + * ncpu(A) >= 1 + * + * otherwise, + * grps(A) <= G * ncpu(A) / N <= ncpu(A), given G <= N + * + * 3) prove how grps(B) <= ncpu(B): + * + * if round_down(G * ncpu(A) / N) == 0, vecs(B) won't be + * over-allocated, so grps(B) <= ncpu(B), + * + * otherwise: + * + * grps(A) = + * round_down(G * ncpu(A) / N) = + * round_down((N - delta) * ncpu(A) / N) = + * round_down((N * ncpu(A) - delta * ncpu(A)) / N) >= + * round_down((N * ncpu(A) - delta * N) / N) = + * cpu(A) - delta + * + * then: + * + * grps(A) - G >= ncpu(A) - delta - G + * => + * G - grps(A) <= G + delta - ncpu(A) + * => + * grps(B) <= N - ncpu(A) + * => + * grps(B) <= cpu(B) + * + * For nodes >= 3, it can be thought as one node and another big + * node given that is exactly what this algorithm is implemented, + * and we always re-calculate 'remaining_ncpus' & 'numgrps', and + * finally for each node X: grps(X) <= ncpu(X). + * + */ + for (n = 0; n < nr_node_ids; n++) { + unsigned ngroups, ncpus; + + if (node_groups[n].ncpus == UINT_MAX) + continue; + + WARN_ON_ONCE(numgrps == 0); + + ncpus = node_groups[n].ncpus; + ngroups = max_t(unsigned, 1, + numgrps * ncpus / remaining_ncpus); + WARN_ON_ONCE(ngroups > ncpus); + + node_groups[n].ngroups = ngroups; + + remaining_ncpus -= ncpus; + numgrps -= ngroups; + } +} + +static int __group_cpus_evenly(unsigned int startgrp, unsigned int numgrps, + cpumask_var_t *node_to_cpumask, + const struct cpumask *cpu_mask, + struct cpumask *nmsk, struct cpumask *masks) +{ + unsigned int i, n, nodes, cpus_per_grp, extra_grps, done = 0; + unsigned int last_grp = numgrps; + unsigned int curgrp = startgrp; + nodemask_t nodemsk = NODE_MASK_NONE; + struct node_groups *node_groups; + + if (cpumask_empty(cpu_mask)) + return 0; + + nodes = get_nodes_in_cpumask(node_to_cpumask, cpu_mask, &nodemsk); + + /* + * If the number of nodes in the mask is greater than or equal the + * number of groups we just spread the groups across the nodes. + */ + if (numgrps <= nodes) { + for_each_node_mask(n, nodemsk) { + /* Ensure that only CPUs which are in both masks are set */ + cpumask_and(nmsk, cpu_mask, node_to_cpumask[n]); + cpumask_or(&masks[curgrp], &masks[curgrp], nmsk); + if (++curgrp == last_grp) + curgrp = 0; + } + return numgrps; + } + + node_groups = kcalloc(nr_node_ids, + sizeof(struct node_groups), + GFP_KERNEL); + if (!node_groups) + return -ENOMEM; + + /* allocate group number for each node */ + alloc_nodes_groups(numgrps, node_to_cpumask, cpu_mask, + nodemsk, nmsk, node_groups); + for (i = 0; i < nr_node_ids; i++) { + unsigned int ncpus, v; + struct node_groups *nv = &node_groups[i]; + + if (nv->ngroups == UINT_MAX) + continue; + + /* Get the cpus on this node which are in the mask */ + cpumask_and(nmsk, cpu_mask, node_to_cpumask[nv->id]); + ncpus = cpumask_weight(nmsk); + if (!ncpus) + continue; + + WARN_ON_ONCE(nv->ngroups > ncpus); + + /* Account for rounding errors */ + extra_grps = ncpus - nv->ngroups * (ncpus / nv->ngroups); + + /* Spread allocated groups on CPUs of the current node */ + for (v = 0; v < nv->ngroups; v++, curgrp++) { + cpus_per_grp = ncpus / nv->ngroups; + + /* Account for extra groups to compensate rounding errors */ + if (extra_grps) { + cpus_per_grp++; + --extra_grps; + } + + /* + * wrapping has to be considered given 'startgrp' + * may start anywhere + */ + if (curgrp >= last_grp) + curgrp = 0; + grp_spread_init_one(&masks[curgrp], nmsk, + cpus_per_grp); + } + done += nv->ngroups; + } + kfree(node_groups); + return done; +} + +/** + * group_cpus_evenly - Group all CPUs evenly per NUMA/CPU locality + * @numgrps: number of groups + * + * Return: cpumask array if successful, NULL otherwise. And each element + * includes CPUs assigned to this group + * + * Try to put close CPUs from viewpoint of CPU and NUMA locality into + * same group, and run two-stage grouping: + * 1) allocate present CPUs on these groups evenly first + * 2) allocate other possible CPUs on these groups evenly + * + * We guarantee in the resulted grouping that all CPUs are covered, and + * no same CPU is assigned to multiple groups + */ +struct cpumask *group_cpus_evenly(unsigned int numgrps) +{ + unsigned int curgrp = 0, nr_present = 0, nr_others = 0; + cpumask_var_t *node_to_cpumask; + cpumask_var_t nmsk, npresmsk; + int ret = -ENOMEM; + struct cpumask *masks = NULL; + + if (!zalloc_cpumask_var(&nmsk, GFP_KERNEL)) + return NULL; + + if (!zalloc_cpumask_var(&npresmsk, GFP_KERNEL)) + goto fail_nmsk; + + node_to_cpumask = alloc_node_to_cpumask(); + if (!node_to_cpumask) + goto fail_npresmsk; + + masks = kcalloc(numgrps, sizeof(*masks), GFP_KERNEL); + if (!masks) + goto fail_node_to_cpumask; + + /* Stabilize the cpumasks */ + cpus_read_lock(); + build_node_to_cpumask(node_to_cpumask); + + /* grouping present CPUs first */ + ret = __group_cpus_evenly(curgrp, numgrps, node_to_cpumask, + cpu_present_mask, nmsk, masks); + if (ret < 0) + goto fail_build_affinity; + nr_present = ret; + + /* + * Allocate non present CPUs starting from the next group to be + * handled. If the grouping of present CPUs already exhausted the + * group space, assign the non present CPUs to the already + * allocated out groups. + */ + if (nr_present >= numgrps) + curgrp = 0; + else + curgrp = nr_present; + cpumask_andnot(npresmsk, cpu_possible_mask, cpu_present_mask); + ret = __group_cpus_evenly(curgrp, numgrps, node_to_cpumask, + npresmsk, nmsk, masks); + if (ret >= 0) + nr_others = ret; + + fail_build_affinity: + cpus_read_unlock(); + + if (ret >= 0) + WARN_ON(nr_present + nr_others < numgrps); + + fail_node_to_cpumask: + free_node_to_cpumask(node_to_cpumask); + + fail_npresmsk: + free_cpumask_var(npresmsk); + + fail_nmsk: + free_cpumask_var(nmsk); + if (ret < 0) { + kfree(masks); + return NULL; + } + return masks; +} +#else /* CONFIG_SMP */ +struct cpumask *group_cpus_evenly(unsigned int numgrps) +{ + struct cpumask *masks = kcalloc(numgrps, sizeof(*masks), GFP_KERNEL); + + if (!masks) + return NULL; + + /* assign all CPUs(cpu 0) to the 1st group only */ + cpumask_copy(&masks[0], cpu_possible_mask); + return masks; +} +#endif /* CONFIG_SMP */ diff --git a/lib/hashtable_test.c b/lib/hashtable_test.c new file mode 100644 index 000000000000..1d1b3288dee2 --- /dev/null +++ b/lib/hashtable_test.c @@ -0,0 +1,317 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * KUnit test for the Kernel Hashtable structures. + * + * Copyright (C) 2022, Google LLC. + * Author: Rae Moar <rmoar@google.com> + */ +#include <kunit/test.h> + +#include <linux/hashtable.h> + +struct hashtable_test_entry { + int key; + int data; + struct hlist_node node; + int visited; +}; + +static void hashtable_test_hash_init(struct kunit *test) +{ + /* Test the different ways of initialising a hashtable. */ + DEFINE_HASHTABLE(hash1, 2); + DECLARE_HASHTABLE(hash2, 3); + + /* When using DECLARE_HASHTABLE, must use hash_init to + * initialize the hashtable. + */ + hash_init(hash2); + + KUNIT_EXPECT_TRUE(test, hash_empty(hash1)); + KUNIT_EXPECT_TRUE(test, hash_empty(hash2)); +} + +static void hashtable_test_hash_empty(struct kunit *test) +{ + struct hashtable_test_entry a; + DEFINE_HASHTABLE(hash, 1); + + KUNIT_EXPECT_TRUE(test, hash_empty(hash)); + + a.key = 1; + a.data = 13; + hash_add(hash, &a.node, a.key); + + /* Hashtable should no longer be empty. */ + KUNIT_EXPECT_FALSE(test, hash_empty(hash)); +} + +static void hashtable_test_hash_hashed(struct kunit *test) +{ + struct hashtable_test_entry a, b; + DEFINE_HASHTABLE(hash, 4); + + a.key = 1; + a.data = 13; + hash_add(hash, &a.node, a.key); + b.key = 1; + b.data = 2; + hash_add(hash, &b.node, b.key); + + KUNIT_EXPECT_TRUE(test, hash_hashed(&a.node)); + KUNIT_EXPECT_TRUE(test, hash_hashed(&b.node)); +} + +static void hashtable_test_hash_add(struct kunit *test) +{ + struct hashtable_test_entry a, b, *x; + int bkt; + DEFINE_HASHTABLE(hash, 3); + + a.key = 1; + a.data = 13; + a.visited = 0; + hash_add(hash, &a.node, a.key); + b.key = 2; + b.data = 10; + b.visited = 0; + hash_add(hash, &b.node, b.key); + + hash_for_each(hash, bkt, x, node) { + x->visited++; + if (x->key == a.key) + KUNIT_EXPECT_EQ(test, x->data, 13); + else if (x->key == b.key) + KUNIT_EXPECT_EQ(test, x->data, 10); + else + KUNIT_FAIL(test, "Unexpected key in hashtable."); + } + + /* Both entries should have been visited exactly once. */ + KUNIT_EXPECT_EQ(test, a.visited, 1); + KUNIT_EXPECT_EQ(test, b.visited, 1); +} + +static void hashtable_test_hash_del(struct kunit *test) +{ + struct hashtable_test_entry a, b, *x; + DEFINE_HASHTABLE(hash, 6); + + a.key = 1; + a.data = 13; + hash_add(hash, &a.node, a.key); + b.key = 2; + b.data = 10; + b.visited = 0; + hash_add(hash, &b.node, b.key); + + hash_del(&b.node); + hash_for_each_possible(hash, x, node, b.key) { + x->visited++; + KUNIT_EXPECT_NE(test, x->key, b.key); + } + + /* The deleted entry should not have been visited. */ + KUNIT_EXPECT_EQ(test, b.visited, 0); + + hash_del(&a.node); + + /* The hashtable should be empty. */ + KUNIT_EXPECT_TRUE(test, hash_empty(hash)); +} + +static void hashtable_test_hash_for_each(struct kunit *test) +{ + struct hashtable_test_entry entries[3]; + struct hashtable_test_entry *x; + int bkt, i, j, count; + DEFINE_HASHTABLE(hash, 3); + + /* Add three entries to the hashtable. */ + for (i = 0; i < 3; i++) { + entries[i].key = i; + entries[i].data = i + 10; + entries[i].visited = 0; + hash_add(hash, &entries[i].node, entries[i].key); + } + + count = 0; + hash_for_each(hash, bkt, x, node) { + x->visited += 1; + KUNIT_ASSERT_GE_MSG(test, x->key, 0, "Unexpected key in hashtable."); + KUNIT_ASSERT_LT_MSG(test, x->key, 3, "Unexpected key in hashtable."); + count++; + } + + /* Should have visited each entry exactly once. */ + KUNIT_EXPECT_EQ(test, count, 3); + for (j = 0; j < 3; j++) + KUNIT_EXPECT_EQ(test, entries[j].visited, 1); +} + +static void hashtable_test_hash_for_each_safe(struct kunit *test) +{ + struct hashtable_test_entry entries[3]; + struct hashtable_test_entry *x; + struct hlist_node *tmp; + int bkt, i, j, count; + DEFINE_HASHTABLE(hash, 3); + + /* Add three entries to the hashtable. */ + for (i = 0; i < 3; i++) { + entries[i].key = i; + entries[i].data = i + 10; + entries[i].visited = 0; + hash_add(hash, &entries[i].node, entries[i].key); + } + + count = 0; + hash_for_each_safe(hash, bkt, tmp, x, node) { + x->visited += 1; + KUNIT_ASSERT_GE_MSG(test, x->key, 0, "Unexpected key in hashtable."); + KUNIT_ASSERT_LT_MSG(test, x->key, 3, "Unexpected key in hashtable."); + count++; + + /* Delete entry during loop. */ + hash_del(&x->node); + } + + /* Should have visited each entry exactly once. */ + KUNIT_EXPECT_EQ(test, count, 3); + for (j = 0; j < 3; j++) + KUNIT_EXPECT_EQ(test, entries[j].visited, 1); +} + +static void hashtable_test_hash_for_each_possible(struct kunit *test) +{ + struct hashtable_test_entry entries[4]; + struct hashtable_test_entry *x, *y; + int buckets[2]; + int bkt, i, j, count; + DEFINE_HASHTABLE(hash, 5); + + /* Add three entries with key = 0 to the hashtable. */ + for (i = 0; i < 3; i++) { + entries[i].key = 0; + entries[i].data = i; + entries[i].visited = 0; + hash_add(hash, &entries[i].node, entries[i].key); + } + + /* Add an entry with key = 1. */ + entries[3].key = 1; + entries[3].data = 3; + entries[3].visited = 0; + hash_add(hash, &entries[3].node, entries[3].key); + + count = 0; + hash_for_each_possible(hash, x, node, 0) { + x->visited += 1; + KUNIT_ASSERT_GE_MSG(test, x->data, 0, "Unexpected data in hashtable."); + KUNIT_ASSERT_LT_MSG(test, x->data, 4, "Unexpected data in hashtable."); + count++; + } + + /* Should have visited each entry with key = 0 exactly once. */ + for (j = 0; j < 3; j++) + KUNIT_EXPECT_EQ(test, entries[j].visited, 1); + + /* Save the buckets for the different keys. */ + hash_for_each(hash, bkt, y, node) { + KUNIT_ASSERT_GE_MSG(test, y->key, 0, "Unexpected key in hashtable."); + KUNIT_ASSERT_LE_MSG(test, y->key, 1, "Unexpected key in hashtable."); + buckets[y->key] = bkt; + } + + /* If entry with key = 1 is in the same bucket as the entries with + * key = 0, check it was visited. Otherwise ensure that only three + * entries were visited. + */ + if (buckets[0] == buckets[1]) { + KUNIT_EXPECT_EQ(test, count, 4); + KUNIT_EXPECT_EQ(test, entries[3].visited, 1); + } else { + KUNIT_EXPECT_EQ(test, count, 3); + KUNIT_EXPECT_EQ(test, entries[3].visited, 0); + } +} + +static void hashtable_test_hash_for_each_possible_safe(struct kunit *test) +{ + struct hashtable_test_entry entries[4]; + struct hashtable_test_entry *x, *y; + struct hlist_node *tmp; + int buckets[2]; + int bkt, i, j, count; + DEFINE_HASHTABLE(hash, 5); + + /* Add three entries with key = 0 to the hashtable. */ + for (i = 0; i < 3; i++) { + entries[i].key = 0; + entries[i].data = i; + entries[i].visited = 0; + hash_add(hash, &entries[i].node, entries[i].key); + } + + /* Add an entry with key = 1. */ + entries[3].key = 1; + entries[3].data = 3; + entries[3].visited = 0; + hash_add(hash, &entries[3].node, entries[3].key); + + count = 0; + hash_for_each_possible_safe(hash, x, tmp, node, 0) { + x->visited += 1; + KUNIT_ASSERT_GE_MSG(test, x->data, 0, "Unexpected data in hashtable."); + KUNIT_ASSERT_LT_MSG(test, x->data, 4, "Unexpected data in hashtable."); + count++; + + /* Delete entry during loop. */ + hash_del(&x->node); + } + + /* Should have visited each entry with key = 0 exactly once. */ + for (j = 0; j < 3; j++) + KUNIT_EXPECT_EQ(test, entries[j].visited, 1); + + /* Save the buckets for the different keys. */ + hash_for_each(hash, bkt, y, node) { + KUNIT_ASSERT_GE_MSG(test, y->key, 0, "Unexpected key in hashtable."); + KUNIT_ASSERT_LE_MSG(test, y->key, 1, "Unexpected key in hashtable."); + buckets[y->key] = bkt; + } + + /* If entry with key = 1 is in the same bucket as the entries with + * key = 0, check it was visited. Otherwise ensure that only three + * entries were visited. + */ + if (buckets[0] == buckets[1]) { + KUNIT_EXPECT_EQ(test, count, 4); + KUNIT_EXPECT_EQ(test, entries[3].visited, 1); + } else { + KUNIT_EXPECT_EQ(test, count, 3); + KUNIT_EXPECT_EQ(test, entries[3].visited, 0); + } +} + +static struct kunit_case hashtable_test_cases[] = { + KUNIT_CASE(hashtable_test_hash_init), + KUNIT_CASE(hashtable_test_hash_empty), + KUNIT_CASE(hashtable_test_hash_hashed), + KUNIT_CASE(hashtable_test_hash_add), + KUNIT_CASE(hashtable_test_hash_del), + KUNIT_CASE(hashtable_test_hash_for_each), + KUNIT_CASE(hashtable_test_hash_for_each_safe), + KUNIT_CASE(hashtable_test_hash_for_each_possible), + KUNIT_CASE(hashtable_test_hash_for_each_possible_safe), + {}, +}; + +static struct kunit_suite hashtable_test_module = { + .name = "hashtable", + .test_cases = hashtable_test_cases, +}; + +kunit_test_suites(&hashtable_test_module); + +MODULE_LICENSE("GPL"); diff --git a/lib/iov_iter.c b/lib/iov_iter.c index f9a3ff37ecd1..274014e4eafe 100644 --- a/lib/iov_iter.c +++ b/lib/iov_iter.c @@ -186,12 +186,6 @@ static int copyin(void *to, const void __user *from, size_t n) return res; } -static inline struct pipe_buffer *pipe_buf(const struct pipe_inode_info *pipe, - unsigned int slot) -{ - return &pipe->bufs[slot & (pipe->ring_size - 1)]; -} - #ifdef PIPE_PARANOIA static bool sanity(const struct iov_iter *i) { @@ -1432,9 +1426,9 @@ static struct page *first_bvec_segment(const struct iov_iter *i, static ssize_t __iov_iter_get_pages_alloc(struct iov_iter *i, struct page ***pages, size_t maxsize, unsigned int maxpages, size_t *start, - unsigned int gup_flags) + iov_iter_extraction_t extraction_flags) { - unsigned int n; + unsigned int n, gup_flags = 0; if (maxsize > i->count) maxsize = i->count; @@ -1442,6 +1436,8 @@ static ssize_t __iov_iter_get_pages_alloc(struct iov_iter *i, return 0; if (maxsize > MAX_RW_COUNT) maxsize = MAX_RW_COUNT; + if (extraction_flags & ITER_ALLOW_P2PDMA) + gup_flags |= FOLL_PCI_P2PDMA; if (likely(user_backed_iter(i))) { unsigned long addr; @@ -1495,14 +1491,14 @@ static ssize_t __iov_iter_get_pages_alloc(struct iov_iter *i, ssize_t iov_iter_get_pages(struct iov_iter *i, struct page **pages, size_t maxsize, unsigned maxpages, - size_t *start, unsigned gup_flags) + size_t *start, iov_iter_extraction_t extraction_flags) { if (!maxpages) return 0; BUG_ON(!pages); return __iov_iter_get_pages_alloc(i, &pages, maxsize, maxpages, - start, gup_flags); + start, extraction_flags); } EXPORT_SYMBOL_GPL(iov_iter_get_pages); @@ -1515,14 +1511,14 @@ EXPORT_SYMBOL(iov_iter_get_pages2); ssize_t iov_iter_get_pages_alloc(struct iov_iter *i, struct page ***pages, size_t maxsize, - size_t *start, unsigned gup_flags) + size_t *start, iov_iter_extraction_t extraction_flags) { ssize_t len; *pages = NULL; len = __iov_iter_get_pages_alloc(i, pages, maxsize, ~0U, start, - gup_flags); + extraction_flags); if (len <= 0) { kvfree(*pages); *pages = NULL; @@ -1877,6 +1873,17 @@ int import_single_range(int rw, void __user *buf, size_t len, } EXPORT_SYMBOL(import_single_range); +int import_ubuf(int rw, void __user *buf, size_t len, struct iov_iter *i) +{ + if (len > MAX_RW_COUNT) + len = MAX_RW_COUNT; + if (unlikely(!access_ok(buf, len))) + return -EFAULT; + + iov_iter_ubuf(i, rw, buf, len); + return 0; +} + /** * iov_iter_restore() - Restore a &struct iov_iter to the same state as when * iov_iter_save_state() was called. @@ -1891,8 +1898,8 @@ EXPORT_SYMBOL(import_single_range); */ void iov_iter_restore(struct iov_iter *i, struct iov_iter_state *state) { - if (WARN_ON_ONCE(!iov_iter_is_bvec(i) && !iter_is_iovec(i)) && - !iov_iter_is_kvec(i) && !iter_is_ubuf(i)) + if (WARN_ON_ONCE(!iov_iter_is_bvec(i) && !iter_is_iovec(i) && + !iter_is_ubuf(i)) && !iov_iter_is_kvec(i)) return; i->iov_offset = state->iov_offset; i->count = state->count; @@ -1914,3 +1921,267 @@ void iov_iter_restore(struct iov_iter *i, struct iov_iter_state *state) i->iov -= state->nr_segs - i->nr_segs; i->nr_segs = state->nr_segs; } + +/* + * Extract a list of contiguous pages from an ITER_XARRAY iterator. This does not + * get references on the pages, nor does it get a pin on them. + */ +static ssize_t iov_iter_extract_xarray_pages(struct iov_iter *i, + struct page ***pages, size_t maxsize, + unsigned int maxpages, + iov_iter_extraction_t extraction_flags, + size_t *offset0) +{ + struct page *page, **p; + unsigned int nr = 0, offset; + loff_t pos = i->xarray_start + i->iov_offset; + pgoff_t index = pos >> PAGE_SHIFT; + XA_STATE(xas, i->xarray, index); + + offset = pos & ~PAGE_MASK; + *offset0 = offset; + + maxpages = want_pages_array(pages, maxsize, offset, maxpages); + if (!maxpages) + return -ENOMEM; + p = *pages; + + rcu_read_lock(); + for (page = xas_load(&xas); page; page = xas_next(&xas)) { + if (xas_retry(&xas, page)) + continue; + + /* Has the page moved or been split? */ + if (unlikely(page != xas_reload(&xas))) { + xas_reset(&xas); + continue; + } + + p[nr++] = find_subpage(page, xas.xa_index); + if (nr == maxpages) + break; + } + rcu_read_unlock(); + + maxsize = min_t(size_t, nr * PAGE_SIZE - offset, maxsize); + iov_iter_advance(i, maxsize); + return maxsize; +} + +/* + * Extract a list of contiguous pages from an ITER_BVEC iterator. This does + * not get references on the pages, nor does it get a pin on them. + */ +static ssize_t iov_iter_extract_bvec_pages(struct iov_iter *i, + struct page ***pages, size_t maxsize, + unsigned int maxpages, + iov_iter_extraction_t extraction_flags, + size_t *offset0) +{ + struct page **p, *page; + size_t skip = i->iov_offset, offset; + int k; + + for (;;) { + if (i->nr_segs == 0) + return 0; + maxsize = min(maxsize, i->bvec->bv_len - skip); + if (maxsize) + break; + i->iov_offset = 0; + i->nr_segs--; + i->bvec++; + skip = 0; + } + + skip += i->bvec->bv_offset; + page = i->bvec->bv_page + skip / PAGE_SIZE; + offset = skip % PAGE_SIZE; + *offset0 = offset; + + maxpages = want_pages_array(pages, maxsize, offset, maxpages); + if (!maxpages) + return -ENOMEM; + p = *pages; + for (k = 0; k < maxpages; k++) + p[k] = page + k; + + maxsize = min_t(size_t, maxsize, maxpages * PAGE_SIZE - offset); + iov_iter_advance(i, maxsize); + return maxsize; +} + +/* + * Extract a list of virtually contiguous pages from an ITER_KVEC iterator. + * This does not get references on the pages, nor does it get a pin on them. + */ +static ssize_t iov_iter_extract_kvec_pages(struct iov_iter *i, + struct page ***pages, size_t maxsize, + unsigned int maxpages, + iov_iter_extraction_t extraction_flags, + size_t *offset0) +{ + struct page **p, *page; + const void *kaddr; + size_t skip = i->iov_offset, offset, len; + int k; + + for (;;) { + if (i->nr_segs == 0) + return 0; + maxsize = min(maxsize, i->kvec->iov_len - skip); + if (maxsize) + break; + i->iov_offset = 0; + i->nr_segs--; + i->kvec++; + skip = 0; + } + + kaddr = i->kvec->iov_base + skip; + offset = (unsigned long)kaddr & ~PAGE_MASK; + *offset0 = offset; + + maxpages = want_pages_array(pages, maxsize, offset, maxpages); + if (!maxpages) + return -ENOMEM; + p = *pages; + + kaddr -= offset; + len = offset + maxsize; + for (k = 0; k < maxpages; k++) { + size_t seg = min_t(size_t, len, PAGE_SIZE); + + if (is_vmalloc_or_module_addr(kaddr)) + page = vmalloc_to_page(kaddr); + else + page = virt_to_page(kaddr); + + p[k] = page; + len -= seg; + kaddr += PAGE_SIZE; + } + + maxsize = min_t(size_t, maxsize, maxpages * PAGE_SIZE - offset); + iov_iter_advance(i, maxsize); + return maxsize; +} + +/* + * Extract a list of contiguous pages from a user iterator and get a pin on + * each of them. This should only be used if the iterator is user-backed + * (IOBUF/UBUF). + * + * It does not get refs on the pages, but the pages must be unpinned by the + * caller once the transfer is complete. + * + * This is safe to be used where background IO/DMA *is* going to be modifying + * the buffer; using a pin rather than a ref makes forces fork() to give the + * child a copy of the page. + */ +static ssize_t iov_iter_extract_user_pages(struct iov_iter *i, + struct page ***pages, + size_t maxsize, + unsigned int maxpages, + iov_iter_extraction_t extraction_flags, + size_t *offset0) +{ + unsigned long addr; + unsigned int gup_flags = 0; + size_t offset; + int res; + + if (i->data_source == ITER_DEST) + gup_flags |= FOLL_WRITE; + if (extraction_flags & ITER_ALLOW_P2PDMA) + gup_flags |= FOLL_PCI_P2PDMA; + if (i->nofault) + gup_flags |= FOLL_NOFAULT; + + addr = first_iovec_segment(i, &maxsize); + *offset0 = offset = addr % PAGE_SIZE; + addr &= PAGE_MASK; + maxpages = want_pages_array(pages, maxsize, offset, maxpages); + if (!maxpages) + return -ENOMEM; + res = pin_user_pages_fast(addr, maxpages, gup_flags, *pages); + if (unlikely(res <= 0)) + return res; + maxsize = min_t(size_t, maxsize, res * PAGE_SIZE - offset); + iov_iter_advance(i, maxsize); + return maxsize; +} + +/** + * iov_iter_extract_pages - Extract a list of contiguous pages from an iterator + * @i: The iterator to extract from + * @pages: Where to return the list of pages + * @maxsize: The maximum amount of iterator to extract + * @maxpages: The maximum size of the list of pages + * @extraction_flags: Flags to qualify request + * @offset0: Where to return the starting offset into (*@pages)[0] + * + * Extract a list of contiguous pages from the current point of the iterator, + * advancing the iterator. The maximum number of pages and the maximum amount + * of page contents can be set. + * + * If *@pages is NULL, a page list will be allocated to the required size and + * *@pages will be set to its base. If *@pages is not NULL, it will be assumed + * that the caller allocated a page list at least @maxpages in size and this + * will be filled in. + * + * @extraction_flags can have ITER_ALLOW_P2PDMA set to request peer-to-peer DMA + * be allowed on the pages extracted. + * + * The iov_iter_extract_will_pin() function can be used to query how cleanup + * should be performed. + * + * Extra refs or pins on the pages may be obtained as follows: + * + * (*) If the iterator is user-backed (ITER_IOVEC/ITER_UBUF), pins will be + * added to the pages, but refs will not be taken. + * iov_iter_extract_will_pin() will return true. + * + * (*) If the iterator is ITER_KVEC, ITER_BVEC or ITER_XARRAY, the pages are + * merely listed; no extra refs or pins are obtained. + * iov_iter_extract_will_pin() will return 0. + * + * Note also: + * + * (*) Use with ITER_DISCARD is not supported as that has no content. + * + * On success, the function sets *@pages to the new pagelist, if allocated, and + * sets *offset0 to the offset into the first page. + * + * It may also return -ENOMEM and -EFAULT. + */ +ssize_t iov_iter_extract_pages(struct iov_iter *i, + struct page ***pages, + size_t maxsize, + unsigned int maxpages, + iov_iter_extraction_t extraction_flags, + size_t *offset0) +{ + maxsize = min_t(size_t, min_t(size_t, maxsize, i->count), MAX_RW_COUNT); + if (!maxsize) + return 0; + + if (likely(user_backed_iter(i))) + return iov_iter_extract_user_pages(i, pages, maxsize, + maxpages, extraction_flags, + offset0); + if (iov_iter_is_kvec(i)) + return iov_iter_extract_kvec_pages(i, pages, maxsize, + maxpages, extraction_flags, + offset0); + if (iov_iter_is_bvec(i)) + return iov_iter_extract_bvec_pages(i, pages, maxsize, + maxpages, extraction_flags, + offset0); + if (iov_iter_is_xarray(i)) + return iov_iter_extract_xarray_pages(i, pages, maxsize, + maxpages, extraction_flags, + offset0); + return -EFAULT; +} +EXPORT_SYMBOL_GPL(iov_iter_extract_pages); diff --git a/lib/kobject.c b/lib/kobject.c index 985ee1c4f2c6..6e2f0bee3560 100644 --- a/lib/kobject.c +++ b/lib/kobject.c @@ -112,7 +112,7 @@ static int get_kobj_path_length(const struct kobject *kobj) return length; } -static void fill_kobj_path(const struct kobject *kobj, char *path, int length) +static int fill_kobj_path(const struct kobject *kobj, char *path, int length) { const struct kobject *parent; @@ -121,12 +121,16 @@ static void fill_kobj_path(const struct kobject *kobj, char *path, int length) int cur = strlen(kobject_name(parent)); /* back up enough to print this name with '/' */ length -= cur; + if (length <= 0) + return -EINVAL; memcpy(path + length, kobject_name(parent), cur); *(path + --length) = '/'; } pr_debug("kobject: '%s' (%p): %s: path = '%s'\n", kobject_name(kobj), kobj, __func__, path); + + return 0; } /** @@ -141,13 +145,17 @@ char *kobject_get_path(const struct kobject *kobj, gfp_t gfp_mask) char *path; int len; +retry: len = get_kobj_path_length(kobj); if (len == 0) return NULL; path = kzalloc(len, gfp_mask); if (!path) return NULL; - fill_kobj_path(kobj, path, len); + if (fill_kobj_path(kobj, path, len)) { + kfree(path); + goto retry; + } return path; } @@ -729,7 +737,7 @@ static void dynamic_kobj_release(struct kobject *kobj) kfree(kobj); } -static struct kobj_type dynamic_kobj_ktype = { +static const struct kobj_type dynamic_kobj_ktype = { .release = dynamic_kobj_release, .sysfs_ops = &kobj_sysfs_ops, }; @@ -913,7 +921,7 @@ static void kset_get_ownership(const struct kobject *kobj, kuid_t *uid, kgid_t * kobject_get_ownership(kobj->parent, uid, gid); } -static struct kobj_type kset_ktype = { +static const struct kobj_type kset_ktype = { .sysfs_ops = &kobj_sysfs_ops, .release = kset_release, .get_ownership = kset_get_ownership, diff --git a/lib/kunit/Makefile b/lib/kunit/Makefile index 29aff6562b42..da665cd4ea12 100644 --- a/lib/kunit/Makefile +++ b/lib/kunit/Makefile @@ -2,6 +2,7 @@ obj-$(CONFIG_KUNIT) += kunit.o kunit-objs += test.o \ resource.o \ + static_stub.o \ string-stream.o \ assert.o \ try-catch.o \ @@ -11,6 +12,9 @@ ifeq ($(CONFIG_KUNIT_DEBUGFS),y) kunit-objs += debugfs.o endif +# KUnit 'hooks' are built-in even when KUnit is built as a module. +lib-y += hooks.o + obj-$(CONFIG_KUNIT_TEST) += kunit-test.o # string-stream-test compiles built-in only. diff --git a/lib/kunit/assert.c b/lib/kunit/assert.c index f5b50babe38d..05a09652f5a1 100644 --- a/lib/kunit/assert.c +++ b/lib/kunit/assert.c @@ -241,24 +241,34 @@ void kunit_mem_assert_format(const struct kunit_assert *assert, mem_assert = container_of(assert, struct kunit_mem_assert, assert); - string_stream_add(stream, - KUNIT_SUBTEST_INDENT "Expected %s %s %s, but\n", - mem_assert->text->left_text, - mem_assert->text->operation, - mem_assert->text->right_text); + if (!mem_assert->left_value) { + string_stream_add(stream, + KUNIT_SUBTEST_INDENT "Expected %s is not null, but is\n", + mem_assert->text->left_text); + } else if (!mem_assert->right_value) { + string_stream_add(stream, + KUNIT_SUBTEST_INDENT "Expected %s is not null, but is\n", + mem_assert->text->right_text); + } else { + string_stream_add(stream, + KUNIT_SUBTEST_INDENT "Expected %s %s %s, but\n", + mem_assert->text->left_text, + mem_assert->text->operation, + mem_assert->text->right_text); - string_stream_add(stream, KUNIT_SUBSUBTEST_INDENT "%s ==\n", - mem_assert->text->left_text); - kunit_assert_hexdump(stream, mem_assert->left_value, - mem_assert->right_value, mem_assert->size); + string_stream_add(stream, KUNIT_SUBSUBTEST_INDENT "%s ==\n", + mem_assert->text->left_text); + kunit_assert_hexdump(stream, mem_assert->left_value, + mem_assert->right_value, mem_assert->size); - string_stream_add(stream, "\n"); + string_stream_add(stream, "\n"); - string_stream_add(stream, KUNIT_SUBSUBTEST_INDENT "%s ==\n", - mem_assert->text->right_text); - kunit_assert_hexdump(stream, mem_assert->right_value, - mem_assert->left_value, mem_assert->size); + string_stream_add(stream, KUNIT_SUBSUBTEST_INDENT "%s ==\n", + mem_assert->text->right_text); + kunit_assert_hexdump(stream, mem_assert->right_value, + mem_assert->left_value, mem_assert->size); - kunit_assert_print_msg(message, stream); + kunit_assert_print_msg(message, stream); + } } EXPORT_SYMBOL_GPL(kunit_mem_assert_format); diff --git a/lib/kunit/hooks-impl.h b/lib/kunit/hooks-impl.h new file mode 100644 index 000000000000..4e71b2d0143b --- /dev/null +++ b/lib/kunit/hooks-impl.h @@ -0,0 +1,31 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * Declarations for hook implementations. + * + * These will be set as the function pointers in struct kunit_hook_table, + * found in include/kunit/test-bug.h. + * + * Copyright (C) 2023, Google LLC. + * Author: David Gow <davidgow@google.com> + */ + +#ifndef _KUNIT_HOOKS_IMPL_H +#define _KUNIT_HOOKS_IMPL_H + +#include <kunit/test-bug.h> + +/* List of declarations. */ +void __printf(3, 4) __kunit_fail_current_test_impl(const char *file, + int line, + const char *fmt, ...); +void *__kunit_get_static_stub_address_impl(struct kunit *test, void *real_fn_addr); + +/* Code to set all of the function pointers. */ +static inline void kunit_install_hooks(void) +{ + /* Install the KUnit hook functions. */ + kunit_hooks.fail_current_test = __kunit_fail_current_test_impl; + kunit_hooks.get_static_stub_address = __kunit_get_static_stub_address_impl; +} + +#endif /* _KUNIT_HOOKS_IMPL_H */ diff --git a/lib/kunit/hooks.c b/lib/kunit/hooks.c new file mode 100644 index 000000000000..365d98d4953c --- /dev/null +++ b/lib/kunit/hooks.c @@ -0,0 +1,21 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * KUnit 'Hooks' implementation. + * + * This file contains code / structures which should be built-in even when + * KUnit itself is built as a module. + * + * Copyright (C) 2022, Google LLC. + * Author: David Gow <davidgow@google.com> + */ + + +#include <kunit/test-bug.h> + +DEFINE_STATIC_KEY_FALSE(kunit_running); +EXPORT_SYMBOL(kunit_running); + +/* Function pointers for hooks. */ +struct kunit_hooks_table kunit_hooks; +EXPORT_SYMBOL(kunit_hooks); + diff --git a/lib/kunit/kunit-example-test.c b/lib/kunit/kunit-example-test.c index 66cc4e2365ec..cd8b7e51d02b 100644 --- a/lib/kunit/kunit-example-test.c +++ b/lib/kunit/kunit-example-test.c @@ -7,6 +7,7 @@ */ #include <kunit/test.h> +#include <kunit/static_stub.h> /* * This is the most fundamental element of KUnit, the test case. A test case @@ -130,6 +131,42 @@ static void example_all_expect_macros_test(struct kunit *test) KUNIT_ASSERT_GT_MSG(test, sizeof(int), 0, "Your ints are 0-bit?!"); } +/* This is a function we'll replace with static stubs. */ +static int add_one(int i) +{ + /* This will trigger the stub if active. */ + KUNIT_STATIC_STUB_REDIRECT(add_one, i); + + return i + 1; +} + +/* This is used as a replacement for the above function. */ +static int subtract_one(int i) +{ + /* We don't need to trigger the stub from the replacement. */ + + return i - 1; +} + +/* + * This test shows the use of static stubs. + */ +static void example_static_stub_test(struct kunit *test) +{ + /* By default, function is not stubbed. */ + KUNIT_EXPECT_EQ(test, add_one(1), 2); + + /* Replace add_one() with subtract_one(). */ + kunit_activate_static_stub(test, add_one, subtract_one); + + /* add_one() is now replaced. */ + KUNIT_EXPECT_EQ(test, add_one(1), 0); + + /* Return add_one() to normal. */ + kunit_deactivate_static_stub(test, add_one); + KUNIT_EXPECT_EQ(test, add_one(1), 2); +} + /* * Here we make a list of all the test cases we want to add to the test suite * below. @@ -145,6 +182,7 @@ static struct kunit_case example_test_cases[] = { KUNIT_CASE(example_skip_test), KUNIT_CASE(example_mark_skipped_test), KUNIT_CASE(example_all_expect_macros_test), + KUNIT_CASE(example_static_stub_test), {} }; diff --git a/lib/kunit/static_stub.c b/lib/kunit/static_stub.c new file mode 100644 index 000000000000..92b2cccd5e76 --- /dev/null +++ b/lib/kunit/static_stub.c @@ -0,0 +1,123 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * KUnit function redirection (static stubbing) API. + * + * Copyright (C) 2022, Google LLC. + * Author: David Gow <davidgow@google.com> + */ + +#include <kunit/test.h> +#include <kunit/static_stub.h> +#include "hooks-impl.h" + + +/* Context for a static stub. This is stored in the resource data. */ +struct kunit_static_stub_ctx { + void *real_fn_addr; + void *replacement_addr; +}; + +static void __kunit_static_stub_resource_free(struct kunit_resource *res) +{ + kfree(res->data); +} + +/* Matching function for kunit_find_resource(). match_data is real_fn_addr. */ +static bool __kunit_static_stub_resource_match(struct kunit *test, + struct kunit_resource *res, + void *match_real_fn_addr) +{ + /* This pointer is only valid if res is a static stub resource. */ + struct kunit_static_stub_ctx *ctx = res->data; + + /* Make sure the resource is a static stub resource. */ + if (res->free != &__kunit_static_stub_resource_free) + return false; + + return ctx->real_fn_addr == match_real_fn_addr; +} + +/* Hook to return the address of the replacement function. */ +void *__kunit_get_static_stub_address_impl(struct kunit *test, void *real_fn_addr) +{ + struct kunit_resource *res; + struct kunit_static_stub_ctx *ctx; + void *replacement_addr; + + res = kunit_find_resource(test, + __kunit_static_stub_resource_match, + real_fn_addr); + + if (!res) + return NULL; + + ctx = res->data; + replacement_addr = ctx->replacement_addr; + kunit_put_resource(res); + return replacement_addr; +} + +void kunit_deactivate_static_stub(struct kunit *test, void *real_fn_addr) +{ + struct kunit_resource *res; + + KUNIT_ASSERT_PTR_NE_MSG(test, real_fn_addr, NULL, + "Tried to deactivate a NULL stub."); + + /* Look up the existing stub for this function. */ + res = kunit_find_resource(test, + __kunit_static_stub_resource_match, + real_fn_addr); + + /* Error out if the stub doesn't exist. */ + KUNIT_ASSERT_PTR_NE_MSG(test, res, NULL, + "Tried to deactivate a nonexistent stub."); + + /* Free the stub. We 'put' twice, as we got a reference + * from kunit_find_resource() + */ + kunit_remove_resource(test, res); + kunit_put_resource(res); +} +EXPORT_SYMBOL_GPL(kunit_deactivate_static_stub); + +/* Helper function for kunit_activate_static_stub(). The macro does + * typechecking, so use it instead. + */ +void __kunit_activate_static_stub(struct kunit *test, + void *real_fn_addr, + void *replacement_addr) +{ + struct kunit_static_stub_ctx *ctx; + struct kunit_resource *res; + + KUNIT_ASSERT_PTR_NE_MSG(test, real_fn_addr, NULL, + "Tried to activate a stub for function NULL"); + + /* If the replacement address is NULL, deactivate the stub. */ + if (!replacement_addr) { + kunit_deactivate_static_stub(test, replacement_addr); + return; + } + + /* Look up any existing stubs for this function, and replace them. */ + res = kunit_find_resource(test, + __kunit_static_stub_resource_match, + real_fn_addr); + if (res) { + ctx = res->data; + ctx->replacement_addr = replacement_addr; + + /* We got an extra reference from find_resource(), so put it. */ + kunit_put_resource(res); + } else { + ctx = kmalloc(sizeof(*ctx), GFP_KERNEL); + KUNIT_ASSERT_NOT_ERR_OR_NULL(test, ctx); + ctx->real_fn_addr = real_fn_addr; + ctx->replacement_addr = replacement_addr; + res = kunit_alloc_resource(test, NULL, + &__kunit_static_stub_resource_free, + GFP_KERNEL, ctx); + } +} +EXPORT_SYMBOL_GPL(__kunit_activate_static_stub); diff --git a/lib/kunit/string-stream.c b/lib/kunit/string-stream.c index f5f51166d8c2..cc32743c1171 100644 --- a/lib/kunit/string-stream.c +++ b/lib/kunit/string-stream.c @@ -23,8 +23,10 @@ static struct string_stream_fragment *alloc_string_stream_fragment( return ERR_PTR(-ENOMEM); frag->fragment = kunit_kmalloc(test, len, gfp); - if (!frag->fragment) + if (!frag->fragment) { + kunit_kfree(test, frag); return ERR_PTR(-ENOMEM); + } return frag; } diff --git a/lib/kunit/test.c b/lib/kunit/test.c index c9ebf975e56b..c9e15bb60058 100644 --- a/lib/kunit/test.c +++ b/lib/kunit/test.c @@ -17,16 +17,14 @@ #include <linux/sched.h> #include "debugfs.h" +#include "hooks-impl.h" #include "string-stream.h" #include "try-catch-impl.h" -DEFINE_STATIC_KEY_FALSE(kunit_running); - -#if IS_BUILTIN(CONFIG_KUNIT) /* - * Fail the current test and print an error message to the log. + * Hook to fail the current test and print an error message to the log. */ -void __kunit_fail_current_test(const char *file, int line, const char *fmt, ...) +void __printf(3, 4) __kunit_fail_current_test_impl(const char *file, int line, const char *fmt, ...) { va_list args; int len; @@ -53,8 +51,6 @@ void __kunit_fail_current_test(const char *file, int line, const char *fmt, ...) kunit_err(current->kunit_test, "%s:%d: %s", file, line, buffer); kunit_kfree(current->kunit_test, buffer); } -EXPORT_SYMBOL_GPL(__kunit_fail_current_test); -#endif /* * Enable KUnit tests to run. @@ -777,6 +773,9 @@ EXPORT_SYMBOL_GPL(kunit_cleanup); static int __init kunit_init(void) { + /* Install the KUnit hook functions. */ + kunit_install_hooks(); + kunit_debugfs_init(); #ifdef CONFIG_MODULES return register_module_notifier(&kunit_mod_nb); @@ -788,6 +787,7 @@ late_initcall(kunit_init); static void __exit kunit_exit(void) { + memset(&kunit_hooks, 0, sizeof(kunit_hooks)); #ifdef CONFIG_MODULES unregister_module_notifier(&kunit_mod_nb); #endif diff --git a/lib/lockref.c b/lib/lockref.c index 45e93ece8ba0..2afe4c5d8919 100644 --- a/lib/lockref.c +++ b/lib/lockref.c @@ -23,7 +23,6 @@ } \ if (!--retry) \ break; \ - cpu_relax(); \ } \ } while (0) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 26e2045d3cda..646297cae5d1 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -146,16 +146,22 @@ struct maple_subtree_state { struct maple_big_node *bn; }; +#ifdef CONFIG_KASAN_STACK +/* Prevent mas_wr_bnode() from exceeding the stack frame limit */ +#define noinline_for_kasan noinline_for_stack +#else +#define noinline_for_kasan inline +#endif + /* Functions */ static inline struct maple_node *mt_alloc_one(gfp_t gfp) { - return kmem_cache_alloc(maple_node_cache, gfp | __GFP_ZERO); + return kmem_cache_alloc(maple_node_cache, gfp); } static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes) { - return kmem_cache_alloc_bulk(maple_node_cache, gfp | __GFP_ZERO, size, - nodes); + return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes); } static inline void mt_free_bulk(size_t size, void __rcu **nodes) @@ -183,7 +189,6 @@ static void ma_free_rcu(struct maple_node *node) call_rcu(&node->rcu, mt_free_rcu); } - static void mas_set_height(struct ma_state *mas) { unsigned int new_flags = mas->tree->ma_flags; @@ -468,7 +473,7 @@ static inline void mte_set_parent(struct maple_enode *enode, const struct maple_enode *parent, unsigned char slot) { - unsigned long val = (unsigned long) parent; + unsigned long val = (unsigned long)parent; unsigned long shift; unsigned long type; enum maple_type p_type = mte_node_type(parent); @@ -502,10 +507,9 @@ void mte_set_parent(struct maple_enode *enode, const struct maple_enode *parent, */ static inline unsigned int mte_parent_slot(const struct maple_enode *enode) { - unsigned long val = (unsigned long) mte_to_node(enode)->parent; + unsigned long val = (unsigned long)mte_to_node(enode)->parent; - /* Root. */ - if (val & 1) + if (val & MA_ROOT_PARENT) return 0; /* @@ -670,12 +674,13 @@ static inline unsigned long mte_pivot(const struct maple_enode *mn, unsigned char piv) { struct maple_node *node = mte_to_node(mn); + enum maple_type type = mte_node_type(mn); - if (piv >= mt_pivots[piv]) { + if (piv >= mt_pivots[type]) { WARN_ON(1); return 0; } - switch (mte_node_type(mn)) { + switch (type) { case maple_arange_64: return node->ma64.pivot[piv]; case maple_range_64: @@ -1127,9 +1132,10 @@ static inline struct maple_node *mas_pop_node(struct ma_state *mas) { struct maple_alloc *ret, *node = mas->alloc; unsigned long total = mas_allocated(mas); + unsigned int req = mas_alloc_req(mas); /* nothing or a request pending. */ - if (unlikely(!total)) + if (WARN_ON(!total)) return NULL; if (total == 1) { @@ -1139,27 +1145,25 @@ static inline struct maple_node *mas_pop_node(struct ma_state *mas) goto single_node; } - if (!node->node_count) { + if (node->node_count == 1) { /* Single allocation in this node. */ mas->alloc = node->slot[0]; - node->slot[0] = NULL; mas->alloc->total = node->total - 1; ret = node; goto new_head; } - node->total--; - ret = node->slot[node->node_count]; - node->slot[node->node_count--] = NULL; + ret = node->slot[--node->node_count]; + node->slot[node->node_count] = NULL; single_node: new_head: - ret->total = 0; - ret->node_count = 0; - if (ret->request_count) { - mas_set_alloc_req(mas, ret->request_count + 1); - ret->request_count = 0; + if (req) { + req++; + mas_set_alloc_req(mas, req); } + + memset(ret, 0, sizeof(*ret)); return (struct maple_node *)ret; } @@ -1178,21 +1182,20 @@ static inline void mas_push_node(struct ma_state *mas, struct maple_node *used) unsigned long count; unsigned int requested = mas_alloc_req(mas); - memset(reuse, 0, sizeof(*reuse)); count = mas_allocated(mas); - if (count && (head->node_count < MAPLE_ALLOC_SLOTS - 1)) { - if (head->slot[0]) - head->node_count++; - head->slot[head->node_count] = reuse; + reuse->request_count = 0; + reuse->node_count = 0; + if (count && (head->node_count < MAPLE_ALLOC_SLOTS)) { + head->slot[head->node_count++] = reuse; head->total++; goto done; } reuse->total = 1; if ((head) && !((unsigned long)head & 0x1)) { - head->request_count = 0; reuse->slot[0] = head; + reuse->node_count = 1; reuse->total += head->total; } @@ -1211,7 +1214,6 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) { struct maple_alloc *node; unsigned long allocated = mas_allocated(mas); - unsigned long success = allocated; unsigned int requested = mas_alloc_req(mas); unsigned int count; void **slots = NULL; @@ -1227,24 +1229,29 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) WARN_ON(!allocated); } - if (!allocated || mas->alloc->node_count == MAPLE_ALLOC_SLOTS - 1) { + if (!allocated || mas->alloc->node_count == MAPLE_ALLOC_SLOTS) { node = (struct maple_alloc *)mt_alloc_one(gfp); if (!node) goto nomem_one; - if (allocated) + if (allocated) { node->slot[0] = mas->alloc; + node->node_count = 1; + } else { + node->node_count = 0; + } - success++; mas->alloc = node; + node->total = ++allocated; requested--; } node = mas->alloc; + node->request_count = 0; while (requested) { max_req = MAPLE_ALLOC_SLOTS; - if (node->slot[0]) { - unsigned int offset = node->node_count + 1; + if (node->node_count) { + unsigned int offset = node->node_count; slots = (void **)&node->slot[offset]; max_req -= offset; @@ -1258,15 +1265,13 @@ static inline void mas_alloc_nodes(struct ma_state *mas, gfp_t gfp) goto nomem_bulk; node->node_count += count; - /* zero indexed. */ - if (slots == (void **)&node->slot) - node->node_count--; - - success += count; + allocated += count; node = node->slot[0]; + node->node_count = 0; + node->request_count = 0; requested -= count; } - mas->alloc->total = success; + mas->alloc->total = allocated; return; nomem_bulk: @@ -1275,10 +1280,8 @@ nomem_bulk: nomem_one: mas_set_alloc_req(mas, requested); if (mas->alloc && !(((unsigned long)mas->alloc & 0x1))) - mas->alloc->total = success; + mas->alloc->total = allocated; mas_set_err(mas, -ENOMEM); - return; - } /* @@ -1333,7 +1336,7 @@ static void mas_node_count(struct ma_state *mas, int count) * mas_start() - Sets up maple state for operations. * @mas: The maple state. * - * If mas->node == MAS_START, then set the min, max, depth, and offset to + * If mas->node == MAS_START, then set the min, max and depth to * defaults. * * Return: @@ -1347,22 +1350,22 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) if (likely(mas_is_start(mas))) { struct maple_enode *root; - mas->node = MAS_NONE; mas->min = 0; mas->max = ULONG_MAX; mas->depth = 0; - mas->offset = 0; root = mas_root(mas); /* Tree with nodes */ if (likely(xa_is_node(root))) { mas->depth = 1; mas->node = mte_safe_root(root); + mas->offset = 0; return NULL; } /* empty tree */ if (unlikely(!root)) { + mas->node = MAS_NONE; mas->offset = MAPLE_NODE_SLOTS; return NULL; } @@ -1886,10 +1889,9 @@ static inline int mab_calc_split(struct ma_state *mas, /* Avoid ending a node on a NULL entry */ split = mab_no_null_split(bn, split, slot_count); - if (!(*mid_split)) - return split; - *mid_split = mab_no_null_split(bn, *mid_split, slot_count); + if (unlikely(*mid_split)) + *mid_split = mab_no_null_split(bn, *mid_split, slot_count); return split; } @@ -2112,7 +2114,7 @@ static inline void mas_bulk_rebalance(struct ma_state *mas, unsigned char end, * * Return: The actual end of the data stored in @b_node */ -static inline void mas_store_b_node(struct ma_wr_state *wr_mas, +static noinline_for_kasan void mas_store_b_node(struct ma_wr_state *wr_mas, struct maple_big_node *b_node, unsigned char offset_end) { unsigned char slot; @@ -2946,7 +2948,7 @@ next: mas->min = prev_min; mas->max = prev_max; mas->node = last; - return (void *) next; + return (void *)next; dead_node: mas_reset(mas); @@ -3466,7 +3468,6 @@ static inline bool mas_push_data(struct ma_state *mas, int height, */ static int mas_split(struct ma_state *mas, struct maple_big_node *b_node) { - struct maple_subtree_state mast; int height = 0; unsigned char mid_split, split = 0; @@ -3585,7 +3586,7 @@ static inline bool mas_reuse_node(struct ma_wr_state *wr_mas, * @b_node: The maple big node * @end: The end of the data. */ -static inline int mas_commit_b_node(struct ma_wr_state *wr_mas, +static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas, struct maple_big_node *b_node, unsigned char end) { struct maple_node *node; @@ -3892,7 +3893,7 @@ next: goto dead_node; } while (!ma_is_leaf(type)); - return (void *) next; + return (void *)next; dead_node: mas_reset(mas); @@ -4661,13 +4662,13 @@ static inline void *mas_next_nentry(struct ma_state *mas, pivots = ma_pivots(node, type); slots = ma_slots(node, type); mas->index = mas_safe_min(mas, pivots, mas->offset); + count = ma_data_end(node, type, pivots, mas->max); if (ma_dead_node(node)) return NULL; if (mas->index > max) return NULL; - count = ma_data_end(node, type, pivots, mas->max); if (mas->offset > count) return NULL; @@ -4710,15 +4711,11 @@ found: static inline void mas_rewalk(struct ma_state *mas, unsigned long index) { - retry: mas_set(mas, index); mas_state_walk(mas); if (mas_is_start(mas)) goto retry; - - return; - } /* @@ -4742,6 +4739,11 @@ static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) unsigned long last; enum maple_type mt; + if (mas->index > limit) { + mas->index = mas->last = limit; + mas_pause(mas); + return NULL; + } last = mas->last; retry: offset = mas->offset; @@ -4848,6 +4850,11 @@ static inline void *mas_prev_entry(struct ma_state *mas, unsigned long min) { void *entry; + if (mas->index < min) { + mas->index = mas->last = min; + mas->node = MAS_NONE; + return NULL; + } retry: while (likely(!mas_is_none(mas))) { entry = mas_prev_nentry(mas, min, mas->index); @@ -4887,7 +4894,7 @@ static bool mas_rev_awalk(struct ma_state *mas, unsigned long size) unsigned long *pivots, *gaps; void __rcu **slots; unsigned long gap = 0; - unsigned long max, min, index; + unsigned long max, min; unsigned char offset; if (unlikely(mas_is_err(mas))) @@ -4909,8 +4916,7 @@ static bool mas_rev_awalk(struct ma_state *mas, unsigned long size) min = mas_safe_min(mas, pivots, --offset); max = mas_safe_pivot(mas, pivots, offset, type); - index = mas->index; - while (index <= max) { + while (mas->index <= max) { gap = 0; if (gaps) gap = gaps[offset]; @@ -4941,10 +4947,8 @@ static bool mas_rev_awalk(struct ma_state *mas, unsigned long size) min = mas_safe_min(mas, pivots, offset); } - if (unlikely(index > max)) { - mas_set_err(mas, -EBUSY); - return false; - } + if (unlikely((mas->index > max) || (size - 1 > max - mas->index))) + goto no_space; if (unlikely(ma_is_leaf(type))) { mas->offset = offset; @@ -4961,9 +4965,11 @@ static bool mas_rev_awalk(struct ma_state *mas, unsigned long size) return false; ascend: - if (mte_is_root(mas->node)) - mas_set_err(mas, -EBUSY); + if (!mte_is_root(mas->node)) + return false; +no_space: + mas_set_err(mas, -EBUSY); return false; } @@ -5590,8 +5596,8 @@ free_leaf: /* * mte_destroy_walk() - Free a tree or sub-tree. - * @enode - the encoded maple node (maple_enode) to start - * @mn - the tree to free - needed for node types. + * @enode: the encoded maple node (maple_enode) to start + * @mt: the tree to free - needed for node types. * * Must hold the write lock. */ @@ -5610,6 +5616,9 @@ static inline void mte_destroy_walk(struct maple_enode *enode, static void mas_wr_store_setup(struct ma_wr_state *wr_mas) { + if (unlikely(mas_is_paused(wr_mas->mas))) + mas_reset(wr_mas->mas); + if (!mas_is_start(wr_mas->mas)) { if (mas_is_none(wr_mas->mas)) { mas_reset(wr_mas->mas); @@ -5620,7 +5629,6 @@ static void mas_wr_store_setup(struct ma_wr_state *wr_mas) mas_reset(wr_mas->mas); } } - } /* Interface */ @@ -5712,12 +5720,11 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc); /** * mas_preallocate() - Preallocate enough nodes for a store operation * @mas: The maple state - * @entry: The entry that will be stored * @gfp: The GFP_FLAGS to use for allocations. * * Return: 0 on success, -ENOMEM if memory could not be allocated. */ -int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) +int mas_preallocate(struct ma_state *mas, gfp_t gfp) { int ret; @@ -5745,6 +5752,7 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) void mas_destroy(struct ma_state *mas) { struct maple_alloc *node; + unsigned long total; /* * When using mas_for_each() to insert an expected number of elements, @@ -5767,14 +5775,20 @@ void mas_destroy(struct ma_state *mas) } mas->mas_flags &= ~(MA_STATE_BULK|MA_STATE_PREALLOC); - while (mas->alloc && !((unsigned long)mas->alloc & 0x1)) { + total = mas_allocated(mas); + while (total) { node = mas->alloc; mas->alloc = node->slot[0]; - if (node->node_count > 0) - mt_free_bulk(node->node_count, - (void __rcu **)&node->slot[1]); + if (node->node_count > 1) { + size_t count = node->node_count - 1; + + mt_free_bulk(count, (void __rcu **)&node->slot[1]); + total -= count; + } kmem_cache_free(maple_node_cache, node); + total--; } + mas->alloc = NULL; } EXPORT_SYMBOL_GPL(mas_destroy); @@ -5912,6 +5926,7 @@ void *mas_prev(struct ma_state *mas, unsigned long min) if (!mas->index) { /* Nothing comes before 0 */ mas->last = 0; + mas->node = MAS_NONE; return NULL; } @@ -6002,6 +6017,9 @@ void *mas_find(struct ma_state *mas, unsigned long max) mas->index = ++mas->last; } + if (unlikely(mas_is_none(mas))) + mas->node = MAS_START; + if (unlikely(mas_is_start(mas))) { /* First run or continue */ void *entry; @@ -6734,7 +6752,7 @@ static void mt_dump_range64(const struct maple_tree *mt, void *entry, if (i < (MAPLE_RANGE64_SLOTS - 1)) last = node->pivot[i]; - else if (!node->slot[i] && max != mt_max[mte_node_type(entry)]) + else if (!node->slot[i] && max != mt_node_max(entry)) break; if (last == 0 && i > 0) break; @@ -6841,7 +6859,7 @@ void mt_dump(const struct maple_tree *mt) if (!xa_is_node(entry)) mt_dump_entry(entry, 0, 0, 0); else if (entry) - mt_dump_node(mt, entry, 0, mt_max[mte_node_type(entry)], 0); + mt_dump_node(mt, entry, 0, mt_node_max(entry), 0); } EXPORT_SYMBOL_GPL(mt_dump); diff --git a/lib/memcpy_kunit.c b/lib/memcpy_kunit.c index 89128551448d..887926f04731 100644 --- a/lib/memcpy_kunit.c +++ b/lib/memcpy_kunit.c @@ -309,6 +309,8 @@ static void set_random_nonzero(struct kunit *test, u8 *byte) static void init_large(struct kunit *test) { + if (!IS_ENABLED(CONFIG_MEMCPY_SLOW_KUNIT_TEST)) + kunit_skip(test, "Slow test skipped. Enable with CONFIG_MEMCPY_SLOW_KUNIT_TEST=y"); /* Get many bit patterns. */ get_random_bytes(large_src, ARRAY_SIZE(large_src)); diff --git a/lib/mpi/mpicoder.c b/lib/mpi/mpicoder.c index 39c4c6731094..3cb6bd148fa9 100644 --- a/lib/mpi/mpicoder.c +++ b/lib/mpi/mpicoder.c @@ -504,7 +504,8 @@ MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) while (sg_miter_next(&miter)) { buff = miter.addr; - len = miter.length; + len = min_t(unsigned, miter.length, nbytes); + nbytes -= len; for (x = 0; x < len; x++) { a <<= 8; diff --git a/lib/nlattr.c b/lib/nlattr.c index 9055e8b4d144..489e15bde5c1 100644 --- a/lib/nlattr.c +++ b/lib/nlattr.c @@ -10,6 +10,7 @@ #include <linux/kernel.h> #include <linux/errno.h> #include <linux/jiffies.h> +#include <linux/nospec.h> #include <linux/skbuff.h> #include <linux/string.h> #include <linux/types.h> @@ -381,6 +382,7 @@ static int validate_nla(const struct nlattr *nla, int maxtype, if (type <= 0 || type > maxtype) return 0; + type = array_index_nospec(type, maxtype + 1); pt = &policy[type]; BUG_ON(pt->type > NLA_TYPE_MAX); @@ -596,6 +598,7 @@ static int __nla_validate_parse(const struct nlattr *head, int len, int maxtype, } continue; } + type = array_index_nospec(type, maxtype + 1); if (policy) { int err = validate_nla(nla, maxtype, policy, validate, extack, depth); diff --git a/lib/nmi_backtrace.c b/lib/nmi_backtrace.c index d01aec6ae15c..5274bbb026d7 100644 --- a/lib/nmi_backtrace.c +++ b/lib/nmi_backtrace.c @@ -64,6 +64,7 @@ void nmi_trigger_cpumask_backtrace(const cpumask_t *mask, if (!cpumask_empty(to_cpumask(backtrace_mask))) { pr_info("Sending NMI from CPU %d to CPUs %*pbl:\n", this_cpu, nr_cpumask_bits, to_cpumask(backtrace_mask)); + nmi_backtrace_stall_snap(to_cpumask(backtrace_mask)); raise(to_cpumask(backtrace_mask)); } @@ -74,6 +75,7 @@ void nmi_trigger_cpumask_backtrace(const cpumask_t *mask, mdelay(1); touch_softlockup_watchdog(); } + nmi_backtrace_stall_check(to_cpumask(backtrace_mask)); /* * Force flush any remote buffers that might be stuck in IRQ context diff --git a/lib/parser.c b/lib/parser.c index bcb23484100e..2b5e2b480253 100644 --- a/lib/parser.c +++ b/lib/parser.c @@ -11,6 +11,15 @@ #include <linux/slab.h> #include <linux/string.h> +/* + * max size needed by different bases to express U64 + * HEX: "0xFFFFFFFFFFFFFFFF" --> 18 + * DEC: "18446744073709551615" --> 20 + * OCT: "01777777777777777777777" --> 23 + * pick the max one to define NUMBER_BUF_LEN + */ +#define NUMBER_BUF_LEN 24 + /** * match_one - Determines if a string matches a simple pattern * @s: the string to examine for presence of the pattern @@ -129,14 +138,12 @@ EXPORT_SYMBOL(match_token); static int match_number(substring_t *s, int *result, int base) { char *endp; - char *buf; + char buf[NUMBER_BUF_LEN]; int ret; long val; - buf = match_strdup(s); - if (!buf) - return -ENOMEM; - + if (match_strlcpy(buf, s, NUMBER_BUF_LEN) >= NUMBER_BUF_LEN) + return -ERANGE; ret = 0; val = simple_strtol(buf, &endp, base); if (endp == buf) @@ -145,7 +152,6 @@ static int match_number(substring_t *s, int *result, int base) ret = -ERANGE; else *result = (int) val; - kfree(buf); return ret; } @@ -163,18 +169,15 @@ static int match_number(substring_t *s, int *result, int base) */ static int match_u64int(substring_t *s, u64 *result, int base) { - char *buf; + char buf[NUMBER_BUF_LEN]; int ret; u64 val; - buf = match_strdup(s); - if (!buf) - return -ENOMEM; - + if (match_strlcpy(buf, s, NUMBER_BUF_LEN) >= NUMBER_BUF_LEN) + return -ERANGE; ret = kstrtoull(buf, base, &val); if (!ret) *result = val; - kfree(buf); return ret; } @@ -206,14 +209,12 @@ EXPORT_SYMBOL(match_int); */ int match_uint(substring_t *s, unsigned int *result) { - int err = -ENOMEM; - char *buf = match_strdup(s); + char buf[NUMBER_BUF_LEN]; - if (buf) { - err = kstrtouint(buf, 10, result); - kfree(buf); - } - return err; + if (match_strlcpy(buf, s, NUMBER_BUF_LEN) >= NUMBER_BUF_LEN) + return -ERANGE; + + return kstrtouint(buf, 10, result); } EXPORT_SYMBOL(match_uint); diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c index 42f729c8e56c..dba56c5c1837 100644 --- a/lib/percpu_counter.c +++ b/lib/percpu_counter.c @@ -73,28 +73,33 @@ void percpu_counter_set(struct percpu_counter *fbc, s64 amount) EXPORT_SYMBOL(percpu_counter_set); /* - * This function is both preempt and irq safe. The former is due to explicit - * preemption disable. The latter is guaranteed by the fact that the slow path - * is explicitly protected by an irq-safe spinlock whereas the fast patch uses - * this_cpu_add which is irq-safe by definition. Hence there is no need muck - * with irq state before calling this one + * local_irq_save() is needed to make the function irq safe: + * - The slow path would be ok as protected by an irq-safe spinlock. + * - this_cpu_add would be ok as it is irq-safe by definition. + * But: + * The decision slow path/fast path and the actual update must be atomic, too. + * Otherwise a call in process context could check the current values and + * decide that the fast path can be used. If now an interrupt occurs before + * the this_cpu_add(), and the interrupt updates this_cpu(*fbc->counters), + * then the this_cpu_add() that is executed after the interrupt has completed + * can produce values larger than "batch" or even overflows. */ void percpu_counter_add_batch(struct percpu_counter *fbc, s64 amount, s32 batch) { s64 count; + unsigned long flags; - preempt_disable(); + local_irq_save(flags); count = __this_cpu_read(*fbc->counters) + amount; if (abs(count) >= batch) { - unsigned long flags; - raw_spin_lock_irqsave(&fbc->lock, flags); + raw_spin_lock(&fbc->lock); fbc->count += count; __this_cpu_sub(*fbc->counters, count - amount); - raw_spin_unlock_irqrestore(&fbc->lock, flags); + raw_spin_unlock(&fbc->lock); } else { this_cpu_add(*fbc->counters, amount); } - preempt_enable(); + local_irq_restore(flags); } EXPORT_SYMBOL(percpu_counter_add_batch); diff --git a/lib/sbitmap.c b/lib/sbitmap.c index 1fcede228fa2..eff4e42c425a 100644 --- a/lib/sbitmap.c +++ b/lib/sbitmap.c @@ -167,15 +167,16 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth, return nr; } -static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index, - unsigned int alloc_hint) +static int sbitmap_find_bit_in_word(struct sbitmap_word *map, + unsigned int depth, + unsigned int alloc_hint, + bool wrap) { - struct sbitmap_word *map = &sb->map[index]; int nr; do { - nr = __sbitmap_get_word(&map->word, __map_depth(sb, index), - alloc_hint, !sb->round_robin); + nr = __sbitmap_get_word(&map->word, depth, + alloc_hint, wrap); if (nr != -1) break; if (!sbitmap_deferred_clear(map)) @@ -185,25 +186,22 @@ static int sbitmap_find_bit_in_index(struct sbitmap *sb, int index, return nr; } -static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint) +static int sbitmap_find_bit(struct sbitmap *sb, + unsigned int depth, + unsigned int index, + unsigned int alloc_hint, + bool wrap) { - unsigned int i, index; + unsigned int i; int nr = -1; - index = SB_NR_TO_INDEX(sb, alloc_hint); - - /* - * Unless we're doing round robin tag allocation, just use the - * alloc_hint to find the right word index. No point in looping - * twice in find_next_zero_bit() for that case. - */ - if (sb->round_robin) - alloc_hint = SB_NR_TO_BIT(sb, alloc_hint); - else - alloc_hint = 0; - for (i = 0; i < sb->map_nr; i++) { - nr = sbitmap_find_bit_in_index(sb, index, alloc_hint); + nr = sbitmap_find_bit_in_word(&sb->map[index], + min_t(unsigned int, + __map_depth(sb, index), + depth), + alloc_hint, wrap); + if (nr != -1) { nr += index << sb->shift; break; @@ -218,6 +216,26 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint) return nr; } +static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint) +{ + unsigned int index; + + index = SB_NR_TO_INDEX(sb, alloc_hint); + + /* + * Unless we're doing round robin tag allocation, just use the + * alloc_hint to find the right word index. No point in looping + * twice in find_next_zero_bit() for that case. + */ + if (sb->round_robin) + alloc_hint = SB_NR_TO_BIT(sb, alloc_hint); + else + alloc_hint = 0; + + return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint, + !sb->round_robin); +} + int sbitmap_get(struct sbitmap *sb) { int nr; @@ -239,37 +257,12 @@ static int __sbitmap_get_shallow(struct sbitmap *sb, unsigned int alloc_hint, unsigned long shallow_depth) { - unsigned int i, index; - int nr = -1; + unsigned int index; index = SB_NR_TO_INDEX(sb, alloc_hint); + alloc_hint = SB_NR_TO_BIT(sb, alloc_hint); - for (i = 0; i < sb->map_nr; i++) { -again: - nr = __sbitmap_get_word(&sb->map[index].word, - min_t(unsigned int, - __map_depth(sb, index), - shallow_depth), - SB_NR_TO_BIT(sb, alloc_hint), true); - if (nr != -1) { - nr += index << sb->shift; - break; - } - - if (sbitmap_deferred_clear(&sb->map[index])) - goto again; - - /* Jump to next index. */ - index++; - alloc_hint = index << sb->shift; - - if (index >= sb->map_nr) { - index = 0; - alloc_hint = 0; - } - } - - return nr; + return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true); } int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth) @@ -464,13 +457,10 @@ void sbitmap_queue_recalculate_wake_batch(struct sbitmap_queue *sbq, unsigned int users) { unsigned int wake_batch; - unsigned int min_batch; unsigned int depth = (sbq->sb.depth + users - 1) / users; - min_batch = sbq->sb.depth >= (4 * SBQ_WAIT_QUEUES) ? 4 : 1; - wake_batch = clamp_val(depth / SBQ_WAIT_QUEUES, - min_batch, SBQ_WAKE_BATCH); + 1, SBQ_WAKE_BATCH); WRITE_ONCE(sbq->wake_batch, wake_batch); } @@ -521,11 +511,9 @@ unsigned long __sbitmap_queue_get_batch(struct sbitmap_queue *sbq, int nr_tags, get_mask = ((1UL << nr_tags) - 1) << nr; val = READ_ONCE(map->word); - do { - if ((val & ~get_mask) != val) - goto next; - } while (!atomic_long_try_cmpxchg(ptr, &val, - get_mask | val)); + while (!atomic_long_try_cmpxchg(ptr, &val, + get_mask | val)) + ; get_mask = (get_mask & ~val) >> nr; if (get_mask) { *offset = nr + (index << sb->shift); diff --git a/lib/scatterlist.c b/lib/scatterlist.c index a0ad2a7959b5..8d7519a8f308 100644 --- a/lib/scatterlist.c +++ b/lib/scatterlist.c @@ -470,22 +470,27 @@ int sg_alloc_append_table_from_pages(struct sg_append_table *sgt_append, return -EOPNOTSUPP; if (sgt_append->prv) { + unsigned long next_pfn = (page_to_phys(sg_page(sgt_append->prv)) + + sgt_append->prv->offset + sgt_append->prv->length) / PAGE_SIZE; + if (WARN_ON(offset)) return -EINVAL; /* Merge contiguous pages into the last SG */ prv_len = sgt_append->prv->length; - last_pg = sg_page(sgt_append->prv); - while (n_pages && pages_are_mergeable(last_pg, pages[0])) { - if (sgt_append->prv->length + PAGE_SIZE > max_segment) - break; - sgt_append->prv->length += PAGE_SIZE; - last_pg = pages[0]; - pages++; - n_pages--; + if (page_to_pfn(pages[0]) == next_pfn) { + last_pg = pfn_to_page(next_pfn - 1); + while (n_pages && pages_are_mergeable(pages[0], last_pg)) { + if (sgt_append->prv->length + PAGE_SIZE > max_segment) + break; + sgt_append->prv->length += PAGE_SIZE; + last_pg = pages[0]; + pages++; + n_pages--; + } + if (!n_pages) + goto out; } - if (!n_pages) - goto out; } /* compute number of contiguous chunks */ diff --git a/lib/stackdepot.c b/lib/stackdepot.c index 79e894cf8406..036da8e295d1 100644 --- a/lib/stackdepot.c +++ b/lib/stackdepot.c @@ -1,24 +1,19 @@ // SPDX-License-Identifier: GPL-2.0-only /* - * Generic stack depot for storing stack traces. + * Stack depot - a stack trace storage that avoids duplication. * - * Some debugging tools need to save stack traces of certain events which can - * be later presented to the user. For example, KASAN needs to safe alloc and - * free stacks for each object, but storing two stack traces per object - * requires too much memory (e.g. SLUB_DEBUG needs 256 bytes per object for - * that). - * - * Instead, stack depot maintains a hashtable of unique stacktraces. Since alloc - * and free stacks repeat a lot, we save about 100x space. - * Stacks are never removed from depot, so we store them contiguously one after - * another in a contiguous memory allocation. + * Internally, stack depot maintains a hash table of unique stacktraces. The + * stack traces themselves are stored contiguously one after another in a set + * of separate page allocations. * * Author: Alexander Potapenko <glider@google.com> * Copyright (C) 2016 Google, Inc. * - * Based on code by Dmitry Chernenkov. + * Based on the code by Dmitry Chernenkov. */ +#define pr_fmt(fmt) "stackdepot: " fmt + #include <linux/gfp.h> #include <linux/jhash.h> #include <linux/kernel.h> @@ -34,243 +29,288 @@ #include <linux/memblock.h> #include <linux/kasan-enabled.h> -#define DEPOT_STACK_BITS (sizeof(depot_stack_handle_t) * 8) - -#define STACK_ALLOC_NULL_PROTECTION_BITS 1 -#define STACK_ALLOC_ORDER 2 /* 'Slab' size order for stack depot, 4 pages */ -#define STACK_ALLOC_SIZE (1LL << (PAGE_SHIFT + STACK_ALLOC_ORDER)) -#define STACK_ALLOC_ALIGN 4 -#define STACK_ALLOC_OFFSET_BITS (STACK_ALLOC_ORDER + PAGE_SHIFT - \ - STACK_ALLOC_ALIGN) -#define STACK_ALLOC_INDEX_BITS (DEPOT_STACK_BITS - \ - STACK_ALLOC_NULL_PROTECTION_BITS - \ - STACK_ALLOC_OFFSET_BITS - STACK_DEPOT_EXTRA_BITS) -#define STACK_ALLOC_SLABS_CAP 8192 -#define STACK_ALLOC_MAX_SLABS \ - (((1LL << (STACK_ALLOC_INDEX_BITS)) < STACK_ALLOC_SLABS_CAP) ? \ - (1LL << (STACK_ALLOC_INDEX_BITS)) : STACK_ALLOC_SLABS_CAP) - -/* The compact structure to store the reference to stacks. */ +#define DEPOT_HANDLE_BITS (sizeof(depot_stack_handle_t) * 8) + +#define DEPOT_VALID_BITS 1 +#define DEPOT_POOL_ORDER 2 /* Pool size order, 4 pages */ +#define DEPOT_POOL_SIZE (1LL << (PAGE_SHIFT + DEPOT_POOL_ORDER)) +#define DEPOT_STACK_ALIGN 4 +#define DEPOT_OFFSET_BITS (DEPOT_POOL_ORDER + PAGE_SHIFT - DEPOT_STACK_ALIGN) +#define DEPOT_POOL_INDEX_BITS (DEPOT_HANDLE_BITS - DEPOT_VALID_BITS - \ + DEPOT_OFFSET_BITS - STACK_DEPOT_EXTRA_BITS) +#define DEPOT_POOLS_CAP 8192 +#define DEPOT_MAX_POOLS \ + (((1LL << (DEPOT_POOL_INDEX_BITS)) < DEPOT_POOLS_CAP) ? \ + (1LL << (DEPOT_POOL_INDEX_BITS)) : DEPOT_POOLS_CAP) + +/* Compact structure that stores a reference to a stack. */ union handle_parts { depot_stack_handle_t handle; struct { - u32 slabindex : STACK_ALLOC_INDEX_BITS; - u32 offset : STACK_ALLOC_OFFSET_BITS; - u32 valid : STACK_ALLOC_NULL_PROTECTION_BITS; - u32 extra : STACK_DEPOT_EXTRA_BITS; + u32 pool_index : DEPOT_POOL_INDEX_BITS; + u32 offset : DEPOT_OFFSET_BITS; + u32 valid : DEPOT_VALID_BITS; + u32 extra : STACK_DEPOT_EXTRA_BITS; }; }; struct stack_record { - struct stack_record *next; /* Link in the hashtable */ - u32 hash; /* Hash in the hastable */ - u32 size; /* Number of frames in the stack */ + struct stack_record *next; /* Link in the hash table */ + u32 hash; /* Hash in the hash table */ + u32 size; /* Number of stored frames */ union handle_parts handle; - unsigned long entries[]; /* Variable-sized array of entries. */ + unsigned long entries[]; /* Variable-sized array of frames */ }; -static bool __stack_depot_want_early_init __initdata = IS_ENABLED(CONFIG_STACKDEPOT_ALWAYS_INIT); +static bool stack_depot_disabled; +static bool __stack_depot_early_init_requested __initdata = IS_ENABLED(CONFIG_STACKDEPOT_ALWAYS_INIT); static bool __stack_depot_early_init_passed __initdata; -static void *stack_slabs[STACK_ALLOC_MAX_SLABS]; - -static int depot_index; -static int next_slab_inited; -static size_t depot_offset; -static DEFINE_RAW_SPINLOCK(depot_lock); - -unsigned int stack_depot_get_extra_bits(depot_stack_handle_t handle) -{ - union handle_parts parts = { .handle = handle }; - - return parts.extra; -} -EXPORT_SYMBOL(stack_depot_get_extra_bits); - -static bool init_stack_slab(void **prealloc) -{ - if (!*prealloc) - return false; - /* - * This smp_load_acquire() pairs with smp_store_release() to - * |next_slab_inited| below and in depot_alloc_stack(). - */ - if (smp_load_acquire(&next_slab_inited)) - return true; - if (stack_slabs[depot_index] == NULL) { - stack_slabs[depot_index] = *prealloc; - *prealloc = NULL; - } else { - /* If this is the last depot slab, do not touch the next one. */ - if (depot_index + 1 < STACK_ALLOC_MAX_SLABS) { - stack_slabs[depot_index + 1] = *prealloc; - *prealloc = NULL; - } - /* - * This smp_store_release pairs with smp_load_acquire() from - * |next_slab_inited| above and in stack_depot_save(). - */ - smp_store_release(&next_slab_inited, 1); - } - return true; -} - -/* Allocation of a new stack in raw storage */ -static struct stack_record * -depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) -{ - struct stack_record *stack; - size_t required_size = struct_size(stack, entries, size); - - required_size = ALIGN(required_size, 1 << STACK_ALLOC_ALIGN); - - if (unlikely(depot_offset + required_size > STACK_ALLOC_SIZE)) { - if (unlikely(depot_index + 1 >= STACK_ALLOC_MAX_SLABS)) { - WARN_ONCE(1, "Stack depot reached limit capacity"); - return NULL; - } - depot_index++; - depot_offset = 0; - /* - * smp_store_release() here pairs with smp_load_acquire() from - * |next_slab_inited| in stack_depot_save() and - * init_stack_slab(). - */ - if (depot_index + 1 < STACK_ALLOC_MAX_SLABS) - smp_store_release(&next_slab_inited, 0); - } - init_stack_slab(prealloc); - if (stack_slabs[depot_index] == NULL) - return NULL; - - stack = stack_slabs[depot_index] + depot_offset; - - stack->hash = hash; - stack->size = size; - stack->handle.slabindex = depot_index; - stack->handle.offset = depot_offset >> STACK_ALLOC_ALIGN; - stack->handle.valid = 1; - stack->handle.extra = 0; - memcpy(stack->entries, entries, flex_array_size(stack, entries, size)); - depot_offset += required_size; - - return stack; -} - -/* one hash table bucket entry per 16kB of memory */ -#define STACK_HASH_SCALE 14 -/* limited between 4k and 1M buckets */ -#define STACK_HASH_ORDER_MIN 12 -#define STACK_HASH_ORDER_MAX 20 +/* Use one hash table bucket per 16 KB of memory. */ +#define STACK_HASH_TABLE_SCALE 14 +/* Limit the number of buckets between 4K and 1M. */ +#define STACK_BUCKET_NUMBER_ORDER_MIN 12 +#define STACK_BUCKET_NUMBER_ORDER_MAX 20 +/* Initial seed for jhash2. */ #define STACK_HASH_SEED 0x9747b28c -static unsigned int stack_hash_order; +/* Hash table of pointers to stored stack traces. */ +static struct stack_record **stack_table; +/* Fixed order of the number of table buckets. Used when KASAN is enabled. */ +static unsigned int stack_bucket_number_order; +/* Hash mask for indexing the table. */ static unsigned int stack_hash_mask; -static bool stack_depot_disable; -static struct stack_record **stack_table; +/* Array of memory regions that store stack traces. */ +static void *stack_pools[DEPOT_MAX_POOLS]; +/* Currently used pool in stack_pools. */ +static int pool_index; +/* Offset to the unused space in the currently used pool. */ +static size_t pool_offset; +/* Lock that protects the variables above. */ +static DEFINE_RAW_SPINLOCK(pool_lock); +/* + * Stack depot tries to keep an extra pool allocated even before it runs out + * of space in the currently used pool. + * This flag marks that this next extra pool needs to be allocated and + * initialized. It has the value 0 when either the next pool is not yet + * initialized or the limit on the number of pools is reached. + */ +static int next_pool_required = 1; -static int __init is_stack_depot_disabled(char *str) +static int __init disable_stack_depot(char *str) { int ret; - ret = kstrtobool(str, &stack_depot_disable); - if (!ret && stack_depot_disable) { - pr_info("Stack Depot is disabled\n"); + ret = kstrtobool(str, &stack_depot_disabled); + if (!ret && stack_depot_disabled) { + pr_info("disabled\n"); stack_table = NULL; } return 0; } -early_param("stack_depot_disable", is_stack_depot_disabled); +early_param("stack_depot_disable", disable_stack_depot); -void __init stack_depot_want_early_init(void) +void __init stack_depot_request_early_init(void) { - /* Too late to request early init now */ + /* Too late to request early init now. */ WARN_ON(__stack_depot_early_init_passed); - __stack_depot_want_early_init = true; + __stack_depot_early_init_requested = true; } +/* Allocates a hash table via memblock. Can only be used during early boot. */ int __init stack_depot_early_init(void) { unsigned long entries = 0; - /* This is supposed to be called only once, from mm_init() */ + /* This function must be called only once, from mm_init(). */ if (WARN_ON(__stack_depot_early_init_passed)) return 0; - __stack_depot_early_init_passed = true; - if (kasan_enabled() && !stack_hash_order) - stack_hash_order = STACK_HASH_ORDER_MAX; + /* + * If KASAN is enabled, use the maximum order: KASAN is frequently used + * in fuzzing scenarios, which leads to a large number of different + * stack traces being stored in stack depot. + */ + if (kasan_enabled() && !stack_bucket_number_order) + stack_bucket_number_order = STACK_BUCKET_NUMBER_ORDER_MAX; - if (!__stack_depot_want_early_init || stack_depot_disable) + if (!__stack_depot_early_init_requested || stack_depot_disabled) return 0; - if (stack_hash_order) - entries = 1UL << stack_hash_order; + /* + * If stack_bucket_number_order is not set, leave entries as 0 to rely + * on the automatic calculations performed by alloc_large_system_hash. + */ + if (stack_bucket_number_order) + entries = 1UL << stack_bucket_number_order; + pr_info("allocating hash table via alloc_large_system_hash\n"); stack_table = alloc_large_system_hash("stackdepot", sizeof(struct stack_record *), entries, - STACK_HASH_SCALE, + STACK_HASH_TABLE_SCALE, HASH_EARLY | HASH_ZERO, NULL, &stack_hash_mask, - 1UL << STACK_HASH_ORDER_MIN, - 1UL << STACK_HASH_ORDER_MAX); - + 1UL << STACK_BUCKET_NUMBER_ORDER_MIN, + 1UL << STACK_BUCKET_NUMBER_ORDER_MAX); if (!stack_table) { - pr_err("Stack Depot hash table allocation failed, disabling\n"); - stack_depot_disable = true; + pr_err("hash table allocation failed, disabling\n"); + stack_depot_disabled = true; return -ENOMEM; } return 0; } +/* Allocates a hash table via kvcalloc. Can be used after boot. */ int stack_depot_init(void) { static DEFINE_MUTEX(stack_depot_init_mutex); + unsigned long entries; int ret = 0; mutex_lock(&stack_depot_init_mutex); - if (!stack_depot_disable && !stack_table) { - unsigned long entries; - int scale = STACK_HASH_SCALE; - - if (stack_hash_order) { - entries = 1UL << stack_hash_order; - } else { - entries = nr_free_buffer_pages(); - entries = roundup_pow_of_two(entries); - - if (scale > PAGE_SHIFT) - entries >>= (scale - PAGE_SHIFT); - else - entries <<= (PAGE_SHIFT - scale); - } - if (entries < 1UL << STACK_HASH_ORDER_MIN) - entries = 1UL << STACK_HASH_ORDER_MIN; - if (entries > 1UL << STACK_HASH_ORDER_MAX) - entries = 1UL << STACK_HASH_ORDER_MAX; - - pr_info("Stack Depot allocating hash table of %lu entries with kvcalloc\n", - entries); - stack_table = kvcalloc(entries, sizeof(struct stack_record *), GFP_KERNEL); - if (!stack_table) { - pr_err("Stack Depot hash table allocation failed, disabling\n"); - stack_depot_disable = true; - ret = -ENOMEM; - } - stack_hash_mask = entries - 1; + if (stack_depot_disabled || stack_table) + goto out_unlock; + + /* + * Similarly to stack_depot_early_init, use stack_bucket_number_order + * if assigned, and rely on automatic scaling otherwise. + */ + if (stack_bucket_number_order) { + entries = 1UL << stack_bucket_number_order; + } else { + int scale = STACK_HASH_TABLE_SCALE; + + entries = nr_free_buffer_pages(); + entries = roundup_pow_of_two(entries); + + if (scale > PAGE_SHIFT) + entries >>= (scale - PAGE_SHIFT); + else + entries <<= (PAGE_SHIFT - scale); + } + + if (entries < 1UL << STACK_BUCKET_NUMBER_ORDER_MIN) + entries = 1UL << STACK_BUCKET_NUMBER_ORDER_MIN; + if (entries > 1UL << STACK_BUCKET_NUMBER_ORDER_MAX) + entries = 1UL << STACK_BUCKET_NUMBER_ORDER_MAX; + + pr_info("allocating hash table of %lu entries via kvcalloc\n", entries); + stack_table = kvcalloc(entries, sizeof(struct stack_record *), GFP_KERNEL); + if (!stack_table) { + pr_err("hash table allocation failed, disabling\n"); + stack_depot_disabled = true; + ret = -ENOMEM; + goto out_unlock; } + stack_hash_mask = entries - 1; + +out_unlock: mutex_unlock(&stack_depot_init_mutex); + return ret; } EXPORT_SYMBOL_GPL(stack_depot_init); -/* Calculate hash for a stack */ +/* Uses preallocated memory to initialize a new stack depot pool. */ +static void depot_init_pool(void **prealloc) +{ + /* + * If the next pool is already initialized or the maximum number of + * pools is reached, do not use the preallocated memory. + * smp_load_acquire() here pairs with smp_store_release() below and + * in depot_alloc_stack(). + */ + if (!smp_load_acquire(&next_pool_required)) + return; + + /* Check if the current pool is not yet allocated. */ + if (stack_pools[pool_index] == NULL) { + /* Use the preallocated memory for the current pool. */ + stack_pools[pool_index] = *prealloc; + *prealloc = NULL; + } else { + /* + * Otherwise, use the preallocated memory for the next pool + * as long as we do not exceed the maximum number of pools. + */ + if (pool_index + 1 < DEPOT_MAX_POOLS) { + stack_pools[pool_index + 1] = *prealloc; + *prealloc = NULL; + } + /* + * At this point, either the next pool is initialized or the + * maximum number of pools is reached. In either case, take + * note that initializing another pool is not required. + * This smp_store_release pairs with smp_load_acquire() above + * and in stack_depot_save(). + */ + smp_store_release(&next_pool_required, 0); + } +} + +/* Allocates a new stack in a stack depot pool. */ +static struct stack_record * +depot_alloc_stack(unsigned long *entries, int size, u32 hash, void **prealloc) +{ + struct stack_record *stack; + size_t required_size = struct_size(stack, entries, size); + + required_size = ALIGN(required_size, 1 << DEPOT_STACK_ALIGN); + + /* Check if there is not enough space in the current pool. */ + if (unlikely(pool_offset + required_size > DEPOT_POOL_SIZE)) { + /* Bail out if we reached the pool limit. */ + if (unlikely(pool_index + 1 >= DEPOT_MAX_POOLS)) { + WARN_ONCE(1, "Stack depot reached limit capacity"); + return NULL; + } + + /* + * Move on to the next pool. + * WRITE_ONCE pairs with potential concurrent read in + * stack_depot_fetch(). + */ + WRITE_ONCE(pool_index, pool_index + 1); + pool_offset = 0; + /* + * If the maximum number of pools is not reached, take note + * that the next pool needs to initialized. + * smp_store_release() here pairs with smp_load_acquire() in + * stack_depot_save() and depot_init_pool(). + */ + if (pool_index + 1 < DEPOT_MAX_POOLS) + smp_store_release(&next_pool_required, 1); + } + + /* Assign the preallocated memory to a pool if required. */ + if (*prealloc) + depot_init_pool(prealloc); + + /* Check if we have a pool to save the stack trace. */ + if (stack_pools[pool_index] == NULL) + return NULL; + + /* Save the stack trace. */ + stack = stack_pools[pool_index] + pool_offset; + stack->hash = hash; + stack->size = size; + stack->handle.pool_index = pool_index; + stack->handle.offset = pool_offset >> DEPOT_STACK_ALIGN; + stack->handle.valid = 1; + stack->handle.extra = 0; + memcpy(stack->entries, entries, flex_array_size(stack, entries, size)); + pool_offset += required_size; + + return stack; +} + +/* Calculates the hash for a stack. */ static inline u32 hash_stack(unsigned long *entries, unsigned int size) { return jhash2((u32 *)entries, @@ -278,9 +318,9 @@ static inline u32 hash_stack(unsigned long *entries, unsigned int size) STACK_HASH_SEED); } -/* Use our own, non-instrumented version of memcmp(). - * - * We actually don't care about the order, just the equality. +/* + * Non-instrumented version of memcmp(). + * Does not check the lexicographical order, only the equality. */ static inline int stackdepot_memcmp(const unsigned long *u1, const unsigned long *u2, @@ -293,7 +333,7 @@ int stackdepot_memcmp(const unsigned long *u1, const unsigned long *u2, return 0; } -/* Find a stack that is equal to the one stored in entries in the hash */ +/* Finds a stack in a bucket of the hash table. */ static inline struct stack_record *find_stack(struct stack_record *bucket, unsigned long *entries, int size, u32 hash) @@ -309,116 +349,8 @@ static inline struct stack_record *find_stack(struct stack_record *bucket, return NULL; } -/** - * stack_depot_snprint - print stack entries from a depot into a buffer - * - * @handle: Stack depot handle which was returned from - * stack_depot_save(). - * @buf: Pointer to the print buffer - * - * @size: Size of the print buffer - * - * @spaces: Number of leading spaces to print - * - * Return: Number of bytes printed. - */ -int stack_depot_snprint(depot_stack_handle_t handle, char *buf, size_t size, - int spaces) -{ - unsigned long *entries; - unsigned int nr_entries; - - nr_entries = stack_depot_fetch(handle, &entries); - return nr_entries ? stack_trace_snprint(buf, size, entries, nr_entries, - spaces) : 0; -} -EXPORT_SYMBOL_GPL(stack_depot_snprint); - -/** - * stack_depot_print - print stack entries from a depot - * - * @stack: Stack depot handle which was returned from - * stack_depot_save(). - * - */ -void stack_depot_print(depot_stack_handle_t stack) -{ - unsigned long *entries; - unsigned int nr_entries; - - nr_entries = stack_depot_fetch(stack, &entries); - if (nr_entries > 0) - stack_trace_print(entries, nr_entries, 0); -} -EXPORT_SYMBOL_GPL(stack_depot_print); - -/** - * stack_depot_fetch - Fetch stack entries from a depot - * - * @handle: Stack depot handle which was returned from - * stack_depot_save(). - * @entries: Pointer to store the entries address - * - * Return: The number of trace entries for this depot. - */ -unsigned int stack_depot_fetch(depot_stack_handle_t handle, - unsigned long **entries) -{ - union handle_parts parts = { .handle = handle }; - void *slab; - size_t offset = parts.offset << STACK_ALLOC_ALIGN; - struct stack_record *stack; - - *entries = NULL; - if (!handle) - return 0; - - if (parts.slabindex > depot_index) { - WARN(1, "slab index %d out of bounds (%d) for stack id %08x\n", - parts.slabindex, depot_index, handle); - return 0; - } - slab = stack_slabs[parts.slabindex]; - if (!slab) - return 0; - stack = slab + offset; - - *entries = stack->entries; - return stack->size; -} -EXPORT_SYMBOL_GPL(stack_depot_fetch); - -/** - * __stack_depot_save - Save a stack trace from an array - * - * @entries: Pointer to storage array - * @nr_entries: Size of the storage array - * @extra_bits: Flags to store in unused bits of depot_stack_handle_t - * @alloc_flags: Allocation gfp flags - * @can_alloc: Allocate stack slabs (increased chance of failure if false) - * - * Saves a stack trace from @entries array of size @nr_entries. If @can_alloc is - * %true, is allowed to replenish the stack slab pool in case no space is left - * (allocates using GFP flags of @alloc_flags). If @can_alloc is %false, avoids - * any allocations and will fail if no space is left to store the stack trace. - * - * If the stack trace in @entries is from an interrupt, only the portion up to - * interrupt entry is saved. - * - * Additional opaque flags can be passed in @extra_bits, stored in the unused - * bits of the stack handle, and retrieved using stack_depot_get_extra_bits() - * without calling stack_depot_fetch(). - * - * Context: Any context, but setting @can_alloc to %false is required if - * alloc_pages() cannot be used from the current context. Currently - * this is the case from contexts where neither %GFP_ATOMIC nor - * %GFP_NOWAIT can be used (NMI, raw_spin_lock). - * - * Return: The handle of the stack struct stored in depot, 0 on failure. - */ depot_stack_handle_t __stack_depot_save(unsigned long *entries, unsigned int nr_entries, - unsigned int extra_bits, gfp_t alloc_flags, bool can_alloc) { struct stack_record *found = NULL, **bucket; @@ -430,15 +362,15 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, /* * If this stack trace is from an interrupt, including anything before - * interrupt entry usually leads to unbounded stackdepot growth. + * interrupt entry usually leads to unbounded stack depot growth. * - * Because use of filter_irq_stacks() is a requirement to ensure - * stackdepot can efficiently deduplicate interrupt stacks, always - * filter_irq_stacks() to simplify all callers' use of stackdepot. + * Since use of filter_irq_stacks() is a requirement to ensure stack + * depot can efficiently deduplicate interrupt stacks, always + * filter_irq_stacks() to simplify all callers' use of stack depot. */ nr_entries = filter_irq_stacks(entries, nr_entries); - if (unlikely(nr_entries == 0) || stack_depot_disable) + if (unlikely(nr_entries == 0) || stack_depot_disabled) goto fast_exit; hash = hash_stack(entries, nr_entries); @@ -449,20 +381,18 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, * The smp_load_acquire() here pairs with smp_store_release() to * |bucket| below. */ - found = find_stack(smp_load_acquire(bucket), entries, - nr_entries, hash); + found = find_stack(smp_load_acquire(bucket), entries, nr_entries, hash); if (found) goto exit; /* - * Check if the current or the next stack slab need to be initialized. - * If so, allocate the memory - we won't be able to do that under the - * lock. + * Check if another stack pool needs to be initialized. If so, allocate + * the memory now - we won't be able to do that under the lock. * * The smp_load_acquire() here pairs with smp_store_release() to - * |next_slab_inited| in depot_alloc_stack() and init_stack_slab(). + * |next_pool_inited| in depot_alloc_stack() and depot_init_pool(). */ - if (unlikely(can_alloc && !smp_load_acquire(&next_slab_inited))) { + if (unlikely(can_alloc && smp_load_acquire(&next_pool_required))) { /* * Zero out zone modifiers, as we don't have specific zone * requirements. Keep the flags related to allocation in atomic @@ -471,16 +401,17 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, alloc_flags &= ~GFP_ZONEMASK; alloc_flags &= (GFP_ATOMIC | GFP_KERNEL); alloc_flags |= __GFP_NOWARN; - page = alloc_pages(alloc_flags, STACK_ALLOC_ORDER); + page = alloc_pages(alloc_flags, DEPOT_POOL_ORDER); if (page) prealloc = page_address(page); } - raw_spin_lock_irqsave(&depot_lock, flags); + raw_spin_lock_irqsave(&pool_lock, flags); found = find_stack(*bucket, entries, nr_entries, hash); if (!found) { - struct stack_record *new = depot_alloc_stack(entries, nr_entries, hash, &prealloc); + struct stack_record *new = + depot_alloc_stack(entries, nr_entries, hash, &prealloc); if (new) { new->next = *bucket; @@ -493,43 +424,106 @@ depot_stack_handle_t __stack_depot_save(unsigned long *entries, } } else if (prealloc) { /* - * We didn't need to store this stack trace, but let's keep - * the preallocated memory for the future. + * Stack depot already contains this stack trace, but let's + * keep the preallocated memory for the future. */ - WARN_ON(!init_stack_slab(&prealloc)); + depot_init_pool(&prealloc); } - raw_spin_unlock_irqrestore(&depot_lock, flags); + raw_spin_unlock_irqrestore(&pool_lock, flags); exit: if (prealloc) { - /* Nobody used this memory, ok to free it. */ - free_pages((unsigned long)prealloc, STACK_ALLOC_ORDER); + /* Stack depot didn't use this memory, free it. */ + free_pages((unsigned long)prealloc, DEPOT_POOL_ORDER); } if (found) retval.handle = found->handle.handle; fast_exit: - retval.extra = extra_bits; - return retval.handle; } EXPORT_SYMBOL_GPL(__stack_depot_save); -/** - * stack_depot_save - Save a stack trace from an array - * - * @entries: Pointer to storage array - * @nr_entries: Size of the storage array - * @alloc_flags: Allocation gfp flags - * - * Context: Contexts where allocations via alloc_pages() are allowed. - * See __stack_depot_save() for more details. - * - * Return: The handle of the stack struct stored in depot, 0 on failure. - */ depot_stack_handle_t stack_depot_save(unsigned long *entries, unsigned int nr_entries, gfp_t alloc_flags) { - return __stack_depot_save(entries, nr_entries, 0, alloc_flags, true); + return __stack_depot_save(entries, nr_entries, alloc_flags, true); } EXPORT_SYMBOL_GPL(stack_depot_save); + +unsigned int stack_depot_fetch(depot_stack_handle_t handle, + unsigned long **entries) +{ + union handle_parts parts = { .handle = handle }; + /* + * READ_ONCE pairs with potential concurrent write in + * depot_alloc_stack. + */ + int pool_index_cached = READ_ONCE(pool_index); + void *pool; + size_t offset = parts.offset << DEPOT_STACK_ALIGN; + struct stack_record *stack; + + *entries = NULL; + if (!handle) + return 0; + + if (parts.pool_index > pool_index_cached) { + WARN(1, "pool index %d out of bounds (%d) for stack id %08x\n", + parts.pool_index, pool_index_cached, handle); + return 0; + } + pool = stack_pools[parts.pool_index]; + if (!pool) + return 0; + stack = pool + offset; + + *entries = stack->entries; + return stack->size; +} +EXPORT_SYMBOL_GPL(stack_depot_fetch); + +void stack_depot_print(depot_stack_handle_t stack) +{ + unsigned long *entries; + unsigned int nr_entries; + + nr_entries = stack_depot_fetch(stack, &entries); + if (nr_entries > 0) + stack_trace_print(entries, nr_entries, 0); +} +EXPORT_SYMBOL_GPL(stack_depot_print); + +int stack_depot_snprint(depot_stack_handle_t handle, char *buf, size_t size, + int spaces) +{ + unsigned long *entries; + unsigned int nr_entries; + + nr_entries = stack_depot_fetch(handle, &entries); + return nr_entries ? stack_trace_snprint(buf, size, entries, nr_entries, + spaces) : 0; +} +EXPORT_SYMBOL_GPL(stack_depot_snprint); + +depot_stack_handle_t __must_check stack_depot_set_extra_bits( + depot_stack_handle_t handle, unsigned int extra_bits) +{ + union handle_parts parts = { .handle = handle }; + + /* Don't set extra bits on empty handles. */ + if (!handle) + return 0; + + parts.extra = extra_bits; + return parts.handle; +} +EXPORT_SYMBOL(stack_depot_set_extra_bits); + +unsigned int stack_depot_get_extra_bits(depot_stack_handle_t handle) +{ + union handle_parts parts = { .handle = handle }; + + return parts.extra; +} +EXPORT_SYMBOL(stack_depot_get_extra_bits); diff --git a/lib/stackinit_kunit.c b/lib/stackinit_kunit.c index 4591d6cf5e01..05947a2feb93 100644 --- a/lib/stackinit_kunit.c +++ b/lib/stackinit_kunit.c @@ -31,8 +31,8 @@ static volatile u8 forced_mask = 0xff; static void *fill_start, *target_start; static size_t fill_size, target_size; -static bool range_contains(char *haystack_start, size_t haystack_size, - char *needle_start, size_t needle_size) +static bool stackinit_range_contains(char *haystack_start, size_t haystack_size, + char *needle_start, size_t needle_size) { if (needle_start >= haystack_start && needle_start + needle_size <= haystack_start + haystack_size) @@ -175,7 +175,7 @@ static noinline void test_ ## name (struct kunit *test) \ \ /* Validate that compiler lined up fill and target. */ \ KUNIT_ASSERT_TRUE_MSG(test, \ - range_contains(fill_start, fill_size, \ + stackinit_range_contains(fill_start, fill_size, \ target_start, target_size), \ "stack fill missed target!? " \ "(fill %zu wide, target offset by %d)\n", \ diff --git a/lib/string.c b/lib/string.c index 4fb566ea610f..3d55ef890106 100644 --- a/lib/string.c +++ b/lib/string.c @@ -480,13 +480,11 @@ EXPORT_SYMBOL(strcspn); */ char *strpbrk(const char *cs, const char *ct) { - const char *sc1, *sc2; + const char *sc; - for (sc1 = cs; *sc1 != '\0'; ++sc1) { - for (sc2 = ct; *sc2 != '\0'; ++sc2) { - if (*sc1 == *sc2) - return (char *)sc1; - } + for (sc = cs; *sc != '\0'; ++sc) { + if (strchr(ct, *sc)) + return (char *)sc; } return NULL; } diff --git a/lib/test_firmware.c b/lib/test_firmware.c index e207bc08820d..05ed84c2fc4c 100644 --- a/lib/test_firmware.c +++ b/lib/test_firmware.c @@ -22,6 +22,7 @@ #include <linux/slab.h> #include <linux/uaccess.h> #include <linux/delay.h> +#include <linux/kstrtox.h> #include <linux/kthread.h> #include <linux/vmalloc.h> #include <linux/efi_embedded_fw.h> @@ -50,7 +51,7 @@ struct test_batched_req { }; /** - * test_config - represents configuration for the test for different triggers + * struct test_config - represents configuration for the test for different triggers * * @name: the name of the firmware file to look for * @into_buf: when the into_buf is used if this is true @@ -358,7 +359,7 @@ static int test_dev_config_update_bool(const char *buf, size_t size, int ret; mutex_lock(&test_fw_mutex); - if (strtobool(buf, cfg) < 0) + if (kstrtobool(buf, cfg) < 0) ret = -EINVAL; else ret = size; diff --git a/lib/test_kmod.c b/lib/test_kmod.c index 6423df9fa8dd..43d9dfd57ab7 100644 --- a/lib/test_kmod.c +++ b/lib/test_kmod.c @@ -51,12 +51,11 @@ static int num_test_devs; /** * enum kmod_test_case - linker table test case - * - * If you add a test case, please be sure to review if you need to se - * @need_mod_put for your tests case. - * * @TEST_KMOD_DRIVER: stress tests request_module() * @TEST_KMOD_FS_TYPE: stress tests get_fs_type() + * + * If you add a test case, please be sure to review if you need to set + * @need_mod_put for your tests case. */ enum kmod_test_case { __TEST_KMOD_INVALID = 0, @@ -78,7 +77,7 @@ struct test_config { struct kmod_test_device; /** - * kmod_test_device_info - thread info + * struct kmod_test_device_info - thread info * * @ret_sync: return value if request_module() is used, sync request for * @TEST_KMOD_DRIVER @@ -101,7 +100,7 @@ struct kmod_test_device_info { }; /** - * kmod_test_device - test device to help test kmod + * struct kmod_test_device - test device to help test kmod * * @dev_idx: unique ID for test device * @config: configuration for the test diff --git a/lib/test_kprobes.c b/lib/test_kprobes.c index 1c95e5719802..0648f7154f5c 100644 --- a/lib/test_kprobes.c +++ b/lib/test_kprobes.c @@ -14,6 +14,7 @@ static u32 rand1, preh_val, posth_val; static u32 (*target)(u32 value); +static u32 (*recursed_target)(u32 value); static u32 (*target2)(u32 value); static struct kunit *current_test; @@ -27,18 +28,27 @@ static noinline u32 kprobe_target(u32 value) return (value / div_factor); } +static noinline u32 kprobe_recursed_target(u32 value) +{ + return (value / div_factor); +} + static int kp_pre_handler(struct kprobe *p, struct pt_regs *regs) { KUNIT_EXPECT_FALSE(current_test, preemptible()); - preh_val = (rand1 / div_factor); + + preh_val = recursed_target(rand1); return 0; } static void kp_post_handler(struct kprobe *p, struct pt_regs *regs, unsigned long flags) { + u32 expval = recursed_target(rand1); + KUNIT_EXPECT_FALSE(current_test, preemptible()); - KUNIT_EXPECT_EQ(current_test, preh_val, (rand1 / div_factor)); + KUNIT_EXPECT_EQ(current_test, preh_val, expval); + posth_val = preh_val + div_factor; } @@ -136,6 +146,29 @@ static void test_kprobes(struct kunit *test) unregister_kprobes(kps, 2); } +static struct kprobe kp_missed = { + .symbol_name = "kprobe_recursed_target", + .pre_handler = kp_pre_handler, + .post_handler = kp_post_handler, +}; + +static void test_kprobe_missed(struct kunit *test) +{ + current_test = test; + preh_val = 0; + posth_val = 0; + + KUNIT_EXPECT_EQ(test, 0, register_kprobe(&kp_missed)); + + recursed_target(rand1); + + KUNIT_EXPECT_EQ(test, 2, kp_missed.nmissed); + KUNIT_EXPECT_NE(test, 0, preh_val); + KUNIT_EXPECT_NE(test, 0, posth_val); + + unregister_kprobe(&kp_missed); +} + #ifdef CONFIG_KRETPROBES static u32 krph_val; @@ -336,6 +369,7 @@ static int kprobes_test_init(struct kunit *test) { target = kprobe_target; target2 = kprobe_target2; + recursed_target = kprobe_recursed_target; stacktrace_target = kprobe_stacktrace_target; internal_target = kprobe_stacktrace_internal_target; stacktrace_driver = kprobe_stacktrace_driver; @@ -346,6 +380,7 @@ static int kprobes_test_init(struct kunit *test) static struct kunit_case kprobes_testcases[] = { KUNIT_CASE(test_kprobe), KUNIT_CASE(test_kprobes), + KUNIT_CASE(test_kprobe_missed), #ifdef CONFIG_KRETPROBES KUNIT_CASE(test_kretprobe), KUNIT_CASE(test_kretprobes), diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 497fc93ccf9e..3d19b1f78d71 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -1709,6 +1709,74 @@ static noinline void check_forking(struct maple_tree *mt) mtree_destroy(&newmt); } +static noinline void check_iteration(struct maple_tree *mt) +{ + int i, nr_entries = 125; + void *val; + MA_STATE(mas, mt, 0, 0); + + for (i = 0; i <= nr_entries; i++) + mtree_store_range(mt, i * 10, i * 10 + 9, + xa_mk_value(i), GFP_KERNEL); + + mt_set_non_kernel(99999); + + i = 0; + mas_lock(&mas); + mas_for_each(&mas, val, 925) { + MT_BUG_ON(mt, mas.index != i * 10); + MT_BUG_ON(mt, mas.last != i * 10 + 9); + /* Overwrite end of entry 92 */ + if (i == 92) { + mas.index = 925; + mas.last = 929; + mas_store(&mas, val); + } + i++; + } + /* Ensure mas_find() gets the next value */ + val = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, val != xa_mk_value(i)); + + mas_set(&mas, 0); + i = 0; + mas_for_each(&mas, val, 785) { + MT_BUG_ON(mt, mas.index != i * 10); + MT_BUG_ON(mt, mas.last != i * 10 + 9); + /* Overwrite start of entry 78 */ + if (i == 78) { + mas.index = 780; + mas.last = 785; + mas_store(&mas, val); + } else { + i++; + } + } + val = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, val != xa_mk_value(i)); + + mas_set(&mas, 0); + i = 0; + mas_for_each(&mas, val, 765) { + MT_BUG_ON(mt, mas.index != i * 10); + MT_BUG_ON(mt, mas.last != i * 10 + 9); + /* Overwrite end of entry 76 and advance to the end */ + if (i == 76) { + mas.index = 760; + mas.last = 765; + mas_store(&mas, val); + mas_next(&mas, ULONG_MAX); + } + i++; + } + /* Make sure the next find returns the one after 765, 766-769 */ + val = mas_find(&mas, ULONG_MAX); + MT_BUG_ON(mt, val != xa_mk_value(76)); + mas_unlock(&mas); + mas_destroy(&mas); + mt_set_non_kernel(0); +} + static noinline void check_mas_store_gfp(struct maple_tree *mt) { @@ -2517,6 +2585,91 @@ static noinline void check_bnode_min_spanning(struct maple_tree *mt) mt_set_non_kernel(0); } +static noinline void check_empty_area_window(struct maple_tree *mt) +{ + unsigned long i, nr_entries = 20; + MA_STATE(mas, mt, 0, 0); + + for (i = 1; i <= nr_entries; i++) + mtree_store_range(mt, i*10, i*10 + 9, + xa_mk_value(i), GFP_KERNEL); + + /* Create another hole besides the one at 0 */ + mtree_store_range(mt, 160, 169, NULL, GFP_KERNEL); + + /* Check lower bounds that don't fit */ + rcu_read_lock(); + MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 10) != -EBUSY); + + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area_rev(&mas, 6, 90, 5) != -EBUSY); + + /* Check lower bound that does fit */ + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 90, 5) != 0); + MT_BUG_ON(mt, mas.index != 5); + MT_BUG_ON(mt, mas.last != 9); + rcu_read_unlock(); + + /* Check one gap that doesn't fit and one that does */ + rcu_read_lock(); + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area_rev(&mas, 5, 217, 9) != 0); + MT_BUG_ON(mt, mas.index != 161); + MT_BUG_ON(mt, mas.last != 169); + + /* Check one gap that does fit above the min */ + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 3) != 0); + MT_BUG_ON(mt, mas.index != 216); + MT_BUG_ON(mt, mas.last != 218); + + /* Check size that doesn't fit any gap */ + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 218, 16) != -EBUSY); + + /* + * Check size that doesn't fit the lower end of the window but + * does fit the gap + */ + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area_rev(&mas, 167, 200, 4) != -EBUSY); + + /* + * Check size that doesn't fit the upper end of the window but + * does fit the gap + */ + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area_rev(&mas, 100, 162, 4) != -EBUSY); + + /* Check mas_empty_area forward */ + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 9) != 0); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != 8); + + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 4) != 0); + MT_BUG_ON(mt, mas.index != 0); + MT_BUG_ON(mt, mas.last != 3); + + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area(&mas, 0, 100, 11) != -EBUSY); + + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area(&mas, 5, 100, 6) != -EBUSY); + + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area(&mas, 0, 8, 10) != -EBUSY); + + mas_reset(&mas); + mas_empty_area(&mas, 100, 165, 3); + + mas_reset(&mas); + MT_BUG_ON(mt, mas_empty_area(&mas, 100, 163, 6) != -EBUSY); + rcu_read_unlock(); +} + static DEFINE_MTREE(tree); static int maple_tree_seed(void) { @@ -2575,6 +2728,10 @@ static int maple_tree_seed(void) #endif mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_iteration(&tree); + mtree_destroy(&tree); + + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_forking(&tree); mtree_destroy(&tree); @@ -2765,6 +2922,10 @@ static int maple_tree_seed(void) check_bnode_min_spanning(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_empty_area_window(&tree); + mtree_destroy(&tree); + #if defined(BENCH) skip: #endif diff --git a/lib/test_printf.c b/lib/test_printf.c index d34dc636b81c..46b4e6c414a3 100644 --- a/lib/test_printf.c +++ b/lib/test_printf.c @@ -674,17 +674,17 @@ flags(void) gfp = GFP_ATOMIC|__GFP_DMA; test("GFP_ATOMIC|GFP_DMA", "%pGg", &gfp); - gfp = __GFP_ATOMIC; - test("__GFP_ATOMIC", "%pGg", &gfp); + gfp = __GFP_HIGH; + test("__GFP_HIGH", "%pGg", &gfp); /* Any flags not translated by the table should remain numeric */ gfp = ~__GFP_BITS_MASK; snprintf(cmp_buffer, BUF_SIZE, "%#lx", (unsigned long) gfp); test(cmp_buffer, "%pGg", &gfp); - snprintf(cmp_buffer, BUF_SIZE, "__GFP_ATOMIC|%#lx", + snprintf(cmp_buffer, BUF_SIZE, "__GFP_HIGH|%#lx", (unsigned long) gfp); - gfp |= __GFP_ATOMIC; + gfp |= __GFP_HIGH; test(cmp_buffer, "%pGg", &gfp); kfree(cmp_buffer); diff --git a/lib/test_vmalloc.c b/lib/test_vmalloc.c index f90d2c27675b..de4ee0d50906 100644 --- a/lib/test_vmalloc.c +++ b/lib/test_vmalloc.c @@ -38,6 +38,9 @@ __param(int, test_loop_count, 1000000, __param(int, nr_pages, 0, "Set number of pages for fix_size_alloc_test(default: 1)"); +__param(bool, use_huge, false, + "Use vmalloc_huge in fix_size_alloc_test"); + __param(int, run_test_mask, INT_MAX, "Set tests specified in the mask.\n\n" "\t\tid: 1, name: fix_size_alloc_test\n" @@ -264,7 +267,10 @@ static int fix_size_alloc_test(void) int i; for (i = 0; i < test_loop_count; i++) { - ptr = vmalloc((nr_pages > 0 ? nr_pages:1) * PAGE_SIZE); + if (use_huge) + ptr = vmalloc_huge((nr_pages > 0 ? nr_pages:1) * PAGE_SIZE, GFP_KERNEL); + else + ptr = vmalloc((nr_pages > 0 ? nr_pages:1) * PAGE_SIZE); if (!ptr) return -1; diff --git a/lib/ubsan.c b/lib/ubsan.c index 60c7099857a0..e2cc4a799312 100644 --- a/lib/ubsan.c +++ b/lib/ubsan.c @@ -14,10 +14,76 @@ #include <linux/types.h> #include <linux/sched.h> #include <linux/uaccess.h> +#include <linux/ubsan.h> #include <kunit/test-bug.h> #include "ubsan.h" +#ifdef CONFIG_UBSAN_TRAP +/* + * Only include matches for UBSAN checks that are actually compiled in. + * The mappings of struct SanitizerKind (the -fsanitize=xxx args) to + * enum SanitizerHandler (the traps) in Clang is in clang/lib/CodeGen/. + */ +const char *report_ubsan_failure(struct pt_regs *regs, u32 check_type) +{ + switch (check_type) { +#ifdef CONFIG_UBSAN_BOUNDS + /* + * SanitizerKind::ArrayBounds and SanitizerKind::LocalBounds + * emit SanitizerHandler::OutOfBounds. + */ + case ubsan_out_of_bounds: + return "UBSAN: array index out of bounds"; +#endif +#ifdef CONFIG_UBSAN_SHIFT + /* + * SanitizerKind::ShiftBase and SanitizerKind::ShiftExponent + * emit SanitizerHandler::ShiftOutOfBounds. + */ + case ubsan_shift_out_of_bounds: + return "UBSAN: shift out of bounds"; +#endif +#ifdef CONFIG_UBSAN_DIV_ZERO + /* + * SanitizerKind::IntegerDivideByZero emits + * SanitizerHandler::DivremOverflow. + */ + case ubsan_divrem_overflow: + return "UBSAN: divide/remainder overflow"; +#endif +#ifdef CONFIG_UBSAN_UNREACHABLE + /* + * SanitizerKind::Unreachable emits + * SanitizerHandler::BuiltinUnreachable. + */ + case ubsan_builtin_unreachable: + return "UBSAN: unreachable code"; +#endif +#if defined(CONFIG_UBSAN_BOOL) || defined(CONFIG_UBSAN_ENUM) + /* + * SanitizerKind::Bool and SanitizerKind::Enum emit + * SanitizerHandler::LoadInvalidValue. + */ + case ubsan_load_invalid_value: + return "UBSAN: loading invalid value"; +#endif +#ifdef CONFIG_UBSAN_ALIGNMENT + /* + * SanitizerKind::Alignment emits SanitizerHandler::TypeMismatch + * or SanitizerHandler::AlignmentAssumption. + */ + case ubsan_alignment_assumption: + return "UBSAN: alignment assumption"; + case ubsan_type_mismatch: + return "UBSAN: type mismatch"; +#endif + default: + return "UBSAN: unrecognized failure code"; + } +} + +#else static const char * const type_check_kinds[] = { "load of", "store to", @@ -339,9 +405,10 @@ void __ubsan_handle_load_invalid_value(void *_data, void *val) { struct invalid_value_data *data = _data; char val_str[VALUE_LENGTH]; + unsigned long ua_flags = user_access_save(); if (suppress_report(&data->location)) - return; + goto out; ubsan_prologue(&data->location, "invalid-load"); @@ -351,6 +418,8 @@ void __ubsan_handle_load_invalid_value(void *_data, void *val) val_str, data->type->type_name); ubsan_epilogue(); +out: + user_access_restore(ua_flags); } EXPORT_SYMBOL(__ubsan_handle_load_invalid_value); @@ -384,3 +453,5 @@ void __ubsan_handle_alignment_assumption(void *_data, unsigned long ptr, ubsan_epilogue(); } EXPORT_SYMBOL(__ubsan_handle_alignment_assumption); + +#endif /* !CONFIG_UBSAN_TRAP */ diff --git a/lib/ubsan.h b/lib/ubsan.h index 9a0b71c5ff9f..cc5cb94895a6 100644 --- a/lib/ubsan.h +++ b/lib/ubsan.h @@ -2,6 +2,38 @@ #ifndef _LIB_UBSAN_H #define _LIB_UBSAN_H +/* + * ABI defined by Clang's UBSAN enum SanitizerHandler: + * https://github.com/llvm/llvm-project/blob/release/16.x/clang/lib/CodeGen/CodeGenFunction.h#L113 + */ +enum ubsan_checks { + ubsan_add_overflow, + ubsan_builtin_unreachable, + ubsan_cfi_check_fail, + ubsan_divrem_overflow, + ubsan_dynamic_type_cache_miss, + ubsan_float_cast_overflow, + ubsan_function_type_mismatch, + ubsan_implicit_conversion, + ubsan_invalid_builtin, + ubsan_invalid_objc_cast, + ubsan_load_invalid_value, + ubsan_missing_return, + ubsan_mul_overflow, + ubsan_negate_overflow, + ubsan_nullability_arg, + ubsan_nullability_return, + ubsan_nonnull_arg, + ubsan_nonnull_return, + ubsan_out_of_bounds, + ubsan_pointer_overflow, + ubsan_shift_out_of_bounds, + ubsan_sub_overflow, + ubsan_type_mismatch, + ubsan_alignment_assumption, + ubsan_vla_bound_not_positive, +}; + enum { type_kind_int = 0, type_kind_float = 1, diff --git a/lib/usercopy.c b/lib/usercopy.c index 1505a52f23a0..d29fe29c6849 100644 --- a/lib/usercopy.c +++ b/lib/usercopy.c @@ -3,6 +3,7 @@ #include <linux/fault-inject-usercopy.h> #include <linux/instrumented.h> #include <linux/uaccess.h> +#include <linux/nospec.h> /* out-of-line parts */ @@ -12,6 +13,12 @@ unsigned long _copy_from_user(void *to, const void __user *from, unsigned long n unsigned long res = n; might_fault(); if (!should_fail_usercopy() && likely(access_ok(from, n))) { + /* + * Ensure that bad access_ok() speculation will not + * lead to nasty side effects *after* the copy is + * finished: + */ + barrier_nospec(); instrument_copy_from_user_before(to, from, n); res = raw_copy_from_user(to, from, n); instrument_copy_from_user_after(to, from, n, res); diff --git a/lib/win_minmax.c b/lib/win_minmax.c index 6bdc1cd15f76..ec10506834b6 100644 --- a/lib/win_minmax.c +++ b/lib/win_minmax.c @@ -1,5 +1,5 @@ // SPDX-License-Identifier: GPL-2.0 -/** +/* * lib/minmax.c: windowed min/max tracker * * Kathleen Nichols' algorithm for tracking the minimum (or maximum) diff --git a/lib/zlib_deflate/deflate.c b/lib/zlib_deflate/deflate.c index 8a878d0d892c..3a1d8d34182e 100644 --- a/lib/zlib_deflate/deflate.c +++ b/lib/zlib_deflate/deflate.c @@ -54,7 +54,7 @@ /* architecture-specific bits */ #ifdef CONFIG_ZLIB_DFLTCC -# include "../zlib_dfltcc/dfltcc.h" +# include "../zlib_dfltcc/dfltcc_deflate.h" #else #define DEFLATE_RESET_HOOK(strm) do {} while (0) #define DEFLATE_HOOK(strm, flush, bstate) 0 @@ -106,7 +106,7 @@ typedef struct deflate_workspace { deflate_state deflate_memory; #ifdef CONFIG_ZLIB_DFLTCC /* State memory for s390 hardware deflate */ - struct dfltcc_state dfltcc_memory; + struct dfltcc_deflate_state dfltcc_memory; #endif Byte *window_memory; Pos *prev_memory; @@ -451,17 +451,24 @@ int zlib_deflate( Assert(strm->avail_out > 0, "bug2"); if (flush != Z_FINISH) return Z_OK; - if (s->noheader) return Z_STREAM_END; - /* Write the zlib trailer (adler32) */ - putShortMSB(s, (uInt)(strm->adler >> 16)); - putShortMSB(s, (uInt)(strm->adler & 0xffff)); + if (!s->noheader) { + /* Write zlib trailer (adler32) */ + putShortMSB(s, (uInt)(strm->adler >> 16)); + putShortMSB(s, (uInt)(strm->adler & 0xffff)); + } flush_pending(strm); /* If avail_out is zero, the application will call deflate again * to flush the rest. */ - s->noheader = -1; /* write the trailer only once! */ - return s->pending != 0 ? Z_OK : Z_STREAM_END; + if (!s->noheader) { + s->noheader = -1; /* write the trailer only once! */ + } + if (s->pending == 0) { + Assert(s->bi_valid == 0, "bi_buf not flushed"); + return Z_STREAM_END; + } + return Z_OK; } /* ========================================================================= */ diff --git a/lib/zlib_dfltcc/dfltcc.c b/lib/zlib_dfltcc/dfltcc.c index 782f76e9d4da..ac6ac9739f5b 100644 --- a/lib/zlib_dfltcc/dfltcc.c +++ b/lib/zlib_dfltcc/dfltcc.c @@ -23,37 +23,18 @@ char *oesc_msg( } } -void dfltcc_reset( - z_streamp strm, - uInt size -) -{ - struct dfltcc_state *dfltcc_state = - (struct dfltcc_state *)((char *)strm->state + size); - struct dfltcc_qaf_param *param = - (struct dfltcc_qaf_param *)&dfltcc_state->param; - +void dfltcc_reset_state(struct dfltcc_state *dfltcc_state) { /* Initialize available functions */ if (is_dfltcc_enabled()) { - dfltcc(DFLTCC_QAF, param, NULL, NULL, NULL, NULL, NULL); - memmove(&dfltcc_state->af, param, sizeof(dfltcc_state->af)); + dfltcc(DFLTCC_QAF, &dfltcc_state->param, NULL, NULL, NULL, NULL, NULL); + memmove(&dfltcc_state->af, &dfltcc_state->param, sizeof(dfltcc_state->af)); } else memset(&dfltcc_state->af, 0, sizeof(dfltcc_state->af)); /* Initialize parameter block */ memset(&dfltcc_state->param, 0, sizeof(dfltcc_state->param)); dfltcc_state->param.nt = 1; - - /* Initialize tuning parameters */ - if (zlib_dfltcc_support == ZLIB_DFLTCC_FULL_DEBUG) - dfltcc_state->level_mask = DFLTCC_LEVEL_MASK_DEBUG; - else - dfltcc_state->level_mask = DFLTCC_LEVEL_MASK; - dfltcc_state->block_size = DFLTCC_BLOCK_SIZE; - dfltcc_state->block_threshold = DFLTCC_FIRST_FHT_BLOCK_SIZE; - dfltcc_state->dht_threshold = DFLTCC_DHT_MIN_SAMPLE_SIZE; dfltcc_state->param.ribm = DFLTCC_RIBM; } -EXPORT_SYMBOL(dfltcc_reset); MODULE_LICENSE("GPL"); diff --git a/lib/zlib_dfltcc/dfltcc.h b/lib/zlib_dfltcc/dfltcc.h index 2a2fac1d050a..b96232bdd44d 100644 --- a/lib/zlib_dfltcc/dfltcc.h +++ b/lib/zlib_dfltcc/dfltcc.h @@ -93,63 +93,32 @@ static_assert(sizeof(struct dfltcc_param_v0) == 1536); struct dfltcc_state { struct dfltcc_param_v0 param; /* Parameter block */ struct dfltcc_qaf_param af; /* Available functions */ + char msg[64]; /* Buffer for strm->msg */ +}; + +/* + * Extension of inflate_state and deflate_state for DFLTCC. + */ +struct dfltcc_deflate_state { + struct dfltcc_state common; /* Parameter block */ uLong level_mask; /* Levels on which to use DFLTCC */ uLong block_size; /* New block each X bytes */ uLong block_threshold; /* New block after total_in > X */ uLong dht_threshold; /* New block only if avail_in >= X */ - char msg[64]; /* Buffer for strm->msg */ }; +#define ALIGN_UP(p, size) (__typeof__(p))(((uintptr_t)(p) + ((size) - 1)) & ~((size) - 1)) /* Resides right after inflate_state or deflate_state */ -#define GET_DFLTCC_STATE(state) ((struct dfltcc_state *)((state) + 1)) - -/* External functions */ -int dfltcc_can_deflate(z_streamp strm); -int dfltcc_deflate(z_streamp strm, - int flush, - block_state *result); -void dfltcc_reset(z_streamp strm, uInt size); -int dfltcc_can_inflate(z_streamp strm); -typedef enum { - DFLTCC_INFLATE_CONTINUE, - DFLTCC_INFLATE_BREAK, - DFLTCC_INFLATE_SOFTWARE, -} dfltcc_inflate_action; -dfltcc_inflate_action dfltcc_inflate(z_streamp strm, - int flush, int *ret); +#define GET_DFLTCC_STATE(state) ((struct dfltcc_state *)((char *)(state) + ALIGN_UP(sizeof(*state), 8))) + +void dfltcc_reset_state(struct dfltcc_state *dfltcc_state); + static inline int is_dfltcc_enabled(void) { return (zlib_dfltcc_support != ZLIB_DFLTCC_DISABLED && test_facility(DFLTCC_FACILITY)); } -#define DEFLATE_RESET_HOOK(strm) \ - dfltcc_reset((strm), sizeof(deflate_state)) - -#define DEFLATE_HOOK dfltcc_deflate - -#define DEFLATE_NEED_CHECKSUM(strm) (!dfltcc_can_deflate((strm))) - #define DEFLATE_DFLTCC_ENABLED() is_dfltcc_enabled() -#define INFLATE_RESET_HOOK(strm) \ - dfltcc_reset((strm), sizeof(struct inflate_state)) - -#define INFLATE_TYPEDO_HOOK(strm, flush) \ - if (dfltcc_can_inflate((strm))) { \ - dfltcc_inflate_action action; \ -\ - RESTORE(); \ - action = dfltcc_inflate((strm), (flush), &ret); \ - LOAD(); \ - if (action == DFLTCC_INFLATE_CONTINUE) \ - break; \ - else if (action == DFLTCC_INFLATE_BREAK) \ - goto inf_leave; \ - } - -#define INFLATE_NEED_CHECKSUM(strm) (!dfltcc_can_inflate((strm))) - -#define INFLATE_NEED_UPDATEWINDOW(strm) (!dfltcc_can_inflate((strm))) - #endif /* DFLTCC_H */ diff --git a/lib/zlib_dfltcc/dfltcc_deflate.c b/lib/zlib_dfltcc/dfltcc_deflate.c index 6c946e8532ee..b732b6d9e35d 100644 --- a/lib/zlib_dfltcc/dfltcc_deflate.c +++ b/lib/zlib_dfltcc/dfltcc_deflate.c @@ -2,11 +2,13 @@ #include "../zlib_deflate/defutil.h" #include "dfltcc_util.h" -#include "dfltcc.h" +#include "dfltcc_deflate.h" #include <asm/setup.h> #include <linux/export.h> #include <linux/zutil.h> +#define GET_DFLTCC_DEFLATE_STATE(state) ((struct dfltcc_deflate_state *)GET_DFLTCC_STATE(state)) + /* * Compress. */ @@ -15,7 +17,7 @@ int dfltcc_can_deflate( ) { deflate_state *state = (deflate_state *)strm->state; - struct dfltcc_state *dfltcc_state = GET_DFLTCC_STATE(state); + struct dfltcc_deflate_state *dfltcc_state = GET_DFLTCC_DEFLATE_STATE(state); /* Check for kernel dfltcc command line parameter */ if (zlib_dfltcc_support == ZLIB_DFLTCC_DISABLED || @@ -28,22 +30,39 @@ int dfltcc_can_deflate( return 0; /* Unsupported hardware */ - if (!is_bit_set(dfltcc_state->af.fns, DFLTCC_GDHT) || - !is_bit_set(dfltcc_state->af.fns, DFLTCC_CMPR) || - !is_bit_set(dfltcc_state->af.fmts, DFLTCC_FMT0)) + if (!is_bit_set(dfltcc_state->common.af.fns, DFLTCC_GDHT) || + !is_bit_set(dfltcc_state->common.af.fns, DFLTCC_CMPR) || + !is_bit_set(dfltcc_state->common.af.fmts, DFLTCC_FMT0)) return 0; return 1; } EXPORT_SYMBOL(dfltcc_can_deflate); +void dfltcc_reset_deflate_state(z_streamp strm) { + deflate_state *state = (deflate_state *)strm->state; + struct dfltcc_deflate_state *dfltcc_state = GET_DFLTCC_DEFLATE_STATE(state); + + dfltcc_reset_state(&dfltcc_state->common); + + /* Initialize tuning parameters */ + if (zlib_dfltcc_support == ZLIB_DFLTCC_FULL_DEBUG) + dfltcc_state->level_mask = DFLTCC_LEVEL_MASK_DEBUG; + else + dfltcc_state->level_mask = DFLTCC_LEVEL_MASK; + dfltcc_state->block_size = DFLTCC_BLOCK_SIZE; + dfltcc_state->block_threshold = DFLTCC_FIRST_FHT_BLOCK_SIZE; + dfltcc_state->dht_threshold = DFLTCC_DHT_MIN_SAMPLE_SIZE; +} +EXPORT_SYMBOL(dfltcc_reset_deflate_state); + static void dfltcc_gdht( z_streamp strm ) { deflate_state *state = (deflate_state *)strm->state; struct dfltcc_param_v0 *param = &GET_DFLTCC_STATE(state)->param; - size_t avail_in = avail_in = strm->avail_in; + size_t avail_in = strm->avail_in; dfltcc(DFLTCC_GDHT, param, NULL, NULL, @@ -104,39 +123,46 @@ int dfltcc_deflate( ) { deflate_state *state = (deflate_state *)strm->state; - struct dfltcc_state *dfltcc_state = GET_DFLTCC_STATE(state); - struct dfltcc_param_v0 *param = &dfltcc_state->param; + struct dfltcc_deflate_state *dfltcc_state = GET_DFLTCC_DEFLATE_STATE(state); + struct dfltcc_param_v0 *param = &dfltcc_state->common.param; uInt masked_avail_in; dfltcc_cc cc; int need_empty_block; int soft_bcc; int no_flush; - if (!dfltcc_can_deflate(strm)) + if (!dfltcc_can_deflate(strm)) { + /* Clear history. */ + if (flush == Z_FULL_FLUSH) + param->hl = 0; return 0; + } again: masked_avail_in = 0; soft_bcc = 0; no_flush = flush == Z_NO_FLUSH; - /* Trailing empty block. Switch to software, except when Continuation Flag - * is set, which means that DFLTCC has buffered some output in the - * parameter block and needs to be called again in order to flush it. + /* No input data. Return, except when Continuation Flag is set, which means + * that DFLTCC has buffered some output in the parameter block and needs to + * be called again in order to flush it. */ - if (flush == Z_FINISH && strm->avail_in == 0 && !param->cf) { - if (param->bcf) { - /* A block is still open, and the hardware does not support closing - * blocks without adding data. Thus, close it manually. - */ + if (strm->avail_in == 0 && !param->cf) { + /* A block is still open, and the hardware does not support closing + * blocks without adding data. Thus, close it manually. + */ + if (!no_flush && param->bcf) { send_eobs(strm, param); param->bcf = 0; } - return 0; - } - - if (strm->avail_in == 0 && !param->cf) { - *result = need_more; + /* Let one of deflate_* functions write a trailing empty block. */ + if (flush == Z_FINISH) + return 0; + /* Clear history. */ + if (flush == Z_FULL_FLUSH) + param->hl = 0; + /* Trigger block post-processing if necessary. */ + *result = no_flush ? need_more : block_done; return 1; } @@ -163,13 +189,18 @@ again: param->bcf = 0; dfltcc_state->block_threshold = strm->total_in + dfltcc_state->block_size; - if (strm->avail_out == 0) { - *result = need_more; - return 1; - } } } + /* No space for compressed data. If we proceed, dfltcc_cmpr() will return + * DFLTCC_CC_OP1_TOO_SHORT without buffering header bits, but we will still + * set BCF=1, which is wrong. Avoid complications and return early. + */ + if (strm->avail_out == 0) { + *result = need_more; + return 1; + } + /* The caller gave us too much data. Pass only one block worth of * uncompressed data to DFLTCC and mask the rest, so that on the next * iteration we start a new block. @@ -189,7 +220,7 @@ again: param->cvt = CVT_ADLER32; if (!no_flush) /* We need to close a block. Always do this in software - when there is - * no input data, the hardware will not nohor BCC. */ + * no input data, the hardware will not hohor BCC. */ soft_bcc = 1; if (flush == Z_FINISH && !param->bcf) /* We are about to open a BFINAL block, set Block Header Final bit @@ -204,8 +235,8 @@ again: param->sbb = (unsigned int)state->bi_valid; if (param->sbb > 0) *strm->next_out = (Byte)state->bi_buf; - if (param->hl) - param->nt = 0; /* Honor history */ + /* Honor history and check value */ + param->nt = 0; param->cv = strm->adler; /* When opening a block, choose a Huffman-Table Type */ @@ -232,7 +263,7 @@ again: } while (cc == DFLTCC_CC_AGAIN); /* Translate parameter block to stream */ - strm->msg = oesc_msg(dfltcc_state->msg, param->oesc); + strm->msg = oesc_msg(dfltcc_state->common.msg, param->oesc); state->bi_valid = param->sbb; if (state->bi_valid == 0) state->bi_buf = 0; /* Avoid accessing next_out */ diff --git a/lib/zlib_dfltcc/dfltcc_deflate.h b/lib/zlib_dfltcc/dfltcc_deflate.h new file mode 100644 index 000000000000..be44b43833b1 --- /dev/null +++ b/lib/zlib_dfltcc/dfltcc_deflate.h @@ -0,0 +1,21 @@ +// SPDX-License-Identifier: Zlib +#ifndef DFLTCC_DEFLATE_H +#define DFLTCC_DEFLATE_H + +#include "dfltcc.h" + +/* External functions */ +int dfltcc_can_deflate(z_streamp strm); +int dfltcc_deflate(z_streamp strm, + int flush, + block_state *result); +void dfltcc_reset_deflate_state(z_streamp strm); + +#define DEFLATE_RESET_HOOK(strm) \ + dfltcc_reset_deflate_state((strm)) + +#define DEFLATE_HOOK dfltcc_deflate + +#define DEFLATE_NEED_CHECKSUM(strm) (!dfltcc_can_deflate((strm))) + +#endif /* DFLTCC_DEFLATE_H */ diff --git a/lib/zlib_dfltcc/dfltcc_inflate.c b/lib/zlib_dfltcc/dfltcc_inflate.c index fb60b5a6a1cb..437cd34c8490 100644 --- a/lib/zlib_dfltcc/dfltcc_inflate.c +++ b/lib/zlib_dfltcc/dfltcc_inflate.c @@ -2,7 +2,7 @@ #include "../zlib_inflate/inflate.h" #include "dfltcc_util.h" -#include "dfltcc.h" +#include "dfltcc_inflate.h" #include <asm/setup.h> #include <linux/export.h> #include <linux/zutil.h> @@ -22,16 +22,20 @@ int dfltcc_can_inflate( zlib_dfltcc_support == ZLIB_DFLTCC_DEFLATE_ONLY) return 0; - /* Unsupported compression settings */ - if (state->wbits != HB_BITS) - return 0; - /* Unsupported hardware */ return is_bit_set(dfltcc_state->af.fns, DFLTCC_XPND) && is_bit_set(dfltcc_state->af.fmts, DFLTCC_FMT0); } EXPORT_SYMBOL(dfltcc_can_inflate); +void dfltcc_reset_inflate_state(z_streamp strm) { + struct inflate_state *state = (struct inflate_state *)strm->state; + struct dfltcc_state *dfltcc_state = GET_DFLTCC_STATE(state); + + dfltcc_reset_state(dfltcc_state); +} +EXPORT_SYMBOL(dfltcc_reset_inflate_state); + static int dfltcc_was_inflate_used( z_streamp strm ) @@ -91,8 +95,10 @@ dfltcc_inflate_action dfltcc_inflate( struct dfltcc_param_v0 *param = &dfltcc_state->param; dfltcc_cc cc; - if (flush == Z_BLOCK) { - /* DFLTCC does not support stopping on block boundaries */ + if (flush == Z_BLOCK || flush == Z_PACKET_FLUSH) { + /* DFLTCC does not support stopping on block boundaries (Z_BLOCK flush option) + * as well as the use of Z_PACKET_FLUSH option (used exclusively by PPP driver) + */ if (dfltcc_inflate_disable(strm)) { *ret = Z_STREAM_ERROR; return DFLTCC_INFLATE_BREAK; @@ -121,8 +127,6 @@ dfltcc_inflate_action dfltcc_inflate( /* Translate stream to parameter block */ param->cvt = CVT_ADLER32; param->sbb = state->bits; - param->hl = state->whave; /* Software and hardware history formats match */ - param->ho = (state->write - state->whave) & ((1 << HB_BITS) - 1); if (param->hl) param->nt = 0; /* Honor history for the first block */ param->cv = state->check; @@ -136,8 +140,6 @@ dfltcc_inflate_action dfltcc_inflate( strm->msg = oesc_msg(dfltcc_state->msg, param->oesc); state->last = cc == DFLTCC_CC_OK; state->bits = param->sbb; - state->whave = param->hl; - state->write = (param->ho + param->hl) & ((1 << HB_BITS) - 1); state->check = param->cv; if (cc == DFLTCC_CC_OP2_CORRUPT && param->oesc != 0) { /* Report an error if stream is corrupted */ diff --git a/lib/zlib_dfltcc/dfltcc_inflate.h b/lib/zlib_dfltcc/dfltcc_inflate.h new file mode 100644 index 000000000000..98d4bc42e526 --- /dev/null +++ b/lib/zlib_dfltcc/dfltcc_inflate.h @@ -0,0 +1,37 @@ +// SPDX-License-Identifier: Zlib +#ifndef DFLTCC_INFLATE_H +#define DFLTCC_INFLATE_H + +#include "dfltcc.h" + +/* External functions */ +void dfltcc_reset_inflate_state(z_streamp strm); +int dfltcc_can_inflate(z_streamp strm); +typedef enum { + DFLTCC_INFLATE_CONTINUE, + DFLTCC_INFLATE_BREAK, + DFLTCC_INFLATE_SOFTWARE, +} dfltcc_inflate_action; +dfltcc_inflate_action dfltcc_inflate(z_streamp strm, + int flush, int *ret); +#define INFLATE_RESET_HOOK(strm) \ + dfltcc_reset_inflate_state((strm)) + +#define INFLATE_TYPEDO_HOOK(strm, flush) \ + if (dfltcc_can_inflate((strm))) { \ + dfltcc_inflate_action action; \ +\ + RESTORE(); \ + action = dfltcc_inflate((strm), (flush), &ret); \ + LOAD(); \ + if (action == DFLTCC_INFLATE_CONTINUE) \ + break; \ + else if (action == DFLTCC_INFLATE_BREAK) \ + goto inf_leave; \ + } + +#define INFLATE_NEED_CHECKSUM(strm) (!dfltcc_can_inflate((strm))) + +#define INFLATE_NEED_UPDATEWINDOW(strm) (!dfltcc_can_inflate((strm))) + +#endif /* DFLTCC_DEFLATE_H */ diff --git a/lib/zlib_inflate/inflate.c b/lib/zlib_inflate/inflate.c index ee39b5eb71f7..d1efad69f02b 100644 --- a/lib/zlib_inflate/inflate.c +++ b/lib/zlib_inflate/inflate.c @@ -17,7 +17,7 @@ /* architecture-specific bits */ #ifdef CONFIG_ZLIB_DFLTCC -# include "../zlib_dfltcc/dfltcc.h" +# include "../zlib_dfltcc/dfltcc_inflate.h" #else #define INFLATE_RESET_HOOK(strm) do {} while (0) #define INFLATE_TYPEDO_HOOK(strm, flush) do {} while (0) |