diff options
Diffstat (limited to 'lib')
44 files changed, 2570 insertions, 969 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index ce2abffb9ed8..5c2da561c516 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -92,6 +92,7 @@ config ARCH_USE_SYM_ANNOTATIONS config INDIRECT_PIO bool "Access I/O in non-MMIO mode" depends on ARM64 + depends on HAS_IOPORT help On some platforms where no separate I/O space exists, there are I/O hosts which can not be accessed in MMIO mode. Using the logical PIO @@ -509,6 +510,9 @@ config HAS_IOMEM depends on !NO_IOMEM default y +config HAS_IOPORT + bool + config HAS_IOPORT_MAP bool depends on HAS_IOMEM && !NO_IOPORT_MAP diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 1dd4bd7dc271..39d1d93164bd 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -752,77 +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 - select STACKDEPOT_ALWAYS_INIT if !DEBUG_KMEMLEAK_DEFAULT_OFF - 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 @@ -1214,7 +1143,7 @@ menu "Scheduler Debugging" config SCHED_DEBUG bool "Collect scheduler debugging info" - depends on DEBUG_KERNEL && PROC_FS + depends on DEBUG_KERNEL && DEBUG_FS default y help If you say Y here, the /sys/kernel/debug/sched file will be provided @@ -1256,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 @@ -1460,7 +1392,7 @@ config LOCKDEP_STACK_TRACE_HASH_BITS range 10 30 default 14 help - Try increasing this value if you need large MAX_STACK_TRACE_ENTRIES. + Try increasing this value if you need large STACK_TRACE_HASH_SIZE. config LOCKDEP_CIRCULAR_QUEUE_BITS int "Bitsize for elements in circular_queue struct" @@ -2100,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 diff --git a/lib/Kconfig.kasan b/lib/Kconfig.kasan index be6ee6020290..fdca89c05745 100644 --- a/lib/Kconfig.kasan +++ b/lib/Kconfig.kasan @@ -49,6 +49,15 @@ menuconfig KASAN if KASAN +config CC_HAS_KASAN_MEMINTRINSIC_PREFIX + def_bool (CC_IS_CLANG && $(cc-option,-fsanitize=kernel-address -mllvm -asan-kernel-mem-intrinsic-prefix=1)) || \ + (CC_IS_GCC && $(cc-option,-fsanitize=kernel-address --param asan-kernel-mem-intrinsic-prefix=1)) + # Don't define it if we don't need it: compilation of the test uses + # this variable to decide how the compiler should treat builtins. + depends on !KASAN_HW_TAGS + help + The compiler is able to prefix memintrinsics with __asan or __hwasan. + choice prompt "KASAN mode" default KASAN_GENERIC diff --git a/lib/Kconfig.kcsan b/lib/Kconfig.kcsan index 4dedd61e5192..609ddfc73de5 100644 --- a/lib/Kconfig.kcsan +++ b/lib/Kconfig.kcsan @@ -14,6 +14,7 @@ menuconfig KCSAN bool "KCSAN: dynamic data race detector" depends on HAVE_ARCH_KCSAN && HAVE_KCSAN_COMPILER depends on DEBUG_KERNEL && !KASAN + select CONSTRUCTORS select STACKTRACE help The Kernel Concurrency Sanitizer (KCSAN) is a dynamic diff --git a/lib/Makefile b/lib/Makefile index a269af847e2e..baf2821f7a00 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 @@ -125,14 +127,10 @@ 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 +# Some KUnit files (hooks.o) need to be built-in even when KUnit is a module, +# so we can't just use obj-$(CONFIG_KUNIT). +ifdef CONFIG_KUNIT +obj-y += kunit/ endif ifeq ($(CONFIG_DEBUG_KOBJECT),y) diff --git a/lib/cpumask_kunit.c b/lib/cpumask_kunit.c index d1fc6ece21f3..a105e6369efc 100644 --- a/lib/cpumask_kunit.c +++ b/lib/cpumask_kunit.c @@ -23,16 +23,6 @@ KUNIT_EXPECT_EQ_MSG((test), mask_weight, iter, MASK_MSG(mask)); \ } while (0) -#define EXPECT_FOR_EACH_CPU_NOT_EQ(test, mask) \ - do { \ - const cpumask_t *m = (mask); \ - int mask_weight = cpumask_weight(m); \ - int cpu, iter = 0; \ - for_each_cpu_not(cpu, m) \ - iter++; \ - KUNIT_EXPECT_EQ_MSG((test), nr_cpu_ids - mask_weight, iter, MASK_MSG(mask)); \ - } while (0) - #define EXPECT_FOR_EACH_CPU_OP_EQ(test, op, mask1, mask2) \ do { \ const cpumask_t *m1 = (mask1); \ @@ -77,7 +67,7 @@ static void test_cpumask_weight(struct kunit *test) KUNIT_EXPECT_EQ_MSG(test, 0, cpumask_weight(&mask_empty), MASK_MSG(&mask_empty)); KUNIT_EXPECT_EQ_MSG(test, nr_cpu_ids, cpumask_weight(cpu_possible_mask), MASK_MSG(cpu_possible_mask)); - KUNIT_EXPECT_EQ_MSG(test, nr_cpumask_bits, cpumask_weight(&mask_all), MASK_MSG(&mask_all)); + KUNIT_EXPECT_EQ_MSG(test, nr_cpu_ids, cpumask_weight(&mask_all), MASK_MSG(&mask_all)); } static void test_cpumask_first(struct kunit *test) @@ -113,14 +103,12 @@ static void test_cpumask_next(struct kunit *test) static void test_cpumask_iterators(struct kunit *test) { EXPECT_FOR_EACH_CPU_EQ(test, &mask_empty); - EXPECT_FOR_EACH_CPU_NOT_EQ(test, &mask_empty); EXPECT_FOR_EACH_CPU_WRAP_EQ(test, &mask_empty); EXPECT_FOR_EACH_CPU_OP_EQ(test, and, &mask_empty, &mask_empty); EXPECT_FOR_EACH_CPU_OP_EQ(test, and, cpu_possible_mask, &mask_empty); EXPECT_FOR_EACH_CPU_OP_EQ(test, andnot, &mask_empty, &mask_empty); EXPECT_FOR_EACH_CPU_EQ(test, cpu_possible_mask); - EXPECT_FOR_EACH_CPU_NOT_EQ(test, cpu_possible_mask); EXPECT_FOR_EACH_CPU_WRAP_EQ(test, cpu_possible_mask); EXPECT_FOR_EACH_CPU_OP_EQ(test, and, cpu_possible_mask, cpu_possible_mask); EXPECT_FOR_EACH_CPU_OP_EQ(test, andnot, cpu_possible_mask, &mask_empty); diff --git a/lib/debugobjects.c b/lib/debugobjects.c index df86e649d8be..b796799fadb2 100644 --- a/lib/debugobjects.c +++ b/lib/debugobjects.c @@ -216,10 +216,6 @@ static struct debug_obj *__alloc_object(struct hlist_head *list) return obj; } -/* - * Allocate a new object. If the pool is empty, switch off the debugger. - * Must be called with interrupts disabled. - */ static struct debug_obj * alloc_object(void *addr, struct debug_bucket *b, const struct debug_obj_descr *descr) { @@ -552,11 +548,49 @@ static void debug_object_is_on_stack(void *addr, int onstack) WARN_ON(1); } +static struct debug_obj *lookup_object_or_alloc(void *addr, struct debug_bucket *b, + const struct debug_obj_descr *descr, + bool onstack, bool alloc_ifstatic) +{ + struct debug_obj *obj = lookup_object(addr, b); + enum debug_obj_state state = ODEBUG_STATE_NONE; + + if (likely(obj)) + return obj; + + /* + * debug_object_init() unconditionally allocates untracked + * objects. It does not matter whether it is a static object or + * not. + * + * debug_object_assert_init() and debug_object_activate() allow + * allocation only if the descriptor callback confirms that the + * object is static and considered initialized. For non-static + * objects the allocation needs to be done from the fixup callback. + */ + if (unlikely(alloc_ifstatic)) { + if (!descr->is_static_object || !descr->is_static_object(addr)) + return ERR_PTR(-ENOENT); + /* Statically allocated objects are considered initialized */ + state = ODEBUG_STATE_INIT; + } + + obj = alloc_object(addr, b, descr); + if (likely(obj)) { + obj->state = state; + debug_object_is_on_stack(addr, onstack); + return obj; + } + + /* Out of memory. Do the cleanup outside of the locked region */ + debug_objects_enabled = 0; + return NULL; +} + static void __debug_object_init(void *addr, const struct debug_obj_descr *descr, int onstack) { enum debug_obj_state state; - bool check_stack = false; struct debug_bucket *db; struct debug_obj *obj; unsigned long flags; @@ -572,16 +606,11 @@ __debug_object_init(void *addr, const struct debug_obj_descr *descr, int onstack raw_spin_lock_irqsave(&db->lock, flags); - obj = lookup_object(addr, db); - if (!obj) { - obj = alloc_object(addr, db, descr); - if (!obj) { - debug_objects_enabled = 0; - raw_spin_unlock_irqrestore(&db->lock, flags); - debug_objects_oom(); - return; - } - check_stack = true; + obj = lookup_object_or_alloc(addr, db, descr, onstack, false); + if (unlikely(!obj)) { + raw_spin_unlock_irqrestore(&db->lock, flags); + debug_objects_oom(); + return; } switch (obj->state) { @@ -607,8 +636,6 @@ __debug_object_init(void *addr, const struct debug_obj_descr *descr, int onstack } raw_spin_unlock_irqrestore(&db->lock, flags); - if (check_stack) - debug_object_is_on_stack(addr, onstack); } /** @@ -648,14 +675,12 @@ EXPORT_SYMBOL_GPL(debug_object_init_on_stack); */ int debug_object_activate(void *addr, const struct debug_obj_descr *descr) { + struct debug_obj o = { .object = addr, .state = ODEBUG_STATE_NOTAVAILABLE, .descr = descr }; enum debug_obj_state state; struct debug_bucket *db; struct debug_obj *obj; unsigned long flags; int ret; - struct debug_obj o = { .object = addr, - .state = ODEBUG_STATE_NOTAVAILABLE, - .descr = descr }; if (!debug_objects_enabled) return 0; @@ -664,8 +689,8 @@ int debug_object_activate(void *addr, const struct debug_obj_descr *descr) raw_spin_lock_irqsave(&db->lock, flags); - obj = lookup_object(addr, db); - if (obj) { + obj = lookup_object_or_alloc(addr, db, descr, false, true); + if (likely(!IS_ERR_OR_NULL(obj))) { bool print_object = false; switch (obj->state) { @@ -698,24 +723,16 @@ int debug_object_activate(void *addr, const struct debug_obj_descr *descr) raw_spin_unlock_irqrestore(&db->lock, flags); - /* - * We are here when a static object is activated. We - * let the type specific code confirm whether this is - * true or not. if true, we just make sure that the - * static object is tracked in the object tracker. If - * not, this must be a bug, so we try to fix it up. - */ - if (descr->is_static_object && descr->is_static_object(addr)) { - /* track this static object */ - debug_object_init(addr, descr); - debug_object_activate(addr, descr); - } else { - debug_print_object(&o, "activate"); - ret = debug_object_fixup(descr->fixup_activate, addr, - ODEBUG_STATE_NOTAVAILABLE); - return ret ? 0 : -EINVAL; + /* If NULL the allocation has hit OOM */ + if (!obj) { + debug_objects_oom(); + return 0; } - return 0; + + /* Object is neither static nor tracked. It's not initialized */ + debug_print_object(&o, "activate"); + ret = debug_object_fixup(descr->fixup_activate, addr, ODEBUG_STATE_NOTAVAILABLE); + return ret ? 0 : -EINVAL; } EXPORT_SYMBOL_GPL(debug_object_activate); @@ -869,6 +886,7 @@ EXPORT_SYMBOL_GPL(debug_object_free); */ void debug_object_assert_init(void *addr, const struct debug_obj_descr *descr) { + struct debug_obj o = { .object = addr, .state = ODEBUG_STATE_NOTAVAILABLE, .descr = descr }; struct debug_bucket *db; struct debug_obj *obj; unsigned long flags; @@ -879,31 +897,20 @@ void debug_object_assert_init(void *addr, const struct debug_obj_descr *descr) db = get_bucket((unsigned long) addr); raw_spin_lock_irqsave(&db->lock, flags); + obj = lookup_object_or_alloc(addr, db, descr, false, true); + raw_spin_unlock_irqrestore(&db->lock, flags); + if (likely(!IS_ERR_OR_NULL(obj))) + return; - obj = lookup_object(addr, db); + /* If NULL the allocation has hit OOM */ if (!obj) { - struct debug_obj o = { .object = addr, - .state = ODEBUG_STATE_NOTAVAILABLE, - .descr = descr }; - - raw_spin_unlock_irqrestore(&db->lock, flags); - /* - * Maybe the object is static, and we let the type specific - * code confirm. Track this static object if true, else invoke - * fixup. - */ - if (descr->is_static_object && descr->is_static_object(addr)) { - /* Track this static object */ - debug_object_init(addr, descr); - } else { - debug_print_object(&o, "assert_init"); - debug_object_fixup(descr->fixup_assert_init, addr, - ODEBUG_STATE_NOTAVAILABLE); - } + debug_objects_oom(); return; } - raw_spin_unlock_irqrestore(&db->lock, flags); + /* Object is neither tracked nor static. It's not initialized. */ + debug_print_object(&o, "assert_init"); + debug_object_fixup(descr->fixup_assert_init, addr, ODEBUG_STATE_NOTAVAILABLE); } EXPORT_SYMBOL_GPL(debug_object_assert_init); 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..f15ac666e9d3 --- /dev/null +++ b/lib/dhry_run.c @@ -0,0 +1,87 @@ +// 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) +{ + unsigned int cpu = get_cpu(); + 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: + put_cpu(); + if (n >= 0) + pr_info("CPU%u: Dhrystones per Second: %d (%d DMIPS)\n", cpu, + 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/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 c10920e66788..32f99e9a670e 100644 --- a/lib/find_bit.c +++ b/lib/find_bit.c @@ -182,6 +182,15 @@ unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned l EXPORT_SYMBOL(_find_next_andnot_bit); #endif +#ifndef find_next_or_bit +unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2, + unsigned long nbits, unsigned long start) +{ + return FIND_NEXT_BIT(addr1[idx] | addr2[idx], /* nop */, nbits, start); +} +EXPORT_SYMBOL(_find_next_or_bit); +#endif + #ifndef find_next_zero_bit unsigned long _find_next_zero_bit(const unsigned long *addr, 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/iov_iter.c b/lib/iov_iter.c index 274014e4eafe..967fba189c5f 100644 --- a/lib/iov_iter.c +++ b/lib/iov_iter.c @@ -126,13 +126,13 @@ __out: \ iterate_buf(i, n, base, len, off, \ i->ubuf, (I)) \ } else if (likely(iter_is_iovec(i))) { \ - const struct iovec *iov = i->iov; \ + const struct iovec *iov = iter_iov(i); \ void __user *base; \ size_t len; \ iterate_iovec(i, n, base, len, off, \ iov, (I)) \ - i->nr_segs -= iov - i->iov; \ - i->iov = iov; \ + i->nr_segs -= iov - iter_iov(i); \ + i->__iov = iov; \ } else if (iov_iter_is_bvec(i)) { \ const struct bio_vec *bvec = i->bvec; \ void *base; \ @@ -355,7 +355,7 @@ size_t fault_in_iov_iter_readable(const struct iov_iter *i, size_t size) size_t skip; size -= count; - for (p = i->iov, skip = i->iov_offset; count; p++, skip = 0) { + for (p = iter_iov(i), skip = i->iov_offset; count; p++, skip = 0) { size_t len = min(count, p->iov_len - skip); size_t ret; @@ -398,7 +398,7 @@ size_t fault_in_iov_iter_writeable(const struct iov_iter *i, size_t size) size_t skip; size -= count; - for (p = i->iov, skip = i->iov_offset; count; p++, skip = 0) { + for (p = iter_iov(i), skip = i->iov_offset; count; p++, skip = 0) { size_t len = min(count, p->iov_len - skip); size_t ret; @@ -425,7 +425,7 @@ void iov_iter_init(struct iov_iter *i, unsigned int direction, .nofault = false, .user_backed = true, .data_source = direction, - .iov = iov, + .__iov = iov, .nr_segs = nr_segs, .iov_offset = 0, .count = count @@ -876,14 +876,14 @@ static void iov_iter_iovec_advance(struct iov_iter *i, size_t size) i->count -= size; size += i->iov_offset; // from beginning of current segment - for (iov = i->iov, end = iov + i->nr_segs; iov < end; iov++) { + for (iov = iter_iov(i), end = iov + i->nr_segs; iov < end; iov++) { if (likely(size < iov->iov_len)) break; size -= iov->iov_len; } i->iov_offset = size; - i->nr_segs -= iov - i->iov; - i->iov = iov; + i->nr_segs -= iov - iter_iov(i); + i->__iov = iov; } void iov_iter_advance(struct iov_iter *i, size_t size) @@ -958,12 +958,12 @@ void iov_iter_revert(struct iov_iter *i, size_t unroll) unroll -= n; } } else { /* same logics for iovec and kvec */ - const struct iovec *iov = i->iov; + const struct iovec *iov = iter_iov(i); while (1) { size_t n = (--iov)->iov_len; i->nr_segs++; if (unroll <= n) { - i->iov = iov; + i->__iov = iov; i->iov_offset = n - unroll; return; } @@ -980,7 +980,7 @@ size_t iov_iter_single_seg_count(const struct iov_iter *i) { if (i->nr_segs > 1) { if (likely(iter_is_iovec(i) || iov_iter_is_kvec(i))) - return min(i->count, i->iov->iov_len - i->iov_offset); + return min(i->count, iter_iov(i)->iov_len - i->iov_offset); if (iov_iter_is_bvec(i)) return min(i->count, i->bvec->bv_len - i->iov_offset); } @@ -1095,13 +1095,14 @@ static bool iov_iter_aligned_iovec(const struct iov_iter *i, unsigned addr_mask, unsigned k; for (k = 0; k < i->nr_segs; k++, skip = 0) { - size_t len = i->iov[k].iov_len - skip; + const struct iovec *iov = iter_iov(i) + k; + size_t len = iov->iov_len - skip; if (len > size) len = size; if (len & len_mask) return false; - if ((unsigned long)(i->iov[k].iov_base + skip) & addr_mask) + if ((unsigned long)(iov->iov_base + skip) & addr_mask) return false; size -= len; @@ -1194,9 +1195,10 @@ static unsigned long iov_iter_alignment_iovec(const struct iov_iter *i) unsigned k; for (k = 0; k < i->nr_segs; k++, skip = 0) { - size_t len = i->iov[k].iov_len - skip; + const struct iovec *iov = iter_iov(i) + k; + size_t len = iov->iov_len - skip; if (len) { - res |= (unsigned long)i->iov[k].iov_base + skip; + res |= (unsigned long)iov->iov_base + skip; if (len > size) len = size; res |= len; @@ -1273,14 +1275,15 @@ unsigned long iov_iter_gap_alignment(const struct iov_iter *i) return ~0U; for (k = 0; k < i->nr_segs; k++) { - if (i->iov[k].iov_len) { - unsigned long base = (unsigned long)i->iov[k].iov_base; + const struct iovec *iov = iter_iov(i) + k; + if (iov->iov_len) { + unsigned long base = (unsigned long)iov->iov_base; if (v) // if not the first one res |= base | v; // this start | previous end - v = base + i->iov[k].iov_len; - if (size <= i->iov[k].iov_len) + v = base + iov->iov_len; + if (size <= iov->iov_len) break; - size -= i->iov[k].iov_len; + size -= iov->iov_len; } } return res; @@ -1396,13 +1399,14 @@ static unsigned long first_iovec_segment(const struct iov_iter *i, size_t *size) return (unsigned long)i->ubuf + i->iov_offset; for (k = 0, skip = i->iov_offset; k < i->nr_segs; k++, skip = 0) { - size_t len = i->iov[k].iov_len - skip; + const struct iovec *iov = iter_iov(i) + k; + size_t len = iov->iov_len - skip; if (unlikely(!len)) continue; if (*size > len) *size = len; - return (unsigned long)i->iov[k].iov_base + skip; + return (unsigned long)iov->iov_base + skip; } BUG(); // if it had been empty, we wouldn't get called } @@ -1614,7 +1618,7 @@ static int iov_npages(const struct iov_iter *i, int maxpages) const struct iovec *p; int npages = 0; - for (p = i->iov; size; skip = 0, p++) { + for (p = iter_iov(i); size; skip = 0, p++) { unsigned offs = offset_in_page(p->iov_base + skip); size_t len = min(p->iov_len - skip, size); @@ -1691,14 +1695,14 @@ const void *dup_iter(struct iov_iter *new, struct iov_iter *old, gfp_t flags) flags); else if (iov_iter_is_kvec(new) || iter_is_iovec(new)) /* iovec and kvec have identical layout */ - return new->iov = kmemdup(new->iov, + return new->__iov = kmemdup(new->__iov, new->nr_segs * sizeof(struct iovec), flags); return NULL; } EXPORT_SYMBOL(dup_iter); -static int copy_compat_iovec_from_user(struct iovec *iov, +static __noclone int copy_compat_iovec_from_user(struct iovec *iov, const struct iovec __user *uvec, unsigned long nr_segs) { const struct compat_iovec __user *uiov = @@ -1731,18 +1735,35 @@ uaccess_end: } static int copy_iovec_from_user(struct iovec *iov, - const struct iovec __user *uvec, unsigned long nr_segs) + const struct iovec __user *uiov, unsigned long nr_segs) { - unsigned long seg; + int ret = -EFAULT; - if (copy_from_user(iov, uvec, nr_segs * sizeof(*uvec))) + if (!user_access_begin(uiov, nr_segs * sizeof(*uiov))) return -EFAULT; - for (seg = 0; seg < nr_segs; seg++) { - if ((ssize_t)iov[seg].iov_len < 0) - return -EINVAL; - } - return 0; + do { + void __user *buf; + ssize_t len; + + unsafe_get_user(len, &uiov->iov_len, uaccess_end); + unsafe_get_user(buf, &uiov->iov_base, uaccess_end); + + /* check for size_t not fitting in ssize_t .. */ + if (unlikely(len < 0)) { + ret = -EINVAL; + goto uaccess_end; + } + iov->iov_base = buf; + iov->iov_len = len; + + uiov++; iov++; + } while (--nr_segs); + + ret = 0; +uaccess_end: + user_access_end(); + return ret; } struct iovec *iovec_from_user(const struct iovec __user *uvec, @@ -1767,7 +1788,7 @@ struct iovec *iovec_from_user(const struct iovec __user *uvec, return ERR_PTR(-ENOMEM); } - if (compat) + if (unlikely(compat)) ret = copy_compat_iovec_from_user(iov, uvec, nr_segs); else ret = copy_iovec_from_user(iov, uvec, nr_segs); @@ -1780,6 +1801,30 @@ struct iovec *iovec_from_user(const struct iovec __user *uvec, return iov; } +/* + * Single segment iovec supplied by the user, import it as ITER_UBUF. + */ +static ssize_t __import_iovec_ubuf(int type, const struct iovec __user *uvec, + struct iovec **iovp, struct iov_iter *i, + bool compat) +{ + struct iovec *iov = *iovp; + ssize_t ret; + + if (compat) + ret = copy_compat_iovec_from_user(iov, uvec, 1); + else + ret = copy_iovec_from_user(iov, uvec, 1); + if (unlikely(ret)) + return ret; + + ret = import_ubuf(type, iov->iov_base, iov->iov_len, i); + if (unlikely(ret)) + return ret; + *iovp = NULL; + return i->count; +} + ssize_t __import_iovec(int type, const struct iovec __user *uvec, unsigned nr_segs, unsigned fast_segs, struct iovec **iovp, struct iov_iter *i, bool compat) @@ -1788,6 +1833,9 @@ ssize_t __import_iovec(int type, const struct iovec __user *uvec, unsigned long seg; struct iovec *iov; + if (nr_segs == 1) + return __import_iovec_ubuf(type, uvec, iovp, i, compat); + iov = iovec_from_user(uvec, nr_segs, fast_segs, *iovp, compat); if (IS_ERR(iov)) { *iovp = NULL; @@ -1866,9 +1914,7 @@ int import_single_range(int rw, void __user *buf, size_t len, if (unlikely(!access_ok(buf, len))) return -EFAULT; - iov->iov_base = buf; - iov->iov_len = len; - iov_iter_init(i, rw, iov, 1, len); + iov_iter_ubuf(i, rw, buf, len); return 0; } EXPORT_SYMBOL(import_single_range); @@ -1918,7 +1964,7 @@ void iov_iter_restore(struct iov_iter *i, struct iov_iter_state *state) if (iov_iter_is_bvec(i)) i->bvec -= state->nr_segs - i->nr_segs; else - i->iov -= state->nr_segs - i->nr_segs; + i->__iov -= state->nr_segs - i->nr_segs; i->nr_segs = state->nr_segs; } 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 da665cd4ea12..cb417f504996 100644 --- a/lib/kunit/Makefile +++ b/lib/kunit/Makefile @@ -13,7 +13,7 @@ kunit-objs += debugfs.o endif # KUnit 'hooks' are built-in even when KUnit is built as a module. -lib-y += hooks.o +obj-y += hooks.o obj-$(CONFIG_KUNIT_TEST) += kunit-test.o diff --git a/lib/kunit/debugfs.c b/lib/kunit/debugfs.c index de0ee2e03ed6..b08bb1fba106 100644 --- a/lib/kunit/debugfs.c +++ b/lib/kunit/debugfs.c @@ -55,14 +55,24 @@ static int debugfs_print_results(struct seq_file *seq, void *v) enum kunit_status success = kunit_suite_has_succeeded(suite); struct kunit_case *test_case; - if (!suite || !suite->log) + if (!suite) return 0; - seq_printf(seq, "%s", suite->log); + /* Print KTAP header so the debugfs log can be parsed as valid KTAP. */ + seq_puts(seq, "KTAP version 1\n"); + seq_puts(seq, "1..1\n"); + + /* Print suite header because it is not stored in the test logs. */ + seq_puts(seq, KUNIT_SUBTEST_INDENT "KTAP version 1\n"); + seq_printf(seq, KUNIT_SUBTEST_INDENT "# Subtest: %s\n", suite->name); + seq_printf(seq, KUNIT_SUBTEST_INDENT "1..%zd\n", kunit_suite_num_test_cases(suite)); kunit_suite_for_each_test_case(suite, test_case) debugfs_print_result(seq, suite, test_case); + if (suite->log) + seq_printf(seq, "%s", suite->log); + seq_printf(seq, "%s %d %s\n", kunit_status_to_ok_not_ok(success), 1, suite->name); return 0; diff --git a/lib/kunit/kunit-test.c b/lib/kunit/kunit-test.c index 4df0335d0d06..42e44caa1bdd 100644 --- a/lib/kunit/kunit-test.c +++ b/lib/kunit/kunit-test.c @@ -6,6 +6,7 @@ * Author: Brendan Higgins <brendanhiggins@google.com> */ #include <kunit/test.h> +#include <kunit/test-bug.h> #include "try-catch-impl.h" @@ -443,18 +444,6 @@ static struct kunit_suite kunit_resource_test_suite = { .test_cases = kunit_resource_test_cases, }; -static void kunit_log_test(struct kunit *test); - -static struct kunit_case kunit_log_test_cases[] = { - KUNIT_CASE(kunit_log_test), - {} -}; - -static struct kunit_suite kunit_log_test_suite = { - .name = "kunit-log-test", - .test_cases = kunit_log_test_cases, -}; - static void kunit_log_test(struct kunit *test) { struct kunit_suite suite; @@ -481,6 +470,29 @@ static void kunit_log_test(struct kunit *test) #endif } +static void kunit_log_newline_test(struct kunit *test) +{ + kunit_info(test, "Add newline\n"); + if (test->log) { + KUNIT_ASSERT_NOT_NULL_MSG(test, strstr(test->log, "Add newline\n"), + "Missing log line, full log:\n%s", test->log); + KUNIT_EXPECT_NULL(test, strstr(test->log, "Add newline\n\n")); + } else { + kunit_skip(test, "only useful when debugfs is enabled"); + } +} + +static struct kunit_case kunit_log_test_cases[] = { + KUNIT_CASE(kunit_log_test), + KUNIT_CASE(kunit_log_newline_test), + {} +}; + +static struct kunit_suite kunit_log_test_suite = { + .name = "kunit-log-test", + .test_cases = kunit_log_test_cases, +}; + static void kunit_status_set_failure_test(struct kunit *test) { struct kunit fake; @@ -521,7 +533,46 @@ static struct kunit_suite kunit_status_test_suite = { .test_cases = kunit_status_test_cases, }; +static void kunit_current_test(struct kunit *test) +{ + /* Check results of both current->kunit_test and + * kunit_get_current_test() are equivalent to current test. + */ + KUNIT_EXPECT_PTR_EQ(test, test, current->kunit_test); + KUNIT_EXPECT_PTR_EQ(test, test, kunit_get_current_test()); +} + +static void kunit_current_fail_test(struct kunit *test) +{ + struct kunit fake; + + kunit_init_test(&fake, "fake test", NULL); + KUNIT_EXPECT_EQ(test, fake.status, KUNIT_SUCCESS); + + /* Set current->kunit_test to fake test. */ + current->kunit_test = &fake; + + kunit_fail_current_test("This should make `fake` test fail."); + KUNIT_EXPECT_EQ(test, fake.status, (enum kunit_status)KUNIT_FAILURE); + kunit_cleanup(&fake); + + /* Reset current->kunit_test to current test. */ + current->kunit_test = test; +} + +static struct kunit_case kunit_current_test_cases[] = { + KUNIT_CASE(kunit_current_test), + KUNIT_CASE(kunit_current_fail_test), + {} +}; + +static struct kunit_suite kunit_current_test_suite = { + .name = "kunit_current", + .test_cases = kunit_current_test_cases, +}; + kunit_test_suites(&kunit_try_catch_test_suite, &kunit_resource_test_suite, - &kunit_log_test_suite, &kunit_status_test_suite); + &kunit_log_test_suite, &kunit_status_test_suite, + &kunit_current_test_suite); MODULE_LICENSE("GPL v2"); diff --git a/lib/kunit/test.c b/lib/kunit/test.c index c9e15bb60058..e2910b261112 100644 --- a/lib/kunit/test.c +++ b/lib/kunit/test.c @@ -108,28 +108,51 @@ static void kunit_print_test_stats(struct kunit *test, stats.total); } +/** + * kunit_log_newline() - Add newline to the end of log if one is not + * already present. + * @log: The log to add the newline to. + */ +static void kunit_log_newline(char *log) +{ + int log_len, len_left; + + log_len = strlen(log); + len_left = KUNIT_LOG_SIZE - log_len - 1; + + if (log_len > 0 && log[log_len - 1] != '\n') + strncat(log, "\n", len_left); +} + /* * Append formatted message to log, size of which is limited to * KUNIT_LOG_SIZE bytes (including null terminating byte). */ void kunit_log_append(char *log, const char *fmt, ...) { - char line[KUNIT_LOG_SIZE]; va_list args; - int len_left; + int len, log_len, len_left; if (!log) return; - len_left = KUNIT_LOG_SIZE - strlen(log) - 1; + log_len = strlen(log); + len_left = KUNIT_LOG_SIZE - log_len - 1; if (len_left <= 0) return; + /* Evaluate length of line to add to log */ + va_start(args, fmt); + len = vsnprintf(NULL, 0, fmt, args) + 1; + va_end(args); + + /* Print formatted line to the log */ va_start(args, fmt); - vsnprintf(line, sizeof(line), fmt, args); + vsnprintf(log + log_len, min(len, len_left), fmt, args); va_end(args); - strncat(log, line, len_left); + /* Add newline to end of log if not already present. */ + kunit_log_newline(log); } EXPORT_SYMBOL_GPL(kunit_log_append); @@ -147,10 +170,18 @@ EXPORT_SYMBOL_GPL(kunit_suite_num_test_cases); static void kunit_print_suite_start(struct kunit_suite *suite) { - kunit_log(KERN_INFO, suite, KUNIT_SUBTEST_INDENT "KTAP version 1\n"); - kunit_log(KERN_INFO, suite, KUNIT_SUBTEST_INDENT "# Subtest: %s", + /* + * We do not log the test suite header as doing so would + * mean debugfs display would consist of the test suite + * header prior to individual test results. + * Hence directly printk the suite status, and we will + * separately seq_printf() the suite header for the debugfs + * representation. + */ + pr_info(KUNIT_SUBTEST_INDENT "KTAP version 1\n"); + pr_info(KUNIT_SUBTEST_INDENT "# Subtest: %s\n", suite->name); - kunit_log(KERN_INFO, suite, KUNIT_SUBTEST_INDENT "1..%zd", + pr_info(KUNIT_SUBTEST_INDENT "1..%zd\n", kunit_suite_num_test_cases(suite)); } @@ -167,10 +198,9 @@ static void kunit_print_ok_not_ok(void *test_or_suite, /* * We do not log the test suite results as doing so would - * mean debugfs display would consist of the test suite - * description and status prior to individual test results. - * Hence directly printk the suite status, and we will - * separately seq_printf() the suite status for the debugfs + * mean debugfs display would consist of an incorrect test + * number. Hence directly printk the suite result, and we will + * separately seq_printf() the suite results for the debugfs * representation. */ if (suite) @@ -437,7 +467,6 @@ static void kunit_run_case_catch_errors(struct kunit_suite *suite, struct kunit_try_catch_context context; struct kunit_try_catch *try_catch; - kunit_init_test(test, test_case->name, test_case->log); try_catch = &test->try_catch; kunit_try_catch_init(try_catch, @@ -533,6 +562,8 @@ int kunit_run_tests(struct kunit_suite *suite) struct kunit_result_stats param_stats = { 0 }; test_case->status = KUNIT_SKIPPED; + kunit_init_test(&test, test_case->name, test_case->log); + if (!test_case->generate_params) { /* Non-parameterised test. */ kunit_run_case_catch_errors(suite, test_case, &test); diff --git a/lib/list-test.c b/lib/list-test.c index d374cf5d1a57..0cc27de9cec8 100644 --- a/lib/list-test.c +++ b/lib/list-test.c @@ -8,6 +8,7 @@ #include <kunit/test.h> #include <linux/list.h> +#include <linux/klist.h> struct list_test_struct { int data; @@ -1199,6 +1200,303 @@ static struct kunit_suite hlist_test_module = { .test_cases = hlist_test_cases, }; -kunit_test_suites(&list_test_module, &hlist_test_module); + +struct klist_test_struct { + int data; + struct klist klist; + struct klist_node klist_node; +}; + +static int node_count; +static struct klist_node *last_node; + +static void check_node(struct klist_node *node_ptr) +{ + node_count++; + last_node = node_ptr; +} + +static void check_delete_node(struct klist_node *node_ptr) +{ + node_count--; + last_node = node_ptr; +} + +static void klist_test_add_tail(struct kunit *test) +{ + struct klist_node a, b; + struct klist mylist; + struct klist_iter i; + + node_count = 0; + klist_init(&mylist, &check_node, NULL); + + klist_add_tail(&a, &mylist); + KUNIT_EXPECT_EQ(test, node_count, 1); + KUNIT_EXPECT_PTR_EQ(test, last_node, &a); + + klist_add_tail(&b, &mylist); + KUNIT_EXPECT_EQ(test, node_count, 2); + KUNIT_EXPECT_PTR_EQ(test, last_node, &b); + + /* should be [list] -> a -> b */ + klist_iter_init(&mylist, &i); + + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); + KUNIT_EXPECT_NULL(test, klist_next(&i)); + + klist_iter_exit(&i); + +} + +static void klist_test_add_head(struct kunit *test) +{ + struct klist_node a, b; + struct klist mylist; + struct klist_iter i; + + node_count = 0; + klist_init(&mylist, &check_node, NULL); + + klist_add_head(&a, &mylist); + KUNIT_EXPECT_EQ(test, node_count, 1); + KUNIT_EXPECT_PTR_EQ(test, last_node, &a); + + klist_add_head(&b, &mylist); + KUNIT_EXPECT_EQ(test, node_count, 2); + KUNIT_EXPECT_PTR_EQ(test, last_node, &b); + + /* should be [list] -> b -> a */ + klist_iter_init(&mylist, &i); + + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); + KUNIT_EXPECT_NULL(test, klist_next(&i)); + + klist_iter_exit(&i); + +} + +static void klist_test_add_behind(struct kunit *test) +{ + struct klist_node a, b, c, d; + struct klist mylist; + struct klist_iter i; + + node_count = 0; + klist_init(&mylist, &check_node, NULL); + + klist_add_head(&a, &mylist); + klist_add_head(&b, &mylist); + + klist_add_behind(&c, &a); + KUNIT_EXPECT_EQ(test, node_count, 3); + KUNIT_EXPECT_PTR_EQ(test, last_node, &c); + + klist_add_behind(&d, &b); + KUNIT_EXPECT_EQ(test, node_count, 4); + KUNIT_EXPECT_PTR_EQ(test, last_node, &d); + + klist_iter_init(&mylist, &i); + + /* should be [list] -> b -> d -> a -> c*/ + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c); + KUNIT_EXPECT_NULL(test, klist_next(&i)); + + klist_iter_exit(&i); + +} + +static void klist_test_add_before(struct kunit *test) +{ + struct klist_node a, b, c, d; + struct klist mylist; + struct klist_iter i; + + node_count = 0; + klist_init(&mylist, &check_node, NULL); + + klist_add_head(&a, &mylist); + klist_add_head(&b, &mylist); + klist_add_before(&c, &a); + KUNIT_EXPECT_EQ(test, node_count, 3); + KUNIT_EXPECT_PTR_EQ(test, last_node, &c); + + klist_add_before(&d, &b); + KUNIT_EXPECT_EQ(test, node_count, 4); + KUNIT_EXPECT_PTR_EQ(test, last_node, &d); + + klist_iter_init(&mylist, &i); + + /* should be [list] -> b -> d -> a -> c*/ + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); + KUNIT_EXPECT_NULL(test, klist_next(&i)); + + klist_iter_exit(&i); + +} + +/* + * Verify that klist_del() delays the deletion of a node until there + * are no other references to it + */ +static void klist_test_del_refcount_greater_than_zero(struct kunit *test) +{ + struct klist_node a, b, c, d; + struct klist mylist; + struct klist_iter i; + + node_count = 0; + klist_init(&mylist, &check_node, &check_delete_node); + + /* Add nodes a,b,c,d to the list*/ + klist_add_tail(&a, &mylist); + klist_add_tail(&b, &mylist); + klist_add_tail(&c, &mylist); + klist_add_tail(&d, &mylist); + + klist_iter_init(&mylist, &i); + + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); + /* Advance the iterator to point to node c*/ + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c); + + /* Try to delete node c while there is a reference to it*/ + klist_del(&c); + + /* + * Verify that node c is still attached to the list even after being + * deleted. Since the iterator still points to c, the reference count is not + * decreased to 0 + */ + KUNIT_EXPECT_TRUE(test, klist_node_attached(&c)); + + /* Check that node c has not been removed yet*/ + KUNIT_EXPECT_EQ(test, node_count, 4); + KUNIT_EXPECT_PTR_EQ(test, last_node, &d); + + klist_iter_exit(&i); + + /* + * Since the iterator is no longer pointing to node c, node c is removed + * from the list + */ + KUNIT_EXPECT_EQ(test, node_count, 3); + KUNIT_EXPECT_PTR_EQ(test, last_node, &c); + +} + +/* + * Verify that klist_del() deletes a node immediately when there are no + * other references to it. + */ +static void klist_test_del_refcount_zero(struct kunit *test) +{ + struct klist_node a, b, c, d; + struct klist mylist; + struct klist_iter i; + + node_count = 0; + klist_init(&mylist, &check_node, &check_delete_node); + + /* Add nodes a,b,c,d to the list*/ + klist_add_tail(&a, &mylist); + klist_add_tail(&b, &mylist); + klist_add_tail(&c, &mylist); + klist_add_tail(&d, &mylist); + /* Delete node c*/ + klist_del(&c); + + /* Check that node c is deleted from the list*/ + KUNIT_EXPECT_EQ(test, node_count, 3); + KUNIT_EXPECT_PTR_EQ(test, last_node, &c); + + /* Should be [list] -> a -> b -> d*/ + klist_iter_init(&mylist, &i); + + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d); + KUNIT_EXPECT_NULL(test, klist_next(&i)); + + klist_iter_exit(&i); + +} + +static void klist_test_remove(struct kunit *test) +{ + /* This test doesn't check correctness under concurrent access */ + struct klist_node a, b, c, d; + struct klist mylist; + struct klist_iter i; + + node_count = 0; + klist_init(&mylist, &check_node, &check_delete_node); + + /* Add nodes a,b,c,d to the list*/ + klist_add_tail(&a, &mylist); + klist_add_tail(&b, &mylist); + klist_add_tail(&c, &mylist); + klist_add_tail(&d, &mylist); + /* Delete node c*/ + klist_remove(&c); + + /* Check the nodes in the list*/ + KUNIT_EXPECT_EQ(test, node_count, 3); + KUNIT_EXPECT_PTR_EQ(test, last_node, &c); + + /* should be [list] -> a -> b -> d*/ + klist_iter_init(&mylist, &i); + + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); + KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d); + KUNIT_EXPECT_NULL(test, klist_next(&i)); + + klist_iter_exit(&i); + +} + +static void klist_test_node_attached(struct kunit *test) +{ + struct klist_node a = {}; + struct klist mylist; + + klist_init(&mylist, NULL, NULL); + + KUNIT_EXPECT_FALSE(test, klist_node_attached(&a)); + klist_add_head(&a, &mylist); + KUNIT_EXPECT_TRUE(test, klist_node_attached(&a)); + klist_del(&a); + KUNIT_EXPECT_FALSE(test, klist_node_attached(&a)); + +} + +static struct kunit_case klist_test_cases[] = { + KUNIT_CASE(klist_test_add_tail), + KUNIT_CASE(klist_test_add_head), + KUNIT_CASE(klist_test_add_behind), + KUNIT_CASE(klist_test_add_before), + KUNIT_CASE(klist_test_del_refcount_greater_than_zero), + KUNIT_CASE(klist_test_del_refcount_zero), + KUNIT_CASE(klist_test_remove), + KUNIT_CASE(klist_test_node_attached), + {}, +}; + +static struct kunit_suite klist_test_module = { + .name = "klist", + .test_cases = klist_test_cases, +}; + +kunit_test_suites(&list_test_module, &hlist_test_module, &klist_test_module); MODULE_LICENSE("GPL v2"); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 5a976393c9ae..1281a40d5735 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) @@ -179,11 +185,10 @@ static void mt_free_rcu(struct rcu_head *head) */ static void ma_free_rcu(struct maple_node *node) { - node->parent = ma_parent_ptr(node); + WARN_ON(node->parent != ma_parent_ptr(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; /* @@ -535,11 +539,14 @@ static inline struct maple_node *mte_parent(const struct maple_enode *enode) */ static inline bool ma_dead_node(const struct maple_node *node) { - struct maple_node *parent = (void *)((unsigned long) - node->parent & ~MAPLE_NODE_MASK); + struct maple_node *parent; + /* Do not reorder reads from the node prior to the parent check */ + smp_rmb(); + parent = (void *)((unsigned long) node->parent & ~MAPLE_NODE_MASK); return (parent == node); } + /* * mte_dead_node() - check if the @enode is dead. * @enode: The encoded maple node @@ -551,6 +558,8 @@ static inline bool mte_dead_node(const struct maple_enode *enode) struct maple_node *parent, *node; node = mte_to_node(enode); + /* Do not reorder reads from the node prior to the parent check */ + smp_rmb(); parent = mte_parent(enode); return (parent == node); } @@ -621,6 +630,8 @@ static inline unsigned int mas_alloc_req(const struct ma_state *mas) * @node - the maple node * @type - the node type * + * In the event of a dead node, this array may be %NULL + * * Return: A pointer to the maple node pivots */ static inline unsigned long *ma_pivots(struct maple_node *node, @@ -813,6 +824,11 @@ static inline void *mt_slot(const struct maple_tree *mt, return rcu_dereference_check(slots[offset], mt_locked(mt)); } +static inline void *mt_slot_locked(struct maple_tree *mt, void __rcu **slots, + unsigned char offset) +{ + return rcu_dereference_protected(slots[offset], mt_locked(mt)); +} /* * mas_slot_locked() - Get the slot value when holding the maple tree lock. * @mas: The maple state @@ -824,7 +840,7 @@ static inline void *mt_slot(const struct maple_tree *mt, static inline void *mas_slot_locked(struct ma_state *mas, void __rcu **slots, unsigned char offset) { - return rcu_dereference_protected(slots[offset], mt_locked(mas->tree)); + return mt_slot_locked(mas->tree, slots, offset); } /* @@ -896,6 +912,45 @@ static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, } /* + * mt_clear_meta() - clear the metadata information of a node, if it exists + * @mt: The maple tree + * @mn: The maple node + * @type: The maple node type + * @offset: The offset of the highest sub-gap in this node. + * @end: The end of the data in this node. + */ +static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn, + enum maple_type type) +{ + struct maple_metadata *meta; + unsigned long *pivots; + void __rcu **slots; + void *next; + + switch (type) { + case maple_range_64: + pivots = mn->mr64.pivot; + if (unlikely(pivots[MAPLE_RANGE64_SLOTS - 2])) { + slots = mn->mr64.slot; + next = mt_slot_locked(mt, slots, + MAPLE_RANGE64_SLOTS - 1); + if (unlikely((mte_to_node(next) && + mte_node_type(next)))) + return; /* no metadata, could be node */ + } + fallthrough; + case maple_arange_64: + meta = ma_meta(mn, type); + break; + default: + return; + } + + meta->gap = 0; + meta->end = 0; +} + +/* * ma_meta_end() - Get the data end of a node from the metadata * @mn: The maple node * @mt: The maple node type @@ -1092,8 +1147,11 @@ static int mas_ascend(struct ma_state *mas) a_type = mas_parent_enum(mas, p_enode); a_node = mte_parent(p_enode); a_slot = mte_parent_slot(p_enode); - pivots = ma_pivots(a_node, a_type); a_enode = mt_mk_node(a_node, a_type); + pivots = ma_pivots(a_node, a_type); + + if (unlikely(ma_dead_node(a_node))) + return 1; if (!set_min && a_slot) { set_min = true; @@ -1128,9 +1186,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) { @@ -1140,27 +1199,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; } @@ -1179,21 +1236,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; } @@ -1212,7 +1268,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; @@ -1228,46 +1283,44 @@ 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; - - slots = (void **)&node->slot[offset]; - max_req -= offset; - } else { - slots = (void **)&node->slot; - } - + max_req = MAPLE_ALLOC_SLOTS - node->node_count; + slots = (void **)&node->slot[node->node_count]; max_req = min(requested, max_req); count = mt_alloc_bulk(gfp, max_req, slots); if (!count) goto nomem_bulk; - node->node_count += count; - /* zero indexed. */ - if (slots == (void **)&node->slot) - node->node_count--; + if (node->node_count == 0) { + node->slot[0]->node_count = 0; + node->slot[0]->request_count = 0; + } - success += count; + node->node_count += count; + allocated += count; node = node->slot[0]; requested -= count; } - mas->alloc->total = success; + mas->alloc->total = allocated; return; nomem_bulk: @@ -1276,10 +1329,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; - } /* @@ -1334,7 +1385,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: @@ -1348,22 +1399,26 @@ 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; +retry: 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; + if (mte_dead_node(mas->node)) + goto retry; + return NULL; } /* empty tree */ if (unlikely(!root)) { + mas->node = MAS_NONE; mas->offset = MAPLE_NODE_SLOTS; return NULL; } @@ -1399,6 +1454,9 @@ static inline unsigned char ma_data_end(struct maple_node *node, { unsigned char offset; + if (!pivots) + return 0; + if (type == maple_arange_64) return ma_meta_end(node, type); @@ -1434,6 +1492,9 @@ static inline unsigned char mas_data_end(struct ma_state *mas) return ma_meta_end(node, type); pivots = ma_pivots(node, type); + if (unlikely(ma_dead_node(node))) + return 0; + offset = mt_pivots[type] - 1; if (likely(!pivots[offset])) return ma_meta_end(node, type); @@ -1722,8 +1783,10 @@ static inline void mas_replace(struct ma_state *mas, bool advanced) rcu_assign_pointer(slots[offset], mas->node); } - if (!advanced) + if (!advanced) { + mte_set_node_dead(old_enode); mas_free(mas, old_enode); + } } /* @@ -1887,10 +1950,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; } @@ -2113,7 +2175,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; @@ -2947,7 +3009,7 @@ next: mas->min = prev_min; mas->max = prev_max; mas->node = last; - return (void *) next; + return (void *)next; dead_node: mas_reset(mas); @@ -3467,7 +3529,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; @@ -3586,7 +3647,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; @@ -3659,10 +3720,9 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) slot++; mas->depth = 1; mas_set_height(mas); - + ma_set_meta(node, maple_leaf_64, 0, slot); /* swap the new root into the tree */ rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); - ma_set_meta(node, maple_leaf_64, 0, slot); return slot; } @@ -3875,25 +3935,20 @@ static inline void *mtree_lookup_walk(struct ma_state *mas) end = ma_data_end(node, type, pivots, max); if (unlikely(ma_dead_node(node))) goto dead_node; - - if (pivots[offset] >= mas->index) - goto next; - do { - offset++; - } while ((offset < end) && (pivots[offset] < mas->index)); - - if (likely(offset > end)) - max = pivots[offset]; + if (pivots[offset] >= mas->index) { + max = pivots[offset]; + break; + } + } while (++offset < end); -next: slots = ma_slots(node, type); next = mt_slot(mas->tree, slots, offset); if (unlikely(ma_dead_node(node))) goto dead_node; } while (!ma_is_leaf(type)); - return (void *) next; + return (void *)next; dead_node: mas_reset(mas); @@ -4164,6 +4219,7 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas) done: mas_leaf_set_meta(mas, newnode, dst_pivots, maple_leaf_64, new_end); if (in_rcu) { + mte_set_node_dead(mas->node); mas->node = mt_mk_node(newnode, wr_mas->type); mas_replace(mas, false); } else { @@ -4505,6 +4561,9 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) node = mas_mn(mas); slots = ma_slots(node, mt); pivots = ma_pivots(node, mt); + if (unlikely(ma_dead_node(node))) + return 1; + mas->max = pivots[offset]; if (offset) mas->min = pivots[offset - 1] + 1; @@ -4526,6 +4585,9 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min) slots = ma_slots(node, mt); pivots = ma_pivots(node, mt); offset = ma_data_end(node, mt, pivots, mas->max); + if (unlikely(ma_dead_node(node))) + return 1; + if (offset) mas->min = pivots[offset - 1] + 1; @@ -4574,6 +4636,7 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, struct maple_enode *enode; int level = 0; unsigned char offset; + unsigned char node_end; enum maple_type mt; void __rcu **slots; @@ -4597,7 +4660,11 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, node = mas_mn(mas); mt = mte_node_type(mas->node); pivots = ma_pivots(node, mt); - } while (unlikely(offset == ma_data_end(node, mt, pivots, mas->max))); + node_end = ma_data_end(node, mt, pivots, mas->max); + if (unlikely(ma_dead_node(node))) + return 1; + + } while (unlikely(offset == node_end)); slots = ma_slots(node, mt); pivot = mas_safe_pivot(mas, pivots, ++offset, mt); @@ -4613,6 +4680,9 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, mt = mte_node_type(mas->node); slots = ma_slots(node, mt); pivots = ma_pivots(node, mt); + if (unlikely(ma_dead_node(node))) + return 1; + offset = 0; pivot = pivots[0]; } @@ -4659,16 +4729,19 @@ static inline void *mas_next_nentry(struct ma_state *mas, return NULL; } - pivots = ma_pivots(node, type); slots = ma_slots(node, type); + pivots = ma_pivots(node, type); + count = ma_data_end(node, type, pivots, mas->max); + if (unlikely(ma_dead_node(node))) + return NULL; + mas->index = mas_safe_min(mas, pivots, mas->offset); - if (ma_dead_node(node)) + if (unlikely(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; @@ -4711,15 +4784,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; - } /* @@ -4743,6 +4812,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; @@ -4816,6 +4890,11 @@ retry: slots = ma_slots(mn, mt); pivots = ma_pivots(mn, mt); + if (unlikely(ma_dead_node(mn))) { + mas_rewalk(mas, index); + goto retry; + } + if (offset == mt_pivots[mt]) pivot = mas->max; else @@ -4849,6 +4928,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); @@ -4881,7 +4965,8 @@ not_found: * Return: True if found in a leaf, false otherwise. * */ -static bool mas_rev_awalk(struct ma_state *mas, unsigned long size) +static bool mas_rev_awalk(struct ma_state *mas, unsigned long size, + unsigned long *gap_min, unsigned long *gap_max) { enum maple_type type = mte_node_type(mas->node); struct maple_node *node = mas_mn(mas); @@ -4946,8 +5031,8 @@ static bool mas_rev_awalk(struct ma_state *mas, unsigned long size) if (unlikely(ma_is_leaf(type))) { mas->offset = offset; - mas->min = min; - mas->max = min + gap - 1; + *gap_min = min; + *gap_max = min + gap - 1; return true; } @@ -4971,10 +5056,10 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) { enum maple_type type = mte_node_type(mas->node); unsigned long pivot, min, gap = 0; - unsigned char offset; - unsigned long *gaps; - unsigned long *pivots = ma_pivots(mas_mn(mas), type); - void __rcu **slots = ma_slots(mas_mn(mas), type); + unsigned char offset, data_end; + unsigned long *gaps, *pivots; + void __rcu **slots; + struct maple_node *node; bool found = false; if (ma_is_dense(type)) { @@ -4982,13 +5067,15 @@ static inline bool mas_anode_descend(struct ma_state *mas, unsigned long size) return true; } - gaps = ma_gaps(mte_to_node(mas->node), type); + node = mas_mn(mas); + pivots = ma_pivots(node, type); + slots = ma_slots(node, type); + gaps = ma_gaps(node, type); offset = mas->offset; min = mas_safe_min(mas, pivots, offset); - for (; offset < mt_slots[type]; offset++) { - pivot = mas_safe_pivot(mas, pivots, offset, type); - if (offset && !pivot) - break; + data_end = ma_data_end(node, type, pivots, mas->max); + for (; offset <= data_end; offset++) { + pivot = mas_logical_pivot(mas, pivots, offset, type); /* Not within lower bounds */ if (mas->index > pivot) @@ -5093,35 +5180,21 @@ static inline bool mas_rewind_node(struct ma_state *mas) */ static inline bool mas_skip_node(struct ma_state *mas) { - unsigned char slot, slot_count; - unsigned long *pivots; - enum maple_type mt; + if (mas_is_err(mas)) + return false; - mt = mte_node_type(mas->node); - slot_count = mt_slots[mt] - 1; do { if (mte_is_root(mas->node)) { - slot = mas->offset; - if (slot > slot_count) { + if (mas->offset >= mas_data_end(mas)) { mas_set_err(mas, -EBUSY); return false; } } else { mas_ascend(mas); - slot = mas->offset; - mt = mte_node_type(mas->node); - slot_count = mt_slots[mt] - 1; } - } while (slot > slot_count); - - mas->offset = ++slot; - pivots = ma_pivots(mas_mn(mas), mt); - if (slot > 0) - mas->min = pivots[slot - 1] + 1; - - if (slot <= slot_count) - mas->max = pivots[slot]; + } while (mas->offset >= mas_data_end(mas)); + mas->offset++; return true; } @@ -5237,6 +5310,9 @@ int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long *pivots; enum maple_type mt; + if (min >= max) + return -EINVAL; + if (mas_is_start(mas)) mas_start(mas); else if (mas->offset >= 2) @@ -5291,6 +5367,9 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, { struct maple_enode *last = mas->node; + if (min >= max) + return -EINVAL; + if (mas_is_start(mas)) { mas_start(mas); mas->offset = mas_data_end(mas); @@ -5310,7 +5389,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, mas->index = min; mas->last = max; - while (!mas_rev_awalk(mas, size)) { + while (!mas_rev_awalk(mas, size, &min, &max)) { if (last == mas->node) { if (!mas_rewind_node(mas)) return -EBUSY; @@ -5325,17 +5404,9 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, if (unlikely(mas->offset == MAPLE_NODE_SLOTS)) return -EBUSY; - /* - * mas_rev_awalk() has set mas->min and mas->max to the gap values. If - * the maximum is outside the window we are searching, then use the last - * location in the search. - * mas->max and mas->min is the range of the gap. - * mas->index and mas->last are currently set to the search range. - */ - /* Trim the upper limit to the max. */ - if (mas->max <= mas->last) - mas->last = mas->max; + if (max <= mas->last) + mas->last = max; mas->index = mas->last - size + 1; return 0; @@ -5408,24 +5479,26 @@ no_gap: } /* - * mas_dead_leaves() - Mark all leaves of a node as dead. + * mte_dead_leaves() - Mark all leaves of a node as dead. * @mas: The maple state * @slots: Pointer to the slot array + * @type: The maple node type * * Must hold the write lock. * * Return: The number of leaves marked as dead. */ static inline -unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots) +unsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt, + void __rcu **slots) { struct maple_node *node; enum maple_type type; void *entry; int offset; - for (offset = 0; offset < mt_slot_count(mas->node); offset++) { - entry = mas_slot_locked(mas, slots, offset); + for (offset = 0; offset < mt_slot_count(enode); offset++) { + entry = mt_slot(mt, slots, offset); type = mte_node_type(entry); node = mte_to_node(entry); /* Use both node and type to catch LE & BE metadata */ @@ -5433,7 +5506,6 @@ unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots) break; mte_set_node_dead(entry); - smp_wmb(); /* Needed for RCU */ node->type = type; rcu_assign_pointer(slots[offset], node); } @@ -5441,157 +5513,166 @@ unsigned char mas_dead_leaves(struct ma_state *mas, void __rcu **slots) return offset; } -static void __rcu **mas_dead_walk(struct ma_state *mas, unsigned char offset) +/** + * mte_dead_walk() - Walk down a dead tree to just before the leaves + * @enode: The maple encoded node + * @offset: The starting offset + * + * Note: This can only be used from the RCU callback context. + */ +static void __rcu **mte_dead_walk(struct maple_enode **enode, unsigned char offset) { struct maple_node *node, *next; void __rcu **slots = NULL; - next = mas_mn(mas); + next = mte_to_node(*enode); do { - mas->node = ma_enode_ptr(next); - node = mas_mn(mas); + *enode = ma_enode_ptr(next); + node = mte_to_node(*enode); slots = ma_slots(node, node->type); - next = mas_slot_locked(mas, slots, offset); + next = rcu_dereference_protected(slots[offset], + lock_is_held(&rcu_callback_map)); offset = 0; } while (!ma_is_leaf(next->type)); return slots; } +/** + * mt_free_walk() - Walk & free a tree in the RCU callback context + * @head: The RCU head that's within the node. + * + * Note: This can only be used from the RCU callback context. + */ static void mt_free_walk(struct rcu_head *head) { void __rcu **slots; struct maple_node *node, *start; - struct maple_tree mt; + struct maple_enode *enode; unsigned char offset; enum maple_type type; - MA_STATE(mas, &mt, 0, 0); node = container_of(head, struct maple_node, rcu); if (ma_is_leaf(node->type)) goto free_leaf; - mt_init_flags(&mt, node->ma_flags); - mas_lock(&mas); start = node; - mas.node = mt_mk_node(node, node->type); - slots = mas_dead_walk(&mas, 0); - node = mas_mn(&mas); + enode = mt_mk_node(node, node->type); + slots = mte_dead_walk(&enode, 0); + node = mte_to_node(enode); do { mt_free_bulk(node->slot_len, slots); offset = node->parent_slot + 1; - mas.node = node->piv_parent; - if (mas_mn(&mas) == node) - goto start_slots_free; - - type = mte_node_type(mas.node); - slots = ma_slots(mte_to_node(mas.node), type); - if ((offset < mt_slots[type]) && (slots[offset])) - slots = mas_dead_walk(&mas, offset); - - node = mas_mn(&mas); + enode = node->piv_parent; + if (mte_to_node(enode) == node) + goto free_leaf; + + type = mte_node_type(enode); + slots = ma_slots(mte_to_node(enode), type); + if ((offset < mt_slots[type]) && + rcu_dereference_protected(slots[offset], + lock_is_held(&rcu_callback_map))) + slots = mte_dead_walk(&enode, offset); + node = mte_to_node(enode); } while ((node != start) || (node->slot_len < offset)); slots = ma_slots(node, node->type); mt_free_bulk(node->slot_len, slots); -start_slots_free: - mas_unlock(&mas); free_leaf: mt_free_rcu(&node->rcu); } -static inline void __rcu **mas_destroy_descend(struct ma_state *mas, - struct maple_enode *prev, unsigned char offset) +static inline void __rcu **mte_destroy_descend(struct maple_enode **enode, + struct maple_tree *mt, struct maple_enode *prev, unsigned char offset) { struct maple_node *node; - struct maple_enode *next = mas->node; + struct maple_enode *next = *enode; void __rcu **slots = NULL; + enum maple_type type; + unsigned char next_offset = 0; do { - mas->node = next; - node = mas_mn(mas); - slots = ma_slots(node, mte_node_type(mas->node)); - next = mas_slot_locked(mas, slots, 0); + *enode = next; + node = mte_to_node(*enode); + type = mte_node_type(*enode); + slots = ma_slots(node, type); + next = mt_slot_locked(mt, slots, next_offset); if ((mte_dead_node(next))) - next = mas_slot_locked(mas, slots, 1); + next = mt_slot_locked(mt, slots, ++next_offset); - mte_set_node_dead(mas->node); - node->type = mte_node_type(mas->node); + mte_set_node_dead(*enode); + node->type = type; node->piv_parent = prev; node->parent_slot = offset; - offset = 0; - prev = mas->node; + offset = next_offset; + next_offset = 0; + prev = *enode; } while (!mte_is_leaf(next)); return slots; } -static void mt_destroy_walk(struct maple_enode *enode, unsigned char ma_flags, +static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, bool free) { void __rcu **slots; struct maple_node *node = mte_to_node(enode); struct maple_enode *start; - struct maple_tree mt; - - MA_STATE(mas, &mt, 0, 0); - if (mte_is_leaf(enode)) + if (mte_is_leaf(enode)) { + node->type = mte_node_type(enode); goto free_leaf; + } - mt_init_flags(&mt, ma_flags); - mas_lock(&mas); - - mas.node = start = enode; - slots = mas_destroy_descend(&mas, start, 0); - node = mas_mn(&mas); + start = enode; + slots = mte_destroy_descend(&enode, mt, start, 0); + node = mte_to_node(enode); // Updated in the above call. do { enum maple_type type; unsigned char offset; struct maple_enode *parent, *tmp; - node->slot_len = mas_dead_leaves(&mas, slots); + node->slot_len = mte_dead_leaves(enode, mt, slots); if (free) mt_free_bulk(node->slot_len, slots); offset = node->parent_slot + 1; - mas.node = node->piv_parent; - if (mas_mn(&mas) == node) - goto start_slots_free; + enode = node->piv_parent; + if (mte_to_node(enode) == node) + goto free_leaf; - type = mte_node_type(mas.node); - slots = ma_slots(mte_to_node(mas.node), type); + type = mte_node_type(enode); + slots = ma_slots(mte_to_node(enode), type); if (offset >= mt_slots[type]) goto next; - tmp = mas_slot_locked(&mas, slots, offset); + tmp = mt_slot_locked(mt, slots, offset); if (mte_node_type(tmp) && mte_to_node(tmp)) { - parent = mas.node; - mas.node = tmp; - slots = mas_destroy_descend(&mas, parent, offset); + parent = enode; + enode = tmp; + slots = mte_destroy_descend(&enode, mt, parent, offset); } next: - node = mas_mn(&mas); - } while (start != mas.node); + node = mte_to_node(enode); + } while (start != enode); - node = mas_mn(&mas); - node->slot_len = mas_dead_leaves(&mas, slots); + node = mte_to_node(enode); + node->slot_len = mte_dead_leaves(enode, mt, slots); if (free) mt_free_bulk(node->slot_len, slots); -start_slots_free: - mas_unlock(&mas); - free_leaf: if (free) mt_free_rcu(&node->rcu); + else + mt_clear_meta(mt, node, node->type); } /* * 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. */ @@ -5601,15 +5682,18 @@ static inline void mte_destroy_walk(struct maple_enode *enode, struct maple_node *node = mte_to_node(enode); if (mt_in_rcu(mt)) { - mt_destroy_walk(enode, mt->ma_flags, false); + mt_destroy_walk(enode, mt, false); call_rcu(&node->rcu, mt_free_walk); } else { - mt_destroy_walk(enode, mt->ma_flags, true); + mt_destroy_walk(enode, mt, true); } } 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 +5704,6 @@ static void mas_wr_store_setup(struct ma_wr_state *wr_mas) mas_reset(wr_mas->mas); } } - } /* Interface */ @@ -5712,12 +5795,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 +5827,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 +5850,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 +6001,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 +6092,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; @@ -6613,11 +6706,11 @@ static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn, while (likely(!ma_is_leaf(mt))) { MT_BUG_ON(mas->tree, mte_dead_node(mas->node)); slots = ma_slots(mn, mt); - pivots = ma_pivots(mn, mt); - max = pivots[0]; entry = mas_slot(mas, slots, 0); + pivots = ma_pivots(mn, mt); if (unlikely(ma_dead_node(mn))) return NULL; + max = pivots[0]; mas->node = entry; mn = mas_mn(mas); mt = mte_node_type(mas->node); @@ -6637,13 +6730,13 @@ static inline void *mas_first_entry(struct ma_state *mas, struct maple_node *mn, if (likely(entry)) return entry; - pivots = ma_pivots(mn, mt); - mas->index = pivots[0] + 1; mas->offset = 1; entry = mas_slot(mas, slots, 1); + pivots = ma_pivots(mn, mt); if (unlikely(ma_dead_node(mn))) return NULL; + mas->index = pivots[0] + 1; if (mas->index > limit) goto none; @@ -6734,7 +6827,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 +6934,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/parser.c b/lib/parser.c index 2b5e2b480253..f4eafb9d74e6 100644 --- a/lib/parser.c +++ b/lib/parser.c @@ -133,7 +133,7 @@ EXPORT_SYMBOL(match_token); * as a number in that base. * * Return: On success, sets @result to the integer represented by the - * string and returns 0. Returns -ENOMEM, -EINVAL, or -ERANGE on failure. + * string and returns 0. Returns -EINVAL or -ERANGE on failure. */ static int match_number(substring_t *s, int *result, int base) { @@ -165,7 +165,7 @@ static int match_number(substring_t *s, int *result, int base) * as a number in that base. * * Return: On success, sets @result to the integer represented by the - * string and returns 0. Returns -ENOMEM, -EINVAL, or -ERANGE on failure. + * string and returns 0. Returns -EINVAL or -ERANGE on failure. */ static int match_u64int(substring_t *s, u64 *result, int base) { @@ -189,7 +189,7 @@ static int match_u64int(substring_t *s, u64 *result, int base) * Description: Attempts to parse the &substring_t @s as a decimal integer. * * Return: On success, sets @result to the integer represented by the string - * and returns 0. Returns -ENOMEM, -EINVAL, or -ERANGE on failure. + * and returns 0. Returns -EINVAL or -ERANGE on failure. */ int match_int(substring_t *s, int *result) { @@ -205,7 +205,7 @@ EXPORT_SYMBOL(match_int); * Description: Attempts to parse the &substring_t @s as a decimal integer. * * Return: On success, sets @result to the integer represented by the string - * and returns 0. Returns -ENOMEM, -EINVAL, or -ERANGE on failure. + * and returns 0. Returns -EINVAL or -ERANGE on failure. */ int match_uint(substring_t *s, unsigned int *result) { @@ -228,7 +228,7 @@ EXPORT_SYMBOL(match_uint); * integer. * * Return: On success, sets @result to the integer represented by the string - * and returns 0. Returns -ENOMEM, -EINVAL, or -ERANGE on failure. + * and returns 0. Returns -EINVAL or -ERANGE on failure. */ int match_u64(substring_t *s, u64 *result) { @@ -244,7 +244,7 @@ EXPORT_SYMBOL(match_u64); * Description: Attempts to parse the &substring_t @s as an octal integer. * * Return: On success, sets @result to the integer represented by the string - * and returns 0. Returns -ENOMEM, -EINVAL, or -ERANGE on failure. + * and returns 0. Returns -EINVAL or -ERANGE on failure. */ int match_octal(substring_t *s, int *result) { @@ -260,7 +260,7 @@ EXPORT_SYMBOL(match_octal); * Description: Attempts to parse the &substring_t @s as a hexadecimal integer. * * Return: On success, sets @result to the integer represented by the string - * and returns 0. Returns -ENOMEM, -EINVAL, or -ERANGE on failure. + * and returns 0. Returns -EINVAL or -ERANGE on failure. */ int match_hex(substring_t *s, int *result) { diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c index 42f729c8e56c..5004463c4f9f 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); @@ -117,8 +122,19 @@ void percpu_counter_sync(struct percpu_counter *fbc) } EXPORT_SYMBOL(percpu_counter_sync); -static s64 __percpu_counter_sum_mask(struct percpu_counter *fbc, - const struct cpumask *cpu_mask) +/* + * Add up all the per-cpu counts, return the result. This is a more accurate + * but much slower version of percpu_counter_read_positive(). + * + * We use the cpu mask of (cpu_online_mask | cpu_dying_mask) to capture sums + * from CPUs that are in the process of being taken offline. Dying cpus have + * been removed from the online mask, but may not have had the hotplug dead + * notifier called to fold the percpu count back into the global counter sum. + * By including dying CPUs in the iteration mask, we avoid this race condition + * so __percpu_counter_sum() just does the right thing when CPUs are being taken + * offline. + */ +s64 __percpu_counter_sum(struct percpu_counter *fbc) { s64 ret; int cpu; @@ -126,35 +142,15 @@ static s64 __percpu_counter_sum_mask(struct percpu_counter *fbc, raw_spin_lock_irqsave(&fbc->lock, flags); ret = fbc->count; - for_each_cpu(cpu, cpu_mask) { + for_each_cpu_or(cpu, cpu_online_mask, cpu_dying_mask) { s32 *pcount = per_cpu_ptr(fbc->counters, cpu); ret += *pcount; } raw_spin_unlock_irqrestore(&fbc->lock, flags); return ret; } - -/* - * Add up all the per-cpu counts, return the result. This is a more accurate - * but much slower version of percpu_counter_read_positive() - */ -s64 __percpu_counter_sum(struct percpu_counter *fbc) -{ - return __percpu_counter_sum_mask(fbc, cpu_online_mask); -} EXPORT_SYMBOL(__percpu_counter_sum); -/* - * This is slower version of percpu_counter_sum as it traverses all possible - * cpus. Use this only in the cases where accurate data is needed in the - * presense of CPUs getting offlined. - */ -s64 percpu_counter_sum_all(struct percpu_counter *fbc) -{ - return __percpu_counter_sum_mask(fbc, cpu_possible_mask); -} -EXPORT_SYMBOL(percpu_counter_sum_all); - int __percpu_counter_init(struct percpu_counter *fbc, s64 amount, gfp_t gfp, struct lock_class_key *key) { 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/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_maple_tree.c b/lib/test_maple_tree.c index ec847bf4dcb4..f1db333270e9 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) { @@ -2602,6 +2670,49 @@ static noinline void check_empty_area_window(struct maple_tree *mt) rcu_read_unlock(); } +static noinline void check_empty_area_fill(struct maple_tree *mt) +{ + const unsigned long max = 0x25D78000; + unsigned long size; + int loop, shift; + MA_STATE(mas, mt, 0, 0); + + mt_set_non_kernel(99999); + for (shift = 12; shift <= 16; shift++) { + loop = 5000; + size = 1 << shift; + while (loop--) { + mas_set(&mas, 0); + mas_lock(&mas); + MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != 0); + MT_BUG_ON(mt, mas.last != mas.index + size - 1); + mas_store_gfp(&mas, (void *)size, GFP_KERNEL); + mas_unlock(&mas); + mas_reset(&mas); + } + } + + /* No space left. */ + size = 0x1000; + rcu_read_lock(); + MT_BUG_ON(mt, mas_empty_area(&mas, 0, max, size) != -EBUSY); + rcu_read_unlock(); + + /* Fill a depth 3 node to the maximum */ + for (unsigned long i = 629440511; i <= 629440800; i += 6) + mtree_store_range(mt, i, i + 5, (void *)i, GFP_KERNEL); + /* Make space in the second-last depth 4 node */ + mtree_erase(mt, 631668735); + /* Make space in the last depth 4 node */ + mtree_erase(mt, 629506047); + mas_reset(&mas); + /* Search from just after the gap in the second-last depth 4 */ + rcu_read_lock(); + MT_BUG_ON(mt, mas_empty_area(&mas, 629506048, 690000000, 0x5000) != 0); + rcu_read_unlock(); + mt_set_non_kernel(0); +} + static DEFINE_MTREE(tree); static int maple_tree_seed(void) { @@ -2660,6 +2771,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); @@ -2854,6 +2969,11 @@ static int maple_tree_seed(void) check_empty_area_window(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_empty_area_fill(&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..cd2bdba6d3ed 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; @@ -328,7 +334,7 @@ kvfree_rcu_1_arg_vmalloc_test(void) return -1; p->array[0] = 'a'; - kvfree_rcu(p); + kvfree_rcu_mightsleep(p); } return 0; diff --git a/lib/vdso/Makefile b/lib/vdso/Makefile index e814061d6aa0..9f031eafc465 100644 --- a/lib/vdso/Makefile +++ b/lib/vdso/Makefile @@ -5,18 +5,13 @@ GENERIC_VDSO_DIR := $(dir $(GENERIC_VDSO_MK_PATH)) c-gettimeofday-$(CONFIG_GENERIC_GETTIMEOFDAY) := $(addprefix $(GENERIC_VDSO_DIR), gettimeofday.c) -# This cmd checks that the vdso library does not contain absolute relocation +# This cmd checks that the vdso library does not contain dynamic relocations. # It has to be called after the linking of the vdso library and requires it # as a parameter. # -# $(ARCH_REL_TYPE_ABS) is defined in the arch specific makefile and corresponds -# to the absolute relocation types printed by "objdump -R" and accepted by the -# dynamic linker. -ifndef ARCH_REL_TYPE_ABS -$(error ARCH_REL_TYPE_ABS is not set) -endif - +# As a workaround for some GNU ld ports which produce unneeded R_*_NONE +# dynamic relocations, ignore R_*_NONE. quiet_cmd_vdso_check = VDSOCHK $@ - cmd_vdso_check = if $(OBJDUMP) -R $@ | grep -E -h "$(ARCH_REL_TYPE_ABS)"; \ + cmd_vdso_check = if $(READELF) -rW $@ | grep -v _NONE | grep -q " R_\w*_"; \ then (echo >&2 "$@: dynamic relocations are not supported"; \ rm -f $@; /bin/false); fi 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_deflate/defutil.h b/lib/zlib_deflate/defutil.h index 385333b22ec6..4ea40f5a279f 100644 --- a/lib/zlib_deflate/defutil.h +++ b/lib/zlib_deflate/defutil.h @@ -420,9 +420,11 @@ static inline void flush_pending( z_streamp strm ) { + unsigned len; deflate_state *s = (deflate_state *) strm->state; - unsigned len = s->pending; + bi_flush(s); + len = s->pending; if (len > strm->avail_out) len = strm->avail_out; if (len == 0) return; 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) diff --git a/lib/zstd/common/zstd_deps.h b/lib/zstd/common/zstd_deps.h index 7a5bf44839c9..f06df065dec0 100644 --- a/lib/zstd/common/zstd_deps.h +++ b/lib/zstd/common/zstd_deps.h @@ -84,7 +84,7 @@ static uint64_t ZSTD_div64(uint64_t dividend, uint32_t divisor) { #include <linux/kernel.h> -#define assert(x) WARN_ON((x)) +#define assert(x) WARN_ON(!(x)) #endif /* ZSTD_DEPS_ASSERT */ #endif /* ZSTD_DEPS_NEED_ASSERT */ diff --git a/lib/zstd/decompress/huf_decompress.c b/lib/zstd/decompress/huf_decompress.c index 89b269a641c7..60958afebc41 100644 --- a/lib/zstd/decompress/huf_decompress.c +++ b/lib/zstd/decompress/huf_decompress.c @@ -985,7 +985,7 @@ static void HUF_fillDTableX2Level2(HUF_DEltX2* DTable, U32 targetLog, const U32 static void HUF_fillDTableX2(HUF_DEltX2* DTable, const U32 targetLog, const sortedSymbol_t* sortedList, - const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight, + const U32* rankStart, rankValCol_t *rankValOrigin, const U32 maxWeight, const U32 nbBitsBaseline) { U32* const rankVal = rankValOrigin[0]; diff --git a/lib/zstd/decompress/zstd_decompress.c b/lib/zstd/decompress/zstd_decompress.c index b9b935a9f5c0..6b3177c94711 100644 --- a/lib/zstd/decompress/zstd_decompress.c +++ b/lib/zstd/decompress/zstd_decompress.c @@ -798,7 +798,7 @@ static size_t ZSTD_copyRawBlock(void* dst, size_t dstCapacity, if (srcSize == 0) return 0; RETURN_ERROR(dstBuffer_null, ""); } - ZSTD_memcpy(dst, src, srcSize); + ZSTD_memmove(dst, src, srcSize); return srcSize; } @@ -858,6 +858,7 @@ static size_t ZSTD_decompressFrame(ZSTD_DCtx* dctx, /* Loop on each block */ while (1) { + BYTE* oBlockEnd = oend; size_t decodedSize; blockProperties_t blockProperties; size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSrcSize, &blockProperties); @@ -867,16 +868,34 @@ static size_t ZSTD_decompressFrame(ZSTD_DCtx* dctx, remainingSrcSize -= ZSTD_blockHeaderSize; RETURN_ERROR_IF(cBlockSize > remainingSrcSize, srcSize_wrong, ""); + if (ip >= op && ip < oBlockEnd) { + /* We are decompressing in-place. Limit the output pointer so that we + * don't overwrite the block that we are currently reading. This will + * fail decompression if the input & output pointers aren't spaced + * far enough apart. + * + * This is important to set, even when the pointers are far enough + * apart, because ZSTD_decompressBlock_internal() can decide to store + * literals in the output buffer, after the block it is decompressing. + * Since we don't want anything to overwrite our input, we have to tell + * ZSTD_decompressBlock_internal to never write past ip. + * + * See ZSTD_allocateLiteralsBuffer() for reference. + */ + oBlockEnd = op + (ip - op); + } + switch(blockProperties.blockType) { case bt_compressed: - decodedSize = ZSTD_decompressBlock_internal(dctx, op, (size_t)(oend-op), ip, cBlockSize, /* frame */ 1, not_streaming); + decodedSize = ZSTD_decompressBlock_internal(dctx, op, (size_t)(oBlockEnd-op), ip, cBlockSize, /* frame */ 1, not_streaming); break; case bt_raw : + /* Use oend instead of oBlockEnd because this function is safe to overlap. It uses memmove. */ decodedSize = ZSTD_copyRawBlock(op, (size_t)(oend-op), ip, cBlockSize); break; case bt_rle : - decodedSize = ZSTD_setRleBlock(op, (size_t)(oend-op), *ip, blockProperties.origSize); + decodedSize = ZSTD_setRleBlock(op, (size_t)(oBlockEnd-op), *ip, blockProperties.origSize); break; case bt_reserved : default: |