On Wed, May 27, 2009 at 10:45:54AM -0400, Mathieu Desnoyers wrote:

* Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:

quoted

On Tue, May 26, 2009 at 09:47:26PM -0400, Mathieu Desnoyers wrote:

quoted

* Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:

quoted

On Tue, May 26, 2009 at 12:41:29PM -0400, Mathieu Desnoyers wrote:

quoted

* Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:

quoted

On Mon, May 25, 2009 at 06:28:43PM -0700, Paul E. McKenney wrote:

quoted

On Tue, May 26, 2009 at 09:03:55AM +0800, Lai Jiangshan wrote:

quoted

Paul E. McKenney wrote:

quoted

Good point -- I should at the very least add a comment to
synchronize_sched_expedited() stating that it cannot be called holding
any lock that is acquired in a CPU hotplug notifier.  If this restriction
causes any problems, then your approach seems like a promising fix.

Reviewed-by: Lai Jiangshan <redacted>

Thank you very much for your review and comments!!!

quoted

quoted

quoted

The coupling of synchronize_sched_expedited() and migration_req
is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled.
   See migration_call::CPU_DEAD

Good.  ;-)

quoted

2) migration_call() is the highest priority of cpu notifiers,
   So even any other cpu notifier calls synchronize_sched_expedited(),
   It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right?  Unless I am
missing something, the current get_online_cpus() approach would deadlock
in this case.

Yes, I mean if using my preempt_disable() approach. The current
get_online_cpus() approach would NOT deadlock in this case also,
we can require get_online_cpus() in cpu notifiers.

I have added the comment for the time being, but should people need to
use this in CPU-hotplug notifiers, then again your preempt_disable()
approach looks to be a promising fix.

I looked more closely at your preempt_disable() suggestion, which you
presented earlier as follows:

quoted

I think we can reuse req->dest_cpu and remove get_online_cpus().
(and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

I am concerned about the following sequence of events:

o	synchronize_sched_expedited() disables preemption, thus blocking
	offlining operations.

o	CPU 1 starts offlining CPU 0.  It acquires the CPU-hotplug lock,
	and proceeds, and is now waiting for preemption to be enabled.

o	synchronize_sched_expedited() disables preemption, sees
	that CPU 0 is online, so initializes and queues a request,
	does a wake-up-process(), and finally does a preempt_enable().

o	CPU 0 is currently running a high-priority real-time process,
	so the wakeup does not immediately happen.

o	The offlining process completes, including the kthread_stop()
	to the migration task.

o	The migration task wakes up, sees kthread_should_stop(),
	and so exits without checking its queue.

o	synchronize_sched_expedited() waits forever for CPU 0 to respond.

I suppose that one way to handle this would be to check for the CPU
going offline before doing the wait_for_completion(), but I am concerned
about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above
sequence of events impossible?

I think you are right, there is a problem there. The simple fact that
this needs to disable preemption to protect against cpu hotplug seems a
bit strange. If I may propose an alternate solution, which assumes that
threads pinned to a CPU are migrated to a different CPU when a CPU goes
offline (and will therefore execute anyway), and that a CPU brought
online after the first iteration on online cpus was already quiescent
(hopefully my assumptions are right). Preemption is left enabled during
all the critical section.

It looks a lot like Lai's approach, except that I use a cpumask (I
thought it looked cleaner and typically involves less operations than
looping on each possible cpu). I also don't disable preemption and
assume that cpu hotplug can happen at any point during this critical
section.

Something along the lines of :

static DECLARE_BITMAP(cpu_wait_expedited_bits, CONFIG_NR_CPUS);
const struct cpumask *const cpu_wait_expedited_mask =
			to_cpumask(cpu_wait_expedited_bits);

	mutex_lock(&rcu_sched_expedited_mutex);
	cpumask_clear(cpu_wait_expedited_mask);
	for_each_online_cpu(cpu) {
		init and queue cpu req, and wake_up_process().
		cpumask_set_cpu(cpu, cpu_wait_expedited_mask);
	}
	for_each_cpu_mask(cpu, cpu_wait_expedited_mask) {
		wait_for_completion(cpu req);
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

There is one concern with this approach : if a CPU is hotunplugged and
hotplugged during the critical section, I think the scheduler would
migrate the thread to a different CPU (upon hotunplug) and let the
thread run on this other CPU. If the target CPU is hotplugged again,
this would mean the thread would have run on a different CPU than the
target. I think we can argue that a CPU going offline and online again
will meet quiescent state requirements, so this should not be a problem.

Having the task runnable on some other CPU is very scary to me.  If the
CPU comes back online, and synchronize_sched_expedited() manages to
run before the task gets migrated back onto that CPU, then the grace
period could be ended too soon.

Well, the idea is that we want all in-flight preempt off sections (as
seen at the beginning of synchronize_sched_expedited()) to be over
before we consider the grace period as ended, right ?

Let's say we read the cpu online mask at a given time (potentially non
atomically, we don't really care).

If, at any point in time while we read the cpu online mask, a CPU
appears to be offline, this means that it cannot hold any in-flight
preempt off section.

Even if that specific CPU comes back online after this moment, and
starts scheduling threads again, these threads cannot ever possibly be
in-flight in the old grace period.

Therefore, my argument is that for rcu_sched (classic rcu), a CPU going
back online while we wait for quiescent state cannot possibly ever start
running a thread in the previous grace period.

My second argument is that if a CPU is hotunplugging while we wait for
QS, either :

- It lets the completion thread run before it goes offline. That's fine
- It goes offline and the completion thread is migrated to another CPU.
  This will just make synchronize_sched_expedited() wait for one more
  completion that will execute on the CPU the thread has migrated to.
  Again, we don't care.
- It goes offline/online/offline/online/... : We go back to my first
  argument, which states that if a CPU is out of the cpu online mask at
  any given time after we started the synchronize_sched_expedited()
  execution, it cannot possibly hold an in-flight preempt off section
  belonging to the old GP.

Or am I missing something ?

I am worried (perhaps unnecessarily) about the CPU coming online,
its kthread still running on some other CPU, someone doing a
synchronize_sched_expedited(), which then might possibly complete before
the kthread migrates back where it belongs.  If the newly onlined CPU is
in an extended RCU read-side critical section, we might end the expedited
grace period too soon.

My turn.  Am I missing something?  ;-)

If the completion kthreads only live within the boundary of the 
rcu_sched_expedited_mutex critical section, we never face this problem.

Therefore, all kthreads created for a given expedited grace period
should be waited for before the rcu_sched_expedited_mutex is released.

True, but the overhead of creating (say) 100 kthreads is not so consistent
with the "expedited" in synchronize_sched_expedited().

Here, I don't know the specific behavior of the threads you are willing
to use, but I see two possibilities when facing cpu hotplug :

- Either those threads are always active in the system, _really_ tied to
  a CPU and the hotunplug event kills them and sends their completion.
  (this is I think what Lai described)

Yep.  And this is what v7 of the patch did.  Lai would like me to get
rid of the get_online_cpus(), replacing it with preempt_disable().
Which I find to be incredibly scary, given the possibility of the
kthread somehow executing on some other CPU, thus breaking RCU.

But see my next reply to Lai.

- Or we create them while holding the rcu_sched_expedited_mutex, pin
  them to a CPU. They are less strictly bound to a CPU and get migrated
  to a different CPU upon hotunplug. Note that their life-span is
  limited to the rcu_sched_expedited_mutex section, because we expect
  them to die after completion. This implies a thread creation overhead.

And the thread-creation/destruction overhead is fatal, I believe.

Hopefully one of the solutions I describe above match the current
implementation. :)

#1.  ;-)

							Thanx, Paul

Mathieu

quoted

						Thanx, Paul

quoted

Mathieu

quoted

All of this is intended to make synchronize_sched_expedited() be able to
run in a CPU hotplug notifier.  Do we have an example where someone
really wants to do this?  If not, I am really starting to like v7 of
the patch.  ;-)

If someone really does need to run synchronize_sched_expedited() from a
CPU hotplug notifier, perhaps a simpler approach is to have something
like a try_get_online_cpus(), and just invoke synchronize_sched() upon
failure:

	void synchronize_sched_expedited(void)
	{
		int cpu;
		unsigned long flags;
		struct rq *rq;
		struct migration_req *req;

		mutex_lock(&rcu_sched_expedited_mutex);
		if (!try_get_online_cpus()) {
			synchronize_sched();
			return;
		}

		/* rest of synchronize_sched_expedited()... */

But I would want to see a real need for this beforehand.

							Thanx, Paul

-- 
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

-- 
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html