LinuxLists.cc - [PATCH] Priority Lists for the RT mutex

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

* Daniel Walker <[email protected]> wrote:

> This patch adds the priority list data structure from Inaky
> Perez-Gonzalez to the Preempt Real-Time mutex.

this one looks really clean.

it makes me wonder, what is the current status of fusyn's? Such a light
datastructure would be much more mergeable upstream than the former
100-queues approach.

Ingo

2005-04-08 08:15:12

by Sven-Thorsten Dietrich

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Fri, 2005-04-08 at 08:28 +0200, Ingo Molnar wrote:
> * Daniel Walker <[email protected]> wrote:
>
> > This patch adds the priority list data structure from Inaky
> > Perez-Gonzalez to the Preempt Real-Time mutex.
>
> this one looks really clean.
>
> it makes me wonder, what is the current status of fusyn's? Such a light
> datastructure would be much more mergeable upstream than the former
> 100-queues approach.

Ingo,

Joe Korty has been doing a lot of work on Fusyn recently.

Fusyn is now a generic implementation, similar to the RT mutex. SMP
scalability is somewhat better for decoupled locks on PI (last I
checked). It has the extra bulk required to support user space.

The major issue that concerns the Fusym and the real-time patch is that
merging the kernel portion of Fusyn creates a collision of redundant PI
implementations with respect to the RT mutex.

The issues are outlined here:

http://developer.osdl.org/dev/mutexes/

There are a few mistakes on the page, (RT mutex does not do priority
ceiling), but for the most part the info is current.

If the RT mutex could be exposed in non PREEMPT_RT configurations,
the fulock portion could be superseded by the RT mutex, and the
remaining pieces merged in. Or vice versa.

We discussed the scenarios recently, any guidance you can offer to help
us out would be greatly appreciated.

http://lists.osdl.org/pipermail/robustmutexes/2005-April/000532.html

Sven

2005-04-08 17:11:35

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Thu, 2005-04-07 at 23:28, Ingo Molnar wrote:

> this one looks really clean.
>
> it makes me wonder, what is the current status of fusyn's? Such a light
> datastructure would be much more mergeable upstream than the former
> 100-queues approach.

Inaky was telling me that 100 queues approach is two years old.

The biggest problem is that fusyn has it's own PI system .. So it's not
clear if that will work with the RT mutex,. I was thinking the PI stuff
could be made generic so, fusyn, maybe futex, can use it also .

Daniel

2005-04-08 21:27:39

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

>From: Daniel Walker [mailto:[email protected]]
>
>On Thu, 2005-04-07 at 23:28, Ingo Molnar wrote:
>
>> this one looks really clean.
>>
>> it makes me wonder, what is the current status of fusyn's? Such a
light
>> datastructure would be much more mergeable upstream than the former
>> 100-queues approach.
>
> Inaky was telling me that 100 queues approach is two years old.
>
>The biggest problem is that fusyn has it's own PI system .. So it's not
>clear if that will work with the RT mutex,. I was thinking the PI stuff
>could be made generic so, fusyn, maybe futex, can use it also .

I concur with Daniel. If we can decide how to deal with that (toss
one out, keep one, merge them, whatever), we could reuse all the user
space glue that is the hardest part to get right.

Current tip of development has some issues with conditional variables
and broadcasts (requeue stuff) that I need to sink my teeth in. Joe
Korty is fixing up a lot of corner cases I wasn't catching, but
other than that is doing fine.

How long ago since you saw it? I also implemented the futex redirection
stuff we discussed some months ago.

-- Inaky

2005-04-08 22:54:05

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

On Fri, 2005-04-08 at 14:25, Perez-Gonzalez, Inaky wrote:
> I concur with Daniel. If we can decide how to deal with that (toss
> one out, keep one, merge them, whatever), we could reuse all the user
> space glue that is the hardest part to get right.

I have a preference to the Real-Time PI , but that's just cause I've
worked with it more. Ingo's really the one that should be make those
choices though, since he has the biggest influence over what goes into
sched.c ..

> Current tip of development has some issues with conditional variables
> and broadcasts (requeue stuff) that I need to sink my teeth in. Joe
> Korty is fixing up a lot of corner cases I wasn't catching, but
> other than that is doing fine.

You try to get out, and they suck you right back in.

> How long ago since you saw it? I also implemented the futex redirection
> stuff we discussed some months ago.

It's been a while since I've seen the fusyn scheduler changes. I have
the curernt fusyn CVS, I'll take a look at it.

Daniel

2005-04-08 23:08:03

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

>From: Daniel Walker [mailto:[email protected]]
>
>> Current tip of development has some issues with conditional variables
>> and broadcasts (requeue stuff) that I need to sink my teeth in. Joe
>> Korty is fixing up a lot of corner cases I wasn't catching, but
>> other than that is doing fine.
>
>You try to get out, and they suck you right back in.

Don't mention it :] That's why I want to get some more people
hooked up to this...so I can move on to do other things :)

>> How long ago since you saw it? I also implemented the futex
redirection
>> stuff we discussed some months ago.
>
>It's been a while since I've seen the fusyn scheduler changes. I have
>the curernt fusyn CVS, I'll take a look at it.

All that stuff is in futex.c; bear in mind what I said at
the confcall, it is just a hacky proof-of-concept--it doesn't
even implement the async interface.

It kind of works, but is not all that solid [last time I tried
the JVMs locked up].

-- Inaky

2005-04-10 10:53:53

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

* Daniel Walker <[email protected]> wrote:

> Description:
> This patch adds the priority list data structure from Inaky
> Perez-Gonzalez to the Preempt Real-Time mutex.

ok, i've added this patch to the -45-00 release. It's looking good on my
testsystems so far, but it will need some more testing i guess.

Ingo

2005-04-10 11:10:54

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

* Sven-Thorsten Dietrich <[email protected]> wrote:

> On Fri, 2005-04-08 at 08:28 +0200, Ingo Molnar wrote:
> > * Daniel Walker <[email protected]> wrote:
> >
> > > This patch adds the priority list data structure from Inaky
> > > Perez-Gonzalez to the Preempt Real-Time mutex.
> >
> > this one looks really clean.
> >
> > it makes me wonder, what is the current status of fusyn's? Such a light
> > datastructure would be much more mergeable upstream than the former
> > 100-queues approach.
>
> Ingo,
>
> Joe Korty has been doing a lot of work on Fusyn recently.
>
> Fusyn is now a generic implementation, similar to the RT mutex. SMP
> scalability is somewhat better for decoupled locks on PI (last I
> checked). It has the extra bulk required to support user space.
>
> The major issue that concerns the Fusym and the real-time patch is
> that merging the kernel portion of Fusyn creates a collision of
> redundant PI implementations with respect to the RT mutex.

i'd not mind merging the extra bits to PREEMPT_RT to enable fusyn's, if
they come in small, clean steps. E.g. Daniel's plist.h stuff was nice
and clean.

> There are a few mistakes on the page, (RT mutex does not do priority
> ceiling), but for the most part the info is current.

is priority ceiling coming in via some POSIX feature that fusyn's need
to address? What would be needed precisely - a way to set a priority for
a lock (independently of the owner's task priority), and let that
control the PI mechanism?

Unless i'm missing something, this could be implemented by detaching
lock->owner_prio from lock->owner - via e.g. negative values. Thus some
minimal code would check whether we need the owner's priority in the PI
logic, or the semaphore's "own" priority level.

i.e. this doesnt seem to really affect the core design of RT mutexes.

OTOH, deadlock detection is another issue. It's quite expensive and i'm
not sure we want to make it a runtime thing. But for fusyn's deadlock
detection and safe teardown on owner-exit is a must-have i suspect?

> If the RT mutex could be exposed in non PREEMPT_RT configurations, the
> fulock portion could be superseded by the RT mutex, and the remaining
> pieces merged in. Or vice versa.

sure, RT mutexes could be exposed in !PREEMPT_RT.

Ingo

2005-04-11 08:34:46

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

>From: Ingo Molnar [mailto:[email protected]]
>
>
>i'd not mind merging the extra bits to PREEMPT_RT to enable fusyn's, if
>they come in small, clean steps. E.g. Daniel's plist.h stuff was nice
>and clean.

I am finishing breaking it up in small bits so you can take a look
at it. Should be finished tomorrow noon (PST).

>is priority ceiling coming in via some POSIX feature that fusyn's need
>to address? What would be needed precisely - a way to set a priority
for
>a lock (independently of the owner's task priority), and let that
>control the PI mechanism?

Yep. It is kind of easy to do (at least in fusyns)--it is just a
matter of setting the priority of the lock, that sets the priority
of its list node.

Because the promotion code only cares about the priority of the
list node, it blends automatically in the whole scheme. The PI
code will modify the list node's priority while promoting all the
tasks affected in the ownership chain, only when the fulocks/mutexes
are PI. The PP code will modify the priority of the fulock/mutex's
list node with an special call.

[you can check for my 2004 OLS paper for a deeper explanation, or
I can extend this one, if you want].

>i.e. this doesnt seem to really affect the core design of RT mutexes.

Nope it doesn't. As I said, it is done in such a way that no
modifications are needed.

>OTOH, deadlock detection is another issue. It's quite expensive and i'm
>not sure we want to make it a runtime thing. But for fusyn's deadlock
>detection and safe teardown on owner-exit is a must-have i suspect?

Not really. Deadlock check is needed on PI, so it can be done at the
same time (you have to walk the chain anyway). In any other case, it
is an option you can request (or not).

-- Inaky

2005-04-11 08:43:40

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

* Perez-Gonzalez, Inaky <[email protected]> wrote:

> >OTOH, deadlock detection is another issue. It's quite expensive and i'm
> >not sure we want to make it a runtime thing. But for fusyn's deadlock
> >detection and safe teardown on owner-exit is a must-have i suspect?
>
> Not really. Deadlock check is needed on PI, so it can be done at the
> same time (you have to walk the chain anyway). In any other case, it
> is an option you can request (or not).

well, i was talking about the mutex code in PREEMPT_RT. There deadlock
detection is an optional debug feature. You dont _have_ to do deadlock
detection for the kernel's locks, and there's a difference in
performance.

Ingo

2005-04-11 08:50:41

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

>From: Ingo Molnar [mailto:[email protected]]
>
>* Perez-Gonzalez, Inaky <[email protected]> wrote:
>
>> >OTOH, deadlock detection is another issue. It's quite expensive and
i'm
>> >not sure we want to make it a runtime thing. But for fusyn's
deadlock
>> >detection and safe teardown on owner-exit is a must-have i suspect?
>>
>> Not really. Deadlock check is needed on PI, so it can be done at the
>> same time (you have to walk the chain anyway). In any other case, it
>> is an option you can request (or not).
>
>well, i was talking about the mutex code in PREEMPT_RT. There deadlock
>detection is an optional debug feature. You dont _have_ to do deadlock
>detection for the kernel's locks, and there's a difference in
>performance.

Big mouth'o mine :-|

Let me re-phrase then: it is a must have only on PI, to make sure
you don't have a loop when doing it. Maybe is a consequence of the
algorithm I chose. -However- it should be possible to disable it
in cases where you are reasonably sure it won't happen (such as
kernel code). In any case, AFAIR, I still did not implement it.

Was this more useful?

-- Inaky

2005-04-11 08:58:39

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

* Perez-Gonzalez, Inaky <[email protected]> wrote:

> Let me re-phrase then: it is a must have only on PI, to make sure you
> don't have a loop when doing it. Maybe is a consequence of the
> algorithm I chose. -However- it should be possible to disable it in
> cases where you are reasonably sure it won't happen (such as kernel
> code). In any case, AFAIR, I still did not implement it.

are there cases where userspace wants to disable deadlock-detection for
its own locks?

the deadlock detector in PREEMPT_RT is pretty much specialized for
debugging (it does all sorts of weird locking tricks to get the first
deadlock out, and to really report it on the console), but it ought to
be possible to make it usable for userspace-controlled locks as well.

Ingo

2005-04-11 09:04:18

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

>From: Ingo Molnar [mailto:[email protected]]
>
>* Perez-Gonzalez, Inaky <[email protected]> wrote:
>
>> Let me re-phrase then: it is a must have only on PI, to make sure you
>> don't have a loop when doing it. Maybe is a consequence of the
>> algorithm I chose. -However- it should be possible to disable it in
>> cases where you are reasonably sure it won't happen (such as kernel
>> code). In any case, AFAIR, I still did not implement it.
>
>are there cases where userspace wants to disable deadlock-detection for
>its own locks?

I would guess--if I know I have coded my application properly
(cough) or I am using locks that by design are completely orthogonal,
I would say deadlock checking is getting in the way.

>the deadlock detector in PREEMPT_RT is pretty much specialized for
>debugging (it does all sorts of weird locking tricks to get the first
>deadlock out, and to really report it on the console), but it ought to
>be possible to make it usable for userspace-controlled locks as well.

fusyn's is as simple as it can get: when you are about to lock(), it
checks that you don't own the lock already, but it generalizes it
(it checks that the owner of the lock is not waiting for a lock
whose owner is waiting for a lock whose owner...is waiting for a lock
that you own).

-- Inaky

2005-04-11 16:23:50

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Sun, 2005-04-10 at 03:53, Ingo Molnar wrote:

> ok, i've added this patch to the -45-00 release. It's looking good on my
> testsystems so far, but it will need some more testing i guess.

Yes, I ran the PI test, and just let the system run .. So it could use
more extensive testing..

Daniel

2005-04-11 22:19:42

by Bill Huey

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Mon, Apr 11, 2005 at 10:57:37AM +0200, Ingo Molnar wrote:
>
> * Perez-Gonzalez, Inaky <[email protected]> wrote:
>
> > Let me re-phrase then: it is a must have only on PI, to make sure you
> > don't have a loop when doing it. Maybe is a consequence of the
> > algorithm I chose. -However- it should be possible to disable it in
> > cases where you are reasonably sure it won't happen (such as kernel
> > code). In any case, AFAIR, I still did not implement it.
>
> are there cases where userspace wants to disable deadlock-detection for
> its own locks?

I'd disable it for userspace locks. There might be folks that want to
implement userspace drivers, but I can't imagine it being 'ok' to have
the kernel call out to userspace and have it block correctly. I would
expect them to do something else that's less drastic.

> the deadlock detector in PREEMPT_RT is pretty much specialized for
> debugging (it does all sorts of weird locking tricks to get the first
> deadlock out, and to really report it on the console), but it ought to
> be possible to make it usable for userspace-controlled locks as well.

If I understand things correctly, I'd let that be an RT app issue and
the app folks should decided what is appropriate for their setup. If
they need a deadlock detector they should decide on their own protocol.
The kernel debugging issues are completely different.

That's my two cents.

bill

2005-04-11 22:35:55

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

>From: Bill Huey (hui) [mailto:[email protected]]
>
>On Mon, Apr 11, 2005 at 10:57:37AM +0200, Ingo Molnar wrote:
>>
>> * Perez-Gonzalez, Inaky <[email protected]> wrote:
>>
>> > Let me re-phrase then: it is a must have only on PI, to make sure
you
>> > don't have a loop when doing it. Maybe is a consequence of the
>> > algorithm I chose. -However- it should be possible to disable it in
>> > cases where you are reasonably sure it won't happen (such as kernel
>> > code). In any case, AFAIR, I still did not implement it.
>>
>> are there cases where userspace wants to disable deadlock-detection
for
>> its own locks?
>
>I'd disable it for userspace locks. There might be folks that want to
>implement userspace drivers, but I can't imagine it being 'ok' to have
>the kernel call out to userspace and have it block correctly. I would
>expect them to do something else that's less drastic.

If you are exposing the kernel locks to userspace to implement
mutexes (eg POSIX mutexes), deadlock checking is a feature you want
to have to complain with POSIX. According to some off the record
requirements I've been given, some applications badly need it (I have
a hard time believing that they are so broken, but heck...).

-- Inaky

2005-04-11 23:11:34

by Bill Huey

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Mon, Apr 11, 2005 at 03:31:41PM -0700, Perez-Gonzalez, Inaky wrote:
> If you are exposing the kernel locks to userspace to implement
> mutexes (eg POSIX mutexes), deadlock checking is a feature you want
> to have to complain with POSIX. According to some off the record
> requirements I've been given, some applications badly need it (I have
> a hard time believing that they are so broken, but heck...).

I'd like to read about those requirements, but, IMO a lot of the value
of various priority protocols varies greatly on the context and size (N
threads) of the application using it. If user/kernel space have to be
coupled via some thread of execution, (IMO) then it's better to seperate
them with some event notification queues like signals (wake a thread
via an queue event) than to mix locks across the user/kernel space
boundary. There's tons of abuse that can be opened up with various
priority protocols with regard to RT apps and giving it a first class
entry way without consideration is kind of scary.

It's important to outline the requirements of the applications and then
see what you can do using minimal synchronization objects before
exploding that divide.

Also, Posix isn't always politically neutral nor complete regarding
various things. You have to consider the context of these things.
I'll have to think about this a bit more and review your patch more
carefully.

I'm all ears if you think I'm wrong.

bill

2005-04-11 23:30:28

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

>From: Bill Huey (hui) [mailto:[email protected]]
>On Mon, Apr 11, 2005 at 03:31:41PM -0700, Perez-Gonzalez, Inaky wrote:
>> If you are exposing the kernel locks to userspace to implement
>> mutexes (eg POSIX mutexes), deadlock checking is a feature you want
>> to have to complain with POSIX. According to some off the record
>> requirements I've been given, some applications badly need it (I have
>> a hard time believing that they are so broken, but heck...).
>
>I'd like to read about those requirements, but, IMO a lot of the value

More than a formal requirement is a "practical" one. Some
company (leader in their field, of course) has this huge
blobl of code they want to use in Linux and it has the typical
API than once upon a time was made multithreaded by just adding
a bunch of pthread_mutex_[un]lock() at the API entry point...
without realizing that some of the top level API calls also
called other top level API calls, so they'd deadlock.

Quick fix: the usual. Enable deadlock detection and if it
returns deadlock, assume it is locked already and proceed (or
do a recursive mutex, or a trylock).

And so on, and so forth...

>of various priority protocols varies greatly on the context and size (N
>threads) of the application using it. If user/kernel space have to be
>coupled via some thread of execution, (IMO) then it's better to
seperate
>them with some event notification queues like signals (wake a thread
>via an queue event) than to mix locks across the user/kernel space
> ...

I wonder if we are confusing apples and oranges here--I don't think
we were considering cases about mixing kernel locks that are accessible
both from kernel and user space.

The focus is to have a kernel lock entity and that user space can
use it for implementing the user space mutexes, but *not* mix
them (like in user and kernel space sharing this lock for doing
whatever).

It is certainly something to explore, but I'd better drive your
way than do it. It's cleaner. Hides implementation details.

>It's important to outline the requirements of the applications and then
>see what you can do using minimal synchronization objects before
>exploding that divide.

I agree, but it doesn't work that well when talking about legacy
systems...that's the problem.

>Also, Posix isn't always politically neutral nor complete regarding
>various things. You have to consider the context of these things.
>I'll have to think about this a bit more and review your patch more
>carefully.

Sure--and because most was for legacy reasons that adhered to
POSIX strictly, it was very simple: we need POSIX this, that and
that (PI, proper adherence to scheduler policy wake up/rt-behaviour,
deadlock detection, etc).

Fortunately in those areas POSIX is not too gray; code to the book.
Deal.

Of course, selling it to the lkml is another story.

-- Inaky

2005-04-12 00:26:59

by Bill Huey

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Mon, Apr 11, 2005 at 04:28:25PM -0700, Perez-Gonzalez, Inaky wrote:
> >From: Bill Huey (hui) [mailto:[email protected]]
...
> API than once upon a time was made multithreaded by just adding
> a bunch of pthread_mutex_[un]lock() at the API entry point...
> without realizing that some of the top level API calls also
> called other top level API calls, so they'd deadlock.

Oh crap.

> Quick fix: the usual. Enable deadlock detection and if it
> returns deadlock, assume it is locked already and proceed (or
> do a recursive mutex, or a trylock).

You have to be joking me ? geez.
...
> It is certainly something to explore, but I'd better drive your
> way than do it. It's cleaner. Hides implementation details.
>
> I agree, but it doesn't work that well when talking about legacy
> systems...that's the problem.

Yeah, ok, I understand what's going on now. There isn't a notion
of projecting priority across into the Unix/Linux kernel traditionally
which is why it seemed so bizarre.

> Sure--and because most was for legacy reasons that adhered to
> POSIX strictly, it was very simple: we need POSIX this, that and
> that (PI, proper adherence to scheduler policy wake up/rt-behaviour,
> deadlock detection, etc).

Some of this stuff sounds like recursive locking. Would this be a
better expression to solve the "top level API locking" problem
you're referring to ?

> Fortunately in those areas POSIX is not too gray; code to the book.
> Deal.

I would think that there will have to be a graph discontinuity
between user/kernel spaces at kernel entry and exit for the deadlock
detector. Can't say about issues at fork time, but I would expect
that those objects would have to be destroyed when the process exits.

The current RT (Ingo's) lock isn't recursive nor is the deadlock
detector the last time I looked. Do think that this is a problem
for legacy apps if it gets overload for being the userspace futex
as well ? (assuming I'm understanding all of this correctly)

> Of course, selling it to the lkml is another story.

I would think that pushing as much of this into userspace would
make the kernel hooks for it more acceptable. Don't know.

/me thinks more

bill

2005-04-12 00:38:34

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

>From: Bill Huey (hui) [mailto:[email protected]]
>
>> Quick fix: the usual. Enable deadlock detection and if it
>> returns deadlock, assume it is locked already and proceed (or
>> do a recursive mutex, or a trylock).
>
>You have to be joking me ? geez.
>...

This is way *more* common than you think--I've seen it around
some big multithreaded OSS packages [can't remember which now].

>> Sure--and because most was for legacy reasons that adhered to
>> POSIX strictly, it was very simple: we need POSIX this, that and
>> that (PI, proper adherence to scheduler policy wake up/rt-behaviour,
>> deadlock detection, etc).
>
>Some of this stuff sounds like recursive locking. Would this be a
>better expression to solve the "top level API locking" problem
>you're referring to ?

Bingo. That's another way to "fix" it. Luckily, recursive locking
can be safely and quickly done in user space (I own this lock,
ergo I just inc the lock count).

The problem with deadlocks is when the scenario gets more complex
and you are trying to lock a mutex and the owner is waiting for
a mutex whose owner is waiting for a mutex that you own...this
more commonly happens when you don't know what the heck is going
on in the code, which unfortunately is very common on people that
inherits big pieces of stacks to maintain.

>> Fortunately in those areas POSIX is not too gray; code to the book.
>> Deal.
>
>I would think that there will have to be a graph discontinuity
>between user/kernel spaces at kernel entry and exit for the deadlock
>detector. Can't say about issues at fork time, but I would expect
>that those objects would have to be destroyed when the process exits.

fork time is not an issue, as POSIX makes forks and thread incompatible
(in a nutshell, only the thread calling fork() survives, all the mutexes
are [IIRC] reinitialized or something like that...).

>The current RT (Ingo's) lock isn't recursive nor is the deadlock
>detector the last time I looked. Do think that this is a problem
>for legacy apps if it gets overload for being the userspace futex
>as well ? (assuming I'm understanding all of this correctly)

Should be not on the recursive side; as I said, that is easy to do
[currently NPTL does it with the futexes]. The deadlock stuff gets
hairier, but it's not such a big of a deal when you have your data
structures setup. It takes time, though.

>> Of course, selling it to the lkml is another story.
>
>I would think that pushing as much of this into userspace would
>make the kernel hooks for it more acceptable. Don't know.

Agreed. Deadlock checking though, has to be done in the kernel. For
the generic case it is the only way to do it sanely.

-- Inaky

2005-04-12 20:32:27

by Paul E. McKenney

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Thu, Apr 07, 2005 at 10:52:25AM -0700, Daniel Walker wrote:
>
> Source: Daniel Walker <[email protected]> MontaVista Software, Inc
> Description:
> This patch adds the priority list data structure from Inaky Perez-Gonzalez
> to the Preempt Real-Time mutex.
>
> the patch order is (starting with a 2.6.11 kernel tree),
>
> patch-2.6.12-rc2
> realtime-preempt-2.6.12-rc2-V0.7.44-01
>
> Signed-off-by: Daniel Walker <[email protected]>
>
> Index: linux-2.6.11/include/linux/plist.h
> ===================================================================
> --- linux-2.6.11.orig/include/linux/plist.h 1970-01-01 00:00:00.000000000 +0000
> +++ linux-2.6.11/include/linux/plist.h 2005-04-07 17:47:42.000000000 +0000
> @@ -0,0 +1,310 @@

[ . . . ]

> +/* Grunt to do the real removal work of @pl from the plist. */
> +static inline
> +void __plist_del (struct plist *pl)
> +{
> + struct list_head *victim;
> + if (list_empty (&pl->dp_node)) /* SP-node, not head */
> + victim = &pl->sp_node;
> + else if (list_empty (&pl->sp_node)) /* DP-node, empty SP list */
> + victim = &pl->dp_node;
> + else { /* SP list head, not empty */
> + struct plist *pl_new = container_of (pl->sp_node.next,
> + struct plist, sp_node);
> + victim = &pl->sp_node;
> + list_replace_rcu (&pl->dp_node, &pl_new->dp_node);

If you are protecting this list with RCU...

> + }
> + list_del_init (victim);

... you need to wait for a grace period before deleting the element
removed from the list.

Or are you just using list_replace_rcu() for its replacement capability?
If so, seems like it might be worthwhile to make a list_replace().
This would get rid of the memory barrier, and also keep from confusing
people like myself. ;-)

Thanx, Paul

2005-04-12 23:13:53

by Esben Nielsen

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

I looked at the PI-code to see what priority the task (old_owner below)
would end up with when it released a lock. From rt.c:

prio = mutex_getprio(old_owner);
if (new_owner && !plist_empty(&new_owner->pi_waiters)) {
w = plist_entry(&new_owner->pi_waiters, struct
rt_mutex_waiter, pi_list);
prio = w->task->prio;
}
if (prio != old_owner->prio)
pi_setprio(lock, old_owner, prio);

What has new_owner to do with it? Shouldn't it be old_owner in these
lines? I.e. the prio we want to set old_owner to should be the prio of the
head of the old_owner->pi_waiters, not the new_owner!

Esben

On Mon, 11 Apr 2005, Ingo Molnar wrote:

>
> * Perez-Gonzalez, Inaky <[email protected]> wrote:
>
> > Let me re-phrase then: it is a must have only on PI, to make sure you
> > don't have a loop when doing it. Maybe is a consequence of the
> > algorithm I chose. -However- it should be possible to disable it in
> > cases where you are reasonably sure it won't happen (such as kernel
> > code). In any case, AFAIR, I still did not implement it.
>
> are there cases where userspace wants to disable deadlock-detection for
> its own locks?
>
> the deadlock detector in PREEMPT_RT is pretty much specialized for
> debugging (it does all sorts of weird locking tricks to get the first
> deadlock out, and to really report it on the console), but it ought to
> be possible to make it usable for userspace-controlled locks as well.
>
> Ingo
>

2005-04-12 18:35:14

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Sun, 2005-04-10 at 04:09, Ingo Molnar wrote:
> Unless i'm missing something, this could be implemented by detaching
> lock->owner_prio from lock->owner - via e.g. negative values. Thus some
> minimal code would check whether we need the owner's priority in the PI
> logic, or the semaphore's "own" priority level.

The owners priority should be set to the semaphore's priority .. Or the
highest priority of all the semaphores that it has locked.

Daniel

2005-05-06 08:57:55

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

Daniel Walker wrote:
>
> Description:
> This patch adds the priority list data structure from Inaky Perez-Gonzalez
> to the Preempt Real-Time mutex.
>
> ...
>
> +#define plist_for_each(pos1, pos2, head) \
> + list_for_each_entry(pos1, &((head)->dp_node), dp_node) \
> + list_for_each_entry(pos2, &((pos1)->sp_node), sp_node)

I can't understand how this can work.

The fist list_for_each_entry(->dp_node) will iterate over nodes
with different priorities, ok. But the second one will skip the
first node (which starts new priority group), because list_for_each(head)
does not count head.

To be sure, I wrote simple test:

#include <stdio.h>
#include <limits.h>
#include "list.h"
#include "plist.h"

int main(void)
{
struct plist head, node, *pos1, *pos2;

plist_init(&head, 0);
plist_init(&node, 0);

plist_add(&node, &head);

plist_for_each(pos1, pos2, &head)
printf("Strange ???\n");

return 0;
}

Prints nothing.

My apologies if I'm misunderstanding something.

Oleg.

2005-05-06 11:06:14

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

Oleg Nesterov wrote:
>
> Daniel Walker wrote:
> >
> > Description:
> > This patch adds the priority list data structure from Inaky Perez-Gonzalez
> > to the Preempt Real-Time mutex.
> >
> ...
>
> I can't understand how this can work.

And I think it is possible to simplify plist's design.

struct plist {
int prio;
struct list_head prio_list;
struct list_head node_list;
};

#define plist_for_each(pos, head) \
list_for_each_entry(pos, &(head)->node_list, node_list)

static inline void plist_add(struct plist *new, struct plist *head)
{
struct plist* pos;

INIT_LIST_HEAD(&new->prio_list);

list_for_each_entry(pos, &head->prio_list, prio_list)
if (new->prio < pos->prio)
goto lt_prio;
else if (new->prio == pos->prio) {
pos = list_entry(pos->prio_list.next,
struct plist, prio_list);
goto eq_prio;
}

lt_prio:
list_add_tail(&new->prio_list, &pos->prio_list);
eq_prio:
list_add_tail(&new->node_list, &pos->node_list);
}

static inline void plist_del(struct plist *del)
{
if (!list_empty(&del->prio_list)) {
struct plist *next = list_entry(del->node_list.next,
struct plist, node_list);
list_move_tail(&next->prio_list, &del->prio_list);
list_del_init(&del->prio_list);
}

list_del_init(&del->node_list);
}

All nodes in prio list are chained via ->node_list, sorted in ascending
->prio/fifo order. Nodes which start different priority slice are chained
via ->prio_list, ascending ->prio order.

Slightly tested, seems to work.

I think this would be even better:

struct plist_head {
struct list_head prio_list;
struct list_head node_list;
}

struct plist {
int prio;
struct plist_head head;
}

The plist_head's min/max prio can be found from
plist_head.prio_list.next/prev.

What do you think?

Oleg.

2005-05-06 18:18:06

[permalink] [raw]

Subject: RE: [PATCH] Priority Lists for the RT mutex

>-----Original Message-----
>From: [email protected] [mailto:[email protected]] On Behalf Of Oleg Nesterov
>Sent: Friday, May 06, 2005 4:13 AM
>To: [email protected]; Daniel Walker; Perez-Gonzalez, Inaky;
Ingo Molnar
>Subject: Re: [PATCH] Priority Lists for the RT mutex
>
>Oleg Nesterov wrote:
>>
>> Daniel Walker wrote:
>> >
>> > Description:
>> > This patch adds the priority list data structure from Inaky
Perez-Gonzalez
>> > to the Preempt Real-Time mutex.
>> >
>> ...
>>
>> I can't understand how this can work.
>
>And I think it is possible to simplify plist's design.
>
> ...
>
> struct plist, prio_list);
> goto eq_prio;
> }
>
>lt_prio:
> list_add_tail(&new->prio_list, &pos->prio_list);
>eq_prio:
> list_add_tail(&new->node_list, &pos->node_list);
>}

Isn't this adding them to *both* lists in the lt_prio
case? I don't understand what do you want to accomplish
in this case.

[like for example, if the list is empty and you add one,
it will start a new node_list, but you have also added
it to the head's prio_list]

If you ware changing the operational mode, can you please
explain your change in more detail?

It could also be I have *the* headache...but hey :)

-- Inaky

2005-05-06 18:56:09

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Fri, 6 May 2005, Oleg Nesterov wrote:

> Oleg Nesterov wrote:
> >
> > Daniel Walker wrote:
> > >
> > > Description:
> > > This patch adds the priority list data structure from Inaky Perez-Gonzalez
> > > to the Preempt Real-Time mutex.
> > >
> > ...
> >
> > I can't understand how this can work.
>
> And I think it is possible to simplify plist's design.
>
> struct plist {
> int prio;
> struct list_head prio_list;
> struct list_head node_list;
> };
>

Make a patch .

Daniel

2005-05-07 07:18:34

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

"Perez-Gonzalez, Inaky" wrote:
>
> >Oleg Nesterov wrote:
> >>
> >> Daniel Walker wrote:
> >> >
> >> > Description:
> >> > This patch adds the priority list data structure from Inaky Perez-Gonzalez
> >> > to the Preempt Real-Time mutex.
> >> >
> >> ...
> >And I think it is possible to simplify plist's design.
> >
> > ...
> >
> >lt_prio:
> > list_add_tail(&new->prio_list, &pos->prio_list);
> >eq_prio:
> > list_add_tail(&new->node_list, &pos->node_list);
> >}
>
> Isn't this adding them to *both* lists in the lt_prio
> case? I don't understand what do you want to accomplish
> in this case.

Yes. ->node_list contains *ALL* nodes, that is why we can:

#define plist_for_each(pos, head) \
list_for_each_entry(pos, &(head)->node_list, node_list)

head <=======> prio=1 <===> prio=2 <===> ...
/\ /| /\
| | |
\/ | \/
prio=1 | prio=2
/\ / /\
| / |
\/ / \/
prio=1 / ....
<---/

/\
Where <===> means ->prio_list, | ->node_list.
\/

Daniel Walker wrote:
>
> Make a patch .

Will do. However, I'm unfamiliar with Ingo's tree, so I
can send only new plist's implementation.

Oleg.

2005-05-09 07:34:38

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

* Oleg Nesterov <[email protected]> wrote:

> Daniel Walker wrote:
> >
> > Make a patch .
>
> Will do. However, I'm unfamiliar with Ingo's tree, so I
> can send only new plist's implementation.

i've uploaded my latest tree to:

http://redhat.com/~mingo/realtime-preempt/

it's easy to give it a go, it's pretty much plug & play, just apply
these patches ontop of a vanilla 2.6.11 kernel tree:

http://kernel.org/pub/linux/kernel/v2.6/testing/patch-2.6.12-rc4.bz2
http://redhat.com/~mingo/realtime-preempt/realtime-preempt-2.6.12-rc4-V0.7.47-00

take your usual .config, do a 'make oldconfig', make sure you pick up
PREEMPT_RT (you can leave all the other .config options at their default
values), recompile and you should be set. All RT tasks (SCHED_FIFO,
SCHED_RR) will get PI handling and will use the plist.h code.

Ingo

2005-05-09 08:01:43

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

Ingo Molnar wrote:
>
> * Oleg Nesterov <[email protected]> wrote:
>
> > Daniel Walker wrote:
> > >
> > > Make a patch .
> >
> > Will do. However, I'm unfamiliar with Ingo's tree, so I
> > can send only new plist's implementation.
>
> i've uploaded my latest tree to:
>
> http://redhat.com/~mingo/realtime-preempt/
>

Ok, I'll try to do it. Do you have any comments/objections to
"[RFC][PATCH] alternative implementation of Priority Lists", see
http://marc.theaimsgroup.com/?l=linux-kernel&m=111547290706136
?

Oleg.

2005-05-09 09:17:21

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

* Oleg Nesterov <[email protected]> wrote:

> > i've uploaded my latest tree to:
> >
> > http://redhat.com/~mingo/realtime-preempt/
> >
>
> Ok, I'll try to do it. Do you have any comments/objections to
> "[RFC][PATCH] alternative implementation of Priority Lists", see
> http://marc.theaimsgroup.com/?l=linux-kernel&m=111547290706136
> ?

i havent reviewed them closely, but on the face of it the changes seem
plausible.

What would be nice to achieve are [low-cost] reductions of the size of
struct rt_mutex (in include/linux/rt_lock.h), upon which all other
PI-aware locking objects are based. Right now it's 9 words, of which
struct plist is 5 words. Would be nice to trim this to 8 words - which
would give a nice round size of 32 bytes on 32-bit.

Ingo

2005-05-09 14:07:38

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Sat, 7 May 2005, Oleg Nesterov wrote:
> Yes. ->node_list contains *ALL* nodes, that is why we can:
>
> #define plist_for_each(pos, head) \
> list_for_each_entry(pos, &(head)->node_list, node_list)
>
> head <=======> prio=1 <===> prio=2 <===> ...
> /\ /| /\
> | | |
> \/ | \/
> prio=1 | prio=2
> /\ / /\
> | / |
> \/ / \/
> prio=1 / ....
> <---/
>
> /\
> Where <===> means ->prio_list, | ->node_list.
> \/
> Will do. However, I'm unfamiliar with Ingo's tree, so I
> can send only new plist's implementation.

I've got something like this queued up .. Feel free to send yours as well
..

Daniel

2005-05-09 14:25:29

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

Ingo Molnar wrote:
>
> What would be nice to achieve are [low-cost] reductions of the size of
> struct rt_mutex (in include/linux/rt_lock.h), upon which all other
> PI-aware locking objects are based. Right now it's 9 words, of which
> struct plist is 5 words. Would be nice to trim this to 8 words - which
> would give a nice round size of 32 bytes on 32-bit.

Yes, the size of pl_head in that patch is 4 words, it doesn't have ->prio.

Oleg.

2005-05-09 18:13:58

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Mon, 2005-05-09 at 02:11, Ingo Molnar wrote:

> What would be nice to achieve are [low-cost] reductions of the size of
> struct rt_mutex (in include/linux/rt_lock.h), upon which all other
> PI-aware locking objects are based. Right now it's 9 words, of which
> struct plist is 5 words. Would be nice to trim this to 8 words - which
> would give a nice round size of 32 bytes on 32-bit.

Why not make rt_mutex->wait_lock a pointer ? Set it to NULL and handle
it in rt.c .

Daniel

2005-05-09 19:22:19

by Steven Rostedt

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Mon, 2005-05-09 at 11:13 -0700, Daniel Walker wrote:
> On Mon, 2005-05-09 at 02:11, Ingo Molnar wrote:
>
> > What would be nice to achieve are [low-cost] reductions of the size of
> > struct rt_mutex (in include/linux/rt_lock.h), upon which all other
> > PI-aware locking objects are based. Right now it's 9 words, of which
> > struct plist is 5 words. Would be nice to trim this to 8 words - which
> > would give a nice round size of 32 bytes on 32-bit.
>
> Why not make rt_mutex->wait_lock a pointer ? Set it to NULL and handle
> it in rt.c .

That may make the rt_mutex structure smaller but this increases the size
of the kernel by the size of that pointer (times every rt_mutex in the
kernel!). You still need to allocate the size of the raw spin lock,
although now you just point to it. Is rounding worth that much overhead?

-- Steve

2005-05-09 21:30:44

[permalink] [raw]

Subject: Re: [PATCH] Priority Lists for the RT mutex

On Mon, 2005-05-09 at 12:21, Steven Rostedt wrote:
> On Mon, 2005-05-09 at 11:13 -0700, Daniel Walker wrote:
> > On Mon, 2005-05-09 at 02:11, Ingo Molnar wrote:
> >
> > > What would be nice to achieve are [low-cost] reductions of the size of
> > > struct rt_mutex (in include/linux/rt_lock.h), upon which all other
> > > PI-aware locking objects are based. Right now it's 9 words, of which
> > > struct plist is 5 words. Would be nice to trim this to 8 words - which
> > > would give a nice round size of 32 bytes on 32-bit.
> >
> > Why not make rt_mutex->wait_lock a pointer ? Set it to NULL and handle
> > it in rt.c .
>
> That may make the rt_mutex structure smaller but this increases the size
> of the kernel by the size of that pointer (times every rt_mutex in the
> kernel!). You still need to allocate the size of the raw spin lock,
> although now you just point to it. Is rounding worth that much overhead?

It's a typo , I mean rt_mutex->wait_list . Sorry .. The list part is a
list head , which is two pointers. We could condense that to one
pointer, and it eliminates the overhead of the structure we use .. Below
seems to work, but consider it an rfc patch..

Daniel

Index: linux-2.6.11/include/linux/rt_lock.h
===================================================================
--- linux-2.6.11.orig/include/linux/rt_lock.h 2005-05-09 17:49:26.000000000 +0000
+++ linux-2.6.11/include/linux/rt_lock.h 2005-05-09 19:29:05.000000000 +0000
@@ -58,7 +58,7 @@ typedef struct {
*/
struct rt_mutex {
raw_spinlock_t wait_lock;
- struct plist wait_list;
+ struct plist *wait_list;
struct task_struct *owner;
int owner_prio;
# ifdef CONFIG_RT_DEADLOCK_DETECT
@@ -86,12 +86,11 @@ struct rt_mutex_waiter {
#ifdef CONFIG_RT_DEADLOCK_DETECT
# define __RT_MUTEX_INITIALIZER(lockname) \
{ .wait_lock = RAW_SPIN_LOCK_UNLOCKED, \
- .wait_list = PLIST_INIT((lockname).wait_list, MAX_PRIO), \
.name = #lockname, .file = __FILE__, .line = __LINE__ }
#else
# define __RT_MUTEX_INITIALIZER(lockname) \
{ .wait_lock = RAW_SPIN_LOCK_UNLOCKED, \
- PLIST_INIT((lockname).wait_list, MAX_PRIO) }
+ }
#endif
/*
* RW-semaphores are an RT mutex plus a reader-depth count.
Index: linux-2.6.11/kernel/rt.c
===================================================================
--- linux-2.6.11.orig/kernel/rt.c 2005-05-09 18:14:31.000000000 +0000
+++ linux-2.6.11/kernel/rt.c 2005-05-09 19:30:37.000000000 +0000
@@ -640,10 +640,11 @@ static void pi_setprio(struct rt_mutex *
plist_init(&w->pi_list, prio);
plist_add(&w->pi_list, &lock->owner->pi_waiters);

- plist_del(&w->list, &lock->wait_list);
- plist_init(&w->list, prio);
- plist_add(&w->list, &lock->wait_list);
-
+ if (!plist_empty(lock->wait_list)) {
+ plist_del(&w->list, lock->wait_list);
+ plist_init(&w->list, prio);
+ plist_add(&w->list, lock->wait_list);
+ }
}
/*
* If the task is blocked on a lock, and we just restored
@@ -656,10 +657,11 @@ static void pi_setprio(struct rt_mutex *
if (!rt_task(p) && !plist_empty(&w->pi_list)) {
TRACE_BUG_ON(!was_rt);
plist_del(&w->pi_list, &lock->owner->pi_waiters);
- plist_del(&w->list, &lock->wait_list);
- plist_init(&w->list, prio);
- plist_add(&w->list, &lock->wait_list);
-
+ if (!plist_empty(lock->wait_list)) {
+ plist_del(&w->list, lock->wait_list);
+ plist_init(&w->list, prio);
+ plist_add(&w->list, lock->wait_list);
+ }
}

pi_walk++;
@@ -694,16 +696,23 @@ task_blocks_on_lock(struct rt_mutex_wait
*/
#ifndef ALL_TASKS_PI
if (!rt_task(task)) {
- plist_add(&waiter->list, &lock->wait_list);
+ if (lock->wait_list)
+ plist_add(&waiter->list, lock->wait_list);
+ else
+ lock->wait_list = &waiter->list;
return;
}
#endif
spin_lock(&pi_lock);
plist_add(&waiter->pi_list, &lock->owner->pi_waiters);
+
/*
* Add RT tasks to the head:
*/
- plist_add(&waiter->list, &lock->wait_list);
+ if (lock->wait_list)
+ plist_add(&waiter->list, lock->wait_list);
+ else
+ lock->wait_list = &waiter->list;
/*
* If the waiter has higher priority than the owner
* then temporarily boost the owner:
@@ -721,7 +730,7 @@ static void __init_rt_mutex(struct rt_mu
{
lock->owner = NULL;
spin_lock_init(&lock->wait_lock);
- plist_init(&lock->wait_list, MAX_PRIO);
+ lock->wait_list = NULL;
#ifdef CONFIG_RT_DEADLOCK_DETECT
lock->save_state = save_state;
INIT_LIST_HEAD(&lock->held_list);
@@ -771,7 +780,7 @@ static inline struct task_struct * pick_
*
* (same-prio RT tasks go FIFO)
*/
- waiter = plist_entry(&lock->wait_list, struct rt_mutex_waiter, list);
+ waiter = plist_entry(lock->wait_list, struct rt_mutex_waiter, list);

trace_special_pid(waiter->task->pid, waiter->task->prio, 0);

@@ -779,7 +788,11 @@ static inline struct task_struct * pick_
check_pi_list_present(lock, waiter, old_owner);
#endif
new_owner = waiter->task;
- plist_del_init(&waiter->list, &lock->wait_list);
+ if (plist_empty(lock->wait_list)) {
+ plist_del_init(&waiter->list, lock->wait_list);
+ lock->wait_list = NULL;
+ } else
+ plist_del_init(&waiter->list, lock->wait_list);

plist_del(&waiter->pi_list, &old_owner->pi_waiters);
plist_init(&waiter->pi_list, waiter->task->prio);
@@ -796,9 +809,6 @@ static inline struct task_struct * pick_

static inline void init_lists(struct rt_mutex *lock)
{
- // we have to do this until the static initializers get fixed:
- if (!lock->wait_list.dp_node.prev && !lock->wait_list.dp_node.next)
- plist_init(&lock->wait_list, MAX_PRIO);
#ifdef CONFIG_RT_DEADLOCK_DETECT
if (!lock->held_list.prev && !lock->held_list.next)
INIT_LIST_HEAD(&lock->held_list);
@@ -927,7 +937,7 @@ static void __sched __down(struct rt_mut
if (grab_lock(lock,task)) {
/* granted */
struct task_struct *old_owner = lock->owner;
- TRACE_WARN_ON(!plist_empty(&lock->wait_list) && !old_owner);
+ TRACE_WARN_ON(lock->wait_list && !old_owner);
spin_lock(&pi_lock);
set_new_owner(lock, old_owner, task, eip);
spin_unlock(&pi_lock);
@@ -1024,7 +1034,7 @@ static void __sched __down_mutex(struct
if (grab_lock(lock,task)) {
/* granted */
struct task_struct *old_owner = lock->owner;
- TRACE_WARN_ON(!plist_empty(&lock->wait_list) && !old_owner);
+ TRACE_WARN_ON(lock->wait_list && !old_owner);
spin_lock(&pi_lock);
set_new_owner(lock, old_owner, task, eip);
spin_unlock(&pi_lock);
@@ -1164,7 +1174,7 @@ static int __sched __down_interruptible(
if (grab_lock(lock,task)) {
/* granted */
struct task_struct *old_owner = lock->owner;
- TRACE_WARN_ON(!plist_empty(&lock->wait_list) && !old_owner);
+ TRACE_WARN_ON(lock->wait_list && !old_owner);
spin_lock(&pi_lock);
set_new_owner(lock, old_owner, task, eip);
spin_unlock(&pi_lock);
@@ -1201,7 +1211,11 @@ wait_again:
trace_lock_irq(&trace_lock);
spin_lock(&lock->wait_lock);
if (waiter.task) {
- plist_del_init(&waiter.list, &lock->wait_list);
+ if (plist_empty(lock->wait_list)) {
+ plist_del_init(&waiter.list, lock->wait_list);
+ lock->wait_list = NULL;
+ } else
+ plist_del_init(&waiter.list, lock->wait_list);
/*
* Just remove ourselves from the PI list.
* (No big problem if our PI effect lingers
@@ -1257,7 +1271,7 @@ static int __down_trylock(struct rt_mute
if (grab_lock(lock,task)) {
/* granted */
struct task_struct *old_owner = lock->owner;
- TRACE_WARN_ON(!plist_empty(&lock->wait_list) && !old_owner);
+ TRACE_WARN_ON(lock->wait_list && !old_owner);
spin_lock(&pi_lock);
set_new_owner(lock, old_owner, task, eip);
spin_unlock(&pi_lock);
@@ -1324,7 +1338,6 @@ static void __up_mutex(struct rt_mutex *
trace_lock_irqsave(&trace_lock, flags);
TRACE_BUG_ON(!irqs_disabled());
spin_lock(&lock->wait_lock);
- TRACE_BUG_ON(!lock->wait_list.dp_node.prev && !lock->wait_list.dp_node.next);

#ifdef CONFIG_RT_DEADLOCK_DETECT
TRACE_WARN_ON(list_empty(&lock->held_list));
@@ -1334,12 +1347,12 @@ static void __up_mutex(struct rt_mutex *

old_owner = lock->owner;
#ifdef ALL_TASKS_PI
- if (plist_empty(&lock->wait_list))
+ if (lock->wait_list)
check_pi_list_empty(lock, old_owner);
#endif
lock->owner = NULL;
new_owner = NULL;
- if (!plist_empty(&lock->wait_list))
+ if (lock->wait_list)
new_owner = pick_new_owner(lock, old_owner, save_state, eip);

/*

2005-05-09 22:15:52