linux-kernel - Re: RFC for a new Scheduling policy/class in the Linux-kernel

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <4A5F448C.2050909@nortel.com>
Date:	Thu, 16 Jul 2009 09:17:32 -0600
From:	"Chris Friesen" <cfriesen@...tel.com>
To:	Ted Baker <baker@...fsu.edu>
CC:	Noah Watkins <jayhawk@....ucsc.edu>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Raistlin <raistlin@...ux.it>,
	Douglas Niehaus <niehaus@...c.ku.edu>,
	Henrik Austad <henrik@...tad.us>,
	LKML <linux-kernel@...r.kernel.org>, Ingo Molnar <mingo@...e.hu>,
	Bill Huey <billh@...ppy.monkey.org>,
	Linux RT <linux-rt-users@...r.kernel.org>,
	Fabio Checconi <fabio@...dalf.sssup.it>,
	"James H. Anderson" <anderson@...unc.edu>,
	Thomas Gleixner <tglx@...utronix.de>,
	Dhaval Giani <dhaval.giani@...il.com>,
	KUSP Google Group <kusp@...glegroups.com>,
	Tommaso Cucinotta <cucinotta@...up.it>,
	Giuseppe Lipari <lipari@...is.sssup.it>
Subject: Re: RFC for a new Scheduling policy/class in the Linux-kernel

Ted Baker wrote:
> On Mon, Jul 13, 2009 at 03:45:11PM -0600, Chris Friesen wrote:
> 
>> Given that the semantics of POSIX PI locking assumes certain scheduler
>> behaviours, is it actually abstraction inversion to have that same
>> dependency expressed in the kernel code that implements it?
> ...> 
>> The whole point of mutexes (and semaphores) within the linux kernel is
>> that it is possible to block while holding them.  I suspect you're going
>> to find it fairly difficult to convince people to spinlocks just to make
>> it possible to provide latency guarantees.
> 
> The abstraction inversion is when the kernel uses (internally)
> something as complex as a POSIX PI mutex.  So, I'm not arguing
> that the kernel does not need internal mutexes/semaphores that
> can be held while a task is suspended/blocked.  I'm just arguing
> that those internal mutexes/semaphores should not be PI ones.

This ties back to your other message with the comment about implementing
userspace PI behaviour via some simpler "loopholes".

If the application is already explicitly relying on PI pthread mutexes
(possibly because it hasn't got enough knowledge of itself to do PP or
to design the priorities in such a way that inversion isn't a problem)
then presumably priority inversion in the kernel itself will also be an
issue.

If a high-priority task makes a syscall that requires a lock currently
held by a sleeping low-priority task, and there is a medium priority
task that wants to run, the classic scenario for priority inversion has
been achieved.

>> On the other hand, PP requires code analysis to properly set the
>> ceilings for each individual mutex.
> 
> Indeed, this is difficult, but no more difficult than estimating
> worst-case blocking times, which requires more extensive code
> analysis and requires consideration of more cases with PI than PP.

I know of at least one example with millions of lines of code being
ported to linux from another OS.  The scheduling requirements are fairly
lax but deadlock due to priority inversion is a highly likely.  They
compare PI and PP, see that PP requires up-front analysis, so they
enable PI.

I suspect there are other similar cases where deadlock is the real
issue, and hard realtime isn't a concern (but low latency may be
desirable).  PI is simple to enable and doesn't require any thought on
the part of the app writer.

>> Certainly if you block waiting for I/O while holding a lock then it
>> impacts the ability to provide latency guarantees for others waiting for
>> that lock.  But this has nothing to do with PI vs PP or spinlocks, and
>> everything to do with how the lock is actually used.
> 
> My only point there was with respect to application-level use of
> POSIX mutexes, that if an application needs to suspend while
> holding a mutex (e.g., for I/O) then the application will have
> potentially unbounded priority inversion, and so is losing the
> benefit from priority inheritance.  So, if the only benefit of
> PRIO_INHERIT over PRIO_PROTECT is being able to suspend while
> holding a lock, there is no real benefit.  

At least for POSIX, both PI and PP mutexes can suspend while the lock is
held.  From the user's point of view, the only difference between the
two is that PP bumps the lock holder's priority always, while PI bumps
the priority only if/when necessary.

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