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

[Steven Rostedt <rostedt@goodmis.org>]

On Mon, 2005-08-22 at 21:32 -0400, Steven Rostedt wrote:

> 
> God, I think a thesis can be made out of this.  Well, let me start
> coding, since I'm one of those that write code better than I design.
> I'm a Spiral type of guy, not a Waterfall one ;-)
> Code crap, write about it, recode it as gold!
> 

I'm really made a mess of the code now and having a lot of fun ;-)

I think this can be pulled off, but I'm seeing that the easiest way is
to do the grabbing of locks with lock -> owner -> lock -> owner ...

So if you have the chain.

P1 X=> L1 -> P2 X=> L2 X=> P3

You would always need to grab the locks in this order:

P1->pi_lock, L1->wait_lock, P2->pi_lock, L2->wait_lock, P3->pi_lock

So on a __down, if you don't get the lock, this makes for easy
transition in the pi_setprio.  You have the current->pi_lock, and then
grab the lock->wait_lock that current is blocked on.  In the loop, you
need to first grab p->wait_lock, to prevent the race with p->blocked_on
and setting it up.  Having to get the lock->wait_lock first would mean
there's a race to get blocked_on, and knowing what it was blocked on.

Now the PITA is with the __up.  Here we have the lock, and we need to
change the owner.  So we need to unlock the lock (as well as the current
owner pi_lock), before giving it to the new owner.  So the race is, if
you have the lock->wait_lock, find the new owner, then unlock the
lock->wait_lock, lock new_owner->pi_lock and then grab the
lock->wait_lock again, in this time a higher priority process could have
come and blocked on this lock.  So the new_owner should really be the
high priority process that just came in. This skips by the pending owner
algorithm.

There's more than one solution to solve this.  The easy, inefficient
way, is to have a test to see if this occurred and try again. But I was
thinking of the following.

When grabbing a lock, you check if there are waiters (although there may
not be an owner or even a pending owner), if you are the highest
priority process, grab the lock and go, otherwise, just add yourself to
the waiting list (and perhaps the pi_list).  So when the original owner
giving up the lock finally runs, it won't need to do anymore work.  If
the lock is owned, then it just unlocks everything, and then it's
someone elses problem.  

The situation could even occur that the higher priority process that
came in and took the lock gave it back to the "new" guy, and the lock
isn't owned at all.  So a simple check of, is the "new" guy still
blocked on the lock and the lock is not owned should be good enough to
finish the change owner job.

It's all complex, but what did you expect when removing a global lock
that makes life simple :-)

-- Steve

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