Skip to contentSkip to conversation

rcu: don't check ->donelist in __rcu_pending()

PATCH In review Oleg Nesterov 4 participants 17 messages Jan 8, 2006 – Jan 11, 2006

lore
Share & tools
lore
#0 lore raw

PATCH 2/5 rcu: don't check ->donelist in __rcu_pending()

->donelist becomes != NULL only in rcu_process_callbacks().

rcu_process_callbacks() always calls rcu_do_batch() when ->donelist != NULL.

rcu_do_batch() schedules rcu_process_callbacks() again if ->donelist was not flushed entirely.

So ->donelist != NULL means that rcu_tasklet is either TASKLET_STATE_SCHED or TASKLET_STATE_RUN, we don't need to check it in __rcu_pending().

[ This patch was tested with rcutorture.ko, I don't understand
it's output, but it says "End of test: SUCCESS". So if this patch incorrect blame Paul, not me! ]

kernel/rcupdate.c renamed from kernel/rcupdate.c~2_DONE +0 -4
@@ -454,10 +454,6 @@ static int __rcu_pending(struct rcu_ctrl
 	if (!rdp->curlist && rdp->nxtlist)
 		return 1;
 
-	/* This cpu has finished callbacks to invoke */
-	if (rdp->donelist)
-		return 1;
-
 	/* The rcu core waits for a quiescent state from the cpu */
 	if (rdp->quiescbatch != rcp->cur || rdp->qs_pending)
 		return 1;
#1 lore raw
Quoted 8 lines · Oleg Nesterov

->donelist becomes != NULL only in rcu_process_callbacks().

rcu_process_callbacks() always calls rcu_do_batch() when ->donelist != NULL.

rcu_do_batch() schedules rcu_process_callbacks() again if ->donelist was not flushed entirely.

Quoted 7 lines

So ->donelist != NULL means that rcu_tasklet is either TASKLET_STATE_SCHED or TASKLET_STATE_RUN, we don't need to check it in __rcu_pending().

[ This patch was tested with rcutorture.ko, I don't understand
it's output, but it says "End of test: SUCCESS". So if this patch incorrect blame Paul, not me! ]

;-)

Did you run the newest version of rcutorture.ko that includes Vatsa's CPU-hotplug additions?

Thanx, Paul

Quoted 16 lines
kernel/rcupdate.c renamed from kernel/rcupdate.c~2_DONE +0 -4
@@ -454,10 +454,6 @@ static int __rcu_pending(struct rcu_ctrl
 	if (!rdp->curlist && rdp->nxtlist)
 		return 1;
 
-	/* This cpu has finished callbacks to invoke */
-	if (rdp->donelist)
-		return 1;
-
 	/* The rcu core waits for a quiescent state from the cpu */
 	if (rdp->quiescbatch != rcp->cur || rdp->qs_pending)
 		return 1;
#2 lore raw
In reply to Oleg Nesterov
Quoted 11 lines · Oleg Nesterov

->donelist becomes != NULL only in rcu_process_callbacks().

rcu_process_callbacks() always calls rcu_do_batch() when ->donelist != NULL.

rcu_do_batch() schedules rcu_process_callbacks() again if ->donelist was not flushed entirely.

So ->donelist != NULL means that rcu_tasklet is either TASKLET_STATE_SCHED or TASKLET_STATE_RUN, we don't need to check it in __rcu_pending().

Do I smell a bug wrt CPU Hotplug here? Basically, I see that we do a rcu_move_batch of ->curlist and ->nxtlist of the dead CPU. Why not ->donelist? If we have to do a rcu_move_batch of ->donelist also, then perhaps the ->donelist != NULL check is required in rcu_pending? This is considering that the RCU tasklet of the dead CPU is killed (rather than moved over to a different CPU).

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#3 lore raw
Quoted 9 lines · Srivatsa Vaddagiri
Quoted 8 lines · Oleg Nesterov

->donelist becomes != NULL only in rcu_process_callbacks().

rcu_process_callbacks() always calls rcu_do_batch() when ->donelist != NULL.

rcu_do_batch() schedules rcu_process_callbacks() again if ->donelist was not flushed entirely.

Quoted 7 lines
Quoted 3 lines

So ->donelist != NULL means that rcu_tasklet is either TASKLET_STATE_SCHED or TASKLET_STATE_RUN, we don't need to check it in __rcu_pending().

Do I smell a bug wrt CPU Hotplug here? Basically, I see that we do a rcu_move_batch of ->curlist and ->nxtlist of the dead CPU. Why not ->donelist?

After the quick reading CPU Hotplug code I think you are right, there is a bug in rcu_offline_cpu(). It should also move ->donelist, it is lost otherwise.

Quoted 3 lines
            If we have to do a rcu_move_batch of ->donelist also,

then perhaps the ->donelist != NULL check is required in rcu_pending?

rcu_move_batch() always adds entries to the ->nxttail, so I think this patch is correct.

Quoted 2 lines

This is considering that the RCU tasklet of the dead
CPU is killed (rather than moved over to a different CPU).

Yes, it is killed explicitly in rcu_offline_cpu() via tasklet_kill_immediate().

Note that we can't remove this tasklet_kill_immediate() and rely on takeover_tasklets(). rcu_process_callbacks() does __get_cpu_var(), so it can't find orphaned rcu_data anyway if the tasklet was moved to another cpu.

So, do we need something like this (untested, uncompiled) patch or not?

kernel/rcupdate.c renamed from kernel/rcupdate.c~ +2 -1
@@ -355,8 +355,9 @@ static void __rcu_offline_cpu(struct rcu
 	spin_unlock_bh(&rcp->lock);
 	rcu_move_batch(this_rdp, rdp->curlist, rdp->curtail);
 	rcu_move_batch(this_rdp, rdp->nxtlist, rdp->nxttail);
-
+	rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail);
 }
+
 static void rcu_offline_cpu(int cpu)
 {
 	struct rcu_data *this_rdp = &get_cpu_var(rcu_data);

Oleg.

#4 lore raw
Quoted 7 lines · Oleg Nesterov
Quoted 3 lines · Srivatsa Vaddagiri
            If we have to do a rcu_move_batch of ->donelist also,

then perhaps the ->donelist != NULL check is required in rcu_pending?

rcu_move_batch() always adds entries to the ->nxttail, so I think this patch is correct.

Hmm ..adding entries on dead cpu's ->donelist to ->nxtlist of some other CPU doesnt make sense (it re-triggers graceperiods for all those callbacks which is not needed). Maybe rcu_move_batch should take that into account and instead add to ->donelist of current CPU which is processing the CPU_DEAD callback.

In which case, ->donelist != NULL check is still reqd in rcu_pending ?

Signature · 5 lines
Thanks and Regards,
Srivatsa Vaddagiri,
Linux Technology Center,
IBM Software Labs,
Bangalore, INDIA - 560017
#5 lore raw
Quoted 7 lines · Srivatsa Vaddagiri
Quoted 5 lines · Oleg Nesterov
Quoted 3 lines · Srivatsa Vaddagiri
            If we have to do a rcu_move_batch of ->donelist also,

then perhaps the ->donelist != NULL check is required in rcu_pending?

Quoted 6 lines
Quoted 2 lines

rcu_move_batch() always adds entries to the ->nxttail, so I think this patch is correct.

Hmm ..adding entries on dead cpu's ->donelist to ->nxtlist of some other CPU doesnt make sense (it re-triggers graceperiods for all those callbacks which is not needed).

Yes, but this is rare event, so ...

Quoted 2 lines

Maybe rcu_move_batch should take that into account and instead add
to ->donelist of current CPU which is processing the CPU_DEAD callback.

May be you are right,

Quoted 1 line

In which case, ->donelist != NULL check is still reqd in rcu_pending ?

Yes, in that case it is required. Do you think it is worth to optimize CPU_DEAD case?

Oleg.

#6 lore raw
In reply to Oleg Nesterov
Quoted 11 lines · Oleg Nesterov

->donelist becomes != NULL only in rcu_process_callbacks().

rcu_process_callbacks() always calls rcu_do_batch() when ->donelist != NULL.

rcu_do_batch() schedules rcu_process_callbacks() again if ->donelist was not flushed entirely.

So ->donelist != NULL means that rcu_tasklet is either TASKLET_STATE_SCHED or TASKLET_STATE_RUN, we don't need to check it in __rcu_pending().

As Vatsa noted, this is needed if the CPU-hotplug case moves from ->donelist to ->donelist. It could be omitted if CPU-hotplug instead moves from ->donelist to ->nextlist, as is the case in Oleg's patch. The extra grace-period delay should not be a problem for the presumably rare hotplug case, but:

o the extra test in __rcu_pending() should be quite inexpensive,
since the cacheline is already loaded given the earlier tests.

o although tasklet_schedule() looks to be perfectly reliable
right now, and although any bugs in tasklet_schedule() must be fixed, having RCU leakage be the major symptom of tasklet_schedule() failure sounds quite unfriendly to me.

So I am not (yet) convinced that this patch is the way to go.

Thanx, Paul

Quoted 20 lines

[ This patch was tested with rcutorture.ko, I don't understand
it's output, but it says "End of test: SUCCESS". So if this patch incorrect blame Paul, not me! ]

kernel/rcupdate.c renamed from kernel/rcupdate.c~2_DONE +0 -4
@@ -454,10 +454,6 @@ static int __rcu_pending(struct rcu_ctrl
 	if (!rdp->curlist && rdp->nxtlist)
 		return 1;
 
-	/* This cpu has finished callbacks to invoke */
-	if (rdp->donelist)
-		return 1;
-
 	/* The rcu core waits for a quiescent state from the cpu */
 	if (rdp->quiescbatch != rcp->cur || rdp->qs_pending)
 		return 1;
#7 lore raw
Quoted 14 lines · Paul E. McKenney
Quoted 11 lines · Oleg Nesterov

->donelist becomes != NULL only in rcu_process_callbacks().

rcu_process_callbacks() always calls rcu_do_batch() when ->donelist != NULL.

rcu_do_batch() schedules rcu_process_callbacks() again if ->donelist was not flushed entirely.

So ->donelist != NULL means that rcu_tasklet is either TASKLET_STATE_SCHED or TASKLET_STATE_RUN, we don't need to check it in __rcu_pending().

Quoted 5 lines

As Vatsa noted, this is needed if the CPU-hotplug case moves from ->donelist to ->donelist. It could be omitted if CPU-hotplug instead moves from ->donelist to ->nextlist, as is the case in Oleg's patch. The extra grace-period delay should not be a problem for the presumably rare hotplug case, but:

Just to be sure. So do you agree that CPU-hotplug is buggy now (without that patch) ?

Quoted 2 lines

o the extra test in __rcu_pending() should be quite inexpensive,
since the cacheline is already loaded given the earlier tests.

Yes, it was a cleanup, not an optimization.

Quoted 6 lines

o although tasklet_schedule() looks to be perfectly reliable
right now, and although any bugs in tasklet_schedule() must be fixed, having RCU leakage be the major symptom of tasklet_schedule() failure sounds quite unfriendly to me.

So I am not (yet) convinced that this patch is the way to go.

Ok, I agree.

Oleg.

#8 lore raw
Quoted 15 lines · Oleg Nesterov
Quoted 14 lines · Paul E. McKenney
Quoted 11 lines · Oleg Nesterov

->donelist becomes != NULL only in rcu_process_callbacks().

rcu_process_callbacks() always calls rcu_do_batch() when ->donelist != NULL.

rcu_do_batch() schedules rcu_process_callbacks() again if ->donelist was not flushed entirely.

So ->donelist != NULL means that rcu_tasklet is either TASKLET_STATE_SCHED or TASKLET_STATE_RUN, we don't need to check it in __rcu_pending().

Quoted 8 lines
Quoted 5 lines

As Vatsa noted, this is needed if the CPU-hotplug case moves from ->donelist to ->donelist. It could be omitted if CPU-hotplug instead moves from ->donelist to ->nextlist, as is the case in Oleg's patch. The extra grace-period delay should not be a problem for the presumably rare hotplug case, but:

Just to be sure. So do you agree that CPU-hotplug is buggy now (without that patch) ?

Hmmm... So your thought is that __rcu_offline_cpu() moves nxtlist and curlist, but not donelist, but then returns to rcu_offline_cpu(), which might well do the tasklet_kill_immediate() before the tasklet completed processing all of donelist.

Seems plausible to me. If true, your patch adding the following statement to the ed of __rcu_offline_cpu seems like a reasonable fix:

	rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail);

Vatsa, is there something that Oleg and I are missing?

Quoted 5 lines
Quoted 2 lines

o the extra test in __rcu_pending() should be quite inexpensive,
since the cacheline is already loaded given the earlier tests.

Yes, it was a cleanup, not an optimization.

Quoted 8 lines
Quoted 6 lines

o although tasklet_schedule() looks to be perfectly reliable
right now, and although any bugs in tasklet_schedule() must be fixed, having RCU leakage be the major symptom of tasklet_schedule() failure sounds quite unfriendly to me.

So I am not (yet) convinced that this patch is the way to go.

Ok, I agree.

Sounds good!

Thanx, Paul

#9 lore raw
Quoted 11 lines · Paul E. McKenney

Hmmm... So your thought is that __rcu_offline_cpu() moves nxtlist and curlist, but not donelist, but then returns to rcu_offline_cpu(), which might well do the tasklet_kill_immediate() before the tasklet completed processing all of donelist.

Seems plausible to me. If true, your patch adding the following statement to the ed of __rcu_offline_cpu seems like a reasonable fix:

	rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail);

Vatsa, is there something that Oleg and I are missing?

I think this should take care of the CPU Hotplug bug, with the caveat that the callbacks on ->donelist will wait for additional grace period before being invoked (which seems ok).

Oleg, do you want to resend the patch after some testing?

- vatsa

#10 lore raw

PATCH 1/1 rcu: fix hotplug-cpu ->donelist leak

Pointed out by Srivatsa Vaddagiri <[email protected]>.

rcu_do_batch() stops after processing maxbatch callbacks on ->donelist leaving rcu_tasklet in TASKLET_STATE_SCHED state.

If CPU_DEAD event happens remaining ->donelist entries are lost, rcu_offline_cpu() kills this tasklet.

With this patch ->donelist migrates along with ->curlist and ->nxtlist to the current cpu.

Compile tested.

kernel/rcupdate.c renamed from kernel/rcupdate.c~4_HPFIX +2 -1
@@ -343,8 +343,9 @@ static void __rcu_offline_cpu(struct rcu
 	spin_unlock_bh(&rcp->lock);
 	rcu_move_batch(this_rdp, rdp->curlist, rdp->curtail);
 	rcu_move_batch(this_rdp, rdp->nxtlist, rdp->nxttail);
-
+	rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail);
 }
+
 static void rcu_offline_cpu(int cpu)
 {
 	struct rcu_data *this_rdp = &get_cpu_var(rcu_data);
#11 lore raw

Re: [PATCH] rcu: fix hotplug-cpu ->donelist leak

Quoted 6 lines · Oleg Nesterov

Pointed out by Srivatsa Vaddagiri <[email protected]>.

rcu_do_batch() stops after processing maxbatch callbacks on ->donelist leaving rcu_tasklet in TASKLET_STATE_SCHED state.

Quoted 7 lines

If CPU_DEAD event happens remaining ->donelist entries are lost, rcu_offline_cpu() kills this tasklet.

With this patch ->donelist migrates along with ->curlist and ->nxtlist to the current cpu.

Compile tested.

Looks good, but I fat-fingered my test scripts and left it out. :-/

Started another RCU-torture run...

Thanx, Paul

Quoted 16 lines
kernel/rcupdate.c renamed from kernel/rcupdate.c~4_HPFIX +2 -1
@@ -343,8 +343,9 @@ static void __rcu_offline_cpu(struct rcu
 	spin_unlock_bh(&rcp->lock);
 	rcu_move_batch(this_rdp, rdp->curlist, rdp->curtail);
 	rcu_move_batch(this_rdp, rdp->nxtlist, rdp->nxttail);
-
+	rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail);
 }
+
 static void rcu_offline_cpu(int cpu)
 {
 	struct rcu_data *this_rdp = &get_cpu_var(rcu_data);
Acked-by on v1 1/1
#12 lore raw

Re: [PATCH] rcu: fix hotplug-cpu ->donelist leak

In reply to Oleg Nesterov
Quoted 6 lines · Oleg Nesterov

Pointed out by Srivatsa Vaddagiri <[email protected]>.

rcu_do_batch() stops after processing maxbatch callbacks on ->donelist leaving rcu_tasklet in TASKLET_STATE_SCHED state.

Quoted 7 lines

If CPU_DEAD event happens remaining ->donelist entries are lost, rcu_offline_cpu() kills this tasklet.

With this patch ->donelist migrates along with ->curlist and ->nxtlist to the current cpu.

Compile tested.

This passed a ten-hour RCU torture test, with the torture test augmented by Vatsa's CPU-hotplug RCU-torture-test patch.

Thanx, Paul

Quoted 16 lines
kernel/rcupdate.c renamed from kernel/rcupdate.c~4_HPFIX +2 -1
@@ -343,8 +343,9 @@ static void __rcu_offline_cpu(struct rcu
 	spin_unlock_bh(&rcp->lock);
 	rcu_move_batch(this_rdp, rdp->curlist, rdp->curtail);
 	rcu_move_batch(this_rdp, rdp->nxtlist, rdp->nxttail);
-
+	rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail);
 }
+
 static void rcu_offline_cpu(int cpu)
 {
 	struct rcu_data *this_rdp = &get_cpu_var(rcu_data);
#13 lore raw

Re: [PATCH] rcu: fix hotplug-cpu ->donelist leak

Quoted 2 lines · Paul E. McKenney

This passed a ten-hour RCU torture test, with the torture test augmented

Thank you!

Quoted 1 line

by Vatsa's CPU-hotplug RCU-torture-test patch.

I can't find this patch, could you point me?

Oleg.

#14 lore raw

Re: [PATCH] rcu: fix hotplug-cpu ->donelist leak

Quoted 9 lines · Oleg Nesterov
Quoted 2 lines · Paul E. McKenney

This passed a ten-hour RCU torture test, with the torture test augmented

Thank you!

Quoted 1 line

by Vatsa's CPU-hotplug RCU-torture-test patch.

I can't find this patch, could you point me?

http://marc.theaimsgroup.com/?l=linux-kernel&m=113378075217761&w=2

I just realized that I had failed to ack this one, so just did so.

Thanx, Paul

#15 lore raw
In reply to Srivatsa Vaddagiri
Quoted 12 lines · Srivatsa Vaddagiri
Quoted 10 lines · Paul E. McKenney

Hmmm... So your thought is that __rcu_offline_cpu() moves nxtlist and curlist, but not donelist, but then returns to rcu_offline_cpu(), which might well do the tasklet_kill_immediate() before the tasklet completed processing all of donelist.

Seems plausible to me. If true, your patch adding the following statement to the ed of __rcu_offline_cpu seems like a reasonable fix:

      rcu_move_batch(this_rdp, rdp->donelist, rdp->donetail);
Quoted 7 lines
Quoted 1 line

Vatsa, is there something that Oleg and I are missing?

I think this should take care of the CPU Hotplug bug, with the caveat that the callbacks on ->donelist will wait for additional grace period before being invoked (which seems ok).

Oleg, do you want to resend the patch after some testing?

Sure. The problem is that I have no idea how to test this change. However, the patch seems "obviously correct", so I am sending it.

Srivatsa, I am sorry, I forgot to add you on CC: list while re-sending these cleanups. I hope you can see them on lkml.

Oleg.

#16 lore raw
In reply to Oleg Nesterov
Quoted 15 lines · Oleg Nesterov

->donelist becomes != NULL only in rcu_process_callbacks().

So ->donelist != NULL means that rcu_tasklet is either TASKLET_STATE_SCHED or TASKLET_STATE_RUN, we don't need to check it in __rcu_pending().

[ This patch was tested with rcutorture.ko, I don't understand
it's output, but it says "End of test: SUCCESS". So if this patch incorrect blame Paul, not me! ]

kernel/rcupdate.c static int __rcu_pending(struct rcu_ctrl · line 459

Quoted 10 lines
kernel/rcupdate.c renamed from kernel/rcupdate.c~2_DONE +0 -4
@@ -454,10 +454,6 @@ static int __rcu_pending(struct rcu_ctrl
 	if (!rdp->curlist && rdp->nxtlist)
 		return 1;
 
-	/* This cpu has finished callbacks to invoke */
-	if (rdp->donelist)
-		return 1;
-
 	/* The rcu core waits for a quiescent state from the cpu */
 	if (rdp->quiescbatch != rcp->cur || rdp->qs_pending)
 		return 1;

This may not be a good idea. For example, during cpu hotplug, a cpu may inherit a set of finished callbacks that need to be invoked. So, an rcu_pending() check needs to detect that.

Thanks
Dipankar