28 Nov
2003
28 Nov
'03
11:55 p.m.
while we're discussing various kernel security patches to facilitate
easier access to SCHED_FIFO/mlockall, i have another idea for a patch
that some people *might* like.
a new system call. call it "switch_to()". takes a PID (actually, it
needs some kind of TID), and does something very similar to
sched_yield() except instead of giving up the processor to whatever
the scheduler thinks is right, it yields to the specific
process/thread.
security: the target thread has to be using the same RT scheduling
policy (FIFO or RR) as the initiating thread. this means that it can
only be used to cause denial-of-service attacks that were already
trivial (because SCHED_FIFO was already available to the initiating
thread).
this could be used to completely short-circuit the FIFO mechanism used
by JACK in favor of completely deterministic, FS-lock-free
system. when you add in stuff like this (from ingo, discussing NPTL):
our kernel thread context switch latency is below 1 usec on a
typical P4 box, so our NPT library should compare pretty favorably
even in such benchmarks. We get from the pthread_create() call to
the first user instruction of the specified thread-function code in
less than 2 usecs, and we get from pthread_exit() to the thread
that does the pthread_join() in less than 2 usecs as well - all of
these operations are done via a single system-call and a single
context switch.
you end up with a truly superb architecture for the kind of thing
we're doing with JACK already.
however, note this comment from ingo as well, which i consider
short-sighted, and is part of the reason for my thinking about
switch_to():
M:N's big mistake is that it concentrates on what matters the least:
useruser context switches. Nothing really wants to do that. And if
it does, it's contended on some userspace locking object, at which
point it doesnt really matter whether the cost of switching is 1
usec or 0.5 usecs, the main application cost is the lost paralellism
and increased cache trashing due to the serialization -
independently of what kind of threading abstraction is used.
any thoughts? adding a syscall is a pretty trivial patch to create.
--p
29 Nov
29 Nov
1:30 a.m.
Paul Davis <paul(a)linuxaudiosystems.com> writes:
a new system call. call it "switch_to()".
takes a PID (actually, it
needs some kind of TID), and does something very similar to
sched_yield() except instead of giving up the processor to whatever
the scheduler thinks is right, it yields to the specific
process/thread.
This could be useful. But, it would probably be better to use some
existing mechanism like Mach ports instead of inventing Yet Another
Dispatch Mechanism. Stephane has already demonstrated that they work
well for running the JACK graph.
I never studied their implementation, but IIRC this kind of
switch_to() logic is implicit in the fast path case of a send() to a
port on which a thread is already waiting to receive(). (I don't
recall their exact terminology.)
The main advantage of an existing mechanism over new ideas is that
there are years of experience with security, performance, methods of
application and other subtleties.
BTW, I am not now nor have I ever been a fan of Mach. Linus is right,
microkernels are evil. But, Rick Rashid did have *some* good ideas.
:-)
Regards,
--
joq
1:57 a.m.
I never studied their implementation, but IIRC this
kind of
switch_to() logic is implicit in the fast path case of a send() to a
port on which a thread is already waiting to receive(). (I don't
recall their exact terminology.)
right, but its also implicit in the fast path case of a write() to a
FIFO on which a thread is waiting to read(), so that doesn't really
buy us anything. the problem with all these mechanisms IIUC is that
they all go via the filesystem in one way or another. and because the
filesystem has to interlock in a robust way to deal with many
different kinds of situations, it will always be a slower pathway than
a direct switch. perhaps the send/receive pair via a socket doesn't
require traversing the filesystem at all. it would be interesting to
know if that's true.
in addition, i don't think that under linux any of the "fast paths"
bypass the scheduler. all that happens is that the send/write marks
the waiter runnable, and then when the scheduler runs, it will
probably execute the waiter. maybe. sometimes. etc. its a much more
complex and RT-unsafe pathway that one PID/TID saying "switch to this
PID/TID now".
now that i remember, its possible that futexes might permit something
like this, but i think it still goes through the scheduler.
The main advantage of an existing mechanism over new
ideas is that
there are years of experience with security, performance, methods of
application and other subtleties.
switch_to() has existed in some form on every Mac until OS X came
along ("cooperative scheduling"). it wasn't very good because apps
could lock up the system by denying other things the change to run.
the point here is that caller can *already* lock up the machine, so
we're not changing this "feature". we're just extending it so that it
can involve other PID/TID's in this existing DoS opportunity :)
--p
8:16 a.m.
On Saturday 29 November 2003 04.54, Paul Davis wrote:
while we're discussing various kernel security
patches to facilitate
easier access to SCHED_FIFO/mlockall, i have another idea for a patch
that some people *might* like.
a new system call. call it "switch_to()". takes a PID (actually, it
needs some kind of TID), and does something very similar to
sched_yield() except instead of giving up the processor to whatever
the scheduler thinks is right, it yields to the specific
process/thread.
security: the target thread has to be using the same RT scheduling
policy (FIFO or RR) as the initiating thread. this means that it can
only be used to cause denial-of-service attacks that were already
trivial (because SCHED_FIFO was already available to the initiating
thread).
this could be used to completely short-circuit the FIFO mechanism used
by JACK in favor of completely deterministic, FS-lock-free
system. when you add in stuff like this (from ingo, discussing NPTL):
our kernel thread context switch latency is below 1 usec on a
typical P4 box, so our NPT library should compare pretty favorably
even in such benchmarks. We get from the pthread_create() call to
the first user instruction of the specified thread-function code in
less than 2 usecs, and we get from pthread_exit() to the thread
that does the pthread_join() in less than 2 usecs as well - all of
these operations are done via a single system-call and a single
context switch.
you end up with a truly superb architecture for the kind of thing
we're doing with JACK already.
The new scheduler is very good at switching processes quickly.
The old one had to walk throu all to decide which one to take,
not the new one. So you will not save much by telling wich process to
switch to. I think that the above figures include the scheduler!
(Have to check)
however, note this comment from ingo as well, which i consider
short-sighted, and is part of the reason for my thinking about
switch_to():
M:N's big mistake is that it concentrates on what matters the least:
useruser context switches. Nothing really wants to do that. And if
it does, it's contended on some userspace locking object, at which
point it doesnt really matter whether the cost of switching is 1
usec or 0.5 usecs, the main application cost is the lost paralellism
and increased cache trashing due to the serialization -
independently of what kind of threading abstraction is used.
This was about switching threads within a single process - simulating
threads in a system where they are not handled by the kernel.
Not about switching from one user process to another.
any thoughts? adding a syscall is a pretty trivial
patch to create.
And then the hard part begins - trying to get it accepted by Linus :-)
/RogerL
--
Roger Larsson
Skellefteå
Sweden
11:18 a.m.
you end up
with a truly superb architecture for the kind of thing
we're doing with JACK already.
The new scheduler is very good at switching processes quickly.
The old one had to walk throu all to decide which one to take,
not the new one. So you will not save much by telling wich process to
switch to. I think that the above figures include the scheduler!
(Have to check) any thoughts?
adding a syscall is a pretty trivial patch to create.
And then the hard part begins - trying to get it accepted by Linus :-)
1:51 p.m.
Paul Davis <paul(a)linuxaudiosystems.com> writes:
the problem is not (just?) the time that the scheduler
takes. its that
its decision making process is opaque. when jackd runs, it knows for
certain which pid/tid to run next. we don't want to cede control of
that back to the kernel scheduler.
No scheduler that I've ever seen, written, or heard of is going to
accept JACK's opinion on this subject as anything more than a strong
hint. The scheduler is the main loop of the entire system, *it*
decides what to run next.
Suggestions are welcome, but JACK truly does *not* know for certain
what to run next. An interrupt could intervene and make a
higher-priority realtime process ready. Or, some other processor
could unlock such a thread. At the very least, there probably needs
to be code in the return path from the system call like the old Unix
logic of testing `runrun' and calling sched().
i think i've mentioned before that i'd like to
do a paper on JACK
someday for Usenix, with a focus on its capabilities for "user space
cooperative real-time scheduling", or something like that.
Sounds good.
--
joq
4:57 p.m.
No scheduler that I've ever seen, written, or heard
of is going to
accept JACK's opinion on this subject as anything more than a strong
hint. The scheduler is the main loop of the entire system, *it*
decides what to run next.
i'm not trying to subvert the general operation of the scheduler. it
will still intervene when it needs/wants to.
what i want to stop is this: jackd is about running the process cycle,
and wants to hand control to the next client. it writes to a FIFO to
wakeup the next client, and goes to sleep waiting for the
"baton-passing" to wake it up again. however, for some bizarre reason,
the scheduler does not in fact run the next client, but does something
else instead.
put another way, i want JACK-the-system to keep running smoothly, even
though this includes crossing process boundaries. i don't want the
handoff of control that is implicit in running the process cycle to
return control to the scheduler "unnaturally".
Suggestions are welcome, but JACK truly does *not* know
for certain
what to run next. An interrupt could intervene and make a
higher-priority realtime process ready. Or, some other processor
could unlock such a thread. At the very least, there probably needs
to be code in the return path from the system call like the old Unix
logic of testing `runrun' and calling sched().
obviously, all these would remain in place and we would be doing
nothing subvert them. all we are doing is avoiding a schedule() caused
by jackd blocking-on-read and the next client being marked
runnable. both jackd and the next client should be considered "part of
the same system".
and just to be clear, i know this is a hack. i'm not pretending that
its good general purpose OS design (Apple already proved how
problematic it was). i'm trying to exploit the hackability that linux
is famous for to create a system really well tuned for "pro audio"
apps.
--p
8:57 p.m.
On Saturday 29 November 2003 21.55, Paul Davis wrote:
Let see - what you want is this:
To get this you should run the clients with higher priority than jackd!
Then they would be started and run before returning from the FIFO
write! :-)
client A requests data from FIFO
kernel lets A waits on FIFO
jackd writes data to FIFO
kernel puts data on FIFO
kernel wakes up waiters
--- client A has higher prio than jackd, it will preempt jackd while
--- jackd is still in the kernel.
client A wakes up
processes
returns baton
waits for more data on FIFO
kernel finds next task to run
and finds jackd (still on run queue)
kernel returns
jackd checks for baton - got it.
jackd determines what client to run next.
Maybe jack should handle the priorities for jack clients - priorities is a
relative issue anyway... Then jackd could use this scheme when there
is only one client to run - and the lower priority clients when there are
several.
/RogerL
--
Roger Larsson
Skellefteå
Sweden
No scheduler
that I've ever seen, written, or heard of is going to
accept JACK's opinion on this subject as anything more than a strong
hint. The scheduler is the main loop of the entire system, *it*
decides what to run next.
i'm not trying to subvert the general operation of the scheduler. it
will still intervene when it needs/wants to.
what i want to stop is this: jackd is about running the process cycle,
and wants to hand control to the next client. it writes to a FIFO to
wakeup the next client,
If next client is a RT process (SCHED_FIFO/RR) then it WILL be selected
unless there is another RT process with higher priority, and lower than jackd
otherwice it would have been running in the first place.
and goes to sleep waiting for the
"baton-passing" to wake it up again.
Jackd waits...
however, for some bizarre reason, the scheduler does
not in fact run the
next client, but does something else instead.
If this ever happens (and something else is not within in the priority range
new process ... jackd) then it is a scheduler BUG - and should be fixed!
Cases where RT processes ends up flushing page cache to disk should
be investigated and fixed. If any...
put another way, i want JACK-the-system to keep running smoothly, even
though this includes crossing process boundaries. i don't want the
handoff of control that is implicit in running the process cycle to
return control to the scheduler "unnaturally".
But the current scheme can do more. Suppose you are running on a SMP
machine (Chip level SMP processors are getting common - there is even a
Xilinx FPGA - Virtex Pro with four PowerPCs [Not G5 but anyway...]!)
Suppose that in this situation you have made data available for several
processes - how can you start them all with your suggested interface?
(You might want to start them all and let the scheduler figure out what
to do - hyperthreading is nice when using the same data)
With the current scheme (OK, I am not quite up to date)
you could write to the FIFOs of all ready processes before starting to
wait on the baton. [giving the sub processes different priority levels
will order them in case you have less processors than CPUs]
Suggestions are
welcome, but JACK truly does *not* know for certain
what to run next. An interrupt could intervene and make a
higher-priority realtime process ready. Or, some other processor
could unlock such a thread. At the very least, there probably needs
to be code in the return path from the system call like the old Unix
logic of testing `runrun' and calling sched().
obviously, all these would remain in place and we would be doing
nothing subvert them. all we are doing is avoiding a schedule() caused
by jackd blocking-on-read and the next client being marked
runnable. both jackd and the next client should be considered "part of
the same system".
10:20 p.m.
Roger Larsson <roger.larsson(a)norran.net> writes:
That's right. But, Paul and I have been working closely with this and
don't have much faith in the correctness of the 2.4 scheduler. Like
all non-trivial software components it has bugs, and getting them
fixed is difficult, if not impossible.
If next client is a RT process (SCHED_FIFO/RR) then it
WILL be selected
unless there is another RT process with higher priority, and lower than jackd
otherwice it would have been running in the first place.
I wish this were the true. But, I strongly suspect that it is not.
however, for
some bizarre reason, the scheduler does not in fact run the
next client, but does something else instead.
If this ever happens (and something else is not within in the priority range
new process ... jackd) then it is a scheduler BUG - and should be fixed! With the current scheme (OK, I am not quite up to
date)
you could write to the FIFOs of all ready processes before starting to
wait on the baton. [giving the sub processes different priority levels
will order them in case you have less processors than CPUs]
The current JACK implementation is completely single-threaded
regardless of how many real or virtual processors your system
possesses.
But, for some (relatively complex) graphs a multithread schedule would
be possible and desirable. So, theoretically your point is valid.
Maybe jack should handle the priorities for jack
clients - priorities is a
relative issue anyway... Then jackd could use this scheme when there
is only one client to run - and the lower priority clients when there are
several.
What problem does this solve?
--
joq
11:35 p.m.
On Sunday 30 November 2003 03.19, Jack O'Quin wrote:
It will better match what you think you do.
When jackd writes in the FIFO - expect client to start.
Jackd waits for baton - wait for client to finish.
But with jackd as highest priority:
Jackd writes to FIFO - nothing will happen for client.
Jackd _waits_ for baton - now client start, processes, finishes.
You could try a low priority jackd (still RT) in this way to see if
things behave better.
Next week I will read some jack and kernel code if you can try
to explain what happens.
/RogerL
--
Roger Larsson
Skellefteå
Sweden
Roger Larsson <roger.larsson(a)norran.net>
writes:
That's right. But, Paul and I have been working closely with this and
don't have much faith in the correctness of the 2.4 scheduler.
Have you told kernel developers about this?
This can be rather critical in embedded systems.
If next client is a RT process (SCHED_FIFO/RR)
then it WILL be selected
unless there is another RT process with higher priority, and lower than
jackd otherwice it would have been running in the first place.
I wish this were the true. But, I strongly suspect that it is not.
however,
for some bizarre reason, the scheduler does not in fact run
the next client, but does something else instead.
If this ever happens (and something else is not within in the priority
range new process ... jackd) then it is a scheduler BUG - and should be
fixed! Like all non-trivial software components it has bugs,
and getting them
fixed is difficult, if not impossible.
But the scheduler is VERY simple when you are using RT (SCHED_FIFO/RR).
It only selects the one with highest priority.
So unless your thread falls off the run queue - critical.
Does not timely get on the run queue after wake up - critical.
Gets stuck somewhere else - program bug?
But it could also be jackd the gets stuck doing something else...
(this is the reason why I am not comfortable with the printfs in
my rt_monitor - they use the console and it is bad...)
Anyway try to describe your problems in linux-kernel (cc me)
With the current scheme (OK, I am not quite up to
date)
you could write to the FIFOs of all ready processes before starting to
wait on the baton. [giving the sub processes different priority levels
will order them in case you have less processors than CPUs]
The current JACK implementation is completely single-threaded
regardless of how many real or virtual processors your system
possesses.
But, for some (relatively complex) graphs a multithread schedule would
be possible and desirable. So, theoretically your point is valid.
Maybe jack should handle the priorities for jack
clients - priorities is
a relative issue anyway... Then jackd could use this scheme when there is
only one client to run - and the lower priority clients when there are
several.
What problem does this solve?
30 Nov
30 Nov
12:04 a.m.
Roger Larsson <roger.larsson(a)norran.net> writes:
No. It's rather difficult to prove. There's no "smoking gun".
But, I have no reason to believe that it works correctly, and I
suspect that it probably does not.
I don't see why this is a problem. All this has to happen for every
cycle, anyway. What difference does it make? And, why do you think we
don't understand this?
--
joq
That's
right. But, Paul and I have been working closely with this and
don't have much faith in the correctness of the 2.4 scheduler.
Have you told kernel developers about this?
This can be rather critical in embedded systems. What problem
does this solve?
It will better match what you think you do.
When jackd writes in the FIFO - expect client to start.
Jackd waits for baton - wait for client to finish.
But with jackd as highest priority:
Jackd writes to FIFO - nothing will happen for client.
Jackd _waits_ for baton - now client start, processes, finishes.
1 Dec
1 Dec
4:41 a.m.
On Sunday 30 November 2003 05.03, Jack O'Quin wrote:
I don't see why this is a problem. All this has to happen for every
cycle, anyway. What difference does it make? And, why do you think we
don't understand this?
Sorry, I got my wording wrong! ("you" = developers in general)
But it is still a way to see that no client burns cycles where it should not -
jackd would not start (or stop). And you _can_ get fewer context switches,
but only if some client burns extra cycles.
Compare:
With jackd as highest priority:
* Client A running
* Jackd starts (higher prio than A), telling client B to run
* Jackd waits
* Client A contiues to run (higher prio than B)
- this could be something very short like preparing to go
to sleep after passing the baton.
* Client A done, goes to sleep.
* Client B runs - but later than expected...
* Client B done
* Jackd continues
Context switches: A->jd->A->B->jd
With jackd as lowest priority:
* Client A runs
* Jackd wants to start but has to wait
* Client A continues to run
* Client A done, goes to sleep
* Jackd starts, telling client B to run
* Client B starts
* Client B done
* Jackd continues, waits - B is finished
Context switches: A->jd->B->jd
Trying with jackd with lowest priority would atleast give you another
data point.
/RogerL
--
Roger Larsson
Skellefteå
Sweden
Roger Larsson <roger.larsson(a)norran.net>
writes:
No. It's rather difficult to prove. There's no "smoking gun".
But, I have no reason to believe that it works correctly, and I
suspect that it probably does not.
Is there a tread documenting your problems?
Anything else?
That's right. But, Paul and I have been working closely with this and
don't have much faith in the correctness of the 2.4 scheduler.
Have you told kernel developers about this?
This can be rather critical in embedded systems. What
problem does this solve?
It will better match what you think you do.
When jackd writes in the FIFO - expect client to start.
Jackd waits for baton - wait for client to finish.
But with jackd as highest priority:
Jackd writes to FIFO - nothing will happen for client.
Jackd _waits_ for baton - now client start, processes, finishes.
9:51 p.m.
Roger Larsson <roger.larsson(a)norran.net> writes:
But it is still a way to see that no client burns
cycles where it should not -
jackd would not start (or stop). And you _can_ get fewer context switches,
but only if some client burns extra cycles.
Compare:
With jackd as highest priority:
Context switches: A->jd->A->B->jd
With jackd as lowest priority:
Context switches: A->jd->B->jd
The actual JACK process cycle works like this:
jd->A->B->jd
--
joq
11:53 p.m.
Roger Larsson <roger.larsson(a)norran.net> writes:
and to be even clearer: the situation roger described where client A
is running and then we switch to jackd before running A again is
called "an xrun" :)
--p
But it is still a way to see that no client burns
cycles where it should not
-
jackd would not start (or stop). And you _can_
get fewer context switches,
but only if some client burns extra cycles.
Compare:
With jackd as highest priority:
Context switches: A->jd->A->B->jd
With jackd as lowest priority:
Context switches: A->jd->B->jd
The actual JACK process cycle works like this:
jd->A->B->jd
2 Dec
2 Dec
3:51 a.m.
New subject: jack context switches (Was: Re: [linux-audio-dev] another kernel patch?)
On Tuesday 02 December 2003 02.50, Jack O'Quin wrote:
Roger Larsson <roger.larsson(a)norran.net>
writes:
How?
How can B start immediately after A without ANY
jackd running in between?
(I am talking about external clients)
/RogerL
--
Roger Larsson
Skellefteå
Sweden
But it is still a way to see that no client burns
cycles where it should
not - jackd would not start (or stop). And you _can_ get fewer context
switches, but only if some client burns extra cycles.
Compare:
With jackd as highest priority:
Context switches: A->jd [start B] ->A [tail] ->B->jd
With jackd as lowest priority:
Context switches: A->jd->B->jd
The actual JACK process cycle works like this:
jd->A->B->jd 
4:41 a.m.
New subject: jack context switches (Was: Re: [linux-audio-dev] another kernel patch?)
On Tue, Dec 02, 2003 at 08:46:39 +0100, Roger Larsson wrote:
Through the magic of libjack. The clients are told who to wake up next.
- Steve
The actual
JACK process cycle works like this:
jd->A->B->jd
How?
How can B start immediately after A without ANY
jackd running in between?
8:04 a.m.
New subject: jack context switches (Was: Re: [linux-audio-dev] another kernel patch?)
The actual
JACK process cycle works like this:
jd->A->B->jd
How?
How can B start immediately after A without ANY
jackd running in between?
(I am talking about external clients) 
1 Dec
1 Dec
10:46 a.m.
At 29 Nov 2003 22:03:09 -0600,
Jack O'Quin wrote:
Roger Larsson <roger.larsson(a)norran.net> writes:
No. It's rather difficult to prove. There's no "smoking gun".
But, I have no reason to believe that it works correctly, and I
suspect that it probably does not.
as Roger pointed, the O(1) scheduler does quite simple tasks for RT
processes. it *should* work. if it deson't work, it's a bug in the
calculation of priority or so.
anyway, it's nice for debugging, if you can reproduce it...
Takashi
That's right. But, Paul and I have been working closely with this and
don't have much faith in the correctness of the 2.4 scheduler.
Have you told kernel developers about this?
This can be rather critical in embedded systems.
3:37 p.m.
Takashi Iwai <tiwai(a)suse.de> writes:
My comment above referred to the 2.4 scheduler with Linuxthreads. I
don't have enough testing time with 2.6 to make any claims about it.
My initial impression is that it works much better. But, it's too
soon to tell whether my distrust is no longer warranted. :-)
I have not studied the Linux O(1) scheduler implementation. But I
agree that it should be simple enough to work reliably. I wrote an
O(1) scheduler for AIX about 15 years ago. It was not at all
complicated. Once you get the data structures right, it's probably
easier than an O(n) scheduler.
Jack O'Quin wrote:
But, I have no
reason to believe that it works correctly, and I
suspect that it probably does not.
as Roger pointed, the O(1) scheduler does quite simple tasks for RT
processes. it *should* work. if it deson't work, it's a bug in the
calculation of priority or so. anyway, it's nice for debugging, if you can
reproduce it...
That would be nice, but I cannot.
It's more a matter of leaving things running overnight and having a
realtime thread get behind by a buffer or two before morning. This
might be due to rare kernel latency bugs and not the scheduler at all.
It could even be an application bug, though I doubt it.
There's just something about the 2.4 scheduler that feels wrong. At
this point I'm more interested in 2.6, so I guess I won't worry about
it any more.
--
joq
7450
days inactive
7454
days old
linux-audio-dev@lists.linuxaudio.org
18 comments
5 participants
participants (5)
-
Jack O'Quin -
Paul Davis -
Roger Larsson -
Steve Harris -
Takashi Iwai