Skip to contentSkip to conversation

lib/on-cpus: A couple of fixes

PATCH Superseded Andrew Jones 2 participants 7 messages Oct 23, 2024 – Oct 31, 2024

Subsystems (4)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

cover lib/on-cpus: A couple of fixes

While creating riscv SBI HSM tests a couple strange on-cpus behaviors were observed. Fix 'em.

Andrew Jones (2):
lib/on-cpus: Correct and simplify synchronization lib/on-cpus: Fix on_cpumask

 lib/cpumask.h | 14 ++++++++++++++
 lib/on-cpus.c | 53 ++++++++++++++++++---------------------------------
 2 files changed, 33 insertions(+), 34 deletions(-)
Signature · 1 line
2.47.0
#1 lore raw

PATCH 1/2 lib/on-cpus: Correct and simplify synchronization

get/put_on_cpu_info() were trying to provide per-cpu locking for the per-cpu on_cpu info, but they were flawed since they would always set the "lock" since they were treating test_and_set/clear as cmpxchg (which they're not). Just revert to a normal spinlock to correct it. Also simplify the break case for on_cpu_async() - we don't care if func is NULL, we only care that the cpu is idle. And, finally, add a missing barrier to on_cpu_async().

Fixes 018550041b38 ("arm/arm64: Remove spinlocks from on_cpu_async")
---
 lib/on-cpus.c | 36 +++++++++++-------------------------
 1 file changed, 11 insertions(+), 25 deletions(-)
lib/on-cpus.c +11 -25
index 892149338419..f6072117fa1b 100644
@@ -9,6 +9,7 @@
 #include <on-cpus.h>
 #include <asm/barrier.h>
 #include <asm/smp.h>
+#include <asm/spinlock.h>
 
 bool cpu0_calls_idle;
 
@@ -18,18 +19,7 @@ struct on_cpu_info {
 	cpumask_t waiters;
 };
 static struct on_cpu_info on_cpu_info[NR_CPUS];
-static cpumask_t on_cpu_info_lock;
-
-static bool get_on_cpu_info(int cpu)
-{
-	return !cpumask_test_and_set_cpu(cpu, &on_cpu_info_lock);
-}
-
-static void put_on_cpu_info(int cpu)
-{
-	int ret = cpumask_test_and_clear_cpu(cpu, &on_cpu_info_lock);
-	assert(ret);
-}
+static struct spinlock lock;
 
 static void __deadlock_check(int cpu, const cpumask_t *waiters, bool *found)
 {
@@ -81,18 +71,14 @@ void do_idle(void)
 	if (cpu == 0)
 		cpu0_calls_idle = true;
 
-	set_cpu_idle(cpu, true);
-	smp_send_event();
-
 	for (;;) {
+		set_cpu_idle(cpu, true);
+		smp_send_event();
+
 		while (cpu_idle(cpu))
 			smp_wait_for_event();
 		smp_rmb();
 		on_cpu_info[cpu].func(on_cpu_info[cpu].data);
-		on_cpu_info[cpu].func = NULL;
-		smp_wmb();
-		set_cpu_idle(cpu, true);
-		smp_send_event();
 	}
 }
 
@@ -110,17 +96,17 @@ void on_cpu_async(int cpu, void (*func)(void *data), void *data)
 
 	for (;;) {
 		cpu_wait(cpu);
-		if (get_on_cpu_info(cpu)) {
-			if ((volatile void *)on_cpu_info[cpu].func == NULL)
-				break;
-			put_on_cpu_info(cpu);
-		}
+		spin_lock(&lock);
+		if (cpu_idle(cpu))
+			break;
+		spin_unlock(&lock);
 	}
 
 	on_cpu_info[cpu].func = func;
 	on_cpu_info[cpu].data = data;
+	smp_wmb();
 	set_cpu_idle(cpu, false);
-	put_on_cpu_info(cpu);
+	spin_unlock(&lock);
 	smp_send_event();
 }
 
Signature · 1 line
2.47.0
#6 lore raw

PATCH 2/2 lib/on-cpus: Fix on_cpumask

In reply to Andrew Jones

on_cpumask should wait until the cpus in the mask, not including the calling cpu, are idle. Checking the weight against nr_cpus minus 1 only works when the mask is the same as the present mask.

Fixes d012cfd5d309 ("lib/on-cpus: Introduce on_cpumask and on_cpumask_async")
---
 lib/cpumask.h | 14 ++++++++++++++
 lib/on-cpus.c | 17 ++++++++---------
 2 files changed, 22 insertions(+), 9 deletions(-)
lib/cpumask.h +14 -0
index e1e92aacd1f1..37d360786573 100644
@@ -58,6 +58,20 @@ static inline void cpumask_clear(cpumask_t *mask)
 	memset(mask, 0, sizeof(*mask));
 }
 
+/* true if src1 is a subset of src2 */
+static inline bool cpumask_subset(const struct cpumask *src1, const struct cpumask *src2)
+{
+	unsigned long lastmask = BIT_MASK(nr_cpus) - 1;
+	int i;
+
+	for (i = 0; i < BIT_WORD(nr_cpus); ++i) {
+		if (cpumask_bits(src1)[i] & ~cpumask_bits(src2)[i])
+			return false;
+	}
+
+	return !lastmask || !((cpumask_bits(src1)[i] & ~cpumask_bits(src2)[i]) & lastmask);
+}
+
 static inline bool cpumask_empty(const cpumask_t *mask)
 {
 	unsigned long lastmask = BIT_MASK(nr_cpus) - 1;
lib/on-cpus.c +8 -9
index f6072117fa1b..7ce58be0e7e9 100644
@@ -126,24 +126,23 @@ void on_cpumask_async(const cpumask_t *mask, void (*func)(void *data), void *dat
 void on_cpumask(const cpumask_t *mask, void (*func)(void *data), void *data)
 {
 	int cpu, me = smp_processor_id();
+	cpumask_t tmp;
 
-	for_each_cpu(cpu, mask) {
-		if (cpu == me)
-			continue;
+	cpumask_copy(&tmp, mask);
+	cpumask_clear_cpu(me, &tmp);
+
+	for_each_cpu(cpu, &tmp)
 		on_cpu_async(cpu, func, data);
-	}
 	if (cpumask_test_cpu(me, mask))
 		func(data);
 
-	for_each_cpu(cpu, mask) {
-		if (cpu == me)
-			continue;
+	for_each_cpu(cpu, &tmp) {
 		cpumask_set_cpu(me, &on_cpu_info[cpu].waiters);
 		deadlock_check(me, cpu);
 	}
-	while (cpumask_weight(&cpu_idle_mask) < nr_cpus - 1)
+	while (!cpumask_subset(&tmp, &cpu_idle_mask))
 		smp_wait_for_event();
-	for_each_cpu(cpu, mask)
+	for_each_cpu(cpu, &tmp)
 		cpumask_clear_cpu(me, &on_cpu_info[cpu].waiters);
 }
 
Signature · 1 line
2.47.0
#2 lore raw

Re: [kvm-unit-tests PATCH 1/2] lib/on-cpus: Correct and simplify synchronization

In reply to Andrew Jones

Hi Drew,

I've been paging in all the on_cpu* machinery, and it occurred to me that we have a chance to simplify the code and to remove a duplicate interface by not exposing smp_boot_secondary() to the tests, as the on_cpu* functions serve the same purpose. With this change, we can remove the entry argument to smp_boot_secondary(), and the assembly for secondary_entry can be made simpler by eliminating the branch to the entry function.

Do you think that would be something worth pursuing? I can have a look at it.

There are exactly two places where smp_boot_secondary() is used: in arm/psci.c and arm/gic.c, and from a quick glance it looks to me like those can be replaced with one of the on_cpu* functions.

Quoted 4 lines · Andrew Jones

get/put_on_cpu_info() were trying to provide per-cpu locking for the per-cpu on_cpu info, but they were flawed since they would always set the "lock" since they were treating test_and_set/clear as cmpxchg (which they're not). Just revert to a normal spinlock

Would you mind expanding on that a bit more?

From my understanding of the code, on arm64, this is the call chain that I get for get_on_cpu_info(cpu):

  ->get_on_cpu_info(cpu):
    ->!cpumask_test_and_set(cpu, on_cpu_info_lock)
      ->!test_and_set_bit(cpu, on_cpu_info_lock->bits):
         return (old & mask) != 0;

'mask' always has the CPU bit set, which means that get_on_cpu_info() returns true if and only if 'old' has the bit clear. I think that prevents a thread getting the lock if it's already held, so from that point of view it does function as a per target cpu spinlock. Have I misunderstood something?

Regardless of the above, on_cpu_async() is used like this:

on_cpu_async()
wait_for_synchronization()

so it doesn't make much sense to optimize for performance for the case were multiple threads call on_cpu_async() concurrently, as they would need to have to wait for synchronization anyway.

So yes, I'm totally in favour for replacing the per-cpu spinlock with a global spinlock, even if the only reason is simplifying the code.

Quoted 2 lines

to correct it. Also simplify the break case for on_cpu_async() - we don't care if func is NULL, we only care that the cpu is idle.

That makes sense.

Quoted 1 line

And, finally, add a missing barrier to on_cpu_async().

Might be worth explaining in the commit message why it was missing. Just in case someone is looking at the code and isn't exactly sure why it's there.

Quoted 46 lines
Fixes 018550041b38 ("arm/arm64: Remove spinlocks from on_cpu_async")
---
 lib/on-cpus.c | 36 +++++++++++-------------------------
 1 file changed, 11 insertions(+), 25 deletions(-)
lib/on-cpus.c +2 -15
index 892149338419..f6072117fa1b 100644
@@ -9,6 +9,7 @@
 #include <on-cpus.h>
 #include <asm/barrier.h>
 #include <asm/smp.h>
+#include <asm/spinlock.h>
 
 bool cpu0_calls_idle;
 
@@ -18,18 +19,7 @@ struct on_cpu_info {
 	cpumask_t waiters;
 };
 static struct on_cpu_info on_cpu_info[NR_CPUS];
-static cpumask_t on_cpu_info_lock;
-
-static bool get_on_cpu_info(int cpu)
-{
-	return !cpumask_test_and_set_cpu(cpu, &on_cpu_info_lock);
-}
-
-static void put_on_cpu_info(int cpu)
-{
-	int ret = cpumask_test_and_clear_cpu(cpu, &on_cpu_info_lock);
-	assert(ret);
-}
+static struct spinlock lock;
 
 static void __deadlock_check(int cpu, const cpumask_t *waiters, bool *found)
 {
@@ -81,18 +71,14 @@ void do_idle(void)
 	if (cpu == 0)
 		cpu0_calls_idle = true;
 
-	set_cpu_idle(cpu, true);
-	smp_send_event();
-

lib/on-cpus.c void do_idle(void) · line 93

Quoted 10 lines
lib/on-cpus.c +3 -2
 	for (;;) {
+		set_cpu_idle(cpu, true);
+		smp_send_event();
+
 		while (cpu_idle(cpu))
 			smp_wait_for_event();
 		smp_rmb();
 		on_cpu_info[cpu].func(on_cpu_info[cpu].data);
-		on_cpu_info[cpu].func = NULL;
-		smp_wmb();

I think the barrier is still needed. The barrier orderered the now removed write func = NULL before the write set_cpu_idle(), but it also orderered whatever writes func(data) performed before set_cpu_idle(cpu, true). This matters for on_cpu(), where I think it's reasonable for the caller to expect to observe the writes made by 'func' after on_cpu() returns.

If you agree that this is the correct approach, I think it's worth adding a comment explaining it.

Quoted 13 lines
lib/on-cpus.c +0 -6
-		set_cpu_idle(cpu, true);
-		smp_send_event();
 	}
 }
 
@@ -110,17 +96,17 @@ void on_cpu_async(int cpu, void (*func)(void *data), void *data)
 
 	for (;;) {
 		cpu_wait(cpu);
-		if (get_on_cpu_info(cpu)) {
-			if ((volatile void *)on_cpu_info[cpu].func == NULL)
-				break;
-			put_on_cpu_info(cpu);

lib/on-cpus.c void on_cpu_async(int cpu, void (*func)(void *data), void *data) · line 107

Quoted 10 lines
lib/on-cpus.c +5 -1
-		}
+		spin_lock(&lock);
+		if (cpu_idle(cpu))
+			break;
+		spin_unlock(&lock);
 	}
 
 	on_cpu_info[cpu].func = func;
 	on_cpu_info[cpu].data = data;
+	smp_wmb();

Without this smp_wmb(), it is possible for the target CPU to read an outdated on_cpu_info[cpu].data. So adding it is the right thing to do, since it orders the writes to on_cpu_info before set_cpu_idle().

lib/on-cpus.c void on_cpu_async(int cpu, void (*func)(void *data), void *data) · line 110

Quoted 4 lines
lib/on-cpus.c +1 -1
 	set_cpu_idle(cpu, false);
-	put_on_cpu_info(cpu);
+	spin_unlock(&lock);
 	smp_send_event();

I think a DSB is necessary before all the smp_send_event() calls in this file. The DSB ensures that the stores to cpu_idle_mask will be observed by the thread that is waiting on the WFE, otherwise it is theoretically possible to get a deadlock (in practice this will never happen, because KVM will be generating the events that cause WFE to complete):

CPU0: on_cpu_async(): CPU1: do_idle():

load CPU1_idle = true
//do stuff
store CPU1_idle=false
SEV
1: WFE
load CPU1_idle=true // old value, allowed b 1b // deadlock

Also, it looks unusual to have smp_send_event() unpaired from set_cpu_idle(). Can't really point to anything being wrong about it though.

Thanks,
Alex

#3 lore raw

Re: [kvm-unit-tests PATCH 1/2] lib/on-cpus: Correct and simplify synchronization

Quoted 8 lines · Alexandru Elisei

Hi Drew,

I've been paging in all the on_cpu* machinery, and it occurred to me that we have a chance to simplify the code and to remove a duplicate interface by not exposing smp_boot_secondary() to the tests, as the on_cpu* functions serve the same purpose. With this change, we can remove the entry argument to smp_boot_secondary(), and the assembly for secondary_entry can be made simpler by eliminating the branch to the entry function.

You're right that smp_boot_secondary() doesn't appear to getting use, but a goal for the library code is to be useful and with defaults that will satisfy nearly all unit tests, but to never restrict a unit test to having to use it. Exposing calls like smp_boot_secondary() give unit tests the ability to eliminate as much library code as possible from their paths without having to duplicate the few lines needed to "boot" a secondary.

Quoted 24 lines

Do you think that would be something worth pursuing? I can have a look at it.

There are exactly two places where smp_boot_secondary() is used: in arm/psci.c and arm/gic.c, and from a quick glance it looks to me like those can be replaced with one of the on_cpu* functions.

Quoted 4 lines · Andrew Jones

get/put_on_cpu_info() were trying to provide per-cpu locking for the per-cpu on_cpu info, but they were flawed since they would always set the "lock" since they were treating test_and_set/clear as cmpxchg (which they're not). Just revert to a normal spinlock

Would you mind expanding on that a bit more?

From my understanding of the code, on arm64, this is the call chain that I get for get_on_cpu_info(cpu):

  ->get_on_cpu_info(cpu):
    ->!cpumask_test_and_set(cpu, on_cpu_info_lock)
      ->!test_and_set_bit(cpu, on_cpu_info_lock->bits):
         return (old & mask) != 0;
Quoted 4 lines

'mask' always has the CPU bit set, which means that get_on_cpu_info() returns true if and only if 'old' has the bit clear. I think that prevents a thread getting the lock if it's already held, so from that point of view it does function as a per target cpu spinlock. Have I misunderstood something?

No, you're right, and thanks for reminding me of the thought process I used when I wrote get/put_on_cpu_info() in the first place :-) While trying to simplify things, I just got fed up with staring at it and reasoning about it, so I threw my hands up and went back to a good ol' lock. Now that you've convinced me [again] that the test-and-set isn't flawed, we could keep it, but...

Quoted 9 lines

Regardless of the above, on_cpu_async() is used like this:

on_cpu_async()
wait_for_synchronization()

so it doesn't make much sense to optimize for performance for the case were multiple threads call on_cpu_async() concurrently, as they would need to have to wait for synchronization anyway.

...even though on_cpu_async() has a wait part, it only waits (outside the lock) for the target cpu to be idle. If all targets are idle already, and we have more than one "launcher" cpu, then we could launch tests on all the targets more-or-less simultaneously with percpu locks, but...

Quoted 3 lines

So yes, I'm totally in favour for replacing the per-cpu spinlock with a global spinlock, even if the only reason is simplifying the code.

...simplifying the code is probably the better choice since the critical section is so small that sharing a lock really shouldn't matter much and even some contention test which needs to run simultaneously on several cpus should use looping rather than rely on a simultaneous launch.

Quoted 10 lines
Quoted 3 lines

to correct it. Also simplify the break case for on_cpu_async() - we don't care if func is NULL, we only care that the cpu is idle.

That makes sense.

Quoted 1 line

And, finally, add a missing barrier to on_cpu_async().

Might be worth explaining in the commit message why it was missing. Just in case someone is looking at the code and isn't exactly sure why it's there.

Sure. I think the reason it's missing is because when 018550041b38 changed from spinlock to put_on_cpu_info(), the release was also moved below the clearing of idle. Prior to that, the spin_unlock() was acting as barrier. With the move of where the release was done a barrier should have been added.

Quoted 64 lines
Quoted 47 lines
Fixes 018550041b38 ("arm/arm64: Remove spinlocks from on_cpu_async")
---
 lib/on-cpus.c | 36 +++++++++++-------------------------
 1 file changed, 11 insertions(+), 25 deletions(-)
lib/on-cpus.c +2 -15
index 892149338419..f6072117fa1b 100644
@@ -9,6 +9,7 @@
 #include <on-cpus.h>
 #include <asm/barrier.h>
 #include <asm/smp.h>
+#include <asm/spinlock.h>
 
 bool cpu0_calls_idle;
 
@@ -18,18 +19,7 @@ struct on_cpu_info {
 	cpumask_t waiters;
 };
 static struct on_cpu_info on_cpu_info[NR_CPUS];
-static cpumask_t on_cpu_info_lock;
-
-static bool get_on_cpu_info(int cpu)
-{
-	return !cpumask_test_and_set_cpu(cpu, &on_cpu_info_lock);
-}
-
-static void put_on_cpu_info(int cpu)
-{
-	int ret = cpumask_test_and_clear_cpu(cpu, &on_cpu_info_lock);
-	assert(ret);
-}
+static struct spinlock lock;
 
 static void __deadlock_check(int cpu, const cpumask_t *waiters, bool *found)
 {
@@ -81,18 +71,14 @@ void do_idle(void)
 	if (cpu == 0)
 		cpu0_calls_idle = true;
 
-	set_cpu_idle(cpu, true);
-	smp_send_event();
-

lib/on-cpus.c void do_idle(void) · line 93

Quoted 10 lines
lib/on-cpus.c +3 -2
 	for (;;) {
+		set_cpu_idle(cpu, true);
+		smp_send_event();
+
 		while (cpu_idle(cpu))
 			smp_wait_for_event();
 		smp_rmb();
 		on_cpu_info[cpu].func(on_cpu_info[cpu].data);
-		on_cpu_info[cpu].func = NULL;
-		smp_wmb();

I think the barrier is still needed. The barrier orderered the now removed write func = NULL before the write set_cpu_idle(), but it also orderered whatever writes func(data) performed before set_cpu_idle(cpu, true). This matters for on_cpu(), where I think it's reasonable for the caller to expect to observe the writes made by 'func' after on_cpu() returns.

Quoted 2 lines

If you agree that this is the correct approach, I think it's worth adding a comment explaining it.

I think that's reasonable (along with adding smp_rmb()'s to the bottom of on_cpu() and on_cpumask()). So the idea is we have

 cpu1                                         cpu2
 ----                                         ----
 func() /* store something */                 /* wait for cpu1 to be idle */
 smp_wmb();                                   smp_rmb();
 set_cpu_idle(smp_processor_id(), true);      /* load what func() stored */
Quoted 42 lines
Quoted 14 lines
lib/on-cpus.c +0 -6
-		set_cpu_idle(cpu, true);
-		smp_send_event();
 	}
 }
 
@@ -110,17 +96,17 @@ void on_cpu_async(int cpu, void (*func)(void *data), void *data)
 
 	for (;;) {
 		cpu_wait(cpu);
-		if (get_on_cpu_info(cpu)) {
-			if ((volatile void *)on_cpu_info[cpu].func == NULL)
-				break;
-			put_on_cpu_info(cpu);

lib/on-cpus.c void on_cpu_async(int cpu, void (*func)(void *data), void *data) · line 107

Quoted 10 lines
lib/on-cpus.c +5 -1
-		}
+		spin_lock(&lock);
+		if (cpu_idle(cpu))
+			break;
+		spin_unlock(&lock);
 	}
 
 	on_cpu_info[cpu].func = func;
 	on_cpu_info[cpu].data = data;
+	smp_wmb();

Without this smp_wmb(), it is possible for the target CPU to read an outdated on_cpu_info[cpu].data. So adding it is the right thing to do, since it orders the writes to on_cpu_info before set_cpu_idle().

lib/on-cpus.c void on_cpu_async(int cpu, void (*func)(void *data), void *data) · line 110

Quoted 4 lines
lib/on-cpus.c +1 -1
 	set_cpu_idle(cpu, false);
-	put_on_cpu_info(cpu);
+	spin_unlock(&lock);
 	smp_send_event();

I think a DSB is necessary before all the smp_send_event() calls in this file. The DSB ensures that the stores to cpu_idle_mask will be observed by the thread that is waiting on the WFE, otherwise it is theoretically possible to get a deadlock (in practice this will never happen, because KVM will be generating the events that cause WFE to complete):

CPU0: on_cpu_async(): CPU1: do_idle():

Quoted 7 lines

load CPU1_idle = true
//do stuff
store CPU1_idle=false
SEV
1: WFE
load CPU1_idle=true // old value, allowed b 1b // deadlock

Good catch. Can you send a patch for that? The patch should be for the arm implementations of smp_send_event() (and smp_wait_for_event()?) in lib/arm/asm/smp.h.

Quoted 3 lines

Also, it looks unusual to have smp_send_event() unpaired from set_cpu_idle(). Can't really point to anything being wrong about it though.

You mean due to the spin_unlock() separating the set_cpu_idle() and smp_send_event()? We could put the spin_unlock() above the set_cpu_idle() (as it was in 018550041b38, which also removes the need for the wmb), but I think I like it the way it is now better for better readability. I also can't think of why it would matter for them to be unpaired.

Thanks,
drew

#4 lore raw

Re: [kvm-unit-tests PATCH 1/2] lib/on-cpus: Correct and simplify synchronization

Hi Drew,

Quoted 10 lines · Andrew Jones
Quoted 8 lines · Alexandru Elisei

Hi Drew,

I've been paging in all the on_cpu* machinery, and it occurred to me that we have a chance to simplify the code and to remove a duplicate interface by not exposing smp_boot_secondary() to the tests, as the on_cpu* functions serve the same purpose. With this change, we can remove the entry argument to smp_boot_secondary(), and the assembly for secondary_entry can be made simpler by eliminating the branch to the entry function.

Quoted 6 lines

You're right that smp_boot_secondary() doesn't appear to getting use, but a goal for the library code is to be useful and with defaults that will satisfy nearly all unit tests, but to never restrict a unit test to having to use it. Exposing calls like smp_boot_secondary() give unit tests the ability to eliminate as much library code as possible from their paths without having to duplicate the few lines needed to "boot" a secondary.

Yep, that makes sense.

Quoted 43 lines
Quoted 25 lines

Do you think that would be something worth pursuing? I can have a look at it.

There are exactly two places where smp_boot_secondary() is used: in arm/psci.c and arm/gic.c, and from a quick glance it looks to me like those can be replaced with one of the on_cpu* functions.

Quoted 4 lines · Andrew Jones

get/put_on_cpu_info() were trying to provide per-cpu locking for the per-cpu on_cpu info, but they were flawed since they would always set the "lock" since they were treating test_and_set/clear as cmpxchg (which they're not). Just revert to a normal spinlock

Would you mind expanding on that a bit more?

From my understanding of the code, on arm64, this is the call chain that I get for get_on_cpu_info(cpu):

  ->get_on_cpu_info(cpu):
    ->!cpumask_test_and_set(cpu, on_cpu_info_lock)
      ->!test_and_set_bit(cpu, on_cpu_info_lock->bits):
         return (old & mask) != 0;
Quoted 4 lines

'mask' always has the CPU bit set, which means that get_on_cpu_info() returns true if and only if 'old' has the bit clear. I think that prevents a thread getting the lock if it's already held, so from that point of view it does function as a per target cpu spinlock. Have I misunderstood something?

No, you're right, and thanks for reminding me of the thought process I used when I wrote get/put_on_cpu_info() in the first place :-) While trying to simplify things, I just got fed up with staring at it and reasoning about it, so I threw my hands up and went back to a good ol' lock. Now that you've convinced me [again] that the test-and-set isn't flawed, we could keep it, but...

Quoted 6 lines

Regardless of the above, on_cpu_async() is used like this:

on_cpu_async()
wait_for_synchronization()

Quoted 8 lines
Quoted 3 lines

so it doesn't make much sense to optimize for performance for the case were multiple threads call on_cpu_async() concurrently, as they would need to have to wait for synchronization anyway.

...even though on_cpu_async() has a wait part, it only waits (outside the lock) for the target cpu to be idle. If all targets are idle already, and we have more than one "launcher" cpu, then we could launch tests on all the targets more-or-less simultaneously with percpu locks, but...

Ahah, that's very interesting, hadn't though about it that way.

Another interesting thing here is that the glanularity for ATOMIC_TESTOP is 8 * 8 = 64 bits, because LDXR loads from an 8 byte address, which is then marked for exclusive access. I think that means that in the end, if you have less than 64 CPUs, then the per-cpu spinlock will end looking similar to a spinlock.

Quoted 9 lines
Quoted 4 lines

So yes, I'm totally in favour for replacing the per-cpu spinlock with a global spinlock, even if the only reason is simplifying the code.

...simplifying the code is probably the better choice since the critical section is so small that sharing a lock really shouldn't matter much and even some contention test which needs to run simultaneously on several cpus should use looping rather than rely on a simultaneous launch.

Yes, please use a spinlock here.

Quoted 82 lines
Quoted 11 lines
Quoted 4 lines

to correct it. Also simplify the break case for on_cpu_async() - we don't care if func is NULL, we only care that the cpu is idle.

That makes sense.

Quoted 1 line

And, finally, add a missing barrier to on_cpu_async().

Might be worth explaining in the commit message why it was missing. Just in case someone is looking at the code and isn't exactly sure why it's there.

Sure. I think the reason it's missing is because when 018550041b38 changed from spinlock to put_on_cpu_info(), the release was also moved below the clearing of idle. Prior to that, the spin_unlock() was acting as barrier. With the move of where the release was done a barrier should have been added.

Quoted 64 lines
Quoted 47 lines
Fixes 018550041b38 ("arm/arm64: Remove spinlocks from on_cpu_async")
---
 lib/on-cpus.c | 36 +++++++++++-------------------------
 1 file changed, 11 insertions(+), 25 deletions(-)
lib/on-cpus.c +2 -15
index 892149338419..f6072117fa1b 100644
@@ -9,6 +9,7 @@
 #include <on-cpus.h>
 #include <asm/barrier.h>
 #include <asm/smp.h>
+#include <asm/spinlock.h>
 
 bool cpu0_calls_idle;
 
@@ -18,18 +19,7 @@ struct on_cpu_info {
 	cpumask_t waiters;
 };
 static struct on_cpu_info on_cpu_info[NR_CPUS];
-static cpumask_t on_cpu_info_lock;
-
-static bool get_on_cpu_info(int cpu)
-{
-	return !cpumask_test_and_set_cpu(cpu, &on_cpu_info_lock);
-}
-
-static void put_on_cpu_info(int cpu)
-{
-	int ret = cpumask_test_and_clear_cpu(cpu, &on_cpu_info_lock);
-	assert(ret);
-}
+static struct spinlock lock;
 
 static void __deadlock_check(int cpu, const cpumask_t *waiters, bool *found)
 {
@@ -81,18 +71,14 @@ void do_idle(void)
 	if (cpu == 0)
 		cpu0_calls_idle = true;
 
-	set_cpu_idle(cpu, true);
-	smp_send_event();
-

lib/on-cpus.c void do_idle(void) · line 93

Quoted 10 lines
lib/on-cpus.c +3 -2
 	for (;;) {
+		set_cpu_idle(cpu, true);
+		smp_send_event();
+
 		while (cpu_idle(cpu))
 			smp_wait_for_event();
 		smp_rmb();
 		on_cpu_info[cpu].func(on_cpu_info[cpu].data);
-		on_cpu_info[cpu].func = NULL;
-		smp_wmb();

I think the barrier is still needed. The barrier orderered the now removed write func = NULL before the write set_cpu_idle(), but it also orderered whatever writes func(data) performed before set_cpu_idle(cpu, true). This matters for on_cpu(), where I think it's reasonable for the caller to expect to observe the writes made by 'func' after on_cpu() returns.

Quoted 5 lines
Quoted 2 lines

If you agree that this is the correct approach, I think it's worth adding a comment explaining it.

I think that's reasonable (along with adding smp_rmb()'s to the bottom of on_cpu() and on_cpumask()). So the idea is we have

I don't think adding smp_rmb() to on_cpu() and on_cpumask() is strictly necessary, because cpumask_set_cpu()->set_bit() already has a smp_mb().

Quoted 7 lines
 cpu1                                         cpu2
 ----                                         ----
 func() /* store something */                 /* wait for cpu1 to be idle */
 smp_wmb();                                   smp_rmb();
 set_cpu_idle(smp_processor_id(), true);      /* load what func() stored */

Just one small thing here, so it's even more precise what is being ordered:
the smp_rmb() on cpu2 orders the read from cpu_online_mask() before the load from what func() stored.

Quoted 50 lines
Quoted 42 lines
Quoted 14 lines
lib/on-cpus.c +0 -6
-		set_cpu_idle(cpu, true);
-		smp_send_event();
 	}
 }
 
@@ -110,17 +96,17 @@ void on_cpu_async(int cpu, void (*func)(void *data), void *data)
 
 	for (;;) {
 		cpu_wait(cpu);
-		if (get_on_cpu_info(cpu)) {
-			if ((volatile void *)on_cpu_info[cpu].func == NULL)
-				break;
-			put_on_cpu_info(cpu);

lib/on-cpus.c void on_cpu_async(int cpu, void (*func)(void *data), void *data) · line 107

Quoted 10 lines
lib/on-cpus.c +5 -1
-		}
+		spin_lock(&lock);
+		if (cpu_idle(cpu))
+			break;
+		spin_unlock(&lock);
 	}
 
 	on_cpu_info[cpu].func = func;
 	on_cpu_info[cpu].data = data;
+	smp_wmb();

Without this smp_wmb(), it is possible for the target CPU to read an outdated on_cpu_info[cpu].data. So adding it is the right thing to do, since it orders the writes to on_cpu_info before set_cpu_idle().

lib/on-cpus.c void on_cpu_async(int cpu, void (*func)(void *data), void *data) · line 110

Quoted 4 lines
lib/on-cpus.c +1 -1
 	set_cpu_idle(cpu, false);
-	put_on_cpu_info(cpu);
+	spin_unlock(&lock);
 	smp_send_event();

I think a DSB is necessary before all the smp_send_event() calls in this file. The DSB ensures that the stores to cpu_idle_mask will be observed by the thread that is waiting on the WFE, otherwise it is theoretically possible to get a deadlock (in practice this will never happen, because KVM will be generating the events that cause WFE to complete):

CPU0: on_cpu_async(): CPU1: do_idle():

Quoted 7 lines

load CPU1_idle = true
//do stuff
store CPU1_idle=false
SEV
1: WFE
load CPU1_idle=true // old value, allowed b 1b // deadlock

Quoted 3 lines

Good catch. Can you send a patch for that? The patch should be for the arm implementations of smp_send_event() (and smp_wait_for_event()?) in lib/arm/asm/smp.h.

Sure, I can do that. Should I wait until this series gets merged?

Also, I don't think smp_wait_for_event() needs a barrier - a wmb() before smp_send_event() will make sure that all stores have **completed** before smp_send_event() is executed, so on the waiting CPU all the stores will be visible.

Using a smp_wmp() (or smp_mb()) will not work, because smp_send_event() is not a memory operation, and the smp_* primitives won't order the memory accesses against it.

Quoted 10 lines
Quoted 4 lines

Also, it looks unusual to have smp_send_event() unpaired from set_cpu_idle(). Can't really point to anything being wrong about it though.

You mean due to the spin_unlock() separating the set_cpu_idle() and smp_send_event()? We could put the spin_unlock() above the set_cpu_idle() (as it was in 018550041b38, which also removes the need for the wmb), but I think I like it the way it is now better for better readability. I also can't think of why it would matter for them to be unpaired.

Then choose whatever looks best for you :)

Thanks,
Alex

#5 lore raw

Re: [kvm-unit-tests PATCH 1/2] lib/on-cpus: Correct and simplify synchronization

Quoted 193 lines · Alexandru Elisei

Hi Drew,

Quoted 10 lines · Andrew Jones
Quoted 8 lines · Alexandru Elisei

Hi Drew,

I've been paging in all the on_cpu* machinery, and it occurred to me that we have a chance to simplify the code and to remove a duplicate interface by not exposing smp_boot_secondary() to the tests, as the on_cpu* functions serve the same purpose. With this change, we can remove the entry argument to smp_boot_secondary(), and the assembly for secondary_entry can be made simpler by eliminating the branch to the entry function.

Quoted 6 lines

You're right that smp_boot_secondary() doesn't appear to getting use, but a goal for the library code is to be useful and with defaults that will satisfy nearly all unit tests, but to never restrict a unit test to having to use it. Exposing calls like smp_boot_secondary() give unit tests the ability to eliminate as much library code as possible from their paths without having to duplicate the few lines needed to "boot" a secondary.

Yep, that makes sense.

Quoted 43 lines
Quoted 25 lines

Do you think that would be something worth pursuing? I can have a look at it.

There are exactly two places where smp_boot_secondary() is used: in arm/psci.c and arm/gic.c, and from a quick glance it looks to me like those can be replaced with one of the on_cpu* functions.

Quoted 4 lines · Andrew Jones

get/put_on_cpu_info() were trying to provide per-cpu locking for the per-cpu on_cpu info, but they were flawed since they would always set the "lock" since they were treating test_and_set/clear as cmpxchg (which they're not). Just revert to a normal spinlock

Would you mind expanding on that a bit more?

From my understanding of the code, on arm64, this is the call chain that I get for get_on_cpu_info(cpu):

  ->get_on_cpu_info(cpu):
    ->!cpumask_test_and_set(cpu, on_cpu_info_lock)
      ->!test_and_set_bit(cpu, on_cpu_info_lock->bits):
         return (old & mask) != 0;
Quoted 4 lines

'mask' always has the CPU bit set, which means that get_on_cpu_info() returns true if and only if 'old' has the bit clear. I think that prevents a thread getting the lock if it's already held, so from that point of view it does function as a per target cpu spinlock. Have I misunderstood something?

No, you're right, and thanks for reminding me of the thought process I used when I wrote get/put_on_cpu_info() in the first place :-) While trying to simplify things, I just got fed up with staring at it and reasoning about it, so I threw my hands up and went back to a good ol' lock. Now that you've convinced me [again] that the test-and-set isn't flawed, we could keep it, but...

Quoted 6 lines

Regardless of the above, on_cpu_async() is used like this:

on_cpu_async()
wait_for_synchronization()

Quoted 8 lines
Quoted 3 lines

so it doesn't make much sense to optimize for performance for the case were multiple threads call on_cpu_async() concurrently, as they would need to have to wait for synchronization anyway.

...even though on_cpu_async() has a wait part, it only waits (outside the lock) for the target cpu to be idle. If all targets are idle already, and we have more than one "launcher" cpu, then we could launch tests on all the targets more-or-less simultaneously with percpu locks, but...

Ahah, that's very interesting, hadn't though about it that way.

Another interesting thing here is that the glanularity for ATOMIC_TESTOP is 8 * 8 = 64 bits, because LDXR loads from an 8 byte address, which is then marked for exclusive access. I think that means that in the end, if you have less than 64 CPUs, then the per-cpu spinlock will end looking similar to a spinlock.

Quoted 9 lines
Quoted 4 lines

So yes, I'm totally in favour for replacing the per-cpu spinlock with a global spinlock, even if the only reason is simplifying the code.

...simplifying the code is probably the better choice since the critical section is so small that sharing a lock really shouldn't matter much and even some contention test which needs to run simultaneously on several cpus should use looping rather than rely on a simultaneous launch.

Yes, please use a spinlock here.

Quoted 82 lines
Quoted 11 lines
Quoted 4 lines

to correct it. Also simplify the break case for on_cpu_async() - we don't care if func is NULL, we only care that the cpu is idle.

That makes sense.

Quoted 1 line

And, finally, add a missing barrier to on_cpu_async().

Might be worth explaining in the commit message why it was missing. Just in case someone is looking at the code and isn't exactly sure why it's there.

Sure. I think the reason it's missing is because when 018550041b38 changed from spinlock to put_on_cpu_info(), the release was also moved below the clearing of idle. Prior to that, the spin_unlock() was acting as barrier. With the move of where the release was done a barrier should have been added.

Quoted 64 lines
Quoted 47 lines
Fixes 018550041b38 ("arm/arm64: Remove spinlocks from on_cpu_async")
---
 lib/on-cpus.c | 36 +++++++++++-------------------------
 1 file changed, 11 insertions(+), 25 deletions(-)
lib/on-cpus.c +2 -15
index 892149338419..f6072117fa1b 100644
@@ -9,6 +9,7 @@
 #include <on-cpus.h>
 #include <asm/barrier.h>
 #include <asm/smp.h>
+#include <asm/spinlock.h>
 
 bool cpu0_calls_idle;
 
@@ -18,18 +19,7 @@ struct on_cpu_info {
 	cpumask_t waiters;
 };
 static struct on_cpu_info on_cpu_info[NR_CPUS];
-static cpumask_t on_cpu_info_lock;
-
-static bool get_on_cpu_info(int cpu)
-{
-	return !cpumask_test_and_set_cpu(cpu, &on_cpu_info_lock);
-}
-
-static void put_on_cpu_info(int cpu)
-{
-	int ret = cpumask_test_and_clear_cpu(cpu, &on_cpu_info_lock);
-	assert(ret);
-}
+static struct spinlock lock;
 
 static void __deadlock_check(int cpu, const cpumask_t *waiters, bool *found)
 {
@@ -81,18 +71,14 @@ void do_idle(void)
 	if (cpu == 0)
 		cpu0_calls_idle = true;
 
-	set_cpu_idle(cpu, true);
-	smp_send_event();
-

lib/on-cpus.c void do_idle(void) · line 93

Quoted 10 lines
lib/on-cpus.c +3 -2
 	for (;;) {
+		set_cpu_idle(cpu, true);
+		smp_send_event();
+
 		while (cpu_idle(cpu))
 			smp_wait_for_event();
 		smp_rmb();
 		on_cpu_info[cpu].func(on_cpu_info[cpu].data);
-		on_cpu_info[cpu].func = NULL;
-		smp_wmb();

I think the barrier is still needed. The barrier orderered the now removed write func = NULL before the write set_cpu_idle(), but it also orderered whatever writes func(data) performed before set_cpu_idle(cpu, true). This matters for on_cpu(), where I think it's reasonable for the caller to expect to observe the writes made by 'func' after on_cpu() returns.

Quoted 5 lines
Quoted 2 lines

If you agree that this is the correct approach, I think it's worth adding a comment explaining it.

I think that's reasonable (along with adding smp_rmb()'s to the bottom of on_cpu() and on_cpumask()). So the idea is we have

I don't think adding smp_rmb() to on_cpu() and on_cpumask() is strictly necessary, because cpumask_set_cpu()->set_bit() already has a smp_mb().

Quoted 7 lines
 cpu1                                         cpu2
 ----                                         ----
 func() /* store something */                 /* wait for cpu1 to be idle */
 smp_wmb();                                   smp_rmb();
 set_cpu_idle(smp_processor_id(), true);      /* load what func() stored */
Quoted 3 lines

Just one small thing here, so it's even more precise what is being ordered:
the smp_rmb() on cpu2 orders the read from cpu_online_mask() before the load from what func() stored.

Right (except s/cpu_online_mask/cpu_idle_mask/)

Quoted 51 lines
Quoted 51 lines
Quoted 50 lines
Quoted 15 lines
lib/on-cpus.c +0 -6
-		set_cpu_idle(cpu, true);
-		smp_send_event();
 	}
 }
 
@@ -110,17 +96,17 @@ void on_cpu_async(int cpu, void (*func)(void *data), void *data)
 
 	for (;;) {
 		cpu_wait(cpu);
-		if (get_on_cpu_info(cpu)) {
-			if ((volatile void *)on_cpu_info[cpu].func == NULL)
-				break;
-			put_on_cpu_info(cpu);

lib/on-cpus.c void on_cpu_async(int cpu, void (*func)(void *data), void *data) · line 107

Quoted 10 lines
lib/on-cpus.c +5 -1
-		}
+		spin_lock(&lock);
+		if (cpu_idle(cpu))
+			break;
+		spin_unlock(&lock);
 	}
 
 	on_cpu_info[cpu].func = func;
 	on_cpu_info[cpu].data = data;
+	smp_wmb();

Without this smp_wmb(), it is possible for the target CPU to read an outdated on_cpu_info[cpu].data. So adding it is the right thing to do, since it orders the writes to on_cpu_info before set_cpu_idle().

lib/on-cpus.c void on_cpu_async(int cpu, void (*func)(void *data), void *data) · line 110

Quoted 4 lines
lib/on-cpus.c +1 -1
 	set_cpu_idle(cpu, false);
-	put_on_cpu_info(cpu);
+	spin_unlock(&lock);
 	smp_send_event();

I think a DSB is necessary before all the smp_send_event() calls in this file. The DSB ensures that the stores to cpu_idle_mask will be observed by the thread that is waiting on the WFE, otherwise it is theoretically possible to get a deadlock (in practice this will never happen, because KVM will be generating the events that cause WFE to complete):

CPU0: on_cpu_async(): CPU1: do_idle():

load CPU1_idle = true
//do stuff
store CPU1_idle=false
SEV
1: WFE
load CPU1_idle=true // old value, allowed b 1b // deadlock

Quoted 5 lines
Quoted 3 lines

Good catch. Can you send a patch for that? The patch should be for the arm implementations of smp_send_event() (and smp_wait_for_event()?) in lib/arm/asm/smp.h.

Sure, I can do that. Should I wait until this series gets merged?

You can send now. I'll sort things out when merging.

Quoted 9 lines

Also, I don't think smp_wait_for_event() needs a barrier - a wmb() before smp_send_event() will make sure that all stores have **completed** before smp_send_event() is executed, so on the waiting CPU all the stores will be visible.

Using a smp_wmp() (or smp_mb()) will not work, because smp_send_event() is not a memory operation, and the smp_* primitives won't order the memory accesses against it.

Thanks. That's all good stuff for the commit message of the patch.

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

Also, it looks unusual to have smp_send_event() unpaired from set_cpu_idle(). Can't really point to anything being wrong about it though.

Quoted 8 lines
Quoted 5 lines

You mean due to the spin_unlock() separating the set_cpu_idle() and smp_send_event()? We could put the spin_unlock() above the set_cpu_idle() (as it was in 018550041b38, which also removes the need for the wmb), but I think I like it the way it is now better for better readability. I also can't think of why it would matter for them to be unpaired.

Then choose whatever looks best for you :)

Thanks. I'll send v2 shortly.

drew