percpu_ida: Take into account CPU topology when stealing tags

But other systems (more dense?) showed increased cache-hit rate up to 20%, i.e. this one:

Quoted 2 lines · Alexander Gordeev

But other systems (more dense?) showed increased cache-hit rate up to 20%, i.e. this one:

Hello Gentlemen,

Any feedback on this?

Quoted 4 lines · Alexander Gordeev

Quoted 2 lines · Alexander Gordeev

But other systems (more dense?) showed increased cache-hit rate up to 20%, i.e. this one:

Quoted 3 lines

Hello Gentlemen,

Any feedback on this?

Sorry for dropping the ball on this. Improvements wrt when to steal, how much, and from whom are sorely needed in percpu_ida. I'll do a bench with this on a system that currently falls apart with it.

Hello,

This series is against 3.14.0-rc7.

It is amied to further improve 'percpu_ida' tags locality by taking into account system's CPU topology when stealing tags. That is try to steal from a CPU which is 'closest' to the stealing one.

I would not bother to post this, since on several system the change did not show any improvement, i.e. on such one:

Quoted 9 lines · Jens Axboe

Quoted 7 lines · Alexander Gordeev

Quoted 2 lines · Alexander Gordeev

But other systems (more dense?) showed increased cache-hit rate up to 20%, i.e. this one:

Hello Gentlemen,

Any feedback on this?

Quoted 3 lines

Sorry for dropping the ball on this. Improvements wrt when to steal, how much, and from whom are sorely needed in percpu_ida. I'll do a bench with this on a system that currently falls apart with it.

Ran some quick numbers with three kernels:

stock 3.15-rc2
limit 3.15-rc2 + steal limit patch (attached)

Hi Jens,

Quoted 10 lines · Jens Axboe

Quoted 9 lines · Jens Axboe

Quoted 7 lines · Alexander Gordeev

Quoted 2 lines · Alexander Gordeev

But other systems (more dense?) showed increased cache-hit rate up to 20%, i.e. this one:

Hello Gentlemen,

Any feedback on this?

Quoted 8 lines

Quoted 3 lines

Sorry for dropping the ball on this. Improvements wrt when to steal, how much, and from whom are sorely needed in percpu_ida. I'll do a bench with this on a system that currently falls apart with it.

Ran some quick numbers with three kernels:

stock 3.15-rc2
limit 3.15-rc2 + steal limit patch (attached)

I am thinking/working on this sort of improving too, but my idea is to compute tags->nr_max_cache by below:

                    nr_tags / hctx->max_nr_ctx

hctx->max_nr_ctx means the max sw queues mapped to the hw queue, which need to be introduced in the approach, actually, the value should represent the CPU topology info.

It is a bit complicated to compute hctx->max_nr_ctx because we need to take account into CPU hotplug and probable user-defined mapping callback.

If user-defined mapping callback needn't to be considered, the hctx->max_nr_ctx can be figured out before mapping sw queue in blk_mq_init_queue() by supposing each CPU is online first, once it is done, the map for offline CPU is cleared, then start to call blk_mq_map_swqueue().

In my null_blk test on a quad core SMP VM:

- 4 hw queue
- timer mode

With the above approach, tag allocation from local CPU can be improved from:

         5%   -> 50% for boot CPU
         30% -> 90% for non-boot CPU.

If no one objects the idea, I'd like to post a patch for review.

Quoted 8 lines · Ming Lei

In my null_blk test on a quad core SMP VM:

- 4 hw queue
- timer mode

With the above approach, tag allocation from local CPU can be improved from:

Quoted 4 lines

         5%   -> 50% for boot CPU
         30% -> 90% for non-boot CPU.

If no one objects the idea, I'd like to post a patch for review.

Sent it out, that can't hurt. I'll take a look at it, and give it a test spin as well.

Hi Jens,

Quoted 17 lines · Jens Axboe

Quoted 12 lines · Ming Lei

In my null_blk test on a quad core SMP VM:

- 4 hw queue
- timer mode

With the above approach, tag allocation from local CPU can be improved from:

         5%   -> 50% for boot CPU
         30% -> 90% for non-boot CPU.

If no one objects the idea, I'd like to post a patch for review.

Quoted 2 lines

Sent it out, that can't hurt. I'll take a look at it, and give it a test spin as well.

I have sent out the patch in below link, and appreciate much you will take a look at it.

      marc.info/?l=linux-kernel&m=139826944613225&w=2

On 04/25/2014 03:10 AM, Ming Lei wrote:

Sorry, I did run it the other day. It has little to no effect here, but that's mostly because there's so much other crap going on in there. The most effective way to currently make it work better, is just to ensure the caching pool is of a sane size.

From percpu_ida view, it is easy to observe it can improve

I've got an alternative tagging scheme that I think would be useful for the cases where the tag space to cpu ratio isn't big enough. So I think we'll retain percpu_ida for the cases where it can cache enough, and punt to an alternative scheme when not.

That doesn't mean we should not improve percpu_ida. There's quite a bit of low hanging fruit in there.

Hi Jens,

Quoted 6 lines · Jens Axboe

On 04/25/2014 03:10 AM, Ming Lei wrote:

Sorry, I did run it the other day. It has little to no effect here, but that's mostly because there's so much other crap going on in there. The most effective way to currently make it work better, is just to ensure the caching pool is of a sane size.

Yes, that is just what the patch is doing, :-)

From percpu_ida view, it is easy to observe it can improve allocation performance. I have several patches to export these information by sysfs for monitoring percpu_ida performance.

Quoted 4 lines

I've got an alternative tagging scheme that I think would be useful for the cases where the tag space to cpu ratio isn't big enough. So I think we'll retain percpu_ida for the cases where it can cache enough, and punt to an alternative scheme when not.

OK, care to comment on the patch or the idea of setting percpu cache size as (nr_tags / hctx->nr_ctx)?

Quoted 2 lines

That doesn't mean we should not improve percpu_ida. There's quite a bit of low hanging fruit in there.

IMO percpu_max_size in percpu_ida is very important for the performance, and it might need to adjust dynamically according to the percpu allocation loading, but it is far more complicated to implement. And it might be the simplest way to fix the parameter before percpu_ida_init().

Quoted 13 lines · Ming Lei

Hi Jens,

Quoted 7 lines · Jens Axboe

On 04/25/2014 03:10 AM, Ming Lei wrote:

Sorry, I did run it the other day. It has little to no effect here, but that's mostly because there's so much other crap going on in there. The most effective way to currently make it work better, is just to ensure the caching pool is of a sane size.

Quoted 1 line

Yes, that is just what the patch is doing, :-)

But it's not enough.

For instance, my test case, it's 255 tags and 64 CPUs. We end up in cross-cpu spinlock nightmare mode.

Quoted 6 lines

From percpu_ida view, it is easy to observe it can improve allocation performance. I have several patches to export these information by sysfs for monitoring percpu_ida performance.

Sounds good!

Quoted 10 lines

Quoted 6 lines

I've got an alternative tagging scheme that I think would be useful for the cases where the tag space to cpu ratio isn't big enough. So I think we'll retain percpu_ida for the cases where it can cache enough, and punt to an alternative scheme when not.

OK, care to comment on the patch or the idea of setting percpu cache size as (nr_tags / hctx->nr_ctx)?

I think it's a good idea. The problem is that for percpu_ida to be effective, you need a bigger cache than the 3 I'd get above. If that isn't the case, it performs poorly. I'm just not convinced the design can ever work in the realm of realistic queue depths.

Quoted 9 lines

Quoted 2 lines

That doesn't mean we should not improve percpu_ida. There's quite a bit of low hanging fruit in there.

IMO percpu_max_size in percpu_ida is very important for the performance, and it might need to adjust dynamically according to the percpu allocation loading, but it is far more complicated to implement. And it might be the simplest way to fix the parameter before percpu_ida_init().

That's what I did, essentially. Ensuring that the percpu_max_size is at least 8 makes it a whole lot better here. But still slower than a regular simple bitmap, which makes me sad. A fairly straight forward cmpxchg based scheme I tested here is around 20% faster than the bitmap approach on a basic desktop machine, and around 35% faster on a 4-socket. Outside of NVMe, I can't think of cases where that approach would not be faster than percpu_ida. That means all of SCSI, basically, and the basic block drivers.

Quoted 14 lines · Jens Axboe

Quoted 13 lines · Ming Lei

Hi Jens,

Quoted 7 lines · Jens Axboe

On 04/25/2014 03:10 AM, Ming Lei wrote:

Sorry, I did run it the other day. It has little to no effect here, but that's mostly because there's so much other crap going on in there. The most effective way to currently make it work better, is just to ensure the caching pool is of a sane size.

Quoted 4 lines

Quoted 1 line

Yes, that is just what the patch is doing, :-)

But it's not enough.

Yes, the patch is only for cases of mutli hw queue and having offline CPUs existed.

Quoted 2 lines

For instance, my test case, it's 255 tags and 64 CPUs. We end up in cross-cpu spinlock nightmare mode.

IMO, the scaling problem for the above case might be caused by either current percpu ida design or blk-mq's usage on it.

One of problems in blk-mq is that the 'set->queue_depth' parameter from driver isn't scalable, maybe it is reasonable to introduce 'set->min_percpu_cache', then ' tags->nr_max_cache' can be computed as below:

     max(nr_tags / hctx->nr_ctx, set->min_percpu_cache)

Another problem in blk-mq is that if it can be improved by computing tags->nr_max_cache as 'nr_tags / hctx->nr_ctx' ? The current approach should be based on that there are parallel I/O activity on each CPU, but I am wondering if it is the common case in reality. Suppose there are N(N << online CPUs in big machine) concurrent I/O on some of CPUs, percpu cache can be increased a lot by (nr_tags / N).

Quoted 7 lines

That's what I did, essentially. Ensuring that the percpu_max_size is at least 8 makes it a whole lot better here. But still slower than a regular simple bitmap, which makes me sad. A fairly straight forward cmpxchg based scheme I tested here is around 20% faster than the bitmap approach on a basic desktop machine, and around 35% faster on a 4-socket. Outside of NVMe, I can't think of cases where that approach would not be faster than percpu_ida. That means all of SCSI, basically, and the basic block drivers.

If percpu_ida wants to beat bitmap allocation, the local cache hit ratio has to keep high, in my tests, it can be got with enough local cache size.

Quoted 23 lines · Ming Lei

Quoted 14 lines · Jens Axboe

Quoted 13 lines · Ming Lei

Hi Jens,

Quoted 7 lines · Jens Axboe

On 04/25/2014 03:10 AM, Ming Lei wrote:

Sorry, I did run it the other day. It has little to no effect here, but that's mostly because there's so much other crap going on in there. The most effective way to currently make it work better, is just to ensure the caching pool is of a sane size.

Quoted 4 lines

Quoted 1 line

Yes, that is just what the patch is doing, :-)

But it's not enough.

Yes, the patch is only for cases of mutli hw queue and having offline CPUs existed.

Quoted 6 lines

Quoted 2 lines

For instance, my test case, it's 255 tags and 64 CPUs. We end up in cross-cpu spinlock nightmare mode.

IMO, the scaling problem for the above case might be caused by either current percpu ida design or blk-mq's usage on it.

That is pretty much my claim, yes. Basically I don't think per-cpu tag caching is ever going to be the best solution for the combination of modern machines and the hardware that is out there (limited tags).

Quoted 7 lines

One of problems in blk-mq is that the 'set->queue_depth' parameter from driver isn't scalable, maybe it is reasonable to introduce 'set->min_percpu_cache', then ' tags->nr_max_cache' can be computed as below:

     max(nr_tags / hctx->nr_ctx, set->min_percpu_cache)

Quoted 7 lines

Another problem in blk-mq is that if it can be improved by computing tags->nr_max_cache as 'nr_tags / hctx->nr_ctx' ? The current approach should be based on that there are parallel I/O activity on each CPU, but I am wondering if it is the common case in reality. Suppose there are N(N << online CPUs in big machine) concurrent I/O on some of CPUs, percpu cache can be increased a lot by (nr_tags / N).

That would certainly help the common case, but it'd still be slow for the cases where you DO have IO from lots of sources. If we consider

tags the minimum for balanced performance, than that doesn't take a whole lot of CPUs to spread out the tag space. Just looking at a case today on SCSI with 62 tags. AHCI and friends have 31 tags. Even for the "bigger" case of the Micron card, you still only have 255 active tags. And we probably want to split that up into groups of 32, making the problem even worse.

I've not had time to revisit/finish them, but you should definitely clean up the percpu_ida stuff and reduce existing contention before going overboard.

Quoted 3 lines · Peter Zijlstra

I've not had time to revisit/finish them, but you should definitely clean up the percpu_ida stuff and reduce existing contention before going overboard.

Hi Peter,

I tried to combine your series into a single patch against 3.15-rc3.

I hope, it looks like you intended and my comments in follow-up message make sense.

Thanks!

lib/percpu_ida.c +26 -12

index 93d145e..14f5151 100644
@@ -51,6 +51,15 @@ static inline void move_tags(unsigned *dst, unsigned *dst_nr,
 	*dst_nr += nr;
 }
 
+static inline void double_lock(spinlock_t *l1, spinlock_t *l2)
+{
+	if (l1 > l2)
+		swap(l1, l2);
+
+	spin_lock(l1);
+	spin_lock_nested(l2, SINGLE_DEPTH_NESTING);
+}
+
 /*
  * Try to steal tags from a remote cpu's percpu freelist.
  *

@@ -84,7 +93,7 @@ static inline void steal_tags(struct percpu_ida *pool,
 		if (remote == tags)
 			continue;
 
-		spin_lock(&remote->lock);
+		double_lock(&tags->lock, &remote->lock);
 
 		if (remote->nr_free) {
 			memcpy(tags->freelist,

@@ -96,36 +105,81 @@ static inline void steal_tags(struct percpu_ida *pool,
 		}
 
 		spin_unlock(&remote->lock);
+		spin_unlock(&tags->lock);
 
 		if (tags->nr_free)
 			break;
 	}
 }
 
-/*
- * Pop up to IDA_PCPU_BATCH_MOVE IDs off the global freelist, and push them onto
- * our percpu freelist:
- */
-static inline void alloc_global_tags(struct percpu_ida *pool,
-				     struct percpu_ida_cpu *tags)
+static inline unsigned alloc_local_tag(struct percpu_ida_cpu *tags)
 {
-	move_tags(tags->freelist, &tags->nr_free,
-		  pool->freelist, &pool->nr_free,
-		  min(pool->nr_free, pool->percpu_batch_size));
+	int tag = -ENOSPC;
+
+	spin_lock(&tags->lock);
+	if (tags->nr_free)
+		tag = tags->freelist[--tags->nr_free];
+	spin_unlock(&tags->lock);
+
+	return tag;
 }
 
-static inline unsigned alloc_local_tag(struct percpu_ida_cpu *tags)
+static inline int alloc_local_tag(struct percpu_ida *pool)
 {
+	struct percpu_ida_cpu *tags;
+	unsigned long flags;
 	int tag = -ENOSPC;
 
+	local_irq_save(flags);
+	tags = this_cpu_ptr(pool->tag_cpu);
 	spin_lock(&tags->lock);
 	if (tags->nr_free)
 		tag = tags->freelist[--tags->nr_free];
-	spin_unlock(&tags->lock);
+	spin_unlock_irqrestore(&tags->lock, flags);
 
 	return tag;

lib/percpu_ida.c +57 -72

+	if (!tags->nr_free)
+		steal_tags(pool, tags);
+
+	if (tags->nr_free) {
+		spin_lock(&tags->lock);
+		if (tags->nr_free) {
+	 		tag = tags->freelist[--tags->nr_free];
+			if (tags->nr_free) {
+				cpumask_set_cpu(smp_processor_id(),
+						&pool->cpus_have_tags);
+			}
+		}
+		spin_unlock(&tags->lock);
+	}
+
+	local_irq_restore(flags);
+ 
+ 	return tag;
+}
+
 /**
  * percpu_ida_alloc - allocate a tag
  * @pool: pool to allocate from

@@ -146,66 +200,26 @@ static inline unsigned alloc_local_tag(struct percpu_ida_cpu *tags)
  */
 int percpu_ida_alloc(struct percpu_ida *pool, int state)
 {
-	DEFINE_WAIT(wait);
-	struct percpu_ida_cpu *tags;
-	unsigned long flags;
-	int tag;
-
-	local_irq_save(flags);
-	tags = this_cpu_ptr(pool->tag_cpu);
-
-	/* Fastpath */
-	tag = alloc_local_tag(tags);
-	if (likely(tag >= 0)) {
-		local_irq_restore(flags);
-		return tag;
-	}
-
-	while (1) {
-		spin_lock(&pool->lock);
-
-		/*
-		 * prepare_to_wait() must come before steal_tags(), in case
-		 * percpu_ida_free() on another cpu flips a bit in
-		 * cpus_have_tags
-		 *
-		 * global lock held and irqs disabled, don't need percpu lock
-		 */
-		if (state != TASK_RUNNING)
-			prepare_to_wait(&pool->wait, &wait, state);
-
-		if (!tags->nr_free)
-			alloc_global_tags(pool, tags);
-		if (!tags->nr_free)
-			steal_tags(pool, tags);
-
-		if (tags->nr_free) {
-			tag = tags->freelist[--tags->nr_free];
-			if (tags->nr_free)
-				cpumask_set_cpu(smp_processor_id(),
-						&pool->cpus_have_tags);
-		}
-
-		spin_unlock(&pool->lock);
-		local_irq_restore(flags);
-
-		if (tag >= 0 || state == TASK_RUNNING)
-			break;
-
-		if (signal_pending_state(state, current)) {
-			tag = -ERESTARTSYS;
-			break;
-		}
-
-		schedule();
-
-		local_irq_save(flags);
-		tags = this_cpu_ptr(pool->tag_cpu);
-	}
-	if (state != TASK_RUNNING)
-		finish_wait(&pool->wait, &wait);
-
-	return tag;
+	int ret;
+
+	ret = alloc_local_tag(pool);
+	if (likely(ret >= 0))
+		return ret;
+
+	if (state != TASK_RUNNING) {
+		int tag;
+ 
+		ret = ___wait_event(pool->wait,
+				    (tag = alloc_global_tag(pool)) >= 0,
+				    state, 0, 0, schedule());
+ 
+		if (tag >= 0)
+			ret = tag;
+	} else {
+		ret = alloc_global_tag(pool);
+ 	}
+ 
+	return ret;
 }
 EXPORT_SYMBOL_GPL(percpu_ida_alloc);
 

@@ -239,12 +253,19 @@ void percpu_ida_free(struct percpu_ida *pool, unsigned tag)
 		wake_up(&pool->wait);
 	}
 
+	/*
+	 * No point in waking when 1 < n < max_size free, because steal_tags()
+	 * will assume max_size per set bit, having more free will not make it
+	 * more or less likely it will visit this cpu.
+	 */
+
 	if (nr_free == pool->percpu_max_size) {
 		spin_lock(&pool->lock);
 
 		/*
-		 * Global lock held and irqs disabled, don't need percpu
-		 * lock
+		 * Global lock held and irqs disabled, don't need percpu lock
+		 * because everybody accessing remote @tags will hold
+		 * pool->lock -- steal_tags().
 		 */
 		if (tags->nr_free == pool->percpu_max_size) {
 			move_tags(pool->freelist, &pool->nr_free,

@@ -344,33 +365,31 @@ EXPORT_SYMBOL_GPL(__percpu_ida_init);
 int percpu_ida_for_each_free(struct percpu_ida *pool, percpu_ida_cb fn,
 	void *data)
 {
-	unsigned long flags;
 	struct percpu_ida_cpu *remote;
-	unsigned cpu, i, err = 0;
+	unsigned long flags;
+	int cpu, i, err = 0;
 
-	local_irq_save(flags);
 	for_each_possible_cpu(cpu) {
 		remote = per_cpu_ptr(pool->tag_cpu, cpu);
-		spin_lock(&remote->lock);
+		spin_lock_irqsave(&remote->lock, flags);
 		for (i = 0; i < remote->nr_free; i++) {
 			err = fn(remote->freelist[i], data);
 			if (err)
 				break;
 		}
-		spin_unlock(&remote->lock);
+		spin_unlock_irqrestore(&remote->lock, flags);
 		if (err)
-			goto out;
+			return err;
 	}
 
-	spin_lock(&pool->lock);
+	spin_lock_irqsave(&pool->lock, flags);
 	for (i = 0; i < pool->nr_free; i++) {
 		err = fn(pool->freelist[i], data);
 		if (err)
 			break;
 	}
-	spin_unlock(&pool->lock);
-out:
-	local_irq_restore(flags);
+	spin_unlock_irqrestore(&pool->lock, flags);
+
 	return err;
 }
 EXPORT_SYMBOL_GPL(percpu_ida_for_each_free);

Quoted 26 lines · Ming Lei

Quoted 14 lines · Jens Axboe

Quoted 13 lines · Ming Lei

Hi Jens,

Quoted 7 lines · Jens Axboe

On 04/25/2014 03:10 AM, Ming Lei wrote:

Sorry, I did run it the other day. It has little to no effect here, but that's mostly because there's so much other crap going on in there. The most effective way to currently make it work better, is just to ensure the caching pool is of a sane size.

Quoted 4 lines

Quoted 1 line

Yes, that is just what the patch is doing, :-)

But it's not enough.

Yes, the patch is only for cases of mutli hw queue and having offline CPUs existed.

Quoted 2 lines

For instance, my test case, it's 255 tags and 64 CPUs. We end up in cross-cpu spinlock nightmare mode.

Quoted 3 lines

IMO, the scaling problem for the above case might be caused by either current percpu ida design or blk-mq's usage on it.

That is pretty much my claim, yes. Basically I don't think per-cpu tag caching is ever going to be the best solution for the combination of modern machines and the hardware that is out there (limited tags).

Quoted 27 lines · Jens Axboe

Quoted 26 lines · Ming Lei

Quoted 14 lines · Jens Axboe

Quoted 13 lines · Ming Lei

Hi Jens,

Quoted 7 lines · Jens Axboe

On 04/25/2014 03:10 AM, Ming Lei wrote:

Sorry, I did run it the other day. It has little to no effect here, but that's mostly because there's so much other crap going on in there. The most effective way to currently make it work better, is just to ensure the caching pool is of a sane size.

Quoted 4 lines

Quoted 1 line

Yes, that is just what the patch is doing, :-)

But it's not enough.

Yes, the patch is only for cases of mutli hw queue and having offline CPUs existed.

Quoted 2 lines

For instance, my test case, it's 255 tags and 64 CPUs. We end up in cross-cpu spinlock nightmare mode.

Quoted 7 lines

Quoted 3 lines

IMO, the scaling problem for the above case might be caused by either current percpu ida design or blk-mq's usage on it.

That is pretty much my claim, yes. Basically I don't think per-cpu tag caching is ever going to be the best solution for the combination of modern machines and the hardware that is out there (limited tags).

Sorry for not being more active in the discussion earlier, but anyways - I'm in 100% agreement with this.

Percpu freelists are _fundamentally_ only _useful_ when you don't need to be using all your available tags, because percpu sharding requires wasting your tag space. I could write a mathematical proof of this if I cared enough.

Otherwise what happens is on alloc failure you're touching all the other cachelines every single time and now you're bouncing _more_ cachelines than if you just had a single global freelist.

So yeah, for small tag spaces just use a single simple bit vector on a single cacheline.

BTW, Shaohua Li's patch d835502f3dacad1638d516ab156d66f0ba377cf5 that changed when steal_tags() runs was fundamentally wrong and broken in this respect, and should be reverted, whatever usage it was that was expecting to be able to allocate the entire tag space was the problem.

Quoted 43 lines · Kent Overstreet

Quoted 27 lines · Jens Axboe

Quoted 26 lines · Ming Lei

Quoted 14 lines · Jens Axboe

Quoted 13 lines · Ming Lei

Hi Jens,

Quoted 7 lines · Jens Axboe

On 04/25/2014 03:10 AM, Ming Lei wrote:

Sorry, I did run it the other day. It has little to no effect here, but that's mostly because there's so much other crap going on in there. The most effective way to currently make it work better, is just to ensure the caching pool is of a sane size.

Quoted 4 lines

Quoted 1 line

Yes, that is just what the patch is doing, :-)

But it's not enough.

Yes, the patch is only for cases of mutli hw queue and having offline CPUs existed.

Quoted 2 lines

For instance, my test case, it's 255 tags and 64 CPUs. We end up in cross-cpu spinlock nightmare mode.

Quoted 7 lines

Quoted 3 lines

IMO, the scaling problem for the above case might be caused by either current percpu ida design or blk-mq's usage on it.

That is pretty much my claim, yes. Basically I don't think per-cpu tag caching is ever going to be the best solution for the combination of modern machines and the hardware that is out there (limited tags).

Sorry for not being more active in the discussion earlier, but anyways - I'm in 100% agreement with this.

Percpu freelists are _fundamentally_ only _useful_ when you don't need to be using all your available tags, because percpu sharding requires wasting your tag space. I could write a mathematical proof of this if I cared enough.

Quoted 6 lines

Otherwise what happens is on alloc failure you're touching all the other cachelines every single time and now you're bouncing _more_ cachelines than if you just had a single global freelist.

So yeah, for small tag spaces just use a single simple bit vector on a single cacheline.

I've taken the consequence of this and implemented another tagging scheme that blk-mq will use if it deems that percpu_ida isn't going to be effective for the device being initialized. But I really hate to have both of them in there. Unfortunately I have no devices available that have a tag space that will justify using percu_ida, so comparisons are a bit hard at the moment. NVMe should change that, though, so decision will have to be deferred until that is tested.

Quoted 4 lines

BTW, Shaohua Li's patch d835502f3dacad1638d516ab156d66f0ba377cf5 that changed when steal_tags() runs was fundamentally wrong and broken in this respect, and should be reverted, whatever usage it was that was expecting to be able to allocate the entire tag space was the problem.

It's hard to blame Shaohua, and I helped push that. It was an attempt in making percpu_ida actually useful for what blk-mq needs it for, and being the primary user of it, it was definitely worth doing. A tagging scheme that requires the tag space to be effectively sparse/huge to be fast is not a good generic tagging algorithm.

Quoted 51 lines · Jens Axboe

Quoted 43 lines · Kent Overstreet

Quoted 27 lines · Jens Axboe

Quoted 26 lines · Ming Lei

Quoted 14 lines · Jens Axboe

Quoted 13 lines · Ming Lei

Hi Jens,

Quoted 7 lines · Jens Axboe

On 04/25/2014 03:10 AM, Ming Lei wrote:

Sorry, I did run it the other day. It has little to no effect here, but that's mostly because there's so much other crap going on in there. The most effective way to currently make it work better, is just to ensure the caching pool is of a sane size.

Quoted 4 lines

Quoted 1 line

Yes, that is just what the patch is doing, :-)

But it's not enough.

Yes, the patch is only for cases of mutli hw queue and having offline CPUs existed.

Quoted 2 lines

For instance, my test case, it's 255 tags and 64 CPUs. We end up in cross-cpu spinlock nightmare mode.

Quoted 7 lines

Quoted 3 lines

IMO, the scaling problem for the above case might be caused by either current percpu ida design or blk-mq's usage on it.

That is pretty much my claim, yes. Basically I don't think per-cpu tag caching is ever going to be the best solution for the combination of modern machines and the hardware that is out there (limited tags).

Sorry for not being more active in the discussion earlier, but anyways - I'm in 100% agreement with this.

Percpu freelists are _fundamentally_ only _useful_ when you don't need to be using all your available tags, because percpu sharding requires wasting your tag space. I could write a mathematical proof of this if I cared enough.

Quoted 6 lines

Otherwise what happens is on alloc failure you're touching all the other cachelines every single time and now you're bouncing _more_ cachelines than if you just had a single global freelist.

So yeah, for small tag spaces just use a single simple bit vector on a single cacheline.

Quoted 7 lines

I've taken the consequence of this and implemented another tagging scheme that blk-mq will use if it deems that percpu_ida isn't going to be effective for the device being initialized. But I really hate to have both of them in there. Unfortunately I have no devices available that have a tag space that will justify using percu_ida, so comparisons are a bit hard at the moment. NVMe should change that, though, so decision will have to be deferred until that is tested.

Yeah, I agree that is annoying. I've thought about the issue too though and I haven't been able to come up with any better ideas, myself.

A given driver probably should be able to always use one or the other though, so we shouldn't _need_ a runtime conditional because of this, though structuring the code that way might be more trouble than it's worth from my vague recollection of what blk-mq looks likee...

(I've actually been fighting with unrelated issues at a very similar layer of abstraction, it's quite annoying.).

Quoted 10 lines

Quoted 4 lines

BTW, Shaohua Li's patch d835502f3dacad1638d516ab156d66f0ba377cf5 that changed when steal_tags() runs was fundamentally wrong and broken in this respect, and should be reverted, whatever usage it was that was expecting to be able to allocate the entire tag space was the problem.

It's hard to blame Shaohua, and I helped push that. It was an attempt in making percpu_ida actually useful for what blk-mq needs it for, and being the primary user of it, it was definitely worth doing. A tagging scheme that requires the tag space to be effectively sparse/huge to be fast is not a good generic tagging algorithm.

Yeah it was definitely not an unreasonable attempt and it's probably my own fault for not speaking up louder at the time (I can't remember how much I commented at the time). Ah well, irritating problem space :)

I've taken the consequence of this and implemented another tagging scheme that blk-mq will use if it deems that percpu_ida isn't going to be effective for the device being initialized. But I really hate to have both of them in there. Unfortunately I have no devices available that have a tag space that will justify using percu_ida, so comparisons are a bit hard at the moment. NVMe should change that, though, so decision will have to be deferred until that is tested.

Quoted 8 lines · Jens Axboe

I've taken the consequence of this and implemented another tagging scheme that blk-mq will use if it deems that percpu_ida isn't going to be effective for the device being initialized. But I really hate to have both of them in there. Unfortunately I have no devices available that have a tag space that will justify using percu_ida, so comparisons are a bit hard at the moment. NVMe should change that, though, so decision will have to be deferred until that is tested.

At least for SCSI devices _tag space_ is plenty, it's just the we artifically limit our tag space to the queue depth to avoid having to track that one separately. In addition we also preallocaste a request for each tag, so even if we would track the queue depth separately we would waste a lot of memory.

Quoted 5 lines

At least for SCSI devices _tag space_ is plenty, it's just the we artifically limit our tag space to the queue depth to avoid having to track that one separately. In addition we also preallocaste a request for each tag, so even if we would track the queue depth separately we would waste a lot of memory.

In practice it comes out to the same, it's not feasible to run a much larger space and track on queue depth. So I don't think that changes the conclusion for SCSI.

Quoted 6 lines · Jens Axboe

Quoted 5 lines

At least for SCSI devices _tag space_ is plenty, it's just the we artifically limit our tag space to the queue depth to avoid having to track that one separately. In addition we also preallocaste a request for each tag, so even if we would track the queue depth separately we would waste a lot of memory.

Quoted 3 lines

In practice it comes out to the same, it's not feasible to run a much larger space and track on queue depth. So I don't think that changes the conclusion for SCSI.

Agreed. Just had to check if my smart ass hat still fits this morning..