* Re: [PATCH] lib/bsearch: add mutex protection for thread-safe binary search
2025-10-16 9:06 [PATCH] lib/bsearch: add mutex protection for thread-safe binary search XueBing Chen
@ 2025-10-16 9:42 ` Kuan-Wei Chiu
2025-10-17 7:28 ` kernel test robot
2025-10-21 4:47 ` kernel test robot
2 siblings, 0 replies; 4+ messages in thread
From: Kuan-Wei Chiu @ 2025-10-16 9:42 UTC (permalink / raw)
To: XueBing Chen; +Cc: akpm, linux-kernel
Hi XueBing,
On Thu, Oct 16, 2025 at 05:06:40PM +0800, XueBing Chen wrote:
> Replace the __inline_bsearch() wrapper with a full implementation
> that includes mutex protection to ensure thread safety when
> multiple threads call bsearch() concurrently.
Adding a global mutex lock here will introduce a performance penalty
for all users of bsearch(), even those who do not require this
protection.
If a specific user needs synchronization, shouldn't they be responsible
for implementing it? For example, by adding a lock around their call t
bsearch() or implementing the necessary locking within their compare
function.
>
> The original implementation lacked synchronization, which could
> lead to race conditions in multi-threaded environments when
> accessing shared arrays or using non-atomic comparison functions.
Could you please provide more details on the specific race condition
you observed? What is the use case, and how does this race manifest?
A concrete example, a reproducer, or a link to a bug report would be
very helpful to understand the motivation for this change.
>
> Signed-off-by: XueBing Chen <chenxb_99091@126.com>
> ---
> lib/bsearch.c | 29 ++++++++++++++++++++++++++---
> 1 file changed, 26 insertions(+), 3 deletions(-)
>
> diff --git a/lib/bsearch.c b/lib/bsearch.c
> index bf86aa66f..9a5a2e949 100644
> --- a/lib/bsearch.c
> +++ b/lib/bsearch.c
> @@ -1,9 +1,12 @@
> -// SPDX-License-Identifier: GPL-2.0-only
> /*
> * A generic implementation of binary search for the Linux kernel
> *
> * Copyright (C) 2008-2009 Ksplice, Inc.
> * Author: Tim Abbott <tabbott@ksplice.com>
> + *
> + * This program is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU General Public License as
> + * published by the Free Software Foundation; version 2.
The addition of the full GPL-2 boilerplate text seems redundant and is
unrelated to the patch's functional change.
> */
>
> #include <linux/export.h>
> @@ -28,9 +31,29 @@
> * the key and elements in the array are of the same type, you can use
> * the same comparison function for both sort() and bsearch().
> */
> -void *bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp)
> +DEFINE_MUTEX(cmp_mutex);
> +void *bsearch(const void *key, const void *base, size_t num, size_t size,
> + int (*cmp)(const void *key, const void *elt))
> {
> - return __inline_bsearch(key, base, num, size, cmp);
This patch replaces the wrapper with a full implementation for the
exported bsearch(), but the inline version remains unlocked.
Why should the non-inline version have this protection while the inline
version does not? This creates an inconsistency.
> + const char *pivot;
> + int result;
> +
> + while (num > 0) {
> + pivot = base + (num >> 1) * size;
> + mutex_lock(&cmp_mutex);
> + result = cmp(key, pivot);
> + mutex_unlock(&cmp_mutex);
If the intent is to protect a cmp function that is not re-entrant,
shouldn't the user who provides that cmp function be responsible for
adding the lock inside it?
Regards,
Kuan-Wei
> + if (result == 0)
> + return (void *)pivot;
> +
> + if (result > 0) {
> + base = pivot + size;
> + num--;
> + }
> + num >>= 1;
> + }
> +
> + return NULL;
> }
> EXPORT_SYMBOL(bsearch);
> NOKPROBE_SYMBOL(bsearch);
> --
> 2.17.1
>
>
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: [PATCH] lib/bsearch: add mutex protection for thread-safe binary search
2025-10-16 9:06 [PATCH] lib/bsearch: add mutex protection for thread-safe binary search XueBing Chen
2025-10-16 9:42 ` Kuan-Wei Chiu
2025-10-17 7:28 ` kernel test robot
@ 2025-10-21 4:47 ` kernel test robot
2 siblings, 0 replies; 4+ messages in thread
From: kernel test robot @ 2025-10-21 4:47 UTC (permalink / raw)
To: XueBing Chen; +Cc: oe-lkp, lkp, linux-kernel, akpm, XueBing Chen, oliver.sang
Hello,
kernel test robot noticed "BUG:sleeping_function_called_from_invalid_context_at_kernel/locking/mutex.c" on:
commit: b10b12648a2241455e9fee86967327ba9553ec48 ("[PATCH] lib/bsearch: add mutex protection for thread-safe binary search")
url: https://github.com/intel-lab-lkp/linux/commits/XueBing-Chen/lib-bsearch-add-mutex-protection-for-thread-safe-binary-search/20251016-171911
base: https://git.kernel.org/cgit/linux/kernel/git/akpm/mm.git mm-nonmm-unstable
patch link: https://lore.kernel.org/all/20251016090640.6331-1-chenxb_99091@126.com/
patch subject: [PATCH] lib/bsearch: add mutex protection for thread-safe binary search
in testcase: boot
config: i386-randconfig-015-20251019
compiler: gcc-14
test machine: qemu-system-i386 -enable-kvm -cpu SandyBridge -smp 2 -m 4G
(please refer to attached dmesg/kmsg for entire log/backtrace)
If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <oliver.sang@intel.com>
| Closes: https://lore.kernel.org/oe-lkp/202510211047.d2cd27e5-lkp@intel.com
[ 14.272996][ T98] BUG: sleeping function called from invalid context at kernel/locking/mutex.c:575
[ 14.275210][ T98] in_atomic(): 0, irqs_disabled(): 0, non_block: 0, pid: 98, name: modprobe
[ 14.275220][ T98] preempt_count: 0, expected: 0
Starting Load Kernel Modules...
[ 14.275223][ T98] RCU nest depth: 1, expected: 0
[ 14.275227][ T98] 1 lock held by modprobe/98:
[ 14.275231][ T98] #0: b2995db8 (rcu_read_lock){....}-{1:3}, at: check_modstruct_version (kernel/module/version.c:77)
[ 14.291645][ T98] CPU: 1 UID: 0 PID: 98 Comm: modprobe Tainted: G T 6.18.0-rc1-00043-gb10b12648a22 #1 PREEMPT(full)
[ 14.291655][ T98] Tainted: [T]=RANDSTRUCT
[ 14.291658][ T98] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014
[ 14.291660][ T98] Call Trace:
[ 14.291663][ T98] ? show_stack (arch/x86/kernel/dumpstack.c:319)
[ 14.291676][ T98] dump_stack_lvl (lib/dump_stack.c:122)
[ 14.291687][ T98] dump_stack (lib/dump_stack.c:130)
[ 14.291692][ T98] __might_resched.cold (kernel/sched/core.c:8926)
[ 14.291706][ T98] __might_sleep (kernel/sched/core.c:8855)
[ 14.291713][ T98] ? local_clock_noinstr (kernel/sched/clock.c:304 (discriminator 1))
[ 14.291724][ T98] __mutex_lock (include/linux/kernel.h:61 kernel/locking/mutex.c:575 kernel/locking/mutex.c:760)
[ 14.291755][ T98] mutex_lock_nested (kernel/locking/mutex.c:813)
[ 14.291759][ T98] ? bsearch (lib/bsearch.c:44)
[ 14.291765][ T98] bsearch (lib/bsearch.c:44)
[ 14.291776][ T98] find_exported_symbol_in_section (kernel/module/main.c:373)
[ 14.291784][ T98] ? unregister_module_notifier (kernel/module/main.c:358)
[ 14.291792][ T98] find_symbol (kernel/module/main.c:401 (discriminator 2))
[ 14.291799][ T98] ? lock_acquire (kernel/locking/lockdep.c:5872)
[ 14.291807][ T98] ? check_version (kernel/module/version.c:77)
[ 14.291816][ T98] check_modstruct_version (kernel/module/version.c:90)
[ 14.291822][ T98] ? check_version (kernel/module/version.c:77)
[ 14.291837][ T98] early_mod_check (kernel/module/main.c:3333 (discriminator 1))
[ 14.291850][ T98] load_module (kernel/module/main.c:3384)
[ 14.291854][ T98] ? kernel_read (fs/read_write.c:549)
[ 14.291872][ T98] ? init_module_from_file (kernel/module/main.c:3683)
[ 14.291891][ T98] init_module_from_file (kernel/module/main.c:3702)
[ 14.291930][ T98] __ia32_sys_finit_module (kernel/module/main.c:3713 kernel/module/main.c:3739 kernel/module/main.c:3723 kernel/module/main.c:3723)
[ 14.291961][ T98] ia32_sys_call (arch/x86/entry/syscall_32.c:50)
[ 14.291968][ T98] do_int80_syscall_32 (arch/x86/entry/syscall_32.c:83 (discriminator 1) arch/x86/entry/syscall_32.c:259 (discriminator 1))
[ 14.291977][ T98] entry_INT80_32 (arch/x86/entry/entry_32.S:945)
[ 14.291981][ T98] EIP: 0xa7f33092
[ 14.291986][ T98] Code: 00 00 00 e9 90 ff ff ff ff a3 24 00 00 00 68 30 00 00 00 e9 80 ff ff ff ff a3 f8 ff ff ff 66 90 00 00 00 00 00 00 00 00 cd 80 <c3> 8d b4 26 00 00 00 00 8d b6 00 00 00 00 8b 1c 24 c3 8d b4 26 00
All code
========
0: 00 00 add %al,(%rax)
2: 00 e9 add %ch,%cl
4: 90 nop
5: ff (bad)
6: ff (bad)
7: ff (bad)
8: ff a3 24 00 00 00 jmp *0x24(%rbx)
e: 68 30 00 00 00 push $0x30
13: e9 80 ff ff ff jmp 0xffffffffffffff98
18: ff a3 f8 ff ff ff jmp *-0x8(%rbx)
1e: 66 90 xchg %ax,%ax
...
28: cd 80 int $0x80
2a:* c3 ret <-- trapping instruction
2b: 8d b4 26 00 00 00 00 lea 0x0(%rsi,%riz,1),%esi
32: 8d b6 00 00 00 00 lea 0x0(%rsi),%esi
38: 8b 1c 24 mov (%rsp),%ebx
3b: c3 ret
3c: 8d .byte 0x8d
3d: b4 26 mov $0x26,%ah
...
Code starting with the faulting instruction
===========================================
0: c3 ret
1: 8d b4 26 00 00 00 00 lea 0x0(%rsi,%riz,1),%esi
8: 8d b6 00 00 00 00 lea 0x0(%rsi),%esi
e: 8b 1c 24 mov (%rsp),%ebx
11: c3 ret
12: 8d .byte 0x8d
13: b4 26 mov $0x26,%ah
...
[ 14.291989][ T98] EAX: ffffffda EBX: 00000003 ECX: 0042e214 EDX: 00000000
[ 14.291992][ T98] ESI: 011d6ec0 EDI: 011d6de0 EBP: 00000000 ESP: afd3c788
[ 14.291995][ T98] DS: 007b ES: 007b FS: 0000 GS: 0033 SS: 007b EFLAGS: 00200296
[ 14.292023][ T98]
[ 14.335982][ T98] =============================
[ 14.335987][ T98] [ BUG: Invalid wait context ]
Startin[ 14.335990][ T98] 6.18.0-rc1-00043-gb10b12648a22 #1 Tainted: G W T
[ 14.335993][ T98] -----------------------------
[ 14.335995][ T98] modprobe/98 is trying to lock:
[ 14.335998][ T98] b2a23080 (cmp_mutex){+.+.}-{4:4}, at: bsearch (lib/bsearch.c:44)
[ 14.367204][ T98] other info that might help us debug this:
[ 14.367208][ T98] context-{5:5}
[ 14.367211][ T98] 1 lock held by modprobe/98:
[ 14.367214][ T98] #0: b2995db8 (rcu_read_lock){....}-{1:3}, at: check_modstruct_version (kernel/module/version.c:77)
[ 14.367233][ T98] stack backtrace:
[ 14.373209][ T98] CPU: 1 UID: 0 PID: 98 Comm: modprobe Tainted: G W T 6.18.0-rc1-00043-gb10b12648a22 #1 PREEMPT(full)
[ 14.373217][ T98] Tainted: [W]=WARN, [T]=RANDSTRUCT
[ 14.373219][ T98] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.16.3-debian-1.16.3-2 04/01/2014
[ 14.373221][ T98] Call Trace:
[ 14.373225][ T98] ? show_stack (arch/x86/kernel/dumpstack.c:319)
[ 14.373237][ T98] dump_stack_lvl (lib/dump_stack.c:122)
[ 14.373244][ T98] dump_stack (lib/dump_stack.c:130)
[ 14.373248][ T98] __lock_acquire (kernel/locking/lockdep.c:4832 kernel/locking/lockdep.c:4902 kernel/locking/lockdep.c:5187)
[ 14.373255][ T98] lock_acquire (include/trace/events/lock.h:24 (discriminator 1) kernel/locking/lockdep.c:5831 (discriminator 1))
[ 14.373259][ T98] ? bsearch (lib/bsearch.c:44)
[ 14.373265][ T98] ? dump_stack (lib/dump_stack.c:130)
[ 14.373268][ T98] ? __might_resched.cold (kernel/sched/core.c:8926)
[ 14.373273][ T98] lock_acquire (kernel/locking/lockdep.c:5872)
[ 14.373277][ T98] ? bsearch (lib/bsearch.c:44)
[ 14.373281][ T98] __mutex_lock (arch/x86/include/asm/atomic.h:23 include/linux/atomic/atomic-arch-fallback.h:457 include/linux/jump_label.h:262 include/trace/events/lock.h:95 kernel/locking/mutex.c:600 kernel/locking/mutex.c:760)
[ 14.373286][ T98] ? bsearch (lib/bsearch.c:44)
[ 14.373293][ T98] mutex_lock_nested (kernel/locking/mutex.c:813)
[ 14.373296][ T98] ? bsearch (lib/bsearch.c:44)
[ 14.373299][ T98] bsearch (lib/bsearch.c:44)
[ 14.373303][ T98] find_exported_symbol_in_section (kernel/module/main.c:373)
[ 14.373310][ T98] ? unregister_module_notifier (kernel/module/main.c:358)
[ 14.373315][ T98] find_symbol (kernel/module/main.c:401 (discriminator 2))
[ 14.373319][ T98] ? lock_acquire (kernel/locking/lockdep.c:5872)
[ 14.373322][ T98] ? check_version (kernel/module/version.c:77)
[ 14.373326][ T98] check_modstruct_version (kernel/module/version.c:90)
[ 14.373330][ T98] ? check_version (kernel/module/version.c:77)
[ 14.373335][ T98] early_mod_check (kernel/module/main.c:3333 (discriminator 1))
[ 14.373339][ T98] load_module (kernel/module/main.c:3384)
[ 14.373343][ T98] ? kernel_read (fs/read_write.c:549)
[ 14.373350][ T98] ? init_module_from_file (kernel/module/main.c:3683)
[ 14.373355][ T98] init_module_from_file (kernel/module/main.c:3702)
[ 14.373364][ T98] __ia32_sys_finit_module (kernel/module/main.c:3713 kernel/module/main.c:3739 kernel/module/main.c:3723 kernel/module/main.c:3723)
[ 14.373372][ T98] ia32_sys_call (arch/x86/entry/syscall_32.c:50)
[ 14.373378][ T98] do_int80_syscall_32 (arch/x86/entry/syscall_32.c:83 (discriminator 1) arch/x86/entry/syscall_32.c:259 (discriminator 1))
[ 14.373382][ T98] entry_INT80_32 (arch/x86/entry/entry_32.S:945)
[ 14.373386][ T98] EIP: 0xa7f33092
[ 14.373390][ T98] Code: 00 00 00 e9 90 ff ff ff ff a3 24 00 00 00 68 30 00 00 00 e9 80 ff ff ff ff a3 f8 ff ff ff 66 90 00 00 00 00 00 00 00 00 cd 80 <c3> 8d b4 26 00 00 00 00 8d b6 00 00 00 00 8b 1c 24 c3 8d b4 26 00
All code
========
0: 00 00 add %al,(%rax)
2: 00 e9 add %ch,%cl
4: 90 nop
5: ff (bad)
6: ff (bad)
7: ff (bad)
8: ff a3 24 00 00 00 jmp *0x24(%rbx)
e: 68 30 00 00 00 push $0x30
13: e9 80 ff ff ff jmp 0xffffffffffffff98
18: ff a3 f8 ff ff ff jmp *-0x8(%rbx)
1e: 66 90 xchg %ax,%ax
...
28: cd 80 int $0x80
2a:* c3 ret <-- trapping instruction
2b: 8d b4 26 00 00 00 00 lea 0x0(%rsi,%riz,1),%esi
32: 8d b6 00 00 00 00 lea 0x0(%rsi),%esi
38: 8b 1c 24 mov (%rsp),%ebx
3b: c3 ret
3c: 8d .byte 0x8d
3d: b4 26 mov $0x26,%ah
...
Code starting with the faulting instruction
===========================================
0: c3 ret
1: 8d b4 26 00 00 00 00 lea 0x0(%rsi,%riz,1),%esi
8: 8d b6 00 00 00 00 lea 0x0(%rsi),%esi
e: 8b 1c 24 mov (%rsp),%ebx
11: c3 ret
12: 8d .byte 0x8d
13: b4 26 mov $0x26,%ah
...
[ 14.373393][ T98] EAX: ffffffda EBX: 00000003 ECX: 0042e214 EDX: 00000000
[ 14.373397][ T98] ESI: 011d6ec0 EDI: 011d6de0 EBP: 00000000 ESP: afd3c788
[ 14.373400][ T98] DS: 007b ES: 007b FS: 0000 GS: 0033 SS: 007b EFLAGS: 00200296
The kernel config and materials to reproduce are available at:
https://download.01.org/0day-ci/archive/20251021/202510211047.d2cd27e5-lkp@intel.com
--
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
^ permalink raw reply [flat|nested] 4+ messages in thread