sbitmap: add sbitmap_find_bit to remove repeat code in __sbitmap_get/__sbitmap_get_shallow
There are three differences between __sbitmap_get and
__sbitmap_get_shallow when searching free bit:
1. __sbitmap_get_shallow limit number of bit to search per word.
__sbitmap_get has no such limit.
2. __sbitmap_get_shallow always searches with wrap set. __sbitmap_get set
wrap according to round_robin.
3. __sbitmap_get_shallow always searches from first bit in first word.
__sbitmap_get searches from first bit when round_robin is not set
otherwise searches from SB_NR_TO_BIT(sb, alloc_hint).
Add helper function sbitmap_find_bit function to do common search while
accept "limit depth per word", "wrap flag" and "first bit to
search" from caller to support the need of both __sbitmap_get and
__sbitmap_get_shallow.
Reviewed-by: Jan Kara <jack@suse.cz>
Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
Link: https://lore.kernel.org/r/20230116205059.3821738-5-shikemeng@huaweicloud.com
Signed-off-by: Jens Axboe <axboe@kernel.dk>
diff --git a/lib/sbitmap.c b/lib/sbitmap.c
index 27cfcc3..2514e7a 100644
--- a/lib/sbitmap.c
+++ b/lib/sbitmap.c
@@ -186,10 +186,39 @@ static int sbitmap_find_bit_in_word(struct sbitmap_word *map,
return nr;
}
+static int sbitmap_find_bit(struct sbitmap *sb,
+ unsigned int depth,
+ unsigned int index,
+ unsigned int alloc_hint,
+ bool wrap)
+{
+ unsigned int i;
+ int nr = -1;
+
+ for (i = 0; i < sb->map_nr; i++) {
+ nr = sbitmap_find_bit_in_word(&sb->map[index],
+ min_t(unsigned int,
+ __map_depth(sb, index),
+ depth),
+ alloc_hint, wrap);
+
+ if (nr != -1) {
+ nr += index << sb->shift;
+ break;
+ }
+
+ /* Jump to next index. */
+ alloc_hint = 0;
+ if (++index >= sb->map_nr)
+ index = 0;
+ }
+
+ return nr;
+}
+
static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
{
- unsigned int i, index;
- int nr = -1;
+ unsigned int index;
index = SB_NR_TO_INDEX(sb, alloc_hint);
@@ -203,22 +232,8 @@ static int __sbitmap_get(struct sbitmap *sb, unsigned int alloc_hint)
else
alloc_hint = 0;
- for (i = 0; i < sb->map_nr; i++) {
- nr = sbitmap_find_bit_in_word(&sb->map[index],
- __map_depth(sb, index),
- alloc_hint, !sb->round_robin);
- if (nr != -1) {
- nr += index << sb->shift;
- break;
- }
-
- /* Jump to next index. */
- alloc_hint = 0;
- if (++index >= sb->map_nr)
- index = 0;
- }
-
- return nr;
+ return sbitmap_find_bit(sb, UINT_MAX, index, alloc_hint,
+ !sb->round_robin);
}
int sbitmap_get(struct sbitmap *sb)
@@ -242,31 +257,12 @@ static int __sbitmap_get_shallow(struct sbitmap *sb,
unsigned int alloc_hint,
unsigned long shallow_depth)
{
- unsigned int i, index;
- int nr = -1;
+ unsigned int index;
index = SB_NR_TO_INDEX(sb, alloc_hint);
alloc_hint = SB_NR_TO_BIT(sb, alloc_hint);
- for (i = 0; i < sb->map_nr; i++) {
- nr = sbitmap_find_bit_in_word(&sb->map[index],
- min_t(unsigned int,
- __map_depth(sb, index),
- shallow_depth),
- alloc_hint, true);
-
- if (nr != -1) {
- nr += index << sb->shift;
- break;
- }
-
- /* Jump to next index. */
- alloc_hint = 0;
- if (++index >= sb->map_nr)
- index = 0;
- }
-
- return nr;
+ return sbitmap_find_bit(sb, shallow_depth, index, alloc_hint, true);
}
int sbitmap_get_shallow(struct sbitmap *sb, unsigned long shallow_depth)
