percpu_ida: Various tweaks
Subsystems (2)
cover percpu_ida: Various tweaks
Hi Kent,
I am resending the series without couple of original patches. As I understand, you have not been able to find this series anywhere, so please note your ACKs to the first two ;)
Thanks!
Alexander Gordeev (3):
percpu_ida: Fix data race on cpus_have_tags cpumask
percpu_ida: Move waking up waiters out of atomic contexts
percpu_ida: Sanity check initialization parameters
lib/percpu_ida.c | 26 +++++++++++++++++++++----- 1 files changed, 21 insertions(+), 5 deletions(-)
Signature · 1 line
1.7.7.6
PATCH RESEND 1/3 percpu_ida: Fix data race on cpus_have_tags cpumask
Function steal_tags() might miss a bit in cpus_have_tags due to unsynchronized access from percpu_ida_free(). As result, function percpu_ida_alloc() might enter unwakable sleep. This update adds memory barriers to prevent the described scenario.
In fact, accesses to cpus_have_tags are fenced by prepare_to_wait() and wake_up() calls at the moment and the aforementioned sequence does not appear could hit. Nevertheless, explicit memory barriers still seem justifiable.
--- lib/percpu_ida.c | 12 ++++++++++-- 1 files changed, 10 insertions(+), 2 deletions(-)
lib/percpu_ida.c +10 -2
@@ -68,6 +68,11 @@ static inline void steal_tags(struct percpu_ida *pool,unsigned cpus_have_tags, cpu = pool->cpu_last_stolen;struct percpu_ida_cpu *remote; +/* +* Pairs with smp_wmb() in percpu_ida_free() +*/ +smp_rmb (); +for (cpus_have_tags =cpumask_weight (&pool->cpus_have_tags); cpus_have_tags * pool->percpu_max_size > pool->nr_tags /2 ; cpus_have_tags--) {
@@ -237,8 +242,11 @@ void percpu_ida_free(struct percpu_ida *pool, unsigned tag)spin_unlock (&tags->lock);if (nr_free ==1 ) { -cpumask_set_cpu (smp_processor_id (), - &pool->cpus_have_tags); +cpumask_set_cpu (smp_processor_id (), &pool->cpus_have_tags); +/* +* Pairs with smp_rmb() in steal_tags() +*/ +smp_wmb ();wake_up (&pool->wait); }
Signature · 1 line
1.7.7.6
Re: [PATCH RESEND 1/3] percpu_ida: Fix data race on cpus_have_tags cpumask
Quoted 38 lines · Alexander Gordeev
Function
steal_tags()might miss a bit incpus_have_tagsdue to unsynchronized access frompercpu_ida_free(). As result, functionpercpu_ida_alloc()might enter unwakable sleep. This update adds memory barriers to prevent the described scenario.In fact, accesses to
cpus_have_tagsare fenced byprepare_to_wait()andwake_up()calls at the moment and the aforementioned sequence does not appear could hit. Nevertheless, explicit memory barriers still seem justifiable.Signed-off-by Alexander Gordeev <[email protected]>Cc Kent Overstreet <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Jens Axboe <[email protected]>Cc "Nicholas A. Bellinger" <[email protected]>Acked-by Kent Overstreet <[email protected]>--- lib/percpu_ida.c | 12 ++++++++++-- 1 files changed, 10 insertions(+), 2 deletions(-)lib/percpu_ida.c +5
-0@@ -68,6 +68,11 @@ static inline void steal_tags(struct percpu_ida *pool,unsigned cpus_have_tags, cpu = pool->cpu_last_stolen;struct percpu_ida_cpu *remote; +/* +* Pairs with smp_wmb() in percpu_ida_free() +*/ +smp_rmb (); +for (cpus_have_tags =cpumask_weight (&pool->cpus_have_tags); cpus_have_tags * pool->percpu_max_size > pool->nr_tags /2 ; cpus_have_tags--) {@@ -237,8 +242,11 @@ void percpu_ida_free(struct percpu_ida *pool, unsigned tag)spin_unlock (&tags->lock);
lib/percpu_ida.c void percpu_ida_free(struct percpu_ida *pool, unsigned tag) · line 250
Quoted 10 lines
lib/percpu_ida.c +5
-2if (nr_free ==1 ) { -cpumask_set_cpu (smp_processor_id (), - &pool->cpus_have_tags); +cpumask_set_cpu (smp_processor_id (), &pool->cpus_have_tags); +/* +* Pairs with smp_rmb() in steal_tags() +*/ +smp_wmb ();wake_up (&pool->wait);
I think I'm nacking this - there's a lot of code in the kernel that relies on the fact that prepare_to_wait)/wake_up() do the appropriate fences, we really shouldn't be adding to the barriers those do.
If you can come up with some other reason we need the barriers I'll reconsider.
Re: [PATCH RESEND 1/3] percpu_ida: Fix data race on cpus_have_tags cpumask
Quoted 40 lines · Kent Overstreet
Quoted 39 lines · Alexander Gordeev
Function
steal_tags()might miss a bit incpus_have_tagsdue to unsynchronized access frompercpu_ida_free(). As result, functionpercpu_ida_alloc()might enter unwakable sleep. This update adds memory barriers to prevent the described scenario.In fact, accesses to
cpus_have_tagsare fenced byprepare_to_wait()andwake_up()calls at the moment and the aforementioned sequence does not appear could hit. Nevertheless, explicit memory barriers still seem justifiable.Signed-off-by Alexander Gordeev <[email protected]>Cc Kent Overstreet <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Jens Axboe <[email protected]>Cc "Nicholas A. Bellinger" <[email protected]>Acked-by Kent Overstreet <[email protected]>--- lib/percpu_ida.c | 12 ++++++++++-- 1 files changed, 10 insertions(+), 2 deletions(-)lib/percpu_ida.c +5
-0@@ -68,6 +68,11 @@ static inline void steal_tags(struct percpu_ida *pool,unsigned cpus_have_tags, cpu = pool->cpu_last_stolen;struct percpu_ida_cpu *remote; +/* +* Pairs with smp_wmb() in percpu_ida_free() +*/ +smp_rmb (); +for (cpus_have_tags =cpumask_weight (&pool->cpus_have_tags); cpus_have_tags * pool->percpu_max_size > pool->nr_tags /2 ; cpus_have_tags--) {@@ -237,8 +242,11 @@ void percpu_ida_free(struct percpu_ida *pool, unsigned tag)spin_unlock (&tags->lock);
Quoted 13 lines
lib/percpu_ida.c void percpu_ida_free(struct percpu_ida *pool, unsigned tag) · line 250
Quoted 9 lines
lib/percpu_ida.c +5
-2if (nr_free ==1 ) { -cpumask_set_cpu (smp_processor_id (), - &pool->cpus_have_tags); +cpumask_set_cpu (smp_processor_id (), &pool->cpus_have_tags); +/* +* Pairs with smp_rmb() in steal_tags() +*/ +smp_wmb ();wake_up (&pool->wait);I think I'm nacking this - there's a lot of code in the kernel that relies on the fact that prepare_to_wait)/wake_up() do the appropriate fences, we really shouldn't be adding to the barriers those do.
In theory, it still might cause percpu_ida_alloc(TASK_RUNNING) failed, looks it isn't a big deal for the case.
But I am wondering why cpumask_set_cpu() isn't called with holding lock inside percpu_ida_free()? Looks 'nr_free == 1' shouldn't have happened frequently.
Thanks,
Signature · 1 line
Ming Lei
Re: [PATCH RESEND 1/3] percpu_ida: Fix data race on cpus_have_tags cpumask
Quoted 17 lines · Ming Lei
Quoted 16 lines
lib/percpu_ida.c void percpu_ida_free(struct percpu_ida *pool, unsigned tag) · line 250
Quoted 12 lines
lib/percpu_ida.c +5
-2@@ -237,8 +242,11 @@ void percpu_ida_free(struct percpu_ida *pool, unsigned tag)spin_unlock (&tags->lock);if (nr_free ==1 ) { -cpumask_set_cpu (smp_processor_id (), - &pool->cpus_have_tags); +cpumask_set_cpu (smp_processor_id (), &pool->cpus_have_tags); +/* +* Pairs with smp_rmb() in steal_tags() +*/ +smp_wmb ();wake_up (&pool->wait);I think I'm nacking this - there's a lot of code in the kernel that relies on the fact that prepare_to_wait)/wake_up() do the appropriate fences, we really shouldn't be adding to the barriers those do.
Quoted 6 lines
In theory, it still might cause
percpu_ida_alloc(TASK_RUNNING)failed, looks it isn't a big deal for the case.But I am wondering why
cpumask_set_cpu()isn't called with holding lock insidepercpu_ida_free()? Looks 'nr_free== 1' shouldn't have happened frequently.
Because bouncing on the lock is more expensive than occasionally putting a thread into sleep.
Quoted 5 lines
Thanks,
Signature · 1 line
Ming Lei
Signature · 3 lines
Regards, Alexander Gordeev [email protected]
Re: [PATCH RESEND 1/3] percpu_ida: Fix data race on cpus_have_tags cpumask
Quoted 10 lines · Alexander Gordeev
Quoted 7 lines
In theory, it still might cause
percpu_ida_alloc(TASK_RUNNING)failed, looks it isn't a big deal for the case.But I am wondering why
cpumask_set_cpu()isn't called with holding lock insidepercpu_ida_free()? Looks 'nr_free== 1' shouldn't have happened frequently.Because bouncing on the lock is more expensive than occasionally putting a thread into sleep.
I mean the below block can be put inside the previous lock:
if (nr_free == 1)
cpumask_set_cpu()As I mentioned, 'nr_free == 1' doesn't happen frequently, so it won't be big deal, will it?
Thanks,
Signature · 1 line
Ming Lei
Re: [PATCH RESEND 1/3] percpu_ida: Fix data race on cpus_have_tags cpumask
Quoted 10 lines · Ming Lei
Quoted 9 lines
Quoted 6 lines
In theory, it still might cause
percpu_ida_alloc(TASK_RUNNING)failed, looks it isn't a big deal for the case.But I am wondering why
cpumask_set_cpu()isn't called with holding lock insidepercpu_ida_free()? Looks 'nr_free== 1' shouldn't have happened frequently.Because bouncing on the lock is more expensive than occasionally putting a thread into sleep.
Quoted 7 lines
I mean the below block can be put inside the previous lock:
if (nr_free == 1) cpumask_set_cpu()As I mentioned, '
nr_free== 1' doesn't happen frequently, so it won't be big deal, will it?
No. The lock will be taken *each* time in your suggestion, which is bad.
Signature · 3 lines
Regards, Alexander Gordeev [email protected]
Re: [PATCH RESEND 1/3] percpu_ida: Fix data race on cpus_have_tags cpumask
In reply to Ming LeiQuoted 1 line · Ming Lei
I mean the below block can be put inside the previous lock:
Oh, *now* I see what you mean. Please, ignore my prevous reply. Still, we want to release the lock as soon as possible and there is no reason to the below bits it under lock.
Quoted 5 lines
if (nr_free == 1) cpumask_set_cpu()As I mentioned, '
nr_free== 1' doesn't happen frequently, so it won't be big deal, will it?
Signature · 3 lines
Regards, Alexander Gordeev [email protected]
Re: [PATCH RESEND 1/3] percpu_ida: Fix data race on cpus_have_tags cpumask
Quoted 6 lines · Alexander Gordeev
Quoted 1 line · Ming Lei
I mean the below block can be put inside the previous lock:
Oh, *now* I see what you mean. Please, ignore my prevous reply. Still, we want to release the lock as soon as possible and there is no reason to the below bits it under lock.
Actually my comment was wrong because pool->cpus_have_tags should be guarded by pool->lock instead of the percpu tag->lock.
Sorry for the noise.
Thanks,
Signature · 1 line
Ming Lei
PATCH RESEND 2/3 percpu_ida: Move waking up waiters out of atomic contexts
In reply to Alexander GordeevCurrently percpu_ida_free() waikes up waiters always with local interrupts disabled and sometimes with pool->lock held. Yet, it does not appear there is any reason why it could not be done out of these atomic contexts.
--- lib/percpu_ida.c | 9 ++++++--- 1 files changed, 6 insertions(+), 3 deletions(-)
lib/percpu_ida.c +6 -3
@@ -229,6 +229,7 @@ void percpu_ida_free(struct percpu_ida *pool, unsigned tag)struct percpu_ida_cpu *tags;unsigned long flags;unsigned nr_free; +bool wake_up = false;BUG_ON (tag >= pool->nr_tags);
@@ -247,7 +248,7 @@ void percpu_ida_free(struct percpu_ida *pool, unsigned tag)* Pairs with smp_rmb() in steal_tags() */ smp_wmb (); -wake_up (&pool->wait); + wake_up = true; }if (nr_free == pool->percpu_max_size) {
@@ -261,13 +262,15 @@ void percpu_ida_free(struct percpu_ida *pool, unsigned tag)move_tags (pool->freelist, &pool->nr_free, tags->freelist, &tags->nr_free, pool->percpu_batch_size); - -wake_up (&pool->wait); + wake_up = true; }spin_unlock (&pool->lock); }local_irq_restore (flags); + +if (wake_up) +wake_up (&pool->wait); }EXPORT_SYMBOL_GPL (percpu_ida_free);
Signature · 1 line
1.7.7.6
PATCH RESEND 3/3 percpu_ida: Sanity check initialization parameters
In reply to Alexander Gordeev--- lib/percpu_ida.c | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-)
lib/percpu_ida.c +5 -0
@@ -305,6 +305,11 @@ int __percpu_ida_init(struct percpu_ida *pool, unsigned long nr_tags, {unsigned i, cpu, order; +if (batch_size > max_size) +return -ERANGE ; +if (!batch_size) +return -EINVAL ; +memset (pool,0 ,sizeof (*pool));init_waitqueue_head (&pool->wait);
Signature · 1 line
1.7.7.6
Re: [PATCH RESEND 3/3] percpu_ida: Sanity check initialization parameters
Quoted 15 lines · Alexander Gordeev
Signed-off-by Alexander Gordeev <[email protected]>Cc Kent Overstreet <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Jens Axboe <[email protected]>Cc "Nicholas A. Bellinger" <[email protected]>--- lib/percpu_ida.c | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-)lib/percpu_ida.c +0
-0@@ -305,6 +305,11 @@ int __percpu_ida_init(struct percpu_ida *pool, unsigned long nr_tags, {
lib/percpu_ida.c int __percpu_ida_init(struct percpu_ida *pool, unsigned long nr_tags, · line 315
Quoted 10 lines
lib/percpu_ida.c +5
-0unsigned i, cpu, order; +if (batch_size > max_size) +return -ERANGE ; +if (!batch_size) +return -EINVAL ; +memset (pool,0 ,sizeof (*pool));init_waitqueue_head (&pool->wait);
PATCH 4/4 percpu_ida: Do not steal all remote CPU tags at once
In reply to Alexander GordeevWhen stealing from a remote CPU all available tags are moved from the remote CPU's cache to the stealing CPU's one. Since the best CPU to steal from is not selected the victim might actively performing IO and (as result of losing all local tags) a further cycle of cache rebouncing and/or stealing could be provoked.
This update is an attempt to soften the described scenario and limit the number of tags to be stolen at once to the value of percpu_batch_size.
--- lib/percpu_ida.c | 18 ++++++++++-------- 1 files changed, 10 insertions(+), 8 deletions(-)
lib/percpu_ida.c +10 -8
@@ -84,20 +84,22 @@ static inline void steal_tags(struct percpu_ida *pool, pool->cpu_last_stolen = cpu; remote =per_cpu_ptr (pool->tag_cpu, cpu); -cpumask_clear_cpu (cpu, &pool->cpus_have_tags); - -if (remote == tags) +if (remote == tags) { +cpumask_clear_cpu (cpu, &pool->cpus_have_tags);continue ; + }spin_lock (&remote->lock);if (remote->nr_free) { -memcpy (tags->freelist, - remote->freelist, -sizeof (unsigned ) * remote->nr_free); +const struct percpu_ida *p = pool; + +move_tags (tags->freelist, &tags->nr_free, + remote->freelist, &remote->nr_free, +min (remote->nr_free, p->percpu_batch_size)); - tags->nr_free = remote->nr_free; - remote->nr_free =0 ; +if (!remote->nr_free) +cpumask_clear_cpu (cpu, &pool->cpus_have_tags); }spin_unlock (&remote->lock);
Signature · 6 lines
1.7.7.6 -- Regards, Alexander Gordeev [email protected]
Re: [PATCH 4/4] percpu_ida: Do not steal all remote CPU tags at once
Quoted 10 lines · Alexander Gordeev
When stealing from a remote CPU all available tags are moved from the remote CPU's cache to the stealing CPU's one. Since the best CPU to steal from is not selected the victim might actively performing IO and (as result of losing all local tags) a further cycle of cache rebouncing and/or stealing could be provoked.
This update is an attempt to soften the described scenario and limit the number of tags to be stolen at once to the value of
percpu_batch_size.
I don't want this patch without a benchmark justifying the change and more analysis; this could easily lead to more stealing and cacheline bouncing.
Quoted 52 lines
Signed-off-by Alexander Gordeev <[email protected]>Cc Kent Overstreet <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Jens Axboe <[email protected]>Cc "Nicholas A. Bellinger" <[email protected]>--- lib/percpu_ida.c | 18 ++++++++++-------- 1 files changed, 10 insertions(+), 8 deletions(-)lib/percpu_ida.c +10
-8@@ -84,20 +84,22 @@ static inline void steal_tags(struct percpu_ida *pool, pool->cpu_last_stolen = cpu; remote =per_cpu_ptr (pool->tag_cpu, cpu); -cpumask_clear_cpu (cpu, &pool->cpus_have_tags); - -if (remote == tags) +if (remote == tags) { +cpumask_clear_cpu (cpu, &pool->cpus_have_tags);continue ; + }spin_lock (&remote->lock);if (remote->nr_free) { -memcpy (tags->freelist, - remote->freelist, -sizeof (unsigned ) * remote->nr_free); +const struct percpu_ida *p = pool; + +move_tags (tags->freelist, &tags->nr_free, + remote->freelist, &remote->nr_free, +min (remote->nr_free, p->percpu_batch_size)); - tags->nr_free = remote->nr_free; - remote->nr_free =0 ; +if (!remote->nr_free) +cpumask_clear_cpu (cpu, &pool->cpus_have_tags); }spin_unlock (&remote->lock);Signature · 6 lines
1.7.7.6 -- Regards, Alexander Gordeev [email protected]
Quoted 3 lines · Alexander Gordeev
Hi Jens,
Any feedback on these?
Sorry, I dropped the ball last time...