Re: [PATCH 1/2] sbitmap: ammortize cost of clearing bits

[Omar Sandoval <osandov@osandov.com>]

On Fri, Nov 30, 2018 at 01:10:47PM -0700, Jens Axboe wrote:
> On 11/30/18 1:03 PM, Omar Sandoval wrote:
> > On Fri, Nov 30, 2018 at 09:01:17AM -0700, Jens Axboe wrote:
> >> sbitmap maintains a set of words that we use to set and clear bits, with
> >> each bit representing a tag for blk-mq. Even though we spread the bits
> >> out and maintain a hint cache, one particular bit allocated will end up
> >> being cleared in the exact same spot.
> >>
> >> This introduces batched clearing of bits. Instead of clearing a given
> >> bit, the same bit is set in a cleared/free mask instead. If we fail
> >> allocating a bit from a given word, then we check the free mask, and
> >> batch move those cleared bits at that time. This trades 64 atomic bitops
> >> for 2 cmpxchg().
> >>
> >> In a threaded poll test case, half the overhead of getting and clearing
> >> tags is removed with this change. On another poll test case with a
> >> single thread, performance is unchanged.
> >>
> >> Signed-off-by: Jens Axboe <axboe@kernel.dk>
> >> ---
> >>  include/linux/sbitmap.h | 31 +++++++++++++---
> >>  lib/sbitmap.c           | 80 +++++++++++++++++++++++++++++++++++++----
> >>  2 files changed, 100 insertions(+), 11 deletions(-)
> >>
> >> diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
> >> index 804a50983ec5..07f117ee19dc 100644
> >> --- a/include/linux/sbitmap.h
> >> +++ b/include/linux/sbitmap.h
> >> @@ -30,14 +30,24 @@ struct seq_file;
> >>   */
> >>  struct sbitmap_word {
> >>  	/**
> >> -	 * @word: The bitmap word itself.
> >> +	 * @depth: Number of bits being used in @word/@cleared
> >>  	 */
> >> -	unsigned long word;
> >> +	unsigned long depth;
> >>  
> >>  	/**
> >> -	 * @depth: Number of bits being used in @word.
> >> +	 * @word: word holding free bits
> >>  	 */
> >> -	unsigned long depth;
> >> +	unsigned long word ____cacheline_aligned_in_smp;
> > 
> > Still splitting up word and depth in separate cachelines?
> 
> Yeah, I mentioned that in one of the other postings, there's still a
> definite win to doing that.
> 
> > Okay, I couldn't find any holes in this one :)
> 
> Good to hear that :-)
> 
> >> -unsigned int sbitmap_weight(const struct sbitmap *sb)
> >> +static unsigned int __sbitmap_weight(const struct sbitmap *sb, bool set)
> >>  {
> >>  	unsigned int i, weight = 0;
> >>  
> >>  	for (i = 0; i < sb->map_nr; i++) {
> >>  		const struct sbitmap_word *word = &sb->map[i];
> >>  
> >> -		weight += bitmap_weight(&word->word, word->depth);
> >> +		if (set)
> >> +			weight += bitmap_weight(&word->word, word->depth);
> > 
> > Should probably do
> > 			weight -= bitmap_weight(&word->cleared, word->depth);
> > 
> > too, right?
> 
> We only use these for the debugfs stuff, how about I just make it static
> instead?

Yeah, with that,

Reviewed-by: Omar Sandoval <osandov@fb.com>