Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Omar Sandoval]

On Thu, Sep 14, 2017 at 07:59:43AM -0700, Omar Sandoval wrote:

[snip]

> Honestly I prefer your original patch with a comment on depth += nr. I'd
> be happy with the following incremental patch on top of your original v4
> patch.

Oh, and the change renaming the off parameter to start would be good to
include, too.

> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
> index 2329b9e1a0e2..8d747048ae4f 100644
> --- a/include/linux/sbitmap.h
> +++ b/include/linux/sbitmap.h
> @@ -218,7 +218,7 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned 
> int, void *);
>  
>  /**
>   * sbitmap_for_each_set() - Iterate over each set bit in a  sbitmap.
> - * @off: Where to start the iteration
> + * @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.
> @@ -230,11 +230,16 @@ static inline void __sbitmap_for_each_set(struct 
> sbitmap *sb,
> unsigned int off,
> sb_for_each_fn fn, void *data)
>  {
> - unsigned int index = SB_NR_TO_INDEX(sb, off);
> - unsigned int nr = SB_NR_TO_BIT(sb, off);
> + unsigned int index;
> + unsigned int nr;
>   unsigned int scanned = 0;
>  
> - while (1) {
> + if (off >= sb->depth)
> + off = 0;
> + index = SB_NR_TO_INDEX(sb, off);
> + nr = SB_NR_TO_BIT(sb, off);
> +
> + while (scanned < sb->depth) {
>   struct sbitmap_word *word = >map[index];
>   unsigned int depth = min_t(unsigned int, word->depth - nr,
>  sb->depth - scanned);
> @@ -243,6 +248,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap 
> *sb,
>   if (!word->word)
>   goto next;
>  
> + /*
> +  * On the first iteration of the outer loop, we need to add the
> +  * bit offset back to the size of the word for find_next_bit().
> +  * On all other iterations, nr is zero, so this is a noop.
> +  */
>   depth += nr;
>   off = index << sb->shift;
>   while (1) {
> @@ -254,9 +264,7 @@ static inline void __sbitmap_for_each_set(struct sbitmap 
> *sb,
>  
>   nr++;
>   }
> - next:
> - if (scanned >= sb->depth)
> - break;
> +next:
>   nr = 0;
>   if (++index >= sb->map_nr)
>   index = 0;
> @@ -268,9 +276,6 @@ static inline void __sbitmap_for_each_set(struct sbitmap 
> *sb,
>   * @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.
>   */
>  static inline void sbitmap_for_each_set(struct sbitmap *sb, sb_for_each_fn 
> fn,
>   void *data)

Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Omar Sandoval]

On Thu, Sep 14, 2017 at 09:56:56AM +0800, Ming Lei wrote:
> On Wed, Sep 13, 2017 at 11:37:20AM -0700, Omar Sandoval wrote:
> > On Mon, Sep 11, 2017 at 12:08:29PM +0800, Ming Lei wrote:
> > > On Sun, Sep 10, 2017 at 10:20:27AM -0700, Omar Sandoval wrote:
> > 
> > [snip]
> > 
> > > > What I mean is that you keep the same initialization above, but instead 
> > > > of
> > > > depth += nr
> > > > you do
> > > > depth = min_t(unsigned int, word->depth, sb->depth - 
> > > > scanned);
> > > > because like I said, the reasoning about why `+= nr` is okay in the
> > > > `sb->depth - scanned` case is subtle.
> > > > 
> > > > And maybe even replace the
> > > > scanned += depth;
> > > > with
> > > > scanned += min_t(unsigned int, word->depth - nr,
> > > >  sb->depth - scanned);
> > > > I.e., don't reuse the depth local variable for two different things. I'm
> > > > nitpicking here but this code is tricky enough as it is.
> > > 
> > > It wasn't reused in old version, just for saving one local variable, and
> > > one extra min_t().
> > > 
> > > Yeah, I admit it isn't clean enough.
> > > 
> > > > 
> > > > For completeness, I mean this exactly:
> > > > 
> > > > while (1) {
> > > > struct sbitmap_word *word = >map[index];
> > > > unsigned int depth;
> > > > 
> > > > scanned += min_t(unsigned int, word->depth - nr,
> > > >  sb->depth - scanned);
> > > > if (!word->word)
> > > > goto next;
> > > > 
> > > > depth = min_t(unsigned int, word->depth, sb->depth - 
> > > > scanned);
> > > 
> > > two min_t and a little code duplication.
> > 
> > They're similar but they represent different things, so I think trying
> > to deduplicate this code just makes it more confusing. If performance is
> > your concern, I'd be really surprised if there's a noticable difference.
> 
> No only one extra min_t(), also it isn't easy to read the code, since
> only in the first scan that 'depth' isn't same with 'depth', that is
> why I set the 1st 'scan' outside of the loop, then we can update 'scan'
> with 'depth' in every loop. People will be easy to follow the
> meaning.
> 
> > 
> > As a side note, I also realized that this code doesn't handle the
> > sb->depth == 0 case. We should change the while (1) to
> > while (scanned < sb->depth) and remove the
> > if (scanned >= sb->depth) break;
> 
> In the attached patch, I remember that the zero depth case is
> addressed by:
> 
>   if (start >= sb->depth)
>   return;
> 
> which is required since 'start' parameter is introduced in
> this patch.

I think the better way to handle this is

if (start >= sb->depth)
start = 0;

Since the sbitmap may have gotten resized since the last time the user
called this and cached their start value.

> > 
> > > > off = index << sb->shift;
> > > > while (1) {
> > > > nr = find_next_bit(>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;
> > > > }
> > > 
> > > The following patch switches to do{}while and handles the
> > > 1st scan outside of the loop, then it should be clean
> > > enough(no two min_t()), so how about this one?
> > 
> > I find this one subtler and harder to follow. The less it looks like the
> > typical loop pattern, the longer someone reading the code has to reason
> > about it.
> 
> Looks using 'depth' to update 'scanned' is easier to follow, than
> two min_t(), since it will make people easy to understand the relation
> between the two, then understand the whole code.

Honestly I prefer your original patch with a comment on depth += nr. I'd
be happy with the following incremental patch on top of your original v4
patch.

diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index 2329b9e1a0e2..8d747048ae4f 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -218,7 +218,7 @@ typedef bool (*sb_for_each_fn)(struct sbitmap *, unsigned 
int, void *);
 
 /**
  * sbitmap_for_each_set() - Iterate over each set bit in a  sbitmap.
- * @off: Where to start the iteration
+ * @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.
@@ -230,11 +230,16 @@ static inline void __sbitmap_for_each_set(struct sbitmap 
*sb,
   

Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Ming Lei]

On Wed, Sep 13, 2017 at 11:37:20AM -0700, Omar Sandoval wrote:
> On Mon, Sep 11, 2017 at 12:08:29PM +0800, Ming Lei wrote:
> > On Sun, Sep 10, 2017 at 10:20:27AM -0700, Omar Sandoval wrote:
> 
> [snip]
> 
> > > What I mean is that you keep the same initialization above, but instead of
> > >   depth += nr
> > > you do
> > >   depth = min_t(unsigned int, word->depth, sb->depth - scanned);
> > > because like I said, the reasoning about why `+= nr` is okay in the
> > > `sb->depth - scanned` case is subtle.
> > > 
> > > And maybe even replace the
> > >   scanned += depth;
> > > with
> > >   scanned += min_t(unsigned int, word->depth - nr,
> > >sb->depth - scanned);
> > > I.e., don't reuse the depth local variable for two different things. I'm
> > > nitpicking here but this code is tricky enough as it is.
> > 
> > It wasn't reused in old version, just for saving one local variable, and
> > one extra min_t().
> > 
> > Yeah, I admit it isn't clean enough.
> > 
> > > 
> > > For completeness, I mean this exactly:
> > > 
> > >   while (1) {
> > >   struct sbitmap_word *word = >map[index];
> > >   unsigned int depth;
> > > 
> > >   scanned += min_t(unsigned int, word->depth - nr,
> > >sb->depth - scanned);
> > >   if (!word->word)
> > >   goto next;
> > > 
> > >   depth = min_t(unsigned int, word->depth, sb->depth - scanned);
> > 
> > two min_t and a little code duplication.
> 
> They're similar but they represent different things, so I think trying
> to deduplicate this code just makes it more confusing. If performance is
> your concern, I'd be really surprised if there's a noticable difference.

No only one extra min_t(), also it isn't easy to read the code, since
only in the first scan that 'depth' isn't same with 'depth', that is
why I set the 1st 'scan' outside of the loop, then we can update 'scan'
with 'depth' in every loop. People will be easy to follow the
meaning.

> 
> As a side note, I also realized that this code doesn't handle the
> sb->depth == 0 case. We should change the while (1) to
> while (scanned < sb->depth) and remove the
> if (scanned >= sb->depth) break;

In the attached patch, I remember that the zero depth case is
addressed by:

if (start >= sb->depth)
return;

which is required since 'start' parameter is introduced in
this patch.

> 
> > >   off = index << sb->shift;
> > >   while (1) {
> > >   nr = find_next_bit(>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;
> > >   }
> > 
> > The following patch switches to do{}while and handles the
> > 1st scan outside of the loop, then it should be clean
> > enough(no two min_t()), so how about this one?
> 
> I find this one subtler and harder to follow. The less it looks like the
> typical loop pattern, the longer someone reading the code has to reason
> about it.

Looks using 'depth' to update 'scanned' is easier to follow, than
two min_t(), since it will make people easy to understand the relation
between the two, then understand the whole code.

-- 
Ming

Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Omar Sandoval]

On Mon, Sep 11, 2017 at 12:08:29PM +0800, Ming Lei wrote:
> On Sun, Sep 10, 2017 at 10:20:27AM -0700, Omar Sandoval wrote:

[snip]

> > What I mean is that you keep the same initialization above, but instead of
> > depth += nr
> > you do
> > depth = min_t(unsigned int, word->depth, sb->depth - scanned);
> > because like I said, the reasoning about why `+= nr` is okay in the
> > `sb->depth - scanned` case is subtle.
> > 
> > And maybe even replace the
> > scanned += depth;
> > with
> > scanned += min_t(unsigned int, word->depth - nr,
> >  sb->depth - scanned);
> > I.e., don't reuse the depth local variable for two different things. I'm
> > nitpicking here but this code is tricky enough as it is.
> 
> It wasn't reused in old version, just for saving one local variable, and
> one extra min_t().
> 
> Yeah, I admit it isn't clean enough.
> 
> > 
> > For completeness, I mean this exactly:
> > 
> > while (1) {
> > struct sbitmap_word *word = >map[index];
> > unsigned int depth;
> > 
> > scanned += min_t(unsigned int, word->depth - nr,
> >  sb->depth - scanned);
> > if (!word->word)
> > goto next;
> > 
> > depth = min_t(unsigned int, word->depth, sb->depth - scanned);
> 
> two min_t and a little code duplication.

They're similar but they represent different things, so I think trying
to deduplicate this code just makes it more confusing. If performance is
your concern, I'd be really surprised if there's a noticable difference.

As a side note, I also realized that this code doesn't handle the
sb->depth == 0 case. We should change the while (1) to
while (scanned < sb->depth) and remove the
if (scanned >= sb->depth) break;

> > off = index << sb->shift;
> > while (1) {
> > nr = find_next_bit(>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;
> > }
> 
> The following patch switches to do{}while and handles the
> 1st scan outside of the loop, then it should be clean
> enough(no two min_t()), so how about this one?

I find this one subtler and harder to follow. The less it looks like the
typical loop pattern, the longer someone reading the code has to reason
about it.

Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Ming Lei]

On Sun, Sep 10, 2017 at 10:20:27AM -0700, Omar Sandoval wrote:
> On Sat, Sep 09, 2017 at 05:38:13PM +0800, Ming Lei wrote:
> > On Fri, Sep 08, 2017 at 01:43:41PM -0700, Omar Sandoval wrote:
> > > 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 
> > > 
> > > A couple of comments below, once you address those you can add
> > > 
> > > Reviewed-by: Omar Sandoval 
> > > 
> > > > Signed-off-by: Ming Lei 
> > > > ---
> > > >  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  
> > > > 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 = >map[i];
> > > > -   unsigned int off, nr;
> > > > +   while (1) {
> > > > +   struct sbitmap_word *word = >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
> > 
> > It should be so only in the last loop, in which the 1st half of
> > the word is to be checked because we start from the 2nd half of
> > the same word.
> > 
> > > 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:
> > 
> > Yes, you are right, nr can be non-zero only in the 1st loop.
> > 
> > > 
> > >   depth = min_t(unsigned int, word->depth, sb->depth - scanned);
> > 
> > If nr isn't zero, the depth to be scanned should be 'word->depth - nr'
> > in the 1st loop, so the above way can't cover this case.
> 
> What I mean is that you keep the same initialization above, but instead of
>   depth += nr
> you do
>   depth = min_t(unsigned int, word->depth, sb->depth - scanned);
> because like I said, the reasoning about why `+= nr` is okay in the
> `sb->depth - scanned` case is subtle.
> 
> And maybe even replace the
>   scanned += depth;
> with
>   scanned += min_t(unsigned int, word->depth - nr,
>sb->depth - scanned);
> I.e., don't reuse the depth local variable for two different things. I'm
> nitpicking here but this code is tricky enough as it is.

It wasn't reused in old version, just for saving one local variable, and
one extra min_t().

Yeah, I admit it isn't clean enough.

> 
> For completeness, I mean this exactly:
> 
>   while (1) {
>   struct sbitmap_word *word = >map[index];
>   

Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Omar Sandoval]

On Sat, Sep 09, 2017 at 05:38:13PM +0800, Ming Lei wrote:
> On Fri, Sep 08, 2017 at 01:43:41PM -0700, Omar Sandoval wrote:
> > 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 
> > 
> > A couple of comments below, once you address those you can add
> > 
> > Reviewed-by: Omar Sandoval 
> > 
> > > Signed-off-by: Ming Lei 
> > > ---
> > >  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  
> > > 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 = >map[i];
> > > - unsigned int off, nr;
> > > + while (1) {
> > > + struct sbitmap_word *word = >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
> 
> It should be so only in the last loop, in which the 1st half of
> the word is to be checked because we start from the 2nd half of
> the same word.
> 
> > 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:
> 
> Yes, you are right, nr can be non-zero only in the 1st loop.
> 
> > 
> > depth = min_t(unsigned int, word->depth, sb->depth - scanned);
> 
> If nr isn't zero, the depth to be scanned should be 'word->depth - nr'
> in the 1st loop, so the above way can't cover this case.

What I mean is that you keep the same initialization above, but instead of
depth += nr
you do
depth = min_t(unsigned int, word->depth, sb->depth - scanned);
because like I said, the reasoning about why `+= nr` is okay in the
`sb->depth - scanned` case is subtle.

And maybe even replace the
scanned += depth;
with
scanned += min_t(unsigned int, word->depth - nr,
 sb->depth - scanned);
I.e., don't reuse the depth local variable for two different things. I'm
nitpicking here but this code is tricky enough as it is.

For completeness, I mean this exactly:

while (1) {
struct sbitmap_word *word = >map[index];
unsigned int depth;

scanned += min_t(unsigned int, word->depth - nr,
 sb->depth - scanned);
if (!word->word)
goto next;

depth = min_t(unsigned int, word->depth, sb->depth - scanned);
off = index << sb->shift;
while (1) {
nr = find_next_bit(>word, depth, nr);
if (nr >= depth)
break;

if (!fn(sb, off + nr, 

Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Ming Lei]

On Fri, Sep 08, 2017 at 01:43:41PM -0700, Omar Sandoval wrote:
> 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 
> 
> A couple of comments below, once you address those you can add
> 
> Reviewed-by: Omar Sandoval 
> 
> > Signed-off-by: Ming Lei 
> > ---
> >  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  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 = >map[i];
> > -   unsigned int off, nr;
> > +   while (1) {
> > +   struct sbitmap_word *word = >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

It should be so only in the last loop, in which the 1st half of
the word is to be checked because we start from the 2nd half of
the same word.

> 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:

Yes, you are right, nr can be non-zero only in the 1st loop.

> 
>   depth = min_t(unsigned int, word->depth, sb->depth - scanned);

If nr isn't zero, the depth to be scanned should be 'word->depth - nr'
in the 1st loop, so the above way can't cover this case.

> 
> > +   off = index << sb->shift;
> > while (1) {
> > -   nr = find_next_bit(>word, word->depth, nr);
> > -   if (nr >= word->depth)
> > +   nr = find_next_bit(>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  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.

OK.

-- 
Ming

Re: [PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Omar Sandoval]

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 

A couple of comments below, once you address those you can add

Reviewed-by: Omar Sandoval 

> Signed-off-by: Ming Lei 
> ---
>  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  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 = >map[i];
> - unsigned int off, nr;
> + while (1) {
> + struct sbitmap_word *word = >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->depth, nr);
> - if (nr >= word->depth)
> + nr = find_next_bit(>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  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
> 

[PATCH V4 02/14] sbitmap: introduce __sbitmap_for_each_set()

[Ming Lei]

We need to iterate ctx starting from any ctx in round robin
way, so introduce this helper.

Cc: Omar Sandoval 
Signed-off-by: Ming Lei 
---
 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  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 = >map[i];
-   unsigned int off, nr;
+   while (1) {
+   struct sbitmap_word *word = >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;
+   off = index << sb->shift;
while (1) {
-   nr = find_next_bit(>word, word->depth, nr);
-   if (nr >= word->depth)
+   nr = find_next_bit(>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  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.
+ */
+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