Re: interrupt checks for spinlocks

Re: interrupt checks for spinlocks

[Pete Zaitcev]

> Date: Sun, 3 Nov 2002 16:28:13 -0800
> From: William Lee Irwin III <wli@holomorphy.com>

> >> (1) check that spinlocks are not taken in interrupt context without
> >> 	interrupts disabled

> > Bill, why is this bad? I routinely use this technique.
> > -- Pete
> 
> If you receive the same interrupt on the same cpu and re-enter code
> that does that, you will deadlock.

How would that happen? I thought it was not possible to re-enter
an interrupt, and that it was pretty fundamental for Linux.
When did we allow it, and what are implications for architectures?

-- Pete

Re: interrupt checks for spinlocks

[William Lee Irwin III]

From: William Lee Irwin III <wli@holomorphy.com>
>>>> (1) check that spinlocks are not taken in interrupt context without
>>>> 	interrupts disabled

At some point in the past, Pete Zaitcev wrote:
>>> Bill, why is this bad? I routinely use this technique.

From: William Lee Irwin III <wli@holomorphy.com>
>> If you receive the same interrupt on the same cpu and re-enter code
>> that does that, you will deadlock.

On Sun, Nov 03, 2002 at 07:42:49PM -0500, Pete Zaitcev wrote:
> How would that happen? I thought it was not possible to re-enter
> an interrupt, and that it was pretty fundamental for Linux.
> When did we allow it, and what are implications for architectures?

This non-reentrant stuff hurts my head. Another patch down the
toilet, I guess.


Bill

Re: interrupt checks for spinlocks

[Robert Love]

On Sun, 2002-11-03 at 19:53, William Lee Irwin III wrote:

> This non-reentrant stuff hurts my head. Another patch down the
> toilet, I guess.

No, I think you have a good idea.  Pete is right, though, the current
interrupt is disabled... but normally the other interrupts are still
enabled.

Your ideas #2, #3, and #4 are good.

Because once the lock is tainted, you still want to ensure process
context disables interrupts before grabbing the lock.

	Robert Love

Re: interrupt checks for spinlocks

[William Lee Irwin III]

On Sun, 2002-11-03 at 19:53, William Lee Irwin III wrote:
>> This non-reentrant stuff hurts my head. Another patch down the
>> toilet, I guess.

On Sun, Nov 03, 2002 at 08:18:04PM -0500, Robert Love wrote:
> No, I think you have a good idea.  Pete is right, though, the current
> interrupt is disabled... but normally the other interrupts are still
> enabled.
> Your ideas #2, #3, and #4 are good.
> Because once the lock is tainted, you still want to ensure process
> context disables interrupts before grabbing the lock.
> 	Robert Love

I'll go figure out why before posting a follow-up. This is not doing
what I wanted it to because the only one I originally wanted was (1),
having to do with interrupt-time recursion on rwlocks and writer
starvation caused by it.


Bill

Re: interrupt checks for spinlocks

[Robert Love]

On Sun, 2002-11-03 at 20:42, William Lee Irwin III wrote:

> I'll go figure out why before posting a follow-up. This is not doing
> what I wanted it to because the only one I originally wanted was (1),
> having to do with interrupt-time recursion on rwlocks and writer
> starvation caused by it.

You can do #1, but you need to figure out if your interrupt is the only
interrupt using the lock or not (possibly hard).

In other words, a lock unique to your interrupt handler does not need to
disable interrupts (since only that handler can grab the lock and it is
disabled).

If other handlers can grab the lock, interrupts need to be disabled.

So a test of irqs_disabled() would show a false-positive in the first
case.  No easy way to tell..

	Robert Love

Re: interrupt checks for spinlocks

[William Lee Irwin III]

On Sun, 2002-11-03 at 20:42, William Lee Irwin III wrote:
>> I'll go figure out why before posting a follow-up. This is not doing
>> what I wanted it to because the only one I originally wanted was (1),
>> having to do with interrupt-time recursion on rwlocks and writer
>> starvation caused by it.

On Sun, Nov 03, 2002 at 10:01:24PM -0500, Robert Love wrote:
> You can do #1, but you need to figure out if your interrupt is the only
> interrupt using the lock or not (possibly hard).
> In other words, a lock unique to your interrupt handler does not need to
> disable interrupts (since only that handler can grab the lock and it is
> disabled).
> If other handlers can grab the lock, interrupts need to be disabled.
> So a test of irqs_disabled() would show a false-positive in the first
> case.  No easy way to tell..
> 	Robert Love

Sounds like I rip out that check and ignore the fact it's useless for
its original intended purpose. No matter, it'll turn up something.

Incoming.

Bill

Re: interrupt checks for spinlocks

[William Lee Irwin III]

On Sun, Nov 03, 2002 at 10:01:24PM -0500, Robert Love wrote:
> You can do #1, but you need to figure out if your interrupt is the only
> interrupt using the lock or not (possibly hard).
> In other words, a lock unique to your interrupt handler does not need to
> disable interrupts (since only that handler can grab the lock and it is
> disabled).
> If other handlers can grab the lock, interrupts need to be disabled.
> So a test of irqs_disabled() would show a false-positive in the first
> case.  No easy way to tell..
> 	Robert Love

Attempt #1:



===== include/linux/spinlock.h 1.18 vs edited =====
--- 1.18/include/linux/spinlock.h	Sun Aug 25 10:25:45 2002
+++ edited/include/linux/spinlock.h	Sun Nov  3 19:21:44 2002
@@ -38,6 +38,44 @@
 #include <asm/spinlock.h>
 
 /*
+ * if a lock is ever taken in interrupt context, it must always be
+ * taken with interrupts disabled. If a locking call is made that
+ * unconditionally disables and then re-enables interrupts, it must
+ * be made with interrupts enabled.
+ */
+#ifndef irq_tainted_lock
+#define irq_tainted_lock(lock)	0 
+#endif
+
+#ifndef irq_taint_lock
+#define irq_taint_lock(lock)	do { } while (0)
+#define
+
+#ifndef CONFIG_DEBUG_SPINLOCK
+#define check_spinlock_irq(lock)		do { } while (0)
+#define check_spinlock_irqs_disabled(lock)	do { } while (0)
+#else
+#define check_spinlock_irq(lock)					\
+	do {								\
+		if (irqs_disabled()) {					\
+			printk("spinlock taken unconditionally "	\
+				"re-enabling interrupts\n");		\
+			dump_stack();					\
+		}							\
+	} while (0)
+#define check_spinlock_irqs_disabled(lock)				\
+	do {								\
+		if (in_interrupt())				\
+			irq_taint_lock(lock);				\
+		else if (irq_tainted_lock(lock)) {			\
+			printk("spinlock taken in process context "	\
+				"without disabling interrupts\n");	\
+			dump_stack();					\
+		}							\
+	} while (0)
+#endif
+
+/*
  * !CONFIG_SMP and spin_lock_init not previously defined
  * (e.g. by including include/asm/spinlock.h)
  */
@@ -87,6 +125,7 @@
  */
 #define spin_lock(lock)	\
 do { \
+	check_spinlock_irqs_disabled(lock); \
 	preempt_disable(); \
 	_raw_spin_lock(lock); \
 } while(0)
@@ -102,6 +141,7 @@
 
 #define read_lock(lock)	\
 do { \
+	check_spinlock_irqs_disabled(lock); \
 	preempt_disable(); \
 	_raw_read_lock(lock); \
 } while(0)
@@ -114,6 +154,7 @@
 
 #define write_lock(lock) \
 do { \
+	check_spinlock_irqs_disabled(lock); \
 	preempt_disable(); \
 	_raw_write_lock(lock); \
 } while(0)
@@ -136,6 +177,7 @@
 
 #define spin_lock_irq(lock) \
 do { \
+	check_spinlock_irq(lock); \
 	local_irq_disable(); \
 	preempt_disable(); \
 	_raw_spin_lock(lock); \
@@ -157,6 +199,7 @@
 
 #define read_lock_irq(lock) \
 do { \
+	check_spinlock_irq(lock); \
 	local_irq_disable(); \
 	preempt_disable(); \
 	_raw_read_lock(lock); \
@@ -178,6 +221,7 @@
 
 #define write_lock_irq(lock) \
 do { \
+	check_spinlock_irq(lock); \
 	local_irq_disable(); \
 	preempt_disable(); \
 	_raw_write_lock(lock); \

Re: interrupt checks for spinlocks

[Zwane Mwaikambo]

On 3 Nov 2002, Robert Love wrote:

> In other words, a lock unique to your interrupt handler does not need to
> disable interrupts (since only that handler can grab the lock and it is
> disabled).
> 
> If other handlers can grab the lock, interrupts need to be disabled.

The only way would be running with SA_INTERRUPT for that isr and any 
others on that line which might contend for the same lock. Determining 
otherwise seems like too much trouble, and anyway i can't recall ever 
seeing such a scenario in drivers/ Basically i think we should forget 
about option 1.

	Zwane
-- 
function.linuxpower.ca

interrupt checks for spinlocks

[William Lee Irwin III]

I recently thought about interrupt disablement and locking again, or
at least such as has gone about in various places, and I got scared.

Hence, a wee addition to CONFIG_DEBUG_SPINLOCK:

(1) check that spinlocks are not taken in interrupt context without
	interrupts disabled
(2) taint spinlocks taken in interrupt context
(3) check for tainted spinlocks taken without interrupts disabled
(4) check for spinlocking calls unconditionally disabling (and
	hence later re-enabling) interrupts with interrupts disabled

The only action taken is printk() and dump_stack(). No arch code has
been futzed with to provide irq tainting yet. Looks like a good way
to shake out lurking bugs to me (somewhat like may_sleep() etc.).

vs. 2.5.x-bk as of 2PM PST 3 Nov

Bill



diff -urN linux-virgin/include/linux/spinlock.h linux-wli/include/linux/spinlock.h
--- linux-virgin/include/linux/spinlock.h	Sun Aug 25 10:25:45 2002
+++ linux-wli/include/linux/spinlock.h	Sun Nov  3 13:58:47 2002
@@ -38,6 +38,48 @@
 #include <asm/spinlock.h>
 
 /*
+ * if a lock is ever taken in interrupt context, it must always be
+ * taken with interrupts disabled. If a locking call is made that
+ * unconditionally disables and then re-enables interrupts, it must
+ * be made with interrupts enabled.
+ */
+#ifndef irq_tainted_lock
+#define irq_tainted_lock(lock)	0 
+#endif
+
+#ifndef irq_taint_lock
+#define irq_taint_lock(lock)	do { } while (0)
+#define
+
+#ifndef CONFIG_DEBUG_SPINLOCK
+#define check_spinlock_irq(lock)		do { } while (0)
+#define check_spinlock_irqs_disabled(lock)	do { } while (0)
+#else
+#define check_spinlock_irq(lock)					\
+	do {								\
+		if (irqs_disabled()) {					\
+			printk("spinlock taken unconditionally "	\
+				"re-enabling interrupts\n");		\
+			dump_stack();					\
+		}							\
+	} while (0)
+#define check_spinlock_irqs_disabled(lock)				\
+	do {								\
+		if (in_interrupt() && !irqs_disabled()) {		\
+			printk("spinlock taken in interrupt context "	\
+				"without disabling interrupts\n");	\
+			dump_stack();					\
+		} else if (in_interrupt())				\
+			irq_taint_lock(lock);				\
+		else if (irq_tainted_lock(lock)) {			\
+			printk("spinlock taken in process context "	\
+				"without disabling interrupts\n");	\
+			dump_stack();					\
+		}							\
+	} while (0)
+#endif
+
+/*
  * !CONFIG_SMP and spin_lock_init not previously defined
  * (e.g. by including include/asm/spinlock.h)
  */
@@ -87,6 +129,7 @@
  */
 #define spin_lock(lock)	\
 do { \
+	check_spinlock_irqs_disabled(lock); \
 	preempt_disable(); \
 	_raw_spin_lock(lock); \
 } while(0)
@@ -102,6 +145,7 @@
 
 #define read_lock(lock)	\
 do { \
+	check_spinlock_irqs_disabled(lock); \
 	preempt_disable(); \
 	_raw_read_lock(lock); \
 } while(0)
@@ -114,6 +158,7 @@
 
 #define write_lock(lock) \
 do { \
+	check_spinlock_irqs_disabled(lock); \
 	preempt_disable(); \
 	_raw_write_lock(lock); \
 } while(0)
@@ -136,6 +181,7 @@
 
 #define spin_lock_irq(lock) \
 do { \
+	check_spinlock_irq(lock); \
 	local_irq_disable(); \
 	preempt_disable(); \
 	_raw_spin_lock(lock); \
@@ -157,6 +203,7 @@
 
 #define read_lock_irq(lock) \
 do { \
+	check_spinlock_irq(lock); \
 	local_irq_disable(); \
 	preempt_disable(); \
 	_raw_read_lock(lock); \
@@ -178,6 +225,7 @@
 
 #define write_lock_irq(lock) \
 do { \
+	check_spinlock_irq(lock); \
 	local_irq_disable(); \
 	preempt_disable(); \
 	_raw_write_lock(lock); \

Re: interrupt checks for spinlocks

[Davide Libenzi]

On Sun, 3 Nov 2002, William Lee Irwin III wrote:

> I recently thought about interrupt disablement and locking again, or
> at least such as has gone about in various places, and I got scared.
>
> Hence, a wee addition to CONFIG_DEBUG_SPINLOCK:
>
> (1) check that spinlocks are not taken in interrupt context without
> 	interrupts disabled
> (2) taint spinlocks taken in interrupt context
> (3) check for tainted spinlocks taken without interrupts disabled
> (4) check for spinlocking calls unconditionally disabling (and
> 	hence later re-enabling) interrupts with interrupts disabled
>
> The only action taken is printk() and dump_stack(). No arch code has
> been futzed with to provide irq tainting yet. Looks like a good way
> to shake out lurking bugs to me (somewhat like may_sleep() etc.).

Wouldn't it be interesting to keep a ( per task ) list of acquired
spinlocks to be able to diagnose cross locks in case of stall ?
( obviously under CONFIG_DEBUG_SPINLOCK )



- Davide

Re: interrupt checks for spinlocks

[William Lee Irwin III]

On Sun, 3 Nov 2002, William Lee Irwin III wrote:
[...]
>> The only action taken is printk() and dump_stack(). No arch code has
>> been futzed with to provide irq tainting yet. Looks like a good way
>> to shake out lurking bugs to me (somewhat like may_sleep() etc.).

On Sun, Nov 03, 2002 at 04:15:46PM -0800, Davide Libenzi wrote:
> Wouldn't it be interesting to keep a ( per task ) list of acquired
> spinlocks to be able to diagnose cross locks in case of stall ?
> ( obviously under CONFIG_DEBUG_SPINLOCK )

That would appear to require cycle detection, but it sounds like a
potential breakthrough usage of graph algorithms in the kernel.
(I've always been told graph algorithms would come back to haunt me.)
Or maybe not, deadlock detection has been done before.

A separate patch/feature/whatever for deadlock detection could do that
nicely, though. What I've presented here is meant only to flag far more
trivial errors with interrupt enablement/disablement than the full
deadlock detection problem.


Bill

Re: interrupt checks for spinlocks

[Davide Libenzi]

On Sun, 3 Nov 2002, William Lee Irwin III wrote:

> On Sun, 3 Nov 2002, William Lee Irwin III wrote:
> [...]
> >> The only action taken is printk() and dump_stack(). No arch code has
> >> been futzed with to provide irq tainting yet. Looks like a good way
> >> to shake out lurking bugs to me (somewhat like may_sleep() etc.).
>
> On Sun, Nov 03, 2002 at 04:15:46PM -0800, Davide Libenzi wrote:
> > Wouldn't it be interesting to keep a ( per task ) list of acquired
> > spinlocks to be able to diagnose cross locks in case of stall ?
> > ( obviously under CONFIG_DEBUG_SPINLOCK )
>
> That would appear to require cycle detection, but it sounds like a
> potential breakthrough usage of graph algorithms in the kernel.
> (I've always been told graph algorithms would come back to haunt me.)
> Or maybe not, deadlock detection has been done before.
>
> A separate patch/feature/whatever for deadlock detection could do that
> nicely, though. What I've presented here is meant only to flag far more
> trivial errors with interrupt enablement/disablement than the full
> deadlock detection problem.

It's not realy a graph Bill.  Each task has a list of acquired locks (
by address ). You keep __LINE__ and __FILE__ with you list items. When
there's a deadlock you'll have somewhere :

   TSK#N	TSK#M
   -------------
   ...		...
   LCK#I	LCK#J
   ...		...
-> LCK#J	LCK#I

Then with a SysReq key you dump the list of acquired locks for each task
who's spinning for a lock. IMO it might be usefull ...



- Davide

Re: interrupt checks for spinlocks

[William Lee Irwin III]

On Sun, Nov 03, 2002 at 05:39:29PM -0800, Davide Libenzi wrote:
> It's not realy a graph Bill.  Each task has a list of acquired locks (
> by address ). You keep __LINE__ and __FILE__ with you list items. When
> there's a deadlock you'll have somewhere :
>    TSK#N	TSK#M
>    -------------
>    ...		...
>    LCK#I	LCK#J
>    ...		...
> -> LCK#J	LCK#I
> Then with a SysReq key you dump the list of acquired locks for each task
> who's spinning for a lock. IMO it might be usefull ...

Then you had something different in mind. I *thought* you meant
maintaining a graph's arcs and dumping the specific deadlocking
processes and their acquired locks at failure time. This scheme
with limited reporting requires less work/code, but is still beyond
the scope of what I was doing.


Bill

Re: interrupt checks for spinlocks

[Randy.Dunlap]

On Sun, 3 Nov 2002, Davide Libenzi wrote:

| On Sun, 3 Nov 2002, William Lee Irwin III wrote:
|
| > On Sun, 3 Nov 2002, William Lee Irwin III wrote:
| > [...]
| > >> The only action taken is printk() and dump_stack(). No arch code has
| > >> been futzed with to provide irq tainting yet. Looks like a good way
| > >> to shake out lurking bugs to me (somewhat like may_sleep() etc.).
| >
| > On Sun, Nov 03, 2002 at 04:15:46PM -0800, Davide Libenzi wrote:
| > > Wouldn't it be interesting to keep a ( per task ) list of acquired
| > > spinlocks to be able to diagnose cross locks in case of stall ?
| > > ( obviously under CONFIG_DEBUG_SPINLOCK )
| >
| > That would appear to require cycle detection, but it sounds like a
| > potential breakthrough usage of graph algorithms in the kernel.
| > (I've always been told graph algorithms would come back to haunt me.)
| > Or maybe not, deadlock detection has been done before.
| >
| > A separate patch/feature/whatever for deadlock detection could do that
| > nicely, though. What I've presented here is meant only to flag far more
| > trivial errors with interrupt enablement/disablement than the full
| > deadlock detection problem.
|
| It's not realy a graph Bill.  Each task has a list of acquired locks (
| by address ). You keep __LINE__ and __FILE__ with you list items. When
| there's a deadlock you'll have somewhere :
|
|    TSK#N	TSK#M
|    -------------
|    ...		...
|    LCK#I	LCK#J
|    ...		...
| -> LCK#J	LCK#I
|
| Then with a SysReq key you dump the list of acquired locks for each task
| who's spinning for a lock. IMO it might be usefull ...

What's a task in this context?  Are we (you) talking about
kernel threads/drivers etc. or userspace?

-- 
~Randy
"I'm a healthy mushroom."

Re: interrupt checks for spinlocks

[Davide Libenzi]

On Sun, 3 Nov 2002, Randy.Dunlap wrote:

> | It's not realy a graph Bill.  Each task has a list of acquired locks (
> | by address ). You keep __LINE__ and __FILE__ with you list items. When
> | there's a deadlock you'll have somewhere :
> |
> |    TSK#N	TSK#M
> |    -------------
> |    ...		...
> |    LCK#I	LCK#J
> |    ...		...
> | -> LCK#J	LCK#I
> |
> | Then with a SysReq key you dump the list of acquired locks for each task
> | who's spinning for a lock. IMO it might be usefull ...
>
> What's a task in this context?  Are we (you) talking about
> kernel threads/drivers etc. or userspace?

Hi Randy,

a task here is anything you can identify with a task_struct*



- Davide

Re: interrupt checks for spinlocks

[Alan Cox]

On Mon, 2002-11-04 at 00:39, William Lee Irwin III wrote:
> That would appear to require cycle detection, but it sounds like a
> potential breakthrough usage of graph algorithms in the kernel.
> (I've always been told graph algorithms would come back to haunt me.)
> Or maybe not, deadlock detection has been done before.

For a spinlock it doesn't appear to be insoluble.

Suppose we do the following

For
	spin_lock(&foo)

	current->waiting = foo;
	foo->waiting += current;

	If foo is held
		Check if foo is on current->locks
			If it is then we shot ourself in the foot
		Check if any member of foo->waiting is waiting on a lock
			we hold (in current->locks)
			If it is then we shot ourselves in both feet
		
	When we get the lock
	foo->waiting -= current;
	foo->held = current;
	current->locks = foo;

For
	spin_unlock(&foo)
	
	if(current->locks != foo)
		We released the locks in the wrong order

	remoe foo from current->locks



Alan