[RFC] RT-patch update to remove the global pi_lock

[Steven Rostedt <rostedt@goodmis.org>]

On Mon, 2005-08-22 at 20:33 +0200, Ingo Molnar wrote:

> any ideas how to get rid of pi_lock altogether?

I've toyed with the idea of adding another raw_spin_lock to the mutex. A
lock specific pi_lock.   Instead of grabbing a global pi_lock, grab the
pi_lock of a lock.  To modify any lock w.r.t PI, you must first grab all
the lock's pi_locks being referenced.

The idea stems from the fact that the kernel must order its taking of
locks to prevent deadlocks.  This way the order of locks that are taken
are also always in order. 

So if you have the following case:

P1 blocked_on L1 owned_by P2 blocked_on L2 owned_by P3 ...

The L1, L2, L3 ... must always be in the same order, otherwise the
kernel itself can have a deadlock.

OK, let me prove this (for myself as well ;-)

Lets go by contradiction.

If we assume that the locks _can_ be in different orders and that no
deadlock would result.

So we could have:

P1 blocked_on L1 owned_by P2 ... blocked on Ln owned_by Pn+1

According to our assumtion, there can exist another list here where

Lx owned_by Px+1 ... blocked_on Ly owned by Py+1 

where y < x <= n  and 1 <= y < x

This means that there exists a process that owns Lx and is blocked on a
lock Ly, and also this means that there's some process that owns Ly is
blocked on Lx. This is a deadlock!

So knowing that this list of locks will always be in the same order,
than there must be someway to capitalize on that and take just the locks
of the locks used instead of a global one.

I haven't fully looked into this idea, but there might be something to
it.  I'm sure it will be complex, and perhaps slow things down on a 2x
system. But it should be scalable, since you are only taking locks that
are being used, and not a global one.

What do you guys think? 

-- Steve