| Message ID | 8bde3953-56d8-32cb-2c34-582d632f4a3f@kernel.dk (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | sbitmap: check cleared bits when iterating busy bits | expand |
On Mon, Dec 03, 2018 at 02:56:17PM -0700, Jens Axboe wrote: > When we are iterating the set bits in a word, we also need to factor in > the cleared bits. Don't call fn() unless the bit is also not set in > the cleared word. > > Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits") > Signed-off-by: Jens Axboe <axboe@kernel.dk> > > diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h > index 92806a2dbab7..9f374fbcdba6 100644 > --- a/include/linux/sbitmap.h > +++ b/include/linux/sbitmap.h > @@ -283,6 +283,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, > nr = find_next_bit(&word->word, depth, nr); > if (nr >= depth) > break; > + /* if set in cleared, it's actually free */ > + if (test_bit(nr, &word->cleared)) { > + nr++; > + continue; > + } > if (!fn(sb, (index << sb->shift) + nr, data)) > return; > > -- > Jens Axboe > How about something like this: diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h index f0f49bbb2617..fe9122386255 100644 --- a/include/linux/sbitmap.h +++ b/include/linux/sbitmap.h @@ -265,12 +265,14 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, nr = SB_NR_TO_BIT(sb, start); while (scanned < sb->depth) { - struct sbitmap_word *word = &sb->map[index]; - unsigned int depth = min_t(unsigned int, word->depth - nr, + unsigned long word; + unsigned int depth = min_t(unsigned int, + sb->map[index].depth - nr, sb->depth - scanned); scanned += depth; - if (!word->word) + word = sb->map[index].word & ~sb->map[index].cleared; + if (!word) goto next; /* @@ -280,7 +282,7 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, */ depth += nr; while (1) { - nr = find_next_bit(&word->word, depth, nr); + nr = find_next_bit(&word, depth, nr); if (nr >= depth) break; if (!fn(sb, (index << sb->shift) + nr, data)) Might be marginally faster.
On 12/3/18 3:05 PM, Omar Sandoval wrote: > On Mon, Dec 03, 2018 at 02:56:17PM -0700, Jens Axboe wrote: >> When we are iterating the set bits in a word, we also need to factor in >> the cleared bits. Don't call fn() unless the bit is also not set in >> the cleared word. >> >> Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits") >> Signed-off-by: Jens Axboe <axboe@kernel.dk> >> >> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h >> index 92806a2dbab7..9f374fbcdba6 100644 >> --- a/include/linux/sbitmap.h >> +++ b/include/linux/sbitmap.h >> @@ -283,6 +283,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, >> nr = find_next_bit(&word->word, depth, nr); >> if (nr >= depth) >> break; >> + /* if set in cleared, it's actually free */ >> + if (test_bit(nr, &word->cleared)) { >> + nr++; >> + continue; >> + } >> if (!fn(sb, (index << sb->shift) + nr, data)) >> return; >> >> -- >> Jens Axboe >> > > How about something like this: > > diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h > index f0f49bbb2617..fe9122386255 100644 > --- a/include/linux/sbitmap.h > +++ b/include/linux/sbitmap.h > @@ -265,12 +265,14 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, > nr = SB_NR_TO_BIT(sb, start); > > while (scanned < sb->depth) { > - struct sbitmap_word *word = &sb->map[index]; > - unsigned int depth = min_t(unsigned int, word->depth - nr, > + unsigned long word; > + unsigned int depth = min_t(unsigned int, > + sb->map[index].depth - nr, > sb->depth - scanned); > > scanned += depth; > - if (!word->word) > + word = sb->map[index].word & ~sb->map[index].cleared; > + if (!word) > goto next; > > /* > @@ -280,7 +282,7 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, > */ > depth += nr; > while (1) { > - nr = find_next_bit(&word->word, depth, nr); > + nr = find_next_bit(&word, depth, nr); > if (nr >= depth) > break; > if (!fn(sb, (index << sb->shift) + nr, data)) > > Might be marginally faster. Yeah that looks fine as well, tests out good too.
diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h index 92806a2dbab7..9f374fbcdba6 100644 --- a/include/linux/sbitmap.h +++ b/include/linux/sbitmap.h @@ -283,6 +283,11 @@ static inline void __sbitmap_for_each_set(struct sbitmap *sb, nr = find_next_bit(&word->word, depth, nr); if (nr >= depth) break; + /* if set in cleared, it's actually free */ + if (test_bit(nr, &word->cleared)) { + nr++; + continue; + } if (!fn(sb, (index << sb->shift) + nr, data)) return;
When we are iterating the set bits in a word, we also need to factor in the cleared bits. Don't call fn() unless the bit is also not set in the cleared word. Fixes: ea86ea2cdced ("sbitmap: ammortize cost of clearing bits") Signed-off-by: Jens Axboe <axboe@kernel.dk>