2.6.11 timeval_to_jiffies() wrong for ms resolution timers

2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Bhavesh P. Davda]

setitimer for 20ms was firing at 21ms, so I wrote a simple debug module
for 2.6.11.10 kernel on i386 to do something like this:

struct timeval tv;
unsigned long jif;

tv.tv_usec = 20000;
tv.tv_sec = 0;

jif = timeval_to_jiffies(&tv);
printk("%lu usec = %lu jiffies\n", tv.tv_usec, jif);

This yields:

20000 usec = 21 jiffies

Egad!

I looked at the timeval_to_jiffies() inline function in
include/linux/jiffies.h, and after pulling my hair for a few minutes
(okay almost an hour), I decided to ask much smarter people than myself
on why it is behaving this way, and what it would take to fix it so that
"20000 usec = 20 jiffies".

I got as far as this in figuring it out for i386:

HZ=1000
SEC_CONVERSION=4194941632
USEC_CONVERSION=2199357558
USEC_ROUND=2199023255551
USEC_JIFFIE_SC=41
SEC_JIFFIE_SC=22

Thanks in advance for saving me from going bald!

- Bhavesh

-- 
Bhavesh P. Davda | Distinguished Member of Technical Staff | Avaya |
1300 West 120th Avenue | B3-B03 | Westminster, CO 80234 | U.S.A. |
Voice/Fax: 303.538.4438 | bhavesh@avaya.com

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[George Anzinger]

Bhavesh P. Davda wrote:
> setitimer for 20ms was firing at 21ms, so I wrote a simple debug module
> for 2.6.11.10 kernel on i386 to do something like this:
> 
> struct timeval tv;
> unsigned long jif;
> 
> tv.tv_usec = 20000;
> tv.tv_sec = 0;
> 
> jif = timeval_to_jiffies(&tv);
> printk("%lu usec = %lu jiffies\n", tv.tv_usec, jif);
> 
> This yields:
> 
> 20000 usec = 21 jiffies
> 
> Egad!
> 
> I looked at the timeval_to_jiffies() inline function in
> include/linux/jiffies.h, and after pulling my hair for a few minutes
> (okay almost an hour), I decided to ask much smarter people than myself
> on why it is behaving this way, and what it would take to fix it so that
> "20000 usec = 20 jiffies".
> 
> I got as far as this in figuring it out for i386:
> 
> HZ=1000
> SEC_CONVERSION=4194941632
> USEC_CONVERSION=2199357558
> USEC_ROUND=2199023255551
> USEC_JIFFIE_SC=41
> SEC_JIFFIE_SC=22
> 
> Thanks in advance for saving me from going bald!

Well, I am already bald  :)

What you are missing is that the PIT can not generate a 1ms tick.  The best it 
can do is 999849 nanoseconds.  Given this we need to convert 20000 usec to not 
less than 2000usec worth of jiffies (time MUST always be rounded up).  20 
jiffies is 19.996980 usec so we need to use 21 (which is 20.996829 usec).

Note that TICK_NSEC and tick_nsec will both be 999849 nanoseconds.

If we do NOT account for this PIT issue, the result is a time drift that is 
outside of what ntp can handle...


-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Chris Friesen]

George Anzinger wrote:
> Bhavesh P. Davda wrote:
>> setitimer for 20ms was firing at 21ms

> If we do NOT account for this PIT issue, the result is a time drift that 
> is outside of what ntp can handle...

Still, it is non-intuitive that a multi-GHz machine can't wake you up 
more accurately than 1ms.

What about telling it to wake up a jiffy earlier, then checking whether 
the scheduling lag was enough to cause it to have waited the full 
specified time.  If not, put it to sleep for another jiffy.

Chris

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[George Anzinger]

Chris Friesen wrote:
> George Anzinger wrote:
> 
>> Bhavesh P. Davda wrote:
>>
>>> setitimer for 20ms was firing at 21ms
> 
> 
>> If we do NOT account for this PIT issue, the result is a time drift 
>> that is outside of what ntp can handle...
> 
> 
> Still, it is non-intuitive that a multi-GHz machine can't wake you up 
> more accurately than 1ms.
> 
> What about telling it to wake up a jiffy earlier, then checking whether 
> the scheduling lag was enough to cause it to have waited the full 
> specified time.  If not, put it to sleep for another jiffy.

The user is, of course, free to do what ever they would like.  For a more 
complete solution you might be interested in HRT (High Res Timers).  See my 
signature below.
> 
-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Chris Friesen]

George Anzinger wrote:
> Chris Friesen wrote:

>> What about telling it to wake up a jiffy earlier, then checking 
>> whether the scheduling lag was enough to cause it to have waited the 
>> full specified time.  If not, put it to sleep for another jiffy.

> The user is, of course, free to do what ever they would like.  

I actually meant doing this in the kernel.

 > For a
> more complete solution you might be interested in HRT (High Res 
> Timers).  See my signature below.

Yep.  One more patch to apply and worry about versions and maintenance. 
  Not enough of a demand for us to be able to use it, at least at this 
point.

Chris

RE: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Davda, Bhavesh P (Bhavesh)]

> -----Original Message-----
> From: Chris Friesen [mailto:cfriesen@nortel.com] 
> Sent: Wednesday, May 25, 2005 12:08 PM
> To: george@mvista.com
> Cc: Davda, Bhavesh P (Bhavesh); linux-kernel@vger.kernel.org
> Subject: Re: 2.6.11 timeval_to_jiffies() wrong for ms 
> resolution timers
> 
> George Anzinger wrote:
> > Chris Friesen wrote:
> 
> >> What about telling it to wake up a jiffy earlier, then checking 
> >> whether the scheduling lag was enough to cause it to have 
> waited the 
> >> full specified time.  If not, put it to sleep for another jiffy.
> 
> > The user is, of course, free to do what ever they would like.  
> 
> I actually meant doing this in the kernel.

Ditto.

> 
>  > For a
> > more complete solution you might be interested in HRT (High Res 
> > Timers).  See my signature below.
> 
> Yep.  One more patch to apply and worry about versions and 
> maintenance. 
>   Not enough of a demand for us to be able to use it, at 
> least at this 
> point.
> 
> Chris

Ditto ditto :)

BTW, this reminds me an aweful lot of TH2GT2G, and Deep Thought taking 7.5 million years to come up with the answer "42!"

Me: Hey Deep Thought! What's 20 us converted into jiffies?

Deep Thought: Let's see: after accounting for all kinds of underflow and overflow possibilities, and extending the operands to 64-bit to retain the best precision, and crunching through a few complex macros, the answer you're looking for is... Is... Is... "21!" The real problem is: You didn't ask me the right question. You should have asked me "What's 19 us converted into jiffies?"

On a more serious note: what is a real-time (read SCHED_FIFO/SCHED_RR) task to use to get millisecond accuracy wakeup timing services from the kernel? i.e. what are the alternatives to setitimer() that wake up the task exactly at the interval that is requested of it? You mention high-res timers as a possibility, but in the form of a patch. What's available in mainline unpatched?

Thanks

- Bhavesh



Bhavesh P. Davda | Distinguished Member of Technical Staff | Avaya |
1300 West 120th Avenue | B3-B03 | Westminster, CO 80234, U.S.A. |
Voice/Fax: (303) 538-4438 | bhavesh@avaya.com 

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[George Anzinger]

~
> On a more serious note: what is a real-time (read SCHED_FIFO/SCHED_RR) task to use to get millisecond accuracy wakeup timing services from the kernel? i.e. what are the alternatives to setitimer() that wake up the task exactly at the interval that is requested of it? You mention high-res timers as a possibility, but in the form of a patch. What's available in mainline unpatched?
> 
We ARE trying to get this into the main line, but save the patch, there is no 
way to get millisecond accuracy in the kernel OR in user land.  Never has been! 
  That is why the patch exists.  There was an effort by some university folks 
prior to the HRT stuff, but AFAIK it is not supported or uptodate.

Also, you should be aware that even with precise timers, there is still latency 
in the kernel AND it is in the millisecond range.  Again, folks are working on 
that in the form of a patch (see the the real time patch by Ingo and friends).

As for jiffies vs time, my understanding from senior time folks is that 1/HZ as 
a resolution is just an approximation.  We do the best we can but the x86 is 
really the PITs (pun intended) when it comes to time keeping resources.  If you 
really want millisecond accuracy, you may need to consider another platform....

-- 
George Anzinger   george@mvista.com
HRT (High-res-timers):  http://sourceforge.net/projects/high-res-timers/

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Thomas Gleixner]

On Wed, 2005-05-25 at 13:02 -0700, George Anzinger wrote:
> We ARE trying to get this into the main line, but save the patch, there is no 
> way to get millisecond accuracy in the kernel OR in user land.  Never has been! 
>   That is why the patch exists.  There was an effort by some university folks 
> prior to the HRT stuff, but AFAIK it is not supported or uptodate.

It's up to date and supported, if you are talking about the KURT
project. Just the website is hopelessly out of date.

> As for jiffies vs time, my understanding from senior time folks is that 1/HZ as 
> a resolution is just an approximation.  We do the best we can but the x86 is 
> really the PITs (pun intended) when it comes to time keeping resources.  If you 
> really want millisecond accuracy, you may need to consider another platform....

Why so ? Accepted PIT, is a PITA due to the ISA access penalty, but it
still allows you to run timers below millisecond accuracy.

tglx

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Olivier Croquette]

George Anzinger wrote:
> If you really want millisecond accuracy, you may 
> need to consider another platform....

Are some platform known for the precision of their timers?

Could hardware help? (like a PCI timer card)

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Richard B. Johnson]

On Thu, 26 May 2005, Olivier Croquette wrote:

>
>
> George Anzinger wrote:
>> If you really want millisecond accuracy, you may
>> need to consider another platform....
>
> Are some platform known for the precision of their timers?
>
> Could hardware help? (like a PCI timer card)
>

You can make hardware timers with picosecond resolution. The problem
is that the only way to use that kind of resolution is to program
some hardware to do something when the previously-set time is up.

A CPU (any CPU) takes a variable amount of time to branch when
a hardware interrupt occurs. The time to branch from what it's
doing to some software to handle the interrupt depends upon what
it is doing and even how long it has been doing what it's doing.
This is because modern CPUs have caches both for the instruction
fetching and for data.

This variable amount of time is called jitter. It may be several
tens of microseconds with ix86 machines and even greater with
some other CPUs like the PPC. CPUs that run in a flat mode with
no instruction cache such as some DSPs have jitter that is much
lower (TMS320C30 comes to mind).

The time for a sleeping (waiting) task to get the CPU is much
greater than the jitter. Once in the ISR, some wake-up call
is "scheduled" and the interrupt returns. A CPU hog may have
been using the CPU when the interrupt occurred. It will continue
to use the CPU until its time-slot (quantum) has expired. This
could be a whole millisecond if HZ is 1000, 10 milliseconds if
100. It's only then that your sleeping task gets awakened
by the interrupting event.

So, accurate waking up is not guaranteed on any multi-user,
multitasking system because you don't know what a user has
been doing with the CPU. On a dedicated machine, one can
have tasks that are most always sleeping or waiting for
I/O so, the latency can come way down. However, signaling
a task, based upon some time will never be very accurate
anywhere.

For accurate events, you need to make hardware that contains
a time-base and an event-counter. Software sets the event-counter.
When the event-counter equals the time-base, the hardware
does something. That, it can do accurately.

Cheers,
Dick Johnson
Penguin : Linux version 2.6.11.9 on an i686 machine (5537.79 BogoMips).
  Notice : All mail here is now cached for review by Dictator Bush.
                  98.36% of all statistics are fiction.

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Lee Revell]

On Thu, 2005-05-26 at 14:10 -0400, Richard B. Johnson wrote:
> The time for a sleeping (waiting) task to get the CPU is much
> greater than the jitter. Once in the ISR, some wake-up call
> is "scheduled" and the interrupt returns. A CPU hog may have
> been using the CPU when the interrupt occurred. It will continue
> to use the CPU until its time-slot (quantum) has expired. This
> could be a whole millisecond if HZ is 1000, 10 milliseconds if
> 100. It's only then that your sleeping task gets awakened
> by the interrupting event.
> 
> So, accurate waking up is not guaranteed on any multi-user,
> multitasking system because you don't know what a user has
> been doing with the CPU. On a dedicated machine, one can
> have tasks that are most always sleeping or waiting for
> I/O so, the latency can come way down. However, signaling
> a task, based upon some time will never be very accurate
> anywhere.

Not quite, if your sleeping task has higher priority than the CPU hog it
will preempt the CPU hog immediately on return from the interrupt.
Unless you've disabled preemption of course, which would be stupid in
this case.

Lee

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[George Anzinger]

Lee Revell wrote:
> On Thu, 2005-05-26 at 14:10 -0400, Richard B. Johnson wrote:
> 
>>The time for a sleeping (waiting) task to get the CPU is much
>>greater than the jitter. Once in the ISR, some wake-up call
>>is "scheduled" and the interrupt returns. A CPU hog may have
>>been using the CPU when the interrupt occurred. It will continue
>>to use the CPU until its time-slot (quantum) has expired. This
>>could be a whole millisecond if HZ is 1000, 10 milliseconds if
>>100. It's only then that your sleeping task gets awakened
>>by the interrupting event.
>>
>>So, accurate waking up is not guaranteed on any multi-user,
>>multitasking system because you don't know what a user has
>>been doing with the CPU. On a dedicated machine, one can
>>have tasks that are most always sleeping or waiting for
>>I/O so, the latency can come way down. However, signaling
>>a task, based upon some time will never be very accurate
>>anywhere.
> 
> 
> Not quite, if your sleeping task has higher priority than the CPU hog it
> will preempt the CPU hog immediately on return from the interrupt.
> Unless you've disabled preemption of course, which would be stupid in
> this case.

And even then the task would need to be in the kernel and would be preempted 
when it exits the kernel.


-- 
George Anzinger   george@mvista.com
HRT (High-res-timers):  http://sourceforge.net/projects/high-res-timers/

Re: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Lee Revell]

On Thu, 2005-05-26 at 12:24 -0700, George Anzinger wrote:
> Lee Revell wrote:
> > On Thu, 2005-05-26 at 14:10 -0400, Richard B. Johnson wrote:
> > 
> >>The time for a sleeping (waiting) task to get the CPU is much
> >>greater than the jitter. Once in the ISR, some wake-up call
> >>is "scheduled" and the interrupt returns. A CPU hog may have
> >>been using the CPU when the interrupt occurred. It will continue
> >>to use the CPU until its time-slot (quantum) has expired. This
> >>could be a whole millisecond if HZ is 1000, 10 milliseconds if
> >>100. It's only then that your sleeping task gets awakened
> >>by the interrupting event.
> >>
> >>So, accurate waking up is not guaranteed on any multi-user,
> >>multitasking system because you don't know what a user has
> >>been doing with the CPU. On a dedicated machine, one can
> >>have tasks that are most always sleeping or waiting for
> >>I/O so, the latency can come way down. However, signaling
> >>a task, based upon some time will never be very accurate
> >>anywhere.
> > 
> > 
> > Not quite, if your sleeping task has higher priority than the CPU hog it
> > will preempt the CPU hog immediately on return from the interrupt.
> > Unless you've disabled preemption of course, which would be stupid in
> > this case.
> 
> And even then the task would need to be in the kernel and would be preempted 
> when it exits the kernel.
> 

Right, and normally the sleeping task would be woken up even if it had
the same static priority as the CPU hog as the scheduler should favor
event driven proceses.

Lee

RE: 2.6.11 timeval_to_jiffies() wrong for ms resolution timers

[Davda, Bhavesh P (Bhavesh)]

Awefully sorry about the line-breaks (or absence thereof!)

Stupid Outlook that corporate IT forces us to use!

And I meant 20 ms, not 20 us, of course...

- Bhavesh

Bhavesh P. Davda | Distinguished Member of Technical Staff | Avaya |
1300 West 120th Avenue | B3-B03 | Westminster, CO 80234, U.S.A. |
Voice/Fax: (303) 538-4438 | bhavesh@avaya.com

 

> -----Original Message-----
> From: Davda, Bhavesh P (Bhavesh) 
> Sent: Wednesday, May 25, 2005 1:07 PM
> To: 'Chris Friesen'; 'george@mvista.com'
> Cc: 'linux-kernel@vger.kernel.org'
> Subject: RE: 2.6.11 timeval_to_jiffies() wrong for ms 
> resolution timers
> 
> > -----Original Message-----
> > From: Chris Friesen [mailto:cfriesen@nortel.com] 
> > Sent: Wednesday, May 25, 2005 12:08 PM
> > To: george@mvista.com
> > Cc: Davda, Bhavesh P (Bhavesh); linux-kernel@vger.kernel.org
> > Subject: Re: 2.6.11 timeval_to_jiffies() wrong for ms 
> > resolution timers
> > 
> > George Anzinger wrote:
> > > Chris Friesen wrote:
> > 
> > >> What about telling it to wake up a jiffy earlier, then checking 
> > >> whether the scheduling lag was enough to cause it to have 
> > waited the 
> > >> full specified time.  If not, put it to sleep for another jiffy.
> > 
> > > The user is, of course, free to do what ever they would like.  
> > 
> > I actually meant doing this in the kernel.
> 
> Ditto.
> 
> > 
> >  > For a
> > > more complete solution you might be interested in HRT (High Res 
> > > Timers).  See my signature below.
> > 
> > Yep.  One more patch to apply and worry about versions and 
> > maintenance. 
> >   Not enough of a demand for us to be able to use it, at 
> > least at this 
> > point.
> > 
> > Chris
> 
> Ditto ditto :)
> 
> BTW, this reminds me an aweful lot of TH2GT2G, and Deep 
> Thought taking 7.5 million years to come up with the answer "42!"
> 
> Me: Hey Deep Thought! What's 20 us converted into jiffies?
> 
> Deep Thought: Let's see: after accounting for all kinds of 
> underflow and overflow possibilities, and extending the 
> operands to 64-bit to retain the best precision, and 
> crunching through a few complex macros, the answer you're 
> looking for is... Is... Is... "21!" The real problem is: You 
> didn't ask me the right question. You should have asked me 
> "What's 19 us converted into jiffies?"
> 
> On a more serious note: what is a real-time (read 
> SCHED_FIFO/SCHED_RR) task to use to get millisecond accuracy 
> wakeup timing services from the kernel? i.e. what are the 
> alternatives to setitimer() that wake up the task exactly at 
> the interval that is requested of it? You mention high-res 
> timers as a possibility, but in the form of a patch. What's 
> available in mainline unpatched?
> 
> Thanks
> 
> - Bhavesh
> 
> 
> 
> Bhavesh P. Davda | Distinguished Member of Technical Staff | Avaya |
> 1300 West 120th Avenue | B3-B03 | Westminster, CO 80234, U.S.A. |
> Voice/Fax: (303) 538-4438 | bhavesh@avaya.com 
>