linux-kernel - [PATCH v2 3/3] sbitmap: drop wrap logic in __sbitmap_get

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

Message-ID: <20230727152020.3633009-3-chengming.zhou@linux.dev>
Date:   Thu, 27 Jul 2023 23:20:20 +0800
From:   chengming.zhou@...ux.dev
To:     axboe@...nel.dk, osandov@...com, ming.lei@...hat.com,
        kbusch@...nel.org, krisman@...e.de
Cc:     linux-block@...r.kernel.org, linux-kernel@...r.kernel.org,
        zhouchengming@...edance.com
Subject: [PATCH v2 3/3] sbitmap: drop wrap logic in __sbitmap_get_word()

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

The complex wrap logic in __sbitmap_get_word() seems unnecessary:

1. Strict round-robin mode: wrap == false
   1.1 hint == 0: we search sb->map_nr words, won't wrap
   1.2 hint > 0: we search (sb->map_nr + 1) words, won't wrap

2. Non round-robin mode: wrap == true
   2.1 hint == 0: we search sb->map_nr words, don't need wrap
   2.2 hint > 0: we search sb->map_nr words, need wrap

So 2.2 is the only reason we need wrap logic in __sbitmap_get_word(),
the only user like 2.2 is __sbitmap_get_shallow().

__sbitmap_get_shallow() always set wrap == true no matter the sbitmap
is round-robin or not, seems that it doesn't want strict round-robin
tag in this limited case.

We can remove 2.2 case by setting hint == 0 in __sbitmap_get_shallow(),
since there is no point in looping twice in find_next_zero_bit() if we
don't want strict round-robin tag for this case.

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

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 6e098a46be26..d042dc5d53c3 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -134,41 +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)) {
-			/*
-			 * We started with an offset, and we didn't reset the
-			 * offset to 0 in a failure case, so start from 0 to
-			 * exhaust the map.
-			 */
-			if (wrap) {
-				wrap = false;
-				hint = 0;
-				continue;
-			}
+		if (unlikely(nr >= depth))
 			return -1;
-		}
 
 		if (!test_and_set_bit_lock(nr, word))
 			break;
 
 		hint = nr + 1;
-		if (unlikely(hint >= depth)) {
-			if (wrap) {
-				wrap = false;
-				hint = 0;
-				continue;
-			}
+		if (unlikely(hint >= depth))
 			return -1;
-		}
 	}
 
 	return nr;
@@ -176,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))
@@ -196,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;
@@ -207,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++) {
@@ -215,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;
@@ -247,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)
@@ -275,9 +252,11 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
 	unsigned int index;
 
 	index = SB_NR_TO_INDEX(sb, alloc_hint);
-	alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
 
-	return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);
+	/* 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);
 }
 
 int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
-- 
2.41.0