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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <aPC-E1ZQhiLaBbWS@google.com>
Date: Thu, 16 Oct 2025 17:42:43 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: XueBing Chen <chenxb_99091@....com>
Cc: akpm@...ux-foundation.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] lib/bsearch: add mutex protection for thread-safe binary
 search

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@....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@...lice.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
> 
>