From 6e24628d78e4785385876125cba62315ca3b04b9 Mon Sep 17 00:00:00 2001 From: Ian Rogers Date: Thu, 13 Feb 2020 23:51:29 -0800 Subject: lib: Introduce generic min-heap Supports push, pop and converting an array into a heap. If the sense of the compare function is inverted then it can provide a max-heap. Based-on-work-by: Peter Zijlstra (Intel) Signed-off-by: Ian Rogers Signed-off-by: Peter Zijlstra (Intel) Signed-off-by: Ingo Molnar Link: https://lkml.kernel.org/r/20200214075133.181299-3-irogers@google.com --- lib/Makefile | 1 + 1 file changed, 1 insertion(+) (limited to 'lib/Makefile') diff --git a/lib/Makefile b/lib/Makefile index 611872c06926..09a8acb0cf92 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -67,6 +67,7 @@ CFLAGS_test_ubsan.o += $(call cc-disable-warning, vla) UBSAN_SANITIZE_test_ubsan.o := y obj-$(CONFIG_TEST_KSTRTOX) += test-kstrtox.o obj-$(CONFIG_TEST_LIST_SORT) += test_list_sort.o +obj-$(CONFIG_TEST_MIN_HEAP) += test_min_heap.o obj-$(CONFIG_TEST_LKM) += test_module.o obj-$(CONFIG_TEST_VMALLOC) += test_vmalloc.o obj-$(CONFIG_TEST_OVERFLOW) += test_overflow.o -- cgit From 30428ef5d1e8caf78639cc70a802f1cb7b1cec04 Mon Sep 17 00:00:00 2001 From: Konstantin Khlebnikov Date: Mon, 6 Apr 2020 20:09:47 -0700 Subject: lib/test_lockup: test module to generate lockups CONFIG_TEST_LOCKUP=m adds module "test_lockup" that helps to make sure that watchdogs and lockup detectors are working properly. Depending on module parameters test_lockup could emulate soft or hard lockup, "hung task", hold arbitrary lock, allocate bunch of pages. Also it could generate series of lockups with cooling-down periods, in this way it could be used as "ping" for locks or page allocator. Loop checks signals between iteration thus could be stopped by ^C. # modinfo test_lockup ... parm: time_secs:lockup time in seconds, default 0 (uint) parm: time_nsecs:nanoseconds part of lockup time, default 0 (uint) parm: cooldown_secs:cooldown time between iterations in seconds, default 0 (uint) parm: cooldown_nsecs:nanoseconds part of cooldown, default 0 (uint) parm: iterations:lockup iterations, default 1 (uint) parm: all_cpus:trigger lockup at all cpus at once (bool) parm: state:wait in 'R' running (default), 'D' uninterruptible, 'K' killable, 'S' interruptible state (charp) parm: use_hrtimer:use high-resolution timer for sleeping (bool) parm: iowait:account sleep time as iowait (bool) parm: lock_read:lock read-write locks for read (bool) parm: lock_single:acquire locks only at one cpu (bool) parm: reacquire_locks:release and reacquire locks/irq/preempt between iterations (bool) parm: touch_softlockup:touch soft-lockup watchdog between iterations (bool) parm: touch_hardlockup:touch hard-lockup watchdog between iterations (bool) parm: call_cond_resched:call cond_resched() between iterations (bool) parm: measure_lock_wait:measure lock wait time (bool) parm: lock_wait_threshold:print lock wait time longer than this in nanoseconds, default off (ulong) parm: disable_irq:disable interrupts: generate hard-lockups (bool) parm: disable_softirq:disable bottom-half irq handlers (bool) parm: disable_preempt:disable preemption: generate soft-lockups (bool) parm: lock_rcu:grab rcu_read_lock: generate rcu stalls (bool) parm: lock_mmap_sem:lock mm->mmap_sem: block procfs interfaces (bool) parm: lock_rwsem_ptr:lock rw_semaphore at address (ulong) parm: lock_mutex_ptr:lock mutex at address (ulong) parm: lock_spinlock_ptr:lock spinlock at address (ulong) parm: lock_rwlock_ptr:lock rwlock at address (ulong) parm: alloc_pages_nr:allocate and free pages under locks (uint) parm: alloc_pages_order:page order to allocate (uint) parm: alloc_pages_gfp:allocate pages with this gfp_mask, default GFP_KERNEL (uint) parm: alloc_pages_atomic:allocate pages with GFP_ATOMIC (bool) parm: reallocate_pages:free and allocate pages between iterations (bool) Parameters for locking by address are unsafe and taints kernel. With CONFIG_DEBUG_SPINLOCK=y they at least check magics for embedded spinlocks. Examples: task hang in D-state: modprobe test_lockup time_secs=1 iterations=60 state=D task hang in io-wait D-state: modprobe test_lockup time_secs=1 iterations=60 state=D iowait softlockup: modprobe test_lockup time_secs=1 iterations=60 state=R hardlockup: modprobe test_lockup time_secs=1 iterations=60 state=R disable_irq system-wide hardlockup: modprobe test_lockup time_secs=1 iterations=60 state=R \ disable_irq all_cpus rcu stall: modprobe test_lockup time_secs=1 iterations=60 state=R \ lock_rcu touch_softlockup lock mmap_sem / block procfs interfaces: modprobe test_lockup time_secs=1 iterations=60 state=S lock_mmap_sem lock tasklist_lock for read / block forks: TASKLIST_LOCK=$(awk '$3 == "tasklist_lock" {print "0x"$1}' /proc/kallsyms) modprobe test_lockup time_secs=1 iterations=60 state=R \ disable_irq lock_read lock_rwlock_ptr=$TASKLIST_LOCK lock namespace_sem / block vfs mount operations: NAMESPACE_SEM=$(awk '$3 == "namespace_sem" {print "0x"$1}' /proc/kallsyms) modprobe test_lockup time_secs=1 iterations=60 state=S \ lock_rwsem_ptr=$NAMESPACE_SEM lock cgroup mutex / block cgroup operations: CGROUP_MUTEX=$(awk '$3 == "cgroup_mutex" {print "0x"$1}' /proc/kallsyms) modprobe test_lockup time_secs=1 iterations=60 state=S \ lock_mutex_ptr=$CGROUP_MUTEX ping cgroup_mutex every second and measure maximum lock wait time: modprobe test_lockup cooldown_secs=1 iterations=60 state=S \ lock_mutex_ptr=$CGROUP_MUTEX reacquire_locks measure_lock_wait [linux@roeck-us.net: rename disable_irq to fix build error] Link: http://lkml.kernel.org/r/20200317133614.23152-1-linux@roeck-us.net Signed-off-by: Konstantin Khlebnikov Signed-off-by: Guenter Roeck Signed-off-by: Andrew Morton Cc: Sasha Levin Cc: Petr Mladek Cc: Kees Cook Cc: Peter Zijlstra Cc: Greg Kroah-Hartman Cc: Steven Rostedt Cc: Sergey Senozhatsky Cc: Dmitry Monakhov Cc: Guenter Roeck Link: http://lkml.kernel.org/r/158132859146.2797.525923171323227836.stgit@buzz Signed-off-by: Linus Torvalds --- lib/Makefile | 1 + 1 file changed, 1 insertion(+) (limited to 'lib/Makefile') diff --git a/lib/Makefile b/lib/Makefile index 09a8acb0cf92..0fd125c4ad07 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -90,6 +90,7 @@ obj-$(CONFIG_TEST_OBJAGG) += test_objagg.o obj-$(CONFIG_TEST_STACKINIT) += test_stackinit.o obj-$(CONFIG_TEST_BLACKHOLE_DEV) += test_blackhole_dev.o obj-$(CONFIG_TEST_MEMINIT) += test_meminit.o +obj-$(CONFIG_TEST_LOCKUP) += test_lockup.o obj-$(CONFIG_TEST_LIVEPATCH) += livepatch/ -- cgit From 9cf016e6b49b53d6c15d4137c034178148149ef4 Mon Sep 17 00:00:00 2001 From: Kees Cook Date: Mon, 6 Apr 2020 20:10:12 -0700 Subject: lib: test_stackinit.c: XFAIL switch variable init tests The tests for initializing a variable defined between a switch statement's test and its first "case" statement are currently not initialized in Clang[1] nor the proposed auto-initialization feature in GCC. We should retain the test (so that we can evaluate compiler fixes), but mark it as an "expected fail". The rest of the kernel source will be adjusted to avoid this corner case. Also disable -Wswitch-unreachable for the test so that the intentionally broken code won't trigger warnings for GCC (nor future Clang) when initialization happens this unhandled place. [1] https://bugs.llvm.org/show_bug.cgi?id=44916 Suggested-by: Alexander Potapenko Signed-off-by: Kees Cook Signed-off-by: Andrew Morton Cc: Jann Horn Cc: Ard Biesheuvel Link: http://lkml.kernel.org/r/202002191358.2897A07C6@keescook Signed-off-by: Linus Torvalds --- lib/Makefile | 1 + 1 file changed, 1 insertion(+) (limited to 'lib/Makefile') diff --git a/lib/Makefile b/lib/Makefile index 0fd125c4ad07..93d05ff4f501 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -87,6 +87,7 @@ obj-$(CONFIG_TEST_KMOD) += test_kmod.o obj-$(CONFIG_TEST_DEBUG_VIRTUAL) += test_debug_virtual.o obj-$(CONFIG_TEST_MEMCAT_P) += test_memcat_p.o obj-$(CONFIG_TEST_OBJAGG) += test_objagg.o +CFLAGS_test_stackinit.o += $(call cc-disable-warning, switch-unreachable) obj-$(CONFIG_TEST_STACKINIT) += test_stackinit.o obj-$(CONFIG_TEST_BLACKHOLE_DEV) += test_blackhole_dev.o obj-$(CONFIG_TEST_MEMINIT) += test_meminit.o -- cgit From 7b65942fb2f0ac939be9c659bb889e78b399f84e Mon Sep 17 00:00:00 2001 From: Alexander Potapenko Date: Mon, 6 Apr 2020 20:10:19 -0700 Subject: lib/stackdepot.c: build with -fno-builtin Clang may replace stackdepot_memcmp() with a call to instrumented bcmp(), which is exactly what we wanted to avoid creating stackdepot_memcmp(). Building the file with -fno-builtin prevents such optimizations. This patch has been previously mailed as part of KMSAN RFC patch series. Signed-off-by: Alexander Potapenko Signed-off-by: Andrew Morton Cc: Vegard Nossum Cc: Dmitry Vyukov Cc: Marco Elver Cc: Andrey Konovalov Cc: Sergey Senozhatsky Cc: Arnd Bergmann Cc: Andrey Ryabinin Link: http://lkml.kernel.org/r/20200220141916.55455-2-glider@google.com Signed-off-by: Linus Torvalds --- lib/Makefile | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'lib/Makefile') diff --git a/lib/Makefile b/lib/Makefile index 93d05ff4f501..3fc06399295d 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -223,6 +223,10 @@ obj-$(CONFIG_MEMREGION) += memregion.o obj-$(CONFIG_STMP_DEVICE) += stmp_device.o obj-$(CONFIG_IRQ_POLL) += irq_poll.o +# stackdepot.c should not be instrumented or call instrumented functions. +# Prevent the compiler from calling builtins like memcmp() or bcmp() from this +# file. +CFLAGS_stackdepot.o += -fno-builtin obj-$(CONFIG_STACKDEPOT) += stackdepot.o KASAN_SANITIZE_stackdepot.o := n KCOV_INSTRUMENT_stackdepot.o := n -- cgit From 0887a7ebc97770c7870abf3075a2e8cd502a7f52 Mon Sep 17 00:00:00 2001 From: Kees Cook Date: Mon, 6 Apr 2020 20:12:27 -0700 Subject: ubsan: add trap instrumentation option Patch series "ubsan: Split out bounds checker", v5. This splits out the bounds checker so it can be individually used. This is enabled in Android and hopefully for syzbot. Includes LKDTM tests for behavioral corner-cases (beyond just the bounds checker), and adjusts ubsan and kasan slightly for correct panic handling. This patch (of 6): The Undefined Behavior Sanitizer can operate in two modes: warning reporting mode via lib/ubsan.c handler calls, or trap mode, which uses __builtin_trap() as the handler. Using lib/ubsan.c means the kernel image is about 5% larger (due to all the debugging text and reporting structures to capture details about the warning conditions). Using the trap mode, the image size changes are much smaller, though at the loss of the "warning only" mode. In order to give greater flexibility to system builders that want minimal changes to image size and are prepared to deal with kernel code being aborted and potentially destabilizing the system, this introduces CONFIG_UBSAN_TRAP. The resulting image sizes comparison: text data bss dec hex filename 19533663 6183037 18554956 44271656 2a38828 vmlinux.stock 19991849 7618513 18874448 46484810 2c54d4a vmlinux.ubsan 19712181 6284181 18366540 44362902 2a4ec96 vmlinux.ubsan-trap CONFIG_UBSAN=y: image +4.8% (text +2.3%, data +18.9%) CONFIG_UBSAN_TRAP=y: image +0.2% (text +0.9%, data +1.6%) Additionally adjusts the CONFIG_UBSAN Kconfig help for clarity and removes the mention of non-existing boot param "ubsan_handle". Suggested-by: Elena Petrova Signed-off-by: Kees Cook Signed-off-by: Andrew Morton Acked-by: Dmitry Vyukov Cc: Andrey Ryabinin Cc: Andrey Konovalov Cc: Alexander Potapenko Cc: Dan Carpenter Cc: "Gustavo A. R. Silva" Cc: Arnd Bergmann Cc: Ard Biesheuvel Link: http://lkml.kernel.org/r/20200227193516.32566-2-keescook@chromium.org Signed-off-by: Linus Torvalds --- lib/Makefile | 2 ++ 1 file changed, 2 insertions(+) (limited to 'lib/Makefile') diff --git a/lib/Makefile b/lib/Makefile index 3fc06399295d..685aee60de1d 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -286,7 +286,9 @@ quiet_cmd_build_OID_registry = GEN $@ clean-files += oid_registry_data.c obj-$(CONFIG_UCS2_STRING) += ucs2_string.o +ifneq ($(CONFIG_UBSAN_TRAP),y) obj-$(CONFIG_UBSAN) += ubsan.o +endif UBSAN_SANITIZE_ubsan.o := n KASAN_SANITIZE_ubsan.o := n -- cgit