[RFC PATCH 1/1] rcu: Use separate wait queues for leaders and followers

[RFC PATCH 1/1] rcu: Use separate wait queues for leaders and followers

[Pranith Kumar]

Commit fbce7497ee5a ("rcu: Parallelize and economize NOCB kthread wakeups")

tries to reduce the wake up overhead by creating leader and follower nocb
kthreads. 

One thing overlooked here is that all the kthreads wait on the same wait queue.
When we try to wake up the leader threads on the wait queue, we also try to wake
up the follower threads because of which there is still wake up overhead. 

This commit tries to avoid that by using separate wait queues for the leaders and
followers.

Signed-off-by: Pranith Kumar <bobby.prani@gmail.com>
---
 kernel/rcu/tree.h        |  3 ++-
 kernel/rcu/tree_plugin.h | 11 ++++++-----
 2 files changed, 8 insertions(+), 6 deletions(-)

diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
index f703ea8..915ca71 100644
--- a/kernel/rcu/tree.h
+++ b/kernel/rcu/tree.h
@@ -348,7 +348,8 @@ struct rcu_data {
 	atomic_long_t nocb_follower_count_lazy; /*  (approximate). */
 	int nocb_p_count;		/* # CBs being invoked by kthread */
 	int nocb_p_count_lazy;		/*  (approximate). */
-	wait_queue_head_t nocb_wq;	/* For nocb kthreads to sleep on. */
+	wait_queue_head_t nocb_leader_wq; /* leader kthreads sleep on. */
+	wait_queue_head_t nocb_follower_wq; /* follower kthreads sleep on. */
 	struct task_struct *nocb_kthread;
 	bool nocb_defer_wakeup;		/* Defer wakeup of nocb_kthread. */
 
diff --git a/kernel/rcu/tree_plugin.h b/kernel/rcu/tree_plugin.h
index 4242c94..bd6faba 100644
--- a/kernel/rcu/tree_plugin.h
+++ b/kernel/rcu/tree_plugin.h
@@ -2045,7 +2045,7 @@ static void wake_nocb_leader(struct rcu_data *rdp, bool force)
 	if (!ACCESS_ONCE(rdp_leader->nocb_leader_wake) || force) {
 		/* Prior xchg orders against prior callback enqueue. */
 		ACCESS_ONCE(rdp_leader->nocb_leader_wake) = true;
-		wake_up(&rdp_leader->nocb_wq);
+		wake_up(&rdp_leader->nocb_leader_wq);
 	}
 }
 
@@ -2220,7 +2220,7 @@ wait_again:
 	/* Wait for callbacks to appear. */
 	if (!rcu_nocb_poll) {
 		trace_rcu_nocb_wake(my_rdp->rsp->name, my_rdp->cpu, "Sleep");
-		wait_event_interruptible(my_rdp->nocb_wq,
+		wait_event_interruptible(my_rdp->nocb_leader_wq,
 					 ACCESS_ONCE(my_rdp->nocb_leader_wake));
 		/* Memory barrier handled by smp_mb() calls below and repoll. */
 	} else if (firsttime) {
@@ -2300,7 +2300,7 @@ wait_again:
 			 * List was empty, wake up the follower.
 			 * Memory barriers supplied by atomic_long_add().
 			 */
-			wake_up(&rdp->nocb_wq);
+			wake_up(&rdp->nocb_follower_wq);
 		}
 	}
 
@@ -2321,7 +2321,7 @@ static void nocb_follower_wait(struct rcu_data *rdp)
 		if (!rcu_nocb_poll) {
 			trace_rcu_nocb_wake(rdp->rsp->name, rdp->cpu,
 					    "FollowerSleep");
-			wait_event_interruptible(rdp->nocb_wq,
+			wait_event_interruptible(rdp->nocb_follower_wq,
 						 ACCESS_ONCE(rdp->nocb_follower_head));
 		} else if (firsttime) {
 			/* Don't drown trace log with "Poll"! */
@@ -2489,7 +2489,8 @@ void __init rcu_init_nohz(void)
 static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp)
 {
 	rdp->nocb_tail = &rdp->nocb_head;
-	init_waitqueue_head(&rdp->nocb_wq);
+	init_waitqueue_head(&rdp->nocb_leader_wq);
+	init_waitqueue_head(&rdp->nocb_follower_wq);
 	rdp->nocb_follower_tail = &rdp->nocb_follower_head;
 }
 
-- 
1.9.1

Re: [RFC PATCH 1/1] rcu: Use separate wait queues for leaders and followers

[Pranith Kumar]

On Mon, Jul 28, 2014 at 10:58 AM, Pranith Kumar <bobby.prani@gmail.com> wrote:
> Commit fbce7497ee5a ("rcu: Parallelize and economize NOCB kthread wakeups")
>
> tries to reduce the wake up overhead by creating leader and follower nocb
> kthreads.
>
> One thing overlooked here is that all the kthreads wait on the same wait queue.
> When we try to wake up the leader threads on the wait queue, we also try to wake
> up the follower threads because of which there is still wake up overhead.
>
> This commit tries to avoid that by using separate wait queues for the leaders and
> followers.

This solution is still not the best we can do. All the followers will
still wait in one wait queue and we try to wake them up all each time
we call wake_up on the follower wait queue.

To illustrate, let me take the original example in the above commit.
Let us say there are 4096 nocb kthreads, 64 leaders each of which have
64 followers.

The grace period kthread will now try to wake up only 64 leader nocb
kthreads, which is better than before, but each leader will try to
wake up all the followers on the follower wait queue. It would be
great if each leader had its own follower wait queue to wake up, but I
guess that is a stretch.

Thoughts?

--
Pranith

Re: [RFC PATCH 1/1] rcu: Use separate wait queues for leaders and followers

[Paul E. McKenney]

On Mon, Jul 28, 2014 at 10:58:07AM -0400, Pranith Kumar wrote:
> Commit fbce7497ee5a ("rcu: Parallelize and economize NOCB kthread wakeups")
> 
> tries to reduce the wake up overhead by creating leader and follower nocb
> kthreads. 
> 
> One thing overlooked here is that all the kthreads wait on the same wait queue.
> When we try to wake up the leader threads on the wait queue, we also try to wake
> up the follower threads because of which there is still wake up overhead. 
> 
> This commit tries to avoid that by using separate wait queues for the leaders and
> followers.
> 
> Signed-off-by: Pranith Kumar <bobby.prani@gmail.com>

But there is a separate rcu_data structure for each CPU.  This means that
the pre-existing ->nocb_wq is automatically either a leader waitqueue
or a follower waitqueue, depending on whether the enclosing rcu_data
structure is a leader or a follower.  So I don't see how adding the
separate ->nocb_leader_wq and ->nocb_follower_wq is doing anything
other than wasting memory.  After all, with your patch, a given rcu_data
structure will use either ->nocb_leader_wq or ->nocb_follower_wq, and
the other will remain unused.

So unless I am missing something subtle here, I must say "no" to this one.

							Thanx, Paul

> ---
>  kernel/rcu/tree.h        |  3 ++-
>  kernel/rcu/tree_plugin.h | 11 ++++++-----
>  2 files changed, 8 insertions(+), 6 deletions(-)
> 
> diff --git a/kernel/rcu/tree.h b/kernel/rcu/tree.h
> index f703ea8..915ca71 100644
> --- a/kernel/rcu/tree.h
> +++ b/kernel/rcu/tree.h
> @@ -348,7 +348,8 @@ struct rcu_data {
>  	atomic_long_t nocb_follower_count_lazy; /*  (approximate). */
>  	int nocb_p_count;		/* # CBs being invoked by kthread */
>  	int nocb_p_count_lazy;		/*  (approximate). */
> -	wait_queue_head_t nocb_wq;	/* For nocb kthreads to sleep on. */
> +	wait_queue_head_t nocb_leader_wq; /* leader kthreads sleep on. */
> +	wait_queue_head_t nocb_follower_wq; /* follower kthreads sleep on. */
>  	struct task_struct *nocb_kthread;
>  	bool nocb_defer_wakeup;		/* Defer wakeup of nocb_kthread. */
> 
> diff --git a/kernel/rcu/tree_plugin.h b/kernel/rcu/tree_plugin.h
> index 4242c94..bd6faba 100644
> --- a/kernel/rcu/tree_plugin.h
> +++ b/kernel/rcu/tree_plugin.h
> @@ -2045,7 +2045,7 @@ static void wake_nocb_leader(struct rcu_data *rdp, bool force)
>  	if (!ACCESS_ONCE(rdp_leader->nocb_leader_wake) || force) {
>  		/* Prior xchg orders against prior callback enqueue. */
>  		ACCESS_ONCE(rdp_leader->nocb_leader_wake) = true;
> -		wake_up(&rdp_leader->nocb_wq);
> +		wake_up(&rdp_leader->nocb_leader_wq);
>  	}
>  }
> 
> @@ -2220,7 +2220,7 @@ wait_again:
>  	/* Wait for callbacks to appear. */
>  	if (!rcu_nocb_poll) {
>  		trace_rcu_nocb_wake(my_rdp->rsp->name, my_rdp->cpu, "Sleep");
> -		wait_event_interruptible(my_rdp->nocb_wq,
> +		wait_event_interruptible(my_rdp->nocb_leader_wq,
>  					 ACCESS_ONCE(my_rdp->nocb_leader_wake));
>  		/* Memory barrier handled by smp_mb() calls below and repoll. */
>  	} else if (firsttime) {
> @@ -2300,7 +2300,7 @@ wait_again:
>  			 * List was empty, wake up the follower.
>  			 * Memory barriers supplied by atomic_long_add().
>  			 */
> -			wake_up(&rdp->nocb_wq);
> +			wake_up(&rdp->nocb_follower_wq);
>  		}
>  	}
> 
> @@ -2321,7 +2321,7 @@ static void nocb_follower_wait(struct rcu_data *rdp)
>  		if (!rcu_nocb_poll) {
>  			trace_rcu_nocb_wake(rdp->rsp->name, rdp->cpu,
>  					    "FollowerSleep");
> -			wait_event_interruptible(rdp->nocb_wq,
> +			wait_event_interruptible(rdp->nocb_follower_wq,
>  						 ACCESS_ONCE(rdp->nocb_follower_head));
>  		} else if (firsttime) {
>  			/* Don't drown trace log with "Poll"! */
> @@ -2489,7 +2489,8 @@ void __init rcu_init_nohz(void)
>  static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp)
>  {
>  	rdp->nocb_tail = &rdp->nocb_head;
> -	init_waitqueue_head(&rdp->nocb_wq);
> +	init_waitqueue_head(&rdp->nocb_leader_wq);
> +	init_waitqueue_head(&rdp->nocb_follower_wq);
>  	rdp->nocb_follower_tail = &rdp->nocb_follower_head;
>  }
> 
> -- 
> 1.9.1
>