Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1441923 > unrolled thread

Severe performance regression w/ 4.4+ on Android due to cgroup locking changes

Back to article view | Back to linux.kernel

Contents

  Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-13 02:10 +0200
    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-13 10:30 +0200
      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-13 16:50 +0200
        Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-13 20:40 +0200
    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-13 20:30 +0200
      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-13 20:40 +0200
        Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-13 22:20 +0200
          Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-13 22:30 +0200
            Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-13 22:50 +0200
              Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-13 23:00 +0200
                Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-13 23:10 +0200
                  Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-13 23:20 +0200
                    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-13 23:50 +0200
                      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-13 23:50 +0200
                        Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-14 00:20 +0200
                          Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-14 00:40 +0200
                            Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-14 01:10 +0200
                              Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-14 01:10 +0200
                                Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-14 13:40 +0200
                                  Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 14:10 +0200
                                    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-14 14:10 +0200
                                      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 14:30 +0200
                                        Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-14 17:10 +0200
                                          Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-14 17:30 +0200
                                          Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 18:40 +0200
                                            Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Oleg Nesterov <oleg@redhat.com> - 2016-07-14 19:40 +0200
                              Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-14 19:00 +0200
                      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-14 00:30 +0200
                    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-14 00:10 +0200
                      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-14 00:40 +0200
                      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 09:00 +0200
                        Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-14 13:30 +0200
                          Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 14:20 +0200
                            Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-14 17:20 +0200
                Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-13 23:10 +0200
                Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-13 23:10 +0200
                Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 15:20 +0200
                  Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 16:20 +0200
                  Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Oleg Nesterov <oleg@redhat.com> - 2016-07-14 17:00 +0200
                    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 18:20 +0200
                    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 18:40 +0200
                      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Oleg Nesterov <oleg@redhat.com> - 2016-07-14 19:10 +0200
                  Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-14 18:30 +0200
                    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 18:50 +0200
                      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-14 19:20 +0200
                  Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-14 18:50 +0200
                    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 18:50 +0200
                      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-14 19:10 +0200
                        Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Oleg Nesterov <oleg@redhat.com> - 2016-07-14 19:20 +0200
                          Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-14 19:40 +0200
                            Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Oleg Nesterov <oleg@redhat.com> - 2016-07-14 19:50 +0200
                              Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-14 20:00 +0200
                  Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Oleg Nesterov <oleg@redhat.com> - 2016-07-14 20:10 +0200
                    Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 20:40 +0200
                      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-14 21:40 +0200
              Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-13 23:00 +0200
            Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Peter Zijlstra <peterz@infradead.org> - 2016-07-13 23:00 +0200
              Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-13 23:10 +0200
            Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-13 23:00 +0200
              Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Dmitry Shmidt <dimitrysh@google.com> - 2016-07-13 23:10 +0200
                Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-13 23:10 +0200
                Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-13 23:10 +0200
        Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes John Stultz <john.stultz@linaro.org> - 2016-07-13 22:20 +0200
        Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Dmitry Shmidt <dimitrysh@google.com> - 2016-07-13 22:40 +0200
      Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Colin Cross <ccross@google.com> - 2016-07-13 22:50 +0200
        Re: Severe performance regression w/ 4.4+ on Android due to cgroup  locking changes Tejun Heo <tj@kernel.org> - 2016-07-13 23:00 +0200

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

#1443393

On Thu, Jul 14, 2016 at 02:04:28PM +0200, Peter Zijlstra wrote:
> > I think it probably makes sense to make this the default on !RT at
> > least with a separate patch w/o stable cc'd.  While most use cases
> > will be fine with the latency on write path, it also means that the
> > reader side is blocked for the duration which can hurt.  rwsem implies
> > a lot more readers and thus more read lock operations than writes.
> > It's weird to trade off higher latency for lower cpu usage when it
> > would also slow down all readers.
> 
> NAK, no expedited muck by default. There's more than just RT that
> doesn't like IPI sprays.

Can you elaborate?  If that's the case, we have the wrong implemention
for percpu-rwsem where very long delays for writers induce the same
level of delays to all readers.  If expedited by default isn't
workable, we should move away from rcu_sync for percpu_rwsem.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1443406

On Thu, Jul 14, 2016 at 08:08:45AM -0400, Tejun Heo wrote:
> On Thu, Jul 14, 2016 at 02:04:28PM +0200, Peter Zijlstra wrote:
> > > I think it probably makes sense to make this the default on !RT at
> > > least with a separate patch w/o stable cc'd.  While most use cases
> > > will be fine with the latency on write path, it also means that the
> > > reader side is blocked for the duration which can hurt.  rwsem implies
> > > a lot more readers and thus more read lock operations than writes.
> > > It's weird to trade off higher latency for lower cpu usage when it
> > > would also slow down all readers.
> > 
> > NAK, no expedited muck by default. There's more than just RT that
> > doesn't like IPI sprays.
> 
> Can you elaborate?  

HPC doesn't use RT but still wants to minimize jitter such that all CPUs
complete their work ASAP. They use barriers to wait on the slowest CPU
to complete work.

Sending random interrupts disturbs cache and other stuff and delays
things unnecessarily.

Same with RDMA (or other) userspace poll loops which want minimal
latency, they too don't use RT, but also very much want to avoid the
kernel poking at them.

Many of this could eventually use NOHZ_FULL, but I'm not sure all of
that is suitable.

In general its very bad form to spray interrupts just because and we've
spend a lot of effort to reduce that.

> If that's the case, we have the wrong implemention
> for percpu-rwsem where very long delays for writers induce the same
> level of delays to all readers.  If expedited by default isn't
> workable, we should move away from rcu_sync for percpu_rwsem.

Just because your usecase doesn't like it, doesn't mean its not good.
Its a perfectly fine implementation for uprobes for example. The
addition/removal of uprobes is extremely rare, as global writers should
be.

And no, the writer delay isn't observed by the readers, those will
continue 'undisturbed' for most of it.

[toc] | [prev] | [next] | [standalone]

#1443514

On Thu, Jul 14, 2016 at 02:20:49PM +0200, Peter Zijlstra wrote:
> > If that's the case, we have the wrong implemention
> > for percpu-rwsem where very long delays for writers induce the same
> > level of delays to all readers.  If expedited by default isn't
> > workable, we should move away from rcu_sync for percpu_rwsem.
> 
> Just because your usecase doesn't like it, doesn't mean its not good.
> Its a perfectly fine implementation for uprobes for example. The
> addition/removal of uprobes is extremely rare, as global writers should
> be.
>
> And no, the writer delay isn't observed by the readers, those will
> continue 'undisturbed' for most of it.

How?  While write lock is pending, no new reader is allowed.  If
reader ops are high frequency, they will surely get affected.  It just
isn't a good design to inject RCU grace period synchronously into a
hot path.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1443525

On Thu, Jul 14, 2016 at 11:07:15AM -0400, Tejun Heo wrote:
> On Thu, Jul 14, 2016 at 02:20:49PM +0200, Peter Zijlstra wrote:
> > > If that's the case, we have the wrong implemention
> > > for percpu-rwsem where very long delays for writers induce the same
> > > level of delays to all readers.  If expedited by default isn't
> > > workable, we should move away from rcu_sync for percpu_rwsem.
> > 
> > Just because your usecase doesn't like it, doesn't mean its not good.
> > Its a perfectly fine implementation for uprobes for example. The
> > addition/removal of uprobes is extremely rare, as global writers should
> > be.
> >
> > And no, the writer delay isn't observed by the readers, those will
> > continue 'undisturbed' for most of it.
> 
> How?  While write lock is pending, no new reader is allowed.  If
> reader ops are high frequency, they will surely get affected.  It just
> isn't a good design to inject RCU grace period synchronously into a
> hot path.

Oops, right, the grace period is just used to switch the lock to
global mode while readers are passing through.  Never mind this point.
It's purely about writer latency then.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1443579

On Thu, Jul 14, 2016 at 11:07:15AM -0400, Tejun Heo wrote:
> How?  While write lock is pending, no new reader is allowed.

Look at the new percpu_down_write (the old one is similar in concept):

+ void percpu_down_write(struct percpu_rw_semaphore *sem)
+ {
+ 	down_write(&sem->rw_sem);
+ 
+ 	/* Notify readers to take the slow path. */
+ 	rcu_sync_enter(&sem->rss);
+ 
+ 	/*
+ 	 * Notify new readers to block; up until now, and thus throughout the
+ 	 * longish rcu_sync_enter() above, new readers could still come in.
+ 	 */
+ 	WRITE_ONCE(sem->state, readers_block);

Note how up until this point new readers could happen? So the 'entire'
synchronize_sched() call is 'invisible' to new readers.

We need the sync_sched() to ensure all new down_read callers will go
through the 'slow' down_read path and even look at sem->state.

+ 
+ 	smp_mb(); /* D matches A */
+ 
+ 	/*
+ 	 * If they don't see our writer of readers_block to sem->state,
+ 	 * then we are guaranteed to see their sem->refcount increment, and
+ 	 * therefore will wait for them.
+ 	 */
+ 
+ 	/* Wait for all now active readers to complete. */
+ 	wait_event(sem->writer, readers_active_check(sem));
+ }

> If reader ops are high frequency, they will surely get affected. 

Before the sync_sched() a down_read (PREEMPT=n, LOCKDEP=n) is basically:

  __this_cpu_inc(*sem->refcount)
  if (sem->rss->gp_state) /* false */
	;

This is one purely local (!atomic) RmW and one load of a shared
variable. Absolute minimal overhead.

During sync_sched() gp_state is !0 and we end up doing:

  __this_cpu_inc(*sem->refcount)
  if (sem->rss->gp_state) {
	smp_mb();
	if (sem->state != readers_block) /* true */
		return;
  }

Which is 1 smp_mb() and 1 shared state load (to the same cacheline we
touched before IIRC) more. Now full barriers are really rather
expensive, and do show up on profiles.

(and this is where the old and new code differ, the old code would end
up doing: __down_read(&sem->rwsem), which is a shared atomic RmW and is
_much_ more expensive).

> It just isn't a good design to inject RCU grace period synchronously
> into a hot path.

That's just the point, the write side of a _global_ lock can never, per
definition, be a hot path.

Now, I realize not everyone wants these same tradeoffs and I did you
this patch to allow that.

But I really think that this Android usecase invalidates the premise of
cgroups using a global lock.

[toc] | [prev] | [next] | [standalone]

#1443630

On 07/14, Peter Zijlstra wrote:
>
> But I really think that this Android usecase invalidates the premise of
> cgroups using a global lock.

Perhaps... but it would be nice to have a global lock for cgroups (and in
fact probably unify it with dup_mmap_sem). And we can't simply revert that
change now.

I am wondering if this use-case is really Android-specific or not. Because,
once again, we can add a boot option or even run-time knob for
cgroup_threadgroup_rwsem. If it is really Android-specific, we do not want
to penalize fork/exit by default.

Oleg.

[toc] | [prev] | [next] | [standalone]

#1443595

On Wed, Jul 13, 2016 at 4:02 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Wed, Jul 13, 2016 at 03:39:37PM -0700, John Stultz wrote:
>>
>> But otherwise both patches look great and are working well!
>>
>> Do you mind marking them both for stable 4.4+?
>
> OK, looks like it does qualify in the "fix a notable performance or
> interactivity issue" category.
>
>> Tested-by: John Stultz <john.stultz@linaro.org>
>> Acked-by: John Stultz <john.stultz@linaro.org>
>>
>> Also, do make sure Dmitry gets the reported-by credit for the first patch.
>
> Done!  The updated first patch is below, and the second will follow.

So just as a heads up, while this patch *greatly* improved the
situation, apparently the occasional 7ms spikes (again, much better
then 80ms!) still seen are causing trouble when compared w/ the 4.1 or
earlier kernels (which I think kept things sub-ms - Dmitry, please
correct me).

So I wanted to dampen my enthusiasm a touch for this, as there may yet
further improvements needed.  I'll try to get some more info on this
as soon as I have details.

thanks
-john

[toc] | [prev] | [next] | [standalone]

#1442919

On Wed, Jul 13, 2016 at 2:42 PM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Wed, Jul 13, 2016 at 02:18:41PM -0700, Paul E. McKenney wrote:
>> On Wed, Jul 13, 2016 at 05:05:26PM -0400, Tejun Heo wrote:
>> > On Wed, Jul 13, 2016 at 02:03:15PM -0700, Paul E. McKenney wrote:
>> > > Take the patch that I just sent out and make the choice of normal
>> > > vs. expedited depend on CONFIG_PREEMPT_RT or whatever the -rt guys are
>> > > calling it these days.  Is there a low-latency Kconfig option other
>> > > than CONFIG_NO_HZ_FULL?
>> >
>> > Sounds like a plan to me.
>>
>> I like the way we like each other's idea.  Mutually assured laziness?  ;-)
>
> But here is what mine might look like.  Untested, probably does
> not even build.  Note that the default is -no- expediting, use the
> rcusync.expedited kernel parameter to enable it.
>
>                                                         Thanx, Paul
>
> ------------------------------------------------------------------------
>
> diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt
> index 82b42c958d1c..b8bc9854e548 100644
> --- a/Documentation/kernel-parameters.txt
> +++ b/Documentation/kernel-parameters.txt
> @@ -3229,6 +3229,11 @@ bytes respectively. Such letter suffixes can also be entirely omitted.
>                         energy efficiency by requiring that the kthreads
>                         periodically wake up to do the polling.
>
> +       rcusync.expedited       [KNL]
> +                       Specify that the rcusync mechanism use expedited
> +                       grace periods.  As of mid-2016, this affects
> +                       per-CPU rwsems.
> +
>         rcutree.blimit= [KNL]
>                         Set maximum number of finished RCU callbacks to
>                         process in one batch.
> diff --git a/kernel/rcu/sync.c b/kernel/rcu/sync.c
> index be922c9f3d37..5bc5bef2e00a 100644
> --- a/kernel/rcu/sync.c
> +++ b/kernel/rcu/sync.c
> @@ -22,6 +22,14 @@
>
>  #include <linux/rcu_sync.h>
>  #include <linux/sched.h>
> +#include <linux/moduleparam.h>
> +#include <linux/module.h>
> +
> +MODULE_ALIAS("rcusync");
> +#ifdef MODULE_PARAM_PREFIX
> +#undef MODULE_PARAM_PREFIX
> +#endif
> +#define MODULE_PARAM_PREFIX "rcusync."
>
>  #ifdef CONFIG_PROVE_RCU
>  #define __INIT_HELD(func)      .held = func,
> @@ -29,7 +37,7 @@
>  #define __INIT_HELD(func)
>  #endif
>
> -static const struct {
> +static struct {
>         void (*sync)(void);
>         void (*call)(struct rcu_head *, void (*)(struct rcu_head *));
>         void (*wait)(void);
> @@ -62,6 +70,20 @@ enum { CB_IDLE = 0, CB_PENDING, CB_REPLAY };
>
>  #define        rss_lock        gp_wait.lock
>
> +static bool expedited;
> +module_param(expedited, bool, 0444);
> +
> +static int __init rcu_sync_early_init(void)
> +{
> +       if (expedited) {
> +               gp_ops[RCU_SYNC].sync = synchronize_rcu_expedited;
> +               gp_ops[RCU_SCHED_SYNC].sync = synchronize_sched_expedited;
> +               gp_ops[RCU_BH_SYNC].sync = synchronize_rcu_bh_expedited;
> +       }

So one minor nit here, with the config based default, you might want
to put some sort of informative message specifying that expidited was
used. This would help narrow down if it was or wasn't enabled when
folks see problems, since it wouldn't be otherwise obvious from a
dmesg log.

thanks
-john

[toc] | [prev] | [next] | [standalone]

#1442904

Hello, Paul.

On Wed, Jul 13, 2016 at 02:18:41PM -0700, Paul E. McKenney wrote:
> On Wed, Jul 13, 2016 at 05:05:26PM -0400, Tejun Heo wrote:
> > On Wed, Jul 13, 2016 at 02:03:15PM -0700, Paul E. McKenney wrote:
> > > Take the patch that I just sent out and make the choice of normal
> > > vs. expedited depend on CONFIG_PREEMPT_RT or whatever the -rt guys are
> > > calling it these days.  Is there a low-latency Kconfig option other
> > > than CONFIG_NO_HZ_FULL?
> > 
> > Sounds like a plan to me.
> 
> I like the way we like each other's idea.  Mutually assured laziness?  ;-)

Heh, indeed. :)

Technically, I think the lglock approach would be better here given
the combination of requirements; however, it's quite a bit more code
which would likely require some sophistications down the line (like
blocking new readers first at the start of down_write).  If we have to
go there, we'll go there but for now I think it'd be simpler to
conditionally switch to the expedited operations.  It can be a config
option which is selected by !RT as you suggested.  If anyone hits an
actual issue with that, we can go for the lglock thing.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1442922

On Wed, Jul 13, 2016 at 06:01:28PM -0400, Tejun Heo wrote:
> Hello, Paul.
> 
> On Wed, Jul 13, 2016 at 02:18:41PM -0700, Paul E. McKenney wrote:
> > On Wed, Jul 13, 2016 at 05:05:26PM -0400, Tejun Heo wrote:
> > > On Wed, Jul 13, 2016 at 02:03:15PM -0700, Paul E. McKenney wrote:
> > > > Take the patch that I just sent out and make the choice of normal
> > > > vs. expedited depend on CONFIG_PREEMPT_RT or whatever the -rt guys are
> > > > calling it these days.  Is there a low-latency Kconfig option other
> > > > than CONFIG_NO_HZ_FULL?
> > > 
> > > Sounds like a plan to me.
> > 
> > I like the way we like each other's idea.  Mutually assured laziness?  ;-)
> 
> Heh, indeed. :)
> 
> Technically, I think the lglock approach would be better here given
> the combination of requirements; however, it's quite a bit more code
> which would likely require some sophistications down the line (like
> blocking new readers first at the start of down_write).  If we have to
> go there, we'll go there but for now I think it'd be simpler to
> conditionally switch to the expedited operations.  It can be a config
> option which is selected by !RT as you suggested.  If anyone hits an
> actual issue with that, we can go for the lglock thing.

Fair enough!  ;-)

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1443109

On Wed, Jul 13, 2016 at 06:01:28PM -0400, Tejun Heo wrote:

> Technically, I think the lglock approach would be better here given
> the combination of requirements; however, it's quite a bit more code
> which would likely require some sophistications down the line (like
> blocking new readers first at the start of down_write). 

So the immediate problem with lg style locks is that the 'local' lock
will not stay local since these are preemptible locks we can get
migrations etc..

All fixable, but still.

> If we have to
> go there, we'll go there but for now I think it'd be simpler to
> conditionally switch to the expedited operations.  It can be a config
> option which is selected by !RT as you suggested.  If anyone hits an
> actual issue with that, we can go for the lglock thing.

So the main objection I have is that this isn't a fundamental fix, this
only cures things because Android only runs on small machines.

If someone with a big computer tries to do the same things we're up some
creek without no paddle. There's just no way we can make a global writer
'fast'.

[toc] | [prev] | [next] | [standalone]

#1443372

On Thu, Jul 14, 2016 at 08:49:56AM +0200, Peter Zijlstra wrote:
> On Wed, Jul 13, 2016 at 06:01:28PM -0400, Tejun Heo wrote:
> 
> > Technically, I think the lglock approach would be better here given
> > the combination of requirements; however, it's quite a bit more code
> > which would likely require some sophistications down the line (like
> > blocking new readers first at the start of down_write). 
> 
> So the immediate problem with lg style locks is that the 'local' lock
> will not stay local since these are preemptible locks we can get
> migrations etc..
> 
> All fixable, but still.

In this case, the locks are read-locked only across operations which
change process hierarchy.  They'll occasionally get migrated while
holding the lock for sure but not often enough to matter.

> > If we have to
> > go there, we'll go there but for now I think it'd be simpler to
> > conditionally switch to the expedited operations.  It can be a config
> > option which is selected by !RT as you suggested.  If anyone hits an
> > actual issue with that, we can go for the lglock thing.
> 
> So the main objection I have is that this isn't a fundamental fix, this
> only cures things because Android only runs on small machines.
>
> If someone with a big computer tries to do the same things we're up some
> creek without no paddle. There's just no way we can make a global writer
> 'fast'.

How so?  As the number of cores increases, it'll get proportionally
more expensive as the same operation is performed on more CPUs;
however, the latency is dependent on the slowest one and it'll get
higher more often with more number of CPUs but not drastically.
Latency won't go up proportionally with the number of CPUs.  For the
most part, we're paying more in terms of processing overhead, not
latency.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1443401

On Thu, Jul 14, 2016 at 07:20:46AM -0400, Tejun Heo wrote:
> On Thu, Jul 14, 2016 at 08:49:56AM +0200, Peter Zijlstra wrote:

> > So the immediate problem with lg style locks is that the 'local' lock
> > will not stay local since these are preemptible locks we can get
> > migrations etc..
> > 
> > All fixable, but still.
> 
> In this case, the locks are read-locked only across operations which
> change process hierarchy.  They'll occasionally get migrated while
> holding the lock for sure but not often enough to matter.

Means having to change the interface to pass along what 'local' is, like
srcu_read_lock().

> > So the main objection I have is that this isn't a fundamental fix, this
> > only cures things because Android only runs on small machines.
> >
> > If someone with a big computer tries to do the same things we're up some
> > creek without no paddle. There's just no way we can make a global writer
> > 'fast'.
> 
> How so?  As the number of cores increases, it'll get proportionally
> more expensive as the same operation is performed on more CPUs;
> however, the latency is dependent on the slowest one and it'll get
> higher more often with more number of CPUs but not drastically.

A global lock on 4 or 8 socket machines with all 200+ cpus trying to
use it really stinks.

Remember, they switch cgroups at really rather high rates here, because
of that binder stuff. I don't see how you can defend a global lock here
:/ Global locks only work when writers are extremely rare, and clearly
that premise is false.

Also note that since these are preemptible locks, you can get unbounded
priority inversions.

[toc] | [prev] | [next] | [standalone]

#1443517

On Thu, Jul 14, 2016 at 02:11:01PM +0200, Peter Zijlstra wrote:
> > How so?  As the number of cores increases, it'll get proportionally
> > more expensive as the same operation is performed on more CPUs;
> > however, the latency is dependent on the slowest one and it'll get
> > higher more often with more number of CPUs but not drastically.
> 
> A global lock on 4 or 8 socket machines with all 200+ cpus trying to
> use it really stinks.

That's why we're using percpu lock here.  With the right
implementation the write locking latency shouldn't be proportional to
the number of cores.  The total processing overhead could be.

> Remember, they switch cgroups at really rather high rates here, because
> of that binder stuff. I don't see how you can defend a global lock here
> :/ Global locks only work when writers are extremely rare, and clearly
> that premise is false.

This is one of the most eccentric uses and if I'm not mistaken they
were even doing memcg charge immigration on fore <-> background
switches which involve re-labeling each page.  And even with binder,
migration isn't nearly hot enough to matter for the most part even
when it's emitting IPIs globally.

We can split the locking but it just isn't necessary at this point.
More downsides than upsides.  If we actually need that, let's go
there.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1442853

On Wed, Jul 13, 2016 at 10:51:02PM +0200, Peter Zijlstra wrote:
> On Wed, Jul 13, 2016 at 04:39:44PM -0400, Tejun Heo wrote:
> So, IIRC, the trade-off is a full memory barrier in read_lock and
> read_unlock() vs sync_sched() in write.
>
> Full memory barriers are expensive and while the combined cost might
> well exceed the cost of the sync_sched() it doesn't suffer the latency
> issues.

Given the way read side is used for percpu_rwsem, full memory barrier
on reader side shouldn't matter at all.  The paths are not *that* hot.

> Not sure if we can frob the two in a single codebase, but I can have a
> poke if Oleg or Paul doesn't beat me to it.

At the simplest, it can be rwsem equivalence of lglock.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1442859

On Wed, Jul 13, 2016 at 10:51:02PM +0200, Peter Zijlstra wrote:
> On Wed, Jul 13, 2016 at 04:39:44PM -0400, Tejun Heo wrote:
> 
> > > There is a synchronize_sched() in there, so sorta. That thing is heavily
> > > geared towards readers, as is the only 'sane' choice for global locks.
> > 
> > It used to use the expedited variant until 001dac627ff3
> > ("locking/percpu-rwsem: Make use of the rcu_sync infrastructure"), so
> > it might have been okay before then.
> 
> Right, but expedited stuff sprays IPIs around the entire system. That's
> stuff other people complain about.

Do anyone other than the non-NO_HZ_FULL low-latency guys and the -rt
guys care?

> > The options that I can see are
> > 
> > 1. Somehow make percpu_rwsem's write behavior more responsive in a way
> >    which is acceptable all use cases.  This would be great but
> >    probably impossible.
> > 
> > 2. Add a fast-writer option to percpu_rwsem so that users which care
> >    about write latency can opt in for higher processing overhead for
> >    lower latency.
> 
> So, IIRC, the trade-off is a full memory barrier in read_lock and
> read_unlock() vs sync_sched() in write.
> 
> Full memory barriers are expensive and while the combined cost might
> well exceed the cost of the sync_sched() it doesn't suffer the latency
> issues.
> 
> Not sure if we can frob the two in a single codebase, but I can have a
> poke if Oleg or Paul doesn't beat me to it.

Take the patch that I just sent out and make the choice of normal
vs. expedited depend on CONFIG_PREEMPT_RT or whatever the -rt guys are
calling it these days.  Is there a low-latency Kconfig option other
than CONFIG_NO_HZ_FULL?

The memory-barrier approach can definitely be made to work, but is
going to be more complex due to the need to wait for readers.

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1443440

On Wed, Jul 13, 2016 at 10:51:02PM +0200, Peter Zijlstra wrote:
> So, IIRC, the trade-off is a full memory barrier in read_lock and
> read_unlock() vs sync_sched() in write.
> 
> Full memory barriers are expensive and while the combined cost might
> well exceed the cost of the sync_sched() it doesn't suffer the latency
> issues.
> 
> Not sure if we can frob the two in a single codebase, but I can have a
> poke if Oleg or Paul doesn't beat me to it.

OK, not too horrible if I say so myself :-)

The below is a compile tested only first draft so far. I'll go give it
some runtime next.


---
 fs/super.c                    |   3 +-
 include/linux/percpu-rwsem.h  |  96 +++++++++++++++--
 include/linux/rcu_sync.h      |   2 +-
 kernel/locking/percpu-rwsem.c | 243 +++++++++++++++++++++++++-----------------
 kernel/rcu/sync.c             |  15 +++
 5 files changed, 249 insertions(+), 110 deletions(-)

diff --git a/fs/super.c b/fs/super.c
index d78b9847e6cb..8ff18af7703f 100644
--- a/fs/super.c
+++ b/fs/super.c
@@ -195,7 +195,8 @@ static struct super_block *alloc_super(struct file_system_type *type, int flags)
 	for (i = 0; i < SB_FREEZE_LEVELS; i++) {
 		if (__percpu_init_rwsem(&s->s_writers.rw_sem[i],
 					sb_writers_name[i],
-					&type->s_writers_key[i]))
+					&type->s_writers_key[i],
+					PERCPU_RWSEM_READER))
 			goto fail;
 	}
 	init_waitqueue_head(&s->s_writers.wait_unfrozen);
diff --git a/include/linux/percpu-rwsem.h b/include/linux/percpu-rwsem.h
index c2fa3ecb0dce..5e1c2b029e3a 100644
--- a/include/linux/percpu-rwsem.h
+++ b/include/linux/percpu-rwsem.h
@@ -10,29 +10,107 @@
 
 struct percpu_rw_semaphore {
 	struct rcu_sync		rss;
-	unsigned int __percpu	*fast_read_ctr;
+	unsigned int __percpu	*refcount;
 	struct rw_semaphore	rw_sem;
-	atomic_t		slow_read_ctr;
-	wait_queue_head_t	write_waitq;
+	wait_queue_head_t	writer;
+	int			state;
 };
 
-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 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 *);
+
+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->refcount);
+	if (unlikely(!rcu_sync_is_idle(&sem->rss)))
+		__percpu_down_read(sem); /* 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->refcount);
+	if (unlikely(!rcu_sync_is_idle(&sem->rss)))
+		ret = __percpu_down_read_trylock(sem);
+	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->refcount);
+	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 *);
 
+enum percpu_rwsem_bias { PERCPU_RWSEM_READER, PERCPU_RWSEM_WRITER };
+
 extern int __percpu_init_rwsem(struct percpu_rw_semaphore *,
-				const char *, struct lock_class_key *);
+				const char *, struct lock_class_key *,
+				enum percpu_rwsem_bias bias);
+
 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,		\
+			    PERCPU_RWSEM_READER);		\
 })
 
+#define percpu_init_rwsem_writer(sem)				\
+({								\
+	static struct lock_class_key rwsem_key;			\
+	__percpu_init_rwsem(sem, #sem, &rwsem_key,i		\
+			    PERCPU_RWSEM_WRITER);		\
+})
 
 #define percpu_rwsem_is_held(sem) lockdep_is_held(&(sem)->rw_sem)
 
diff --git a/include/linux/rcu_sync.h b/include/linux/rcu_sync.h
index a63a33e6196e..e556baaf785e 100644
--- a/include/linux/rcu_sync.h
+++ b/include/linux/rcu_sync.h
@@ -26,7 +26,7 @@
 #include <linux/wait.h>
 #include <linux/rcupdate.h>
 
-enum rcu_sync_type { RCU_SYNC, RCU_SCHED_SYNC, RCU_BH_SYNC };
+enum rcu_sync_type { RCU_SYNC, RCU_SCHED_SYNC, RCU_BH_SYNC, RCU_NONE };
 
 /* Structure to mediate between updaters and fastpath-using readers.  */
 struct rcu_sync {
diff --git a/kernel/locking/percpu-rwsem.c b/kernel/locking/percpu-rwsem.c
index bec0b647f9cc..be37c7732b54 100644
--- a/kernel/locking/percpu-rwsem.c
+++ b/kernel/locking/percpu-rwsem.c
@@ -8,152 +8,197 @@
 #include <linux/sched.h>
 #include <linux/errno.h>
 
-int __percpu_init_rwsem(struct percpu_rw_semaphore *brw,
-			const char *name, struct lock_class_key *rwsem_key)
+enum { readers_slow, readers_block };
+
+int __percpu_init_rwsem(struct percpu_rw_semaphore *sem,
+			const char *name, struct lock_class_key *rwsem_key,
+			enum percpu_rwsem_bias bias)
 {
-	brw->fast_read_ctr = alloc_percpu(int);
-	if (unlikely(!brw->fast_read_ctr))
+	sem->refcount = alloc_percpu(int);
+	if (unlikely(!sem->refcount))
 		return -ENOMEM;
 
 	/* ->rw_sem represents the whole percpu_rw_semaphore for lockdep */
-	__init_rwsem(&brw->rw_sem, name, rwsem_key);
-	rcu_sync_init(&brw->rss, RCU_SCHED_SYNC);
-	atomic_set(&brw->slow_read_ctr, 0);
-	init_waitqueue_head(&brw->write_waitq);
+	rcu_sync_init(&sem->rss, bias == PERCPU_RWSEM_READER ? 
+				 RCU_SCHED_SYNC : 
+				 RCU_NONE);
+	__init_rwsem(&sem->rw_sem, name, rwsem_key);
+	init_waitqueue_head(&sem->writer);
+	sem->state = readers_slow;
 	return 0;
 }
 EXPORT_SYMBOL_GPL(__percpu_init_rwsem);
 
-void percpu_free_rwsem(struct percpu_rw_semaphore *brw)
+void percpu_free_rwsem(struct percpu_rw_semaphore *sem)
 {
 	/*
 	 * XXX: temporary kludge. The error path in alloc_super()
 	 * assumes that percpu_free_rwsem() is safe after kzalloc().
 	 */
-	if (!brw->fast_read_ctr)
+	if (!sem->refcount)
 		return;
 
-	rcu_sync_dtor(&brw->rss);
-	free_percpu(brw->fast_read_ctr);
-	brw->fast_read_ctr = NULL; /* catch use after free bugs */
+	rcu_sync_dtor(&sem->rss);
+	free_percpu(sem->refcount);
+	sem->refcount = NULL; /* catch use after free bugs */
 }
 EXPORT_SYMBOL_GPL(percpu_free_rwsem);
 
-/*
- * This is the fast-path for down_read/up_read. If it succeeds we rely
- * on the barriers provided by rcu_sync_enter/exit; see the comments in
- * percpu_down_write() and percpu_up_write().
- *
- * If this helper fails the callers rely on the normal rw_semaphore and
- * atomic_dec_and_test(), so in this case we have the necessary barriers.
- */
-static bool update_fast_ctr(struct percpu_rw_semaphore *brw, unsigned int val)
+void __percpu_down_read(struct percpu_rw_semaphore *sem)
 {
-	bool success;
+	/*
+	 * Due to having preemption disabled the decrement happens on
+	 * the same CPU as the increment, avoiding the
+	 * increment-on-one-CPU-and-decrement-on-another problem.
+	 *
+	 * And yes, if the reader misses the writer's assignment of
+	 * readers_block to sem->state, then the writer is
+	 * guaranteed to see the reader's increment.  Conversely, any
+	 * readers that increment their sem->refcount after the
+	 * writer looks are guaranteed to see the readers_block value,
+	 * which in turn means that they are guaranteed to immediately
+	 * decrement their sem->refcount, so that it doesn't matter
+	 * that the writer missed them.
+	 */
 
-	preempt_disable();
-	success = rcu_sync_is_idle(&brw->rss);
-	if (likely(success))
-		__this_cpu_add(*brw->fast_read_ctr, val);
-	preempt_enable();
+	smp_mb(); /* A matches D */
 
-	return success;
-}
+	/*
+	 * If !readers_block the critical section starts here, matched by the
+	 * release in percpu_up_write().
+	 */
+	if (likely(smp_load_acquire(&sem->state) != readers_block))
+		return;
 
-/*
- * Like the normal down_read() this is not recursive, the writer can
- * come after the first percpu_down_read() and create the deadlock.
- *
- * Note: returns with lock_is_held(brw->rw_sem) == T for lockdep,
- * percpu_up_read() does rwsem_release(). This pairs with the usage
- * of ->rw_sem in percpu_down/up_write().
- */
-void percpu_down_read(struct percpu_rw_semaphore *brw)
-{
-	might_sleep();
-	rwsem_acquire_read(&brw->rw_sem.dep_map, 0, 0, _RET_IP_);
+	/*
+	 * Per the above comment; we still have preemption disabled and
+	 * will thus decrement on the same CPU as we incremented.
+	 */
+	__percpu_up_read(sem);
 
-	if (likely(update_fast_ctr(brw, +1)))
-		return;
+	/*
+	 * We either call schedule() in the wait, or we'll fall through
+	 * and reschedule on the preempt_enable() in percpu_down_read().
+	 */
+	preempt_enable_no_resched();
+
+	/*
+	 * Avoid lockdep for the down/up_read() we already have them.
+	 */
+	__down_read(&sem->rw_sem);
+	__this_cpu_inc(*sem->refcount);
+	__up_read(&sem->rw_sem);
 
-	/* Avoid rwsem_acquire_read() and rwsem_release() */
-	__down_read(&brw->rw_sem);
-	atomic_inc(&brw->slow_read_ctr);
-	__up_read(&brw->rw_sem);
+	preempt_disable();
 }
-EXPORT_SYMBOL_GPL(percpu_down_read);
+EXPORT_SYMBOL_GPL(__percpu_down_read);
 
-int percpu_down_read_trylock(struct percpu_rw_semaphore *brw)
+int __percpu_down_read_trylock(struct percpu_rw_semaphore *sem)
 {
-	if (unlikely(!update_fast_ctr(brw, +1))) {
-		if (!__down_read_trylock(&brw->rw_sem))
-			return 0;
-		atomic_inc(&brw->slow_read_ctr);
-		__up_read(&brw->rw_sem);
-	}
-
-	rwsem_acquire_read(&brw->rw_sem.dep_map, 0, 1, _RET_IP_);
-	return 1;
+	smp_mb(); /* A matches D */
+
+	if (likely(smp_load_acquire(&sem->state) != readers_block))
+		return 1;
+
+	__percpu_up_read(sem);
+	return 0;
 }
+EXPORT_SYMBOL_GPL(__percpu_down_read_trylock);
 
-void percpu_up_read(struct percpu_rw_semaphore *brw)
+void __percpu_up_read(struct percpu_rw_semaphore *sem)
 {
-	rwsem_release(&brw->rw_sem.dep_map, 1, _RET_IP_);
-
-	if (likely(update_fast_ctr(brw, -1)))
-		return;
+	smp_mb(); /* B matches C */
+	/*
+	 * In other words, if they see our decrement (presumably to aggregate
+	 * zero, as that is the only time it matters) they will also see our
+	 * critical section.
+	 */
+	__this_cpu_dec(*sem->refcount);
 
-	/* false-positive is possible but harmless */
-	if (atomic_dec_and_test(&brw->slow_read_ctr))
-		wake_up_all(&brw->write_waitq);
+	/* Prod writer to recheck readers_active */
+	wake_up(&sem->writer);
 }
-EXPORT_SYMBOL_GPL(percpu_up_read);
+EXPORT_SYMBOL_GPL(__percpu_up_read);
+
+#define per_cpu_sum(var)						\
+({									\
+	typeof(var) __sum = 0;						\
+	int cpu;							\
+	compiletime_assert_atomic_type(__sum);				\
+	for_each_possible_cpu(cpu)					\
+		__sum += per_cpu(var, cpu);				\
+	__sum;								\
+})
 
-static int clear_fast_ctr(struct percpu_rw_semaphore *brw)
+/*
+ * Return true if the modular sum of the sem->refcount per-CPU variable is
+ * zero.  If this sum is zero, then it is stable due to the fact that if any
+ * newly arriving readers increment a given counter, they will immediately
+ * decrement that same counter.
+ */
+static bool readers_active_check(struct percpu_rw_semaphore *sem)
 {
-	unsigned int sum = 0;
-	int cpu;
+	if (per_cpu_sum(*sem->refcount) != 0)
+		return false;
+
+	/*
+	 * If we observed the decrement; ensure we see the entire critical
+	 * section.
+	 */
 
-	for_each_possible_cpu(cpu) {
-		sum += per_cpu(*brw->fast_read_ctr, cpu);
-		per_cpu(*brw->fast_read_ctr, cpu) = 0;
-	}
+	smp_mb(); /* C matches B */
 
-	return sum;
+	return true;
 }
 
-void percpu_down_write(struct percpu_rw_semaphore *brw)
+void percpu_down_write(struct percpu_rw_semaphore *sem)
 {
+	down_write(&sem->rw_sem);
+
+	/* Notify readers to take the slow path. */
+	rcu_sync_enter(&sem->rss);
+
 	/*
-	 * Make rcu_sync_is_idle() == F and thus disable the fast-path in
-	 * percpu_down_read() and percpu_up_read(), and wait for gp pass.
-	 *
-	 * The latter synchronises us with the preceding readers which used
-	 * the fast-past, so we can not miss the result of __this_cpu_add()
-	 * or anything else inside their criticial sections.
+	 * Notify new readers to block; up until now, and thus throughout the
+	 * longish rcu_sync_enter() above, new readers could still come in.
 	 */
-	rcu_sync_enter(&brw->rss);
+	sem->state = readers_block;
 
-	/* exclude other writers, and block the new readers completely */
-	down_write(&brw->rw_sem);
+	smp_mb(); /* D matches A */
 
-	/* nobody can use fast_read_ctr, move its sum into slow_read_ctr */
-	atomic_add(clear_fast_ctr(brw), &brw->slow_read_ctr);
+	/*
+	 * If they don't see our writer of readers_block to sem->state,
+	 * then we are guaranteed to see their sem->refcount increment, and
+	 * therefore will wait for them.
+	 */
 
-	/* wait for all readers to complete their percpu_up_read() */
-	wait_event(brw->write_waitq, !atomic_read(&brw->slow_read_ctr));
+	/* Wait for all now active readers to complete. */
+	wait_event(sem->writer, readers_active_check(sem));
 }
-EXPORT_SYMBOL_GPL(percpu_down_write);
 
-void percpu_up_write(struct percpu_rw_semaphore *brw)
+void percpu_up_write(struct percpu_rw_semaphore *sem)
 {
-	/* release the lock, but the readers can't use the fast-path */
-	up_write(&brw->rw_sem);
 	/*
-	 * Enable the fast-path in percpu_down_read() and percpu_up_read()
-	 * but only after another gp pass; this adds the necessary barrier
-	 * to ensure the reader can't miss the changes done by us.
+	 * Signal the writer is done, no fast path yet.
+	 *
+	 * One reason that we cannot just immediately flip to readers_fast is
+	 * that new readers might fail to see the results of this writer's
+	 * critical section.
+	 *
+	 * Therefore we force it through the slow path which guarantees an
+	 * acquire and thereby guarantees the critical section's consistency.
+	 */
+	smp_store_release(&sem->state, readers_slow);
+
+	/*
+	 * Release the write lock, this will allow readers back in the game.
+	 */
+	up_write(&sem->rw_sem);
+
+	/*
+	 * Once this completes (at least one RCU grace period hence) the reader
+	 * fast path will be available again. Safe to use outside the exclusive
+	 * write lock because its counting.
 	 */
-	rcu_sync_exit(&brw->rss);
+	rcu_sync_exit(&sem->rss);
 }
-EXPORT_SYMBOL_GPL(percpu_up_write);
diff --git a/kernel/rcu/sync.c b/kernel/rcu/sync.c
index be922c9f3d37..48055bf629af 100644
--- a/kernel/rcu/sync.c
+++ b/kernel/rcu/sync.c
@@ -55,6 +55,7 @@ static const struct {
 		.wait = rcu_barrier_bh,
 		__INIT_HELD(rcu_read_lock_bh_held)
 	},
+	[RCU_NONE] = { },
 };
 
 enum { GP_IDLE = 0, GP_PENDING, GP_PASSED };
@@ -65,6 +66,9 @@ enum { CB_IDLE = 0, CB_PENDING, CB_REPLAY };
 #ifdef CONFIG_PROVE_RCU
 void rcu_sync_lockdep_assert(struct rcu_sync *rsp)
 {
+	if (rsp->gp_type == RCU_NONE)
+		return;
+
 	RCU_LOCKDEP_WARN(!gp_ops[rsp->gp_type].held(),
 			 "suspicious rcu_sync_is_idle() usage");
 }
@@ -80,6 +84,8 @@ void rcu_sync_init(struct rcu_sync *rsp, enum rcu_sync_type type)
 	memset(rsp, 0, sizeof(*rsp));
 	init_waitqueue_head(&rsp->gp_wait);
 	rsp->gp_type = type;
+	if (rsp->gp_type == RCU_NONE)
+		rsp->gp_state = GP_PENDING; /* anything !0 */
 }
 
 /**
@@ -101,6 +107,9 @@ void rcu_sync_enter(struct rcu_sync *rsp)
 {
 	bool need_wait, need_sync;
 
+	if (rsp->gp_type == RCU_NONE)
+		return;
+
 	spin_lock_irq(&rsp->rss_lock);
 	need_wait = rsp->gp_count++;
 	need_sync = rsp->gp_state == GP_IDLE;
@@ -188,6 +197,9 @@ static void rcu_sync_func(struct rcu_head *rcu)
  */
 void rcu_sync_exit(struct rcu_sync *rsp)
 {
+	if (rsp->gp_type == RCU_NONE)
+		return;
+
 	spin_lock_irq(&rsp->rss_lock);
 	if (!--rsp->gp_count) {
 		if (rsp->cb_state == CB_IDLE) {
@@ -208,6 +220,9 @@ void rcu_sync_dtor(struct rcu_sync *rsp)
 {
 	int cb_state;
 
+	if (rsp->gp_type == RCU_NONE)
+		return;
+
 	BUG_ON(rsp->gp_count);
 
 	spin_lock_irq(&rsp->rss_lock);

[toc] | [prev] | [next] | [standalone]

#1443480

On Thu, Jul 14, 2016 at 03:18:09PM +0200, Peter Zijlstra wrote:
> On Wed, Jul 13, 2016 at 10:51:02PM +0200, Peter Zijlstra wrote:
> > So, IIRC, the trade-off is a full memory barrier in read_lock and
> > read_unlock() vs sync_sched() in write.
> > 
> > Full memory barriers are expensive and while the combined cost might
> > well exceed the cost of the sync_sched() it doesn't suffer the latency
> > issues.
> > 
> > Not sure if we can frob the two in a single codebase, but I can have a
> > poke if Oleg or Paul doesn't beat me to it.
> 
> OK, not too horrible if I say so myself :-)
> 
> The below is a compile tested only first draft so far. I'll go give it
> some runtime next.

Doesn't explode if I run:

root@ivb-ep:/cgroup# mkdir ponies; for ((i=0; i<60; i++)) ; do while :; do echo $$ > tasks; echo $$ > ponies/tasks ; done & done

with cgroup using either READER or WRITER bias.

So passes light torture.

[toc] | [prev] | [next] | [standalone]

#1443508

On 07/14, Peter Zijlstra wrote:
>
> OK, not too horrible if I say so myself :-)
>
> The below is a compile tested only first draft so far. I'll go give it
> some runtime next.

Yes, thanks.

But note that we do not need RCU_NONE. All we need is the trivial change
below. Damn, I am trying to find my old rcu-sync patches which I didn't
send, but can't... OK, this almost off-topic right now, just this "enter"
is ugly and we can't switch the slow/fast modes dynamically.

The rest of you patch is "optimize the slow path" and we already discussed
it before, I personally like it. Perhaps you can redo it without RCU_NONE
part?

Of course, this leads to another question: do we really need rcu-sync at
all, or should we change percpu-rwsem to always work in the "slow" mode
which is not that slow with your change... I'd like to keep it ;)

What do you think?

Oleg.

--- a/kernel/cgroup.c
+++ b/kernel/cgroup.c
@@ -5605,6 +5605,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);
+
 	get_user_ns(init_cgroup_ns.user_ns);
 
 	mutex_lock(&cgroup_mutex);

[toc] | [prev] | [next] | [standalone]

#1443565

On Thu, Jul 14, 2016 at 04:58:44PM +0200, Oleg Nesterov wrote:
> 
> Of course, this leads to another question: do we really need rcu-sync at
> all, or should we change percpu-rwsem to always work in the "slow" mode
> which is not that slow with your change... I'd like to keep it ;)
> 
> What do you think?

Yes, I think we wants to keep it. There are users where the read size
cost really are performance critical. I still have to repost that lglock
removal series for example, which replaces the fs/locks lglock with a
percpu-rwsem.

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4  Next page →

Back to top | Article view | linux.kernel

csiph-web