Re: [PATCH v2 RFC 2/4] lib/sbitmap: fix shallow_depth tag allocation

[Yu Kuai]

Hi,

在 2024/12/18 5:47, Bart Van Assche 写道:
> On 12/16/24 6:40 PM, Yu Kuai wrote:
> > From: Yu Kuai <yukuai3@xxxxxxxxxx>
> >
> > Currently, shallow_depth is used by bfq, kyber and mq-deadline, they both
>
> both -> all
>
> > pass in the value for the whole sbitmap, while sbitmap treats the value
>
> treats for -> applies to
>
> > for just one word. Which means, shallow_depth never work as expected,
>
> work -> works
>
> > and there really is no such functional tests to covert it.
>
> is ... tests -> is ... test or are ... tests
>
> covert -> cover
>
> > Consider that callers doesn't know which word will be used, and it's
>
> Consider -> Considering
> doesn't -> don't
>
> > diff --git a/include/linux/sbitmap.h b/include/linux/sbitmap.h
> > index 189140bf11fc..92e77bc13cf6 100644
> > --- a/include/linux/sbitmap.h
> > +++ b/include/linux/sbitmap.h
> > @@ -213,12 +213,12 @@ int sbitmap_get(struct sbitmap *sb);
> >    * sbitmap_get_shallow() - Try to allocate a free bit from a &struct 
> > sbitmap,
> >    * limiting the depth used from each word.
> >    * @sb: Bitmap to allocate from.
> > - * @shallow_depth: The maximum number of bits to allocate from a 
> > single word.
> > + * @shallow_depth: The maximum number of bits to allocate from the 
> > bitmap.
> >    *
> >    * This rather specific operation allows for having multiple users with
> >    * different allocation limits. E.g., there can be a high-priority 
> > class that
> >    * uses sbitmap_get() and a low-priority class that uses 
> > sbitmap_get_shallow()
> > - * with a @shallow_depth of (1 << (@sb->shift - 1)). Then, the 
> > low-priority
> > + * with a @shallow_depth of (sb->depth << 1). Then, the low-priority
>
> (sb->depth << 1) -> (sb->depth >> 1)
>
> > diff --git a/lib/sbitmap.c b/lib/sbitmap.c
> > index d3412984170c..6b8b909614a5 100644
> > --- a/lib/sbitmap.c
> > +++ b/lib/sbitmap.c
> > @@ -208,8 +208,27 @@ static int sbitmap_find_bit_in_word(struct 
> > sbitmap_word *map,
> >       return nr;
> >   }
> > +static unsigned int __map_depth_with_shallow(const struct sbitmap *sb,
> > +                         int index,
> > +                         unsigned int shallow_depth)
> > +{
> > +    unsigned int pre_word_bits = 0;
> > +
> > +    if (shallow_depth >= sb->depth)
> > +        return __map_depth(sb, index);
> > +
> > +    if (index > 0)
> > +        pre_word_bits += (index - 1) << sb->shift;
>
> Why "index - 1" instead of "index"?

We're finding bit in the 'index' word, and pre_word_bits are the number
of bits in previous workds.

> > +
> > +    if (shallow_depth <= pre_word_bits)
> > +        return 0;
> > +
> > +    return min_t(unsigned int, __map_depth(sb, index),
> > +                   shallow_depth - pre_word_bits);
> > +}
>
> How about renaming pre_word_bits into lower_bound?

Yes.
> Otherwise this patch looks good to me.

Thanks,
Kuai

> Thanks,
>
> Bart.
> .