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