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 <osan...@fb.com>
> > >
> > > A couple of comments below, once you address those you can add
> > >
> > > Reviewed-by: Omar Sandoval <osan...@fb.com>
> > >
> > > > Signed-off-by: Ming Lei <ming....@redhat.com>
> > > > ---
> > > > 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
> >
> > 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 = &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.
> 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?
>From dd455230fed9200d519d3ae4f4c32a1430506441 Mon Sep 17 00:00:00 2001
From: Ming Lei <ming....@redhat.com>
Date: Wed, 2 Aug 2017 15:53:09 +0800
Subject: [PATCH] sbitmap: introduce __sbitmap_for_each_set()
We need to iterate ctx starting from any ctx in round robin
way, so introduce this helper.
Cc: Omar Sandoval <osan...@fb.com>
Signed-off-by: Ming Lei <ming....@redhat.com>
---
include/linux/sbitmap.h | 68 ++++++++++++++++++++++++++++++++++---------------
1 file changed, 48 insertions(+), 20 deletions(-)
diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
index a1904aadbc45..4df5480b7c4e 100644
--- a/include/linux/sbitmap.h
+++ b/include/linux/sbitmap.h
@@ -211,46 +211,74 @@ 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.
+ * @start: 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.
- *
- * 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,
+ const unsigned int start,
+ sb_for_each_fn fn, void *data)
{
- unsigned int i;
-
- for (i = 0; i < sb->map_nr; i++) {
- struct sbitmap_word *word = &sb->map[i];
- unsigned int off, nr;
+ unsigned int index = SB_NR_TO_INDEX(sb, start);
+ unsigned int nr = SB_NR_TO_BIT(sb, start);
+ struct sbitmap_word *word = &sb->map[index];
+ unsigned int depth = word->depth;
+ /*
+ * 'scanned' is always updated beforehand, so the exit
+ * check has to be done after the inner bitmap scanning
+ * is completed.
+ */
+ unsigned int scanned = depth - nr;
+ do {
if (!word->word)
- continue;
+ goto next;
- nr = 0;
- off = i << 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))
+ if (!fn(sb, (index << sb->shift) + nr, data))
return;
nr++;
}
- }
+ next:
+ if (scanned >= sb->depth)
+ break;
+
+ depth = min_t(unsigned int, word->depth, sb->depth - scanned);
+ scanned += depth;
+
+ if (++index >= sb->map_nr)
+ index = 0;
+ word = &sb->map[index];
+ nr = 0;
+ } while (1);
}
-#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.
+ */
+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
--
Ming
