On Sat, Sep 02, 2017 at 11:17:17PM +0800, Ming Lei wrote: > We need to iterate ctx starting from any ctx in round robin > way, so introduce this helper. > > Cc: Omar Sandoval <[email protected]>
A couple of comments below, once you address those you can add Reviewed-by: Omar Sandoval <[email protected]> > Signed-off-by: Ming Lei <[email protected]> > --- > include/linux/sbitmap.h | 54 > ++++++++++++++++++++++++++++++++++++------------- > 1 file changed, 40 insertions(+), 14 deletions(-) > > diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h > index a1904aadbc45..2329b9e1a0e2 100644 > --- a/include/linux/sbitmap.h > +++ b/include/linux/sbitmap.h > @@ -211,10 +211,14 @@ bool sbitmap_any_bit_set(const struct sbitmap *sb); > */ > bool sbitmap_any_bit_clear(const struct sbitmap *sb); > > +#define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift) > +#define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U)) > + > typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned int, void *); > > /** > * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap. > + * @off: Where to start the iteration > * @sb: Bitmap to iterate over. > * @fn: Callback. Should return true to continue or false to break early. > * @data: Pointer to pass to callback. > @@ -222,35 +226,57 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, > unsigned int, void *); > * This is inline even though it's non-trivial so that the function calls to > the > * callback will hopefully get optimized away. > */ > -static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn > fn, > - void *data) > +static inline void __sbitmap_for_each_set(struct sbitmap *sb, > + unsigned int off, > + sb_for_each_fn fn, void *data) > { > - unsigned int i; > + unsigned int index = SB_NR_TO_INDEX(sb, off); > + unsigned int nr = SB_NR_TO_BIT(sb, off); > + unsigned int scanned = 0; > > - for (i = 0; i < sb->map_nr; i++) { > - struct sbitmap_word *word = &sb->map[i]; > - unsigned int off, nr; > + while (1) { > + struct sbitmap_word *word = &sb->map[index]; > + unsigned int depth = min_t(unsigned int, word->depth - nr, > + sb->depth - scanned); > > + scanned += depth; > if (!word->word) > - continue; > + goto next; > > - nr = 0; > - off = i << sb->shift; > + depth += nr; I had to think hard to convince myself this was right. If above we set depth to (sb->depth - scanned), then we must have already looped at least once, so nr must be 0, therefore this is okay. Am I following this correctly? I think reassigning like so would be more clear: depth = min_t(unsigned int, word->depth, sb->depth - scanned); > + off = index << sb->shift; > while (1) { > - nr = find_next_bit(&word->word, word->depth, nr); > - if (nr >= word->depth) > + nr = find_next_bit(&word->word, depth, nr); > + if (nr >= depth) > break; > - > if (!fn(sb, off + nr, data)) > return; > > nr++; > } > + next: > + if (scanned >= sb->depth) > + break; > + nr = 0; > + if (++index >= sb->map_nr) > + index = 0; > } > } > > -#define SB_NR_TO_INDEX(sb, bitnr) ((bitnr) >> (sb)->shift) > -#define SB_NR_TO_BIT(sb, bitnr) ((bitnr) & ((1U << (sb)->shift) - 1U)) > +/** > + * sbitmap_for_each_set() - Iterate over each set bit in a &struct sbitmap. > + * @sb: Bitmap to iterate over. > + * @fn: Callback. Should return true to continue or false to break early. > + * @data: Pointer to pass to callback. > + * > + * This is inline even though it's non-trivial so that the function calls to > the > + * callback will hopefully get optimized away. This part of the comment doesn't make sense for this wrapper, please remove it. > + */ > +static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn > fn, > + void *data) > +{ > + __sbitmap_for_each_set(sb, 0, fn, data); > +} > > static inline unsigned long *__sbitmap_word(struct sbitmap *sb, > unsigned int bitnr) > -- > 2.9.5 >
