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

[Omar Sandoval <osandov@osandov.com>]

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.

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