Darren Hart wrote:
George Anzinger wrote:
|First I want to express my joy that we are discussing these issues at
some depth.
~
The point is, the standard, low res, timer code needs to be only
minimally aware of the HR bits. On the other hand, since the HR timer
will be started on expiration of the low res timer, we need that
expiration to be aligned with the clock in a stable, predictable long
term way. (For what its worth, we have yet to address NTP clock
drifting in the HRT patch, so that is still a fly in this web of time.)
You are still dependent on jiffies which is very unreliable do to lost
ticks, HZ vs ACTHZ, etc. Even if you use a periodic tick, it seems the
HRT code would still benefit from a human-time soft-timers sub-system
that wasn't affected by such things.
Well, first we clean up jiffies WRT lost ticks. We just don't have them with
the HRT patch. If you mean being late, just as John's code give the right time
all the time so does the HRT time code. The notion is that the TSC or the
pm_counter can carry us over a couple of lost ticks as well as the between tick
times. So, we aren't affected by lost ticks and ACTHZ just is not part of the
POSIX clocks & timers world.
>
~
For what its worth, we have such a clock in HRT. It is expressed in
jiffies and arch_cycles, but jiffies is what is used today as the
"standard" for internal system time. This gets into the area of just
how to express time in areas where you need to quickly get and compare
the time. After a lot of though, I decided to use arch_cycles rather
than nanoseconds because arch_cycles are directly readable from the
hardware. Any other unit of time requires a conversion, and, as you
know, usually requires 64-bits as well. By staying with arch_cycles we
avoid "most" of the conversion overhead.
I can see why you might want to use arch_cycles, and at least it is an
absolute time. Jiffies though is not. Perhaps HRT could benefit from a
conversion to "milliseconds + arch_cycles" ?
Two points here, first, jiffies, once you convince yourself that the PIT is the
gold time standard, IS the time. It is the best time we have in the x86 world
and in all other archs too. That is what the arch time code is supposed to do.
Your milliseconds is, or should be, derived from jiffies or, in other archs,
the same place jiffies is derived from, i.e. the time keeping "rock" on the
mother board. To account for things like NTP, we always grab arch_cycles,
xtime, jiffies, and wall_to_monotonic under a read lock at the same time. This
allows us to peg one expression of time against another.
All that said, for HRT to work correctly, the timer must have a high resolution
time contained in its structure. Currently this is jiffies and arch_cycles.
Further, we need to know that when that jiffies value arrives, we will get
called ASAP, and not at some random time between that value and the next time it
changes. For repeating timers we use these values _after_ the timer expires to
figure the next expire time, so if they are changed by the timer code, we are in
trouble.
>
>
~
> I think currently, we do something similar to next_timer_interrupt(),
> making sure we update the stored value whenever we add a new timer, if
> necessary. Except now, we will determine the next time to set the hw
> timer to go off every time we expire timers.
Finding the next timer is a high overhead operation....
Perhaps it is now, but does it have to be? The process scheduler used
to be full of O(N) algorithms to, but they were all converted to O(1) by
doing several incremental calculations instead of one huge one. Perhaps
something similar could be done with timers by caching a couple of
timer expirations and modifying them as timers are added, removed, and
modified. Just brainstorming here.
Believe me I did a lot of "brainstorming" around how to keep HR timers along
with the LR timers. Until just recently I had a different timer list in timer.c
which was hashed on the low timer bits. After much thought and finally
realizing that MOST timers do NOT expire, I came to conclude that the current
list is just right given what it is currently used for. The stuff that is not
O(1) in this structure is the cascading. The reason this is not a big issue is
just that most timers are removed prior to the cascade.
In the list structure I used to use, I had to order timers by expire time,
accounting for both jiffies and arch_cycles. Now HRT uses the same old cascade
structure and the timer code, for the most part, ignores the arch_cycles member.
Only on expire is it discovered and the timer sent to the hrtime code where
the timer is entered in to a very short list of timers that are to expire some
time between now and the next jiffie. This is a very simple O(N/2) list, but it
is also really short. (This is a simplified discussion. The code is on the HRT
web site and in the HRT CVS on that site for the curious.)
>
~
--
George Anzinger [email protected]
High-res-timers: http://sourceforge.net/projects/high-res-timers/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]