Skip to contentSkip to conversation

Buggy IPI and MTRR code on low memory

PATCH In review Steven Rostedt 8 participants 57 messages Jan 28, 2009 – Jan 31, 2009 x86

lore
Share & tools
lore
#0 lore raw

While developing the RT git tree I came across this deadlock.

To avoid touching the memory allocator in smp_call_function_many I forced the stack use case, the path that would be taken if data fails to allocate.

Here's the current code in kernel/smp.c:

void smp_call_function_many(const struct cpumask *mask,

                            void (*func)(void *), void *info,
                            bool wait)
{
        struct call_function_data *data;
[...]
        data = kmalloc(sizeof(*data) + cpumask_size(), GFP_ATOMIC);
        if (unlikely(!data)) {
                /* Slow path. */
                for_each_online_cpu(cpu) {
                        if (cpu == smp_processor_id())
                                continue;
                        if (cpumask_test_cpu(cpu, mask))
                                smp_call_function_single(cpu, func, info, 
wait);
                }
                return;
        }

[...]

int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
int wait)

{
        struct call_single_data d;
[...]
                if (!wait) {
                        data = kmalloc(sizeof(*data), GFP_ATOMIC);
                        if (data)
                                data->flags = CSD_FLAG_ALLOC;
                }
                if (!data) {
                        data = &d;
                        data->flags = CSD_FLAG_WAIT;
                }

Note that if data failed to allocate, we force the wait state.

This immediately caused a deadlock with the mtrr code:

arch/x86/kernel/cpu/mtrr/main.c:

static void set_mtrr(unsigned int reg, unsigned long base,
unsigned long size, mtrr_type type)

{
        struct set_mtrr_data data;
[...]
        /*  Start the ball rolling on other CPUs  */
        if (smp_call_function(ipi_handler, &data, 0) != 0)
                panic("mtrr: timed out waiting for other CPUs\n");

        local_irq_save(flags);

        while(atomic_read(&data.count))
                cpu_relax();

        /* ok, reset count and toggle gate */
        atomic_set(&data.count, num_booting_cpus() - 1);
        smp_wmb();
        atomic_set(&data.gate,1);

[...]

static void ipi_handler(void *info)
/* [SUMMARY] Synchronisation handler. Executed by "other" CPUs.
[RETURNS] Nothing.
*/
{

#ifdef CONFIG_SMP
        struct set_mtrr_data *data = info;
        unsigned long flags;

        local_irq_save(flags);

        atomic_dec(&data->count);
        while(!atomic_read(&data->gate))
                cpu_relax();

The problem is that if we use the stack, then we must wait for the function to finish. But in the mtrr code, the called functions are waiting for the caller to do something after the smp_call_function. Thus we deadlock! This mtrr code seems to have been there for a while. At least longer than the git history.

To get around this, I did the following hack. Now this may be good enough to handle the case. I'm posting it for comments.

The patch creates another flag called CSD_FLAG_RELEASE. If we fail to alloc the data and the wait bit is not set, we still use the stack but we also set this flag instead of the wait flag. The receiving IPI will copy the data locally, and if this flag is set, it will clear it. The caller, after sending the IPI, will wait on this flag to be cleared.

The difference between this and the wait bit is that the release bit is just a way to let the callee tell the caller that it copied the data and is continuing. The data can be released with no worries. This prevents the deadlock because the caller can continue without waiting for the functions to be called.

I tested this patch by forcing the data to be null:

	data = NULL; // kmalloc(...);

Also, when forcing data to be NULL on the latest git tree, without applying the patch, I hit a deadlock in testing of the NMI watchdog. This means there may be other areas in the kernel that think smp_call_function, without the wait bit set, expects that function not to ever wait.

kernel/smp.c +31 -2
index 5cfa0e5..e85881b 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_RELEASE	= 0x04,
 };
 
 struct call_function_data {
@@ -168,21 +169,32 @@ void generic_smp_call_function_single_interrupt(void)
 
 		while (!list_empty(&list)) {
 			struct call_single_data *data;
+			struct call_single_data d;
 
 			data = list_entry(list.next, struct call_single_data,
 						list);
 			list_del(&data->list);
 
+			d = *data;
+			/* Make sure the data was read before released */
+			smp_mb();
+			data->flags &= ~CSD_FLAG_RELEASE;
+
 			/*
 			 * 'data' can be invalid after this call if
 			 * flags == 0 (when called through
 			 * generic_exec_single(), so save them away before
 			 * making the call.
 			 */
-			data_flags = data->flags;
+			data_flags = d.flags;
+			smp_rmb();
 
-			data->func(data->info);
+			d.func(d.info);
 
+			/*
+			 * data still exists if either of these
+			 * flags are true. We should not use d.
+			 */
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
@@ -230,6 +242,20 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 			data = kmalloc(sizeof(*data), GFP_ATOMIC);
 			if (data)
 				data->flags = CSD_FLAG_ALLOC;
+			else {
+				/*
+				 * There exist callers that call
+				 * functions that will wait on the caller
+				 * to do something after calling this.
+				 * This means we can not wait for the callee
+				 * function to finish.
+				 * Use the stack data but have the callee
+				 * copy it and tell us we can continue
+				 * before they call the function.
+				 */
+				data = &d;
+				data->flags = CSD_FLAG_RELEASE;
+			}
 		}
 		if (!data) {
 			data = &d;
@@ -239,6 +265,9 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		data->func = func;
 		data->info = info;
 		generic_exec_single(cpu, data);
+
+		while (data->flags & CSD_FLAG_RELEASE)
+			cpu_relax();
 	} else {
 		err = -ENXIO;	/* CPU not online */
 	}
#1 lore raw

Duh! I forgot to CC Jens.

-- Steve

Quoted 200 lines · Steven Rostedt

While developing the RT git tree I came across this deadlock.

To avoid touching the memory allocator in smp_call_function_many I forced the stack use case, the path that would be taken if data fails to allocate.

Here's the current code in kernel/smp.c:

void smp_call_function_many(const struct cpumask *mask,

                            void (*func)(void *), void *info,
                            bool wait)
{
        struct call_function_data *data;
[...]
        data = kmalloc(sizeof(*data) + cpumask_size(), GFP_ATOMIC);
        if (unlikely(!data)) {
                /* Slow path. */
                for_each_online_cpu(cpu) {
                        if (cpu == smp_processor_id())
                                continue;
                        if (cpumask_test_cpu(cpu, mask))
                                smp_call_function_single(cpu, func, info, 
wait);
                }
                return;
        }

[...]

int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
int wait)

{
        struct call_single_data d;
[...]
                if (!wait) {
                        data = kmalloc(sizeof(*data), GFP_ATOMIC);
                        if (data)
                                data->flags = CSD_FLAG_ALLOC;
                }
                if (!data) {
                        data = &d;
                        data->flags = CSD_FLAG_WAIT;
                }

Note that if data failed to allocate, we force the wait state.

This immediately caused a deadlock with the mtrr code:

arch/x86/kernel/cpu/mtrr/main.c:

static void set_mtrr(unsigned int reg, unsigned long base,
unsigned long size, mtrr_type type)

{
        struct set_mtrr_data data;
[...]
        /*  Start the ball rolling on other CPUs  */
        if (smp_call_function(ipi_handler, &data, 0) != 0)
                panic("mtrr: timed out waiting for other CPUs\n");

        local_irq_save(flags);

        while(atomic_read(&data.count))
                cpu_relax();

        /* ok, reset count and toggle gate */
        atomic_set(&data.count, num_booting_cpus() - 1);
        smp_wmb();
        atomic_set(&data.gate,1);

[...]

static void ipi_handler(void *info)
/* [SUMMARY] Synchronisation handler. Executed by "other" CPUs.
[RETURNS] Nothing.
*/
{

#ifdef CONFIG_SMP
        struct set_mtrr_data *data = info;
        unsigned long flags;

        local_irq_save(flags);

        atomic_dec(&data->count);
        while(!atomic_read(&data->gate))
                cpu_relax();

The problem is that if we use the stack, then we must wait for the function to finish. But in the mtrr code, the called functions are waiting for the caller to do something after the smp_call_function. Thus we deadlock! This mtrr code seems to have been there for a while. At least longer than the git history.

To get around this, I did the following hack. Now this may be good enough to handle the case. I'm posting it for comments.

The patch creates another flag called CSD_FLAG_RELEASE. If we fail to alloc the data and the wait bit is not set, we still use the stack but we also set this flag instead of the wait flag. The receiving IPI will copy the data locally, and if this flag is set, it will clear it. The caller, after sending the IPI, will wait on this flag to be cleared.

The difference between this and the wait bit is that the release bit is just a way to let the callee tell the caller that it copied the data and is continuing. The data can be released with no worries. This prevents the deadlock because the caller can continue without waiting for the functions to be called.

I tested this patch by forcing the data to be null:

	data = NULL; // kmalloc(...);

Also, when forcing data to be NULL on the latest git tree, without applying the patch, I hit a deadlock in testing of the NMI watchdog. This means there may be other areas in the kernel that think smp_call_function, without the wait bit set, expects that function not to ever wait.

kernel/smp.c +31 -2
index 5cfa0e5..e85881b 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_RELEASE	= 0x04,
 };
 
 struct call_function_data {
@@ -168,21 +169,32 @@ void generic_smp_call_function_single_interrupt(void)
 
 		while (!list_empty(&list)) {
 			struct call_single_data *data;
+			struct call_single_data d;
 
 			data = list_entry(list.next, struct call_single_data,
 						list);
 			list_del(&data->list);
 
+			d = *data;
+			/* Make sure the data was read before released */
+			smp_mb();
+			data->flags &= ~CSD_FLAG_RELEASE;
+
 			/*
 			 * 'data' can be invalid after this call if
 			 * flags == 0 (when called through
 			 * generic_exec_single(), so save them away before
 			 * making the call.
 			 */
-			data_flags = data->flags;
+			data_flags = d.flags;
+			smp_rmb();
 
-			data->func(data->info);
+			d.func(d.info);
 
+			/*
+			 * data still exists if either of these
+			 * flags are true. We should not use d.
+			 */
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
@@ -230,6 +242,20 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 			data = kmalloc(sizeof(*data), GFP_ATOMIC);
 			if (data)
 				data->flags = CSD_FLAG_ALLOC;
+			else {
+				/*
+				 * There exist callers that call
+				 * functions that will wait on the caller
+				 * to do something after calling this.
+				 * This means we can not wait for the callee
+				 * function to finish.
+				 * Use the stack data but have the callee
+				 * copy it and tell us we can continue
+				 * before they call the function.
+				 */
+				data = &d;
+				data->flags = CSD_FLAG_RELEASE;
+			}
 		}
 		if (!data) {
 			data = &d;
@@ -239,6 +265,9 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		data->func = func;
 		data->info = info;
 		generic_exec_single(cpu, data);
+
+		while (data->flags & CSD_FLAG_RELEASE)
+			cpu_relax();
 	} else {
 		err = -ENXIO;	/* CPU not online */
 	}
#2 lore raw
In reply to Steven Rostedt
Quoted 4 lines · Steven Rostedt

The problem is that if we use the stack, then we must wait for the function to finish. But in the mtrr code, the called functions are waiting for the caller to do something after the smp_call_function. Thus we deadlock!

You'd have to 'fix' the regular fallback paths to use your scheme as well.

Below is a fix for the mtrr code to not rely on this.

---
Subject: x86: fix potential deadlock in set_mtrr()
From: Peter Zijlstra <[email protected]>
Date: Wed Jan 28 17:17:32 CET 2009

smp_call_function() can fall-back to waiting on completion in case of low memory (GFP_ATOMIC). set_mtrr() relies on the async behaviour of !wait.

This would deadlock.

Fix this by providing per-cpu csd's and using __smp_call_function_single().

---
 arch/x86/kernel/cpu/mtrr/main.c |   34 ++++++++++++++++++++++++++++------
 1 file changed, 28 insertions(+), 6 deletions(-)
arch/x86/kernel/cpu/mtrr/main.c +28 -6
Index: linux-2.6/arch/x86/kernel/cpu/mtrr/main.c
===================================================================
@@ -38,6 +38,7 @@
 #include <linux/cpu.h>
 #include <linux/mutex.h>
 #include <linux/sort.h>
+#include <linux/smp.h>
 
 #include <asm/e820.h>
 #include <asm/mtrr.h>
@@ -130,12 +131,12 @@ struct set_mtrr_data {
 	mtrr_type	smp_type;
 };
 
+#ifdef CONFIG_SMP
 static void ipi_handler(void *info)
 /*  [SUMMARY] Synchronisation handler. Executed by "other" CPUs.
     [RETURNS] Nothing.
 */
 {
-#ifdef CONFIG_SMP
 	struct set_mtrr_data *data = info;
 	unsigned long flags;
 
@@ -158,9 +159,31 @@ static void ipi_handler(void *info)
 
 	atomic_dec(&data->count);
 	local_irq_restore(flags);
-#endif
 }
 
+DEFINE_PER_CPU(struct call_single_data, mtrr_csd);
+
+static void set_mtrr_smp(struct set_mtrr_data *data)
+{
+	int cpu;
+
+	for_each_online_cpu(cpu) {
+		struct call_single_data *csd = &per_cpu(mtrr_csd, cpu);
+
+		if (cpu == smp_processor_id())
+			continue;
+
+		csd->func = ipi_handler;
+		csd->info = data;
+		__smp_call_function_single(cpu, csd);
+	}
+}
+#else
+static void set_mtrr_smp(struct set_mtrr_data *data)
+{
+}
+#endif
+
 static inline int types_compatible(mtrr_type type1, mtrr_type type2) {
 	return type1 == MTRR_TYPE_UNCACHABLE ||
 	       type2 == MTRR_TYPE_UNCACHABLE ||
@@ -222,12 +245,11 @@ static void set_mtrr(unsigned int reg, u
 	smp_wmb();
 	atomic_set(&data.gate,0);
 
-	/*  Start the ball rolling on other CPUs  */
-	if (smp_call_function(ipi_handler, &data, 0) != 0)
-		panic("mtrr: timed out waiting for other CPUs\n");
-
 	local_irq_save(flags);
 
+	/*  Start the ball rolling on other CPUs  */
+	set_mtrr_smp(&data);
+
 	while(atomic_read(&data.count))
 		cpu_relax();
 
#3 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 4 lines · Steven Rostedt

The problem is that if we use the stack, then we must wait for the function to finish. But in the mtrr code, the called functions are waiting for the caller to do something after the smp_call_function. Thus we deadlock!

You'd have to 'fix' the regular fallback paths to use your scheme as well.

Not sure what you mean by that. I booted just fine with the patch, and forcing data to NULL. Although, I'm not saying that these should not be fixed.

-- Steve

#4 lore raw
Quoted 9 lines · Steven Rostedt
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Steven Rostedt

The problem is that if we use the stack, then we must wait for the function to finish. But in the mtrr code, the called functions are waiting for the caller to do something after the smp_call_function. Thus we deadlock!

Quoted 6 lines
Quoted 2 lines

You'd have to 'fix' the regular fallback paths to use your scheme as well.

Not sure what you mean by that. I booted just fine with the patch, and forcing data to NULL. Although, I'm not saying that these should not be fixed.

Yeah, I was being confused by:

Quoted 11 lines
(quoted diff) +7 -0
@@ -230,6 +242,20 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
                        data = kmalloc(sizeof(*data), GFP_ATOMIC);
                        if (data)
                                data->flags = CSD_FLAG_ALLOC;
+                       else {
+                               /*
+                                * There exist callers that call
+                                * functions that will wait on the caller
+                                * to do something after calling this.
+                                * This means we can not wait for the callee
+                                * function to finish.

Review int smp_call_function_single(int cpu, void (*func) (void *info), void *info, · line 261

Quoted 10 lines
(quoted diff) +7 -0
+                                * Use the stack data but have the callee
+                                * copy it and tell us we can continue
+                                * before they call the function.
+                                */
+                               data = &d;
+                               data->flags = CSD_FLAG_RELEASE;
+                       }
                }
                if (!data) {
                        data = &d;

that second !data test in there, thinking there was a fallback path still relying on CSD_FLAG_WAIT.

It appears all is well indeed.

#5 lore raw
In reply to Peter Zijlstra
Quoted 11 lines · Peter Zijlstra

---
Subject: x86: fix potential deadlock in set_mtrr()
From: Peter Zijlstra <[email protected]>
Date: Wed Jan 28 17:17:32 CET 2009

smp_call_function() can fall-back to waiting on completion in case of low memory (GFP_ATOMIC). set_mtrr() relies on the async behaviour of !wait.

This would deadlock.

Fix this by providing per-cpu csd's and using __smp_call_function_single().

I applied the patch but it still locked up in the testing NMI watchdog code. Not saying your patch is at fault, because we never made it to your code. This is probably not an issue, since if we have low memory at bootup, we have much bigger problems to deal with.

I'll have skip the NMI test and see if it locks up any place else.

-- Steve

#6 lore raw
Quoted 11 lines · Steven Rostedt
Quoted 10 lines · Peter Zijlstra

---
Subject: x86: fix potential deadlock in set_mtrr()
From: Peter Zijlstra <[email protected]>
Date: Wed Jan 28 17:17:32 CET 2009

smp_call_function() can fall-back to waiting on completion in case of low memory (GFP_ATOMIC). set_mtrr() relies on the async behaviour of !wait.

This would deadlock.

Quoted 8 lines
Quoted 1 line

Fix this by providing per-cpu csd's and using __smp_call_function_single().

I applied the patch but it still locked up in the testing NMI watchdog code. Not saying your patch is at fault, because we never made it to your code. This is probably not an issue, since if we have low memory at bootup, we have much bigger problems to deal with.

I'll have skip the NMI test and see if it locks up any place else.

Right, the NMI code does exactly the same, in that case your patch might well be the best way forward.

#7 lore raw
Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Steven Rostedt
Quoted 11 lines · Peter Zijlstra

---
Subject: x86: fix potential deadlock in set_mtrr()
From: Peter Zijlstra <[email protected]>
Date: Wed Jan 28 17:17:32 CET 2009

smp_call_function() can fall-back to waiting on completion in case of low memory (GFP_ATOMIC). set_mtrr() relies on the async behaviour of !wait.

This would deadlock.

Fix this by providing per-cpu csd's and using __smp_call_function_single().

I applied the patch but it still locked up in the testing NMI watchdog code. Not saying your patch is at fault, because we never made it to your code. This is probably not an issue, since if we have low memory at bootup, we have much bigger problems to deal with.

Quoted 4 lines
Quoted 1 line

I'll have skip the NMI test and see if it locks up any place else.

Right, the NMI code does exactly the same, in that case your patch might well be the best way forward.

Is there any reason to force the user to have to deal with a wait? We can add this code to handle the failed alloc case, and I can even make it a bit better to only do the copy *d = data; when the RELEASE flag is set.

-- Steve

#8 lore raw
In reply to Steven Rostedt
Quoted 2 lines · On Wed, 28 Jan 2009 12:24:48 -0500 (EST) Steven Rostedt <[email protected]>…
Quoted 1 line

---

I'll have skip the NMI test and see if it locks up any place else.

if you get an NMI during MTRR changing you are more or less screwed. Really. (the cpu is uncachable etc)

the MTRR code should disable NMIs as much as possible.

and for sure in -RT, the MTRR change section should not be preemptable at all.

Signature · 3 lines
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org
#9 lore raw
Quoted 8 lines · Arjan van de Ven
Quoted 2 lines · On Wed, 28 Jan 2009 12:24:48 -0500 (EST) Steven Rostedt <[email protected]>…
Quoted 1 line

---

I'll have skip the NMI test and see if it locks up any place else.

if you get an NMI during MTRR changing you are more or less screwed. Really. (the cpu is uncachable etc)

Heh, the NMI is just another place that has the IPI problem. A different issue to the MTRR. Well, same bug, different place.

Quoted 5 lines

the MTRR code should disable NMIs as much as possible.

and for sure in -RT, the MTRR change section should not be preemptable at all.

Yeah, that is why I found this. The current code calls kfree and such from the IPI if it is allocated (not to mention the kmalloc in smp_call_function. Both of which can sleep in RT. I was forcing the data=NULL case in RT to keep it from entering the allocation code paths. But this is where I found the deadlock with MTRR (and NMI).

-- Steve

#10 lore raw
In reply to Steven Rostedt
Quoted 89 lines · On Wed, 28 Jan 2009 11:38:14 -0500 (EST) Steven Rostedt <[email protected]>…

While developing the RT git tree I came across this deadlock.

To avoid touching the memory allocator in smp_call_function_many I forced the stack use case, the path that would be taken if data fails to allocate.

Here's the current code in kernel/smp.c:

void smp_call_function_many(const struct cpumask *mask,

                            void (*func)(void *), void *info,
                            bool wait)
{
        struct call_function_data *data;
[...]
        data = kmalloc(sizeof(*data) + cpumask_size(), GFP_ATOMIC);
        if (unlikely(!data)) {
                /* Slow path. */
                for_each_online_cpu(cpu) {
                        if (cpu == smp_processor_id())
                                continue;
                        if (cpumask_test_cpu(cpu, mask))
                                smp_call_function_single(cpu, func, info, 
wait);
                }
                return;
        }

[...]

int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
int wait)

{
        struct call_single_data d;
[...]
                if (!wait) {
                        data = kmalloc(sizeof(*data), GFP_ATOMIC);
                        if (data)
                                data->flags = CSD_FLAG_ALLOC;
                }
                if (!data) {
                        data = &d;
                        data->flags = CSD_FLAG_WAIT;
                }

Note that if data failed to allocate, we force the wait state.

This immediately caused a deadlock with the mtrr code:

arch/x86/kernel/cpu/mtrr/main.c:

static void set_mtrr(unsigned int reg, unsigned long base,
unsigned long size, mtrr_type type)

{
        struct set_mtrr_data data;
[...]
        /*  Start the ball rolling on other CPUs  */
        if (smp_call_function(ipi_handler, &data, 0) != 0)
                panic("mtrr: timed out waiting for other CPUs\n");

        local_irq_save(flags);

        while(atomic_read(&data.count))
                cpu_relax();

        /* ok, reset count and toggle gate */
        atomic_set(&data.count, num_booting_cpus() - 1);
        smp_wmb();
        atomic_set(&data.gate,1);

[...]

static void ipi_handler(void *info)
/* [SUMMARY] Synchronisation handler. Executed by "other" CPUs.
[RETURNS] Nothing.
*/
{

#ifdef CONFIG_SMP
        struct set_mtrr_data *data = info;
        unsigned long flags;

        local_irq_save(flags);

        atomic_dec(&data->count);
        while(!atomic_read(&data->gate))
                cpu_relax();
Quoted 5 lines

The problem is that if we use the stack, then we must wait for the function to finish. But in the mtrr code, the called functions are waiting for the caller to do something after the smp_call_function. Thus we deadlock! This mtrr code seems to have been there for a while. At least longer than the git history.

My initial reaction is that the mtrr code is being stupid, but I guess that strengthening the smp_call_function() stuff is good, and we _do_ have this "wait=0" contract.

Quoted 15 lines

To get around this, I did the following hack. Now this may be good enough to handle the case. I'm posting it for comments.

The patch creates another flag called CSD_FLAG_RELEASE. If we fail to alloc the data and the wait bit is not set, we still use the stack but we also set this flag instead of the wait flag. The receiving IPI will copy the data locally, and if this flag is set, it will clear it. The caller, after sending the IPI, will wait on this flag to be cleared.

The difference between this and the wait bit is that the release bit is just a way to let the callee tell the caller that it copied the data and is continuing. The data can be released with no worries. This prevents the deadlock because the caller can continue without waiting for the functions to be called.

Quoted 8 lines

I tested this patch by forcing the data to be null:

	data = NULL; // kmalloc(...);

Also, when forcing data to be NULL on the latest git tree, without applying the patch, I hit a deadlock in testing of the NMI watchdog. This means there may be other areas in the kernel that think smp_call_function, without the wait bit set, expects that function not to ever wait.

Concern 1: do all architectures actually call generic_smp_call_function_single_interrupt()? I don't think they _have_ to at present, and if they don't, we now have inconsistent behaviour between architectures.

Concern 2: not all architectures set CONFIG_USE_GENERIC_SMP_HELPERS=y. Those which do not set CONFIG_USE_GENERIC_SMP_HELPERS might need to have similar changes made so that the behaviour remains consistent across architectures.

Thought: do we need to do the kmalloc at all? Perhaps we can instead use a statically allocated per-cpu call_single_data local to kernel/smp.c? It would need a spinlock or something to protect it...

#11 lore raw
Quoted 3 lines · On Wed, 28 Jan 2009 13:12:02 -0800 Andrew Morton <[email protected]>…

Thought: do we need to do the kmalloc at all? Perhaps we can instead use a statically allocated per-cpu call_single_data local to kernel/smp.c? It would need a spinlock or something to protect it...

(not a spinlock - get_cpu_var/put_cpu_var will suffice)

#12 lore raw
Quoted 8 lines · Andrew Morton
Quoted 3 lines · On Wed, 28 Jan 2009 13:12:02 -0800 Andrew Morton <[email protected]>…

Thought: do we need to do the kmalloc at all? Perhaps we can instead use a statically allocated per-cpu call_single_data local to kernel/smp.c? It would need a spinlock or something to protect it...

(not a spinlock - get_cpu_var/put_cpu_var will suffice)

Is that enough?

The calling IPIs may process the data after smp_call_function is made. What happens if two smp_call_functions are executed one after the other? The second one may corrupt the data if the IPI function has not executed yet.

We may still need that "RELEASE" flag for that case.

-- Steve

#13 lore raw
Quoted 12 lines · On Wed, 28 Jan 2009 16:23:32 -0500 (EST) Steven Rostedt <[email protected]>…
Quoted 8 lines · Andrew Morton
Quoted 3 lines · On Wed, 28 Jan 2009 13:12:02 -0800 Andrew Morton <[email protected]>…

Thought: do we need to do the kmalloc at all? Perhaps we can instead use a statically allocated per-cpu call_single_data local to kernel/smp.c? It would need a spinlock or something to protect it...

(not a spinlock - get_cpu_var/put_cpu_var will suffice)

Quoted 9 lines

Is that enough?

The calling IPIs may process the data after smp_call_function is made. What happens if two smp_call_functions are executed one after the other? The second one may corrupt the data if the IPI function has not executed yet.

We may still need that "RELEASE" flag for that case.

Good point.

Forget I said that - smp_call_function_single() is calling a function on a *different* CPU, so data which is local to the calling CPU is of course in the wrong place.

So if we're going to use per-cpu data then we'd need to protect it with a lock. We could (should?) have a separate lock for each destination CPU.

We could make smp_call_function_single() block until the IPI handler has consumed the call_single_data, in which case we might as well put the call_single_data, onto the caller's stack, as you've done.

Or we could take the per-cpu spinlock in smp_call_function_single(), and release it in the IPI handler, after the call_single_data has been consumed, which is a bit more efficient. But I have a suspicion that this is AB/BA deadlockable.

<tries to think of any scenarios>

<fails>

So we have

smp_call_function_single(int cpu)

{
	spin_lock(per_cpu(cpu, locks));
	per_cpu(cpu, call_single_data) = <stuff>
	send_ipi(cpu);
	return;
}

ipi_handler(...)

{
	int cpu = smp_processor_id();
	call_single_data csd = per_cpu(cpu, call_single_data);

	spin_unlock(per_cpu(cpu, locks));
	use(csd);
}

does that work?

Dunno if it's any better than what you have now. It does however remove the unpleasant "try kmalloc and if that failed, try something else" mess.

#14 lore raw
Quoted 37 lines · Andrew Morton

So if we're going to use per-cpu data then we'd need to protect it with a lock. We could (should?) have a separate lock for each destination CPU.

We could make smp_call_function_single() block until the IPI handler has consumed the call_single_data, in which case we might as well put the call_single_data, onto the caller's stack, as you've done.

Or we could take the per-cpu spinlock in smp_call_function_single(), and release it in the IPI handler, after the call_single_data has been consumed, which is a bit more efficient. But I have a suspicion that this is AB/BA deadlockable.

<tries to think of any scenarios>

<fails>

So we have

smp_call_function_single(int cpu)

{
	spin_lock(per_cpu(cpu, locks));
	per_cpu(cpu, call_single_data) = <stuff>
	send_ipi(cpu);
	return;
}

ipi_handler(...)

{
	int cpu = smp_processor_id();
	call_single_data csd = per_cpu(cpu, call_single_data);

	spin_unlock(per_cpu(cpu, locks));
	use(csd);
}
Quoted 1 line

does that work?

I don't think so. With ticket spinlocks and such, that just looks like it is destine to crash. Also, spinlocks disable preemption, and we would need to enable it again otherwise we have a dangling preempt_disable.

Quoted 4 lines

Dunno if it's any better than what you have now. It does however remove the unpleasant "try kmalloc and if that failed, try something else" mess.

We could have a percpu for single data and still use the lock. Keep the method of the IPI handler signaling to the caller that they copied it to their stack. Then the caller could release the lock.

We can keep this only for the non wait case. Most users set the wait bit, so it will only slow down the non waiters.

Of course this will only work with the single cpu function callers. I think the all cpu function callers still need to alloc.

-- Steve

#15 lore raw
Quoted 39 lines · On Wed, 28 Jan 2009 17:47:55 -0500 (EST) Steven Rostedt <[email protected]>…
Quoted 37 lines · Andrew Morton

So if we're going to use per-cpu data then we'd need to protect it with a lock. We could (should?) have a separate lock for each destination CPU.

We could make smp_call_function_single() block until the IPI handler has consumed the call_single_data, in which case we might as well put the call_single_data, onto the caller's stack, as you've done.

Or we could take the per-cpu spinlock in smp_call_function_single(), and release it in the IPI handler, after the call_single_data has been consumed, which is a bit more efficient. But I have a suspicion that this is AB/BA deadlockable.

<tries to think of any scenarios>

<fails>

So we have

smp_call_function_single(int cpu)

{
	spin_lock(per_cpu(cpu, locks));
	per_cpu(cpu, call_single_data) = <stuff>
	send_ipi(cpu);
	return;
}

ipi_handler(...)

{
	int cpu = smp_processor_id();
	call_single_data csd = per_cpu(cpu, call_single_data);

	spin_unlock(per_cpu(cpu, locks));
	use(csd);
}
Quoted 5 lines
Quoted 1 line

does that work?

I don't think so. With ticket spinlocks and such, that just looks like it is destine to crash. Also, spinlocks disable preemption, and we would need to enable it again otherwise we have a dangling preempt_disable.

Well that sucks.

I think the model of taking a lock, passing the data across to another thread of control and having that thread of control release the lock once the data has been consumed is a good one. It's faster and in this case it means that we can now (maybe) perform (wait=0) IPI calls with local interrupts disabled, which wasn't the case before.

It's a shame that irrelevant-other-stuff prevents us from implementing such a thing. Of course, we can still do it, via some ad-hoc locking thing using raw_spin_lock/atomic_t's/bitops/cpu_relax/etc.

Quoted 8 lines
Quoted 4 lines

Dunno if it's any better than what you have now. It does however remove the unpleasant "try kmalloc and if that failed, try something else" mess.

We could have a percpu for single data and still use the lock. Keep the method of the IPI handler signaling to the caller that they copied it to their stack. Then the caller could release the lock.

Yeah, spose so. That separates the signalling from the locking, rather than using the lock as the signal. But it's an inferior solution because it a) makes the caller hang around until the consumer has executed and it b) requires that callers still have local interrupts enabled.

Now, maybe we can never implement b) at all - maybe we'll still require that callers have local interrupts enabled. Because there might be arch_send_call_function_single_ipi() which has to loop around until it sees that the target CPU has accepted the interrupt, dunno.

Quoted 2 lines

We can keep this only for the non wait case. Most users set the wait bit, so it will only slow down the non waiters.

It would be good to avoid separate sync and async code paths as much as possible, of course.

Quoted 2 lines

Of course this will only work with the single cpu function callers. I think the all cpu function callers still need to alloc.

I haven't really thought about the smp_call_function_many() common case.

#16 lore raw
Quoted 5 lines · Andrew Morton
Quoted 4 lines

I don't think so. With ticket spinlocks and such, that just looks like it is destine to crash. Also, spinlocks disable preemption, and we would need to enable it again otherwise we have a dangling preempt_disable.

Quoted 7 lines

Well that sucks.

I think the model of taking a lock, passing the data across to another thread of control and having that thread of control release the lock once the data has been consumed is a good one. It's faster and in this case it means that we can now (maybe) perform (wait=0) IPI calls with local interrupts disabled, which wasn't the case before.

I think that model is nice too. Just not for spinlocks ;-)

Quoted 4 lines

It's a shame that irrelevant-other-stuff prevents us from implementing such a thing. Of course, we can still do it, via some ad-hoc locking thing using raw_spin_lock/atomic_t's/bitops/cpu_relax/etc.

It should not be too hackish. I don't even think we need raw or atomic.

cpu caller:

again:

	spin_lock(&data_lock);
	if (per_cpu(data, cpu).lock) {
		spin_unlock(&data_lock);
		cpu_relax();
		goto again;
	}

	per_cpu(data, cpu).lock = 1;
	spin_unlock(&data_lock);

	call ipi functions

cpu callee:

	func();

	smp_wmb();
	per_cpu(data, cpu).lock = 0;

Here we can only call an ipi on a funcion if the data lock is cleared. If it is set, we wait for the ipi function to clear it and then we set it.

Thus we synchronize the callers, but the callers do not need to wait on the callees. And since the callers can only call a ipi on a cpu that is finished, we do not need to worry about corrupted data.

Quoted 6 lines
Quoted 3 lines

Of course this will only work with the single cpu function callers. I think the all cpu function callers still need to alloc.

I haven't really thought about the smp_call_function_many() common case.

We can keep the original code that still does the malloc for the many cpus. But falls back to the single version that does not use malloc if the malloc fails.

current code for smp_call_function_many():

        data = kmalloc(sizeof(*data) + cpumask_size(), GFP_ATOMIC);
        if (unlikely(!data)) {
                /* Slow path. */
                for_each_online_cpu(cpu) {
                        if (cpu == smp_processor_id())
                                continue;
                        if (cpumask_test_cpu(cpu, mask))
                                smp_call_function_single(cpu, func, info, wait);
                }
                return;
        }

I think this would work.

/me goes and tries it out

-- Steve

#17 lore raw
In reply to Steven Rostedt
Quoted 8 lines · On Thursday 29 January 2009 03:08:14 Steven Rostedt wrote:

While developing the RT git tree I came across this deadlock.

To avoid touching the memory allocator in smp_call_function_many I forced the stack use case, the path that would be taken if data fails to allocate.

Here's the current code in kernel/smp.c:

Interesting. I simplified smp_call_function_ma{sk,ny}, and introduced this bug (see 54b11e6d57a10aa9d0009efd93873e17bffd5d30).

We used to wait on OOM, yes, but we didn't do them one at a time.

We could restore that quiesce code, or call a function on all online cpus using on-stack data, and have them atomic_dec a counter when they're done (I'm not sure why we didn't do this in the first place: Nick?)

Quoted 5 lines

The problem is that if we use the stack, then we must wait for the function to finish. But in the mtrr code, the called functions are waiting for the caller to do something after the smp_call_function. Thus we deadlock! This mtrr code seems to have been there for a while. At least longer than the git history.

I don't see how the *ever* worked then, even with the quiesce stuff.

Quoted 5 lines

The patch creates another flag called CSD_FLAG_RELEASE. If we fail to alloc the data and the wait bit is not set, we still use the stack but we also set this flag instead of the wait flag. The receiving IPI will copy the data locally, and if this flag is set, it will clear it. The caller, after sending the IPI, will wait on this flag to be cleared.

Doesn't this break with more than one cpus? I think a refcnt is needed for the general case...

Rusty.

#18 lore raw
Quoted 4 lines · Rusty Russell
Quoted 3 lines · On Thursday 29 January 2009 03:08:14 Steven Rostedt wrote:

While developing the RT git tree I came across this deadlock.

Quoted 8 lines
Quoted 5 lines

To avoid touching the memory allocator in smp_call_function_many I forced the stack use case, the path that would be taken if data fails to allocate.

Here's the current code in kernel/smp.c:

Interesting. I simplified smp_call_function_ma{sk,ny}, and introduced this bug (see 54b11e6d57a10aa9d0009efd93873e17bffd5d30).

No, I think the bug existed before you simplified it. In fact, I'm currently working on 2.6.28 where I hit the bug. I actually backported part of that commit to implement this.

Quoted 8 lines

We used to wait on OOM, yes, but we didn't do them one at a time.

We could restore that quiesce code, or call a function on all online cpus using on-stack data, and have them atomic_dec a counter when they're done (I'm not sure why we didn't do this in the first place:
Nick?)

Quoted 7 lines
Quoted 5 lines

The problem is that if we use the stack, then we must wait for the function to finish. But in the mtrr code, the called functions are waiting for the caller to do something after the smp_call_function. Thus we deadlock! This mtrr code seems to have been there for a while. At least longer than the git history.

I don't see how the *ever* worked then, even with the quiesce stuff.

It didn't ;-)

Quoted 9 lines
Quoted 6 lines

The patch creates another flag called CSD_FLAG_RELEASE. If we fail to alloc the data and the wait bit is not set, we still use the stack but we also set this flag instead of the wait flag. The receiving IPI will copy the data locally, and if this flag is set, it will clear it. The caller, after sending the IPI, will wait on this flag to be cleared.

Doesn't this break with more than one cpus? I think a refcnt is needed for the general case...

I only use it on a single cpu call. This was what I backported from your patch. I still have the first alloc (ifdef out for RT), but the fall back goes to single CPU mode, one at a time.

void smp_call_function_many(const struct cpumask *mask,

                            void (*func)(void *), void *info,
                            bool wait)
{
        struct call_function_data *data;
[...]
        data = kmalloc(sizeof(*data) + cpumask_size(), GFP_ATOMIC);
        if (unlikely(!data)) {
                /* Slow path. */
                for_each_online_cpu(cpu) {
                        if (cpu == smp_processor_id())
                                continue;
                        if (cpumask_test_cpu(cpu, mask))
                                smp_call_function_single(cpu, func, info, wait);
                }
                return;
        }

I only needed to handle the single cpu case. Yes, this is slow because it would need to wait for each individual CPU before going to the next. But it at least is a work around.

-- Steve

#19 lore raw

PATCH 1/1 use per cpu data for single cpu ipi calls

In reply to Rusty Russell

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables instead of allocating for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

---

kernel/smp.c +34 -6
index 5cfa0e5..aba3813 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_LOCK		= 0x04,
 };
 
 struct call_function_data {
@@ -186,6 +187,9 @@ void generic_smp_call_function_single_interrupt(void)
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
+			} else if (data_flags & CSD_FLAG_LOCK) {
+				smp_wmb();
+				data->flags &= ~CSD_FLAG_LOCK;
 			} else if (data_flags & CSD_FLAG_ALLOC)
 				kfree(data);
 		}
@@ -196,6 +200,9 @@ void generic_smp_call_function_single_interrupt(void)
 	}
 }
 
+static DEFINE_PER_CPU(struct call_single_data, csd_data);
+static DEFINE_SPINLOCK(csd_data_lock);
+
 /*
  * smp_call_function_single - Run a function on a specific CPU
  * @func: The function to run. This must be fast and non-blocking.
@@ -224,14 +231,35 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		func(info);
 		local_irq_restore(flags);
 	} else if ((unsigned)cpu < nr_cpu_ids && cpu_online(cpu)) {
-		struct call_single_data *data = NULL;
+		struct call_single_data *data;
 
 		if (!wait) {
-			data = kmalloc(sizeof(*data), GFP_ATOMIC);
-			if (data)
-				data->flags = CSD_FLAG_ALLOC;
-		}
-		if (!data) {
+			data = &per_cpu(csd_data, cpu);
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We use a per cpu data to pass the information
+			 * to that CPU, but since all callers of this
+			 * code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 * We use spinlocks to manage the callers.
+			 */
+			spin_lock(&csd_data_lock);
+			while (data->flags & CSD_FLAG_LOCK)
+				cpu_relax();
+			data->flags = CSD_FLAG_LOCK;
+			spin_unlock(&csd_data_lock);
+		} else {
 			data = &d;
 			data->flags = CSD_FLAG_WAIT;
 		}
#20 lore raw

Re: [PATCH] use per cpu data for single cpu ipi calls

Quoted 5 lines · On Wed, 28 Jan 2009 19:52:16 -0500 (EST) Steven Rostedt <[email protected]>…

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the

"mandatory"

Quoted 9 lines

smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if

"Unfortunately".

Quoted 93 lines

the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables instead of allocating for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

---

kernel/smp.c +27 -6
index 5cfa0e5..aba3813 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_LOCK		= 0x04,
 };
 
 struct call_function_data {
@@ -186,6 +187,9 @@ void generic_smp_call_function_single_interrupt(void)
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
+			} else if (data_flags & CSD_FLAG_LOCK) {
+				smp_wmb();
+				data->flags &= ~CSD_FLAG_LOCK;
 			} else if (data_flags & CSD_FLAG_ALLOC)
 				kfree(data);
 		}
@@ -196,6 +200,9 @@ void generic_smp_call_function_single_interrupt(void)
 	}
 }
 
+static DEFINE_PER_CPU(struct call_single_data, csd_data);
+static DEFINE_SPINLOCK(csd_data_lock);
+
 /*
  * smp_call_function_single - Run a function on a specific CPU
  * @func: The function to run. This must be fast and non-blocking.
@@ -224,14 +231,35 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		func(info);
 		local_irq_restore(flags);
 	} else if ((unsigned)cpu < nr_cpu_ids && cpu_online(cpu)) {
-		struct call_single_data *data = NULL;
+		struct call_single_data *data;
 
 		if (!wait) {
-			data = kmalloc(sizeof(*data), GFP_ATOMIC);
-			if (data)
-				data->flags = CSD_FLAG_ALLOC;
-		}
-		if (!data) {
+			data = &per_cpu(csd_data, cpu);
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We use a per cpu data to pass the information
+			 * to that CPU, but since all callers of this
+			 * code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 * We use spinlocks to manage the callers.

kernel/smp.c int smp_call_function_single(int cpu, void (*func) (void *info), void *info, · line 265

Quoted 10 lines
kernel/smp.c +7 -0
+			 */
+			spin_lock(&csd_data_lock);
+			while (data->flags & CSD_FLAG_LOCK)
+				cpu_relax();
+			data->flags = CSD_FLAG_LOCK;
+			spin_unlock(&csd_data_lock);
+		} else {
 			data = &d;
 			data->flags = CSD_FLAG_WAIT;
 		}

Well that looks nice.

Can we make the spinlock a per-cpu thing as well? Or is that over-optimising? We'd need to initialise all those spinlocks at runtime.

In generic_smp_call_function_single_interrupt(), did you consider releasing the "lock" _before_ calling the callback function? That would reduces latencies a bit, allow more concurrency. Maybe that's over-optimising too.

Can generic_smp_call_function_single_interrupt() ever see CSD_FLAG_ALLOC set now? If not, that kfree can go away.

And where do we now stand with the architectures which _don't_ use the kernel/smp.c code? If someone writes code in generic kernel which relies upon the new capabilities, it will go bad on those architectures. Makes davem sad.

#21 lore raw

Re: [PATCH] use per cpu data for single cpu ipi calls

Quoted 10 lines · Andrew Morton
Quoted 5 lines · On Wed, 28 Jan 2009 19:52:16 -0500 (EST) Steven Rostedt <[email protected]>…

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the

"mandatory"

Some day I'll learn to use spell check.

Quoted 4 lines
Quoted 2 lines

Unfortunatly, some callers do no abide by this hint and act as if

"Unfortunately".

Unfortunately, not today.

Quoted 2 lines

Well that looks nice.

Thank you.

Quoted 4 lines

Can we make the spinlock a per-cpu thing as well? Or is that over-optimising? We'd need to initialise all those spinlocks at runtime.

I thought about it and thought it was over optimizing (US spelling). But I could be wrong.

Quoted 5 lines

In generic_smp_call_function_single_interrupt(), did you consider releasing the "lock" _before_ calling the callback function? That would reduces latencies a bit, allow more concurrency. Maybe that's over-optimising too.

I thought about it too, but I wanted to avoid the coping of the data fields. Currently the callee does:

                   data = list_entry(list.next, struct call_single_data,
                                           list);
                   list_del(&data->list);

                   /*
                    * 'data' can be invalid after this call if
                    * flags == 0 (when called through
                    * generic_exec_single(), so save them away before
                    * making the call.
                    */
                    data_flags = data->flags;

                    data->func(data->info);

I would need to have a stack item like I did in my first release, and copy it.

	d = *data;
	smp_wmb();
	data->flags &= ~CDS_FLAG_LOCK;

	d->func(d->info).

I figured that the contention would only happen with a second caller. The first caller does not have to wait. And I doubt that there would be many instances of two callers contending. Matters how often smp_call_function is called.

Probably not enough contention to worry about.

Quoted 3 lines

Can generic_smp_call_function_single_interrupt() ever see CSD_FLAG_ALLOC set now? If not, that kfree can go away.

Probably not, but I kept it just in case. I see there's a way a caller can pass in their own data through

generic_exec_single()

A user could potentially set the ALLOC flag. But since the enum is defined in this file, I find that highly unlikely. But looking at some of the code in the kernel, I would not be surprised if it is.

Quoted 5 lines

And where do we now stand with the architectures which _don't_ use the kernel/smp.c code? If someone writes code in generic kernel which relies upon the new capabilities, it will go bad on those architectures. Makes davem sad.

I guess someone should flag the arch list.

-- Steve

#22 lore raw

Re: [PATCH] use per cpu data for single cpu ipi calls

In reply to Andrew Morton
Quoted 91 lines · Andrew Morton
Quoted 5 lines · On Wed, 28 Jan 2009 19:52:16 -0500 (EST) Steven Rostedt <[email protected]>…

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the

"mandatory"

Quoted 9 lines

smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if

"Unfortunately".

Quoted 68 lines

the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables instead of allocating for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

---

kernel/smp.c +8 -1
index 5cfa0e5..aba3813 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_LOCK		= 0x04,
 };
 
 struct call_function_data {
@@ -186,6 +187,9 @@ void generic_smp_call_function_single_interrupt(void)
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
+			} else if (data_flags & CSD_FLAG_LOCK) {
+				smp_wmb();
+				data->flags &= ~CSD_FLAG_LOCK;
 			} else if (data_flags & CSD_FLAG_ALLOC)
 				kfree(data);
 		}
@@ -196,6 +200,9 @@ void generic_smp_call_function_single_interrupt(void)
 	}
 }
 
+static DEFINE_PER_CPU(struct call_single_data, csd_data);
+static DEFINE_SPINLOCK(csd_data_lock);
+
 /*
  * smp_call_function_single - Run a function on a specific CPU
  * @func: The function to run. This must be fast and non-blocking.
@@ -224,14 +231,35 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		func(info);
 		local_irq_restore(flags);
 	} else if ((unsigned)cpu < nr_cpu_ids && cpu_online(cpu)) {
-		struct call_single_data *data = NULL;
+		struct call_single_data *data;
 
Quoted 5 lines

kernel/smp.c int smp_call_function_single(int cpu, void (*func) (void *info), void *info, · line 233

Quoted 5 lines
kernel/smp.c +0 -4
 		if (!wait) {
-			data = kmalloc(sizeof(*data), GFP_ATOMIC);
-			if (data)
-				data->flags = CSD_FLAG_ALLOC;
-		}

I would advise against removing this, it would destroy a lot of the properties of smp_call_function_single() that it was designed to have.

That kmalloc allows you to send multiple requests and batch them.

Quoted 33 lines
Quoted 20 lines
kernel/smp.c +19 -1
-		if (!data) {
+			data = &per_cpu(csd_data, cpu);
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We use a per cpu data to pass the information
+			 * to that CPU, but since all callers of this
+			 * code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 * We use spinlocks to manage the callers.

kernel/smp.c int smp_call_function_single(int cpu, void (*func) (void *info), void *info, · line 265

Quoted 10 lines
kernel/smp.c +7 -0
+			 */
+			spin_lock(&csd_data_lock);
+			while (data->flags & CSD_FLAG_LOCK)
+				cpu_relax();
+			data->flags = CSD_FLAG_LOCK;
+			spin_unlock(&csd_data_lock);
+		} else {
 			data = &d;
 			data->flags = CSD_FLAG_WAIT;
 		}

Well that looks nice.

Quoted 3 lines

Can we make the spinlock a per-cpu thing as well? Or is that over-optimising? We'd need to initialise all those spinlocks at runtime.

I think we should, its easy enough, and

static DEFINE_PER_CPU(spinlock_t, csd_lock) =

	__SPIN_LOCK_UNLOCKED(csd_lock);

might just work.

Quoted 4 lines

In generic_smp_call_function_single_interrupt(), did you consider releasing the "lock" _before_ calling the callback function? That would reduces latencies a bit, allow more concurrency. Maybe that's over-optimising too.

You'd have to copy the func and info fields to do that, but yeah, that'd work.

Quoted 2 lines

Can generic_smp_call_function_single_interrupt() ever see CSD_FLAG_ALLOC set now? If not, that kfree can go away.

Like said above, removing that kmalloc will hurt people.

#23 lore raw

Re: [PATCH] use per cpu data for single cpu ipi calls

Quoted 4 lines · Peter Zijlstra
Quoted 2 lines

Can generic_smp_call_function_single_interrupt() ever see CSD_FLAG_ALLOC set now? If not, that kfree can go away.

Like said above, removing that kmalloc will hurt people.

the whole promise of generic-IPI seems to dwindle and we'll get back to roughly where we started out from.

Ingo

#24 lore raw

Re: [PATCH] use per cpu data for single cpu ipi calls

Quoted 9 lines · Ingo Molnar
Quoted 4 lines · Peter Zijlstra
Quoted 2 lines

Can generic_smp_call_function_single_interrupt() ever see CSD_FLAG_ALLOC set now? If not, that kfree can go away.

Like said above, removing that kmalloc will hurt people.

the whole promise of generic-IPI seems to dwindle and we'll get back to roughly where we started out from.

I'd not go that far, the per-cpu csd is a nice fallback, but removing that kmalloc is just silly.

And I see no reason why arch specific could do any better (aside from sparc which has fancy ipis).

#25 lore raw

Re: [PATCH] use per cpu data for single cpu ipi calls

Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Ingo Molnar
Quoted 4 lines · Peter Zijlstra
Quoted 2 lines

Can generic_smp_call_function_single_interrupt() ever see CSD_FLAG_ALLOC set now? If not, that kfree can go away.

Like said above, removing that kmalloc will hurt people.

Quoted 8 lines
Quoted 2 lines

the whole promise of generic-IPI seems to dwindle and we'll get back to roughly where we started out from.

I'd not go that far, the per-cpu csd is a nice fallback, but removing that kmalloc is just silly.

And I see no reason why arch specific could do any better (aside from sparc which has fancy ipis).

well if the hw can embedd at least 64 bit of dataload in the IPI itself, we could get rid of a lot of complications. But since we cannot (on x86 and most other architectures), we've got to demultiplex from generic data which brings up serialization issues and adds overhead .

Ingo

#26 lore raw

Re: [PATCH] use per cpu data for single cpu ipi calls

In reply to Peter Zijlstra
Quoted 6 lines · Peter Zijlstra
Quoted 5 lines · Ingo Molnar
Quoted 3 lines · Peter Zijlstra
Quoted 2 lines

Can generic_smp_call_function_single_interrupt() ever see CSD_FLAG_ALLOC set now? If not, that kfree can go away.

Quoted 7 lines
Quoted 4 lines
Quoted 1 line

Like said above, removing that kmalloc will hurt people.

the whole promise of generic-IPI seems to dwindle and we'll get back to roughly where we started out from.

I'd not go that far, the per-cpu csd is a nice fallback, but removing that kmalloc is just silly.

I'll add the kmalloc back. But the rest should be fine.

-- Steve

#27 lore raw

PATCH 1/1 use per cpu data for single cpu ipi calls

In reply to Peter Zijlstra

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables if the allocation of the data fails for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

[
changes for v2:

-- kept kmalloc and only use per cpu if kmalloc fails.
(Requested by Peter Zijlstra)

-- added per cpu spinlocks
(Requested by Andrew Morton and Peter Zijlstra)
]

---

kernel/smp.c +38 -3
index 5cfa0e5..9bce851 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_LOCK		= 0x04,
 };
 
 struct call_function_data {
@@ -186,6 +187,9 @@ void generic_smp_call_function_single_interrupt(void)
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
+			} else if (data_flags & CSD_FLAG_LOCK) {
+				smp_wmb();
+				data->flags &= ~CSD_FLAG_LOCK;
 			} else if (data_flags & CSD_FLAG_ALLOC)
 				kfree(data);
 		}
@@ -196,6 +200,10 @@ void generic_smp_call_function_single_interrupt(void)
 	}
 }
 
+static DEFINE_PER_CPU(struct call_single_data, csd_data);
+static DEFINE_PER_CPU(spinlock_t, csd_data_lock) =
+	__SPIN_LOCK_UNLOCKED(csd_lock);
+
 /*
  * smp_call_function_single - Run a function on a specific CPU
  * @func: The function to run. This must be fast and non-blocking.
@@ -224,14 +232,41 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		func(info);
 		local_irq_restore(flags);
 	} else if ((unsigned)cpu < nr_cpu_ids && cpu_online(cpu)) {
-		struct call_single_data *data = NULL;
+		struct call_single_data *data;
 
 		if (!wait) {
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We first try to allocate the data, but if we
+			 * fail, we fall back to use a per cpu data to pass
+			 * the information to that CPU. Since all callers
+			 * of this code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 * We use spinlocks to manage the callers.
+			 */
 			data = kmalloc(sizeof(*data), GFP_ATOMIC);
 			if (data)
 				data->flags = CSD_FLAG_ALLOC;
-		}
-		if (!data) {
+			else {
+				data = &per_cpu(csd_data, cpu);
+				spin_lock(&per_cpu(csd_data_lock, cpu));
+				while (data->flags & CSD_FLAG_LOCK)
+					cpu_relax();
+				data->flags = CSD_FLAG_LOCK;
+				spin_unlock(&per_cpu(csd_data_lock, cpu));
+			}
+		} else {
 			data = &d;
 			data->flags = CSD_FLAG_WAIT;
 		}
Acked-by on v1 1/1
#28 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Quoted 43 lines · Steven Rostedt

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables if the allocation of the data fails for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

[
changes for v2:

Quoted 8 lines

-- kept kmalloc and only use per cpu if kmalloc fails.
(Requested by Peter Zijlstra)

-- added per cpu spinlocks
(Requested by Andrew Morton and Peter Zijlstra)
]

Looks nice, thanks!

Quoted 80 lines

---

kernel/smp.c +38 -3
index 5cfa0e5..9bce851 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_LOCK		= 0x04,
 };
 
 struct call_function_data {
@@ -186,6 +187,9 @@ void generic_smp_call_function_single_interrupt(void)
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
+			} else if (data_flags & CSD_FLAG_LOCK) {
+				smp_wmb();
+				data->flags &= ~CSD_FLAG_LOCK;
 			} else if (data_flags & CSD_FLAG_ALLOC)
 				kfree(data);
 		}
@@ -196,6 +200,10 @@ void generic_smp_call_function_single_interrupt(void)
 	}
 }
 
+static DEFINE_PER_CPU(struct call_single_data, csd_data);
+static DEFINE_PER_CPU(spinlock_t, csd_data_lock) =
+	__SPIN_LOCK_UNLOCKED(csd_lock);
+
 /*
  * smp_call_function_single - Run a function on a specific CPU
  * @func: The function to run. This must be fast and non-blocking.
@@ -224,14 +232,41 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		func(info);
 		local_irq_restore(flags);
 	} else if ((unsigned)cpu < nr_cpu_ids && cpu_online(cpu)) {
-		struct call_single_data *data = NULL;
+		struct call_single_data *data;
 
 		if (!wait) {
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We first try to allocate the data, but if we
+			 * fail, we fall back to use a per cpu data to pass
+			 * the information to that CPU. Since all callers
+			 * of this code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 * We use spinlocks to manage the callers.
+			 */
 			data = kmalloc(sizeof(*data), GFP_ATOMIC);
 			if (data)
 				data->flags = CSD_FLAG_ALLOC;
-		}
-		if (!data) {
+			else {
+				data = &per_cpu(csd_data, cpu);
+				spin_lock(&per_cpu(csd_data_lock, cpu));
+				while (data->flags & CSD_FLAG_LOCK)
+					cpu_relax();
+				data->flags = CSD_FLAG_LOCK;
+				spin_unlock(&per_cpu(csd_data_lock, cpu));
+			}
+		} else {
 			data = &d;
 			data->flags = CSD_FLAG_WAIT;
 		}
#29 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Quoted 51 lines · Peter Zijlstra
Quoted 50 lines · Steven Rostedt

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables if the allocation of the data fails for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

[
changes for v2:

-- kept kmalloc and only use per cpu if kmalloc fails.
(Requested by Peter Zijlstra)

-- added per cpu spinlocks
(Requested by Andrew Morton and Peter Zijlstra)
]

Quoted 5 lines
Quoted 1 line

Looks nice, thanks!

started testing it in tip/core/urgent, thanks guys!

Ingo

#30 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

In reply to Steven Rostedt
Quoted 7 lines · Steven Rostedt

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

That spinlock cannot be right. It is provably wrong for so many reasons..

Think about it. We're talking about a per-CPU lock, which already makes no
sense: we're only locking against our own CPU, and we've already disabled preemption for totally unrelated reasons.

And the only way locking can make sense against our own CPU is if we lock against interrupts - but the lock isn't actually irq-safe, so if you are trying to lock against interrupts, you are (a) doing it wrong (you should disable interrupts, not use a spinlock) and (b) causing a deadlock if it ever happens.

In other words: no way in hell does that make any sense what-so-ever.

Just remove it. As it is, it can only hurt. There's no possible point to it.

Now, if people actually do send IPI's from interrupts (and it does happen
- cross-cpu wakeups etc), then that implies that you do want to then make the whole thing irq-safe. But the *spinlock* is pointless.

But to be irq-safe, you now need to protect the _whole_ region against interrupts, because otherwise an incoming interrupt will hit while the CSD_FLAG_LOCK bit is set, perhaps _before_ the actual IPI has been sent, and now nothing will ever clear it. So the interrupt handler that tries to send an IPI will now spin forever.

So NAK on this patch. I think the approach is correct, but the implementation is buggy.

Linus

#31 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Quoted 11 lines · Linus Torvalds
Quoted 7 lines · Steven Rostedt

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

Quoted 5 lines

That spinlock cannot be right. It is provably wrong for so many reasons..

Think about it. We're talking about a per-CPU lock, which already makes no
sense: we're only locking against our own CPU, and we've already disabled preemption for totally unrelated reasons.

Actually, we are locking against the destination CPU. Or perhaps I'm misunderstanding you. The lock is protecting the destination data. The 'cpu' variable is the CPU we call to, not the current CPU.

Quoted 6 lines

And the only way locking can make sense against our own CPU is if we lock against interrupts - but the lock isn't actually irq-safe, so if you are trying to lock against interrupts, you are (a) doing it wrong (you should disable interrupts, not use a spinlock) and (b) causing a deadlock if it ever happens.

I did not think an interrupt handler was allowed to do a smp_call_function. If it is, then you are correct and this is very buggy.

Both smp_call_function and smp_call_function have a:

	WARN_ON(irqs_disabled());

and comments saying that interrupts must be enabled and that these can not be called from interrupt or softirq handlers.

The spin lock is to protect this scenario:

task on CPU 0 sends IPI to CPU 2
task on CPU 1 sends IPI to CPU 2

The first task to get past that spin lock (which is for CPU 2) will send the IPI. The second task will keep have to spin until the LOCK bit is cleared.

In other words, that spin lock is just a fancy:

again:

	flags = per_cpu(csd_data).flags & ~CSD_FLAG_LOCK;
	if (cmpxchg(&per_cpu(csd_data, cpu).lock, flags,
	    flags | CSD_FLAG_LOCK) != flags) {
		cpu_relax();
		goto again;
	}
Quoted 9 lines

In other words: no way in hell does that make any sense what-so-ever.

Just remove it. As it is, it can only hurt. There's no possible point to it.

Now, if people actually do send IPI's from interrupts (and it does happen
- cross-cpu wakeups etc), then that implies that you do want to then make the whole thing irq-safe. But the *spinlock* is pointless.

But these IPIs would not use the smp_call_function routines.

Quoted 6 lines

But to be irq-safe, you now need to protect the _whole_ region against interrupts, because otherwise an incoming interrupt will hit while the CSD_FLAG_LOCK bit is set, perhaps _before_ the actual IPI has been sent, and now nothing will ever clear it. So the interrupt handler that tries to send an IPI will now spin forever.

Again, this code is not allowed to run from an interrupt handler.

Quoted 3 lines

So NAK on this patch. I think the approach is correct, but the implementation is buggy.

-- Steve

#32 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Quoted 13 lines · Steven Rostedt
Quoted 7 lines

But to be irq-safe, you now need to protect the _whole_ region against interrupts, because otherwise an incoming interrupt will hit while the CSD_FLAG_LOCK bit is set, perhaps _before_ the actual IPI has been sent, and now nothing will ever clear it. So the interrupt handler that tries to send an IPI will now spin forever.

Again, this code is not allowed to run from an interrupt handler.

Quoted 3 lines

So NAK on this patch. I think the approach is correct, but the implementation is buggy.

My whole assumption of this is that smp_call_function_single can not be called from an interrupt handler. If it can, then perhaps I just change the spinlock to the cmpxchg code, and put a:

	WARN_ON(cpu == smp_processor_id());

-- Steve

#33 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

In reply to Steven Rostedt
Quoted 2 lines · Steven Rostedt

Actually, we are locking against the destination CPU.

Oh.

THAT'S JUST INCOMPETENT.

What the *fuck* is the point of having per-CPU data, and then using it for the wrong CPU?

Stop doing that idiocy. Put the per-cpu data on the senders side, and stop the idiocy. You are going to get cross-CPU cacheline bouncing anyway, there's no way to avoid it, but as long as you do it on the wrong CPU's local data, you're missing the whole POINT of having per-cpu data in the first place.

But yeah, that explains the locking. One stupid design mistake leads to another.

And are you really sure it cannot be called from within interrupts? I'm finding a lot of callers of smp_call_function_single(), and while I couldn't find any that look like interrupts, I also couldn't find any indication that it never happens.

Linus

#34 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Quoted 9 lines · Linus Torvalds
Quoted 2 lines · Steven Rostedt

Actually, we are locking against the destination CPU.

Oh.

THAT'S JUST INCOMPETENT.

Or lack of sleep ;-)

Quoted 10 lines

What the *fuck* is the point of having per-CPU data, and then using it for the wrong CPU?

Stop doing that idiocy. Put the per-cpu data on the senders side, and stop the idiocy. You are going to get cross-CPU cacheline bouncing anyway, there's no way to avoid it, but as long as you do it on the wrong CPU's local data, you're missing the whole POINT of having per-cpu data in the first place.

Quoted 7 lines

But yeah, that explains the locking. One stupid design mistake leads to another.

And are you really sure it cannot be called from within interrupts? I'm finding a lot of callers of smp_call_function_single(), and while I couldn't find any that look like interrupts, I also couldn't find any indication that it never happens.

No, the solution that Peter gave on top of mine looks like something we can all be happy with.

-- Steve

#35 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

In reply to Linus Torvalds
Quoted 4 lines · Linus Torvalds

And are you really sure it cannot be called from within interrupts? I'm finding a lot of callers of smp_call_function_single(), and while I couldn't find any that look like interrupts, I also couldn't find any indication that it never happens.

Calls with wait=1 are deadlockable when done from within irqs or irq disabled sections because two cpus could cross ipi each other and stay waiting.

That leaves us with the !wait case, which wasn't safe because that kmalloc could fail, and the fallback was wait, which yields the same deadlock.

That leaves us with 6 cases,

root@laptop:/usr/src/linux-2.6# git grep "smp_call_function_single(.*0)"
arch/blackfin/kernel/kgdb.c:    smp_call_function_single(cpu, kgdb_passive_cpu_callback, NULL, 0);
arch/ia64/kernel/smpboot.c:     if (smp_call_function_single(master, sync_master, NULL, 0) < 0) {
arch/ia64/kvm/kvm-ia64.c:               smp_call_function_single(ipi_pcpu, vcpu_kick_intr, vcpu, 0);
arch/x86/kvm/x86.c:             smp_call_function_single(ipi_pcpu, vcpu_kick_intr, vcpu, 0);
arch/x86/oprofile/nmi_int.c:            smp_call_function_single(cpu, nmi_cpu_start, NULL, 0);
arch/x86/pci/amd_bus.c:         smp_call_function_single(cpu, enable_pci_io_ecs, NULL, 0);

The kgdb one looks to be buggy, as it calls smp_call_function_single() from under irqs disabled.

Such users should use __smp_call_single_function() with a pre-allocated csd.

Didn't check the others.

#36 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Quoted 25 lines · Peter Zijlstra
Quoted 4 lines · Linus Torvalds

And are you really sure it cannot be called from within interrupts? I'm finding a lot of callers of smp_call_function_single(), and while I couldn't find any that look like interrupts, I also couldn't find any indication that it never happens.

Calls with wait=1 are deadlockable when done from within irqs or irq disabled sections because two cpus could cross ipi each other and stay waiting.

That leaves us with the !wait case, which wasn't safe because that kmalloc could fail, and the fallback was wait, which yields the same deadlock.

That leaves us with 6 cases,

root@laptop:/usr/src/linux-2.6# git grep "smp_call_function_single(.*0)"
arch/blackfin/kernel/kgdb.c:    smp_call_function_single(cpu, kgdb_passive_cpu_callback, NULL, 0);
arch/ia64/kernel/smpboot.c:     if (smp_call_function_single(master, sync_master, NULL, 0) < 0) {
arch/ia64/kvm/kvm-ia64.c:               smp_call_function_single(ipi_pcpu, vcpu_kick_intr, vcpu, 0);
arch/x86/kvm/x86.c:             smp_call_function_single(ipi_pcpu, vcpu_kick_intr, vcpu, 0);
arch/x86/oprofile/nmi_int.c:            smp_call_function_single(cpu, nmi_cpu_start, NULL, 0);
arch/x86/pci/amd_bus.c:         smp_call_function_single(cpu, enable_pci_io_ecs, NULL, 0);
Quoted 7 lines

The kgdb one looks to be buggy, as it calls smp_call_function_single() from under irqs disabled.

Such users should use __smp_call_single_function() with a pre-allocated csd.

Didn't check the others.

Regardless of this, I like your change better than my original. We should do that anyway.

-- Steve

#37 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

In reply to Peter Zijlstra
Quoted 4 lines · Peter Zijlstra

Calls with wait=1 are deadlockable when done from within irqs or irq disabled sections because two cpus could cross ipi each other and stay waiting.

Sure. But this isn't the "wait=1" case. In the waiting case, we don't need to allocate anything at all, we can just use the stack.

So the only case that matters for interrupts is indeed "wait=0", but that's very much also the case we're talking about.

Quoted 3 lines

That leaves us with the !wait case, which wasn't safe because that kmalloc could fail, and the fallback was wait, which yields the same deadlock.

Yes. I agree that the _concept_ of the patch is good. No argument there.

I'm just worried about the details.

Quoted 3 lines

That leaves us with 6 cases,

root@laptop:/usr/src/linux-2.6# git grep "smp_call_function_single(.*0)"

This misses a _lot_ of cases. What about this one:

kernel/relay.c: err = smp_call_function_single(i,

where you're not seeing if it's a non-waiting one or not (it's a waiting one, but my point is that your grep is missing cases).

Doing

git grep -w smp_call_function_single | grep -v '1);'

is probably more likely to find the cases to look for.

But you're right, I'm still not seeing anything that looks _likely_ to be a problem. But I worry that it's something somebody may want to do.

Linus

#38 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Quoted 2 lines · Linus Torvalds

But you're right, I'm still not seeing anything that looks _likely_ to be a problem. But I worry that it's something somebody may want to do.

Well, the kgdb case I looked at did exactly that, and that is a problem.

As for people wanting to do it, we have __smp_call_function_single() to do just that, all you have to do is provide your own csd.

#39 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Hi,

A little late into this discussion, was nasty ill the past days.

Anyway, v2 with the suggested patches looks fine to me. That is, use local cpu storage (and thus lose the lock) and retain the the kmalloc() for the !wait case. That should still scale fine, as far as I can tell. The block layer usage, for which this was originally concocted, doesn't really care that much, since it always provides its own csd storage and thus use the __ variant of the helper.

Peter, can you post a final complete patch for review and acks?

Signature · 1 line
Jens Axboe
#40 lore raw

PATCH 1/1 use per cpu data for single cpu ipi calls

Quoted 1 line · Jens Axboe

Peter, can you post a final complete patch for review and acks?

Sure,

---

Author: Steven Rostedt <[email protected]>
Date:   Thu Jan 29 10:08:01 2009 -0500

generic-ipi: use per cpu data for single cpu ipi calls

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables if the allocation of the data fails for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it.

---
 kernel/smp.c |   37 ++++++++++++++++++++++++++++++++++---
 1 files changed, 34 insertions(+), 3 deletions(-)
kernel/smp.c +34 -3
index 5cfa0e5..9eead6c 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_LOCK		= 0x04,
 };
 
 struct call_function_data {
@@ -186,6 +187,9 @@ void generic_smp_call_function_single_interrupt(void)
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
+			} else if (data_flags & CSD_FLAG_LOCK) {
+				smp_wmb();
+				data->flags &= ~CSD_FLAG_LOCK;
 			} else if (data_flags & CSD_FLAG_ALLOC)
 				kfree(data);
 		}
@@ -196,6 +200,8 @@ void generic_smp_call_function_single_interrupt(void)
 	}
 }
 
+static DEFINE_PER_CPU(struct call_single_data, csd_data);
+
 /*
  * smp_call_function_single - Run a function on a specific CPU
  * @func: The function to run. This must be fast and non-blocking.
@@ -224,14 +230,39 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		func(info);
 		local_irq_restore(flags);
 	} else if ((unsigned)cpu < nr_cpu_ids && cpu_online(cpu)) {
-		struct call_single_data *data = NULL;
+		struct call_single_data *data;
 
 		if (!wait) {
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We first try to allocate the data, but if we
+			 * fail, we fall back to use a per cpu data to pass
+			 * the information to that CPU. Since all callers
+			 * of this code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 * We use spinlocks to manage the callers.
+			 */
 			data = kmalloc(sizeof(*data), GFP_ATOMIC);
 			if (data)
 				data->flags = CSD_FLAG_ALLOC;
-		}
-		if (!data) {
+			else {
+				data = &per_cpu(csd_data, me);
+				while (data->flags & CSD_FLAG_LOCK)
+					cpu_relax();
+				data->flags = CSD_FLAG_LOCK;
+			}
+		} else {
 			data = &d;
 			data->flags = CSD_FLAG_WAIT;
 		}
#41 lore raw

Re: [PATCH -v3] use per cpu data for single cpu ipi calls

Quoted 5 lines · Peter Zijlstra
Quoted 1 line · Jens Axboe

Peter, can you post a final complete patch for review and acks?

Sure,

Looks good, you can add my acked-by to that. One small comment:

Quoted 11 lines
kernel/smp.c +10 -0
 		if (!wait) {
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We first try to allocate the data, but if we
+			 * fail, we fall back to use a per cpu data to pass
+			 * the information to that CPU. Since all callers
+			 * of this code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.

kernel/smp.c int smp_call_function_single(int cpu, void (*func) (void *info), void *info, · line 255

Quoted 10 lines
kernel/smp.c +10 -0
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 * We use spinlocks to manage the callers.
+			 */

That last sentence appears stale now, since there's no locking involved for the per-cpu csd.

Signature · 1 line
Jens Axboe
#42 lore raw

Re: [PATCH -v3] use per cpu data for single cpu ipi calls

Quoted 16 lines · Jens Axboe
Quoted 16 lines
(quoted diff) +15 -0
 		if (!wait) {
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We first try to allocate the data, but if we
+			 * fail, we fall back to use a per cpu data to pass
+			 * the information to that CPU. Since all callers
+			 * of this code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 * We use spinlocks to manage the callers.
+			 */

That last sentence appears stale now, since there's no locking involved for the per-cpu csd.

Gah, I edited that, and generated the patch using

# git diff --stat -p 4f4b6c1a94a8735bbdc030a2911cf395495645b6.. kernel/smp.c | xclip

on Ingo's tip/master. However it seems such a diff does not include non-commited changes, even though a regular git diff does:

# git diff kernel/smp.c
kernel/smp.c +0 -1
index 9eead6c..bbedbb7 100644
@@ -251,7 +251,6 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
                         * it to clear before we set it again. This
                         * will make sure the callee is done with the
                         * data before a new caller will use it.
-                        * We use spinlocks to manage the callers.
                         */
                        data = kmalloc(sizeof(*data), GFP_ATOMIC);
                        if (data)

What is the recommended way to do such a diff?

#43 lore raw

Re: [PATCH -v3] use per cpu data for single cpu ipi calls

Quoted 48 lines · Peter Zijlstra
Quoted 16 lines · Jens Axboe
Quoted 16 lines
(quoted diff) +15 -0
 		if (!wait) {
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We first try to allocate the data, but if we
+			 * fail, we fall back to use a per cpu data to pass
+			 * the information to that CPU. Since all callers
+			 * of this code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 * We use spinlocks to manage the callers.
+			 */

That last sentence appears stale now, since there's no locking involved for the per-cpu csd.

Gah, I edited that, and generated the patch using

# git diff --stat -p 4f4b6c1a94a8735bbdc030a2911cf395495645b6.. kernel/smp.c | xclip

on Ingo's tip/master. However it seems such a diff does not include non-commited changes, even though a regular git diff does:

# git diff kernel/smp.c
kernel/smp.c +0 -1
index 9eead6c..bbedbb7 100644
@@ -251,7 +251,6 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
                         * it to clear before we set it again. This
                         * will make sure the callee is done with the
                         * data before a new caller will use it.
-                        * We use spinlocks to manage the callers.
                         */
                        data = kmalloc(sizeof(*data), GFP_ATOMIC);
                        if (data)
Quoted 1 line

What is the recommended way to do such a diff?

Drop the .. and it should work. Don't ask me why :-)

Signature · 1 line
Jens Axboe
#44 lore raw

Re: [PATCH -v3] use per cpu data for single cpu ipi calls

Quoted 1 line · Jens Axboe

Drop the .. and it should work. Don't ask me why :-)

On second thought, probably because XXX.. will mean from XXX to HEAD, and HEAD doesn't include the edited part since it isn't committed.

Signature · 1 line
Jens Axboe
#45 lore raw

Re: [PATCH -v3] use per cpu data for single cpu ipi calls

Quoted 5 lines · Jens Axboe
Quoted 1 line · Jens Axboe

Drop the .. and it should work. Don't ask me why :-)

On second thought, probably because XXX.. will mean from XXX to HEAD, and HEAD doesn't include the edited part since it isn't committed.

Ah, I guess that makes some sense. Let me do a v4 :-)

#46 lore raw

PATCH 1/1 use per cpu data for single cpu ipi calls

In reply to Peter Zijlstra
Author: Steven Rostedt <[email protected]>
Date:   Thu Jan 29 10:08:01 2009 -0500

generic-ipi: use per cpu data for single cpu ipi calls

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables if the allocation of the data fails for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it.

---
 kernel/smp.c |   36 +++++++++++++++++++++++++++++++++---
 1 files changed, 33 insertions(+), 3 deletions(-)
kernel/smp.c +33 -3
index 5cfa0e5..bbedbb7 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_LOCK		= 0x04,
 };
 
 struct call_function_data {
@@ -186,6 +187,9 @@ void generic_smp_call_function_single_interrupt(void)
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
+			} else if (data_flags & CSD_FLAG_LOCK) {
+				smp_wmb();
+				data->flags &= ~CSD_FLAG_LOCK;
 			} else if (data_flags & CSD_FLAG_ALLOC)
 				kfree(data);
 		}
@@ -196,6 +200,8 @@ void generic_smp_call_function_single_interrupt(void)
 	}
 }
 
+static DEFINE_PER_CPU(struct call_single_data, csd_data);
+
 /*
  * smp_call_function_single - Run a function on a specific CPU
  * @func: The function to run. This must be fast and non-blocking.
@@ -224,14 +230,38 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		func(info);
 		local_irq_restore(flags);
 	} else if ((unsigned)cpu < nr_cpu_ids && cpu_online(cpu)) {
-		struct call_single_data *data = NULL;
+		struct call_single_data *data;
 
 		if (!wait) {
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We first try to allocate the data, but if we
+			 * fail, we fall back to use a per cpu data to pass
+			 * the information to that CPU. Since all callers
+			 * of this code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 */
 			data = kmalloc(sizeof(*data), GFP_ATOMIC);
 			if (data)
 				data->flags = CSD_FLAG_ALLOC;
-		}
-		if (!data) {
+			else {
+				data = &per_cpu(csd_data, me);
+				while (data->flags & CSD_FLAG_LOCK)
+					cpu_relax();
+				data->flags = CSD_FLAG_LOCK;
+			}
+		} else {
 			data = &d;
 			data->flags = CSD_FLAG_WAIT;
 		}
Acked-by Jens Axboe on v1 1/1
#47 lore raw

Re: [PATCH -v4] use per cpu data for single cpu ipi calls

Quoted 41 lines · Peter Zijlstra
Author: Steven Rostedt <[email protected]>
Date:   Thu Jan 29 10:08:01 2009 -0500

generic-ipi: use per cpu data for single cpu ipi calls

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables if the allocation of the data fails for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it.

Quoted 6 lines
---
 kernel/smp.c |   36 +++++++++++++++++++++++++++++++++---
 1 files changed, 33 insertions(+), 3 deletions(-)

ok, i've updated the commit in tip/core/urgent with the commit line removal and the updated description. Find it below - any objections?

Ingo

--------------------->

Quoted 1 line

From 05257ef396a72daef9ef57e01c8dc0d55351c5c7 Mon Sep 17 00:00:00 2001

From: Steven Rostedt <[email protected]>
Date: Thu, 29 Jan 2009 10:08:01 -0500
Subject: [PATCH] generic-ipi: use per cpu data for single cpu ipi calls

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the smp_call_function can decide not to return and wait instead.

The reason for this is because it uses kmalloc to allocate storage to send to the called CPU and that CPU will free it when it is done. But if we fail to allocate the storage, the stack is used instead. This means we must wait for the called CPU to finish before continuing.

Unfortunatly, some callers do no abide by this hint and act as if the non-wait option is mandatory. The MTRR code for instance will deadlock if the smp_call_function is set to wait. This is because the smp_call_function will wait for the other CPUs to finish their called functions, but those functions are waiting on the caller to continue.

This patch changes the generic smp_call_function code to use per cpu variables if the allocation of the data fails for a single CPU call. The smp_call_function_many will fall back to the smp_call_function_single if it fails its alloc. The smp_call_function_single is modified to not force the wait state.

Since we now are using a single data per cpu we must synchronize the callers to prevent a second caller modifying the data before the first called IPI functions complete. To do so, I added a flag to the call_single_data called CSD_FLAG_LOCK. When the single CPU is called (which can be called when a many call fails an alloc), we set the LOCK bit on this per cpu data. When the caller finishes it clears the LOCK bit.

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it.

---
 kernel/smp.c |   36 +++++++++++++++++++++++++++++++++---
 1 files changed, 33 insertions(+), 3 deletions(-)
kernel/smp.c +33 -3
index 5cfa0e5..bbedbb7 100644
@@ -18,6 +18,7 @@ __cacheline_aligned_in_smp DEFINE_SPINLOCK(call_function_lock);
 enum {
 	CSD_FLAG_WAIT		= 0x01,
 	CSD_FLAG_ALLOC		= 0x02,
+	CSD_FLAG_LOCK		= 0x04,
 };
 
 struct call_function_data {
@@ -186,6 +187,9 @@ void generic_smp_call_function_single_interrupt(void)
 			if (data_flags & CSD_FLAG_WAIT) {
 				smp_wmb();
 				data->flags &= ~CSD_FLAG_WAIT;
+			} else if (data_flags & CSD_FLAG_LOCK) {
+				smp_wmb();
+				data->flags &= ~CSD_FLAG_LOCK;
 			} else if (data_flags & CSD_FLAG_ALLOC)
 				kfree(data);
 		}
@@ -196,6 +200,8 @@ void generic_smp_call_function_single_interrupt(void)
 	}
 }
 
+static DEFINE_PER_CPU(struct call_single_data, csd_data);
+
 /*
  * smp_call_function_single - Run a function on a specific CPU
  * @func: The function to run. This must be fast and non-blocking.
@@ -224,14 +230,38 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 		func(info);
 		local_irq_restore(flags);
 	} else if ((unsigned)cpu < nr_cpu_ids && cpu_online(cpu)) {
-		struct call_single_data *data = NULL;
+		struct call_single_data *data;
 
 		if (!wait) {
+			/*
+			 * We are calling a function on a single CPU
+			 * and we are not going to wait for it to finish.
+			 * We first try to allocate the data, but if we
+			 * fail, we fall back to use a per cpu data to pass
+			 * the information to that CPU. Since all callers
+			 * of this code will use the same data, we must
+			 * synchronize the callers to prevent a new caller
+			 * from corrupting the data before the callee
+			 * can access it.
+			 *
+			 * The CSD_FLAG_LOCK is used to let us know when
+			 * the IPI handler is done with the data.
+			 * The first caller will set it, and the callee
+			 * will clear it. The next caller must wait for
+			 * it to clear before we set it again. This
+			 * will make sure the callee is done with the
+			 * data before a new caller will use it.
+			 */
 			data = kmalloc(sizeof(*data), GFP_ATOMIC);
 			if (data)
 				data->flags = CSD_FLAG_ALLOC;
-		}
-		if (!data) {
+			else {
+				data = &per_cpu(csd_data, me);
+				while (data->flags & CSD_FLAG_LOCK)
+					cpu_relax();
+				data->flags = CSD_FLAG_LOCK;
+			}
+		} else {
 			data = &d;
 			data->flags = CSD_FLAG_WAIT;
 		}
Acked-by on v1 1/1
#48 lore raw

Re: [PATCH -v3] use per cpu data for single cpu ipi calls

In reply to Peter Zijlstra
Quoted 3 lines · Peter Zijlstra

My only question is whetherr we might even drop the kmalloc() some day:
I suspect that the CSD_FLAG_LOCK is essentially never a contention point, and the cost (and occasional synchronization) of kmalloc() quite possibly overwhelms any theoretical scaling ability.

If another CPU hasn't even received its IPI before the same CPU sends the next one, I'm not sure we _want_ to send one, in fact.

But that's a secondary issue, and isn't a correctness thing, just a "do we really need three different allocations?" musing..

Linus

#49 lore raw

Re: [PATCH -v3] use per cpu data for single cpu ipi calls

Quoted 4 lines · Linus Torvalds

My only question is whetherr we might even drop the kmalloc() some day:
I suspect that the CSD_FLAG_LOCK is essentially never a contention point, and the cost (and occasional synchronization) of kmalloc() quite possibly overwhelms any theoretical scaling ability.

IIRC the recent SL*B numbers posted showed that a kmalloc could be as cheap as ~100 cycles or something. IPIs are sadly still a bit more expensive.

Quoted 2 lines

If another CPU hasn't even received its IPI before the same CPU sends the next one, I'm not sure we _want_ to send one, in fact.

I think the intent was to re-route IO-completion interrupts to whatever cpu/node issued the IO with the idea that that cpu/node has the page hottest etc. and transferring the completion is cheaper than bouncing the page.

Since that would be relaying hardware interrupts, there's nothing much you can do about the rate, or something, that's up to the firmware on $$$ scsi thing.

But Jens already said that that path was using the __ variant and providing its own csds, the kmalloc isn't needed there, so it might all be moot.

Quoted 2 lines

But that's a secondary issue, and isn't a correctness thing, just a "do we really need three different allocations?" musing..

Nick, Jens, I was under the presumption that the kmalloc was needed for something other than failing to deadlock, happen to remember what?

#50 lore raw

Re: [PATCH -v3] use per cpu data for single cpu ipi calls

Quoted 7 lines · Peter Zijlstra
Quoted 2 lines

If another CPU hasn't even received its IPI before the same CPU sends the next one, I'm not sure we _want_ to send one, in fact.

I think the intent was to re-route IO-completion interrupts to whatever cpu/node issued the IO with the idea that that cpu/node has the page hottest etc. and transferring the completion is cheaper than bouncing the page.

Correct

Quoted 7 lines

Since that would be relaying hardware interrupts, there's nothing much you can do about the rate, or something, that's up to the firmware on $$$ scsi thing.

But Jens already said that that path was using the __ variant and providing its own csds, the kmalloc isn't needed there, so it might all be moot.

In fact the block layer already does attempt to do what Linus describes. We queue the events for the target cpu, and then do:

        local_irq_save(flags);
        list = &__get_cpu_var(blk_cpu_done);
        list_add_tail(&rq->csd.list, list);

        if (list->next == &rq->csd.list)
                raise_softirq_irqoff(BLOCK_SOFTIRQ);

thus only triggering a new softirq interrupt, if the preceeding one hasn't run already. So this is done for the block layer trigger_softirq() part, but could be provided by the lower layer as well instead.

Quoted 5 lines
Quoted 2 lines

But that's a secondary issue, and isn't a correctness thing, just a "do we really need three different allocations?" musing..

Nick, Jens, I was under the presumption that the kmalloc was needed for something other than failing to deadlock, happen to remember what?

As far as I remember, it was just the way to allocate memory for the non-wait case. The per-cpu single csd will limit you to a single pending entry on the cpu queue, you could have more (like the block layer will do) and get a nice batching effect for ipi busy workloads instead of a 1:1 mapping between work and ipi's fired.

Signature · 1 line
Jens Axboe
#51 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

In reply to Linus Torvalds
Quoted 4 lines · Linus Torvalds

And are you really sure it cannot be called from within interrupts? I'm finding a lot of callers of smp_call_function_single(), and while I couldn't find any that look like interrupts, I also couldn't find any indication that it never happens.

smp_call_function_single() must not be called from irqs-off code - and that implicitly includes most IRQ handlers as well. (most of which run with hardirqs off)

We check for that via:

        /* Can deadlock when called with interrupts disabled */
        WARN_ON(irqs_disabled());

[ although it should probably be extended to '&& !in_interrupt()' as well,
to cover the subset of IRQ handlers running with irqs enabled - which is small but nonzero. It would also cover softirqs. ]

There are 3 reasons why sending IPIs from an irqs off critical section is a bad idea currently:

1) the implementation is deadlockable as you noted. That is self-inflicted stupidity and fixable.

2) the _concept_ of two CPUs sending IPIs to each other at once and expecting them to be handled and then waiting for them is a deadlock. We could allow async IPIs from irqs-off sections, but isnt that a too narrow special-case?

3) the third reason is nasty: the act of sending an IPI on x86 hardware needs to happen with interrupts enabled. In the lowlevel IPI sending code we first poll the hardware whether it's ready to accept new IPIs:
via apic_wait_icr_idle().

There've been incidents in the past where the ICR-ready (Interrupt Command Register - ready) bit would deadlock the box in certain situations (usually with wackier APIC implementations and if there's too many IPIs 'in flight' and the only way to make progress is to allow IPIs to happen locally - i.e. to have irqs on), if the IPI was sent from an irqs-off section.

So i'm not sure we could relax things here without expecting too much of the hardware.

What i like least about kernel/smp.c is the kmalloc(GFP_ATOMIC) - and we had to add that in a late -rc for an essential bugfix.

IMO that kmalloc() has "layering violation" written all over it. It turns the pure act of 'sending messages' into a conceptually heavy and wide facility. Is the buffering of async messages really such a big deal in practice? Does anyone have any numbers?

Btw., there _is_ a relatively atomic, safe and instantaneous way of sending IPIs on x86: sending NMIs. But that has its own host of issues both on the hardware and on the software side ...

Ingo

#52 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

In reply to Linus Torvalds
Quoted 11 lines · On Friday 30 January 2009 04:38:23 Linus Torvalds wrote:
Quoted 2 lines · Steven Rostedt

Actually, we are locking against the destination CPU.

Oh.

THAT'S JUST INCOMPETENT.

What the *fuck* is the point of having per-CPU data, and then using it for the wrong CPU?

Maybe we made it too easy to declare and use per-cpu data?

Could we use an nr_cpu_ids array? Yes, it needs alloc at boot somewhere, but
it avoids collateral damage to other percpu data (and please don't suggest DEFINE_PER_CPU_SHARED_ALIGNED: that's just antisocial).

Thanks,
Rusty.

#53 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

In reply to Linus Torvalds
Quoted 22 lines · Linus Torvalds
Quoted 7 lines · Steven Rostedt

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

That spinlock cannot be right. It is provably wrong for so many reasons..

Think about it. We're talking about a per-CPU lock, which already makes no
sense: we're only locking against our own CPU, and we've already disabled preemption for totally unrelated reasons.

And the only way locking can make sense against our own CPU is if we lock against interrupts - but the lock isn't actually irq-safe, so if you are trying to lock against interrupts, you are (a) doing it wrong (you should disable interrupts, not use a spinlock) and (b) causing a deadlock if it ever happens.

kernel/smp.c int smp_call_function_single(int cpu, void (*func) (void *info), void *info, · line 268

Quoted 8 lines
kernel/smp.c +8 -0
+                       else {
+                               data = &per_cpu(csd_data, cpu);
+                               spin_lock(&per_cpu(csd_data_lock, cpu));
+                               while (data->flags & CSD_FLAG_LOCK)
+                                       cpu_relax();
+                               data->flags = CSD_FLAG_LOCK;
+                               spin_unlock(&per_cpu(csd_data_lock, cpu));
+                       }

I think your argument would hold if he did:

  data = &__get_cpu_var(csd_data);

But now he's actually grabbing the remote cpu's csd, and thus needs atomicy around that remote csd -- which two cpus could contend for.

#54 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Quoted 32 lines · Peter Zijlstra
Quoted 22 lines · Linus Torvalds
Quoted 7 lines · Steven Rostedt

The caller must wait till the LOCK bit is cleared before setting it. When it is cleared, there is no IPI function using it. A spinlock is used to synchronize the setting of the bit between callers. Since only one callee can be called at a time, and it is the only thing to clear it, the IPI does not need to use any locking.

That spinlock cannot be right. It is provably wrong for so many reasons..

Think about it. We're talking about a per-CPU lock, which already makes no
sense: we're only locking against our own CPU, and we've already disabled preemption for totally unrelated reasons.

And the only way locking can make sense against our own CPU is if we lock against interrupts - but the lock isn't actually irq-safe, so if you are trying to lock against interrupts, you are (a) doing it wrong (you should disable interrupts, not use a spinlock) and (b) causing a deadlock if it ever happens.

Review

Quoted 8 lines
(quoted diff) +8 -0
+                       else {
+                               data = &per_cpu(csd_data, cpu);
+                               spin_lock(&per_cpu(csd_data_lock, cpu));
+                               while (data->flags & CSD_FLAG_LOCK)
+                                       cpu_relax();
+                               data->flags = CSD_FLAG_LOCK;
+                               spin_unlock(&per_cpu(csd_data_lock, cpu));
+                       }
Quoted 6 lines

I think your argument would hold if he did:

  data = &__get_cpu_var(csd_data);

But now he's actually grabbing the remote cpu's csd, and thus needs atomicy around that remote csd -- which two cpus could contend for.

So the below should do

---
 kernel/smp.c |    6 +-----
 1 files changed, 1 insertions(+), 5 deletions(-)
kernel/smp.c +1 -5
index 9bce851..9eead6c 100644
@@ -201,8 +201,6 @@ void generic_smp_call_function_single_interrupt(void)
 }
 
 static DEFINE_PER_CPU(struct call_single_data, csd_data);
-static DEFINE_PER_CPU(spinlock_t, csd_data_lock) =
-	__SPIN_LOCK_UNLOCKED(csd_lock);
 
 /*
  * smp_call_function_single - Run a function on a specific CPU
@@ -259,12 +257,10 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 			if (data)
 				data->flags = CSD_FLAG_ALLOC;
 			else {
-				data = &per_cpu(csd_data, cpu);
-				spin_lock(&per_cpu(csd_data_lock, cpu));
+				data = &per_cpu(csd_data, me);
 				while (data->flags & CSD_FLAG_LOCK)
 					cpu_relax();
 				data->flags = CSD_FLAG_LOCK;
-				spin_unlock(&per_cpu(csd_data_lock, cpu));
 			}
 		} else {
 			data = &d;
#55 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

Quoted 41 lines · Peter Zijlstra
Quoted 11 lines

Review

Quoted 10 lines
(quoted diff) +8 -0
+                       else {
+                               data = &per_cpu(csd_data, cpu);
+                               spin_lock(&per_cpu(csd_data_lock, cpu));
+                               while (data->flags & CSD_FLAG_LOCK)
+                                       cpu_relax();
+                               data->flags = CSD_FLAG_LOCK;
+                               spin_unlock(&per_cpu(csd_data_lock, cpu));
+                       }
Quoted 6 lines

I think your argument would hold if he did:

  data = &__get_cpu_var(csd_data);

But now he's actually grabbing the remote cpu's csd, and thus needs atomicy around that remote csd -- which two cpus could contend for.

So the below should do

---
 kernel/smp.c |    6 +-----
 1 files changed, 1 insertions(+), 5 deletions(-)
kernel/smp.c +0 -2
index 9bce851..9eead6c 100644
@@ -201,8 +201,6 @@ void generic_smp_call_function_single_interrupt(void)
 }
 
 static DEFINE_PER_CPU(struct call_single_data, csd_data);
-static DEFINE_PER_CPU(spinlock_t, csd_data_lock) =
-	__SPIN_LOCK_UNLOCKED(csd_lock);
 
 /*
  * smp_call_function_single - Run a function on a specific CPU
@@ -259,12 +257,10 @@ int smp_call_function_single(int cpu, void (*func) (void *info), void *info,
 			if (data)
 				data->flags = CSD_FLAG_ALLOC;
 			else {

kernel/smp.c int smp_call_function_single(int cpu, void (*func) (void *info), void *info, · line 266

Quoted 10 lines
kernel/smp.c +1 -3
-				data = &per_cpu(csd_data, cpu);
-				spin_lock(&per_cpu(csd_data_lock, cpu));
+				data = &per_cpu(csd_data, me);
 				while (data->flags & CSD_FLAG_LOCK)
 					cpu_relax();
 				data->flags = CSD_FLAG_LOCK;
-				spin_unlock(&per_cpu(csd_data_lock, cpu));
 			}
 		} else {
 			data = &d;

Ah, OK.

So if we just use our own CPU data, we can through away the spinlocks and just do the test ourselves.

That's even better.

Ingo, can you apply Peter's patch on top of mine.

-- Steve

Acked-by on v1 1/1
#56 lore raw

Re: [PATCH -v2] use per cpu data for single cpu ipi calls

In reply to Steven Rostedt
Quoted 6 lines · On Friday 30 January 2009 01:38:01 Steven Rostedt wrote:

The smp_call_function can be passed a wait parameter telling it to wait for all the functions running on other CPUs to complete before returning, or to return without waiting. Unfortunately, this is currently just a suggestion and not manditory. That is, the smp_call_function can decide not to return and wait instead.

I think the file could probably use some comment love and the comments made more pithy (the correct comment in the "kmalloc failed" path usually involves cussing), but we can't have everything.

Not that it matters, but since I was the last one to touch this file:

Thanks!
Rusty.