Jan,

A timer interrupt is required each second to update the clock frequency
no matter what. In addition, a sweep is made through the associations to
see if a poll is pending. It would be in principle posssible to
implement a system of queues to avopid sweeping the associations each
second, but that would save very few cycles, add some more cycles and
additional complexity. My advice is to avoid the patch; however, be
advised if used it might not work in future as the code is further refined.

Dave

Jan Ceuleers wrote:
> I came across the following page:
>
> http://www.lesswatts.org/projects/powertop/known.php
>
> which says the following on ntpd:
>
> "By default, the ntp time synchronization daemon will wake up once per
> second, and will make the kernel do work on it's behalf even more. Red
> Hat has created a patch to ntp to fix this issue and ships it in their
> rawhide and FC7 ntp packages. You can download this patch from the
> Fedora cvs server."
>
> Has anyone here looked at that patch? Does it compromise correctness of
> the algorithms?
>
> Thanks, Jan

"David L. Mills" writes:

>Jan,

>A timer interrupt is required each second to update the clock frequency
>no matter what. In addition, a sweep is made through the associations to

I thought that the ntp daemon runs the per second routine only if the
kernel discipline is not available.
And Linux I thought has the kernel discipline.
Now of course I suspect that the kernel has to wake itself even more often
than once a second (eg the timer interrupt) and if it did not, the effect
on the time discipline would be pretty bad.


>see if a poll is pending. It would be in principle posssible to
>implement a system of queues to avopid sweeping the associations each
>second, but that would save very few cycles, add some more cycles and
>additional complexity. My advice is to avoid the patch; however, be
>advised if used it might not work in future as the code is further refined.

>Dave

>Jan Ceuleers wrote:
>> I came across the following page:
>>
>> http://www.lesswatts.org/projects/powertop/known.php
>>
>> which says the following on ntpd:
>>
>> "By default, the ntp time synchronization daemon will wake up once per
>> second, and will make the kernel do work on it's behalf even more. Red
>> Hat has created a patch to ntp to fix this issue and ships it in their
>> rawhide and FC7 ntp packages. You can download this patch from the
>> Fedora cvs server."
>>
>> Has anyone here looked at that patch? Does it compromise correctness of
>> the algorithms?
>>
>> Thanks, Jan

Bill,

Bill Unruh wrote:
> Now of course I suspect that the kernel has to wake itself even more often
> than once a second (eg the timer interrupt) and if it did not, the effect
> on the time discipline would be pretty bad.

The Linux kernel has recently gone tickless, meaning that it only
schedules a wakeup for itself at the first time that it knows a timer
will expire. A quick intro on that can be found here:

http://www.lesswatts.org/documentati.../#ticklessidle

Cheers, Jan

Jan Ceuleers wrote:

> The Linux kernel has recently gone tickless, meaning that it only
> schedules a wakeup for itself at the first time that it knows a timer
> will expire. A quick intro on that can be found here:
>

Given the Linux kernel developers' past history of breaking NTP, have
they made all the necessary enhancements to gettimeofday to ensure that
it progresses the kernel discipline correctly to account for the missing
updates. (Of course it also needs to do the same when it does schedule
a clock event.

Have they considered the resulting increased processing time, and more
importantly, variability in processing time of gettimeofday?

To really go tickless well with NTP you need to move the kernel time
discipline into the hardware!

David Woolley wrote:
> Have they considered the resulting increased processing time, and more
> importantly, variability in processing time of gettimeofday?

That's why I'm raising the question here. If anyone on the ntpd team has
contacts at Red Hat, a brief discussion about this would be of
considerable help.

KR, Jan

On Thu, May 15, 2008 at 06:51:24PM +0200, Jan Ceuleers wrote:
> I came across the following page:
>
> http://www.lesswatts.org/projects/powertop/known.php
>
> which says the following on ntpd:
>
> "By default, the ntp time synchronization daemon will wake up once per
> second, and will make the kernel do work on it's behalf even more. Red
> Hat has created a patch to ntp to fix this issue and ships it in their
> rawhide and FC7 ntp packages. You can download this patch from the
> Fedora cvs server."
>
> Has anyone here looked at that patch? Does it compromise correctness of
> the algorithms?

A bug report for this issue is here:
https://support.ntp.org/bugs/show_bug.cgi?id=802

There are two different patches, the first one is just looking ahead
for the next event and it should be safe to use (at least on Linux).
The second patch implements a queue timer, it is more complex and
harder to maintain. In the Fedora CVS is maintained the first patch,
a version for the latest stable ntp release can also be found there.

--
Miroslav Lichvar

Bill,

I have no idea what you are talking about in the timer interrupt issue.
By timer interrupt I mean the kernel facility to create a program
interrupt at specified times, in this case once each second. Even if the
kernel discipline is in use the one-second interrupt is still used to
scan for poll events and several other things, like key expiry,
interface scan, etc.

In modern machines a timer interupt takes about one microsecond and to
scan through the one-second code is really quick. So, we are talking
about an overhead in the order of .00001 percent. A more contentious
issue is that the interrupt could cause a swapped-out ntpd process to be
dragged back in. If this could be the case, the use of NTP is not
justified in the first place and should be replaced by something else.

Dave

Bill Unruh wrote:
> "David L. Mills" writes:
>
>
>>Jan,
>
>
>>A timer interrupt is required each second to update the clock frequency
>>no matter what. In addition, a sweep is made through the associations to
>
>
> I thought that the ntp daemon runs the per second routine only if the
> kernel discipline is not available.
> And Linux I thought has the kernel discipline.
> Now of course I suspect that the kernel has to wake itself even more often
> than once a second (eg the timer interrupt) and if it did not, the effect
> on the time discipline would be pretty bad.
>
>
>
>>see if a poll is pending. It would be in principle posssible to
>>implement a system of queues to avopid sweeping the associations each
>>second, but that would save very few cycles, add some more cycles and
>>additional complexity. My advice is to avoid the patch; however, be
>>advised if used it might not work in future as the code is further refined.
>
>
>>Dave
>
>
>>Jan Ceuleers wrote:
>>
>>>I came across the following page:
>>>
>>>http://www.lesswatts.org/projects/powertop/known.php
>>>
>>>which says the following on ntpd:
>>>
>>>"By default, the ntp time synchronization daemon will wake up once per
>>>second, and will make the kernel do work on it's behalf even more. Red
>>>Hat has created a patch to ntp to fix this issue and ships it in their
>>>rawhide and FC7 ntp packages. You can download this patch from the
>>>Fedora cvs server."
>>>
>>>Has anyone here looked at that patch? Does it compromise correctness of
>>>the algorithms?
>>>
>>>Thanks, Jan

"David L. Mills" writes:

>Bill,

>I have no idea what you are talking about in the timer interrupt issue.

The 18 or 100 or 250 or 1000 Hz timer interrupt.
And if they do not occur (lost ticks) problems arise.


>By timer interrupt I mean the kernel facility to create a program
>interrupt at specified times, in this case once each second. Even if the

Which I believe rides on the coattails of the harware time interrupt.

>kernel discipline is in use the one-second interrupt is still used to
>scan for poll events and several other things, like key expiry,
>interface scan, etc.

>In modern machines a timer interupt takes about one microsecond and to
>scan through the one-second code is really quick. So, we are talking
>about an overhead in the order of .00001 percent. A more contentious
>issue is that the interrupt could cause a swapped-out ntpd process to be
>dragged back in. If this could be the case, the use of NTP is not
>justified in the first place and should be replaced by something else.

Fair enough.

>Dave

>Bill Unruh wrote:
>> "David L. Mills" writes:
>>
>>
>>>Jan,
>>
>>
>>>A timer interrupt is required each second to update the clock frequency
>>>no matter what. In addition, a sweep is made through the associations to
>>
>>
>> I thought that the ntp daemon runs the per second routine only if the
>> kernel discipline is not available.
>> And Linux I thought has the kernel discipline.
>> Now of course I suspect that the kernel has to wake itself even more often
>> than once a second (eg the timer interrupt) and if it did not, the effect
>> on the time discipline would be pretty bad.
>>
>>
>>
>>>see if a poll is pending. It would be in principle posssible to
>>>implement a system of queues to avopid sweeping the associations each
>>>second, but that would save very few cycles, add some more cycles and
>>>additional complexity. My advice is to avoid the patch; however, be
>>>advised if used it might not work in future as the code is further refined.
>>
>>
>>>Dave
>>
>>
>>>Jan Ceuleers wrote:
>>>
>>>>I came across the following page:
>>>>
>>>>http://www.lesswatts.org/projects/powertop/known.php
>>>>
>>>>which says the following on ntpd:
>>>>
>>>>"By default, the ntp time synchronization daemon will wake up once per
>>>>second, and will make the kernel do work on it's behalf even more. Red
>>>>Hat has created a patch to ntp to fix this issue and ships it in their
>>>>rawhide and FC7 ntp packages. You can download this patch from the
>>>>Fedora cvs server."
>>>>
>>>>Has anyone here looked at that patch? Does it compromise correctness of
>>>>the algorithms?
>>>>
>>>>Thanks, Jan

Miroslav,

You said it exactly slam-dunk right on the head.

Timer queue facilities are tricky and can be absolutely awful to debug
when something doesn't work right. I know this, as I built what might
now be called a tickless kernel for the PDP11 fuzzball in 1979. It did
avoid program interrupts to increment timers, which was important in
those old, slow machines, but it did require considerable overhead to
scan, insert and remove queue entries and worry about hash tables.

If you have been with this project for many years, you know a timer
queue facility was once implemented in xntpd and carried over to early
ntpd. However, it was fragile, poorly implemented, impossible to
maintain and eventually was ripped out. You can understand my reluctance
to repeat that adventure. Over the years there have been a number of
occasions where somebody dumps something on the distributution and then
disappears. Ten years later I stumble over it because it has broken
something, then realize it never did work properly, so I rip it out.

But the real slam-dunk issue is who is going to maintain the facility if
it is incorporated in ntpd? How will it affect future enhancements? Is
it to be optional and enabled by defines and configure? If Linux folks
think it necessary and maintain it, nobody here needs to worry. However,
the Linux folks might have to worry if something in the distribution
changes and the patch doesn't work any more.

Dave

Miroslav Lichvar wrote:

> On Thu, May 15, 2008 at 06:51:24PM +0200, Jan Ceuleers wrote:
>
>>I came across the following page:
>>
>>http://www.lesswatts.org/projects/powertop/known.php
>>
>>which says the following on ntpd:
>>
>>"By default, the ntp time synchronization daemon will wake up once per
>>second, and will make the kernel do work on it's behalf even more. Red
>>Hat has created a patch to ntp to fix this issue and ships it in their
>>rawhide and FC7 ntp packages. You can download this patch from the
>>Fedora cvs server."
>>
>>Has anyone here looked at that patch? Does it compromise correctness of
>>the algorithms?
>
>
> A bug report for this issue is here:
> https://support.ntp.org/bugs/show_bug.cgi?id=802
>
> There are two different patches, the first one is just looking ahead
> for the next event and it should be safe to use (at least on Linux).
> The second patch implements a queue timer, it is more complex and
> harder to maintain. In the Fedora CVS is maintained the first patch,
> a version for the latest stable ntp release can also be found there.
>

On May 15, 9:28 pm, "David L. Mills" wrote:
>
> A timer interrupt is required each second to update the clock frequency
> no matter what. In addition, a sweep is made through the associations to
> see if a poll is pending. It would be in principle posssible to
> implement a system of queues to avopid sweeping the associations each
> second, but that would save very few cycles, add some more cycles and
> additional complexity.

NTP could set a reminder for itself not for the next second, in case
there's a poll pending, but for the minimum period left among all
polled servers. This would be pretty simple and power-friendly.

Mind you, a CPU uses orders of magnitude less power in a stand-by
state, even a simple halt-instruction, than running. See page 3 of
http://download.intel.com/technology...ol10_art03.pdf
for more info.

HTH

On May 16, 12:29 pm, "David L. Mills" wrote:
>
> In modern machines a timer interupt takes about one microsecond and to
> scan through the one-second code is really quick. So, we are talking
> about an overhead in the order of .00001 percent.

In terms of performance, yes, but in terms of power, no. If NTP gets
the CPU out of a deep stand-by state, then it may take hundreds of
milliseconds for the CPU to go back to that state. Moreover, NTP 1s-
timer may prevent the CPU from going to even deeper stand-by states.

With this in mind, if NTP wakes the CPU up in order to do nothing,
it's not doing the right thing, IMHO.

HTH

Evandro Menezes wrote:

> In terms of performance, yes, but in terms of power, no. If NTP gets
> the CPU out of a deep stand-by state, then it may take hundreds of
> milliseconds for the CPU to go back to that state. Moreover, NTP 1s-
> timer may prevent the CPU from going to even deeper stand-by states.

If it is in a deep stand by state, it is going to take a long time to
service the interrupts from the timing sources, and you are going to get
a large jitter on the time measurements.

The answer to the delay in getting back into standby is for applications
to have an API that can tell the kernel that they are going to sleep,
rather than using timeouts to deduce that.

This smacks of one size fits all. A system that needs accurate time,
most likely won't need to do a lot of intensive power saving. A system
that has extreme power management requirements probably doesn't need
precise time. If it does, it should use special hardware. E.g.
microncontrollers often completely stop the main oscillator, but have a
timer than runs on a completely separate, low power, oscillator.

Another problem you will get with putting the system into deep sleeps is
that the oscillator temperature is going to vary wildly.

Bill,

I've have reports of folks using kernel timer interrupts at 10,000 Hz in
Linux. That has nothing to do with ntpd, only the fact that ntpd expects
to be called by the kernel timer routines once per second.

Dave

> "David L. Mills" writes:
>
>
>>Bill,
>
>
>>I have no idea what you are talking about in the timer interrupt issue.
>
>
> The 18 or 100 or 250 or 1000 Hz timer interrupt.
> And if they do not occur (lost ticks) problems arise.
>
>
>
>>By timer interrupt I mean the kernel facility to create a program
>>interrupt at specified times, in this case once each second. Even if the
>
>
> Which I believe rides on the coattails of the harware time interrupt.
>
>
>>kernel discipline is in use the one-second interrupt is still used to
>>scan for poll events and several other things, like key expiry,
>>interface scan, etc.
>
>
>>In modern machines a timer interupt takes about one microsecond and to
>>scan through the one-second code is really quick. So, we are talking
>>about an overhead in the order of .00001 percent. A more contentious
>>issue is that the interrupt could cause a swapped-out ntpd process to be
>>dragged back in. If this could be the case, the use of NTP is not
>>justified in the first place and should be replaced by something else.
>
>
> Fair enough.
>
>
>>Dave
>
>
>>Bill Unruh wrote:
>>
>>>"David L. Mills" writes:
>>>
>>>
>>>
>>>>Jan,
>>>
>>>
>>>>A timer interrupt is required each second to update the clock frequency
>>>>no matter what. In addition, a sweep is made through the associations to
>>>
>>>
>>>I thought that the ntp daemon runs the per second routine only if the
>>>kernel discipline is not available.
>>>And Linux I thought has the kernel discipline.
>>>Now of course I suspect that the kernel has to wake itself even more often
>>>than once a second (eg the timer interrupt) and if it did not, the effect
>>>on the time discipline would be pretty bad.
>>>
>>>
>>>
>>>
>>>>see if a poll is pending. It would be in principle posssible to
>>>>implement a system of queues to avopid sweeping the associations each
>>>>second, but that would save very few cycles, add some more cycles and
>>>>additional complexity. My advice is to avoid the patch; however, be
>>>>advised if used it might not work in future as the code is further refined.
>>>
>>>
>>>>Dave
>>>
>>>
>>>>Jan Ceuleers wrote:
>>>>
>>>>
>>>>>I came across the following page:
>>>>>
>>>>>http://www.lesswatts.org/projects/powertop/known.php
>>>>>
>>>>>which says the following on ntpd:
>>>>>
>>>>>"By default, the ntp time synchronization daemon will wake up once per
>>>>>second, and will make the kernel do work on it's behalf even more. Red
>>>>>Hat has created a patch to ntp to fix this issue and ships it in their
>>>>>rawhide and FC7 ntp packages. You can download this patch from the
>>>>>Fedora cvs server."
>>>>>
>>>>>Has anyone here looked at that patch? Does it compromise correctness of
>>>>>the algorithms?
>>>>>
>>>>>Thanks, Jan

Evandro,

With respect, you miss the point. The ntpd does not require a tickle
every second just to scan for polls; it requires that tickle in order to
discipline the clcok frequency. The additional cycles necessary to link
to the next association structure, then increment and test a variable,
are way, way down in the noise.

Folks might not appreciate just how many counters are coincident with
the one-second interrupt. Every association has both a poll counter and
headway counter. Every cryptotraphic key has a lifetime counter. Several
drivers, includiing the WWVB and ACTS drivers, have internal counters
for protocol purposes. There are seconds counters for interface refresh,
autokey protocol cookie refresh, leapsecond countdown and hourly statistics.

While some of these functions could be managed by a timer queue
facility, most of the counters are routinely preempted. With a timer
queue facility, these operations would require overhead to sort queues
and manage hash tables. Since a one-second interrupt is necessary
anyway, extra complexity is simply not justified.

Dave

Evandro Menezes wrote:

> On May 15, 9:28 pm, "David L. Mills" wrote:
>
>>A timer interrupt is required each second to update the clock frequency
>>no matter what. In addition, a sweep is made through the associations to
>>see if a poll is pending. It would be in principle posssible to
>>implement a system of queues to avopid sweeping the associations each
>>second, but that would save very few cycles, add some more cycles and
>>additional complexity.
>
>
> NTP could set a reminder for itself not for the next second, in case
> there's a poll pending, but for the minimum period left among all
> polled servers. This would be pretty simple and power-friendly.
>
> Mind you, a CPU uses orders of magnitude less power in a stand-by
> state, even a simple halt-instruction, than running. See page 3 of
> http://download.intel.com/technology...ol10_art03.pdf
> for more info.
>
> HTH

Evandro and others,

Now it's me that missed the point. I didn't realize you were concerned
about a milliwatt or two every second. My first kneejerk reaction was
why would you use ntpd on a laptop under conditions where it might
sleep? Better to kill it before sleeping and restart when waking up. My
second jerk was, even if the seconds interrupt could be avoided, there
are still arriving and departing packets. I assume this wakes the beast,
although at 1024 s poll, that might not be a problem.

Well, let's consider the case of a tickless ntpd and see what breaks.
The first thing that breaks is the frequency discipline. As somebody
mentioned, that can be done in the kernel on the assumption that tick
interrupts dyill work. At a tick interrupt rate of 1000 Hz, this doesn't
seem a good idea. Or maybe the hardware can be programmed to adjust the
frequency. The frequency needs to be desciplined to the order of a few
parts in 10^9, which would require some unusual chipset capabilities.

A second approach might be to abandon frequency discipline except when a
packet shows up, which with laptops I know will considerably degrade the
accuracy, probablly to many tens of milliseconds, but this might not
matter if the machine is sleeping. When it comes awake; however, there
will ee nasty transient. Even more clever, anticipate the change due to
the calibrated frequency error and yank accordingly. To do this,
however, means a substantial modification of the clock discipline
algorithm and some kind os switch to know when to do this.

Next, just dropping in a timer queue facility makes no sense unless
those peskty seconds counters can be replaced by calculated intervals
that may have to be recalculated when some event or other happens. To do
this is a major redesign job. Even considering the effort and testing
requiree, it might be a worthwhile project better suited to an
implementation other than ntpd. Maybe openNTP or chrony would be a
better place to start.

Better yet, take the ntp_proto.c module from thedistribution, throw
everything else out and rebuild the infrastructure specialized for
laptops. I must disclose I have an ulterior motive here, since an
approach like this is needed for spacecraft.

Dave

Evandro Menezes wrote:

> On May 16, 12:29 pm, "David L. Mills" wrote:
>
>>In modern machines a timer interupt takes about one microsecond and to
>>scan through the one-second code is really quick. So, we are talking
>>about an overhead in the order of .00001 percent.
>
>
> In terms of performance, yes, but in terms of power, no. If NTP gets
> the CPU out of a deep stand-by state, then it may take hundreds of
> milliseconds for the CPU to go back to that state. Moreover, NTP 1s-
> timer may prevent the CPU from going to even deeper stand-by states.
>
> With this in mind, if NTP wakes the CPU up in order to do nothing,
> it's not doing the right thing, IMHO.
>
> HTH

David L. Mills wrote:
> packet shows up, which with laptops I know will considerably degrade the

I'm not convinced this is even about laptops. I think it is about PDAs,
or about embedded systems that may run for a year on a couple of AA
bateries, or may run on small photocell arrays.

David Woolley wrote:
> David L. Mills wrote:
>
>> packet shows up, which with laptops I know will considerably degrade the
>
>
> I'm not convinced this is even about laptops. I think it is about PDAs,
> or about embedded systems that may run for a year on a couple of AA
> bateries, or may run on small photocell arrays.

This is valid for every type of system that goes into powersave modes.

Even desktops do this on a regular basis these days.
AND this includes server type systems too.

Power Dissipation is an issue everywhere.

uwe

David L. Mills wrote:

> Better yet, take the ntp_proto.c module from thedistribution, throw
> everything else out and rebuild the infrastructure specialized for
> laptops. I must disclose I have an ulterior motive here, since an
> approach like this is needed for spacecraft.

Hi David,

Hand in Hand to having IP connectivity to missions?

Any mission that uses ntp (or lookalike) already?

What about all the other hassle:
doppler shift,
changing pathlength ( and thus changing transmit delays )
...

uwe

David Woolley wrote:
>> packet shows up, which with laptops I know will considerably degrade the
>
> I'm not convinced this is even about laptops. I think it is about PDAs,
> or about embedded systems that may run for a year on a couple of AA
> bateries, or may run on small photocell arrays.

I think that the lesswatts.org initiative (which should of course have
been called fewerwatts.org but that's another story) is about reducing
the power consumption of _all_ hardware that runs Linux, including
laptops, desktops, servers, embedded devices etc. I also think that ntpd
runs on a sizeable percentage of all such hardware that's in service out
there.

But that's not why I raised the question here. Ntpd's once-per-second
interrupt is nothing compared with the hundreds-to-thousands of wakeups
per second initiated by certain poorly-written hardware device drivers.
I just wanted to prompt a discussion on understanding the implications
of Red Hat's patch.

Application writers do (I think) have a responsibility to the planet to
verify/justify their application's impact on the platform's total power
consumption (and the lesswatts.org website provides tools for doing
that, e.g. powertop), but as I said I don't think that ntpd is an
especially power-hungry application.

The lesswatts.org site also mentions a range of other power-saving
measures in recent Linux kernels, including the bunching together of
wakeup events. Some applications have no need for very precise timers,
they just want to be woken up more-or-less-2s-from-now. The kernel is
then able to schedule a bunch of these imprecise timers at the same time
such that the number of wakeups is minimised.

Clearly ntpd does need precision and therefore probably must not use
this new class of imprecise timers, but I also don't know whether anyone
knows if the existence of the imprecise timers has a knock-on effect on
the precision of the standard timers. On the other hand, perhaps ntpd
_can_ use the imprecise timers provided it also has access to an
accurate platform time stamp when the timer fires.

Cheers, Jan