by Peter Zijlstra

[permalink] [raw]

Subject: Re: [PATCH-v2 1/3] percpu_ida: Make percpu_ida_alloc + callers accept task state bitmask

2014-01-23 16:46:30

by Peter Zijlstra

[permalink] [raw]

2014-01-23 19:34:48

by Kent Overstreet

[permalink] [raw]

Subject: Re: [PATCH-v2 1/3] percpu_ida: Make percpu_ida_alloc + callers accept task state bitmask

On Thu, Jan 23, 2014 at 08:12:29PM +0100, Peter Zijlstra wrote:
> On Thu, Jan 23, 2014 at 10:40:04AM -0800, Nicholas A. Bellinger wrote:
> > On Wed, 2014-01-22 at 11:53 -0800, Nicholas A. Bellinger wrote:
> > > Hi Peter,
> > >
> > > Does this satisfy your questions..?
> > >
> > > Do you have any more concerns about TASK_RUNNING + prepare_to_wait()
> > > usage in percpu_ida_alloc() that need to be addressed before I can drop
> > > this series into target-pending/for-next to address the original bug..?
> > >
> >
> > Given the silence,
>
> You mean the silence in which I send a 4+ emails earlier today?
>
> > I'll assume your OK with the initial TASK_RUNNING +
> > prepare_to_wait() bit, right..?
>
> No, I would prefer not to do that. While it does work its awkward at
> best.

I do like the improvements, but personally, I really don't see anything wrong
with the initial patch and for backporting that really is what we should do -
this code _is_ subtle enough backporting our (your) improvements is not
something I'd want to do, having debugged this code when I first wrote it...

2014-01-23 19:36:16

by Nicholas A. Bellinger

[permalink] [raw]

Subject: Re: [PATCH-v2 1/3] percpu_ida: Make percpu_ida_alloc + callers accept task state bitmask

On Thu, 2014-01-23 at 11:31 -0800, Nicholas A. Bellinger wrote:
> On Thu, 2014-01-23 at 20:12 +0100, Peter Zijlstra wrote:
> > On Thu, Jan 23, 2014 at 10:40:04AM -0800, Nicholas A. Bellinger wrote:
> > > On Wed, 2014-01-22 at 11:53 -0800, Nicholas A. Bellinger wrote:
> > > > Hi Peter,
> > > >
> > > > Does this satisfy your questions..?
> > > >
> > > > Do you have any more concerns about TASK_RUNNING + prepare_to_wait()
> > > > usage in percpu_ida_alloc() that need to be addressed before I can drop
> > > > this series into target-pending/for-next to address the original bug..?
> > > >
> > >
> > > Given the silence,
> >
> > You mean the silence in which I send a 4+ emails earlier today?
> >
> > > I'll assume your OK with the initial TASK_RUNNING +
> > > prepare_to_wait() bit, right..?
> >
> > No, I would prefer not to do that. While it does work its awkward at
> > best.
>
> AFAICT, those changes don't address the original bug that the series was
> trying to address, allowing the percpu_ida_alloc() tag stealing slow
> path to be interrupted by a signal..
>
> Also, keep in mind this change needs to be backported to >= v3.12, which
> is why the percpu_ida changes have been kept to a minimum.
>

<A little too eager to SEND>

So would you prefer the following addition to the original bugfix
instead..?

diff --git a/lib/percpu_ida.c b/lib/percpu_ida.c
index a48ce2e..58b6714 100644
--- a/lib/percpu_ida.c
+++ b/lib/percpu_ida.c
@@ -174,7 +174,8 @@ int percpu_ida_alloc(struct percpu_ida *pool, int state)
*
* global lock held and irqs disabled, don't need percpu lock
*/
- prepare_to_wait(&pool->wait, &wait, state);
+ if (state != TASK_RUNNING)
+ prepare_to_wait(&pool->wait, &wait, state);

if (!tags->nr_free)
alloc_global_tags(pool, tags);
@@ -199,8 +200,9 @@ int percpu_ida_alloc(struct percpu_ida *pool, int state)
local_irq_save(flags);
tags = this_cpu_ptr(pool->tag_cpu);
}
+ if (state != TASK_RUNNING)
+ finish_wait(&pool->wait, &wait);

- finish_wait(&pool->wait, &wait);
return tag;
}
EXPORT_SYMBOL_GPL(percpu_ida_alloc);

2014-01-24 15:15:07

by Peter Zijlstra

[permalink] [raw]

Subject: Re: [PATCH-v2 1/3] percpu_ida: Make percpu_ida_alloc + callers accept task state bitmask

On Thu, Jan 23, 2014 at 11:38:24AM -0800, Nicholas A. Bellinger wrote:
> > AFAICT, those changes don't address the original bug that the series was
> > trying to address, allowing the percpu_ida_alloc() tag stealing slow
> > path to be interrupted by a signal..
> >
> > Also, keep in mind this change needs to be backported to >= v3.12, which
> > is why the percpu_ida changes have been kept to a minimum.

Well, the other option is to revert whatever caused the issue in the
first place :-)

I'm not much for making ugly fixes just because its easier to backport.

> <A little too eager to SEND>
>
> So would you prefer the following addition to the original bugfix
> instead..?

I'll make a right old mess out of percpu_ida.c, but yeah.

> diff --git a/lib/percpu_ida.c b/lib/percpu_ida.c
> index a48ce2e..58b6714 100644
> --- a/lib/percpu_ida.c
> +++ b/lib/percpu_ida.c
> @@ -174,7 +174,8 @@ int percpu_ida_alloc(struct percpu_ida *pool, int state)
> *
> * global lock held and irqs disabled, don't need percpu lock
> */
> - prepare_to_wait(&pool->wait, &wait, state);
> + if (state != TASK_RUNNING)
> + prepare_to_wait(&pool->wait, &wait, state);
>
> if (!tags->nr_free)
> alloc_global_tags(pool, tags);
> @@ -199,8 +200,9 @@ int percpu_ida_alloc(struct percpu_ida *pool, int state)
> local_irq_save(flags);
> tags = this_cpu_ptr(pool->tag_cpu);
> }
> + if (state != TASK_RUNNING)
> + finish_wait(&pool->wait, &wait);
>
> - finish_wait(&pool->wait, &wait);
> return tag;
> }
> EXPORT_SYMBOL_GPL(percpu_ida_alloc);
>
>

2014-01-25 06:31:46

by Nicholas A. Bellinger

[permalink] [raw]

Subject: Re: [PATCH-v2 1/3] percpu_ida: Make percpu_ida_alloc + callers accept task state bitmask

On Fri, 2014-01-24 at 16:14 +0100, Peter Zijlstra wrote:
> On Thu, Jan 23, 2014 at 11:38:24AM -0800, Nicholas A. Bellinger wrote:
> > > AFAICT, those changes don't address the original bug that the series was
> > > trying to address, allowing the percpu_ida_alloc() tag stealing slow
> > > path to be interrupted by a signal..
> > >
> > > Also, keep in mind this change needs to be backported to >= v3.12, which
> > > is why the percpu_ida changes have been kept to a minimum.
>
> Well, the other option is to revert whatever caused the issue in the
> first place :-)
>
> I'm not much for making ugly fixes just because its easier to backport.
>

Me either, but given Kent's comment on subtle issues for larger
improvements in the tag stealing slow path, it's the right approach for
addressing a bug in stable code.

Also, I'd also prefer to avoid introducing new issues for blk-mq in the
first round of stable code, give the amount of testing it's already
undergone with percpu_ida for v3.13.

> > <A little too eager to SEND>
> >
> > So would you prefer the following addition to the original bugfix
> > instead..?
>
> I'll make a right old mess out of percpu_ida.c, but yeah.
>

Kent and I would both like to see your improvements merged in upstream,
just not in a manner that would cause Greg-KH to start cursing loudly
for a stable backport.

That said, unless Jens throws a last minute NACK, I'll be queuing patch
#1 + #3 into target-pending/for-next for sunday night's build.

Jens, please feel free to pickup Patch #2 for a post v3.15 merge at your
earliest convenience.

Thanks,

--nab

> > diff --git a/lib/percpu_ida.c b/lib/percpu_ida.c
> > index a48ce2e..58b6714 100644
> > --- a/lib/percpu_ida.c
> > +++ b/lib/percpu_ida.c
> > @@ -174,7 +174,8 @@ int percpu_ida_alloc(struct percpu_ida *pool, int state)
> > *
> > * global lock held and irqs disabled, don't need percpu lock
> > */
> > - prepare_to_wait(&pool->wait, &wait, state);
> > + if (state != TASK_RUNNING)
> > + prepare_to_wait(&pool->wait, &wait, state);
> >
> > if (!tags->nr_free)
> > alloc_global_tags(pool, tags);
> > @@ -199,8 +200,9 @@ int percpu_ida_alloc(struct percpu_ida *pool, int state)
> > local_irq_save(flags);
> > tags = this_cpu_ptr(pool->tag_cpu);
> > }
> > + if (state != TASK_RUNNING)
> > + finish_wait(&pool->wait, &wait);
> >
> > - finish_wait(&pool->wait, &wait);
> > return tag;
> > }
> > EXPORT_SYMBOL_GPL(percpu_ida_alloc);
> >
> >
> --
> To unsubscribe from this list: send the line "unsubscribe target-devel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html

2014-02-10 09:28:49

by Alexander Gordeev

[permalink] [raw]

Subject: Re: [PATCH-v2 1/3] percpu_ida: Make percpu_ida_alloc + callers accept task state bitmask

On Thu, Jan 23, 2014 at 05:22:54PM +0100, Peter Zijlstra wrote:
> On Thu, Jan 23, 2014 at 05:28:29AM -0800, Kent Overstreet wrote:
> > pool->lock is also going to be fairly badly contended in the worst case,
> > and that can get real bad real fast... now that I think about it we
> > probably want to avoid the __alloc_global_tag() double call just because
> > of that, pool->lock is going to be quite a bit more contended than the
> > waitlist lock just because fo the amount of work done under it.
>
> On top of the two previous; I think we can reduce pool->lock contention
> by not holding it while doing steal_tags().
>
> By dropping pool->lock around steal_tags() we loose serialization over:
>
> pool->cpus_have_tags is an atomic bitmask, and
> pool->cpu_last_stolem, that's a heuristic anyway, so sod it.
>
> We further loose the guarantee relied upon by percpu_ida_free(), so have
> it also acquire the tags->lock, which should be a far less contended
> resource.
>
> Now everything modifying percpu_ida_cpu state holds
> percpu_ida_cpu::lock, everything that modifies the actual percpu_ida
> freelists holds percpu_ida::lock, and percpu_ida_cpu::lock nests inside
> percpu_ida::lock.
>
>
> The only annoying thing is that we're still holding IRQs over
> steal_tags(), we should be able to make that a preempt_disable() without
> too much effort, or very much cheat and drop even that and rely on the
> percpu_ida_cpu::lock to serialize everything and just hope that we don't
> migrate too often.
>
> But that's for another patch.
>
> ---
> --- a/lib/percpu_ida.c
> +++ b/lib/percpu_ida.c
> @@ -68,8 +68,6 @@ static inline void steal_tags(struct per
> unsigned cpus_have_tags, cpu = pool->cpu_last_stolen;
> struct percpu_ida_cpu *remote;
>
> - lockdep_assert_held(&pool->lock);
> -
> for (cpus_have_tags = cpumask_weight(&pool->cpus_have_tags);
> cpus_have_tags * pool->percpu_max_size > pool->nr_tags / 2;
> cpus_have_tags--) {

Two concurrent threads find and unset the very same bit few lines below

cpu = cpumask_next(cpu, &pool->cpus_have_tags);

[...]

cpumask_clear_cpu(cpu, &pool->cpus_have_tags);

The second's thread unset races with cpumask_set_cpu() in percpu_ida_free()
or alloc_global_tag()

if (nr_free == 1) {
cpumask_set_cpu(smp_processor_id(),
&pool->cpus_have_tags);
wake_up(&pool->wait);
}

Which results in the woken thread does not find the (illegitimately) unset
bit while looping over the mask in steal_tags(). I suspect this or another
thread might enter an unwakable sleep as the number of bits in the mask
and number of threads in the waitqueue became unbalanced.

Hope, I am wrong here.

> @@ -141,18 +139,24 @@ static inline int alloc_global_tag(struc
> min(pool->nr_free, pool->percpu_batch_size));
> }
>
> + spin_unlock(&pool->lock);
> +
> if (!tags->nr_free)
> steal_tags(pool, tags);
>
> if (tags->nr_free) {
> - tag = tags->freelist[--tags->nr_free];
> + spin_lock(&tags->lock);
> if (tags->nr_free) {
> - cpumask_set_cpu(smp_processor_id(),
> - &pool->cpus_have_tags);
> + tag = tags->freelist[--tags->nr_free];
> + if (tags->nr_free) {
> + cpumask_set_cpu(smp_processor_id(),
> + &pool->cpus_have_tags);
> + }
> }
> + spin_unlock(&tags->lock);
> }
>
> - spin_unlock_irqrestore(&pool->lock, flags);
> + local_irq_restore(flags);
>
> return tag;
> }
> @@ -238,12 +242,8 @@ void percpu_ida_free(struct percpu_ida *
>
> if (nr_free == pool->percpu_max_size) {
> spin_lock(&pool->lock);
> + spin_lock(&tags->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,
> tags->freelist, &tags->nr_free,
> @@ -251,6 +251,8 @@ void percpu_ida_free(struct percpu_ida *
>
> wake_up(&pool->wait);
> }
> +
> + spin_unlock(&tags->lock);
> spin_unlock(&pool->lock);
> }
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/

--
Regards,
Alexander Gordeev
[email protected]