Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1478683 > unrolled thread

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

Back to article view | Back to linux.kernel

Contents

  [PATCH v2 0/5] blk-mq: abstract tag allocation out into scale_bitmap library Omar Sandoval <osandov@osandov.com> - 2016-09-08 01:50 +0200
    [PATCH v2 4/5] scale_bitmap: push alloc policy into scale_bitmap_queue Omar Sandoval <osandov@osandov.com> - 2016-09-08 01:50 +0200
    Re: [PATCH v2 1/5] blk-mq: abstract tag allocation out into  scale_bitmap library Omar Sandoval <osandov@osandov.com> - 2016-09-08 02:40 +0200
      Re: [PATCH v2 1/5] blk-mq: abstract tag allocation out into  scale_bitmap library Omar Sandoval <osandov@osandov.com> - 2016-09-08 20:20 +0200

#1478683 — [PATCH v2 0/5] blk-mq: abstract tag allocation out into scale_bitmap library

From: Omar Sandoval <osandov@fb.com>

Here's v2 of the patch making blk-mq's scalable bitmaps a generic
library, now blown up into 5 patches. v1 is here [1].

Changes since v1:

- Return -EINVAL instead of BUG_ON() if an invalid shift is passed to
  the initialization functions.
- Rename last_cache to alloc_hint.
- Split the wait queue allocation change into a separate patch. Patch 1
  should now be a no-op.
- Add patches 3 and 4 to make the API cleaner by pushing some context
  from the blk-mq data structures into the common scale_bitmap code.
- Add patch 5 to randomize the allocation hint on initialization like
  was intended originally for blk-mq.

I ran some fio jobs on top of null-blk and verified that there was no
performance impact from patches 1-4. Patch 5 is a slight win, although I
couldn't come up with a benchmark where the tag allocation is enough of
a bottleneck to see huge benefits. My synthetic test module [2], which
does the scale_bitmap operations directly, shows much better results.

This survived a quick run of xfstests and a battery of benchmarks.
Applies to 4.8-rc5.

Thanks!

1: http://marc.info/?l=linux-block&m=147251402805405&w=2
2: https://github.com/osandov/osandov-linux/blob/master/modules/scale_bitmap_benchmark/scale_bitmap_benchmark.c

Omar Sandoval (5):
  blk-mq: abstract tag allocation out into scale_bitmap library
  scale_bitmap: allocate wait queues on a specific node
  scale_bitmap: push per-cpu last_tag into scale_bitmap_queue
  scale_bitmap: push alloc policy into scale_bitmap_queue
  scale_bitmap: randomize initial last_cache values

 MAINTAINERS                  |   1 +
 block/Kconfig                |   1 +
 block/blk-mq-tag.c           | 504 ++++++++++---------------------------------
 block/blk-mq-tag.h           |  42 ++--
 block/blk-mq.c               | 115 +++-------
 block/blk-mq.h               |  11 -
 include/linux/blk-mq.h       |   9 +-
 include/linux/scale_bitmap.h | 390 +++++++++++++++++++++++++++++++++
 lib/Kconfig                  |   3 +
 lib/Makefile                 |   2 +
 lib/scale_bitmap.c           | 325 ++++++++++++++++++++++++++++
 11 files changed, 887 insertions(+), 516 deletions(-)
 create mode 100644 include/linux/scale_bitmap.h
 create mode 100644 lib/scale_bitmap.c

-- 
2.9.3

[toc] | [next] | [standalone]

#1478684 — [PATCH v2 4/5] scale_bitmap: push alloc policy into scale_bitmap_queue

From: Omar Sandoval <osandov@fb.com>

Again, there's no point in passing this in every time. Make it part of
`struct scale_bitmap_queue` and clean up the API.

Signed-off-by: Omar Sandoval <osandov@fb.com>
---
 block/blk-mq-tag.c           | 33 +++++++++++++++------------------
 block/blk-mq-tag.h           |  1 -
 include/linux/scale_bitmap.h | 24 +++++++++++++-----------
 lib/scale_bitmap.c           | 10 ++++++----
 4 files changed, 34 insertions(+), 34 deletions(-)

diff --git a/block/blk-mq-tag.c b/block/blk-mq-tag.c
index cc1941b..4dff92c 100644
--- a/block/blk-mq-tag.c
+++ b/block/blk-mq-tag.c
@@ -91,14 +91,11 @@ static inline bool hctx_may_queue(struct blk_mq_hw_ctx *hctx,
 	return atomic_read(&hctx->nr_active) < depth;
 }
 
-#define BT_ALLOC_RR(tags) (tags->alloc_policy == BLK_TAG_ALLOC_RR)
-
-static int __bt_get(struct blk_mq_hw_ctx *hctx, struct scale_bitmap_queue *bt,
-		    struct blk_mq_tags *tags)
+static int __bt_get(struct blk_mq_hw_ctx *hctx, struct scale_bitmap_queue *bt)
 {
 	if (!hctx_may_queue(hctx, bt))
 		return -1;
-	return __scale_bitmap_queue_get(bt, BT_ALLOC_RR(tags));
+	return __scale_bitmap_queue_get(bt);
 }
 
 static int bt_get(struct blk_mq_alloc_data *data, struct scale_bitmap_queue *bt,
@@ -108,7 +105,7 @@ static int bt_get(struct blk_mq_alloc_data *data, struct scale_bitmap_queue *bt,
 	DEFINE_WAIT(wait);
 	int tag;
 
-	tag = __bt_get(hctx, bt, tags);
+	tag = __bt_get(hctx, bt);
 	if (tag != -1)
 		return tag;
 
@@ -119,7 +116,7 @@ static int bt_get(struct blk_mq_alloc_data *data, struct scale_bitmap_queue *bt,
 	do {
 		prepare_to_wait(&ws->wait, &wait, TASK_UNINTERRUPTIBLE);
 
-		tag = __bt_get(hctx, bt, tags);
+		tag = __bt_get(hctx, bt);
 		if (tag != -1)
 			break;
 
@@ -136,7 +133,7 @@ static int bt_get(struct blk_mq_alloc_data *data, struct scale_bitmap_queue *bt,
 		 * Retry tag allocation after running the hardware queue,
 		 * as running the queue may also have found completions.
 		 */
-		tag = __bt_get(hctx, bt, tags);
+		tag = __bt_get(hctx, bt);
 		if (tag != -1)
 			break;
 
@@ -206,12 +203,10 @@ void blk_mq_put_tag(struct blk_mq_hw_ctx *hctx, struct blk_mq_ctx *ctx,
 		const int real_tag = tag - tags->nr_reserved_tags;
 
 		BUG_ON(real_tag >= tags->nr_tags);
-		scale_bitmap_queue_clear(&tags->bitmap_tags, real_tag,
-					 BT_ALLOC_RR(tags), ctx->cpu);
+		scale_bitmap_queue_clear(&tags->bitmap_tags, real_tag, ctx->cpu);
 	} else {
 		BUG_ON(tag >= tags->nr_reserved_tags);
-		scale_bitmap_queue_clear(&tags->breserved_tags, tag,
-					 BT_ALLOC_RR(tags), ctx->cpu);
+		scale_bitmap_queue_clear(&tags->breserved_tags, tag, ctx->cpu);
 	}
 }
 
@@ -366,21 +361,23 @@ static unsigned int bt_unused_tags(const struct scale_bitmap_queue *bt)
 	return bt->map.depth - scale_bitmap_weight(&bt->map);
 }
 
-static int bt_alloc(struct scale_bitmap_queue *bt, unsigned int depth, int node)
+static int bt_alloc(struct scale_bitmap_queue *bt, unsigned int depth,
+		    bool round_robin, int node)
 {
-	return scale_bitmap_queue_init_node(bt, depth, -1, GFP_KERNEL, node);
+	return scale_bitmap_queue_init_node(bt, depth, -1, round_robin,
+					    GFP_KERNEL, node);
 }
 
 static struct blk_mq_tags *blk_mq_init_bitmap_tags(struct blk_mq_tags *tags,
 						   int node, int alloc_policy)
 {
 	unsigned int depth = tags->nr_tags - tags->nr_reserved_tags;
+	bool round_robin = alloc_policy == BLK_TAG_ALLOC_RR;
 
-	tags->alloc_policy = alloc_policy;
-
-	if (bt_alloc(&tags->bitmap_tags, depth, node))
+	if (bt_alloc(&tags->bitmap_tags, depth, round_robin, node))
 		goto free_tags;
-	if (bt_alloc(&tags->breserved_tags, tags->nr_reserved_tags, node))
+	if (bt_alloc(&tags->breserved_tags, tags->nr_reserved_tags, round_robin,
+		     node))
 		goto free_bitmap_tags;
 
 	return tags;
diff --git a/block/blk-mq-tag.h b/block/blk-mq-tag.h
index d52c286..e6fc179c 100644
--- a/block/blk-mq-tag.h
+++ b/block/blk-mq-tag.h
@@ -18,7 +18,6 @@ struct blk_mq_tags {
 	struct request **rqs;
 	struct list_head page_list;
 
-	int alloc_policy;
 	cpumask_var_t cpumask;
 };
 
diff --git a/include/linux/scale_bitmap.h b/include/linux/scale_bitmap.h
index 49824c1..b83db63 100644
--- a/include/linux/scale_bitmap.h
+++ b/include/linux/scale_bitmap.h
@@ -122,6 +122,11 @@ struct scale_bitmap_queue {
 	 * @ws: Wait queues.
 	 */
 	struct sbq_wait_state *ws;
+
+	/**
+	 * @round_robin: Allocate bits in strict round-robin order.
+	 */
+	bool round_robin;
 };
 
 /**
@@ -270,14 +275,15 @@ unsigned int scale_bitmap_weight(const struct scale_bitmap *bitmap);
  * @sbq: Bitmap queue to initialize.
  * @depth: See scale_bitmap_init_node().
  * @shift: See scale_bitmap_init_node().
+ * @round_robin: See scale_bitmap_get().
  * @flags: Allocation flags.
  * @node: Memory node to allocate on.
  *
  * Return: Zero on success or negative errno on failure.
  */
 int scale_bitmap_queue_init_node(struct scale_bitmap_queue *sbq,
-				 unsigned int depth, int shift, gfp_t flags,
-				 int node);
+				 unsigned int depth, int shift,
+				 bool round_robin, gfp_t flags, int node);
 
 /**
  * scale_bitmap_queue_free() - Free memory used by a &struct scale_bitmap_queue.
@@ -307,34 +313,31 @@ void scale_bitmap_queue_resize(struct scale_bitmap_queue *sbq,
  * __scale_bitmap_queue_get() - Try to allocate a free bit from a &struct
  * scale_bitmap_queue with preemption already disabled.
  * @sbq: Bitmap queue to allocate from.
- * @round_robin: See scale_bitmap_get().
  *
  * Return: Non-negative allocated bit number if successful, -1 otherwise.
  */
-static inline int __scale_bitmap_queue_get(struct scale_bitmap_queue *sbq,
-					   bool round_robin)
+static inline int __scale_bitmap_queue_get(struct scale_bitmap_queue *sbq)
 {
 	return scale_bitmap_get(&sbq->map, this_cpu_ptr(sbq->alloc_hint),
-				round_robin);
+				sbq->round_robin);
 }
 
 /**
  * scale_bitmap_queue_get() - Try to allocate a free bit from a &struct
  * scale_bitmap_queue.
  * @sbq: Bitmap queue to allocate from.
- * @round_robin: See scale_bitmap_get().
  * @cpu: Output parameter; will contain the CPU we ran on (e.g., to be passed to
  *       scale_bitmap_queue_clear()).
  *
  * Return: Non-negative allocated bit number if successful, -1 otherwise.
  */
 static inline int scale_bitmap_queue_get(struct scale_bitmap_queue *sbq,
-					 bool round_robin, unsigned int *cpu)
+					 unsigned int *cpu)
 {
 	int ret;
 
 	*cpu = get_cpu();
-	ret = __scale_bitmap_queue_get(sbq, round_robin);
+	ret = __scale_bitmap_queue_get(sbq);
 	put_cpu();
 	return ret;
 }
@@ -344,11 +347,10 @@ static inline int scale_bitmap_queue_get(struct scale_bitmap_queue *sbq,
  * &struct scale_bitmap_queue.
  * @sbq: Bitmap to free from.
  * @nr: Bit number to free.
- * @round_robin: See scale_bitmap_get().
  * @cpu: CPU the bit was allocated on.
  */
 void scale_bitmap_queue_clear(struct scale_bitmap_queue *sbq, unsigned int nr,
-			      bool round_robin, unsigned int cpu);
+			      unsigned int cpu);
 
 static inline int sbq_index_inc(int index)
 {
diff --git a/lib/scale_bitmap.c b/lib/scale_bitmap.c
index 12fee62..8abe2cd 100644
--- a/lib/scale_bitmap.c
+++ b/lib/scale_bitmap.c
@@ -196,8 +196,8 @@ unsigned int scale_bitmap_weight(const struct scale_bitmap *bitmap)
 EXPORT_SYMBOL_GPL(scale_bitmap_weight);
 
 int scale_bitmap_queue_init_node(struct scale_bitmap_queue *sbq,
-				 unsigned int depth, int shift, gfp_t flags,
-				 int node)
+				 unsigned int depth, int shift,
+				 bool round_robin, gfp_t flags, int node)
 {
 	int ret;
 	int i;
@@ -229,6 +229,8 @@ int scale_bitmap_queue_init_node(struct scale_bitmap_queue *sbq,
 		init_waitqueue_head(&sbq->ws[i].wait);
 		atomic_set(&sbq->ws[i].wait_cnt, sbq->wake_batch);
 	}
+
+	sbq->round_robin = round_robin;
 	return 0;
 }
 EXPORT_SYMBOL_GPL(scale_bitmap_queue_init_node);
@@ -267,7 +269,7 @@ static struct sbq_wait_state *sbq_wake_ptr(struct scale_bitmap_queue *sbq)
 }
 
 void scale_bitmap_queue_clear(struct scale_bitmap_queue *sbq, unsigned int nr,
-			      bool round_robin, unsigned int cpu)
+			      unsigned int cpu)
 {
 	struct sbq_wait_state *ws;
 	int wait_cnt;
@@ -291,7 +293,7 @@ void scale_bitmap_queue_clear(struct scale_bitmap_queue *sbq, unsigned int nr,
 	}
 
 update_cache:
-	if (likely(!round_robin))
+	if (likely(!sbq->round_robin))
 		*per_cpu_ptr(sbq->alloc_hint, cpu) = nr;
 }
 EXPORT_SYMBOL_GPL(scale_bitmap_queue_clear);
-- 
2.9.3

[toc] | [prev] | [next] | [standalone]

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

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

[toc] | [prev] | [next] | [standalone]

#1479426 — 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@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`?
> > 
> > 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

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web