smp_call_function_many SMP race

I managed to forget all about this bug, probably because of how much it makes my brain hurt.

I tried to fix it by ordering the read and the write of ->cpumask and ->refs. In doing so I missed a critical case but Paul McKenney was able to spot my bug thankfully :) To ensure we arent viewing previous iterations the interrupt handler needs to read ->refs then ->cpumask then ->refs _again_.

---

Index: linux-2.6/kernel/smp.c
===================================================================

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 renamed from kernel/smp.c 2010-12-22 17:19:11.262835785 +1100 +5 -0

@@ -194,6 +194,31 @@ void generic_smp_call_function_interrupt
        list_for_each_entry_rcu(data, &call_function.queue, csd.list) {
                int refs;
 
+               /*
+                * Since we walk the list without any locks, we might
+                * see an entry that was completed, removed from the
+                * list and is in the process of being reused.
+                *

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 renamed from kernel/smp.c 2010-12-22 17:19:11.262835785 +1100 +1 -0

@@ -458,6 +483,14 @@ void smp_call_function_many(const struct
        data->csd.info = info;
        cpumask_and(data->cpumask, mask, cpu_online_mask);
        cpumask_clear_cpu(this_cpu, data->cpumask);
+

Quoted 2 lines · Anton Blanchard

I managed to forget all about this bug, probably because of how much it makes my brain hurt.

Agreed.

Quoted 21 lines

I tried to fix it by ordering the read and the write of ->cpumask and ->refs. In doing so I missed a critical case but Paul McKenney was able to spot my bug thankfully :) To ensure we arent viewing previous iterations the interrupt handler needs to read ->refs then ->cpumask then ->refs _again_.

---

Index: linux-2.6/kernel/smp.c
=====================================================================

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 renamed from kernel/smp.c 2010-12-22 17:19:11.262835785 +1100 +5 -0

@@ -194,6 +194,31 @@ void generic_smp_call_function_interrupt
        list_for_each_entry_rcu(data, &call_function.queue, csd.list) {
                int refs;
 
+               /*
+                * Since we walk the list without any locks, we might
+                * see an entry that was completed, removed from the
+                * list and is in the process of being reused.
+                *

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 void generic_smp_call_function_interrupt · line 211

Quoted 10 lines

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 renamed from kernel/smp.c 2010-12-22 17:19:11.262835785 +1100 +10 -0

+                * Just checking data->refs then data->cpumask is not good
+                * enough because we could see a non zero data->refs from a
+                * previous iteration. We need to check data->refs, then
+                * data->cpumask then data->refs again. Talk about
+                * complicated!
+                */
+
+               if (atomic_read(&data->refs) == 0)
+                       continue;
+

So here we might see the old ref

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 void generic_smp_call_function_interrupt · line 215

Quoted 4 lines

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 renamed from kernel/smp.c 2010-12-22 17:19:11.262835785 +1100 +4 -0

+               smp_rmb();
+
+               if (!cpumask_test_cpu(cpu, data->cpumask))
+                       continue;

Here we might see the new cpumask

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 void generic_smp_call_function_interrupt · line 220

Quoted 5 lines

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 renamed from kernel/smp.c 2010-12-22 17:19:11.262835785 +1100 +5 -0

+               smp_rmb();
+
+               if (atomic_read(&data->refs) == 0)
+                       continue;
+

But then still see a 0 ref, at which point we skip this entry and rely on the fact that arch_send_call_function_ipi_mask() will simply latch our IPI line and cause a back-to-back IPI such that we can process the data on the second go-round?

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 void generic_smp_call_function_interrupt · line 222

Quoted 2 lines

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 renamed from kernel/smp.c 2010-12-22 17:19:11.262835785 +1100 +0 -0

                if (!cpumask_test_and_clear_cpu(cpu, data->cpumask))
                        continue;

And finally, once we observe a valid ->refs, do we test the ->cpumask again so we cross with the store order (->cpumask first, then ->refs).

Quoted 5 lines

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 renamed from kernel/smp.c 2010-12-22 17:19:11.262835785 +1100 +1 -0

@@ -458,6 +483,14 @@ void smp_call_function_many(const struct
        data->csd.info = info;
        cpumask_and(data->cpumask, mask, cpu_online_mask);
        cpumask_clear_cpu(this_cpu, data->cpumask);
+

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 void smp_call_function_many(const struct · line 496

Quoted 10 lines

kernel/smp.c 2011-01-12 15:03:08.793324402 +1100 renamed from kernel/smp.c 2010-12-22 17:19:11.262835785 +1100 +7 -0

+       /*
+        * To ensure the interrupt handler gets an up to date view
+        * we order the cpumask and refs writes and order the
+        * read of them in the interrupt handler.
+        */
+       smp_wmb();
+
        atomic_set(&data->refs, cpumask_weight(data->cpumask));
 
        raw_spin_lock_irqsave(&call_function.lock, flags); 

Read side: Write side:

list_for_each_rcu()
!->refs, continue ->cpumask =
rmb wmb
!->cpumask, continue ->refs =
rmb wmb
!->refs, continue list_add_rcu()
mb
!->cpumask, continue

Wouldn't something like:

list_for_each_rcu()
!->cpumask, continue ->refs =
rmb wmb
!->refs, continue ->cpumask =
mb wmb
!->cpumask, continue list_add_rcu()

Suffice? There we can observe the old ->cpumask, new ->refs and new ->cpumask in crossed order, so we filter out the old, and cross the new, and have one rmb and conditional less.

Or am I totally missing something here,.. like said, this stuff hurts brains.

I noticed a failure where we hit the following WARN_ON in generic_smp_call_function_interrupt:

                if (!cpumask_test_and_clear_cpu(cpu, data->cpumask))
                        continue;

                data->csd.func(data->csd.info);

                refs = atomic_dec_return(&data->refs);
                WARN_ON(refs < 0);      <-------------------------

We atomically tested and cleared our bit in the cpumask, and yet the number of cpus left (ie refs) was 0. How can this be?

It turns out commit 54fdade1c3332391948ec43530c02c4794a38172 (generic-ipi: make struct call_function_data lockless) is at fault. It removes locking from smp_call_function_many and in doing so creates a rather complicated race.

Index: common/kernel/smp.c
===================================================================

kernel/smp.c +13 -0

@@ -193,6 +193,7 @@ void generic_smp_call_function_interrupt
 	 */
 	list_for_each_entry_rcu(data, &call_function.queue, csd.list) {
 		int refs;
+		void (*func) (void *info);
 
 		/*
 		 * Since we walk the list without any locks, we might

@@ -212,24 +213,32 @@ void generic_smp_call_function_interrupt
 		if (atomic_read(&data->refs) == 0)
 			continue;
 
+		func = data->csd.func;			/* for later warn */
 		data->csd.func(data->csd.info);
 
+		/*
+		 * If the cpu mask is not still set then it enabled interrupts,
+		 * we took another smp interrupt, and executed the function
+		 * twice on this cpu.  In theory that copy decremented refs.
+		 */
+		if (!cpumask_test_and_clear_cpu(cpu, data->cpumask)) {
+			WARN(1, "%pS enabled interrupts and double executed\n",
+			     func);
+			continue;
+		}
+
 		refs = atomic_dec_return(&data->refs);
 		WARN_ON(refs < 0);
 
 		if (refs)
 			continue;

Quoted 35 lines · Milton Miller

Index: common/kernel/smp.c
=====================================================================

kernel/smp.c +13 -0

@@ -193,6 +193,7 @@ void generic_smp_call_function_interrupt
 	 */
 	list_for_each_entry_rcu(data, &call_function.queue, csd.list) {
 		int refs;
+		void (*func) (void *info);
 
 		/*
 		 * Since we walk the list without any locks, we might

@@ -212,24 +213,32 @@ void generic_smp_call_function_interrupt
 		if (atomic_read(&data->refs) == 0)
 			continue;
 
+		func = data->csd.func;			/* for later warn */
 		data->csd.func(data->csd.info);
 
+		/*
+		 * If the cpu mask is not still set then it enabled interrupts,
+		 * we took another smp interrupt, and executed the function
+		 * twice on this cpu.  In theory that copy decremented refs.
+		 */
+		if (!cpumask_test_and_clear_cpu(cpu, data->cpumask)) {
+			WARN(1, "%pS enabled interrupts and double executed\n",
+			     func);
+			continue;
+		}
+
 		refs = atomic_dec_return(&data->refs);
 		WARN_ON(refs < 0);
 
 		if (refs)
 			continue;

kernel/smp.c void generic_smp_call_function_interrupt · line 244

Quoted 10 lines

kernel/smp.c +6 -0

 
+		WARN_ON(!cpumask_empty(data->cpumask));
+
+		raw_spin_lock(&call_function.lock);
+		list_del_rcu(&data->csd.list);
+		raw_spin_unlock(&call_function.lock);
+
 		csd_unlock(&data->csd);
 	}
 

So after this we have:

list_for_each_entry_rcu()
rbd
!->cpumask ->cpumask =
rmb wmb
!->refs ->refs =
->func() wmb
mb list_add_rcu()
->refs--
if (!->refs)

    list_del_rcu()

So even if we see it as an old-ref, when we see a valid cpumask, valid ref, we execute the function clear our cpumask bit and decrement the ref and delete the entry, even though it might not yet be added?

(old-ref)

				->cpumask =
  if (!->cpumask)
				->refs = 

if (!->refs)

->func()
->refs--
if (!->refs)

    list_del_rcu()
				list_add_rcu()

Then what happens?

Peter pointed out there was nothing preventing the list_del_rcu in smp_call_function_interrupt from running before the list_add_rcu in
smp_call_function_many. Fix this by not setting refs until we have put
the entry on the list. We can use the lock acquire and release instead of a wmb.

Wondering if a final sanity check makes sense. I've got a perma-spin bug where comment apparently happened. Another CPU's diddle the mask IPI may make this CPU do horrible things to itself as it's setting up to IPI others with that mask.

---
 kernel/smp.c |    3 +++
 1 file changed, 3 insertions(+)

Index: linux-2.6.38.git/kernel/smp.c
===================================================================

Quoted 14 lines · Mike Galbraith

Wondering if a final sanity check makes sense. I've got a perma-spin bug where comment apparently happened. Another CPU's diddle the mask IPI may make this CPU do horrible things to itself as it's setting up to IPI others with that mask.

---
 kernel/smp.c |    3 +++
 1 file changed, 3 insertions(+)

Index: linux-2.6.38.git/kernel/smp.c
===================================================================

kernel/smp.c void smp_call_function_many(const struct · line 495

Quoted 6 lines

kernel/smp.c +3 -0

@@ -490,6 +490,9 @@ void smp_call_function_many(const struct
 	cpumask_and(data->cpumask, mask, cpu_online_mask);
 	cpumask_clear_cpu(this_cpu, data->cpumask);
 
+	/* Did you pass me a mask that can be changed/emptied under me? */
+	BUG_ON(cpumask_empty(data->cpumask));
+

I was thinking of this as "the ipi cpumask was cleared", but I realize now you are saying the caller passed in a cpumask, but between the cpu_first/ cpu_next calls above and the cpumask_and another cpu cleared all the cpus?

I could see how that could happen on say a mask of cpus that might have a translation context, or cpus that need a push to complete an rcu window. Instead of the BUG_ON, we can handle the mask being cleared.

The arch code to send the IPI must handle an empty mask, as the other cpus are racing to clear their bit while its trying to send the IPI. In fact that expected race is the cause of the x86 warning in bz 23042
https://bugzilla.kernel.org/show_bug.cgi?id=23042 that Andrew pointed out.

How about this [untested] patch?

Mike Galbraith reported finding a lockup where aparently the passed in cpumask was cleared on other cpu(s) while this cpu was preparing its
smp_call_function_many block. Detect this race and unlock the call
data block. Note: arch_send_call_function_ipi_mask must still handle an empty mask because the element is globally visable before it is called. And obviously there are no guarantees to which cpus are notified if the mask is changed during the call.

Peter pointed out there was nothing preventing the list_del_rcu in smp_call_function_interrupt from running before the list_add_rcu in
smp_call_function_many. Fix this by not setting refs until we have put
the entry on the list. We can use the lock acquire and release instead of a wmb.

Reported-by Peter Zijlstra <[email protected]>

Signed-off-by Milton Miller <[email protected]>

Cc "Paul E. McKenney" <[email protected]>

---

I tried to force this race with a udelay before the lock & list_add and by mixing all 64 online cpus with just 3 random cpus in the mask, but was unsuccessful. Still, it seems to be a valid race, and the fix is a simple change to the current code.

Index: common/kernel/smp.c
===================================================================

kernel/smp.c +12 -8

@@ -491,15 +491,17 @@ void smp_call_function_many(const struct
 	cpumask_clear_cpu(this_cpu, data->cpumask);
 
 	/*
-	 * To ensure the interrupt handler gets an complete view
-	 * we order the cpumask and refs writes and order the read
-	 * of them in the interrupt handler.  In addition we may
-	 * only clear our own cpu bit from the mask.
+	 * We reuse the call function data without waiting for any grace
+	 * period after some other cpu removes it from the global queue.
+	 * This means a cpu might find our data block as it is writen.
+	 * The interrupt handler waits until it sees refs filled out
+	 * while its cpu mask bit is set; here we may only clear our
+	 * own cpu mask bit, and must wait to set refs until we are sure
+	 * previous writes are complete and we have obtained the lock to
+	 * add the element to the queue.  We use the acquire and release
+	 * of the lock as a wmb() -- acquire prevents write moving up and
+	 * release requires old writes are visible.
 	 */
-	smp_wmb();
-
-	atomic_set(&data->refs, cpumask_weight(data->cpumask));
-
 	raw_spin_lock_irqsave(&call_function.lock, flags);
 	/*
 	 * Place entry at the _HEAD_ of the list, so that any cpu still

@@ -509,6 +511,8 @@ void smp_call_function_many(const struct
 	list_add_rcu(&data->csd.list, &call_function.queue);
 	raw_spin_unlock_irqrestore(&call_function.lock, flags);
 
+	atomic_set(&data->refs, cpumask_weight(data->cpumask));
+
 	/*
 	 * Make the list addition visible before sending the ipi.
 	 * (IPIs must obey or appear to obey normal Linux cache

Quoted 9 lines · Milton Miller

Peter pointed out there was nothing preventing the list_del_rcu in smp_call_function_interrupt from running before the list_add_rcu in
smp_call_function_many. Fix this by not setting refs until we have put
the entry on the list. We can use the lock acquire and release instead of a wmb.

Reported-by Peter Zijlstra <[email protected]>

Signed-off-by Milton Miller <[email protected]>

Cc "Paul E. McKenney" <[email protected]>

Quoted 6 lines

---

I tried to force this race with a udelay before the lock & list_add and by mixing all 64 online cpus with just 3 random cpus in the mask, but was unsuccessful. Still, it seems to be a valid race, and the fix is a simple change to the current code.

Yes, I think this will fix it, I think simply putting that assignment under the lock is sufficient, because then the list removal will serialize again the list add. But placing it after the list add does also seem sufficient.

Acked-by Peter Zijlstra <[email protected]>

Quoted 22 lines · Peter Zijlstra

Quoted 9 lines · Milton Miller

Peter pointed out there was nothing preventing the list_del_rcu in smp_call_function_interrupt from running before the list_add_rcu in
smp_call_function_many. Fix this by not setting refs until we have put
the entry on the list. We can use the lock acquire and release instead of a wmb.

Reported-by Peter Zijlstra <[email protected]>

Signed-off-by Milton Miller <[email protected]>

Cc "Paul E. McKenney" <[email protected]>

Quoted 6 lines

---

I tried to force this race with a udelay before the lock & list_add and by mixing all 64 online cpus with just 3 random cpus in the mask, but was unsuccessful. Still, it seems to be a valid race, and the fix is a simple change to the current code.

Yes, I think this will fix it, I think simply putting that assignment under the lock is sufficient, because then the list removal will serialize again the list add. But placing it after the list add does also seem sufficient.

Quoted 2 lines

Acked-by Peter Zijlstra <[email protected]>

I was worried some architectures would allow a write before the spinlock to drop into the spinlock region,

in which case the data or function
pointer could be found stale with the cpu mask bit set.

The unlock
must flush all prior writes and

therefore the new function and data
will be seen before refs is set.

kernel/smp.c +0 -4

@@ -491,15 +491,17 @@ void smp_call_function_many(const struct
        cpumask_clear_cpu(this_cpu, data->cpumask);
 
        /*
-        * To ensure the interrupt handler gets an complete view
-        * we order the cpumask and refs writes and order the read
-        * of them in the interrupt handler.  In addition we may
-        * only clear our own cpu bit from the mask.

kernel/smp.c +2 -0

+       atomic_set(&data->refs, cpumask_weight(data->cpumask));
+
        /*
         * Make the list addition visible before sending the ipi.
         * (IPIs must obey or appear to obey normal Linux cache 

Quoted 8 lines · Milton Miller

kernel/smp.c +0 -4

@@ -491,15 +491,17 @@ void smp_call_function_many(const struct
        cpumask_clear_cpu(this_cpu, data->cpumask);
 
        /*
-        * To ensure the interrupt handler gets an complete view
-        * we order the cpumask and refs writes and order the read
-        * of them in the interrupt handler.  In addition we may
-        * only clear our own cpu bit from the mask.

kernel/smp.c void smp_call_function_many(const struct · line 503

Quoted 10 lines

kernel/smp.c +10 -0

+        * We reuse the call function data without waiting for any grace
+        * period after some other cpu removes it from the global queue.
+        * This means a cpu might find our data block as it is writen.
+        * The interrupt handler waits until it sees refs filled out
+        * while its cpu mask bit is set; here we may only clear our
+        * own cpu mask bit, and must wait to set refs until we are sure
+        * previous writes are complete and we have obtained the lock to
+        * add the element to the queue.  We use the acquire and release
+        * of the lock as a wmb() -- acquire prevents write moving up and
+        * release requires old writes are visible.

That's wrong:

->foo =
LOCK
UNLOCK
->bar =

can be re-ordered as:

LOCK
->bar =
->foo =
UNLOCK

Only a UNLOCK+LOCK sequence can be considered an MB.

However, I think the code is still OK, because list_add_rcu() implies a wmb(), so in that respect its an improvement since we fix a race and avoid an extra wmb. But the comment needs an update.

kernel/smp.c void smp_call_function_many(const struct · line 512

Quoted 11 lines

kernel/smp.c +0 -4

         */
-       smp_wmb();
-
-       atomic_set(&data->refs, cpumask_weight(data->cpumask));
-
        raw_spin_lock_irqsave(&call_function.lock, flags);
        /*
         * Place entry at the _HEAD_ of the list, so that any cpu still

@@ -509,6 +511,8 @@ void smp_call_function_many(const struct
        list_add_rcu(&data->csd.list, &call_function.queue);
        raw_spin_unlock_irqrestore(&call_function.lock, flags);

And this wants to grow a comment that it relies on the wmb implied by list_add_rcu()

Quoted 2 lines

kernel/smp.c +2 -0

+       atomic_set(&data->refs, cpumask_weight(data->cpumask));
+

That's wrong:

->foo =
LOCK
UNLOCK
->bar =

can be re-ordered as:

LOCK
->bar =
->foo =
UNLOCK

Quoted 7 lines · Peter Zijlstra

That's wrong:

 ->foo =
 LOCK
 UNLOCK
 ->bar =

Quoted 6 lines

can be re-ordered as:

 LOCK
 ->bar =
 ->foo =
 UNLOCK

Can it ? I though UNLOCK had a write barrier semantic ?

So yes, ->bar = can leak into the lock, as can ->foo =, but they can't be re-ordered vs. each other because the implied barrier will keep ->foo = in the same "domain" as the unlock itself.

Or do other archs do something really nasty here that don't provide this guarantee ?

Quoted 8 lines · Benjamin Herrenschmidt

Quoted 7 lines · Peter Zijlstra

That's wrong:

 ->foo =
 LOCK
 UNLOCK
 ->bar =

Quoted 8 lines

Quoted 6 lines

can be re-ordered as:

 LOCK
 ->bar =
 ->foo =
 UNLOCK

Can it ? I though UNLOCK had a write barrier semantic ?

The re-ordering of ->foo and UNLOCK that Peter claims is definitely possible, and the unlock is not guaranteed to be a write barrier. The unlock just guarantees "release" consistency, which means that no previous reads or writes will be migrated down from within the locked region, but it is very much a one-way barrier, so a subsequent write - or more commonly a read - could easily migrate up past the unlock.

(Same for lock, except the permeability is obviously the other way around - "acquire" consistency)

Quoted 6 lines

So yes, ->bar = can leak into the lock, as can ->foo =, but they can't be re-ordered vs. each other because the implied barrier will keep ->foo = in the same "domain" as the unlock itself.

Or do other archs do something really nasty here that don't provide this guarantee ?

I think we actually allow the accesses to ->bar and ->foo to be re-ordered wrt each other, exactly because they can *both* get re-ordered first into the locked region, and then after that they can get re-ordered wrt each other (because there is no other memory barrier).

So a "unlock+lock" is guaranteed to be equivalent to a full memory barrier (because an operation before the unlock cannot pass the unlock, and an access after the lock cannot percolate up before it). But the regular "lock+unlock" sequence is not, exactly because accesses outside of it are allowed to first leak in, and then not have ordering constraints within the locked region.

That said, we may have some confusion there, and I would *STRONGLY* suggest that architectures should have stronger lock consistency guarantees than the theoretical ones. Especially since x86 has such strong rules, and locking is a full memory barrier. Anybody with very weak ordering is likely to just hit more bugs.

And so while I'm not sure it's ever been documented, I do think it is likely a good idea to just make sure that "lock+unlock" is a full memory barrier, the same way "unlock+lock" is. I think it's practically true anyway on all architectures (with the possible exception of ia64, which I think actually implements real acquire/release semantics)

(Practically speaking, there really aren't many reasons to allow writes to be re-ordered wrt lock/unlock operations, and there is no reason to ever move reads later, only earlier. Writes are _not_ performance-sensitive the way reads are, so there is no real reason to really take advantage of the one-way permeability for them. It's reads that you really want to speculate and do early, not writes, and so allowing a read after a UNLOCK to percolate into the critical region is really the only relevant case from a performance perspective).

Linus

Documentation/memory-barriers.txt specifies this.

Quoted 2 lines · Paul E. McKenney

Documentation/memory-barriers.txt specifies this.

Good, so it really is documented, with both cases explicitly mentioned.

That said, I do think that if your memory ordering is much weaker than x86, you are going to see bugs that most testers don't see, and it simply might not be worth it.

Quoted 4 lines · Linus Torvalds

That said, I do think that if your memory ordering is much weaker than x86, you are going to see bugs that most testers don't see, and it simply might not be worth it.

IBM's CPUs do split the difference, with s390 having somewhat stronger ordering than x86, and with powerpc being rather weaker

Quite frankly, the POWER case is made worse by the fact that the synchronization primitives have this total confusion about "pipeline" synchronization due to historical implementation oddities etc. Talk about crazy. The whole "isync" vs "sync" vs "lwsync" thing is just an embarrassment. But this is, after all, a company that ran out of vowels in instruction naming, so I guess their misleading and confused naming for memory ordering is just par for the course.

Quoted 6 lines · Paul E. McKenney

Quoted 4 lines · Linus Torvalds

That said, I do think that if your memory ordering is much weaker than x86, you are going to see bugs that most testers don't see, and it simply might not be worth it.

Quoted 2 lines

IBM's CPUs do split the difference, with s390 having somewhat stronger ordering than x86, and with powerpc being rather weaker

I'm not talking about memory ordering as done by the cpu, but as done by the spinlock operations. They can be arbitrarily strong, even if the CPU architecture itself might be weakly ordered.

Quite frankly, the POWER case is made worse by the fact that the synchronization primitives have this total confusion about "pipeline" synchronization due to historical implementation oddities etc. Talk about crazy. The whole "isync" vs "sync" vs "lwsync" thing is just an embarrassment.

Quoted 2 lines · Paul E. McKenney

Documentation/memory-barriers.txt specifies this.

Good, so it really is documented, with both cases explicitly mentioned.

That said, I do think that if your memory ordering is much weaker than x86, you are going to see bugs that most testers don't see, and it simply might not be worth it.

Peter pointed out there was nothing preventing the list_del_rcu in smp_call_function_interrupt from running before the list_add_rcu in
smp_call_function_many. Fix this by not setting refs until we
have gotten the lock for the list. Take advantage of the wmb in list_add_rcu to save an explicit additional one.

Quoted 5 lines · Milton Miller

Peter pointed out there was nothing preventing the list_del_rcu in smp_call_function_interrupt from running before the list_add_rcu in
smp_call_function_many. Fix this by not setting refs until we
have gotten the lock for the list. Take advantage of the wmb in list_add_rcu to save an explicit additional one.

Finally getting a chance to give this full attention...

I don't know how to do this patch-by-patch, so I applied these three patches to mainline and looked at the result. This probably gets some comments that are irrelevant to these patches, but so it goes.

Starting with smp_call_function_many():

o The check for refs is redundant:

		/* some callers might race with other cpus changing the mask */
		if (unlikely(!refs)) {
			csd_unlock(&data->csd);
			return;
		}

	The memory barriers and atomic functions in
	generic_smp_call_function_interrupt() prevent the callback from
	being reused before the cpumask bits have all been cleared, right?

Furthermore, csd_lock() contains a full memory barrier that pairs with the full memory barrier in csd_unlock(), so if csd_lock() returns, we are guaranteed to see the effects of all accesses to the prior incarnation of this structure.

Yes, there might be another CPU that got a pointer to this callback just as another CPU removed it. That CPU will see the callback as having their bit of the CPU mask zero until we set it, and they will further see ->refs as being zero until we set it. And we don't set ->refs until after we re-insert the callback.

So I we can drop this "if" statement entirely.

o The smp_mb() below look extraneous. The comment in
generic_exec_single() agrees -- it says that the IPI code is required to impose ordering. Besides, there is a lock in arch_send_call_function_ipi_mask(), and in conjunction with the unlock below, this makes a full memory barrier. So I believe that we can drop the smp_mb() shown below. (But not the comment!!!)

raw_spin_unlock_irqrestore(&call_function.lock, flags);

/*
* Make the list addition visible before sending the ipi.
* (IPIs must obey or appear to obey normal Linux cache
* coherency rules -- see comment in generic_exec_single). */
smp_mb();

		/* Send a message to all CPUs in the map */
		arch_send_call_function_ipi_mask(data->cpumask);

Next up: generic_smp_call_function_interrupt()

o Shouldn't the smp_mb() at the top of the function be supplied
in arch-specific code for those architectures that require it?

o So, the check for the current CPU's bit in the mask...

o If the bit is clear, then we are looking at an callback
that this CPU already processed or that was not intended for this CPU in the first place.

Of course, this callback might be reused immediately after we do the check. In that case, there should be an IPI waiting for us shortly. If the IPI beat the callback to us, that seems to me to be a bug in the architecture rather than in this code.

o If the bit is set, then we need to process this callback.
IRQs are disabled, so we cannot race with ourselves -- our bit will remain set until we clear it. The list_add_rcu() in smp_call_function_many() in conjunction with the list_for_each_entry_rcu() in generic_smp_call_function_interrupt() guarantees that all of the field except for ->refs will be seen as initialized in the common case where we are looking at an callback that has just been enqueued.

In the uncommon case where we picked up the pointer in list_for_each_entry_rcu() just before the last CPU removed the callback and when someone else immediately recycled it, all bets are off. We must ensure that we see all initialization via some other means.

OK, so where is the memory barrier that pairs with the smp_rmb() between the ->cpumask and ->refs checks? It must be before the assignment to ->cpumask. One candidate is the smp_mb() in csd_lock(), but that does not make much sense. What we need to do is to ensure that if we see our bit in ->cpumask, that we also see the atomic decrement that previously zeroed ->refs.

But some third CPU did that atomic decrement, which brings transitivity into play, which leads me to believe that this smp_rmb() might need to be upgraded to a full smp_mb().

o After we verify that the ->refs field is non-zero, we pick
up the ->csd.func and ->csd.info fields, but with no intervening memory barrier. There needs to be at least an smp_rmb() following the test of the ->refs field. Since there is no transitivity required, smp_rmb() should do the trick.

If this seems unnecessary, please keep in mind that there is nothing stopping the compiler and the CPU from reordering the statements in smp_call_function_many() that initialize ->csd.func, ->csd.info, and ->cpumask.

	In contrast, given the suggested smp_rmb(), we are guaranteed
	of the identity of the callback from the time we test ->refs
	until the time someone calls csd_unlock(), which cannot precede
	the time that we atomically decrement ->refs.

o It seems silly to pick up the ->csd.func field twice. Why
not use the local variable?

o The cpumask_test_and_clear_cpu() and the atomic_dec_return()
are both atomic operations that return values, so they act as full memory barriers.

The cpumask_test_and_clear_cpu() needs to be atomic despite the identity guarantee because CPUs might be concurrently trying to clear bits in the same word.

Here is the corresponding (untested) patch.

Thoughts?

Thanx, Paul

------------------------------------------------------------------------

smp_call_function: additional memory-order tightening.

The csd_lock() and csd_unlock() interaction guarantees that the smp_call_function_many() function sees the results of interactions with prior incarnations of the callback, so the check is not needed. Instead, tighter memory ordering is required in the companion generic_smp_call_function_interrupt() function to ensure proper interaction with partially initialized callbacks.

Signed-off-by Paul E. McKenney <[email protected]>

kernel/smp.c +0 -0

index 064bb6e..4c8b005 100644

Quoted 18 lines · Paul E. McKenney

Quoted 5 lines · Milton Miller

Peter pointed out there was nothing preventing the list_del_rcu in smp_call_function_interrupt from running before the list_add_rcu in
smp_call_function_many. Fix this by not setting refs until we
have gotten the lock for the list. Take advantage of the wmb in list_add_rcu to save an explicit additional one.

Finally getting a chance to give this full attention...

I don't know how to do this patch-by-patch, so I applied these three patches to mainline and looked at the result. This probably gets some comments that are irrelevant to these patches, but so it goes.

Starting with smp_call_function_many():

o The check for refs is redundant:

Quoted 9 lines

		/* some callers might race with other cpus changing the mask */
		if (unlikely(!refs)) {
			csd_unlock(&data->csd);
			return;
		}

	The memory barriers and atomic functions in
	generic_smp_call_function_interrupt() prevent the callback from
	being reused before the cpumask bits have all been cleared, right?

The issue is not the cpumask in the csd, but the mask passed in from the caller. If other cpus clear the mask between the cpumask_first and and cpumask_next above (where we established there were at least two cpus not ourself) and the cpumask_copy, then this can happen. Both Mike Galbraith and Jan Beulich saw this in practice (Mikes case was mm_cpumask(mm)).

This was explained in the changelog for the second patch.

Quoted 12 lines

Furthermore, csd_lock() contains a full memory barrier that pairs with the full memory barrier in csd_unlock(), so if csd_lock() returns, we are guaranteed to see the effects of all accesses to the prior incarnation of this structure.

Yes, there might be another CPU that got a pointer to this callback just as another CPU removed it. That CPU will see the callback as having their bit of the CPU mask zero until we set it, and they will further see ->refs as being zero until we set it. And we don't set ->refs until after we re-insert the callback.

Quoted 1 line

So I we can drop this "if" statement entirely.

Disagree, see above.

Quoted 8 lines

o The smp_mb() below look extraneous. The comment in
generic_exec_single() agrees -- it says that the IPI code is required to impose ordering. Besides, there is a lock in arch_send_call_function_ipi_mask(), and in conjunction with the unlock below, this makes a full memory barrier. So I believe that we can drop the smp_mb() shown below. (But not the comment!!!)

Quoted 8 lines

raw_spin_unlock_irqrestore(&call_function.lock, flags);

/*
* Make the list addition visible before sending the ipi.
* (IPIs must obey or appear to obey normal Linux cache
* coherency rules -- see comment in generic_exec_single). */
smp_mb();

Well, this says the generic code guarantees mb before calling IPI ... this has been here since 2.6.30 and would need at least an arch audit so I vote to leave this here for now.

After we are confident in the locking, we can remove the internal bugs and warn on the cpumask and refs, leaving the one for mask clear and the ones for cpu online and calling context.

Quoted 5 lines

		/* Send a message to all CPUs in the map */
		arch_send_call_function_ipi_mask(data->cpumask);

Next up: generic_smp_call_function_interrupt()

Quoted 2 lines

o Shouldn't the smp_mb() at the top of the function be supplied
in arch-specific code for those architectures that require it?

Again, this would require an arch audit, I vote to leave for now. This says the generic code will guarantee that an IPI is received after the list is visiable with a mb on each side (as long as the arch makes IPI appear as ordered by smp_mb()).

Quoted 11 lines

o So, the check for the current CPU's bit in the mask...

o If the bit is clear, then we are looking at an callback
that this CPU already processed or that was not intended for this CPU in the first place.

Of course, this callback might be reused immediately after we do the check. In that case, there should be an IPI waiting for us shortly. If the IPI beat the callback to us, that seems to me to be a bug in the architecture rather than in this code.

agreed

Quoted 18 lines

o If the bit is set, then we need to process this callback.
IRQs are disabled, so we cannot race with ourselves -- our bit will remain set until we clear it. The list_add_rcu() in smp_call_function_many() in conjunction with the list_for_each_entry_rcu() in generic_smp_call_function_interrupt() guarantees that all of the field except for ->refs will be seen as initialized in the common case where we are looking at an callback that has just been enqueued.

In the uncommon case where we picked up the pointer in list_for_each_entry_rcu() just before the last CPU removed the callback and when someone else immediately recycled it, all bets are off. We must ensure that we see all initialization via some other means.

Quoted 7 lines

OK, so where is the memory barrier that pairs with the smp_rmb() between the ->cpumask and ->refs checks? It must be before the assignment to ->cpumask. One candidate is the smp_mb() in csd_lock(), but that does not make much sense. What we need to do is to ensure that if we see our bit in ->cpumask, that we also see the atomic decrement that previously zeroed ->refs.

We have a full mb in csd_unlock on the cpu that zeroed refs and a full mb in csd_lock on the cpu that sets mask and later refs.

We rely on the atomic returns to order the two atomics, and the atomic_dec_return to establish a single cpu as the last. After
that atomic is performed we do a full mb in unlock. At this
point all cpus must have visibility to all this prior processing. On the owning cpu we then do a full mb in lock.

How can any of the second party writes after the paired mb in lock be visible and not all of the prior third party writes?

How can any cpu see the old refs after the new mask is set? And if they could, how can we guarantee the ordering between the cpumask clearing and the unlock?

We rely on the statment that the cpumask memory will not change to an intermediate value has bits set that will be later cleared, that is we rely on the and of the incoming mask and online mask to occur before the store. We are broken if we copy online mask then and in the source mask..

The multiple non-atomic writes to data, func, and mask must be occur after the mb in lock and before the wmb in list_add_rcu. This wmb must force all processing except for the set of refs, and we require atomic_set to be atomic wrt atomic_dec_return.

Quoted 4 lines

But some third CPU did that atomic decrement, which brings transitivity into play, which leads me to believe that this smp_rmb() might need to be upgraded to a full smp_mb().

I'm not sure I understand the need for this upgrade. We are only performing reads on this cpu, how is smp_mb stronger than smp_rmb?

All the prior writes were ordered by atomic returns or a full mb.

Quoted 8 lines

o After we verify that the ->refs field is non-zero, we pick

	up the ->csd.func and ->csd.info fields, but with no intervening
	memory barrier.  There needs to be at least an smp_rmb()
	following the test of the ->refs field.  Since there is
	no transitivity required, smp_rmb() should do the trick.

Quoted 4 lines

If this seems unnecessary, please keep in mind that there is nothing stopping the compiler and the CPU from reordering the statements in smp_call_function_many() that initialize ->csd.func, ->csd.info, and ->cpumask.

Ok I agree, we need either wmb before setting cpumask or rmb before reading data & func after wmb is set.

Quoted 7 lines

	In contrast, given the suggested smp_rmb(), we are guaranteed
	of the identity of the callback from the time we test ->refs
	until the time someone calls csd_unlock(), which cannot precede
	the time that we atomically decrement ->refs.

o It seems silly to pick up the ->csd.func field twice. Why
not use the local variable?

I added the local variable for the warn and just left the compiler to
recognise the duplicate load. But yes, we could use the local to make
the call too. At the time I choose fewer loc changed.

Quoted 7 lines

o The cpumask_test_and_clear_cpu() and the atomic_dec_return()
are both atomic operations that return values, so they act as full memory barriers.

The cpumask_test_and_clear_cpu() needs to be atomic despite the identity guarantee because CPUs might be concurrently trying to clear bits in the same word.

Ok and in addition, since these are necessarly ordered then we can assert that the test_and_clear_cpu must execute before the decrement of refs, which is requried for total ordering to say that all cpus are done clearing their mask bit and decrementing refs before we do the csd_unlock, which allows the reuse.

Quoted 27 lines

Here is the corresponding (untested) patch.

Thoughts?

Thanx, Paul

------------------------------------------------------------------------

smp_call_function: additional memory-order tightening.

The csd_lock() and csd_unlock() interaction guarantees that the smp_call_function_many() function sees the results of interactions with prior incarnations of the callback, so the check is not needed. Instead, tighter memory ordering is required in the companion generic_smp_call_function_interrupt() function to ensure proper interaction with partially initialized callbacks.

Signed-off-by Paul E. McKenney <[email protected]>

kernel/smp.c +0 -0

index 064bb6e..4c8b005 100644
@@ -209,13 +209,19 @@ void generic_smp_call_function_interrupt(void)
 		if (!cpumask_test_cpu(cpu, data->cpumask))
 			continue;
 

kernel/smp.c void generic_smp_call_function_interrupt(void) · line 214

Quoted 4 lines

kernel/smp.c +3 -1

-		smp_rmb();
+		smp_mb(); /* If we see our bit set above, we need to see */
+			  /* all the processing associated with the prior */
+			  /* incarnation of this callback. */

Again, I want more justification. Why is mb required over rmb? We are ordering two reads. If we could see an old value before stored by another cpu then what does the mb in lock and unlock mean?

kernel/smp.c void generic_smp_call_function_interrupt(void) · line 221

Quoted 7 lines

kernel/smp.c +4 -0

 		if (atomic_read(&data->refs) == 0)
 			continue;
 
+		smp_rmb(); /* If we see non-zero ->refs, we need to see all */
+			   /* other initialization for this incarnation of */
+			   /* this callback. */
+

/* Need to read func and info after refs to see the new values, pairs with the wmb before setting refs. */

kernel/smp.c void generic_smp_call_function_interrupt(void) · line 223

Quoted 3 lines

kernel/smp.c +1 -1

 		func = data->csd.func;			/* for later warn */
-		data->csd.func(data->csd.info);
+		func(data->csd.info);

Ok, and can merge with the add of rmb.

Quoted 6 lines

kernel/smp.c +0 -0

 		/*
 		 * If the cpu mask is not still set then func enabled

@@ -492,12 +498,6 @@ void smp_call_function_many(const struct cpumask *mask,
 	cpumask_clear_cpu(this_cpu, data->cpumask);
 	refs = cpumask_weight(data->cpumask);
 

kernel/smp.c void smp_call_function_many(const struct cpumask *mask, · line 500

Quoted 6 lines

kernel/smp.c +0 -6

-	/* some callers might race with other cpus changing the mask */
-	if (unlikely(!refs)) {
-		csd_unlock(&data->csd);
-		return;
-	}
-

Again, this is needed, you were considering the csd mask but this is protecting against the cpumask argument is the source of the cpumask_copy changing.

Quoted 5 lines

kernel/smp.c +0 -0

 	/*
 	 * We reuse the call function data without waiting for any grace
 	 * period after some other cpu removes it from the global queue.

@@ -527,8 +527,9 @@ void smp_call_function_many(const struct cpumask *mask,
 	 * Make the list addition visible before sending the ipi.

kernel/smp.c void smp_call_function_many(const struct cpumask *mask, · line 531

Quoted 6 lines

kernel/smp.c +2 -1

 	 * (IPIs must obey or appear to obey normal Linux cache
 	 * coherency rules -- see comment in generic_exec_single).
+	 * The unlock above combined with the lock in the IPI
+	 * code covers this requirement.
 	 */
-	smp_mb();

again, this requires the arch audit.

kernel/smp.c void smp_call_function_many(const struct cpumask *mask, · line 534

Quoted 2 lines

kernel/smp.c +0 -0

 	/* Send a message to all CPUs in the map */
 	arch_send_call_function_ipi_mask(data->cpumask);

Quoted 2 lines · Milton Miller

Quoted 1 line · Paul E. McKenney

On Tue, Feb 01, 2011 at 01:12:18AM -0600, Milton Miller wrote:

Quoted 34 lines

Quoted 17 lines

o If the bit is set, then we need to process this callback.
IRQs are disabled, so we cannot race with ourselves -- our bit will remain set until we clear it. The list_add_rcu() in smp_call_function_many() in conjunction with the list_for_each_entry_rcu() in generic_smp_call_function_interrupt() guarantees that all of the field except for ->refs will be seen as initialized in the common case where we are looking at an callback that has just been enqueued.

In the uncommon case where we picked up the pointer in list_for_each_entry_rcu() just before the last CPU removed the callback and when someone else immediately recycled it, all bets are off. We must ensure that we see all initialization via some other means.

Quoted 7 lines

OK, so where is the memory barrier that pairs with the smp_rmb() between the ->cpumask and ->refs checks? It must be before the assignment to ->cpumask. One candidate is the smp_mb() in csd_lock(), but that does not make much sense. What we need to do is to ensure that if we see our bit in ->cpumask, that we also see the atomic decrement that previously zeroed ->refs.

We have a full mb in csd_unlock on the cpu that zeroed refs and a full mb in csd_lock on the cpu that sets mask and later refs.

We rely on the atomic returns to order the two atomics, and the atomic_dec_return to establish a single cpu as the last. After
that atomic is performed we do a full mb in unlock. At this
point all cpus must have visibility to all this prior processing. On the owning cpu we then do a full mb in lock.

Quoted 2 lines

How can any of the second party writes after the paired mb in lock be visible and not all of the prior third party writes?

Because smp_rmb() is not required to order prior writes against subsequent reads. The prior third-party writes are writes, right? When you want transitivity (observing n-th party writes that n-1-th party observed before n-1-th party's memory barrier), then you need a full memory barrier -- smp_mb().

Dimitri or Tony, let me know if you would like a revert patch for 75c1c91c to be added after patch 3.

Quoted 2 lines

Dimitri or Tony, let me know if you would like a revert patch for 75c1c91c to be added after patch 3.

It appears that we won't need this anymore, so sure - revert it.

Picking up this thread from the beginning of Feburary, I updated the comments in 3 and 4 based on Paul's review. I have inserted my proposed alternative to Paul's additional patch as patch 2, and tweaked the changelog on 1.

[PATCH 1/4 v3] call_function_many: fix list delete vs add race [PATCH 2/4 v3] call_function_many: add missing ordering [PATCH 3/4 v3] smp_call_function_many: handle concurrent clearing of mask [PATCH 4/4 v3] smp_call_function_interrupt: use typedef and %pf

Peter Z acked a prior version of patch 1, and Mike Galbraith has done some stress testing on the combinaton of 1,3,4, and Paul's patch.

The prior posting of this series is available here:
https://patchwork.kernel.org/patch/522021/
https://patchwork.kernel.org/patch/522031/
http://marc.info/?l=linux-kernel&m=129654439817236&w=2

And Paul's additional patch from review was here
https://patchwork.kernel.org/patch/525891/

Looking forward, I would suggest 1 and 2 are required for stable, 3 may be suitable as it fixes races that otherwise requires cpumask copies as in 75c1c91cb92806f960fcd6e53d2a0c21f343081c ([IA64] eliminate race condition in smp_flush_tlb_mm). By contrast 4 is just comments except for the %pS to %pf change.

Looking forward, I would suggest 1 and 2 are required for stable, 3 may be suitable as it fixes races that otherwise requires cpumask copies as in 75c1c91cb92806f960fcd6e53d2a0c21f343081c ([IA64] eliminate race condition in smp_flush_tlb_mm).  By contrast 4 is just comments except for the %pS to %pf change.

Quoted 6 lines · Milton Miller

Looking forward, I would suggest 1 and 2 are required for stable, 3 may be suitable as it fixes races that otherwise requires cpumask copies as in 75c1c91cb92806f960fcd6e53d2a0c21f343081c ([IA64] eliminate race condition in smp_flush_tlb_mm). By contrast 4 is just comments except for the %pS to %pf change.

Ok, who should I expect to take this series from? I think the last batch came through Andrew. The kernel/smp.c file seems to be one of those "unclear maintenance rules" one. The git statistics for the last 12 months seem to be

Andrew Morton <[email protected]> (commit_signer:4/9=44%) Peter Zijlstra <[email protected]> (commit_signer:2/9=22%) Milton Miller <[email protected]> (commit_signer:2/9=22%) Tejun Heo <[email protected]> (commit_signer:2/9=22%)
Ingo Molnar <[email protected]> (commit_signer:2/9=22%)

according to get_maintainer.pl. Should I just take these directly?

Picking up this thread from the beginning of Feburary, I updated the comments in 3 and 4 based on Paul's review. I have inserted my proposed alternative to Paul's additional patch as patch 2, and tweaked the changelog on 1.

[PATCH 1/4 v3] call_function_many: fix list delete vs add race [PATCH 2/4 v3] call_function_many: add missing ordering [PATCH 3/4 v3] smp_call_function_many: handle concurrent clearing of mask [PATCH 4/4 v3] smp_call_function_interrupt: use typedef and %pf

Peter Z acked a prior version of patch 1, and Mike Galbraith has done some stress testing on the combinaton of 1,3,4, and Paul's patch.

The prior posting of this series is available here:
https://patchwork.kernel.org/patch/522021/
https://patchwork.kernel.org/patch/522031/
http://marc.info/?l=linux-kernel&m=129654439817236&w=2

And Paul's additional patch from review was here
https://patchwork.kernel.org/patch/525891/

Looking forward, I would suggest 1 and 2 are required for stable, 3 may be suitable..

------------------------------------------------------------------------

smp_call_function: additional memory-order tightening.

The csd_lock() and csd_unlock() interaction guarantees that the smp_call_function_many() function sees the results of interactions with prior incarnations of the callback, so the check is not needed. Instead, tighter memory ordering is required in the companion generic_smp_call_function_interrupt() function to ensure proper interaction with partially initialized callbacks.

Signed-off-by Paul E. McKenney <[email protected]>

kernel/smp.c +8 -3

index 064bb6e..e091905 100644
@@ -182,7 +182,7 @@ void generic_smp_call_function_interrupt(void)
 
 	/*
 	 * Ensure entry is visible on call_function_queue after we have
-	 * entered the IPI. See comment in smp_call_function_many.
+	 * entered the IPI. See comment in smp_call_function_many
 	 * If we don't have this, then we may miss an entry on the list
 	 * and never get another IPI to process it.
 	 */

@@ -209,13 +209,18 @@ void generic_smp_call_function_interrupt(void)
 		if (!cpumask_test_cpu(cpu, data->cpumask))
 			continue;
 
-		smp_rmb();
+		smp_mb(); /* If we see our bit set above, we need to see */
+			  /* all the processing associated with the prior */
+			  /* incarnation of this callback. */
 
 		if (atomic_read(&data->refs) == 0)
 			continue;
 
+		smp_rmb(); /* We need to read ->refs before we read either */
+			   /* ->csd.func and ->csd.info. */
+
 		func = data->csd.func;			/* for later warn */
-		data->csd.func(data->csd.info);
+		func(data->csd.info);
 
 		/*
 		 * If the cpu mask is not still set then func enabled

On Tue, 2011-02-01 at 20:17 -0800, Paul E. McKenney wrote:

FWIW, my red headed stepchild (.32 xen cluster beast) with..
smp-smp_call_function_many-fix-SMP-race (6dc1989) smp-consolidate-writes-in-smp_call_function_interrupt (225c8e0) smp-smp_call_function_many-fix-list-delete-vs-add-race (V2) smp-smp_call_function_many-handle-concurrent-clearing-of-mask (V2) smp-generic_smp_call_function_interrupt-additional-memory-order-tightening (below)
..has not experienced any IPI problems lately, nor have I been able to trigger anything beating up my box running normal x64_64 kernels.

That's not saying much since my IPI woes were only the concurrent clearing variety, just letting you know that these patches have received (and are receiving) hefty thumpage.

Quoted 47 lines

------------------------------------------------------------------------

smp_call_function: additional memory-order tightening.

The csd_lock() and csd_unlock() interaction guarantees that the smp_call_function_many() function sees the results of interactions with prior incarnations of the callback, so the check is not needed. Instead, tighter memory ordering is required in the companion generic_smp_call_function_interrupt() function to ensure proper interaction with partially initialized callbacks.

Signed-off-by Paul E. McKenney <[email protected]>

kernel/smp.c +8 -3

index 064bb6e..e091905 100644
@@ -182,7 +182,7 @@ void generic_smp_call_function_interrupt(void)
 
 	/*
 	 * Ensure entry is visible on call_function_queue after we have
-	 * entered the IPI. See comment in smp_call_function_many.
+	 * entered the IPI. See comment in smp_call_function_many
 	 * If we don't have this, then we may miss an entry on the list
 	 * and never get another IPI to process it.
 	 */

@@ -209,13 +209,18 @@ void generic_smp_call_function_interrupt(void)
 		if (!cpumask_test_cpu(cpu, data->cpumask))
 			continue;
 
-		smp_rmb();
+		smp_mb(); /* If we see our bit set above, we need to see */
+			  /* all the processing associated with the prior */
+			  /* incarnation of this callback. */
 
 		if (atomic_read(&data->refs) == 0)
 			continue;
 
+		smp_rmb(); /* We need to read ->refs before we read either */
+			   /* ->csd.func and ->csd.info. */
+
 		func = data->csd.func;			/* for later warn */
-		data->csd.func(data->csd.info);
+		func(data->csd.info);
 
 		/*
 		 * If the cpu mask is not still set then func enabled

Quoted 11 lines · Mike Galbraith

On Tue, 2011-02-01 at 20:17 -0800, Paul E. McKenney wrote:

FWIW, my red headed stepchild (.32 xen cluster beast) with..
smp-smp_call_function_many-fix-SMP-race (6dc1989) smp-consolidate-writes-in-smp_call_function_interrupt (225c8e0) smp-smp_call_function_many-fix-list-delete-vs-add-race (V2) smp-smp_call_function_many-handle-concurrent-clearing-of-mask (V2) smp-generic_smp_call_function_interrupt-additional-memory-order-tightening (below)
..has not experienced any IPI problems lately, nor have I been able to trigger anything beating up my box running normal x64_64 kernels.

Quoted 3 lines

That's not saying much since my IPI woes were only the concurrent clearing variety, just letting you know that these patches have received (and are receiving) hefty thumpage.

Very good, I have added your Tested-by to my patch.

Thanx, Paul

Quoted 49 lines

Quoted 47 lines

------------------------------------------------------------------------

smp_call_function: additional memory-order tightening.

The csd_lock() and csd_unlock() interaction guarantees that the smp_call_function_many() function sees the results of interactions with prior incarnations of the callback, so the check is not needed. Instead, tighter memory ordering is required in the companion generic_smp_call_function_interrupt() function to ensure proper interaction with partially initialized callbacks.

Signed-off-by Paul E. McKenney <[email protected]>

kernel/smp.c +8 -3

index 064bb6e..e091905 100644
@@ -182,7 +182,7 @@ void generic_smp_call_function_interrupt(void)
 
 	/*
 	 * Ensure entry is visible on call_function_queue after we have
-	 * entered the IPI. See comment in smp_call_function_many.
+	 * entered the IPI. See comment in smp_call_function_many
 	 * If we don't have this, then we may miss an entry on the list
 	 * and never get another IPI to process it.
 	 */

@@ -209,13 +209,18 @@ void generic_smp_call_function_interrupt(void)
 		if (!cpumask_test_cpu(cpu, data->cpumask))
 			continue;
 
-		smp_rmb();
+		smp_mb(); /* If we see our bit set above, we need to see */
+			  /* all the processing associated with the prior */
+			  /* incarnation of this callback. */
 
 		if (atomic_read(&data->refs) == 0)
 			continue;
 
+		smp_rmb(); /* We need to read ->refs before we read either */
+			   /* ->csd.func and ->csd.info. */
+
 		func = data->csd.func;			/* for later warn */
-		data->csd.func(data->csd.info);
+		func(data->csd.info);
 
 		/*
 		 * If the cpu mask is not still set then func enabled

Quoted 4 lines · Paul E. McKenney

Starting with smp_call_function_many():

o The check for refs is redundant:

Quoted 9 lines

		/* some callers might race with other cpus changing the mask */
		if (unlikely(!refs)) {
			csd_unlock(&data->csd);
			return;
		}

	The memory barriers and atomic functions in
	generic_smp_call_function_interrupt() prevent the callback from
	being reused before the cpumask bits have all been cleared, right?

The issue is not the cpumask in the csd, but the mask passed in from the caller. If other cpus clear the mask between the cpumask_first and and cpumask_next above (where we established there were at least two cpus not ourself) and the cpumask_copy, then this can happen. Both Mike Galbraith and Jan Beulich saw this in practice (Mikes case was mm_cpumask(mm)).

Paul McKenney's review pointed out two problems with the barriers in the 2.6.38 update to the smp call function many code.

First, a barrier that would force the func and info members of data to be visible before their consumption in the interrupt handler was missing. This can be solved by adding a smp_wmb between setting the func and info members and setting setting the cpumask; this will pair with the existing and required smp_rmb ordering the cpumask read before the read of refs. This placement avoids the need a second smp_rmb in the interrupt handler which would be executed on each of the N cpus executing the call request. (I was thinking this barrier was present but was not).

Second, the previous write to refs (establishing the zero that we the interrupt handler was testing from all cpus) was performed by a third party cpu. This would invoke transitivity which, as a recient or concurrent addition to memory-barriers.txt now explicitly states, would require a full smp_mb().

However, we know the cpumask will only be set by one cpu (the data owner) and any preivous iteration of the mask would have cleared by the reading cpu. By redundantly writing refs to 0 on the owning cpu before the smp_wmb, the write to refs will follow the same path as the writes that set the cpumask, which in turn allows us to keep the barrier in the interrupt handler a smp_rmb instead of promoting it to a smp_mb (which will be be executed by N cpus for each of the possible M elements on the list).

I moved and expanded the comment about our (ab)use of the rcu list primitives for the concurrent walk earlier into this function. I considered moving the first two paragraphs to the queue list head and lock, but felt it would have been too disconected from the code.

Cc Paul McKinney <[email protected]>

Cc stable (2.6.32 and later)

Signed-off-by Milton Miller <[email protected]>

Paul, please review this alternative to your patch at either of

http://marc.info/?l=linux-kernel&m=129662029916241&w=2
https://patchwork.kernel.org/patch/525891/

In contrast to your patch, this proposal keeps the additional barriers in the (interrupt enabled) requester instead of the execution interrupt, where they would be executed by all N cpus in the system triggered concurrently for each of the N possible elements in the list.

Index: common/kernel/smp.c
===================================================================

kernel/smp.c +33 -14

@@ -483,23 +483,42 @@ void smp_call_function_many(const struct
 
 	data = &__get_cpu_var(cfd_data);
 	csd_lock(&data->csd);
-	BUG_ON(atomic_read(&data->refs) || !cpumask_empty(data->cpumask));
 
-	data->csd.func = func;
-	data->csd.info = info;
-	cpumask_and(data->cpumask, mask, cpu_online_mask);
-	cpumask_clear_cpu(this_cpu, data->cpumask);
+	/* This BUG_ON verifies our reuse assertions and can be removed */
+	BUG_ON(atomic_read(&data->refs) || !cpumask_empty(data->cpumask));
 
 	/*
+	 * The global call function queue list add and delete are protected
+	 * by a lock, but the list is traversed without any lock, relying
+	 * on the rcu list add and delete to allow safe concurrent traversal.
 	 * We reuse the call function data without waiting for any grace
 	 * period after some other cpu removes it from the global queue.
-	 * This means a cpu might find our data block as it is writen.
-	 * The interrupt handler waits until it sees refs filled out
-	 * while its cpu mask bit is set; here we may only clear our
-	 * own cpu mask bit, and must wait to set refs until we are sure
-	 * previous writes are complete and we have obtained the lock to
-	 * add the element to the queue.
+	 * This means a cpu might find our data block as it is being
+	 * filled out.
+	 *
+	 * We hold off the interrupt handler on the other cpu by
+	 * ordering our writes to the cpu mask vs our setting of the
+	 * refs counter.  We assert only the cpu owning the data block
+	 * will set a bit in cpumask, and each bit will only be cleared
+	 * by the subject cpu.  Each cpu must first find its bit is
+	 * set and then check that refs is set indicating the element is
+	 * ready to be processed, otherwise it must skip the entry.
+	 *
+	 * On the previous iteration refs was set to 0 by another cpu.
+	 * To avoid the use of transitivity, set the counter to 0 here
+	 * so the wmb will pair with the rmb in the interrupt handler.
 	 */
+	atomic_set(&data->refs, 0);	/* convert 3rd to 1st party write */
+
+	data->csd.func = func;
+	data->csd.info = info;
+
+	/* Ensure 0 refs is visible before mask.  Also orders func and info */
+	smp_wmb();
+
+	/* We rely on the "and" being processed before the store */
+	cpumask_and(data->cpumask, mask, cpu_online_mask);
+	cpumask_clear_cpu(this_cpu, data->cpumask);
 
 	raw_spin_lock_irqsave(&call_function.lock, flags);
 	/*

@@ -509,8 +528,9 @@ void smp_call_function_many(const struct
 	 */
 	list_add_rcu(&data->csd.list, &call_function.queue);
 	/*
-	 * We rely on the wmb() in list_add_rcu to order the writes
-	 * to func, data, and cpumask before this write to refs.
+	 * We rely on the wmb() in list_add_rcu to complete our writes
+	 * to the cpumask before this write to refs, which indicates
+	 * data is on the list and is ready to be processed.
 	 */
 	atomic_set(&data->refs, cpumask_weight(data->cpumask));
 	raw_spin_unlock_irqrestore(&call_function.lock, flags);
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Mike Galbraith reported finding a lockup ("perma-spin bug") where the cpumask passed to smp_call_function_many was cleared by other cpu(s) while a cpu was preparing its call_data block, resulting in no cpu to clear the last ref and unlock the block.

Quoted 1 line

Quoted 1 line · Milton Miller

Mike Galbraith reported finding a lockup ("perma-spin bug") where the cpumask passed to smp_call_function_many was cleared by other cpu(s) while a cpu was preparing its call_data block, resulting in no cpu to clear the last ref and unlock the block.

Having cpus clear their bit asynchronously could be useful on a mask of cpus that might have a translation context, or cpus that need a push to complete an rcu window.

Instead of adding a BUG_ON and requiring yet another cpumask copy, just detect the race and handle it.

Note: arch_send_call_function_ipi_mask must still handle an empty cpumask because the data block is globally visible before the that arch callback is made. And (obviously) there are no guarantees to which cpus are notified if the mask is changed during the call; only cpus that were online and had their mask bit set during the whole call are guaranteed to be called.

Reported-by Mike Galbraith <[email protected]>

Reported-by Jan Beulich <[email protected]>

Signed-off-by Milton Miller <[email protected]>

---
v3: try to clarify which mask in comment
v2: rediff for v2 of call_function_many: fix list delete vs add race

The arch code not expecting the race to empty the mask is the cause of https://bugzilla.kernel.org/show_bug.cgi?id=23042 that Andrew pointed out.

Index: common/kernel/smp.c
===================================================================

kernel/smp.c +10 -3

@@ -450,7 +450,7 @@ void smp_call_function_many(const struct
 {
 	struct call_function_data *data;
 	unsigned long flags;
-	int cpu, next_cpu, this_cpu = smp_processor_id();
+	int refs, cpu, next_cpu, this_cpu = smp_processor_id();
 
 	/*
 	 * Can deadlock when called with interrupts disabled.

@@ -461,7 +461,7 @@ void smp_call_function_many(const struct
 	WARN_ON_ONCE(cpu_online(this_cpu) && irqs_disabled()
 		     && !oops_in_progress && !early_boot_irqs_disabled);
 
-	/* So, what's a CPU they want? Ignoring this one. */
+	/* Try to fastpath.  So, what's a CPU they want? Ignoring this one. */
 	cpu = cpumask_first_and(mask, cpu_online_mask);
 	if (cpu == this_cpu)
 		cpu = cpumask_next_and(cpu, mask, cpu_online_mask);

@@ -519,6 +519,13 @@ void smp_call_function_many(const struct
 	/* We rely on the "and" being processed before the store */
 	cpumask_and(data->cpumask, mask, cpu_online_mask);
 	cpumask_clear_cpu(this_cpu, data->cpumask);
+	refs = cpumask_weight(data->cpumask);
+
+	/* Some callers race with other cpus changing the passed mask */
+	if (unlikely(!refs)) {
+		csd_unlock(&data->csd);
+		return;
+	}
 
 	raw_spin_lock_irqsave(&call_function.lock, flags);
 	/*

@@ -532,7 +539,7 @@ void smp_call_function_many(const struct
 	 * to the cpumask before this write to refs, which indicates
 	 * data is on the list and is ready to be processed.
 	 */
-	atomic_set(&data->refs, cpumask_weight(data->cpumask));
+	atomic_set(&data->refs, refs);
 	raw_spin_unlock_irqrestore(&call_function.lock, flags);
 
 	/*