locking/percpu-rwsem: Optimize readers and reduce global impact

PATCH In review Peter Zijlstra 8 participants 19 messages Aug 9, 2016 – Aug 31, 2016 2 messages not in the archive

Subsystems (3)

RCU Locking primitives Per-CPU memory allocator

lore

Share & tools

lore

Peter Zijlstra

author maintainer

2016-08-09 09:51 UTC #0 lore raw

PATCH v2 1/1 locking/percpu-rwsem: Optimize readers and reduce global impact

Currently the percpu-rwsem switches to (global) atomic ops while a writer is waiting; which could be quite a while and slows down releasing the readers.

This patch cures this problem by ordering the reader-state vs reader-count (see the comments in __percpu_down_read() and percpu_down_write()). This changes a global atomic op into a full memory barrier, which doesn't have the global cacheline contention.

This also enables using the percpu-rwsem with rcu_sync disabled in order to bias the implementation differently, reducing the writer latency by adding some cost to readers.

Cc Paul McKenney <[email protected]>

Reviewed-by Oleg Nesterov <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 include/linux/percpu-rwsem.h  |   84 +++++++++++++--
 kernel/locking/percpu-rwsem.c |  228 ++++++++++++++++++++++++------------------
 2 files changed, 206 insertions(+), 106 deletions(-)

include/linux/percpu-rwsem.h +75 -9

@@ -10,30 +10,96 @@
 
 struct percpu_rw_semaphore {
 	struct rcu_sync		rss;
-	unsigned int __percpu	*fast_read_ctr;
+	unsigned int __percpu	*read_count;
 	struct rw_semaphore	rw_sem;
-	atomic_t		slow_read_ctr;
-	wait_queue_head_t	write_waitq;
+	wait_queue_head_t	writer;
+	int			readers_block;
 };
 
-extern void percpu_down_read(struct percpu_rw_semaphore *);
-extern int  percpu_down_read_trylock(struct percpu_rw_semaphore *);
-extern void percpu_up_read(struct percpu_rw_semaphore *);
+extern int __percpu_down_read(struct percpu_rw_semaphore *, int);
+extern void __percpu_up_read(struct percpu_rw_semaphore *);
+
+static inline void percpu_down_read(struct percpu_rw_semaphore *sem)
+{
+	might_sleep();
+
+	rwsem_acquire_read(&sem->rw_sem.dep_map, 0, 0, _RET_IP_);
+
+	preempt_disable();
+	/*
+	 * We are in an RCU-sched read-side critical section, so the writer
+	 * cannot both change sem->state from readers_fast and start checking
+	 * counters while we are here. So if we see !sem->state, we know that
+	 * the writer won't be checking until we're past the preempt_enable()
+	 * and that one the synchronize_sched() is done, the writer will see
+	 * anything we did within this RCU-sched read-size critical section.
+	 */
+	__this_cpu_inc(*sem->read_count);
+	if (unlikely(!rcu_sync_is_idle(&sem->rss)))
+		__percpu_down_read(sem, false); /* Unconditional memory barrier */
+	preempt_enable();
+	/*
+	 * The barrier() from preempt_enable() prevents the compiler from
+	 * bleeding the critical section out.
+	 */
+}
+
+static inline int percpu_down_read_trylock(struct percpu_rw_semaphore *sem)
+{
+	int ret = 1;
+
+	preempt_disable();
+	/*
+	 * Same as in percpu_down_read().
+	 */
+	__this_cpu_inc(*sem->read_count);
+	if (unlikely(!rcu_sync_is_idle(&sem->rss)))
+		ret = __percpu_down_read(sem, true); /* Unconditional memory barrier */
+	preempt_enable();
+	/*
+	 * The barrier() from preempt_enable() prevents the compiler from
+	 * bleeding the critical section out.
+	 */
+
+	if (ret)
+		rwsem_acquire_read(&sem->rw_sem.dep_map, 0, 1, _RET_IP_);
+
+	return ret;
+}
+
+static inline void percpu_up_read(struct percpu_rw_semaphore *sem)
+{
+	/*
+	 * The barrier() in preempt_disable() prevents the compiler from
+	 * bleeding the critical section out.
+	 */
+	preempt_disable();
+	/*
+	 * Same as in percpu_down_read().
+	 */
+	if (likely(rcu_sync_is_idle(&sem->rss)))
+		__this_cpu_dec(*sem->read_count);
+	else
+		__percpu_up_read(sem); /* Unconditional memory barrier */
+	preempt_enable();
+
+	rwsem_release(&sem->rw_sem.dep_map, 1, _RET_IP_);
+}
 
 extern void percpu_down_write(struct percpu_rw_semaphore *);
 extern void percpu_up_write(struct percpu_rw_semaphore *);
 
 extern int __percpu_init_rwsem(struct percpu_rw_semaphore *,
 				const char *, struct lock_class_key *);
+
 extern void percpu_free_rwsem(struct percpu_rw_semaphore *);
 
-#define percpu_init_rwsem(brw)	\
+#define percpu_init_rwsem(sem)					\
 ({								\
 	static struct lock_class_key rwsem_key;			\
-	__percpu_init_rwsem(brw, #brw, &rwsem_key);		\
+	__percpu_init_rwsem(sem, #sem, &rwsem_key);		\
 })
 
-
 #define percpu_rwsem_is_held(sem) lockdep_is_held(&(sem)->rw_sem)
 
 static inline void percpu_rwsem_release(struct percpu_rw_semaphore *sem,

kernel/locking/percpu-rwsem.c +131 ~~-97~~

283 lines not on this page · raw message

John Stultz

2016-08-09 23:47 UTC #1 lore raw

Quoted 5 lines · Peter Zijlstra

Currently the percpu-rwsem switches to (global) atomic ops while a writer is waiting; which could be quite a while and slows down releasing the readers.

Quoted 8 lines

This patch cures this problem by ordering the reader-state vs reader-count (see the comments in __percpu_down_read() and percpu_down_write()). This changes a global atomic op into a full memory barrier, which doesn't have the global cacheline contention.
This also enables using the percpu-rwsem with rcu_sync disabled in order to bias the implementation differently, reducing the writer latency by adding some cost to readers.

So this by itself doesn't help us much, but including the following from Oleg does help quite a bit:

kernel/cgroup.c +2 -0

index db27804..9e9200b 100644
@@ -5394,6 +5394,8 @@ int __init cgroup_init(void)
        BUG_ON(cgroup_init_cftypes(NULL, cgroup_dfl_base_files));
        BUG_ON(cgroup_init_cftypes(NULL, cgroup_legacy_base_files));
 
+       rcu_sync_enter(&cgroup_threadgroup_rwsem.rss);
+
        mutex_lock(&cgroup_mutex);
 
        /* Add init_css_set to the hash table */

thanks
-john

Peter Zijlstra

author maintainer

2016-08-10 19:12 UTC #2 lore raw

Quoted 11 lines · John Stultz

Quoted 10 lines · Peter Zijlstra
Currently the percpu-rwsem switches to (global) atomic ops while a writer is waiting; which could be quite a while and slows down releasing the readers.
This patch cures this problem by ordering the reader-state vs reader-count (see the comments in __percpu_down_read() and percpu_down_write()). This changes a global atomic op into a full memory barrier, which doesn't have the global cacheline contention.

Quoted 6 lines

Quoted 3 lines
This also enables using the percpu-rwsem with rcu_sync disabled in order to bias the implementation differently, reducing the writer latency by adding some cost to readers.
So this by itself doesn't help us much, but including the following from Oleg does help quite a bit:

Correct, Oleg was going to send his rcu_sync rework on top of this. But since its holiday season things might be tad delayed.

Oleg Nesterov

2016-08-10 18:27 UTC #3 lore raw

Quoted 17 lines · Peter Zijlstra

Quoted 15 lines · John Stultz
Quoted 13 lines · Peter Zijlstra
Currently the percpu-rwsem switches to (global) atomic ops while a writer is waiting; which could be quite a while and slows down releasing the readers.
This patch cures this problem by ordering the reader-state vs reader-count (see the comments in __percpu_down_read() and percpu_down_write()). This changes a global atomic op into a full memory barrier, which doesn't have the global cacheline contention.
This also enables using the percpu-rwsem with rcu_sync disabled in order to bias the implementation differently, reducing the writer latency by adding some cost to readers.

Quoted 5 lines

Quoted 2 lines
So this by itself doesn't help us much, but including the following from Oleg does help quite a bit:
Correct, Oleg was going to send his rcu_sync rework on top of this. But since its holiday season things might be tad delayed.

Yeees. The patch is ready and even seems to work, but I still can't (re)write the comments. Will try to finish tomorrow.

But. We need something simple and backportable, so I am going to send the patch below first. As you can see this is your "sabotage" change, just the new helper was renamed + s/!GP_IDLE/GP_PASSED/ fix. And the only reason I can't send it today is that somehow I can't write the changelog ;)

So I would be really happy if you send this change instead of me, I am going to keep "From: peterz" anyway.

Oleg.

include/linux/rcu_sync.h +1 -0

index a63a33e..ece7ed9 100644
@@ -59,6 +59,7 @@ static inline bool rcu_sync_is_idle(struct rcu_sync *rsp)
 }
 
 extern void rcu_sync_init(struct rcu_sync *, enum rcu_sync_type);
+extern void rcu_sync_enter_start(struct rcu_sync *);
 extern void rcu_sync_enter(struct rcu_sync *);
 extern void rcu_sync_exit(struct rcu_sync *);
 extern void rcu_sync_dtor(struct rcu_sync *);

kernel/cgroup.c +2 -0

index 75c0ff0..614f9cd 100644
@@ -5609,6 +5609,8 @@ int __init cgroup_init(void)
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_dfl_base_files));
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_legacy_base_files));
 
+	rcu_sync_enter_start(&cgroup_threadgroup_rwsem.rss);
+
 	get_user_ns(init_cgroup_ns.user_ns);
 
 	mutex_lock(&cgroup_mutex);

kernel/rcu/sync.c +12 -0

index be922c9..c9b7bc8 100644
@@ -83,6 +83,18 @@ void rcu_sync_init(struct rcu_sync *rsp, enum rcu_sync_type type)
 }
 
 /**
+ * Must be called after rcu_sync_init() and before first use.
+ *
+ * Ensures rcu_sync_is_idle() returns false and rcu_sync_{enter,exit}() pairs
+ * turn into NO-OPs.
+ */
+void rcu_sync_enter_start(struct rcu_sync *rsp)
+{
+	rsp->gp_count++;
+	rsp->gp_state = GP_PASSED;
+}
+
+/**
  * rcu_sync_enter() - Force readers onto slowpath
  * @rsp: Pointer to rcu_sync structure to use for synchronization
  *

A message that is not in the archive (sent off-list or not yet received): CAH7ZN-zXrenrbbcmvZ+biNozYe21jw6fULopG=g9-xRwWHE6nw@mail.gmail.com

A message that is not in the archive (sent off-list or not yet received): [email protected]

Om Dhyade

2016-08-13 01:44 UTC #6 lore raw

Thank you Dimtry for sharing the patches.

Update from my tests:
Use-case: Android application launches.

I tested the patches on android N build, i see max latency ~7ms.
In my tests, the wait is due to: copy_process(fork.c) blocks all threads in __cgroup_procs_write including threads which are not part of the forking process's thread-group.

Dimtry had provided a hack patch which reverts to per-process rw-sem which had max latency of ~2ms.

android user-space binder library does 2 cgroup write operations per transaction, apart from the copy_process(fork.c) wait, i see pre-emption in _cgroup_procs_write causing waits.

Thanks.

Signature · 2 lines

The Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
a Linux Foundation Collaborative Project

John Stultz

2016-08-24 21:16 UTC #7 lore raw

Quoted 8 lines · Om Dhyade

Update from my tests:
Use-case: Android application launches.
I tested the patches on android N build, i see max latency ~7ms. In my tests, the wait is due to: copy_process(fork.c) blocks all threads in __cgroup_procs_write including threads which are not part of the forking process's thread-group.

Quoted 6 lines

Dimtry had provided a hack patch which reverts to per-process rw-sem which had max latency of ~2ms.
android user-space binder library does 2 cgroup write operations per transaction, apart from the copy_process(fork.c) wait, i see pre-emption in _cgroup_procs_write causing waits.

Hey Peter, Tejun, Oleg,
So while you're tweaks for the percpu-rwsem have greatly helped the
regression folks were seeing (many thanks, by the way), as noted above, the performance regression with the global lock compared to earlier kernels is still ~3x slower (though again, much better then the 80x slower that was seen earlier).

So I was wondering if patches to go back to the per signal_struct locking would still be considered? Or is the global lock approach the only way forward?

At a higher level, I'm worried that Android's use of cgroups as a priority enforcement mechanism is at odds with developers focusing on it as a container enforcement mechanism, as in the latter its not common for tasks to change between cgroups, but with the former priority adjustments are quite common.

thanks
-john

Tejun Heo

maintainer

2016-08-24 21:30 UTC #8 lore raw

Hello, John.

Quoted 10 lines · John Stultz

Hey Peter, Tejun, Oleg,
So while you're tweaks for the percpu-rwsem have greatly helped the
regression folks were seeing (many thanks, by the way), as noted above, the performance regression with the global lock compared to earlier kernels is still ~3x slower (though again, much better then the 80x slower that was seen earlier).
So I was wondering if patches to go back to the per signal_struct locking would still be considered? Or is the global lock approach the only way forward?

We can't simply revert but we can make the lock per signal_struct again. It's just that it'd be quite a bit more complex (but, again, if we need it...) and for cases where migrations aren't as frequent percpu-rwsem would be at least a bit lower overhead. Can you please test with the following patch applied just in case?

https://git.kernel.org/cgit/linux/kernel/git/tj/cgroup.git/commit/?h=for-4.8-fixes&id=568ac888215c7fb2fabe8ea739b00ec3c1f5d440

Quoted 5 lines

At a higher level, I'm worried that Android's use of cgroups as a priority enforcement mechanism is at odds with developers focusing on it as a container enforcement mechanism, as in the latter its not common for tasks to change between cgroups, but with the former priority adjustments are quite common.

It has been at odds as long as android existed. cgroup used to have synchronous synchronize_rcu() in the migration path which android kernel simply deleted (didn't break android's use case), re-labeling every page's memcg ownership on foreground and background switches (does it still do that? it's simply unworkable) and so on.

I find it difficult to believe that android's requirements can be satisfied only through moving processes around. cgroup usage model is affected by container use cases but isn't limited to it. If android is willing to change, I'd be more than happy to work with you and solve obstacles. If not, we'll surely try not to break it anymore than it has always been broken.

Thanks.

Signature · 1 line

tejun

John Stultz

2016-08-24 22:50 UTC #9 lore raw

Quoted 6 lines · Tejun Heo

Quoted 4 lines · John Stultz
So I was wondering if patches to go back to the per signal_struct locking would still be considered? Or is the global lock approach the only way forward?

Quoted 7 lines

We can't simply revert but we can make the lock per signal_struct again. It's just that it'd be quite a bit more complex (but, again, if we need it...) and for cases where migrations aren't as frequent percpu-rwsem would be at least a bit lower overhead. Can you please test with the following patch applied just in case?
https://git.kernel.org/cgit/linux/kernel/git/tj/cgroup.git/commit/?h=for-4.8-fixes&id=568ac888215c7fb2fabe8ea739b00ec3c1f5d440

That does provide a reasonable improvement in my testing! But, I'll pass it along to folks who are doing more in-depth performance analysis to make sure.

If that doesn't work, I'll talk w/ Dmitry about submitting his patch reworking things back to the per signal_struct locking.

Quoted 11 lines

Quoted 5 lines
At a higher level, I'm worried that Android's use of cgroups as a priority enforcement mechanism is at odds with developers focusing on it as a container enforcement mechanism, as in the latter its not common for tasks to change between cgroups, but with the former priority adjustments are quite common.
It has been at odds as long as android existed. cgroup used to have synchronous synchronize_rcu() in the migration path which android kernel simply deleted (didn't break android's use case), re-labeling every page's memcg ownership on foreground and background switches (does it still do that? it's simply unworkable) and so on.

Yea. Android folks can correct me, but I think the memcg forground/background bits have been dropped. They still use a apps memcg group for low-memory-notification in their userland-low-memory-killer-daemon (however my understanding is that has yet to sufficiently replace the in-kernel low-memory-killer).

Quoted 6 lines

I find it difficult to believe that android's requirements can be satisfied only through moving processes around. cgroup usage model is affected by container use cases but isn't limited to it. If android is willing to change, I'd be more than happy to work with you and solve obstacles. If not, we'll surely try not to break it anymore than it has always been broken.

I think folks are open to ideas, but going from idea-from-the-list to something reliable enough to ship is always a bit fraught, so it often takes some time and effort to really validate if those ideas are workable.

I have on my list to re-submit the can_attach logic Android uses to provide permissions checks on processes migrating other tasks between cgroups, so at least we can try to reduce the separate domains of focus and get folks sharing the same code bases.

thanks
-john

John Stultz

2016-08-26 02:20 UTC #10 lore raw

In reply to Tejun Heo

Quoted 14 lines · Tejun Heo

Hello, John.
Quoted 10 lines · John Stultz
Hey Peter, Tejun, Oleg,
So while you're tweaks for the percpu-rwsem have greatly helped the
regression folks were seeing (many thanks, by the way), as noted above, the performance regression with the global lock compared to earlier kernels is still ~3x slower (though again, much better then the 80x slower that was seen earlier).
So I was wondering if patches to go back to the per signal_struct locking would still be considered? Or is the global lock approach the only way forward?

Quoted 7 lines

We can't simply revert but we can make the lock per signal_struct again. It's just that it'd be quite a bit more complex (but, again, if we need it...) and for cases where migrations aren't as frequent percpu-rwsem would be at least a bit lower overhead. Can you please test with the following patch applied just in case?
https://git.kernel.org/cgit/linux/kernel/git/tj/cgroup.git/commit/?h=for-4.8-fixes&id=568ac888215c7fb2fabe8ea739b00ec3c1f5d440

Hey! Good news. This patch along with Peter's locking changes pushes the latencies down to an apparently acceptable level!

Many thanks for the pointer!

thanks
-john

Tejun Heo

maintainer

2016-08-26 12:51 UTC #11 lore raw

Hello, John.

Quoted 2 lines · John Stultz

Hey! Good news. This patch along with Peter's locking changes pushes the latencies down to an apparently acceptable level!

Ah, that's good to hear. Please feel free to ping me if you guys wanna talk about cgroup usage in android.

Thanks!

Signature · 1 line

tejun

Dmitry Shmidt

2016-08-26 16:47 UTC #12 lore raw

Quoted 8 lines · Tejun Heo

Hello, John.
Quoted 2 lines · John Stultz
Hey! Good news. This patch along with Peter's locking changes pushes the latencies down to an apparently acceptable level!
Ah, that's good to hear. Please feel free to ping me if you guys wanna talk about cgroup usage in android.

Thanks a lot for all your help resolving this issue!

Quoted 4 lines

Thanks!
--
tejun

Om Dhyade

2016-08-26 20:10 UTC #13 lore raw

Quoted 12 lines · Dmitry Shmidt

Quoted 8 lines · Tejun Heo
Hello, John.
Quoted 2 lines · John Stultz
Hey! Good news. This patch along with Peter's locking changes pushes the latencies down to an apparently acceptable level!
Ah, that's good to hear. Please feel free to ping me if you guys wanna talk about cgroup usage in android.
Thanks a lot for all your help resolving this issue!

Thank you for the help.

Quoted 4 lines

Quoted 4 lines
Thanks!
--
tejun

Signature · 2 lines

The Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
a Linux Foundation Collaborative Project

Oleg Nesterov

2016-08-11 16:54 UTC #14 lore raw

PATCH 1/1 cgroup: avoid synchronize_sched() in __cgroup_procs_write()

In reply to Peter Zijlstra

From: Peter Zijlstra <[email protected]>

The current percpu-rwsem read side is entirely free of serializing insns at the cost of having a synchronize_sched() in the write path.

The latency of the synchronize_sched() is too high for cgroups. The commit 1ed1328792ff talks about the write path being a fairly cold path but this is not the case for Android which moves task to the foreground cgroup and back around binder IPC calls from foreground processes to background processes, so it is significantly hotter than human initiated operations.

Switch cgroup_threadgroup_rwsem into the slow mode for now to avoid the problem, hopefully it should not be that slow after another commit 80127a39681b ("locking/percpu-rwsem: Optimize readers and reduce global impact").

We could just add rcu_sync_enter() into cgroup_init() but we do not want another synchronize_sched() at boot time, so this patch adds the new helper which doesn't block but currently can only be called before the first use.

Cc Tejun Heo <[email protected]>

Cc Paul McKenney <[email protected]>

Reported-by John Stultz <[email protected]>

Reported-by Dmitry Shmidt <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Signed-off-by Oleg Nesterov <[email protected]>

---
 include/linux/rcu_sync.h |  1 +
 kernel/cgroup.c          |  6 ++++++
 kernel/rcu/sync.c        | 12 ++++++++++++
 3 files changed, 19 insertions(+)

include/linux/rcu_sync.h +1 -0

index a63a33e..ece7ed9 100644
@@ -59,6 +59,7 @@ static inline bool rcu_sync_is_idle(struct rcu_sync *rsp)
 }
 
 extern void rcu_sync_init(struct rcu_sync *, enum rcu_sync_type);
+extern void rcu_sync_enter_start(struct rcu_sync *);
 extern void rcu_sync_enter(struct rcu_sync *);
 extern void rcu_sync_exit(struct rcu_sync *);
 extern void rcu_sync_dtor(struct rcu_sync *);

kernel/cgroup.c +6 -0

index 75c0ff0..8b79751 100644
@@ -5609,6 +5609,12 @@ int __init cgroup_init(void)
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_dfl_base_files));
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_legacy_base_files));
 
+	/*
+	 * The latency of the synchronize_sched() is too high for cgroups,
+	 * avoid it at the cost of forcing all readers into the slow path.
+	 */
+	rcu_sync_enter_start(&cgroup_threadgroup_rwsem.rss);
+
 	get_user_ns(init_cgroup_ns.user_ns);
 
 	mutex_lock(&cgroup_mutex);

kernel/rcu/sync.c +12 -0

index be922c9..e358313 100644
@@ -83,6 +83,18 @@ void rcu_sync_init(struct rcu_sync *rsp, enum rcu_sync_type type)
 }
 
 /**
+ * Must be called after rcu_sync_init() and before first use.
+ *
+ * Ensures rcu_sync_is_idle() returns false and rcu_sync_{enter,exit}()
+ * pairs turn into NO-OPs.
+ */
+void rcu_sync_enter_start(struct rcu_sync *rsp)
+{
+	rsp->gp_count++;
+	rsp->gp_state = GP_PASSED;
+}
+
+/**
  * rcu_sync_enter() - Force readers onto slowpath
  * @rsp: Pointer to rcu_sync structure to use for synchronization
  *

Signature · 1 line

2.5.0

tip-bot for Peter Zijlstra

merge bot

2016-08-18 11:00 UTC #15 lore raw

[tip:locking/core] locking, rcu, cgroup: Avoid synchronize_sched() in __cgroup_procs_write()

locking, rcu, cgroup: Avoid synchronize_sched() in __cgroup_procs_write()

Commit-ID:  64ca3c072e18deaee2a3716d460bf3d72aac242f
Gitweb:     http://git.kernel.org/tip/64ca3c072e18deaee2a3716d460bf3d72aac242f
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Thu, 11 Aug 2016 18:54:13 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Thu, 18 Aug 2016 11:34:25 +0200

locking, rcu, cgroup: Avoid synchronize_sched() in __cgroup_procs_write()

The current percpu-rwsem read side is entirely free of serializing insns at the cost of having a synchronize_sched() in the write path.

Switch cgroup_threadgroup_rwsem into the slow mode for now to avoid the problem, hopefully it should not be that slow after another commit:

80127a39681b ("locking/percpu-rwsem: Optimize readers and reduce global impact").

Reported-by John Stultz <[email protected]>

Reported-by Dmitry Shmidt <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Signed-off-by Oleg Nesterov <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Cc Andrew Morton <[email protected]>

Cc Colin Cross <[email protected]>

Cc Linus Torvalds <[email protected]>

Cc Paul E. McKenney <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Rom Lemarchand <[email protected]>

Cc Tejun Heo <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Todd Kjos <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Ingo Molnar <[email protected]>

---
 include/linux/rcu_sync.h |  1 +
 kernel/cgroup.c          |  6 ++++++
 kernel/rcu/sync.c        | 12 ++++++++++++
 3 files changed, 19 insertions(+)

include/linux/rcu_sync.h +1 -0

index a63a33e..ece7ed9 100644
@@ -59,6 +59,7 @@ static inline bool rcu_sync_is_idle(struct rcu_sync *rsp)
 }
 
 extern void rcu_sync_init(struct rcu_sync *, enum rcu_sync_type);
+extern void rcu_sync_enter_start(struct rcu_sync *);
 extern void rcu_sync_enter(struct rcu_sync *);
 extern void rcu_sync_exit(struct rcu_sync *);
 extern void rcu_sync_dtor(struct rcu_sync *);

kernel/cgroup.c +6 -0

index d1c51b7..9f51cdf 100644
@@ -5606,6 +5606,12 @@ int __init cgroup_init(void)
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_dfl_base_files));
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_legacy_base_files));
 
+	/*
+	 * The latency of the synchronize_sched() is too high for cgroups,
+	 * avoid it at the cost of forcing all readers into the slow path.
+	 */
+	rcu_sync_enter_start(&cgroup_threadgroup_rwsem.rss);
+
 	get_user_ns(init_cgroup_ns.user_ns);
 
 	mutex_lock(&cgroup_mutex);

kernel/rcu/sync.c +12 -0

index be922c9..e358313 100644
@@ -83,6 +83,18 @@ void rcu_sync_init(struct rcu_sync *rsp, enum rcu_sync_type type)
 }
 
 /**
+ * Must be called after rcu_sync_init() and before first use.
+ *
+ * Ensures rcu_sync_is_idle() returns false and rcu_sync_{enter,exit}()
+ * pairs turn into NO-OPs.
+ */
+void rcu_sync_enter_start(struct rcu_sync *rsp)
+{
+	rsp->gp_count++;
+	rsp->gp_state = GP_PASSED;
+}
+
+/**
  * rcu_sync_enter() - Force readers onto slowpath
  * @rsp: Pointer to rcu_sync structure to use for synchronization
  *

tip-bot for Peter Zijlstra

merge bot

2016-08-18 13:45 UTC #16 lore raw

[tip:locking/core] locking, rcu, cgroup: Avoid synchronize_sched() in __cgroup_procs_write()

In reply to Oleg Nesterov

locking, rcu, cgroup: Avoid synchronize_sched() in __cgroup_procs_write()

Commit-ID:  3942a9bd7b5842a924e99ee6ec1350b8006c94ec
Gitweb:     http://git.kernel.org/tip/3942a9bd7b5842a924e99ee6ec1350b8006c94ec
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Thu, 11 Aug 2016 18:54:13 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Thu, 18 Aug 2016 15:36:59 +0200

locking, rcu, cgroup: Avoid synchronize_sched() in __cgroup_procs_write()

The current percpu-rwsem read side is entirely free of serializing insns at the cost of having a synchronize_sched() in the write path.

Switch cgroup_threadgroup_rwsem into the slow mode for now to avoid the problem, hopefully it should not be that slow after another commit:

80127a39681b ("locking/percpu-rwsem: Optimize readers and reduce global impact").

Reported-by John Stultz <[email protected]>

Reported-by Dmitry Shmidt <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Signed-off-by Oleg Nesterov <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Cc Andrew Morton <[email protected]>

Cc Colin Cross <[email protected]>

Cc Linus Torvalds <[email protected]>

Cc Paul E. McKenney <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Rom Lemarchand <[email protected]>

Cc Tejun Heo <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Todd Kjos <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Ingo Molnar <[email protected]>

---
 include/linux/rcu_sync.h |  1 +
 kernel/cgroup.c          |  6 ++++++
 kernel/rcu/sync.c        | 12 ++++++++++++
 3 files changed, 19 insertions(+)

include/linux/rcu_sync.h +1 -0

index a63a33e..ece7ed9 100644
@@ -59,6 +59,7 @@ static inline bool rcu_sync_is_idle(struct rcu_sync *rsp)
 }
 
 extern void rcu_sync_init(struct rcu_sync *, enum rcu_sync_type);
+extern void rcu_sync_enter_start(struct rcu_sync *);
 extern void rcu_sync_enter(struct rcu_sync *);
 extern void rcu_sync_exit(struct rcu_sync *);
 extern void rcu_sync_dtor(struct rcu_sync *);

kernel/cgroup.c +6 -0

index d1c51b7..9f51cdf 100644
@@ -5606,6 +5606,12 @@ int __init cgroup_init(void)
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_dfl_base_files));
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_legacy_base_files));
 
+	/*
+	 * The latency of the synchronize_sched() is too high for cgroups,
+	 * avoid it at the cost of forcing all readers into the slow path.
+	 */
+	rcu_sync_enter_start(&cgroup_threadgroup_rwsem.rss);
+
 	get_user_ns(init_cgroup_ns.user_ns);
 
 	mutex_lock(&cgroup_mutex);

kernel/rcu/sync.c +12 -0

index 198473d..50d1861 100644
@@ -85,6 +85,18 @@ void rcu_sync_init(struct rcu_sync *rsp, enum rcu_sync_type type)
 }
 
 /**
+ * Must be called after rcu_sync_init() and before first use.
+ *
+ * Ensures rcu_sync_is_idle() returns false and rcu_sync_{enter,exit}()
+ * pairs turn into NO-OPs.
+ */
+void rcu_sync_enter_start(struct rcu_sync *rsp)
+{
+	rsp->gp_count++;
+	rsp->gp_state = GP_PASSED;
+}
+
+/**
  * rcu_sync_enter() - Force readers onto slowpath
  * @rsp: Pointer to rcu_sync structure to use for synchronization
  *

Guenter Roeck

2016-08-31 05:21 UTC #17 lore raw

In reply to Peter Zijlstra

Peter,

Quoted 49 lines · Peter Zijlstra

Currently the percpu-rwsem switches to (global) atomic ops while a writer is waiting; which could be quite a while and slows down releasing the readers.
This patch cures this problem by ordering the reader-state vs reader-count (see the comments in __percpu_down_read() and percpu_down_write()). This changes a global atomic op into a full memory barrier, which doesn't have the global cacheline contention.
This also enables using the percpu-rwsem with rcu_sync disabled in order to bias the implementation differently, reducing the writer latency by adding some cost to readers.
Cc Paul McKenney <[email protected]>
Reviewed-by Oleg Nesterov <[email protected]>
Signed-off-by Peter Zijlstra (Intel) <[email protected]>
---
 include/linux/percpu-rwsem.h  |   84 +++++++++++++--
 kernel/locking/percpu-rwsem.c |  228 ++++++++++++++++++++++++------------------
 2 files changed, 206 insertions(+), 106 deletions(-)
include/linux/percpu-rwsem.h +13 -6
@@ -10,30 +10,96 @@
 
 struct percpu_rw_semaphore {
 	struct rcu_sync		rss;
-	unsigned int __percpu	*fast_read_ctr;
+	unsigned int __percpu	*read_count;
 	struct rw_semaphore	rw_sem;
-	atomic_t		slow_read_ctr;
-	wait_queue_head_t	write_waitq;
+	wait_queue_head_t	writer;
+	int			readers_block;
 };
 
-extern void percpu_down_read(struct percpu_rw_semaphore *);
-extern int  percpu_down_read_trylock(struct percpu_rw_semaphore *);
-extern void percpu_up_read(struct percpu_rw_semaphore *);
+extern int __percpu_down_read(struct percpu_rw_semaphore *, int);
+extern void __percpu_up_read(struct percpu_rw_semaphore *);
+
+static inline void percpu_down_read(struct percpu_rw_semaphore *sem)
+{
+	might_sleep();
+
+	rwsem_acquire_read(&sem->rw_sem.dep_map, 0, 0, _RET_IP_);
+
+	preempt_disable();

include/linux/percpu-rwsem.h line 38

Quoted 10 lines

include/linux/percpu-rwsem.h +10 -0

+	/*
+	 * We are in an RCU-sched read-side critical section, so the writer
+	 * cannot both change sem->state from readers_fast and start checking
+	 * counters while we are here. So if we see !sem->state, we know that
+	 * the writer won't be checking until we're past the preempt_enable()
+	 * and that one the synchronize_sched() is done, the writer will see
+	 * anything we did within this RCU-sched read-size critical section.
+	 */
+	__this_cpu_inc(*sem->read_count);
+	if (unlikely(!rcu_sync_is_idle(&sem->rss)))

The call to rcu_sync_is_idle() causes the following build error when building x86_64:allmodconfig.

ERROR: "rcu_sync_lockdep_assert" [kernel/locking/locktorture.ko] undefined!
ERROR: "rcu_sync_lockdep_assert" [fs/ext4/ext4.ko] undefined!

I think this was also reported by the 0-day build bot.

The simple fix would of course be to export rcu_sync_lockdep_assert. Before I apply that change to the Android code (where the patch has been aplied and the problem is seen) - do you by any chance have a better solution in mind ?

Thanks,
Guenter

Peter Zijlstra

author maintainer

2016-08-31 08:10 UTC #18 lore raw

Quoted 5 lines · Guenter Roeck

Peter,
The call to rcu_sync_is_idle() causes the following build error when building x86_64:allmodconfig.

Quoted 8 lines

ERROR: "rcu_sync_lockdep_assert" [kernel/locking/locktorture.ko] undefined!
ERROR: "rcu_sync_lockdep_assert" [fs/ext4/ext4.ko] undefined!
I think this was also reported by the 0-day build bot.
The simple fix would of course be to export rcu_sync_lockdep_assert. Before I apply that change to the Android code (where the patch has been aplied and the problem is seen) - do you by any chance have a better solution in mind ?

Nope, that's exactly what Ingo did when he ran into this. If you look at commit 80127a39681b ("locking/percpu-rwsem: Optimize readers and reduce global impact"), you'll notice the last hunk:

kernel/rcu/sync.c +2 -0

index be922c9f3d37..198473d90f81 100644
@@ -68,6 +68,8 @@ void rcu_sync_lockdep_assert(struct rcu_sync *rsp)
 	RCU_LOCKDEP_WARN(!gp_ops[rsp->gp_type].held(),
 			 "suspicious rcu_sync_is_idle() usage");
 }
+
+EXPORT_SYMBOL_GPL(rcu_sync_lockdep_assert);
 #endif
 
 /**

Guenter Roeck

2016-08-31 13:41 UTC #19 lore raw

Quoted 11 lines · Peter Zijlstra

Quoted 10 lines · Guenter Roeck
Peter,
The call to rcu_sync_is_idle() causes the following build error when building x86_64:allmodconfig.
ERROR: "rcu_sync_lockdep_assert" [kernel/locking/locktorture.ko] undefined!
ERROR: "rcu_sync_lockdep_assert" [fs/ext4/ext4.ko] undefined!
I think this was also reported by the 0-day build bot.

Quoted 8 lines

Quoted 3 lines
The simple fix would of course be to export rcu_sync_lockdep_assert. Before I apply that change to the Android code (where the patch has been aplied and the problem is seen) - do you by any chance have a better solution in mind ?
Nope, that's exactly what Ingo did when he ran into this. If you look at commit 80127a39681b ("locking/percpu-rwsem: Optimize readers and reduce global impact"), you'll notice the last hunk:

Ah, I missed that, and didn't realize that it is already upstream. Thanks a lot!

Guenter

Guenter Roeck

2016-08-31 13:47 UTC #20 lore raw

Quoted 16 lines · Guenter Roeck

Quoted 15 lines · Peter Zijlstra
Quoted 13 lines · Guenter Roeck
Peter,
The call to rcu_sync_is_idle() causes the following build error when building x86_64:allmodconfig.
ERROR: "rcu_sync_lockdep_assert" [kernel/locking/locktorture.ko] undefined!
ERROR: "rcu_sync_lockdep_assert" [fs/ext4/ext4.ko] undefined!
I think this was also reported by the 0-day build bot.
The simple fix would of course be to export rcu_sync_lockdep_assert. Before I apply that change to the Android code (where the patch has been aplied and the problem is seen) - do you by any chance have a better solution in mind ?

Quoted 6 lines

Quoted 4 lines
Nope, that's exactly what Ingo did when he ran into this. If you look at commit 80127a39681b ("locking/percpu-rwsem: Optimize readers and reduce global impact"), you'll notice the last hunk:
Ah, I missed that, and didn't realize that it is already upstream. Thanks a lot!

Wait, it isn't ... I must have fetched a branch with 80127a39681b. Ignore the noise I am making until after I had another coffee.

Guenter