Re: [PATCH v2 1/5] blk-mq: abstract tag allocation out into scale_bitmap library

[Omar Sandoval <osandov@osandov.com>]

On Wed, Sep 07, 2016 at 05:01:56PM -0700, Alexei Starovoitov wrote:
> On 9/7/16 4:46 PM, Omar Sandoval wrote:
> > From: Omar Sandoval <osandov@fb.com>
> > 
> > This is a generally useful data structure, so make it available to
> > anyone else who might want to use it. It's also a nice cleanup
> > separating the allocation logic from the rest of the tag handling logic.
> > 
> > The code is behind a new Kconfig option, CONFIG_SCALE_BITMAP, which is
> > only selected by CONFIG_BLOCK for now.
> > 
> > This should be a complete noop functionality-wise.
> > 
> > Signed-off-by: Omar Sandoval <osandov@fb.com>
> > ---
> >   MAINTAINERS                  |   1 +
> >   block/Kconfig                |   1 +
> >   block/blk-mq-tag.c           | 469 ++++++++++---------------------------------
> >   block/blk-mq-tag.h           |  37 +---
> >   block/blk-mq.c               | 113 +++--------
> >   block/blk-mq.h               |   9 -
> >   include/linux/blk-mq.h       |   9 +-
> >   include/linux/scale_bitmap.h | 340 +++++++++++++++++++++++++++++++
> >   lib/Kconfig                  |   3 +
> >   lib/Makefile                 |   2 +
> >   lib/scale_bitmap.c           | 305 ++++++++++++++++++++++++++++
> ...
> > diff --git a/include/linux/scale_bitmap.h b/include/linux/scale_bitmap.h
> > new file mode 100644
> > index 0000000..63f712b
> > --- /dev/null
> > +++ b/include/linux/scale_bitmap.h
> > @@ -0,0 +1,340 @@
> > +/*
> > + * Fast and scalable bitmaps.
> ...
> > +/**
> > + * struct scale_bitmap_word - Word in a &struct scale_bitmap.
> > + */
> > +struct scale_bitmap_word {
> > +/**
> > + * struct scale_bitmap - Scalable bitmap.
> > + *
> > + * A &struct scale_bitmap is spread over multiple cachelines to avoid ping-pong.
> > + * This trades off higher memory usage for better scalability.
> > + */
> > +struct scale_bitmap {
> 
> scale_bitmap sounds odd, since 'scale' is also a verb.
> We also have lib/rhashtable.c:
>  * Resizable, Scalable, Concurrent Hash Table
> everything is 'scalable' nowadays.

Agreed, I'm not a huge fan of the name.

> May be resizable bitmap would be a better name?
> 'struct rbitmap'... lib/rbitmap.c ?
> 

Hm, the resizing operation isn't very well thought-out right now, it's
there because it's okay for the way blk-mq uses it, but it's definitely
not the point of the data structure. It's more of a cache-friendly
bitmap, or a sparse bitmap. `struct sbitmap`? `struct cbitmap`?

-- 
Omar