PATCH? rcu: eliminate rcu_ctrlblk.lock

PATCH? rcu: eliminate rcu_ctrlblk.lock

[Oleg Nesterov]

Hello.

I am trying to understand the rcu implementetion.

I can't understand why rcu_ctrlblk.seqcount is needed.
It seems to me it can be replaced by a couple of barriers.

I mean:

void rcu_start_batch(rcu_ctrlblk *rcp, rcu_state *rsp, int next_pending)
{
	if (next_pending)
		rcp->next_pending = 1;

	if (rcp->next_pending && rcp->completed == rcp->cur) {
		rsp->cpumask = cpu_online_map;
		rcp->next_pending = 0;
		smp_wmb();			<------------------
		rcp->cur++;
	}
}

void __rcu_process_callbacks(rcu_ctrlblk *rcp, rcu_state *rsp, rcu_data *rdp)
{
	if (rdp->nxtlist && !rdp->curlist)
	{
		rdp->batch = rcp->cur + 1;
		smp_rmb();			<------------------

		if (!rcp->next_pending) {
			spin_lock(&rsp->lock);
			rcu_start_batch(rcp, rsp, 1);
			spin_unlock(&rsp->lock);
		}
	}
}

This way, if __rcu_process_callbacks() sees incremented rcu_ctrlblk.cur
value, it must also see that rcu_ctrlblk.next_pending == 0 (or rcu_start_batch()
is already in progress on another cpu).

Could you please explain to me where may i be wrong?

Oleg.

Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>

--- 2.6.10-rc2/include/linux/rcupdate.h~	2004-11-15 17:12:20.000000000 +0300
+++ 2.6.10-rc2/include/linux/rcupdate.h	2004-11-27 21:32:49.812077616 +0300
@@ -65,7 +65,6 @@ struct rcu_ctrlblk {
 	long	cur;		/* Current batch number.                      */
 	long	completed;	/* Number of the last completed batch         */
 	int	next_pending;	/* Is the next batch already waiting?         */
-	seqcount_t lock;	/* For atomic reads of cur and next_pending.  */
 } ____cacheline_maxaligned_in_smp;
 
 /* Is batch a before batch b ? */
--- 2.6.10-rc2/kernel/rcupdate.c~	2004-11-08 19:43:29.000000000 +0300
+++ 2.6.10-rc2/kernel/rcupdate.c	2004-11-27 21:40:02.328325152 +0300
@@ -49,9 +49,9 @@
 
 /* Definition for rcupdate control block. */
 struct rcu_ctrlblk rcu_ctrlblk = 
-	{ .cur = -300, .completed = -300 , .lock = SEQCNT_ZERO };
+	{ .cur = -300, .completed = -300 };
 struct rcu_ctrlblk rcu_bh_ctrlblk =
-	{ .cur = -300, .completed = -300 , .lock = SEQCNT_ZERO };
+	{ .cur = -300, .completed = -300 };
 
 /* Bookkeeping of the progress of the grace period */
 struct rcu_state {
@@ -185,10 +185,9 @@ static void rcu_start_batch(struct rcu_c
 			rcp->completed == rcp->cur) {
 		/* Can't change, since spin lock held. */
 		cpus_andnot(rsp->cpumask, cpu_online_map, nohz_cpu_mask);
-		write_seqcount_begin(&rcp->lock);
 		rcp->next_pending = 0;
+		smp_wmb();
 		rcp->cur++;
-		write_seqcount_end(&rcp->lock);
 	}
 }
 
@@ -319,8 +318,6 @@ static void __rcu_process_callbacks(stru
 
 	local_irq_disable();
 	if (rdp->nxtlist && !rdp->curlist) {
-		int next_pending, seq;
-
 		rdp->curlist = rdp->nxtlist;
 		rdp->curtail = rdp->nxttail;
 		rdp->nxtlist = NULL;
@@ -330,14 +327,12 @@ static void __rcu_process_callbacks(stru
 		/*
 		 * start the next batch of callbacks
 		 */
-		do {
-			seq = read_seqcount_begin(&rcp->lock);
-			/* determine batch number */
-			rdp->batch = rcp->cur + 1;
-			next_pending = rcp->next_pending;
-		} while (read_seqcount_retry(&rcp->lock, seq));
 
-		if (!next_pending) {
+		/* determine batch number */
+		rdp->batch = rcp->cur + 1;
+		smp_rmb();
+
+		if (!rcp->next_pending) {
 			/* and start it/schedule start if it's a new batch */
 			spin_lock(&rsp->lock);
 			rcu_start_batch(rcp, rsp, 1);

Re: PATCH? rcu: eliminate rcu_ctrlblk.lock

[Manfred Spraul]

Oleg Nesterov wrote:

>Hello.
>
>I am trying to understand the rcu implementetion.
>
>I can't understand why rcu_ctrlblk.seqcount is needed.
>It seems to me it can be replaced by a couple of barriers.
>
>  
>

Your patch would add one new corner case:

start: next_pending==1. rcp->cur == 11.
cpu 1: rcu_start_back sets next_pending to 0.
cpu 2: rdp->batch = rcp->cur + 1 [i.e. wait for end of period 12]
cpu 2: notices next_pending == 0, tries to acquire the spinlock [blocks]
cpu 1: rcp->cur++ [i.e. start period 12]
cpu 1: releases the spinlock
cpu 2: gets the spinlock, sets next_pending to 1 and exits.

Now next_pending is 1 [i.e. at the end of grace period 12 grace period 
13 is automatically started], although noone has callbacks waiting for 
period 13.

This is not fatal: the combination is rare, so perhaps we could tolerate 
the race. But on the other hand the sequence locks are outside of the 
hot paths and not much slower than a smp_rmb().

Dipankar - what do you think?

--
    Manfred

Re: PATCH? rcu: eliminate rcu_ctrlblk.lock

[Oleg Nesterov]

Manfred Spraul wrote:
>
> Your patch would add one new corner case:
>
> start: next_pending==1. rcp->cur == 11.
> cpu 1: rcu_start_back sets next_pending to 0.
> cpu 2: rdp->batch = rcp->cur + 1 [i.e. wait for end of period 12]
> cpu 2: notices next_pending == 0, tries to acquire the spinlock [blocks]
> cpu 1: rcp->cur++ [i.e. start period 12]
> cpu 1: releases the spinlock
> cpu 2: gets the spinlock, sets next_pending to 1 and exits.
>
> Now next_pending is 1 [i.e. at the end of grace period 12 grace period
> 13 is automatically started], although noone has callbacks waiting for
> period 13.

Yes. But if i understand correctly, the current behaviour a bit worse.
In this scenario rcu_process_callbacks() on cpu 2 will re-read cur==12
and next_pendind==0 and call start_batch(), so grace period 13 will be
started at the end of grace period 12 anyway.

The difference is that with this patch the 'curlist' will be flushed when
the grace period 12 is completed, while the current code will postpone it
up to 13.

Oleg.