[PATCH v2 1/3] sbitmap: fix hint wrap in the failure case

[PATCH v2 1/3] sbitmap: fix hint wrap in the failure case

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

```
hint = nr + 1;
if (hint >= depth - 1)
	hint = 0;
```

Now we wrap the hint to 0 in the failure case, but has two problems:
1. hint == depth - 1, is actually an available offset hint, in which
   case we shouldn't wrap hint to 0.
2. In the strict round_robin non-wrap case, we shouldn't wrap at all.

```
wrap = wrap && hint;
```

We only need to check wrap based on the original hint ( > 0), don't need
to recheck the new hint which maybe updated in the failure case, which
may cause second wrap. We set wrap to false after we wrap once to avoid
repeated wrap, which is clearer than rechecking the hint.

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

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index d0a5081dfd12..ac4027884765 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -149,7 +149,8 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
 			 * offset to 0 in a failure case, so start from 0 to
 			 * exhaust the map.
 			 */
-			if (hint && wrap) {
+			if (wrap) {
+				wrap = false;
 				hint = 0;
 				continue;
 			}
@@ -160,8 +161,14 @@ static int __sbitmap_get_word(unsigned long *word, unsigned long depth,
 			break;
 
 		hint = nr + 1;
-		if (hint >= depth - 1)
-			hint = 0;
+		if (unlikely(hint >= depth)) {
+			if (wrap) {
+				wrap = false;
+				hint = 0;
+				continue;
+			}
+			return -1;
+		}
 	}
 
 	return nr;
-- 
2.41.0

[PATCH v2 2/3] sbitmap: fix strict round-robin non-wrap with hint > 0

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.com>

If we have alloc_hint > 0 and don't wrap, we need to recheck
sb->map[index] with hint == 0 to exhaust the map.

For example: we have 8 words to search, index == 4, hint > 0

In sb->map[4] word, we only search [hint, 63] bits in the first
word search. Then we search left 7 words, the sb->map[4] [0, hint-1]
bits aren't searched.

This patch fix it by searching 9 words in this case, so we will
search sb->map[4] the second time at last with hint == 0.

Signed-off-by: Chengming Zhou <zhouchengming@bytedance.com>
---
 lib/sbitmap.c | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)

diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index ac4027884765..6e098a46be26 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -199,10 +199,18 @@ static int sbitmap_find_bit(struct sbitmap *sb,
 			    unsigned int alloc_hint,
 			    bool wrap)
 {
+	unsigned int map_nr = sb->map_nr;
 	unsigned int i;
 	int nr = -1;
 
-	for (i = 0; i < sb->map_nr; i++) {
+	/*
+	 * 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)
+		map_nr += 1;
+
+	for (i = 0; i < map_nr; i++) {
 		nr = sbitmap_find_bit_in_word(&sb->map[index],
 					      min_t(unsigned int,
 						    __map_depth(sb, index),
-- 
2.41.0

[PATCH v2 3/3] sbitmap: drop wrap logic in __sbitmap_get_word()

[chengming.zhou]

From: Chengming Zhou <zhouchengming@bytedance.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@bytedance.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