On Tuesday 16 March 2004 18:30, Jamie Lokier wrote:
> Mark Gross wrote:
> > What can I do to help get high res timers available in the base kernel?
>
> Patches were written long ago, by George Anzinger I think.
>
> They were not accepted. You might want to look into why not. I think
> the reason was nothing to do with the quality of code, but rather that
> the clock programming overhead and code bloat wasn't desirable, and
> the gains not worth it.
>
> That is less true now that the kernel is pre-emptive. Before,
> high-res timers couldn't provide any useful scheduling guarantee: you
> might receive a timer at exactly 1.56ms, but your code might still not
> run for another 150ms anyway.
Thats not what we see using the HRT patch on 2.4.40, or with the RHT patch on 2.6.
Yes, preemptive kernels are cool.
>
> Now there is still no guarantee, but the statistical response is much
> better.
Its A LOT better in practice with HRT, and more or less good enough for interactive and multi-media uses.
>
> > I have some internal folks I've been assigned to help out that need
> > a low jitter time base to do some VoIP and need jitter < 250usec on
> > a ~2ms timer for the DSP computations to be do-able in user space.
> >
> > I would love to help get the existing HRT patches updated so as to
> > be acceptible, or failing that perhaps write a simple low jitter
> > time base driver vareant of the rtc driver.
>
> If it's appropriate for your application, just use one of the existing
> real-time linuxes (RTAI etc.). They all offer high-res timers and
> will give much better VoIP guarantees than any of the high-res timer
> patches for non-real-time linux.
>
Nope, we need something thats in the future typical distribution or this product is not viable.
This isn't an embedded gadgit these guys are working on, so shipping an HRT patched kernel
is a show stopper for the product.
> If, however, you can't do that, consider: on i386 HZ is currently
> 1000. So your request for 2ms timer is perfectly satisfiable using
> the standard timers. Remember to turn on CONFIG_PREEMPT, and use a
> SCHED_FIFO sceduling policy.
>
They tested that a long time ago, an I re-tested it recently. It doesn't work.
The Jitter is just way too high doing this without HR timers.
Check out the non-HRT timer code it rounds up to the next jiffies, always.
Running with the HRT patch, we get a lot closer to what is being asked for.
> If you measure the jitter and find it is unacceptable, be aware that
> none of the high-res timer patches for non-real-time linux will
> improve that.
Not true. The HRT patch does indeed improve things a lot. In fact it more or less does the job and it
enables the application. Its not perfect, but its good.
The high res timer patch re-programs the PIT to produce an interrupt as close to the timeout as it
can, where just the jiffies clock will wake up on the following jiffies tick. On average 1 jiffies late! Thats
a LOT of jitter. If you look at the code and follow through the logic, if you ask for a 2ms sleep, you are basically
going to get a 3ms sleep. If you ask for a 1.1ms sleep you get a 2ms (with random larger jitters) sleep.
To change this without doing some of the things in the HRT patch opens up the timer code to waking up
the process too early. Also a bad thing.
This just isn't good enough for an entire class of applications that could exist on linux if it weren't for this issue.
>
> > Yup, and the human ear is even more sensitive.
> > Busted lip synch on video playback is embarassing under linux.
>
> Lip sync isn't a problem for buffered audio+video, if the playback
> code is able to adapt to the sound card's slight deviation from the
> nominal sample rate. The sound card itself provides the regular
> clock. A small difference between audio and video times is ok, as
> long as it stays consistent.
>
> The difficulty occurs with two-way communication, i.e. VoIP and video,
> when you can't buffer much.
>
Communications is definitely a harder problem calling for good low jitter time base services
> > My faverate flash animation web sites have a hard time with this as well.
>
> Btw, I noticed that flash animations seem visually smoother on
> Netscape 4 than Mozilla 1.2, on the same fast box running 2.6.
> Strange -- do they have different flash implementations?
>
I don't know, but my home box doesn't play back flash too well when booted into Mandrake or Fedora, where
you-know-who's OS works just fine. Its a BP-6 box, not too speedy. Regardless, my point is that without
an OS standard low jitter time base in the OS all the ISV's will be cobbling together there own hacks to get
low jitter time bases for their applications. Some will work well, others will be flaky, more will have coexistence
issues sharing time base sources like the /dev/rtc.
If the OS provides such support they would all tend to do the same thing and programs
needing this type of time base features would all just work better.
> > Linux needs a low jitter time base standard for desktop multi-media
> > applications of many types.
>
> That's one of the reasons why HZ was changed to 1000 on x86 for 2.6
> kernels, and the major motivation for adding CONFIG_PREEMPT.
>
I know, but the current solution still isn't good enough, on a number of levels.
--mgross
Mark Gross wrote:
> > If, however, you can't do that, consider: on i386 HZ is currently
> > 1000. So your request for 2ms timer is perfectly satisfiable using
> > the standard timers. Remember to turn on CONFIG_PREEMPT, and use a
> > SCHED_FIFO sceduling policy.
>
> Check out the non-HRT timer code it rounds up to the next jiffies, always.
You said you wanted a _2ms_ timer. Rounded up to the next jiffie,
that's... 2ms!
> Running with the HRT patch, we get a lot closer to what is being asked for.
Ok.
> > If you measure the jitter and find it is unacceptable, be aware that
> > none of the high-res timer patches for non-real-time linux will
> > improve that.
>
> Not true. The HRT patch does indeed improve things a lot. In fact
> it more or less does the job and it enables the application. Its
> not perfect, but its good.
Ok. My point was theoretical and I got it wrong, you're right and you
tried it. :)
> The high res timer patch re-programs the PIT to produce an interrupt
> as close to the timeout as it can, where just the jiffies clock will
> wake up on the following jiffies tick. On average 1 jiffies late!
> Thats a LOT of jitter. If you look at the code and follow through
> the logic, if you ask for a 2ms sleep, you are basically going to
> get a 3ms sleep. If you ask for a 1.1ms sleep you get a 2ms (with
> random larger jitters) sleep.
Yes. The point is that the added delay with the standard timers is
predictable, so it is possible to structure your program around that,
synchronising to the jiffies clock: have your program tick every
1.99ms or whatever that _actual_ rate of HZ/2 is on 2.6 x86 kernels.
(I gather the jiffie is slightly shorter than 1ms due to timer chip
limitation).
I don't see that the unpredictable part of the jitter would be
improved with high res timers: the unpredictable part being due to
disabled preemption, other interrupts etc.
That's what I meant by jitter, sorry for the lack of precision (no pun
intended).
> To change this without doing some of the things in the HRT patch opens up the timer code to waking up
> the process too early. Also a bad thing.
That's what I did with my old "Snake" program: determine when select()
will round up, and then wake up early and busy-wait in a loop calling
gettimeofday() until the precise time arrives.
It's not good, although the busy wait is limited to the length of 1
jiffie, or less if you can structure your program to compute
synchronised with the jiffie clock.
> This just isn't good enough for an entire class of applications that
> could exist on linux if it weren't for this issue.
Hmm.
For VoIP, I'm wondering why you need a timebase other than the sound
card. Won't it provide an interrupt for every new sound fragment?
> > > Linux needs a low jitter time base standard for desktop multi-media
> > > applications of many types.
> >
> > That's one of the reasons why HZ was changed to 1000 on x86 for 2.6
> > kernels, and the major motivation for adding CONFIG_PREEMPT.
>
> I know, but the current solution still isn't good enough, on a
> number of levels.
To demonstrate that 1000Hz ticks aren't good enough, because you need
much smaller jitter than 1ms on "ordinary machines" i.e. standard
distros, you'll have to demonstrate that you really are seeing much
smaller jitter than 1ms in your HRT-patched kernels and that it makes
a useful difference.
The pre-emptive patches was initially rejected, but Linus changed his
mind after a lot of good experimental data showing significant and
consistent improvements in latency statistics, the fact that the
patches were remarkeably non-invasive (because most of the work had
been done to support fine-grained SMP by then), and perhaps most
importantly, and surprisingly, I/O performance improved.
So there is hope with HRT, but it needs more than an implementation to
get into the standard tree (IMHO): it has to be fairly small,
non-invasive, not harm existing performance, and backed by convincing
experimental data showing worthwhile improvements.
On the bright side, HRT makes it possible to eliminate the jiffie tick
entirely, which is quite likely to be good for performance and power
consumption. The objection to that has been that changing code which
depends on the timer tick to not use it any more would complicate that
code without much gain, and it's just not worth complicating anything
for it. But maybe, as for kernel pre-emption, it will turn out
simpler than expected.
-- Jamie
On Wednesday 17 March 2004 12:07, Jamie Lokier wrote:
> That's what I did with my old "Snake" program: determine when select()
> will round up, and then wake up early and busy-wait in a loop calling
> gettimeofday() until the precise time arrives.
>
> It's not good, although the busy wait is limited to the length of 1
> jiffie, or less if you can structure your program to compute
> synchronised with the jiffie clock.
>
Is this not a very strong argument for some type of HRT support in the kernel?
> > This just isn't good enough for an entire class of applications that
> > could exist on linux if it weren't for this issue.
>
> Hmm.
>
> For VoIP, I'm wondering why you need a timebase other than the sound
> card. Won't it provide an interrupt for every new sound fragment?
>
I don't know the application the team I'm trying to help out well enough to say if thats workable.
We are exploring different "plan -B"s in case we can't get George's HRT patch updated and
into the base. I would rather put my effort into helping George and the HRT
implementation than writing another RTC like driver with crappy non-posix interface.
> > > > Linux needs a low jitter time base standard for desktop multi-media
> > > > applications of many types.
> > >
> > > That's one of the reasons why HZ was changed to 1000 on x86 for 2.6
> > > kernels, and the major motivation for adding CONFIG_PREEMPT.
> >
> > I know, but the current solution still isn't good enough, on a
> > number of levels.
>
> To demonstrate that 1000Hz ticks aren't good enough, because you need
> much smaller jitter than 1ms on "ordinary machines" i.e. standard
> distros, you'll have to demonstrate that you really are seeing much
> smaller jitter than 1ms in your HRT-patched kernels and that it makes
> a useful difference.
I'm trying!
I think I have demostrated that you cannot get a 1ms timer
by code inspection.
I've also demonstrated that asking for a 2ms periodic wake up will
result in a 3ms periodic wake up.
The application I'm trying to enable spec's out a 0.25ms jitter on a 2ms
periodic event clock to support doing some audio dsp. However; I
cannot argue the validity of the 0.25ms requierment. I think its a valid requierment.
Attached is the jitter test using the HRT. Running on 2.6.3 + a rebase of the source
forge patch gets me a 2ms wave form with some jitter < 0.25ms. On my oscilloscope
it "looks" like about +/- 0.2 ms.
It makes a useful difference today.
I should state the HRT patch for 2.6 on the source forge site is a bit out
of date WRT 2.6 and needs some updating. It works for the test application, but has
some problems that don't happen with the 2.4 version of the patch. George
tells me he's rolling in some fixes he has binned up "soon". Running the same test
using the 2.4.20 + HRT + preemption patch gives less jitter than the 2.6 version.
I'm here to help get that fixed up for 2.6.
The point here is that the rebased version of the current 2.6 HRT patch works good
enough for the application I'm worried about.
>
> The pre-emptive patches was initially rejected, but Linus changed his
> mind after a lot of good experimental data showing significant and
> consistent improvements in latency statistics, the fact that the
> patches were remarkeably non-invasive (because most of the work had
> been done to support fine-grained SMP by then), and perhaps most
> importantly, and surprisingly, I/O performance improved.
>
> So there is hope with HRT, but it needs more than an implementation to
> get into the standard tree (IMHO): it has to be fairly small,
> non-invasive, not harm existing performance, and backed by convincing
> experimental data showing worthwhile improvements.
>
Hope is good.
> On the bright side, HRT makes it possible to eliminate the jiffie tick
> entirely, which is quite likely to be good for performance and power
> consumption. The objection to that has been that changing code which
> depends on the timer tick to not use it any more would complicate that
> code without much gain, and it's just not worth complicating anything
> for it. But maybe, as for kernel pre-emption, it will turn out
> simpler than expected.
Perhaps.
--mgross
Jamie Lokier wrote:
> So there is hope with HRT, but it needs more than an implementation to
> get into the standard tree (IMHO): it has to be fairly small,
> non-invasive, not harm existing performance, and backed by convincing
> experimental data showing worthwhile improvements.
Looking at the high-res timer stuff, it's somewhat similar to what
RTAI does (reprogram timer chip, use nanoseconds for computations,
provide API for ease of use, etc.) except that it can't guarantee
hard-rt, and it's integrated directly with Linux's scheduling
whereas RTAI has its own scheduler and lives as a module.
It's not my intention to debate which is better, I'll leave that
for another day. What I'm interested in, however, is that there is
a common functionality that all such facilities can use to achieve/
deliver hard-rt.
I'm thinking here of Adeos. It's the smallest subset of services
required for obtaining hard-rt in the kernel, and it's fairly
non-invasive (not to mention that configuring it out results in no
changes to the kernel.) So while Adeos doesn't provide abstract
services such as "tasks" or "timers", it does provide the basic
mechanism for all add-ons that want to provide these to obtain
the hard-rt from Adeos using an architecture-independent API.
Here are a few examples of software that can obtain hard-rt with
Adeos:
- RT Executives: Currently RTAI uses Adeos on x86 and a port of
RTLinux/GPL to Adeos is planned. Adeos, however, isn't limited to
either of these executives, and could easily be used by any other
RT executive to sit side-by-side with Linux and other kernels.
- hard-rt drivers: It's fairly trivial for a driver to hook into the
Adeos pipeline and obtain hard-rt without using either RTAI or
RTLinux. In that case, there's just the standard Linux kernel with
a hard-rt driver side-by-side atop Adeos.
- HRT: Any mechanism that modifies the PIT can then export timer
services to drivers for providing them with deterministic timer
response times. Granted there would be no integration with the
current Linux scheduler, but the added advantage is that HRT can
live as a loadable module. Scheduling/notifying of user-space
processes using such HRT is possible; RTAI's hard-rt scheduling
of normal Linux processes being an example.
Actually, most software that needs hard-rt can live as loadable
modules once Adeos is integrated in the kernel.
The Adeos patches are available here for those who are interested:
http://download.gna.org/adeos/patches/
P.S.: Before anyone comes back shouting after looking at the #ifdefs
used to modify _existing_ kernel files in the current Adeos patches,
please keep in mind that they are mainly there because they make it
fairly trivial to create patches for new kernels. When cleaning up
the patches for inclusion, most of these would disappear.
Karim
--
Author, Speaker, Developer, Consultant
Pushing Embedded and Real-Time Linux Systems Beyond the Limits
http://www.opersys.com || [email protected] || 1-866-677-4546
I see we have gone from a desire for soft-rt high-res timers to
pushing hard-rt :)
Karim Yaghmour wrote:
> I'm thinking here of Adeos. It's the smallest subset of services
> required for obtaining hard-rt in the kernel,
In this case, it's not clear that hard-rt is desirable. VoIP doesn't
like occasional glitches, but it can tolerate them and must do so when
a machine is overloaded, e.g. trying to handle too many scheduling
objectives at once. I don't know much about the original poster's
problem, that's just my take on VoIP.
> and it's fairly non-invasive (not to mention that configuring it out
> results in no changes to the kernel.) So while Adeos doesn't provide
> abstract services such as "tasks" or "timers", it does provide the
> basic mechanism for all add-ons that want to provide these to obtain
> the hard-rt from Adeos using an architecture-independent API.
There is also Bernard Kuhn's recent "real-time interrupts" patch for
2.6 which could be utilised:
http://home.t-online.de/home/Bernhard_Kuhn/rtirq/20040304/rtirq.html
http://home.t-online.de/home/Bernhard_Kuhn/rtirq/20040304/rtirq-2.6.2-20040304.tar.bz2
> Actually, most software that needs hard-rt can live as loadable
> modules once Adeos is integrated in the kernel.
A couple of questions.
Can Adeos-registed timer callbacks call the same functions as normal
timer callbacks, schedule userspace, and kick network I/O with near-RT
guarantees? Or do they run in a non-kernel context?
(Mark can say whether a normal context, i.e. with system calls, memory
allocation and network I/O, is required for Intel's VoIP application.)
Can Adeos itself be loaded as a module which overrides normal non-RT
kernel interrupt and timer functions? If it can be kept out of the
standard kernel, but loaded when needed, that would be nice.
One more thing would help, IMHO, in getting any fancy interrupt system
in: if it balanced the different execution contexts, i.e. limit total
CPU taken in high priority, low priority interrupts, task queues
etc. in an efficient yet fair way, such that overall throughput was
improved over standard kernels in cases such as network overload.
NAPI does this at the network card level, but there is no reason why
balancing CPU among contexts cannot be done at the generic interrupt
scheduling level, making it work for all I/O devices without special
driver support.
-- Jamie
Jamie Lokier wrote:
> I see we have gone from a desire for soft-rt high-res timers to
> pushing hard-rt :)
:D
> In this case, it's not clear that hard-rt is desirable. VoIP doesn't
> like occasional glitches, but it can tolerate them and must do so when
> a machine is overloaded, e.g. trying to handle too many scheduling
> objectives at once. I don't know much about the original poster's
> problem, that's just my take on VoIP.
I agree that VoIP doesn't "require" hard-rt, I have no issue with that.
I was expanding on the specific discussion of the HRT mechanism, not
the intended usage itself. Let me know if you'd rather see this discussed
separately.
> There is also Bernard Kuhn's recent "real-time interrupts" patch for
> 2.6 which could be utilised:
The first implementation of such a mechanism for Linux was done by David
Schleef a few years back and it was called the "no-warm air" patch (long
story.) Basically, though, I think this is the wrong approach because the
resulting behavior is very much CPU-dependent (interrupt priority
mechanisms being CPU-specific.) With Adeos, you get the same API and
the same behavior regardless of underlying architecture. Adeos' pipeline
actually provides the same net effect as playing with the int controllers,
except that it's totally hardware independent. No to mention that a
nanokernel's behavior can be modified/extended while a CPU's behavior is
pretty much ... hmmm, well, fixed in silicone ...
> A couple of questions.
Sure.
> Can Adeos-registed timer callbacks call the same functions as normal
> timer callbacks, schedule userspace, and kick network I/O with near-RT
> guarantees? Or do they run in a non-kernel context?
The Adeos-registered callbacks cannot _directly_ call kernel functions.
They can, however, trigger virtual IRQs that, once propagated to Linux,
can then take care of such calls. Here are the relevant Adeos functions
(see http://home.gna.org/adeos/doc/api/interface_8h.html for the full
API and its usage):
unsigned adeos_alloc_irq (void)
> Allocates a system-wide pipelined virtual interrupt. Virtual interrupts
> are pseudo-interrupt channels which are handled in exactly the same way
> than their hardware-generated counterparts. This is a basic, one-way
> only, inter-domain communication system allowing a domain to trigger the
> execution of a handler inside cooperating domains using the interrupt
> semantics (see adeos_trigger_irq()). A domain can trap the virtual
> interrupt using the adeos_virtualize_irq() service. Any domain can use
> adeos_virtualize_irq() on a virtual interrupt even if such interrupt was
> allocated by another domain.
int adeos_trigger_irq (unsigned irq)
> Simulates the occurrence of an interrupt. Adeos acts as if the specified
> interrupt had been received from the underlying hardware, and starts
> propagating it down the pipeline. The calling domain might be immediately
> preempted on behalf of this routine if the interrupt is delivered to a more
> prioritary domain.
Using these basic functions and the relevant callbacks it's fairly simple
to have the hard-rt component do the critical stuff and immediately signal
a Linux-aware handler to "call the same functions as normal timer callbacks,
schedule userspace, and kick network I/O with near-RT guarantees." It
should also be possible to wrap these primitives around higher-level
functions such as HRT, for example.
Side note: virtual IRQs is something CPU int controller silicone is
incapable of.
> Can Adeos itself be loaded as a module which overrides normal non-RT
> kernel interrupt and timer functions? If it can be kept out of the
> standard kernel, but loaded when needed, that would be nice.
Sure, Adeos can be compiled as a module and loaded at runtime, but it does
require a few basic things to be modified within the kernel in order to
allow runtime loading.
> One more thing would help, IMHO, in getting any fancy interrupt system
> in: if it balanced the different execution contexts, i.e. limit total
> CPU taken in high priority, low priority interrupts, task queues
> etc. in an efficient yet fair way, such that overall throughput was
> improved over standard kernels in cases such as network overload.
> NAPI does this at the network card level, but there is no reason why
> balancing CPU among contexts cannot be done at the generic interrupt
> scheduling level, making it work for all I/O devices without special
> driver support.
Hmm... IOW, Adeos wouldn't implement a pipeline, but an interrupt
scheduler? I guess that's possible, but I can see things getting very
confusing very fast for driver developers because of the hard-rt issues,
not to mention code complexity in the interrupt scheduler for avoiding
starvation, missed deadlines, overruns, etc. Given that Adeos itself is
a nanokernel it really would make little sense for it to act as the
scheduler of any interrupts within any of its clients. It could certainly
have an OS scheduler, but that's different from you're asking for. There
is no reason, however, for not having an additional Linux-specific
mechanism for prioritizing incoming Linux interrupts. For example, if I
understand it correctly TimeSys has implemented some form of interrupt
threading in their kernel. Maybe that can be used at the Linux level in
addition to having a basic bare-bones hard-RT mechanism for delivering
interrupts. While I can't expand on this, since I haven't seen their
code, I think something similar may be better adapted in order to
preserve existing driver behavior.
Karim
--
Author, Speaker, Developer, Consultant
Pushing Embedded and Real-Time Linux Systems Beyond the Limits
http://www.opersys.com || [email protected] || 1-866-677-4546
On Thu Mar 18, 2004 at 10:23:55AM -0500, Karim Yaghmour wrote:
> except that it's totally hardware independent. No to mention that a
> nanokernel's behavior can be modified/extended while a CPU's behavior is
> pretty much ... hmmm, well, fixed in silicone ...
Silicone? You expect CPU behavior to jiggle around
a lot I suppose. ;-)
-Erik
--
Erik B. Andersen http://codepoet-consulting.com/
--This message was written using 73% post-consumer electrons--
Erik Andersen wrote:
> Silicone? You expect CPU behavior to jiggle around
> a lot I suppose. ;-)
... I'm sure that it would sometimes help explain odd system behavior :)
Speaking of sexy, though, you gotta love these virtual interrupts.
Karim
--
Author, Speaker, Developer, Consultant
Pushing Embedded and Real-Time Linux Systems Beyond the Limits
http://www.opersys.com || [email protected] || 1-866-677-4546