linux-kernel - [PATCH 4/6] sbitmap: remove offset wrap logic when finding bit in word

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: <20230720094555.1397621-5-chengming.zhou@linux.dev>
Date:   Thu, 20 Jul 2023 17:45:53 +0800
From:   chengming.zhou@...ux.dev
To:     axboe@...nel.dk, osandov@...com, ming.lei@...hat.com,
        kbusch@...nel.org, krisman@...e.de
Cc:     linux-kernel@...r.kernel.org, linux-block@...r.kernel.org,
        zhouchengming@...edance.com
Subject: [PATCH 4/6] sbitmap: remove offset wrap logic when finding bit in word

From: Chengming Zhou <zhouchengming@...edance.com>

We actually don't need the offset hint wrap logic in word:

1. Strict round-robin mode: just search from that offset hint,
   we will recheck that word at last if offset hint > 0.

2. No round-robin mode: we use offset hint == 0, so don't need
   to wrap offset hint too.

We remove offset wrap logic and simplify the code.

Signed-off-by: Chengming Zhou <zhouchengming@...edance.com>
---
 lib/sbitmap.c | 36 ++++++++++--------------------------
 1 file changed, 10 insertions(+), 26 deletions(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 0f3943bd3940..50bdf3a31947 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -134,34 +134,21 @@ void sbitmap_resize(struct sbitmap *sb, unsigned int depth)
 EXPORT_SYMBOL_GPL(sbitmap_resize);
 
 static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
-			      unsigned int hint, bool wrap)
+			      unsigned int hint)
 {
 	int nr;
 
-	/* don't wrap if starting from 0 */
-	wrap = wrap && hint;
-
 	while (1) {
 		nr = find_next_zero_bit(word, depth, hint);
-		if (unlikely(nr >= depth)) {
-			if (wrap) {
-				hint = 0;
-				continue;
-			}
+		if (unlikely(nr >= depth))
 			return -1;
-		}
 
 		if (!test_and_set_bit_lock(nr, word))
 			break;
 
 		hint = nr + 1;
-		if (hint >= depth) {
-			if (wrap) {
-				hint = 0;
-				continue;
-			}
+		if (hint >= depth)
 			return -1;
-		}
 	}
 
 	return nr;
@@ -169,14 +156,13 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
 
 static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
 				    unsigned int depth,
-				    unsigned int alloc_hint,
-				    bool wrap)
+				    unsigned int alloc_hint)
 {
 	int nr;
 
 	do {
 		nr = __sbitmap_get_word(&map->word, depth,
-					alloc_hint, wrap);
+					alloc_hint);
 		if (nr != -1)
 			break;
 		if (!sbitmap_deferred_clear(map))
@@ -189,8 +175,7 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
 static int sbitmap_find_bit(struct sbitmap *sb,
 			    unsigned int depth,
 			    unsigned int index,
-			    unsigned int alloc_hint,
-			    bool wrap)
+			    unsigned int alloc_hint)
 {
 	unsigned int map_nr = sb->map_nr;
 	unsigned int i;
@@ -200,7 +185,7 @@ static int sbitmap_find_bit(struct sbitmap *sb,
 	 * If we have alloc_hint > 0 and don't wrap, we need to
 	 * recheck sb->map[index] with hint == 0 to exhaust the map.
 	 */
-	if (alloc_hint && !wrap)
+	if (alloc_hint)
 		map_nr += 1;
 
 	for (i = 0; i < map_nr; i++) {
@@ -208,7 +193,7 @@ static int sbitmap_find_bit(struct sbitmap *sb,
 					      min_t(unsigned int,
 						    __map_depth(sb, index),
 						    depth),
-					      alloc_hint, wrap);
+					      alloc_hint);
 
 		if (nr != -1) {
 			nr += index << sb->shift;
@@ -240,8 +225,7 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
 	else
 		alloc_hint = 0;
 
-	return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,
-				!sb->round_robin);
+	return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint);
 }
 
 int sbitmap_get(struct sbitmap *sb)
@@ -272,7 +256,7 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 	/* No point in looping twice in find_next_zero_bit() for this case. */
 	alloc_hint = 0;
 
-	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);
+	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint);
 }
 
 int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
-- 
2.41.0