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

[Omar Sandoval <osandov@osandov.com>]

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 = &sb->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->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 &struct 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 = &sb->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)