percpu rwsem -v2

+enum { readers_slow, readers_block };

A bit off-topic probably
but maybe this should not be in kernel/locking/percpu-rwsem.c but in a generic percpu location as this construct is present in the core a few times atleast in:
kernel/irq/irqdesc.c:kstat_irqs

kernel/fork.c:nr_processes

mm/memcontrol.c:mem_cgroup_read_events
mm/memcontrol.c:mem_cgroup_read_stat

kernel/locking/percpu-rwsem.c line 106

Quoted 9 lines

kernel/locking/percpu-rwsem.c +9 -0

+#define per_cpu_sum(var)                                             \
+({                                                                   \
+     typeof(var) __sum = 0;                                          \
+     int cpu;                                                        \
+     for_each_possible_cpu(cpu)                                      \
+             __sum += per_cpu(var, cpu);                             \
+     __sum;                                                          \
+})
+

so maybe put it into include/linux/percpu.h ?

Quoted 2 lines

mm/memcontrol.c:mem_cgroup_read_events
mm/memcontrol.c:mem_cgroup_read_stat

Those seem to be hotplug challenged. I'm thinking dropping that nocpu_base.count[] crap and just iterating all possible CPUs would've been much easier.

Quoted 11 lines

kernel/locking/percpu-rwsem.c line 106

Quoted 9 lines

kernel/locking/percpu-rwsem.c +9 -0

+#define per_cpu_sum(var)                                             \
+({                                                                   \
+     typeof(var) __sum = 0;                                          \
+     int cpu;                                                        \
+     for_each_possible_cpu(cpu)                                      \
+             __sum += per_cpu(var, cpu);                             \
+     __sum;                                                          \
+})
+

so maybe put it into include/linux/percpu.h ?

Yes I can do that.

We can try and use it more after that, there seems to be loads of places that could use this fs/namespace.c fs/inode.c etc..

Hmmm... the only worry I have about this is people using it on u64 on 32bit machines. CPU local ops can do split updates on lower and upper halves and the remotely-read value will be surprising. We have the same issues w/ regular per_cpu accesses to but the summing function / macro is better at giving the false sense of security. Prolly limiting it upto ulong size is a good idea?

Hello, Peter.

Quoted 9 lines · Peter Zijlstra

Agreed, luckily we already have the infrastructure for this, something like so?

include/linux/percpu-defs.h +0 -0

@@ -287,6 +287,16 @@ do {									\
 	preempt_enable();						\
 } while (0)
 

include/linux/percpu-defs.h do { \ · line 293

Quoted 4 lines

include/linux/percpu-defs.h +4 -0

+#define per_cpu_sum(var)						\
+({									\
+	typeof(var) __sum = 0;						\
+	int cpu;							\

Why not __cpu?

include/linux/percpu-rwsem.h +15 -0

+static inline bool percpu_down_read_trylock(struct percpu_rw_semaphore *sem)
+{
+	bool ret = true;
+
+	preempt_disable();
+	__this_cpu_inc(*sem->refcount);
+	if (unlikely(!rcu_sync_is_idle(&sem->rss)))
+		ret = __percpu_down_read_trylock(sem);
+	preempt_enable();
+
+	if (ret)
+		rwsem_acquire_read(&sem->rw_sem.dep_map, 0, 1, _RET_IP_);
+
+	return ret;
+}

The cpu hotplug lock is a rwsem with read-in-write and read-in-read recursion. Implement it as such.

include/linux/percpu-rwsem.h +6 -3

-static inline void percpu_down_read(struct percpu_rw_semaphore *sem)
+static inline void _percpu_down_read(struct percpu_rw_semaphore *sem)
 {
 	might_sleep();
 
-	rwsem_acquire_read(&sem->rw_sem.dep_map, 0, 0, _RET_IP_);
-
 	preempt_disable();
 	/*
 	 * We are in an RCU-sched read-side critical section, so the writer

@@ -46,6 +44,12 @@ static inline void percpu_down_read(stru
 	 */
 }
 
+static inline void percpu_down_read(struct percpu_rw_semaphore *sem)
+{
+	rwsem_acquire_read(&sem->rw_sem.dep_map, 0, 0, _RET_IP_);
+	_percpu_down_read(sem);
+}

void get_online_cpus(void)
{

kernel/cpu.c +6 -1

 	might_sleep();
-	if (cpu_hotplug.active_writer == current)
+
+	/* read in write recursion */
+	if (cpu_hotplug.writer == current)
+		return;
+
+	/* read in read recursion */

kernel/cpu.c static int cpu_hotplug_disabled; · line 92

Quoted 4 lines

kernel/cpu.c +3 -0

+
+	lock_map_acquire_read(&cpu_hotplug.rwsem.rw_sem.dep_map);
+	_percpu_down_read(&cpu_hotplug.rwsem);
 }

Confused... Why do we need _percpu_down_read()? Can't get_online_cpus() just use percpu_down_read() ?

Yes, percpu_down_read() is not recursive, like the normal down_read(). But this does not matter because we rely on ->cpuhp_ref anyway?

kernel/fork.c static struct task_struct *copy_process( · line 1413

Quoted 7 lines

kernel/fork.c +1 -0

@@ -1410,6 +1410,8 @@ static struct task_struct *copy_process(
 	p->sequential_io_avg	= 0;
 #endif
 
+	cpu_hotplug_init_task(p);

This is probably unnecessary, copy_process() should not be called under get_online_cpus().

Quoted 8 lines · Oleg Nesterov

kernel/cpu.c static int cpu_hotplug_disabled; · line 92

Quoted 4 lines

kernel/cpu.c +3 -0

+
+	lock_map_acquire_read(&cpu_hotplug.rwsem.rw_sem.dep_map);
+	_percpu_down_read(&cpu_hotplug.rwsem);
 }

Confused... Why do we need _percpu_down_read()? Can't get_online_cpus() just use percpu_down_read() ?

Quoted 2 lines

Yes, percpu_down_read() is not recursive, like the normal down_read(). But this does not matter because we rely on ->cpuhp_ref anyway?

While we will not call the actual lock, lockdep will still get confused by the inconsistent locking order observed.

Change it and boot, you'll find lockdep output pretty quickly.

Quoted 7 lines

Quoted 7 lines

kernel/fork.c +0 -0

@@ -1410,6 +1410,8 @@ static struct task_struct *copy_process(
 	p->sequential_io_avg	= 0;
 #endif
 

Quoted 4 lines

kernel/fork.c static struct task_struct *copy_process( · line 1413

Quoted 1 line

kernel/fork.c +1 -0

+	cpu_hotplug_init_task(p);

This is probably unnecessary, copy_process() should not be called under get_online_cpus().

Probably true, in which case we could still use the callback to insert a WARN_ON_ONCE(p->cpuhp_ref) :-)

void get_online_cpus(void)
{

kernel/cpu.c +4 -1

 	might_sleep();
-	if (cpu_hotplug.active_writer == current)
+
+	/* read in write recursion */
+	if (cpu_hotplug.writer == current)
+		return;

Quoted 13 lines · Peter Zijlstra

Quoted 10 lines · Oleg Nesterov

kernel/cpu.c static int cpu_hotplug_disabled; · line 92

Quoted 4 lines

kernel/cpu.c +3 -0

+
+	lock_map_acquire_read(&cpu_hotplug.rwsem.rw_sem.dep_map);
+	_percpu_down_read(&cpu_hotplug.rwsem);
 }

Confused... Why do we need _percpu_down_read()? Can't get_online_cpus() just use percpu_down_read() ?

Yes, percpu_down_read() is not recursive, like the normal down_read(). But this does not matter because we rely on ->cpuhp_ref anyway?

Quoted 4 lines

While we will not call the actual lock, lockdep will still get confused by the inconsistent locking order observed.

Change it and boot, you'll find lockdep output pretty quickly.

Hmm. and I simply can't understand why...

Quoted 14 lines · Oleg Nesterov

Quoted 13 lines · Peter Zijlstra

Quoted 10 lines · Oleg Nesterov

kernel/cpu.c static int cpu_hotplug_disabled; · line 92

Quoted 4 lines

kernel/cpu.c +3 -0

+
+	lock_map_acquire_read(&cpu_hotplug.rwsem.rw_sem.dep_map);
+	_percpu_down_read(&cpu_hotplug.rwsem);
 }

Confused... Why do we need _percpu_down_read()? Can't get_online_cpus() just use percpu_down_read() ?

Yes, percpu_down_read() is not recursive, like the normal down_read(). But this does not matter because we rely on ->cpuhp_ref anyway?

Quoted 6 lines

Quoted 4 lines

While we will not call the actual lock, lockdep will still get confused by the inconsistent locking order observed.

Change it and boot, you'll find lockdep output pretty quickly.

Hmm. and I simply can't understand why...

If in one callchain we do:

	get_online_cpus();
	lock(A);

in another we do:

	lock(A);
	get_online_cpus();

lockdep will complain about the inverted lock order, however this is not a problem at all for recursive locks.

Quoted 5 lines · Peter Zijlstra

If in one callchain we do:

	get_online_cpus();
	lock(A);

Quoted 7 lines

in another we do:

	lock(A);
	get_online_cpus();

lockdep will complain about the inverted lock order, however this is not a problem at all for recursive locks.

Ah, but in this case lockdep is right. This is deadlockable because with the new implementation percpu_down_write() blocks the new readers. So this change just hides the valid warning.

Just suppose that the 3rd CPU does percpu_down_write()->down_write() right after the 2nd CPU (above) takes lock(A).

I have to admit that I didn't realize that the code above is currently correct... but it is.

So we need percpu_down_write_dont_block_readers(). I already thought about this before, I'll try to make the patch tomorrow on top of your changes.

This means that we do not need task_struct->cpuhp_ref, but we can't avoid livelock we currently have: cpu_hotplug_begin() can never succeed if the new readers come fast enough.

Quoted 28 lines · Oleg Nesterov

Quoted 5 lines · Peter Zijlstra

If in one callchain we do:

	get_online_cpus();
	lock(A);

Quoted 7 lines

in another we do:

	lock(A);
	get_online_cpus();

lockdep will complain about the inverted lock order, however this is not a problem at all for recursive locks.

Ah, but in this case lockdep is right. This is deadlockable because with the new implementation percpu_down_write() blocks the new readers. So this change just hides the valid warning.

Just suppose that the 3rd CPU does percpu_down_write()->down_write() right after the 2nd CPU (above) takes lock(A).

I have to admit that I didn't realize that the code above is currently correct... but it is.

So we need percpu_down_write_dont_block_readers(). I already thought about this before, I'll try to make the patch tomorrow on top of your changes.

Quoted 3 lines

This means that we do not need task_struct->cpuhp_ref, but we can't avoid livelock we currently have: cpu_hotplug_begin() can never succeed if the new readers come fast enough.

I'm confused.. why isn't the read-in-read recursion good enough?

Quoted 1 line · Peter Zijlstra

I'm confused.. why isn't the read-in-read recursion good enough?

Because the code above can actually deadlock if 2 CPU's do this at the same time?

So we need percpu_down_write_dont_block_readers(). I already thought about this before, I'll try to make the patch tomorrow on top of your changes.

This means that we do not need task_struct->cpuhp_ref, but we can't avoid livelock we currently have: cpu_hotplug_begin() can never succeed if the new readers come fast enough.

fs/locks.c +1 -2

@@ -2650,9 +2660,8 @@ static void *locks_start(struct seq_file
 
 	iter->li_pos = *pos + 1;
 	percpu_down_write(&file_rwsem);
-	lg_global_lock(&file_lock_lglock);
 	spin_lock(&blocked_lock_lock);
-	return seq_hlist_start_percpu(&file_lock_list, &iter->li_cpu, *pos);
+	return seq_hlist_start_percpu(&file_lock_list.hlist, &iter->li_cpu, *pos);
 }

By having stop_two_cpus() acquire two cpu_stopper::locks we gain full order against the global stop_machine which takes each of these locks in order.

kernel/stop_machine.c +7 -0

+static void cpu_stop_queue_work(unsigned int cpu, struct cpu_stop_work *work)
+{
+	struct cpu_stopper *stopper = &per_cpu(cpu_stopper, cpu);
+	unsigned long flags;
+
+	spin_lock_irqsave(&stopper->lock, flags);
+	__cpu_stop_queue_work(cpu, work);
 	spin_unlock_irqrestore(&stopper->lock, flags);
 }

int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void *arg) {

kernel/stop_machine.c +6 -1

-	struct cpu_stop_done done;
+	struct cpu_stopper *stopper1, *stopper2;
 	struct cpu_stop_work work1, work2;
 	struct multi_stop_data msdata;
+	struct cpu_stop_done done;
+	unsigned long flags;
+
+	if (cpu2 < cpu1)
+		swap(cpu1, cpu2);

Suppose that stop_two_cpus(cpu1 => 0, cpu2 => 1) races with stop_machine().

- stop_machine takes the lock on CPU 0, adds the work and drops the lock

- cpu_stop_queue_work() queues both works

- stop_machine takes the lock on CPU 1, etc

In this case both CPU 0 and 1 will run multi_cpu_stop() but they will use different multi_stop_data's, so they will wait for each other forever?

We can of course slap a percpu-rwsem in, but I wonder if there's anything smarter we can do here.

Quoted 2 lines · Peter Zijlstra

We can of course slap a percpu-rwsem in, but I wonder if there's anything smarter we can do here.

Urgh, we cannot use percpu-rwsem here, because that would require percpu_down_write_trylock(), and I'm not sure we can get around the sync_sched() for that.

Now try_stop_cpus(), which requires the down_write_trylock() is used to implement synchronize_sched_expedited().

Using sync_sched() to implement sync_sched_expedited would make me happy, but it does somewhat defeat the purpose.

Paul, why does this use stop_machine anyway? I seemed to remember you sending resched IPIs around.

The rcu_sched_qs() thing would set passed_quiesce, which you can then collect to gauge progress.

Shooting IPIs around is bad enough, but running a full blown stop_machine is really blunt and heavy.

void synchronize_sched_expedited(void)
{

kernel/rcu/tree.c +0 -15

-	while (try_stop_cpus(cma ? cm : cpu_online_mask,
-			     synchronize_sched_expedited_cpu_stop,
-			     NULL) == -EAGAIN) {
-		put_online_cpus();
-		atomic_long_inc(&rsp->expedited_tryfail);
-
-		/* Check to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);
-		if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
-			/* ensure test happens before caller kfree */
-			smp_mb__before_atomic(); /* ^^^ */
-			atomic_long_inc(&rsp->expedited_workdone1);
-			free_cpumask_var(cm);
-			return;
-		}

kernel/rcu/tree.c +2 -0

+	for_each_online_cpu(cpu) {
+		struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);

Quoted 2 lines · Peter Zijlstra

Paul, why does this use stop_machine anyway? I seemed to remember you sending resched IPIs around.

Quoted 5 lines

The rcu_sched_qs() thing would set passed_quiesce, which you can then collect to gauge progress.

Shooting IPIs around is bad enough, but running a full blown stop_machine is really blunt and heavy.

Is there anything obviously amiss with the below? It does stop_one_cpu() in a loop instead of the multi cpu stop_machine and is therefore much friendlier (albeit still heavier than bare resched IPIs) since the CPUs do not have to go an sync up.

After all, all we're really interested in is that each CPUs has scheduled at least once, we do not care about the cross cpu syncup.

---
 include/linux/stop_machine.h |  7 ----
 kernel/rcu/tree.c            | 99 +++++---------------------------------------
 kernel/stop_machine.c        | 30 --------------
 3 files changed, 10 insertions(+), 126 deletions(-)

include/linux/stop_machine.h +0 -7

index d2abbdb8c6aa..f992da7ee492 100644
@@ -32,7 +32,6 @@ int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void *
 void stop_one_cpu_nowait(unsigned int cpu, cpu_stop_fn_t fn, void *arg,
 			 struct cpu_stop_work *work_buf);
 int stop_cpus(const struct cpumask *cpumask, cpu_stop_fn_t fn, void *arg);
-int try_stop_cpus(const struct cpumask *cpumask, cpu_stop_fn_t fn, void *arg);
 
 #else	/* CONFIG_SMP */
 

@@ -83,12 +82,6 @@ static inline int stop_cpus(const struct cpumask *cpumask,
 	return -ENOENT;
 }
 
-static inline int try_stop_cpus(const struct cpumask *cpumask,
-				cpu_stop_fn_t fn, void *arg)
-{
-	return stop_cpus(cpumask, fn, arg);
-}
-
 #endif	/* CONFIG_SMP */
 
 /*

kernel/rcu/tree.c +3 -16

index add042926a66..4a8cde155dce 100644
@@ -3257,7 +3257,7 @@ static int synchronize_sched_expedited_cpu_stop(void *data)
 {
 	/*
 	 * There must be a full memory barrier on each affected CPU
-	 * between the time that try_stop_cpus() is called and the
+	 * between the time that stop_one_cpu() is called and the
 	 * time that it returns.
 	 *
 	 * In the current initial implementation of cpu_stop, the

@@ -3291,25 +3291,12 @@ static int synchronize_sched_expedited_cpu_stop(void *data)
  * grace period.  We are then done, so we use atomic_cmpxchg() to
  * update sync_sched_expedited_done to match our snapshot -- but
  * only if someone else has not already advanced past our snapshot.
- *
- * On the other hand, if try_stop_cpus() fails, we check the value
- * of sync_sched_expedited_done.  If it has advanced past our
- * initial snapshot, then someone else must have forced a grace period
- * some time after we took our snapshot.  In this case, our work is
- * done for us, and we can simply return.  Otherwise, we try again,
- * but keep our initial snapshot for purposes of checking for someone
- * doing our work for us.
- *
- * If we fail too many times in a row, we fall back to synchronize_sched().
  */
 void synchronize_sched_expedited(void)
 {
-	cpumask_var_t cm;
-	bool cma = false;
-	int cpu;
-	long firstsnap, s, snap;
-	int trycount = 0;
 	struct rcu_state *rsp = &rcu_sched_state;
+	long s, snap;
+	int cpu;
 
 	/*
 	 * If we are in danger of counter wrap, just do synchronize_sched().

kernel/rcu/tree.c +0 -4

 	if (!try_get_online_cpus()) {
 		/* CPU hotplug operation in flight, fall back to normal GP. */
 		wait_rcu_gp(call_rcu_sched);

@@ -3341,82 +3327,17 @@ void synchronize_sched_expedited(void)
 	}
 	WARN_ON_ONCE(cpu_is_offline(raw_smp_processor_id()));
 
-	/* Offline CPUs, idle CPUs, and any CPU we run on are quiescent. */
-	cma = zalloc_cpumask_var(&cm, GFP_KERNEL);
-	if (cma) {
-		cpumask_copy(cm, cpu_online_mask);

kernel/rcu/tree.c +0 -8

-	/*
-	 * Each pass through the following loop attempts to force a
-	 * context switch on each CPU.
-	 */
-	while (try_stop_cpus(cma ? cm : cpu_online_mask,
-			     synchronize_sched_expedited_cpu_stop,
-			     NULL) == -EAGAIN) {
-		put_online_cpus();

kernel/rcu/tree.c +2 -2

+	for_each_online_cpu(cpu) {
+		struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
 
-		/* Recheck to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);

kernel/rcu/tree.c +0 -7

-		/*
-		 * Refetching sync_sched_expedited_started allows later
-		 * callers to piggyback on our grace period.  We retry
-		 * after they started, so our grace period works for them,
-		 * and they started after our first try, so their grace
-		 * period works for us.
-		 */

kernel/rcu/tree.c +1 -3

 	}
-	atomic_long_inc(&rsp->expedited_stoppedcpus);
 
-all_cpus_idle:
-	free_cpumask_var(cm);
+	atomic_long_inc(&rsp->expedited_stoppedcpus);
 
 	/*
 	 * Everyone up to our most recent fetch is covered by our grace

kernel/stop_machine.c +0 -30

index fd643d8c4b42..b1329a213503 100644
@@ -371,36 +371,6 @@ int stop_cpus(const struct cpumask *cpumask, cpu_stop_fn_t fn, void *arg)
 	return ret;
 }
 
-/**
- * try_stop_cpus - try to stop multiple cpus
- * @cpumask: cpus to stop
- * @fn: function to execute
- * @arg: argument to @fn
- *
- * Identical to stop_cpus() except that it fails with -EAGAIN if
- * someone else is already using the facility.
- *
- * CONTEXT:
- * Might sleep.
- *
- * RETURNS:
- * -EAGAIN if someone else is already stopping cpus, -ENOENT if
- * @fn(@arg) was not executed at all because all cpus in @cpumask were
- * offline; otherwise, 0 if all executions of @fn returned 0, any non
- * zero return value if any returned non zero.
- */
-int try_stop_cpus(const struct cpumask *cpumask, cpu_stop_fn_t fn, void *arg)
-{
-	int ret;
-
-	/* static works are used, process one request at a time */
-	if (!mutex_trylock(&stop_cpus_mutex))
-		return -EAGAIN;
-	ret = __stop_cpus(cpumask, fn, arg);
-	mutex_unlock(&stop_cpus_mutex);
-	return ret;
-}
-
 static int cpu_stop_should_run(unsigned int cpu)
 {
 	struct cpu_stopper *stopper = &per_cpu(cpu_stopper, cpu);

Good, you don't need this because you can check for dynticks later. You will need to check for offline CPUs.

Quoted 16 lines

kernel/rcu/tree.c +0 -16

-	/*
-	 * Each pass through the following loop attempts to force a
-	 * context switch on each CPU.
-	 */
-	while (try_stop_cpus(cma ? cm : cpu_online_mask,
-			     synchronize_sched_expedited_cpu_stop,
-			     NULL) == -EAGAIN) {
-		put_online_cpus();
-		atomic_long_inc(&rsp->expedited_tryfail);
-
-		/* Check to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);
-		if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
-			/* ensure test happens before caller kfree */
-			smp_mb__before_atomic(); /* ^^^ */
-			atomic_long_inc(&rsp->expedited_workdone1);

Review

Quoted 2 lines

(quoted diff) +0 -2

-			free_cpumask_var(cm);
-			return;

Here you lose batching. Yeah, I know that synchronize_sched_expedited() is -supposed- to be used sparingly, but it is not cool for the kernel to melt down just because some creative user found a way to heat up a code path. Need a mutex_trylock() with a counter and checking for others having already done the needed work.

And we still need to be able to drop back to synchronize_sched() (AKA wait_rcu_gp(call_rcu_sched) in this case) in case we have both a creative user and a long-running RCU-sched read-side critical section.

Quoted 5 lines

kernel/rcu/tree.c +2 -2

+	for_each_online_cpu(cpu) {
+		struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
 
-		/* Recheck to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);

kernel/rcu/tree.c void synchronize_sched_expedited(void) · line 3335

Quoted 10 lines

kernel/rcu/tree.c +3 -7

-		if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
-			/* ensure test happens before caller kfree */
-			smp_mb__before_atomic(); /* ^^^ */
-			atomic_long_inc(&rsp->expedited_workdone2);
-			free_cpumask_var(cm);
-			return;
-		}
+		/* Offline CPUs, idle CPUs, and any CPU we run on are quiescent. */
+		if (!(atomic_add_return(0, &rdtp->dynticks) & 0x1))
+			continue;

Let's see... This does work for idle CPUs and for nohz_full CPUs running in userspace.

It does not work for the current CPU, so the check needs an additional check against raw_smp_processor_id(), which is easy enough to add.

There always has been a race window involving CPU hotplug.

kernel/rcu/tree.c void synchronize_sched_expedited(void) · line 3337

Quoted 1 line

kernel/rcu/tree.c +1 -0

+		stop_one_cpu(cpu, synchronize_sched_expedited_cpu_stop, NULL);

My thought was to use smp_call_function_single(), and to have the function called recheck dyntick-idle state, avoiding doing a set_tsk_need_resched() if so.

This would result in a single pass through schedule() instead of stop_one_cpu()'s double context switch. It would likely also require some rework of rcu_note_context_switch(), which stop_one_cpu() avoids the need for.

Quoted 2 lines · Paul E. McKenney

Good, you don't need this because you can check for dynticks later. You will need to check for offline CPUs.

get_online_cpus()
for_each_online_cpus() {
...
}

is what the new code does.

Quoted 16 lines

Quoted 16 lines

kernel/rcu/tree.c +0 -16

-	/*
-	 * Each pass through the following loop attempts to force a
-	 * context switch on each CPU.
-	 */
-	while (try_stop_cpus(cma ? cm : cpu_online_mask,
-			     synchronize_sched_expedited_cpu_stop,
-			     NULL) == -EAGAIN) {
-		put_online_cpus();
-		atomic_long_inc(&rsp->expedited_tryfail);
-
-		/* Check to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);
-		if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
-			/* ensure test happens before caller kfree */
-			smp_mb__before_atomic(); /* ^^^ */
-			atomic_long_inc(&rsp->expedited_workdone1);

Quoted 8 lines

Review

Quoted 2 lines

(quoted diff) +0 -2

-			free_cpumask_var(cm);
-			return;

Here you lose batching. Yeah, I know that synchronize_sched_expedited() is -supposed- to be used sparingly, but it is not cool for the kernel to melt down just because some creative user found a way to heat up a code path. Need a mutex_trylock() with a counter and checking for others having already done the needed work.

I really think you're making that expedited nonsense far too accessible.

But it was exactly that trylock I was trying to get rid of.

Quoted 3 lines

And we still need to be able to drop back to synchronize_sched() (AKA wait_rcu_gp(call_rcu_sched) in this case) in case we have both a creative user and a long-running RCU-sched read-side critical section.

No, a long-running RCU-sched read-side is a bug and we should fix that, its called a preemption-latency, we don't like those.

Quoted 19 lines

Quoted 5 lines

kernel/rcu/tree.c +2 -2

+	for_each_online_cpu(cpu) {
+		struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
 
-		/* Recheck to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);

kernel/rcu/tree.c void synchronize_sched_expedited(void) · line 3335

Quoted 10 lines

kernel/rcu/tree.c +3 -7

-		if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
-			/* ensure test happens before caller kfree */
-			smp_mb__before_atomic(); /* ^^^ */
-			atomic_long_inc(&rsp->expedited_workdone2);
-			free_cpumask_var(cm);
-			return;
-		}
+		/* Offline CPUs, idle CPUs, and any CPU we run on are quiescent. */
+		if (!(atomic_add_return(0, &rdtp->dynticks) & 0x1))
+			continue;

Let's see... This does work for idle CPUs and for nohz_full CPUs running in userspace.

Quoted 2 lines

It does not work for the current CPU, so the check needs an additional check against raw_smp_processor_id(), which is easy enough to add.

Right, realized after I send it out, but it _should_ work for the current cpu too. Just pointless doing it.

Quoted 1 line

There always has been a race window involving CPU hotplug.

There is no hotplug race, the entire thing has get_online_cpus() held across it.

Quoted 5 lines

kernel/rcu/tree.c void synchronize_sched_expedited(void) · line 3337

Quoted 1 line

kernel/rcu/tree.c +1 -0

+		stop_one_cpu(cpu, synchronize_sched_expedited_cpu_stop, NULL);

My thought was to use smp_call_function_single(), and to have the function called recheck dyntick-idle state, avoiding doing a set_tsk_need_resched() if so.

set_tsk_need_resched() is buggy and should not be used.

Quoted 4 lines

This would result in a single pass through schedule() instead of stop_one_cpu()'s double context switch. It would likely also require some rework of rcu_note_context_switch(), which stop_one_cpu() avoids the need for.

_IF_ you're going to touch rcu_note_context_switch(), you might as well use a completion, set it for the number of CPUs that need a resched, spray resched-IPI and have rcu_note_context_switch() do a complete().

But I would really like to avoid adding code to rcu_note_context_switch(), because we run that on _every_ single context switch.

Quoted 4 lines · Peter Zijlstra

Quoted 2 lines · Paul E. McKenney

Good, you don't need this because you can check for dynticks later. You will need to check for offline CPUs.

Quoted 6 lines

get_online_cpus()
for_each_online_cpus() {
...
}

is what the new code does.

Ah, I missed that this was not deleted.

Quoted 25 lines

Quoted 16 lines

Quoted 16 lines

kernel/rcu/tree.c +0 -16

-	/*
-	 * Each pass through the following loop attempts to force a
-	 * context switch on each CPU.
-	 */
-	while (try_stop_cpus(cma ? cm : cpu_online_mask,
-			     synchronize_sched_expedited_cpu_stop,
-			     NULL) == -EAGAIN) {
-		put_online_cpus();
-		atomic_long_inc(&rsp->expedited_tryfail);
-
-		/* Check to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);
-		if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
-			/* ensure test happens before caller kfree */
-			smp_mb__before_atomic(); /* ^^^ */
-			atomic_long_inc(&rsp->expedited_workdone1);

Quoted 8 lines

Review

Quoted 2 lines

(quoted diff) +0 -2

-			free_cpumask_var(cm);
-			return;

Here you lose batching. Yeah, I know that synchronize_sched_expedited() is -supposed- to be used sparingly, but it is not cool for the kernel to melt down just because some creative user found a way to heat up a code path. Need a mutex_trylock() with a counter and checking for others having already done the needed work.

Quoted 1 line

I really think you're making that expedited nonsense far too accessible.

This has nothing to do with accessibility and everything to do with robustness. And with me not becoming the triage center for too many non-RCU bugs.

Quoted 1 line

But it was exactly that trylock I was trying to get rid of.

OK. Why, exactly?

Quoted 6 lines

Quoted 3 lines

And we still need to be able to drop back to synchronize_sched() (AKA wait_rcu_gp(call_rcu_sched) in this case) in case we have both a creative user and a long-running RCU-sched read-side critical section.

No, a long-running RCU-sched read-side is a bug and we should fix that, its called a preemption-latency, we don't like those.

Yes, we should fix them. No, they absolutely must not result in a meltdown of some unrelated portion of the kernel (like RCU), particularly if this situation occurs on some system running a production workload that doesn't happen to care about preemption latency.

Quoted 19 lines

Quoted 19 lines

Quoted 5 lines

kernel/rcu/tree.c +2 -2

+	for_each_online_cpu(cpu) {
+		struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
 
-		/* Recheck to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);

kernel/rcu/tree.c void synchronize_sched_expedited(void) · line 3335

Quoted 10 lines

kernel/rcu/tree.c +3 -7

-		if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
-			/* ensure test happens before caller kfree */
-			smp_mb__before_atomic(); /* ^^^ */
-			atomic_long_inc(&rsp->expedited_workdone2);
-			free_cpumask_var(cm);
-			return;
-		}
+		/* Offline CPUs, idle CPUs, and any CPU we run on are quiescent. */
+		if (!(atomic_add_return(0, &rdtp->dynticks) & 0x1))
+			continue;

Let's see... This does work for idle CPUs and for nohz_full CPUs running in userspace.

Quoted 5 lines

Quoted 2 lines

It does not work for the current CPU, so the check needs an additional check against raw_smp_processor_id(), which is easy enough to add.

Right, realized after I send it out, but it _should_ work for the current cpu too. Just pointless doing it.

OK, and easily fixed up in any case.

Quoted 4 lines

Quoted 1 line

There always has been a race window involving CPU hotplug.

There is no hotplug race, the entire thing has get_online_cpus() held across it.

Which I would like to get rid of, but not urgent.

Quoted 7 lines

Quoted 5 lines

kernel/rcu/tree.c void synchronize_sched_expedited(void) · line 3337

Quoted 1 line

kernel/rcu/tree.c +1 -0

+		stop_one_cpu(cpu, synchronize_sched_expedited_cpu_stop, NULL);

My thought was to use smp_call_function_single(), and to have the function called recheck dyntick-idle state, avoiding doing a set_tsk_need_resched() if so.

set_tsk_need_resched() is buggy and should not be used.

OK, what API is used for this purpose?

Quoted 5 lines

Quoted 4 lines

This would result in a single pass through schedule() instead of stop_one_cpu()'s double context switch. It would likely also require some rework of rcu_note_context_switch(), which stop_one_cpu() avoids the need for.

Quoted 7 lines

_IF_ you're going to touch rcu_note_context_switch(), you might as well use a completion, set it for the number of CPUs that need a resched, spray resched-IPI and have rcu_note_context_switch() do a complete().

But I would really like to avoid adding code to rcu_note_context_switch(), because we run that on _every_ single context switch.

I believe that I can rework the current code to get the effect without increased overhead, given that I have no intention of adding the complete(). Adding the complete -would- add overhead to that fastpath.

Thanx, Paul

Quoted 10 lines · Paul E. McKenney

Quoted 9 lines · Peter Zijlstra

Quoted 2 lines · Paul E. McKenney

Good, you don't need this because you can check for dynticks later. You will need to check for offline CPUs.

get_online_cpus()
for_each_online_cpus() {
...
}

Quoted 3 lines

Quoted 1 line

is what the new code does.

Ah, I missed that this was not deleted.

But get_online_cpus() will re-introduce a deadlock.

And here is an untested patch that applies the gist of your approach, the series of stop_one_cpu() calls, but without undoing the rest. I forged your Signed-off-by, please let me know if that doesn't work for you. There are a number of simplifications that can be made, but the basic approach gets a good testing first.

kernel/rcu/tree.c +3 -0

+		atomic_long_inc(&rsp->expedited_workdone1);
+		goto unlock;
+	}

kernel/rcu/tree.c void synchronize_sched_expedited(void) · line 3354

Quoted 4 lines · Peter Zijlstra

kernel/rcu/tree.c +4 -0

+	s = atomic_long_read(&rsp->expedited_done);
+	if (ULONG_CMP_GE((ulong)s, (ulong)snap)) {
+		/* ensure test happens before caller kfree */
+		smp_mb__before_atomic(); /* ^^^ */

FWIW isn't that guaranteed by the control dep?

Quoted 3 lines

kernel/rcu/tree.c +3 -0

+		atomic_long_inc(&rsp->expedited_workdone1);
+		goto unlock;
+	}

Quoted 5 lines · Paul E. McKenney

And here is an untested patch that applies the gist of your approach, the series of stop_one_cpu() calls, but without undoing the rest. I forged your Signed-off-by, please let me know if that doesn't work for you. There are a number of simplifications that can be made, but the basic approach gets a good testing first.

So I really do not get the point of the trylock. It doesn't make sense.

Why would you poll the mutex instead of just wait for it and then recheck if someone did the work while you were waiting for it?

What's wrong with the below?

---
 kernel/rcu/tree.c | 100 +++++++++++++++---------------------------------------
 kernel/rcu/tree.h |   1 +
 2 files changed, 29 insertions(+), 72 deletions(-)

kernel/rcu/tree.c +28 -72

index add042926a66..b39a5672a7ac 100644
@@ -103,6 +103,7 @@ struct rcu_state sname##_state = { \
 	.orphan_nxttail = &sname##_state.orphan_nxtlist, \
 	.orphan_donetail = &sname##_state.orphan_donelist, \
 	.barrier_mutex = __MUTEX_INITIALIZER(sname##_state.barrier_mutex), \
+	.expedited_mutex = __MUTEX_INITIALIZER(sname##_state.expedited_mutex), \
 	.name = RCU_STATE_NAME(sname), \
 	.abbr = sabbr, \
 }

@@ -3304,12 +3305,9 @@ static int synchronize_sched_expedited_cpu_stop(void *data)
  */
 void synchronize_sched_expedited(void)
 {
-	cpumask_var_t cm;
-	bool cma = false;
-	int cpu;
-	long firstsnap, s, snap;
-	int trycount = 0;
 	struct rcu_state *rsp = &rcu_sched_state;
+	long s, snap;
+	int cpu;
 
 	/*
 	 * If we are in danger of counter wrap, just do synchronize_sched().

@@ -3332,7 +3330,6 @@ void synchronize_sched_expedited(void)
 	 * full memory barrier.
 	 */
 	snap = atomic_long_inc_return(&rsp->expedited_start);
-	firstsnap = snap;
 	if (!try_get_online_cpus()) {
 		/* CPU hotplug operation in flight, fall back to normal GP. */
 		wait_rcu_gp(call_rcu_sched);

@@ -3341,83 +3338,40 @@ void synchronize_sched_expedited(void)
 	}
 	WARN_ON_ONCE(cpu_is_offline(raw_smp_processor_id()));
 
-	/* Offline CPUs, idle CPUs, and any CPU we run on are quiescent. */
-	cma = zalloc_cpumask_var(&cm, GFP_KERNEL);
-	if (cma) {
-		cpumask_copy(cm, cpu_online_mask);
-		cpumask_clear_cpu(raw_smp_processor_id(), cm);
-		for_each_cpu(cpu, cm) {
-			struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
-
-			if (!(atomic_add_return(0, &rdtp->dynticks) & 0x1))
-				cpumask_clear_cpu(cpu, cm);
-		}
-		if (cpumask_weight(cm) == 0)
-			goto all_cpus_idle;
-	}
-
 	/*
 	 * Each pass through the following loop attempts to force a
 	 * context switch on each CPU.
 	 */
-	while (try_stop_cpus(cma ? cm : cpu_online_mask,
-			     synchronize_sched_expedited_cpu_stop,
-			     NULL) == -EAGAIN) {
-		put_online_cpus();
-		atomic_long_inc(&rsp->expedited_tryfail);
+	mutex_lock(&rsp->expedited_mutex);
 
-		/* Check to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);
-		if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
-			/* ensure test happens before caller kfree */
-			smp_mb__before_atomic(); /* ^^^ */
-			atomic_long_inc(&rsp->expedited_workdone1);
-			free_cpumask_var(cm);
-			return;
-		}
+	/*
+	 * Check to see if someone else did our work for us, while we were
+	 * waiting for the mutex.
+	 */
+	s = atomic_long_read(&rsp->expedited_done);
+	if (ULONG_CMP_GE((ulong)s, (ulong)snap)) {
+		/* ensure test happens before caller kfree */
+		smp_mb__before_atomic(); /* ^^^ */
+		atomic_long_inc(&rsp->expedited_workdone1);
+		goto unlock;
+	}
 
-		/* No joy, try again later.  Or just synchronize_sched(). */
-		if (trycount++ < 10) {
-			udelay(trycount * num_online_cpus());
-		} else {
-			wait_rcu_gp(call_rcu_sched);
-			atomic_long_inc(&rsp->expedited_normal);
-			free_cpumask_var(cm);
-			return;
-		}
+	/* Stop each CPU that is online, non-idle, and not us. */
+	for_each_online_cpu(cpu) {
+		struct rcu_dynticks *rdtp = &per_cpu(rcu_dynticks, cpu);
 
-		/* Recheck to see if someone else did our work for us. */
-		s = atomic_long_read(&rsp->expedited_done);
-		if (ULONG_CMP_GE((ulong)s, (ulong)firstsnap)) {
-			/* ensure test happens before caller kfree */
-			smp_mb__before_atomic(); /* ^^^ */
-			atomic_long_inc(&rsp->expedited_workdone2);
-			free_cpumask_var(cm);
-			return;
-		}
+		/* Skip our CPU, */
+		if (raw_smp_processor_id() == cpu)
+			continue;
 
-		/*
-		 * Refetching sync_sched_expedited_started allows later
-		 * callers to piggyback on our grace period.  We retry
-		 * after they started, so our grace period works for them,
-		 * and they started after our first try, so their grace
-		 * period works for us.
-		 */
-		if (!try_get_online_cpus()) {
-			/* CPU hotplug operation in flight, use normal GP. */
-			wait_rcu_gp(call_rcu_sched);
-			atomic_long_inc(&rsp->expedited_normal);
-			free_cpumask_var(cm);
-			return;
-		}
-		snap = atomic_long_read(&rsp->expedited_start);
-		smp_mb(); /* ensure read is before try_stop_cpus(). */
+		/* and any idle CPUs. */
+		if (!(atomic_add_return(0, &rdtp->dynticks) & 0x1))
+			continue;
+
+		stop_one_cpu(cpu, synchronize_sched_expedited_cpu_stop, NULL);
 	}
 	atomic_long_inc(&rsp->expedited_stoppedcpus);
 
-all_cpus_idle:
-	free_cpumask_var(cm);
-
 	/*
 	 * Everyone up to our most recent fetch is covered by our grace
 	 * period.  Update the counter, but only if our work is still

@@ -3435,6 +3389,8 @@ void synchronize_sched_expedited(void)
 		}
 	} while (atomic_long_cmpxchg(&rsp->expedited_done, s, snap) != s);
 	atomic_long_inc(&rsp->expedited_done_exit);
+unlock:
+	mutex_unlock(&rsp->expedited_mutex);
 
 	put_online_cpus();
 }

kernel/rcu/tree.h +1 -0

index 4adb7ca0bf47..10348c081e8e 100644
@@ -483,6 +483,7 @@ struct rcu_state {
 						/*  _rcu_barrier(). */
 	/* End of fields guarded by barrier_mutex. */
 
+	struct mutex  expedited_mutex;		/* Serializes expediting. */
 	atomic_long_t expedited_start;		/* Starting ticket. */
 	atomic_long_t expedited_done;		/* Done ticket. */
 	atomic_long_t expedited_wrap;		/* # near-wrap incidents. */

Quoted 7 lines · Peter Zijlstra

Quoted 5 lines · Paul E. McKenney

And here is an untested patch that applies the gist of your approach, the series of stop_one_cpu() calls, but without undoing the rest. I forged your Signed-off-by, please let me know if that doesn't work for you. There are a number of simplifications that can be made, but the basic approach gets a good testing first.

Quoted 6 lines

So I really do not get the point of the trylock. It doesn't make sense.

Why would you poll the mutex instead of just wait for it and then recheck if someone did the work while you were waiting for it?

What's wrong with the below?

Various delays can cause tasks to queue on the mutex out of order.

This can cause a given task not only to have been delayed between sampling ->expedited_start and the mutex_lock(), but be further delayed because tasks granted the mutex earlier will wait on grace periods that the delayed task doesn't need to wait on. These extra waits are simply not consistent with the "expedited" in synchronize_sched_expedited().

Quoted 1 line

I really think you're making that expedited nonsense far too accessible.

This has nothing to do with accessibility and everything to do with robustness. And with me not becoming the triage center for too many non-RCU bugs.

Quoted 6 lines

Quoted 3 lines

And we still need to be able to drop back to synchronize_sched() (AKA wait_rcu_gp(call_rcu_sched) in this case) in case we have both a creative user and a long-running RCU-sched read-side critical section.

No, a long-running RCU-sched read-side is a bug and we should fix that, its called a preemption-latency, we don't like those.

Yes, we should fix them. No, they absolutely must not result in a meltdown of some unrelated portion of the kernel (like RCU), particularly if this situation occurs on some system running a production workload that doesn't happen to care about preemption latency.

Quoted 7 lines

Quoted 5 lines

kernel/rcu/tree.c void synchronize_sched_expedited(void) · line 3337

Quoted 1 line

kernel/rcu/tree.c +1 -0

+		stop_one_cpu(cpu, synchronize_sched_expedited_cpu_stop, NULL);

My thought was to use smp_call_function_single(), and to have the function called recheck dyntick-idle state, avoiding doing a set_tsk_need_resched() if so.

set_tsk_need_resched() is buggy and should not be used.

OK, what API is used for this purpose?

Quoted 6 lines · Paul E. McKenney

Quoted 2 lines

I really think you're making that expedited nonsense far too accessible.

This has nothing to do with accessibility and everything to do with robustness. And with me not becoming the triage center for too many non-RCU bugs.

But by making it so you're rewarding abuse instead of flagging it :-(

Quoted 4 lines · Peter Zijlstra

Quoted 3 lines · Paul E. McKenney

Quoted 2 lines

I really think you're making that expedited nonsense far too accessible.

Quoted 5 lines

Quoted 3 lines

This has nothing to do with accessibility and everything to do with robustness. And with me not becoming the triage center for too many non-RCU bugs.

But by making it so you're rewarding abuse instead of flagging it :-(

Btw., being a 'triage center' is the bane of APIs that are overly successful, so we should take that burden with pride! :-)

Lockdep (and the scheduler APIs as well) frequently got into such situations as well, and we mostly solved it by being more informative with debug splats.

I don't think a kernel API should (ever!) stay artificially silent, just for fear of flagging too many problems in other code.

Quoted 11 lines · Ingo Molnar

Quoted 8 lines · Peter Zijlstra

Quoted 6 lines · Paul E. McKenney

Quoted 2 lines

I really think you're making that expedited nonsense far too accessible.

This has nothing to do with accessibility and everything to do with robustness. And with me not becoming the triage center for too many non-RCU bugs.

Quoted 4 lines

Quoted 1 line

But by making it so you're rewarding abuse instead of flagging it :-(

Btw., being a 'triage center' is the bane of APIs that are overly successful, so we should take that burden with pride! :-)

I will gladly accept that compliment.

And the burden. But, lazy as I am, I intend to automate it. ;-)

Quoted 5 lines

Lockdep (and the scheduler APIs as well) frequently got into such situations as well, and we mostly solved it by being more informative with debug splats.

I don't think a kernel API should (ever!) stay artificially silent, just for fear of flagging too many problems in other code.

I agree, as attested by RCU CPU stall warnings, lockdep-RCU, sparse-based RCU checks, and the object-debug-based checks for double call_rcu(). That said, in all of these cases, including your example of lockdep, the diagnostic is a debug splat rather than a mutex-contention meltdown. And it is the mutex-contention meltdown that I will continue making synchronize_sched_expedited() avoid.