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@xxxxxx>
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@xxxxxx>
---
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".
--
Jens Axboe
--
To unsubscribe from this list: send the line "unsubscribe linux-block" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
