linux-kernel - [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-next>] [day] [month] [year] [list]

Message-Id: <20251016090640.6331-1-chenxb_99091@126.com>
Date: Thu, 16 Oct 2025 17:06:40 +0800
From: XueBing Chen <chenxb_99091@....com>
To: akpm@...ux-foundation.org
Cc: linux-kernel@...r.kernel.org,
	XueBing Chen <chenxb_99091@....com>
Subject: [PATCH] lib/bsearch: add mutex protection for thread-safe binary search

Replace the __inline_bsearch() wrapper with a full implementation
that includes mutex protection to ensure thread safety when
multiple threads call bsearch() concurrently.

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.

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.
  */
 
 #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);
+	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 (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