[PATCH 0/8] srcu: cleanup for 3.8

[PATCH 0/8] srcu: cleanup for 3.8

[Lai Jiangshan]

Hi, Paul

These are tiny cleanups for srcu.

PATCH 4~8 make the code or the comments match the new SRCU.

Thanks,
Lai

Lai Jiangshan (8):
  srcu: simplify __srcu_read_unlock() via this_cpu_dec()
  srcu: add might_sleep() annotation to synchronize_srcu()
  srcu: simple cleanup for cleanup_srcu_struct()
  srcu: srcu_read_lock() can be called from offline cpu
  srcu: srcu_read_lock() can be called from idle loop
  srcu: update the comments of synchronize_srcu()
  srcu: update the comments of synchronize_srcu_expedited()
  srcu: use ACCESS_ONCE() to access sp->completed in srcu_read_lock()

 include/linux/srcu.h |   26 +++-----------------------
 kernel/srcu.c        |   37 ++++++++++++++++---------------------
 2 files changed, 19 insertions(+), 44 deletions(-)

-- 
1.7.4.4

[PATCH 1/8] srcu: simplify __srcu_read_unlock() via this_cpu_dec()

[Lai Jiangshan]

this_cpu_dec() can do the same thing and sometimes it is better.
(avoid preempt_disable() and use more tiny instructions)

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/srcu.c |    4 +---
 1 files changed, 1 insertions(+), 3 deletions(-)

diff --git a/kernel/srcu.c b/kernel/srcu.c
index b363b09..b2e4f36 100644
--- a/kernel/srcu.c
+++ b/kernel/srcu.c
@@ -317,10 +317,8 @@ EXPORT_SYMBOL_GPL(__srcu_read_lock);
  */
 void __srcu_read_unlock(struct srcu_struct *sp, int idx)
 {
-	preempt_disable();
 	smp_mb(); /* C */  /* Avoid leaking the critical section. */
-	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) -= 1;
-	preempt_enable();
+	this_cpu_dec(sp->per_cpu_ref->c[idx]);
 }
 EXPORT_SYMBOL_GPL(__srcu_read_unlock);
 
-- 
1.7.4.4

[PATCH 2/8] srcu: add might_sleep() annotation to synchronize_srcu()

[Lai Jiangshan]

synchronize_srcu() can sleep but it will not sleep if the fast path
succeeds. This annotation will helps us to catch the problem early
if it is called in a wrong contex which can't sleep.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/srcu.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/kernel/srcu.c b/kernel/srcu.c
index b2e4f36..48d0edb 100644
--- a/kernel/srcu.c
+++ b/kernel/srcu.c
@@ -417,6 +417,7 @@ static void __synchronize_srcu(struct srcu_struct *sp, int trycount)
 			   !lock_is_held(&rcu_sched_lock_map),
 			   "Illegal synchronize_srcu() in same-type SRCU (or RCU) read-side critical section");
 
+	might_sleep();
 	init_completion(&rcu.completion);
 
 	head->next = NULL;
-- 
1.7.4.4

[PATCH 3/8] srcu: simple cleanup for cleanup_srcu_struct()

[Lai Jiangshan]

Pack 6 lines of code into 2 lines.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/srcu.c |    8 ++------
 1 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/kernel/srcu.c b/kernel/srcu.c
index 48d0edb..ac08970 100644
--- a/kernel/srcu.c
+++ b/kernel/srcu.c
@@ -278,12 +278,8 @@ static int srcu_readers_active(struct srcu_struct *sp)
  */
 void cleanup_srcu_struct(struct srcu_struct *sp)
 {
-	int sum;
-
-	sum = srcu_readers_active(sp);
-	WARN_ON(sum);  /* Leakage unless caller handles error. */
-	if (sum != 0)
-		return;
+	if (WARN_ON(srcu_readers_active(sp)))
+		return; /* Leakage unless caller handles error. */
 	free_percpu(sp->per_cpu_ref);
 	sp->per_cpu_ref = NULL;
 }
-- 
1.7.4.4

[PATCH 4/8] srcu: srcu_read_lock() can be called from offline cpu

[Lai Jiangshan]

SRCU is based on its own statemachine and it doesn't
relies on normal RCU now, its read critical section can be used in
offline cpu, so we remove the check and the comments.

It partially reverts c0d6d01b(the part for SRCU).

It also makes the codes match the comments in whatisRCU.txt:

g.	Do you need read-side critical sections that are respected
	even though they are in the middle of the idle loop, during
	user-mode execution, or on an offlined CPU?  If so, SRCU is the
	only choice that will work for you.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 include/linux/srcu.h |    5 -----
 1 files changed, 0 insertions(+), 5 deletions(-)

diff --git a/include/linux/srcu.h b/include/linux/srcu.h
index 6eb691b..ae3ee39 100644
--- a/include/linux/srcu.h
+++ b/include/linux/srcu.h
@@ -163,9 +163,6 @@ void srcu_barrier(struct srcu_struct *sp);
  * power mode. This way we can notice an extended quiescent state to
  * other CPUs that started a grace period. Otherwise we would delay any
  * grace period as long as we run in the idle task.
- *
- * Similarly, we avoid claiming an SRCU read lock held if the current
- * CPU is offline.
  */
 static inline int srcu_read_lock_held(struct srcu_struct *sp)
 {
@@ -173,8 +170,6 @@ static inline int srcu_read_lock_held(struct srcu_struct *sp)
 		return 1;
 	if (rcu_is_cpu_idle())
 		return 0;
-	if (!rcu_lockdep_current_cpu_online())
-		return 0;
 	return lock_is_held(&sp->dep_map);
 }
 
-- 
1.7.4.4

Re: [PATCH 4/8] srcu: srcu_read_lock() can be called from offline cpu

[Paul E. McKenney]

On Thu, Nov 29, 2012 at 04:46:05PM +0800, Lai Jiangshan wrote:
> SRCU is based on its own statemachine and it doesn't
> relies on normal RCU now, its read critical section can be used in
> offline cpu, so we remove the check and the comments.
> 
> It partially reverts c0d6d01b(the part for SRCU).
> 
> It also makes the codes match the comments in whatisRCU.txt:
> 
> g.	Do you need read-side critical sections that are respected
> 	even though they are in the middle of the idle loop, during
> 	user-mode execution, or on an offlined CPU?  If so, SRCU is the
> 	only choice that will work for you.

One thing just occurred to me...  Won't lockdep refuse to operated on
offline CPUs?  If so, one way to handle this would be to flag srcu_struct
structures that were to be used on idle and offline CPUs, and avoid
using lockdep on them.  This would allow most uses of SRCU to continue
using lockdep, while avoiding lockdep false positives in other cases.

Or am I confused?

							Thanx, Paul

> Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
> ---
>  include/linux/srcu.h |    5 -----
>  1 files changed, 0 insertions(+), 5 deletions(-)
> 
> diff --git a/include/linux/srcu.h b/include/linux/srcu.h
> index 6eb691b..ae3ee39 100644
> --- a/include/linux/srcu.h
> +++ b/include/linux/srcu.h
> @@ -163,9 +163,6 @@ void srcu_barrier(struct srcu_struct *sp);
>   * power mode. This way we can notice an extended quiescent state to
>   * other CPUs that started a grace period. Otherwise we would delay any
>   * grace period as long as we run in the idle task.
> - *
> - * Similarly, we avoid claiming an SRCU read lock held if the current
> - * CPU is offline.
>   */
>  static inline int srcu_read_lock_held(struct srcu_struct *sp)
>  {
> @@ -173,8 +170,6 @@ static inline int srcu_read_lock_held(struct srcu_struct *sp)
>  		return 1;
>  	if (rcu_is_cpu_idle())
>  		return 0;
> -	if (!rcu_lockdep_current_cpu_online())
> -		return 0;
>  	return lock_is_held(&sp->dep_map);
>  }
> 
> -- 
> 1.7.4.4
> 

[PATCH 5/8] srcu: srcu_read_lock() can be called from idle loop

[Lai Jiangshan]

SRCU is based on its own statemachine and it doesn't
relies on normal RCU now, its read critical section can be used in
idle loop, so we remove the check and the comments.

It partially reverts ff195cb6(the part for SRCU).

It also makes the codes match the comments in whatisRCU.txt:

g.	Do you need read-side critical sections that are respected
	even though they are in the middle of the idle loop, during
	user-mode execution, or on an offlined CPU?  If so, SRCU is the
	only choice that will work for you.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 include/linux/srcu.h |   21 +++------------------
 1 files changed, 3 insertions(+), 18 deletions(-)

diff --git a/include/linux/srcu.h b/include/linux/srcu.h
index ae3ee39..04f4121 100644
--- a/include/linux/srcu.h
+++ b/include/linux/srcu.h
@@ -151,25 +151,14 @@ void srcu_barrier(struct srcu_struct *sp);
  * Checks debug_lockdep_rcu_enabled() to prevent false positives during boot
  * and while lockdep is disabled.
  *
- * Note that if the CPU is in the idle loop from an RCU point of view
- * (ie: that we are in the section between rcu_idle_enter() and
- * rcu_idle_exit()) then srcu_read_lock_held() returns false even if
- * the CPU did an srcu_read_lock().  The reason for this is that RCU
- * ignores CPUs that are in such a section, considering these as in
- * extended quiescent state, so such a CPU is effectively never in an
- * RCU read-side critical section regardless of what RCU primitives it
- * invokes.  This state of affairs is required --- we need to keep an
- * RCU-free window in idle where the CPU may possibly enter into low
- * power mode. This way we can notice an extended quiescent state to
- * other CPUs that started a grace period. Otherwise we would delay any
- * grace period as long as we run in the idle task.
+ * Note that SRCU is based on its own statemachine and it doesn't
+ * relies on normal RCU, it can be called from the CPU which
+ * is in the idle loop from an RCU point of view or offline.
  */
 static inline int srcu_read_lock_held(struct srcu_struct *sp)
 {
 	if (!debug_lockdep_rcu_enabled())
 		return 1;
-	if (rcu_is_cpu_idle())
-		return 0;
 	return lock_is_held(&sp->dep_map);
 }
 
@@ -231,8 +220,6 @@ static inline int srcu_read_lock(struct srcu_struct *sp) __acquires(sp)
 	int retval = __srcu_read_lock(sp);
 
 	rcu_lock_acquire(&(sp)->dep_map);
-	rcu_lockdep_assert(!rcu_is_cpu_idle(),
-			   "srcu_read_lock() used illegally while idle");
 	return retval;
 }
 
@@ -246,8 +233,6 @@ static inline int srcu_read_lock(struct srcu_struct *sp) __acquires(sp)
 static inline void srcu_read_unlock(struct srcu_struct *sp, int idx)
 	__releases(sp)
 {
-	rcu_lockdep_assert(!rcu_is_cpu_idle(),
-			   "srcu_read_unlock() used illegally while idle");
 	rcu_lock_release(&(sp)->dep_map);
 	__srcu_read_unlock(sp, idx);
 }
-- 
1.7.4.4

[PATCH 6/8] srcu: update the comments of synchronize_srcu()

[Lai Jiangshan]

The core of srcu is changed, but the comments of synchronize_srcu()
describe the old algorithm. Update it to match the new algorithm.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/srcu.c |   10 ++++++----
 1 files changed, 6 insertions(+), 4 deletions(-)

diff --git a/kernel/srcu.c b/kernel/srcu.c
index ac08970..55524f6 100644
--- a/kernel/srcu.c
+++ b/kernel/srcu.c
@@ -446,10 +446,12 @@ static void __synchronize_srcu(struct srcu_struct *sp, int trycount)
  * synchronize_srcu - wait for prior SRCU read-side critical-section completion
  * @sp: srcu_struct with which to synchronize.
  *
- * Flip the completed counter, and wait for the old count to drain to zero.
- * As with classic RCU, the updater must use some separate means of
- * synchronizing concurrent updates.  Can block; must be called from
- * process context.
+ * Wait for the count to drain to zero of both indexes. To avoid the
+ * possible starvation of synchronize_srcu(), it waits for the count of
+ * the index=((->completed & 1) ^ 1) to drain to zero at first,
+ * and then flip the completed and wait for the count of the other index.
+ *
+ * Can block; must be called from process context.
  *
  * Note that it is illegal to call synchronize_srcu() from the corresponding
  * SRCU read-side critical section; doing so will result in deadlock.
-- 
1.7.4.4

[PATCH 7/8] srcu: update the comments of synchronize_srcu_expedited()

[Lai Jiangshan]

The new synchronize_srcu_expedited() does not use synchronize_rcu_sched_expedited(),
it removed such lock dependence.

This patch only removes this small piece of the comments:
"it is illegal to call this function while holding any lock
that is acquired by a CPU-hotplug notifier"

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/srcu.c |   11 +++++------
 1 files changed, 5 insertions(+), 6 deletions(-)

diff --git a/kernel/srcu.c b/kernel/srcu.c
index 55524f6..38a762f 100644
--- a/kernel/srcu.c
+++ b/kernel/srcu.c
@@ -471,12 +471,11 @@ EXPORT_SYMBOL_GPL(synchronize_srcu);
  * Wait for an SRCU grace period to elapse, but be more aggressive about
  * spinning rather than blocking when waiting.
  *
- * Note that it is illegal to call this function while holding any lock
- * that is acquired by a CPU-hotplug notifier.  It is also illegal to call
- * synchronize_srcu_expedited() from the corresponding SRCU read-side
- * critical section; doing so will result in deadlock.  However, it is
- * perfectly legal to call synchronize_srcu_expedited() on one srcu_struct
- * from some other srcu_struct's read-side critical section, as long as
+ * Note that it is also illegal to call synchronize_srcu_expedited()
+ * from the corresponding SRCU read-side critical section;
+ * doing so will result in deadlock.  However, it is perfectly legal
+ * to call synchronize_srcu_expedited() on one srcu_struct from some
+ * other srcu_struct's read-side critical section, as long as
  * the resulting graph of srcu_structs is acyclic.
  */
 void synchronize_srcu_expedited(struct srcu_struct *sp)
-- 
1.7.4.4

[PATCH 8/8] srcu: use ACCESS_ONCE() to access sp->completed in srcu_read_lock()

[Lai Jiangshan]

Old srcu implement requires sp->completed is loaded in
RCU-sched(preempt_disable()) section.

The new srcu is now not RCU-sched based, it doesn't require the load of
sp->completed and the access to counter must be in the same RCU-sched
read site C.S., so we use ACCESS_ONCE() instead, and move it out of
the preempt_disable() section, preempt_disable() section is only used
for percpu data, not for RCU-sched.

The resulted code is almost as the same as before, but it helps people to
understand the code, and it avoids to add surprise to reviewer: "why we need
rcu_read_lock_sched_held() here?"

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/srcu.c |    3 +--
 1 files changed, 1 insertions(+), 2 deletions(-)

diff --git a/kernel/srcu.c b/kernel/srcu.c
index 38a762f..224400a 100644
--- a/kernel/srcu.c
+++ b/kernel/srcu.c
@@ -294,9 +294,8 @@ int __srcu_read_lock(struct srcu_struct *sp)
 {
 	int idx;
 
+	idx = ACCESS_ONCE(sp->completed) & 0x1;
 	preempt_disable();
-	idx = rcu_dereference_index_check(sp->completed,
-					  rcu_read_lock_sched_held()) & 0x1;
 	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 1;
 	smp_mb(); /* B */  /* Avoid leaking the critical section. */
 	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->seq[idx]) += 1;
-- 
1.7.4.4

Re: [PATCH 8/8] srcu: use ACCESS_ONCE() to access sp->completed in srcu_read_lock()

[Paul E. McKenney]

On Thu, Nov 29, 2012 at 04:46:09PM +0800, Lai Jiangshan wrote:
> Old srcu implement requires sp->completed is loaded in
> RCU-sched(preempt_disable()) section.
> 
> The new srcu is now not RCU-sched based, it doesn't require the load of
> sp->completed and the access to counter must be in the same RCU-sched
> read site C.S., so we use ACCESS_ONCE() instead, and move it out of
> the preempt_disable() section, preempt_disable() section is only used
> for percpu data, not for RCU-sched.
> 
> The resulted code is almost as the same as before, but it helps people to
> understand the code, and it avoids to add surprise to reviewer: "why we need
> rcu_read_lock_sched_held() here?"

The first seven patches look good!

One question about this one -- the current code provided dependency
ordering between the fetch of idx and the increment, but the code after
this patch would not provide this ordering (at least not on Alpha,
and maybe also not in presence of aggressive compiler optimizations).

In the immortal words of MSDOS, "Are you sure?"

							Thanx, Paul

> Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
> ---
>  kernel/srcu.c |    3 +--
>  1 files changed, 1 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/srcu.c b/kernel/srcu.c
> index 38a762f..224400a 100644
> --- a/kernel/srcu.c
> +++ b/kernel/srcu.c
> @@ -294,9 +294,8 @@ int __srcu_read_lock(struct srcu_struct *sp)
>  {
>  	int idx;
> 
> +	idx = ACCESS_ONCE(sp->completed) & 0x1;
>  	preempt_disable();
> -	idx = rcu_dereference_index_check(sp->completed,
> -					  rcu_read_lock_sched_held()) & 0x1;
>  	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 1;
>  	smp_mb(); /* B */  /* Avoid leaking the critical section. */
>  	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->seq[idx]) += 1;
> -- 
> 1.7.4.4
> 

Re: [PATCH 8/8] srcu: use ACCESS_ONCE() to access sp->completed in srcu_read_lock()

[Lai Jiangshan]

On 11/30/2012 06:05 AM, Paul E. McKenney wrote:
> On Thu, Nov 29, 2012 at 04:46:09PM +0800, Lai Jiangshan wrote:
>> Old srcu implement requires sp->completed is loaded in
>> RCU-sched(preempt_disable()) section.
>>
>> The new srcu is now not RCU-sched based, it doesn't require the load of
>> sp->completed and the access to counter must be in the same RCU-sched
>> read site C.S., so we use ACCESS_ONCE() instead, and move it out of
>> the preempt_disable() section, preempt_disable() section is only used
>> for percpu data, not for RCU-sched.
>>
>> The resulted code is almost as the same as before, but it helps people to
>> understand the code, and it avoids to add surprise to reviewer: "why we need
>> rcu_read_lock_sched_held() here?"
> 
> The first seven patches look good!
> 
> One question about this one -- the current code provided dependency
> ordering between the fetch of idx and the increment, but the code after
> this patch would not provide this ordering (at least not on Alpha,
> and maybe also not in presence of aggressive compiler optimizations).
> 
> In the immortal words of MSDOS, "Are you sure?"

Sure, the update site doesn't modify the percpu counter, so there is
no dependency mb needed in read-site. I can ask "where is the corresponding
mb which is paired with this dependency mb?"


The correctness of SRCU is based on
	the wait in synchrinize_srcu()
	the counter and seq and the mbs between them
	X: sp->completed is not necessary here except for reporting how many GP passed.

The starvation-free of SRCU is based on
	split counter and seq into two index,
	split the wait into two waits for both index
	add sp->completed field
	the flip between the two waits
	-> the index for wait and the index for late-enough-after-flip read-site are different.


Thanks,
Lai



>> Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
>> ---
>>  kernel/srcu.c |    3 +--
>>  1 files changed, 1 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/srcu.c b/kernel/srcu.c
>> index 38a762f..224400a 100644
>> --- a/kernel/srcu.c
>> +++ b/kernel/srcu.c
>> @@ -294,9 +294,8 @@ int __srcu_read_lock(struct srcu_struct *sp)
>>  {
>>  	int idx;
>>
>> +	idx = ACCESS_ONCE(sp->completed) & 0x1;
>>  	preempt_disable();
>> -	idx = rcu_dereference_index_check(sp->completed,
>> -					  rcu_read_lock_sched_held()) & 0x1;
>>  	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 1;
>>  	smp_mb(); /* B */  /* Avoid leaking the critical section. */
>>  	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->seq[idx]) += 1;
>> -- 
>> 1.7.4.4
>>
> 
>