Re: [PATCH] lib/bsearch: add mutex protection for thread-safe binary search

[Kuan-Wei Chiu <visitorckw@gmail.com>]

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
> 
>