linux-kernel - Re: [PATCH v2 1/5] blk-mq: abstract tag allocation out into scale

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20160908181640.GA30638@vader.DHCP.thefacebook.com>
Date:   Thu, 8 Sep 2016 11:16:40 -0700
From:   Omar Sandoval <osandov@...ndov.com>
To:     Jens Axboe <axboe@...com>
Cc:     Alexei Starovoitov <ast@...com>, linux-block@...r.kernel.org,
        linux-kernel@...r.kernel.org, kernel-team@...com
Subject: Re: [PATCH v2 1/5] blk-mq: abstract tag allocation out into
 scale_bitmap library

On Thu, Sep 08, 2016 at 10:11:58AM -0600, Jens Axboe wrote:
> On 09/07/2016 07:12 PM, Alexei Starovoitov wrote:
> > On 9/7/16 5:38 PM, Omar Sandoval wrote:
> > > 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@...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@...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`?
> > 
> > yeah. naming is hard.
> > I think the name ideally should indicate how this bitmap
> > is different from array of bits that is already covered by
> > primitives in bitmap.h
> > Is it because the user can wait on the bit or because it's
> > smp aware? sort of percpu? I think that's the main trick how
> > it achieves good concurrent set/get access, right?
> > struct pcpu_bitmap ?
> > struct sbitmap is fine too.
> 
> It's not a true percpu bitmap. Rather it's a sparse bitmap, that
> provides some nice cache behavior through the nature of the sparseness.
> The percpu hinting helps with that. sbitmap might work, S for scale
> and/or sparse.
> 
> No name is going to convey what is special about it, but luckily Omar
> did a great job documenting it while pulling it out of blk-mq-tag. So
> I'm fine with just calling it sbitmap. I'll be pronouncing it like
> "spitmap".

"spitmap" it is :) I'll also do scale_bitmap_queue -> sbitmap_queue
unless anyone has a better idea.

-- 
Omar