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

[Jens Axboe <axboe@kernel.dk>]

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?


-- 
Jens Axboe