Hi, I have one question about rt_mutex.

Hi, I have one question about rt_mutex.

[Li Yu]

Hi, Steven.

Nice to meet you again.

I have read the rt-mutex-design.txt that you wrote. That is excellent
description of rt_mutex. But I have a question for rt_mutex.

As you said:


> Now since mutexes can be defined by user-land applications, we don't
want a DOS
> type of application that nests large amounts of mutexes to create a large
> PI chain, and have the code holding spin locks while looking at a large
> amount of data. So to prevent this, the implementation not only implements
> a maximum lock depth, but also only holds at most two different locks at a
> time, as it walks the PI chain. More about this below.

After read the implementation of rt_mutex_adjust_prio_chain(), I found
the we really require maximin lock depth (1024 default), but I can not
see the check for more same locks duplication. Does this doc is
inconsistent with code?

Thanks in advanced.

Good luck.
- Li Yu

Re: Hi, I have one question about rt_mutex.

[Esben Nielsen]

On Thu, 10 May 2007, Li Yu wrote:

> Hi, Steven.
>
> Nice to meet you again.
>
> I have read the rt-mutex-design.txt that you wrote. That is excellent
> description of rt_mutex. But I have a question for rt_mutex.
>
> As you said:
>
>
>> Now since mutexes can be defined by user-land applications, we don't
> want a DOS
>> type of application that nests large amounts of mutexes to create a large
>> PI chain, and have the code holding spin locks while looking at a large
>> amount of data. So to prevent this, the implementation not only implements
>> a maximum lock depth, but also only holds at most two different locks at a
>> time, as it walks the PI chain. More about this below.
>
> After read the implementation of rt_mutex_adjust_prio_chain(), I found
> the we really require maximin lock depth (1024 default), but I can not
> see the check for more same locks duplication. Does this doc is
> inconsistent with code?
>
> Thanks in advanced.
>
> Good luck.
> - Li Yu

At the label "again:" inside rt_mutex_adjust_prio_chain() no spinlocks are 
held. That is the kernel can reschedule at that point in the loop. So if 
you as a priority X task try to take a lock you will not delay any higher 
priority than X by more than the amount of time it takes to go 
around in the loop once. The max lock depth is just an extra safety.

The whole idea in a priority based real-time system is that the latency on 
priorty X only depends on what is going on at priority X and higher 
(including interrupt handlers). What ever goes on at lower priority can only
interfere with a fixed, predetermined, small amount of jitter.

Esben

> -
> 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/
>

Hi, I have one question about rt_mutex.

[Li Yu]

Hi, Steven.

Nice to meet you again.

I have read the rt-mutex-design.txt that you wrote. That is excellent
description of rt_mutex. But I have a question for rt_mutex.

As you said:


> Now since mutexes can be defined by user-land applications, we don't
want a DOS
> type of application that nests large amounts of mutexes to create a large
> PI chain, and have the code holding spin locks while looking at a large
> amount of data. So to prevent this, the implementation not only implements
> a maximum lock depth, but also only holds at most two different locks at a
> time, as it walks the PI chain. More about this below.

After read the implementation of rt_mutex_adjust_prio_chain(), I found
the we really require maximin lock depth (1024 default), but I can not
see the check for more same locks duplication. Does this doc is
inconsistent with code?

Thanks in advanced.

Good luck.
- Li Yu

Re: Hi, I have one question about rt_mutex.

[Steven Rostedt]

Li Yu wrote:
>> Now since mutexes can be defined by user-land applications, we don't
> want a DOS
>> type of application that nests large amounts of mutexes to create a large
>> PI chain, and have the code holding spin locks while looking at a large
>> amount of data. So to prevent this, the implementation not only implements
>> a maximum lock depth, but also only holds at most two different locks at a
>> time, as it walks the PI chain. More about this below.
> 
> After read the implementation of rt_mutex_adjust_prio_chain(), I found
> the we really require maximin lock depth (1024 default), but I can not
> see the check for more same locks duplication. Does this doc is
> inconsistent with code?

Nope, the code and the doc are still the same.

The thing that was most difficult in writing that document, was a way to
talk about the user locks (futex - fast user mutex) and the kernel locks
(spin_locks) without confusing the two.  The max depth is in reference
to the user futex, but the comment about the "at most two different
locks" is referencing the kernel's spin_locks.

I don't remember talking about looking for "lock duplication", which I'm
thinking you are referring to circular dead locks. I didn't cover that
in the document and I believe I even mentioned that I would not cover
the debug aspect of the code which would handle catching circular deadlocks.

But back to the "no more than two kernel locks held". This is very
important. Some PI implementations requires all locks in the PI chain to
have their internal locks held (as in spin_locks).  But letting user
space determine the number of spin locks held can cause large latencies
for the rest of the system.  So we designed a method to only need to
hold two internal spin_locks in the PI chain at a time.  The kernel
doesn't care if the user application is abusing itself (holding too many
of it's own user locks).  But the kernel does care if a user application
can affect other non related applications.

As Esben already mentioned, the PI chain even lets the locking user
mutex schedule without holding any kernel locks.  This is very key. It
keeps the latency down on setting up a PI chain which can be very expensive.

Note: Esben helped a lot in the development of the final design of
rtmutex.c.

-- Steve

Re: Hi, I have one question about rt_mutex.

[Li Yu]

Steven Rostedt wrote:
> Li Yu wrote:
>   
>>> Now since mutexes can be defined by user-land applications, we don't
>>>       
>> want a DOS
>>     
>>> type of application that nests large amounts of mutexes to create a large
>>> PI chain, and have the code holding spin locks while looking at a large
>>> amount of data. So to prevent this, the implementation not only implements
>>> a maximum lock depth, but also only holds at most two different locks at a
>>> time, as it walks the PI chain. More about this below.
>>>       
>> After read the implementation of rt_mutex_adjust_prio_chain(), I found
>> the we really require maximin lock depth (1024 default), but I can not
>> see the check for more same locks duplication. Does this doc is
>> inconsistent with code?
>>     
>
> Nope, the code and the doc are still the same.
>
> The thing that was most difficult in writing that document, was a way to
> talk about the user locks (futex - fast user mutex) and the kernel locks
> (spin_locks) without confusing the two.  The max depth is in reference
> to the user futex, but the comment about the "at most two different
> locks" is referencing the kernel's spin_locks.
>
> I don't remember talking about looking for "lock duplication", which I'm
> thinking you are referring to circular dead locks. I didn't cover that
> in the document and I believe I even mentioned that I would not cover
> the debug aspect of the code which would handle catching circular deadlocks.
>
> But back to the "no more than two kernel locks held". This is very
> important. Some PI implementations requires all locks in the PI chain to
> have their internal locks held (as in spin_locks).  But letting user
> space determine the number of spin locks held can cause large latencies
> for the rest of the system.  So we designed a method to only need to
> hold two internal spin_locks in the PI chain at a time.  The kernel
> doesn't care if the user application is abusing itself (holding too many
> of it's own user locks).  But the kernel does care if a user application
> can affect other non related applications.
>
> As Esben already mentioned, the PI chain even lets the locking user
> mutex schedule without holding any kernel locks.  This is very key. It
> keeps the latency down on setting up a PI chain which can be very expensive.
>
> Note: Esben helped a lot in the development of the final design of
> rtmutex.c.
>
> -- Steve
>   
First, Thanks for such good explanation from you two guru in time.

Er, I think these two locks which you said are task->pi_lock and
rt_mutex->wait_lock.

>The max depth is in reference to the user futex, but the comment
>about the "at most two different locks" is referencing the 
>kernel's spin_locks.

This sentence make the my world clear from now on ;)

However, I found the sys_futex() do not use rt_mutex, so what's mean of the user futex you said?
Even, I have not found any usage for rt_mutex in kernel code. Or, some beautiful story will happen in future?

Goodluck.

- Li Yu

Re: Hi, I have one question about rt_mutex.

[Steven Rostedt]

Li Yu wrote:
> 
> However, I found the sys_futex() do not use rt_mutex, so what's mean of the user futex you said?
> Even, I have not found any usage for rt_mutex in kernel code. Or, some beautiful story will happen in future?
> 

Just need to look a little deeper :-)


sys_futex calls do_futex

do_futex with the option of FUTEX_LOCK_PI will call futex_lock_pi

futex_lock_pi calls rt_mutex_timed_lock or rt_mutex_trylock  both of
which are part of the rtmutex.c code.


So it's there today :-)

-- Steve