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

Groups > linux.kernel > #1443672 > unrolled thread

[PATCH 2/2] locking/percpu-rwsem: Introduce bias knob

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob Peter Zijlstra <peterz@infradead.org> - 2016-07-14 20:40 +0200
    Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob Oleg Nesterov <oleg@redhat.com> - 2016-07-14 20:50 +0200
      Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob Peter Zijlstra <peterz@infradead.org> - 2016-07-14 21:00 +0200
      Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob Peter Zijlstra <peterz@infradead.org> - 2016-07-14 21:30 +0200
        Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-14 21:30 +0200
          Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob Peter Zijlstra <peterz@infradead.org> - 2016-07-14 21:40 +0200
            Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-14 22:00 +0200
        Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob Oleg Nesterov <oleg@redhat.com> - 2016-07-15 15:30 +0200
          Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-15 15:40 +0200
            Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob Oleg Nesterov <oleg@redhat.com> - 2016-07-15 15:50 +0200
              Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-15 17:40 +0200
                Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob Oleg Nesterov <oleg@redhat.com> - 2016-07-15 18:50 +0200
                  Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-15 20:10 +0200
                    [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Oleg Nesterov <oleg@redhat.com> - 2016-07-16 19:20 +0200
                      Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Oleg Nesterov <oleg@redhat.com> - 2016-07-16 20:50 +0200
                      Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Peter Zijlstra <peterz@infradead.org> - 2016-07-18 14:00 +0200
                        Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Oleg Nesterov <oleg@redhat.com> - 2016-07-18 15:50 +0200
                      Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-19 23:00 +0200
                        Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Oleg Nesterov <oleg@redhat.com> - 2016-07-20 17:20 +0200
                          Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-20 23:00 +0200
                            Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Oleg Nesterov <oleg@redhat.com> - 2016-07-21 19:40 +0200
                        Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Oleg Nesterov <oleg@redhat.com> - 2016-07-20 19:20 +0200
                          Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-20 23:40 +0200
                            Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Oleg Nesterov <oleg@redhat.com> - 2016-07-21 19:40 +0200
                              Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-22 05:30 +0200
                                Re: [PATCH] rcu_sync: simplify the state machine, introduce __rcu_sync_enter() John Stultz <john.stultz@linaro.org> - 2016-07-25 19:10 +0200
                                  Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Oleg Nesterov <oleg@redhat.com> - 2016-07-25 19:30 +0200
                                Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() Oleg Nesterov <oleg@redhat.com> - 2016-07-25 19:10 +0200
                                  Re: [PATCH] rcu_sync: simplify the state machine, introduce  __rcu_sync_enter() "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2016-07-25 19:50 +0200
        Re: [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob Oleg Nesterov <oleg@redhat.com> - 2016-07-15 15:50 +0200

Page 1 of 2  [1] 2  Next page →

#1443672 — [PATCH 2/2] locking/percpu-rwsem: Introduce bias knob

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

The latency of the synchronize_sched() is too high for some users
(cgroups), so provide a __percpu_init_rwsem(.bias) argument to forgot
this synchronize_sched() at the cost of forcing all readers into the
slow path, which has serializing instructions.

Cc: Tejun Heo <tj@kernel.org>
Cc: Oleg Nesterov <oleg@redhat.com>
Cc: Paul McKenney <paulmck@linux.vnet.ibm.com>
Reported-by: John Stultz <john.stultz@linaro.org>
Reported-by: Dmitry Shmidt <dimitrysh@google.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 fs/super.c                    |    3 ++-
 include/linux/percpu-rwsem.h  |   15 +++++++++++++--
 kernel/cgroup.c               |    2 +-
 kernel/locking/percpu-rwsem.c |   10 +++++++++-
 4 files changed, 25 insertions(+), 5 deletions(-)

--- a/fs/super.c
+++ b/fs/super.c
@@ -195,7 +195,8 @@ static struct super_block *alloc_super(s
 	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);
--- a/include/linux/percpu-rwsem.h
+++ b/include/linux/percpu-rwsem.h
@@ -90,15 +90,26 @@ static inline void percpu_up_read(struct
 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(sem)					\
 ({								\
 	static struct lock_class_key rwsem_key;			\
-	__percpu_init_rwsem(sem, #sem, &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,		\
+			    PERCPU_RWSEM_WRITER);		\
 })
 
 #define percpu_rwsem_is_held(sem) lockdep_is_held(&(sem)->rw_sem)
--- a/kernel/cgroup.c
+++ b/kernel/cgroup.c
@@ -5605,7 +5605,7 @@ int __init cgroup_init(void)
 	int ssid;
 
 	BUILD_BUG_ON(CGROUP_SUBSYS_COUNT > 16);
-	BUG_ON(percpu_init_rwsem(&cgroup_threadgroup_rwsem));
+	BUG_ON(percpu_init_rwsem_writer(&cgroup_threadgroup_rwsem));
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_dfl_base_files));
 	BUG_ON(cgroup_init_cftypes(NULL, cgroup_legacy_base_files));
 
--- a/kernel/locking/percpu-rwsem.c
+++ b/kernel/locking/percpu-rwsem.c
@@ -11,7 +11,8 @@
 enum { readers_slow, readers_block };
 
 int __percpu_init_rwsem(struct percpu_rw_semaphore *sem,
-			const char *name, struct lock_class_key *rwsem_key)
+			const char *name, struct lock_class_key *rwsem_key,
+			enum percpu_rwsem_bias bias)
 {
 	sem->read_count = alloc_percpu(int);
 	if (unlikely(!sem->read_count))
@@ -19,6 +20,13 @@ int __percpu_init_rwsem(struct percpu_rw
 
 	/* ->rw_sem represents the whole percpu_rw_semaphore for lockdep */
 	rcu_sync_init(&sem->rss, RCU_SCHED_SYNC);
+	if (bias == PERCPU_RWSEM_WRITER) {
+		/*
+		 * Disable rcu_sync() and force slow path.
+		 */
+		sem->rss.gp_count++;
+		sem->rss.gp_state = !0;
+	}
 	__init_rwsem(&sem->rw_sem, name, rwsem_key);
 	init_waitqueue_head(&sem->writer);
 	sem->state = readers_slow;

[toc] | [next] | [standalone]

#1443691

On 07/14, Peter Zijlstra wrote:
>
> The current percpu-rwsem read side is entirely free of serializing
> instructions at the cost of having a synchronize_sched() in the write
> path.
>
> The latency of the synchronize_sched() is too high for some users
> (cgroups), so provide a __percpu_init_rwsem(.bias) argument to forgot
> this synchronize_sched() at the cost of forcing all readers into the
> slow path, which has serializing instructions.

Oh well... I personally do not think this is what we want... Can't
we just add the stupid rcu_sync_enter() into cgroup_init() at least
for now? Yes, this means the unnecessary .sync() at boot time, but
it will go away after cleanups I am going to send.

Because, again, we will probably want to change this bias dynamically.

Oleg.

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

#1443698

On Thu, Jul 14, 2016 at 08:43:51PM +0200, Oleg Nesterov wrote:
> On 07/14, Peter Zijlstra wrote:
> >
> > The current percpu-rwsem read side is entirely free of serializing
> > instructions at the cost of having a synchronize_sched() in the write
> > path.
> >
> > The latency of the synchronize_sched() is too high for some users
> > (cgroups), so provide a __percpu_init_rwsem(.bias) argument to forgot
> > this synchronize_sched() at the cost of forcing all readers into the
> > slow path, which has serializing instructions.
> 
> Oh well... I personally do not think this is what we want... Can't
> we just add the stupid rcu_sync_enter() into cgroup_init() at least
> for now? 

> Yes, this means the unnecessary .sync() at boot time, but
> it will go away after cleanups I am going to send.

Those would have to hit the same merge window though; some people (like
Arjan) really care about boot times and hunt and kill people adding
pointless delays..

> Because, again, we will probably want to change this bias dynamically.

Hmm, how so?

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

#1443714

On Thu, Jul 14, 2016 at 08:43:51PM +0200, Oleg Nesterov wrote:
> 
> Oh well... I personally do not think this is what we want... Can't
> we just add the stupid rcu_sync_enter() into cgroup_init() at least
> for now? Yes, this means the unnecessary .sync() at boot time, but
> it will go away after cleanups I am going to send.

Something like so then?

---
--- a/include/linux/rcu_sync.h
+++ b/include/linux/rcu_sync.h
@@ -59,6 +59,7 @@ static inline bool rcu_sync_is_idle(stru
 }
 
 extern void rcu_sync_init(struct rcu_sync *, enum rcu_sync_type);
+extern void rcu_sync_sabotage(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 *);
--- a/kernel/cgroup.c
+++ b/kernel/cgroup.c
@@ -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_sabotage(&cgroup_threadgroup_rwsem.rss);
+
 	get_user_ns(init_cgroup_ns.user_ns);
 
 	mutex_lock(&cgroup_mutex);
--- a/kernel/rcu/sync.c
+++ b/kernel/rcu/sync.c
@@ -83,6 +83,21 @@ void rcu_sync_init(struct rcu_sync *rsp,
 }
 
 /**
+ * rcu_sync_sabotage() - Sabotage a fresh rcu_sync instance
+ * @rsp: Pointer to rcu_sync structure to be sabotaged
+ *
+ * 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_sabotage(struct rcu_sync *rsp)
+{
+	rsp->gp_count++;
+	rsp->gp_state = !GP_IDLE;
+}
+
+/**
  * rcu_sync_enter() - Force readers onto slowpath
  * @rsp: Pointer to rcu_sync structure to use for synchronization
  *

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

#1443716

On Thu, Jul 14, 2016 at 09:20:18PM +0200, Peter Zijlstra wrote:
> On Thu, Jul 14, 2016 at 08:43:51PM +0200, Oleg Nesterov wrote:
> > 
> > Oh well... I personally do not think this is what we want... Can't
> > we just add the stupid rcu_sync_enter() into cgroup_init() at least
> > for now? Yes, this means the unnecessary .sync() at boot time, but
> > it will go away after cleanups I am going to send.
> 
> Something like so then?
> 
> ---
> --- a/include/linux/rcu_sync.h
> +++ b/include/linux/rcu_sync.h
> @@ -59,6 +59,7 @@ static inline bool rcu_sync_is_idle(stru
>  }
> 
>  extern void rcu_sync_init(struct rcu_sync *, enum rcu_sync_type);
> +extern void rcu_sync_sabotage(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 *);
> --- a/kernel/cgroup.c
> +++ b/kernel/cgroup.c
> @@ -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_sabotage(&cgroup_threadgroup_rwsem.rss);

With a name like that...

> +
>  	get_user_ns(init_cgroup_ns.user_ns);
> 
>  	mutex_lock(&cgroup_mutex);
> --- a/kernel/rcu/sync.c
> +++ b/kernel/rcu/sync.c
> @@ -83,6 +83,21 @@ void rcu_sync_init(struct rcu_sync *rsp,
>  }
> 
>  /**
> + * rcu_sync_sabotage() - Sabotage a fresh rcu_sync instance
> + * @rsp: Pointer to rcu_sync structure to be sabotaged
> + *
> + * 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_sabotage(struct rcu_sync *rsp)
> +{
> +	rsp->gp_count++;
> +	rsp->gp_state = !GP_IDLE;

???  A very strange way to say GP_PENDING.  A new GP_DISABLED, perhaps?

							Thanx, Paul

> +}
> +
> +/**
>   * rcu_sync_enter() - Force readers onto slowpath
>   * @rsp: Pointer to rcu_sync structure to use for synchronization
>   *
> 

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

#1443718

On Thu, Jul 14, 2016 at 12:29:59PM -0700, Paul E. McKenney wrote:
> On Thu, Jul 14, 2016 at 09:20:18PM +0200, Peter Zijlstra wrote:
> >  /**
> > + * rcu_sync_sabotage() - Sabotage a fresh rcu_sync instance
> > + * @rsp: Pointer to rcu_sync structure to be sabotaged
> > + *
> > + * 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_sabotage(struct rcu_sync *rsp)
> > +{
> > +	rsp->gp_count++;
> > +	rsp->gp_state = !GP_IDLE;
> 
> ???  A very strange way to say GP_PENDING.  A new GP_DISABLED, perhaps?

Right, so the important thing is that its not GP_IDLE, the rest doesn't
really matter.

This forces rcu_sync_is_idle() to return false. The skewed gp_count
ensures rcu_sync_{enter,exit}() pairs no-op.

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

#1443724

On Thu, Jul 14, 2016 at 09:38:00PM +0200, Peter Zijlstra wrote:
> On Thu, Jul 14, 2016 at 12:29:59PM -0700, Paul E. McKenney wrote:
> > On Thu, Jul 14, 2016 at 09:20:18PM +0200, Peter Zijlstra wrote:
> > >  /**
> > > + * rcu_sync_sabotage() - Sabotage a fresh rcu_sync instance
> > > + * @rsp: Pointer to rcu_sync structure to be sabotaged
> > > + *
> > > + * 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_sabotage(struct rcu_sync *rsp)
> > > +{
> > > +	rsp->gp_count++;
> > > +	rsp->gp_state = !GP_IDLE;
> > 
> > ???  A very strange way to say GP_PENDING.  A new GP_DISABLED, perhaps?
> 
> Right, so the important thing is that its not GP_IDLE, the rest doesn't
> really matter.
> 
> This forces rcu_sync_is_idle() to return false. The skewed gp_count
> ensures rcu_sync_{enter,exit}() pairs no-op.

Understood.  But let's have at least some pity on the poor people who
might one day read this code.

							Thanx, Paul

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

#1444322

On 07/14, Peter Zijlstra wrote:
>
> On Thu, Jul 14, 2016 at 08:43:51PM +0200, Oleg Nesterov wrote:
> >
> > Oh well... I personally do not think this is what we want... Can't
> > we just add the stupid rcu_sync_enter() into cgroup_init() at least
> > for now? Yes, this means the unnecessary .sync() at boot time, but
> > it will go away after cleanups I am going to send.
>
> Something like so then?

OK, agreed,

> ---
> --- a/include/linux/rcu_sync.h
> +++ b/include/linux/rcu_sync.h
> @@ -59,6 +59,7 @@ static inline bool rcu_sync_is_idle(stru
>  }
>
>  extern void rcu_sync_init(struct rcu_sync *, enum rcu_sync_type);
> +extern void rcu_sync_sabotage(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 *);
> --- a/kernel/cgroup.c
> +++ b/kernel/cgroup.c
> @@ -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_sabotage(&cgroup_threadgroup_rwsem.rss);

Heh ;) I too think it should be renamed. I'd suggest

	__rcu_sync_enter(rss);

although I do not really mind and agree with any name.

Hopefully I'll send some cleanups soon, rcu_sync_enter() will be
re-implemented as

	rcu_sync_enter(rss)
	{
		if (__rcu_sync_enter(rss))
			__rcu_sync_wait(rss);
	}

> + * rcu_sync_sabotage() - Sabotage a fresh rcu_sync instance
> + * @rsp: Pointer to rcu_sync structure to be sabotaged
> + *
> + * Must be called after rcu_sync_init() and before first use.

OK. And after those cleanups __rcu_sync_enter() can be called at any
time.

Oleg.

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

#1444326

On Fri, Jul 15, 2016 at 03:27:09PM +0200, Oleg Nesterov wrote:
> On 07/14, Peter Zijlstra wrote:
> >
> > On Thu, Jul 14, 2016 at 08:43:51PM +0200, Oleg Nesterov wrote:
> > >
> > > Oh well... I personally do not think this is what we want... Can't
> > > we just add the stupid rcu_sync_enter() into cgroup_init() at least
> > > for now? Yes, this means the unnecessary .sync() at boot time, but
> > > it will go away after cleanups I am going to send.
> >
> > Something like so then?
> 
> OK, agreed,
> 
> > ---
> > --- a/include/linux/rcu_sync.h
> > +++ b/include/linux/rcu_sync.h
> > @@ -59,6 +59,7 @@ static inline bool rcu_sync_is_idle(stru
> >  }
> >
> >  extern void rcu_sync_init(struct rcu_sync *, enum rcu_sync_type);
> > +extern void rcu_sync_sabotage(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 *);
> > --- a/kernel/cgroup.c
> > +++ b/kernel/cgroup.c
> > @@ -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_sabotage(&cgroup_threadgroup_rwsem.rss);
> 
> Heh ;) I too think it should be renamed. I'd suggest
> 
> 	__rcu_sync_enter(rss);
> 
> although I do not really mind and agree with any name.

Hmmm...  Why not just move the checks out into the caller?  That
would make the intent much more clear.

							Thanx, Paul

> Hopefully I'll send some cleanups soon, rcu_sync_enter() will be
> re-implemented as
> 
> 	rcu_sync_enter(rss)
> 	{
> 		if (__rcu_sync_enter(rss))
> 			__rcu_sync_wait(rss);
> 	}
> 
> > + * rcu_sync_sabotage() - Sabotage a fresh rcu_sync instance
> > + * @rsp: Pointer to rcu_sync structure to be sabotaged
> > + *
> > + * Must be called after rcu_sync_init() and before first use.
> 
> OK. And after those cleanups __rcu_sync_enter() can be called at any
> time.
> 
> Oleg.
> 

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

#1444335

On 07/15, Paul E. McKenney wrote:
>
> On Fri, Jul 15, 2016 at 03:27:09PM +0200, Oleg Nesterov wrote:
> >
> > Heh ;) I too think it should be renamed. I'd suggest
> >
> > 	__rcu_sync_enter(rss);
> >
> > although I do not really mind and agree with any name.
>
> Hmmm...  Why not just move the checks out into the caller?  That
> would make the intent much more clear.

Hmm. which caller?

Oleg.

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

#1444382

On Fri, Jul 15, 2016 at 03:45:24PM +0200, Oleg Nesterov wrote:
> On 07/15, Paul E. McKenney wrote:
> >
> > On Fri, Jul 15, 2016 at 03:27:09PM +0200, Oleg Nesterov wrote:
> > >
> > > Heh ;) I too think it should be renamed. I'd suggest
> > >
> > > 	__rcu_sync_enter(rss);
> > >
> > > although I do not really mind and agree with any name.
> >
> > Hmmm...  Why not just move the checks out into the caller?  That
> > would make the intent much more clear.
> 
> Hmm. which caller?

The ones associated with a percpu_rwsem_bias of PERCPU_RWSEM_READER.

							Thanx, Paul

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

#1444444

On 07/15, Paul E. McKenney wrote:
> On Fri, Jul 15, 2016 at 03:45:24PM +0200, Oleg Nesterov wrote:
> > On 07/15, Paul E. McKenney wrote:
> > >
> > > On Fri, Jul 15, 2016 at 03:27:09PM +0200, Oleg Nesterov wrote:
> > > >
> > > > Heh ;) I too think it should be renamed. I'd suggest
> > > >
> > > > 	__rcu_sync_enter(rss);
> > > >
> > > > although I do not really mind and agree with any name.
> > >
> > > Hmmm...  Why not just move the checks out into the caller?  That
> > > would make the intent much more clear.
> >
> > Hmm. which caller?
>
> The ones associated with a percpu_rwsem_bias of PERCPU_RWSEM_READER.

Ah. But if we add __rcu_sync_enter() instead of bias/PERCPU_RWSEM_READER.

IOW, please ignore 2/2 which adds PERCPU_RWSEM_READER, the new version
just adds rcu_sync_sabotage() which should be renamed (and use GP_PASSED).

Oleg.

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

#1444494

On Fri, Jul 15, 2016 at 06:49:39PM +0200, Oleg Nesterov wrote:
> On 07/15, Paul E. McKenney wrote:
> > On Fri, Jul 15, 2016 at 03:45:24PM +0200, Oleg Nesterov wrote:
> > > On 07/15, Paul E. McKenney wrote:
> > > >
> > > > On Fri, Jul 15, 2016 at 03:27:09PM +0200, Oleg Nesterov wrote:
> > > > >
> > > > > Heh ;) I too think it should be renamed. I'd suggest
> > > > >
> > > > > 	__rcu_sync_enter(rss);
> > > > >
> > > > > although I do not really mind and agree with any name.
> > > >
> > > > Hmmm...  Why not just move the checks out into the caller?  That
> > > > would make the intent much more clear.
> > >
> > > Hmm. which caller?
> >
> > The ones associated with a percpu_rwsem_bias of PERCPU_RWSEM_READER.
> 
> Ah. But if we add __rcu_sync_enter() instead of bias/PERCPU_RWSEM_READER.
> 
> IOW, please ignore 2/2 which adds PERCPU_RWSEM_READER, the new version
> just adds rcu_sync_sabotage() which should be renamed (and use GP_PASSED).

OK, then move the checks out into the callers that would have used
__rcu_sync_enter().  ;-)

							Thanx, Paul

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

#1444890 — [PATCH] rcu_sync: simplify the state machine, introduce __rcu_sync_enter()

On 07/15, Paul E. McKenney wrote:
>
> On Fri, Jul 15, 2016 at 06:49:39PM +0200, Oleg Nesterov wrote:
> >
> > IOW, please ignore 2/2 which adds PERCPU_RWSEM_READER, the new version
> > just adds rcu_sync_sabotage() which should be renamed (and use GP_PASSED).
>
> OK, then move the checks out into the callers that would have used
> __rcu_sync_enter().  ;-)

Cough, now I can't understand which check do you mean ;) OK, let me
show the code, then we will hopefully understand each other.

----------------------------------------------------------------------
So, as you can see I have fooled you ;) I'll send the patch on top of
Peter's changes, this is the (UNTESTED) code with the patch applied.

Peter, Paul, could you review? Do you see any hole?

Why. Firstly, note that the state machine was greatly simplified, and
rsp->cb_state has gone, we have a single "state" variable, gp_state.
Note also the ->sync() op has gone (and actually ->wait() too, see the
"TODO" comment).

GP_IDLE	- owned by __rcu_sync_enter() which can only move this state to

GP_ENTER - owned by rcu-callback which moves it to

GP_PASSED - owned by the last rcu_sync_exit() which moves it to

GP_EXIT - owned by rcu-callback which moves it back to GP_IDLE.

Yes, this is a bit simplified, we also have GP_REPLAY, but hopefully
clear.

And, there is another possible transition, GP_ENTER -> GP_IDLE, because
not it is possible to call __rcu_sync_enter() and rcu_sync_exit() in any
state (except obviously they should be balanced), and they do not block.

The only blocking call is __rcu_sync_wait() which actually waits for GP.
Obviously should only be called if gp_count != 0, iow after __rcu_sync_enter.


--------------------------------------------------------------------------
Now, cgroup_init() can simply call __rcu_sync_enter(&cgroup_threadgroup_rwsem)
and switch this sem into the slow mode. Compared to "sabotage" from Peter
this implies the unnecessary call_rcu_sched(), but I hope we can tolerate
this.

And we can even add a runtime knob to switch between "fast" and "slow
aka writer-biased" modes for cgroup_threadgroup_rwsem.

--------------------------------------------------------------------------
And I think __rcu_sync_enter() can have more users. Let's look at
freeze_super(). It calls percpu_down_write() 3 times, and waits for 3 GP's
sequentally.

Now we can add 3 __rcu_sync_enter's at the start and 3 rcu_sync_exit's at
the end (actually we can do better, just to simplify). And again, note
that rcu_sync_exit() will work correctly even if we (say) return -EBUSY,
so rcu_sync_wait and/or percpu_down_write() was not called in between,
and in this case we won't block waiting for GP.

What do you think?

Oleg.
---

// rcu_sync.h: ----------------------------------------------------------------

struct rcu_sync {
	int			gp_state;
	int			gp_count;
	wait_queue_head_t	gp_wait;

	struct rcu_head		cb_head;
	enum rcu_sync_type	gp_type;
};

// sync.c ---------------------------------------------------------------------
#include <linux/rcu_sync.h>
#include <linux/sched.h>

#ifdef CONFIG_PROVE_RCU
#define __INIT_HELD(func)	.held = func,
#else
#define __INIT_HELD(func)
#endif

static const struct {
	void (*call)(struct rcu_head *, void (*)(struct rcu_head *));
	void (*wait)(void);	// TODO: remove this, see the comment in dtor
#ifdef CONFIG_PROVE_RCU
	int  (*held)(void);
#endif
} gp_ops[] = {
	[RCU_SYNC] = {
		.call = call_rcu,
		.wait = rcu_barrier,
		__INIT_HELD(rcu_read_lock_held)
	},
	[RCU_SCHED_SYNC] = {
		.call = call_rcu_sched,
		.wait = rcu_barrier_sched,
		__INIT_HELD(rcu_read_lock_sched_held)
	},
	[RCU_BH_SYNC] = {
		.call = call_rcu_bh,
		.wait = rcu_barrier_bh,
		__INIT_HELD(rcu_read_lock_bh_held)
	},
};

#define	rss_lock	gp_wait.lock

enum { GP_IDLE = 0, GP_ENTER, GP_PASSED, GP_EXIT, GP_REPLAY };

static void rcu_sync_func(struct rcu_head *rcu);

static void rcu_sync_call(struct rcu_sync *rsp)
{
	// TODO: THIS IS SUBOPTIMAL. We want to call it directly
	// if rcu_blocking_is_gp() == T, but it has might_sleep().
	gp_ops[rsp->gp_type].call(&rsp->cb_head, rcu_sync_func);
}

static void rcu_sync_func(struct rcu_head *rcu)
{
	struct rcu_sync *rsp = container_of(rcu, struct rcu_sync, cb_head);
	unsigned long flags;

	BUG_ON(rsp->gp_state == GP_IDLE);
	BUG_ON(rsp->gp_state == GP_PASSED);

	spin_lock_irqsave(&rsp->rss_lock, flags);
	if (rsp->gp_count) {
		/*
		 * We're at least a GP after the first __rcu_sync_enter().
		 */
		rsp->gp_state = GP_PASSED;
	} else if (rsp->gp_state == GP_REPLAY) {
		/*
		 * A new rcu_sync_exit() has happened; requeue the callback
		 * to catch a later GP.
		 */
		rsp->gp_state = GP_EXIT;
		rcu_sync_call(rsp);
	} else {
		/*
		 * We're at least a GP after the last rcu_sync_exit();
		 * eveybody will now have observed the write side critical
		 * section. Let 'em rip!.
		 *
		 * OR. ->gp_state can be still GP_ENTER if __rcu_sync_wait()
		 * wasn't called after __rcu_sync_enter(), abort.
		 */
		rsp->gp_state = GP_IDLE;
	}
	spin_unlock_irqrestore(&rsp->rss_lock, flags);
}

bool __rcu_sync_enter(struct rcu_sync *rsp)
{
	int gp_count, gp_state;

	spin_lock_irq(&rsp->rss_lock);
	gp_count = rsp->gp_count++;
	gp_state = rsp->gp_state;
	if (gp_state == GP_IDLE) {
		rsp->gp_state = GP_ENTER;
		rcu_sync_call(rsp);
	}
	spin_unlock_irq(&rsp->rss_lock);

	BUG_ON(gp_count != 0 && gp_state == GP_IDLE);
	BUG_ON(gp_count == 0 && gp_state == GP_PASSED);

	return gp_state < GP_PASSED;
}

void __rcu_sync_wait(struct rcu_sync *rsp)
{
	BUG_ON(rsp->gp_state == GP_IDLE);
	BUG_ON(rsp->gp_count == 0);

	wait_event(rsp->gp_wait, rsp->gp_state >= GP_PASSED);
}

void rcu_sync_enter(struct rcu_sync *rsp)
{
	if (__rcu_sync_enter(rsp))
		__rcu_sync_wait(rsp);
}

void rcu_sync_exit(struct rcu_sync *rsp)
{
	BUG_ON(rsp->gp_state == GP_IDLE);
	BUG_ON(rsp->gp_count == 0);

	spin_lock_irq(&rsp->rss_lock);
	if (!--rsp->gp_count) {
		if (rsp->gp_state == GP_PASSED) {
			rsp->gp_state = GP_EXIT;
			rcu_sync_call(rsp);
		} else if (rsp->gp_state == GP_EXIT) {
			rsp->gp_state = GP_REPLAY;
		}
	}
	spin_unlock_irq(&rsp->rss_lock);
}

void rcu_sync_dtor(struct rcu_sync *rsp)
{
	int gp_state;

	BUG_ON(rsp->gp_count);
	BUG_ON(rsp->gp_state == GP_PASSED);

	spin_lock_irq(&rsp->rss_lock);
	if (rsp->gp_state == GP_REPLAY)
		rsp->gp_state = GP_EXIT;
	gp_state = rsp->gp_state;
	spin_unlock_irq(&rsp->rss_lock);

	// TODO: add another wake_up_locked() into rcu_sync_func(),
	// use wait_event + spin_lock_wait, remove gp_ops->wait().
	if (gp_state != GP_IDLE) {
		gp_ops[rsp->gp_type].wait();
		BUG_ON(rsp->gp_state != GP_IDLE);
	}
}

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

#1444897 — Re: [PATCH] rcu_sync: simplify the state machine, introduce __rcu_sync_enter()

Damn, sorry for noise...

On 07/16, Oleg Nesterov wrote:
>
> And, there is another possible transition, GP_ENTER -> GP_IDLE, because
> not it is possible to call __rcu_sync_enter() and rcu_sync_exit() in any
  ^^^
I tried to say "now it is possible ..."

Oleg.

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

#1445415 — Re: [PATCH] rcu_sync: simplify the state machine, introduce __rcu_sync_enter()

On Sat, Jul 16, 2016 at 07:10:07PM +0200, Oleg Nesterov wrote:
> Peter, Paul, could you review? Do you see any hole?
> 
> Why. Firstly, note that the state machine was greatly simplified, and
> rsp->cb_state has gone, we have a single "state" variable, gp_state.
> Note also the ->sync() op has gone (and actually ->wait() too, see the
> "TODO" comment).

Yes, that seems like a nice simplification.

> GP_IDLE	- owned by __rcu_sync_enter() which can only move this state to
> 
> GP_ENTER - owned by rcu-callback which moves it to
> 
> GP_PASSED - owned by the last rcu_sync_exit() which moves it to
> 
> GP_EXIT - owned by rcu-callback which moves it back to GP_IDLE.
> 
> Yes, this is a bit simplified, we also have GP_REPLAY, but hopefully
> clear.
> 
> And, there is another possible transition, GP_ENTER -> GP_IDLE, because
> not it is possible to call __rcu_sync_enter() and rcu_sync_exit() in any
> state (except obviously they should be balanced), and they do not block.
> 
> The only blocking call is __rcu_sync_wait() which actually waits for GP.
> Obviously should only be called if gp_count != 0, iow after __rcu_sync_enter.

So I'm a complete moron today, to aid the failing brain I draw pictures.

I think I ended up with this:

 .---->	GP_IDLE <--------------.
 |	  |                    |
 |	  | __rcu_sync_enter() | <GP> / rcu_sync_exit()
 |	  v                    |
 |	GP_ENTER --------------'
 |	  |
 |  <GP>  |
 |        v
 |	GP_PASSED <---------.
 |	  |                 |
 |	  | rcu_sync_exit() | <GP> / __rcu_sync_enter()
 |	  v                 |
 `----- GP_EXIT ------------'
	  ^
    <GP>  | __rcu_sync_enter() + rcu_sync_exit()
	  v
	GP_RETRY


> enum { GP_IDLE = 0, GP_ENTER, GP_PASSED, GP_EXIT, GP_REPLAY };
> 
> static void rcu_sync_func(struct rcu_head *rcu);
> 
> static void rcu_sync_call(struct rcu_sync *rsp)
> {
> 	// TODO: THIS IS SUBOPTIMAL. We want to call it directly
> 	// if rcu_blocking_is_gp() == T, but it has might_sleep().

Not sure I get that comment..

> 	gp_ops[rsp->gp_type].call(&rsp->cb_head, rcu_sync_func);
> }
> 
> static void rcu_sync_func(struct rcu_head *rcu)
> {
> 	struct rcu_sync *rsp = container_of(rcu, struct rcu_sync, cb_head);
> 	unsigned long flags;
> 

Right, those are 'stable' states and must be advanced through explicit
calls to __rcu_sync_enter()/rcu_sync_exit() respectively.

> 	BUG_ON(rsp->gp_state == GP_IDLE);
> 	BUG_ON(rsp->gp_state == GP_PASSED);
> 
> 	spin_lock_irqsave(&rsp->rss_lock, flags);
> 	if (rsp->gp_count) {
> 		/*
> 		 * We're at least a GP after the first __rcu_sync_enter().
> 		 */
> 		rsp->gp_state = GP_PASSED;

So we can end up here in two ways afaict.

The simple way: someone called __rcu_sync_enter(), we go IDLE -> ENTER
with a raised count. Once the GP passes, we get here, observe the raised
count and advance to PASSED.

The more involved way: we were EXIT and someone calls __rcu_sync_enter()
to raise the count again. The callback from rcu_sync_exit() was still
pending and once we get here we observe the raised count and voila.

Now, since state != IDLE, I suppose this is valid, but it does hurt my
brain.

Else, !count:

> 	} else if (rsp->gp_state == GP_REPLAY) {

Fairly straight forward: during EXIT someone did __rcu_sync_enter +
rcu_sync_exit() and we need to wait longer still.

> 		/*
> 		 * A new rcu_sync_exit() has happened; requeue the callback
> 		 * to catch a later GP.
> 		 */
> 		rsp->gp_state = GP_EXIT;
> 		rcu_sync_call(rsp);
> 	} else {

Again two ways here, simple: we were EXIT, GP passed, we let em rip.

But its also possible, as you noted, that someone called rcu_sync_exit()
during ENTER and we ended up with !count which gets us back to IDLE.

> 		/*
> 		 * We're at least a GP after the last rcu_sync_exit();
> 		 * eveybody will now have observed the write side critical
> 		 * section. Let 'em rip!.
> 		 *
> 		 * OR. ->gp_state can be still GP_ENTER if __rcu_sync_wait()
> 		 * wasn't called after __rcu_sync_enter(), abort.
> 		 */
> 		rsp->gp_state = GP_IDLE;
> 	}
> 	spin_unlock_irqrestore(&rsp->rss_lock, flags);
> }

Agreed on the rest.

So I think its solid, but you failed to mention one state transition,
which seems ok in any case.

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

#1445493 — Re: [PATCH] rcu_sync: simplify the state machine, introduce __rcu_sync_enter()

On 07/18, Peter Zijlstra wrote:
>
> I think I ended up with this:
>
>  .---->	GP_IDLE <--------------.
>  |	  |                    |
>  |	  | __rcu_sync_enter() | <GP> / rcu_sync_exit()
>  |	  v                    |
>  |	GP_ENTER --------------'
>  |	  |
>  |  <GP>  |
>  |        v
>  |	GP_PASSED <---------.
>  |	  |                 |
>  |	  | rcu_sync_exit() | <GP> / __rcu_sync_enter()
>  |	  v                 |
>  `----- GP_EXIT ------------'
> 	  ^
>     <GP>  | __rcu_sync_enter() + rcu_sync_exit()
> 	  v
> 	GP_RETRY

Thanks! I'll include this into the changelog.

> > static void rcu_sync_call(struct rcu_sync *rsp)
> > {
> > 	// TODO: THIS IS SUBOPTIMAL. We want to call it directly
> > 	// if rcu_blocking_is_gp() == T, but it has might_sleep().
>
> Not sure I get that comment..

I meant, we actually want

	static void rcu_sync_call(struct rcu_sync *rsp)
	{
		if (rcu_blocking_is_gp())
			rcu_sync_func(rsp);
		else
			gp_ops[rsp->gp_type].call(&rsp->cb_head, rcu_sync_func)
	}

but this needs some other simple changes. rcu_sync_func() needs
the same spinlock and rcu_blocking_is_gp() calls might_sleep().

We can simply move rcu_sync_call() outside of rsp->rss_lock, but
then we will need more comments to explain why we can't race with
enter/exit from someone else. Or introduce __rcu_blocking_is_gp()
without might_sleep(), but this needs a trivial change outside of
rcu/sync.c.

We will see. This is simple anyway.

> > 	spin_lock_irqsave(&rsp->rss_lock, flags);
> > 	if (rsp->gp_count) {
> > 		/*
> > 		 * We're at least a GP after the first __rcu_sync_enter().
> > 		 */
> > 		rsp->gp_state = GP_PASSED;
>
> So we can end up here in two ways afaict.
>
> The simple way: someone called __rcu_sync_enter(), we go IDLE -> ENTER
> with a raised count. Once the GP passes, we get here, observe the raised
> count and advance to PASSED.
>
> The more involved way: we were EXIT and someone calls __rcu_sync_enter()
> to raise the count again. The callback from rcu_sync_exit() was still
> pending and once we get here we observe the raised count and voila.

Yes, yes.

> Now, since state != IDLE, I suppose this is valid, but it does hurt my
> brain.

Simply put, if rsp->gp_count != 0 we do not care about the history and
GP_PASSED is always correct when rcu callback is called, this obviously
means that we passed a GP.

Except GP_IDLE -> GP_PASSED transition is wrong, but this must not be
possible because only rcu callback can set GP_IDLE and only if !gp_count,
so we must always have at least one GP in between. Note also BUG_ON()
checks at the start.

> So I think its solid, but you failed to mention one state transition,
> which seems ok in any case.

Great, thanks for review.

I'll send the actual patch on top of your changes.

Oleg.

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

#1446733 — Re: [PATCH] rcu_sync: simplify the state machine, introduce __rcu_sync_enter()

On Sat, Jul 16, 2016 at 07:10:07PM +0200, Oleg Nesterov wrote:
> On 07/15, Paul E. McKenney wrote:
> >
> > On Fri, Jul 15, 2016 at 06:49:39PM +0200, Oleg Nesterov wrote:
> > >
> > > IOW, please ignore 2/2 which adds PERCPU_RWSEM_READER, the new version
> > > just adds rcu_sync_sabotage() which should be renamed (and use GP_PASSED).
> >
> > OK, then move the checks out into the callers that would have used
> > __rcu_sync_enter().  ;-)
> 
> Cough, now I can't understand which check do you mean ;) OK, let me
> show the code, then we will hopefully understand each other.

The check in an earlier patch having to do with some _NONE value.  I don't
see any such checks here.  Which might be a good thing, who knows?  ;-)

> ----------------------------------------------------------------------
> So, as you can see I have fooled you ;) I'll send the patch on top of
> Peter's changes, this is the (UNTESTED) code with the patch applied.
> 
> Peter, Paul, could you review? Do you see any hole?

Please see below.  I see what looks like a missing wakeup and something
that could fail to wait for pre-existing RCU readers.  At the very end,
I have a somewhat more elaborate state diagram, along with assumptions
I made during review.  Please do check these assumptions carefully.

And the state table, for that matter...

> Why. Firstly, note that the state machine was greatly simplified, and
> rsp->cb_state has gone, we have a single "state" variable, gp_state.
> Note also the ->sync() op has gone (and actually ->wait() too, see the
> "TODO" comment).
> 
> GP_IDLE	- owned by __rcu_sync_enter() which can only move this state to
> 
> GP_ENTER - owned by rcu-callback which moves it to
> 
> GP_PASSED - owned by the last rcu_sync_exit() which moves it to
> 
> GP_EXIT - owned by rcu-callback which moves it back to GP_IDLE.
> 
> Yes, this is a bit simplified, we also have GP_REPLAY, but hopefully
> clear.

Agreed, given that you are ignoring GP_REPLAY.

> And, there is another possible transition, GP_ENTER -> GP_IDLE, because
> not it is possible to call __rcu_sync_enter() and rcu_sync_exit() in any
> state (except obviously they should be balanced), and they do not block.

Hmmm...  I am assuming that the only threads allowed to invoke
rcu_sync_exit() are those that have executed an unpaired rcu_sync_enter().
With that assumption, rcu_sync_enter() is illegal if GP_IDLE or GP_ENTER,
because the rcu_sync_enter() calls won't return until the state reaches
GP_PASSED.

If you feel strongly about allowing rcu_sync_exit() in GP_ENTER state,
could you please tell me your use case?  Or am I confused?

> The only blocking call is __rcu_sync_wait() which actually waits for GP.
> Obviously should only be called if gp_count != 0, iow after __rcu_sync_enter.

Well, rcu_sync_dtor() as well.  But to your point, it is blocking in
rcu_barrier(), not in wait_event().

> --------------------------------------------------------------------------
> Now, cgroup_init() can simply call __rcu_sync_enter(&cgroup_threadgroup_rwsem)
> and switch this sem into the slow mode. Compared to "sabotage" from Peter
> this implies the unnecessary call_rcu_sched(), but I hope we can tolerate
> this.

Or you could add a flag to rcu_sync_init() and friends, but I vaguely
recall some objection to that.

> And we can even add a runtime knob to switch between "fast" and "slow
> aka writer-biased" modes for cgroup_threadgroup_rwsem.

This might well be the check that I was objecting to earlier.  ;-)

> --------------------------------------------------------------------------
> And I think __rcu_sync_enter() can have more users. Let's look at
> freeze_super(). It calls percpu_down_write() 3 times, and waits for 3 GP's
> sequentally.
> 
> Now we can add 3 __rcu_sync_enter's at the start and 3 rcu_sync_exit's at
> the end (actually we can do better, just to simplify). And again, note
> that rcu_sync_exit() will work correctly even if we (say) return -EBUSY,
> so rcu_sync_wait and/or percpu_down_write() was not called in between,
> and in this case we won't block waiting for GP.
> 
> What do you think?

I am not going to claim to understand freeze_super(), but it does seem
to have a fair amount of waiting.

But yes, you could put rcu_sync_enter() and rcu_sync_exit() before and
after a series of write-side enter/exit pairs in order to force things
to stay in writer mode, if that is what you are suggesting.

> Oleg.
> ---
> 
> // rcu_sync.h: ----------------------------------------------------------------
> 
> struct rcu_sync {
> 	int			gp_state;
> 	int			gp_count;
> 	wait_queue_head_t	gp_wait;
> 
> 	struct rcu_head		cb_head;
> 	enum rcu_sync_type	gp_type;
> };
> 
> // sync.c ---------------------------------------------------------------------
> #include <linux/rcu_sync.h>
> #include <linux/sched.h>
> 
> #ifdef CONFIG_PROVE_RCU
> #define __INIT_HELD(func)	.held = func,
> #else
> #define __INIT_HELD(func)
> #endif
> 
> static const struct {
> 	void (*call)(struct rcu_head *, void (*)(struct rcu_head *));
> 	void (*wait)(void);	// TODO: remove this, see the comment in dtor
> #ifdef CONFIG_PROVE_RCU
> 	int  (*held)(void);
> #endif
> } gp_ops[] = {
> 	[RCU_SYNC] = {
> 		.call = call_rcu,
> 		.wait = rcu_barrier,
> 		__INIT_HELD(rcu_read_lock_held)
> 	},
> 	[RCU_SCHED_SYNC] = {
> 		.call = call_rcu_sched,
> 		.wait = rcu_barrier_sched,
> 		__INIT_HELD(rcu_read_lock_sched_held)
> 	},
> 	[RCU_BH_SYNC] = {
> 		.call = call_rcu_bh,
> 		.wait = rcu_barrier_bh,
> 		__INIT_HELD(rcu_read_lock_bh_held)
> 	},
> };
> 
> #define	rss_lock	gp_wait.lock

Interesting...  Should there instead be a wait_queue_lock() and
wait_queue_unlock()?  If someone changes how wait-queue locking work,
this one might be a bit tricky.

> enum { GP_IDLE = 0, GP_ENTER, GP_PASSED, GP_EXIT, GP_REPLAY };
> 
> static void rcu_sync_func(struct rcu_head *rcu);
> 
> static void rcu_sync_call(struct rcu_sync *rsp)
> {
> 	// TODO: THIS IS SUBOPTIMAL. We want to call it directly
> 	// if rcu_blocking_is_gp() == T, but it has might_sleep().

Careful!  This optimization works only for RCU-sched and RCU-bh.
With normal RCU, you can be tripped up by tasks preempted within RCU
read-side critical sections should CONFIG_PREEMPT=y.

> 	gp_ops[rsp->gp_type].call(&rsp->cb_head, rcu_sync_func);
> }
> 
> static void rcu_sync_func(struct rcu_head *rcu)
> {
> 	struct rcu_sync *rsp = container_of(rcu, struct rcu_sync, cb_head);
> 	unsigned long flags;
> 
> 	BUG_ON(rsp->gp_state == GP_IDLE);

If you really want rcu_sync_exit() to be invoked before the corresponding
rcu_sync_enter() returns, and if you want that to set the state to
GP_IDLE, then the above BUG_ON() can fire.  This is why I was assuming
that rcu_sync_enter() must return before the corresponding rcu_sync_exit()
can start.

> 	BUG_ON(rsp->gp_state == GP_PASSED);

READ_ONCE() would feel better in both of the above BUG_ON()s, given that
we are not yet holding the lock.

> 	spin_lock_irqsave(&rsp->rss_lock, flags);
> 	if (rsp->gp_count) {
> 		/*
> 		 * We're at least a GP after the first __rcu_sync_enter().
> 		 */

Don't we need a wakeup here?

> 		rsp->gp_state = GP_PASSED;
> 	} else if (rsp->gp_state == GP_REPLAY) {
> 		/*
> 		 * A new rcu_sync_exit() has happened; requeue the callback
> 		 * to catch a later GP.
> 		 */
> 		rsp->gp_state = GP_EXIT;
> 		rcu_sync_call(rsp);
> 	} else {
> 		/*
> 		 * We're at least a GP after the last rcu_sync_exit();
> 		 * EVeybody will now have observed the write side critical
> 		 * section. Let 'em rip!.
> 		 *
> 		 * OR. ->gp_state can be still GP_ENTER if __rcu_sync_wait()
> 		 * wasn't called after __rcu_sync_enter(), abort.
> 		 */
> 		rsp->gp_state = GP_IDLE;
> 	}
> 	spin_unlock_irqrestore(&rsp->rss_lock, flags);
> }
> 
> bool __rcu_sync_enter(struct rcu_sync *rsp)
> {
> 	int gp_count, gp_state;
> 
> 	spin_lock_irq(&rsp->rss_lock);
> 	gp_count = rsp->gp_count++;
> 	gp_state = rsp->gp_state;
> 	if (gp_state == GP_IDLE) {
> 		rsp->gp_state = GP_ENTER;
> 		rcu_sync_call(rsp);
> 	}
> 	spin_unlock_irq(&rsp->rss_lock);
> 
> 	BUG_ON(gp_count != 0 && gp_state == GP_IDLE);
> 	BUG_ON(gp_count == 0 && gp_state == GP_PASSED);

Isn't gp_count==0 illegal here regardless of gp_state value?

> 	return gp_state < GP_PASSED;

And the above statement is another reason why I believe that it
should be illegal to invoke rcu_sync_exit() until after the matching
rcu_sync_enter() has returned.  If we were preempted just before the
above "return" statement, we might be in GP_IDLE state upon return,
which could fatally disappoint the caller.

And ditto for the next BUG_ON().

> }
> 
> void __rcu_sync_wait(struct rcu_sync *rsp)
> {
> 	BUG_ON(rsp->gp_state == GP_IDLE);
> 	BUG_ON(rsp->gp_count == 0);
> 
> 	wait_event(rsp->gp_wait, rsp->gp_state >= GP_PASSED);

I would feel better if all the references to ->gp_state and ->gp_count
outside of the lock be READ_ONCE().  Compilers can be tricky beasts.

> }

Here is what I believe rcu_sync_enter() does:

rcu_sync_enter() checks to see if the rcu_sync structure is in writer
mode, and, if not, initiates a transition to writer mode and waits for
that transition to complete.  Either way, a writer reference is acquired.

> void rcu_sync_enter(struct rcu_sync *rsp)
> {
> 	if (__rcu_sync_enter(rsp))
> 		__rcu_sync_wait(rsp);
> }

Here is what I believe rcu_sync_exit() does:

rcu_sync_exit() removes an updater reference, and if there are no more,
starts the transition to reader mode.  Note that this must handle
transitions back to writer mode that occur before the transition to
reader mode has fully completed.

> void rcu_sync_exit(struct rcu_sync *rsp)
> {
> 	BUG_ON(rsp->gp_state == GP_IDLE);

	BUG_ON(READ_ONCE(rsp->gp_state) == GP_ENTER);

If you do allow rcu_sync_exit() while GP_ENTER, then all the readers
can do rcu_sync_exit() in that state, leaving the state at GP_PASSED
instead of the desired GP_IDLE.

> 	BUG_ON(rsp->gp_count == 0);
> 
> 	spin_lock_irq(&rsp->rss_lock);
> 	if (!--rsp->gp_count) {
> 		if (rsp->gp_state == GP_PASSED) {
> 			rsp->gp_state = GP_EXIT;
> 			rcu_sync_call(rsp);
> 		} else if (rsp->gp_state == GP_EXIT) {
> 			rsp->gp_state = GP_REPLAY;
> 		}
> 	}
> 	spin_unlock_irq(&rsp->rss_lock);
> }

And here is what I believe rcu_sync_dtor() does:

rcu_sync_dtor() cleans up at end, waiting for a full transition back
into reader mode.  Anything invoking rcu_sync_dtor() must have ensured
that there will be no more calls to rcu_sync_enter() and rcu_sync_exit().

> void rcu_sync_dtor(struct rcu_sync *rsp)
> {
> 	int gp_state;
> 
> 	BUG_ON(rsp->gp_count);
> 	BUG_ON(rsp->gp_state == GP_PASSED);
> 
> 	spin_lock_irq(&rsp->rss_lock);
> 	if (rsp->gp_state == GP_REPLAY)
> 		rsp->gp_state = GP_EXIT;

OK, this ensures that the .wait() below will wait for the callback, but
it might result in some RCU read-side critical sections still being in
flight after rcu_sync_dtor() completes.  In other words, any transition
started by an rcu_sync_exit() will normally wait until all pre-existing
RCU readers complete -- unless that rcu_sync_exit() set the state to
GP_REPLAY and was quickly followed by rcu_sync_dtor().

Is this really OK???

You might get a more robust API if you left the value of ->gp_state
alone and rechecked ->gp_state below (under the lock).  The additional
overhead is incurred only at cleanup, so should not be a problem.

Or am I missing some subtle constraint on use cases here?

> 	gp_state = rsp->gp_state;
> 	spin_unlock_irq(&rsp->rss_lock);
> 
> 	// TODO: add another wake_up_locked() into rcu_sync_func(),

We need to add the first wakeup before we can add another one.  ;-)

But I don't see why we need a second wakeup, given that rcu_barrier()
wakes itself up.

> 	// use wait_event + spin_lock_wait, remove gp_ops->wait().
> 	if (gp_state != GP_IDLE) {
> 		gp_ops[rsp->gp_type].wait();
> 		BUG_ON(rsp->gp_state != GP_IDLE);
> 	}
> }
> 

And please see below for the state table and assumptions.

So, what am I missing?

							Thanx, Paul

------------------------------------------------------------------------


o       "count" is the value of the rcu_sync structure's ->gp_count field.

o       "state" is the value of the rcu_sync structure's ->gp_state field.

o       "CB?" is "yes" if there is an RCU callback pending and "no" otherwise.



   | count | state     | CB? | next state
---+-------+-----------+-----+------------------------------------
   |       |           |     |
 A |   0   | GP_IDLE   | no  | rcu_sync_enter() -> B (wait)
   |       |           |     | rcu_sync_exit() -> illegal
   |       |           |     | rcu_sync_dtor() -> H
   |       |           |     | callback -> cannot happen
   |       |           |     |
---+-------+-----------+-----+------------------------------------
   |       |           |     |
 B |   1+  | GP_ENTER  | yes | rcu_sync_enter() -> B (wait)
   |       |           |     | rcu_sync_exit() -> illegal
   |       |           |     | rcu_sync_dtor() -> illegal
   |       |           |     | callback -> C (ends _enter() wait)
   |       |           |     |
---+-------+-----------+-----+------------------------------------
   |       |           |     |
 C |   1+  | GP_PASSED | no  | rcu_sync_enter() -> C
   |       |           |     | last rcu_sync_exit() -> E
   |       |           |     | non-last rcu_sync_exit() -> C
   |       |           |     | rcu_sync_dtor() -> illegal
   |       |           |     | callback -> cannot happen
   |       |           |     |
---+-------+-----------+-----+------------------------------------
   |       |           |     |
 D |   0   | GP_REPLAY | yes | rcu_sync_enter() -> F
   |       |           |     | rcu_sync_exit() -> illegal
   |       |           |     | rcu_sync_dtor() -> I (wait ???)
   |       |           |     | callback -> E
   |       |           |     |
---+-------+-----------+-----+------------------------------------
   |       |           |     |
 E |   0   | GP_EXIT   | yes | rcu_sync_enter() -> G
   |       |           |     | rcu_sync_exit() -> illegal
   |       |           |     | rcu_sync_dtor() -> I (wait)
   |       |           |     | callback -> A
   |       |           |     |
---+-------+-----------+-----+------------------------------------
   |       |           |     |
 F |   1+  | GP_REPLAY | yes | rcu_sync_enter() -> F
   |       |           |     | last rcu_sync_exit() -> D
   |       |           |     | non-last rcu_sync_exit() -> F
   |       |           |     | rcu_sync_dtor() -> illegal
   |       |           |     | callback -> C
   |       |           |     |
---+-------+-----------+-----+------------------------------------
   |       |           |     |
 G |   1+  | GP_EXIT   | yes | rcu_sync_enter() -> G
   |       |           |     | last rcu_sync_exit() -> D
   |       |           |     | non-last rcu_sync_exit() -> F
   |       |           |     | rcu_sync_dtor() -> illegal
   |       |           |     | callback -> C
   |       |           |     |
---+-------+-----------+-----+------------------------------------
   |       |           |     |
 H |   0   | GP_IDLE   | no  | rcu_sync_enter() -> illegal
   |       |           |     | rcu_sync_exit() -> illegal
   |       |           |     | rcu_sync_dtor() -> illegal
   |       |           |     | callback -> cannot happen
   |       |           |     |
---+-------+-----------+-----+------------------------------------
   |       |           |     |
 I |   0   | GP_EXIT   | yes | rcu_sync_enter() -> illegal
   |       |           |     | rcu_sync_exit() -> illegal
   |       |           |     | rcu_sync_dtor() -> illegal
   |       |           |     | callback -> H (ends dtor() wait)


Assumptions:

o	Initial state is A.

o	Final state is H.

o	There will never be enough unpaired rcu_sync_enter() calls to
	overflow ->gp_count.

o	All calls to rcu_sync_exit() must pair with a preceding call
	to rcu_sync_enter() by that same thread.

o	It is illegal to invoke rcu_sync_dtor() until after the caller
	has ensured that there will be no future calls to either
	rcu_sync_enter() or rcu_sync_exit().

o	It is illegal to invoke rcu_sync_dtor() while there are any
	unpaired calls to rcu_sync_enter().

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

#1447288 — Re: [PATCH] rcu_sync: simplify the state machine, introduce __rcu_sync_enter()

On 07/19, Paul E. McKenney wrote:
>
> On Sat, Jul 16, 2016 at 07:10:07PM +0200, Oleg Nesterov wrote:
>
> > And, there is another possible transition, GP_ENTER -> GP_IDLE, because
> > not it is possible to call __rcu_sync_enter() and rcu_sync_exit() in any
> > state (except obviously they should be balanced), and they do not block.
>
> Hmmm...  I am assuming that the only threads allowed to invoke
> rcu_sync_exit() are those that have executed an unpaired rcu_sync_enter().
> With that assumption, rcu_sync_enter() is illegal if GP_IDLE or GP_ENTER,
> because the rcu_sync_enter() calls won't return until the state reaches
> GP_PASSED.

Not sure I understand... Obviously rcu_sync_exit() can only be used if
it pairs with the preceeding __rcu_sync_enter() or rcu_sync_enter(), if
nothing else rsp->gp_count-- must not underflow.

rcu_sync_enter() or __rcu_sync_enter() is legal in any state, the latter
won't block.

> If you feel strongly about allowing rcu_sync_exit() in GP_ENTER state,
> could you please tell me your use case?  Or am I confused?

I'll write another email, let me reply to the code review first. And
thanks for your review!

> > The only blocking call is __rcu_sync_wait() which actually waits for GP.
> > Obviously should only be called if gp_count != 0, iow after __rcu_sync_enter.
>
> Well, rcu_sync_dtor() as well.  But to your point, it is blocking in
> rcu_barrier(), not in wait_event().

Yes, yes, sure. I mean't the only blocking call in enter/exit paths.

> > #define	rss_lock	gp_wait.lock
>
> Interesting...  Should there instead be a wait_queue_lock() and
> wait_queue_unlock()?  If someone changes how wait-queue locking work,
> this one might be a bit tricky.

Well, the current version does the same... I do not mind to add
wait_queue_lock(), but personally I do not think this would be better.
Either way the code should not use gp_wait.lock directly, to make it
clear that we abuse the spinlock we already have in rcu_sync->gp_wait.

To me

	spin_lock_irq(&rsp->rss_lock);
	spin_unlock_irq(&rsp->rss_lock);

looks a bit better than

	wait_queue_lock();
	wait_queue_unlock();

because we need to protect the state, not the wait-queue. And if
someone changes how wait-queue locking work, we can just actually
add "spinlock_t rss_lock" into rcu_sync and remove that "#define".

> > static void rcu_sync_call(struct rcu_sync *rsp)
> > {
> > 	// TODO: THIS IS SUBOPTIMAL. We want to call it directly
> > 	// if rcu_blocking_is_gp() == T, but it has might_sleep().
>
> Careful!  This optimization works only for RCU-sched and RCU-bh.
> With normal RCU, you can be tripped up by tasks preempted within RCU
> read-side critical sections should CONFIG_PREEMPT=y.

Yes, thanks, I understand ;) another reason why I do not want to add
this optimization into the initial version.

> > static void rcu_sync_func(struct rcu_head *rcu)
> > {
> > 	struct rcu_sync *rsp = container_of(rcu, struct rcu_sync, cb_head);
> > 	unsigned long flags;
> >
> > 	BUG_ON(rsp->gp_state == GP_IDLE);
>
> If you really want rcu_sync_exit() to be invoked before the corresponding
> rcu_sync_enter() returns, and if you want that to set the state to
> GP_IDLE, then the above BUG_ON() can fire.  This is why I was assuming
> that rcu_sync_enter() must return before the corresponding rcu_sync_exit()
> can start.

Again, can't understand. Let me repeat, of course rcu_sync_exit() can only
be called after __rcu_sync_enter() (or rcu_sync_enter() which does
__rcu_sync_enter + wait), they obviously should be balanced.

But, it should be fine to call rcu_sync_exit() right after __rcu_sync_enter()
returns, without waiting for GP_PASSED, iow without __rcu_sync_wait().

But probably I misunderstood you... Either way, rcu_sync_func() can never
hit gp_state == GP_IDLE. Because this state can only be set by rcu_sync_func(),
nobody else can set this state. Ignoring the initial state of course.

And every caller of rcu_sync_call() (which does call_rcu(rcu_sync_func))
updates the state first:

	rsp->gp_state = GP_ENTER;	// __rcu_sync_enter()
	rcu_sync_call(rsp);

	rsp->gp_state = GP_EXIT;	// rcu_sync_exit() or REPLAY
	rcu_sync_call(rsp);

so I simply can't understand your concern.

> > 	BUG_ON(rsp->gp_state == GP_PASSED);
>
> READ_ONCE() would feel better in both of the above BUG_ON()s, given that
> we are not yet holding the lock.

The lockless checks are fine, both states can only be set by the callback.
As for READ_ONCE(), please see below.

> > 	spin_lock_irqsave(&rsp->rss_lock, flags);
> > 	if (rsp->gp_count) {
> > 		/*
> > 		 * We're at least a GP after the first __rcu_sync_enter().
> > 		 */
>
> Don't we need a wakeup here?

Heh ;) let me show you what I have in kernel/rcu/sync.c~

	if (rsp->gp_count) {
		/*
		 * COMMENT.
		 */
		rsp->gp_state = GP_PASSED;
		wake_up_locked(&rsp->gp_wait);
	} else if (rsp->gp_state == GP_REPLAY) {

apparently I removed this wake_up_locked() by accident when I edited
the "COMMENT" placeholder ;)

Thanks!

> > bool __rcu_sync_enter(struct rcu_sync *rsp)
> > {
> > 	int gp_count, gp_state;
> >
> > 	spin_lock_irq(&rsp->rss_lock);
> > 	gp_count = rsp->gp_count++;
> > 	gp_state = rsp->gp_state;
> > 	if (gp_state == GP_IDLE) {
> > 		rsp->gp_state = GP_ENTER;
> > 		rcu_sync_call(rsp);
> > 	}
> > 	spin_unlock_irq(&rsp->rss_lock);
> >
> > 	BUG_ON(gp_count != 0 && gp_state == GP_IDLE);
> > 	BUG_ON(gp_count == 0 && gp_state == GP_PASSED);
>
> Isn't gp_count==0 illegal here regardless of gp_state value?

No. gp_count is the old value of rsp->gp_count, before it was
incremented by us.

> > 	return gp_state < GP_PASSED;
>
> And the above statement is another reason why I believe that it
> should be illegal to invoke rcu_sync_exit() until after the matching
> rcu_sync_enter() has returned.  If we were preempted just before the
> above "return" statement, we might be in GP_IDLE state upon return,

How? Note the GP_IDLE -> GP_ENTER transition above, it can't be GP_IDLE.
And since we incremented rsp->gp_count, GP_IDLE is not possibly until
rcu_sync_exit() which pairs with this "enter" decrements the counter
and fires the RCU callback which will set GP_IDLE after GP.

> > void __rcu_sync_wait(struct rcu_sync *rsp)
> > {
> > 	BUG_ON(rsp->gp_state == GP_IDLE);
> > 	BUG_ON(rsp->gp_count == 0);
> >
> > 	wait_event(rsp->gp_wait, rsp->gp_state >= GP_PASSED);
>
> I would feel better if all the references to ->gp_state and ->gp_count
> outside of the lock be READ_ONCE().  Compilers can be tricky beasts.

Oh. I won't argue too much, but I do not agree.

Because I started to hate these _ONCE() helpers a long ago. Why? Because
(imo) we have too many XXX_ONCE() added "just in case, because compiler
can be buggy".

Now, when I look some particular READ_ONCE() I can almost never understand
the reason: do we really need it for correctness? or this is another "it
does not hurt" case?

So why do we need READ_ONCE() here? How this wait_event() differs from
any other wait_event() which does a plain LOAD? Should we "fix" them all?

> rcu_sync_enter() checks to see if the rcu_sync structure is in writer
> mode, and, if not, initiates a transition to writer mode and waits for
> that transition to complete.  Either way, a writer reference is acquired.
>
> > void rcu_sync_enter(struct rcu_sync *rsp)
> > {
> > 	if (__rcu_sync_enter(rsp))
> > 		__rcu_sync_wait(rsp);
> > }

Yes. And of course it could call __rcu_sync_wait() unconditionally:

	__rcu_sync_enter(rsp);
	__rcu_sync_wait(rsp);

This "if" is more the documentation than optimization.

> Here is what I believe rcu_sync_exit() does:
>
> rcu_sync_exit() removes an updater reference, and if there are no more,
> starts the transition to reader mode.  Note that this must handle
> transitions back to writer mode that occur before the transition to
> reader mode has fully completed.
>
> > void rcu_sync_exit(struct rcu_sync *rsp)
> > {
> > 	BUG_ON(rsp->gp_state == GP_IDLE);
>
> 	BUG_ON(READ_ONCE(rsp->gp_state) == GP_ENTER);
>
> If you do allow rcu_sync_exit() while GP_ENTER, then all the readers
> can do rcu_sync_exit() in that state, leaving the state at GP_PASSED
> instead of the desired GP_IDLE.

Can't understand this too...

Firstly, readers do not do rcu_sync_enter/exit. They only use
rcu_sync_is_idle() which checks gp_state == GP_IDLE.

As for enter() path, we only need to ensure that after __rcu_sync_wait()
returns, all CPU's must see gp_state != GP_IDLE. Yes, yes, this is not
really true, we also need the memory barriers implied by RCU, lets ignore
this to simplify the discussion.

Now lets suppose that rcu_sync_exit() is called while GP_ENTER. This is
only possible if __rcu_sync_wait() was not called by us. IOW, this thread
does

	__rcu_sync_enter();
	rcu_sync_exit();

by any reason.

Now. If gp_count is not zero after we decrement it, rcu_sync_exit() does
nothing.

If it is zero, we could set GP_IDLE right now. We do not care about the
readers in this case, exactly because __rcu_sync_wait() was not called
and thus we can't even know if other CPU's had any chance to observe the
gp_state != GP_IDLE state set by __rcu_sync_enter().

But. We can't actually set GP_IDLE, because GP_ENTER means that the RCU
callback is already pending and this can break the next enter(). IOW, this
would break the "GP_IDLE is owned by __rcu_sync_enter" contract.

And we do not need to do this! We rely on the already pending rcu_sync_func()
which will set GP_IDLE _if_ the counter is still zero.

Now suppose that another writer (__rcu_sync_enter) comes and increments
gp_count right before rcu_sync_func() is called by RCU. In this case
rcu_sync_func() will notice rsp->gp_count != 0 and correctly set GP_PASSED.

Note that in this case that new writer won't wait for a full GP, quite
possibly __rcu_sync_wait() won't even block. And this is correct, we know
that we have at least one full GP after the previous GP_IDLE -> GP_ENTER
transition.


> And here is what I believe rcu_sync_dtor() does:
>
> rcu_sync_dtor() cleans up at end, waiting for a full transition back
> into reader mode.  Anything invoking rcu_sync_dtor() must have ensured
> that there will be no more calls to rcu_sync_enter() and rcu_sync_exit().

Sure, we are going to destroy/free this object.

> > void rcu_sync_dtor(struct rcu_sync *rsp)
> > {
> > 	int gp_state;
> >
> > 	BUG_ON(rsp->gp_count);
> > 	BUG_ON(rsp->gp_state == GP_PASSED);
> >
> > 	spin_lock_irq(&rsp->rss_lock);
> > 	if (rsp->gp_state == GP_REPLAY)
> > 		rsp->gp_state = GP_EXIT;
>
> OK, this ensures that the .wait() below will wait for the callback, but
> it might result in some RCU read-side critical sections still being in
> flight after rcu_sync_dtor() completes.

Hmm. Obviously, the caller should prevent this somehow or it is simply
buggy. Or I misunderstood.

> In other words, any transition
> started by an rcu_sync_exit() will normally wait until all pre-existing
> RCU readers complete -- unless that rcu_sync_exit() set the state to
> GP_REPLAY and was quickly followed by rcu_sync_dtor().

Again, we are going to (say) free this memory. The caller must ensure
that rcu_sync_is_idle(rsp) or anything else which can touch this object
is not possible.

The only reason for rcu_sync_dtor() is that we can't free/destroy this
memory until we ensure that the pending rcu_sync_func() finishes. And
of course we need to ensure it won't re-arm itself, that is why we
do GP_REPLAY -> GP_EXIT transition.

And in any case, this patch doesn't change rcu_sync_dtor() logic, it
is the same even if ->cb_state goes away.

> We need to add the first wakeup before we can add another one.  ;-)

Yes ;) see above.

> But I don't see why we need a second wakeup, given that rcu_barrier()
> wakes itself up.
>
> > 	// use wait_event + spin_lock_wait, remove gp_ops->wait().
> > 	if (gp_state != GP_IDLE) {
> > 		gp_ops[rsp->gp_type].wait();
> > 		BUG_ON(rsp->gp_state != GP_IDLE);
> > 	}
> > }

Because we can remove .wait() op and simplify the code a bit more. This
also can be more efficient, altough this doesn't really matter. The main
reason is that this would be more clear: we only need to sync with one
particular callback, we do not need to wait for all outstanding RCU
callbacks to complete. Anyway, this is TODO and needs another patch, we
will discuss this later.

> And please see below for the state table and assumptions.

I'll try to read it carefully later.

Thanks Paul!

Oleg.

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

#1447468 — Re: [PATCH] rcu_sync: simplify the state machine, introduce __rcu_sync_enter()

On Wed, Jul 20, 2016 at 05:13:58PM +0200, Oleg Nesterov wrote:
> On 07/19, Paul E. McKenney wrote:
> >
> > On Sat, Jul 16, 2016 at 07:10:07PM +0200, Oleg Nesterov wrote:
> >
> > > And, there is another possible transition, GP_ENTER -> GP_IDLE, because
> > > not it is possible to call __rcu_sync_enter() and rcu_sync_exit() in any
> > > state (except obviously they should be balanced), and they do not block.
> >
> > Hmmm...  I am assuming that the only threads allowed to invoke
> > rcu_sync_exit() are those that have executed an unpaired rcu_sync_enter().
> > With that assumption, rcu_sync_enter() is illegal if GP_IDLE or GP_ENTER,
> > because the rcu_sync_enter() calls won't return until the state reaches
> > GP_PASSED.
> 
> Not sure I understand... Obviously rcu_sync_exit() can only be used if
> it pairs with the preceeding __rcu_sync_enter() or rcu_sync_enter(), if
> nothing else rsp->gp_count-- must not underflow.

Agreed, just wondering what the no-wait use case is.

> rcu_sync_enter() or __rcu_sync_enter() is legal in any state, the latter
> won't block.

Actually, I had no idea that __rcu_sync_enter() was intended for anything
other than internal use.

Other than that, agreed, with the exception that it is illegal after
rcu_sync_dtor() has been called.

> > If you feel strongly about allowing rcu_sync_exit() in GP_ENTER state,
> > could you please tell me your use case?  Or am I confused?
> 
> I'll write another email, let me reply to the code review first. And
> thanks for your review!

Fair enough, hope it is helpful.

> > > The only blocking call is __rcu_sync_wait() which actually waits for GP.
> > > Obviously should only be called if gp_count != 0, iow after __rcu_sync_enter.
> >
> > Well, rcu_sync_dtor() as well.  But to your point, it is blocking in
> > rcu_barrier(), not in wait_event().
> 
> Yes, yes, sure. I mean't the only blocking call in enter/exit paths.

Pedantic of me, isn't it?  ;-)

> > > #define	rss_lock	gp_wait.lock
> >
> > Interesting...  Should there instead be a wait_queue_lock() and
> > wait_queue_unlock()?  If someone changes how wait-queue locking work,
> > this one might be a bit tricky.
> 
> Well, the current version does the same... I do not mind to add
> wait_queue_lock(), but personally I do not think this would be better.
> Either way the code should not use gp_wait.lock directly, to make it
> clear that we abuse the spinlock we already have in rcu_sync->gp_wait.
> 
> To me
> 
> 	spin_lock_irq(&rsp->rss_lock);
> 	spin_unlock_irq(&rsp->rss_lock);
> 
> looks a bit better than
> 
> 	wait_queue_lock();
> 	wait_queue_unlock();
> 
> because we need to protect the state, not the wait-queue. And if
> someone changes how wait-queue locking work, we can just actually
> add "spinlock_t rss_lock" into rcu_sync and remove that "#define".

I don't feel all that strongly about it, but it did look strange.

In any case, please don't reach inside RCU in this way without asking
me first!  ;-)

> > > static void rcu_sync_call(struct rcu_sync *rsp)
> > > {
> > > 	// TODO: THIS IS SUBOPTIMAL. We want to call it directly
> > > 	// if rcu_blocking_is_gp() == T, but it has might_sleep().
> >
> > Careful!  This optimization works only for RCU-sched and RCU-bh.
> > With normal RCU, you can be tripped up by tasks preempted within RCU
> > read-side critical sections should CONFIG_PREEMPT=y.
> 
> Yes, thanks, I understand ;) another reason why I do not want to add
> this optimization into the initial version.

So I should take this as a request to export rcu_blocking_is_gp()?

I would probably need to change the name.  Or comment it more heavily.
Or hand out coccinelle scripts looking for this pattern:

	if (!rcu_blocking_is_gp())
		synchronize_rcu();

Or maybe all of the above.

> > > static void rcu_sync_func(struct rcu_head *rcu)
> > > {
> > > 	struct rcu_sync *rsp = container_of(rcu, struct rcu_sync, cb_head);
> > > 	unsigned long flags;
> > >
> > > 	BUG_ON(rsp->gp_state == GP_IDLE);
> >
> > If you really want rcu_sync_exit() to be invoked before the corresponding
> > rcu_sync_enter() returns, and if you want that to set the state to
> > GP_IDLE, then the above BUG_ON() can fire.  This is why I was assuming
> > that rcu_sync_enter() must return before the corresponding rcu_sync_exit()
> > can start.
> 
> Again, can't understand. Let me repeat, of course rcu_sync_exit() can only
> be called after __rcu_sync_enter() (or rcu_sync_enter() which does
> __rcu_sync_enter + wait), they obviously should be balanced.
> 
> But, it should be fine to call rcu_sync_exit() right after __rcu_sync_enter()
> returns, without waiting for GP_PASSED, iow without __rcu_sync_wait().
> 
> But probably I misunderstood you... Either way, rcu_sync_func() can never
> hit gp_state == GP_IDLE. Because this state can only be set by rcu_sync_func(),
> nobody else can set this state. Ignoring the initial state of course.
> 
> And every caller of rcu_sync_call() (which does call_rcu(rcu_sync_func))
> updates the state first:
> 
> 	rsp->gp_state = GP_ENTER;	// __rcu_sync_enter()
> 	rcu_sync_call(rsp);
> 
> 	rsp->gp_state = GP_EXIT;	// rcu_sync_exit() or REPLAY
> 	rcu_sync_call(rsp);
> 
> so I simply can't understand your concern.

You are right, the state is always set to something other than GP_IDLE
before the callback is registered.  Never mind!

> > > 	BUG_ON(rsp->gp_state == GP_PASSED);
> >
> > READ_ONCE() would feel better in both of the above BUG_ON()s, given that
> > we are not yet holding the lock.
> 
> The lockless checks are fine, both states can only be set by the callback.
> As for READ_ONCE(), please see below.
> 
> > > 	spin_lock_irqsave(&rsp->rss_lock, flags);
> > > 	if (rsp->gp_count) {
> > > 		/*
> > > 		 * We're at least a GP after the first __rcu_sync_enter().
> > > 		 */
> >
> > Don't we need a wakeup here?
> 
> Heh ;) let me show you what I have in kernel/rcu/sync.c~
> 
> 	if (rsp->gp_count) {
> 		/*
> 		 * COMMENT.
> 		 */
> 		rsp->gp_state = GP_PASSED;
> 		wake_up_locked(&rsp->gp_wait);
> 	} else if (rsp->gp_state == GP_REPLAY) {
> 
> apparently I removed this wake_up_locked() by accident when I edited
> the "COMMENT" placeholder ;)

Sounds like something that I might do!  ;-)

> Thanks!

No problem -- you have done the same for me many times!

> > > bool __rcu_sync_enter(struct rcu_sync *rsp)
> > > {
> > > 	int gp_count, gp_state;
> > >
> > > 	spin_lock_irq(&rsp->rss_lock);
> > > 	gp_count = rsp->gp_count++;
> > > 	gp_state = rsp->gp_state;
> > > 	if (gp_state == GP_IDLE) {
> > > 		rsp->gp_state = GP_ENTER;
> > > 		rcu_sync_call(rsp);
> > > 	}
> > > 	spin_unlock_irq(&rsp->rss_lock);
> > >
> > > 	BUG_ON(gp_count != 0 && gp_state == GP_IDLE);
> > > 	BUG_ON(gp_count == 0 && gp_state == GP_PASSED);
> >
> > Isn't gp_count==0 illegal here regardless of gp_state value?
> 
> No. gp_count is the old value of rsp->gp_count, before it was
> incremented by us.

Got it -- blindness on my part, I guess.

> > > 	return gp_state < GP_PASSED;
> >
> > And the above statement is another reason why I believe that it
> > should be illegal to invoke rcu_sync_exit() until after the matching
> > rcu_sync_enter() has returned.  If we were preempted just before the
> > above "return" statement, we might be in GP_IDLE state upon return,
> 
> How? Note the GP_IDLE -> GP_ENTER transition above, it can't be GP_IDLE.
> And since we incremented rsp->gp_count, GP_IDLE is not possibly until
> rcu_sync_exit() which pairs with this "enter" decrements the counter
> and fires the RCU callback which will set GP_IDLE after GP.

Right -- I was again confusing gp_state with rsp->gp_state.

> > > void __rcu_sync_wait(struct rcu_sync *rsp)
> > > {
> > > 	BUG_ON(rsp->gp_state == GP_IDLE);
> > > 	BUG_ON(rsp->gp_count == 0);
> > >
> > > 	wait_event(rsp->gp_wait, rsp->gp_state >= GP_PASSED);
> >
> > I would feel better if all the references to ->gp_state and ->gp_count
> > outside of the lock be READ_ONCE().  Compilers can be tricky beasts.
> 
> Oh. I won't argue too much, but I do not agree.
> 
> Because I started to hate these _ONCE() helpers a long ago. Why? Because
> (imo) we have too many XXX_ONCE() added "just in case, because compiler
> can be buggy".
> 
> Now, when I look some particular READ_ONCE() I can almost never understand
> the reason: do we really need it for correctness? or this is another "it
> does not hurt" case?
> 
> So why do we need READ_ONCE() here? How this wait_event() differs from
> any other wait_event() which does a plain LOAD? Should we "fix" them all?

I think of them as "this accesses a shared variable".  I have been
learning more about what the compiler is permitted to do to normal
variables, and I am paranoid.  The default compiler assumption that no
other thread is looking at or modifying the variable is a very powerful
and profound assumption, and it points to a rather stunning array of
"creative" optimizations.

It has been suggested that gcc implement a -std=kernel, which might be
a decent alternative.  However, we would need to specify what we want
gcc to do (and not do) in that case.

This is not an easy thing, nor will it go away.  Though I suppose that
doesn't mean we cannot ignore it.  For awhile, anyway.  ;-)

> > rcu_sync_enter() checks to see if the rcu_sync structure is in writer
> > mode, and, if not, initiates a transition to writer mode and waits for
> > that transition to complete.  Either way, a writer reference is acquired.
> >
> > > void rcu_sync_enter(struct rcu_sync *rsp)
> > > {
> > > 	if (__rcu_sync_enter(rsp))
> > > 		__rcu_sync_wait(rsp);
> > > }
> 
> Yes. And of course it could call __rcu_sync_wait() unconditionally:
> 
> 	__rcu_sync_enter(rsp);
> 	__rcu_sync_wait(rsp);
> 
> This "if" is more the documentation than optimization.

Understood.

> > Here is what I believe rcu_sync_exit() does:
> >
> > rcu_sync_exit() removes an updater reference, and if there are no more,
> > starts the transition to reader mode.  Note that this must handle
> > transitions back to writer mode that occur before the transition to
> > reader mode has fully completed.
> >
> > > void rcu_sync_exit(struct rcu_sync *rsp)
> > > {
> > > 	BUG_ON(rsp->gp_state == GP_IDLE);
> >
> > 	BUG_ON(READ_ONCE(rsp->gp_state) == GP_ENTER);
> >
> > If you do allow rcu_sync_exit() while GP_ENTER, then all the readers

s/readers/writers/, sorry!

> > can do rcu_sync_exit() in that state, leaving the state at GP_PASSED
> > instead of the desired GP_IDLE.
> 
> Can't understand this too...
> 
> Firstly, readers do not do rcu_sync_enter/exit. They only use
> rcu_sync_is_idle() which checks gp_state == GP_IDLE.
> 
> As for enter() path, we only need to ensure that after __rcu_sync_wait()
> returns, all CPU's must see gp_state != GP_IDLE. Yes, yes, this is not
> really true, we also need the memory barriers implied by RCU, lets ignore
> this to simplify the discussion.
> 
> Now lets suppose that rcu_sync_exit() is called while GP_ENTER. This is
> only possible if __rcu_sync_wait() was not called by us. IOW, this thread
> does
> 
> 	__rcu_sync_enter();
> 	rcu_sync_exit();
> 
> by any reason.
> 
> Now. If gp_count is not zero after we decrement it, rcu_sync_exit() does
> nothing.
> 
> If it is zero, we could set GP_IDLE right now. We do not care about the
> readers in this case, exactly because __rcu_sync_wait() was not called
> and thus we can't even know if other CPU's had any chance to observe the
> gp_state != GP_IDLE state set by __rcu_sync_enter().
> 
> But. We can't actually set GP_IDLE, because GP_ENTER means that the RCU
> callback is already pending and this can break the next enter(). IOW, this
> would break the "GP_IDLE is owned by __rcu_sync_enter" contract.
> 
> And we do not need to do this! We rely on the already pending rcu_sync_func()
> which will set GP_IDLE _if_ the counter is still zero.
> 
> Now suppose that another writer (__rcu_sync_enter) comes and increments
> gp_count right before rcu_sync_func() is called by RCU. In this case
> rcu_sync_func() will notice rsp->gp_count != 0 and correctly set GP_PASSED.
> 
> Note that in this case that new writer won't wait for a full GP, quite
> possibly __rcu_sync_wait() won't even block. And this is correct, we know
> that we have at least one full GP after the previous GP_IDLE -> GP_ENTER
> transition.

Let me try laying out the sequence of events that I was concerned about,
which will hopefully either prove my point or identify my error:

o	The rcu_sync structure is in state GP_IDLE with count 0 and
	no CB posted.  (State A in my table.)

o	Task A invokes __rcu_sync_enter(), which puts the state at
	GP_ENTER with count 1 and a CB posted.

o	Task B also invokes __rcu_sync_enter(), which increments count
	to 2, but leaves the state otherwise unchanged.

o	Both Task A and Task B invoke rcu_sync_exit(), which decrements
	count back down to zero, but otherwise leaves the state unchanged.
	So we are at GP_ENTER with count 0.

Ah, but the CB is still pending, and when it is invoked, as you say above,
it will see that count==0 and therefore set the state to GP_IDLE.

OK, you are quite right.

> > And here is what I believe rcu_sync_dtor() does:
> >
> > rcu_sync_dtor() cleans up at end, waiting for a full transition back
> > into reader mode.  Anything invoking rcu_sync_dtor() must have ensured
> > that there will be no more calls to rcu_sync_enter() and rcu_sync_exit().
> 
> Sure, we are going to destroy/free this object.
> 
> > > void rcu_sync_dtor(struct rcu_sync *rsp)
> > > {
> > > 	int gp_state;
> > >
> > > 	BUG_ON(rsp->gp_count);
> > > 	BUG_ON(rsp->gp_state == GP_PASSED);
> > >
> > > 	spin_lock_irq(&rsp->rss_lock);
> > > 	if (rsp->gp_state == GP_REPLAY)
> > > 		rsp->gp_state = GP_EXIT;
> >
> > OK, this ensures that the .wait() below will wait for the callback, but
> > it might result in some RCU read-side critical sections still being in
> > flight after rcu_sync_dtor() completes.
> 
> Hmm. Obviously, the caller should prevent this somehow or it is simply
> buggy. Or I misunderstood.

Hard to say without knowing what the permitted use cases are...

Me, I would make rcu_sync_dtor() wait the extra grace period in this case.
It should be a low-probability race, and it reduces the _dtor-time
state space.

What it looks like you are saying is that the caller must not only ensure
that there will never again be a __rcu_sync_enter(), rcu_sync_enter(),
or rcu_sync_exit() (or, I suppose, rcu_sync_dtor()) for this rcu_sync
structure, but must also ensure that any relevant RCU read-side critical
sections have completed.

I guess that either way is OK, but whatever the rules are, they do need
to be clearly communicated.  Of course, this does indicate a bug in
rcu_sync_dtor()'s current comment header.  ;-)

> > In other words, any transition
> > started by an rcu_sync_exit() will normally wait until all pre-existing
> > RCU readers complete -- unless that rcu_sync_exit() set the state to
> > GP_REPLAY and was quickly followed by rcu_sync_dtor().
> 
> Again, we are going to (say) free this memory. The caller must ensure
> that rcu_sync_is_idle(rsp) or anything else which can touch this object
> is not possible.
> 
> The only reason for rcu_sync_dtor() is that we can't free/destroy this
> memory until we ensure that the pending rcu_sync_func() finishes. And
> of course we need to ensure it won't re-arm itself, that is why we
> do GP_REPLAY -> GP_EXIT transition.
> 
> And in any case, this patch doesn't change rcu_sync_dtor() logic, it
> is the same even if ->cb_state goes away.

Agreed, this is something that I should have complained about eleven
months ago.  So I am slow!  ;-)

> > We need to add the first wakeup before we can add another one.  ;-)
> 
> Yes ;) see above.
> 
> > But I don't see why we need a second wakeup, given that rcu_barrier()
> > wakes itself up.
> >
> > > 	// use wait_event + spin_lock_wait, remove gp_ops->wait().
> > > 	if (gp_state != GP_IDLE) {
> > > 		gp_ops[rsp->gp_type].wait();
> > > 		BUG_ON(rsp->gp_state != GP_IDLE);
> > > 	}
> > > }
> 
> Because we can remove .wait() op and simplify the code a bit more. This
> also can be more efficient, altough this doesn't really matter. The main
> reason is that this would be more clear: we only need to sync with one
> particular callback, we do not need to wait for all outstanding RCU
> callbacks to complete. Anyway, this is TODO and needs another patch, we
> will discuss this later.

Yes, you could have a flag that the callback manipulates and a
wait_event()/wake_up() or similar, which would be quite a bit lighter
weight than rcu_barrier().  So it does sound worthwhile.

The only concern would be scalability, but we should run into that
problem before solving it, and the callback will be the least of
our worries.

							Thanx, Paul

> > And please see below for the state table and assumptions.
> 
> I'll try to read it carefully later.
> 
> Thanks Paul!
> 
> Oleg.
> 

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web